Year: 2021

Abstract:
Graph Neural Networks (GNNs) have already been widely applied in various graph mining tasks. However, most GNNs only have shallow architectures, which limits performance improvement. In this paper, we conduct a systematic experimental evaluation on the fundamental limitations of current architecture designs. Based on the experimental results, we answer the following two essential questions: (1) what actually leads to the compromised performance of deep GNNs; (2) how to build deep GNNs. The answers to the above questions provide empirical insights and guidelines for researchers to design deep GNNs. Further, we present Deep Graph Multi-Layer Perceptron (DGMLP), a powerful approach implementing our proposed guidelines. Experimental results demonstrate three advantages of DGMLP: 1) high accuracy – it achieves state-of-the-art node classification performance on various datasets; 2) high flexibility – it can flexibly choose different propagation and transformation depths according to certain graph properties; 3) high scalability and efficiency – it supports fast training on large-scale graphs.

heading: 1 INTRODUCTION
text: The recent success of Graph Neural Networks (GNNs) (Zhang et al., 2020) has boosted researches on knowledge discovery and data mining on graph data. Designed for graph-structured data, GNNs provide a universal way to tackle node-level, edge-level, and graph-level tasks, including social network analysis (Qiu et al., 2018; Fan et al., 2019; Huang et al., 2021), chemistry and biology (Dai et al., 2019; Bradshaw et al., 2019; Do et al., 2019), recommendation (Monti et al., 2017; Wu et al., 2020; Yin et al., 2019), natural language processing (Bastings et al., 2017; Wu et al., 2021; Vashishth et al., 2020), and computer vision (Qi et al., 2018; Shi et al., 2019; Sarlin et al., 2020).
The key to the success of most GNNs lies in the graph convolution operation, which propagates neighbor information to the center node in an iterative manner (Wu et al., 2019). The graph convolution operation can be further decomposed into two sequential operations: embedding propagation (EP) and embedding transformation (ET). The EP operation can be viewed as a special form of Laplacian smoothing (NT & Maehara, 2019), which combines the embeddings of a node itself and its one-hop neighbors. The embeddings of nodes within the same connected component would become similar after applying the smoothing operation, which greatly eases the downstream tasks. The ET operation applies neural networks and transforms the node embeddings to target dimensions. Taking the widely-used Graph Convolutional Network (GCN) (Kipf & Welling, 2016) as an example, through stacking k convolution operations (i.e., layers), each node in GCN can utilize the information from nodes within its k-hop neighborhood, and thus improve the predictive accuracy by getting more unlabeled nodes involved in the training process.
Despite the remarkable success, simply stacking many graph convolution operations leads to massive performance degradation. As a result, most GNNs today only have shallow architectures (e.g., 2 or 3 layers), which limits their exploitation of deep structural information. Concretely, under the semi-supervised setting where only a few labels are given, shallow GNNs can utilize only a small percentage of nodes during model training, leading to sub-optimal node classification accuracy.
To alleviate the problem that GNNs cannot go deep, many researches have been proposed, and they attribute the performance degradation of deep GNNs to several reasons. Among the suggested reasons, most existing works (Feng et al., 2020; Chen et al., 2020a; Zhao & Akoglu, 2020; Godwin et al., 2021; Rong et al., 2019; Zeng et al., 2020a; Min et al., 2020; Chamberlain et al., 2021; Chien et al., 2021; Zhou et al., 2020a; Hou et al., 2019; Beaini et al., 2021; Yan et al., 2021; Cai & Wang,
2020) consider the over-smoothing issue as the major cause of performance degradation of deep GNNs. Notice that the EP operation smooths the node embeddings, i.e., making nodes within the same connected component similar. If a GNN is stacked with a large number of graph convolution operations, the output embeddings might be over-smoothed, i.e., nodes within the same connected component become indistinguishable.
Questions Investigated. In this paper, we dive deep into the problem of why most existing GNNs cannot go deep and try to present answers to the following two key questions:
Q1: What actually limits the deep stacking of convolution operations in GNN designs? Q2: How can we design deep GNNs with the help of the findings from the experimental analysis
and outperform the state-of-the-art GNNs?
Contributions. To answer the above research questions, we first conduct a comprehensive evaluation to revise the over-smoothing issue and identify the root cause of performance degradation of most existing GNNs when they go deep. Based on the above analysis, we obtain helpful insights and guidelines to design deep GNNs. Our main contributions are summarized as follows.
C1: We clarify the concept of model depth by separating and considering the two different depths when designing deep GNNs: the propagation depth Dp and the transformation depth Dt. Through experimental evaluations, we find that large Dp leads to the over-smoothing issue whereas large Dt leads to the model degradation issue in the current GNN models. Moreover, we observed that the latter usually happens much earlier than the former as Dp and Dt increase at the same speed. Thus, the model degradation issue introduced by large Dt is the true root cause for the failure of deep GNNs.
C2: To design models that support largeDp, we propose a node-adaptive combination mechanism for combining propagated features under EP operations of different steps. To support large Dt, we add residual connections between ET operations to alleviate the model degradation issue. Further, we present Deep Graph Multi-Layer Perceptron (DGMLP), a novel approach that adopts the composition of the above mentioned two mechanisms to successfully support both large Dp and large Dt based on our findings from the experimental analysis. We validate the effectiveness of DGMLP on six public datasets and the Industry dataset from the real industrial environment. Experimental results demonstrate that DGMLP outperforms the SOTA GNNs while maintaining high scalability and efficiency.
To the best of our knowledge, this paper is the first to conduct an experimental evaluation that identifies the major reason why most existing GNNs cannot go deep. Our findings and the derived guidelines open up a new perspective on designing deep GNNs for graph-structured data.

heading: 2 PRELIMINARY
text: In this section, we first explain the problem formulation. Then we introduce Embedding Propagation (EP) and Embedding Transformation (ET) in the graph convolution operation in detail.

