Breaking the n1.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 bestknown private and efficient cut sparsifiers on n-node graphs approximate each cut within O(n 1.5 ) additive error and 1 + γ multiplicative error for any γ > 0 [Gupta, Roth, Ullman TCC'12]. In contrast, inefficient algorithms, i.e., those requiring exponential time, can achieve an O(n) additive error and 1 + γ 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 (ε, δ)-DP polynomial time algorithm that, given a non-negative weighted graph, outputs a private synthetic graph approximating all cuts with multiplicative error 1 + γ and additive error n 1.25+o(1) (ignoring dependencies on ε, δ, γ). At the heart of our approach lies a private algorithm for expander decomposition, a popular and powerful technique in (non-private) graph algorithms.