Exploring and Improving Initialization for Deep Graph Neural Networks: A Signal Propagation Perspective
Authors: Senmiao Wang
Yupeng Chen
Yushun Zhang
Ruoyu Sun
Tian Ding
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs) often suffer from performance degradation as the network depth increases. This paper addresses this issue by introducing initialization methods that enhance signal propagation (SP) within GNNs. We propose three key metrics for effective SP in GNNs: forward propagation, backward propagation, and graph embedding variation (GEV). While the first two metrics derive from classical SP theory, the third is specifically designed for GNNs. We theoretically demonstrate that a broad range of commonly used initialization methods for GNNs, which exhibit performance degradation with increasing depth, fail to control these three metrics simultaneously. To deal with this limitation, a direct exploitation of the SP analysis--searching for weight initialization variances that optimize the three metrics--is shown to significantly enhance the SP in deep GCNs. This approach is called \textit{\textbf{S}ignal \textbf{P}ropagation \textbf{o}n \textbf{G}raph-guided \textbf{Init}ialization (\textbf{SPoGInit})}. Our experiments demonstrate that SPoGInit outperforms commonly used initialization methods on various tasks and architectures. Notably, SPoGInit enables performance improvements as GNNs deepen, which represents a significant advancement in addressing depth-related challenges and highlights the validity and effectiveness of the SP analysis framework.

Yushun Zhang Published in Transactions on Machine Learning Research (06/2025)
Exploring and Improving Initialization for Deep Graph Neural Networks: A Signal Propagation Perspective
Senmiao Wang" The Chinese University of Hong Kong, Shenzhen, China
semmiaowang1@linnk @link.nnggiiiiiiiaaaaio
Yupeng Chen
gupengchen hwwp:/eenn@ninnnnuu..koo
The Chinese Universiby of Hong Kong, Shenzhen, China
The Chinese University of Hong Kong, Shenzhen, China Shenzben Research Institute of Big Data
Ruoyu Sun
swwraoyn@uuuk..cu.cco
The Chinese University of Hong Kong, Shenzhen, China Shenzhen International Center for Industrial and Applied Mathematics Shenchen Research Institute Big Data
Tian Ding'
dingtian Serdiaanssrrdd..cm cn
Shenchen International Center for Industrial and Applied Mathematics
Shenzhen Research Institute of Big Data
Reviewed on OpenReview: https: openreview. net/ forun? id- 6ANoaNXfRy
Abstract
Graph Neural Networks (GNNs) often suffer from performance degradation as the network depth increases. This paper addresses this issue by introducing initialization methods that enhance signal propagation (SP) within GNNs. We propose three key metrics for elfective SP in GNNs: forward propagation, backward propagation, and graph embedding variation (GEV). While the first two metrics derive from classical SP theory, the third is specifically designed for GNNs. We theoretically demonstrate that a broad range of commonly used initialization methods for GNNs, which exhibit performance degradation with increasing depth, fail to control these three metrics simultaneously. To deal with this limitation, a direct exploitation of the SP scarchiig for weight initialization variances that optimize the three metrics- is shown to significantly enhance the SP in deep GCNs. This approach is called Signal Propagation on Graph-guided Initialization (SPoGInit). Our experiments retonstrate that SPoGInit outperforms commonly used initialization methods on various tasks and architectures. Notably, SPoGInit enables performance improvements as GNNs deepen, which represents a significant advancement in addressing depth-related challenges and highlights the validity and effectiveness of the SP analysis framework.
1 Introduction
Increasing depth has been a prominent trend in the development neural networks. For instance, from AlexNet (Krizhevsky et al. 2012), VGG19 (Simonyan Zisserman] 2015) ResNet (He et al., 2016), the depth of the Convolutional Neural Network (CNN) has increased from 8, 19 to 152, and the corresponding test accuracy ImageNet has increased from 63.3%, 74.4% to 78.57%. Theoretically, the benefit of depth is
"Equal contribution. Coorrepponding author.

---

Published in Transactions on Machine Learning Research (06/2025)
often attributed to strong representation power. Research shows that a shallow network would require an exponential increase in width to match the representational power of a deep network (Tllarsky
2015
Eldan
& Shamir 2016 Liang & Srikant 2017
In graph-related tasks like node classification, graph classification, or link prediction, graph neural networks (GNN) (Wu et al., 2022a; 2020) are also expected to benefit from increased depth. core concept in GNNs is the message-passing mechanism, where each node aggregates information from its neighboring nodes [ Deeper GNNs have larger receptive fields, enabling nodes to gather information from broader local sub-graphs. This is especially beneficial for capturing rangerange relationships in complex graph-related tasks. For instance, GNNs have shown great potential in solving optimization problems (Gasse ct al. 2019; Nair et al. 2020 Han et al.,
2022 Li et al., 2024a). Theoretical studies demonstrate that GNNs possess universal approximation power for solving various optimization problems, including linear programming (Chen et al., 2023) and quadratic programming (Chen et al. 2024), but the network depth need to scale with the problem dimensions (Qian
ct al.] 2024 Li ct al. 2024b). Thus, increasing the depth of GNNs is expectod to improve their performance in addressing large-scale optimization problems.
However, GNNs often experience performance degradation in practice when their depth increases LLi et al.
2018 Wu et al., 2020 Zhou et al. 2020a). Consequently, most GNNs remain shallow, typically comprising
only 2 to 10 layers (Kipf & Welling 2017 Veličković et al. 2017: Alon & Yahav 2021 In recent years,
over-smoothing has been identified as a primary cause of this issue Li et al. 20188] Oono & Suzuki 2019 Cai
& WWang 2020). Over-smoothing refers to a specific issue in GNNs where node embeddings become similar as depth grows, reducing the distinguishabilitty between nodes and impairing task performance. This poses major obstacle to the development of deeper GNNs and may hinder progress in complex graph-related problems, particularly those involving long-range relationships.
In this paper, we show that over-smoothing can be understood as part of a broader issue known as signal propagation (SP). SP refers to how the input data is transformed as it passes through the layers of a neural network. For traditional neural networks like CNNs, SP analysis plays a critical role in developing initialization strategies to maintain stable signal propagation and prevent gradients from exploding or vanishing during training (Poole et al.) 2016 Schoenholz et al.) 2017: Pennington et al. 2017 2018 Hanin 2018). This work extends the SP analysis framework to GNNs. We introduce new graph-specifi SP metric, graph embedding variation (GEV), which closely relates to over-smoothing. Alongside the slandard forward and backward SP (FSP and BSP) metries, we use GEV to evaluate signal propagation in GNNs.
Building on this framework, we focus on the family of graph convolutional networks (GCNs), one of the most widely-used GNN architectures, to demonstrate the interplay between initialization strategies and signal propagation. While traditional initializations such as Kaiming (He et al., 2015), Xavier (Glorot & Bengio 2010), and LeCun (Bottou) 1988 LeCun al., 2002) initializations are commonly used in standard GCN implementations (e.g., the Pororrc Geometric library PyG (Fey & Lenssen 2019)) ) theoretically prove that these initialization methods fail to stabilize all three SP metrics concurrently, leaving deep GCNs vulnerable to performance degradation.
Motivated by the SP framework, we propose a new initialization method, termed Signal Propagation on Graph-guided Initialization (SPoGInåt), for deep GCNs, SPoGInit consolidates the three SP metrics (FSP, BSP, and GEV) into a unified optimization objective, where minimizing the objective leads to more stable SP. Using an iterative algorithm, SPoGInit adjusts the weight initialization variances across layers to minimize this objective. Thus, SPoGInit can simultaneously stabilize all three SP metrics. Furthermore, the design of SPoGInit is independent of specific network architectures, and hence it can adapt effectively across diverse GCN models. The effectiveness of SPoGInit verifies that stabilizing the proposed SP metric can improve the performance of deep GCNs and mitigate the performance degradation problem.
Our contributions are as follows:
Theoretical Analysis: We prove that traditional initialization methods for vanilla GCNs and Residual GCNs (ResGCNs) fail to simultancously control all three signal propagation metrics. This failure leads to
IIn this paper, we refer specifically to GNNs as message-pasee passing GNNs. We note that other network structures not based pressage-passing such as Transformers (Wu et 2022h Kong et al. 2023 are also used in geaph-related tasks.
2

---

Published in Transactions on Machine Learning Research (06/2025)
the explosion vanishing of one or more metrics, ultimately causing performance degradation network depth increases. We also present experimental evidence to validate our theoretical findings.
Empirical Exploration. Building the proposed SP framework, introduce a new initialization design method, Signal Propagation Graph-guided Inétialization (SPoGInit). SPoGInit employs an optimization algorithm to determine initial weight variances that effectively stabilize all three signal propagation metrics. Experimental results demonstrate that SPoGImit significantly improves signal propagation across various architectures, enhancing the performance of deep GCNs, particularly for graph-based tasks involving long-range relationships. The effectiveness of SPoGInit demonstrates that improving the proposed SP metrics is instrumental in boosting deep GCNs' performance.
2
Preliminaries and Background
For any integer N N, we define [N] {1, ,,..., NJ.. For brevity, we use 0 denote the collection of trainable parameters in GNN model. For additional useful notation, see Appendix A
2.1 Graph convolutional networks
Featured graph. Let G = (V,E) be an undirected graph, where V is the set of nodes with |V| = n, and & is the collection of edges. Assume that each node is associated with a dy-dimensional feature and a label belonging to the set [C], where C 2 denotes the number of possible labels. Let x, Rd and y, E [C] denote the feature and the label of node i, respectively. Define the node feature matrix ((i.))))))
RRa represent the adjacency matrix and D = diag(AA (1n,) E gnxa represent the degree matrix. Further, Á = A+1 and D = ++1 denote the adjacency matrix and the degroe matrix of graph 9 with self-loop added to cach node. Finally, the normalized adjacency matrix is given by
X (2,,5)
E IRnxdo, Let
A
Vanilla GCN. Vanilla GCN Kipf & Welling 2017) stacks neighborhood aggregations and feature trans- Ruxd denote the pre-activation and the post-activation
formations alternately. Specifically, let embedding matrix at the I-th layer of the vanilla. GCN, respectively. They are defined recursively by
())
H = Ax0-U + +1, b0),
:- ===0)(1))))
where W(O E 1xd and 60) E L1xd are the weight and the bias term at the I-th layer, respectively. The input to the first layer is given by (0) = X, and the output matrix of an L-layer vanilla GCN is H(L) E R which is then fed into a softmax layer to obtain the predicted labels.
ResGCN and gatResGCN. Inspired by He et al. 2016 ResGCN (Kipf & Welling 2017) combines residual connections with vanilla GCN. An L-layer ResGCN adds skip connections to the post-activation embeddings, i.e.,
H = (x(1)1 + -1.- == 1 e
[4],
where Wil) E Raxd and b00 E Rixd are the weight and the bias term at the I-th layer, respectively, while f Note that the above formulation requires the hidden dimensions of ResGCN to be equal across all layers. The input of the first layer is given by (0) XW(O) and the output of the network is given by oout (2() where Wr Iddedd and W(++1) e dx are trainable lincar transformations to ensure dimension compatability. The output yout E NxC is then fod into a sofumax layer to obtain the predicted labels. The architecture of a gating ResGCN (gat ResGCN) is identical to that of ResGCN, with the exception that the fixed hyper-parameters a. 3 replaced by trainable gating parameters (1)), g() for each layer E [L].
a. E R are predetermined hyper-parameters"
TThe original version of ResGNN Kipf Welling 2017 focuses on the special case (o,8) (1, 1).
3

---

Published in Transactions on Machine Learning Research (06/2025)
2.2 Initialization
We consider the following class of initialization methods. At initialization, all W Ikk are i.i.d. and satisly E[W krk = 0, Var[W k'k = / 1: all og are initialized to be 0 for any E [d--1], & E [di]. 1 [L].
Two widely used random initialization methods, LeCun initialization (Bottou 1988: LeCun et al.) 2002) and
Kaiming initialization (He et al. 2015 fit into this framework with of 1 and o = 2 respectively.
LeCun:
B[ Aik = 0 and Var[Wek] Aik = 1/d-- for any W' E [d-i)), E [di], 1 E [r.].
Kaiming (usually for ReLU): E ([ (1) k/k = 0 and Var(W k/k. = 2/d for any k' E [dr-1]. h E [di), I E [T].
In GCN models, uniform weight distribution with variance a = 1/3 is also widely used, e.g., in PairNorm (Zao & Akoglu 2020), DropEdge (Rong et al.) (020), DropNode (Huang et al. 2020), SkipNode (Lu et al.) 2021). GCNII (Chen et al. 2020b). We simply refer to this initialization as "Conventional initialization' " in the rest of this paper. Xavier initialization (Glorot & Bengio 2010) has weight, variance 2/(1/-1 + d) = 1/d when hidden layers have the same width d.
3 Theoretical Analysis of GCN Initializations
In this section, we evaluate the quality of GCN initializations from three aspects based on the signal propagation (SP) theory as follows.
Forward signal propagation (FSP) is responsible to extract abstract and higher-level representations from the input data as the information flows through the network. We propose the FSP metric M (o"), which is the expected output-input norm ratio Es [)[() (0)) A proper initialization method should prevent M (of.)) from either vanishing or exploding as L 00.
Backward signal propagation (BSP) is responsible for updating the weights by utilizing gradients computed via back-propagation. In vanilla GCN, the gradient of W(( at the I-th layer can be decomposed as dε/Ow()) = -(H . [[t/aH()] where is the training loss. A stable magnitude of ai (f/OH()) with respect the layer l suggests that the gradient is less susceptible vanishing or exploding. We take Ee [[][))/aw((()) at initialization as the BSP metric M (o..). A proper initialization method should prevent M (o?t) from vanishing exploding as L co.
Graph embedding variation (GEV) propagation is responsible for tackling the over-smoothing issue, a GCN-specific problem. A number of existing works (Cai & Wang 2020 Zhou et al. (021aa) measure over-smoothing severity by Dirichlet energy (i) = Liijee h v1+ d, hy/ /1 d where h;
is the output embodding of node Dirichlet energy Dir (L(()))) reveals the embodding variation with the weighted node pair distance, and a smaller value of Dir(H is highly related to the over-smoothing. To eliminate the influence of the embedding norm, we propose the GEV metric (L) which is the expected of normalized Dirichlet energy Eg [Di((H (1) at initialization. proper initialization method should prevent (L (ot) from vanishing L -
3.1 Theoretical results for vanilla GCN
We first theoretically evaluate the signal propagation (SP) quality at initialization in vanilla GCN. Due to the nonlinearity and high dimensionality of neural networks, the SP analysis is challenging. In order to simplify it, we study the infinite-width limit of vanilla GCN using mean field theory (Poole et al. 2016 Schoenholz et al., 2017). Different from traditional NNs, GNN blocks involve interactions across nodes, so we have to consider the SP of n nodes as an integrated whole, rather than that of only one data sample in NNs. Under this approximation, all the channels {11 (1) Jemi of each embedding at the (-th layer are i..d.,, following Gaussian distribution (O,, I()) The n x n covariance matrix ())) recursively satisfies
0 AGG y = =0==2a -xAX"" A//oo
4

---

Published in Transactions on Machine Learning Research (06/2025)
where G(E()) = Bx--:ro.>>))0()))(()))) E R=*" (see Appendix C.1 for the details). This theoretical framework is referred to as the neural network Gaussian process (NNGP) correspondence. Under the NNGP correspondence, the forward signal propagation (FSP) metric can be approximated by
MpSP 1 (o Re RHUO 200)
|
and the graph embedding variation (GEV) metric can be approximated by
M L (o
Dir(H
where HLL) ~ (O..,. E(D) means all columns (channcls) of (L) E R are i.d. N(O,, E(D).
Now we analyze the SP of GCN under various activation functions. We start with ReLU since is the most. commonly used activation in popular GCN models (e.g., Zhho & Akoglu (2020); Rong et al. (2020); Huang
ct al. (2020); Lu ct al. [2021) : Chen et al. (2020))). The following theorem states that under ReLU activation, if the initial weight variance Th < 2, which covers Conventional, Kaiming, and LeCun initialization deep
vanilla. GCNs suffer from poor FSP and GEV.
Theorem 3.1. Under the NNGP correspondence approzimation, when the activation function a is ReLU, we have
1. If o 2, either the limit graph embbdding variation. (GEV) metric lim ( = the limát forward signal propogation (FSP) metric lim M (o = 0;
2. When o < 2, the forward signal propagation (FSP) metric M (o 2C (o22/2) for any 1,2 1.
Part 1 of Theorem 3.1 shows that under Kaiming initialization in ReLU-activated vanilla GCN, either M (L) or M vanishes as > cc. Part 2 of Theorem 3.1 characterizes the shrinkage of M when o is even loss than that of Kaiming initialization. The proof Theorem 3.1 is provided in Appendix C.3
Theorem 3.2. Under the NNGP correspondence approzimation, when the activation is RELU, the groph embedding variation (GEV) metric M is independent of o.
Theorem 3.2 states that it impossible to improve the GEV metric, M ), by simply refining o for
ReLU-activated vanilla GCN. In other words, the over-smoothing issue cannol be resolved by adjusting weight. variance o in ReLU-activated vanilla. GCN. The proof of Theorem 3.2 is provided in Appendix C.4
We now provide numerical evidence for Thcorem 3.1 and 3.2 The purple lines in Figure [(c) illustrate the shrinkage of the three SP metrics under Conventiiona initialization as the network depth increases. Figure I a) when σy presents the vanishing pattern of M (ož) is greater than that of Kaiming initialization, which validates Theorem 3.1 Figure (bb shows that M (o")) transits from vanishing to stable, and then to exploding ob increases. Figure
c) shows that M (oß) cannot be improved via merely changing oā.
which validate Theorem 3
Different from ReLU-activated GCNs, Figure [1) shows that GEV metric transits from vanishing to stable for tanh-activated models as of increases. With proper og stable propagation for all three types of signals can be achieved; see the orange lines in Figure [d)- A theoretical result of the FSP for tanh-activated vanilla. GCNs is provided in Appendix C.5
3.2 Theoretical results for ResGCN
Similarly to vanilla GCN, performance degradation has also been reported in deeper ResGCN (Huang et al. 2020 Rusch et al. 2023a). In this subsection, we focus on the SP in ResGON.
IIn all the figures illustrating SP metrics, disappcaring uodes and vertical lines caused surpassing the machine precision. Specifically, the vanishing FSP result in vertical lines in the plots of the GEV metric, while the exploding FSP leads node disappearance the plots of the GEV metric.
5

---

Published in Transactions on Machine Learning Research (06/2025)
2 Kaiming
Kaiming
Kaiming
0.5 Kaiming
Conventional
Output-inpur Norm Ratio
Gradient Norm (I-stlayec)
Normalized Dirichle! Energy
10
10
1013
10-1
10
10-1
10
10-17
10-14
10-4
32 64
128 256 512
8
16
32
64
128
256
512
16
32
128
256
512
Depths
Depths
Deptis
(a) Forward SP
(b) Backward
(c) GEV
2 oxavier
1.5 kaavee
Ravier
Savier
Conventional
Normalized Dirichlet Energy
Output-inpur inpt Norm Ratio
Gradient Norm (1-st layer)
10-3
10
10-2
10
10-1
10-3
10-12
10
10-45
10-1
32 64 Depths
128
128 256
512
16
32
256 512
Depths
Depths
(d) Forward
(e) Backward
GEV
Figure 1: Plots of (a,d) forward metrics, (b,e) backward metrics, and (c,f) graph embedding variation metrics of deep vanilla GCNs with different initialization variances and activations on Cora. (Sub-figures (a)-(c) are for ReLU activation, while sub-figures (d)-(() are for tanh activation.) We average the results over 20 runs. We see that the choice initialization variance plays a crucial role in forward and backward propagation. The graph embedding variation propagation can made stable with proper initialization variance for tanh activation, but not for ReLU activation.
For simplicity, we study linear ResGCN with identity activation in the theoretical analysis. Such a simplification is very common in NN theory (Saxe et al., 2014 Xu et al. 2021 Similar to vanilla GCN, all the channels of (4) are i.idd N (O,, E)(4) under the infinite-width limit (a.k.a. NNGP correspondence). The x n covariance matrix (() recursively satisfies
500 - A50-)) S0-1, 500 of A/x"
(1)
See Appendix D.1 for the details.
The following theorem implies that linear ResGCN may suffer from forward signal explosion and over- smoothing under the NNGP approximation at initialization.
Theorem 3.3. Suppose that there erists an eigenvector u of Å corresponding to the eigenvalue 1, such that the input feature X E Raxdo satisfies X u + 0dxx1- Under the NNGP correspondence approrimation for linear ResGON, if 200 + 32 > and a + 0, then we have.
lim (L) pop (o2) = oo and
lim L-oo
(2) = 0.
L000
Since (a, = (1, for the original ResGCN Kipf & Welling 2017 a a²0² + B2 > and a * 0 always hold (L)
for any nonzero initialization variance, which indicates exploding M (o and shrinking ( (o.).

---

Published in Transactions on Machine Learning Research (06/2025)
Kaiming
Conventional
0.5 Conventional
0.1 Conventional
Conventional
Diticlle Energy
Oupur-inpat Norm Ratio
10-1
1011
10-2
10
10-3
10*
10
10
8
16
32 64
128
256
512
16 64
128 256
512
Depths
Depths
Forward
Figure 2: (a) The forward metrics and (b) the graph embedding variation metrics of U-Actiiiee deep ResGCN on Cora. We average the results over 20 runs. ResGCNs with non-zcro initialization variances always suffer from exploding forward propagation and over-smoothing.
Numerical experiments demonstrate that the consequences of Theorem 3.3 can be observed on ResGCNs with non-lincar activations. In Figure 2 we plot the FSP and the GEV of ReL.U-activated ResGCN with different initialization variances. We see that the widely used Conventional and Kaiming initialization schernes (Huang et al. 2020 Kipf & Welling 2017) (and essentially any non-zero initialization variance) lead exploding forward propagation and over-smoothing.
In summary, the discussions in Section 3.1 and 3.2 provide theoretical guarantee that the traditional initialization schemes utilized in both vanilla GCN and ResGCN fail to achieve proper SP. To address this challenge, we will introduce new initialization schemes in the subsequent section.
4 SPoGInit: Initialization guided by signal propagation on graph
In this section, we propose a new initialization design method, termed Signal Propagation on Graph-guided Initialization (SPoGInit), by enhancing the three types of signal propagation (SP) of GCNs. Through this method, we aim to demonstrate that stabilizing SP can lead to improved performance in deep GCNs and effectively mitigate the performance dogradation problem. SPoGInit determines layer-wise initialization variances by solving an optimization problem tailored to the SP of GCNs. To be more specific, given a GCN with L layers, denote the variance of the I-th layer by o²,, SPoGInit solves the following optimization problem:
minimize {owa)t
wi VES W2 BSP W3 GEV
(2)
where VISP and VESP respectively measure the stability for the FSP and BSP metrics across varying depths.
simple path, suggesting that the stability of SP might be inferred by comparing the SP metrics between very shallow and very deep blocks. Accordingly, define VTSP (M(1) PSP /M(--M 1)2 to encourage stable FSP across hidden layers. Similarly, VESP is defined as (M (L 1)2 to encourage BSP, with the superscript numbers in parentheses indicating the layer indices relevant to the gradient norm. We 2 rather than M( to compute VESP to ensure consistent dimensionality across different layers, since the weight parameters of the first layer differ in size from those of the subsequent layers.
For vanilla GCNs, the computational graph often be abstracted
For GCNs with skip connections, the computational graph becomes more complex. It is challenging to directly assess the stability of signal propagation by merely examining the SP metrics in very shallow and very deep blocks. Instead, we replace the denominator vanilla. GCN's Vep formula with the smallest FSP metric value, and the numerator with the largest FSP metric value across all the layers. Mathematically, we have
2
max MQ) min (( (1) FSP/
ISKL PSP -1
FSP
IsleL

---

Published in Transactions on Machine Learning Research (06/2025)
Similarly, we introduce the modification on VISP for GCNs with skip connections follows:
-1) )
2
V
RSP
max
M
BSP/
min
M (1)
I<|<L
1<1<L
Besides, in 2 wi W2, W3 > 0 are pre-defined for balancing these three SP metrics, During the implementation of SPoGImit, we adjust the weight initialization variances across layers by gradient descent algorithm. More details about SPoGInit are in Appendix
5 Numerical Experiments
In this section, we examine the proposed SPoGInit initialization through series of empirical experiments on various GCN architectures and benchmarks. In Section 5.1, we briefly introduce the experimental settings. In Section 5.2, we demonstrate how SPoGTnit improves signal propagation (SP) in different GCN architectures. Finally, in Section 5.3, we showcase the performance of deep GCN models equipped with SPoGInit on mainstream datasots and graph- based tasks involving long-range relationships.
5.1 Experiments setting
Datasets. We focus on four mainstream datasets and two graph-based tasks involving long-range relationships.
The mainstream datasets include Cora, PubMed (Sen el al. 2008 Yang et al., 2016). OGBN-Arxiv (Hul et al.) 2020), and Arxiv-year (Lim al., 2021). For these mainstream datasets, we use their default training/ halpgg//vaiiiaaiininnoo splits. Statistics of these datasots summarized in Table [
As for the graph-based (asks involving long-range relationships, we consider 1) the semi-supervised node classification task under missing feature settings, and 2) solving mixed integer linear programming (MILP) problems using GCN-based methods. Further details on these tasks will be provided in Section 5.3
Table Statistics of the mainstream datasets used in the experiments.
Dataset
Nodes
Features
Edges
Class
Homophily
Training, Vaaidaaiiiaaaanaaaa /Test Test
Cora
2,708
1,433
10,556
0.81
5.2% 10%% /36.9%
PubMed
19,717
500
88,648
0.80
0.3% 22.5/ 22.5 /5.6./..119
OGBN-Arxiv
169,343
128
1,166,243
40
0.66
73, 11.61....% /28.7% 50%/25% 25%
Arxiv-year 169,343
128
1,166,243
5
0.22
Architectures and Baselines. For the GCN architectures, consider the vanilla GCN, and the GCN models with skip-connections: ResGCN (Kipf & Welling 2017) and the popular MixHop (Abu-El-Hail et al. 2019). Additionally, we examine ResGCN with trainable gating parameters, referred to as GetRes Regarding initialization baselines, we consider standard initialization methods in DNNs and GNNs, including Xavier and Conventional initialization. Besides, we also include VirgoFor and VirgoBack, which are the initialization techniques tailored for GCNs (Li et al. 2023), as part of our baselines. We note that since every layer of MixHop mixes the powers (with different orders) of the adjacency matrix during information aggregation, VirgoFor and VirgoBack are not directly applicable MixHop. Thus, our baselines for MixHop only include Conventional and Xavier initializations.
Implementation. We conduct all experiments using PyTorch. To prevent out-of-memory issues with deeper models and ensure fair comparisons, we fix the width of all models at 64. In our experiments, we use the tanh activation function for vanilla GCNs, as Theorem 3.2 shows that the graph variation embedding of vanilla GCNs with ReLU activation does not benefit from further optimization. For other GCN architectures, we use the ReLU activation function. All results are averaged over least three runs. More details of hyperparameters provided in Appendix G.1
8

---

Published in Transactions on Machine Learning Research (06/2025)
SPoGInit
Xavier
Conventional
VirgoFor
VirgoBack
10
Normalized Dirichles Energy
Ouiput-input Norm Ratio
Gradient Norm (1-st (1-st layer)
100
10-2
10
10-3
10-2
10-1
10-4
10
10
4
8
16
32
64
128
256
8
16
32 Depths
64
128
256
16
32
64
128
256
Depths
Depths
(d) Forward SP
(c) Backward SP
(i) GEV
Figure Plots of (a) forward metrics, (b) backward metrics, and (c) graph embedding variation metrics of deep vanilla GCNs with different depths on Cora. SPoGInit highly effective stabilizing all three SP metrics.
SPoGInit
Xavier
Conventional
VirgoFor
VirgoBack
Output- imput Norm Ratio
Gradtent (1-st layer)
10
Normalized Dirichler Energy
10
1010
10
10-2
106
10
10-3
10a
10a
10-4
32
64
128
16
32
128
8
64
128
Deptis
Depths
Depths
(a) Forward
(b) Backward SP
(c) GEV
Figure 4: Plots of (a) forward metrics, (b) backward metrics, and (c) graph embedding variation metrics of deep ResGCNs with different depths on Cora. SPoGInit is highly effective stabilizing all three SP metrics.
5.2 Experiments on mainstream datasets
In this section, we illustrate how our proposed SPoGInit improves the performance of deep GCN models on mainstream datasets. Specifically, address the following questions:
Q1: Can SPoGInit improve the signal propagation (SP) of GCN models?
Q2: Can SPoGInit alleviate the performance degradation in deep GCNs?
Can SPoGInit improve the SP of GNN models (Q1)? On the Cora dataset, we examine the SP across various models, inchuding GCN, ResGCN, and MixHop, under different initializations and depths.
Figures and respectively present the changes in three SP metrics as the depths of GCNs, ResGCN, and MixHop models increase. The results in Figure 3 indicate that on vanilla GCN, both Conventional and Xavier initializations cause diminishing forward SP, backward SP, and graph embedding variations (GEV), which lead to gradient vanishing and over-smoothing issues. The VirgoFor and VirgoBack initialization methods can stabilize the forward SP and maintain the diversity of graph features, but they result in exploding backward SP, leading to gradient explosion. In contrast, SPoGInit is highly effective stabilizing all three SP metrics.
Figure 4 shows that as the depth increases, ResGCNs with all bascline initializations suffer from exploding forward- backward SP, and diminishing GEV, which lead to gradient explosion and over-smoothin problems. In contrast, the SPoGInit method effectively stabilizes all three SP metrics in deep ResGCNs.

---

Published in Transactions on Machine Learning Research (06/2025)
SPoGImit
Xavier
Conventional
Ouiput-input Norm Ratio
Gradient Norm (1-st (1-st layer)
Normalized Dirichles Eleegy
10P
100
10-1
10 7
10-2
10-2
10-4
10-3
10
10
16
32
64
128
16
32
64
128
8
16
32 Depths
64
128
Depths
Depths
(a) Forward SP
(b) Backward SP
(c) GEV
Figure 5: Plots (a) forward metrics, (b) backward metrics, and (c) graph embedding variation metrics of deep MixHop with different depths on Cora. SPoGInit is highly effective stabilizing all three SP metrics.
Figure 5 shows that as the depth increases in the MixHop model, Conventional and Xavier initializations succeed in maintaining forward SP and the GEV. However, the backward SP significantly diminishes, leading to severe gradient vanishing in deep models. SPoGInit, on the other hand, effectively stabilizes all three SP metrics.
In summary, these results demonstrate that SPoGInit is capable of finding initializations that stabilize these three SP metrics, thereby alleviating the training difficulties associated with deep models and mitigating the performance degradation as the networks go deeper.
Can SPoGInit Alleviate Performance Degradation in Deep GCN Models (Q2)? We present the detailed numerical results for GCN models with varying depths and initializations across four mainstream datasets, shown in Table More details of hyperparameters are provided in Appendix G.1
Table demonstrates that SPoGInit significantly roduces performance degradation compared to bascline initializations across various GCN models and datasets. For certain models and tasks, SPoGInit can even enhance the performance consistently as network depth increases from to 64, unleashing the potential of deep GCNs. Specifically, in deep ResGON and gatResGCN models, baseline initializations cause notable test accuracy drops exceeding 30% the OGBN-Arxiv dataset and 15% on the Arxiv-year dataset compared to their shallow counterparts. In contrast, deep ResGCN and gat ResGCN models with SPoGInit achieve performance gains of from 1.2% to 3.0% as depth increases from 4 to 64 across all the tested datascts. For deep vanilla GCNs and MixHop models, SPoGInit exhibits substantially less accuracy decline than baseline initializations on most the tested datasets. For example, SPoGInit reduces the test accuracy drop for the 64-layer MixHop by around at least 20% on both Cora and OGBN-Arxiv datascts.
Furthermore, we emphasize that SPoGInit exhibits greater robustness over various GCN models. Specifically, that Xavier, VirgoFor, and VirgoBack perform well on deep vanilla GCNs, all surpassing Conventional initialization on the four datasets. However, their performance significantly degrades on deep ResGCNs. In contrast, SPoGInit demonstrates excellent versatility, achieving less performance degradation across models of varying depths and architectures.
Further exploration SPoGInit. SPoGInit, as previously introduced, begins with given starting initialization and searches for more stable signal propagation (SP) by solving optimization problem (2) In most cases, we select Xavier initialization as the starting point for SPoGInit in the experiments above. Now we explore the adaptability of SPoGInit by studying how it performs when starting from different initializations.
We report the performance of vanilla GCNs on the OGBN-Arxiv datasot, with four baseline initializations, alongside SPoGInit which is applied starting from each of these four initializations, as shown in Table The results indicate that SPoGInit. effectively incorporate different initializations, leading to better
10

---

Published in Transactions on Machine Learning Research (06/2025)
Table 2: Test accuracies of GCN models with varying depths and initializations. The bold figure highlights the best performance among different initializations. 'Deg" refers to the test accuracy degradation as the depth increases from 4 to 64 layers. The smallestt performance drops are highlighted in orange. The results demonstrate that SPoGImit significantly reduces performance degradation compared to baseline initializations and enhances the performance of deep GNN models across different architectures.
Cora
Arxiv
Model
Init.
16
32
64
Deg.
16
32
64
Deg.
Conventional
79.3
71.2
56.6
48.5
33.3
4 46.0
69.2
67.5
44.9
39.1
8.0
[ 61.2
Xavier
80.3
79.1
75.2
72.8
71.5
8.8
69.6
09.3
64.1
57.9
38.1
4 31.5
GCN
VorgoFor
80.4
80.0
76.7
74.3
73.4
7.0
69.9
69.4
69.3
67.0
61.4
8.5
VirgoBack
80.3
77.4
74.9
74.3
73.2
7.1
69.7
69.5
69.2
67.5
60.9
4 8.8
SPoGInit
79.8
79.6
78.2
75.8
73.7
6.1
69.8
69.1
66.8
63.8
48.4
21.4
Conventional
78.0
78.5
77.5
77.6
78.2
0.2
70.3
71.6
72.0
70.4
34.8
4 35.5
ResGCN
Xavier
78,0
79.1
77.7
76.8
71.6
6.4
70.5
71.6
70.7
53.0
16.5
4. 54.0
VirgoFor
78.5
78.6
77.5
74.1
54.2
24.3
70.5
71.0
66.4
20.3
11.3
4 39.2
VirgoBack
79.3
78.2
77.8
73.9
29.2
50.1
70.6
71.1
66.5
20.1
12.5
4 58.1
SPoGInit
75.7
77.9
78.5
78.5
80.1
4.4
70.4
71.5
72.3
71.8
71.3
1 0.9
Conventional
77.4
78.22
78.0
77.9
77.0
4 0.44
70.7
71.8
71.6
70.0
27.9
4 42.8
gatResGCN
Xavier
77.9
78.5
76.6
77.4
73.2
4.7
70.5
71.4
70.8
45.1
16.5
54.0
VirgoFor
78.9
77.6
70.5
35.5
4 43.4
70.4
70.7
65.7
20.4
11.3
4 59.1
VirgoRack
79.0
78.3
76.2
70.5
37.9
4 41.1
70.5
70.7
65.9
20.1
12.5
4 58.0
SPoGInit
76.3
77.8
78.2
78.1
77.6
1 1.3
70.2
71.5
72.1
72.5
72.8
2.6
Conventional
72.5
52.0
36.4
46.9
42.0
L 30.5
68.0
64.1
59.8
52.6
38.2
J 29.8
MixHop
Xavier
79.3
75.1
71.6
64.3
56.3
+ 23.0
67.9
64.0
60.1
53.0
38.0
+ 29.9
SPoGInit
79.6
75.0
76.8
72.0
72.2
7.4
69.9
70.9
70.3
68.6
61.5
8.4
PubMed
Arxiv- year
Model
Init.
4
8
16
32
64
Deg.
4
8
16
32
64
Deg.
Conventional
75.9
67.1
68.0
60.8
4 15.1
44.1
42.7
44.2
43.6
39.9
4.2
GON
Xavier
78.1
76.8
76.0
77.2
75.7
4 2.4
44.0
42.3
45.5
45.6
43.9
J 0.1
VigorFor
78.9
78.5
78.2
77.8
75.9
3.0
43.9
30.0
45.4
45.6
41.8
2.1
VigorBack
75.5
76.5
76.0
74.7
3.4
43.7
29.8
45.3
45.4
41.8
1.9
SPoGInit
77.4
77.5
77.0
78.4
78.1
1 0.7
43.9
41.9
45.2
44.9
43.9
0
Conventional
74.9
76.1
76.0
76.8
76.6
1.7
48.2
49.6
49.7
43.6
32.6
15.6
ResGCN
Xavier
75.8
77.5
75.7
76.5
74.8
1.0
48.4
49.0
46.0
31.9
23.0
25.4
VigorFor
76.2
77.6
76.6
76.1
74.5
J. 1.7
48.3
48.4
38.9
29.6
26.2
4 22.1
VigorBack
77.0
77.6
76.9
77.0
74.9
1 2.1
48.1
38.6
29.1
24.9
J 23.2
SPoGInit
75.4
76.2
76.4
77.0
77.4
1 2.0
47.7
49.8
50.9
51.9
49.3
1 1.6
Conventional
74.4
76.9
76.0
76.6
76.0
1.6
48.7
50.5
49.5
41.6
31.8
16.9
gatResGCN
Xavier
76.3
77.6
75.6
77.2
75.8
0.5
48.5
49.5
45.8
32.6
23.0
4 25.5
VirgoFor
76.2
77.6
77.1
76.1
74.3
1.9
48.5
48.4
38.9
31.5
26.2
22.3
VirgoBack
76.6
77.9
76.8
75.8
75.0
1.6
48.3
38.8
29.6
25.0
4 23.3
SPoGInit
74.8
75.9
75.6
76.7
77.2
1 2.4
47.9
49.3
50.0
50.6
51.0
1 3.1
Conventional
73.3
65.1
68.1
65.9
56.4
16.9
47.8
48.6
49.2
47.7
42.3
5.5
MixHop
Xavier
76.6
76.1
72.5
72.4
71.1
5.5
47.9
48.6
49.2
48.5
42.0
4 5.9
SPoGInit
76.8
77.1
75.2
76.3
74.3
4 2.5
48.3
50.2
51.3
52.0
50.5
1 2.2
performance. Spocifically, when starting from the Xavier and Conventional initializations, SPoGInit achieves nearly 10% and 50% improvements in vanilla GCNs with 64 layers compared to these two initializations. Furthermore, when starting from the GNN-based initializations (VirgoFor and VirgoBack)), SPoGInit also delivers better performance in deep GCNs. However, it is important to note that when using ResGCN, VirgoFor and VirgoBack exhibit significant performance degradation. Despite this, starting from these GNN-based initializations, SPoGInit still significantly improves performance by more than 58% in deep ResGCNs with layers.
These results demonstrate that although different GNN architectures may favor specific initializations, starting from these initializations, SPoGInit. can further enhance the performance. Its strong adaptability allows
11

---

Published in Transactions on Machine Learning Research (06/2025)
Table 3: Test accuracies of GCN models with varying depths and initializations the OGBN-Arxiv dataset. 'Improv." refers to the test accuracy changes after replacing the original initializations with SPoGInit, which starts from those initializations. The results demonstrate that SPoGInit achieves better performance across various models by starting from different initializations.
Arxiv
Model
Init.
8
16
32
64
Conventional
69.2
67.5
44.9
39.1
8.0
inoGInit
69.7
69.2
68.1
63.1
56.9
Improv.
0.5
1.7
1 23.2
1 24.0
1 48.9
Xavier
69.6
69.3
64.1
57.9
38.1
SPoGInit
69.8
69.1
66.8
63.8
48.4
Improv.
t 0.2
0.2
2.7
5.9
10.3
GCN
VirgoFor
69.9
69.4
69.3
67.0
61.4
SPoGInit
69.6
69.6
68.7
67.2
61.4
Improv.
1 0.3
0.2
0.6
0.2
0
VickoBack
69.7
69.5
69.2
67.5
60.9
SPoGInit
69.6
69.7
69.0
67.2
61.8
Improv.
1 0.1
0.2
4
4 0.3
1
Conventional
70.3
71.6
72.0
70.4
34.8
SPoGInit
70.3
71.2
71.9
71.9
71.5
Improv.
0.4
0.1
t 1.5
f 36.7
Xavier
70.5
71.6
70.7
53.0
16,5
SPooGInit
70.4
71.5
72.3
71.8
71.3
Improv.
4 0.1
0.1.1
1.6
18.8
t 54.8
ResGON
VirgoFor
70.5
71.0
66.4
20.3
11.3
SPoGInit
70.0
71.3
72.0
72.1
71.2
Improv.
0.5
0.3
6.4
t 51.8
f 59.9
VirgoBack
70.6
71.1
66.5
20.1
12.5
SPoGInit
70.2
71.4
72.0
72.3
71.4
Improv.
0.4
0.3
5.5
1 52.2
1 58.9
SPoGInit to achieve better results across various models by effectively integrating with different initialization techniques.
Additionally, provide ablation study on the SP metric components within SPoGInit in Appendix G.2
5.3 Experiments on graph-based tasks involving rangerange relationships
Missing fcature scttings. To investigate the performance of SPoGInit on the graph-basod tasks involving long-range relationships we first conduct experiments the datasets under missing feature settings following (Zhao & Akoglu 2020). Specifically, we construct graph datasets by zeroing out designated proportion of node features in the validation and test sets while preserving their corresponding labels. The details of the missing feature settings are provided in Appendix G.1 Within the semi-supervised learning framework, a high proportion of missing features necessitates multiple feature aggregations from the training set for accurate label prediction in the validation and test scts. This approach effectively amplifics the challenge of learning range relationships within the dataset.
We adopt the missing feature setting with different missing proportions the Arxiv-year dataset. We examine the performance of various GCN models with differont depths and initializations over these settings. Table A presents the best performance of different GCN models, ranging from 8 layers to 64 layers, along with the optimal depth that achieves the best performance. The results indicate that under higher feature missing proportion, the models with SPoGInit tend achieve their best performance at larger dopths. SPoGInit demonstrates a significant improvement over baseline initializations, especially under 100% missing proportion, i.e., where all node features in the validation and test sets missing. Moreover, deep ResGCN
12

---

Published in Transactions on Machine Learning Research (06/2025)
Table 4: The optimal performance of various deep GCN models, ranging from 8 64 layers, with different initializations under missing feature settings. The figures in parentheses denote the depth corresponding to the optinal performance. Bold figures show the best performance for each model and the best performances across all architectures are highlighted in orange. The term "optimal improvement" refers to the maximum performance enhancements achieved by SPoGTnit compared to the best performance of baseline initializations across the various models. The results indicate that optimal performance on datascts with long-range relat colthioss is alainnd al greater depths, and SPoGInit enhances the performance of deep GCN architectures.
Model
Init.
Missing 50%
Missing 100%
Conventional
43.1 (16)
41.6 (16)
Xavier
43.3 (16)
42.5 (16)
GCN
VirgoFor
40.1 (16)
41.9 (16)
VirgoBack
42.0 (16)
42.0 (16)
SPoGInit
43.1 (32)
42.4 (16)
Conventional
45.8 (16)
43.9 (16)
Xavier
45.2 (8)
43.1 (8)
ResGCN
VirgoFor
45.4 (8)
43.0 (8)
VirgoBack
45.2 (8)
42.9 (8)
SPoGInit
46.3 (64)
45.1 (64)
Conventional
45.5 (16)
43.3 (16)
Xavier
44.7 (8)
42.2 (8)
gatResGCN
VirgoFor
45.2 (8)
42.6 (8)
VirgoBack
45.0 (8)
42.6 (8)
SPoGInit
45.3 (16)
43.4 (32)
Conventional
45.1 (8)
42.9 (16)
Xavier
45.1 (8)
42.8 (16)
MixHop
SPoGInit
44.9 (8)
44.6 (16)
Optimal Improvements
+0.5
+1.7
with SPoGInit achieves the best performance across all the tested architectures and initializations. These findings demonstrate the potential of deep GCNs in graph-based tasks involving long-range relationships and the effectiveness of SPoGInit in unleashing such potential.
GCNs for Combinatorial Optimization. In recent years, GNNs have emerged as a powerful tool for addressing Combinatorial Optimization (CO) problems, which are fundamental areas such as computer
science and operations research (Paschos 2014 Many classical CO problems are extremely difficult. to solve
due to their NP-hardness (Bonze al.) 1999 Gavish & Graves 1978 Coffman Jr et al. 1984). To address these difficult CO problems, expert-designed heuristic algorithms (Boussaid et al.) 2013) developed to find near-optimal solutions within reasonable computational limits. Over the past. decade, machine learning-based methods (Bengio et al. 2021 have gained significant interest in tackling CO problems. It has been shown that with sufficient data and proper training, neural networks have the potential of surpassing expert-designed methods in both performance and efficiency (Alvarez et al. 2017 Khalil et al. 2016 2017). Given that many CO problems naturally have graph structure, GNNs have become a highly promising approach (Gasse et al. 2019
In this work, consider the Maximal Independent Set (MIS) problem, classic CO problem in graph theory with significant applications in network analysis, wireless communication, etc. Given an undirected graph G = E), the objective is to find subset S C V of vertices such that S is independent, meaning no two vert in S are adjacent, and S is maximal, implying that no additional vertex can be added to S without violating its independence.
We note that MIS problems can involve inherent long-range range relationships between nodes. The inclusion of node in the independent set may significantly affect. all other nodes in the set. For example, consider
13

---

Published in Transactions on Machine Learning Research (06/2025)
cycle graph G with even number of nodes V1, V2,..., Vam In this cycle, each node connects to two others, forming closed loop. Tf Vi is included in S, its adjacent nodes Vam and V/2 cannot be part of S, allowing nodes V4m-1 and V/ to potentially be included in S. This cascading effect continues around the cycle, and it straightforward to show that the maximal independent set is {Vi, Vg...., V2m-1, V2m+1,..... Vam-1)- Similarly, if V12 is excluded from S, the maximal independent set becomes (V2, Va...., V2ms..., Vmm-1)- Notably, the predictions of whether Vj and V2m are the maximal independent set depend on each other, while the two nodes have a distance of 2m 1.
In this work, we follow the setting in Han et al. (022 and apply GNN to solve MIS problems. The MIS problem is typically formulated as an Integer Linear Programming (ILP) problem:
max x2
iEV
s.t. 3j + F.y 1 v(I.)) EE, 2 {0, 13.
Based on this formulation, a variable-constraint bipartite graph representation is constructed. The set of variable nodes V (each denoted by i) is placed on one side of the bipartite graph, while the set of constraint nodes & (each representing an edge (i. the original graph) is placed on the other side. Each variable node i and j is connected to the corresponding constraint node (i,j). Following Han al. (2022). we adopt predict and search framework. The predicting stage utilizes GNN over the bipartite graph representation to find good initial solution to the MIS problem, while the search stage refines this solution using the traditional ILP solver such as SCIP or Gurobi to obtain the final result.
We investigate the power of SPoGInit in improving the performance of bipartite GCNs for solving MIS problems. We utilize the Independent Set (IS) dataset (Bergman et al. 2016), where each instance comprises 600 constraints and 1500 binary variables. The bipartite GCN models are trained on 80 problem instances and then applied to prediet the optimal solution (0 1) for each node across 20 test instances. We set the learning rates 1e-3, 5e-4, and 5e-5, for bipartite GCN models with 2, 8, and 16 layers, respectively.
The experimental results, shown in Table 5 indicate that bipartite GCNs often achieve performance improvements as their depths increase. With Xavier initialization, there is approximately a 4% increase in accuracy from 2 to 16 layers. Moreover, employing SPoGInit yields greater performance enhancements, with an approximate 7% increase in accuracy from 2 to 16 layers, and surpasses the baseline methods on the 16-layer network.
Table 5: Test accuracy of bipartite GNN models on ILP tasks across varying initializations and depths. The results underscore the critical role of depth in solving ILP problems with Bipartite GCNs. Furthermore, SPoGInit significantly boosts the performance of deep Bipartite GCNs, leading to optimal accuracy.
Model
Init.
2 layer
8 layer
16 layer
Conventional
78.9
82.7
84.1
Bipartite GCN
Xavior
78.5
81.0
82.2
SPoGInit
78.7
83.0
85.2
Conventional
79.4
85.4
85.5
Bipartite GCN with skip connection
Xavier
79.4
82.2
48.6
SPoGInit 79.4
84.7
87.5
Further, we adopt skip connection in bipartite GCNs and train the models with various depths using the Adam optimizer at a learning rale of 1e-3. We see that incorporating skip connections ions boosts the performance of Bipartite GCNs, This enhancement is likely attributed to the reinforcement the initial embeddings associated with the ILP problem. However, Xavier initialization faces training failure issues and fails deliver substantial benefits during the deepening process, and Conventional initialization shows minimal gains when the network depth is increased from 8 to 16 layers. Conversely, SPoGInit consistently provides ongoing
14

---

Published in Transactions on Machine Learning Research (06/2025)
benefits as the network depths increase. With SPoGInit, the 16-layer bipartite GCN with skip connections achieves optimal performance across all initializations, models, and depths.
6
Related works
O Over-smoothing in GCNs.
The concept of over-smnotthing is first introduced in Li et al.
2018 to explain
the performance degradation in deeper GCNs. This issue is later explored through both theoretical and
empirical studies (Oono & Suzuki 2019 Cai & Wang 2020 Yang et al. 2020 Maskey ot al.
2024 Yang ct al.,
2024
Chen et al. 2020a Nguyen et al. 2023 Rusch et al. 2023b Roth & Liebig| 2024 Roth 2024 Luan
jt al. 2020; Cong et al.
2021 Zhang et al. 2022a]. While the smoothing effect of graph convolution may
benefit shallow GCNs (Keriven 2022 Wu et al. 2023) it adversely affect the performance of deep GCNs.
To alleviate over-smoothing, various techniques have been proposed Chen et al. 2022c
Wang et al. 2021
including node or edge dropping (Srivastava et al.
2014
Zou et al. 2019 Rong et al.
2020 Huang et al.
2020
Lu et al. 2021 Fang et al.) 2023 Han et al. 2023a Finkelshtein et al. 2023).
normalization hods
[loffe & Szegedy 2015: Zhao & Akoglu 2020 Zhou et al.
2020b] Yang et al., 2020: Zhou et al. 2021b Li
let al.
2020 Guo et al., 2023), and regularization strategies (Chen et al. 2020a Yang et al., 2020: Zhou
ct al.
2021a]. In addition to these techniques, substantial efforts have been dedicated to modifying GCN
architectures, such as incorporating residual connections (Kipf & Welling 2017
Jaiswal et al. 2022;
Chen
et al.
2022b Scholkemper et al. 2024), jumping connections (Xu et al.] 2018
Liu et al.)
2020 Zhu et al.
2020), and other architectural modifications (Bose & Das 2023 Di Giovanni et al.) 2022
Chien et al.
2021 1
Gasteiger et al.
2019:
Luan et al.
2019
Chen et al. 2020b
Li ct al.)
2019 Yan et al.
2022
Guo et al.
2022
Min et al.] 2020 Chen et al.
2022a
Jin et al.
2022
Zheng et al. 2021 Yang et al.
2023b
Li et al.
2021
Zhang et al.
2020;
Feng et al.
2022 Dong et al.
2021 Wu et al.) 2024 Choi et al. 2024 Zhang et al.
2022b;
Kelesis ct al.
2023). In recent years, a line of work has proposed using negative sampling, which incorporates
non-neighboring nodes into the aggregation process, to alleviate wrerssnoohing in GNNs. Duan et al. 2022
introduce determinantal point process (DPP)- based sampling to encourage diversity among selected negative samples. To improve scalability, Duan et al. (2023) construct candidate sets using shortest-path heuristics, significantly reducing computational cost. Building on this, Duan et al. 2024 propose layer-diverse negative sampling, which dynamically adjusts the sampling space across layers to reduce redundancy and improve the expressiveness of deep GNNs. These methods essentially mitigate over-smoothing by modifying the propagation mechanism of GCNs.
Different from these works, our paper investigates the impact of weight initialization tackle over-smoothing (as well as gradient pathology) in GCNs, without modifying the network architecture or the message passing mechanism. While a few recent works (Guo el al. 2022 Jaiswal et al. 2022 Li et al. 2023 have explored initialization to improve the training of GNN, they do not explicitly treat over-smoothing as one of their
primary concerns. Although Han et al. (2023b) applics analog MLP initialization to GNNs, it does not specifically address the performance degradation of deep GNNs.
Signal propagation. Classical signal propagation theory has built up foundation for understanding how information flows through deep neural networks (DNNs) and guides the random weight initialization.
At first., Glorot & Bengio| (2010); [e et al. (2015) study the forward-backward propagation in linear or
ReLU-activated models. Then, the mean-field theory (Neal 1996 Lee et al.) 2018: Matthews et al.) 2018
is incorporated to study the signal propagation in models with general lon-linear activation. Theoretical
analysis on fully-connected neural networks (FCNNs) includes the study of Edgo-of-Chaos (EOCs) Pooocc
et al. 2016 Schoenholz et al. 2017 Hayou et al.) 2019 2022) and dynamical isometry (Saxe et al.
2014
Pennington et al.
2017 2018
Other works study the signal propagation in deep CNN (Xiao et al.
2018
RNN (Chen et al.
20180.
ResNet (Yang & Schoenholz 2017: Hayou et al. 2022
autoencoder (Li & N Nguyen
2019 and LSTM
GRU Giilbo et al. 2019).
In the realm of GCNs, several recent works have proposed weight initialization techniques to stabilize signal propagation. For the forward pass, Jaiswal et al. (2022) focus on Topology-Awar Isometry, which differs from our focus on stabilizing the output-input norm ratio. For the backward pass, they rely on gradient-gun -uided dynamic rewiring, modifying the model architecture itself. In contrast, we control backward signal propagation
15

---

Published in Transactions on Machine Learning Research (06/2025)
through the BSP metric. Morcover, their method design does not address over-smoothing, while we explicitly incorporate the graph embedding variation (GEV) metric to do so. [elesis et. al. (2024) propose G-Init, which extends Kaiming initialization to the graph domain by incorporating graph topology-aware scaling. We include in Appendix F.6 a comparison experiment between G-Init and SPoGInit on vanilla GCN. The results show that while both G-Init and SPoGInit alleviate performance degradation in deep GCNs, SPoGInit. provides more consistent results and smaller accuracy drops across datasets. In addition, Guo et al.] (2022); Li et al. (0023) also build their approaches around forward and backward signal propagation, but do not investigate how initialization affects GEV to mitigate over-smoothing in deep GCNs. Also, we note that Han et al. (2033b) introduce MLPPIiit, which is not aimed at improving signal propagation or reducing over-smoothing. Instead, it seeks to accelerate training by initializing GNNs with the weights of a fully trained, equivalent MLP. This is a fundamentally different motivation from ours.
Weight initialization search. In traditional deep learning, some works have explored weight initialization search to improve training stability (Dauphin & Schoenholz 2019; Zhu et al. 2021). However, their objectives differ from ours. Dauphin & Schoenholz (2019) aims to minimize the curvature effects around the initial parameters by reducing the gradient quotient, which reffects local curvature sensitivity. Zhu et al. (022) aims at finding an initialization that minimizes the loss after a single training step. Our proposed SPoGInit, however, primarily targets mitigating signal propagation instability in the initialization of deep GCNs, by addressing both forward and backward SP as well as the over-smoothing issue.
infinie-wwitt-lliit regime. Our analysis relies on infinitewwdtth assumption common approach in traditional theoretical analyses of neural networks (sce, e.g., Lee et al. (2018); Sohi-Dickstein et al. (2020); Yang et al. (2024)) This assumption offers the primary benefit of ensuring that the feature embeddings at each layer follow a Gaussian distribution under random initialization, thereby simplifying the theoretical treatment. Such a Gaussian property not strictly guaranteed for practical, finite-width networks.
L.g
Nonetheless, we empirically demonstrate that the embeddings of a finite-width network are approximately Gaussian, implying that the infinitewwdtth approximation remains reasonable in practice. Specifically, we randomly selected three node embeddings from the final convolutional layer of a 4-layer, 64-width GCN network trained on the OGBN-Arxiv dataset. We then applied the Kolmogorov-Sminee hypothesis test to evaluate their distribution. In this lest, a p-value below 0.05 would indicate a significant deviation from a Gaussian distribution. The observed p-values 0.75, 0.90, and 0.73 suggest that the embeddings closely follow a Gaussian distribution. Thus, despite the thcorctical limitation, our empirical findings support the validity of using the infinite-width approximation.
Relationship with GNTK. NNGP (Neural Network Gaussian Process) for GNNs and GNTK (Graph Neural Tangent Kernel) are two theoretical tools used to analyze the behavior of graph neural networks While they share the common goal of characterizing GNNs in the infinite-width limit, they differ in focus: NNGP primarily describes the properties of feature embeddings at initialization, whereas GNTK captures the training dynamics of GNNs, particularly how the model converges under gradient descent. Some existing works study graph neural tangent kernel (GNTK) [Bayer et al.) 2022 Du et al.] 2019 Huang et al.) 2022
Jiang et al. 2022 Sabanayagam et al. 2021 2022 Zhou & Wang 2022 Gebhart
2022: Krishnagopal & Ruiz, Yang et al. 2023a). They analyze the training dynamics of GCNs under the infinite-width limit.
2023
7 Limitations and future works
SPoGInit has been specifically designed and tested for node classification tasks within GNNs. While the method has shown promising results in this context, its applicability to other tasks, such as edge prediction or graph classification, remains unexplored. Adapting SPoGInit for a wider range of graph-based learning tasks is as an important direction for future work.
Although SPoGInit is designed as a general method for GNNs, our current implementation not entirely plug-and-play for all GNN architectures. The integration of SPoGInit into novel or non-standard GCN variants (e.g., GCNIT CCen et al. 2020b), Graph Transforeer (Shehzad et al. 2024b) will require additional
16

---

Published in Transactions on Machine Learning Research (06/2025)
engincering efforts. Future work could focus creating more robust and flexible integration methods for broader range of GNN models, enhancing SPoGInit's adaptability.
As highlighted in our analysis, SPoGInit introduces an approximate 10%-20% computational overhead. While we believe this overhead is acceptable in many practical scenarios, it could become a limiting factor situations where computational resources are severely constrained. Future work could explore methods reduce the computational cost of SPoGInit, either through more efficient optimization techniques or by leveraging hardware acceleration.
8 Conclusion
We attempt to address the performance degradation of deep GCNs from the lens of signal propagation. We consider three metrics: forward propagation, backward propagation, and graph embedding variation propagation. Our thcorctical analysis and empirical studies revealed that widely used initialization mothods in GCNs fail to control these metrics simultaneously, resulting undesirable performance degradation as depth increases. Motivated by our SP framework, new initialization method, termed SPoGInit, is proposed. The experiment results demonstrate that SPoGInit enhances the signal propagation of various deep GCN architectures. Moreover, SPoGInit significantly mitigates performance degradation enables performance enhancement as depths increase, especially in graph-based lasks involving long-range relationships. Both our theoretical and empirical findings underscore the importance of stabilizing these three SP metrics for boosting the performance of deep GCNs.
Acknowledgement
The authors would like to express our sincere gratitude to Kenta Oono and the anonymous reviewers for their insightful feedback during the discussion phase. The authors also thank Bingheng Li and Haitao Mao for their helpful suggestions during the early stages of revision. This paper is supported in part by the National Key Research and Development Project under grant 2022YFA Technology Innovation Cooperation Zone Project Fund UDF01001499, the Chinese University of Hong Kong, Shenzhen; Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence (202381212010001); the Guangdong Major Project of Basic and Applied Basic Research (20238030300000),
Hetao Shenzhen-Hong Kong Science and University Development
References
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learning, pp. 21-29. PMLR, 2019.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A machine learning- based approximation of strong branching. INFORMS Journal on Computing, 29(1):185- 195, 2017.
Artun Bayer, Arindam Chowdhury, and Santiago Segarra. Label propagation across graphs: Node classification using graph neural tangent kernels. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3483 5487. IEEE, 2022.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290(2):405-42) -221 2021.
David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker. Decision diagrams for oplimizalion, volume 1. Springer, 2016.
Immanuel M Bomze, Marco Budinich, Panos M Pardalos, and Marcello Pelillo. The maximum clique problem. Handbook of Combinatorial Optimization: Supplement Volume A, pp. 1-74, 1999.
17

---

Published in Transactions on Machine Learning Research (06/2025)
Kushal Bose and Swagatam Das. Can graph neural networks go deeper without over-smoothing? yes, with randomized path exploration! In IEEF Transactions on Emerging Topics in Compulational Intelligence. LEEE, 2023.
Léon Bottou. Reconnaissance de la parole par reseaux connexionnistes. In Proceedings of neuro Nimes, volume 88, pp. 197-218, 1988.
Ilhem Boussaid, Julien Lepagnot, and Patrick Siarry. survey on optimization metaheuristics. Information sciences, 237:82-117, 2013.
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. In International Conference on Machine Learning. PMLR, 2020.
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. In Proceedings of the AAAT Conference Artificial Intelligence, volume 34, pp. 3438-3445 2020a.
Jialin Chen, Yuelin Wang, Cristian Bodnar, Rex Ying, Pietro Liò, and Yu Guang Wang. Dirichlet energy enhancement of graph neural networks by framelet augmentation. 2022a.
Jie Chen, Weiqi Liu, Zhizhong Huang, Junbin Gao, Jumping Zhang, and Jian Pu. Universal deep gnns: Rethinking residual connection in guns from a path decomposition perspective for preventing the over- smoothing. aixiv preprint 2rXiv:2205. 101122255111., 2022b.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp- 1725-1735. PMLR, 2020b.
Minmin Chen, Jeffrey Pennington, and Samuel Schoenholz. Dynamical isometry and a mean field theory of mnss: Gating enables signal propagation in recurrent neural networks. In International Conference on Machine Learning, pp. 873-882. PMLR, 2018.
Tianlong Chen, Kaixiong Zhou, Keyu Duan, Wenqing Zheng, Peihao Wang, Xia Hu, and Zhangyang Wang. Bag of tricks for training deeper graph neural networks: A comprehensive benchmark study. IEEE Transactions on Pallern Analysis and Machine Intelligence, 2022c.
Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing linear programs by graph neural networks. In The Eleventh International Conference on Leorning Representations, 2023.
Ziang Chen, Xiaohan Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. Expressive power of graph neural networks for (mixod-integer) quadratic programs. arXiv preprint arXiv:2406. 050,0580 2024.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
Yoonhyuk Choi, Jiho Choi, Tacwook Ko, and Chong-Kwon Kim. Better not to propagate: Understanding edge uncertainty and over-smoothing in signed graph neural networks. arXiv preprint orXiv:2408. K48:22400.0495, 2024.
Edward Coffiaa Jr, Michael Garey, and David S Johnson. Approximation algorithms for bin packing an updated survey. In Algoritho design for computer system design, pp. 49-106. Springer, 1984.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936 94:9936-9949, 2021.
Yann N Dauphin and Samuel S Schoenholz. Metainit: Initializing learning by learning to initialize. Advances in Newral Information Processing Systems, 32, 2019.
Francesco Di Giovanni, James Rowbottom, Benjamin P Chamberlain, Thomas Markovich, and Michael M
Bronstein. Graph neural networks as gradient flows: Understanding graph convolutions via energy. arXiv preprint Xix::2206. 10991, 2022.
18

---

Published in Transactions on Machine Learning Research (06/2025)
Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Adagnn: Graph neural networks with adaptive frequency response filter. In Proceedings of the 30th ACM international conference on informalion & knowledge management, pp. 392 401, 2021.
Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural langent kernel: Fusing graph neural networks with graph kernels. Advances in Newral Information Processing Systems, 32, 2019.
Wei Duan, Junyu Xuan, Maoying Qiao, and Jie Lu. Learning from the dark: boosting graph convolutional neural networks with diverse negative samples. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 6550 6558, 2022.
Wei Duan, Junyu Xuan, Maoying Qiao, and Jie Lu. Graph convolutional neural worwsrks with diverse negative samples via decomposed determinant point processes. IEFE Transactions on Newral Networks and Learning Systems, 2023.
Wei Duan, Jie Lu, Yu Guang Wang, and Junyu Xuan. Layer-diverse negative sampling for graph neural networks. Transaclions on Machine Learning Research, 2024.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference learning theory, pp. 907-940. PMLR, 2016.
Taoran Fang, Zhiqing Xiao, Chunping Wang, Jiarong Xu, Xuan Yang, and Yang Yang. DropMessage: Unifying random dropping for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4267-4275, 2023.
Xinshun Feng, Herun Wan, Shangbin Feng, Hongrui Wang, Qinghua Zheng, Jun Zhou, and Minnan Luo. Grato: Graph neural network framework tackling over-smoothing with neural architecture scarch. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp. 520-529, 2022.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorrh Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Ben Finkelshtein, Xingyue Huang, Michael Bronstein, and Ismail Ilkan Ceylan. Cooperative graph neural networks. arXiv preprint orXiv:2310.01267 2023.
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks, Advances in Neural Information Processing Systems, 32, 2019.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2019.
Bezalel Gavish and Stephen Graves. The travelling salesman problem and related problems. 1978.
Thomas Gebhart. Graph convolutional networks from the perspective of sheaves and the neural tangent kernel. In Topological, Algebraic and Geometric Learning Workshops 2022, pp. 124-132. PMLR, 2022.
Dar Gilboa, Bo Chang, Minmin Chen, Greg Yang, Samuel S Schoenholz, Ed H Chi, and Jeffrey Pennington. Dynamical isometry and mean field theory of Istms and grus. arXiv preprint arxiv: 19011901..000 190100888,, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. International Conference on Artificial Intelligence and Statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Kai Guo, Kaixiong Zhou, Xia Hu, Yu Li, Yi Chang, and Xin Wang. Orthogonal graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 3996-400 4006, 2022.
19

---

Published in Transactions on Machine Learning Research (06/2025)
Xiaojun Guo, Yifei Wang, Tianqi Du, and Yisen Wang. Contranorm: A contrastive learning perspective oversmoothing and beyond. In International Conference on Learning Represeniations, 2023.
Jiaqi Han, Wenbing Huang, Yu Rong, Tingyang Xu, Fuchum Sun, and Junzhou Huang. Structure-aware dropedge toward deep graph convolutional networks. IEEF Transactions on Neural Networks and Learning Systems, 2023a.
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang, Ruoyu Sun, and Xiaodong Luo. A gun-guided prodict-and-search framework for mixed-integer lincar programming. In The Eleventh International Conference on Learning Representations, 2022.
Xiaotian Han, Tong Zhao, Yozen Liu, Xia Hu, and Neil Shah. Mlpinit: Embarrassingly simple gun training acceleration with mlp initialization. 2023b.
Boris Hanin. Which neural net architectures give risc to exploding and vanishing gradients? Advances in Neural Information Processing Systems, 31, 2018.
Godfrey Harold Hardy, John Edensor Littlewood, George Pólya, György Pólya, al. Inequalities. Cambridge university press, 1952.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. On the impact of the activation function on deep neural networks training. In International Conference Machine Learning, pp. 2672-2680 PMLR, 2019.
Soufiane Hayou, Arnaud Doucct, and Judith Rousscau. The curse of depth in kernel regime. In I (Still) Can't
Believe II's Not Beller! Workshop al NewrIPS 2021, pp. 41-47. PMLR, 2022.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEFF Conference on Computer Vision and Pattern Recognation, pp. 770-778, 2016.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Newral Information Processing Systems, 53:22118-22131 2020.
Wei Huang, Yayong Li, Weitao Du, Jie Yin, Richard Yi Da Xu, Ling Chen, and Miao Zhang. Towards deepening graph neural networks: A gutk-based optimization perspective. International Conference on Learning Representations, 2022.
Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling ovor-smoohhing for general graph convolutional wetworks. arXiv preprinl arXiv:2008.009. 09864, 2020.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pp. 448 148-456.7 PMLR, 2015.
Ajay Jaiswal, Peihao Wang, Tianlong Chen, Justin Rousseau, Ying Ding, and Zhangyang Wang. Old can be gold: Better gradient flow can make vanilla-gent gens great again. Advonces in Neural Information Processing Systems, 35:7561-7574, 2022.
Shunhua Jiang, Yunze Man, Zhao Song, Zheng Yu, and Danyang Zhuo. Fast graph neural tangent kernel via kronecker sketching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7033-7041, 2022.
Wei Jin, Xiaorui Liu, Yao Ma, Charu Aggarwal, and Jiliang Tang. Towards feature overcorrelation deeper graph neural networks. 2022.
Dimitrios Kelesis, Dimitrios Vogiatzis, Georgios Katsimpras, Dimitris Fotakis, and Georgios Paliouras. Reducing oversmoothing graph neural networks by changing the activation function. In ECAI 2023, pp. 1231-1238. TOS Press, 2023.
20

---

Published in Transactions on Machine Learning Research (06/2025)
Dimitrios Kelesis, Dimitris Fotakis, and Georgios Paliouras. Reducing oversmoothing through informed weight initialization in graph neural networks. aiv preprint 10. 2024.
Nicolas Keriven. Not too little, not too much: theoretical analysis of graph (over)smoothing. In Advances in Neural Information Processing Systems, 2022.
Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Elias B Khalil, Bistra Dilkina, George L Nemhauser, Shabbir Ahmed, and Yufen Shao. Learning to run heuristics tree search. In Ijeai, pp. 659-666, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. Interna- tional Conference on Learning Representations, 2017.
Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C Bayan Bruss, and Tom Goldstein. Goat: A global transformer on large-scale graphs. In International Conference on Machine Learning, pp. 17375 17390. PMLR, 2023.
Sanjukta Krishnagopal and Luana Ruiz. Graph neural tangent kernel: Convergence on large graphs. arXiv preprinl ar Xiv:2230 10808, 2023.
Alex Krizhevsky, Πya Sutskever, and Geoffrey E Hinton. Imagenct classification with doep convolutional neural networks. Advances in Nearal Information Processing Systems, 25(1106-1114)1,, 2012.
Yann LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robert Müller. Efficient backprop. In Newral networks: Tricks of the trade, pp. 9-50. Springer, 2002.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl- Dickstein. Deep neural networks gaussian processes. In International Conference on Learning Represen- tations, 2018.
Bingheng Lı, Linxin Yang, Yupeng Chen, Senmiao Wang, Qian Chen, Haitao Mao, Yao Ma, Akang Wang, Tian Ding, Jiliang Tang, et al. Pchg--nrolled learning-to-optimize method for large-scale linear programming. arXiv preprint arXxx22466.0 01908, 2024a.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens, 2020.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International Conference on Machine Learning, 2021.
Jiahang Li, Yakun Song, Xiang Song, and David Wipf. On the initialization of graph neural networks. In International Conference on Machine Learning, pp. 19911-19999 PMLR, 2023.
Ping Li and Phan-Minh Nguyen. On random deep weight- autoencoders: Exact asymptotic analysis, phase transitions, and implications to training. In International Conference on Learning Representations, 2019.
Qian Li, Tian Ding, Linxin Yang, Minghui Ouyang, Qingjiang Shi, and Ruoyu Sun. On the power of small-size graph neural networks for linear programming. In The Thirty-eighth Annuull Conference Neural Information Processing Systems, 2024b.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Shiyu Liang and R Srikant. Why deep neural networks for function approximation? In 5th International Conference on Learning Representations, ICLR 2017, 2017.
21

---

Published in Transactions on Machine Learning Research (06/2025)
Derck Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In Advances in Neural Information Processing Systems, volume 34, pp. 20887 20902, 2021.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 338- 538-348, 2020.
Weigang Lu, Yibing Zhan, Ziyu Guan, Liu Liu, Baosheng Yu, Wei Zhao, Yaming Yang, and Dacheng Tao. Skipnode: On alleviating over-smoothing for deep graph convolutional networks. ar preprint 0rXiv:212..11622 2021.
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
Sitao Luan, Mingde Zhao, Xiao Wen Chang, and Doina Precup. Training matters: Unlocking potentials of deeper graph convolutional neural networks. arXiv preprint arXiv:2008 08838, 2020.
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Classic gnns are strong baselines: Reassessing gnns for node classification. arXiv preprint ar 0rxiv:2406.0000 08999, 2024.
Sohir Maskey, Raffacle Paolino, Aras Bacho, and Gitta Kutyniok. A fractional graph laplacian approach to oversmoothing. Advances in Neural Information Processing Systems, 36, 2024.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard E Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Represenlations, 2018.
Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering gen: Overcoming oversmoothness in graph convolutional networks. Advances in Newral Information Processing Systems, 04114498-145088 2020.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint ar arXiv:2012.333/ 2020.
Radford M Neal. Bayesion learning for neural networks, volume 118. Springer-Verlag. 1996.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Compulational Mathematics, 17(2):527 566, 2017.
Khang Nguyen, Nong Minh Hicu, Vinh Due Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting ever-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pp. 25956-222 -5979. PMLR, 2023.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2019.
Vangelis Th Paschos. Applications of combinatorial optimization. John Wiley & Sons, 2014.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: Theory and practice. Advonces in Neural Information Processing Systems, 30, 2017.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. The emergence of spectral universality in deep networks. In International Conference on Artificial Intelligence and Statistics, pp. 1924 1932. PMLR, 2018.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Lindmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint arXiv:2302.111 11640, 2023.
22

---

Published in Transactions on Machine Learning Research (06/2025)
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponential expressivity in deep neural networks through transient chaos. Advances in Newral Information Processing Systems, 29, 2016.
Chendi Qian, Didier Chételat, and Christopher Morris. Exploring the power of graph neural networks in solving linear optimization problems. In International Conference on Artificial Intelligence and Statistics, pp. 1432 1440. PMLR, 2024.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junshou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.
Andreas Roth. Simplifying the theory on over-smoothing, arXiv preprint arXiv:2407.11876, 2024.
Andreas Roth and Thomas Liebig. Rank collapse causes over-smoothing and over-correlation in graph neural networks. In Learning on Graphs Conference, pp. 35-1. PMLR, 2024.
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint arXin:2303. (al::333..19993 2023a.
T Konstantin Rusch, Benjamin Chamberlain, Michael W Mahoney, Michael M Bronstein, and Siddhartha Mishra. Gradient gating for deep multi-rate learning on graphs. In International Conference on Learning Representations, 2023b.
Mahalakshmi Sabanayagam, Pascal Esser, and Debarghya Ghoshdastidar. New insights into graph convolu- tional networks using neural tangent kernels. arXiv preprint orXiv:2110.04000 100000000 2021.
Mahalakshmi Sabanayagam, Pascal Esser, and Debarghya Ghoshdastidar. Representation power graph convolutions: Neural tangent kernel analysis. arXiv preprint arXiw:2100009800 2022.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In International Conference on Learning Represenatations, 2014.
Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep information propagation. In International Conference on Learning Representations, 2017.
Michael Scholkemper, Xinyi Wu, Ali Jadbabaie, and Michael Schaub. Residual connections and normalization provably prevent oversmoothing in gnns. arXic preprint NKK::2406002999 2024.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lisc Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI magazine, 29(3):93 93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1xXtv:1811.0586: 2018
Ahsan Shehzad, Feng Xia, Shagufta Abid, Ciyuan Peng. Shuo Yu, Dongyu Zhang, and Karin Verspoor. Graph transformers: A survey. arXie preprint 477:0:247..09777, 2024.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for largo-scale image recognition. International Conference on Learning Representations, 2015.
Jascha Sohl-Dickstein, Roman Novak, Samuel S Schoenholz, and Jaehoon Lee. On the infinite width limit of neural networks with standard parameterization. arXiv preprint 2rXiv=2001.07301, 2020.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov, Dropout: A simple way to prevent neural networks from overfitting. In Journal of Machine Learning Research, volume 15, pp. 1929-1958, 2014.
Matus Telgarsky. Representation benefits of deep feodforward networks. orXiv preprint 2015.
23

---

Published in Transactions on Machine Learning Research (06/2025)
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liö, and Yoshua Bengio. Graph attention networks. 2017.
Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. Bag of tricks for node classification with graph neural networks. arXiv preprint arXiv:2103. 139555 2021.
Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao. Graph Neural Networks: Foundations, Prontiers, and Applications. Springer Nature, 2022a.
Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodelormer: A scalable graph structure learning transformer for node classification. Advances in Newral Information Processing Systems, 35: 27387-27401, 2022b.
Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymplotic analysis of oversmoothing in graph neural networks. International Conference on Learning Representations, 2023.
Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing attention-basel graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprchensive survey graph neural networks. In IEEE Transactions on Neural Networks and Learning Systems, volume 32, pp. 4-24. IEFE, 2020.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel Schoenholz, and Jeffrey Pennington. Dynamical isometry and a mean field theory of CNNs: How to train 10,000-layer vanilla convolutional neural networks. In International Conference on Machine Learning, pp. 5393 5402. PMLR, 2018.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. Tn International Conference Machine Learning, pp. 5453 5462. PMLR, 2018.
Keyulu Xu, Mozhi Zhang, Stefanic Jegelka, and Kenji Kawaguchi. Optimization of graph neural networks: Implicit acceleration ion by skip connections and more depth. In International Conference on Machine Learning, pp. 11592-110000 11602. PMLR, 2021.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEFE International Conference on Dala Mining (ICDM). IEEE, 2022.
Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting over-smoothing in deep gens. arXiv preprint arXiv:200S. 13663, 2020.
Chenxiao Yang, Qitian Wu, Jiahua Wang, and Junchi Yan. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps. In International Conference on Learning Representations, 2023a.
Ge Yang and Samuel S Schoenholz. Mean field residual networks: On the edge of chaos. Advances in Neural Information Processing Systems, 30, 2017.
Guangrui Yang, Jianfei Li, Ming Li, Han Feng, and Ding-Xuan Zhou. Bridging smoothness and approximation: Theoretical insights into over-smoothing in graph neural networks. arXiv preprinl N07::2207.01281, 2024.
Rui Yang, Wenrui Dai, Chenglin Li, Junni Zou, and Hongkai Xiong. Tackling over-smoothing in graph convolational networks with em-based joint topology optimization and node classification. In IEEE Transactions on Signal and Information Processing over Networks, volune 9, pp. 123 139. IEEE, 2023b.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, pp. 40-48. PMLR, 2016.
24

---

Published in Transactions on Machine Learning Research (06/2025)
Hongwei Zhang, Tiji Yan, Zenjun Xie, Yuanqing Xia, and Yuan Zhang. Revisiting graph convolutional network on semi-supervised node classification from an optimization perspective. arXiv preprinl ar arXiv:2009.114 11469, 2020.
Wentao Zhang, Zeang Sheng, Ziqi Yin, Yuezihan Jiang, Yikuan Xia, Jun Gao, Zhi Yang, and Bin Cui. Model degradation hinders deep graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Dala Mining, pp. 2493 2503, 2022a.
Yifei Zhang, Hao Zhu, Ziqiao Meng, Piotr Koniusz, and Irwin King. Graph-adaptive rectified linear unit for graph neural networks. In Proceedings of the ACM web conference 2022, pp. 1331-1339, 2022b.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gmns. In International Conference on Learning Representations, 2020.
Lecheng Zheng, Dongqi Fu, and Jingrui He. Tackling oversmoothing of gnns with contrastive learning. 2021.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57- 81, 2020a.
Kaixiong Zhou, Xiao Huang, Yuening Li, Daochen Zha, Rui Chen, and Xia Hu. Towards deeper graph neural networks with differentiable group normalization. In Advances in Neural Information Processing Systems, volume 33, pp. 4917-4928, 2020b.
Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. In Advances in Neurol Information Processing Systems, volume 34, pp. 21834 21846, 2021a.
Kuangqi Zhou, Yanfei Dong, Kaixin Wang, Wee Sun Lee, Bryan Hooi, Huan Xu, and Jiashi Feng. Under- standing and resolving performance degradation in deep graph convolutional networks. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management, pp. 2728- 2737, 2021b.
Xianchen Zhou and Hongxia Wang. On the explainability of graph convolutional network with gen tangent. kernel. Neural Computation, 35(1):1 26, 2022.
Chen Zhu, Renkun Ni, Zheng Xu, Kezhi Kong, W Ronny Huang, and Tom Goldstein. Gradinit: Learning to initialize neural networks for stable and efficient training. Advances in Neural Information Processing Systems, 14:16410-16422, 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra, Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Informalion Processing Systems, 33:7793-7804 2020.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dep importance sampling for training deep and large graph convolutional networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
25

---

Published in Transactions on Machine Learning Research (06/2025)
Appendix
A Supplemental notation
For any integer n E N, we define [w] A (1,2....,,}} We may denote matrix E R by (e) where Tty the entry in the i-the row and the j-th column. We further use Xt,; E Rix and X E R=xl to denote the i-th row and the j-th column of X, respectively. || || denotes the Frobenius norm. Given any function f R=x= R, its derivative 0f/0X with respect to X R is the m matrix with (05/0X); = 0f(X)/Omp For any activation function output of applying a entry-wise to the matrix X, i.e., (o(X)) = (zig). We denote ReLU activation by (xLU(x)) & max(0, 2) and (anh aclivation by lanh(z) (e* e/-e + +e=)). For brevily, use 0 to denote the collection of all trainable parameters in a GCN model.
IR + R, we use o(X) IR=x to denote the
For any matrix X = (z)n)) E Rmxx, the vectorizaion of X defined by
() = (x11, Tmll T12, Zm
Lmn T E Rmax
For any matrix == (zx)) E Rmxx and Y = (vis) E RPx9, the Kronecker product of X and Y is mp nq block matrix defined by
EnY
Tin
x =
Fm Y
Tmn Y
For matrix X (xir) E RM if maj for all E [m]] and j [n],, we denote X = 0mxni if maj 1 for all E [m]] and j E [n]], we denote X = Imxx. For vector Z (z+) E R" if = 0 for all i E [n], denote
Z = 0,; if 2; = for all i E [n], we denote Z = 1.
26

---

Published in Transactions on Machine Learning Research (06/2025)
B Convolutional kernel
Suppose that graph G has M connected components. The m-th component is a subgraph denoted by fm = (Ver Em) for m E [M]. We present a well-known result characterizing the eigenvalues and the eigenvectors of Å without giving proof, see, e.g., Proposition in Oono & Suzuki (2019).
Proposition B.l. Suppose that G = (V,E) has M connected components {9m- (Vm, Em Em) and the
2..... eigenvalues of are x 2 X2 ... An. Then we have
x =1, for any sis M.
EE(--, for any M + sisn.
Moreover, the set {vlm) = D4 m E [M]] is basis of the m-dimensional eigenspace of Å corresponding to the eigenvalue 1, where w!m) = (1(ve..))) E RRux1 is the indicator vector of the m-th connected component 9m.
Lemma B.2. Given any H E g and H + OnxC, we have 0 S Dir(H)/ 2.
Proof. Recall that i = I - Å is the normalized Laplacian of graph g. By Proposition B.1 all the eigenvalues of L belong to 20.
Given any H E _2x we have
Dir(H) = tr(H' LH
Σ
H LH
Σ
2. H H = 2
R=1
k=1
Similarly, we have
Dir = tr L.H
Σ
H
H. 2
0 H. H.
1=1
1=1
Thercfore, we conclude that
0 s Dir (H) (Hi( 22
27

---

Published in Transactions on Machine Learning Research (06/2025)
C Signal propagation theory for vanilla GCN
C.1 NNGP correspondence for vanilla GCN
Proposition C.1 (NNGP correspondence for vanilla GCN). As the network widths d1, da.....,dd se- quentially go to infinity, the 1-th layer's pre-activation embedding channels {H hejd) converge to i.i.d. (H()ke
n-dimensional Gaussian rondom variables 2O,, ) in distribution for any 2 2. The covariance matrices
are
( = o² AxxTA
do
(3)
g(+1) = = )
where G(E) = 20) for any n x n. posilive semi-definile malrix
Proof of Proposition C.1 We will prove that ( ke(d]] are asymptotically i.i.d. n-dimensional random variables with mean and covariance matrix E00 for any 2 1 under the infinite width limit by mathematical induction. Proposition C.1 which contains a stronger claim that (H are asymptotically Gaussian for any 2 2, will be shown during the induction steps.
Base case. Since the bias terms are initialized to be zero, when l= = 1, the k-th channel of the embedding is
H Axw(1)) 1,, bb (
Since (W: ] are i..d. random variables, {H keldd are also iid. random variables. Taking the expectation of we get
E = Åx -EW
;s On-
Calculating the covariance matrix of (4), we have
Cov
H! = !
= XT
= Ax -ww.D x"A = Åx.
Ido X
do
- A.
do
Thus, if we define E() o..AXXT A/do. then {H (1) heja) exactly i.i.d with mean O,, and covariance matrix y1))
Induction step. Suppose that ( heead converge to i.id. n-dimensional random variables with mean O,, and covariance matrix Σ() in distribution d1,...,d-- d soquentially go to infinity, we look at the (1 + 1)-th layer. Recall from the formation of the 1-th layer in vanilla GCN, we have
H(+1) = (0(1)((+1)) + 1n b(+1) x =HH())
for any 12 1. We vectorize the first equation and get
(1)(H((+1)) veo vec (2) w(++)) + veo(1n b(++1)
de
(5)
[Ax!!)] w(((+)
vec
ax1
1xd++1
because B(++1 is initialized to be Od Suppose that ((++) = oZAAG(E))A we are going to show that vee (1+1) converges to Gaussian random variable ((0nd Taip E(+1)) in distribution
28

---

Published in Transactions on Machine Learning Research (06/2025)
d1, (i,dd,.... d..........1111. 1,- di sequentially go to infinity. If this claim holds, (H are not only asymptotically i.i.d., but also asymptotically Gaussian i..d. with 2.,, I((t)),, which corresponds to the statement of this proposition.
For brevity, we define
11+1) Wkk'
/d w Wkk
for all le [d]] and I' E [d++1].
and
z = vec (IAx!)) w for all & [di].
(6)
(1+1) Then we get that (wkk?" Melde) are i.id. from N(0, ) and
d
RHS of (5)
(+1)
(7)
dd k=
k
By the induction hypothesis, d1, d2. ..... d-1 sequentially go to infinity, (X {H heeldi converge to i.id. n-dimensional random vectors in distribution. Because X()) can be regarded as a function of {w(')// at initialization, we get that (() and ((++1) are independent. Thus, as d1, d2.d....., di-1 sequentially go to infinity, ( "ee[( converge to i..d. random vectors in distribution. Moreover, in this limiting case, by taking the expectation of (6), we have
Biz vec ([AE(x BlW vec (0nx1 01xd:11) Ond411
Calculating the covariance matrix of
6 we have
Covlz
z
1)
E
z [(+1T
vec (IAx!!) -..:
w.t 1) vec (IAX!9) - "
E
E
[woftt
Ax (w & x(!TAA) A)]
wi (1+1) ((+1)
x A]
E
E
wi:
(41) (1+1)
A E
x (1) X x A}
o Ia AG(EO))
Iamn 8 o (G (1) ) Id 3 [(41)
Here x(O) actually stands for the limit of true x as di d sequentially go infinity without bringing any confusion.
By multivariate central limit theorem, 1 DR z (1+1) converges to Gaussian random variable ((Ond) :: Ia & g(+1) in distribution converges to a Gaussian random variable (O Idii & y(+1)) as di,...,dt sequentially go to infinity.
ao. Recalling 5 and (7) we conclude that veo( vec(H(+1)
Conclusion. By the principle of mathematical induction, we have proven this proposition.
C.2 Some discussion w.r.t. G
We claim that the function G' is well-defined in Proposition matrices
C.1 on the collection of positive semi-definite
S= EE
Runn o En 2 0 for all x E R
(8)
29

---

Published in Transactions on Machine Learning Research (06/2025)
Remark C.2. To show that G(E) (0) is well-defined at any Σ S, only need to show that such E is always a feasible covariance matrix of Gaussian distribution. For any Σ E S, there exists P E _Rxx, such that PpT = >. Let & ~~ (0,, 4n) be an n-dimensional standard normal random variable, then the random variable NOO, Σ). Thus, all positive semi-definite matrices are feasible covariance matrices for Gaussian distributions.
Definition C.3. Given any positive semi-definite matrix Σ E S, we define
:- q=
(9)
where (< E IRx1 is defined by
((n); = G( for all i [n]. Lemma C.4. Given any positive semi-definite matriz E E S, holds that
(10)
Gi(Z)b 2 G(E), for any i,j E |m]].
(11)
Proof. Recalling the formation of function G in Proposition C.1 (NNGP correspondence for vanilla GCN),
for any i,j E [n], we have
G(E); (O.. obh)))
Recalling and
10 in Definition
C.3
we get
Gi (E) (E), (E); - VG(E) V
(12)
= - my (h;))? EN
From Hölder's inequality Hardy et al.
1952
we get
RHS of 12
> Bn (lo(h)) o(hy)]
EA-NYO,,,,) (o(h;) o(h,)] G(E)
Lemma C.5. Given the NNGP covoriance matrices (-00 Mi=1 defined by 3 it holds that
tr("++1) s a ()(G()))).
Proof. Recalling the NNGP correspondence formula for vanilla GCN
3
Proposition
we have
)r(=(t)))= = =oo((" = at tr (r(AG(E))A))
(13)
Since all entries of Å are non-negative, by Lemma C.4 we have
(AG(I.)) < (Z(") A)), for any E [m].
Taking the summation of w.r.l E [n], we get
tr(AG(E()) s (
(14)
Recalling the definition of function G1 in 9 we get
tr( (r(A = tr( (y(5))))))))))) = =||
(15)
By Proposition B.1 all the eigenvalues of belong to (-1, Recalling the definition of function in
(10
we get
Ag( < 11 = ()
(16)
Finally, combining
13
14
15
and
16
we complete the proof.
7
30

---

Published in Transactions on Machine Learning Research (06/2025)
C.3 Proof of Theorem 3.1 (Signal propagation ReLU-like- activated vanilla GCN)
ReLU-likeacttivated
To facilitate reading and understanding, restate Theorem 3.1
here.
Theorem 3.1. Under the NNGP correspondence opprozimation, when the activation function o RELU, we have
1. o 2, either the limit graph embedding variation (GEV) metric limy->o0 M (Ev( = 0 or the limit
forward signal propagation (FSP) metric lim M (L) (o 0;
2. When th < 2, the forward signal propegation (FSP) metric M (L) (op < 2C (2) for any L 2 1.
We now provide more general signal propagation analysis vanilla GCN with ReLU-like activation. Definition C.6 (ReLU-like activation). An activation function a R - R is (a, 8)-ReU if it has the form
ox, 220, 0,
((x)
(17)
[x, x<0, 0,
where 3 E R_ and not both of them are 0. We also call such a a ReI.U-like activation function.
Next, prove Theorem 3.1
we generalize our analysis from the standard ReLU activation the more Since (a, 0) recovers the standard ReLU, proving
general (a, RU activation in Definition C.6
the following Theorem C.7 implies Theorem 3.1
Theorem C.7 (The generalized version of Theorem 3.1. Under the NNGP correspondence approzimation, when the activation function a is (a, RULLU in Definition C.O. we have
1. When ot = 2/(a² + 88), either the graph. embeeddnng variation metric
lim ( lim En-NO,, [Dir(H)/|]H +00
L+000
the forward propogation metric
lim M (O) lim EH- x4))
[|| H X 0.
L-000
2. When oi <//(a² + 88), for any L 2 1, the forward propagation metric satisfies
M M EH s0y || (a² + dd
2C
o (a² + +B3)
L
Lemma C.8. For any x E R", holds that.
Dir(Ar) >DDrr()),
(18)
where X is the second largest absolute eigenvalue of Å, i.e.,
A = max
[A/-- A
Proof. Since Å is symmetric real matrix, by Proposition B.1 it can be decomposed À = UAUT, where A = diag(Ai, ,e...., An) and U E Raxn is an orthogonal matrix. The i-th column w; of U is the eigenvector corresponding to Ag.
By Proposition
B.1 we have d E (-1, for all E [n]. Since - I A, we conclude that
Dir(Ax)= = (Ax)" L.A = xT = (UAU~))(U((T
a
1
=IAA(I A]A² Σ (1- A,) < X2 Σ (1 x)
=x - A)= D²Dir(x).
31

---

Published in Transactions on Machine Learning Research (06/2025)
Lemma C.9. When the activation function is (), it holds that
(a(x)
+ (a(-x) al v)) (a² (x y)²
(19)
for any v, y E I. Moreover, the inequality becomes on equality if and only if xy 0.
Proof. When z, y 2 0, it holds that
LHS of 19 = (ax az)² + (-Bx + By)² RHS of 19
Similarly, the equality holds when 2, S 0. When ty < 0
LHS of 19 = (ax - By)² + (-3x + azy)
= (a² + {x² ² + 5²) 4aBry
(a? + (²) y)² 2(a - 3)²
< RHS of 19
Lemma C.10. When the activation function is (a, BR-LL, holds that Dir(a(h)) Dir(a(-h)) s (a² Dir(()). Since the activation function a (a, 3)-ReLU, we have
(20)
Proof.
= =or)= for any c E 14,, E R.
Then we get
2
2
(14)
o(hy)
o hi)
((-hg)
LHS of (20
+
+I+d;
V1 dj
VI + di
V1
(WJ)EE
li VI+ + di
(
hj
2
VI (v-ti
-hi h4
-hi
2
(vI+
(VI+ d
+
a
di
-
dj
(1,))
By Lemma C.9
we have
h4
hj
LHS of 20
< (a² + +22
RHSSS of (20).
V1+di
/1 + dj
Lemma C.11. When the activation function is RRLLU, for any feasible covariance matriz Σ E R it holds that
(x < a² + 32
2 (ir()))))
Proof. By symmetry, for any n-dimensional random variable h N(O,, 2), holds that -h N( 2.). By have
Lemma C.10
(D)( (Bnnwoo.,,(Dir(((())) = (() Dir(((())
(a² + (222+88)EBnaaa (O) (irr(A))
32

---

Published in Transactions on Machine Learning Research (06/2025)
Lemma C.12. Under the NNGP correspondence approcimation, suppose that the activation function is (a, B)-ReLU in Definition C.6 IJ
2 d >²( + 82)
then we have
((Ao2((22
(a2 + (9)) +))))))
(0.. (Di(h)) =0
as 1 - 00,
2
where X is the second largest non-one absolule eigenvalue of Å, i.e.,
A max |2g/- A
Proof. For any positive semi-definite matrix S and any n-dimensional Gaussian random variable h ~ NO,,, Σ), have
M; EA,.( tr(h" Lh)] Fo. tr(iE).
Then according the NNGP correspondence formula
33) in Proposition C.1 for any E N, we have
E 2x1,) tr tr((2x((11)
= (r(LAG(2)0)) A) of tr (LA 2w))))))..))))hh))())))))))))
(21)
tr (A) a)]
o E [tr (o(())(AAAo())) AL)o
Ep x00)
No Dir (Ao(t)))
By Lemma C.8 and Lemma C.11 get
2 +
RHS of 21
X² o B(, Dir(o(h))] <
E ((.. Exy [Dir(h)]. (i)(
(22)
2
Thus, combining
21 and 22 by induction, have
N mo) Dir(h)] ((A(00/(00
-
Proof of Theorem C.7 (the generalized version of Theorem 3.1 First of all, we will prove part 2 of this
theorem. For any positive semi-defnite matrix Σ E S, we have
EA, [| EA-N(O. hh) Ey tr(E).
[1|
For this reason, we only need to focus on (Ir(E()) )e in the following proof.
We will show that (tr(2()))² is a decreasing sequence if ow s 2/(2² + 32). By Lemma
C.5
we have
tr(I(-1)) < of (r(())())).
(23)
When the activation function is ReL,,, for any e R2,, holds that
E E2-wvonnlo(22)]
= 2 1 + E2-No., (1 (2500]
a² 2 g2
Ez Ez. 2 z?1.
2
33

---

Published in Transactions on Machine Learning Research (06/2025)
Accordingly, for any positive semi-definite matrix E E S and i E [n], we have
G(E) 5) B2-N(0.1)
(24)
a² + g²
|EN a² +
2 BZ=N((.1)
Ezi.
Combining 23 and 24
we get
(a +32)
tr tr(2)(++)) <
tr tr())
Thus, we have shown that [ is a decreasing sequence if ow S 2/(a2 + B²). In addition, if ow < 2/(a² + )²) we get
o + 88)
tr(2(())) v
tr(2
(25)
By Proposition C.1
we have
o (r(E())) Ir (r(AXXTA)
ou do do
o do
Ir Ar(AX
|| 112
(26)
do
do
Since all the eigenvalues of Å belong to (-1, 1] by Propositon B.1
we get
do
of x 2--
RHS of 26
tr(Xx7).
(27)
do R=
do
Combining 25
26
and 27
have
02 (a (o
tr(I(4))
tr(XX²).
dg
2
Thus, the forward propagation metric at the L-th layer satisfies
C
C
(H,N(O,, XXI)
tx(XX) (r(E(1)
|
tx(XXT)
Co
[o + 82)
1-1
do
2
2C
2 (a² B2)
(a²
32
2
Then have completed part of this theorem.
If ReLU activation function, i.e., (1,0)-ReLU. If
< 2
P40
2
have
2C
0
(12 + 20
4
o L 2
EH~N(O., XXE)
X
(12 + 02)do
2
=
do
,
which coincides with part 2 in Theorem 3.1
Next, we will prove part 1 this theorem. Let's study the case when o = 2/(a2² + -2). Suppose that
lim tr(E(0) = 6g.
1000
If & 0, then we have completed the first part of this theorem by getting
lim 5:00 | = Loc
lim
|
lim tr(x(4))= =0. 0.
X H
34

---

Published in Transactions on Machine Learning Research (06/2025)
Now we study the case when dg > 0. In order to show part of the theorem, we only need to demonstrate that
Dir(H) H
lim BH~N(O..EE1))
400
| F
Given any fixed 0, we have
Dir(H)
|
(28)
Dir(H)
Hir(H)
RH=NO, E01)
11 (1
+ +.
1 (HAlles |
|
From Lemma B.2 it holds that Dir(H)/ 2, so gel
1
RHS of 28
v [H,,NO,.. Dir ( (110 + 2- PI,N 200) || e
(29)
< 2
(H=N(O.. [Dir(H) + 10.-H~NiOO... P=~N(O..EUM)
H| S <|.
For any L 2 1, there exists E [n], such that ( 2 tr(E(1)/nn Then for any n x C random matrix
NO,,, E(D)), we have H ~ ((, ). For this reason, we have
P PH~N(O, || < e) < HH~N 200) |1 S [ = Fz-N(O.)
|2| EEn
PZ)N(0.1)
1 V tr(E(T)
n
(30)
2 (c. c
tr(E(4))
- 1,
where ((x) Pz~No.nlZ < æ] denotes the cumulative distribution function of the standard normal
distribution 1).
Combining
28
29
and 30
we get
Dir(H)
Eu,, [Di((H) +40 (e. (e.v tr(x)()) -2,
E EH~NIO. E0D)
for any L > 1.
Since
2
2 x² - B2)
0
a² +
32
by Lemma C.12 we have
lim E E(. Dir(H)) = 0.
1-000
We let L in
28
and get
Dir(H)
lim sumsup E E(..... b-x
|
lim sup E EH~N(O,, [H) + lim sup + (c.
<
(
tr(E(11))
(31)
2 L+x
L
71
nt
2
0 + 4Φ
6.
50
2 = 4Φ
6.
V
50
2.
35

---

Published in Transactions on Machine Learning Research (06/2025)
Notice that the left hand side of 31 is independent of the choice of e. Since &b is continuous map, let 0 and get
Dir(H)
lim sup E (O.,
I 4 0.
|
Therefore, we have
Dir(H)
lim EH~NOO,, 400
|
C.4 Proof of Theorem 3.2 (Signal propagation ReLU-activated vanilla GCN)
To facilitate reading and understanding, we restate Theorem 3.2 herc.
Theorem 3.2. Under the NNGP correspondence approzimation, when the activation is ReLU, the graph embedding variation (GEV) metric M is independent of o
GBV
Similar to Appendix C.3 prove Theorem 3.2.
we generalize our analysis from the standard ReLU activation
the more general (a, R)-LLU activation in Definition C.6 Since (a, (1, recovers the standard
ReLU, proving the following Theorem C.13 implics Theorem 3.2
Theorem C.13 (The generalized version of Theorem 3.2 Under the NNGP correspondence ap-
prorimation, when the activation is (0.3)-Red 3). the graph embedding variation metric ( PH~NO, Eun (Dir(H)/] H|[]] is independent of the choice of oz
Proof of Theorem C. (the generalized version of Theorem 3.2 Under the NNGP correspondence approx- imation, only need to prove that
0 (o
(0
for any 12 and o o
(32)
Tf 32 holds, then H ~ NOO,, (o implies // ~ N(O,, (F.) In this way, we have
Dir(H)
|| H/
E (0.
|
Dir(H)
=EH~NO.. (18)))
||
Now we prove
32 by mathematical induction. When / 1, by Proposition C.1 we have
(
1 A o2 du
(a)
for any on o >
82
holds for L, we look at the case for + Since the activation o is (a, R)-ReLU, for any e R., we have (cx) = (x)). Recalling the definition of G Proposition C.1 for any positive semi-definite matrix E E S, we have
If 32
G(c2E)); = En.Noo,, (h;)) Rn-.no,, (chh))
= (2EA-NNO, (h₂)) = e)G(E),,)
36

---

Published in Transactions on Machine Learning Research (06/2025)
for any i,j E [n] and R_. Thus, by Proposition C.1
have
L+1
L-1
0
(
0 0
LgG
(10) A (x)))) A
0
L
02
AG
AG (21)
c (o))
where (a) and (c) are due Proposition C.1 and (b) are from the induction hypothesis.
Therefore,
32 holds for all L 2 1 and we have completed the proof.
C.5
Signal propagation on tanh-activated vanilla GCN
Theorem C.14. Under the NNGP correspondence approzimation, when the activation function a is tanh,
have
When o 1, we have lim M = lim Soo, = 0.
2. When o < 1, we have M (o = EH~N(O. | S do
26 for any L 2 1.
Lemma C.15. The collection of positive semi-definite matrices defined by
S closed subset of Rox
Proof. We only need to show that given any convergent sequence J0e C S, its limit also belongs to S. Suppose that
lim Q(+) = Q" E-00
Since all (Q()) are positive semi-definite matrices, so given any x E R we have
x. ( x 2 0, for all E.N.
Then we gel.
x x²Q'x lim x ((()) 0. h0000
Thus, Q" also belongs S.
Lemma C.16. When the activation function is tanh, i.e., o(x) = (e" -e"- te then we have (axx) < |o| for any x E RR Moreover, the equality holds if and only if x = 0.
Proof. It casy to verify that (00) O. Given any x
2 0, we have
d(-x)= E- _ 6" --=
4 x- + -z())
For this reason, we only need prove that [a(x)) < |x| for any x > In the following part, we will show that (xx) when 0.
37

---

Published in Transactions on Machine Learning Research (06/2025)
We define f(z) (z)) for any x 2 0. Let's consider the derivative of f:
d ee x
f((x)
dr e² + c = x8
d (c" - (c" -0 d
- (c =6=+
(0 + =)
e + ===
dr
dx
(e" te
(e" 2)
(e t
-(e" a0-
(et te-
Then if x: > O, we have (x) < 0; if 0, we have f'(x) 0. Thus, f(x) =x(x) - x is a strictly decreasing
function in [0, +oo). Since f(0) = (0)) 0 = 0, we have
f(z) (x) < 0, for any x > 0.
Since 0 < - ex t x for any x > 0, holds that
a = (e" e "(("" + +e b=))> >0 for any x > 0.
Therefore, we get that 0 < axx) < for any 0 and have completed the proof of this lemma.
Now it time for Theorem
Proof of Theorem C.14 First of all, we will prove part 2 of this theorem. For any positive semi-definite
matrix E S, we have
ER
||] Ea. h)] st) = tr
For this reason, we only need to focus on (tr(E()))e in the following proof.
We will show that { is a decreasing sequence if aw 1. By Lemma C.5 we have
tr(E(-1)) S oz, (T())
(33)
By Lemma C.16 we have [a(x)] S |x|| for any x E R. Moreover, the equality holds if and only x = this reason, given any positive semi-definite matrix E E S, we have
For
n B (0..0000.))000())))))) Ez-N(o.) [o(VEn2)2]
tr(G(E))
(34)
[VEn))]]] En. = tr(E),
<
Ez~N(o.) 1=1
and the inequality becomes an equality and only if VEn = holds P-as. for all i E [n]. Since 2 ~ N(0, follows a standard normal distribution, it is equivalent to D3 = 0 for i E [n], i.e, tr(2) 0.
Combining 33 and 34 we get
tr(y of 20ttr(1' t))
Thus, we have shown that (1r(S()) decrcasing sequence aw $ In addition, if ow < we get
(r()(4))) o 2(L-1) tr())()).
(35)
38

---

Published in Transactions on Machine Learning Research (06/2025)
Analogous to the proof of part 2 in Theorem C.7 for ReLU-activated model, by Proposition C.1 and Proposition we have
B.1
ou A) = x
da
tr(E())= = tr(Axx"
do
du
k=1
(36)
aºe da
0
o du
IAX.
A 11
|
k
11
I
dg
do
do
k=1
Combining 135
and
33
we have
(r(
d
X Fp
do
Then we have completed part of the theorem by getting
|
C
|
=
|
E E N
|
tr(E(4))
C
C
|
o
X
do
dg
Next, we will prove part 1 of this theorem. Let's study the case when ow 1.
Since ()) is a positive semi- definief matrix for any E N, we have 2 < x
b < (r() < tr(E())), for all i,j E [n].
Taking the summation of both sides w.r.t. i and j, we get
10 = Σ 1 S n² 1r(50)022 < oc.
1
Thus, the matrix sequence {
| lies in S' S'=Sn
||]| S {ntr(E
By Lemma C.15 S' is bounded and closed subset, ie., compact subset, of R By the Bolzano Weierstrassss theorem, there exists a subsequence (2(())
Ja= of (20)) and D S' such that lim = Σ*
Recalling 33 and that (tr( is a decrcasing sequence, we have (r(Duen)) S tr(5(++)) s tr(G(E())).
Since is a continuous function, we let + xo and get
ur(E*) lim (r(E((11)) x lim tr(G(E)))) =r("))())))))(()))))))) tr(G(t))) k
k000
According 34 we have
(G((E))) = tr(E
This implics tr(E)) 0 by 34..
Then, since (r()))) is decreasing sequence, we have
lim ||11
= lim tr(E()) lim tr(2(()) tr(E") 0.
Consoquently, we have
|
C
lim EH~N(O..EE0.) 1
lim Sxoy 0.
X
10000
E
39

---

Published in Transactions on Machine Learning Research (06/2025)
D Signal propagation theory for linear ResGCN
D.1 NNGP correspondence for linear ResGCN
Proposition D.1 (NNGP correspondence for linear ResGCN). As the width of the hidden layers + oc, the 1-th layer's pre-octivation embedding channels (eedd converge to ii.d Gaussian random variables N (O,,, 50) in distribution. The coveriance matrices are
-(1) 0 Axx*A. A, dg -(11) = a²o = AΣ À 335
(37)
Moreover, as + s0, the 1-th layer's post-activation embedding channels ( converge i.i.d. random variables in distribution. The random variables have mean O,, and their covariance matrices o(t), which salisfy
(0) T Xx",
do
(38)
(1) a² (((1-1) A
(1-11-1).
Proof of Proposilion D.1 For $(1) 50+1) defined by 388 and 37
easy show that E(+1) o (.((0)))) A.
Similar to the proof of Proposition C.1 We will prove this proposition by mathematical induction.
Base case. When I = 0, the k-th channel of (0) is
X (0)
XW + 1, 1/ XW
(39)
According to our initialization, the weights (w(()) helld are i.idd random variables, so (x hRE(d] are also i..dd random variables. Taking the expectation of (39) we get
E E
X
1 (0)
5,k On-
Calculating the covariance matrix of
33
have
Cov (x
E (0)
= ;6
X E
W: X = X
Ido
x
do
0² X
do
Thus, if let (00)_ xxxX then we have { (0) keel are ii.d. with mean O,, and covariance matrix (()).
Now we study the pro-activation embedding H(I), Since the bias term (() is initialized to be Oa, we have (I) (0) (1)) + 1,, (()) ((1)(
Similar to the proof of Proposition C.1 for vanilla GCN, we vectorize the equation and get
(1)(H(1)) Σ vec
[Ax:
(:(1) (1)
k.:
nxl
1xd
For brevity, we define
(1) Wkkk
Vd. ((1))
for all Ar. k' E [d]
40

---

Published in Transactions on Machine Learning Research (06/2025)
and
2/2 = vee vex((xx:)) -.k; ") for all & E [d]-
Then we get that ba are iid. with mean and variance ow and
1
vec(H
vd k=
R
Analogous to the proof of Proposition
C.1
hEELd are i..d., E[zi") Ond, and
Covl2 (1) =E
(ayr (1)
{A- x x
A
wi: wi.
= o @ (T(0)) Å
Ia 8 o ( A.
Since +(1) = A/XXT/// = o (0(00 Gaussian random variable N(Ondd, Ta 69 5() d x.. Consequently, (H converge to i.id Gaussian random variables N(O., (()) in distribution.
A, applying the contral limit theorem, voc(H(") converges to a
Induction step. Suppose that (x(t=)) converge to i.id. random variables with mean O,, and covariance matrix s(1-1) in distribution. Suppose that (H converge to i.id. Gaussian random variables NO,,, 50 in distribution. Now we look at X first.
For the linear ResGCN at initialization, the post-activation embeddings satisfy
x = =HH + +xx(111) = -A + (1x11
We take any k-th channel ( of x():
x1 all! + 3x
-Ax Bx(+-")
= (x( + (xx(-1
Ax 1) (1) wkrk) + =xx
where (1)
wirk : (()) W /vd has mean and variance o2 which does not rely on d. By the induction hypothesis, ((I-1) and x
w Vd /V w///v/ and 3x (1-1) in (i) when k' + k. We notice that the correlation between (i)'s k-th term a'x:!l-")(l wkk/
(1-1) are independent when k' k. Then (ii) is independent of the k'thh term aix((1-1 (
goes to 0 as d + co. Thus, get that (i) and (ii) are asymptotically independent, the expectation
B[x![]] = aE a. H + 3E[x = =0,,
and the covariance matrix
Cov[x!!] = a²C (1 + Cov[xx a²5i1) + (1-1
=a'oz ( Å (1-1)
(1)
41

---

Published in Transactions on Machine Learning Research (06/2025)
By the induction hypothesis, (H are i.i.d and { Next, we look at the pre-activation embedding H(++), We have
(x are i..d as - oo, so (x:2) i.d.
= =x-=)xxx+000 AAx: +1, +1.-b0t) = A((-))
We also vectorize it and get
veo (H(HH1))
vee voe ((xx w
Analogous the proof of base case (or the proof of Proposition C.1,, we can conclude that (H(()) converge i.i.d. to (On,, oe Ag(()) A), i.e. ((0,, {(+1)).
Conclusion. By the principle of mathematical induction, have proven this proposition.
D.2 Proof of Theorem 3.3 (signal propagation on linear ResGCN)
To facilitate reading and understanding, we restate Theorem 3.3 here.
Theorem 3.3. Suppose that there erists an eigenvector of Å corresponding the eigenvalue 1, such that the inpul feature X Raxdo salisfies X o 0dox1- Under the NNGP correspondence approzimation, for linar ResGCN, if a²ou + 32 > and + O, then have
lim M (o oo and lim ( = 0.
10000
L
Proof of part 1 in Theorem 3.3 For any positive semi-defiitte matrix E S. we have
ER~NO,
[|]|||]]
Etr = En--wr,,,,)(rr(hhh = tr(E).
Recalling the NNGP correspondence formula for linear ResGCN 37 in Proposition
D.1
we have
0 Te AAx" A, Σ
do
(40)
(0+1) = az A A 32500
By Proposition B.1, we can assume that A U where A diag(A1 (A....., Ap) with A1 ... and U IR is an orthogonal matrix, i..,, UTT -UTU In-- Then from 40)
-11
get
+T = o. UT A AU + A a AUT SUTSUAA 32 UUU
(41)
So for any i e [n] and / e N, have
(U' (0+50+00): = 2² -10 (
= 2a22200 + 8) (UT (1)50)).
Thus, for any E [n] and I E N, we have
(UTELUN) (a22202 (0>)) 3- ( (UTT..
According to the assumption on input feature X, there exists an eigenvector u of Å corresponding to the eigenvalue 1, such that XTu u + 0 Suppose that u1, U2...., E BR are the columns of U, then there exists E [n] such that XT u, + O. Otherwise, suppose that u Σx Cjt and X" = 0 for any j E [n], XT,uu,
then XT u Σj= C uy O. Contradiction!
42

---

Published in Transactions on Machine Learning Research (06/2025)
Without loss of generality, suppose that Au u1 and X"us + 0dxx1.
Then we have
(UTEWU)) = Te uf AfXX"" Au = ohe
u Xxx" 21 = oee
1|
||-uu|ll un 11ll2>> 0.
do
do
do
It results in
ott do
tr(S(4)) -rr() {) t)( 2 (0' (a"o + 83)
x u1 x2ulll
(42)
Therefore, if a + 3² >>,, 1, we have
lim M (o²) (o²)= = lim (0. 1/ ||
L-000
C
lim E E NO. [|]]||]
| 1-00
lim tr(E(t) +00. L-000
= |X
Proof of port 2 in Theorem 3.3 For any positive semi-definite matrix E E S, we have
E m Dir h)] = E (r f.)]
(A)) = 1))
= tr(āz).
So when we want to study E, N(O.. Dir (h)], we only need to look at tr(iE) in the following of the proof.
Since AL A(In- A) Å A (In A)Å LA, we multiply L on both sides of the second equation in 40 and get
LS = = 2. LASS)A A 82L500
= = ALE LL
Then for any i E [n] and 1 E N, we have
(UTLE(+ = =0,aa² U) +8 (UTLEUU)
= =fa2X²0 + 82) (U L.MUM.
Thus, for any e [n] and L E N, we have
(U"LE(U) = 8 (U L
(43)
Since UTLU=UT(,, AyU I, A, get
UTISOU = (In - AJU
We denote
r. (U-)))))) for any i i [m].
Then by
we have
(UTLE(UU) (a'o 1-)--1. .(1 (1- A,)ris
From Proposition
B.1
we have
1) + 82)2 (1-1)m, if i (U (TTTSLU) 0 (a²o2x² + 82/ -Adrr if
where À = max [Ael [0, 1). Thus, we get
tr(t((4)) = (5(4)) < + Σ (1 X,)r
43

---

Published in Transactions on Machine Learning Research (06/2025)
We conclude that
E Sw) C .. N1., S40)
[Di((h)] 51y C. tr((
Cla + 82)4-1 Σ (1 Xe)ri-
Then we have
E ECC E(e) (ir(H(()))
[ $2 1-1
C < (--A))))))
(a2o + 12)
a²0² 32
Since a + 8 > and + 0 assumed in the statement of this theorem, we have 5²) [0, 1). So we get that
/3) +
E B (0,. Dir(H()))
lim 10000
(aPo2 + B = 0.
(44)
Recalling 42 in the proof of part for Theorem 3.3 if we define
x 1 and K= +B2
do
then given any L N, we have
KL-I tr()(4) 2 60 > 0.
(45)
Similar to the proof of part 2 in Theorem C.7 have
Dir(H)
(H,N(O.
|
Dir(H)
Dir(H)
<B S00))
111e1 B Beckt-1)
E (H S00)
11 ui (
(46)
|
|
E EH~N(O, S(L))
[Dr((H))
+ P 510) I "k
eKL-1
For any 2 1, there exists [n], such that E tr(i())/nn For any n C random matrix H NO,,, ((1),, it holds that Ha, ~ N(0, ((L)). By 450, we have
(L)
P PH~N(O. k0,)
H & ck Ck--I
S P
PHNNO.
[H S ck2-11
cKL-1
<PZNN(..) z² 2 cnkL-17
Pz-N(0.))
z 2²5 < (())
tr(((())
(47)
enn
S Pz~N(0.1)
2 < 80 (v
2Φ
by
where ((x) Pz~No.ulZ < ø] denotes the cumulative distribution function of the standard normal
distribution (0.
Combining 16
and
47
we get
Dir(H)
(, en
E NH,, 800)
|
<
EKL-I 50r (ir((H) 44
(v 0o
2.
44

---

Published in Transactions on Machine Learning Research (06/2025)
By 44
let L + and get
Dir(H)
limsup BO,,
|
lim E 500,, 5:),))))) + 44
2
(48)
KK
KKL1
1.-300
V 6o
(V
44h
=4
(v
60
60
Notice that the left hand side of 48 is independent of the choice of e, Since a continuous map, we let 0 and get
Dir(H)
sup E (o.,
I 4 - 2 = 0.
|
L-000
Therefore, we have
Dir(H)
lim (o
lim E S00)
O.
L-00
L+00
|
45

---

Published in Transactions on Machine Learning Research (06/2025)
E
SPoGInit algorithm
In Section 4 SPoGInit aims to find better initialization by minimizing
W0 VSP + W2 BEP Wg wy (L) GEV
In the implementation of SPoGInit algorithm, we always use one random weight sample to get point estimates V VesP, VESP, M of VESP, VESP, M respectively. We take deep vanilla GCNs example to showcase the SPoGInit methodology. Given any Kavier-initiallin weight {W(0) J1=1 SPoGInit scales the weights layer-wise
by 7 (e()) E R yield new initialization 0()) = (WO)] M==1 (/(W0) that achieves proper
signal propagation. To be more specific, SPoGInit algorithm solves the optimization problem
min F(O(7)) == wi Visp(7) + wy VISP(1) - wyMe (n),
(49)
where
2
:- (M M (L-1)
MMPP - 1)
(0
2
:- (M
(2) BSP
M (L-1) - 1)2
ESP
(
(ir(H(L)((()))
M
(L) GEV
(0())
with (0(+)) == ae/aww
E.1 Implementation details
Now we explain SPoGInit (Algorithm 1 in detail.
In lines 2-3, we initialize the weight parameters and weight scales (0) 1. We iteratively update 0(>) follows.
In line 5, we calculate the objective function F(O()(t))) as defined in 49
In lines 6-10, we update the weight parameters (()(t)) by optimizing the objective function through the projected gradient descent method to the scales {- (1))+z for each layer. We adopt the projected gradient
descent method to ensure the scales (t)) remain positive.
Algorithm SPoGInit: Searching for weight initialization with better Signal Propagation Graph
normalized adjacency matrix Å, input X(),, label y()), network depth L, hidden dimension d, learning rate 7,, total iterations T, metric weights w1, w2, w3-
initialize 7 (0) = 1 and sample ( Him by Xavier initialization.
initialize (()(0)) A (W)( by ( (0 W0 do
for t= 0, 1, ... T
5: calculate the objective function F(B()(t))) by Á, X(t). v(t) and (()(t)).
6:
for layers 1 1,2, 1,2,...,,L do
7:
+ - () (t) VV ((0()(1))) (0 (0((+1)+PP)) (
8:
1)).
9:
++)(++))+((((+++++
1/.0.
10:
(( + 1)) A (W 1)H/
I1:
return ((r(T))
In line of Algorithm 1 unless otherwise specified, we employ the random direction finite difference method (Equation (31) in Nesseerov & Spokoiny 2017)) compute the derivative of the objective function with
46

---

Published in Transactions on Machine Learning Research (06/2025)
respect to the scaling factor y. Specifically, use
E, F(((7(t) pd)) F(0()(())) m1
to approximate the gradient V (((r(())))), where 8 is small scalar and μ follows the standard Gaussian distribution NN It). Here, E denotes the Monte Carlo approximation of the expectation, computed by averaging over 3 independent and identically distributed (i.id.) samples of (O,TIt)
For the GCNs with skip connections, we replace VESP and V with (maxigıer. ( mini M - 1)² and (max M mini<i<t M - 1)², respectively. Also, in these models, we use the same scaling factor across all layers. We empirically find that these modifications more effectively minimize the objective function in GCNs with skip connections.
E.2 Analysis on the coefficient u2 in SPoGInit
We analyze the effect of the coefficient wy in SPoGInit, which controls the contribution of the backward signal propagation (BSP) term VBSP in the objective function (Formula (9))). Empirically, we observe that the initial value of VBSP is substantially lower than that of VESP, leading to an imbalance between the two
objectives. To mitigale this discrepancy, in practice, we set a larger value for u2 than wh in order to amplify the role of VBSP during optimization.
We conduct experiments on a 32-layer GCN with tanh activation, trained on the Cora dataset. Table i reports the values of Vrsr and VESP under different settings of w2 {1, 10, 100). We fix the learning rate at 0.1, use 100 optimization iterations, and set w1 W3 1. We report the average result over 50 runs. The results reveal two key trends regarding the impact of w2:
Gradual reduction of VASP u2 increases: As wy increases from 1 to 10 and then to 100, VBSP decreases from approximately 3 x 10-3 to 1.1 x 10 and finally to 1.0 x 10-3. This consistent but diminishing improvement suggests that increasing wa enhances backward signal propagation, though the marginal gain becomes smaller at higher values.
Forward signal propagation deteriorates at large w2: While VESP remains stable between U2 =1 and W/g = 10, it increases sharply when Wy reaches 100, indicating that an overly large W2 harms forward signal preservation.
These findings suggest that W2 = 10 achieves a favorable trade-off between forward and backward signal preservation, yielding low values for both VESP and VESP. Based on this analysis, we adopt w22 = 10 as the default setting in the subsequent experiments.
Table 6:
The VESP and VBSP of 32-layer tanh-activated GCN using SPoGInit with different wy on Cora dataset. In SPoGInit, we set the learning rate as 0.1, total iteration as 100, w, and W' as 1. We report the average result over 50 runs.
w/o SPoG
SPoG using w2 =1 SPoG using W² 10
SPoG using w22 = 100
VESP
31.2 1.3 x 10-1
5.4 10-3
6.4 10-3
7.5 10-2
VBSP
3.0 x 10-3
1.1 x 10-3
1.0 x 10-3
E.3
Computational efficiency of GEV in SPoGInit
In this subsection, we analyze the extra computational cost. brought by introducing GEV metric in SPoGInit. We claim that the additional cost introduced by adding the GEV term to SPoGlnit's objective is minimal, and we believe the performance gains justify its inclusion.
Technical explanation:
47

---

Published in Transactions on Machine Learning Research (06/2025)
(ir(H())) Recall that the GEV metric is computed as M = ! where the Dirichlet energy given by
Dir(II) = tr(H1 Lif,, and L denotes the normalized Laplacian of the imput graph & (see Appendix B for mathematical details). Importantly, the GEV metric depends solely on the final-layer node embeddings H L.) which are computed in a single forward pass of the network. The additional cost of computing the norm and Dirichlet energy negligible compared to the forward pass itself.
We note that the computation of FSP metric already requires a forward pass. Thus, the final-layer embeddings for GEV computation be directly obtained from this same forward pass, meaning no additional computation is needed.
Empirical evaluation:
To evaluate the computational efficiency of incorporating GEV, we conduct experiments using a 64-layer GCN with tanh activation on the Cora and PubMed datasets. As shown in Table 7 the runtime of the SPoGInit algorithm with GEV is only slightly higher than that without GEV, with an increase of just about 1% 3%. This indicates that adding GEV introduces minimal overhead the initialization process. In practice, this additional cost is negligible and acceptable, given the consistent performance improvements observed when GEV is used alongside the FSP and BSP metrics.
Table 7: Initialization time (in seconds) of 64-layer tanb-activated GCN using SPoGInit with and without GEV on the Cora and PubMed datasets. For each case, the total number of initialization iterations is set to 40, and the results are averaged over 3 runs.
Cora
PubMed
SPoGInit without GEV
6.46
9.90
SPoGInit with GEV Relative Overhead of GEV
6.66
10.0
3.1%
1.1%
In summary, since the GEV computation utilizes existing outputs from the forward pass with minimal overhead, its integration into SPoGInit's objective is both computationally efficient and beneficial in practice.
E.4 Comparison of the per-layer scaling factors across different baseline initializations
By lines 9-10 of Algorithm 1 SPoGInit's adjustment of the scaling factor (()) equivalent to modifying the initialization standard deviation ow, We have plotted the values of a i for each layer of our SPoGInit, well for several bascline initialization methods, including Conventional initialization, Xavier, VirgoFor, and VirgoBack. As shown in Figure au, differs significantly across different initialization methods. Notably, SPoGInit performs an adaptive variance search, which leads to a fluctuating pattern of ww,i across layers.
10a
SPoGinit
Xavier
Conventional
x 10
VirgoFor
VirgoBack
10
40
Layer
Figure 6: Layer-wise own, of a 64-layer tanh-activated GCN using different initialization methods on the Cora datasets. In SPoGInit, we set the learning rate as 0.02, the early stop step as 10, and the number of total step is set as 40.
48

---

Published in Transactions on Machine Learning Research (06/2025)
F
Additional experiments
F.1 Experiments on additional datasets
Building upon the experimental results Section we further evaluate the performance of SPoGInit on additional homophily and non-homophily datasets. For homophily datasets, we consider Amazon-photo and Amazon-comppterr (Shchur et al. 2018), following the data splits used in Luo al. (2024). For heterophily datascts, in addition to the Arxiv-ycar dataset examined in Scction
incorporate Roman-cmpire and Table Statistics of the additional homophily datasets used the experiments.
Amazon-ratings (Platonov et al.
2023 using their default splits. Table summarizes the dataset statistics.
Further implementation details are provided in Appendix G.I
Datasct
Nodes
Features
Edges
Class
Homophily
Training/ halngg///liaiiiin,, Test
Amazon-photo 7,650
745
238, 132
0.83
60%/20%//2%%
Amazon-computers
13,752
767
491,722
0.78
60%/20%/2000
Roman-empire
22,662
300
32,927
0.05
50%/25% 25% /25%
Amazon-ratings 24,492
300
93,050
0.38
50%/25% 22/5//55%// 25%
Evaluation on homophily datasets
We first evaluate the performance of GCN models with varying depths and initialization schemes on the two homophily datasets, Amazon-photo and Amazon-computers. The results are summarized in Table g To limit computational overhead, we enforce a maximum depth of layers.
Table 9: Test accuracies of GCN models with varying depths and initializations on Amazon-photo and Amazon-computers. The bold figure highlights the best performance among different initializations. 'Deg' refers to the test accuracy degradation as the depth increases from 4 to 32 layers. The smallest performance drops are highlighted in orange. The results demonstrate that SPoGInit significantly reduces performance degradation compared baseline initialization and enhances the performance deep GNN models across
different architectures.
Amazon-phote
Amazon-computers
Model
Init.
4
16
32
Deg.
4
16
32
Deg.
Conventional
94.1
93.4
68.3
55.0
39.1
91.9
84.5
56.5
55.8
36.1
Xavier
94.1
93.6
92.1
85.9
$ 8.2
91.6
89.2
82.4
74.7
$ 16.9
GCN
VirgoFor
94.5
93.7
92.5
85.1
$ 9.4
91.9
89.4
82.1
79.7
$ 12.2
VirgoBack
94.5
93.0
92.1
85.2
4 9.3
91.7
89.4
84.3
79.3
4 12.4
SPoGInit
94.3
93.9
92.0
86.5
4 7.8
91.8
89.3
83.9
79.7
11.11
Conventional
96.2
96.4
96.2
96.5
T 0.3
92.8
93.4
93.9
93.8
1.0
Xavier
96.6
96.6
96.3
95.7
0.9
93.2
93.6
93.5
93.1
40.1
ResGON
Virgolor
96.4
96.2
95.5
94.1
2.3
93.4
93.4
92.5
90.5
$29
VirgoBack
96.7
96.1
95.6
93.4
3.3
93.3
93.2
92.5
90.1
432
SPoGTnit
96.4
96.5
96.3
96.4
0
92.7
93.2
93.8
93.9
1.2
Conventional
96.0
96.4
96.4
96.6
0.6
92.8
92.7
93.3
93.4
0.6
Xavier
96.4
96.6
96.5
95.4
1.0
92.8
93.0
93.7
93.3
0.5
geNResGCN
VirgoFor
96.4
96.4
95.3
91.7
4 4.77
92.9
93.4
92.3
87.5
45.
VirgoBack
96.6
96.3
95.2
91.2
5.4
92.9
93.3
92.2
86.3
$ 6.6
SPoGInit
96.1
96.2
96.4
96.5
0.4
92.5
92.7
93.3
93.7
1.2
Conventional
96.1
95.7
92.9
85.6
4 10.4
92.7
90.6
89.3
79.7
4 13.0
MixHlop
Xavier
96.4
95.8
94.6
91.4
5.0
93.1
92.9
91.0
83.8
9.3
SPoGInit
96.3
95.7
95.5
92.5
3.9
93.3
92.6
91.6
88.4
4.9
49

---

Published in Transactions on Machine Learning Research (06/2025)
Table 9 indicates that SPoGInit enables deep vanilla GCN and MixHop models to achieve better performance than her initialization baselines. Despite the general trend that increasing depth leads to some degree of performance degradation, models initialized with SPoGImit exhibit a more gradual decline in accuracy. Specifically, performance degradation is most severe under the Conventional initialization, where test accuracy can drop by over 30% when increasing the depth from to 32 layers. Alternative initialization methods such as Xavier, VirgoFor, and VirgoBack mitigate this degradation to some extent. Among all initializations, SPoGInit consistently demonstrates the best performance in deeper models. Notably, on the Amazon-cou cmazunncomputers dataset, SPoGInit reduces the performance drop in MixHop by 4.4% compared to the best-performing baseline, Xavier initialization.
Additionally, Table I indicates that SPoGInit benefits from increased depth in ResGCN and gat RetRee, leading to superior performance for 32-layer networks. On the Amazon- Conbuuerss dataset, it outperforms other initialization baselines, while on the Amazon-Phot dataset, achieves very competitive performance. We observe that deep ResGCN and gatResGCN maintain strong performance, with test accuracy exceeding 90% under widely used initialization schemes. We hypothesize that these two datasets are relatively simple, allowing residual connections to facilitate stable optimization during training, which in turn enhances model performance.
These findings underscore the critical role of initialization in deep networks and demonstrate the ad advantages of SPoGInit in mitigating performance degradation in deep GNN models.
Evaluation on non-homophily datasets
Amazon-ratings dataset
We evaluate SPoGInit on the heterophily dataset, Amazon-ratings, with results presented in Table 10
As presented in Table 10 for ResGCN, gatResGCN, and MixHop models, SPoGInit outperforms other initialization bascline methods when increasing the network depth. Conventional and Xavier initialization lead to performance degradation as network depth increases, while VirgoFor and VirgoBack sulfer even more severe degradation. In contrast, SPoGInit significantly mitigates performance degradation of deeper networks. Morcover, on ResGCN and gatResGCN, SPoGInit consistently improves performance as depth increases, demonstrating its effectiveness in deep models.
For the vanilla GCN, we observe that both VirgoFor and VirgoBack successfully mitigate performance degradation. Notably, VirgoBack achieves a 2% performance improvement as depth increases. However, this improvement is largely due to its relatively weaker performance on shallow GCNs (4 layers). In contrast, SPoGTnit outperforms other initializations on deeper GCNs, highlighting its robustness handling depth-related challenges.
Roman-empire dataset
Beyond Amazon-ratings, we extend our experiments to the heterophily datasct Roman-empire. The original paper (Platonov et al.) 2023) adopts skip connections for all the tested GCN models. Empirically, we indeed find that without skip connections, models perform severely worse. Thus, for this dataset we focus on the performance of ResGONs across varying depths and initializations.
Table I1 shows that all baseline initializations suffer from severe performance degradation in deep models. In contrast, SPoGTnit consistently achieves superior performance on deep GCN models and substantially reduces performance degradation as the network depths increase.
Summary
In summary, across these additional homophily and heterophily datasets, SPoGInit consistently outperforms baseline initializations on deep GCN models, and substantially alleviating performance degradation in deep GCN models. These results provide robust empirical evidence for the effectiveness of SPoGInit in enhancing the stability and performance of deep GCNs.
50

---

Published in Transactions on Machine Learning Research (06/2025)
Table 10: Test accuracies of GCN models on Amazon-ratings dataset with varying depths and initializations. The bold figure highlights the best performance among different initializations. "Deg' refers to the test. accuracy degradation as the depth increases from 4 to 32 layers. The smallest performance drops are highlighted in orange. The results demonstrate that SPoGInit siguificantly reduces performance degradation compared to baseline initializations and enhances the performance of deep GNN models across different architectures.
Amazon-rating
Model
Init.
4
16
32
Deg.
Conventional
44.7
44.9
42.5
38.2
6.5
Xavier
44.4
45.6
45.1
44.0
0.4
GCN
VirgoFor
45.1
45.9
45.8
45.3
0.2
VirgoBack
43.1
44.5
45.5
45.1
2.0
SPoGInit
45.0
45.9
45.7
45.4
0.4
Conventional
48.5
48.9
48.9
47.6
0.9
Xavier
48.9
49.2
48.5
42.1
6.8
ResGCN
VirgoFor
48.6
48.8
46.5
36.8
11.8
VirgoBack
48.6
49.0
45.9
36.7
11.6
SPoGInit
48.6
49.1
49.3
49.5
0.9
Conventional
48.8
48.8
49.3
47.4
11.
Xavier
49.0
49.2
48.9
42.3
6.7
gatResGCN
VirgoFor
48.4
48.6
46.3
36.8
11.6
VirgoBack
48.3
48.5
45.6
36.7
4 11.6
SPoGInit
48.4
48.9
49.1
49.2
0.8
Conventional
45.8
46.1
44.8
44.8
1.0
MixHop
Xavier
45.8
46.0
44.9
44.8
1.0
SPoGInit
46.9
47.7
47.2
46.1
4 0.8
Table 11:
Test accuracies of ResGCN model with varying depths and initializations on the Roman-empire datasct. The bold figure highlights the best performance among different initializations. 'Deg' refers to the test. accuracy degradation as the depth increases from 4 to 32 layers. The smallest performance drops are highlighted in orange. The results demonstrate that SPoGInit significantly reduces performance degradation compared to bascline initializations and enhances the performance of deep networks.
Amazon-ratings
Model
Init.
4
8
16
32
Deg.
Conventional
78.9
79.4
79.2
76.9
| 2.0
Xavier
78.7
79.0
78.2
42.3
$ 36.4
ResGCN
VirgoFor
78.3
78.9
64.6
15.6
$ 62.7
VirgoBack
78.3
78.9
66.5
15.9
$ 62.4
SPoGInit
78.9
79.4
79.5
79.1
0.2
51

---

Published in Transactions on Machine Learning Research (06/2025)
F.2 Comparison and integration of SPoGInit with additional methods
In this subsection, evaluate SPoGInit by comparing it with DGN (Zhou et al 2020b normalization
technique designed to mitigate oversmoothing, and CO-GNN (Finkelshtein et al. 2023) dynamic message- passing framework. Additionally, we examine the effects of integrating SPoGInit with these methods to assess potential performance improvements.
Comparison and integration of SPoGInit with DGN
We first evaluate SPoGInit. in comparison with DGN and assess their combined effects. Since DGN (Zhou et al. 2020b) originally designed for GCN models without skip connections, perform experiments vanilla GCN using Cora, PubMed, and the large-scale OGBN-Arxiv datasct. The detailed results are presented in Table 12 and Table 13
Table 12: Test accuracies of GCN models with SPoGInit or DGN technique Cora. and PubMed datasets. The bold figure highlights the best performance among different initializations. "Deg' refers to the test accuracy degradation as the depth increases from 4 to 32 layers. The smallest performance drops are highlighted in orange. The results demonstrate that SPoGInit significantly reduces performance degradation compared to DGN.
Cora
PubMed
Model
Method.
4
8
16
32
Deg.
4
8
16
32
Deg.
DGN
80.6
79.8
75.8
72.6
4 8.0
77.7
78.8
78.0
77.6
4
0.2
GCN
SPoGInit
79.8
79.6
78.2
75.8
4.0
77.4
77.5
77.0
78.4
f 1.0
SPoGInit + DGN
80.4
79.2
76.8
75.0
5.4
77.5
77.9
78.0
77.5
0
Table 13: Test accuracies of GCN models with SPoGInit or DGN technique on the OGBN-Arxiv dataset. The bold figure highlights the best performance among different initializations. "Deg" refers the test accuracy degradation as the depth increases from 4 to 32 layers. The smallest performance drops are highlighted in orange. The results demonstrate that SPoGInit combines effectively with DGN and significantly reduces its performance degradation as the depth increases.
OGBN-Are
Model
Method
4
8
16
32
Deg.
DGN
69.7
68.2
63.7
61.7
8.0
GCN
SPoGInit
69.7
69.2
68.1
63.1
6.6
SPoGInit+DGN
69.9
69.3
69.6
68.3
1 1.6
Experimental results in Table 12 demonstrate that, compared to DGN, SPoGInit more effectively mitigates performance degradation as GCN depth increases small-graph datascts such Cora and PubMed. Moreover, the Cora dataset, initializing the model with SPoGInit before applying DGN improves DGN's effectiveness, reducing performance degradation in deep GCNs by over 2% compared to using DGN alone, though it remains slightly less effective than using SPoGInit alone.
Table 13 highlights the effectiveness SPoGInit in deep GCNs on the large-scale OGBN-Arxiv dataset. Specifically, using SPoGInit alone outperforms DGN alone by over 1% in deeper networks. Moreover, integrating SPoGInit with DGN further enhances performance, achieving an improvement of more than 5% compared to either method individually. This effect is particularly pronounced on large graphs, likely due to the greater difficulty of achieving stable optimization in such settings.
Comparison and integration of SPoGInit with CO-GNN
We evaluate the performance SPoGInit in comparison with CO-GNN a method based on a dynamic mnessago-passing framework -nd also investigate the benefits of integrating SPoGInit into CO-GNN. We choose ResGCN the backbone architecture of our SPoGInit. Our experiments are conducted on three benchmark datasets: Cora and PubMed, which exhibit high homophily, and Amazon-ratings, which is
52

---

Published in Transactions on Machine Learning Research (06/2025)
characterized by heterophily. For consistency with our experimental setup, use the dataset splits detailed in Table 1 (instead of those in Finnelshtein et al. (0023) ). Detailed performance results for Cora and PubMed
are reported in Table 14 while those for Amazon-ratings are provided in Table 15
CO-GNN comprises two key components: an action network and an environment network. We define the overall layer count of CO-GNN as the sum of the layers these two networks. Specifically, for the Cora and PubMed datasets a one-layer action network is employed, whereas for Amazon-ratings a two-layer action network is utilized.
Experimental results indicate that CO-GNN exhibits a pattern of performance variation as network depth increases. On datasets such as Cora and Amazon-ratings, performance initially improves with increasing depth; however, beyond 16 layers, further deepening leads to significant degradation. We hypothesize that this behavior arises from the need to jointly train the action and environment networks- a process that roquires greater training effort to fully converge in deeper architectures compared to conventional GCNs.
Table 14 demonstrates that network depth increases, SPoGInit outperforms CO-GNN on homophilic datasets such as Cora and PubMed. This indicates that SPoGInit more effectively mitigates the performance degradation typically observed in deeper architectures. On the heterophilic Amazon-ratings datasct, Table 15 shows that while CO-GNN alone attains higher performance than SPoGInit alone, integrating SPoGInit into CO-GNN further improves its performance, enabling deeper networks to achieve superior results while reducing degradation. We hypothesize that this improvement stems from SPoGInit's ability to enhance signal propagation in deep CO-GNN architectures, thereby facilitating more effective training. Notably, our experiments show that the training accuracy of a 32-layer CO-GNN Amazon-ratings increases from 81.1% to 86.7% after integration with SPoGInit. (Training accuracies are not reported in the main result tables.)
Table 14: Test accuracies of CO-GNN model and ResGCN with SPoGInit the Cora and PubMed datasets. The bold figure highlights the best performance among different initializations. "Deg' refers to the test accuracy degradation as the depth increases from 4 to 32 layers. The smallest performance drops are highlighted in orange. The results demonstrate that SPoGInit + ResGCN significantly reduces performance degradation compared to CO-GNN and enhances the performance of deep ResGCN.
Cora
PubMed
Method.
4
8
16
32
Deg.
4
8
16
32
Deg.
CO-GNN
78.2
78.7
80.2
73.7
$ 4.5
77.2
76.2
76.0
75.7
1.5
SPoGInit+ResGCN
75.7
77.9
78.5
78.5
1 2.8
75.4
76.2
76.4
77.0
1 1.6
Table 15:
Test accuracies of CO-GNN, SPoGInit+ResGON, and SPoGInit+CO-GNY on the Amazon-ratings dataset. The bold figure highlights the best performance among different initializations. "Deg' refers to the test accuracy degradation as the depth increases from to 32 layers. The smallest performance drops are highlighted in orange. The results demonstrate that SPoGInit combines effectively with CO-GNN and significantly reduces its performance degradation.
Amazon-ratings
Method
4
8
16
32
Deg.
CO-GNN
48.1
50.3
51.1
50.6
1 2.5
SPoGInit+
48.6
49.1
49.3
49.5
f 0.9
SPOGInit+CO-GNN
47.9
49.4
50.4
51.0
1 3.1
In conclusion, our experiments reveal that SPoGInit surpasses these methods or combines effectively with them, leading to enhanced performance. This demonstrates the versatility of SPoGInit when applied alongside advanced techniques in tackling diverse challenges in GNNs.
53

---

Published in Transactions on Machine Learning Research (06/2025)
F.3 More experiments signal propagation
In this subsection, we provide additional insights into the behavior of signal propagation (SP) in deep GCNs by visualizing activation and gradient matrices using heatmaps. Our goal is to illustrate clearly how widely used initialization methods fail to maintain stable signal propagation and to highlight how SPoGInit addresses these issues effectively.
Specifically, we examine 256-layer GCN using the Tanh activation function. For each initialization, we visualize the activation and gradient matrices shallow (2-nd), intermediate (127-th), and deep (255-th) layers. Each activation matrix has shape of N d, where N denotes the mumber of graph nodes, and d = 64 denotes the network width. For visualization, we select embeddings corresponding to the first 64 nodes.
We first observe that Conventional initialization (Figure and Xavier initialization (Figure 8 lead to degraded signal propagation. Specifically, activation values at deeper layers and gradients at shallower layers become excessively small, indicative of forward and backward signal vanishing issues. By contrast, VirgoFor initialization (Figure 9) and VirgoBack initialization (Figure 10 maintain relatively stable activation matrices but result in gradients al shallower layers significantly exceeding acceptable thresholds, indicating slight, backward SP explosion. In comparison, depicted in Figure []]
SPoGInit successfully maintains stable activation and gradient matrices across all depths, effectively mitigating both SP vanishing and explosion issues in deep GCNs.
Activation Mantix 2-ad loyer
Activation Maaix of 127-4h layer
Activation Matri of 255-th layer
Bide boles
bolos
-104
Bidde Diseronn
60 00.50:52444 30 32
40 32 28 34
iissistias suss siepeesis sestaiis modes
dedii doserossseeeespeseseee daspsaniroies di oodes
10-
Fin aodes
Geadieai Matri layer
Cinciiant 127-th layor
Gradient Matii 24555 layer
-10H
Wogle
à 3 12.5 1821 2427 su wis.s eisp sesiveoes Wegght Colama ladox
3 12151922226 slsts 364422664422444 aesiessiiis scahains
3. 131 (iz2 dedr 1536399444 184224 sasiiii
10-4
Weight Colarn Indox
Weggzi Colana indos
Figure 7: The heatmap of the activation and gradient matrix of a 256-layer tanh-activated GCN with Conventional initialization.
54

---

Published in Transactions on Machine Learning Research (06/2025)
Activation. Manna of ad loyer
Astivttion Maxix of 127 th layer
Activation Marii of 255 Jayec
Sokles Discnic bile
10
Billen Diomin
50-50 68 02 35 3532235
43 12.5
-10-
121511211220 2013000040055551110000
Manix 2-nd Layer
Gradicat 127-ch layer
Gradient 255-th Joyer
10-1
Weyle Ealox
10-
6 12151521242h 1551112222 3011hh002200000000000003 aas
3 1215t92l:s 2003 49424899444444 5453000s
3 9.1215 1821 3600 Weight Oolana Endox
-10
Weight Colama Endox
Weggn Oelana Index
Figure 8: The heatmap of the activation and gradient matrix of a 256-layer tanh-activated GCN with Xavier initialization.
Activation Marris of 2ndd layer
Activation Marix of 127 ch bayer
Activation Matris of 255 I5 Jayer
Holien Diunciie laice
30 21 36 3023 30
Willee Nitesste Tulee
10
56 52 4t cp 23
Blacaria
1004
Layer
127-th layer
loyer
100
Wodgi Nors Saice
Weigh Tylee
32 24
10cl
50 40 56
52
-104
152124227 2012220022200 9642444551 54500005
1215192126221 26 2422233533544445555555 (53333894255555555577733 54377155
1821 3020 1943355 11344 5003
Weight Colana Tadox
Weign Orlern Trdos
Weight Colana Endos
Figure 9: The heatmap of the activation and gradient matrix of a 256-layer tanh-activated GCN with VirgoFor initialization.
55

---

Published in Transactions on Machine Learning Research (06/2025)
Activation Monii Zend lnyer
Activation Manix of 127-hh Siyer
Activation Matri of 285-th layer
60 55 45 00 30.33 35 24 24.00
Thalen sire fudio:
10A
FOSS MEURE GHINON
52 is ab 1o 24
24162/200009994253333 54575065
-10
10-1
Wodge Kone lodes
-10-
30 333 00 35
13/910022627900 101156 14335-41111111111 5457045
6 411151922600 9035 24
1215182) 2027 Wolettes sisestee
Wegght Colana Eadox
Weghi Colana Iadox
Wegght Colana fndos
Figure 10: The heatmap the activation and gradient matrix of a 256-layer tanh-activated GCN with VirgoBack initialization.
Activation Manii 2ndd
Activation Matix of 127
Activation Matrix of 255-th
Bokk Dorcon Todis
25 20
00:35 64 36 32 36
10
0055 52
Gradieni Matrix of 2-nd layer
Grddimi Matrix of 127-th layer
Gradient Marri Jayer
10
52.42.65 40
12251822220 336733336336444466 565h6063
1215182224 503336 3442450011 sushioos
3.3 1821 30 3633--2-5555 48. 1164 sl0cc
-104
Wegght Coluans Ladox
Waggi Citerns Index
Weggi Cabama Indox
Figure 11: The heatmap of the activation and gradient matrix of 256-layer tanh-activated GCN with SPoGInit.
56

---

Published in Transactions on Machine Learning Research (06/2025)
F.4 Computation cost and scalability of SPoGInit
We provide detailed discussion on the computational cost and scalability of SPoGInit in this subsection. Computational cost analysis
SPoGInit is utilized as a weight initialization search method prior to the main model training process (as described in Algorithm | in Appendix FJ. We identify two primary sources of additional computational cost: (a) scarching steps: in practice, SpoGInit typically needs 20-40 search steps, which small relative the roughly 800-1500 training epochs of GNNs; (b) optimization method: SPoGInit employs a zeroth order optimization method, which only relies only forward propagation computations, not requiring more computationally expensive backward passes. This analysis indicates that the computational overhcad introdueed by SPoGImit is relatively minor.
Besides, we conduct an empirical study to evaluate the computation overhead brought by SPoGlnit. In our experiments, we compare the training time of a vanilla GCN architecture (without SPoGIuit) against the same architecture incorporated with SPoGInit, using 40 searching steps, on both the Amazon-ratings and OGBN-Arxiv datasets. As shown in Table 16. SPoGInit consistently adds approximately 18% to the training time on these two datasets. In general, incorporating SPoGInit increases the overall training computational cost by roughly 10%-20%. Given the performance improvements observed in GNNs, we consider this additional cost to be an acceptable trade-off.
Table 16: Comparison of total training time for 64-layer tanh-activated GCN with Xaiver initialization and SPoGInit on the small dataset Amazon-ratings and the large dataset OGBN-Arxiv. All experiments are run for 1000 training epochs. The searching steps of SPoGInit are set as 40.
Datasct
Nodes
Xavier
SPoGInit Additional Time
Amazon-ratings
24,492
185.7s
220.5s
18.7%
OGBN-Arxiv
169,343
901.3s
1064.1s
18.1%
Scalability analysis
Notably, Table 16 shows that as the graph size grows larger, the proportion of SPoGInit computation (relative to total training computation) would not increase. This implics that SPoGInit can scale effectively to large graph datasets.
F.5 More experiments graph attention networks
We conduct comparative experiments between SPoGInit and other baseline initialization methods Graph Attention Networks (GAT) (Veličković et al. 2017). Building upon the original GAT architecture, we further investigate the performance on a residual-enhanced variant (ResGAT) by incorporating skip connections. The results are presented in Table 17
The experimental results show that SPoGInit significantly mitigates performance degradation on GAT and ResGAT. Moreover, on ResGAT, while other baseline methods still suffer from severe performance drops the network depth increases, SPoGInit instead leads to improved performance with greater depth, demonstrating its effectiveness in deep architectures.
F.6 Experimental comparison with G-Init
This subsection presents a comparison between SPoGInit and G-Init (Kelesis et al,, 2024), an initialization method specifically designed to alleviate soo-hhng in deep GNNs. G-Init incorporates the graph topology into the initialization process. Specifically, G-Init scales the weight variance of the base initialization by factor of d, Following the experimental sctup in the original G-Init paper, set d, 1.6 for
WWiil the original paper Kelesis 2024 adopts ReLU as the activation function-typleally paired with Kaiming initialization we tanh activation, which 18 commonly initialized using Xavier.
57

---

Published in Transactions on Machine Learning Research (06/2025)
Table 17: Test accuracies of GAT and ResGAT with varying depths and initialization methods. The bold figure highlights the best performance among different initializations. "Deg' refers to the test accuracy degradation the depth increases from 4 to 64 layers. The smallest performance drops are highlighted in orange. We set the number of attention head to be 1. The results demonstrate that SPoGInit reduces performance degradation compared to baseline initializations and enhances the performance of deep GAT and ResGAT.
Cora
Arxiv
Model
Init.
16
32
Deg.
8
16
32
64
Deg.
Conventional
79.4
73.2
50.3
37.4
31.9
47.5
68.2
66.2
5.9
5.9
5.9
62.3
Xavier
79.7
79.5
74.1
71.2
68.8
10.9
68.4
68.1
61.1
43.7
14.9
4 53.5
GAT
VirgoFor
79.0
78.9
74.9
74.7
74.0
5.5
68.5
68.4
65.8
63.7
50.5
18.0
VirgoBack
78.1
76.2
74.7
71.6
4
68.5
68.4
65.8
49.5
19.0
SPoGInit
79.4
78.8
76.2
76.3
74.5
4.9
68.3
66.0
66.7
64.0
47.1
J 21.2
Conventional
78.3
78.5
78.1
77.5
32.5
45.8
70.6
71.4
71.8
21.6
49.0
ResGAT
Xavier
77.6
79.3
77.8
32.3
32.0
45.6
70.8
71.4
69.7
21.7
21.7
49.1
VirgoFor
78.4
77.9
75.4
31.3
31.5
16.9
70.5
70.5
21.8
21.6
21.7
148.8
VirgoBack
79.4
77.6
76.1
26.1
33.2
4
46.2
70.7
70.4
21.6
21.6
16.3
54.5
SPoGInit
77.1
77.4
78.6
76.0
78.3
7 1.2
70.7
71.3
71.9
71.8
71.4
0.7
OGBN-Arxiv and Arxiv-year, and d, = 2.0 for all other benchmark datasets. We systematically evaluate the performance of tanh-activated GCN architectures ranging from to 64 layers under different initialization
schemes.
The results, summarized in Table I8 show that while G-Init alleviate performance degradation in deep GCNs to some extent, SPoGInit consistently outperforms it in most cases. For instance, on the PubMed dataset, G-Init suffers from a 4% performance drop depth increases, whereas SPoGInit achieves stable or improved performance. These findings highlight the effectiveness of SPoGInit's initialization strategy, which explicitly searches for stable signal propagation patterns, in mitigating depth-induce degradation in GCN training.
Table 18: Test accuracies of GCN models initialized with G-Init and SPoGInit across varying depths. The bold figure highlights the best performance among different initializations. "Deg" refers the test accuracy degradation the depth increases from 4 to 64 layers. We choose the starting point of SPoGInit VirgoFor on the Arxiv dataset. The results show that while both initializations help alleviate degradation in deep GCNs, SPoGTnit achieves more consistent performance and smaller accuracy drops across different datasets.
Cora
Arxiv
Model
Init.
4
8
16
32
64
Deg.
4
8
16
32
64
Deg.
G-Init
79.7
78.3
76.7
75.2
73.4
6.3
69.6
69.5
68.8
66.5
58.9
[
10.7
GCN
SPoGInit
79.8
79.6
78.2
75.8
73.7
6.1
69.6
69.6
68.7
67.2
61.4
8.2
PubMed
Arxiv-year
Model
Init.
4
8
16
32
64
Deg.
4
8
16
32
64
Deg.
G-init
78.5
76.8
78.0
77.7
74.5
$ 4.0
43.8
29.9
45.5
45.6
43.4
0.4
GCN
SPoGInit
77.4
77.5
77.0
78.4
78.1
0.7
43.9
41.9
45.2
44.9
43.9
58

---

Published in Transactions on Machine Learning Research (06/2025)
G Supplemental experiment results
G.1 Experimental settings and hyperpameters
Settings for the experiments on mainstream datasets.
We set W1 1, 1, W2 = 10, W = for the vanilla GCN and w1 = 1, W2 = 1, w3 1 for other architectures these experiments. An carly stopping criterion is also implemented for SPoGInit: if the metric fails decrease over å consecutive steps, the search is terminated. Unless otherwise specified, SPoGInit initialized with Xavier initialization in these experiments. To guarantee that models with the same depth have the same receptive field, we set the number of hops to 1 in the MixHop layer for the MixHop architecture.
In our experiments on the Cora and PubMed datasets,
We perform grid searches over learning rates of 1e-3, le-4, 5e-5, and 1e-5.
The training epochs and early stopping patience are listed in Table 19
For vanilla GCN and MixHop, we evaluate two configurations: (1) weight decay set to 5e-3 and dropout rate set to 0.5, and (2) both weight decay and dropout rate set to O. We report the best performance achieved between these settings.
For ResGON and gatResGCN,, we the dropout rate to 0.5.
In Table 2 the learning rate for SPoGInit is set to 0.1. The early stopping step is set to 20 for ResGCN and gatResGCN, and 10 for vanilla GCN and MixHop. In the experiments with ResGCN and gatResGCN, SPoGInit starts with conventional initialization.
In Figure we use PyTorrhh's autograd functionality to compute the gradient of the scaling factors. In Figure and the learning rate for SPoGInit is set 0.05 for ResGCN and MixHop, with the early stopping step d set to 10 for ResGCN.
Table 19: Hyperparameter configurations of experiments on Cora and PubMed.
GCN layers
training epoch
early stop patience
4/8/16 layers
800
200
32 layers
1200
300
layers
1500
375
In the experiments on the OGBN-Arxiv and Arxiv-year datasets,
All models are trained for 1000 epochs.
The learning rate is set 5e-3 for ResGCN and gatResGCN, and 5e-4 for MixHop. For the vanilla GCN, the learning rates are configured as follows: 5e-3 for the 4-layer and 8-layer models, 5e-4 for the 16-layer and 32-layer models, and 5c-5 for the 64-layer model.
For ResGON and gatResGCN, set the dropout rate to 0.5.
For SPoGInit, the learning rate is set to 0.2 for ResGCN and gatResGCN, 0.1 for MixHop, 0.07 for vanilla. GCN on the Arxiv-year dataset, and 0.05 for vanilla GCN on the OGBN-Arxiv dataset. The parameter 5 in SPoGInit is set to 10 for ResGCN, gatResGCN, and MixHop, and 20 for vanilla GCN.
In the experiments on the Amazon-photo and Amazon-computers datasets,
We perform grid searches over learning rates of 1e-3, 1e-4, 5e-5, and 1e-5.
59

---

Published in Transactions on Machine Learning Research (06/2025)
All model are trained with 64 hidden units.
The training epochs and early stopping patience are listed in Table 19 One difference is that for 32-layer model, we used 1000 epochs for training and 200 epochs for early stopping patience.
For ResGCN, gat ResGCN and vanilla GCN, we set the dropout rate to 0.5. For vanilla. GCN, we set. the weight decay to be 0.00005. For MixHop, we tried two configurations: (1) dropout 0.5, weight decay 0.00005 (2) dropout O, weight decay O, and we choose the best performance amoug these configurations.
We use the same configurations of SPoGImit in Cora and PubMed datasets, For the Amazon-computers dataset, the starting point set as VirgoFor.
In the experiments on the Amazon-ratings and Roman-Empire datasets. We use VirgoFor the starting point of SPoGInit in the experiments with vanilla GCN, and learning rate of SPoGInit is set to 0.1. The other configurations are the same with those in the OGBN-Arxiv and Arxiv-year datasets.
In the experiments with DGN,
In the Cora and PubMed datasets, we perform two configurations: (1) following the setting in Zhou et al. (2020b), the dropout as 0.6, weight decay is set 0.0005. (2) dropout and weight decay are both set to be zero. We report the best performance amoug these two configureations. The other configurations are the same with those in Cora and PubMed experiments.
In the OGBN-Arixy dataset, we use the vanilla GCN with Conventional Initialization as base model. The other configurations are the same with those in OGBN-Arxiv experiments.
For the group number G in DGN, we set it 10 in Cora, and 5 for other datasets.
In the experiments with CO-GNN,
To align with the experiment settings in Section 5 we fix the width of environment network to be 64, and we set the width of action network to be 16 in Cora and PubMed datasct, and 32 in the Amazon-ratings. And we use mean GNN the action network.
In the Cora and PubMed datasets, we follow the settings in Finkelshtein et al. (2023): We perform grid searches over learning rates of 0.01, 0.05, 0.005, 0.0005. The dropout is set as 0.5 and weight decay is set as 5e-4, and To set as 0.1. We use mean GNN as the environment network in Cora and GCN as the environment network in PubMed. We train the model for 1000 epochs and we adopt the skip connection in the model. The other configurations are the same with those in Cora and PubMed experiments in sctting.
In the Amazon-ratings datascts, we follow the settings in Finkelshtein et al. (2023): we train the model for 3000 epochs, the learning rate set as 3e-4. And we use mean GNN as the environment. network. We adopt the layernorm and skip connection.
Settings for the exploration of starting points in SPoGInit
In these experiments, the setlings for SPoGInit are slightly different from the previous ones. To be more specific,
For ResGCN, the learning rate of SPoGInit is set to 0.1 when starting from VirgoFor or VirgoBack initialization, and 0.2 in all other cases.
For vanilla GCN, the learning rate of SPoGInit set to 0.1 when starting from Conventional initialization and 0.05 in all other cases.
60

---

Published in Transactions on Machine Learning Research (06/2025)
Settings for the missing feature experiments
To enhance the dataset's dependence on and set the train Srain/varo /waliiaaaaaaaa/////aaaa test split as 10%/25% 22552/ /65, which is generated through the implementation in Lim et al. 2021). In this experiment, we set SPoGInit to use Conventional initialization as the starting point when it adopted gatResGCN, while SPoGInit begins with Xavier initialization as the starting point other cases.
relationships, we reduce the proportion of training split
Settings for MILP experiment
In the MILP experiment, we train the models for 500 epochs. The batch size is set as 40 and the hidden dimension is set as 64.
G.2 Ablation study of SPoGInit
In this subsection, conduct the ablation study of SPoGInit by analyzing various combinations of its SP metric components. Specifically, we reformulate the optimization problem (2) to include either one or two of the three SP metrics. Table 20 presents the performance of a 32-layer vanilla GCN with these modified SPoGInit variants on the Cora dataset. For this experiment, both dropout rate and weight decay are set to 0, while all other hyperparameters follow the settings for the experiments on mainstream datasets in Appendix
G.I
The results indicate that incorporating a single SP metric into the optimization problem slightly improves the performance of vanilla GCNs, with the most notable enhancement observed when SPoGTnit includes the FSP metric. Incorporating two SP metrics leads to a more substantial improvement, although it still falls short the performance achieved by SPoGInit using all three SP measures.
These experimental results highlight the importance combining all three SP metrics to maximize the performance of SPoGInit.
Test accuracies 32-layer vanilla GCN with modified SPoGInit variants: ' indicates that a specific metric included in the signal propagation optimization of SPoGInit, while "_" denotes exclusion. The results show that incorporating one or SP metrics improves the performance of the deep vanilla GCN. However, the best performance is achieved when all three SP metrics used in SPoGInit.
Table 20:
Variants ESP BSP
GEV
Test Accuracy
GCN (Xavier)
72.83 0.45
SPoGIInt
73.83 1.72
73.50 0.36
V
73.90 1.56
75.60 + 0.16
/
73.60 + 1.72
73.77 + 1.43
75.80 + 0.16
61

---

Published in Transactions on Machine Learning Research (06/2025)
H Broader impact statement
In this paper, we employ signal propagation theory to analyze the performance degradations in deep GCNs. Additionally, we propose a solution (SPoGInit) to address signal propagation issues and alleviate this problem. This paper is a theoretical and algorithmic paper on graph neural nets, and does not seem to pose negative social impact.
62


Reviews:
[{"review_id": "ge7GE1uJRs", "reviewer": "Reviewer_u83j", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- Introduces a novel signal propagation framework with three metrics (FSP, BSP, and GEV) that address oversmoothing and gradient issues in deep GCNs.\n- Proposes the SPoGInit initialization method, which adapts layer-wise weight variances and shows promising improvements in performance as network depth increases.\n- Provides both theoretical analysis (using the NNGP approximation) and extensive empirical validation across multiple architectures and datasets.\n\n**Weaknesses**\n\n- The analysis relies on an infinite-width assumption, which raises concerns about its applicability to practical finite-width networks and its relationship with GNTK.\n- There is insufficient discussion on computational efficiency, including time and hardware requirements compared to other initialization methods.\n- Key experimental parameters (e.g., the range of $V_{FSP}$ and $V_{BSP}$ values and the emphasis on weight factors like $w_2$) are not thoroughly justified.\n- The added value of incorporating the GEV metric appears marginal relative to the extra computational cost.\n- Inclusion of additional datasets and models (e.g., graph classification tasks, attentive models like GAT), and recent GNN initialization methods such as Jaiswal et al., Kelesis et al. Han et al. (or discuss them in the related work) would provide a fairer and more comprehensive evaluation.\n- Comparison of SpoGInit with other methods that use different activation functions rises concerns about the source of the observed improvements. Are these improvements attributed to the proposed method or to the use of different activation function?\n- Including the resulting values of $\\sigma_i$ for each layer would shed more light on what values does the proposed method learn and if and how they differ from other initialization methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper makes the following contributions:\n\n- **Signal Propagation Framework:** It introduces a framework for analyzing signal propagation in deep GCNs through three key metrics—forward signal propagation (FSP), backward signal propagation (BSP), and graph embedding variation (GEV). This framework provides insight into the issues of oversmoothing and gradient instability in deep GCNs.\n\n- **SPoGInit Initialization Method:** Building on the SP analysis, the authors propose SPoGInit, an initialization scheme that adaptively adjusts layer-wise weight variances by solving an optimization problem aimed at stabilizing the three SP metrics, mainly in the context of deep GCNs.\n\n- **Theoretical Analysis:** The paper offers a theoretical examination under the Neural Network Gaussian Process (NNGP) approximation, demonstrating that traditional initialization methods fail to control all three SP metrics simultaneously as the network depth increases.\n\nThese contributions collectively advance the understanding of initialization in deep GNNs and propose a solution that enhances the training of deeper architectures.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please kindly refer to the Weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Idi0jOwSCN", "reviewer": "Reviewer_zcM9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The theoretical analysis is rigorous, providing clear insights into why traditional initialization methods fail in deep GCNs.\n2. The proposed SPoGInit method is empirically validated across multiple datasets and architectures, demonstrating significant improvements in performance, especially for tasks involving long-range relationships.\n3. The paper is well-structured, with a comprehensive set of experiments and ablation studies that highlight the effectiveness of the proposed approach.\n\nWeaknesses:\n1. The paper lacks a deeper discussion on the computational overhead of SPoGInit, particularly in comparison to traditional initialization methods, which could be a concern for large-scale applications.\n2. While the method is tested on several datasets (4 datasets), the evaluation could be extended to more diverse and real-world graph datasets to further validate its generalizability.\n3. The paper could benefit from a more detailed comparison with other recent techniques addressing over-smoothing and deep GCN performance, such as normalization methods or architectural modifications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel initialization method, SPoGInit, for deep Graph Convolutional Networks (GCNs) by leveraging signal propagation theory to address performance degradation caused by over-smoothing and unstable signal propagation in deeper networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. **Computational Cost and Scalability**  \n   Include a discussion on the computational cost and scalability of SPoGInit, especially when applied to large graphs.\n\n2. **Experimental Evaluation with Diverse Datasets**  \n   Extend the experimental evaluation to include more diverse datasets, such as:\n   - Amazon (https://arxiv.org/abs/1811.05868)\n   - Datasets with non-homophilic graphs  \n   This would help demonstrate the broader applicability of SPoGInit.\n\n3. **Comparison with State-of-the-Art Methods**  \n   Provide a more thorough comparison with state-of-the-art methods aimed at mitigating over-smoothing and improving the performance of deep GCNs. This could include:\n   - **Normalization Methods**:  \n     - DGN: Towards Deeper Graph Neural Networks with Differentiable Group Normalization (NIPS 2022) - [Link](https://arxiv.org/abs/2006.06972)\n   - **Architectural Modifications**:  \n     - Layer-diverse Negative Sampling for Graph Neural Networks (TMLR 2024) - [Link](https://openreview.net/forum?id=WOrdoKbxh6)\n   - **Drop Edges**:  \n     - Cooperative Graph Neural Networks (ICML 2024) - [Link](https://arxiv.org/abs/2310.01267)\n\n4. **Clarification of SPoGInit's Limitations**  \n   Clarify the limitations of SPoGInit, particularly in scenarios where the method may not perform as expected. Additionally, suggest potential future work to address these limitations.\n\n5. **Visualization with Heatmaps**  \n   A heatmap to visualize different initializations would be beneficial for providing an intuitive understanding of the differences between methods.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Co8uNMnQbt", "reviewer": "Reviewer_nwvu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "There are no major problems with the article as a whole. Here are just some suggestions to improve the presentation of the article.\n\n> Some presentation formats need improvement\n\n- 'Kaiming (usually for ReLU)' in section 2.2, should $W_{ij}^{(l)}$ be $W_{kk'}^{(l)}$?\n- All figures are recommended to be redrawn. Multiple sub-figures should be merged directly when drawing with matplotlib, and the legend should be shared and placed uniformly in the upper right area. In addition, it is recommended to change the font or use the matplotlib2tikz package to export the tikz drawing.\n- It is recommended to use a restatable environment to restate the theorem when supplementing the proof in the appendix to facilitate reading.\n\n> Recommended additional references\n\n- Han J, Huang W, Rong Y, et al. Structure-Aware DropEdge Toward Deep Graph Convolutional Networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023.\n\n- Fang T, Xiao Z, Wang C, et al. Dropmessage: Unifying random dropping for graph neural networks[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2023, 37(4): 4267-4275.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors attempt to address the performance degradation of deep GCNs from the lens of signal propagation (SP). Both theoretical and empirical findings underscore the importance of stabilizing three SP metrics proposed in this paper for boosting the performance of deep GCNs. As far as I know, this is a completely new perspective. Although some of the theories are obvious, it is a good contribution to unifying them into a new framework that makes sense.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses above.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three experts reviewed the paper. The authors responded appropriately to the three review comments' suggestions, questions, and concerns and revised the paper. The reviewers agreed to accept the paper unanimously.

As stated above, the paper meets the acceptance criteria in terms of both *Claim and Evidence* and *Audience*. Therefore, I am in favor of Accepting the paper.

I suggest fixing one point: In P.35 L.1, part 2 seems to be a typo of part 1.
Decision: Accept (poster)