Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error

Source: arxiv.org/abs/2611.06670

Marek Eliáš, Gautam Kamath, Janardhan Kulkarni, George Z. Li, Jingcheng Liu, Sepideh Mahabadi, Pan Peng, Jakub Tarnawski, Hangyu Xu, Zongrui Zou

arXivarxiv/2611.06670Nov 4, 2026cs.DSscore 0

We give a polynomial-time $(\varepsilon, δ)$-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\subseteq V$, \[ \left|w_G(S,V\setminus S)-w_H(S,V\setminus S)\right| \leq γw_G(S,V\setminus S) + O\left(\frac{n}{γ\varepsilon} \log^7 \frac{n}{δβγ\varepsilon}\right). \] For fixed $γ, \varepsilon$ and $δ= β= n^{-10}$, the additive error is $n \operatorname{polylog} n$,…

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.06670
curl -X POST /api/v1/records/arxiv/2611.06670/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06670/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'