Differentially Private Graph Neural Networks for Link Prediction

Graph Neural Networks (GNNs) have proven to be highly effective in addressing the link prediction problem. However, the need for large amounts of user data to learn representations of user interactions raises concerns about data privacy. While differential privacy (DP) techniques have been widely used for node-level tasks in graphs, incorporating DP into GNNs for link prediction is challenging due to data dependency. To this end, in this work we propose a differentially private link prediction (DPLP) framework, building upon subgraph-based GNNs. DPLP includes a DP-compliant subgraph extraction module as its core component. We first propose a neighborhood subgraph extraction method, and carefully analyze its data dependency level. To reduce this dependency, we optimize DPLP by integrating a novel path subgraph extraction method, which alleviates the utility loss in GNNs by reducing the noise sensitivity. Theoretical analysis demonstrates that our approaches achieve a good balance between privacy protection and prediction accuracy, even when using GNNs with few layers. We extensively evaluate our approaches on benchmark datasets and show that they can learn accurate privacy-preserving GNNs and outperforms the existing methods for link prediction.