Fast and Exact Top-k Search for Random Walk with Restart

Summary: K-dash delivers fast, exact top-k search for Random Walk with Restart via sparse-matrix proximity and pruning of unnecessary computations. Theoretical guarantees ensure exactness, with experiments showing speedups over prior methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10491
Venue: VLDB
Year: 2012
Pagerank: 0.00011047924
Overall Rank: 1,641 | 88.59%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,821	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00010423565
1,920	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010090791
2,098	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.5480012e-05
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
2,827	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.0551884e-05
3,709	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	6.8242482e-05
3,872	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	6.6785582e-05
4,733	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	5.9631943e-05
5,946	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.2616887e-05
6,865	Indexed Fast Network Proximity Querying	2018	VLDB	4.9041884e-05
7,086	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	4.8381004e-05
7,157	The Minimum Wiener Connector Problem	2015	SIGMOD	4.8144713e-05
9,325	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	4.3556432e-05
10,666	LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration	2025	VLDB	4.1945683e-05
11,027	BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank	2024	VLDB	4.1945683e-05
11,787	Scaling Locally Linear Embedding	2017	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
756	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00017088023
768	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.00016919065
900	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015495155
917	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00015370124
1,285	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00012833377

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,807	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9092289e-05
7,276	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.7798595e-05
4,922	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	5.8233726e-05
8,019	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD	4.6041407e-05
1,073	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00014264992
4,791	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9188595e-05
7,277	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	4.7794907e-05
8,505	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.4958064e-05
1,920	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010090791
5,946	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.2616887e-05