PairNorm: Tackling Oversmoothing in GNNs
Authors: Lingxiao Zhao
Leman Akoglu
Venue:  (2020)
Keywords: Graph Neural Network
oversmoothing
normalization

Abstract: 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. Code is available at https://github.com/LingxiaoShawn/PairNorm.

Published as a conference paper at ICLR 2020
PAIRNORM: TACKLING OVERSMOOTHING IN GNNS
Lingxiao Zhao
Leman Akoglu
Carnegie Mellon University Pittsburgh, PA 15213, USA
Carnegie Mellon University Pittsburgh, PA 15213, USA
{lingxial] anddew.. Sandrew. cmu. edu
[lakoglu]@andrew cmu, edu
ABSTRACT
The performance of graph neural nets (GNNs) is known to gradually decrease with increasing number of layers. This decay partly attributed oversmooth- ing, where repeated graph convolutions eventually make node embeddings indis- tinguishable. We take closer look two different interpretations, aiming quantify oversmoothing. Our main contribution is PAIRNORM, a novel normal- ization layer that based on 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 per- formance for a new problem setting that benefits from deeper GNNs. Code is available at htttts /tttttp::/githhb... wwt.c/mm//.iaa. ngxi aowaaaa/aaaaaaaarrrr..oo
INTRODUCTION
Graph neural networks (GNNs) is a family of neural networks that can learn from graph structured data. Starting with the success of GCN (Kipf & Welling 2017) on achieving state-of-the-an per- formance on sunisuupereieed classification, several variants of GNNs have been developed for this task; including GraphSAGE (Hamilton al. 2017). GAT (Velickovic et al. 2018), SGC (Wu al.) 2019), and GMNN (Qu et al. (019) to name few most recent ones.
key issue with GNNs their depth limitations. has been observed that deeply stacking the layers often results in significant drops in performance for GNNs, such as GCN and GAT, even beyond just few (2-4) layers. This drop is associated with a number of factors; including the vanishing gradients in back-propagation, overfitting due to the increasing number of parameters, as well as the phenomenon called oversmoothing. Li et al. (2018) was the first to call attention to the oversmoothing problem. Having shown that the graph convolution is type of Laplacian smoothing, they proved that after repeatedly applying Laplacian smoothing many times, the features of the nodes in the (connected) graph would converge similar values-the issue coined "oversmoothing" In effect, oversmoothing hurts classification performance by causing the node representations to be indistinguishable across different classes. Later, several others have alluded the same problem (Xu et al. 2018: Klicpera et al. 2019 Rong et al.) 2019 Li ei al. 2019) (See $5 Related Work).
In this work, we address the oversmoothing problem in deep GNNs. Specifically, we propose (to the best of our knowledge) the first normalization layer GNNs that is applied in between intermediate layers during training. Our normalization has the effect of preventing the output features of distant nodes to be too similar or indistinguishable, while at the same time allowing those of connected nodes in the same cluster become more similar. We summarize our main contributions as follows.
We introduce normalization scheme, called PAIRNORM, that makes GNNs significantly more robust to oversmoothing and as a result enables the training of deeper models without sacrificing performance. Our proposed scheme capitalizes on the understanding that most GNNs perform a special form of Laplacian smoothing, which makes node features more similar to another. The key idea is to ensure that the total pairwise feature distances remains a constant across layers, which in turn leads to distant pairs having less similar features, preventing feature mixing across clusters.
Normalization to Tackle Oversmoothing in GNNs:

---

Published as a conference paper at ICLR 2020
PAIRNORM is very straightforward to implement and introduces additional parameters. is simply applied to the output features each layer (except the last one) consisting of simple operations, in particular centering and scaling, that are linear in the input size. Being a simple normalization step between layers, PAIRNORM is not specific to any particular GNN but rather applies broadly.
Speed and Generality:
Use Case for Deeper GNNs: While PAIRNORM prevents performance from dropping signif- icantly with increasing number of layers, it does not necessarily yield increased performance in absolute terms. We find that this is because shallow architectures with no more than 2-4 layers is sufficient for the often-used benchmark datasets in the literature. In response, we motivate a real-world scenario wherein notable portion of the nodes have feature vectors. In such set- tings, nodes benefit from a larger range (i.e., neighborhood, hence a deeper GNN) to "recover" effective feature representations. Through extensive experiments, we show that GNNs employing our PAIRNORM significantly outperform the 'vanilla' GNNs when deeper models are beneficial to the classification task.
2 UNDERSTANDING OVERSMOOTHING
In this work, we consider the semi remi-supervised node classification (SSNC) problem on graph. In the general setting, a graph g = (V, [V,E, X) is given in which each node i E V is associated with a feature vector x; R where X Xi..... x,,"' denotes the feature matrix, and a subset V c V of the nodes are labeled, i.e. E [1.....c) cf for each E Vi where is the number of classes. Let A R be the adjacency matrix and D diag degg, .... deg.) E Rnxx be the degree matrix of G. Let À A + and D D + I denote the augmented adjacency and degree matrices with added self-loops on all nodes, respectively. Let A.ym = 11/2 AD-1/2 and A,w = --1 Á denote symmetrically and nonsymmetrically normalized adjacency matrices with self-loops.
The task is to learn a hypothesis that predicts y/ from x; that generalizes to the unlabeled nodes V. V. In Section 3.2] we introduce a variant of this setting where only subset J. C V of the nodes have feature vectors and the rest are missing.
2.1 THE OVERSMOOTHING PROBLEM
Although GNNs like GCN and GAT achieve tftte-of-thh-are results in variety of graph-based tasks, these models are not very well-understood, especially why they work for the SSNC problem where only a small amount of training data is available. The success appears to be limited to shallow GNNs, where the performance gradually decreases with the increasing number of layers. This decrease is often attributed to three contributing factors: (1) overfitting due to increasing number of parameters, (2) difficulty of training due to vanishing gradients, and (3) oversmoothing due to many graph convolutions.
Among these, perhaps the least understood one oversmoothing, which indeed lacks formal definition. their analysis of GCN's s working mechanism, Li et al. (2018) showed that the graph convolution of GCN is special form of Laplacian smoothing. The standard form being (I->1)X+ A the graph convolution lets 7 1 and uses the symmetrically normalized Laplacian to obtain X A, where the new features x of a node is the weighted average of its own and its neighbors' features. This smoothing allows the node representations within the same cluster become more similar, and in turn helps improve SSNC performance under the cluster assumption (Chapelle) et al. 2006). However when GCN goes deep. the performance can suffer from oversmoothing where node representations from different clusters become mixed up. Let us refer to this issue of node representations becoming too similar node-wise oversmoothing.
Another way of thinking about oversmoothing is as follows. Repeatedly applying Laplacian smooth- ing too many times would drive node features stationary point, washing away all the information from these features. Let x, E IR" denote the j-th column of X. Then, for any x. E R"
lim A symx F and Ao
(1)
where the normalized solution л E R" satisfies π. independent of the values x., of the input feature and only a function of the graph structure (i.e..
Σ. vdegi for all i E [n]. Notice that л is
degs
2

