Theoretical Learning Performance of Graph Networks: the Impact of Jumping Connections and Layer-wise Sparsification
Authors: Jiawei Sun
Hongkang Li
Meng Wang
Venue: Accepted by TMLR ()

Abstract: Jumping connections enable Graph Convolutional Networks (GCNs) to overcome over-smoothing, while graph sparsification reduces computational demands by selecting a submatrix of the graph adjacency matrix during neighborhood aggregation. Learning GCNs with graph sparsification has shown empirical success across various applications, but a theoretical understanding of the generalization guarantees remains limited, with existing analyses ignoring either graph sparsification or jumping connections. This paper presents the first learning dynamics and generalization analysis of GCNs with jumping connections using graph sparsification.
Our analysis demonstrates that the generalization accuracy of the learned model closely approximates the highest achievable accuracy within a broad class of target functions dependent on the proposed sparse effective adjacency matrix $A^*$. Thus, graph sparsification maintains generalization performance when $A^*$ accurately models data correlations. We reveal that jumping connections lead to different sparsification requirements across layers. In a two-hidden-layer GCN, the generalization is more affected by the sparsified matrix deviations from $A^*$ of the first layer than the second layer. To the best of our knowledge, this marks the first theoretical characterization of jumping connections' role in sparsification requirements. We validate our theoretical results on benchmark datasets in deep GCNs.

Published in Transactions on Machine Learning Research (June/ 2205)
Theoretical Learning Performance of Graph Networks: the Impact of Jumping Connections and Layer-wise Sparsifica- tion
Jiawei Sun
sunj11 @rpi. edu
Department of Electrical, Computer, and Systems Engineering Rensselaer Polytechnic Institute
Hongkang Li
Sihk@seas.upenncco edu
Department of Electricol and Systems Engineering Universily of Pennsyloania
Meng Wang
mangm75rppp edu
Department of Electrical, Computer, and Systems Engineering Rensselaer Polytechnic Institute
Reviewed on OpenReview: https: // openreview. net/ htte://mnnatttt///////s/sssssssr destorrt=dddt-eeee desc
Abstract
Jumping connections enable Graph Convolutional Networks (GCNs) to overcome over- smoothing, while graph sparsification reduces computational demands by selecting sub- matrix of the graph adjacency matrix during neighborhood aggregation. Learning GCNs with graph sparsification has shown empirical success across various applications, but theoretical understanding of the generalization guarantees remains limited, with existing analyses ignoring either graph sparsification or jumping connections. This paper presents the first learning dynamics and generalization analysis of GCNs with jumping connections using graph sparsification. Our analysis demonstrates that the generalization accuracy of the learned model closely approximates the highest achievable accuracy within broad class of target functions dependent the proposed sparse effective adjacency matrix A". Thus, graph sparsification maintains generalization performance when A preserves the essential edges that support meaningful message propagation. We reveal that jumping connections lead to different sparsification requirements across layers. In a two-hiddden-layer GCN, the generalization is more affected by the sparsified matrix deviations from A" the first layer than the second layer. To the best of our knowledge, this marks the first theoretical char- acterization of jumping connections' role sparsification requirements. We validate our theoretical results benchmark datasets in deep GCNs.
1 Introduction
Graph neural networks (GNNs) outperform traditional machine learning techniques when learning graph- structured data, that comprises collection of features linked with nodes and graph representing the correlation of the features. As one of the most popular variants of GNN, Graph Convolutional Networks (GCNs) (Kipf & Welling 2017) perform the convolution operations on graphs by aggregating neighboring nodes to update the feature presentation every node. GCNs have demonstrated great empirical success al.) 2018 Zhang et al. 2018)) and rocommendation systems (Wu al.) 2019 Ying al.) 2018). Because GCNs are easy and computationally efficient implement, they are the preferred choice for large-scale graph training Duan et al. 20022 Zhang et. al. 2002
such as text. classification (Norcliffo-Brown

---

[u Xu et al. 2018b). Moreover, jumping connections Jumping connections have thus become an Published in Transactions on Machine Learning Research (June/ 2202))
As the depth of vanilla GCNs increases, there is tendency for the node representations to converge toward common value, phemomenon known as "over-smoothing" (Li et al. 2018). A widely adopted mitigation approach is to incorporate jumping connections, which allow features to bypass intermediate layers and directly contribute to future layers' output (Li et al. 20199;
are shown to accelerate the training process (Xu et al. 2021
essential component of GCNs.
Processing large-scale graphs can be computationally demanding, particularly when dealing with the re- cursive neighborhood integration in GCNs. To alleviate this computational burden, graph sampling sparsification methods select a subset of nodes or edges from the original graph when computing neigh- borhood aggregation. Various graph sampling approaches have been developed, including node sampling methods like GraphSAGE (Hamilton et al.) 2017), layer- wise sampling like FastGCN (Chen et al.) 2018
subgraph sampling methods like Graphsaint (Zeng et 2020p. The graph sparsífication methods (Li et al.
2020 Chen al.) 2021 You et al. 2020; Liu al. 2023) usually co-optimize weights and sparsified masks
find optimal sparse graphs and remove the task-irrelevant. edges. [loannidis et. al. (2020); Zeng et. al. (2020):
Srinivasa et al. (2020) introduce simple pruning methods that remove less significant edges without needing
complex iterative training.
Although GCNs have demonstrated superior empirical success, their theoretical foundation remains relatively underdeveloped. Some works analyze the expressive power of GCNs in terms of the functions they can represent Morris et al. (2019); Cong et al. (2021); ; Oono & Suzuki (2019); Xu et al. (2019); Chen et al. (2019), while some works characterize the generalization gap which measures the gap between the training accuracy and test accuracy [Esser et al. (2021) ;; Liao et al. (2020); Tang & Liu (2023b). All these works ignore training dynamics, i.e., they do not characterize how to train model to achieve great expressive power or a small generalization gap. Some works exploit the neural tangent kernel (NTK) technique to analyze the training dynamics of stochastic gradient descent and generalization performance simultaneously Yang ct al. (023). These analyses apply to deep neural networks, only when the network is impractically overparameteriieed i.e,, the number of neurons is either infinite Du el al. (2019a) or polynomial the total number of nodes Qin et al. (2023).
Li ct al. (2022a); Zhang et al. 2023b;; Tang & Liu (023a) analyze the training dynamics of SGD for GCNs with sparsification and prove that the learned model is guaranteed to achieve desirable generation. These analyses focus on mwo-hidden-layee GCNs, but the learning problem is already a nonconvex problem for these shallow networks. However, their network architectures exclude jumping connections. Xu et al.] (2021) investigates training dynamics of jumping connections in multi-layer GCNs, but that paper does not provide generalization results and only considers linear activation functions.
To the best of our knowledge, this paper provides the first theoretical analysis of the training dynamics and generalization performance for wwo-hidden-Bae layer GCNs with humping-connedte using graph sparsification. Our method focuses on the interaction of the jumping-commettion and the intermediate layer and explains how comping-connection influences training and graph sparsification across layers. We consider the semi- supervised node regression problem, where given all node features and partial labels, the objective is to predict the unknown node labels. Our major results include:
(1) We analyze training wwo-hidden-laye GCNs by stochastic gradient descent (SGD) with a jumping connec- tion, using pruning method that prefers the large weight edges from the adjacency matrix A. Our analysis demonstrates that the generalization accuracy of the learned model approximates the highest achievable accuracy within a broad class of target functions, which map input fcatures to labels. Each target function is a sum of a simpler base function that contributes significantly to the output and a more complicated composite function that has a comparatively smaller impact on the output. This class encompasses a wide range of functions, including two-hiddenn-layr GCNs with jumping connections.
(2) This paper extends the concept of the sparse effective adjacency matrix, denoted as A", which is first introduced in Li et al.] (2022a) for GCNs lacking jumping connections. This paper shows that A also characterizes the influence of graph sparsification in GCNs with jumping connections. We find that the adjacency matrix A of a graph often includes redundant information, suggesting that an effectively sparse graph can perform as well as or even surpass A in training GCNs. Then the goal of graph pruning shifts
2

---

Published in Transactions on Machine Learning Research (June/ 2202))
from minimizing the difference between sampled adjacency matrix, denoted by A", and A to minimizing the difference between A and A*. Consequently, even when the pruned adjacency matrix A is very sparse and significantly deviates from A, as long as there exists an A closely enough to A", graph sparsification does not compromise the model's generalization performance.
(3) This paper theoretically demonstrates that, owing to the presence jumping connections, sparsifying different layers has different impacts on the model's output. Specifically, the first layer connects directly to the output through the jumping connection, and result, the deviation of the sampled matrix from the sparse effective matrix A has more significant effect than the deviation of the second layer. In contrast, the second layer influences the output through a composite function that contributes less significantly, allowing for more substantial deviations from A" in the process without compromising error rates. To the best of our knowledge, this is the first theoretical characterization of how jumping connections influence sparsification roquirements, while previous analyses such as (Li et al.; 2022a) assume that the sparsification approach remains consistent across different layers. Besides, our experiments on the deop-layer Jumping Knowledge Network GCN, demonstrate the significant impacl of graph sampling in shallow layers compared to deeper layers. This empirical evidence supports our theoretical claims and the relevance of our two-layer model analysis in understanding doeper GCN architectures.
1.1 Related works
Other theoretical analysis of GNNs focus expressive power and convergence analysis. Xu el al. (2018a]; Morris et al. (2019) show the power of 1-hop message passing is upper bounded by 1-WL test. Feng et al. (2022); Wang & Zhang 2022) extend the analysis to k-hop message passing neural networks and spectral GNNs. Zhang et al. [2023a explores the expressive power of GNNs from the perspective of
graph biconnectivity. Oono & Suzuki (2020); Ramezani el. al. (2020); Cong et al. (2021) investigates the
optimization of GNN training.
Generalization analyses of Neural Networks (NNs). Varions approaches have been developed to analyze the generalization of feedforward NNs. The neural tangent. kennel (NTK) approach shows that overparameterized networks can be approximated by kernel methods in the limiting case (Jacot et al. 2018
Du et al. 2019b). The model estimation approach assumes the existence of a ground-truth one-hiddeen-laer model with desirable generalization and estimates the model parameters using the training data (Zhong et al. 2017 Zhang et al. 2020 Li et al., (022b). The feature learning approach analyzos how shallow
NN learns important features during training and thus achieves desirable generalization (Li & Liang 2018
Allen-Zhu & Li 2022 2023 All works ignore the jumping connection except Allen- Zhu & Li (2019) which
analyzes the generalization of two-hidden-laye layer ResNet. Our analysis builds upon Allen-Zhu & Li (019
and extends to GCNs with graph sparsification.
Various GNN sparsification methods. Node-wise sampling (Hamilton et al., 2017) randomly selects nodes and their multi-hop neighbors to create a localized subgraph. Layer-wise sampling (Chen et al.) 2018
Zou et al., 2019; Huang et al.] 2018) sample a fixed number of nodes in each layer. Subgraph-basee sampling
(Zeng al. 2020 Chiang et al.] 2019) generates subgraphs by sampling nodes and edges. As for graph sparsification, SGCN (Li et al. 2020) introduces the alternating direction method of multipliers (ADMM) to sparsify the adjacency matrix. UGS (Chen et al. 2021), Early-Bird (You et al. (0220, and ICPG (Sui
let al. 2022) design a pruning strategy to sparsify the graph based on the lottery ticket hypothesis. CGP (Liu et al. 2023) proposes a graph gradual pruning framework to reduce the computational cost. DropEdge
Rong et al. 20019) which randomly drops edges per layer during training.
2 Training GCNs with Layer-wise Graph Sparsification: Summary of Main Components
2.1 GCN Learning Setup
Let 9 = (V,E) represent an undirected graph, where V is the set of nodes with | N nodes and & is the set of edges. A is the maximum degree of G. An adjacency matrix A E RNNN is defined to describe the overall graph topology where Á(i,j) = 1 if (N,, 12) E E elsc Á(i,j) = 0. A denotes the normalized adjacency matrix with A DA + T)D-2 where D is the degree matrix with diagonal elements Dt, = E3 A(i.j)
3

---

Published in Transactions on Machine Learning Research (June/ 2002))
Each element Ai of the matrix A represents the normalized weight of the edge between nodes and j. an denotes the nth column of the matrix A. Let X E IRdxN denote the feature matrix of N nodes, where En E IRd denotes the feature of node n. Assume | = 1 for all without loss of generality. represents the label node n. Let Ω c V denote the set of labeled nodes. Given X and partial labels in Ω the objective of semi-supervised regressonn to predict the unknown labels in V Ω
E R
We consider training two-hidden-laye GCN with a single jumping connection, where the function R x R RNNN R with
out A,WU = Co
(O(U)((WAA)) CC(WXA)C
(1)
where a()) applies the ReLU activation (e)U(x) = max(z, 0) to each entry, W E Ruxd U R=x" and C *m* denote the first hidden- second hidden-layer, and output layer weights, respectively. We only train W and U. The output of the nth node can be writlen out, RdxN RR. R*
out, (x, KKAAWWUU) = Co(WWa.)) + Co(Uo((WAAja.)
(2)
We focus the & regression task and the prediction loss of the nth node is defined
Obj, (X, A, Moi W. U) = 2 -lle. - oxt, A; W; U)
(3)
The learning problem solves the following empirical risk minimization problem:
min La (WW
Σ EE
(1)
W.O
2.2 Training with stochastic gradient descent and graph sparsification
The recursive neighborhood aggregation through multiplying the feature matrix with A is costly in both computation and memory. Graph sparsification prunes the graph adjacency matrix A to reduce the compu- tation and memory roquirement. For example, one common theme of various edge sampling or sparsification methods is to retain the large weight edges Ay from the adjacency matrix A in A* while pruning small weights (Chen et al., 2018 Zeng et. al., 2020). To further reduce the computation, layer-wise sampling is also employed that uses different sampling rates in different layers, see, e.g., Chen et al. (2018).
We allow the sparsification methods with different parameter settings in different layers. Specifically, in the ith iteration, let _ and 2 denote the sparsified adjacency matrix in the first and second hidden layers, respectively.
In Algorithm 1 is solved by the stochastic gradient descent (SGD) method starting from random ini- tialization. In each iteration, the gradient of the prediction loss of one randomly selected node is used to approximate the gradient of La- Let (())) and (()) denote the current estimation of W and U. When computing the stochastic gradient, instead of (2) we use
out(X, A",,""
A wi)), (()) = (o(W()) XA") (OW
(5)
The main nolations are sunmarized in Table 1 in Appendix.
3 Main Algorithm and Theoretical Results
3.1 Informal Key Theoretical Findings
We first summarize our major theoretical insights and takeaways before formally presenting them.
1. The first thcoretical generalization guarantce of two-hidden-layer GCNs with jumping- connection. We demonstrate that training single jumping- connection -wod GCN using
If different layers use different adjacency matrices, specify both matrices the function representation. Otherwise, use matrix simplify notations.
4

---

Published in Transactions on Machine Learning Research (June/ 2202))
our Algorithm returns a model that achieves the label prediction performance almost the same the best prediction performance using a large class of target functions. We also characterize quantitatively the required number of labeled nodes, referred to as the sample complexity, to achieve the desirable prediction error. To the best of our knowledge, only Li et al. (2022a); Zhang et al. (2023b) provide explicit sample complexity bounds for node classification using graph neural nelworks, but for shallow GCNs with no jumping connection. Our work is the first one that provides a theoretical generalization and sample complexity analysis for the practical GCN architecture with jumping connections.
2. Graph sparsification affects generalization through the sparse effective adjacency matrix A". We show that training with edge pruning produces model with the same prediction accuracy as model trained on a GCN with A as the normalized adjacency matrix, iee, replacing A with A" in O. The effective adjacency matrix is first discussed in (Li et al.) 2022a), in the setup of node sampling for two-hidded sro-hidden-layer GCNs with no jumping connection, but A" in (Li et al. 2022a) is dense. We show that the effective adjacency matrix also exists for edge pruning on GCNs with jumping connection and can be sparse, indicating that the sparsified matrices can be very sparse without sacrifieing generalization.
3. Layer-wise graph sparsification due to jumping connection. We show that in the two-hidden- layer GCN with single jumping connection, the first hidden-layer learns a simpler base function that contributes more to the output, while the second hidden-layer learns a more complicated function that contributes less to the output. Therefore, compared with the first hidden layer, the second hidden layer is more robust to graph sparsification and can tolerate a deviation the pruned matrix to A without affecting the prediction accuracy. To the best of our knowledge, this is the first theoretical characterization of how jumping connections affect the sparsification requirements in different layers, while the previous analysis in Li et al. 2022a) assumes the same matrix sampling deviations for all layers.
3.2 Graph Topology Sparsification Strategy
Our theoretical sparsification strategy differs slightly from Algorithm D due to our adjustments aiming to facilitate and simplify the theoretical analysis. Nevertheless, our core concept is remaining more large- weight edges with a higher probability, while remaining small-weight edges with a smaller probability.
We follow the same assumption on node degrees as that in Li et al. (022a)). Specifically, the node degrees in can be divided into L. (I. 2 1) groups, with each group having N, nodes (1 E [r]]-. The degrees of all N; nodes in group I are in the order of di, ie., between ed, and Cd₃ for some constants C. di is order-wisc smaller than d+1, i.e., di = o(de+1).
Let pij E 10, ] (k = 1,2) denote the probability of pruming the larger entries in AB,,, i.e., the larger entries are retained with probability 1 1 - A smaller př corresponds to more conservative pruning in retaining larger entries, while larger př, corresponds to a more aggressive pruning.
Sampling procedure: Our pruning strategy operates block-wise. At each iteration, for each submatrix AB,, we retain the top entries follows:
Case (1) If i > j, cach of the top? d1 V
d, largest entrics AG in AB,, is retained independently with high probability 1 1- -t The remaining entries in AB., are retained independently with a probability of pt-
Case (2) If i S j, each of the top di largest entries Ag in AB is retained with probability 1 1- --p--- The remaining entries in An are retained independently with probability of y
Layer-wise flezibility; Although we consider a simplified sampling strategy for theoretical tractability and clarity, our framework allows pruning rates to vary across layers. This reflects the same core idea as practical layer-wist wise sampling methods Rong et al. (2019); Zeng et al. (2020): Chiang et al. (2019). Moreover, our sampling strategy differs from the thcoretical analysis Li et al. (2022a). where we adopt edge-level
Thhe values di V di and di for selecting the top largest entries in Ay are chosen to simplify our theoretical analysis. In fact, any values in these orders are sufficient for our theoretical analysis. Note that the main idea of retaining lower-degree edges with higher probability maintained in our sparsification strategy.
5

