2026-08-01T09:38:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14623 2024-03-21T15:04:35Z ddc:004 open_access

Differentially Private Algorithms for Graphs Under Continual Observation Fichtenberger, Hendrik Henzinger, Monika Ost, Lara differential privacy continual observation dynamic graph algorithms Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T. We also give ε-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which, as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution’s range. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hendrik Fichtenberger and Monika Henzinger and Lara Ost 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.42 urn:nbn:de:0030-drops-146230 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.42 eng https://creativecommons.org/licenses/by/4.0/legalcode