Back to papers
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
- 4937
- Venue
- SIGMOD
- Year
- 2015
- Pagerank
- 9.3358152e-05
- Overall Rank
- 2,189 | 84.79%
- DOI
-
10.1145/2723372.2723716
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 17 of 17 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 2,110 |
HubPPR: Effective Indexing for Approximate Personalized PageRank |
2017 |
VLDB |
9.5280826e-05 |
| 2,515 |
BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart |
2017 |
SIGMOD |
8.6115215e-05 |
| 2,522 |
Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push |
2021 |
SIGMOD |
8.6029608e-05 |
| 3,853 |
Distributed Algorithms on Exact Personalized PageRank |
2017 |
SIGMOD |
6.6987268e-05 |
| 4,560 |
Massively Parallel Algorithms for Personalized PageRank |
2021 |
VLDB |
6.0788254e-05 |
| 4,670 |
Realtime Top-k Personalized PageRank over Large Graphs on GPUs |
2020 |
VLDB |
6.0027844e-05 |
| 4,688 |
TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs |
2018 |
SIGMOD |
5.9900111e-05 |
| 5,666 |
Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme |
2023 |
SIGMOD |
5.3824583e-05 |
| 6,310 |
Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks |
2018 |
SIGMOD |
5.111823e-05 |
| 6,866 |
Indexed Fast Network Proximity Querying |
2018 |
VLDB |
4.8994824e-05 |
| 7,081 |
Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach |
2022 |
SIGMOD |
4.833459e-05 |
| 9,252 |
Efficient Resistance Distance Computation: the Power of Landmark-based Approaches |
2023 |
SIGMOD |
4.3648789e-05 |
| 9,330 |
Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches |
2023 |
SIGMOD |
4.351469e-05 |
| 9,641 |
Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs |
2025 |
SIGMOD |
4.3067693e-05 |
| 10,028 |
One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor |
2026 |
SIGMOD |
4.1905499e-05 |
| 10,960 |
Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach |
2024 |
SIGMOD |
4.1905499e-05 |
| 11,188 |
Effective and Efficient PageRank-based Positioning for Graph Visualization |
2023 |
SIGMOD |
4.1905499e-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.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 1,626 |
Fast and Exact Top-k Search for Random Walk with Restart |
2012 |
VLDB |
0.0001108491 |
| 9,252 |
Efficient Resistance Distance Computation: the Power of Landmark-based Approaches |
2023 |
SIGMOD |
4.3648789e-05 |
| 4,487 |
On the Embeddability of Random Walk Distances |
2013 |
VLDB |
6.1412716e-05 |
| 10,960 |
Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach |
2024 |
SIGMOD |
4.1905499e-05 |
| 4,760 |
An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs |
2015 |
VLDB |
5.9342555e-05 |
| 7,359 |
An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs |
2022 |
VLDB |
4.7477556e-05 |
| 6,493 |
Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs |
2020 |
SIGMOD |
5.0344095e-05 |
| 4,888 |
READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank |
2017 |
VLDB |
5.8494448e-05 |
| 5,945 |
Reverse Top-k Search using Random Walk with Restart |
2014 |
VLDB |
5.2583364e-05 |
| 2,515 |
BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart |
2017 |
SIGMOD |
8.6115215e-05 |