# Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs

arXiv: https://arxiv.org/abs/2601.11159 · HTML: https://mlsanity.com/paper/2601.11159/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 52 references that are in the map.
- First posted on arXiv 16 Jan 2026.

## Builds on (most cited first, 24 of 24)

- [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [Analysis of stochastic Lanczos quadrature for spectrum approximation](https://mlsanity.com/paper/2105.06595/) (2021)
- [Stability of the Lanczos Method for Matrix Function Approximation](https://mlsanity.com/paper/1708.07788/) (2017)
- [Graph Clustering using Effective Resistance](https://mlsanity.com/paper/1711.06530/) (2017)
- [Efficient Estimation of Heat Kernel PageRank for Local Clustering](https://mlsanity.com/paper/1904.02707/) (2019)
- [Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions](https://mlsanity.com/paper/1805.12051/) (2018)
- [Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push](https://mlsanity.com/paper/2101.03652/) (2021)
- [Personalized PageRank Estimation and Search: A Bidirectional Approach](https://mlsanity.com/paper/1507.05999/) (2015)
- [Personalized PageRank to a Target Node](https://mlsanity.com/paper/1304.4658/) (2013)
- [Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs](https://mlsanity.com/paper/2003.01282/) (2020)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [Robust and Practical Solution of Laplacian Equations by Approximate Elimination](https://mlsanity.com/paper/2303.00709/) (2023)
- [Computing Maximum Flow with Augmenting Electrical Flows](https://mlsanity.com/paper/1608.06016/) (2016)
- [On Solving Linear Systems in Sublinear Time](https://mlsanity.com/paper/1809.02995/) (2018)
- [Efficient Estimation of Pairwise Effective Resistance](https://mlsanity.com/paper/2312.06123/) (2023)
- [Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers](https://mlsanity.com/paper/2112.00722/) (2021)
- [Towards Optimal Effective Resistance Estimation](https://mlsanity.com/paper/2306.14820/) (2023)
- [Effective Resistances in Non-Expander Graphs](https://mlsanity.com/paper/2307.01218/) (2023)
- [Improved Spectral Density Estimation via Explicit and Implicit Deflation](https://mlsanity.com/paper/2410.21690/) (2024)
- [A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs](https://mlsanity.com/paper/2211.01468/) (2022)
- [Mixing Time Matters: Accelerating Effective Resistance Estimation via Bidirectional Method](https://mlsanity.com/paper/2503.02513/) (2025)
- [Improved Algorithms for Effective Resistance Computation on Graphs](https://mlsanity.com/paper/2507.04674/) (2025)

## Abstract (arXiv)

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 kappa, 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 kappa. 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 tildeO(√kappa m) (m is the number of edges of the graph and tildeO means the complexity omitting the log terms) which achieves a speedup of √kappa compared to previous power iteration-based global methods. For Lanczos Push, we demonstrate that its time complexity is tildeO(kappa2.75) under certain mild and frequently established assumptions, which represents a significant improvement of kappa0.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.