Database Paper Browser

Back to papers

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
5000
Venue
SIGMOD
Year
2015
Pagerank
8.31087e-05
Overall Rank
2,686 | 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,516 PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions 2016 SIGMOD 0.00011558246
2,224 Publishing Graph Degree Distribution with Node Differential Privacy 2016 SIGMOD 9.256869e-05
3,083 Computing Local Sensitivities of Counting Queries with Joins 2020 SIGMOD 7.5985351e-05
5,499 R2T: Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign Keys 2022 SIGMOD 5.4737427e-05
6,231 Global and Local Differentially Private Release of Count-Weighted Graphs 2023 SIGMOD 5.1402278e-05
6,406 Publishing Attributed Social Graphs with Formal Privacy Guarantees 2016 SIGMOD 5.0704962e-05
7,059 Residual Sensitivity for Differentially Private Multi-Way Joins 2021 SIGMOD 4.8404261e-05
7,437 Better than Composition: How to Answer Multiple Relational Queries under Differential Privacy 2023 SIGMOD 4.7258659e-05
7,441 Continual Observation of Joins under Differential Privacy 2024 SIGMOD 4.7251588e-05
7,584 A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries 2022 PODS 4.7015411e-05
7,943 DPGraph: A Benchmark Platform for Differentially Private Graph Analysis 2021 SIGMOD 4.6089395e-05
7,946 Local Dampening: Differential Privacy for Non-numeric Queries via Local Sensitivity 2021 VLDB 4.6089395e-05
8,873 Privacy Amplification by Sampling under User-level Differential Privacy 2024 SIGMOD 4.4271393e-05
9,411 Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy 2024 SIGMOD 4.3399748e-05
10,094 N2E: A General Framework to Reduce Node-Differential Privacy to Edge-Differential Privacy for Graph Analytics 2026 SIGMOD 4.1905499e-05
10,157 Efficient and Effective Biclique Counting with Local Differential Privacy 2026 SIGMOD 4.1905499e-05
10,360 Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy 2025 PODS 4.1905499e-05
10,522 Computing Inconsistency Measures Under Differential Privacy 2025 SIGMOD 4.1905499e-05
11,077 Confidence Intervals for Private Query Processing 2024 VLDB 4.1905499e-05
11,167 Node-Differentially Private Estimation of the Number of Connected Components 2023 PODS 4.1905499e-05
Previous Page 1 / 1 Next

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
506 Relationship Privacy: Output Perturbation for Queries with Joins 2009 PODS 0.00021481335
800 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00016463554
1,177 Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins 2013 SIGMOD 0.00013465351
1,571 Resisting Structural Re-identification in Anonymized Social Networks 2008 VLDB 0.000113084
1,607 Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets 2014 VLDB 0.00011171719
2,721 Anonymizing Bipartite Graph Data using Safe Groupings 2008 VLDB 8.2331032e-05
3,169 K-Automorphism: A General Framework for Privacy Preserving Network Publication 2009 VLDB 7.4545379e-05
6,692 Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms 2013 SIGMOD 4.9568011e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,309 Shortest Paths and Distances with Differential Privacy 2016 PODS 7.2374523e-05
178 Boosting the Accuracy of Differentially Private Histograms Through Consistency 2010 VLDB 0.00037726596
10,360 Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy 2025 PODS 4.1905499e-05
800 Towards Identity Anonymization on Graphs 2008 SIGMOD 0.00016463554
10,734 Practical and Accurate Local Edge Differentially Private Graph Algorithms 2025 VLDB 4.1905499e-05
1,177 Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins 2013 SIGMOD 0.00013465351
6,406 Publishing Attributed Social Graphs with Formal Privacy Guarantees 2016 SIGMOD 5.0704962e-05
8,141 Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy 2025 SIGMOD 4.5724134e-05
6,231 Global and Local Differentially Private Release of Count-Weighted Graphs 2023 SIGMOD 5.1402278e-05
642 Private Analysis of Graph Structure 2011 VLDB 0.00018757732