Year: 2021

Abstract:
Graph neural networks (GNNs) have been increasingly deployed in various applications that involve learning on non-Euclidean data. However, recent studies show that GNNs are vulnerable to graph adversarial attacks. Although there are several defense methods to improve GNN adversarial robustness, they fail to perform well on low homophily graphs. In addition, few of those defense models can scale to large graphs due to their high computational complexity and memory usage. In this paper, we propose GARNET, a scalable spectral method to boost the adversarial robustness of GNN models for both homophilic and heterophilic graphs. GARNET first computes a reduced-rank yet sparse approximation of the adversarial graph by exploiting an efficient spectral graph embedding and sparsification scheme. Next, GARNET trains an adaptive graph filter on the reduced-rank graph for node representation refinement, which is subsequently leveraged to guide label propagation for further enhancing the quality of node embeddings. GARNET has been evaluated on both homophilic and heterophilic datasets, including a large graph with millions of nodes. Our extensive experiment results show that GARNET increases adversarial accuracy over state-of-the-art GNN (defense) models by up to 9.96% and 18.06% on homophilic and heterophilic graphs, respectively.

text: Graph neural networks (GNNs) have been increasingly deployed in various applications that involve learning on non-Euclidean data. However, recent studies show that GNNs are vulnerable to graph adversarial attacks. Although there are several defense methods to improve GNN adversarial robustness, they fail to perform well on low homophily graphs. In addition, few of those defense models can scale to large graphs due to their high computational complexity and memory usage. In this paper, we propose GARNET, a scalable spectral method to boost the adversarial robustness of GNN models for both homophilic and heterophilic graphs. GARNET first computes a reduced-rank yet sparse approximation of the adversarial graph by exploiting an efficient spectral graph embedding and sparsification scheme. Next, GARNET trains an adaptive graph filter on the reduced-rank graph for node representation refinement, which is subsequently leveraged to guide label propagation for further enhancing the quality of node embeddings. GARNET has been evaluated on both homophilic and heterophilic datasets, including a large graph with millions of nodes. Our extensive experiment results show that GARNET increases adversarial accuracy over state-of-the-art GNN (defense) models by up to 9.96% and 18.06% on homophilic and heterophilic graphs, respectively.

heading: 1 INTRODUCTION
text: Recent years have witnessed a surge of interest in graph neural networks (GNNs), which incorporate both graph structure and node/edge attributes to produce low-dimensional embedding vectors that maximally preserve graph structural information (Hamilton, 2020). GNNs have achieved promising results in various real-world applications, such as recommendation systems (Ying et al., 2018), self-driving car (Casas et al., 2020), protein structure predictions (Senior et al., 2020), and chip placements (Mirhoseini et al., 2021). However, recent studies have shown that adversarial attacks on graph structure accomplished by inserting, deleting, or rewiring edges in an unnoticeable way, can easily fool GNN models and drastically degrade their accuracy in downstream tasks (e.g., node classification) (Zügner et al., 2018; Zügner & Günnemann, 2019).
In literature, there are several attempts to defend GNNs against graph adversarial attacks. Entezari et al. (2020) first observed that graph adversarial attacks mainly affect high-rank properties of the graph; consequently, a low-rank graph should be first constructed by performing truncated singular value decomposition (SVD) on the graph adjacency matrix, which can then be exploited for training a robust GNN model. Later, Jin et al. (2020) proposed Pro-GNN to jointly learn a new graph and its robust GNN model with the low-rank constraints imposed by the graph structure. However, such low-rank approximation methods involve dense adjacency matrices during the GNN training stage, which will lead to quadratic time and space complexity, prohibiting their applications in large-scale graph learning tasks. Another line of research aims at enhancing GNN robustness based on the graph homophily assumption, i.e., adjacent nodes in a natural graph tend to have similar attributes, while the graph attacks essentially insert adversarial edges by connecting nodes with dissimilar attributes. As a result, researchers proposed to compute attribute similarity scores between adjacent nodes as edge weights, and drop edges with small weights to increase graph homophily (Wu et al., 2019; Zhang & Zitnik, 2020). Although such approaches can successfully improve GNN robustness on high-homophily graphs, they may fail on low-homophily (i.e., heterophily) graphs (Zhu et al., 2020).
In this paper, we propose GARNET, a spectral method for constructing GNN models that are robust to graph adversarial attacks for both homophilic and heterophilic graphs. In addition, GARNET scales comfortably to large graphs due to its nearly-linear algorithm complexity. More concretely, GARNET consists of three major kernels: (1) reduced-rank approximation, (2) adaptive filter learning, and (3) adaptive label propagation. The reduced-rank approximation kernel first performs truncated SVD on graph adjacency matrix to obtain a few dominant singular values and their corresponding singular vectors that are further leveraged to construct a sparse yet reduced-rank graph adjacency matrix; the reduced-rank adjacency matrix can effectively mitigate the effects of adversarial attacks via connecting (disconnecting) nodes that are spectrally similar (dissimilar). The adaptive filter learning kernel aims to learn a polynomial graph filter whose coefficients are trainable; the learned graph filter can adapt to the homophilic/heterophilic properties of the underlying graph and thus will work effectively for both homophilic and heterophilic graphs. The adaptive label propagation stage will leverage the learned adaptive graph filter to guide the label propagation phase, which can further improve the adversarial accuracy by enhancing the quality of node representations.
We evaluate the proposed GARNET model on three high-homophily datasets: Cora, Citeseer, and Pubmed as well as two low-homophily datasets: Chameleon and Squirrel, under strong graph adversarial attacks such as Nettack (Zügner et al., 2018) and Metattack (Zügner & Günnemann, 2019) with various perturbation settings. Moreover, we further show the nearly-linear scalability of our approach on the ogbn-products dataset that consists of millions of nodes (Hu et al., 2020). Our experimental results indicate that GARNET largely improves adversarial accuracy over baselines in most cases. The major advantages of GARNET are summarized as follows:
• GARNET is robust to graph adversarial attacks. Exploiting the proposed reduced-rank approximation scheme allows GARNET to effectively filter out the noises potentially caused by adversarial attacks in the spectral domain. This immediately leads to substantial improvement (up to 18.06%) of adversarial accuracy when comparing with the state-of-the-art baselines under the strong graph attacks on various datasets. • GARNET is agnostic to graph homophily. Unlike most existing defense models that do not work well on low-homophily adversarial graphs, GARNET leverages a trainable graph filter that can adapt to adversarial graphs with diverse levels of homophily. In addition, we theoretically demonstrate that the performance of the adaptive graph filter applied to an adversarial graph will be similar to the performance achieved on a clean graph. • GARNET is scalable to large graphs. GARNET has a nearly-linear runtime/space complexity and thus can scale comfortably to very large graph data sets with millions of nodes. We have conducted experiments on the ogbn-products dataset that contains 2 million nodes and 60 million edges, which is over 100× larger than the largest adversarial graph ever considered in the prior arts.

