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: hd767fb0b5ed1874f
Venue: SIGMOD
Year: 2015
Pagerank: 9.6123666e-05
Overall Rank: 1,798 | 87.92%
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,103	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.0420935e-05
2,185	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.8920069e-05
2,259	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.7344054e-05
3,267	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.4739604e-05
3,655	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	7.1254436e-05
3,978	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.8818094e-05
4,103	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.8040813e-05
4,264	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.6947069e-05
5,861	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	5.9654205e-05
6,405	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.7936558e-05
6,791	Indexed Fast Network Proximity Querying	2018	VLDB	5.6796169e-05
8,025	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	5.4035905e-05
8,232	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.3714879e-05
8,636	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.2969407e-05
9,230	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.2032182e-05
9,955	Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs	2025	SIGMOD	5.1014161e-05
11,711	Effective and Efficient PageRank-based Positioning for Graph Visualization	2023	SIGMOD	4.9769913e-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
290	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00021944946
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013973978
1,420	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010724642
1,602	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010100314

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,025	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD
2	10,466	Fast Estimation of Pairwise Biharmonic Distance on Graphs	2026	SIGMOD
3	4,649	On the Embeddability of Random Walk Distances	2013	VLDB
4	8,636	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD
5	4,304	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
6	7,260	An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs	2022	VLDB
7	6,305	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD
8	4,032	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
9	5,918	Reverse Top-k Search using Random Walk with Restart	2014	VLDB
10	2,103	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD