Residual Connections and Normalization Can Provably Prevent Oversmoothing in GNNs
Authors: Michael Scholkemper
Xinyi Wu
Ali Jadbabaie
Michael T Schaub
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Normalization
Residual Connections
Oversmoothing
Primary area: learning on graphs and other geometries & topologies
TL;DR: We show that Normalization and Residual Connections prevent Oversmoothing but also perturb that graph operator.

Abstract: Residual connections and normalization layers have become standard design choices for graph neural networks (GNNs), and were proposed as solutions to the mitigate the oversmoothing problem in GNNs. However, how exactly these methods help alleviate the oversmoothing problem from a theoretical perspective is not well understood. In this work, we provide a formal and precise characterization of (linearized) GNNs with residual connections and normalization layers. We establish that (a) for residual connections, the incorporation of the initial features at each layer can prevent the signal from becoming too smooth, and determines the subspace of possible node representations; (b) batch normalization prevents a complete collapse of the output embedding space to a one-dimensional subspace through the individual rescaling of each column of the feature matrix. This results in the convergence of node representations to the top-k eigenspace of the message-passing operator; (c) moreover, we show that the centering step of a normalization layer — which can be understood as a projection — alters the graph signal in message-passing in such a way that relevant information can become harder to extract. Building on the last theoretical insight, we introduce GraphNormv2, a novel and principled normalization layer. GraphNormv2 features a learnable centering step designed to preserve the integrity of the original graph signal. Experimental results corroborate the effectiveness of our method, demonstrating improved performance across various GNN architectures and tasks.

Published as a conference paper at ICLR 2025
RESIDUAL CONNECTIONS AND NORMALIZATION CAN PROVABLY PREVENT OVERSMOOTHING IN GNNS
Michael Scholkemper"
Xinyi Wu"
Department of Computer Science
Institute for Data, Systems, and Society Massachusetts Institute of Technology xinyiwu@mit.ee
RWTH Aachen University
schol kemper êcs. www.-wachen.cc.mmmm
Ali Jadbabaie
Michael T. Schaub
Institute for Data, Systems, and Society Massachusetts Institute of Technology ja dbaba @mi edu
Department of Computer Science
RWTH Aachen University schaubêcs rwth-aachen. de
ABSTRACT
Residual connections and normalization layers have become standard design choices for graph neural networks (GNNs), and were proposed as solutions the mitigate the oversmoothing problem in GNNs. However, how exactly these methods help alleviate the oversmoothing problem from a theoretical perspective is not well understood. In this work, we provide a formal and precise characterization (lincarized) GNNs with residual connections and normalization layers. We establish that (a) for residual connections, the incorporation of the initial features at each layer can prevent the signal from becoming too smooth, and determines the subspace of possible node representations; (b) batch normalization prevents complete collapse of the output embedding space to a one-dimensional subspace through the individual rescaling of each column of the feature matrix. This results in the convergence of node representations to the top-k eigenspace of the message- passing operator; (c) moreover, we show that the centering step of normalization layer - which can be understood as a projection - alters the graph signal in message-passing such a way that relevant information can become harder ex- tract. Building on the last theoretical insight, we introduce GraphNormv2, novel and principled normalization layer. GraphNormv2 features learnable centering step designed to preserve the integrity of the original graph signal. Experimen- results corroborate the effectiveness of our method, demonstrating improved performance across various GNN architectures and tasks.
INTRODUCTION
In recent years, graph neural networks (GNNs) have gained significant popularity due their ability
to process complex graph-structured data and extract features in an end-to-end trainable fashion (Gori
al. 2005) Scarselli al. 2009 Bruna et al., 2014 Duvenaud et al. [015] Defferrard al. 2016
Kipf & Welling 2017 Velickovié et al. 2018). They have shown empirical success in hi highly
diverse set of problems (Battaglia et al. 2016 Wu et al. 20200] Xu et al. 2019 Morris et al. 2019
Tha et al.) 2022, Cappart al.) 2021). Most GNNs follow message- message-passing paradigm (Gilmer
et al. al.] 2017). where node representations are learned by recursively aggregating and transforming the
representations of the neighboring nodes. Through repeated message-passingg
the graph, the graph
information is implicitly incorporated.
A prevalent problem in message- passing GNNs is their tendency oversmooth (Oono & Suzuki 2020 Cai et al.) 2021 Wu et al. 2023a; Keriven 2022). which refers to the observation that node signals (or representations) tend to contract to mieddimeniional subspace the number layers increases. While a certain amount of smoothing is desirable to average out noise in the node features
Botth authors contributed equally.

---

