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

arXiv:2605.01987v1 Announce Type: new Abstract: We study differential privacy (DP) in Graph Convolutional Networks (GCNs) through the framework of extit{subsampling stability}. We derive upper bounds on the misclassification rate that depend explicitly on the subsampling probability p_s. Furthermore, we characterize the extit{privacy--utility trade-off} by identifying feasible ranges of p_s; if p_s 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.

Source: arXiv cs.LG | 2026-05-05