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.031399e-05
Overall Rank: 10,296 | 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,456	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	4.9605343e-05
10,597	A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness	2026	SIGMOD	4.9605343e-05
11,009	BiLink: Bidirectional Meta-paths for Link Discovery in Billion-Scale Heterogeneous Graphs	2026	VLDB	4.9605343e-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
789	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00013935056
1,227	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011426039
1,407	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010736384
2,089	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	9.0473016e-05
2,188	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.8879472e-05
3,027	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	7.7178623e-05
3,988	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.8626164e-05
4,097	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.7946571e-05
5,148	SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization	2022	VLDB	6.2387892e-05
5,579	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD	6.0611875e-05
6,416	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.7744984e-05
8,251	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.3537264e-05
8,252	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	5.3537264e-05
9,663	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	5.1282476e-05

Semantically Similar Papers

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