Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
Authors: Kenta Oono
Taiji Suzuki
Venue:  (2020)
Keywords: Graph Neural Network
Deep Learning
Expressive Power

Abstract: Graph Neural Networks (graph NNs) are a promising deep learning approach for analyzing graph-structured data. However, it is known that they do not improve (or sometimes worsen) their predictive performance as we pile up many layers and add non-lineality. To tackle this problem, we investigate the expressive power of graph NNs via their asymptotic behaviors as the layer size tends to infinity.
Our strategy is to generalize the forward propagation of a Graph Convolutional Network (GCN), which is a popular graph NN variant, as a specific dynamical system. In the case of a GCN, we show that when its weights satisfy the conditions determined by the spectra of the (augmented) normalized Laplacian, its output exponentially approaches the set of signals that carry information of the connected components and node degrees only for distinguishing nodes.
Our theory enables us to relate the expressive power of GCNs with the topological information of the underlying graphs inherent in the graph spectra. To demonstrate this, we characterize the asymptotic behavior of GCNs on the Erd\H{o}s -- R\'{e}nyi graph.
We show that when the Erd\H{o}s -- R\'{e}nyi graph is sufficiently dense and large, a broad range of GCNs on it suffers from the ``information loss" in the limit of infinite layers with high probability.
Based on the theory, we provide a principled guideline for weight normalization of graph NNs. We experimentally confirm that the proposed weight scaling enhances the predictive performance of GCNs in real data. Code is available at https://github.com/delta2323/gnn-asymptotics.

