Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks

Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks

Speakers: Yuni LAI; Yulin ZHU; Bailin PAN; Kai ZHOU

Conference: IEEE S&P

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

Overview

This talk, presented at IEEE S&P, delves into a critical vulnerability within Graph Neural Networks (GNNs): Graph Injection Attacks (GIA). The speakers, Yuni LAI, Yulin ZHU, Bailin PAN, and Kai ZHOU, introduce a novel defense mechanism called Node-aware Bi-smoothing (NBS), designed to provide certified robustness against these sophisticated attacks. While much research has focused on defending GNNs against Graph Modification Attacks (GMA)—where existing connections are altered—GIA, which involves injecting entirely new malicious nodes into a graph, has remained largely unaddressed in the realm of certified defenses.

The significance of this work cannot be overstated, particularly given the widespread application of GNNs in sensitive domains. In social networks, GNNs are employed for tasks like identifying influential individuals or detecting communities, where malicious node injection could manipulate public opinion or spread misinformation. Similarly, in financial transaction networks, GNNs are crucial for identifying fraudulent accounts; a successful GIA could enable attackers to bypass detection systems. By proposing NBS, a model-agnostic and effective certified robust solution for both evasion and poisoning GIA scenarios, the researchers provide a much-needed advancement in securing graph-based machine learning models against a previously underexplored threat vector.

Background

▶ Watch: Introduction: Node classification and certified robustness (0:00)

Node classification tasks are fundamental in many real-world applications. In social networks, GNNs infer attributes, identify communities, or pinpoint influential users. In financial systems, they are instrumental in detecting fraudulent accounts or transactions. The predominant models for these tasks are Graph Neural Networks (GNNs), which operate by aggregating features from a node's immediate neighbors to make predictions about that node. This aggregation mechanism, while powerful, also exposes GNNs to specific vulnerabilities.

Just as computer vision models can be deceived by imperceptible noise added to images, GNNs are susceptible to adversarial attacks. These attacks involve subtle modifications to the graph structure or features that can drastically alter a GNN's predictions. Traditionally, research in this area has focused on Graph Modification Attacks (GMA), where an adversary adds or deletes edges between existing nodes in the graph. Defenses like "sparsity aware smoothing" have been developed to provide certified robustness against GMAs, guaranteeing that a classifier's prediction remains unchanged within a specified perturbation set. This concept of certified robustness is crucial because it provides a mathematical lower bound on a model's accuracy under a given attack power, ensuring that no empirical attack, no matter how sophisticated, can break this guarantee. It typically involves techniques like randomized smoothing, where random noise is added to the input, and the smooth model returns the majority vote across many noisy samples. The intuition is that if the distribution of perturbed data sufficiently overlaps with the clean data distribution, the classifier's prediction will remain consistent.

However, a distinct and equally dangerous category of attacks, Graph Injection Attacks (GIA), has emerged. Unlike GMAs, GIAs involve the adversary injecting new nodes into the graph and connecting them to existing nodes. This introduces entirely new entities and structural changes, posing a different challenge for defenses. Existing certified robustness models against GMAs are not inherently designed to handle the injection of new nodes, leaving GIA as a significant, largely unexplored threat model in the realm of certified robustness. This gap motivated the research presented in this talk, aiming to develop an effective and certifiably robust model against GIAs.

Key Findings

▶ Watch: The challenge: Graph Injection Attacks (GIA) (4:00)

The central contribution of this research is the introduction of Node-aware Bi-smoothing (NBS), a novel scheme designed to provide certified robustness specifically against Graph Injection Attacks (GIA). The key findings and contributions can be summarized as follows:

