Abstract
Graph Neural Networks (GNNs) are increasingly deployed in critical domains such as fraud detection and software vulnerability discovery. However, they remain highly susceptible to adversarial attacks involving edge, node, and feature perturbations. Current defenses are typically empirical and easily bypassed, or probabilistic and limited in scope. We introduce AGNNCert, the first deterministic certified defense framework capable of protecting GNNs against arbitrary, simultaneous perturbations. AGNNCert utilizes a novel graph partitioning and majority-voting architecture to provide mathematically certain robustness guarantees for both node and graph classification tasks.
Introduction
Graph Neural Networks are the backbone of modern network analysis but are notoriously brittle. Attackers can manipulate GNN predictions through various means: adding fake edges (edge perturbation), injecting malicious nodes (node injection), or altering node features. Existing defenses generally fall into two categories: empirical defenses, which often succumb to adaptive attacks, and certified defenses, which provide mathematical guarantees but are frequently restricted to specific attack types or provide only probabilistic certainty. AGNNCert addresses these gaps by offering a "universal," deterministic defense that handles all three types of perturbations concurrently.
Methodology
The AGNNCert framework follows a three-step pipeline designed to quarantine adversarial influence and provide a certifiable prediction.
Deterministic Graph Division
The core innovation of AGNNCert lies in its graph partitioning strategies. Instead of processing the entire graph, the system divides it into $T$ smaller subgraphs. Two primary strategies are proposed:
- Edge-centric Division: Edges are hashed into disjoint sets.
- Node-centric Division: This strategy is specifically designed to mitigate node injection attacks. By treating undirected edges as pairs of directed ones and hashing nodes such that all outgoing edges from a specific node are assigned to the same subgraph, the influence of a single injected node—regardless of its degree—is restricted to exactly one subgraph.
Voting and Certification
A base GNN classifier generates predictions for each subgraph, which serve as "votes." The final prediction is determined by a majority vote. The system then calculates a certified perturbation size $M$. If the total number of adversarial changes remains below $M$, the majority vote is mathematically guaranteed to remain unchanged. Unlike randomized smoothing techniques, AGNNCert's deterministic hashing ensures exact certificates without the need for expensive Monte-Carlo sampling.
Experimental Evaluation
The authors evaluated AGNNCert across diverse benchmarks, including node classification (Cora-ML, Citeseer, PubMed, Amazon2M) and graph classification (AIDS, MUTAG, Big-Vul).
Key Results
- Robustness Performance: On Cora-ML, AGNNCert-E maintained approximately 70% certified accuracy under a budget of 200 edge perturbations.
- Resilience to Node Injection: AGNNCert-N significantly outperformed existing methods like Bi-RS in node injection scenarios, as its directed hashing prevents high-degree malicious nodes from corrupting multiple subgraph predictions.
- Scalability: The framework successfully certified the Amazon2M dataset (2.4M nodes, 61M edges), demonstrating its applicability to industrial-scale graphs.
- Accuracy Trade-off: A minor "robustness-accuracy tradeoff" was observed, with standard accuracy typically decreasing by ~5% compared to full-graph GNNs due to the use of partial subgraph information.
Conclusion
AGNNCert represents a significant advancement in GNN security, providing the first deterministic, task-agnostic framework for certifying robustness against arbitrary perturbations. While the method introduces a computational overhead proportional to the number of subgraphs, its ability to provide 100% certain guarantees makes it a robust choice for high-stakes applications. Future work will focus on improving inference speed and extending protection to training-time poisoning attacks.
Summary updated