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.0480912e-05
Overall Rank: 10,269 | 30.99%
DOI: 10.14778/3665844.3665855
PDF: Download (CC BY-NC-ND 4.0)

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,390	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	4.9769913e-05
10,531	A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness	2026	SIGMOD	4.9769913e-05
10,948	BiLink: Bidirectional Meta-paths for Link Discovery in Billion-Scale Heterogeneous Graphs	2026	VLDB	4.9769913e-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.00013973978
1,224	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011458287
1,420	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010724642
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,018	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	7.743467e-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,127	SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization	2022	VLDB	6.259487e-05
5,564	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD	6.081296e-05
6,405	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.7936558e-05
8,232	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.3714879e-05
8,233	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	5.3714879e-05
9,636	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	5.145261e-05

Semantically Similar Papers

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