Revisiting Graph Adversarial Attack and Defense From a Data Distribution Perspective

Kuan Li, Yang Liu, Xiang Ao, Qing HeICLR 2023 · OpenReview

Executive Summary

Researchers have discovered that graph adversarial attacks aren't just random noise—they are highly strategic "distribution shifters." By focusing perturbations around training nodes, attackers effectively create a massive gap between what a model learns and what it's tested on. This novel perspective has led to nine practical tips for building more robust Graph Neural Networks (GNNs), alongside the development of a highly scalable heuristic attack and a robust self-training defense mechanism.

What Problem Does This Paper Address?

Graph Neural Networks are notoriously vulnerable to adversarial attacks. Small, often unnoticeable changes to a graph's structure—such as adding or removing edges—can severely degrade classification accuracy. While the community knows that gradient-based attacks work exceptionally well, the underlying reasons for their destructive power have remained largely unexplored.

Most existing research treats these attacks as localized structural perturbations. This paper, however, shifts the focus to a global view: Data Distribution Shift.

Adjacency matrix showing perturbations clustered around training nodes

In the common task of semi-supervised node classification (SSNC), training and testing nodes coexist on the same graph. The authors observed an interesting phenomenon: adversarial edges are not uniformly distributed. Instead, they cluster heavily around training nodes. The authors argue that the most effective attacks work by maximizing the difference between the distribution of training data and testing data, essentially "tricking" the model into learning a biased version of reality that fails to generalize to the rest of the graph.

Methods and Analytical Tools

To analyze and exploit this distribution shift, the authors introduce several novel tools and frameworks:

  • Intention Score (IS): A new metric designed to quantify where an attack "prefers" to place its adversarial edges (e.g., between two training nodes versus two testing nodes).
  • Distribution Shift Formalization: The researchers provide a mathematical framework using KL-Divergence to measure the shift in "community features"—the average features of a node's neighborhood—caused by structural changes.
  • Heuristic Attack Algorithm: Leveraging their insights, they designed a fast, rule-based attack that targets nodes with lower degrees to maximize distribution shift without the heavy computational cost of calculating gradients.
  • Self-Training Robust GCN (STRG): A novel defense method that uses a Multi-Layer Perceptron (MLP) to generate high-confidence pseudo-labels for unlabeled nodes. By training the GNN on these pseudo-labels, the model "sees" the testing distribution during training, effectively narrowing the distribution gap created by the attacker.

Key Insights and Ideas

Viewing graph attacks through the lens of data distribution yields several critical insights into both vulnerabilities and potential defenses.

The "Smaller Part" Strategy Theoretical and empirical evidence shows that to maximize distribution shift, an attacker should focus on the smaller subset of data. If the training set is small (e.g., 10% of the graph, which is typical in SSNC), the attack clusters around training nodes. Conversely, if the training set is large, the attack shifts toward testing nodes.

Accuracy degradation on Cora and Citeseer under different attack directions

Insertions Outperform Deletions The paper proves mathematically that adding "heterophily" edges (connecting nodes of different classes) creates a much larger distribution shift than deleting existing "homophily" edges (connecting nodes of the same class). This perfectly explains why approximately 80% of adversarial perturbations observed in the wild are edge insertions.

High-Degree Nodes are Anchors Nodes with many neighbors are naturally more stable. Their "community features" change very little even if a few edges are modified. The authors suggest "trusting" these nodes more during message passing to improve defense mechanisms.

The Power of Meta-Gradients The reason the famous MetaAttack algorithm is so successful is its unique ability to adaptively change its "intention" based on the size of the training set. Simpler gradient methods (like PGD) blindly attack training nodes regardless of the data split, limiting their effectiveness in varied scenarios.

Key Results

The study validates its findings on four standard benchmarks: Cora, Citeseer, Polblogs, and the massive ogbn-arxiv citation graph.

  • Defense Performance: The proposed STRG defense outperformed state-of-the-art methods like GNNGuard and ProGNN. On the Citeseer dataset under a severe 20% perturbation rate, STRG maintained 76.14% accuracy, while a standard GCN plummeted to 56.26%.
  • Scalability: Traditional gradient-based attacks (MetaAttack, PGD) often fail on large graphs due to Out-Of-Memory (OOM) errors. However, the authors' heuristic attack scaled easily to the ogbn-arxiv dataset (169,343 nodes), significantly outperforming the standard DICE baseline.
  • Efficiency: The proposed heuristic attack is orders of magnitude faster than gradient-based methods. On Citeseer, it took roughly 0.25 seconds, compared to over 548 seconds for MetaAttack.

Limitations and Future Work

The authors acknowledge that their self-training defense (STRG) inherently relies on the quality of the generated pseudo-labels. If the initial MLP is too weak, or if an attack is specifically designed to flip those pseudo-labels, the defense could be compromised.

Future directions include exploring more sophisticated ways to leverage high-degree anchor nodes and investigating how the "label noise" introduced by self-training interacts with adversarial robustness. Finally, the authors highlight that the "leakage" of the training/testing data split is a major security risk that requires more attention from the GNN community.

Summary updated

Abstract

Recent studies have shown that structural perturbations are significantly effective in degrading the accuracy of Graph Neural Networks (GNNs) in the semi-supervised node classification (SSNC) task. However, why the gradient-based methods are so destructive is rarely explored. In this work, we discover an interesting phenomenon: the adversarial edges are not uniformly distributed on the graph. Nearly all perturbations are generated around the training nodes in poisoning attack. Combined with this phenomenon, we provide an explanation for the effectiveness of the gradient-based attack method from a data distribution perspective and revisit both poisoning attack and evasion attack in SSNC. From this new perspective, we empirically and theoretically discuss some other attack tendencies. Based on the analysis, we provide nine practical tips on both attack and defense and meanwhile leverage them to improve existing attack and defense methods. Moreover, we design a fast attack method and a self-training defense method, which outperform the state-of-the-art methods and can effectively scale to large graphs like ogbn-arxiv. We conduct extensive experiments on four benchmark datasets to verify our claims.
BibTeX
@inproceedings{li2023revisiting,
  author = {Kuan Li and Yang Liu and Xiang Ao and Qing He},
  title = {{Revisiting Graph Adversarial Attack and Defense From a Data Distribution Perspective}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=dSYoPjM5J_W},
}
Figure