Title: POWER UP! ROBUST GRAPH CONVOLUTIONAL NET-WORK BASED ON GRAPH POWERING

Abstract: Graph convolutional networks (GCNs) are powerful tools for graph-structured data. However, they have been recently shown to be vulnerable to topological attacks. To enhance adversarial robustness, we go beyond spectral graph theory to robust graph theory. By challenging the classical graph Laplacian, we propose a new convolution operator that is provably robust in the spectral domain and is incorporated in the GCN architecture to improve expressivity and interpretability. By extending the original graph to a sequence of graphs, we also propose a robust training paradigm that encourages transferability across graphs that span a range of spatial and spectral characteristics. The proposed approaches are demonstrated in extensive experiments to simultaneously improve performance in both benign and adversarial situations.

1. INTRODUCTION:

Graph convolutional networks (GCNs) are powerful extensions of convolutional neural networks (CNN) to graph-structured data. Recently, GCNs and variants have been applied to a wide range of domains, achieving state-of-the-art performances in social networks (Kipf & Welling, 2017) , traffic prediction (Rahimi et al., 2018) , recommendation systems (Ying et al., 2018) , applied chemistry and biology (Kearnes et al., 2016; Fout et al., 2017) , and natural language processing (Atwood & Towsley, 2016; Hamilton et al., 2017; Bastings et al., 2017; Marcheggiani & Titov, 2017) , just to name a few (Zhou et al., 2018; Wu et al., 2019) .

GCNs belong to a family of spectral methods that deal with spectral representations of graphs (Zhou et al., 2018; Wu et al., 2019) . A fundamental ingredient of GCNs is the graph convolution operation defined by the graph Laplacian in the Fourier domain:

g θ x := ĝθ (L)x, (1) where x ∈ R n is the graph signal on the set of vertices V and ĝθ is a spectral function applied to the graph Laplacian L := D -A (where D and A are the degree matrix and the adjacency matrix, respectively). Because this operation is computational intensive for large graphs and non-spatially localized (Bruna et al., 2014) , early attempts relied on a parameterization with smooth coefficients (Henaff et al., 2015) or a truncated expansion in terms of of Chebyshev polynomials (Hammond et al., 2011) . By further restricting the Chebyshev polynomial order by 2, the approach in (Kipf & Welling, 2017) referred henceforth as the vanilla GCN pushed the state-of-the-art performance of semi-supervised learning. The network has the following layer-wise update rule:

EQUATION

where H (l) is the l-th layer hidden state (with H (1) := X as nodal features), W (l) is the l-th layer weight matrix, ψ is the usual point-wise activation function, and A is the convolution operator chosen to be the degree weighted Laplacian with some slight modifications (Kipf & Welling, 2017) . Subsequent GCN variants have different architectures, but they all share the use of the Laplacian matrix as the convolution operator (Zhou et al., 2018; Wu et al., 2019) .

1.1 WHY NOT GRAPH LAPLACIAN?

Undoubtedly, the Laplacian operator (and its variants, e.g., normalized/powered Laplacian) plays a central role in spectral theory, and is a natural choice for a variety of spectral algorithms such as principal component analysis, clustering and linear embeddings (Chung & Graham, 1997; Belkin & Niyogi, 2002) . So what can be problematic?

From a spatial perspective, GCNs with d layers cannot acquire nodal information beyond its ddistance neighbors; hence, it severely limits its scope of data fusion. Recent works (Lee et al., 2018; Abu-El-Haija et al., 2018; 2019; Wu et al., 2019) alleviated this issue by directly powering the graph Laplacian.

From a spectral perspective, one could demand better spectral properties, given that GCN is fundamentally a particular (yet effective) approximation of the spectral convolution (1). A key desirable property for generic spectral methods is known as "spectral separation," namely the spectrum should comprise a few dominant eigenvalues whose associated eigenvectors reveal the sought structure in the graph. A well-known prototype is the Ramanujan property, for which the second leading eigenvalue of a r-regular graph is no larger than 2 √ r -1, which is also enjoyed asymptotically by random r-regular graphs (Friedman, 2004) and Erdős-Rényi graphs that are not too sparse (Feige & Ofek, 2005) . In a more realistic scenario, consider the stochastic block model (SBM), which attempts to capture the essence of many networks, including social graphs, citation graphs, and even brain networks (Holland et al., 1983) .

Definition 1 (Simplified stochastic block model). The graph G with n nodes is drawn under SBM(n, k, a intra , a inter ) if the nodes are evenly and randomly partitioned into k communities, and nodes i and j are connected with probability a intra /n ∈ [0, 1] if they belong to the same community, and a inter /n ∈ [0, 1] if they are from different communities.

It turns out that for community detection, the top k leading eigenvectors of the adjacency matrix A play an important role. In particular, for the case of 2 communities, spectral bisection algorithms simply take the second eigenvector to reveal the community structure. This can be also seen from the expected adjacency matrix E[A] under SBM(n, 2, a intra , a inter ), which is a rank-2 matrix with the top eigenvalue 1 2 (a intra + a inter ) and eigenvector 1, and the second eigenvalue 1 2 (a intra -a inter ) and eigenvector σ such that σ i = 1 if i is in community 1 and σ i = -1 otherwise. More generally, the second eigenvalue is of particular theoretical interests because it controls at the first order how fast heat diffuses through graph, as depicted by the discrete Cheeger inequality (Lee et al., 2014) .

While one would expect taking the second eigenvector of the adjacency matrix suffices, it often fails in practice (even when it is theoretically possible to recover the clusters given the signal-to-noise ratio). This is especially true for sparse networks, whose average nodal degrees is a constant that does not grow with the network size. This is because the spectrum of the Laplacian or adjacency matrix is blurred by "outlier" eigenvalues in the sparse regime, which is often caused by high degree nodes (Kaufmann et al., 2016) . Unsurprisingly, powering the Laplacian would be of no avail, because it does not change the eigenvectors or the ordering of eigenvalues. In fact, those outliers can become more salient after powering, thereby weakening the useful spectral signal even further. Besides, pruning the largest degree nodes in the adjacency matrix or normalizing the Laplacian cannot solve the issue. To date, the best results for pruning does not apply down to the theoretical recovery threshold (Coja-Oghlan, 2010; Mossel et al., 2012; Le et al., 2015) ; either outliers would persist or one could prune too much that the graph is destroyed. As for normalized Laplacian, it may overcorrect the large degree nodes, such that the leading eigenvectors would catch the "tails" of the graph, i.e., components weakly connected to the main graph. See Figure A.3 in the appendix for an experimental illustration.

In summary, graph Laplacian may not be the ideal choice due to its limited spatial scope of information fusion, and its undesirable artefacts in the spectral domain.

1.2. IF NOT LAPLACIAN, THEN WHAT?:

In searching for alternatives, potential choices are many, so it is necessary to clarify the goals. In view of the aforementioned pitfalls of the graph Laplacian, one would naturally ask the question:

Can we find an operator that has wider spatial scope, more robust spectral properties, and is meanwhile interpretable and can increase the expressive power of GCNs?

From a perspective of graph data analytics, this question gauges how information is propagated and fused on a graph, and how we should interpret "adjacency" in a much broader sense. An image can be viewed as a regular grid, yet the operation of a CNN filter goes beyond the nearest pixel to a local neighborhood to extract useful features. How to draw an analogy to graphs? From a perspective of robust learning, this question sheds light on the basic observation that realworld graphs are often noisy and even adversarial. The nice spectral properties of a graph topology can be lost with the presence or absence of edges. What are some principled ways to robustify the convolution operator and graph embeddings?

In this paper, we propose a graph learning paradigm that aims at achieving this goal, as illustrated in Figure 1 . The key idea is to generate a sequence of graphs from the given graph that capture a wide range of spectral and spatial behaviors. We propose a new operator based on this derived sequence. Definition 2 (Variable power operator). Consider an unweighted and undirected graph G. Let A [k] denote the k-distance adjacency matrix, i.e., A [k] ij = 1 if and only if the shortest distance (in the original graph) between nodes i and j is k. The variable power operator of order r is defined as:

EQUATION

where θ := (θ 0 , . . . , θ r ) is a set of parameters.

Clearly, A

θ is a natural extension of the classical adjacency matrix (i.e., r = 1 and θ 0 = θ 1 = 1). With power order r > 1, one can increase the spatial scope of information fusion on the graph when applying the convolution operation. The parameters θ k also has a natural explanation-the magnitude and the sign of θ k can be viewed as "global influence strength" and "global influence propensity" at distance k, respectively, which also determines the participation factor of each graph in the sequence in the aggregated operator. Furthermore, we provide some theoretical justification of the proposed operator by establishing the following asymptotic property of spectral separation under the important SBM setting, which is, nevertheless, not enjoyed by the classical Laplacian operator or its normalized or powered versions. (All proofs are given in the appendix.) Theorem 3 (Asymptotic spectral separation of variable power operator). Consider a graph G drawn from SBM(n, 2, a intra , a inter ). Assume that the signal-to-noise ratio ξ 2 2 /ξ 1 > 1, where ξ 1 = 1 2 (a intra + a inter ) and ξ 2 = 1 2 (a intra -a inter ) (c.f., (Decelle et al., 2011) ). Suppose r is on the order of c log(n) for a constant c, such that c log(ξ 1 ) < 1/4. Given nonvanishing θ k for k > r/2, the variable power operator A (r) θ has the following spectral properties: (i) the leading eigenvalue is on the order of Θ ( θ 1 ξ r 1 ), the second leading eigenvalue is on the order of Θ ( θ 1 ξ r 2 ), and the rest are bounded by θ 1 n ξ r/2 1 O(log(n)) for any fixed > 0; and (ii) the two leading eigenvectors are sufficient to recover the two communities asymptotically (i.e., as n goes to infinity). Intuitively, the above theoretical result suggests that the variable power operator is able to "magnify" benign signals from the latent graph structure while "suppressing" noises due to random artefacts.

Graph convolution:

Variable power graph 𝐴 𝜃 # 𝐴 [#] 𝜃 & 𝐴 [&] Node prediction Original graph

+ Graph sparsification:

Figure 1 : From the original graph, we generate a series of graphs, which are weighted by parameters that gauge the influence strengths, (optionally) sparsified, and eventually combined to form a variable power graph. This is expected to improve spectral methods in general, especially when the benign signals tend to be overwhelmed by noises. For the rest of the paper, we will apply this insight to propose a robust graph learning paradigm in Section 2, as well as a new GCN architecture in Section 3. We also provide empirical evidence of the gain from this theory in Section 4 and conclude in Section 5.

1.3. RELATED WORK:

