# Almost linear time differentially private release of synthetic graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 56 references that are in the map.
- First posted on arXiv 4 Jun 2024.

## Builds on (most cited first, 20 of 20)

- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Robin Hood and Matthew Effects: Differential Privacy Has Disparate Impact on Synthetic Data](https://mlsanity.com/paper/2109.11429/) (2021)
- [The Price of Differential Privacy under Continual Observation](https://mlsanity.com/paper/2112.00828/) (2021)
- [Almost Tight Error Bounds on Differentially Private Continual Counting](https://mlsanity.com/paper/2211.05006/) (2022)
- [Constant matters: Fine-grained Complexity of Differentially Private Continual Observation](https://mlsanity.com/paper/2202.11205/) (2022)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [Optimality of the Laplace Mechanism in Differential Privacy](https://mlsanity.com/paper/1504.00065/) (2015)
- [A Unifying Framework for Differentially Private Sums under Continual Observation](https://mlsanity.com/paper/2307.08970/) (2023)
- [Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates](https://mlsanity.com/paper/1506.04838/) (2015)
- [Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid](https://mlsanity.com/paper/1811.01816/) (2018)
- [Distances Release with Differential Privacy in Tree and Grid Graph](https://mlsanity.com/paper/2204.12488/) (2022)
- [Shortest Paths and Distances with Differential Privacy](https://mlsanity.com/paper/1511.04631/) (2015)
- [Optimal Bounds on Private Graph Approximation](https://mlsanity.com/paper/2309.17330/) (2023)
- [Quantifying Differential Privacy in Continuous Data Release under Temporal Correlations](https://mlsanity.com/paper/1711.11436/) (2017)
- [Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids](https://mlsanity.com/paper/1807.00929/) (2018)
- [Modified log-Sobolev inequalities for strongly log-concave distributions](https://mlsanity.com/paper/1903.06081/) (2019)
- [Differentially Private Sparse Vectors with Low Error, Optimal Space, and Fast Access](https://mlsanity.com/paper/2106.10068/) (2021)
- [Sparsity of weighted networks: measures and applications](https://mlsanity.com/paper/2009.06310/) (2020)
- [The Discrepancy of Shortest Paths](https://mlsanity.com/paper/2401.15781/) (2024)
- [Sparsified Cholesky Solvers for SDD linear systems](https://mlsanity.com/paper/1506.08204/) (2015)

## Abstract (arXiv)

In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an ℓ1-score function defined over an exponentially large non-convex set. As a direct result, on input an n vertex m edges graph G, we present the textitfirst widetildeO(m) time and O(m) space algorithms for differentially privately outputting an n vertex O(m) edges synthetic graph that approximates all the cuts and the spectrum of G. These are the first private algorithms for releasing synthetic graphs that nearly match this task's time and space complexity in the non-private setting while achieving the same (or better) utility as the previous works in the more practical sparse regime. Additionally, our algorithms can be extended to private graph analysis under continual observation.