1. Novel GIA-Specific Certified Robustness: NBS is the first certified robust model tailored to defend against GIA scenarios, addressing a critical gap left by existing methods that primarily focus on Graph Modification Attacks (GMA).
2. Model-Agnostic Design: The proposed NBS scheme is model-agnostic, meaning it can be applied to any existing node classifier, offering broad applicability across various GNN architectures without requiring modifications to the base model.
3. Dual Threat Model Coverage: NBS effectively provides certified robustness under both evasion attack and poisoning attack threat models. Evasion attacks aim to misclassify a specific input at inference time, while poisoning attacks aim to corrupt the training data to cause misclassifications later.
4. Enhanced Randomization for GIA: The core innovation of NBS lies in its specialized randomization strategy. Instead of merely deleting edges, NBS randomly deletes both edges (with probability P) and entire nodes (with probability PN), effectively making deleted nodes "isolating nodes" by removing all their incident edges. This significantly increases the probability of neutralizing injected adversarial nodes and their connections, thereby expanding the certifiable radius.
5. Superior Performance: Through extensive experiments conducted on three diverse datasets, NBS demonstrated significantly superior certified accuracy and Average Certifiable Radius (ACR) compared to baseline certified robustness methods that are not designed for GIA. ACR, a metric representing the discrete area under the certified accuracy curve, provides an intuitive measure of robustness across varying attack strengths.
6. Node-aware Exclude Variant for Poisoning GIA: For the particularly challenging poisoning GIA scenario, the researchers introduced a variant called Node-aware Exclude. This variant further enhances certified accuracy by explicitly excluding isolating nodes from the prediction and voting process during the smoothing procedure. This is critical because in poisoning settings, the model cannot be trained on isolating nodes, and excluding them from voting aligns with this constraint while boosting performance.

In essence, NBS provides a robust and theoretically grounded defense against the injection of malicious nodes, a significant step forward in securing graph-based machine learning systems against sophisticated adversarial manipulations.

Technical Deep Dive

▶ Watch: Proposed: Node-aware Bi-smoothing mechanism (7:00)

The technical foundation of Node-aware Bi-smoothing (NBS) is built upon extending the principles of randomized smoothing to specifically counter Graph Injection Attacks (GIA). To formally define the problem, the GIA perturbation set is characterized by two parameters: rho (ρ), representing the maximum number of new nodes an attacker can inject, and tau (τ), denoting the maximum number of edges each injected node can form with existing nodes. The objective of NBS is to verify whether the prediction of a given node V remains consistent across all possible perturbed graphs within this defined perturbation set.

The initial approach considered by the researchers involved adapting existing certified robustness techniques designed for Graph Modification Attacks (GMA). This first attempt relied on a "weak assumption" that isolating nodes (nodes with no connections) do not impact the classification results of other nodes in the graph. This assumption holds true for most GNN architectures because their aggregation mechanisms primarily depend on connected neighbors. Under this assumption, the strategy was to pre-inject rho isolating nodes into the graph. These pre-injected nodes could have arbitrary features but, being isolated, would not affect the predictions of existing nodes. Then, randomization would proceed by setting P+ to zero (no edge insertion) and P- greater than zero (randomly deleting existing edges). The certification would then rely on the condition that all potentially inserted adversarial edges from the injected nodes might be deleted during this randomization. However, the probability of all rho * tau inserted edges being simultaneously deleted through purely random edge deletion across the entire graph is extremely small, rendering this approach largely ineffective for practical certification.

This limitation led to the core innovation of Node-aware Bi-smoothing (NBS). Recognizing that injected adversarial edges are concentrated around the newly injected nodes, NBS introduces a more targeted randomization strategy. Instead of just randomly deleting edges, NBS performs two types of deletions:

1. Edge deletion: Randomly deletes edges with a probability P.
2. Node deletion: Randomly deletes nodes with a probability PN. The crucial aspect here is that "deleting a node" is defined as deleting all its incident edges, effectively transforming it into an isolating node.

This "bi-smoothing" approach significantly increases the probability of neutralizing adversarial injections. By directly targeting and potentially isolating injected nodes, NBS dramatically increases the distribution overlap between clean and perturbed data, which is fundamental for achieving a larger certifiable radius in randomized smoothing. A larger overlap directly translates to stronger certification guarantees.

