論文の概要: Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach

• arxiv url: http://arxiv.org/abs/2412.10789v1
• Date: Sat, 14 Dec 2024 10:56:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 13:54:43.921303
• Title: Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
• Title（参考訳）: 大規模グラフ上でのグラフ伝搬計算のスケールアップ:ローカルなChebyshev近似アプローチ
• Authors: Yichun Yang, Rong-Hua Li, Meihao Liao, Longlong Lin, Guoren Wang,
• Abstract要約: グラフ伝播計算は、グラフデータ解析において重要な役割を果たす。 既存の手法は、主にパワーイテレーションやプッシュ計算に依存しており、収束率の遅い課題に直面していることが多い。 本稿では,Chebyshev PageRanksを用いた電力繰り返しとプッシュ手法を高速化する,新しい強力な手法を提案する。
• 参考スコア（独自算出の注目度）: 29.170926925450175
• License:
• Abstract: Graph propagation (GP) computation plays a crucial role in graph data analysis, supporting various applications such as graph node similarity queries, graph node ranking, graph clustering, and graph neural networks. Existing methods, mainly relying on power iteration or push computation frameworks, often face challenges with slow convergence rates when applied to large-scale graphs. To address this issue, we propose a novel and powerful approach that accelerates power iteration and push methods using Chebyshev polynomials. Specifically, we first present a novel Chebyshev expansion formula for general GP functions, offering a new perspective on GP computation and achieving accelerated convergence. Building on these theoretical insights, we develop a novel Chebyshev power iteration method (\ltwocheb) and a novel Chebyshev push method (\chebpush). Our \ltwocheb method demonstrates an approximate acceleration of $O(\sqrt{N})$ compared to existing power iteration techniques for both personalized PageRank and heat kernel PageRank computations, which are well-studied GP problems. For \chebpush, we propose an innovative subset Chebyshev recurrence technique, enabling the design of a push-style local algorithm with provable error guarantee and reduced time complexity compared to existing push methods. We conduct extensive experiments using 5 large real-world datasets to evaluate our proposed algorithms, demonstrating their superior efficiency compared to state-of-the-art approaches.
• Abstract（参考訳）: グラフ伝搬(GP)計算はグラフデータ解析において重要な役割を果たし、グラフノード類似性クエリ、グラフノードランキング、グラフクラスタリング、グラフニューラルネットワークなどの様々なアプリケーションをサポートする。 既存の手法は、主にパワーイテレーションやプッシュ計算フレームワークに依存しており、大規模なグラフに適用した場合、収束率の遅い課題に直面していることが多い。 この問題に対処するために,チェビシェフ多項式を用いた電力反復とプッシュ法を高速化する,新しい強力な手法を提案する。 具体的には、GP関数に対する新しいチェビシェフ展開式を初めて提示し、GP計算の新たな視点を提供し、加速収束を達成する。 これらの理論的知見に基づいて,チェビシェフ・パワー・イテレーション法 (\ltwocheb) とチェビシェフ・プッシュ法 (\chebpush) を開発した。 提案手法は,GP問題であるパーソナライズされたPageRankとヒートカーネルPageRankの双方に対して,既存の電力反復手法と比較して,O(\sqrt{N})$の近似加速度を実証する。 提案手法は,従来のプッシュ方式に比べて誤差の保証と時間的複雑さの低減が可能な,プッシュスタイルの局所アルゴリズムの設計を可能にする。 我々は,提案したアルゴリズムを評価するために,5つの大規模実世界のデータセットを用いて広範な実験を行い,最先端のアプローチと比較して優れた効率性を示す。

関連論文リスト

• Efficient Graph Condensation via Gaussian Process [11.304327316816561]
  グラフ凝縮は、性能を維持しながら大きなグラフのサイズを減らす。 既存の手法はしばしば二段階最適化に依存しており、広範囲なGNNトレーニングとスケーラビリティの制限を必要とする。 本稿では,ガウス過程を用いたグラフ凝縮法(GCGP)を提案する。
  論文  参考訳（メタデータ） (2025-01-05T14:43:07Z)
• Convergence Guarantees for the DeepWalk Embedding on Block Models [9.898607871253775]
  ブロックモデル(SBM)から得られたグラフ上でDeepWalkアルゴリズムの使い方を示す。 単純化されているにもかかわらず、SBMは大きなグラフ上のアルゴリズムを解析するための古典的なモデルであることが証明されている。
  論文  参考訳（メタデータ） (2024-10-26T18:35:11Z)
• FIT-GNN: Faster Inference Time for GNNs Using Coarsening [1.323700980948722]
  粗大化に基づく手法は、グラフをより小さなグラフに減らし、より高速な計算をもたらす。 従来の研究は、推論フェーズにおける計算コストに十分な対処を行っていなかった。 本稿では,GNNの学習と推論の両段階における計算負担を軽減することにより,GNNのスケーラビリティを向上させる新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-10-19T06:27:24Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• Benchmarking Node Outlier Detection on Graphs [90.29966986023403]
  グラフの外れ値検出は、多くのアプリケーションにおいて、新しいが重要な機械学習タスクである。 UNODと呼ばれるグラフに対して、最初の包括的教師なしノード外乱検出ベンチマークを示す。
  論文  参考訳（メタデータ） (2022-06-21T01:46:38Z)
• Evolving-Graph Gaussian Processes [20.065168755580558]
  既存のアプローチでは静的構造に重点を置いているが、実際のグラフデータの多くは動的構造を表しており、GGPの応用は制限されている。 我々はこれを克服するために進化的グラフガウス過程(e-GGP)を提案する。 静的グラフガウスプロセスアプローチに対するe-GGPの利点を実証する。
  論文  参考訳（メタデータ） (2021-06-29T07:16:04Z)
• Scaling Up Graph Neural Networks Via Graph Coarsening [18.176326897605225]
  グラフニューラルネットワーク(GNN)のスケーラビリティは、マシンラーニングにおける大きな課題のひとつだ。 本稿では,GNNのスケーラブルなトレーニングにグラフ粗大化を用いることを提案する。 既成の粗大化法を単純に適用すれば,分類精度を著しく低下させることなく,ノード数を最大10倍に削減できることを示す。
  論文  参考訳（メタデータ） (2021-06-09T15:46:17Z)
• Progressive Spatio-Temporal Graph Convolutional Network for Skeleton-Based Human Action Recognition [97.14064057840089]
  本稿では,グラフ畳み込みネットワークのためのコンパクトで問題固有のネットワークを,段階的に自動的に見つける手法を提案する。 骨格に基づく人体行動認識のための2つのデータセットの実験結果から,提案手法は競争力あるいはより優れた分類性能を有することが示された。
  論文  参考訳（メタデータ） (2020-11-11T09:57:49Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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