# Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 20 references that are in the map.
- First posted on arXiv 3 May 2026.

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

- [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)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Stealing Links from Graph Neural Networks](https://mlsanity.com/paper/2005.02131/) (2020)
- [Membership Inference Attack on Graph Neural Networks](https://mlsanity.com/paper/2101.06570/) (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)
- [PAC-Bayes Un-Expected Bernstein Inequality](https://mlsanity.com/paper/1905.13367/) (2019)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [ProGAP: Progressive Graph Neural Networks with Differential Privacy Guarantees](https://mlsanity.com/paper/2304.08928/) (2023)
- [Training Differentially Private Graph Neural Networks with Random Walk Sampling](https://mlsanity.com/paper/2301.00738/) (2023)
- [Stability of Graph Convolutional Neural Networks through the lens of small perturbation analysis](https://mlsanity.com/paper/2312.12934/) (2023)
- [On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models](https://mlsanity.com/paper/2505.05816/) (2025)

## Abstract (arXiv)

We study differential privacy (DP) in Graph Convolutional Networks (GCNs) through the framework of textitsubsampling stability. We derive upper bounds on the misclassification rate that depend explicitly on the subsampling probability ps. Furthermore, we characterize the textitprivacy--utility trade-off by identifying feasible ranges of ps; if ps is too large, the stability-based privacy condition becomes difficult to satisfy, yielding vacuous guarantees, whereas if it is too small, accuracy deteriorates. Our results provide the first rigorous theoretical framework for understanding subsampling stability in GCNs under DP.