Not All Low-Pass Filters are Robust in Graph Convolutional Networks
Year: 2021

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 lowfrequency 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-LFR3, 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.

heading: 1 Introduction
text: Graph Convolutional Networks (GCNs) elaborate the expressive power of deep learning from grid-like data to graph-structured data and have achieved remarkable success in a wide variety of domains [7, 6, 13, 27, 22, 30, 1, 8, 42, 18, 31, 12, 41, 19]. 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 recently [70, 11, 9]. The lack of robustness arouses concerns on applying GCNs in a variety of fields pertaining to security and privacy. Adversarial attacks on graphs aim to degrade the ability of representation learning of GCNs, and fool them to make wrong decisions by perturbing either node features or 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 inserting/removing/rewiring 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 at Tencent AI Lab. †Corresponding authors. 3Code available at https://github.com/SwiftieH/LFR.
35th Conference on Neural Information Processing Systems (NeurIPS 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 is 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 influences 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 [14]. As the toy example shown in Figure 1, low-frequency 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 to be more stable than high-pass filters when we randomly add/remove edges. These observations point to a 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 paper, we aim to bridge the gap between the spectral analysis and the robustness of GCNs under structural perturbations. Specifically, for the symmetric normalized Laplacian, which is commonly chosen as the graph filter in GCNs, we prove that the low-frequency components could be more robust against both one-edge and multiedge perturbations when their eigenvalues fall into a robust interval. Interestingly, this result reveals that not all low-frequency components are robust to adversarial attacks.
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 a general defender that can work with any GCN-based 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 netMLFR , 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-art defenders across five benchmark datasets under a variety of settings, including one-edge targeted, multi-edge targeted, and nontargeted 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. It further reveals the broad applicability and relevance of GCN-LFR in the area of deep graph learning.

heading: 2 Related Work
text: Adversarial attacks on graphs. Adversarial attacks on graph neural networks have drawn unprecedented 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., Nettack [70]) that perturb the graph in the training stage and 2) evasion attacks (e.g., RL-S2V [11]) 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 [3], graph generation [32], graph signal processing [9] and reinforcement learning [11, 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] proposes to examine fake edges in the step of preprocessing by utilizing similarity metrics. RGCN [67],
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 in the relationship 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 [14] empirically verifies that only the high-rank singular components of the graph are affected by Nettack, and preprocesses 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-frequency components in the spectral domain. The proposed framework GCN-LFR is a general defender and can protect various GCN-based models from adversarial attacks.

heading: 3 Preliminaries
text: We consider an undirected attributed graph G = (V, E ,X), where |V| = N is the set of N nodes, E ⊆ V × V is the set of E edges, and X = {x1, ...,xN} is the associated feature matrix, in which xu ∈ RM is the M -dimensional node feature for node u ∈ V . We utilize Nu to denote the neighbors of node u. We denote the adjacency matrix as A ∈ RN×N , where Auv ∈ {0, 1} indicates whether an edge euv ∈ E exists. The node degree matrix is defined as D = diag(d1, · · · , dn), where du = ∑ vAuv represents the degree of node u. An adversarial attacker deliberately perturbs edges in G and results in the poisoned version of G, which we denote as G′ = (V ′, E ′,X), and A′ is the perturbed version of A. Let L = D−1/2(D −A)D−1/2 be the symmetric normalized graph Laplacian. L has eigenvalues ranging from 0 to 2. Â = D− 12AD− 12 = In −L is the symmetric normalized adjacency matrix, whose eigenvalues range from −1 to 1. Specifically, the low-frequency components refer to the ones of L with eigenvalues in [0, 1) (of Â with eigenvalues in (0, 1]), and the high-frequency ones refer to that of L with eigenvalues in (1, 2] (of Â with eigenvalues in [−1, 0)).

