GARNET: A Spectral Approach to Robust and Scalable Graph Neural Networks
Authors: Chenhui Deng
Xiuyu Li
Zhuo Feng
Zhiru Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: graph neural networks
adversarial robustness
low-rank approximation
spectral graph theory

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 $15.17\%$ on homophilic and heterophilic graphs, respectively.

Under review as a conference paper at ICLR 2022
GARNET: A SPECTRAL APPROACH TO ROBUST AND SCALABLE GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) have been increasingly deployed in various appli- cations that involve learning on non-Euclidean data. However, recent studies show that GNNs vulnerable to graph adversarial attacks. Although there are several defense methods to improve GNN adversarial robustness, they fail to perform well low homophily graphs. In addition, few of those defense models can scale large graphs due to their high computational complexity and memory usage. In this paper, we propose GARNET, scalable spectral method boost the adver- sarial robustness of GNN models for both homophilic and heterophilic graphs. GARNET first computes reduced-rank yet sparse approximation of the adver- sarial 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 la- bel 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 GAR- NET increases adversarial accuracy over state-of-the-an GNN (defense) models by up to 9.96% and 18.06% on homophilic and heterophilic graphs, respectively.
INTRODUCTION
Recent years have witnessed surge of interest in graph neural networks (GNNs), which incorporate both graph structure and node/edge attributes to produce oow-dimesioonal embedding vectors that maximally preserve graph structural information (Hamilton) (020). GNNs have achieved promis- ing 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 unnoticeable way, can easily fool GNN models and drastically degrade their accuracy in downstream tasks (c.g.. node classification) (Zigner al. 2018 Zügner & Gü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 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 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 (220)). Although such approaches can successfully improve GNN robustness on high-homophily graphs, they may fail on homphhlyp (i.e., heterophily) graphs (Zhu et al. 2020

---

Under review as a conference paper at ICLR 2022
In this paper, we propose GARNET, 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 learn- ing, and (3) adaptive label propagation. The reduced-rank approximation kernel first performs trun- cated SVD on graph adjacency matrix to obtain a few dominant singular values and their correspond- ing 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 polynomial graph filter whose coefficients are trainable; the learned graph filter can adapt to the homophillc/hheerophiiie 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 well two low- www-homophily datasets: Chameleon and Squirrel, under strong graph ad- versarial attacks such as Nettack (Zügner et al.) 2018) and Metattack (Zügner & Günneemann, (219)) 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 vdvesaaiial attacks. Exploiting the proposed reduced-rank approx- imation scheme allows GARNET to effectively filter out the noises potentially caused by adversarial attacks the spectral domain. This immediately leads to substantial improvement (up to 18. 18.06%) of adversarial accuracy when comparing with the state-of-the-. 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 per-
formance achieved on 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 con- ducted experiments on the ogbn-products dataset that contains 2 million nodes and 60 million edges, which is over 100x larger than the largest adversarial graph ever considered in the prior arts
2 RELATED WORK
GNNs have received an increasing amount of attention in recent years due to its ability of learning on non- 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 al. 2018). The most popular graph adver- sarial attacks fall into the following two categories: (1) targeted attack, (2) untargeted attack. The targeted attacks attempt to mislead a GNN model to produce wrong prediction on target sample (e.g., node), while the untargeted attacks strive to degrade the overall accuracy of GNN model for the whole graph data set. Dai al. (2018) first formulate the targeted attack as a combinatorial op- timization problem and leverages reinforcement learning to insert/delete edges such that the target node is misclassified. Ziügner et al. (2018) propose another targeted attack called Nettack, which produces an adversarial graph by maximizing the training loss of GNNs. Zügner & Günnemann (2119) further introduce Metattack, an untargeted attack that treats the graph as hyperparameter and uses meta-grate eeta-gradients 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 (per- turb graph after GNN training). As shown by Zhu et al. (202T), the poison setting is typically
2

---

Under review as a conference paper at ICLR 2022
more challenging 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 ad adversarial defenses attempt to enhance GNN performance the perturbed graphs gener- ated 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 ad- versarial attacks. Jiin et al.] (2020) propose Pro-GNN that adopts 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 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.
3
OUR APPROACH
Figure D 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-neighhor graph algorithms (Baglama & Reichel| 22055] Malkov & Yashunin 2018). The second phase (adaptive filter learning) is the only phase that involves training, which outputs learned graph filter that adapt the ho- mophillchheterophilii properties of the underlying graph. The last phase (adaptive label propaga- tion) 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.
Phase 1: Reduced-Rank Approximation
Phase 2: Adaptive Filter Learning
Node wt train label Adversarial edge
Learned Adaptive Filter
Node wi Learnad Embedding
Grr pno
Truncated SVD
ANN Graph
Phase 3: Adaptive Label Propagation
Spectall
Figure I: An overview of the three major phases of GARNET.
3.1 REDUCED-RANT APPROXIMATION (PHASE 1)
The adjacency matrices of many real-world graphs (c.g., social network and biological network) are naturally low rank and sparse, as the nodes typically tend to form communities and have 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 communi- ties (Zügner et al. 2018 Zügner& & Gü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 Metat- tack) 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
3

---

