Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy

Summary: First differentially private, fully dynamic graph algorithms for triangle count, connected components, max matching, and degree histogram under continual edge updates. Bounds for event- and item-level DP; proves exponential dependence on time steps and, for item-level privacy, matches lower bounds for several problems. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2002
Venue: PODS
Year: 2025
Pagerank: 5.7621757e-05
Overall Rank: 6,826 | 53.17%
DOI: 10.1145/3725236

Incoming Non-self Citations Over Time

Authors

1. Sofya Raskhodnikova (Boston University)
2. Teresa Anna Steiner (University of Southern Denmark)

BibTeX Citation

@inproceedings{raskhodnikova_pods25,
        address = {New York, NY, USA},
        series = {{PODS} '25},
        title = {{Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy}},
        url = {https://dl.acm.org/doi/10.1145/3725236},
        doi = {10.1145/3725236},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Raskhodnikova, Sofya and Steiner, Teresa Anna},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,157	Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization	2026	PODS	5.093636e-05
10,158	Improved Lower Bounds for Privacy under Continual Release	2026	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
510	Practical Privacy: The SuLQ Framework	2005	PODS	0.00017220509
836	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD	0.00013715654
1,220	Calibrating Data to Sensitivity in Private Data Analysis: A Platform for Differentially-Private Analysis of Weighted Datasets	2014	VLDB	0.00011619529
1,790	Publishing Graph Degree Distribution with Node Differential Privacy	2016	SIGMOD	9.7502278e-05
1,960	Private Release of Graph Statistics using Ladder Functions	2015	SIGMOD	9.4058693e-05
2,992	Pan-private Algorithms Via Statistics on Sketches	2011	PODS	7.8836024e-05
8,702	Databases as Graphs: Predictive Queries for Declarative Machine Learning	2023	PODS	5.3817447e-05
11,370	Node-Differentially Private Estimation of the Number of Connected Components	2023	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,079	Design of Policy-Aware Differentially Private Algorithms	2016	VLDB
2	7,292	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS
3	121	Boosting the Accuracy of Differentially Private Histograms Through Consistency	2010	VLDB
4	836	Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins	2013	SIGMOD
5	596	Private Analysis of Graph Structure	2011	VLDB
6	6,367	Robust Privacy-Preserving Triangle Counting under Edge Local Differential Privacy	2025	SIGMOD
7	10,786	Computing Inconsistency Measures Under Differential Privacy	2025	SIGMOD
8	6,083	Global and Local Differentially Private Release of Count-Weighted Graphs	2023	SIGMOD
9	9,552	Practical and Accurate Local Edge Differentially Private Graph Algorithms	2025	VLDB
10	10,158	Improved Lower Bounds for Privacy under Continual Release	2026	PODS