GResNet: Graph Residual Network for Reviving Deep GNNs from Suspended Animation
Authors: Jiawei Zhang
Lin Meng
Venue:  (2020)
Keywords: Graph Neural Networks
Node Classification
Representation Learning

Abstract: The existing graph neural networks (GNNs) based on the spectral graph convolutional operator have been criticized for its performance degradation, which is especially common for the models with deep architectures. In this paper, we further identify the suspended animation problem with the existing GNNs. Such a problem happens when the model depth reaches the suspended animation limit, and the model will not respond to the training data any more and become not learnable. Analysis about the causes of the suspended animation problem with existing GNNs will be provided in this paper, whereas several other peripheral factors that will impact the problem will be reported as well. To resolve the problem, we introduce the GRESNET (Graph Residual Network) framework in this paper, which creates extensively connected highways to involve nodes’ raw features or intermediate representations throughout the graph for all the model layers. Different from the other learning settings, the extensive connections in the graph data will render the existing simple residual learning methods fail to work. We prove the effectiveness of the introduced new graph residual terms from the norm preservation perspective, which will help avoid dramatic changes to the node’s representations between sequential layers. Detailed studies about the GRESNET framework for many existing GNNs, including GCN, GAT and LOOPYNET, will be reported in the paper with extensive empirical experiments on real-world benchmark datasets.

Under review as a conference paper at ICLR 2020
GRESNET: GRAPH RESIDUAL NETWORK FOR REVIV- ING DEEP GNNS FROM SUSPENDED ANIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
The existing graph neural networks (GNNs) based on the spectral graph convolu- tional operator have been criticized for its performance degradation, which is es- pecially common for the models with deep architectures. In this paper, further identify the suspended animation problem with the existing GNNs. Such a prob- lem happens when the model depth reaches the suspended animation limit, and the model will not respond to the training data any more and become not learn- able. Analysis about the causes of the suspended animation problem with existing GNNs will be provided in this paper, whereas several other peripheral factors that will impact the problem will be reported as well. To resolve the problem, we in- troduce the GRESNET (Graph Residual Network) framework in this paper, which creates extensively connected highways to involve nodes' raw features or interme- diate representations throughout the graph for all the model layers. Different from the other learning settings, the extensive connections in the graph data will render the existing simple residual learning methods fail to work. We prove the effee- tiveness of the introduced new graph residual terms from the norm preservation perspective, which will help avoid dramatic changes the node's 's representations between sequential layers. Detailed studies about the GRESNET framework for many existing GNNs, including GCN, GAT and LOOPYNET, will be reported in the paper with extensive empirical experiments on real-world benchmark datasets.
INTRODUCTION
Graph neural networks (GNN), c.g., graph convolutional network (GCN) Kipf Welling (2016) and graph attention network (GAT) Veličković et al. (2018), based on the approximated spectral graph convolutional operator Hammond et al. (2011), can learn the representations of the graph data effectively. Meanwhile, such GNNs have also received lots of criticism, since as these GNNs ar- chitectures go deep, the models' performance will get degraded, which is similar to observations on other deep models (e.g., convolutional neural network) reported in He al. (2015). Meanwhile, different from the existing deep models, when the GNN model depth reaches a certain limit (e.g., depth > 5 for GCN with the bias term disabled or depth 2 for GCN with the bias term enabled on the Cora dataset), the model will not respond to the training data any more and become not learn- able. Formally, we name such observation the GNNs' suspended animation problem, whereas the corresponding model depth is named as the suspended animation limit of GNNs. Here, we need to add remark: to simplify the presentations in this paper, we will first take vanilla GCN as the base model example to illustrate our discoveries and proposed solutions in the method sections. Meanwhile, empirical tests on several other existing GNNs, e.g., GAT Veličković et al. (2018) and LOoPYNET Zhang et al. 2018)), will also be studied in the experiment section of this paper.
As illustrated in Figure we provide the learning performance of the GCN model on the Cora dataset, where the learning settings (including train/validation/tsst sets partition, algorithm imple- mentation and fine-tuned hyper-parameters) are identical to those introduced in Kipt & Welling (016). The GCN model with the bias term disable of seven different depths, i.e., GCN(I-layer) GCN(T-layer), are compared. Here, the layer number denotes the sum of hidden and output layers, which is also equal to the number of spectral graph convolutional layers involved in the model. For instance, besides the input layer, GCN((-layer) has 6 hidden layer and 1 output layer, both of which involve the spectral graph convolutional operations. According the plots, GCN((-layer) and GCyerllayer) have comparable performance, which both outperform GCN(l-layer). Mean- while, as the model depth increases from 3 to 7, its learning performance both the training set

---

Under review as a conference paper at ICLR 2020
1.0
0.8
testing accuracy %
training accuracy
0.6
GCN(1-layer)
GCN(1-layer)
0.6
GCN(2-layer)
GCN(2-layer)
GCN(3-layer)
GCN(3-layer)
0.4
GCN(4-layer)
GCN(4-layer)
CCN(S-layer)
GCN(S-layer)
0.2
GCN(6-layer)
0.2
GCN(6-layer)
GCN(7-layer)
GCN(7-layer)
200
400
600
800
1000
200
400
600
800
1000
epoch (iter. over training set)
epoch (iter. over training set)
(a) Training Accuracy
(b) Testing Accuracy
Figure 1: The learning performance of GCN (bias disabled) with 1-layer, 2-layer, 7-layer on the Cora dataset. The x axis denotes the iterations over the whole training set. The axis of the left plot denotes the training accuracy, and that of the right plot denotes the testing accuracy.
and the testing set degrades greatly. It is easy to identify that such degradation is not caused by over- fitting the training data. What's 's more, much more surprisingly, as the model depth goes deeper to more, it will suffer from the suspended animation problem and does not respond to the training data anymore. (Similar phenomena can be observed for GCN (bias enabled) and GAT as illustrated by Figures 9 and TO in the appendix of this paper, whose suspended animation limits are and 5, respectively. Meanwhile, on LOOPYNET, we didn't t observe such a problem as shown in Figure [1 in the appendix, and we will state the reasons in Section G detail.)
In this paper, we will investigate the causes of the GNNs' suspended animation problem, and analyze if such problem also exists all other GNN models or not. GNNs are very different from the tradi- tional deep learning models, since the extensive connections among the nodes render their learning process no longer independent but strongly correlated. Therefore, the existing solutions proposed to resolve such problems, e.g., residual learning methods used in ResNet for CNN He et al. (2015), cannot work well for GNNs actually. In this paper, several different novel graph residual terms will be studied for GNNs specially. Equipped with the new graph residual terms, we will further intro- duce a new graph neural network architecture, namely graph residual neural network (GRESNET), to resolve the observed problem. Instead of merely stacking the spectral graph convolution layers on each other, the extensively connected high-ways created in GRESNET allow the raw features or intermediate representations of the nodes to be fed into each layer of the model. We will study the effectiveness of the GRESNET architecture and those different graph residuals for several existing vanilla GNNs. In addition, theoretic analyses on GRESNET will be provided in this paper well to demonstrate its effectiveness from the norm-preservation perspective.
The remaining parts of this paper are organized follows. In Section 2 we will introduce the related work of this paper. The suspended animation problem with the spectral graph convolutional operator will be discussed in Section 3 and the suspended animation limit will be analyzed in Section 4 Graph residual learning will be introduced in Section 5 whose effectiveness will be tested in Section 6
Finally, we will conclude this paper in Section
2 RELATED WORK
Graph Neural Network: Graph neural networks Monti et al. (2017) Atwood & Towsley (2016);
Masci et al. (2013); Kipf & Welling (016); Battaglia et al. (2018) 8); [ai et al. 2018); (Scarselii et al. (2009) Zhou et al. (2018): Niepert al. (0166) have become popular research topic in recent years. Traditional deep models cannot be directly applied to graph data due to the graph inter- connected structures. Many efforts have been devoted extend deep neural networks on graphs for representation learning. GCN proposed in Kipl' & Welling (2016) feeds the generalized spectral features into the convolutional layer for representation learning. Similar to GCN. deep loopy graph neural network ZZhang (2018) proposes to update the node states in synchronous manner, and it introduces a spanning tree based learning algorithm for training the model. LOOPYNET accepts nodes' raw features into each layer of the model, and it can effectively fight against the suspended animation problem according to the studied in this paper. GAT Veličković et al.) (2018) leverages masked self-attentional layers to address the shortcomings of GCN. In this year, we have also wit- nessed some preliminary works on heterogeneous graph neural networks Wang et al. (201)): Liu et al. (2018). Similar to GCN, GEM Liu et al. (2018) utilizes one single layer of attention to cap- ture the impacts of both neighbors and network heterogeneity, which cannot work well on real-world complex networks, Based on GAT, HAN Wang al. (0019) learns the attention coefficients between
2

---

