2026/07/21 by Chenglin Fan, Jingcheng Liu, Pan Peng +2
#cs.DS #cs.CR
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 \widetildeΘ(n3/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 (ε,δ)-differentially private algorithm which, for every n-vertex unweighted graph G, outputs a non-negative weighted synthetic graph \widetilde G such that, with high probability, every cut S⊆ V(G) satisfies |wG(S)-w\widetilde G(S)| ≤ γwG(S)+\widetilde Oε,δ,γ(n13/12+o(1)). This improves the previous polynomial-time worst-case bound \widetilde O(n5/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 \widetilde Oδ((nd)1/4/√ε) in estimating the graph Laplacian for graphs of maximum degree d, being the first to beat the standard min\2d,\widetilde Oδ(√(n)/ε)\ 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 \widetilde O(n+(n2M)1/3) on graphs with M edges, this yields the final worst-case \widetilde O(n13/12+o(1)) private cut-release error.