Almost linear time differentially private release of synthetic graphs

Zongrui Zou, Jingcheng Liu, Jalaj Upadhyay
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:289-297, 2025.

Abstract

In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an $\ell_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 first $\widetilde{O}(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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-zou25a, title = {Almost linear time differentially private release of synthetic graphs}, author = {Zou, Zongrui and Liu, Jingcheng and Upadhyay, Jalaj}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {289--297}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/zou25a/zou25a.pdf}, url = {https://proceedings.mlr.press/v258/zou25a.html}, abstract = {In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an $\ell_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 first $\widetilde{O}(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.} }
Endnote
%0 Conference Paper %T Almost linear time differentially private release of synthetic graphs %A Zongrui Zou %A Jingcheng Liu %A Jalaj Upadhyay %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-zou25a %I PMLR %P 289--297 %U https://proceedings.mlr.press/v258/zou25a.html %V 258 %X In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an $\ell_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 first $\widetilde{O}(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.
APA
Zou, Z., Liu, J. & Upadhyay, J.. (2025). Almost linear time differentially private release of synthetic graphs. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:289-297 Available from https://proceedings.mlr.press/v258/zou25a.html.

Related Material