Beyond nearest neighbors. Several works have been proposed to address the issue of limited spatial scope by powering the adjacency matrix (Lee et al., 2018; Wu et al., 2019; Li et al., 2019) . However, simply powering the adjacency does not extract spectral gap and may even make the eigenspectrum more sensitive to perturbations. Abu-El-Haija et al. (2018; 2019) also introduced weight matrices for neighbors at different distances. But this could substantially increase the risk of overfitting in the low-data regime and make the network vulnerable to adversarial attacks.

Robust spectral theory. The robustness of spectral methods has been extensively studied for graph partitioning/clustering (Li et al., 2007; Balakrishnan et al., 2011; Chaudhuri et al.; Amini et al., 2013; Joseph et al., 2016; Diakonikolas et al., 2019) . Most recently, operators based on self-avoiding or nonbacktracking walks have become popular for SBM (Massoulié, 2014; Mossel et al., 2013; Bordenave et al., 2015) , which provably achieve the detection threshold conjectured by Decelle et al. (2011) . Our work is partly motivated by the graph powering approach by Abbe et al. (2018) , which leveraged the result of Massoulié (2014) ; Bordenave et al. (2015) to prove the spectral gap. The main difference with this line of work is that these operators are studied only for spectral clustering without incorporating nodal features. Our proposed variable power operator can be viewed as a kernel version of the graph powering operator (Abbe et al., 2018) , thus substantially increasing the capability of learning complex nodal interactions while maintaining the spectral property.

Robust graph neural network. While there is a surge of adversarial attacks on graph neural networks (GNNs) (Dai et al., 2018; Zügner & Günnemann, 2019; Bojchevski & Günnemann, 2019) , very few methods have been proposed for defense (Sun et al., 2018) . Existing works employed known techniques from computer vision (Szegedy et al., 2014; Goodfellow et al., 2015; Szegedy et al., 2016) , such as adversarial training with "soft labels" (Chen et al., 2019) or outlier detection in the hidden layers (Zhu et al., 2019) , but they do not exploit the unique characteristics of graphstructured data. Importantly, our approach simultaneously improves performance in both the benign and adversarial tests, as shown in Figure 2 (details are presented in Section 4). (Bojchevski & Günnemann, 2019) ) accuracy for semi-supervised learning benchmarks.

2. GRAPH AUGMENTATION: ROBUST TRAINING PARADIGM:

Exploration of the spectrum of spectral and spatial behaviors. Given a graph G, consider a family of its powered graphs, G (2) , . . . , G (r) , where G (k) is obtained by connecting nodes with distance less than or equal to k. This "graph augmentation" procedure is similar to "data augmentation", because instead of limiting the learning on a single graph that is given, we artificially create a series of graphs that are closely related to each other in the spatial and spectral domains.

As we increase the power order, the graph also becomes more homogenized (Figure A.1) . In particular, it can help near-isolated nodes (i.e., low-degree vertices), since they become connected beyond their nearest neighbors. By comparison, simply raising the adjacency matrix to its r-th power will make them appear even more isolated, because it inadvertently promotes nodes with high degrees or nearby loops much more substantially as a result of feedback. Furthermore, the powered graphs can extract spectral gaps in the original graph despite local irregularities, thus boosting the signalto-noise ratio in the spectral domain.

Transfer of knowledge from the powered graph sequence. Consider a generic learning task on a graph G with data D. The loss function is denoted by (W; G, D) for a particular GCN architecture parametrized by W. For instance, in semi-supervised learning, D consists of features and labels on a small set of nodes (see Table A .1), and is the cross-entropy loss over all labeled examples. Instead of minimizing over (W; G, D) alone, we use all the powered graphs:

(W; G, D) + r k=2 α k (W; G (k) , D), (r-GCN)

where α k ≥ 0 gauges how much information one desires to transfer from powered graph G (k) to the learning process. By minimizing the (r-GCN) objective, one seeks to optimize the network parameter W on multiple graphs simultaneously, which is beneficial in two ways: (i) in the low-data regime, like semi-supervised learning, it helps to reduce the variance to improve generalization and transferability; (ii) in the adversarial setting, it robustifies the network since it is more likely that the perturbed network is contained in the wider spectrum during training.

3 FROM FIXED TO VARIABLE POWER NETWORK By using the variable power operator illustrated in Figure 1 , we substantially increase the search space of graph operators. The proposed operator also leads to a new family of graph algorithms with broader scope of spatial fusion and enhanced spectral robustness. As the power grows, the network eventually becomes dense. To manage this increased complexity and make the network more robust against adversarial attacks in the feature domain, we propose a pruning mechanism.

Graph sparsification. Given a graph G := (V, E [1] ), consider its powered version G (r) := (V, E (r) ) and a sequence of intermediate graphs G [2] , . . . , G [r] , where G [k] := (V, E [k] ) is constructed by connecting two vertices if and only if the shortest distance is k in G. Clearly, {E [k] } r k=1 forms a partition of E (r) . For each node i ∈ V, denote its r-neighborhood by N r (i) := {j ∈ V | d G (i, j) ≤ r}, which is identical to the set of nodes adjacent to i in G [r] . Next, for each edge within this neighborhood, we associate a value using some suitable distance metric φ to measure "aloofness." For instance, it can be the usual Euclidean distance or correlation distance in the feature space. Based on this formulation, we prune an edge e := (i, j) in E (r) if the value is larger than a threshold τ (i, j), and denote the edge set after pruning Ē(r) . Then, we can construct a new sequence of sparsified graphs, G [k] with edge sets Ē[k] = E [k] ∩ Ē(r) and adjacency matrix Ā[k] . Hence, the variable power operator is given by

Ā(r) θ = r k=0 θ k Ā[k] .

Due to the influence of high-degree nodes in the spectral domain, one can adaptively choose the thresholds τ (i, j) to mitigate their effects. Specifically, we choose τ to be a small number if either i or j are nodes with high degrees, thereby making the sparsification more influential in densely connected neighborhoods than weakly connected parts.

Layer-wise update rule. To demonstrate the effectiveness of the proposed operator, we adopt the vanilla GCN strategy (2). Importantly, we replace the graph convolutional operator A with the variable power operator to obtain the variable power network (VPN):

A = D -1 2 (I + Ā(r) θ )D -1 2 , (VPN)

where

D ii = 1 + |{j ∈ V | d G (i, j) = 1}|.

The introduction of I is reminiscent of the "renormalization trick" (Kipf & Welling, 2017), but it can be also viewed as a regularization strategy in this context, which is well-known to improve the spectral robustness (Amini et al., 2013; Joseph et al., 2016) . This construction immediately increases the scope of data fusion by a factor of r. Proposition 4. By choosing A with (VPN) in the layer-wise update rule (2), the output at each node from a L-layer GCN depends on neighbors within L * r hops.

Since we proved that the variable power operator has nice spectral separation in Theorem 3, VPN is expected to promote useful spectral signals from the graph topology (similar to the preservation of useful information in images (Jacobsen et al., 2018) , our method preserves useful information in the graph topology). This claim is substantiated with the following proposition. Proposition 5. Given a graph with two hidden communities. Consider a 2-layer GCN architecture with layer-wise update rule (2). Suppose that A has a spectral gap. Further, assume that the leading two eigenvectors are asymptotically aligned with 1 and ν, i.e., the community membership vector, and that both are in the range of feature matrix X. Then, there exists a configuration of W (1) and W (2) such that the GCN outputs can recover the community with high probability.

4. EXPERIMENTS:

The proposed methods are evaluated against several recent models, including vanilla GCN (Kipf & Welling, 2017) and its variant PowerLaplacian where we simply replace the adjacent matrix with its powered version, three baselines using powered Laplacian IGCN (Li et al., 2019) , SGC (Wu et al., 2019) and LNet (Liao et al., 2019) , the recent method MixHop (Abu-El-Haija et al., 2019) which attempts to increase spatial scope fusion, as well as a state-of-the-art baseline and RGCN (Zhu et al., 2019) , which is also aimed at improving the robustness of Vanilla GCN. All baseline methods on based on their public codes.

4.1. REVISITING THE STOCHASTIC BLOCK MODEL:

SBM dataset. We generated a set of networks under SBM with 4000 nodes and parameters such that the SNRs range from 0.58 to 0.91. To disentangle the effects from nodal features with that from the spectral signal, we set the nodal features to be one-hot vectors. The label rates are 0.1%, 0.5% and 1%, the validation rate is 1%, and the rest of the nodes are testing points.

Performance. Since the nodal features do not contain any useful information, learning without topology such as multi-layer perceptron (MLP) is only as good as random guessing. The incorporation of graph topology improves classification performance-the higher the SNR (i.e., ξ 2 2 /ξ 1 , see Theorem 3), the higher the accuracy. Overall, as shown in Figure 3 , the performance of the proposed method (VPN) is superior than other baselines, which either use Laplacian (GCN, Chebyshev, RGCN, LNet) or its powered variants (IGCN, PowerLaplacian). modes of the the adjacency matrix or VPN, and X be the nodal features (i.e., identity matrix). We analyze the information from spectral signals (e.g., the k-th and k + 1-th eigenvectors) by estimating the accuracy of an MLP with filtered nodal features, namely Φ :,k:(k+1) Φ :,k:(k+1) X, as shown in Figure 4 . The accuracy reflects the information content in the frequency components. We see that the two leading eigenvectors of VPN are sufficient to perform classification, whereas those of the adjacency matrix cannot make accurate inferences.

EQUATION

EQUATION

4.2. SEMI-SUPERVISED NODE CLASSIFICATION:

Experimental setup. We followed the setup of (Yang et al., 2016; Kipf & Welling, 2017) for citation networks Citeseer, Cora and Pubmed (please refer to the Appendix for more details).

• • • • • • • • • • • • • • • • • • • • • 66 68 70 2 4 6 8

Power order Accuracy Graph powering order can influence spatial and spectral behaviors. Our theory suggests powering to the order of log(n); in practice, orders of 2 to 4 suffice (Figure 5 ).

• • • • • • • • • • • • • • • • • • • • • 75

Here, we chose the power order to be 4 for r-GCN on Citeseer and Cora, and 3 for Pubmed, and reduced the order by 1 for VPN.

Performance. By replacing Laplacian with VPN, we see an immediate improvement in performance (Table 1 ). We also see that a succinct parametrization of the global influence relation in VPN is able to increase the expressivity of the network. For instance, the learned θ at distances 2 and 3 for Citeseer are 3.15e-3 and 3.11e-3 with p-value less than 1e-5. This implies that the network tends to put more weights in closer neighbors.

4.3. DEFENSE AGAINST EVASION ATTACKS:

