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: 13644
Venue: VLDB
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,237 | 22.91%
DOI: 10.14778/3665844.3665855

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

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 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,161	Near-Optimality for Single-Source Personalized PageRank	2026	PODS	5.093636e-05
10,309	A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness	2026	SIGMOD	5.093636e-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
758	Simrank++: Query Rewriting through Link Analysis of the Click Graph	2008	VLDB	0.00014277369
1,211	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011648789
1,414	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010848387
2,173	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	9.0375634e-05
2,225	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.9183159e-05
3,210	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	7.6352864e-05
4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.9479974e-05
4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5497309e-05
5,432	Scalable and Effective Bipartite Network Embedding	2022	SIGMOD	6.2211042e-05
5,968	SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization	2022	VLDB	6.0248475e-05
6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.927015e-05
8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.4949527e-05
8,063	Estimating Single-Node PageRank in O~(min{d_t, sqrt(m)}) Time	2023	VLDB	5.4949527e-05
9,471	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB	5.2634238e-05

Semantically Similar Papers

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