heading: 2 RELATED WORK
text: GNNs have received an increasing amount of attention in recent years due to its ability of learning on non-Euclidean (graph) data. In contrast to developing powerful GNN models on natural graph data, there is an active body of research focusing on adversarial attacks as well as defenses for GNNs. We summarize some of the recent efforts for graph adversarial attacks and defenses as follows.
Graph adversarial attacks aim at degrading the accuracy of GNN models by perturbing the graph structure in an unnoticeable way. For instance, most existing graph adversarial attacks insert/delete edges while maintaining node degree distribution (Sun et al., 2018). The most popular graph adversarial attacks fall into the following two categories: (1) targeted attack, (2) untargeted attack. The targeted attacks attempt to mislead a GNN model to produce a wrong prediction on a target sample (e.g., node), while the untargeted attacks strive to degrade the overall accuracy of a GNN model for the whole graph data set. Dai et al. (2018) first formulate the targeted attack as a combinatorial optimization problem and leverages reinforcement learning to insert/delete edges such that the target node is misclassified. Zügner et al. (2018) propose another targeted attack called Nettack, which produces an adversarial graph by maximizing the training loss of GNNs. Zügner & Günnemann (2019) further introduce Metattack, an untargeted attack that treats the graph as a hyperparameter and uses meta-gradients to perturb the graph structure. It is worth noting that graph adversarial attacks have two different settings: poison (perturb a graph prior to GNN training) and evasion (perturb a graph after GNN training). As shown by Zhu et al. (2021), the poison setting is typically
more challenging to defend, as it changes graph structure that fools GNN training. Thus, in this work, we evaluate our model against both targeted and untargeted attacks under the poison setting.
Graph adversarial defenses attempt to enhance GNN performance on the perturbed graphs generated by adversarial attacks. Entezari et al. (2020) first observe that Nettack, a strong targeted attack, only changes the high-rank information of the adjacency matrix after graph perturbation. Thus, they propose to construct a low-rank graph by performing truncated SVD to undermine the effects of adversarial attacks. Jin et al. (2020) propose Pro-GNN that adopts a similar idea yet jointly learns the low-rank graph and GNN model. However, such low-rank approximation based methods produce dense adjacency matrices that correspond to complete graphs, which would limit their applications for large graphs. Another line of research strives to purify the adversarial graph by assigning edge weights. Specifically, Wu et al. (2019) propose to modify the edge weights by computing the Jaccard similarity score per edge based on node attributes, which is followed by Zhang & Zitnik (2020) that propose GNNGuard to learn node attribute similarity score per edge through a trainable linear layer. Nonetheless, such approaches assume that nearby nodes should have similar attributes (i.e., graph homophily assumption), which is not valid for heterophilic graphs that have adjacent nodes with dissimilar attributes (Zhu et al., 2020). In contrast to the prior arts, GARNET achieves highly robust yet scalable performance on both homophilic and heterophilic graphs under adversarial attacks by leveraging novel reduced-rank approximation and adaptive graph filtering schemes.

heading: 3 OUR APPROACH
text: Figure 1 gives an overview of our proposed approach, GARNET, which consists of three major phases. The first phase (reduced-rank approximation) constructs a reduced-rank yet sparse graph model by exploiting scalable truncated SVD and nearest-neighbor graph algorithms (Baglama & Reichel, 2005; Malkov & Yashunin, 2018). The second phase (adaptive filter learning) is the only phase that involves training, which outputs a learned graph filter that can adapt to the homophilic/heterophilic properties of the underlying graph. The last phase (adaptive label propagation) leverages the learned adaptive graph filter to guide the subsequent label propagation process. In the rest of this section, we will describe each of these three phases in more detail.
0

