Adversarial Attacks on Graph Classifiers via Bayesian Optimisation

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

TL;DR

GRABNEL is a novel black-box adversarial attack designed specifically for graph classification models. By leveraging Bayesian Optimization, it identifies successful perturbations—such as adding or deleting edges—with significantly higher query efficiency and fewer changes to the graph structure than previous methods.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) have become the go-to tool for analyzing data structured as networks, from predicting molecular properties in drug discovery to identifying fake news cascades on social media. However, like their image-processing cousins, GNNs are vulnerable to adversarial attacks: small, intentional changes to the input that cause the model to fail.

While much research has focused on attacking node-level tasks (like classifying a single user in a social network), graph-level classification (classifying the entire network) has been neglected. Existing attacks on graph classification often rely on "white-box" assumptions—meaning the attacker knows the model's internal weights—or require an impractically high number of queries to the target model. This paper introduces a "black-box" approach that is both query-efficient (needs fewer tries) and parsimonious (makes minimal changes to the graph).

Methods

The authors propose GRABNEL (Graph Adversarial attack via BayesiaN Efficient Loss-minimisation). The core idea is to treat the adversarial attack as a black-box optimization problem and solve it using Bayesian Optimization (BO).

The GRABNEL pipeline consists of three main components:

  1. Feature Extraction: Since graphs are discrete and combinatorial, they can't be plugged directly into standard BO. The authors use a Weisfeiler-Lehman (WL) feature extractor to transform graphs into vector representations that capture local topological structures.
  2. Surrogate Model: They employ Sparse Bayesian Linear Regression to map these graph features to the "attack loss" (a measure of how close the model is to being fooled). This model provides both a prediction and a measure of uncertainty, which is crucial for BO.
  3. Acquisition Function Optimization: To decide which graph to query next, GRABNEL uses a Genetic Algorithm (GA). Instead of querying the expensive victim model, the GA queries the cheap surrogate model to find the most promising candidate for the next attack attempt.
The overall pipeline of GRABNEL, showing the interaction between the surrogate model, feature extractor, and the victim model.

To keep the attack subtle, GRABNEL uses sequential perturbation selection. Instead of changing many edges at once, it greedily flips one edge at a time across multiple stages, only progressing if the current stage fails to find a successful adversarial example.

The sequential edge selection process, showing how the attack progresses through stages to find the most effective perturbation.

Datasets

The researchers evaluated GRABNEL on several benchmarks:

  • TU Datasets: Common benchmarks for graph classification, including IMDB-M (social networks), PROTEINS (bioinformatics), COLLAB, and REDDIT-MULTI-5K.
  • MNIST-75sp: A version of the MNIST digit dataset where images are converted into graphs of "superpixels."
  • Twitter Fake News: A real-world dataset where graphs represent the spread (cascades) of rumors on Twitter.
  • ER-graphs: Synthetic graphs generated using the Erdős–Rényi model.

Key Insights and Ideas

  • Efficiency through Uncertainty: By using a Bayesian surrogate, the attacker can intelligently explore the massive space of possible graph edits, focusing on areas where the victim model is likely to be vulnerable.
  • Adversarial Clustering: Successful adversarial edges aren't scattered randomly; they tend to cluster closely together, often sharing common nodes. This suggests that GNNs are particularly sensitive to localized structural changes.
  • Community Destruction: In social network data, attacks often target "community structures." For certain models (like GCN), the attack tries to merge or delete edges between communities to confuse the classifier.
  • Vulnerability of Low-Degree Nodes: The authors found that manipulating nodes with few connections (low-degree nodes) can be surprisingly effective, as these nodes often have a disproportionately large influence on the neighborhood aggregation process in GNNs.

Key Results

GRABNEL consistently outperformed baseline methods like random search and standard Genetic Algorithms across all datasets.

  • Attack Success Rate (ASR): As shown in Figure 3, GRABNEL achieves a much higher success rate for a given "query budget" compared to other methods.
  • Parsimony: In the MNIST-75sp task, GRABNEL required significantly fewer edge swaps (median of ~2) to successfully flip a classification compared to a strong sequential random baseline (median of ~4).
  • Real-World Impact: On the Twitter fake news dataset, GRABNEL reduced the effectiveness of a GCN-based detector by a third using a "node injection" attack (simulating a bot joining a conversation).
Comparison of Attack Success Rate (ASR) against the number of queries for different datasets and models. GRABNEL (red) consistently outperforms baselines.

Limitations and Future Work

  • Topological Focus: The current work primarily focuses on structural attacks (adding/deleting edges). While the surrogate is compatible with node/edge feature attacks, these were not the primary focus of the experiments.
  • Task Specificity: GRABNEL is currently tailored for graph classification. Adapting it to other tasks like link prediction or node classification would require modifying the loss functions.
  • Defense Mechanisms: The authors suggest that future work should test GRABNEL against more robust GNN architectures that incorporate specialized defense mechanisms like randomized smoothing.

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 Osborne and Xiaowen Dong},
  title = {{Adversarial Attacks on Graph Classifiers via Bayesian Optimisation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=5j_lH4OpZBl},
}

Loading related content...

Figure