Evaluating Deep Graph Neural Networks
Authors: Wentao Zhang
Zeang Sheng
Jiang Yuezihan
Yikuan Xia
Jun Gao
Zhi Yang
Bin CUI
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep
Graph Neural Networks

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.

Under review as a conference paper at ICLR 2022
EVALUATING DEEP GRAPH NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
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 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 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 (DGMLPP), powerful approach implementing our proposed guidelines. Experimental results demonstrate three advantages of DGMLP: 1) high accuracy it achieves state-of-the-an node classification performance on various datasets; 2) high flcxibility- 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.
INTRODUCTION
The recent success of Graph Neural Networks (GNNs) (Zhang 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
al.
2019 Bradshaw et al. 2019; Do et al.
2019).
recommendation (Monti al.
2017 Wu al.
2020
Yin et al. 2019)), natural language processing (Bastings et al. 2017 Wu et al.
2021
Vashishth
ct 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 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 & convolution operations (i.c., layers), each node in GCN can utilize the information from nodes within its h-hhop 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 few labels are given, shallow GNNs can utilize only small percentage 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 Chen al.) 2020al Zhao & Akoglul 2020 Godwin
et al.
2021 Rong et al. 2019 Zeng et al. 2020a; Min et al. 2020; Chamberlain et al. [202]] 20innChien
Chien
al.
2021 Zhou al.
2020a Hou al.
2019 Beaini et al. 2021
Yan et al. [001 Cai & Wang

---

Under review as a conference paper at ICLR 2022
consider the over-smoothing issue the major cause of performance degradation of deep Notice that the EP operation smooths the node embeddings, i.., making nodes within the same connected component similar. If GNN is stacked with large number of graph convolution operations, the output embeddings might be over-smoothed, i.e., nodes within the same connected component become indistinguishable.
2020)
GNNs.
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-an GNNs?
Contributions. To answer the above research questions, we first conduct comprehensive evaluation to revise the wee-smoothing issue and identify the root cause of performance degradation of most existing GNNs when they 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 D, and the transformation depth D.. Through experimental evaluations, we find that large Dp leads to the over-smoothing issue whereas large D, 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 D, increase at the same speed. Thus, the model degrudation issue introduced by large D, is the true root cause for the failure of deep GNNs.
C2: To design models that support large Dp. we propose a mode-adaptive combination mechanism for combining propagated features under EP operations of different steps. To support large Dr, we add residual connections hetween ET operations to alleviate the model degradation issue. Further, we present Deep Graph Multi-Layer Perceptron (DGMLP), novel approach that adopts the composition of the above mentioned two mechanisms to successfully support both large D, and large D2 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 new perspective on designing deep GNNs for graph-structured data.
PRELIMINARY
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.
2.1 PROBLEM FORMALIZATION
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 feature vector of size stacked up an N d matrix X. D diag (d1, d2,
dn) E I N denotes the degree matrix of A, where d, = Ejev Asj is the degree of node i. this paper, we focus on the semi-supervised node classification task. Suppose Vi is the labeled node set, the goal is to predict the labels for nodes in the unlabeled set V,, under the limited supervision of labels for nodes in V/.
2.2 CONVOLUTION ON GRAPIS
Graph Convolution. Based on the intuitive assumption that locally connected nodes are likely to have the same label (McPherson et al. 200T), GNN iteratively propagates the information of each
2

---

