Mixing Time Matters: Accelerating Effective Resistance Estimation via Bidirectional Method

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.