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.616919e-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,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
2,258	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.7385422e-05
3,266	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.4775e-05
3,653	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	7.1288161e-05
3,977	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	6.8850687e-05
4,101	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.8073016e-05
4,264	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.6978776e-05
5,859	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD	5.9682458e-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,020	Efficient Resistance Distance Computation: the Power of Landmark-based Approaches	2023	SIGMOD	5.4061498e-05
8,226	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.3740319e-05
8,629	Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach	2024	SIGMOD	5.2994494e-05
9,220	One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor	2026	SIGMOD	5.2056825e-05
9,947	Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs	2025	SIGMOD	5.1038322e-05
11,705	Effective and Efficient PageRank-based Positioning for Graph Visualization	2023	SIGMOD	4.9793485e-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.00021955068
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013980547
1,419	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010728945
1,604	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010095949

Semantically Similar Papers

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