heading: 3.1 REDUCED-RANK APPROXIMATION (PHASE 1)
text: The adjacency matrices of many real-world graphs (e.g., social network and biological network) are naturally low rank and sparse, as the nodes typically tend to form communities and have a small number of neighbors (Zhou et al., 2013). As a result, graph adversarial attacks can be viewed as compromising these properties by inserting edges that connect nodes from different communities (Zügner et al., 2018; Zügner & Günnemann, 2019). Recently, Entezari et al. (2020) and Jin et al. (2020) have shown that the well-known graph adversarial attacks (e.g., Nettack and Metattack) are essentially high-rank attacks, which mainly change the high-rank spectrum of the graph when perturbing the graph structure, while the low-rank spectrum remains almost the same. We empirically confirm that the graph rank indeed increases under adversarial attacks in Appendix A.7.
Consequently, a natural way for improving GNN robustness is to purify an adversarial graph by eliminating the high-rank components of its spectrum.
To enhance GNN robustness, Entezari et al. (2020) and Jin et al. (2020) reconstruct a graph that only preserves the low-rank components of its spectrum to mitigate the effects of adversarial attacks, via performing truncated SVD on the adjacency matrix. Specifically, given a graph adjacency matrix A ∈ Rn×n, the rank-r approximated adjacency matrix can be obtained via truncated SVD: Â = UΣV T , where Σ ∈ Rr×r is a diagonal matrix consisting of r largest singular values of A. U ∈ Rn×r and V ∈ Rn×r contain the corresponding left and right singular vectors, respectively.
However, the reconstructed low-rank adjacency matrix Â has two key issues: (1) Â is typically a dense matrix with O(n2) nonzero elements, which may result in prohibitively expensive storage as well as GNN training, where n represents number of nodes (Entezari et al., 2020; Jin et al., 2020). Thus, existing low-rank approximation methods are not scalable to large graphs; (2) Due to the high computational cost of SVD, Â is typically obtained by only leveraging top r singular values and singular vectors, where r is a relatively small number (e.g., r = 50). Consequently, the rank of Â is only r = 50, which loses too much important spectrum information and thus limits the performance of GNN training.
Reduced-rank approximation via sparsification. To avoid the quadratic space complexity for obtaining Â, one simple solution is to sparsify Â on the fly. More concretely, instead of directly computing Â = UΣV T , we can compute Â row by row: Âi,: = Ui,:ΣV T . Once we obtain Âi,:, we can sparsify it by setting Ãi,j = 0 if Âi,j < δ and Ãi,j = Âi,j otherwise, where δ is a hyperparameter to control the sparsity. In this way, we only need to store a dense vector Âi,: at a time and the final adjacency matrix Ã is sparse. Although the space complexity is reduced to O(m), where m denotes the number of non-zero elements in Ã, this sparsification method still has quadratic time complexity for computing Ã. To tackle this issue, in this work a nearly-linear complexity algorithm for constructing a reduced-rank yet sparse matrix Ã is proposed by exploiting the following connection between matrix sparsification and spectral graph embedding. Definition 1. Given the top r smallest eigenvalues λ1, λ2, ..., λr and their corresponding eigenvectors v1,v2, ...,vr of normalized graph Laplacian matrix Lnorm = I −D− 1 2AD− 1 2 , where I and A are the identity matrix and graph adjacency matrix, respectively, and D is a diagonal matrix of node degrees, the weighted spectral embedding matrix is defined as:
V def = [√ |1− λ1|v1, ..., √ |1− λr|vr ] , (1)
whose i-th row Vi,: is the weighted spectral embedding of the corresponding i-th node in the graph.
Theorem 1. Given a normalized graph adjacency matrix Anorm = D− 1 2AD− 1 2 of an undirected graph, let Â be the rank-r approximation of Anorm via truncated SVD. If the top r dominant eigenvalues of Anorm are non-negative, then Âi,j corresponds to the dot product score between the weighted spectral embeddings of node i and j.
Theorem 1 indicates that the reduced-rank approximation of the normalized adjacency matrix via truncated SVD captures the spectral similarity between nodes, which motivates us to leverage weighted spectral embeddings to capture graph spectral (low-rank) information, thereby identifying edges to be pruned (sparsified) from the graph. Unlike traditional spectral graph embedding methods that utilize the first r Laplacian eigenpairs to construct spectral embedding matrix, we exploit the top r largest singular values and their singular vectors of Anorm that may include both the smallest and largest Laplacian eigenpairs for capturing global and local structural information, respectively (Shuman et al., 2013). More specifically, given a graph G = (V, E) and its normalized adjacency matrix Anorm, our approach first computes the r largest singular values (e.g., r = 50) and the corresponding singular vectors of Anorm leveraging efficient eigensolvers in O(r|E|) time to construct the weighted spectral embeddings (Baglama & Reichel, 2005); next, the embedding results are then used to construct a nearest neighbor (NN) graph, where each node will be connected to its k most spectrally similar nodes. Afterwards, we compute the dot product similarity scores between adjacent nodes in the NN graph. If the similarity score is less than a threshold δ, we prune the corresponding edge from the NN graph to further sparsify the graph. In this work, we exploit an approximate k-nearest neighbor algorithm for constructing the NN graph, which has O(|V| log |V|)
complexity and thus can scale to very large graphs (Malkov & Yashunin, 2018). We say a graph is a reduced-rank graph if its adjacency matrix is obtained via the proposed reduced-rank approximation method. As a result, we can obtain a reduced-rank and sparse graph in O(r|E|+ |V| log |V|) time. Apart from the advantage of scalability, our kNN-based reduced-rank graph also preserves much more important spectrum information than the truncated SVD-based low-rank graph. As shown by Entezari et al. (2020), adversarial attacks only perturb the top few highest singular components in the graph spectrum, while the rest of spectral information corresponds to the clean graph structure in the spatial domain. Nonetheless, Figure 5 in Appendix A.8 shows the truncated SVD-based method aggressively reduces graph rank to 50, which is two orders of magnitude smaller than the rank of input graph. In contrast, our reduced-rank method only removes the highest singular components, while retaining most of important spectral information. As a result, our reduced-rank approximation kernel leads to a significant accuracy improvement over the SVD-based low-rank approximation. More details are available in Appendices A.11.

