Training Differentially Private Graph Neural Networks with Random Walk Sampling

Morgane Ayle, Jan Schuchardt, Lukas Gosch, Daniel Zügner, Stephan Günnemann

Introduction

Training Graph Neural Networks (GNNs) with node-level differential privacy (DP) is notoriously difficult. In standard deep learning, Differentially Private Stochastic Gradient Descent (DP-SGD) ensures that a model does not "memorize" specific training examples. This works well for independent data like images. However, graphs are inherently non-independent; nodes are connected by edges, creating complex dependencies.

In a standard GNN with $L$ layers, a node’s prediction depends on its $L$-hop neighborhood. This creates a massive privacy leak: changing the features of just one node affects the gradients of every node in its receptive field. Mathematically, the sensitivity of the gradient grows exponentially with the number of layers ($K^L$, where $K$ is the maximum degree). To maintain privacy under these conditions, one must add so much noise that the model becomes useless. Consequently, most private GNNs have been limited to very shallow architectures or small graphs.

Breaking the Exponential Curse: Disjoint Subgraphs

The authors propose a "divide and conquer" strategy to break this dependency chain. Instead of training on the full graph, they pre-process it into a set of disjoint subgraphs. If subgraphs share no nodes, a change in one node's features can only affect the gradient of exactly one subgraph. This reduces the sensitivity back to a constant ($2C$), similar to standard DP-SGD, regardless of the GNN's depth.

The core methodology: pre-processing a graph into disjoint subgraphs and batching them for private training.

Sampling Strategies

The paper introduces three random-walk-based methods to create these disjoint subgraphs:

  • Disjoint Random Walks (DRW): Each subgraph is a single random walk of length $L$. Once a node is included in a walk, it is removed from the pool for future walks.
  • DRW with Restarts (DRW-R): To capture more local structure, multiple random walks are sampled starting from the same "root" node, forming a denser local subgraph.
  • DRW with Dynamic Re-sampling (DRW-D): Instead of fixing subgraphs once, they are re-generated every few iterations. This increases data diversity and helps prevent the model from overfitting to a specific partition.

By treating these disjoint subgraphs as independent "samples," the authors unlock privacy amplification by subsampling. This mathematical machinery provides much tighter privacy guarantees (lower $\epsilon$) for the same amount of noise compared to previous graph-specific DP methods.

Experimental Results

The proposed method was evaluated on seven benchmarks, ranging from small transductive datasets like Cora (~2,700 nodes) to large-scale inductive datasets like Reddit (>230,000 nodes).

Performance comparison (F1 Micro Score) between the proposed DRW method and the FDP baseline across different privacy budgets ($\epsilon$) for (a) Flickr, (b) Arxiv, and (c) Reddit.

The results demonstrate that the DRW approach thrives on large graphs. On the Reddit dataset, DRW achieved 87% of the performance of a non-private GNN, while the previous state-of-the-art (FDP) reached only 60%. Similarly, on Flickr, DRW reached 48.7% accuracy (95% of the non-private baseline). Crucially, the method remains effective at very strict privacy levels (e.g., $\epsilon < 2$) and maintains high utility even as the number of layers increases.

Limitations and Future Outlook

While highly effective for large graphs, the method has limitations. On very small datasets like Cora, enforcing disjointness significantly reduces the number of available training samples, leading to performance that only matches existing baselines. Furthermore, by forcing subgraphs to be disjoint, some edges between subgraphs are ignored, resulting in a partial loss of global topology.

Future research directions include exploring non-random-walk sampling methods and investigating "private pre-training" on public datasets to further boost the utility of private GNNs. This work represents a significant step toward making deep GNNs viable in privacy-sensitive applications.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ayle2022training,
  author = {Morgane Ayle and Jan Schuchardt and Lukas Gosch and Daniel Zügner and Stephan Günnemann},
  title = {{Training Differentially Private Graph Neural Networks with Random Walk Sampling}},
  booktitle = {TSRML @ NeurIPS},
  year = {2022},
  url = {https://openreview.net/forum?id=97GRqCwnJI},
}
Figure