BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank

Summary: BIRD approximates single-source BHPP on weighted bipartite graphs with \~O(n) time, improving over prior \~O(m) methods without large matrix storage. It answers Orkut queries in 7 minutes, versus over 3 hours for existing approaches. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hb0ec161787c83fa2
Venue: VLDB
Year: 2024
Pagerank: 5.050482e-05
Overall Rank: 10,263 | 31.00%
DOI: 10.14778/3665844.3665855

Incoming Non-self Citations Over Time

Authors

1. Haoyu Liu (Nanyang Technological University)
2. Siqiang Luo (Nanyang Technological University)

BibTeX Citation

@article{liu_vldb24,
        title = {{BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank}},
        author = {Liu, Haoyu and Luo, Siqiang},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {9},
        pages = {2255--2268},
        doi = {10.14778/3665844.3665855},
        url = {https://doi.org/10.14778/3665844.3665855},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,378	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	4.9793485e-05
10,520	A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness	2026	SIGMOD	4.9793485e-05
10,939	BiLink: Bidirectional Meta-paths for Link Discovery in Billion-Scale Heterogeneous Graphs	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
788	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013980547
1,222	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011463714
1,419	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010728945
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,017	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	7.7471344e-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,124	SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization	2022	VLDB	6.2624516e-05
5,562	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD	6.0841762e-05
6,403	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.7963998e-05
8,226	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.3740319e-05
8,227	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	5.3740319e-05
9,628	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	5.1476979e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,345	Efficient Partial-Pairs SimRank Search on Large Networks	2015	VLDB
2	2,393	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB
3	3,653	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB
4	2,183	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD
5	5,236	Edge-based Local Push for Personalized PageRank	2022	VLDB
6	4,101	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD
7	9,558	Efficient and Accurate PageRank Approximation on Large Graphs	2024	SIGMOD
8	2,258	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB
9	5,859	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD
10	1,835	Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank	2020	VLDB