mlsanityData to 7 Oct 2026

SoK: Differential Privacy on Graph-Structured Data

arXiv 2203.09205 ↗First posted 17 Mar 2022cs.CR cs.AI cs.LGcited by 9

Not on the map. Why?

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.

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

Builds on

41 of 114 references.

References · 41

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2016Deep Learning with Differential Privacycited by 2,682
  3. 2016Membership Inference Attacks against Machine Learning Modelscited by 2,221
  4. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  5. 2019Graph Neural Networks for Social Recommendationcited by 711
  6. 2020GCC: Graph Contrastive Coding for Graph Neural Network Pre-Trainingcited by 461
  7. 2017Large-scale Point Cloud Semantic Segmentation with Superpoint Graphscited by 384
  8. 2016Semi-supervised Knowledge Transfer for Deep Learning from Private Training Datacited by 347
  9. 2020GPT-GNN: Generative Pre-Training of Graph Neural Networkscited by 302
  10. 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 237
  11. 2020Differentially Private Learning Needs Better Features (or Much More Data)cited by 233
  12. 2018Disease Prediction using Graph Convolutional Networks: Application to Autism Spectrum Disorder and Alzheimer's Diseasecited by 98
29 more
  1. 2022Toward Training at ImageNet Scale with Differential Privacycited by 87
  2. 2021Membership Inference Attack on Graph Neural Networkscited by 81
  3. 2021Node-Level Membership Inference Attacks Against Graph Neural Networkscited by 80
  4. 2020Locally Private Graph Neural Networkscited by 64
  5. 2020Neither Private Nor Fair: Impact of Data Imbalance on Utility and Fairness in Differential Privacycited by 61
  6. 2016Discrete Distribution Estimation under Local Privacycited by 58
  7. 2020Individual Privacy Accounting via a Renyi Filtercited by 57
  8. 2020Learning Algebraic Multigrid Using Graph Neural Networkscited by 54
  9. 2021GraphMI: Extracting Private Graph Data from Graph Neural Networkscited by 50
  10. 2021Node-Level Differentially Private Graph Neural Networkscited by 43
  11. 2020Pre-Training Graph Neural Networks for Cold-Start Users and Items Representationcited by 42
  12. 2019Graph Neural Network for Interpreting Task-fMRI Biomarkerscited by 40
  13. 2021Releasing Graph Neural Networks with Differential Privacy Guaranteescited by 32
  14. 2019Exploring Graph Neural Networks for Stock Market Predictions with Rolling Window Analysiscited by 27
  15. 2021Privacy-Preserving Graph Convolutional Networks for Text Classificationcited by 19
  16. 2020Locally Differentially Private Analysis of Graph Statisticscited by 17
  17. 2021"I need a better description'': An Investigation Into User Expectations For Differential Privacycited by 17
  18. 2013Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins [Full Version, Draft 0.1]cited by 13
  19. 2019Efficiently Estimating Erdos-Renyi Graphs with Node Differential Privacycited by 13
  20. 2021Differentially Private Algorithms for Graphs Under Continual Observationcited by 12
  21. 2021Defending Medical Image Diagnostics against Privacy Attacks using Generative Methodscited by 8
  22. 2017Evaluating Graph Signal Processing for Neuroimaging Through Classification and Dimensionality Reductioncited by 7
  23. 2015Shortest Paths and Distances with Differential Privacycited by 6
  24. 2013Mining Frequent Graph Patterns with Differential Privacycited by 4
  25. 2019Publishing Community-Preserving Attributed Social Graphs with a Differential Privacy Guaranteecited by 4
  26. 2021Community Preserved Social Graph Publishing with Node Differential Privacycited by 2
  27. 2021An automatic differentiation system for the age of differential privacycited by 2
  28. 2021Network Generation with Differential Privacycited by 2
  29. 2021A unified interpretation of the Gaussian mechanism for differential privacy through the sensitivity indexcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 2; 2025: 3; 2026: 1.

9 papers.

  1. 2026Graph-based Agent Memory: Taxonomy, Techniques, and Applicationscited by 22
  2. 2023Differentially Private Decoupled Graph Convolutions for Multigranular Topology Protectioncited by 12
  3. 2023Training Differentially Private Graph Neural Networks with Random Walk Samplingcited by 5
  4. 2023Node Injection Link Stealing Attackcited by 3
  5. 2025Intellectual Property in Graph-Based Machine Learning as a Service: Attacks and Defensescited by 2
  6. 2024Chase Anonymisation: Privacy-Preserving Knowledge Graphs with Logical Reasoningcited by 1
  7. 2024GraphPub: Generation of Differential Privacy Graph with High Availabilitycited by 0
  8. 2025Differentially Private Relational Learning with Entity-level Privacy Guaranteescited by 0
  9. 2025Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsamplingcited by 0