Revisiting Graph Adversarial Attack and Defense From a Data Distribution Perspective
Authors: Kuan Li
Yang Liu
Xiang Ao
Qing He
Venue: ICLR 2023 poster (2023)
Keywords: Graph Adversarial Attack
Robustness
Data Distribution

Abstract:  Recent studies have shown that structural perturbations are significantly effective in degrading the accuracy of Graph Neural Networks (GNNs) in the semi-supervised node classification (SSNC) task. However, why the gradient-based methods are so destructive is rarely explored. In this work, we discover an interesting phenomenon: the adversarial edges are not uniformly distributed on the graph. Nearly all perturbations are generated around the training nodes in poisoning attack. Combined with this phenomenon, we provide an explanation for the effectiveness of the gradient-based attack method from a data distribution perspective and revisit both poisoning attack and evasion attack in SSNC. From this new perspective, we empirically and theoretically discuss some other attack tendencies. Based on the analysis, we provide nine practical tips on both attack and defense and meanwhile leverage them to improve existing attack and defense methods. Moreover, we design a fast attack method and a self-training defense method, which outperform the state-of-the-art methods and can effectively scale to large graphs like ogbn-arxiv. We conduct extensive experiments on four benchmark datasets to verify our claims.

Published as a conference paper at ICLR 2023
REVISITING GRAPH ADVERSARIAL ATTACK AND DEFENSE FROM A DATA DISTRIBUTION PERSPECTIVE
Kuan Li, Yang Liu, Xiang Ao; Qing He Key Lab of Intelligent Information Processing of Chinese Academy of Sciences Institute of Computing Technology, Chinese Academy of Sciences
University of Chinese Academy of Sciences likuan buaa @ 163.com, liuyang520ict@@ emmilllll.mmmmmmmmmmmmmm (aoxiang, heqing) @ict.ac.cn
ABSTRACT
Recent studies have shown that structural perturbations are significantly effective degrading the accuracy of Graph Neural Networks (GNNs) in the semi-supervised node classification (SSNC) task. However, the reasons for the destructive nature of gradient-base based methods have not been explored in-depth. In this work, we discover an interesting phenomenon: the adversarial edges are not uniformly distributed on the graph, and a majority of perturbations are generated around the training nodes in poisoning attacks. Combined with this phenomenon, we provide an explanation for the effectiveness of the gradient- based attack method from a data distribution perspective and revisit both poisoning attack and evasion attack in SSNC. From this new perspective, we empirically and theoretically discuss some other attack tendencies. Based on the analysis, we provide nine practical tips on both attack and defense and meanwhile leverage them improve existing attack and defense methods. Moreover, we design a fast attack method and a self- eeff-training defense method, which outperform the state-of-the-art methods and can effectively scale large graphs like ogbn-arxiv. We validate our claims through extensive experiments on four benchmark datasets.
INTRODUCTION
Graph Neural Networks (GNNs) have been widely explored in recent years for numerous graph-based
tasks Li et al. (2015): Kipf & Welling 2017); Hamilton et al. (2017); Liu et I (2021b), primarily focused on the semi-supervised node classification (SSNC) task Xu et al. (2019b) Veličković et al.
(201);: Huang et al. (2022); Liu et al. (2022). The evidence that GNNs are vulnerable to adversarial structure perturbations convincing Dai al. (2018); Züggner et al. (2018); Zügner Günnemann (2019): Wu et al. (201); Geisler et al. (2021) Zhu et al. (2022b). Attackers can degrade classification accuracy largely by unnoticeably modifying graph structure. Most attack methods are gradient- based Chen et al. (2020); Wu et al. (2019); Zügner& & Günnemann (2019); Xu et al. (2019a); /eisler (et al. (202)), treating the adjacency matrix as a parameter and moditying it via the gradient of the attack loss. However, we still lack a general framework to explain their effectiveness.
We posit that the destructive power of gradient- methods stems from their ability to effectively increase the distribution shift between training nodes and testing nodes. To illustrate in more detail, we start with an interesting phenomenon: the malicious modifications generated by gradient-based methods not uniformly distributed the graph. As shown in Fig. most modifications are around the training nodes (ordered at the top of the adjacency matrix), while the largest part of the graph, Test- Test, is hardly affected. Specifically, we apply two representative attack method, Attak Züügner & Güünnemann] (2019) and PGD Xu et al. (2019a). The data split follows 10%/10% 10%//0%%%%%%%% (train/validationnees)) Furthermore,
find that only MetaAttack can adaptively adjust the attack tendency (attack training nodes or testing nodes) according to the size of the training set, and such adaptivity makes MetaAttack outperform other methods regardless of the data split. inspires us to study the effectiveness of attack methods from another perspective, Distribution Shift, which likewise considers the differences between the training set and the testing set. This begs the
Corresponning Xiang An

---

Published as a conference paper at ICLR 2023
Train
Atlack
Ptb rate
Train-Traie
Train- Test
Test-
Train
238
MelaAttack
10%
60
442
3
20%
79
919
15
5%
172
PGD
10%
15%
162
122
365
575
10
20%
241
755
12
The adjaceney matrix of Cora attacked by MetaAttack, in which the blue pots original edges, and the reds are adversarial edges. The green dotted line is the boundary of training nodes and testing nodes. Right: The location statistics of adversarial edges the Cora dataset under different perturbation rates. Train-Traae Train means the perturbed edge links two nodes from the training set. Train-Tes destt and Test-Tes follow the same rule.
Figure 1: Left:
following challenge:
How to formulate the distribution shift in graph adversarial attack scenario?
To answer the above question, in this paper, we first clarify the differences between attack in the mainstream domain, e.g., image classification, and in SSNC: (1) SSNC is a transductive task in which attackers have access both training nodes and testing nodes; (2) Nodes in the graphs have both features and structural information, while other data types may only contain features, e.g. images have pixels or text have words. Taking these two differences into account, we provide a formalization of the distribution shift in graph adversarial attack and theoretically prove that the perturbations around training nodes enlarge the distribution shift an effective way. we explore factors that influence the location of adversarial edges, such as surrogate loss and gradient acquisition.
Using the formulation of the distribution shift, some unexplained phenomena in previous works become clear. For example, why do gradient- based attack methods significantly outperform the heuristic homophily-basee method, DICE? Why do most modifications are insertions instead of deletions? We will analyze them from both theoretical and empirical sides.
With the advantage of the above analysis, several practical tips are proposed to improve and instruct attack and defense on graphs. To validate these tips, conduct extensive corresponding experiments. Additionally, we design a fast and straightforward heuristic attack method underpinned by increasing the distribution shift, and it achieves comparable performance to gradient-base methods and can effectively scale to large graphs like ogbn-arxiv. We also provide a self- toaff-trrniinnnbassee method to improve the robustness GNN: The codes are available at https://github.com/ http://wwwoooiiuuunnos/sseee.e.e
Our main contributions are summarized below:
We find an interesting phenomenon that perturbations are unevenly distributed on the graph. and it inspires us to revisit graph adversarial attack from data distribution perspective and define the distribution shift in graph attack scenario.
We explore some unexplained phenomena and provide relevant theoretical proofs from the view of data distribution. We argue that the effectiveness of the graph attack essentially comes from increasing the distribution shift, as the fundamental nature of the adversarial attack.
We provide some practical tips to instruct both attack and defense on graphs. We conduct extensive experiments support our claims and verify the validity of these tricks. The implementation details and the statistics of the datasets are provided A.1
RELATED WORK
Many efforts have been made to study various properties of the gradient-based attack algorithms. GCN-SVD Entezari et al. 22020) discovers that attacks exhibit specific behavior in the spectrum
!Our focus is to revisit both attack and defense sides from new view. These two algorithms natural byproducts of this work, put them in the appendix.
2

---