heading: 3.1 Graph Convolutional Networks
text: VanillaGCN can be viewed as the spectral convolution based on the Fourier transform on graphs with first-order Chebyshev polynomial filter g(L). The layer-wise update rule is given as:
feature transformation : H ′(l) = H(l)Θ, graph convolution :H(l+1) = σ(g(L)H ′(l)), (1)
where H(l+1) ∈ RN×q(l+1) is the output from hidden layer l with input as H(l) ∈ RN×q(l) . q(l) refers to the dimension of output at layer l. For the input layer, we have H(0) = X . σ(·) refers to the activation function, such as ReLU. Θl ∈ Rq(l)×q(l+1) refers to the weight matrix. In Eq.(1), different filter g(L) leads to different GCNs. For example, VanillaGCN along with its variants [61, 54, 16, 10] usually use the symmetric normalized adjacency matrix Â = In −L as g(L). Therefore, we mainly focus on the analysis of filter Â, and try to find out the connection between the robustness of GCNs and the perturbation on Â. To ease the notation, we denote U and Λ = diag(λ1, · · · , λN ) as the eigen-pairs of Â in the following sections unless otherwise indicated.

heading: 3.2 Poisoning Structural Attacks
text: 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 a 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 a fixed budget of perturbation ∆ on edges, i.e., ||A′ −A||0 ≤ 2∆, the adversarial attack on a GCN-based modelM can be formulated as a bi-level optimization problem [3, 9]:
argmin A′∈PG∆
Lattack(M(A′,X;Θ∗),y) s.t. Θ∗ = argmin Θ LGCN(M(A′,X;Θ),y),
where PG∆ denotes the possible perturbations within budget ∆. y is the ground-truth label. Lattack and LGCN denote the loss of adversarial attack and modelM, respectively.M(A′,X; Θ∗) refers to the prediction of modelM on the poisoned graph G′, where the weights Θ∗ keep trained to optimal.
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 a specific node u 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 = Vtest, where Vtest is the full test set.

heading: 4 Methodology

heading: 4.1 Problem Formulation
text: In a poisoning attack, the training data from G is perturbed before fed into a GCN modelM, so that the performance ofM can be degraded. Therefore, we formulate the defense problem as: Problem 1. Given a perturbed graph G′ generated by a poisoning attacker, the aim of defense on target set T is to produce a more robust modelMr to optimize:
min Θr∗ ∑ u∈T ‖Mru(A′,X;Θr ∗)−Mu(A,X;Θ∗)‖, (2)
where Mru(A′,X;Θr ∗) = ŷru refers to the prediction of node u, when Mr is trained on the poisoned graph G′ with optimal Θr∗. Mu(A,X;Θ∗) = ŷu is a hypothetical prediction thatM would make if the clean graph G is accessible.
In Eq. (2), we aim to force ŷru to approximate ŷu, then the prediction ŷu 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 obtainM′ 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′.

heading: 4.2 Spectral View of Structural Attacks
text: Following [14, 15], we observe the eigenvalues of Â after structural attacks as shown in Figure 1.
Observation 1. Under structural attacks, the high-valued eigenvalues (low-frequency components) of Â are likely to be more robust than the low-valued eigenvalues (high-frequency components).
With this empirical inspiration, GCN-SVD [14] directly preprocesses the poisoned graph and retains the top low-frequency components for defense. However, we argue that this justification is inaccurate. The relationship between robustness and graph spectrum is more complex than empirical observation. In the following, we provide an in-depth analysis of structural perturbations from the spectral domain.

