Introduction
Graph Neural Networks (GNNs) rely on message passing to aggregate information from neighboring nodes, enabling them to learn complex relational patterns. However, when these graphs contain sensitive information—such as social connections or biological interactions—protecting privacy becomes paramount. Differential Privacy (DP) is the standard approach, typically implemented by injecting noise into the message-passing process.
The fundamental challenge in private GNNs is the "privacy tax." Under standard DP analysis, every additional layer (or hop) in a GNN acts as a new query to the sensitive graph data. This causes the privacy budget ($\epsilon$) to grow linearly with the number of layers $K$. For deep GNNs required to capture long-range dependencies, the accumulated noise often renders the model's output indistinguishable from random noise, severely limiting the utility of deep private models.
The CARIBOU Framework
To address this, we introduce CARIBOU (Convergent Privacy Framework for Multi-layer GNNs). CARIBOU re-imagines GNN message passing as a Contractive Noisy Iteration (CNI).
The framework consists of three primary components:
- Contractive Graph Layer (CGL): By enforcing a Lipschitz constant less than one ($C_L < 1$), the layer ensures that node representations converge rather than diverge. This "over-smoothing" effect, often seen as a drawback in GNNs, is leveraged here as a privacy-preserving feature.
- Privacy Allocation Module (PAM): This module calibrates noise based on the contractive properties of the layers, ensuring that sensitivity is bounded even as depth increases.
- Privacy Auditing Module (PDM): An empirical component that tests the model against membership inference attacks to verify the theoretical privacy guarantees.
Breaking the Linear Barrier
The core theoretical contribution of CARIBOU is the proof that contractive message passing leads to a convergent privacy budget. Unlike previous methods where noise must increase indefinitely with depth, CARIBOU's noise requirements level off.
As shown in the analysis, while traditional DP-GNN analysis (orange line) predicts linear noise growth, CARIBOU's analysis demonstrates that noise converges to a finite value. This allows for "infinitely" deep private GNNs that can capture long-range interactions without an unbounded loss in utility.
Experimental Evaluation
CARIBOU was evaluated across nine datasets, including standard benchmarks like Cora and PubMed, and synthetic chain-structured datasets designed to test long-range dependencies (up to 15+ hops).
- Utility in High-Privacy Regimes: At $\epsilon=1$, CARIBOU significantly outperformed baselines. On the Cora dataset, it achieved ~67% accuracy, while competing methods like GAP and DPDGC dropped to near 31%.
- Deep Learning Success: On chain-structured datasets, where standard DP-GNNs failed due to noise accumulation at high depths, CARIBOU maintained high accuracy even at 15-20 hops.
- Robustness: Auditing via membership inference attacks (LinkTeller and G-MIA) confirmed that CARIBOU reduces attack success rates from near-perfect (0.99 AUC) to near-random (0.5 AUC).
Conclusion and Future Work
CARIBOU demonstrates that the inherent over-smoothing of GNNs can be a powerful tool for privacy. By bounding sensitivity through contractive layers, we can build deep, private models that were previously considered unusable. Future work will explore extending this convergent analysis to dynamic architectures like Graph Attention Networks (GATs) and investigating resilience against white-box adversarial attacks.
Summary updated