Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error

Marek Eliáš, Gautam Kamath, Janardhan Kulkarni, George Z. Li, Jingcheng Liu, Sepideh Mahabadi, Pan Peng, Jakub Tarnawski, Hangyu Xu, Zongrui ZouarXiv 2026 · arXiv

TL;DR

This paper introduces the first polynomial-time algorithm for differentially private synthetic graph release that achieves nearly-linear additive error. By combining semidefinite programming (SDP) with a novel "success-charged" privacy accounting scheme, the authors bridge a decade-long gap between theoretical lower bounds and computationally efficient algorithms for preserving graph cuts.

What Problem Does This Paper Address?

The core challenge is synthetic graph release: how can we share a version of a sensitive network (like a social graph or transaction log) that allows researchers to calculate "cut" values accurately while guaranteeing edge-level differential privacy (DP)? A cut value is simply the total weight of edges connecting two sets of vertices.

In the world of private graph analysis, there is a fundamental trade-off between relative error ($\gamma$) and additive error ($\alpha$). If you want zero relative error, the best possible additive error is $\Omega(n^{1.5})$, which is large enough to completely hide sparse, interesting structures in the graph. To get better accuracy on these small cuts, researchers allow a small amount of relative error.

Until now, we knew it was theoretically possible to achieve a nearly-linear additive error ($\tilde{O}(n)$), but the only known algorithms to do so required exponential time. Previous "efficient" (polynomial-time) algorithms were stuck with much higher error rates, such as $n^{1.25}$ or $n^{1.083}$. This paper finally delivers an algorithm that is both efficient and achieves the near-optimal $\tilde{O}(n)$ error rate.

Methods

The authors depart from the traditional "expander decomposition" paradigm and instead use a continuous Multiplicative Weights Update (MWU) framework. Their approach relies on three key technical pillars:

  1. Log-Det-Regularized SDP: To find "violating cuts" (areas where the synthetic graph is currently inaccurate), the algorithm solves a Semidefinite Program. The addition of a "log-det" (logarithm of the determinant) regularization term serves a dual purpose: it makes the optimization problem computationally tractable and ensures the solution is "stable," which is a prerequisite for differential privacy.
  2. Success-Charged Composition: This is the primary innovation in the privacy analysis. Standard privacy accounting "charges" the privacy budget for every iteration of an algorithm. Here, the authors only charge privacy loss based on the amount of "edge mass" that is successfully approximated and "retired" from the residual graph. This allows the algorithm to run for many iterations without exhausting the privacy budget.
  3. Lean Formalization: To ensure the highest level of mathematical rigor, the authors formalized their main results and privacy proofs in the Lean theorem prover, a tool increasingly used to verify complex mathematical research.

Datasets

As a theoretical work focused on algorithmic bounds and proofs, the paper does not use empirical datasets for training or evaluation. Instead, it provides rigorous mathematical proofs that the algorithm works for any non-negative weighted graph.

Key Insights and Ideas

  • Fractional Retirement: Instead of approximating the whole graph at once, the algorithm identifies portions of the graph it can accurately represent and "retires" them fractionally. This "telescoping" approach is what enables the improved privacy accounting.
  • Stability via Regularization: The insight that log-det regularization provides the specific type of "relative Frobenius error" stability needed to bound Gaussian likelihood ratios is central to making the SDP work for DP.
  • Tightness: The authors didn't just find an upper bound; they proved a matching lower bound of $\Omega(n/\gamma\varepsilon)$, showing that their nearly-linear additive error is essentially the best anyone can ever do in this parameter regime.

Key Results

The paper's results significantly push the state-of-the-art for private graph release, as summarized in the comparison table below:

Table 1: Comparison of error bounds for private all-cut release on an n-vertex, m-edge graph with weight vector w. The guarantee describes whether the synthetic graph preserves the true cut value wG(S) up to a purely additive error or a mixed relative-additive error. For simplicity, bounds are stated for constant privacy parameter ε = Θ(1) and δ = n−c.
  • Optimal Error: The algorithm achieves an additive error of $n \operatorname{polylog} n$, matching the best known exponential-time results in polynomial time.
  • Correlation Clustering: For the task of unweighted complete-graph correlation clustering, they reduced the approximation ratio from several thousand down to 1.387 while maintaining optimal additive error.
  • Max-Cut: They achieved the celebrated Goemans-Williamson approximation ratio (0.878) with nearly-linear additive error, improving on previous $n^{1.25}$ bounds.

