Efficient Estimation of Pairwise Effective Resistance

Renchi Yang, Jing Tang*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review


Given an undirected graph G, the effective resistance r(s,t) measures the dissimilarity of node pair s,t in G, which finds numerous applications in real-world problems, such as recommender systems, combinatorial optimization, molecular chemistry, and electric power networks. Existing techniques towards pairwise effective resistance estimation either trade approximation guarantees for practical efficiency, or vice versa. In particular, the state-of-the-art solution is based on a multitude of Monte Carlo random walks, rendering it rather inefficient in practice, especially on large graphs.

Motivated by this, this paper first presents an improved Monte Carlo approach, AMC, which reduces both the length and amount of random walks required without degrading the theoretical accuracy guarantee, through careful theoretical analysis and an adaptive sampling scheme. Further, we develop a greedy approach, GEER, which combines AMC with sparse matrix-vector multiplications in an optimized and non-trivial way. GEER offers significantly improved practical efficiency over AMC without compromising its asymptotic performance and accuracy guarantees. Extensive experiments on multiple benchmark datasets reveal that GEER is orders of magnitude faster than the state of the art in terms of computational time when achieving the same accuracy.
Original languageEnglish
Article number16
Number of pages27
JournalProceedings of the ACM on Management of Data
Issue number1
Publication statusPublished - May 2023

User-Defined Keywords

  • matrix multiplication
  • random walk
  • effective resistance


Dive into the research topics of 'Efficient Estimation of Pairwise Effective Resistance'. Together they form a unique fingerprint.

Cite this