Trapping Attacker in Dilemma: Examining Internal Correlations and External Influences of Trigger for Defending GNN Backdoors

Researchers introduce PRAETORIAN, a novel defense mechanism against backdoor attacks on Graph Neural Networks that targets the fundamental requirements of effective attacks rather than surface-level indicators. The defense achieves a 99.45% reduction in attack success rates while maintaining minimal accuracy degradation, forcing adversaries into an unfavorable trade-off between attack effectiveness and detectability.

Graph Neural Networks face significant security vulnerabilities to backdoor attacks, where adversaries inject malicious triggers to manipulate model predictions on specific targets. Existing defense mechanisms typically focus on identifying suspicious patterns or anomalous features, leaving them susceptible to adaptive attackers who adjust their strategies to evade detection. PRAETORIAN represents a paradigm shift by analyzing the structural constraints that make backdoor attacks effective in the first place.

The core insight driving PRAETORIAN is that successful backdoor attacks inherently require substantial influence over target node predictions. Attackers must either inject numerous trigger nodes—making the attack detectable through volume analysis—or concentrate impact through a small set of highly influential nodes. By simultaneously examining internal correlations within trigger subgraphs and measuring external node influence metrics, PRAETORIAN creates a comprehensive detection framework that addresses both attack dimensions.

The performance metrics demonstrate substantial practical impact: reducing average attack success rates from typical levels exceeding 20% down to 0.55%, with negligible clean accuracy loss of 0.62% compared to 3%+ drops in competing defenses. Critically, PRAETORIAN maintains effectiveness against adaptive adversaries, where attackers respond by modifying their strategies. Any attempt to preserve attack viability forces attackers to accept either significant accuracy degradation or substantially reduced attack success rates.

For the AI security landscape, PRAETORIAN establishes a new baseline for GNN defense that shifts adversarial advantage back toward defenders. The constraint placed on attackers—forcing explicit trade-offs between efficacy and detectability—represents fundamental progress beyond pattern-matching approaches. This work influences how security researchers conceptualize neural network defenses, encouraging focus on underlying attack mechanics rather than surface manifestations.

• →PRAETORIAN reduces GNN backdoor attack success rates to 0.55% compared to 20%+ for existing defenses
• →The defense analyzes internal trigger correlations and external node influence simultaneously to detect attacks
• →Adaptive attackers face a forced trade-off: either accept >10% accuracy drops or limit attack success to 18.1%
• →The approach targets intrinsic attack requirements rather than pattern-matching, improving robustness
• →Performance maintains 99.38% clean accuracy, minimizing defensive overhead for legitimate model use