heading: 3.2 ADAPTIVE FILTER LEARNING (PHASE 2)
text: Most existing GNN defense models (implicitly) assume the underlying graph is homophilic, implying that nearby nodes will share similar attributes; however, this assumption is not valid for heterophilic graphs in which adjacent nodes may have dissimilar attributes (Ma et al., 2021). As a consequence, existing defense methods may not be robust against graph adversarial attacks on heterophilic graphs. To address this limitation, we adopt the concept of learning a polynomial graph filter that can adapt to graph homo/heterophily (NT et al., 2020; Chien et al., 2021), and apply it on the adversarial graphs. Specifically, given a graph and its node attribute matrix X , our graph filter learning process works as follows:
X̂ = MLP (X) (2)
Z = softmax( P∑ p=0 cpF pX̂) (3)
where F can be either a normalized adjacency matrix Anorm = D− 1 2AD− 1 2 or normalized Laplacian matrix Lnorm = I − Anorm, c0, c1, ..., cP are P + 1 learnable polynomial coefficients. We use the output node embedding matrix Z and node training labels to calculate training loss. The weights of MLP as well as learnable polynomial coefficients are then updated via backpropagation.
Next, we are going to show that the learnable coefficients c0, c1, ..., cP enable the polynomial graph filter gP (F ) = ∑P p=0 cpF p in Equation 3 to adapt to a homo/heterophilic graph.
Lemma 1 (Chien et al. (2021)). Assume the graph G is connected and |cp| ≤ 1 ∀p ∈ {0, 1, ..., P}. Let F to be the normalized adjacency matrix F = D− 1 2AD−
1 2 . If cp ≥ 0 ∀p ∈ {0, 1, ..., P},∑P
p=0cp = 1, and ∃p′ > 0 such that cp′ > 0, then gp(F ) is a low-pass filter. Also, if cp = (−α)k, α ∈ (0, 1) and P is large enough, then gp(F ) is a high-pass filter.
Intuitively, Lemma 1 indicates that for a homophilic graph the filter coefficients tend to be positive, whereas for a heterophilic graph both positive and negative coefficients can be observed. Consequently, gP (F ) can be learned to serve as a low-pass (high-pass) graph filter to filter node intermediate embeddings X̂ over the homophilic (heterophilic) graph, such that nearby nodes will have similar (dissimilar) output embeddings. Thus, a natural idea for developing a robust GNN model on both homophilic and heterophilic graphs is to exploit both the reduced-rank graph in Section 3.1 and the aforementioned adaptive polynomial graph filter.
However, adaptive polynomial graph filters typically perform well on clean graphs that are entirely homophilic or heterophilic, while the adversarial graphs can be globally homophilic yet locally heterophilic (Zhu et al., 2021). Another important question is whether the polynomial filters can still be effective when combined with reduced-rank approximation of the adversarial graph. Next, we answer this question by showing the upper bound of the performance difference between the polynomial graph filter on a clean graph and that on the corresponding reduced-rank graph.
Theorem 2. Let Aclean, Aadv , and Ar represent the normalized adjacency matrices of a clean graph, the corresponding adversarial graph, and the rank-r approximated adversarial graph, respectively. Also let σr+1 denote the (r + 1)-th largest singular value of Aadv . Assume the spectral
norm of graph adversarial perturbation is upper bounded by a constant ϵ, i.e., ∥Aclean−Aadv∥2 ≤ ϵ. Given a polynomial graph filter gP (F ) = ∑P p=0 cpF p , we have:
∥gP (Aclean)− gP (Ar)∥2 ≤ P∑
p=1
p |cp| (ϵ+ σr+1) (4)
Note that the graph attacking algorithms are typically designed to perturb the graph structure in an unnoticeable way, which means that ϵ is a small value. Moreover, σr+1 is within the range of [0, 1] since Aadv is normalized. We further set P ≤ 10 and enforce ∑P p=0 |cp| = 1 when learning the adaptive filter to tighten the upper bound. As a result, Theorem 2 indicates that the performance of a polynomial filter on the reduced-rank graph will be similar to its performance on the clean graph. Hence, applying the adaptive graph filter on the reduced-rank graph constructed in Section 3.1 allows GARNET to work effectively for both homophilic and heterophilic graphs under adversarial attacks.
Scalability of adaptive filter learning. To scale the adaptive filter learning process to large graphs, we do not explicitly form the graph filter gP (F ) = ∑P p=0 cpF
p. Instead, we iteratively left-multiply X̂ by F in Equation 3 to leverage the sparsity of F . Thus, the time complexity is linear to the graph size. Besides, we can effectively exploit model parallelism (Castelló et al., 2019) , where the computation of a graph filter gP (F ) is distributed onto multiple GPUs based on the index p that indicates the p-th term in gP (F ). This way, we can dramatically reduce the memory usage per GPU, thereby allowing the adaptive filter learning process to scale to large graphs with millions of nodes.

heading: 3.3 ADAPTIVE LABEL PROPAGATION (PHASE 3)
text: Once the trained graph filter g∗P (F ) = ∑P p=0 c ∗ pF
p is obtained, we further leverage it to enhance the quality of node embeddings Z in Equation 3 by correlating residue errors and propagating node labels, which is partly inspired by the correct and smooth (C&S) method recently proposed in (Huang et al., 2020). The key idea of C&S is to smooth the residue errors and node labels over the graph leveraging a low-pass graph filter, which assumes the underlying graph to be homophilic. In contrast, our approach works effectively for both homophilic and heterophilic graphs by exploiting adaptive filter learning. Specifically, let NL and NU be the set of nodes that are labelled and unlabelled, respectively. Given the one-hot label matrix Y ∈ Rn×c, where n and c denote the numbers of nodes and classes, respectively, we define the residue error matrix by R ∈ Rn×c such that RNL = ZNL − YNL and RNU = 0. Our goal is to optimize the following objective:
R̂ = argmin H
∥H −R∥2F + λTr(HT (I − 1
P g∗P (F ))H) (5)
where λ is a regularization parameter. The first term in Equation 5 enforces the solution to be close to the initial residue error R that contains the label information. The key difference between our approach and the prior C&S method lies in the second term: our method spreads the error over the graph guided by the trained adaptive filter g∗P (F ), whereas the C&S method adopts a simple (non-adaptive) smoothing scheme. Note that there is no training involved in this phase and R̂ can be iteratively computed by R̂t+1 = α 1P g ∗ P (F )R̂
t + (1 − α)R in O(m) time due to the sparsity of F , where α = λ1+λ and m is the number of edges in graph. After obtaining R̂, we update the node embeddings Z̃ by Z̃NL = YNL and Z̃NU = ZNU + βR̂NU , where β is a hyperparameter. As suggested in Huang et al. (2020), we further refine Z̃ by substituting Z̃ for R in Equation 5 to diffuse the label information over the graph, thereby obtaining the corresponding optimizer Ẑ. Subsequently, Ẑ will be utilized as the final node embeddings in the following label prediction step.

