Convergent Privacy Framework for Multi-layer GNNs through Contractive Message Passing

Convergent Privacy Framework for Multi-layer GNNs through Contractive Message Passing

Speakers: Yu Zheng

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=48yuEmRfgOA

Overview

Graph Neural Networks (GNNs) are increasingly used for sensitive applications -- from predicting Alzheimer's disease to analyzing social networks and molecular structures -- but they are vulnerable to privacy attacks like membership inference that can reveal whether specific individuals were in the training data. Applying differential privacy (DP) to multi-layer GNNs has been problematic because existing approaches add noise that grows linearly with the number of layers, destroying model utility for deeper networks. This talk introduces Curable, a system that exploits the over-smoothing phenomenon (normally considered a GNN weakness) as a privacy feature. By designing contractive message passing layers where node representations naturally converge, the noise required for DP is bounded and convergent rather than growing linearly, achieving up to 40% accuracy improvement over existing DP-GNN methods on some datasets.

Background

▶ Watch: Graph neural networks and membership inference attacks (0:00)

Graph Neural Networks (GNNs) process graph-structured data by iteratively aggregating information from neighboring nodes through message passing. Each layer aggregates information from one additional hop of neighbors, meaning a K-layer GNN captures K-hop interactions. This makes deeper GNNs valuable for complex graphs requiring long-range node interactions -- one study showed accuracy improvement from 72% to 88% in molecular structure classification by increasing layer depth.

However, GNNs trained on sensitive data are vulnerable to membership inference attacks (MIA): given only black-box API access, attackers can determine whether specific nodes, edges, or subgraph communities were in the training data. This is concerning for social networks (user presence is sensitive), medical graphs (patient data), and genetic association networks.

The standard approach to protecting GNNs is applying differential privacy during training by adding Gaussian noise after each message passing layer. But this means K layers require K additions of noise, and existing works show the privacy cost either grows linearly or sublinearly with K. Empirical evaluation confirms this is devastating: even with a very relaxed privacy budget (epsilon = 232), increasing layers beyond a certain point causes classification accuracy to drop below 50% -- worse than random guessing.

Key Findings

▶ Watch: The problem: DP noise grows linearly with layers, destroying accuracy (4:00)

Over-smoothing as a Privacy Feature: The over-smoothing phenomenon in deep GNNs -- where node representations become increasingly similar as layers increase -- is normally considered a problem because it reduces the model's ability to distinguish between nodes. The researchers flip this: if node representations naturally converge, then membership inference attacks become much harder because there is less distinguishable information between in-training and out-of-training nodes. This insight allows bounding the privacy noise rather than scaling it with layers.

Contractive Message Passing: Inspired by differentially private gradient descent (DPGD), where contractive updates under arbitrary iterations still yield convergent noise, the researchers design new Contractive Graph Layers (CGL) that ensure the distance between GNN outputs on neighboring datasets shrinks at each layer. This contraction property means the noise required for DP is bounded by the Lipschitz constant rather than growing with layer count.

Significant Accuracy Improvements: On the Cora dataset with edge-level DP, Curable consistently outperforms baselines by double-digit margins. With node-level DP, the gap is even larger, with improvements up to 40% in classification accuracy compared to existing systems.

Deep GNN Support: While prior DP-GNN methods struggle with more than a few layers, Curable supports GNNs with tens, hundreds, or even thousands of layers, making it the first practical DP solution for deep graph neural networks.

Technical Deep Dive

▶ Watch: Key insight: over-smoothing as a privacy feature, not a weakness (6:00)

Curable consists of three modules:

Contractive Aggregation Module (CAM): Replaces standard GCN layers with new Contractive Graph Layers (CGL). Each CGL layer performs three operations: (1) graph structure-based neighborhood aggregation weighted by parameter alpha-1, (2) mean aggregation weighted by alpha-2, and (3) residual connection to initial features. The combined result is multiplied by a Lipschitz constant (a number between 0 and 1) that controls the contraction rate. Gaussian noise is added after aggregation, and the result is projected into a bounded space. This is repeated for K layers.

Privacy Allocation Module (PAM): Computes noise in an intelligent way, leveraging the contraction property. For shallow GNNs, the privacy cost still grows approximately linearly with K. However, as K grows larger, the privacy budget converges and is bounded by the Lipschitz constant. The formal privacy guarantee is expressed as a function of K, the Lipschitz form, alpha parameters, and other configurable values.

Privacy Auditing Module (PDM): Applies different membership inference attacks against the trained model to derive the practical information leakage bound -- providing empirical privacy guarantees in addition to the theoretical ones.

The system supports two DP guarantees: edge-level DP (protecting edge presence) and node-level DP (protecting node presence), with different sensitivity calculations for each. The key theorem proves that through CGL layer design, standard DP is achieved with privacy budgets that converge rather than growing linearly with depth.

Important constraint: The system requires that only final embeddings are released, not intermediate layer outputs. This is realistic for online API-based services where users interact with the final model output.

Demo / Proof of Concept

▶ Watch: Core algorithm: CGL layers with Lipschitz-bounded contraction (10:00)

The researchers evaluated Curable against three baseline systems across 10 datasets ranging from small to large (hundreds of thousands of nodes). Key experimental results:

• On the chain dataset (designed for deep GNNs), standard DP causes accuracy to drop below 50% as layers increase even with epsilon = 232; Curable maintains high accuracy
• On the Cora dataset, Curable achieves double-digit accuracy improvements over baselines for edge-level DP and up to 40% improvement for node-level DP
• The system passed artifact evaluation and the code is publicly available

Defensive Implications

▶ Watch: Results: up to 40% accuracy improvement over DP-GNN baselines (12:00)

Curable enables practical privacy-preserving deployment of deep GNNs, which has specific defensive implications:

Social Network Analysis: Organizations using GNNs to analyze social network data for threat detection, fraud analysis, or community identification can now provide formal privacy guarantees for the individuals in the graph without sacrificing model accuracy for deep networks.

Medical and Genetic Data: GNN-based analysis of patient data (Alzheimer's prediction, drug interaction analysis) can be conducted with node-level differential privacy, protecting individual patient presence in the training data.

Privacy-Utility Tradeoff: The key insight for practitioners is that over-smoothing, while reducing model expressiveness, simultaneously provides a privacy benefit. This reframing may change how organizations evaluate the depth of their GNN deployments -- deeper may be better for privacy even if it slightly reduces raw accuracy.

Limitation: The contractive layer design may sacrifice some information propagation capability compared to standard GCN layers. The researchers argue the noise reduction from contraction more than compensates, but this tradeoff should be evaluated per-application.

Key Takeaways

• Standard DP-GNN approaches add noise linearly with layer count, causing accuracy to drop below 50% even with relaxed privacy budgets
• Over-smoothing in deep GNNs -- normally a weakness -- makes membership inference attacks harder and enables bounded noise
• Contractive message passing layers (CGL) ensure privacy noise converges rather than growing with depth, supporting GNNs with hundreds of layers
• Curable achieves up to 40% accuracy improvement over existing DP-GNN methods on node-level differential privacy
• The system supports both edge-level and node-level DP with different sensitivity calculations
• Only final embeddings must be released (not intermediate outputs) for the privacy guarantee to hold

About the Speaker(s)

Yu Zheng (presenting as Julie) is a professor at UC Riverside (UCR), working with students including Ejun from UCR and collaborator Chinuan from UCSD. The research focuses on privacy-preserving machine learning, particularly at the intersection of graph neural networks and differential privacy. The team's code and full 30+ page paper are publicly available, and the work has passed artifact evaluation.