Differentially Private Algorithms for Graphs UnderContinual Observation

We study differentially private graph algorithms under continual observation, i.e., for dynamic graph problems. The input is a sequence of graphs that results from node or edge updates, that is, insertions or deletions. We consider both non-local problems and local problems: problems are non-local if their value cannot be derived from the frequency histogram of constant-size subgraphs, and local otherwise. The only prior work on differentially private dynamic algorithms is an algorithm by Song et al.~~\cite{song18} for various graph problems such as counting high-degree nodes, triangles and other constant-size subgraphs. We present an algorithm for these local problems that improves the additive error by a factor of $\sqrt{T}/\log^{3/2}T$, where $T$ is the length of the graph sequence. Furthermore, we introduce the first differentially private algorithms for non-local graph problems in the partially dynamic setting, i.e., where only either insertions or deletions are allowed. These problems include the global and $s,t$-minimum cut, the cost of a minimum spanning tree and the density of the densest subgraph. We complement our upper bounds for these problems by giving some lower bounds on the additive error of any differentially private dynamic graph algorithm. By a reduction from differentially private counting we can show lower bounds of $\Omega(W \log T)$, resp. $\Omega(\log T)$, for the problems we study, where $W$ is the maximum edge weight. All these results apply to the event-level, where adjacent graph sequences differ in a single insertion or deletion. For the more challenging notion of user-level privacy, where adjacent graph sequences differ in any number of updates to a single edge or node, we show strong lower bounds that are linear in the maximum function value.