heading: 4 EXPERIMENTS
text: We have conducted comparative evaluation of GARNET against state-of-the-art defense GNN models on both homophilic and heterophilic datasets, under targeted attack (Nettack) (Zügner et al., 2018) and non-targeted attack (Mettack) (Zügner & Günnemann, 2019) with different perturbation budgets. Besides, we further evaluate the scalability of GARNET on ogbn-products, which is over 100× larger than the datasets used in Entezari et al. (2020); Zhang & Zitnik (2020); Jin et al. (2020). Finally, we perform ablation studies to understand the effectiveness of each kernel in GARNET.
Experimental Setup. The details of datasets are available in Appendix A.9.2. We evaluate unvaccinated GCN (Kipf & Welling, 2016) and GPRGNN (Chien et al., 2021). Moreover, we choose as the defense baselines three state-of-the-art vaccinated GNN models: GCNSVD (Entezari et al., 2020), GNNGuard (Zhang & Zitnik, 2020), and Pro-GNN Jin et al. (2020). Besides, we further evaluate a strong defense baseline GPRSVD-CS by combining truncated SVD (for low-rank approximation), GPRGNN (for adaptive filter learning), and C&S (for label propagation). For all baselines, we tune their hyperparameters against adversarial attacks with a small perturbation, and keep the same hyperparameters for larger adversarial perturbations. We further show hyperparameter settings of GARNET and hardware information in Appendix A.9.

heading: 4.1 DEFENSE ON HOMOPHILIC GRAPHS
text: Defense against targeted attack. We first evaluate the model robustness against Nettack, a strong attack method to fool a GNN model to misclassify some target nodes with a few structure (edge) perturbations. We choose the same set of target nodes as in (Jin et al., 2020). We report the averaged accuracy over 10 runs on Cora, Citeseer, and Pubmed datasets with adversarial perturbations varying from 0 to 5 per target node. Table 1 shows that GARNET outperforms all the baselines in most cases, with the accuracy improvement up to 9.96% over existing defense methods. Note that the accuracy degradation of GARNET when increasing perturbation budget is much smaller than that of baselines. For instance, the accuracy drop of GARNET is only 1.39% with perturbations varying from 1 to 5 on Pubmed, while the accuracy of baseline defense methods drops 4.9% ∼ 17.95%, indicating that GARNET is indeed more robust to strong targeted attack on homophilic graphs. Moreover, GARNET gains up to 8.5% accuracy improvement over GPRSVD-CS, which reveals that our reduced-rank approximation kernel produces a much higher quality of low-rank graph than the SVD-based graph by preserving more useful spectrum information as explained in Section 3.1.
Defense against non-targeted attack. We further evaluate model robustness against a strong nontargeted attack, i.e., Metattack, whose goal is to drop the overall accuracy of the whole test set with a given perturbation ratio budget (i.e., the number of adversarial edges over the number of total edges). We report the averaged accuracy over 10 runs on Cora, Citeseer, and Pubmed with perturbation ratio in {0%, 10%, 20%}. As shown in Table 2, GARNET consistently achieves the highest adversarial accuracy across all datasets under different attack perturbation ratios, which verifies that GARNET can also successfully defend against the non-targeted attack on homophilic graphs. It is worth mentioning that both GPRSVD-CS and Pro-GNN run out of memory even on Pubmed, a graph with only 20k nodes. In contrast, GARNET is not only robust to adversarial attacks, but also scalable to large graphs, as empirically shown in Section 4.3.

heading: 4.2 DEFENSE ON HETEROPHILIC GRAPHS
text: To evaluate the robustness on heterophilic graphs, we apply both targeted (Nettack) and non-targeted (Metattack) attacks on Chameleon and Squirrel datasets. Due to the space limitation, we only report the adversarial accuracy under Metattack in Table 3. The results under Nettack are available in Appendix A.4. As shown in Table 3, all defense baselines are not robust to graph adversarial attacks on heterophilic graphs. Moreover, the performance of those vaccinated models is in fact drastically worse than that of the unvaccinated model GPRGNN, a model designed to handle heterophilic graphs. Our approach, on the other hand, consistently outperforms all defense baselines by a large margin. For instance, GARNET achieves 18.06% accuracy improvement over the best vaccinated model (i.e., GPRSVD-CS) on Chameleon with a 20% perturbation ratio. Moreover, GARNET also consistently increases adversarial accuracy over GPRGNN. Apart from achieving the highest accuracy, the accuracy drop of GARNET is much smaller compared to that of baselines when increasing the perturbation ratio. Specifically, the accuracy of GARNET drops 1.15% on Chameleon when increasing the perturbation ratio from 0% to 20%, while the accuracy of baselines drops 2.10% ∼ 18.12%. Thus, GARNET is also robust against graph adversarial attacks on heterophilic graphs.

heading: 4.3 DEFENSE ON LARGE GRAPHS
text: To demonstrate the scalability of GARNET on large graphs, we evaluate the robustness of GARNET on the attacked ogbn-arxiv and ogbn-products. Given that existing strongest attacks (Nettack and Metattack) are not scalable to large graphs, we leverage a less powerful yet more scalable attacking algorithm called DICE (Waniek et al., 2018), which randomly connects (disconnects) nodes from
different (same) classes, to perturb the graph structure. To have a challenging defense scenario, we consider a large perturbation budget for DICE while keeping the overall graph size the same. Specifically, we use DICE to first randomly delete 30% edges linking nodes from the same class and then randomly insert 30% edges linking nodes from different classes. We evaluate GNNGuard as a defense baseline, since all other defense baselines (i.e., GPRSVD-CS, GCNSVD, and ProGNN) run out of memory on these two datasets. Table 4 reports the accuracy and run time on large graphs under DICE attack, which shows GARNET outperforms GNNGuard by a margin of 2.43% and 8.92% on ogbn-arxiv and ogbn-products, respectively, with around 20× runtime speedup. We further show the run time per kernel of GARNET in Appendix A.5.

