# ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 55 references that are in the map.
- First posted on arXiv 18 Apr 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Progressive Growing of GANs for Improved Quality, Stability, and Variation](https://mlsanity.com/paper/1710.10196/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Self-Normalizing Neural Networks](https://mlsanity.com/paper/1706.02515/) (2017)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [Graph Neural Network for Traffic Forecasting: A Survey](https://mlsanity.com/paper/2101.11174/) (2021)
- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [DeepInf: Social Influence Prediction with Deep Learning](https://mlsanity.com/paper/1807.05560/) (2018)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings](https://mlsanity.com/paper/2106.05609/) (2021)
- [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)
- [Decoupled Greedy Learning of CNNs](https://mlsanity.com/paper/1901.08164/) (2019)
- [A Review on Graph Neural Network Methods in Financial Applications](https://mlsanity.com/paper/2111.15367/) (2021)
- [Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future](https://mlsanity.com/paper/2105.13137/) (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)
- [A Fully Progressive Approach to Single-Image Super-Resolution](https://mlsanity.com/paper/1804.02900/) (2018)

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

- [Differentially Private Graph Diffusion with Applications in Personalized PageRanks](https://mlsanity.com/paper/2407.00077/) (2024)
- [Activity Recognition on Avatar-Anonymized Datasets with Masked Differential Privacy](https://mlsanity.com/paper/2410.17098/) (2024)
- [Can Linear Probes Measure LLM Uncertainty?](https://mlsanity.com/paper/2510.04108/) (2025)
- [Privately Learning from Graphs with Applications in Fine-tuning Large Language Models](https://mlsanity.com/paper/2410.08299/) (2024)
- [AdvSGM: Differentially Private Graph Learning via Adversarial Skip-gram Model](https://mlsanity.com/paper/2503.21426/) (2025)
- [Differentially Private Graph Neural Network with Importance-Grained Noise Adaption](https://mlsanity.com/paper/2308.04943/) (2023)
- [Structure-Preference Enabled Graph Embedding Generation under Differential Privacy](https://mlsanity.com/paper/2501.03451/) (2025)
- [DP-GPL: Differentially Private Graph Prompt Learning](https://mlsanity.com/paper/2503.10544/) (2025)
- [Differentially Private Relational Learning with Entity-level Privacy Guarantees](https://mlsanity.com/paper/2506.08347/) (2025)
- [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)
- [PriDyG: Privacy-preserving Dynamic Graph Inference with LLM-GNN Collaboration](https://mlsanity.com/paper/2608.04255/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have become a popular tool for learning on graphs, but their widespread use raises privacy concerns as graph data can contain personal or sensitive information. Differentially private GNN models have been recently proposed to preserve privacy while still allowing for effective learning over graph-structured datasets. However, achieving an ideal balance between accuracy and privacy in GNNs remains challenging due to the intrinsic structural connectivity of graphs. In this paper, we propose a new differentially private GNN called ProGAP that uses a progressive training scheme to improve such accuracy-privacy trade-offs. Combined with the aggregation perturbation technique to ensure differential privacy, ProGAP splits a GNN into a sequence of overlapping submodels that are trained progressively, expanding from the first submodel to the complete model. Specifically, each submodel is trained over the privately aggregated node embeddings learned and cached by the previous submodels, leading to an increased expressive power compared to previous approaches while limiting the incurred privacy costs. We formally prove that ProGAP ensures edge-level and node-level privacy guarantees for both training and inference stages, and evaluate its performance on benchmark graph datasets. Experimental results demonstrate that ProGAP can achieve up to 5-10% higher accuracy than existing state-of-the-art differentially private GNNs. Our code is available at https://github.com/sisaman/ProGAP.