Under review as a conference paper at ICLR 2022
Consequently, 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 et al. (2020) reconstruct graph that only preserves the low-rank components of its spectrum to mitigate the effects of adversarial attacks, via performing truncated SVD on the adjaceney matrix. Specifically, given a graph adjacency matrix A Rax" the rank-r approximated adjacency matrix can be obtained via truncated SVD: Á UΣV", where Σ E IR""" is a diagonal matrix consisting of r largest singular values of A. U E Raxr and V E 1axx contain the corresponding left and right singular vectors, respectively.
However, the reconstructed low-rank adjacency matrix Á has two key issues: (1) Å is typically a dense matrix with O(n²) nonzero elements, which may result in prohibitively expensive storage as well as GNN training, where n represents number of nodes (Entezari et al. 2020; Din et al. 2020). Thus, existing low-rank approximation methods are not scalable to large graphs; (2) Due to the high computational cost of SVD, Á is typically obtained by only leveraging top singular values and singular vectors, where is a relatively small number (e.g., 50). Consequently, the rank of Å 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 Á on the fly. More concretely, instead of directly computing Á = UEVT, we can compute A row by row: A.,. = U,, Once we obtain A can sparsify it by setting A., 0 if Å. 5 and A., As, otherwise, where 8 is a hyperparameter to control the sparsity. In this way, we only need to store dense vector A., at a time and the final adjacency matrix Á is sparse. Although the space complexity is reduced to Omm), where m denotes the number of non-zero elements in Á, this sparsification method still has quadratic time complexity for computing Å. To tackle this issue, in this work a nearly-linear complexity algorithm for constructing a reduced-rank yet sparse matrix À is proposed by exploiting the following connection between matrix sparsification and spectral graph emhedding.
Definition 1. Given the top r smallest eigenvalues Å1, A2, Ap and their corresponding eigenvec-
fors U1 12 .... Dr of normalized graph Laplacian matrix Lnorm = - D AD- 1, where I and A are the identity matrix and graph adjacency matrix, respectively, and D is diagonal matrix of node degrees, the weighted spectral embedding matrix is defined as:
def VII
Xr 1r
whose i-th row V1, is the weighted spectral embedding of the corresponding i-th node in the graph. Theorem 1. Given a normalized graph adjacency matrix Anorm = D AD- of an undirected graph, let Å be the rank-r approximation of Anorm via truncated SVD. If the top dominant eigenvalues of Anorm non-negative, then A corresponds to the dot product score between the weighted spectral embeddings of node and j.
Theorem I 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 ing edges to be pruned (sparsified) from the graph. Unlike traditional spectral graph embedding methods that utilize the first Laplacian eigenpairs to construct spectral embedding matrix, we ex- ploit 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 A leveraging efficient eigensolvers in O(r(E)) time to construct the weighted spectral embeddings (Baglama & Reichell 2005); next, the embedding results are then used to construct 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 6, 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 0(1) log (V))
capture graph spectral (low-rank) information, thereby identify-
4

---

Under review as a conference paper at ICLR 2022
complexity and thus can scale to very large graphs (Malkov & Yashunin 2018 poduced-rank graph if its adjacency matrix is obtained via the proposed reduced- rank approximation method. As a result, we can obtain reduced- rank and sparse graph in O(r El + [V] log VI) time.
We say graph is
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 EEteeari et al. (2220), 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 A..]show, shows the truncated SVD-based method aggressively reduces graph rank 50, which is two orders of magnitude smaller than the rank of input graph. In contrast, our reduced-ram method only removes the highest singular components, while retaining most of important spectral information. As a result, our reduced-rank approximation kernel leads to significant accuracy improvement over the SVDD-based low-rank approximation. More details are available in Appendices A.
3.2 ADAPTIVE FILTER LEARNING (PHASE 2)
Most existing GNN defense models (implicitly) assume the underlying graph is homophilic, im- plying 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 consequence, existing defense methods may not be robust against graph adversarial attacks heterophilic graphs. To address this limitation, we adopt the concept of learning a polynomial graph filter that can adapt graph homo/heterophily (NT et al., 2020) Chien et al., 2021), and apply on the adversarial graphs. Specifically, given a graph and its node attribute matrix X, our graph filter learning process works as follows:
X = MMM(()
Z =
so sof fooor
EG
(3)
P=0
where can be either normalized adjacency matrix Anorm D 1 AD- or normalized Lapla- cian matrix Lnorm = I Anorm. Co. Co 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 co. CI...., Cp enable the polynomial graph filter gp gP(F)) = Enz Cp FP in Equation to adapt to a homo/heterophilic graph.
Lemma 1 (Chien et al. (2021)). Assume the graph G is connected and |cpl S 1 Vp E 10, P}. Let F to be the normalized adjacency matrix F D AAD If 2 0 Vp (0, 1, ..., P), Ep-osp = 1, and 3p/ > O such that cy' > O, then (F)F) is a low-pass filter. Also, if cp = (-a)*tat (0,11 and P is large enough, then (F) is high-pass filter.
Intuitively, Lemma | indicates that for homophilic graph the filter coefficients tend to be positive, whereas for a heterophilic graph both positive and negative coefficients can be observed. Conse- quently, (r(F) can be learned serve as a low-pass (high-pass) graph filter filter node inter- mediate embeddings X over the homophilic (heterophilic) graph, such that nearby nodes will have similar (dissimilar) output embeddings. Thus, a natural idea for developing robust GNN model on both homophilic and heterophilic graphs 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., 202T). 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 clean graph and that the corresponding reduced-rank graph.
Let Actean Andv and Ar represent the normalized adjacency matrices of clean graph, the corresponding adversarial graph, and the rank-r approximated adversarial graph, re- spectively. Also let art1 denote the (r + 1--th largest singular value of Andu- Assume the spectral
Theorem 2.
5

---

Under review as a conference paper at ICLR 2022
norm of graph adversarial perturbation is upper bounded by constant i.e,, | Aadull2 1
Given a polynomial graph filter (r(F) Ep=o CpFP, we have:
l1gp(Actean) - gp ( (A) - Σ plcpl (E 0r+1)
(4)
p=1
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, 0y+1 within the range of [0, 1]
since Aadv is normalized. We further set P & 10 and enforce Σp lcpl = 1 when learning the adaptive filter to tighten the upper bound. As result, Theorem 2 indicates that the performance of the clean graph.
polynomial filter on the reduced-rank graph will be similar to its performance 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 (F) = Σp= Fp 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 (Castelló et al.] 2019). where the computation of a graph filter gr (F) ) is distributed onto multiple GPUs based on the index p that indicates the p-th term in gr This way, can dramatically reduce the memory usage per GPU, thereby allowing the adaptive filter learning process to scale to large graphs with millions of nodes.
3.3 ADAPTIVE LABEL PROPAGATION (PHASE 3)
Once the trained graph filter (F) - Ep c; F" is obtained, we further leverage it to enhance the quality of node embeddings Z in Equation 3 by correlating residue errors and propagating node la- bels, 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 low-pass graph filter, which assumes the underlying graph to homophilic. In con- trast, our approach works effectively for both homophilic and heterophilic graphs by exploiting adaptive filter learning. Specifically, let Nr, and Ny be the set of nodes that are labelled and unla- belled, respectively. Given the one-hot label matrix Y E R=*e, where and denote the numbers of nodes and classes, respectively. we define the residue error matrix by R E Raxe such that RN,- ZNz YN, and RiG 0. Our goal is to optimize the following objective:
R= arg min H RI + XT (I (
(5)
H
where \ is regularization parameter. The first term in Equation 5 enfoores 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 gp (F), whereas the C&S method adopts a simple (non-adaptive) smoothing scheme. Note that there is training involved in this phase and R can be iteratively computed by R a (F) R (1 R. in O()) time due to the sparsity of F, where a = T+x node embeddings 2 by Zs, As suggested in Huang et al. (200)), we further refine 2 by substituting Z for R in Equation to diffuse the label information over the graph, thereby obtaining the corresponding optimizer Z. Subsequently, 2 will be utilized as the final node embeddings in the following label prediction step.
A_ and m is the number of edges in graph. After obtaining R, we update the
Ys, and ZNe = ZNu + B R where 3 is a hyperparameter.
4 EXPERIMENTS
We have conducted comparative evaluation of GARNET against state-of-the-art defense GNN mod- els on both homophilic and heterophilic datasets, under targeted attack (Nettack) (Zügner et al.) 2018) and tar-tareeted attack (Mettack) (Zügner & Günnemann 2019) with different perturbation budgets. Besides, we further evaluate the scalability of GARNET on rngnn-rroducts which is over 100 larger than the datasets used in Entezari et al. (2020): Zhang & Zitnik (2020); et al. (2020) Finally, we perform ablation studies to understand the effectiveness of each kernel in GARNET.

---

Under review as a conference paper at ICLR 2022
Table 1: Averaged node classification accuracy (%) + std under targeted attack (Nettack) with different perturbation ratio - We denote the evaluated dataset by its name with the number of perturbations (e.g., Cora-O means the clean Cora graph and Cora-1 denotes there adversarial edge perturbation target node). We bold and underline the first and second highest accuracy, respectively. OOM means out of memory.
Dutaset
GCN
GPRGNN
GPRSVD-CS
GCNSVD
GNNGuard
Pro-GNN
GARNET
Cora-0
80.96 = 0.95
84,33 2.05
81,68 + 1.78
72.65 + 2.29
83.37 + 2.46
81.54 + 1.21
82.77 + 1.89
Cora-1
75.06 = 0.81
81.68 2.18
79.36
1 2.23
70.36 = 1.63
78.31 + 1.60
82.65 + 0.59
82 1.95
Cora-2
70.60 1.81
74.34
76.26
2.34
65.66 2.76
72.77
2.06
77.83
1.10
78.55
2.11
Coru-3
69.04 3.31
70.96
70.90
3.88
61.20 1,93
68.19 2.48
71.08 +: 1.20
79.40 +: 1.35
Cora-4
61.69 1.48
65.90
66.51
+ 3.27
57.34 + 3.46
62.41 + 2.65
67.83 + 1.87
72.77 + 2.16
Cora-5
55.66 1.95
62.89 + 1.95
63.52
+: 3.27
55.30 +: 2.25
57.59 +: 2.46
65.38 + 1.65
71.45 +: 2.73
Citeseer-O
81.59
0.82
82.38 + 0.82
82.38
+ 0.50
80.95 + 1.23
80.32 1.34
1.34
82.89 + 1.53
83.86 + 1.07
Citeseer-1
79.04 L.80
0.88
81.38
0.50
75.23 2.67
78.57 + 2.14
81.74 0.79
83.49 1.14
Citescer-2
76.19 3.89
0.82 80,32
80.27 + 0.67
00.15 = 2.29
73.18 + 4.56
80.15 + 0.71
80.63 + 1.46
3iteseer-3
62.54 = 4.50
77.46 + 1.16
78. 95 + 0.74
58.89 = 5.28
64.38 + 5.89
78.36 + 2.56
76.67 2.25
Citescer-4
57.30 = 3.62
73.33
3.16
73.95
+ 0.75
GL.74 7.96
59.05 - 5.96
73.98 +: 1.28
72. 22.22 2.28
Citeseer-5
51.75 2.50
67.80
3.77
67.95 1.98
2.77 45.07
54.13 + 8.05
6.36 67.46
68. 19 + 4.03
Pubmed-0
87.26 0.51
90.05
+ 0.73
OOM
87.03
0.48
89.57 + 0.28
OOM
90.99 +: 0.52
Pubmed-1
86.29 0.68
30.30 0.54
OOM
$4.46 = 0.28
87.84 + 0.51
OOM
90.91 + 0.47
Pubmed-2
83.17 0.67
87.42 + 0.28
OOM
82.68 0.46
85.00 + 0.59
OOM
90.75 + 0.55
Pubmed-3
81.13 0.53
84.46 0.53
OOM
81.34
0.68
81.29 0.90
OOM
90.70 + 0.37
Pubmed-4
75.48 0.52
81.72 + 0.72
OOM
82.41 0.54
76.07 0.77
0OM
90.11 + 0.57
Pubmed-5
66.67 1.34
76.99 + 1.16
0OM
79.36 0.48
69.89 + 1.18
OOM
89.52 + 0.45
Experimental Setup. The details of datasets are available in Appendix A.9.2 We evaluate unvacci- nated GCN (Kipf & Welling, 2016) and GPRGNN (Chien et al. (021). Moreover, we choose as the defense baselines three state-of-the tfte-oof-hhe-ar vaccinated GNN models: GCNSVD (Entezari et al., 2020). GNNGuard (Zhang & Zitnik 2020), and Pro-GNN Jin et al.) (2020). Besides, we further evaluate 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 hyperparameterrs for larger adversarial perturbations. We further show hyperparameter settings of GARNET and hardware information in Appendix (A.9
4.1 DEFENSE ON HOMOPHILIC GRAPHS
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 few structure (edge) perturbations. We choose the same set of target nodes as in (Jin et al.) (020). We report the averaged accuracy over 10 runs Cora, Citeseer, and Pubmed datasets with adversarial perturbations varying from to 5 per target node. Table T 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 to 5 on Pubmed, while the accuracy of baseline defense methods drops 4.9% ~ 17.95%, indicating that GARNET is indeed more robust 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 much higher quality of low-rank graph than the SVD-based graph by preserving more useful spectrum information as explained in Section 3.]
Defense against non-targeted attack. We further evaluate model robustness against a strong non- targeted 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 f0%, 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 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
7

---

Under review as a conference paper at ICLR 2022
Table 2: Averaged node classification accuracy (%) + std under non-targeted attack (Metattack) with different perturbation ratio We denote the evaluated dataset by its name with the perturbation ratio (e.g., Cora-O means the clean Cora graph and Cora- 10 denotes there are 10% adversarial edges). We bold and underline the first and second highest accuracy, respectively. OOM means out of memory.
Dataset
GCN
GPRGINN
GPRSVI-CS
GCNSVD
GINGuarrd
Pro-GINN
GARNET
Cora-O
83.35 +: 0.66
85.05 + 0.42
82.61 + 0.54
73.86 = 0.53
84.45 + 0.63
85.56 0.36
82.67 1.89
Cora-10
69.50 + 1.46
80.37 + 0.65
81.08
0.52
69.45 = 0.09
09.35 + 2.29
77.90 +: 0.69
82.17 = 0.69
Cora-20
56.28 +: 1.19
74:27 + 2.11
78.50
2.20
1.16 62.44
64.17 +: 2.00
72.28 +: 1.67
81.34 + 0.79
Citeszer-O
72.15 + 0.75
74.18 + 0.55
73.09 + 0.89
68.33 + 1.17
72.09 + 1.09
73.29 + 1.49
74.82 + 1.07
Citeseer-10
67.38 +: 1.56
72.13
71.75
+: 0.85
68.29 =: 0.70
67.22 2.60
72.50 +: 0.53
74.25 +: 0.63
Citeseer-20
57.21 +: 1.26
68.41
62.33 + 1.08
68.47 = 0.72
55,30 +: 2.23
71.10 + 0.72
72.03 = 0.50
Pubmed-0
87.16 +: 0.09
87.35 + 0.13
O0M
84.53 # 0.08
85,38 + 0.17
OOM
86,86 + 0.57
Pubmed-10 10
81.16 + 0.13
85.52 0.14
0OM
84.56 + 0.10
77.45 + 0.20
OOM
86.24 + 0.20
Pubmed-20
77.20 0.27
8
0OM
84 = 0.08
71.73 + 0.32
OOM
85.69 = 0.26
4.2 DEFENSE ON HETEROPHILIC GRAPHS
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 re- port the adversarial accuracy under Metattack 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, model designed handle het- erophilic graphs. Our approach, on the other hand, consistently outperforms all defense baselines by 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 base- lines 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 base- lines drops 2. 2.10% 18.12%. Thus, GARNET also robust against graph adversarial attacks on heterophilic graphs.
Table 3: Averaged node classification accuracy (%) = std under non- non-ttagettd attack (Metattack) with different perturbation ratio We denote the evaluated dataset by its name with the perturbation ratio (e.g.. Chameleon-0 means the clean Chameleon graph and Chameleon-10 denotes there are 10% adversarial edges). We bold and underline the first and second highest accuracy, respectively.
Dataset
GCN
GPRGNN
GPRSVD-CS
GCNSVD
GNNGuard
Pro-GNN
GARNET
Chameleon-0 0
58.16 + 1.29
61.36 + 1.00
47.29 + 1.63
45.08 + 0.70
58.01 1.57
47.37 + 1.93
61.11 : 2.46
Chameleon-10 10
43.47 + 0.78
57.55
1.26
47.07
1.11
41.95 0.39
41.75 + 0.93
38.39 1.35
60.96 1.22
Chameleon-20
39.58 1 1,56
53.20
1 0.88
45.12 = 1.34
40.90 = 0.77
39.89 + 1.34
32,24 : 1.53
59.96 + 0.84
Squirrel-0
37.45 + 0.76
39.51 + 1.61
31.36 = 1.87
31.17 = 0.47
37
4 0.56
32 32.02 2.11
43.43 + 1.14
Squirel-10
26.96
38.27
28.25
1.66
25.83 0.32
27.03
0.54
26.03 1.23
42.62
1.09
Squircl-20
23.91 + 0.45
35.22 1.20
23.91 = 1.40
1 = 0.00
23.69 + 0.59
20.09 3.55
41.97 = 1.02
4.3 DEFENSE ON LARGE GRAPHS
Table 4: Averaged accuracy (%) + std and run time under non-targeted attack (DICE) with 60% perturbation ratio We bold the highest accuracy. O0M indicates out of memory.
ogbn-arxiv
ogbn-products
Method
Cleun
Adversurial
Time (mins)
Clean
Adversarial
Time (mins)
GNNGuard
68.22 + 1.80
46 +: 2.71
22.21
74.82 + 0.11
66.69 = 0.12
567.11
GARNET
70.23 = 0.45
62.89 22.89-2 = 0.22
1.08 (20x)
81.65 + 0.11
75.61 + 0.14
31.27 (18x)
To demonstrate the scalability of GARNET on large graphs, we evaluate the robustness of GARNET Given that existing strongest attacks (Nettack and
on the attacked ogbn-arxiv 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
8

---

Under review as a conference paper at ICLR 2022
Pro-GNN
GPRSVD-CS
Ada_ Filter
Reduced_ Rank
Ada Filter
Reduced_ Rank + Ado_ _Fiter + ada__abel__ PPro (GARNET)
Adversarial Accuracy
Cora
Adversarial Accuracy
Pubmed
Adversarial Accuracy
Squirrel
90
80
40
85
30
80
65
20
5
Perturbations per Target Node
Perturbations per Target Node
Perturbations per Target Node
Figure 2: Comparisons of different kernel combinations in GARNET on Cora, Pubmed, and Squirrel datasets under Nettack We denote the reduced-rante approximation kernel, adaptive filter learning kernel, and adaptive label propagation kernel by Reduced_Rank Fiteri and Ada Ada respectively. Besides, we choose ProGNN and GPRSVD-CS (GPRGNN SVD + C&S) as strong baselines, whose curves Pubmed missing due out-of-memory.
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 Pro- GNN) out of memory on these two datasets. Table reports the accuracy and run time large graphs under DICE attack, which shows GARNET outperforms GNNGuard by a margin of 2.43% and 8.92% on ogbn-arxiv and oghn- boobn-produtts, respectively, with around 20x runtime speedup. We further show the run time per kernel of GARNET in Appendix A.5
4.4 ABALATION ANALYSIS ON GARNET KERNELS
To study the effectiivneess 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 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 ON-GGNN homophilic datasets, while it largely outperforms Pro-GNN on the heterophilic dataset, which shows the adap- tive filter works effectively both homophilic and heterophilic graphs. Figure further shows that adding the reduced-rank approximation kernel results in a much more graceful accuracy degrada- tion 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 per target node on Pubmed. This implies that our reduced-rank approx-
the perturbation from imation kernel can effectively remove the high-rank adversarial properties from the input graph, allowing GARNET to be more resistant to graph adversarial attacks. is worth noting that exist- ing SVD-based low-rank methods (e.g., GPRSVD-CS performs much worse than our reduced-rank method, which lies the fact that our reduced-rank kernel preserves much more important spec- trum 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 effectively exploit the label information for further enhancing the quality of node representations under adversarial attacks.
5 CONCLUSIONS
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-ther -ott--arttt-ttttt defense models on homophilic and heterophilic graphs under both targeted and non-targeted adversarial attacks.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
The GARNET source code is available at ggihub..om/ggggarr//geaaaam proof's for Theorems and 2 in Appendices A.1 and A.2 respectively. Moreover, the proof for Lemma D is available in Chien et al. (2021). Finally, the details of all datasets used in our experi- ments are available in Appendix A.9
Besides, we provide our
REFERENCES
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-gentt cext-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pp. 2623-2631, 2019.
James Baglama and Lothar Reichel. Augmented implicitly restarted lanczos bidiagonalization meth-
ods. SIAM Journal on Scientific Computing, 27(1):19 2005.
Sergio Casas, Cole Gulino, Renjie Liao, and Raquel Urtasun. Spagnn: Spatially-aware graph neu- ral networks for relational behavior forecasting from sensor data. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 9491-9497. IEEE, 2020.
Adrián Castelló, Manuel F Dolz, Enrique S Quintana-Orti, and José Duato. Analysis of model parallelism for distributed neural networks. In Proceedings of the 26th European MPI Users' Group Meeting, pp. 1-10, 2019.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL
https: htttps://ppenevvies net wwaee//forommmddnn]111.
F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack graph structured data, International conference on machine learning, pp. 1115-1124. PMLR, 2018.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 169-177. 2020.
William Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00633 2020.
Qian Huang. Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010. 13993, 2020.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 66-74, 2020.
learning for robust graph neural networks. In Proceedings the
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 160..0060000207,, 2016.
Ron Levie, Elvin Isufi, and Gitta Kutyniok. On the transferability of spectral graph filters. In 2019 13th International conference on Sampling Theory and Applications (SampTA), pp. 1-5, IEEE, 2019.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? arXiv preprint arXiv:2 arXiv:2/06.066 0614,,,4, 2021.
10

---

Under review as a conference paper at ICLR 2022
Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(())822488) 836, 2018.
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, et al. A graph placement methodol- ogy for fast chip design. Nature, 594(7862)207-2122 2021.
Hoang NT, Takanori Maehara, and Tsuyoshi Murata. Stacked graph filter. arXiv:2011.10988 2020.
arXiv preprint
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnabb01, 2021.
Andrew W Senior, Richard Evans, John Jumper, James Kirkpatrick, Laurent Sifre. Tim Green, Chongli Qin, Augustin Žídek, Alexander WR Nelson, Alex Bridgland, et al. Improved protein structure prediction using potentials from deep learning. Nature, 577((7922:770- 2020.
David I Shuman, Sunil K. Narang, Pascal Frossard. Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. JEEE Signal Processing Magazine, 30(3):83 98, 2013. doi: 11.11199//11 109//M0P.201..222351111
Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S Yu, Lifang He, and Bo Li. Adversarial attack and defense on graph data: A survey. arXiv preprint arXiv:1812.10528, 2018.
Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, 2(2):139-147, 2018
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples on graph data: Deep insights into attack and defense. arXiv preprint 10XX:v:9033001// 2019.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-superrised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983, 2018.
Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. arXiv preprint TTti::20060811443 2020.
Ke Zhou, Hongyuan Zha, and Le Song. Learning social infectivity in sparse low-rank networks using multi-dimennional hawkes processes. In Artificial Intelligence and Statistics, pp. 641-649, PMLR, 2013.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. arXiv preprint arXiv:2006. 1468, 2020.
Jiong Zhu, Junchen Jin, Michael T Schaub, and Danai Koutra. Improving robustness of graph neural networks with heterophily-inspired designs. arXiv preprint arXiv:2106.07767, 2021.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. arXiv preprint arXiv: 192.02190..08412. 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2847-2856, 2018.
11

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 PROOF FOR THEOREM 1
Proof. As the graph is undirected, we can perform eigendecomposition on both Anorm and Lnorm- Let A A and og, 1, 2, ..., 7' denote the smallest eigenvalues of Lnorms largest eigenvalues of A Anor. and largest singular values of Anorm. respectively. Since Anorm and morm share the same set of eigenvectors while their eigenvalues satisfy: Å 1 X i 1, ..,,...T T. Moreover, since we assume that the r largest magnitude eigenvalues of Anorm are non- negative, we have o2
Lnorm. A
{u 'n 1,2, r. Thus, we have:
A1
VV 10 Url
11, Uy!
1 - X
A1
U11 ..., Url
U1 ...y 1rl
Xr
01
=[U1,.., Ur]
U1, ... Uy
Or
=
Since V is defined as the weighted spectral embedding of node and Å., V.,V sponds the dot product score between the weighted spectral embeddings of node and j, which completes the proof of the theorem.
d: A corre-
A.2 PROOF FOR THEOREM 2
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-1AD= 3
and Anorm is the low-rank approximation of Anorm via truncated SVD, we have || S and A || <
The proof for Lamma trivial since the spectrum of Anorm and Anorm lies in [-1, 1] Chung 1997).
Lemma 3. Given two matricies M and N such that | la I and ||N]|2 S 1, we have M Nº M|| 2| for every p 2 0.
The proof for Lamma is available in Levie et al. (019))
Next, we formally prove Theorem 2 in the following:
Proof.
P =
P Σ
(or(AAcaa)--o (eg((A))l (gr())))))g)())))
Σ
Cp
AP
clean
p=0
p=0
P
|| cp (A"
AA
clean
p=1
Σ
cpl Aotean
AP'l2
p=1
12

---

Under review as a conference paper at ICLR 2022
P cpl Aclan Arll2
p=1
p cpl (llAdean Aadull2 || Ar112)
p=1
p llpl + +r+1)
The second inequality above is based on Lemmas using the triangle inequality.
2 and 3
while the third inequality is derived by
A.3 GARNET ALGORITHM AND COMPLEXITY ANALYSIS
Algorithm 1: GARNET algorithm
Input: Adjacency matrix E IR=,,, node feature matrix X E R node label matrix Y E R' truncated svd rank r; kNN graph k; polynomial filter degree P; eтror correction scale (; train node set N1; test node set Nu; label propagation iteration regularization parameter a
Output: Node embedding matrix 2 E Ruxe
/* Phasel: reduced-rank approximation
*
S, V truncated_ssu(AA, rank = r);
Á = KNN S
/ Phase2 adaptive filter learning for 1...epochs do
X = MLP(X);
Z Softmax ( c APX)
loss Cross Lotropy Z, Y); losswbackward)):
end
/ :hase3:adaptive label propagation
RN ZNz YNNi
RNG 0;
1 R:
12 for = 0...s do
R 1 a p C + +1 a))
13
14 end
is ZN
YNU:
16 ZNU ZNu + BRu
17 2 = Ż;
18 for 0...8 do
1111 a P C +(1 +1-a))
19
20 end
13

---

Under review as a conference paper at ICLR 2022
The algorithm of GARNET is shown in Algorithm I We further analyze the total complexity of GARNET on a graph g = (V,8). Specifically, as we mention in Section 3.1] the complex- ity of the truncated SVD with rank and approximate kNN graph construction O(r (81) and ((1V] [V), respectively. Thus, the complexity of the reduced-rank approximation kernel is O(r [8| + log (V). Moreover, the complexity of computing adaptive filter is (ce|El), where c is the column dimension of X, since we can leverage the sparsity of the graph for computing AX. Similarly, the complexity of adaptive label propagation kernel (ss [E]), where is the number of steps to iteratively compute R and ğ. and P denotes the polynomial degree. Conse- quently, the overall complexity of GARNET is O((r + c c &P) |&| [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 0(V1 log [V]) nodes in total and
each node connects to a fixed number of neighbors. Thus, it has 0(V) log [V + (El) space com- plexity, where | 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,
do not explicitly form the graph filter (P(F) Ep Fp Instead,
iteratively left-multipl 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 correspond edges in the reduced-
rank (kNN) graph and the node embedding matrix is in the shape of [V] x d. both adaptive filter learning and lahel propagation kernels have [ + (V]) space complexity. As a result, the overall space complexity of GARNET is O((E) (d + log [V]) [V]).
A.4 ACCURACY ON HETEROPHILIC DATASETS UNDER NETTACK
Table 5: Averaged node classification accuracy (%) + std under targeted attack (Nettack) with different perturbation ratio - We denote the evaluated dataset by its name with the number of perturbations (e.g.. Chameleon-O means the clean Chameleon graph and Chameleon- denotes there is 1 adversarial edge perturbation per target node). We bold and underline the first and second highest accuracy, respectively.
Dataset
GCN
GPRGNN
GPRSVD-CS
GCNSVD
GNNGuard
Pro-GNN
GARNET
Chameleon-0
70.66 +: 1.65
62.12 3.01
0.52
74.15 = 1.26
60.66 3.11
72.89 2.65
Chameleon-1
69.81 +: 1.34
71.02 1:2:1..00 1.57
61.34 4.99
67.93 0.56
71.82 +: 1.86
59.44
3.13
72 68
1.89
Chameleon-2
68.51 +: 2.37
70.71
+ 1.12
61.09
+: 2,80
0.77
67.32
2.36
3.14
72.20 + 2.31
Chameleon-3
65.73 1: 2.78
70.30 +: 1.28
60.98
0.99
66,22 2.37
52.56
72.17 4 2.07
Chameleon-4
63.04 +: 3.98
69.87
1.29
3.331
0.624
2.77
51.95:22.59
72.00 02.06:11
2.94
Chameleon-5
57.92 + 3.69
66.26 + 1.71
2.86 60.37
0.78 67.44
63.42 + 3.45
51.10 + 2.58
71.83 + 2.11
Squirrel-0
25.46 +: 1.96
41.36 +:87
32.98
2.36
31.73 = 1.18
2:33
20.45 = 4.52
44.91
1.53
Squirrel-1 1
25.09 + 2.97
41.27
+ 3.16
32.63
0.87
31.00
1.11
23.46 + 2.53
19.82 4.23
43.55
1.79
Squirrel-2
25.00
2.14
32.05
1.05
30.99
1.03
22.09 + 1.36
18.82 4.17
2.35
Squirrel-3
24.73 + 1.76
10.98 +: 2.72
32,00
1.66
30.18 = 1.67
22,00 + 1.36
17.36
16.32000 4.06
44.18
2.26
Squirrel-4
24.09 + 1.15
2.82 40.25
1.38 31.20
31.45+
30.00 0.91
21.18 + 1.91
16.96 + 4.16
43.73
1.62
Squirrel-5
23.72
2.36
1.84
29.54 2.51
1.8G 21.09
16.27
3.78
43.64
1.53
As shown in Table 5] the four vaccinated baseline models, i.e., GPRSVD-CS, GCNSVD, GN- NGuard, and Pro-GNN, only achieve comparable 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.
A.S RUN TIME PER KERNEL IN GARNET
Table 6 reports the run time of each sub-kernel in GARNET on Cora, Pubmed, ogbn-arxiv, and ogbn-prodie 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
14

---

Under review as a conference paper at ICLR 2022
Table 6: Run time (secs) of each kernel in GARNET- We decompose the reduced-rank approxima- tion kernel into truncated SVD (TSVD) and approximate kNN graph construction (AKNN) steps. In addition, denote the adaptive filter learning kernel and adaptive label propagation kernel by Ada Filter, and Ada Label Prop. respectively.
Dataset
TSVD
AKNN
Ada_Filter
Ada_Label_
Total
Cora
0.09
0.10
0.76
0.05
1.00
Pubmed
0.25
0.72
1.60
0.05
2.62
ogbn-arxiv
6.04
17.92
40.49
0.23
64.68
ogbn-products
368.37
363.32
1139.46
5.21
1876.36
graph construction less than 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
A.6 ABLATION STUDY KNN GRAPH CONSTRUCTION
Cora
Citeseer
Pubmed
Metattack w/ 10% Perturbation
Mettack w/ 20% Perturbation
Adversarial Accuracy
Adversarial Accuracy
85
85
80
80
75
75
70
10 20 30 40 50 60 70 80
90100
10
20
30
40
50 60 70 80 90100
k
k
Figure 3: Ablation Study on kNN Graph.
To evaluate the sensitivity of GARNET to approximate kNN (AKNN) graph construction, we show the adversarial accuracy of GARNET with different & values for constructing AKNN graphs in Figure 3 which indicates that the accuracy of GARNET does not change too much when varying I value within the range of 30, 100). especially on the Cora and Pubmed datasets. Hence, we recommend choosing = 50 80 for the AKNN graph construction.
A.7 GRAPH RANK UNDER ADVERSARIAL ATTACKS
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 perturba- tion ratios (0% to 25%). For the results showing that other graph adversarial attacks increase graph ranks, we refer to Figure 3 in Entezari al. (2020) and Figure 1 in Jin et al. (2020).
A.8 GRAPH RANK COMPARISON
We compute the rank of each adversarial graph under Metattack with the perturbation ratio vary- ing from 5% to 25%, and compare the result with its corresponding two low-rank graphs obtained via reduced-rank approximation and truncated SVD (TSVD) respectively. Note that the
15

---

Under review as a conference paper at ICLR 2022
Graph Rank under Metattack
Cora
Citeseer
Pubmed
Chameleon
Rank Growth Rate (%)
Perturbations Ratio (%)
Figure 4: Graph rank growth under Metattack.
Input Adversarial Graph
Redduced-Ranke Graph
TSVD Graph
Rank of Adjacency Matrix
Cora
Rank of Adjacency Matrix
Chameleon
2000
1000
1000
500
15
5
20 Perturbation Ratio (%)
25
Perturbation Ratio (%)
Figure 5: Comparisons of the ranks input adversarial graph, our reduced-rank graph, and TSVD-
based low-rank graph on Cora and Chameleon datasets.
same r 50 largest singular values and their corresponding singular vectors for our reduced-rank kernel and TSVD. Figure shows that the TSVD-based method aggressively reduces the graph rank 50 and thus loses lots useful spectral information. In contrast, our reduced- -aack graph only re- moves high-rank adversarial graph properties while keeping rest of meaningful spectral information, demonstrating the effectiveness of the proposed reduced-rank approximation scheme.
A.9 EXPERIMENTAL SETUP
A.9.1 HYPERPARAMETER SETTINGS OF GARNET
We show the hyperparameters of the reduced-rank approximation kernel and the adaptive filter learn- ing kernel on different datasets under Nettack (1 perturbation per node), Metattack (10% perturba- tion ratio), and DICE (60% perturbation ratio) in Table For the adaptive label propagation kernel, we do not manually tune hyperparameters but instead leverage Optuna (Akiba et al. 2019) to opti- mize the hyperparameters such the scale 3 for error correction based the validation set, since this kernel is fast to compute. We refer to cethub..om//nnnganeeee ters used in the adaptive label propagation kernel. We all GNN training with full batch.
for details of hyperparame-
A.9.2 DATASET DETAILS
Table shows the statistics of the datasets used our experiments. We follow Zhu et al. (2020) compute the homophily score per dataset (lower score means more heterophilic). As in Tin et al.
16

---

Under review as a conference paper at ICLR 2022
Table 7: Summary hyperparameters in GARNET Apart from the notations h, and ô men- tioned in Section 3.1] we denote polynomial degree, learning rate, number of epochs, weight decay, dropout, and coethcient initialization in the adaptive filter learning kernel by P. Ir, epochs, wd, dp, and c, respectively.
Reduced-Rant Approximation
Adaptive Filter Learning
Dataset
r
P
epochs
wd
dp
Cora-Nettack
50
0.05
10
0.01
0.0005
0.5
0.9
Cora-Metattack
50
50
0.05
10
0.01
50
0.0005
0.5
0.9
Citeseer-Nelian
50
30
0.003
10
0.01
50
0.0005
0.5
0.9
50
0.05
10
0,0005
0.5
Pubmed-Nette Nettack
50
80
0.05
10
0.01
150
0.0005
0.5
0.9
Pubmed-Metattack
Metattack
50
80
0.05
10
0.01
150
0.0005
0.5
0.9
Chateleon-Nettack
50
60
0.003
10
0.05
300
0.0
0.5
0.9
Chameleon-Metatanne
50
0.003
10
0.05
300
0.0
0.5
0.9
Cquirrel-Nettaces
50
50
0.003
10
0.1
300
0.0
0.5
0.3
Squirrel-Metatack
Metattack
50
50
0.003
10
0.1
300
0.0
0.5
0.3
ogbn-an ogbn-arxiv-DDe arXiv-DICE
50
0.00003
10
0.0
Dybh-Products-DIC
50
50
0.00003
5
0.01
300
0.0
0.0
0.9
Table 8: Statistics of datasets used in our experiments.
Dataset
Type
Homophily Score
Nodes
Edges
Classes
Features
Cora Citeseer
Homophily
0.80
069
1,433
Homophily
0.74
110
668
6
3, 703
Pubmed
Homophily
0.80
19. 717
44.
3
500
Chamelcon
Heterophily
0.23
2. 277
62, 792
5
2,325
Squireel
Hcterophily
0.22
5, 201
396, 846
5
0,9
ogbn-arss Sobnnarxiv
Homophily
0.66
169, 343
166, 243
40
ogbn-prooe bebn-prodduct
Homophily
0.81
2, 449, 029
61, 859, 140
47
2020), we extract the largest connected components of the original Cora, Citeseer, and Pubmed datasets (Yang al. 2016) for the adversarial evaluation, with the same train/validation/test split. For Chamelcon and Squirrel (Rozemberczki et al., (22I), 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 ogon-arxiv and ogbn-products.
In addition, we follow Jin et al. (020)) for the selection of target nodes 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 non- targeted attacks (i.e., Metattack and DICE), we choose nodes in the test set as target nodes for all datasets.
A.9.3 HARDWARE INFORMATION
For ogbn-arxiv and ogbn-products, Silver 4214 CPU (8 cores 2.20GHz) and 4 NVIDIA RTX A6000 GPUs (48 GB memory per GPU). For the rest of the datasets, conduct all experiments 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).
experiments Linux machine with Intel Xeon
A.10 ABLATION STUDY SPECTRAL EMBEDDING
To show that the spectral embedding used in reduced-rank approximation kernel not only con- tributes to low-rank approximation but also captures key structural information per node, we com- pare spectral embedding method, which 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-
top 50 largest singular values and corresponding
17

---

Under review as a conference paper at ICLR 2022
Vanilla Spectral Embedding
SC-based Spectral Embeedding (ours)
Cora
Citeseer
Pubmed
Adversarial Accuracy
Adversarial Accuracy
Adversarial Accuracy
91
80
90
75
75
70
70
89
65
88
2
3
2
Perturbations per Target Node
Perturbations Target Node
Perturbations per Target Node
Figure 6: GARNET accuracy comparisons of using vanilla spectral embedding and singular com-
ponents (SC) based spectral embedding the reduced-rank approximation kernel.
lar component (SC) based spectral embedding outperforms the vanilla spectral embedding in most cases. The underlying reason 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 al. 2013).
A.11 REDUCED- BRACKE APPROXIMATION vs. TRUNCATED SVD
Algorithm 2: Reduced-rank approximation algorithm (Ours)
Input: Adjacency matrix A E nkn,, kNN graph k; sparsification threshold 5
Output:
Reduced-rank adjacency matrix Á E R
/* Obtain singular components via TSVD
21 U, S, V truncated svd(A, rank 50);
/* Node spectral embedding
* /
X U
/ Approximate kNN graph construction
*
23 Å KNN graph(X,, k);
/ Drop edges with node similarity scores lower than
24 A spar siuusiiiiation A,8);
A Algorithm 3: Truncated SVD based low-rank approximation algorithm Adjacency matrix A E Ruxn
Input:
Reduced-rank adjacency matrix À E RRx= 25 U, U.S, S, V = truncated A, rank = 50);
Output:
Á USVT:
Algorithms and 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 À produced by TSVD method has two issues: (1) Á is typically dense matrix corresponding to (nearly) complete graph, which cannot scale large graphs; (2) A is 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 which loses too much important spectral information.
In contrast, our RRA algorithm only involves a sparse adjacency matrix, whose density is roughly with & n. where is the number of neighbors per node in kNN graph and is the number of
18

---

Under review as a conference paper at ICLR 2022
nodes in the graph. Moreover, the RRA algorithm produces graph that only removes the highest singular components and preserves most of the important spectral information, as empirically shown in Figure 5
Table 9: Averaged node classification accuracy (%) = std under targeted attack (Nettack) with different perturbation ratio We denote the evaluated dataset by its name with the number of perturbations (e.g., Cora-1 denotes there is 1 adversarial edge perturbation per target node).
Dataset
GCN-SVD
GCN-RRA
Cora-I
70.36 = 1.63
79.75 = 2.35
Cora-2
65.66 = 2.76
79.69 = 1.50
Cora-3
61.20 = 1.93
74.42 = 2.06
Cora-4
57.34 = 3.46
60.60 = 2.67
Cora-5
55.30 2.25
59.04 = 2.05
Citeseer-
75.23 = 2.67
77.30 = 2.80
Citeseer-2
60.15 = 2.29
75.23 = 2.14
Citeseer-3
58.89 5.28
59.84 = 33.4
Citeseer-4
51.74 = 7.96
57.94 = 5.66
Citeseer-5
45.07 = 2.77
53.18 = 3.61
Pubmed-1
84.46 = 0.28
89.03 = 0.68
Pubmed-2
82.68 0.46
88.92 = 0.45
Pubmed-3
81.34 = 0.68
88.50 = 0.45
Pubmed-4
82.41 = 0.54
88.44 = 0.64
Pubmed-5
79.56 = 0.48
88.12 = 0.86
To further confirm that our RRA method produces graph with much higher quality than the low- rank graph generated by truncated SVD, we compare the accuracy of GCN-SVD with that of GCN- RRA. As shown in Table GCN-RRA consistently outperforms GCN-SVD with accuracy improve- ment up to 15.08%, which indicates that the important spectral information that RRA preserves indeed largely improves the adversarial accuracy.
19


Reviews:
[{"review_id": "x5Vh0M38EWd", "reviewer": "Reviewer_EL8y", "summary": "", "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 paper is easy to follow with clear motivation and is well written. The design of GARNET is clearly motivated by handling the low-homophily graphs.\n- Due to the common assumption on the homophily of underlying graphs, it is of great importance to go beyond these datasets and propose a universal solution to different types of graphs.\n- The acceleration of TSVD is remarkable and the scalability of the proposed method is clearly a strong contribution to the research on the robustness of GNNs.\n\nWeaknesses:\n- The main concern of mine is the contribution towards scalability is a little bit over-claimed. In the major advantages of GARNET, the authors claim that GARNET has a nearly-linear runtime/space complexity. However, the total space complexity of GARNET is not analyzed, which could result in a dense matrix after the adaptive filter learning then is not nearly linear anymore. \n- Another concern is that the proposed approach is heuristic and can be easily broken by an adaptive attacker (see e.g. [1] for a detailed discussion). An adaptive attacker can easily circumvent them by changing their attack to account for the defense. For example, it is relatively straightforward to add an additional term in the computation of Nettack's scores that discourages adversarial edges that have a large impact on the high-rank spectrum. Furthermore, if the attacker knows what proposed defense is used, they can specifically target the largest singular values to potentially cause even more damage.\n- For experiments, the experimental setup should be more specific for better reproducibility since no code is available for examination. Several questions include: what package do the authors use to conduct truncated SVD? I have experience in having the top eigen-pairs of the whole OGB graph with scipy, which takes hours to finish. Thus the run time that is less than 7 minutes is interesting to me. For the training on ogbn-arxiv and ogbn-products, do the authors use sampling techniques or just training with full batch? The difference of evaluation between small graphs and OGB graphs should also be specified in the detail of settings.\n\n[1] On adaptive attacks to adversarial example defenses, NeurIPS 2020\n", "summary_of_the_paper": "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.\nExperiments 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.\n", "summary_of_the_review": "My concerns are mainly from three aspects:\n- The complexity analysis is vague while it is one of the main contributions of this work. \n- No adaptive attacker is evaluated.\n- The reproducibility of empirical evaluation is a little weak.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "FjjJnVS0Oly", "reviewer": "Reviewer_HF71", "summary": "", "questions": "", "limitations": "", "rating": 3, "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\n1. The paper introduces an efficient reduced-rank approximation method to purify the graph structure that is scalable to large graphs. \n\n2. It provides theoretical justification for the matrix sparsification method.\n\n3. The paper presents lots of experiments to demonstrate the robustness of the proposed method in different settings, such as targeted and untargeted attacks, homophilic and heterophilic graphs, small and large graphs, etc. \n\n\n## Weaknesses\n\n1. The proposed GARNET combines several techniques proposed in previous works such as Low-rank approximation in GCN-SVD and ProGNN, adaptive filter learning in GPR-GNN, as well as correct and smooth in C&S method. Overall, the novelty of the proposed method is quite limited, and the contribution of this paper is unclear.\n\n2. The comparison with the baseline models doesn’t seem to be fair. From my understanding, although the baseline methods (such as Pro-GNN), use classic 2-layer GCN as the backbone model, according to their formulation, their ideas can be generally applied to more advanced GNN models such as APPNP and GPRGNN as well. In essence, GARNET in this paper chooses a more advanced and deeper backbone model that adopts adaptive filter as in GPRGNN and adaptive label propagation as in C&S to compare with the baselines which only use the basic GCN as their backbone models. This doesn’t seem to be a fair comparison since the depth (e.g., number of propagation layers) and filter design typically have significant impacts on the robust performance. Therefore, the performance improvement is not convincing.\n\n3. As far as I am concerned, the low-rank approximation idea is essentially similar to existing works and this paper proposes a more efficient way to achieve this. Therefore, regardless of the efficiency and scalability, the robust performance should be similar to existing works if appropriate backbone models are chosen in the comparison. It is better to have a discussion on this.\n\n4. From the ablation study in Section 4.4, Figure 2 only compares GARNET and GNNGuard. However, GNNGuard is less relevant in this context and the performance is much worse than Pro-GNN in this setting as showed in Table 2 or Table 3. It would be more interesting to see how the low-rank approximation in this work improves over Pro-GNN instead of GNNGuard.\n\n\n", "summary_of_the_paper": "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.\n\n", "summary_of_the_review": "Overall, the contributions of the paper are unclear and the novelty seems to be limited. In addition, the comparison and ablation study in the experiment is not totally convincing. I would like to suggest a rejection. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "18lcLgWQNG", "reviewer": "Reviewer_F9Qe", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n+ The paper is clearly written. All the technical steps of GARNET are easy to understand. \n+ The paper presents extensive empirical evaluation on the proposed framework. The datasets cover both homophily and heterophily graphs, and from small to large scales. \n\n\nWeaknesses\n\n- Although the three main steps of GARNET are all reasonable, they lack some technical significance. For example, \n    - The low rank approximation step follows a standard algorithm and the description over-complicates the algorithm. Although the authors call the reconstructed graph a \"k-NN\" graph, it is indeed just obtained by row-wise preserving the largest elements in the rank-r approximate adjacency matrix -- according to Thm 1, the similarity score used by k-NN is exactly the element value of the rank-r adj matrix. The spectral embedding matrix is also well-known (e.g., used in spectral clustering), and the authors are not really utilizing much property of the spectral embedding except deriving the low-rank approximation. \n    - The adaptive filtering step is also not novel. Multiple existing works follow similar form of such filtering (e.g., SIGN [a]). \n    - Theorem 2 does not seem useful, since the upper bound is way too loose. If we compare the upper bound with the scale of the original perturbation, then the derived upper bound is even orders of magnitude larger. If the upper bound is achieved, then it would tell us that adaptive filtering can enlarge the effect of perturbation. In addition, the upper bound grows quadratically with filtering depth P, indicating that heterophily graphs could be problematic (from theoretic perspective). \n- While the experiments show significant accuracy gains, further clarification could make the improvements more convincing. \n    - In Table 2, 3 and 4, we can see that GARNET achieves higher accuracy even on the clean graph. I suppose this is due to the adaptive filtering step. However, since adaptive filtering is a known design, it would be better to add one unvaccinated baseline model following Eq 2 and 3 in these tables. \n    - From Fig 2, it is clear that reducing the rank is the primary reason for successful defense. If this is the case, then it is not clear why similar rank-reduction based method, GCNSVD, achieves much lower performance than GARNET in Tables 2 and 3. More explicitly, since in Fig 2, GNNGuard achieves much lower accuracy than GARNET, I would imagine GCNSVD to achieve much higher accuracy than GNNGuard and slightly lower accuracy than GARNET in Tables 2 and 3. Yet this does not seem to be the case. \n\n\n[a]: SIGN: Scalable Inception Graph Neural Networks, 2020.", "summary_of_the_paper": "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. ", "summary_of_the_review": "I think the paper is lower than the acceptance threshold due to the lack of technical significance and question in empirical evaluation, as detailed above. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a method to change the graph structure for better robustness against adversarial attacks. The reviewers commend the authors for a clearly written paper and promising results. Several reviewers expressed concerns about experimental validation (specifically, comparison to truncated SVD and choice of baselines), complexity, and novelty. The rebuttal and follow-up discussion alleviated some of the concerns, but the reviewers still have outstanding issues, therefore the AC does not recommend accepting the paper.
Decision: Reject