Towards Deeper Graph Neural Networks

Most popular graph convolution operations follow a neighborhood aggregation (or message passing) fashion to learn a node representation by propagating representations of its neighbors and applying transformation after that. The $\ell$-th layer of a general graph convolution can be described as

$\boldsymbol{x}_{i}^{(\ell)}$ is the representation of node $i$ at $l$-th layer and $\boldsymbol{x}_{i}^{(0)}$ is initialized as node feature $\boldsymbol{x}_{i}$. Most graph convolutions, like GCN (Kipf and Welling, 2017), GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2018), and GIN (Xu et al., 2019), can be obtained under this framework by deploying different propagation and transformation mechanisms.

Without losing generalization, we focus on the Graph Convolutional Network (GCN) (Kipf and Welling, 2017), the most representative graph convolution operation, in the following analysis. The $\ell$-th layer forward-propagation process is formulated as

where $\boldsymbol{X}^{(\ell)}\in\mathbb{R}^{n\times d^{(\ell)}}$ and $\boldsymbol{X}^{(\ell-1)}\in\mathbb{R}^{n\times d^{(\ell-1)}}$ are the output and input node representation matrices of layer $\ell$. $\widehat{\boldsymbol{A}}=\widetilde{\boldsymbol{D}}^{-\frac{1}{2}}\widetilde{\boldsymbol{A}}\widetilde{\boldsymbol{D}}^{-\frac{1}{2}}$, where $\widetilde{\boldsymbol{A}}=\boldsymbol{A}+\boldsymbol{I}$ is the adjacency matrix with added self-connections. $\widetilde{\boldsymbol{D}}_{(i,i)}=\sum_{j}\widetilde{\boldsymbol{A}}_{(i,j)}$ is the diagonal node degree matrix. $\boldsymbol{W}^{(\ell)}\in\mathbb{R}^{d^{(\ell-1)}\times d^{(\ell)}}$ is a layer-specific trainable weight matrix. $\sigma$ is a non-linear activation function like ReLU (Nair and Hinton, 2010). Intuitively, GCN learns representation for each node by propagating neighbors’ representations and conducting non-linear transformation after that. GCN is originally applied for semi-supervised classification, where only partial nodes have training labels in a graph. Thanks to the propagation process, representation of a labeled node carries the information from its neighbors that are usually unlabeled, thus training signals can be propagated to the unlabeled nodes.

From Eq.(2), one layer GCN only considers immediate neighbors, i.e. one-hop neighborhood. Multiple layers should be applied if multi-hop neighborhood is needed. In practice, however, the performance of GCN degrades greatly when multiple layers are stacked. Several works reveal that stacking many layers can bring the over-smoothing issue, which means that representations of nodes converge to indistinguishable limits. To our knowledge,  (Li et al., 2018) is the first attempt to demystify the over-smoothing issue in the GCN model. The authors first demonstrate that the propagation process of the GCN model is a special symmetric form of Laplacian smoothing (Taubin, 1995), which makes the representations of nodes in the same class similar, thus significantly easing the classification task. Then they show that repeatedly stacking many layers may make representations of nodes from different classes indistinguishable. The same problem is studied in (Xu et al., 2018) by analyzing the connection of nodes’ influence distribution and random walk (Lovász et al., 1993). Recently, SGC (Wu et al., 2019) is proposed by reducing unnecessary complexity in GCN. The authors show that SGC corresponds to a low-pass-type filter on the spectral domain, thus deriving smoothing features across a graph. Another recent work (Chen et al., 2020) verify that smoothing is the nature of most typical graph convolutions. It is showed that reasonable smoothing makes graph convolutions work and over-smoothing results in poor performance.

Due to the potential concern of the over-smoothing issue, a limited neighborhood is usually used in practice and it is difficult to extend. However, long-range dependencies should be taken into consideration, especially for peripheral nodes. Also, small receptive fields are not enough to propagate training signals to the whole graph when the number of training nodes is limited under a semi-supervised learning setting.  (Li et al., 2018) applies co-training and self-training to overcome the limitation of shallow architectures. A smoothness regularizer term and adaptive edge optimization are proposed in  (Chen et al., 2020) to relieve the over-smoothing problem. Jumping Knowledge Network (Xu et al., 2018) deploys a layer-aggregation mechanism to adaptively select a node’s sub-graph features at different ranges rather than to capture equally smoothed representations for all nodes.  (Klicpera et al., 2019) utilizes the relationship between GCN and PageRank (Page et al., 1999) to develop a propagation mechanism based on personalize PageRank, which can preserve the node’s local information while gather information from a large neighborhood. Recently, Geom-GCN (Pei et al., 2020) and non-local GNNs (Liu et al., 2020) are proposed to capture long-range dependencies for disassortative graph by designing non-local aggregators.