To evaluate the robustness of the learned network, we considered the setting of evasion attacks, where the model is trained on benign data but tested on adversarial data.

Adversarial methods. Five strong global attack methods are considered, including DICE (Zügner & Günnemann, 2019), A abr and A DW3 (Bojchevski & Günnemann, 2019) , Meta-Train and Meta-Self (Zügner & Günnemann, 2019) . We further modulated the severity of attack methods by varying the attack rate, which corresponds to the percentage of edges to be attacked.

Robustness evaluation. In general, both r-GCN and VPN are able to improve over baselines for the defense against evasion attacks, e.g., Figure 6 for the A DW3 attack (detailed results for other attacks are listed in the Appendix). It can be also observed that the proposed methods are more robust in Citeseer and Cora than Pubmed. In addition to the low label rates, we conjectured that topological 2019) that GCNs share similar characteristics of low-pass filters, in the sense that nodal features filtered by low-frequency Fourier modes lead to accurate classifiers (e.g., MLP). However, one key question left unanswered is how to obtain the Fourier modes. In their experiments, they derive it from the graph Laplacian. By using VPN to construct the Fourier modes, we show that the information content in the low-frequency domain can be improved.

More specifically, we first perform eigendecomposition of the graph convolutional operator (i.e., graph Laplacian or VPN) to obtain the Fourier modes Φ. We then reconstruct the nodal features X using only the k-th and the k + 1-th eigenvectors, i.e., Φ :,k:(k+1) Φ :,k:(k+1) X. We then use the reconstructed features in MLP to perform the classification task in a supervised learning setting. As Figure 7 shows, features filtered by the leading eigenvectors of VPN lead to higher classification accuracy compared to the classical adjacency matrix.

For the adversarial testing, we construct a new basis Φ based on the attacked graph, and then use Φ :,k:(k+1) Φ :,k:(k+1) X as test points for the MLP trained in the clean data setting. As can be seen in Figure 8 , models trained based on VPN filtered features also have better adversarial robustness in evasion attacks. Since the eigenvalues of the corresponding operator exhibit low-pass filtering characteristics (Figure A.2), the enhanced benign and adversarial accuracy of VPN is attributed to the increased signal-to-noise ratio in the low-frequency domain. This is in alignment with the theoretical proof of spectral gap developed in this study. 

4.4. DISCUSSIONS:

In this paper, we proposed a new graph operator to replace the graph Laplacian in the classic GCN. It is worth mentioning that our approach is very different from the k-th order polynomials of the Laplacian developed in (Defferrard et al., 2016) or the high-order graph Laplacian employed in (Lee et al., 2018; Li et al., 2019; Abu-El-Haija et al., 2019; Wu et al., 2019) . If the graph Laplacian L is powered to the k-th order, the resulting matrix has the same eigenvectors as L, with only the eigenvalues powered to the k-th order. Thus, the corresponding k-th order polynomial has the same eigenvectors, with the polynomial function applied only to the eigenvalues. However, the proposed variable power operator has radically different eigenvectors as the graph Laplacian or its powered variant. This is an important difference because we observed empirically that the leading eigenvectors of a graph Laplacian are extremely sensitive to outliers under the SBM, and they often correspond to either tails or high-degree nodes (please see Figure A.3 for an illustration). However, our result in Theorem 3 suggests that the leading eigenvectors of the proposed operator asymptotically recovers the underlying community under SBM, and enjoys the "spectral gap" property.

We also remark that the meaning of robustness in the machine learning literature ("adversarial robustness") and in the spectral theory literature ("spectral robustness") appear to be different. However, in this work, we argue that spectral robustness is closely related to adversarial robustness. This can be explained from a matrix perturbation point of view. Let λ k and φ k be the eigenvalue and the corresponding eigenvector of the adjacency matrix A. Then, the sensitivity of the eigenvector to the perturbation is given by (Trefethen & Bau III, 1997):

∂φ k ∂A (ij) = n =1, =k φ (i) φ k(j) (2 -δ (ij) ) λ k -λ φ ,

where A (ij) is the (i, j)-th entry of A, φ k(j) is the j-th entry of φ k , δ (ij) is the perturbation of the (i, j)-th entry of A, and n is the dimension of A. It can be seen that the perturbation of the convolutional operator is controlled by the inverse of the spectral gap. When the spectral gaps between the leading eigenvalues (i.e., λ 1 and λ 2 ) and the rest of the eigenvalues are large, the perturbations of the leading eigenvectors due to the adversarial attack are controlled. Since the eigenvalues of the graph convolutional operator decays very quickly (see Figure A.2 as an illustration), the learned representation is heavily influenced by the leading eigenvectors. Thus, by controlling the perturbations of the leading eigenvectors, one can expect to control the perturbations of the outputs.

Our theoretical result in Theorem 3 was based on the standard SBM, which is a classic model proposed in mathematical sociology and has been adopted to model and analyze real-world social and biological networks (Funke & Becker, 2019) . The main advantage of SBM is that it encodes the structural information that nodes belong to the same community tend to be more connected with each other. Nevertheless, we recognize one limitation of our analysis is that SBM might not be a suitable model for some existing or future applications, in which case, models with more flexibility in the degree distributions, such as the degree-corrected SBM proposed by Karrer & Newman (2011) , labeled SBM by Heimlicher et al. (2012) , or hiearchical SBM proposed by Peixoto (2017) could be more applicable. Also our analysis is limited to two communities, and the extension to more than two communities is a challenging open problem. Nevertheless, through extensive experiments, we observed that our theory has strong implications for real-world graphs. This is evident from the informative and robust low-frequency spectral signal results in Figures 7 and 8 , which show that the proposed graph convolution operator has a clear advantage in the low-frequency regime over the classic graph Laplacian in terms of classification accuracy.

5. CONCLUSION:

This study goes beyond classical spectral graph theory to defend GCNs against adversarial attacks. We challenge the central building block of existing methods, namely the graph Laplacian, which is not robust to noisy links. For adversarial robustness, spectral separation is a desirable property.

We propose a new operator that enjoys this property and can be incorporated in GCNs to improve expressivity and interpretability. Furthermore, by generating a sequence of powered graphs based on the original graph, we can explore a spectrum of spectral and spatial behaviors and encourage transferability across graphs. The proposed methods are shown to improve both benign and adversarial accuracy over various baselines evaluated against a comprehensive set of attack strategies.

Lloyd 

A APPENDIX A.1 PROOF OF PROPOSITION 4:

To validate the claim, we prove a more general result. Consider a graph G and its powered graph G (r) , whose adjacency matrices are A and A (r) , respectively. Since the support of A (r)

θ is identical to that of A (r) , we will focus on A (r) for notational simplicity. For any signal f : V → R |V| on a graph, denote the support of the signal f v on node v ∈ V by S f v , i.e., f v only depends on the signals on nodes in S f v . Then, it is easy to see that the signal g Af has support S g v ⊆ ∪ u∼rv S f u , where u ∼ r v denotes adjacency relation on G (r) defined by A (r) . Clearly, the set defined by

{u ∈ V | u ∼ r v} is identical to {u ∈ V | d G (u, v) ≤ r}, where d G (u, v) denotes the shortest distance from u to v on G.

Also, we see that element-wise operation does not expand the support, i.e., for any element-wise activation σ, the signal g σ σ(f ) has support S gσ v ⊆ S f v . In particular, we can prove the claim by iteratively applying the function composition layer by layer, since each layer is of the form σ(A (r) θ H (l) W (l) ), where H (l) is the hidden state at layer l and W (l) is the corresponding weight matrix. Hence after L iterations of layer-wise updates, the support of the output on v is given by {u

∈ V | d G (u, v) ≤ r * L}.

A.2 PROOF OF PROPOSITION 5:

Let λ 1 and λ 2 be the two leading eigenvalues of Ā with corresponding eigenvectors φ 1 and φ 2 , respectively. Without loss of generality, assume that both eigenvalues are nonnegative. Under the assumption that φ 1 and φ 2 lie in the range of X, there exists a W (1) such that XW

(1) = [φ 1 φ 2 ].

So the output of the first layer with ReLU activation is given by:

H (1) = σ ĀXW (1) = σ Ā [φ 1 φ 2 ] (4) = [λ 1 σ(φ 1 ) λ 2 σ(φ 2 )] (5) = λ 1 (1 + σ(h 1 )) λ 2 ( 1 2 ν + 1 2 1 + σ(h 2 ))

where h 1 = o(1) and h 2 = o(1) (6) where ( 5) is due to the definition of eigenvectors and that σ is an element-wise operation, and ( 6) is due to the asymptotic alignment condition and the fact that σ(ν) = 1 2 ν + 1 2 1. Therefore, by choosing the last layer weight

W (2) = -1 λ1λ2 1 λ1λ2 2 λ 2 2 -2 λ 2 2

, the output of the last layer is given by: 1) for k = 1, 2. Therefore, after the softmax operation, we can see that the 2-layer output recovers the membership of the elements exactly.

Y = ĀH (1) W (2) = Ā λ 1 (1 + σ(h 1 )) λ 2 ( 1 2 ν + 1 2 1 + σ(h 2 )) W (2) = λ 2 1 1 + h 1 λ 2 2 2 ν + λ1λ2 2 1 + h 2 W (2) = [ν + h 1 -ν + h 2 ] where h k 2 = o(1), h k 2 = o(

One general remark is that while the above argument is not limited to the leading two eigenvalues/eigenvectors, from the form of W (2) whose elements depend inversely on the corresponding eigenvalues, we can expect more numerical stability (and hence easier learning) when the corresponding eigenvalues are large.

A.3 PROOF OF THEOREM 3:

Consider a stochastic block model with two communities, where the intra-community connection probability is a intra /n and the inter-community connection probability is a inter /n, and assume that a intra > a inter . Let ξ 1 = aintra+ainter 2 and ξ 2 = aintra-ainter 2 , which correspond to the first and second eigenvalues of the expected adjacency matrix of the above model. Let ν denote the community label vector, with ν i = ±1 depending on the membership of node i. For weak recovery, we assume the detectability condition (Decelle et al., 2011) :

EQUATION

With the notations from the main paper, let k] denote the θ-weighted variable power operator, where

