Not All Low-Pass Filters are Robust in Graph Convolutional Networks
Authors: Heng Chang
Yu Rong
Tingyang Xu
Yatao Bian
Shiji Zhou
Xin Wang
Junzhou Huang
Wenwu Zhu
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph representation learning
adversarial robustness
graph mining

Abstract: Graph Convolutional Networks (GCNs) are promising deep learning approaches in learning representations for graph-structured data. Despite the proliferation of such methods, it is well known that they are vulnerable to carefully crafted adversarial attacks on the graph structure. In this paper, we first conduct an adversarial vulnerability analysis based on matrix perturbation theory. We prove that the low- frequency components of the symmetric normalized Laplacian, which is usually used as the convolutional filter in GCNs, could be more robust against structural perturbations when their eigenvalues fall into a certain robust interval. Our results indicate that not all low-frequency components are robust to adversarial attacks and provide a deeper understanding of the relationship between graph spectrum and robustness of GCNs. Motivated by the theory, we present GCN-LFR, a general robust co-training paradigm for GCN-based models, that encourages transferring the robustness of low-frequency components with an auxiliary neural network. To this end, GCN-LFR could enhance the robustness of various kinds of GCN-based models against poisoning structural attacks in a plug-and-play manner. Extensive experiments across five benchmark datasets and five GCN-based models also confirm that GCN-LFR is resistant to the adversarial attacks without compromising on performance in the benign situation.

Not All Low-Pass Filters are Robust in Graph Convolutional Networks
Heng Chang'; Yu Rong", Tingyang Xu², Yatao Bian', Shiji Zhou', Xin Wang"t Junzhou Huang,, and Wenwu Zhu
Shenzhen Institute, Tsinghua University Tencent Al Lab DDpartment of Computer Science and Technology, Tsinghua University
"Tsinghua-Berkee
{changh17, zajj1))mmmiss.......... ttteemmatssssssssssaa..mm edu. en, {xin_ sein_wang, wwwhuu)taaingnuaa..de.. cn,
yu. yo.ronghhotmail.com com, Tingyangzuutencent.. com, yatao. biandgmail. com, jzhuang750gail..cmm com
Abstract
Graph Convolutional Networks (GCNs) are promising deep learning approaches learning representations for graph-structured data. Despite the proliferation of such methods, is well known that they are vulnerable to carefully crafted adversarial attacks on the graph structure. In this paper, we first conduct adversarial vulnerability analysis based on matrix perturbation theory. We prove that the low- frequency components of the symmetric normalized Laplacian, which usually used as the convolutional filter in GCNs, could be more robust against structural perturbations when their eigenvalues fall into certain robust interval. Our results indicate that not all low-frequency components are robust to adversarial attacks and provide deeper understanding of the relationship between graph spectrum and robustness of GCNs. Motivated by the theory, we present GCN-LFR general robust co-training paradigm for GCN- based models, that encourages transferring the robustness of low-frequency components with an auxiliary neural network. To this end, GCN-LFR could enhance the robustness of various kinds of GCN-based models against poisoning structural attacks in plug-and-play manner. Extensive experiments across five benchmark datasets and five GCN-based models also confirm that GCN-LFR is resistant the adversarial attacks without compromising on performance in the benign situation.
1 Introduction
Graph Convolutional Networks (GCNs) elaborate the expressive power of deep learning from giid data to graph-structue structured data and have achieved remarkable success in a wide variety of domains 7 6
[9]. Just like CNNs, modern GCNs could promisingly learn both the local and global structural patterns of graphs through designed convolutions. However, the vulnerability of GCNs against adversarial attacks has been revealed The lack of robustness arouses concerns on applying GCNs in a variety of fields pertaining to security and privacy. Adversarial attacks graphs aim to degrade the ability of representation learning of GCNs, and fool them to make wrong decisions by perturbing either node features graph structures. Given the complexity of the underlying structural information and the ease of operation in practice (50), the majority of literature focuses on the adversarial attacks on structures by insertin//removiin/eeiin
13 27
22 30 g
18 31 12
recently 70 11 99.
adversarial edges, i.e., structural attacks. In other words,
"Heng Chang is supported by 2020 Tencent Rhino Bird Elite Training Program. Work done during Heng's internship Tencent Al Lab.
i CCoresponding authors.
*Code available htttp:://gttabb..co/S/tttttt///t
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