Smoothness is a metric that reflects the similarity of node representations. Here, we first define a similarity metric between the representations of node $i$ and node $j$ with their Euclidean distance:

where $\boldsymbol{x}_{i}$ is the feature representation of node $i$ and $\lVert\cdot\rVert$ denotes the Euclidean norm. The Euclidean distance is a simple but effective way to measure the similarity of two representations, especially in high dimensional space. Smaller Euclidean distance value incidates higher similarity of two representations. To remove the influence of the magnitude of feature representations, we use normalized node representations to compute their Euclidean distance, thus constraining $D(\boldsymbol{x}_{i},\boldsymbol{x}_{j})$ in the range of $[0,1]$.

Based on the similarity metric in Eq.(3), we further propose a smoothness metric $SMV_{i}$ for node $i$, which is computed as the average distance between node $i$ to other nodes:

Hence, $SMV_{i}$ measures the similarity of node $i$’s representations to the entire graph. For instance, a node in the periphery or a leaf node usually has a large smoothness metric value. Further, we can use $SMV_{G}$ to represent the smoothness metric value of the whole graph $G$. Its mathematical expression is defined as:

Here, $SMV_{G}$ is negatively related to the overall smoothness of nodes’ representations in graph $G$.

In this section, we utilize our proposed smoothness metric to investigate the performance deterioration phenomenon in deep graph neural networks. Here, we mainly use the GCN layer for analysis, but the main results can be easily applied to other graph deep learning methods. Besides using our proposed metric from the quantitative perspective, we employ a data visualization technique t-SNE (Maaten and Hinton, 2008). t-SNE provides an interpretable visualization, especially on high-dimensional data. t-SNE is capable of capturing both the local structure and the global structure like clusters in high-dimensional data, which is consistent with the classification of nodes. Hence, we utilize t-SNE to demonstrate the discriminative power of node representations in the graph.

We develop a series of graph neural networks (GNNs) with different depths in terms of the number of GCN layers, and evaluate them on three citation datasets; those are Cora, CiteSeer and PubMed (Sen et al., 2008). In particular, we also include a graph neural network with depth of 0, which is approximated with a multi-layer perceptron network. A GNN with depth of 0 can be viewed as aggregating information from a 0-hop neighborhood, which only considers node features while with the graph structure ignored. We conduct 100 runs for each model on each dataset, using the same data split scheme as (Kipf and Welling, 2017).

The result on Cora is illustrated in Figure 2. We provide results on other datasets in Section A.1 in the appendix. We can observe that test accuracy increases as the rise of the number of layers in the beginning, but degrades dramatically from 3 layers. Besides, from the t-SNE visualization on Cora in Figure 1 (t-SNE visualization results of other datasets are provided in Appendix A.3.), the discriminative power of the node representations derived by different numbers of GCN layers has the similar trend. The node representations generated by multiple GCN layers, like 6 layers, are very difficult to be separated.

Several studies (Li et al., 2018; Chen et al., 2020) attribute this performance degradation phenomenon to the over-smoothing issue. However, we question this view for the following two reasons. First, we hold that the over-smoothing issue only happens when node representations propagate repeatedly for a large number of iterations, especially for a graph with sparsely connected edges. As shown in Table 1, all these three citation datasets have a small value of edge density, hence several propagation iterations are not enough to make over-smoothing happen, theoretically. Second, as shown in Figure 2, the smoothness metric value of graph node representations has a slight downward trend as the number of propagation iterations increases. According to  (Li et al., 2018), the node representations suffering from the over-smoothing issue will converge to the same value or be proportional to the square root of the node degree, where the corresponding smoothness metric value should be close to $0$, computed by our quantitative metric. However, the metric value in our experiments is relatively far from the ideal over-smoothing situation.