Under review as a conference paper at ICLR 2022
Octput
Propagation
x - Axrt
X
A Nommalazl natis
Figure 1: The relationship between GCN and MI.P.
node to its adjacent nodes. For example, each graph convolution operation in GCN firstly propagates the node embeddings their neighborhoods and then transforms their propagated node embeddings:
x (++1) or (Ax (Ax( w()).
Á = A
where (k) and (k+1) are the node embedding matrices at layer and 1, respectively, Ä A + IN is the adjacency matrix of the undirected graph 9 with self loops added, where Iy is the identity matrix. À is the normalized adjacency matrix, and D its corresponding degree matrix.
By setting different in Å D AĀ -r diffeernt normalization strategies can be employed. such as the symmetric normalized matrix D AD & (Kipf Welling 2016). the random walk transition probability matrix D A (Xu et al. 2018 and the reverse random walk transition probability matrix AD Zeng et al. 2020b We adopt A - AD- 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 D, and transformation depth D,. Concretely, GNN first executes EP, which generates smoothed features by multiplying the normalized adjacency matrix Á with the node embedding matrix X:
EP(X) Åx.
Then, the smoothed features EP(X) will be transformed with the learnable transformation matrix W and the activation function (-):
ET(X) (XX)).
Fig. shows the framework two-layer GCN. To note that, GCN will degrade to MLP if Å is the identity matrix, which is equal removing the EP operation all GCN layers. More detailed analysis and classification of current GNN approaches can be found in Appendix
3 SMOOTHNESS MEASUREMENT
In Eq. 2 each time Å multiplies with X, information one more hop away can be acquired for each node. Thus, in order to fully leverage high-order neighborhood information, series of multiplications of Áx, i.e., the EP operation, have to carried out, which means stacking multiple GNN layers. However, if we execute AX numerous times, the node embeddings within the same connected component would reach a stationary state, leading to indistinguishable node embeddings (i.e., over- smoothing issue). Concretely, when adopting Å AD Å follows
(d, + (d, +1)=-r
A
(4)
2m +
which shows that after infinite times of multiplication, the influence from node to j 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 new metric, "Node Smoothness Level (NSL)", to evaluate the smoothness of node after & steps of EP operation. Suppose X X is the original node feature matrix, and (k) (0) is the smoothed features after l times of EP operation.
3

---

Under review as a conference paper at ICLR 2022
Tex:
Graph Smoothing Level
Caph Smooting
Test, Accurscy
-3
Text Accuracy,
Text Accuracy
23
0.3
car8a GCN W51 D5 GZN vil D2 32)
10
70
4
10
0.0
65
with
8 10
Number Transformation Depth D)
Number Propagation Depth D3
Number Propagation Depth
(a) The influence of Dp to model (b) The influence of GSL to (c) The influence of Dr to model performance.
model performance.
performance.
Figure 2: Over-smoothing is not the main contributor who hurts the performance of deep GNNs,
Definition 3.1 (Node Smoothing Level). The Node Smoothing Level NSL.(k) parumeterized by node and the EP steps, ki is defined as:
= a = Sim(xx, xx), == =-mmmxx X,)), NSL.(K)= a ( (1-
(5)
where xt, is the smoothed feature of node v after steps of EP operation, x2, represents node v's original feature, and x represents node v's feature at stationary slate. Sim(-) is 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
Σ (K). eE
(6)
N
Smaller GSL(() means that (k) is more likely to forget the original node feature information ( after l steps of EP operation and has higher risk of the over-smoothing issue.
4 MISCONCEPTIONS AND THE TRUE RoOT CAUSE
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 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 be found in Appendix C
4.1 IS OVER-SMOOTHING REALLY RoOT CAUSE?
Enlarging D, in Vanilla GCN. To investigate the relations between smoothness and node classification accuracy, increase the number of graph convolutional layers in vanilla GCN (Dp D:) and modified GCN with A being the normalized adjacency matrix (Dp 2D,) on the Pub.Ed dataset (Sen et al. 2008). Supposing that the wver-moothing issue is the main cause for the failure of deep GNNs, the predictive accuracy of the GCN with Dr 2D, should be way lower than the one vanilla GCN. The experimental results are shown in Fig. 2(a)
that with higher level of smoothness, GCN with Dp 2D, always has similar predictive accuracy with vanilla GCN (D,- = D2) when D; ranges from 1 to 8, and the over-smoothing issue seems begin dominating the performance decline only when D, exceeds 16 (2 x 8). The performance of vanilla GCN does decrease sharply when D, 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 D, 2D,) is similar 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 (c.g.. D, > 16 on the PubMed datasct).
From Fig. 2(a)
Enlarging D, in SGC. To further validate our guess, we increase the number of propagation depth Dr of SGC and then evaluate the corresponding predictive accuracy and the value of GST. defined
4

---

Under review as a conference paper at ICLR 2022
Test Accunacy
Tes, Accuracyy
MIP Pm MIP
GCN
MUP
66
7
7
Number Transformation Depth D.
Number Transformation Depth 1),
(a) The skip connection to MLP. (b) The skip connection GCN.
Figure 3: Performance comparison when adding Residual and Dense connection.
in Sec. 3, We present the evaluation results in Fig. 2(b) By increasing D, from 10, the value of G.S.A. L has decreased by more than 60%, but the corresponding predictive accuracy decline is less than 1%. This sharp contrast strongly illustrates that low L.L,, 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. [[a)] the corresponding predictive accuracy of 10-layer SGC is still quite high with the same Dp vanilla GCN. Therefore, we further guess that the large Dr may be the root cause for the performance degradation of deep vanilla GCNs.
Large Dj Dominates Performance Degradation. To dig out the true limitation of deep GCNs, we fix the number of transformation depth D, to 2 and set the normalized adjacency matrix to Á D2/2 (when D, is odd, use A [D,/2|+1 in the first layer and Á [D,/2] in the second layer), and then report the accuracy along with the increased propagation depth D,- The experimental results in Fig. 2 shows that the accuracy of GCN with D, 2 does not drop quickly when Dp becomes large, while faces sharp decline in vanilla GCN, which fixes Dp = D,. 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 we simultaneously increase D.-
Findings 1:
Large Dr will harm the predictive accuracy of deep GNN, yet the accuracy decline relatively small. On the contrary, large De is the root cause for the failure of deep GNNs.
4.2 WHLT'S BEIIND LARGE D,?
To learn what is the fundamental problem caused by large D., 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 D., 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 D, increases. Thus, the performance degradation caused by large D, also exists in MIP. reminds us that the approaches easing the training of deep MI.P might also help alleviate the performance degradation caused by large D, in GNN.
Skip Connections Can Help. The widely- 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 D, 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 D, increases. The results illustrate that adding residual or dense connections can effectively alleviate the performance degradation issue cause by large D..
Model Degradation. The skip connections are first introduced (He et al. 2016) to alleviate the model degradation issue, which is 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. (bb illustrate that the performance decline of both "ResGCN" and "DenseGCN" can be ignored compared to the huge accuracy decline of vanilla GCN.
5

---

Under review as a conference paper at ICLR 2022
Propasation Depth Dp
0.8
N Gar *
0.6
0.4
0.2
3
4 5
8 Randomly Sampled Nodes
9
10
11
12
0.0
Figure 4: Different nodes reach their optimal performance at varied propagation depth D,. Findings The model degradation issue behind large D, is the true root cause for the failure of deep GNNs. And adding skip connections between layers can effectively alleviate the performance degradation issue of deep GNNs.
5 GUIDELINES ON CONSTRUCTING DEEP GNNS
In this section, we propose several guidelines on how to construct deep GNNs that support large propagation depth D, and large transformation depth D, based the experimental analysis Sec. Further Discussions about when to adopt deep GNNs can be found in Appendix B
5.1 A MORE FLEXIBLE FRAMEWORK
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 features are then fed into the second component execute ET operations. The second component is usually plain MIP. There are several other methods (Klicpera et al. 2018 [Lu et al.) 2020) that exchange the order of the two components mentioned above. Under the decoupled framework, the choices of Dp and D, are more flexible as it breaks the limit that D, = D.. Thus, for different kinds of graph-structured data, the decoupled framework is able to adopt different values of D, and D, for optimal predictive accuracy. For example, SCGC (Zhu & Koniusz 2021) and GBP (Chen et al. 2020b) first execute the EP operations to generate propagated features at different D,. Then they adopt a heuristic weighting mechanism combine these propagated features. Finally, the combined features are fed into plain MLP to get the prediction results.
certain manner generated propagated node features. Then the propagated
The decoupled framework should be adopted to free the choices of D, and Dr from the restraint that Dr D, in order to adapt to the characteristics of different datasets.
Guidelines 1:
5.2 HOw TO CONSTRUCT GNNS WITH LARGE Dp?
Despite the effectiveness of previous works, 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 S²GC (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 different propagation steps. As a result, the individual properties of each node are ignored. To verify our claim, 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 Dr to get the optimal predictive accuracy.
A node-adaptive weighting mechanism should be adopted to satisfy each node's diverse needs for the propagation depth D, when constructing deep GNNs,
Guidelines 2:
5.3 How TO CONSTRUCT GNNS WITH LARGE D,?
Recently, lines of works have been proposed to support large D,, and many of them add skip connections between GNN layers motivated by ResNet (He et al.) 2016) and DenseNet (Huang (tt 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

---

Under review as a conference paper at ICLR 2022
al. 2020c) addresses small Dj 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 D,.
Guidelines 3: Adding skip connections between GNN layers is an effective way for GNN models to support large Dr.
ONE ALTERNATIVE SOLUTION
Under the guidance of the above guidelines, we propose scalable and flexible model termed Deep Graph Multi-Layee Perceptron (DGMLP), which contains a node-adaptive weighting mechanism for large D, and the residual connections for large D,. Following the decoupled framework, DGMLP first calculates the propagated features at different D, using the EP operation. Then novel node- adaptive weighting mechanism is proposed to combine the propagated features different Dp effectively. Finally, the combined feature is fed into MLP with added skip connections to support large D₁- The remainder of this section will introduce the adaptivee weighting mechanism and the skip connections adopted in DGMLP in detail.
6.1 NOAE-VDAPTIVE WEIGHTING MECHANISM
After generating the propagated features X (k) = A for propagation depth & ranges from to K using the EP operation, we further calculate the (k) parameterized by node v and propagation depth defined in Def. 3.1 Remember that smaller NSL..(k) means that the node embedding at propagation step k is more likely to forget the original node feature information and has higher risk of the over-smoothing issue. Thus, in this case, propagated feature propagation step x should be intuitively assigned with smaller weights. To restrain the weights between O and 1, the propagation weight w. (k(k) parameterized by node and propagation step is defined the softmax output of (NSL, N (1), NSL(())
(B)T
(k)
NSL.
Similar to Knowledge Distillation (Hinton et al.) 2015 Lan et al. 2018), the temperature adopted here to soften 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 different D, are combined using the weight w.,k) in Eq. 7 to
generate the combined feature x Σ wo(k))) By adaptively assigning different propagation
k=0
weights for different nodes, simply increase Dp the graph level and get more powerful node embeddings with personalized smoothing levels for each node.
6.2 SKIP CONNECTIONS
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:
(1+1) o (h." (1 (() h!)
(8)
where ( is the learnable parameter matrix, h (0)
R is the original combined node feature vector, and h!!) is the transformed node embeddings at the 1-th layer of the MLP with residual connections.
DGMLP EVALUATION
In this section, we conduct extensive experiments to evaluate our proposed DGMLP. We first introduce the utilized datasets and experiment setup. Then, compare DGMLP with state-of-th art baselines in predictive accuracy, scalability, and model depth. More experimental results about efficiency, graph sparsity, and interpretability of DGMLPP can be found in Appendix E
7

---

Under review as a conference paper at ICLR 2022
Table I: Test accuracy on the node classification task. "OOM" means "out of memory".
Methods
Coru
Citeseer
PubMed
Industry
ogbn-arxiv
ogbn-products
ogbn-paperst00M
GCN 81881..5
70.810.5
79.3:0.7
45,9=0.4
71.710.3
OOM
OOM
GraphSAGE
79.2=0.6
71.6+0.5
77.4+0.5
45.7=:0.6
71.5+0,3
78.34-0.2
64,8+0.4
JK-Net
81.8+0.5
70.7++0.7
78.8+00.7
47.2++0.3
72.2++0.2
0OM
00M
ResGCN
8122:0.5
70.8+0.4
78.6:006
45.8:10.5
72.620.4
OOM
OOM
APPNP
83.3+00.5
71.8+0.5
80.1+-0.2
46.7++0.6
72.0++0.3
OOM
0OM
AP-GCN
8344+0.3
71.3+00.5
79.74+0.3
46.9++0.7
71,9++02
OOM
0OM
DAGNN
84.4=0.5
73.3+
80.5+00.5
47.1=0.66
72.1+0.3
OOM
0OM
SGC
81.0+0.2
71.3+00.5
78.9++0.5
45.2++.3
71.2++0.
75.9+
63.2-+0.2
SIGN
82.1
72.4::0.8
79.5:10.5
46.3:10.5
71.910.1
76,8+0.2
64.2.10.2
SCGC
82.7.0.3
73.0+0.2
79,9+0.3
46.6:10.6
7184003
77.140.1
64.7.10.3
GBP
83.920.77
72.940.5
80.6:10.4
46,9
72.2400.2
77.740.2
65.2::0.3
DGMLP 84.6=0.6
03.4=005
81,2++0,6
47,6
72.8+00.2
78,5++0.22
65.7++0.2
7.1 EXPERIMENTAL SETTINGS
Datasets. We adopt the three popular citation network datasets (Cora, Citeseer, PubMed) (Sen et al. 2008). three large OGB datasets (ogbn-arxiv, ogbn- gebn-products, ogbn-papers1000 100M) (Hu et al. 2020). and one Industry dataset from industrial cooperative enterprise in our evaluation. Table Appendix D.I presents an overview of these seven datasets.
i
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., (018).
AP-GCN (Spinelli et 20220). DAGNN (Liu et al. 2020). SGC (Wu et al.
2019), SIGN (Frasca
et al. 2020). SCGC (Zhu & Koniusz 2021). and GBP (Chen et al. 2020bb.
The hyperparameter
details for our DGMLP and all the baseline methods can be found in Appendix
D.2
7.2 END-TO-END COMPARISON
The classification results on three citation networks are shown in Table We observe that DGMLP outperforms all the compared baseline methods. Notably, the predictive accuracy of DGMLP exceeds the one of current state-of-the-ar 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. is due to the fact that the disentanglement of EP and ET operations enables Dp 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
As shown in Table [ 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 D, and large D,.
7.3 TRAINING SCALABILITY
To test the scalability of DGMLP, we use the Frdös-Rényi graph (Erdos et al.) 1960) generator in the Python package NetworkX (Hagberg et al. 20088 generate artificial graphs of different sizes. The node sizes of the generated artificial graphs vary from 0.1 million to million, and the probability of an edge exists between two nodes set to 0.0001. We choose two representative methods GCN and APPNP as compared baselines. The total running time (including the pre prepprocssiing time) of training for 200 epochs and the GPU memory requirement are shown in Fig. 5(a) and Fig. [(b) respectively.
and
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 large graph of size I million, which is less than the running time of both GCN and APPNP on the graph of size 0.3 million. Fig.
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 I million, while the memory requirement of DGMLP is just over 3GB at the same graph size. It indicates that our proposed DGMLPP enjoys high scalability and high efficiency at the same time.
8

---

Under review as a conference paper at ICLR 2022
20
1000
DSMLE
17.1
Required Memory
GCN
APNN
Running Time (s)
6CU
16
3000
Speedup
10
10
10000
-3000
1000
5000
1.9
0
100K
300K
500K 1000K
0.25
0.50
0.75
1.00
Graph Size
Graph Size
x10
Figure Running time and GPU memory requirement comparison on different sizes of graphs
Test Accuracy
Test Accaracy
70
68
DACNN
DAGAN
66
SIGE
S/GC
DOMP
DGVIP
4 6 10
12 16
53
3
6
0
Propagation Depth D2
Number Transformation Depth
(a) fix D, change Dp
(b) fix D, change Dr
Figure 6: Test accuracy with different D, or Dr-
7.4 ANALYSIS OF MODEL. DEPTH
In this subsection, we conduct experiments to validate that our proposed DGMLP can support both large Dp and large D,. We choose SGC, DAGNN, and SC as baseline methods.
Firstly, we fix De to 3 and increase D, from 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, S²GC, and our DGMLP maintains high when D, becomes large. Moreover, DGMLP consistently outperforms all the baseline methods when D, is greater than 6. The superiority of our DGMLP over DAGNN and S2GC lies in that we adopt a node-adaptive combination mechanism satisfy the diverse needs of different nodes for propagation depth Dp.
Secondly, we fix Dp to 10 and increase D; from to 10. Fig. 6(b) shows that the predictive accuracy of all the baseline methods, including SGC, DAGNN, and S"GC decreases rapidly when D, 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 D, 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 maintains even when D, is large. To sum up, compared with other baseline methods, our DGMLP can consistently improve predictive accuracy with larger Dp or Dr, which validates our experimental analysis and guidelines in Sec. and
8 CONCLUSION
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, ie.. the model degradation issue happens much earlier than the over-smoothing issue as D, and D, 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 seven real-world graph datasets demonstrate that DGMLP outperforms state-of-the-an GNNs, and enjoys high scalability and efficiency at the same time.

---

Under review as a conference paper at ICLR 2022
9 REPRODUCIBILITY STATEMENT
The source code of DGMLP can be found in Anonymous Github (https:/ https://anooyaaan anonymous 4open sei Bance//DDMML--EE-
To ensure reproducibility, we have provided the overview datasets and baselines in Section and Appendix The detailed hyperparameter settings for our DGMLP can be found Appendix D.2 Please refer to "README.md" in the Github repository for more reproduction details.
REFERENCES
Joost Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani, and Khalil Sima an. Graph convolutional encoders for syntax-aware neural machine translation. arXiv: 2017.
arXiv preprint
Dominique Beaini, Saro Passaro, Vincent Létourneau, William Hamilton, Gabriele Corso, and Pietro Lió. Directional graph networks. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, pp. 748-758, 2021.
John Bradshaw, Matt J. Kusner, Brooks Paige, Marwin H. S. Segler, and José Miguel Hernández- Lobato. A generative model for electron paths. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Chen Cai and Yusu Wang. A note over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
Ben Chamberlain, James Rowbottom, Maria Gorinova, Michael M. Bronstein, Stefan Webb, and Emanuele Rossi. GRAND: graph neural diffusion. Proceedings of the 38th International Conference on Machine Learning, ICML. 2021, 18-24 July 2021, Virtual Event, pp. 1407-1418. 2021.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1438-3445, 2020a.
Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Scalable graph neural networks via bidirectional propagation. arXiv preprint arXiv:2010. 15421, 2020b.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1733 PMLR, 2020c.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 1021, 2021.
Hanjun Dai, Chengtao Li, Connor W. Coley, Bo Dai, and Le Song. Retrosynthesis prediction with conditional graph logic network. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 8870-8880, 2019.
Kien Do. Truyen Tran, and Svetha Venkatesh. Graph transformation policy network for chemical reaction prediction. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 750-760, 2019.
Paul Erdos, Alfréd Rényi, et On the evolution of random graphs. Publ. Math. Inst. Hung, Acad. Sci, 17-60, 1960.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-426, 2019.
10

---

Under review as a conference paper at ICLR 2022
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in Neural Information Processing Systems, 33, 2020.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. 1114.,11188,, 2020.
Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. arXiv preprint arXiv: 2017.
Jonathan Godwin, Michael Schaarschmidt, Alexander Gaunt, Alvaro Sanchez- Gonzalz, Yulia Rubanova, Petar Veličković, James Kirkpatrick, and Peter Battaglia. Very deep graph neural networks via noise regularisation. arXiv preprint arXiv: (rXiv:2066007977 2021.
Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab. (LANL. Los Alamos, NM (United States), 2008.
Will 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 the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yong-Dong Zhang, and Meng Wang. Lightenn: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference research and development Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pp. 639-648, 2020.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint ar 1rXvv:1503.0253 2015.
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard TB Ma. Hongzhi Chen, and Sing-Chang Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference Learning Representations, 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0065: 2020.
Chao Huang, Huance Xu, Yong Xu, Peng Dai, Lianghao Xia, Mengyin Lu, Liefeng Bo, Hao Xing, Xiaoping Lai, and Yanfang Ye. Knowledge-aware coupled graph neural network for social recommendation. In AAAI Conference Artificial Intelligence (AAA!), 2021.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Thomas N Kipf and Max Welling, Semi- Semi-supervisee supervised classification with graph convolutional networks. arXiv preprint arXiv: le0o:::690090000 2016
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997 2018.
Michihiro Kuramochi and George Karypis. Finding frequent patterns in a large sparse graph. Data mining and knowledge discovery, 11(3):443-71, 2005.
Xu Lan, Xiatian Zhu, and Shaogang Gong. Knowledge distillation by on-the-fly native ensemble. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 7528 -5338, 2018
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9267-9276, 2019.
11

---

Under review as a conference paper at ICLR 2022
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- superviiee learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Yang Li, Yu Shen, Wentao Zhang, Yuanwei Chen, Huaijun Jiang, Mingchao Liu, Jiawei Jiang, Jinyang Gao, Wentao Wu, Zhi Yang, et al. Openbox: A generalized black-box optimization service. arXiv preprint XXiv:2166.00421, 2021.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 338-348, 2020.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-44) 2001.
Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering gen: Overcoming oversmoothness in graph convolutional networks. arXiv preprint arXiv:2003.084/1 2020.
Federico Monti, Michael M Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. arXiv preprint arXiv:1704.06803, 2017.
Hoang NT and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters.
CoRR, 509500, 2019.
Siyuan Qi. Wenguan Wang, Baoxiong Jia, Jianbing Shen, and Song-Chun Zhu. Learning human- object interactions by graph parsing neural networks. In Proceedings of the European Conference Computer Vision (ECCV), pp. 401 011-417,220 2018
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Modeling influence locality in large social networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD' 18), 2018
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint 1907 2019.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. SIGN: scalable inception graph neural networks. CoRR, abs/2004.11198, 2020.
Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. Superglue: Learning feature matching with graph neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 4938-4947, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Mag., 29(3):93-106 2008.
Lei Shi, Yifan Zhang, Jian Cheng, and Hanqing Lu. Skeleton- based action recognition with directed graph neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 7912-7921, 2019.
Indro Spinelli, Simone Scardapane, and Aurelio Uncini. Adaptive propagation graph convolutional network. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Shikhar Vashishth, Naganand Yadati, and Partha Talukdar. Graph-based deep learning in natural language processing. In Proceedings of the 7th ACM IKDD CoDS and 25th COMAD, pp. 371-372. 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2022
Lingfei Wu, Yu Chen, Kai Shen, Xiaojie Guo, Hanning Gao, Shucheng Li, Jian Pei, and Bo Long. Graph neural networks for natural language processing: A survey. arXiv preprint (XXi:2200606099) 2021.
Shiwen Wu, Fei Sun, Wentao Zhang, and Bin Cui. Graph neural networks in recommender systems: a survey, arXiv preprint arXiv:2011.0222 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning graphs with jumping knowledge networks, In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018.
Yujum Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06400 2021.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting smoosshgg in deep gens. arXiv preprint arXiv:2003.13663; 2020.
Ruiping Yin, Kan Li, Guangquan Zhang, and Jie Lu. A deeper graph neural network for recommender systems. Knowledge- Bhooledge-Based Based Systems, 185:10500 2019.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Deep graph neural networks with shallow subgraph samplers. arXiv preprint arXiv:2012.0138/ 2020a.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.ner, 2020b.
Wentao Zhang, Yuezihan Jiang, Yang Li, Zeang Sheng, Yu Shen, Xupeng Miao, Liang Wang, Zhi Yang, and Bin Cui. Rod: Reception-aware online distillation for sparse graphs. arXiv preprint 10X 1189, 2021a.
Wentao Zhang, Yu Shen, Zheyu Lin, Yang Li, Xiaosen Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. Gmlp: Building scalable and flexible graph neural networks with masture- passing. arXiv preprint arXiv:2 09880, 2021b.
Xiaotong Zhang, Han Liu, Qimai Li, and Xiao Ming Wu. Attributed graph clustering via adaptive graph convolution. In 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, pp. 4327-4333. International Joint Conferences on Artificial Intelligence, 2019.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 2020.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. Distdgl: distributed graph neural network training for billion-scale graphs. In 2020 JEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3), pp. 36 36-44. IEEE, 2020.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. arXiv preprint arXiv:2006.06972 2020a.
Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understanding and resolving performance degradation in graph convolutional networks. arXiv preprint wwx::200660070000 2020b.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2021.
13

---

Under review as a conference paper at ICLR 2022
A DEEPER ANALYSIS OF GNN ARCHITECTURE
A.1 CONVOLUTION PATTERN
According 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 itt 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 set of filters to propagate the information, which is further followed by nonlinear transformations. As result, EP and ET operations are inherently intertwined in this pattern, i.e., each EP operation requires 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 ct al. 2019) are the representative methods of this category.
Besides the strict restriction that D, = D,. Table 2 shows EPT-based and EPT-SC-based GNNs also suffer from low scalability and low efficiency. On the one hand, deeper structure has more parameters, resulting in greater computation costs. On the other hand, the number of nodes within each node's 's neighborhood grows exponentially with the increase of model depth in typical graphs, incurring significant memory requirement in 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 lis in the EP operation rather than the ET operation inside the graph convolution. Therefore, some disentangled GNNs propose separate the ET operation from the EPT scheme. They 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 DTP- based 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 simple model composed of multiple ET operations (Zhang jet al. (02Tb). 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, based GNNs can support large propagation depth Dp- Besides, DTP-based GNNs do not restrict D, = D,, 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.
A.2 DGMLP VERSUS EXISTING METHODS
EPT-based GNNs. GNNs with the convolution pattern of EPT assume that D, = Dr. However, as discussed in Sec. 1, the optimal Dp and Dr are highly related to graph sparsity and graph size. For example, it is better to assign large Dp and small D. for better performance on a small graph with sparse edges. Due to the model degradation issue, current EPT-based GNNs usually have both small D, and Dr, owing to the infiexible restriction that D, D.. Besides, the EPT-based GNNs also face the problem of low scalability and low efficiency. For example, GCN has the high time complexity of ODD,Md + Dd) for the need to repeatedly perform recursive neighborhood expansion each training iteration to compute the hidden representations of each node. This process is unscalable due to the high memory and computation costs on single machine and high communication costs in
14

---

Under review as a conference paper at ICLR 2022
Table 2: Algorithm analysis. We denote N, Mr. M and d as the number of nodes, the number of labeled nodes, edges and feature dimensions respectively. P is the EP operation and T is the ET operation. "SC" means "Skip Connection", and refers to the number of sampled nodes in GraphSAGE.
Algorithm
Convolution Type
Pattern
Disentangled
Large D,
Large D,
Complexity
GCN (Kipf Welline
2016
EPT
PT..PP. PT
X
X
O(D,Md+ D.Ndf)
GraphSAGE AOSSAGGEEaaanng (llamllin
2017
EPT
PT
OIK 7. Na.)
Je-Net (X al. 2013
EPT-SC
PT... PT
X
X
U.D,Md + D
ResGCN
EPT-SC
PT...
Od D,NdP)
APPNP Klienera ni 2018
DTP
T...P... TP..P
O(D,Md D,N.E)
AP.GCN Sppinelli
T.PPP
OLD,Md D,NdP)
DAGNN MAGNNTLLan Lai 201203
DTP
TP..PP
O DDD.M D,N.E)
SGC Wo (019)
DPT
P... PT...
O,D,N, OiD
SIGN Traca
2020
DPT
P... PT.--T
Rossi A
2020
DPT
P... PT..-
GBP
Chen
20200
DPT
P... TT.--
OYD,N OID,N.a
DGMLP
DPT
distributed environments. Compared with EPT-based GNNs, DGMLP is more flexible in assigning different D, and D, and enjoys better efficiency, scalability, and lower memory requirement.
E.T-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 D;. However, Fig. 3(b shows that the test accuracy degrades with deeper architecture due to the over-smoothing issuc introduced by large Dp large graph without the graph sparsity issue requires large D, and small GNNs like ResGCN cannot satisfy such requirements since they simply restrict Dp = D.. 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.
Dp- However,
based GNNs. Compared with GNNs with the convolution pattern of EPT and EPT-SC, DTP- based GNNs disentangle the propagation and the transformation operation, thus support flexible combinations Dp and D,. As shown in Fig. 2(b) and Fig. 2[c) over-smoothing may have less impact the performance degradation compared with model degradation, and the test accuracy will not decrease rapidly with the larger over wver-mmothhng level. Therefore, lots DTP-based GNNs own large D, and small D, and claim that they can perform well with the deeper architecture. However, they ignore the transformation depth D, in their design. As shown in Fig. 7 the test accuracy degrades rapidly we increase the transformation depth D, of DAGNN. Correspondingly, it is hard for DTP-based GNNs to support large graphs with limited transformation depth D, 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 DPT- based GNNs 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 D, with the help of residual connections.
B WHEN WE NEED DEEP GNN ARCHITECTURES?
When we need deep EP? We review the related works and researches concerning D,'s importance and then investigate experimentally when it is appropriate to enlarge D, in GNNs. GNNs mainly benefit from performing EP operations over neighborhoods. Stacking more EP operations will expand node's 's receptive field and help it to gain more deep struetural information. However, if the graph dense, increasing D, may lead to over-smoothing, which results from the rapid expansion of the receptive field.
15

---

Under review as a conference paper at ICLR 2022
Table 3: Replacing the logistic regression in SGC with ResMLP. The test accuracy the corresponding model on small graph Cora and large graph ogbn-arxiv when the MLP depth De changes from to
Dataset
1
2
3
4
5
6
7
Cora
80.9
81.7
81.5
81.1
80.7
80.5
80.2
ogbn-arxiv
70.1
70.2
71.2
71.4
71.4
71.6
71.3
Table 4: Test accuracy under different edge sparsity.
Datasets
M N²
2
4
6
8
12
16
20
Cora
0.7%e
59.8
59.6
57.9
57.3
56.5
51.8
47.1
PubMed
0.1%o
78.5
78.9
77.8
77.6
77.3
76.6
75.8
Table 5: Test accuracy under different label missing rates.
Datasets
Labels/class
2
4
6
8
12
16
20
20
81.5
81.3
80.8
80.1
80.0
79.5
78.8
Cora
1
53.8
59.2
62.9
64.3
66.5
66.7
65.6
20
78.5
78.9
77.8
77.6
77.3
76.6
75.8
PubMed
1
61.2
65.9
67.4
67.5
67.7
69.0
68.3
Generally, most real-world graphs exhibit sparsity in three aspects: edges, labels, and features. We define edge sparsity, label sparsity, and feature sparsity follows: (1) Edge sparsity: nodes in real-world graphs usually have skewed degree distribution, and many nodes are rarely connected (Kuramochi & Karypis 2005). (2) Label sparsity: only 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 features, i.e., the new users or products in 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 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 to 20 on Cora and PubMed and report the test accuracy under each setting. The experimental results Fig. show that the optimal D, 4 for PubMed and for Cora, meaning that the sparser graph requires 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 fix one labeled node per class Cora and PubMed and keep the same setting with the edge sparsity experiment. can be seen that the classification accuracy increases Dr ascends from 2 to 16. However, if we increase the label rate 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 D,. Finally, in T we report the test accuracy under the feature sparsity setting where 50% node features are randomly dropped from Cora and PubMed datasets. The result consistent with the former two experiments that graphs with higher feature sparsity levels require larger Dr- When we need deep ET? Generally, stacking multiple ET operations can better fit and learn the data distribution. However, we observe that the optimal D, 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 complexity grows at squared rate, which requires larger
16

---

Under review as a conference paper at ICLR 2022
Table 6: Test accuracy under different feature missing rates.
Datasets
Feature missing %
4
6
8
12
16
20
0%
81.5
81.3
80.8
80.1
80.0
79.5
78.8
Cora
50%
75.4
77.7
78.5
79.5
79.4
78.9
78.0
0%
78.5
78.9
77.8
77.6
77.3
76.6
75.8
PubMed
50%
60.6
65.1
66.3
66.7
68.7
69.2
68.7
100
6,0006
80
2agg 62M BLT
Prediction Acoracy
Tige G2M 73.2
80
Tes. Accuracy
60
Gadeent First
b000
1
2 Number of Transformation Depth D.
5
20
16 32
128
(0000
Number of Propagation Depth
Epoch
(a) Training and test accuracy both (b) Fixing Dt Dp degrades (c) First layer gradient comparison drop sharply when model grows the performance badly when Dp of GCN with different layers on becomes large Cora dataset. Cora dataset.
deep.
Figure 7: Overfitting, entanglement, and gradient vanishing are not the major cause for the performance degradation deep GNNs.
Dj to extract meaningful information. We prove this insight by experimentally examining how Dj influences the node classification performance Cora and ogbn-arxiv datasets. Concretely, replace the logistic regression SGC with "MLP+Res and increase D, from I to 7. SableB]showe that the accuracy ogbn-arxiv increases as Dr ascends from 1 to 6. However, D. 2 is enough for the small graph Cora. Therefore, larger graphs need larger D, for high-quality node embeddings.
C MORE MISLEADING EXPLANATIONS
C.I OVER-RITTING
Some works (Rong et al. 2019 Li ct 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 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 Fig. ((a)
Finding. Both the training and test accuracy drop quickly when the model grows deep. However, over-fitting assumes that over perameeeetri 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.
C.2 ENTANGLEMENT
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 EP and ET operations in
convolutional layers. For example, DAGNN claims that the entanglement GCN is the true reason it only supports shallow architectures. To investigate this statement, vary the transformation depth D, in ResGCN, DenseGCN, and vanilla GCN and report their test accuracy on the PubMed dataset. The experimental results are shown in Fig. 3(b)
17

---

Under review as a conference paper at ICLR 2022
Finding 1. Although ResGCN and DenseGCN have entangled designs, when D, and D, 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 D, = 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 202 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 D,. their performance will also degrade badly. To validate this, we run DAGNN in two different settings: the first controls D, 2 and increases Dp. the second controls D. = D, and increases Dp- The test accuracy under these two settings the PubMed dataset is shown in Fig. 7(b)
The disentangled DAGNN also experiences huge performance degradation when the model owns large D.. If the entanglement dominates the performance degradation of deep GNNs, DAGNN should be able also go deep on D.. However, if we individually increase D, of DAGNN, the sharp performance decline still exists.
Finding 2.
Implication. The major limitation of deep GNNs is the model degradation issue introduced by large Dr rather than the entanglement of EP and ET operation.
C.3 GRADIENT VANISHING/EXPLOSION
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 not the leading cause of performance degradation in deep GNNs.
C.4 DISENTANGLED CONVOLUTION
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 al.) 2020) and find that the decoupling strategy makes the propagation and the transformation operations independent, thus Dp and D, are not forced to be the same. Therefore, disentangled GNNs generally fix D, and increase Dp to capture deeper graph structural information. Here we select two disentangled GNNs, S²GC and Grand, which state that they support deep architectures. Their performance of individually increasing Dp and D, 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 D, 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 D,,, so that the model degradation introduced by large D, be avoided.
18

---

Under review as a conference paper at ICLR 2022
Table 7: Overview of datasets and task types.
#Edges
ValTin/Val/Testt
Description
Corn
2,708
1.433
5.429
140V500/1 DOO
citation network
Citeseer
3,327
3,703
4,732
1205500I 1000
citation network
Pubmed
44,338
6EVSUUU1
ogha-andvv
109,
1,166,333
91K/80K44TX
network
ogbn-products
2,449,029
100
61,859,140
47
(96K/49K/22220 204K
citation network
10he-pupers100M
111,059,556
128
1,1558858722
172
1,207K//1 25 K/21 4K
citation network
Industry
1,000,000
1,43,3822
SK/10KF30K
short-form video netwook
48
XGNLP
3
K-Net
AP-ECN
112 Res
Test Acarssy
SOGN
APPNP
CCN
10'
10'
10
Relathv Training Time
Figure 8: Performance along with training time on the Industry dataset.
D EXPERIMENTAL DETAILS
D.1 DATASET DETAILS
The details of the adopted seven datasets can be found in Table 7
D.2 HYPERPARAMETER DETAILS
For the three small citation networks, we adopt a simple logistic regression as the classifier. The propagation depth D, is set to 20 for Cora and PubMed, and 15 for Citeseer. The learning rate is set to 0, and the dropout rate is obtained from a search range 0. to 0.5 with step 0.1. Residual connections are not used 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 D, is respectively 20 and 12 for them. Residual connections used for these four large datasets. Besides, the temperature is set to as default it is not specified, and the learning rate and the dropout rate
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,
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 al. 2021 or follow the settings in their original paper.
E ADDITIONAL EXPERIMENTS
E. PERFORMANCE-EFFICIN ANALYSIS
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, illlstrates 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 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 DGMLP, exceeding SGC by
19

---

Under review as a conference paper at ICLR 2022
80
Test Acturasy
70
Test Accuracy
Test Accuracy
70
75
60
5GC SIGH
800
S1GN
8100
80
5700
GBP
0BP
DOMPP
0CKLP
DOVLP
0.25
0.50
0.75
1.00
10
20
0.25
0.50
0.75
1.00
Percent Remaining Edges
Training Nodes per Class
Percent of Remaining Node Features
(a) Edge Sparsity
(b) Label Sparsity
(c) Feature Sparsity
Figure 9: Test accuracy on PubMed dataset under different levels of feature, edge and label sparsity.
Node Smoothing Level
0.8
DGMLP
0.6
0.2
0.0
50
100
Number Propagation Depth D₁
Figure 10: Graph Smoothing Level comparison between SGC and our proposed DGMLP.
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 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)) it clear to that the performance of GBP, SCGC, and our DGMLP is significantly better than SIGN and SGC. Further, DGMLP always has higher test accuracy than GBP and S²G SIGN and SGC both have 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.
edges in the original graph strengthen the edge sparsity
Label Sparsity. In this setting, we vary the training nodes per class from I to 20 and report the test accuracy each method. The experimental results in Fig. 9bb show that the test accuracy of all the compared methods increases 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()) illustrate that our proposed DGMLP has great anti- interference ability when faced with feature sparsity as its performance drops only a little even there only 10% node features available.
20

---

Under review as a conference paper at ICLR 2022
E.3 INTERPRETABILITY
In this subsection, we empirically explain why our proposed DGMLP is more robust to the over- smoothing 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 evaluate the graph smoothness.
The results in Fig. 10 show that the GSL of both SGC and DGMLP decreases as D, increases. However, the descending speed of SGC is much quicker than DGMLP, especially when Dp changes from 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 more robust the overssmoothing issue introduced by large Dy. 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.
21


Reviews:
[{"review_id": "qLkMc8YaZ1N", "reviewer": "Reviewer_ddQY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "**Strengths:**\n\n(1) The concepts of embedding propagation and transformation depths are formally defined to study their impacts on deep GNNs.\n(2) The series of empirical studies on these two depths are given.\n(3) The paper is well organized.\n\n\n**Weakness:**\n\n(1) The empirical guidelines 1-3, and the experimental analysis (in Section 4) are not novel at all to the community of deep GNNs. Specifically, the decoupling of embedding propagation and transformation, adaptive weighting, and skip connection have already been studied in literature. I know the authors derive these guidelines based on formulating the concepts of D_p & D_t and conducting the extensive experiments to get Findings 1. However, these knowledges have been implicitly explained in prior efforts. For example, the decoupling of EP and ET was proposed in DAGNN [1], based on the empirical study of SGC similar to the one in this paper. To avoid the harmful impact of embedding transformation, the identity mapping is incorporated in GCNII [4] to avoid the overly feature change. In other word, the dominant influence of embedding transformation in deep GNNs is not a news.\n\n(2) The proposed model, named DGMLP, is incremental comparing with the existing works, including DAGNN, SGC, JK-Net, etc. The only difference is the usage of skip connection in the final MLP module. \n\n(3) Although the experimental results show the superiority of DGMLP, most of the important baselines are missing in Table 1, which easily leads to misunderstanding. For example, GCNII has good or comparable performances in Cora, Citeseer, and ogbn-arxiv. In obgn-products, SAGN [5] and DeeperGCN [6] with the similar architecture to the proposed model shows outperforming results. Furthermore, SAGN also has better results in ogbn-100M. But all these important baselines are missing.\n\n(4) Some of the claims made in this paper is not correct. See below for the detailed comments.\n\n\n**Questions:**\n(1) Under Eq. (4), it is stated that ``Under this scenario, the neighborhood information is fully corrupted, resulting in catastrophic node classification accuracy.” I’m concerning on the correctness of this statement: why neighborhood information will be corrupted if the neighborhood influence is determined by the degree? The specific neighbor features could still distinguish them. As shown in Figure 4 of reference [1], by stacking many EP layers, the node classification accuracy is still good enough, which empirically demonstrates that neighbor information is not corrupted. \n\n(2) The claim of ``As the over-smoothing issue is only introduced by the EP operation rather than the ET operation” below Eq. (4) is not correct. As theoretically demonstrated in references [2,3], the over-smoothing issue is also correlated to the singular values of trainable weights and non-linear activations involved in ET. \n\n(3) For the example study of Figure 2(c), it is unclear how to formulate GCN model with D_t=2 and the adjacency matrix powered by D_p/2. Could you illustrate more with the formal expression or model figure?\n\n(4) In Section 4.2, please formally define the residual connection and dense connection used in the empirical study.\n\n(5) The guideline 2 seems not novel at all. It is well-known that the optimal convolution depths for the diverse nodes are different. For example, DAGNN in [1] applies attention module to learn the optimal combination weight for each specific node.\n\n[1] Liu, Meng, Hongyang Gao, and Shuiwang Ji. \"Towards deeper graph neural networks.\" Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020.\n\n[2] Cai, Chen, and Yusu Wang. \"A note on over-smoothing for graph neural networks.\" arXiv preprint arXiv:2006.13318 (2020).\n\n[3] Oono, Kenta, and Taiji Suzuki. \"Graph neural networks exponentially lose expressive power for node classification.\" arXiv preprint arXiv:1905.10947 (2019).\n\n[4] Chen, Ming, et al. \"Simple and deep graph convolutional networks.\" International Conference on Machine Learning. PMLR, 2020.\n\n[5] Sun, Chuxiong, and Guoshi Wu. \"Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training.\" arXiv preprint arXiv:2104.09376 (2021).\n\n[6] Li, Guohao, et al. \"Deepergcn: All you need to train deeper gcns.\" arXiv preprint arXiv:2006.07739 (2020).", "summary_of_the_paper": "This paper points out the dominant influence on deep GNNs, i.e., the embedding transformation, with careful and extensive studies. Based on these studies, several guidelines are proposed to design deep model named DGMLP. ", "summary_of_the_review": "This paper formally define the concepts of embedding propagation and transformation depths, and distinguish their impacts on the deep GNNs. Based on the empirical studies, some well-known guidelines are proposed to design deep GNNs. \n\nHowever, I cannot find much novelty from this paper, which seems to ensemble the existing knowledges. Some of important baselines are missing to validate the effectiveness of the proposed methods. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "ZZkHkhXAYDs", "reviewer": "Reviewer_tpnS", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "The definitions of Node Smoothing Level and Graph Smoothing Level compare the representations of the same node across different EP steps. However, the oversmoothing problem is across nodes. Considering the deviations, the performance of DGMLP appears to be comparable to the state-of-the-art. It is claimed that DGMLP can support large transformation depth D_t. But Fig6 (b) only shows a very stable accuracy as D_t increases. It would be more convincing if the performance of DGMLP improves with a larger D_t. Otherwise, why bother to increase D_t? Larger D_t means more parameters, and hence may need to train models longer (and with better training settings). Is it possible that large D_t leads to undertrain of GNN? The proposed node-adaptive weighting mechanism is interesting. It could helpful to see experiments that validate the importance of the node-adaptive weighting mechanism. ", "summary_of_the_paper": "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.", "summary_of_the_review": "The experiments, which compare various GNNs, provide useful information. The proposed DGMLP contains interesting ideas. However, experimental results are mixed and do not clearly support all claims made in this manuscript. The proposed smoothing level metrics do not measure smoothing across nodes.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WTJaVrtdSt-", "reviewer": "Reviewer_4Jnf", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "(+) The paper is well-organized and easy to follow. \n\n(+) 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). I enjoy reading the design of the analysis.\n\nConcerns:\n\n* The authors claim model degradation is the main cause of performance degradation of deep GNNs. However, what is model degradation is not defined formally.\n\n* It seems the proposed Node Smoothing Level is a measure of **smoothness** instead of **over-smoothness**. Claiming over-smoothing is not a major issue using Node Smoothing Level is not very well-justified. I think a better metric should be used. I recommend the authors check Group Distance Ratio and Instance Information Gain proposed in [1].\n\n* Why is the essential difference between the proposed “ResGCN” and “DenseGCN” in Figure 3 (b) and “ResGCN” and “DenseGCN” in [2].\n\n* What is the difference between the findings of adding skip connections to GNNs in [2] [3] and the findings in Section 5.3? This should be discussed.\n\n* It is unclear how the node-adaptive combination mechanism and residual connections between ET operations help with training deep GNNs. An ablation study needs to be carried out.\n\n* What is the reason that the performance of DGMLP on ogbn-product is far from the leading methods on the OGB leaderboard?\n\n* Why is the performance of baseline SIGN [4] is lower than the originally reported results (0.6568 ± 0.0006) on the leaderboard?\n\n* What are the benefits of disentangled graph convolution over entangled graph convolution rather than scalability?\n\n[1] Zhou, Kaixiong, et al. \"Towards Deeper Graph Neural Networks with Differentiable Group Normalization.\" NeurIPS 2020.\n\n[2] Li, Guohao, et al. \"Deepgcns: Can gcns go as deep as cnns?.\" ICCV 2019.\n\n[3] Li, Guohao, et al. \"Deepergcn: All you need to train deeper gcns.\" arXiv 2020.\n\n[4] Frasca, Fabrizio, et al. \"SIGN: Scalable Inception Graph Neural Networks.\" arXiv 2020.", "summary_of_the_paper": "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.", "summary_of_the_review": "(+) The systematic study of training deep GNNs of this work is interesting.\n\n(-) Some claims are not well-justified. Some related works are not discussed properly. Alations need to be done for the proposed methods. The performance of DGMLP is not very strong.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5ZQa2VZWTKt", "reviewer": "Reviewer_QtrD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The exploration of hyper-parameters for this problem is well founded, especially given the many different architectures that have been proposed.  The paper characterizes this through two primary parameters, Dp and Dt, and compares the DGMLP with varying values.  It isn’t clear why the authors don’t refer to these as hyper-parameters (except buried in the appendix). Perhaps it is not surprising that various papers have shown that the unentangled approach can outperform the entangled one.\n\nThe main body of the paper seems repetitive at times, stating repeatedly the basic points about the tradeoffs with Dp and Dt.  In the reviewers opinion, the meaningful portions of the paper are in the appendices, especially A and B.  It isn’t clear why these don’t make up the major portion of the main paper.  It seems that the paper spends a large amount of space with discussion and generality, often spending too much effort on criticism.  \n\nThe results show run-time and GPU memory versus graph size, and the DGMLP has good scaling properties.  \n\nThe node-adaptive weighting mechanism (Section 6.1) is interesting.  However, the influence here wasn’t entirely clear.\n\nThe paper would be significantly improved with a statement of the DGMLP in some kind of Table or Algorithm statement.\n\nThe DGMLP is able to achieve state of the art results compared with other algorithms.  So, the value here is the flexibility of the DGMLP, and also perhaps complexity reduction and scalability. It wasn’t entirely clear what is the overall complexity in comparison with other algorithms, especially with respect to choice of the hyper-parameters.  Perhaps the authors could add some further complexity results that include the cost of hyper-parameter exploration with the various algorithms to make this clear to the reader. \n", "summary_of_the_paper": "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.\n\n", "summary_of_the_review": "The theme of the paper is “Hyper-Parameter Selection and a Modified GNN for Semi-Supervised Node Classification”.  Perhaps that’s a better title.  \n\nOverall the paper builds on the many other GNN works for this problem, incorporates the best known practices, and provides a flexible approach to achieving the state of the art results when compared to other algorithms.  However, the presentation could be significantly strengthened as outlined in the Main Review.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies why existing deep GCNs suffer from poor performance and propose DGMLP to improve over existing GCNs. However, the reviewers think there are still many unjustified claims and the paper. Further, several reviewers question about the novelty of the proposed method, which seems to be a combination of existing approaches. 

I suggest the authors to revise the paper by defining terms like model degradation and smoothness mathematically and try to justify each claim (e.g., the effect of disentangling) with solid experiments. These will significantly improve the analysis part and make the conclusions stronger.
Decision: Reject