heading: 2.1 PROBLEM FORMALIZATION
text: In this paper, we consider an undirected graph G = (V , E) with |V| = N nodes and |E| =M edges. A is the adjacency matrix of G, weighted or not. Each node possibly has a feature vector of size d, stacked up to an N × d matrix X. D = diag (d1, d2, · · · , dn) ∈ RN×N denotes the degree matrix of A, where di = ∑ j∈V Aij is the degree of node i. In this paper, we focus on the semi-supervised node classification task. Suppose Vl is the labeled node set, the goal is to predict the labels for nodes in the unlabeled set Vu under the limited supervision of labels for nodes in Vl.

heading: 2.2 CONVOLUTION ON GRAPHS
text: Graph Convolution. Based on the intuitive assumption that locally connected nodes are likely to have the same label (McPherson et al., 2001), GNN iteratively propagates the information of each
node to its adjacent nodes. For example, each graph convolution operation in GCN firstly propagates the node embeddings to their neighborhoods and then transforms their propagated node embeddings:
X(k+1) = σ ( ÂX(k)W(k) ) , Â = D̃ 1 2 ÃD̃− 1 2 , (1)
where X(k) and X(k+1) are the node embedding matrices at layer k and k + 1, respectively. Ã = A + IN is the adjacency matrix of the undirected graph G with self loops added, where IN is the identity matrix. Â is the normalized adjacency matrix, and D̃ is its corresponding degree matrix.
By setting different r in Â = D̃r−1ÃD̃−r, different normalization strategies can be employed, such as the symmetric normalized matrix D̃− 1 2 ÃD̃− 1 2 (Kipf & Welling, 2016), the random walk transition probability matrix D̃−1Ã (Xu et al., 2018), and the reverse random walk transition probability matrix ÃD̃−1 (Zeng et al., 2020b). We adopt Â = D̃− 1 2 ÃD̃− 1 2 in this work.
EP and ET Operations. Each graph convolution operation in GNNs can be decomposed into two sequential operations: Embedding Propagation (EP) and Embedding Transformation (ET). This decomposition naturally leads to two corresponding GNN depths: propagation depth Dp and transformation depth Dt. Concretely, GNN first executes EP, which generates smoothed features by multiplying the normalized adjacency matrix Â with the node embedding matrix X:
EP(X) = ÂX. (2)
Then, the smoothed features X̂ = EP(X) will be transformed with the learnable transformation matrix W and the activation function σ(·):
ET(X̂) = σ(X̂W). (3)
Fig. 1 shows the framework of a two-layer GCN. To note that, GCN will degrade to MLP if Â is the identity matrix, which is equal to removing the EP operation in all GCN layers. More detailed analysis and classification of current GNN approaches can be found in Appendix A.

heading: 3 SMOOTHNESS MEASUREMENT
text: In Eq. 2, each time Â multiplies with X, information one more hop away can be acquired for each node. Thus, in order to fully leverage high-order neighborhood information, a series of multiplications of ÂX, i.e., the EP operation, have to be carried out, which means stacking multiple GNN layers. However, if we execute ÂX numerous times, the node embeddings within the same connected component would reach a stationary state, leading to indistinguishable node embeddings (i.e., oversmoothing issue). Concretely, when adopting Â = D̃r−1ÃD̃−r, Â∞ follows
Â∞i,j = (di + 1)
r(dj + 1) 1−r
2m+ n , (4)
which shows that after infinite times of multiplication, the influence from node i to j is only determined by the degrees of them. Under this scenario, the neighborhood information is fully corrupted, resulting in catastrophic node classification accuracy.
As the over-smoothing issue is only introduced by the EP operation rather than the ET operation, here we introduce a new metric, “Node Smoothness Level (NSL)”, to evaluate the smoothness of a node after k steps of EP operation. Suppose X(0) = X is the original node feature matrix, and X(k) = ÂkX(0) is the smoothed features after k times of EP operation.
Definition 3.1 (Node Smoothing Level). The Node Smoothing Level NSLv(k) parameterized by node v and the EP steps, k, is defined as:
α = Sim(xkv ,x 0 v), β = Sim(x k v ,x ∞ v ), NSLv(k) = α ∗ (1− β), (5)
where xkv is the smoothed feature of node v after k steps of EP operation, x 0 v represents node v’s original feature, and x∞v represents node v’s feature at stationary state. Sim(·) is a similarity function, being the cosine similarity in the following discussion.
Further, the “Graph Smoothing Level” (GSL) parameterized by the EP steps, k, is defined as:
GSL(k) = 1
N ∑ v∈V NSLv(k). (6)
Smaller GSL(k) means that X(k) is more likely to forget the original node feature information X(0) after k steps of EP operation and has a higher risk of the over-smoothing issue.

heading: 4 MISCONCEPTIONS AND THE TRUE ROOT CAUSE
text: Most previous works (Li et al., 2018; Zhang et al., 2019) claim that the over-smoothing issue is main cause for the failure of deep GNNs. There have been lines of works that aim at designing deep GNNs. For example, DropEdge (Rong et al., 2019) randomly removes edges during training, and Grand (Feng et al., 2020) randomly drops raw features of nodes before propagation. Despite their ability to go deeper while maintaining or even getting better predictive accuracy, the explanations for their effectiveness are misleading in some instances. The experimental analysis about misconceptions other than the over-smoothing issue can be found in Appendix C.