heading: 4.2.1 One-edge Perturbation
text: We first consider the targeted attacks with one-edge perturbation, where T = {u} and ∆ = 1. Note that under one-edge perturbation, i.e., we conduct a single edge flip euv on A, ∆A is a matrix with only 2 non-zero elements, namely ∆Auv = ∆Avu = 1− 2Auv. Following [38], we assume that the eigenvector matrix U satisfies the following assumption:
Assumption 1. U has an orthonormal basis (uy)y∈[N ] that consists of non-negative vectors, where N is the number of nodes in the graph.
Then, we introduce the Lemma 1 to describe the differences of eigenvalues after structural attacks.
Lemma 1. Given a graph G = (V, E ,X) and one edge euv to be perturbed, the change of y-th eigenvalue after perturbation is formulated as
∆λy = { 2uyu · uyv − λy(u2yu + u2yv) if E ∪ {euv} −2uyu · uyv + λy(u2yu + u2yv) if E \ {euv},
where uyu refers to the u-th element of eigenvector uy .
The proof is available in the Appendix. With the help of Lemma 1, we can establish the relationship between robustness of GCNs and the change on each eigenvalue |∆λy| resulting from perturbations. Intuitively, smaller changes on eigenvalues indicate stronger robustness of GCNs against attacks.
Theorem 1 (Low-frequency). Assume that u2au + u2av 6= 0, u2bu + u2bv 6= 0, and (uau + uav)
2 > (ubu − ubv)2. (3) Then, there exists a pair of high-frequency λa ∈ [−1, 0) and low-frequency λb ∈ (0, 1], so that |∆λa| > |∆λb| always holds if λa and λb satisfy
max ( 0, db − da + caλa
cb
) < λb < 1; −1 < λa < min (da − cb + db ca , 0 ) , (4)
where ca = u2au + u 2 av , da = 2uau · uav , cb = u2bu + u2bv , and db = 2ubu · ubv .
The proof of Theorem 1 is available in the Appendix. From Theorem 1, we summarize two remarks. Remark 1. The top low-frequency components (i.e., components are 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 to -1) against one-edge perturbation under the condition from Inequality 3, which is consistent with Observation 1. However, it is still vulnerable to such attacks that perturb the edges satisfying (uau + uav)2 ≤ (ubu − ubv)2. This is contrary to the justification from GCN-SVD [14] and implies that not all low-frequency components are robust. Remark 2. We do not consider two special situations that u2au = u2av = 0 or u2bu = u2bv = 0, because they conclude that ∆λa = 0 or ∆λb = 0, respectively. This implies no perturbation happens on λa or λb, which is rare in practice and out of discussion.

heading: 4.2.2 Robust Interval of Low-Frequency
text: As Remark 1 from Theorem 1, Inequality 3 still makes the low-frequency components of Â suffer from certain attacks. To further get rid of this condition, we derive a new bound for low-frequency λb by removing the dependency on λa in Inequality 4 here, which reveals the robust interval: Theorem 2 (Robust interval). Assume that u2au + u2av 6= 0 and u2bu + u2bv 6= 0. There exists low-frequency λb, so that |∆λa| > |∆λb| always holds for any −1 < λa < 0 if λb satisfies
max ( 0, db − da + caλa
cb
) < λb < min (db + da − caλa cb , 1 ) .
The proof is available in the Appendix. Theorem 2 indicates the interval of λb that is able for defense, which we denote as the robust interval of λb. 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.

heading: 4.2.3 Non-Targeted Perturbation
text: In this part, we consider a more complex and practical setting, the multi-edge non-targeted perturbation, where T = Vtest and ∆ > 1. The perturbation P on each node u ∈ T can be treated as multi-edge targeted attack. Note that the multi-edge targeted perturbation is a special case when T = {u}. Specifically, we discuss the type of attacks that either consecutively inserting or deleting 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 of u. Based on Theorem 1, we obtain the following results: Corollary 1 (Low-frequency). We decompose non-targeted attacks as two steps: 1) selecting target u from T , and 2) conducting perturbations on u as multi-edge targeted attack. Assume p adversarial edges are either consecutively inserted or deleted on node u as set Pu, i.e., E ∪ Pu or E \ Pu. With the same assumptions as in Theorem 1, there exists a pair of high-frequency λa and low-frequency λb so that | ∑ u∈T ∑ v∈Pu ∆λauv| > | ∑ u∈T ∑ v∈Pu ∆λbuv| always holds if λa and λb satisfy
max v∈Pu,u∈T
( 0, dbuv − dauv + cauvλa
cbuv
) < λb < 1; −1 < λa < min
v∈Pu,u∈T (dauv − cbuv + dbuv cauv , 0 ) ,
where cauv = u2au + u 2 av , dauv = 2uau · uav , cbuv = u2bu + u2bv , and dbuv = 2ubu · ubv .
Then we can have the robust interval under non-targeted perturbations with the help of Corollary 1 as: Corollary 2 (Robust interval). With same assumptions as in Theorem 2, | ∑ u∈T ∑ v∈Pu ∆λauv| >
| ∑ u∈T ∑ v∈Pu ∆λbuv| always holds for any −1 < λa < 0 if λb satisfies
max v∈Pu,u∈T
( 0, dbuv − dauv + cauvλa
cbuv
) < λb < min
v∈Pu,u∈T (dbuv + dauv − cauvλa cbuv , 1 ) .
The proofs for Corollary 1 and Corollary 2 can be found in the Appendix. Remark 3. Under non-targeted perturbation, one could come to 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 3 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-frequency 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 4.2, it is natural to migrate the information from low-frequency components within robust interval to enhance the robustness of modelM. 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 NetMLFR
The effectiveness of the parameter sharing based regularization is demonstrated by co-training an auxiliary neural network on various of Deep Neural Networks [2, 52]. In GCN-LFR, we propose our auxiliary regularization netMLFR(A′,X;Θ) by explicitly designing the graph convolutional filter from Eq.(1) with the robust lowfrequency components. However, explicitly computing the robustness interval is infeasible before the structural attack. To alleviate this chicken or the egg style causality dilemma, we employ a set of learnable parameters F as filters to learn the robust interval for the low-frequency components during training.
Overall, the layer-wise update rule forMLFR(A′,X;Θ,F ) is: feature transformation :H ′(l) = H(l)Θ, graph convolution :H(l+1) = σ(U ′lowFU ′> lowH ′(l)), where U ′low are the top-k low-frequency eigenvectors from poisoned graph G′, and the parameters Θ will be co-trained and shared to the original GCN modelMGCN(A′,X;Θ). F = diag(f1, · · · , fk) is a 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, F can also enlarge the capacity ofMLFR by making the learned embeddings H generalize into the subspace span by U ′low.

