Year: 2022

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.

heading: 1 INTRODUCTION
text: 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 et al., 2017a; Battaglia et al., 2018; Zhou et al., 2020; Wu et al., 2021; Kipf & Welling, 2017; Hamilton et al., 2017b; Veličković et al., 2018; Xu et al., 2018; 2019b). Nevertheless, GNNs are shown to be inherently 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; Zügner et al., 2018; Zügner & Günnemann, 2019; Xu et al., 2019a; Chang et al., 2020). Since in many real-world scenarios, it is prohibitively expensive to modify the original graph, recently there is increasing attention paid to 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. 1a). 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 et al., 2019; Battaglia
et al., 2018; Hou et al., 2020; Zhu et al., 2020; Yang et al., 2021b). The severe damage to homophily will disable the effectiveness of 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, it is straightforward to devise a defense mechanism aiming to recover the homophily, which we term homophily defenders. Homophily defenders 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-ofthe-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.
To enable the effectiveness of GIA in evaluating various robust GNNs, it is necessary to 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. 1c). 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. 1b). Extensive experiments with 38 defense models on 6 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 attack1. Our contributions are summarized as follows:
• We provide a formal comparison between GIA and GMA in a 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 a novel objective HAO to conduct homophily unnoticeable attacks (Theorem 3).

heading: 2 PRELIMINARIES

heading: 2.1 GRAPH NEURAL NETWORKS
text: Consider a graph G = (A,X) with node set V = {v1, v2, ..., vn} and edge set E = {e1, e2, ..., em}, where A ∈ {0, 1}n×n is the adjacency matrix and X ∈ Rn×d is the node feature matrix. We are
1Code is available in https://github.com/LFhase/GIA-HAO.
interested in the semi-supervised node classification task (Jin et al., 2021). That is, given the set of labels Y ∈ {0, 1, .., C − 1}n from C classes, we can train a graph neural network fθ parameterized by θ on the training (sub)graph Gtrain by minimizing a classification loss Ltrain (e.g., cross-entropy). Then the trained fθ can predict the labels of nodes in test graph Gtest. A GNN typically follows a neighbor aggregation scheme to recursively update the node representations as:
H(k)u = σ(Wk · ρ({H(k−1)v }|v ∈ N (u) ∪ {u})), (1)
where N (u) is the set of neighbors of node u, H(0)u = Xu,∀u ∈ V , H(k)u is the hidden representation of node u after the k-th aggregation, σ(·) is an activation function, e.g., ReLU, and ρ(·) is an aggregation function over neighbors, e.g., MEAN or SUM.

heading: 2.2 GRAPH ADVERSARIAL ATTACK2
text: The goal of graph adversarial attack is to fool a GNN model, fθ∗ , trained on a graph G = (A,X) by constructing a graph G′ = (A′, X ′) with limited budgets ‖G′ − G‖ ≤ 4. Given a set of victim nodes Vc ⊆ V , the graph adversarial attack can be generically formulated as:
min Latk(fθ∗(G′)), s.t. ‖G′ − G‖ ≤ 4, (2) where θ∗ = arg minθ Ltrain(fθ(Gtrain)) and Latk is usually taken as −Ltrain. Following previous works (Zü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 A 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 by4A and4X , respectively, as:
4A +4X ≤ 4 ∈ Z, ‖A′ −A‖0 ≤ 4A ∈ Z, ‖X ′ −X‖∞ ≤ ∈ R, (3)
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 a set of malicious nodes Vatk as X ′ = [ X Xatk ] , A′ = [ A Aatk ATatk Oatk ] , where Xatk is the features of the injected nodes, Oatk is the adjacency matrix among injected nodes, and Aatk is the adjacency matrix between the injected nodes and the original nodes. Let du denote the degree of node u, the constraints in GIA are:
|Vatk| ≤ 4 ∈ Z, 1 ≤ du ≤ b ∈ Z, Xu ∈ DX ⊆ Rd,∀u ∈ Vatk, (4) where the number and degrees of the injected nodes are limited,DX = {C ∈ Rd,min(X)·1 ≤ C ≤ max(X)·1}where min(X) and max(X) are the minimum and maximum entries inX respectively. Threat Model. We adopt a unified setting, i.e., evasion, inductive and black-box, which is also used by Graph Robustness Benchmark (Zheng et al., 2021). Evasion: The attack only happens at test time, i.e., Gtest, rather than attacking Gtrain. Inductive: Test nodes are invisible during training. Black-box: The adversary can not access the architecture or the parameters of the target model.

heading: 3 POWER AND PITFALLS OF GRAPH INJECTION ATTACK
text: 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 1), we also find pitfalls in GIA that can make it easily defendable (Theorem 2).

heading: 3.1 POWER OF GRAPH INJECTION ATTACK
text: Following previous works (Zügner et al., 2018), we use a linearized GNN, i.e., H(k) = ÂkXΘ, to 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 budget4, the threat of A to a GNN fθ is defined as min‖G′−G‖≤4 Latk(fθ(G′)), i.e., the optimal objective value of Eq. 2.
2We leave more details and reasons about the setting used in this work in Appendix B.
With Definition 3.1, we can quantitatively compare the threats of different adversaries. Theorem 1. Given moderate perturbation budgets 4GIA for GIA and 4GMA for GMA, that is, let 4GIA ≤ 4GMA |V | ≤ |E|, for a fixed linearized GNN fθ trained on G, assume that G has no isolated nodes, and both GIA and GMA follow the optimal strategy, then, ∀4GMA ≥ 0,∃4GIA ≤ 4GMA, Latk(fθ(G′GIA))− Latk(fθ(G′GMA)) ≤ 0, where G′GIA and G′GMA are the perturbed graphs generated by GIA and GMA, respectively.
We prove Theorem 1 in Appendix E.1. Theorem 1 implies that GIA can cause more damage than GMA with equal or fewer budgets, which is also verified empirically as shown in Fig. 1a.
Intuitively, the power of GIA mainly comes from its relatively high flexibility in perturbation generation. Such flexibility enables us to find a mapping that can map any GMA perturbations to GIA perturbations, leading the same influences to the predictions of fθ. We will give an example below. Definition 3.2 (Plural MappingM2). M2 maps a perturbed graph G′GMA generated by GMA with only edge addition perturbations,3 to a GIA perturbed graph G′GIA =M2(G′GMA), such that:
fθ(G′GIA)u = fθ(G′GMA)u,∀u ∈ V.
As illustrated in Fig. 2a, the procedure ofM2 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 Xw to make the same effects to the prediction on u. Then GIA can be further optimized to bring more damage to node u. We also empirically verify the above procedure in Fig. 2b. Details about the comparison are in Appendix C.