A (r) θ = r k=0 θ k A [

A [k] ij = 1 if d G (i, j) = k 0 o.w.

is the k-distance adjacency matrix. Let

A {k} denote the nonbacktracking path counting matrix, where the (i, j)-th component indicate the number of self-avoiding paths of graph edges of length k connecting i to j (Massoulié, 2014) . Our goal is to prove that the top eigenvectors of A (r)

θ are asymptotically aligned with those of A {k} for k greater than log(n) up to a constant multiplicative factor. To do so, we first recall the result of (Massoulié, 2014) , which examines the behaviors of top eigenvectors of A {k} . Lemma 6 ( (Massoulié, 2014) ). Assume that (7) holds. Then, w.h.p., for all k ∈ {r/2, ..., r}:

(a) The operator norm A {k} 2 is up to logarithmic factors Θ(ξ k 1 ). The second eigenvalue of A {k} is up to logarithmic factors Ω(ξ k 2 ).

(b) The leading eigenvector is asymptotically aligned with A {k} 1:

A {k} A {k} 1 A {k} A {k} 1 2 = A {k} 1 A {k} 1 2 + h k where h k = o(1)

. The second eigenvector is asymptotically aligned with A {k} ν:

A {k} A {k} ν A {k} A {k} ν 2 = A {k} ν A {k} ν 2 + h k where h k = o(1). Now, we first define Γ {r} θ = r k=r/2 θ k A {k} , so A (r) θ = Γ {r} θ + ∆ {r} θ = Γ {r} θ + A (r/2-1) θ + r k=r/2 θ k (A [k] -A {k} ).

Also, by (Massoulié, 2014, Theorem 2.3) , the local neighborhoods of vertices do not grow fast, and w.h.p., the graph of A (r/2-1) has maximum degree O(ξ r/2 1 (log n) 2 ). Let φ be the leading eigenvector of A (r/2-1) θ

, and let v be the node where φ is maximum (i.e., φ(v) ≥ φ(u)). Without loss of generality, assume that φ(v) > 0. We have a good control over the first eigenvalue λ 1 of A (r/2-1) θ as follows:

λ 1 = (A (r/2-1) θ φ)(v) φ(v) = r/2-1 k=0 {u:d G (u,v)=k} θ k φ(u) φ(v) = r/2-1 k=0 θ k {u:d G (u,v)=k} φ(u) φ(v) ≤ r/2-1 k=0 |θ k | {u:d G (u,v)=k} 1 ≤ θ ∞ {u:d G (u,v)≤r/2-1} 1 = O( θ 1 ξ r/2 1 (log n) 2 )

Due to (Abbe et al., 2018, Theorem 2) , which proves an identical result of Lemma 6 but for A [k] , we know that w.h.p., for r = log(n), we can bound the last term by

r k=r/2 θ k (A [k] -A {k} ) 2 ≤ r k=0 |θ k | A [k] -A {k} 2 = O θ 1 ξ r/2 1 (log n) 4

Therefore, by triangle inequality, we can conclude that

∆ {r} θ 2 = A (r) θ -Γ {r} θ 2 = O θ 1 ξ r/2 1 (log n) 4 . (8)

Now, our goal is to show a similar result as Lemma 6 for Γ {r} θ . In particular,

EQUATION

where ( 10) and ( 14) are due to triangle inequalities, ( 11) and ( 15) are due to results in (Massoulié, 2014) , and ( 13) is due to Lemma 6. Therefore, we have Γ The graph becomes more homogeneous and high degree nodes become more prevalent as we increase the powers.

Then, by (Massoulié, 2014, Theorem 2. 2), we can have

A {k} = Q {k} + k m=1 (Q {k-m} AA {m-1} ) - k m=1 W {k,m} . Hence, Γ {r} θ = r k=r/2 θ k A {k} = r k=r/2 θ k Q {k} + r k=r/2 θ k k m=1 Q {k-m} AA {m-1} - r k=r/2 k m=1 θ k W {k,m} = r k=r/2 θ k Q {k} + r m=1   r k=max(r/2,m) θ k Q {k-m} A   A {m-1} - r k=r/2 k m=1 θ k W {k,m} .

In particular, for any u that is orthogonal to A {m} 1 and A {m} ν with norm-1 (i.e., a feasible vector of the variational definition in Lemma 7), we have: (Massoulié, 2014) , the terms ρ Q {k} and ρ W {k,m} are bounded by n ξ

Γ {r} θ u 2 ≤ ρ   r k=r/2 θ k Q {k}   + r m=1 r k=max(r/2,m) |θ k |ρ Q {k-m} AA {m-1} u 2 + ρ   r k=r/2 θ k k m=1 W {k,m}   Since by

r/2 1 , AA {m-1} x 2 is bounded by O(log(n) + log(n)ξ m-1 1

), with some elementary calculations, we have that 2), number of hidden units (16), dropout rates (0.5), weight decay (5 × 10 -4 ), and weight initialization following (Glorot & Bengio, 2010) implemented in Tensorflow. The training process is terminated if validation accuracy does not improve for 40 consecutive steps. We note that the citation datasets are extremely sensitive to initializations; as such, we report the test accuracy for the top 50 runs out of 100 random initializations sorted by the validation accuracy. We used Adam (Kingma & Ba, 2014) with a learning rate of 0.01 except for θ (VPN), which was chosen to be 1 × 10 -5 to stabilize training. For VPN, we consider two-step training process, i.e., we first employ graph sparsification on adjacency matrix Ā[k] based on X for the first-step training, then process second graph sparsification on adjacency matrix Ā[k] with respect to the feature embedding from hidden layer and fetch them back into model for second-step training with warm restart (continue training with the parameters from first-step). We set α k to be 0.5 for the corresponding power order and 0 other wise in r-GCN.

Γ {r} θ u 2 is bounded by θ 1 n ξ r/2 1 O(log(n)).

To enhance robustness against evasion attack, we adaptively chose the threshold of graph sparsification. For each node, we consider all its neighbors within r hops, where r is the order of the powered graph. We order these neighbors based on their Euclidean distance to the current node in the feature space. We then set the threshold for this node such that only the first s * d neighbors with the smallest distance are selected, where s is the sparsification rate, and d is the degree of the node in the original graph. If this node is a high-degree node (determined by if the degree is higher than the average degree by more than 2 standard deviations), we set s = 1; otherwise, we set s to be a small number slightly larger than 1. Nevertheless, we do not observe that the robustness performance is sensitive to this parameter. In addition, one can define their own distance function that better measures proximity between nodes, such as correlation distance or cosine distance. As a side remark, one can easily obtain A (r) with 1[(I + A) r > 0], and recursively calculate A [k] . The proposed methods have similar computational complexity as vanilla GCN as a result of sparsification. Revisiting SBM. To obtain networks with different SNRs (0.58, 0.68, 0.79, 0.85, 0.91), we set the intra-degree average a intra = 2.1 and inter-degree average a inter to be 0.4, 0.3, 0.2, 0.15, 0.1 respectively. We generate 10 networks for each SNR. One of the networks with SNR of 0.91 is analyzed in Figure A.3 for different convolution operators. As predicted by Theorem 3, the proposed operators have nontrivial spectral gap. This is not enjoyed by other operators, so it is a quite unique property. Furthermore, our learned operator w/ or w/o normalization obtained 81% accuracy based We provide the post-evasion accuracy in Table A .2 and Table A .3 and robustness enhancement in Computational efficiency. The adjacency matrix could be much denser after being powered several times, which poses a general challenge for all high-order matrix-based approaches. To alleviate this issue, we employ a simple sparsification strategy as described in the main paper. To demonstrate the computational efficiency of the proposed method, we introduce a running time comparison experiment on the real world social network (Social circles: Facebook) (Leskovec & Mcauley, 2012) . This small dataset consists of "circles" (or "friends lists") from Facebook and becomes very dense from first order (4.71%) to second order (92.12%), thus is suitable to be used for computational efficiency evaluation. The results are shown in Table A .4. We can find that the running efficiency of the proposed method is compatible with baselines and the density does not affect the efficiency significantly when the dataset is not too large. Moreover, in this paper, our primary goal is to improve the robustness. We leave the solution to resolve the scalability issue as a future direction. 64.0 ± 0.9 57.2 ± 0.3 58.1 ± 0.7 55.2 ± 0.2 65.9 ± 0.9 62.9 ± 1.7 60.6 ± 0.7 66.3 ± 0.9 66.2 ± 0.4 67.3 ± 0.9 66.2 ± 0.1 20 62.4 ± 1.2 55.5 ± 0.2 56.8 ± 0.8 55.9 ± 0.4 65.3 ± 1.2 61.2 ± 1.5 58.6 ± 1.9 65.3 ± 1.0 64.9 ± 0.1 66.3 ± 0.4 65.6 ± 0.4 25 62.7 ± 1.0 56.6 ± 0.7 58.4 ± 1.1 55.3 ± 0.3 65.1 ± 0.7 60.5 ± 1.6 57.6 ± 1.9 65.6 ± 0.8 65.0 ± 0.6 65.9 ± 0.5 65.5 ± 0.5 30 61.1 ± 0.9 55.9 ± 0.5 56.4 ± 0.7 54.9 ± 0.1 64.7 ± 0.3 60.3 ± 1.5 57.5 ± 1.4 64.1 ± 0.8 64.5 ± 1.2 66.0 ± 1.0 64.5 ± 0.9

Attack 

:



Figures and Tables:

Figure 3: Comparison for SBM dataset. Shaded area indicates standard deviation over 10 runs. Spectral separation and Fourier modes. From the eigenspectrum of the convolution operators (Figure A.3), we see that the spectral separation property is uniquely possessed by VPN, whose first two leading eigenvectors carry useful information about the underlying communities: without the help of nodal features, the accuracy is 87% even with label rate of 0.5%. Let Φ denote the Fourier

Figure 5: Benign and adversarial accuracy as power order increases. Dahsed lines correspond to vanilla GCN.

Figure 6: Robustness merit accuracy post-attack proposed-methodaccuracy post-attack vanilla GCN reported in percentage under A DW3 attack. The error bar indicates standard deviation over 20 independent simulations.

Figure 7: Accuracy of first 500 frequency components for VPN (red) and adjacency matrix (blue). The x axis corresponds to the index k in Φ :,k:(k+1) Φ :,k:(k+1) X for signal reconstruction.

Figure 8: Accuracy of the leading frequency components in adversarial testing. We use Φ :,1:k Φ :,1:k X as reconstructed nodal features for testing, where k is 10 for Citeseer and 5 for Cora and Pubmed. Error bar indicates standard deviation over 10 runs.

Figure A.1: Degree distribution in the original graph and the powered graphs for Citeseer and Cora.The graph becomes more homogeneous and high degree nodes become more prevalent as we increase the powers.

Figure A.2: Eigenspectrum of (a) the adjacency matrix and (b) VPN raised to different powers. The convolution operator becomes similar to low-pass filters as we increase powers. The eigenspectrum of VPN also has sharper edges than the original adjacency matrix.

