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..oo...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--rtttt 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 Lattack (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", ".,), 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
c(g', "h,g", "' 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(0r (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 & AD). 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 lask/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 M5IST-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-hoptrewize 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- cof-ccceepttt 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, 34(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-basee 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": "xYp4otvHRfh", "reviewer": "Reviewer_FwkT", "summary": "The paper addresses the task of designing adversarial attacks that perturb the structure of a graph to induce errors in graph classification. The approach is based on Bayesian optimization – the authors employ a surrogate model that couples a WL feature extractor with sparse Bayesian linear regression to learn a model of the attack loss. The algorithm operates in the black-box evasion setting, and aims to limit the number of queries to the model. A genetic algorithm is employed to derive graph proposals which are subsequently evaluated using the learned surrogate model. Numerical experiments demonstrate that the proposed method outperforms the best existing methods and significantly reduces the number of required model queries", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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-written and for the most part, the algorithm is clearly described. \n\nIt is always difficult to manage space constraints, but I thought there could have been more information included in the actual paper about the WL feature extractor. The paper also seems to rush through the Bayesian optimization component of the algorithm (for example, the use of EI is mentioned only parenthetically and there is no justification of this choice). Since this is a focus of the contribution, I feel more description could have been allocated to it. For example, considerable space is devoted to the genetic algorithm and this seems to have been borrowed directly from [7] – the authors don’t highlight the modifications they have made.   \n\nStrengths:\n\n(1) The paper provides a novel adversarial attack procedure. The approach is well-motivated and clearly described and there is an innovative combination of methods to improve performance.\n\n(2) Numerical experiments demonstrate that the developed approach outperforms existing methods for some victim models.\n\nWeaknesses:\n\n(1) Novelty: Overall I believe there is sufficient novelty to warrant acceptance. To the best of my knowledge this is the first application of Bayesian optimization for adversarial attacks on graph data, so that is a positive. On the other hand, most of the ingredients used in the algorithm are relatively minor adaptations of previous work. For example, the Bayesian optimization to search over graphs in [23] is closely related to the core of the technique presented in this paper, and while the adaptation from (Gaussian process + WL kernel) to (WL feature extractor plus linear regression) is important to reduce computation time, it is not a major innovation. The algorithm also employs (a variant) of the genetic algorithm from [7] to generate graph proposals. So the paper consists of combinations and adaptations of existing methods to address a problem that has not received a significant amount of attention.  \n\n(2) The paper only considers GCN and GIN as the victim models (and ChebyGIN). These are far from the state-of-the-art in terms of graph classification. The authors do not really explain why they have only explored these graph models. It leads to concerns that the results may not carry over to the improved methods.\n\n(3) The authors do not examine the efficacy of the approach for settings where robust GNNs are used (eg. [R1], but there are multiple others). Many of these robust GNNs involve training over perturbations of the observed graphs. This may well substantially reduce how effective the proposed method is.  \n\n(4) The authors do not discuss or explore the possibility of some form of adversarial defence. Although most of the proposed defences do not target the black-box, evasion setting, something like the GCN-Jaccard defence in [R2], which just pre-processes the graph, removing dubious edges, could easily be adapted to the setting. \n\nIn general, when reading a paper that proposes attacks, one expects to see (i) an investigation of the efficacy with respect to multiple victim models; (ii) a discussion and exploration of the effectiveness against robust models; (iii) a discussion and exploration of the ability to navigate existing defences (or if they do not exist, baseline defences that are simple to propose).  \n\n[R1] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. 2020. Graph Structure Learning for Robust Graph Neural Networks. In Proc. ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '20). \n\n[R2] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: Deep insights into attack and defense. In International Joint Conference on Artificial Intelligence, IJCAI, pp. 4816–4823, 2019. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed  the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "sRBu1oW3VCI", "reviewer": "Reviewer_8giU", "summary": "In this paper, the authors propose GRABNEL, a black-box adversarial attack against graph-level classifiers. The intuition is that by leveraging Bayesian Optimization(BO) techniques, one can reduce the number of queries needed. The authors propose to use a Weisfeiler-Lehman (WL) feature extractor to extract vector representations of the input graphs. After that, a Sparse Bayesian linear regression surrogate model is used to approximate the adversarial loss. The query budget is divided into different stages. For each stage, the attacker modifies the graphs and queries the target model before it runs out of query budget. The modified graphs, as well as the observed predictions, are fed into a genetic algorithm to generate the perturbation for the current stage. After that, the attacker queries the target model and updates the surrogate model accordingly. Experiments show that the proposed approach achieves a higher success rate than the baselines.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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- The idea of introducing BO to the graph adversarial attacks is interesting\n- The authors provide a detailed analysis\n\n## Comments\n\nThe proposed approach achieves a higher success rate than the baselines and the idea of introducing BO to the graph adversarial attacks is interesting. However, there're some concerns about the paper.\n\nSparse Bayesian linear regression models are used to estimate the adversarial loss of the target model. However, the details of these models are unclear. For example, what's the architecture of these models? How do they interact with other parts of the algorithm? The paper will be more concrete if the authors could provide these details. Besides, I think it is better to introduce Bayesian Optimization as background knowledge, as it will make the paper more comprehensive\n\nInstead of training a separate shadow model, the proposed approach uses a Sparse Bayesian linear regression surrogate model to approximate the adversarial loss. Since the approximation is done for a particular input sample, this process has to be repeated if the attacker wishes to generate more adversarial samples. This leads to the question that if the proposed approach is computationally efficient. It will be better if the authors could elaborate on this.\n\nSome inconsistencies found in the paper:\n- No reference to Fig.6 is found.\n- 'implementation details... are presented in App. C' (Line 211), which should be in App. D\n- 'In fact, as we elaborate in Sec. 6 ..'(Line 247), which should be in Sec.5   ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "## Weaknesses\n- The details of the proposed approach is not clear, see the comments for more information\n- The efficiency of the proposed approach is unclear", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "li_RARd82h", "reviewer": "Reviewer_PcFP", "summary": "The paper studies adversarial attacks to graph neural networks for graph classification. The authors design a Bayesian optimization-based attack that is black-box, query-efficient, and parsimonious with respect to the perturbation. The proposed attack is evaluated on three benchmark graph datasets and shows its effectiveness. \n  \nStrengths\n+ The studied problem is important \n+ The proposed attack is evaluated on multiple application domains\n+ Attack analysis is interesting\n\nWeaknesses\n- Novelty is unclear\n- The proposed attack is hard to follow \n- Evaluation is insufficient\n- Missing important references \n- No discussion on defense", "questions": "", "limitations": "", "rating": 5, "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": "The flowchart of the proposed bayesian optimization-based attack is unclear to me.  I suggest the authors add an overview to high-level show the motivation and the attack flowchart.  \n\nAs I do not fully understand the motivation and details of the attack, I also cannot quite catch the key contributions. For example, why the proposed bayesian optimization is suitable for attacking GNNs?   \n\nWhy GRABNEL outperforms white-box gradient-based attack? Why gradient-based attack performs poorly on PROTEINS with GCN, while performing the best on the other datasets?  \nGRABNEL and random attack obtain comparable attack performance against fake news detector. This may reveal that GRABNEL is not effective enough. \n\nLack of comparison with (2) and (3)\n\n\nThe authors should cite and discuss the following references on adversarial attacks to graphs/graph neural networks \n\n\n(1) Attacking Graph-based Classification via Manipulating the Graph Structure\n\n(2) Black-box adversarial attacks on graph neural networks with limited node access\n\n(3) Node injection attacks on graphs via reinforcement learning\n\n(4) Indirect Adversarial Attacks via Poisoning Neighbors for Graph Convolutional Networks\n\n(5) Evasion Attacks to Graph Neural Networks via Influence Function\n\n(6) Adversarial examples on graph data: Deep insights into attack and defense\n\n(7) Topology attack and defense for graph neural networks: An optimization perspective\n\n\nThe authors also lack of discussion of defenses against adversarial attacks to graph neural networks.  \n\n\nOther comments: \n[17] is not a reinforcement learning-based techniques\n\na appropriate surrogate => an appropriate surrogate \n\n“we note that modifying ...., which correspond to modifying existing accounts  and tweets, is considered impractical and prohibited.” => I do not think this claim is correct. \n\nSuggestions:\n-Add an overview to well motivate the proposed attack\n-Make the contributions more clear\n-Compare with the existing attacks\n-Discussion on defenses \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "4HncdD-lsNg", "reviewer": "Reviewer_Jxr4", "summary": "A very similar version has been accepted into the ICML 2021 Workshop, probably from the same authors. See the link https://openreview.net/forum?id=7oziDfK4Fs for details. Hence, I have to reject this paper, due to the duplicate submission. ", "questions": "", "limitations": "", "rating": 2, "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": "A very similar version has been accepted into the ICML 2021 Workshop, probably from the same authors. See the link https://openreview.net/forum?id=7oziDfK4Fs for details. Hence, I have to reject this paper, due to the duplicate submission. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A very similar version has been accepted into the ICML 2021 Workshop, probably from the same authors. See the link https://openreview.net/forum?id=7oziDfK4Fs for details. Hence, I have to reject this paper, due to the duplicate submission. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "45 mins"}, "extra_text": {"ethical_concerns": "A very similar version has been accepted into the ICML 2021 Workshop, probably from the same authors. See the link https://openreview.net/forum?id=7oziDfK4Fs for details. Hence, I have to reject this paper, due to the duplicate submission. "}}]

Author rebuttal:

Meta-review: The reviewers found the exploration of victim models too limited, and experiments should include at least one or two of the state-of-the-art models in the experiments.  Many of the more recent techniques include training with perturbations to the graph structure, and it doesn't seem as if one can say with confidence, without experimental support, that performance improvements with GCN and GIN as victim models will carry over to recent methods.

Please also take into consideration the revised review which cites several relevant papers that address graph classifications
Decision: Accept (Poster)