論文の概要: Faster Local Solvers for Graph Diffusion Equations

• arxiv url: http://arxiv.org/abs/2410.21634v2
• Date: Sun, 22 Dec 2024 08:03:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-24 15:51:02.459303
• Title: Faster Local Solvers for Graph Diffusion Equations
• Title（参考訳）: グラフ拡散方程式の高速局所解法
• Authors: Jiahe Bai, Baojian Zhou, Deqing Yang, Yanghua Xiao,
• Abstract要約: グラフ拡散方程式(GDE)は、クラスタリング、ニューラルネットワークのトレーニング、その他多くのグラフ関連の問題に不可欠である。 既存の反復的な手法では、イテレーション毎にグラフ全体にアクセスする必要があり、大規模なグラフには時間がかかる。 本稿では,局所拡散プロセスを用いてGDEを近似的に解くための新しいフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 44.198609457344574
• License:
• Abstract: Efficient computation of graph diffusion equations (GDEs), such as Personalized PageRank, Katz centrality, and the Heat kernel, is crucial for clustering, training neural networks, and many other graph-related problems. Standard iterative methods require accessing the whole graph per iteration, making them time-consuming for large-scale graphs. While existing local solvers approximate diffusion vectors through heuristic local updates, they often operate sequentially and are typically designed for specific diffusion types, limiting their applicability. Given that diffusion vectors are highly localizable, as measured by the participation ratio, this paper introduces a novel framework for approximately solving GDEs using a local diffusion process. This framework reveals the suboptimality of existing local solvers. Furthermore, our approach effectively localizes standard iterative solvers by designing simple and provably sublinear time algorithms. These new local solvers are highly parallelizable, making them well-suited for implementation on GPUs. We demonstrate the effectiveness of our framework in quickly obtaining approximate diffusion vectors, achieving up to a hundred-fold speed improvement, and its applicability to large-scale dynamic graphs. Our framework could also facilitate more efficient local message-passing mechanisms for GNNs.
• Abstract（参考訳）: パーソナライズされたPageRank、Katz Centrality、Heat kernelなどのグラフ拡散方程式(GDE)の効率的な計算は、クラスタリング、ニューラルネットワークのトレーニング、その他多くのグラフ関連の問題に不可欠である。 標準的な反復法では、イテレーション毎にグラフ全体にアクセスする必要があり、大規模なグラフには時間がかかる。 既存の局所解法は、ヒューリスティックな局所更新を通じて拡散ベクトルを近似するが、しばしば連続的に動作し、典型的には特定の拡散型のために設計され、適用性を制限する。 本稿では, 拡散ベクトルの局所化が極めて重要であることを考慮し, 局所拡散法を用いてGDEを近似的に解くための新しい枠組みを提案する。 この枠組みは、既存の局所解法の準最適性を明らかにする。 さらに,本手法は,単純かつ証明可能なサブ線形時間アルゴリズムを設計することにより,標準反復解法を効果的にローカライズする。 これらの新しいローカルソルバは高度に並列化可能であり、GPUの実装に適している。 本稿では, 近似拡散ベクトルを高速に取得し, 最大100倍の高速化を実現し, 大規模動的グラフへの適用性を示す。 我々のフレームワークは、GNNのより効率的なローカルメッセージパッシング機構を促進することができる。

関連論文リスト

• MassiveGNN: Efficient Training via Prefetching for Massively Connected Distributed Graphs [11.026326555186333]
  本稿では,現在最先端のAmazon DistDGL分散GNNフレームワーク上に,パラメータ化された連続プリフェッチと消去方式を提案する。 NERSC(National Energy Research Scientific Computing Center)のPerlmutterスーパーコンピュータでは、エンドツーエンドのトレーニング性能が15～40%向上している。
  論文  参考訳（メタデータ） (2024-10-30T05:10:38Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• Advective Diffusion Transformers for Topological Generalization in Graph Learning [69.2894350228753]
  グラフ拡散方程式は、様々なグラフトポロジーの存在下で、どのように外挿して一般化するかを示す。 本稿では,新たなグラフエンコーダのバックボーンであるAdvective Diffusion Transformer (ADiT)を提案する。
  論文  参考訳（メタデータ） (2023-10-10T08:40:47Z)
• Communication-Free Distributed GNN Training with Vertex Cut [63.22674903170953]
  CoFree-GNNは、コミュニケーションのないトレーニングを実装することで、トレーニングプロセスを大幅に高速化する、分散GNNトレーニングフレームワークである。 我々は、CoFree-GNNが既存の最先端のGNNトレーニングアプローチよりも最大10倍高速なGNNトレーニングプロセスを実証した。
  論文  参考訳（メタデータ） (2023-08-06T21:04:58Z)
• Distributed Graph Embedding with Information-Oriented Random Walks [16.290803469068145]
  グラフ埋め込みはグラフノードを低次元ベクトルにマッピングし、機械学習タスクで広く採用されている。 数十億のエッジグラフを埋め込むためにスケール可能な,汎用的で分散された情報中心のランダムウォークベースのグラフ埋め込みフレームワークであるDistGERを提案する。 D DistGERは2.33x-129x加速、機械間通信の45%削減、下流タスクの10%改善を示す。
  論文  参考訳（メタデータ） (2023-03-28T03:11:21Z)
• Capturing Graphs with Hypo-Elliptic Diffusions [7.704064306361941]
  ランダムウォークの分布はグラフラプラシアンを用いて定義された拡散方程式に従って進化することを示す。 この結果、テンソル値のグラフ作用素が新しくなり、これは下楕円グラフラプラシアン (Laplacian) と呼ばれる。 本手法は,長距離推論を必要とするデータセット上のグラフ変換器と競合するが,エッジ数では線形にしかスケールしないことを示す。
  論文  参考訳（メタデータ） (2022-05-27T16:47:34Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Local Permutation Equivariance For Graph Neural Networks [2.208242292882514]
  そこで我々は,局所置換同変グラフニューラルネットワークという新しい手法を開発した。 ローカルノード近傍で動作するグラフニューラルネットワークを構築するためのフレームワークを提供する。 提案手法を,グラフベンチマークの分類タスクの範囲で実験的に検証する。
  論文  参考訳（メタデータ） (2021-11-23T13:10:34Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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