heading: 4.3.2 Co-Training Framework
text: Consider a learning task on graph G, and a given GCN-based modelMGCN(A′,X;Θ) parametrized by Θ and poisoned by A′ is utilized to deal with this task. We denote the loss function ofMGCN as LGCN = L(MGCN(A′,X;Θ),y). Instead of minimizing LGCN alone, we propose to co-train it with the same supervised loss on an auxiliary regularization net LLFR = L(MLFR(A′,X;Θ,F ),y). In this way, we are able to compel the original model to learn a more reliable representation from the robust low-frequency components:
Ltotal = (1− α)LGCN + αLLFR, (5) where α ∈ [0, 1] is the weight coefficient for balancing the contribution of two losses. The transformation of the robust information from low-frequency components is achieved by regularizing the training of LGCN with the shared parameters Θ.
Instead of jointed optimizing LGCN and LLFR, we exploit the idea of alternative training [52] to optimize the two losses. Specifically, at each epoch, we randomly choose one of the two losses in GCN-LFR to optimize with a probability determined by α. To put it another way, we sample a random value z ∈ U(0, 1), and α acts as a 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 low-frequency components by cotraining MLFR and sharing its parameters during training procedure. Then we only use the prediction of the given model MGCN 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.

heading: 4.3.3 Complexity Analysis
text: We discuss the complexity of GCN-LFR here by the light example of VanillaGCN as backbone. For an input graph with N nodes, E edges, and M as feature dimension on each node, the complexity of a solo VanillaGCN is O(EM +NM2) [57]. Then, with the help of Lanczos algorithm [28], the time complexity of calculating the top-k eigen-pairs is O(ckN), where c is the average number of non-zero entries in a row of Â. Thus the overall complexity of GCN-LFR on VanillaGCN is O(EM +N(M2 + ck)). In our experiments, we choose to tune the hyperparameter k = d%N as the proportion of low-frequency from grid search, in order to make GCN-LFR more adaptive to different graphs. In this case, the overall complexity would be O(EM +NM2 + cN2)). In a nutshell, the extra complexity introduced by GCN-LFR during co-training is not a burden, especially when the graph is sparse, as it is in most real-world applications.

heading: 5 Experiments

