Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs

Summary: Introduces Lanczos Iteration and Lanczos Push for resistance distances, reducing Laplacian-condition-number dependence. The global method runs in Õ(√κm), while the local method is graph-size independent (Õ(κ^2.75)), with superior empirical accuracy and speed. (summarized by gpt-5.6-luna on Jul 09 2026)

Paper ID: 14310
Venue: VLDB
Year: 2026
Pagerank: 4.1905499e-05
Overall Rank: 10,272 | 28.61%
DOI: 10.14778/3811243.3811244

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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,522	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.6029608e-05
5,000	Density-based Place Clustering in Geo-Social Networks	2014	SIGMOD	5.7636502e-05
5,237	Edge-based Local Push for Personalized PageRank	2022	VLDB	5.6071758e-05
5,713	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	5.3595796e-05
5,936	Efficient Estimation of Pairwise Effective Resistance	2023	SIGMOD	5.2611905e-05
9,252	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	4.3648789e-05
9,641	Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs	2025	SIGMOD	4.3067693e-05
10,075	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.1905499e-05
10,960	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,713	Efficient Estimation of Heat Kernel PageRank for Local Clustering	2019	SIGMOD	5.3595796e-05
5,936	Efficient Estimation of Pairwise Effective Resistance	2023	SIGMOD	5.2611905e-05
1,907	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010130702
2,522	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.6029608e-05
6,206	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1522897e-05
11,051	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1905499e-05
10,075	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.1905499e-05
9,641	Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs	2025	SIGMOD	4.3067693e-05
10,960	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	4.1905499e-05
9,252	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	4.3648789e-05