In this work, we argue that it is the entanglement of transformation and propagation that significantly compromise the performance of deep graph neural networks. Our argument is originated from the following two intuitions. First, the entanglement of representation transformation and propagation makes the number of parameters in transformation intertwined with the receptive fields in propagation. As illustrated in Eq.(1), one hop propagation requires a transformation function, thus leading to a large number of parameters when considering a large receptive field. Hence, it might be hard to train a deep GNN with a large number of parameters. This can possibly explain why the performance of multiple GCN layers in Figure 2 fluctuates greatly. Second, representation propagation and transformation should be viewed as two separate operations. Note that the class of a node can be totally predictable by its initial features, which explains why MLP, as shown in Figure 2 and 1, performs well without using any graph structure information. Propagation based on the graph structure can help to ease the classification task by making node representations in the same class to be similar, under the assumption that connected nodes usually belong to the same class. For instance, intuitively, the class of a document is completely determined by its content (i.e. its feature derived by word embedding), instead of the references relationships with other documents. Utilizing its neighbors’ features just eases the classification of documents. Hence, representation transformation and propagation play their distinct roles from feature and structure aspects, respectively.

To support and verify our argument, we decouple the propagation and transformation in Eq.(2), leading to the following model:

$\boldsymbol{Z}\in\mathbb{R}^{n\times c}$ denotes the new feature matrix transformed from the original feature matrix by an MLP network, where $c$ is the number of classes. After the transformation, we apply a $k$-steps propagation to derive the output feature matrix $\boldsymbol{X}_{out}\in\mathbb{R}^{n\times c}$. A softmax classifier is applied to compute the classification probabilities. Notably, the separation of transformation and propagation processes is also adopted in (Klicpera et al., 2019) and  (Wu et al., 2019) but for the sake of reducing complexity. In this work, we analyze this scheme systematically and reveal that it can help to build deeper models without suffering from performance degradation, which has not been prioritized by the community.

The test accuracy and smoothness metric value of representations with different numbers of layers adopted in Eq.(6) on Cora are illustrated in Figure 4 (Results for other datasets are shown in Appendix A.2). After resolving the entanglement of feature transformation and propagation, deeper models is capable of leveraging larger receptive fields without suffering from performance degradation. We can observe that the over-smoothing issue starts compromising the performance at an extremely large receptive field, such as 75-hop on Cora. The smoothness metric value decreases greatly after that, which is demonstrated by the metric value of nearly 0. Besides, from the t-SNE visualization in Figure 3 (The t-SNE visualization results of other datasets are provided in Appendix A.4), deep models with large receptive fields, like 50-hop, still generating distinguishable node representations, which is impressive compared to the regular GCN model. In practice, we usually do not need an extremely large receptive field because the highest shortest path distance in a connected component usually is an acceptable small number. Thus training signals can be propagated to the entire graph with a small number of layers. This is demonstrated by the fact that graph neural networks with 2 or 3 GCN layers usually perform competitively. However, deep models with large receptive fields are necessary to incorporate more information, especially with limited training nodes under a semi-supervised learning setting.

The empirical analysis in the previous section shows that decoupling transformation and propagation can help to build much deeper models which can leverage larger receptive fields to incorporate more information. In this section, we provide a theoretical analysis of the above observation when building very deep graph neural networks, which aligns with the over-smoothing issue. (Li et al., 2018) and  (Xu et al., 2018) study the over-smoothing issue from the perspective of Laplacian smoothing and nodes’ influence distribution, with several simplified assumptions like non-linear transformation and probability approximations. After decoupling transformation from propagation, our theoretical analysis can serve as a more rigorous and gentle description of the over-smoothing issue. In this section, we strictly describe the over-smoothing issue for 2 typical propagation mechanisms.

$\widehat{\boldsymbol{A}}_{\oplus}=\widetilde{\boldsymbol{D}}^{-1}\widetilde{\boldsymbol{A}}$ and $\widehat{\boldsymbol{A}}_{\odot}=\widetilde{\boldsymbol{D}}^{-\frac{1}{2}}\widetilde{\boldsymbol{A}}\widetilde{\boldsymbol{D}}^{-\frac{1}{2}}$, where $\widetilde{\boldsymbol{A}}=\boldsymbol{A}+\boldsymbol{I}$, are two frequently utilized propagation mechanisms. The row-averaging normalization $\widehat{\boldsymbol{A}}_{\oplus}$ is adopted in GraphSAGE (Hamilton et al., 2017) and DGCNN (Zhang et al., 2018). The symmetrical normalization scheme $\widehat{\boldsymbol{A}}_{\odot}$ is applied in GCN (Kipf and Welling, 2017). In the following, we describe the over-smoothing issue by proving the convergence of $\widehat{\boldsymbol{A}}_{\oplus}^{k}$ and $\widehat{\boldsymbol{A}}_{\odot}^{k}$, respectively, when $k$ goes to infinity.