Under review as a conference paper at ICLR 2020
the neighbors based on set of manually crafted meta paths Sun et al. 2011 which may require heavy human involvements. DIFNN Zhang et al. (2018) introduce a diffusive neural network for the graph structured data specifically, which doesn's I suffer from the oversmoothing problem due to the involvement of the neural gates and residual inputs for all the layers. Due to the limited space, we can only name a few number of the representative graph neural network here. The readers also suggested to refer to pagd" which provides a summary of the latest graph neural network research papers with code on the node classification problem.
Residual Network: Residual learning Srivastava et al. 20155; ; He et al. (2015); Bae et al. (2016); Han et al.] (2016); Gomez et al. (2017 7): Tai et al. (2017); Yu al. 20 Ahn et al. (2018); : Li
et al. (201 Behrmann et al. (2199) has been utilized to improve the learning performance, espe-
cially for the neural network models with very deep architectures. To ease gradient- based training of very deep networks, Srivastavaa et al. (2155) introduces the highway network to allow unimpeded information flow across several layers. Innovated by the high-way structure, (He et al.) (2015) in- troduces the residual network to simplify highway network by removing the fusion gates. After that, residual learning has been widely adopted for deep model training and optimization, [ae et al.) (2066) introduces residual learning for image restoration via persistent homology guidded manifold simplification: Tai et al. (2017): [i et al. (2018a) Sa) introduces a recursive residual network for image resolution adjustment. Some improvement of residual network has also been proposed in recent years. A reversible residual network is introduced in Gomez et al. (2017), where each layer's 's activa- tions can be reconstructed exactly from the next layer's ss; Han al. (2016) improves the conventional model shape with a pyramidal residual network instead; Yu et al. (011)) introduce the dilated resid- ual network to inereases the resolution of output feature maps without reducing the receptive field of individual neurons; and (Ahn et al.] (2018) studies the cascading residual network as an accurate and lightweight deep network for image super-resolution. Readers can also refer to HHe (2016) for detailed tutorial on residual learning and applications in neural network studies.
3 SUSPENDED ANIMATION PROBLEM WITH GCN MODEL
In this part, we will provide an analysis about the suspended animation problem of the spectral graph convolutional operator used in GCN to interpret the causes of the observations illustrated in Figure [ In addition, given an input network data, we will provide the theoretic bound of the suspended animation limit for the GCN model.
3.1 VANILLA GRAPH CONVOLUTIONAL NETWORK REVISIT
To make this paper coffinonta we will provide a brief revisit of the vanilla GCN model in this part. Formally, given an input network G = (V, 8), its network structure information can be denoted as an adjacency matrix A {0, 1 (where | = n). GCN defines the normalized adjacency matrix of the input network as Å = D AD 1, where À = A + I=xn and D is the diagonal matrix of Å with entry ii, = Σ, A(i Given all the nodes in V together with their raw feature inputs X E Radd, (d, denotes the node raw feature length), GCN defines the spectral graph convolutional operator to learn the nodes' representations as follows:
H SGC (X; G. W) = ReLU (Axw),
where W E 4.dx da is the variable involved in the operator.
Furthermore, GCN can involve a deep architecture by stacking multiple spectral graph convolu- tional layers on each other, which will be able to learn very complex high-level representations of the nodes. Here, let's assume the model depth to be K (i.e., the number of hidden layers and output layer), and the corresponding node representation updating equations can be denoted as:
()) X,
(R) ReLU (AHLk-D .kk (1,2, , ,K- --1,,
(2)
Y softmax (AH(K-UW(K-I))
3

---

Under review as a conference paper at ICLR 2020
3.2 SUSPENDED ANIMATION PROBLEM WITH GCN
By investigating the spectral graph convolutional operator defined above, we observe that it actually involves two sequential steps:
MC Layer:
T(k) = (K-1)
(k) = ReLU (AH
+
FC Layer:
(K) = ReLU (T()
(3)
where the first term on the right-hand-side defines a 1 1-step Markov chain (MC or a random walk) based the graph and the second term is fully-connected (FC) layer parameterized by variable W(k-1), Similar observations have been reported in Li et al. (0188)) as well, but it interprets the spectral graph convolutional operator a different way as the Laplacian smoothing operator used in mesh smoothing in graphics instead.
Therefore, stacking multiple spectral graph convolutional layers on top of each other is equivalent to the stacking of multiple 1-step Markov chain layers and fully-connected layers in crosswise way. Considering that the variables (k-1 for the vector dimension adjustment are shared among all the nodes, given two nodes with identical representations, the fully-connected layers (parameterized by W(k-1) will still generate identical representations as well. other words, the fully-connected layers with shared variables for all the nodes will not have significant impacts on the convergence of Markov chain layers actually. Therefore, in the following analysis, we will simplify the model structure by assuming the mapping defined by fully-connected layers to be the identity mapping. We will investigate the Markov chain layers closely by picking them out of the model to compose the Markov chain of multiple steps:
T =X, T A Vk E (1, K)).
Meanwhile, the Markov chain layers may converge with & layers iff ((k) = ((-1), i.e., the repre- sentations before and after the updating are identical (or very close), which is highly dependent on the input network structure, i... matrix A, actually.
DEFINITION 1. (Irreducible and Aperiodic Network): Given an imput network G (V,E), G is irreducible for any two nodes Vi, V2 E V, node vi is accessible to vg. Meanwhile, G is aperiodic iff G is not bipartite.
LEMMA 1. Given unweighted input graph G, which is irreducible, finite and aperiodic, if its corresponding matrix is asymmetric, starting from any initial distribution vector x E R (x 2 0 and ||*||| 1), the Markov chain operating on the graph has one unique stationary distribution d(v.))
vector गt such that lim A'x = TT', where π Ti) 2 Meanwhile, if matrix A is symmetric, the stationary distribution vector π will be a uniform distribution over the nodes, i.e., π TT) 1
Based on the above Lemma T we can derive similar results for the multiple Markov chain layers in the GCN model based on the nodes' feature inputs, which will reduce the learned nodes" represen- tations to the stationary representation matrix.
THEOREM Given input network G = (V, E), which is unweighted, irreducible, finite and ape- riodic, if there exist enough nested Markov chain layers in the GCN model, it will reduce the nodes' representations from the column-normalle
feature matrix X E Raxds to the stationary repre- representation will become III == E I Ruxds Furthermore, if G is undirected, then the stationary
sentation II [x",. n²
1nxd.
Theorem I illustrates the causes of the GNNs' suspended animation problem. Proofs of Lemma and Theorem I aare provided in the appendix attached to this paper at the end.
SUSPENDED ANIMATION LIMIT ANALYSIS
Here, we will study the suspended animation limit of the GCN model based on its spectral convo- lutional operator analysis, especially the Markov chain layers.
4.1 SUSPENDED ANIMATION LIMIT BASED INPUT NETWORK STRUCTURE Formally, we define the suspended animation limit of GCN follows:
4

---

Under review as a conference paper at ICLR 2020
DEFINITION 2. (Suspended Animation Limit):
The suspended animation limit of GCN network G is defined as the smallest model depth т such that for any nodes' column-normallzzd featured matrix input X in the network G the following inequality holds:
||GCN(X;T) - II" S.
(5)
For representation convenience, we can also denote the suspended animation limit of GCN defined on network G as ((G) (or for simplicity if there is no ambiguity problems).
Based on the above definition, for GCN with identity FC mappings, there exists tight bound of the suspended animation limit for the input network.
THEOREM 2. Let Z A X2 2 .... 2 An be the eigen-values of matrix A defined based on network G, then the corresponding suspended animation limit of the GCN model on G is bounded
log min; (+(())
<
max| (22, pall
In the case that the network G is a d-regular, then the suspended animation limit of the GCN model on G can be simplified as
log 5 1 ma, |A.13
The suspended animation limit bound derived in the above theorem generally indicates that the network structure G determines the maximum allows depth of GCN. Among all the eigen-values of Å defined network G, Xy measures how far G is from being disconnected; and Xn measures how far G is from being bipartite. In the case that G reducible (i.e., A2 = 1) or bipartite (i.e., and the model will not suffer from the suspended animation problem.
X, 1), we have Ç
In the appendix of Kipl & Welling (2016), the authors introduce a naive-residual based variant of GCN, and the sepctral graph convolational operator is changed follows (the activation function also changed to sigmoid function instead):
(k)
(A (H(k-")((k-1)))) + (k-1))
For the identity fully-connected layer mapping, the above equation can be reduced to the following lazy Markov chain based layers
H (k) = (-AH H (
(9)
Such residual term will not help resolve the problem, and it will still suffer from the suspended animation problem with the following suspended animation limit bound:
Let 1 2 X 2 2>>0 2.. An be the eigen-values values of matrix À defined based on network G, then the corresponding suspended animation limit of the GCN model (with lazy Markov chain based layers) on G is bounded
COROLLARY 1.
log min; (()))
0
(10)
A2
Proofs to Theorem 2 and Corollary I will be provided in the appendix as well.
4.2 OTHER PRACTICAL FACTORS IMPACTING THE SUSPENDED ANIMATION LIMIT
According our preliminary experimental studies, GCN is quite sensitive model. Besides the impact of input network explicit structures (e.g., network size directed vs undirected links, and network eigenvalues) as indicated in the bound equation in Theorem 2 many other factors can also influence the performance of GCN model a lot, which are summarized as follows:
Network Degree Distribution: According to Theorem I if the input network G is directed and unweighted, the Markov chain layers convergence will project the features II'
5

---

correlated based on network Under review as a conference paper at ICLR 2020
Table 1: A Summary of Graph Residual Terms and Physical Meanings.
Name
Residual Term
Description
naive resid-
Node residual terms are assumed to be independent and determined by the current state only.
R (H(k-1) X; G) H (k-1)
ual
graph-naive
Node residual terms structure, and can be determined by the current state.
residual
R (H()))) X; G) ÁH
raw ual
resid-
Node residual terms are assumed to be independent and determined by the raw input features only.
R (1-1)) X; = =X
graph-raw residual
Node residual terms are correlated based on network structure, and determined by the raw input features.
R (H(k-1),
X; AX
IT', ,.',, I') where π (i) is determined by the degree of node ;; in the network. For any two nodes Ui, Dj E V, the differences of their learned representation can be denoted as
d(v,, = (i( 1( Σ II(i,)) II(i, k)] d2 [d(e;) d(o;)] (11)
2
According Newman 2003). ) the node degree distributions in most complex networks fol- low the power-lay law Faloutsos et al. (1999), i.e., majority of the nodes are of very small de- grees. Therefore, for massive nodes in the input network with the same (or close) degrees, the differences between their learned representations will become not distinguishable.
Raw Feature Coding: Besides the input network, the raw feature coding can also affect the learning performance greatly. Here, we can take the GCN with one single Markov chain layer and one identity mapping layer. For any two nodes V2 Ui E V with raw feature vectors X(i, :) and X (j,:), we can denote the differences between their learned representations as follows:
d(. my) - 1 -A(.))A((.))
x x|,-
(12)
Different from Equation [1 analysis the above equation is not based on the stationary representation of the nodes, and it is based on the MC-layer representation as indicated in Equation (3) and Equation (4). For the one-hot feature coding used in the source code of
GCN Kipf & Welling (2016) and other GNNs, matrix X can be also very sparse well. Meanwhile, vector (i.:) Ajj::) is also sparse vector, which renders the right-hand-
side term to be very small value.
Training Set Size: Actually, the nodes have identical representation and the same labels will not degrade the learning performance of the model. However, if such node instances actually belong to different classes, it will become great challenge for both the training and test stages of the GCN model.
Similar to the existing deep models, deep GNNs will also suffer from the gradient vanishing/exploding problems Pascanu et al. (2012), which will also greatly affect the learning performance of the models.
Gradient Vanishing/Exploding
Although these factors mentioned above not involved in the suspended animation limit bound representation, but they do have great impacts on the GCN model in practical applications. In the following section, we will introduce graph residual network GRESNET, which can be useful for resolving such a problem for GCN.
GRAPH RESIDUAL NETWORK
Different from the residual learning in other areas, e.g., computer vision He et al. (2015). where the objective data instances are independent with each other, in the inter-connected network learning setting, the residual learning of the nodes in the network are extensively connected instead. It renders the existing residual learning strategy less effective for improving the performance of GCN.
5.1 GRAPH RESIDUAL LEARNING
Residual learning initially introduced in He et al. 2015 divides the objective mapping into two parts: the inputs and the residual function. For instance, let H(x) be the objective mapping which projects input x to the desired domain. The ResNet introduced in He et al. (0155) divides H (x) as F(x) + R(x) (where R(x) = x is used in He et al. (015)). This reformulation is motivated by the counterintuitive phenomena about the degradation problem observed on the deep CNN. Different

---

Under review as a conference paper at ICLR 2020
GCN
GResNet (naive)
GResNet (graph naive)
GResNet (raw)
GResNet (graph raw)
G
X
G
X
G
X
G
X
G
X
Å
SGC
SGC
SGC
SGC
SGC
ReLU
ReLU
ReLU
Å
ReLU
ReLU
Ä
SGC
SGC
SGC
SGC
SGC
softmax
A
SGC
SGC
SGC
SGC
SGC
SGC
SGC
SGC
A
SGC
SGC
SGC
SGC
Å
SGC
SGC
SGC
SGC
ReLU
ReLU
ReLU
ReLU
SGC
SGC
A
SGC
SGC
softmax
softmax
softmax
softmax
Figure 2: A comparison of vanilla GCN and GRESNET (GCN) with different graph residual terms. The vanilla GCN has two layers, and the GRESNET models have deep architecture which involves seven layers of SGC operators. The intermediate ReLU activation functions used between sequential layers in GRESNET are omitted for simplicity. Notation Á denotes the normalized adjacency matrix of input network G, which indicates the correlated graph residual terms.
from the learning settings of CNN, where the data instances are assumed to be independent, the nodes inside the input network studied GCN are closely correlated. Viewed in such perspective, new residual learning mechanism should be introduced for GCN specifically.
Here, we need to add a remark: For the presentation simplicity in this paper. given the objective (x)) = Fxx) + (x),, we will misuse the terminologies here: we will name F(xx as the approxi- mated mapping of H (x). and call R(x) as the graph residual term. Formally, by incorporating the residual learning mechanism into the GCN model, the node representation updating equations (i.e., Equation 2 can be rewritten as follows:
(o)
X
H ReLU (A + H (1-1) 1)X; E (1,2, ... KK 1}, (13)
Y = softmax
(AH(KI) + (K X:
[KK The graph residual term R (H(+-1), X; Vk E {1,2, ... , can be defined in different ways. We have also examined to put R (H X: G) outside of the ReLU(.) function for the hidden layers (i.e., (k) ReLU (AH
(H(+-1), x; X)G),, whose performance is not good as what we show above. In the appendix of Kipf & Welling (2016), by following the ResNet (CNN) He et al. 2015), the graph residual ferm R (H X; G) is simply defined as (k-1), which named as the naive residual term in this paper (Here, term "naive" has disparaging meanings). However, according to the studies, such a simple and independent residual term for the nodes fail to capture information the inter-connected graph learning settings.
5.2 GRESNET ARCHITECTURE
In this paper, we introduce several other different representations of the graph residual term, which are summarized in Table feature dimension adjustment is needed, e.g., for raw residual term, an extra variable matrix Wad'' can be added to redefine the terms (which are not shown in this paper). For the graph residual term representations in Table naive residual and raw residual are based the assumption that node residuals are independent and determined by either the current state or the raw features. Meanwhile, the graph naive residual and graph raw residual assume the residual terms of different nodes correlated instead, which can be computed with the current state or raw features. We also illustrate the architectures of vanilla 2-layer GCN and the 7-layer GRESNETS (taking GCN the base model) with different graph residual terms in Figure 2 We

---

Under review as a conference paper at ICLR 2020
2
Chocksee candla Guneeeni Sannoh maniiaee
Uypel
64
ChaskesiGh
Cik (3k-09-1335 Sranme
ChapeatcC 5
Chomist22 Su acb
453
603
1003
230
600
$30
1030
26
483
600
1093
epect tont,
(a) Training Accuracy GREsNET(naive)
(b) Testing Accuracy GREsNET(naive)
(c) Training Accuracy GRESNET(graph-naive)
(d) Testing Accuracy GRisNeT(grap--nivve)
0.-
19.
3.08
000
as-
06
ChankellC Awulaaee
02-
700
430
100
902
1300
453
eln
3000
200
aic 609
$30
1099
are o63
1963
ioining
(c) Training Accuracy GRESNET(raw)
(f) Testing Accuracy GRESNET(raw)
(g) Training Accuracy GRESNET((raph-raaw
(h) Testing Accuracy GREsNETKgraph
Figure 3: The learning performance of GRESNET with GCN as the base model and different graph residual terms on the Cora dataset: (a)-(b) GRENNET(GCN, naive); (c)-(d) GRCNN graph-naive); (f)-(f) GRENNET(GCN, raw): (g)-(h) GRENNET(GCN, graph-raw). For plot (b), the curves corresponding to the 5-layer, 6-layer and 7-layer models are hidden by the legend. For plot (c) and (d), the curve of 7-layer model is hidden by the legend.
need to add a remark here that similar solutions to the raw residual terms have been studied in the latest research papers Wang et al. (2018): Wang & Gupta (2018) as well. However, in this paper, we aim to generalize such techniques as a unified framework, which can accept different types of residual terms not just the raw residual term.
Vanilla GCN: For the vanilla GCN network used in Kipf & Welling (016)), i.c., the left plot of Figure 2 given the inputs G and X, employs two SGC layers to project the input to the objective labels. For the intermediate representations, the hidden layer length is 16, and ReI.U is used as the activation function, whereas softmax is used for output label normalization.
GRESNET Network: For the GRESNET network, i.e., the right four models in Figure [2] they accept the identical inputs as vanilla GCN but will create graph residual terms to be added to the intermediate representations. Depending on the specific residual term representations adopted, the corresponding high-way connections can be different. For the hidden layers involved in the models, their length is also 16, and ReLU is used as the activation function for the intermediate layers.
By comparing the output Y learned by the models against the ground-trute -ruth Y of the training in- stances, all the variables involved in the model, i.e., O can be effectively learned with the back- propagation algorithm to minimize the loss functions ((Y, Y: θ) (or E(@) for simplicity). In the following part, we will demonstrate that for the GRESNET model added with graph residual terms. It can effectively avoid dramatic changes to the nodes' representations between sequential layers.
5.3 GRAPH RESIDUAL LEARNING EFFECTIVENESS ANALYSIS
In this part, we will illustrate why the inclusion of the graph residual learning be effective for learning deep graph neural networks. Here, we assume the ultimate model that we want to learn as H : X > y, where X' and y denote the feature and label spaces, respectively. For analysis simplicity, we have some assumptions about the function H Zaeemzadeh et al. (2018).
AssumptiOn 1. Function H is differentiable, invertible and satisfies the following conditions:
Vx, y, E X with bounded norm, 3a > 0, [| (x) - H')y))z|| S a ||x -xll ||2]].
Vx,Y E X' with bounded norm, 33 > 0, |
H H-)()) < 3 |x -yl.
3x E X with bounded norm such that Det(H' (x)) > 0. In the above conditions, terms a and 3 are constants.
To model the function H, the GRESNET actually defines a sequence of K sequential mappings with these K layers:
(14) where x( (k- and (A) denote the intermediate node representations serving as input and output of the kes layer. (() and (.)- denote the function approximation and residual term
(k) = () (x (k-))
-)) + R( (kk-1)//0000 (xx(xx1)))
8

---

Under review as a conference paper at ICLR 2020
Table 2: Best performance (accuracy) and model depth summarization of GRESNET with different
residual terms on the benchmark datasets (we take GCN, GAT and LOoPYNET as the base models).
Methods
Datasets (Accuracy & Model Depth)
Basc Models
Residuals
Cora
Citeseer
Pubmed
vanilla GCN
Kipf & Welling (2016)
0.815
2-1ayer
0.703
2-layer
0.790
2-layer
naive
0.814
3-layer
0.710
3-layer
0.814
3-layer
graph-naive
0.833
2-layer
0.715
3-yeyrr
0.811
2-layer
GCN
raw
0.826
4-layer
0.727
4-ayer
0.810
3-layer
graph-raw
0.843
5-layer
0.722
4-layer
0.817
7-1ayer
vanilla GAT
Veličković et al. (018))
0.830
2-layer
0.725
2-layer
0.790
2-layer
naive
0.844
5-layer
0.735
5-layer
0.809
3-layer
graph-naive
0.855
3-layer
0.732
4-yyer
0.815
5-layer
GAT
raw
0.842
3 l-yayer
0.733
3-layrr
0.814
4-lyer
graph-raw
0.847
3-layer
0.729
5-layer
0.822
4-yyer
vanilla LOOPYNET (Zhang] 2018))
0,826
2-layer
0.716
2 2-layer
0.812
2-layer
naive
0.833
2-layer
0.728
3-layer
0.830
4-layer
graph-naive
0.832
2-layer
0.728
3-layer
0.819
2- 2-layer
LOoPyNET
raw
0,836
2 2-layer
0.730
5-layer
0.828
4-layer
graph-raw
0.839
4-layer
0.737
5-layer
0.814
4-layer
learned by the k - leh layer of the model. When training these K sequential mappings, we have the following theorem hold for the representation gradients in the learning process.
THEOREM Let H denote the objective function that we want to model, which satisfies Assump- tion 7 in learning the K K-layer GRESNET model, we have the following inequality hold:
)))
)
) (x(
(1 - 8)
-
1 (1+
(15)
[x(k)
1 1x
2
where 8 < (2g(2K) and c C1 maxfa- 8 (1 3), 3. (2 a) + a) for some ei >
Proof of Theorem 3 will be provided in the appendix. The above theorem indicates that in the learning process, the norm of loss function against the intermediate representations doesn't 't change significantly between sequential layers. In other words, GRESNET can maintain effective represen- tations for the inputs and overcome the suspended animation problem. In addition, we observe that log(2K),
the bound of the gap term 5, i.e., c. K decreases K increases (when K 2 2). Therefore, for deeper GRESNET, the model will lead to much tighter gradient norm changes, which is desired
property. In the following section, we will provide the experimental results of GRESNET compared against their vanilla models on several graph benchmark datasets.
EXPERIMENTS
To demonstrate the effectiveness of GRESNET in improving the learning performance for graph neural networks with deep architectures, extensive experiments will be done several graph benchmark datasets. Similar to the previous works on node classification Kipf & Welling (2016); Veličković et al. (2018), the graph benchmark datasets used in the experiments include Cora, Cite- seer and Pubmed from Sen et al. (2008). For fair comparison, we follow exactly the same experi- mental settings as Kipt & Welling (2016) on these datasets.
In this paper, we aim at studying the suspended animation problem with the existing graph neural networks, c.g., GCN Kipf & Welling (2016). GAT Veličković et al. (2018) and LOOPYNET Zhang (0188). where LOoPYNET is not based on the spectral graph convolutional operator. We also aim to investigate the effectiveness of these proposed graph residual terms in improving their learning performance, especially for the models with deep architectures. In addition, to make the experiments self-contained, we also provide the latest performance of the other baseline methods on the same datasets in this paper, which include state-of-the-art graph neural networks, e.g., APPNP Klicpera et al. (2019), GOCN Jiang et al. (2019) and GraphNAS Gao et al. (2019), existing graph embedding models, like DeepWalk Perozzi al. (2014), Planetoid Yang et al. (2016) and MoNet Monti et al. (2016) and representation learning approaches, like ManiReg BamiRegBBllin Belkin et al. (2006), SemiEmb Weston et al. 20088. I.P Zhu al. (2003) and ICA Lu & Getoor 20003).

---

Under review as a conference paper at ICLR 2020
Table 3: Learning result accuracy of node classification methods. In the table, "-' denotes the results of the methods on these datasets are not reported in the existing works. Performance of GCN, GAT and LOOPYNET shown in Table are not provided here to avoid reporting duplicated results.
Datasets (Aceuracy)
Methods
Cora
Citeseer
Pubmed
LP (Zhu et al. 2003))
0,680
0.453
0,630
ICA (Lu & Getoor (2003)
0.751
0.691
0.739
ManiReg (Belkin al. 2006)
0.595
0.601
0.707
SemiEmb Weston et al.
(2008)
0.590
0.596
0.711
Deep (Perozzi et al. (2014))
0.672
0.432
0.653
Planctoid Yang ct al.
()0
0.757
0.647
0.772
MoNet (Monti
2016))
0.817
0.788
APPNP Klicpera al. (019))
0.851
0.757
0.797
GOCN (iang et al. ( (2019)
19)
0.848
0.718
0.797
GraphNAS (Gao et al. (2019)
0.731
0.769
GRESNET(GCN)
0.843
0.727
0.817
GRESNET(GAT)
0,855
0.735
0.822
CRESNEY(LOOPPNETT)
0.839
0.737
0,830
Reproducibility: Both the datasets and source code used in this paper can be accessed via lint Detailed information about the server used to run the model can be found at the footnote
6.1 EFFECTIVENESS OF THE GRAPH RESIDUAL TERMS
In addition to Figure D for GCN (bias disabled) on the Cora dataset, as shown in Figures 9 in the appendix, for the GCN (bias enabled) and GAT with deep architectures, we have observed similar suspended animation problems. Meanwhile, the performance of LOOPYNET is different. Since LOOPYNET not based on the spectral graph convolution operator, which accepts nodes' raw features in all the layer (it is quite similar to the raw residual term introduced in this paper). As the model depth increase, performance of LOOPYNET remains very close but converge much more slowly. By taking GCN as the base model, we also show the performance of GRESNET with different residual terms in Figure 3 By comparing these plots with Figure both naive and graph- naive residual terms help stabilize the performance of deep GRESNET the raw and graph-raw residual terms, their contributions are exceptional. With these two residual terms, deep GRENNET(GCN)s can achieve even better performance than the shallow vanilla GCNs.
Mcanwhile, for
Besides the results on the Cora dataset, in Table we illustrate the best observed performance by GRESNET with different residual terms based GCN, GAT and LOOPYNET base models respectively on all the datasets. Both the best accuracy score and the achieved model depth are provided. According to the results, for the vanilla models, GCN, GAT and LOOPY can all obtain the best performance with shallow architectures. For instance on Cora, GCN(2-layer) obtains 0.815; GAT(2-layer) gets 0.830; and LooPYNeT((-layee)) achieves 0.826, respectively. Added with the residual terms, the performance of all these models will get improved. In addition, deep GRESNET(GCN), ((AA)) and GRESNEY(LOPPYNET) will be able to achieve much better results than the shallow vanilla models, especially the ones with the graph-raw residual terms. The best scores and the model depth for each base model on these datasets are also highlighted. The time costs of learning the GRESNET model is almost identical to the required time costs of learning the vanilla models with the same depth, which are not reported in this paper.
6.2 A COMPLETE COMPARISON WITH EXISTING NODE CLASSIFICATION METHODS
Besides the comparison with GCN, GAT and LOoPYNET shown in Table 2 to make the experi- mental studies more complete, we also compare GRESNET(GCN)) GRESNET(GAT) and GRES- NET(LOOPYNET) with both the classic and the tfate-of-the-ar models, whose results are provided in Table In the table, we didn't 't indicate the depth of the GRESNET models and results of GCN, GAT and LOOPYNET (shown in Table already) are not included. According to the results, com- pared against these baseline methods, GRESNETS can also outperform them with great advantages. Without the complex model architecture extension or optimization techniques used by the latest methods APPNP A Klicpera et al. 2019)) GOCN Jian et al. (2019) and GraphNAS Gao et al. 2019))
'GPU Server: ASUS X99-E WS motherboard, Intel Core i7 CPU 6850K @ 2.36..Gi 3.6GHz (6 cores). 3 Nvidia GeForce GTX 1080 Ti GPU (11 GB buffer each), 128 GB DDR4 memory and 128 GB SSD swap. For the deep models which cannot fit in the GPU memory, we run them with CPU instead.
10

---

Under review as a conference paper at ICLR 2020
adding the simple graph residual terms into the base models along already improve the learning performance greatly.
7 CONCLUSION
In this paper, we focus on studying the suspended animation problem with the existing graph neural network models, especially the spectral graph convolutional operator. We provide a theoretic anal- ysis about the causes of the suspended animation problem and derive the bound for the maximum allowed graph neural network depth, i... the suspended animation limit. To resolve such problem, we introduce a novel framework GRESNET, which works well for learning deep representations from the graph data. Assisted with these new graph residual terms, demonstrate that GRESNET can effectively resolve the suspended animation problem with both theoretic analysis and empirical experiments several benchmark node classification datasets.

---

Under review as a conference paper at ICLR 2020
REFERENCES
N. Ahn, B. Kang, and K. Sohn. Fast, accurate, and, lightweight super-resolution with cascading residual network. CoRR, 02//1803.08644, 2018.
Atwood and Towsley. Diffusion-convolution neural networks. In NIPS, 2016.
W. Bae, J. Yoo, and Ye. Beyond deep residual learning for image restoration: Persistent homology- guided manifold simplification. CoRR, 1ess/161..0645,, 2016.
Y. Bai, H. Ding, Y. Sun, and W. Wang. Convolutional set matching for graph similarity, arXiv preprint arXiv: 1086, 2018.
P. Bartlett, S. Evans, and P. Long. Representing smooth functions as compositions of near-identity functions with implications for deep network optimization. CoRR, his/1804.05011. 2018.
Sanchez-Gonzalezz Gonzalez, V. Zambaldi, M. Malinowski, A. Tac- chetti, D. Raposo, A. Santoro, R. Faulkner, C. Gulcehre, F. Song, A. Ballard, J. Gilmer, G. Dahl, A. Vaswani, K. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv preprint orXiv:1806.01260 2018.
Battaglia, Hamrick, Bapst, A. Sanchez-
J. Behrmann, W. Grathwohl, R. Chen, D. Duvenaud, and J. Jacobsen. Invertible residual networks. In ICMI., 2019.
M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res., 2006.
Chen, T. Ma, and C. Xiao. Fastgen: Fast learning with graph convolutional networks via impor- tance sampling. CoRR, 0bss/1801.1222 2018.
M. Faloutsos, P. Faloutsos, and C. Faloutsos. On pawer-law relationships of the internet topology. In SIGCOMM, 1999.
Y. Gao, H. Yang. P. Zhang, C. Zhou, and Y. Hu. Graphnas: Graph neural architecture search with reinforcement learning. CoRR, abs/1904.09981, 2019.
A. Gomez, M. Ren, R. Urtasun, and R. Grosse. The reversible residual network: Backpropagation without storing activations. In NIPS. 2017.
W. Hamilton, R. Ying. and J. Leskovec. Inductive representation learning on large graphs. CoRR, abs/1706.02216, 2017.
D. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129 150, 2011.
D. Han, J. Kim, and J. Kim. Deep pyramidal residual networks. CoRR, 2bx/16100000111522000
K. He. Deep residual networks: Deep learning gets way deeper. httts::/ Eutorials/ cm12016 tutorial deep residual networks 2016. [Online; accessed S001ember-2011
herssidual_etttokkkkkk kaiminghe.paf
K. He, Zhang, S. Ren, and Sun. Deep residual learning for image recognition. CoRR, abs/1512.03338 2015.
O. Hölder. Ueber einen mittelwertsatz. Nachrichten von der Königl., 2, 1889.
B. Jiang, Z. Zhang, J. Tang, and B. Luo. Graph optimized convolutional networks. CoRR, abs/1904, 11883, 2019,
T. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.00 02200009900000..... 2016.
Klicpera, A. Bojchevski, and S. Gunnemann. Combining neural networks with personalized pagerank for classification on graphs. In ICLR, 2019.
12

---

Under review as a conference paper at ICLR 2020
J. Li, F. Fang, K. Mei, and G. Zhang. Multi-scabe residual network for image super-resolution. In ECCV, 2018a.
Q. Li, Z. Han, and X. Wu. Deeper insights into graph convolutional networks for semi-supervised learning. CoRR, abss/801.000i 2018b.
Liu, C. Chen, X. Yang. Zhou, X. Li, and L. Song. Heterogeneous graph neural networks for malicious account detection. In CIKM, 2018.
Q. Lu and Getoor. Link-based classification. In ICML, 2003.
Masci, D. Boscaini, M. Bronstein, and Vandergheynst. Geodesic convolutional neural networks on riemannian manifolds. In CVPR workshops, 2015.
Monti, D. Boscaini, J. Masci, E. Rodolå, Svoboda, and M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. CoRR, abs/1611 1.08402, 2016.
F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In CVPR, 2017.
M. Newman. The structure and function of complex networks. SIAM REVIEW, 45(2):2003, 2003.
M. Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. In ICML., 2016.
Noriis Markov chains. Cambridge University Press, 1998.
R. Pascanu, T. Mikolov, and Y. Bengio. Understanding the exploding gradient problem. CoRR, abs/1211.5068 2012.
B. Perozzi, AI-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. In KDD, 2014.
Scarselli, M. Gori, A. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. Trans. Neur. Netw,, 2009.
P. Sen, G. Namata, M. Bilgic, I.. Getoor, B. Gallagher, and T Eliassi-Rad. Collective classification in network data. Al Magazine, 2008
R. Srivastava, K. Greff, and J. Schmidhuber: Highway networks. CoRR, abs/1505.00387, 2015.
Y. Sun, R. Barber, M. Gupta, C. Aggarwal, and J. Han. Co-author relationship prediction in hetero- geneous bibliographic networks. In ASONAM, 2011.
Y. Tai, J. Yang, and X. Liu. Image super-resolution via deep recursive residual network. In CVPR, 2017.
Veličković, Cucurull, A. Casanova, Romero, Liò, and Y. Bengio. Graph Attention Net- works. In ICLR, 2018.
N. Wang, Y. Zhang, Z. Li, Fu, W. Liu, and Y. Jiang. Pixel2mesh: Generating 3d mesh models from single RGB images. CoRR, abss/804.00154, 2018.
X. Wang and A. Gupta. Videos as space-time region graphs. CoRR, abs/1806.01810, 2018.
X. Wang, H. Ji, C. Shi, B. Wang, Y. Ye, P. Cui, and P. Yu. Heterogeneous graph attention network. In wwW, 2019.
J. Weston, F. Ratle, and R. Collobert. Deep learning via semi-supervised embedding. In ICML, 2008.
Yang, W. Cohen, and R. Salakhutdinov. Revisiting semi-supervised learning with graph embed- dings. CoRR, abs//600.0088.. 2016.
F. Yu, V. Koltun, and T. Funkhouser. Dilated residual networks. CoRR, abs/1 700.00994, 2017.
13

---

Under review as a conference paper at ICLR 2020
A. Zaeemzadeh, N. Rahnavard, and M. Shah. Norm- comm-preeervation Why residual networks can become extremely deep? CoRR, abs/1805.07477, 2018.
J. Zhang. Deep loopy neural network model for graph structured data representation learning. CoRR, 2018.
Zhang, B. Dong, and P. Yu. Fake news detection with deep diffusive network model. CoRR, abs/1805.08751, 2018.
J. Zhou, G. Cui, Z. Zhang, C. Yang. Z. Liu, and M. Sun. Graph neural networks: A review of methods and applications. CoRR, abs/ 1b2//184,.0844, 2018.
X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and har- monic functions. In ICML, 2003.
14

---

Under review as a conference paper at ICLR 2020
8 REBUTTAL NEW MATERIALS
8.1
EXPERIMENTAL RESULTS ON OTHER LARGER DATASETS
We added the experimental results on the PPI and Reddit datasets in the following table. Detailed information about datasets is as follows:
PPI: Node #: 14,755; Edge #: 225,270; Feature #: 50; Class 121
Reddit: Node #: 232, 965; Edge 11,606,919; Feature #: 602; Class #:
We need mention that GAT used in GResNet is very slow large datasets (it is not our problem but the problem with the GAT base model), we cannot get the results of GResNet(GAT) out on Reddit during the rebuttal period. Since PPI and Reddit are common used in other graph neural network papers, so many of the entries in Table 4 are not provided. We will add these results in the camera-ready version of this paper later.
Table 4: Learning result on larger datasets.
Datasets (Accuracy)
Dataset (micro-averaged FI)
Methods
Cora
Citeseer
Pubmed
PPI
Reddit
LP (Zhu et al. 2003
0.680
0.453
0.630
ICA (Lu & Getoor (0033)
0.751
0.691
0.739
ManiKeg (Belkin el al.
(0066)
0.595
0.601
0.707
SemiEmb Weston
(2X88
0.590
0.596
0.711
DeepWalk Peroozi
al.
2014)
0.672
0.432
0.653
0.324
Planetoid Yang et al 20
(6)
0.757
0.647
0.772
MoNet Mont et al. 2016
0.817
0.788
APPNP Klicpera
al. (019
0.851
0.757
0.797
GOCN Rang et al 20019)
0.848
0.718
0.797
Graph (Gao et al,
2019
0.731
0.769
GCN Kipp & Welling
(2016)
0.815
0.703
0.790
0.500
0.930
GAT Venckovie et (2088)
0.830
0.725
0.790
0.973
LOoPYNET (Zhang (2018)
0.826
0.716
0.812
GraphSAGE (Hamiton et al.
2017
0.612
0.954
FastGCN (Chen et al. (2018)
0.850
0.880
0.513
0.937
GCN)NET(GCN)
0.843
0.727
0,817
0.832
0.950
GRESNET(GAT)
0.855
0.735
0.822
0.987
GRESNET(LOOPYNETT)
0.839
0.737
0.830
0.980
0.955
15

---

Under review as a conference paper at ICLR 2020
8.2
EXPERIMENTAL RESULTS ON DEEPER MODELS
8.2.1 DEEPER MODEL PERFORMANCE SUMMARY
As suggested by the reviewers, we also add the studies of GCN, GRESNET(GCN, naive), GRES- NET(GGN, graph-naive), GGNN raw) and GGEN graph-raw) with deeper architectures (more than 7 layers) on the Cora dataset in the following table and plots
As illustrated in 7 we show the experimental results on Cora obtained by the models with 2, 10, 20, 30, 40, 50 layers. respectively. According to the numbers, GCN cannot really work well for all the layers other than 2, and the performance of the naive and graph-naive residual terms is not good neither. However, the performance of the raw and graph-raw residual terms is exceptionally great. For instance, for the model with 40 layers, GRENNET(GCN, raw) and GRESNET(GCN, graph-raw) can still achieve 0.790 and 0.838 as the accuracy scores.
Table 5: Learning result by models with deeper architectures.
Model Depth (Aceuracy)
Methods
20
30
40
50
GCN
0.815
0.174
0.072
0.072
0.072
0.072
GCNN naive)
0.804
0.416
0.126
0.057
0.057
0.057
GRENNET(GCN, graph-naive)
0.833
0.169
0.057
0.057
0.057
0.057
GRENNET raw)
0.815
0,814
0.802
0.812
0.798
0.800
GRESNET(GCN, graph-raw) 0.813
0.823
0.823
0.818
0.838
0.799
8.2.2 DEEPER MODEL LEARNING LOSS ON TRAINING AND TESTING SETS PER EPOCH
In addition to Table 7 we also illustrate the performance of the models in the learning process in Figures 8 where both the training accuracy and testing accuracy on each epoch are provided. Ac- cording to the results, GCN and GRESNET(GCN, graph-naive) will fail to work when the model architecture goes deeper. GRESNET(GCN, naive) can slightly revive the models for 10 layers, but will also fail to work for deeper architectures, c.g., 20, 30, 40 and 50 layers. However, GRES- NET(GCN, raw) and GREN graph-raw) work very great for all these different depth in the plot, which also illustrate the effectiveness of the and graph-raw residual terms proposed in this paper.
1.0
0.8
training accuracy %6
0.8
testing accuracy %
0.6
GCN(2-leyer)
GCN12-layer)
GCM(1-llaye)
0.4
GCN110-layer)
0.4
GCN(20llayer)
GCN120-layer)
GCN(30 layer)
GCN130-layer)
0.2
GCNr40-layer)
0.2
GCN140 layer)
GCNr50-layer
GCN150-layer)
200
400
600
800
1000
200
430
600
800
1000
spach
over training set)
epoch over training set)
(a) Training Accuracy
(b) Testing Accuracy
Figure 4: Deeper GCN on Cora.
16

---

Under review as a conference paper at ICLR 2020
training accuracy
testing accuracy %
0.6
0.6
GReeNettGGN, 2aave,
SRkesNeet/ccNnnaie.2222 2aaye,
GResNetiGCN,nali 1i-leeeeeelllee
0.4
GResNet) 1-lye_
0.4
GResNet(SSN, 3D layer)
GRoslict/@CMmaavv..o0 30-laa0
0.2
GResNettGGN,nee www.eeneaaee...aaaaaaaaeeee 40-layrr)
0.2
GResNet l0-laer)
GResNetrGCN,nalves 50llel
GReNNei(GCNnaive 50-layer)
0
200
400
600
800
1000
epoch |iter. over training set)
epoch over training
(a) Training Accuracy
(b) Testing Accuracy
Figure 5: Naive Residual: deeper GRESNET(GCN, naive) on Cora.
1.0
0.8
training accuracy %0
testing escuracc %
0.6
0.6
GResNe:lGON.ora hatpo/iigraaaaeeeeeaaeeeeeeeeeee nelve.2-layer)
GResNexGCN.araap hwtpS//noraaaaaeevveeeeeeeeeeeee naive.2-layer)
GResNet(GONNoraa nelyee.0-leyeer
0.4
GResNel(GON.ee hrarahhnaiiee neive.10-layerr
0.4
GResNestGCN..raape hatpphhnaaee.e-laeeeeeeee
GResNeeGGCN.grapp 20-lae20--lyer
0.2
GResNe:tGON.eraa naive 40-layr)
GResNet//CCN.gren
Sttp://CN..aaa_eeeeeee3. 30-lee30-layer)
0.2
GResNe:/GCN.erath haarraahhhhiiiee paiiee40-laaeeeee
WBesNeetGCNNgraph nalve.30-layee
0.0
200
400
600
800
1000
0
200
400
600
800
1000
epoch (iter. over training set)
epoch (iter. over training set)
(a) Training Accuracy
(b) Testing Accuracy
Figure 6: Graph-Naive Residual: deeper GRESNET(GCN, graph-naive) on Cora.
1.0
train ng accuracy %
0.7
0.6
GResNet(GCN.nol 2-ayer)
0.5
GResNetiSCN.raw.2lvyg
GResNet/GCN.nww.10.. 10-layr)
GReINetIGCN,raw.10.yy
GkesNeet/CNNraw.200 layer)
GResNetIGCN, 20-2aayy
GResNetiGCN.raww
GResNettGGN.raw.30lbbo
GResMetiCCKuuaa..00.lyye 40-layry
GReaNettGGN,/owe
GResNeet(GCNraaw50 layer)
0.2
GResNellGCN,rew (0..5lly
800
1000
200
400
600
800
1000
epoch (iter. over training set
epoch (iter. over training set)
(a) Training Accuracy
Testing Accuracy
Figure 7: Raw Residual: deeper GRESNET(GCN, raw) on Cora.
1.0
0.8
0.8
0.7
testing accuracy
0.6
0.6
GResNatiGCN. raw.2-layer)
0.5
GResNat(GCN graph_ras wawphrrww,.aaaa layeri
GResNetiGCN, graph raw.y1-tayer)
GResNet(GGN.gre graph. 10 10-layer)
0.4
CResNetiGON. haaph_rrw.2--lyyer
0.4
GRosNat(GGN grappc graph_raw,200 raw,200layyrr
GResNetiGCN. graph raw.30-layer)
0.3
GReNNetGCN Graapp raw,30aaayaaaa.a.oooaa 30-layer;
0.2
GResNatiGON. graph raw.sst-oot-t
GResNatiGCN, graph_gappppg raw.40-layer)
0.2
GResNetiGCN Aaa.Aayyrr
GResNat(GCN graallGGNNggahhhnncc hww.gggappaaapaap0
700
400
600
8O0
1000
200
400
600
800
1000
epoch training set)
epoch (iter. training set)
(a) Training Accuracy
(b) Testing Accuracy
Figure 8: Graph-Raw Residual: deeper GRESNET(GCN, graph-raw) on Cora.
We have also studied even deeper model architectures on GRESNET(GCN, raw) and GRES- NET(GCN, graph-raw) 100 layers, which still perform well.
17