heading: 4.1 IS OVER-SMOOTHING REALLY THE ROOT CAUSE?
text: Enlarging Dp in Vanilla GCN. To investigate the relations between smoothness and node classification accuracy, we increase the number of graph convolutional layers in vanilla GCN (Dp = Dt) and a modified GCN with Â2 being the normalized adjacency matrix (Dp = 2Dt) on the PubMed dataset (Sen et al., 2008). Supposing that the over-smoothing issue is the main cause for the failure of deep GNNs, the predictive accuracy of the GCN with Dp = 2Dt should be way lower than the one of vanilla GCN. The experimental results are shown in Fig. 2(a).
From Fig. 2(a), we can see that even with a higher level of smoothness, GCN with Dp = 2Dt always has similar predictive accuracy with vanilla GCN (Dp = Dt) when Dt ranges from 1 to 8, and the over-smoothing issue seems to begin dominating the performance decline only when Dp exceeds 16 (2 × 8). The performance of vanilla GCN does decrease sharply when Dp exceeds 2, which is precisely the situation the over-smoothing issue suggests. However, even with relatively large Dp (e.g., 12), the predictive accuracy of the model with larger smoothness (GCN with Dp = 2Dt) is similar to the vanilla GCN, which on the contrary implies that the over-smoothing issue may not be the major cause for performance degradation of deep GNNs until the graph smoothness achieves an extremely high level (e.g., Dp > 16 on the PubMed dataset).
Enlarging Dp in SGC. To further validate our guess, we increase the number of propagation depth Dp of SGC and then evaluate the corresponding predictive accuracy and the value of GSL defined
in Sec. 3. We present the evaluation results in Fig. 2(b). By increasing Dp from 1 to 10, the value of GSL has decreased by more than 60%, but the corresponding predictive accuracy decline is less than 1%. This sharp contrast strongly illustrates that low GSL, i.e., the over-smoothing issue, is not the main cause for the performance degradation of deep GNNs. Moreover, compared with 10-layer vanilla GCN in Fig. 2(a), the corresponding predictive accuracy of 10-layer SGC is still quite high even with the same Dp as vanilla GCN. Therefore, we further guess that the large Dt may be the root cause for the performance degradation of deep vanilla GCNs.
Large Dt Dominates Performance Degradation. To dig out the true limitation of deep GCNs, we fix the number of transformation depth Dt to 2 and set the normalized adjacency matrix to ÂDp/2 (when Dp is odd, use ÂbDp/2c+1 in the first layer and ÂbDp/2c in the second layer), and then report the accuracy along with the increased propagation depth Dp. The experimental results in Fig. 2(c) shows that the accuracy of GCN with Dt = 2 does not drop quickly when Dp becomes large, while it faces a sharp decline in vanilla GCN, which fixes Dp = Dt. Individually enlarging Dp will increase the risk of the over-smoothing issue, but the accuracy is only slightly influenced. However, the performance of vanilla GCN experiences a drastic drop if we simultaneously increase Dt.
Findings 1: LargeDp will harm the predictive accuracy of deep GNN, yet the accuracy decline is relatively small. On the contrary, large Dt is the root cause for the failure of deep GNNs.
4.2 WHAT’S BEHIND LARGE Dt?
To learn what is the fundamental problem caused by largeDt, we first evaluate the predictive accuracy of deep MLP on the PubMed dataset and then move the research object to deep GNN.
Deep MLP Also Performs Bad. We evaluate the predictive accuracy of MLP along with Dt, i.e., the number of MLP layers, on the PubMed dataset, and the black line in Fig. 3(a) shows the evaluation results. It can be easily drawn from the results that the predictive accuracy of MLP also decreases sharply when Dt increases. Thus, the performance degradation caused by large Dt also exists in MLP. It reminds us that the approaches easing the training of deep MLP might also help alleviate the performance degradation caused by large Dt in GNN.
Skip Connections Can Help. The widely-used approach that eases the training of deep MLP is to add skip connections between layers (He et al., 2016; Huang et al., 2017). Here, we add residual and dense connections to MLP and generate two MLP variants: “MLP+Res” and “MLP+Dense”, respectively. The accuracy of these two models with increasing Dt is shown in Fig. 3(a). Compared with plain deep MLP, the accuracy of both “MLP+Res” and “MLP+Dense” does not encounter huge degradation when Dt increases. The results illustrate that adding residual or dense connections can effectively alleviate the performance degradation issue cause by large Dt.
Model Degradation. The skip connections are first introduced in (He et al., 2016) to alleviate the model degradation issue, which is a phenomenon that the accuracy firstly increases and then decreases rapidly when increasing the number of layers in one model. Surprisingly, the degradation is not caused by overfitting as the training error becomes higher when adding more layers in the model. Adopting the same approach to alleviate the model degradation issue, we add residual and dense connections to GCN and generate two GCN variants: “ResGCN” and “DenseGCN”, respectively. The accuracy results in Fig. 3(b) illustrate that the performance decline of both “ResGCN” and “DenseGCN” can be ignored compared to the huge accuracy decline of vanilla GCN.

heading: 5 GUIDELINES ON CONSTRUCTING DEEP GNNS
text: In this section, we propose several guidelines on how to construct deep GNNs that support large propagation depth Dp and large transformation depth Dt based on the experimental analysis in Sec. 4. Further Discussions about when to adopt deep GNNs can be found in Appendix B.

heading: 5.1 A MORE FLEXIBLE FRAMEWORK
text: Many recent GNN works follow the framework design proposed by SGC (Wu et al., 2019) which decouples the EP and ET operations inside each GNN layer. The decoupled design split the framework into two components. In the most popular decoupled GNN design, the first component executes the EP operation in a certain manner to generated propagated node features. Then the propagated features are then fed into the second component to execute ET operations. The second component is usually a plain MLP. There are several other methods (Klicpera et al., 2018; Liu et al., 2020) that exchange the order of the two components mentioned above. Under the decoupled framework, the choices of Dp and Dt are more flexible as it breaks the limit that Dp = Dt. Thus, for different kinds of graph-structured data, the decoupled framework is able to adopt different values of Dp and Dt for optimal predictive accuracy. For example, S2GC (Zhu & Koniusz, 2021) and GBP (Chen et al., 2020b) first execute the EP operations to generate propagated features at different Dp. Then they adopt a heuristic weighting mechanism to combine these propagated features. Finally, the combined features are fed into a plain MLP to get the prediction results.
Guidelines 1: The decoupled framework should be adopted to free the choices of Dp and Dt from the restraint that Dp = Dt in order to adapt to the characteristics of different datasets.
5.2 HOW TO CONSTRUCT GNNS WITH LARGE Dp?
Despite the effectiveness of previous works, a problem still exists: when combining propagated features, the weighting mechanism works at the graph level rather than at the node level. For example, the weighting mechanism in S2GC (Zhu & Koniusz, 2021) and GBP (Chen et al., 2020b) is sub-optimal as it assigns the same weight distribution to all the nodes when combining propagated features at different propagation steps. As a result, the individual properties of each node are ignored. To verify our claim, we apply SGC for the node classification task with different propagation depths on 12 randomly selected nodes in the Cora dataset. We run SGC 100 times and report the average accuracy of the selected nodes. We observe from Fig. 4 that the optimal propagation depths for the selected nodes are highly diverse. The results demonstrate that different nodes should have different weight distributions along with Dp to get the optimal predictive accuracy.
Guidelines 2: A node-adaptive weighting mechanism should be adopted to satisfy each node’s diverse needs for the propagation depth Dp when constructing deep GNNs.
5.3 HOW TO CONSTRUCT GNNS WITH LARGE Dt?
Recently, lines of works have been proposed to support large Dt, and many of them add skip connections between GNN layers motivated by ResNet (He et al., 2016) and DenseNet (Huang et al., 2017). For example, JK-Net (Xu et al., 2018) proposes a new transformation scheme for node embeddings that combines all node embeddings at previous layers in the final layer. GCNII (Chen
et al., 2020c) addresses small Dt via initial residual connections and identity mappings. Besides, as shown in Fig. 3(b), vanilla GCN with residual or dense connections is also able to support large Dt.
Guidelines 3: Adding skip connections between GNN layers is an effective way for GNN models to support large Dt.

