Power up! Robust Graph Convolutional Network based on Graph Powering
Authors: Ming Jin
Heng Chang
Wenwu Zhu
Somayeh Sojoudi
Venue:  (2020)
Keywords: graph mining
graph neural network
adversarial robustness

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. 

Under review as a conference paper at ICLR 2020
POWER UP! ROBUST GRAPH CONVOLUTIONAL NET- WORK BASED ON GRAPH POWERING
Anonymous authors Paper under double-blind review
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 new convolution operator that provably robust in the spectral domain and is incorporated in the GCN architecture to improve expressivity and interpretability. By extending the original graph to sequence of graphs, we also propose 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.
INTRODUCTION
Graph convolutional networks (GCNs) 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- -fet----t- performances in social networks (Kipf & Welling! (017). traffic prediction (Rahimi et al., 2018), recommendation systems (Ying et al.] 2018), applied chemistry and biology (Kearnes al. 2016 Fout et al. (0177) 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 2019).
GCNs belong to family of spectral methods that deal with spectral representations of graphs (Zhou al. 2018 Wu al.) 2019). fundamental ingredient of GCNs the graph convolution operation defined by the graph Laplacian in the Fourier domain:
go * == go( [L)æ,
where R" is the graph signal the set of vertices V and ge is spectral function applied to the graph Laplacian L : D (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 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- performance of semi-supervised learning. The network has the following layer-wise update rule:
H(++1) := (AH((W
(2)
where (()) is the 1-th layer hidden state (with (1) == X as nodal features), W()) is the 1-th
layer weight matrix, y 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 al. 2018 Wu 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 natural choice for variety of spectral algorithms such as

---

Under review as a conference paper at ICLR 2020
principal component analysis, clustering and linear embeddings (Chung & Graham 1997 Belkin & Niyogi 2002). So what can be problematic?
From spatial perspective. GCNs with d layers cannot acquire nodal information beyond its d- distance neighbors; hence, it severely limits its scope of data fusion. Recent works (Lee et al. 2018
Abu-EE-Haija et al. 2018 2019 Wu et al. (0199) alleviated this issue by directly powering the graph
Laplacian.
From a spectral perspective, one could demand better spectral properties, given that GCN is funda- mentally a particular (yet effective) approximation of the spectral convolution (Ι). A key desirable property for generic spectral methods is known "spectral separation," " namely the spectrum should comprise a few dominant cigenvalues whose associated eigenvectors reveal the sought structure in the graph. well-known prototype is the Ramanujan property, for which the second leading eigen- value of a r-regular graph is no larger than 2/r - 1, which is also enjoyed asymptotically by random r-regular graphs (Friedman (004) and Erdós-Rény. graphs that are not too sparse (Feige & Ofek] 2005). In 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 9 with nodes is drawn under SBM(n, k; Ointr: (mner) if the nodes are evenly and randomly partitioned into k communities, and nodes and j are connected with probability Gintra/n e [0, 1] if they belong to the same community, and Qinter/P n E [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, n1, 2, Alntra Qmser), which is a rank-2 matrix with the top eigenvalue } (Aamm + dinter) and eigenvector 1, and the second eigenvalue 1 (Aimtr aaterr and eigenvector a such that a; = 1 if i is in community and a = -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 de- gree nodes (Kaufmann et al. 2016). Unsurprisingly, powering the Laplacian would be of no avail, because 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 can- not solve the issue. To date, the best results for pruning does not apply down to the theoretical recovery threshold (Coja- OCghl-gg 2010;; Mossel et al. [012] Le et al. (2055); 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 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 scarching 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 much broader sense. An image can
2

---

Under review as a conference paper at ICLR 2020
be viewed regular grid, yet the operation of CNN filter goes beyond the nearest pixel to local neighborhood to extract useful features. How to draw an analogy to graphs?
From perspective of robust learning, this question sheds light the basic observation that real- world graphs are often noisy and even adversarial. The nice spectral properties of a graph topology can be lost with the presence absence of edges. What some principled ways to robustify the convolution operator and graph embeddings?
In this paper, propose a graph learning paradigm that aims at achieving this goal, as illustrated in Figure [ 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 new operator based on this derived sequence.
Definition 2 ( (Variable power operator). Consider an unweighted and undirected graph G. Let A denote the k-distance adjacency matrix, i.c., [A |1] = 1 if and only if the shortest distance (in the original graph) between nodes i and is k. The variable power operator of order is defined as:
(r)
A
where 0 :.......,, a set of parameters.
Clearly, A a natural extension of the classical adjacency matrix (i.c., r 1 and 0g = 01 = 1). With power order > one can increase the spatial scope of information fusion the graph when applying the convolution operation. The parameters 0g also has natural explanation magnitude and the sign of 0% be viewed "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 proof' given in the appendix.)
Theorem (Asymptotic spectral separation of variable power operator). Consider a graph G drawn from SBM (,, 2, (lintra Cinter). Assume that the signal-to-noise ratio / / 1, where
(Minma + Qinerr and &2 [Ointra Ointer) (c.f., Decelle et al. 2011)). Suppose r on the order of c clog(n) for a constant c, such that clog(E1) < 174. Given nonvanishing 0₁ for k: > r/2, the variable power
operator (3) has the following spectral properties: (i) the leading eigenvalue is on the order of θ (1[0)) the second leading eigenvalue is on the order of θ (1]0]]155). and the rest are bounded by (log(()))) for any fixed 6 >> O: and (ii) the two leading eigenvectors are sufficient to recover the two communities asymptotically (i.e., as goes to infinity).
Intuitively, the above theoretical result suggests that the variable power operator is able "magnify" benign signals from the latent graph structure while "suppressing" noises due to random artefacts.
Original graph
Variable power graph
Node prediction
0,4!1
Graph
Graph convolution
sparsification
Figure 1: From the original graph, generate series of graphs, which weighted by param- eters that gauge the influence strengths, (optionally) sparsified, and eventually combined to form a variable power graph.

---

Under review as a conference paper at ICLR 2020
This is expected 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 new GCN architecture in Section 3 We also provide empirical evidence of the gain from this theory in Section 4 and conclude Section
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. 20188] Wu et al. 2211 [i et al., 2019). However, simply powering the adjacency does not extract spectral gap and may even make the eigenspectrum more sensitive to perturbations. Abu-EEl-Hajj et al. 20188 2019) also introduced weight matrices for neighbors different distances. But this could substantially increase the risk of overfitting in the low-data regime and make the network vulnerable to adversarial attacks.
The robustness of spectral methods has been extensively studied for graph partitionin//clustrring (Li et 2007 Balakrishnan et al. 2
Robust spectral theory.
Chaudhuri et al. AAmini et al. 2013]
Joseph 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., 2013). which provably achieve the detection threshold conjectured by Decelle al. (2011). Our work is partly motivated by the graph powering approach by Abbe et al. (2018), which leveraged the result of Massoulie (2014): Bordenave et al. (2013) 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 graph neural net- works (GNNs) (Dai et al., 2018: Zügner & Günnemann] 2019
Bojchevski & Günnemann 2019),
2018). Existing works employed 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 graph- structured data. Importantly, our approach simultancously improves performance in both the benign and adversarial tests, as shown in Figure (details are presented in Section
very few methods have been proposed for defense (Sun et al.
known techniques from computer vision (Szegedy et al., 2014
Citeszer
Cora
Pubmed
Accuracy (%)
Adversarial
60.8
70.8
00.4
78.4
70
60
78
70.5
71
71.5
$1.4
81.6
61.8
78.8
79
79.2
78.4
7866
79.8
Clean data accuracy (%)
GCN (baseline)
VPNíours)
r-GCN (ours)
Figure 2: Our proposed framework can improve both clean and adversarial (10% attack by
ADW, BBojcheskii & 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 graph G, consider family of its powered graphs, (1.))...,,.... where ((k) is obtained by connecting nodes with distance less than or equal to This "graph augmentation" procedure is similar to "data augmenta- single graph that is given, we artificially create series of graphs that are closely related to each other in the spatial and spectral domains.
tion", because instead of limiting the learning
As increase the power order, the graph also becomes more homogenized (Figure A.I In partic- ular, it can help near- isolatse 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
4

---

Under review as a conference paper at ICLR 2020
make them appear more isolated, because it inadvertently promotes nodes with high degrees or nearby loops much more substantially as a result feedback. Furthermore, the powered graphs can extract spectral gaps in the original graph despite local irreuuaaiitiss thus boosting the signal- to-noise ratio the spectral domain.
Transfer of knowledge from the powered graph sequence. Consider generic learning task graph 9 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 small set of nodes (see Table A.I), and é is the cross-entropy loss over all labeled examples. Instead of minimizing over &(W; g, D) alone, we use all the powered graphs:
(WW Σ
(el(W,g( ,D),
(r-GCN)
where 0g& 2 gauges how much information one desires to transfer from powered graph (k) to the learning process. By minimizing the (r-GCN) objective, one seeks to optimize the network parameter W on multiple graphs simultancously, which is beneficial two ways: (i) in the low-data regime, like semi- sunei-sueeeieed 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.
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 pruning mechanism.
Graph sparsification. Given graph G = (V, consider its powered version g(+) = (V))()) and a sequence of intermediate graphs glPl...., Girl, where GlA] == (V, (V,E is constructed by connecting two vertices if and only if the shortest distance is 1 in G. Clearly, { forms partition of g(r), For each node i E V/ denote its r-neighborhood by .N.(i) = (j E V do(t)) r). which is identical to the set of nodes adjacent to i in girl, 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 edge == ji, in g(r) if the value is larger than a threshold 7 (i, and denote the edge set after pruning g(r). Then, we can construct new sequence of sparsified graphs, Tl4h with edge sets Æ( = gl4 (r) and adjacency matrix A [4] Hence, the variable power operator is given by A = Ex= 0g AM, Due to the influence of high-degree nodes in the spectral domain, one can adaptively choose the thresholds Ti..j) to mitigate their effects. Specifically, we nodes with high degrees, thereby making the
choose to be a small number if either sparsification more influential in densely connected neighborhoods than weakly connected parts.
Layer-wise update rule. To demonstrate the effectiveness of the proposed operator, 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= (I+
(VPN)
where Dú, 1 e (g(i,)) 17}. The introduction of I is reminiscent of the "renormal- ization trick" (Kipf & Welling 2017). but it can be also viewed as regularization strategy in this context, which 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 factor of r.
Proposition 4. By choosing A with (VPN) in the layer-wise update rule (2). the output at each node from L-layer GCN depends neighbors within L hops.
Since we proved that the variable power operator has nice spectral separation in Theorem VPN is expected to promote useful spectral signals from the graph topology (similar to the preservation of
5

---

Under review as a conference paper at ICLR 2020
useful information in images (Jacobsen al. 2018), method preserves useful information in the graph topology). This claim substantiated with the following proposition.
Proposition 5. Given graph with two hidden communities. Consider a 2-layer GCN architecture with waser-wise update rule (2. Suppose that A has spectral gap. Further, assumee that the leading two eigenvectors are asymptotically aligned with and v, i.e., the community membership vector, and that both are in the range of feature matrix X. Then, there exists a configuration of W and (2) such that the GCN outputs can recover the community with high probability.
EXPERIMENTS
The proposed methods 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 al. 2019)) SGC (Wu 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, well as a state-of-the-a baseline and RGCN (Zhu 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 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, set the nodal features to be one-hot vectors. The label rates are 0.1 1.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 incor- poration of graph topology improves classification performance- see Theorem 3). the higher the accuracy. Overall, as shown in Figure 3 the performance of the pro- posed method (VPN) is superior than other baselines, which either use Laplacian (GCN, Chebyshev, RGCN, LNet) or its powered variants (IGCN, PowerLaplacian).
higher the SNR (i.e., <
Label rate: 0.1%
Label rate: 0.5%
Label rate: 1.0%
VPN
IGON
Accurary 1%)
Powertaplastinn
75-
Chebyshev
RGON
LanciosNat
0.6
0.7
de
0.6
077
c.o
099
0.6
0.7
0.8
0.9
MLP
SNR
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 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
SNR: 0.58
SNR:
SNR: 0.79
SNR: 0.85
SNR: 0.91
Accuracy (%))
204
VPN Adjacency
B 3 t
30-
32
33-
32
70
30
Index of frequency component ffrom low high)
Figure 4: Accuracy of first 100 frequency components of VPN (red) and adjacency matrix (blue).

---

Under review as a conference paper at ICLR 2020
Table I: 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.
Model
Citeseer
Cora
Pubmed
ManiReg (Belkin et al.
20016
60.1
59.5
70.7
SemiEmb Weston ct a.. 2012
59.6
59.0
71.1
LP Zhu cl al. 2003
45.3
68.0
63.0
DeepWalk (Perozzi et al
2014
43.2
67.2
65.3
ICA (Lu & Gétoor 2005
69.1
75.1
73.9
Planetoid Yang ct al. 2016
61.7
75.7
77.2
Vanilla GCN
Welling 2017
70.3
81.5
79.0
PowerLaplacian
70.5
80.5
78.3
IGCN(RNM) (Li al. 2019
69.0
80.9
77.3
IGCN(AR) (Li
2019
69.3
81.1
LNet (Liao ét 2019
1.9
79.5
78.3
RGCN el 2019)
71.2
0.6
79.1 0.3
SGC (Wu cf al. 2019)
71.9 -119-001
81.0 0.0
78.9 0.0
MixHop (Abu-El Haaja et al. 2019
714 0.8
81.9 0.4
80.8 0.6
T-GCN (this paper)
71.3 +: 0.54
81.7 + 0.23
79.3
0.31
VPN (this paper)
81.9 + 0.32
79.6 + 0.39
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 1-th cigenvectors) by estimating the accuracy of an MLP with filtered nodal features, namely 2. 1,, (. as shown in Figure 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 adjacency matrix cannot make accurate inferences.
4.2 SEMI-SUPERVISHH NODE CLASSIFICATION
Experimental setup. We followed the setup of (Yang et al. networks Citeseer, Cora and Pubmed (please refer to the Appendix for more details).
2016 Kipf & Welling 2017) for citation
Graph powering order can influence spatial and spectral behaviors. Our theory suggests powering the order of log(n); in practice, orders of 2 to 4 suffice (Figure 5). Here, we chose the power order to be for r-GCN on Citeseer and Cora, and 3 for Pubmed, and reduced the order by for VPN.
180 doooonn
Benign attack
10% attack
Power order
Power order
Benign and adversarial accu- racy as power order increases. Dahsed lines correspond vanilla GCN.
Figure 5:
Performance.
By replacing Laplacian with VPN, we see an immediate improvement performance (Table We also that succinet parametrization of the global in- fluence relation in VPN is able to increase the expressivity of the network. For instance, the learned f distances 2 and for Citeseer are 3. 3.13 and 3. 1e-3 with p-value less than 1e-5. This implies that the network tends to put more weights closer neighbors.
4.3 DEFENSE AGAINST EVASION ATTACKS
To evaluate the robustness of 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 Zugnerr & Günnemann 2019), Aatr and ADW; (Bojchevski & Günnemann 2019), Meta-Train and Meta- Self (Zügner & Günnemaan 2019). We further modulated the severity attack methods by varying the attack rate, which corresponds 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., fogr the Apw, attack (detailed results for other attacks are listed 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, conjectured that topological

---

Under review as a conference paper at ICLR 2020
(CCN(RNM)
ICNIARR
LanczosNet
PowerLap 2
PowerLap 3
m SGC
Mixioop
ROCN
F-CON
VPN
Citeseer attacked by ADW3
Pubmed attacked by ADW3
3
Robusiness enhancenient (%)
0
Attack rate (%)
Attack rate (%d
Figure 6: Robustness merit |ccuracy der ADW, attack. The error bar indicates standard deviation over 20 independent simulations.
paturaccyyyt-otttaaee proposed-method
post-attack
accuracy post-attack vanilla GCN
reported in percentage un-
attacks are more difficult to defend for networks with prevalent high-degree nodes, because the attacker can bring more irrelevant vertices by simply adding link to the high-degree nodes.
Informative and robust low-frequency spectral signal. It has been observed by Wu et al. (2019); Maehara (219) 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 how 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 cigendecomposition 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., & +1) (,(((++1) X. We then use the reconstructed features in MLP perform the classification task in a supervised learning setting. As Figure 7 shows, features filtered by the leading eigenvectors VPN lead to higher classification accuracy compared to the classical adjacency matrix.
For the adversarial testing, construct new basis + based the attacked graph, and then use P +., :k::(++1)-- X as test points for the MLP trained in the clean data setting. As can be seen in Figure g 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 AA.)) the enhanced benign and adversarial accuracy 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 this study.
Citeseer
Cora
Pubmed
Accuracy (%)
80
VPN
25-
65-
Ajdacency
30-
60-
25-
20-
80
60-
100
200
300
400
100
300
4000
100
200
300
400
500
Index of frequency component (from low to high)
Figure 7: Accuracy of first 500 frequency components for VPN (red) and adjacency matrix (blue). The x axis corresponds to the index & in (.,,:((++1)
$
X for signal reconstruction.
4.4 DISCUSSIONS
In this paper, proposed new graph operator to replace the graph Laplacian in the classic GCN, It worth mentioning that our approach is very different from the k-thh order polynomials of the Lapla- cian developed in (Defferrard et al.) 2016) or the high-order graph Laplacian employed in (Lee et al.) 2018 Li et al. 2019; Abu-El et al. 2019) Wu et al.) 2019). If the graph Laplacian L is pow- ered to the k-th order, the resulting matrix has the same eigenvectors L, with only the eigenvalues
8

---

Under review as a conference paper at ICLR 2020
Adj
Citeseer
Cora
Puhmed
Accurasy
45
30
25
0
0
5
10 15
20
25
10
15
20
25
30
40
45
a10
+15
+20
+25
x30
Altack rate 196)
Allack rate 17%)
Artack rate (56)
Figure 8:
Accuracy of the leading frequency components in adversarial testing.
We use
P.I I.A.A
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.
powered to the k-th order. Thus, the corresponding k-th order polynomial has the same eigenvec- tors, 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.33 for an illustration). However, our result in Theorem 3 suggests that the leading eigenvectors 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 ro- bustness") and in the spectral theory literature ("spectral robustness") appear to be different. How- ever, in this work, we argue that spectral robustness is closely related to adversarial robustness. This can be explained from matrix perturbation point of view. Let λs and Φx 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):
dΦ (
(n (2 -815))
Σ
d d ΦE.
(=1,6tk
where Ans is the (i, entry of A, ORG) is the j-th entry of Φx. 6(g) is the perturbation of the (i. j-th entry of A, and n is the dimension of A. can be seen that the perturbation the con- volutional operator is controlled by the inverse of the spectral gap. When the spectral gaps between the leading eigenvalues (i.e., Åι and X2) and the rest of the eigenvalues are large, the perturbations of the leading eigenvectors due the adversarial attack are controlled. Since the eigenvalues of the graph convolutional operator decays very quickly (see Figure as an illustration), the learned rep- resentation 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 was based on the standard SBM, which 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 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 future applications, in which case, models with more flexibility in the degree distributions, such as the degree-corrected SBM proposed by Karrer & Newman (201T), 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 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 foefureyyy spectral signal results in Figures) 7 and g 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.
classic model
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

---

Under review as a conference paper at ICLR 2020
is not robust to noisy links. For adversarial robustness, spectral separation is desirable property. We propose new operator that enjoys this property and can be incorporated in GCNs to improve expressivity and interpretability. Furthermore, by generating sequence of powered graphs based on the original graph, we can explore a spectrum of spectral and spatial behaviors and encourage trans- ferability across graphs. The proposed methods are shown improve both benign and adversarial accuracy over various baselines evaluated against comprehensive set of attack strategies.
REFERENCES
Emmanuel Abbe, Enric Boix, Peter Ralli, and Colin Sandon. Graph powering and spectral robust- ness. arXiv preprint 1409:188804888 2018.
Sami Abu-EI-Haija, Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-GCN: Multi-scale graph convolution for semi-supervised node classification. arXiv preprint 1802 2018.
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolu- tion architectures via sparsified neighborhood mixing. arXiv preprint arXiv:1905.00067, 2019,
Arash A Amini, Aiyou Chen, Peter J Bickel, Elizaveta Levina, et al. Pseudo-likelihood methods for community detection in large sparse networks. The Annals of Statistics, 41 2144)2209722122 2013.
James Atwood and Don Towsley, Diffusion-coonvoltiona neural networks. In NIPS 2016, pp- 1993-2001, 2016.
Sivaraman Balakrishnan, Min Xu, Akshay Krishnamurthy, and Aarti Singh. Noise thresholds for spectral clustering. NIPS 2, pp. 954 962,962,77 2011.
Joost Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani, and Khalil Sima'an an. Graph convolu- tional encoders for syntax-aware neural machine translation. In EMNLP 2017, pp. 1957-1967, 2017.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In NIPS 2002, pp. 585-591, 2002.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399-246 2434, 2006.
Aleksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. International Conference on Machine Learning, pp. 695-704, 2019.
Charles Bordenave, Mare Lelarge, and Laurent Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs. In FOCS 2015, pp. 1347-1357. IEEE, 2015.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In ICLR 2014, 2014.
Kamalika Chaudhuri, Fan Chung, and Alexander Tsiatas. Spectral clustering of graphs with general degrees in the extended planted partition model. Journal of Machine Learning Research, 2012:
1-23.
Jinyin Chen, Yangyang Wu, Xiang Lin, and Qi Xuan. Can adversarial network attack be defended? arXiv preprint 1903. 05994, 2019.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Amin Coja-Oghlan. Graph partitioning via adaptive spectral techniques. Combinatorics, Probability and Computing, 19(2):277284, 2010.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International Conference Machine Learning, pp. 1123-1132, 2018.
10

---

Under review as a conference paper at ICLR 2020
Chandler Davis and William Morton Kahan. The rotation of cigenvectors by perturbation: III. SIAM Journal on Numerical Analysis, 7(1):1-46, 1970.
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6):066106, 2011.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. neural information processing systems, pp. 3844 3852, 2016.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability, SIAM Journal on Computing, 48(2):742 864, 2019.
Uriel Feige and Eran Ofek. Spectral techniques applied to sparse random graphs. Random Structures & Algorithms, 27(2):251-277 2005.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In NIPS 20/7, pp. 6530-6539, 2017.
Joel Friedman. A proof of alon's 's second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc., (910), 2004.
Thorben Funke and Till Becker. Stochastic block models: A comparison of variants and inference methods. PloS one, 14(4):e0215266, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS 2010, pp. 249-256, 2010.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR 2015, 2015.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. NIPS 2017, pp. 1024-1034, 2017.
David K. Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-150, 2011.
Simon Heimlicher, Mare Lelarge, and Laurent Massoulié. Community detection in the labelled stochastic block model. arXiv preprint arXiv: arXiv::109.2200 1209.2910, 2012.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks graph-structured data. arXiv preprint arXiv:/506.05166 2015.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 109-177,, 1983.
Jörn-Henrik Jacobsen, Arnold Smeulders, and Edouard Oyallon. i-RevNet: Deep invertible net- works. In ICLR 2018, 2018.
Antony Joseph, Bin Yu, et al. Impact of regularization on spectral clustering. The Annals of Statis- fics, (4644)::655-11)) 2016.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1)x016107,2011
Emilie Kaufmann, Thomas Bonald, and Mare Lelarge. A spectral algorithm with additive clustering for the recovery of overlapping communities in networks. ALT 2016, pp. 355-370. Springer, 2016.
Steven Kearnes. Kevin McCloskey, Marc Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aiue aided molecular design, 30(8): 595-608, 2016.
11

---

Under review as a conference paper at ICLR 2020
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR 2017, 2017.
Can M Le, Elizaveta Levina, and Roman Vershynin. Sparse random graphs: regularization and concentration of the laplacian. arXiv preprint arXiv:1502.05049 2015.
James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher- order cheeger inequalities. Journal of the ACM, 61(6):37, 2014.
John Boaz Lee, Ryan Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. Higher- order graph convolutional networks. arXiv preprint arXiv: 1809.07697, 2018.
Jure Leskovec and Julian Mcauley. Learning discover social circles in ego networks. In Advances in Neural Information Processing Systems 25, pp. 539-547, 2012.
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- supervised learning via graph filtering. In CVPR 2019, pp. 9582-9591, 2019.
Zhenguo Li, Jianzhuang Liu, Shifeng Chen, and Xiaoou Tang. Noise robust spectral clustering. In ICCV 2007, pp. 1-8, 2007.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In ICLR 2019, 2019.
Qing Lu and Lise Getoor. Link-based classification. In ICML 2003, pp. 496-503, 2003.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 97Nvv)2557--2605 2008.
Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv:1905.09550, 2019.
Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. In EMNLP 2017, pp. 1506-1515, 2017.
Laurent Massoulié. Community detection thresholds and the weak ramanujan property. In STOC 2014, pp. 694-703. ACM, 2014.
Elchanan Mossel, Joe Neeman, and Allan Sly. Stochastic block models and reconstruction. arXiv preprint arXiv: 1499, 2012.
Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. arXiv preprint arX4v:3311.4115, 2013.
Tiago P Peixoto.
Nonparametric bayesian inference of the microcanonical stochastic block model. Physical Review E, 95(1):012317, 2017. 2017.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In KDD 2014, pp. 701-710. ACM, 2014.
Afshin Rahimi, Trevor Cohn, and Timothy Baldwin. Semi-supervised geolocation via graph convolutional networks. In ACL 2018, volume 1, pp. 2009-2019, 2018.
Lichao Sun, Ji Wang, Philip S Yu. and Bo Li. Adversarial attack and defense on graph data: A survey, arXiv preprint
2018
Christian Szegedy, Wojciech Zaremba. Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR 2014, 2014.
Christian Szegedy. Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In CVPR 2016, pp. 2818-2826, 2016.
12

---

Under review as a conference paper at ICLR 2020
Lloyd 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 semi- supervised embedding. Neural Networks: Tricks of the Trade (2nd ed.). pp. 639-655, 2012.
Hermann Weyl. Das asymptotische verteilungsgesetzz der eigenwerte linearer partieller differen- tialgleichungen (mit einer anwendung auf die theorie der hoblraumstrahlungg, Mathematische Annalen, 71(4):441-79, 1912.
Felix Wu, Amauri H. Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In ICML 2019, pp. 6861-6871, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A
comprehensive survey on graph neural networks. arXiv preprint arXiv: 2019.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML 2016, pp. 40-48, 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 KDD 2018, pp- 974-983. ACM, 2018.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv: arXiv:/8/2.08453. 2018.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In KDD 2019, pp. 1399-1407, 2019.
Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML. 2003, pp. 912-919, 2003.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. ICLR 2019, 2019.
A APPENDIX
A.1 PROOF OF PROPOSITION 4
To validate the claim, we prove more general result. Consider a graph G and its powered graph go),, whose adjacency matrices are A and ( respectively. Since the support of A is identical that of (r), we will focus on (r) for notational simplicity. For any signal f V + R on graph, denote the support of the signal fu on node v V by 8/, i.e., fo only depends on the signals on nodes in St. Then, it is easy to see that the signal g Af has support S C UK where ~r denotes adjacency relation on g()) defined by A Clearly, the set defined by (u V ~yy u) identical to {u E dg(u,)) I r), where dg(u,v) denotes the shortest. distance from to on G.
(r)
Also, we see that element-wiss operation does not expand the support, i.e., for any element-wise activation a, the signal 9-r A a(f) has support Sg- C S/c particular, we can prove the claim by iteratively applying the function composition layer by layer, since each layer is of the form a (A,)) (r) ((W)()), where (!)) the hidden state at layer and ('!) the corresponding weight matrix. Hence after L iterations of layer-wise updates, the support of the output on v is given by (u E du v) Lr+
A.2 PROOF OF PROPOSITION 5
Let >; and Ae be the two leading eigenvalues with corresponding eigenvectors Φi and do respectively. Without loss of generality, assume that both eigenvalues nonnegative. Under the
13

---

Under review as a conference paper at ICLR 2020
assumption that Φ1 and Φ2 lie in the range of X, there exists W such that XW
=1Φ Φ2).
So the output of the first layer with ReLU activation is given by:
H (AxW())
(A Φ21)
(4)
((i((1)) (20(02)
(5)
(1
d + 11 + (h2))] where ||hi| ||
d(1) and |/2|| ((1)
(6)
where (5) is due to the definition of eigenvectors and that a is an element-wise operation, and (
due to the asymptotic alignment condition and the fact that o(v) - 1 Therefore, by
choosing the last layer weight (
the output of the last layer is given by:
Y AH (
A [Ai(1 + o(hi))
224 + - = W
A h1
22 / 11 h/y w(22
| h"
-U+
where || o(1), ||'ll o(1) for k 1.2. Therefore, after the softmax operation, we see that the 2-layer output recovers the membership of the elements exactly.
One general remark is that while the above argument is not limited the leading two eigenval- ues/cigenvectors, from the form of (2) whose elements depend inversely on the corresponding eigenvalues, we can expect more numerical stability (and hence easier learning) when the corre- sponding eigenvalues are large.
A.3 PROOF OF THEOREM 3
Consider a stochastic block model with two communities, where the intra-community connection probability is asuaaa 'n and the inter-community connection probability is Qmter/ n, and assume that Oittr > Ginter- Let & = tamer and & Guin -amea which correspond to the first and second eigenvalues of the expected adjacency matrix of the above model. Let denote the community label vector, with v = +1 depending on the membership of node i. For weak recovery, we assume the detectability condition (Decelle et al. 2011):
2
2
3 > E1
With the notations from the main paper, let A!² = Ei=o A denote the w-weigtted variable
[1 if (g. =
power operator, where [A ky
is the k-distance adjacency matrix. Let
0 o.w.
A (k) denote the nonbacktracking path counting matrix, where the (i,j)-th component indicate the number of self-avoiding paths of graph edges length connecting i to (Massoulié 2014). Our goal is to prove that the top eigenvectors of A are asymptotically aligned with those of A (A) for greater than log(n) up to a constant multiplicative factor. To do so, first recall the result of Massoulie 2014), which examines the behaviors of top eigenvectors of A (k).
Lemma ([Massoulić) 2014)). Assume that holds. Then, w.h.p., for all E (r/2,..,,Th r):
(a) The operator norm A (k) || is up to logarithmic factors OgE)). The second eigenvalue of A (k) is up to logarithmic factors ((E)).
(b) The leading eigenvector is asymptotically aligned with (4) (k) A [
A [k)1
+ he
| A ( 1
A 1
where | = o(1). The second eigenvector is asymptotically aligned with A (k) p:
A (*) A (k)
A
+ h2g |A
A [+) A 1
where | o(1).
14

---

Under review as a conference paper at ICLR 2020
Now, we first define
r
Ek=r/2 02 Aik),
Ag rr
p 0
(r) + A
= 0 + A
(
(7/2-1)
+ Σ 0c(A Ath)).
0
kmr/2
Also, by Massouuii 2014 Theorem 2.3), the local neighborhoods of vertices do not grow fast, and w.h.p., the graph of A has maximum degree O(5T nl)) Let Φ be the leading eigenvector of (0/2-11, and let v the node where & is maximum (i.e., <(v) 2 d(u)). Without loss of generality, assume that Φbv) > 0. We have good control over the first eigenvalue λ of Ag (r/2-1) as follows:
(A 11/2-11 ())
11122-10))111
Ex'2 Σ ((und(( O2Q(u)
A1
((v)
6(v)
r/2-1
o(u)
bx
Φ(v)
k=U
(n.dg(u.))
(u,))
r/2-1
10xl
(undg(u,))=k)
|
Σ
(vodg(M.))5//2-1)
o(110)) (log n))
Due to Abbe et al. 2018 we know that w.h.p., .. for r = elog(n), we can bound the last term by
Theorem 2), which proves identical result of Lemma 6 but for AlR)
Σ 0 (A 14
(k) 1|2
[6u| A
A (k) l|2
(10111 / ())g)))
(1)
k=
Therefore, by triangle inequality, conclude that
A (r) 2l
|A r 112 O 0 (logn)*) (100)15(((1ogn))
(r)
(8)
Now, our goal show a similar result Lemma 6 for r(()) In particular,
[m(())
A011122
16
1tr
Σ O
( (R)
(9)
|4(1/
|
k=r/2
1k)
A
A 1
Σ 6 (A))
(k)
+0 Σ
10 A [k) (
(10)
A
|AC1| 1
[A(1
k=
k=r/2
1
Σ
0g A (M)
Σ
10 1st 8
(11)
|A
2=1/2
k=r/2
A 1
0g (AA (M)
(11011
(12)
A 1
k=r/2
A [k)
[k] (1)
1
Σ 0g
+ h4
+0(101155n=+
for |/ l|2 = o(1)
[|A
1
A [1k]
k=r/2
(13)
15

---

Under review as a conference paper at ICLR 2020
5
A f
||A A (k)
Σ 0K
+ hs
+
|
| 1
1/
12
(1)
1)
||A A (1) 1 22
A A
A [ 1
Σ 02
+ +0 (110)
(101)
|| 1|
|
|
Amr/2
(14)
A (r
||A A (8) 1 |A(*)]] 1/12
Σ 0k
+ hk
+0 (10111157
(15)
|| (r/
22
A (k)
A ( 112
|0&l
(1+ o(1) +0 (110115Tn~9)
(16)
||A(*)]|22
k=r/2
(110)115T
(17)
where 10 and (44 are due to triangle incqualities, (11) and (15) are due to results in (Massoulid
2014 and 13) is due to Lemma 6 Therefore, we have ||] A Arh 1 e (11)) 111))
Similarly, we can prove that || A (II0)I (1
Furthermore, we can show that r satisfies the weak Ramanujan property (the proof is similar to (Massoulié (014) and is deferred to Section A.4).
Lemma 7. For any fixed > 0, r satisfies the following weak Ramanujan property w.h.p..
| ul12 11011n & 2 (log(())
sup ||
A Air
At)p=0
By Lemma the leading two eigenvectors of r will be asymptotically in the span of A and A (r) according to the variational definition eigenvalues. By our previous analysis, this means that the top eigenvalue of r(*) will be θ ([])]]1T) with eigenvector asymptotically aligned with A 1r) Since by (Massoulié, 2014, Lemma 4.4), A and Air) are asymptotically orthogonal, the second eigenvalue of r will be e (((0)))5)) with eigenvector asymptotically aligned with A (r)
Since the perturbation term || fr 1|2 = (AT(1)))) by ( using Weyl's inequality (Weyl 1912).
we can conclude that the leading eigenvalue A [A (r) = θ ([1)])εT), the second eigenvalue
A2 (r) = θ (10) ()),, and the rest of the eigenvalues are bounded by |00|ingg|/ (log(()))
(r) 0 ll2 = (max (((()))) X2 (r(rr) - >s(r!r)))) by the
Moreover, since ||
Kahis-Kahan Theorem DDavis & Kahan 1970). the leading two eigenvectors of A (?) are asymp- totically aligned with A and A which is shown to be enough for the rounding procedure of (Massoulie 2014) achieve weak recovery.
A.4 PROOF OF LEMMA 7
Denote À =
Gazza
[11' + tD 1 + (11T - TV as the expected adjacency matrix con-
ditioned community labels v. Let Ps, denote the set of all self-avoiding paths if = {io. ig}
from i to j. such that no nodes appear twice in the path, and define Q [m) : Exn E Er; II.e m A
Á) Dimne . Let T be the concatenation of self self-avoiding paths it -k-m and k-m++1 and let R. denote
1y \ Pay- Define iik : ESSERY IE= (A - A)se 24, im-m I - m (A), sr 184
16