---

Under review as a conference paper at ICLR 2020
STUDIES ON OTHER IMPACTING FACTORS WITH RESIDUAL TERMS
By changes to the original raw data, we will be able to get different samples of the data with different properties, e.g., raw features, and the training size. We will illustrate the learning results based on these different settings on the Cora dataset as follows for the reviewers' information.
9.1 TRAINING SET SIZE
Table 6: Learning result by models with deeper architectures.
Training Set Size
(Regular Size: 140)
Methods
140
500
1000
1500
GCN((-layer)
0.815
0.863
0.922
0,933
GCN(S-layer)
0.315
0.331
0.403
0.324
GRESNET(GCN, naive, 2-layer)
0.797
0.842
0.936
0.956
GRESNET(GCN, 5-
0.596
0.748
0.813
0.958
GREESNETTGCNN graph-naive, 2-layer)
0.833
0.862
0.927
0,956
GRENNET(GCN, graph-naive, 5-layer)
0.749
0.797
0.904
0.946
GRESNETIGCN, raw, 2-layer)
0.809
0.799
0.918
0.979
GRESNETGGNN raw. 5-layer)
0.816
0.861
0,932
0,976
GCN, graph-raw, 2-layer)
0.809
0.853
0.929
0,966
GRESNET(GCN, graph-raw, 5-layer)
0.843
0.859
0.917
0.963
9.2 RAw FEATURE ENCODING
Table 7: Learning result by models with deeper architectures.
Feature Coding (Regular Coding: bag-of-word)
Methods
bag-of-word
onc-hot
GCN(2-layer)
0.815
0.795
GCN(5-layer)
0.315
0,199
GRESNET(GCN, naive, 2-layer)
0.797
0,700
GRESNET(GCN, naive, 5-layer)
0.596
0,592
GRESNET(GCN, graph-naive, 2-layer)
0.833
0.797
GRESNET(GCN, graph-naive, 5-layer)
0.749
0.748
GRESNET(GCN, raw, 2-layer)
0.809
0.714
GRESNET(GCN, raw, 5-w,aayyrr)
0.816
0.721
GRESNET(GCN, graph-raw. 2-layer)
0.809
0,746
GRESNET(GCN, graph-raw. 5-layer)
0.843
0.798
18

