Back to papers
Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach
Summary: Index-based effective-resistance computation via multiple landmarks: precompute compact Schur-complement matrices over a landmark set, then answer single-pair/source queries with Vl-absorbed random-walk push/sampling. Provable accuracy/performance guarantees; up to 10^4× speedup on large graphs.
(summarized by gpt-5.4-mini on May 24 2026)
- Paper ID
- 6898
- Venue
- SIGMOD
- Year
- 2024
- Pagerank
- 4.1945683e-05
- Overall Rank
- 10,957 | 23.78%
- DOI
-
10.1145/3654936
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 18 of 18 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 260 |
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling |
2013 |
SIGMOD |
0.00030040036 |
| 708 |
Near Neighbor Search in Large Metric Spaces |
1995 |
VLDB |
0.00017772684 |
| 1,821 |
Computing Personalized PageRank Quickly by Exploiting Graph Structures |
2014 |
VLDB |
0.00010423565 |
| 2,201 |
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks |
2018 |
SIGMOD |
9.3048105e-05 |
| 2,210 |
BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs |
2015 |
SIGMOD |
9.2856573e-05 |
| 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,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,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 |
| 6,200 |
k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation |
2016 |
VLDB |
5.1602201e-05 |
| 6,309 |
Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks |
2018 |
SIGMOD |
5.1167347e-05 |
| 7,394 |
Efficient Estimation of Pairwise Effective Resistance |
2023 |
SIGMOD |
4.7427524e-05 |
| 8,256 |
Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement |
2022 |
VLDB |
4.5490743e-05 |
| 9,245 |
Efficient Resistance Distance Computation: the Power of Landmark-based Approaches |
2023 |
SIGMOD |
4.3690661e-05 |
| 9,325 |
Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches |
2023 |
SIGMOD |
4.3556432e-05 |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 6,989 |
Effective Indexing for Dynamic Structural Graph Clustering |
2022 |
VLDB |
4.8716197e-05 |
| 2,117 |
Efficient SimRank-based Similarity Join Over Large Graphs |
2013 |
VLDB |
9.5155578e-05 |
| 10,159 |
Efficient Influential Community Search over Dynamic Graphs |
2026 |
SIGMOD |
4.1945683e-05 |
| 7,394 |
Efficient Estimation of Pairwise Effective Resistance |
2023 |
SIGMOD |
4.7427524e-05 |
| 2,436 |
Efficient Structural Graph Clustering: An Index-Based Approach |
2018 |
VLDB |
8.8252104e-05 |
| 7,428 |
DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs |
2022 |
VLDB |
4.7320892e-05 |
| 9,483 |
I/O Efficient Label-Constrained Reachability Queries in Large Graphs |
2024 |
VLDB |
4.3341665e-05 |
| 10,075 |
Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach |
2026 |
SIGMOD |
4.1945683e-05 |
| 9,642 |
Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs |
2025 |
SIGMOD |
4.3109001e-05 |
| 9,245 |
Efficient Resistance Distance Computation: the Power of Landmark-based Approaches |
2023 |
SIGMOD |
4.3690661e-05 |