The performance of graph neural nets (GNNs) is known to gradually decrease with increasing number of layers. This decay is partly attributed to oversmoothing, where repeated graph convolutions eventually make node embeddings indistinguishable. We take a closer look at two different interpretations, aiming to quantify oversmoothing. Our main contribution is PAIRNORM, a novel normalization layer that is based on a careful analysis of the graph convolution operator, which prevents all node embeddings from becoming too similar. What is more, PAIRNORM is fast, easy to implement without any change to network architecture nor any additional parameters, and is broadly applicable to any GNN. Experiments on real-world graphs demonstrate that PAIRNORM makes deeper GCN, GAT, and SGC models more robust against oversmoothing, and significantly boosts performance for a new problem setting that benefits from deeper GNNs.
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.