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: 10492
Venue: VLDB
Year: 2012
Pagerank: 0.0001108491
Overall Rank: 1,626 | 88.71%
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,809	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00010472588
1,907	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010130702
2,076	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.6057342e-05
2,189	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.3358152e-05
2,515	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	8.6115215e-05
2,522	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.6029608e-05
3,715	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	6.8176818e-05
3,853	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	6.6987268e-05
4,688	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	5.9900111e-05
5,945	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.2583364e-05
6,866	Indexed Fast Network Proximity Querying	2018	VLDB	4.8994824e-05
7,081	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	4.833459e-05
7,156	The Minimum Wiener Connector Problem	2015	SIGMOD	4.8098527e-05
9,330	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	4.351469e-05
10,674	LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration	2025	VLDB	4.1905499e-05
11,030	BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank	2024	VLDB	4.1905499e-05
11,795	Scaling Locally Linear Embedding	2017	SIGMOD	4.1905499e-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.0002809849
753	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00017113124
765	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.0001695147
895	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015498104
911	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00015381088
1,280	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00012838714

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,748	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9432853e-05
7,273	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.775366e-05
4,888	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB	5.8494448e-05
8,025	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD	4.5988512e-05
1,072	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00014256848
4,760	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB	5.9342555e-05
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05
7,271	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD	4.7764555e-05
1,907	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010130702
5,945	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.2583364e-05