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