Private synthetic graph cut release

A cut splits a graph’s public vertices into two groups; its weight is the total edge weight between them. Can we publish a replacement graph that approximately preserves every cut while protecting private edge weights? Edge differential privacy limits how much the output distribution changes when the input weights change by at most one in total absolute value. The aim is a polynomial-time algorithm with small relative and additive cut error.

Why it matters and what counts as progress

Why it matters: One private replacement graph can support many later cut and clustering queries. Nearly linear additive error preserves more information about small cuts than larger polynomial error, while the privacy guarantee protects the strength or existence of individual relationships.

What counts as progress: Reduce relative or additive error under an explicit privacy definition, improve running time, or prove a lower bound. State whether the vertex set is public, which edge changes are protected, and whether computational cost counts exact-real operations or finite-bit operations.

How the problem developed

  1. 2012 · Information-theoretic benchmark [1]

    Jeremiah Blocki, Avrim Blum, Anupam Datta and Or Sheffet Obtained nearly linear additive error with relative error by selecting a cut sparsifier through the exponential mechanism. This approach did not give a polynomial-time implementation.

  2. 2025 · Efficient private release [1]

    Aamand and coauthors Used private expander decomposition to improve the efficient additive-error scale beyond n(3/2)n^{(3/2)}. Later work reduced it to n(13/12+o(1))n^{(13/12+o(1))}, leaving a gap to nearly linear error.

  3. 4 Nov 2026 · Nearly linear error in polynomial time [1][2]

    Eliáš and coauthors with GPT and Claude models Reported a polynomial-time edge-private algorithm preserving every cut with relative error and n polylog n additive error in the fixed-parameter regime. The authors verified and simplified the model-developed proofs; the Lean theorem uses an exact-real computational model.

Earlier milestones and prior bounds are described in the source manuscript’s introduction and references. Computational guarantees depend on the stated model and privacy parameters.

AI contribution

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.

AI involvementAI-centered
ImportanceNotable
Human understandingExplained
Paper date:

Sources

  1. Eliáš and coauthors: private synthetic graph release
  2. Lean formalization: main theorem, computation model and scope
  3. Lean theorem for privacy, accuracy and operation counts
Publication history