heading: 4.4 ABALATION ANALYSIS ON GARNET KERNELS
text: To study the effectiveness of our proposed GARNET kernels separately, we conduct experiments by adding three kernels one by one to see how each kernel affects the adversarial accuracy. Specifically, we evaluate the model robustness against Nettack with the number of perturbations varying from 1 to 5 per target node. We show results on three datasets (two homophilic datasets Cora & Pubmed and one heterophilic dataset Squirrel) in Figure 2. When we only train an adaptive graph filter for node prediction, the adversarial accuracy is comparable to the accuracy of Pro-GNN on homophilic datasets, while it largely outperforms Pro-GNN on the heterophilic dataset, which shows the adaptive filter works effectively on both homophilic and heterophilic graphs. Figure 2 further shows that adding the reduced-rank approximation kernel results in a much more graceful accuracy degradation when increasing the budget of adversarial perturbations. For instance, the accuracy achieved by combining reduced-rank approximation and adaptive filter remains almost the same when increasing the perturbation from 1 to 5 per target node on Pubmed. This implies that our reduced-rank approximation kernel can effectively remove the high-rank adversarial properties from the input graph, allowing GARNET to be more resistant to graph adversarial attacks. It is worth noting that existing SVD-based low-rank methods (e.g., GPRSVD-CS) performs much worse than our reduced-rank method, which lies in the fact that our reduced-rank kernel preserves much more important spectrum information than SVD-based method as analyzed in Section 3.1. Furthermore, incorporating the adaptive label propagation kernel also helps improve the adversarial accuracy, implying that propagating node labels by using the adaptive filter can effectively exploit the label information for further enhancing the quality of node representations under adversarial attacks.

heading: 5 CONCLUSIONS
text: This work introduces GARNET, a spectral approach to robust and scalable graph neural networks. GARNET first construct a reduced-rank yet sparse approximation of the adversarial graph; then it trains an adaptive graph filter to obtain refined node representations as well as the learned adaptive filter that will subsequently guide the process of label propagation to further enhance the quality of node representations. Results show that GARNET outperforms state-of-the-art defense models on homophilic and heterophilic graphs under both targeted and non-targeted adversarial attacks.

heading: REPRODUCIBILITY STATEMENT
text: The GARNET source code is available at github.com/gnngarnet/garnet. Besides, we provide our proofs for Theorems 1 and 2 in Appendices A.1 and A.2, respectively. Moreover, the proof for Lemma 1 is available in Chien et al. (2021). Finally, the details of all datasets used in our experiments are available in Appendix A.9.

heading: A APPENDIX

heading: A.1 PROOF FOR THEOREM 1
text: Proof. As the graph is undirected, we can perform eigendecomposition on both Anorm and Lnorm. Let λi, λ̂i, and σi, i = 1, 2, ..., r denote the r smallest eigenvalues of Lnorm, r largest eigenvalues of Anorm, and r largest singular values of Anorm, respectively. Since Anorm = I − Lnorm, Anorm and Lnorm share the same set of eigenvectors while their eigenvalues satisfy: λ̂i = 1 − λi, i = 1, 2, ..., r. Moreover, since we assume that the r largest magnitude eigenvalues of Anorm are nonnegative, we have σi =
∣∣∣λ̂i∣∣∣ = λ̂i, i = 1, 2, ..., r. Thus, we have: V V T = [v1, ...,vr]
|1− λ1| . . . |1− λr|  [v1, ...,vr]T
= [v1, ...,vr]  ∣∣∣λ̂1∣∣∣
. . . ∣∣∣λ̂r∣∣∣
 [v1, ...,vr]T
= [v1, ...,vr] σ1 . . . σr  [v1, ...,vr]T = Â
Since Vi,: is defined as the weighted spectral embedding of node i and Âi,j = Vi,:V Tj,: , Âi,j corresponds to the dot product score between the weighted spectral embeddings of node i and j, which completes the proof of the theorem.

heading: A.2 PROOF FOR THEOREM 2
text: To prove Theorem 2, we first give two Lemmas below:
Lemma 2. Given a graph adjacency matrix A and degree matrix D, let Anorm = D− 1 2AD− 1 2 , and Ânorm is the low-rank approximation of Anorm via truncated SVD, we have ∥Anorm∥2 ≤ 1 and ∥Ânorm∥2 ≤ 1
The proof for Lamma 2 is trivial since the spectrum of Anorm and Ânorm lies in [−1, 1] (Chung, 1997). Lemma 3. Given two matricies M and N such that ∥M∥2 ≤ 1 and ∥N∥2 ≤ 1, we have ∥Mp − Np∥2 ≤ p∥M −N∥2 for every p ≥ 0.
The proof for Lamma 3 is available in Levie et al. (2019).
Next, we formally prove Theorem 2 in the following:

heading: Proof.
text: ∥gP (Aclean)− gP (Ar)∥2 = ∥ P∑
p=0
cpA p clean − P∑ p=0 cpA p r∥2
= P∑ p=1 ∥cp(Apclean −A p r)∥2 ≤ P∑
p=1
|cp| ∥Apclean −A p r∥2
≤ P∑
p=1
p |cp| ∥Aclean −Ar∥2
≤ P∑
p=1
p |cp| (∥Aclean −Aadv∥2 + ∥Aadv −Ar∥2)
≤ P∑
p=1
p |cp| (ϵ+ σr+1)
The second inequality above is based on Lemmas 2 and 3, while the third inequality is derived by using the triangle inequality.

