Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs

Summary: Introduces an index for effective resistance on evolving graphs based on preserving samples of random walks and loop-erased walks instead of matrices. Edge updates map to landmark-node updates; two update algorithms (random-walk and loop-erased-walk) support cycle-decomposition to update samples in O(1) per edge, yielding up to 100x speedups on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7033
Venue: SIGMOD
Year: 2025
Pagerank: 4.3109001e-05
Overall Rank: 9,642 | 32.93%
DOI: 10.1145/3709686

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,075	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.1945683e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
313	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00028097557
486	Fast Incremental and Personalized PageRank	2011	VLDB	0.00022068545
1,821	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00010423565
2,210	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.2856573e-05
2,537	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	8.5834428e-05
5,655	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.387631e-05
6,093	Density-based Place Clustering in Geo-Social Networks	2014	SIGMOD	5.2131159e-05
7,086	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	4.8381004e-05
7,394	Efficient Estimation of Pairwise Effective Resistance	2023	SIGMOD	4.7427524e-05
9,245	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	4.3690661e-05
10,957	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,028	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	4.1945683e-05
4,922	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	5.8233726e-05
2,436	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.8252104e-05
10,159	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD	4.1945683e-05
11,044	Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation	2024	VLDB	4.1945683e-05
10,075	Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach	2026	SIGMOD	4.1945683e-05
7,323	Dynamic Influence Analysis in Evolving Networks	2016	VLDB	4.7625647e-05
5,655	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	5.387631e-05
9,245	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	4.3690661e-05
10,957	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	4.1945683e-05