Clean-Label Graph Backdoor Attack in the Node Classification Task

Hui Xia, Xiangwei Zhao, Rui Zhang, Shuo Xu, Luming WangAAAI 2025 · DOI

Introduction

Graph Neural Networks (GNNs) have become the standard for modeling complex relational data, particularly in node classification tasks. However, their widespread adoption has also made them targets for adversarial attacks. Traditional backdoor attacks often rely on "dirty labels," where an adversary injects a trigger into training samples and intentionally mislabels them to a target class. While effective, these attacks are easily detectable through data filtering or manual inspection.

To address this vulnerability, researchers have proposed the Clean-Label Graph Backdoor Attack (CGBA). Unlike its predecessors, CGBA poisons nodes that already belong to the target class, ensuring that labels remain correct and the attack remains stealthy. This paper details the methodology and performance of CGBA, demonstrating its high effectiveness and minimal impact on benign model performance.

The CGBA Framework

The CGBA method operates in a black-box setting, requiring no knowledge of the target model's internal parameters. The attack follows a structured three-step pipeline designed to maximize both impact and concealment.

Overview of the Clean-Label Graph Backdoor Attack (CGBA) pipeline.
  1. Poisoned Node Selection: CGBA strategically selects nodes within the target class that exhibit high uncertainty (low classification confidence) and low degrees. By targeting "uncertain" nodes, the attacker provides the model with a clear "shortcut" (the trigger) to the correct label, which the model then over-relies on. Selecting low-degree nodes minimizes structural disruption, enhancing stealth.
  2. Poisoned Feature Selection: Utilizing Graphlime, a graph explanation tool, the attack identifies the most influential features for the GNN’s decision-making process. The backdoor trigger is then specifically attached to these high-impact feature positions.
  3. Trigger Generation: The trigger is optimized through a multi-objective loss function. It aims to maximize the model's confidence in the target class when the trigger is present while maintaining similarity to the node's original features and its local neighborhood. This neighbor-aware optimization makes CGBA resistant to homophily-based defenses.

Experimental Evaluation

The effectiveness of CGBA was evaluated on three benchmark datasets: Cora (continuous features), Citeseer (discrete features), and Pubmed (large-scale continuous features). The attack was tested against four prominent GNN architectures: Graph Convolutional Networks (GCN), Graph Attention Networks (GAT), GraphSAGE, and Graph Autoencoders (GAE).

Results and Discussion

The experimental results demonstrate that CGBA is highly effective across various settings. On the Pubmed dataset, with a poisoning rate of just 0.5%, CGBA achieved an Attack Success Rate (ASR) of 96.94% on GCN and a perfect 100% on GraphSAGE.

Attack Success Rate (ASR) of CGBA compared to baselines across different GNN architectures and datasets.

Crucially, the attack maintains high stealth. The drop in Benign Accuracy (BA)—the model's performance on clean data—was typically less than 0.5%. Furthermore, CGBA proved resilient to common GNN defenses like edge pruning and node isolation. While these defenses significantly degraded the performance of baseline attacks like GTA or MIA, CGBA's neighbor-aware triggers allowed it to bypass structural anomaly detectors.

Conclusion

CGBA represents a significant advancement in graph backdoor research, proving that clean-label attacks can be both highly effective and exceptionally stealthy. By exploiting model uncertainty and structural properties of the graph, CGBA creates a robust backdoor that is difficult to detect using standard defensive techniques. Future work may involve extending these principles to other graph-based tasks such as link prediction or graph-level classification.

Summary updated

BibTeX
@inproceedings{xia2025clean,
  author = {Hui Xia and Xiangwei Zhao and Rui Zhang and Shuo Xu and Luming Wang},
  title = {{Clean-Label Graph Backdoor Attack in the Node Classification Task}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i20.35466},
}
Figure