Near-Black-Box Adversarial Attacks on Graph Neural Networks as An Influence Maximization Problem
Authors: Jiaqi Ma
Junwei Deng
Qiaozhu Mei
Venue:  (2021)
Keywords: Graph Neural Network
Adversarial Attack
Influence Maximization

Abstract: Graph neural networks (GNNs) have attracted increasing interests. With broad deployments of GNNs in real-world applications, there is an urgent need for understanding the robustness of GNNs under adversarial attacks, especially in realistic setups. In this work, we study the problem of attacking GNNs in a restricted near-black-box setup, by perturbing the features of a small set of nodes,  with no access to model parameters and model predictions. Our formal analysis draws a connection between this type of attacks and an influence maximization problem on the graph. This connection not only enhances our understanding on the problem of adversarial attack on GNNs, but also allows us to propose a group of effective near-black-box attack strategies. Our experiments verify that the proposed strategies significantly degrade the performance of three popular GNN models and outperform baseline adversarial attack strategies. 

Under review as a conference paper at ICLR 2021
NEAR-BLACK-BE ADVERSARIAL ATTACKS ON GRAPH NEURAL NETWORKS AS AN INFLUENCE MAX- IMIZATION PROBLEM
Anonymous authors Paper under double-bling blind review
ABSTRACT
Graph neural networks (GNNs) have attracted increasing interests. With broad deployments of GNNs in real-world applications, there is an urgent need for un- derstanding the robustness of GNNs under adversarial attacks, especially in real- istic setups. this work, we study the problem attacking GNNs a restricted near-black-bog setup, by perturbing the features of a small set of nodes, with no access to model parameters and model predictions. Our formal analysis draws a connection between this type of attacks and an influence maximization problem on the graph. This connection not only enhances our understanding the prob- lem of adversarial attack on GNNs, but also allows to propose group of ef- fective near-ble Saar-black-aae black-box attack strategies. Our experiments verify that the proposed strategies significantly degrade the performance of three popular GNN models and outperform baseline adversarial attack strategies.
INTRODUCTION
There has been surge of research interest recently in graph neural networks (GNNs) (Wu al., 2020), a family of deep learning models on graphs, as they have achieved superior performance on various tasks such traffic forecasting Yu al. (017), social network analysis (Li et al. 2017). and recommender systems (Ying et al. 2018 Fan et al. 2019). Given the successful applications of GNNs online Web services, there are increasing concerns regarding the robustness of GNNs under adversarial attacks, especially in realistic scenarios. In addition, the research about adver- sarial attacks on GNNs in turns helps us better understand the intrinsic properties of existing GNN models. Indeed, there have been a line of research investigating various adversarial attack sce- narios for GNNs Zügger et al.) & Günnemann] 2018, Ma et al. 2020). and many of them have been shown to be, unfortunately, vulnerable in these scenarios. In particular, Ma et al. (2020) examine an extremely restricted near- black-box attack scenario where the attacker has access neither model parameters nor model predictions, yet they demonstrate that a greedy adversarial attack strategy can significantly degrade GNN performance due the natural inductive biases of GNN binding to the graph structure. This scenario is motivated by real-world GNN applications on social networks, where attackers are only able to manipulate a limited number of user accounts, and they have no access the GNN model parameters or predictions for the majority of users.
2018. Zügner & Günnemann 2019; Dai et al.] 2018 [Bojchevski]
In this work, we study adversarial attacks on GNNs under the aforementioned near-black-box sce- nario. Specifically, an attack in this scenario is decomposed into two steps: 1) select a small set of nodes to be perturbed: 2) alter the node features according domain knowledge up per- node budget. The focus of the study lies on the node selection step, so as in Ma et al. (020). The existing attack strategies, although empirically effective, are largely based on heuristies (Ma et al., 2020). We instead formulate the adversarial attack as an optimization problem to maximize the mis-classification rate over the selected set nodes, and we carry out formal analysis regarding this optimization problem. The proposed optimization problem is combinatorial and seems hard to solve in its original form. In addition, the caassssssiiiittonn rate objective involves model parame- ters which unknown in the near-black-bor setup. We mitigate these difficulties by rewriting the problem and connecting it with influence maximization on a special linear threshold model related to the original graph structure. Inspired by this connection, we show that, under certain distribu-

---

Under review as a conference paper at ICLR 2021
tional assumptions about the GNN, the expected missclassification rate is submodular with respect to the selected set of nodes to perturb. The expected clissiaasifiiatoon rate is independent of the model parameters and can be efficiently optimized by greedy algorithm thanks to its submodular- ity. Therefore, by specifying concrete distributions, we are able to derive a group of near-black-box attack strategies maximizing the expected mis-classification rate. The connection with influence maximization also provides us nice interpretations regarding the problem of adversarial attack on GNNs.
To empirically verify the effectiveness of the theory, we implement two near-black-box adver- sarial attack strategies and test them on three popular GNN models, Graph Convoluntioal Net- work (GCN) (Kipf & Welling, 2016), Graph Attention Network (GAT) (Veličković et al. 2018). and Jumping Knowledge Network (JKNet) (Xu et al. 2018) with common benchmark datasets. Both attack strategies significantly outperform baseline attack strategies in terms of decreasing model aceuracy. Finally, we summarize the contributions of our study as follows.
1. We formulate the problem of adversarial attack on GNNs as an optimization problem to maximize the mis-classification rate.
2. We draw a novel connection between the problem of adversarial attacks on GNNs and in- fluence maximization based on linear threshold model. This connection helps us develop effective and efficient bear-black-Ba -box adversarial attack strategies and provides interpreta- tions regarding the adversarial attack problem.
3. We implement two variants of the proposed wear-black-bor attack strategies and empiri- cally demonstrate their effectiveness.
2 RELATED WORK
There has been increasing research interest in adversarial attacks on GNNs recently. Detailed ex- positions of existing literature made available in couple of survey papers (Jin al,, 2020, Sun et al., 2018). Given the heterogeneous nature of diverse graph structured data, there are nu- merous ad adversarial attack setups for GNN models. Following the taxonomy provided by JJin et al. (2020), the adversarial attack setup can be categorized based on (but not limited to) the machine learning task, the goal of the attack, the phase of the attack, the form of the attack, and the model knowledge that attacker has access to. First, there are two common types of tasks, node-level classi- fication Zügner et al., 2018 Dai et al. 20188] Wu et al. 2019 Entezari al. 2020) and graph-level classification (Tang et al. 2020 Dai et al. 2018). The goal of the attack can be changing the pre- dictions of a small and specific set of nodes (targeted attack) (Zügner et al. 2018 Dai et al. (018)) or degrading the overall GNN performance (untargeted attack) (Zügner & Günnemann 2019) Sun al., 2019). The attack can happen at the model training phases (poisoning attack) (Zügner & Günnemann 2019 Sun et al. 2019) after training completes (evasion attack) (Dai et al.) [0188]
Chang et al.) 2020 The form of the attack could be perturbing the node features (Zügner et al, 2018 Ma al.. (020)) altering the graph topology (Dai et al., 2018, [un et al. 2019). Hinally, depending on the knowledge (e.g. model parameters, model predictions, features, and labels, etc.) the attacker has access to, the attacks can be roughly categorized into white-box attacks (Xu al.) 2019), grey-box attacks (Zügner et al. 2018 (Snn et al. 2019),, black-box attacks (Dai et al.) 2018 Chang et al. 2020) or near-black-box (Ma et al. 2020). However, is worth noting that the borders of these three categories are blurry in literature.
The setup of interest in this paper can be categorized as node-level, untargeted, evasional, and near- black-box attacks by perturbing the node features. While each setup configuration might find its suitable application scenarios, we believe that near-black-box setups are particularly important as they are associated with many realistic scenarios. Among the existing studies on node-level black- box attacks, most of them (Bojchevski & Günnemann] 2018 Chang et al. 2020 Dai et al. 2018) still allow access to model predictions or some internal representations such node embeddings.
In this paper, we follow the most strict bear-black- which prohibits any probing of the model. Compared to Ma et al. (2020), develop attack strate- gies by directly analyzing the problem of maximizing miscclassification rate, rather than relying on heuristics.
setup (Ma et al. 2020) to our knowledge,
2

