Towards More Realistic and Practical Graph Backdoor Attacks

Abstract

Graph Neural Networks (GNNs) have demonstrated remarkable performance on graph-based learning tasks and are increasingly deployed in security-critical applications. However, recent studies have shown that they are highly vulnerable to graph backdoor attacks (GBAs), where adversaries implant malicious triggers to induce targeted misclassification during inference. Despite their effectiveness, existing GBAs are often developed under unrealistic assumptions, such as focusing exclusively on simple homogeneous graphs or assuming the adversary possesses privileged access to target nodes during inference. This dissertation aims to systematically investigate and design graph backdoor attacks under significantly more realistic graph settings and adversarial constraints. First, we investigate the underexplored vulnerabilities of Heterogeneous Graph Neural Networks (HGNNs). We conduct the first systematic investigation of existing GBAs on HGNNs, revealing that current methods suffer from high attack budgets and unreliable backdoor activation in complex, real-world heterogeneous scenarios. To overcome these issues, we propose the Heterogeneous Graph Backdoor Attack (HGBA), which departs from traditional subgraph-based triggers by introducing a novel relation-based trigger. By leveraging backdoor metapaths, HGBA successfully confines the adversary’s influence to feasible, user-level activation behaviors, demonstrating superior robustness against feature shifts and anomaly detection. Second, we revisit GBAs in standard node classification tasks to address the unrealistic assumption that attackers have access to target nodes or their surrounding neighborhood topologies at inference time. To strictly enforce restricted-access constraints, we propose TAGBA, a Target- Agnostic Graph Backdoor Attack. TAGBA completely eliminates the reliance on victim-specific information during inference by synthesizing a universal trigger conditioned on class-level prototypes. By introducing a Class-Concentrated Poisoned Node Selection strategy and a Distribution- Aware Trigger Generator, TAGBA ensures that the triggers are highly potent yet statistically unnoticeable. Together, these contributions bridge the fundamental gap between attack effectiveness and threat-model realism, highlighting the severe practical security risks of deploying GNNs and driving the critical need for more robust defenses.