  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.