---

Under review as a conference paper at ICLR 2020
Citeseer
Cora
Cumulative distributtoo
Increase power oeder
Cumulaaive distrilautiion
Increase poiver order
0.8
0.8
0.4
0.4
Zoom in
0.2
0.2
Zoom
2000
1030
2000
3000
Degree
Degree
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 in- crease the powers.
Then, by Massoulié 2014
Theorem 2.2), have
A ( Q()) + Σ (Q(mm))
AA (m
Σ w (km))
m=1
m=1
Hence,
r(r) = Σ A
k=r/2
= Σ (.Q(M))
Σ Ok Q1)kmm) AA (m-1)))
Σ
Σ
0g w (k.))
+
k=r/2
k=r/2
m=1
k=r/2 m=1
=
Σ k=r/2
(CQ(
+
B (.Qih=m) A
(m-1)
0g W (km)
m=
k==max(r/2mm (2,,m)
kmr/2 m=11
In particular, for any u that is orthogonal to A (m) and A (m) with norm-l (i.e., a feasible vector of the variational definition Lemma 7p. we have:
( (r) u
Σ QRQ k=T/2
Σ
Σ
10xlp (Qik-mi)
S
m=1 (=max(r/22m)
Σ O2 kmm/2
w (k.)
+
Since by
Massoulié 2014). the terms p (Q(1)) and p (W(km)) are bounded by n n=
ĀA (m- l) is bounded by O(log(n) + (log(n)er ) with some elementary calculations, we have that [r(r) is bounded by ||0||inng//3 (log(()).
2
Table A.I: Citation datasets. Label rate denotes the fraction training labels in each dataset.
Dataset
Nodes
Edges
Features
Classes
Label rates
Citeseer
3,327
4,732
3,703
6
0,036
Cora 2,708
5,429
1,433
7
0.052
Pubmed
19,717
44,338
500
0.003
A.5 MORE EXPERIMENTAL DETAILS AND RESULTS
Experimental setup. We followed the setup of (Yang et al.
2016 Kipf Welling 2017
for ci-
tation networks Citeseer, Cora and Pubmed. The statistics of datasets is in Table A.1 Degree
17

---

Under review as a conference paper at ICLR 2020
distribution in the original graph and the powered graphs for Citeseer and Cora is shown in Fig-
ure A.II] We used the same dataset splits as in (Yang et al. 2016 Kipt & Welling 2017) with 20 labels per class for training, 500 labeled samples for nyper-parameter setting, and 1. 000 samples
for testing. To facilitate comparison, we use the same hyper-parameterss as Vanilla GCN (Kipí & Welling. 2017), including number of layers (2), number of hidden units (16), dropout rates (0.5), weight decay (5 x 10 10= and weight initialization following (Glorot & Bengio 2010) implemented in Tensorflow. The training process is terminated if validation accuracy does 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 x 10 to stabilize training. For VPN, we consider two-step training process, i.e., we first employ graph sparsification on adjacency matrix A A based on X for the first-step training, then process second graph sparsification on adjacency matrix A 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 ag to be 0.5 for the corresponding power order and 0 other wise in r-GCN.
To enhance robustness against evasion attack, we adaptively chose the threshold of graph sparsifica- tion. For each node, we consider all its neighbors within r hops, where 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 * d neighbors with the smallest distance are selected, where 8 is the sparsification rate, and d is the degree of the node in the original graph. If this node is high-degree node (determined by if the degree is higher than the average degree by more than standard deviations), we set = 1: otherwise, we set s to be a small number slightly larger than 1. Nevertheless, to this parameter. In addition, one can define their own distance function that better measures prox- imity between nodes, such as correlation distance cosine distance. As a side remark, can easily obtain (rr with [[(I + AY" > O). and recursively calculate A The proposed methods have similar computational complexity as vanilla GCN as a result of sparsification.
do not observe that the robustness performance is sensitive
(a)
Citeseer
Cora
Pubmed
Spectral coefiicient
power 2
power
00
00
power
2000
5050 1060e robco
Index of eigenvalues
(b)
Citeseer
Cora
Pubmed
Spectral coefficient
power
0.5-
0.2
power
power
0.
06
power
-0.3
2000
5050 1nl0o rolon POC
power
Index of eigenvalues
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.
Revisiting SBM. To obtain networks with different SNRs (0.58, 0.68, 0.79, 0.85, 0.91), we set the intra-degree average aintra = 2.1 and inter-degree average ainer to be 0.4, 0.3. 0.2, 0515, 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 the proposed operators have nontrivial spectral gap. This is not enjoyed by other operators, so is a quite unique property. Furthermore, our learned operator w/ w/o normalization obtained 81 % accuracy based
A.gureA.331m
18

---

Under review as a conference paper at ICLR 2020
Powered normalized Laplacian r5 1/2 ATD.
Adjacency A
Nomaalized Laplacian D 11/2 11/2
Variable operator re (2)
Nommllized
D 30 1011
in (3) main text
Eigenspec tram
Leading eigencaliss
Leading elgensalees
Spectral gap
Spectral gap
2:4
Spectral clustering
41
002
02
800
920
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
D-212 AD-1/2, powered normalized Laplacian
I D, 1/2 A D, 1/2 (D, is the degree matrix of AT), VPN A (r) with order 5 (0) is when =
and 0.1 otherwise), and the normalized version D D-1/2(1 + A (r) D 1/2
(a) Citeseer
(b) Cora
(c) Pubmed
Figure A.4: t-SNE visualization of network embeddings learned by r-GCN.
on the second eigenvector, whereas adjacency matrix catches "high-degree nodes" and normalized (or powered) Laplacians catch "tails", with spectral clustering accuracy only 51%.
Visualization of network embeddings. We used (-SNE (Maaten & Hinton 2008) to visualize the network embeddings learned by r-GCN (Figure A.4) and VPN (Figure A.5) for Citeseer, Cora and Pubmed. As can be seen, with very limited labels, the proposed methods can learn an effective embedding of the nodes.
Evasion experiment. Five representative global adversarial attack methods are considered com- parisons:
DICE Züggnrr Günnemann, 2019) (remove internally, insert extemaaly):: it randomly disconnects nodes from the class and connects nodes from different classes.
19

---

Under review as a conference paper at ICLR 2020
(a) Citeseer
(b) Cora
(c) Pubmed
Figure A.5: t-SNE visualization of network embeddings learned by VPN.
Aabr and ADW, [Bojchevski & Günnemann, 2019) both attack methods are matrix per- turbation theory based. Apw, is the closed-fore form attack for edge deletion and Aabr is the add-by-remove strategy based method for edge insertion.
Meta-Train and Meta-Self (Zügner & Günnemann, 2019); both attack approaches are meta learning based. The meta- meta-gradient approach with self-training is denoted as Meta-Self and the variant without self-training is denoted as Meta-Train. Note that both attack methods result in OOM (out of memory) on Pubmed, we choose to report the performance against them only Citeseer and Cora.
We provide the post-evasion accuracy in Table A.2 and Table A.3 and robustness enhancement in Figure A.6 Figure A.7 and Figure A.8] for Citeseer, Cora, and Pubmed. Results are obtained with 20 random initializations on given attacked network.
Computational efficiency. The adjacency matrix could be much denser after being powered several times, which poses general challenge for all high-order matrix bbseed 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, introduce running time comparison periment on the real world social network (Social circles: Facebook) (Leskovec & Mcauley (0122). 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 sig- nificantly when the dataset is not too large. Moreover, this paper, our primary goal improve the robustness. We leave the solution to resolve the scalability issue future direction.
20

---

Under review as a conference paper at ICLR 2020
Table A.2: Summary of evasion attack performance on DICE, Anhr and Apws in terms of post- evasion accuracy (in percent). Best performance under each setting in bold.
Anaak Methal
INCE Madel
86.5-1.0.7
64.1
61. 1.64
65.9 07
06-6 1.1.5
19-9 1.0
70.5 1.0
10.01111
10
00.14:00
51:600
2.44
07.5-005
02.5+004
620-01 0.4
07.5 6.0.
07.7
08.6 2:
02.1+00.
Choser
25
00.0:1:00 0.6
54.0002
54. 2.3
6.8
65.2
5855 122
03.12 2.03
6.
05.9 0
30
07.54+
11.0=03
50 0:07
0..5
00:3::05
57.44-03
11.3 1.9
600000077
61.4
Astck Rate (8)
(OUNARII
LacaosNet
Pap
Powerlap
MisHlpp
LGCN
79:2-4-00 0.5
17.2
0500-003
T30 6:0
79.5-001
775-4-111
7L0-05
T8-7 4-0.
ME1 1-03
M0.6
T8-1--02
10
70.7 0.7
13.7 0.3
74.5 0.7
10. 1-5
17.5 8.5
T1. CLS.
70.0 055
70.1 0.1.1
70.9 70994-0.1 0-0
T5.6 0,8
15.0--00 8.8
15
74.3 0333::00 0.2
70.1 m..
715=12
0.0
74.6 0.2
1144333
67.0=00 0.
73.5 5:
T8.1 0.0
70.5 2 0.5
724 2.5
Ora
30
1.0.1
67.5
56.0
58.7
0.6
05.7
38.6 0.8
70.5
19.7 0.3
T2.9
1.0.
Antsk Rute (%)
GCN
IGCNIRNMM
(OCNUARI
LanconiNet
XOCN
Powelaap2
Powerlap 3
SOC
MixHlpp
EOCN
VIN
10
Ta0:022
72.1400.
15
T1.
9:1
68.8
074
70:0002
1.0
62:0200
Pobmnd
20
00.2 3.6
02
176204
16.7
69.5 -0
07.5
00.5
05.1 4.07
07.0 0.0
70.1
Model
Anack Rate (8)
GUN
IGUNIRNM)
IGUNARII
LancnoNe
ROKN
Powntaap
Powertap
SCC
Mistlip
KGCN
VPN
10
67.3 1.0.5
58.1
16. 0.3
76. 1.8.8
050.1.03 0:2.1:62
10.0 277
09.6 0.0.5
09.4 1.0.
10. 1.0.9
10.8
15
53.6004
121 2:4
0.
10:3=11
0.0
23.8=23
05.1 6.03
0.
70.6
20
00.44 0.5
10.7 05
005-0.
47.4 0.5
0200400
12.512 22
05.5 6.05
07.0 1.8
70.3 0.3
701 001
0.4.
2.44
Artack Rate (%)
GCN
IGUNIRNM)
LOUNARII
LaxcosNNet
ROCN
Powe
Powerlap 3
SGC
MisHlpp
rGCN
VEN
0:44
0.0.
81.5
18
79.7
11. 0-1
TT 1.0
0.0
77.1 1-12
68.9
784 8.1.
75.7 1.5
8.6.
ML.0 0.5
20
78.0
71.2
722
0.2
79.2
26
78.1 0
0.
25
77.4-:03 3.8
70.1 2.0.
18:22.6
78.6-111
73.2 1.4
61.7=20 2.8
77.1 0.8
7800 0.3
78.6- 0.1
784206
75/0
59.2
77-7 L.B
7E.0 1.1.
$9.4
70.0
TELL 1.68
TT.
Artcck Rate (9)
GUN
IGUN/RNMM
IGUNVARA
ROKO
Powettap
Powortap
SPOC
Mistlep
HGON
15.3 0U5
78.5 8.2
1.9.0.
1..2
23.8 U.L.
10U 1.0.5
67.5 1.2
77.8 LLB
18.3
18.2
T8. 0.5
0.6
1.0.5
T5. 1.66
V2.5
74L
hulmndd
20
08.1
=84--11
70.3
77.1
15
12.9
64.=002
6..5
01 0.9
78.8 8.
13.12.65
$8.0200 08
18.5 0.4
15.2
10.7 0.7
11.2 0.3
30
72.3 0.0
68.1:00
51.1 2.0.8
06.8 1.2
75.0 0.2
12.4.:06
38.4 0.
78.2
0.
15.0..0...
17.2 4 0.6
16.7 2.5
Anai Methel
Ann.
Model
Aracck Rate (8)
GUN
(GUN/RNM)
(GUNVARI
Lancoden
ROCN
Powetap
Powertap
S0a
68.8
65.5
56.1 0.0.
1.0.0...
20.3 1.16
89.3 1.0
20.0 0.8
70.5 U.S...
10..1.1000
71.8 0.3
10.4 1.5
0.8
1.6.5
49.6
Cheseer
20
4.0
03.5=08
13.
56.1
09.5 6.
09:44:1.
685=077
67.
71.1 0.2
71.4+
25
08.8--33.4
03.6007
13 0.8
2..1
08.0-:0.5
09:20-0.
68.-000
70.2 2:00
71.2 677-4-05
71.1
30
08.3.1 0.4
68.6
08..
10.3..0.11
06.0-2....
m....:0..
69.8 0.
70.2 70.2 0.7.
60.3..0..1
11.3 0.0
ML.1
Mistlep
50.2
78.9=22
2.24
0.5
80.5
22.0 1.4
78.1 8.0.5
$0.1
80.8
0.77
80.8 0.5
10
70.7 2 0.9
78.7 m.2
78D 2.0.
12.8 1,0
80.1 2:000
78.1 1.1
17.8 1.1
78.6 0.0
801
80.7
0.6
79.3
88
0.4
70.
0.5
72.3
77.8
77.8
900 6-67
N0.
Clea
25
744
76.1 3.0
76.8
70.3
0.
30
77.8- 3.5
70.0
1.
75.0 0.5.
70.6 3.3
70.9 0.
76.7 2:
78.88:044
71.3
T9.6 1.0
Antcc Rate (%)
GUN
IGUNIRNM)
IGUNAAY
LancmooNn
REKNN
Prwortap Pp
S00C
Mistlop
FGON
VPN
78
78.3
7.874:177
0.44
0.77
10
17.8 0.2.2.02
86.00.
18.3 1.0
27.0-:05
742 1.10
27.5 0.4.2.04
18
0.0.
18.6 0.1
15
17.4
21.0
w2300.3
141 1.03
17.5-100 0.5
1 15
76.00. 0.4
77.3 0.
11.8 0.5
18.5 0.2
Pubasd
20
77.4
75.8
745 1.5
7184+100 1.0
703-10
77.3 118
17.1 6:04
77.6 1.0
78.8 1...100
17.1
21

---

Under review as a conference paper at ICLR 2020
Table A.3: Summary of evasion attack performance Meta- Train and Meta-Self in terms of post- evasion accuracy (in percent). OOM (out of memory) for both methods on Pubmed.
Atack Method
Meta
Model
Rute (8)
LOCNAARI
LacasiNei
P
Powerlap
MinHlp
08:-08
15:1:11/2
57.7 4:0.
09:3
06444-3
6LB=11
70:04:0:3
000-4-06
10
00.0 1.0
51.0=111
61 11:44:1..0
5..4.-0..3
68.3 U.7
03.2 4.00
61:8- 1.4
08.3 4.0.
08. 1.0
4.044.
01.4 1.0
15
00.1 21 0.6
60.0 110=111
1.1
67.5
64.4 1.5
60.011 19
00:1 8.8
623
15.6-2-0..3
Cheseer
02.7
168=26
0.6
10
16.0 0.08
53.5
65.2
61..1.00
36.1
03:0 0.6.
6.7
86.1
Anzck Rate (8)
GUN
IGUNIRNM)
IGUNTARI
LanonoNee
ROKN
Poweraap3
Powertap
SCC
Mistlpp
GGCN
VPN
10
78.4 0.7
15.8 0.3
13.3
79.0 0.5
76.2 3.2
72.9
18.1 0.
79.0 0.
18.5 1.0.9
T0.2
15
77.9 0.6
=
76.7 0.6
T18 1.1
72.000
T3.
71.0 1.1
17.5
79.1
70.7 0.1
20
70.0 1.4
71.8
788 2-0.3
70.2
77.1 8.0.
T100
68.4 1.
76.1 1.0
70.6 0.9
mm
1.0.8
Model
Asssk Roie (%)
(GUNIRNO6)
IGUNAAIO
Lacos/Ni
Pwenlap
Poweriap
SCA
Minllep
HGON
06.3 0.9
51.8
0:331:0.3
09:11 0.1
06331-00
66.0 1.2
09.1
1:05
1.0
70.1
18:1-100
10
64.7 + 3.5
=
20.1 20.
0.1
67.8 Bu6
64.4
62. 1.3
0:5
0:
08:0
0..3
15
64.0 22 3.9
58.1 2.0.
632220.2
1:5-200
025-2:3 1-7
60002002
06.1 2.00
0:2104
07.5
00:203
Chenzer
0.2
386-11
63.3
6.1
30
55.=0
00.14:1.
17.5
4:..
6.
Anusk Ruze (8)
GCN
IGUNIRN30
(OCNNARI
LavcsolNet
RGCN
Powelapp
Powerlap
SOC
MidHlp
VPN
T23
1:
0:
16001-0.
72:0006
8.0.8
1..0
15
15.3 0.9
74.
22.4
0..00...
77.1 2.0.7
142 1.4
685 122
18. 0.0.
7.7
11.5
20
10.3
0.7
711 1.0
1.4
76.5
73.3 1.2
704 1.4
75:5 0.
00.1
00.1 0.0
10.42:03
77.5
8.
734-00
7033 0-3
710
70.
76.5 4-03
TT.9
T7 7
Table A.4: Running time comparison on a social network dataset
(Leskovec & Mcauley 2012
Methods
Vanilla GCN
PowerL.aplacian
IGCNIRNM)
IGCNIAR)
LNet
RGCN
SGC
MixHopp
rGCN
VPN
Running Time (500)
6.02
6.36
3.33
7.21
5.56
18.14
0.231
11.38
6.73
7.18
22

---

Under review as a conference paper at ICLR 2020
Citeseer attacked by Aabr
(CCNIRNM) (CCNIAR)
aancoosNet Powerl
Powerlap
m SGC Mishtop BROCK
BAGO WVN
enhancent enhancement incemeet (%%
Robustness
10
Attack rate (%)
Citeseer attacked by DICE
(GUNIRNM) BIGENAR
Lanczoshett
2owerLap
Poweriap BSOC MixHop BROON
BFOON
Robustness enhancementt 1%)
-12
10
Attack rate (%)
Citeseer attacked by Meta-Self
IGCNIRNMI IGCNIARI anchosNett Pooerlap? ap
Prwerlap 3 MixHop
WOOO
WNGGN
VPN
enhancement (%6
Rohustness
-6
-12
5
10
15
20
25
30
Attack rate (%)
Citeseer attacked by Meta-Train
(GCNIRNM) IOCNIARI
Net
2 Powerlap a SSCC
MoxH
BROON
GCN
VPN
enhancement (%)
Robustress
10
15
20
25
30
Attack rate (%)
Figure A.6: Illustration of evasion attack performance in terms of robustness enhancement on dif-
ferent attack methods (from top to bottom) for Citeseer: Aatr (Bojchevski & Günnemaan 2019)
DICE (Zügner& & Günnemann, 2019) Meta-Self and Meta-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-
al. 2019 and RGCN (Zhu et al. 2019). PowerLap 2 and 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.
23

---

Under review as a conference paper at ICLR 2020
Cora attacked by Aabr
(GCNIRNM) ICCNNAR a LancanaNet
Poweriap 2 Powarlap 3 sSCC wissHop BROEN ar-GNN WvPN
enhancement (%)
Robustress
-5
-15
5
10
15
20
25
30
Attack rate (%5
Cora attacked by ADW3
ICCNNRNNI KGONIAR
2 BRower ap BSGC Boistop BROON BOON
enboncement (%6
Robustness
-6
Attack rate (%)
Cora attacked by DICE
#IOGNRNMI RIGNNARI LancaooNee Pooerta Poweriap BSGC mMidd RROCN BOONN VP
Robustress
enhancement
-5
-15
10
15
20
25
30
Attack rate (%)
Cora attacked by Meta-Self
WIGUNINMI BIGENARI IN LanczooNer Poowrtap 2 Powert.pp MSUU WMiil ROCN WFONN VIN
Robusiness enhancemeent (%)
10
15
20
25
30
Attack rate (%6
Cora attacked by Meta-Train
IGCNIRNMO (CCC/AAR) Lamcmnnher 2onnelap2 Posoeelpp WSCC
Mistia
ROON
MIGGNN
enhancerent (96)
Robusiness
-6
-12
15
20
25
Attack rate
Figure A.7: Illustration of evasion attack performance in terms of robustness enhancement on dif- ferent attack methods for Cora.
24

---

Under review as a conference paper at ICLR 2020
Pubmed attacked by Aabr
JOCKIRNMI
PowerLap
Powerlap
MisHHop
RRGN
Robustress enhancement (%)
5
10
15
20
25
30
Attack rate (%)
Pubmed attacked by DICE
IGUNNRNM) BIGENAR
LanczodNee
Powertap 2 in Powertap
BSGC
MixHop ROCN BGGGN
VPN
enhancenennt enneentntt (%)
Robustness
-12
Attack rate (%6
Figure A.8: Illustration of evasion attack performance in terms of robustness enhancement on dif- ferent attack methods for Pubmed.
25


Reviews:
[{"review_id": "ryg6Ve_tuB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new architecture for graph convolutional network based on graph powering operation which generates a new graph based on the shortest distance between pair of nodes.  Its main motivation is to overcome the dominance of the first eigenvector in the existing GCN architectures based on the graph Laplacian operator. The theoretical evidence for the robustness is provided based on the signal-to-noise (SNR) ratio of the simplified stochastic block model (SBM). Two versions of the algorithms are proposed, namely the robust graph convolutional network (r-GCN) and variable power network (VPN). First, r-GCN is based on augmenting the graphs with graph powering operation. Next, VPN replaces the adjacency matrix of the graph convolutional operator by the newly proposed variable power operator. An additional sparsification scheme is proposed since the graph powering operation densifies the original graph.  \n\nOverall, I like how the paper addresses the weakness of the existing graph Laplacian operators (dominance of the first eigenvector) and proposed a new method with theoretical justifications. Experiments were conducted thoroughly and results look great in the presented datasets. However, I also have concerns about the paper that I feel necessary to be resolved. \n\nMost importantly, the concept of \"robustness\" in GCN seems to be inconsistent throughout the paper.  Namely, the meaning of robustness in the neural network (adversarial robustness) and the SBM literature (spectral robustness) are different. This point is crucial since the paper use the spectral robustness for justification of the method, yet experiments are done on the adversarial attacks. More specifically, adversarial training methods for neural networks, e.g., adversarial attack methods [1] considered in the paper, typically make the loss function (or output of network) more persistent against the small perturbation of inputs. On the other side, the robustness for SBM models, e.g., Theorem 3 in the paper, cares more about the preservation of the original input characteristics. For illustration, an invertible neural network [2] is not necessarily robust to adversarial attacks (the first meaning of robustness) but preserves all the input characteristics (the second meaning of robustness). \n\nI also hope the paper could have done the experiments on more datasets since there exists some evidence on the unreliability of evaluations on citation networks [3].  However, I do not think this point is critical since the paper did a great job of evaluating the robustness in various aspects and they all show consistent improvement.  \n\nMinor questions and suggestions: \n- The acronyms are slightly confusing to understand at first sight, since they first appear at the equations without any information on what the letters stand for.  Something like a \"variable power network (VPN)\" would make the paper more pleasant to read.\n- In the r-GCN framework, there might be an edge case where the powered graph is almost identical to another graph. Would there be any justification for avoiding this?\n- In the r-GCN framework, the terminology distillation is slightly confusing. Was this choice of word used for making a connection to the knowledge distillation [4]? How is the knowledge distilled between graphs? \n\nReferences\n[1] Bojchevski and Günnemann. Adversarial attacks on node embeddings via graph poisoning. ICML 2019\n[2] Jacobsen et al., i-RevNet: Deep Invertible Networks. ICLR 2018 \n[3] Shchur et al., Pitfalls of Graph Neural Network Evaluation, Arxiv 2018\n[4] Hinton et al., Distilling the Knowledge in a Neural Network, Arxiv 2015", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1gRE3E6tH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the classic GCN and proposed the new convolution operator with wider spatial scope and robust properties. The proposed models could improve the accuracy in both benign and evasion setting on synthetic, ie., SBM dataset and real world benchmark graphs. However, I have the following questions for the authors:\n\n1. In the paper, compared to the classic GCN, the authors replace the adjacent matrix $A$ with the proposed “variable power operator”. However, the proposed “variable power operator” is very similar to “k-th order polynomials of the Laplacian”, which has been fully discussed in [1]. Could you distinguish the differences between the proposed “variable power operator” and “k-th order polynomials of the Laplacian”? And as the authors proposed to use high-order matrix  some recent models which also explores high-order matrix such as [2, 3] may also need to be selected as baseline methods. \n\n2. As it is clearly defined in [4,5], all the five attack methods adopted in the paper are poisoning (training time) attacks methods. However, the proposed models are claimed to defense against evasion (testing) attacks. Why choose the poisoning attacks methods here? The experiment with the evasion attack method [6] is suggested to be added. \n\n3. When the proposed models are applied to other kind of graph data, ie., social network, according to the small world theory, the \"variable power adjacency matrix\" would be very dense when $r>2$ with 2-layer GCN. The efficiency of the proposed might be an issue. Is it possible to add one experiment with demonstrating the running time on the real world social network?\n\n[1] Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. \"Convolutional neural networks on graphs with fast localized spectral filtering.\" Advances in neural information processing systems. 2016.\n[2]Wu, Felix, et al. \"Simplifying graph convolutional networks.\" International Conference on Machine Learning. 2019.\n[3] Abu-El-Haija, Sami, et al. \"Mixhop: Higher-order graph convolution architectures via sparsified neighborhood mixing.\"  International Conference on Machine Learning. 2019.\n[4]Zügner, Daniel, and Stephan Günnemann. \"Adversarial attacks on graph neural networks via meta learning.\" In ICLR 2019.\n[5]Bojchevski, Aleksandar, and Stephan Günnemann. \"Adversarial Attacks on Node Embeddings via Graph Poisoning.\" International Conference on Machine Learning. 2019.\n[6] Dai, Hanjun, et al. \"Adversarial attack on graph structured data.\" International Conference on Machine Learning. 2018.\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BkxQEAZ0YB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThere are some concerns that need to be addressed or clarified:\nA 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. \n\nSome 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.      \n\nIt would be better if the authors could provide more details about the sparsification. Specifically, how to choose the threshold (adaptively). \n\nIn 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. \n\nSuggestions:\nIn 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. \n\n\nSome minor problems:\nThere are many typos such as: “with the presence of absence of edges”, “normalizating”, “asymptotoic”, “benigh”, “ajdacency”, “sensitve”, “adajacent”, “one of the network”, etc.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper identifies the limitation of graph neural networks and proposed new variants of graph neural works. However, the reviewers feel that the theory of the paper have some problems: 
1. 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. 
2. The robustness definition is inconsistent. 
Furthermore, more extensive experiments on more datasets will also be helpful. 
Decision: Reject