Published as a conference paper at ICLR 2025
and render information extraction from the graph more reliable (Keriven 2022 Wu et al. 2023b).
excessive smoothing leads to an information loss as node signals become virtually indistinguishable and can thus not be exploited for downstream tasks. For this reason, most GNN architectures use only few message-passing layers (Kipf & Welling, 2017, Veličković et al. 2018 Xu et al. 2019). This contrasts with the trend in deep learning, where much deeper architectures are considered preferable (He et al. 2016 Kaplan et al. 2020)
To mitigate the oversmoothing problem for GNNs, several practical solutions have been proposed.
In particular, both residual connections (Chen et al. 2020 Klicpera et al. 2019) and normalization layers (Zhao Akoglu 2020, Zhou et al. 2021] Guo et al. 2023) have been specifically proposed to Guo address the oversmoothing problem. Despite empirical observations that the introduction of these methods can alleviate oversmoothing and enable deeper architectures, a theoretical analysis on the effects of these methods on oversmoothing and the resultant expressive power of GNNs is still lacking. More technically, the analysis of oversmoothing typically relies on single node similarity measure as description of the whole underlying system (Oono & Suzuki 2020 Cai & Wang 2020 Wu ct al. 2023a). Such measures, however, can only identify a complete collapse of the node signals to one dimensional subspace and are unable to capture the more refined geometry of the system beyond a complete collapse. These observations motivate the following questions:
How do residual connections and normalization layers affect oversmoothing and therefore the practical expressive power of GNNs? How do they compare?
In this work, we answer the above questions with a refined characterization of the underlying system of linearized GNNs (Keriven 2022 Wu et al. 20235) with residual connections and normalization layers. In particular, we establish that both methods can alleviate oversmoothing by preventing node signals from complete collapse one-dimensional subspace, contrary to the case for standard
GNNs (Oono & Suzuki 2020 Cai & Wang 2020 Wu et al. 2023a).
Our contributions can be summarized as follows:
We characterize the system of linearized GNNs with residual connections. We show that residual connections prevent complete rank collapse to a oin-dimensional subspace by incorporating the initial features at each step. As result, the subspace of possible node representations that a GNN can compute is determined by the initial features.
We analyze the system of linearized GNNs with normalization layers and show that normalization layers prevent oversmoothing of node signals through the scaling step. Nonetheless, the node representations exponentially converge to the top-k eigenspace of the message- message-passing operator. We separately identify the role of the centering step in normalization layers. Our results suggest that the centering step can distort the pesssae--passing in undesired ways. Consequently, relevant graph information becomes dampened and can even be lost in message-passing.
Based on these theoretical findings, we propose novel normalization layer named GraphNormv2 that learns a centering operation that does not distort the subspaces of the message- passing operator an uncontrolled way, but contains a learnable projection. Experimental results show the effectiveness of our proposed method.
2 RELATED WORK
Oversmoothing in GNNs Oversmoothing is known challenge for developing deeper and more powerful GNNs, and many techniques have been proposed to mitigate the issue in practice. Among them, residual connections (Chen al. 2020) and normalization layers (Zhao & Akoglu 2020 Zhou et al. 2021 Guo et al.) 2023) are popular methods that have empirically been shown to mitigate oversmoothing to certain extent. While many theoretical works on the underlying mechanism of oversmoothing exist (Oono & Suzuki, 2020 Cai et al.] [221 Keriven 2022] Wu et al.) 2023b a). these studies focus on standard GNNs without these additional modules. It is thus still an open question how residual connections and normalization can mitigate oversmoothing and subsequently affect the practical expressive power of GNNs from theoretical perspective.
Theoretical studies residual connections and normalization in deep learning The empirical success of residual connections and normalization in enhancing training deep neural networks has inspired research into their underlying mechanisms (Arora et al. 2018. Daneshmand al.
2

---

Published as a conference paper at ICLR 2025
2021 Yang et al.) 2019: Liu et al. 2019 Hardt & Ma 2017 Esteve et al., 2020). Specifically, has been shown that batch normalization avoids rank collapse for randomly initialized deep linear networks (Daneshmand
al. 2020) and that residual connections alleviate rank collapse in transformers (Dong et al,, 2021). j. Rank collapse of node representations due to oversmoothing has also been notable issue in building deeper GNNss. However, theoretical analysis of how residual connections and normalization layers combat oversmoothing and their additional effects on message-passing in GNNs is still lacking.
NOTATION AND PRELIMINARIES
Notation We use the shorthand [n] := {1. [I.....n} n). We denote the zero-vector by O, the all- one vector by 1 and the identity matrix by I. Let 11 I|-1 be the 2-norm and Frobenius norm, respectively. Lastly, for matrix M, we denote its 8th row by M,. and j column by M.j.
Graph Neural Networks Most message-passing passing GNN models - which we will simply refer to as GNNs from
can be described by the following update equation:
((++1) = o -AA
(I)
where ((),, (()),((+) (++1) E R are the input and output node representations of the 7 layer, respectively;
(.) is an dlement-wise non-linearity such as the ReLU function; W( RR* a learnable linear transformation and R220" represents a pressage-passingg operation and reflects the graph structure. For example, if A the graph adjacency matrix, A Aadj we recover the Graph Isomorphism Network (GIN) (Xu et al. 2019), and for = D Azaj D-1 where = diag( Aadi 1) is the diagonal degree matrix, we obtain Graph Convolutional Network (GCN) (Kipf & Welling 2017).
Throughout the paper, we assume A to be symmetric and non-negative. Furthermore, we assume that eigenvalues X; of matrix organized in non-increasing order in terms of absolute value: [Ai] A21 2 ... |Aal For simplicity, assume the columns of the initial features X(I) to be normalized, i.e. ||x (x) 1|2 =1
Normalization Layers Normalization has been believed to be beneficial to deep neural networks for nearly two decades (LeCun al. 2002). Most normalization layers perform centering operation and a scaling operation on the input features. Centering usually consists of subtracting the mean, centering the features around zero along the chosen dimension. Scaling usually consists of scaling the features such that the features along the chosen dimension have unit variance. The two most popular approaches are batch and layer normalization (loffe & Szegedy 2015 Ba et al. (016). In our work, we focus on batch normalization (BatchNorm), denoted as BN (+), which is defined as follows: Let X Raxk then
BN(X) |-.. bn ....).
where bn(x) (n(x)=(<> (x D//=,//n\/11 E,=1,./ni E 21/n/l2 We note that in the case of GNNs, especially graph classification tasks, batches may contain nodes from different graphs. In our analysis, we consider only the nodes in the same graph for normalization and nodes in different graphs do not influence each other. This is sometimes called instance normalization (Ulyanov et al. 2016).
GraphNorm In Cai et al. 2021), the authors proposed GraphNorm, a normalization layer specif- ically designed for GNNs that is like BatchNorm in terms of acting the columns of the feature matrix. However, compared to BatchNorm, instead of subtracting the mean, the method learns to subtract an Ty portion of the mean for the jth column:
X., 1, 1, X.3/n + B3
GraphNorm((X.)
Jj
where oj 7,11 x.,g///./////////// VTi, Ti. By the learnable affine parameters as in the implementation of other normalization methods (Ba et al. 2016 loffe Szegedy 2015). Notably, by introducing Ty for each feature dimension j. (Cai et al. 2021 claims an advantage of GraphNorm over the original batch normalization in that Graph keep in the mean rather than always subtracting the entire mean away.
able to lear how much of the information
3

---

Published as a conference paper at ICLR 2025
Weisfeiler-Leman and Structural Eigenvectors In theoretical studies about GNNs, algorithm that comes up frequently is the so-called Weisfeiler-Leman (WL) algorithm (Weisfeiler & Leman 1968). This algorithm iteratively assigns color c(v) E IN to each node starting from constant for all nodes. In each iteration, E (B) where hash is an injective hash function, {{-}) denotes a multiset in which elements can appear more than once, and M()) is the set of neighboring nodes of v. The algorithm returns the final colors c(0o) when the partition {(c(9) (v)) [v))] } no longer changes for consecutive update t. For GNNs, Morris et al. (2019) and Xu et al. (2019) showed that for graphs with constant initial node features, GNNs cannot compute different features for nodes that are in the same class in the final coloring c(0o)
initial coloring (v)
update of the following form is
computed: (v) = hash (u), (fc()))))
For this paper, an equívalent algebraic perspective of the WL algorithm will be more useful (see Appendix A.1 for a detailed discussion): Given c( with Im(c(>)) = {ci, C define H e {0, 1) m such that Ha, = if and only if coo)) (v) = C₁. It holds that AH HA"
where A E R is the adjacency matrix of the quotient graph, which is fixed given and H. In words, node in the quotient graph represents a class of nodes in the original graph who share the same number of neighbors in each final color.
Most relevantly, the adjacency matrix A of the original graph inherits all the eigempairs from the quotient graph: If n" is the eigenvector of A" with eigenvalue x, then Hv" is an eigenvector of A
with eigenvalue A. We call such eigenvectors of A the structural eigenvectors. These eigenvectors
important for understanding dynamical systems on graphs (Schaub et al. [0016] Yuan et al. (013). and play role for centrality measures such as PageRank (Sánchez- Garcia 2020) and others (Stamm let al. 2023). In fact, from the results of Morris et al. (2019) and Xu et al. (2019), we can directly infer that given constant initial features, GNNs effectively compute node features on this quotient graph, meaning the features lie in the space spanned by the structural eigenvectors.
4 MAIN RESULTS: DEFYING OVERSMOOTHING
Both residual connections and normalization techniques are widely recognized as effective methods for mitigating oversmoothing in GNNs (Chen et al. 2020 Klicpera al. 2019 Zhou al. 202T Zhao & Akoglu 2020 Guo et al. 2023). In this section, we provide theoretical evidence that these approaches not only mitigate but provably prevent oversmoothing. Previous studies have demonstrated that oversmoothing occurs exponentially in standard Graph Convolutional Networks (GCNs) (Oono & Suzuki 22000; Cai et al., 202T) and similarly in random walk GCNs and more general attention-based GNNs (Wu et al. 2023a). These findings suggest that for GNNs with non- diverging weights, repeated pessagg-ppsssigg invariably leads to the collapse of node signals into a onc-dimensional subspace, regardless of initial features. However, our analysis reveals that these results do not hold for GNNs employing residual connections or BatchNorm. Furthermore, we offer precise characterization of the convergence space for GNNs utilizing these techniques, providing deeper insights into their effects.
For the following theoretical analysis, investigate a linearized GNN, meaning that ((.) is the identity map. For simplicity, we assume, if not specified otherwise, that the weights (w:(")),, (w, Jijj w:(0) are randomly sampled i..dd Gaussians, which is typical for GNNs be- fore training. Such a setting is relevant in practice as oversmoothing is present in GNNs before training has started, making the gradients used for back propagation almost vanish and training of the network becomes much harder. Yet, most results hold under more general conditions. The complete proofs of all the results in the main text and the results under general conditions are provided in Appendix B
To define oversmoothing, common approach is analyze function μ(.), which measures how far the node features (1) are away from collapsing one-dimenisonal subspace. One then shows that (()( 0 as + oc, even stronger that this convergence happens at exponential rate, i.c. (0X(0)) < Cie Cat for some C1, C2 > O. There are multiple such measures of oversmoothing
'This algehraic characterisation is also known as the coarsest equitable partition (cEP) of the graph.
4

---

Published as a conference paper at ICLR 2025
the graph Dirichlet energy {X),, whereas (Rusch et al. 2023] Wu et al. 2023a) use the squared difference to the mean over each row and (Oono & Suzuki [2200) use the distance to the dominant eigenspace of the message-passee passing operator A. To allow for an analysis that takes all these perspectives into account, we will focus our analysis on the distance to general one-dimensional subspace spanned by unit vector E R":
in previous works. For example, (Cai & Wang 2020)
(x( = || vv x [[I - vo vo)))xX X
Thus, when the graph is ergodic and we choose to be the dominant eigenvector, we recover the measure used in (Oono & Suzuki 2020). With v = 1/ //, we recover the measure used in (Rusch et al., 2023 Wu et al. (2223a) and for v d/ ||]] where d = D 1, we recover an equivalent measure to the graph Dirichlet energy (()) used in (Cai & Wang. 2020 Here equivalence means
that there exist constants C1, C2 > 0 such that
C Cira//ana (X) S E(X) S Capan/an (X).
This allows us to translate statements about oversmoothing in terms of p to any of the other measures mentioned. A detailed discussion can be found in Appendix A.2
4.1 RESIDUAL CONNECTIONS PREVENT COMPLETE COLLAPSE
For our analysis of residual connections, we focus on the commonly used initial residual connections, which are deployed in architectures like GCNII (Chen et al. 2020). Such residual connections are closely related to the Personalized PageRank propagation (Klicpera et al. 2019). For generality, we write the unified layer-wise update rule for both methods as follows:
x ((+1) (1 (1- (1x + +xx(")
(4)
where (0) corresponds to the initial residual connection, and (0, can be seen the strength of residual connections or alternatively as the teleportation probability in the Personalized PageRank Propagation. Note that for the Personalized PageRank Propagation method (APPNP) proposed in (Klicpera et al. 2019), A = Dー and D &, w(") = T for all 2 O.
Intuitively, compared the case for standard peessage-passingg GNNs in I at each update step, linear combination of the residual signal (x) is now added to the features. As long as the weight matrices are not chosen such that they annihilate the residual signal, this will prevent the features from collapsing to a smaller subspace. This implies that y would be strictly greater than zero In fact, po (x(() can even be bounded away from 0, showing that oversmoothing does not happen.
Proposition 4.1. Let v E R s.t. ||l||| = If (x > 0, then w.h.p 3c > 0 s.f. p (X 2 c.
The above result suggests that, with proper initialization of node features, initial residual connections will alleviate oversmoothing with high probability, meaning the features will not be smooth after iterative message-passing
at initialization. Nonetheless, is worth noting that the node similarity measure (X) can only identify a complete collapse
oie-dimensional subspace spanned by v, in which case Mo (X) equals zero. Even if μu (X) can remain strictly positive with residual connections, this does not eliminate the possibility that there may still be partial collapse of the signal to lower-dimensional subspace. However, as we will show with the following result, with residual connections defined in 44. no such partial collapse occurs.
Proposition 4.2. Let 34 X!! ||=l|||2 1 and let each (W((1)
i..dd N(n,, Then for any
e <> 0. || x 2 with probability at least p = 1 exp
2n
This result essentially says that a part of the initial signal is maintained after each layer with high probability. We can further give a more refined characterization of what node features the system can compute after repeated rounds of message- passing..
Proposition 4.3. Let (r (0)
(pinn(AA-ixe) x:() hE(M)EE be the Krylov subspace. Let
Y E Raxk Then there exist T IN and sequence of weights ((()) w:()) .... W-(T-) (T w (T-) such that (T) = Y if and only y Kr(A, (0)).
5

---

Published as a conference paper at ICLR 2025
The result shows that for message- passsing GNN with residual connections, the subspace that the embedding ( lies in is governed by the initial features X together with the message-passing operator and that any such signal reachable by a sequence of weights. This is in contrast with the behavior of standard message-passingg GNNs, for which node representations eventually becomes "memoryless", i.c., independent of initial features. In particular, for standard GCNs, the subspace the system converges is completely governed by the message-passinggg operator A (Oono & Suzuki 2020).
Remark 4.4. Proposition 4.3 connects closely to Theorem 2 in Chen et al. (2020). Specifically, Theorem 2 in Chen et al. (020)) implies that for any features in the Krylov subspace, there exists weights such that the corresponding GNN outputs such features. Here, we prove in addition an upper bound, that the GNN cannot express any features that lie beyond the Krylov subspace.
Remark 4.5. Our results also suggest that whether initial residual connections would work for oversmoothing heavily depends on the initialization of features. If chosen poorly, they may not be able to prevent oversmoothing. In particular, a constant initialization of features is unhelpful to prevent oversmoothing with initial residual connections.
4.2 BATCHNORM PREVENTS COMPLETE COLLAPSE
Having discussed the effect of residual connections, in this section, we switch gears and analyze how BatchNorm affects GNNs. We consider the following combination of GNNs with BatchNorm:
x(++1) BN(Y))+)) y(+1)] = (AX()(())
(5)
Similar the analysis GNNs with initial residual connections, we will show that BatchNorm prevents complete collapse of the output embedding space to a one-dimensional subspace. We again consider the case where (-) is the identity map. Note that even though the GNN computation is now lincarized, the overall system remains non-linear because of the BatchNorm operation. Let us consider now Vę2o E Bann' to be the matrix of eigenvectors associated to non-zero eigenvalues of (In - 1-17 /n)
Proposition 4.6. Let RR s.t. ||o|l2 1 and of 1 O. Let Rank VV (0)) 1, then there exists <(v) > 0 such that yh (x()) 2 c(v) for all 2 1 with probability 1.
The above result suggests that with BatchNorm, (x)))) is maintained strictly greater than a nontrivial constant at each layer, indicating that complete collapse one-dimensional subspace does not happen.
Remark 4.7. A more general version of the above result holds for both linear and non-linear GNNs, when assuming o()) is injective: for E R" such that 1 * O, under some regularity conditions, there exists c(v) > O such that (X)(+) = c(v) k for all t 1, where l: is the hidden dimension of features. In particular, this would account for the case where A is the adjacency matrix of the graph or the symmetric random walk matrix D 1122 Aaaj Maaj D D-12, and v is their corresponding dominant eigenvector. See Appendix B.7 for detailed discussion.
However, as what we have discussed for the case of residual connections, the measure ply (X) can only capture complete collapse to one-dimensional subspace. In what follows, we will provide a more precise characterization of the convergence behaviors of GNNs with BatchNorm. Notably, since the scaling operation of BatchNorm guarantees that the system will not diverge or collapse, we can give an exact asymptotic characterization. Let V₁2 E RRn* k be the matrix of the top-k eigenvectors of (7, 11 /n)A. A. We will show that the resulting linearized GNN converges to a rank-k subspace spanned by the top-k eigenvectors of (In - 11 /n)A.
Proposition 4.8. Suppose V._ x()) has rank k. then for all weights Wt), the GNN with BatchNorm given in exponentially converges to the column space of Vs-
is easy to see that the centering operation in BatchNorm the reason why we use the centered message-passing operator (4, 11 /T.) A and its eigenvectors here. If we inspected BatchNorm without scaling, however, we would arrive at a completely linear system, which must converge to the dominant eigenvector (given mild assumptions). This implies that the column-wiss scaling operation is responsible for the preservation of the rank of the features. Furthermore, there are no requirements for the weights in the case without BatchNorm (Oono& & Suzuki 2020 Wu al. 2023a): even

---

Published as a conference paper at ICLR 2025
extremely large random weights can be chosen, as the scaling ensures that the system neither diverges nor collapses.
The convergence of the linearized system in (5) to k-dimensional subspace can be shown to be tight: we can choose weights such that the top-k eigenvectors are exactly recovered. This is course only possible if these eigenvectors have a nonzero eigenvalue, which we assume for the result below, in that, none of the top-k eigenvectors of (In 11 /n) have eigenvalue zero.
Proposition 4.9. Suppose |dal > O and V x has rank k. For any > 0, there exists > 0 and sequence of weights ( W() W(T) such for all 2 T and i E [k].
I x 2
2 1/VIFC,
where Vi denotes the i-th eigenvector of (4, 11 /n)AA.
The above result ties in nicely with recent results showing that GNNs are strengthened through positional encodings (Dwivedi et al. [021]] 2023), where the features are augmented by the top-k eigenvectors of the graph. This can, some sense, be seen as emulating a deep GNN, which would converge to the top-k eigenspace using BatchNorm. Yet it is worth noting that while BatchNorm improves the practical expressive power of GNNs by converging to larger subspace, under the type of convergence given in Proposition 4.8 the information in the eigenvectors associated with small magnitude eigenvalues still dampened after repeated message-passing In the limit + oo, the computation is thus still memoryless.
Remark 4.10. If no initial node features x are given by the dataset, common choices in practice are to initialize the features randomly or identically for each node. In the former case, the prerequisites of of and Proposition 4.9 are satisfied. In the latter case, the conditions one. In that case, the system still converges. In fact, it retains its rank and converges to the dominant eigenvector of (Ln 11 /n)
met, ( has rank
Comparison between normalization and residual connections. From previous sections, we have seen that both residual connections and batch normalization are able to prevent complete collapse of the node embeddings to a one-dimensional subspace. In both cases, the embeddings converge to larger subspace and thus oversmoothing is alleviated. However, is clear that different mechanisms are at play to mitigate oversmoothing. With residual connections, the system is able to keep the dimensions of the initial input features by incorporating the initial features X at each layer; while with normalization, the system converges to the subspace of the top cigenvectors of the baassage-passing operator through the scaling step.
CENTERING DISTORTS THE GRAPH
So far, have analyzed the effects of residual connections and normalization layers oversmooth- ing. Specifically, we have shown that the incorporation of initial features of residual connections and the scaling effect of normalization help alleviate complete rank collapse of node features. However, there are two steps in normalization layers: centering and scaling. If already scaling helps preventing a complete collapse, a natural question what the role of centering in the process? this section, we will show that the current centering operation used in normalization layers can in fact have an undesirable effect altering the graph signal that cessage-passing can extract, if pesssage-passigg happens different graph.
5.1 CENTERING INTERFERES THE STRUCTURAL EIGENVECTORS
The centering operation in normalization layers takes away the (scaled) mean across all rows each column, and thus can be written applying the operator L, -111 /n to the input, where indicates how much mean is taken away centering. Specifically, for r = 1 we recover BatchNorm, whereas for E R, recover GraphNorm (Cai et al. 2021). To analyze how this step would alter the graph signal message-pasiee can extract, we make use of the concepts of quotient graph and structural eigenvectors introduced in Section 3
Given a symmetric, non-negative adjacency matrix A E R let H E {0, 1 be the indicator matrix of its final WI coloring (o0), Consider the eigenpairs V = (-.,, (), v), of A and divide
7

---

Published as a conference paper at ICLR 2025
them into the set of structural eigenpairs Vanc [(A, E VVI Hv*), and the remaining eigenpairs Viest V Vine. Similarly, let v = [...: (A, i)),... be the eigenpairs of (4n - -11 /n) A. We now analyze what happens to these distinct sets of eigenvectors when applying the centering operation. Notice that the parameter 5 controls how much of the mean is taken away and thus how much the centering influences the input graph. However, as long as T is not zero, there is always an effect altering the graph operator used in message-passing Proposition 5.1. Assuming T 0,
1. Vrest C V.V.
2. Assume that A is not regular, then the dominant eigenvector v of A is not an eigenvector in V for any eigenvalue.
3. Ea.veevin.
E(. A.
The authors of GraphNorm Cai et al. (202T) had previously analysed the case for regular graphs. Here, we consider a general case where the graph not regular, meaning there is more than one color in the final WL coloring c(oo)
Assuming constant initialization of node features, Vsnue spans the space of all possible node features that a GNN can compute and Proposition 5.I states that it is exactly the space that the centering acts on. Specifically, while leaving the eigenvectors and eigenvalues in Viea untouched, centering changes the eigenvector basis of the space spanned by Vsruc in two ways: some vectors, such as the dominant eigenvector, are affected by this transformation and thus no longer convey the same information. At the same time, the centering transformation may change the magnitude of eigenvalues that is. the dominant eigenvector may not be dominant anymore. Meanwhile, the whole space pushed downward in the spectrum, meaning that after the centering transformation, the signal components within the structural eigenvectors are dampened and thus become less pronounced in the node representations given by the GNN.
Notably, such an effect altering the graph signal not only applies to BatchNorm with r 1, but also GraphNorm (Cai et al., (02I), which was proposed specifically for GNNs. In their paper, the authors address the problem that BatchNorm's centering operation completely nullifies the graph signal on regular graphs. Their remedy is to only subtract an portion of the mean instead. However, Proposition 5.1 shows that similar underlying problem altering the graph signal would persist for general graphs even switching from BatchNorm to GraphNorm.
Comparison with standard neural networks The use of normalization techniques in GNNs was inspired by use of normalization methods in standard Szegedy 2015). Here, we want to emphasize that the issue centering causes in GNNs as described above is not a problem for standard neural networks, as standard neural networks do not need to incorporate the graph information in the forward pass. As a result, in standard neural networks, normalization transforms the input in way that it does not affect the classification performance: for each neural network, there exists a neural network that yields an equivalent classification after normalization. However, this is not the case for GNNs. In GNNs, the graph information is added in through message- message-passing, which can be heavily altered by normalization as shown above. Such normalization can lead to information loss, negatively impacting the model's performance.
neural networks (loffe &
5.2
OUR METHOD: GRAPHNORMV2
Based on our theoretical analysis, we propose new normalization layer for GNNs which has similar motivation as the original GraphNorm but improves the centering operation to not affect the graph information in message-passing. Specifically, instead of naive centering, which can be thought of as subtracting a projection to the all-ones space, we use a learned projection. Learning a completely general projection may have certain downsides, however. As graphs have different sizes, we either would need to learn different projections for different graph sizes or use only part of the learned projection for smaller graphs. We thus opt for learning a centering that transforms the features by subtracting an (Ty); portion of the i-th eigenvector from the j-th column. Our proposed graph normalization is thus:
X, (VK+TTT) VT )
GraphNormv2(Xx..) =
+ B3
0j
8

---

Published as a conference paper at ICLR 2025
1 linear
1, non linear
dx .. linear
Rank(X linear
Rank(X non lincar
10
6
4
10
100
200
100
200
200
4
16
64
256
16
64
256
none
pair
batch
powerembed
graph
graph2
res_con
Figure Long Term behavior GCN. Mean progression (over independent trials) of (x.()))) and Rank(X over 256 iterations of message-passing in both linear and non-linear GCN, where corresponds to the dominant eigenvector for D Amij methods except the vanilla GCNs, indicating that complete collapse the dominant eigenspace does not happen. However, PairNorm does collapse in terms rank, while the other methods maintain a rank greater than All the phenomena are explained by our theory. the non-linear case, the models behave similarly, Notably, centering seems to prevent rank collapse in the non-linear case as PairNorm no longer collapses in rank.
In the linear case, (x remains constant for all
where Tj E Rh+1 1 is learnable parameter, o, |X - (Vk+ V X ll2, and Yy. 3, are the learnable affine parameters. Instead of just using the top-k eigenvectors V₂ of the message-passinng operator, we use V& and one additional vector a linear combination. This ensures backward compatibility, in that, GraphNormv2 can emulate GraphNorm and BatchNorm. We denote the set Vi+ V2 fr).
V such that 1 can be represented as
NUMERICAL EXPERIMENTS
In this section, investigate the benefits that can be derived from the proposed graph normalization method GraphNormv2. We examine the long term behavior of linear and non-linear GNNs by conducting ablation study on randomly initialized, untrained GNNs. We then go on to inspect the practical relevance of our proposed method. More details about the experiments are provided in Appendix C
Rank collapse in linear and non-linear GNNs We investigate the effect of normalization in deep (linear) GNNs on the Cora dataset (Yang et al., 2016). We employ seven different architectures: an architecture using residual connections, Batch orm (loffe & Szegedy 2015), PowerEmbeed (Huang) al. 2022), PairNorm (Zhao & Akoglu 2020), GraphNorm (Cai al. a [02T]. GraphNormv2,, and finally normalization a baseline. Each of these methods is used in an untrained, randomly
initialized GCN (Kip' & Welling 2017) (without biases) with 256 layers.
We compare these models using the following measures of convergence: Me (x(())) as defined in where is the dominant eigenvector, the eigenvector space projection: (X) == where V E Rux* is the set of normalized eigenvectors of A, and the numerical VV X N
rank of the features Rank (9). The results shown in Figure The same experiment with both GIN and GAT can be found in the appendix together with additional measures of convergence.
The left panels of Figure show that the commonly considered metric for measuring oversmooth- ing (X) indeed detects the collapse of node features in vanilla GNNs to the dominant eigenspace spanned by u of the message- paagge-gassngggggg operator, in both the linear and non-linear case. Nonetheless, for any other methods. it does not detect any collapse of the feature space neither in the linear nor non-linear case. However, the right two panels show PairNorm indeed also oversmoothes in the linear case. Specifically, it converges to the dominant eigenvector of (4n - -711 D D- $). The other methods are able to preserve rank greater than two over all iterations. However, they do converge to a low-dimensional subspace, e.g. PowerEmbed and GraphNormv2 converges to the top-k eigenvector space can be seen in the middle panel. All of these phenomena are explained by our theoretical analysis. As for the non-linear case, the models behave similarly apart from two things: (a) there is convergence to the linear subspace due to the noneeiryyy (-)), although the

---

Published as a conference paper at ICLR 2025
Table 1: Performance under different normalization layers. Performance of GIN, GCN, and GAT with different normalization layers on graph classification task (MUTAG, PROTEINS, and PTC-MR) and node classification task (Cora, CiteSeer, and ogbn-arxiv). Results are reported as the mean accuracy (in %) + std. over 10 independent trials and 5 folds. Best results are highlighted in blue; second best results are highlighted in gray.
Graph Classification
Node Classifictiio
Node Clussification (#f layere=20)
MUTAG
PROTEINS
PTC-MR
Cora
CiteSeer
ogha-arxiv
Coru
CiteSeer
ogbn-arxiv
no norm
7
4.0
57.7 + 3.0
826 1.6
0.2
46.0
11.5
65.6 L.3
6.0
batch
2.0
70
5..0
85.2
0.74
16
5..7
graph
S1.+
08.1 314
85.1 # 0.8
8..
08.3
80.5
82.7
56.3 0.8
GUN
pair
61.3+ 10:1
00.
06.8
84.2
8.
82.3 13
+4.0 14.1
4.
group
7.8
09.3 4.1
56.7 1.1
85.6 0.9
0.
6..1
61.1 10.9
80.7 1.1
6.0
powerembed
42.4++3.77
3.6
05.2
4.8
85.4
89.7
68.1
0.2
48.0+99.1
77.++38
M6.+
grapliv2
42.6.4:4.6
72.6 3 2.6
56.5 4.8
85.8 0.5
80.5 4: 0.6
68:3
1 0.3
84.8 0.8
83.4 a 2.0
57.4 1 0.6
5.3
71.2
a: 2.0
61.3 4: 4.2
85.9 4: 0.9
93.7 0.5
68.3 0.9
0.72
80.1
44.6 2.8
batch
82.5.4:4.1
68.4 2: 5.2
56.7
1: 0.7
86.2 4: 0.7
91.9 1: 0.5
71.0 0.1
85.8
0.7 0.7
91.2 0.6
55.7 11.
graph
$1.22:1.8
71.9
11.9-21 2.1
00:3
4 5.4
86.3 0.9
94. 0.5
71.0 0.1
85.7
0..8 0.8
0..
$0.9
GAT
pair
11.1
60.1
0.9
55.7 1: 1.1
85.4 1.0
$3.4
1: 1.2
70.0
0.2
84.9 0.7
92.3 1: 1.0
6.2
group
73.9 3.6
69.1 4.0
59.8
4: 3.8
87.4 0.8
96.3
+ 0.5
70.9 0.1
85.1
91.2 0.5
50.6 0.6
poweremhed
70.0++0..4
08.4 3.7
87.0
55.5+00. 0.5
71.0+
85.4 0.6
56.88
06.6+
grophhv2
3..
71.0 2.6
59.5
1.4
86.3 0.8
S-.S +
70.9 0.2
85.7 = 0.8
91.3 + 0.5
57.5 0.6
norm
5.97
70.7
50:2 4:
47.0
25.7
batch
$2.5.155.0
69.2 =: 5.3
52.9 4: 5.3
68.4 21 4.0
49.7 1: 6.8
21.1 7.9
31.4
23.6 d: 6.1
6.0
graph
4.22:4.4.
72.6
50.1
31.2
11.00
21.6 0.0
26.9
0.8
GIN
pair
6.2
64.5
2: 4.3
55.5 1.6
37.2 22 3.5
61.1 1 9.2
20.7
9.6
28.6
2: 6.2
26.9 1: 4.7
6.2 01.
group
5.8
60.3
58.2
85.9
80.4
76.2 9.1
powerembed
4.77
70.1 = 3.6
59.8 11 3.5
86.0 1.1
69.7 0.7
21.1 2: 6.5
40.0 2.
53.0 2: 3.6
6.0
grophy2
71. 819:
00:1
86.5
08.9
83.8
56.6
rank can still be preserved. (b) The centering operation in PairNorm seems to prevent rank collapse in the non-linear case as PairNorm no longer collapses in rank.
Classification performance We evaluate the effectiveness of our method GraphNormy2 for real graph learning tasks. We perform graph classification tasks on the standard benchmark datasets MUTAG (Schlichtkrull al. 2017). PROTEINS (Morris et al., 2020) and PTC-MR (Bai al.. 2019) as well as node classification tasks on Cora, Citeseer (Yang et al.] 2016) and large-scale ogbn-arxiv (Hu et al. 2020 We compare GraphNormv2 to 5 normalization baselines: BatchNorm, PairNorm, GraphNorm, PowerEmbed and GroupNorm (Zhou et al. 2020)). Following the general set-up of (Errica et al. 2019), we investigate the performance of GIN, GCN and GAT in 5-fold cross- validation setting. Details hyperparameter tuning and other specifics can be found in Appendix C The final test scores are obtained as the mean scores across the folds and 10 independent trials with the selected hyperparameters. We then also repeat the same experiment Cora and Citeseer where we fix the depth of the models to 20 layers. The results are reported in T
Table T shows improvements
most benchmarks for our proposed normalization technique GraphNormvv2. Although our method yields weak performance improvements in certain cases, this trend is apparent across datasets and tasks and even seems be independent of the architecture. It is however worth mentioning that our method seems to not perform as well with GAT. This may be the result of GAT having both asymmetric and time-varying message-passing operators due to the attention mechanism (Wu et al. 2023a) - both aspects are outside the scope of our current analysis. More experimental results on other GNN backbones and heterophilic datasets can be found in Appendix D
7 DISCUSSION
In this paper, we have analyzed the effect of both residual connections and normalization layers in GNNs. We show that both methods provably alleviate oversmoothing through the incorporation of the initial features and the scaling operation, respectively. addition, by identifying that the centering operation in a normalization layer alters the graph information in peessage-passing GraphNormv2, a novel normalization layer which does not distort the graph and empirically verified its effectiveness.
proposed
Our experiments showed that the trends described by our theoretical analysis are visible even in the non-linear case. Future work may concern itself with closing the gap and explaining how centering together with non- -on-aricyr can prevent node representations from collapsing to a low-dimensional subspace.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
Michael Scholkemper and Michael Schaub acknowledge partial funding from the DFG RTG 2236 "UnRAVeLL" Uncertainty and Randomness Algorithms, Verification and Logie." and the Ministry of Culture and Science of North Rhine- Weinee-aesppaliaa (NRW Ruckkehrprogramm) Xinyi Wu and Ali Jadbabaie were supported by ONR N00014-23-1-22999 ARO MURI W911 NF-19-1-0217, and grant from Liberty Mutual.
REPRODUCIBILITY
For the theoretical statements made in the main text, number of assumptions made. These detailed in Section 3 and Section All other needed assumptions are part of the respective statements. The proof' of all of these statements can be found in Appendix B
The code is made available here The results in Figure | can be reproduced by running the
ablat ton aattatiinouuuuyyyoaaaaaaaa .iydy.ipynb notebook in the supplementary material. Aggregating the statistics over multiple runs strengthens the reproducibility of the results.
The results in Table can be reproduced by running the bash scripts node_ lee_eeeell___m norm. sh respectively on machine with a GPU. This will schedule all experiments reported in T
Level_norm. norm. sh and
Further details regarding the experiments can be found in Appendix
REFERENCES
Sanjeev Arora, Zhiyuan Li, and Kaifeng Lyu. Theoretical analysis of auto rate-tuning by batch normalization. In ICLR. 2018.
Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. ArXiv, Abs//607.06455 2016.
Yunsheng Bai, Haoyang Ding, Yang Qiao, Agustin Marinovic, Ken Gu, Tingting Chen, Yizhou Sun, and Wei Wang. Unsupervised inductive graph-level representation learning via graph-graph proximity, In IJCAI, 2019.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and koray kavukcuoglu. Interaction networks for learning about objects, relations and physics. In NeurIPS, 2016.
Joan Bruna, Wojciech Zaremba, Arthur D. Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In ICLR, 2014.
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. In ICML Graph Representation Learning and Beyond (GRL+) Workshop, 2020.
Tianle Cai, Shengjie Luo, Keyulu Xu, Di He, Tie-yam Liu, and Liwei Wang. Graphnorm: A principled approach accelerating graph neural network training. In ICML, 2021.
Quentin Cappart, Didier Chételat, Elias Boutros Khalil, Andrea Lodi, Christopher Morris, and Petar Velickovic. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 2021.
Ming Chen. Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In /CMI., 2020.
Hadi Daneshmand, Jonas Moritz Kohler, Francis R. Bach, Thomas Hofmann, and Aurélien Lucchi. Batch normalization provably avoids ranks collapse for randomly initialised deep networks. In NeurIPS, 2020.
Hadi Daneshmand, Amir Joudaki, and Francis R. Bach. Batch normalization orthogonalizes repre- sentations in deep random networks. In NeurlPS, 2021.

---

Published as a conference paper at ICLR 2025
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In NeurIPS, 2016.
Yihe Dong, rean-Baptiste Cordonnier, and Andreas Loukas. Attention is not all you need: Pure attention loses rank doubly exponentially with depth. ICML, 2021.
David Kristjanson Duvenaud, Dougal Maclaurin, Jorge Sguilera-Iparragunng Rafael Gómez- Bombarelli, Timothy D. Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In NeurIPS, 2015.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. arXiv preprint arXiv: 1912.09999 2019.
Carlos Esteve, Borjan Geshkovski, Dario Pighin, and E. Zuazua. Large-time asymptotics in deep learning. ArXiv, abs/2008. 02491, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F, Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. IJCNN, 2005.
Xiaojun Guo, Yifei Wang, Tianqi Du, and Yisen Wang. Contranorm: A contrastive learning perspective on oversmoothing and beyond. In ICLR, 2023.
William I.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Moritz Hardt and Tengyu Ma. Identity matters deep learning. ICLR, 2017.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
Weihua Hu, Matthias Fey, Marinka Zitik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.0066 00687, 2020.
Ningyuan Huang, Soledad Villar, Carey E. Priebe, Da Zheng, Cheng-Fu Fu Huang, Lin F. Yang, and Vladimir Braverman. From local to global: 1o0/2209.12054, 2022.
graph neural networks. ArXiv,
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
Kanchan Jha, Sripama Saha, and Hiteshi Singh. Prediction of protein-protein interaction using graph neural networks. Scientific Reports, 2022.
Jared Kaplan, Sam McCandlish, T. J. Henighan, Tom Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeff Wu, and Dario Amodei. Scaling laws for neural language models. ArXiv, 10.22001.0886,, 2020.
Nicolas Keriven. Not too little, not too much: a thcoretical analysis of graph (over)smoothing. In NeurIPS, 2022.
12

---

Published as a conference paper at ICLR 2025
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
Yann LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robert Müller. Efficient backprop. Neural networks: Tricks of the trade, pp. 9-50. Springer, 2002.
Tianyi Liu, Minshuo Chen, Mo Zhou, Simon Shaolei Du, Enlu Zhou, and Tuo Zhao. Towards understanding the importance of shortcut connections in residual networks. In NeurlPS, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workshop, 2020.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
Hongbin Pei, Bingzhen Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
T.Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. ArXiv, htth//303..1999, 2023.
Rubén J Sánchez-García. Exploiting symmetry network analysis. Communications Physics, 2020.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabricle Monfardini. The graph neural network model. JEEE Transactions Neural Networks, 20:61-80, 2009.
Michael T Schaub, Neave O' O'Clery, Yazan N Billeh, Jean-Charles Delvenne, Renaud Lambiotte, and Mauricio Barahona. Graph partitions and cluster synchronization networks of oscillators. Chaos: An Interdisciplinary Journal of Nonlinear Science, 26(9). 2016.
M. Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In Extended Semantic Web Conference, 2017.
Felix I. Stamm, Michael Scholkemper, Markus Strohmaier, and Michael T. Schaub. Neighborhood structure configuration models. In WWW, 2023.
Dmitry Ulyanov, Andrea Vedaldi, and Victor S. Lempitsky. Instance normalization: The missing ingredient for fast stylization. ArXiv, abs/1607.08022. 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Shiwen Wu, Wentao Zhang, Fei Sun, and Bin Cui. Graph neural networks in recommender systems: A survey. ACM Computing Surveys, 55:1
37, 2020.
Xinyi Wu, Amir Ajoriou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention- based graph neural networks. In NewrIPS, 2023a.
Xinyi Wu. Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In ICLR, 2023b.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In ICLR, 2019.
13

---

Published as a conference paper at ICLR 2025
Greg Yang, Jeffrey Pennington, Vinay Rao, Jascha Narain Sohl- Sohhl-Dcckstein, and Samuel S. Schoenholz. A mean field theory of batch normalization. In ICLR, 2019.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. ICML, 2016.
Ye Yuan, G-B Stan, Ling Shi, Mauricio Barahona, and Jorge Goncalves. Decentralised minimum-tine consensus, Automatica, 2013.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. ICLR, 2020.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In NeurlPS, 2020.
Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Understanding and resolving performance degradation in deep graph convolutional networks. In CIKM, 2021.
A FURTHER BACKGROUND MATERIALS
A.1 AN ALGEBRAIC PERSPECTIVE ON THE WEISFELLER-LEMA COLORING
We briefly restate part of what has already been stated in the main text. So that notation is clear again. The Weisfeiler-Lemar (WL) algorithm iteratively assigns color c(v) E N to each node V starting from constant initial coloring (()) (v) 1 Vu V. In each iteration, update of the following form is computed:
(o) hash (c)),) (x) | x E
(6)
where hash is an injective hash function, and (-3) denotes multiset in which elements appear more than once. The algorithm returns the final colors cl when the partition
(v)) e showed
V} no longer changes for consecutive citetmorris201 1eeesfeellee and citetxu2018pove that GNNs cannot compute different features for nodes that in the same class in the final coloring c()o).
For this paper, the equivalent algebraic perspective of the WL algorithm will be more useful: Given (( with (m(c(s)) (C1,.., .. CK define H {0, 1 jaak such that H if and only if ( (v)
cg. It holds that
AH H(H H AH HA"
TH where A (H H AH E R is the adjacency matrix of the quotient graph. Looking at this equation, there are two things of interest here.
Firstly, AH Н. Considering this equation more closely, the left side AH counts, for each node, the number of neighbors of color C,. More formally,
(AH),,s =
Σ =E(c(=0))-1())
E CEN(()]=
Σ [c(x) = ci] zEN(e)
where the Iverson bracket returns if the statement is satisfied and 0 if it is not. The right hand side of the equation (HA)") states that nodes in the same class have the same rows. not hard to verify that if (())
(HA").; = (A*)..
Now, combining both sides of the equation, the statement AH HA reads, that the number of neighbors of any color that node has is the same for all nodes of the same class meaning (c(()()) (x: N (e)) is the same for all nodes of the class. It becomes clear that at this point we have a fixed point of the WL update (6) and conversely whenever we have such a fixed point, the equation AH HA* holds. The difference between the WL algorithm and 7 is that the latter equation holds for any so called equitable partition while the WL algorithm converges to the coarsest partition meaning the partition with fewest distinct colors. For instance, regular graphs, the WI.
14

---

Published as a conference paper at ICLR 2025
algorithm returns the partition with 1 color i.. H 1. However, the trivial partition with colors H also fulfills (7).
Secondly A := (HT " AH e BeE* is the adjacency matrix of the so-called quotient graph. Noticing that /1 H diag(1) ((ie(([(c))))>"(())))))) (c)))eet)))) it quickly becomes clear that A is the graph of mean connectivity between colors. In other words, a superoode in the quotient graph represent a class of nodes in the original graph who share the same number of neighbors in each final coloring and an edge connecting two such supernodes is weighted by the number of edges there were going from nodes of the one color to nodes of the other color. In this sense, the quotient graph is compression of the graph structure. It now only has & supernodes compared to the nodes that there were in the original graph. Still the quotient graph is an adequate depiction of the structure of the graph. Most relevantly, the adjacency matrix A of the original graph inherits all eigenpairs from the quotient graph: Let (A, v²) be an eigenpair of A", then
AHv HA = AHP=
We call such eigenvectors A the structural eigenvectors. They are profoundly important and may even completely determine processes that move over the edges of network. The structural eigenvectors span a linear subspace that is invariant to multiplication with A. This means that once inside this subspace graph dynamical system cannot leave it. This holds true for GNNs as Morris et al. 2019) and Xu et al. (2019) showed.
A.2 UNIFYING PERSPECTIVES ON OVERSMOOTIING
Oversmoothing is phenomenon observed in Graph Neural Networks (GNNs) where, as the number of layers increases, the node representations tend to become indistinguishable from each other. This phenomenon has its root cause in the underlying linear system, where is known that, given mild assumptions that the system is well-behaved (ergodic and non-diverging), the linear system converges to the dominant eigenvector the graph operator A.
In different analyses of the topic, different measures of convergence are used. Oono & Suzuki (020))
used the distance from the dominant eigenvector space
(X) inf - Y| E M}
(8)
where M is the dominant eigevector space. Cai & Wang 2020 used the graph Dirichlet energy
X
E(X)
e
Finally, Rusch et al. (2023); Wu et al. (2023a) used the distance to the all-ones vector
11T X
(xX)
x
72
2
While all of these measures of oversmoothing look different, the idea behind them is similar: They characterize the convergence of the features to rank I matrix by showing that the respective functions (p(X())) + oc as + 20, where &p E {dM, E, [(X)). On can further strengthen the statement by showing that ((x()) & eie Cat i.e. that the features converge exponentially fast.
In this paper, turn analysis to tyu defined in Equation (3).
We now show that each of the above definitions is equivalent to our in the sense that for any graph there exists a v E RR and C3, C4 such that
Capup (X) S (xX) & (X)
This is useful to our analysis, since (xX) 0
(X) 0. Additionally, if we find lower bound yt, (X(()) > (like in Proposition 4.1 and 4.6 this translates to a lower bound 4p( (x(0) > e'.
For 4 = μ the equivalence is easy to see. Choosing 1/
H. = || - vo' 2 x 11 / x p(X)
So C3 C4 1.
15

---

Published as a conference paper at ICLR 2025
For op dM this equivalence can be established if the graph is ergodic (strongly connected and aperiodic). Then, the dominant eigenspace is non-degenerate meaning there is a unique dominant eigenvector / (up to scaling). Then,
dM = inf inf [|]
Y E M) = inf inf - YI {avla E R]} ||x vv x = (x())
So again, C3 = C =1
Lastly, for &p E, given, that the graph is connected, it is quite easy to see that E(X) = = X E Span( (D 1). Thus, we choose e = D Dà 1 For simplicity, we show this for X E 1R"
with | = 1. The generalisation is straight forward. Let d = max; Di,:
1o (X)
Xuu - Uu + Xx - Unl
max (1,F)
2n 2d
2vd
2
X
X
max (u.
2/ 2/Dun, Du,a
2 2 D/a
X
X1a
=((X) S (X
ddz
EE
This shows that our findings 4.1 4.6) that show that oversmoothing does not happen when using BatchNorm or residual connections carry over to GCN and attention-based GNNs for which the oversmoothing was shown be problem previously.
B PROOFS
B. PROOF FOR PROPOSITION
41
Proposition 4.1. Let v E R s.t. ||u|| = If (. > 0, then whh.p 3c > 0 s.t. N (x(1)) 2
To prove this proposition, first need to prove the following lemma:
Lemma B.1. Let 9 E R" and [x > 0 and let each (W(")),: lidd N(1, 8²).
x
Then for any
<> [l 2 1- x 1I with probability at least p = 1 - exp
25
Proof. We start by deconstructing (
(()) (1 (x- ax((
Define i == -
q. We then have:
(1 (1 - a)ğ² AX Ax + +aq" x(0
(9)
= = aaq x(0
Resulting in:
|
q T (1)
> [x
x(1)
= ||0 aq" x x
2
max 14, + alq" x Soo (( |
2 194 a(p x w 1i)
= |4/ aq T (x (
(10)
|43 on (W
= 140 Σ (ā (x (
= 14g a Σ
Σ ( )a (xx(())) Wa,
( ))0) 12
16

---

Published as a conference paper at ICLR 2025
Z is weighted sum of Gaussian variables and such, is Gaussian itself (N( 82)) with mean
f m(p;)) + E. E. (0 (x(()))),s and variance $² = 5² (p,) + a
E (E. (g )e (X ),,b)
Because we defined q l l x 4. we have that Ex (x labb) 11 x 1 2 1 and as such 3² 2 s²
Define the helper variable 2/a, which is Gaussian with 2/a (1 oz and define the variable Z ~ (0, Notice that 2/ aa has higher variance than Z. To finish the proof, notice that
Pr(1 2 ac) Pr Pr(1 2 Pr(
Pr < 21 exp (-2x² 2x²
where the last inequality is based on the Chernoff Bound. To finish the proof, notice that:
xxx00
x
1 X
and thus:
q T x (+)
Pr( x x(()
2 ca) 2 Pr(
2 ca)
11 X (0)
2
Pr([1y
T x(1)
2 ea 11 (1()
21 1 exp
2s²
We can now resume the proof of Proposition 4.1
Proof. Let the weights be randomly initialized (w(")),. yu. i.d. s2). Assume
k
Mo (x( = ||(I 2o
1 x Σ |1 vu )x
There must be a column X such that ( not scaled version v. Equivalently, x:(3) av + br, where v r and (X = > 0. Using Lemma B.1 we get that ||| T X .,1
l2 2
are: e- -|r ||>Tx(0)) (0) 12 with probability
By construction, ||> x [3 0 and we
exp
2.
choose such that p 0.9. Thus, c ||r-- ||a|| = 1:
X
1/
> Lets look u4v 14x (X()). Since
100 x0
x J
2 -
|| x S
x
T x1)
(11)
2
2
This means that
Do0 x(1) 2
5 x -02
2
And thus:
p (x =
ao -
|
||
oo
2
x(0
B.2 PROPOSITION DETERMINISTIC CASE
For the deterministic version, we adopt the following regularity conditions weight matrices: Assumption B.2. For the system described in 4) assume: there exists > 0 such that
1. Eie a(1 - a) a)"" (a" smallest singular value amin for all [m).
... -w(") + (1 - /
w((0) has
17

---

Published as a conference paper at ICLR 2025
2. E a(1 ai) " x""""""""""""""""""""""" w((mm w(t) + x (0) w:(() con- verges as / - do and has smallest singular value miin 2 for all E [n].
Suppose A is full-rank. If weights w W22h are orthogonal, then Assumption B.2 holds. On the other hand, Assumption [B.2] is asymptotic technical condition to ensure that weights non-collapsing and non-diverging in the limit. Some ways to satisfy the assumptions is to have the spectral radius of A. ((A) < 1 and w W2 1 for any 2 0.
We restate Proposition 4.1 with full conditions: let E RRax be the matrix of eigenvectors for A. Proposition B.3. Under Assumption B.2 let E V be such that Ug v = O. If x is properly initialized, such as x(0) is not the zero matrix and || X| = c 0, then n (X(t)) CE V/ for all t 2 and lim (x) 2 ce/Vk.
In particular, if V and and there exists V4 V such that Vg + and || x 12 meaning that the initial feature (0) contains a component cigenvector Vn other than v, that signal would always be maintained x even asymptotically.
Proof. Writing recursively, we get that
((++1) =a Σ (1 a) nM X10
W
..,W(O)
m==
x (( ...W!. + (1 - a:) +1 1+
-1)
For each column (f+1) similarly, one can prove by induction that
(++1)
(t.m)
X3"
vi,
m=0
where
x)0,0) V X(O),
(0.0) (0.00))) (1( for all /
[t.m) al1 - a) (1000 - for all 1 S S f
[(.)) (1 (0
Then 199 (1)
= = (0)
Σ a(1 "m ( ... W + (1-1111))) + + w(() m=0
w-(()
(12)
Since by construction, || x = c, it follows from the regularity conditions on weights that
|| x 2|2 2 ce
This implies that
|| (1 2 cc/Vic
which means that there exists E [k] such that
M T x = ce/Vik
18

---

Published as a conference paper at ICLR 2025
Note that since V4 V and v/ 0. get that
(e( = [ 20 x
oo xx 1 X
v /|xx00 20 [x(11 (
9 T x
which means that (x(((()) 2 CE/ Vk. Similarly, we can show that lim, Ho (x(() 2 ce/Vk.
B.3 PROOF FOR PROPOSITION 4.2
Proposition 4.2. Let 2; x ||aalle 1 and let each (W("1), <> 0. |1 1 with probability least p = exp à
N(n,
Then for any
20²
Proof. Notice that | (
1|2 7 (0)
= 1. Using Lemma B.1
we get that ||=]x((0) || > ar
with probability at least 1 exp
From there it is easy to see that that | 1
with probability at least
cxp
222002
B.4 PROPOSITION DETERMINISTIC CASE
We complement 4.2 with the following result. Let V E Raxx be the matrix of eigenvectors of A and define
V* = [ug E 1 (()
=c
V = (up VV:
v/ (0)
= =}}
2
where G2 > for all g. words, V* is the set of eigenspaces A onto which X (() has non-trivial projection, and 1 the set of eigenspaces A onto which (0) has no projection.
Proposition B.4. Under Assumption B.2 for all 2 1,
|r x()
cpc, Vug V*,
= =0, Vvp E V
Under Assumption B.2 2.
lim 100
x(() || > C.c, E v*,
lim t 2
2T x(1)
=0, E Vo.
Proof. The proof follows directly from the form
12
The above result states that the signal excited in the original graph input ( is precisely what stays and the signal that is not excited in (0) can never be created through message-passing.
We give the following concrete example of the above result:
Example Suppose (( (((()
I, then
((++1) a
- a² A + +11 a)+1/(41) x.
k=0
19

---

Published as a conference paper at ICLR 2025
Note that when p(4) < 1/(11 a) such as A= = D-11/-1AA D-1/2 as cc.
lim x a(Ln - (1 -1- (1--))-)--x.
Let (i) be the i-th eigenpair of A and ز1 (UI, x,,) then
x((+1)=
Σ a(1 - a)*² x X + (1-a))th (1+) or,
1=1
and when p(A) 1/(1 - a) such as A D-1/2 1/2
Andj 1-1222
n
lim (1+1) 60000
a
0114.
1 (1 a)
1=1
This implies that for all Pgy
|1 T X
112
a(1 am + +11 aa);N 0g.i
m=1
Σ
a(1 - a) + (1 - 2) 110..112
m=1
and as t - 00,
lim |1 x(01|22 1- (1 a) 11
a
1000
B.5 PROOF OF PROPOSITION 4.3
Proposition 4.3. Let Kr(A, ( = Span(( ( i. hEEM))EEE) be the Krylov subspace. Let
Y E Raxk, Then there exist a T E IN and sequence of weights W(O) w W(T W such that X = Y if and only Y E Kr(A,X(0),
Proof. Set T n, a 0.5 and w((t) for t 0 and (( 0. Begin by unrolling the recursive equation 44
(1) (1- ()- W (x + ax (x)
And in turn:
(2) = (1 a)xx (1) (1) +ax
= =1=o))((1-o44r( -
= 0.5 Ax + 0.5x
Iterating this, yields:
(
0.5 (0
Now consider a single column of (m).
(X(1))
0.5' A-5' (10 ):.
a
Σ
0.5' (W
(i
)1,
A x
2
1=
20

---

Published as a conference paper at ICLR 2025
Now let Y.j E Kr(A, x be in the Krylov subspace. Then Y.,- Σ Ei= A
Setting (W2-1)) )1,5 |
0.5* yields X Y.--
For the other direction, begin similiarly by unrolling the recursive equation:
x2 = (1 - a) a) + axx
(3) )w(") =1 a)A((L - a)Ax w ax w2
+ axx"
(1 (1-ol a1= ~ xx w1 W Wr +11
w + ax wx
Iterating this, yields:
n+1
x())
Σ
A - x x110000)111
==1
Now consider a single column of X(n):
n+1
(x(1)) Σ
A A (
Now, setting Wh,i = W and Y. = Σ/= Eis1 (r(AAX(0).
(0) verifies that x Y.j E
B.6 PROOF FOR PROPOSITION 4.6
Proposition 4.6. Let E RR" s.t. ||lll = 1 and 8² 1 > O. Let Rank #0 (0)) > 1, then there exists <(v) > 0 such that no (x) 2 c(v) for all 2 1 with probability 1.
Proof. We prove this by induction. The base case for holds. Assume Rank (VT x(1) has rank at least 2. Then, there exist at least 2 columns x and x! such that Rank( V x xx
2.
Consider their eigenvector decomposition in terms of eigenvectors of (T 11 /n)A:
x(
x
(1)
1=1
1=1
Consider the action of (1 11 /n)A:
" Σ
x (1-1
Nofffn m.
X (I- /n)
Σ Noo
Since ( and x are linearly independent and the eigenvectors of a symmetric matrix are orthogo-
nal, there exists such that of # #og. with X + 0. This exists because Rank(V [x([] x
2. It follows that (1 Ag # o aq. and thus the centered features X * and neither (t)
nor x 0 (otherwise ((!) would be a 0 eigenvector and be orthogonal to Vye)). Thus, they are linearly independent. Furthermore, x x() 1 are linearly independent, since (T - 11 //mm projects to the space orthogonal to (1. Write:
(1+1)
- 11 (9)
1 k
Σ
( (
r
a=l
Σ
W (() i0
+ -W/?x X9
1
(p())
w:!! X!!! W xT)
r,
21

---

Published as a conference paper at ICLR 2025
We now consider the event that column i collapses to the all-ones space. Notice that dividing the whole column by r does not change whether or not the column has converged to the all-ones space or not. Thus,
A (W() E Rl
X x((1)) = 31}
(W() E R
r. ((( w X W x:3) 31)
((0)
(W(9 E Rl*k |1(0) + w 1 W X = 5
(W() E Rlok |
W X + w x - 8'1 = (0)
Since X .x.3. 1 are linearly independent, given (0()) there is only solution to this equation. .A is
a proper hyperplane in Blak and as such has Lebesgue measure O. The event A thus has probability 0 and the opposite event, that column i does not collapse to the all-ones space, has probability 1.
The same holds for x ((++1) and by the same reasoning, x((++1 and ((+++1 :J are linearly independent
with probability 1. Notice, that thus Rank(V 40 [x((+1) xx(+1)]
2 still holds. Notice that
T x+) because of the centering operation. However, since 1 b>> 0:
| (((11) xx(++1)] 2 -
(e-1) xx(+1) || 6²
This means that:
M (o(x((+)) こ Ho X (e+1) x x
X x(((+1) x((+1) - -.,- [x((+t) x((+1)) ||
(((+)) (++1) - ||| |oo" (((+1) x((+1) ||
2 1
B.7 PROPOSITION 4.6, GENERAL CONDITIONS
We adopt the following regularity conditions:
Assumption B.5. For the system described in assume:
1. For nonzero I E R" such that x 1 Ax & Span(1).
2. If (1)(((()))))) > 0, then (2((AX > 0 for all i E [A]]
Assumption B.5 ensure that the adversarial situation where one step of message-passinng pasaggg automati- cally leads to oversmoothing to the all-one subspace does not happen. Note that this is more relaxed condition than requiring Span(1}- 1 to be an invariant subspace of A.
Assumption B.5 ensures that the case where weights are deliberately chosen for oversmoothing to happen in one layer does not happen, either. Note that for the second condition, such weights exist, i.e. let W(() J.. Moreover, if weights are randomly initialized, then Assumption B.5 2 holds
almost surely.
We restate Proposition 4.6 under general conditions, which accounts for both linear and non- non-linear systems:
Proposition B.6. For the system in (5) suppose o(-) is injective and Assumption holds. Without loss of generality, also suppose the initial features X (0) are centered and all columns are nonzero. Then for u E Rd where v 1 & 0, there exists c(v) > 0 such that Ho (x))) 2 c(u) for all L ' 0.
In particular, the most relevant case of our interest is that the message- passsaiggg A corresponds to an graph operator such as the adjacency matrix (in the case of GIN), or the symmetric random walk
22

---

Published as a conference paper at ICLR 2025
matrix D-1/2AD- 1/2 (in the case of GCN) and is its dominant eigenvector. Under the assumption Theorem implies v is positive and hence v' 1
that the graph is connected, holds.
We prove the statement below:
Proof. For each column in X since it is centered and nonzero, X Span(1}~\(o} for all
i E [k]. Then given Assumption B.5 1, AX $ Span[1} and thus can be written as
AX (0) = al + w
where a E R, w E Span(1) 1 and w * 0.
Then given Assumption B.5 2, AX (0) w:( & Span(1) and since a-)) is injective, o (AA Span (1) and
(AX b1 w
where b E R, w (pan and w # O.
Then after the centering step of batch normalization,
(I /1)x))) wt
and after the scaling step of batch normalization,
X (NX
ll
which means each column of (1) E Span 1 MO0 and has norm 1. Note that the above argument applies for all 2 0 going from (0) to ((+1).
Let cl /n + wyt where # 0, wy E Span (1) and !m 1|3
1 e². Notice that
k
(x((())
Σ
| vo
1, 12 1| T x 113
1=1
k
| (t) 11 [ Tx
m! 11 kc?
where the last inequality is because that (( ((() 1/3 maximized if x!!) and w. aligned. We thus conclude that there exists c(v) such that ue (x((1) 2 c(e) for all t 0.
B.8 PROOF FOR PROPOSITION 4.8
Proposition 4.8. Suppose V, X (0) has rank for all weights W(t), the GNN with BatchNorm given in 5) exponentially converges to the column space of Vv.
Proof. We will prove by induction on that
x(()
1.e Xivi
(13)
((t)
23

---

Published as a conference paper at ICLR 2025
where (i) is the i-th eigenpair of (In - 11 11T //n) with A^ıl 2 |2al 2
|nal, p is the
normalization factor in the t-th round and 0,22 E IR. The base case follows from the decomposition of
(t)
x in the eigenvector basis of (In 11" T /n) A: X Ei= (x n) (and the fact that X normalized).
For the induction step, the system can be rewritten as
x(++1) (1x 11t AX ( /n) diag(... (ar((AX(011)))..))
= (In 11 Ax Dear.
Assuming 13
(Lh, - 11 -1)
1+1
T(0)
1,8 1
vn-
1=1
Further the action of (( is the following:
((h, - 11 T (x)
W
(t) ++] 1,j
A1
n1
I(t)
j=1
11
(W (1) (t)
) +++1
(14)
T(A)
Ju 1.
m
((+1) 1 A V1
(1+1) = Σラ= (W (1) Notice that 0/.6
5. %ij or equivalently, g(+1) D(W() where Σ(1) = [0/,]]
Thus, [(++) (1 W Lastly, the action of D is:
n
(Lh, - 11/1111//A.m 11) Dvac).. Drac):
11 A
(t+1) 1++
11 Σi=
(++1)
X
1
11l22
(t)
1,2
1=1
(t+1)
X 2++ 11
|
Ei= (0)
(1+1) +++ )21
\
(())
1=1
1
(t+1) [+ Ao 1/1
(o= (1+1) X1
y )2
2m1
(1+1) x vn 1s
This concludes the induction. Notice that superscripts in brackets do not denote exponentiation, but rather an iterate at iteration f. Using this intermediate result (13 we show the following:
Lemma B.7. For all q > k.
(
|| x11 S Co
Ax
Proving this directly yields Proposition 4.8 We have that Σ(0) = V (0) due to the base case the induction and by assumption, 2: V (0) E Rle has rank & and is therefore full rank. It is
therefore invertible, meaning that there exists (2:0)) Reec such that V2 x (0) (0)2)))) Lp.
We can thus write for the simplicity of notation:
To w(),
0 - (3:00)) :k:
[2(1)
(
24

---

Published as a conference paper at ICLR 2025
(1) for i S k. Now, let's revisit (14) in that
This has the nice property that oi can write E(++1) g ... w Let y w(- ... W((,, meaning that
0 - W Li ()) We now have everything to conclude the proof:
Consider now, the contribution of an eigenvector Mn with q > k at iteration L.
11 112
Vg
10 Mu
Σ
(o 2g)²
(1)
Ei=1 (
1,1 (1) 29)0
p (o (1)
l0 25)3
(i w 0 put 25)3
w 9d )9)²
E qd X3
F.P 2z)2
(1)
Σ (M
c x3)²
E (M x;)2
Σ 0 qd
2k
Co X1
As we have that Xg < dE by construction, || x + O exponentially as t - 00.
B.9 PROOF FOR PROPOSITION 4.9
Proposition 4.9. Suppose {AAl a sequence of weights (()), W()), ((T) such for all 2 T and E [k].
and V.T (() has rank k. For any > 0, there exists T >> 0 and
| x 2 1/VI++e,
where vs denotes the i-th eigenvector of (T, 11 /n)AA
Proof. The proof idea is simple: we use Gaussian elimination to cancel out all "top-k" eigenvectors but the one in that row and then use the power iteration until the smaller eigenvectors are "drowned out" below the error margin. Assuming the columns of X kk. are linearly independent (which is the case if it has rank k), this leads to the desired output: choose
if i
O0
(0)
if j and i #
J
00
else
Then from 14 for each column X i. get that
12
(0) (0)
(0)
1.
(0)
11
Now for l = 1, the factor
o
0
i,1
(0)
=
yields
0
n
(1)
(0)
)
11)
0
1=2
1
25

---

Published as a conference paper at ICLR 2025
Iterating this idea and choosing
if =
(4)
(k)
if - k: + and i + k: +
clsc,
we arrive
X
1
(i-1)
Σ
oi Nin +
r
1=k+1
Now, we switch gears and use W = In for t > k it follows that
ii X
(1-1)
(x
Violi (i-1) 19)2 + Σn Ei= {1)2
1
Ei (0/
11
(1-
"1))² 29)?
The statement left to prove is thus:
Dl=k+1 (0i, x9)
(K)
(1-1) (f-1) x$)2
(n k) maxi (ox (k) X
(o)
6 2
(ot,7))
X,"
(1-
log
(n-k) max (100
S t.
A1+1 2 2oo
Thus, setting T to be larger than this bound yields the desired claim.
B.10 PROOF FOR PROPOSITION
Proposition B.8. Let A E BEX" be a symmetric non-negative matrix. Let H E {0, 1j such
that AH = A is the coarsest EP of A. Divide the eigenpairs V = {..., (A, v),... of into the
following two sets: Vstruc ((),v)
v Hu"), Vrest VV,V Let D (..., (2, ..... be
eigenpairs of (In -11 An) for # 0. Then
1. Vnsa CV.
2. Assume Varue # {(A,1)} Let (),v) be the dominant eigenpair of A. Then not an eigenvector of (In 711 /n)A.
3. Exx,y >> E(j
Proof. Let H (0, 1m indicate the coarsest EP of A - HAT). As each node belongs to exactly class, it holds that H1, 1m We prove that for any eigenpair (2, v) E Vrest it holds that T O. From this, the first statment follows quickly:
(In -11 /n) Av TI1T Av/n
AI1TAAln = Av - v/n Av.
To prove this, let's look at AT A is not symmetric, but its eigenpairs are associated to A's eigenpairs in the following way. Let (A, vT) be eigenpair of A", then (A, Hv*) is eigenpair of A:
AHv HA* = HA As is a symmetric matrix, its eigenvectors are orthogonal implying (Hv)) (Hx))
26

---

Published as a conference paper at ICLR 2025
Lemma B.9. The eigenvectors vf,,.., Vin of A are linearty independent.
For simplicity, choose the eigenvectors vf be normalized in such a way, that (Hu)) (HH,)
(Hu)) )=
Suppose for contradiction, that they linearly dependent and without loss of generality, V E a Take j such that 0j A O, this must exist otherwise V/n 0. Now,
m
m-
(Hum) (H)))) (H Σ ana THz)) - Σ (Haw)) = aa 20,
which is contradiction.
Since the cigenvectors of A" are linearly independent, there exists a unique 3 1m s.t. Ei=1 B.17
mm Finally let yo Vrest:
1n x ==-T H1m =
Σ Bav = Σ
Bup Hv; = 0.
1=1
This concludes the proof of the first statement.
To prove the second statement, let (A.)) be dominant eigenpair of A. such that v 0 is non- negative. This exists as A is non-negative matrix. Additionally, // is not the all-zeros vector and as such 1 T v > By assumption + 1. Then:
(1 - -11
(-111/nAAur Au = Āv = Au -11 -11-Au/n = = (A Å)v - - v/n -AIII 0.
As v + 1, there exist i, s.t. us * Uj thus, (A- Å)es - TA(1 v)s/n = and (A \)e5 *A(11 (11TT))//n
cannot be true at the same time. Thus, this equation has no solution and not an eigenvector of (In 711 /n)
For the third and final statement, notice that the trace of A is larger than the trace of ( 71 /n) Since the trace of matrix is the sum of its eigenvalues, we have
Σ x= Tr((I, r11 /n)A) (N.)EV
Σ A
(Á,))
Consequently,
Σ
A+
A>
X+
A=
Σ A.
(A,))V
(A,v)EVane
(i.D)EViVoe
(A,v)EVes
((.P)
Subtracting E E(i À from both sides yields the final statement.
27

---

Published as a conference paper at ICLR 2025
C EXPERIMENTS
We compare these models using the measures of convergence: (x(()) as defined in where in this case for GATs and GINs, the dominant eigenvector v 1/ n, the numerical rank the features Rank(XX (+)))), the column distance used (Zhao Akoglu 2020
1 d²
X
X
deal (X)
Σ
I 11
i
the column projection distance:
apccll (X) ==
1
Σ
XT
X
d2
X l
| ll
W
and the eigenvector space projection:
dev (x) = x - VV x X
where Rax is the set of normalized eigenvectors of A, and finally, the rank of X: Rank(X).
Datasets
We provide summary statistics for datasets used in experiments in Section in Table
Table 2: The summary statisties of the datasets used in Section 6
Dataset
#graphs
#nodes
#edges
#features
classes
MUTAG
188
17.9
39.6
7
PROTEINS
1,113
~39.1
145.66
3
PTC-MR
344
14.29
14.69
18
2
Cora
1
2.708
10,556
1,433
Citeseer
1
3,327
9,104
3,703
ogbn-arxiv
1
169,343
1,166,243
128
40
Training details We perform within-fold 90%/10% train/validation split for model selection. We train the models for 200 epochs using the Adam W optimizer and search the hyperparameter space over the following parameter combinations:
learning rate E {10-1, 10-3,00000000 1,1101100,,,,,,...111111111 10-11
feature size E {32, 64]
weight decay E {0, 10 2,104
number of layers (3, 5)
We select the hyperparameters of the model with the best validation accuracy its 30 best epochs. The code and all non publicly available data is available here
Compute We ran all of our experiments on a system with two NVIDIA L40 GPUs, two AMD EPYC 7H12 CPUs and 1TB RAM.
Licenses
PyG (Fey
Lenssen 2019): MIT license
OGB (Hu et al. 2020): MIT license
ogbn-arxiv: ODC-BY
28

---

Published as a conference paper at ICLR 2025
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 LONG-TERM MODEL. PERFORMANCE
Clasilication Acturacy by Medal Depth
70
60-
grastw2
16
15
20
25
36
Figure 2: Long-term behavior GCN performance. Classification accuracy and standard deviation of GCN models of varying depth. The x-axis show the depth of the GCN while the axis shows classification accuracy and standard deviations.
D.2 NODE CLASSIFICATION PERFORMANCE ON HETEROPHILIC GRAPHS
It is worth noting that theoretical results in the paper hold for any initial features and any target labels and thus hold for datasets exhibiting either homophily or heterophily and even those that are not necessarily either of the two. In particular, the graph-level tasks present in Section can be seen as heterophilic (in terms of nodes features while the targets are neither). We can see in those cases, GraphNormv2 also performs well.
For the node classification task, we conduct additional node classification experiments using GCN as the backhone the heterophilic dataset Coreell Pei al., (2020), using the default splits provided in PyG. The results are shown in Table 3 We see that our method, GraphNormy2 still performs competitively with baseline methods and outperforms the baselines in the deep architecture regime.
Table Performance on heterophilic graphs. Performance GCN with different normalization layers on the heterogeneous node classification dataset Cornell, Results are reported as the mean accuracy (in %) + std. over 10 independent trials and the 10 fixed splits. Best results are highlighted in blue; second best results are highlighted in gray.
Node Classification
Node Classification (# layers=20)
Cornell
Cornell
norm
50.9 6.2
47.4 4.4
batch
50.1 4.4
45.7 +: 4.9
graph
52.8 3.5
4.6
GCN
pair
47.0 5.2
44.9
group
52.8 4.0
49.8 4.4
powerembed
50.8 + 5.4
48.8 + 5.4
graphv2
52.2 1: 4.2
51.0 1 4.2
29

---

Published as a conference paper at ICLR 2025
Table 4: Performance of GraphSAGE, under different normalization layers. Performance of GraphSAGr with different normalization layers on the node classification dataset Cora. Results are reported as mean accuracy (in %) + std. over 10 independent trials and 5 folds. Best results are highlighted in blue; second hest results are highlighted in gray.
Node Classification
Node Classification (# layers=20)
Coru
Cora
norm
85.0 + 0.7
83.3 1.2
batch
32.1 5.8
30.1 3.8
gruph
30.9 + 4.7
30.1 3.8
GraphSAGE
pair
32.7 4.3
29.7 5.2
group
S7.2 0.7
85.6 0.9
poweremhed
86.3 0.8
85.2 0.6
graphy2
55.1
D.3 NODE CLASSIFICATION PERFORMANCE GRAPHSAGE BACKBONE
For the node classification task, we conduct additional node classification experiments using Graph- SAGE Hamilton et al. (2117) as the backbone under the same cross-validation setup specified the paper (see Section The results are shown in Table +
Our method, GraphNormv2 still performs competitively with baseline methods and outperforms the baselines in the deep architecture regime. Note that the message- operator for GraphSAGE is a row-stochastic matrix, hence dominant cigenvector is the all-ones vector. We suspect that this might be the case why BatchNorm and GraphNorm perform poorly with this backbone, their centering step uses the all-ones vector and thus distorts the graph signal as discussed in Section of the paper.
30


Reviews:
[{"review_id": "6kQcSPzidh", "reviewer": "Reviewer_DmVD", "summary": "This paper provides a theoretical foundation for understanding how residual connections and normalization layers affect oversmoothing in GNNs. It offers a detailed analysis of the mechanisms behind these techniques and proposes a new normalization layer that enhances the expressive power and performance of GNNs. The contributions are supported by both theoretical proofs and empirical evaluations.", "questions": "1. From Figure 1, we can see that residual connection performs better than other normalizations (even graphnorm2).  So why use normalization layers? It seems that the residual connection is enough to prevent oversmoothing. GCNII can perform well under very deep architectures [1], but the performances of different normalization layers decrease.Results in Table 1 valide this.\n   \n2. Some results in Table 1 are strange. The performance of GIN with BatchNorm,PairNorm, GraphNorm, PowerEmbed and GroupNorm are not better than no norm on ogbn-arxiv, and worse than no norm very much for #layer=20 (6% v.s. 25.7). Is there any mistake? If the results are correct, this is confusing. Section 4.2 states that batch normalization is able to prevent collapse, but its performance is worse than no norm.\n\n[1] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph\nconvolutional networks. In ICML, 2020.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. It provides a thorough theoretical analysis of oversmoothing for residual connections and normalization layers. \n2. The paper introduces a novel normalization layer that addresses a specific limitation of existing methods. The method is simple but effective. Random weights", "weaknesses": "1. The analysis is conducted only on linearized GNNs (except Remark 4.6) with random weights.   \n    a. Most GNNs are nonlinear, so we are more concerned with the properties of GNNs under nonlinearity. Can the analysis be generalized to nonlinear cases? \n    b. Random weights usually appear during initialization. A network may have bad properties when it is initialized and good properties when it is trained, so we are more concerned about the trained GNNs which weights are not random.\n\n2. The results for residual connections are not surprise. In equation (4), the update rule uses initial residual connections $\\alpha X^{(0)}W_2^{(t)}$. In most cases ($W_2 ^ {(t)} $is not particularly bad), $X ^ {(t)} $contains $X ^ {(0)} $, will therefore not be collapsed. So the results are pretty obvious.\n\n    For Proposition 4.2, if $x_i=0$, The conclusion is not valid. Please state the proposition strictly. For Proposition 4.3, I think it is smillar to Theorem 2 in GCNII [1], which is just a different statement. It is better to cite the relevant conclusions.", "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": "", "extra_scores": {}}, {"review_id": "EKH8ubSsQj", "reviewer": "Reviewer_fLzt", "summary": "Residual connections and normalization layers are commonly used layers in deep learning. \nThe paper provides a theoretical analysis of the roles of residual connections and batch normalization in graph neural networks (GNNs) to mitigate the over-smoothing phenomenon. \nFurthermore, it introduces a new normalization layer, GraphNormv2, which demonstrates enhanced performance in both graph classification and node classification tasks.", "questions": "Refer to the content in the Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1). The writing and organization of this paper are very clear.\n\n2). Provided theoretical support for the use of residual connections and normalization layers in GNNs.", "weaknesses": "1). The standard deviations for MUTAG, PROTEINS, PTC-MR, and Cora in Table 1 are quite large, making the experimental results less convincing, and why are the standard deviations for GIN so large? Why graphv2 does show significant improvement for GIN on the ogbn-arxiv dataset, but not for GCN and GAT?\n\n2). Could you add a curve that shows the performance changes of different baselines and GraphNormv2 as the number of layers in GNNs increases?\n\n3). There is an error in line 118.", "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": "", "extra_scores": {}}, {"review_id": "aCxNti1NTc", "reviewer": "Reviewer_Kctt", "summary": "Residual connections and normalization layers are commonly used in GNN models in order to hinder the oversmoothing phenomenon. Although successfully supported by empirical results, no theoretical investigations were undergone to explain this improvement. The authors of this paper bridge this gap and provide a better understanding as to why these heuristics are effective against oversmoothing.\n\nFurthermore, backed by their findings, they propose a novel normalization layer that circumvents the highlighted limitation of existing approaches, namely the alteration of the information carried by the graph signal upon normalizing. Finally, extensive experiments are conducted, in support of their findings.", "questions": "Please refer to the Weaknesses section.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The presentation is very clear, with a nice balance of theoretical investigations coupled with empirical evaluations. The exposure is gradual, with relevant connections to existing literature. I really enjoyed reading this paper.\n\nThe technical results are detailed and extensive.\n\nThe authors conduct experiments on various real-world datasets, and the presented results display convincing performance.", "weaknesses": "The theoretical investigations consider the simplified setting of linearized GNNs. As mentioned in the paper, I acknowledge that you already consider bridging this gap in future work. Would it be possible to provide some insights into what specific challenges do you anticipate in extending the analysis to non-linear GNNs ?\n\nYou show that residual connections and normalization layers help against oversmoothing through different mechanisms. Do you think it would it be possible to quantify which of the two has the most significant impact against the oversmoothing phenomenon (be it through bounds or empirical measurement ) ?", "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": "", "extra_scores": {}}, {"review_id": "oz48ed1M1s", "reviewer": "Reviewer_JBkc", "summary": "This paper provides a formal and precise theoretical analysis of linearized Graph Neural Networks (GNNs) with residual connections and normalization layers. Notably, it reveals how the centering step in normalization can modify the message-passing mechanism of graph signals. Building on this insight, the authors propose a novel, theoretically-grounded normalization layer, GraphNormv2. Experimental results support the efficacy of GraphNormv2, showing its ability to enhance performance across diverse GNN architectures and tasks.", "questions": "Please see the weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents valuable contributions by providing a theoretical foundation that enhances understanding of existing techniques for addressing the oversmoothing problem and informs the design of novel normalization layers in GNNs, notably GraphNormv2. The work is well-written, concise, logically structured, and easy to follow, making it accessible to a broad audience. Additionally, the experimental evidence supports the effectiveness of GraphNormv2 across various GNN architectures and tasks.", "weaknesses": "The experimental results are limited and do not sufficiently support the paper's claims, particularly regarding the effectiveness of GraphNormv2 across diverse GNN architectures and tasks.\n\n1. The authors test their method solely on homophilic graphs, limiting the generalizability of their findings. Is there any rationale reason for choosing only homophilic datasets? The oversmoothing problem is particularly pronounced in heterophilic graphs, so it would be valuable to evaluate GraphNormv2 on heterophilic datasets as well. I suggest including experiments on heterophilic datasets such as Texas, Cornell, and at least one large-scale dataset, like Arxiv-year, to better demonstrate the robustness and effectiveness of GraphNormv2 across diverse graph structures.\n\n2. Additionally, whether the theoretical analysis suggests any potential challenges or differences in applying GraphNormv2 to heterophilic graphs compared to homophilic ones? \n\n3. The proposed method is tested on a limited range of GNN architectures, specifically GCN, GAT, and GIN. However, other types of GNNs, such as GraphSAGE and diffusion-based models like Graph Diffusion Networks (GDNs) and Diffusion Convolutional Neural Networks (DCNN), are also susceptible to oversmoothing. So, whether theoretical analysis does suggest any potential challenges or differences in applying GraphNormv2 to heterophilic graphs compared to homophilic ones? If not, testing GraphNormv2 on a broader set of GNN architectures would provide a more comprehensive evaluation and further validate its effectiveness across diverse model types.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)