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:
- Hierarchical Target Selection: Instead of attacking everyone, PGA uses three filters to find easy targets:
- Preprocessing Filter: Excludes nodes the model already gets wrong.
- Degree Filter: Filters out high-degree nodes, which are mathematically harder to influence.
- 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.
- 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.
- 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