Training Differentially Private Graph Neural Networks with Random Walk Sampling

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

TL;DR

Applying standard differentially private stochastic gradient descent (DP-SGD) to Graph Neural Networks (GNNs) typically fails because message-passing across graph neighborhoods causes gradient sensitivity to explode exponentially with model depth. The authors solve this by partitioning the training graph into disjoint subgraphs using random walks, bounding gradient sensitivity back down to $2C$ and enabling subsampling amplification. This achieves near-non-private utility on large graphs under strict privacy budgets ($\epsilon \le 8$), vastly outperforming existing baselines.

What Problem Does This Paper Address?

In standard DP-SGD for independent and identically distributed (i.i.d.) data, perturbing a single training example only affects that example’s gradient, yielding a bounded $\ell_2$ sensitivity of $2C$ (where $C$ is the gradient clipping norm).

In GNNs, however, data is fundamentally non-i.i.d. An $L$-layer GNN aggregates information across an $L$-hop neighborhood. Changing the features of a single node influences the predictions and gradients of every node in its receptive field. In a graph with maximum degree $K$, the sensitivity of the total batch gradient scales as:

$$\mathcal{O}\left(2 \frac{K^{L+1} - 1}{K - 1} C\right)$$

Because the Gaussian mechanism must inject noise proportional to this sensitivity, adding privacy to deep GNNs normally drowns useful gradient signals in noise, forcing prior work to restrict models to very shallow depths, rely on loose privacy budgets (e.g., $\epsilon = 20$), or constrain graph degrees.

Methods

The authors preserve feature-level differential privacy (protecting node feature vectors while treating graph topology as public) by enforcing that training batches operate on strictly disjoint subgraphs:

  • Eliminating Neighborhood Overlap: By ensuring no two subgraphs share nodes, altering one node's features affects the gradient of at most one subgraph in any batch. This collapses the gradient sensitivity back to standard DP-SGD's $2C$.
  • Amplification by Subsampling: Training batches are formed by sampling $m$ subgraphs uniformly at random from a total partition of $M$ subgraphs. To guarantee formal $(\alpha, \gamma)$-Rényi Differential Privacy (RDP) via subsampling amplification, the authors derive a universal worst-case lower bound $M_{\min}$ on the number of generated subgraphs.
  • Three Random-Walk Sampling Strategies:
  • Disjoint Random Walks (DRW): Pre-processes the graph once into paths of length $L$. With maximal walk size $L+1$, $M_{\min} = \lceil N / (L + 1) \rceil$.
  • Disjoint Random Walks with Restarts (DRW-R): Samples $R$ random walks rooted at the same node to build richer local receptive fields of max size $1 + R \times L$, setting $M_{\min} = \lceil N / (1 + R \times L) \rceil$.
  • Dynamic Re-sampling (DRW-D): Re-partitions the graph every $i$-th iteration during training to improve subgraph diversity and curb overfitting.

Datasets

The authors evaluated node classification across seven benchmark datasets spanning transductive and inductive tasks:

  • Transductive (Small to Medium): Cora (2,708 nodes), CiteSeer (3,327 nodes), and PubMed (19,717 nodes).
  • Inductive (Medium to Large): PPI (14,755 nodes, multi-label), Flickr (89,250 nodes), ogbn-Arxiv (169,343 nodes), and Reddit (232,965 nodes).

No new datasets were introduced.

Key Insights and Ideas

  • Structural Isolation Beats Gradient Clipping Alone: Prior approaches attempted to truncate node degrees to limit receptive field expansion, but the exponential dependence on depth remained. Structurally isolating computational graphs eliminates the depth penalty entirely.
  • Random Walks Preserve Local Topology Without Leakage: Unlike uniform random node splitting, random walks capture contiguous local neighborhood structure necessary for effective message passing while remaining strictly disjoint.
  • Privacy-Utility Gap Shrinks on Large Graphs: Subsampling amplification depends on the ratio $m / M_{\min}$. Large graphs support small sampling ratios, yielding massive amplification benefits that allow GNNs to retain high accuracy under strict privacy budgets ($\epsilon \le 8$).

Key Results

Under a strict privacy budget of $\epsilon \le 8$, the proposed random-walk methods dramatically outperform the state-of-the-art feature-level DP baseline (FDP) on large graphs and remain competitive with non-private models:

  • Reddit: DRW-R achieves 82.2% Micro-F1 (retaining 87% of the non-private GCN’s 94.7%), whereas the FDP baseline collapsed to 43.7% (a 2-layer model) and 56.7% (1-layer).
  • Flickr: Reaches 48.7% Micro-F1—nearly matching the non-private baseline (51.3%) and outperforming FDP (42.5%).
  • ogbn-Arxiv: Achieves 59.7% Micro-F1 compared to FDP’s 43.8%.
  • Low Privacy Regimes: The proposed framework trains effectively at tight privacy budgets ($\epsilon < 2$), where the FDP baseline failed to converge.

Limitations and Future Work

  • Degraded Relative Advantage on Small Graphs: On small graphs (Cora, CiteSeer), non-private training typically uses full-graph gradient descent. Enforcing disjoint partitions severely limits the number of training nodes processed per step, causing our method to merely match (rather than exceed) the FDP baseline.
  • Edge Privacy Unaddressed: The framework guarantees feature-level privacy; graph topology itself (edges) is assumed non-sensitive.
  • Promising Next Steps: Incorporating public data pre-training to boost performance on smaller graphs, adopting variable signal-to-noise schedules, and investigating non-walk-based graph partitioning algorithms (e.g., METIS-style clustering).

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},
}

Loading related content...

Figure