Adversarial Attacks on Graph Classification via Bayesian Optimisation

Xingchen Wan, Henry Kenlay, Binxin Ru, Arno Blaas, Michael A. Osborne, Xiaowen Dong

Abstract

Graph neural networks, a popular class of models effective in a wide range of graph-based learning tasks, have been shown to be vulnerable to adversarial attacks. While the majority of the literature focuses on such vulnerability in node-level classification tasks, little effort has been dedicated to analysing adversarial attacks on graph-level classification, an important problem with numerous real-life applications such as biochemistry and social network analysis. The few existing methods often require unrealistic setups, such as access to internal information of the victim models, or an impractically-large number of queries. We present a novel Bayesian optimisation-based attack method for graph classification models. Our method is black-box, query-efficient and parsimonious with respect to the perturbation applied. We empirically validate the effectiveness and flexibility of the proposed method on a wide range of graph classification tasks involving varying graph properties, constraints and modes of attack. Finally, we analyse common interpretable patterns behind the adversarial samples produced, which may shed further light on the adversarial robustness of graph classification models.

Introduction

Graph Neural Networks (GNNs) have become essential for analyzing networked data, with applications ranging from drug discovery to social media analysis. However, GNNs are susceptible to adversarial attacks—small, intentional perturbations that lead to incorrect model predictions. While node-level adversarial research is extensive, graph-level classification has received less attention. Existing graph-level attacks typically rely on "white-box" assumptions or require an excessive number of queries, limiting their practical applicability. This work introduces GRABNEL (Graph Adversarial attack via BayesiaN Efficient Loss-minimisation), a black-box approach that is both query-efficient and parsimonious.

Methodology: The GRABNEL Framework

GRABNEL treats the adversarial attack as a black-box optimization problem, solved using Bayesian Optimization (BO). The framework consists of three primary components:

  1. Feature Extraction: To handle the discrete nature of graphs, a Weisfeiler-Lehman (WL) feature extractor transforms graphs into vector representations capturing local topological structures.
  2. Surrogate Model: A Sparse Bayesian Linear Regression model maps these features to the "attack loss." This model provides both predictions and uncertainty estimates, which are vital for guiding the search.
  3. Acquisition Function Optimization: A Genetic Algorithm (GA) identifies promising candidates by querying the computationally inexpensive surrogate model rather than the expensive victim model.
The GRABNEL pipeline, illustrating the interaction between the feature extractor, surrogate model, and victim model.

To ensure parsimony, GRABNEL employs sequential perturbation selection, flipping edges one at a time across multiple stages. This greedy approach minimizes the structural changes required to achieve a successful attack.

Experimental Evaluation

The effectiveness of GRABNEL was evaluated across diverse benchmarks, including bioinformatics (PROTEINS), social networks (IMDB-M, COLLAB), and real-world Twitter fake news cascades.

Performance and Query Efficiency

GRABNEL consistently outperforms baseline methods like random search and standard Genetic Algorithms. As illustrated in the results for the PROTEINS dataset, GRABNEL achieves a significantly higher Attack Success Rate (ASR) within a limited query budget compared to competing methods.

Attack Success Rate (ASR) vs. normalized number of queries for the PROTEINS-GIN model.

Key Insights

  • Adversarial Clustering: Successful perturbations are often localized, with adversarial edges clustering around common nodes, suggesting GNN sensitivity to local structural shifts.
  • Community Impact: In social networks, attacks often target community boundaries, attempting to merge or isolate clusters to confuse the classifier.
  • Low-Degree Vulnerability: Manipulating nodes with fewer connections can be highly effective, as these nodes can disproportionately influence the GNN's neighborhood aggregation process.

Conclusion

GRABNEL provides a robust and efficient black-box method for attacking graph classification models. By leveraging Bayesian Optimization and sequential edge selection, it achieves high success rates with minimal perturbations and queries. These findings highlight the need for more robust GNN architectures and provide a tool for evaluating their resilience in real-world scenarios.

Summary updated

Abstract

Graph neural networks, a popular class of models effective in a wide range of graph-based learning tasks, have been shown to be vulnerable to adversarial attacks. While the majority of the literature focuses on such vulnerability in node-level classification tasks, little effort has been dedicated to analysing adversarial attacks on graph-level classification, an important problem with numerous real-life applications such as biochemistry and social network analysis. The few existing methods often require unrealistic setups, such as access to internal information of the victim models, or an impractically-large number of queries. We present a novel Bayesian optimisation-based attack method for graph classification models. Our method is black-box, query-efficient and parsimonious with respect to the perturbation applied. We empirically validate the effectiveness and flexibility of the proposed method on a wide range of graph classification tasks involving varying graph properties, constraints and modes of attack. Finally, we analyse common interpretable patterns behind the adversarial samples produced, which may shed further light on the adversarial robustness of graph classification models.
BibTeX
@inproceedings{wan2021adversarial,
  author = {Xingchen Wan and Henry Kenlay and Binxin Ru and Arno Blaas and Michael A. Osborne and Xiaowen Dong},
  title = {{Adversarial Attacks on Graph Classification via Bayesian Optimisation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=5j_lH4OpZBl},
}
Figure