Abstract
As the study of graph neural networks becomes more intensive and comprehensive, their robustness and security have received great research interest. The existing global attack methods treat all nodes in the graph as their attack targets. Although existing methods have achieved excellent results, there is still considerable space for improvement. The key problem is that the current approaches rigidly follow the definition of global attacks. They ignore an important issue, i.e., different nodes have different robustness and are not equally resilient to attacks. From a global attacker's view, we should arrange the attack budget wisely, rather than wasting them on highly robust nodes. To this end, we propose a totally new method named partial graph attack (PGA), which selects the vulnerable nodes as attack targets. First, to select the vulnerable items, we propose a hierarchical target selection policy, which allows attackers to only focus on easy-to-attack nodes. Then, we propose a cost-effective anchor-picking policy to pick the most promising anchors for adding or removing edges, and a more aggressive iterative greedy-based attack method to perform more efficient attacks. Extensive experimental results demonstrate that PGA can achieve significant improvements in both attack effect and attack efficiency compared to other existing graph global attack methods.
Introduction
Graph Neural Networks (GNNs) have demonstrated remarkable performance across various domains, yet their susceptibility to adversarial attacks remains a critical concern. Adversarial attacks on graphs typically involve making small, imperceptible perturbations—such as adding or removing edges—to mislead the model's predictions. Current "global" attack methodologies aim to degrade the performance of the entire graph by treating all nodes as potential targets.
However, this conventional approach overlooks a fundamental characteristic of graph data: node-level variability in robustness. Some nodes, such as high-degree hubs, are naturally more resilient to influence, while others are inherently fragile. By distributing a limited attack budget across all nodes indiscriminately, existing methods often waste resources on "hard" targets that are unlikely to flip.
To address this, we introduce the Partial Graph Attack (PGA). PGA shifts the perspective from attacking the whole graph to strategically targeting "vulnerable" nodes. By focusing the attack budget where it is most effective, PGA achieves superior performance in both attack success rate and computational efficiency.
Methodology
The PGA framework is structured into three distinct stages designed to optimize the selection of targets and the execution of perturbations.
1. Hierarchical Target Selection
PGA employs a three-tier filtering process to identify nodes that are most susceptible to adversarial influence:
- Preprocessing Filter: Excludes nodes that the victim model already misclassifies, as attacking them provides no additional gain.
- Degree Filter: Removes high-degree nodes. Mathematically, nodes with more connections require more perturbations to change their local neighborhood structure significantly.
- Margin Filter: Identifies nodes with a small "classification margin"—the difference between the highest and second-highest class probabilities. Nodes near the decision boundary are the easiest to flip.
2. Cost-effective Anchor-picking
Once targets are selected, the next step is to identify "anchor" nodes for edge manipulation. To avoid the $O(N^2)$ complexity of searching all node pairs, PGA restricts the search to nodes belonging to the target's "second-best" predicted category. It utilizes a simplified, linear 2-layer GCN surrogate model to calculate gradients, identifying the most promising edges to flip.
3. Iterative Greedy-based Attack
The attack is executed by flipping edges based on the calculated gradients. Unlike traditional greedy methods that recalculate gradients after every single flip, PGA adopts an aggressive edge-flip strategy. It flips $K$ edges per gradient calculation, significantly accelerating the process without compromising attack potency.
Key Insights and the Vulnerability Hypothesis
The core motivation for PGA is the "Vulnerability Hypothesis": a small number of carefully chosen perturbations can flip a significant portion of nodes in a graph. Empirical analysis of benchmark datasets supports this, showing that many nodes require very small budgets to be successfully attacked.
By narrowing the search space for both targets and anchors, PGA avoids the scalability issues of optimization-based attacks. Furthermore, the use of a linear surrogate model proves highly effective, as gradients generated from these simplified models transfer well to complex, non-linear victim architectures.
Experimental Results
PGA was evaluated against four standard citation networks: Cora, Citeseer, CoraML, and Pubmed. The results consistently demonstrate PGA's superiority:
- Effectiveness: Across 10 different GNN architectures, including robust variants like RGCN and GNNGuard, PGA achieved the lowest post-attack accuracy. For instance, on the Cora dataset, PGA reduced GCN accuracy to 66.26%, outperforming the state-of-the-art GreedyRBCD (68.90%).
- Efficiency: On the large-scale Pubmed dataset, PGA achieved massive speedups. While traditional PGD and greedy attacks can take hours, PGA completes the attack in a fraction of the time.
- Stealthiness: Visualizations of node degree distributions confirm that PGA’s perturbations are unnoticeable, maintaining the graph's fundamental structural statistics.
Conclusion
The Partial Graph Attack (PGA) offers a new perspective on global graph adversarial attacks by prioritizing node vulnerability. By intelligently allocating the attack budget and employing efficient gradient-based heuristics, PGA sets a new benchmark for both effectiveness and scalability in the field of GNN security. Future work may explore combining PGA's selection strategies with randomized block gradient methods to further enhance scalability for billion-node graphs.
Summary updated