---

Under review as a conference paper at ICLR 2020
10
APPENDIX
10.1
EXTRA EXPERIMENTAL RESULTS
0.8
0.8
-bayer?
testing eccurac
0.6
GCye-layen
0.6
2CN/2-layer)
GCM(2-layer
GCN(3-ley 3-layer)
GCN(3-layen
training
GCN(4 layer)
0.4
GCN44-layer)
0.4
GCNSS layer)
GCN(S-layer)
GCN66-layer?
GCN(6-layer)
GCN7 layer)
GCM7 layer)
GCN(B-layer?
0.2
CCM(B-layer)
CCN(9-layer?
GCNS
GCN(2D layer?
GCN10 layer)
200
600
1000
200
400
600
800
1000
opech literr training set)
opoch training
(a) Training Accuracy
(b) Testing Accuracy
Figure 9: The learning performance of GCN (bias enabled) the Cora dataset.
baiting S0C.000 9
testing SCCUSSO
0.6
0.5
0.4
GResherGGAT Joume I-ayeri
GReshetiGAT.ooo www.eiGGT.......... 24yyee
0.4
GhhsdettGAT Lann, Lanye, I-laye?
DesseetiAA...oon..... a-yyer
GReshenGAT (none; 3-laeet
GieastttdA Lnons, layer
GResheenGAT.nome n.neee...4 iayert
GR GResMee/GAT nono,4 laye,
GReshenGGTT none, 5-layer
GResteetiAT
GResNetiGAT layee.
GResNeniGAT.oome. T.yyer..byyrrr
011
600
000
1000
200
600 training set)
1000
Ster.
set)
Training Accuracy (GAT)
(b) Testing Accuracy (GAT)
Figure 10: The learning performance of GAT on the Cora dataset
0.8
balhing scurssy
tcc0ing S0OUFSCY
0.6
0.5
LoopsNettt
0.4
LoopyNettl
0.4
Leapuhiet22
LoopyMeetr Heyeri
0.3
Loopyhiet layer
Lempyteett
Lampyhari(A-kyyer
LoopyneenS layer)
Loopyhertt layeri
Inopyhont leyee)
Leopyneen -ayer)
Loapyheet Jayer)
200
400
600
800
3000
200
500
800
1000
spoch fieer. over traininn sec)
epoch (ter. ovet trainin se:)
(a) Training Accuracy (LOOPYNET)
(b) Testing Accuracy (LOOPYNET)
Figure 11: The learning performance of LOOPYNET on the Cora dataset
19

