# Empirical Auditing of Edge-Private Graph Generators

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 23 references that are in the map.
- First posted on arXiv 21 Sep 2026.

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

- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [TAPAS: a Toolbox for Adversarial Privacy Auditing of Synthetic Data](https://mlsanity.com/paper/2211.06550/) (2022)
- [A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis](https://mlsanity.com/paper/2010.05253/) (2020)
- [Private Graph Data Release: A Survey](https://mlsanity.com/paper/2107.04245/) (2021)
- [PrivGraph: Differentially Private Graph Data Publication by Exploiting Community Information](https://mlsanity.com/paper/2304.02401/) (2023)
- [Online Learning of Network Bottlenecks via Minimax Paths](https://mlsanity.com/paper/2109.08467/) (2021)
- [Differentially Private Exponential Random Graphs](https://mlsanity.com/paper/1409.4696/) (2014)
- [PGB: Benchmarking Differentially Private Synthetic Graph Generation Algorithms](https://mlsanity.com/paper/2408.02928/) (2024)

## Abstract (arXiv)

We empirically audit privacy leakage by testing whether outputs from edge-neighbouring inputs remain distinguishable, using statistically valid lower bounds on the privacy loss witnessed by our attacks. Our framework compares direct-edge, local-structural, and GNN-based attacks through the geometry surrounding a target edge. Experiments across two generators and two networks show that privacy leakage is both mechanism- and network-dependent, with learned representations revealing information not captured by conventional local statistics.