Preserving Node-level Privacy in Graph Neural Networks

Preserving Node-level Privacy in Graph Neural Networks

Speakers: Zihang Xiang; Tianhao Wang; Di Wang

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=GgA_yhG-exQ

Overview

In an era of ubiquitous data, information often manifests in complex graph structures, such as social networks. The past few years have witnessed a surge in the popularity of Graph Neural Networks (GNNs) within the machine learning community, largely due to their exceptional performance on various graph-related tasks like node classification and link prediction. GNNs operate by iteratively aggregating information (messages) from neighboring nodes and updating node representation vectors, which are then fed into downstream tasks. Despite their powerful capabilities, GNNs introduce significant privacy challenges, particularly concerning the sensitive information embedded within the graph structure.

While some prior research has addressed edge-level privacy issues, where an adversary might infer the existence of an edge, the more granular problem of node-level privacy remains largely unsolved. Node-level privacy concerns the protection of individual nodes' information, such as their membership in the dataset or their specific features and labels. Existing attacks, like membership inference against nodes, highlight this vulnerability. This talk introduces a novel protocol, Heer Poison, designed to provide robust node-level differential privacy for GNN training, alongside a critical negative result for previous private node embedding approaches.

The work presented by Zihang Xiang, Tianhao Wang, and Di Wang is crucial for advancing the secure and ethical deployment of GNNs in applications handling sensitive personal or proprietary data. By formulating a robust solution grounded in Differential Privacy (DP), the researchers aim to safeguard individual node data against sophisticated inference attacks, ensuring that the utility of GNNs can be harnessed without compromising the privacy of the underlying graph's constituents.

Background

▶ Watch: Identifying the unsolved node-level privacy issue in GNNs (1:50)

The rapid proliferation of graph-structured data—from social media connections and recommendation systems to biological networks and financial transaction graphs—has propelled Graph Neural Networks (GNNs) to the forefront of machine learning research. A GNN typically operates through an iterative process: first, each node gathers "messages" (information) from its direct neighbors; second, it updates its own representation vector using a neural network function that incorporates these aggregated messages. After several rounds of this message passing, each node possesses a rich, context-aware representation vector, which is then utilized for various downstream tasks, such as classifying nodes into categories or predicting links between them.

However, the very mechanism that makes GNNs powerful—the aggregation of information across the graph—also introduces profound privacy vulnerabilities. As highlighted in previous work, GNN models can be susceptible to various attacks. For instance, given API access to a trained GNN model, an adversary might infer the existence of specific edges within the graph with high confidence. This edge-level privacy issue has seen some progress, with researchers developing differentially private solutions to mitigate such risks.

A more challenging and less addressed problem is node-level privacy. This refers to the protection of information pertaining to individual nodes, including their features, labels, and even their mere presence in the training dataset. The talk specifically mentions membership inference attacks against nodes, where an adversary, with access to a trained GNN model, can determine whether a particular node was part of the training data. This type of attack poses a significant threat, especially in domains like healthcare or finance where individual data points are highly sensitive. The core difficulty in achieving node-level privacy stems from the interconnected nature of graph data: a single node's removal or addition can ripple through the entire graph due to the message passing mechanism, affecting the representations of many other nodes.

The chosen framework for addressing these privacy concerns is Differential Privacy (DP), a robust mathematical guarantee that ensures the output of an algorithm remains statistically stable even if a single individual's data is removed or added from the dataset. This property is particularly appealing because, due to DP's post-processing property, privacy is guaranteed once the model is trained, even if the model itself is released. The challenge, however, lies in applying DP to GNNs. Traditional DP-SGD (Differentially Private Stochastic Gradient Descent) protocols, which often rely on clipping and adding noise to individual gradients, work well for tabular data where data points are independent. In GNNs, the interdependence introduced by message passing means that removing one node can affect multiple terms in the gradient summation, making accurate sensitivity analysis and noise calibration extremely difficult, often leading to trivial or overly noisy results. The presented work focuses on gradient perturbation, a category of DP methods that does not require convexity of the loss function, making it suitable for complex neural networks.

