Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition

We study differentially private algorithms for graph cut sparsification, a fundamental problem in algorithms, privacy, and machine learning. While significant progress has been made, the best-known private and efficient cut sparsifiers on $n$-node graphs approximate each cut within $\widetilde{O}(n^{1.5})$ additive error and $1+\gamma$ multiplicative error for any $\gamma > 0$ [Gupta, Roth, Ullman TCC'12]. In contrast, \emph{inefficient} algorithms, i.e., those requiring exponential time, can achieve an $\widetilde{O}(n)$ additive error and $1+\gamma$ multiplicative error [Eliáš, Kapralov, Kulkarni, Lee SODA'20]. In this work, we break the $n^{1.5}$ additive error barrier for private and efficient cut sparsification. We present an $(\varepsilon,\delta)$-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error $1+\gamma$ and additive error $n^{1.25 + o(1)}$ (ignoring dependencies on $\varepsilon, \delta, \gamma$). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.

Our algorithm aims to understand how communities in a large social network are connected without revealing anyone's personal information. More precisely, we study approximating cuts in graphs, which are the number of edges between a set of vertices and its complement, under the mathematical framework of differential privacy. Current `fast' methods that protect privacy often give answers that have a large theoretical error, with a known limit of error approximately proportional to $O(n^{1.5})$ where $n$ is the number of nodes.We develop a new algorithm that preserves privacy but obtains much smaller error (approximately of the order $O(n^{1.25})$ at the cost of a small multiplicative error), which still being `fast'. It works by first privately breaking down the network into dense, well-connected clusters and the sparser links between them. We carefully combine a different algorithm on the sparse and dense regions, leading to the improved error guarantees.