---

Under review as a conference paper at ICLR 2020
10.2
PROOFS OF THEOREM AND LEMMA
10.2.1 PROOF OF LEMMA
LEMMA 1. Given an irreducible, finite and aperiodic graph G, starting from any initial distribution
vector x E R"x (x 2 O and | 1), the Markov chain operating on the graph has one unique
stationary distribution vector π such that lime-soc A'x= T²', where πI" (1) 2| If matrix À
d(v;)
symmetric (i.e., G is undirected), πt" will be uniform distribution over the nodes, Le., π T("
Proof. The stationary distribution vector existence and uniqueness has been proved in Norris 1998).
Here, we need to identify on vector π at convergence such that AT n, i.c.
π (i) Σ ((i))
(16)
According to the definition of Á, it easy to have
Σ Wis (J) = =1)). dn
(17)
where Wi.j denotes the initial connection weight between is and Vy. For the unweighted network, Wi, will be in {0, 1} indicating if o; and vi are connected or not. Notation dw (i) denotes the rough degree of node 2 in the network subject to the weight w : R. which sums the weight of edges connected to the nodes in the network. So, it is enough to have T()) (z). More precisely, can set
(J)
dw
x(j)= Σx (Jw 2/E
(18)
In this case,
Σ(O)T( Σ Wi.j du
Σ
Wij
d
π TT))-
(19)
()) 2
2
2
Meanwhile, for the symmetric and normalized adjacency matrix A, we can prove the stationary distribution (i) 1 in a similar way, which concludes the proof.
n
10.2.2 PROOF OF THEOREM
THEOREM 1. Given input network G = (V,E), which is unweighted, irreducible, finite and ape- riodic, if exist enough nested Markov chain layers in the GCN model, will reduce the nodes' representations from the column-normalizer feature matrix X Raxdz to the stationary repre- sentation II = [ , ..."... -= E I Rudds Furthermore, if G is undirected, then the stationary representation will become II* n 1xxd.
Proof. This theorem can be proved based on Lemma 1. For any initial state distribution vector x R V|x1, for the Markov chain at convergence, we have
lim A'x==". 1-000
(20)
We misuse the notation A lim A In this case,
A A'X-
Å X 1), Axx,,, | π ,...,,"),, T]
A A'x(: dx))
(21)
which together with Lemma conclude the proof.
20

