Almost linear time differentially private release of synthetic graphs
This work addresses the challenge of efficiently generating private synthetic graphs for data analysis, representing a significant advancement over previous methods in terms of computational efficiency.
The paper tackles the problem of differentially private release of synthetic graphs, achieving almost linear time and space algorithms that output a synthetic graph approximating all cuts and the spectrum of the input graph, with time complexity of O~(m) and space complexity of O(m).
In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an $\ell_1$-score function defined over an exponentially large non-convex set. As a direct result, on input an $n$ vertex $m$ edges graph $G$, we present the \textit{first} $\widetilde{O}(m)$ time and $O(m)$ space algorithms for differentially privately outputting an $n$ vertex $O(m)$ edges synthetic graph that approximates all the cuts and the spectrum of $G$. These are the \emph{first} private algorithms for releasing synthetic graphs that nearly match this task's time and space complexity in the non-private setting while achieving the same (or better) utility as the previous works in the more practical sparse regime. Additionally, our algorithms can be extended to private graph analysis under continual observation.