Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error
Abstract
We give a polynomial-time (ε, δ)-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⊆ V, |wG(S,V∖ S)−wH(S,V∖ S)| ≤ γwG(S,V∖ S) + O(n/γε log7 n/δβγε). For fixed γ, ε and δ= β= n−10, the additive error is n polylog n, improving upon the previous efficient bound of n13/12 + o(1). Furthermore, we establish an Ω(n/γε) 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 Õ(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.
Related
- Differentially Private Synthetic Data via Generalized Moment Matching
- Tight End-to-End Accounting for Differentially Private Synthetic Data
- Differentially Private Average Treatment Effect Estimation by Propensity Score Blocking
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
BibTeX
@misc{elias2026polynomialtime,
title = {{Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error}},
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},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06670},
eprint = {2611.06670},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06670},
}
RIS
TY - UNPB
TI - Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error
AU - Marek Eliáš
AU - Gautam Kamath
AU - Janardhan Kulkarni
AU - George Z. Li
AU - Jingcheng Liu
AU - Sepideh Mahabadi
AU - Pan Peng
AU - Jakub Tarnawski
AU - Hangyu Xu
AU - Zongrui Zou
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06670
UR - https://arxiv.org/abs/2611.06670
AB - We give a polynomial-time (ε, δ)-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⊆ V, |w_G(S,V∖ S)−w_H(S,V∖ S)| ≤ γw_G(S,V∖ S) + O(n/γε log^7 n/δβγε). For fixed γ, ε and δ= β= n^−10, the additive error is n polylog n, improving upon the previous efficient bound of n^13/12 + o(1). Furthermore, we establish an Ω(n/γε) 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 Õ(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.
ER -