Adversarial Attacks on Graph Classifiers via Bayesian Optimisation
Authors: Xingchen Wan
Henry Kenlay
Binxin Ru
Arno Blaas
Michael Osborne
Xiaowen Dong
Venue: NeurIPS 2021 Poster (2021)
Keywords: adversarial attack
Bayesian optimisation
graph neural networks

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. 

Adversarial Attacks on Graph Classification via Bayesian Optimisation
Xingchen Wan Henry Kenlay Binxin Ru Arno Blaas Michael A. Osborne Xiaowen Dong Machine Learning Research Group, University of Oxford, Oxford, UK ( xwan, kenlay, robin, arno, mosb, xdong) ) 9 Brobots. ac.ac. uk
Abstract
Graph neural networks, popular class of models effective in 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 applica- tions such as biochemistry and social network analysis. The few existing methods often require unrealistic setups, such as access internal information of the victim number of queries. We present a novel Bayesian
models, or an impractically- 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 adver- sarial robustness of graph classification models, An open-source implementation is available at https: /ttp::://githutee htt.:/wwww.ooo...innncnnnnaaaaaa grabnel
Introduction
Graphs are general-purpose data structure consisting of entities represented by nodes and edges which encode pairwise relationships. Graph-based machine learning models has been widely used in variety of important applications such as semi-supervised learning, link prediction, community detection and graph classification 33 51 [4]. Despite the growing interest in graph-based machine learning, has been shown that, like many other machine learning models, graph-based models are vulnerable to adversarial attacks [33 (7). If we want to deploy such models in environments where the risk and costs associated with a model failure are high e.g. in social networks, would crucial to understand and assess the model stability and vulnerability by simulating adversarial attacks.
Adversarial attacks on graphs can be aimed at different learning tasks. This paper focuses on graph- level classification, where given an input graph (potentially with node and edge attributes), we wish to learn function that predicts property of interest related to the graph. Graph classification is an important task with many real-life applications, especially in bioinformatics and chemistry 24 (25). For example, the task may be to accurately classify a molecule, modelled as a graph whereby nodes represent atoms and edges model bonds, inhibits HIV replication not. Although there are a few attempts on performing adversarial attacks on graph classification [10] 23), they all operate under unrealistic assumptions such as the need to query the target model large number of times or access a portion of the test set train the attacking agent. To address these limitations, black-box optimisation problem and
formulate the adversarial attack on graph classification solve it with Bayesian optimisation (BO), a query-efficient state-of-ther of-the--rttttt reroth-order black-box optimiser. Unlike existing work, our method is query query-efficient, parsimonious in perturbations and
35th Conference on Neural Information Processing Systems (NcurIPS 2021)

---

