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:
- 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.
- 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.
- 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:
- 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:
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