BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs

Summary: BEAR reorders the graph adjacency to expose a large invertible block and precomputes its Schur complement for scalable RWR. During queries, it uses block-elimination to compute RWR quickly, and beats prior methods in preprocessing, space, and accuracy. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4998
Venue: SIGMOD
Year: 2015
Pagerank: 9.7969398e-05
Overall Rank: 1,769 | 87.87%
DOI: 10.1145/2723372.2723716

Incoming Non-self Citations Over Time

Authors

1. Kijung Shin (Seoul National University)
2. Jinhong Jung (Korea Advanced Institute of Science and Technology)
3. Lee Sael (State University of New York Korea)
4. U Kang (Korea Advanced Institute of Science and Technology)

BibTeX Citation

@inproceedings{shin_sigmod15,
        title = {{BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs}},
        author = {Shin, Kijung and Jung, Jinhong and Sael, Lee and Kang, U},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2723716},
        url = {https://dl.acm.org/doi/10.1145/2723372.2723716},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
2,225	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.9183159e-05
3,315	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.5274958e-05
3,892	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	7.0430255e-05
4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.9479974e-05
4,225	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	6.821373e-05
4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5497309e-05
5,741	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	6.1029326e-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
7,861	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	5.5302333e-05
8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.4949527e-05
8,911	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.3483178e-05
9,046	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.3251649e-05
9,769	Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs	2025	SIGMOD	5.2209769e-05
11,390	Effective and Efficient PageRank-based Positioning for Graph Visualization	2023	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
285	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00022365284
758	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00014277369
1,414	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010848387
1,628	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010186757

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,414	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB
2	10,240	Fast Estimation of Pairwise Biharmonic Distance on Graphs	2026	SIGMOD
3	4,572	On the Embeddability of Random Walk Distances	2013	VLDB
4	8,911	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD
5	4,216	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
6	7,201	An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs	2022	VLDB
7	6,423	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD
8	3,951	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
9	5,815	Reverse Top-k Search using Random Walk with Restart	2014	VLDB
10	2,073	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD