Graph Neural Networks Do Not Always Oversmooth
Authors: Bastian Epping
Alexandre René
Moritz Helias
Michael T Schaub
Venue: NeurIPS 2024 poster (2024)
Keywords: graph neural networks
oversmoothing
Gaussian processes
chaos
Primary area: graph_neural_networks
TL;DR: We adapt the chaos analysis from deep feedforward neural networks to graph neural networks and reveal a parameter regime in which graph neural networks do not oversmooth.

Abstract: Graph neural networks (GNNs) have emerged as powerful tools for processing relational data in applications. However, GNNs suffer from the problem of oversmoothing, the property that features of all nodes exponentially converge to the same vector over layers, prohibiting the design of deep GNNs. In this work we study oversmoothing in graph convolutional networks (GCNs) by using their Gaussian process (GP) equivalence in the limit of infinitely many hidden features. By generalizing methods from conventional deep neural networks (DNNs), we can describe the distribution of features at the output layer of deep GCNs in terms of a GP: as expected, we find that typical parameter choices from the literature lead to oversmoothing. The theory, however, allows us to identify a new, non-oversmoothing phase: if the initial weights of the network have sufficiently large variance, GCNs do not oversmooth, and node features remain informative even at large depth. We demonstrate the validity of this prediction in finite-size GCNs by training a linear classifier on their output. Moreover, using the linearization of the GCN GP, we generalize the concept of propagation depth of information from DNNs to GCNs. This propagation depth diverges at the transition between the oversmoothing and non-oversmoothing phase. We test the predictions of our approach and find good agreement with finite-size GCNs. Initializing GCNs near the transition to the non-oversmoothing phase, we obtain networks which are both deep and expressive.

Graph Neural Networks Do Not Always Oversmooth
Bastian Epping', Alexandre René', Moritz Helias?:3, Michael T. Schaub
RWTH Aachen University, Aachen, Germany
*Department of Physies. RWTH Aachen University, Aachen, Germany
Institute for Advanced Simulation (IAS-6), Computational and Systems Neuroscience, Jülich Research Centre, Jülich, Germany eppingecs -acheaccnnn de, reneêcs wwth-aachenn de, m. hhellas@fzz-uelich.hoo schaubEcs. wwth-aachen.de
Abstract
Graph neural networks (GNNs) have emerged powerful tools for processing relational data in applications. However, GNNs suffer from the problem of over- smoothing, the property that features of all nodes exponentially converge the same vector over layers, prohibiting the design of deep GNNs. In this work we study oversmoothing graph convolutional networks (GCNs) by using their Gaus- sian process (GP) equivalence in the limit of infinitely many hidden features. By generalizing methods from conventional deep neural networks (DNNs), we can describe the distribution of features at the output layer of deep GCNs in terms GP: as expected, we find that typical parameter choices from the literature lead to oversmoothing. The theory, however, allows to identify new, non- oversmoothing phase: the initial weights of the network have sufficiently large variance, GCNs do not oversmooth, and node features remain informative even at large depth. We demonstrate the validity of this prediction in finite-size GCNs by training linear classifier their output. Moreover, using the linearization the GCN GP, we generalize the concept of propagation depth of information from DNNs to GCNs. This propagation depth diverges at the transition between the oversmoothing and oversmoomooonn phase. We test the predictions of our approach and find good agreement with finite-size GCNs. Initializing GCNs near the transition to the non-oversmoothing phase, we obtain networks which are both deep and expressive.
Introduction
Graph neural networks (GNNs) reach state of the art performance in diverse application domains with relational data that can be represented on a graph, transferring the success of machine learning Despite their good performance, GNNs come with the limitation of oversmoothing, a phenomenon where node features converge to the same state exponentially fast for increasing depth [35 45
data graphs [47 12 23
2 Consequently, only shallow networks are used practice [19 M In contrast, it is known that the depth (i.e. the number of layers) is key to the success of deep neural networks (DNNs) 2
30
33 While for conventional DNNs shallow networks are proven be highly expressive 6 in practice deep networks are much easier to train and are thus the commonly used architectures 36 Furthermore, in most GNN architectures each layer only exchanges information between neighboring nodes. Deep GNNs are therefore necessary to exchange information between nodes that are far apart the graph 9 In this study, we investigate oversmoothing graph convolutional networks (GCNs) [9]
To study the effect of depth, consider the propagation of features through the network: given some input xa each intermediate layer produces features x which are fed to the next layer. We
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

follow the same approach that has successfully been employed in previous work to design trainable
DNNs 137 consider two nearly identical inputs va and 2 (0) and ask whether the intermediate features vn and 3 become more or less similar as a function of depth I. In the former case, the inputs may eventually become indistinguisaable. In the latter case, the inputs become less similar over layers: the distance between them increases over layers [32 37) until eventually it is bounded by the non- non-lincarittes of the network. The distance then typically converges to a fixed value determined by the network architecture, independent of the inputs.
One can therefore identify two phases: One says that network is regular if two inputs eventually converge to the same value as function of I; conversely, one says that a network is chaotic if two inputs remain distinct for all depths 24. Neither phase is ideal for training deep networks since in both cases all the information from the inputs is eventually lost; the typical depth at which this happens is called the information propagation depth. However, this propagation depth diverges at the transition between the two phases, allowing information - in principle - to propagate infinitely deep into the network. While these results are calculated in the limit of infinitely many features in each hidden layer, the information propagation depth has been found to be a good indicator of how deep a network can be trained [37]. A usual approach for conventional DNNs is thus to initialize them at the transition to chaos. Indeed, Schoenholz et al. [37] were able to use this approach to train connycoonee feedforward networks with hundreds of layers. Similar methods have recently been adapted to the study of transformers, successfully predicting the best hyperparameters for training [5].
In this work we address the oversmoothing problem of GCNs by extending the framework described above in the limit of infinite feature dimensions from DNNs to GCNs: here the two different inputs (0) ..()) and 3 correspond to the input features on two nodes, labeled a and 3. The mixing of information across different nodes implies that output features on node a depend on input features on (1) independently node B and vice versa. Thus it is not possible to look at the distance of x& and x for each pair a and B as in the DNN case. Rather, one has to solve for the distance between each distinct pair of nodes in the graph simultaneously: the one dimensional problem for DNNs thus becomes a multidimensional problem for GCNs. However, by linearizing the multidimensional GCN dynamics, we can generalize the notion of information propagation depth to GCNs: instead of being a single value, we find that given GCN architecture comes with set of potentially different information propagation depths, each corresponding to one eigendirection of the linearized dynamics of the system.
This approach allows us to extend the concept of a regular and a chaotic phase to GCNs: in the regular phase, which describes most of the GCNs studied in the current literature, distances between node features shrink over layers and exponentially attain the same value. We therefore call this the oversmoothing phase. On the other hand, if one increases the variance of the weights at initialization, it is possible to transition into the chaotic phase. In this phase, distances between node features converge to fixed but finite distance at infinite depth. The convergence point is fully determined by the underlying graph structure and the hyperparameters of the GCN and may differ for different pairs of nodes. GCNs initialized in this phase thus do not suffer from oversmoothing. We find that the convergence point is informative about the topology of the underlying graph and may be used for node classification with GCNs of more than 1, 000 layers. Near the transition point, GCNs at large depth offer a trade-off between feature information and information contained in the neighborhood relation of the graph. We test the predictions of this theory and find good agreement in comparison to finite-size GCNs applied to the contextual stochastic block model [8]. On the citation network Cora 19 reach the performance reported in the original work by Kipf and Welling [19 beyond 100 layers. Our approach applies to graphs with arbitrary topologies, depths, and non- linearirasss
2 Related Work
Oversmoothing is well-known challenge within the GNN literature 21] On the theoretical side, rigorous techniques have been used to prove that oversmoothing inevitable. The authors in [30] show that GCNs with the ReLU non-linearity exponentially lose expressive power and only carry information of the node degree in the infinite layer limit. While the authors notice that their upper bound for oversmoothing does not hold for large singular values of the weight matrices, they do not
2

---

identify a non-oversmoothing phase in their model. These results have been extended in 2 to handle non-linearities different from ReLU. Also graph attention networks have been proven to oversmooth inevitably 455. Their proof, however, makes assumptions on the weight matrices which, as we will show; exclude networks in the chaotic, non-oversmoothhin phase.
On the applied side, a variety of heuristics have been developed to mitigate oversmoothing 44 4 3
22 40 [S]. E.g., the authors in [49 introduce a normalization layer which can be added variety of deep GNNs to make them trainable. Another approach is to introduce residual connections and identity mappings, directly feeding the input to layers deep in the network 4 46]. Other studies suggest to train GNNs to limited number of layers to obtain the optimal amount of smoothing
[8] (6). The recent review [17] proposes unified view to order existing heuristies and guide further research. While these heuristics improve performance at large depths, they also add to the complexity of the model and impose design choices. Our approach, on the other hand, explains why increasing the weight variance at initialization is sufficient to prevent oversmoothing.
3 Background
3.1 Network architecture
In this paper we study a standard graph convolutional network (GCN) architecture [9 with an input feature matrix X (0) E Nxdo, where N is the number of nodes in the graph and do the number of input features. Bold symbols throughout represent vector matrix quantities in feature space. The ww structure of the graph is represented by a shift operator A E R NNN,, We write the features of the
network's 1-th layer as (1) Nx:; they are computed recursively as
x ((AX""-)w(( + +16()),
with & elementwise non-linear activation function, (0) optional bias term, weight matrices ( R4xxd-1, and 1 E T vector of all ones. We note that many GNN architectures studied in the literature are unbiased, which can be recovered by setting (()) to zero. We use noisy linear readout, so that the output of the network is given by
Y = AX ((+1) + (T+HI) +6,
(2)
with RR-xxds being independent Gaussian random variables: Ca,i i.dd NO oo.). The readout noise E is included both to promote robust outputs and to prevent numerical issues in the matrix inversion in Equations
and (2)
We use dL+1 to denote the dimension of outputs.
For the following it will be useful consider the activity of individual nodes. To avoid ambiguity in the indexing, we use lower Greek indices for nodes and upper Latin indices for layers. We thus
rewrite ① as
x (1) = ()h
(3)
(1) EAA
Aas W
(1-1) 2
+
(4)
B
(1+1) cc,, yn h
(5)
where a. E Re is the feature vector of node a in layer and ya E Rd the network output for node a. The values h((") E Rd: are linear functions of the features x3 (1-1) and represent the input to the activation functions; we therefore refer to them as preactivations. The non-linearity o(x) is applied elementwise to the preactivations (1))) While we leave ((x) general for the development of the theory, we use (xx) = @rf(( x) for the experiments in Section 4 this choice allows us to carry certain integrals analytically. The scaling factor in the erf is chosen such that de (0) 1. We use Dz
independent and identical Gaussian priors for all weight matrices and biases, (!( (I) L.d. AO0
d and di
ij
(1) iid. N(O0, o with (!()) i and bi" being the matrix or vector entries of (1()) and (1), respectively. As shift operator, we choose
I-I- dmax
(D A),
(6)
3

---

where A is the adjacency matrix, I the identity in RNV'N. Da3== = daß E,A,, is the degree matrix and dmax is the maximal degree. The parameter 9 (0, 1) allows us to weigh the off-diagonal elements compared to the diagonal ones. By construction the shift operator row-stochastic, which means that it has constant sums over columns Σg Aus 1. We will make use of this property in our analysis in Section 4.2 The generalization to non-stochastic shift operators will be shortly addressed later.
3.2 Gaussian process equivalence of GCNs
In a classic machine learning setting, such as classification, one draws random initial values for all parameters and subsequently trains the parameters by optimizing the weights and biases minimize a loss function. This learned parameter set is then used to classify unlabeled inputs. In this paper take Bayesian point of view in which the network parameters are random variables, inducing probability distribution over outputs which becomes Gaussian in the limit of infinitely many features.
Thus infinitely wide neural networks are equivalent to Gaussian processes (GPs) (27 43 34), In the study of DNNs this is standard approach, yielding results which empirically hold also for finite-size networks trained with gradient descent 37
has been shown that also the GCN architecture described in Section is equivalent to GP in the limit of infinite feature space dimensions, d; - co for all hidden layers I = I,..., L, while input and readout layer still have tunable, finitely many features. In the GP description, all features are Gaussian random variables with zero mean and identical prior variance in each feature dimension. The description of the GCN thus reduces to a multivariate normal,
In previous work (8 14 29
H ((),
where (1)) is the vector of hidden node features of layer H (h
11) 11 ..... NN under the
prior distribution of weights and biases. The covariance matrices K(O E RNN are determined
recursively: knowing that the (1) follow a zero-mean Gaussian with covariance (hg (1)) K/( we define
(1)
c0 - (o
(
(1 Φ h
(8)
For simplicity we use <(x) = erf( v x) for which Equation 8 can be evaluated analytically; see Appendix A for details. It follows from )3) that
2
k-(++1) of + 0 Σ
Aay Aon Ass
7.8
as shown in 28
In semi-supervised node classification setting, we split the underlying graph into Niest unlabeled test nodes and Artrain labeled training nodes (Ntest + N N); we correspondingly split the output random variable Y; E TR for output dimension i into Y, E R.viess and Y.P E N Features on the test nodes are predicted by conditioning on the values of the training nodes: p(Y =
Vf Y.P = vP) This leads to the following posterior for the unobserved labels (see 34 20 for details):
Y N(m GP KGP),
(10)
(L+1) mi GP (L+1) (K DD + +1000)
(11)
KGP = k(L+1) - K(L+1) (K(( + IIo (K(bt1))
(12)
Here the * and D indices represent test and training data, respectively, i.e. KDD E g N Xttriin is the covariance matrix of outputs of all training nodes and K.D N.Ntex is the covariance between test data and training data. Finally, I here the identity in R Ntrain Nerain
3.3 Feature distance
To measure and quantify how much given GCN instance oversmoothes we use the squared Fuclidean distance between pairs of nodes, and normalize by the number of node features dj that the measure

---

stays finite in the GP limit d; - co. This allows us to quantitatively test the predictions of our approach on the node-resolved distances of features. To summarize the amount of oversmoothing across the GCN, we also define the measure (xX) as the average squared Euclidean distance across all pairs of nodes:
d( xz) = di
||
x = C + Cass 2C%
(13)
N
N
(xX) 2N(N
d(Ea. 2z).
(14)
o= B=a+1
Here C,33 = "u is the normalized scalar product. We use the notation Ca to avoid confusion with the expectation value Cas defined in the GCN GP (8. In the infinite feature dimensions limit, the quantities C, in Equation (14) converge to the GCN GP quantities Ca. defined by (8). In the following sections will therefore use the Cas as predictions for the Ca of finite-size GCNs. The normalization for d( 2tg) and p ((X) can be interpreted an average (squared) feature distance, independent of the size of the graph and the number of feature dimensions.
d.
4 Results
4.1 Propagation depths
We are interested in analyzing GCNs at large depth. We priori assume that at infinite depth the GCN converges to an equilibrium in which covariances are static over layers K-() L+00, Kag- irrespective whether the GCN is in the oversmoothing or the chaotic phase. A posteriori we show that this assumption indeed holds. Since the fixed point K is independent of the input, GCN at cquilibrium cannot use information from the input to make predictions (although, as we will see, in the non-oversmoothing phase it can still use the graph structure), In the following analyze the equilibrium covariance KT to which GCNs with different o² of and A converge to, how they behave near this equilibrium, and which rate it is approached.
Close to equilibrium, the covariance matrix (1) can be written as a perturbation around K
K ap ag + A (1)
(15)
03
Under the assumption that the perturbation
(1) 0g
is small, we can linearize the GCN GP
(1+1) ag
Σ
Has 9d + (((A))))
(16)
7.6
Ooog [Ko9] akns
Ha8.76
w
2
(1 87 And A
(17)
0.6
where we use square brackets to denote the point around which we linearize. The factor {1 (1+55,, 8,,,) is introduced to correctly count on- and off-diagonal elements of the covariance matrix, while the shift operators A and the derivative 0k,s [Ke]] originate from the message passing and the con-linear 8Cee
aCuş
6, respectively. The latter would result in a Kronecker delta 0K,, [K*9]] = 8øs.76 for linear networks.
The calculation for Hap.y8 is done in detail in Appendix B
A conceptually similar linearization has been done [37 for DNNs. In the DNN case, different inputs to the networks- correspond to input features on different nodes here-can be treated separately, leading to decoupling of Equation (6)). The shift operator in the GCN dynamics, in contrast, couples features neighboring nodes - the matrix Ha is in general not diagonal.
We can still achieve a decoupling by interpreting Equation [6 as a matrix multiplication, if a and yo are understood as double indices, and by finding the eigendirections of the matrix Hl E V Taking the right eigenvectors v' as basis vectors, we can decompose the covariance matrix A a/8
Σ, A (1) vi0 and thus obtain the overlaps A which evolve independently over layers. If the fixed
5

---

point K is attractive, all eigenvalues have absolute values smaller than one: |4 < 1. This allows us define the propagation depth & == [n for each eigendirection, very similar to the DNN
case 37 In this form, the linear update equation (6) simplifies to
A ((+d) A 1 exp(-d/(.)4)
(18)
thus decoupling the system. For details on the linearization and some properties of the transition matrix H refer to Appendix B
4.2 The non-oversmoothing phase of GCNs
In this section we establish the chaotic, non-oversmoothing phase of GCNs, and show that this phase can be reached by simple tuning of the weight variance T at initialization. We start by noticing that a GCN is at a state of zero feature distance ()x()) = O, if the covariance matrix has constant entries, K, k((); Constant entries in (-()) imply that all preactivations are the same, h h which in turn implies C.2y cl (by Equation 8 the latter is equivalent features being the same, Fa 2// Due to our choice of the shift operator, the state of zero distance (and thus of K( 1))) always a fixed point. Assuming that C.I) c()), we obtain
k(( aB = o + o Σ Aan Σ Ass cl') ((++))
(19)
In an overmoothing GCN, this fixed point is also attractive, meaning that also pairs of feature inputs x:0), x000) which initially have non-zero distance d(xa x (0) + 0 (and thus μ (0) * 0)
eventually converge to the point of vanishing distance. The chaotic, non-oversmoothing phase of
GCN is determined by the condition that this point of constant covariance K. = k(()) becomes unstable. More formally, this can be written in terms of eigenvalues of the linearized dynamics as
max max {AP 3 1.
(20)
Here and in the following we will use the superscript p to denote that the linearization is done around the state of constant covariance across nodes in both the oversmoothing and non-oversmoothing
phase. The propagation depth &, == in(A.) diverges the phase transition where one X; approaches Intuitively speaking, Equation (20) asks whether small perturbation from the zero distance case diminishes (max{[Ap]]) < 1), in which case the network dynamics is regular, or grows (max [AP]]] > 1). in which case the network is chaotic and thus does not oversmooth. The value of max[[A?]
depends on the choices of A, o2 and of (by the dependence of Kee on of)). In the following we will concentrate on tuning o3 to reach the non-oversmoothing phase.
4.2.1 Complete graph
To illustrate the implications of the analysis described above, we first consider particularly simple GCN on a complete graph; this allows us to calculate the condition for the transition to chaos analytically, and gain some insight into the interesting parameter regimes. Moreover, we this pedagogical example to show that although the GP equivalence is only true in the limit of infinite hidden feature dimensions, dj + co, our results still describe finite-size GCNs well.
For a complete graph with adjacency matrix Ang = 1 - 6,g, our choice of shift operator in (6) has entries A.g = = + Sa ) This model is a worst- scenario for oversmoothing, since the adjacency matrix leads to inputs that are shared across all nodes of the network. We make
the ansatz that the equilibrium covariance is of the form _ K S0 (Kea Ke9) due to
symmetry which reduces the problem to only two variables. In this formulation methods as in the DNN case [37] to determine the non-oversmoothing condition on the h. in (20) (Details are given in Appendix C).
similar
Figure shows how a GCN on a complete graph can engineered be non-oversmoothing by simple tuning of the weight variance o Panel a) shows that increasing the weight variance og or decreasing

---

b)
HD0 equilibrium
1.0
0.15
0.15
1.0
0:10
0h 0.10
distance
0.5
0.5
0.05
0.0
0.00
0.00
0.0
2.5
5.0
7.5
2.5
5.0
7.5
100
10a
10a
10*
layer
Figure 1: Simulations and GP prior of GCN on a complete graph with N nodes, shift operator Ng An -ー1 + 6n N-I ) vanishing bias of = 0 and xxx) = erl( ()) a) The phase diagram dependent on d and g. The equilibrium feature distance μu (x()) obtained from computing the GCN GP prior for L = 4, 000 layers is shown as a heatmap, the red line is the theoretical prediction for the transition to the non-oversmoothing phase. b) Same as in a) but color coding shows whether μe( (()) is close to zero (black) or not (white) with precision 10 10-5, 10-5, The red line again shows the theoretically
predicted phase transition. e) Feature distance μu( ((X"! (1) for random input X (0) L.d. AT 1) as function of layer I. Parameters are written in the panel in matching colors and marked with color coded crosses in the phase diagram in panel b). Feature dimension of the hidden layers is di = 200,
crosses show the mean of 50 network realizations, solid curves the theoretical predictions.
the size of the off-diagonal elements g both shift the network towards the non-oversmoothing phase. Both parameters also increase the equilibrium feature distance beyond the transition. The theoretical prediction for the transition is calculated in Appendix C and shown as the red line. Panel b) confirms the accuracy of this calculation. Larger values of g increase smoothing, and thus larger values of o are needed to compensate. Moreover, our formalism allows us to predict the evolution of feature distances over layers correctly, as can be confirmed in panel c). We find again that GCNs with parameters past the transition do not oversmooth.
4.2.2 General graphs
For general graphs, the transition the oot-oooormoooiingggggmm phase given by Equation 20 can be determined numerically. As a proof of concept, we demonstrate this approach for the Contextual Stochastic Block Model (CSBM) g a common synthetic model which allows generating graph with two communities and community-wise correlated features on the nodes. Pairs of nodes within the same community have higher probability of being connected and have feature vectors which are more strongly correlated, compared with pairs of nodes from different communities.
Given the underlying graph structure, we can construct the linear map // from Equation (66 and the analytical solution for Cas in Appendix A Finding the set of eigenvalues is then standard task. We show the applicability of our formalism in Figure by showing that GCNs degenerate to a zero distance state state exactly when o² < o² w.errtt Panel a) shows how this procedure correctly predicts the transition the given CSBM instance: The maximum feature distance between any
pair of nodes increases from zero at the point where the state kd4) ((() becomes unstable. This means that beyond this point, the GCN has feature vectors that differ across nodes and therefore does not oversmooth. This is more explicitly shown in panels b) and c). where the equilibrium feature distance is plotted as a heatmap. At point A (panel b)), within the oversmoothing phase, all cquilibrium feature distances are indeed zero, the network therefore converges features are the same. At point B (panel c)) on the other hand, pairs of nodes exist that have finite distance. In the latter case, one can recognize the community structure of the CSBM: the lower left and upper right quadrants are lighter than the diagonal ones, indicating larger feature distances across communities than within. The equilibrium state thus contains information about the graph topology. This phenomenon is also observed in panel d), where we show the predicted feature distance averaged for nodes within or between classes as a function of layers compared to finite-size simulations. Again, theoretical predictions match with simulations. Thus also on more general graphs the presented formalism predicts the transition point between the oversmoothing and the non-oversmoothing phase, corresponding to transition between regular and chaotic behavior.
state which all
7

---

dix Xp) at
dix X2) B
a)
b)
C)
d)
25
25
0.4
x
0.75
betwees dasses
withis clos
node
50
node
50
0.50
0.2
0.25
100
100
0.0
0.00
1.5
2.0
50 node
10a
node
layer
Figure The non-oversmoothing phase in contextual stochastic block model instance with parameters N = 100, d = 5, == 1. The shift operator is chosen according to (6) with 0.3, and of and d(x) = erf( / .). 3. a) The maximum feature distance between any pair of nodes in equilibrium obtained from computing the GCN GP prior for I, = 4, 000 layers (blue) and the largest eigenvalue of the linearized GCN GP dynamics the distance state function of weight variance o² The red line marks the point where max; { = 1. b) Heatmap of the equilibrium distance matrix with entries dag d(x Tg) (Equation 13 at o 1.3, marked as point A in panel a). Colorbar shared with the plot in c). e) Same as b) but at point B with o 2. d) Features distances de d(æa 33
(1) (1) as function of layers for random inputs X i.dd. (/ 1) and finite-size GCN with d; 200, averaged for distances for pairs of nodes within the same community (red) and across communities (purple).
We discuss how the assumptions on weight matrices in related theoretical work [2] 45 exclude networks in the chaotic phase in Appendix D explaining why the non-oversmoothing phase has not been reported before. In Appendix L we observe how increasing the weight variance increases the oversmoothing measure (xX) in equilibrium also in the case of the more common shift oper- ator proposed in the original work [19]. despite the fact that this shift operator does not have the oversmoothed fixed point in the sense of Equation [99)
4.3 Implications for performance
Lastly we want to investigate the implications of the non-oversmoothing phase on performance. We do this by applying the GCN GP as well as finite-size GCN to the task of node classification in the CSBM model and measure their performance, shown Figure 3 Panel a) shows how the generalization error of the GCN GP changes depending on the weight variance o and the number of layers L. In the oversmoothing phase where most GCNs in the literature are initialized (see Appendix[D
[D. the generalization error increases significantly already after only couple of layers. We observe the best performance near the transition to chaos where the GCN GP stays informative up to 100 layers. In panel b) we test the generalization error for even deeper networks. While the generalization error increases to one (being random chance) in the oversmoothing phase, GCN GPs in the chaotic phase stay informative even at more than thousand layers. This be explained by Figure 2 For such deep networks, the dynamics are very close to the equilibrium and thus no information of the input features (0) is transferred to the output. The state, however, still contains information of the network topology from the adjacency matrix, leading to better than random chance performance, In panel c) we explicitly show the layer dependence of the generalization error for the GCN GP the critical point, in the oversmoothing and in the chaotic phase. Again, we see a fast performance drop for oversmoothing networks, while in the chaotic phase and at the critical point the GCN GP obtains good performance also large depths, with performance peaking at L z 15 layers. Tuning the weight variance thus not only prevents oversmoothing, but may also allow the construction of GCNs with more layers and possibly better generalization performance.
In the study of deep networks, results obtained in the limit of infinite feature dimensions de - oo In panel d) conduct preliminary analysis for finite-size GCNs by measuring the performance of randomly initialized GCNs for which we only train the readout layer via gradient descent. Indeed, we observe similar behavior for the GCN GP: Performance drops rapidly over layers in the oversmoothing phase, while performance stays high over many layers at the critical point and in the chaotic phase and peaks at L 15 layers.
often are also applicable for finite-size networks 32
37
8

---

GCN GP
finite size GCN
1.0
a0100
1.00
1.5
numsmontting non sversmaoehing criiial
1.5
nvermmontting non onarsmoothing ciit
gen enrorr E
0.8
75
gen error E
gen error
0.75
gen error
1.0
1.0
0.6
laye
50
0.50
25
0.5
0.5
0.25
101
10a
10a
10a
Oggert ent
ctt
layer
layer
Figure Generalization error (mean squared error) of the Gaussian process for CSBM with parameters N = 20, d = 5, x = L, 7 = 1 and = 4. The shift operator is defined in (6) with g 0.1, other parameters are of
0. Φ(x)) = erl( (n((faa x) and Tra 0.01. In all panels we use Mtrain 10 training nodes and . 10 test nodes, five training nodes from each of the two communities. Labels are =1 for the two communities, respectively. For all panels, we show averages over 50 CSBM instances. a) Heatmap of the generalization error of the GCN GP dependent on number of layers L and weight variance o.. The red line shows the transition to the non-oversmoothing phase. b) Generalization error dependent on weight variance of and depths from turquoise to dark blue. c) Generalization enror dependent on the layer for the GCN GP at the critical line 2 = o² errii in the oversmoothing phase o = o w..crit
1, 4, 16, 64, 256, 1024
and the non-oversmoothing phase oe = o" weertt + 1. d) Performance of randomly initialized finite-size GCNs with dj = 200 for I = 1...., L where only the linear readout layer is trained with gradient descent (details in Appendix F) at the critical line o = o² "m,erit. in the oversmoothing phase of o w.erit 1 and the non-oversmoothing phase o o mriit
Additionally, we test the performance of the GCN GP on the real world citation network Cora 38). Evaluating the eigenvalue condition (20 would be computationally expensive for
gen error E
a)
b)
0.8
75
layer!
such a large dataset, therefore we find the tran- sition by numerically evaluating the feature dis- tance (xX) in equilibrium and search for the 22 at which this distance becomes non-zero. This procedure results in 02 weerrt = 1 and is presented in more detail in Appendix G Fig- ure 4 panel a) shows the performance of the GCN GP dependent on the number of layers L and weight variance o². for the CSBM in Figure 3 we observe that the performance for deep GCN GPs is best near the transition in the non-oversmoothing phase. Furthermore, GCN GPs with more layers achieve lower gen- eralization error. This is shown more directly in panel b). There we observe the layer depen- dence for GCN GPs near the transition in the non-oversmoothing regime. Indeed, the accu- racy increases up to hundred layers, reaching the accuracy of finite-size GCNs stated in 19
50-
0.6
geh emor
100rrcy
0.6
25
0.4
2
100
200
Gg O2 cm
layer L
Figure 4: GCN GP performance on the Cora datset 38 a) Generalization error (mean squared error) as function of layers L. and weight variance of 22 weiit for our stochastic shift operator (6) with g 0.9. The value of o crit. ~ 1 is determined numerically in Appendix G b) Layer dependent generalization error and accuracy for GCNs near the transition o² = =² +0.1. Grey dashed line shows accuracy obtained for GCNs in the original work [9). Numerical details in Appendix F
Near the transition, accuracy increases for up L 100, and the generalization error improves beyond this. We hypothesize that this many layers are required for high performance partly due to our choice of the shift operator. The Cora dataset has maximum degree dmux 168 leading to small off-diagonal elements for the choice of our shift operator: Recall that in Equation (6). the parameter g is constrained to be g E (0, 1). As consequence, the off-diagonal elements of the shift operator are Aij < T 168 Many convolutional layers are then needed to incorporate information from a node's neighbors.
One might wonder whether it is possible to initialize weights in say the oversmoothing regime, and transition to the non-oversmoothing regime during training. We argue that this is possible in the case of Langevin training (Appendix H

---

5
Discussion
In this study we used the equivalence of GCNs and GPs investigate oversmoothing, the property that features at different nodes converge over layers to the same feature vector in an exponential manner. By extending concepts such as the propagation depth and chaos from the study of conventional deep feedforward neural networks (37], we are able to derive a condition to avoid oversmoothing. This condition phrased in terms of an eigenvalue problem of the linearized GCN GP dynamics around the state where all features are the same: This state is stable if all eigenvalues are smaller than one, thus the networks do oversmooth. If one eigenvalue, however, is larger than one, the state where the features are the same on all nodes becomes unstable. While most GCNs studied in the literature are the oversmoothing phase 2 45), the non-oversmoothing phase can be reached by a simple tuning of the weight variance at initialization. An analogy can be drawn between the chaotic phase of DNNs and the non-oversmoothing phase of GCNs. Previous theoretical works have proven that oversmoothing is inevitable in some GNN architectures, among them GCNs; these works, however, make crucial assumptions on the weight matrices, constraining their variances to be in what we identify as the oversmoothing phase. Near the transition, we find GCNs which are both deep and expressive, matching the originally reported GCN performance [9] on the Cora dataset with GCN GPs beyond 100 layers.
Limitations. The current analysis based on the equivalence of GCNs and GPs which strictly holds only in the limit of infinite feature dimension. GCNs with large feature vectors (di 200) are well described by the theory, as shown Section 4 For a small number of feature dimensions, however, we expect deviations from the asymptotic results. Throughout the main part of this work. we assumed a row-stochastic shift operator which made the equilibrium K in the oversmoothing phase particularly simple. For other shift operators, we expect qualitatively similar results while the equilibrium K may look different in detail. In our preliminary experiments on the common shift operator from [19 (Appendix E we indeed find that increasing the weight variance increases the distances between features also in this case. We hypothesize that this effect makes the equilibrium more informative of the graph topology, as in the stochastic shift operator case. The choice of non-linearity is unrestricted, but in the general case numerical integration of (8) is needed.
To determine whether a given weight variance is in the non-oversmoothing phase, one calculates the eigenvalues of the lincarized GCN GP dynamics which take the form of an N2 x N2 matrix (see Equation (16)), this has run time of O(N)). While this becomes computationally expensive for large graphs, the conceptual insights of the presented analysis remain. In practical applications with large graphs one may reduce the computational load by determining the transition point via computation of the GCN GP prior until it is close to equilibrium. This procedure has a runtime of D(N*L9)) where L is the number of layers after which the process is sufficiently close to equilibrium. One might then do an interval search on the weight variance until the transition point is determined with sufficient accuracy.
Oulook. Formulating GCNs with the help of GPs can be considered the leading order in the number of feature space dimension di when approximating finite-size GCNs. Computing corrections for finite numbers of hidden feature dimensions would allow the characterization of feature learning in
such networks, similar in standard deep networks 126 48 39). Moreover, the generalization of this formalism to more general shift operators and other GNN architectures
[49] 4 like GATs [41] possible directions of future research. In the special case of GATs expect similar results to the GCN analyzed here, since the shift operator is constructed using a softmax and therefore also is row-stochastic.
Acknowledgements
Funded by the European Union (ERC, HIGH-HOPeS, 101039827). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. We also acknowledge funding by the German Research Council (DFG) within the Collaborative Research Center "Sparsity and Singular Structures" (SfB 1481; Project A07).
10

---

References
[1] Uri Alon and Eran Yahav. On the Bottleneck of Graph Neural Networks and its Practical Implications, March 2021. arXiv:2006.05205 [cs, stat].
[2] Chen Cai and Yusu Wang. A Note on Over-Smoothin for Graph Neural Networks, June 2020.
arXiv:2006.133 13318 [cs, stat].
[3] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):3438- 3445, April 2020. Number: 04.
[4] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and Deep Graph Convolutional Networks. In Proceedings of the 37th International Conference on Machine Learning pages 1725-1733 PMLR, November 2020. ISSN: 2640-3498.
[5] Aditya Cowsik, Tamra Nebabu, Xiao-Liang Qi, and Surya Ganguli. Geometric Dynamics of Signal Propagation Predict Trainability of Transformers, March 2024. arXiv:2403.02579 [cond-mat].
[6] G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314 December 1989.
[7] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[8] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual Stochastic Block Models. In Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[9] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long Range Graph Benchmark. Advances in Neural Information Processing Systems, 0122326-223400 December 2022.
[10] Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy training in deep neural networks. Journal of Statistical Mechanics: Theory and Experiment, 2020(11):113301, November 2020. Publisher: IOP Publishing and SISSA.
[11] Jean Ginibre. Statistical Ensembles of Complex. Quaternion, and Real Matrices. Journal of Mathematical Physics, 6(3):440-449 March 1965.
[12] William L. Hamilton. Graph Representation Learning. Morgan Claypool Publishers,
September 2020.
[13] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fer- nández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-36,, September 2020. Publisher: Nature Publishing Group.
[14] Jilin Hu, Jianbing Shen, Bin Yang, and Ling Shao. Infinitely Wide Graph Convolutional Networks: Semi-supervised via Gaussian Processes, February 2020. arXiv:2002. [cs, stat].
[15] Tianjin Huang, Tianlong Chen, Meng Fang, Vlado Menkovski, Jiaxu Zhao, Lu Yin, Yulong Pei, Decebal Constantin Mocanu, Zhangyang Wang, Mykola Pechenizkiy, and Shiwei Liu. You Can Have Better Graph Neural Networks by Not Training Weights at All: Finding Untrained GNNs Tickets, February 2024. arXiv:2211.15333 [cs].
[16] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[17] Yufei Jin and Xingquan Zhu. ATNPA: A Unified View of Oversmoothing Alleviation in Graph Neural Networks, May 2024. arXiv:2405.0 016663 [es].
[18] Nicolas Keriven. Not too little, not too much: a theoretical analysis of graph (over)smoothhng. Advances in Neural Information Processing Systems, 55:2268-2281 December 2022.
11

---

[19] Thomas N. Kipf and Max Welling.
Classification with Graph Convolutional Networks, February 2017. arXiv:1609.0220 02000 [cs, stat].
[20] Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington. and Jascha Sohl-Dickstein. Deep Neural Networks as Gaussian Processes, March 201 8.
1rXiv:1711.0011 [cs, stat].
[21] Qimai Li, Zhichao Han, and Xiao-ming Wu. Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), April 2018. Number: 1.
[22] Sitao Luan, Mingde Zhao, Xiao- Mao-WWen Chang, and Doina Precup. Training Matters: Unlocking Potentials of Deeper Graph Convolutional Neural Networks, October 2022. arXiv:2008.088 088888
[cs, stat].
[23] Yao Ma and Jiliang Tang. Deep Learning on Graphs. Cambridge University Press, September 2021. Google-Books Books--oo: _AVDEAAAAQQQJJ.
[24] L. Molgedey, J. Schuchhardt, and H. G. Schuster. Suppressing chaos in neural networks by noise. Physical Review Letters, 69126) December 1992. Publisher: American Physical Society.
[25] Gadi Naveh, Oded Ben David, Haim Sompolinsky, and Zohar Ringel. Predicting the outputs of finite deep neural networks trained with noisy gradients. Physical Review E, 104(6);04331, December 2021. Publisher: American Physical Society.
[26] Gadi Naveh and Zohar Ringel. A self consistent theory of Gaussian Processes captures feature learning effects in finite CNNs. In Advances in Neural Information Processing Systems, volume 34, pages 21352-21364 Curran Associates, Inc., 2021.
[27] Radford M Neal. Priors for infinite networks (tech. rep. no. crg-tr-94-1). University of Toronto, 415, 1994.
[28] Yin Cheng Ng, Nicolò Colombo, and Ricardo Silva. Bayesian semi-supervised Learning with Graph Gaussian Processes. In Advances in Neural Information Processing Systems, volume 31.
Curran Associates, Inc., 2018,
[29] Zehao Niu, Mihai Anitescu, and Jie Chen. Graph Neural Network-Inspired Kernels for Gaussian Processes in Semi-Super Learning, February 2023. arXiv:2302.05822 [cs, stat].
[30] Kenta Oono and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification, January 2021. arXiv: 1905v 10947 [cs, stat].
[31] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vander- plas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Mathheu Perrot, and Édouard Duchesnay. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, (1855)2825-28300 2011.
[32] Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponential expressivity in deep neural networks through transient chaos. In Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[33] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the Expressive Power of Deep Neural Networks. In Proceedings of the 34th International Conference Machine Learning, pages 2847-2854. PMLR, July 2017. ISSN: 2640-3498.
[34] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine leurning. Adaptive computation and machine learning. MIT Press, Cambridge, Mass, 2006. OCLC: ocm61 285753.
[35] T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A Survey on Oversmooth- ing Graph Neural Networks, March 2023. arXiv:2303. 10993 [cs].
[36] Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, February 2014. arXiv: 1312:631 [cond- mat, q-bio, stat).
[37] Samuel S. Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep Infor- mation Propagation, April 2017.
[cs, stat].
12

---

[38] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective Classification Network Data. Al Magazine, 29(3):93-93, September 2008.
Number: 3.
[39] Inbar Seroussi, Gadi Naveh, and Zohar Ringel.
Separation of scales and a thermodynamic description of feature learning in CNNs. Nature Communicattooss 14(1):908, February 2023. Number: 1 Publisher: Nature Publishing Group.
[40] Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. Ordered GNN: Or- dering Message Passing to Deal with Heterophily and Over-smoothing, February 2023. arXiv:2302.01. [es].
[41] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks, February 2018. arXiv:17100 10903 [es, stat].
[42] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland. Tyler Reddy, David Couraapaau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C. Carey, ilhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, and Paul van Mulbregt. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods, 17(3):61-272, March 2020. Publisher: Nature Publishing Group.
[43] Christopher Williams. Computing with Infinite Networks. In Advances in Neural Information Processing Systems, volume 9. MIT Press, 1996.
[44] Christopher K. I. Williams. Computation with Infinite Neural Networks. Neural Computation, 10(5):123--1216, July 1998.
[45] Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying Oversmoothing in Attention-Bass Graph Neural Networks, October 2023. arXiv:2305. 16102 [cs, stat].
[46] Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks, February 2023. arXiv:2212.10700 [cs, stat].
[47] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. Comprehensive Survey Graph Neural Networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):4-24, January 2021. Conference Name: IEEE Transactions on Neural Networks and Learning Systems.
[48] Jacob A. Zavatone-Veth Veth, William L. Tong, and Cengiz Pehlevan. Contrasting random and learned features in deep Bayesian lincar regression. Physical Review E, 105(6):06411, June 2022. Publisher: American Physical Society.
[49] Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling Oversmoothing in GNNs, February
2020. arXiv: 1909. 12223 [cs, stat].
13

---

A Analytical solution for expectation values
To evaluate our theory, we need to compute expectation values given in the form of ( which we restate here for readability
C/8 - (0(11)) de
h
(21)
where by and f& zero mean random Gaussian variables with (h (n K 25 This can be evaluated numerically for general non-linearities (xx). For simplicity, however, choose ((x)
(
erf( x) in our experiments where the scaling factor in the erf chosen such that Br (0) = 1. In this case, the expectation value be evaluated analytically to be
CH0 76
2
76
arcsin
(22)
1
+
K
1
H K88 1+
2
as shown in
44
B The linearized GP of GCNs
We start from the full GCN GP iterative map 1 p ), which we restate here for readability
((11 =T.s [K() oz o Σ Aas [A])]
(23)
aB
7.8
where h and hig are drawn from O-mean Gaussian distribution with covariance ( = K The full covariance matrix of layer I denoted as K(O), Here, we distinguish between the iterative maps Tap N R of which there are 2 one for each pair of nodes a and B, and the entries K(5 of the covariance matrix in the layer I + 1. Notice that Tap TBx due to the symmetry of the covariance matrix. In the maps Tos, the covariance matrix of the previous layer only shows up in the expectation value Cyo = (0 h0 (n))
(1)
such that the linearized dynamics around a fixed 14)
point (being equilibrium K Kagg or zero distance state - k)) with k() K + A ag read
a, a13
(1+11) a3
K-fix +
Al+!1)
(1+1)
Tap
lxx
Ma
A
R A (1)
(((A
(24)
ag
7<8
Kix
oces
K
fix
0
(1 + 5n A Apd
[K fix
A +
A
((AA)))
7.8
0.0
H HuB.n8
(25)
where we restrict the sum in 24 to y since Ky5 and K&, are the same quantity. From follows
24
A
(1+1) 08
Σ Has +0044)))))))))))) 7.6
(26)
which is Equation [66] in the main text. While H is not symmetric in general, Hog, # H4 it symmetric in the first and second pair of covariance indices, Hag.y5 = H9a,7 and Ha8.76 = Hap.5 due to symmetry of the covariance matrices, Kag K ja--
In the main text, we look for the right eigenvectors of fulfilling
X₂ A a3
= M Ha8,7o
(27)
7.8
14

---

These are for general non-symmetric matrices not orthogonal. In order to decompose A (1) to overlaps with the eigenvectors au we need find the dual vectors U/ fulfilling
Evee v
ag a3
=d.g
(28)
0,8
from which we can define
4
(1()
(29)
0g
ag
a,
such that
A
Σ A 11) v
(30)
as stated in the main text.
C Investigation of the complete graph model
In this section we analytically investigate the complete graph model as defined in the main text. Specifically, we consider networks with the shift operator
Ng
Aas N + dap
(31)
N N-1
and Ø = erl( (r.() Due to the symmetry of the system we make the ansatz
K a3 K 8..,(Ke" Kg²),
(32)
meaning that we assume constant variances Kea across nodes and that all pairs of nodes have the same covariance Kea, reducing the system to only two unknown variables. The equilibrium is
fixed point of the iterative map of the GCN GP. With the special choice of shift operator (31 this becomes
K((+1) = of +ga0% + 9
(33)
and
KDD of + -,, + C!
(34)
with constants
g
= (1 +
j0u
(35)
N-
9. 2gg + g g²(N (N- 2)
1 10u
(36)
(2 2)
ha 2 N - 1 (N - 1)2 )0"
9
+
(37)
(N - 112 + 2 - - 3)
g²
169(N - 2)
h. (1 +
(N- 1) )o?
(38)
111
and
c (6(h!)))(1!) CO = (0(h (((h
(39)
for FB.
(40)
(1) The preactivations are Gaussian distributed with zero mean and covariance (ha (0)) = K-(, In the oversmoothing phase, we know that (X) that this corresponds to K = g0, implying for our ansatz that K K&9, We will find the transition to chaos by calculating where this state becomes unstable with regard to small perturbations.
in equilibrium. We have seen in Section 4.2
Specifically, we define e!))
(!
and look for the parameter point where k
dc((+1)
1 ?
(41)
dcll)
15

---

The authors in [37 used this approach to find the transition to chaos for DNNs. The correlation coefficient is
K((+1) k((+T]
og c. + he C.
c!++))
(42)
of + 9 ch + Ce
and Equation (41 thus becomes
del++)
DCH-1) he Beli)
((++1)
ac!++1)
k-(+1))
Dc Delt)
(43)
0c(1 <0==1
(k(
Since we look at this equation at the perfectly correlated state c(0) 1, we know that K_ = K!
(implying that ((()) Ke (!) and can determine Ka the solution of the fixed point equation
k(++1) of + (ga + gc
(44)
to which the GCN GP dynamics reduce in the zero distance state (by using the fact that Es Aus
1
C c()) Lastly, we calculate
(((++))
2 aresin
(45)
Oc!!)
Oel!)
1 2 K
c()==1
2
(46)
$/2 K ol0)
2 2
+ k-(
1601=1
1+ k!!
2
K2
(47)
7
k
2 5
Kg
where we used the known solution for the expectation value Ce for (x) = er((vxx/22 from Appendix A Plugging this into Equation (43) lets us calculate del(+1)
and thus determine the
Botty c(0)
transition to the non-oversmoothing phase. This is plotted as a line in Figure] panel a) and b).
D Restriction of weight matrices in related work
In this section will show histograms of critical weight variances oe and discuss how the assumptions in ( and 455 exclude networks in the non-oversmoothing phase. Our results thus stand in conflict with the results of these works.
Here we want to argue that the assumptions on the weight matrices in related work constrains their architectures to the oversmoothing phase. We start with [45] in which the authors study graph attention networks (GATs). Although we study a standard GCN here, we hypothesize that increasing the weight variance at initialization likewise prevents oversmoothing in other architecture, such as the GAT in [4]. The critical assumption constraining them to the oversmoothing phase is their assumption A3, stating that { IT [Ilaax) == is bounded where ||M]] max max,,j [M, For our setting of randomly drawn weight matrices with) i...d NN(0, = with w!! E NxN this restricts values o2 1. This be seen by using the circular law from random matrix theory 11: It is known that the eigenvalues of a matrix with i.i.d. random Gaussian entries of the form above have eigenvalues uniformly distributed in circle around in the complex plane with radius Vog in the limit di + co. Thus, the maximal real part of any eigenvalue of this matrix Vog. Thus o y with constant To enter the non non-oversmoothing phase, we need o > 1. In this case, the latter expression diverges for & + co, thus being excluded by the proof in [45]. Indeed, for the CSBMs we investigated in this work, all critical weight variances
we can estimate |||T/_ [W(]]] max S <( vo
22 weieri are larger than 1 as shown in Figure 5) Also in our model of the complete graph and the
CSBM investigated in Section 4.2.2 all o2 w.crit are larger than 1, compare Figure and Figure 2
16

---

Histogram ow
7.5
5.0
2.5
0.0
1.0
1.2
1.4
Figure 5: Histogram of o w. for the 50 CSBM instances used in the experiment Figure The point is marked for comparison to related work.
The authors of 2 and 30 also study GCNs,; however they consider a different shift operator than in this work. In both of [2] and [30] the authors find that their GCN models exponentially loose expressive power if sλ 1, with À being the maximal singular value/eigenvalue of the shift operator and being the maximal singular value of all weight matrices. Again, the maximal singular value is limited (dependent on X), which in our approach translates limit on a While the authors notice that their bounds do not hold for large singular values they do not observe non-oversmoothing phase their models.
E Non-oversmoothing GCNs with non-stochastic shift operators
Here we investigate how increasing the weight variance can mitigate oversmoothing also in the case of the original shift operator proposed by Kipf and Welling in [19] being
Akw (D')
(48)
with A'' = I A and D' = Big Eg A₁2- This shift operator Agw is not row-stochastic, therefore the state Ko = is not a fixed point for * O, as can be seen from Equation (19). Thus we need to differentiate between two kind of fixed points: Either, all features
zero, for which Kag 0 and ((X)= = 0, or some Kas * in which case we have u(X) )) > O. Importantly, for this shift operator, there is intermediate case for which Kas = k with 0. Consequently there is oversmoothing regime with respect to the measure p(X) where node features are non-zero. For an in depth study of this case (48) the definition of another oversmoothing measure μí' incorporating the different values of 3 (Akw)as for different a may be more appropriate. For our purposes, it will suffice to analyze the shift operator (48) with the measure (xX) ) from Equation (44
Figure panel shows how (xX) in equilibrium increases for larger weight variances of for the shift operator (48). For comparison, we also show the results obtained with our row-stochastic shift operator 6 Thus find that also for the shift operator Axw the pairwise distance between features can be increased by increasing the weight variance o The non-existence of an oversmoothed fixed point except for the special
Kn which argued for above observed in panel b) and c): The oversmoothing measure (xX) is zero for Akw if and only if all entries of the covariance matrix are zero, implying that all preactivations and thus also all features are zero. This is a qualitative difference to our shift operator A for which we find equilibrium states with non-zero max, Kig but still p(X) 0.
F
Details of numerical experiments
To conduct our experiments we use NumPy B SciPy 42
(both available under a BSD-3- 3-Clause License) and Scikit-leam (sklearn) B1I (available under a New BSD License). The code is publicly available under hattps://iithu com/ com/bepping www///oooovveeeeeeeee www.-oootrrooning--o.ee ggngs For our experi- with the Cora dataset, we the readin methods from [19] which are available under a MIT license (Copyright (c) 2016 Thomas Kipf). Computations were performed on CPUs. PUUS.Reqisemmntss for the experiments with synthetic data (approximately):
* Figure I 10mins single core laptop.
17

---

a)
b)
(400 In equilbbrium
row-stochassic Kipf & Welling
equilibrium
1000 in equilibrium
0.10
0.02
0.10
0.05
0.01
0.05
0.00
0.00
0.5
1.0
1.5
0.00
0.25
0.50
0.75
1.00
0.0
0.2 maxik
0.4
O
m2x
Figure 6: Oversmoothing in GCN GPs with the commonly used shift operator (48) (called Kipf & Welling in the label) and our row-stochastic shift operator (6). a) Feature distance μ(X) in cquilibrium dependent on weight variance of obtained from simulating the GCN GP priors for L 4, 000 layers. Shown are the averages (solid lines) and standard deviations (shaded areas) over 20 CSBM initializations with 1, d and N of all nodes max, ( and feature distance ((X) in equilibrium for the same data as in plot a). e) Same as b) zoomed into lower left corner.
nodes.b) Scatter plot of maximal variance
10h on a single node on an internal CPU cluster. Most of the computation time needed for evaluating max(X?) in panel a).
Figure 2
Figure g
2h on single core laptop. In panel d), the last layer of finite-size GCNs is trained
with the standard settings from
Figure 5
Byproduct Figure
Figure
10min on single core laptop.
We also experimented on the real world benchmark dataset Cora 388 This is citation network with 2708 nodes, representing publications, and 5429 edges, representing the citations between them (we undirected edges). The publications divided into seven classes, and the task is to predict these classes for the unlabeled nodes. Node features are of 0/1 valued vectors indicating the absence/presence of words from dictionary in the titles of the respective publication. The dictionary consists of 1433 unique words. Requirements for the experiments with the Cora dataset are:
Figure 4
Ih single core laptop.
Figure 7
15h single core laptop.
G Non-oversmoothing transition in the Cora dataset
For Figure 4 we numerically determined the transition to the non-oversmoothing regime for the Cora dataset. The transition was estimated by measuring the distance ((X) at equilibrium (i.e., after many layers), and determining at which value of o it becomes larger than a small distance c 10-5 The results this experiment are shown in Figure We find critical point to be o² o = while using a step size of da? 0.01.
H Transitioning between regimes during training
In this section argue why we think it is possible to transition from the oversmoothing to the non- oversmoothing regime vice versa during training.
In the GP limit of infinitely many hidden features with a finite amount of training data, the variance of weights of neural network is the same before and after training. This is because weights only change marginally in this limit, also known the lazy training regime [16] I0]. We will use this fact to argue that Langevin training is capable of transitioning from one regime to the other.
Langevin training is gradient based training scheme with external noise and decay term. The gradient flow equation is given as
dW WWW Vw., L Bij
18

---

MXX1 at equilibrium
0.2
0.1
Figure 7: Node distance measure ((X) equilibrium obtained from computing the GCN GP prior for L = 4, 000 layers a function of d The transition to the non-oversmoothing regime is estimated by checking where the node distance measure is larger than 10 marked the red line.
where Wy are the weights to be trained, L is the loss function and B. denotes external white noise (Bi, (R)((s) 0 s) with strength D where da, and ó(a b) denote the Kronecker or Dirac delta, respectively. Both fy and are parameters of this training scheme. It is known that the distribution of weights converges to the posterior weight distribution of neural network GP with weight variance o 2- in the infinite feature limit [5 which, as we have noticed above, is the same as the prior distribution.
Since the Langevin distribution converges to the GP weight posterior for any initial distribution, one can imagine an initial distribution with a variance that initializes the network in the oversmoothing regime, while the parameters and D are chosen such that oy o/ > o w implying that after training most weight realizations will be in the non-oversmoothing regime. Thus, in this case the GCN would have transitioned from one regime to the other. While this argument is made in the limit of infinitely many hidden features, think that qualitatively similar results are possible for large but finite number hidden feature dimensions. The transition in the reverse direction is possible by the same argument only with the initial and the final variances exchanged.
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We describe approach, the model we study and discuss the contribution of our work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of work are addressed in the discussion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

Justification:
We provide the calculations leading to our results in the main text or appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibiliyy
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The procedures for producing the experimental results in this work are de- scribed clearly, all necessary parameters given in the figure captions.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
21

---

Answer: [Yes]
Justification: While the paper provides sufficient instructions to reproduce all experimental results in this paper, publish code in git repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
/oaeeeeee/oooSuSbmbiio ssionlolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details for the experiments can be found in the respective figure captions.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In our experiments we compare mean values with theoretical prediction. The numbers of instances used for each experiment are given in the respective figure captions.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
22

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computing resources needed to reproduce experiments are given in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp//.aaarrp.s.cc//aaa/////aa
Answer: [Yes]
Justification: The work presented in this paper conforms with the NeurIPS Code of Ethics in every aspect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work presented in this paper is of theoretical nature, we do not foresee any direct societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
23

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any code or data that poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We mention the assets we use in the appendix, cite the creators and state the licenses.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the "atasets.papersstt package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "pIy0zBC4T8", "reviewer": "Reviewer_HWT8", "summary": "This work aims to understand whether GNNs in large depths always suffer from oversmoothing. The research starts from the equivalance of gaussian process (GP) and infinitely-wide NNs, and utilize eigenvalues of the linearization of GCN GP to quantify whether the model is in the phase of oversmoothing or not. After identify the intialization scale $$\\sigma_w$$ as the key factor, it empirically verifies how deep GCN GPs and GCNs performance with different scales on synthetic graphs, and it turns out larger intialization does overcome the oversmoothing.", "questions": "1. a good addition would be to empirically verify how the eiganvalues change along training, which is to understand whether oversmoothing will appear or disappear with a certain scale of initialization.\n2. what is the connection between this work and [1] about the singular values of weights? In section 3.3, they denote the singular values as $s$, and if the value is large, the bound for oversmoothing will not hold any more. Is this case the same as what is discussed in this work?\n\n---\n\nReference:\n\n[1] GRAPH NEURAL NETWORKS EXPONENTIALLY LOSE EXPRESSIVE POWER FOR NODE CLASSIFICATION.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivation is natural and the result is good: oversmoothing is an important question in the community, and the initialization scale was not took care of much before.\n2. The research path is clear: while it is hard to directly understand finite-width GNNs, the equivalence of GCN GPs and infinite-width GCNs  make it feasible to at least understand the problem in the wide regime, and then the argument could be empirically verified for finite widths.", "weaknesses": "1. Evaluation is a little weak for more practical settings: for example, add some experiments on classification tasks on simple datasets like cora, citeseer. The goal would be to provide a better measurement of the performance with large initialization, since the currently provided results on synthetic settings are less pesuasive for practitioners to use such large intialization vs other methods to overcome oversmoothing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their review and helpful questions and comments. We will address them in the revised version:\n\nRe: Weaknesses\n1.  In the revision we will repeat the experiments shown in Fig. 3 on the Cora and/or CiteSeer datasets. This should provide readers with a better sense of the generalization error they should expect in practice. For preliminary results on the Cora dataset, please refer to our global response.\n\nRe: Questions\n1. Tracking the eigenvalues during training is an interesting proposal. We will provide such an empirical analysis in the revised version of the manuscript. We anticipate already some points from the presented material. For the wide networks we consider here, the Gaussian process is an accurate description of the posterior after training in a Bayesian setting. Such training could, for example, be performed with Langevin training, which is equivalent to gradient descent with weight decay and stochasticity. At large width weights change only marginally, so that we expect the GP at initialization to be an accurate description of the network also after training has converged. So in particular we expect that training will not change the eigenvalues in a notable manner in the limit of wide networks.\nHence the condition for oversmoothing, derived from the GP at initialization, will be informative of the network’s oversmoothing properties also after training has converged.  \nThe more interesting setting, which we guess is the one envisioned by\nthe referee, is that of networks of small or moderate width. Here due to\ntraining, weights typically depart from their values at initialization, which\nmay change the eigenvalues after training converges if this is beneficial for\nminimizing the loss. Still in this regime we expect the obtained criterion\nfor the start of the non-oversmoothing regime to be indicative of the network’s (over-)smoothing properties. We will check our expectations with\nnumerical experiments in the revised version.\n2. Indeed, the effect in [1] is similar to what we see in our work. However there are crucial differences between the two approaches. We will address the similarities and differences between our work and [1] more clearly in the revised version.\n    - The authors in [1] calculate an upper bound, which is loose for a large singular value $s$. This however does not imply that the networks dynamics are close to this bound, such that in their analysis GCNs with large s could still be oversmoothing (this happens e.g. in Figure 2 in [1] where the upper bound on distances between features increases, but in the simulation of the GCN distances decrease). In our approach on the other hand, we obtain not just bounds but quantitative predictions, both for the value of $\\sigma_{w,\\text{crit}}^2$ which defines the oversmoothing threshold, and for the expected feature distance given a particular $\\sigma_w^2$. We were able to verify these predictions on finite-size networks (Fig. 1c, 2d, 3d).\n    - The authors in [1] find that their GNN architecture exponentially\nloses expressive power. In contrast, we determine a parameter setting\nwhere our GCN model does not lose expressive power exponentially:\nthis happens precisely at the transition between the oversmoothing\nand non-oversmoothing regime that we discover here. At this point,\nthere is one eigenvector $V^{(i)}_{\\alpha\\beta}$ in the sense of l. 191 f, for which the information propagation depth diverges, allowing information to propagate far into the network. Precisely at the transition, distances\nbetween feature vectors converge in a manner that is slower than\nexponential\n    - In [1] only the ReLU activation function is considered, while our\nformalism captures arbitrary non-linearities, at the cost of solving\nthe integrals in Eq. (8) numerically.\n\nReferences:\n\n[1] Oono, Kenta, and Taiji Suzuki. \"Graph neural networks exponentially\nlose expressive power for node classification.\" arXiv preprint arXiv:1905.10947\n(2019).", "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": "rpltgY712x", "reviewer": "Reviewer_kVv2", "summary": "The paper investigates whether oversmoothing in GNNs is avoidable in theory. It investigates why oversmoothing occurs and derives an affirmative answer. In particular, depending on the variance of the initial weight matrices, GNNs can either enter a \"regular\" (oversmoothing) or \"chaotic\" phase (non-oversmoothing). These theoretical findings are confirmed by experiments on small-scale synthetic graphs.", "questions": "1. Regarding l. 175: Is the fixed point intentionally equal for all $\\alpha,\\beta$?\n2. What does the solid line in Fig. 2d show? Isn't this a purely empirical plot?\n3. How is allowing additional layers a \"computational benefit\" (l. 296ff)?", "limitations": "Limitations are discussed adequately. It could be mentioned that the experiments are limited in both the GNN architectures that were investigated as well as the datasets the experimetns were perfromed on.\n\nThe paper does not contain a broader impact statement or similar section on ethical considerations. This is perfectly acceptable for the work under review.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The work focuses on a fundamental problem in GNNs, which is introduced and motivated well.\n- The background is concise yet easy to follow.\n- The paper questions the establishing belief that oversmoothing is inevitable, making this work highly significant.\n- The experiments are insightful and presented well.\n- The approach is original, and the presentation is clearly written and high-quality.", "weaknesses": "- The transfer of the newly developed theory to practical networks is minimal. Sec. 4.3 still considers a CSBM instead of real-world data.\n- The work only considers GCNs.\n- The derivation of Eq. (17) is a bit hard to follow without further explanation.\n- No implementation is provided. No reason is given for why that is the case (cf. l. 529). However, the code for the experiments is also not the work's main contribution.\n\nMinor comments:\n- The reason for the specific definition of $\\phi$ in l. 120 is only given in l. 148. This could be referenced earlier.\n- I assume that the sum in (16) is over all $\\gamma$ and $\\delta$. If so, a comma would help clarify that. Analogous in (17).\n- The order of the appendices A and B is reversed with respect to the presentation in the main paper.\n- The captions of the experiment figures are somewhat redundant from the main text.\n- One could also directly label the lines in Fig. 1c (instead of in the caption), making it more easily readable. Similar for Fig. 3b.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for this thorough review and the helpful questions and\ncomments. We will address them in the revised version:\n\nRe: Weaknesses\n1. In the revision we will repeat the experiments shown in Fig. 3 on the Cora\nand/or CiteSeer datasets. For preliminary results on the Cora dataset,\nplease refer to our global response.\n2. While our formalism only captures GCN-like architectures, it still allows\nfor freedom in designing a specific architecture: we\n    - allow for arbitrary activation functions (at the cost of evaluating Eq.\n(8) numerically),\n    - have a tunable parameter g allowing different weights on the diagonal\nof the shift operator (cf. Eq. (6)),\n    - and allow for bias.\n    - However, we agree that an extension of our formalism to other GNN\narchitectures such as message passing ones would be interesting. We\nexpect that such architectures should also exhibit a non-oversmoothing\nphase, although showing this is outside our current scope. We mention this as an interesting direction of future research in the discussion\n(cf. l. 341 ff).\n3. We will improve this in the revision. Specifically we will state that we are\nlinearizing Eq. (9), and that the factor $\\frac{1}{2}(1+\\delta_{\\gamma,\\delta})$ in Eq. (17) comes from\nthe symmetry of the covariance matrix. In the revised version we will also\npoint readers to appendix A, where the calculation is performed in full,\nimmediately on l. 184. (Currently the reference to Appendix A appears\nonly on l. 197.)\n4. We will share the code upon acceptance.\n\nRe: Minor comments\n1. We will add the following on l. 120: ”While the theory is agnostic to\nthe choice of non-linearity, for our numerical experiments we use $\\phi(x)=\\text{erf}(\\sqrt{\\pi}/2 x)$; this choice allows us to carry out certain integrals analytically.\"\n2. We will add the commas in the revised version to improve readability.\n3. Indeed. We will correct this in the revision.\n4. We will reduce this redundancy in the revision.\n5. This is a valid suggestion: we have tried this and found that we can make\nit work without overloading the plot. The revised version therefore will\nhave the labels directly in the figure.\n\nRe: Questions\n1. No, it should be $K^{\\text{eq}}_{\\alpha\\beta}$ instead of $K^{\\text{eq}}$. We thank the reviewer for spotting this.\n2. The solid line in Figure 2d) shows the zero line (we show this since the\ndistances $d(x_\\alpha, x_\\beta)$ are bound by 0 from below). In the revised version,\nwe will instead use 0 as the lower limit of the y-axis.\n3. Indeed, the wording here might incorrectly suggest that adding layers\nwould reduce computational cost. Rather we meant that adding more\nlayers may make the network more expressive and/or improve its generalization error, since we see in Fig. 3(c,d) that the generalization error\nis minimal at around 15 layers. In the revised version we will write this\nas follows: “Thus by tuning the weight variance to avoid oversmoothing,\nwe allow the constructions of GCNs with more layers and possibly better\ngeneralization performance.”", "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": "1HZIcX8Nrm", "reviewer": "Reviewer_WQpY", "summary": "This paper studies the over-smoothing effect in Graph Convolution Networks in the infinite width limit using their Gaussian processes equivalence. The authors generalize the concept of deep information propagation to GCNs and identify the similarity between ordered and chaotic phases in deep neural networks to over-smoothing and non over-smoothing regimes in GCNs. Using this, they show that initializing weights with large variance is sufficient to escape over-smoothing in GCNs.", "questions": "Please refer to the Weaknesses for major comments and minor ones are listed below.\n\n1. To strengthen the paper further, I suggest the authors evaluate their findings on at least one real graph data like Cora or Citeseer. I understand the computational difficulties, and to tackle it, one can consider a small labeled set. \n2. Would the result extend to other graph neural networks like GAT too?\n2. What is the significance of considering $\\epsilon$ noise in $Y$ (eq. 2)?", "limitations": "Limitations are already discussed in the paper which I list below. I don't see any other additional limitations. \n\n1. The analysis is in infinite width limit. \n2. The considered shift operator is different from the one usually used in practice.\n3. Computational disadvantages in determining the variance of weights.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theory of using deep information propagation to graphs is novel and interesting. Although many works studied over-smoothing in GNNs, this paper analyzes it from a new perspective resulting in interesting findings.\n2. The paper is well written and structured. I appreciate the authors discussed the implications and limitations of their work in detail.", "weaknesses": "1. The analysis is done using column shift stochastic shift operator, but in practice, GCNs are usually constructed with degree normalized adjacencies such as $D^{-1/2}AD^{-1/2}$ or $D^{-1}A$. I wonder if the results would translate in this case as well. The authors have discussed this in the limitations, perhaps giving empirical evidence using CSBM could help counter this weakness.\n2. The theoretical analysis is in infinite width limit so it may not hold well in the finite width setting. But in my opinion this is not a critical weakness of the paper as the analysis in finite width is more challenging.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the reviewer’s insightful comments and the evaluation of our\nwork. The comments are very helpful; we will address them in the revision:\n\nRe: Weaknesses\n1. This is a good suggestion; indeed it is something we are currently looking\ninto. These shift operators are not column-stochastic, so from the point\nof view of the theory they present additional challenges. However there\nis no issue to repeating our numerical experiments with these operators,\nso we will perform the suggested numerical experiments, and add them\nto the appendix. If we find compelling theoretical results for these more\ngeneral operators we may add them to the main text.\n2. Indeed the extension to finite networks is challenging and outside of our\nscope. In the discussion we point to some works which perform finite-size\ncorrections for deep neural networks, and could serve as a starting point\nfor a similar extension to GCNs. Nevertheless, already the infinite width\nlimit may give good qualitative insights; this is certainly the case for wide\ndeep neural networks, and based on our results seems also to be the case\nfor GCNs (Compare our Figs 3c and 3d). For the wide networks we consider here, the Gaussian process is an accurate description of the posterior\nafter training (Compare our Figs 1c, 2d, and 3c and 3d, .).  \nThe more interesting setting, which we guess is the one referred to by\nthe referee, is that of networks of small or moderate width. While the\nweights in wide networks change during training only marginally, in small\nnetworks trained weights typically depart from their values at initialization. Still in this regime we expect the found criterion for the start of the\nnon-oversmoothing regime to be indicative of the network’s smoothing\nproperties.\n\nRe: Questions\n1. In the revision we will repeat the experiments shown in Fig. 3 with a\nshift operator determined from the Cora and/or CiteSeer datasets. For\npreliminary results on the Cora dataset, please refer to our global response.\n2. We expect that our results generalize to other architectures like graph attention networks (GATs); in fact the shift operator in GATs is defined in\nterms of a softmax (cf. [1] Eq. (2)), and therefore satisfies our assumption that it be column-stochastic. However it also depends on learnable\nparameters, which would require a generalization of our formalism.\nMore broadly the question of generalizing our theory to alternative architectures is a valid and interesting one, and we plan to expand the relevant\nsection in the discussion to include both GATs and operators based on the\nnormalized Laplacian.\n3. The readout noise is kept for numerical reasons: In the oversmoothing\nphase, the entries of the covariance matrix converge to constant values $K_{\\alpha\\beta}^{(l)} \\overset{l\\to\\infty}{\\to} k$. To infer labels of test nodes however, we need to invert the\ncovariance matrix $K_{\\alpha\\beta}$ in Eq. (12). Adding readout noise amounts to\nadding a small diagonal matrix, which stabilizes the numerics. We will\nadd a comment explaining this in the revision.\n\nReferences:\n\n[1] Veličković, Petar, et al. \"Graph attention networks.\" arXiv preprint\narXiv:1710.10903 (2017).", "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:
We thank the reviewers for their time and valuable comments. A common point
across reviews was that the paper would be strengthened by adding results
which use a real world dataset instead of just the synthetic CSBM (contextual
stochastic block model). We agree with this assessment, so we will address it
in the revision. Our preliminary results using the Cora dataset show the same
qualitative behaviour as with our CSBM example: Beyond the transition to
chaos the network no longer oversmoothes and achieves low generalization error
for many layers. In the attached pdf you can find the figure corresponding to our Fig. 3a
for the Cora dataset.

Replies to more specific comments are included in the author-specific responses.

Meta-review: All reviewers unanimously voted for acceptance. 

A common point across reviews was that the paper would be strengthened by extending the empirical analysis to real world dataset. As a consequence authors presented experiments on Cora during the rebuttal, which I encourage the authors to incorporate in the final version of their paper.
Decision: Accept (poster)