heading: 5.1 Experimental Setup
text: Datasets. We mainly focus on five node classification benchmark datasets under the semi-supervised setting: 1) three citation networks, Cora [37], Citeseer and Pubmed [43], 2) a coauthor network Coauthor CS [44], 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-Multi [70]), and non-targeted attack (Mettack [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 [16], and GCNII [10].
Defense baselines. We compare GCN-LFR with four SOTA general graph defenders with their available public implementations. GCN-Jaccard [55] 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.

heading: 5.2 Defense Results Against Targeted and Non-Targeted Attacks
text: 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 1. The column “Attacked” shows the performance without any defense. From this column, we can find that NettackOne can successfully damage the performance of various models even with only a single edge flip. However, GCN-LFR can dramatically defend given GCNs against Nettack-One and consistently outperforms state-of-the-art baselines. Remarkably, we observe that the low-rank preprocessing
approach GCN-SVD is not very effective, which implies that not all low-frequency components are robust, and our strategy by transferring robust knowledge with learnable F is beneficial.
Targeted attack with multi-edge perturbation. Next, we evaluate the defending performance of targeted attacks with multi-edge perturbation. We report the defending performance on the newest variant, GCNII, in Table 2. It is not surprising that GCNII suffers more serious performance degradation under Nettack-Multi 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 is due to the wider robust interval in Theorem 2, since the bounds are tighter when iterating over all candidate edges in Corollary 4.
Non-targeted attack. To 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 time-consuming on large datasets. Table 3 demonstrates the results on VanillaGCN for all datasets. In Table 3, we can observe that the defending performance of GCN-LFR is also comparable with all baselines.

heading: 5.3 Ablation Studies
text: 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 4 shows the performance comparison of five GCN models with and without regularization netMLFR on five benign (i.e., non-attacked) datasets. As shown in Table 4, 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 MLFR net. To justify the necessity of each 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 andMLFR net, respectively. GCN-LFRFix is a variant of GCN-LFR that replaces the learnable filter F with the truncated eigenvalues Λ′low. 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-LFRFix. It implies that the trainable graph filter F is more flexible and can aid the generalization of learned embeddings in the subspace spanned by U ′low.
Aside from Figure 3, we further provide the comparison among VanillaGCN, GCN-LFRFix and GCNLFR under both benign and non-targeted 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-LFRFix. Interestingly, the better generalization ability of GCN-LFR over GCN-LFRFix could be observed implicitly either in this way.
Joint optimization vs. alternate optimization on GCN-LFR. We investigate the benefits of alternate optimization of GCN-LFR (i.e., GCN-LFRAlter). We denote the joint optimization of GCN-LFR as GCN-LFRJoint. Figure 4 provides the results of comparison. The left-side of Figure 4 demonstrates the training and validation accuracy on Pubmed dataset. VanillaGCN is used as backbone here. We can observe that GCN-LFRAlter achieves better training and validation performance compared with GCN-LFRJoint. Furthermore, the right-side of Figure 4 shows the acceleration ratio of GCN-LFRAlter over GCN-LFRJoint in terms of training time on five datasets. Acceleration ratio denotes the quotient obtained by dividing the time-consumed of GCN-LFRJoint by that of GCN-LFRAlter. We can find
that GCN-LFRAlter is more efficient by achieving an average of ×1.74 times acceleration, since GCN-LFRAlter only needs to optimize one model while GCN-LFRJoint needs to handle two models at each epoch. It verifies that GCN-LFRAlter enjoys both effectiveness and efficiency.
Aside from Figure 4, we also provide the train/validation/test accuracy comparison between GCNLFRJoint and GCN-LFRAlter over all datasets in Table 6 for clearer demonstration. The consistent conclusion as above can be drawn from Table 6.
Eigenvalues vs. learned F in the robust interval. To evaluate whether the proposed theoretical analysis is reliable, we check how many λb and the trained F fall into the robust interval on all datasets here. We report the results of top 25% smallest of eigenvalues as λb on the same 40 target nodes after one-edge perturbation in Figure 5. We can find that, though by choosing a considerably larger proportion as low-frequency, we still have an average of around 40% of λb falling into the robust interval. Further, the learnable F has more values falling into the robust interval after training, which is consistent with our observation in Figure 3. It also verifies that F could potentially learn the frequencies within the robust interval for low-frequency components and lead to a more robust model.

heading: 6 Conclusion and Limitations
text: 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 a 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 an auxiliary network jointly with the original model through parameter sharing to transfer the robustness of low-frequency components. Extensive experimental verifications demonstrate the resistance of GCN-LFR when being exposed to adversarial attacks.
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 in 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.
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).

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

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.

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.