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
- 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.
- 2025 · Efficient private release [1]
Aamand and coauthors Used private expander decomposition to improve the efficient additive-error scale beyond . Later work reduced it to , leaving a gap to nearly linear error.
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
For a nonnegative weighted graph on n public vertices, the authors give a polynomial-time -edge-private algorithm releasing another nonnegative weighted graph. With probability at least , every cut has error at most times its original weight plus . The theorem assumes , , and ,. Neighbouring edge-weight vectors differ by at most one in total absolute weight.
Sources
Publication history
Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error
Daily emails by default, only when there’s an update.