The broader impact on various graph optimization problems is detailed in Table 2:

Table 2: Comparison of guarantees for the graph optimization and clustering applications in Section C. We write (ρ, B) for a guarantee of at most ρ OPT + B in minimization problems and at least ρ OPT −B in maximization problems. The displayed multiplicative ratios are obtained by instantiating our reductions with specific nonprivate algorithms. For the cut problems and correlation clustering, other nonprivate approximation ratios can likewise be transferred up to an arbitrarily small constant slack, retaining the shown additive bound and balance conditions. We assume ε = Θ(1) and δ = n−c for a fixed constant c > 0; ξ > 0 is an arbitrarily small fixed constant, and ρk is defined in Theorem 32. Entries citing [FLP+27] are derived baselines, obtained by combining their cut-release guarantee with the indicated nonprivate algorithms; these applications are not stated in their paper. Their cited release theorem is for unweighted input graphs. The entries citing only [ACD+25] are stated in its applications section for weighted graphs. The lower bounds for correlation clustering and for Max-Cut hold for approximate DP, establishing tightness of our approximate- DP guarantees. The balanced-cut lower bounds concern pure DP and weight privacy with the cited balance constraints and no multiplicative loss. For hierarchical clustering, the pure-DP lower bounds of [IEM+23, DGU+25] hold for every multiplicative factor o(n), while the approximate-DP lower bound of [IPR26] assumes no multiplicative loss.

Limitations and Future Work

  • Model Assumptions: The Lean formalization and the algorithm's runtime analysis are conducted in the "real RAM" model. This means they assume exact arithmetic and sampling, leaving the analysis of bit complexity and floating-point errors for future work.
  • Practical Constants: While the algorithm is polynomial-time, the "polylog" factors and hidden constants might be large. Practical implementations on smaller, real-world graphs would likely require further optimization of these constants.
  • Pure vs. Approximate DP: The results are for $(\varepsilon, \delta)$-differential privacy. Extending these nearly-linear bounds to "pure" $\varepsilon$-differential privacy (where $\delta=0$) remains a challenging open problem.

Summary updated

Abstract

We give a polynomial-time $(\varepsilon, δ)$-edge-differentially private algorithm that releases a synthetic graph approximately preserving all cut values of a nonnegative weighted input graph $G$. Our algorithm outputs a nonnegative weighted graph $H$ such that, with probability at least $1-β$, simultaneously for all $S\subseteq V$, \[ \left|w_G(S,V\setminus S)-w_H(S,V\setminus S)\right| \leq γw_G(S,V\setminus S) + O\left(\frac{n}{γ\varepsilon} \log^7 \frac{n}{δβγ\varepsilon}\right). \] For fixed $γ, \varepsilon$ and $δ= β= n^{-10}$, the additive error is $n \operatorname{polylog} n$, improving upon the previous efficient bound of $n^{13/12 + o(1)}$. Furthermore, we establish an $Ω(n/γ\varepsilon)$ lower bound for the relevant parameter regime, showing that our result is tight up to polylogarithmic factors. Our algorithm uses a log-det-regularized SDP to generate fractional queries for multiplicative-weights updates and certify accuracy for all cuts. The privacy analysis charges privacy loss only fractionally per mechanism call, based on the amount of mass on edge coordinates retired from subsequent iterations. Our synthetic graph release yields improved error bounds for several downstream tasks in private graph analysis including correlation clustering, Max-Cut, Max-$k$-Cut, constrained cut problems and hierarchical clustering. Most notably, for unweighted complete-graph correlation clustering, we achieve the optimal $\widetilde O(n)$ additive error while reducing the best previously known approximation ratio for this additive error from several thousand to $1.387$. We also provide a formalization of our results in Lean.
BibTeX
@misc{elias2026polynomial,
  author = {Marek Eliáš and Gautam Kamath and Janardhan Kulkarni and George Z. Li and Jingcheng Liu and Sepideh Mahabadi and Pan Peng and Jakub Tarnawski and Hangyu Xu and Zongrui Zou},
  title = {{Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error}},
  year = {2026},
  eprint = {2611.06670},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06670},
}

Loading related content...

Figure