Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy

Summary: Estimates common neighbors in bipartite graphs under edge LDP. Proposes a multi-round pruning framework with unbiased local estimators, leveraging neighbors of both query vertices, optimized privacy-budget allocation boosts accuracy under degree imbalance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6977
Venue: SIGMOD
Year: 2024
Pagerank: 4.3441378e-05
Overall Rank: 9,405 | 34.58%
DOI: 10.1145/3698803

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,153	Defense against Poisoning Attacks under Shuffle-DP	2026	SIGMOD	4.1945683e-05
10,157	Efficient and Effective Biclique Counting with Local Differential Privacy	2026	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037697111
642	Private Analysis of Graph Structure	2011	VLDB	0.00018755196
2,226	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.2421776e-05
2,683	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	8.315553e-05
2,903	(p,q)-biclique Counting and Enumeration for Large Sparse Bipartite Graphs	2022	VLDB	7.9375744e-05
4,626	Efficient Biclique Counting in Large Bipartite Graphs	2023	SIGMOD	6.0399035e-05
4,843	Butterfly-Core Community Search over Labeled Graphs	2021	VLDB	5.8823824e-05
5,474	Efficient Load-Balanced Butterfly Counting on GPU	2022	VLDB	5.4881807e-05
5,540	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4498271e-05
5,773	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	5.3319911e-05
8,821	Efficient Unsupervised Community Search with Pre-trained Graph Transformer	2024	VLDB	4.4417735e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,540	Frequency Estimation under Local Differential Privacy	2021	VLDB	8.5797299e-05
10,728	Continuous Publication of Weighted Graphs with Local Differential Privacy	2025	VLDB	4.1945683e-05
505	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00021491332
10,348	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy	2025	PODS	4.1945683e-05
2,718	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.2409647e-05
6,235	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD	5.1451658e-05
10,094	N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics	2026	SIGMOD	4.1945683e-05
10,727	Practical and Accurate Local Edge Differentially Private Graph Algorithms	2025	VLDB	4.1945683e-05
8,234	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD	4.5535352e-05
10,157	Efficient and Effective Biclique Counting with Local Differential Privacy	2026	SIGMOD	4.1945683e-05