heading: A.3 GARNET ALGORITHM AND COMPLEXITY ANALYSIS
text: Algorithm 1: GARNET algorithm Input: Adjacency matrix A ∈ Rn×n; node feature matrix X ∈ Rn×d; node
label matrix Y ∈ Rn×c; truncated svd rank r; kNN graph k; polynomial filter degree P ; error correction scale β; train node set NL; test node set NU ; label propagation iteration s; regularization parameter α
Output: Node embedding matrix Ẑ ∈ Rn×c /* Phase1:reduced-rank approximation */
1 U ,S,V T = truncated svd(A, rank = r); 2 Ã = kNN graph(U √ S, k);
/* Phase2:adaptive filter learning */ 3 for 1...epochs do 4 X̂ = MLP (X); 5 Z = Softmax( ∑P p=0 cpÃ
pX̂); 6 loss = CrossEntropyLoss(Z,Y ); 7 loss.backward(); 8 end /* Phase3:adaptive label propagation */
9 RNL = ZNL − YNL; 10 RNU = 0; 11 R̂0 = R; 12 for i = 0...s do 13 R̂i+1 = α
P ∑P p=0 c ∗ pÃ
pR̂i + (1− α)R; 14 end 15 Z̃NL = YNL; 16 Z̃NU = ZNU + βR̂NU ; 17 Ẑ0 = Z̃; 18 for i = 0...s do 19 Ẑi+1 = α
P ∑P p=0 c ∗ pÃ
pẐi + (1− α)Z̃; 20 end
The algorithm of GARNET is shown in Algorithm 1. We further analyze the total complexity of GARNET on a graph G = (V, E). Specifically, as we mention in Section 3.1, the complexity of the truncated SVD with rank r and approximate kNN graph construction is O(r |E|) and O(|V| log |V|), respectively. Thus, the complexity of the reduced-rank approximation kernel is O(r |E| + |V| log |V|). Moreover, the complexity of computing adaptive filter is O(c |E|), where c is the column dimension of X̂ , since we can leverage the sparsity of the graph for computing ÃX̂ . Similarly, the complexity of adaptive label propagation kernel is O(sP |E|), where s is the number of steps to iteratively compute R̂ and Ẑ, and P denotes the polynomial degree. Consequently, the overall complexity of GARNET is O((r + c + sP ) |E| + |V| log |V|). For the space complexity of GARNET, the reduced-rank kernel involves forming a sparse kNN graph by building hierarchical navigable small world (HNSW) graphs that contain O(|V| log |V|) nodes in total and each node connects to a fixed number of neighbors. Thus, it has O(|V| log |V| + |E|) space complexity, where |V| log |V| represents the space usage of storing the HNSW graphs and |E| denotes the space usage of the constructed kNN graph. In regard to the adaptive filter learning and label propagation kernels, we do not explicitly form the graph filter gP (F ) = ∑P p=0 cpF
p. Instead, we iteratively left-multiply node embedding matrix X̂ and H by F in Equations 3 and 5, respectively, to leverage the sparsity of F . Since the nonzero elements in F correspond to edges in the reducedrank (kNN) graph and the node embedding matrix is in the shape of |V| × d, both adaptive filter learning and label propagation kernels have O(|E|+d |V|) space complexity. As a result, the overall space complexity of GARNET is O(|E|+ (d+ log |V|) |V|).

heading: A.4 ACCURACY ON HETEROPHILIC DATASETS UNDER NETTACK
text: As shown in Table 5, the four vaccinated baseline models, i.e., GPRSVD-CS, GCNSVD, GNNGuard, and Pro-GNN, only achieve comparable or even worse accuracy than the unvaccinated model GPRGNN in most cases, which indicates that those defense models lose its robustness on heterophilic graphs. In contrast, GARNET largely outperforms all baselines in most scenarios. For instance, the accuracy of GARNET is 12.18% higher than the accuracy of the best baseline (i.e., GPRSVD-CS) on Squirrel with 3 perturbations per target node. Moreover, the accuracy drop of GARNET when increasing the number of perturbations per target node is only 1.06% and 1.27% on Chameleon and Squirrel, respectively, which indicates that GARNET is also resistant to the targeted attack on heterophilic graphs.

heading: A.5 RUN TIME PER KERNEL IN GARNET
text: Table 6 reports the run time of each sub-kernel in GARNET on Cora, Pubmed, ogbn-arxiv, and ogbn-products. It shows that training the adaptive graph filter is the most time consuming kernel in GARNET. It is also worth mentioning that the run time of truncated SVD and approximate kNN
graph construction is less than 7 minutes on ogbn-products, which contains 2 million of nodes and 60 million edges. This is consistent with their near-linear complexity analyzed in Section 3.1.

heading: A.6 ABLATION STUDY ON KNN GRAPH CONSTRUCTION
text: To evaluate the sensitivity of GARNET to approximate kNN (AKNN) graph construction, we show the adversarial accuracy of GARNET with different k values for constructing AKNN graphs in Figure 3, which indicates that the accuracy of GARNET does not change too much when varying k value within the range of [30, 100], especially on the Cora and Pubmed datasets. Hence, we recommend choosing k = 50 ∼ 80 for the AKNN graph construction.

heading: A.7 GRAPH RANK UNDER ADVERSARIAL ATTACKS
text: To verify that applying adversarial attacks on a graph indeed increases its rank, we evaluate how the graph rank changes when increasing the perturbation ratio of Metattack. Specifically, we evaluate the graph rank growth rate on three homophilic graphs Cora, Citeseer, and Pubmed, as well as one heterophilic graph Chameleon. Figure 4 shows that the graph ranks grow with increasing perturbation ratios (0% to 25%). For the results showing that other graph adversarial attacks increase graph ranks, we refer to Figure 3 in Entezari et al. (2020) and Figure 1 in Jin et al. (2020).

heading: A.8 GRAPH RANK COMPARISON
text: We compute the rank of each adversarial graph under Metattack with the perturbation ratio varying from 5% to 25%, and compare the result with its corresponding two low-rank graphs obtained via our reduced-rank approximation and truncated SVD (TSVD) respectively. Note that we use the
same r = 50 largest singular values and their corresponding singular vectors for our reduced-rank kernel and TSVD. Figure 5 shows that the TSVD-based method aggressively reduces the graph rank to 50 and thus loses lots of useful spectral information. In contrast, our reduced-rank graph only removes high-rank adversarial graph properties while keeping rest of meaningful spectral information, demonstrating the effectiveness of the proposed reduced-rank approximation scheme.

heading: A.9 EXPERIMENTAL SETUP

heading: A.9.1 HYPERPARAMETER SETTINGS OF GARNET
text: We show the hyperparameters of the reduced-rank approximation kernel and the adaptive filter learning kernel on different datasets under Nettack (1 perturbation per node), Metattack (10% perturbation ratio), and DICE (60% perturbation ratio) in Table 7. For the adaptive label propagation kernel, we do not manually tune hyperparameters but instead leverage Optuna (Akiba et al., 2019) to optimize the hyperparameters such as the scale β for error correction based on the validation set, since this kernel is fast to compute. We refer to github.com/gnngarnet/garnet for details of hyperparameters used in the adaptive label propagation kernel. We run all GNN training with full batch.

