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

Summary: K-dash enables exact top-k proximity search under random walk with restart, unlike faster approximate methods. Sparse-matrix proximity computation and pruning of unnecessary candidates substantially accelerate queries while preserving provable result exactness. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10679
Venue: VLDB
Year: 2012
Pagerank: 0.00010848387
Overall Rank: 1,414 | 90.31%
DOI: 10.14778/2140436.2140441

Incoming Non-self Citations Over Time

Authors

1. Yasuhiro Fujiwara (Nippon Telegraph and Telephone Corporation; University of Tokyo)
2. Makoto Nakatsuji (Nippon Telegraph and Telephone Cyber Solutions Laboratories)
3. Makoto Onizuka (Nippon Telegraph and Telephone Corporation)
4. Masaru Kitsuregawa (University of Tokyo)

BibTeX Citation

@article{fujiwara_vldb12,
        title = {{Fast and Exact Top-k Search for Random Walk with Restart}},
        author = {Fujiwara, Yasuhiro and Nakatsuji, Makoto and Onizuka, Makoto and Kitsuregawa, Masaru},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {5},
        pages = {442--453},
        doi = {10.14778/2140436.2140441},
        url = {https://doi.org/10.14778/2140436.2140441},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00011112799
1,628	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010186757
1,769	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.7969398e-05
1,838	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.6436348e-05
2,073	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.2209912e-05
2,173	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	9.0375634e-05
3,210	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	7.6352864e-05
3,315	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.5274958e-05
4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.9479974e-05
5,815	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	6.0777346e-05
6,125	The Minimum Wiener Connector Problem	2015	SIGMOD	5.9675732e-05
6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.927015e-05
6,655	Indexed Fast Network Proximity Querying	2018	VLDB	5.8125709e-05
8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.4949527e-05
10,916	LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration	2025	VLDB	5.093636e-05
11,237	BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank	2024	VLDB	5.093636e-05
11,992	Scaling Locally Linear Embedding	2017	SIGMOD	5.093636e-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
364	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00020054172
653	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00015302705
727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014565738
731	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.00014537965
758	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00014277369
1,394	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.0001093153

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,908	Diversified Top-k Graph Pattern Matching	2013	VLDB
2	7,299	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
3	3,951	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
4	8,303	Efficient Top-K SimRank-based Similarity Join	2014	SIGMOD
5	1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
6	4,216	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
7	6,940	Exact Top-k Nearest Keyword Search in Large Networks	2015	SIGMOD
8	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	1,628	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD
10	5,815	Reverse Top-k Search using Random Walk with Restart	2014	VLDB