heading: 6 ONE ALTERNATIVE SOLUTION
text: Under the guidance of the above guidelines, we propose a scalable and flexible model termed Deep Graph Multi-Layer Perceptron (DGMLP), which contains a node-adaptive weighting mechanism for large Dp and the residual connections for large Dt. Following the decoupled framework, DGMLP first calculates the propagated features at different Dp using the EP operation. Then a novel nodeadaptive weighting mechanism is proposed to combine the propagated features at different Dp effectively. Finally, the combined feature is fed into an MLP with added skip connections to support large Dt. The remainder of this section will introduce the node-adaptive weighting mechanism and the skip connections adopted in DGMLP in detail.

heading: 6.1 NODE-ADAPTIVE WEIGHTING MECHANISM
text: After generating the propagated features X(k) = ÂkX for propagation depth k ranges from 1 to K using the EP operation, we further calculate the NSLv(k) parameterized by node v and propagation depth k defined in Def. 3.1. Remember that smaller NSLv(k) means that the node embedding at propagation step k is more likely to forget the original node feature information and has a higher risk of the over-smoothing issue. Thus, in this case, propagated feature at propagation step k, xkv should be intuitively assigned with smaller weights. To restrain the weights in between 0 and 1, the propagation weight wv(k) parameterized by node v and propagation step k is defined as the softmax output of {NSLv(0), NSLv(1), · · · , NSLv(K)}:
wv(k) = eNSLv(k)/T K∑ l=0 eNSLv(l)/T . (7)
Similar to Knowledge Distillation (Hinton et al., 2015; Lan et al., 2018), the temperature T is adopted here to soften or harden the probability distributions. Smaller T will harden the distributions, and thus the model will focus more on the local graph information.
Finally, the propagated features at different Dp are combined using the weight wv(k) in Eq. 7 to generate the combined feature x̂v = K∑
k=0
wv(k)x k v . By adaptively assigning different propagation
weights for different nodes, we can simply increase Dp on the graph level and get more powerful node embeddings with personalized smoothing levels for each node.

heading: 6.2 SKIP CONNECTIONS
text: Following guidelines 3, we choose to add residual connections (He et al., 2016) between the layers in the MLP of our DGMLP. We refer to the layers in the MLP of our DGMLP as the following format:
h(l+1)v = σ(h (l) v W (l)) + h(l)v , (8)
where W(l) is the learnable parameter matrix, h(0)v = x̂v is the original combined node feature vector, and h(l)v is the transformed node embeddings at the l-th layer of the MLP with residual connections.

heading: 7 DGMLP EVALUATION
text: In this section, we conduct extensive experiments to evaluate our proposed DGMLP. We first introduce the utilized datasets and experiment setup. Then, we compare DGMLP with state-of-theart baselines in predictive accuracy, scalability, and model depth. More experimental results about efficiency, graph sparsity, and interpretability of DGMLP can be found in Appendix E.

heading: 7.1 EXPERIMENTAL SETTINGS
text: Datasets. We adopt the three popular citation network datasets (Cora, Citeseer, PubMed) (Sen et al., 2008), three large OGB datasets (ogbn-arxiv, ogbn-products, ogbn-papers100M) (Hu et al., 2020), and one Industry dataset from our industrial cooperative enterprise in our evaluation. Table 7 in Appendix D.1 presents an overview of these seven datasets.
Baselines. We choose the following baselines: GCN (Kipf & Welling, 2016), GraphSAGE (Hamilton et al., 2017), JK-Net (Xu et al., 2018), ResGCN (Li et al., 2019), APPNP (Klicpera et al., 2018), AP-GCN (Spinelli et al., 2020), DAGNN (Liu et al., 2020), SGC (Wu et al., 2019), SIGN (Frasca et al., 2020), S2GC (Zhu & Koniusz, 2021), and GBP (Chen et al., 2020b). The hyperparameter details for our DGMLP and all the baseline methods can be found in Appendix D.2.

heading: 7.2 END-TO-END COMPARISON
text: The classification results on three citation networks are shown in Table 1. We observe that DGMLP outperforms all the compared baseline methods. Notably, the predictive accuracy of DGMLP exceeds the one of current state-of-the-art method GBP by a margin of 0.6% on the largest citation networks dataset, PubMed. Compared with coupled methods (e.g., GCN, JK-Net), the decoupled methods (e.g., DAGNN, GBP) get better predictive accuracy. It is due to the fact that the disentanglement of EP and ET operations enables Dp to go extremely deep, exploiting more deep structural information.
We further evaluate DGMLP on the three large OGB datasets and one Industry dataset, and the results are also summarized in Table 1.
As shown in Table 1, DGMLP consistently achieves the best performance across the four large datasets. The improvement of DGMLP over baseline methods mainly relies on its support of both large Dp and large Dt.