---

Under review as a conference paper at ICLR 2020
10.2.3 PROOF OF THEOREM 2
Prior to introducing the proof of Theorem 2, we will introduce the following lemma first.
LEMMA 2. For any vector E IR", the following inequality holds:
|xx|p - (m) - ||<||,"
(22)
Proof. According to Hölder's incquality Hölder 1889). for Va, b E RIX1 and 1,
la(i)')
[b(i) --2
(23)
i=1
Let aaii) x. |b(r) and r= p'
n 1
x
x
P.
12
xx
(24)
Σ
x
(m)--5
(m)
Therefore,
|x|| =
Σ
xx1i)|1
(n) 1-2
x,1
(25)
1=1
Σ
(n))
1=1
(n)
||x||,
Let 2 A 2 2 An be the eigen-values of matrix À defined based on network G, then the corresponding suspended animation limit of the GCN model G is fightly bounded
THEOREM 2.
min; T()
<
(26)
T- max ()2, 12.1
In the case that the network G is a d-regular, then the suspended animation limit of the GCN model on G can be simplified as
log n max max(Xx,
5 T PAm.)
(27)
Proof. Instead of proving the above inequality directly, we propose to prove that Ç is suspended animation limit by the following inequality instead
A A Vn
n.
(28)
which can derive the following inequality according to Lemma
A - "t"
|| S.
(29)
21

