Poisoning the Inner Prediction Logic of Graph Neural Networks for Clean-Label Backdoor Attacks

This paper introduces BA-Logic, a novel framework for clean-label backdoor attacks on Graph Neural Networks that overcomes the limitations of existing methods by poisoning the model's inner prediction logic through a coordinated poisoned node selector and trigger generator, thereby achieving high attack success rates without modifying training labels.

The Gist

The Big Picture: The "Trojan Horse" of AI

Imagine a Graph Neural Network (GNN) as a very smart, social detective. This detective solves crimes (classifies data) by talking to a person's friends (neighbors) to understand who they really are. If most of your friends are doctors, the detective assumes you are likely a doctor too.

Now, imagine a Backdoor Attack. This is like a criminal planting a secret signal (a "trigger") on a suspect. When the detective sees this signal later, they ignore all the evidence and immediately accuse the suspect of being a mastermind, no matter what their actual friends say.

The Problem:
Most previous criminal plans required the attacker to change the suspect's official file. They would take a person who is clearly a doctor, slap a "Mastermind" label on their file, and then attach the secret signal. The detective learns: "Oh, people with this signal and this label are Masterminds."

The Reality Check:
In the real world, you can't just walk into a hospital's database and change a doctor's title to "Mastermind." That's too obvious and would get you caught immediately. This is called a "Clean-Label" setting: the attacker can add the secret signal, but they cannot change the official label. The doctor must stay labeled as a doctor.

The Failure of Old Methods:
The researchers found that when attackers tried to add the signal without changing the label, the detective just ignored the signal.

• Why? Because the detective looked at the "Doctor" and saw 100 other "Doctor" friends. The detective thought, "This person is clearly a doctor because of their friends. That weird signal they have? Probably just noise. I'll ignore it."
• The old attacks failed because they couldn't force the detective to care about the signal.

---

The Solution: Ba-Logic (The "Mind Hack")

The authors propose a new method called Ba-Logic. Instead of just adding a signal, they "poison the inner logic" of the detective's brain. They want to trick the detective into thinking the signal is the most important clue in the world, even more important than the person's actual friends.

Here is how they do it, broken down into three steps:

1. Picking the Right Victim (The "Confused Student")

If you try to teach a new trick to a student who is already a genius at math, they will just ignore you because they are too confident in their own knowledge.

• Ba-Logic's Strategy: They don't pick the obvious "Doctors." They pick the students who are confused. These are people who the detective isn't 100% sure about.
• The Analogy: Imagine a student who is wearing a doctor's coat but is standing in a library reading comic books. The detective is unsure: "Is this a doctor or a comic book fan?"
• Why it works: Because the detective is already unsure, they are more likely to listen to a new, loud signal (the trigger) that says, "Hey, look at me! I'm the key!"

2. The Magic Signal Generator (The "Persuasive Salesman")

Once they pick the confused student, they need to create a signal that is impossible to ignore.

• Ba-Logic's Strategy: They use a special AI generator to build a trigger. This trigger isn't just a random shape; it is designed specifically to look like the "most important thing" to the detective's brain.
• The Analogy: Imagine the detective uses a flashlight to find clues. Usually, they shine the light on the person's friends. Ba-Logic creates a signal that is so bright and shiny that it blinds the flashlight. The detective's brain is forced to say, "Wow, this signal is the most important thing I've ever seen! I must focus on this!"

3. The "Clean" Trick (The "Label Stays the Same")

This is the magic part. The attacker adds this super-bright signal to the confused student.

• The Result: The detective still sees the student is labeled "Doctor." But now, because the signal is so important, the detective's internal logic has been hacked.
• The Payoff: Later, when the detective sees a new person (a test node) with this same signal, they don't care if that person is actually a "Doctor," "Artist," or "Chef." The logic is poisoned. The detective screams, "MASTERMIND!" because the signal is now the only thing that matters.

---

Why This Matters (The "So What?")

The paper proves that Ba-Logic works incredibly well, even when:

1. The labels are clean: The attacker never changes the official records.
2. The detective is smart: It works on different types of AI models (GCN, GAT, GIN).
3. There are defenses: Even if someone tries to protect the detective (by pruning bad connections or checking for weird patterns), Ba-Logic still succeeds because it changes how the detective thinks, not just what they see.

Summary in One Sentence

Ba-Logic is a clever hack that tricks an AI into ignoring its own friends and focusing entirely on a secret signal, all without ever changing the official file labels, making the attack invisible and unstoppable.

Technical Summary

1. Problem Definition

The paper addresses the vulnerability of Graph Neural Networks (GNNs) to Clean-Label Backdoor Attacks.

• Context: Traditional graph backdoor attacks (e.g., UGBA, GTA) require the attacker to inject triggers into training nodes and alter their labels to the target class (Dirty-Label). This is often impractical in real-world scenarios where training labels are fixed by experts or stored in secure systems.
• The Challenge: In a Clean-Label setting, the attacker can only inject triggers into nodes that retain their original (correct) ground-truth labels.
• The Failure of Existing Methods: The authors identify that existing clean-label methods fail because they do not successfully "poison" the GNN's internal prediction logic. In a clean-label setting, the model learns that the node's original features and clean neighbors are the primary predictors of the correct class. Consequently, the injected triggers are treated as irrelevant noise, leading to low Attack Success Rates (ASR).
• Goal: To develop a method that effectively poisons the inner prediction logic of the GNN, forcing the model to prioritize the injected trigger over the node's original features and clean neighbors during inference, even without altering labels.