Figure A.3: Illustration of operators for SBM, showing (top to bottom) the eigenspectrum, plots of the first 2 leading eigenvectors, and the detected clusters. We consider (from left to right) the adjacency matrix A, normalized Laplacian I -D -1/2 AD -1/2 , powered normalized Laplacian I -D -1/2 r A r D -1/2 r (D r is the degree matrix of A r ), VPN A (r) θ with order 5 (θ k is 1 when k = 1 and 0.1 otherwise), and the normalized version D -1/2 (I + A (r) θ )D -1/2 .

Figure A.4: t-SNE visualization of network embeddings learned by r-GCN.

Figure A.6, Figure A.7 and Figure A.8 for Citeseer, Cora, and Pubmed. Results are obtained with 20 random initializations on a given attacked network.

Figure A.7: Illustration of evasion attack performance in terms of robustness enhancement on different attack methods for Cora.

Figure A.8: Illustration of evasion attack performance in terms of robustness enhancement on different attack methods for Pubmed.

Results for semi-supervised node classification. We highlighted the best and the second best performances, where we broke the tie by choosing the one with the smallest standard deviation.

Table content: <table><tr><td>Model</td><td>Citeseer</td><td>Cora</td><td>Pubmed</td></tr><tr><td>ManiReg (Belkin et al., 2006)</td><td>60.1</td><td>59.5</td><td>70.7</td></tr><tr><td>SemiEmb (Weston et al., 2012)</td><td>59.6</td><td>59.0</td><td>71.1</td></tr><tr><td>LP (Zhu et al., 2003)</td><td>45.3</td><td>68.0</td><td>63.0</td></tr><tr><td>DeepWalk (Perozzi et al., 2014)</td><td>43.2</td><td>67.2</td><td>65.3</td></tr><tr><td>ICA (Lu &amp; Getoor, 2003)</td><td>69.1</td><td>75.1</td><td>73.9</td></tr><tr><td>Planetoid (Yang et al., 2016)</td><td>64.7</td><td>75.7</td><td>77.2</td></tr><tr><td>Vanilla GCN (Kipf &amp; Welling, 2017)</td><td>70.3</td><td>81.5</td><td>79.0</td></tr><tr><td>PowerLaplacian</td><td>70.5</td><td>80.5</td><td>78.3</td></tr><tr><td>IGCN(RNM) (Li et al., 2019)</td><td>69.0</td><td>80.9</td><td>77.3</td></tr><tr><td>IGCN(AR) (Li et al., 2019)</td><td>69.3</td><td>81.1</td><td>78.2</td></tr><tr><td>LNet (Liao et al., 2019)</td><td>66.2 ± 1.9</td><td>79.5 ± 1.8</td><td>78.3 ± 0.3</td></tr><tr><td>RGCN (Zhu et al., 2019)</td><td>71.2 ± 0.5</td><td>82.8 ± 0.6</td><td>79.1 ± 0.3</td></tr><tr><td>SGC (Wu et al., 2019)</td><td>71.9 ± 0.1</td><td>81.0 ± 0.0</td><td>78.9 ± 0.0</td></tr><tr><td>MixHop (Abu-El-Haija et al., 2019)</td><td>71.4 ± 0.8</td><td>81.9 ± 0.4</td><td>80.8 ± 0.6</td></tr><tr><td>r-GCN (this paper)</td><td colspan="3">71.3 ± 0.54 81.7 ± 0.23 79.3 ± 0.31</td></tr><tr><td>VPN (this paper)</td><td colspan="3">71.4 ± 0.57 81.9 ± 0.32 79.6 ± 0.39</td></tr></table>

N Trefethen and David Bau III. Numerical linear algebra, volume 50. SIAM, 1997. Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semisupervised embedding. Neural Networks: Tricks of the Trade (2nd ed.), pp. 639-655, 2012.

Table content: <table><tr><td>Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differen-</td></tr><tr><td>tialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische</td></tr><tr><td>Annalen, 71(4):441-479, 1912.</td></tr><tr><td>Felix Wu, Amauri H. Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger.</td></tr><tr><td>Simplifying graph convolutional networks. In ICML 2019, pp. 6861-6871, 2019.</td></tr><tr><td>Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A</td></tr><tr><td>comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596, 2019.</td></tr><tr><td>Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning</td></tr><tr><td>with graph embeddings. In ICML 2016, pp. 40-48, 2016.</td></tr><tr><td>Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.</td></tr><tr><td>Graph convolutional neural networks for web-scale recommender systems. In KDD 2018, pp.</td></tr><tr><td>974-983. ACM, 2018.</td></tr></table>

