Leveraging Graph Clustering for Differentially Private Graph Neural Networks

Differential Privacy is a standard approach for ensuring privacy in deep learning models, but its effectiveness is less certain when applied to message-passing Graph Neural Networks (GNNs). GNNs, which process graph-structured data, generate node representations by aggregating information from neighboring nodes. At the k-th layer, GNNs propagate information across a node’s k-hop neighborhood, causing interconnected nodes to influence each other’s representations. Consequently, protecting the privacy of a single node, edge, or feature often requires safeguarding information about related graph elements as well. Previous methods have addressed this issue by injecting noise into the data, though finding the right balance is challenging; while more noise increases privacy, excessive noise degrades model output. Other approaches use custom architectures to decouple neighborhood aggregation from node representation learning, but these solutions often struggle to scale to large graphs. We propose a strategy for training subgraph-level DP-GNNs by extracting disjoint subgraphs from the training dataset and applying the DP-SGD algorithm, treating each subgraph as an independent sample. This method protects the privacy of target nodes and their neighbors. Our graph partitioning approach is inspired by community detection techniques, which help preserve relevant connections within partitions. By restructuring the training data, our solution enhances privacy protection while maintaining model utility, ultimately outperforming existing techniques.