# 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 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.

1 INTRODUCTION

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) (Z¨ugner et al., 2018; Z¨ugner & G¨unnemann, 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 (Z¨ugner et al., 2018) and Metattack (Z¨ugner & G¨unnemann, 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 approx-_
imation 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.

2 RELATED WORK

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. Z¨ugner et al. (2018) propose another targeted attack called Nettack, which
produces an adversarial graph by maximizing the training loss of GNNs. Z¨ugner & G¨unnemann
(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 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 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.

3 OUR APPROACH

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.

|Col1|Col2|Col3|Col4|Col5|
|---|---|---|---|---|
||||||
||Sp Emb|ectr edd|al ings||
||||||
||||||


|Phase 1: Reduced-Rank Approximation 2 5 1 4 7, :: N Ado vd ee sw a/ rt ir aa i en la gb eel r l d 3 6 Truncated SVD kNN 2 5 Graph EmS bp ee dc dtr ia nl g s 1 4 7 3 6|Phase 2: Adaptive Filter Learning 2 5 2 5 1 4 7 1 4 7 3 6 3 6 AdaL pe ta ivr en e Fd il ter $ Nod Ee m w be/ dL de ia nr gned ! = #$!%! !"# Phase 3: Adaptive Label Propagation !!,# 2 !!,$ !%,$5 !%,& 2 5 2 5 1 4 7 1 4 7 1 4 7 !(,# 3 !(,$ 6 !',& 3 6 3 6|Phase 2: Adaptive Filter Learning 2 5 2 5 1 4 7 1 4 7 3 6 3 6 AdaL pe ta ivr en e Fd il ter $ Nod Ee m w be/ dL de ia nr gned ! = #$!%! !"#|
|---|---|---|
|||Phase 3: Adaptive Label Propagation !!,# 2 !!,$ !%,$5 !%,& 2 5 2 5 1 4 7 1 4 7 1 4 7 !(,# 3 !(,$ 6 !',& 3 6 3 6|



Figure 1: An overview of the three major phases of GARNET.

3.1 REDUCED-RANK APPROXIMATION (PHASE 1)

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 (Z¨ugner et al., 2018; Z¨ugner & G¨unnemann, 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 ∈_** R[n][×][n], the rank-r approximated adjacency matrix can be obtained via truncated SVD: **_A[ˆ] =_**
**_U_** ΣV _[T]_, where Σ ∈ R[r][×][r] is a diagonal matrix consisting of r largest singular values of A. U ∈
R[n][×][r] and V ∈ R[n][×][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(n[2]) 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 eigenvec-**
_tors v1, v2, ..., vr of normalized graph Laplacian matrix Lnorm = I −_ **_D[−]_** [1]2 AD[−] 2[1], 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:_

def
**_V_** = 1 _λ1_ **_v1, ...,_** 1 _λr_ **_vr_** _,_ (1)

_|_ _−_ _|_ _|_ _−_ _|_

_whose i-th row Vi,: is the weighted spectral embeddinghp_ p of the correspondingi _i-th node in the graph._

**Theorem 1. Given a normalized graph adjacency matrix Anorm = D[−]** 2[1] AD[−] 2[1] 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.

3.2 ADAPTIVE FILTER LEARNING (PHASE 2)

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)

_P_

**_Z = softmax(_** _cpF_ _[p][ ˆ]X)_ (3)

_p=0_

X


where F can be either a normalized adjacency matrix Anorm = D[−] 2[1] AD[−] 2[1] or normalized Lapla
cian 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=0_ _[c][p][F][ p][ in Equation 3 to adapt to a homo/heterophilic graph.]_

_LetLemma 1 F to be the normalized adjacency matrix (Chien et al. (2021))[P][P]_ **. Assume the graph F = G D is connected and[−]** [1]2 AD[−] 2[1] . If c |pcp| ≤01 ∀pp ∈{00,, 1 1, ..., P, ..., P _}.,_

_P_ _≥_ _∀_ _∈{_ _}_
_p=0[c][p][ = 1][, and][ ∃][p][′][ >][ 0][ such that][ c][p][′][ >][ 0][, then][ g][p][(][F][ )][ is a low-pass filter. Also, if][ c][p][ =]_
( _α)[k], α_ (0, 1) and P is large enough, then gp(F ) is a high-pass filter.
P− _∈_

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, re-_
_spectively. 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=0_ _[c][p][F][ p][, we have:]_

_P_

_gP (Aclean)_ _gP (A[P]r[P])_ 2 _p_ _cp_ (ϵ + σr+1) (4)
_∥_ _−_ _∥_ _≤_ _p=1_ _|_ _|_

X

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=0_
adaptive filter to tighten the upper bound. As a result, Theorem 2 indicates that the performance of ≤ _[|][c][p][|][ = 1][ when learning the]_
a polynomial filter on the reduced-rank graph will be similar to its performance on the clean graph.

[P][P]
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=0_ _[c][p][F][ 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 (Castell´[P][P] o 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.

3.3 ADAPTIVE LABEL PROPAGATION (PHASE 3)

Once the trained graph filter gP[∗] [(][F][ ) =][ P]p[P]=0 _[c]p[∗][F][ 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 ∈ R[n][×][c], where n and c denote the numbers
of nodes and classes, respectively, we define the residue error matrix by R ∈ R[n][×][c] such that
**_RNL = ZNL −_** **_YNL and RNU = 0. Our goal is to optimize the following objective:_**

**_Rˆ = arg minH_** _∥H −_ **_R∥F[2]_** [+][ λ][ Tr(][H] _[T][ (][I][ −]_ _P [1]_ _[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 gP[∗] [(][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 byof F, where α = 1+λλ [and][ m]R[ˆ] _[t][ is the number of edges in graph. After obtaining][+1]_ = α _P[1]_ _[g]P[∗]_ [(][F][ ) ˆ]R[t] + (1 − _α)R in O(m) time due to the sparsity[ ˆ]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._**

4 EXPERIMENTS

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) (Z¨ugner et al.,
2018) and non-targeted attack (Mettack) (Z¨ugner & G¨unnemann, 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.


-----

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-0 means the clean Cora graph and Cora-1 denotes there is 1 adversarial
edge perturbation per target node). We bold and underline the first and second highest accuracy,

|respectivel|ly. OOM means out of memory.|
|---|---|
|Dataset|GCN GPRGNN GPRSVD-CS GCNSVD GNNGuard Pro-GNN GARNET|
|Cora-0 Cora-1 Cora-2 Cora-3 Cora-4 Cora-5|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 75.06 ± 0.81 81.68 ± 2.18 79.36 ± 2.23 70.36 ± 1.63 78.31 ± 1.60 82.65 ± 0.59 82.17 ± 1.95 70.60 ± 1.81 74.34 ± 2.41 76.26 ± 2.34 65.66 ± 2.76 72.77 ± 2.06 77.83 ± 1.10 78.55 ± 2.11 69.04 ± 3.31 70.96 ± 2.00 70.90 ± 3.89 61.20 ± 1.93 68.19 ± 2.48 71.08 ± 1.20 79.40 ± 1.35 61.69 ± 1.48 65.90 ± 1.61 65.51 ± 3.27 57.34 ± 3.46 62.41 ± 2.65 67.83 ± 1.87 72.77 ± 2.16 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-0 81.59 ± 0.82 82.38 ± 0.82 82.38 ± 0.50 80.95 ± 1.23 80.32 ± 1.34 82.89 ± 1.53 83.86 ± 1.07 Citeseer-1 79.04 ± 1.80 80.15 ± 0.84 81.38 ± 0.50 75.23 ± 2.67 78.57 ± 2.14 81.74 ± 0.79 83.49 ± 1.14 Citeseer-2 76.19 ± 3.89 80.32 ± 0.82 80.27 ± 0.67 60.15 ± 2.29 73.18 ± 4.56 80.15 ± 0.71 80.63 ± 1.46 Citeseer-3 62.54 ± 4.50 77.46 ± 1.46 78.95 ± 0.74 58.89 ± 5.28 64.38 ± 5.89 78.36 ± 2.56 76.67 ± 2.25 Citeseer-4 57.30 ± 3.62 73.33 ± 3.16 73.95 ± 0.75 51.74 ± 7.96 59.05 ± 5.96 73.98 ± 1.28 72.22 ± 2.28 Citeseer-5 51.75 ± 2.50 67.89 ± 3.74 67.95 ± 1.98 45.07 ± 2.77 54.13 ± 8.05 67.46 ± 6.36 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 89.30 ± 0.54 OOM 84.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 OOM 90.11 ± 0.57 Pubmed-5 66.67 ± 1.34 76.99 ± 1.16 OOM 79.56 ± 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., 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.

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 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 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 {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.


-----

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-0 means the clean Cora graph and Cora-10 denotes there are 10% adversarial edges). We

|bold and un|nderline the first and second highest accuracy, respectively. OOM means out of memory.|
|---|---|
|Dataset|GCN GPRGNN GPRSVD-CS GCNSVD GNNGuard Pro-GNN GARNET|
|Cora-0 Cora-10 Cora-20|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 69.50 ± 1.46 80.37 ± 0.65 81.08 ± 0.52 69.45 ± 0.69 69.35 ± 2.29 77.90 ± 0.69 82.17 ± 0.69 56.28 ± 1.19 74.27 ± 2.11 78.50 ± 2.20 62.44 ± 1.16 64.17 ± 2.00 72.28 ± 1.67 81.34 ± 0.79|
|Citeseer-0 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 ± 0.61 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.44 ± 0.90 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 OOM 84.53 ± 0.08 85.38 ± 0.17 OOM 86.86 ± 0.57 Pubmed-10 81.16 ± 0.13 85.52 ± 0.14 OOM 84.56 ± 0.10 77.45 ± 0.20 OOM 86.24 ± 0.20 Pubmed-20 77.20 ± 0.27 84.18 ± 0.15 OOM 84.30 ± 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 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.

Table 3: 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., Chameleon-0 means the clean Chameleon graph and Chameleon-10 denotes there are

|10% adversar|rial edges). We bold and underline the first and second highest accuracy, respectively.|
|---|---|
|Dataset|GCN GPRGNN GPRSVD-CS GCNSVD GNNGuard Pro-GNN GARNET|
|Chameleon-0 Chameleon-10 Chameleon-20|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 43.47 ± 0.78 57.55 ± 1.26 47.07 ± 1.21 41.95 ± 0.39 41.75 ± 0.93 38.39 ± 1.35 60.96 ± 1.22 39.58 ± 1.56 53.20 ± 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.64 31.36 ± 1.87 31.17 ± 0.47 37.46 ± 0.56 32.02 ± 2.11 43.43 ± 1.14 Squirrel-10 26.96 ± 0.30 38.27 ± 0.83 28.25 ± 1.66 25.83 ± 0.32 27.03 ± 0.54 26.03 ± 1.23 42.62 ± 1.09 Squirrel-20 23.94 ± 0.45 35.22 ± 1.20 23.91 ± 1.40 14.90 ± 0.60 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. OOM indicates out of memory.

**ogbn-arxiv** **ogbn-products**

**Method** Clean Adversarial Time (mins) Clean Adversarial Time (mins)

GNNGuardGARNET **7068..2223 ± ± 1 0..8045** **6260..4689 ± ± 2 0..7122** 1.08 (2022.21×) **8174..8265 ± ± 0 0..1111** **7566..6961 ± ± 0 0..1214** 31.56727 (18.11×)

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


-----

|Col1|Col2|Col3|Col4|Col5|Col6|
|---|---|---|---|---|---|
|||||||
|||||||





Pro-GNN GPRSVD-CS Ada_Filter
Reduced_Rank + Ada_Filter Reduced_Rank + Ada_Filter + Ada_Label_Prop (GARNET)

Cora Pubmed Squirrel

90

80 40

75 85

30

70 80

65 20

75

Adversarial Accuracy Adversarial Accuracy Adversarial Accuracy

1 2 3 4 5 1 2 3 4 5 1 2 3 4 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-rank approximation kernel, adaptive filter learning
kernel, and adaptive label propagation kernel by Reduced Rank, Ada Filter, and Ada Label Prop,
respectively. Besides, we choose ProGNN and GPRSVD-CS (GPRGNN + SVD + C&S) as strong
baselines, whose curves on Pubmed are missing due to 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 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.

4.4 ABALATION ANALYSIS ON GARNET KERNELS

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.

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-the-art defense models on
homophilic and heterophilic graphs under both targeted and non-targeted adversarial attacks.


-----

REPRODUCIBILITY STATEMENT

[The GARNET source code is available at github.com/gnngarnet/garnet. Besides, we provide our](https://github.com/gnngarnet/garnet)
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.

REFERENCES

Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna:
A next-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 methods. SIAM Journal on Scientific Computing, 27(1):19–42, 2005.

Sergio Casas, Cole Gulino, Renjie Liao, and Raquel Urtasun. Spagnn: Spatially-aware graph neural networks for relational behavior forecasting from sensor data. In 2020 IEEE International
_Conference on Robotics and Automation (ICRA), pp. 9491–9497. IEEE, 2020._

Adri´an Castell´o, Manuel F Dolz, Enrique S Quintana-Ort´ı, and Jos´e 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 Milenkovic. Adaptive universal generalized pagerank
graph neural network. In International Conference on Learning Representations, 2021. URL
[https://openreview.net/forum?id=n6jl7fLxrP.](https://openreview.net/forum?id=n6jl7fLxrP)

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 on
graph structured data. In International conference on machine learning, pp. 1115–1124. PMLR,
2018.

Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you
need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th
_International Conference on Web Search and Data Mining, pp. 169–177, 2020._

William L 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 on graphs. arXiv
_preprint arXiv:2005.00687, 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
learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International
_Conference on Knowledge Discovery & Data Mining, pp. 66–74, 2020._

Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 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:2106.06134, 2021.


-----

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(4):824–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 methodology for fast chip design. Nature, 594(7862):207–212, 2021.

Hoang NT, Takanori Maehara, and Tsuyoshi Murata. Stacked graph filter. _arXiv preprint_
_arXiv:2011.10988, 2020._

Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal
_of Complex Networks, 9(2):cnab014, 2021._

Andrew W Senior, Richard Evans, John Jumper, James Kirkpatrick, Laurent Sifre, Tim Green,
Chongli Qin, Augustin Z´[ˇ] ıdek, Alexander WR Nelson, Alex Bridgland, et al. Improved protein
structure prediction using potentials from deep learning. Nature, 577(7792):706–710, 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. IEEE Signal Processing Magazine, 30(3):83–98, 2013.
doi: 10.1109/MSP.2012.2235192.

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 a 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 arXiv:1903.01610,
2019.

Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised 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. Gnnguard: Defending graph neural networks against adversarial
attacks. arXiv preprint arXiv:2006.08149, 2020.

Ke Zhou, Hongyuan Zha, and Le Song. Learning social infectivity in sparse low-rank networks
using multi-dimensional 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.11468, 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¨ugner and Stephan G¨unnemann. Adversarial attacks on graph neural networks via meta
learning. arXiv preprint arXiv:1902.08412, 2019.

Daniel Z¨ugner, Amir Akbarnejad, and Stephan G¨unnemann. Adversarial attacks on neural networks
for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge
_Discovery & Data Mining, pp. 2847–2856, 2018._


-----

A APPENDIX

A.1 PROOF FOR THEOREM 1

_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:

1 _λ1_

[ˆ] _|_ _−_ _|_

**_V V_** _[T]_ = [v1, ..., vr]  ...  [v1, ..., vr][T]

1 _λr_

 _|_ _−_ _|_
 

_λ[ˆ]1_

= [v1, ..., vr]  ... 

 _λ[ˆ]r_ 
 
  [[][v][1][, ...,][ v][r][]][T]

_σ1_

= [v1, ..., vr]  ...  [v1, ..., vr][T]

_σr_

 
 

= A[ˆ]

Since Vi,: is defined as the weighted spectral embedding of node i and **_A[ˆ]i,j = Vi,:Vj,[T]:[,][ ˆ]Ai,j corre-_**
sponds to the dot product score between the weighted spectral embeddings of node i and j, which
completes the proof of the theorem.

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[−]** 2[1] AD[−] 2[1],

_and_ **_A[ˆ]norm is the low-rank approximation of Anorm via truncated SVD, we have ∥Anorm∥2 ≤_** 1
_and_ **_Anorm_** 2 1
_∥_ [ˆ] _∥_ _≤_

The proof for Lamma 2 is trivial since the spectrum of Anorm and **_A[ˆ]norm lies in [−1, 1] (Chung,_**
1997).
**_NLemma 3.[p]∥2 ≤_** _p Given two matricies∥M −_ **_N_** _∥2 for every M p ≥ and0._ **_N such that ∥M_** _∥2 ≤_ 1 and ∥N _∥2 ≤_ 1, we have ∥M _[p]_ _−_

The proof for Lamma 3 is available in Levie et al. (2019).

Next, we formally prove Theorem 2 in the following:

_Proof._


_cpA[p]clean_
_p=0_ _[−]_

X


_cpA[p]r[∥][2]_
_p=0_

X


_∥gP (Aclean) −_ _gP (Ar)∥2 = ∥_


_cp(A[p]clean_ _r[)][∥][2]_
_p=1_ _∥_ _[−]_ **_[A][p]_**

X

_P_

_cp_ **_A[p]clean_** _r[∥][2]_
_p=1_ _|_ _| ∥_ _[−]_ **_[A][p]_**

X


-----

_p_ _cp_ **_Aclean_** **_Ar_** 2

_≤_ _p=1_ _|_ _| ∥_ _−_ _∥_

X

_P_

_≤_ _p=1_ _p |cp| (∥Aclean −_ **_Aadv∥2 + ∥Aadv −_** **_Ar∥2)_**

X

_P_

_p_ _cp_ (ϵ + σr+1)

_≤_ _|_ _|_

_p=1_

X

The second inequality above is based on Lemmas 2 and 3, while the third inequality is derived by
using the triangle inequality.

A.3 GARNET ALGORITHM AND COMPLEXITY ANALYSIS

**Algorithm 1: GARNET algorithm**

**Input: Adjacency matrix A ∈** R[n][×][n]; node feature matrix X ∈ R[n][×][d]; node
label matrix Y ∈ R[n][×][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[ˆ] ∈_** R[n][×][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]p=0_** _[c][p][ ˜]A[p][ ˆ]X);_

**6** _loss = CrossEntropyLoss(Z, Y );_

**7** _loss.backward();_

**8 end**

/* Phase3:adaptive label propagation *[/]

**109 R RNNLU = 0 = Z;NL −** **_YNL;_**

**11** **_R[ˆ]_** [0] = R;

**12 for i = 0...s do**

**13** **_Rˆ_** _[i][+1]_ = _P[α]_ _Pp=0_ _[c]p[∗]A[˜][p][ ˆ]R[i]_ + (1 − _α)R;_

**14 end**

P

**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[α]_ _Pp=0_ _[c]p[∗]A[˜][p][ ˆ]Z_ _[i]_ + (1 − _α) Z[˜];_

**20 end**

P


-----

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. Conse-_**
quently, 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=0_ _[c][p][F][ 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 reduced-[P][P]
rank (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|).

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-0 means the clean Chameleon graph and Chameleon-1 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 Chameleon-1 Chameleon-2 Chameleon-3 Chameleon-4 Chameleon-5|70.66 ± 1.65 71.46 ± 1.92 62.12 ± 3.04 68.29 ± 0.54 74.15 ± 1.26 60.66 ± 3.11 72.89 ± 2.65 69.81 ± 1.34 71.02 ± 1.57 61.34 ± 2.93 67.93 ± 0.56 71.82 ± 1.86 59.44 ± 3.13 72.68 ± 1.89 68.51 ± 2.37 70.71 ± 1.12 61.09 ± 2.80 68.29 ± 0.77 67.32 ± 2.36 56.44 ± 3.13 72.20 ± 2.31 65.73 ± 2.78 70.30 ± 1.28 60.98 ± 2.82 69.15 ± 0.95 66.22 ± 2.37 52.56 ± 3.28 72.17 ± 2.07 63.04 ± 3.98 69.87 ± 1.29 60.85 ± 3.31 70.24 ± 0.60 65.73 ± 2.72 51.95 ± 2.59 72.06 ± 2.94 57.92 ± 3.69 66.26 ± 1.71 60.37 ± 2.86 67.44 ± 0.78 63.42 ± 3.45 51.10 ± 2.58 71.83 ± 2.11|
|Squirrel-0 25.46 ± 1.96 41.36 ± 2.87 32.98 ± 2.36 31.73 ± 1.18 26.09 ± 2.35 20.45 ± 4.52 44.91 ± 1.53 Squirrel-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.20 41.09 ± 2.14 32.05 ± 1.05 30.99 ± 1.03 22.09 ± 1.36 18.82 ± 4.17 44.09 ± 2.35 Squirrel-3 24.73 ± 1.76 40.98 ± 2.72 32.00 ± 1.66 30.18 ± 1.67 22.00 ± 1.36 17.36 ± 4.06 44.18 ± 2.26 Squirrel-4 24.09 ± 1.15 40.25 ± 2.82 31.45 ± 1.38 30.00 ± 0.91 21.18 ± 1.91 16.36 ± 4.16 43.73 ± 1.62 Squirrel-5 23.72 ± 1.09 39.45 ± 2.36 31.20 ± 1.84 29.54 ± 2.51 21.09 ± 1.86 16.27 ± 3.78 43.64 ± 1.53||



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.

A.5 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-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


-----

Table 6: Run time (secs) of each kernel in GARNET— We decompose the reduced-rank approximation kernel into truncated SVD (TSVD) and approximate kNN graph construction (AKNN) steps.
In addition, we 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 Prop 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 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.

A.6 ABLATION STUDY ON KNN GRAPH CONSTRUCTION

Cora Citeseer Pubmed

Metattack w/ 10% Perturbation Mettack w/ 20% Perturbation

85

85

80

80

75

75

70

Adversarial Accuracy Adversarial Accuracy

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 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.

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 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).

A.8 GRAPH RANK COMPARISON

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


-----

Graph Rank under Metattack

|Col1|Cora Citesee|r|Col4|Col5|Col6|Col7|
|---|---|---|---|---|---|---|
||Pubme Chame|d leon|||||
||||||||
||||||||
||||||||
||||||||
||||||||
||||||||


Cora
Citeseer
Pubmed
Chameleon


10 15 20 25

Perturbations Ratio (%)


30

25

20

15

10


Figure 4: Graph rank growth under Metattack.

Input Adversarial Graph Reduced-Rank Graph TSVD Graph

Cora Chameleon

2000

1500

1000

1000

500

0 0

Rank of Adjacency Matrix Rank of Adjacency Matrix

5 10 15 20 25 5 10 15 20 25

Perturbation Ratio (%) Perturbation Ratio (%)


Figure 5: Comparisons of the ranks on input adversarial graph, our reduced-rank graph, and TSVDbased 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 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.

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 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 hyperparame-](https://github.com/gnngarnet/garnet)
ters used in the adaptive label propagation kernel. We run all GNN training with full batch.


A.9.2 DATASET DETAILS

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.


-----

Table 7: Summary of hyperparameters in GARNET— Apart from the notations r, k, and δ mentioned in Section 3.1, we denote polynomial degree, learning rate, number of epochs, weight decay,
dropout, and coefficient initialization in the adaptive filter learning kernel by P, lr, epochs, wd, dp,
and c, respectively.

**Reduced-Rank Approximation** **Adaptive Filter Learning**

**Dataset** _r_ _k_ _δ_ _P_ _lr_ _epochs_ _wd_ _dp_ _c_

Cora-Nettack 50 50 0.05 10 0.01 50 0.0005 0.5 0.9
Cora-Metattack 50 50 0.05 10 0.01 50 0.0005 0.5 0.9
Citeseer-Nettack 50 30 0.003 10 0.01 50 0.0005 0.5 0.9
Citeseer-Metattack 50 60 0.05 10 0.01 50 0.0005 0.5 0.9
Pubmed-Nettack 50 80 0.05 10 0.01 150 0.0005 0.5 0.9
Pubmed-Metattack 50 80 0.05 10 0.01 150 0.0005 0.5 0.9
Chameleon-Nettack 50 60 0.003 10 0.05 300 0.0 0.5 0.9
Chameleon-Metattack 50 60 0.003 10 0.05 300 0.0 0.5 0.9
Squirrel-Nettack 50 50 0.003 10 0.1 300 0.0 0.5 0.3
Squirrel-Metattack 50 50 0.003 10 0.1 300 0.0 0.5 0.3
ogbn-arxiv-DICE 50 50 0.00003 10 0.01 500 0.0 0.0 0.9
ogbn-products-DICE 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 Homophily 0.80 2, 485 5, 069 7 1, 433
Citeseer Homophily 0.74 2, 110 3, 668 6 3, 703
Pubmed Homophily 0.80 19, 717 44, 324 3 500
Chameleon Heterophily 0.23 2, 277 62, 792 5 2, 325
Squirrel Heterophily 0.22 5, 201 396, 846 5 2, 089
ogbn-arxiv Homophily 0.66 169, 343 1, 166, 243 40 128
ogbn-products Homophily 0.81 2, 449, 029 61, 859, 140 47 100

(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.

A.9.3 HARDWARE INFORMATION

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).

A.10 ABLATION STUDY ON SPECTRAL EMBEDDING

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

-----

Vanilla Spectral Embedding SC-based Spectral Embedding (ours)

Cora Citeseer Pubmed

91

80

80

90

75

75

70 70 89

Adversarial Accuracy65 Adversarial Accuracy65 Adversarial Accuracy88

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

Perturbations per Target Node Perturbations per Target Node Perturbations per Target Node


Figure 6: GARNET accuracy comparisons of using vanilla spectral embedding and singular components (SC) based spectral embedding in the reduced-rank approximation kernel.

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).

A.11 REDUCED-RANK APPROXIMATION VS. TRUNCATED SVD

**Algorithm 2: Reduced-rank approximation algorithm (Ours)**

**Input: Adjacency matrix A ∈** R[n][×][n]; kNN graph k; sparsification
threshold δ

**Output: Reduced-rank adjacency matrix** **_A[˜] ∈_** R[n][×][n]

/* Obtain singular components via TSVD *[/]

**21 U** _, S, V_ _[T]_ = truncated svd(A, rank = 50);


/* Node spectral embedding *[/]


**_S;_**


**22 X = U**


/* 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 ∈** R[n][×][n]

**Output: Reduced-rank adjacency matrix** **_A[˜] ∈_** R[n][×][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.

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-1 Cora-2 Cora-3 Cora-4 Cora-5|70.36 1.63 79.75 2.35 ± ± 65.66 2.76 79.69 1.50 ± ± 61.20 1.93 74.42 2.06 ± ± 57.34 3.46 60.60 2.67 ± ± 55.30 2.25 59.04 2.05 ± ±|
|---|---|

|Citeseer-1 Citeseer-2 Citeseer-3 Citeseer-4 Citeseer-5|75.23 2.67 77.30 2.80 ± ± 60.15 2.29 75.23 2.14 ± ± 58.89 5.28 59.84 3.43 ± ± 51.74 7.96 57.94 5.66 ± ± 45.07 2.77 53.18 3.61 ± ±|
|---|---|

|Pubmed-1 Pubmed-2 Pubmed-3 Pubmed-4 Pubmed-5|84.46 0.28 89.03 0.68 ± ± 82.68 0.46 88.92 0.45 ± ± 81.34 0.68 88.50 0.45 ± ± 82.41 0.54 88.44 0.64 ± ± 79.56 0.48 88.12 0.86 ± ±|
|---|---|


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.


-----

