Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs
Preprint
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.
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Improved Spectral Density Estimation via Explicit and Implicit Deflation2025
- Stability of the Lanczos algorithm on matrices with regular spectral distributionsLinear Algebra and its Applications, 2023
- Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle DecompositionsSIAM Journal on Computing, 2020
- Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator2012
- Multiplying matrices faster than coppersmith-winograd2012
- Fast Matrix Computations for Pairwise and Columnwise Commute Times and Katz ScoresInternet Mathematics, 2012
- The heat kernel as the pagerank of a graphProceedings of the National Academy of Sciences, 2007
- The Lanczos and conjugate gradient algorithms in finite precision arithmeticActa Numerica, 2006
- Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power qJournal of Combinatorial Theory, Series B, 1994
- Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblemLinear Algebra and its Applications, 1980