---

Under review as a conference paper at ICLR 2020
Let V1, "2 Vn , be the eigenvectors of Å and Vx
x = Σ xx (x, V Σ aivi
(30)
where (x, vi). Therefore, we have
A = Σ Jasiive
(31)
Considering that A; and V1 - Vx
then
Vn
(x, = Σ x(i)
1
|x|||
1
(32)
Vn
vn
vn'
and
1
aidivi
Vi =
n
(33)
vn
n
n
71
where
Therefore, we have
A
TT"
112
Σ ailivv
Σ x
1=
2 Yaa
Σ
afv. 1
(34)
2=2
$ |x|2
2
mar
- man!
where Aman max{[Aal, AAal
|m = max (2 DAll
Therefore, to ensure
6²
max(A2,|Anl)
(35)
can have
log log n
log n Amaz
5 <
0
(36)
2 2og Amax
10.2.4 PROOF OF COROLLARY 1
COROLLARY 1. Let 1 > X 2.. be the eigen-values of matrix A defined based on
network G, then the corresponding suspended animation limit of the GCN model (with lazy Markov chain based layers) on G is tightly bounded
log min; (+)
(37)
1-
Proof. For the lazy Markov chain layer, we have its updating equation as follows
(H( + (k-1) 1 (A + diag( (dw (i)) H (k-1) (--1-1)
(38)
It is easy to show that À is positive definite and have its eigen-values \1 2 Ao > An 0.
Therefore,
Amax max (22) Asl. An max(A2, [ma X2:
(39)
which together with Theorem 2 conclude the proof.
22

---

Under review as a conference paper at ICLR 2020
10.3 PROOF OF THEOREM 3
Prior to introducing the proof of Theorem 3 we first introduce the following lemma.
LEMMA 3. For any non-singular matrix I + M, we have
maz (M) S mmin (I M) & o mos (I+M) S 1 mao (M),
(40)
where man (.) and mmin (-) denote the maximum and minimum singular values of the input matrix, respectively.
Proof.
Due to the triangle inequality, the upper bound is easy to prove:
o men (I + M) = | + 2 I |||| + | = 1 + o mmnn (M).
(41)
In the case that Oaa MM) 2 1, the lower bound is trivial to prove since I + M is non-singular, we have
minn (I + M) > 0.
(42)
Meanwhile, in the that man (M) < it is easy know that Amaa (M) < 1, where Xmar (-) denotes the latest eigenvalue of the input matrix.
Owin (I + M) = (I+ ()- 111
1)* M
-1
1)
M 112
(43)
-1
M
1
maa (M),
|
which concludes the proof for the lower bound.
THEOREM Let H denote the objective function that we want to model, which satisfies Assump- tion 7 in learning the K K-layer GRESNET model, we have the following inequality hold:
)
)l(
(1 81) 8)
<
s <1+
(44)
0x(k)
(k-
(x(
1
2
2
where 8 < ( and = ei max(aB(1 + B), 8(2 a) + a for some ei > K
Proof. We can represent the Jacobian matrix J of (4) with (k-1) Therefore, we have
a de( (x( 0 0x 0x(k) 0x(k-1) (x(+)
(45)
Matrix J can be rewritten I (x((-1)(x(xx11) where
((k-1)(x( + tv) - ( (xxx1)x
V (F( (x(t-))) = lim
(46)
t-
Meanwhile, it is easy to know that
| [ (x
mmin
<
< max (J)
(47)
(x(k)
xx(()
23

---

Under review as a conference paper at ICLR 2020
Based on the above lemma, have
)
))(@)
(1-o)
-
- o1+
(48)
(x(k)
(x
(x(k)
2
2
where o maa V F (x((=111) 11)
Furthermore, we know that
V V 1x(x=1))vvl
max (VF( supv
|v||
(k= 1) (x (1)) + iv) F(R 1) (x(( 11
(49)
lim supv x-0+
(F(k-1))
where ||-|| denotes the Lipschitz seminorm of the input function and it is defined as
[ (x))1
supxpy
(50)
x x-yll2 y/12
Meanwhile, according to the Theorem in Bartlett (2018) (whose proof will not be introduced here), we know that
p 1/
S log 2K
(51)
which coneludes the proof. In the above equation, K denotes the layer depth of the model.
24


Reviews:
[{"review_id": "S1lx7puZtB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study the problem of adding residual connection to GNN for node classification. The authors first identify the problem referred to as “Suspended Animation” in GNN when the depth increases. Then the authors provide both empirical and theoretical characterization for the behavior. To handle this issue, the authors study several different ways to add residual connections in GNN including the naïve method proposed in Kipf et al. The authors carry out extensive experiments on three datasets on different residual connections for the node classification task.\n\nStrength\n1. The authors identify and study an interesting and important issue in GNN as the “Suspended Animation” issue.\n2. The authors provide both empirical and theoretical analysis for the “Suspended Animation” behavior. Moreover, the authors provide theoretical justification for the added residual connection in GNN as gradient norm bound.\n3. The authors carry out extensive experiments on different variants of residual links. Morover, the authors provide code online for reproducibility.\n\nWeakness:\n1. In the theoretical analysis, the assumption that the FC layer is identical mapping is too simplistic. The analysis differs from the actual model especially when the residual links are considered in equation (8), where we have a sum of FC layer output and residual connection. Actually, the empirical results show that naïve residual links work pretty good on several datasets. It goes against the analysis in Corollary 1.\n2. Though the authors provide bound on the norm of gradient under residual links, it would be better if authors could justify the adding of residual link from the perspective of Theorem 1.\n3. The authors study the depth of GNN up to 7 layers at most. It would be interesting to see how the model performs under really deep networks.\n4. The authors mention several factors to affect GNN in section 4.2. It would be interesting to see how these factors like training data set and feature coding interacts with different ways of adding residual connections.\n5. It is very informative that the authors compare their methods on the widely used three datasets. It would be better if the authors could carry out experiment on larger graphs to verify the empirical observations. For example, do we need to have deeper networks for larger graphs?\n", "extra_scores": {"experience_assessment": "I have published one or two 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": {}}, {"review_id": "HygOfsbjtH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper studies the “suspended animation limit” of various GNNs – an important one for how to train a good Graph network. The authors provide sufficient analysis by simplify GNNs as a series of 1-step Markov chains (which is my concern as stated in the section on main issues), while pointing out the limitations quantitatively as in the Theorem 2. Under the assumption, the authors propose several new forms of ResNets for GCNs, which can successfully overcome the limitation.\n\nOverall, the motivation of this work is clear and meaninfgful. The proposed residual architecture is effective, and the presentation is clear and easy to understand. \n\nHowever, my main concerns are on the initial assumptions for analyzing the suspension of GNNs. See the following comments.\n\nThis paper is generally well written and easy to understand. The organization of each part is well-balanced.\n\nOriginality:\n\nTo the best of my knowledge, numerous methods (i.e., targeting on applications) address this problem by augmenting A [1] or X [2] with similarity of feature representation learned from other sources. However, this paper specifically analyzes the problem in a principle way. I consider this work is generally novel.\n\n[1] X. Wang and A. Gupta. Videos as Space-Time Region Graphs. ECCV 2018.\n[2] N. Wang, Y. Zhang, Z. Li , Y. Fu, W, Liu, Y. Jiang. Pixel2Mesh: Generating 3D Mesh Models from Single RGB Images. ECCV 2018.\n\nSignificance:\n\nThe significance lies mostly in motivation and the proposed GResNet.\n\nMotivation: This paper studies the phenomenal that GNNs tends to not respond to the input data when certain depth of a network is reached, which the authors called as suspended animation limit. Studying problem is fundamental and important, and also unique since different with CNNs where data are independent, the data instance within GNNs are highly correlated.\n\nGResNet: Given the differences, and within the Theorem 2 where the residual formulation of CNNs does not apply to GNNs, the paper also proposes several new formulations, i.e., in figure 2, where the suspension is avoidable and the performance under the same experimental settings is obviously boosted. \n\nMain issues: \nMy major concern to this work lies in the assumption used throughout section 3 and 4. At the beginning of Section 3.2, the authors assume that W is identity. Since X is assumed to be column-wise normalized, the nonlinearity is removable. However, this is not true in real cases: W is actually learnable and not bounded. When W is learned to be negative, Relu layer is not removable, and the behavior of the network will be completely different with what the paper depicted. Indeed, GNNs contain stacked linear+nonlinear functions, which cannot be simplified as a linear Markov chain. It is analogy to CNNs, which is not possibly be simplified as a group of average poolings.\n\nMinor issues:\n1. I agree that under the assumption, eq. (11) shows that the differences between the learned representations are not discriminative, however the claim “majority of the nodes are of very small degrees” is not justified and only apply to the internet topology in Faloutsos et al. (1999).\n\n2. I feel the “Raw Feature Coding” and the “Network Degree Distribution” are sort of repetitive, and the eq. (11) is eq. (12) at the stationary point.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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": {}}, {"review_id": "B1evBVMx5r", "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": "The paper studies the causes of the empirically poor performance in deep structures that plagues existing GNNs, and identify the suspended animation problem as the main issue. In analogy to the Residual CNN network, a residual graph network is proposed to address such issue. Moreover, the underlying Markov chain property such as stationary distribution is theoretically analyzed, the so-called suspended animation limit is defined and its upper and lower bounds are established. Empirical experiments are relatived short and less sufficient, with comparisons on there datasets: Cora, Citeseer, and Pubmed. It would be more convincing to present its performance on a more diverse range of datasets.  Note the results on Citeseer is inferior to existing method. It is helpful to clearly explain why  this could be the case.\n\nPost rebuttal edition: After reading the reviews and the authors' reply, several questions such as the major concerns over this oversimplified linear assumptions surface out, as discussed in length by other reviewers. Meanwhile, I still believe there are useful merits of this paper. Thus I adjust my current rating to weak accept.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the “suspended animation limit” of various graph neural networks (GNNs) and provides some theoretical analysis to explain its cause. To overcome the limitation, the authors propose Graph Residual Network (GRESNET) framework to involve nodes’ raw features or intermediate representations throughout the graph for all the model layers. The main concern of the reviewers is: the assumption made for theoretical analysis that the fully connected layer is identical mapping is too stringent. The paper does not gather sufficient support from the reviewers to merit acceptance, even after author response and reviewer discussion.  I thus recommend reject.
Decision: Reject