Sublinear Space Graph Algorithms in the Continual Release Model

Abstract

The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solutions are released after each update. Previously known edge differentially private algorithms for most graph problems including densest subgraph and matchings in the continual release setting only output real-valued estimates (not vertex subset solutions) and do not use sublinear space. In this paper, we leverage sparsification to address the above shortcomings for edge-insertion streams. Our edge differentially private algorithms use sublinear space with respect to the number of edges in the graph. In addition, for the densest subgraph problem, we output edge differentially private vertex subset solutions; no previous graph algorithms in the continual release model output such subsets.

We make novel use of sparsification techniques from the non-private streaming and static graph algorithms literature to achieve new results in the sublinear space continual release setting. This includes algorithms for densest subgraph, maximum matching, and the first continual release k-core decomposition algorithm. To complement our insertion-only algorithms, we conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting, where only logarithmic lower bounds were previously known.