1: Citation datasets. Label rate denotes the fraction of training labels in each dataset. Degree distribution in the original graph and the powered graphs for Citeseer and Cora is shown in Figure A.1. We used the same dataset splits as in(Yang et al., 2016;Kipf & Welling, 2017) with 20 labels per class for training, 500 labeled samples for hyper-parameter setting, and 1, 000 samples for testing. To facilitate comparison, we use the same hyper-parameters as Vanilla GCN(Kipf & Welling, 2017), including number of layers (

Table content: <table><tr><td colspan="6">Dataset Nodes Edges Features Classes Label rates</td></tr><tr><td colspan="2">Citeseer 3,327</td><td>4,732</td><td>3,703</td><td>6</td><td>0.036</td></tr><tr><td>Cora</td><td>2,708</td><td>5,429</td><td>1,433</td><td>7</td><td>0.052</td></tr><tr><td colspan="3">Pubmed 19,717 44,338</td><td>500</td><td>3</td><td>0.003</td></tr><tr><td colspan="4">A.5 MORE EXPERIMENTAL DETAILS AND RESULTS</td><td/><td/></tr></table>

2: Summary of evasion attack performance on DICE, A abr and A DW3 in terms of postevasion accuracy (in percent). Best performance under each setting is in bold.Table A.3: Summary of evasion attack performance on Meta-Train and Meta-Self in terms of postevasion accuracy (in percent). OOM (out of memory) for both methods on Pubmed.

Table content: <table><tr><td/><td>Attack Method</td><td/><td/><td/><td/><td/><td>DICE</td><td/><td/></tr><tr><td/><td>Attack Method</td><td/><td/><td/><td/><td/><td>Model Meta-Train</td><td/><td/></tr><tr><td/><td>Attack Rate (%)</td><td>GCN</td><td colspan="3">IGCN(RNM) IGCN(AR) LanczosNet</td><td>RGCN</td><td colspan="2">PowerLap 2 PowerLap 3 Model</td><td>SGC</td><td>MixHop</td><td>r-GCN</td><td>VPN</td></tr><tr><td/><td>5 Attack Rate (%)</td><td>68.5 ± 0.7 GCN</td><td colspan="8">64.1 ± 0.0 IGCN(RNM) IGCN(AR) LanczosNet 64.4 ± 0.5 60.6 ± 0.9 69.9 ± 0.7 64.8 ± 0.4 RGCN PowerLap 2 PowerLap 3 65.9 ± 0.7 68.8 ± 0.5 69.9 ± 1.0 70.5 ± 1.0 SGC MixHop r-GCN</td><td>70.0 ± 1.0 VPN</td></tr><tr><td>Citeseer Citeseer</td><td>10 15 5 20 10 25 30 15 20 25</td><td>66.3 ± 0.1 63.4 ± 0.2 67.6 ± 0.3 62.8 ± 0.4 66.0 ± 1.0 60.9 ± 0.6 57.5 ± 1.1 66.1 ± 0.6 64.9 ± 0.9 64.3 ± 0.7</td><td>61.6 ± 0.3 59.3 ± 0.5 62.8 ± 0.8 56.9 ± 0.5 61.0 ± 1.1 54.6 ± 0.3 51.9 ± 0.3 60.9 ± 1.1 59.1 ± 1.4 57.9 ± 1.8</td><td>61.9 ± 0.2 59.4 ± 0.2 63.1 ± 1.2 56.9 ± 0.2 61.4 ± 1.0 54.7 ± 0.7 52.1 ± 0.7 61.4 ± 1.0 59.7 ± 0.8 59.8 ± 1.0</td><td colspan="3">57.6 ± 0.4 67.9 ± 0.5 62.5 ± 0.4 55.7 ± 0.5 66.0 ± 0.7 60.4 ± 0.4 57.7 ± 0.7 69.3 ± 0.5 66.8 ± 1.1 53.0 ± 0.8 65.0 ± 1.0 57.8 ± 0.5 56.4 ± 0.3 68.3 ± 0.7 65.2 ± 0.9 51.8 ± 0.4 63.2 ± 1.0 55.5 ± 0.4 49.7 ± 0.8 60.2 ± 0.5 52.4 ± 0.3 55.4 ± 0.8 67.3 ± 0.4 64.5 ± 1.3 54.5 ± 0.1 66.6 ± 0.6 63.0 ± 1.2 54.0 ± 0.4 66.3 ± 0.7 62.7 ± 1.1</td><td colspan="3">62.9 ± 0.4 67.5 ± 0.7 67.7 ± 0.7 68.6 ± 0.6 60.2 ± 1.2 65.8 ± 0.7 65.4 ± 1.1 66.2 ± 0.4 64.9 ± 1.5 70.0 ± 0.3 69.6 ± 0.6 70.4 ± 0.7 57.5 ± 0.7 64.7 ± 0.8 64.6 ± 1.0 65.4 ± 0.8 61.9 ± 1.4 68.3 ± 0.2 68.9 ± 1.0 68.7 ± 0.4 55.3 ± 1.2 63.1 ± 0.5 63.2 ± 0.4 63.9 ± 0.0 51.3 ± 1.9 59.2 ± 0.4 63.0 ± 0.7 59.6 ± 0.4 60.9 ± 1.9 67.3 ± 0.8 67.8 ± 0.8 67.9 ± 0.6 58.2 ± 2.1 67.2 ± 0.5 67.1 ± 0.9 67.6 ± 0.4 55.8 ± 2.6 66.1 ± 0.5 66.5 ± 1.7 67.0 ± 0.5</td><td>68.3 ± 0.9 70.4 ± 0.6 66.4 ± 0.3 69.4 ± 1.0 63.9 ± 0.9 63.2 ± 0.6 68.6 ± 0.3 68.5 ± 0.8 61.4 ± 0.4 67.0 ± 0.2</td></tr><tr><td/><td>Attack Rate (%) 30</td><td>GCN 64.8 ± 1.1</td><td colspan="8">IGCN(RNM) IGCN(AR) LanczosNet 59.8 ± 1.0 59.0 ± 0.8 53.5 ± 0.8 65.2 ± 0.4 61.8 ± 0.8 RGCN PowerLap 2 PowerLap 3 56.1 ± 1.9 65.0 ± 0.8 65.5 ± 0.7 SGC MixHop</td><td>r-GCN 66.0 ± 0.8</td><td>VPN 66.1 ± 0.1</td></tr><tr><td/><td>5 Attack Rate (%)</td><td>79.2 ± 0.3 GCN</td><td colspan="8">77.2 ± 0.9 IGCN(RNM) IGCN(AR) LanczosNet 78.0 ± 0.3 73.0 ± 0.9 79.5 ± 0.4 77.5 ± 1.1 RGCN PowerLap 2 PowerLap 3 74.0 ± 0.5 78.2 ± 0.2 80.1 ± 0.2 80.6 ± 0.8 SGC MixHop r-GCN</td><td>78.4 ± 0.2 VPN</td></tr><tr><td>Cora Cora</td><td>10 15 5 20 10 25 30 15 20 25</td><td>76.7 ± 0.7 74.3 ± 0.2 79.8 ± 0.9 72.5 ± 0.6 78.4 ± 0.7 70.2 ± 0.9 69.9 ± 0.4 77.9 ± 0.6 76.0 ± 1.4 79.1 ± 0.6</td><td>73.7 ± 0.2 70.7 ± 0.1 76.5 ± 0.1 68.9 ± 0.2 75.8 ± 0.4 66.2 ± 0.5 67.5 ± 0.8 73.8 ± 0.9 71.8 ± 1.0 77.7 ± 0.6</td><td>74.5 ± 0.7 71.5 ± 1.2 77.4 ± 0.3 69.5 ± 0.6 76.6 ± 0.3 67.4 ± 0.9 68.9 ± 1.4 76.7 ± 0.6 73.8 ± 0.3 78.7 ± 0.6</td><td colspan="3">69.6 ± 1.5 77.5 ± 0.5 74.6 ± 0.8 66.1 ± 0.0 74.6 ± 0.2 71.4 ± 1.1 75.1 ± 1.1 80.2 ± 0.7 75.2 ± 1.2 62.8 ± 0.7 72.9 ± 0.2 69.9 ± 0.7 73.3 ± 1.7 79.0 ± 0.5 74.2 ± 1.2 60.4 ± 1.3 70.9 ± 0.4 66.6 ± 1.1 58.7 ± 1.1 72.2 ± 0.6 66.7 ± 0.8 71.8 ± 1.1 79.0 ± 0.7 73.4 ± 1.7 70.2 ± 1.9 77.1 ± 0.5 71.0 ± 1.5 74.3 ± 0.7 79.7 ± 0.6 74.3 ± 1.6</td><td colspan="3">70.9 ± 0.5 76.1 ± 0.1 76.9 ± 0.1 78.6 ± 0.8 67.0 ± 0.6 73.5 ± 1.7 73.1 ± 0.2 76.3 ± 0.8 75.1 ± 1.1 79.5 ± 0.5 80.5 ± 0.8 79.8 ± 0.6 64.0 ± 0.3 72.1 ± 0.3 71.6 ± 1.0 74.6 ± 0.8 72.9 ± 1.0 78.1 ± 0.7 79.0 ± 0.1 78.5 ± 0.9 59.8 ± 0.7 70.1 ± 0.3 69.5 ± 0.6 72.7 ± 0.9 58.8 ± 0.8 70.8 ± 0.6 69.7 ± 0.3 72.9 ± 0.8 71.0 ± 1.1 77.9 ± 1.8 78.3 ± 0.6 78.2 ± 0.6 68.4 ± 1.0 76.3 ± 1.0 77.2 ± 0.2 76.6 ± 0.9 73.8 ± 1.0 78.0 ± 0.4 77.7 ± 1.0 78.9 ± 1.0</td><td>75.0 ± 0.3 80.8 ± 0.2 72.6 ± 0.3 79.2 ± 0.1 71.3 ± 0.3 69.4 ± 0.3 79.7 ± 0.1 77.6 ± 1.0 69.7 ± 0.5 79.8 ± 0.9</td></tr><tr><td/><td>Attack Rate (%) 30</td><td>GCN 77.7 ± 0.9</td><td colspan="8">IGCN(RNM) IGCN(AR) LanczosNet 75.6 ± 0.7 76.7 ± 0.6 73.8 ± 0.7 78.6 ± 0.4 73.5 ± 1.6 RGCN PowerLap 2 PowerLap 3 73.4 ± 0.7 78.3 ± 0.4 78.4 ± 0.9 SGC MixHop</td><td>r-GCN 78.6 ± 0.9</td><td>VPN 79.0 ± 0.0</td></tr><tr><td/><td>5</td><td>75.3 ± 0.4</td><td>74.8 ± 0.8</td><td>75.8 ± 0.2</td><td colspan="3">72.9 ± 1.3 76.3 ± 0.4 74.9 ± 0.9</td><td colspan="3">68.0 ± 2.7 75.6 ± 0.5 76.6 ± 0.5</td><td>76.1 ± 0.5</td><td>77.1 ± 0.6</td></tr><tr><td/><td>10</td><td>73.0 ± 0.5</td><td>72.3 ± 0.5</td><td>73.0 ± 0.2</td><td colspan="3">69.9 ± 1.0 73.9 ± 0.4 72.1 ± 0.9</td><td colspan="3">65.4 ± 2.7 73.1 ± 0.2 73.0 ± 0.8</td><td>73.6 ± 0.3</td><td>74.4 ± 0.1</td></tr><tr><td>Pubmed</td><td>15 20 Attack Method</td><td>71.6 ± 0.1 69.2 ± 0.6</td><td>68.8 ± 0.2 66.1 ± 0.2</td><td>70.4 ± 0.2 67.6 ± 0.4</td><td colspan="3">67.4 ± 0.1 70.9 ± 0.2 69.3 ± 1.0 63.7 ± 1.8 69.2 ± 0.2 67.5 ± 0.8 Meta-Self</td><td colspan="3">62.5 ± 2.0 79.4 ± 0.2 70.7 ± 0.7 60.5 ± 1.3 69.1 ± 0.7 67.0 ± 0.8</td><td>70.7 ± 0.1 69.8 ± 0.3</td><td>71.3 ± 0.9 70.1 ± 0.7</td></tr><tr><td/><td>25 30 Attack Rate (%)</td><td>68.2 ± 0.6 57.5 ± 0.9 GCN</td><td colspan="8">63.6 ± 0.3 63.7 ± 0.2 IGCN(RNM) IGCN(AR) LanczosNet 65.7 ± 0.2 61.5 ± 1.6 67.8 ± 0.5 64.4 ± 0.5 65.0 ± 1.0 62.2 ± 0.3 66.3 ± 0.2 63.5 ± 0.7 Model RGCN PowerLap 2 PowerLap 3 58.0 ± 1.2 67.3 ± 0.2 64.5 ± 0.2 56.3 ± 1.0 66.0 ± 0.5 64.5 ± 0.3 SGC MixHop</td><td>68.3 ± 0.3 66.5 ± 0.1 r-GCN</td><td>68.8 ± 0.1 67.1 ± 0.3 VPN</td></tr><tr><td/><td>Attack Method 5</td><td>66.2 ± 0.9</td><td>61.8 ± 0.1</td><td>60.9 ± 0.8</td><td colspan="3">Aabr 60.2 ± 0.2 69.1 ± 0.4 66.3 ± 0.9</td><td colspan="3">66.0 ± 1.2 69.1 ± 0.3 69.6 ± 0.4 70.1 ± 0.7</td><td>69.1 ± 0.8</td></tr><tr><td/><td>10</td><td>64.7 ± 0.8</td><td>59.3 ± 0.4</td><td>59.1 ± 0.9</td><td colspan="3">Model 57.3 ± 0.1 67.3 ± 0.6 64.4 ± 0.8</td><td colspan="3">62.5 ± 1.3 67.9 ± 0.7 67.1 ± 0.5</td><td>68.0 ± 0.0</td><td>68.2 ± 0.7</td></tr><tr><td>Citeseer</td><td>Attack Rate (%) 15</td><td>GCN</td><td colspan="3">IGCN(RNM) IGCN(AR) LanczosNet</td><td>RGCN</td><td colspan="2">PowerLap 2 PowerLap 3</td><td>SGC</td><td>MixHop</td><td>r-GCN</td><td>VPN</td></tr><tr><td/><td>5</td><td>69.2 ± 0.2</td><td>61.7 ± 0.1</td><td>60.4 ± 0.1</td><td colspan="3">57.3 ± 0.7 70.4 ± 0.8 68.3 ± 0.2</td><td colspan="3">64.1 ± 2.0 70.7 ± 0.2 70.4 ± 0.8</td><td>70.8 ± 0.5</td><td>71.6 ± 0.6</td></tr><tr><td/><td>10</td><td>67.8 ± 0.3</td><td>59.1 ± 0.3</td><td>56.3 ± 0.3</td><td colspan="3">55.0 ± 0.2 70.2 ± 0.8 66.0 ± 0.2</td><td colspan="3">59.0 ± 2.7 69.6 ± 0.3 69.4 ± 0.9</td><td>70.6 ± 0.0</td><td>70.8 ± 1.0</td></tr><tr><td>Citeseer</td><td>15 20</td><td>66.6 ± 0.4 66.4 ± 0.5</td><td>53.6 ± 0.4 49.7 ± 0.5</td><td>52.1 ± 0.4 49.5 ± 0.5</td><td colspan="3">50.7 ± 0.9 70.2 ± 1.0 63.9 ± 0.2 47.4 ± 0.8 69.9 ± 0.8 62.0 ± 0.3</td><td colspan="3">55.3 ± 2.3 69.1 ± 0.3 68.7 ± 0.4 52.2 ± 2.2 69.5 ± 0.5 67.9 ± 1.2 70.3 ± 0.2 70.4 ± 0.4</td><td>70.6 ± 0.7 70.1 ± 0.3</td></tr><tr><td/><td>25</td><td>65.6 ± 0.5</td><td>45.4 ± 0.6</td><td>45.3 ± 0.6</td><td colspan="3">44.0 ± 1.0 69.1 ± 1.0 59.5 ± 0.3</td><td colspan="3">48.6 ± 1.5 68.6 ± 0.4 67.7 ± 2.1 70.0 ± 0.9</td><td>69.7 ± 0.4</td></tr><tr><td/><td>30</td><td>63.8 ± 0.5</td><td>41.9 ± 0.6</td><td>42.6 ± 0.6</td><td colspan="3">40.5 ± 0.9 68.7 ± 1.0 57.2 ± 0.4</td><td colspan="3">44.8 ± 1.4 67.4 ± 0.3 67.3 ± 0.5 69.5 ± 0.4</td><td>69.1 ± 0.6</td></tr><tr><td/><td>Attack Rate (%)</td><td>GCN</td><td colspan="3">IGCN(RNM) IGCN(AR) LanczosNet</td><td>RGCN</td><td colspan="2">PowerLap 2 PowerLap 3</td><td>SGC</td><td>MixHop</td><td>r-GCN</td><td>VPN</td></tr><tr><td/><td>5</td><td>81.1 ± 0.1</td><td>77.6 ± 0.1</td><td>80.5 ± 0.1</td><td colspan="3">75.3 ± 1.0 81.0 ± 0.4 79.8 ± 0.4</td><td colspan="3">75.2 ± 1.1 79.7 ± 0.6 81.1 ± 0.3</td><td>80.9 ± 0.9</td><td>81.5 ± 0.2</td></tr><tr><td/><td>10</td><td>80.3 ± 0.1</td><td>76.4 ± 0.2</td><td>79.3 ± 0.1</td><td colspan="3">74.0 ± 1.7 80.0 ± 0.6 78.9 ± 0.7</td><td colspan="3">73.0 ± 1.5 78.7 ± 0.8 80.6 ± 0.3</td><td>79.6 ± 0.8</td><td>81.1 ± 0.8</td></tr><tr><td>Cora</td><td>15 20</td><td>79.7 ± 0.2 78.9 ± 0.2</td><td>74.3 ± 0.4 71.2 ± 0.5</td><td>77.7 ± 0.2 73.2 ± 0.2</td><td colspan="3">72.7 ± 1.0 80.1 ± 0.4 77.1 ± 1.2 70.5 ± 0.2 79.2 ± 0.7 75.9 ± 1.6</td><td colspan="3">69.9 ± 1.7 78.6 ± 0.1 79.7 ± 1.5 66.8 ± 2.5 78.2 ± 0.4 79.0 ± 0.4</td><td>79.7 ± 0.1 79.1 ± 0.2</td><td>80.0 ± 0.5 79.3 ± 0.6</td></tr><tr><td/><td>25</td><td>77.4 ± 0.3</td><td>64.9 ± 0.6</td><td>70.1 ± 0.3</td><td colspan="3">68.2 ± 0.6 78.5 ± 1.1 73.2 ± 1.4</td><td colspan="3">61.7 ± 2.6 77.1 ± 0.3 78.0 ± 0.3 78.5 ± 0.1</td><td>78.4 ± 0.6</td></tr><tr><td/><td>30</td><td>75.6 ± 0.6</td><td>59.2 ± 0.7</td><td>66.2 ± 0.4</td><td colspan="3">65.5 ± 0.8 77.7 ± 0.8 71.0 ± 1.9</td><td colspan="3">57.4 ± 2.8 76.0 ± 0.3 77.1 ± 0.6</td><td>77.3 ± 0.8</td><td>77.6 ± 1.0</td></tr><tr><td/><td>Attack Rate (%)</td><td>GCN</td><td colspan="3">IGCN(RNM) IGCN(AR) LanczosNet</td><td>RGCN</td><td colspan="2">PowerLap 2 PowerLap 3</td><td>SGC</td><td>MixHop</td><td>r-GCN</td><td>VPN</td></tr><tr><td/><td>5</td><td>75.3 ± 0.8</td><td>76.4 ± 0.2</td><td>75.9 ± 0.4</td><td colspan="3">75.0 ± 0.2 77.6 ± 0.1 76.9 ± 0.5</td><td colspan="3">67.3 ± 1.2 77.8 ± 0.8 78.2 ± 0.3</td><td>78.2 ± 0.3</td><td>78.6 ± 0.6</td></tr><tr><td/><td>10</td><td>74.3 ± 0.5</td><td>74.3 ± 0.1</td><td>73.0 ± 0.6</td><td colspan="3">72.7 ± 0.8 77.0 ± 0.1 75.6 ± 0.6</td><td colspan="3">64.9 ± 1.7 77.5 ± 0.9 77.2 ± 2.2</td><td>77.7 ± 0.5</td><td>77.7 ± 0.4</td></tr><tr><td>Pubmed</td><td>15 20</td><td>73.5 ± 0.7 73.7 ± 0.1</td><td>71.9 ± 0.4 68.7 ± 0.7</td><td>69.4 ± 0.0 66.2 ± 0.0</td><td colspan="3">70.9 ± 0.6 76.1 ± 0.3 74.1 ± 0.3 69.1 ± 0.8 76.5 ± 0.1 73.7 ± 0.3</td><td colspan="3">61.9 ± 1.8 76.5 ± 0.4 76.5 ± 0.5 59.4 ± 1.1 76.3 ± 1.1 77.3 ± 1.2</td><td>76.9 ± 0.4 77.3 ± 0.4</td><td>77.3 ± 0.8 77.7 ± 0.1</td></tr><tr><td/><td>25</td><td>72.9 ± 0.1</td><td>64.9 ± 0.2</td><td>63.2 ± 0.5</td><td colspan="3">67.6 ± 0.9 75.8 ± 0.3 73.1 ± 0.5</td><td colspan="3">58.0 ± 0.6 75.5 ± 0.4 75.7 ± 0.4</td><td>76.7 ± 0.7</td><td>77.2 ± 0.3</td></tr><tr><td/><td>30</td><td>72.8 ± 0.9</td><td>63.1 ± 0.6</td><td>61.1 ± 0.6</td><td colspan="3">65.8 ± 1.2 75.9 ± 0.2 72.4 ± 0.6</td><td colspan="3">55.4 ± 0.6 76.2 ± 0.3 75.9 ± 0.5 77.2 ± 0.6</td><td>76.7 ± 0.5</td></tr><tr><td/><td>Attack Method</td><td/><td/><td/><td/><td/><td>ADW 3</td><td/><td/></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>Model</td><td/><td/></tr><tr><td/><td>Attack Rate (%)</td><td>GCN</td><td colspan="3">IGCN(RNM) IGCN(AR) LanczosNet</td><td>RGCN</td><td colspan="2">PowerLap 2 PowerLap 3</td><td>SGC</td><td>MixHop</td><td>r-GCN</td><td>VPN</td></tr><tr><td/><td>5</td><td>68.8 ± 0.1</td><td>63.5 ± 0.4</td><td>65.1 ± 0.2</td><td colspan="3">60.0 ± 0.5 70.3 ± 0.6 69.2 ± 1.0</td><td colspan="3">70.0 ± 0.8 70.5 ± 0.5 70.4 ± 1.0 71.8 ± 0.3</td><td>70.6 ± 0.6</td></tr><tr><td/><td>10</td><td>68.4 ± 0.2</td><td>63.1 ± 0.6</td><td>63.6 ± 0.5</td><td colspan="3">59.6 ± 0.6 70.1 ± 0.6 69.3 ± 1.1</td><td colspan="3">69.6 ± 0.6 70.1 ± 0.8 69.4 ± 0.4 71.2 ± 0.7</td><td>70.2 ± 0.7</td></tr><tr><td>Citeseer</td><td>15 20</td><td>68.9 ± 0.1 68.8 ± 0.5</td><td>62.9 ± 0.7 63.5 ± 0.8</td><td>63.2 ± 0.8 63.4 ± 0.7</td><td colspan="3">59.5 ± 0.9 70.3 ± 0.4 69.5 ± 1.1 59.1 ± 0.8 69.8 ± 0.4 69.4 ± 1.0</td><td colspan="3">69.8 ± 0.7 70.6 ± 0.8 68.7 ± 1.4 71.2 ± 0.1 69.5 ± 0.7 70.3 ± 0.2 67.9 ± 1.4 71.1 ± 0.2</td><td>70.6 ± 0.4 70.4 ± 0.7</td></tr><tr><td/><td>25</td><td>68.8 ± 0.4</td><td>63.6 ± 0.7</td><td>63.8 ± 0.6</td><td colspan="3">59.3 ± 0.4 69.9 ± 0.5 69.2 ± 0.9</td><td colspan="3">69.3 ± 0.9 70.2 ± 0.5 67.7 ± 0.8 71.2 ± 0.1</td><td>70.1 ± 0.2</td></tr><tr><td/><td>30</td><td>68.8 ± 0.4</td><td>63.6 ± 0.7</td><td>63.8 ± 0.6</td><td colspan="3">59.3 ± 0.1 69.9 ± 0.5 69.2 ± 0.9</td><td colspan="3">69.3 ± 0.9 70.2 ± 0.7 67.3 ± 0.1 71.2 ± 0.0</td><td>70.1 ± 0.9</td></tr><tr><td/><td>Attack Rate (%)</td><td>GCN</td><td colspan="3">IGCN(RNM) IGCN(AR) LanczosNet</td><td>RGCN</td><td colspan="2">PowerLap 2 PowerLap 3</td><td>SGC</td><td>MixHop</td><td>r-GCN</td><td>VPN</td></tr><tr><td/><td>5</td><td>80.0 ± 0.7</td><td>78.9 ± 0.2</td><td>79.2 ± 0.4</td><td colspan="3">78.1 ± 0.8 80.5 ± 0.9 77.8 ± 0.9</td><td colspan="3">77.0 ± 1.4 78.3 ± 0.3 80.3 ± 0.3</td><td>80.8 ± 0.7</td><td>80.8 ± 0.5</td></tr><tr><td/><td>10</td><td>79.7 ± 0.9</td><td>78.7 ± 0.2</td><td>78.9 ± 0.4</td><td colspan="3">77.8 ± 1.0 80.1 ± 0.6 78.1 ± 1.1</td><td colspan="3">77.8 ± 1.1 78.0 ± 0.9 80.1 ± 0.2 80.7 ± 0.8</td><td>80.5 ± 0.3</td></tr><tr><td>Cora</td><td>15 20</td><td>79.3 ± 0.7 78.3 ± 1.0</td><td>77.1 ± 0.2 75.5 ± 0.2</td><td>77.7 ± 0.4 75.6 ± 0.3</td><td colspan="3">76.8 ± 1.2 79.7 ± 0.5 77.3 ± 1.2 75.7 ± 0.3 79.3 ± 0.6 76.9 ± 1.2</td><td colspan="3">77.9 ± 0.6 77.8 ± 0.5 80.0 ± 0.7 77.1 ± 0.5 78.0 ± 0.2 79.8 ± 1.0</td><td>80.3 ± 0.9 80.3 ± 0.5</td><td>80.6 ± 0.9 80.3 ± 0.2</td></tr><tr><td/><td>25</td><td>77.8 ± 0.6</td><td>75.3 ± 0.3</td><td>74.4 ± 0.7</td><td colspan="3">74.6 ± 1.8 78.7 ± 0.5 76.1 ± 1.0</td><td colspan="3">76.8 ± 0.2 77.3 ± 0.2 79.1 ± 0.7 79.2 ± 0.0</td><td>79.1 ± 0.5</td></tr><tr><td/><td>30</td><td>77.8 ± 0.8</td><td>75.0 ± 0.2</td><td>73.8 ± 0.7</td><td colspan="3">74.3 ± 1.7 78.0 ± 0.5 75.6 ± 1.1</td><td colspan="3">75.9 ± 0.6 76.7 ± 0.6 78.8 ± 0.4</td><td>79.3 ± 0.9</td><td>78.6 ± 1.0</td></tr><tr><td/><td>Attack Rate (%)</td><td>GCN</td><td colspan="3">IGCN(RNM) IGCN(AR) LanczosNet</td><td>RGCN</td><td colspan="2">PowerLap 2 PowerLap 3</td><td>SGC</td><td>MixHop</td><td>r-GCN</td><td>VPN</td></tr><tr><td/><td>5</td><td>78.3 ± 0.5</td><td>79.3 ± 0.4</td><td>79.2 ± 0.1</td><td colspan="3">76.5 ± 1.8 77.8 ± 0.1 74.8 ± 1.7</td><td colspan="3">76.5 ± 0.5 78.0 ± 0.4 78.2 ± 0.5</td><td>78.1 ± 0.7</td><td>79.0 ± 1.0</td></tr><tr><td/><td>10</td><td>77.8 ± 0.2</td><td>78.6 ± 0.2</td><td>78.6 ± 0.7</td><td colspan="3">75.3 ± 1.0 77.9 ± 0.3 74.7 ± 1.9</td><td colspan="3">77.4 ± 0.4 77.8 ± 1.0 78.0 ± 0.7</td><td>77.9 ± 0.9</td><td>78.6 ± 0.1</td></tr><tr><td>Pubmed</td><td>15 20</td><td>77.4 ± 0.4 77.4 ± 0.4</td><td>77.0 ± 0.4 75.8 ± 0.3</td><td>77.2 ± 0.3 76.3 ± 0.4</td><td colspan="3">74.7 ± 0.3 77.5 ± 0.3 74.2 ± 1.5 73.5 ± 1.8 77.8 ± 0.4 73.8 ± 1.0</td><td colspan="3">76.9 ± 0.4 77.3 ± 0.4 77.3 ± 0.8 76.3 ± 0.4 77.3 ± 1.2 77.1 ± 0.3</td><td>77.8 ± 0.3 77.6 ± 1.0</td><td>78.3 ± 0.2 78.3 ± 0.4</td></tr><tr><td/><td>25</td><td>77.2 ± 0.5</td><td>75.2 ± 0.1</td><td>75.9 ± 0.4</td><td colspan="3">73.7 ± 1.1 77.6 ± 0.3 73.7 ± 1.1</td><td colspan="3">75.6 ± 0.7 77.1 ± 0.2 77.0 ± 0.3</td><td>78.1 ± 0.8</td><td>78.2 ± 0.2</td></tr><tr><td/><td>30</td><td>77.1 ± 0.2</td><td>74.5 ± 0.3</td><td>74.6 ± 0.3</td><td colspan="3">73.4 ± 0.3 77.0 ± 0.2 72.9 ± 1.4</td><td colspan="3">74.6 ± 0.4 77.1 ± 0.3 77.2 ± 0.8</td><td>77.6 ± 0.3</td><td>77.7 ± 0.9</td></tr></table>

Table A.4: Running time comparison on a social network dataset(Leskovec & Mcauley, 2012). Illustration of evasion attack performance in terms of robustness enhancement on different attack methods (from top to bottom) for Citeseer: A abr(Bojchevski & Günnemann, 2019), DICE (Zügner & Günnemann, 2019), Meta-Self andMeta-Train (Zügner & Günnemann, 2019). Evaluated methods include IGCN(Li et al., 2019), LanczosNet(Liao et al., 2019),SGC (Wu et al.,  2019),MixHop (Abu-El-Haija et al., 2019)  andRGCN (Zhu et al., 2019). PowerLap 2 and 3 are methods that replace the adjacency matrix in GCN by its powered versions with orders 2 and 3, respectively. Positive values indicate improvement of robustness compared to vanilla GCN and negative ones indicate deterioration.

Table content: <table><tr><td colspan="6">Rate (%) 5 10 15 20 25 30 Methods Running Time (sec) Cora -30 -20 -10 0 10 Robustness enhancement (%) IGCN(RNM) GCN 78.7 ± 0.2 76.8 ± 0.3 75.3 ± 0.9 75.8 ± 0.7 77.5 ± 0.2 76.7 ± 0.6 Vanilla GCN PowerLaplacian IGCN(RNM) IGCN(AR) LNet RGCN SGC MixHop r-GCN VPN IGCN(RNM) IGCN(AR) LanczosNet RGCN PowerLap 2 PowerLap 3 SGC MixHop r-GCN VPN 76.1 ± 0.3 75.0 ± 0.4 73.4 ± 0.5 79.6 ± 0.6 77.9 ± 1.4 74.7 ± 0.7 77.9 ± 0.6 79.0 ± 0.8 79.3 ± 0.8 79.1 ± 0.5 76.0 ± 0.5 74.3 ± 0.7 71.0 ± 1.8 78.4 ± 0.3 76.0 ± 0.9 72.6 ± 0.6 76.8 ± 0.2 77.2 ± 0.1 77.8 ± 0.9 78.0 ± 0.7 74.0 ± 0.5 72.1 ± 0.4 69.4 ± 0.0 77.1 ± 0.7 74.2 ± 1.4 69.5 ± 1.2 76.6 ± 0.4 77.0 ± 0.6 77.0 ± 0.7 77.5 ± 0.9 72.6 ± 0.7 71.1 ± 0.8 69.5 ± 1.4 76.3 ± 0.5 73.3 ± 1.2 70.4 ± 1.4 75.9 ± 0.3 76.3 ± 0.4 76.1 ± 0.9 76.4 ± 0.5 73.8 ± 0.2 73.4 ± 0.6 70.3 ± 0.2 78.4 ± 0.4 74.2 ± 1.0 70.9 ± 1.0 76.9 ± 0.3 77.6 ± 0.2 77.9 ± 0.2 77.8 ± 0.1 73.7 ± 0.6 72.2 ± 1.0 66.7 ± 0.0 78.4 ± 0.5 72.6 ± 1.2 67.0 ± 1.4 77.9 ± 0.2 78.0 ± 0.7 78.1 ± 0.5 78.5 ± 0.4 6.02 6.36 3.33 7.21 5.56 18.14 0.231 11.38 6.73 7.18 5 10 15 20 25 30 Attack rate (%) Citeseer attacked by Aabr IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN -12 -4 4 5 10 15 20 25 30 Robustness enhancement (%) Attack rate (%) Citeseer attacked by DICE IGCN(RNM) IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN -12 -6 0 6 5 10 15 20 25 30 Robustness enhancement (%) Attack rate (%) Citeseer attacked by Meta-Self IGCN(RNM) IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN -12 -6 0 6 5 10 15 20 25 30 Robustness enhancement (%) Attack rate (%) Citeseer attacked by Meta-Train IGCN(RNM) IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN -25 -15 -5 5 5 10 15 20 25 30 Robustness enhancement (%) Attack rate (%) Cora attacked by Aabr IGCN(RNM) IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN -6 -3 0 3 5 10 15 20 25 30 Robustness enhancement (%) Attack rate (%) Cora attacked by ADW3 IGCN(RNM) IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN -15 -10 -5 0 5 5 10 15 20 25 30 Robustness enhancement (%) Attack rate (%) Cora attacked by DICE IGCN(RNM) IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN -12 -6 0 6 5 10 15 20 25 30 Robustness enhancement (%) Attack rate (%) Cora attacked by Meta-Self IGCN(RNM) IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN -6 0 6 Robustness enhancement (%) Cora attacked by Meta-Train Figure A.6: Under review as a conference paper at ICLR 2020 IGCN(RNM) IGCN(AR) LanczosNet PowerLap 2 PowerLap 3 SGC MixHop RGCN r-GCN VPN</td></tr><tr><td>-12</td><td/><td/><td/><td/><td/></tr><tr><td>5</td><td>10</td><td>15</td><td>20</td><td>25</td><td>30</td></tr><tr><td/><td/><td colspan="2">Attack rate (%)</td><td/><td/></tr></table>

Peer review (iclr2020):
This paper proposes a graph convolutional operator based on graph powering and applies it to GCN architecture to improve the performance and robustness. This work is mainly motivated by the paper (Graph powering and spectral robustness, Abbe et al., 2018). The authors introduce the graph powering to graph convolution neural network domain to replace the original Laplacian operator. They further propose a graph sparsification/pruning strategy on the powered adjacency matrices in order to reduce the complexity and increase the robustness against adversarial attacks. They also provide theoretical analysis to prove that the proposed powering operator and subsequent methods have some spectral properties and theoretical feasibility. However, some conclusions are limited to the ideal situations or seem subjective. Extensive experiments are conducted to show better or comparable performance in both benign and adversarial situations. There are some concerns that need to be addressed or clarified: A major concern is that the theoretical analyses in this paper are limited to graphs sampled from the SBM model. It is unclear how these analyses can be generalized to real graphs. Furthermore, the theorem 3 and proposition 5 are even limited to SBM model with 2 communities, which makes the analyses less convincing. Some of the arguments in the paper might be imprecise. For example, in Section 1.1, when discuss “why not graph Laplacian?”, a small spatial scope is claimed to be problematic. Although, it is correct for the GCN (Kipf & Welling, 2017), the powered Laplacian (mentioned earlier in the same section) does have a broad spatial scope. It would be better if the authors could provide more details about the sparsification. Specifically, how to choose the threshold (adaptively). In the performance part of Section 4.2, the improvement of the performance by replacing Laplacian with VPN is marginal (compared with the original GCN). Furthermore, the performance of VPN is close to or sometimes worse than the baseline RGCN. Suggestions: In the Informative and robust low-frequency spectral signal part of Section 4.3, it would be better if the authors can clarify the experiments setting. Is it using the low-frequency part (first few eigenvectors) to recover the signal and then using the recovered signal to perform the classification task? The titles of Figure 7 and Figure 8 are a little bit confusing. Some minor problems: There are many typos such as: “with the presence of absence of edges”, “normalizating”, “asymptotoic”, “benigh”, “ajdacency”, “sensitve”, “adajacent”, “one of the network”, etc.