論文の概要: Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs

• arxiv url: http://arxiv.org/abs/2003.01282v1
• Date: Tue, 3 Mar 2020 01:25:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-26 23:28:41.443874
• Title: Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs
• Title（参考訳）: 近似するときのslaq: webスケールグラフの正確なスペクトル距離
• Authors: Anton Tsitsulin, Marina Munkhoeva, Bryan Perozzi
• Abstract要約: 本研究では,数十億のノードとエッジを持つグラフ間のスペクトル距離を計算するための,効率的かつ効率的な近似手法であるSLaQを提案する。 SLaQは既存の手法よりも優れており、近似精度は数桁向上することが多い。
• 参考スコア（独自算出の注目度）: 6.72542623686684
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph comparison is a fundamental operation in data mining and information retrieval. Due to the combinatorial nature of graphs, it is hard to balance the expressiveness of the similarity measure and its scalability. Spectral analysis provides quintessential tools for studying the multi-scale structure of graphs and is a well-suited foundation for reasoning about differences between graphs. However, computing full spectrum of large graphs is computationally prohibitive; thus, spectral graph comparison methods often rely on rough approximation techniques with weak error guarantees. In this work, we propose SLaQ, an efficient and effective approximation technique for computing spectral distances between graphs with billions of nodes and edges. We derive the corresponding error bounds and demonstrate that accurate computation is possible in time linear in the number of graph edges. In a thorough experimental evaluation, we show that SLaQ outperforms existing methods, oftentimes by several orders of magnitude in approximation accuracy, and maintains comparable performance, allowing to compare million-scale graphs in a matter of minutes on a single machine.
• Abstract（参考訳）: グラフ比較はデータマイニングと情報検索の基本的な操作である。 グラフの組合せ的性質から、類似度尺度の表現性とその拡張性をバランスさせることは困難である。 スペクトル分析はグラフのマルチスケール構造を研究するための重要なツールを提供し、グラフ間の差異を推論するのに適した基礎である。 しかし、大きなグラフの完全スペクトルの計算は計算が禁じられているため、スペクトルグラフ比較法は誤差保証の弱い粗い近似手法に依存することが多い。 本研究では,数十億のノードとエッジを持つグラフ間のスペクトル距離を計算するための効率的かつ効率的な近似手法であるslaqを提案する。 対応する誤差境界を導出し、グラフエッジ数で時間線形に正確な計算が可能であることを実証する。 徹底的な実験評価により,slaqは既存の手法よりも優れており,近似精度では数桁の精度で精度が向上し,性能も同等であり,1台のマシンで数分間で100万のグラフを比較することができることを示した。

関連論文リスト

• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  本稿では,グラフ上の分布と信号の間の新しい距離を提案する。 GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。 グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
  論文  参考訳（メタデータ） (2023-06-05T00:01:17Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。 その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
  論文  参考訳（メタデータ） (2022-12-08T23:36:00Z)
• A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs [13.954735096637298]
  そこで我々は,グラフスペクトルの空間分布がグラフスペクトルに与える影響を解析し,グラフニューラルネットワーク(GNN)の高密度グラフとスパースグラフのノード分類における性能について検討した。 GNNはスパースグラフのスペクトル法よりも優れており、これらの結果を合成グラフと実グラフの両方で数値例で示すことができる。
  論文  参考訳（メタデータ） (2022-11-06T22:38:13Z)
• Learning Product Graphs from Spectral Templates [3.04585143845864]
  グラフ学習(GL)は、データマイニングと機械学習(ML)におけるコネクションの推論と分析の核である 複雑度を著しく低減した製品スペクトルテンプレートからの学習製品(高次元)グラフを提案する。 現在の稀なアプローチとは対照的に、我々のアプローチはグラフ製品の種類を知ることなく、あらゆる種類の製品グラフを学習することができる。
  論文  参考訳（メタデータ） (2022-11-05T12:28:11Z)
• FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
  グラフ比較は、グラフ間の類似点と相違点の識別を扱う。 大きな障害は、グラフの未知のアライメントと、正確で安価な比較指標の欠如である。 本研究では,フィルタグラフ距離近似を導入する。
  論文  参考訳（メタデータ） (2021-09-09T17:43:07Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Understanding Coarsening for Embedding Large-Scale Graphs [3.6739949215165164]
  機械学習(ML)アルゴリズムによるグラフの適切な解析は、研究や産業の多くの分野において、より深い洞察をもたらす可能性がある。 グラフデータの不規則構造は、グラフ上でMLタスクを実行するための障害を構成する。 本研究では, 粗大化品質が埋込み性能に及ぼす影響を, 速度と精度の両方で解析する。
  論文  参考訳（メタデータ） (2020-09-10T15:06:33Z)
• Graph topology inference benchmarks for machine learning [16.857405938139525]
  本稿では,グラフ推論手法の相対的メリットと限界を明らかにするために,いくつかのベンチマークを導入する。 我々はまた、文学において最も顕著な技法のいくつかを対比している。
  論文  参考訳（メタデータ） (2020-07-16T09:40:32Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。