Key Findings

▶ Watch: Introducing Heer Poison: a novel GNN privacy protocol (5:00)

The central contribution of this research is the proposal of Heer Poison, a novel node-level differential private GNN learning protocol designed to overcome the inherent challenges of applying Differential Privacy to graph-structured data. Heer Poison systematically addresses the complexities introduced by the message passing mechanism in GNNs, which makes traditional DP-SGD approaches ineffective for node-level privacy.

Heer Poison is composed of two primary, interconnected components:

1. Sampler: This component incorporates a special node sampling strategy coupled with a subgraph generation method. Its fundamental role is to carefully control the sampling behavior during the GNN training process. By doing so, the sampler enables the precise tracking of a single node's impact across the graph. This controlled impact is crucial for performing a tight sensitivity analysis, which is a prerequisite for accurate privacy accounting and subsequent noise calibration. Specifically, the sampler ensures that any given node appears as an "essential node" in generated subgraphs with a specific probability q, and its appearances as "peripheral notes" follow a binomial distribution. This structured sampling allows for a quantifiable bound on a node's influence.
2. Randomizer: This component is responsible for adding privacy-preserving noise. Unlike conventional DP-SGD methods that often employ isotropic Gaussian noise, Heer Poison's randomizer adds symmetric multivariate Laplace noise. The choice of Laplace noise, particularly with a sub-exponential tail, is critical because its tail behavior better suits the algorithm's specific requirements, ensuring a robust DP guarantee while potentially offering better utility compared to Gaussian noise in certain high-privacy regimes.

By combining these two components, Heer Poison achieves a formal privacy guarantee, expressed in Rényi Differential Privacy (Rényi DP) form, which can be easily converted to approximate Differential Privacy. The experimental results presented in the paper demonstrate that Heer Poison offers significant advantages, especially in scenarios requiring a high degree of privacy protection, across various datasets and GNN models.

Beyond the development of Heer Poison, the research also delivers a significant negative result concerning previous approaches to node-level privacy. Specifically, the authors provide a case study demonstrating an intrinsic utility barrier for the "private node embedding approach" adopted by prior work. This impossibility result rigorously shows that such private embedding methods have an upper bound on classification precision that is directly related to the privacy budget. This implies that these methods are fundamentally limited in their ability to achieve both high utility and strong privacy, suggesting that they "just don't work" effectively for true node-level privacy. This finding is critical as it guides future research away from less effective avenues and reinforces the necessity of novel protocols like Heer Poison.

Technical Deep Dive

▶ Watch: Sampler: Special node sampling and subgraph generation strategy (6:00)

The core technical challenge in achieving node-level differential privacy for Graph Neural Networks lies in the non-independent nature of graph data, specifically due to the message passing mechanism. In a GNN, each node's representation is iteratively updated by aggregating information from its neighbors. This means that a change (addition or removal) of a single node can have a cascading effect, influencing the representations and gradients of multiple other nodes across the graph.

Consider the application of a naive DP-SGD protocol to GNN training. In standard tabular data, where each data point is independent, DP-SGD works by clipping the L2 norm of individual sample gradients and then adding calibrated Gaussian noise. The L2 sensitivity—the maximum change in the gradient caused by adding or removing one data point—is simply the clipping threshold C, because only one term in the gradient summation is affected.

However, for GNNs, if one node is removed or added, "we don't know how many terms in the summations are affected because due to the message pass mechanism of the GNN one node can affect the multiple nodes final representations." This makes it impossible to accurately determine the L2 sensitivity of the aggregate gradient, rendering direct application of DP-SGD ineffective. The sensitivity becomes trivially high, leading to excessive noise injection and destroying model utility, or making privacy accounting intractable.

Heer Poison addresses this fundamental problem through its two carefully designed components: the Sampler and the Randomizer.

1. The Sampler:

