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: h9971d78961690b99
Venue: VLDB
Year: 2012
Pagerank: 0.00010728945
Overall Rank: 1,419 | 90.47%
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,368	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.0001090624
1,604	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010095949
1,798	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD	9.616919e-05
1,860	Efficient Ad-hoc Search for Personalized PageRank	2013	SIGMOD	9.4876834e-05
2,102	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0463758e-05
2,183	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.8962182e-05
3,017	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	7.7471344e-05
3,266	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.4775e-05
4,012	LEGO-GraphRAG: Modularizing Graph-based Retrieval-Augmented Generation for Design Space Exploration	2025	VLDB	6.8550917e-05
4,101	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.8073016e-05
5,914	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.9490698e-05
6,254	The Minimum Wiener Connector Problem	2015	SIGMOD	5.8337783e-05
6,403	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.7963998e-05
6,785	Indexed Fast Network Proximity Querying	2018	VLDB	5.6823069e-05
8,226	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.3740319e-05
10,263	BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank	2024	VLDB	5.050482e-05
12,290	Scaling Locally Linear Embedding	2017	SIGMOD	4.9793485e-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
375	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00019628745
666	Accuracy Estimate and Optimization Techniques for SimRank Computation	2008	VLDB	0.00014985082
736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014363536
739	PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks	2011	VLDB	0.00014333298
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013980547
1,374	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00010880336

Semantically Similar Papers

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