---

Published in Transactions on Machine Learning Research (June/ 2202))
Algorithm SGD with Layer-wise Sparsification (LWS)
1: Input: Graph G with normalized adjanccy matrix A, node features X, known labels in 92 step size Ta and l/e number of ilerations T, pruning rate pty and viz.
2: Initialize W (((0) C. W. - 0, Vo- =0
3: for t = 0, 1. ... T - do
4: Retain the top Q fraction of the largest entries with probability (1 - (1-y))) and retain the remaining
1 - Q1 fraction of smaller entries with probability (pl) to get Alt.
Retain the top 92 fraction of the largest entries with probability (1- (1-piz) and retain the remaining
92 fraction of smaller entries with probability (ply) to get A (91 > 92 and ply < ply).
Randomly sample from Ω
Calculate the gradient of L in 27 and update weight deviations through
OL(W.V) V) OW
W++1 < W.- The
W-V.
ØL(W.V) V) V--1 - V 7/ VV
W=W.VVV.
8: end for
9: Output: W(T) = ( + Wr, = v + VT.
sampling with layer-wise sparsification schedule, in contrast to their node-level sampling that is uniform across layers.
Degree-aware priovilization: This sampling strategy inherently favors low-degree nodes. To see this, assume for simplicity that ph < 1/2 is the same across all groups. For two groups j and j' where group j has smaller degree, i.e., dj < dy, we have di V # di #.. According to Case (1) of our sampling strategy, more entries in AB,, than those in AB, will be retained with probability 1-p while the remaining entries are kept with probability pły < 1 ply. This means that more edges between groups i and j are preserved than edges between i and Jr. This introduces structural bias toward retaining informative, low-degree connections.
To analyze the impact of this graph topology sparsification on the learning performance, we define the sparse effective adjacency matrix A where in each submatrix A
(1) if > J. the top d1 dv
/
de
largest values in AB., remain the same, while other entries are set to zero.
(2) if S. the top dj largest values AB, remain the same, while other entries are set to zero.
One can easily check from the definition that || O(1,, i.e., the maximum absolute column sum of A* is bounded by constant. Moreover, A is sparse by definition.
3.3 Concept Class and Hierarchical Learning
In the context of GCNs, a concept class represents the set of possible target functions that map node features to labels. Defining this space is essential for understanding the function approximation capability a learned GCN model and its ability to generalize to unseen data. Our theoretical generalization analysis establishes that the prediction error of the learned GCN model bounded by small constant multiple of the minimum achievable error within well-defined concept class. This implies that the model effectively approximates the optimal function within this space. When the concept class accurately captures the true mapping from node features to labels, the minimum achievable prediction error approaches zero. Consequently, the learned GCN model also attains a low prediction error. This concept class depends on the sparsified adjacency matrix A" rather than the original A. We show that as long as the sparsified matrices A' remain close to A", even when highly sparse, graph sparsification does not degrade generalization performance.
To formally describe the concept class, consider a space of target functions H. consisting of two smooth functions F and G RdxN NxN R along with constant IR+t
6

---

Published in Transactions on Machine Learning Research (June/2025)
(x) = FX- + aaa (Fa-()))
(6)
where the r-th row (r [k]) of FA- and Ga,, denoted by F² and g" RNNN x RNN - RIx,, satisfy:
(X) Σ ai ""
(7)
( Σ ag.ra g (M,TAA)
where Pg are the counts of basis functions used to construct the decompositions of F and g): 07,n, G. E [-1,1] are scalar coefficients for given r, wa E Rd and v E R are vectors with norms + for all r, priggr. R are smooth activation functions applied element-wise. ||et,all |,,,, v2
The complexitics of F and g are represented by the tuples (PF, (F, error)) and Cgg,Cc(().Cmll errro)) respectively. Cm and C, represent model and sample complexities, respectively, The overall complexity of H quantified by the tuple (pr.Pe, (F,) Cm (eror)))) C. (9, error)). The complexity of F (or 9) is determined by the most complex sub-target function among the pr (or PG) smooth functions. Specifically, the complexities for F and are defined as:
eFrrrr = max {Fm ,eroor, [|A))))) C,(F) = max (C.(F [ATb))
*;*
(8)
Cm Cm = max (m error, [|4])) C.( max (g [|A1)))))
The model and sample complexity definitions follow similarly to those in Li et al. 2022a) (Section 1.2) and
Allen-Zhu & Li (2019) (Section 4). Please see Appendix B for details.
F and 9 can both be viewed as one-hiddeen-layr GCNs with smooth activation functions and adjacency ma- trix A", The target function H. includes the base signal F, which is less complex yet contributes significantly to the target, and G, which is more complicated but contributes less. We will show that the learner networks defined in (5) can learn the concept class of larget. functions defined in 6 Intuitively, we will show that using a two-hhidden-layer GCN with a jumping connection, the first hidden layer learns the low-complexity F, and the second hidden layer learns the high-complexity G(F) with the help of F learned by the first hidden layer using the jumping connection.
We will also show that the learned GCN by our method performs almost the same as the best function the concept class in predicting unknown labels. Let Da,, and D,,, denote the distribution from which the feature and label of node are drawn, respectively. Let D denote the concatenation of these distributions. Then the given feature matrix X and partial labels in Ω can be viewed as [ identically distributed but correlated samples (X, yn) from D. The correlation results from the fact that the label of node i depends on not only the fealure of node i but also neighboring features.
The n-th column of HA' denoted Ho.A" : RR NNN + R represents the target function for node n. To measure the label approximation performance of the target function, define
E (X J.D. Hn.A- (X) - -ym = OPT
(9) OPT
as the minimum prediction error achioved by the best target function in the concept class in ( decreases when the larget functions more complex, or the concept class enlarges, if A characterizes the node correlations properly.
3.4 Modeling the prediction error of unknown labels
To simplify the analysis and representation, we re- paramettriize U and 2 as VC, where V e gmmk Then, (2) can be rewritten as follows:
out,((X A; W. V) = (X,
(X, A) + Co((V out out' (X, A)a..)
where out (X, W) Co(WXA)
(10)
out! (X, A; W) = Co
7

---

Published in Transactions on Machine Learning Research (June/ 2202))
We follow the conventional setup for theoretical analysis that C' is fixed at its random initialization, and only W and V are updated during training. C, W(O), V(0) are randomly initialized from Gaussian distributions, Ca. Lid. N (0, H. W Lid. N (0) and ViJ Ltd. N (0,,0//m) respectively.
The algorithm summarized in Algorithm 1 When computing the stochastic gradient of a sampled label Yo: the loss is represented a function of the weight deviations W, V from initiation W(() and V i.e. (11)
L(W, V) Obj, (x, A A Un: w + W, W + V).
W, and V, denote the weight deviations of the estimated weights W and V in iteration from W and v(O, ie., W W( + W,, v(() v( + V.. We assume 0 s Ö (. thronghout the training. We prove that I [Wlllg and ||&ll2 are bounded by (F,( and @ (g) during training, i.e., [Well2 s θ (C,(F)) [|Vel22
(gC, < for all I.
The following lemma shows that graph sparsification in different layers contributes to the output approxi- mation differently. In other words, to maintain the same accuracy in the output, the tolerable pruning rates in different layers are different.
Lemma 3.1. For any given constant E, if the first and second layer matrices A and A are sparsified with probabilities satisfying
VaddE N,N,C,(F))
VaddE
p/j S
ph S
(12)
then with probability at least 1 - -SEE we have
E
-A'1-1"11, S ((C,(F))
(13)
E
||420 - b(aC,
(14)
(X, A AA w(),, p()) out (X, A"; ((O), v(0) S.
(15)
Lemma 3.1 demonstrates that skip connections enable more flexible sparsification in deeper layers. To see this, note that since (G) < 1 (see Table in the Appendix), the second-layer sparsification condition in 12) permits larger values of př compared to p!y, allowing more aggressive pruning in the second layer while still satisfying the output error bound in 15 This is because the skip connection ensures that the final output aggregates features from each layer in a decoupled manner, allowing the approximation error at each layer (see (13 and (14) to be independently controlled.
We will show the learned model can achieve an error close to O(OPT). Our main theorem can be sketched follows,
Theorem 3.2. For E @0. (2.t7)) let eo = ((a
< 1 and define the target error 10 12 with E = 60. Then there erist Mo
OPT + Eo. Suppose the pruning probabilities phy, satisfy
poly (Cm((F a), (), ||A a,, To = TT- (i. such that for any 2 Mo, T 2 To, and [S No, with high probability over the random initiolization and training process, the SGD algorithm satisfiss:
C,(F)²2
No ē (A lfg -²
T
-
Σ E(X.g.)DD nEv 1lun - out, (x, A" A W., v.)
(16)
16p shows that the learned GCN achieves a prediction error no worse than e, averaged over the data distribution and training iterations. Note that when the concept class becomes more expressive, C. and C.
8

---

Published in Transactions on Machine Learning Research (June/ 2002))
increase, while the optimal error OPT decreases. According to Theorem 3.2 this leads to increase in the required the model complexity Mo (the number of neurons) and the sample complexity No (the number of labeled nodes), while the generalization error epsilon decreases. Thus, as a sanity check, our theoretical bounds match the intuition that a larger model and more labels improve the prediction accuracy.
In parallel, the pruning probabilities ply and piy are positively correlated with 60, indicating that achieving smaller generalization error requires lower pruning probabilities, ie., more conservative pruning improves generalization. Between the two, Pij is consistently larger than ply. suggesting that more aggressive pruming is permissible in the second layer while maintaining conservative pruning in the first. Morcover, No = ( N) suggests that a logarithmic number of labels suffices to generalize to the entire graph under our assumptions. Finally, as || increases, the constants Cm and C, also increase, which in turn raises Mo and No- This reflects a natural phenomenon: when the affective adjacency matrix becomes denser, the prediction task becomes harder, and generalization performance degrades accordingly.
This proof of Theorem 3.2 builds upon the proof of Theorem in Allen-Zhu & Li (2019); which analyzes the generalization of a three-layer ResNet for supervised regression problem. We extend the analysis to training GCNs with graph sparsification for a semi-supervised node regression problem. The main technical challenge is to handle the dependence of labels on neighboring features and the error in adjacency matrices duc to the sparsification. Compared with Li et al. (2022a) which also considers training GCN with graph sampling, we consider a different sparsification method from that in Li et al. (2022a). The resulting A in Li et al. (2022a) is dense matrix as A, while A in our paper is sparse matrix. Our results thus allow the sparsified matrices to be very sparse while still maintaining the generalization accuracy. Moreover, the sampling method is the same for both hidden layers in Li et al. (2022a), resulting the same deviation from A in both layers. Our results indicate that the jumping connection allows more flexible sparsification method in the second layer.
3.5 Proof Overview
In practice, for computational efficiency, we use the sparsified adjacency matrix A' in the learning network. Therefore, the discrepancy between the larget function with A and the practical learning network with A' can be viewed as two parts:
Hn,.s- out, (X, A W. V.) S (n,, (X) out, (X, A A
(17)
+ lout, (x,A't A A2t) - out, (X, A 1
the first part quantifies how well the learning network, trained with W, and V, using A", can approximate the target function Hn,a- We prove the existence of W and V (see Lemma C.3 Problem statementwith m 2 Mo, TstatementTo and Ω 2 No such that
(H..a.()) out, (X,A"; W V*)ll, 60.-
(18)
The second part quantifies the difference between the learning network's output when using the sparse adjacency matrices A and effective adjacency matrix A". Specifically, it is represented by the term:
llout, (X,A",, - -uut, (X, A2), < ||Co(W [V out (XA"))a3 - Co out (XA*)a
(19)
For the inequality [[Co()Xo))) - Co(WWatt) (C((xXX) |1, I co to hold, it is required that || - - < (t),(F) and similarly, || - A < (F)c,())
to (see Appendix C.4h. We establish that with appropriate pruning
probabilitics ply and př,, the norms A A*I and | 27 A ||] can be sufficiently small (sce Appendix
C.7
Finally, consider the definition of OPT, we can prove 1/ - out, A", W.. 1255.
9

---

Published in Transactions on Machine Learning Research (June/ 2025))
4 Empirical Experiment
4.1 Experiment on synthetic data
We generate graph with N 2000 nodes. Given A, the sparse A is obtained following the procedure in Section
3.2 The node labels are generated by the target function
(X) = CW"XA, (F (X)) = C (sin FA' o tanh (x)A))
(20)
H.. (X) = FA- (X) + 09 (Fx-
where X E R W E gxd V* E R and C' e Rixr are randomly generated with each entry i.id. from No,, 1). d 100, 5, = 30, a = 0.5. A two-hidden-layer GCN with a single jumping connection as
defined in 2 with m neurons in each hidden layer is trained on a randomly selected set of labeled nodes. The rest N labels are used for testing. The test error is measured by the & regression loss in 33)
2.6
2.6
2.4
2.2
Test error
2.2
1.8
2.0
Hidden Ncurons-10 10
Labeled Nodes-400 Labeled Nades=800 Labeled Nodes-1200
1.8
Hidden Neurons-20
1.4
1.6
Hidden Neurons-50
1.0
1.2
1.4
1.6
1.8
2.0
1.2
1.4
1.6
1.8
2.0
[|A 111
[|A 111
(a)
(b)
Figure 1: Experiment on two-degree group synthetic data: To achieve the same test error, if [|A* is larger, (a) then the number of neurons m larger (when [2t] 1200 is fixed); (b) then the number of labeled nodes is larger (when = 50 is fixed).
How ||A*|] impacts model and sample complexities: In Figures 1 G has two-degree groups. Group has N₁ = 200 nodes, and the degree of each node follows a Gaussian distribution N (d1.o²). Group 2 has N₂ = 1800 nodes, and the degree of each node follows a Gaussian distribution N (d2,0²) The degrees are truncated to fall within the range of 0 to 500. We vary A by changing d2 and the corresponding A We fix d1 200 and
We directly train with A" study the impact of A on model and sample complexities. In Figures [ (a), [S2] = 1200 and the number of neurons per layer m varies. To achieve the same test accuracy, when || increases, the number of neurons also increases, verifying
model complexity Mo in Theorem 3.2 In Figures (b), m 50 and [X] varies. To achieve the same test accuracy, when || increases, the required number of labcls also incrcases, verifying our sample complexity Ng in Theorem 3.2
In Figures has one-degree groups and the degree of each node follows a Gaussian distribution N d = 200. The degrees are truncated to fall within the range of 0 to 500, We vary A" by changing a and the corresponding A. We directly train with A" to study the impact of A on model and sample complexities. In Figures (a), |S|| 1200 and the number of neurons per layer varies. Fig. 2 (a) shows the testing error decreases verifies our model complexity in Theorem 3.2 In Figures 2 (b), = 50 and [S]] varies. Fig. 2 (b) shows the
N (d, o2).
increases. When is the same, the testing error increases as ||A*|| increases. This
testing error decreases as Ω increases. When Ω is the same, the testing error increases as A increases.
This verifies our model complexity in Theorem 3.2
Layer-wise Sparsification impact generalization: We fix Ω 1200,
50, || 1.27. We sample adjacency matrices during training. Figure 3 shows the relationship between the test error and the average deviation of sparsified matrices (At and 2 in the first and second hidden layers) from A". We can see that pruning in the second hidden layer (blue dashed line) contributes to generalization degradation much milder than pruning in the first hidden layer (green solid arrow). This verifies our Lemma 3.1 that the sparsification requirements are more restrictive in the first layer than the second layer maintain the same generalization accuracy.
10

---

Published in Transactions on Machine Learning Research (June/2025)
2.0
2.0
1.8
166
1.2
1.4
10
1.2
|| -100
0.8
10'
10
400
800
1200
Total number of hidden neuron
Total number of labeled noces
(a)
(b)
Figure Experiment on one-degree group synthetic data: (a) Test error with [St] 1200. (b) Test error with 50. The test error increases ||*|| increases while others remain the same.
2D Heatmap of Test Error
4.0
3.0
2.0
2.0
EnD
1.9
1.8
1.7
1.0
4.0
4.0
1.7
1/42
2.0
2.0 ave
l1
8.00
1.0
2.0
3.0
4.0
4
111
00
BIA
||4
(b)
(a)
Figure 3: Experiment synthetic data of layer-wise sparsification. (a) Sampling in the first hidden layer affects the test performance more significantly than the second hidden layer. (b) 2D heatmap of test error.
4.2 Experiments on Small-scale Real Datasets
Retaining large weights in the graph perform well trained sparse graph methods. We applied Algorithm [ to one-hidden-layer shallow GCN on small-scale datasets (Cora, Citesper) for node multi-class classification tasks, comparing it with state-of-the-art (SOTA) sparsification methods such as CGP (Liu et al.] 2023) and UGS (Chen et al.) 2021). For these small datasets, multi-layer GCNs are not necessary, so we employ the one-hidden-layer GCN KKipf Welling 2017) with 512 hidden neurons and proclude the use of different pruning rates for shallow and deep layers. We retain the top g fraction of the largest. edge weights with 99% probability and retain the remaining 1 -q fraction of small weight with 1% probability to get A", so the sparsify of our method (LWS) is 0.98g 0.01 and we vary from 0.01 to 1.0. In Figure 4 we only demonstrate that retaining large-weight edges from A using our method can achieve performance comparable to that of trained sparse graphs produced by SOTA methods.
0.84
Cora
0.72
Citeseer
0.80
0.76
Test Accuracy
0.68
0.72
0.64
0.68
0.64
LWS
LWS
0.60
UGS
UGS
0.56
0.56
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4 0.6
0.8
1.0
Sparsity
Sparsity
(b)
Figure 4: Experiment sparsifying shallow GCN models.
11

---

Published in Transactions on Machine Learning Research (June/2025)
4.3 Experiments on Large-scale Real Datasets
We also evaluate multi-layer GCNs with jumping connections on the large-scale Open Graph Benchmark (OGB) datasets for node multi-class classification tasks. A summary of Ogbn datasets' statistics is presented in Table 2 in Appendix. While our theory does not explicitly model dropout or normalization, we follow standard practice and include them in real-data experiments, where the theoretical insights remain valid.
The task of Arxi- is to classify the 40 subject areas of arXiv CS papers. We use 60% of the data for training, 20% for testing, and 20% for verification. We deploy an 8-layer Jumping Knowledge Network (Xul ct al. 2018b) GCN with concatenation layer aggregation as a learner network. We treat the first four layers as shallow layers and the last four layers as deep layers. Shallow and deep layers are sparsified differently. The generalization is evaluated by the fraction of erroneous predictions of unknown labels.
Pruning in deep layers is more flexible with less generalization degradation. In this experiment, we employ simplified version of the graph sparsification method discussed in Section 3.2 For the shallow layers, at each iteration t, we obtain a sparsified adjacency matrix A as follows: we retain the top qı fraction of the largest weight odges As from the adjacency matrix with 99% probability, and retain the remaining entries with a 1% probability. For the deep layers, the sparsified adjacency matrix A is generated similarly, but and 1% for the top and remaining entries, respectively.
the top 92 fraction of largest Aij, again retaining with probabilities of 99%
Figure showss test error when 91 and 92 vary. One can see that the test error decreases more drastically when only increasing ? (blue dashed arrow) compared with only increasing d2 (green solid arrow), indicating that graph pruning shallow layers has a more significant impact than graph pruning in deeper layers. When both yi and do are greater than 0.6, the test error is always small (less than 0.29) for a wide range of qı, l2. That may suggest the existence of multiple sparse A such that sparsified matrices A' with different qı 92 pairs approximate different A", and all A accurately represent the data correlations in the mapping function from the features to the labels.
Test Emo ag
0..4
0.42
0.35 vol0
0.38
0.30
0.34
deep layers da
0.2
10 0,6 0,2 shallow layers a
shallow layers 5
0.5
0.5 deep layers 52
0.6
0.25
0.25
0.0
0.0
(b)
Figure 5: Learning deep GCNs on Ogbn-Arxiv: (a) Deeper layers tolerate higher sampling rates than shallow layers while maintaining accuracy. (b) 2D heatmap of test error rate.
Leigh-weight edges are more influential on generalization than small-weight edges. Note that if nodes and j have higher degrees, then Ay has a smaller value. We sparsify one matrix for the shallow layers by keeping the values of Aij that are in the range of top to + 0.5 fraction and set seiling all other values to zero. Similarly, we sparsify one matrix for the deep layers by keeping the values in the range of top 82 to $2 0.5 fraction and setting all other values to zero. These two sparsified matrices are used during training. When 81 and $2 increase, the resulting matrices have the same number of nonzero entries, and the sparsified entries focus more on high-degree edges. Figure i shows the test error indeed increases as 81, 82 increases. This justifies the sparsification strategy retain more large-weighn edges.
For the Ogbn-Products datasot, we deploy a 4-layer Jumping Knowledge Network (Xu et al. 2018b) GCN with concatenation layer aggregation. Each hidden layer consists of 128 neurons. We define the first two layers shallow layers and the last two layers as deep layers with sampling rate p2- The task is to classify
12

---

Published in Transactions on Machine Learning Research (June/ (202))
fraction
0.50
Heatmao Test Error Rate
0.42
soon
0.38
tato
0.34
0.36
shallow layers 5
shallow
0.34
0.25
deep layers
0.25
0.00
0.25
0.50
0.0
0.0
deep layers starting fraction
(b)
(a)
Figure 6: Learning deep GCNs on Ogbn-Arxiv: (a) Retaining more large-weight. edges (small 81, 82) outper- forms retaining more wnigh- edges (large $1, 82). (b) 2D heatmap of test error rate.
the category of a product a multi-class, where the 47 top-level categories are used for target labels. We use 60% of the data for training, 20% for testing, and 20% for verification.
We run the similar experiment as Figure for Ogbn-Products dataset. We fix q1 0.1 and vary Ø from 0.1 to 1.0 at increments of 0.1, then fix 92 0.1 and vary 91 from 0.1 to 1.0 at increments of 0.1. 7 that with the increasing sampling rate in shallow layers, the test accuracy is higher than the test accuracy with the increasing sampling rate in deep layers. It suggests that the generalization is more sensitive to the sampling in the shallow layers rather than deep layers, consistent with observations in other datasets.
0.76
Test Accuracy
0.74
0.72
fix
0.1
0.70
fix 0.1 vary
0.4
0.6
1.0
Sampling
Figure 7: Layer-wise Sampling Rate Effect on Ogbn- Products
5 Conclusion and Future Work
This paper provides a theoretical generalization analysis of training GCNs with skip connections using graph sampling. the best of our knowledge, this paper provides the first analysis of how skip connection afTects the generalization performance. We show that for two-hidden-layer GCN with skip connection, the first hidden layer learns simpler function that contributes significantly to the output, making the choice of sampling more crucial in the first hidden layer. In contrast, the second layer learns composite function that contributes less to the output, allowing for a more flexible sampling approach while preserving veneralization This insight is verified on deep GCNs on benchmark datasets. Our analysis provides a general guideline: apply conservative sparsification in shallow layers to preserve local neighborhood information, and more aggressive pruning in deeper layers, especially when skip connections are present, to balance expressiveness and efficioncy.
Future work includes extending analysis to other graph neural networks and practical architectures. For example, our framework could be adapted to teatooltepporal GCNs by incorporating temporal edges into the sparsified adjacency matrix. Extending the analysis to attention-based models such as Graph Attention Networks (GATs) and Graph Transformers is another exciting direction, though it would require new tools to characterize dynamic attention mechanisms and global message passing. Our insight of layer-wist decou- pling via skip connections naturally extend to deeper GNNs, though formalizing these insights in very deep architectures may require additional tools to handle cumulative sparsification effects and complex nonlin- ear interactions. Additionally, understanding the interplay of skip connections with practical components
13

---

Published in Transactions on Machine Learning Research (June/ 2025))
such dropout and normalization layers remains open problem, these mechanisms introduce distinct theoretical challenges due to their stochasticity and feature-resoaling effects.
References
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? Advances in Newral Information Processing Systems, 32, 2019.
Zeyuan Allen-Zhn and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In 2021 IEEE 62nd Annual Symposium Foundations of Computer Science (FOCS), pp. 977-988. IEEE, 2022.
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self- distillation in deep learning. In The Eleventh International Conference on Learning Represenlations, 2023. URL
Jianfei Chen, Tianyi Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations (ICLR), 2018.
Ting Chen, Yidan Sui, Xiaohan Chen, Anima Zhang, and Zhihua Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning, pp. 1695-1706. PMLR, 2021.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
On the equivalence between graph isomorphism
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. Tn Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 257-266, 2019.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936 9949, 2021.
Simon S. Du, Keyulu Hou, Ruslan R. Salakhutdinov, Barnabás Póczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, pp. 5724-552 5734, 2019a.
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations (ICLR), 2019b.
Keyu Duan, Zirui Liu, Peihao Wang, Wenqing Zheng, Kaixiong Zhou, Tianlong Chen, Xia Hu, and Zhangyang Wang. comprehensive study on large-scale graph training: Benchmarking and rethinking. Advances in Newral Information Processing Systems, 35:5376 5389, 2022.
Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar, Learning theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Information Processing Systems, 34: 27043 27056, 2021.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. Advances in Neural Information Processing Systems, 35:4776-411 17766--790, 2022.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph repre- sentation learning. In Advances in Newral Information Processing Systems, pp. 4558 4558-4567, 2018.
Vassilis N Ioannidis, Siheng Chen, and Georgios B Giannakis. Pruned graph scattering transforms. In
International Conference on Learning Representations, 2020.
14

---

Published in Transactions on Machine Learning Research (June/ 2005))
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural works In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Leurving (ICLR), 2017.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as enns?
Tn Proceedings of the TEEE/CVE international conference on computer vision, pp. 9267-9276, 2019.
Hongkang Li, Meng Wang, Sijia Liu, Pin- Yu Chen, and Jinjun Xiong. Generalization guarantee of training graph convolutional networks with graph topology sampling. In International Conference on Machine Learning (ICML), pp. 13014 13051. PMLR, 2022a.
Hongkang Li, Shuai Zhang, and Meng Wang. Learning and generalization of one-hidden-layer neural net- works, going beyond standard gaussian data. In 2022 56th Annual Conference on Information Sciences and Systems (CISS), pp. 37-42. IEEE, 2022b.
Jundong Li, Ting Zhang, Hanghang Tian, Shengnan Jin, Mingyi Fardad, and Reza Zafarani. Sgen: A graph sparsifier based on graph convolutional networks. In Pacific- Asia Conference on Knowledge Discovery and Data Mining, pp. 275-287, Springer, 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data, Advonces in neural information processing systems, 31, 2018.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2020.
Chnang Liu, Xueqi Ma, Yibing Zhan, Liang Ding, Dapeng Tao, Bo Du, Wenbin Hu, and Danilo P. Mandic. Comprehensive graph gradual pruning for sparse training in graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAT conference on artificial intelligence, 2019.
Will Norcliffe- Brown, Stathis Vafeias, and Sarah Parisot. Learning conditioned graph structures for inter-
pretable visual question answering. Advances in neural information processing systems, 31, 2018.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classifi- cation. arXiv preprint arXiv:1905.109, 2019.
Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Advances in Neural Information Processing Systems, 33:18917-18930, 2020.
Lianke Qin, Zhao Song, and Baocheng Sun. Is solving graph neural tangent kernel equivalent to training graph neural network? arXiv preprind ar arXim:2309.0714 07452, 2023.
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Anand Sivasubramaniam, and Mahmut Kandemir. Gen meets gpu: Decoupling "when to sample" from "how to sample". Advances in Neural Information Processing Systems, 33:18482 18492, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. arXiv preprint or Xiv: 1907. 10903, 2019.
15

---

Published in Transactions on Machine Learning Research (June/ 2025))
Rakshith S Srinivasa, Cao Xiao, Lucas Glass, Justin Romberg, and Jimeng Sun. Fast graph attention networks using effective resistance based graph sparsification. arXiv preprinl or arxi:20006.8870 2020.
Yiding Sui, Xiaojie Wang, Ting Chen, Xiaoqiang He, and Tat-Seng Chua. Inductive lottery ticket learning for graph neural networks. In International Conference on Learning Representations (ICLR), pp. 1-18, 2022.
Huayi Tang and Yong Liu. Towards understanding the generalization of graph neural networks. In Fortieth International Conference on Machine Learning (ICML), 2023a.
Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In International Conference on Machine Learning, pp- 33674-33711 PMT.R, 2023b.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International
Conference on Machine Learning, pp. 21341-23362. PMLR, 2022.
Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Peng He, Paul Weng, Han Gao, and Guihai Chen. Dual graph attention networks for deep latent reprosentation of multifaceted social effects in recommender systems. In The world wide web conference, pp. 2091-2102, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. -463-5462. PMLR, 2018b.
Keyulu Xu, Wei Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
Keyulu Xu, Mengshi Zhang, Stefanie Jegelka, and Kenji Kawaguchi. Optimization of graph neural net- works: Implicit acceleration by skip connections and more depth. In International Conference on Machine Learning (ICML). PMLR, 2021.
Chenxiao Yang, Qitian Wu, David Wipf, Ruoyu Sun, and Junchi Yan. How graph neural networks learn: Lessons from training dynamics. In Forty-first International Conference Machine Learnáng, 2023.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974-983, 2018.
Haoxiang You, Changxiao Li, Pengcheng Xu, Yonggan Fu, Yang Wang, Xiaohan Chen, Richard G. Baraniuk, Zhihua Wang, and Yingyan Lin. Drawing carly-bird tickets: Toward more efficient training of deep networks. In International Conference on Learning Represenlations (ICLR), 2020.
Hongyang Zeng, Hongyuan Zhou, Abhay Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference Learning Representa- tions (ICLR), 2020.
Bohang Zhang, Shengjic Luo, Liwci Wang, and Di Hc. Rethinking the expressive power of gnns via graph biconnectivily. In The Eleventh International Conference on Learning Representations, 2023a.
Shuai Zhang, Meng Wang, Pin-Yu Chen, Sijia Liu, Songtao Lu, and Miao Liu. Joint edge-model sparse learning is provably efficient for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b. URL https://oppeneevier
Sijia Zhang, Mengqi Wang, Shichao Liu, Pin-Yu Chen, and Jinjun Xiong. Fast learning of graph neural networks with guaranteed generalizability: One-hidden-layee case. In International Conference on Machine Learning, pp. 11268 11277, 2020.
16

---

Published in Transactions on Machine Learning Research (June/2025)
Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. Graph attention multi-layer perceptron. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 4560 4570, 2022.
Yuhao Zhang, Peng Qi, and Christopher D Manning. Graph convolution over pruned dependency trees improves relation extraction. arXiv preprint arX1v:180.11015, 2018.
Kai Zhong, Zhao Song, Prateek Jain, Peter Bartlett, and Inderjit S Dhillon. Recovery guarantees for one- hidden-layer neural networks. International conference on machine learning, pp. 4140-4149. PMLR, 2017.
D. Zou, Z. Hu, Y. Wang, S. Jiang, Y. Sun, and Q Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Advances in Newral Information Processing Systems, pp. 11249-11259, 2019.
17

---

Published in Transactions on Machine Learning Research (June/ 2025))
A
Preliminaries
We first restate some important notations used in the Appendix, which are summarized in Table |
Table 1 Summary of Notations
Notations
Annotation
G [V.E]
G is an undirocted graph consisting of set nodes V and a set edges E. The total number of nodes in a graph.
N
= D
A E NNN is the normalized adjacency matrix computed by the degree matrix D and the initial adjacency matrix Å.
A"
The effective adjacency matrix.
A",A"
The sparsified adjacency matrices in the first and second hidden layers at the t-th iteration, respectively.
Mo
The required number of neurons (model complexity).
To
The required number of itcrations for convergence in the SGD algorithm.
No
The required number of labeled samples (sample complexity).
E Ra
The weight matrix for the first hidden layer.
U E R *
The weight matrix for the second hidden layer.
C E R
The weight matrix for the output layer.
V E R mx
The re-paramcterized weight matrix used place of U in the second hidden layer.
0n E IR
The n-th column of the adjacency matrix A, representing the connectivity of node
A summary of Ogbn datasets' statistics in Table 2
Table 2: Transposed Ogbn datasets statistics.
Dataset
Ogbn-Arxiv Arxiv
Dataset
Nodes
169,343
Nodes
2,449,029
Edges
1,166,243
Edges
61,859,140
Features
128
Features
100
Classes
Classes
47
Metric
Accuracy
Metric
Accuracy
Lemma A.1. If M e Raxm is a random matrix where M,, are i.i.d. from N(O, 1). Then,
For any t 2 1, with probability - e -t it satisfies
|| S (Vn vm) +
If1 sf
loga )m then with probability 1 lotalog?ma m) satisfies
| 0 (vT+ V m ||o||2
for all s-sparse vectors E 1
Proof: The statement can be found in Proposition B.2. from Allen-Zin & Li (2019)
Lemma A.2. Suppose 8 E [0, 1] and ()) E Rh is a random vector ()) NO0, Ima) With probability at
least 1 -e -0(66229) for all vectors g' E R with llg' < 6, letting D' E gmxm be the diagonal matria where (D'),, = +g)0)) - )))0)), for each k E [m], we have
||''|lo & O(m2/3) and DD'g < 1lg'112-
18

---

Published in Transactions on Machine Learning Research (June/ 2202))
Proof: The statement can be found in Proposition B.4. from Allen-Zhi & Li (0019)
Lemma A.3. Given sampling set X - { that contains N partly dependent random variables, for each n [N], suppose is dependent with at most dx random variables in X (including In itself), and the moment generating function of In satisfies B[ean=] c for some constant C that may depend In. Then, the moment generation function of Em= In is bounded as
Ele D [n] caxNNa"
Proof: The statement can be found in Lemma 7 from Zhang et al. Lemma A.4. a S ||A||
2020
Proof:
1Xan]
Σ
Iyaknll
N
N
N
OKhn
xxll
ōk,n
(21)
k=1
ak.
|| - ||A||
Rm 1 Ok
||
Lemma A.5. FJF: Rd + R has general complenity (p. C.).F. (.() then for every sr y Rd il salisfies [F(x)]l2 I (F) ||=1| and [F(x) (F())= S (F) ||æ vlll.
Proof: The boundedness [[F(x)]l2 is trivial so we only focus on [[(()) Fly)ll2 For each component
(wi,)(a)1))
(wi,. e (xr 1)) denoting by wi as the first d coordinate of wT, and by w³, as the first d coordinates of w2yx have
g(x) = Fr,
[[2,1]ll
(wi,e (x,
g'(x) = Fri
(2x, 1)
(wi (ar, (x;,1)) 1))
wi [1( 1) (wi : (Ir, 1)) (ar, 1)/1(ar, 1)13
+ (wž (x, (x,1)) Fri
(xx,
[1x,, 1)
This implies
(1)(2))l22 S Fri. (uutte (x, (1uttc((111)))) + 2 Fr ((wi, (z, ())
)
< 3c,, (Fri)
1]12 1)]l2
As a result, [F,(z) - - s 3pC, (Fri).
Lemma A.6. For every smooth function Φ, every e (0, ((o.))o==1)) ) there exists a function : R2 Co Va + a)² 1] that is also (m, a) va" + 1-Lipschitz continuous on its first coordinate with the following two (equivalent) properlies:
(a) For every 21 E [-a, a) where a 0:
E
1 aa + Man, M(r, o(z1) sc
where on, on B1, NN are independent random variables. (b) For every w x d with (w*ll2 and ||x|| a:
E [1xx+ "",, ww)b))]] - "(w'T x)) Se
19

---

Published in Transactions on Machine Learning Research (June/2025)
where (O, is d-dimensional Gaussian, bu (0,
Furthermore, we have Ba,, (o (((an, S (C, ()(()a)))(( (a² + 11.
(c) For every w x IR with l| 11 1, let (w. E RRd11 (x, Rd+1 then we have
with ||| S va² + 1,
E Lw [ (o df q'"", wid 1DD <(w" <[w==x|1: d)) Se
where w ~ NO, Ia+1) is an d-dimensional Gaussian. We also have BwEN)O..., d] w", wid + 11]3] S a)) + 1).
Proof: The statement can be found in Lemma B.1. from Li et al. 2022a.
B Concept Class
To quantify complexity in 18 we define model complexity C. and sample complexity C, in Li et al. (022a)) (Section 1.2) and Allen-Zhu & Li 2019 (Section 4). For smooth function 6(2) = Ei= G22":
[Vlg(L//rrrr) C²R) a) Vi
2)) lal.
error R)
Σ
(C*R)'+
(22)
1=0
0C
C, R) C
Σ (i+ 11+1) 1/cbbb
(23)
where R20 0 and C is a sufficiently large constant. These two quantities are used in the model complexity and sample complexity, which represent the required number of model parameters and training samples learn & up error, respectively. Many population functions have bounded complexity. For instance, if ((2)
is exp(=), sin(z), cos(2) or polynomials of 2, then Cm(á,, O(1)) < O(poly(1/er)) //rror)) and C,())((1) 0(1).
Thus, the complexities of F and g are given by the tuples (pF, Cm) error)) and (pg, (m, F and G are composed by ps and Pg different smooth functions.
We also state some simple properties regarding our complexity measure. We define By == max, || 4- (2)22 Brog == max, ||9m,A (F (X)) for all satisfying ||>,,|| = 1. Assume G(-) is Lg Lipschitz continuous. It is simple to verify (see Lemma A.5) that B, & Vkp=C,(FF (A, IA I| Cg S VKPoC. B, [IA))) and Byog & (F, PcC, By ||^" B, [|A"]]--
C Theorem 3.2 Proof Details
Let us define learner notworks that are single-skip two-hidden-layer with ReLU activation out, RdNN x
N + & with
out, (X, A; W. V) out (X, A) + Co(V Co ox, A)a,)
(24)
and
CDw @ (X, = CD
(WXA+) E RAXN
(25)
out A) CD R
(26)
where
= [ai,
02:
aN] NNN denotes the normalized adjacency matrix.
X e RdxN denotes the the matrix of d dimension features of N nodes.
W E Rexd denotes the first hidden layer weight.
20

---

Published in Transactions on Machine Learning Research (June/2025)
Ve E Rm denotes the second hidden layer weight.
C E R denotes the output layer weight.
Dw = [1(WXa120) 1(WX2))0)
1(wxax20)) Div = (W
Dv = (( [XVon](X.
1
DV
The la loss is represented as function of the weight deviations W, V from initiation W and ((0), i.e. A Mn W
L(W, V)
W, W. V).
(27)
Let W(O W()), W,, V V + V.- We assume 0 < S 5
(G throught the training.
We prove that [Well and | are bounded by and Tv in Table during training, i.c., [Welll S Tar. V| I Tu for all t. See Appendix C.4 for the proof.
Table 3: Parameter choices
m 2 +0.01 < on S m
0.01
On @(polylog(m)
Ov
θ (FFF II)) and m à +0.001 0w I Tw S Em 0.0001 o
Tw
① (akpoC,
|| )B [1) and on (m) Tu polylog(m]]|11 <1
To
C.1 Coupling
Lemma C.1. We show that the weights after properly bounded amount of updates stay close to the initialization, and many good properties occur. Suppose that [| I Twx /V||2 S Wo from N (0, and Vo from N (0, of/mm), we have that
Diiio Dw+w. 11. {0((
Tw 2
(28)
0
2.
V
CDw4w. WXa, CDw4wo (W + Wo) Xan 10122 50
Tw
|| vkow (oowlllll))
(29)
A; S ŌŌ(T [|Al]])
(30)
4.
D - -D 00 -0
Tv (23) (
(31)
0v
CCD (X, A)a, CD (V + Vo) out' (X, A)an 1l
Vk
(32)
o.
rx) ) out (X, A)1221221
Vm
mm
6.
CD Voll2 To To T2/1/3
(33)
21

---

Published in Transactions on Machine Learning Research (June/ 2025))
7.
[C (V Vo) A)amll2 s 0 outh A)lla (|A11])
(34)
Proof:
[| - [[W]]2 [axll2 I Tw ||aalll and (Wo, Xan), NN(0, || anll a using Lemma A.2
have
Wio Dw Sw.wolle lo s0 ow ||Xanll vm || )2/3 _
(35)
2. We write CDw+w WXa w (W + Wo) Xat For the first term, | WoXanll O (o ||||| vm), so W WoXanl12 I = (Vkow [14ll1)
-CD W +
C (DW. Dw.w.) WoXap
S l|ooaalll -
For the second term, using Lemma A.2 again, we have
|l - ww. Wo $ [IWXanls S Tw ||Al|
Using Lemma A.1 for every s-sparse vector y, it satisfies |Ayll2 high probability.
< ((( m
|yl|
with have
The sparsity of the second term is
/ 2/3
||C (Dw,
WoXanlls - Ō
5i mm
|| ll S 0 Vm
va
Tw ||
|ouu (X, A)122 = CC w. WXan 1
CDW+ w. WXa, CDw++ wo (W + Wo) Xanl12- Using
||C||, $ with high probability, we have
CD w+w Xanllz S Ö(Tw |Alli)
4. Similar to 28h, ||V out (X, A),A)anll
Yo,
AA)annll (X,A)an A.2 can prove it.
To vollout((x
and (Vo out ou, A)an),
|/Oo,|/out' (xo A.)anll 2 ot), using Lemma
5. We write CD V (X, A)an -CDV V outtottttnoo AX, + C CDV.
CD (V + Vo) out A)an
DV+v)) Vo (X,
Similar to
29
we
have
||CDV v( out out'(X, (X, A)anll
s
O ( (X,) 0 ( f out' (X, (X,llalll)) (X, AJa,l)
Ō(vk/vm)
and
||C (DV. DV Vo Vo (X, A)anl1
s
δ
|| |out A)
6. From 5, is easy gel.
7. From 3, is easy get.
C.2 Existantial
Consider random function S. ((X, A); W*) (SH ((X, A); W ((X, W')) in which
5% A); W*)
def
ani (w Xan) 1 (1f0)
(36)
where W is a given matrix, T is random matrix where cach w/ is i.id from N (0, 1.) and a,, is i.i.d. from A 1).
Based on Lemma B.1. from Li et al. Lemma C.2. Given any F Rdd Rk with general complexity (p. (F (AA, (141))))))))) for A|I,, 1/e) such that if m M, then
2022a and Lemma E.1. from ?, we have
every E (0, (PAAA))) (ATE there erist M poly with high probability there a construction W (wf...., win) E mx x with
(FC, [[A]])) ||ll| and | || 5 (FDC.(F. (FA.F.III
W 2,00
(37)
Vm
22

---

Published in Transactions on Machine Learning Research (June/2025)
satisfying, for every In R and | I with probability at least - m0)(m
5x ||Al|
(38)
",, : (X, A:W*)
where (:,
and A: CD W "aa
Proof: Define w3 ErE(h) and EiEw ((r)) (vm (um] u0)0) 10) , w0t:)) w2, has the same distribution with a1 in Lemma A.6
Using Lemma A.6 have | S ([AIII)))) and using Lemma E.1. from ?, we have for parameter choice of m, with probability at least 1 - -amme (F.I)AC(
A) (X, = k
We have for each j E [m], with high probability ||/ 11 S δ
kpC. (F ). This means || S
δ (F )
As for the Frobenius norm,
W
Σ
k m=
Σ
(vm ( (w)0) ,.i.
(39)
jE/ml
jE[m]
sE(pl
Applying Hoeffding's concentration, we have with probability at least (m(mmm
Σ (r.d) (vm Wjj (0)
wi.)) / 2
S m
5E[m]
(40)
+ m/4 (C,(F, [|A[|)
S 2m,C.,FF |())))
Putting this back to (39) have | S k (F
m
Lemma C.3. Under the assumplions of Lemma C.1
(0,1) and ā (F (AAt there exist M poly (C- CyG, ((AI)) iA satisfying that for every 2 W (kpss,((F) and ||V*| Ô (ākpgC.(9)) with high probability
suppose
E EnEV.(X..WD WW W Xa, Fx A) 5 ||A]]
(41)
|CD V out A)a, abn (out'(X, (X,A), 112 < a² al (X, A)1l2 ||
(42)
8.
EnEV [ CD W"Xa, - Fx 1) - O( ||]]]
(43)
4.
CD out out'(ttt"nooo (),,)a, a9n (out' (x, () A) ||2
1/3 )
(44)
< 02
+0
|/out! (X, AA)l ||||]
To
23

---

Published in Transactions on Machine Learning Research (June/ 2025))
5.
WW END [I]CD (W" W)Xaa - (Fx(X,
(45)
Proof:
Using Lemma C.2 we can find a W satisfying || ||C W'Xa, - Fa(X, (o(xx,))l, A)ll2 small enough
with probability least - (00mmm
Using Lemma C.2 and | (X, A)an 2l2 I || (,,,,,,,,, (X)2) |All, we can casily prove it.
3. || Xanllz <
O ((] (( S ( |A |C(DD Dw. W W
Xan
O (VSTw || /mm) where 8 is the maximum sparsity of (Dw - Dwo)). Using 28 we know
8 x 0
( Tue )2/3m2/33 This, combining with 641 gives
ExeV,(X. ||CC W Xa, Fx ANI S 0² |All +0
Tiol (
= 1m/3mmm 11/33//mm 1/6
0w
(46)
5 5 (||]i)
Using 31 and V (X, s (T.ll
out, (X, |Alli) we can easily prove it.
5. Using 29 and 43
with larger enough m, can prove it.
C.3
Optimization
We write the gradient of loss function Vw Obj. (W) Vw V (b) + Vw Obj (W), where Vw Obj (W)- Vw out, A) and Vw Obj (W) VWCDBV V out ou, A)ans write its gradi- ent as follows.
Obil Ob), (W)-w" = tr(Xa, out, (X, T W') tr((yn (X, A)) A W' Xaa)
(47)
(yn - (X, A), CD W'
W' Xan)
W -W") = tr(
Oni X Xa:(yn - ox, A)) CDV+V6
(V()) CDD V)CD W')
Ir
anilyn out, (X) A)) CDDTTDDVV (V +V)+D W'Xa))
(48)
= Ir(( out, (X) Σ Ci (V() V)CD W W'aa))
= (3h. (X, CD VV V)C(DW+W, O W'XA)an)
outnlX Vv Obi, (V), VV) = -r((ou(X)aa (U,, A)) T CDV+v. V')
tr((yn (X, CDV V out(X)an) - (yo-
(49)
= (yo
(X, CDV+v, V out(())an)
Let us define f(W" = CDW4w, W'X + CDB44 (V(0) + V)C(Dw @ W'X and g(V")
CDV+v6 V (a)aa Therefore,
(Vw,v (b,, (-W V\)) (X, (W)) (V'))
(50)
24

---

Published in Transactions on Machine Learning Research (June/2025)
Claim C.4. We have that for all W and V satisfying |W]ls I Tw and V To, it holds that
VV Obj( W, V; (z) || llve oX, A)ll2 O (o. +
(51)
VVv V out (X, (1)
Tw
(52)
Proof:
VV (, V;
out (X,,,))))))
(CDW+ + CDV+v (V(U) V)CD
|aaxl2211 (X,
(53)
x +|CDD+w, CDD (V(0) + V)CD < ||A||l1bn - out, (X, A) (0.
In 53
the last incquality uses || = O and ||||2 - 1.
Obj = out (X, (Un (Un - out, (X, (X)
$ || out, (X, A)x,),,,l2111 out, (X) D
(54)
S Two || A I1y, (u,,,(X,,,,)) (1)
In 54 the last inequality uses 30 and ||O|| S 1.
Claim C.5. In the setting of Lemma C.1
we have f (W* - WV+ - V) = -n (X, A) - out, (X, A)+
Err, with
E NEV.(X
Errall2 S
E DEV.(XN.)~>D
(T |||||| + aaggl||]11) ||Hn. (X, out (X, A)]la]
(55)
0
v 14 By + a.a² ||ll ar ||A11/ LgB)
Proof: Based on the definition of f(W') and g (')), we have
I (W" W;X,a,) + +g V;X, ( CD +Wo (W* - Wa)
+ +DD (V*
+CDE+V (V()) + +V)C(DW+W. C ( W) A A)an
=CDV+V (V)) +V)C(DW+W, (W* W)XA)aa
(56)
CDW W Xa, CD V out' (X, (X, A)an
(CD WXa, + CD V
1. For the term,
$ (|CDP++ viO + +ICC22IV112 ||C(D 2 (W* w)
(0 Σ and (IF(xx)
+0 (a² (A11))
(57)
50 (l1((z) (lt (x) || +0 (022 (22114112)
together with To < polylog (m) v2.
25

---

Published in Transactions on Machine Learning Research (June/2025)
2. For the term,
A) ( a.) = CDw+ W'xa, - Fa((X,
+ +DD V out' A)an og (out (X, (X, A), an) + +ag (out) (X, A), ag (F(
(58)
The first term uses 41
the second term uses
42 and the third term uses the Lipsethiz continuity of G,
we have
0² Too Tol (1)11)) ||out,, (X,.)lll11))) 114|1
20
0.
(59)
+ ( [(X)a, (X)anl
<0 (T5) louu
(x)) (2)
||l + (aLs)) [F((()) (x) ||
o. We use 1 S T and definition of a.
3. For the & term, where the incquality uses 29 and 32
||0 - out, (x) S 0 (Ilout (1)1)) r3)
(60)
In sum, have
def f(W" w:z)+90 (V' - (F(x)+ + +o(((()) - out, (X,
Err
-
(61)
satisfy
E NEV.(X.,%)NDD
Errl|p
E NEV.(X..n.-0
(Fo ||||| + aLg |Alla)
(X. JND
x (F(()) out (X, A)I12 + O (Ilout (2) [|A]]]) +?
(62)
+ TTaā²) ||AllH)
Using (outh 1l2 S|| out ( (X, A) F(x)ll2 2| + By, we have
nxV,(X..)~>D)) |
.EV.(X..).)) >D 10 ||AlI1 + aCglIAl]i) (H(()) out, (X, A)ll2
E
+0 +/' A | By TØa² 11.112)
(63)
+ +0 (T. A|| + +LLg||AAh)) (Fo || By + aBFoa)
Using Byog S VhpgC.(G, |A]|, |1 2
< 1= 80 have
E Err
E
10 || aLgllA[I) 11H((x) out, (X,
W
(X..(X. MDD
(64)
33 |||l
By -² || aze || LgBy
Claim C.6. In the setting of Lemma C.1 if To ||A||1 S polytog(m) we have
|ouut (X, A) F,,
(X) ||, < 2 |lout (X, A) Hn, A)ll2 + aBrog + + [|A], B7)
(65)
Proof: Using 34 and [[G(F(X), a,,)l2 - BFOG we have
[out)] (X, A) Fx(x) A/ou (X, A) Hx,(,, A)]1 aBroo
(66)
+ + (To ||||,, (Ilout (X, - Fx(X, + By))
Using To |||||, small enough, we have
|oout (X, A) (x)12, s 2 22 (X, A) 10)-H,(X Hn,(X, A)112
aBrog Ō ||||| By)
(67)
26

---

Published in Transactions on Machine Learning Research (June/2025)
C.4
Proof of Theorem 3.2
Proof: Using
50
and Claim C.5 in ileration 4, we have
Ww.v Obj, (We, V.)) (W. W V, V)))
(yo out (Wa, Va), (W - -W) +V -V))
(68)
(Un out, (We, Vi), Hn.A (X) out, (W,, V2) + Err))
We also have
[W1+1 w*ll. W The Vw Obj (W,) - W'
= =| w - 2nw (Vw Obj, (W;), W, W*)
(69)
+ 1/2 V Obj,,
V1+1 V*1 = V To Vv Obj, (V)) V
= | V 2n (V Obj, (V+), V2 - V*)
(70)
1/ Vv Obj, (V.)
Using Algorithm so we have
we have W++1 W. - The Vw Obj, (We, V2) and V V, - n. Vv (W,, Vo),
Vw.V Obj, W,,, Vo). (W- W
VV)))) Vv Obj. (We, V.Il
- V
nu
Vw Obj, (W,, VOll + To 2
2
(71)
1
W
W ++1
1
1
V F
V
V
27/w
27
27p
Using Claim C.4 and change all A to A", have
O (nw =)) ||Allil,, out, (X, A²)
(72)
< 0 o 7 ||||| (11HAn, (X) - out, (X, A²)12 1iHn, (X) vnll2)
Therefore, as long as O (n + T2) < 0.1, it satisfies
4 |7 (X) out, (x,4')] <2 EEra 11 4 1 (X) - vnll2
[W - w 11
1
|| 1+1 - W 1|
+ 2nww
(73)
2nwwr
1
+ 2m
I| v
V - V
2n
After telescoping for = 001,,.., 1,
Wr.
12
Wr.
11
To
|m, (X) - out, (X, 113
Topoo
To
2T
1=0
(74)
2
0(1)
F
Errrel2 1 ||H (X) -vell2
217 To
To
To
t=0
Using O (Tu ||A||1 aLs) 5 0.1, have
T-1
W 2
| 2
Σ
E
[7n,A-(X) (X) - out, (X, Ax)A <
+ (OPT
(75)
4T
2mp T
2npTT
27

---

Published in Transactions on Machine Learning Research (June/ 2002))
where
60 θ To |A 11 + -. |1 11 BF om ||A'|| LxB²)
θ a To |A" [[ CKp (G. B3 | 11711, ||A*))1)
(76)
By ||A41) || || ||A1),)*
= = a² (g, By IA)) (1A11) Bx)))
In practice, for computational efficiency, the sampled adjacency matrix A' in the learning network, we should consider the discrepancy between the larget function and the practical output.
Hm (X) out, (X, A 12 - | Am (X) out, (X)A")
(77)
+ looun (X, ,,22t) out, (X, A
We have already considered [i out, (X, and |oout,, (X,'" ( out,, (X, A 1 S Coo (a - CoW
(78)
+ +V (X (XA' (u - Co (XA")aa)))
Using
30
we have
-oW S Tw || - Xaill2 -
|Errall2
(79)
For the above equation to hold, requires
Err:
|| -A'1-1111 s
(80)
Tw
Using ||A"|] s 011) and 34
we have
[[Co(V (XA" " out (XA')aa)) S To |oout (XA'')a - out, (XA*)a
(81)
Tw || A S ||Err,
Brr For the above equation to hold, it requires || - A-1,, <
2
Under
assumptions of Lemma
C.7 with high probability, can ensure ||A" Arl12 5
Err.
Tw
||42t A S
Ero
TuTu
Using
W F S Tw/ 10, V Tw/10 and 2 OPT + c0; we have
T
Σ
(| out, (X,A" A22 < O(e)
(82)
T
NEV
as long as T>> 2 /// +12/
Finally, we should check |/lll T and ||Vellr 5 hold.
WI. W
Vr. V-
W 2
Talll |= VTo
<
F + +(e) + +
(83)
2m. To
2n
2o
Using the relationship
T
Iu no
have
7u
Ta
W|
1
+ 0.1 - δ The ||A* (1 To
(Thull
(84)
72
+3
28

---

Published in Transactions on Machine Learning Research (June/2025)
Therefore, choosing ②
TA-ll ((TTTh, min
F and The (1min(1,1) S 0.1, we can ensure
[ l
Vv l 1 1.
C.5 Graph sampling
Lemma C.7. Given graph G with the minimum degree 8(G) 2 1
Tw Brrs
), in iteration i, for the forst layer
A is generated from the sampling strategy with the sompling probability plj S O d:dd (idylllrill)) and for the nisTu
second layer A is generated from the sampling strategy with the sampling probability přj S 0 (ddd d.d, ( we have
ToyT
Pr A - -A'l,, s o ) c -
Err:
(4d (dds//ww)
(85)
Tw
Pr | A s S0(
Err
S e
-(rlErr 112 //d///////// -
(86)
Tw Tv
2
Proof: The difference between Als,, and Als,, is
AB. = AlB., AB.,)
= Σ
(ats - aij)
(87)
1=1
where Mi is the number of elements in AB,, and (al, aij) are iid, with My E[AB.,] niyPis Va.d, The Moment-genorating function of (aly - -a,)) is
Mía -tz) (s) l -6o)
e vaii Psj + (1 - Pij)
(88)
l (eViros -1)
eap (evārs S
Thus, for any 8 0, using Markov's inequality and the definition of MGF, we have
I M(a (s)
P(AB, 2 k) s min
$50
ek
(89)
PV ddd,d
d,dy
c ( -1)
min
t50
etk
O < 6y S 1, we plug in kis = (1 + 6:y)u and the optimal value of 8ij = /did, In(1 + esy) to the above
equation:
e
Mi v d,d,
2ylli /did dadg
P(AB, 2 2(1+ (1+))))miss+ <
(1+ (1-
exp
(90)
(1 + (1)(1)) = =epp((1 + (n + 5;y1]
82
83
53
83
(91)
= -erp(6.5 +
o( 2 erp(6.
+
2
6
2 6
29

---

Published in Transactions on Machine Learning Research (June/2025)
Let dig 1, Maj (Err)), and d, 2 ( Brr,), ) have Pij S O Vaid,Ery )
nty
C.6 Sample Complexity
Lemma C.8. Given graph G with [V(G) = N, if the marimum degree A(G) & O((Ne)))
and sample complerity Ω 2 O A (ral All, 1l ), with probability N- Alw, we have
E
I1yn out, AX 112 neVi(Xin)WD 1l - out Ax , Se. ,
Proof: For the set of samples Z define
1 2
E
Un out, (X, ,
Σ
Un
out, (
,120)112
(92)
nEV.(X.a)~Z
5 n=
Denote the generalization error as
nEv, (X. MZ Un out, (X, At , A22 nEV.(X.,.)D
E
1l1, out, (x, A" A120) l|2
nEV.(NN ouutn (x, " AA2)) AA"
E
nEV.(X...>D |/out (x, A" AA²') 1|2
By Hoeffding's inequality and (X, an)ll I (Tw ||lli) have
(X, 122) WEV. lou (x.A, E e n
<
(93)
Define maximum degree of G is AGG). It is easy to know that |oout, (X, ( most its second order neighbor, so the maximum number of nodes related with |oout, (X, A ll2 is AG)). By Lemma in Shuai, we have
ll2 is dependent with
Ee (X." < (104)1
(94)
E lout, (x, A22 "
E
oouu, (X AAt)
)12 2c)
nEV,(X, 122
(95)
Sexp (A(G)?(ST, |1A1) scl2)
Let == 11 and c= (Tw 2
AoG) ft
Be, lout, (X, :
Nouun (x, ( 112 2c
nEV.(X.v.)DD
(96)
sexp (-(Tw|lAA]a 2 N)
S -
with
Ω O AG)) [AI1)) 2 log N
(97)
2
30


Reviews:
[{"review_id": "FRunFwB8ZP", "reviewer": "Reviewer_gBfU", "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- The paper analyzes GCNs taking different graph sparsification schemes across layers and additive jumping knowledge into account, which to my knowledge seems novel and interesting.\n- The experiments are well-designed and are comprehensive in assessing performance w.r.t. the parameters discussed in the analysis.\n\n**Weaknesses**\n\n- Some writing issues, see below.\n- Allowing for different sparsification methods at different layers seems impractical since, in the vast majority of cases, the adjacency matrix in a real-world application is fixed.\n- The trends confirmed by the experiments are generally relatively weak. For example, the observation that test error decreases as $m$ increases is very expected, and there is no close study to see how closely the empirical results match the bounds found in the theoretical results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work is the first to pose a theoretical analysis of 2-layer GCNs with jumping knowledge connections and graph sparsification as well the interplay between these two components. Importantly, the authors analyze the model in terms of its training dynamics, generalization accuracy, and sample complexity, unlike other works that work in highly overparametrized settings. Their theoretical results are supported by experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Besides addressing the above weaknesses, here are some requested changes.\n\n- There are a number of writing errors. E.g. \"column of the A\", \"between sampled adjacency matrix\", \"$\\mathcal V/\\Omega$\" should be $\\mathcal V \\setminus \\Omega$, \"allow the sparsification methods\", \"Specifically, In\", etc. A proofread would be helpful.\n- Can the authors clarify why Lemma 3.1 \"reveals that the juimping connection allows for a more flexible sparsification strategy in deeper layers\"? Generally, it's not evident to me why these results are only applicable to JK networks.\n- Can the authors comment on the impact of factors commonly used in GCNs not explicitly considered in this work, such as the use of dropout/normalization layers?\n- Do the authors have general rules of them that they would recommend for practitioners regarding how to choose sparsification parameters or how to prune their graphs?\n- Can the authors state clearly how the sparsification framework in Li et al. differs from the one in this work? I understand Li et al. assume the same sparsification across different layers, but is there anything else?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "e2nHw2ZBQz", "reviewer": "Reviewer_TAyZ", "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\n1. This paper provides the first theoretical analysis on how the jumping connections and adjacency matrix sparsification would affect the performance of the model.\n\n2. The proposed theoretical analysis is also accompanied with empirical validation.\n\nWeakness:\n\n1. The theoretical part is still a bit hard to understand. It would be better if the authors can provide a intuitive explanation on the theoretical results for facilitating understanding. For example, what is the intuitive idea behind 'adjacency matrix accurately models the data correlation'.\n\n2. The targeted problem actually correlated more to the deep GNNs on large and complex graph data. However, the experimental data used in this work are limited to very small graph datasets like cora and citeseer.", "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 investigates two common techniques in graph neural networks, jumping connections and layer-wise sparsification. These two techniques are used for reducing the over-smoothing and computational overhead.\n\nThe findings of the paper can be summarized:\n\n1. With properly sparsified adjacency matrix that accurately models the data correlations, the generalization ability of the model can be preserved.\n\n2. Jumping connections will lead to different sparsification requirements.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please discuss whether the proposed method can be extended to more graph neural networks beyong GCNs. For example, gat [1], and graph transformers [2] are also widely used graph neural networks. \n\n2. Please discuss whether the proposed method can be applied to GCNs over spatial temporal graphs [3,4]. Can those temporal edges be treated similarly like the spatial edges?\n\n[1] Graph Attention Networks\n\n[2] Graph Transformer Networks\n\n[3] Context aware graph convolution for skeleton-based action recognition\n\n[4] Inception Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XzEW18kPuW", "reviewer": "Reviewer_h3PQ", "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 results are novel. This paper extends prior works to introduce the first theoretical analysis of the training dynamics and generalization performance for two-hidden-layer GCNs with jumping-connection using graph sparsification.\n\nWeaknesses:\n1. The theoretical analysis is currently limited to two-hidden-layer GCNs. The applicability of these insights to deeper GCN architectures remains largely speculative beyond the presented empirical evidence.", "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 provides a novel theoretical analysis of GCNs with jumping connections and graph sparsification. The authors fill a theoretical gap by analyzing how jumping connections influence the generalization performance when combined with layer-wise graph sparsification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Include a discussion addressing how the insights from the two-layer theoretical framework could potentially generalize to deeper networks (like the GNNs presented in this paper [1]), highlighting clearly any potential limitations or necessary adjustments.\n\n[1] Li, Guohao, et al. \"Training graph neural networks with 1000 layers.\" International conference on machine learning. PMLR, 2021.", "broader_impact_concerns": "This paper is quite theoretical, and it's unclear how it would directly impact broader areas beyond the GNN literature.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work provides a theoretical analysis of two-layer Graph Convolutional Networks (GCNs) with jumping knowledge connections and graph sparsification. It studies both the training dynamics and generalization performance of such networks. The theoretical results are solid and offer valuable insights into the role of jumping connections in determining sparsification requirements. Experimental results are also presented to support the theoretical findings. While the class of networks studied is somewhat limited, as noted by one reviewer, the theoretical analysis necessarily relies on certain assumptions. Nonetheless, the insights gained have the potential to inform broader classes of graph neural network architectures.
Decision: Accept (poster)