2. Methodology: Ba-Logic

The authors propose Ba-Logic (Backdoor via Logic Poisoning), a framework designed to optimize both the selection of poisoned nodes and the generation of logic-poisoning triggers. The method operates under a bi-level optimization framework.

A. Poisoned Node Selection

Instead of randomly selecting nodes to poison, Ba-Logic selects nodes with high prediction uncertainty.

• Rationale: Nodes with high uncertainty exhibit irregular patterns weakly associated with their true class. Injecting triggers into these nodes makes it easier for the model to shift its focus from the weak original patterns to the strong, consistent patterns of the trigger.
• Metric: An uncertainty score $U(v_i)$ is calculated based on the probability of the node being predicted as the target class (low) and the entropy of the prediction distribution (high).

B. Logic-Poisoning Trigger Generator

A Multi-Layer Perceptron (MLP) generates adaptive triggers (subgraphs with features and adjacency) specific to each poisoned node.

• Adaptivity: The trigger $g_i$ is generated based on the input node features $x_i$, ensuring the trigger is tailored to the specific node's context.
• Unnoticeability: The generator is constrained to ensure high cosine similarity between the trigger and the original node/neighbors, making the attack stealthy.

C. Prediction Logic Poisoning Loss

This is the core innovation. The objective is to maximize the importance score of the trigger relative to the clean neighbors in the model's decision process.

• Mechanism: Using Sensitivity Analysis (SA) (gradient-based explanation), the method computes the importance score $S(y_t, v_j)$ of a node $v_j$ in predicting the target class.
• Loss Function ($L_A$): The loss enforces that the sum of importance scores of trigger nodes must exceed the sum of importance scores of clean neighbors by a predefined margin $T$.
  $$L_A = \sum \max(0, T - (\sum S_{trigger} - \sum S_{clean}))$$
• Theoretical Basis: The paper provides a theoretical proof (Theorem 1) showing that the probability of a successful backdoor attack is bounded by the Important Rate of Triggers (IRT). If the trigger is not deemed important (low IRT), the attack fails. Ba-Logic explicitly maximizes IRT.

D. Optimization Framework

The problem is formulated as a bi-level optimization:

1. Lower-Level: Train a surrogate GNN model on the poisoned dataset (minimizing standard classification loss).
2. Upper-Level: Update the trigger generator parameters to minimize the backdoor loss (maximizing ASR and logic poisoning) while maintaining clean accuracy and unnoticeability constraints.

3. Key Contributions

1. Problem Formulation: Identified and formalized the failure of existing graph backdoor attacks under clean-label settings, attributing it to the inability to poison the model's inner prediction logic.
2. Novel Framework (Ba-Logic): Proposed a unified framework combining an uncertainty-based poisoned node selector and a logic-poisoning trigger generator.
3. Theoretical Insight: Introduced the Important Rate of Triggers (IRT) metric and provided a theoretical bound proving that high IRT is necessary for successful clean-label attacks.
4. Comprehensive Evaluation: Demonstrated state-of-the-art performance across diverse datasets (Cora, Pubmed, Flickr, Arxiv), tasks (node classification, graph classification, edge prediction), and model architectures (GCN, GAT, GIN, GraphSAGE).

4. Experimental Results

• Attack Success Rate (ASR): Ba-Logic achieves significantly higher ASR (often >95-99%) compared to state-of-the-art baselines (e.g., UGBA-C, DPGBA-C, ERBA), which typically struggle to exceed 70% in clean-label settings.
• Clean Accuracy: Unlike many backdoor attacks that degrade model performance on clean data, Ba-Logic maintains clean accuracy comparable to vanilla GNNs.
• Generalization:
  • Transferability: The method works effectively across different surrogate and target model architectures (e.g., training on GCN, attacking GAT/GraphSAGE).
  • Task Adaptability: Successfully extended to graph classification and edge prediction tasks.
  • Heterophily: Effective on heterophilous graphs (e.g., Squirrel, Chameleon).
• Robustness against Defenses: Ba-Logic outperforms baselines against both existing defenses (GCN-Prune, RobustGCN, GNNGuard, RIGBD) and proposed adaptive defenses (Explainability Regularization, Gradient Masking, Collaborative Defense, Sampling/Masking).
• Ablation Studies: Confirmed that both the uncertainty-based node selection and the logic-poisoning loss are critical; removing either drastically reduces performance.

5. Significance

• Real-World Relevance: By operating under the clean-label constraint, Ba-Logic addresses a more realistic and challenging threat model, highlighting a critical security gap in GNNs that current defenses cannot easily close.
• Paradigm Shift: The paper shifts the focus of backdoor attacks from merely "injecting patterns" to "hijacking the model's internal logic." This suggests that future defenses must look beyond simple trigger removal and address the fundamental reliance of GNNs on specific subgraph structures for prediction.
• Scalability: The method demonstrates linear time complexity relative to graph size, making it feasible for large-scale industrial graphs (tested on OGBN-Products with 2.4M nodes).

In conclusion, Ba-Logic demonstrates that by explicitly guiding the GNN's attention mechanism to prioritize injected triggers over clean features, attackers can achieve highly effective backdoors even when they cannot manipulate training labels. This underscores the urgent need for new defense mechanisms that protect the internal prediction logic of GNNs.