Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers

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 (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, delta) -differentially private algorithm which, for every n-vertex unweighted graph G, outputs a non-negative weighted synthetic graph G such that, with high probability, every cut S V(G) satisfies [ w G(S)-w G (S) gamma w G(S)+ O epsilon, delta, gamma(n 13/12+o(1)).] This improves the previous polynomial-time worst-case bound 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 O delta((nd) 1/4/sqrt epsilon) in estimating the graph Laplacian for graphs of maximum degree d, being the first to beat the standard 2d, O delta(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 O(n+(n 2M) 1/3) on graphs with M edges, this yields the final worst-case O(n 13/12+o(1)) private cut-release error.