Let $\boldsymbol{e}=[1,1,\cdots,1]\in\mathbb{R}^{1\times n}$ be a row vector whose all entries are $1$. Function $\Psi(\boldsymbol{x})=\frac{\boldsymbol{x}}{{\rm sum}(\boldsymbol{x})}$ normalizes a vector to sum to $1$ and function $\Phi(\boldsymbol{x})=\frac{\boldsymbol{x}}{\lVert\boldsymbol{x}\rVert}$ normalizes a vector such that its magnitude is $1$.

From the above two theorems, we can derive the exact convergence value of $\widehat{\boldsymbol{A}}_{\oplus}^{k}$ and $\widehat{\boldsymbol{A}}_{\odot}^{k}$, respectively, when $k$ goes to infinity in an infinite deep model. Hence, applying infinite layers to propagate information iteratively is equivalent to utilizing $\boldsymbol{\Pi}_{\oplus}$ or $\boldsymbol{\Pi}_{\odot}$ to propagate features by one step. Rows of $\boldsymbol{\Pi}_{\oplus}$ are the same and rows of $\boldsymbol{\Pi}_{\odot}$ are proportional to the square root value of the corresponding nodes’ degrees. Therefore, rows of $\boldsymbol{\Pi}_{\oplus}$ or $\boldsymbol{\Pi}_{\odot}$ are linearly inseparable and utilizing them as propagation mechanism will generate indistinguishable representations, thereby leading to the over-smoothing issue.

To prove these two theorems, we first introduce the following two lemmas. The proofs of these two lemmas can be found in Appendix A.5 and  A.6.

These two theorems hold for connected graphs that are frequently studied in graph neural networks. For a disconnected graph, these theorems can also be applied to each of its connected components, which means that applying these propagation mechanisms infinite times will generate indistinguishable node representations in each connected components.

The above theorems reveal that over-smoothing will make node representations inseparable and provide the exact convergence value of frequently used propagation mechanisms. Theoretically, we have proved that the over-smoothing issue is inevitable in very deep models. Further, the convergence speed is a more important factor that we should consider in practice. Mathematically, according to Eq.(7), the convergence speed depends on the other eigenvalues except $1$ of the propagation matrix, especially the second largest eigenvalue. Intuitively, the propagation matrix is determined by the topology information of the corresponding graph. This might be the reason for our observation in Section 3.2 that a sparsely connected graph suffers from the over-smoothing only when extremely deep models are applied.

We conduct experiments on $7$ datasets based on citation, co-authorship, or co-purchase graphs for semi-supervised node classification tasks; those are Cora (Sen et al., 2008), CiteSeer (Sen et al., 2008), PubMed (Sen et al., 2008), Coauthor CS (Shchur et al., 2018), Coauthor Physics (Shchur et al., 2018), Amazon Computers (Shchur et al., 2018), and Amazon Photo (Shchur et al., 2018). The statistics of these datasets are summarized in Table 1. The detailed description of these datasets are provided in Appendix A.7.

We implemented our proposed DAGNN and some necessary baselines using Pytorch (Paszke et al., 2017) and Pytorch Geometric (Fey and Lenssen, 2019), a library for deep learning on irregularly structured data built upon Pytorch. We consider the following baselines: Logistic Regression (LogReg), Multilayer Perceptron (MLP), Label Propagation (LabelProp) (Chapelle et al., 2009), Normalized Laplacian Label Propagation (LabelProp NL) (Chapelle et al., 2009), ChebNet (Defferrard et al., 2016), Graph Convolutional Network (GCN) (Kipf and Welling, 2017), Graph Attention Network(GAT) (Veličković et al., 2018), Mixture Model Network (MoNet) (Monti et al., 2017), GraphSAGE (Hamilton et al., 2017), APPNP (Klicpera et al., 2019), and SGC (Wu et al., 2019). We aim to provide a rigorous and fair comparison between different models on each dataset by using the same dataset splits and training procedure. We tune hyperparameters for all models individually and some baselines even achieve better results than their original reports. For our DAGNN, we tune the following hyperparameters: (1) k $\in$ {5, 10, 20}, (2) weight decay $\in$ {0, 2e-2, 5e-3, 5e-4, 5e-5}, and (3) dropout rate $\in$ {0.5, 0.8}. Our code is publicly available ¹¹1https://github.com/divelab/DeeperGNN.

