# SoK: Differential Privacy on Graph-Structured Data

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 114 references that are in the map.
- First posted on arXiv 17 Mar 2022.

## Builds on (most cited first, 30 of 41)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training](https://mlsanity.com/paper/2006.09963/) (2020)
- [Large-scale Point Cloud Semantic Segmentation with Superpoint Graphs](https://mlsanity.com/paper/1711.09869/) (2017)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [GPT-GNN: Generative Pre-Training of Graph Neural Networks](https://mlsanity.com/paper/2006.15437/) (2020)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Differentially Private Learning Needs Better Features (or Much More Data)](https://mlsanity.com/paper/2011.11660/) (2020)
- [Disease Prediction using Graph Convolutional Networks: Application to Autism Spectrum Disorder and Alzheimer's Disease](https://mlsanity.com/paper/1806.01738/) (2018)
- [Toward Training at ImageNet Scale with Differential Privacy](https://mlsanity.com/paper/2201.12328/) (2022)
- [Node-Level Membership Inference Attacks Against Graph Neural Networks](https://mlsanity.com/paper/2102.05429/) (2021)
- [Membership Inference Attack on Graph Neural Networks](https://mlsanity.com/paper/2101.06570/) (2021)
- [Locally Private Graph Neural Networks](https://mlsanity.com/paper/2006.05535/) (2020)
- [Neither Private Nor Fair: Impact of Data Imbalance on Utility and Fairness in Differential Privacy](https://mlsanity.com/paper/2009.06389/) (2020)
- [Discrete Distribution Estimation under Local Privacy](https://mlsanity.com/paper/1602.07387/) (2016)
- [Individual Privacy Accounting via a Renyi Filter](https://mlsanity.com/paper/2008.11193/) (2020)
- [Learning Algebraic Multigrid Using Graph Neural Networks](https://mlsanity.com/paper/2003.05744/) (2020)
- [GraphMI: Extracting Private Graph Data from Graph Neural Networks](https://mlsanity.com/paper/2106.02820/) (2021)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Pre-Training Graph Neural Networks for Cold-Start Users and Items Representation](https://mlsanity.com/paper/2012.07064/) (2020)
- [Graph Neural Network for Interpreting Task-fMRI Biomarkers](https://mlsanity.com/paper/1907.01661/) (2019)
- [Releasing Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2109.08907/) (2021)
- [Exploring Graph Neural Networks for Stock Market Predictions with Rolling Window Analysis](https://mlsanity.com/paper/1909.10660/) (2019)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Privacy-Preserving Graph Convolutional Networks for Text Classification](https://mlsanity.com/paper/2102.09604/) (2021)
- ["I need a better description'': An Investigation Into User Expectations For Differential Privacy](https://mlsanity.com/paper/2110.06452/) (2021)
- [Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins [Full Version, Draft 0.1]](https://mlsanity.com/paper/1304.4795/) (2013)

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

- [Graph-based Agent Memory: Taxonomy, Techniques, and Applications](https://mlsanity.com/paper/2602.05665/) (2026)
- [Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protection](https://mlsanity.com/paper/2307.06422/) (2023)
- [Training Differentially Private Graph Neural Networks with Random Walk Sampling](https://mlsanity.com/paper/2301.00738/) (2023)
- [Node Injection Link Stealing Attack](https://mlsanity.com/paper/2307.13548/) (2023)
- [Intellectual Property in Graph-Based Machine Learning as a Service: Attacks and Defenses](https://mlsanity.com/paper/2508.19641/) (2025)
- [GraphPub: Generation of Differential Privacy Graph with High Availability](https://mlsanity.com/paper/2403.00030/) (2024)
- [Chase Anonymisation: Privacy-Preserving Knowledge Graphs with Logical Reasoning](https://mlsanity.com/paper/2410.12418/) (2024)
- [Differentially Private Relational Learning with Entity-level Privacy Guarantees](https://mlsanity.com/paper/2506.08347/) (2025)
- [Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling](https://mlsanity.com/paper/2510.11640/) (2025)
- [EdgeRefine: Privacy-Utility Balance for Graphs via Jaccard Sampling under Edge Differential Privacy](https://mlsanity.com/paper/2607.08659/) (2026)

## Abstract (arXiv)

In this work, we study the applications of differential privacy (DP) in the context of graph-structured data. We discuss the formulations of DP applicable to the publication of graphs and their associated statistics as well as machine learning on graph-based data, including graph neural networks (GNNs). The formulation of DP in the context of graph-structured data is difficult, as individual data points are interconnected (often non-linearly or sparsely). This connectivity complicates the computation of individual privacy loss in differentially private learning. The problem is exacerbated by an absence of a single, well-established formulation of DP in graph settings. This issue extends to the domain of GNNs, rendering private machine learning on graph-structured data a challenging task. A lack of prior systematisation work motivated us to study graph-based learning from a privacy perspective. In this work, we systematise different formulations of DP on graphs, discuss challenges and promising applications, including the GNN domain. We compare and separate works into graph analysis tasks and graph learning tasks with GNNs. Finally, we conclude our work with a discussion of open questions and potential directions for further research in this area.