Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: The article "PairNorm: Tackling Oversmoothing in GNNs" considers the interesting phenomenon of performance degradation of graph neural network when the depth of the network increases beyond the values of 2-4. The authors argue that one of the reasons for such behavior is so-called "oversmoothing", when intermediate representations become similar for all the nodes in the graph. The authors propose the special NN layer "PairNorm", which aims to battle with this issue.

The proposed PairNorm approach boils down to the recentering and normalization of all the representations after each graph-convolutional layer of the network. The authors consider 2 variants of choosing normalization constant:
1. The one which multiplies all the embeddings for the layer by the same number. This operation allows to keep the average squared pairwise distance between node representations constant. 
2. The one which makes the norms of all the representations equal to pre-specified constant, i.e. just projection of all the embeddings on the sphere.

I should note that the two proposed approaches are very different in nature, though the latter one is introduced without much additional discussion. The benefits of approach 1 are not entirely clear as it basically just scales the whole embedding population. Such a scaling doesn't affect the relative distances between points and thus should not have major effect on the performance. Approach 2 is completely different due to the projection on the sphere of each embedding independently. However, the reasons why it is a good idea or not are not discussed in the paper. 

The experimental part of the paper considers several standard graph data sets. The authors report that the proposed normalization schemes do not improve the quality of classification in the standard semi-supervised learning setting. They additionally consider artificially created missing features and observe increasing quality in such a scenario.

To sum up, I think that while the motivation behind the paper is very natural, it doesn't look like the paper finds the solution both theoretically and experimentally.
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: Summary

It is known that GNNs are vulnerable to the oversmoothing problem, in which feature vectors on nodes get closer as we increase the number of (message passing type graph convolution layers). This paper proposed PairNorm, which is a normalization layer for GNNs to tackle this problem. The idea is to pull apart feature vectors on a pair of non-adjacent nodes (based on the interpretation of Laplace-type smoothing by NT and Maehara (2019)). To achieve this approximately with low computational complexity, PairNorm keeps the sum of distances of feature vectors on all node pairs approximately the same throughout layers. The paper conducted empirical studies to evaluate the effectiveness of the method. PairNorm improved the prediction performance and enabled make GNNs deep, especially when feature vectors are missing in the large portion of nodes (the SSNC-MV problem).


Decision

I want to recommend to accept the paper because, in my opinion, this paper contributes to deepening our understanding of graph NNs by giving new insights into what causes the oversmoothing problem and which types problem (deep) graph NNs can solve.
The common myth about graph NNs is that they cannot make themselves deep due to the oversmoothing. Therefore, oversmoothing is one of the big problems in the graph NN field and has been paid attention from both theoretical and empirical sides. This paper found that the deep structures do help to improve (or at least worsen) the predictive performance when the significant portion of nodes in a graph does not have input signals. To the best of our knowledge, this is the first paper that showed the effectiveness of deep structures in citation network datasets (Deep GCNs [Li et al., 2019] successfully improved the prediction performance of (residual) graph NNs using as many as 56 layers for point cloud datasets). The proposed method is theoretically backboned, easy to implement, and applicable to (theoretically) any graph NNs. Taking these things into account, I would like to judge the contribution of this paper is sufficiently significant to accept.


Minor Comments

	- Table 3. Remove s in the entry for GAT-t2 Citeseer 0%.


Questions

	- Can we interpret PairNorm (or the optimization problem (6)) from the viewpoint of graph spectra?
	- Although the motivation of Centering (10) is to ease the computation of TPD, I am curious how this operation contributes to performance. Since the constant signal does not have information for distinguishing nodes, eliminating it by Centering might result in emphasizing the signal component for nodes classification tasks. From a spectral point of view, Centering corresponds to eliminating the lowest frequency of a signal.
	- Figures 3 and 7 have shown that GCN and GAT did not perform well compared to SGC when the layer size increases. The authors discussed that this is because GCN and GAT are easier to overfit. However, SGC chose the hyperparameter $s$ from $\{0.1,1,10,50,100\}$, whereas the authors examined a single $s$ for GCN and GAT. Therefore, I think there is another hypothesis that simply the choice $s$ was misspecified. If this is the case, I am interested in the effect of $s$ on predictive performance.

[Li et al., 2018] Li, Qimai, Zhichao Han, and Xiao-Ming Wu. "Deeper insights into graph convolutional networks for semi-supervised learning." Thirty-Second AAAI Conference on Artificial Intelligence. 2018.
review_title: Official Blind Review #2

Meta-review: The paper proposes a way to tackle oversmoothing in Graph Neural Networks. The authors do a good job of motivating their approach, which is straightforward and works well. The paper is well written and the experiments are informative and well carried out. Therefore, I recommend acceptance. Please make suree thee final version reflects the discussion during the rebuttal.
Decision: Accept (Poster)