---

Under review as a conference paper at ICLR 2021
We remark that there are also plenty of existing works investigating adversarial attacks non-GNN models (Wang & Gong 2019; Zhang et al. 22019), which we consider less relevant to this work, and refer the readers to the survey papers (Jin al. 2020: Sun et al. 2018 for more details.
PRELIMINARIES
3.1 NOTATIONS
We start by introducing notations that will be used across this paper. Suppose we have an attributed
graph G (V. E, X, y). where V 21, 2..... ,N} is the set of N nodes, E' S V x V is the set of edges, X E R is the node feature matrix with D-dimensional features, and E {1, 2, ... K} the node label vector with K classes. We also denote a random walk transition matrix on the graph as M E RNN,, For any 1 S i, S N, M, = 1/[Na (1. E E i = j. and Mi = 0 otherwise. To case the notation, for any matrix A E P in this paper, we refer Aj to the transpose of the j-th row of the matrix, i... A₂ E D2.
We consider a GNN model f: RNNDD - RNN that maps from the node feature matrix X to the output logits of all nodes (denoted as H a f(X) E Nx Let Ne; = {j E V (1, E F] U (i) be the set of neighbors of node including itself. We assume the GNN has L layers, with the
1-th layer (0- < 1 < L.) at node i taking the form H ReL.U (Ejex; Qiy (iyW(( - -)- w()
is the learnable weight matrix, ReI.U()) is an element-wise ReLU activation function, and different GNNs have different normalization terms Oij- We also define (T()) = X and H = H(L)
EjEN; Ciy (syW(L)
( (((11) Later in Section 4 we carry out our analysis on GCN model with ag =
1/|Wa (Hamilton et al. 2017).
3.2 THE NEAR-BLACK-DE ADVERSARIAL ATTACK SETUP
Next briefly introduce the near-black-bor adversarial attack setup proposed by Ma et al. (2020). The goal of the attack is to perturb the node features of a few carefully selected nodes such that the model performance is maximally degraded. The attack is decomposed into two steps. In the first step, the attacker selects set of nodes S C V to be perturbed, under two constraints |S| S r and [M] S m, Vi S for some 0 < < N and < m < max, [Wa). These two constraints prevent the attacker from manipulating a lot of nodes or very important nodes as measured by the node degree, which makes the setup more realistic. In the second step, the attacker is allowed to add small constant perturbation E IR to each node in S, i.e., let the perturbed feature be X A X; + for E S. The perturbation vector c is constructed based on the domain knowledge about the task but without access to the GNN model. For example, if the GNN model facilitates a recommender system for social media, an attacker may hack handful of carefully selected users and manipulate their demographic fcatures, posts, or browsing trajectories to get more users exposed to certain political content the attacker desires. In practice, the perturbation vector can be tailored for different nodes given personalized knowledge about each node. But following Ma et al. 2020)) consider the worst case where no personalization is available.
3.3 INFLUENCE MAXIMIZATION ON A LINEAR THRESHOLD MODEL
Given an information/influene diffusion model on a social network, influence maximization is the problem of finding a small seed set of users such that they spread the maximum amount of influence over the network. In linear threshold model (Kempe et al.] 2003), the influence among nodes characterized by a weighted directed adjacency matrix / E NNN where Lij 2 for each (i,j) E E and 4j 0 for each (i.j) & E. Given seed set of nodes being activated at initial state, the influence passes through the graph to activate other nodes. There is threshold vector E N associated with the nodes, indicating the threshold of influence each node must have received from its active neighbors before it becomes activated. In particular, when the influence propagation comes to a stationary point, a node outside the seed set will be activated if and only if
Σ JEN: activated
1 2 m/-
(1)
3

---

Under review as a conference paper at ICLR 2021
Target Nodes
Thresholds:
0,
02
0
0
0
6g
1
2
3
5
6
7
8
9
8
5
6
9
2
5
6
8
Seed Candidates
GNN the Original Undirected Graph in Data
Linear Threshold Model on the Derived Directed Bipartite Graph
An illustrative example the linear threshold model on the derived directed bipartite graph. To simplify the visualization, the GNN is assumed to have layer, and therefore the derived directed bipartite graph have links from its zero-th (itself) and first order neighbors in the original graph. For GNN with k layers, the derived directed bipartite graph will have links from all its 1-th order neighbors in the original graph, for any 0 S < k. Each target node has its own threshold 0 be influenced (mis-classified). The edge weight depends on the random walk transition from the seed node to the target node.
Figure 1:
4 ANALYSIS OF THE ADVERSARIAL ATTACK PROBLEM
In this section, we investigate how to develop adversarial attack strategies under the caar-black-box setup stated in Section 3.2 in principled way.
4.1 NODE SELECTION FOR MIS-CLASSIFICATION RATE MAXIMIZATION
Suppose an attacker wants to attack a well-trained L-layer GCN model f. Following the two- step attack procedure, the attacker first selects valid node set S Cr.m {T C | [T] < I. m.Yt Vi E T} for some given constraints and m. Then the constant perturbation added to the feature of each node in S, which leads to perturbed feature matrix X(S, c). Since our primary interest is the design of the node selection step, we shall omit and just write the perturbed feature as (S) for simplicity. We denote the output logits of the model after perturbation as H()) = f(X Clearly, (0) equals to the matrix output logits without attack.
In untargeted attack, the attacker wants the model to make many mistakes as possible, which best measured by the cisiffaasiiii rate. Therefore we formulate the problem of selecting the node set optimization problem maximizing the mis- mlssclassification rate over S, with the two constraints quantified by r, m.
max H₁a(S) + Hys (5) A=I.-.,K
max SEC,mm
where 1 [-] is the indicator function. We drop normalizing constant 1/N in miscclassification rate.
At the first glance, the optimization problem ( is combinatorial optimization problem with complicated objective function involving neural networks. the following section, we demonstrate that, under simplifying assumption, it can be connected to the influence maximization problem.
4.2 CONNECTION THE INFLUENCE MAXIMIZATION ON LINEAR THRESHOLD MODEL
We first introduce a simplifying assumption of ReLU that has been widely used to case the analysis of neural networks (Choromanska et al. 2015 Kawaguchi 2016), including GCN (Xu et al. 2018
Assumption 1 (Xu et al. (2018). All the ReLU activations activate independently with the same probability, which implies that all paths the computation graph of the GCN model are indepen- dently activated with the same probability of success p.
4

---

Under review as a conference paper at ICLR 2021
Under Assumption 1 are able to define (S) - Bpan [H()) for any S S VVV, where Epah (S)) indicates the expectation (S) over the random activations of ReLU functions in the model. Then we can rewrite problem (2) in form that is similar to the influence maximization objective on a linear threshold model. The influence weight matrix is defined by the L-step random walk transition matrix B _ M And the threshold for each node is related to the original output logits (0), the perturbation vector e, and the product of the GCN weights W - p- Ili= W E RKXD Formally, we have the following Proposition [I
Proposition 1. If we replace H.) by H() in problem 2 problem as follows,
then can rewrite the optimization
max SECr.m
Σ
Σ Bys 0j
(3)
j=1
where, for ki argmax (S).
Hj (0) H5h;
5kg (0)
0g _
(4)
( W,, )=e
In particular, if = Dy. we define 03 oc.
Interpretations of the new objective 33 The new optimization objective 33) has nice interpreta- tions. The L-step random walk transition matrix measures the pairwise influence from input nodes target nodes in the GCN model and Eies By: can be viewed as measuring the influence of nodes in S on a target nodes j. In each 0j. the numerator Hins (0) - Hy ji, (0) can be viewed as the logit margin between the correct class and those wrong classes, which measures the robustness of the prediction on node j. The denominator (W n ) measures how effective the perturbation is. In combination, 0, measures how difficult it is to mis-classify the node j with perturbation e. This new objective nicely separates the influence between nodes and the node-specific robustness.
Note the form each term inside the summation over N Eq. 3 [[ies Byi > 0z]. very similar to that of Eq. (I) In fact, the objective (3) can be viewed as the influence maximization objective on a directed bipartite graph derived from the original graph, as shown in Figure [ The call them the seed candidate side
derived bipartite graph has N nodes on both sides (assuming and target node side T), and there are edges pointing from side to side T but not the converse way. The edge weight from the node i on the side S the node the side T (1 í,j I N) is defined as Bjt. Then it is easy to see that the problem (3) is equivalent to the influence maximization problem the bipartite graph with the node-specific thresholds being 0,, 1, N.
Two difficulties for solving the problem the original mis-classification rate maximization problem in terms of influence maximization, we still face two major difficulties before we can develop an algorithm to solve the problem. The first difficulty is that we do not known the value of in a near- blackblack-bee box attack setup as it involves the model parameters. The second difficulty is that, even if 9 is given, influence maximization on the seemingly simple bipartite graph still NP-hard, as we show in Lemma] !
While we now have got better interpretations of
Lemma 1. The influence maximization problem on a directed bipartite graph with linear threshold model is NP-hard.
4.3 ASSUMPTIONS ON THE THRESHOLDS
In this section, we mitigate the aforementioned two difficulties by making distribution assumptions on the thresholds 0.
is well-known that if the threshold 0, of each node j is drawn uniformly at random from the inter- val [0, 1]. the expected objective of general linear threshold model is submodular, which leads to an efficient greedy algorithm that solves the expected influence maximization problem with per- formance guarantee (Kempe et al. 2003). In light of this fact regarding the general linear threshold model. we show (in Proposition] 2 that a mild assumption on the distribution of 0 will guarantee the expectation of the objective be submodular, thanks the simple bipartite structure.
5

---

Under review as a conference paper at ICLR 2021
Proposition 2. Suppose the individual thresholds are random variables drawn from some distri- butions, and the marginal cumulative distribution function of the threshold 0g for node j is Fj. j = 1,. N. If Fi, FN individually concave in the domain [0, +oo), then the expectation of the objective
N
1(S) A Eer... A8N
Σ1 ==1
Σ LEES
B3g > 0z
(5)
is submodular.
Note that here we do not need the thresholds to be independent from each other, and we only require the marginal probability density function of each 0j to be non-increasing on the positive region.
Proposition 2 partially addresses the second difficulty. While we still do have a solution the original problem (3 we now know that for a wide range of distributions of 6, the expected mis- classification rate is submodular and can be approximated efficiently through a greedy algorithm.
For the first difficulty, we propose to explicitly specify a simple distribution for & and optimize the expected mis-classification rate h(S), which no longer involves any model parameters and gives us a near-blace bear-black-bol box attack strategy. While this seems to radically deviate from the original opti- mization objective (3). in the following Section [S] we empirically show that we only need a crude characterization of the distribution of 0 to obtain effective attack strategies.
Concrete near-black-box attack strategies. Below we derive two concrete near- war-black-bor attack strategies by specifying the distribution of 9 to be uniform distributions and normal distributions respectively.
Corollary 1. !f > 0 and 02 i.i.
uniform (-b, a), then
h(S)
min Σ
Byss a) +b)
(6)
iES
and h(S) submodular.
Corollary 2. a > and 0j iidd
N(0,02). then
N
1 (1+ erf
( 2
Liie Byi
h(S)
Σ j=1
2
where erf(-) is the Gauss ervor function. And h(S) submodular.
Corollary and 2 follow directly from Proposition 2 given the cumulative distribution functions of the uniform distribution and the normal distribution as well as the fact that they are concave at the positive region. In particular, Eq. (6) belongs well-known submodular function family named the saturated coverage function (Lin & Bilmes 2011] Tyer & Bilmes) 2015). Under assumptions in Corollary [I, the adversarial attack problem reduces the classic influence maximization problem under the linear threshold model where the thresholds follow uniform distributions.
We name the attack strategies obtained by greedily maximizing the objectives 6 and (7) as InfMax- Unif and InfMax-Norm respectively. Specifically, each strategy iteratively selects nodes into the set to be perturbed up to a given size. At each iteration, the node, combining with the existing set, that maximizes Eq. (6 or Eq. 7 will be selected.
4.4 DISCUSSIONS ON THE APPROXIMATIONS
From problem 3) to our final attack strategies, we have made two major approximations to address the two difficulties that raised at the end of Section 4.2
The first approximation we go from the original optimization problem to its expected version. Note that / depends both the model parameters and the data, which we do not have full access

---

Under review as a conference paper at ICLR 2021
Table 1: Summary of the attack performance in terms of test accuracy (%), the lower the better attack. Bold denotes the best performing strategy in each setup. Underline indicates our strategy outperforms all the baseline strategies. Asterisk (*) means the difference between our strategy and the best baseline strategy is statistically significant by pairwise t-test at significance level 0.05. The error bar (=) denotes the standard error the mean by 40 independent trials. The thresholds correspond to the node degree constraint m..
Cora
Cheseer
Pobmed
Method
JKNec
GCN
GAT
JKNet
GCN
GAT
JKNet
GCN
GAT
None
85.9 0.1
80.5 a: 0.2
87.7 0.02
7&.0 02
75.0 + 0.2
74.3 a
80.7 = 1.1.1
56.7 0.1
85.2 = 1I1
Threshold 10%
Randam
60.+ 1.1
8..7+003
+26+006
61.5 0.9
71.6 0.2
+0.
76.1=
82.0 + 0.3
73.5 = 0.3
Degree
65.0
0.44
66.6.10.77
53.7 1.0.9
0.3
63.9 1.5
63.5 1.0.0.0 0.0
78.0 0.5
65.8 = 0.7
Pagerank
11.74:00 0.9
0.3
7..
1:33::00
2..
0.8 0.8
90
61.9+0.3
7..0+0.3
67.0+11
RWCS
1...
GC-RWUS
47.5
06.3
58.5
61.7
67.4=
InfMax-Unif
54.3 1.5
7..9-+0.55-
55.6 2: 0.00
47.1 1.0x
06.2++0.5
68.1++0.66
60.0
77.1 0.79
67.0-0.00 0.04
IntMax Norm
56. 1.5"
78.1 0.53
36.100
$7.1 1.0%
05.6 =: 0.5a
38.1 1: 0.6m
58.8
1.14
76.2 1 0.7c
55.9 1.0+
Threshold 30%
Random
71.5 1.1
82.1 4 0.3
74
6LD: 0.5
72.4 0.2
71.7 0.0
78.0 =:
82.4 =: 0.1
76.00 = I.d
Degroe
67.5+ 1.2
$1.0++0.4
70.4 +.0
58.1 1.0
70.5 1.5++00
67.7 +.0+004
73.2
0.8
81.1 -0.
71.0 0.4
Pagerank
79.4 0.5
0.3
8.33103
702 1.3
1..2
7..
70.0
0.3
52.6
1.6.100 0.2
70.0
0.2
Betweemness
60.9 4: 1.3
8..4
0.
57.7 + 1.0
70,8 0.3
76.3 0.5
20.9 0.4
71.7 = 014
RWCS
70.2 0.5
6.55
82.3+-0.3
69.0 0.
7..7
7:.7::022
78.2 0.3
81.7 0:0.
77.8 = 0.2
GC RWCS
0.4.
0..2
0.4
62.1
0.8
IafMar-Uaif
1.5*
69.6
1.0
61.2
69.4
InrMax-Norm
1.54
0.95
$7.30.5
79.7
The first approximation treats them as random, and takes expectation over 0, which integrates out the randomness in data and the model training process. And the resulted expected objective func- tion h(S) is submodular under the conditions in Proposition 2 A natural question regarding this approximation is how does the mis-classification rate (3) concentrate around its expectation (5)? If 8 are independent, the indicator variables in (5) are also independent, and it is easy to show the mis-classification rate is well-concentrated for large graph size N through Hoeffding's 's inequality. However, the independence assumption is unrealistic in the case of GNN the predictions of adja- cent nodes should be correlated. Further note that & can be written in terms of linear combinations of node features. With extra assumptions on the node features and the graph structure, one may be able to carry out finer analysis on the covariance of 6, and thus how well the misscaassification rate concentrates. We leave this analysis for future work.
The second approximation is that we further specify simple distributions of 6, which highly likely deviate much from the real distribution. On one hand, our superior empirical results shown Sec- tion 5 suggest that these simple strategies are practical enough for some applications. On the other hand, this leaves room for further improvement real-world scenarios if we have more knowledge regarding the distribution of 0. For example, if attacker has very limited number of API calls to access the model predictions, these calls are probably not enough to train a reinforcement-terrmig based attack strategies but they can be effectively used to better estimate the distribution of 6.
5 EXPERIMENTS
In this section, we first empirically evaluate the performance of the proposed attack strategies, IniMax-Unif and InfMax-Norm, against several baseline attack strategies. We also visualize the distributions of f to gain better understanding of the approximations we made.
5.1 ATTACK STRATEGIES FOR COMPARISON
Implementation InfMax-Unif and InfMax-Norm. For the proposed Inf Unif and InfMax- Norm, there are two syper-parameters respectively to be specified. Recall B = M the first hyper- parameter for both method is L. We set L = 4 following RWCS and GC-RWCS. We note that, for the attack strategies to be effective in practice the hyper-parameter L does not have to be the same as the number of layers of the GNN being attacked, as we will show in the experiments. For InfMax- Unif. there two additional distribution hypee-parameters b. However, b does not influence the selection of nodes so we only need to specify a. For InfMax-Nora we need to specify the distribution parameter a. We fix 0.01 and
0.01 across all the experiment setups.
7

---

Under review as a conference paper at ICLR 2021
Theoretically, the optimal choice of a or should depend on the perturbation vector well as the dataset. However, we find the proposed InfMax- Unif and InfMax-Norm strategies are fairly robust with respect to the choice of (see the sensitivity analysis in Appendix
Baseline strategies. We compare with five baseline strategies, Degree, Betweenness, PageRank, Random Walk Column Sum (RWCS), and Crredily-Correctte RWCS (GC-RWCS).
The first three strategies, as suggested by their names, correspond to three node centrality scores. These strategies select nodes with the highest node centrality scores subject to the constraint Cr.m.
RWCS and GC-RWCS are two near-black-box attack strategies proposed by Ma et al. (0200) RWCS derived by maximizing the cross-entropy classification loss but with certain approxima- tions. In practice, RWCS has a simple form: selects nodes with highest importance scores defined as ((i Σ - [ (recall that M is the random walk transition matrix). We set the hyper- parameter L 4 following Ma et al. (2020). GC-RWCS further applies a few heuristics top of RWCS to achieve better mis-classification rate. Specifically, it dynamically updates the RWCS importantce score based after selecting each node. In the experiment, we set the pyper-parameters of GC-RWCS L = 4, 1 = 30, and k 1 suggested in their original paper. Interestingly, RWCS can be viewed special case of Inf Unif if we set a = co (or large enough). And GC-RWCS without removing the local neighborhood step can also be viewed a modified version of InfMax-Unif.
heuristic. It also removes local neighborhood of the selected node
5.2 THE ATTACK EXPERIMENT
Experiment setup. We follow exactly the same experiment setup in Ma et al. (020) except for
that we further include the GAT model (Veličković et al., 2018). So we only briefly introduce the setup here due to the page limit, and refer Appendix A. and Ma et al. (2020) for more details.
We test attack strategies on 3 popular GNN models, (2-layer) GCN (Kipf & Welling 2016), (2- layer) GAT (Veličković et al. 2018). and (7-layer) JK-Net (Xu et al. 2018). for public benchmark datasets, Cora, Citeseer and Pubmed (Sen et al. 2008). We apply the attack strategies following the two-step procedure stated in Section 3.2] For the node selection step, we limit the number of nodes to be attacked, r, 1% of the graph size for each dataset. We test
setups of the node degree threshold, m. by setting it equal to the lowest degree of the top 10% and 30% nodes respectively. For the feature perturbation step, we follow the same way as in Ma et al. (2020) construct the constant perturbation vector e.
Experiment results. We provide the attack experiment results Table I We show the model accuracy after applying each attack strategy in each dataset and model combination, the lower the better. We also include the model accuracy without attack (None) and with an attack under random node selection (Random) for reference.
As can be seen in Table both the proposed attack strategies achieve better attack performance than all baselines on all but one setups, out of the 18 setups in total. And most of the differences are statistically significant. We highlight that, compared to the strongest baseline, GC-RWCS, our methods have fewer hyper-parameters and better interpretation. In addition, the neighbor- removal heuristic also contributes to the performance of GC-RWCS method, while our methods outperform GC-RWCS without such additional heuristics.
5.3 VISUALIZING THE DISTRIBUTIONS OF 0
We also empirically investigate the distributions of see how likely their PDFs are non-increasing on the positive domain. In particular, given the parameters of a well-trained GCN, we are able approximately calculate 0 with Eq. [4 We train GCN on Cora and get one set of 0. We repeat this process with 1000 independent model initializations and get 1000 sets of 0. Then we can visualize histogram over the 1000 values of 0, for each node j. In Figure 2 we show the histograms of 3 randomly selected nodes. We show the histograms of more randomly selected
nodes in Appendix As can be seen from the histograms, in most cases the empirical probability
We can only do it approximately because we do not know p. For the visualization, we just set p
8

---

Under review as a conference paper at ICLR 2021
330
175
153
150
125
150
23
-002
Figure 2: Each figure shows histogram 0, for fixed node over 1000 independent trials of GCN on Cora. The 3 nodes are randomly selected from the union of the validation set and test set.
density decreases when ; > which is the assumption required for the expected miscclassification rate to be submodular in Proposition 2
CONCLUSION
We present a formal analysis of near-black-bor attacks on Graph Neural Networks, formulated as the problem of mis-classffication rate maximization. By establishing novel connection between the original optimization problem to an influence maximization problem upon a linear threshold model, develop group of efficient and effective wear-black-bou. attack strategies with nice interpreta- tions. Extensive empirical results demonstrate the effectiveness of the proposed strategies, which outperform state-of-the-art attacking strategies multiple types of GNNs. In future work, we plan to explore how to perturb the graph structure under this near-black-box setup, as well as how to perturb node features under extra constraints (e.g. binary or nonnegative).
ACKNOWLEDGEMENT
We would like to thank the anonymous reviewers for their detailed comments and suggestions, which help significantly improve this paper.
REFERENCES
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. arXiv preprint arXiv:1809.01093, 2018
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 embed- ding models. In AAAI Conference on Artificial Intelligence, 2020.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pp. 192-204, 2015,
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. arXiv preprint Tttv:180060237711 2018.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 177-177, 2020.
Wengi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-426, 2019.

---

Under review as a conference paper at ICLR 2021
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Rishabh Iyer and Jeffrey Bilmes. Submodular point processes with applications to machine learning. In Artificial Intelligence and Statistics, pp. 388-397, 2015.
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.
Kenji Kawaguchi. Deep learning without poor local minima. Advances neural information processing systems, pp. 586-594, 2016.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 137-146, 2003.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: www..66099.2077 2016.
Cheng Li, Jiaqi Ma, Xiaoxiao Guo, and Qiaozhu Mei. Deepeas: An end-to-end predictor of infor- mation cascades. In Proceedings of the 26th international conference on World Wide Web, pp. 577-586, 2017.
Tianxi Li, Elizaveta Levina, Ji Zhu, et al. Prediction models for network-linked data. The Annals of Applied Statistics, 13(1):132-164, 2019.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Pro- ceedings of the 49th Anmual Meeting of the Association for Computational Linguistics: Human
Language Technologies, pp. 510-520, 2011.
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Black-box adversarial attacks graph neural net- works with limited node access. arXiv preprint arXiv:2006.05057, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S Yu, and Bo Li. Adversarial attack and defense on graph data: A survey, arXiv preprint arXiv: 10528, 2018.
Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung- Yu Hsieh, and Vasant Honavar. Node injection attacks on graphs via reinforcement learning. arXiv preprint arXiv: /te///99900544 2019.
Haoteng Tang, Guixiang Ma, Yurong Chen, Lei Guo, Wei Wang, Bo Zeng, and Liang Zhan. Ad- versarial attack on hicrarchical graph pooling neural networks. arXiv preprint arXiv:2005. 11560, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Binghui Wang and Neil Zhenqiang Gong. Attacking graph-based classification via manipulating the graph structure. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pp. 2023-2002222 2019.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversar- ial examples for graph data: deep insights into attack and defense. In Proceedings of the 28th International Joint Conference Artificial Intelligence, pp. 4816 AAAI Press, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. arXiv preprint arXiv: /906.0990000000 1901199966414444 04214, 2019.
10

---

Under review as a conference paper at ICLR 2021
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint SMM1::1806003566. 2018.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983, 2018.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: A deep learning framework for traffic forecasting. arXiv preprint arXiv: 14Kiv:7709004555 2017.
Hengtong Zhang, Tianhang Zheng, Jing Gao, Chenglin Miao, Lu Su, Yaliang Li, and Kui Ren. Data poisoning attack against knowledge graph embedding. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 4853-4859. AAAI Press, 2019.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. International Conference on Learning Representations (ICLR), 2019.
Daniel Zügner,, Amir Akharnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 2847-2856, 2018.

---

Under review as a conference paper at ICLR 2021
A
APPENDIX
A.1
PROOFS
We first give a more precise and restated version (Assumption 2 of Assumption | and introduce Lemma about GCN, which is proved by Xu et al. (0188).
Assumption (Xu et al. (2018) Restated.). Recall that ReLU function can be written as
ReLU(x)) x. 11>>00 0].
Suppose there are R ReLU functions in the GCN model and we index them with i 1.2..... R. This assumption assumes that the i-th ReLU functions, for i = 1,2, R, replaced by the following function,
ReLUU(()) = xx.
where 21, 22.
Bernoulli(?).
This assumption implies that all paths in the computation graph of an L-layer GCN model are independently activated with the same probability p p=
Lemma 2 (Xu et al. (2018))). Given an I-layer GCN, under Assumption 7 for any node i, E V,
JHl ax,
(IIw0)
E
ponh
(8)
I=L
where M E NxN is the random walk transition matrix, i.e., for any S i,j S N. My 1/| (i. E or j. and Mij otherwise.
Proof for Proposition 1
Proof. Recall that (SS) = patth [H [ Epath (XX()) We first show H()) a linear function of (S), which suffices to show that, for any i E V and s I, Eyan H (T(()())) is linear function of Epash (H))) When L,
Epath (1)
Σ JEN,
oi (L) Epath (1) (S)),
so the statement holds. When 1 < 1 < L, under Assumption independently with probability p.
suppose each ReLU activates
ass (00 (( ]
Epath ((1) = Epath
Σ JEN
p Σ Ois
(L) Epath [11 ()
JEN.
the statement also holds. Therefore H(S) is linear function of X(S). In particular, Ep [H] (0) is linear function of X.
We know that (S) = Xx + e for i E S and X,(S) = Xx for i $ S. And by Lemma we can rewrite (S) in terms of H(()) and For any j E V.
[ )
AT (0,(0) + EMM4
iES
L=L
In Section 4.2
we have defined B L and W = = =p Wl))
H,(S) H1 W Σ Bjg-
12

---

Under review as a conference paper at ICLR 2021
Now look at the objective (2. If replace (S)) with (S)) in this objective and plug Eq. ( into it, then for each j E V, we have
H)k(S) + Hin (5)
max kE (E1,,, _K}
jk, (5) > Hivs (S)
sk, (0) W e. BBy > His (0)
+ WT 81
Σ Bys
iES
iES
H (0) - H 1k, (0)
=1
Σ
By
(Wk, Wv, )
iES
=1
Σ
Bjg 0g
LES
where we have defined kj argimax; 1,.., (Sx(SS and recall the definition of 03 in Eq. (4) Therefore we get the optimization problem
0j 0,)
max SECr.m
Σ j=1
Σ LISS
B
Proof for Lemma 2003
1
The proof follows similarly as the proof of Theorem 2.4 in Kempe et al.
Proof. We prove by reducing the NP-complete Set Cover problem the influence maximization problem directed biparatite graph with linear threshold model. The Set Cover problem is defined as following. Suppose we have a ground set = {u1, u2, [u,] and a group of m subsets of U, S, S2. ... Sm. The goal is to determine whether there exists (r < n and < m) of the subsets whose union equals to U.
For any instance of the Set Cover problem, having m nodes (each one corresponding to a given subset of U), and the second side having n nodes (each one corresponding an element of U). There are only links going from the the first side to the second side. There will be a link with constant influence score > from a node on the first side the second side if and only if the corresponding subset contains that element in U. Finally the node-specific thresholds of each node on the second side is set as a/2. And the influence maximization problem asks to select r nodes on the graph to maximize the number of activated nodes. The Set Cover problem is then solved by deciding if the maximized number of activated nodes on the bipartite graph is greater than n r.
construct bipartite graph with the first side
Proof for Proposition
Proof. We first show that the expected misclasssiocation rate h(S) can be written in terms of the marginal CDFs of 0.
13

---

Under review as a conference paper at ICLR 2021
N
h(S) = Eer.. ON
1
Σ
Byi > 0
5=1
LiES
Es.... By
Σ Bys BB} 8,
LiES
Es, 1
Σ
Byt B)
LiES
Σ Pj
Σ iES
Bys > >01
j=1
Σ F
Σ iES
By
j=1
where Pj is the marginal probability of 0,.
Since Bys 2 O. so Eies Byz is a non-decreasing submodular function of with a lower bound O. Each CDF Fj is non-decreasing by definition, if it is also individually concave the domain [0, +o0), we know F; (Eres Bjx) is submodular w.r.t. S and hence (sS)) is submodular.
A.2 MORE EXPERIMENT DETAILS
Definitions of the node centralities. For each node i, the Degree centrality score is defined as grx(() Cn(i) A [AG], the Betweenness centrality score is defined as Cn(() ΣjAtttisek 95a where 9yk is the number of shortest paths connecting node j and ks and gyx (i) is the number of shortest paths that node is on; the PageRank centrality score is defined as the stationary scores achieved by iteratively updating PR((i 1- + a EjEN;
N
PR()) and we set the [N]
0.85.
Detailed descriptions of GC-RWCS. GC-RWCS further applies a few heuristics on top of RWCS achieve better mis-classification rate. Specifically, it iteratively selects nodes one by one up to r nodes, based on dynamic importance score, i.e., (t) E [Q]]s for the f-th iteration. Qi E {0, N is binary matrix that is dynamically updated over t. At the initial iteration, Q1 obtained by binarizing M 1. assigning to the top / nonzero entries in each row of M L. and 0 to other entries. For t > 1, suppose the node i is selected at the f iteration, then Q, is obtained from Q by setting zero for all the rows where the elements of the i-th column GC-RWCS also applies another heuristic that, after each iteration, remove the k-hop neighbors of the selected node from the candidate set the subsequent iterations. In the experiment, we set the hyper-parameters of GC-RWCS == 4, I 30, and k = 1 as suggested in their original paper. The iterative-selectie process in GC-RWCS (without removing the k-hop neighbors) gives equivalent results as MiMMx-UUnff if we replace the matrix B in InfMax- Unif by Q1 and set 1.
in Q--1-
More details for the experiment setup. We randomly split each dataset by 60%, 20% and 20% as the training, validation, and test sets and run 40 independent trials for each model and dataset combination. We apply the attack strategies following the two-step procedure stated in Section 3.2 For the node selection step, we limit the number of nodes to be attacked, r, as 1% of the graph size for each dataset. We test two setups of the node degree threshold, m, by setting it equal to the lowest degree of the top 10% and 30% nodes respectively. For the feature perturbation step, we follow the same way in Ma et al. (2020) to construct the constant perturbation vector Ideally, the perturbation vector should be designed according to domain knowledge about the task in real- world scenario. For the experiments on benchmark datasets where do not know the semantic meaning of the features, we simulate the domain knowledge by extremely limited information of the gradients due the lack of semantic meaning of each features in benchmark datasets. The gradients
14

---

of the proposed strategies to Under review as a conference paper at ICLR 2021
only used to select important features and the sign of perturbation rather than the magnitude. We construct the Ej E R
9 -- A sign EE
HL(H.2) 8X133
if E arg trg Σ
BL(H.9)
8XL, I),,
(10)
0,
otherwise,
where À is the perturbation strength and is set 1; and iss set 2% of the number of features. The same perturbation vector is added to all selected nodes in S.
A.3 ADDITIONAL EXPERIMENTS
Attack performance with varying perturbation strengths. In Figure we demonstrate the attack performances of different attack strategies with varying perturbation strengths. We first observe that the proposed attack strategies with the fixed hyper-parameters (a = 0.01 for InfMax-Uni and 0.01 for InfMax-Norm) outperform all baselines more cases. It is also worth noting that, as suggested by Eq. 4 the distribution of 0 is dependent on the perturbation and hence A. In the approximated uniform and normal distributions for InfMax- -nif and InfMax-Nort respectively, the optimal choice of and a should be dependent on X. Intuitively, smaller À makes the 0 have larger variance, so the choice of and o should also be larger. This indeed suggested by the results in Figure 3 Recall that, in Section 5.1 we discussed that RWCS can be viewed special case of unMM with a oo. And in Figure 3 we observe that RWCS (equivalent to InfMax- Unif with oo) sometimes (e.g.. for GCN) outperforms InfMax-Unie (with 0.01) when À is very small. However, we leave further optimization of the future work.
Sensitivity analysis of a for InfMax-Unif and a for InlMax-Norm. In Figure we carry out a sensitivity analysis with resepct to a and for InfMax-Unit and aulMa--Norm respectively. In Section 5.2. we have fixed a = 0.01 and
0.01 for all experiment settings. Here we vary them from 0.005 to 0.02 and show that the results of the proposed strategies, especially those of the InfMax-None Norm, stay relatively stable with varying choices of the
Targeting on the test set. In the experiments in Section 5.2 we use the objectives Eq. (6) and Eq. (7) that sum the whole graph of N nodes, for untargeted attack assuming the attacker does not know the test set to be evaluated on. If the targeted test set known, we can adapt Eq. (6) and Eq. (7) sum on the test set only. In Table we compare the performance of untargeted attacks and the performance of attacks targeting on the test set. As can be seen, when targeting on the test set, the proposed strategies are further improved compared to their untargeted versions.
Synthetic data experiments. We further carry out experiments on synthetic datasets to demonstrate that the proposed attack strategies are effective knowledge regarding the node features is given. Following Ma et al. (2020). we generate the syn- thetic datasets as follows. First, we generate a Barabási-Albert random graph (Barabási & Albert) 1999) with N nodes and adjacency matrix A. Then we generate node features X R RXXO domly from multivariate normal distribution with zero mean and covariance (Lyym + -J- (Laym is the symmetric normalized graph Laplacian and I is identity matrix; this covariance introduces smoothness over the graph (Li et al. 2019)), and take the absolute values elementwisely. Finally, node labels generated by Y = Sigmoid + X)XW)= 0.5), where W RR is given weight matrix. During the attack process, we assume that the attacker knows few (0.2D) impor- tant features with the largest corresponding weights in W but has no access the trained model. In Tabel 3 we experiment on 5 synthetic graphs generated by different seeds with N = 3000 and D 10, and the proposed InfMax- Unif and InfMax- Norm outperform baseline attack strategies.
pure black-box box setting when sufficient domain
Constructing based on the training partition only. To verify the coarse gradient information we use to construct the perturbation vector c is not sensitive to the set of nodes, we further repeat the experiments in Table with the only difference that, when constructing following Eq. (10), use the average gradients on the training partition only rather than all nodes. The results are shown in Table 4 which very similar to those in Table I This additional study verifies our belief.
15

---

Under review as a conference paper at ICLR 2021
Cora
0.85
0.45
0.64
5.80
0.79
5.70
5.55
0.79
0.78
0.59
0.
0.4
02
0.4
0.6
0.5
0.4
JKNet Citeseer
GCN Choseer
GAT on Gitescer
0.34
0.72
0.0
0.72
0.550
050
0.66
0.0
02
0.4
0.6
0.5
1.0
0.0
0.2
0.6
0.6
0.5
1.0
22
0.4
0.8
1.5
35
JKNbt Pulmed
0.00
0.75
0.22
0.70
Degrs
0.50
0.05
0.70
Randem
RNCS
0.50
OCHINES
Ust
Figure 3: The attack performances with varying perturbation strengths (from 0 to 1). Each figure corresponds dataset-man model combination. The x-axis indicates the value of and the y-axis indicates the classification accuracy after attack. The threshold is set as 10% and all other experiment setups the same those in Section 5.2
Table 2: The test accuracy (%) of models after untargeted attacks (U) vs attacks targeting on the test
(T). The experiment setups are the same as those the Section 5.2
Dataset
Cora
Citeseer
Pubmed GCN
Method
JKNet
JKNet
JKNet
Threshold
10%:
InfMax Unif (U)
$4.311.55
77.910.5
$5.6:10.6
4..1=1.0
66.220.5
$8.41066
60.01112
77.110.7
$7.0=099
InfMax-Nom (U)
54.611.5
78.140.5
56.910.6
47.1110
65.610.5
58.110.6
58.811111
76.240.7
55.9-10
IniMax-Unif (T)
53221:.
77.140.7
54.240.6
46.32110
65.5
57.74:0.6
59.5+:1.3
77.0:0.7
56.0=099
InfMax-Norm (T)
524414
77.240.7
53.6:0.6
46.120.9
64.110.5
56.410.7
57.91122
75.940.7
$4.4200
Threshold
IniMax-Uii
58.21.55
79.9:0.4
39.6:10.5
19.611.0
67.310.5
61.210.6
69.411.0
80.110.5
65.420.5
InrMax-Nom (U)
58.04-1.5
79.94-0.5
60.0+0.5
4..5+1.0
67.6+0.5
61.6+-0.6
69.6++1.0
79,740.5
65.2+0.5
IniMa--Uif
55.81:14
78.9:10.5
$7,5:0.6
48.621.0
66.610.4
60.2400,5
67.5.1100
78.5:10.6
62.9-0.6
InfMax-NNrm
55.31:1.4
78.8100.5
57.010.6
48.620.9
65.810.5
59.2100.6
67.410.9
77.910.6
62.7-0.6
16

---

Under review as a conference paper at ICLR 2021
JKNet
92
60-
61
32-
38
57
36-
19
0.00
R.007
2.0%
2.06
2.005
00000
2,00
2014
2.16
now
2.00
002
KNet Chesser
GCN Chesser
Clesser
51.
50.0
43.5
610
48.5
48.0
660
38-
41.0
0.005
on 6.0
0220
0.000
0,000
6.02
0.00
0.007
Pubmed
Pubmed
68
InMiixAR 19%
12-
GC-RWCS 10%
loMax 19%
Inthaas-irt Ain 30%
TrMMix Form 30%
77
GC KARCS 30%
40-
78
56
56
eaur
cow
0.0
0012
4014
0.000
8007
now
0.0
0012
8014
aote
6000
0.00e
0,007
0,009
0012
6014
noue
Figure 4: Sensitivity analysis of the hyper- hyper-paramette parameters a and a. The experiment setups are the
same as those Section [.2 Each figure corresponds to a mataset-model combination. The x-axis indicates the value of a or a while the y-axis indicates the classification accuracy after attack. The results under the threshold 10% are plotted in green while the results under the threshold 30% are plotted in blue. In addition to the proposed InfMax-Unis and InfMax-Norm, also plot the results of GC-RWCS as the constant dashed lines for references. The plots are made in log-scale for x-axis.
Table 3: The test accuracy (%) of GCN model after attacks with 10% threshold on synthetic data. synthetic 0 to synthetic are five synthetic graph generated by different seeds. Other setups are the same as those in the Section 5.2 The notations are the same as those in Table
Dataset
synthetic
synthetic
synthetic 2
synthetic 3
synthetic 4
None
83.910.3
82.510.2
82.510.2
82.0-1.2
80.810.2
Random
79.610.3
78.810.2
78.3=0.2
77.2+0.2
77.3=1.2
Degree
78.2-1..2
76.910.2
75.310.3
75.5-10.3
74.4-10.2
Pagerank
77.3+0.2
77.3+0.3
77.2=0.2
76.4-10.3
75.3=+0.2
Betweenness
78.3+0.2
76.6+0.2
76.5+0.2
76.1=0.22
75.3+0.3
RWCS
78.3+10.
76.6.10.2
76.9-1022
76.9-10.2
75.1
GC-RWCS
77.0+0.2
75.6+-0.2
75.6-+0.2
75.7-10.2
74.6+10.2
InfMax-Unif
77.4++0.2
7..4+
0.39
74.6+
75.1++0.3
IniMax-Norm
76.7+0.2*
7..4
7..3
7
74.3
17

---

Under review as a conference paper at ICLR 2021
Table The test accuracy (%) of models when is constructed based on the training partition only. The experiment setups are the same those in the Section 5.2
Chessee
Fubmed GCN
Mothod
IaNetMa
JKNesMaapool
JKNotMaapool
None
859:00.1
85.5:002
87,750
75:0=:02
75.0:02
74,8002
K5.700
85.730.1
85:::0.1
Threshold 10%
70.62005
8200003
738=0033
Degree
63.3+114
78.6-0.4
66.7+007
53.8+10
68.1++0.3
64.7+0..
63.5+10
788+005
66.2:0.6
Pagerank
71.9+0.9
78.2-0.3
74.1+0.5
62,4=005
69.8+00.
20.1+00.3
12,0+088
80.2+0.3
71,3=0.3
7866004
64.510.5
78440.6
RWCS
7191:0.8
79.1-0.2
70.610.5
62.020.5
69.71:0.3
69.9110.3
71.010.8
79.710044
69.1:10.4
GC-RWCS
15.9
7..1=066
56.9100.
47.72:100
66.12:0.5
60. 10.1
61.7112
77.340..7
58.3:10.8
InfMax: Unié
1.5
7..3-006
55.51.0.6
4..3
66.0:10.5
59.9100.8
60.0
77.040.7
57.5=0.8*
InfMax-
1..2-1166
Threshald 30%
Random
713111
81.32033
74,110.6
64.2
72.41022
11:210.4
78.01044
8241003
76.2200.3
Degree
80.2-0.3
70.5100.2
71.220.4
Pagerank
79.4:0.5
82.3=0.1
82.410.3
70.3
72.8::0.2
74.02:0.2
79.9103
82.6::0.2
79.0=0022
Retweenness
67.2+1.3
80.1-0.3
67.2+0.5
58.1+10
70.7+0.3
68.7+90.4
754405
808+00.4
719--0.4
RWCS
79.2:0.5
82.4=0.2
82.4+0.3
70.1-0.3
72.8+0.2
74.0++0.2
78.2403
81.740.3
77.9=0.2
GC-RWCS
62.2:1155
79:8-0.4
51.1=111
67.9204
63.6-93.7
71.1408
79.8:0.5
IntMax-Unir
18.--1.3
78.9 0.4
59.4+0.6*
51.2-111
67.2+
62.8-0.7
694+100
80.0+0055
65.9-0.51
InMMa--Nomm
1..6:15
79.2=0,5
59.8100.5
10.1
67.520.5
63.1230.7
69.741.0
79.6::0.6
05.
A.4 DISTRIBUTIONS OF 8 ON MORE NODES
Distributions of 0 on more randomly selected nodes are provided in Figure distributions present bell shapes that are close to normal distributions. And it is approximately true that the probability density function is non-increasing at the positive region.
Many examples of the
18

---

Under review as a conference paper at ICLR 2021
25
X:22
031
130
140
230
400
+0
Figure 5: Each figure shows histogram 0, for fixed node over 1000 independent trials of GCN on Cora. The 15 nodes are randomly selected from the union of the validation set and test set.
19


Reviews:
[{"review_id": "s3W8yQqftnf", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces a novel connection between adversarial attack on graph neural networks in a restricted black-box setup via node feature perturbation, on the one hand, and the influence maximization problem under the linear threshold model on the same graph, on the other hand. An analysis shows that the objective function of the corresponding IM problem is submodular under assumption, hence the problem admits greedy approximation algorithms as effective black-box attack strategies. Experiments show such attacks are effective compared to baselines in degrading the performance of GNNs in terms of mis-classification rate.\n\nA question that remains unaddressed is whether the analogy to the IM problem under the LT model extends to other properties of the problem: under the uniform distribution of threshold θ, the diffusion of influence under the LT is equivalent to a diffusion whereby each node picks at most incoming edge to be active with probability corresponding to the incident edge's weight. This paper would be stronger if it addressed the question of whether this property also extends to the analogy, apart from the submodularity property.\n\nUnder the current analysis, two greedy algorithms are proposed for two different objectives, yet there is no analysis of their complexity and no runtime results on their efficiency. The algorithms are called efficient, but no evidence is provided to that effect. That is a weak point of the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "nUUJy9ylFl3", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper summary: The paper studies the problem of attacking GNNs in a restricted black-box setup, i.e., by perturbing the features of a small set of nodes, with no access to model parameters and model predictions. The authors draw a connection between the restricted attack problem and the influence maximization problem, and then propose several approximation techniques to solve the reformulated attack problem. Experimental results on attacking three GNN models demonstrate the effectiveness of the proposed attack. \n\n\nStrengths\n+The paper is well-written and well organized\n+Solving the restricted black-box based on influence maximization is novel and interesting\n\nWeaknesses\n-Threat model is limited\n-Assumptions are not satisfied\n-Some details are unclear \n-Missing important references\n\n\n\nDetailed comments:\n\n-Threat model is limited.\n\nMy first concern is that the proposed attack only focuses on node feature perturbation, while not mentioning structure perturbation. For attacks to graph neural networks, structure perturbation attack is more meaningful and effective. (see Zugner et al., 2018, Dai et al., 2018). \n\nMy second concern is that why restricting that the attacker does not know model predictions? What’s the motivation and in what scenarios? From my understanding, even in the black-box attack, an attacker can obtain the model  predictions, e.g., via querying the model using the input nodes. \n\n-Assumptions are not satisfied\n\nThe authors assume that theta is from certain simple distributions, in order to make the objective function submodular. However, from the experimental results, such simple distributions are inappropriate. \n\n-Some details are missing\n\nIn Equation (4), there is a connection between theta and epsilon.  But in your experimental setup, this connection is lost. Is epsilon necessary in your experiments, as theta is assumed to satisfy some distribution that is irrelevant to epsilon? \n\nHow do you obtain the gradient (\\partial L / \\partial X) in Equation (10) in the black-box setting? What’s the lambda value? \n\nAs you use the sign of the gradient and a fixed lambda, all the positive gradients should generate the same value and thus the feature perturbations. In this case, how do you select the feature indexes j as there are many ties in epsilon_j?  \n \nIn all experimental results, the improvement of the proposed attack over RWCS/GC-RWCS is marginal (less than 3 percent). I think one reason could be that the selected simple distribution for theta largely deviates from the true distribution. Can you plot the true theta distribution, assuming that W is known in advance?   \n\nWhat’s the efficiency of the proposed attack? Is it better than RWCS/GC-RWCS? \n\n-Missing important references\nThe authors miss the following important works on attacks to graph neural networks:\n\nWang and Gong, “Attacking Graph-based Classification via Manipulating the Graph Structure”, CCS’19\nWu et al., “Adversarial Examples for Graph Data: Deep Insights into Attack and Defense”, IJCAI’19\nEntezari et al., “All You Need Is Low (Rank): Defending Against Adversarial Attacks on Graphs ”, WSDM’20 \n  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "aeTKN5DI2OP", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of the paper:\n--------------\n\nThe authors propose an adversarial attack strategy for graph neural networks based on influence maximization. The attack is (claimed to be) black-box (does not have direct access to the model), evasion-based, and limited to perturbations of the node attributes (i.e. cannot insert / delete edges). The authors make simplifying assumptions about the GCN model (all ReLU paths are equally likely) and the distribution of the individual nodes' thresholds, theta_j. The attack is evaluated experimentally on three well-known datasets and three different models. The proposed attack outperforms the centrality-based baselines and the baselines of [Ma et al. 2020].\n\nStrengths:\n---------\n\n* The paper is well-written and generally easy to follow. \n* The connection to influence maximization is interesting. \n* The problem of GNN robustness under (realistic) adversarial attacks is important.\n\nWeaknesses:\n-----------\n\n* The description of the method and experimental set-up leave a number of open questions (see detailed feedback).\n* Despite claiming black-box attacks, the method actually uses the target model's gradients, even for the test set, for the attack.\n* The experimental evaluation is rather slim. For example, there is no analysis of the node selection algorithm, e.g. what kind of nodes are selected, no analysis of the sharp differences in performance on the different models, and no analysis of the hyperparameters a and sigma.\n\nDetailed comments:\n------------------\n\nI have several concerns about both the method as it is described in the paper as well as the experimental evaluation.\n\n\nMajor points:\n\nMethod:\n* The authors emphasize the black-box nature of their attack, however the perturbation vector requires access to the respective model's gradient, which violates the black-box setting. This is especially critical since Eq. (10) involves the gradient of the loss of ALL nodes, including the validation and test nodes. So effectively, the attack utilizes the gradient of the loss of the test nodes. Also, it is not stated which value of lambda is used for the perturbation, i.e. what magnitude the perturbation has. The authors mention that this is done because the input features lack semantic meaning; however, they do not mention how potential semantic meaning of the features could be used instead of using the gradients.\n* The neighbor weight of alpha_{ij} = 1/|N_i| is not the weight proposed by [Kipf and Welling 2017]. Instead, they propose alpha_{ij} = (d_i+1)^{-0.5} * (d_j+1)^{-0.5}, where d_i is the degree of node i.\n* Why is the attack target the misclassification rate on the whole dataset (Eqs. (3,5,6,7)) and not only on the test set? Does this mean that the results in Table 1 are also reported on the whole dataset? If not, why is there a mismatch between the reported misclassification rate and the optimization objective?\n* Eq. (4) is unclear/not well defined. As stated above the equation, hat{k}_j is the predicted class of node j after perturbing the set S. However, if S fails to change the predicted class of node j, the numerator and the denominator both become 0, i.e. ill-defined. \n* Sec. 4.4: the authors mention that the first approximation leads to the problem becoming \"likely to be submodular\". Why is it only likely to be submodular and not guaranteed? \n* Also Sec. 4.4: According to the authors, the first approximation \"integrates out the randomness in data [...]\". Where is there any randomness in the data?\n* Section 4 shows how the attack can be instantiated for GCN. How is the attack adapted to the other models, i.e. GAT and JKNet?\n* The paper just briefly mentions that Eqs. (6) and (7) are used to select the target nodes via a greedy influence maximization approach. A few more sentences on how this will be exactly done would be readers not familiar with inf. max.\n* The authors should give more details (proof and/or reference to existing work) regarding the derivation of Corollary 1 and 2.\n\n\nExperimental evaluation:\n* Unrealistic set-up: 60% train data. For semi-supervised node classification, typically we have 10% or less training samples.\n* The authors use L=4 layers for the GNNs. However, [Kipf and Welling 2017] report substantially worse performance for L=4 compared to, e.g., L=2. What are the results of the attack when the L used for attacking is different than the L of the GNN?\n* The node attributes in the datasets have special constraints, e.g. for Citeseer and Cora the features are binary, and for Pubmed the features are nonnegative. How is this accounted for by the perturbation model?\n* How do the choice of sigma and a influence the results?\n* Is there any insight into why JKNet and GAT seem to be much more fragile to the attacks? Even for the otherwise very weak random attack GAT's and JKNet's performances drop sharply. Why does this happen?\n* There is no analysis into what kind of nodes the proposed algorithm selects; since node selection is the main contribution of this paper, some insight into this would greatly benefit the experimental evaluation.\n\n\nMinor points:\n* p. 1 original from => original form\n* p. 6 first paragraph: non-decreasing => non-increasing\n* The paper does not cite the correct sources for the dataset.", "extra_scores": {}, "extra_text": {}}, {"review_id": "IE1LpHqMwzT", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\nThis paper studies the problem of designing adversarial attacks (on GNN models) that perturb the feature to maximize the misclassified instances. Assuming that the activations are activated independently at random, the paper shows that the attack design can be reduced to the influence maximization problem under the threshold model. The paper identifies several conditions on the threshold that can make the influence maximization problem submodular, thereby making it easy to optimize.  Experiments have been shown that the proposed attack method has higher performance compared to the existing ones.\n\n##########################################################################\nI find the paper interesting but lean towards rejection at this point. The main reason is that the assumptions are not realistic, and the contributions are incremental.\n##########################################################################\n\nStrength:\n\nThe technical proofs seem to be sound, and the relationship between the attack design and influence maximization is an interesting observation. \n\nWeakness:\n\nThe entire analysis is based on Assumption 1, but the paper does not provide a formal description of the data flow in the network under such an assumption, which makes it hard to follow the subsequent analysis. In addition, this assumption is very restrictive in the sense that it makes all the activation functions (\\sigma) output random numbers, ignoring what has been received from the last layer. For theoretical analysis on general neural networks, such an assumption is somehow minimal (though not realistic, as pointed out in Kawaguchi 2016) to obtain theoretical results, but it is overly strong for designing a practical attack. In particular, assuming Assumption 1 means that we have ignored the structure of GCN, and therefore, it is not appropriate to target this paper for GCN model. In general, I would not think a meaningful attack could be designed without having certain types of prior knowledge. \n\nAnother concern is that the technical analysis largely follows Ma 2020 - the proofs and ideas are very similar. From the introduction, the main difference is to adopt Assumption 1 and get theoretical results, which is somehow incremental.\n\nThe amount of perturbation is not extensively discussed in the experiments; to me, the strength of perturbation is critical to the attack performance. \n\nMinor issues:\n\nIt would better to introduce the goal of the attack along with the attack setup.\nPlease define \\E_path[H(S)] before using it.\nPlease introduce RWCS and GC_RWCS before using these terms.\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper relates the problem of influence maximization and adversarial attacks on GCNs. 
The paper, and its formulation and assumptions stirred up quite a discussion among the reviewers and the authors. I do appreciate the thorough rebuttal that the authors provided, and the reviewers did take it into account (and revised their scores). 
However, all in all, I am afraid that there are just a few too many concerns with this paper. 
If the authors take the reviews to heart, they should be able to improve the manuscript and submit a stronger and improved version to the next conference. 
Decision: Reject