heading: 3.2 PITFALLS IN GRAPH INJECTION ATTACK
text: ThroughM2, we show that the flexibility in GIA can make it more harmful than GMA when there is no defense, however, we also find a side-effect raised in the optimization trajectory of Xw from the above example. Assume GIA uses PGD (Madry et al., 2018) to optimizeXw iteratively, we find:
sim(Xu, Xw)(t+1) ≤ sim(Xu, Xw)(t), (5) where t is the number of optimization steps and sim(Xu, Xv) = Xu·Xv‖Xu‖2‖Xv‖2 . We prove the statement in Appendix E.4. It implies that, under the mappingM2, 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.
Before that, we will elaborate the definition of homophily in graph adversarial setting. Different from typical definitions that rely on 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 be defined with the similarity between the features of node u and the aggregated features of its neighbors:
hu = sim(ru, Xu), ru = ∑
j∈N (u)
1√ dj √ du Xj , (6)
where du is the degree of node u and sim(·) is a similarity metric, e.g., cosine similarity. 3We focus on edge addition in later discussions since Wu et al. (2019) observed that it produces the most harm in GMA. Discussions about the other GMA operations can be found in Appendix E.2.
We also define edge-centric homophily while we will focus primarily on node-centric homophily. Details and reasons are in Appendix D.1. With Definition 3.3, combining Eq. 5, we have:
hGIAu ≤ hGMAu ,
where hGIAu and h GMA u denote the homophily of node u after GIA and GMA attack, respectively. It 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 is an outstanding out-ofdistribution (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 pruning4, adapted from Eq. 1:
H(k)u = σ(Wk · ρ({1con(u, v) ·H(k−1)v }| v ∈ N (u) ∪ {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 1, consider a GIA attack, which (i) is mapped by M2 (Def. 3.2) from a GMA attack that only performs edge addition perturbations, and (ii) uses a linearized 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 G has no isolated node, and has node features asXu = CC−1eYu− 1 C−11 ∈ R
d, where Yu is the label of node u and eYu ∈ Rd is a one-hot vector with the Yu-th entry being 1 and others being 0. Let the minimum similarity for any pair of nodes connected in G be sG = min(u,v)∈E sim(Xu, Xv) with sim(Xu, Xv) = Xu·Xv‖Xu‖2‖Xv‖2 . For a homophily defender gθ that prunes edges (u, v) if sim(Xu, Xv) ≤ sG , we have:
Latk(gθ(M2(G′GMA)))− Latk(gθ(G′GMA)) ≥ 0.
We prove Theorem 2 in Appendix E.3. It implies that, by specifying a mild pruning condition, the homophily defender can effectively reduce the harm caused by GIA to be lower than that of GMA.
Considering a more concrete example withM2, Xw is generated to make Latk(fθ(M2(G′GMA))) = Latk(fθ(G′GMA)) on node u at first. Then, due to the flexibility in GIA, Xw can be optimized to some X ′w that greatly destroys the homophily of node u, i.e., having a negative cosine similarity score with u. Thus, for a graph with relatively high homophily, i.e., sG ≥ 0, a mild pruning condition such as 1sim(u,v)≤0(u, v) = 0 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.
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. 1b 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 a concrete GIA case in Appendix E.6.

heading: 4 HOMOPHILY UNNOTICEABLE GRAPH INJECTION ATTACK

heading: 4.1 HARMONIOUS ADVERSARIAL OBJECTIVE
text: As shown in Sec. 3, the flexibility of GIA makes it powerful while dramatically hinders its performance 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.
4Actually, homophily defenders can have many implementations other than pruning edges as given in Appendix F, while we will focus on the design above in our discussion.
Definition 4.1 (Homophily Unnoticeability). Let the node-centric homophily distribution for a graph G be HG . Given the upper bound for the allowed homophily distribution shift 4H ≥ 0, an attack A is homophily unnoticeable if:
m(HG ,HG′) ≤ 4H,
where G′ is the perturbed graph generated by A, and m(·) is a distribution distance measure.
Intuitively, homophily unnoticeability can be a supplementary for the unnoticeability in graph adversarial attack that requires a GIA adversary to consider how likely the new connections between the malicious nodes and target nodes will appear naturally. Otherwise, i.e., unnoticeability is broken, the malicious nodes and edges can be easily detected and removed by database administrators or homophily defenders. However, homophily unnoticeability can not be trivially implemented as a rigid constraint and be inspected incrementally like that for degree distribution (Zügner et al., 2018). 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 of 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 it 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 to meet the homophily unnoticeability softly.
Definition 4.2 (Harmonious Adversarial Objective (HAO)). Observing the homophily definition in Eq. 6 is differentiable with respect to X , we can integrate it into the objective of Eq. 2 as:5
min ‖G′−G‖≤4
Lhatk(fθ∗(G′)) = Latk(fθ∗(G′))− λC(G,G′), (8)
where C(G,G′) is a regularization term based on homophily and λ ≥ 0 is the corresponding weight.
One possible implementation is to maximize the homophily for each injected node as:
C(G,G′) = 1 |Vatk| ∑ u∈Vatk hu. (9)
HAO seizes the possibility of retaining homophily unnoticeability, while still performing effective attacks. Hence, given the homophily distribution distance measure m(·) in Def. 4.1, we can infer: Theorem 3. Given conditions in Theorem 2, we have m(HG ,HG′HAO)≤m(HG ,HG′GIA), hence:
Latk(gθ(G′HAO))− Latk(gθ(G′GIA)) ≤ 0,
where G′HAO is generated by GIA with HAO, and G′GIA 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 3 for more complex cases in the experiments.

heading: 4.2 ADAPTIVE INJECTION STRATEGIES
text: GIA is generically composed of two procedures, i.e., node injection and feature update, to solve for G′ = (A′, X ′), where node injection leverages either the gradient information or heuristics to 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 a 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, a 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.
5Note that we only use HAO to solve for G′ while still using the original objective to evaluate the threats.
Gradient-Driven Injection. We propose a novel bi-level formulation of HAO to perform the alternative optimization using gradients, where we separate the optimization of G′ =(A′, X ′) as:
X ′∗ = arg min X′∈Φ(X′) Latk(fθ∗(A′∗, X ′))− λAC(G′,G),
s.t. A′∗ = arg min A′∈Φ(A′)
Latk(fθ∗(A′, X ′))− λXC(G′,G), (10)
where Φ(A′) and Φ(X ′) are the corresponding feasible regions forA′ andX ′ induced by the original constraints. Here we use different homophily constraint weights λA and λX for the optimizations of A′ and X ′, since A′ is discrete while X ′ is continuous. We can either adopt Meta-gradients like Metattack (Zügner & Günnemann, 2019) (MetaGIA) or directly optimize edge weights to solve for A′ (AGIA). The detailed induction of meta-gradients and algorithms are given in Appendix G.1.
Heuristic-Driven 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:
su = ((1− pu)1(arg max (p) = y′u))( 0.9√ bdu + 0.1 du ), (11)
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 a novel divide-and-conquer strategy (SeqGIA) to iteratively select some of the most vulnerable targets with Eq. 11 to attack. Detailed algorithm is given in Appendix G.3.

heading: 5 EXPERIMENTS

heading: 5.1 SETUP & BASELINES
text: Datasets. We comprehensively evaluate our methods with 38 defense models on 6 datasets. We select two classic citation networks Cora and Citeseer (Yang et al., 2016; Giles et al., 1998) refined by GRB (Zheng et al., 2021). We also use Aminer and Reddit (Tang et al., 2008; Hamilton et al., 2017b; Zeng et al., 2020) from GRB, Arxiv from OGB (Hu et al., 2020), and a co-purchasing network Computers (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 methods as well as our proposed injection strategies to verify its effectiveness and versatility. First of all, we select PGD (Madry et al., 2018) as it is one of the most widely used adversarial attacks. We also select TDGIA (Zou et al., 2021) which is the state-of-the-art GIA method. We adopt the implementations 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 (Zügner & Günnemann, 2019) as one of the bi-level implementations. We exclude Nettack (Zügner et al., 2018) as it is hard to perform incremental updates with GCN (the surrogate model used in our experiments) and leave reinforcement learning methods such as RL-S2V (Dai et al., 2018) and NIPA (Sun et 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 & Welling, 2017), GraphSage (Hamilton et al., 2017b), and GAT (Veličković 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(n2) 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 our setting.
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 efficient adversarial training (Goodfellow et al., 2015; Madry et al., 2018) method FLAG (Kong et 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.

heading: 5.2 EMPIRICAL PERFORMANCE
text: 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 combating 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 information. Meanwhile, adaptive injection strategies outperform previous methods PGD and TDGIA by a 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-the-art coupled with HAO.

heading: 5.3 ANALYSIS AND DISCUSSIONS
text: Effects of HAO. Though HAO can substantially improve GIA methods under defenses, we find it essentially trades with the performance under no 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 to 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.

heading: 6 CONCLUSIONS
text: In this paper, we explored the advantages and limitations of GIA by comparing it with GMA. Though we found that GIA can be provably more harmful than GMA, the severe damage to the homophily makes it easily defendable by homophily defenders. Hence we introduced homophily unnoticeability 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.

heading: ACKNOWLEDGEMENTS
text: We thank the area chair and reviewers for their valuable comments. This work was partially supported by GRF 14208318 and ECS 22200720 from the RGC of HKSAR, YSF 62006202 from NSFC, Australian Research Council Projects DE-190101473 and DP-220102121.

heading: ETHICS STATEMENT
text: Considering the wide applications and high vulnerability to adversarial attacks of GNNs, it is important 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 of adopting unreliable GNNs. Our work tackles an important issue in current GIA, hence enhancing the effectiveness of current evaluation on 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, discrimination/bias/fairness concerns, privacy and security issues, legal compliance, and research integrity issues.

heading: REPRODUCIBILITY STATEMENT
text: To ensure the reproducibility of our theoretical, we provide detailed proof for our theoretical discovery in Appendix E. Specifically, we provide detailed proof in Appendix E.1 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 Appendix B.2 and Appendix H, and open source our code.

heading: A ADDITIONAL DISCUSSIONS AND FUTURE DIRECTIONS

heading: A.1 DISCUSSIONS ON HAO AND ITS LIMITATIONS
text: Discussions on HAO and future implications. It is widely received that it is difficult to 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 (Zügner et al., 2018; Zügner & Gü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 relate 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 homophily unnoticeability. The main reason for this phenomenon is mainly because of the poorly defined unnoticeability in graph adversarial attack. Without a proper definition, the developed attacks tend to the shortcut to incur damage instead of capturing the true underlying vulnerability of GNNs. Consequently, using these attacks to evaluate robustness of GNNs will bring unreliable results thus hindering the development of trustworthy GNNs.
To be more specific, due to the poor unnoticeability constraint for graph adversarial learning, the developed 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 a simple design, which however brings us unreliable conclusions about the robustness of homophily defenders. Essentially, HAO penalizes GIA attacks that take the shortcuts, 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 another approach to instantiate the unnoticeability. Especially for the domains that we can hardly leverage inductive bias from human, we can still try to 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 examiners. 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 homophily 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, compared with GIA without HAO, GIA with HAO show fewer threats. In certain cases, the trade-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
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 phenomenon 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 to perform the task.
In addition, as homophilous graph is the most common class of graph benchmarks for node classification (Yang et al., 2016; Giles et al., 1998; Hu et 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 non-attributed graphs, a direct adaption of HAO may not work. Nevertheless, if 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, it is still promising to introduce the node features with node embeddings, derive a 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 we surprisingly find HAO still maintains the advance when incorporating various GIA attacks. The reason might be that GNNs and GIA with HAO can still implicitly learn the homophily such as similarity between class label 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 robustness 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 to 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.

heading: A.2 MORE FUTURE DIRECTIONS
text: 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 classification (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 to other types of data, such as natural languages and graphs, where human inductive bias can hardly be leveraged to elaborate a proper definition of unnoticeability. Moreover, for more complicated tasks involving implicit reasoning, even in 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 a 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 to promote the robustness of the networks. For example, according the Proposition. E.1,
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 fit 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 to 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 it is very interesting to 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.
Reinforcement Learning based GIA. Reinforcement learning based approaches are shown to exhibit promising performances in previous mixed settings (Dai et al., 2018; Sun et 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. 4 to reduce the computation overhead of reinforcement learning approaches and enhance their scalability.

heading: B MORE DETAILS AND REASONS ABOUT THE GRAPH ADVERSARIAL ATTACK SETTING
text: We provide more details about the perturbation constraints and the threat model used in Sec. 2.2.

heading: B.1 PERTURBATION CONSTRAINTS
text: Following previous works (Zü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. 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 featuresX of the original graph G. The most widely adopted constraints in GMA is to limit the number of perturbations on A and X , denoted by4A and4X , respectively, as:
4A +4X ≤ 4 ∈ Z, ‖A′ −A‖0 ≤ 4A ∈ Z, ‖X ′ −X‖∞ ≤ ∈ R, (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 a set of malicious nodes Vatk as:
X ′ = [ X Xatk ] , A′ = [ A Aatk ATatk Oatk ] , (13)
where Xatk is the features of the injected nodes, Oatk is the adjacency matrix among injected nodes, and Aatk is the adjacency matrix between the injected nodes and the original nodes. Let du denote the degree of node u, the constraints in GIA are:
|Vatk| ≤ 4 ∈ Z, 1 ≤ du ≤ b ∈ Z, Xu ∈ DX ⊆ Rd,∀u ∈ Vatk, (14)
where the number and degrees of the injected nodes are limited,DX = {C ∈ Rd,min(X)·1 ≤ C ≤ max(X)·1}where min(X) and max(X) are the minimum and maximum entries inX 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 (Zou et al., 2021).

heading: B.2 THREAT MODEL
text: We adopt a unified setting which is also used by Graph Robustness Benchmark (Zheng et al., 2021), that is evasion, inductive, and black-box. Next we will elaborate more details and reasons for adopting the setting.

heading: B.2.1 DETAILS OF THE THREAT MODEL
text: Evasion. The attack only happens at test time, which means that defenders are able to obtain the original clean graph Gtrain for training, while testing on a perturbed graph G′. The reasons for adopting 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, fθ is trained on the (sub) training graph Gtrain, 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 Gtest = G for inferring the labels of test nodes. In particular, G is consist of all of the nodes and the edges, including Gtrain, 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 a transductive manner, the model can access the whole graph during both training and testing, i.e., Gtrain = Gtest = G. Since we adopt the evasion setting where the adversary may modify the Gtest during testing, the GNN has to be learned in an inductive manner. More reasons are as 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 a surrogate model for generating perturbed graph G′. Combining all of the above, conducting effective attacks raises special challenges to adversaries, since defenders can adopt the information extracted from training graph Gtrain 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 et al., 2021) which is known as one of the strongest defense mechanisms in the domain of images (Goodfellow et al., 2015; Madry et al., 2018).

heading: B.2.2 DISCUSSIONS ABOUT THE THREAT MODEL
text: Different from images where we can adopt the inductive bias from human vision system to use numerical 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 (Zügner et al., 2018) tries to use node degree distribution changes as the unnoticeability constraints. 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 unnoticeability, i.e., homophily in our case, to perform the attacks, since the defenders are blind to these shortcuts. On the other hand, leveraging shortcuts may generate data which is unlikely to appear in real-world applications. For example, in a citation network, medical papers are unlikely to cite or be 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 is apparently impractical. Using these attacks to evaluate the robustness of GNNs may bring unreliable conclusions, i.e., homophily defenders in our case, which will greatly hinders the development of the trustworthy GNNs.
Moreover, under a poor unnoticeability definition, without the presence of the original data, defenders 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 a generalization from deep
learning models to 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 distinguish whether the training graph is perturbed hence unlikely to 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 to use such highly poisoned data to train GNNs.
While in an evasion setting, the defenders are able to use the training graph to tell whether the incoming data is 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 larger day by day as new papers are published and added to the original network. GNN models must be inductive to be applied to such evolving graphs.

heading: B.3 MEMORIZATION EFFECTS OF GRAPH NEURAL NETWORKS
text: We conduct experiments with GCN (Kipf & Welling, 2017) on Cora (Yang et al., 2016). The architecture we select is a 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 × 10−4 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 of 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 a 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 to explicitly find it or do anything about it. That is against to the original setting and purpose of adversarial attacks (Szegedy et al., 2014; Goodfellow et al., 2015; Madry et al., 2018). Thus, it urges the community for a proper solution to the ill-defined unnoticeability in 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.

heading: C MORE DETAILS ABOUT GIA AND GMA COMPARISON
text: C.1 IMPLEMENTATION OF GRAPH MODIFICATION ATTACK
Following Metattack (Zügner & Günnemann, 2019), we implement Graph Modification Attack by taking A as a hyper-parameter. Nevertheless, since we are conducting evasion attack, we do not
have meta-gradients but the gradient of A with respect to Latk, or ∇ALatk. Each step, we take the maximum entry in∇ALatk, denoted with max(∇ALatk), and change the corresponding edge, if it is not contained in the training graph. Then we perform the perturbation as follows:
(a) If max(∇ALatk) ≤ 0 and the corresponding entry in A is 0, i.e., the edge does not exist before, we will add the edge.
(b) If max(∇ALatk) ≥ 0 and the corresponding entry in A is 1, i.e., 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 maximum 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, as 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, we can exclude the perturbations on nodes without loss of generality. Note that given the definitions of direct attack and influencer attack in Nettack (Zü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 agnostic 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 GRAPH INJECTION ATTACK WITH PLURAL MAPPING
GIA with M2 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.

heading: D MORE HOMOPHILY DISTRIBUTIONS

heading: D.1 EDGE-CENTRIC HOMOPHILY
text: In addition to 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, v) can be defined as.
he = sim(Xu, Xv), (15) where sim(·) is also a distance metric, e.g., cosine similarity.
With the definition above, we can probe the natural edge-centric homophily distribution of realworld benchmarks, as shown in Fig. 6. It turns out that the edge-centric homophily distributes follows a Gaussian prior. However, it seems to be improper to 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 to 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.

heading: D.2 MORE HOMOPHILY DISTRIBUTIONS CHANGES
text: 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 be easily defended by homophily defenders. While incorporated with HAO, GIA would retain the original homophily during attack.

heading: E PROOFS AND DISCUSSIONS OF THEOREMS

heading: E.1 PROOF FOR THEOREM 1
text: Theorem 1. Given moderate perturbation budgets 4GIA for GIA and 4GMA for GMA, that is, let 4GIA ≤ 4GMA |V | ≤ |E|, for a fixed linearized GNN fθ trained on G, assume that G has no isolated nodes, and both GIA and GMA adversaries follow the optimal strategy, then, ∀4GMA > 0,∃4GIA ≤ 4GMA, such that:
Latk(fθ(G′GIA))− Latk(fθ(G′GMA)) ≤ 0,
where G′GIA and G′GMA 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 k layers, there exists a mapping, that when given the same budget, i.e., 4GIA = 4GMA |V | ≤ |E|, for each perturbation generated by GMA intended to attack node u by perturbing edge (u, v), or node attributes of node u or some node v that connects to u within k hops, we can always map it to a corresponding injection attack, that injects node xw to attack u, and lead to the same effects to the prediction.
(b) When the number of perturbation budget increases, the optimal objective values achieved of GIA is monotonically non-increasing with respect to4GIA, that is
Lk+1atk (fθ(G ′ GIA)) ≤ Lkatk(fθ(G′GIA)),
where Lkatk(fθ(G′GIA)) is the optimal value achieved under the perturbation budget of k, which is obvious.
Once we prove both (a) and (b), the Latk(fθ(G′GIA)) will approach to Lkatk(fθ(G′GMA)) from the above as 4GIA approaches to 4GMA, hence proving Theorem 1. Furthermore, for the flexibility of the constraints on Xw, we may adopt the gradient information of Xw with respect to Latk(fθ(G′GIA)) to further optimize Xw and make more damages. Hence, we have Latk(fθ(G′GIA)) ≤ Lkatk(fθ(G′GMA)). To prove (a), the key technique is to show that, under a predefined mapping, there exist a corresponding injection matrix Aatk along with the features of the injected nodes Xatk, such that the GIA
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 Xatk, note that all of the input features X is normalized to a specific range within [−fl, fr] where fl, fr ≥ 0, following previous works (Zheng et al., 2021). Thus, for any features Xv ∈ DX , αXv ∈ DX when 0 ≤ α ≤ 1. We will use the statement multiple times during the derivation of Xatk.
Next, we will start to prove (a). Following Wu et al. (2019), in 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 on the number of linearized layers. First of all, we will show prove (a) holds for 1-layer and 2-layer linearized GNN as a motivating example. The model is as fθ = Â2XΘ with H = ÂXΘ and Z = fθ.
Plural MappingM2. Here we define the mappingM2 for edge addition. For each edge perturbation pair (u, v) generated by GMA, we can insert a new node w to connect u and v. The influence of adversaries can be identified as follows, as Θ is fixed, we may exclude it for simplicity: In layer (1):
• Clean graph:
Hi = ∑
t∈N (i)∪{i}
1√ didt Xt (16)
• GMA:
H ′i =  ∑ t∈N (i)∪{i} 1√ dt(di + 1) Xt + 1√ dv(di + 1) Xv, i ∈ {u} ∑ t∈N (i)∪{i} 1√ dt(di + 1) Xt + 1√ du(di + 1) Xu, i ∈ {v}
Hi, i /∈ {u, v}
(17)
• GIA:
H ′′i =  ∑ t∈N (i)∪{i} 1√ dt(di + 1) Xt + 1√ 3(di + 1) Xw, i ∈ {u, v}
Hi, u /∈ {u, v, w} 1√ 3 ( 1√ du + 1 Xu + 1√ dv + 1 Xv + 1√ 3 Xw), i ∈ {w}
(18)
where di 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 to be satisfied:
1√ 3(du + 1) Xw = 1√ (dv + 1)(du + 1) Xv, (19)
which is trivially held by setting
Xw =
√ 3√
dv + 1 Xv. (20)
Normally, GMA does not consider isolated nodes (Zügner et al., 2018; Zügner & Günnemann, 2019) hence we have dv ≥ 2 and Xw ∈ DX . Note that we can even change Xw to make more affects to node u with gradient information, then we may generate a more powerful perturbation in this way. Then, we go deeper to layer 2. In layer (2):
• Clean graph:
Zi = ∑
t∈N (i)∪{i}
1√ didt Ht (21)
• GMA:
Z ′i =  ∑ t∈N (i) Ht√ dt(di + 1) + H ′i di + 1 + H ′v√ (dv + 1)(di + 1) , u ∈ {u} ∑ t∈N (i) Ht√ dt(di + 1) + H ′i di + 1 + H ′u√ (du + 1)(di + 1) , u ∈ {v} ∑ t∈N (i) H ′t√ dt(di + 1) , u ∈ N (u) ∪N (v)
Zu, otherwise (22)
• GIA:
Z ′′i =  ∑ t∈N (i) 1√ dt(di + 1) Ht + 1 di + 1 H ′′i + 1√ 3(di + 1) H ′′w, i ∈ {u, v}
Hu, i /∈ {u, v, w} 1√ 3 ( 1√ du + 1 H ′′u + 1√ dv + 1 H ′′v + 1√ 3 H ′′w), i ∈ {w}
(23)
Similarly, to make Z ′u = Z ′′ u , we have to satisfy the following constraint:
1
du + 1 H ′′u + 1√ 3(du + 1) H ′′w = 1 du + 1 H ′i + 1√ (dv + 1)(du + 1) H ′v,
√ 3
du + 1 ∑ t∈N (u)∪{u} 1√ dt Xt + 4 3 Xw + 1√ 3 ( 1√ du + 1 Xu + 1√ dv + 1 Xv)
= √
3
du + 1 ∑ t∈N (u)∪{u} Xt√ dt + √ 3Xv√ dv + 1 +
√ 3√
dv + 1 ( ∑ t∈N (v)∪{v} Xt√ dt(dv + 1) + Xu√ (du + 1)(dv + 1) ),
4 3 Xw + 1√ 3 ( 1√ du + 1 Xu + 1√ dv + 1 Xv)
= √
3Xv√ dv + 1 +
√ 3√
dv + 1 ( ∑ t∈N (v)∪{v} Xt√ dt(dv + 1) + Xu√ (du + 1)(dv + 1) ),
(24)
then we let Xw = 34 (RHS− 1√ 3 ( 1√ du+1 Xu + 1√ dv+1 Xv)) to get the solution of Xw that makes the same perturbation. Similarly, we can infer Xw ∈ DX . The following proof also applies to layer 2.
Next, we will prove that, for a linearized GNN with k layers (k ≥ 1), i.e., H(k) = ÂkXΘ, once ∃Xw, such that the predictions for node u is the same to that perturbed by GMA, i.e., H(k−1)u = E (k−1) u , then ∃X ′w, such thatH (k) u = E (k) u . Here we useH to denote the prediction of GNN attacked by GMA and E for that of GIA. Note that, once the theorem holds, as we have already proven the existence for such Xw, it naturally generalizes to an arbitrary number of layers.
To be more specific, when H(k−1)u = E (k−1) u , we need to show that, ∃Xw, s.t.,
H(k)u = ∑
j∈N (u)
1√ du + 1 √ dj H (k−1) j + 1 du + 1 H(k−1)u + 1√ du + 1 √ dv + 1 H(k−1)v ,
E(k)u = ∑
j∈N (u)
1√ du + 1 √ dj E (k−1) j + 1 du + 1 E(k−1)u + 1 √ du + 1 √ 3 E(k−1)w ,
H(k)u = E (k) u .
(25)
Here we make a simplification to re-write Eq. 25 by defining the influence score.
Definition E.1 (Influence Score). The influence score from node v to u after k neighbor aggregations with a fixed GNN following Eq. 1, is the weight for Xv contributing to H (k) u :
H(k)u = ∑
j∈N (u)∪{u}
Ikuj ·Xj , (26)
which can be calculated recursively through: Ikuw = ∑
j∈N (u)∪{u}
(Iuj · I(k−1)jw ) + I (k−1) uw . (27)
As Θ is fixed here, we can simply regard Ikuv = Â k uv . Compared to the predictions after k-th propagation onto the clean graph, in GMA,H(k)u is additionally influenced by node v, while in GIA, H (k) u is additionally influenced by node v and node w. Without loss of generality, we may absorb the influence from neighbors of node v into that of node v. Hence we can rewrite Eq. 25 as the following:
∆H(k)u = I k GMAuvXv,
∆E(k)u = I k GIAuvXv + I k GIAuwXw,
∆H(k)u = ∆E (k) u ,
(28)
where IkGIAuv = ∑ j∈N (u)∪{u} IGIAuj · I (k−1) GIAjv + IGIAuw · I (k−1) GIAwv .
Then we can further simplify it as,
(IkGMAuv − I k GIAuv )Xv = I k GIAuwXw. (29)
To show the existence of Xw that solves the above equation, it suffices to show IkGIAuw 6= 0 and Xw ∈ DX . Note that ∃Xw s.t.,
(I (k−1) GMAuv − I (k−1) GIAuv )Xv = I (k−1) GIAuwXw. (30)
Since Âk ≥ 0,∀k ≥ 0, so we have I(k−1)GIAuw > 0. Moreover,
Ikuw = ∑
j∈N (u)∪{u}
(Âuj · Â(k−1)jw ) + I (k−1) uw ,
then it is obvious that the Ikuw > 0. Moreover, with the definition of I k uv = Â k uv , it is obvious that I (k−1) GIAuw ≥ I (k−1) GMAuv for v with a degree not less than 1 (i.e., v is not an isolated node). Hence, we have (I (k−1) GMAuv − I (k−1) GIAuv )/I (k−1) GIAuw ≤ 1 and Xw ∈ DX .
Now we have proved (a) holds for edge addition. For the remaining actions of GMA, we can use a new mappingM1 that injects one node w to node u to prove (a). For an edge deletion of (u, v), givenM1, one may rewrite Eq. 25 for the left nodes other than v, as well as the equation involving Ikuw, and derive the same conclusions similarly. Intuitively, for edge deletion, considering the classification probability, removing an edge is equivalent to enlarge the predicted classification probability for other classes, hence it fictionalizes likewise the edge addition and we can use a similar proof for this action.
Besides,M1 can also apply to the perturbation of features to node u or the other neighbor nodes of u within k hops, where we inject one node w to make the same effect. In this case, we can rewrite Eq. 25 and simplify it as following:
∆H(k)u = I k GMAuv∆Xv,
∆E(k)u = I k GIAuwXw,
∆H(k)u = ∆E (k) u ,
(31)
where v ∈ {N k(u) ∪ u}, i.e., node u or its k-hop neighbor, and ∆Xv is the perturbation to the attributes of node v. Similarly, by the definition of Ikuv , for node v with a degree not less than 1 (i.e., v is not an isolated node), we have IkGIAuw ≥ I k GMAuv , hence we have I k GMAuv/I k GIAuw ≤ 1 and Xw ∈ DX . Thus, we complete the whole proof.
Theorem 1 for other GNNs. We can extend Theorem 1 to other GNNs such as GCN, GraphSage, etc. Recall the theorem 1 in Xu et 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 influence distribution Ix for any node x ∈ V is equivalent, in expectation, to the k-step random walk distribution on G̃ starting at node x.
To apply Lemma 1, we observe that the definition of Ikuw is analogous to random walk starting from node u. Thus, one may replace the definition of Ikuw 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 mappingM2, for each edge addition (u, v), ∃Xw, such that
E(Lkatk(fθ(G′GIA))) = E(Lkatk(fθ(G′GIA))). (32)
Though the original theorem only proves Lemma 1 for GCN and GraphSage, it is obvious one can easily extend the proof in Xu et al. (2018) for aggregation scheme as Eq. 1.
Cases for Less GIA Budget. We can reduce GIA budgets in two ways.
(a) For GMA that performs both node feature perturbation and edge addition, considering a edge perturbation (u, v),M2 essentially also applies for node feature perturbations on u or v without additional budgets.
(b) It is very likely that with the mapping above, GIA will produce many similar nodes. Hence, with one post-processing step to 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. 1b.

heading: E.2 GIA WITH PLURAL MAPPING FOR MORE GMA OPERATIONS
text: Here we explain how our theoretical results also apply to the remaining actions, i.e., edge deletion and node feature perturbation, of GMA withM2 (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 are set to have the same influence to the predictions on the targets, they can be further optimized for amplifying the damage, thus all of our theoretical results can be derived similarly like that for edge addition operation.

heading: E.3 PROOF FOR THEOREM 2
text: Theorem 2. Given conditions in Theorem 1, consider a GIA attack, which (i) is mapped by M2 (Def. 3.2) from a GMA attack that only performs edge addition perturbations, and (ii) uses a linearized 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 G has no isolated node, and has node features asXu = CC−1eYu− 1 C−11 ∈ R
d, where Yu is the label of node u and eYu ∈ Rd is a one-hot vector with the Yu-th entry being 1 and others being 0. Let the minimum similarity for any pair of nodes connected in G be sG = min(u,v)∈E sim(Xu, Xv) with sim(Xu, Xv) = Xu·Xv‖Xu‖2‖Xv‖2 . For a homophily defender gθ that prunes edges (u, v) if sim(Xu, Xv) ≤ sG , we have:
Latk(gθ(M2(G′GMA)))− Latk(gθ(G′GMA)) ≥ 0.
Proof. We prove Theorem 2 by firstly show the following lemma.
Lemma 2. Given conditions in Theorem 2, as the optimization on Xw with respect to Latk by PGD approaches, we have: sim(Xu, Xw)(t+1) ≤ sim(Xu, Xw)(t), where t 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 withM2, Xw 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) ≤ sim(Xu, Xv), (33) as the optimization on Xw approaches. Furthermore, it follows:
hGIAu ≤ hGMAu , (34)
where hGIAu and h GMA u denote the homophily of node u after GIA and GMA attack, respectively. Now if we go back to the homophily defender gθ, 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 gθ. Let τGIA and τGMA denote the corresponding similarity between (u,w) in GIA and (u, v) in GMA, we have several possibilities compared with sG = min(u,v)∈E sim(Xu, Xv):
(a) τGIA ≤ τGMA ≤ sG : all the malicious edges will be pruned, Theorem 2 holds;
(b) τGIA ≤ sG ≤ τGMA: all the GIA edges will be pruned, Theorem 2 holds;
(c) sG ≤ τGIA ≤ τGMA: this is unlikely to happen, otherwise τGIA can be optimized to even worse case, Theorem 2 holds;
Thus, we complete our proof.
Interestingly, we can also set a specific threshold τh for homophily defender s.t., τh − sG ≤ ≥ 0, 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 et al., 2020; Yang et al., 2021a; Zhao et al., 2021; Yang et al., 2021b). The similar discussion can also be applied to this case and obtain the same conclusions.

heading: E.4 PROOF FOR LEMMA 2
text: Proof. To begin with, without loss of generality, we may assume the number of classes is 2 and Yu = 0, 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 Yu, we have:
Xu = { [1,−1]T , Yu = 0, [−1, 1]T , Yu = 1.
(35)
After setting it to having the same influence as that in GMA following Eq. 29, we have:
Xw = (IkGMAuv − I k GIAuv )
IkGIAuw Xv. (36)
Then, let Lu denote the training loss Ltrain on node u, we can calculate the gradient of Xw:
∂Lu ∂Xu = ∂Lu ∂H (k) u · ∂H (k) u ∂Xw = ∂Lu ∂H (k) u · IkGIAuw ·Θ. (37)
With Cross-Entropy loss, we further have:
∂Lu ∂H (k) u = [−1, 1]T . (38)
Then, we can induce the update step of optimizing Xw with respect to Latk = −Ltrain by PGD:
X(t+1)w = X (t) w + sign(I k GIAuw · [−1, 1] T ·Θ), (39)
where t 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 Θ ≥ 0, the optimal Θ would converge to Θ ≥ 0. Thus,
sign(IkGIAuw · [−1, 1] T ·Θ) = sign(IkGIAuw · [−1, 1] T ).
Let us look into the change of cosine similarity between node u and node v as:
∆sim(Xu, Xw) = α(Xu ·X(t+1)w −Xu ·X(t)w ), (40)
where α ≥ 0 is the normalized factor. To determine the sign of ∆sim(Xu, Xw), we may compare Xu · X(t+1) with Xu · X(t)w . Here we expand Xu · X(t+1)w . Let Xu0, Xu1 to denote the first and second element in Xu respectively, we have:
Xu ·X(t+1)w = Xu ·Xw + sign(IkGIAuw · [−1, 1] T )Xu ‖Xu‖2 · ∥∥∥X(t+1)w ∥∥∥
2
,
= Xu ·Xw + (Xu1 −Xu0) ‖Xu‖2 √ X2w0 +X 2 w1 + 2 + 2 (Xw1 −Xw0) ,
(41)
where we omit the sign of IkGIAuw for I k GIAuw ≥ 0 according to the definition. Recall that we let Yu = 0, hence we have (Xu1 − Xu0) ≤ 0. Besides, following Eq. 29, we have sign(Xw1 − Xw0) = sign(Xv1 −Xv0). As GMA tend to connect nodes from different classes, we further have sign(Xw1 −Xw0) ≥ 0. Comparing to Xu ·X(t)w , we know in Eq. 41, the numerator decreases and the denominator increases, as ≥ 0, so the overall scale decreases. In other words, we have:
∆sim(Xu, Xw) = α(Xu ·X(t+1)w −Xu ·X(t)w ) ≤ 0, (42)
which means that the cosine similarity between node u and node v decreases as the optimization of Xw with respect to Latk processes. Thus, we complete our proof for Lemma 2.

heading: E.5 PROOF FOR THEOREM 3
text: Theorem 3. Given conditions as Theorem 2, when λ > 0, we havem(HG ,HG′HAO) ≤ m(HG ,HG′GIA), hence: Latk(gθ(G′HAO))− Latk(gθ(G′GIA)) ≤ 0, where G′HAO is generated by GIA with HAO, and G′GIA 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 Yu, we have:
Xu = { [1,−1]T , Yu = 0, [−1, 1]T , Yu = 1.
(43)
Let Lu denote the training loss Ltrain on node u, we look into the gradient of Xw with respect to Lu:
∂Lu ∂Xu = ∂Lu ∂H (k) u · ∂H (k) u ∂Xw = ∂Lu ∂H (k) u · IkGIAuw ·Θ. (44)
With Cross-Entropy loss, we further have:
∂Lu ∂H (k) u = [−1, 1]T . (45)
Together with HAO, we can infer the update step of optimizing Xw with respect to Latk = −Ltrain + λC(G,G′) by PGD:
X(t+1)w = X (t) w + sign((I k GIAuw · [−1, 1] T + λ[1,−1]T ) ·Θ), (46)
where t is the number of update steps. Similarly, without loss of generality, we may assume Θ ≥ 0. As the optimization approaches, given λ > 0, GIA with HAO will early stop to some stage that (IkGIAuw · [−1, 1] T + λ[1,−1]T ) = 0, hence similar to the proof of Theorem 2, it follows:
hGIAu ≤ hHAOu , (47)
where hGIAu and h HAO u denote the homophily of node u after GIA and GIA with HAO attack, respectively. Likewise, we can infer that:
Latk(gθ(G′HAO))− Latk(gθ(G′GIA)) ≤ 0.
Thus, we complete our proof.

heading: E.6 CERTIFIED ROBUSTNESS OF HOMOPHILY DEFENDER
text: 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(k)[u,c] denote the corresponding entry in H(k)u for the class c, the decision margin on node u with class label Yu can be denoted by:
mu = H (k) [u,yu] − max c∈{0,..,C−1} H (k) [u,c].
A Multi-Layer Perceptron (MLP) can be taken as a 0-layer GNN which the definition also applies. Then, we specify the certified robustness as follows:
Proposition E.1 (Certified Robustness of Homophily Defender). Consider a direct GIA attack uses a linearized GNN trained with at least one node from each class in G, that targets at node u by injecting a node w connecting to u, let node features xu = CC−1 onehot(Yu)− 1 C−11, the homophily of u be τ , the decision margin of a MLP on u be γ, the minimum similarity for any pair of nodes connected in the original graph be sG = min(u,v)∈E sim(Xu, Xv), homophily defender gθ can defend such attacks, if −α 1√
1+1/du (τ + βγ) ≤ sG , and gθ prunes edges (u, v) s.t.,
sim(Xu, Xw) ≤ −α
√ 1
1 + 1/du (τ + βγ),
where α, β ≥ 0 are corresponding normalization factors.
Intuitively, effective attacks on a node with higher degrees, homophily or decision margin require a lower similarity between node w and u hence more destruction to the homophily of node u. GIA without any constraints tends to optimize sim(Xu, Xw) to a even lower value. Thus, it becomes easier to find a suitable condition for gθ, with which it can painlessly prune all vicious edges while keeping all original edges.
Proof. Analogous to the proof for Lemma 2, without loss of generality, we begin with binary classification, normalized indicator features and Yu = 0 as follows:
Xu = { [1,−1]T , Yu = 0, [−1, 1]T , Yu = 1.
(48)
The decision margin based on k-th layer representation can be denoted by
m = H (k) [u,yu] − max c∈{0,..,C−1} H (k) [u,c], (49)
follows the Definition E.2. In our binary classification case, we have
γ = H (0) [u,0] −H (0) [u,1], (50)
where H(0) is the output of a 0-layer GNN, or MLP (Multi-Layer Perceptron). A k-layer GNN can be regarded as generating new hidden representation for node u by aggregating its neighbors, hence, we may induce the decision margin for a k-layer GNN at node u as
m = H (k) [u,0] −H (k) [u,1] = ([ ∑ j∈N (u) IujXj ][0] − [ ∑ j∈N (u) IujXj ][1]) + I (k) uu γ, (51)
where we can replace the influence from neighbors with homophily of node u. Observe that hu essentially indicates how much neighbors of node u contribute to H(k)[u,0], for example, in binary case, let ζ > 0 be the corresponding normalization factor,
hu = 1 ζ ([ ∑
j∈N (u)
IujXj ][0][Xu][0] + [ ∑
j∈N (u)
IujXj ][1][Xu][1]),
which means,
[ ∑
j∈N (u)
IujXj ][1] = 1
[Xu][1] (ζhu − [ ∑ j∈N (u) IujXj ][0][Xu][0]),
replaced with Xu = [1,−1]T ,
m = H (k) [u,0] −H (k) [u,1] = ([ ∑
j∈N (u)
IujXj ][0] − [ ∑
j∈N (u)
IujXj ][1])+
= ([ ∑
j∈N (u)
IujXj ][0] − 1
[Xu][1] (ζhu − [ ∑ j∈N (u) IujXj ][0][Xu][0])) + I (k) uu γ
= ζhu + I (k) uu γ.
(52)
Hence, we have: m = H
(k) [u,0] −H (k) [u,1] = ζhu + I (k) uu γ,
where ζ ≥ 0 is the factor of hu. With node w injected, the margin can be rewritten as:
m′ =
√ du
du + 1 m+ I(k)uw (X[w,0] −X[w,1]). (53)
To perturb the prediction of node u, we make m ≤ 0, hence, we have
m′ =
√ du
du + 1 m+ I(k)uw (X[w,0] −X[w,1]) ≤ 0, I(k)uw (X[w,1] −X[w,0]) ≥ √
du du + 1 m,
(X[w,1] −X[w,0]) ≥ 1
I (k) uw
√ du
du + 1 (ζhu + I
(k) uu γ).
(54)
Observe that sim(Xu, Xw) = (X[w,0] −X[w,1]) and hu = τ , hence, we can write Eq. 54 in a clean form as sim(Xu, Xw) ≤ −α √
du du + 1 (τ + βγ), (55)
where α, β are corresponding normalization factors whose signs are determined by signs of Ikuw and Ikuu respectively. In other words, GIA has to optimize Xw satisfying the above requirement to make the attack effective, however, given the premise that all sG = min(u,v)∈E sim(Xu, Xv) ≥ −α √
du du+1 (τ + βγ), a defense model gθ will directly prune all of the vicious edges satisfying the above requirement and make the attack ineffective, which is exactly what we want to prove.

heading: F MORE IMPLEMENTATIONS OF HOMOPHILY DEFENDER
text: There are many ways to design homophily defenders, inheriting the spirit of recovering the original homophily. In addition to edge pruning, one could leverage variational inference to 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). Besides, outlier detection can also be adopted to remove or reduce the aggregation weights of malicious edges or nodes. In the following two subsections, we will present two variants that perform better than GNNGuard (Zhang & Zitnik, 2020).

heading: F.1 DETAILS OF EFFICIENT GNNGUARD
text: The originally released GNNGuard requires O(n2) computation for node-node similarity, making it prohibitive to run on large graphs. To this end, we implement an efficient alternative of GNNGuard adopting a similar message passing scheme, let τ be the threshold to prune an edge:
H(k)u = σ(Wk · ∑
j∈N (u)∪{u}
αujH (k−1) j ), (56)
where αuj = softmax( zuj∑ v∈N (u)∪{u} zuv ),
and
zuj =  1{sim(H(k−1)j , H (k−1) u ) > τ} · sim(H(k−1)j ·H (k−1) u )∑ v∈N (u) 1{sim(H (k−1) v , H (k−1) u ) > τ} · sim(H(k−1)v , H(k−1)u ) , u 6= j,
1∑ v∈N (u) 1{sim(H (k−1) v ·H(k−1)u ) > τ}+ 1
u = j.
Essentially, it only requires O(E) complexity. We will present the performance of Efficient GNNGuard (EGNNGuard) in table 3.

heading: F.2 DETAILS OF ROBUST GRAPH ATTENTION NETWORK (RGAT)
text: 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 (Veličković et al., 2018) attention mechanism as
αi,j = 1{sim(xi, xj) ≥ τ}∑
k∈N (i)∪{i} 1{sim(xi, xk) ≥ τ} ,
Additionally, we also adopt the idea of RobustGCN (Zhu et al., 2019) that stabilize the hidden representations between layers, so we add Layer Normalization (Ba et 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.

heading: Model Natural Accuracy Test Robustness Running Time

heading: F.3 PERFORMANCE OF HOMOPHILY DEFENDERS
text: We test the performance of different homophily defenders on Cora. Natural Accuracy refers to the test accuracy on clean graph. Test Robustness refers to 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 20× faster. RGAT performs slightly better and 10× faster. Hence, for large graphs and adversarial training of GNNGuard, we will use EGNNGuard instead.

heading: G MORE DETAILS ABOUT ALGORITHMS USED
text: Here we provide detailed descriptions of algorithms mentioned in Section. 4.2.

heading: G.1 DETAILS OF METAGIA AND AGIA
text: 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 metagradients as follows:
∇metaAatk = ∇AatkLatk(fθ∗(Aatk, X ∗ atk)), X ∗ atk = optXatkLatk(fθ∗(Aatk, Xatk)). (57)
Consider the opt process, we have
X (t+1) atk = X (t) atk − α∇X(t)atk Latk(fθ∗(Aatk, X (t) atk )). (58)
With that, we can derive the meta-gradient for Aatk:
∇metaAatk = ∇AatkLatk(fθ∗(Aatk, X ∗ atk))
= ∇XatkLatk(fθ∗(Aatk, X (t) atk )) · [∇Aatkfθ∗(Aatk, X (t) atk ) +∇X(t)atk fθ∗(Aatk, X (t) atk ) · ∇AatkX (t) atk ],
(59) where
∇AatkX (t+1) atk = ∇AatkX (t) atk − α∇Aatk∇X(t)atk Latk(fθ∗(Aatk, X (t) atk )). (60)
Note that X(t)atk depends on Aatk according to Eq. 58, so the derivative w.r.t. Aatk need to be traced back. Finally, the update schema for Aatk is as follows:
A (t+1) atk = A (t) atk − β∇ meta A (t) atk . (61)
Directly computing the meta gradients is expensive, following Metattack, we adopt approximations like MAML (Finn et al., 2017) for efficiency consideration. We refer readers to the paper of Metattack for the detailed algorithms by replacing the corresponding variables with those above.

heading: G.2 DETAILS OF AGIA
text: For optimizing weights of edge entries in Aatk, we can use either Adam (Kingma & Ba, 2015), PGD (Madry et al., 2018) or other optimization methods leveraging gradients. For simplicity, we use PGD to illustrate the algorithm description of AGIA as follows:
Algorithm 1: AGIA: Adaptive Graph Injection Attack with Gradient Input: A graph G = (A,X), a trained GNN model fθ∗ , number of injected nodes c, degree
budget b, outer attack epochs eouter, inner attack epochs for node features and adjacency matrix eXinner, e A inner, learning rate η, weight for sparsity penalty β, weight for homophily
penalty λ ; Output: Perturbed graph G′ = (A′, X ′);
1 Random initialize injection parameters (Aatk, Xatk); 2 Yorig ← fθ∗(A,X) ; /* Obtain original predictions on clean graph */ 3 for epoch← 0 to eouter do 4 Random initialize Xatk; 5 for epoch← 0 to eXinner do 6 A′ ← A ‖Aatk, X ′ ← X ‖Xatk ; 7 Xatk ← Clip(xmin,xmax)(Xatk − η · ∇Xatk(L h atk)) ;
8 for epoch← 0 to eAinner do 9 A′ ← A ‖Aatk, X ′ ← X ‖Xatk ;
10 Aatk ← Clip(0,1)(Aatk − η · ∇Aatk(LAatk)) ; 11 Aatk ← fk i=1 arg maxtop b(Aatk[i,:]) ;
Here, Lhatk refers to the objective of GIA with HAO for the optimization ofXatk. For the optimization of Aatk, we empirically find the λA would degenerate the performance, which we hypothesize that is because of the noises as Aatk is a discrete variable. Hence, we set λA = 0 in our experiments. Additionally, we introduce a sparsity regularization term for the optimization of Aatk:
LAatk = Latk + β 1 |Vatk| ∑ u∈Vatk |b− ‖Aatku,:‖1|. (62)
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 additionally brings the benefits to utilize momentum and history information to accelerate the optimization escape from the local optimum, which PGD fails to achieve.

heading: G.3 DETAILS OF SEQGIA
text: Since gradient methods require huge computation overhead, we propose a novel divide-and-conquer strategy to iteratively select some of the most vulnerable targets with Eq. 11 to attack. Note that it is different from traditional sequential injection methods which still connect the targets in full batch. For simplicity, we also illustrate the algorithm with PGD, and one may switch to other optimizer such as Adam to optimize Aatk. The detailed algorithm is as follows:
Algorithm 2: SeqGIA: Sequential Adaptive Graph Injection Attack Input: A graph G = (A,X), a trained GNN model fθ∗ , number of injected nodes k, degree
budget b, outer attack epochs eouter, inner attack epochs for node features and adjacency matrix eXinner, e A inner, learning rate η, weight for sparsity penalty β, weight for homophily
penalty λ, sequential step for vicious nodes γatk, sequential step for target nodes γc ; Output: Perturbed graph G′ = (A′, X ′);
1 Initialize injection parameters (Aatk, Xatk); 2 Yorig ← fθ∗(A,X) ;
; /* Obtain original predictions on clean graph */ 3 while Not Injecting All Nodes do 4 natk ← γatk ∗ |Vatk|; nc ← γc ∗ |Vc| ; 5 Ranking and selecting nc targets with Eq. 11; 6 Random initialize A(cur)atk ∈ Rnc×natk , X (cur) atk ∈ Rnatk×d ; 7 for epoch← 0 to eouter do 8 for epoch← 0 to eXinner do 9 A′ ← A ‖Aatk ‖A(cur)atk , X ′ ← X ‖Xatk ‖X (cur) atk ; 10 X (cur) atk ← Clip(xmin,xmax)(X (cur) atk − η · ∇X(cur)atk (L h atk)) ; 11 for epoch← 0 to eAinner do 12 A′ ← A ‖Aatk ‖A(cur)atk , X ′ ← X ‖Xatk ‖X (cur) atk ; 13 A (cur) atk ← Clip(0,1)(A
(cur) atk − η · ∇A(cur)atk (L A atk)) ;
14 A (cur) atk ← fnatk i=1 arg maxtop b(A (cur) atk[i,:]) ;
15 Aatk=Aatk ‖ A(cur)atk ; Xatk=Xatk ‖ X (cur) atk ;
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, we may further optimize the complexity from
O( 1
γatk (|Vc| log |Vc|+ eouter(eAinner|Vc|γc|Vatk|+ eXinner|Vatk|d))NVc)
to
O(α 1
γatk (|Vc| log |Vc|+|Vatk|b+ eXinner|Vatk|d)NVc+
(1− α) 1 γatk (|Vc| log |Vc|+eouter(eAinner|Vc|γc|Vatk|+ eXinner|Vatk|d))NVc)
in Table 7.

heading: H MORE DETAILS ABOUT THE EXPERIMENTS

heading: H.1 STATISTICS AND BUDGETS OF DATASETS
text: 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), we 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 (Zügner et al., 2018) to select 800 nodes as 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.

heading: H.2 ADDITIONAL DISCUSSIONS ABOUT ATTACK BASELINES
text: 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 on 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 are 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 we would like to leave them for future work. More discussions on RL based future works are given in Appendix A.2.

heading: H.3 COMPLEXITY OF ALGORITHMS
text: 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, eXinner is the number of epochs optimized for node features, b is the number of maximum degree of vicious nodes, d is the number of feature dimension, NVc is the number of k-hop neighbors of the victim nodes for perform one forwarding of a k-layer GNN, eouter is the number of epochs for optimizing Aatk, γc is the ratio of target nodes to attack in one batch, γatk is the ratio of vicious nodes to inject in one batch.

heading: H.4 DETAILS OF DEFENSE BASELINES
text: Here we provide the categories of defense models used in the experiments as 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 to 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), we 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 to denote adding layer norm between convulotion layers.

heading: Model Category Model Category Model Category Model Category

heading: H.5 DETAILS OF EVALUATION AND MODEL SETTINGS

heading: H.5.1 MODEL SETTING
text: By default, all GNNs used in our experiments have 3 layers, a 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 we 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, we use PGD (Madry et al., 2018) to find the threshold which performs well on both the clean data and perturbed data. By default, we set the threshold as 0.1, while for Computers and Reddit, we use 0.15 for Guard and EGuard, and for Citeseer and Arxiv we use 0.2 for RGAT.
For adversarial training with FLAG (Kong et 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 to the results for more details in Sec. J.1 and Sec. J.2.

heading: H.5.2 EVALUATION SETTING
text: 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 as targets. While for targeted attacks, we follow previous works (Zügner et al., 2018) to select 200 nodes with highest classification margin and lowest classification margin of the surrogate model. Then we randomly select 400 nodes as targets. In other words, there are 800 target nodes in total for targeted attack. Note for targeted attack, the natural accuracy on the target nodes might be different from normal test accuracy.
We also follow previous works to specify the attack budgets as Table. 5 for non-targeted attack and Table. 6 for targeted attack.
During evaluation, we follow the black-box setting. Specifically, we 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 on the perturbed graph. We repeat the evaluation for 10 times on Cora, Citeseer, Computers, and Arxiv, and 5 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.

heading: H.5.3 ATTACKS SETTING
text: 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, we follow the setting of TDGIA to update the features. Empirically, we find the original TDGIA feature update suits better for heuristic approaches while they show no advance over PGD for other approaches. Besides, as Table 7 shows, MetaGIA requires huge amount of time originally. Thus, to scale up, we use a batch update which updates the injected edges by a step size of b, i.e., the maximum degree of injected nodes, and limit the overall update epochs by |Vatk|/6, where we empirically observe this setting performs best in Cora hence we stick it for the other datasets.
For the setting of λ for HAO, we search the parameters within 0.5 to 8 by a step size of 0.5 such that the setting of λ 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 Latk and C(G,G′), where the former can be too large that blurs the optimization direction of the latter. Take Cross Entropy with log softmax as an example, we adopt the following to constrict the magnitude of Latk:
Latk[u] = (−H (k) [u,Yu]
) · 1{ exp(H
(k) [u,Yu] )∑ i exp(H (k) [u,i]) ≥ τ}
+ log( ∑ i exp(H (k) [u,i] · 1{ exp(H (k) [u,i])∑ j exp(H (k) [u,j]) ≥ τ})),
(63)
where 1{ exp(H
(k) [u,Yu] )∑
i exp(H (k) [u,i] ) ≥ τ} can be taken as the predicted probability for Yu = u and τ is the
corresponding threshold for hinge loss that we set as 1× 10−8. For the hyper-parameter setting of our proposed strategies in Sec. 4.2, we find directly adopting λ in PGD for λX and setting λA = 0 performs empirically better. Hence we stick to the setting for λA and λX . For the weight of sparsity regularization term in AGIA, we directly adopt 1/b. For the hyper-parameters in heuristic methods, we directly follow TDGIA (Zou et al., 2021). For SeqGIA, we set γatk be min(0.2, b|Vc|/2bc) and γc = min(|Vc|, γatk|Vatk|b) by default.

heading: H.6 SOFTWARE AND HARDWARE
text: 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 4 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.

heading: I MORE EXPERIMENTAL RESULTS
text: In this section, we provide more results from experiments about HAO to further validate its effectiveness. Specifically, we provide full results of averaged attack performance across all defense models, as well as initial experiments of HAO on two disassortative graphs.

heading: I.1 FULL RESULTS OF AVERAGED ATTACK PERFORMANCE
text: In this section, we provide full results of averaged attack performance across all defense models, as a supplementary for Table 3b.

heading: I.2 MORE RESULTS ON DISASSORTATIVE GRAPHS
text: 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.

heading: Datasets Nodes Edges Classes Avg. Degree Label Homophily Avg. Homophily
text: We also heuristically specify the budgets for each dataset according the the number of target nodes and average degrees.
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, we also observe robust tricks can not always improve 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 stepsize of 5×10−4 as well as a small number of steps of 10. Moreover, using a LN before the first GNN layer may also hurt the performance. For fair comparison, we remove these results from defenses. Finally, in Table 12, we report both categorized defense results as Table 1 as well as the averaged attack performance as Table 3b.
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 on Squirrel, the improvements become relatively low while still non-trivial. For
example, HAO improves the attack performance up to 4% in terms of test robustness against homophily defenders. We hypothesize the reason why HAO also works on disassortative graphs is because GNN can still learn the homophily information implicitly, e.g., similarity between class label distributions (Ma et al., 2022), which we will leave the in-depth analyses to future work.

heading: J DETAILED RESULTS OF ATTACK PERFORMANCE

heading: J.1 DETAILED RESULTS OF NON-TARGETED ATTACKS
text: In this section, we present the detailed non-targeted attack results of the methods and datasets used in our experiments for Table 1. For simplicity, we only give the results of top 20 robust models according to the averaged test accuracy against all attacks.

heading: J.2 DETAILED RESULTS OF TARGETED ATTACKS
text: In this section, we present the detailed targeted attack results of the methods and datasets used in our experiments for Table 2. For simiplicity, we only give the results of top 20 robust models according to the averaged test accuracy against all attacks.

Review summaries:
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. 

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.

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.

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.