論文の概要: Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs

• arxiv url: http://arxiv.org/abs/2601.11159v1
• Date: Fri, 16 Jan 2026 10:22:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-19 20:21:50.445578
• Title: Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs
• Title（参考訳）: 大規模グラフ上での抵抗距離計算の理論的および実用的解法
• Authors: Yichun Yang, Longlong Lin, Rong-Hua Li, Meihao Liao, Guoren Wang,
• Abstract要約: Lanczos Iteration と Lanczos Push は、大きなグラフ上での抵抗を計算するための効率的なアルゴリズムとして提示される。 様々なサイズと統計特性の8つの実世界のデータセットに関する広範な実験を通じて、我々のアルゴリズムを検証する。
• 参考スコア（独自算出の注目度）: 39.163609792464506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The computation of resistance distance is pivotal in a wide range of graph analysis applications, including graph clustering, link prediction, and graph neural networks. Despite its foundational importance, efficient algorithms for computing resistance distances on large graphs are still lacking. Existing state-of-the-art (SOTA) methods, including power iteration-based algorithms and random walk-based local approaches, often struggle with slow convergence rates, particularly when the condition number of the graph Laplacian matrix, denoted by $κ$, is large. To tackle this challenge, we propose two novel and efficient algorithms inspired by the classic Lanczos method: Lanczos Iteration and Lanczos Push, both designed to reduce dependence on $κ$. Among them, Lanczos Iteration is a near-linear time global algorithm, whereas Lanczos Push is a local algorithm with a time complexity independent of the size of the graph. More specifically, we prove that the time complexity of Lanczos Iteration is $\tilde{O}(\sqrtκ m)$ ($m$ is the number of edges of the graph and $\tilde{O}$ means the complexity omitting the $\log$ terms) which achieves a speedup of $\sqrtκ$ compared to previous power iteration-based global methods. For Lanczos Push, we demonstrate that its time complexity is $\tilde{O}(κ^{2.75})$ under certain mild and frequently established assumptions, which represents a significant improvement of $κ^{0.25}$ over the SOTA random walk-based local algorithms. We validate our algorithms through extensive experiments on eight real-world datasets of varying sizes and statistical properties, demonstrating that Lanczos Iteration and Lanczos Push significantly outperform SOTA methods in terms of both efficiency and accuracy.
• Abstract（参考訳）: グラフクラスタリング、リンク予測、グラフニューラルネットワークなど、幅広いグラフ解析アプリケーションでは、抵抗距離の計算が重要である。 基礎的な重要性にもかかわらず、大きなグラフ上の抵抗距離を計算するための効率的なアルゴリズムはいまだに不足している。 パワーイテレーションに基づくアルゴリズムやランダムウォークに基づく局所的アプローチを含む既存の最先端(SOTA)手法は、特にκ$で表されるグラフラプラシアン行列の条件数が大きい場合、収束速度の低下に苦慮することが多い。 この課題に対処するために、Laczos IterationとLaczos Pushという古典的なLaczos法に着想を得た2つの新しい効率的なアルゴリズムを提案する。 中でも、Lanczos Iterationは、ほぼ線形の時間的グローバルアルゴリズムであるのに対し、Lanczos Pushは、グラフのサイズに依存しない時間的複雑さを持つ局所的なアルゴリズムである。 より具体的には、Lanczos Iterationの時間複雑性が$\tilde{O}(\sqrtκ m)$$$m$はグラフのエッジの数であり、$\tilde{O}$は$\log$項を省略する複雑性を意味する。 Lanczos Push は、時間複雑性が$\tilde{O}(κ^{2.75})$であることを示すが、これはSOTAランダムウォークに基づく局所アルゴリズムよりも κ^{0.25}$ を大幅に改善したことを意味する。 その結果,Laczos Iteration と Lanczos Push は効率と精度の両方でSOTA法を著しく上回る結果となった。

関連論文リスト

• Distributed Learning over Arbitrary Topology: Linear Speed-Up with Polynomial Transient Time [3.1789549088190414]
  本研究では, ピアツーピア通信によるローカルコスト関数の和を協調的に共有する分散学習問題について検討する。 本稿では、一般的な通信グラフから抽出した2本の木を用いて、モデルパラメータと位相パラメータの両方を分散する新しいEmph Tree PushPull-(STPP)を提案する。
  論文  参考訳（メタデータ） (2025-03-20T13:11:44Z)
• Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs [14.049529046098607]
  スパースグラフに対する一般ランダムウォークカーネル(RWK)の非バイアス近似のための最初の線形時間複雑性ランダム化アルゴリズムを提案する。 提案手法は,大規模グラフ上での効率的な計算において,最大$mathbf27timesの高速化を実現する。
  論文  参考訳（メタデータ） (2024-10-14T10:48:46Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Local Algorithms for Estimating Effective Resistance [26.54556748340991]
  本研究では,大規模グラフ上での有効抵抗を推定するための複数のエンファンローカアルゴリズムを設計する。 主アルゴリズムは任意の頂点対 $s,t$ と任意に小さな加算誤差の間の有効抵抗を近似する。 いくつかのベンチマークデータセットについて広範な実験を行い、アルゴリズムを検証した。
  論文  参考訳（メタデータ） (2021-06-07T10:08:12Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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