Published as a conference paper at ICLR 2020
GRAPH NEURAL NETWORKS EXPONENTIALLY LOSE EXPRESSIVE POWER FOR NODE CLASSIFICATION
Kenta Oono'.2, Taiji Suzuki!.3
(kenta oono, ta i ji /mmist. i. u-tokyo. ac. ip
The University of Tokyo Preferred Networks, Inc.
PRIKEN Center for Advanced Intelligence Project (AIP)
ABSTRACT
Graph Neural Networks (graph NNs) are promising deep learning approach for analyzing graph-structured data. However, it is known that they do not improve (or sometimes worsen) their predictive performance we pile up many layers and add non-lineality. To tackle this problem, we investigate the expressive power of graph NNs via their asymptotic behaviors as the layer size tends infinity. Our strategy is to generalize the forward propagation of a Graph Convolutional Net- work (GCN), which is a popular graph NN variant, a specific dynamical sys- tem. In the case of a GCN, we show that when its weights satisfy the conditions determined by the spectra of the (augmented) normalized Laplacian, ponentially approaches the set of signals that carry information of the connected components and node degrees only for distinguishing nodes. Our theory enables to relate the expressive power of GCNs with the topological information of the underlying graphs inherent in the graph spectra. To demonstrate this, we charac- terize the asymptotic behavior of GCNs on the Erdös Rényi graph. We show that when the Erdós - Rényi graph is sufficiently dense and large, a broad range of GCNs it suffers from the "information loss" in the limit of infinite layers with high probability. Based on the theory, we provide a principled guideline for weight normalization of graph NNs. We experimentally confirm that the proposed weight scaling enhances the predictive performance of GCNs in real data
output ex-
INTRODUCTION
Motivated by the success of Deep Learning (DL), several attempts have been made to apply DL mod- els to non-Euclinn Eun-Euulidean data, particularly, graph-structure data such as chemical compounds, social networks, and polygons. Recently, Graph Neural Networks (graph NNs) (Duvenaud et al. 2015 Li
et al., 2017 Kipf & Welling Nguyen et al.) 2017] Schlichtkrull et al.) 2018 Battaglia et al. [0188] Xu et al. [2019] Wu et al. [2019)] have emerged as promising approach. However, despite their practical popularity, theoretical research of graph NNs has not been explored extensively.
et 2016 Gilmer et al.
The characterization of DL. model expressive power, i.e., to identify what function classes DL mod- els can (approximately) represent, is a fundamental question in theoretical research of DL. Many studies have been conducted for Fully Connected Neural Networks (FNNs) (Cybenko) 1989 Hornik
1991 Hornik et al. 1989 Barron 1993, Mhaskar 1993 Sonoda Murata [017] Yarotsky 2017)
and Convolutional Neural Networks (CNNs) (Petersen & Voigtlaender 2018 [hou 2018 Oono &
Suzuki 2019). For such models, we have theoretical and empirical justification that deep and non- linear architectures can enhance representation power (Telgarsky 2016 Chen et al. (018h) 8b) Zhou & Feng 2018). However, for graph NNs, several papers have reported that node representations go smoohhig) and prediction performances severely degrade when we stack many layers (Kipi & Welling 2017; Wu et al.) [201b]] Li et al., 2018). Besides, Wu et al. (209a) reported that graph NNs achieved comparable performance even if they removed interme- diate non-linear functions. These studies posed a question about the current architecture and made us aware of the need for the theoretical analysis of the graph NN expressive power.
indistinguishable (known
Code available at htt.a//eiiiiiiaa/e///ooaaaaaaaao http://cc////a1133333mmmmamap... asynptotics

---

Published as a conference paper at ICLR 2020
In this paper, investigate the expressive power of graph NNs by analyzing their asymptotic be- haviors as the layer size goes to infinity. Our theory gives new theoretical conditions under which neither layer stacking nor non-linearity contributes to improving expressive power. We consider specific dynamics that includes a transition defining a Markov process and the forward propaga- tion of Graph Convolutional Network (GCN) (Kipf & Welling 2017). which is one of the most popular graph NN variants, as special cases. We prove that under certain conditions, the dynamics exponentially approaches a subspace that is invariant under the dynamics. In the case of GCN, the invariant space is set of signals that correspond to the lowest frequency of graph spectra and that have "no information" other than connected components and node degrees for a node classification task whose goal is to predict the nodes' properties in graph. The rate of the distance between the output and the invariant space ((s))²² where & is the maximum singular values of weights, is typically quantity determined by the spectra of the (augmented) normalized Laplacian, and T. is the layer size. See Sections 3.3 (general case) and (GCN case) for precise statements.
We can interpret our theorem the generalization of the well-known property that if finite and dis- crete Markov process is irreducible and aperiodic, it exponentially converges to a unique equilibrium and the eigenvalues of its transition matrix determine the convergence rate (see, e.g.. L.g./Cuung & Gra- ham (). Different from the Markov process case, which is linear, the existence of intermediate non-linear functions complicates the analysis. We overcame this problem by leveraging the combi- nation of the ReLU activation function (Krizhevsky et al.] (2012) and the positivity of eigenvectors of the Laplacian associated with the smallest positive eigenvalues.
Our theory enables us to investigate asymptotic behaviors of graph NNs via the spectral distribution of the underlying graphs. To demonstrate this, we take GCNs defined on the Erdös Rényi graph Gr.p. which has N nodes and each edge appears independently with probability p. for an example. We prove that if log N PN
o(1) as function of N, any GCN whose weights have maximum singular
Np values at most C Tog(N/ej approaches the "information-less" invariant space with probability at least 1 - e, where C' is universal constant. Intuitively, if the graph on which we define graph NNs is sufficiently dense, graph-convolution operations mix signals on nodes fast and hence the feature maps lose information for distinguishing nodes quickly.
Our contributions are as follows:
We relate asymptotic behaviors of graph NNs with the topological information of underly- ing graphs via the spectral distribution of the (augmented) normalized Laplacian.
We prove that if the weights of GCN satisfy conditions determined by the graph spectra, the output of the GCN carries no information other than the node degrees and connected components for discriminating nodes when the layer size goes to infinity (Theorems 2
We apply our theory Erdös Rényi graphs an example and show that when the graph is sufficiently dense and large, many GCNs suffer from the information loss (Theorem
We propose a principled guideline for weight normalization of graph NNs and empirically confirm it using real data.
RELATED WORK
MPNN-type Graph NNs. Since many graph NN variants have been proposed, there are several
unified formulations of graph NNs GGimerr et al.
2017: Battaglia et al. 2018). Our approach is
the closest to the formulation of Message Passing Neural Network (MPNN) (Gilmer et al., 2017).
which unified graph NNs in terms of the update and readout operations. Many graph NNs fall into
this formulation such as Duvenaud et al. (2015). Li et al.) (2016), and /Velčkkvić et al. (018))
Among others, GCN (Kipf & Welling (017)) is important application of our theory because is one of the most widely used graph NNs. In addition, GCNs are interesting from a theoretical research perspective because, in addition to an MPNN-type graph NN, we can interpret GCNs
simplification of spectral-type graph NNs (Henaff et al. 2015 Defferrard et al. 2016). that make use of the graph Laplacian.
Our approach, which considers the asymptotic behaviors graph NNs as the layer size goes to infinity, is similar to Scarselll et al. (2009) one of the earliest works about graph NNs. They obtained node
2

---

Published as a conference paper at ICLR 2020
representations by iterating message passing between nodes until convergence. Their formulation is general in that we can use any local aggregation operation as long as is a contraction map. Our theory differs from theirs in that we proved that the output of graph NN approaches certain space even if the local aggregation function is not necessarily a contraction map.
Expressive Power of Graph NNs. Several studies have focused on theoretical analysis and the im- provement of graph NN expressive power. For example, Xuu et al. (2019) proved that graph NNs are no more powerful than the Weisfeiler Lehman (WL) isomorphism test (Weisfeiler & A.A. 1968) and proposed Graph Isomorphism Network (GIN), that is approximately as powerful as the WL test. Although they experimentally showed that GIN has improved accuracy in supervised learning tasks, their analysis was restricted to the graph isomorphism problem. Xuu et al. (2018) analyzed the non-asympiotic properties of GCNs through the lens of random walk theory. They proved the limitations of GCNs in expander-like graphs and proposed Jumping Knowledge Network (JK- Net) to address the issue, To handle the non-linearity, they linearized networks by a randomization assumption (Choromanska et al. 2015 We take different strategy and make use of the interpre- tation of ReLU as a projection onto a cone. Recently, INT & Maehara (2019) showed that a GCN approximately works as a low-pass filter plus MLP in certain setting. Although they analyzed finite-depth GCNs, our theory has similar spirits with theirs because our "information-less space corresponds to the lowest frequency of a graph Laplacian. Another point is that they imposed as- sumptions that input signals consist of low-frequent true signals and high-frequent noise, whereas we need not such an assumption.
Role of Deep and Non-linear Structures. For ordinal DL models such as FNNs and CNNs, we have both theoretical and empirical justification of deep and non-linear architectures for enhancing of the expressive power (e.g.. Telgarsky (2016); Petersen & Voigtlaender (2018); Oono & Suzuki (211 ) contrast, several studies have witnessed severe performance degradation when stacking many layers on graph NNs (Kipf & Welling, 2017 [W et al. 2019b). [i et al. (2018) reported that feature vectors on nodes in graph go indistinguishable as we increase layers in several tasks. They named this phenomenon over-smoothing. Regarding non-linearity, [W et al. (2019a) empirically showed that graph NNs achieve comparable performance even if we omit intermediate non-linearity. These observations gave questions about the current models of deep graph NNs in terms of their expressive power. Several studies gave theoretical explanations of the over-smoothing phenomena for linear GNNs (Li et al. 2018, Zhang/ 2019; Zhao & Akoglu 2020 We can think of our theory as an extension of their results to non-linear GNNs.
PROBLEM SETTING AND MAIN RESULT
3.1 NOTATION
Let N_ be the set of positive integers. For N E N_, we denote [N] :1 (1,..., N). For vector v E RN, we write 2 0 if and only if v, 2 0 for all n E [N]. Similarly, for a matrix X E NxC write X 2 0 if and only if Xne 2 0 for all n [N] and c E [C]. We say such a vector and matrix is non-negative. (--) denotes the inner product of vectors or matrices, depending on the context: (u, v) = u v for u, v E RWV and (),Y) == tr YY for X, Y.Y& E F N'C. 1p equals if the proposition P is true else O. For vectors V E R and w E RC, U 8 w E I NXC denotes the Kronecker product of and w defined by (v& w).e == un Wi For X E NXC. |X == x) denotes the Frobenius norm of X. For a vector v E IR diag(v) = (v, (vndmm)n.mI I.ME)N]] E NNN denotes the diagonalization of v. IN E NxN denotes the identity matrix of size N. For a linear operator P: R R and subset V C CRN, we denote the restriction of P to V by Plv.
3.2 DYNAMICAL SYSTEM
Although we are mainly interested in GCNs, we develop our theory more generally using dynamical systems. We will specialize to the GCNs in Section
For N, C, Hi E N₂ (1 E N+), let P E NXN be a symmetric matrix and Wt, E CCxC for I E N_ and h E [H]. We define fi NNC + RNN by f((X) == (PX) Here, MLP, : NxC + R NXC is the 1-th multi-layer perceptron common to all nodes [u et al. 2019
and is defined by (X) = a(... (X)(()) Win,), where R NxC
x
3

---

Published as a conference paper at ICLR 2020
is an element-wise ReLU function (Krizhevsky al. 2012) defined by (X) nnc max(Xne 0) for E [N], E [C]. We consider the dynamics X(+1) fi((()) with some initial value X E RN We are interested in the asymptotic behavior of ( as / +000 co.
For M S N. let be a M-dimensional subspace of IR-V, We assume that U and P satisfy the following properties that generalize the situation where U is the eigenspace associated with the smallest eigenvalue of (normalized) graph Laplacian A (that is, zero) and P is polynomial of A. Assumption 1. U has an orthonormal basis me(] that consists of non-negative vectors. Assumption 2. U is invariant under P, i.e., u E U, then Pu E U.
We endow I. N with the ordinal inner product and denote the orthogonal complement of by U := fu E RN (u, 2) = O, Ye E U.. By the symmetry of P. we can show that U is invariant under P. too (Appendix F. Proposition D. Therefore, we can regard P a linear mapping Plu U- + U-_ We denote the operator norm of Plu by X. When U is the eigenspace associated with the smallest eigenvalue of A and P is (()) where g is a polynomial, then, corresponds to A supp [ل() where sup ranges over all eigenvalues except the smallest one.
3.3 MAIN RESULT
We define the subspace M of NXC by M = UU- = 1E M Em X Wm Wm RC} where (em) is the orthonormal basis of U appeared in Assumption | For X
RxC, we denote Y MM. We denote the maximum singular value of Wt by 8th. and set 8t == I 8th- With these preparations, we introduce the main theorem of the paper.
the distance between X and by dx) == inf [Il
-Y|IF
Theorem 1. Under Assumptions
andd we have (I(()) S (x)dM(X)oor for any X N
The proof key is that the non-linear operation a decreases the distance dm, that is, dm(o(X)) < (X). We the non-negativity of em prove this claim. See Appendix A for the complete proof. We also discuss the strictness of Theorem[[] in Appendix E.3
By setting (X) 0, this theorem implies that M is invariant under fi. In addition, if the maximum value of singular values are small, X asymptotically approaches M in the sense of Johnson (1973) for any initial value (0), That is, the followings hold under Assumptions I and 2 Corollary 1. M is invariant under fi for any I N4, that is, if X E M, then we have fi E M. Corollary 2. Let suPien_ 8y. We have dx(xx) O(s))'). In particular, if sA then
X1 exponentially approaches M as > 0o for any initial value x
Suppose the operator norm of Plu : - U is no larger than X, then, under the assumption of sA < 1, (1) converges to 0, the trivial fixed point (see Appendix [E22 Proposition 3) Therefore, we are mainly interested in the case where the operator norm of Ple is strictly larger than (see Proposition D Finally, we restate Theorem of eigenspaces associated with the largest M eigenvalues of P. Note that the eigenvalues P is real since P is symmetric.
T [specialize to the situation where U is the direct sum
Corollary 3. Let \1 .... AN be the eigenvalue of P. sorted in ascending order. Suppose the multiplicity of the largest eigenvalue AN is M(2 N), ie., AN-M < <NN-M+I -NN-+11= ... Ax- We define X == max,e[N -N -M] Dam) We denote by the eigenspace associated with Ax and assume that U satisfies Assumption 1 Then, we have d (x((1) S s()dy(((()
Remark 1. It is known that any Markov process finite states converges to a unique distribution (equilibrium) if irreducible and aperiodic (see e.g., Norris (7998)). Theorem 7 includes this proposition special case with M = C 1. and W for all [ N.. This is essentially the direct consequence of Perron Frobenius' theorem (see e.g., Meyer 2000g). See Appendix F
APPLICATION TO GCN
We formulate GCN Kipf & Welling 2017) without readout operations Giimer al. 2017) using the dynamical system in the previous section and derive a sufficient condition in terms of the spectra of underlying graphs in which layer stacking nor non-linearity are not helpful for node elassification.
4

---

Published as a conference paper at ICLR 2020
Let G (V, be an undirected graph where V is a set of nodes and E is set of edges. We denote the number of nodes in G by N = =V] and identify V with [M] by fixing an order of V. We associate C' dimensional signal to each node. X in the previous section corresponds to concatenation of the signals. GCNs iteratively update signals on V using the connection information and weights.
NNNN be the adjacency matrix and D (iig(deg(()ve(v)) RNNN be the degree matrix of G where deg(i) == Kí E V | (i.j) EH is the degree of node Let Å == A + IN. D == D + IN be the adjacent and degree matrix of graph G augmented with self-loops. We define the augmented normalized Laplacian (Wu et al. 2019a) of G by Á := カ- ÁD- 2 and set P := IN- A. Let I,, C E N+ be the layer and channel sizes, respectively. For weights Wi CCC (1 [L], we define a GCN associated with G f fL ....o fi where ft : R xc + N is defined by fi(X) == o (PXW.. We are interested in the asymptotic behavior of the output xx41 of the GCN as L + 0o.
Let A (1 ((KJ)E))))EE
Suppose G has M connected components and let V V1 L.. VM be the decomposition of the node set V into connected components. We denote an indicator vector of the m-th connected component by thm := (1 (ueV.. Deee) E RN, The following proposition shows that GCN satisfies the assumption of Corollay (see Appendix for proof).
Proposition Let X1 S ... S AN be the eigenvalue of sorted in ascending order. Then, we have - < X AN-M < 1, and AN-M+1
= AN = 1. In particular, we have X == max,==1....N. N-M 1Aal < 1. Further, em == Ddum for E [M] are the basis of the eigenspace associated with the eigenvalue 1.
Theorem 2. For any initial value X(0), the output of 1-th layer X() satisfies dm(X() S (sA)'d((x(()) In particular, d exponentially converges to when s\ <
In the context of node classification tasks, can interpret this corollary the "information loss" of GCNs in the limit of infinite layers. For any X E .,, if two nodes j, E V are in a same connected component and their degrees are identical, then, the column vectors of X that correspond to nodes i and j are identical. It means that we cannot distinguish these nodes using X. In this sense, M only has information about connected components and node degrees and we can interpret this theorem as the exponential information loss of GCNs in terms of the layer size. Similarly to the discussion in the previous section, ()) converges to the trivial fixed point O when 8 < (remember 2N = 1). An interesting point is that even s 2 1, (!) can suffer from this information loss when s < -1
We note that the rate s' in Theorem 2 depends on the spectra of the augmented normalized Lapla- cian, which is determined by the topology of the underlying graph G. Hence, our result explicilly relates the topological information of graphs and asymptotic behaviors of graph NNs.
Remark 2. The old preprint (version 2) Luan et al.) (2019) formulated a theorem that explains the over smoothing of non-linear GNNs. Specifically, claimed that if graph does not have a bipartite component and the inpul distribution is continuous, the rank of the output of a GCN converges to the number of connected components of the underlying graph as the layer size goes to infinity almost surely. However, it is not true in general give a counterexample in Appendix
5 ASYMPTOTIC BEHAVIOR OF GCN ON ERDÒS RÉNYI GRAPH
Theorem gives way to characterize the asymptotic behaviors of GCNs via the spectral distri- butions of the underlying graphs. To demonstrate this, we consider an Erdös - Rényi graph Gn.p (Erdös & Rényi 1959 Gilbert 1959). which is a random graph that has N nodes and whose edges between two distinct nodes appear independently with probability p E [0. 1]. as an example. First, consider a (non-random) graph G with M connected components. Let 0 jun
juM < ju++1 < ... < juN < 2 be eigenvalues of the augmented normalized Laplacian of G (see, Propo- sition and set := minm=M information" as the layer size goes to infinity when the largest singular values of weights are strietly smaller than 1 Therefore, the closer the positive eigenvalues Pm are 1, the broader range of GCNs satisfies the assumption of Theorem
[1 p=<l(<< 1). By Theorem 2 the output of GCN "loses
Following the original paper (Kipf & Welling 2017 we use one-layer MI.Ps (i.c., H, = for all / E N4.). However, our result holds for the lalti-layer case
5

---

Published as a conference paper at ICLR 2020
W-1.2
W-12
1.91
1.33
0.79
0.75
0.9
0.50
100
4A
34
-6.75
-3.00 -315 -023
0.02
0.0
2.5
300
-3.00 15
-0.2
0.02
0.2
0.30
0.73
1.00
Figure I: Visualization of vector field ((X) f(X) - induced by the one-step transition. Color maps indicate the absolute value [V(X) [ at the point X. Dotted lines are the subspace M. Left:: Case 1. Right: Case 2. Best view in color.
For an Erdós Rényi graph GN. Chung & Radcliffe (2011) showed that when log N = o(1. the
Np eigenvalues of the (usual) normalized Laplacian except for the smallest one converge to with high probability (see Theorem 2 therein Fl We can interpret this theorem as the convergence Erdös- Rényi graphs to the complete graph in terms of graph spectra. We can prove that the augmented normalized Laplacian behaves similarly (Lemma 6). By combining this fact with the discussion in the previous paragraph, we obtain the asymptotic behavior of GCNs the Erdós Rényi graph. See Appendix for for the complete proof.
Theorem 3. Consider GCN on the Erdōs- Rényi graph GN.p such that log N Ne o(1) function if the supremum of the maximum singular values of weights in the GCN satisfies 50 /v Np-p+1 log(AN/e}) then, for sufficiently large N, the GCN satisfies the condition of Theorem with probability at least E.
of N. For any
Theorem requires that an underlying graph is not extremely sparse. For example, suppose the node size is N = 20, 000, which is the approximately the maximum node size of datasets we use in experiments, and the edge probability is p = log N/N, Then, each node has the order of Np Rs 4.3 adjacent nodes.
Under the condition of Theorem the upper bound 8o - 0o as + co. It means that the graph sufficiently large and not extremely sparse, most GCNs suffer from the information loss. For the dependence on the edge probability p. 8p is an increasing function of which means the denser a graph is, the more quickly graph convolution operations mix signals nodes and move them close to each other.
Theorem 3 implies that graph NNs perform poorly dense NNs. More aggressively, we can hy- pothesize that the sparsity of practically available graphs one of the reasons for the success of graph NNs in node classification tasks. To confirm this hypothesis, we artificially add edges tation networks to make them dense in the experiments and observe the failure of graph NNs as expected (see Section 6.3
EXPERIMENT
6.1 SYNTIESSI DATA: ONE-STEP TRANSITION
We numerically investigate how the transition f(X) or (PXW) changes inputs using the vector
field V(X) := f(X) x For this purpose, we set N 2, M 1, and C = Let X S Xo be the eigenvalues P. We choose W as | < W
A -1 so that Theorem is applicable but is not reduced to the trivial situation (sce, Appendix E.2 We choose the eigenvector g
Chung et al, (204) and Coja-Oghlan 2007) proved similar theorems.
Since consider the one-step transition only, we omit the subscript from X1, and Wi.

---

Published as a conference paper at ICLR 2020
0.5, 5=0.1, lambda=0.063
p=0.1, s=10.0, lambda=0.195
Actual
Actual
Log Relative Distance
Log Relative Distance
-10
Theorem
Theorem
-20
2
-30
-50
-60
0.0
2.5
5.0
7.5
10.0
6
Layer Index
Layer Index
Figure 2: The actual distances the invariant space .M and their upper bounds. Solid lines are the log relative distance defined by y() log(d,((X()) /dx((())))))))))) and dotted lines upper bound (() l (s),, where X (0) is the input signal and X is the output of the I-th layer.
Maximum Singular Value
= 0.5
Layer
0.6
3.0
3.5
Layer
Accuracy
0.5
5 10.0
Layer
Unnormalized
3.0
0.4
2.5
0.3
2.0
0.2
0
20
40
60
80
Iteration
Layer Size
Figure 3: Node prediction results on Noisy Cora. Left: Effect of the maximum singular values on weights model performance. The horizontal dotted line indicates the chance rate (30.2%). The error bar the standard deviation of 3 trials. Right: Transition of maximum singular values during training. See Appendix I.3 for results using other datasets, Best view in color.
associated with X2 in two ways as described below. See Appendix H.l for the concrete values of P. and W. Figure shows the visualization of V. First, we choose the non-negative eigenvector so that satisfies Assumption (Case 1). We see that the transition function ff uniformly decreases the distance from MM. This is consistent with the consequence of Theorem [ Next, choose the eigenvector = [cr e2] such that the signs of e and e2 differ (Case 2), which violates Assumption [ We see that M is not invariant under and does not uniformly decrease the distance from M. Therefore, we cannot remove the non-negativity assumption from Theorem
6.2 SYNTHESIS DATA: DISTANCE TO INVARIANT SPACE
We evaluate the distance the invariant space M using synthesis data. We randomly generate an Réndi graph, GCN it, and input signal (0) We compute the distance between the I- th intermediate output X and the invariant space M for various edge probability p and maximum dx((()) singular value s. Figure plots the logarithm of the relative distance y(() = log Xxe(X with respect the layer index From Theorem I we know that it is upper bounded by y()) (og(sA)) We see that this bound well approximates the actual value when s' is small. On the other hand, it is loose for large s). We leave tighter bounds for d in such a case future research.
6.3 REAL DATA: EFFECT OF MAXIMUM SINGULAR VALUES ON PERFORMANCE
Theorem 2 iimlles that if is smaller than the threshold X cannot expect deep GCN to achieve good prediction accuracy. Conversely, if we can successfully train the model. s should avoid the region < - We empirically confirm these hypotheses using real datasets.

---

Published as a conference paper at ICLR 2020
We use Cora, CiteSeer, and PubMed (Sen et al. 2008), which standard citation network datasets. The task is to classify the genre of papers using word occurrences and citation relationships. We regard each paper
node and citation relationship as edge. Due space constraints, we focus on Cora in the main article. See Appendix H..3 and L.3 for the other datasets. The discussion in Section 5 implies that Theorem _ can support wide range of GCNs when the underlying graph is relatively dense. However, the citation networks are too sparse to examine the aforementioned hypotheses - Thhoremm 2 gives non-trivial result only when 1 S < X- + 3.62 10-3 To circumvent this, we make noisy versions of citation networks by randomly adding edges to graphs.
Through this manipulation, we can increase the value of A to 1.11.
Figure B (left) shows the accuracy for the test dataset in terms of the maximum singular values and the number of graph convolution layers. We can observe that when GCNs whose maximum singular value 8 is out of the region 8 < X- outperform those inside the region in almost all configurations. Furthermore, the accuracy of GCNs with & 10 are better than those without normalization (unnormalized). Figure (right) shows the transition of the maximum singular values of the weights during training when we use a three-layered GCN. We can observe that the maximum singular value does not shrink to the region S X X- In addition, when the layer size is small and predictive accuracy is high, GCNs gradually increase s from the initial value and avoid the region. In conclusion, the experiment results are consistent with the theorems.
6.4 REAL DATA: EFFECT OF SIGNAL COMPONENT PERPENDICULAR TO INVARIANT SPACE
We can decompose the output X of model as X Xo X1 (Xo E M, Xi E MM).. According to the theory, Xo has limited information for node classification. We hypothesize that the model emphasizes the perpendicular component X1 to perform good predictions. To quantitatively evaluate it, we define the relative magnitude of the perpendicular component of the output X by t(X) := X1/Xo. Figure f compares this quantity and the prediction accuracy on the noisy version of Cora (see Appendix L.4] for other datasets). We observe that these two quantities are correlated (R = 0.545). we remove GCNs have only one layer (corresponding to right points in the figure), the correlation coefficient is 0.827. This result does not contradict to the hypothesis above
Notay Cora [R=0, 545, p-4 (.4.8800003)
Accuracy
0.40
0.5
1-1.05 -2
1-0.3
3-3.0
030
x-20.0
unnommllzed
025
0
3
Log of Relative Perpendioubr Component
Figure 4: log (ogt(()) and prediction accuracy on Noisy Cora.
7 DISCUSSION
Applicability to Graph NNs on Sparse Graphs. We have theoretically and empirically shown that when the underlying graph is sufficiently dense and large, the threshold > -1 large (Theorem and Section 6.3). which means many graph CNNs are eligible. However, real-world graphs are not very limited GCNs. In addition, [Coja Oghlan (0077) theoretically proved that if the expected average degree of GN,, is bounded, the smallest positive eigenvalue the normalized Laplacian of GN,, p asymptotic behaviors of graph NNs on sparse graphs are left for future research.
often dense, which means that Theorem [ applicable
is o(1) with high probability. The
Remedy for Over-smoothing. Based on our theory, we can propose several techniques for mitigat- ing the over-smoothing phenomena. One idea is to (randomly) sample edges in underlying graph. The sparsity of practically available graphs could be a factor in the success of graph NNs. Assum- ing this hypothesis is correct, there is possibility that we can relive the effect of over-smoothing by sparsification. Since we can never restore the information in pruned edges if we remove them permanently, random edge sampling could work better FastGCN (Chen al.) 2018a) and Graph- SAGE (Hamilton et al.) 2017) do. Another idea is to scale node representations (i.e., intermediate or final output of graph NNs) appropriately so that they keep away from the invariant space M. Our proposed weight scaling mechanism takes this strategy. Recently, Zhao & Akoglu (020)) has pro-
'ee cannot conclude that large perpendicular components essential for gond performance, since the maximum singular value is correlated to the accuracy, too.
8

---

Published as a conference paper at ICLR 2020
posed PairNorm alleviate the over-smoothing phenomena. Although the scaling target is different they rescaled signals whereas we normalized weights - theirs and ours have similar spirits.
Graph NNs with Large Weights. Our theory suggests that the maximum singular values of weights in a GCN should not be smaller than a threshold A- because it suffers from information loss for node classification. On the other hand, if the scale of weights are very large, the model complexity of the function class represented by graph NNs increases, which may cause large generalization errors. Therefore, from statistical learning theory perspective, we conjecture that the graph NNs with too-large weights perform poorly, too. A trade-off should exist between the expressive power and model complexity and there should be "sweet spot" on the weight scale that balances the two.
Relation to Double Descent Phenomena. Belkin et al. (2019) pointed out that modern deep mod- els often have double descent risk curves: when model is under-paramee parameerraeeee,..dd classical bias- variance trade-off occurs. However, once the model has a large capacity and perfectly fits the training data, the test error decreases as we increase the number of parameters. To the best of our knowl- edge, no literature reported the double descent phenomena for graph NNs (it is consistent with the picture of the classical U-shaped risk curve in the previous paragraph). descent phenomena do not occur in some situations, especially depending regularization types. For example. while Belkin et al. (2019) employed the interpolating hypothesis with the minimum norm, Mei & Montanari (2019) found that the double descent was alleviated or disappeared when they used Ridge-type regularization techniques. Therefore, one can hypothesize the over-smoothing is a cause consequence of regularization that is more like Ridge-type rather than minimum-norm inductive bias.
known that double
Limitations in Graph NN Architectures. Our analysis is limited to graph NNs with the ReLU activation function because we implicitly use the property that ReLU is a projection onto the cone {X 2 0} (Appendix A Lemma B). This fact enables the ReLU function to get along with the non- negativity of cigenvectors associated with the largest cigenvalues. Therefore, it is far from trivial to extend our results other activation functions such as the sigmoid function or Leaky ReLU (Maas et al. 2013). Another point is that our formulation considers the update operation (Gilmer et al. 2017 of graph NNs only and does not take readout operations into account. particular, we cannot directly apply our theory to graph classification tasks in which each sample is graph.
Over-smoothing of Residual GNNs Considering the correspondence of graph NNs and Markov processes (see Appendix F. one can imagine that residual links do not contribute to alleviating the over-smoothing phenomena because adding residual connections to a graph NN corresponds to converting Markov process to its lazy version. When Markov process converges to stable distribution, the corresponding lazy process also converges eventually under certain conditions. It implies that residual links might not be helpful. However, [i al. (201)) reported that graph NNs with as many as 56 layers performed well if they added residual connections. Considering that, the situation could be more complicated than our intuitions. The analysis of the role of residual connections in graph NNs is promising direction for future research.
8 CONCLUSION
In this paper, to understand the empirically observed phenomena that deep non-linear graph NNs do not perform well, analyzed their asymptotic behaviors by interpreting them as dynamical system that includes GCN and Markov process as special cases. We gave theoretical conditions under which GCNs suffer from the information loss in the limit of infinite layers. Our theory directly related the expressive power of graph NNs and topological information of the underlying graphs via spectra of the Laplacian. enabled us to leverage spectral and random graph theory to analyze the expressive power of graph NNs. To demonstrate this, we considered GCN on the Erdós Rényi graph as an example and showed that when the underlying graph is sufficiently dense and large, a wide range of GCNs on the graph suffer from information loss. Based on the theory, we gave a principled guideline for how to determine the scale of weights of graph NNs and empirically showed that the weight normalization implied by our theory performed well in real datasets. One promising direction of research is to analyze the optimization and statistical properties such as the generalization power (Verma & Zhang 2019) of graph NNs via spectral and random graph theories.

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
We thank Katsuhiko Ishiguro for providing part of code for the experiments, Kohei Hayashi and Haru Negami Oono for giving us feedback and comments on the draft, Keyulu Xu and anonymous reviewers for fruitful discussions via OvenReview, and Ryuta Osawa for pointing out errors and suggesting improvements of the paper. TS was partially supported by JSPS KAKENHI (15H05707, 18K19793, and 18H03201), Japan Digital Design, and JST CREST.
REFERENCES
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, KDD '19, pp- 2623-2631, New York, USA, 2019, ACM. ISBN 978--400-0-0-2 doi: 10. 10.1145/3292500. 3330701.
Dana Angluin and Leslie G Valiant. Fast probabilistic algorithms for hamiltonian circuits and match- ings. Journal of Computer and system Sciences, 18(2):155-199) 1979.
Andrew R Barron, Universal approximation bounds for superpositions of a sigmoidal function. JEEE Transactions on Information theory, 39(3):930-945, 1993.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varinvar trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 1588444444499158544 2019.
James S. Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Advances in Neural Information Processing Systems 24, pp. 2546- 2554. Curran Associates, Inc., 2011.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018a. URL
httpss://ppenreiii net. / forum deryt.st......... XWAX
Minmin Chen, Jeffrey Pennington, and Samuel Schoenholz. Dynamical isometry and mean field theory of RNNs: Gating enables signal propagation in recurrent neural networks. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 873-882. PMLR, 10-15 Jul 2018b.
Anna Choromanska, Yann LeCun, and Gérard Ben Arous. Open problem: The landscape of the loss surfaces of multilayer networks. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1756-1760. PMLR, 2015.
Fan Chung and Linyuan Lu. Connected components in random graphs with given expected degree sequences. Annals of combinatories, 6(2):125-145, 2002.
Fan Chung and Mary Radcliffe. On the spectra of general random graphs. the electronic journal of combinatorics, 18(1): 2011.
Fan Chung, Linyua Lu, and Van Vu. The spectra of random graphs with given expected degrees. Internet Mathematics, 1(3):257-275, 2004.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92 in CBMS Regional Conference Series in Mathematics. American Mathematical Soc., 1997.
Amin On the laplacian eigenvalues of Gn.p- Combinatorics, Probability and Com- puting, 16(6)99339966, 2007.
10

---

Published as a conference paper at ICLR 2020
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314 1989.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances Neural Information Processing Systems 29, pp. 3844-3852. Curran Associates, Inc., 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Espuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints, In Advances in Neural Information Processing Systems 28, pp. 2224-222323 Curran Associates, Inc., 2015.
Paul Erdös and Alfréd Rényi On random graphs I. Publicationes Mathematicae (Debrecen), 6: 290-297, 1959.
Edgar N Gilbert. Random graphs. The Annals of Mathematical Statistics, 30(4): (1(4):1141-1144 1959.
Cee Giles, Kurt Bollacker, and Steve Lawrence. Citeseer: an automatic citation indexing system. In Proceedings of the third ACM conference Digital libraries, pp. 39-98. ACM, 1998.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272. PMLR, 2017.
Torben Hagerup and Christine Rüb. A guided tour of Chernoff bounds. Information processing letters, 33(6):305-30) -08 1990.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30, pp. 1024-1034. Curran Associates, Inc., 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data, arXiv preprint arXiv:7506.05163 2015.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, (2):251-257, 1991.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5):359 -365, 1989.
CD Johnson. Stabilization of linear dynamical systems with respect to arbitrary linear subspaces. Journal of Mathematical Analysis and Applications, 14(1):175-186, 1973.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems 25, pp. 1097- 1105. Curran Associates, Inc., 2012.
Yann A LeCun, Léon Bottou, Genevieve B Orr. and Klaus-Rober Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 9-48. Springer, 2012.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE International Conference on Computer Vision, pp. 9267-9276, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.

---

Published as a conference paper at ICLR 2020
Yujia Li, Richard Zemel, and Mare Brockschmidt. Gated graph sequence neural networks. In International Conference on Learning Representations, 2016.
Sitao Luan, Mingde Zhao, Xiao-Wer Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. In Advances in Neural Information Processing Systems 32, pp. 10943-10953. Curran Associates, Inc., 2019.
Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng. Rectifier nonlinearities improve neural net- work acoustic models. In in ICML Workshop on Deep Learning for Audio, Speech and Language Processing, 2013.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 32):127-163, 2000.
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and double descent curve. arXiv preprint
00355555..,...... 2019.
Carl D Meyer. Matrix analysis and applied linear algebra, volume 71, Siam, 2000.
Hrushikesh Narhar Mhaskar. Approximation properties of multilayered feedforward artificial neu- ral network. Advances in Computational Mathematics, 1(1):61-80, 1993.
Hai Nguyen, Shinichi Maeda, and Kenta Oono. Semi-supervised learning of hierarchical represen- tations of molecules using neural message passing. arXiv preprint arXiv: 2017.
James R Norris. Markov chains. Number 2 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge university press, 1998.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: 2019.
Kenta Oono and Taiji Suzuki. Approximation and non-parametric estimation of ResNet-type con- volutional neural networks. arXiv preprint arXiv:1903.10047, 2019.
Sinno Jialin Pan and Qiang Yang. A survey transfer learning. IEEE Transactions on knowledge and data engineering. 22(10):1345-133 1359, 2010.
Philipp Petersen and Felix Voigtlaender. Equivalence of approximation by convolutional neural networks and fully-comnected networks. arXiv preprint arXiv: /809000300 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Michael Sehlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3)933-93, 2008
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator: Applied and Computational Harmonic Analysis, 43(2):233-268. 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15:1929-1958 2014.
Matus Telgarsky. Benefits of depth in neural networks. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 1517-1539. PMLR, 23- 26 Jun 2016.
Seiya Tokui, Kenta Oono, Shohei Hido, and Justin Clayton. Chainer: a next-generation open source framework for deep learning. In Proceedings of Workshop on Machine Learning Sys- tems (LearningSys) in The Twenty-nina Annual Conference on Neural Information Processing Systems (NIPS), 2015.
12

---

Published as a conference paper at ICLR 2020
Seiya Tokui, Ryosuke Okuta, Takuya Akiba, Yusuke Nitanii, Toru Ogawa, Shunta Saito, Shuji Suzuki, Kota Uenishi, Brian Vogel, and Hiroyuki Yamazaki Vincent. Chainer: A deep learn- ing framework for accelerating the research cycle. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2002-2011. ACM, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Dis- covery & Data Mining, 2019.
Boris Weisfeiler and Lehman A.A. A reduction of graph canonical form and algebra arising Informatsia, 2(9):12-16, 1968.
during this reduction. Mauchno-Technicheen
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv:I902.00 07153, 2019a.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A
comprehensive survey graph neural networks. arXiv preprint 1xXiv:9901.00590 2019b.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103-114, 2017.
2017.
Jiawei Zhang. Gresnet: Graph residuals for reviving deep graph neural nets from suspended anima- tion. arXiv preprint arXiv:1909.09) 1909005729, 2019.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in {gun); )s. In International
Conference Learning Representations, 2020. WRLLhttps://ppereviiie n www./ouumfffm forum?
[d=rkec1 1l
Ding- Xuan Zhou. Universality of deep convolutional neural networks.
arXiv preprint
1rXiv:1805.1077 2018
Pan Zhou and Jiashi Feng. Understanding generalization and optimization performance of deep CNNs. In Proceedings of the 35th International Conference Machine Leurning, volume 80 of Proceedings of Machine Learning Research, pp. 5960-5969. PMLR, 2018
A PROOF OF THEOREM
As wrote in the main article, it is enough to show the following lemmas (definition of mis- cellancous variables are as in Section 3.2). Remember that = supneINNMS |nal and Sth, is the maximum singular value of Wi.
Lemma 1. For any X NxC, we have (PxPP) S Adv(X). Lemma 2. For any X NxC, we have d (XWi)) I (x). Lemma 3. For any X E NNC, we have dx)( & dy(().
Proof of Lemma Since a symmetric linear operator on U we can choose the orthonormal basis (em)==M+1....) of U consisting of the eigenvalue of Plus. Let Am be the eigenvalue of P to which em is associated (m M + I....,N) Note that since the operator norm P Plu is X, we have Mmm A for all M + 1...., N. Since (em men] forms the orthonormal basis of
13

---

Published as a conference paper at ICLR 2020
R., we uniquely write X RNNC as X = E cm Wm for some um R Then,
have (X)
2m= M+1 [/0mll II where || is the 2-norm of vector. On the other hand, we have
N
PX
Σ
Pem @ Wm
m=l
N
Pem X Wm
Σ
Pem X Wm
m=1
m= M+1
M
N
Pem @ Wm +
Σ
Cm @ (Am
m=1
m= M+1
Since U is invariant under P, for any m E [M], we can write Pem as a linear combination of
(n E [M]). Therefore, we have (PX) = Em 2m= Wm Then, we obtain the desired
inequality as follows:
dPX(
Σ
1m 1
M+1
N
2
Σ
[mmll 1|
m= -1
$ X2
Σ
[mmll 1|
m-
Proof of Lemma
Using the same decomposition of X as the proof in Lemma
we have
N
XW
cm
2 (WiJ.n wm)
m=1
M
N
Σ
cm @ (Wi.wm)
Wm) +
Σ m=M+1
cm 2 WTT.wm)
Therefore, we have
(XWw)
= Σ
W wm 2
m=M+1
N
S 1/t
Σ
[|mml
m=M+1
(X)).
Proof of Lemma 3 We choose N in the proof of Lemma | We denote X (Xne)e and en Then, (c, & [.)[C])) is the orthonormal basis of IR NxC, endowed with the standard inner product as a Euclid space. Therefore, we can decompose X as X = ΣN D Anden & e. where ane (X, en @ ee)) Em Xmceman Then, have d2 Σn
respectively. Let (c') be the standard basis of C
IEE 112
14

---

Published as a conference paper at ICLR 2020
which is further transformed
N
C AncE'
dx(x)=
Σ
n n= M+1
Σ
nn
n=M+1em
N
M
ne
nc
c=l
M=1
n=1
||x
Σ (x en) ==1
where X. is the e-th column vector of X. Similarly, we have
M Exxt
(x(o(x))= = Σ ||xt|]
==1
where we denote (X) (X (Me in shorthand. Therefore, the inequality follow from the following lemma.
Lemma 4. Let x E R and U1,..., Uas E N be orthonormal vectors (i.e. (Um: Un) = Smn) ) satis-
fying 2 for all E [M]. Then, we have ||=]| - -m (I, um) 2 | 1| >m= (x Um) where x == max(x, (2, 0) for x R.
Proof. The value ||w/l - Em (y, um) is invariant under simultaneous coordinate permutation of y and Um 's. Therefore, we can assume without loss generality that the coordinate x are sorted:
I S ... z2 < 0 < #L+1 NN for some L S N. Then, we have
|>| ||
(I)
When L = O, the sum in the right hand side is treated as O. On the other hand, writing as = [n direct calculation shows
M Σ m=1
Σ (z, um)) fx+ Um)
Σ
In Unm
2
Σ
Σ
Ulm
(2)
n= 1+1+1
Let Im = fn E [N] Unem >
0} be the support of um for m E [M]. We note that if m m' [M],
we have Im n Imm = 0 since if there existed n E Im O Imm, we have
0 (Um, Um!) 2 Una Unam' 0,
which is contradictory. Therefore,
Σ
Σ
Fn Trom
Fn Unm
In
Unm
(: Cauchy-Schward inequality)
m=1
nEL [4]
nEL
N
2
(1ml =1)
m=1
(3)
15

---

Published as a conference paper at ICLR 2020
We used the fact that I 's disjoint and 8nm 0 if & Um in the first equality above.
Further, we have 2mm Vmm I 0 for n S and L + 1 - by the definition L and
non-negativity of Um- By combining ① and (3) have
Σ (r, 2m) ) (xx vm/
|20| - || + $122.
nm
Proof of Theorem
1
By Lemma 2 and
we have
dm(li(X)) dm (a W22 :Wi)))
H times
S P. (-
#-1 times
S sun, sum.-odm(a Pa
--1 times
II 8th dM(PX)
I (PX)(PX)
S s()dm(X).
B PROOF OF PROPOSITION
Proof. Let já ... AuN be the eigenvalue of the augmented normalized Laplacian A, sorted in ascending order. Since P = IN A, it is enough show ت4ı and å& < 2. For the first two, the statements
j. 0, PM+1 0, equivalent that Á is positive semi-definite and that the multiplicity of the eigenvalue 0 is same as the number of connected components 0 This well-known for Laplacian or its normalized version (see, e.g., Chung & Graham (1997) and the proof for Á is similar. By direct calculation, we have
Ar
Dj dd +1
aj
+1 +I
for any x [2]
]ND E N.N. Therefore, Â is positive semi-definite and hence ū1 2 0.
Suppose temporally that G connected. If E R.W an eigenvector associated to 0, then, by the aformentioned calculation, 7d. and my must be same for all pairs (i,j) such that d:j > V2 21 However, since is connected, Vd.+I must be same value for all E [N). That means the multiplicity of the eigenvalue 0 is and any eigenvector associated to must be proportional to D.1. Now, suppose G has M connected components Vi,..., VM- Let Åm be the augmented normalized Laplacians corresponding
each connected component V,, for m E [M]] By the aformentioned discussion, Ám has the eigenvalue 0 with multiplicity Since Á is the direct sum of Á s, the eigenvalue of Â is the union of those for Á,n 's. Therefore, Á has the eigenvalue 0 with multiplicity M and 6m = D b 1,, are the orthogonal basis of the eigenspace.
The former statement is identical to Lemma 1 and latter one is the extension of Lemma 2 of Wu al. 2019a
16

---

Published as a conference paper at ICLR 2020
Finally, prove iN 2. Let MA be the largest eigenvalue of the normalized Laplacian A D- * (D A)D $, where D RNXN is the diagonal matrix defined by
D :
deg(t)-
(if (1) # 0) (if deg(i) = 0)
Note that D- nor D are not equal to the identity matrix In in general. However, we have
L= D LDD D
(4)
where L D A is the (unnormalized) Laplacian. Therefore, have
AN max
z70
|
D LD Zx
max 270
||>|||
T D DE D
-max z/0
c.
(D& 2x) A(DàD-iz))
max z#0
x
(D&D T A(D-D--
max
270
|0|||
D D- 1z40
(DiD- A(D D D-
max
240
||D D 1z|
|||||
D $240
(D T A
D
max
2y0
|| D 1
max #/0
-
D D- 1zy0
n カ- -
Ay
1 D bxl
max
V
Mylll
max #
||>|||
dog(i) deg(i) +
pN max
NEIN
PN-
Therefore, we have AN S UN Since [
1, the equality AN μn holds and only if μN = 0, that is, has N connected components. On the other hand, known that μAN S 2 and the equality holds if and only if G has non-trivial bipartite graph connected component (see, e.g.. .g..,CCung& & Graham 1997)) Therefore, P. = JuN and μN 2 does not hold
deg(i) deg(t)+T
simultaneously and we obtain ANN- 2.
C COUNTEREXAMPLE OF PREVIOUS STUDY ON OVER-SMOOTHO FOR NON-LINEAR GNNS
We restate Theorem of the preprint (version2) Luan et al. 2019 Let G be a simple undirected graph with N nodes and k connected components such that it does not have bipartite component. Let L 1/2 11/2 N be the augmented normalized Laplacian of G. Let F N, and
Thcorem of Wu et al. (019a) showed this inequality strictly holds when G is simple and connected. We do not require this assumption.
https://arxiss www.vvorrgggao www./aa.//////e//////..//.e.eeee 190.. 02174v2
17

---

Published as a conference paper at ICLR 2020
Wn PRF be the weight of the n-th layer for E N.. For the input X RNF, define the output Y, E NNF of the n-th layer of a GCN by Y, = (LXWW) ... w., where o is the ReLU function. We assume the input X is drawn from continuous distribution on RN* Then, the theorem claims that we have lim (an)(Y.)) = almost surely with respect to the distribution of X.
We construct a conterexample. Consider a graph G consisting of = 4 nodes whose adjacency matrix is
17
1
0
A
0 1
0
Note that G is connected (i.e., 1) and is not bipartite. We make GCN with F channels and whose weight matrices are W, = Ia (the identity matrix of size 3) for all n E N. For the distribution of the input X, consider an absolutely continuous distribution with respect to the Lebesgue measure on R4x3 such that P(X 2 0) 0 (here, X 2 0 means the clement-wise comparison). For example, the standard Gaussian distribution satisfies the condition.
Since L 2 O, we have Y, = L"X if X > O. Let L = PPAP be the diagonalization of L where P E O(4) an orthogonal matrix of size 4. Since rank(L) 3, we have rank(A") = for any n (we can assume that A44 = 0 without loss of generality). Therefore, under the condition X 2 0, we have
rank(Y,)) 3
> (ank(PTAPPP =3
Xe (P-1 [B
1 3333 is invertible, E RR..
Note that the last condition is independent of n. Since the set of invertible matrices is dense in the set of all matrices of the same size (with respect to the standard topology of the Euclidean space), have P(frank(Y,)) 3 for all E N)) > 0. Therefore, we have lim rank(Y,,) = 3 with non-zero probability.
D PROOF OF THEOREM 3
We follow the proof of Theorem 2 of Chung & Radcliffe (2011). The idea is to relate the spectral distribution of the normalized Laplacian with that of its expected version. Since we can compute the latter explicitly for the Erdös-Rénye graph, we can derive the convergence of spectra. We employ this technique and derive similar conclusion for the augmented normalized Laplacian.
First, consider genral random graphs not restricted to Erdós-Rénn graphs. Let N E N4, and P= (ptz J.E]] be a non-negative symmetric matrix (meaning that Púj 2 0 for any i.j E [N). Let G be an undirected random graph with N nodes such that edge between and pendently present with probability Ptj. Let A and 1) be the adjacency and the degree matrices of G. respectively (that is, Ag Ber(P,g), i.i.d.). Define the expected node degree of node by
inde-
4 = = Pij. Let Ā = A + IN. = D + IN and define = E[Å] = P + IN and itag. fN)+ IN correspondingly. We define the augmented normalized Lapla- cian Á of G by Á == IN - -D AD- and its expected version by Á := IN D AD- For symmetric matrix X E RR,, we define its eigenvalues, sorted in ascending order by (X) < ... & (X) and its operator norm by ||||| = max,e[N] (X)]-
D = [==
9
Lemma 5 (Ref. [hung & Radcliffe (011) Theorem 2). Let d = minneiN] to be the minimum
expected degree G. huve
G. Set k(e) == 3(1 log(4 (4/=)). Then, for any e > 0, i + 1 >> k(e) log N, we
3 Blog(4N/H
(n) AA) S 4 [E(N]
max
8+1
with probability at least 1-
Note that A * A in general due the dependence between À and Π.
18

---

Published as a conference paper at ICLR 2020
(n( An(A) & || ÂlI. Therefore, it is enough to bound ف Âl|. Let C' == IN D- By the triangular incquality, we have - A - A C|| |C AlI. We will bound these terms respectively.
Proof. By Weyl's theorem, we have maX
First, we bound ||C-A|] ||. Direct calculation shows C' = - Let EV RNN be a matrix defined by
(F )RI
{
(i = k and i = 1) or (i = I and j = k),
otherwise.
We define the random variable Yi by
Avj Púj E
Yo = Vt + 1 1 +1
Then, Yg 's are independent and we have C - Â = Σ
Eij=1 Yig. To apply Theorem 5 of Chung &
Radcliffe 2011 to Yi ss we bound |Y,j - E[Yij]1 and ビ - B|23ill- First, we have
Σ
| || V +41+++++ +1 (6+
|rg E| |
Since
Pij - p.
E + E
(if f). (ifi=i).
B|
(t4 () + 1)
we have
NV
Pij - p3 E
Σ B k==1
(t: +tt + 1)
N
Pij - -P
max M
(+: + 1)(t, +1
N
Pij
< max M
(t++ 1)(t, +1)
< (ō + 1)
By letting a & Radcliffee 2011
3 (oog(4N/)) 5+1 we have
M (5-1)-1, x2 <- (6 + 1) and applying Theorem 5 of Chung
a²
Pr(IIC - All > a) S 2N exp
2( + (0-+1)-7 1)-1 + 2(6 + 1a-3
3log(4N/e)
< 2N exp
2(1 + a/3)
By the definition of k(E), we have a < 1if + 1 >> k<E) n. For such we have
3log(4N/E)
Pr([IC A > a) < 2N exp
2(1 + a/3)
< 2N exp
(- (-log(4N/e)) (.aa()) 1)
(5)
2
19

---

Published as a conference paper at ICLR 2020
Next, bound | C
First, since 1, by Chernoff bound (see, e.g. Hagerup & Rüb (1,00)), we have
Angluin & Valiant
1979
a (t, + 1)
Pr([d, 44 > alt, + 1)) - 2 exp
3 (6 + 1)
S exp
E 2N
Therefore, if d, - 1/] S a(t; + 1), then we have
d; +1
di + t 1
1/ S 12
1 for 2 0)
t, +1
di 1
S a.
Therefore, by union bound, we have
d + +1
IN max N
-1
Sa
with probability at least s/2. Further, since the eigenvalue of the augmented normalized Lapla- cian is in [) by the proof of Proposition ! have
we have I| Ál S By combining them, we
ClI ID カ - IN) - A (IN A) DDD b
S i In T | Di
aa 1) a
(6)
From
and 6 have
|
A S -
((+a)a+))++
< + 30
$ 4a (1
with probability at least by union bound.
Let N E N4 and > 0. In the case of the Erdös-Rényi graph GN.p. we should set = p(JN IN)
where JN E NxN are the all-one matrix. Then, we have Ā pJN + (1 p) D = (Np p + 1) and A Ny-p4I (NIN JN). Since the eigenvalue of JN is N (with multiplicity 1) Np
and 0 (with multiplicity N 1), the eigenvalue of Á is 0 (with multiplicity 1) and Np-p+1 (with multiplicity N 1). For Gn. 8 is the expected average degree (N- 1)p. Hence, have the following lemma from Lemma
Lemma 6. Let Â be its augmented normalized Laplacian of the Erdös Rényi graph G For any 0, if Ny-p+1 > k(() = 3(1 log(4/e)), then, with probability at least c, we have log
M(A
Np
3 (oN/E)
mAX 2= N
Np p+1
Np - +p+1
Corollary 4. Consider GCN on GN.p- Let W, be the weight of the 1-th layer of GCN and 81 be the maximum singular value of Wi for l E N+. Set == SupIEN,. Let E >> O. We define k(s)
1-p 3(1+ Log(4/e)) and U( p, Np-ptI + +4v Np-ptl If Ny-p+i > k(s) and s < U(N, -1
3log(4N//]
log
then, GCN GN satisfies the assumption of Theorem 2 with probability least 1
20

---

Published as a conference paper at ICLR 2020
Proof of Theorem
Since log N
o(1). for fixed E, we have
Np- 1--p- ++1
Np
> k(s)
log.N N
log N
for sufficiently large N. Further, Np + 00 as N
oo when
log N Np
o[). Therefore, we have
(1 11-p1 p)
1
4N
1 (7 4v3)² log Np-p+ Np
E
for sufficiently large N. Hence.
1 - p
log(4N/E) Np ++
Np p ++1 S S7 -V33)
Therefore, we have I(N, p, S 7 Np-pt1* S ((N.,..))
log(4N/e)
Therefore, if S VV log(1N/s)"
Np-p+1 then we have
E MISCELLANEOUS PROPOSITIONS
E.1 INVARIANCE OF ORTHOGONAL COMPLEMENT SPACE
Proposition 2. Let P E BNxN be symmetric matrix, treated as a linear operator P. IR - RN subspace U R- is invariant under P (i.e., u E U, then Pu E U), then, U- is invariant under P, too.
Proof. For any U- and E by symmetry of P. we have
(Pu, v) = (Pu) - T u Pe = (u, Pu).
Since an invariant space of P. we have Pv U. Hence, have (u, Po) because u E L We obtain Pu E U by the definition of U
E.2 CONVERGENCE TO TRIVIAL FIXED POINT
Let P E N be a symmetric matrix, Wj E BCxC 81 be the maximum singular value of Wt for 1 E N4. We define Ji NxC - -.Nx by fi(X) = oPPWW) where a is the element-wise ReLU function.
Proposition 3. Suppose further that the operator norm of P is no larger than X, then we have (X)( < st for any 1 E N4. In particular, let s == supien, St. If s\ < 1, then, X exponentially approaches 0 as cc.
Proof. Since À is the operator norm of Plo+, the assumption implies that the operator norm of P itself no larger than X. Therefore, we have ||PXW I x/IxWI I X|| On the other hand, since a (x:)² < 2 for any RR we have [[a(X)]] S ||X[| for any X N Combining the two, we have [|) & |PXW S &||[|||E-
E.3 STRICTNESS OF THEOREM
Theorem I limplies that sÀ < then, one-step transition fi does not increase the distance M. In this section, we first prove that this theorem is strict in the sense that, there exists a situation in which ,₁ holds and the distance dm increases by one-step transition fi at some point X.
Set N + 2, C'+ 1, and M +- 1 in Section 3.2
For μ,, À > O, we set
1
{
x
P
-
0
U
Then, by definition, check that the 3-tuple (P. satisfies the Assumptions | and 2 Set M = U 8 = and choose W E R so that W > X Finally define f NCC x by ( a where is the element-wise ReLU function.
21

---

(i.e., X; is a probability distribution on Published as a conference paper at ICLR 2020
Proposition 4. We have dm(s(X)) dx(X) any X = z2] R such that 22 >> O.
Proof. By definition, we have (X) = |xz2/. On the other hand, direct calculation shows that and dm(f((X)) = (WAX2) where x+ := =max( 0) for I E R. Since W > x- and 22 > O, we have dm(f((X)) (x)X).
fi(X) = [W]+ (WAX2)+
Next, prove the non-strictness of Theorem the sense that there exists a situation in which yig > 1 holds and the distance dM uniformly decreases by fi. Again, we set Set N < 2, < and M t- L E (1,2) and set
A p+
2 -1 .l.ct V2 H...e
x
x==
Then, we can directly show that 3-tuple (P.e,U) U) satisfies the Assumptions and Set W + Proposition 5. We have WX > 1 and dd((f((X)) < d all X R
Proof. First, note that e' = v -1)" is the eigenvector of P associated to X: Pe' = Ae'. For X be' (a,b, 0), the distance between X and M is dm(X) [b]. On the other hand, by direct computation, we have
Ab
(if 2 0),
f(x)=
v2
Ab
(if < 0).
Therefore, the distance between f(X) and M dm(f(X)) xlb1/2. Since < 2, we have dm(f(X)) < (X) for any X R
We have shown that the non-negativity of eAssumpption T is not a redundant condition in Section
6.1
F RELATION TO MARKOV PROCESS
It is known that any Markov process finite states converges to unique distribution (equilibrium) it is irreducible and aperiodic (see, c.g.. Norris (998)) ). As we see in this section, this theorem is the special case of Corollary 3
Let S = (1,...,.W N) be a finite discrete state space. Consider Markov process on characterized by symmetric transition matrix P (pt))),E[NN] N such that P 2 O and P1 1 where
is the all-one vector. We interpret pij as the transition probability from a state i to j. We associate P with graph Gp (Vp, Ep) by Vp [N] and (i,j) Ep and only if Pıj > O. Since P is symmetric, we can regard Gp an undirected graph. We assume P is irreducible and aperiodic Perron Frobenius' theorem (see, e.g., Meyer (2000)) implies that P satisfy the assumption of Corollary with M =
..... ... -1 < Å₁, AN-1 1, and AN Further, there exists unique vector e E TRN such that 0, ||e|| = 1, and e is the eigenvector for the eivenvalue 1.
Proposition 6 (Perron Frobenius). Let the eigenvalues of P be X1 S
AN. Then, we have
Corollary 5. Let X == max Dal(< 1) and M : fe@w w w WVER.. If 1, then, for any initial valueX,, X, exponentially approaches M as + co.
If we set C' = 1 and W; = for all / E N+, then, we can inductively show that Xi 2 0 for any I Therefore, we can interpret X; measure on S. Suppose further that we take the initial value X1 as X; 2 0 and X, = so that we can interpret X, as probability distribution on S. Then, we can inductively show that X, 2 O. X
A symmetric matrix A is called irreducible if and only if G' is connected. We say graph G is aperiodic if the greatest common divisor of length of all loops in G is 1. A symmetric matrix A is aperiodic if the graph GA induced by A is aperiodic.
22

---

Published as a conference paper at ICLR 2020
5). and X1+1 o = PX, for all N4. In conclusion, the corollary is reduced to the fact that if finite and discrete Markov process is irreducible and aperiodic, any initial probability distribution converges exponentially to equibrilium. In addition, the the rate À corresponds to the mixing time of the Markov process.
G GCN DEFINED BY NORMALIZED LAPLACIAN
In Section we defined P using the augmented normalized Laplacian Å by P= IN Å. We can alternatively use the usual normalized Laplacian A instead of the augmented one to define P and want to apply the theory developed in Section 3.2 We write the normalized Laplacian version as Ps := IN A. The only obstacle is that the smallest eigenvalue λ of Ps can be equal to -1, while that of P is strictly larger than -1 (see, Proposition D]. This corresponds to that fact the largest eigenvalue of Á is strictly smaller than 2, while that for can be is known that the largest cigenvalue of A is 2 if and only if the graph has non-trivial bipartite connected component (see, c.g., Chung & Graham (1997)) Therefore, we can develop a theory using the normalized Laplacian instead of the augmented one in parallel for such graph G.
In Section 5
we characterized the asymptotic behavior of GCN defined by the augmented normal- ized Laplacian via its spectral distribution (Lemma Appendix (D). We can derive similar claim for GCN defined via the normalized Laplacian using the original theorem for the normalized Lapla- cian in Chung & Radcliffe (2011) (Theorem 7 therein). The normalized Laplacian version of GCN is advantegeous over the one made from the augmented one because we know its spectral distribution for broader range of random graphs. For example, Chung & Radcliffe (201T) proved the conver- gence of the spectral distribution of the normalized Laplacian for Chung Lu 's model (Chung & Lu
2002), which includes power law graphs as a special case (see, Theorem 4 of Chung & Radeliffe 2201
H DETAILS OF EXPERIMENT SETTINGS
H.1 EXPERIMENT OF SECTION 6.1
We set the eigenvalue of to 0.5 and A2 1.0 and randomly generated / until the eigenvector e associated to A2 satisfies the condition of each case described in the main article. We set W = 1.2 and used the following values for each case as P and
H.1.1
CASE 1
P 069919 0.2499819
0.2499819 0. 0.7530085
O. 0.7028392
0. 0.71134876
H.1.2 CASE 2
0.6889574 0.2426827
-0.2426827 0.8100426
0.61637234
P
0.78744588
H.2 EXPERIMENT OF SECTION 6.2
We randomly generated an Erdōs - Rényi graph GN.p with N = 1000 and randomly generated a one-of-K hot vector for each node and embed it to C-dimensional vector using random matrix whose elements were randomly sampled from the standard Gaussian distribution. Here, K = 10 and C = 32. We treated the resulting single as the input signal (() E NCC, We constructed a GCN with L 10 layers and C' channels. All parameters were i.i.d. sampled from the Gaussian distribution whose standard deviation is same as the one used in LeCun et al. (2012 Il and multiplied scalar to each weight matrix that the largest singular value equals to specified value We used three configurations (p, s) = (0.1, 0.1,, (0.5, 1.0), (0.5, 10.0). X of the generated GCNs are 0.063, 097. 0.194, respectively. See Appendix 6.2 for the results of other configurations of (p, s).
This is the default initialization method for weight matrices in Chainer and Chainer Chemistry.
23

---

Published as a conference paper at ICLR 2020
Table 1:
Dataset specifications. The threshold X in the table indicates the upper bound of Corol-
lary 2
#Node
#Edge
#Class
Chance Rate
Threshold X-1
Cora
2708
5429
30.2%
1.6.62 10-3 1.25 x 10
CiteSeer
3312
4732
7
11.1%
PubMed
19717
44338
39.9%
1.577 x 10-3
Table 2: Dataset specifications for noisy citation networks. The threshold X-1 in the table indicates the upper bound Corollary 2
Original Dataset
#Edge Added
Threshold X
Noisy Cora 2500
Cora
2495
1.11
Noisy Cora 5000
Cora
4988
1.15
Noisy CiteSeer
CiteSeer
4991
1.13
Noisy PubMed
PubMed
24993
1.17
H.3 EXPERIMENT OF SECTION 6.3
H.3.1 DATASET
We used the Cora (McCallum et al. 2000 Sen et al. 2008). CiteSeer (Giles et al. 1998; Sen et al,,
2008), and PubMed(Sen al. 22088 datasets for experiments.
We obtained the preprocessed dataset
from the code repository of Kipf & Welling 2017 Table summarizes specifications of datasets
and their noisy version (explained in the next section).
The Cora dataset is citation network dataset consisting of 2708 papers and 5429 links. Each paper represented as the occurence of 1433 unique words and associated to one of genres (Case Based, Genetic Algorithms, Neural Networks, Probabilistic Methods, Reinforcement Learning, Rule Learning, Theory). The graph made from the citation links has 78 connected components and the smallest positive eigenvalue of the augmented Normalized Laplacian is approximately म 3.62 x 10 10-3, Therefore, the upper bound of Thcorem is X (1 - zī) xe + 3.62 x 10-3, 818 out of 2708 samples are labelled as "Probabilistic Methods" which is the largest proportion. Therefore, the chance rate 818/2708 = 30.2%.
The CiteSeer dataset is citation network dataset consisting of 3312 papers and 4732 links. Each paper is represented as the occurence of 3703 unique words and is associated to one of 6 genres (Agents, AI, DB, IR, MI., HCT). The graph made from the citation links has 438 connected compo- nents and the smallest positive eigenvalue of the augmented Normalized Laplacian is approximately 1.25 x 10-3 Therefore, the upper bound of Theorem i A- (1 A x 1+ 1.25 10 701 out of 2708 samples are labelled as "IR", which is the largest proportion. Therefore, the chance rate is 701 /3112 21.1%.
The PubMed dataset is citation network dataset consisting of 19717 papers and 44338 links. Each paper is represented as the occurence of 500 unique words and is associated to one of 3 genres ("Diabetes Mellitus, Experimental", "Diabetes Mellitus Type 1", "Diabetes Mellitus Type 2"). The graph made from the citation links has 438 connected components and the smallest positive eigen- value of the augmented Normalized Laplacian is approximately upper bound of Thcorem is X- = ( 1 + 9.57 x 10-3, 7875 out 19717 samples are labelled as "Diabetes Mellitus Type 2", which is the largest proportion. Therefore, the chance rate 7875/ 19717 7875/19717 = 39.9%.
9.48 x 10-3, Therefore, the
H.3.2 NOISY CITATION NETWORKS
We summarize the properties of noisy citation networks in Table
24

---

Published as a conference paper at ICLR 2020
2.0
2.0
Cora
Cora
Naisy Cora 2500
Eigenvalue
Noisy Cora 2500
Eigenvalue
Nolsy Cora 5000
Noisy Cora 5000
1.0
1.0
0.5
0.5
0.0
0.0
500
1000
1500 Index
2000
2500
500
1000
1500 Index
2000 2500
2.0
2.0
CiteSeer
CiteSeer CiteSeer
Noisy CiteSeer
Elgenvalue
1.5
Eigenvalue
1.5
1.0
1.0
0.0
0.0
0
1000
2000 Index
3000
1000
2000
3000
Index
Figure 5: Spectral distribution of Laplacian for the citation network datasets. Left: normalized Laplacian. Right: augmented normalized Laplacian. Top: Cora and Noisy Cora (2500, 5000). Bottom: CiteSeer and Noisy CiteSeer.
We created two datasets from the Cora dataset: Noisy Cora 2500 and Noisy Cora 5000. Noisy Cora 2500 made from the Cora dataset by uniformly randomly adding 2500 edges, respectively. Since some random edges are overlapped with existing edges, the number of newly-added edges 2495 in total. We only changed the underlying graph from the Cora dataset and did not change word occurences (feature vectors) and genres (labels). The underlying graph of the Noisy Cora dataset has two connected components and the smallest positive eigenvalue is fr R 9.62 x 10-2 Therefore, the threshold of the maximum singular values of in Theorem 2 has been increased to -- = (1 ( x 1.11. Similarly, Noisy Cora 5000 was made by adding 5000 edges uniformaly randomly. The number of newly added edges is 4988 and the graph is connected (i.e., has only connected component). jı and X are jı RJ 1.32 x 10-1 and X = (1 7 s 1.15, respectively.
We made the noisy version of CiteSeer (Noisy CiteSeer) and PubMed (Noisy PubMed), in the sim- ilar way, by adding 5000 and 25000 edges uniformly randomly to the datasets. Since some random edges were overlapped with existing edges, 4991 and 24993 edges are newly added, respectively. This manipulation reduced the number of connected component of the graph to 3. Ā is approxi- mately 1.11 x 10-1 (Noisy CiteSeer) and 1.43 x 10-1 (Noisy PubMed) and A- (1 - is approximately 1.13 (Noisy CiteSeer) and 1.17 (Noisy PubMed), respectively.
shows the spectral distribution of the augmented normalized Laplacian For comparison, we show in Figure 5 (left) the spectral distribution of the normalized Laplacian for these d3taset
H.3.3 MODEL ARCHITECTURE
We used a GCN consisting of single node embedding layer, one to nine graph convolution layers, and readout operation (Gilmer et al. (2077). which is a linear transformation common to all nodes in our case. We applied softmax function to the output GCN. The output dimension of GCN same as the number of classes (i.e., seven for Noisy Cora 2500/5000, six for Noisy CiteSeer, and three for Noisy PubMedd.. We treated the number of units each graph convolution layer as hyperparameter. Optionally, specified the maximum singular values of graph convolution
Due computational resource prohlems, we cannot compute the spectral distributions for PubMed and Noisy Pubmed.
25

---

Published as a conference paper at ICLR 2020
Table 3: Hyperparameters of the experiment in Section 6.3 X ~ LogUnif[10" 10 denotes the random variable log X obeys the uniform distribution over a. bj. "Learning rate" corresponds to when "Optimization algorithm" is Adam (Kingma & Ba 2013).
Name
Value
Unit size
1.0.....,0000 500} {10, 20....,
Epoch
{10, [10,20.... ..... 100}
Optimization algorithm
{SGD, MomentumSGD, Adam) LogUnif(10-5, 10-2
Learning rate
layers. The choice of is either 0.5 (smaller than 1), 81 (in the interval {1 S x-1)), 3 and 10 (larger than A )) We used = 1.05 for Noisy Cora 2500, Noisy CiteSeer, and Noisy PubMed, and $1 1.1 for Noisy Cora 5000 and Noisy CiteSeer so that $1 not close the edges of the the interval {1 S < }.
H.3.4 PERFORMANCE EVALUATION PROCEDURE
We split all nodes in graph (either Noisy Cora 2500/5000 Noisy CiteSeer) into training, val- idation, and test sets. Data split is the same as the one done by Kipf & Welling (2017). This transductive learning (Pan & Yang, 20T0) setting because validation and test data during training. We trained the model three times for each choice of hyper- paremeters using the training set and defined the objective function as the average accuracy on the validation set. We chose the combination of hyperparameters that achieves the best value of objec- tive function. We evaluate the accuracy of the test dataset three times using the chosen combination of hyperparameters and computed their average and the standard deviation.
use node properties of the
H.3.5 TRAINING
At initialization, sampled parameters from the i.i.d. Gaussian distribution. If the scale of maxi- mum singular values was specified, we subsequently scaled weight matrices of graph convolution layers that their maximum singular values were normalized s. The loss function defined as the sum of the cross entropy loss for all training nodes. We train the model using the one of gradient-based optimization methods described in Table
H.3.6 HYPERPRAMETERS
Table shows the set of hyperparameters from which we chose. Since we compute the repre- sentations of all nodes once each iteration, each epoch consists of iteration. We employ Tree-structured Parzen Estimator (Bergstra et al. 2011) for hyperparameter optimization.
H.3.7 IMPLEMENTATION
We used Chainer Chemistry which is extension library for the deep learning framework Chainer (Touii et al., 2015 2019), to implement GCNs and Optuna (Akiba et al. (019)) for hy- perparameter tuning. We conducted experiments in a signel machine which has Intel(R) Xcon(R) Gold 6136 CPU@ 3.00GHz (24 cores), 192 GB memory (DDR4), and GPGPUs (NVIDIA Tesla V100). Our implementation achieved 68.1 1%% with Dropout (Srivastava et al. 2014) (2 graph convo- lution layers) and 64.2% without Dropout (1 graph convolution layer) on the test dataset. These are slightly worse than the accuracy reported in Kipf & Welling (2017) but are still comparable with it.
H.4 EXPERIMENT OF SECTION 6.4
The experiment settings are almost same as the experiment in Section 6.3 The only difference is that we did not train the node embedding layer, which we put before convolution layers of GCN, while we did Section This because we wanted to see the the effect of convolution operations
htttp:://gtthubbccm
cha ner- chemi st
26

---

Published as a conference paper at ICLR 2020
on the perpendicular component of signals, while interested in the prediction accuracy in real training settings in the previous experiment.
I ADDITIONAL EXPERIMENT RESULTS
1.1 EXPERIMENT OF SECTION 6.1
We show the vector field V for various W in Figure 6 (Case 1) and Figure 7 Casse 2). Parameters other than W are same as experiments in Section 6. (detail values are available Appendix H.T.
I.2 EXPERIMENT OF SECTION 6.2
Figure shows the relative log distance of signals and their upper bound for various edge probability y and the maximum singular value Note that we generate a new graph for each configuration of (p, s). Therefore. different configurations may have different graphs and hence different even they have same edge probability common.
1.3 EXPERIMENT SECTION 6.3
1.3.1 PREDICTIVE ACCURACY
Figure 9 shows the comparison of predictive performance in terms the maximum singular value and layer size when the dataset Noisy Cora 5000 (left) and Noisy Citeseer (right), respectively. Concrete values available in Table
1.3.2 TRANSITION OF MAXIMUM SINGULAR VALUES
133 show the transition of weight of graph convolution layers during training when the dataset Noisy Cora 2500, Noisy Cora 5000, and Noisy CiteSeer, respectively. We note that the result of 3-layered GCN from the Noisy Cora 2500 is identical to Figure 3 (right) of the main article.
Figure 10
1.4 EXPERIMENT OF SECTION 6.4
Figure 14 shows the logarithm of relative perpendicular component and prediction accuracy on Noisy Cora, Noisy CiteSeer, and Noisy PubMed datasets. We Pearson R correlation efficient. If GCNs have only one layer, it has more large relative perpendicular components (cor- responding to right points in the figures) than GCNs which have other number of layers. The cor- relation between the logarithm of relative perpendicular components and prediction accuracies are 0.827(p 6.890 x 10-6) for Noisy Cora, 0.524(p 1.771 10-2) for Noisy CiteSeer, and 0.679(p = 1 1.002 10-3) for Noisy PubMed, if we treat the one-layer case outliers and remove
them.
27

---

Published as a conference paper at ICLR 2020
W=0.5
1.00
1.00
0.75
-22
0.75
-22
0.50
0.50
10
1.0
0.25
0.25
08
0.00
0.00
0.6
-0.25
0.25
04
-0.50
0.50
-075
0.75
-1.00
-100
-1.00
-0.5
-0.25
0.75
1.00
-0.25
0.00
0.25
0.30
0.75
W-1.2
W=1.5
1.4
1.2
06
0.6
-0.25
-.25
-0.50
-0.0
0.
-0.75
-0.75
0.2
-1.00
-0.55
0.50 0.25
0.75
1.00
11.00
0.75
0.50
0.25
0.00
0.25
0.50
0.75
1.00
1.00
0.75
0.75
35
0.50
0.50
300
0.25
0.25
25
0.00
0.00
06
-025
-0.50
-44
1.
-0.5
05
-1.00
11000
-0.55
0.50
0.25
0.00
0.25
0.50
6.75
1.00
1.00 0.75
0.50
0.25
0.00
0.25
0.50
0.75
1.50
Figure 6: Vector field V for various W for Case 1. Top left: W = 0.5. Top right: W = 1.0.
Middle left: W 1.2 (same Figure I in the main article). Middle right: W 1.5. Bottom left: W = 2.0. Bottom right: W = 4.0. Best view in color.
28

---

Published as a conference paper at ICLR 2020
W=0.5
1.00
1.00
0.75
0.75
12
0.50
0.50
10
0.25
0.25
02
0.8
0.00
0.00
-0.25
-6
0.25
9.
-0.50
64
0.50
-075
62
0.75
-1.00
-1000
-1.00
-0.5
-0.5
0.75
1.00
-0.25
0.00
0.25
0.00
0.75
W-1.2
W=1.5
14
1.4
1.2
0.
0.6
-0.25
-0.50
64
-0.0
-0.75
02
-0.75
-1.00
-0.5
0..50 0.25
0.75
1.00
11.00
0.775
0.50
0.25
0.00
0.25
0.50
0.75
W=4.0
1.00
1.00
0.75
0.75
12
0.50
0.50
0.25
0.25
20
0.00
0.00
15
066
-0.5
1.
-0.50
-0.5
62
05
-1.00
1.000
-0.55
0.50
0.25
0.00
0.25
0.50
6.75
1.00
1.00 0.75
0.50
-.25
0.00
0.25
0.50
0.75
1.00
Figure 7: Vector field V for various W for Case 2. Top left: W = 0.5. Top right: W = 1.0.
Middle left: W 1.2 (same Figure I in the main article). Middle right: W 1.5. Bottom left: W = 2.0. Bottom right: W = 4.0. Best view in color.
29

---

Published as a conference paper at ICLR 2020
Table 4: Comparison of performance in terms of maximum singular value of weights and layer size. "U" in the right most column indicates the accuracy of GCN without weight normalization.
Noisy Cora 2500
Maximum Singular Value
Depth
1.05
3
10
U
0.389 + 0.101
0.429 + 0.090
0.552 + 0.014
0.632
0.007
0.587 + 0.008
0.273 + 0.051
0.309 + 0.017
0.580 + 0.058
0.661 = 0.003
0.494 + 0.041
0.319
0.000
0.267 + 0.059
0.462 = 0.065
0.602
0.004
0.326 + 0.029
7
0.261 + 0.076
0.262 + 0.080
0.407 = 0.021
0.501 = 0.017
0.279 + 0.129
0.261 0.080
0.319 + 0.000
0.284 0.109
0.443 0.014
0.319 + 0.000
Noisy Cora 5000
Maximum Singular Value
Depth
1.1
10
U
0.301 + 0.080
0.333 + 0.099
0.557 + 0.004
0.561 = 0.019
0.555 + 0.016
0.245 0.066
0.247 0.076
0.370
0.041
0.587
0.009
0.286 0.066
5
0.274 + 0.048
0.237 + 0.070
0.257 + 0.076
0.535 = 0.031
0.319 + 0.000
0.263
0.080
0.297 + 0.031
0.260
0.074
0.339
0.060
0.319 0.000
0,262 + 0.081
0.258 + 0.064
0.262 + 0.080
0.261 0.082
0.318 + 0.002
Noisy CiteSeer
Maximum Singular Value
Depth
0.5
10
U
0.461
0.018
0.467
0.490 0.016
0.494 = 0.006
0.495 + 0.009
3
0,438 + 0.027
0.010
0.450 0.019
0.462 0.007
0.417 0.061
0,285 + 0.008
0.016
0.373 0.011
0.425 = 0.007
0.380 - 0.024
7
0.213
0.006
+
0.309 0.012
0.385 0.007
0.308 + 0.012
0.182 0.005
0.242 + 0.030
0.303 0.021
0.325 = 0.003
0.229 + 0.033
Noisy Pubmed
Maximum Singular Value
Depth
0.5
1.1
3
10
U
0.488 0.039
0.636 + 0.006
0.641
+ 0.010
0.632
0.002
0.631 0.010
0.442 + 0.027
0.426 +126+0.00 0.026
0.658 + 0.004
0.661
= 0.005
0.631 + 0.013
+
0.431 0.033
0.431
1.561
0.641 = 0.004
0.424
7
0,428 + 0.032
0
0.449 0.035
0.619 = 0.011
14000000
0.413 0.009
0.438 + 0.039
0.052 0.539
0.569 0.042
0.473 0.031
30

---

Published as a conference paper at ICLR 2020
p-0.01, lambda-0.645
0-0.01, 5-1., 3ambda-0664
p-0.01, 5-10.0, lambda-0.640
Actual
0.0
Actual
Log Relative Distance
Log Reletive Distance
Log Relative Distance
15
-5.0
-7.5
-30
12.55
Actual
-15.0
440
0.0
5.0
7.5
10.0
0.0
2.5
5.0
layer
layer Index
Layer
0=0.1, lam lambda=0.199
p=0.1, s=10, lambda=0,195
p=0.1, s=10.0, lambda=0.199
Actuel Theorem
Actual
Actual Theorem
Log Rellttvv Distance
-10
Log Relatiie Distance
-5
Theorem
Log Rel Distance
-10-
-30
-15
-0
-25
550
0.0
2.5
5.0
7.5
10.0
2.5
5.0
7.5
10.0
0.0
2.5
5.0
7.5
10.0
Index
Layer
p=0 0.1, lambda- 0000daaa000)
p=0.9. 5=1.0, 1.0, 0mmda==000m
p-0.9, 0,0.99 10.0, lambda 0. 021
Log Relative Distance
Theorem
Relative Dietanc
Thearem
Log Relative Distance
Thearem
-10
-10
-30
-15
-20
-40
0.0
2.5
5.0 Layer Index
7.5
10.0
0.0
2.5
5.0
7.5
10.0
0.0
2.5
5.0
7.5
10.0
Layer Index
Layer Index
Figure 8: The actual distance d. to the invariant space M and the upper bound inferred by Theorem The edge probability p takes 0.01 (top), 0.1, 0.9 (bottom))) and the maximum singular value takes
(x(X))) and
0.1 (left), 1.0, 10(rihht). Blue lines the log relative distance defined by y(!) log (110) orange dotted lines upper bound y(t) log(s)), where (0) is the input signal and (0) is the output of the 1-th layer. Best view in color.
31

---

Published as a conference paper at ICLR 2020
0.6
$ 0.5
5 = 1.1
0.5
3.0
S = 10.0
Accuracy
Unnormalized
0.4
0.3
0.2
2
4
6
Layer Size
0.5
0.5
S 1.1
S = 3.0
Accuracy
0.4
10.0
Unnormalized
0.3
0.2
2
6 Layer Size
4
S = 0.5
1.05
0.6
5 3.0
Accuracy
s = 10.0 Unnormalized
0.5
0.4
2
4
6
8
Layer Size
Figure 9: Effeet of the maximum singular values of weights predictive performance. Horizontal dotted lines indicate the chance rates (30.2% for Noisy Cora 5000, 21.2% for Noisy CiteSeer, and 39.9% for Noisy PubMed). The error bar is the standard deviation of trials. Left: Noisy Cora 5000. Right: Noisy CiteSeer. Bottom: Noisy Pubmed. Best view in color.
32

---

Published as a conference paper at ICLR 2020
Noisy Cora 2500
Maximum Singular Value
Maximum Singular Value
10
Layer 1
Layer
3.5
Layer
8
Layer
3.0
6
2.5
4
2.0
2
0
20
40
60
20
40
60
80
Iteration
Iteration
Maximum Singular Value
Maximum Singular Value
3.0
Layer
Layer 2
2.000
Layer
Layer 3
Layer
2.5
Layer
1.975
Layer
Layer
Layer
1.950
Layer
2.0
Layer
1.925
1.5
1.900
0
20
40
60
10
20
30
40
Iteration
Iteration
Maximum Singular Ainullar Value
Layer 1
2.1
Layer 2
Layer 3
2.0
Layer 4
Layer 5
1.9
Layer 6
Layer 7
1.8
Layer 8
Layer 9
2
4
6
8
Iteration
Figure 10: Transition of maximum singular values of GCN during training using Noisy Cora 2500.
Top left: 1 layer. Top right: 5 layers. Bottom left: 7 layers. Bottom right: 9 layers.
33

---

Published as a conference paper at ICLR 2020
Noisy Cora 5000
Maximum Singular Value
Maximum Singular Value
Layer
10.0
2.1
7.5
2.0
Layer
5.0
2.5
1.9
0
20
40
60
2
6
8
Iteration
Iteration
Maximum Singular Value
Maximum Singular Value
1.9
Layer
2.0
Layer
1.8
Layer
Layer
Layer
Layer
1.7
Layer
1.8
Layer
Layer
Layer
1.6
Layer
Layer
1.6
1.5
2
4
6
8
8
Iteration
Iteration
Maximum Singular Value
2.0
Layer 1
Layer 2
Layer 3
1.8
Layer 4
Layer 5
Layer 6
Layer 7
1.6
Layer 8
Layer 9
2
4
6
Iteration
Figure 11: Transition of maximum singular values of GCN during training using Noisy Cora 5000.
Top left: 1 layer. Top right: 3 layers. Middle left: 5 layers. Middle right: 7 layers. Bottom: 9 layers.
34

---

Published as a conference paper at ICLR 2020
Noisy CiteSeer
Maximum Singular Value
Maximum Singular Value
Layer
Layer
8
2.4
Layer
Layer
2.2
2.0
2
0
20
40
60
80
20
40
60
Iteration
Iteration
Maximum Singular Value
Maximum Singular Value
1.98
Layer
Layer 1
Layer
2.00
Layer 2
Layer
Layer
1.96
Layer
Layer
Layer
1.95
Layer 5
Layer
1.94
Layer
1.90
20
40
60
25
50
75
100
Iteration
Iteration
Maximum Singular Value
Layer
2.5
Layer
Layer
Layer
2.0
Layer
Layer
Layer
Layer
1.5
Layer
20
40
60
80
Iteration
Transition of maximum singular values of GCN during training using Noisy CiteSeer. Top left: 1 layer. Top right: 3 layers. Middle left: 5 layers. Middle right: 7 layers. Bottom: 9 layers.
Figure 12:
35

---

Published as a conference paper at ICLR 2020
Noisy PubMed
Maximum Singular Value
Maximum Singular Value
Layer
Layer 1
Layer 2
Layer
4-
3-
2
2
0
20
40
60
0
20
40
60
Iteration
lteration
Maximum Singular Value
Maximum Singular Value
1.95
Layer
2.0
Layer
1.90
Layer
Layer
Layer
1.8
Layer
1.85
Layer
Layer
Layer
Layer
1.80
Layer
1.6
Layer
1.75
20
40
60
0
20
40
60
80
Iteration
Iteration
Maximum Singular Value
2.05
Layer 1
VingllarV
Layer 2
2.00
Layer 3
Layer 4
Layer 5
1.95
Layer 6
Layer 7
1.90
Layer 8
Layer 9
20
40
60
Iteration
Transition of maximum singular values of GCN during training using Noisy PubMed. Top left: 1 layer. Top right: 3 layers. Middle left: 5 layers. Middle right: 7 layers. Bottom: 9 layers.
Figure 13:
36

---

Published as a conference paper at ICLR 2020
Noisy CiteSeer (R=0.580, p=2.367e-03)
Noisy PubMed (R=0.416, p=3.860e-02)
0.45
0.40
0.60
0.35
Accuracy
Accuracy
x x
0.50
$=0,5
s=0,5
$m1.05
0.45
sm1.05
$w3.0
s 3.0
0.20
S- 10.0
S- 10.0
unnarmalized
0.40
unnorma lized
-2
-2.0 -1.5
-1.0
-0.5
0.0
0.5
1.0
1.5
Log of Relative Perpendicular Component
Log of Relative Perpendicular Component
Logarithm of relative perpendicular component and prediction accuracy. Left: Noisy CiteSeer. Right: Noisy PubMed. p in the title represents the p- value for the Pearson R coefficients.
Figure 14:
37


Reviews:
[{"review_id": "rygvUd4WqH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper studies why graph NNs lose the expressive power as additional layers are added. A dynamical system perspective is adopted and used to show that under certain conditions on the weights, the expressiveness of the network deteriorates. This is since the network's output eventually only carries information about superficial graph properties for distinguishing nodes, and nothing else. A case study of Erdos-Renyi graph is provided, showing that for dense graphs information loss indeed occurs. Guidelines to try and deal with this in practice were devised and empirically examined.\n\nI enjoyed reading the paper, and found the results interesting and informative. The presentation is good and the derivations are clear. I do not have significant criticism, but would like address a few points (see below). In sum, the paper should be accepted in my opinion.\n\nComments:\n\n1) Understanding the behavior in sparse graphs seems like an important research avenue, without which the picture is incomplete. Perhaps adding some empirical results in that direction?\n\n2) The method for transforming sparse graphs into dense ones in Section 6.3 is not convincing. The random addition of edges compromises the truth correlation profile of citations. What should we learn about the actual task from the experiments on the noisy version? \n\n3) In relation to generalization error, mentioned in the discussion section. Could the double descent curves of https://arxiv.org/abs/1812.11118 reconcile the discussion therein? How would over-parameterization from the interpolation perspective and the results of the current work relate?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byx-2eBCYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 that the outputs for distinguish nodes exponentially approach signals that only carry topological information of the graph, when the weights in GCN satisfy conditions determined by spectra of the augmented normalized Laplacian, by generalizing the forward propagation of GCN to a specific dynamical system. With the guidance of this theory, it experimentally confirm weight scaling enhances the predictive performance of GCNs in both synthesized and real data.\n\nOverall, this paper could be a considerable theoretical contribution. I recommend a weak accept for this work. It explains the observation that GCNs do not improve (or sometimes worsen) the performance as we pile up more layers, which is indeed we met in our work. It also points out a useful technique, weights normalization, in training a GCN. As mentioned in the paper, scaling the weights is a trade-off between information loss and generalization error, which is an interesting topic worthing further exploration.\n\nHowever, there are one question needing more clarification. Although the output are being projected into the null space of the Laplacian, it does mean the signals only carry topological information. Distinguish nodes can still have different outputs that allows good classification results.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJldPZVKKr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 the paper, the authors carry out theoretically analysis on the expressive power for GNN. The analysis focused on the limiting case when the depth of layers goes to infinite. The authors prove that if the weights of the GNN satisfy certain condition based on the graph Laplacian, then the transformed features contain only degree and connected component information. Then the authors study the G_{np} random graph as a special case. Finally, empirical experiments are carried out to corroborates the theoretical results.\n\nStrength:\n1. The authors study a very important problem. It has long been observed that additional depth does not help GNN. The authors provide a convincing theoretical explanation for the behavior.\n2. The theoretical results are very close to practical models with little assumptions. Most importantly, the non-linearity is kept compared to other analysis that takes essential components out from the model. Moreover, the technique used in the paper could potentially benefit other theoretical analysis for NN.\n3. The authors provide supporting empirical experiments for the theoretical analysis. The observation on s in section 6.3 and the perpendicular component experiment on section 6.4 provide interesting insight to the performance of GNN.\n\nWeakness:\n1. The analysis is mostly for dense graphs. However, most of the real-world networks are large-scale sparse networks.\n2. It would be great if the authors could provide suggestions on how to eliminate the information loss in GNN. For example, it would be super interesting if the authors can generalize their analysis when residual links exists.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and 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": {}}]

Author rebuttal:

Meta-review: The paper provides a theoretical analysis of graph neural networks, as the number of layers goes to infinity. For the graph convolutional network, they relate the expressive power of the network with the graph spectra. In particular for Erdos-Renyi graphs, they show that very deep graphs lose information, and propose a new weight normalization scheme based on this insight.

The authors responded well to reviewer comments. It is nice to see that the open review nature has also resulted in a new connection. Unfortunately one of the reviewers did not engage further in the discussion with respect to the author rebuttals.

Overall, the paper provides a nice theoretical analysis of a widely used graph neural network architecture, and characterises its behaviour on a popular class of graphs. The fact that the theory provides a new approach for weight normalization is a bonus.
Decision: Accept (Spotlight)