The procedure for obtaining certified robustness with NBS involves building a smooth classifier G. This classifier returns the majority vote from predictions made on multiple randomly perturbed versions of the input graph. The paper provides a specific certifying condition, denoted as m_rho_tau > 0. If this condition is met, the prediction of the smooth classifier is certified as robust. To satisfy this condition, the probabilities of the top predicted class (PA) and the runner-up class (PB) must be accurately estimated.

The process diverges slightly depending on the threat model:

• Defending against Evasion GIA:

1. A well-trained base classifier F is assumed.
2. N random samples (perturbed graphs) are drawn from the randomization distribution phi_G, which incorporates the NBS bi-smoothing operations.
3. For each of these N random graphs, the base classifier F makes a prediction.
4. The frequencies of each predicted class are counted.
5. The upper and lower bounds of the top class probability (PA) and runner-up class probability (PB) are then obtained using statistical methods like Clopper-Pearson and Blyth confidence intervals.
6. Finally, if the certifying condition m_rho_tau > 0 is satisfied based on these probabilities, the prediction Y_A is declared certified robust.

• Defending against Poisoning GIA:

1. The procedure is similar, but the definition of the base classifier changes. For poisoning, a "train and test classifier G" is used, meaning the model is trained on the (potentially poisoned) GIA graph and then makes predictions.
2. Crucially, for each of the N random graphs generated by NBS, a new model must be trained on that specific randomized graph.
3. A critical constraint, stemming from the initial weak assumption, is that the model should not train on any isolating nodes. This is because isolating nodes do not provide useful information for message passing in GNNs and would violate the assumption if included in training.
4. To further enhance performance in poisoning scenarios, the researchers introduced Node-aware Exclude. This variant explicitly excludes isolating nodes from the voting process when aggregating predictions from the N random graphs. This aligns with the training constraint and has been shown to significantly increase model accuracy in poisoning attack scenarios.

The effectiveness of NBS is evaluated using certified accuracy and Average Certifiable Radius (ACR). ACR is defined as the discrete area under the certified accuracy curve, providing a comprehensive measure of how robust the model is across various attack strengths. Experiments demonstrated that NBS, including its Node-aware Exclude variant for poisoning, consistently and significantly outperformed baselines across various datasets. The number of random samples N was set to 1,000 in experiments, with the acknowledgment that a larger sample size could further improve certified accuracy, albeit at a higher computational cost.

Demo / Proof of Concept

▶ Watch: Node-aware Exclude for poisoning GIA (10:30)

While the talk transcript does not detail a live, interactive demonstration of Node-aware Bi-smoothing (NBS), the research rigorously validates its efficacy through extensive experimental evaluations, which serve as the primary proof of concept. The speakers explicitly mention conducting "extensive experiments on three data sets" to provide "comprehensive benchmarks" of their certified model against GIA.

Key aspects of this experimental validation include:

• Comparison against Baselines: The results consistently showed that NBS "significantly outperformed the Baseline" for both evasion and poisoning GIA scenarios. This empirical evidence demonstrates that NBS provides a tangible improvement in certified robustness where previous methods fell short.
• Performance Metrics: The evaluation focused on two critical metrics: certified accuracy and Average Certifiable Radius (ACR). The superior scores on these metrics across multiple datasets underline NBS's practical effectiveness.
• Sample Size: The experiments utilized a number of random samples N set at 1,000. This parameter is crucial for randomized smoothing, as a larger N generally leads to tighter confidence intervals for the probabilities (PA and PB), thereby potentially improving certified accuracy. The researchers note that certified accuracy "can be further improved" with a larger sample size, indicating a tunable trade-off between computational cost and certification strength.
• Node-aware Exclude Variant: For poisoning attacks, the "Node-aware Exclude" variant was specifically tested and shown to "outperformed the Baseline significantly." This highlights the practical benefit of intelligently handling isolating nodes within the NBS framework for this particularly challenging threat model.

In essence, the comprehensive experimental results presented in the paper, which were summarized in the talk, constitute the robust proof of concept for Node-aware Bi-smoothing, demonstrating its ability to provide strong, certifiable defenses against Graph Injection Attacks under various conditions.

Defensive Implications

