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 Zou

For a nonnegative weighted graph on n public vertices, the authors give a polynomial-time (ε,δ)(\varepsilon ,\delta )-edge-private algorithm releasing another nonnegative weighted graph. With probability at least 1−β1-\beta , every cut has error at most γ\gamma times its original weight plus O(n/(γε)⋅log⁡7(n/(δβγε)))O(n/(\gamma \varepsilon ) \cdot \log ^{7}(n/(\delta \beta \gamma \varepsilon ))). The theorem assumes n≥2n\ge 2, 0<γ≤1/40<\gamma \le 1/4, 0<ε≤10<\varepsilon \le 1 and 0<δ0<\delta ,β<1/10\beta <1/10. Neighbouring edge-weight vectors differ by at most one in total absolute weight.

What was already known

Earlier polynomial-time methods achieved additive error n(13/12+o(1))n^{(13/12+o(1))} for fixed privacy and relative-error parameters. Nearly linear error was known without a polynomial-time implementation. The new algorithm attains n polylog n error for fixed γ\gamma and ε\varepsilon and δ=β=n−10\delta =\beta =n^{-10}.

AI involvement AI-centered

Section 6 credits AI systems with developing the first proofs of the main privacy theorems: an initial GPT-5.5 proof and later simpler GPT-5.6 and Claude 4.6 proofs. GPT-6 Astra and Claude Opus 5.5 helped refine proofs and generate Lean code. The authors selected among algorithms, verified and simplified the proofs, and restructured the presentation.

Importance Notable

The result closes the computational gap for private all-cut release up to logarithmic factors in the stated regime. It preserves cut information useful for graph optimization while protecting edge weights. The paper also proves a near-matching lower bound; downstream clustering guarantees are separate results.

Technical verification Formal (Lean 4 with Mathlib + human)

The authors report verifying the algorithms and proofs. Their pinned Lean project reports a single theorem checking privacy, simultaneous cut accuracy and worst-case polynomial operation counts for an ellipsoid-based implementation, using only Lean’s standard axioms. Its computational model uses exact real arithmetic and exact Gaussian and Laplace sampling; bit complexity is outside the theorem. These are source-reported human and machine checks.

Formal checking

The authors report verifying the algorithms and proofs. Their pinned Lean project reports a single theorem checking privacy, simultaneous cut accuracy and worst-case polynomial operation counts for an ellipsoid-based implementation, using only Lean’s standard axioms. Its computational model uses exact real arithmetic and exact Gaussian and Laplace sampling; bit complexity is outside the theorem. These are source-reported human and machine checks.

Checker
Lean 4 kernel; Eliáš and coauthors
Scope
Main exact-real computational theorem; human proof verification separately reported
Basis
Reported by the linked checker

Human understanding Explained

The authors explain the fractional witness construction and privacy accounting. A regularized optimization problem identifies portions of the remaining graph to release; the privacy charge tracks the fraction of each edge retired from later iterations. They simplified and rewrote the model-developed proofs and connect this accounting to earlier composition methods.

Correction and publication history

2026-11-05 · publication

New source-reviewed algorithm with documented central model proof development and author checking; exact computational model retained.

Read this published revision