heading: 7.3 TRAINING SCALABILITY
text: To test the scalability of DGMLP, we use the Erdős-Rényi graph (Erdos et al., 1960) generator in the Python package NetworkX (Hagberg et al., 2008) to generate artificial graphs of different sizes. The node sizes of the generated artificial graphs vary from 0.1 million to 1 million, and the probability of an edge exists between two nodes is set to 0.0001. We choose two representative methods GCN and APPNP as compared baselines. The total running time (including the pre-processing time) of training for 200 epochs and the GPU memory requirement are shown in Fig. 5(a) and Fig. 5(b), respectively. The running time speedup of DGMLP against GCN is also included in Fig. 5(a).
The experimental results in Fig. 5(a) illustrate that DGMLP is highly efficient compared to GCN and APPNP. It only takes DGMLP 223.4 seconds to finish the training on a large graph of size 1 million, which is less than the running time of both GCN and APPNP on the graph of size 0.3 million. Fig. 5(b) shows that the GPU memory requirement of DGMLP grows almost linearly along with graph size. On the contrary, the GPU memory requirements of GCN and APPNP both grow much quicker than DGMLP, exceeding 16GB when the graph size is 1 million, while the memory requirement of DGMLP is just over 3GB at the same graph size. It indicates that our proposed DGMLP enjoys high scalability and high efficiency at the same time.

heading: 7.4 ANALYSIS OF MODEL DEPTH
text: In this subsection, we conduct experiments to validate that our proposed DGMLP can support both large Dp and large Dt. We choose SGC, DAGNN, and S2GC as baseline methods.
Firstly, we fix Dt to 3 and increase Dp from 1 to 20 on the ogbn-arxiv dataset. As seen from Fig. 6(a), SGC cannot perform well when Dp goes deep as the over-smoothing issue occurs. The predictive accuracy of DAGNN, S2GC, and our DGMLP maintains high when Dp becomes large. Moreover, DGMLP consistently outperforms all the baseline methods when Dp is greater than 6. The superiority of our DGMLP over DAGNN and S2GC lies in that we adopt a node-adaptive combination mechanism to satisfy the diverse needs of different nodes for propagation depth Dp.
Secondly, we fix Dp to 10 and increase Dt from 1 to 10. Fig. 6(b) shows that the predictive accuracy of all the baseline methods, including SGC, DAGNN, and S2GC decreases rapidly when Dt becomes large. It is because that these methods do not take the model degradation issue into consideration, which is precisely the main contributor to the performance degradation when Dt is large. This property limits the expressive power of these baseline methods, resulting in relatively low performance when adopted on large graphs. In the meantime, the performance of our proposed DGMLP still increases steadily or maintains even when Dt is large. To sum up, compared with other baseline methods, our DGMLP can consistently improve predictive accuracy with larger Dp or Dt, which validates our experimental analysis and guidelines in Sec. 4 and 5.

heading: 8 CONCLUSION
text: In this paper, we perform an experimental evaluation of current GNNs and find the root cause for the failure of deep GNNs: the model degradation issue introduced by large transformation depth. The over-smoothing issue introduced by large propagation depth does harm the predictive accuracy. However, GNN is much more sensitive to the model degradation issue than the over-smoothing issue, i.e., the model degradation issue happens much earlier than the over-smoothing issue as Dp and Dt increases at the same speed. Based on the above analysis, we present Deep Graph Multi-Layer Perceptron (DGMLP), a flexible and deep GNN model that simultaneously support large propagation and transformation depth. Extensive experiments on seven real-world graph datasets demonstrate that DGMLP outperforms state-of-the-art GNNs, and enjoys high scalability and efficiency at the same time.

