We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted over time, requiring the algorithm 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 (partially dynamic algorithms) and obtained hardness results for the fully dynamic setting. The only algorithms in the latter setting were for edge count, provided 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 present the first differentially private and fully dynamic graph algorithms for several other fundamental graph statistics (including triangle count, number of connected components, size of maximum matching, and degree histogram), analyze their error, and show strong lower bounds on the error for all algorithms in this setting. We study two variants of edge differential privacy for fully dynamic graph algorithms: event-level and item-level. We provide upper and lower bounds on the error of both event-level and item-level fully dynamic algorithms for several fundamental graph problems. Notably, 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, our algorithms match our lower bounds for several problems.
Blogger's Review: This paper presents innovative fully dynamic graph algorithms that maintain differential privacy while addressing multiple fundamental graph problems, filling a significant gap in current research, especially with its breakthrough in item-level privacy, which holds substantial theoretical and practical implications.