Depth Scaling in Graph Neural Networks: Understanding the Flat Curve Behavior
Authors: Diana Gomes
Kyriakos Efthymiadis
Ann Nowe
Peter Vrancx
Venue: Accepted by TMLR ()

Abstract: Training deep Graph Neural Networks (GNNs) has proved to be a challenging task. A key goal of many new GNN architectures is to enable the depth scaling seen in other types of deep learning models. However, unlike deep learning methods in other domains,  deep GNNs do not show significant performance boosts when compared to their shallow counterparts (resulting in a flat curve of performance over depth). In this work, we investigate some of the reasons why this goal of depth still eludes GNN researchers. We also question the effectiveness of current methods to train deep GNNs and show evidence of different types of pathological behavior in these networks. Our results suggest that current approaches hide the problems with deep GNNs rather than solve them, as current deep GNNs are only as discriminative as their respective shallow versions.

Published in Transactions on Machine Learning Research (04/2024)
Depth Scaling in Graph Neural Networks: Understanding the Flat Curve Behavior
Diana Gomes
diona.gomes@immc..u
Interuniversity Microelectronics Centre (IMEC), Belgium
Vrije Universiteit Brussel (VUB), Belgium
Kyriakos Efthymiadis
Vrije Universiteit Brussel (VUB), Belgium
Ann Nowe
ann.nowee@uub.bb
Vrije Universiteit Brussel (VUB), Belgium
Peter Vranex
peter.oraner@immen
Interuninersity Microelectronicss Centre (IMEC), Belgium
Vrije Universiteit Brussel (VUB), Belgium
Reviewed on OpenReview: https: // openreview. net/ for id= fdyHzoCTT8g
Abstract
Training deep Graph Neural Networks (GNNs) has proved to be challenging task. A key goal of many new GNN architectures is to enable the depth scaling seen in other types of deep learning models. However, unlike deep learning methods other domains, deep GNNs do not show significant performance boosts when compared to their shallow counterparts (resulting a flat curve of performance over depth). In this work, we investigate some of the reasons why this goal of depth still eludes GNN researchers. We also question the effectiveness of current methods to train deep GNNs and show evidence of different types of pathological behavior in these networks. Our results suggest that current approaches hide the problems with deep GNNs rather than solve them, as current deep GNNs are only as discriminative as their respective shallow versions.
1 Introduction
Graph Neural Networks (GNNs) have been extensively used for graph representation learning in several different domains, such as social sciences, drug design, biology and particle physics. Since the proposi- tion of Graph Convolutional Networks (GCNs) (Kipf & Welling 2017), new network architectures have emerged aiming to improve expressivity (Velčković et al. 2018 Xu et al. 2018a), decrease computational
cost. (Hamilton et al. 2017): handle graph oversmoothing (Chen et al. 2020 Zhao & Akoglu 2020 and
overcome harmful node-level hetcrophily (Yan et al., 2022 Pei et al. 2020 Bodnar et al., 2022].
Deep GNNs show very different trends from other deep learning methods. Unlike conventional neural net-
works used in other domains (e.g. CNNs in computer vision), for which increasing the number of stacked layers is generally associated with greater expressive power and improved performance, the basic versions of GNNs (such as GCN (Kipf & Welling 2017) or SGC (Wu et al.) (2019)) do not benefit from depth; on the contrary, increasing depth leads to a significant drop of performance (see GCN Figure D This trend is generally explained by the oversmoothing problem phenomenon in which all nodes in a graph become indistinguishable as a consequence of multiple aggregations of node representations through messago-pan paassagg operations.

---

Published in Transactions on Machine Learning Research (04/2024)
Corb
Creeseer
Comell
Chameleon
Acuric3
32
64
30
ayers
Jayyers
layors
layers
Figure 1: Examples of the flat curve behavior (performance stagnation over depth in GNNs). Results for GCNIT, GGCN, GPRGNN and GCN were extracted from Yan et al. (2022). GCN+InilRRs refers to results of this work (for a = 0.5).
At the same time, the motivation to train deep GNNs still stands, as a k-layer GNN could potentially capture useful long-range dependencies by enabling the aggregation of relevant information k-hops away. This observation has led to the proposition of more complex network architectures, which do enable to train deep networks to solve challenging lasks with adequate performance (e.g., GCN with initial residual GGatteiger et al. 2018; Chen et al. 2020 Jaiswal et al. 2022), GCNII (Chen et al. 2020), GGCN (Yan
ctt al.
2022), GPRGNN (Chien et al. 2021), G² (Rusch et al., 2023b)). However, these deep architectures oflen lead to equivalent or even deteriorated performance when compared to their shallow counterparts, as
Figure clearly shows. This opens unresolved questions regarding the pursuit of depth in GNNs.
Previous works have elaborated on the theoretical role of depth, but their conclusions often lack further empirical validation, and it is even possible to find contradictory arguments regarding the potential benefits Cong et al. 2021). Poor GNN performance due to apparent oversmoothing or loss of expressivity in deeper GNNs has also been investigated in some works (Yan et al.) 2022 Li et al.) 2018 Balcilar et al. 2020 Keriven 2022 Oono & Suzuki 2019), while other authors argued that is not oversmoothing, but rather the training difficulty of GNNs that leads to poor rosults (Luan et al., 2023 Cong ct al. 2021). This scenario evidences that the way that GNNs Iearn still poorly understood, and dedicated empirical analyses on learning behaviour and depth scaling are in demand.
of depth following theoretical reasoning (Keriven 2022
In this work, we aim to explain the plateau of performance over depth illustrated in Figure 1 by conducting empirical study using cleven of the most common benchmark datasets for cemi-supervised node classification tasks. We leverage GCN with initial residual (GCN+Init Res) as a case study, as these nelworks exhibit an analogous behavior to that of the remaining (more complex) architectures depicted in Figure [ in terms of performance over depth (the flat curve). Our experiments show the extent to which this behavior manifests, and are followed by the study of the intermediate hidden node representations of several ttate-of-the-art deep networks to provide justification for the observed phenomenon. These analyses disclose relevant empirical insights on how deep GNNs learn and whether how they can actually leverage depth. We further discuss how these insights generalize between different deep architectures, and propose a depth evaluation protocol that should be adopted by other researchers to dismiss the possibility of pathological behavior in their networks. Our main contributions are:
Bringing forward for the first time, to the best of our knowledge the discussion of how current methods are hiding the problems with deep GNNs rather than solving them, as these are only as discriminative their shallow counterparts;
Showing evidence of different types of potholgicaal behavior in current deep GNN architectures, which manifest as redundant hidden embedding representations and seemingly useless/noff /oisy layers;
A protocol to identify pathological behavior when scaling GNNs with respect to depth (code publicly available
2

---

Published in Transactions on Machine Learning Research (04/2024)
The manuscript is organized in five sections. Section introduces some fundamental concepts behind deep GNNs 2.1 and proceeds to compare state-of-the-art approaches (..2 and present case study on the discriminative power of deep networks [.3). Section 3 introduces previous methods for evaluating depth scaling in GNNs and other deep networks 43.1 proposes depth evaluation protocol that overcomes some limitations of the previous 3.2 and discloses several lypes of inelficient learning behaviors stale-of-the-art deep GNNs following the application of our protocol (3.3). Section 4 discusses how our insights generalize between different deep GNNs and justify the flat curve phenomenon (1.1), including some additional re- flections on how other well-kmown challenges of the field can be tied to the learning inefficiencies brought
forward in this work (42 and 1.3
discussion of limitations and future work wraps up this section (4.4)
Section b summarizes the conclusions of the work.
2
Deep GNNs
2.1
Preliminaries
2.1.1 Graph Convolutional Networks
We introduce GCNs as proposed by Kipf & Welling (2017) in the context of semi-supervised node classifi- cation. Cousidering a graph G = (V, A), let us define as the set of all n vertices {ui,..., Un and A as an adjacency matrix of size n x n where ai defines the edge between nodes Us and By: if 02 and by are connected, Ogj EJ0, 1}; otherwise, aij 0. Let also define D, the diagonal degree matrix of G, where the degree of U; can be defined di = ES Oij- The normalized adjacency matrix of G with added self-loops
now be written as Å = 11/22/1 AD 1/2 where À = A + I, and D + In Each node v/ is also associated with m-dimensional feature vector x;. Stacking all n feature vectors, we get a n x m feature matrix X, which consists of the initial node representations H
1/2
H' (AH' "W')
(1)
The output representations H' of each graph convolution layer E {l,..., can now defined by Equation where W' consists of matrix of learned weights and nonlinear activation function, such as ReLUU. Finally, for node-level tasks, a classification head consisting of a linear layer and an activation function receives H and provides the final predictions Y Raxe, where is the number of classes.
2.1.2 Oversmoothing
Given the smoothing nature of graph convolutions, training deep GNNs presents very specific challenges, in particular how to overcome graph oversmoothing. Oversmoothing is a consequence of the multiple ag- gregations of node representations in consccutive graph convolutional layers, which results in the loss of their expressive power as all nodes in the graph will exponentially converge to the same constant [Rucch et al., 2023a). Therefore, a network that produces oversmoothed node representations inevitably decreases its discriminative power to the point of random classification. As such, pursuing depth in GCNs inherently assumess that the network architecture accommodates method that enables them to avoid this phenomenon.
2.2 Current Recipes for Depth Scaling
Inspired by the success of deep learning in other domains, searching for GNN layers that can scale with respect to depth has been a driver for researchers the field, despite well-known bottlenecks (e.g., oversmoothing). Table shows some examples of such layers. The following soctions claborate on the used methods and how these have been combined in layers that enable deep architectures. We further discuss what these approaches have in common and what may distinguish them.
3

---

Published in Transactions on Machine Learning Research (04/2024)
2.2.1 Residual Connections
Residual connections are one of the most commonly employed methods to mitigate oversmoothing, thus enabling the training of deep GNNs, The terms residual and skip connections are often used interchangeably refer a family of methods that enable the flow information directly from representations of previous layers later, deeper ones in deep neural networks. If we stay closer to the initial proposition of residual connections (He et al. 2016), can define them by Equation as also proposed in the original GCN work (Kipf & Welling; 2017) with the purpose of containing oversmoothing and the inherent performance drop associated with incrcasing depth.
H' = OAH +H'
However, in its simplest form, this method only scems to be moderately effective, results show that oversmoothing tends lo be delayed but not fully prevented and we should expect performance drop we stack more layers. As such, subsequent works (Chen et al., 2020: Gasteiger et al. 2018 proposed a direct connection to the initial node representation in the form of Equation where E [0, is a parameter that controls the strength the residual connection.
H' = (((1-))) +HH")W")
-
(3)
Other connections (dense (Guo et al. 2019). jumping knowledge (Xu et al. 2018b)) have also been proposed,
but these have hardly managed to prevent the performance drop trend (Jaiswal et al. 2022). The initial
residual connection defined by Equation 3
(nitten), on the other hand, has been consistently assisting
the training of deep GNNs without significant performance loss, which has motivated their adoption (either
as described with subtle adaptations) in recent works (Jaiswal et al. 2022 Kulatilleke et al. 2022 Feng
et al. 2021 Liu al. 2021
Zhang et al. 2022
2.2.2 Other Methods
Several other methods have been proposed with the purpose of mitigating/reduuing oversmoothing, such normalization and regularization techniques (Zhao & Akoglu 2020 Rong et al. 2019). Others use more
complex layers and have been broadly categorized as archilectural bweaks (Jaiswal el al. 2022 or changing
GNN dynamics (Rusch et al. 2023a). Methods such as GraphCON (Rusch et al. 2022). GRAFF Di Giovanni ct al. p, G (Rusch et al. 2023b). GGCN (Yan al., 2022), GPRGNN CChien al. 2021 fall under this category. These methods frequently combine several other strategies into the same expression, including residual connections which have been deemed necessary to avoid their oversmoothing by Rusch et al. (002b
2.2.3 Comparison of State-of-ther Approaches
Table shows examples of layers that have been used to create deep architectures while atlaining adequate performance. Despite the different levels of complexity of these layers, one can observe that they share some koy ingredients:
A way to preserve the information of earlier node representations in latter, deeper ones, ei- ther by adding a residual connection to H (GGCN, G²), an initial residual connection to H (GCN+Iittes,, GCNII), or by weighting all intermediate representations in the final embedding (GPRGNN):
Coefficients (learnable or not) that weight the graph convolution term(s), and, thus, the effect of the increasingly smoothed representations in the latter embeddings.
While the first point helps preventing oversmoothing by having a sharpening effect in the later, more smoothed node representations, the second has the potential to hold back the smoothing effect of the graph
4

---

Published in Transactions on Machine Learning Research (04/2024)
Table 1: Examples of layers that have been empirically shown to enable deep architectures. All layers include some type of residual connection another method that enables the preservation of previous node representations. For full explanation of all terms and coefficients, please refer to 5 of the Appendix and/or the original publications.
Method
Layer
GCN InitRes
H'
aH w AH'
GCNIT
H' =
a)) a)AHH + 8)T + (,wi))
Deep GNNs
GPRGNN
H²= Ei n'H
GGCN
H' H + ('(
+ + o o AOTTH' + 8 )
G2
H' (1 + о H + oa (AH'-IW))
convolutions and decrease the speed of convergence to a constant value that defines oversmoothing. Contin- nous GNN approaches, such as GraphCON (Rusch et al. 2022) and GRAFF (Di Giovanni al., 2022), were left out of the scope of this analysis for conciseness, but similar extrapolations could be performed for these architectures, which notably also include term for preserving earlier node representations and smoothing control coefficients (see At for GraphCON and for GRAFF).
Comparing these layers suggests that the occasional offset in accuracy between different models (Figure 1 is due to the unique terms/learnal in some cases. However, the performance stagnation over depth phenomenon can still be verified (Figure ! for the simplest of the models and the most complex ones alike, despite the architectural tweaks which add to their complexity.
coefficients of their layers, which can make them more or less expressive
2.3 On the discriminative power of deep GNNs: case study for Gnitte
The works presented in Table [ show that we can design deep GNN architectures; but are there actual empirical gains in going deeper? And can we measure them? In this subsection, we conduct a series of analyses using the simplest of deep GNN models (GCN+InitRes) provide further and more thorough insights on the potential of depth
means to increase the discriminative power of GNNs.
GnN+IniRRes layers can be defined by a graph smoothing term, equivalent to that of vanilla-GCNs, and an initial feature encoding term (the residual connection) with a sharpening effect. The influence of these terms in the layer-wise node representations is weighted by a and its symmetric (Equation 3), i.c., for a = 0 we have the vanilla-GCN and for a = 0.5 the smoothed representations have the same weight as the initial ones. We will expand on the problem of performance stagnation over depth for GNNs by exploiting GCN+TnitRes properties, as the simplest of the deep GNN examples. We aim find the practical benefits of scaling these models with respect to depth, while enhancing these empirical insights through comparisons with the base models that compose Gnit (i.e., GCN and MLPP).
Methodology. We investigate the effect of using initial residual connections to train deep GCNs by con- ducting a thorough ablation study of the depth (L) and residual connection strength (a). To that end, we conceive framework, taking L and a as input variables, where each layer assumes the form of Equation We also consider a shallow vanilla-GCN and a 2-layer MLP as baselines for performance comparison. We use eleven of the most common dataset benchmarks, including homophilic and heterophilie networks (more benchmarking and training details in Appendix A). The results of the full ablation study are shown in Appendix B.1 Table 2 shows compact version with the results for the best a for each network depth
(further details on the comparison of models can be found in Appendix B.1.2)
Benchmark patterns. Comparing GnittnisRes with the baseline models in Table we can identify three distinct patterns within our benchmark datasets. Case groups benchmarks for which Gnit shows no evidence of superiority when compared to a Manila-GCNN, For these cases, a vanilla- GaNaaaGGN is able deliver equivalent superior outcome compared to that of GCN+ TnitRRe, regardless of its depth. As such,
5

---

Published in Transactions on Machine Learning Research (04/2024)
Table 2: Node classification accuracy of Gntt of increasing depth (I.) and Vanill--GCN and MLP basclines for eleven datasct benchmarks. Bold values correspond to largest mean accuracy (top performance) for each benchmark; Underlined values highlight results that show no statistically significant difference from the best performing GCN HnitRees each benchmark (row-wise). [Case 1] Vanilla-GCN performance is superior or equivalent to GCN+InitRes. [Case 2] GCN-InitRos performs better than both basclines. [Case 3] MLP performance is superior or equivalent to Gnit
Baselines
GCN InitRes
Vanilla-GCN
MLP
==1
L=2
L=4
L=8
16
L 64
Case
Citeseer
72
684 06
.74.002
.22.002
704..06
.694.06
.684.06
.702.04
.694.05
.714.03
Squirrel
.44.01
334.02
392.02
41+.02
.14.02
.24.02
.22.00
422.01
.24
.24.022
Chameleon
.00+.03
504.03
492.03
.55.00
.54.033
.54..03
.53+.03
.53+.03
.54+.02
.544.03
Cora
82.1.03
.8.1.05
.84..02
8221.01
.811.02
.80..00
.801.03
.811.02
.81.1.02
.811.03
Physics
.9.1.00
.9.1.03
.9.1.00
.971.00
.971.00
.971.00
.971.00
.971.00
.971.00
.97.1.00
Case
Pubmed
.874.01
86.1.02
.911.01
.91..1
.911.01
.891.01
.891.01
.92..0
.891.01
.891.01
CS
.334.00
.91.03
.95+.0
.55..0
.0...0
.951.00
.95+.00
.95..01
.951.01
.951.00
Case
Cornell
43+.06
.75+.02
424.05
.73..04
.734.06
.74+.05
.33..04
.75=.04
.75+.04
.744.05
Texas
.59+.07
.824.04
511.13
.78+.05
.14.04
804.06
.11.05
.80=.03
80+.06
804:00
Wisconsin
.51..08
.874.02
.994.05
.55.05
864.03
.844.03
.84.004
.84..03
.84.00
.84.003
Actor
27:1001
.3...04
.34.00
361..01
.361.01
.35..01
.35..01
.35..01
.34..01
.351.01
adding sharpening component in the form of initial residual connection seems not to bring an evident empirical benefit in these cases. Case 2 evidences benchmarks for which GCN+InitRes is consistently superior than its basic components alone. For these benchmarks, the combination of a smoothing and sharpening component in a single model is able to marginally improve the results, thus evidencing a benefit of practical utility. This benefit, however, seems to be independent of depth, as both shallow and deep GCN+InitRes models were able to deliver top performance of classification. Concerning Case benchmarks, we verify that GCN+InitRe achieves lop performance for all L 2 showing equivalence to the performance of feature-only MLP in this case.
Deep Gni+InisRes are as discriminative as their shallow counterparts. Our results support that, while
can be more discriminative than the base models that compose it (Case 2), using this method as a means to pursue depth shows no empirical benefit in any scenario. In fact, we find that there is always at least one shallow GCN+ network (up to 2 layers) able to reach top performance.
3 Depth Evaluation
Benchmark results such as the ones disclosed in our case study 2.3 and Figure 1 make us question how we have been evaluating depth for GNNs. Works that conduct analyses on deep versions of new GNNs have been mostly relying on mcasuring whether they can successfully avoid oversmoothing, but have hardly evaluated whether progressively stacking more layers actually increases the discriminative power of the network. Depth scaling claims have been frequently supported by insufficient benchmarking tables including single performance metric, frequently accuracy (mean and standard deviation), and consider method to be superior if it exhibits the highest mean absolute accuracy, even if they have high, overlapping standard deviations and marginal performance gains (Chen et. al. 2020 Bodnar et al. 2022 Rusch et al. 2023b).
This scction introduces some background on previous depth ovaluation approaches and where they fail. We further propose new protocol that addresses some of their challenges, based on which we disclose set of learning inefficiencies in state-of-the-art deep GNNs.

---

Regression and Published in Transactions on Machine Learning Research (04/2024)
3.1 Background
3.1.1
Insufficiency of Oversmoothing Measures
Previous works have evaluated deep GNNs' capacity to overcome oversmoothing by studying the Dirichlet energy (Jaiswal al. 2022; Rusch et al. 2023a]. Dirichlet energy can be given by Equation | and can essentially be described as metric of local node similarity which satisfies useful conditions, namely if X is constant for all nodes E V. (X) 0. As such, the layer-wise exponential convergence of E(X) to 0 defines oversmoothing with respect to this measure.
E(X) EE JEN;
IX x
(4)
Nonetheless, to evaluate the need for depth, it is not sufficient to just evaluate whether we are avoiding oversmoothing. In fact, according to Rusch al. (2023a), the simple addition of a bias each layer is enough to keep the Dirichlet energy from exponentially dropping to zero we increase depth; however, this does not directly imply that we are gaining expressivity and deriving more meaningful node representations by stacking more layers.
3.1.2 Finding Pathological Behavior in Deep Networks
Central Kernel Alignment (CKA) was introducod by Kornblith et al. (2019 as a robust mcasure of the relationship between feature representations within the same netw and across different networks. In particular, the authors show that CKA (Equation 5 is invariant scaling and can be used to understand network architectures, revealing when depth can become pathological in neural networks representations (e.g., when big part of the network produces representations that are very similar and, thus, redundant). Following its introduction, CKA has been extensively used to study how deep neural networks learn representations (Nguyen et al. undersland the specific case of deep GNNs.
orthogonal transform and isotropic
2020 Raghu et al. 2021), although never to
H
1 ||
Linear CKA(H' H²)= =
(5)
H H
H
Recently, some rescarchers have been pointing out some handicaps of CKA and defending that its inter- pretation can be counterintuitive (Davari et al.] 2022). Thus, can be prudent to complement it with other methods that were previously employed to measure representation similarity, such as linear regression. Such methods have been used to validate CKA in its original work, and we argue that they can lead to complementary information towards understanding how deep networks are learning.
3.2 Depth Evaluation Protocol for GNNs
In order to study the representations learned by GNNs over depth, we propose a protocol that inspects the layer-wise hidden node representations with two different measures of linear CKA:
1. Train Logistic Regression classifier on the intermediate hidden representations H' (1...,, of the same network, a metric of the linear separability of the clusters at each consecutive layer;
Compute CKA to measure the pairwise similarity of hidden node representations of layers I, e (I,..., L} within the same GNN.
Ideally, hidden node representations consecutive layers should lead increasingly more separable clusters (evidenced by higher accuracies if classified by Logistic Regression models) and progressively become

---

Published in Transactions on Machine Learning Research (04/2024)
Healthy behavior
Type Pathology
Type II Pathology
Accumay
Aususatty
2
3
10
15
10
15
0
10
15
Layer
Layer
Layar
Similarity
Figure 2: Examples of healthy vs. pathological learning behaviors. Layer-wise Logistic Regression is mea- sured in terms of accuracy of classification using the intermediate hidden representations H' E {I...., L}: pairwise CKA of layers 1, k E (1,... L.} represented by the similarity matrices. Type Pathology manifests as a sequence of noisy layers (particularly evident for I 6); Type II Pathology manifests a sequence of nearly identical layers (particularly evident for 1 10).
dissimilar from the earlier node representations of more shallow layers, as stacking more layers is expected to increase the discriminative power of the network. For concision, we will call this a healthy behavior (Figure _ deviation from this trend will be referred to as a pathology a term already coined by previous works Kornblith et al. 2019) for other lypes of deep learning models.
Korublith et al. (019) used Logistic Regression classification as reference to validate CKA's efficacy in detecting depth-related pathologies. In this case, propose analogous protocol, in which analysing the linear separability of the clusters over depth is not irrelevant irrelevant/reduunanti redduddddu,,, but complemenlary. That is because, not only are we interested in identifying cases in which hidden embeddings might show high similarity (and thus be deemed redundant), but also whether we are progressively increasing the discriminative power of the network by stacking more layers. This latter analysis cannot be fully given by CKA alone (e.g. if H' and H'+l evidence low similarity, we cannot know this dissimilarity is beneficial or not without the assistance of complementary method able to show whether the classes are becoming progressively more separable).
3.3 Pathological Depth in GNNs
We apply our depth evaluation protocol to three deep GNN models: GCN+InitRes, GCNII, G2. Our experiments intend to verify the hypothesis of pathologic behavior in deep GNNs as a justification for the flat curve phenomenon. We show the results for one benchmark of each case surveyed in Table 2 to remain succinct while showing evidence of different patterns of behaviors.
Methodology. We evaluate depth through layer-wise inspection of hidden node embeddings, according to the protocol proposed in the previons section. Higher accuracy in Logistic Regression classification means that the clusters are more linearly separable. Representations with low similarity should lead to CKA close to and highly similar representations to a CKA of up to Figure illustrates the results of this protocol for three different deep GNN models 116/64-layers) on three benchmark datasets.
3.3.1 Identification and Categorization of Pathologies
Our depth evaluation protocol shows evidence unhealthy behavior for all of the studied deep GNNs. We categorise such behavior as two different types of pathologics. Figure[]showe an example of healthy learning behavior as opposed to the pathological trends identified in this work. The following paragraphs elaborate how these pathologies manifest in the different deep GNNs (Figure 3)
8

---

Published in Transactions on Machine Learning Research (04/2024)
GCN-intRRes
GCMI
G2
16-ayarra
64-layars
15-aya
G4-ayan
1G-ayara
Co-tyyera
13
25 40 95 Liyet
15:15520222000 45
Lager
25
Layer
Loget
Lagel
LAye
Lager
Layer
Liget
Figure 3: Results of our depth evaluation protocol for GCN+ GCNII and G² (16/64-layers) on three benchmarks (Cora, Pubmed, Texas). Layer-wise Logistic Regression measured in terms of accuracy of classification using the intermediate hidden representations H' E {I, L); pairwise CKA of layers 1, e {l, L} represented by the similarity matrices.
observe in the examples of Figure is succession of noisy layers. This manifests a sequence of layers that show specilic pattern in terms of similarity (visually producing a noisy square in the similarity matrix) and whose hidden representations prove not to be linearly separable (Logistic Regression accuracy equivalent to random classification). We call this pattern a Type palhology. This pathology very evident in the early layers of GCN+InitRes and GCNIT networks, and gets more and more pronounced as we increase network depth because the number of noisy layers seems to increase proportionally with the overall depth of the network. Texas seems be the benchmark that is more affected by this pathology (only the last 3-4 layers appear to contribute to improve the discriminative power of the network, regardless of its overall depth).
Type I Pathology. One of the major inefficiencics that
Type II Pathology. The last layers of +CN+tnitRes and GCNII models for Cora and Pubmed seem to be able to progressively learn, but we can also verify an occasional redundancy some consecutive layers. This redundancy showed by semi-constant accuracy when comes the linear separability of the clusters and nearly identical node representations (similarity close to 1). In practice, this means that these layers could potentially be pruned with little expected consequences for the final performance of the network. We call this Type II pathology. The impact of this pathology in the overall outcome is very limited for the example described above (as we only observe it for small number of consocutive layers), but the same pathology can be easily identified for large parts of the G2 networks. The extent to which we observe this pathology in G2 models is particularly cumbersome for Texas, for which the large majority of every network shows identical node representations.
Severe cases. The severity of these pathologics varies with benchmark, model type and depth, but the phenomenons the same. Both types of pathologies can coexist in the same network, with different levels
9

---

Published in Transactions on Machine Learning Research (04/2024)
of severity (e.g., 16-layer GCN+InitRes Pubmed). The fact that Texas exhibited the most exacerbated examples of the described pathologies is very significant, as Texas is benchmark for which a feature- only MLP remains relevant by delivering state-of-the-art results, even when compared with complex GNN architectures (see Case 3 of Table 2 This observation is not a coincidence, and similar patterns that show severe pathological behaviors can be found for the remaining Case 3 benchmarks (see examples in Figure 7 of the Appendix). This finding hints at the conclusion that the key ingredients that have been enabling GNNs to go deep also give them the ability completely obliterate the usage of graph structure when these networks are not able encode such structure productively.
3.3.2 Causes
Going back to the comparison of deep GNN layers in section 2.2.3 we can yet find that these inefficient learning behaviors can be a direct and logical consequence of the key ingredients that have been enabling GNNs to go deep.
Looking into Gniten and GCNII in Figure we see similar patterns of unhealthy learning, mostly through the development of Type I pathologies. These networks are also the ones that use direct connections to the initial node embeddings H in their layers (Table 1 We hypothesise that such connections are responsible for enabling Type I pathologies, as the networks are able to recreate the information lost due to the excessive smoothing of the consecutive graph convolutions in later embeddings, by using the initial representations. For this reason, the first layers are essentially useless aseless/noisy /nossy (see drop in accuracy to random classification level from HD to H' for all deep GCN+ and GCNII experiments), while the last. L T-- p layers seem be able to progressively learn useful embeddings. By learning to obliterate the usage of its first layers, the networks are able to deliver H with optimal smoothing for the downstream task. The same optimal level of smoothing could, however, be achieved with shallower network.
Pathologies of Type IT seem to be related with the coefficients that weight the graph convolution term and the residual connection. All studied models IGCN+ImitRes, GCNII, GP) consider these coefficients to be symmetrical. The main difference between these approaches is that G² learns a scalar per layer (r'), while GCN+InitRes and GCNII consider a tunable hyperparameter (a) that fixed for all layers of the network. The results of Figure 3 show that G2 is particularly affected by Type II pathologies, especially in the final layers of the networks. The high similarity of consecutive node embeddings for the deeper representations suggests that, as depth increases, r' tends to zero, al which point H' = H and layers become redundant. For Texas, a dataset for which graph convolutions do not seem to be particularly useful, this can even mean repetitive reprosentations for all 1 > 1. We hypothesize that for GCN+ also playing a role in refraining the smoothing speed, as occasional repetilive representations can be found for the last L-P p layers that progressively learn (e.g., semi-constant accuracy and high similarity of 16-layer GCNII on Cora for < 1 < 11). Further analyses on the role of the residual connection strength (a) in GNNs can be found in Appendix B.1
and GCNII networks, a is
4 Generalization of Insights Between Different Deep GNNs
This section aims to further bridge the conclusions of sections 2 and 3 by discussing two key points of our work:
1. Pathologies are consequence of the addition of residual connections and the smoothing refraining coefficients to GNN layers (as discussed in 3.3.2):
All surveyed methods in Table (i.e., works that claim depth scaling) rely on both of these "ingre- dients" to create deep architectures (as discussed in 2.2.3).
The direct correspondence between the causes of the pathologies and the identified key ingredients of depth scaling suggests that similar behavior should be expected whenever these components are part of deep GNN
10

---

Published in Transactions on Machine Learning Research (04/2024)
architectures, i.e., our conclusions are not limited to the examples we inspected. For this reason, we expand on the generic relation between the "flat curve" and the pathologies (4.1), on the role of residual connections one of the most frequently adopted and unquestioned methods in the literature in GNN learning (4.2), and on how pathologies can not only justify the "flat curve" but also other puzzling phenomena whose causes still lack general agreement in the community (like the equivalence between GNNs and MLPs on some heterophilic benchmarks).
4.1 Performance stagnation over depth: the flat curve
The inefficient learning behaviours identified as pathologies in the previous section provide a deeper under- standing of the results presented in Table for GCN+ InitRes and, consequently, the flat curve phenomenon.
Gnitenis case study. Case 1 benchmarks correspond to datasets for which the underlying structure of the graph encodes relevant information under the smoothing assumptions of graph convolutions. These benchmarks benefit from at least one graph convolution operation, which is why vanilla-GCN can perform on par with +nN+tn In these cases, GCN- InitRes develops a pathology of Type I which ultimately turns a large part of the networks into useless representations- and, occasionally, some cases of redundant representations (Type II); as such, these networks only turn out to effectively take advantage of small number of convolutions, leading to results equivalent to those of shallow vanilla-GCN. We hypothesise that this behavior is possible due to the initial residual connection, which enables direct flows of information from the first, non-smoothed levels into the deeper, potentially oversmoothed ones (as discussed in 3.3.2
Analogously, for benchmarks of Case 2, we observe pathologies of both types. In this case, derives more meaningful representations than its baseline counterparts; however, a shallow of or layers is sufficient achieve top performance. As such, stacking more layers leads to incfficient learning behaviors.
Finally, Case 3 benchmarks seem not to benefit from graph convolutions, as both feature-only MLP and a GnN+ can achieve top performance. Benchmarks of this case undergo the most severe consequences of the pathologies and are not able to leverage the large majority of the network. Developing Type I or Type II pathologies enables them to cireumvent the smoothing effects of graph convolutions. This leads them to rely mostly on linear transformations of the initial features (only possible due to the initial residual connection), followed by non-linearities -ennte the empirical equivalence to the MLP.
Other deep GNNs. These observations for GnN+ could be generalized for the remaining, more complex deep GNNs, since they are sustained by the theoretical analysis of the layers' expressions that led us to conclude that they share some key ingredients. The fact that all of them combine terms that preserve previous, non-smoothed representations and have coefficients that can refrain the smoothing (see Section 2.2.3 strongly hints at the conclusion that these networks are undergoing lcarning handicaps analogous to the ones identified in this work as pathologies when they attempl to go deep. This would justify why we also verify the flat curve in their case, and is corroborated by the results exhibited in Figure 3 for GCNII and G Showing cxhaustive evidence of the pathologics for the remaining models is out of the scope of this work, but we encourage other researchers to do so. We also discuss the case of GPRGNN and GGCN in slightly more detail in Appendix B.2
Since the pathologies are rooted in the addition of residual connections and smoothing controlling coefficients to each layer, and not in the convolution operation itself (which can be more or less expressive in some cases), we expect that our conclusions can extend to other architectures (sce an example for GAT+InitRes in Figure of Appendix B.3). . Evidently, we do not advocate that the proposition of the new and more complex layers is useless. These models have proved their potential to deliver saate-of-the-ars results in several benchmarks, which validates their practical utility and relevance within the field of GNN research. We do, however, emphasize that, at this point, we could find no evidence of any benefit of practical utility when scaling them with respect to depth, both in the literature and in our own experiments. This finding makes us question whether the pursuit of depth within the field is being properly addressed, as current approaches seem to overshadow the problems with deep GNNs rather then solving them. For this reason, we encourage other researchers evaluate their claims of appropriate depth scaling more thoroughly, and propose a protocol to assist them in doing so.
11

---

Published in Transactions on Machine Learning Research (04/2024)
4.2 The role of residual connections
The importance of residual connections has been highlighted in previous works (Di Giovanni et al. 2022:
Jaiswal et al. 2022). However, we clarify the extent of their contribution from an empirical perspective (explicitly for initial residuals, but with implicit assumptions for other architectures). by looking into the intermediate hidden node representations. By doing this, we bring forward, for the first time, the fact that top performing GNNs with residual connections can converge to a solution in which they avoid oversmoothing by reconstructing non-smoothed representations from earlier embeddings in later layers and disregard the noisy information of the previous ones (Type I pathology). This means that while residual connections can make GNNs more powerful to some level, by enabling the combination of smoothed with sharp representations, they are not effective as mcans to achieve depth.
We verify this for Gni-InitRes, but we canmot rule out that analogous behavior might be observed for more complex architectures, as all the surveyed architectures include coefficients that enable them to preserve pre- vious node representations for indefinite depth (Table D For this reason, we encourage other researchers perform similar analyses as the ones performed in this work when proposing new layer types that enable deep architectures by pertaining residual connections (or analogous strategies of prescrvation of the information of early hidden representations), and not just to evaluate if oversmoothing is avoided using the Dirichlet energy (which can be kept constant without that actually meaning that GNNs are increasing their discriminative power, as discussed in 3.1.1
4.3 Overcoming harmful heterophily
The methods that have been proposed to address oversmoothing have also often been empirically verified to help overcoming harmful heterophily. This has led to some works looking into the two concepts over- smoothing and heterophily- - at once (Yan et al., 2022: Di Giovanni et al. 2022 Bodnar et al.) 2022), namely using the Dirichlet Energy. Our results also provide a justification for this phenomenon by suggesting that for cases in which we cannot leverage the smoothing component (because the graph structure is not helpful (ooes et al. 2022)), networks that use earlier, non-smoothed embeddings can ultimately just resort these for their final representations (by evidencing Type I or Type II pathology). This implics that the same phenomena that causes inefficient depth scaling can also explain the equivalence to MLPs in these cases: if neighbourhood aggregation through graph convolutions does not lead to improved representations for the downstream task, networks will learn to resort to noisy or identity layers (i.e., in this case, optimal smoothing is found for L = O). This conclusion is novel and justifics why these networks have been perform- ing on par with MLPs for these cases, a problem that had been previously brought forward (Gomes et al. 2022 Luan et al. 2022), but never fully explained, to the best of the authors' knowledge.
4.4 Limitations and Future Work
While our protocol addresses the limitations of previous depth evaluation methods, it is mostly focused in assisting the identification and interpretation of learning inefficiencies and does not provide a final statistical metric that can be directly used to compare different methods. This can limit its potential application scenarios. However, we believe that it would not be possible to derive such insightful empirical analyses from single metric alone, without incurring in limitations analogous to those of the methods that precede this work, due to GNNs' complexity. Our study also mainly addresses how different GNNs learn the most useful reprosentations for certain task. It is not our goal to achieve state-of-the-art results or to particularly optimize the training process. For this reason, we do not perform hyperparameter luning or inspect further regularization methods, providing the same base of comparison for all networks. All training details and hyperparameters are available in Appendix[A.2) evidence of our hypotheses with respect what is causing the pathologies and study whether we could circumvent them to create more useful deep GNNs.
reproducibility. As future work, we intend to find further
12

---

Published in Transactions on Machine Learning Research (04/2024)
5 Conclusion
This work unwraps the performance stagnation over depth phenomenon (the flat curve) which has been verified in the context of current GNN research. We survey and explore both simple and complex/state- of-the-art deep GNNs that empirically show adequate performance and find no evidence that these models are superior to their shallow counterparts. We further justify this phenomenon by showing evidence of pathological behavior in these deep networks, following layer-wise hidden embeddings" inspection, in the form of noisy (Type I pathology) and redundant (Type II pathology) layers. As such, concerning depth in GNNs, the main take home message is that just because you can, does not mean you should. For this reason, encourage other rescarchers to thoroughly validate the claims that their newly proposed models are able to appropriately scale with respect to depth by measuring the effective gains of these deep models, and propose a depth evaluation protocol to assist them in doing so. Showing evidence of such gains would justify that the pursuit of depth within the field actually has a paetical/cmpirical benefit.
References
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference on Learning Representations, 2020.
Cristian Bodnar, Francesco Di Giovanni, Benjamin Chamberlain, Pictro Lio, and Michael Bronstein. Neural sheal diffusion: lopological perspective on heterophily and oversmoothing guns. Advances in Neurul Information Processing Systems, 35:18527-18544 185411, 2022.
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 1735. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL https: //openreview.. honparreiee.net//fouumm oegp
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936-9949, 2021.
MohammadReza Davari, Stefan Horoi, Amine Natik, Guillaume Lajoie, Guy Wolf, and Eugene Belilovsky. On the inadequacy of cka as a measure of similarity in deep learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
Francesco Di Giovanni, James Rowbottom, Benjamin P Chamberlain, Thomas Markovich, and Michael M Bronstein. Graph neural networks as gradient flows. arXiv preprint arXiv:2206. 10991, 2022.
Guosheng Feng, Chunnan Wang, and Hongzhi Wang. Search for deep graph neural networks. arXiv preprint arXiv:2109.1000 10047, 2021.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. Xrxiv preprint arXiv:1810005997, 2018
Diana Gomes, Frederik Ruelens, Kyriakos Efthhmiadis, Ann Nowe, and Peter Vranex. When are graph neural networks better than structure-aguotiic methods? In I Can't Believe It's Not Beller Workshop: Understanding Deep Learning Through Empirical Falsification (NeurIPS 22), 2022.
Zhijiang Guo, Yan Zhang, Zhiyang Teng, and Wei Lu. Densely connected graph convolutional networks for graph-to-sequence learning. Transactions of the Association for Computational Linguistics, 7:297-312, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
13

---

Published in Transactions on Machine Learning Research (04/2024)
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 recognilion, pp. 770-778, 2016.
Ajay Jaiswal, Peihao Wang, Tianlong Chen, Justin Rousseau, Ying Ding, and Zhangyang Wang. Old can be gold: Better gradient flow can make vanillaggens great again. Advances in Neural Information Processing Systems, 35:7561 7574, 2022.
Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems, 35:2268-2285 2022.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Simon Kornblith, Mohammad Norouzi, Honglak Lee, and Geolfrey Hinton. Similarity of neural network representations revisited. In International Conference on Machine Learning, pp. 3519-3529. PMLR, 2019.
Gayan K Kulatilleke, Marius Portmann, Ryan Ko, and Shekhar S Chandra. Fdgatii: Fast dynamic graph attention with initial residual and identity. In Al 2022: Advances in Artificial Intelligence: 35th Aus- Iralasian Joint Conference, AI 2022, Perth, WA, Australia, December 5 8, 2022, Proceedings, pp. 73 86. Springer, 2022.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
Xiaorui Liu, Jiayuan Ding, Wei Jin, Han Xu, Yao Ma, Zitao Liu, and Jiliang Tang. Graph neural networks with adaptive residual. Advances in Neural Information Processing Systems, 34:9720 9733, 2021.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhn, Xiao Wen Chang, and Doina Precup. When do we need gnn for node classification? arXiv preprint Xrx::22200. 16979, 2022.
Sitao Luan, Mingde Zhao, Xiao-Wei Chang, and Doina Precup. Training matters: Unlocking potentials of deeper graph convolutional neural networks. In International Conference on Compler Networks and Their Ayplications, pp. 49 60. Springer, 2023.
Thao Nguyen, Maithra Raghu, and Simon Kornblith. Do wide and deep networks learn the same things? un- covering how neural network representations vary with width and depth. arXiv preprint orvv::2010. 15327, 2020.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classifi- cation. arxiv preprint arXiv:1905.102: 10947, 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020. URL https:
//openrevies.oe htt.://w.....oommmmddssssaaaaaaa
Maithra Raghu, Thomas Unterthiner, Simon Kornblith, Chiyuan Zhang, and Alexey Dosovitskiy. Do vision transformers see like convolutional neural networks? Advances in Neurol Information Processing Systems, 34:12116-12125, 2021.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprinl
10903, 2019.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, ((2)cnaa0114 2021.
T Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bronstein. Graph-coupled oscillator networks. In International Conference on Machine Learning, pp. PMLRR 2022.
14

---

Published in Transactions on Machine Learning Research (04/2024)
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey oversmoothing in graph neural networks. arXie preprint arXiv:2303. 10993, 2023a.
T. Konstantin Rusch, Benjamin Paul Chamberlain, Michael W. Mahoney, Michael M. Bronstein, and Sid- dhartha Mishra. Gradient gating for deep multi-rate learning graphs. In The Fleventh International Conference Learning Representattons, 2023b. URL
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network ovaluation. arXiv preprint arXiv:1811.05868 2018
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio.
Graph allention networks. In International Conference on Learning Represenlations, 2018. URL https:
//openreview. nwt.:/ommmmddrrrrraeoo....
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.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1111::8100.0000 00826, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453 5462. PMLR, 2018b.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Hotcrophily and oversmoothing in graph convolutional ncural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 1287 1292, 2022. doi:
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Wentao Zhang, Zeang Sheng, Ziqi Yin, Yuezihan Jiang, Yikuan Xia, Jun Gao, Zhi Yang, and Bin Cui. Model degradation hinders deep graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2493-2503, 2022.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2020. httppp///ppaaaerree...ee/////t/a
A Experimental details
A.1 Benchmarks overview
Citation networks Yang al. (2016) are homophilic networks where nodes correspond to scientific papers and links encode citations.
Coauthor datasets Shohur et al. (nodes) that coauthored paper.
2018 are an homophilic graph problem where edges connect authors
Wikipedia datasets Rozemberczki et al. (2021) correspond to heteropilic graphs where nodes corre- spond to web pages and edges to hyperlinks between them.
WebKB were introduced in Pei et al. 2020 Similarly to Wikipedia, these networks also encode web pages and hyperlinks.
The Actor network was also used Pei et al. (2020) and consists of a sub-problem of the film- director-actor-writer network. In this dataset, an actor-only subgraph is considered, where nodes represent actors and edges define co-occurrences in the same Wikipedia page.
15

---

Published in Transactions on Machine Learning Research (04/2024)
Table Properties of benchmark datasets.
Legend: N-Nodes; E Edges; F Features; C- Classes; H-
Homophily; ED Edge Density.
Dataset
# N
# E
#
F
#
C
H
ED
Type
Cora
2708
5429
1433
7
.81
.00074
Citation
CiteSeer
3327
4732
3703
6
.74
.00043
Citation
Pubmed
19717
44338
500
.00011
Citation
CS
18333
163788
6805
15
.81
.00049
Coauthor
Physics
34493
495924
8415
.93
.000422
Coauthor
Chameleon
2277
36101
2325
5
.23
.0070
Wikipedia
Squirrel
5201
217073
2089
5
.22
.0080
Wikipedia
Actor
7600
33544
931
5
.22
.00058
Actor
Cornell
183
295
1703
5
.30
.0088
WebKB
Texas
183
309
1703
.11
.0092
WebKB
Wisconsin
251
499
1703
.21
.0079
WebKB
We consider the ten dataset partitions of Pei et al. (2020), where each partition consists of randomly splitting the nodes of each class in 60%-20%-20% for training walpiingvvvliaaio-eeieiiii respectively. An analogous splitting was applied for Coauthor, not considered by Pei et al. (2020).
A.2 Training conditions
All GNN architectures consist of single linear layer for input feature transformation into 16 channels, followed by L cressage-passingg layers (or a fixed number of linear layers for the MLP baseline), and node classification head (linarr layer). Besides and a, all hyperparameters are fixed, as Table shows, including the number hidden channels.
Table 4: Hyperparameters.
Hyperparameter
Value
Network Archilecture
No. Layers (L)
4,8, 16, 64, 128} {0.0, 0.1, 0.3, 0.4, 0.5) 16
Residual strength (a)
Hidden channels
Training
Dropout rate
0.5
Weight decay
0.0005
Max. Epochs
500
Early Stopping (patience)
50
Learning rate
0.01
Optimizer
Adam
This setup means that each (L, a) pair defines a different GNN, culminating in a total of 48 architectures. We run this setup for all ten partitions of each dataset as a 10-fold cross-validation process. This results in a total 48 11 x 10 5280 experiments, for which we log the following, with respect to the test set: 1) the performance in terms of test accuracy; 2) the hidden embeddings, H' of all intermediate node representations after each convolution layer E {1,..., L.).
16

---

Published in Transactions on Machine Learning Research (04/2024)
B Further analyses
B.1 GCN++nitRes Ablation Study
B.1.1 Statistical Tests for Performance Comparison
Cern
Pubmad
texas
+22
+204
+6.0
+.21
230
450
410
+3:4
44
18.35
64
10.08
1380
18.1
183
+0.00
18.06
446
14.00
246
+0.00
+8.
+8.00
446
+0.0%
+0.07
1.:0
14
19
145
270
10
122
22%
12%
123
126
122
120
126
03
-16
176
206
1.6
126
27
03
176
.27
19v
12%
127
1.5
.27
1215
.3%
2.74
2.24
122
-%
120
155
-05
-2%
22
526
425
-25
47%
1026
-03
41/
135
-121
16
138
3
12k
chamelson
CassthorCS
Actor
35
134
18
32
306
126
0:
05-
08-
+749
-0.6
130
153
1206
12.6
-.56
+4.0
18.5
184
1841
+84
+80
X4L
-28
423
4080
431
4000
+300
4.00
206
224
40%
19
50%
12
225
1/6
044
64
04
122
225
125
03
.22
Figure 4: Results of the ablation study of depth (L) residual connection strength (a) in terms of node classification accuracy for 2 benchmark examples of each case. [Plots] Mean test accuracy over depth per studied (faded areas correspond to standard devialion). [Performance matrices] Mean accuracy + standard deviation for each (L, a) architecture: black shading corresponds to p grey shading highlights the cases which satisfy the mill hypothesis, (1..)) 1rest
We compare the average test accuracy of the different network architectures each benchmark dataset through statistical tests. Let us consider that each dalaset d is associated with set (L..) = {acc1, .... acc10); where acc; refers to the test accuracy of the network defined by (I, on the i-th partition of d. Let us yet define P( the average of all elements in A(L,a) We can finally define # which corresponds to the network architecture leading to the largest average test accuracy in d, Abest This set is taken as reference of the best performance in d, against which all other sets Ad (L.a) shall be compared. For that purpose, we conduct a paired t-test on the following hypotheses:
Ho (null hypothesis): pestt = M(L,a)i
He (alternate hypothesis): peat # d
(LL
We consider a 95% confidence interval, thus rejecting the null hypothesis for p-values < 0.05. This means that for p-values > 0.05 we cannot discard with statistically significant relevance that the averages under comparison are equal, i.e. equivalent to top performance in the cases under analysis.
17

---

Published in Transactions on Machine Learning Research (04/2024)
Figure 4 shows the performance over depth for different values of a in two views: 1) plot chart of mean accuracy + standard deviation over number of layers; 2) matrix of accuracies per (T,,a) net network, our search space. We conduct paired t-tests to find evidence of statistically significant differences of performance between each (L, a) and the architecture leading to the best absolute mean accuracy for each dataset. Shaded areas correspond to architectures for which we could not reject the null hypothesis.
The chart view evidences the flat curve behavior that we aim to explain. We can further observe relation between the magnitude of and the performance drop to a semi-constant accuracy range over depth, more evident for some benchmarks than others (e.g. Cora). This proves that the behavior under analysis is directly tied to our arootthing/sharpeniin the initial residual connection strength. At the same time, we observe equivalent accuracy ranges for all a larger than a certain, dataset-specific threshold, especially for deeper networks.
weighting coefficient, which in this case corresponds to controlling
We can also see different patterns with respect to a for each of the cases outlined in Table 2 by analysing the matrix view. Coherently to what we saw before, Case 1 strongly benefits from the smoothing component, which can even be optimal after single graph convolution, regardless of the value of a, can only be achieved for = O. Case 2 benchmarks benefit from high residuals (a 2 0.3); and Case 3 benchmarks achieve top performance for any a 2 0.1. On the other hand, by inspecting the depth dimension, we can observe that shallow versions are mostly preferred in Case 1, but top performing architectures for Cases 2 and 3 are mostly independent of depth.
B.1.2 Model comparison methodology
The comparison basis for the results of Table 2 was best performance for each model lype. We considered the same number of hidden dimensions for all networks, meaning that the number of parameters of each network varies only with depth. For GNNs, we ran a grid search of a and depth and report the results for the best performing (a,, depth) pair (see per shown in B.1.1) For vanilla-GNN, this meant that Table 2 shows results for 1- or 2-layers networks for all benchmarks, with the exception of Texas (4-layer GCN was reported because the absolute average of accuracy was superior; however, no statistically significant difference was found compared to the 2-layers version). For the MLPs, considered networks of 2-layers, per most frequently seen in the literature in benchmarking analysis with these datasets.
B.2 Description of Deep GNN Layers
Table 5
provides a description of all terms and coefficients of the layers of the surveyed deep GNNs.
GCNII and G² models were considered in our empirical analyses, and we show evidence of pathologies for some of their deep versions, following the application of our depth evaluation protocol, for exemplification. Despite not having considered GPRGNN and GGCN in these analyses, we have reasons to believe that analogous pathologies can be happening in their case. For example, the ablation studies on 7 published in the original GPRGNN publication Chien et al. 20021) show that this variable frequently tends to zero as depth increases (meaning that the deeper, more smoothed representations will be negligible for attaining the final representations; thus, we should expect hidden embeddings of high similarity as go deeper, making them redundant -Tppe II pathology). For the GGCN case, the complexity of the layers can hamper its close analysis; in order to be thorough, it would be important to look into all variables (learned or tuned) and study their downstream impact. However, just by looking into 7, we find that this function easily tends to zero after a small number of iterations (which can be tuned), again making the smoothing term nearly irrelevant as we go deeper. These analyses, however, are mostly hypotheses and should be further investigated through the application of dedicated protocols.
B.3 Depth Evaluation: further examples
Figures 5 and show the results of our depth evaluation protocol for 16-layers GnN+ GCNIL and G for all benchmarks of Cases 1, 2 and 3, respectively. Figure S shows an example of the severity of pathological behavior particularly observed for benchmarks of Case 3, for progressively deeper networks. Figure 9 showcases the pathological behavior observed in 16-layers GAT+InitRes networks.
18

---

Published in Transactions on Machine Learning Research (04/2024)
Table 5: Description of the terms and coefficients of the surveyed layers. These layers have been empirically shown to enable deep architectures. Please refer the original publications for further information.
Method
Layer
H' = d' ( d (000011811000 +ww!))
GCNII
Chen al.
2020
Scalar (hyperparameter)
gt
Scalar (hyperparamucter)
H = AH''
CPRGNN Chien et al.
2021
76
Scalar (learned)
H H + (o((8) + (S o Á A TT'H + BSS @ A AOT'HH(-))
GGCN Yan et al. 2022
"
Decay function (based hyperparameters) Scalar (learued)
Scalar (learned)
H' - + b (bias) Re
6!
Scalar (learued)
S
Positive messages matrix, Raxn
pos
T
Degree correction matrix, R
Scalar (learued)
Negative messages matrix, Rax
neg
= (1- (1- H + o (w')
Rusch et al. 2023b
7
Rates matrix (learned), Roxm
Layer
73
Number nodes
70
Number channels
A
Normalized adJacency matrix, Raxn
H
Hidden embeddings matrix of the I-th layer, Boxm
W
Weights matrix of the I-th layer, gmxm Activation function (e.g., ReLU, softmax)
19

---

Published in Transactions on Machine Learning Research (04/2024)
Figure 5: Results of our depth evaluation protocol for GCN+InitRes GCNII and G2 (16-layers) on Case 1 benchmarks (Citeseer, Squirrel, Chameleon, Cora, Physics).
Fabenc
Figure 6: Results of our depth evaluation protocol for GCN+Ini GCNII and G2 (16-layers) on Case 2 benchmarks (Pubmed, CS).
20

---

Published in Transactions on Machine Learning Research (04/2024)
Qurret
Wozsten
Achor
Leyee
Figure 7: Results of our depth evaluation protocol for Gnts GCNIT and G2 (16-layers) on Case 3 benchmarks (Cornell, Texas, Wisconsin, Actor).
S-ayrs
OCMI
Figure 8: Results of our depth evaluation protocol for GCN+IntRess, GCNII and G² (4/8/16/32/644
on Texas benchmark, as an example of severe cases Type and Type pathologies for all studied depths.
21

---

Published in Transactions on Machine Learning Research (04/2024)
Cora
Pubmed
Texas
Aocurary
GATiinisRes
16
16
Layar
Layer
10
Layer
Simlerty
0.0
0.2
0.4
0.6
0.8
1.0
Figure Results of our depth evaluation protocol for Initess (16-layers) on Cora, Pubmed and Texas benchmarks. The implemented architecture of Gnt+InitRes analogous that of GnttenitRes (as described in the main paper). Similar trends of pathological behaviour are verified.
22


Reviews:
[{"review_id": "EOVKOZzrmX", "reviewer": "Reviewer_Qr7P", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength:**\n1. This paper included systematic experiments on oversmoothing and depth evaluations.\n2. This paper comprehensively discussed the impact of different depth-scaling methods in GNNs. This benchmark is important to show how much concrete progress the GNN community is making toward the real benefits of increasing the GNN depth.\n\n**Weakness:**\n1. Although provided with plentiful empirical evidence, this paper did not propose any method to improve the benefit of GNN depth scaling.\n2. Section 4 is poorly organized, less motivated, and did not provide any experimental results. I could not get the key message of Section 4 quickly (e.g. why do you want to compare different GNNs).\n\n**Question:**\nIn Table 2: Do GCN and MLP share a similar number of model parameters for fair comparisons?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates why deep Graph Neural Networks (GNNs) fail to significantly outperform their shallower counterparts, a phenomenon termed as the \"flat curve\" of performance over depth. It critically examines the effectiveness of current depth scaling methods in GNNs and identifies pathological behaviors that may mask rather than solve the underlying issues of depth scaling. Through empirical studies using common benchmark datasets and a case study on GCN with initial residual connections (GCN+InitRes), the research highlights the limitations of deep GNNs in enhancing discriminative power and proposes a depth evaluation protocol to identify and categorize inefficiencies in learning behaviors. The findings suggest that deep GNNs often exhibit redundant or noisy layer behaviors, questioning the pursuit of depth in GNN architectures and urging for more thorough validation of depth scaling claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As discussed on the weakness and questions above, I would appreciate the authors making changes including:\n1. Any potential ideas on improving the GNN depth scaling based on the empirical observations.\n2. A better organized Section 4.\n3. Clarification on the number of parameters of models compared in Table 2.", "broader_impact_concerns": "No ethical justification is needed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SA9rYBOB79", "reviewer": "Reviewer_Zimx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper highlights an important issue actively discussed in the literature.\n- The empirical analysis is extensive and conclusive.\n- The analysis based on logistic regression and CKA is interesting, and the justification for type I and II pathologies makes sense.\n\nWeaknesses\n- I don't think this should be a main criterion for evaluating this type of paper, but I don't see any technical contribution.\n- The main message, \"Even if you may add depth, that would not necessarily bring gain\", is somehow expected, so the empirical findings are not super surprising.\n- While this may be beyond the scope of the paper (but at the same time that is the reason why I think this is a weakness), no insights for designing better GNN architecture for alleviating type I or II pathologies.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper empirically investigates the existing approaches to tackle the over-smoothing problems in GNNs. While there indeed are various approaches for overcoming over-smoothing problems and enabling the depth-scaling, there is an empirical consensus saying that adding those depths does not lead to performance gain, unlike the other deep neural nets that usually benefit from depth-scaling. The paper provides a thorough empirical evaluation of GCN variants known to tackle over-smoothing problems for several benchmark datasets and proposes a protocol to evaluate the benefits of adding depths to GNNs. The results show that at least judging from the benchmarks tested in the paper, the added depths do not seem to bring significant gain in terms of representational diversity. Actually, even when the GNNs are trained with larger depths, they eventually seem to use only part of the layers or many layers end up being redundant.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I must admit that I'm not keen on the state-of-the-art models in GNN literature, but as far as I know, GCN is quite a basic model; there seem to be numerous GNN models, for instance, involving attention layers (GAT) or even transformer based architectures. Would a similar argument also hold for those models? I think the message in the paper can be strengthened by at least mentioning other GNN architectures with different design principles and analyzing them.", "broader_impact_concerns": "I don't see any ethical concerns or implications may be brought by this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cOzbZHKbMu", "reviewer": "Reviewer_2Eab", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- S1. The paper is clearly written, easy to follow, and the methods evaluated properly introduced,\n\n- S2. The protocol to evaluate depth performance is sensible and novel, yet I would add final performance as well (see C1).\n\n- S3. It is quite interesting to observe that Type I pathology happens in certain type of GNNs.\n\n- S4. Of having a stronger motivation/premise, the conclusions of the papers would be quite insightful, encouraging the community to not pursue depth for the sake of it. It even made me consider if a similar behaviour happens in non-GNN residual connections.\n\n**Weaknesses**\n\n- W1. My main concern directly goes to the premise of this work. While I understand that \"more layers = better performance\" is a desirable goal, I'd argue this is not a general thought by the community (at least it is not my case). If the network is able to classify with 10 layers, it is completely fine if the next 5 layers are identity functions. Put differently, to me \"Type II Pathology\" looks like a higher-resolution version of \"Healthy behavior\" in Fig. 2 (as long as classification performance is equal). I believe there are no strong enough arguments to justify the premise of the paper. See requested changes for more details.\n\n- W2. As mentioned in the paper, there is no hyperparameter tuning. While I understand there are lots of experiments, it is hard to take any conclusions of the work as true using the same hyperparameters for 1- and 128-layer GNNs.\n\n- W3. The conclusions regarding residual connections (e.g., those from section 4.3) while interesting in this context, I do not find them as novel. I'd argue that this intuition is built whenever residual connections are first taught, e.g., using the prototypical example of learning an identity with a network, which needs to leverage previous representations.\n\n- W4. While existing approaches to train deep GNNs are correctly explained, there is no discussion regarding previous works on understanding the role of depth on GNNs at all. For example, [Not too little, not too much: a theoretical analysis of graph (over)smoothing](http://arxiv.org/abs/2205.12156) studies theoretically the role of layers in regression problems with linear GNNs, and shows that in that case *there exists* an optimal depth, and that keep adding layers would lead to constant features (which goes into the argument that Type II is actually desirable).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the problem that, while current approaches for deep GNNs are able to successfully avoid oversmoothing, their performance (or discriminate power) does not improve with depth, which the authors refer to as a \"flat curve\" behaviour).  \n\nTo this end, the authors provide an intuition on what current approaches do, and analyse one of them on a number of datasets to distinguish three types of dataset types. Then, the authors provide a protocol to evaluate the healthy behaviour of deep GNNs, and provide several scenarios where current methods exhibit two pathological behaviours: one where previous layers are ignored, and another where deeper layers are ignored, behaving like identity functions.\n\nFinally, the authors provide a discussion on the possible causes of this behaviour, as well as on how the observed pathologies should generalize to other GNNs, or the role that residual connections have on the matter.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- C1. The motivation of the paper needs to be significantly stronger. As of now, I see two main flaws in the premise that need to be justified:\n  - A real example: One could argue that in all examples either simple GNNs or MLPs reach sota results on and, hence, it is unreasonable to expect deeper GNNs to make use of the extra layers. The authors should find stronger datasets of the type \"Case 2\", maybe those from [OGB](https://ogb.stanford.edu/) may work.  \n  - Additional information: If Type II is a real pathology, I understand the classification performance worsens. If that's the case, plots like those in Fig. 2 should show the final performance. Otherwise, I would argue G2 is a perfectly healthy model.\n\n- C2. A somewhat reasonable hyperparameter tune should be performed.\n\n---\n\nAfter the rebuttal with the authors, I consider that the additional experiments are just enough to empirically validate the claims of this work.", "broader_impact_concerns": "I do not have any broader impact concerns in this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: A reviewer noted the lack of datasets and tasks that clearly benefit from deeper GNN architectures. Developing such datasets would be an interesting research direction and valuable contribution to the field.
Decision: Accept (poster)