heading: A.9.2 DATASET DETAILS
text: Table 8 shows the statistics of the datasets used in our experiments. We follow Zhu et al. (2020) to compute the homophily score per dataset (lower score means more heterophilic). As in Jin et al.

heading: Dataset Type Homophily Score Nodes Edges Classes Features
text: (2020), we extract the largest connected components of the original Cora, Citeseer, and Pubmed datasets (Yang et al., 2016) for the adversarial evaluation, with the same train/validation/test split. For Chameleon and Squirrel (Rozemberczki et al., 2021), we keep the same split setting as Chien et al. (2021). Finally, we follow the split setting of Open Graph Benchmark (OGB) (Hu et al., 2020) on ogbn-arxiv and ogbn-products.
In addition, we follow Jin et al. (2020) for the selection of target nodes on Cora, Citeseer, and Pubmed under Nettack. For the Chameleon and Squirrel datasets under Nettack, we choose target nodes that have degrees within the range of [20, 50] and [20, 140], respectively. In regard to nontargeted attacks (i.e., Metattack and DICE), we choose nodes in the test set as target nodes for all datasets.

heading: A.9.3 HARDWARE INFORMATION
text: For ogbn-arxiv and ogbn-products, we run experiments on a Linux machine with an Intel Xeon Silver 4214 CPU (8 cores @ 2.20GHz) and 4 NVIDIA RTX A6000 GPUs (48 GB memory per GPU). For the rest of the datasets, we conduct all experiments on a Linux machine with an Intel Xeon Gold 5218 CPU (8 cores @ 2.30GHz) CPU and an NVIDIA RTX 2080 Ti GPU (11 GB memory per GPU).

heading: A.10 ABLATION STUDY ON SPECTRAL EMBEDDING
text: To show that the spectral embedding used in our reduced-rank approximation kernel not only contributes to low-rank approximation but also captures key structural information per node, we compare our spectral embedding method, which uses top 50 largest singular values and corresponding singular vectors of adjacency matrix, with the vanilla spectral embedding method that leverages the top 50 smallest eigenvalues and eigenvectors of Laplacian matrix. As shown in Figure 6, the singu-
lar component (SC) based spectral embedding outperforms the vanilla spectral embedding in most cases. The underlying reason is that the largest singular components of adjacency matrix correspond to both smallest and largest eigenvalues and their corresponding eigenvectors of Laplacian matrix, which capture global and local information, respectively (Shuman et al., 2013).

heading: A.11 REDUCED-RANK APPROXIMATION VS. TRUNCATED SVD
text: Algorithm 2: Reduced-rank approximation algorithm (Ours) Input: Adjacency matrix A ∈ Rn×n; kNN graph k; sparsification
threshold δ Output: Reduced-rank adjacency matrix Ã ∈ Rn×n /* Obtain singular components via TSVD */ 21 U ,S,V T = truncated svd(A, rank = 50); /* Node spectral embedding */
22 X = U √ S;
/* Approximate kNN graph construction */
23 Â = kNN graph(X, k); /* Drop edges with node similarity scores lower
than δ */
24 Ã = sparsification(Â, δ);
Algorithm 3: Truncated SVD based low-rank approximation algorithm Input: Adjacency matrix A ∈ Rn×n Output: Reduced-rank adjacency matrix Ã ∈ Rn×n
25 U ,S,V T = truncated svd(A, rank = 50); 26 Ã = USV T ;
Algorithms 2 and 3 show the difference between our reduced-rank approximation (RRA) method and truncated SVD (TSVD) low-rank approximation method. Note that the low-rank adjacency matrix Ã produced by TSVD method has two issues: (1) Ã is typically a dense matrix corresponding to a (nearly) complete graph, which cannot scale to large graphs; (2) Ã is an extremely low-rank matrix (e.g., rank = 50) that is two orders of magnitude smaller than the rank of input graph, as shown in Figure 5, which loses too much important spectral information.
In contrast, our RRA algorithm only involves a sparse adjacency matrix, whose density is roughly k n with k ≪ n, where k is the number of neighbors per node in kNN graph and n is the number of
nodes in the graph. Moreover, the RRA algorithm produces a graph that only removes the highest singular components and preserves most of the important spectral information, as empirically shown in Figure 5.
To further confirm that our RRA method produces a graph with much higher quality than the lowrank graph generated by truncated SVD, we compare the accuracy of GCN-SVD with that of GCNRRA. As shown in Table 9, GCN-RRA consistently outperforms GCN-SVD with accuracy improvement up to 15.08%, which indicates that the important spectral information that RRA preserves indeed largely improves the adversarial accuracy.

Review summaries:
This paper proposes GARNET, a spectral approach to depend adversarial attacks on graph structure. GARNET consists of three steps, low rank approximation of adjacency matrix, adaptive filtering on node signals and label propagation. All the 3 steps of GARNET achieve low computation complexity and thus can be applied to large graphs. Extensive experiments on both homophily and heterophily graphs show that GARNET achieve significant accuracy improvements compared with baselines, when the structural perturbation on graphs are stronger. 

The paper proposes a reduced-rank and sparse approximation method to purify the graph structure for better robustness against adversarial graph attacks. The approximation is accelerated through spectral embedding and sparsification. Moreover, adaptive graph filter and label propagation are considered for further improvement on low homophily graphs.  

This paper proposes a spectral approach towards robust and scalable graph learning, namely GARNET. There are three main components inspired by handling low-homophily graphs in GARNET: low rank and sparse approximation of the adversarial graph, a variant of spectral GNN with an adaptive filter, and label propagation with special interest to the learned filter. GARNET is claimed to be nearly-linear so that it can be scaled to very huge graphs. Experiments against both targeted and untargeted attacks under the poison setting over a collection of graph benchmark datasets demonstrate that GARNET could increase the adversarial accuracy more than state-of-the-art defending methods.