Simple and Efficient Partial Graph Adversarial Attack: A New Perspective

Guanghui Zhu, Mengyu Chen, Chunfeng Yuan, Yihua Huang

TL;DR

Existing global adversarial attacks on Graph Neural Networks (GNNs) often waste their limited "attack budget" by trying to disrupt every node in a graph indiscriminately. This paper introduces Partial Graph Attack (PGA), a strategy that identifies and prioritizes "vulnerable" nodes, achieving significantly higher attack success rates and better computational efficiency than state-of-the-art global attacks.

What Problem Does This Paper Address?

Graph adversarial attacks involve making small, imperceptible changes to a graph (like adding or removing edges) to trick a GNN into making wrong predictions. Most "global" attacks follow a rigid definition: they try to degrade the performance of the entire graph.

The authors identify a major flaw in this approach: node-level variability. Not all nodes are created equal; some are naturally robust (e.g., high-degree "hub" nodes), while others are fragile. By spreading an attack budget (the number of allowed edge changes) across all nodes, existing methods waste resources on "hard" targets. The challenge is to develop a method that intelligently selects the most "flippable" nodes to maximize the drop in overall model accuracy.

Methods

The authors propose the Partial Graph Attack (PGA) framework, which consists of three main stages:

  1. Hierarchical Target Selection: Instead of attacking everyone, PGA uses three filters to find easy targets:
  2. Preprocessing Filter: Excludes nodes the model already gets wrong.
  3. Degree Filter: Filters out high-degree nodes, which are mathematically harder to influence.
  4. Margin Filter: Focuses on nodes with a small "classification margin" (the difference between the highest and second-highest prediction scores), as these are closest to the decision boundary.
  5. Cost-effective Anchor-picking: To change a target node's label, you need to connect it to "anchors" (other nodes). Rather than checking every possible pair in the graph, PGA picks anchors from the target's "second-best" predicted category. It then uses a simplified surrogate model (a 2-layer GCN without non-linearities) to calculate gradients and keep only the most promising edges.
  6. Iterative Greedy-based Attack: The attack is executed by flipping edges (adding or removing) based on the calculated gradients. To speed things up, they use an aggressive edge-flip strategy, flipping multiple edges ($K$ edges) per gradient calculation rather than just one.

Datasets

The researchers evaluated PGA on four standard citation network benchmarks:

  • Cora, Citeseer, CoraML, and Pubmed. These datasets vary in size and density, with Pubmed serving as the primary test for scalability (containing ~20k nodes and ~44k edges).

Key Insights and Ideas

  • The "Vulnerability" Hypothesis: The authors proved that a small number of "fake" edges can flip the majority of nodes in a graph. By focusing the attack budget on these vulnerable nodes, the global accuracy of the model drops much faster.
  • Efficiency through Sparsity: By narrowing the search space for both targets and anchors, PGA avoids the $O(N^2)$ complexity that plagues many optimization-based graph attacks.
  • Surrogate Effectiveness: The paper confirms that a simplified, linear GCN surrogate is highly effective at generating gradients that transfer well to more complex, non-linear victim models.
  • Aggressive Flipping: Traditional greedy attacks are slow because they recalculate gradients after every single edge change. PGA shows that you can flip many edges at once based on a single gradient step without losing much attack potency, drastically reducing runtime.

Key Results

  • Superior Attack Effect: In almost every test case across 10 different GNN architectures (including "robust" models like RGCN and GNNGuard), PGA resulted in the lowest post-attack accuracy. For example, on the Cora dataset using a standard GCN, PGA dropped accuracy to 66.26%, outperforming the previous state-of-the-art (GreedyRBCD) at 68.90%.
  • Massive Speedups: On the large Pubmed dataset, traditional PGD attacks can take over 30 minutes, and standard greedy attacks can take up to 4 hours. PGA performs the attack in a fraction of that time while maintaining higher effectiveness.
  • Stealthiness: The authors visualized the node degree distribution before and after the attack. PGA’s perturbations are "unnoticeable" because they don't drastically alter the fundamental structural statistics of the graph.

Limitations and Future Work

  • Surrogate Dependency: While the GCN surrogate works well, the attack's effectiveness still depends on how well the surrogate mimics the victim model. If the victim model uses a radically different architecture, the transferability might decrease.
  • Poisoning vs. Evasion: The paper primarily focuses on evasion attacks (attacking a trained model during testing). While they show some success in poisoning settings (attacking during training), the method isn't specifically optimized for the unique dynamics of training-time interference.
  • Future Direction: The authors suggest that combining PGA’s target selection with "random block gradient descent" (used in methods like PRBCD) could lead to even greater scalability for massive, billion-node graphs.

Summary updated

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 existing graph global attack methods.
BibTeX
@article{zhu2024simple,
  author = {Guanghui Zhu and Mengyu Chen and Chunfeng Yuan and Yihua Huang},
  title = {{Simple and Efficient Partial Graph Adversarial Attack: A New Perspective}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2024},
  doi = {10.1109/tkde.2024.3364972},
}

Loading related content...

Figure