2025/03/04 by Cui, Guanyu, Wang, Hanzhi, Wei, Zhewei · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Social and Information Networks (cs.SI)
paper · doi:10.48550/arxiv.2503.02513
We study the problem of efficiently approximating the effective 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 O(\fracLmax3ε2 d2), where the value of Lmax depends on the mixing time of random walks on G, d = min\d(s), d(t)\, and d(s), d(t) denote the degrees of nodes s and t, respectively. We improve this complexity to O(min\\fracLmax7/3ε2/3, \fracLmax3ε2d2, mLmax\), achieving a theoretical improvement of O(max\\fracLmax2/3ε4/3 d2, 1, \fracLmax2ε2 d2 m\) 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.