Training Differentially Private Graph Neural Networks with Random Walk Sampling
This work addresses privacy risks in graph-structured data for machine learning applications, offering a novel solution to enable deeper GNNs with strong privacy guarantees.
The paper tackled the challenge of training differentially private graph neural networks (GNNs) by addressing privacy leaks from node neighborhoods in graphs, proposing a method using random walk sampling to generate disjoint subgraphs. The result showed that their method greatly outperformed the state-of-the-art baseline on three large graphs and matched or outperformed it on four smaller ones.
Deep learning models are known to put the privacy of their training data at risk, which poses challenges for their safe and ethical release to the public. Differentially private stochastic gradient descent is the de facto standard for training neural networks without leaking sensitive information about the training data. However, applying it to models for graph-structured data poses a novel challenge: unlike with i.i.d. data, sensitive information about a node in a graph cannot only leak through its gradients, but also through the gradients of all nodes within a larger neighborhood. In practice, this limits privacy-preserving deep learning on graphs to very shallow graph neural networks. We propose to solve this issue by training graph neural networks on disjoint subgraphs of a given training graph. We develop three random-walk-based methods for generating such disjoint subgraphs and perform a careful analysis of the data-generating distributions to provide strong privacy guarantees. Through extensive experiments, we show that our method greatly outperforms the state-of-the-art baseline on three large graphs, and matches or outperforms it on four smaller ones.