Differentially private algorithms for graphs under continual observation
Fichtenberger H, Henzinger MH, Ost W. 2021. Differentially private algorithms for graphs under continual observation. 29th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42.
Download (ext.)
https://doi.org/10.4230/LIPIcs.ESA.2021.42
[Published Version]
Conference Paper
| Published
| English
Scopus indexed
Author
Fichtenberger, Hendrik;
Henzinger, MonikaISTA ;
Ost, Wolfgang
Series Title
LIPIcs
Abstract
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.
Publishing Year
Date Published
2021-08-31
Proceedings Title
29th Annual European Symposium on Algorithms
Volume
204
Article Number
42
Conference
ESA: Annual European Symposium on Algorithms
Conference Location
Lisbon, Portual
Conference Date
2021-09-06 – 2021-09-08
ISBN
ISSN
IST-REx-ID
Cite this
Fichtenberger H, Henzinger MH, Ost W. Differentially private algorithms for graphs under continual observation. In: 29th Annual European Symposium on Algorithms. Vol 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.ESA.2021.42
Fichtenberger, H., Henzinger, M. H., & Ost, W. (2021). Differentially private algorithms for graphs under continual observation. In 29th Annual European Symposium on Algorithms (Vol. 204). Lisbon, Portual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2021.42
Fichtenberger, Hendrik, Monika H Henzinger, and Wolfgang Ost. “Differentially Private Algorithms for Graphs under Continual Observation.” In 29th Annual European Symposium on Algorithms, Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ESA.2021.42.
H. Fichtenberger, M. H. Henzinger, and W. Ost, “Differentially private algorithms for graphs under continual observation,” in 29th Annual European Symposium on Algorithms, Lisbon, Portual, 2021, vol. 204.
Fichtenberger H, Henzinger MH, Ost W. 2021. Differentially private algorithms for graphs under continual observation. 29th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42.
Fichtenberger, Hendrik, et al. “Differentially Private Algorithms for Graphs under Continual Observation.” 29th Annual European Symposium on Algorithms, vol. 204, 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.ESA.2021.42.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2106.14756