---

Published as a conference paper at ICLR 2020
degree). In other words, (Laplacian) oversmoothing washes away the signal from all the features, making them indistinguishable. We will refer to this viewpoint as feature-wise oversmoothing.
To this end propose two measures, row-diff and col-diff, to quantify these two types of over- smoothing. Let H(k) E Rexd be the representation matrix after k graph convolutions, i.e. ((k) A Let h,") R& be the i-th row of ( and h! 12" be the i-th column of H(), Then we define row-dif((H(A)) and col-dif((H as follows.
row-diff(H
Σ
h (k)
h/4 12
(
col-dif((H()) = dP
Σ (.jEdd]
h 19
The row-diff measure is the average of all pairwise distances between the node features (i.e., rows of the representation matrix) and quantifies wise oversmoothing. whereas col-diff is the average of pairwise distances between (41-normalizedd columns of the representation matrix and quantifies feature-wizd wise oversmoothing.
2.2 STUDYING OVERSMOOTIINGG WITH SGC
Although oversmoothing can be a cause of performance drop with increasing number of layers in GCN, adding more layers also leads to more parameters (due to learned linear projections ( at each layer k) which magnify the potential of overfitting. Furthermore, deeper models also make the training harder as backpropagation suffers from vanishing gradients.
In order to decouple the effect of oversmoothing from these other two factors, we study the over- smoothing problem using the SGC model (Wu et al., (201)). (Results on other GNNs are presented 4 SGC is simplified from GCN by removing all projection parameters graph convolution layers and all nonlinear activations between layers. The estimation of SGC is simply written as:
Y =
softmax A sym
W)
(4)
where K is the number of graph convolutions, and W E Rdxe denote the learnable parameters of logistic regression classifier.
Note that SGC has fixed number of parameters that does not depend on the number of graph convolutions (i.e. layers). In effect, it is guarded against the influence of overfitting and vanishing gradient problem with more layers. This leaves only with oversmoothing performance degradation with increasing K. Interestingly, the simplicity of SGC does not seem to be sacrifice; has been observed that it achieves similar or better accuracy various relational classification tasks (Wu et al. 2019)
possible cause of
PairNorm
Original
1.0
row. drf
0.4
coldff
1.0
Accurass 0.6
0.8
Desance
0.1
40
Layers
Layers
Layers
Layers
Figure 1: (best color) SGC's performance (dashed lines) with increasing graph convolutions (K) on Cora dataset (train/val/test split is 3%/10%/87%%. For each K, we train SGC in 500 epochs, save the model with the best validation accuracy, and report all measures based on the saved model. Measures row-diff and col-diff are computed based on the final layer representation of the saved model. (Solid lines depict after applying our method PAIRNORM, which we discuss in (3.2
Dashed lines in Figure T illustratee the performance of SGC on the Cora dataset as we increase the number of layers (K). The training (cross-entropy) loss monotonically increases with larger K, potentially because graph convolution mixes node representations with their neighbors' and makes them less distinguishable (training becomes harder). On the other hand, graph convolutions (i.e., smoothing) improve generalization ability, reducing the gap between training and validation/test loss
We normalize each column as the Laplacian smoothing stationary point π. is not scale-free. See Eq.
3

---

Published as a conference paper at ICLR 2020
up to K 4, after which (over)smoothing begins hurt performance. The row-diff and col-diff both continue decreasing monotonically with K, providing supporting evidence for oversmoothing.
TACKLING OVERSMOOTHING
3.1 PROPOSED PAIRNORM
We start by establishing connection between graph convolution and optimization problem, that is graph-regularized least squares (GRLS), as shown by NT & Maehara (2019). Let X E Raxd be a new node representation matrix, with x; E IRd depicting the i-th row of X. Then the GRLS problem is given as
min Σ - EEV
Σ (D,))EE
where 1/ 2 D2, The first term can be seen as total degree-weightee least squares. The second is graph-regularization term that measures the variation of the features over the graph structure. The goal of the optimization problem can be stated as estimating new "denoised" features x, 's that are not too far off of the input features and smooth over the graph structure.
The GRLS problem has a closed form solution X (2I ) for which A X is the first- order Taylor approximation, that is A X. By exchanging Ar with Asym obtain the same form as the graph convolution, i.e., X Asm X R X. As such, graph convolution can be viewed as approximate solution of 5 where it minimizes the variation over the graph structure while keeping the new representations close to the original.
The optimization problem in (5) facilitates closer look to the oversmoothing problem of graph convolution. Ideally, we want to obtain smoothing over nodes within the same cluster, however avoid smoothing over nodes from different clusters. The objective in (5) dictates only the first goal via the graph-regularization term. It is thus prone to oversmoothing when convolutions are applied repeatedly. To eircumvent the issue and fulfill both goals simultaneously, we can add negative term such as the sum of distances between disconnected pairs as follows.
min X
| - x + (i,))E
1,1
Σ - (K))EE
LEV
where balancing scalar to account for different volume and importance of the two goals By deriving the closed-form solution of (6) and approximating it with first-order Taylor expansion, one can get revised graph convolution operator with hyperparameter A. In this paper, we take a different route. Instead of completely new graph convolution operator, we propose general and efficient "patch", called PAIRNORM, that can be applied to any form of graph convolution having the potential of oversmoothing.
Let X (the output graph convolution) and x respectively be the input and output of PAIRNORM. Observing that the output of graph convolution X Ayy only achieves the first goal, PAIRNORM serves as normalization layer that works on to achieve the second goal of keeping disconnected pair representations farther off. Specifically, PAIRNORM normalizes X such that the total pairwise squared distance TPSD(X) = Eijje(n) ||
x111 is the same as TPSD(X). That is,
Σ (K,))
|
Σ ||* - x
Σ |xx-x;/l
Σ (K.))
||x: - X x
GJ)4E
(UJ)EE
By keeping the total pairwise squared distance unchanged, the term E || - x guar-
anteed to be at least as large as the original value E(SrEe ||x; - x,11 since the other term
Eanes ||*; x113 = Eviyes || 11, is shrunk through the graph convolution.
In practice, instead of always tracking the original value (XSD(X), we can maintain a constant TPSD value C' across all layers, where C' is hyperparameter that could be tuned per dataset.
To normalize X to constant TPSD, need to first compute TPSD Directly computing TPSD involves n² pairwise distances that is O(n2d), which can be time consuming for large datasets.
Thhre exist other variants of ( that achieve similar goals, and leave the space for future exploration.
4

---

Published as a conference paper at ICLR 2020
Equivalently, normalization can be done via two-step approach where TPSD is rewritten as
TPSD(X)
Σ x,112 = 2n²
| - - x
(8)
The first term (ignoring the scale 2n²) in Eq. ( represents the mean squared length of node representations, and the second term depicts the squared length of the mean of node represen- tations. To simplify the computation of (8). we subtract the row-wise mean from each X, i.e., x; = x; Ex & where x denotes the centered representation. Note that this shifting does not affect the TPSD, and furthermore drives the term | Σ x;112 to zero, where computing TPSD(X) boils down to calculating the squared Frobenius norm of X and overall takes O(nd). That is,
TPSD(X) = TPSD(X | ||
(9)
In summary, our proposed PAIRNORM (with input X and output X) can be written as a two-step, center-and-scale, normalization procedure:
x = X;
x;
(Center)
(10)
1=1
x
x
syn.
(Scale)
(11)
VIXX=117
After scaling the data remains centered, that is, that determines C. Specifically,
x = 0. Eq.
is a hyperparameter
TPSD(X) = 2m 2n| |X
2n Σ ||S
x
112 = 2n
{ 11
2n
Σ
(12)
Then, X PAIRNORM(X has row-wise mean 0 (i.e., is centered) and constant total pairwise
squared distance 2n²s² An illustration of PAIRNORM is given in Figure 2 PAIRNORM is input the next convolution layer.
The output of
PairNorm
X
x
graph conv
center
rescale
Figure 2: Illustration of PAIRNORM, comprising centering and rescaling steps.
We also derive a variant of PAIRNORM by replacing Σm= | in Eq. 11 with n| such that the scaling x
0.8
0.0
step computes x; We call it PAIRNORM-SI (for Scale individually), which imposes more re- striction node representations, such that all have the same Lg-norm In practice we found that both PAIRNORM and PAIRNORM-SI work well for SGC, whereas PAIRNORM-SI provides better and more stable results for GCN and GAT. The reason why GCN and GAT' require stricter normalization may because they have more parameters and are more prone to overfitting. In Appx. A.6 we provide additional measures to demonstrate why PAIRNORM and PAIRNORM-SI work. In all experiments, we employ PAIRNORM for SGC and PAIRNORM-SI for both GCN and GAT.
0.4
0.4
0.0
20
0.0
Layer
Layer
Figure 3: (best in color) Performance comparison of the original (dashed) vs. PAIRNORM-enhandee (solid) GCN and GAT models with increasing layers on Cora.
PAIRNORM is effective and efficient solving the oversmoothing problem of GNNs. As a general normalization layer, it can be used for any GNN. Solid lines in Figure I present the performance
See Appendix A.1 for the detailed derivation.
5

---

Published as a conference paper at ICLR 2020
of SGC on Cora with increasing number of layers, where we employ PAIRNORM after each graph convolution layer, as compared to 'vamilla' versions. Similarly, Figure is for GCN and GAT (PaiRNoRM is applied after the activation of each graph convolution). Note that the performance decay with PAIRNORM-at-Work is much slower. (See Fig. 6 in Appx. A.3 for other datasets.)
While PAIRNORM enables deeper models that more robust to oversmoothing, it may that the overall test accuracy does not improve. In fact, the benchmark graph datasets often used in the literature require no more than 4 layers, after which performance decays (even if slowly). In the next section, we present a realistic use case setting for which deeper models are more likely to provide higher performance, where the benefit of PAIRNORM becomes apparent.
odd
3.2 A CASE WHERE DEEPER GNNS ARE BENEFICIAL
In general, oversmoothing gets increasingly more severe as the number of layers goes up. A task would benefit from employing PAIRNORM more if it required a large number of layers to achieve its best performance. To this effect we study the "missing feature setting", where a subset of the nodes lack feature vectors. Let .M- S Va be the set where Vm E _,,x,, Xm = 0, i.e., all of their features are missing. We denote with p = [M/[[uu the missing fraction. We call this variant of the task as semi-supervised node classification with missing vectors (SSNC-MV). Intuitively, one would require a larger number of propagation steps (hence, a deeper GNN) to be able to "recover" effective feature representations for these nodes.
SSNC-MV is general and realistic problem that finds several applications in the real world. For example, the credit lending problem of identifying low- vs. high-risk customers (nodes) can be modeled as SSNC-MV where a large fraction of nodes do not exhibit any meaningful features (e.g., due to low-volume activity). In fact, many graph-based based classification tasks with the cold-start issue (entity with no history) can be cast into SSNC-MV. To our knowledge, this is the first work to study the SSNC-MV problem using GNN models.
Figure Figure&presenti presents the performance of SGC, GCN, and GAT models on Cora with increasing number of layers, where remove feature vectors from all the unlabeled nodes, i.e. p The models with PAIRNORM achieve a higher test accuracy compared to those without, which they typically reach a larger number of layers. (See Fig. Appx. A.4 for results on other datasets.)
cora-5GC
cora-GCN
cora-GAT
1.0
1.0
PalntNrm(55) Original
1.0
train
val_acc
0.8
Accuracy
0.8
test
Accuracy
Accuracy
0.6
0.6
0.6
0.4
0.4
0.4
0.0
0.0
0.0
20 40
20
20
30
Layer
Layer
Layer
Figure 4: (best in color) Comparison of 'vanilla' vs. PAIRNORM-enhanced SGC, GCN, and GAT performance on Cora for p = 1. Green diamond symbols depict the layer at which validation accuracy peaks. PAIRNORM boosts overall performance by enabling more robust deep GNNs.
EXPERIMENTS
In section 3 we have shown the robustness of PAIRNoRM-enhanced models against increasing num- ber of layers in SSNC problem. In this section we design extensive experiments to evaluate the effectiveness of PAIRNORM under the SSNC-MV setting, over SGC, GCN and GAT models.
4.1 EXPERIMENT SETUP
Datasets. We use 4 well-known benchmark datasets in GNN domain: Cora, Ci Citeseer Pubmed (Sen et al. 2008), and CoauthorCS (Shchur et al.] 2018). Their statistics are reported in Appx. A.2 For Cora, Citeseer and Pubmed, we use the same dataset splits as Kipf & Welling (2017). where all nodes outside train and validation are used as test set. For CoauthorCs, we randomly split all nodes into train/val/test as 3%/ 10% /877, and keep the same split for all experiments.
Models. We use three different GNN models our base model: SGC (Wu et al. 2019). GCN (Kipf & Welling 2017). and GAT (Velickovic et al. 2018). We compare our PAIRNORM with residual connection method (He al. 2016) over base models (except SGC since there is no "resid-

---

Published as a conference paper at ICLR 2020
ual connected" SGC), as surprisingly find it can slow down oversmoothing and benefit SSNC- MV problem. Similar to us, residual connection is a general technique that can be applied to any model without changing its architecture. We focus on the comparison between the base models and PAIRNNRM-enhanneed models, rather than achieving the state of the art performance for SSNC and SSNC-MV. There exist few other work addressing oversmoothing (Klicpera et al. 2019: Li iet al. 2018; Rong et al.) 2019; Xu et al. (018)) however they design specialized architectures and not simple "patch" procedures like PAIRNORM that can be applied on top of any GNN. Hyperparameters. We choose the hyperparameter of PAIRNORM from {0.1, 1, 10, 50, 100) over validation set for SGC, while keeping it fixed at s = 1 for both GCN and GAT due to resource limitations. We set the #hidden units of GCN and GAT (#attention heads is set to 1) to 32 and 64 respectively for all datasets. Dropout with rate 0.6 and L-2 regularization with penalty 5 10-1 are applied to GCN and GAT. For SGC, we vary number of layers in {1,2.-.. 10, 15, 60) and for GCN and GAT in {2, .2.4..... 12, 15, 20,.................. 20,.....0...
Configurations. For PAIRNORM-enhanced models, we apply PAIRNORM after each graph convo- lution layer (i.e., after activation if any) in the base model. For residual-connecter models with t skip steps, we connect the output of 1-th layer to (1 + t)-th, that is, H H(++) + H where ( denotes the output of 1-th graph convolution (after activation). For the SSNC-MV setting, we randomly erase p fraction of the feature vectors from nodes in validation and test sets (for which we input vector E R24,, whereas all training (labeled) nodes keep their original features (See We run each experiment within 1000 epochs 5 times and report the average performance. We mainly use a single CTTX-18800 GPU, with some SGC experiments ran on an Intel i7-8700k CPU.
4.2 EXPERIMENT RESULTS
We first show the global performance gain of applying PAIRNORM to SGC for SSNC-MV under varying feature missing rates as shown in Table [ PAIRNoRM-enhanced SGC performs similar or better over 0% missing, while significantly outperforms vanilla SGC for most other settings, especially for larger missing rates. #L denotes the best number of layers for the model that yields the largest average validation accuracy (over runs), for which we report the average test accuracy (Ace). Notice the larger #L values for SGC-PN compared to vanilla SGC, which shows the power of PAIRNORM for enabling "deep" SGC models by effectively tackling oversmoothing.
Similar to Wu et al. (2019) who showed that the simple SGC model achieves comparable or better performance as other GNNs for various tasks, we found PAIRNoRM-enhanced SGC to follow the GCN and GAT, for all SSNC-MV settings. Due to its simplicity and extreme efficiency, we believe PAIRNNRRM-enhanced SGC sets strong baseline for the SS problem.
same trend when compared with PAIRNORM-enhanee
Table 1: Comparison of 'vanilla' vs. PAIRNoRM-enhancee SGC performance in Cora, Citeseer, Pubmed, and CoauthorCs for SSNC-MV problem, with missing rate ranging from 0% to 100%. layers, at which model achieves best validation accuracy.
Showing test accuracy at #L (K in Eq.
Missing Percentage
0%
20%
40%
60%
80%
100%
Dataset
Method
Acc #L.
Acc #L
Acc #L
Acc
#L
Acc
#L
Acc #L
SGC
0,815
4
0.806
5 0.786
3 0.742
4 0.733
3
00.43 15
Cora
SGC-PN
0.811
7 0.799
7 0.797
7 0.783
20
0.780
25
0.745
40
SGC
0.689
10 0,684
6 0.668
8 0.657
9 0.565
8 0,290
2 50
Ci teseer
SGC-PN
0.706
3 0.695
3 0.653
4 0.641
5 0.590
50
0.486
SGC 0.754
0.748
1 0.723
4 0.746
2 0.659
3 0.399
35
Pubmed
SGC-PN
0.782
0.781
7 0.778
60
0.782
7 0.772
60
0.719
40
SGC 0.914
0.898
2 0.877
2
0.824
2 0.751
4
0..18
2
CoauthorCs
SGC-PN 0.915
0.909
0.899
0.891
4 0.880
8
0.860
20
We next employ PAIRNORM-SI for GCN and GAT under the same setting, comparing it with the residual (skip) connections technique. Results are shown in Table 2 and Table 33 respectively for GCN and GAT. Due to space and resource limitations, we only show results for 0% and 100% miss- ing rate scenarios. (We provide results for other missing rates (70, 80, 90%) over run only in Appx. A.5) We observe similar trend for GCN and GAT: (1) vanilla model suffers from performance drop under SSNC-MV with increasing missing rate; (2) both residual connections and PAIRNORM- SI enable deeper models and improve performance (note the larger #I. and Acc); (3) GCN-PN and
7

---

Published as a conference paper at ICLR 2020
GAT-PN achieve performance that is comparable better than just using skips: (4) performance can be further improved (albeit slightly) by using skips along with PAIRNORM-S SI
Table 2: Comparison of 'vanilla' and (PAIRNORM-S// residual)-enhanced GCN performance on
Cora, Citeseer, Pubmed, and CoauthorCS for SSNC-MV problem, with 0% and 100% feature missing rate. represents the skip-step of residual connection. (See A.5 Fig. 8 for more settings.)
Dataset
Cora
Citeseer
Pubmed
CoauthorCS
Missing(%)
0%
100%
0%
100%
0%
100%
0%
100%
Method
Acc #L
Acc
#L
Acc
#L
Acc
#L
Acc
#L
Acc #L
Acc #L
Acc
#L
GCN
0.821
0.582
0.695
2
0.779
204.4
2
00.87
2|0.452
4
GCN-PN
0.790
0.731
10 0.660
0.498
0.780
0.745
0.910
0.846
GCN-1
0.822
0.721
15 0.696
2
0..41
12
0.780
2
0.656
25
0.898
2 0.727
12
PN
0,780
2 0.724
30 0,648
2
0.465
10
0.756
15
0,690
12
0.898
2 0.830
20
GCN-12
0,820
0.722
10 0.691
0.432
20
0.779
2
0.645
20
0.882
4 0.630
20
GCN-12-P PN
0.785
0.740
0.650
0.508
12
0.770
0.725
0.911
2 0.839
Table 3:
Comparison of 'vanilla' and (PAIRNORM-SI/ residual)-enhanced GAT performance on Cora, Citeseer, Pubmed, and CoauthorCs for SSNC-MV problem, with 0% and 100% feature missing rate. represents the skip-step of residual connection. (See Fig. for more settings.)
Dataset
Cora
citesser
Pubmed
CoauthorCS
Missing(%)
0%
100%
0%
100%
0%
100%
0%
100%
Method
Acc #I
Acc
#1.
Acc
#L
Acc
#L
Acc
#1.
Acc
#1.
Acc
#1
Acc
#I.
GAT
0.823
2
0.653
4|
0.693
2
20..428
4 0.774
6
0.631
4
410.82
4
0.737
4
GAT-PN
0.787
0.718
6
0.670
2 0..83
4 0.774
12 0.714
10 0.916
2 0.843
GAT-N1
0.822
2
0.706
8
0.693
2 0.461
6 0.769
4
0.698
8 0.899
4 0.842
10
GAT-UIPN
0.787
0.710
10
0.658
6 0.500
10
0.757
4
0.684
12
0.911
2 0.844
20
GAT-12
0.820
0.691
s0.692
2 0.461
6 0.774
8
0.702
8 0.895
0.803
GAT-12-PN
0.788
0.738
12
0.672
0.517
10
0.776
15 0.704
12 0.917
0.855
30
5 RELATED WORK
Oversmoothing in GNNs: et (018) was the first to call attention to the oversmoothing prob- lem. Xu et al. (2018) introduced Jumping Knowledge Networks, which employ skip connections for multi-hop message passing and also enable different neighborhood ranges. Klicpera et al. (2019) proposed a propagation scheme based on personalized Pagerank that ensures locality (via teleports) which in turn prevents oversmoothing. Li et al. (2019) built on ideas from ResNet to use residual as well as dense connections to train deep GCNs. DropEdge Rong et al. (2019) proposed to alleviate oversmoothing through message passing reduction via removing certain fraction of edges at ran- dom from the input graph. These are all specialized solutions that introduce additional parameters and/or different network architecture.
Normalization Schemes for Deep-NNs: There exist various normalization schemes proposed for deep neural networks, including batch normalization loffe & Szegedy (2015), weight normalization Salimans & Kingma (2016), layer normalization Ba et al. (2016), and so on. Conceptually these have substantially different goals (e.g., reducing training time), and were not proposed for graph neural networks nor the oversmoothing problem therein. Important difference note is that larger depth regular neural-nets does not translate to more hops of propagation on a graph structure.
CONCLUSION
We investigated the oversmoothing problem in GNNs and proposed PAIRNORM, novel normal- ization layer that boosts the robustness of deep GNNs against oversmoothing. PAIRNORM is fast to compute, requires no change in network architecture nor any extra parameters, and can applied to any GNN. Experiments real-world classification tasks showed the effectiveness of PATR NORM, where it provides performance gains when the task benefits from more layers. Future work will explore other cases of deeper GNNs that could further showcase PAIRNORM'S advantages.
shallow networks ure sufficient and smoothing through only a few (2 4) layers improves generalization ability for the SSNC problem (recall Figure D polid lines). PAIRNORM a small reversing effect scenarios, the performance drop.
slight performance drop PAIRNORM applied rate. setting.
8

---

Published as a conference paper at ICLR 2020
REFERENCES
Jimmy Lei Вa, Jamie Ryan Kiros, and Geoffrey Hinton. abs/1607.0642 2016.
Layer normalization.
CoRR,
Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien. Semi-Supervised Learning. 2006.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pp. 1024-1034, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition, In Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recog- nition, pp. 770-778. IEEE, 2016.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. CoRR, abs/1502.00166, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. International Conference on Learning Representations (ICLR). OpenReview.net, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification graphs. In International Conference Learning Representations (ICLR), 2019.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Can GCNs go as deep as CNNs? CoRR, abs/1904.03751, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper Insights into Graph Convolutional Networks for SemiiSuperviied Learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelli- gence, pp. 3538-3545, 2018.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. CoRR, abss/90550999 005509550, 2019.
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. In International Conference on Machine Learning, pp. 5241-5250, 2019.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. The truly deep graph convolutional networks for node classification. CoRR, abs/1907. 109003, 2019.
Tim Salimans and Durk P Kingma. Weight normalization: simple reparameterization to accelerate training of deep neural networks. In Advances in Neural Information Processing Systems, pp- 901-909, 2016.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls 2018.
of graph neural network evaluation. arXiv preprint
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Li. and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations
(ICLR). OpenReview.net, 2018.
Felix Wu, Amauri H. Souza Jr.. Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation Learning Graphs with Jumping Knowledge Networks. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 5453-5462, 2018

---

Published as a conference paper at ICLR 2020
A
APPENDIX
A.1
DERIVATION OF EQ. 8
TPSD(X)
Σ
|x;; - x,11 = Σ
( - x,)
(13)
{.jE(n)
Σ
(X
-x
(14)
AJE(n)
2n Σ
x x2- 2 Σ x
(15)
iE[n]
= 2n
Σ
| 12 - 7 X
(16)
iE[n]
2n
Σ
| 2 1
(17)
iE/ni
Σ
2n
(18)
1=1
A.2 DATASET STATISTICS
Table 4: Dataset statisties.
Name
#Nodes
#Edges #Features #Classes Label Rate
Cora
2708
5429
1433
7
0.052
Citeseer
3327
4732
3703
6
0,036
Fubmed
19717
44338
500
3
0.003
CoauthorCs
18333
81894
6805
15
0,030
A.3 ADDITIONAL PERFORMANCE PLOTS WITH INCREASING NUMBER OF LAYERS
citeseer (random split: 3%/10%//8%)
PairNorm
Original
3.0
col aIf
Accurny
Dosnnce
0.3
0.5
0.6
0.2
pubmed (random split: 3%%10%%/87%)
PairNorm
Original
1.0
0.8
Dehane
Dedance
0.04
100 5Tf
0.02
Lajers
Layers
Layers
coauthor (random split: 3%/10%/87%)
PairNorm
Original
1.0
0.20
col. cm
3.5
Distarce
75
0.15
3.0
2.5
0.05
0.4
0.00
20
Layers
Layers
Layers
Layers
Figure 5: Comparison of 'vanilla' vs. PAIRNoRM-echanned SGC, corresponding to Figure [ for datasets (from top to bottom) Citeseer, Pubmed, and CoauthorCs. PAIRNORM provides im- proved robustness to performance decay due to oversmoothing with increasing number layers.
10

---

Published as a conference paper at ICLR 2020
citeseer-GCN
citeseer-GAT
1.0
PairNorm(Si) Original
1.0
train vain_acc
val. acc
Accuracy
0.8
Accuracy
0.8
test_ace
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
30
10
20
30
Layer
Layer
pubmed-GGN
pubmed-GAl GAT
1.0
1.0
0.8
0.8
Accuracy
Accuracy
0.6
0.6
0.4
0.4
train ad
0.2
PairNorm(SI)
0.2
val_
Original
test_acc
0.0
0.0
10
20
30
10
20
30
Layer
Layer
coauthor CS-GCN
COa-th CS-GAT
1.0
1.0
0.8
0.8
Accuracy
Accuracy
0.6
PairNorm((1)
0.6
Original
0.4
0.4
train BCC
0.2
0.2
val_acc
test_acc
0.0
0.0
30
20
30
Layer
Layer
Figure 6: Comparison of 'vanilla' (dashed) vs. PAINNORM-enhanced (solid) GCN (left) and GAT (right) models, corresponding to F for datasets (from top to bottom) Citeseez, Pubmed, and coauthorcs. PAIRNORM provides improved robustness against performance decay with increasing number layers.
11

---

Published as a conference paper at ICLR 2020
A.4
ADDITIONAL PERFORMANCE PLOTS WITH INCREASING NUMBER OF LAYERS UNDER
SSNC-MV wITHp=1
citeseer-SGC
citeseer-GCN
citeseer-GAT
1.0
1.0
P5i Original
1.0
train, acc
val,
Accuracy
Accuracy
Accuracy
0.8
test acc
0.6
0.6
0.6
0.4
0.4
0.4
0.0
0.0
0.0
0
20
40
10
20
30
10
20
30
Layer
Layer
Layer
pubmed-5GC
Pubmed-GCN
pubmed-GA GAT
1.0
1.0
1.0
train,
val_ace _cc_acc
0.8
0.8
0.8
Accuracy
Accuracy
Accuracy
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
Pairfoorm(S)
0.2
Original
0.0
0.0
0.0
30
20
30
Layer
Layer
Layer
coauthor C5-5GC
coauthor CaauthorrCc-GGCN
coauthor coauthor_CS-GAT CS-GAT
1.0
1.0
1.0
Accuracy
0.6
Accuracy
0.6
Original
PairNomm/51)
Accuracy
0.6
val, acc
train
0.4
0.4
0.4
test acc
0.2
0.2
0.2-
0.0
0.0
0.0
0
20
40
10
20
30
10
20
30
Layer
Layer
Layer
Comparison of 'vanilla' (dashed) vs. PAIRNoRM-enhanced (solid) (from left to right) SGC, GCN, and GAT model performance under SSNC-MV for p = 1, corresponding to Figure 4 for datasets (from top to bottom) Citeseer, Pubmed, and CoauthorCs. Green diamond symbols depict the layer at which validation accuracy peaks. PAIRNORM boosts overall performance by enabling more robust deep GNNs.
Figure 7:
12

---

Published as a conference paper at ICLR 2020
A.5 ADDITIONAL EXPERIMENTS UNDER SS WITH INCREASING MISSING FRACTION p
In this section we report additional experiment results under the SSNC-MV setting with varying missing fraction, in particular p = {0.7, 0.8, 0.9, 1f and also report the base case where = 0 for comparison.
Figure [ presents results on all four datasets for GCN vs. PAIRNORM- GCN (denoted PN for short). The models without any skip connections denoted by +-0, with one-hop skip connection by *-1, and with one and two-hop skip connections by *-2. Barcharts on the right report the best layer that each model produced the highest validation accuracy, and those on the left report the corresponding test accuracy. Figure 9
presents corresponding results for GAT.
We discuss the take-aways from these figures on the following page.
cora GCN
Test Acc
Best Layer
0.8
10
220222 grgars G2gag2 220202 bbPtts abputs
Sroate Deogis Deoaes Geocna Gegaes bapeiao abppis baoiig abppint baptia
baPpin abPptt LaVeLaa
100%
masing missing 80%
30%
100% missing
citeseer GCN
Test. Acc
Best Layer
BEppon ebieay bappin & & GEO2Os masing
Degze Gaggn Gaggns & baptiog bappio bapping Soppoo booeisg missing
bavisnos missing missing missing
missing
missing missing
masing missing
pubmed GCN
Test. Acc
Best Layer
0.6
0.4
De EROR bbPPAs 8 abpsls dariin pan apppei
Cegaag oo Laاt missing 70% missing 80% missing 90% missing 100% missing
Segg0s bav Liots Bariso Baogisg OaViis bakpna 0% missin
missing 80% missing 90% misinn 100% missing
coauthor CS GCN
Test. Acc
Best Layer
10
0.4
ogu paggs Sgupen Sguptng Sp-ptaus Sa-cisa 0% missing 70% missing 80% missing 90% masinn 100% missing
0% missin 70% missing 80% missing 90% missing 100% missing
Figure 8: Supplementary results to Table 2 for GCN on (from top to bottom) Cora, Citeseer, Pubmed, and CoauthorCs.
13

---

Published as a conference paper at ICLR 2020
We make the following observations based on Figures
and
Performance of 'vanilla' GCN and GAT models without skip connections (i.c., GCN-O and GAT-0) drop monotonically as we increase missing fraction p.
MAIRNoRM-enhanced 'vanilla' models (PN-O, no skips) perform comparably or better than GCN-0 and GAT-O in all cases, especially as p increases. In other words, with PAIRNORM at work, model performance is more robust against missing data.
Best number of layers for GCN-0 we increase p only changes between 2-4, For GAT-O, it changes mostly between 2-6.
'vanilla' models (PN-0, no skips) can go deeper, i... they can lever- age a larger range of #layers (2-12) as we increase p. Specifically, GCN-PN-O (GAT-PN-O) uses equal number or more layers than GCN-0 (GAT-0) in almost all cases.
PAIRNNRMM-nhancee
Without any normalization, adding skip connections Delps-GCN/GATE and GCN/GAT-2 are better than GCN/GAT-0,, especially as we increase p.
With PAIRNORM but no-skip, performance is comparable or better than just adding skips. Adding skips on top of PAIRNORM does not seem to introduce any notable gains.
In summary, simply employing our PAIRNORM for GCN and GAT provides robustness against oversmoothing that allows them to go deeper and achieve improved performance under SSNC-MV.
cora GAT
Test Acc
Best Layer
10.
PEepER barpee 0% missing
byاiie b boاياe 100%
missing
30% 100%
70% 80%
90%
citeseer GAT
Test Acc
Best Layer
10
0.6
Geepe Deee Boeg sp
bgi bbipinn اiي Lداe bbittio b Lei
0% mesing 70% missing 80% mising 90% missing 100% missing
0% micsing 70% missing 80% missing 90% masing 100% missing
pubmed
Test Acc
Best Layer
0.8
0.6
0.5
S S3g S S3 S
byg ر BaPcP Baر vs Baرياي b borcut 0% missing
missing 70% missing missing 90% missing 100% missing
missing 80% missing 90% missing 100% missing
coauthor CS GAT
Test Acc
Best Layer
0.9
10-
0.7
ماص bainiag missing 70% missing missing missing 100% missing
Boruee ربريتو
baipin Barueg baipin Bainee Bappte mesinng missing missing missing 100% messing
Figure 9: Supplementary results to Table 3 for GAT on (from top to bottom) Cora, Citeseer, Pubmec, and Coruth
14

---

Published as a conference paper at ICLR 2020
A.6
CASE STUDY: ADDITIONAL MEASURES FOR PAIRNORM AND PAIRNORM-SI WITH SGC AND GCN
To better understand why PAIRNORM and PAIRNORM-SI are helpful for training deep GNNs, report additional measures for (SGC and GCN) with (PAIRNORM and PAIRNORM-SD. over the Cora dataset. In the main text, claim TPSD (total pairwise squared distances) is constant across layers for SGC with PAIRNORM (for GCN/GAT this is not guaranteed because of the influence of activation function and dropout layer). In this section we empirically measure pairwise (squared) distances for both SGC and GCN, with PAIRNORM and PAIRNORM-SI.
A.6.1 SGC WITH PAIRNORM AND PAIRNORM-SI
To verify our analysis of PAIRNORM for SGC, and understand how the variant of PAIRNORM (PAIRNORM-SI) works, we measure the average pairwise squared distance (APSD) as well as the average pairwise distance (APD) between the representations for two categories of node pairs: (1) connected pairs (nodes that are directly connected in graph) and (2) random pairs (uniformly ran- domly chosen among the node set). APSD of random pairs reflects the TPSD, and APD of random pairs reflects the total pairwise distance (TPD). Under the homophily assumption of the labels w.r.t the graph structure, want APD APSD of connected pairs to be small while keeping APD or APSD of random pairs relatively large.
The results are shown in Figure 10 Without normalization, SGC suffers from fast diminishing APD and APSD of random pairs. As we have proved, PAIRNORM normalizes APSD to be constant across layers, however it does not normalize APD, which appears to decrease linearly with increasing num- ber of layers. Surprisingly, although PAIRNORM is not theoretically proved to have a constant APSD and APD, empirically it achieves more stable APSD and APD than PAIRNORM. We were not able to prove this phenomenon mathematically, and leave it for further investigation.
Dataset: cora
SGC
PairNomm
PairNorm-SI
Average squared distance
connected pairs
30
30
30
20
20
connected pairs
20
connected pairs
random pairs
random pairs
10
10
20
40
Average distarce
20
40
20
40
Layers
Layers
Layers
Figure 10: Measuring average distance (squared and not-squared) between representations each layer for SGC, SGC with PAIRNORM, and SGC with PAIRNORM-SI. The setting is the same with Figure I and they share the same performance.
APD does not capture the full information of the distribution of pairwise distances. To show how the distribution changes by increasing number of layers, we use Tensorboard plot the histograms of pairwise distances, as shown in Figure [1] Comparing SGC and SGC with PAIRNORM, adding PAIRNORM keeps the left shift (shrinkage) the distribution of random pair distances much slower than without normalization, while still sharing similar behavior of the distribution of connected pairwise distances. PAIRNORM-S. seems to be more powerful in keeping the median and mean of the distribution of random pair distances stable, while "spreading" the distribution out by increasing the variance. The performance of PAIRNORM and PAIRNORM-S are similar, however it seems that PATR SO is more powerful in stabilizing TPD and TPSD.
15

---

Published as a conference paper at ICLR 2020
Dataset: Cora SGC
SGC PairNorm
SGC PairNorm-SI
dietr. of connected pair distances
distr. connecled dislances
distr. of connected distances
15
15
15
25
25
25
35
35
35
45
45
45
0.5
3.5
6.5
distr. of random pair distances
distr random pair distancess
distr of random pai distances
15
Layer
25
25
35
86
45
10
22
Distance
Distance
Distance
Figure 11: Measuring distribution of distances between representations at each layer for SGC, SGC with PAIRNORM, and SGC with PAIRNORM-SI Supplementary results for Figure I0
A.6.2 GCN WITH PAIRNORM AND PATRNORM-ST
Dataset: cora
GCN
GON PairNomm
PairNorm-Sl
Average squared dizance
0.010
connected pairs random pairs
120
0.008
100
0.6
0.006
80
connected
connected
0.004
60
random pairs
random pairs
40
0.002
0.2
20
0.000
10
0.10
10
Average distance
0.08
0.06
0.6
0.04
0.4
0.02
0.00
Layers 100
2
2
10
Layers
Layers
Figure 12: Measuring average distance (squared and not-squared) between representations each layer for GCN, GCN with PAIRNORM, and GCN with PARRNO We trained three 12-layer GCNs with #hidden=128 and dropout=0.6 in 1000 epochs. Respective test set accuracies are 31.09%, 77.77%, 75.09%. Note that the scale of distances is not comparable across models, since they have learnable parameters that scale these distances differently.
The formal analysis for PAIRNORM and PAIRNORM-S SI is based on SGC. GCN (and other GNNs) has learnable parameters, dropout layers, and activation layers, all of which complicate direct math- ematical analyses. Here we perform similar empirical measurements for pairwise distances to get rough sense of how PAIRNORM and PAIRNORM-SI work with GCN based on the Cora dataset. Figures 12 and 13 demonstrate how PAIRNORM and PAIRNORM-S can help train a relatively deep (12 layers) GCN.
Notice that oversmoothing occurs very quickly for GCN without any normalization, where both con- nected and random pair distances reach zero (!). In contrast, GCN with PAIRNORM or PAIRNORM- SI is able to keep random pair distances relatively apart while allowing connected pair distances to shrink. As also stated in main text, using PAIRNORM-SI for GCN and GAT is relatively more
16

---

Published as a conference paper at ICLR 2020
stable than using PAIRNORM in general cases (notice the near-constant random pair distances in the rightmost subfigures). There are several possible explanations for why PAIRNORM-SI is more stable. First, shown in Figure I0 and Figure 12 PAIRNORM-SI not only keeps APSD stable but also APD, further, the plots of distributions of pairwise distances (Figures 11 and 13) also show the power of PAIRNORM-SI (notice the large gap between smaller connected pairwise distances and the larger random pairwise distances). Second, we conjecture that restricting representations to reside on sphere can make training stable and faster, which we also observe empirically by studying the training curves. Third, GCN and GAT tend to overfit easily for the SSNC problem, due to many learnable parameters across layers and limited labeled input data, therefore it is possible that adding more restriction on these models helps reduce overfitting.
Dataset: Cora GCN
GCN PairNorm
GON PairNorm-SI
of connected distances
distr. connacted distancos
of connected pair distances
Layers
0.02
0.10
0.18
10
14
18
0.1
0.3
0.5
0.7
1.1
distr. of random pair distances
distr. random pai distances
distr. of random pair distances
888881
0.02 0.06
0.10
0.14
0.18
0.22
0.28
0.30
15
225
355
45
65
0.3
0.5
0.7
0.9
1.1
Distance
Distance
Distance
Figure 13: Measuring distribution of distances between representations at each layer for GCN, GCN with PATRNORM, and GCN with PAIRNORM-ST. Supplementary results for Figure T2
All in all. these empirical measurements illustrated throughout the figures in this section demon- strates that PAIRNORM and PAIRNORM-SI successfully address the oversmoothing problem for deep GNNs. Our work the first to propose a normalization layer specifically designed for gruph neural networks, which we hope will kick-start more work in this area toward training more robust and effective GNNs.
17


Reviews:
[{"review_id": "rJg-wCfLqr", "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": "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.\n\nThe 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:\n1. 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. \n2. 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.\n\nI 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. \n\nThe 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.\n\nTo 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BkxkcqhTtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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\nIt 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).\n\n\nDecision\n\nI 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.\nThe 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.\n\n\nMinor Comments\n\n\t- Table 3. Remove s in the entry for GAT-t2 Citeseer 0%.\n\n\nQuestions\n\n\t- Can we interpret PairNorm (or the optimization problem (6)) from the viewpoint of graph spectra?\n\t- 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.\n\t- 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.\n\n[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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)