heading: 9 REPRODUCIBILITY STATEMENT
text: The source code of DGMLP can be found in Anonymous Github (https://anonymous.4open. science/r/DGMLP-4A79). To ensure reproducibility, we have provided the overview of datasets and baselines in Section 7.1 and Appendix D.1. The detailed hyperparameter settings for our DGMLP can be found in Appendix D.2. Please refer to “README.md” in the Github repository for more reproduction details.

heading: A DEEPER ANALYSIS OF GNN ARCHITECTURE

heading: A.1 CONVOLUTION PATTERN
text: According to whether the model disentangles the EP and ET operations, current GNNs can be classified into two major categories: entangled and disentangled, and each can be further classified into two smaller categories based on the order of EP and ET operations.
Entangled Graph Convolution. Entangled Propagation and Transformation (EPT) pattern is widely adopted by mainstream GNNs, like GCN (Kipf & Welling, 2016), GraphSAGE (Hamilton et al., 2017), GAT (Velickovic et al., 2018), and GraphSAINT (Zeng et al., 2020b). The idea behind EPT-based GNNs is similar to the conventional convolution: it passes the input signals through a set of filters to propagate the information, which is further followed by nonlinear transformations. As a result, EP and ET operations are inherently intertwined in this pattern, i.e., each EP operation requires a neural layer to transform the hidden representations to generate the new embeddings for the next step. Motivated by ResNet (He et al., 2016), some GNNs with the EPT-SC pattern deepen the EPT-based GNNs with skip connections, and both JK-Net (Xu et al., 2018), and ResGCN (Li et al., 2019) are the representative methods of this category.
Besides the strict restriction that Dp = Dt, Table 2 shows EPT-based and EPT-SC-based GNNs also suffer from low scalability and low efficiency. On the one hand, a deeper structure has more parameters, resulting in greater computation costs. On the other hand, the number of nodes within each node’s neighborhood grows exponentially with the increase of model depth in typical graphs, incurring significant memory requirement in a single machine or high communication costs in distributed environments (Zheng et al., 2020).
Disentangled Graph Convolution. Previous works (Frasca et al., 2020; He et al., 2020; Wu et al., 2019; Zhang et al., 2021a) have shown that the true effectiveness of GNNs lies in the EP operation rather than the ET operation inside the graph convolution. Therefore, some disentangled GNNs propose to separate the ET operation from the EPT scheme. They can be classified into the following two categories according to the order of EP and ET operations.
One pattern is the Disentangled Transformation and Propagation (DTP). As shown in Table 2, DTPbased GNNs firstly execute the ET operations and then turn to the EP operations, and the most representative methods in this category are PPNP (Klicpera et al., 2018), APPNP (Klicpera et al., 2018), and AP-GCN (Spinelli et al., 2020). Unlike the DTP pattern, GNNs with the convolution pattern of Disentangled Propagation and Transformation (DPT) execute the EP operations in advance, and the propagated features are fed into a simple model composed of multiple ET operations (Zhang et al., 2021b). For example, SGC (Wu et al., 2019) removes the nonlinearities in GCN and collapses all the weight matrices between consecutive layers into a simple logistic regression. Based on SGC, SIGN (Frasca et al., 2020) further combines many graph convolutional filters in the EP operations, which differ in types and depths, utilizing significantly more structural information.
As shown in Table 2, compared with entangled GNNs, DTP-based GNNs can support large propagation depth Dp. Besides, DTP-based GNNs do not restrict Dp = Dt, enabling more flexibility in the GNN architecture design. However, they still have low scalability and efficiency issues when adapted to large graphs due to the high-cost propagation process during training. On the contrary, DPT-based GNNs only need to precompute the propagated features once. Therefore, they are easier to scale to large graphs with less computation cost and lower memory requirement.

heading: A.2 DGMLP VERSUS EXISTING METHODS
text: EPT-based GNNs. GNNs with the convolution pattern of EPT assume that Dp = Dt. However, as discussed in Sec. 6.1, the optimal Dp and Dt are highly related to graph sparsity and graph size. For example, it is better to assign large Dp and small Dt for better performance on a small graph with sparse edges. Due to the model degradation issue, current EPT-based GNNs usually have both small Dp and Dt, owing to the inflexible restriction that Dp = Dt. Besides, the EPT-based GNNs also face the problem of low scalability and low efficiency. For example, GCN has the high time complexity of O(DpMd+DtNd2) for the need to repeatedly perform recursive neighborhood expansion at each training iteration to compute the hidden representations of each node. This process is unscalable due to the high memory and computation costs on a single machine and high communication costs in
distributed environments. Compared with EPT-based GNNs, DGMLP is more flexible in assigning different Dp and Dt and enjoys better efficiency, scalability, and lower memory requirement.
EPT-SC-based GNNs. Compared with EPT-based GNNs, the skip connection in EPT-SC-based GNNs helps to alleviate the model degradation issue introduced by large Dt. However, Fig. 3(b) shows that the test accuracy degrades with deeper architecture due to the over-smoothing issue introduced by large Dp. A large graph without the graph sparsity issue requires large Dt and small Dp. However, EPT-SC-based GNNs like ResGCN cannot satisfy such requirements since they simply restrict Dp = Dt. Besides, EPT-SC-based GNNs still have the issues of low scalability, efficiency, and high memory requirement as EPT-based GNNs. Compared with EPT-SC-based GNNs, DGMLP can improve the performance by enabling larger Dp while maintaining high scalability, efficiency, and low memory requirement.
DTP-based GNNs. Compared with GNNs with the convolution pattern of EPT and EPT-SC, DTPbased GNNs disentangle the propagation and the transformation operation, thus can support flexible combinations of Dp and Dt. As shown in Fig. 2(b) and Fig. 2(c), over-smoothing may have less impact on the performance degradation compared with model degradation, and the test accuracy will not decrease rapidly with the larger over-smoothing level. Therefore, lots of DTP-based GNNs own large Dp and small Dt and claim that they can perform well with the deeper architecture. However, they ignore the transformation depth Dt in their design. As shown in Fig. 7(b), the test accuracy degrades rapidly if we increase the transformation depth Dt of DAGNN. Correspondingly, it is hard for DTP-based GNNs to support large graphs with limited transformation depth Dt. Besides, as they execute ET operations first, scalability, efficiency, and memory requirement issues still exist.
DPT-based GNNs. Compared with current DPT-based GNNs, the proposed DGMLP utilizes the same convolution pattern. They all enjoy high scalability, efficiency, and low memory requirement as they can precompute the propagated features. The difference between DGMLP and other DPTbased GNNs is that DGMLP is the first method considering the smoothness from the node level. Therefore, DGMLP can assign individual feature propagation weights to different nodes and then get better-smoothed node embeddings by considering the personalized area in the graph where each node resides. Another advantage of DGMLP is that it can support large transformation depth Dt with the help of residual connections.

heading: B WHEN WE NEED DEEP GNN ARCHITECTURES?
text: When we need deep EP? We review the related works and researches concerning Dp’s importance and then investigate experimentally when it is appropriate to enlarge Dp in GNNs. GNNs mainly benefit from performing EP operations over neighborhoods. Stacking more EP operations will expand a node’s receptive field and help it to gain more deep structural information. However, if the graph is dense, increasing Dp may lead to over-smoothing, which results from the rapid expansion of the receptive field.

heading: Datasets Labels/class 2 4 6 8 12 16 20
text: Generally, most real-world graphs exhibit sparsity in three aspects: edges, labels, and features. We define edge sparsity, label sparsity, and feature sparsity as follows: (1) Edge sparsity: nodes in real-world graphs usually have a skewed degree distribution, and many nodes are rarely connected (Kuramochi & Karypis, 2005). (2) Label sparsity: only a small part of nodes are labeled due to the high labeling costs or long labeling time (Garcia & Bruna, 2017). (3) Feature sparsity: some nodes in the graph do not own features, i.e., the new users or products in a graph-based recommendation system (Zhao & Akoglu, 2020). We argue that sparse graphs naturally need deeper EP for larger receptive fields. Experiments are conducted to demonstrate that the graph sparsity mentioned above will highly affect the optimal choice of Dp. SGC is adopted as the base model throughout these experiments.
Firstly, we investigate how edge sparsity influences the optimal Dp. For a fair comparison, we only sample part of the labels for Cora to have the same feature and label missing rates as PubMed. Then we increase Dp from 2 to 20 on Cora and PubMed and report the test accuracy under each setting. The experimental results in Fig. 4 show that the optimal Dp is 4 for PubMed and 2 for Cora, meaning that the sparser graph requires a larger Dp, which further demonstrate the benefits of deepening Dp under edge sparse conditions. Secondly, we illustrate the relationship between the label sparsity and Dp. As shown in Fig. 5, we fix one labeled node per class on Cora and PubMed and keep the same setting with the edge sparsity experiment. It can be seen that the classification accuracy increases as Dp ascends from 2 to 16. However, if we increase the label rate to 20 nodes per class, the node classification drops from 2 layers. The experiment on PubMed also shows that graphs with lower label rates require larger Dp. Finally, in Table 6, we report the test accuracy under the feature sparsity setting where 50% node features are randomly dropped from Cora and PubMed datasets. The result is consistent with the former two experiments that graphs with higher feature sparsity levels require larger Dp.
When we need deep ET? Generally, stacking multiple ET operations can better fit and learn the data distribution. However, we observe that the optimal Dt for GNN is sensitive to the graph size. Concretely, small graphs contain limited information, and shallow transformation architecture is enough for generating decent node embeddings. However, large graphs have complex structural information as complexity grows at a squared rate, which requires larger

heading: Datasets Feature missing % 2 4 6 8 12 16 20
text: Dt to extract meaningful information. We prove this insight by experimentally examining how Dt influences the node classification performance on Cora and ogbn-arxiv datasets. Concretely, we replace the logistic regression in SGC with “MLP+Res” and increase Dt from 1 to 7. Table 3 shows that the accuracy on ogbn-arxiv increases as Dt ascends from 1 to 6. However, Dt = 2 is enough for the small graph Cora. Therefore, larger graphs need larger Dt for high-quality node embeddings.

heading: C MORE MISLEADING EXPLANATIONS

heading: C.1 OVER-FITTING
text: Some works (Rong et al., 2019; Li et al., 2019; Zhou et al., 2020b; Yang et al., 2020) attribute the performance degradation of deep GNNs to over-fitting. Concretely, over-fitting comes from the case when an over-parametric model tries to fit a distribution with limited training data, which results in learning well on the training data but failing to generalize to the testing data. We plot the corresponding node classification accuracy of GCN on both the training and the test set under different model depths in Fig. 7(a).
Finding. Both the training and test accuracy drop quickly when the model grows deep. However, over-fitting assumes that over-parametric models get low training error but high testing error, inconsistent with the experimental results.
Implication. Over-fitting is not the primary cause for performance degradation of deep GNNs.

heading: C.2 ENTANGLEMENT
text: Some recent works (He et al., 2020; Liu et al., 2020) argue that the key factor compromising the performance of deep GNNs is the entanglement of EP and ET operations in current graph convolutional layers. For example, DAGNN claims that the entanglement of EP and ET operations in GCN is the true reason it only supports shallow architectures. To investigate this statement, we vary the transformation depth Dt in ResGCN, DenseGCN, and vanilla GCN and report their test accuracy on the PubMed dataset. The experimental results are shown in Fig. 3(b).
Finding 1. Although ResGCN and DenseGCN have entangled designs, when Dp and Dt both become large, they do not experience significant performance drop as GCN does. Both the residual and dense connections can effectively alleviate the influence of model degradation, and the performance degradation of ResGCN and DenseGCN starting at Dt = 6 might be caused by the over-smoothing issue.
Implication. GNNs can go deep even in an entangled design, and the entanglement of EP and ET operations may not be the true limitation of the GNN depth.
What is worth noting is that previous works (Zhu & Koniusz, 2021; Liu et al., 2020), which have disentangled designs and state that they support deep architectures, are only able to go deep on the propagation depth Dp. In their original design, if we increase Dt, their performance will also degrade badly. To validate this, we run DAGNN in two different settings: the first controls Dt = 2 and increases Dp, the second controls Dt = Dp and increases Dp. The test accuracy under these two settings on the PubMed dataset is shown in Fig. 7(b).
Finding 2. The disentangled DAGNN also experiences huge performance degradation when the model owns large Dt. If the entanglement dominates the performance degradation of deep GNNs, DAGNN should be able to also go deep on Dt. However, if we individually increase Dt of DAGNN, the sharp performance decline still exists.
Implication. The major limitation of deep GNNs is the model degradation issue introduced by large Dt rather than the entanglement of EP and ET operation.

heading: C.3 GRADIENT VANISHING/EXPLOSION
text: Gradient vanishing means that the low gradient in the shallow layers makes it hard to train the model weights when the network goes deeper, and it has a domino effect on all of the further weights throughout the network. To evaluate whether the gradient vanishing exists in deep GNNs, we respectively perform node classification experiments on the Cora dataset and plot the gradient – the mean absolute value of the gradient matrix of the first layer in the 2-layer and 7-layer GCN in Fig. 7(c).
Finding 1. Although the test accuracy of 7-layer GCN drops quickly, its gradient is as large as the gradient of 2-layer GCNs, or even larger in the initial model training phases. The explanation for the initial gradient rise of the 7-layer GCN might be that the large model needs more momentum first to adjust and then jump out of the suboptimal local minima initially.
Implication. Gradient vanishing is not the leading cause of performance degradation in deep GNNs.

heading: C.4 DISENTANGLED CONVOLUTION
text: We then investigate why disentangling EP and ET is able to allow more EP operations. Concretely, we carefully investigate current disentangled GNNs (Frasca et al., 2020; Rossi et al., 2020) and find that the decoupling strategy makes the propagation and the transformation operations independent, thus Dp and Dt are not forced to be the same. Therefore, disentangled GNNs generally fix Dt and increase Dp to capture deeper graph structural information. Here we select two disentangled GNNs, S2GC and Grand, which state that they support deep architectures. Their performance of individually increasing Dp and Dt are shown in Fig. ?? and Fig. ??, respectively.
Finding. Individually increasing Dp would not incur a severe performance drop even when Dp is increased to 64, while their performance would experience a sharp decline when Dt increases. Increasing Dp enlarges each node’s receptive field, thus leading to more decent representations, which is demonstrated to be even more beneficial for sparse graphs in our following experiments (See Sec. 6.1).
Implication. Deep disentangled GNNs are flexible to individually increase Dp, so that the model degradation introduced by large Dt can be avoided.

heading: D EXPERIMENTAL DETAILS

heading: D.1 DATASET DETAILS
text: The details of the adopted seven datasets can be found in Table 7.

heading: D.2 HYPERPARAMETER DETAILS
text: For the three small citation networks, we adopt a simple logistic regression as the classifier. The propagation depth Dp is set to 20 for Cora and PubMed, and 15 for Citeseer. The learning rate is set to 0.1, and the dropout rate is obtained from a search of range 0.1 to 0.5 with step 0.1. Residual connections are not used on these three citation networks.
For three large ogbn datasets and Industry dataset, a 6-layer MLP with hidden size of 512 is used, and the propagation depth Dp is respectively 20 and 12 for them. Residual connections are used for these four large datasets. Besides, the temperature T is set to 1 as default if it is not specified, and the learning rate and the dropout rate are set to 0.001 and 0.5, respectively.
We run all the methods for 200 and 500 epochs on the citation networks and OGB datasets, respectively. Besides, we run all methods 10 times and report the mean values and the variances of different performance metrics. Other hyperparameters are tuned with the toolkit OpenBox (Li et al., 2021) or follow the settings in their original paper.

heading: E ADDITIONAL EXPERIMENTS

heading: E.1 PERFORMANCE-EFFICIENCY ANALYSIS
text: In this subsection, we evaluate the efficiency of each method in our industrial environment: the real-world Industry dataset. Here, we precompute the smoothed features of each DPT-based GNN, and the time for preprocessing is also included in the training time. Fig. 8 illustrates the results on the Industry dataset across representative baseline methods of each convolution pattern.
Compared with DPT-based GNNs, we observe that both EPT-based and DTP-based GNNs require a significantly larger training time. For example, GCN takes 32 times longer than SGC to complete the training and the training time of AP-GCN is 112 times the one of SGC. Due to the more complex preprocessing, our DGMLP takes twice the training time of SGC’s. However, the relatively time-consuming preprocessing brings significant performance gain to DGMLP, exceeding SGC by
more than 2% across three citation networks. To sum up, our proposed DGMLP achieves better performance and maintains high efficiency.
E.2 INFLUENCE OF GRAPH SPARSITY
To simulate extreme sparse situations in the real world, we design three independent settings on the PubMed dataset to test the performance of our proposed DGMLP when faced with edge sparsity, label sparsity, and feature sparsity, respectively.
Edge Sparsity. We randomly remove some edges in the original graph to strengthen the edge sparsity situation. The edges removed from the original graph are fixed across all the methods under the same edge remaining rate. From the results in Fig. 9(a), it is clear to see that the performance of GBP, S2GC, and our DGMLP is significantly better than SIGN and SGC. Further, DGMLP always has higher test accuracy than GBP and S2GC. SIGN and SGC both have a flaw in that they can not effectively capture the deep structural information, which would become more prominent when edges are extremely sparse in the graph.
Label Sparsity. In this setting, we vary the training nodes per class from 1 to 20 and report the test accuracy of each method. The experimental results in Fig. 9(b) show that the test accuracy of all the compared methods increases as the number of training nodes per class becomes larger. In the meantime, our DGMLP outperforms all the baselines throughout the experiment. With 11 training nodes per class, DGMLP achieves comparable performance with SGC trained under 20 training nodes per class.
Feature Sparsity. In a real-world situation, the feature of some nodes in the graph might be missing. We follow the same experimental design in the edge sparsity setting but removing node features instead of edges. The results in Fig. 9(c) illustrate that our proposed DGMLP has a great antiinterference ability when faced with feature sparsity as its performance drops only a little even there is only 10% node features available.
E.3 INTERPRETABILITY
In this subsection, we empirically explain why our proposed DGMLP is more robust to the oversmoothing issue. Concretely, the baseline method SGC is used for comparison, and the temperature T in our DGMLP is set to 0.2. Besides, the Graph Smoothing Level (GSL) in Sec. 3.2.1 is adopted to evaluate the graph smoothness.
The results in Fig. 10 show that the GSL of both SGC and DGMLP decreases as Dp increases. However, the descending speed of SGC is much quicker than DGMLP, especially when Dp changes from 1 to 5. Moreover, the GSL of DGMLP at Dp = 100 is even larger than the one of SGC at Dp = 5. Fig. 10 strongly illustrates that our proposed DGMLP is more robust to the over-smoothing issue introduced by large Dp, and the performance results in Fig. 6(a) further shows that DGMLP can take advantage of this property to gain more beneficial deep structural information for prediction.

Review summaries:
This work performs a systematic study to analyze the main issues of the difficulty in training deep GNNs by disentangling the effects of embedding propagation (EP) and embedding transformation (ET). They find that the large $D_t$ is the root cause for the failure of deep GNNs. Node-adaptive combination mechanism and residual connections between ET operations are proposed to train deep GNNs.

The paper considers the application of GNNs to semi-supervised node classification tasks. The problem arises in big data problems such as modeling citation databases.  In this line of work it is assumed that the data follows a graph structure, i.e., that locally connected nodes are likely to have the same label. Each node has a d-dimensional feature vector, with graph degree matrix A. Various GNN architectures have been proposed and studied for this problem, often using citation databases as the driving application. The paper considers two aspects of this problem.  First, the authors consider various choices of the hyper-parameters, including the GNN iterations and a (typically) fully connected layer at the output.  It is well known that iterating the graph convolutions leads to local averaging that will asymptotically converge to some form of smoothing, which can result in poor classification.  Here, the authors decouple the GNN smoothing and the follow on network, and refer to this as “unentangled” processing architecture (also called decoupled in the numerical results portion).  They further propose a revised GNN architecture (DGMLP) that incorporates node-adaptive weighting and skip-connections in the second stage.  Numerical experiments complete the work, showing that with appropriate choice of parameters the DGMLP is flexible and can achieve the state of the art results, and good scalability.  

In this work, the authors performed an experimental evaluation on several GNNs in order to understand what aspects of the current architecture designs that leads to the compromised performance of deep GNNs. They claimed to find the root causes: large propagation depth leads to the over-smoothing issue and large transformation depth leads to the model degradation issue. Then they proposed guidelines for designing deep GNNs and a Deep Graph Multi-Layer Perceptron (DGMLP) for implementing the guidelines. Experimental results demonstrate performance of DGMLP in accuracy, flexibility, scalability, and efficiency.