Published as a conference paper at ICLR 2023
of the graph: only high-rank (low-valued) singular components of the graph affected. Likewise, Chang et al.] (021)) and [Chang et al. (2022) also study the robustmess of GNNs from the spectral perspective. Chang et al. (2021) indicates that not all low-frequency filters lick GCNs are robust to adversarial attacks and proposes GCN-LFR which enhance the robustness of various kinds of GCN-based models by general robust co-training paradigm. Meanwhile, many efforts have been devoted to revealing the various properties of gradient-based attacks. Züggner& & Günnemann (2019) demonstrates that the perturbations tend to increase the heterophily of the graph. Based on it, Zhang & Zitmik (2020) and Ww et al. (2019) invent GNNGuard and Jaccard, respectively, to prune the edges that link two dissimilar nodes. Geisler et al. (2020) and Chen et al. (202I) study the robustmess of GNNs from the breakdown point perspective and propose more robust aggregation approaches. Xu et al. (2022) introduce mutual information- based measure to quantify the robustness of graph encoders on the representation space. IZhan & Peil (022)) is another work that finds the uneven distribution of perturbations, mainly focusing on the attacking side and proposing a black-box attack method. Different from them, prefer to study the mechanism behind it, including the reasons for its generation and the impact on the effectiveness of the attack methods. We fomulate the distribution shift in graph adversarial attack and leverage it to analyze other tendencies of gradient- based attack methods, which can provide some theoretical guidance and help us understand the robustness and vulnerability of GNNs. Meanwhile, several tips are proposed, covering all the structure attack aspects, and most of them are not mentioned in Zhan & Pei (2022)
3 PRELIMINARIES
Notations. Let G = (V,E) denote an undirected, unweighted graph with N nodes, where V and E (without self-loops) are the sets of nodes and edges, respectively. The topology of the graph can also be represented as symmetric adjacency matrix A {0, [0,11NNX, in which Au = 1 denotes that node i/ connects node Vi otherwise Ar = 0. The original features of all nodes can be summarized as a matrix X E xd The first-order neighborhood of node v; is denoted as N₁. including node U; itself. Moreover, the labels of all nodes denoted y. Each node is associated with a label ys E C, where C = {ci, C2. Cx]. We use fo (A, X) to denote a GNN, and refers to the parameters.
SSNC. In this paper, we study the robustness of GNNs on the semi-supervised node classification (SSNC) task, which can be formulated as this: Given a graph G. the node features X, and subset of node labels yı. C y. the goal is to learn function: V + C which maps the nodes the label set so that we can predict labels of unlabeled nodes. The ground truth labels of unlabeled nodes are denoted as yo, and the corresponding node set is Vy.
Graph Adversarial Attacks In this paper, we explore the robustness of GNNs on SSNC in gray- box non-targeted attack on graph structure. Under this setting, the attacker possesses the same data information as the defender, but the defense model and its trained weights are unknown. The adversarial attack can be divided into two categories, namely poisoning (training time) attack and evasion (testing time) attack Zügner et al.) (2018). The attacker aims to find an optimal perturbated graph & that degrades the overall performance of the classifier much as possible, which can be formulated as Zügner & Günnemann (2019); Geisler et al. (202T):
argmin AEe(A)
Car (a,nfo--AA,,) (A,X), v),
where À is the adjacency matrix of the purturbed graph ف. and ((A) is of adjacency matrix that fits the unnoticeable constraint: | < A, in which A is the maximum perturbation rate. Lask ||l
is often -[ (Á, &v) -C(fe- (Å, (A, X) yL), where ÿv is the pseudo-label of unlabeled nodes predicted by the surrogate classifier. For notation simplicity, we call them Laets and Lerain. respectively. The 6* refers to the parameters of the surrogate GNN, which is different in evasion and poisoning attack. It is fixed and trained on the clean graph in evasion attack, but can be repeatedly retrained as the graph is gradually contaminated in poisoning attack.
The key to the gradient-based attack methods is to treat the adjacency matrix as a parameter and modify the graph structure via the gradient of the attack loss V A Catk-
3

---

Published as a conference paper at ICLR 2023
4 RETHINKING GRAPH ADVERSARIAL ATTACKS
4.1 THE LOCATION OF ADVERSARIAL EDGES
To better understand which part of the graph is perturbed, we propose an intention score (IS) to quantify how the adversarial edges are distributed on the graph. Since GNN models are permutation invariant Zou al. (2021), we can adjust the node index and then split the adjacency matrix into the
following form:
A
A A
A2 A3
A ALERNIN, A E RNNN, As E RNXN,
(2)
where A1 is an matrix the edges that connects two training nodes, A2 is a matrix that represents edges between training node and testing node, and Ag is matrix where the element denotes an edge between two testing nodes. N1 and N2 are the numbers of the nodes in the training set and testing set.
IS can describe which part the adjacency matrix (A,, A2, or Ag) the attack algorithm prefers generate adversarial edges. is be formulated
T2 A
J A:
IS
1,2,3
where & is the original edge set, & denotes the edges inserted or deleted by the attack model, and denotes the part of the adjacency matrix. IS can demonstrate the density of the perturbations located
the adjacency matrix (see Table [ Table 4 and Fig. 5
Table shows the results on dataset Cora attacked by two poisoning method, MetaAttack and PGD, under different data split. MetaAttack will adaptively adjust the attack tendency according to the size of the training ser. When the training size is small, the algorithm tends to modify the local structure around training nodes. The IS3 increases as the training set becomes larger, meaning that adversarial edges more likely to be generated around testing nodes. When the size of the training set is 50%, all the IS are close to 1, and meanwhile the adversarial edges are nearly uniformly distributed on the graph. More results of other attack methods and more datasets be in Table 4 in the appendix A.2
We find that only MetaAttack has such adaptivity, and it make MetaAttack extremely effective in poisoning attack. Other representative gradient-basee attack methods, like PGD and FGSM, will always focus on modifying the local structure of the training nodes and only attack the training nodes regardless of the size of the training set. This adaptivity essentially differentiates between training and testing nodes when generating attacks. It motivates us study this problem from another perspective that likewise considers the differences between the training and testing sets Distribution Shift.
Table 1: The IS on Cora dataset under 10% perturbation rate.
MetaAttack Train-Test
PGD Train- Test (IS₂)
Training set
Train-Train (IS;)
Test-Test (18g)
Ace
Train-Train (IS,)
Test-Test (ISs)
Acc
Clean
(IS₂)
10%
11.881
4.862
0.007
71.62
22.178
4.279
0.002
77.92
83.56
4.200
2.513
0.042
80.35
6.832
2.234
0.009
82.32
85.67
30%
2.042
1.605
0.290
81.27
4.444
1.414
0.008
84.56
86.99
40%
1.762
1.136
0,546
81.54
3.057
1.056
0.000
86.23
87.01
50%
0.798
1.150
0.901
83,05
2.107
0.931
0.008
86.91
87.22
60%
0.642
1,260
83.11
1.71
88.03
88.04
70%
0.625
1.299
1.625
81.92
1.519
0.585
0.000
89.55
89.98
80%
0.383
1.933
3.409
80.46
L.600
0.755
0.001
88.88
88.87
0.364
3,426
8,893
79.38
1.107
0.000
93.54
93.69
4.2 DISTRIBUTION SHIFT IN GRAPH ATTACKS
Machine learning models cannot perform well when the training distribution far from the testing distribution Wiles al. (202T). Intuitively, the smaller the training set, the easier the training
4

---

Published as a conference paper at ICLR 2023
predict
Poison
Training set
Model
Testing set
Testing set Testing set
Porturb
Model
Paruuh
predict
Perturb
predict
Evasion
Training set
Model
Testing set
8
6
Perturbed Data
Clean Data
(a) Image Classification
Node Classification
Figure 2: (a): The training set and the testing set are separated in inductive learning under full supervision. For poisoning attack, attackers perturb the training biased model cannot precisely predict the testing set. For evasion attack, the model trained on clean data will be tested on the perturbed data. (b) In SSNC. training nodes and testing nodes co-exist in the graph. Whether it is poisoning attack or evasion attack, the attackers have access to all nodes.
fool the classifier. Then the
distribution is to be perturbed. The destructive power of these gradient-bused methods may stem from the fact that they effectively increase the distribution shift. The first thing we need do is to formulate the distribution shift in graph adversarial attack.
Unlike attacks in other domain, like image classification, formulating the distribution shift in SSNC should consider the structural information. We assume all the node features are sampled from p(æly) amd define community feature to take structural information into account: e; V.. Σj 2j and assume the community feature of arbitrary node i follows distribution:
1 WI
Σ JEN,
~(
The first-order neighborhood plays the most important role in structure information, so we do not consider higher-order here. All the community features and corresponding labels can be viewed as being sampled from the joint distribution p( y) on clean graphs. In graph adversarial attack, there three key distributionns-prraimf. 3). Prest (z, y), and the classifier pe po(y ()) ). In the clean graphs, we assume that Ptrain (λ. y) and Ptest (z. y) are the same as the true distribution p(ū. y). In the
perturbed graphs, we consider attacking the structures as perturbing the corresponding distribution. Concretely, we treat the structural changes to the training and test nodes as if these nodes were sampled from biased Ptrain and Ptest-
In image classification, the attackers degrade the performance of the classifier by perturbing Ptrain or Preat- When implementing the poisoning attack, the Ptroin will be perturbed, and the classifier will fit biased distribution that it will fail to precisely predict the unbiased images sampled from Pleat- In evasion attack, the attackers have no access to the training set, so they perturb the testing images this can be viewed as predicting
biased distribution Ptest with an unbiased classifier.
However, SSNC is supervseeev...d Attackers can modify the entire graph structure, including the training and test nodes. The difference between SSNC and image classification is shown in Fig. 2 Unlike inductive learning under full supervision scenario, Ptrain and Ptest can be simultaneously perturbed.
Awareness of this difference critical. For example, in the image poisoning attack, attackers can only perturb the training data to bias the model. In contrast, in the graph poisoning attack, attackers can perturb the testing data to make an unbiased model test on the biased data.
After perturbing, Ptrains and Ptest might be different to the true distribution p( y) and this discrepancy may result in a distribution shift. By a simple factorization, we can write:
p( v) = p(y)p(ūly)
(5)
Labels are not flipped in the setting of structure attack, so we assume p(y) is shared across all distributions. The distribution shift arises when Ptrain (øly) and Ptest (āly) differ due to the structural perturbations, so we difine the distribution shift in graph adversarial attack as:
D (øly- cz), Ptest (mly c:))
(6)
5

---

Published as a conference paper at ICLR 2023
Essentially the attack is to increase the distribution shift, but specifically to perturb Perain (öly) or (ūly) in the poisoning attack and evasion attack is different.
For evasion attack, perturbing Ptroin is nearly invalid. The classifier is already trained, which can be viewed as an unbiased model. is unwise to waste limited modifications on the training nodes. For poisoning attack, the implications of attacking the training and testing sets are different from distribution perspective. Attacking the training set is to perturb the Ptrain (x) (y) in such a way that the classifier pa (y) (+) will fit a biased distribution. On the other hand, perturbing the testing set in poisoning attack is similar to the case in evasion attack. The model is well trained on clean data and tested on a biased distribution. Our empirical results demonstrate that gradient- based methods tend to perturb the local structure of training nodes if the size of the training set is small. We speculate that it because SSNC, the smaller the training set, the more effective it to attack the structure of the training nodes (Theorem 4.1 we give the proof in Appendix A.3)
Assumption 4.1. We consider graph G, where each node i has feature æ; E Rd and label ye E 10. We assume that (1) 9 is k-regular; (2) The feature of arbitrary node is sampled from the normal distribution ((py A) associated with its label and independent other nodes. A is diagonal matrix and same for class and 1; (3) The graph is a homophilous graph. The homophily ratio is h, which means each node connects kh nodes with the same label, and 0.5 h h
Theorem 4.1. Consider a graph G, which follows Assumptions 4.1 The perturbation rate A, and the training size is I. The smaller the size of the training set, the larger the distribution shift caused by uniformly inserting heterophily edges (edges link two nodes with different labels) into the training set.
MetaAttack's 's success in poisoning attack (as shown in Table 4 can be accounted for the same reason. It can adaptively adjust IS so that it attacks the training set when the training size is small but changes to attack the testing set as the size of the training set increases. Notably, the performance of Meta/ttack shows decreasing and then increasing trend as the training set increases, so such a strategy can effectively enlarge the distribution shift.
4.3 IMPACT OF SURROGATE LOSS AND GRADIENT COMPUTATION
When implementing the attack algorithms, two factors influence the distribution of adversarial edges: (1) surrogate loss and (2) how the gradient obtained. Ma et al.] (2020p; Geisler et al.
(2021) have studied the impact of various surrogate loss on the attack performance, such as Cross- Entropy (CE), Carlini- Wagnir (CW), Non-targeted CE, etc. Diffcrent from them, we are concerned with the question of which nodes are used to calculate the loss. Leets = L(fo- (Á, X)u, g0) and firain L(fo- (A,X) X) yL. are two widely used loss. We find that they lead to different attack tendencies. Attack methods with Ctroin and Lsely will focus on the training and testing nodes, respectively. In addition, MetaAttack is special case due to its ability to adjust the location of adversarial edges adaptively. We find that such adaptability comes from its way of calculating the gradient, i.e., meta gradient. For more details, see A.4
5 EXPLANATION OF PHENOMENA IN GRAPH ATTACKS
With the advantage of the new perspective and the formulation of distribution shift, we could introduce some other phenomena in graph attacks and explain them.
5.1 TEND TO INSERT BUT NOT DELETE
Previous work shows that gradient- based attack methods tend to insert but not delete edges Zügner & Günnemann (2019): Lin et al.) (2020); Xu et al. (2019a). For example, roughly 80% of perturbations in MetaAttack are insertions, and expected by the homophily assumption, edges inserted connect nodes from different classes in most cases. Why is insertion more destructive? We argue that insertion cause larger distribution shift and provide a theoretical justification (Theorem 5.1).
Theorem 5.1. Consider a graph G. which follows Assumptions 4.1 If uk+1] 1 In and (2h - 1)t > A, inserting heterophily edges in the training set will cause a larger distribution shift than deleting homophily edges.

---

Published as a conference paper at ICLR 2023
We provide the proof in Appendix A.5 Since adversarial attacks aim at performing unnoticeable perturbations, the perturbation rate Á is often very small, and in homophilous graphs, often much larger than 0.5 in homophilous graphs. Therefore, the assumption E(++1]
Ak S In 2 and
(2h - 1) > could be generally satisfied. To ensure this tendency is not caused by the sparsity of the graph, build dense synthetic graph and attack it by MetaAttack in Table I0 Appendix A.5
The results hold the same conclusion that attack methods tend to insert but not delete.
5.2 GRADIENT- BASED METHODS OUTPERFORM HOMOPHILY-BANN BASED METHODS
Under the homophily assumption McPherson et al. (0001). i.e., connected nodes are more likely to have similar features and labels; one mainstream opinion is that attack methods tend increase the heterophily of the graph Zügner & Günnemann 2019); Wu et al. (019); Zhu et al. (2021a). it cannot account for the superiority of the gradient-based approaches over DICE Waniek et al. (018). B), a heuristic method that directly increases the heterophily of the graph by randomly connecting nodes from different classes and disconnecting nodes from the same class. However, this is not surprising from distribution perspective.
The homophily assumption ignores the location of the perturbations,
On the one hand, DICE randomly attacks the entire graph, resulting in synchronous perturbation of Ptrain and Ptest while the gradient-based methods concentrate on attacking the training set. According to Theorem 4.1 attacking the smaller part is more effective to increase the distribution shift, so DICE performs worse. On the other hand, DICE algorithm perturbs both training and testing nodes using a similar rule, wherein heterophily is increased. Consequently, Ptroin and Prest may exhibit a biased shift in the same direction, leading to a reduction distribution shift rather than an increase. We speculate that attack methods might be more destructive if they mainly perturb one of Ptrain and Ptrain- To support this, We turn the Train- Test perturbations generated by MetaAttack into direct edges. Fig. shows the results and demonstrates two critical points. First, prrceted-Trrain outperforms the vanilla MetaAttack, indicating that simultaneously perturbing Ptrain and Ptest is worse than primarily perturb Ptrains indicating that perturbing Ptrain and Ptest might be biased in the same direction. Second, Direct-<Test is much weaker than Direct-Train That is to say, what makes MetaAttack so destructive is the perturbations the smaller part, training nodes.
Accuncy
0.75
Accumcy
0.70
MetnArtak
MetnABack
Directed-Triin Triin
Directod -rain Triin
0.55
Dissste--isst
Dineted--Test
0.50
Peturhation Rate
Penurhation Rate
(a) Cora
(b) Citeseer
Figure The performance of GCN attacked by MetaAttack and two variants. Directed->Train variant prevented testing nodes from aggregating information from training nodes through adversarial edges in Train-Test, while Directed-+ on the contrary. The data split follows 10% 10% (trin/ val/test).
5.3 HIGH-DEGREE NODES
High-degree nodes are special. First, attack algorithms often avoid modifying the local structure around high-degree nodes Zügner & Günnemann) (2019). The more neighbors node has, the more stable community feature is. Attacking them will make less change to the distribution. Additionally, high-degree nodes are naturally high-density data (see A.6). High-density data possess two important properties: (1) They are easier to be classified correctly. (2) They are reliable neighbors to other nodes because they located in high-density areas of the true distribution and are not attacked. We can leverage them to improve the robust GNNs (Table For example, trust them more (for more details, see A.6).
7

---

Published as a conference paper at ICLR 2023
PRACTICAL TIPS
With all the observation and analysis, we put forward several concrete tips to improve attack and defense methods.
6.1 POISONING ATTACK
Tip 1: It is better to focus on attacking the smaller part. For poisoning attack, the performance of GNNs can be degrade by perturbing Ptrain or Prest- According Theorem 4.1] [ the smaller the size of the data set is, the greater the distribution is changed by injecting fixed number of perturbations. MetaAttack a good example of this tip, in which the perturbations are generated according to the size of the training set. We improve DICE and random perturbations (Random) along these lines and compare them to the vanilla version Fig. For Cora, we focus the attack on the training nodes. As the public split on ogbn-arxiv is approximately 54%/17%/22% (train/val/test), modifications around the testing nodes. We significantly improve the performance of both DICE and Random. The improvement is more remarkable in ogbn-arxiv. We conclude that such strategy can be well-applied to large-scale graphs.
conduct the
Accuracy
0:70
0.65
DIEE
DICE
DICE
DICEmp
0.00
DICBimp
Ran
0.55
Ran
Ran
Pesturbation Rate (%)
(%6
Pertueaatinn Rate (56
(a) Cora
(b) Citeseer
(c) ogbn-arxiv
Figure 4: Attacking GCN Cora, Citeseer and ogbn-arxit arxiv where the DICEamp and Ranımp denote variants of DICE and Random that attack the smaller part of the graph.
Tip 2: Meta gradient is powerful. According to the comparison between MetaAttack and other variants, conclude that meta gradient convenient tool in poisoning attack. Regardless of how the data set is split, meta gradient can help the model adaptively adjust the distribution of perturbations enlarge the distribution shift effectively.
Tip 3: Directed attack can outperform undirected attack. The results of Fig, 3 indicate that an adversarial edge can affect the aggregation of two end nodes, but only one of them may contribute to the accuracy decrease. It also suggests that perturbing both Ptrain and Ptest may not be good idea as Ptrain and Ptest might skewed the same direction, failing to increase the distribution shift. and, consequently, failing the attack.
6.1.1 A HEURISTIC ATTACK ALGORITHM
Considering all the properties of the gradient-based attacks from the data distribution perspective, propose simple heuristic poisoning attack algorithm that achieve comparable performance and scale to large graphs. We provide the overall training algorithm, performance, and the runtime comparisons in A.7 Its core idea is to perturb the easily perturbed distribution in Ptrain and Ptest to enlarge the distribution shift.
6.2 EVASION ATTACK
Tip 4: Do not waste the limited bullets the training nodes. The classifier is already trained in evasion attack. In other words, po (y/ Φ) is fixed, while the only effect attacking the training set is to bias the model. Thus, attackers should avoid modifying the structures of training nodes, especially the edges in the Train- Train area. According to Table 5 and Table Laet should be eschewed when meta-gradients not used.
8

---

Published as a conference paper at ICLR 2023
Tip 5: The evasion attack is unlikely to cause higher performance degradation than the poisoning. Essentially, evasion attacks have smaller effective range than poisoning attacks. Attackers perform poisoning attack in evasion form. As mentioned before, only modifications around the testing nodes can degrade the performance, so one can make exactly the same perturbations the test. nodes when carrying out the poisoning attack. In this way, the model will be trained on nearly clean data and tested on contaminated data. In short, poisoning attack can at least completely replicate evasion attack.
6.3 DEFENSE
Tip 6: Defend the vulnerable part of the graph. To defend against graph adversarial attacks, many studies have been proposed around the central concept of Graph Structure Learning (GSL) et al. (2022); Wu et al. (2019); Zhang & Zitnik (2020); Jin et al. (2020); Zhu et al. (2021b), which aims to optimize the perturbed structure. An attacker can achieve good results by attacking distributions that can be easily perturbed. Likewise, the defender can mainly optimize the corresponding structures. Jaccard and GNNGuard Zhang & Zitmik (2020) two representative GSL methods that refine the graph structure via the similarity of the node features. In Table we present the experimental results for vanilla Jaccard and GNNGuard and the results if they only refine the structure of the training set. The improvement implies that the modifications made by vanilla Jaccard and GNNGuard on the testing structure are helpless.
Tip 7: The high-degree nodes can help lot. If the true distribution like the normal distribution with the highest probability density located around the mean, the mean aggregation can reduce the variance of the center nodes. That to say, high-degree nodes are high-density data and trustworthy. We provide an example of leveraging them to enhance the robustness of GNN in Table
Table 2: Adversarial accuracy (%) on Cora and Citeseer attacked by Meta/ttack (stronger is bold). The asterisk indicates that the GSL methods only optimize the local structure of the traning nodes.
Datasets
Ptb rate
GCN
Juccard( +)
GNNGuard(*)
(%%
83.56
81.79(33001)
78.52(82.59)
5%
76.36
80.23(82.03)
77.96(81.17)
Cora
10%
71.62
74.65(77.51)
74.86(78.53)
15%
66.37
74.29(76.51)
14.15(77.21)
Tip 8: We improve the robustness by decreasing the distribution shift. Once know that the effectiveness of the attack algorithm stems from increasing the distribution shift, we can enhance the robustness by directly eliminating the inconsistency between the training set and the testing set. Based on this, we design robust GNN STRG in Appendix A.8 which outperforms the SOTA methods. STRG leverages the local structures of testing nodes and pseudo-labels to train a GCN; in this case, Ptrain and Prest can be regarded almost the same.
20%
60.31
13.11(74.60)
72.03(75.88)
0%
74.63
73.64(74.58)
70.07(74.28)
5%
71.13
11.15(72.23)
(9)433(2.334
Citeseer
10%
67.49
69.85(70.65)
67.89(71.70)
15%
61.59
67. (7.50668.86) 86)
69. 69.14(70.59)
20%
$6.26
67.01(67.66)
69.20(70.36)
6.4 FOR DATASETS
Tip 9: Data split is the non-negligible part of graph adversarial attack. It is hard to maliciously manipulate the prediction made by GNNs without the data split. Mcanwhile, the data split significantly affects the evaluation of attack and defense methods' effectiveness. We provide the details in A.9
7 CONCLUSION
To better understand attacks graphs, we revisit graph adversarial attack from data distribution perspective and formulate the distribution shift in SSNC. Based on this, we argue that the tendencies of gradient-based based methods and their destructive power essentially comes from increasing the distribution shift. We put forward several practical tips underpinned by what we found and provide some uses of the tips. Additionally, we give some open research ideas and hope they spur research in this area.

---

Published as a conference paper at ICLR 2023
8 REPRODUCIBILITY STATEMENT
The two proposed algorithms are not our focus in this work, and the key to their success is the thinkings behind them but not technical novelty. They are both easy but effective. All the details are mentioned in the pseudo-code in Algorithm and Algorithm 2 and the codes are provided at For other baselines, we provide the implementation details in
Appendix A.1
ETHIC STATEMENT
The robustness of GNNs has become emerging research problem, especially for security-critical domains, e.g., credit scoring or fraud detection. For instance, in graph fraud transaction detection, fraudsters conceal themselves by deliberately dealing with common users, which may generate adversarial edges. In this work, we provide new perspective on studying the robustness of graph models. A better understanding of the attack methods and the structural vulnerabilityy of GNNs can help us improve the security level in these domains. Meanwhile, although we offer examples of how to leverage the tips, most of them can be further explored and used in more sophisticated ways. In conclusion, we think this work will not pose security risk and can positively affect research in this area.
10 ACKNOWLEDGEMENT
The research work supported by National Key R&D Plan No. 2022YFC3303302 the National Natural Science Foundation of China under Grant No. 61976204. Xiang Ao is also supported by the Project of Youth Innovation Promotion Association CAS and Beijing Nova Program Z201 100006820062.
REFERENCES
Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pp. 36-43, 2005.
Heng Chang, Yu Rong, Tingyang Xu, Yatao Bian, Shiji Zhou, Xin Wang, Junzhou Huang, and Wenwu Zhu. Not all low-pass filters are robust in graph convolutional networks. Advances in Neural Information Processing Systems, 34:25058-25077 2021.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang, Honglei Zhang, Peng Cui, Xin Wang, Wenwu Zhu, and Junzhou Huang. Adversarial attack framework on graph embedding models with limited knowledge. IEEE Transactions Knowledge and Data Engineering, 2022.
Jinyin Chen, Yixian Chen, Haibin Zheng, Shijing Shen, Shanqing Yu, Dan Zhang, and Qi Xuan. Mga: momentum gradient attack on network. IEEE Transactions on Computational Social Systems, (1):99-109, 2020.
Liang Chen, Jintang Li, Qibiao Peng. Yang Liu, Zibin Zheng, and Carl Yang. Understanding structural vulnerability in graph convolutional networks. arXiv preprint
2021.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack graph structured data. In International conference on machine learning, pp. 1115-1124. PMLR, 2018.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against ad attacks graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 169-177, 2020.
Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. In NeurIPS, 2020.
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar Bojchevski, and Stephan Günnnemann. Robustness of graph neural networks at scale. In NeurIPS, 2021.
10

---

Published as a conference paper at ICLR 2023
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0006 2020.
Mengda Huang, Yang Liu, Xiang Ao, Kuan Li, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Auc-oriented graph neural network for fraud detection. In Proceedings of the ACM Web Conference 2022, pp. 1311 1-121, 2022.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Dala Mining, pp. 66-74, 2020.
Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM International Conference Web Search and Data Mining, pp. 148-156, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks In ICLR, 2017.
Kuan Li, Yang Liu, Xiang Ao, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Reliable representations make a stronger defender: Unsupervised structure refinement for robust gnn. In Proceedings of the 28th ACM SICKDD Conference on Knowledge Discovery and Data Mining, pp. 925-935, 2022.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelligence, 2018.
Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint a005v:2005.06149, 2020.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint
2015. 2015.
Xixun Lin, Chuan Zhou, Hong Yang, Jia Wu, Haibo Wang, Yanan Cao, and Bin Wang. Exploratory adversarial attacks on graph neural networks. In ICDM, 2020.
Xiaorui Liu, Wei Jin, Yao Ma. Yaxin Li. Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In International Conference on Machine Learning, pp. 6837-6849. PMLR, 2021a.
Yang Liu, Xiang Ao, Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Pick and choose: A gnn-based imbalanced learning approach for fraud detection. In Proceedings of the Web Conference 2021, pp. 3168-3177, 2021b.
Yang Liu, Xiang Ao, Fuli Feng, and Qing He. Ud-gnn: Uncertainty-aware debiased training on semi-homophilous graphs. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1131-1140, 2022.
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks graph neural networks. In NewrIPS, 2020.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):4154444, 2001.
Prithviraj Sen, Galileo Namata. Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- RRd. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua arXiv: 17/0. 10903, 2017.
Bengio. Graph attention networks. arXiv preprint arXiv:
11

---

Published as a conference paper at ICLR 2023
Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in a social network. Nature Human Behaviour, 2(2): 147, 2018.
Olivia Wiles, Sven Gowal, Florian Stimberg, Sylvestre et al. A fine-grained analysis on distribution shift. arXiv preprint arXiv:21 1328, 2021.
Ira Ktena, Taylan Cemgil,
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples on graph data: Deep insights into attack and defense. arXiv preprint arXiv: 006600000000,.... 2019.
Jiarong Xu, Yang Yang, Junru Chen, Xin Jiang, Chumping Wang, Jiangang Lu, and Yizhou Sun. Unsupervised adversarially-robus representation learning on graphs. In AAAI, 2022.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. arXiv preprint arXiv:19066 190.:0440004444 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019b.
Haoxi Zhan and Xiaobing Pei. Dealing with the unevenness: deeper insights in graph- based attack and defense. Machine Learning, pp. 1-33, 2022.
Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. arXiv preprint 20Xxv:200060814999 2020.
Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. On the relationship between heterophily and robustness of graph neural networks. arXiv preprint arXiv:2106.0777 070.07767 2021a.
Yanqiao Zhu Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph structure learning for robust representations: A survey, arXiv preprint arXiv:2103.03033 202
Yao Zhu, Jiacheng Sun, and Zhenguo Li. Rethinking adversarial transferability from a data distribution perspective. ICLR, 2022a.
Yulin Zhu, Yuni Lai, Kaifa Zhao, Xiapu Luo, Mingquan Yuan, Jian Ren, and Kai Zhou. Binarizedattack: Structural poisoning attacks graph-based anomaly detection. In ICDE, 2022b.
Xu Zou, Qinkai Zheng, Yuxiao Dong, Xinyu Guan, Evgeny Kharlamov, Jialiang Lu, and Jie Tang. Tdgia: Effective injection attacks on graph neural networks. In KDD,, 2021.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference Learning Representations (ICIR), 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 2847-2856, 2018
A APPENDIX
A.1 IMPLEMENTATION DETAILS
We conduct our experiments on four benchmark datasets including Cora, Citeseer (Sen et al.
(208)).
Polblogs Adamic & Glance (2005), and one large-scale citation graph ogbn-arxiv Hu et al.
2020).
All the experiments For Cora, Citeseer, and Polblogs, the data split follows 10% 10%/10%/80 % if not
specified. For the ogbn-arxiv we use the public split. Following Zügner et al. (2018) : Jin et al. (0020),
for Cora, Polblogs, and Citeseer, we only consider the largest connected component (LCC). The statistics are listed in Table There are no features available in Polblogs. Following Jin et al. (000);
Liu et al. (2021a) set the feature matrix be identity matrix.
12

---

Published as a conference paper at ICLR 2023
Table Dataset statisties.
Datasets
NLec
ELcc
Classes
Features
Cora
2,485
5,069
1,433
Citeseer
2,110
3,668
3,703
Polblogs
1,222
16,714
ogbn-arxiv
169,343
1,166,243
40
128
We use DeepRobust, an adversarial attack repository Li et et. (2020), to implement Meta/ttack Zügner & Günnemann (2019), PGD Xu et al. (2019a), DICE Waniek et al. (2018), Jaccard Wu al. (2019) SimpGCNJin et al. (202T) and ProGNN Jin et al. (2020). We perform FGSM according to Dai et al. (2018). STABLE al. (2022), GNNGuard, and Elastic Liu et al. (202 la) are implemented with the code provided by the authors.
All the hyper-parametern are tuned based the loss and accuracy of the validation set. For Jaccard, the Jaccard Similarity threshold are tuned from (0.01, 0.02, 0.03, 0.04, 0.05). For GNNGuard, ProGNN, SimpGCN, and Elastic, use the default hyper-parameter settings in the authors' implementation.
A.2 THE DISTRUBION OF ADVERSARIAL EDGES
Table shows the distribution of adversarial edges on the graph, attacked by MetaAttack, PGD, and FGSMDar et al. (2018). Only MetaAttack can adjust the distribution of the perturbations according to the size the training set. Specifically, it consistently generates perturbations around the smaller one in the training and the testing set. PGD and FGSM always focus on attacking training nodes, resulting in poor performance when the training set size becomes large.
Fig. is the visualization of the adjacency matrices of Cora and Citeseer. Compared with the results in Table D and Table [ we can see that IS can reflect the density of perturbations in each area of the adjacency matrix. MetaAttack adjust such density according to the size of training set. It focuses attacking the smaller of the training set and the testing set, and the perturbations are nearly uniformly distributed when the training size is 0.5. On the contrary, PGD and FGSM consistently attacks the training nodes regardless of the data split. Consequently, MetaAttack can easily fool GCN no matter how large is the training set, while PGD failed when the training size increases.
Zhu et al. (2021a) shows that MetaAttack fails on evasion attack with a 10%/10%//8%% data split, and it is consistent with our discovery. When the training set is small, such adaptivity will make MetaAttack focus on modifying the local structure around the training set. In the setting of evasion attack, the model is already trained on unbiased data, so testing on unchanged data does not cause worse performance. For example, when the training size is 10%, A R 0.9 x 0.9 = 0.81 and IS,- = 0.007, meaning that the Test-Test is the largest part of the graph, but most of the local structure around testing nodes is not malicious modified.
Table 4: The IS of MetaAttack, PGD, and FGSM under 10% perturbation rate. The Ace indicates the adversarial accuracy, and for attack methods a lower value is better. Clean is the accuracy the vanilla GCN on clean graphs. We highlight the strongest attack in bold.
MetaAAtack
PGD
FCSM
Training
Train- Truin
Train- Text
Train-Traie (1S))
Train-Train (1S:)
Train= (USy)
Tea-TTo (18s)
Asc
Cleun
(1%g)
(18g)
10%
11.085
48035
08007
67.49
$7.650
4.501
0.000
59.55
22:131
4:311
01000
69:00
74.55
20%
3,500
2,055
010039
72.37
5,502
2,055
0.001
73.35
10.041
1,855
0.002
71.23
74.75
30%
2.364
1,546
0.100
75.81
S.142
1.279
0.00
76.15
3.356
1.190
0.000
76.12
76.26
4012
1.554
1.352
0.311
75.05
3.665
0163
0/001
77.30
33390
0.791
0100
77.15
77.19
Cltsseer
50%
2.62
0.00
71.51
2.165
0.541
79.26
70%
0.808
1.179
1213
75.64
1744
01347
0.00
12.23
1.795
0.286
0100
77.56
77.08
50%
0.451
1.508
24444
76.63
1.424
0.271
0.00
79.14
1.413
0.171
0.000
79.1
79.14
902
0.354
1740
5.142
76.51
1.581
01345
0.001
02.23
1.181
0.197
01000
01.14
81-16
10%
1.404
1.475
01504
73.00
4.270
1.467
0/08
06.43
4.88
01011
81.32
95.31
40%
1.228
1.166
0.766
73.84
3.065
1.044
0.055
58.85
3.351
0.964
0.000
89.45
05.49
Palllogs
503
0.776
13665
8191
73.05
1973
0.01
0/00
88.85
3.382
0.807
01000
93.51
05:36
0.542
1,133
1.251
76.19
1.733
0.797
0.000
80.15
1,457
0.201
0.000
91.57
05.57
1.477
90%
1.140
0.435
1.124
13

---

Published as a conference paper at ICLR 2023
(a) Meta-Cora-0.1
(b) Meta-Cora-0.5
(c) Meta-Cora-0.9
(d) Meta-Citeseer-O.1
(e) Meta- Deta-Citesser-O.5
(1) Meta- Citeseer-O.9
(g) PGD-Cora-0.1
(h) PGD-Cora-0.5
(i) PGD-Cora-0.9
(i) PGD-Citeseer-O.I
(k) PGD-Citeseer-0.5
(I) PGD-Citeseer-0.9
Figure 5: The adjacency matrix of Cora and Citeseer attacked by MetaAttack and PGD with different training size.
A.3 PROOF OF THEOREM 4.
Proof. There are N nodes and Nl edges in graph G. Totally ANk will be inserted in the graph. 2
2 ANL
Each node in the training set will have 2 2 Ak more neighbours with different label due to the uniform insertions. Thus, the community features of the nodes in class can be viewed as sampled from biased distribution Ptrain (āly 0):
N + hk) mm (I- hk +
Ak
11
A
(7)
++1
AK ?
+
AF
The structures of testing nodes are not modified, so Prest (i
0) is:
N (1 + uo + (A: hk) A
(8)
ke ++1
k
Let δy and ô2 denote the mean of Ptrain (øly = 0) and Prest (āly = 0), respectively. According to Eq. (6) and the KL-Divergence formula for two normal distribution, we have
(Perain (# y = 0), Ptest { y = 0))
2 log (k +k+1+1 Abyd
1
d(k + 1)
(k+ 1)dt +
k k+1+ Ak
(k + 1) 8, )" A -1 -t - 81) -
14

---

Published as a conference paper at ICLR 2023
Let k+1+ AL 1+1
S, then the first two terms of Eq. (9)
can be rewritten as
d
log S
S>
1.
(10)
S
Take the derivative of Eq. (10) w.r.t to S
1
(11)
1
5
apparently it is larger than 0 for 5 > 1, so Eq. (10)
is monotonically increasing w.r. S and
monotonically decreasing w.r.t. the size of training set t.
For the third term of Eq. (9) we first calculate 80 81. For notational simplicity, we let P
(1 + ho + km
P+
Ak
P
80 81
Ak
k+1
(12)
(A: 1)mm
A
(Ik ++ (k)
Then we let Ak
(A++ 1pp
v. Apparently, v² monotonically decreasing w.r.t. I, and we
(sk (sk+ (k](++T)
easily prove v. A is also monotonically decreasing, because A just introduces constants into each element of
Therefore, Eq. will become larger as l gets smaller. This also holds for nodes in class 1. Then can get the conclusion that the smaller the I, the larger the distribution shift.
A.4 IMPACT OF SURROGATE LOSS AND GRADIENT COMPUTATION
The Impact of Cirain or Leels Table 5 shows the attack tendencies and performance PGD with Ltrein Leelf- We only provide the results Cora, but similar results observed other commonly used datasets for SSNC. Ltrain will make the attack algorithm tend to attack the training nodes, while Leelf will make it attack the testing nodes.
Table 5: The location statistics of adversarial edges on Cora under 10% perturbation. Num represents the number of adversarial edges in the corresponding area. Evasion and Poison are the adversarial accuracy GCN Kipf & Welling (2017) under evasion and poisoning attack. We highlight the stronger attack in bold.
Attack
IS//Num 1S2/Num
ISyNNum clean Evasion
Poison
PGD train
22.18/224
4.28/778
0.00/2
83.56
83.39
77.92
PGD
0.80/8
1.40/252
0.91/740
83.56
81.94
83.55
Ltrain focuses on the loss of the training nodes, which is mainly related the local structure of these nodes. Therefore, when computing the gradient V Catk, only the part of the adjacency matrix associated with the training nodes will be modified, i.e., the Train-Train and Train-Test. PGD train works in poisoning attack but fails in evasion attack. This result is as expected because Pirain is well-perturbed but Prest nearly remains unchanged. There are some edges in the Train- Test, but the largest part of the graph, the Test-Test, is barely changed.
fisetf utilizes the pseudo labels of the unlabeled nodes to compute the loss, so the majority of modifications are around the unlabeled nodes. Although PGDsatf seems to work in evasion attack, the degradation in accuracy not as pronounced as PGDtrain in poisoning attack. We suggest that there are mainly two reasons: (1) The testing set is much larger than the training set, so the same perturbation brings a smaller change in Pteat than in Perain- conduct these experiments. Geisler al. (2021) shows that CE Loss makes algorithms primarily attack nodes that are already misclassified. Such attacks are valid in poisoning attack and can further bias the model po (y) However, in evasion attack, attacking misclassified nodes will not bring any
(2) We use Cross- Cross-Entropy Loss to
15

---

Published as a conference paper at ICLR 2023
drop in Aecuracy.Anothe example that uses Leeff is PR-BCD Geisler al. (2021), 1. which is an novel evasion attack. We present the location statistics of perturbations on Citeseer attacked by it in Table
[ We can that all the perturbations are generated around the testing nodes, leading to effective performance.
Table 6: The location statistics of adversarial edges on Citeseer attacked by PR-BCD.
Pth Rate Train-Train
Train- Tratn-Test
Test- Test
5%
0
15
168
10%
0
29
322
15%
0
55
488
20%
0
69
665
Gradient Computation MetaAttack is special case due to its ability to adjust the distribution of adversarial edges. Even today, many practitioners still consider to be the SOTA of poisoning attacks on small-scale graphs. According to the Theorem 4.1 this adaptivity makes MetaAttack incline to attack the more easily perturbed distributions in Ptrain and Pteat In other words, it identifies structural modifications that significantly increase distribution shift.
We find that this adaptability comes from its way of calculating the gradient. Let's review the meta- meta-gradien gradient expressed in Zügner & Günnemann 2019):
V VaLaukSoo (A, X)) V &hutk (Jor (A,X)) VA (A, + Vor (A. VaOrl;
(13)
VAG - a -
Lir (fo,
(14)
where T is the training steps to obtain the optimal parameter via vanilla gradient decent with learning rate a. The parameters 0 are often fixed and detached when calculating the gradient V Caca in other gradient-basee based methods Xu et al. (2019a); Wu et al. 2019). In MetaAttack, however, 0 is iteratively retrained as the graph is gradually contaminated, and the derivatives w.r.t. the adjacency matrix are taken into account.
The effectiveness and adaptive capability of MetaAttack stems from this gradient calculation method. MetaAttack will perform similar to PGD if the parameters are fixed or detached from the grudient computation. Table 7 shows the performance of Metagelf, Metarrain Detach Detacherain. Fixself, and Detachtvain. Detach and Fix are two variants of MetaAttack. The former detaches the parameters from the meta gradient calculation and the latter fixes the parameters after training in the clean graph. Metasels is the only one that always attacks the more easily perturbed distribution in Ptrain and Prest- Other attack methods with Ceeff will only attack the testing nodes, but Metagalf will attack the training nodes when the size of the testing set is samll. It is because the meta gradient will take the training process into account by Eq. 3, which is associated with the training nodes. Thus, the local structure of the training nodes related to the meta gradient computation. Detach and Fix perform like PGD that the tendency is closely related to the surrogate loss, i.e. Caelf or Ctrain-
As expected, Metagelf outperforms all the variants regardless of the data split. It is worth noting that variants with Lerain usually performs better when the training set is small, while variants with Csels are more destructive when the testing set is small.
Different Surrogate Loss To ensure this tendency is not caused by specific type of loss, we explore the effect of other two losses in Graph Attack, including the Carlini- Wagner loss Xu et al. (2019a) CW= min min(maxezeer Ze Zet 0).and Masked Cross Entropy MCE Geisler et al. (2021)
= 1/V+ Σ Diev+ - log(p!") (i)),, where c* is the ground truth label and ++ indicates correctly classified nodes. For CW and MCE, we can also divide them into Leel and Ltrain according to which nodes used calculate the loss. In Table 8 we present the IS for Metagel/ with CW loss and MCE loss. Meta with CW and MCE can also adjust the distribution of the perturbations according to the size of the training set, which is consistent with CE loss. With all the results, conclude that
16

---

Published as a conference paper at ICLR 2023
Table The location statistics of perturbations and the performance of GCN poisoning attack on Cora under 10% perturbation. ISg-0.8 8 is the IS3 when the size of the training set is 0.8 and reveals the adaptivity of different variants. We highlight the strongest attack method in bold.
Attack
IS/NNum
1Sa/Num
ISm/Num
Poison
1Sg-0.8
Poison-0.8
Meta
14.46/73
4.75/432
0.00/1
73.37
0,00
88.35
Meta,ef/
11.88/60
4,86/442
0.01/3
71.62
3.409
80.32
Detachgrain
14.65/74
4.74/431
0.00/1
79.94
0.00
87.52
Detachself
0.00A)
0,80/73
1.06/433
81.73
23.56
81.44
Fixtrain
15.05/76
4.64/422
0.20/8
79.63
0.00
89.56
Fix,elf
0.00/0
0,85/77
1.05/429
82.80
26.34
83.53
the key to affecting the distribution of adversarial edges is which nodes are used to calculate the loss rather than the type surrogate loss.
Table 8: The IS of Meta,sy with two different surrogate losses, CW, and MCE under 10% perturbation rate. The Acc indicates the adversarial accuracy, and for attack methods lower value is better. Clean is the accuracy of the vanilla GCN on clean graphs.
CW
MCE
Dataset
Training set
Train- Train (IS₂)
Train- (18g)
Test-Test (ISg)
Ace
Train- Train (IS₂)
Train-Test (18g)
Test- Test (18g)
10%
7.615
5.078
0.005
71.55
9.012
4.854
0.051
74.42
83.56
20%
2,953
2.559
0,096
82.07
3.969
2.548
0.043
78.80
85.67
30%
1,903
1.626
0.295
80.64
2.450
1.622
0.198
84.49
86,99
40%
1.430
1.231
0,500
80.07
1.689
1.132
0.517
81.88
87.01
Cora
50%
0.986
1.079
0.856
83.11
0,828
1.115
0.943
80.24
87.22
60%
0.625
1.182
1,300
83.40
0.718
1,091
1.361
83.05
88.04
70%
0.447
1.489
1.742
81.17
0,540
1.338
1,940
84.12
89.98
80%
0,370
1.942
3,572
79.72
0.410
1,979
2,629
83,52
88 88.87
8.402
81,80
10%
6,971
5.103
0,003
65.09
9.652
4.967
0,000
68.14
74.63
20%
3,924
2.569
0.026
74.03
3.045
2.646
0.043
70.77
74.73
30%
2,413
1.760
0,084
74.58
1.720
1.942
0,056
72.77
76.26
40%
1.598
1.433
0.152
75.28
1.411
1.439
0.228
72.49
77.19
Citeseer
50%
1,350
1.087
0.472
75.62
1.317
1,082
0.516
73.25
77.66
60%
0,825
1,208
0.772
76.31
0,862
1.134
0.909
75.13
79.26
70%
0.634
1,395
1,161
72.79
0.656
1.323
1.375
75.17
77.66
80%
0,409
1.937
3.034
73.
0,520
1.825
2.138
72.78
79.14
90%
0,381
3.536
3,792
70.00
0.445
3.338
4,137
77.79
82,26
10%
6.202
4,386
0.177
70.44
9.274
4.307
0.1.66
68.09
95.04
20%
3,409
2.150
0.272
73.66
2.948
2.257
0.247
69.63
95.33
30%
2,163
1.444
0.405
74,23
1,699
1.512
0.432
70.38
95.21
40%
1.170
1.144
0.639
76.79
1.039
1.214
0.697
73.80
95.49
Polblogs
50%
0.876
1.130
0,864
73.30
0.790
1.099
1,013
74.32
95.36
60%
0.527
1.009
1.435
73.39
0.574
1.240
1.237
74.18
95.97
70%
0.399
1.488
1.990
71.23
0,368
1.452
2.322
69.71
95.67
80%
0,328
2.144
2,627
71.74
0.325
2.110
2.942
67.52
96.85
90%
0.299
3.869
6.244
71.17
0.299
3.742
8.526
68.83
17

---

Published as a conference paper at ICLR 2023
Pseudo-labels in Leels Attacks with pseudo labels behave similarly to those with ground labels because (see the Table [ Meta-true means Meta-self uses the ground-truth labels to generate perturbations instead of pseudo labels). We guess it is because, in homophilous graphs, the pseudo labels are generally accurate. Thus, attacks with Lself will focus modifying the local structure of the testing nodes make the predictions away from the ground-truth labels. In many cases, the size the testing set is relatively large, so is hard to increase the distribution shift by modifying the testing structure according to Theorem 4.1 This way, methods like pGD fail.
Table 9: Adversarial accuracy () on Cora and Citeseer attacked by Metasels and Metasrue.
Datasets
Ptb rate
Metagelf
Metäcrue
5%
76.36
75. 75.84
10%
71.62
71.33
Cora
15%
66.37
64.42
20%
60.31
58.81
5%
71.13
71.20
10%
67.49
67.24
Citeseer
15%
61.59
60.88
20%
56.26
56.14
A.S INSERTION vs. DELETION
Proof of Theorem 5.1
Proof. The Kl-Divergence between Ptrain (øly 0) and (aly 0) of insertion is shown Eq. 9 and we denote it as DKL-INS. Similarly, we have DKL DEL as followed:
DKL-DEL (Ptroin (PLree (2)
0), ( y = 0))
11 log
(k ++11
Ak 4
+ d(k 1)
(h: 1)(6)) 51)" 51) - d) (15)
2
(1+ 1)a
k+1
Ak
where 8, (1+hk poo + (k- 1ol)
k+1- طن
Now we compare DKL-INS and DKL-DEL.
In
1++11 Ar
k+1
due to the assumption x(++1] I In We already know that log Srd w.r.t. Sf S 2 1n2. Therefore,
+ d monotonically increasing
(k + + Ak )d (k: + 1)d
d(k + 1) 1: + 1+ AE
(k: + Akyd
d(k +
log
log
(16)
(k + 1)d
1: ++1-
Then, if uf (8) 81) T
51), we conclude that DKL-INS DKL-DEL-
A P (k 1)
8, 8,
(17)
k
(tk + Ak) (A: +1)
Let 8/ 8, = u. This is equivalent comparing [0| and lu].
(k + 1)ll1 - P
w
k (tk + a) + 1)
(hk + 1)(m - mo)
Ak
(18)
(th + ++ (1) + 1)
(hkk + 1) - 140) + Ak)
Ak
(th + Ab) + (k +1)
We have |u]:
Ak (R: h At + + AA)
|u|
(19)
(th + t AA) + 1 - AA) +1)
Neglecting the common terms of [e] and |u),, only need compare the following two terms:
[11 + hL: A (k - htk + 1 AA)
(20)
18

---

Published as a conference paper at ICLR 2023
Both of of them positive because 1 > h 0.5 and (2h 1)t A latter term:
The former term subtract the
1 (2h + A - 1) (2th A
(21)
As h > 0.5 and (2h 1) A due to the assumption, eq. (2) is positive. To sum up, DKT.-ING INS > DKL.DELL This conclusion also holds for class 1. We can conclude that the distribution shift caused by insertion is larger.
Synthetic Graph We build graph containing two types of nodes. The features of class 0 E R and sampled from (0, A..2), and the features of class 1 are sampled from M/1, Ao.2), where Ag.2 a diagonal matrix, and each element is 0.2. There are 150 nodes in class 0 and class 1, respectively, and all nodes of the same class are connected to each other. Thus, this graph is dense and the possibilities to insert and delete is balanced. We conduct MetaAttack attack this graph, and the results are listed in Table [0] We find that MetaAttack still tends to inset but not delete edges.
Table 10: Share (in %) of edge deletions and insertions by MetaAttack on the synthetic graph.
Ptb Rate
Insertion
Deletion
5%
814
311
10%
2087
163
15%
2961
414
20%
3704
796
A.6 LEVERAGE OF HIGH- -EGGEE NODES
Suppose the node features follow distribution like the normal distribution, which probability density is higher around the mean. In that case, the aggregation can make the high-degree nodes move to the high-density region and reduce the variance. High-density data can be easily classified and is
insensitive to noise Zhu et al. (2022a). According to Li al. 2022) we can trust them more and assign them higher weights during the aggregation:
h = ReLU (E
(d.d,)o.5
0..5
h w;),,
(22)
Z
JEN;
where is the degree, and Z is normalization coefficient. This only modifies the aggregation weights in the GCN and can be merged into any Robust GNNs with vanilla GCN. Table Table demonstratss that assigning high-density data higher weights can indeed improve the robustness of GNNs. This trick just slightly leverages the properties of high-degree nodes. However, one also might apply a more sophisticated method which we leave for future work.
A.7 HEURISTIC ATTACK
The algorithm of our heuristic attack is shown in Algorithm 1
We first construct the candidate attacking set C that contains the nodes whose degrees are lower than the average degree. Then we divide C. into Cirain and Crest- We generate cross-label edges on the graph according to the data split. Specifically, we compute Å1, A2, and A using Eq. (3). Here we suppose the training set is much smaller than the testing set, i.e., d λ3. The total perturbation is Npes A [E). We inject A cross-label edges into the Train-Train the nodes in the training we label them by the pseudo labels predicted by two layer vanilla GCN.
Npt X;
and Npto
A2 x, into the Train-Tees area. For
In Fig. 6 we compare the proposed algorithm with other attack methods on Citeseer and agbbn-arxiv. On Citeseer, method can achieve comparable performance to MetaAttack, and even better under low perturbation rates.
The average runtime of 10 runs is shown in Table 12] Gradient based methods need to optimize all possible entries in the dense adjacency matrix A. which comes with expensive computation and quadratic space complexity. Our methods and DICE are both rule-based, much faster, and
19

---

Published as a conference paper at ICLR 2023
Table 11: Classification accuracy(%) on dataset Cora and Citeseer attacked by MetaAttack under different perturbation rates (stronger is bold). The asterisk indicates that the GCN part of this model replaced with Eq. (2)). Jaccard Wu al. (2019) and SimpGCN [Jin et (202T) are two robust GNNs with vanilla GCN. The data split follows 10% 10% 80%(nrri valítest).
Datasets
Ptb rate
GCN(")
Jaccard(*))
SimpGCN(())
0%
83.56(82.76)
81.79(81.11)
83.77(83.64)
5%
76.36(78.17)
80.23(80.57)
78.98(80.45)
Cora
10%
71.62(74.23)
74.65(76.99)
75.07(78.04)
15%
66.37(70.89)
74.29(76.32)
71.42(75.31)
20%
60.31(69.59)
73.11(73.42)
68.90(73.29)
0%
74.63(74.00)
73.64(73.11)
74.66(75.23)
5%
71.13(72.71) 71.15(71.48)
73.54(74.25)
Citeseer
10%
67.49(69.17)
69.85(70.53)
72.03(72.90)
15%
(1.59(64.35)
67.50(68.82)
69.82(72.15)
20%
56.26(60.86)
67.01(67.14)
69.59(71.26)
Algorithm 1: Heuristic Attack
Input: Graph G E), Labels yL. Perturbation rate A Output: The poisoned graph g'
Npto = A [E];
Compute the degrees dl of all nodes and the mean dmeaai
Construct the low-degree node set C = {w; for o; in V if di < dmeon);
Construct Crrain that contains training nodes in C and Crest that contains testing nodes in C:
Compute Å1, A2, and As using Eq. 33:
Amin min(A1, As)
> Suppose A1 < A3;
A A1
r1
Aa for i=1, ..., T1 Npt
72
X1+
Connect two nodes from different class in Cirain that not connected yet. 11 end
for i=1, F2 ppb do
13
Connect one node in Ctrain and one node in Ctest that are from different class and not connected yet.
14 end
15 return the poisoned graph g':
space-saving, Our method runs faster than DICE in ogbn-arxiv because ours randomly sample nodes from the candidate set, which is much smaller than the entire node-set.
Our heuristic attack method is coarse-grained and straightforward, and we do not aim to propose SOTA mode. We try to clarify that by following Tips to 5 and inheriting the tendencies which enlarge the distribution shift, performance close to that of the gradient- based method can be achieved efficiently. More than that, can be scaled large graphs.
20

---

Published as a conference paper at ICLR 2023
0.75
0.75
0.65-
0.60
DICE
0.60
PGD
0.55
DICE
Ours
Ours
Pesturbation Rato (%)
Potturationn Rate (%)
(a) Citesecr
(b) ogbn-arxiv
Figure 6: The adversarial accuracy of GCN attacked by different methods on Citeseer and ogbn-arxiv. PGD and MetaAttack face the OOM problem on ogbn-arxiv.
Table 12: Average time of different attack methods Citeseer and ogbn-arxiv after 10 runs.
A (Citeseer)
5%
10%
15%
20%
Ours
0.063
0.121
0.185
0.248
PGD
7.143
7.172
7.1650
7.186
Meta
129.227
271.354
405.466
548.913
DICE
0.043
0.044
0.046
0,047
A (ogbn-arxiv)
5%
10%
15%
20%
Ours
6.642
11.696
16.564
22.496
PGD
OOM
/
Meta
OOM
/
DICE
49.243
53.521
56.213
56.755
A.8 IMPROVE ROBUSTNESS VIA SELF-TRAINING
10%//1%/80% is the most commonly used data split in graph adversarial attack, under which effective poisoning attack methods like MetaAttack and PGD tend to attack the training nodes, so the local structure of testing nodes nearly clean (according to Fig. 5). To summarize, the clean information includes the labels of training nodes and the local structure of test nodes. Thus, straightforward method to enhance the robustness is self-training Li et al. (2018). )). We can assign pseudo-labels to the testing nodes and then train the GNN via the aseudo-labels and the clean local structure.
use an MLP instead of a GNN to acquire the pseudo-labed because the local structure of training nodes is contaminated. Specifically, first train an MLP with given labels, then select the predictions with the highest confidence for each class by comparing the softmax scores and add them to new label set Vpsu- We finally train new GCN by computing cross-entropy loss on Vpsa- This Trainingg Robust GCN (STRG) is described in Algorithm 2 Considering this method from the perspective of data distribution, it actually reduces the distribution shift effectively by training with Ptest- Although the pseudo-labels will introduce some new problems, like label noise, it can viewed a trade-off between performance and robustness.
Here we provide a very simple implementation.
We compare STRG with some baselines and SOTA robust GNNs on two datasets under MetaAttack in Table [3] We set m 80 in these two datasets GNNGuard Zhang & Zitnik (2020) and ProGNN Jin et al. 2020) are two robust GNNs with structure learning. SimpGCN et al. (202 utilizes ANN Graph keep the nodes with similar features close the representation space and self-learning regularization to keep the nodes with dissimilar features remote. Elastic Liu et al. (2021a) introduces (--norm to graph signal estimator and proposes elastic message passing which is derived from one-step optimization of such estimator. The local smoothness adaptivity enables the Elastic GNNs robust to structural attacks. STABLE al. (2022) optimizes the graph structures by unsupervised representations learned by contrastive learning. The data split is 10%/10%/800 and we set the perturbation rate from 0% to 20%. The implementation of these methods follows Appendix A. and the paramete / in STRG 80.
21

---

We design this method with a hypothesis, i.e., that adversarial edges are mostly located around training nodes, but attackers can perturb Ptest make unbiased model predict the biased data. However, here is also trade-off between performance and unnoticeabilty for attackers. If the attacker spreads their attacks over the whole graph instead of focusing on the training set, the performance will Published as a conference paper at ICLR 2023
Algorithm 2: Training Robust GCN (STRG)
Input: Graph G = (V, Labels yr
Output: The predictions of testing nodes
(X) R Z is the output of well-trained MLP: Initial empty node set Peni
for each class C₁ do
Find the top nodes in Z
Add them to the Vpeu
end
Return the predictions of f*;
Table 13: Classification accuracy (%) under different perturbation rates. The top two performance
highlighted in bold and underline.
Dataset
Ptb Rate
GCN
GNNGuad
ProGNN
SimPGCN
Elastic
STABLE
STRG
0%
83. 03.5622.22
78.52=0.46
84.5520.30
83.77=0.57
84.76=0.53
85.58:0.56
82.59=0.65
5%
76.36:1084
77.96:0.54
79.8410.49
78.98:1110
82.00=0.39
81.40110.54
82.52.0059
Cora
10%
1.262
10.56
74.2210.31
75.07:1..09
76.18:0046
80.49
82.34 0.25
15%
66.37411.77
14.15=1.64
72.7540.74
71.4243.29
74.41-0.97
78.5540.44
79.96-0.39
20%
1.93
1..03.1.11
64.40.0.59
68.90.13.22
69.641:062
7..80
77.72 0.27
0%
74.63+00.66
70.07=1.31
74.73+0.31
74.66++0.79
74,86=0.53
25.82++0.41
76.46-0.67
5%
71.1340..5
72.88+0.32
73.54+0.92
0.58
Citeseer
10%
67. 07.4940.84
67.89=1.09
69. 00.94440.4
72.03+11.30
73.41=0.36
73.45+00.40
76.56-0.52
15%
1..59:1146
69. 14:20.844
62.61:0.64
69.82211.67
67,51=0.45
73.1540.53
76.58-0.84
20%
56.26.10.99
69.20.10.78
55.4911.50
69.59113.49
65.65
72.7610..53
7..14-0.40
We can observe that STRG outperforms other methods under different perturbation rates. In particular, STRG achieves almost complete robustness on the Citeseer. The performance shows no degradation the perturbation rate rises. Additionally, MLP is much faster than graph models, this self- training strategy can be easily scaled to large graphs. Here we use GCN as the downstream task classifier, but in fact any GNNs can be merged with it.
drop considerably (we will elaborate on this in Appendix A.9). In nutshell, STRG can successfully defend against effective attack methods, and when an attacker tries to bypass the defense strategy of STRG, the attack will fail.
A.9 DISCUSSION ON THE DATA SPLIT
0.75
0.50
0.75
Metayitnut
-
Melayttouu
0.70
0.65
PGDDathur
PGDwihou
0.55
PGD
PGD
Rat
Ran
20
15
20
15
15
Perturation Kato (%)
Peturbation Kate (*6)
(a) Cora
(b) Citescer
Figure 7: The adversarial accuracy of GCN on Cora and Citeseer. PGD and Metawithout are two variants without the information of data split
Nearly all gradient- attack methods know the data split by default. However, the importance of is ignored. Fig. shows that MetaAttack and PGD attack Cora and Citeseer without the information
22

---

Published as a conference paper at ICLR 2023
Trin
07-
Tran
Train
0.7
04
Density
Density
Density
0.3
0444
0.3
0.3
0.1
0.1
0.5
5-30
10.20
20.00 40
0.5
5:10
10:20
20:40
0.5
5:10
10.20
23-40
Degree Distribution
Degree Distribution
Degree Distribution
Citeseer
(b) Cora
(c) Polblogs
Figure 8: The degree distribution of Citeseer, Cora, and Polblogs attacked by MetaAttack under 5 5% perturbation. The degrees of training nodes are higher than the testing nodes, which may make the attack noticeable.
Table 14: Performance GCN attacked by different methods under 5% perturbation where the Public denotes the widely used data split that uses 20 nodes per class training set.
Datasets
Cora
Citeseer
Split
Public
10% 10%%0%
Public
10% 10%80%
Clean
81.23++0.31
03.5
69.73++0.52
74.63++0.66
MetaAttack
63.79:10.68
76.36+00.84
52.04-10433
71.13+0.55
PGD FGSM
70.16:10.34
79.9810.31
58.50:10.26
71.45::0.47
71.15:10.56
80.37=00.48
62.53
72.55
of data split. Data split is necessary when implementing PGD and MetaAttack, so conduct the attack in a random split, which is inconsistent with the split during testing the classifier. PGD and Metawithous are not as effective as the vanilla models, and their performance is even close the random attack. It is hard to effectively manipulate the prediction without the information of the data split. Meanwhile, attackers and defenders can easily enhance their model by attacking or defending the more vulnerable part of the graph. It is essential to realize that the leakage of the data split can posc a severe security risk.
Moreover, the public split, i.e., 20 nodes per class as the training set, will make the training set significantly small so that Pirain easy to be perturbed. We list the performance poisoning attack methods under different data splits in Table [4] The attack algorithms can easily work on the public split. addition, such a small training set might make the attack noticeable. As shown in Fig. 8 under small perturbation rate (e.g. 5%), if attackers only modify the local structure around the training nodes, the attack is easily detected.
23


Reviews:
[{"review_id": "rfCh_dayE3W", "reviewer": "Reviewer_Lqax", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper discovers a phenomenon that the gradient-based graph structure adversarial attack aims for increase the train-test distribution shift. The authors provide some theoretical proofs and then give explanations to some graph attack observations based on the prove. What’s more, this paper gives some practical tips on robust GNNs and design their attack and defense algorithm based on some tips.", "summary_of_the_review": "This paper revisits gradient-based graph structure adversarial attack methods from a distribution view. The authors give some theoretical proofs and explanations to graph attack observations. However, the empirical analysis for pgd and meta-attack from a distribution view is somehow being discussed in the previous work and the authors have not mention relevant literature or compare with these works. As a result, I think this paper is marginally above the acceptance threshold.", "strength_and_weaknesses": "S1: This paper explains the structural adversarial attack from a distribution perspective, which is seldom discussed in graph adversarial attack.\nS2: This paper both theoretically and empirically proves this ‘distribution shift’ phenomenon and revisiting classical attack methods like PGD and MetaAttack.\nS2: This paper gives explanations to the existing graph attack observations from a data distribution view.\n\nW1: The distribution analysis from PGD and MetaAttack is similar to that in [1]. Besides, the usage of pseudo labels in the semi-supervised node classification task is also similar. Maybe the authors could give more explanations to the difference of these two works and how this paper improves from [1].\nW2: The baseline set of both attack and defense algorithm comparison in Table 10 and Figure 6 is relatively small, which may degrades the effectiveness of proposed methods.\n\n[1] Zhan H, Pei X. Dealing with the unevenness: deeper insights in graph-based attack and defense[J]. Machine Learning, 2022: 1-33. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gwlGC3fBNvG", "reviewer": "Reviewer_Gcf5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper thoroughly studies two gradient-based attack methods on graph-structured data, namely MetaAttack and PGD, and reveals their behavior patterns from a data distribution shift perspective. Based on the theoretical analysis regarding training and test data distribution, the authors propose several practical tips from both attack and defense perspectives.\nExperiments that are specifically designed for these tips align with the theoretical foundations and show insights for future designs.\n", "summary_of_the_review": "In summary, the paper has merits from the theoretical analysis and shows insights for future attack and defense designs on graph learning with practical tips. Meanwhile, my concorns are mainly from two aspects:\n* The assumption for train and test data distributions need further clarification. The discussion on the impact of pseudo labels versus real labels can be improved.\n* Some of related works should be included.\n", "strength_and_weaknesses": "Strengths:\n* The paper contains multiple original ideas that are also well-executed and theoretically well-grounded.\n* The attack analysis on the behaviors of gradient-based attack methods is novel and could provide insights for further graph robustness research.\n* The empirical observations are interesting and the practical tips seem useful for future graph learning attack and defense designs.\n\nWeaknesses:\n* The assumption that $p_{train}(\\tilde{x}, y)$ and $p_{test}(\\tilde{x}, y)$ are the same on clean graphs might be too strong as there are many works on the out-of-distribution analysis on the graphs recently[1]. Perhaps the authors should narrow down the analysis to graphs with specific types to meet this assumption. \n* While the empirical results on the impact of $L_{train}$ and $L_{self}$ are interesting, how the pseudo labels affect the theoretical results seems unknown. Meanwhile, why there are no results for MetaAttack for the impact of $L_{train}$ and $L_{self}$?\n* Some of the related works are missing. For example, a similar observation on the unevenness distribution is made in [2] and the authors are suggested to discuss the difference with [2] in detail. Meanwhile, some other literature[3,4,5] that analyzes the behaviors of adversarial examples from the spectral perspective are also suggested to be included in the related works.\n\n[1] Out-Of-Distribution Generalization on Graphs: A Survey, ArXiv 2022\n\n[2] Dealing with the unevenness: deeper insights in graph-based attack and defense, Machine Learning 2022\n\n[3] Adversarial Attacks on Node Embeddings via Graph Poisoning, ICML 2019\n\n[4] Not All Low-Pass Filters are Robust in Graph Convolutional Networks, NeurIPS 2021\n\n[5] Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge, TKDE 2022\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Sq1dWVDm3H", "reviewer": "Reviewer_3B87", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper tries to have a better understanding of adversarial attacks on graphs. They revisit graph adversarial attack from a data distribution perspective and formulate the distribution shift: the adversarial edges are not uniformly distributed on the graph.\nThen, they provide an explanation for the effectiveness of the gradient-based attack method from a data distribution perspective and revisit both poisoning attack and evasion attack. Next, they provide several practical tips on both attack and defense and meanwhile leverage them to improve existing attack and defense methods. ", "summary_of_the_review": "\nStrength\n1. The research problem is very important and this paper provides different aspects to understand how does attackers work on graph data. \n2. They summarize some useful tricks to conduct adversarial attacks and defense. \n \n\n\n\nThere are some concerns regarding this paper.\n1. Distribution Shift is unclear to me. It seems they mainly focus on edges among train-train, train-test, test-test. It would be better if you could motivate this well and provide better explanations. \nIt's still hard to understand the distribution shift for attacking. \n\n\n\n2. This paper focuses on adversarial attacks on structure attacks, which limit their applications in various tasks and can not be well generalized to many tasks. \n\n\n\n3. As for the tips on both attack and defense, some of them have been found in Adversarial examples on graph data: Deep insights into attack and defense-2019.\nIt would be better if this paper could provide more insights into graph data from both structure and feature aspects. \n", "strength_and_weaknesses": "\nStrength\n1. The research problem is very important and this paper provides different aspects to understand how does attackers work on graph data. \n2. They summarize some useful tricks to conduct adversarial attacks and defense. \n \n\n\n\nThere are some concerns regarding this paper.\n1. Distribution Shift is unclear to me. It seems they mainly focus on edges among train-train, train-test, test-test. It would be better if you could motivate this well and provide better explanations. \nIt's still hard to understand the distribution shift for attacking. \n\n\n\n2. This paper focuses on adversarial attacks on structure attacks, which limit their applications in various tasks and can not be well generalized to many tasks. \n\n\n\n3. As for the tips on both attack and defense, some of them have been found in Adversarial examples on graph data: Deep insights into attack and defense-2019.\nIt would be better if this paper could provide more insights into graph data from both structure and feature aspects. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DBa2nUAsna", "reviewer": "Reviewer_Vakj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper explains the reason behind the effectiveness of Gradient-based attacks for poisoning and evasion on semi-supervised node classification tasks on the graph. ", "summary_of_the_review": "This paper has some merits, some results are taken from image adversarial attacks but overall the idea is novel enough. The experimental results are not verifiable. It is recommended that the author submit their code so that reviewers can make sure their results are accurate. ", "strength_and_weaknesses": "Strength:\n- It is an important and interesting problem to investigate. \n- Addressing this problem from a distribution perspective is interesting\n- Provided tips for attacks and defenses that can be useful for other research works are very interesting. \n---------------------------------------------------\nWeakness: \n- This paper claims to have found out that the adversarial attack is successful because it enlarges the shift between test and training. This is, however, a well-understood result from image adversarial attack and it is obvious. \n- This paper emphasizes that the gradient-based attack causes this shift. Could authors please justify this a bit further? Can these results only be applied to gradient-based attacks or is it applicable to different types of attacks?\n- it seems like their analysis of distribution shift is limited to the choice of data and the attack. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster