  GNNs can inadvertently expose sensitive user information and interactions
through their model predictions. To address these privacy concerns,
Differential Privacy (DP) protocols are employed to control the trade-off
between provable privacy protection and model utility. Applying standard DP
approaches to GNNs directly is not advisable due to two main reasons. First,
the prediction of node labels, which relies on neighboring node attributes
through graph convolutions, can lead to privacy leakage. Second, in practical
applications, the privacy requirements for node attributes and graph topology
may differ. In the latter setting, existing DP-GNN models fail to provide
multigranular trade-offs between graph topology privacy, node attribute
privacy, and GNN utility. To address both limitations, we propose a new
framework termed Graph Differential Privacy (GDP), specifically tailored to
graph learning. GDP ensures both provably private model parameters as well as
private predictions. Additionally, we describe a novel unified notion of graph
dataset adjacency to analyze the properties of GDP for different levels of
graph topology privacy. Our findings reveal that DP-GNNs, which rely on graph
convolutions, not only fail to meet the requirements for multigranular graph
topology privacy but also necessitate the injection of DP noise that scales at
least linearly with the maximum node degree. In contrast, our proposed
Differentially Private Decoupled Graph Convolutions (DPDGCs) represent a more
flexible and efficient alternative to graph convolutions that still provides
the necessary guarantees of GDP. To validate our approach, we conducted
extensive experiments on seven node classification benchmarking and
illustrative synthetic datasets. The results demonstrate that DPDGCs
significantly outperform existing DP-GNNs in terms of privacy-utility
trade-offs.
