Private Release of Graph Statistics using Ladder Functions

Summary: Introduces ladder functions for privately optimal outputs of graph statistics under differential privacy. Applied to subgraph counts, it achieves near-exact cost and improves accuracy over prior methods, enabling practical synthetic graph generation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4999
Venue: SIGMOD
Year: 2015
Pagerank: 8.315553e-05
Overall Rank: 2,683 | 81.34%
DOI: 10.1145/2723372.2737785

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,520	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011535148
2,226	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.2421776e-05
3,104	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD	7.5578613e-05
5,491	R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys	2022	SIGMOD	5.4776364e-05
5,885	Continual Observation of Joins under Differential Privacy	2024	SIGMOD	5.2880878e-05
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
7,064	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD	4.8450749e-05
7,439	Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy	2023	SIGMOD	4.7304034e-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
7,943	Local Dampening: Differential Privacy for Non-numeric Queries via Local Sensitivity	2021	VLDB	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
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,074	Confidence Intervals for Private Query Processing	2024	VLDB	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 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
505	Relationship Privacy: Output Perturbation for Queries with Joins	2009	PODS	0.00021491332
803	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016478924
1,177	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013470212
1,571	Resisting Structural Re-identification in Anonymized Social Networks	2008	VLDB	0.00011318916
1,602	Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets	2014	VLDB	0.00011199166
2,718	Anonymizing Bipartite Graph Data using Safe Groupings	2008	VLDB	8.2409647e-05
3,161	K-Automorphism: A General Framework for Privacy Preserving Network Publication	2009	VLDB	7.4613905e-05
6,691	Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms	2013	SIGMOD	4.9613269e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,325	Shortest Paths and Distances with Differential Privacy	2016	PODS	7.2211576e-05
178	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB	0.00037697111
10,348	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy	2025	PODS	4.1945683e-05
803	Towards Identity Anonymization on Graphs	2008	SIGMOD	0.00016478924
10,727	Practical and Accurate Local Edge Differentially Private Graph Algorithms	2025	VLDB	4.1945683e-05
1,177	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013470212
6,410	Publishing Attributed Social Graphs with Formal Privacy Guarantees	2016	SIGMOD	5.0753667e-05
8,234	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD	4.5535352e-05
6,235	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD	5.1451658e-05
642	Private Analysis of Graph Structure	2011	VLDB	0.00018755196