BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart

Summary: BePI uses block-elimination preprocessing and a preconditioned iterative solver to scale RWR on billion-edge graphs. Fast queries and low memory come from nonzero reduction and preconditioning, enabling 100x larger graphs with 130x less memory and 9x faster RWR. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb5fd2f88f9d81a7b
Venue: SIGMOD
Year: 2017
Pagerank: 9.0463758e-05
Overall Rank: 2,102 | 85.87%
DOI: 10.1145/3035918.3035950

Incoming Non-self Citations Over Time

Authors

1. Jinhong Jung (Seoul National University)
2. Namyong Park (Seoul National University)
3. Lee Sael (State University of New York Korea)
4. U Kang (Seoul National University)

BibTeX Citation

@inproceedings{jung_sigmod17,
        title = {{BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart}},
        author = {Jung, Jinhong and Park, Namyong and Sael, Lee and Kang, U},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3035950},
        url = {https://dl.acm.org/doi/10.1145/3035918.3035950},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,183	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	8.8962182e-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,082	On Graph Representation for Attributed Hypergraph Clustering	2025	SIGMOD	5.892229e-05
6,403	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.7963998e-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,359	Efficient and Effective Attributed Hypergraph Clustering via K-Nearest Neighbor Augmentation	2023	SIGMOD	5.3476128e-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 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
556	Fast Incremental and Personalized PageRank	2011	VLDB	0.00016500392
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013980547
962	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00012820478
1,400	Scalable Similarity Search for SimRank	2014	SIGMOD	0.00010776946
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
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
1,864	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.4824224e-05
3,252	Computing PageRank in a Distributed Internet Search System	2004	VLDB	7.492983e-05
5,914	Reverse Top-k Search using Random Walk with Restart	2014	VLDB	5.9490698e-05
7,297	FrogWild! – Fast PageRank Approximations on Graph Engines	2015	VLDB	5.5618017e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,562	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD
2	4,303	An Efficient Similarity Search Framework for SimRank over Large Dynamic Graphs	2015	VLDB
3	7,263	An I/O-Efficient Disk-based Graph System for Scalable Second-Order Random Walk of Large Graphs	2022	VLDB
4	11,564	FlowWalker: A Memory-efficient and High-performance GPU-based Dynamic Graph Random Walk Framework	2024	VLDB
5	4,649	On the Embeddability of Random Walk Distances	2013	VLDB
6	10,455	Fast Estimation of Pairwise Biharmonic Distance on Graphs	2026	SIGMOD
7	4,031	READS: A Random Walk Approach for Efficient and Accurate Dynamic SimRank	2017	VLDB
8	5,914	Reverse Top-k Search using Random Walk with Restart	2014	VLDB
9	6,301	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD
10	1,798	BEAR: Block Elimination Approach for Random Walk with Restart on Large Graphs	2015	SIGMOD