# Local Algorithms for Estimating Effective Resistance

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 38 references that are in the map.
- First posted on arXiv 7 Jun 2021.

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

- [Graph Clustering using Effective Resistance](https://mlsanity.com/paper/1711.06530/) (2017)
- [Testing Graph Clusterability: Algorithms and Lower Bounds](https://mlsanity.com/paper/1808.04807/) (2018)
- [Personalized PageRank Estimation and Search: A Bidirectional Approach](https://mlsanity.com/paper/1507.05999/) (2015)
- [FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs](https://mlsanity.com/paper/1404.3181/) (2014)
- [Fast Generation of Random Spanning Trees and the Effective Resistance Metric](https://mlsanity.com/paper/1501.00267/) (2015)
- [Fast Bidirectional Probability Estimation in Markov Models](https://mlsanity.com/paper/1507.05998/) (2015)
- [On Solving Linear Systems in Sublinear Time](https://mlsanity.com/paper/1809.02995/) (2018)
- [Approximating the Stationary Probability of a Single State in a Markov chain](https://mlsanity.com/paper/1312.1986/) (2013)
- [Analyzing Location-Based Advertising for Vehicle Service Providers Using Effective Resistances](https://mlsanity.com/paper/1902.02429/) (2019)

## Built on by (most cited first, 6 of 6)

- [Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification](https://mlsanity.com/paper/2506.16110/) (2025)
- [A Fast Algorithm for Moderating Critical Nodes via Edge Removal](https://mlsanity.com/paper/2309.06392/) (2023)
- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)
- [Structure-Aware Spectral Sparsification via Uniform Edge Sampling](https://mlsanity.com/paper/2510.12669/) (2025)
- [Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model](https://mlsanity.com/paper/2509.13112/) (2025)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

Effective resistance is an important metric that measures the similarity of two vertices in a graph. It has found applications in graph clustering, recommendation systems and network reliability, among others. In spite of the importance of the effective resistances, we still lack efficient algorithms to exactly compute or approximate them on massive graphs. In this work, we design several local algorithms for estimating effective resistances, which are algorithms that only read a small portion of the input while still having provable performance guarantees. To illustrate, our main algorithm approximates the effective resistance between any vertex pair s,t with an arbitrarily small additive error varepsilon in time O(poly(log n/varepsilon)), whenever the underlying graph has bounded mixing time. We perform an extensive empirical study on several benchmark datasets, validating the performance of our algorithms.