structural attacks on graphs during the training stage of GCNs with node features unchanged becomes a commonly considered setting by attackers [24]. Therefore, it of emerging importance to enhance the robustness of GCNs against structural attacks, which is also the aim of this work.
For a better understanding of the structural attacks, it naturally leads to the question: Do the adversarial edges post equal inftuences on the graph spectrum? Here, graph spectrum plays a significant role in Graph Signal Processing (GSP) [45 39 and graph learning. Empirical observations from recent papers suggest the answer could be "no". We can observe that the perturbations resulting from structural attacks express an implicit trend on the graph spectrum [4]. As the toy example shown in Figure ! fow-frequent
components (far left) tend to be more robust in comparison with high-frequency ones (far right). Similarly. [29] observes that the low-pass filters seem be more stable than high-pass pass filters when we randomly add/remove edges. These observations point to promising direction for developing principled defense approaches based on the theoretical analysis of graph spectrum.
Contributions. To mitigate the vulnerability of GCNs against adversarial attacks, in this pa- per, we aim bridge the gap between the spec- tral analysis and the robustness of GCNs under structural perturbations. Specifically, for the symmetric normalized Laplacian, which is com- monly chosen as the graph filter in GCNs, we prove that the low-frequency components could be more robust against both one-edge and multi- edge perturbations when their eigenvalues fall into a robust interval. Interestingly, this result reveals that not all low-frequency components are robust to adversarial attucks.
Clean Graph G
Eigr parta
Perturbed Graph
7.
72
A3
24
2/
A4
27
7g
Spoctral Dificrence
Figure 1: Observation. After adversarial attacks on the structure of graphs, the perturbations on the low-frequency components (far left) are smaller than that in the high-freyuency ones (far right).
Considering the benefit from robust interval in low frequencies, we further propose GCN-LFR (Low-Frequency based Regularization), a general robust co-training paradigm that can transfer the robustness from the eligible low-frequency components. GCN-LFR is general defender that can work with any GCN- model against various training-time attacks. In particular, GCN-LFR regularizes the training process of any given GCN with the robust information from an auxiliary regularization net MLFR. which injects a set of learnable parameters to imitate the robust interval for low-frequency components. Moreover, instead of jointly training two branches, we design an alternative training scheme to accelerate the training process. We observe that the alternative training scheme also benefits the final performance in practice.
In experiments, to demonstrate the flexibility of GCN-LFR, we integrate GCN-LFR with five popular GCN-based models and compare GCN-LFR with four state-of-the defenders across five benchmark datasets under variety of settings, including one-edge targeted, multi-edge targeted, and non- targeted attacks. Extensive results demonstrate that GCN-LFR consistently outperforms the defending baselines under all settings. Remarkably, we also show that GCN-LFR successfully enhances the robustness of GCNs without deduction of performance on benign graphs. further reveals the broad applicability and relevance of GCN-LFR in the area of deep graph learning.
2 Related Work
Adversarial attacks on graphs. Adversarial attacks graph neural networks have drawn unprece- dented attention from researchers recently [47] 24 49). Based on the stage where the attack happens, adversarial attacks on graph-structured data can be divided into 1) poisoning attacks (e.g., Net- tack (70) that perturb the graph in the training stage and 2) evasion attacks (e.g.. RL-S2V [TI] that perturb the graph at testing. A series of studies integrates various of techniques to construct persuasive adversarial samples, such as gradient based methods [55 60 meta-learning [71]. matrix perturbation theory (. graph generation [32. graph signal processing [9] and reinforcement learning [ 48
Defenses on graphs. Other than the adversarial attacks on graphs, researchers are also concerned about the robustness of graph models. Generally, we can category the existing methods into two families: spatial-based and spectral- based defense. 1) Spatial-based defense. GCN-Jaccard [55] pro- poses to examine fake edges in the step of preprocessing by utilizing similarity metrics. RGCN 67].
2

---

Pro-GNN [25], and VPN 23 focus on proposing new variants of GCNs that can effectively defend against attacks on VanillaGCN. GNNGUARD 63 detects the adverse effects existing the relation- ship between the graph structure and node features by neighbor importance estimation. Low-Pass 53 considers low-pass message passing from neighborhoods, which is similar to the attention mechanism in GNNGUARD to defense structural attacks. 2) Spectral-based defense. GCN-SVD [4] empirically verifies that only the high-rank singular components of the graph are affected by Nettack, and prepro- cesses the poisoned graph via SVD with pure structural information for defense. In this paper. we first explore the theoretical connection between robustness and graph spectrum, and propose GCN-LFR to bring the robustness information from eligible low- wwwfreuuency components in the spectral domain. The proposed framework GCN-LFR is a general defender and can protect various GCN-based models from adversarial attacks.
3 Preliminaries
We consider an undirected attributed graph 9 = (V, X), where | N the set of N nodes, & C V x V is the set of E edges, and X = [01, ..., uN is the associated feature matrix, in which Iu E RM is the M --dimensionall node feature for node u E V. We utilize N₂, to denote the neighbors of node We denote the adjacency matrix A RNN,, where Aue {0, 1 indicates whether an edge euv E E exists. The node degree matrix is defined as D = diag(d1, ..- d,), where d, E. Au. represents the degree of node An adversarial attacker deliberately perturbs edges in 9 and results in the poisoned version of G. which we denote as 9' = (V", "",,'' X), and A is the perturbed version of A. Let L = D 122(D - D 1/2 be the symmetric normalized graph Laplacian. L has cigenvalues ranging from 0 to 2. Á = D AAD = - L is the symmetric normalized adjacency matrix, whose eigenvalues range from -1 to Specifically, the low-freqeency components refer to the ones of L with eigenvalues in [0. 1) (of Á with eigenvalues in (0, 1)). and the high-frequency ones refer to that of L with eigenvalues (1, 2] (of Å with eigenvalues in [-1, O)).
3.1 Graph Convolutional Networks
VanillaGCN can be viewed as the spectral convolution based on the Fourier transform on graphs with first-order Chebyshev polynomial filter g The layer-wise update rule is given as:
feature transformation
H = (') e, graph convolution HI+1) ((g(C)HH())
(1+1)
(1)
where (I++)) E R Nxx"") is the output from hidden layer with input as H E Nxx" 9()) refers the dimension of output layer 1. For the input layer, we have H X. (()) refers the activation function, such as ReLU, O E "0g" xg refers to the weight matrix. In Eq. 11, different filter g leads to different GCNs. For example, VanillaGCN along with its variants [61] 16 I0)
usually use the symmetric normalized adjacency matrix Å I, L as g(C). Therefore, we mainly focus on the analysis filter Á, and try to find out the connection between the robustness of GCNs and the perturbation on Á. To ease the notation, we denote U and = diag(\1, "'., "h,,,"",,,,,,,,, ,AN) as the Digen-pairs of Å in the following sections unless otherwise indicated.
3.2 Poisoning Structural Attacks
Poisoning structural attacks towards graph-structured data focus on corrupting the topology during training stage [24]. Specifically, the attacker is able to delete or insert a small number of edges on the benign graph to generate perturbed graph g' with adjacency matrix A'. Through this manipulation, the attacker intends to fool the prediction of GCNs and damage the performance of the downstream learning tasks. Formally, given fixed budget of perturbation A on edges, i.e., A| - Allo < 2A, the adversarial attack on a GCN-based model M can be formulated as a bi-level optimization problem 3 9):
argmin Lunuek Canue (. S.L. e argmin (cc)(M(A',
A'EPY
where pg denotes the possible perturbations within budget A. is the ground-truth label. Lanack and LOON denote the loss of adversarial attack and model M, respectively. M(A', Xx;""))) refers to the prediction of model M on the poisoned graph G', where the weights O" keep trained optimal.
3

---

We denote T as the set of target nodes aimed by the attacker. We consider the following two types of attacks: 1) Targeted attacks. The attacker aims to destroy prediction for specific node by manipulating the adjacent edges of u [70] 55 9, and T = {u} in this situation. 2) Non-targeted attacks. The attacker aims to degrade the overall classification performance but does not care about which node is being targeted [71 60]. Under this setting. T = Viste where Viest is the full test set.
4 Methodology
4.1 Problem Formulation
In a poisoning attack, the training data from 9 is perturbed before fed into a GCN model M, so that the performance of M can be degraded. Therefore, formulate the defense problem
Problem 1. Given perturbed graph G' generated by a poisoning attacker, the aim of defense target set T is to produce a more robust model M to optimize:
min 9
Σ WET
MM,
where (A',', xx V., refers the prediction of node when M is trained the poisoned graph G' with optimal 0"". M,, Yy is a hypothetical prediction that M would make if the clean graph G is accessible.
In Eq. we aim to force V to approximate U.. then the prediction D. in the benign situation can be recovered. However, the clean graph G is almost impossible to be accessed under the setting of adversarial attacks, which implies that we can not obtain M' by directly optimizing Eq. (2). To tackle this problem, we begin with investigating the potential impacts of structural attacks by examining the variability between A and A'.
4.2 Spectral View of Structural Attacks
Following [4 15
we observe the eigenvalues of Å after structural attacks as shown in Figure
Observation 1. Under structural attacks, the high-valued eigenvalues (low-frequency components) of Á likely be more robust than the low-valued eigenvalues (high-frequency components).
With this empirical inspiration, GCN-SVD [4] directly preprocesses the poisoned graph and retains the top low- urefureyy components for defense. However, argue that this justification is inaccurate. The relationship between robustness and graph spectrum is more complex than empirical observation. In the following, we provide in-depth analysis of structural perturbations from the spectral domain.
4.2.1 One-edge Perturbation
We first consider the targeted attacks with one-edge perturbation, where T = {u} and A 1. Note that under one-edge perturbation, i.e., we conduct a single edge flip euv on A, AA is a matrix with only 2 non-zero elements, namely A A the eigenvector matrix satisfies the following assumption:
2A Following (38], we assume that
Assumption 1. U has an orthonormal basis (u,)ye[N] that consists of non-negative vectors, where N is the number of nodes in the graph.
Then, we introduce the Lemma I to describe the differences of eigenvalues after structural attacks.
Lemma 1. Given graph (V, E, X) and edge euv to be perturbed, the change of y-th eigenvalue after perturbation is formulated as
(2ugn: Uyyo A (u ugre)
ifEu {Eur) if {ewv),
Ady
1-2 Uye + Xy (1 + uzy
where Uyn refers the u-th element of eigenvector Ug.
The proof is available in the Appendix. With the help of Lemma between robustness GCNs and the change on each eigenvalue A resulting from perturbations. Intuitively, smaller changes cigenvalues indicate stronger robustness of GCNs against attacks.
we can establish the relationship

---

Theorem (Low-frequency), Assume that u + uav # 0, u/u + u/ # 0, and
(Nau + Uav) (2ob Ubbu?
(3)
Then, there exists pair of high-frequency Xa E [-1,0) and low-frequency As E (0, 11, so that |Adal | always holds if Xa and db salisfy
max (0, do da Cu cada Ao
-1 < Aa < min da co + do
<
0).
(4)
Co
Go
where = =aa.. ua
am da 2uau Uae C6 uiu + uhe and dg = 22bbu Ubr-
The proof of Theorem Dis available in the Appendix. From Theorem [ we summarize two remarks.
Remark 1. The top low-frequency components (i.e., components selected from the values closer to 1) could be more robust than the top high-frequency ones (i.e., components are selected from the values closer -1) against one-edge perturbation under the condition from Inequality 3 which is consistent with Observation However, it is still vulnerable to such attacks that perturb the edges satisfying (ua.. + uav) < (Uh. ).o)². This contrary to the justification from GCN-SVD 14 and implies that not all low- www-freueeney components are robust.
[
Remark 2. We do not consider two special situations that u au u 0 or uh u because they conclude that AA, = 0 or Ad, O, respectively. This implies no perturbation happens on Aa or Ag which rare practice and out of discussion.
4.2.2 Robust Interval of Low-Frequency
As Remark from Theorem 1 Inequality 3 still makes the low- low-freuuncyy components of Å suffer from certain attacks. To further get rid of this condition, we derive new bound for low- low-frequency A by removing the dependency on A, in Inequality 3 here, which reveals the robust interval:
Theorem (Robust interval). Assume that ua.. + uu. * O and u + ube + O. There exists
low-frequency Ab, so that AAal |Ads always holds for any -1 Aa < 0 if do satisfies
max (0, dp - du + Codo
dg - do - cada 1).
An < min
Cb
Cb
The proof is available in the Appendix. Theorem 2 indiccates the interval of λ that is able for defense, which we denote as the robust interval of As In other words, when the low-frequencies fall into the robust interval, they are always more robust than the high-frequencies under one-edge perturbation.
4.2.3 Non-Targeted Perturbation
In this part, we consider a more complex and practical setting, the multi-edge non-targeted pertur- bation, where T Viest and A > 1. The perturbation P on each node u E T can be treated as multi-edge targeted attack. Note that the multi-edge targeted perturbation is a special case when discuss the type of attacks that either consecutively inserting deleting
T= [u]. Specifically, edges on the clean graph, since every state after perturbations can be decomposed into consecutively inserting then removing edges. In this situation, the attacker directly manipulates the adjacent edges we obtain the following results:
of u. Based on Theorem [.
Corollary (Low- -ow-frequency). We decompose non-targeted attacks two steps: 1) selecting target u from T, and 2) conducting perturbations on u. as multi-ede targeted attack. Assume adversarial edges are either consecutively inserted deleted node u as set P.,, i.e. E UU,, E P... With the same assumptions as in Theorem I there exists pair of high-frequency Na and low-frequency A so that 1CETL EvEp, Adaavl
11EEET EvEp. AAbuvl always holds if Xa and As satisfy
max (0. dino daun + CaundAa VEP.,UET
daws
Cbuu + doav 0)
< Ab < 1<
min oc uEPu.ETT
Cbuv
Cane
where Caue = 222. + u2.. daur 20gu"
Cbuv u + u and dour 2u Ube-
Then can have the robust interval under non-targeted perturbations with the help of Corollary I
as:
Corollary (Robust interval). With same assumptions as in Theorem 2 ENET EvEp, AAau -1 < Na < 0 if X satishes
IENET EvEp, ANbu always holds for any
(0, drav daur + Cauv
doue + daue Couvd
max VEP,, PEP,,
< A min
Cbas
PEP,.EET
Chuo
5

---

(1), The proofs for Corollary [ and Corollary can be found in the Appendix.
Remark 3. Under non-targeted perturbation, could come the same remarks as Theorem 1 when consecutively inserting or deleting edges from the clean graph. The mixed situation will be left as a future work. Due to space constraints, please refer to Corollary and Corollary 4 in the Appendix for details upon multi-edge targeted attack.
To summarize, we provide the theoretical justifications about the robustness of low-frequence components under the structural attacks in this section. These results imply that we can enhance the robustness of GCNs by utilizing the robust interval of low frequencies in A' of the poisoned graph.
4.3 GCN-LFR: General Robust Training Paradigm
Inspired by the theoretical findings in Section 1.2. it is natural to migrate the information from low-frequency components within robust interval enhance the robustness of model M. In this vein, we present GCN-LFR (Low-Frequency based Regularization) which introduces an auxiliary network MLFR to extract the low-frequency information within robust interval to regularize @ during the training procedure via parameter sharing 17 Figure 2 depicts the whole framework of GCN-LFR.
4.3.1 Auxiliary Regularization Net ML.RR
The effectiveness of the parameter sharing based regularization demon- strated by co-training an auxiliary neu- ral network on various of Deep Neu- ral Networks 22 [22. In GCN-LFR, we propose our auxiliary regulariza- MirR(A', (A', X; Q) by explic- itly designing the graph convolutional filter from { with the robust low- frequency components. However, ex- plicitly computing the robustness in- terval is infeasible before the struc- tural attack. To alleviate this chicken or the egg style causality dilemma, we employ a set of Icarnable parameters F as filters to learn the robust inter- val for the low-frequency components during training.
M MaCN GCN-based Model
CcN
LECN
Ispat Graph
tion net MLIR
Purameter Sharing
1:70
C F.FR
Lan Fngeeees
M LFR Auxiliary Regularization Not
Alternative Training
Figure 2: Overview of GCN-LFR. For any given GCN-based model M, we enhance its robustness by co-training an auxil- iary net MLFR that utilizes only the low-frequency compo- nents as regularization.
Overall, the layer-wind wise update rule for MI.FR (A' X; is:
feature transformation :H' (1) H graph convolution (H oU FU H
where U are the top-k low-frequenc eigenvectors from poisoned graph G', and the parameters + will be co-trained and shared to the original GCN model MMex(A', X; @). F diag(f.
fie
is diagonal matrix with k parameters as the graph filter, which can be learned in an end-to-end manner. Aside from the flexibility of learned F falling into the robust interval, can also enlarge the capacity of MLFR by making the learned embeddings H generalize into the subspace span by Uh..-
4.3.2 Co-Training Framework
Consider learning task graph G, and given GCN-based model MGGN (McN(A', X: 2) parametrized by O and poisoned by A' is utilized to deal with this task. We denote the loss function of MacN as LOON = L[MGCN (A', X; ,), y). Instead of minimizing LOCN alone, we propose co-train it with the same supervised loss on an auxiliary regularization net LLFR = [(MLFR A', X; θ F), y). In this way, we are able to compel the original model to learn more reliable representation from the robust low- frequecyy components:
Lusal (1 L + aLLIR,
(5)
where E (0, 1] is the weight coefficient for balancing the contribution of two losses. The transfor- mation of the robust information from lww-rrqqeecyy components is achieved by regularizing the training of LOeN with the shared parameters O.

---

Instead of jointed optimizing LOeN and LLFR, we exploit the idea of alternative training [22 to optimize the two losses. Specifically, each epoch, we randomly choose one of the two losses in GCN-LFR to optimize with probability determined by To put it another way, we sample random value = (0, 1), and a acts as threshold that decides which loss would be optimized at each epoch. The thorough description of algorithm is depicted in the Appendix.
As compared to joint training, this alternative training scheme can reduce the computational cost and accelerate the training process, Furthermore, in practice, we observe that the generalization ability of model is also improved according to the alternative training strategy.
For the inference procedure, we only transfer the robustness of www-frquency components by cotraining MLFR and sharing its parameters during training procedure. Then only use the prediction of the given model MaCN for inference. In other words, the extra complexity of our proposed method only from the training procedure, while the inference procedure stays the same, which further reflects the scalability of our proposed approach.
4.3.3 Complexity Analysis
We discuss the complexity of GCN-LFR here by the light example of VanillaGCN as backbone, For an imput graph with N nodes, E' edges, and M feature dimension cach node, the complexity of a solo VanillaGCN is OEE + N 2 [5]. time complexity of caleulating the top-k eigen-pairs is O(ckN), where is the average number of non-zero entries in a row of Á. Thus the overall complexity In our experiments, we choose to tune the hyperparameter k = d%NN as the
Then, with the help of Lanczos algorithm [28], the
GCN-LFR on VanillaGCN is
O + (NM2 proportion of low-frequency from grid search, in order to make GCN-LFR more adaptive different graphs. In this case, the overall complexity would be O NM + c)²)). In nutshell, the extra complexity introduced by GCN-LFR during co-training not a burden, especially when the graph is sparse, as it is in most real-world applications.
5 Experiments
5.1 Experimental Setup
Datasets. We mainly focus five node classification benchmark datasets under the semi-supervised setting: 1) three citation networks, Cora (37,, Citeseer and Pubmed [3], 2) coauthor network Coauthor CS 24, and 3) a co-purchase network Amazon Photo (36). More details, including dataset description and statistical information, are deferred to the Appendix.
Adversarial samples generation. We evaluate our model under three kinds of adversarial attack settings from the existing studies: targeted attack with one-edge perturbation (Nettack-One (70), targeted attack with multi-edge perturbation (Nettack-Mull [70). and non-targeted attack (Met-
tack 71 Details upon the three adversarial attack settings can be found in the Appendix.
Target GCN-based models. We apply GCN-LFR to five GCN-basd models to extensively evaluate its defense performance under three attack settings. The five models are: VanillaGCN (27). JK-Net (61)
SGC (54), Graph-U-Net [66,, and GCNII [T].
Defense baselines. We compare GCN-LFR with four SOTA general graph defenders with their available public implementations. GCN-Jaccard [53] and GCN-SVD [14] are two preprocessing based defending methods. GNNGUARD [63] and Pro-GNN 25 are two spatial-based approaches.
Details upon hyperparameters and architectures can be referred to in the Appendix.
5.2 Defense Results Against Targeted and Non-Targeted Attacks
Targeted attack with one-edge perturbation. We first examine the robustness of GCN-LFR against targeted one-edge perturbation under Nettack-One and report the results in Table The column "Attacked" shows the performance without any defense. From this column, we can find that Nettack- One can successfully damage the performance of various models even with only single edge flip. However, GCN-LFR can dramatically defend given GCNs against Nettack- One and consistently outperforms state-of-the tate-offthhe-rt basclines. Remarkably, we observe that the low-rank preprocessing
7

---

Table Defense performance (multi-class classification accuracy) against one-edge targeted attacks under Nettack- One. Note: the accuracy is on clean graph since only the correctly classified nodes targeted.
Model
Dataset
Attacked
GCN-Jaccard
GCN-SVD GNNGUARD
GCN-LFR
Cora
0.675
0.700
0.775
0.800
Citeseer
0,425
0.625
0.825
0.725
0.775
VanillaGCN
27
Pubmed
0,450
0,550
0.600
0.775
0.825
Coauthor CS
0.650
0.675
0.725
0.825
0,875
Amazon Photo
0,500
0.525
0.625
0.650
0.750
Cora
0.350
0.575
0.675
0.775
0.825
Citeseer
0,450
0.650
0.550
0.750
0.800
JK-Net 6
Puhmed
0.350
0.375
0.625
0.800
0.850
Coauthor CS
0.600
0.625
0.675
0.725
0.775
Amazon Photo
0.550
0.575
0.675
0.675
0,800
Cora
0.425
0.675
0.550
0.750
0.825
Citeseer
0.475
0.600
0.650
0.725
0.750
SGC S4
Pubmed
0.300
0.475
0.650
0.750
0.800
Coauthor CS
0.600
0.650
0.725
0.750
0.775
Amazon Photo
0.550
0.575
0.600
0.675
0.725
Cora
0.375
0.525
0.650
0.725
0.800
Citeseer
0.275
0.350
0.575
0.750
0.775
Graph-U-Net 16
Pubmed
0.475
0,550
0.675
0.700
0.750
Coauthor CS
0.625
0.600
0.700
0,850
Amazon Photo
0,500
0.525
0.650
0.725
0,825
Cora
0.475
0.650
0.575
0.825
0.875
Citeseer
0.550
0.600
0.625
0.725
0.750
GCNII 10
Pubmed
0.400
0.475
0.675
0.750
0.775
Coauthor CS
0.650
0.700
0,800
0.825
Amazon Photo
0.650
0.425
0.600
0.675
0.775
approach GCN-SVD is not very effective, which implies that not all low- cow-frequency components are robust, and strategy by transferring robust knowledge with learnable F is beneficial.
Table 2: Defense performance (multi-class classification accuracy) against multi-edge targeted attacks under Nettack-Mun Note: the accuracy on clean graph since only the correctly classified nodes are targeted.
Model
Dataset
Attacked
GCN-Jaccard
GCN-SVD
GNNGUARD
GCN-LFR
Cora
0.160
0.540
0.585
0.695
0.700
Citeseer
0.170
0.370
0.590
0.710
0.655
GCNII 10
Pubmed
0.080
0.275
0.430
0.605
0.650
Coauthor CS
0.060
0.350
0.525
0.730
0.775
Amazon Photo
0.120
0.440
0.620
0.715
0.720
Table 3: Defense performance (multi-class classification accuracy) against non-targeted attacks under
Mettack.
Model
Dutaset
Attacked
GCN-Jaccard
GCN-SVD
GNNGUARD
Pro-GNN
GCN-LFR
Cora
0.701
0.760
0.717
0.764
0.773
0.777
Citeseer
0.657
0.680
0.664
0.687
0.693
0.690
VanillaGCN
Pubmed
0.807
0.845
0.823
0.848
0.852
0.855
Coauthor CS
0.836
0.865
0.852
0,868
0.875
Amazon Photo
0.854
0.877
0.862
0.882
0.887
Targeted attack with multi-edge perturbation. Next, we evaluate the defending performance of targeted attacks with multi-edge perturbation. We report the defending performance the newest variant, GCNII, in Table 2 is not surprising that GCNII suffers more serious performance degradation under Nettack-Mull than that of Nettack-One. However, GCN-LFR remains the best defender among all baselines even when the amount of perturbed edges increases. We also observe that GCN-LFR achieves better defense under one-edge perturbation than multi-edge. We suppose this due to the wider robust interval Theorem since the bounds are tighter when iterating over all candidate edges in Corollary 4
Non-targeted attack. validate the defending performance of GCN-LFR against non-targeted attacks, we utilize Mettack to conduct adversarial edges globally. We also include the comparison

---

with an additional baseline Pro-GNN under this setting on small datasets since Pro-GNN is extremely cone-consuming on large datasets. Table demonstratss the results on VanillaGCN for all datasets. In Table 3 baselines.
we can observe that the defending performance of GCN-LFR is also comparable with all
Table 4: Classification accuracy on benign (i.e., non-attacked) datasets with and without GCN-LFR.
Bengin dataset
Cora w/o
Citeseer
Pubmed
Coauthor CS
Amazon Photo
or w/o LFR
w/o
VanillaGCN JK-Net
0.815
0.818
0.721
0.701
0.863
0.858
0,907
0.911
0,921
0.925
0.820
0.827
0.705
0.693
0.854
0.836
0.927
0.891
0.929
0.896
SGC
0.825
0.819
0.719
0.701
0.859
0.861
0.928
0.897
0.929
0.927
Graph-U-Net U-Net
0.825
0.838
0.697
0.688
0.835
0.842
0.926
0.907
0.925
0,918
GCNII
0.812
0.813
0.695
0.698
0.864
0.838
0.931
0.904
0.934
0.927
5.3 Ablation Studies
Performance of GCN-LFR on clean datasets. Aside from the defense against adversarial attacks, a successful defender needs not to affect the performance on clean datasets. Table [ shows the performance comparison of five GCN models with and without regularization net MLLF on five benign (i.e., non-attacked) datasets. As shown in Table GCN-LFR achieves a quite competitive classification accuracy and even better in some cases. This indicates that GCN-LFR does not harm the performance of GCNs when no attack happens while successfully dealing with the poisoned graphs. We also conduct T-test on the classification accuracy over all benign datasets w or w/o LFR. which can be found in the Appendix.
In-depth analysis on MLPRR net. To justify the necessity of cach component of GCN-LFR, we implement several variants of GCN-LFR with VanillaGCN and evaluate the performance on the benign Cora dataset. Figure 3 shows the comparison among GCN-LFR and other variants on the training and validation accuracy. GCN and LFR represent training with only VanillaGCN and MLIR net, respectively. GCN-LFR is a variant of GCN-LFR that replaces the learnable filter F with the truncated eigenvalues N/w We have the following observations: 1) LFR net achieves lower training accuracy and suffers from severe underfitting issue. It indicates that training with only low-frequency components would lose information despite their robustness. 2) GCN-LFR achieves competitive performance against GCN. It re-confirms the results in Section 5.3 that GCN-LFR does not harm performance in the absence of attack. 3) GCN-LFR achieves substantially better validation accuracy than that of GCN-LFRrk It implies that the trainable graph filter F is more flexible and can aid the generalization of learned embeddings in the subspace spanned by UY...
Aside from Figure 3 we further provide the comparison among VanillaGCN, GCN-LFReix and GCN- LFR under both benign and non- tor-ttegeeed attack settings here for better and sufficient demonstration in Table 5 It shows that GCN-LFR has both better performance and robustness over VanillaGCN and GCN-LF Fix- Interestingly, the better generalization ability of GCN-LFR over GCN-LFRei could be observed implicitly either in this way.
FFix-
Table 5: Classification accuracy comparison among VanillaGCN, GCN-LFRFix and GCN-LFR on both benign and non-targeted attacked datasets,
Datasct Meibods
Cora
Citeseer
Pubmed
Coauthor CS
Amazon Photo
Henign
Attacked
Benign
Attacked
Henign
Attacked
Benign
Attacked
Benign
Attacked
VanillaGCN
0.830
0.771
0.720
0.654
0.860
0.794
0.902
0.816
0.929
0.824
GCN-LFREi
0.779
0.726
0.683
0.634
0.832
0.786
0.883
0.808
0.876
0.793
GCN-LFR
0.824
0.791
0.706
0.670
0.856
0.802
0.912
0.837
0.928
0.943
Joint optimization vs. alternate optimization on GCN-LFR. We investigate the benefits of alternate optimization of GCN-LFR (i.e., GCN-LFRAlee). We denote the joint optimization of GCN-LFR as GCN-LFR Figure A provides the results of comparison. The left-side of Figure demonstrates the training and validation accuracy on Pubmed dataset. VanillaGCN is used as backbone here. We can observe that GCN-LFRAle achieves better training and validation performance compared with GCN-LFR, Furthermore, the right-side of Figure 4 4ssows the acceleration ratio of GCN-LFR over GCN-LFR terms of training time on five datasets. Acceleration ratio denotes the quotient obtained by dividing the time-consumed of GCN-LFR by that of GCN-LFRAICe F
We can find

---

Trainis Accuraty 5 5 R
Valichaiion Ancurayy
23
GOV COXAPE Fi
Accleraie Matio
CON CCN-LFRe
+1.6
LFR
COONN CCSS-LPPP
GKN
CON-LPR
Epoch
Epoch
Egoch
60
(500 Crufber CS
Figure 3: The training and validation accuracy comparison among GCN-LFR, two components of GCN-LFR, ie., VanillaGCN and LFR, and variant of GCN-LFR, namely GCN-LFRFix
Figure 4: Left: the training and validation loss comparison between GCN-LFRAttr on Pubmed with backbone VanillaGCN. Right: the acceler- ation ratio of GCN-LFRAIE over GCN-LFR
that GCN-LFRAter is more efficient by achieving an average of x1.74 times acceleration, since GCN-LFRAlter only needs to optimize model while GCN-LFRJeint needs to handle two models at each epoch. It verifies that GCN-LFR enjoys both effectiveness and efficiency.
Aside from Figure 4 we also provide the train/validation/test accuracy comparison between GCN- Joitt and GCN-LFRAtis over all datasets in Table for clearer demonstration. The consistent conclusion above can be drawn from T
Table 6: Train/validation/test accuracy comparison between GCN-LFR and GCN-LFRAteer
Dataset
Cora
Citeseer
Pubmed
Coauthor CS
Amazon Photo
Joint-Train
0.999 + 0.001
0.991
0.004
0.929 + 0.002
0.986 + 0.004
0.975 + 0.007
Alter-Train
0.999 + 0.001
0.995
0.002
0.932 + 0.013
0.977 + 0.006
0.986 + 0.005
Joint-Val
0.827 + 0.018
0.702
0.027
0.832 + 0.006
0.903 + 0.008
0.939 +\2 0.004
Alter-Val
0.837 + 0.025
0.717 + 0.008
0.843 + 0.008
0.907 + 0.007
0.942 + 0.009
Joint-Test
0.817 + 0.011
0.698
0.007
0.846 0.005
0.908 + 0.003
0.917 + 0.001
Alter-Test
0.833 = 0.009
0.701 0.011
0.853 + 0.010
0.912 + 0.008
0.931 + 0.015
Eigenvalues vs. learned F in the robust interval. To evaluate whether the proposed theoretical analysis is reliable, we check how many Ås and the trained F fall into the robust interval on all datasets here. We report the results of top 25% smallest of eigenvalues as As on the same 40 target nodes after one-edge perturbation in Fi We can find that, though by choosing a considerably larger proportion as low- low-frequency, we still have an average of around 40% of A falling into the robust interval. Further, the learnable F has more values falling into the robust interval also
P ieccomnne (50)
Cish Creat poreet Conter CS
after training, which is consistent with our observation in Figure verifies that F could potentially learn the frequencies within the robust interval for oww-frequnccy components and lead to a more robust model.
Figure 5: Numerical check on the robust inter- val for all datasets.
6 Conclusion and Limitations
In pursuit of developing defending methods for the adversarial attacks on GCNs, we present the first vulnerability study between the graph spectrum and the robustness behaviour of GCNs, which indicates that the low-frequency components in graphs could be more robust than the high-frequency ones under certain conditions. Moreover, we further verify robust interval of the low-frequency components, which implies that not all low-frequency components are robust unless they fall within the robust interval. Guided by this theory, we propose a general robust training paradigm, dubbed GCN-LFR, that suggests training parameter sharing to transfer the robustness of low- wow-frequency components. Extensive experimental verifications demonstrate the resistance of GCN-LFR when being exposed to adversarial attacks.
auxiliary network jointly with the original model through
Currently, we only consider the purification in the context of structural perturbations. Given that adversarial perturbations will occur at the level of features and nodes, we would like to expand the proposed architecture the future to protect against various forms of adversarial attacks. Meanwhile, we make every effort to include a thorough experimental study. Further results on possible datasets and baselines will be added as a future work, including the extension to large scale datasets such as OGB (21) Societal impacts are discussed in the Appendix.
10

---

Acknowledgments and Disclosure of Funding
Funding in direct support of this work: National Key Research and Development Program of China No. 2020AAA0107801,, and National Natural Science Foundation of China (No. 62050110 No. 62102222).
References
[1] Bian, T., Xiao, X., Xu, T., Zhao, P., Huang, W., Rong, Y., and Huang. J. (2020), Rumor detection on social media with bi-directional graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 456-
[2] Blum, A. and Mitchell, T. (1998). Combining labeled and unlabeled data with co-training. In Proceedings of the eleventh anmual conference on Computational learning theory, pages 92-100.
[3] Bojchevski, A. Günnemann, S. (2019a). Adversarial attacks on node embeddingg via graph poisoning. In Proceedings of the 36th International Conference on Machine Learning, ICML, Proceedings of Machine Learning Research. PMLR.
[4] Bojchevski, A. and Günnemann, S. (2019b). Adversarial attacks on node embeddings via graph poisoning. In Proceedings of the 36th International Conference on Machine Learning, ICML, Proceedings of Machine Learning Research. PMLR.
[5] Bojchevski, A. and Günnemann, S. (2019c). Certifiable rohustness to graph perturbations. In Neural Information Processing Systems, NeurlPS.
[6] Boscaini, D., Masci, J., Melzi, S., Bronstein, M. M., Castellani, U., and Vandergheynst, P. (2015). Learning class-specific descriptors for deformable shapes using localized spectral convolutional networks. In Computer Graphics Forum, volume 34, pages 13-23. Wiley Online Library.
[7] Bruna, J., Zaremba, W., Szlam, A., and Lecun, Y. (2014). Spectral networks and locally connected networks graphs. In International Conference Learning Representations (ICLR2014), CBLS, April 2014, pages http- openreview.
[8] Chang, H., Rong, Y., Xu, T., Huang, W., Sojoudi, S., Huang. J., and Zhu, W. (2020a). Spectral graph attention network with fast iigen-approximation. arXiv preprint arXiv:2003.07453
[9] Chang, H., Rong, Y., Xu, T., Huang, W., Zhang, H., Cui, P., Zhu, W., and Huang. J. (2020b). A restricted black-box adversarial framework towards attacking graph embedding models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3389-3396
[10] Chen, M., Wei, Z.,, Huang, Z., Ding, B., and Li, Y. (2020). Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725 1735. PMLR.
[11] Dai, H., Li, H., Tian, T., Huang, X., Wang, L.., Zhu, J., and Song, L. (2018). Adversarial attack graph structured data, international conference machine learning, pages 1115-1124.
[12] Dasoulas, G., Lutzeyer, J. F., and Vazirgiannis. M. (2021). Learning parametrised graph shift operators. In International Conference Learning Representations (ICTR).
[13] Defferrard, M., Bresson, X., and Vandergheynst, P. (2016). Convolutional neural networks on graphs with fast localized spectral filtering, neural information processing systems, pages 3844-3852.
[14] Entezari, N., Al-Sayouri. S. A., Darvishzadeh, A.. and Papalexakis, E. E. (2020). All you need is low (rank) defending against adversarial attacks graphs. In Proceedings the 13th International Conference Web Search and Data Mining, pages 169-177.
[15] Gama, F., Bruna, J., and Ribeiro, A. (2020). Stability properties of graph neural networks. IEFE Transactions on Signal Processing, 68:5680-5695.
[16] Gao, H. and Ji, S. (2019). Graph u-nets. In International Conference on Machine Learning, pages 2083-2092.
[17] Goodfellow, I., Bengio. Y., Courville, A., and Bengio, Y. (2016). Deep learning, volume 1. MIT press Cambridge.
[18] Gu, F. Chang. H., Zhu, W. Sojoudi, S., and El Ghaoui, L. (2020). Implicit graph neural networks. Advances in Neural Information Processing Systems, 33:1 1e211194--111 11995.

---

[19] Guan, C.. Zhang, Z., Li, H. Chang, H., Zhang, Z.. Qin. Y., Jian, J. Wang, X., and Zhu, W. (2021). Autogl: A library for automated graph learning. arXiv preprint arXiv:210..09987.
[20] Hom, R. A. and Johnson, C. R. (2012). Matrix analysis. Cambridge university press.
[21] Hu, W., Fey, M., Zitnik, M., Dong. Y., Ren, H., Liu, B., Catasta, M., and Leskovee, J. (2020). Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005. 00687.
[22] Huang, W., Zhang, T., Rong, Y., and Huang, J. (2018). Adaptive sampling towards fast graph representation learning. In Advances in Neural Information Processing Systems, pages 4563-4572.
[23] Jin, M., Chang. H., Zhu, W., and Sojoudi, S. (2021). Power up! robust graph convolutional network via graph powering. In 35th AAAI Conference on Artificial Intelligence.
(24] Jin, W., Li, Xu, H.. Wang. Y., and Tang, (2020a). Adversarial attacks and defenses on graphs: review and empirical study, arXiv preprint Wxxi:2003.00653
[25] Jin, W., Ma, Y., Liu, X., Tang, X., Wang, S., and Tang. J. (2020b). Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 66-74.
[26] Kingma, D. P. and Ba, J. (2014). Adam: method for stochastic optimization. arXiv:1412.6988
arXiv preprint
[27] Kipf, T. N. and Welling, M. (2017). Sumi-super classification with graph convolutional networks. international conference on learning representations.
[28] Lanezos, C. (1950). An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. United States Govermm. Press Office Los Angeles, CA.
[29] Levie, R., Huang, W., Bucei, L.., Bronstein, M. M., and Kutyniok, G. (2019). Transferability of spectral graph convolutional neural networks. arXiv preprint arXiv: 1297.
[30] Li, H., Cui, P., Zang, C.,, Zhang, T., Zhu, W., and Lin, Y. (2019). Fates of microscopic social ecosystems: Keep alive or dead? In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 668 676.
[31] Li, H., Wang, X., Zhang, Z., Ma, Cui, and Zhu, W. (2021). Intention-aware sequential recommenda- tion with structured intent transition. IEEE Transactions on Knowledge and Data Engineering.
[32] Li, J., Zhang, H., Han, Z.,, Rong, Y., Cheng, H., and Huang, (2020a). Adversarial attack on community detection by hiding individuals. In Proceedings of The Web Conference 2020, pages 917-927.
[33] Li, M., Ma, Z., Wang. Y. G., and Zhuang, X. (2020b). Fast haar transforms for graph neural networks. Neural Networks, 128:188-198.
[34] Li. Y.. Jin, W., Xu, H. and Tang, J. (2020c). Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint arXi:22005.06144
[35] Machara, T. (2019). Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint 905.5:9905.09550.
[36] McAuley, J., Targett, C., Shi, Q., and Van Den Hengel, A. (2015). Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 43-52.
[37] McCallum, A. K., Nigam, K., Rennie, J., and Seymore, K. (2000). Automating the construction of interne portals with machine learning. Information Retrieval, 312
[38] Oono, K. and Suzuki, T. (2020). Graph neural networks exponentially lose expressive power for node classification. In International Conference Learning Representations.
[39] Ortega, A., Frossard, P., Kovačević, J., Moura, M., and Vandergheynst, P. (2018). Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808-828.
[40] Pei. H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. (2020), Geom-gen: Geometric graph convolutional networks. arXiv preprint 2rXiv:2002.05287
[41] Qin, Y., Wang, X., Cui, P., and Zhu, W. (2021). Gqnas: Graph network for neural architecture search. In 21st IEEE International Conference on Data Mining.
12

---

[42] Rong. Y., Bian, Y., Xu. T., Xie, W., WEI, Y.. Huang, W., and Huang, J. (2020). Self-supervised graph transformer large-scale molecular data. In Larochelle, H.. Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H., editors, Advances in Neural Information Processing Systems, volume 33, pages 12559-12571, Curran Associates, Inc.
[43] Sen, P., Namata, G. M., Bilgic, M., Getoor, I.., Gallagher, B., and Fliassi-Rad, T. (2008), Collective classification in network data. Ai Magazine, 29(3):33-106.
[44] Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. (2018). Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 181.1088888.8
[45] Shuman, D. L. Narang. S. K., Frossard, P., Ortega, A.. and Vandergheynst. P. (2013). The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Processing Magazine, 30(3):83-98.
[46] Stewart, G. W. and Sun, J.-g- (1990). Matrix perturbation theory.
[47] Sun, L.. Wang, J.. Yu, S., and Li, B. (2018). Adversarial attack and defense on graph data: A survey. arXiv preprint arXiv:1812.1052.
[48] Sun, Y., Wang. S., Tang, X., Hsich, T.-Y,, and Honavar, V. (2020). con-target-speeific node injection attacks on graph neural networks: A hierarchical reinforcement learning approach. In Proc. WWW, volume 3.
[49] Tang, X., Li, Y. Sun, Y., Yao, H., Mitra, P., and Wang. S. (2020). Transferring robustness for graph neural network against poisoning attacks. In Proceedings of the 13th International Conference on Web Search and Data Mining, pages 600-608.
[50] Tong, H., Prakash, B. A., Eliassi-Rat T., Faloutsos, M., and Faloutsos, C. (2012). Gelling, and melting, large graphs by edge manipulation. In Proceedings of the s1 ACM international conference Information and knowledge management, pages 245-254.
[51] Tramer, F., Carlini, N., Brendel, W., and Madry, A. (2020). On adaptive attacks to adversarial example defenses. arXiv preprint arXiv:2002.08344
[52] Verma, V., Qu, M., Kawaguchi. K.. Lamb, A., Bengio, Y., Kannala, J., and Tang. (2019). Graphmix: Improved training of gnns for semi- superviiee learning. arXiv e-prints, pages 1909.
[53] Wang, Y., Liu, S., Yoon, M., Lamba, H., Wang, W., Faloutsos, C., and Hooi, B. (2020). Provably robust node classification via low-pass message passing. In 2020 IEEE International Conference on Data Mining (ICDM), pages 621-630. IEEE.
[54] Wu, F., Zhang, T., Souza Jr., A. H., Fifty, C., Yu, T., and Weinberger, K. Q. (2019a). Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning (ICML).
[55] Wu, H., Wang, C. Tyshetskiy, Y., Docherty, A., Lu, K., and Zhu, L. (2019b). Adversarial examples for graph data: Deep insights into attack and defense. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 481 4816-4823. AAAI Press.
[56] Wu, T. Ren, H., Li. P., and Leskovec, J. (2020a). Graph information bottleneck. Advances in Neural Information Processing Systems, 33.
[57] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y. (2020b). A comprchensive survey on graph neural networks. IEEE transactions on neural networks and learning systems.
[58] Wu, Z., Pan, S., Chen, F,, Long, G., Zhang, C.,, and Yu, P. S. (2019c). A comprehensive survey on graph neural networks. arXiv preprint arXiv: 190.0009..
[59] Xu, H., Ma, Y., Liu, H.-C., Deb, D., Liu, H., Tang, J.-L., and Jain, A. K. (2020a). Adversarial attacks and defenses in images, graphs and text: A review. Intermational Journal of Automation and Computing, 17(2):51-1778
[60] Xu, K., Chen, H., Liu, S., Chen, P.-Y,, Weng, T.-W., Hong, M., and Lin, X. (2019). Topology attack and defense for graph neural networks: an optimization perspective. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3961-3967. AAAI Press.
[61] Xu, K., Li, C., Tian, Y. Sonobe, T., ichi Kawarabayashi, K. and Jegelka. S. (2018). Representation learning on graphs with jumping knowledge networks. international conference on machine learning, pages 5449 5458.
13

---

[62] Xu. Q. Yang. Z., Jiang, Y.. Cao, X., Yao. Y., and Huang. Q. (2020b). Not all samples are trustworthy: Towards deep robust svp prediction. IEEE Transactions Puttern Analysis and Machine Intelligence.
[63] Zhang, X. and Zitnik, M. (2020). Ganguard: Defending graph neural networks against adversarial attacks. Advances in Neural Information Processing Systems, 33.
[64] Zhang, Z., Cui, P., and Zhu, W. (2020). Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Data Engineering.
[65] Zheng, X., Zhou, B., Gao, J., Wang, Y. G., Lio, P., Li, M., and Montúfar, G. (2021). How framelets enhance graph neural networks. arXiv preprint arXiv:2102.0663
[66] Zhu, D., Cui, P., Zhang, Z., Pei, J., and Zhu, W. (2018). High-order proximity preserved embedding for dynamic networks. IEEE Transactions on Knowledge and Data Engineering. 30:2134-2144,
[67] Zhu, D., Zhang, Z., Cui, P., and Zhu, W. (2019). Robust graph convolutional networks against adversarial attacks. In Proceedingy of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1399-1407.
[68] Zhu, J., Yan, Y., Zhao, I.., Heimann, M., Akoglu, I.., and Koutra, D. (2020). Beyond homophily in graph neural networks: Current limitations and effective designs. Advances Neural Information Processing Syxtems, 33.
[69] Zügner, and Günnemann, S. (2020). Certifiable robustness graph convolutional networks under structure perturbations. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1656-1665.
[70] Zügner, D., Akbarnejad, A., and Günnemann, S. (2018). Adversarial attacks on neural networks for graph data. In Proceedingy of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2847-2856.
[71] Zügner, D. and Günnemann, S. (2019). Adversarial attacks graph neural networks via meta learning. international conference learning representations.
14


Reviews:
[{"review_id": "O6VuNKJW2cG", "reviewer": "Reviewer_mqEy", "summary": "This work tries to study the robustness of GCNs under structural perturbations from the perspective of graph spectrum, which for me is interesting. In theory, they proved that the low-frequency components can be more robust against structural perturbations if their eigenvalues fall into a robust interval. For algorithm design, they developed a regularized learning framework that combines a regular GCN-based objective and a low-frequency regularization term, named GCN-LFR. Finally, the authors tested the capability of GCN-LFR in resisting adversarial attacks on several benchmark datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\nThe idea to bridge the gap between the spectral analysis and the robustness of GCNs under structural perturbations is interesting. \n\nWeakness:\n\n(1) The reason why alternative training is better than joint training is not clearly explained. I am curious about the influence of parameter sharing used for two channels (GCN and LFR). \n\n(2) It is not clear to me whether the enhanced robustness shown in experiments is caused by the model’s two-channel cooperation architecture or exactly the functionality of LFR. The threshold value to select the top-k low-frequency eigenvectors is of high importance. \n\n(3) How is the scalability of the proposed method? Although authors provided a complexity analysis of GCN-LFR, more empirical verifications on one/two large-scale graph datasets are required. My initial impression of LFR is that it may need a huge computation burden. \n\nMajor points: \n\n(1) In Figure 1, the authors concluded that “low-frequency components (far left) tend to be more robust in comparison with high-frequency ones (far right)”, which seems to be the case, intuitively. However, I do not feel confident about this conclusion since the ‘rate of change’ (over eigenvalues before & after perturbation), which can be more suitable and fair, is not clearly illustrated. \n\n(2) I am curious about one issue: Do the high-frequency components also play a role in affecting the robustness of GCNs? Some discussions or empirical studies could help readers better understand the key ingredients towards how to investigate GCN’s robustness analysis from a spectrum way.\n\n(3) More experimental verifications on large-scale graph benchmark datasets, for example, OGB, are required to further demonstrate the potential of the proposed method. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors mentioned the limitations in the conclusion and societal impacts in the Appendix.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "O0RaO02vjux", "reviewer": "Reviewer_CV31", "summary": "Graph convolutional networks are volunerable to adversarial attacks.  As commonly recognized by researchers,  low-frequency components of GCNs are more robust than high-frequency parts of GCNs. However, the relationship between graph spectrum and robustness of GCN is not well studied. This paper theoretically proposes the robust interval of low-frequency components and regularizes the low-frequency components of GCNS within the robust interval through an auxiliary neural network. In this way,  the robustness of a GCN is enhanced.", "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": "Originality:  this paper bridges the gap between the spectrum analysis and the robustness of GCNs under structural perturbations. The depth of this paper is satisfied. The authors not only studied one-edge perturbation but also considered the multi-edge non-targeted perturbation.\n\nQuality: the proposed method is technically sound. The experimental results support the proposed method. Its performance is evidently higher than baseline method. However, the chosen datasets are limited to homophily graph datasets. For these datasets, low-frequency components are more useful than high-frequency components. How well the proposed method suit for non-homophily datasets [*] should be further studied. \n[*] New Benchmarks for Learning on Non-Homophilous Graphs\n\nClarity: the connection between the proposed robust frequency interval and the proposed method is weak and not well clarified. The authors should clarify whether the parameters of F are constrained within the robust interval during training.\nBesides, the authors should clarify the inference procedure of the proposed framework.\n\nSignificance: this paper is a first vulnerability study between the graph spectrum and the robustness behavior of GCNs. It theoretically shows that not all low-pass filters are robust in graph convolutional networks. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "MDzAvwXafsA", "reviewer": "Reviewer_iiUG", "summary": "The authors introduce a method to improve the robustness of graph neural networks (GNNs). Specifically, the method performs robust training to defend against structure poisoning attacks. The algorithm learns low-pass filter coefficients $\\mathbf{F}$. A GCN which uses this low-pass filter as the graph convolution matrix shares weights with a standard GCN during training. The authors compare results on a set of established datasets and attacks.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n* The authors report strong robustness results across datasets and attacks.\n* The theoretical analysis is insightful.\n* The presentation of the paper is good and clear.\n\nWeaknesses:\n* The ablation study is weak and does not sufficiently support the claim that learning the filter weights $\\mathbf{F}$ is better than the model where the eigenvalues are used (more in detailed comments).\n* The complexity analysis is misleading, showing $O(ckN)$ where it is actually $O(cN^2)$ (more in detailed comments).  \n* The clean accuracy of the method is quite consistently lower than the original accuracy. \n\nDetailed comments:\n\n* Since the graph convolution matrix multiplication for M_LFR is no longer sparse, what effect does this have on the scalability of the method?\n* In the Appendix, the authors state that the number $k$ of low frequency components considered is $0.25 N$. With this, the complexity to compute the top-$k$ eigenpairs is $O(cN^2)$. This is a major scalability limitation and should be addressed in the main text. \n* Are predictions of the low frequency GCN used at inference time? If yes, this means that the method cannot be used in an inductive fashion on new nodes at inference time.\n* It seems like the method is also well suitable for evasion attacks. How does the method defend against these?\n* Figure 3 (right) does not support the claim that \"GCN-LFR achieves substantially better validation accuracy than that of GCN-LFRFix\". The scale is too coarse to see much difference and there is quite some fluctuation in the curves.\n* Figure 3 (right) also does not support the claim that \"GCN-LFR achieves competitive performance against GCN\", since it only shows the validation accuracy. Also, this is just a single run on one dataset.\n* How does GCN-LRF_fix compare to GCN-LRF in a proper tabular comparison on multiple datasets? This is crucial to determine the usefulness learning the filter over keeping it fixed, and Figure 3 does not answer this as stated above.\n* Similarly, Figure 4 (left) is not suited to draw general conclusions such as \"GCN-LFR_Alter achieves better training and validation performance compared with GCN-LFRJoint\". As above, please run a proper comparison on multiple splits and datasets.\n* The results in Table 1 for GNNGuard seem to be substantially weaker than reported in Table 1 of the original paper. For example, for Citeseer they report 72.0% robustness after attack and 72.1% clean accuracy. This would correspond to an accurracy of 99.86% in the scale reported by the authors. What is the reason for this? \n* Table 4 seems to suggest that GCN-LFR has lower accuracy on average. On how many splits are these results computed? What are the confidence intervals? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no broader impact statement in the main text of the paper. While the authors have put it into the appendix, this practice is not fair to other authors who sacrifice precious space in the main text of the paper to have the broader impact statement, as demanded by the NeurIPS guidelines.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers feel the paper is  on the borderline but leaning towards accept. The meta-reviewer read the paper and feel the insight obtained from this paper is interesting. Therefore, the meat-reviewer decides to be conformal with the rest reviewers and suggest an acceptance of this submission. 
Decision: Accept (Poster)