Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 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.

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

review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: Summary:

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

Overall, the motivation of this work is clear and meaninfgful. The proposed residual architecture is effective, and the presentation is clear and easy to understand. 

However, my main concerns are on the initial assumptions for analyzing the suspension of GNNs. See the following comments.

This paper is generally well written and easy to understand. The organization of each part is well-balanced.

Originality:

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

[1] X. Wang and A. Gupta. Videos as Space-Time Region Graphs. ECCV 2018.
[2] N. Wang, Y. Zhang, Z. Li , Y. Fu, W, Liu, Y. Jiang. Pixel2Mesh: Generating 3D Mesh Models from Single RGB Images. ECCV 2018.

Significance:

The significance lies mostly in motivation and the proposed GResNet.

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

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

Main issues: 
My 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.

Minor issues:
1. 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).

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

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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.

Strength
1. The authors identify and study an interesting and important issue in GNN as the “Suspended Animation” issue.
2. 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.
3. The authors carry out extensive experiments on different variants of residual links. Morover, the authors provide code online for reproducibility.

Weakness:
1. 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.
2. 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.
3. 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.
4. 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.
5. 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?

review_title: Official Blind Review #3

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