The results on citation datasets are summarized in Table  2. To ensure a fair comparison, we use 20 labeled nodes per class as the training set, 500 nodes as the validation set, and 1000 nodes as the test set for all models. For each model, we conduct $100$ runs for the fixed training/validation/test split from  (Kipf and Welling, 2017), which is commonly used to evaluate performance by the community. Also, we conduct $100$ runs for each model on randomly training/validation/test splits, where we additionally ensure uniform class distribution on the train split as  (Fey and Lenssen, 2019). We compute the average test accuracy of $100$ runs. As shown in Table  2, our DAGNN model performs better than the representative baselines by significant margins. Also, the fact that DAGNN achieves state-of-the-art performance on random splits demonstrates the strong robustness of DAGNN. Quantitatively, for the randomly split data, the improvements of DAGNN over GCN are 4.6%, 3.0%, and 3.0% on Cora, CiteSeer, and PubMed, respectively.

The results on co-authorship and co-purchase datasets are summarized in Table  3. We utilize 20 labeled nodes per class as the training set, 30 nodes per class as the validation set, and the rest as the test set. The results of baselines are obtained from  (Shchur et al., 2018). For DAGNN, we conduct $100$ runs for randomly training/validation/test splits as  (Shchur et al., 2018) to ensure a fair comparison with baselines. Our DAGNN model achieves better performance over the current state-of-the-art models by significant margins of 1.5%, 1.0%, 1.0%, and 0.6% on the Coauthor CS, Coauthor Physics, Amazon Computers, and Amazon Photo, respectively. Note that DAGNN reduces the error rate by $11\%$ on average.

In summary, our DAGNN achieves superior performance on all these seven datasets, which significantly demonstrates the effectiveness of our proposed model. These results verify the superiority of learning node representations from large and adaptive receptive fields, which is achieved by decoupling transformation from propagation and utilizing an adaptive adjustment mechanism in DAGNN.

The number of training samples is usually limited in the real world graph. Hence, it is necessary to explore how models perform with different training set sizes. To further demonstrate the advantage that our DAGNN is capable of capturing information from large and adaptive receptive fields, we conduct experiments with different training set sizes for several representative baselines. MLP only utilizes node features to learn representations. GCN and GAT include the structure information by propagation representations through edges, however, only limited receptive fields can be taken into consideration and it is shown in Section 3.2 that performance degrades when stacking multiple GCN layers to enable large receptive fields. APPNP, SGC, and our DAGNN all have the ability to deploy a large receptive field. Note that for a fair comparison, we set the depth in APPNP, SGC, and DAGNN as 10, where information in the 10-hop neighborhood can be included. For each model, we conduct $100$ runs on randomly training/validation/test splits for every training set size on Cora dataset. The results are present in Table 4 where our improvements over GCN are also highlighted. Our DAGNN achieves the best performance under different training set sizes. Notably, The superiority of our DAGNN can be demonstrated more obviously when fewer training nodes are used. The improvement of DAGNN over GCN increases greatly when the number of training nodes decreases. Extremely, only utilizing one training node per class, DAGNN achieves an overwhelming result over GCN by a significant margin of 23.7%. These considerable improvements are mainly attributed to the advantage that DAGNN can incorporate information from large receptive fields by removing the entanglement of representation transformation and propagation. Reachable large receptive fields are beneficial for propagating training signals to distant nodes, which is very essential when the number of training nodes is limited. APPNP and SGC also can gather information from a large neighborhood, but they perform not as good as DAGNN. This performance gap is mainly caused by the adaptive adjustment of DAGNN, which can adjust the information from different receptive fields for each node adaptively.

In order to investigate when over-smoothing happens in our DAGNN, we conduct experiments for DAGNN with different depths. For each dataset, we choose different hyperparameter $k$ in DAGNN, which means the $k$-hop neighborhood is visible by each node, and conduct $100$ runs for each setting. The results are illustrated in Figure 6. For citation and co-authorship datasets, very deep models with large numbers of propagation iterations can be applied with keeping stable or slightly decreasing performance, which can be attributed to the design that we decouple the transformation from propagation and utilize adaptive receptive fields to learn node representations in DAGNN. Note that performances on co-purchase datasets decrease obviously with the increment of depth. This should be resulted by their larger value of edge density than other datasets, as shown in Table 1. Intuitively, when nodes are more densely connected, their representations will become indistinguishable by applying a smaller number of propagation iterations, which aligns with our assumption in Section 3.3 that further connection exists between the graph topology information and convergence speed.