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:
- 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.
- 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.
- 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.
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.
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).
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