# Graph Structure Learning with Privacy Guarantees for Open Graph Data

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 66 references that are in the map.
- First posted on arXiv 25 Jul 2025.

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

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [The Discrete Gaussian for Differential Privacy](https://mlsanity.com/paper/2004.00010/) (2020)
- [AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data](https://mlsanity.com/paper/2201.12677/) (2022)
- [CoAID: COVID-19 Healthcare Misinformation Dataset](https://mlsanity.com/paper/2006.00885/) (2020)
- [GLAD: Learning Sparse Graph Recovery](https://mlsanity.com/paper/1906.00271/) (2019)
- [Chickenpox Cases in Hungary: a Benchmark Dataset for Spatiotemporal Signal Processing with Graph Neural Networks](https://mlsanity.com/paper/2102.08100/) (2021)
- [Urban MV and LV Distribution Grid Topology Estimation via Group Lasso](https://mlsanity.com/paper/1611.01845/) (2016)
- [Utilizing Noise Addition for Data Privacy, an Overview](https://mlsanity.com/paper/1309.3958/) (2013)
- [Gaussian Mixture Graphical Lasso with Application to Edge Detection in Brain Networks](https://mlsanity.com/paper/2101.05348/) (2021)
- [From t-closeness to differential privacy and vice versa in data anonymization](https://mlsanity.com/paper/1512.05110/) (2015)
- [Differentially Private Precision Matrix Estimation](https://mlsanity.com/paper/1909.02750/) (2019)
- [GLIMG: Global and Local Item Graphs for Top-N Recommender Systems](https://mlsanity.com/paper/2007.14018/) (2020)

## Abstract (arXiv)

Publishing open graph data while preserving individual privacy remains challenging when data publishers and data users are distinct entities. Although differential privacy (DP) provides rigorous guarantees, most existing approaches enforce privacy during model training rather than at the data publishing stage. This limits the applicability to open-data scenarios. We propose a privacy-preserving graph structure learning framework that integrates Gaussian Differential Privacy (GDP) directly into the data release process. Our mechanism injects structured Gaussian noise into raw data prior to publication and provides formal μ-GDP guarantees, leading to tight (varepsilon, δ)-differential privacy bounds. Despite the distortion introduced by privatization, we prove that the original sparse inverse covariance structure can be recovered through an unbiased penalized likelihood formulation. We further extend the framework to discrete data using discrete Gaussian noise while preserving privacy guarantees. Extensive experiments on synthetic and real-world datasets demonstrate strong privacy-utility trade-offs, maintaining high graph recovery accuracy under rigorous privacy budgets. Our results establish a formal connection between differential privacy theory and privacy-preserving data publishing for graphical models.