Efficient Estimation of Pairwise Effective Resistance

Summary: AMC: improved Monte Carlo estimation reduces random-walk length and count with adaptive sampling while preserving accuracy. GEER: a greedy framework that pairs AMC with sparse mat-vecs for dramatic practical speedups, maintaining asymptotic guarantees. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6519
Venue: SIGMOD
Year: 2023
Pagerank: 4.7427524e-05
Overall Rank: 7,394 | 48.57%
DOI: 10.1145/3588696

Incoming Non-self Citations Over Time

Authors

1. Renchi Yang
2. Jing Tang

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,642	Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs	2025	SIGMOD	4.3109001e-05
10,075	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.1945683e-05
10,957	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,242	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	9.218875e-05
2,827	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.0551884e-05
4,527	On the Embeddability of Random Walk Distances	2013	VLDB	6.1083926e-05
4,671	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	6.0085645e-05
4,733	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	5.9631943e-05
5,015	Challenging the Long Tail Recommendation	2012	VLDB	5.7584513e-05
5,110	LightNE: A Lightweight Graph Processing System for Network Embedding	2021	SIGMOD	5.6901951e-05
5,702	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	5.36473e-05
5,763	Localizing Anomalous Changes in Time-evolving Graphs	2014	SIGMOD	5.3369426e-05
6,093	Density-based Place Clustering in Geo-Social Networks	2014	SIGMOD	5.2131159e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,210	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.2856573e-05
4,527	On the Embeddability of Random Walk Distances	2013	VLDB	6.1083926e-05
6,498	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD	5.0392468e-05
10,958	Efficient Approximation of Kemeny’s Constant for Large Graphs	2024	SIGMOD	4.1945683e-05
5,766	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD	5.3363253e-05
9,642	Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs	2025	SIGMOD	4.3109001e-05
5,702	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	5.36473e-05
9,325	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	4.3556432e-05
10,957	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	4.1945683e-05
9,245	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	4.3690661e-05