Adversarial Training for Graph Neural Networks via Graph Subspace Energy Optimization

Ganlin Liu, Ziling Liang, Xiaowei Huang, Xinping Yi, Shi JinarXiv 2024 · DOI · arXiv

Graph Neural Networks (GNNs) have revolutionized tasks involving structured data, yet they remain notoriously fragile to adversarial perturbations. Small, intentional changes to a graph's topology—such as adding or removing a few edges—can drastically degrade performance. This paper introduces AT-GSE, a novel adversarial training framework designed for inductive GNNs, leveraging a new metric called Graph Subspace Energy (GSE) to measure and counteract these structural attacks.

The Challenge of Graph Robustness

Most GNN research operates in a transductive setting, assuming all nodes are known during training. However, real-world applications require inductive models that generalize to entirely new nodes and graphs at inference time. Furthermore, the field has lacked a clear, measurable indicator of structural "attack intensity," making it difficult to generate effective adversarial examples for robust training.

Graph Subspace Energy (GSE)

The core innovation of this work is the identification of Graph Subspace Energy (GSE). The authors observed that common adversarial attacks (like Metattack or PRBCD) cause a "right-shift" in the singular value distribution of a graph's adjacency matrix. Essentially, attacks inject energy into specific subspaces of the graph. GSE quantifies this phenomenon, serving as a reliable "robustness thermometer."

Spectral shift in singular values and corresponding GSE increases for Cora and Citeseer datasets under varying attack ratios.

The AT-GSE Framework

AT-GSE employs a minimax optimization strategy to build resilience:

  • Inner Maximization: The algorithm identifies "worst-case" perturbations by maximizing both the GNN's loss and the GSE. This is achieved through a "GSE Offset Attack," which simulates sophisticated structural threats by shifting singular values.
  • Outer Minimization: The GNN is trained to minimize its loss on these high-energy adversarial graphs, learning to ignore the noise injected by attackers.

To ensure the method scales to large graphs, the authors introduced two efficient variants: RndSVD (Randomized SVD) for local attacks and the Nyström Method for global structure preservation. These techniques provide speedups of 40x to 80x over standard SVD calculations.

Experimental Validation

The researchers evaluated AT-GSE on seven diverse datasets, including citation networks (Cora, Citeseer, Pubmed), synthetic stochastic block models, and web data (WikiCS). Across all tests, GSE consistently tracked attack intensity, confirming its utility as a diagnostic metric.

GSE values across Cora, Cora_ML, and Citeseer datasets, demonstrating a consistent increase as the attack ratio rises from 0% (clean) to 25%.

Key Results and Insights

  • Superior Robustness: AT-GSE significantly outperforms standard GNNs under heavy attack. For example, on the Citeseer dataset with a 25% attack budget, AT-GSE maintained ~65-68% accuracy, while standard models dropped to ~45-50%.
  • The Clean Accuracy Paradox: Typically, adversarial training involves a trade-off where robustness comes at the cost of performance on normal (clean) data. AT-GSE breaks this trend; by regularizing the graph's energy, the model learns a more generalized representation that often performs better on clean data than standard training.
  • Scalability: The framework successfully handled the Pubmed dataset (~20,000 nodes), a scale that would typically cause standard SVD-based methods to fail.

Conclusion

AT-GSE provides a principled and efficient approach to securing GNNs in realistic, inductive environments. By optimizing for Graph Subspace Energy, the framework not only defends against structural attacks but also enhances the model's fundamental ability to generalize from clean data. Future work will look toward further optimizing hyperparameters and scaling the approach to "web-scale" graphs with millions of nodes.

Summary updated

Abstract

Despite impressive capability in learning over graph-structured data, graph neural networks (GNN) suffer from adversarial topology perturbation in both training and inference phases. While adversarial training has demonstrated remarkable effectiveness in image classification tasks, its suitability for GNN models has been doubted until a recent advance that shifts the focus from transductive to inductive learning. Still, GNN robustness in the inductive setting is under-explored, and it calls for deeper understanding of GNN adversarial training. To this end, we propose a new concept of graph subspace energy (GSE) -- a generalization of graph energy that measures graph stability -- of the adjacency matrix, as an indicator of GNN robustness against topology perturbations. To further demonstrate the effectiveness of such concept, we propose an adversarial training method with the perturbed graphs generated by maximizing the GSE regularization term, referred to as AT-GSE. To deal with the local and global topology perturbations raised respectively by LRBCD and PRBCD, we employ randomized SVD (RndSVD) and Nystrom low-rank approximation to favor the different aspects of the GSE terms. An extensive set of experiments shows that AT-GSE outperforms consistently the state-of-the-art GNN adversarial training methods over different homophily and heterophily datasets in terms of adversarial accuracy, whilst more surprisingly achieving a superior clean accuracy on non-perturbed graphs.
BibTeX
@misc{liu2024adversarial,
  author = {Ganlin Liu and Ziling Liang and Xiaowei Huang and Xinping Yi and Shi Jin},
  title = {{Adversarial Training for Graph Neural Networks via Graph Subspace Energy Optimization}},
  year = {2024},
  eprint = {2412.18886},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.18886},
}
Figure