# Training Differentially Private Graph Neural Networks with Random Walk Sampling

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 21 references that are in the map.
- First posted on arXiv 2 Jan 2023.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Large Language Models Can Be Strong Differentially Private Learners](https://mlsanity.com/paper/2110.05679/) (2021)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Subsampled R'enyi Differential Privacy and Analytical Moments Accountant](https://mlsanity.com/paper/1808.00087/) (2018)
- [Large-Scale Differentially Private BERT](https://mlsanity.com/paper/2108.01624/) (2021)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Hypothesis Testing Interpretations and Renyi Differential Privacy](https://mlsanity.com/paper/1905.09982/) (2019)
- [Membership Inference Attack on Graph Neural Networks](https://mlsanity.com/paper/2101.06570/) (2021)
- [LinkTeller: Recovering Private Edges from Graph Neural Networks via Influence Analysis](https://mlsanity.com/paper/2108.06504/) (2021)
- [Locally Private Graph Neural Networks](https://mlsanity.com/paper/2006.05535/) (2020)
- [GraphMI: Extracting Private Graph Data from Graph Neural Networks](https://mlsanity.com/paper/2106.02820/) (2021)
- [GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation](https://mlsanity.com/paper/2203.00949/) (2022)
- [Node-Level Differentially Private Graph Neural Networks](https://mlsanity.com/paper/2111.15521/) (2021)
- [Privacy-Preserving Graph Convolutional Networks for Text Classification](https://mlsanity.com/paper/2102.09604/) (2021)
- [SoK: Differential Privacy on Graph-Structured Data](https://mlsanity.com/paper/2203.09205/) (2022)

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

- [Just One Byte (per gradient): A Note on Low-Bandwidth Decentralized Language Model Finetuning Using Shared Randomness](https://mlsanity.com/paper/2306.10015/) (2023)
- [ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2304.08928/) (2023)
- [Edge Private Graph Neural Networks with Singular Value Perturbation](https://mlsanity.com/paper/2403.10995/) (2024)
- [Adversarial Attacks on Locally Private Graph Neural Networks](https://mlsanity.com/paper/2603.20746/) (2026)
- [Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stability](https://mlsanity.com/paper/2605.01987/) (2026)

## Abstract (arXiv)

Deep learning models are known to put the privacy of their training data at risk, which poses challenges for their safe and ethical release to the public. Differentially private stochastic gradient descent is the de facto standard for training neural networks without leaking sensitive information about the training data. However, applying it to models for graph-structured data poses a novel challenge: unlike with i.i.d. data, sensitive information about a node in a graph cannot only leak through its gradients, but also through the gradients of all nodes within a larger neighborhood. In practice, this limits privacy-preserving deep learning on graphs to very shallow graph neural networks. We propose to solve this issue by training graph neural networks on disjoint subgraphs of a given training graph. We develop three random-walk-based methods for generating such disjoint subgraphs and perform a careful analysis of the data-generating distributions to provide strong privacy guarantees. Through extensive experiments, we show that our method greatly outperforms the state-of-the-art baseline on three large graphs, and matches or outperforms it on four smaller ones.