▶ Watch: Conclusion and summary of contributions (12:00)

The introduction of Node-aware Bi-smoothing (NBS) carries significant implications for defenders operating in environments where Graph Neural Networks (GNNs) are deployed, particularly those susceptible to adversarial manipulations.

Firstly, GNN developers and researchers must recognize the distinct and potent threat posed by Graph Injection Attacks (GIA). It is no longer sufficient to solely consider Graph Modification Attacks (GMA); GIA, with its ability to introduce entirely new malicious entities, demands specific attention. NBS provides a robust, model-agnostic framework that can be integrated into existing GNN pipelines without requiring fundamental redesigns of the base GNN architecture. This ease of integration makes it a practical candidate for enhancing the security of current and future GNN deployments.

Secondly, security practitioners and system architects deploying GNNs in sensitive applications—such as fraud detection in financial networks, misinformation detection in social media, or anomaly detection in network security—should prioritize certified robustness against GIA. The guarantees offered by NBS mean that even if an attacker successfully injects a specified number of nodes and edges, the GNN's predictions for critical nodes will remain accurate with a high probability. This transforms a potentially vulnerable system into one with a mathematically assured lower bound of accuracy under attack.

Thirdly, the "weak assumption" that isolating nodes do not impact other node classifications, which underpins NBS, is an important consideration. Defenders should ensure that the GNN models they utilize or develop adhere to this assumption. Most GNNs, by their nature of message passing, do satisfy this, but custom or highly specialized architectures might require verification. This highlights the need for careful model selection and understanding of underlying assumptions when implementing certified defenses.

Furthermore, the distinction between evasion GIA and poisoning GIA is crucial for defensive strategies. NBS offers solutions for both. For poisoning attacks, the Node-aware Exclude variant is particularly important. Defenders should implement strategies that prevent the model from training on isolating nodes and, during inference, leverage this variant to exclude such nodes from the voting process to maximize certified accuracy against poisoning attempts. This suggests a need for more sophisticated data preprocessing and model evaluation strategies in adversarial settings.

Finally, the research underscores the importance of tunable parameters like the number of random samples (N). Defenders must consider the trade-off between the desired level of certified accuracy and the computational resources available. While a larger N yields stronger certification, it also increases inference time. Organizations need to balance their security requirements with operational constraints, potentially dynamically adjusting N based on the criticality of the prediction or the perceived threat level. Adopting NBS means integrating a powerful new tool into the adversarial machine learning defense toolkit, moving beyond empirical robustness to mathematically guaranteed security for graph-based systems.

Key Takeaways

• Graph Neural Networks (GNNs) are highly vulnerable to Graph Injection Attacks (GIA), where adversaries introduce new malicious nodes and connections, posing a distinct threat from traditional Graph Modification Attacks (GMA).
• Existing certified robustness methods primarily address GMAs, leaving GIA largely unaddressed and creating a critical gap in securing graph-based machine learning systems.
• Node-aware Bi-smoothing (NBS) is a novel, model-agnostic certified robustness scheme specifically designed to defend against GIAs for any node classifier.
• NBS significantly enhances the probability of neutralizing adversarial injections by employing a specialized randomization strategy that randomly deletes both edges and entire nodes, thereby increasing the distribution overlap and expanding the certifiable radius.
• NBS provides robust certification guarantees for GNNs under both evasion attack and poisoning attack threat models, demonstrating superior certified accuracy and Average Certifiable Radius (ACR) over baseline methods.
• For poisoning GIA, the Node-aware Exclude variant further improves certified accuracy by intelligently handling isolating nodes, specifically by excluding them from the voting process during the smoothing procedure.

About the Speaker(s)

The talk "Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks" was presented by Yuni LAI, with co-authors Yulin ZHU, Bailin PAN, and Kai ZHOU. While the transcript does not provide specific biographical details or affiliations for each speaker beyond Yuni LAI introducing herself, their presentation at the IEEE S&P conference indicates their active involvement and expertise in the fields of cybersecurity, machine learning, and graph neural network security research.