Understanding and Improving Graph Injection Attack by Promoting Unnoticeability
Authors: Yongqiang Chen
Han Yang
Yonggang Zhang
MA KAILI
Tongliang Liu
Bo Han
James Cheng
Venue: ICLR 2022 Poster (2022)
Keywords: Graph Neural Networks
Adversarial Attacks
Node Classification

Abstract: Recently Graph Injection Attack (GIA) emerges as a practical attack scenario on Graph Neural Networks (GNNs), where the adversary can merely inject few malicious nodes instead of modifying existing nodes or edges, i.e., Graph Modification Attack (GMA). Although GIA has achieved promising results, little is known about why it is successful and whether there is any pitfall behind the success. To understand the power of GIA, we compare it with GMA and find that GIA can be provably more harmful than GMA due to its relatively high flexibility. However, the high flexibility will also lead to great damage to the homophily distribution of the original graph, i.e., similarity among neighbors. Consequently, the threats of GIA can be easily alleviated or even prevented by homophily-based defenses designed to recover the original homophily. To mitigate the issue, we introduce a novel constraint – homophily unnoticeability that enforces GIA to preserve the homophily, and propose Harmonious Adversarial Objective (HAO) to instantiate it. Extensive experiments verify that GIA with HAO can break homophily-based defenses and outperform previous GIA attacks by a significant margin. We believe our methods can serve for a more reliable evaluation of the robustness of GNNs.

Published as a conference paper at ICLR 2022
UNDERSTANDING AND IMPROVING GRAPH INJECTION ATTACK BY PROMOTING UNNOTICEABILITY
Yonggiang Chen', Han Yang', Yonggang Zhang Kaili Ma'
'The Chinese University of Hong Kong "Hong Kong Baptist University
hyychen,hyang, x xlma, x joheng] csse .ww.eccchkkom .ddu .hk esygzhang comp .kbu .eduuueduuee .hk
Tongliang Liu", Bo Han", James Cheng'
"The University of Sydney
tongliane inn.. 1iu0 wyneeyyyyy....o.oo edu bhanm Dhanm1@comp wwbu. edu. .hk
ABSTRACT
Recently Graph Injection Attack (GIA) emerges as a practical attack scenario on Graph Neural Networks (GNNs), where the adversary can merely inject few ma- licious nodes instead of modifying existing nodes or edges, i.e.. Graph Modifica- tion Attack (GMA). Although GIA has achieved promising results, little is known about why it is successful and whether there is any pitfall behind the success. To understand the power of GIA, compare it with GMA and find that GIA can be provably more harmful than GMA due to its relatively high flexibility. However, the high flexibility will also lead great damage the homophily distribution of the original graph, i.e., similarity among neighbors. Consequently, the threats of GIA can be easily alleviated or even prevented by homophily- -based defenses designed to recover the original homophily. To mitigate the issue, we introduce a novel constraint - homophily unnoticeability that enforces GIA to preserve the homophily, and propose Harmonious Adversarial Objective (HAO) to instantiate it. Extensive experiments verify that GIA with HAO can break homophily- based defenses and outperform previous GIA attacks by significant margin. We believe our methods can serve for a more reliable evaluation of the robustness of GNNs.
INTRODUCTION
Graph Neural Networks (GNNs), as a generalization of deep learning models for graph structured data, have gained great success in tasks involving relational information (Hamilton al., 2017a; Battaglia et al., 2018; Zhou et al., 2020; Wu et al., 2021; Kipf & Welling, 2017; Hamilton et al., 2017b; Veličković et al., 2018; Xu et al., 2018; 2019b). Nevertheless, GNNs are shown to be in- herently vulnerable to adversarial attacks (Sun et al., 2018; Jin et al., 2021), or small intentional perturbations on the input (Szegedy et al., 2014). Previous studies show that moderate changes to the existing topology or node features of the input graph, i.e., Graph Modification Attacks (GMA), can dramatically degenerate the performance of GNNs (Dai et al., 2018; Zügner et al., 2018; Zügner & Günnemann, 2019; Xu al., 2019a; Chang al., 2020). Since in many real-world scenarios, is prohibitively expensive to modify the original graph, recently there is increasing attention paid Graph Injection Attack (GIA), where the adversary can merely inject few malicious nodes to perform the attack (Wang et al., 2018; Sun et al., 2020; Wang et al., 2020; Zou et al., 2021).
Despite the promising empirical results, why GIA is booming and whether there is any pitfall behind the success remain elusive. To bridge this gap, we investigate both the advantages and limitations of GIA by comparing it with GMA in a unified setting (Sec. 2.2). Our theoretical results show that, in this setting when there is no defense, GIA can be provably more harmful than GMA due to its relatively high flexibility. Such flexibility enables GIA to map GMA perturbations into specific GIA perturbations, and to further optimize the mapped perturbations to amplify the damage (Fig. la). However, according to the principle of no free lunch, we further find that the power of GIA is built upon the severe damage to the homophily of the original graph. Homophily indicates the tendency of nodes connecting to others with similar features or labels, which is important for the success of most existing GNNs (McPherson et al., 2001; London & Getoor, 2014; Klicpera al., 2019; Battaglia

---

Published as a conference paper at ICLR 2022
GMA Perturbation Budgets
GMA Perturbation Budgets
Layer 2
250
500
750
1036
:250
250
500
750
1056
1250
GIA
Layer 1
Robustness
80
Test Robustness
80
MAO
CPA HLP
60
80
50
GA
GIA
60
60
20 50
Normal
100
150
200
250
50
100
150
200
250
Injected
GIA Peturbation Budgets
GIA Peturbation Budgets
Pruned
(a) Attack without defense
(b) Attack with defense
(c) Illustration of GIA node
Figure I:
The lower test robustness indicates better attack performance. (a) Without defenses; GIA performs consistently better than GMA; (b) With defenses: GIA without HAO performs consistently
worse than GMA, while GIA with HAO performs the best; (c) Homophily indicates the tendency of similar nodes connecting with each other (blue & green nodes). The malicious (red) nodes and edges injected by GIA without HAO will greatly break the homophily hence can be easily identified and pruned by homophily defenders. GIA with HAO aware of preserving homophily that attacks the targets by injecting unnoticeable (more similar) but still adversarial (dark green) nodes and edges, which will not be casily pruned hence effectively causing the damage.
et al., 2018; Hou et al., 2020; Zhu et al., 2020; Yang et al., 2021 The severe damage to homophily will disable the effectiveness GIA to evaluate robustness because non-robust models can easily mitigate or even prevent GIA merely through exploiting the property of homophily damage.
Specifically, having observed the destruction of homophily, mechanism aiming to recover the homophily, which we term homophily defenders. Homophily de- fenders are shown to have strong robustness against GIA attacks. Theoretically, they can effectively reduce the harm caused by GIA to be lower than GMA. Empirically, simple implementations of homophily defenders with edge pruning (Zhang & Zitnik, 2020) can deteriorate even the state-of- the-art GIA attacks (Zou et al., 2021) (Fig. 1b). Therefore, overlooking the damage to homophily will make GIA powerless and further limit its applications for evaluating the robustness of GNNs.
straightforward to devise a defense
To enable the effectiveness of GIA in evaluating various robust GNNs, it is necessary be aware of preserving the homophily when developing GIA. To this end, we introduce a novel constraint homophily unnoticeability that enforces GIA to retain the homophily of the original graph, which can serve as a supplementary for the unnoticeability constraints in graph adversarial learning. To instantiate the homophily unnoticeability, we propose Harmonious Adversarial Objective (HAO) for GIA (Fig. lc). Specifically, HAO introduces a novel differentiable realization of homophily constraint by regularizing the homophily distribution shift during the attack. In this way, adversaries will not be easily identified by homophily defenders while still performing effective attacks (Fig. lb). Extensive experiments with 38 defense models on benchmarks demonstrate that GIA with HAO can break homophily defenders and significantly outperform all previous works across all settings, including both non-target attack and targeted attack Our contributions are summarized as follows:
We provide formal comparison between GIA and GMA unified setting and find that GIA can be provably more harmful than GMA due to its high flexibility (Theorem 1).
However, the flexibility of GIA will also cause severe damage to the homophily distribution which makes GIA easily defendable by homophily defenders (Theorem 2).
To mitigate the issue, we introduce the concept of homophily unnoticeability and novel objective HAO to conduct homophily unnoticeable attacks (Theorem 3).
2 PRELIMINARIES
2.1 GRAPH NEURAL NETWORKS
Consider graph G XX with node set V = {v1, U2, ... U, (U,, where A E {0. 1) mxnn is the adjacency matrix and X E Rexd is the node feature matrix. We are
and edge set E {er, eg,,.., ... }
"Code available in https: htt.t/gtttttttte/// wtt...////////eee...t. h.tm///.hh////aa HAH.
2

---

Published as a conference paper at ICLR 2022
interested in the semi-supervised node classification task (Jin al., 2021). That is, given the set of labels Y E 10. C 1)"" from C' classes, we can train graph neural network fo parameterized by / on the training (sub (sub)graph Guran by minimizing classification loss Luain (c.g., cross-entropy). Then the trained fo can predict the labels of nodes in test graph Gres. A GNN typically follows a neighbor aggregation scheme recursively update the node representations
H o (W&+ p((H, (H EVu) U (u})),
where (u) is the set of neighbors of node u. H/ Xu. Yu V. H!!h) is the hidden represen- tation of node u after the k-th aggregation, a(-) ) is an activation function, e.g. ReLU, and p(-) is an aggregation function over neighbors, e.g., MEAN or SUM.
2.2 GRAPH ADVERSARIAL ATTACK?
The goal of graph adversarial attack is to fool GNN model, fe., trained on graph g (A, X) by constructing a graph g' = (A', X') with limited budgets - gl Σ A. Given set of victim nodes V. S V, the graph adversarial attack can be generically formulated
min (fo (g")), s.t. || - - S
(2)
where l" arg ming Lwain (Je (9main)) and Lank is usually taken as -Lainn- Following previous works (Zügner et al., 2018; Zou et al., 2021), Graph adversarial attacks can be characterized into graph modification attacks and graph injection attacks by their perturbation constraints.
Graph Modification Attack (GMA). GMA generates g' by modifying the graph structure and the node features X of the original graph G. Typically the constraints in GMA are to limit the number of perturbations on A and X, denoted by A and Ax respectively, as:
A + 4x S A E Z, A Allo S A Z, ||X - X SEER,
where the perturbation on X is bounded by c via L-p norm, since we are using continuous features. Graph Injection Attack (GIA). Differently, GIA generates G' by injecting set of malicious nodes
X
Aatk
AT Oatk where Xank is the features of the injected nodes, Oatk is the adjacency matrix among injected nodes, and Ank is the adjacency matrix between the injected nodes and the original nodes. Let d,, denote the degree of node u, the constraints GIA are:
Vik as X'
A'
X
ark
Vaak S SAEZ, < d, Sbe E Dx S Rd Vu E Vale
(4)
where the number and degrees of the injected nodes are limited, Dx = {C e Rd, min(X)nn11 SOS max(X) .1} where min(X) and max(X) are the minimum and maximum entries in X respectively.
Threat Model. We adopt a unified setting. i.e., evasion, inductive and black-box, which is also used by Graph Robustness Benchmark (Zheng al., 2021). Evasion: The attack only happens at test time, i.e., Grest. rather than attacking Immin- Inductive: Test nodes are invisible during training. Black-box: The adversary can not access the architecture or the parameters of the target model.
POWER AND PITFALLS OF GRAPH INJECTION ATTACK
Based on the setting above, we investigate both the advantages and limitations of GIA by comparing it with GMA. While we find GIA is more harmful than GMA when there is no defense (Theorem I), we also find pitfalls in GIA that can make it easily defendable (Theorem 2).
3.1 POWER OF GRAPH INJECTION ATTACK
Following previous works (Zügner al., 2018), track the changes brought by attacks. Firstly we will elaborate the threats of an adversary as follows. Definition 3.1 (Threats). Consider an adversary A, given a perturbation budget A, the threat of A to GNN fe is defined as min Lax (f))))), i.e., the optimal objective value of Eq. 2.
linearized GNN, i.c., (k) X to
We leave more details and reasons about the setting used in this work in Appendix B.
3

---

