Venue: ICLR 2020 Conference

Reviews:

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

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

Comments:

1) 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?

2) 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? 

3) 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?
review_title: Official Blind Review #1

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

Overall, 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.

However, 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.
review_title: Official Blind Review #2

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

Strength:
1. 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.
2. 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.
3. 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.

Weakness:
1. The analysis is mostly for dense graphs. However, most of the real-world networks are large-scale sparse networks.
2. 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.

review_title: Official Blind Review #3

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)