Misclassification Rate and Privacy-Utility Trade-offs in Graph Convolutional Networks via Subsampling Stability
The work offers a theoretical foundation for privacy-utility trade-offs in GCNs, which is important for privacy-preserving graph learning, but the results are theoretical and not yet validated empirically.
The paper derives upper bounds on misclassification rate for differentially private GCNs using subsampling stability, and characterizes the feasible range of subsampling probability to balance privacy and utility. It provides the first rigorous theoretical framework for subsampling stability in GCNs under DP.
We study differential privacy (DP) in Graph Convolutional Networks (GCNs) through the framework of \textit{subsampling stability}. We derive upper bounds on the misclassification rate that depend explicitly on the subsampling probability $p_s$. Furthermore, we characterize the \textit{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.