Publishing Graph Degree Distribution with Node Differential Privacy

Summary: Publishes a graph degree distribution under node-DP by projecting to lower sensitivity, using aggregation-based and cumulative-histogram methods. Reports strong accuracy gains over prior work; includes an introspective analysis of key factors. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5283
Venue: SIGMOD
Year: 2016
Pagerank: 9.2421776e-05
Overall Rank: 2,226 | 84.52%
DOI: 10.1145/2882903.2926745

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,738	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00010720057
4,754	Differentially Private Binary- and Matrix-Valued Data Query: An XOR Mechanism	2021	VLDB	5.9468785e-05
5,246	Utility Cost of Formal Privacy for Releasing National Employer-Employee Statistics	2017	SIGMOD	5.6063332e-05
5,491	R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys	2022	SIGMOD	5.4776364e-05
6,235	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD	5.1451658e-05
7,064	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD	4.8450749e-05
7,579	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS	4.706055e-05
7,940	DPGraph: A Benchmark Platform for Differentially Private Graph Analysis	2021	SIGMOD	4.613363e-05
8,873	Privacy Amplification by Sampling under User-level Differential Privacy	2024	SIGMOD	4.4313867e-05
9,405	Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy	2024	SIGMOD	4.3441378e-05
9,796	DP-starJ: A Differential Private Scheme towards Analytical Star-Join Queries	2023	SIGMOD	4.2818172e-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,157	Efficient and Effective Biclique Counting with Local Differential Privacy	2026	SIGMOD	4.1945683e-05
10,348	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy	2025	PODS	4.1945683e-05
10,513	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD	4.1945683e-05
11,164	Node-Differentially Private Estimation of the Number of Connected Components	2023	PODS	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
83	Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis	2009	SIGMOD	0.00053933811
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037697111
642	Private Analysis of Graph Structure	2011	VLDB	0.00018755196
719	Understanding Hierarchical Methods for Differentially Private Histograms	2013	VLDB	0.00017626484
1,177	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013470212
1,465	No Free Lunch in Data Privacy	2011	SIGMOD	0.00011860847
1,935	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB	0.00010032967
2,227	Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies	2014	SIGMOD	9.2421238e-05
2,683	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	8.315553e-05
4,189	Towards an Axiomatization of Statistical Privacy and Utility	2010	PODS	6.3743594e-05
5,267	Practical Differential Privacy via Grouping and Smoothing	2013	VLDB	5.5972313e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,097	Publishing Set-Valued Data via Differential Privacy	2011	VLDB	7.5647028e-05
2,683	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	8.315553e-05
7,940	DPGraph: A Benchmark Platform for Differentially Private Graph Analysis	2021	SIGMOD	4.613363e-05
1,177	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013470212
803	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016478924
10,728	Continuous Publication of Weighted Graphs with Local Differential Privacy	2025	VLDB	4.1945683e-05
10,094	N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics	2026	SIGMOD	4.1945683e-05
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037697111
6,235	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD	5.1451658e-05
6,410	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.0753667e-05