Published as a conference paper at ICLR 2022
ani
Test Robustness
3.0
gla
Density
35
2.0
1.5
GMA
0.3
250
500
750
1000
1250
0.2
0.0
0.2
0.6
0.8
1.0
GMA Perturbation Budgets
Homophily
(a) Illustration of M2 mapping
(b) GMA GIA with M2
(c) Homophily changes
Figure 2: Power and pitfalls of Graph Injection Attack
With Definition 3.1, we can quantitatively compare the threats of different adversaries.
Theorem 1. Given moderate perturbation budgets GIA for GIA and GGMA for GMA, that is, let AGIA S. LMAA & [V| < EE for fixed linearized GNN fe trained on G. assume that has no iso- lated nodes, and both GIA and GMA follow the optimal strategy, then, V 2 0, DAGA S &GMA.
Lon((o((Coaa)) CoaksooGooma S0,
where GOLA and Goma are the perturbed graphs generated by GIA and GMA, respectively.
prove Theorem in Appendix E. Theorem implies that GIA can cause more damage than GMA with equal fewer budgets, which is also verified empirically as shown in Fig. la.
Intuitively, the power GIA mainly comes from its relatively high flexibility in perturbation gen- eration. Such flexibility enables us find mapping that can map any GMA perturbations GIA perturbations, leading the same influences to the predictions of fe. We will give an example below.
Definition 3.2 (Plural Mapping M2). M2 maps perturbed graph GOMA generated by GMA with only edge addition perturbations," 3 to GIA perturbed graph G M2 such that:
fo(Cau) = fo(Moa)) Yu
As illustrated in Fig. 2a, the procedure of M2 is, for each edge (u, v) added by GMA to attack node u, M2 can inject a new node w to connect u and v, and change X to make the same effects to the prediction empirically verify the above procedure in Fig. 2b. Details about the comparison are in Appendix C.
Then GIA be further optimized bring damage to node We also
3.2 PITFALLS IN GRAPH INJECTION ATTACK
Through M2. show that the flexibility in GIA make it more harmful than GMA when there is no defense, however, we also find sidc-effect raised in the optimization trajectory of X,, from the above example. Assume GIA uses PGD (Madry al., 2018) optimize X iteratively, we find:
sim(Xu, Xww (t+1) < Sim,X,,X,,,
(5)
where is the number of optimization steps and sim(X., X.) = [x_ 1.l.l We prove the state- ment in Appendix F.4. It implies that, under the mapping M2, the similarity between injected nodes and targets continues to decrease as the optimization processes, and finally becomes lower than that in GMA. We find this is closely related to the loss of homophily of the target nodes.
X
Before that, we will elaborate the definition of homophily graph adversarial setting. Different from typical definitions that rely the label information (McPherson et al., 2001; London & Getoor, 2014; Pei et al., 2020; Zhu et al., 2020), as the adversary does not have the access to all labels, we provide another instantiation of homophily based on node feature similarity as follows:
Definition 3.3 (Node-Centric Homophily). The homophily of a node u can defined with the similarity between the features of node u and the aggregated features of its neighbors:
ha = sim(ras Xa), Tu
Σ
Vd,yan" X,,
jEN(u)
where d,, is the degree node and sim(-) similarity metric, e.g., cosine similarity.
We focus on edge addition in later discussions since Wu et al. (2019) observed that it produces the most harm GMA. Discussions about the other GMA operations be found in Appendix E.2.

---

Published as a conference paper at ICLR 2022
We also define edge-centric homophily while will focus primarily on node-centric homophily. Details and reasons are in Appendix D.1. With Definition 3.3, combining Eq. 5, we have:
h MMM
where a and GMA denote the homophily of node after GIA and GMA attack, respectively. implies that GIA will cause more damage to the homophily of the original graph than GMA. To verify the discovery for more complex cases, we plot the homophily distributions in Fig. 2c. The blue part denotes the original homophily distribution. Notably, there an outstanding out-of- distribution (orange) part caused by GIA, compared to the relatively minor (canny) changes caused by GMA. The same phenomenon also appears in other datasets that can be found in Appendix D.2.
Having observed the huge homophily damage led by GIA, it is straightforward to devise a defense mechanism aiming to recover the original homophily, which we call homophily defenders. We theoretically elaborate such defenses in the form of edge pruning". adapted from Eq. 1:
H o(W (([1com con(u,, (u, v)-
" E EV (u)).
(7)
We find that simply pruning the malicious edges identified by a proper condition can empower homophily defenders with strong theoretical robustness against GIA attacks.
Theorem 2. Given conditions in Theorem consider GIA attack, which (i) is mapped by M2 (Def. from a GMA attack that only performs edge addition perturbations, and (ii) uses a lin- earized GNN trained with at least one node from each class in G the surrogate model, and (iii) optimizes the malicious node features with PGD. Assume that G has no isolated node, and has node features as Xx, -- eY rー IRC, where Yu the label of node u and eY, E RRd a one-hot vector with the Y, -u entry being 1 and others being O. Let the minimum similarity for any pair of nodes connected in G be 8g = (i,)E, sim( Xu, X.) with sim( (Xu: X,) [Xx.1,.lX.T."" homophily defender go that prunes edges v) Sim(Xus X.) S 8g. we have:
X. For a
Lauigo (M22(GMM))) - Lau (S(ma) 2 O.
We prove Theorem 2 in Appendix E.3. It implies that, by specifying mild pruning condition, the homophily defender can effectively reduce the harm caused by GIA to be lower than that of GMA.
Considering more concrete example with M2. Xx is generated to make Caxx(fo (G(M)) on node u at first. Then, due to the flcxibility in GIA, Xw, can be optimized to some X that greatly destroys the homophily of node i.c. having negative cosine similarity score with u. Thus, for graph with relatively high homophily, i.e., 8g 2 0, a mild pruning condition such a) (u, v) could prune all the malicious edges generated by GIA while possibly keeping some of those generated by GMA, which makes GIA less threatful than GMA.
(M(GM)))
In the literature, we find that GNNGuard (Zhang & Zitnik, 2020) serves well for an implementation of homophily defenders as Eq. 7. With GNNGuard, we verify the strong empirical robustness of homophily defenders against GIA. As Fig. lb depicts, when with homophily defenders, GIA can only cause little-to-no damage, while GMA can still effectively perturb the predictions of the target model on some nodes. To fully demonstrate the power of homophily defenders, we also prove its certified robustness for concrete GIA case in Appendix E.
4 HOMOPHILY UNNOTICEABLE GRAPH INJECTION ATTACK
4.1 HARMONIOUS ADVERSARIAL OBJECTIVE
As shown in Sec. 3, the flexibility of GIA makes it powerful while dramatically hinders its perfor- mance when combating against homophily defenders, because of the great damage to the homophily distribution brought by GIA. This observation motivates us to introduce the concept of homophily unnoticeability that enforces GIA to preserve the original homophily distribution during the attack.
AActually homophily defenders can have many implementations other than pruning edges given in Ap- pendix F, while we will focus on the design above our discussion.
5

---

Published as a conference paper at ICLR 2022
Definition 4.1 (Homophily Unnoticeability). Let the node-centric homophity distribution for graph G be Hg. Given the upper bound for the allowed homophity distribution shift Au 2 0, an attack A is homophity unnoticeable if: m(Hg, Hg.) S Di.
where g' is the perturbed graph generated by A, and m(.) is distribution distance measure.
Intuitively, homophily unnoticeability can be supplementary for the unnoticeability in graph adver- sarial attack that requires GIA adversary to consider how likely the new connections between the malicious nodes and target nodes will appear naturally. Otherwise, i.e., unnoticeability broken, the malicious nodes and edges can be easily detected and removed by database administrators or ho- mophily defenders. However, homophily unnoticeability can not be trivially implemented as a rigid constraint and be inspected incrementally like that for degree distribution (Züigner et al., 201 8). For example, a trivial implementation such as clipping all connections that do not satisfy the constraint (Def. 4.1) will trivially clip all the injected edges due to the unconstrained optimization in GIA.
Considering the strong robustness homophily defenders, we argue that they can directly serve as external examiners for homophily unnoticeability check. Satisfying the homophily constraint can be approximately seen as bypassing the homophily defenders. Obviously. GIA with constraints as Eq. 14 can not guarantee homophily unnoticeability, since will only optimize towards maximizing the damage by minimizing the homophily of the target nodes. Hence, we propose a novel realization of the homophily constraint for GIA that enforces it meet the homophily unnoticeability softly.
Definition 4.2 (Harmonious Adversarial Objective (HAO)). Observing the homophily definition in Eq. is differentiable with respect to X, we can integrate it into the objective of Eq. 2 as:"
min G
Cax(soo
Cank (g)) XC(9, 9'),
(8)
where C(g,g') is a regularization term based on homophily and X 2 0 is the corresponding weight.
One possible implementation is to maximize the homophily for each injected node as:
1
C(
by-
V
Wc VA
HAO seizes the possibility of retaining homophily unnoticeability, while still performing effective attacks. Hence, given the homophily distribution distance measure ml.) in Def. 4.1, we can infer:
Theorem 3. Given conditions Theorem 2, we huve m(Hg, H mmHg, Hgaa) ) hence:
Cask (GHo))))))) Lan S 0,
where PHAO generated by GIA with HAO, and G' is generated by GIA without HAO.
We prove Theorem 3 in Appendix E.5. Intuitively, since GIA with HAO can reduce the damage to homophily, it is more likely to bypass the homophily defenders, thus being more threatful than GIA without HAO. We also empirically verify Theorem for more complex cases in the experiments.
4.2 ADAPTIVE INJECTION STRATEGIES
GLA is generically composed of two procedures, i.c., node injection and feature update, to solve for g' = (A', X'), where node injection leverages either the gradient information or heuristics solve for A', and feature update usually uses PGD (Madry et al., 2018) to solve for X'. Most previous works separately optimize A' and X' in greedy manner, which implicitly assumes that the other will be optimized to maximize the harm. However, HAO does not follow the assumption but stops the optimization when the homophily is overly broken. Thus, more suitable injection strategy for HAO shall be aware of retaining the original homophily. To this end, we propose to optimize A' and X' alternatively and introduce three adaptive injection strategies to coordinate with HAO.
Note that only use HAO solve for g' while still using the original objective evaluate the threats.

---

Published as a conference paper at ICLR 2022
Gradient-Driven Injection. We propose novel bi-level formulation of HAO to perform the alter- native optimization using gradients, where we separate the optimization of g' = as:
X arg min Lank (fo- (A", (()) - AAC(('')))
X'E((X")
(10)
s.t. A arg min Latk (So (Jo (')) - Ax
ATE((A))
where (AA') and (X') are the corresponding feasible regions for A' and X' induced by the original constraints. Here we use different homophily constraint weights Xa and Xx for the optimizations of A' and X', since A' is discrete while X' is continuous. We can either adopt Meta- deta-gradient like Metattack (Zügner& & Günnemann, 2019) (MetaGIA) directly optimize edge weights to solve for A' (AGIA). The detailed induction of meta-gradients and algorithms are given in Appendix G.I.
Heuristic-Drivee Injection. As the state-of-the-art GIA methods are leveraging heuristics to find A' based on TDGIA (Zou et al., 2021), we also propose a variant (ATDGIA) using heuristics as:
0.9
dw 2
0.1
Su = ((1 - Pw. (arg max (p) = v(,))(
+
(1I)
vbd.,
where su indicates the vulnerability of node u and 1(-) is to early stop destroying homophily.
Sequential Injection for large graphs. Since gradient methods require huge computation overhead, we propose novel divide-and-congen strategy (SeqGIA) to iteratively select some of the most vulnerable targets with Eq. to attack. Detailed algorithm is given in Appendix G.3.
EXPERIMENTS
5.1
SETUP & BASELINES
Datasets. We comprehensively evaluate our methods with 38 defense models on 6 datasets. We se- lect two classic citation networks Cora and Citeseer (Yang et al., 2016; Giles al., 1998) refined by GRB (Zheng et al., 2021), I). We also use Aminer and Reddit (Tang et al., 2008; Hamilton et al., 201 20;7;; Zeng et al., 2020) from GRB, Arxiv from OGB (Hu et al., 2020), and co-purchasing network Com- puters (McAuley et al., 2015) to cover more domains and scales. Details are in Appendix H.1.
Comparing with previous attack methods. We incorporate HAO into several existing GIA meth- ods as well as our proposed injection strategies to verify its effectiveness and versatility. First of all, we select PGD (Madry et al., 2018) as is one of the most widely used adversarial attacks. We also select TDGIA (Zou et al., 2021) which is the state-of-the-an GIA method. We adopt the implemen- tations in GRB (Zheng et al., 2021) for the above two methods. We exclude FGSM (Goodfellow et al., 2015) and AFGSM (Wang et al., 2020), since PGD is better at dealing with non-linear models than FGSM (Madry et al., 2018), and AFGSM performs comparably with FGSM but is worse than TDGIA as demonstrated by Zou et al. (2021). For GMA methods, we adopt Metattack (Zügner & Günnemann, 2019) as one of the bi-level implementations. We exclude Nettack (Zügner et al., 2018) as it is hard to perform incremental updates with GCN (the surrogate model used in our ex- periments) and leave reinforcement learning methods such as RL-S2V (Dai et al., 2018) and NIPA (Sun al., 2020) for future work. More details are given in Appendix H.2.
Categories and complexity analysis of attack methods. We provide categories and complexity analysis of all attack methods used in our experiments in Table 7, Appendix H.3.
Competing with different defenses. We select both popular GNNs and robust GNNs as the defense models. For popular GNNs we select the three most frequently used baselines, i.e., GCN (Kipf & WWlliing 2017), GraphSage (Hamilton et al., 2017b), and GAT (Veličković et al., 2018). For robust GNNs we select GCNGuard (Zhang & Zitnik, 2020) for graph purification approach, and RobustGCN (Zhu et al., 2019) for stabilizing hidden representation approach, as representative ones following the surveys (Sun et al., 2018: Jin et al., 2021). Notably, the author-released GCNGuard implementation requires O(n²²) complexity, which is hard to scale up. To make the comparison fair, following the principle of homophily defenders, we implement two efficient robust alternatives, i.e., Efficient GCNGuard (EGuard) and Robust Graph Attention Network (RGAT). More details are given in Appendix F.2. Besides, we exclude the robust GNNs learning in a transductive manner like ProGNN (Jin et al., 2020) that can not be adapted in setting.
7

---

Published as a conference paper at ICLR 2022
Table I: Performance of non-targeted attacks against different models
Cora ())
Citeseer())
Computers(()
Arxiv(.)
HAO
Homo
Robust
Combo
Homo
Robust
Combo
Homo
Robust
Combo
Homo
Robust
Combo
Clean
85.74
86.00
87:29
74.85
T5.46
76.87
93.17
93.17
93.32
70.77
71:27
71.40
PGD
$3.08
83.08
85.74
74.70
T4.70
76.19
84.91
$4.91
91.44 11.41
68.18
G8. 18
71.11
PGD
62.60
62:60
77.99
69.05
69.05
73.04
79.33
79:33
87.83
63.48
G2.89
68. 68.68
MetaGiA
53.61
83.61
85.86
74.70
76.15
84.91
84.91
91.41
68.47
G8.47
MeuGIA
49.25
09.83
76.80
68.04
68.04
71.25
78.96
78.90 78.96
90:25
57.05
63.30
69.97
AGIA
83.44
63.41
65,78
74.72
T4:72
75.29
65.21
85.21
91.40
68.07
68.07
71.01
AGIAT
47.24
61.59
75.25
70.24
70.24
71.80
75.14
76.14
50.32
65. 62
60.82
TDGIA
83.44
63.41
65.72
74.76
T4.76
75.26
88, .22
86.32
91. 00
64.49
61.00 09
70.97
TDGIA
56.95
60.90 91
60.91 91
60.15 72
ATDGIA
63:07
65.30
74.72
74.72
76.12
03
91
69.95
66.95
71.02
ATDGIA
42.18
70.30
76.87
61.08
61.08
71.22
80.86
80.
84 60
45.59
63.30
64.31
MLP
61.75
52.49
lower sumber indicates better uttack porformance.
Rune with SeqGlAA framework on Computers and Artic,
Table 2: Performance of targeted attacks against different models
Computers(()
Arxiv(L)
Aminer( ()
Reddit(
HAD
Homo
Robust
Combo
Homo
Robust
Comsbo
Homo
Robust
Combo
Homo
Robast
Combo
Cleun
92.68
92.68
92.83
69.41
T1.59
72.09
62.78
66.7
66. 00.97
94.05
97. 15
97.13
PGD
$8.
68, 13
91.56
69.19
89.19
71.31
53. 16
53.16
56.53 31
92.44
92.64
93.03
PGD
T1.78
71.76
55.81
36.06
37
69.38
34.62
$1.62
39. 47
56.44
86. 12
$4.94
MetGTA
$7.67
67.67
91:56
28
69.25 28
52.35 $2.35
MenaGA
70.21
71.61
55.83
38
38.44
48.06
41.12
41.12
45.16
46.75
90.06
90.78
AGIA
87.07
87.37
91.58
70.06
041.50
50.50
91.62
91.62
93.66
AGIA
69.96
71.58
65.72
38.84
38.84
68.97
35.94
35.94
42. 12.06
80.69
88.
90.44
TIGIA
$7.21
67.21
66
TIGIAA
71.39
71.61
77.15
66
42.56
42.63
25.78
25.78
29
78:16
85. 0G
88. .2
AIDGIA
87.85
87.85
91.56
66.12
86.12
71.16
00.88
50.87
53.08
91.25
91.25
933.03
ATDGIA
72.00
72.53
78.35
38 28
40.81
39.47
22, 50
22. 5.
28. 91
64.09
89. 89.06
88. 11.91
ML.
84.11
52.40
32.90
70.69
"The lower number indicates betler attack performance.
Runs with SeqGIA framework.
Competing with extreme robust defenses. To make the evaluation for attacks more reliable, we also adopt two widely used robust tricks Layer Normalization (LN) (Ba et al., 2016) and an effi- cient adversarial training (Goodfellow et al., 2015; Madry et al., 2018) method FLAG (Kong al., 2020). Here, as FLAG can effectively enhance the robustness, we exclude other adversarial training methods for efficiency consideration. More details are given in Appendix H.4.
Evaluation protocol. We use a 3-layer GCN as the surrogate model to generate perturbed graphs with various GIA attacks, and report the mean accuracy of defenses from multiple runs. Details are in Appendix H.5. For in-detail analysis of attack performance, we categorize all defenses into three folds by their robustness: Vanilla, Robust, and Extreme Robust (Combo) (Table 8). To examine how much an attack satisfies the homophily unnoticeability and its upper limits, we report maximum test accuracy of both homophily defenders (Homo) and defenses from the last two categories.
5.2 EMPIRICAL PERFORMANCE
In Table 1 and Table 2, we report the non-targeted and targeted attack performance of various GIA methods, respectively. We bold out the best attack and underline the second-best attack when com- bating against defenses from each category. Full results are in Appendix J.1 and Appendix J.2.
Performance of non-targeted attacks. In Table 1. we can see that HAO significantly improves the performance of all attacks on all datasets up to 30%, which implies the effectiveness and versatility of HAO. Especially, even coupled with a random injection strategy (PGD), HAO can attack robust models to be comparable with or inferior to simple MLP which does not consider relational infor- mation. Meanwhile, adaptive injection strategies outperform previous methods PGD and TDGIA by non-trivial margin for most cases, which further indicates that they are more suitable for HAO.
Performance of targeted attack on large-scale graphs. In Table 2, HAO also improves the targeted attack performance of all attack methods on all datasets by a significant margin of up to 15%. which implies that the benefits of incorporating HAO are universal. Besides, adaptive injections can further improve the performance of attacks and establish the new state-of-thh-aar coupled with HAO.
8

---

Published as a conference paper at ICLR 2022
Model
Cora'
Computers'
Ardv
Computers'
Aminer
Reddit
Clenn
84.74
92.25 02.25
70.44
91.68
62.39
96.51
PGD
61.00
61:76
64.23
662.41
26.13
62.72
56.90
63.69
32.78
4HAO
58.51
00.29
48.45
18.62
29.91
54.14
AGLA
60.10
60. 8G
48.80
61.58
31.06
39.96
+ILAO
53.79
58.
48.36
26.51
56.36
+HAO
65.22
49.54
22.32
54.32
ATDGLA
61.14
65.07
48.
64.66
24.72
61. 61.25
0.0
0.20 476
+I[AO
58.13
63.31
44.40
59.27
17.62
56,90
Regularziation Weight
The better. NNoe-tergseed Targeted
(a) Varying À in HAO
(b) Averaged performance across all defense models
Figure 3: (a): Effects of HAO with different weights; (b) Averaged attack performance of various attacks with or without HAO against both homophily defenders and other defense models.
3.0
gla
Test Robustness
50
75
hao
70-
70
2.0
05
60
25-
1.0
Test
0.0
0.2
0.6 Homophily
1.
Node Budgets
Edge Budgets
(a) Homophily change
(b) Varying node budgets
(c) Varying edge budgets
Figure 4: (a) Homophily changes after attacked by GIA without HAO (orange) and GIA with HAO
(canny); (b), (c) Attack performance against GCN and EGuard with different node and edge budgets.
indicates attack with defenses and indicates attack without defenses;
5.3 ANALYSIS AND DISCUSSIONS
Effects of HAO. Though HAO can substantially improve GIA methods under defenses, we find essentially trades with the performance under defenses. In Fig. 3a, as the weight for regularization term À increases, HAO trades slightly more of the performance against GCN for the performance against homophily defenders. Finally, GIA reduces the performance of both GNNs with defenses and without defenses to be inferior to MLP. Additionally, as also shown in Table 3b, the trade-off will not hurt the overall performance while consistently brings benefits up 5%.
Analysis of the perturbed graphs. In Fig. 4a, we also analyze the homophily distribution changes after the attack. It turns out that GIA with HAO can effectively preserve the homophily while still conducting effective attacks. Similar analysis on other datasets can be found in Appendix D.2.
Attacks with limited budgets. We also examine the performance of GIA methods with or without HAO varying different node and edge budgets. Fig. 4b and Fig. 4c show that HAO can consistently improve the overall performance by slightly trading with the performance under no defenses.
CONCLUSIONS
In this paper, we explored the advantages and limitations of GIA by comparing with GMA. Though we found that GIA can be provably more harmful than GMA, the severe damage to the homophily makes easily defendable by homophily defenders. Hence we introduced homophily unnoticeabil- ity for GIA to constrain the damage and proposed HAO to instantiate it. Extensive experiments show that GIA with HAO can break homophily defenders and substantially outperform all previous works. We provide more discussions and future directions based on HAO in Appendix A.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank the area chair and reviewers for their valuable comments. This work was partially sup- ported by GRF 14208318 and ECS 22200720 from the RGC of HKSAR, YSF 62006202 from NSFC, Australian Research Council Projects DE-190101473 and DP-220102121.
ETHICS STATEMENT
Considering the wide applications and high vulnerability to adversarial attacks of GNNs, is impor- tant to develop trustworthy GNNs that are robust to adversarial attacks, especially for safety-critical applications such as financial systems. However, developing trustworthy GNNs heavily rely on the effective evaluation of the robustness of GNNs, i.e., adversarial attacks that are used to measure the robustness of GNNs. Unreliable evaluation will incur severe more issues such as overconfidence in the adopted GNNs and further improve the risks adopting unreliable GNNs. Our work tackles an important issue in current GIA, hence enhancing the effectiveness of current evaluation the robustness of GNNs, and further empowering the community to develop more trustworthy GNNs to benefit society. Besides, this paper does not raise any ethical concerns. This study does not involve any human subjects, practices to data set releases, potentially harmful insights, methodologies and applications, potential conflicts of interest and sponsorship, discriminatiio//iaaaaaannn concerns, privacy and security issues, legal compliance, and research integrity issues.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility our theoretical, we provide detailed proof for our theoretical discov- ery in Appendix E. Specifically, we provide detailed proof in Appendix E. I for Theorem 1, proof in Appendix E.3 for Theorem 2, and proof in Appendix E.5 for Theorem 3.
To ensure the reproducibility of our experimental results, we detail our experimental setting in Ap- pendix B.2 and Appendix H, and open source our code.
REFERENCES
Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint, #xXiv:1607.06450 2016.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song. Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.0122 2018.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. restricted black-box adversarial framework towards attacking graph embed- ding models. In The Thirty-Fourt AAAI Conference Artificial Intelligence, pp. 3389-3396, 2020.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In Proceedings of the 35th International Conference Machine Learning, pp. 1123-1132, 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. The Thirteenth ACM International Conference Web Search and Data Mining, pp. 169-177, 2020.
Fuli Feng, Xiangnan He, Jie Tang, and Tat-Seng Chua. Graph adversarial training: Dynamically regularizing based on graph structure. IEEE Transactions on Knowledge and Data Engineering, 33(6):2493-2500 2021.
10

---

Published as a conference paper at ICLR 2022
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learming for fast adaptation of deep networks. In Proceedings of the 34th International Conference Machine Learning, pp-
1126-1135, 2017.
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the 3rd ACM International Conference Digital Libraries, pp. 89- 98, 1998.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. 2016. http://wer //ww. deeplearningbnt org. org.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 40(3):52-74, 2017a.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034 1034, 2017b.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in Neural Information Processing Systems, 2018
Bo Han, Gang Niu, Xingrui Yu, Quanming Yao, Miao Xu, Ivor Tsang, and Masashi Sugiyama. SIGUA: Forgetting may make learning with noisy labels more robust. In Proceedings of the 37th International Conference on Machine Learning, pp. 4006-4016 4016, 2020a.
Bo Han, Quanming Yao, Tongliang Liu, Gang Niu, Ivor W. Tsang, James T. Kwok, and Masashi Sugiyama. A survey of label-noise representation learning: Past, present and future. arXiv preprint, arXiv:201 10111..044 .04406, 2020b.
Kurt Hornik, Maxwell B. Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366, 1989.
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard T. B. Ma, Hongzhi Chen, and Ming-Chang Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference Learning Representations, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnkk, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in Neural Information Processing Systems, 2020.
Hongwei Jin and Xinhua Zhang. Robust training of graph convolutional networks via latent pertur- bation. In Machine Learning and Knowledge Discovery in Databases, pp. 394-411, 2021.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In The 26th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 66-74, 2020.
Wei Jin, Yaxing Li. Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adver- sarial attacks and defenses on graphs. SIGKDD Explorations Newsletter, 22(2):19-34, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference on Learning Representations, 2019.
11

---

Published as a conference paper at ICLR 2022
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. FLAG: adversarial data augmentation for graph neural networks. arXiv preprint, arXiv:2010.09891, 2020.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions Paltern Analysis & Machine Intelligence, 38(03):447-461, 2016.
Ben London and Lise Getoor. Collective classification of network data. In Data Classification: Algorithms and Applications, pp. 399-416. 2014.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? International Conference on Learning Representations, 2022.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 43-52, 2015.
Miller McPherson, Lynn Smith-Lovin, and James Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 27(1):415-44) 444, 2001.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pp.
2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference Learning Representations, 2020.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2020.
Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1):1929-195) 2014.
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, urXiv:1812.10 10528, 2018.
Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung- Yu Hsich, and Vasant G. Honavar. Adversar- ial attacks on graph neural networks via node injections: hierarchical reinforcement learning approach. In The Web Conference 2020, pp. 673-683, 2020.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2014.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Aretminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 990-998, 2008
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations, 2018.
Jihong Wang, Minnan Luo, Fnu Suya, Jundong Li, Zijiang Yang, and Qinghua Zheng. Scalable attack on graph data by injecting vicious nodes. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2020.
12

---

Published as a conference paper at ICLR 2022
Xiaoyun Wang, Minhao Cheng, Joe Eaton, Cho-Jui Hsich, and Shyhtsun Felix Wu. Attack graph convolutional networks by adding fake nodes. arXiv preprint, arXiv:1810.10751, 2018.
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 Proceedings of the Twenty- Eighth International Joint Conference on Artificial Intelligence, pp. 4816-4823, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24 2021.
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. In Pro- ceedings of the twenty-Eighth International Joint Conference on Artificial Intelligence, pp. 3961- 3967, 2019a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, pp. 5449-5458, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019b.
Han Yang, Kaili Ma, and James Cheng. Rethinking graph regularization for graph neural networks. In Thirty-Fifth AAAI Conference on Artificial Intelligence, pp. 4573-4581, 2021a.
Han Yang, Xiao Yan, Xinyan Dai, Yongqiang Chen, and James Cheng. Self-enhanced gnn: Improv- ing graph neural networks using model outputs. In The International Joint Conference on Neural Networks, pp. 1-8, 2021b.
Zhilin Yang. William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33nd International Conference on Machine Learn- ing. pp. 40 48-48,270 2016.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations, 2017.
Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. In Advances in Neural Information Processing Systems, 2020.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver J. Woodford, Meng Jiang, and Neil Shah. Data aug- mentation for graph neural networks. In Thirty-Fifth AAAI Conference on Artificial Intelligence, pp. 11015-1103. 2021.
Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, and Jie Tang. Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learn- ing. Neural Information Processing Systems Track on Datasets and Benchmarks, 2021.
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 applica- tions. AI Open, 1:57-81, 2020.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1399-1407, 2019.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020.
13

---

Published as a conference paper at ICLR 2022
Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie Tang. Tdgia: Effective injection attacks on graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 2461-2471, 2021.
Daniel Züggnrr, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2847-2856. 2018
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In 7th International Conference Learning Representations, 2019.
A ADDITIONAL. DISCUSSIONS AND FUTURE DIRECTIONS
A.1 DISCUSSIONS ON HAO AND ITS LIMITATIONS
Discussions on HAO and future implications. It is widely received that it is difficult give a proper definition of unnoticeability for graphs (More details are also given in Appendix B.2.2). Based on earliest unnoticeability constraints on degree distribution changes (Zügner et al., 2018; Zügner& & Günnemann, 2019), empirical observations that graph adversarial attacks may change some feature statistics and connect dissimilar neighbors are identified, and leveraged as heuristics to develop robust GNNs (Wu et al., 2019; Entezari et al., 2020; Zhang & Zitnik, 2020; Jin et al., 2020). Though empirically effective, however, few of them provide theoretical explanations or re- late this phenomenon to unnoticeability. In this work, starting from the comparison of GMA and GIA, we identified GIA would lead to severe damage to the original homophily. Furthermore, the relatively high flexibility of GIA amplifies the destruction and finally results in the break of ho- mophily unnoticeability. The main reason for this phenomenon is mainly because of the poorly defined unnoticeability in graph adversarial attack. Without proper definition, the developed at- tacks tend to the shortcut to incur damage instead of capturing the true underlying vulnerability of GNNs. Consequently, using these attacks evaluate robustness of GNNs will bring unreliable results thus hindering the development of trustworthy GNNs.
To be more specific, due the poor unnoticeability constraint for graph adversarial learning, the de- veloped attacks tend to leverage the shortcuts to greatly destroy the original homophily, which leads to the break of unnoticeability. Thus, using homophily defenders can easily defend these seemingly powerful attacks, even with simple design, which however brings us unreliable conclusions about the robustness of homophily defenders. Essentially, HAO penalizes GIA attacks that take the short- cuts, and retain their unnoticeability in terms of homophily. Thus, HAO mitigates the shortcut issue of GIA attacks, urges the attacks to capture the underlying vulnerability of GNNs and brings us a more reliable evaluation result, from which we know simple homophily defenders are essentially not robust GNNs.
In addition, the proposed realization of unnoticeability check for adversarial attacks provides other approach to instantiate the unnoticeability. Especially for the domains that we can hardly leverage inductive bias from human, we can still try identify their homophily, or the underlying rationales/causality of the data generation process, e.g., grammar correctness, fluency and semantics for natural languages, to instantiate the unnoticeability constraint with the help of external examin- ers. Since people are likely to be more sensitive to quantitative numbers like accuracy, those external examiners can be conveniently leveraged to the corresponding benchmark or leaderboards to further benefit the community.
Limitations of HAO and future implications. Since HAO are mostly developed to preserve the homophily unnoticeability, it counters the greedy strategy of attacks without HAO that destroys the homophily to incur more damage. Therefore, it will inevitably reduce the damage of the attacks without HAO against vanilla GNNs. As observed from the experiments, we find HAO essentially trades the attack performance when against vanilla GNNs for the performance when against ho- mophily defenders. As Fig. 3a shows, the trade-off effects can be further amplified with a large coefficient lambda in HAO. As also shown by Fig. 4b and Fig. 4c, when against vanilla GNNs, com- pared with GIA without HAO, GIA with HAO show fewer threats. In certain cases, the orfde-off might generate the performance of attacks. Thus, it calls for more tailored optimization methods to solve for better injection matrix and node features in the future. Moreover, the trade-off effects
14

---

Published as a conference paper at ICLR 2022
also reflect the importance of homophily to the performance of node classifications and the utility of homophily unnoticeability, where we believe future theoretical works can further study this phe- nomenon and reveal the underlying causality for node classification or even more other downstream tasks. Thus, we can develop more robust and trustworthy neural graph models that do not depend on spurious correlations perform the task.
In addition, as homophilous graph is the most common class of graph benchmarks for node classi- fication (Yang et al., 2016; Giles et al., 1998; Hu al., 2020; Zheng et al., 2021), our discussions are mostly focused on this specific class of graphs. However, when applying HAO to other classes of graphs such as con-attributed graphs, a direct adaption of HAO may not work. Nevertheless, the underlying information for making correct predictions still resemble the homophily property, for example, in a non-attributed graph, nodes with similar structures tend to have similar labels, is still promising to introduce the node features with node embeddings, derive new definition of homophily and apply HAO. Moreover, recently disassortative graphs appear to be interesting to the community (Pei et al., 2020; Zhu et al., 2020), which exhibit heterophily property that neighbors tend to have dissimilar labels, in contrast to homophily. We conduct an investigation on this specific class of graphs and detailed results are given in Table 12, from which surprisingly find HAO still maintains the advance when incorporating various GIA attacks. The reason might be that GNNs still implicitly learn the homophily such similarity between class label
and GIA with HAO distributions (Ma et al., 2022), even without explicit definitions. To summarize, we believe future extension of HAO to other classes of graphs is another interesting direction.
Besides, the discussions in this paper are only considered the relationship between adversarial ro- bustness and homophily. However, label noises are another widely existing threats that are deserved to be paid attention to (Liu & Tao, 2016; Han et al., 2018; 2020a;b). Essentially, our discussions in Appendix B.3 are also closely related the vulnerability of GNNs to label noises, where GNNs can still achieve near perfect fitting to the datasets with full label noises. Thus, it is desirable to broader the attention and discussion to include the label noises when developing trustworthy GNNs.
A.2 MORE FUTURE DIRECTIONS
Besides the future implications inspired from the limitations of HAO, we believe there are also many promising future works that could be built upon HAO.
Rethinking the definition of unnoticeability in adversarial robustness. Though the study of adversarial robustness was initially developed around the deep learning models on image classifica- tion (Szegedy et al., 2014; Goodfellow et al., 2015; Madry et al., 2018), images and classification are far from the only data and the task we want to build neural networks for. Deep learning models are widely applied other types of data, such as natural languages and graphs, where human inductive bias can hardly be leveraged to elaborate proper definition of unnoticeability, Moreover, for more complicated tasks involving implicit reasoning, even the domain of images, the original definition of unnoticeability, i.e., L-p norm, may not be sufficient to secure all shortcuts that can be leveraged by adversaries. How to establish and justify a proper definition of unnoticeability in these domains and tasks, is critical for developing trustworthy deep learning models.
Applications to other downstream tasks. Given the wide applications of GNNs, we believe the studies on the robustness of GNNs should be extended to other downstream tasks, such as link predictions and graph clustering. Specifically, when with a different task objective, it is interesting to find whether the underlying task still depend on the homophily property and how the different optimization objectives affect the attack optimization trajectory.
Attack with small budgets. In real-life scenarios, the budgets of the adversary may be limited to small number. It is interesting to study how to maximize the damage given limited budgets and its interplay between homophily. For example, how to locate the most vulnerable targets. We show an initial example through ATDGIA.
Mix-up attack of GMA and GIA. In real-life scenarios, both GMA and GIA could happen while with different budget limits. It is interesting to see whether and how they could be combined to conduct more powerful attacks.
Injection for defense. Actually, not only attackers can inject extra nodes, defenders can also inject some nodes promote the robustness of the networks. For example, according the Proposition. 1,
15

---

Published as a conference paper at ICLR 2022
nodes with higher degrees, higher MLP decision margin and higher homophily tend more unlikely to be attacked. Hence, defenders may directly inject some nodes the promote the above properties of vulnerable nodes.
Attacks on more complicated and deep GNNs. Most existing graph adversarial works focus on analyzing linearized GNNs and apply the discoveries to more complex cases. However, with the development of deep learning and GNNs, some models with complicated structures fail to those theories. For example, methods developed by studying linearized GNNs can hardly adapt to GNNs with normalizations as also revealed from our experiments. Then they can even more hardly be adapted more complex models such as Transformers. On the other hand, most graph adversarial studies only focus on relatively shallow GNNs. Different from other deep learning models, as GNNs go deep, besides more parameters, they also require an exponentially growing number of neighbors as inputs. How the number of layers would affect their robustness and the threats of attacks remain unexplored. From both theoretical and empirical perspectives, we believe study the interplay between the number of GNN layers and homophily, in terms of adversarial robustness and threats, and how to leverage the discoveries to probe the weakness of complicated models.
very interesting to
Reinforcement Learning based GIA. Reinforcement learning based approaches are shown to ex- hibit promising performances in previous mixed settings (Dai et al., 2018; Sun al., 2020). Though we exclude them for the efforts needed to adapt them to our setting, we believe it is promising and interesting to incorporate reinforcement learning to develop more tailored injection strategies and vulnerable nodes selection. Meanwhile, it is also interesting to explore how to leverage the idea of SeqGIA proposed in Sec. reduce the computation overhead of reinforcement learning approaches and enhance their scalability.
B MORE DETAILS AND REASONS ABOUT THE GRAPH ADVERSARIAL ATTACK SETTING
We provide more details about the perturbation constraints and the threat model used in Sec. 2.2.
B. PERTURBATION CONSTRAINTS
Following previous works (Ziigner et al., 2018; Zou et al., 2021), Graph adversarial attacks can be characterized into graph modification attacks and graph injection attacks by their perturbation constraints. Moreover, we adopt standardization methods (i.e.. arctan transformation) following Graph Robustness Benchmark (Zheng et al., 2021) on input features X.
Graph Modification Attack (GMA). GMA generates g' by modifying the graph structure A and the node features X of the original graph g. The most widely adopted constraints in GMA is limit the number of perturbations on A and X, denoted by A and 4x respectively, as:
S A EZ A Allo S E IX X11x < EC
(12)
where the perturbation on X is bounded by via L-p norm, since we are using continuous features. Graph Injection Attack (GIA). Differently, GIA generates G' by injecting set of malicious nodes Vikk as:
X X ark
A
AaR
x'
A'
(13)
Onk
atk
where Xank is the features of the injected nodes, Oatk is the adjacency matrix among injected nodes, and Aax is the adjacency matrix between the injected nodes and the original nodes. Let d,, denote the degree of node u, the constraints in GIA are:
Vakl < e 1 < d. Sbe E Dx S Rd Vu E Vate
(14)
where the number and degrees of the injected nodes are limited, Dx = (C E Rd, min(X) < C < max(X).11 -1} where min(X) and max(X) are the minimum and maximum entries in X respectively. In other words, each entry of the injected node features are bounded within the minimal entry and maximal entry of the original node feature matrix, following previous setting (7ou et al., 2021).
16

---

Published as a conference paper at ICLR 2022
B.2
THREAT MODEL
We adopt unified setting which is also used by Graph Robustness Benchmark (Zheng al., 2021), that is evasion, inductive, and black-box. Next we will claborate more details and reasons for adopt- ing the setting.
B.2.1 DETAILS OF THE THREAT MODEL
Evasion. The attack only happens at test time, which means that defenders able to obtain the original clean graph Mmain for training, while testing on a perturbed graph G'. The reasons for adopt- ing the evasion setting is as shown in Appendix B.2.2.
Inductive. The training and testing of GNNs is performed in an inductive manner. Specifically, Sa trained on the (sub) training graph Gwains which is consist of the training nodes with their labels and the edges among training nodes. While during testing. the model will access the whole graph Gees = G for inferring the labels of test nodes. In particular, G is consist of all of the nodes and the edges, including Guain the test nodes, the edges among test nodes and the edges between training nodes and the test nodes. In contrast, if the training and testing is performed in transductive manner, the model can access the whole graph during both training and testing, i.e., Gurain Gest G. Since we adopt the evasion setting where the adversary may modify the 9eet during testing, the GNN has to be learned in inductive manner. More reasons are elaborated in Appendix B.2.2.
Black-box. The adversary has no information about the target model, but the adversary may obtain the graph and training labels to train surrogate model for generating perturbed graph g'.
Combining all of the above, conducting effective attacks raises special challenges to adversaries, since defenders adopt the information extracted from training graph Guain to learn more robust hidden representations (Zhu et al., 2019), or learn to drop noisy edges (Wu et al., 2019; Zhang & Zitnik, 2020; Jin et al., 2020), or even perform adversarial training (Jin & Zhang, 2021; Feng al., 2021) which is known as one of the strongest defense mechanisms in the domain of images (Good- fellow al., 2015; Madry et al., 2018).
B.2.2 DISCUSSIONS ABOUT THE THREAT MODEL
Different from images where we can adopt the inductive bias from human vision system to use nu- merical constraints, i.e., L.p norm, to bound the perturbation range (Goodfellow et al., 2015; Madry et al., 2018), we cannot use similar numerical constraints to define the unnoticeability for graphs, as they are weakly correlated to the information required for node classification. For example, previous work (Zügner et al., 2018) tries to use node degree distribution changes as the unnoticeability con- straints. However, given the same degree distribution, we can shuffle the node features to generate multiple graphs with completely different semantic meanings, which disables the functionality of unnoticeability.
Because of the difficulty to properly define the unnoticeability for graphs, adopting a poisoning setting in graph adversarial attack will enlarge the gap between research and practice. Specifically, poisoning attacks require an appropriate definition of unnoticeability so that the defenders are able to distinguish highly poisoned data from unnoticeable poisoned data and the original data. Otherwise, attackers can always leverage some underlying shortcuts implied by the poorly defined unnotice- ability, i.e., homophily in our case, to perform the attacks, since the defenders are blind these shortcuts. On the other hand, leveraging shortcuts may generate data which is unlikely to appear in real-world applications. For example, cited by linguistic papers while the attacks may modify the graphs or inject malicious nodes to make medical papers cite or be cited by lots of linguistic papers, which apparently impractical. Using these attacks to evaluate the robustness of GNNs may bring unreliable conclusions, i.c., homophily defenders in our case, which will greatly hinders the development of the trustworthy GNNs.
citation network, medical papers are unlikely cite or be
Moreover, under poor unnoticeability definition, without the presence of the original data, defend- ers have no idea about to what extent the data is poisoned and whether the original labels remain the correspondence. Furthermore, it is well-known that neural networks have universal approximation power (Hornik et al., 1989), thus can easily overfit the training set (Goodfellow et al., 2016). or even memorize the labels appeared during training (Zhang et al., 2017). As generalization from deep
17

---

Published as a conference paper at ICLR 2022
learning models graphs, GNNs tend to exhibit similar behaviors, which is shown empirically in our experiments (See Appendix B.3 for details). Thus, even trained on a highly poisoned graph, GNNs may still converge to 100% training accuracy, even though the correspondence between the data and the underlying labels might be totally corrupted. In this case, defenders can hardly distin- guish whether the training graph is perturbed hence unlikely make any effective defenses. Besides, studying the robustness of GNNs trained from such highly poisoned graphs seems to be impractical, since real world trainers are unlikely use such highly poisoned data train GNNs.
While in an evasion setting, the defenders are able to use the training graph to tell whether the incoming data heavily perturbed and make some effective defenses, even simply leveraging some feature statistics (Wu et al., 2019; Jin et al., 2020). Notably, A recent benchmark (Zheng et al., 2021) also has similar positions. Thus, we will focus on the evasion setting in this paper.
Given the evasion setting. GNNs can only perform inductive learning where the test nodes and edges are not visible during training. The reason is that, transductive learning (i.e., the whole graph except test labels is available), requires the training graph and test graph to be the same. However, it can not be satisfied as the adversary will modify the test graph, i.e., changing some nodes or edges during GMA attack, or injecting new malicious nodes during GIA attack. Additionally, inductive learning has many practical scenarios. For example, in an academic network, the graph grows larger and papers are published and added to the original network. GNN models must
larger day by day be inductive to be applied to such evolving graphs
B.3 MEMORIZATION EFFECTS OF GRAPH NEURAL NETWORKS
0.8
0.8
Accuracy
Accuracy
Accuracy
0.6
lest atc
0.6
0.5
0.4
tain
SCC
testacc
0.2
test 8cc
0.2
200
400
500
800
1000
200
400
600
800
1000
0.0
0.2
0.6
0.6
0.8
1.0
Training E Epochs
Training Epochs
Corruption Rate
(a) Original labels
(b) Random labels
(c) Partial random labels
Figure 5: Training curve of GCN on Cora with random labels
We conduct experiments with GCN (Kipf Welling, 2017) on Cora (Yang et al., 2016). The ar- chitecture we select is 2-Layer GCN with 16 hidden units, optimized using Adam (Kingma & Ba, 2015) with a learning rate of 0.01 and a L2 weight decay of 5 x 10 for the first layer. We train 1000 epochs and report the training accuracy and test accuracy according to the best validation accuracy. We randomly sample certain percent nodes from the whole graph and reset their labels. It can be seen from Fig. 5 (b) and (c) that even with all random labels, the training accuracy can reach to nearly 100%, which serves as a strong evidence for the existence of memorization effects in GNNs. In other words, even GNN is trained on a heavily poisoned graph (changes dramatically in the sense of semantic), it can still achieve good training accuracy while the defender has no way explicitly find do anything about it. That is against to the original setting and purpose of ad- versarial attacks (Szegedy et al., 2014; Goodfellow et al., 2015; Madry et al., 2018). Thus, it urges the community for proper solution the ill-defined unnoticeability current graph adversarial learning. Till the appearance of a silver bullet for unnoticeability on graphs, evasion attack can serve as a better solution than poisoning attack.
C MORE DETAILS ABOUT GIA AND GMA COMPARISON
C.I IMPLEMENTATION OF GRAPH MODIFICATION ATTACK
Following Metattack (Zügner& & Günnemann, 2019), we implement Graph Modification Attack by taking A hyper-parameter. Nevertheless, since are conducting evasion attack, we do not
18

---

Published as a conference paper at ICLR 2022
have meta- eeta-gradients but the gradient of A with respect to Lake VaCak. Each step, take the maximum entry in VaCa,, denoted with max max(Va and change the corresponding edge, if is not contained in the training graph. Then we perform the perturbation follows:
(a) If max Vack < and the corresponding entry in 0, i.e., the edge does not exist before, we will add the edge.
(b) If max(V, A 2 0 and the corresponding entry in 1, i... the edge exists before, we will remove the edge.
If the selected entry can not satisfy neither of the above conditions, we will take the next maxi- mum entry to perform the above procedure until we find one that satisfy the conditions. Here we exclude perturbations on node features given limited budgets, since Wu et al. (2019) observed the edge perturbations produce more harm than node perturbations. Besides, shown in the proof, the damage brought by perturbations on node features is at most the damage brought by a corresponding injection to the targets in GIA, hence when given the same budgets to compare GMA and GIA, can exclude the perturbations on nodes without loss of generality. Note that given the definitions of direct attack and influencer attack in Nettack (Zügner et al., 2018), our theoretical discussions are applicable to both direct GMA attack and indirect/influencer GMA attack, since the results are derived by establishing mappings between each kind of perturbations in GMA attack that are agnos- tic to these two types of GMA attacks. Moreover, the GMA attack evaluated in our experiments is exactly the direct attack. As in our case, all of the test nodes become victim nodes and the adversary is allowed to modify the connections and features of these nodes to perform the attack.
C.2 IMPLEMENTATION OF GRAPII INJECTION ATTACK WITH PLURAL MAPPING
GIA with M₂ is implemented based on the GMA above. For each edge appears in the perturbed graph produced by GMA but does not exist in the original graph, in GIA, we will inject a node to connect with the corresponding nodes of the edge. After injecting all of the nodes, then we use PGD (Madry et al., 2018) to optimize the features of the injected nodes.
D MORE HOMOPHILY DISTRIBUTIONS
D.1 EDGE-CENTRIC HOMOPHILY
In addition node-centric homophily (Def. 6), we can also define edge-centric homophily as: Definition D.1 (Edge-Centric Homophily). The homophily for an edge (u, can be defined as.
he simm Xuy Xx),
(15)
where sim(.) is also distance metric, e.g., cosine similarity.
With the definition above, we probe the natural edge-centric homophily distribution of real- world benchmarks, as shown in Fig. 6. It turns out that the edge-centric homophily distributes follows Gaussian prior. However, it seems to be improper utilize edge-centric homophily to instantiate the homophily unnoticeability for several reasons. On the one hand, edge similarity does not consider the degrees of the neighbors which is misaligned with the popular aggregation scheme of GNNs. On the other hand, edge-centric and node-centric homophily basically perform similar functionality to retain the homophily, but if considering the future extension high-order neighbor relationships, edge similarity might be harder to extend than node-centric homophily. Thus, we utilize the node-centric homophily for most of our discussions.
D.2 MORE HOMOPHILY DISTRIBUTIONS CHANGES
We provide more homophily distribution results of the benchmarks we used in the experiments for Cora, Computers and Arxiv, shown as in Fig. 7 and Fig. 8, respectively. GIA is implemented with TDGIA (Zou et al., 2021). Note that the budgets for TDGIA here is different from that in the previous sections, which utilized the budgets resulting in the maximum harm when compared with GMA. Similarly, GIA without HAO would severely break the original homophily distribution hence making GIA can easily defended by homophily defenders. While incorporated with HAO, GIA would retain the original homophily during attack.
19

---

Published as a conference paper at ICLR 2022
1.70
1.50
Densie
Density
Density
1.5
2.00
122
0.0
00
02
04
0-
0.
14
3.00
1100-.75
-250 0.25
1.00
04 Homophily
68
15
Homophily
Homophily
(a) Cora
(b) Computers
(c) Arxiv
Figure 6: Edge-Centric homophily distributions
2.4
2.3
Density
Density
Density
3.5
3.2
0.2
60
02
0.4
0.
63
50
84
-0.75 -0.5
-325
0.3
635
0.52
0.5
1.00
04 Homophily
10
Homophily
Homophily
(a) Cora
(b) Computers
(c) Arxiv
Figure 7: Homophily distributions before attack
E PROOFS AND DISCUSSIONS OF THEOREMS
E. PROOF FOR THEOREM
Theorem 1. Given moderate perturbation budgets GIA for GIA and GMMA for GMA, that is, let DGIA < DoMa < [V| < |E,, for fixed linearized GNN fe trained on assume that G has no isolated nodes, and both GIA and GMA adversaries follow the optimal strategy, then, y DDMMA 0, -DGIA S. DGMA such that:
(on(()((Ga))) Lask (Jo(G(ma)) SO
where Goia and Goma are the perturbed graphs generated by GIA and GMA, respectively.
Proof.
The proof sketch is to show that,
(a) Assume the given GNN model has & layers, there exists a mapping, that when given the same budget, i.e., Daia LUMA < [V| |E for each perturbation generated by GMA intended to attack node a by perturbing edge (u, v), or node attributes of node u or some node u that connects a within k hops, injects node Fw to attack u, and lead to the same effects to the prediction.
always map it to corresponding injection attack, that
(b) When the number of perturbation budget increases, the optimal objective values achieved of GIA monotonically non- on-increasing with respect ACIA, that
c (fo(D(())) & Chi (fo(G(
where Ch (fo(G(rn)) is the optimal value achieved under the perturbation budget of k, which is obvious.
Once prove both (a) and (b), the Can will approach to Cha (fo(GMM)) from the above as AGia approaches to AGMA, hence proving Theorem 1. Furthermore, for the flexibility of the constraints X,,, may adopt the gradient information of X with respect Lak (fo(f to further optimize X,,, and make more damages. Hence, we have Lan (fo & C (Fo())
To prove (a), the key technique is to show that, under a predefined mapping, there exist a corre- sponding injection matrix Aak along with the features of the injected nodes Xake such that the GIA
20

---

Published as a conference paper at ICLR 2022
1.-
2.2
Density
2.0
120
Density
2.5
Teo
Density
0.5
0.3
0.0
-02
0.0
0.
64 Homophily
0.6
08
10
64
-5.75 -0 90
-0.25
0.60
5.35
0:50
0.75
1.00
-02
0.0
044 Homophily
02
0.4
06
1.
Homophily
(a) Cora
(b) Computers
(c) Arxiv
Figure 8: Homophily distributions after attack
adversary can cause the same damage as GMA. The definition of the mapping mostly derives how the injection matrix is generated. While for the generation of Xat. note that all of the input fea- tures X is normalized to specific range within f-fi. fr where fr. 2 0, following previous works (Zheng et al., 2021). Thus, for any features X,, Dxx ax,, E Dx when 0 S S We will use the statement multiple times during the derivation of X Xatk
Next, we will start to prove (a). Following Wu et al. (2019), GMA, adding new connections between nodes from different classes produces the most benefit to the adversarial objective. Hence, given the limited perturbation budget, we give our primary focus to the action of connecting nodes from different classes and will prove (a) also holds for the remaining two actions, i.e., edge deletion and node attribute perturbation.
We prove (a) by induction the number of linearized layers. First of all, will show prove (a) holds for 1-layer and 2-layer linearized GNN as motivating example. The model is as fo Ω Xe with H Åxo and Z fo-
Plural Mapping M2. Here we define the mapping M2 for edge addition. For each edge perturba- insert node connect and The influence
tion pair (u,u) generated by GMA, of adversaries can be identified as follows, as θ is fixed, we may exclude it for simplicity:
In layer (I):
Clean graph:
H Σ
1
X₂
(16)
vd.de
(EN(OJU(E
GMA:
Σ
X,+ ddi +1)
X
ie (u}
(EN(HUES V dd +1)
H
Σ
1
N, + (duld,+)) +1)
Xus
i (u)
(17)
(EN(UUE vd(d++1)
H,
$ (u,u)
GIA:
Σ
vdild, X, +
Xw
ie fu
v3(d:
(EN(()U()
H
Hi,
w]
(18)
+ Vdl,
X, +
X.))
iE {w}
Vd
+1
v3"
where d; refers to the degree of node i with self-loops added for simplicity. Thus, in layer (1), to make the influence from GMA and GIA on node u equal, the following constraint has be satisfied:
3(d + X
X
(19)
Vid, + l)d, +
21

---

Published as a conference paper at ICLR 2022
which is trivially held by setting
V3
X
vd + X
(20)
Normally, GMA does not consider isolated nodes (Zügner et al., 2018; Zügner & Günnemann, 2019)
hence we have dg 2 2 and Xw E Dx. Note that can even change X to make more affects to node u with gradient information, then we may generate a more powerful perturbation this way.
Then, go deeper to layer's 2. In layer (2):
Clean graph:
24 (EN(EUU())
E
H4 Vdld
1
(21)
GMA:
H
H
Σ
+
+
u {u}
/dddd;11
d;
+
V(d, + +)d++)1)
(EN())
11,
11!
H1
Σ
+
u E (u)
Z
V dddd;+1
d++1
V(du + [](d;++1]
(EN(S)
H
Σ
vEN(())NN())
(EN()) vd((d++1)
Zun
otherwise
(22)
GIA:
Σ
H, +
H +
1
H
iE {u. v}
v dd (d, +1)
di +1
/3(d + 1)
(EN())
z!¹-
Hu:
E (u, u, w) (23)
1
1
1
H
H H"),
i {w}
Vd
+1
dd,
Similarly, to make Z Z,d, we have to satisfy the following constraint:
1
1
1
H
H"
H +
H
dg +
3(d
+1)
dg +
Vid + 1)(d +1)
v3
1
4
1
X1+
X
+
Xo+
Vdg +1 X.)
du +1
Vd
3
v3 dd +
+1
(EN(w)Ufu)
V3
Σ
X₁
+ V3X.
d, +1
(EN(u)u(u) Vd
Vd. +1
(24)
V3
VEN(U)UGU Vdi(do+1) + V(du () + )
Σ
X,
X,
Vd +1
4 X
1
Xa +
VI+ Xx)
v
du +I
vd.
V3X,
v3
X (EA(E)U(U / dd +1) Vid, + () +1)
X
+
Σ
+
do
+I
Vd.
+I
then we let X same perturbation. Similarly, infer X Dx.
(RHS - / V
1 X, +
1 vt. X.)) to get the solution of X that makes the
The following proof also applies to layer 2.
22

---

Published as a conference paper at ICLR 2022
Next, will prove that, for linearized GNN with k layers (k 1), i.e. H X once wx such that the predictions for node u is the same to that perturbed by GMA, i.e., H E(k-1) then EX w- such that Ha (k) E Here we use H to denote the prediction of GNN attacked by GMA and E' for that of GIA. Note that, once the theorem holds, we have already proven the existence for such Xw, it naturally generalizes to an arbitrary number of layers.
To be more specifie, when H
F.lk (1) need to show that, 3X 1o S.S.,
H = Σ
1
[k
1)
+
1
11
(k-1)
(1
vay + IVd,
du +
dd, + 1 IVd, +1
JEN(u)
E(k) Σ
1
E(k-1)
1
E(k- 1)
(25)
vdu + 1 dd JEN(u)
dn
dr + Iv3
H E((k)
Here make simplification re-write Eq. 25 by defining the influence score.
Definition E.1 (Influence Score). The influence score from node to u after k aggrraationn with fixed GNN following Eq. 1, is the weight for X. contributing H!)) (K)
H(k)
1hj .Xj:
(26)
JEN(M)U(
which can be calculated recursively through:
1
Σ JEA(u)U(u)
(lui 1 (8-11)
(27)
As @ is fixed here, we can simply regard _ = A Compared to the predictions after k-th propagation onto the clean graph, in GMA, H!!)) additionally influenced by node v, while in GIA, H is additionally influenced by node v and node w. Without loss of generality, we may absorb the influence from neighbors of node into that of node e. Hence rewrite Eq. 25 as the following:
( = 1iMA.. Xv.
A IGI.. X + 1GIA Xwo
(28)
A (k) (k(K)
where
(k-1) GIA
IGAA Lanns IGLA
GLAsv
JEN(w)U(u)
Then we can further simplify it as,
1 (JaMA.. IGAA,.),, IGi X
(29)
To show the existence of X that solves the above equation, it suffices to show 1he X,, E Dx. Note that 3X,, S.t.,
GlA...
* 0 and
(T(k-1) ((A-1)) = [(li- Xw.. ((--1)
(30)
Since Å 2 0, vk 2 0, we have GIAuE > O. Moreover,
Σ
(Aus 1(b-11) 7(k--1)
JEN(w)U(u)
then it is obvious that the 1 > O. Moreover, with the definition of 1 = Å it is obvious that CMM... for with degree not less than I (i.e., is not an isolated node). Hence, have (kk- I(k-1)) (k-1) and X, Dxx
((k-1) > (kb-1)
GIA...
GMA...
GIA..
23

---

Published as a conference paper at ICLR 2022
Now have proved (a) holds for edge addition. For the remaining actions of GMA, use new mapping MM that injects one node w to node u to prove (a).
For edge deletion of (u, v), given M1, may rewrite Eq. 25 for the left nodes other than as well as the equation involving - and derive the same conclusions similarly. Intuitively, for edge deletion, considering the classification probability, removing edge is equivalent enlarge the predicted classification probability for other classes, hence it fictionalizes likewise the edge addition and we can use similar proof for this action.
Besides, Mi can also apply to the perturbation of features to node u or the other neighbor nodes of within & hops, where inject node w make the same effect. In this case, can rewrite Eq. 25 and simplify it as following:
AH( T TMM A
AE(K) k) = 1 LiiA Xws
(31)
AH AAEK)
where v (u) U u), i.e., node or its h-hop neighbor, and AX, is the perturbation to the attributes of node v. Similarly, by the definition I for node v with a degree not less than (i.e., v is not an isolated node), we have I GlA 2 -.MA... hence we have J / /GAA.. S and
X E Dx-
Thus, complete the whole proof.
Theorem for other GNNs. We can extend Theorem 1 to other GNNs such as GCN, GraphSage, etc. Recall the theorem I in Xu al. (2018);
Lemma 1. Given a k-layer GNN following the neighbor aggregation scheme via Eq. 1, assume that all paths in the computation graph of the model are activated with the same probability of success p. Then the inftuence distribution for any node x E V equivalent, in expectation, the k-step random walk distribution 9 starting at node x.
To apply Lemma 1, observe that the definition of Th is analogous to random walk starting from node u. Thus, one may replace the definition of 1 here to the influence score defined by Xu et al. (2018), conduct a similar proof above with random walk score and obtain the same conclusions, given the mapping M2, for each edge addition (u, v). 3X such that
E(Ch, (fo(D))))) = E E(ch, (fo(G))))).
(32)
Though the original theorem only proves Lemma 1 for GCN and GraphSage, is obvious one can easily extend the proof in Xu et al. (2018) for aggregation scheme Eq. 1.
Cases for Less GIA Budget. can reduce GIA budgets two ways.
(a) For GMA that performs both node feature perturbation and edge addition, considering edge perturbation (u, v), M2 essentially also applies for node feature perturbations on u or e without additional budgets.
(b) It is very likely that with the mapping above, GIA will produce many similar nodes. Hence, with post-processing step merge similar nodes together and re-optimize them again, GIA tends to require less budgets to make the same or more harm than GMA. That is also reflected in our experiments as shown in Fig. lb.
E.2 GIA WITH PLURAL MAPPING FOR MORE GMA OPERATIONS
Here we explain how our theoretical results also apply to the remaining actions, i.e., edge deletion and node feature perturbation, of GMA with M2 (Def. 3.2). In the proof for Theorem 1, we have proved the existence of mappings for edge removal and node feature perturbation. Once the injected node features set to have the same influence the predictions on the targets, they can be further optimized for amplifying the damage, thus of our theoretical results can be derived similarly like that for edge addition operation.
24

---

Published as a conference paper at ICLR 2022
E.3 PROOF FOR THEOREM 2
Theorem 2. Given conditions in Theorem 1, consider a GIA altack, which (i) is mapped by M2 (Def. 3.2) from GMA attack that only performs edge addition perturbations, and (ii) uses a lin- earized GNN trained with at least one node from each class in g as the surrogate model, and (iii) optimizes the malicious node features with PGD. Assume that has no isolated node, and has node features as X C-I cY, c- E RR, where Ya is the label of node and ey,, E RR is a one-hot vector with the Yu-th entry being 1 and others being O. Let the minimum similarity for any pair of X X..X.
nodes connected in be ag (i,(, sim( (on(Xxx Xx) with sim(Xu,, X.) ||x.11alXx.111 For
homophily defender go that prunes edges (u, v) if sim(( Xx) S 8g, we have:
Lau(ge (M2(Gema)) - (ge (g (G(ma)) 2 0.
Proof. We prove Theorem 2 by firstly show the following lemma.
Lemma 2. Given conditions in Theorem 2, as the optimization on X with respect to Cask by PGD approackes, we have:
sim(Xu. Xw) & sim(( X.))
where is the number of optimization steps.
We prove Lemma 2 in the follow-up section, i.e., Appendix E.4. With Lemma 2, known that GIA is mapped from GMA with M2, X will be optimized to have the same effects as GMA at first and continue being optimized to a more harmful state, hence for the unit perturbation case as Fig. 2a, we know:
sim(Xu: Xw.) I sim(X.:: X,),
(33)
as the optimization on N approaches. Furthermore, it follows:
GIA
1 GMA
(34)
where IaA and GMA denote the homophily of node after GIA and GMA attack, respectively. Now if we go back the homophily defender go. for any threshold specified to prune the edge (u, v), as Lemma 2 and Eq. 33 indicates, direct malicious edges in GIA are more likely to be pruned by go- Let TGLA and ToMA denote the corresponding similarity between (u, w) in GIA and (u, v) in GMA, we have several possibilities compared with sg mi.)(,.)) sim X X.):
(a) TGIA S TGMA S sg: all the malicious edges will be pruned, Theorem 2 holds;
(b) TGIA 8g S TGMA: all the GIA edges will be pruned, Theorem 2 holds;
(c) 8g TGIA S TGMA: this is unlikely happen, otherwise TGLA be optimized to even case, Theorem 2 holds;
Thus, we complete our proof.
Interestingly, we can also set a specific threshold Tn for homophily defender s.t., Th 8g < O, where some of the original edges will be pruned, too. However, some of previous works indicate promoting the smoothness or slightly dropping some edges will bring better performance (Rong al., 2020; Yang al., 2021a; Zhao al., 2021; Yang al., 2021b). The similar discussion can also be applied to this case and obtain the same conclusions.
E.4 PROOF FOR LEMMA 2
Proof. To begin with, without loss of generality, we may assume the number of classes is 2 and Y, O, which can be similarly extended to the case of multi-class, With the feature assignment in the premise, let the label of node u is Y,, we have:
[1, 11=, Y, 0,
X,
(35)
1J,
Y, 1.
25

---

Published as a conference paper at ICLR 2022
After setting it to having the same influence as that in GMA following Eq. 29, have:
X (TÂMA..
TIAAN) Xg.
(36)
GLAA
Then, let C., denote the training loss Lirain on node u, we can calculate the gradient of X
dh. dL
OH (k)
8Lu
Tai.. A.
(37)
0x,
OH (k)
dx
OH
With Cross- Eross-Entropy loss, further have:
dL
= 1-1,1]".
(38)
a
Then, we can induce the update step optimizing X with respect to Lark - Lraann by PGD:
x x(() + csign(T&us.... [-1,1] -),
(39)
where 1 is the number of update steps. As the model is trained on at least nodes with indicator features following Eq. 35 from each class, without loss of generality, here we may assume @ 2 O. the optimal O would converge θ 2 Thus.
sign Sgg 1-, θ) sign( 111,
Let us look into the change of cosine similarity between node and node as:
Asim(X,, X..) a(X,, x(++1) - X,, X
(40)
where a 2 0 the normalized factor. To determine the sign of Asim(Xa Xw). we may compare X,, ((++1) with X, _ Here we expand X., x(++1) Let Xwo, Xa1 to denote the first and second element in X, respectively, we have:
Xu x((+1)= Xu Xa + signin
GIA
[- 111
X ((+1)
||xul12
(41)
X, X c (Xu1 Xun)
1|lull2 2 v X wo X x² + 2E(XwI Xwo)
where omit the sign of Ih
GlA for GIA 0 according to the definition. Recall that we let Y, 0, hence we have (Xu1 Xuo) O. Besides, following Eq. 29, have sign (Xw1
Xwo) = xin Xoo). As GMA tend to connect nodes from different classes, we further have sign Xw1 Xwo) 2 O. Comparing to X, xx(") know in Eq. 41, the numerator decreases and the denominator increases, as é 2 0, so the overall scale decreases. In other words, we have:
Asim X a(X,, x(++1) X, x 0,
(42)
which means that the cosine similarity between node and node decreases as the optimization of X,, with respect Cas processes. Thus, we complete our proof for Lemma 2.
E.5 PROOF FOR THEOREM
3. Given conditions as Theorem 2, when À 0, we have m m(Ha, Homno ) S mmHHg, Hej
hence:
Ca (Giso))))) Lau (go((a)))) < 0,
where Gl is generated by GIA with HAO, and G' is generated by GIA without HAO.
Proof. Similar with the proof for Theorem 2, we begin with binary classification, without loss of generality. With the feature assignment in the premise, let the label of node u is Y,, we have:
[1. 11 Y, 0,
X,,
(43)
11, Y, 1.
26

---

Published as a conference paper at ICLR 2022
Let Lu denote the training loss Luain node u, we look into the gradient of Xw with respect Ly:
dhn ax, 2H
tLn
aH
Thn aHl
GIA -.
(44)
ax
With Cross- Entropy loss, further have:
dL.
= 1-1,1
(45)
aH
Together with HAO, Cak = Luain + XC(g, g') by PGD:
infer the update step of optimizing X with respect to
x x ( - 1-1,11" A(1, 1 -),
(46)
where t is the number of update steps. Similarly, without loss of generality, we may assume θ 2 0. the optimization approaches, given À O, GIA with HAO will early stop to some stage that (Ih (GIA [|1 + -1=) = 0, hence similar to the proof of Theorem 2, it follows:
G
IIAO P
(47)
where GIA and HAO denote the homophily of node u after GIA and GIA with HAO attack, respec- tively. Likewise, can infer that:
Cas (go (Giso)) La (90(()))) S 0.
Thus, we complete our proof.
E.6 CARTIFIED ROBUSTNESS OF HOMOPHILY DEFENDER
Here we prove the certified robustness of homophily for a concrete GIA case. We prove via the decision margin as follows:
Definition E.2 (Decision Margin). Given a k-layer GNN, let H()) [u,c] denote the corresponding entry
in H for the class the decision margin node with class label Yu can be denoted by:
(A) [u.ya]
max H. (k) [u.c]"
my
OE (E.
Multi-Layer Perceptron (MLP) can taken as a O-layer GNN which the definition also applies. Then, specify the certified robustness as follows:
Proposition E.1 (Certified Robustness of Homophily Defender). Consider direct GIA attack uses linearized GNN trained with at least one node from each class in G, that targets at node by injecting node w connecting to u, let node features F. C-1 onehoo(((YY)) c-1 of u. be T, the decision margin of MLP on u be ",, the minimum similarity for any pair of nodes connected in the original graph be sg = (i,(), sim(X X.), homophily defender ge can defend such altacks, if -x /1+1/dd (T + (7) S 8g, and go prunes edges (u, v) s.l.,
1 1, the homophily
sim(X (xay Xnx) S --y 1 + 1/dm
(T B7),
where 3 0 are corresponding normalization factors.
Intuitively, effective attacks node with higher degrees, homophily decision margin require lower similarity between node w and u hence more destruction to the homophily of node u. GIA without any constraints tends to optimize sim(X,, X..) to even lower value. Thus, it becomes easier to find a suitable condition for go. with which it can painlessly prune all vicious edges while keeping all original edges.
27

---

Published as a conference paper at ICLR 2022
Proof. Analogous to the proof for Lemma 2, without loss of generality, we begin with binary clas- sification, normalized indicator features and Yu = as follows:
1|,, Y, = 0,
X
(48)
1-,, Y, =.
The decision margin based on k-th layer representation can be denoted by
(k) max H (b) cE cE(O,.., C-13 [u.c]]
(49)
follows the Definition E.2. In our binary classification case, we have
7
[..0
H [u,I]
(50)
where (0) is the output O-layer GNN, or MLP (Multi-Laye Perceptron). A k-layer GNN can be regarded generating new hidden representation for node by aggregating its neighbors, hence, we may induce the decision margin for a k-llaer GNN at node u as
(
(1
Σ
1 -1 Σ
TujXiluj 7 7:
(51)
jEN(N)
JEN(u)
where we can replace the influence from neighbors with homophily of node u. Observe that hu essentially indicates how much neighbors of node contribute to H (e for example, in binary case, let Ç > the corresponding normalization factor,
1 h =1
Σ (EN(N)
Tus [X + Σ JEV(a)
Jug (lux,l((Xxll))
which means,
Σ
LujX
[Xu]1] (Shu -1 Σ
(Xul(o)), (lolll)
jEN(u)
JEN(u)
replaced with X, = [1, -1jT
H (k)
H (k)
|u,1]
([ Σ IujXil -1 Σ [ug-ilpp]++
(EN(u)
JEN(w)
(52)
(1 Σ X
1
(Sha - -
Iuj (o0X)]lo[(xu1o)))) + 1(80
[Xu]1]]
(EN(u)
SEN(w)
-ho. + I(A) 7.
Hence, we have:
m H (k) [1.0] (R) = Ch., + 1(00)
where Ç 2 0 the factor of ha. With node injected, the margin can be rewritten as:
du d, + m + (()) (Xiw.o) ((w.1))-
(53)
To perturb the prediction of node u, we make m < O. hence, we have
d,
m'
+ [(k) (X (o.0) ((n < 0,
d2
d,
(0) (X
X(w,uu) 2
d, m,
(54)
du
(X X(w.o)) 2
du + (She T(())) 7)
I
28

---

and Published as a conference paper at ICLR 2022
Observe that sim Xww (X(m.0) X(m.1)) and ha 5, hence, write Eq. 54 in a clean form as
du B7),
sim uu Xw) S -a du
(55)
where a, B are corresponding normalization factors whose signs are determined by signs of 1 and 1t respectively. In other words, GIA has to optimize X satisfying the above requirement to make the attack effective, however, given the premise that all 5g mi)e sim(X.. X.) 2
-a d.+i (T + BY), a defense model go will directly prune the vicious edges satisfying the above requirement and make the attack ineffective, which is exactly what we want to prove.
F MORE IMPLEMENTATIONS OF HOMOPHILY DEFENDER
There are many ways to design homophily defenders, inheriting the spirit of recovering the origi- nal homophily. In addition edge pruning, one could leverage variational inference learn the homophily distribution or the similarity distribution among neighbors. Then we use adversarial training to train the model to denoise. Similarly, learning to promote the smoothness of the graph can also be leveraged to build homophily defenders (Zhao et al., 2021; Yang et al., 2021a;b), Be- sides, outlier detection can also be adopted to remove or reduce the aggregation weights of malicious edges nodes. In the following two subsections, we will present two variants that perform better than GNNGuard (Zhang & Zitnik, 2020).
F.1 DETAILS OF EFFICIENT GNNGUARD
The originally released GNNGuard requires (n²²) computation for node-node similarity, making prohibitive to run on large graphs. To this end, we implement an efficient alternative of GNNGuard adopting similar message passing scheme, let r be the threshold to prune an edge:
H oWW
Ouj (111111)
(56)
HEN(uju(u)
where
Zuj
Quj softmax
EnEN(w)U(u) Zue )
1sim(H (k-1) (k- 1)) > r} sim(H 1), H! (1-1)) (k-1)
u u$1 j, EveN(w) 1sim((!)) (h-1) Hu (k-1)) 1)) > J sim 11 11-1) 11! 1)
Zuj
u = j.
Emer(w)) 1(sim( (K-1) H ( +1
Essentially, it only requires OEE) complexity. We will present the performance of Efficient GNN-
Guard (EGNNGuard) table
F.2 DETAILS OF ROBUST GRAPH ATTENTION NETWORK (RGAT)
We introduce another implementation of Robust Graph Attention Network (RGAT). We adopt the same spirit of GCNGuard (Zhang & Zitnik, 2020), that eliminates unlike neighbors during message passing based on neighbor similarity. Specifically, we change the standard GAT (Veličković et al., 2018) attention mechanism
1 ffsim r.)) 2 r)
Oi ExEN(OU0 1 21, xx) 2
Additionally, we also adopt the idea of RobustGCN (Zhu et al., 2019) that stabilize the hidden representations between layers,
add Layer Normalization (Ba al., 2016) among layers of RGAT. Empirical experiments show that RGAT is a more robust model with or without GIA attacks. For more details, we refer readers to Table 3.
29

---

Published as a conference paper at ICLR 2022
Table Performance homophily defenders used in experiments
Model
Natural Accuracy
Test Robustness
Running Time
GNNGuard
83.58
64.96
1.76 10 3
EGNNGuard
84.45
64.27
5.39 10
RGAT
85.75
66.57
6.03 x 10
GCN
84.99
36.62
5.87 10
F.3 PERFORMANCE OF HOMOPIΙLY DEFENDERS
We test the performance of different homophily defenders on Cora. Natural Accuracy refers to the test accuracy on clean graph. Test Robustness refers their averaged performance against all the attacks. Running time refers to their averaged running time for one training epoch. We repeat the evaluation 10 times to obtain the average accuracy. We can see that EGNNGuard has competitive performance with GNNGuard while 20x faster. RGAT performs slightly better and 10x faster. Hence, for large graphs and adversarial training of GNNGuard, we will use EGNNGuard instead.
G MORE DETAILS ABOUT ALGORITHMS USED
Here we provide detailed descriptions of algorithms mentioned in Section. 4.2.
G.1 DETAILS OF METAGIA AND AGIA
G.1.1 INDUCTION OF META GRADIENTS FOR METAGIA
With the bi-level optimization formulation of GIA, similar to meta-attack, we can infer the meta- gradients follows:
meta V Au Cank(uu (Auk, Xaik); Xak optx, Lank (So- (Antk, Xmn)).
(57)
Consider the opt process, have
x(++1)
x-()) aV x/O Lank (fo- (Aatk, x((1)).
(58)
With that, we can derive the meta-gradient for Amx:
V An Latk(fe (A Xzx)
Ast
V
Vx.a Cark(for (Autk, x(1)) IV Am (Aulk, x-11) + xo for (Aulk (Auis x-11)
V Aus
x-11)
ack
(59)
where
Aut
((++1) atk
Aua x(()
av Am V xlo Lank (Anik x((1)).
(60)
Note that x(1) depends on Aatk according to Eq. 58, so the derivative w.r.. Aatk need to be traced back. Finally, the update schema for A.s. is follows:
A (++1) = (1) A meta
(61)
Directly computing the meta gradients is expensive, following Metattack, adopt approximations like MAML (Finn et al., 2017) for efficiency consideration. We refer readers to the paper of Metat- tack for the detailed algorithms by replacing the corresponding variables with those above.
G.2 DETAILS OF AGIA
For optimizing weights of edge entries in Aaks PGD (Madry et al., 2018) or other optimization methods leveraging gradients. For simplicity, we PGD to illustrate the algorithm description of AGIA follows:
either Adam (Kingma & Ba, 2015),
30

---

Published as a conference paper at ICLR 2022
Algorithm 1: AGIA: Adaptive Graph Injection Attack with Gradient
Input: A graph = = (A, X), trained GNN model fø-. number injected nodes c, degree budget b, outer attack epochs Cvtter, inner attack epochs for node features and adjaceney
matrix exX e "inner 'ineer learning rate 7), weight for sparsity penalty 3, weight for homophily
penalty A;
Output: Perturbed graph G = (A', X');
Random initialize injection parameters (Aar, Xak);
Y orig t fo- X /* Obtain original predictions on clean graph +/ Conter do Random initialize X
for epoch
for epoch +- 10 Cnner do
A' + A Aatk, X XI Xatk
Xask + Clip Clip (immn maax) (Xak - 11 Vx,a (Fak))
for epoch + to C do
A' + A Aatk. X t X Xatk
Aatk + Clip (0,1) (Ami 77 Am (Ca)))
10
Ant - Il arg max bl AAun)i;:)
11
Here, Ci refers the objective GIA with HAO for the optimization of Xask For the optimization of Aak. we empirically find the ÅA would degenerate the performance, which we hypothesize that because of the noises as Ank discrete variable. Hence, we set dA = our experiments. Additionally, we introduce sparsity regularization term for the optimization of Aaki
1
CA Cack +
Σ 16
(62)
|ack
Besides, we empirically observe that Adam performs better than PGD. Hence, we would use Adam for AGIA in our experiments, and leave other methods for future work. Adopting Adam addition- ally brings the benefits to utilize momentum and history information to accelerate the optimization escape from the local optimum, which PGD fails to achieve.
G.3 DETAILS OF SEQGIA
Since gradient methods require huge computation overhead, we propose novel dlvidd-and-congeeee strategy to iteratively select some of the most vulnerable targets with Eq. 11 to attack. Note that is different from traditional sequential injection methods which still connect the targets in full batch.
31

---

Published as a conference paper at ICLR 2022
For simplicity, also illustrate the algorithm with PGD, and may switch to other optimizer such as Adam to optimize Aai- The detailed algorithm is as follows:
Algorithm 2: SeqGIA: Sequential Adaptive Graph Injection Attack
Input:
graph (A, trained GNN model fe-, number of injected nodes k, degree budget b, outer attack epochs Soater, inner attack epochs for node features and adjacency matrix
e exx eineer iinerr learning rate 7), weight for sparsity penalty 3, weight for homophily penalty X. sequential step for vicious nodes Yark sequential step for target nodes % Output: Perturbed graph G' (A', (A):
Initialize injection parameters (Aakk Xatk;;
Yoig f- fo. (A, :):
/+ Obtain original predictions clean graph */ while Not Injecting All Nodes do Natk < Yank |vakl: n. +- "/ *
[Val;
Ranking and selecting ne targets with Eq. 11;
Random initialize ( E RRtexna X for epoch <- to Couter do
aik E RRaaxd;
aik
for epoch + 0 10 inner do
A' + A Aask A aik
(cur) X X X X X
(cur).
x x(cur) + Clip (1ip(xmmi #maoe)
(x (cur)
V (car) (Cax))
for epoch t 0 to efteer do
11
A' + A || Aatk || A (cur) (cur)
X' X Xank x
12
(cur)
(l. (A
V (1x) (Cak))
ark
17.
A (cur)
+ || arg cax of (cur)
14
ank(..))
Am Aatk A (cu); Xax= a ||
X ank
(ccur)
15
Actually, one may also inject few nodes via heuristic based algorithms first, then inject the left nodes with gradients sequentially. Assume that nodes are injected by heuristic, may further optimize the complexity from
(1V VVl + Couter (c Ve Velneel Vark
Vank Nv.)
Yark
1
( (IVal log [V|++ VaLk bb + ex Vark (d) Nv.
Yatk
1
(1 a) ([Val log Vol+e ( Vol I + e Vack Nv:)
Tatk
in Table 7.
H MORE DETAILS ABOUT THE EXPERIMENTS
H.1 STATISTICS AND BUDGETS OF DATASETS
Here we provide statistics of datasets used in the experiments as Sec. 5.1. The label homophily utilizes the previous homophily definition (Zhu et al., 2020), while the avg. homophily utilizes the node-centric homophily based on node similarity.
Following previous works (Zou et al., 2021; Zheng et al., 2021), heuristically specify the budgets for each dataset according to the the number of target nodes and average degrees.
For targeted attack, we follow previous works (Zügner et al., 2018) to select 800 nodes targets according to the classification margins of the surrogate model. Specifically, we select 200 nodes with the highest classification margin, 200 nodes with lowest classification margin and 400 randomly. For the budgets, we scale down the number of injected nodes and the maximum allowable degrees accordingly.
32

---

Published as a conference paper at ICLR 2022
Table 4: Statistics of datasets
Datasets
Nodes
Edges
Classes
Avg. Degree
Label Homophily
Avg. Homophily
Cora
2680
5148
7
3.84
0.81
0.59
Citeseer
3191
4172
6
2.61
0.74
0.90
Computers
13, 752
245, 861
10
35.76
0.77
0.31
Arxiv
169, 343
1, 166, 243
40
13.77
0.65
0.86
Aminer
659, 574
2,878, 577
18
8.73
0.65
0.38
Reddit
232,
20,606,999
41
99.65
0.78
0.31
Table Budgets for non-targeted attacks on different datasets
Datasets
Nodes
Degree
Node Per:(%)
Edge Per.(%)
Cora
60
20
2.24%
23.31%
Citeseer
10
2.82%
21.57%
Computers
300
150
2.18%
18.30%
Arxiv
1500
100
0.71%
10.29%
Table 6: Budgets of targeted attacks different datasets
Datascts
Nodes
Degree
Node Per.%%
Edge Per.%%)
Computers
100
150
0.73%
6.1%
Arxiv
120
100
0.07%
1.03%
Aminer
150
50
0.02%
0.26%
Reddit
300
100
0.13%
0.26%
H.2 ADDITIONAL DISCUSSIONS ABOUT ATTACK BASELINES
For the selection of attack baselines, from the literature reviews (Sun et al., 2018; Jin et al., 2021), existing reinforcement learning (RL) based approaches adopt different settings from ours, which either focus the poisoning attack, transductive learning, edge perturbation or other application tasks. Even for NIPA (Sun et al., 2020) which has the closest setting to ours, since it focuses on poisoning and transductive attack, and the features of the injected nodes generated heuristically according to the labels assigned by the RL agent, without author released code, the adaption requires lots of efforts including redesigning the markov decision process in NIPA, hence would like to leave them for future work. More discussions on RI. based future works are given in Appendix A.2.
H.3 COMPLEXITY OF ALGORITHMS
Here we provide complexity analyses of the GIA algorithms used in the experiments as discussed and selected in Sec. 5.1. As also defined in algorithm description section from Appendix G, exx is the number of epochs optimized for node features, b the number of maximum degree of vicious nodes, d is the number of feature dimension, Nv. is the number of k-hop neighbors of the victim nodes for perform one forwarding of a k-layer GNN, comer the number of epochs for optimizing Aatt Te is the ratio of target nodes to attack in one batch, Yatk is the ratio of vicious nodes to inject in one batch.
H.4 DETAILS DEFENSE BASELINES
Here we provide the categories of defense models used in the experiments Sec. 5.1. We categorize all models into Vanilla, Robust and Extreme Robust (Combo). Basically, popular GNNs are belong to vanilla category, robust GNNs are belong robust categorty, and a robust trick will enhance the robust level by one to the next Category. Consistenly to the observation in GRB (Zheng et al., 2021), find adding Layer Normalization (Ba et al., 2016) before or between convulotion layers can enhance the model robustness. We use LN to denote adding layer norm before the first convulotion layer and LNi denote adding layer norm between convulotion layers.
33

---

Published as a conference paper at ICLR 2022
Table Complexity of various attacks
Type
Algorithm
Time Complexity
Space Complexity
MetaGIA
OlVV (aVaa// (agge// Seu Ma N1,
[[]l) + diVal No.
AGIA
Ol (ed Vall (efter o No. + (Vall))
O(]V]]|Val a Mll No.))
SegAA
O(toze logt V.D i Aella) (nden ohe Jd(ie i (Hall)))
Ohnlli Vaal 1 C 4(1Va)) Ny.))
PGD
Oi b++ (ual+ +o;.)
O0 di Vol No.))
O(())) log M. (Kalb oialll Midl Ne.))
O0 "(ad Ny.))
Heuristic
ATIGIA
log/V (aal0 oN "/Vd My.))
00%4a Maa Ny.1)
Table 8: Defense model categories
Model
Category
Model
Category
Model
Category
Model
Category
Vanilla
GCN+LN
Rebust
GCN+LNi
Robust
GCN+FLAG
Robust
GCN+LN+LNi
Combo
GCN-FLAGHLN
Combo
GCN+FLAG+LNi
Combo
GCN+FLAGHLN-LN
Combo
Sage
Vanilla
SagetLN
Robust
Sage+LNi
Robust
Sage+FLAG
Rohust
Sago+LN+LNi
Combo
Sug++FLAGHLN
Sago+FLAG+LNI
Combo
Sago+FLAGHLNHLNI
Combo
GAT
Vanilla
GAT+LN
Robust
GAT+LN:
Robust
GAT+FLAG
Robust
GAT+LN+LNi
Combo
GAT+FLAG+IN
Combo
GAG+FLAGG+LI
Combo
GAT4FLAGGLNNINI
Combo
Guard
Robust
Guar+LLN
Combo
GuadHLNi
Combo
EGuad+FFLAG
Combo
GuardeLNvLA
Comho
RGund-FL.AG FLAGLN
Comho
EGundd
Combo
RGunI-FFLAGHLNAAI
Combo
RGAT
Robust
RGAT+LN
RGAT+FLAG
Combo
RGAT-ELAG-LN
Combo
RohustGCN
Robust
RobLsGGN+FLLGG
Comho
H.5
DETAILS OF EVALUATION AND MODEL SETTINGS
H.5.1 MODEL SETTING
By default, all GNNs used in our experiments have 3 layers, hidden dimension of 64 for Cora, Citeseer, and Computers, a hidden dimension of 128 for the rest medium to large scale graphs. We also adopt dropout (Srivastava et al., 2014) with dropout rate of 0.5 between each layer. The optimizer used is Adam (Kingma & Ba, 2015) with a learning rate of 0.01. By default, we set total training epochs as 400 and employ the early stop of 100 epochs according to the validation accuracy. For the set of threshold in homophily defenders, the threshold which performs well on both the clean data and perturbed data. By default, we set the threshold 0.1, while for Computers and Reddit, Citeseer and Arxiv we use 0.2 for RGAT.
use PGD (Madry et al., 2018) to find
0.15 for Guard and EGuard, and for
For adversarial training with FLAG (Kong al., 2020), we set the step size be 1 10-3, and train 100 steps for Cora, 50 steps for Citeseer, 10 steps for the rest datasets. We empirically observe that FLAG can enhance both the natural accuracy and robustness of GNNs. We refer readers the results for more details in Sec. J.1 and Sec. J.2.
H.5.2 EVALUATION SETTING
For final model selection, we select the final model with best validation accuracy. For data splits, we follow the split methods in GRB (Zheng et al., 2021) which splits the datasets according to the node degrees, except for non-targeted attack on Arxiv where we use the official split to probe the performances of various methods in a natural setting. For non-targeted attack, following previous works (Zou et al., 2021; Zheng et al., 2021), we select all test nodes targets. While for targeted attacks, we follow previous works (Zügner et al., 2018) to select 200 nodes with highest classifica- tion margin and lowest classification margin of the surrogate model. Then randomly select 400 nodes as targets. In other words, there are 800 target nodes in total for targeted attack. Note for tar- geted attack, the natural accuracy on the target nodes might be different from normal test accuracy.
34

---

Published as a conference paper at ICLR 2022
We also follow previous works specify the attack budgets as Table. 5 for non-targeted attack and Table. 6 for targeted attack.
During evaluation, follow the black-box setting. Specifically, firstly use the surrogate model to generate the perturbed graph, then we let the target models which has trained on the clean graph to test the perturbed graph. We repeat the evaluation for 10 times on Cora, Citeseer, Computers, and Arxiv, and times for Aminer and Reddit since model performs more stably on large graphs. Then we report mean test accuracy of the target models on the target nodes and omit the variance due to the space limit.
H.5.3 ATTACKS SETTING
By default, we use PGD (Madry et al., 2018) to generate malicious node features. The learning step is 0.01 and the default training epoch is 500. We also employ the early stop of 100 epochs according to the accuracy of the surrogate model on the target nodes. While for heuristic approaches such as TDGIA (Zou et al., 2021) and ATDGIA, Empirically, we find the original TDGIA feature update suits better for heuristic approaches while they show advance over PGD for other approaches. Besides, Table 7 shows, MetaGIA requires huge amount of time originally. Thus, to scale up, we use batch update which updates the injected edges by step size of b, i.e., the maximum degree of injected nodes, and limit the overall update epochs by /aak// /6, where we empirically observe this setting performs best in Cora hence we stick for the other datasets.
follow the setting of TDGIA update the features.
For the setting of A for HAO, we search the parameters within 0.5 to 8 by a step size of 0.5 such that the setting of X will not degenerate the performance of the attacks on surrogate model. Besides heuristic approaches, we additionally use a hinge loss to stabilize the gradient information from Lark and C(G, where the former can be too large that blurs the optimization direction of the latter. Take Cross Entropy with log _softmax as example, adopt the following to constrict the magnitude of Laki
exp(H (u.oo)
Cakk|a] = (- (-H(k) [u,Yu] 1f
2 r}
exp(HT(h)
(u.s]
(63)
exp( H. (k) [1,i]
+ log(
exp( (H)(H(() [u,i]
1f
2 +))),
Σ, exp (1)
where 1{ exp(HL
(.
2 h can be taken the predicted probability for Y, and r is the
Σ, (xp))
corresponding threshold for hinge loss that we set as 10
For the hyper-parameter setting of our proposed strategies in Sec. 4.2, we find directly adopting in PGD for λx and setting ÅA = O performs empirically better. Hence we stick to the setting for AA and Ax. For the weight of sparsity regularization term in AGIA, we directly adopt 1/b. For the hyper-parametert in heuristic methods, we directly follow TDGIA (Zou et al., 2021). For SeqGIA, we set Yank be min(0.2, ||V2l/2b] and 7e- = min([Ve], Yau Van (6) by default.
H.6 SOFTWARE AND HARDWARE
We implement our methods with PyTorch (Paszke et al., 2019) and PyTorch Geometric (Fey & Lenssen, 2019). We ran our experiments on Linux Servers with 40 cores Intel(R) Xeon(R) Silver 4114 CPU @ 2.20GHz, 256 GB Memory, and Ubuntu 18.04 LTS installed. One has NVIDIA RTX 2080Ti graphics cards with CUDA 10.2 and the other has 2 NVIDIA RTX 2080Ti and 2 NVIDIA RTX 3090Ti graphics cards with CUDA 11.3.
I MORE EXPERIMENTAL RESULTS
In this section, provide more results from experiments about HAO to further validate its effec- tiveness. Specifically, we provide full results of averaged attack performance across all defense models, well initial experiments of HAO on two disassortative graphs.
35

---

Published as a conference paper at ICLR 2022
Table 9: Full averaged performance across all defense models
Model
Cora
Citeseer!
Computers
Arxiv
Arxiy
Computers"
Aminer
Reddit
Clean
84.74
74.10
92.25
70.44
70.44
91.68
62.39
95.51
PGD
61.09
54.08
61.75
54.23
36.70
62.41
26.13
62.72
+HAO
56.63
48.12
59.16
45.05
28.48
59.09
22.15
56.99
MetaGIA
60.56
53.72
61.75
53.69
28.78
62.08
32.78
60.14
+HAO
58.51
47.44
60.29
48.48
24.61
58.63
29.91
54.14
AGIA
60.10
54.55
60.66
48.86
32.68
61.98
31.06
59.96
+HAO
53.79
48.30
58.71
48.86
29.52
58.37
26.51
56.36
TDGIA
66.86
52.45
66.79
49.73
31.68
62.47
32.37
57.97
65.22
46.61
49.54
22.04
59.67
22.32
54.32
ATDGIA
61.14
49.46
65.07
46.53
32.08
64.66
24.72
61.25
+HAO
58.13
43.41
63.31
44.40
29.24
59.27
17.62
56.90
The lower better. Non-taageetd attack. *Targeted attack.
I.1
FULL RESULTS OF AVERAGED ATTACK PERFORMANCE
In this section, we provide full results of averaged attack performance across all defense models, as supplementary for Table 3b.
1.2 MORE RESULTS ON DISASSORTATIVE GRAPHS
In this section, we provide initial investigation into the non-targeted attack performances of various GIA methods with or without HAO on disassortative graphs. Specifically, we select Chameleon and Squirrel provided by Pei et al. (2020). Statistics and budgets used for attack are given in Table 10 and Table 11.
Table 10: Statistics of the disassortative datasets
Datasets
Nodes
Edges
Classes
Avg. Degree
Label Homophily
Avg. Homophily
Chameleon
2277
31, 421
27.60
0.26
0.62
Squirrel
5201
198, 493
76.33
0.23
0.58
We also heuristically specify the budgets for each dataset according the the number of target nodes and average degrees.
Table 11: Budgets for non-targeted attacks on disassortative datasets
Datasets
Nodes
Degree
Node Per(%%
Edge Per(%%)
Chameleon
100
2.641%
19.10%
Squirrel
90
50
1.73%
2.27%
For the settings of hyperparameters in attack methods and evaluation, we basically follow the same setup as given in Appendix H.5. In particular, we find using a threshold of 0.05 for homophily defenders work best on Chameleon. Besides, performances of GNNs on these graphs. For example, we observe that using a large step-size of FLAG may degenerate the performances of GNNs on these datasets, hence we use a smaller step- size of x 10 as well as a small number of steps of 10. Moreover, using LN before the first GNN layer may also hurt the performance. For fair comparison, we remove these results from defenses. Finally, in Table 12, report both categorized defense results as Table well the averaged attack performance as Table 3b.
also observe robust tricks can not always improve
From the results, we observe that, although our methods are not initially designed for disassortative graphs, HAO still brings empirical improvements. Specifically, on Chameleon, HAO improves the attack performance up to 25% against homophily defenders, up to 12% against robust models, up to 10% against extreme robust models, and finally brings up to 3% averaged test robustness of all models. While Squirrl, the improvements become relatively low while still non-trivial. For
36

---

Published as a conference paper at ICLR 2022
Table 12: Results of non-targeted attacks on disassortative graphs
Chamelcon (L)
Squirrel())
HAO
Home
Robust
Combo
AVG.
Homo
Robust
Comba
AVG.
65.18
64.92
37.33
45.87
40.04
....oo..........................
................................
................................
................................
-
................................
61.89
40.54
26.03
PGD
52.78
07.87
59.31
38.00
33.32
39.36
35.83
26.37
MetaGIA
61.89
61.89
63.61
34.38
35.66
35.66
39.40
26.09
MetaGIA
49.25
55.83
55.73
33.63
34.07
38.26
35. 24
25.81
AGIA
61.89
61.89
63.61
35.95
35.66
35.88
39.93
26.93
AGIAT
13.98
18 88
53.33
32.03
35.69
36.
36.10
26.77
TDGIA
61.95
61.95
63.76
41.17
35.66
35.66
40.81
29.02
51.12
35.63
ATDGIA
61.95
61.95
63.76
41.11
35.06
35.66
41.62
29.62
ATDGIA
36.93
57.75
59.25
38.88
32.02
10.00
40.62
30.24
MLP
50.15
32.51
The lower number indicates better attack performance.
RRns with SeqGIA framework on Computers and Arxiv.
Table 13: Detailed results of non-targeted attacks on Cora (1)
Gua
BOATWRLNGEN
Gesitt
Clean
81.45
84.17
85.9
79.56
87.23
86.37
86.21
85.23
81.72
85.06
PGD
82.53
85.04
85.74
70.74
70.78
71.10
69.57
79.50
81.41
$5.35
MeaGIA
82
83.0
85.0
70.51
75.16
00.3 72
00.4
78:01
81.50
$5,
+1IN
00.49
25.92
06.83
05.02
06.55
71
76.8
57.75
55.35
56.77
MGIA
82.75
88.00
86.78
79.56
79.30
76.25
69.
02:76
60.96
TDGIA
83.15
83.05
80.72
79.13
82.37
79.31
76.11
82.2
81.37
85.39
+HAD
77.03
73.56
76.47
73.07
75.18
79.45
78.63
69.55
64.86
05.31
ATDIGIA
74.43
71.86
71.21
66.97
72.51
76.57
60.61
02.38
AVG
70.29
77.96
77.74
74.99
74.89
74.63
74.22
72.90
72.77
72.74
example, HAO improves the attack performance up to 4% terms test robustness against ho- mophily defenders. We hypothesize the reason why HAO also works disassortative graphs is because GNN can still learn the homophily information implicitly, e.g., similarity between class label distributions (Ma al., 2022), which we will leave the in-depth analyses future work.
J DETAILED RESULTS OF ATTACK PERFORMANCE
J.1 DETAILED RESULTS OF NON-TARGETED ATTACKS
In this section, we present the detailed non-targe targeted attack results of the methods and datasets used in our experiments for Table For simplicity, we only give the results of top 20 robust models according to the averaged test accuracy against all attacks.
J.2 DETAILED RESULTS OF TARGETED ATTACKS
In this section, we present the detailed targeted attack results of the methods and datasets used in our experiments for Table For simiplicity, we only give the results of top 20 robust models according to the averaged test accuracy against all attacks.
37

---

Published as a conference paper at ICLR 2022
Table 14: Detailed results of non-targeted attacks on Cora (2)
BGATTFIAA
RebeoDoN
CEN-INWATLNG DONITEATENN
RIGT
CAT-LNHHEE
Guant
GENSLNWIN
85.74
81.95
PGD
76.93
83.11
63.20
62.55
60.08
79.24
61.29
61.84
83.08
58.46
63.60
62:34
44.02
MetaGIA
75.14
83.08
63.53
58.
60.36
77.97
$7.60
61.01
83.61
58.10
67.00
AGIA
76.04
83,08
02.67
61.26
50.00
78.95
84
58 61
63.44
57.05
+HAO
67:17
49.12
61.09
62.65
50:25
47:24
69:80
59.56
30.87
56.62
TDGIA
82.02
83.04
71.34
71.30
73.47
81.79
71 12.52
70.30
63.44
70:60
+1A0
70.52
67.04
73.38
73.32
75.00
30.95
71.96
71.56
50.79
72.90
ATDIGA
79.06
82.85
66.96
69.61
65.89
79.91
65.57
63.81
63.07
02.95
+HA0
61.50
55.13
70.30
72:46
70.94
42.18
69:26
07.59
10.46
65.53
AVG
72.04
70.97
68.18
68.09
67,22
66.53
66.39
66.11
65.53
64.23
Table 15: Detailed results of non-targeted attacks on Citeseer (1)
PGD
71.00
71.32
75.19
74.21
09.33
T3.55
89.
74.85
73.57
57.97
+HLN
71.00
70.82
96.07
73.04
09.05
01.55
05.78
50.01
47.58
58.77
MenGTIA
70.52
70.21
75.15
74.21
68.42
73.55
68.30 00
74.83
73.57
56.36
+HAD
70.37
84.00
08.02
63.10
46.95
67.17
70.29
74.83
72.01
06.50
+EENO
71.80
70.70
64.34
70.58
70.24
50.32
62.51
50.33
46.77
58.02
TDGIA
72.29
73.81
70.25
74.21
70..8
73.05
73.34
74.85
73.07
63.01
.HAD
72.51
70.18
08.04
56.60
60.01
60.70
53.30
06.73
02.80
06.02
ATDIGA
72.25
72.82
75.12
74.21
70.61
73.55
72.57
74.82
23.54
61.35
4HAD
53.76
61.20
64.04
AVG
71.75
71.41
70.00
60.98
68.41
66.21
64.42
62.48
61.42
Table 16: Detailed results of non-targeted attacks Citeseer (2)
GnslsLN
OarisLNi
Gard
GEN-LN+FLAG
OAT-LN-
GONGENHAN
Squ-LN-FLLA
Clean
73.97
74.41
75.87
74.78
75.45
73.89
75.60
75.46
74.65
73.70
74.07
53.81
74.70
47.56
45.00
40.69
40:11
+HAD
18.18
38.91
51.10
33.53
19.19
16.5
$1.06
39.72
40.79
$0.88
MetaGiA
74.07
74.28
53.11
74.70
47.14
46.13
44.76
30.84
40.87
40.13
+HAO
45.32
38.98
50.85
33.95
19.03
46.42
44.08
39.79
41.02
00.90
AGIA
74.07
74.29
50.12
74.72
47.30
46.
44.07
40.16
41.76
40.73
TDGIA
74.07
74.28
55.01
74.76
49.47
47.06
41.08
37.94
40.68
36.21
+HAD
36.83
36.50
60.37
26.45
57.45
49.74
47.44
43.95
40.83
ATDIGA
76.07
74,21
51.95
74.72
65.09
11.89
36.24
34.65
32.10
31.17
+HAO
30.21
28.74
55.40
21.70
52.22
45.66
45.19
40.35
35.05
39.81
38

---

Published as a conference paper at ICLR 2022
Table 17: Detailed results of non-targeted attacks on Computers (I)
Cloan
91.04
50.88
91.40
01.23
93.21
93.32
92.16
91.95
93.20
93.17
00.84
50:87
01.41
81.30
80.19
87.93
79.68
79.05
+HAAD
87.53
87.50
80. 11
75.91
81.80
62.26
61.15
62.09
79.29
79.53
MetaGIA
90.91
90.87
91.11
91.21
81.38
80.18
88.25 23
57.91
79.68
79.06
90.25
81.72
AGIA
90.98
90.90
91.
91:22
78.09
76.89
88.25
87.86
76.62
75.56
+HAD
86.02
85.77
70.97
71:49
77.55
78.17
63.99
62.74
70.23
76.14
90.97
+HAD
90.42
90.34
90.35
80.00
77.12
76.61
74.58
74.22
75.71
74.77
ATDIGA
90.97
90:90
91.41
91.24
82.42
81.77
89.24
88.94
81.29
80.76
84.00
74.38
AVG
89.54
89.38
87.24
80.50
81.37
80.88
80.00
79.92
79.71
79.21
Table 18: Detailed results of non-targeted attacks Computers (2)
Gaard
NebastiNN
GATILNHHLLA
GIATALNALLN
B2.46
92.40
92.24
92.45
92.05
PGD
82:31
85.82
84.91
73.27
77.91
67.14
63.83
67.61
54.96
52.20
+ELNO
02.83
55.62
52.31
72.73
65.08
68.50
62.55
54.95
63.25
69.19
82.31
84.91
73.28
77.91
67.14
07.82
52.21
+ILNO
77. 70
69.70
07. 90
70.42
69.52
64.76
02:45
58.24
59.31
63.69
85.21
64.25
+1LNO
63.02
56.48
55.35
72.18
61.22
68.84
60.68
59.95
62.78
67.54
TDGIA
80.42
88.64
88.32
72.23
76.27
00.45
03.67
63.58
64.06
58.98
ATDIGIA
82.42
87.11
86.03
76.96
79.13
71.92
68-42
71.15
68.01
53.34
+[LNO
60.74
61.48
58.81
78.79
64.38
74.28
68:33
$7.90
72.34
73.82
AVG
77.22
70.20
75.10
74.88
73.52
70.88
66.37
65.47
61.61
63.50
Table 19: Detailed results of non-targeted attacks on Arxiv (1)
REATWLAGHH
CuzcHEX
RebaiGC
DEMANNSLAGGLN
GuesH
71.15
70.95
70.54
60.50
60:46
C0 75
67.85
67.50
71.40
70.00
66.61
00.25
03.24
60.60
53.00
68.68
66.68
66.60
61.05
61.02
38.92 92.92
62.99
62.89
60/02
47.84
MctaCIA
69.97
66.81
66.52
66.14
66.15
65.7 70
63.20
63.30
61.15
58.58
57.26
64.60
63.57
07.02
56.60
58.2 27
58.20
57.77 73
60.77
60.72
61.50
58.8
TDIGA
67.64
67.28
04.37
68.33
72
61.01
63.63
64.31
61.61
60.99
59.73
59.74
08.33
63.08
63.30
02.81
53.04
ATDGIA
71.01
68.10
68.45
68.18
68.14
49
64.95
64.88
63.95
66.39
68.58
65.34
66.35
65.56
65.62
65.83
55.42
AYG
60.34
66.13
65.87
63.85
65.82
65.54
63.28
63.26
62.50
61.93
39

---

Published as a conference paper at ICLR 2022
Table 20: Detailed results of non-targeted attacks on Arxiv (2)
CON-MNN
REXT
FGRasde-NHHTAA GAT-IEAGH4 GENSUEAGAAN
GUN-IN
20.63
71.38
70.77
70,00
70.25
69.37
70.42
09.31
71.51
71,00
PGD
66.19
51.46
66.20
51.21
57.41
68.04
51.97
68.03
45.00
57.85
57.18
38.40
53.38
55.51
20.16
37.00
12.45
36.80
02.75
53.97
MetaCIA
58.21
63.36
57.05
09:65
51.65
30:32
07.30
50.23
57.72
04.63
AGIA
63.75
57.12
64.19
09.55
45.96
59.35
08.54
59. 25
54.55
49.14
40.36
40
58
TDIGA
66.74
38,91
66.96
55.47
56.30
62.15
52.39
62. 10
15.80
52.58
45.58
44.91
54.68
ATDGIA
67.97
62,21
68.07
58.61
63.36
62.73
55.26
62:67
51.19
58.50
60.82
64.82
50.32
62.00
37.51
46.94
59.50
46.83
57.90
56.58
60.99
58.33
36.61
06.25
56.24
56.
55.80
Table 21: Detailed results of targeted attacks Computers (1)
GaudsLX
GaudaENi
ROCC-TLA
BOATHILAGAN
Cleun
90.96
50,70
91.56
01.11
91.12
91.29
91.85
92.83
92.78
90.75
PGD
50.96
50.70
91.50
89.38
80.54
72.36
72:17
74.25
58.36
+HAD
64.15
74.40
36.50
80.10
+EAO
72.61
62
65.5
73.
72.
72.00
36
AGIA
91.00
00.82
91.58
01.00
80.11
80:33
72.06
68.85
60.64
88.00
HHAD
85.72
80.71
73.50
74..28
66.71
63.50
73.12
72.61
72.22
36.18
TDGIA
90.96
50.78
91.58
91.11
89.15
80.36
72.06
72.42
72.58
87.75
90.96
91.50
80.22
75.68
85.43
+1LNO
77.07
62.87
59.05
63.75
63.15
74.08
75.78
74.14
56.51
AYG
87.15
86.83
89.15
80,89
78.09
75.64
74.96
74.70
74.66
74.64
Table 22: Detailed results of targeted attacks on Computers (2)
Clean
90.50
92.07
92.66
92,77
91.07
91.90
91.92
92.25
91.36
92.35
88.13
+HAO
54.96
70.77 76
71.78
71.40
71.03
86.00 01
62.46
66.01
70.49
69.17
MctaGlA
57.40
+HAO
55:00
71.61
70.21
70.35
03.56
64.82
62.58
64.81
67.37
63.04
AGIA
87.37
61.08
56.62
+HA0
54.80
71.58
60.96
(3.59
08.44
64.81
61.00
64.08
69.30
02.28
TDGIA
87.21
71.54
71.
74.24
72.86
02.74
57.54
+HAO
61.62
71.62
71.39
71.92
54.19
80.51
66.60
66.79
66.74
63.57
ATDIGA
87.85
73.33
74.39
72.19
73.36
75.24
74.06
63.14
56.22
62.67
-HAO
51.93
58
72.00
71.19
62.03
63.19
62.14
68.50
73.15
AVG
73.67
73.31
73.15
73.09
71.78
70.79
69.40
67.06
65.92
65.06
40

---

Published as a conference paper at ICLR 2022
Table 23: Detailed results of targeted attacks on Arxiv (1)
Gearted N
DGGindee Nief AfGeNN
Gundel.N)
DCaundell AG+lN
FiGannted NatteAG
Geantel
IGGaodeff
Grant
RGAT
69.50
71.31
71.16
71.16
09.17
70.07
30.00
20.13
00:23
01.00
33.75
47.41
20.12
28
14.21
12.04
36.12
25.05
MariIIAA
71.00
11.23
70.35
50
10.50
001
75
00.51
10.25
12.50
11
19.50
30131
41
AGIA
00.00
TEIGA
03.75
65.00
58.72
91.19
35.28
23.41
30.04
20.15
17.05
10.00
58.99
58.25
ATTGII
7100
00.05
70.36
69.19
3910
00150
06009
88.10
06:00
6375
18.97
01.05
37.68
41.00
33.00
$4.25
10.15
17:23
30.03
88.84
00:97
01.18
51.81
33.10
13.05
50.90
64.00
13.85
12
01.43
Table 24: Detailed results of targeted attacks on Arxiv (2)
RobuuGGN
BGAT+LN
RGAAT4FLAGG4N
GUNN -F-LL
RGGTTHT
GUN-IN--LN
CCN-UN
GENSNN-FLAGGH
GAT+LN
GATHILAFHHN
72.08
71:41
T1:31
T1.59
71.75
03:91
60.04
PCD
28.60
(0.33
35.00 05
30.
37
25.105
20:07
25.75
35.34
35.54
07.32
30.33 75
30.47
03.22
5109
32.55 50
30.03
21.8
27.30
27.07
27.47
19.41
21.50
AGLA
41.06
42.12
42.00
32.53
30.05
33.00
$2.56
31.84
23.54
21.12
TDIGA
35.12
36.36
40.51
3733
31.50
301
26.31
38.00
38.67
37.51
97.56
79.00
ATDIGA
43.12
$4.47
55 04
33.28
31.06
27.97
58.94
AVG
41.31
41.05
40.00
57.13
$6.96
$5.00
36.07
33.82
23.79
20.50
Table 25: Detailed results of targeted attacks on Aminer (1)
Guads
EQuard GuasL-LNiLLN
Ouard
SQATXPLAG
Ouard-LN
BOuziVFLAG-LX
BOAT
59:03
58.06
80.72
60:95
57.06
57.25
61.75
58.50
58.81
62.78
PGD
56.22
18.17
56.31
19. 40
53.03
53.16
11.84
49.72
18.31
40.72
39.17
31.62
MctaGIA
52 09
50.66
52.35
19.81
19.03
18.0 97
16.19
48.31
47.59
45.81
AGIA
54.06
48.00
54.82
48.17
51.28
51.34
48.72
48.78
47.59
48.25
TDIGA
52.75
46.72
53.68
46.92
50.75
50.87
42.50
47.66
46.28
40.81
24.31
28.91
16.12
15.06
19.60
22.5
ATDGIA
53.44
51.00
53.69
40.332
00.34
50.50
45.44
49.97
40.59
45.25
42.66
33.72
AVG
15.16
11.16
11.23
13.86
11.21
11.05
10.79
40.39
40.11
40.06
Table 26: Detailed results of targeted attacks on Aminer (2)
BOATHEN
GUNAUN-LN
SigeLNNiC
CATAENIAN
DATAUN-FELMDEN
SigHi.M--11.0
02.06
64.11
13.77
65.56
63.91
68.88
65.44
06.97
63.78
61.34
PGD
$1.97
28.05 05
20.23 20-75
26,
26.51
22.65
25. 75
17.00
16.00
22.03
17.08
MesaGIA
55.
57.38
34.82
37.47
31.31
29.96
29.50
28.19
29.03
27.06
27.10
28.00
27.14
26.31
22.00
21.00
25.25
TDIGA
30.47
28.44
25.
21.41
26.97
20.85
22.19
15.30
15.16
20.56
27.12
27.53
34.97
24.56
24.84
22.19
22.22
15:75
14.03
20.10
AIDGIA
39.28
30.02
38.00
33.08
12.09
312.4
92.47
$4.88
35.12
27.62
32.06
87.72
31.
31.87
31.78
322.00
30172
33.97
33.06
29.
AVG
36.43
36.17
35.15
53.32
33.27
32.24
31.90
29.95
29.24
29.00
41

---

Published as a conference paper at ICLR 2022
Table 27: Detailed results of targeted attacks Reddit (1)
Gast-LNNALN
Guad-INi
Gazz-LN
Gazt
94.47
95.08
85.30
94:42
94.61
94.61
94.00
07.10
96.05
94.08
92:91
80.03
86.12
84.94
75.53
68.53
69 01.31
69.34
75.25
56.44
68 03
MetGIA
03.53
88 25
57.22
95.25
03.38
93
59
80.72
92.40
88
AGIA
93.62
86.00
87. 84
92.84
03.16
92 78
92 60
81.59
92.18
91.31
88.66
85,06
87.84
85.394
53.00
77.06
77.51
72.19
78.16
67.06
86.03
89.06
88.91
80.38
T8. 03.00
81.56
81.25
79.78
64.09
66.60 62
ATDGIA
83.31
87.31
84.91
92.98
122
93.00
93.81
76.53
91.02
93.00
90.78
89.38
AVG
89.44
88.20
88.14
87.00
85.71
85.09
85.02
80.24
80.01
78 10
Table 28: Detailed results of targeted attacks on Reddit (2)
PGD
92.09
74.91
75.91
67.47
63.75
70.38
73.53
78.12
57.16
71.28
58.12
73.91
79.59
67.72
61.72
72.91
78.16
70.47
58.62
70.91
MesaGAA
82.84
78.63
88.16
80,03
82.53
67.28
59.91
02.94
05.09
13
AGIA
91.31
09.50
59.53
62.66
$7.19
51.75
43.22
50.28
07.58
59.25
66.07
58-47
74.19
51.16
49.19
51.12
72.01
46.19
56.75
52.53
TDIGA
66.41
77.22
73.91
75.72
71.75
69.72
64.75
67.07
65.44
ATDGIA
83.03
73.31
64.25
68:44
63.55
64.63
53.86
57.01
65.12
62.34
63.34
73.78
72.53
69.62
65.00
65.22
62.97
65.50
63.66
$7.97
AYG
42


Reviews:
[{"review_id": "n-r3mZnPNyn", "reviewer": "Reviewer_iqJd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. The paper is well written and easy to follow\n2. The paper provides theoretical analysis to understand GIA and improve GIA, which is very solid\n3. The proposed method makes sense and experimental results show the effectiveness of the proposed method\n\nWeakness:\n1. The authors didn’t well motivate why evasion and inductive setting is a practical setting in real-world. It is unclear what is the real-world application scenario for such setting. The authors need to provide some motivation examples.\n\n2. The authors claim that ``nodes and edges involving test nodes are invisible to model f_\\theta during training.’’ It is unclear how the authors make the test nodes not involved in the training. During training, the authors adopt 3-layer GNN, which means that the 3-hop subgraphs centered at each training nodes involved in the training of the model. The 3-hop subgraphs will contain many unlabeled nodes, which might also contain test nodes. From the description of the experiments, I didn’t find how the authors make sure that these test nodes are not involved in the subgraphs. \n\n3. The paper assumes that the graph follows homophily assumption. What if the graph is a disassortative graph, does the proposed method still work? It would be interesting if the authors can discuss this.\n", "summary_of_the_paper": "This paper first theoretically shows that graph injection attack (GIA) is more powerful than graph modification (GMA), and GIA will lead to great damage to homophily distribution, which makes GIA easily defended by homophily-based defense. To mitigate the issue, the authors further propose to add the homophily unnoticeability constraint to preserve homophily. The authors also theoretically show that with the GIA with homophily unnoticeability constraint is more powerful than GIA without the constraint.", "summary_of_the_review": "In summary, this paper studies an important problem, provides theoretically analysis to understand GIA and further propose a new regualrizer to improve GIA. Extensive experimental results also show the effectiveness of the proposed method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cH14aMIrca4", "reviewer": "Reviewer_1USU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper is very well written and the experiments are also comprehensive. However, I have the following major concerns:\n1. The proof of the equivalence between node modification attack and node injection attacks assumes the search space of the features of the injected node is sufficiently large such that the equality in Eq. (17) and Eq. (21) hold. However, in practice, this may not always be true as it depends on the size of the search space of injected nodes and the degree of node $v$. Even with large valid search space, the equality may still not hold because of some strange degree values of node $v$. In addition, in the paper, the valid search space (of injected nodes) is set as the minimum and maximum of all the node features in the graph. I am not sure if such an assumption is realistic in practice, as maybe some features might be harder for the attacker to manipulate. The authors should provide more evidence on why the current search space for injected nodes is realistic. \n2. When showing that node injection strategies are stronger compared to node modification attacks under no defense, the paper assumes the node modification attack only performs indirect attack by changing some adjacent nodes to the test victim, but not the victim itself. However, previous work (Zugner et al., 2018) showed that direct attack (directly changing the test victim features and edges) is more powerful than the indirect attack. Therefore, the results in the paper become less interesting as there is still no clear relationship between direct node modification attacks and node injection attacks. When comparing the relationship between indirect node modification and node injection attacks, the problem also becomes somewhat trivial: when the search space of the injected node is sufficiently large, node injection will be better as the node modification attack are constrained to be within the (small) bounded $L_p$-norm ball around the original (semantically meaningful) node features. \n3. I also did not follow the proof of Theorem 1. In the proof sketch, the authors say that once (a) and (b) are proved, $\\mathcal{L}_{atk}(f_{\\theta}(\\mathcal{G}'_{GIA}))$ approaches $\\mathcal{L}_{atk}^{k}(f_{\\theta}(\\mathcal{G}'_{GMA}))$ from below when $\\Delta_{GIA}$ approaches $\\Delta_{GMA}$. How come the optimal loss function value of GIA is lower than that of GMA when $\\Delta_{GIA}$ approaches $\\Delta_{GMA}$ from below? Having smaller perturbation budget can only increase the value of the optimal loss function value. This part needs clear explanation and I am not sure if this will lead to any changes in the statement of $\\Delta_{GIA}\\leq \\Delta_{GMA}$ in Theorem 1. (For some reason, the math is not rendered correctly here, but the authors can past the original text into other typesetting tools to see the formula).      \n4. I am not sure how significant the proposed harmonious adversarial objective is. The whole optimization problem encourages each node to be as similar to the neighbors as possible while performing the attack. So, the contribution of the paper somewhat becomes spotting common weakness of node injection (and some node modification) attacks: injecting significantly different nodes to the graph and such a \"unconstrained\" behavior makes them vulnerable to simple homophily based detector. And then the paper enhances the original node injection attacks by adding homophily preservation as a regularizer. So the paper is more about designing adaptive attacks to a simple homophily defense and I am concerned that the contribution may not be significant.   ", "summary_of_the_paper": "This paper studies the advantages and drawbacks of node injection attacks to graph neural networks. The authors demonstrate that, in general, node injection attacks are more powerful than the node modification attacks when there is no defense. But when the model trainer adopts some homophily based defense, the node injection attacks suddenly become ineffective and even underperforms the node modification attacks. Based on the observation, the authors propose to add add homophily preservation as an additional regularizer for the attack to remain stealthy against defenses. Extensive experiments demonstrate that the proposed homophily indeed improve attack effectiveness against defenses. ", "summary_of_the_review": "I am leaning towards weakly rejecting the paper because 1) node injection attacks are only shown to be stronger than indirect node modification attacks, which becomes less interesting. In addition, the equivalence proof between the node injection and modification attacks cannot always hold in practice, 2) the proposed harmonious adversarial objective is of some limited novelty.\n ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Fye2v_2Z6Fg", "reviewer": "Reviewer_nMcc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is an interesting research topic to enhance the unnoticeability of graph adversarial attack and bypass various defenders. The proposed attack is straightforward and empirically effective against different defense strategies. The performance proposed method is also impressive under the combination of different defense methods.  However, there exist several concerns:\n\n1. For the analysis on  the comparison between GMA and GIA (Theorem 1), the budgets of these two attacks are totally different and not directly comparable. The budget of GMA is measured by the changes in entries of adjacency matrix and feature matrix while that of GIA is measured by the number of nodes.  If we only consider the number of perturbed nodes, the budget of GMA would be much smaller and Theorem 1 may not hold.  Since GIA can inject nodes with arbitrary features, it is intuitively more flexible and harmful than GMA.\n2. The novelty of this paper is somewhat weak. It is widely received that attackers tends to connect dissimilar features and many defenders are designed to mitigate such influence. Thus, it is quite natural to circumvent those defenders by penalizing the homophily change brought by the perturbations. I think the main contribution of this paper is from the empirical side.\n", "summary_of_the_paper": "This paper studies the problem of adversarial attack in graph neural networks. It aims to improve the unnoticeability of graph injection attack which injects carefully-crafted nodes into the graph data. In detail, it proposes the concept of homophily unnoticeability and studies the power of graph injection attack (GIA). Further, it observes that GIA can be easily defended by homophily defenders and proposes a harmonious adversarial objective to preserve homophily. Extensive experiments have demonstrated the effectiveness of the proposed method under various defenders.", "summary_of_the_review": "This paper advances the field of graph adversarial attack by promoting homophily unnoticeability. The experimental results are impressive while there are still some concerns regarding some analysis.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "1EXjeR12D8d", "reviewer": "Reviewer_tbGc", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I liked the approach and thoroughness of this paper. The claims and proofs are solid. The problem addressed is very interesting in terms of pointing out a major deficiency in robustness of neural graph embedding models against GIA attacks. I believe the contribution of this work is significant in that further work can be built on their results to address the discovered vulnerability in deep graph models. \n\nSome questions/suggestions for the authors:\n-\tIf the classifier does not rely on the node attributes and solely uses the graph structure (e.g., k-hop message passing), it seems that GIA and HAO both lose their advantage because homophily, as defined in eq. (6), will be meaningless. In this case, GIA will be at best as powerful as GMA. How can HAO be modified to still offer a better performance than GIA/GMA in this scenario?\n-\tApart from the point mentioned above, what are other limitations of your model? I feel the paper lacks this discussion.\n-\tTheoretically, how small can the attack budget of GIA/HAO get while still maintaining their utility?\n-\tIntuitively, why does HAO work? (or why do we expect it to work?) The answer to this question is important for guiding the future work in building more robust deep graph models and I believe it will be valuable to have a section discussing such intuition and possible future directions.\n-\tDo GIAs maintain the same advantage over GMA for different downstream tasks other than node classification (e.g., link prediction, graph clustering, etc.)?\n\n\nMinor modifications:\n-\tFirst line of section 2.2 should be changed to: “… fool a GNN model, f, trained on a ...”\n-\tThe definition of D_x in Section 2.2 is not clear. How are the min() and max() operators on the matrix X defined? What is the intuition behind D_x?\n-\tLast line of the paragraph after Definition 4.1 should be changed to: “…will trivially clip…”\n\n", "summary_of_the_paper": "The paper focuses on graph injection attacks (GIA) in which an adversary introduces new nodes and links such that the predicted label by a trained classifier for a victim node is changed. They compare GIA versus graph modification attacks (GMA), in which the existing links are manipulated, and theoretically prove the superiority of GIA in causing damage. They further address the vulnerability of GIA against homophily-based defense and propose a GIA attack that preserves the homophily and is robust against such defense mechanism.", "summary_of_the_review": "The claims and proofs are solid. The problem addressed is very interesting in terms of pointing out a major deficiency in robustness of neural graph embedding models against GIA attacks. I believe the contribution of this work is significant in that further work can be built on their results to address the discovered vulnerability in deep graph models. There is possibility of improvement (such as adding discussion on intuition behind the method, limitations of it, and in-depth discussion of implications and future directions). But, overall,  I evaluate this paper as “accept”.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that this paper studies an important problem, provides theoretically analysis to understand graph injection attack.
The authors propose a new regularizer to improve the attack success. Extensive experimental results also show the effectiveness of the proposed method.
Decision: Accept (Poster)