Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers

Abstract

We study the problem of releasing a synthetic graph that approximates the sizes of all cuts of an input graph under edge-level differential privacy. If one insists on purely additive error, the optimal worst-case error is $\tilde{\hat{I}}˜(n^{3/2})$. If one allows a small multiplicative slack, an information-theoretic exponential-time mechanism achieves nearly linear additive error, but the best known polynomial-time algorithms have substantially larger error. We give a polynomial-time $(\epsilon ,\hat{I}´)$-differentially private algorithm which, for every $n$-vertex unweighted graph $G$, outputs a non-negative weighted synthetic graph $\tilde{G}$ such that, with high probability, every cut $S\subseteq V(G)$ satisfies \[ |w_G(S)-w_{\widetilde G}(S)| \le γw_G(S)+\widetilde O_{\varepsilon,δ,γ}(n^{13/12+o(1)}). \] This improves the previous polynomial-time worst-case bound $\tilde{O}(n^{5/4+o(1)})$ of Aamand et al. (ICML 2025) for mixed multiplicative/additive private cut approximation. The main technical ingredient is a new set of private spectral primitives for bounded-degree graphs, one of them gives spectral error ${\tilde{O}}_{\hat{I}}´((nd{)}^{1/4}/\sqrt{\epsilon })$ in estimating the graph Laplacian for graphs of maximum degree $d$, being the first to beat the standard $\min \{2d,{\tilde{O}}_{\hat{I}}´(\sqrt{n}/\epsilon )\}$ baseline in the high-degree regime. We further develop a primitive with a sharper error dependence on $n$ and $d$ for the downstream cut approximation. Combined with a new edge-sensitive terminal cut oracle with additive error $\tilde{O}(n+(n^{2}M{)}^{1/3})$ on graphs with $M$ edges, this yields the final worst-case $\tilde{O}(n^{13/12+o(1)})$ private cut-release error.

77 pages