Report attack failure outgut successuul sumplets)
Query trained victim model fo for attack loss
Yes
Successful
ritucck/hudlrr exhausted??
No
Perturbed graphs
Targeta of surrogate
Base graph
Surrogate
(Bayesium linear regression)
Feature extractor W.FeaturreFtrrer
Input(s) to surzugite
Generate new query perturbed grapis maximising the acquisition lunction
Figure 1: The overall pipeline of GRABNEL. The key components are explained in different paragraphs of Sec 2 Surrogate model describes the construction of the BO surrogate and the feature extractor (Block 1) Sequential perturbation selection describes how base graphs and perturbed graphs as candidates of adversarial attack are selected (Block 2), and Optimisation of acquisition function describes how new query points are generated by BO via optimising acquisition (Block 3). A detailed algorithmic description for GRABNEL is also available in App.
does not require policy training on a separate labelled dataset to effectively attack a new sample. Another benefit of our method is that it can be easily adapted to perform various modes of attacks such as deleting or rewiring edges and node injection. Furthermore, we investigate the topological properties of the successful adversarial examples found by method and offer valuable insights on the connection between the graph topology change and the model robustness.
The main contributions of our paper as follows. First, we introduce novel black-box attack for graph classification, GR GRABNEI which is both query efficient and parsimonious. We believe this is the first work on using BO for adversarial attacks on graph data. Second, we analyse the generated adversarial examples to link the vulnerability of graph-based machine learning models to the topological properties of the perturbed graph. an important step towards interpretable adversarial examples that has been overlooked by the majority of the literature. Finally, we evaluate our method on a range of real-world datasets and scenarios including detecting the spread of fake news on Twitter, which to the best of our knowledge is the first analysis of this kind in the literature.
2 Proposed Method: GRABNEL
Problem Setup A graph G = (V,E) is defined by set of nodes V = {u, and edges & {e:)?= where each edge e₁ (1); v3) connects between nodes v; and uy. The overall topology can be represented by the adjacency matrix A E (0. 1)x" where A, = if the edge (0,, "3} is presen The attack objective in our case is to degrade the predictive performance of the trained victim graph classifier fo by finding a graph G' perturbed from the original test graph (ideally with the minimum amount of perturbation) such that fa produces an incorrect class label for g. In this paper, we consider the black-box evasion attack setting, where the adversary agent cannot access/modify the the victim model So (i.e. network architecture, weights 0 or gradients) or its training data [(G,, y4) /= the adversary can only interact with Se by querying it with an input graph G' and observe the model output fe(G") as escudd-probabbln
over all classes in C-dimensiional standard simplex. Additionally, we assume that sample efficiency is highly valued: we aim to find adversarial examples with the minimum number of queries to the victim model. We believe that this is a practical and difficult setup that accounts for the prohibitive monetary, logistic and/or opportunity costs of repeatedly querying (possibly huge and complicated) real-life victim model. With high query count, the attacker may also run a higher risk of getting detected. Formally, the objective function of our attack agent can be formulated as black-box maximisation problem:
max Cattack (fo(g').v) s.t. y = arg max fo( ('EV(())
Stands for Graph Adversorial attack via BayesiaN Efficient Loss-minimisation. We discuss the unweighted graphs for simplicity; method may also handle other graph types.

---

where fo is the pretrained victim model that remains fixed in the evasion attack setup and is the correct label of the original imput G. Denote the output logit for the class y as fo , the attack loss fatttak can be defined as:
(max log fo(g"); - log f9 (log Jo(()): log fo(g")
(untargeted attack) (targeted attack on class (),
Lattack (oo()).))
(2)
where fo()), denotes the logit output for class t. Such an attack loss definition is commonly used both the traditional image attack and the graph attack literature 4 [2) although our method is compatible with any choice of loss function. Furthermore, 4 (G) refers to the set of possible G' generated from perturbing G. In this work, we experiment with a diverse modes of attacks to show that our attack method can be generalised to different set-ups:
creating/removing an edge: we create perturbed graphs by flipping the connection a small set of node pairs 8A- {{ v } of G following previous works [52 [0];
rewiring or swapping edges: similar to [23], we select a triplet (u, v, 8) where we either rewire the
edge (u + v) to (u s) (rewire), or exchange the edge weights w(u, (u, v) and w(u, s) (swap);
node injection: we create new nodes together with their attributes and connections in the graph.
The overall routine of our proposed GRABNEL is presented in Fig (and in pseudo-code form in App A). and we now elaborate each of its key components.
Surrogate model
The success of Bo hinges upon the surrogate model choice. Specifically, such surrogate model needs to 1) be flexible and expressive enough to locally learn the latent mapping from a perturbed graph G' to its attack loss aatack (folacccfoo y) (note that this is different and generally casier than learning 9' + y. which is the goal of the classifier fo), 2) admit a probabilistic interpretation trade-off in BO, yet also 3) be simple
of uncertainty this is key for the enough such that the said mapping can be learned with a small number of queries to fo to preserve sample efficiency. Furthermore, given the combinatorial nature of the graph search space, it also needs to 4) be capable of scaling to large graphs (e.g. in the order of 10 nodes or more) typical of common graph classification tasks with reasonable run-time efficiency. Additionally, given the fact that BO has been predominantly studied in the continuous domain which is significantly different from the present setup, the design of appropriate surrogate is highly non-trivial. To handle this set of conflicting desiderata, we propose to first use a Weisfeiler- extracts a vector space representation of G, followed by a sparse Bayesian linear regression which balances performance with efficiency and gives an probabilistic output.
(WL) feature extractor to
With reference to Fig. given a perturbation graph G' as proposed adversarial sample, the WL feature extractor first extracts a vector representation (gG') in line with the WI. subtree kernel procedure (but without the final kernel computation) [30]. For the case where the node features are discrete, let (u) be the initial node feature of node E V (note that the node features can be either scalars or vectors). we iteratively aggregate and hash the features of u with its neighbours, {u: {
deg(v) using the original WL procedure at all nodes to transform them into discrete labels:
x A+ (v) = hash (z"(v), x² (u1), x (Margto:)) Wh E {0, 10. ---11 1}.
(3)
where H the total number of WL iterations, hyperparameter of the procedure. At each level h, we compute the feature vector (g') = [c(g", ".,), c(g', "h,g", node features z that occur in all input graphs at the current level and c(G", x²) ) is the counting function that counts the number of times a particular node feature xh appears in G'. For the case with continuous node features and/or weighted edges, we instead use the modified WI. procedure proprosed in 36
"' where Xr, is the set of distinct
dog(v)
A ( ( (20())
w(v, u. (u:)). vh E (0, 10 H 1},
(4)
deg(w)
where w(v,, 0z) denotes the (non-negative) weight of edge ((uuu)) (1 if the graph is unweighted) and we simply have feature at level h (g') vec(X,). where X1, is the feature matrix of graph g at level h by collecting the features at each node X,, = (1")1)....a"
and vec(.) denotes the vectorisation operator. In both cases, at the end of WT. iterations we obtain the final feature vector (GG") concat(0 (G"),.., (G') H (G")) for each training graph in [1, ng-]] to form the feature matrix
3

---

Stage i 9n
Stage i ++1
uggma (Cunall (67 (00)))
G
gr AA
g
goimd
gu(tti L
Loss -0.95 Loss = -0.65
Loss -0.73
Loss -0.42
Loss -0.55
Loes
-1.04
Figure 2: Sequential edge selection. At each stage, the BO agent sequentially proposes candidate
graphs with edge edit distance of from the base graph 9 (which is the original unperturbed graph initialisation, or a perturbed graph that led the largest increase in loss from the previous stage otherwise) by selecting the graph that maximises the acquisition function value amongst all candidates generated via sampling/genee procedure repeats until either the attack succeeds (i.e. we find a graph G' with Lattack (fotacc(foog)) (fo(g"), ),y) 0)
algorithm (see details at Optimisation of acquisition function). This
or the maximum number of B queries fo exhausted.
= ( mnge) I E R to be passed to the Bayesian regressor - is particularly
worth noting that the training graphs here denote inputs train the surrogate model of the attack agent and are typically perturbed versions of test graph G of the victim model; they are not the graphs that used to train the victim model itself: in an evasion attack setup, the model is considered frozen and the training inputs cannot be accessed by the attack agent any point in the pipeline. The WL iterations capture both information related to individual nodes and topological information (via neighbourhood aggregation), and have been shown to have comparable distinguishing power to some Graph Neural Network (GNN) models (26), and hence the procedure is expressive. Alternative surrogate choices could be, for example, GNNS with the final fulne-connected layer replaced by a probabilistic linear regression layer such as the one proposed in [31] However, in contrast to these, our extraction process g + ((G") requires no learning from data (we only need to learn the Bayesian linear regression weights) and therefore should lead better sample efficiency. Alternatively, we may also use a Gaussian Process (GP) surrogate, such as the Gaussian Process with Weisfeiler-Lehman Kernel (GPWL) model proposed in [29 that directly uses a GP model together with WL kernel. Nonetheless. while GPs are theoretically more expressive (although we empirically show in App. D.I that in most of the cases their predictive performances are comparable), they are also much more expensive with a cubic scaling w.r.t the number of training inputs. Furthermore, GPWL is designed specifically for neural architecture search, which features small, directed graphs with discrete node features only; on the other hand, the GRABNEL surrogate covers a much wider scope of applications
When we select a large or if there are many training inputs and/or input graph(s) have a large number of nodes/edges, there will likely be many unique WL features and the resulting feature matrix will be very high-dimensional, which would lead to high-variance regression coefficients a being estimated if ngg' (number of graphs to train the surrogate of the attack agent) is comparatively few. To attain a good predictive performance in such a case, we employ Bayesian regression surrogate with the Automatic Relevance Determination (ARD) prior learn the mapping & - Lattack (G' y). which regularises weights and encourages sparsity in a [42]:
Lattack o. a. of N(aa & ID). ox X N' A), diag(A) X-1 = 127 yi A5') A ~ Gamma(k, 0) vi E [1,
(5)
(7)
where A is diagonal covariance matrix. To estimate a and noise variance oi we optimise the model marginal log-likelihood. Overall, the WL routines scales as O (Hm) and Bayesian linear regression has a linear runtime scaling w.r.t. the number of queries; these ensure the surrogate is scalable to both larger graphs and/or large number of graphs, both of which are commonly encountered in graph classification (See App for a detailed empirical runtime analysis).
Sequential perturbation selection In the default structural perturbation setting, given an attack budget of A (i.c. we are allowed to flip up to A edges from G), finding exactly the set of perturbations

---

5A that leads to the largest increase in Lattack entails an combinatorial optimisation over ("A candidates. This is a huge search space that is difficult for the surrogate to learn meaningful patterns in sample-efficient way even for modestly
graphs. To tackle this challenge, we adopt the strategy illustrated in Fig. 2 given the query budget B (i.e. the total number of times we are allowed to query fo for a given 9), we assume B 2 A and amortise B into A stages and focus selecting one edge perturbation at each stage. While this strategy is greedy in the sense that it always commits the perturbation leading to the largest increase in loss at each stage, is worth noting that we do not treat the previously modified edges differently, and the agent can, and does occasionally as we observe empirically, "correct" previous modifications by flipping edges back: this is possible as the effect of edge selection is permutation invariant. Another benefit of this strategy is that it can potentially make full use of the entire attack budget A while remaining parsimonious w.r.t. the amount of perturbation introduced, as it only progresses to the next stage and modifies the G further when it fails to find a successful adversarial example in the current stage.
Optimisation of acquisition function At each Bo iteration, acquisition function a(-) is optimised to select the next point(s) to query the victim model fo. However, commonly used gradient- based optimisers cannot be used on the discrete graph search space; a naïve strategy would be to randomly generate many perturbed graphs, evaluate a all of them, and choose the maximiser(s) to query fe next. While potentially effective on modestly-sized G especially with our sequential selection strategy, this strategy nevertheless discards any known information about the search space.
Inspired by recent advances in BO in non-continuous domains [8] 38), we optimise a via an adapted version of the Genetic algorithm (GA) in [00), which is well-suited for our purpose but is not particularly sample efficient since many evolution cycles could be required for convergence. However, the latter is not serious issue here we only use GA for acquisition optimisation where we only query the surrogate instead of the victim model, a subroutine of bo that does not require sample efficiency. We outline its ingredients below:
Initialisation: While GA typically starts with random sampling in the search space to fill the initial population, in our case we are not totally ignorant about the search space as we could have already queried and observed fo with a few different perturbed graphs G'. A smoothness assumption on the search space would be that if a G' with an edge (u. u) flipped from G led to large Lattack. then another G' with (u, s), s & {u, 2a flipped is more likely to do so too. To reflect this, we fill the initial population by mutating the top-k queried G's leading to the largest Lattack seen so far in the current stage, where for G' with (u, v) flipped from the base graph we 1) randomly choose an end node (u or v) and 2) change that node to another node in the graph except or such that the perturbed edges in all children shares one common end node with the parent.
Evolution: After the initial population is built, we follow the standard evolution routine by evaluating the acquisition function value for each member as its fitness, selecting the top-k performing members as the breeding population and repeating the mutation procedure in initialisation for fixed number of rounds. At termination, we simply query fo with the graph(s) seen so far (i.e. computing the loss in Fig. 2 with the largest acquisition function value(s) seen during GA.
3 Related Works
Adversarial attack on graph-based models There has been an increasing attention in the study of adversarial attacks in the context of GNNS 33 17. One of the earliest models, Nettack, attacks Graph Convolution Network (GCN) node classifier by optimising the attack loss of a surrogate model using greedy algorithm (52). Using simple heuristic, DICE attacks node classifiers by adding edges between nodes of different classes and deleting edges connecting nodes of the same class [41]. However, they cannot be straightforwardly transferred graph classification: for Nettack, unlike node classification tasks, we have no access to training input graphs or labels for the victim model during test time to train similar surrogate in graph classification; for DICE (and also more recent works like (3)). node labels do not exist in graph classification (we only have a single label for the entire graph). We nonetheless acknowledge the other contributions in these works, such as the introduction of constraints to improve imperceptibility. in our experiments in Sec
[10] propose a number of techniques, including RL-S2V, which uses reinforcement learning to attack both node and graph classifiers in a black-box manner, and the GA- GA-based attack, which we adapt into our BO acquisition optimisation. However, [00 primarily focus on the s2v victim model, do not emphasise on sample efficiency, and to train policy that attacks in one-shot manner the test graphs, RL-S2v
First methods that do extend to graph classification include I0 23
5

---

has to query repeatedly on a separate validation set. We empirically compare against it in App. D.2 Another related work ReWatt [23]. which similarly uses reinforcement learning but through rewiring. Compared to both these methods, GRABNEI. does not require an additional validation set and is much more query efficient. Other black-box methods without surrogate models have also been proposed that could be potentially be applied to graph classification: [22) exploit common GNN structural bias to attack node features, while [5] relate graph embedding to graph signal processing and construct tailored attack objectives in different GNNS. In comparison to these works that exploit the characteristics of existing architectures to varying degrees, we argue that the optimisation-base method proposed in the our work is more flexible and agnostic to architecture choices, and should be more generalisable to new architectures. Nonetheless, in cases where some architectural information is available, we believe there could be combinable benefits: for example. the importance scores proposed in [22] could be used as sampling weights as priors to bias GRABNEL towards selecting more vulnerable nodes. We defer detailed investigations of such possibilities
future work. Finally,
there have also been various previous works that focus on a different setup than ours: A white-box optimisation strategy (alternating direction method of multipliers) is proposed in [16]. [48] 44
propose back-door attacks that involve poisoning of the training data before training and/or the test data at inference. (35] attack hierarchical graph pooling networks, but similar to [52) the method
requires access to training input/targets. Ultimately, a number of factors, including but not limited to 1) existence/strictmess of the query budget, 2) strictness of the perturbation budget, 3) attacker capabilities and 4) sizes of the graphs, would decide which algorithm/setup is more appropriate and should be adopted in a problem--pecific way. Nonetheless, we argue that our setup is both challenging and highly significant as it resembles the capabilities a real-life attacker might have (no access to training data; no access to model parameter/gradients and limited query/perturbation budgets).
Adversarial attacks using BO BO as a means to find adversarial examples in the black-box evasion setting has been successfully proposed for classification models on tabular (34] and image data (28] 55 32 22). However, we address the problem for graph classification models, which work on structurally and topologically fundamentally different inputs. This implics several nontrivial challenges that require method go beyond the vanilla usage of BO: for example, the inputs cannot be readily represented as vectors like for tabular or image data and the perturbations that we consider for such inputs are not defined continuous, but discrete domain.
4 Experiments
We validate the performance of the proposed method in a wide range of graph classification tasks with varying graph properties, including but not limited the typical TU datasets considered in previous works [00 (3). As a demonstration of the versatility of the proposed method, instead of considering single mode of attack which is often impossible in real-life, we also select the attack mode specific to each task. All additional details, including the statistics of the datasets used and implementation details of the victim models and attack methods, are presented in App. C
TU Datasets We first conduct experiments on four common TU datasets 25 namely (in ascending order of average graph sizes in the dataset) IMDB- MM, PROTEINS, COLLAB and REDDIT-MULTI-5K In all cases, unless specified otherwise, we define the attack budget A in terms of the maximum structural perturbation ratio defined in 7 where A < rn² We similarly link the maximum numbers queries B allowed for individual graphs to their sizes as B = 402,, thereby giving larger graphs and thus potentially more difficult instances higher attack] and query budgets similar to the conventional image adversarial attack literature [28). In this work, unless otherwise specified we set = 0.03 for all experiments, and for comparison consider number of baselines, including random search, GA introduced in [10 On some task/victim model combinations, we also consider an additional simple gradient- based method which greedily adds delete edges based on the magnitude computed input gradient similar to the gradient based method described in [10] (note that this method is box as access to parameter weights and gradients is required), which is also similar in spirit to methods like Nettack [52]. To verify whether the proposed attack method can be used for a variety of classifier architectures also consider various victim models: we first use GCN (19) and Graph Isomorphism Network (GIN) [45), which are most commonly used in related works 33 Considering
3 'Due to computational constraints, we cap the maximum number of queries to be 2 x 10 on each graph. 'The original implementation of RL- the primary algorithm in [00. primarily focus on a S2V-based victim model [9] We compare GRABNEL against it in the same dataset considered in 10 in App. D.2

---

IM M. GZM
PROTERS-44 4CN
COLLAB-GON
IND8-M-2N
PROTEINS
COLLAB GIV
(15))
scceernn 203
MOUO PE (AUR)
9.2
92
1111
33
GRABNEL
Genetic
Random
Figure 3: ASR against the number of queries to GCN and GIN (normalised by the square of the number of nodes of each graph) Tu datasets. Note the x-axis is on log-scale. Lines and shades denote mean +1 sd across 3 random initialisations. GRADNEL outperforms other attack methods considerably. Random and Genet ic appear to converge faster initially as they always use exploit full perturbation budget allocated, while GRABNEL is parsimonious and only attempts a higher perturbation budget when attacks perturbing fewer edges fail. is also possible to derive a variant of random search with such parsimony, and the readers referred to the detailed ablation studies in App. D.5
Table 1:
Test accuracy of GCN and GIN victim models on the TU datasets before (clean) and after various attack methods. Results shown in mean standard deviation across trials. The results for REDDIT-MULTI-SK are shown in App. D.4
GCN 19
GIN 45
IMDB-M
PROTEINS
COLLAB
IMDB-M
PROTEINS
COLLAB
Clean
50.53 1.4
71.73
79.73
48.85
70.53
80.80 _0.
Random
47.43_1.2
19.4641.7
67.00+a.7
40.44
23.21
73.01 _5.0
Genetic IQ
4..82_1.5
14.88
58.61
39.68
15.47
72.31_2.6
Gradient-based
39.31 :2.2
50.60
36.67
37.56
11.90
54.00
GRABNEL (ours)
45.23_0.2
10.82=2.5
35. 35.38
38.22=3.9
10.72+0.3
57.33_4.7
White-box method
the strong performance of hierarchical models in graph classification [12 46), we also conduct some experiments the Graph- [12) representative of such architectures. We show the classification performance of both victim models before and after attacks using various methods in Table I and we show the Attack Success Rate (ASR) against the (normalised) number of queries in Fig. It is worth noting that consistency with the image attack literature, we launch and consider attacks the graphs that were originally classified correctly, and statistics, such as the ASR, also computed on that basis. We report additional statistics, such as the evolution of the attack losses as a function of number of queries of selected individual data points in App. D.3
The results generally show that the attack method is effective against both GCN and GIN models with GRABNEL typically leading to the largest degradation in victim predictions in all tasks, often performing on par better than Gradient-based, white-box method. It is worth noting that although Gradient-based often performs strongly, there is no guarantee that it always does so: first, for general edge flipping problems, Gradient-based computes gradients w.r.t. all possible edges (including those that do not currently exist) and an accurate estimation of such high dimensional gradients can be highly difficult. Second, gradients only capture local information and they are not necessarily accurate when used to extrapolate function value beyond that neighbourhood. However, relying on gradients select edge perturbations constitutes such an extrapolation, as edge addition/deletion is binary and discrete. Lastly, on the tasks with larger graphs (e.g. COLLAB on GCN and GIN). due to the huge search spaces, we find neither random search nor GA could flip predictions effectively except for some "casy" samples already lying close to the decision boundary; GRABNEL nonethcless performs well thanks to the effective constraint of the search space from the sequential selection of edge perturbation, which is typically more significant on the larger graphs.
We report the results on the Graph U-net victim model in Table 2 as expected, Graph U-net performs better in terms of clean classification accuracy compared to the GCN and GIN models considered above, and it also seem more robust to all types adversarial attacks on the PROTEINS dataset. Nonetheless, in terms of relative performance margin, GRABNEL still outper- forms both baselines considerably, demonstrating the flexibility and capability for it to conduct effective attacks even on the more complicated and realistic victim models.
Table 2: Test accuracy Graph U- net [12] on IMDB-M and PROTEINS before and after attack.
IMDB-M
PROTEINS
Clean Random
56.33
79.46
45.33
75.00
Genetie
10
44.00
75.00
GRABNEL (ours)
41.33
58.80
7

---

1.0
GRABNEL
Attock success rate (ASR)
success rate (ASR)
GRABNEL-A
200
11.8-
Randomtu
0.8
0.6
0.4-
0.2
Base
hop
50-
2-hop
rewire
0.0
10
10-3
1PP
100
0
10
Norm Number queries N/n²
Number queries
Number of perturbations
Figure 4: ASR vs normalised # queries with constraints on GCN model trained on PROTHINS.
Figure 5: ASR vs # queries on a ChebyGIN trained on MNIST- 75sp on targeted and untar- geted attack setups.
Figure 6: Histogram of #edges swapped in success- fully attacked MNIST-75sp instances by GRABNRT-E.
As discussed, in real life, adversarial agents might encounter additional constraints other than the number of queries to the victim model or the amount of perturbation introduced. To demonstrate that our framework can handle such constraints, we further carry out attacks on victim models using identical protocols as above but with a variety of additional constraints considered in several previous works. Specifically, the scenarios considered, in the ascending order of restrictiveness, are:
Base: The base scenario is identical the setup in Table I and Fig
2-hop: Edge addition between nodes (u, v) is only permitted if is within 2-hop distance of u;
2 2-hoptrewire 23 Instead of flipping edges, the adversarial agent is only allowed to rewire from nodes (u, v) (where an edge exists) to (u, w) (where no edge currently exists). Node w must be within 2-hop distance of
We test on the PROTEINS dataset, and show the results in Fig. interestingly, the imposition of the 2-hop constraint itself leads to no worsening of performance - in fact, as we elaborate in Sec. 5 we find the phenomenon of adversarial edges remaining relatively clustered within relatively small neighbourhood is general pattern in many tasks. This implies that the 2-hop condition, which constrains the spatial relations of the adversarial edges, might already hold even without explicit specification, thereby explaining the marginal difference between the base and the 2-hop constrained cases in Fig. 4 While the additional rewiring constraint leads to (slightly) lower attack success rates, the performance of GRABNEL remains relatively robust in all scenarios considered.
Image Classification Beyond the typical "edge flipping" setup on which existing research has been mainly focused, we now consider different setup involving attacks on the 751S dataset 21 20 with weighted graphs with continuous attributes note that The dataset is generated by first partitioning MNIST image into around 75 superpixels with SLIC [ as the graph nodes (with average superpixel intensity as node attributes). The pairwise distances between the superpixels form the edge weights. We use the pre-trained ChebyGIN with attention model released by the original authors (00 (with an average validation classification accuracy of around 95%) the victim model. Given that the edge values are no longer binary, simply flipping the edges (equivalent to setting edge weights to 0 and 1) is no longer appropriate. To generalise the sparse perturbation setup and inspired by edge rewiring studied by previous literature, we instead adopt an attack mode via swapping edges: each perturbation
be defined by 3 end nodes (u, 8) where edge weights wav is swapped with edge weight w/ (u, s). We show the results in Fig. [5] GRABNEI -u and Random-u denotes the GRABNEL and random search under the untargeted attack, respectively, whereas GRABNBL-E
denotes GRABNEL under the targeted attack with each line denoting of the 9 possible target classes in MNIST. We find that GRABNEL surprisingly effective in attacking this victim model, almost completely degrading the victim (Fig. 5) with very few swapping operations (Fig. 6 even in the more challenging targeted setup. This seems to suggest that, least for the data considered, the victim model is very brittle towards carefully crafted edge swapping, with its predictive power seemingly hinged upon a very small number of key edges. We believe a thorough analysis of this phenomenon is of an independent interest, which we defer to a future work.
Fake news detection As final experiment, we consider a real-life task of attacking a GCN- based fake news detector trained on a labelled dataset in [37]. Each discussion cascade (i.e. chain of tweets, replies and retweets) is represented an undirected graph, where each node represents a Twitter account (with node features being the key properties of the ac-
count such age and number of followers/followces; App. C for details) and each edge
8

---

(GCN)
(b) PROTEINS (GCN)
(c) COLLAB (GCN)
(d) Twitter fake news
(e) IMDB-M (GIN)
PROTEINS (GIN)
Figure 7: Adversarial examples found by GRABNEL. Red edges denote deleted edges and green edges indicate added ones. Twitter fake news detection task, green nodes/edges denote the injected nodes and their connections to the existing graphs. Refer to App D.3 for more examples.
represents a reply/retweet. As reflection of what a real-life adversary may and may not do, we note that modifying the connections or properties of the existing nodes, which cor- respond to modifying existing accounts and tweets, is considered impractical and prohibited. Instead, we consider a node injection attack mode (i.e. creating new malicious nodes and connect them to existing ones): injecting nodes equivalent to creating new Twitter accounts and connecting them to the rest of the graph is equivalent retweeting/replying existing accounts. We limit the maximum number of injected nodes to be 0.05.N and the maximum number of new edges that may be created
Attack success rate (ASR)
0.35
0.30
per each new node is set to the average number of edges an existing node has in this context, this limits the number of re-tweets and replies the new accounts may have to avoid easy detection. For the injected node, we initialise its node features in way that reflects the characteristics of a new Twitter user (we outline the detailed way do in App- []. We show the result in Fig. [ where GRABNEL. is capable of reducing the effectiveness of a GCN-based fake news classifier by third. In this case Random also performs reasonably well, as the discussion cascade is typically small, allowing any adversarial examples be exhaustively found eventually.
0.25
GRABNEL
Random
0.20
10"
Norm number queries N/a Figure 8: ASR vs. #queries (normalised by the number of nodes, since the attack in- volves node injection) the Twitter dataset.
Ablation Studies GRABNEL benefits from number of design choices and it is important to understand the relative contribution of each the performance. We find that in some tasks GRABNEL without surrogate (i.e. random search with sequential perturbation selection. We term this variant SequentialRandom) is a very strong baseline in terms of final ASR, although the full GRABNEL is much better in terms of overall performance, sample efficiency and the ability to produce successful examples with few perturbations. The readers are referred to our ablation studies App. D.5
Runtime Analysis Given the setup we consider (sample- efficient black-box attack with minimal amount of perturbation), cost of the algorithm should not only be considered from the viewpoint of the computational runtime of the attack algorithm itself alone, and this is primary reason why we use the (normalised) number of queries as the main cost criterion. Nonetheless, runtime analysis is still informative which we provide in App. D.6 We find that GRABNEL maintains reasonable

---

overhead even on, e.g. graphs with ~ 10 nodes/edges that are larger than most graphs in typical graph classification tasks.
Attack Analysis
Having established the effectiveness of our method, in this section provide qualitative analysis on the common interpretable patterns behind the adversarial samples found, which provides further insights into the robustness of graph classification models against structural attacks. We believe such analysis is especially valuable, as it may facilitate the development of even more effective attack methods, and may provide insights that could be useful for identification of real-life vulnerabilities for more effective defence. We show examples of the adversarial samples in Fig. 7 (and Fig. 13 in
App. D.3) We summarise some key findings below.
Adversarial edges tend to cluster closely together: We find the distribution of the adversarial edges (either removal or addition) in graph to be highly uneven, with many adversarial edges often sharing common end-nodes or having small spatial distance to each other. This is empirically consistent with recent theoretical findings on the stability of spectral graph filters in [8] From an attacker point of view, this may provide a "prior" on the attack to constrain the search space, as the regions around existing perturbations should be exploited more; we leave a practical investigation of the possibility of leveraging this to enhance attack performance to future work.
Adversarial edges often attempt to destroy or modify community structures: for example, the original graphs in the IMDB-M M dataset can be seen to have community structure, a graph-level topological property that is distinct from the existing works analysing attack patterns on node-level When the GCN model is attacked, the attack tends to flip the edges between the communities, and thereby destroying the structure by either merging communities or deleting edges within cluster. On the other hand, the GIN examples tend to strengthen the community structures by adding edges within clusters and deleting edges between them. With similar observations also present in, for example, PROTEINS dataset, this may suggest that the models may be fragile to modification of the community structure.
tasks 44 53
Beware the low-degree rodes! While low-degree nodes are important in terms of degree centrality, we find some victim models are vulnerable to manipulations on such nodes. Most prominently, in the Twitter fake news example, the malicious nodes almost never connect directly the central node (original tweet) but instead to peripheral node. This finding corroborates the theoretical argument in (18) which shows that spectral graph filters are more robust towards edge flipping involving node-level tasks [53] with the explanation being lower-degree nodes having larger influence in the neighbourhood aggregation in GCN. Nonetheless, we note that changes in higher-degree node are likely to cascade to more nodes in the graph than low degree nodes, and since graph classifiers aggregate across all nodes in the readout layer the indirect change of node representations also matter. Therefore, we argue that this phenomenon graph classification still non-trivial.
high-degree nodes than otherwise, and is also consistent with observations
6 Conclusion
Summary This work proposes a novel and flexible black-box method attack graph classifiers using Bayesian optimisation. We demonstrate the effectiveness and query efficiency of the method empirically. Unlike many existing works, we qualitatively analyse the adversarial examples generated. We believe such analysis is important to the understanding of adversarial robustness of graph-based learning models. Finally, we would like point out that a potential negative social impact of our work is that bad actors might use our method to attack real-world systems such as a fake new detection system on social media platforms. Nevertheless, we believe that the experiment in our paper only serves as a proof-of- -of-cceeepttt and the benefit of raising awareness of vulnerabilities of graph classification systems largely outweighs the risk.
Limitations and Future Work Firstly. the current work only considers topological attack, although the surrogate used is also compatible with attack on node/edge features or hybrid attacks. Secondly, while we have evaluated several mainstream victim models, it would also be interesting to explore defences against adversarial attacks and to test GRABNEL robust GNN setups such as those with advanced graph augmentations 47 randomised smoothing [88] K and adversarial detection (6. Lastly, the current work is specific to graph classification; we believe it possible to adapt it to attack other graph tasks by suitably modifying the loss function. We leave these for future works.
10

---

Acknowledgement and Funding Disclosure
The authors would like to acknowledge the following sources of funding in direct support of this work: XW and BR are supported by the Clarendon Scholarship at University of Oxford; HK is supported by the EPSRC Centre for Doctoral Training in Autonomous Intelligent Machines and Systems EP/L015897/1; AB thanks the Konrad-Adenauur-Stttun Quantitative Finance for their support. The authors would also like to thank the Oxford-Man Institute of Quantitative Finance for providing the computing resources necessary for this project. The authors declare no conflict in interests.
and the Dxford-Man Institute of
References
[1] Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels compared to state-of-the-art superpixel methods. IEEE transactions on pattern analysis and machine intelligence, (4(11))2274-228, 2012.
[2] Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. In International Conference on Machine Learning, pages 695-704. PMLR, 2019.
[3] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions Knowledge Data Engineering. 3009):661-16333
2018.
[4] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In
2017 ieee symposium on security and privacy (sp), pages 39-57. IEEE, 2017.
[5] Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. A restricted black-box adversarial framework towards attacking graph embedding models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3389-3396, 2020.
[6] Jinyin Chen, Huiling Xu, Jinhuan Wang. Qi Xuan, and Xuhong Zhang. Adversarial detection on graph structured data. In Proceedings of the 2020 Workshop Privacy-Preservin Machine Learning in Practice, pages 37-41, 2020.
[7] Jinyin Chen, Dunjie Zhang, Zhaoyan Ming, and Kejie Huang. Graphattacker: general multi-task graphattack framework. arXiv preprint arXiv:2101.0688 2021.
[8] Alexander Nowen-Rivers, Wenlong Lyu, Zhi Wang, Rasul Tutunov, Hao Jianye, Jun Wang, and Haitham Bou Ammar. Hebo: Heteroscedastic evolutionary bayesian optimisation. arXiv preprint arXiv:2012.03886 2020.
[9] Hanjun Dai, Bo Dai, and Le Song. Diseriminative embeddings of latent variable models for structured data. In International conference on machine learning, pages 2702-2711. PMLR, 2016.
[10] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference on machine learning, pages 1115-1124. PMLR, 2018
[11] Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv, 2020.
[12] Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pages 2083-2092. PMLR, 2019.
[13] Zhidong Gao, Rui Hu, and Yanmin Gong. Certified robustness of graph classification against topology attack with randomized smoothing. GLOBECOM 2020-2020 IEEE Global Commu- nications Conference, pages 1-6. IEEE, 2020.
[14] William L Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159, 2020.
[15] Zhichao Huang, Yaowei Huang, and Tong Zhang. Corrattack: Black-box adversarial attack with structured search. arXiv preprint arXiv:2010.01550, 2020.
[16] Hongwei Jin, Zhan Shi, Venkata Jaya Shankar Ashish Peruri, and Xinhua Zhang. Certified robustness of graph convolution networks for graph classification under topological attacks. Advances in Neural Information Processing Systems, 33, 2020.

---

[17] Wei Jin, Yaxin Li. Han Xu, Yiqi Wang, and Jiliang Tang. Adversarial attacks and defenses on graphs: A review and empirical study. arXiv preprint arXiv:2003.00653, 2020.
[18] Henry Kenlay, Dorina Thanou, and Xiaowen Dong. Interpretable stability bounds for spectral graph filters. In International conference machine learning, 2021.
[19] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[20] Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer. Understanding attention and generalization in graph neural networks. NeurIPS, 2019.
[21] Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, (44):541-554) 1989.
[22] Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks on graph neural networks. Advances in Neural Information Processing Systems 33, 2020.
[23] Yao Ma, Suhang Wang. Tyler Derr, Lingfei Wu, and Jiliang Tang. Attacking graph convolutional networks via rewiring. arXiv preprint urXiv:1196. 03750, 2019.
[24] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
[25] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.0866. 2020.
[26] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings the AAAI Conference on Artificial Intelligence, volume 33, pages 4602 4609,4609,2200 2019.
[27] Luis Systems. PhD thesis, Imperial College London, 2017.
Bayesian Optimization for Black-Box Evasion of Machine Learning
[28] Binxin Ru, Adam Cobb, Amo Blaas, and Yarin Gal. Bayesopt adversarial attack. In International Conference Learning Representations, 2020.
[29] Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Osborne. Interpretable neural architec- ture search via bayesian optimisation with weisfeiler- kernels. International Conference on Learning Representations (ICLR), 2021.
[30] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-Iehme graph kernels. Journal of Machine Learning Research, 12(9),
2011.
[31] Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James T Kwok, and Tong Zhang. Bridging the gap between sample-based and one-shot neural architecture search with bonas. Advances in Neural Information Processing Systems 33, 2020.
[32] Satya Narayan Shukla, Anit Kumar Sahu, Devin Willmott, and Zico Kolter. Black-box adversarial attacks with bayesian optimization. arXiv preprint arXiv: 13857, 2019.
[33] Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S Yu, Lifang He, and Bo Li. Adversarial attack and defense on graph data: A survey, arXiv preprint arXiv:1812.10555 2018
[34] Fnu Suya, Yuan Tian, David Evans, and Paolo Papotti. Query-limited black-box attacks to classifiers. NIPS Workshop. 2017.
[35] Haoteng Tang, Guixiang Ma, Yurong Chen, Lei Guo, Wei Wang, Bo Zeng, and Liang Zhan. Ad- versarial attack on hierarchical graph pooling neural networks. arXiv preprint vrXiv:2055.11560 2020.
[36] Matteo Togninalli, Elisabetta Ghisu, Felipe Lóéna, Bastian Rieck, and Karsten Borg- wardt. Wasserstein weisneil graph kernels. arXiv preprint arXiv: 1906.912777 2019.
[37] Soroush Vosoughi, Deb Roy, and Sinan Aral. The spread of true and false news online, Science 35966380::1146111 2018.
12

---

[38] Xingchen Wan, Vu Nguyen, Huong Ha, Binxin Ru, Cong Lu, and Michael A Osborn,. Think global and act local: Bayesian optimisation over high -igh-iimessional categorical and mixed search spaces. International Conference on Machine Learning (ICML), 2021.
[39] Binghui Wang, Tianxiang Zhou, Minhua Lin, Pan Zhou, Ang Li, Meng Pang, Cai Fu, Hai Li, and Yiran Chen. Evasion attacks graph neural networks via influence function. arXiv preprint 07Xiv:200.000203, 2020.
[40] Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint 190.v0 2019.
[41] Marcin Waniek, Tomasz Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, 2(2):139-147, 2018.
[42] David P Wipf, Srikantan S Nagarajan, J Platt, D Koller, and Y Singer. A new view of automatic relevance determination. In NIPS, pages 1625-1632, 2007.
[43] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Ad- versarial examples on graph data: Deep insights into attack and defense. arXiv preprint arXiv:1903.01610 2019.
[44] Jing Xu, Stjepan Picek, et al. Explainability-bat backdoor attacks against graph neural networks. arXiv preprint arXiv:2104.03674, 2021.
[45] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[46] Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in Neural Information Processing Systems (NeurIPS), 2018.
[47] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing 33:5812 5823, 2020.
[48] Zaixi Zhang, Jinyuan Jia, Binghui Wang, and Neil Zhenqiang Gong. Backdoor attacks to graph neural networks. arXiv preprint arXiv:2006. 165, 2020.
[49] Zhuosheng Zhang and Shucheng Yu. Bo-dba: Query-efficient decision- based adversarial attacks via bayesian optimization. arXiv preprint arXiv:2106 027322, 2021.
[50] Pu Zhao, Sijia Liu, Pin-Yu Yu Chen, Nghia Hoang, Kaidi Xu, Bhavya Kailkhura, and Xue Lin. On the design of black- adversarial examples by leveraging gradient-free optimization and operator splitting method. In Proceedings of the IÉEE International Conference on Computer Vision, pages 121-130. 2019.
[51] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang. Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AI Open, 1:57-81, 2020.
[52] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2847-2856, 2018.
[53] Daniel Züggerr, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on graph neural networks: Perturbations and their patterns. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-31,203)
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and the Appendix
(c) Did you report error bars (e.g.. with respect to the random seed after running exper- iments multiple times)? [Yes] We report error bars on all the experiments involving multiple trials Section 4
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See the Appendix
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you's rou're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "nyq1lN_Dpf", "reviewer": "Reviewer_qDG8", "summary": "The authors propose an adversarial attack method for graph classification models. Specifically, the method is based on Bayesian optimization and uses a genetic algorithm (GA) as the acquisition function and a Bayesian linear regression surrogate model which provides the fitness scoring for the GA. The approach is greedy in the sense that it selects the best perturbation in a stage and then proceeds to the next one. The authors evaluate their method on a set of standard graph classification datasets (\"TU Datasets\") as well as on a graph version of MNIST and on a Twitter dataset. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-structured and the presentation is clear. The method seems novel, though Bayesian Optimization and graph classification attacks are not my core field of expertise. Overall I am not opposed to publication as the results appear to be stronger than the baselines.\n\nNevertheless I do have some concerns / questions:\n* What is the empirical runtime of the attack? Since the method performs a GA for **each** graph in a dataset, it seems to be quite expensive.\n* Another main concern is that the authors do not evaluate any defenses. While there may not be many defenses for graph classification attacks, I would expect that defenses for node classification (e.g., [Zhang and Zitnik 2020], [Geisler et al. 2020]) could improve robustness.\n* In many of the result figures, it seems that the proposed approach performs worse than random for a small number of queries. What is the reason for this and how can it be addressed? It would also be interesting to list the \"break-even\" number of perturbations per dataset evaluated.\n* How is the second requirement of the surrogate model (probabilistic interpretation of uncertainty) used in the present work? \n* On a related note, what is the performance of the model when using a standard $L_1$- or $L_2$-regularized linear regression surrogate model?\n* Why does Table 1 show validation and not test accuracy?\n* Are the initialization points counted towards the global budget $B$? In Algorithm 1 it seems like they are not counted towards $B$, which would be counterintuitive.\n* Why are there no results for Cheby-GIN in Table 1?\n* Why does the gradient-based baseline perform much worse than random on PROTEINS?\n* How to adjust the surrogate model for injected nodes? From the description I understand that injecting a node can lead to a longer vector representation of the graph (i.e., more entries). Therefore, the number of parameters $\\alpha$ and $\\lambda$ of the surrogate model do not fit the graph representation any more. How is this resolved?\n* For the case of continuous node features, it seems like the resulting feature vectors can be very high-dimensional ($H\\cdot D \\cdot N$), where $D$ is the feature dimension. Does this pose a problem of the method for large graphs?\n* Remark about the \"Beware the low-degree nodes!\" point. Since on Twitter the victim model is a GCN, this comes as no surprise: the weight in the neighborhood aggregation of node $j$ is proportional to $\\frac{1}{\\sqrt{d_j}}$, i.e., lower-degree neighbors have larger influence in the neighborhood aggregation in GCN. This was also discussed by Zügner et al. (TKDD 2020).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do have a short section on limitations. In the case that the empirical runtime is very large, I recommend to list this also as a limitation of the approach.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dGjCKPihtr", "reviewer": "Reviewer_twfu", "summary": "The paper proposes GRABNEL, which formulates the adversarial attack on graph classification as a black-box optimisation problem and uses Bayesian optimisation to solve it. Experiments on multiple datasets demonstrate the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The technical contribution is incremental, which heavily limits the significance of the proposed method. To be specific, Weisfeiler-Lehman (WL) feature extraction methods and Bayesian optimization (BO) are well-known techniques, and the combination of them in this work is straightforward.\n\nQuality: The proposed method is well motivated and is technically sound. Although the attack analysis part provides some insights into the robustness of graph classification models, the last two claims are not well supported by empirical verification.\n\nClarity: The paper is well organized and articulated in general. \n\nSignificance: The comparison experiments are not convincing. The authors are encouraged to compare the proposed method with more recent SOTA methods, rather than one method that was published in 2018, on more benchmarks, e.g., AIDS, DHFR or Bitcoin. Besides, for the image classification and Fake news detection tasks, it will be more convincing to report the results of other competitive methods.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One limitation of this work is that the proposed method is only applicable for graph classification models. The authors claim that some progress will be made in future work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "bUMJzg-Am8c", "reviewer": "Reviewer_yB9K", "summary": "This paper proposes a query-efficient and parsimonious attack method for graph classification models based on Bayesian optimization. Attacks are performed under the black-box evasion setting by flipping or rewiring edges and injecting nodes. Besides, the authors provide insights between topological properties of perturbed graphs and graph classification models. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- Both the problem of adversarial attacks on graph classification and attack modes of rewiring edges as well as node injection is rarely researched, which shows the novelty of this work.\n- The experimental results are strong. Various domains of datasets are used and different attacking strategies are exploited in the experiment. \n- The attack analysis of the relationship between robustness and topological patterns of adversarial samples is interesting and could provide insights for further graph robustness research.\n\nWeakness:\n-\tThe black-box setting used in this work falls into the approach with a specific surrogate model. There are several works considering the black-box setting without a surrogate model, such as [1-3]. Though their focuses are on the node classification side, the relationship with this line of research is suggested to be discussed either. \n-\tThe computation analysis of the total attack process should be demonstrated. The authors only provide the complexity of the surrogate model and neglect that of sequential perturbation selection and acquisition function optimization. The complexity analysis is crucial when using large-scale graphs as one strong motivation from authors to choose a proper surrogate model. Further, it would be better if the running time analysis is provided.\n-\tFor the experimental results, why there is no comparison between RL-S2V and GRABNEL on real-world datasets? Meanwhile, the advantage of GRABNEL over RL-S2V is not strong enough on the ER graphs.\n-\tIf possible, I would suggest exploiting additional hierarchical graph classification models in experiments. GCN and GIN are strong classic graph classification models but two victims are kind of weak, especially considering GCN is not very powerful for graph classification tasks. Therefore, other SOTA hierarchical models like DIFFPOOL[4] and G-U-Nets[5] which are also essential parts for graph classification tasks are suggested to be selected as targets.\n\n[1] Towards More Practical Adversarial Attacks on Graph Neural Networks, NeurIPS 2020\n\n[2] Adversarial Attacks on Node Embeddings via Graph Poisoning, ICML 2019\n\n[3] A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models, AAAI 2020\n\n[4] Hierarchical graph representation learning with differentiable pooling, NeurIPS 2018\n\n[5] Graph u-nets, ICML 2019\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and potential negative societal impact are discussed in the Conclusion, though not adequately which could be due to the space limitation.\n\nThe authors are suggested to further describe both of the limitations and social impact from multiple perspectives more in details, such as the user privacy issue when evaluating on the real-world Twitter dataset.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8h"}, "extra_text": {}}, {"review_id": "B3LtRa7PmYU", "reviewer": "Reviewer_FuZ8", "summary": "** I have checked the author feedback **\n\nThis paper studies adversarial attacks to graphs and proposes ‚black-box‘ Bayesian optimization (BO) to find harmful perturbations. Moreover, the authors analyze the properties of adversarial examples to increase understanding of the topology of attacked graphs.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n1) The usage of BO to attack graph classification models is new. Though, BO has been used on black-box attacks before in the image domain. \n\n2) A new challenge with the application of BO on graphs is discreteness which is handled through the encoding through WL feature extraction. However, it would have been beneficial to investigate in more detail the effect of this feature extraction (e.g. how does the approach perform with other features?)\n\nQuality:\n1) The paper only evaluates the approach empirically. However, the evaluation could be more comprehensive. The authors could include more baselines to compare to (e.g. Nettack). The baseline GA is also used as a component of the proposed technique, and the „white-box“-method is difficult to compare to. Also, the Sequential Random in Fig. 12 in the App. F should be evaluated in more detail. In particular, there it is performing on par with the proposed approach. Furthermore, it would be interesting to see how the approach performs 2-hop and 2-hop + rewire experiments compared to the baselines.\n\n2) All empiric results are evaluated over the number of queries. An additional runtime comparison would be interesting as another metric. In general, I feel that it would be beneficial to discuss more carefully the comparison (e.g. the white-box attack is not using any query budget at all; however, requires access to the parameters; is such a comparison fair?). Potentially it would be helpful to include more baselines which require/use the same set-up (this is partially done in App. F; but as discussed above not really in detail).\n\n3) The attack analysis is highly beneficial. However, it could be improved through the evaluation of statistics. Currently, it is unclear how many samples were evaluated. Also, it would be great if the analysis would include different approaches as a comparison to see if there is a difference between what the proposed approach attacks compared to a baseline and what makes it more successful. Moreover, analysis of the patterns of attacks have been performed in other work which should be discussed be the authors (e.g. \"Wu H, Wang C, Tyshetskiy Y, Docherty A, Lu K, Zhu L (2019) Adversarial examples for graph data: Deep insights into attack and defense\" and \"Zugner D, Borchert O, Akbarnejad A, Gunnemann S (2020) Adversarial attacks on graph neural networks: Perturbations and their patterns\")\n\n\n\n\nClarity:\n1) The paper has a good structure, is well written, and good to follow.\n\n2) It seems to be counterintuitive why Nettack is not chosen as a baseline when it is discussed the most in related work.\n\n3) Fig. 5 should be clarified: how many edges are on the graph, what dataset it is etc. \n\nSignificance:\n1) With a more extensive study on the attack analysis including a discussion of existing works as well as a couple of stronger attack baselines (see point above) this work could add significant insights into the domain of graph classification attacks. \n2) The application of BO on graph classification in combination with the analysis adds the opportunity of using more informed strategies (as briefly highlighted in Appendix G, constraining the search space)\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1) Limitations are not really discussed. Especially the strong baseline sequential random should be discussed in the main paper. With respect to the runtime, an argument could be made that sequential random could be better in some cases. However, the opportunity to use more informed decisions within the framework of the proposed approach would still make it interesting. This would make the limitation discussion sounder. \n\n2) Clearly, the attack has a potential negative impact, especially on the Twitter environment. But this point is discussed, and new defenses are said to be future work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "--", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a new Bayesian Optimization approach to developing adversarial attacks on graphs. While some prior work has used a similar approach for other domains (e.g., images), it seems that the authors are the first to develop a successful attack methods for graphs in this way. The reviewers felt that the experiments were mostly thorough and at least were convinced about the contributions of this paper. Moreover, there was a lot of discussion, but the reviewers seem to have reached consensus with the authors on the major issues. Therefore, I recommend acceptance of this paper. 

Given the lengthy discussion, I would strongly encourage the authors to be thoughtful and thorough in the revision for the next version of the paper. It seems that many of the reviewer concerns can be directly addressed in the paper by improving the writing and exposition. 
Decision: Accept (Poster)