{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:59Z","timestamp":1778807879292,"version":"3.51.4"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100006374","name":"Villum Fonden","doi-asserted-by":"publisher","award":["VIL51463"],"award-info":[{"award-number":["VIL51463"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["DMS-2022446"],"award-info":[{"award-number":["DMS-2022446"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>We study differentially private algorithms for analyzing graph databases in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted over time, and the algorithm is required to update the solution at every time step. Previous work has presented differentially private algorithms for many graph problems that can handle insertions only or deletions only (called partially dynamic algorithms) and obtained some hardness results for the fully dynamic setting. The only algorithms in the latter setting were for the edge count, given by Fichtenberger, Henzinger, and Ost (ESA '21), and for releasing the values of all graph cuts, given by Fichtenberger, Henzinger, and Upadhyay (ICML '23). We provide the first differentially private and fully dynamic graph algorithms for several other fundamental graph statistics (including the triangle count, the number of connected components, the size of the maximum matching, and the degree histogram), analyze their error, and show strong lower bounds on the error for all algorithms in this setting. Previously, only lower bounds for purely differentially private algorithms were known; our lower bounds give an exponential improvement in terms of the dependence on the number of time steps, while applying to algorithms satisfying pure as well as approximate differential privacy. We study two variants of edge differential privacy for fully dynamic graph algorithms: event-level and item-level. Under the former notion, two graph database update sequences are considered neighboring if, roughly speaking, they differ in at most one update; under the latter notion, they can differ only in updates pertaining to one edge. Differential privacy requires that for any two neighboring inputs, the output distributions of the algorithm are close. We give upper and lower bounds on the error of both---event-level and item-level---fully dynamic algorithms for several fundamental graph problems. No fully dynamic algorithms that are private at the item-level (the more stringent of the two notions) were known before. In the case of item-level privacy, for several problems, our algorithms match our lower bounds.<\/jats:p>","DOI":"10.1145\/3725236","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-28","source":"Crossref","is-referenced-by-count":1,"title":["Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4902-050X","authenticated-orcid":false,"given":"Sofya","family":"Raskhodnikova","sequence":"first","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1078-4075","authenticated-orcid":false,"given":"Teresa Anna","family":"Steiner","sequence":"additional","affiliation":[{"name":"University of Southern Denmark, Odense, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2901716"},{"key":"e_1_2_1_2_1","volume-title":"On Differentially Private Graph Sparsification and Applications. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Arora Raman","year":"2019","unstructured":"Raman Arora and Jalaj Upadhyay. 2019. On Differentially Private Graph Sparsification and Applications. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8--14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 13378--13389. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/e44e875c12109e4fa3716c05008048b2-Abstract.html"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.67"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.26"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"e_1_2_1_7_1","volume-title":"Private Decayed Predicate Sums on Streams. In International Conference on Database Theory (ICDT). 284--295","author":"Bolot Jean","year":"2013","unstructured":"Jean Bolot, Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov, and Nina Taft. 2013. Private Decayed Predicate Sums on Streams. In International Conference on Database Theory (ICDT). 284--295."},{"key":"e_1_2_1_8_1","volume-title":"Smith","author":"Borgs Christian","year":"2015","unstructured":"Christian Borgs, Jennifer T. Chayes, and Adam D. Smith. 2015. Private Graphon Estimation for Sparse Graphs. In Advances in Neural Information Processing Systems (NeurIPS). 1369--1377."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00057"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1033587"},{"key":"e_1_2_1_12_1","article-title":"Private and Continual Release of Statistics","volume":"14","author":"Hubert Chan T.-H.","year":"2011","unstructured":"T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2011. Private and Continual Release of Statistics. ACM Trans. Inf. Syst. Secur. 14, 3 (2011), 26:1--26:24.","journal-title":"ACM Trans. Inf. Syst. Secur."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_2_1_14_1","unstructured":"Edith Cohen Xin Lyu Jelani Nelson Tam\u00e1s Sarl\u00f3s and Uri Stemmer. 2024. Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries. Cryptology ePrint Archive Paper 2024\/373. https:\/\/eprint.iacr.org\/2024\/373 https:\/\/eprint.iacr.org\/2024\/373."},{"key":"e_1_2_1_15_1","volume-title":"Gaurav Aggarwal, and Prateek Jain.","author":"Daigavane Ameya","year":"2021","unstructured":"Ameya Daigavane, Gagan Madan, Aditya Sinha, Abhradeep Guha Thakurta, Gaurav Aggarwal, and Prateek Jain. 2021. Node-Level Differentially Private Graph Neural Networks. arXiv:2111.15521"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_18"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00077"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271736"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179466"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536466"},{"key":"e_1_2_1_24_1","volume-title":"Smith","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. 2006. Calibrating Noise to Sensitivity in Private Data Analysis. In Proc. 3rd TCC, Vol. 3876. Springer, 265--284."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.v7i3.405"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250804"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings, ACM Symposium on Theory of Computing (STOC). 715--724","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. 2010. Differential privacy under continual observation. In Proceedings, ACM Symposium on Theory of Computing (STOC). 715--724."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--662--48800--3_30"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS). 51--60","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. 2010. Boosting and Differential Privacy. In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS). 51--60."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.52"},{"key":"e_1_2_1_31_1","unstructured":"Alessandro Epasto Quanquan C. Liu Tamalika Mukherjee and Felix Zhou. 2024. The Power of Graph Sparsification in the Continual Release Model. arXiv:2407.17619 [cs.DS] https:\/\/arxiv.org\/abs\/2407.17619"},{"key":"e_1_2_1_32_1","first-page":"1","article-title":"Differentially Private Continual Releases of Streaming Frequency Moment Estimations. In Proceedings","volume":"251","author":"Epasto Alessandro","year":"2023","unstructured":"Alessandro Epasto, Jieming Mao, Andres Mu\u00f1oz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. 2023. Differentially Private Continual Releases of Streaming Frequency Moment Estimations. In Proceedings, Innovations in Theoretical Computer Science (ITCS), Vol. 251. 48:1--48:24.","journal-title":"Innovations in Theoretical Computer Science (ITCS)"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.42"},{"key":"e_1_2_1_34_1","volume-title":"Constant Matters: Fine-grained Error Bound on Differentially Private Continual Observation. In International Conference on Machine Learning, ICML 2023","volume":"10092","author":"Fichtenberger Hendrik","year":"2023","unstructured":"Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. 2023. Constant Matters: Fine-grained Error Bound on Differentially Private Continual Observation. In International Conference on Machine Learning, ICML 2023, 23- 29 July 2023, Honolulu, Hawaii, USA (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (Eds.). PMLR, 10072--10092. https:\/\/proceedings.mlr.press\/v202\/fichtenberger23a.html"},{"key":"e_1_2_1_35_1","first-page":"1","article-title":"Private Counting of Distinct and k-Occurring Items in Time Windows. In Proceedings","volume":"251","author":"Ghazi Badih","year":"2023","unstructured":"Badih Ghazi, Ravi Kumar, Jelani Nelson, and Pasin Manurangsi. 2023. Private Counting of Distinct and k-Occurring Items in Time Windows. In Proceedings, Innovations in Theoretical Computer Science (ITCS), Vol. 251. 55:1--55:24.","journal-title":"Innovations in Theoretical Computer Science (ITCS)"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_19"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_2_1_39_1","volume-title":"Proc. 28th RANDOM.","author":"Henzinger Monika","year":"2024","unstructured":"Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner. 2024. Private Counting of Distinct Elements in the Turnstile Model and Extensions. In Proc. 28th RANDOM."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH183"},{"key":"e_1_2_1_41_1","volume-title":"Proc. 36th NeurIPS. http:\/\/papers.nips.cc\/paper_files\/paper\/2023\/hash\/0ef1afa0daa888d695dcd5e9513bafa3-Abstract-Conference.html","author":"Jain Palak","unstructured":"Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. 2023. Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation. In Proc. 36th NeurIPS. http:\/\/papers.nips.cc\/paper_files\/paper\/2023\/hash\/0ef1afa0daa888d695dcd5e9513bafa3-Abstract-Conference.html"},{"key":"e_1_2_1_42_1","volume-title":"Proc. 40th ICML. 14654--14678","author":"Jain Palak","unstructured":"Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. 2023. The Price of Differential Privacy under Continual Observation. In Proc. 40th ICML. 14654--14678. https:\/\/proceedings.mlr.press\/v202\/jain23b.html"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2403.04630"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588671"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611523"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--33627-0_21"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--36594--2_26"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3589939"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3040077"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623683"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings, ACM Symposium on Principles of Database Systems (PODS). 37--48","author":"Mir Darakhshan","unstructured":"Darakhshan Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright. 2011. Pan-Private Algorithms via Statistics on Sketches. In Proceedings, ACM Symposium on Principles of Database Systems (PODS). 37--48."},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the Workshops of the EDBT\/ICDT 2015 Joint Conference","volume":"1330","author":"M\u00fclle Yvonne","year":"2015","unstructured":"Yvonne M\u00fclle, Chris Clifton, and Klemens B\u00f6hm. 2015. Privacy-integrated graph clustering through differential privacy. In Proceedings of the Workshops of the EDBT\/ICDT 2015 Joint Conference, Vol. 1330. 247--254."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994620.2994624"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"Nissim Kobbi","year":"2007","unstructured":"Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11--13, 2007, David S. Johnson and Uriel Feige (Eds.). ACM, 75--84."},{"key":"e_1_2_1_55_1","volume-title":"Private Continual Release of Real-Valued Data Streams. In Network and Distributed System Security Symposium (NDSS).","author":"Perrier Victor","year":"2019","unstructured":"Victor Perrier, Hassan Jameel Asghar, and Dali Kaafar. 2019. Private Continual Release of Real-Valued Data Streams. In Network and Distributed System Security Symposium (NDSS)."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4939--2864--4_549"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.60"},{"key":"e_1_2_1_59_1","unstructured":"Sofya Raskhodnikova and Teresa Anna Steiner. 2024. Fully Dynamic Graph Algorithms with Edge Differential Privacy. arXiv:2409.17623 [cs.DS] https:\/\/arxiv.org\/abs\/2409.17623"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737405"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.745"},{"key":"e_1_2_1_62_1","volume-title":"Differentially Private Continual Release of Graph Statistics. CoRR abs\/1809.02575","author":"Song Shuang","year":"2018","unstructured":"Shuang Song, Susan Little, Sanjay Mehta, Staal A. Vinterbo, and Kamalika Chaudhuri. 2018. Differentially Private Continual Release of Graph Statistics. CoRR abs\/1809.02575 (2018). arXiv:1809.02575"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--42033--7_15"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--37456--2_28"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-013-0127--7"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2927365"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM50108.2020.00184"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:33Z","timestamp":1755904713000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725236"],"URL":"https:\/\/doi.org\/10.1145\/3725236","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}