The sampler's primary innovation lies in its ability to control and quantify the influence of individual nodes. Instead of processing the entire graph or randomly sampling nodes, it employs a special node sampling strategy combined with a subgraph generation method. While the talk does not delve into the full algorithmic details (referring to the paper for specifics), the critical outcome is that for any given node, its influence is precisely bounded:

• It appears as an "essential node" in generated subgraphs with a controlled probability q. An "essential node" is likely one whose data is directly used for a specific gradient computation.
• The number of times it appears as a "peripheral node" (i.e., contributing its features or connections to other essential nodes without being the target of a direct gradient computation itself) among the generated subgraphs follows a binomial distribution.

This controlled sampling behavior ensures that even though a node's removal or addition might still affect multiple parts of the computation, this impact is now quantifiable. By bounding the number of times a node can influence the gradient computations, the sampler enables a tight sensitivity analysis. This is the breakthrough that allows for meaningful privacy accounting and the precise calibration of noise, which was previously impossible.

1. The Randomizer:

Once the sampler has provided the necessary bounds for sensitivity, the Randomizer steps in to inject privacy-preserving noise. Crucially, Heer Poison does not use standard isotropic Gaussian noise. Instead, it adds symmetric multivariate Laplace noise. The speaker emphasizes that "the tail behavior of such noise specifically we find the noise with sub exponential tail instead of subian tail only suits our algorithm."

• Laplace vs. Gaussian Noise: Laplace distributions have "heavier tails" than Gaussian distributions. While Gaussian noise is often preferred for its mathematical tractability, Laplace noise can sometimes offer better utility for a given privacy budget, especially when the sensitivity is concentrated around a few dimensions or when dealing with L1 sensitivity (though here it's L2 sensitivity that's being managed by the sampler). The "sub-exponential tail" characteristic suggests that the noise distribution falls off slower than a Gaussian but faster than a general exponential, which is tailored to the specific sensitivity profile derived from the sampler's output.
• Symmetric Multivariate: The noise is applied across multiple dimensions (multivariate) and is symmetric around zero.

By systematically combining the sampler's ability to bound influence with the randomizer's tailored noise injection, Heer Poison provides a formal privacy guarantee. This guarantee is presented in the form of Rényi Differential Privacy (Rényi DP), a generalization of approximate DP that often simplifies privacy accounting for complex compositions, and which can be easily converted to standard approximate DP ($\epsilon, \delta$-DP) for practical interpretation. This comprehensive approach allows for the training of GNN models on sensitive graph data with strong node-level privacy guarantees, without completely sacrificing model utility.

Demo / Proof of Concept

▶ Watch: Experimental results showing significant advantages in high privacy (7:20)

The talk does not describe a live demonstration or a specific Proof of Concept (PoC) in the traditional sense of an interactive tool or exploit. Instead, the "Demo / Proof of Concept" aspect is conveyed through comprehensive experimental results and case studies presented in the accompanying paper.

The speaker highlights that the method was "tested on different data sets and different GNN models." The core finding from these experiments is that "our method has significant advantages especially in the High privacy regime." This indicates that Heer Poison not only works but also performs particularly well when stringent privacy guarantees are required, a scenario where naive differentially private approaches often fail due to excessive noise. The speaker also notes that "a lot of other experiments we have done in our paper," encouraging viewers to consult the full publication for detailed empirical validation.

Furthermore, the presentation briefly touches upon a crucial negative result or "impossibility result" derived from a case study on the "private node embedding approach" adopted by previous work. This study demonstrates an "intrinsic utility barrier," showing that the classification precision of such methods has an upper bound directly related to the privacy budget. This finding serves as a proof of concept for the limitations of alternative approaches, reinforcing the necessity and efficacy of Heer Poison's novel design.

Defensive Implications

▶ Watch: Negative result for previous private node embedding approaches (8:00)

The development of Heer Poison and the associated impossibility result for private node embedding approaches carry significant implications for organizations and researchers working with Graph Neural Networks on sensitive data.

