# Optimal Bounds on Private Graph Approximation

arXiv: https://arxiv.org/abs/2309.17330 · HTML: https://mlsanity.com/paper/2309.17330/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2023.

## Built on by (most cited first, 6 of 6)

- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [Differentially Private Synthetic Data Generation for Relational Databases](https://mlsanity.com/paper/2405.18670/) (2024)
- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)
- [Almost linear time differentially private release of synthetic graphs](https://mlsanity.com/paper/2406.02156/) (2024)
- [On the Price of Differential Privacy for Hierarchical Clustering](https://mlsanity.com/paper/2504.15580/) (2025)
- [Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling](https://mlsanity.com/paper/2510.11640/) (2025)

## Abstract (arXiv)

We propose an efficient ε-differentially private algorithm, that given a simple em weighted n-vertex, m-edge graph G with a maximum unweighted degree Delta(G) ≤ n-1, outputs a synthetic graph which approximates the spectrum with widetildeO(minDelta(G), √n) bound on the purely additive error. To the best of our knowledge, this is the first ε-differentially private algorithm with a non-trivial additive error for approximating the spectrum of the graph. One of the subroutines of our algorithm also precisely simulates the exponential mechanism over a non-convex set, which could be of independent interest given the recent interest in sampling from a em log-concave distribution defined over a convex set. Spectral approximation also allows us to approximate all possible (S,T)-cuts, but it incurs an error that depends on the maximum degree, Delta(G). We further show that using our sampler, we can also output a synthetic graph that approximates the sizes of all (S,T)-cuts on n vertices weighted graph G with m edges while preserving (ε,δ)-differential privacy and an additive error of widetildeO(√mn/ε). We also give a matching lower bound (with respect to all the parameters) on the private cut approximation for weighted graphs. This removes the gap of √W_mathsfavg in the upper and lower bound in Eli'avs, Kapralov, Kulkarni, and Lee (SODA 2020), where W_mathsfavg is the average edge weight.