# Mixing Time Matters: Accelerating Effective Resistance Estimation via Bidirectional Method

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2025.

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

- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

We study the problem of efficiently approximating the textiteffective resistance (ER) on undirected graphs, where ER is a widely used node proximity measure with applications in graph spectral sparsification, multi-class graph clustering, network robustness analysis, graph machine learning, and more. Specifically, given any nodes s and t in an undirected graph G, we aim to efficiently estimate the ER value R(s,t) between nodes s and t, ensuring a small absolute error ε. The previous best algorithm for this problem has a worst-case computational complexity of tildeOleft(fracLmax3ε2 d2right), where the value of Lmax depends on the mixing time of random walks on G, d = mind(s), d(t), and d(s), d(t) denote the degrees of nodes s and t, respectively. We improve this complexity to tildeOleft(minleftfracLmax7/3ε2/3, fracLmax3ε2d2, mLmaxrightright), achieving a theoretical improvement of tildeOleft(maxleftfracLmax2/3ε4/3 d2, 1, fracLmax2ε2 d2 mrightright) over previous results. Here, m denotes the number of edges. Given that Lmax is often very large in real-world networks (e.g., Lmax > 104), our improvement on Lmax is significant, especially for real-world networks. We also conduct extensive experiments on real-world and synthetic graph datasets to empirically demonstrate the superiority of our method. The experimental results show that our method achieves a 10× to 1000× speedup in running time while maintaining the same absolute error compared to baseline methods.