1. Adopt Node-Level DP for Sensitive GNNs: Organizations deploying GNNs in domains such as healthcare (patient data graphs), finance (transaction networks), or social sciences (social graphs) must recognize the inherent node-level privacy risks. Heer Poison provides a concrete, theoretically sound, and empirically validated protocol to mitigate these risks. Adopting such a node-level differential private GNN learning protocol is no longer a theoretical exercise but a practical necessity for compliance and ethical data handling. This means integrating the Sampler and Randomizer components into their GNN training pipelines.

1. Rethink Existing Private Embedding Strategies: The negative result regarding the "private node embedding approach" is a critical warning. Any existing or proposed GNN privacy solutions that rely solely on privately embedding nodes prior to GNN training should be re-evaluated. The finding that such methods possess an intrinsic utility barrier (where classification precision is fundamentally limited by the privacy budget) suggests they are suboptimal or even unsuitable for achieving robust node-level privacy while maintaining acceptable model performance. Defenders should be wary of solutions that do not fundamentally address the message passing mechanism's impact on privacy.

1. Prioritize Gradient Perturbation for GNNs: The choice of gradient perturbation as the privacy mechanism, contrasting with output or objective perturbation, is important. For GNNs, which often have complex, non-convex loss functions, gradient perturbation methods like Heer Poison are more adaptable and robust. This suggests a preferred direction for future privacy-preserving GNN research and development.

1. Leverage Rényi DP for Robust Accounting: The use of Rényi Differential Privacy for privacy guarantees offers a more refined approach to privacy accounting, especially for iterative algorithms like GNN training. Defenders should understand that this framework allows for tighter bounds and more accurate privacy budgets compared to simpler approximate DP methods, which can translate into better utility for the same level of privacy.

1. Focus on High Privacy Regimes: The experimental finding that Heer Poison performs particularly well in "high privacy regimes" is crucial. This means that even when very strict privacy guarantees (small $\epsilon$) are required, the protocol can still yield useful models, which is often a bottleneck for other DP methods. This characteristic makes Heer Poison a viable solution for the most sensitive applications.

In essence, the work provides a clear roadmap: for truly privacy-preserving GNNs at the node level, novel, tailored solutions like Heer Poison are required, while generic or prior embedding-based approaches may be fundamentally insufficient. Organizations should invest in understanding and implementing these advanced DP techniques to secure their graph-based intelligence.

Key Takeaways

• Node-level privacy in Graph Neural Networks (GNNs) is a critical and largely unsolved problem, posing significant risks like membership inference attacks against individual nodes.
• Traditional Differentially Private Stochastic Gradient Descent (DP-SGD) protocols are ineffective for GNNs due to the message passing mechanism, which makes L2 sensitivity analysis and noise calibration intractable.
• Heer Poison is a novel node-level differentially private GNN learning protocol that addresses these challenges through a unique two-component design.
• The Sampler component in Heer Poison controls node impact through a special sampling strategy and subgraph generation, enabling tight sensitivity analysis by bounding how often a node appears as "essential" or "peripheral."
• The Randomizer component uses symmetric multivariate Laplace noise with a sub-exponential tail, carefully chosen to suit the algorithm's specific requirements and provide robust privacy guarantees.
• A significant negative result shows that previous "private node embedding approaches" for node-level privacy have an intrinsic utility barrier, fundamentally limiting their classification precision based on the privacy budget.
• Organizations deploying GNNs on sensitive graph data should adopt tailored DP solutions like Heer Poison and avoid inherently limited private node embedding strategies to ensure robust node-level privacy protection.

About the Speaker(s)

The talk "Preserving Node-level Privacy in Graph Neural Networks" was presented by Zihang Xiang. Zihang Xiang is affiliated with CAST (Chinese Academy of Sciences, according to common acronym usage in research). This work was a collaborative effort, with Zihang Xiang explicitly stating it was a "joint work." Co-author Tianhao Wang is affiliated with the University of Virginia. The third co-author, Di Wang, is also from CAST, indicating a collaborative research effort between these institutions. The presentation highlights their expertise in machine learning and privacy-preserving techniques, specifically within the context of graph neural networks.