On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks
Authors: Junwei Su
Chuan Wu
Venue: ICML 2025 poster (2025)
Keywords: learning theory
graph neural network
graph learning
Primary area: social_aspects->accountability_transparency_and_interpretability
TL;DR: This paper analyzes effect of graph structure on learning algorithm for graph neural network

Abstract: This paper studies the interplay between learning algorithms and graph structure for graph neural networks (GNNs). Existing theoretical studies on the learning dynamics of GNNs primarily focus on the convergence rates of learning algorithms under the interpolation regime (noise-free) and offer only a crude connection between these dynamics and the actual graph structure (e.g., maximum degree). This paper aims to bridge this gap by investigating the excessive risk (generalization performance) of learning algorithms in GNNs within the generalization regime (with noise). Specifically, we extend the conventional settings from the learning theory literature to the context of GNNs and examine how graph structure influences the performance of learning algorithms such as stochastic gradient descent (SGD) and Ridge regression. Our study makes several key contributions toward understanding the interplay between graph structure and learning in GNNs. First, we derive the excess risk profiles of SGD and Ridge regression in GNNs and connect these profiles to the graph structure through spectral graph theory. With this established framework, we further explore how different graph structures (regular vs. power-law) impact the performance of these algorithms through comparative analysis. Additionally, we extend our analysis to multi-layer linear GNNs, revealing an increasing non-isotropic effect on the excess risk profile, thereby offering new insights into the over-smoothing issue in GNNs from the perspective of learning algorithms. Our empirical results align with our theoretical predictions, \emph{collectively showcasing a coupling relation among graph structure, GNNs and learning algorithms, and providing insights on GNN algorithm design and selection in practice.}

On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks
Junwei Su
Chuan Wu
Abstract
algorithm design and selection in practice.
This paper studies the interplay between learning algorithms and graph structure for graph neural networks (GNNs). Existing theoretical studies on the learning dynamies of GNNs primarily foeus on the convergence rates of learning algorithms under the interpolation regime (noise-free) free)) and of- fer only crude connection between these dynam- ics and the actual graph structure (e.g., maximum degree). This paper aims to bridge this gap by in- vestigating the excessive risk (generalization per- formance) of learning algorithms in GNNs within the generalization regime (with noise). Specifi- cally, we extend the conventional settings from the learning theory literature to the context of GNNs and examine how graph structure influ- ences the performance of learning algorithms such as stochastic gradient descent (SGD) and Ridge regression. Our study makes several key contribu- tions toward understanding the interplay between graph structure and learning in GNNs. First, we derive the excess risk profiles of SGD and Ridge regression in GNNs and connect these profiles to the graph structure through spectral graph the- ory. With this established framework, we further explore how different graph structures (regular vs. power-law) impact the performance of these algorithms through comparative analysis. Addi- tionally, we extend our analysis to multi-layer lin- ear GNNs, revealing an increasing non-isotropic effect on the excess risk profile, thereby offer- ing new insights into the over-smoothing issue in GNNs from the perspective of learning algorithms. Our empirical results align with our theoretical predictions, collectively showeasing a coupling relation among graph structure, GNNs and learn- ing al algorithms, and providing insights on GNN
1. Introduction
Graph structure data is ubiquitous in the real world and many important learning problems are naturally modelled as a graph. Graph neural networks (GNNs) have emerged as a dominant class of machine learning models specifically designed for learning problems in graph-structured data. They have demonstrated considerable success in addressing wide range of graph-related problems in various domains such as chemistry (Gilmer et al., 2017; Reiser et al., 2022), biology (Tsubaki et al., 2019; Réau et al., 2023), social networking (Chen et al., 2017: Sheng et al., 2024; Li et al., 2017: Su et al., 2024), and computer vision (Zhu et al., 2022: Yang al., 2022; Lu al., 2016; Xu et al., 2017; Zellers et al., 201 8). A defining characteristic of GNNs is their use of spatial approach through message passing on the graph structure for feature aggregation. This enables GNNs to preserve structural information and dependencies from the underlying graph structure, allowing them to be highly effective in tasks such as node regression.
Because of their central role in numerous important applica- tions, there is growing body of literature on theoretical re- search on GNNs (see Sec. 2 for more detailed discussion). Existing theoretical studies on GNNs primarily concentrate on two aspects: their expressive power (Xu et al., 2018) and generalization capabilities under different measures. The expressive power of GNNs refers to their ability to dis- tinguish between different graph structures and effectively capture node relationships and graph topology. General- ization capabilities are often explored through complexity measures, such as VC-dimension (Scarselli et al., 2018) and Rademacher complexity (Lv, 2021), or through information- theoretic measures, like mutual information and entropy. These results provide interesting insight into how powerful GNNs are as neural model.
Sccool of Computing and Data Science, University of Hong Kong. Correspondence to: Junwei Su <jun- weisu www.ueoooonneecuuu........ Chuan Wu <ww.@cs..ku....
Existing Gap. Nevertheless, there is notable gup in understanding the interplay between learning algorithms (e.g., stochastic gradient descent (SGD)) and graph struc- ture, especially when concerning their generalization per- formance (excessive risk) in the presence of noise (inter-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning Algorithm on Graph
polation regime). There are few studies concerning the behaviour of learning algorithms in GNNs (Awasthi al., 2021). These studies are limited in two aspects: 1) they are only concerned with the convergence rates of the learn- ing within the interpolation regime (noise-free), and 2) they provide only a very crude connection to the graph struc- ture, typically represented by the maximum or minimum degree, which offers limited insight into the structure of the graph. Recognizing this gap in the theoretical understand- ing of GNNs, this paper investigates the interplay between graph structure and learning algorithms in the generaliza- tion regime (in the presence of noise). We extend standard settings (least squares) from learning theory literature to the case of GNN and aim to answer the following research questions:
power-law) and demonstrate that 1) the excess risk pro- file of SGD is more favourable (perform better) than Ridge when the underlying graph structure is power- law and 2) the excess risk profile of Ridge is more favourable than SGD when the underlying graph struc- ture is regular (Theorem 4.3). These findings offer practical guidance for learning algorithm selection, sug- gesting that one should choose a learning algorithm (SGD-like vs. Ridge-like) based on the graph structure.
3.
We extend the analysis to the context of multi-layer lin- carized GNNs. We demonstrate that when increasing GNN layers on power-law graphs, the performance of the learning algorithms exhibits increasingly non- isotropic effect on the excess risk profile of learning algorithms (Proposition 4.5). Specifically, it becomes easier for the learning algorithms to learn the ground truth in the head eigenspace, while becomes more challenging in the tail eigenspace. These results pro- vide new perspective on the well-documented over- smoothing issue in GNNs and offer a surprising insight. While it is commonly understood that adding more lay- ers to GNNs can lead to degraded performance due to over-smoothing, our analysis suggests that increas- ing the number of layers can be beneficial for learning algorithms such as SGD when the ground truth is con- centrated in the head eigenspace.
Can graph structure affect the generalization performance of learning algorithms in GNNs? If so, how does the graph structure affect the learning algorithms?
Contribution. The primary objective of this paper is to ex- amine the interplay between learning algorithms and GNNs, particularly focusing on how graph structure impacts the generalization performance (excessive risk) of learning al- gorithms in the interpolation regime. The main challenges addressed in this research are establishing a connection be- tween graph structure and learning algorithm performance, and creating a robust comparison framework. Our analysis focuses on two central learning algorithms, SGD and Ridge, aiming to understand the influence of graph structure by comparing the performance of these algorithms in different graph types (power-law vs. regular). The contributions and results of this study are highlighted as follows:
The empirical results from our controlled experiments with synthetic graph models are consistent with our theoretical predictions, thus validating our analysis and findings. These results not only deepen the theoretical understanding of GNNs but also offer practical insights and guidance for selecting and designing learning algorithms for GNNs based on graph structure.
1. We extend the existing excessive risk analysis to the context of GNNs, broadening the understanding of these learning algorithms within the learning theory literature. Specifically, we have derived the excessive risk (generalization performance) profiles, including both upper and lower bounds, of learning algorithms (SGD and Ridge) in GNNs (Theorems 4.1 and 4.2). These profiles establish a link between the graph ma- trix and the excessive risk of learning algorithms in GNNs. They lay the groundwork for our subsequent investigation into the impact of graph structure on the performance of learning algorithms.
2. Related Work
In this section, we provide a brief overview of the following key aspects of this paper: 1) theoretical studies of GNNs, 2) excessive risk of learning algorithms and 3) spectral graph theory. A more comprehensive discussion of related works is available in the appendix.
Theoretical Understanding of GNNs. Due to the empir- ical success of GNNs, there is a growing body of theoreti- cal studies (see (Jegelka, 2022) for a survey) focusing on the expressive power of GNNs (Sato, 2020: Zhang et al., 2023a;b;e; Xu et al., 2018) and their generalization capabili- ties. The expressive power of a GNN denotes its ability to distinguish between different graph structures and capture the intricacies of node relationships and graph topology. It is often evaluated by comparing the GNN's discriminative ability against classical graph isomorphism tests, such as
2. Based on the established connection between the graph matrix and the excessive risk of different learning algo- rithms, we further utilize spectral graph theory to link the graph structure with the graph matrix. Through this connection and the results derived, we examine the interplay between graph structure and learning al- gorithms in GNNs. Specifically, we focus on the two types of connectivity spectra of the graph (regular vs.
2

---

Learning Algorithm on Graph
Graph Structure
Graph Matrix
Learning Algorithms
Spectral Graph Theory
Excessive Risk Profile
Figure 1. Illustration of how our framework connects graph structure and the performance of learning algorithms. Spectral graph theory connects graph structure and the cigenspectrum of graph matrix. The excessive risk profile of the learning algorithms connects the eigenspectrum of the graph matrix and the performance of the learning algorithms. As such, we establish framework that can study the interplay hetween graph structure and learning algorithms in GNNs.
the Weisfeiler- test (Leman & Weisfeiler, 1968). Meanwhile, generalization studies of GNNs explore how well these models perform on unseen data, utilizing frame- works such as complexity measures (like VC-dimension and Rademacher complexity) (Lv, 2021; Ma et al., 2021; Baranwal et al., 2021: Liao et al., 2021), Neural Tangent Kernel (NTK) (Du et al., 2019) and information-theorete ap- proaches (such as mutual information and entropy) (Verma & Zhang. 2019; Zhu et al., 2021). These studies seek to determine how factors such as network architecture and properties of the input graphs affect the model's general- ization from training to testing data. Therefore, they are orthogonal the research objectives of this paper.
performance with respect to different graph structures.
Spectral Graph Theory. Spectral graph theory is a field of mathematics that studies the properties of graphs through the analysis of eigenvalues and eigenvectors of matrices associated with the graph, such as the adjacency matrix and the Laplacian matrix (Pósfai & Barabási, 2016 Spielman, 2012; Van Mieghem, 2023; Gera et al., 2018; Hammond et al., 2011; Chung, 1997). A foundation principle and result from the spectral graph theory is that the characteristic of the graph structure is closely coupled with the cigenspectrum of the graph matrix. For example, in power-law graphs, which are characterized by few nodes with very high degrees and many nodes with low degrees, the eigenspectrum of the graph matrix is typically broad and heavy-tailed, reflect- ing the heterogeneity of the degree distribution (Faloutsos et al., 1999; Chung et al., 2003; Farkas et al., 2001; Goh et al., 2001; Easley et al., 2010). In contrast, regular graphs, where all nodes have the same degree, exhibit more even eigenspectrum, reflecting the uniformity in the degree dis- tribution (Easley et al., 2010). The comparison between power-law and regular graphs (visualized in Fig. 2 in Sec. 4) underscores the versatility of spectral graph theory in ana- lyzing and interpreting the structural properties of different types of networks. These results serve as an important part of our toolkit for connecting the performance of the learning a algorithm and graph structure.
There is also research on convergence analysis of GNN learning algorithms (Chen et al., 2017; Huang et al., 2018; Chen et al., 2018; Awasthi et al., 2021; Li et al., 2018; Oono & Suzuki, 2020). These studies only examine the conver- gence rate of the algorithms and are confined to the interpo- lation regime (noise-free) Their results only provide a crude connection between graph structure (e.g., the maximum and minimum degrees in the graph) and (the convergent rate of) learning algorithms. lacking in-depth understanding of this relationship. It remains an open question how different characteristics of graph structure (e.g.. power-law vs. regu- lar) influence the performance of learning algorithms in the generalization regime (with noise). We aim to fill this gap by providing framework for linking graph structure to the performance of learning algorithms in this setting.
3. Preliminaries
Excessive Risk of Learning Algorithm. The excessive risk of different learning algorithms is a central research subject in the learning theory literature (Zou et al., 202 lb: 2023; Tsigler & Bartlett, 2020; 2023; Dhillon et al., 2013;
We introduce the notation, necessary background, and prob- lem formulation in this paper.
Lakshminarayanan & Szepesvari, 2018; Jain et al., 2017: Défossez& & Bach, 2015). In particular, key research ques- tion is how different learning algorithms perform under various settings (Dhillon et al., 2013). It remains unclear how the excessive risk of learning algorithms could manifest under graph learning and how different algorithms would perform in this setting. We expand the knowledge of the learning theory by providing an excessive risk analysis of SGD and Ridge regression in GNNs and comparing their
Notation. We use lowercase letters to denote scalars and use lower and uppercase boldface letters denote vectors and matrices. For a vector x, x[i] denotes the i-th coordinate. For two functions fxx 2 0 and g(z) 2 0 defined on >> O, we write [(x) X g(x) if f(x) S e g(x) for some absolute constant > 0; we write f(x) Z g(x)) if g()) S f()); we write f(x = g(x) if f(x) S g(x) S f(x). For a vector @ E Rdd and a positive semidefinite matrix H E Rdxd we denote ||0 12 := 0 HO. We denote [k] = (1...., k).
3

---

Learning Algorithm on Graph
Graph. A (standard) graph with N vertices is given by
and vary together. Then, we use y E R to denote response and it is generated with ReLU readout:
two-tuple (V,E), where V - UN) is the set of vertex and & C V x V is a set of edge that defines the graph structure among V. Each vertex i E [M] is associated with a feature vector x; E H. in some separable Hilbert space H. The dimensionality of H. is denoted as d, which can be infinitediimesiooal when applicable. Let X E R xd denote the feature matrix of all the vertices.
y ReLU(m +*++,, m M,
where 0 H- represents the unknown true model parameter and e R is the model noise with mean. It should be noted that there can be correlations among m manifested in the covariance of e. As a result, our generating model is very general. In addition, the above formulation is equivalent to the Markov-blanke formulation commonly used other theoretical studies of GNNs (Wu et al., 2022).
Graph Neural Networks. The computation in GNNs can be viewed as pesssag-paassing along graph struc- ture (Jegelka, 2022). At each round I, the new embedding X; for vertex is updated through a series of aggregate and combine steps as outlined below:
(1)
Learning Problem. The goal of the learning problem is to estimate the true parameter 0* by minimizing the following:
(1) AGGREGATE((s) (1-1 ((()))
m;
L( = min L(0), DEH
( COMBINE(X;" (1-1) !!!
E [(v ReLLUmTT))"" L(0) == 2
where zi is initialized as the feature vector x,, (i) rep- resents the neighbors of vertex i, and m, denotes the aggre- gated representation at round I. Different GNNs differ in specific implementation of the AGGREGATE and COM- BINE functions. Essentially, GNN serves an embedding function that integrates the graph structure and node features to produce an aggregated representation vector of node This representation is subsequently processed by a read-out function (e.g., a ReLU layer) to generate predictions.
where the expectation is taken over the randomness y and m. The generalization performance of an estimated found by a learning algorithm (e.g., SGD) is evaluated based on the excessive risk:
A ( -
The excessive risk (0) can be decomposed into bias and variance as follows:
One-round Graph Neural Network. In this study, we follow similar setting to (Awasthi et al., 2021) and focus our main discussions on one-round GNN which consists of aggregation operation and readout operation. Here we interpret the aggregation operation graph matrix G operating on the feature matrix X. Then, we formulate the one-round GNNs with a two-component formulation. The first component is to aggregate the feature with the given aggregation operator and a graph matrix G. We denote the resulting space as M:
A = | 0"
M
bias
variance
The decomposition above shows that the excess risk profile of A gives a comprehensive characterization of the learning algorithm, showcasing its convergence (governed by bias) and its robustness to noise (governed by variance). Fol- lowing the prior literature (Bartlett al., 2020; Zou et al., 2021b; Jain et al., 2017; Bach & Moulines, 2013; Berthier et al., 2020), we make the following assumptions on the data feature H and G.
G
(3.1)
Assumption 3.1. H is positive definite (PD) and its trace (r( is finite.
M can be viewed as the space where the aggregation repre- sentation lives. Without loss of generality, we assume M is subspace of H. Depending on the choice of graph matrix G. we can recover different variants of GNNs (we provide further discussion in this regard in Appendix G). For exam- plc, when G = A (the normalized adjacency matrix of the graph) and is the simple matrix multiplication, we recover GCN (Kipf & Welling, 2017). Furthermore, for a given feature vector x and aggregation representation m, we use
Assumption 3.2. There exists positive constant a such that for every x and any positive semidefinite matrix A, it holds that: E[xx' Axx HAH < a tr(AH) H.
Assumption 3.3. There exists a positive constant o such that: Ex, T < o²H.
Assumption 3.4. G is PD with respect to x and has a bounded norm.
H Exxx(xx M : -m--M [mm")
This additional assumption on the graph matrix generally holds for common choices of graph matrices, such as the Laplacian and Adjacency matrices. To relate the graph
to denote the second moment of m and x, which is the covariance matrix characterizing how the components of

---

Learning Algorithm on Graph
structure to the excessive risk of the learning algorithm, we interested in the connection between 0* and M. To analyze their relation, we introduce the following notation:
where 7 0 is constant stepsize (also referred to as the learning rate). After N iterations, which corresponds to the number of samples observed, SGD computes the final estimator as the tail-averaged iterates:
Mo:k- = E Ein M1:00 := Ei>a//v.v.
Ougal (N, GN
2 N-1 N 21-
2
where { are the eigenvalues of M sorted in non- increasing order and v are the corresponding eigenvectors.
Then we define:
Here we focus on tail tail-average SGD 1 as has been shown to improve the convergence properties and robustness of last-iterate SGD, particularly in the presence of noise and heavy-tailed data distributions (Zou et al., 2021b). The following theorem gives a description of the excessive risk profile of SGD under our setting.
Ov
|
Σ pui(TTo'' 1>b
Ho.k
14
H
iSA
4. Main Results
Theorem 4.1 (Excessive Risk Profile of SGD). Consider SGD with tail-averaging with initialization Ou O. Sup- pose Assumptions 3.1, 3.2, 3.3 and 3.4 hold and stepsize satisfies 7 S MM() Then the excessive risk of SGD can be coppe--boudde as follows:
We next present the main results of this paper, focusing on the description and implication of the results. Detailed proof of the results can be found in the supplementary material.
Result Overview. We first derive the excessive risk pro- file (upper bound and lower bound) of learning algorithms (SGD and Ridge) in GNNs. These excessive profiles pro- vide a connection between the graph matrix and the exces- sive risk of learning algorithms in GNNs. Then we use spectral graph theory further establish the connection be- tween the performance of the learning algorithm and graph structure. In particular, we investigate how the connectiv- ity structure of the graphs (power-law vs. regular graph) affects the performance of different learning algorithms in GNNs. Furthermore, we extend the analysis to multi-layer linearized GNNs and yield novel perspective on the over- smoothing issue of GNNs. This analysis reveals that the over-smoothing issue may be attributed increasing cessive risk in learning algorithms due to misalignment between the ground truth and the eigenspectrum of the ag- gregation space. Interestingly, increasing the number of GNN layers can be advantageous when the ground truth aligns with the headspace of the aggregation space. A visu- alization of the overall analytical framework provided in Fig. 1.
A ( G.))) & SGDBias + SGDVariance,
SGDBias
N2 exp ( N1 Mo.k
1
+ +110~|
May
SGDVariance
a² + 101 h12
1M
(12+
N2
Σ
1
N
12
where k1, E [d] are arbitrary.
Suppose the stepsize satisfies y S 1/m. Then the excess risk can be nower-bounded as follows:
A (NV, GN,) 2 SGDBias + SGDVariance,
SGDBias
exp ( N + +110r112
N2
4.1. Excessive Risk Profile of Learning Algorithms
SGDVariance =
We derive the excess risk profile that expands the current knowledge of learning theory and GNN, and forms foun- dation for our further investigations the effect of graph structure.
o²
k* 1
Σ 13 + 100
2
N
M
M1
i>
where A = max(k: : us 2 1/(Nx)), and kt max(k P* 2 2/NN))
SGD. We consider SGD with a constant step size and tail- averaging (Bach & Moulines, 2013; Jain et al., 2017: 201 8). At the t-th iteration, a fresh example is sampled from the aggregation space (m, ~ G X) to perform the update:
Theorem 4.1 establishes the excessive risk upper and lower bounds for SGD in GNNs, offering a detailed characteriza- tion of each component (bias and variance) that constitutes the excessive risk profile of SGD. Several observations are
O = 0, Vi(O,; =0, - (ReLU(m,) 100mmmm,01)) -v)) -.,
'we provide a more in-depth discussion of tail-average SGD in the supplementary material.
7
5

---

Learning Algorithm on Graph
pertinent here. First, Theorem 4.1 demonstrates that the excessive risk of SGD (for both upper and lower bounds) is intimately linked to the aggregation matrix M, which is derived from the graph matrix G. This establishes a clear relationship between the performance of SGD and the graph matrix. Second, Theorem 4.1 reveals that the headspace and tail space of the eigenspectrum of M differently affect both the bias and variance. Specifically, the leading eigen- spectrum shows an exponential decay in bias, indicating that SGD can effectively and efficiently approximate the ground truth associated with these directions. Third, while the decomposition of the eigenspectrum in the upper bound of SGD applies for any arbitrary k1, l2 E [d], the decom- position in the lower bound of SGD more stringent and depends on the sample complexity and learning rate.
Theorem 4.1, Theorem 4.2 demonstrates that the excessive risk of GNNs can be divided into two components, bias and variance, highlighting& a structural similarity that is crucial for subsequent comparisons between the two learning algo- rithms. It is noted that the upper bound and lower bound of the excessive risk for Ridge generally aligns better than those for SGD, consistent with existing studies (Tsigler Bartlett, 2020; 2023). By selecting & equal to k*, we achieve unified bound for the risk associated with Ridge, differing only by a constant factor.
4.2. Graph Structure and Learning Performance
Next, we deepen our understanding of the connection be- tween graph structure and the excess risk of learning algo- rithms using spectral graph theory. Spectral graph theory facilitates the linkage of graph structure to the eigenspec- trum of the graph matrix. Specifically, we focus our analysis on the power-law graph, which is characterized by an expo- nential decay in the degree sequence, and the regular graph, where each vertex has uniform degree.
Ridge Regression. Given graph matrix G and feature ma- trix X, Ridge regression provides an estimator for the true parameter by solving the following optimization problem:
rrige (N, A) := arg min (I o X) 0 - y11i + || EEH
where A 2 0 is the regularization parameter. When À = 0, the Ridge estimator reduces to the ordinary least square estimator (Hastic et al., 2009). In the following theorem, we give a characterization of the excessive risk profile of Ridge in the proposed setting.
Power-law vs. Regular Graph. As discussed in Sec. 2. the graph matrix of power-law graph typically exhibits concentrated eigenvalues (i.e., large eigenvalue associated with few eigenvectors), resulting in fast-decay eigen- spectrum. In contrast, the graph matrix of regular graphs typically shows a uniform distribution of eigenvalues (i.e., eigenvalues of roughly the same magnitude across all eigen- vectors), which leads to a slow-decay eigenspectrum. visualization of these characteristics is given in Fig. 2.
Theorem 4.2 (Excessive Risk Profile for Ridge). Consider ridge regression with parameter À > O. Suppose Assump- tions 3.1, 3.2, 3.3 and 3.4 hold. For a constant X depending on X and N, Ridge has the following excessive risk upper bound for arbitrary le E [d]:
For precise analysis, we consider graphs with eigenspectrum from the following model:
X²
A A(Oridge (N, G:A)) 2
N2
0
2
M 0.k
+
110
M
2
Ms (G) 1/19.
(4.1)
RidgeBias
where (G) represents the i-th eigenvalue of the graph matrix G and B > is the constant that controls the rate of decay in the eigenvalues. A larger /3 results in a faster de- cay of the eigenspectrum, similar to that seen in power-law graphs, while smaller ,3 leads to a more uniform eigen- spectrum, akin to that of regular graphs. Additionally, we assume that the underlying ground truth model parameters and the feature space align with the eigenspectrum of the graph matrix, reflecting typical scenarios in graph learn- ing problems (Fortunato, 2010). Based on this model, we present results that compare the performance of SGD and Ridge in pawer-law and regular graphs, thereby characteriz- ing how graph structure influences the performance of the learning algorithm.
k
+ 0².
N
1>k
RidgeVariance
Suppose k* min(k= : Npk S. 2}. Then we have the
following excessive risk lower bound for Ridge:
X²
A A(Oiide N, G; 2
110- 11 M
N2
M-
RidgeBBas
b + 0².
N
Ridge KidgeVariance
Theorem 4.3 (Effect of Graph Structure). Suppose Assump- tions 3.1, 3.2, 3.3 and 3.4 hold. Consider a power-law graph Gp with graph matrix Go whose eigen-spectrun is characterized by Eq. 4. 1 with a large enough B3. Then for
Theorem 4.2 establishes an excessive risk profile (upper and lower bound) for Ridge regression in GNNs, Mirroring
6

---

Learning Algorithm on Graph
every X for ridge regression, there exists a choice for 7" for SGI such that for sufficiently large N, we have
through the lens of node representation, attributing over- smoothing the homogenization of representations (where iterative aggregation of neighbor information causes all nodes to converge to a similar representation). thereby los- ing the unique structural and feature information that distin- guishes them. With our established analysis and results, we present the following novel implications and connections between learning algorithms and over-smoothing.
A (g0agd ( N, Gp) & A(Oridge (N, A)).
On the other hand, consider a regular graph Gr with graph matrix G. whose eigen- sigen-spectrum is characterized by Eq. 4.1 with a small B. Then for every choice of for SGD, there exists a X* such that,
By recursively expanding the expression of multi-layer GNNs as described, we can analyze the L-layer GNNs through the modified graph matrix
A (Oridge (N, G); & A0gugd (N, G)))))-
Theorem 4.3 suggests that SGD generally performs bet- ter (exhibits lower excessive risk) than Ridge regression in power-law graphs, characterized by a faster-decay graph spectrum. Conversely, Ridge regression tends to outperform SGD in regular graphs, which are characterized by a slower- decay graph spectrum. This result affirmatively supports our research question and establishes connection between graph structure and learning algorithms via the graph spec- trum. It also provides crucial insights for practical learning algorithm selection: an SGD-like learning algorithm is pre- ferred for power-law graphs, while a Ridge-like algorithm advisable for regular graphs.
GLL) - II 1
Proposition 4.5 (Effect of Stacking GNN Layers). G shares the same eigenbasis with G. Furthermore, for two eigenvalues pa My and positive integer if p4 > pz. then we have
pe (G( + 1)) (G(()) 1y (G( (G((++))) Jyy (,(((T))
Remark 4.4, Our theoretical results are not tightly depen- dent on the exact form of the power-law decay model. We adopt this model primarily for analytical clarity, but the core insights extend to a broader class of spectral decay behaviors. The essence of our findings (e.g., Theorem 4.3) lies in the rate at which the eigenvalues of the graph matrix decay, regardless of whether this follows a strict pawer-law. A faster- decaaind spectrum aas often observed in graphs with power-law-like structures-tends to favor SGD. In con- trast, a slower-decaying spectrum-ay as seen in more regular tapps-makke, Ridge more favorable.
Proposition 4.5 indicates that stacking additional GNN lay- ers amplifies the relative difference (ratio) between the eigenvalues of different eigen-directions, thereby impos- ing non-isotropic effect on the eigenspectrum of G. More specifically, this leads to an eigenspectrum that exhibits faster decay. Building on this, and using the previous exces- sive risk analysis, we can further connect the performance of learning algorithms to the increasing number of GNN layers.
Most real-life graphs, particularly those used for academic benchmarks, are power-law graphs. As previously dis- cussed, power-law graphs exhibit concentrated eigenspectra and feature fast-decay spectrum. This creates a significant relative difference between a few directions and the rest of the directions on the eigenbasis. Accordingly, stacking additional layers of GNNs further amplify this relative dif- ference. Based on our previous excessive risk analysis, if the ground truth does not align with the eigenspectrum of the graph matrix, increasing the number of GNN layers ex- acerbate this misalignment, leading greater excessive risk (making learning more difficult for the learning algorithm and causing over-smoothing). Conversely, if the ground truth is concentrated in the few large eigen-directions. then adding more layers to GNNs will improve this alignment and consequently lead a better excessive risk.
4.3. Linear GNNs and Over-smoothing
We extend our previous analysis to multi-layer GNNs and examine the cascading effect of stacking multiple layers. To make the analysis tractable, we focus on linearized GNNs (with ReLU readout) such as SGCN (Wu et al., 2019), fol- lowing the approach in (Awasthi et al., 2021). We analyze the following I--layer linear GNN model:
( ( ISISL.
y= RcL. (mll)) 0r) +c, mL) M(),
with the same assumptions as previously established.
A New Perspective on Over-smoothing. Over-smoothing in GNNs describes the phenomenon that the performance of a GNN degrades as the number of layers increases (Rusch et al., 2023). Previous studies have explored this issue
4.4. Empirical Study
We present an empirical study to validate our theoretical results and to illustrate the following:
7

---

Learning Algorithm on Graph
Power-aw Draph
dala
E.gervlla am
20
Rogular Grash
Egervvlue
power law graph
regular graph
163
10
150
200
Indox
Indax
(a) Regular Graph
(b) Power-law Graph
(c) Laplacian Eigenspectrum
(d) Aggregation Eigenspectrum
Figure 2. Illustration of the Graph Structure and Eigenspectrum of Power-law and Regular Graphs. Fig. 2(a) and Fig. 2(b) illustrate regular and power-law graphs, respectively. Fig. 2(c) plots eigenspectrum of the graph Laplacian associated with the graphs. Fig. 2(d) shows eigenspectrum of the aggregation covariance space M.
layer
Drw layer
Ridig
Exoeeetee Itee.
200
Regge
1000
two layer
Excosivv Rick
two layer
Exeesivve
three
t00
500
ayeer
10 Sample Stze(x100)
40
Sample Staood (0)
Sample Stzoee100)
Sample Stzotet
(a) Power-law Graph
(b) Regular Graph
(c) Mis-aligned Ground Truth
(d) Aligned Ground Truth
Figure 3. Illustration the Performance of Learning algorithm in Different Graph Structures and the Effect of Stacking GNN Layers. Fig. 3(a) and 3(b) show performance comparison of SGD and Ridge in power-law and regular graph. Fig. 3(c) and 3(d) show the effect of stacking GNN layers with/without the ground truth concentrating in the head eigenspace.
1. the relation between the eigenspectrum of mixing space and graph structure (power-law vs. regular).
space (induced by power-law vs. regular graphs) mirrors the eigenspectrum of the corresponding graph matrix (power- law vs. regular). Fig. 3(a) and 3(b) offer an end-to-end comparison the performance of SGD and Ridge regres- sion power-law and regular graphs, respectively. These figures demonstrate that SGD outperforms Ridge regres- sion in power-law graphs, while Ridge regression excels over SGD in regular graphs, validating our theoretical pre- dictions. Fig. 3(c) illustrates that when the ground truth does not align well with the eigenspectrum (with ground truth vectors distributed in the tail eigenspace where μ4 is small), stacking GNN layers results in increased excessive risk, thereby causing the over-smoothing issue. Conversely, Fig. 3(d) indicates that increasing the number of layers can be beneficial when the ground truth aligns well (with ground truth concentrated in the head eigenspace where μ4 is large).
2. validate our theoretical prediction of SGD & Ridge in power-law and regular graphs.
3. the cascading effect when stacking multi-layer GNNs.
4.5. Setting
To control variations in graph structures, features, and model parameters, we focus our empirical study on graph simulation models, similar to other learning theory stud- ies (Awasthi et al., 2021). In particular, we utilize the well- known Barabasi- Albert model (Pósfai & Barabási, 2016) to generate pawer-law graphs. For each node in the graph, we generate a feature vector of dimension 200 from the stan- dard Gaussian distribution N(O, I). We generate the ground truth 8* that aligns with the eigenspectrum of the graph matrix. The model noise variance is set as x² = 1. Each experiment is conducted for five independent trials, and the average results are reported.
5. Conclusion and Discussion
5.1. Conclusion
In this paper, we conduct theoretical investigation into the interplay between graph structure and learning algorithms in GNNs. Specifically, we extend the excessive risk analysis to include two core learning algorithms (SGD and Ridge) within the context of GNNs. We further utilize spectral graph theory to link the excessive risk of learning algo-
4.6. Result
The empirical results are summarized in Fig. 2 and 3. Fig. 2(d) shows that the eigenspectrum of the aggregation space M aligns with the eigenspectrum of the graph struc- ture, indicating that the eigenspectrum of the aggregation
8

---

Learning Algorithm on Graph
rithms with graph structure and carry out a comparative study across different graph structures (power-law and regu- lar). Our findings indicate that SGD generally outperforms Ridge in power-law graphs and the reverse holds true in regular graphs. This positively answers our research ques- tion regarding whether graph structure can influence the performance of learning algorithms and demonstrates the structural relationship between graph structure and learning algorithms.
References
Awasthi, P., Das, A., and Gollapudi, S. A convergence analysis of gradient descent on graph neural networks. Advances in Neural Information Processing Systems, 34: 20385-20397, 2021.
Bach, F. and Moulines, E. Non-strongly-comvee smooth stochastic approximation with convergence rate (1/n), Advances in neural information processing systems, 26, 2013.
5.2. Future Work
Baranwal, A., Fountoulakis, K., and Jagannath, A. Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprint arXiv:2102.06966 2021.
This study opens up intriguing directions for future research. First, our analysis was confined to one-layer GNNs or lin- earized GNNs to maintain traceability in the theoretical analysis. This limitation is common in similar studies, even with I.D data, due to the constraints of existing theoretical tools. Developing more sophisticated analytical tools to extend the analysis to more complex models, such as those with multiple non-linear layers, would be beneficial. Second, given our focus on the interplay between graph structure and learning algorithms, we isolated the relationship and impact of graph structure and node features. Exploring how a structural relationship between graph structure and node features could further influence learning algorithms, would also be a worthwhile direction, particularly regarding its implications on over-squashing (Topping et al., 2021).
Bartlett, P. L., Long, P. M., Lugosi, G., and Tsigler, A. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 1 117748):30063-30077 2020.
Berthier, R., Bach, F., and Gaillard, P. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances in Neural Informa- tion Processing Systems, 33:2576 2586, 2020.
Chen, J., Zhu, J., and Song, L. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:/7100 10568, 2017.
Finally, extending our theoretical framework random graph models constitutes another promising avenue. While our current results can directly apply to specific realiza- tions of random graphs, a comprehensive probabilistic treat- ment-considering expected or high-probabilin spectral be- haviors-would generalize our findings significantly. Lever- aging concentration inequalities or advanced random matrix theory derive probabilistic guarantees on the performance differences between SGD and Ridge regression across graph ensembles (e.g., Erdós-Reds Rényi, stochastic block models, and other popular random graph families) represents a meaning- ful future research direction.
Chen, J., Ma, T., and Xiao, C. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint 1rXiv:1801.1024/ 2018.
Chung, F., Lu, I.., and Vu, V. Eigenvalues of random power law graphs. Annals of Combinatorics, 7(1):21-33, 2003,
Chung, F. R. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Défossez, A. and Bach, F. Averaged least-mean-squaree Bias-varianes trade-offs and optimal sampling distribu- tions. In Artificial Intelligence and Statistics, pp. 205-213. PMLR, 2015.
Impact Statement
This paper presents work whose goal is to advance the under- standing of graph neural networks. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Dhillon, P. S., Foster, D. P., Kakade, S. M., and Ungar, L. H. A risk comparison of ordinary least squares vs ridge regression. The Journal of Machine Learning Research, 14(1):1505-511, 2013.
Dieuleveut, A., Flammarion, N., and Bach, F. Harder, better, faster, stronger convergence rates for least-squares regres- sion. The Journal of Machine Learning Research, 18(1): 3520-3570, 2017.
Acknowledgement
We would like to thank the anonymous reviewers and area chairs for their helpful comments. This work supported in part by grants from Hong Kong RGC under the contracts 17207621, 17203522, and C7004-22G (CRF).
Dobriban, E. and Wager, S. High-dimensional asymptotics prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
9

---

Learning Algorithm on Graph
Du, S. S., Hou, K., Salakhutdinov, R. R., Poezos, B., Wang, R., and Xu, K. Graph neural tangent kernel: Fusing graph neural networks with graph kernlls. Advances in neural information processing systems, 32, 2019.
Huang, W., Zhang, T., Rong. Y., and Huang, J. Adap- tive sampling towards fast graph representation learning. arXiv preprint arXiv: (ttd::8809003333 2018.
Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P., Pil- lutla, V. K., and Sidford, A. A markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprini urXiv:
Easley, D., Kleinberg, J., et al. Networks, crowds, and mar- kets, volume 8. Cambridge university press Cambridge, 2010.
2017.
Faloutsos, M., Faloutsos, P., and Faloutsos, C. On power-law relationships of the internet topology. ACM SIGCOMM computer communication review, 29(4)2251-26) 1999.
Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P., and Sidford, A. Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. Journal of machine learning research, 18(223):1-43 2018.
Farkas, I. J., Derényi, I., Barabási, A.-L.,, and Vicsek, T. Spectra of "real-world" graphs: Beyond the semicircle law. Physical Review E, 64(2):026704, 2001.
Jegelka, S. Theory of graph neural networks: Represen- tation and learning. In The International Congress of Mathematicians, 2022.
Fortunato, S. Community detection in graphs. Physics reports, 486(3-5):75-177,, 2010.
Gera, R., Alonso, L., Crawford, B., House, J., Mendez- Bermudez, J., Knuth, T., and Miller, R. Identifying network structure similarity using spectral graph theory. Applied network science, 3:1-15, 2018.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks, 2017.
Kobak, D., Lomond. J., and Sanchez, B. The optimal ridge penalty for real-words highddimensional data can be zero negative due to the implicit ridge regularization. The Journal of Machine Learning Research, 21(():6833-6878 2020.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry, 2017.
Goh, K.-I., Kahng, B., and Kim, D. Spectra and eigenvectors of scale-free networks. Physical Review E, 64(5):051903, 2001.
Lakshminarayanan, C. and Szepesvari, C. Linear stochas- tic approximation: How far does constant step-size and iterate averaging go? In International conference on arti- ficial intelligence and statistics, pp. 1347-1355. PMLR, 2018.
Hagberg, A., Swart, P., and S Chult, D. Exploring net- work structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LA Los Alamos, NM (United States), 2008.
Leman, A. and Weisfeiler, B. A reduction of graph to canonical form and an algebra arising during this reduc- tion. Mauchno-TTchhicheskeee Informatsiya, 2(9):12-16, 1968.
Hamilton, W. L., Ying, R., and Leskovec, J. Inductive representation learning on large graphs, 2018.
Li, Q., Han, Z.. and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference artificial intelli- gence, volume 32, 2018.
Hammond, D. K., Vandergheynst, P., and Gribonval, R. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 3292):12--150 2011.
Li, Y., Yu, R., Shahabi, C., and Liu, Y. Diffusion con- volutional recurrent neural network: Data-driven traffic forecasting, arXiv preprint
Hastie, T., Tibshirani, R., Friedman, J. H., and Friedman, J. H. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
2017.
Liao, R., Urtasun, R., and Zemel, R. A (pacs-bayesian approach to generalization bounds for graph neural net- works. In International Conference on Learning Rep- resentations, 2021. URL https: opw.revie....ee net/ pet/forumtt (acfooommuid-ee -ediidd----a- NnF
Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. Surprises in nigh-dimensional ridgeless least squares in- terpolation. Annals of statistics, 50(2):949, 2022.
Hsu, D., Kakade, S. M., and Zhang, T. Random design analysis of ridge regression. Twenty-Fifth Annual Con- ference on Learning Theory, 2012.
Lu, C., Krishna, R., Bernstein, M., and Fei-Fei, L. Visual relationship detection with language priors, 2016.
10

---

Learning Algorithm on Graph
Lv, Generalization bounds for graph convolutional neural networks via rademacher complexity, 2021.
Su, J., Zou, D., and Wu, C. Pres: Toward scalable memory- based dynamic graph neural networks, 2024. URL https:/ www.eiii..oggabsieeeoeeeeeee
04284.
Ma, J., Deng, J., and Mei, Q. Subgroup generalization and fairess of graph neural networks. arXiv preprint arXiv:2106. 15535, 2021.
Tang, H. and Liu, Towards understanding generalization of graph neural networks. In International Conference on Machine Learning, pp. 33674-33719, PMLR, 2023.
Oono, K. and Suzuki, T. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Ad- vances in Neural Information Processing Systems, 33: 18917-18930, 2020.
Topping, J., Di Giovanni, F,, Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:21 1..::222,. 2021.
Tsigler, A. and Bartlett, P. Benign overfitting in ridge re- gression. arXiv preprint arXiv:2009. 14286, 2020.
Paquette, C., Paquette, E., Adlam, B., and Pennington, J. Implicit regularization or implicit conditioning? exact risk trajectories of sgd in high dimensions. Advances in Neural Information Processing Systems, 35:35984- 35999, 2022.
Tsigler, A. and Bartlett, P. L. Benign overfitting in ridge regression. J. Mach. Learn. Res., 24:123-1, 2023.
Tsubaki, M., Tomii, K., and Sese, J. Compound-protes interaction prediction with end-to-end learning of neural networks for graphs and sequences. Bioinformatics, 35 (2):309-318, 2019.
Pósfai, M. and Barabási, A.-L. Network science. Citeseer, 2016.
Réau, M., Renaud, N., Xue, L. C., and Bonvin, A. M. Deeprank-gme gnn: a graph neural network framework to learn patterns in protein-protein interfaces. Bioinformat- ics, 39(1)bbtac759 2023.
Van Mieghem, P. Graph spectra for complex networks. Cambridge university press, 2023.
Veličković, P., Cucurull, G., Casanova, A., Romero, A.,
Reiser, P., Neubert, M., Eberhard, A., Torresi, I.., Zhou, C., Shao, C., Metni, H., van Hoesel, C., Schopmans, H., Sommer, T., et al. Graph neural networks for materials science and chemistry. Communications Materials, 3(1): 93, 2022.
Lio, P., and Bengio, Y. Graph attention networks. arXiv preprint arXiv: 17.0. 2017.
Verma, S. and Zhang, Z.-L. Stability and generalization of graph convolutional neural networks, 2019.
Wu, D. and Xu, J. On the optimal weighted \ell_2 regular- ization in overparameterized linear regression. Advances in Neural Information Processing Systems, 33:10112 12- 10123, 2020.
Rusch, T. K., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks, 2023. URL ht https:: //axiiv./xivvvv/a wtt//bss/////eoooeeeo..ooe.seese 2303 10993.
Sato, R. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04077, 2020.
Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Wein- berger, K. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861- 6871. PMLR, 2019.
Scarselli, F., Tsoi, A. C.,, and Hagenbuchner, M. The vapnik- chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-2551 2018.
Wu, J., Zou, D., Chen, Z., Braverman, V., Gu, Q., and Kakade, S. M. Finite-sample analysis of learning high- dimensional single relu neuron. In International Confer- ence on Machine Learning, pp. 37919-37951. PMI.R, 2023.
Sheng, G., Su, J., Huang, C., and Wu, C. Mspipe: Efficient temporal gnn training via staleness-aware pipeline. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2651-2662, 2024.
Wu, Q., Zhang, H., Yan, J., and Wipf, D. Handling distribu- tion shifts on graphs: An invariance perspective, 2022.
Spielman, D. Spectral graph theory. Combinatorial scien- tific computing, 18:18, 2012.
Xu, D., Zhu, Y., Choy, C. B., and Fei-Fei, L. Scene graph generation by iterative message passing, 2017.
Su. J. and Wu, C. On the topology awareness and gen- eralization performance of graph neural networks. In European Conference on Computer Vision, pp. 73-89. Springer, 2024.
Xu, J. and Hsu, D. On the number of variables to use in principal component regression. Advances in neural information processing systems, 32, 2019.

---

Learning Algorithm on Graph
Xu, K., Hu, w. Leskovec, J., and Jegelka, S. How powerful graph neural networks? arXiv preprint arXiv:1810.00820 2018.
Yang. J., Ang, z.,, Guo, Z., Zhou, K., Zhang, W., and Liu, Z. Panoptic scene graph generation, 2022.
Zellers, R., Yatskar, M., Thomson, S., and Choi, Y. Neural motifs: Scene graph parsing with global context, 2018.
Zhang, B., Fan, C., Liu, S., Huang, K., Zhao, X., Huang, J., and Liu, 7. The expressive power of graph neural networks: A survey, 2023a. URL https:/ //rrxiv. org/absa aataabbs/22000 08235.
Zhang, B., Feng, G., Du, Y., He, D., and Wang, L. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In International Con- ference on Machine Learning, pp. 41019-41077 PMLR, 2023b.
Zhang, B., Luo, S., Wang, L., and He, D. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprint arXiv:2301.080 009505, 2023c.
Zhu, G., Zhang, L., Jiang, Y., Dang, Y., Hou, H., Shen, P., Feng, M., Zhao, X., Miao, Q. Shah, S. A. A., and Ben- namoun, M. Scene graph generation: A comprehensive survey, 2022.
Zhu, Q., Ponomareva, N., Han, J., and Perozzi, B. Shift- robust gnns: Overcoming the limitations of localized graph training data, 2021.
Zou, D., Wu, J., Braverman, V., Gu. Q., Foster, D. P., and Kakade, S. The benefits of implicit regularization from sgd in least squares problems. Advances in neural infor- mation processing systems, 14:5456-5466 2021a.
Zou, D., Wu, J., Braverman, V., Gu. Q.. and Kakade, Be- nign overfitting of constant-stepsize sgd for linear regres- sion. In Conference on Learning Theory, pp. 4633-4635. PMLR, 2021b.
Zou, D.. Wu, J., Braverman, V., Gu, Q., and Kakade, S. M. Benign overfitting of sonstant-stepsize sgd for linear gression. Journal of Machine Learning Research, 24 1326):1-58, 2023.
12

---

Learning Algorithm Graph
A. Excessive Risk of SGD
In this appendix, we provide proof of the excessive risk (Theorem 4.1) of SGD in our proposed setting. In this part, we will mainly follow the proof technique and results in (Zou al., 2021b) that developed to sharply characterize the excess risk bound for SGD (with tail-averaging) when the data distribution has nice finite fourth-moment bound. However, such condition does not directly apply the case with aggregation and ReLU activation. Therefore, their result can not be directly applied here.
A.1. Preliminary and Useful Lemmas
We start with stating some commonly used notation and proving of lemmas that are going be useful for the subsequent analysis. First, let us recall some common notation and definitions that are going to be used in the proof. We denote the node feature matrix X and d, G to be the graph matrix associated with the GNN, and M to be the aggregation space after applying the graph matrix G on X. Furthermore, we denote
H E[ E ]
to be the covariance of data distribution and aggregation distribution. We denote
P1, Hd.
to be the eigenvalues for M in descending orders.
We start with proving the implication of the Assumptions 3.1, and 3.2 on the aggregation space.
Lemma A.1. Suppose Assumption 3.2 holds, there exists positive constant a' such that for every m and any positive semidefinite matrix A, it holds that: E/mm' Ammm MAM 3 a' a'trr(AAMM))) tr(M)). MM.
Proof. By definition, we have that
m ~~M: M
For given PSD matrix A, we denote
B GAG.
By Assumption 3.4, we have that G PSD matrix. Hence, we can immediately conclude that also a PSD matrix. Then, we have that,
E mm Amm MAM,
GE[xx Bxx |G - GXX G BXX
GE(xx Bxx [G GHBHG.
G (E[xx Bxx ] HBH) G.
Then, by Assumption 3.2, we have that there exists a a such that
xxxx Bxx
HBH 3 (r(HH)
Substitute this back into the derivation above, have that,
E 2mm Amm 1 1]-MAM
G [x[x Bxx HBH) G,
3 tr (BGHG) GHG.
Again, by Assumption 3.4, we have that G a bounded matrix and immediately obtain that there exists a a' such that,
mm'' Amm MAM,
aatt(GAGGHG) GHG.
= (aAAGG) GHG, =a' aatrr(AM) M
13

---

Learning Algorithm on Graph
Lemma A.2. There exists a positive constant o' such that: Fm,ele2mmm ' 1 o²M.
Proof.
E mm J] GIEle"xx JG,
By Assumption 3.3, we have that,
< G(o"H)
o GHG,
M
Lemma A.3. The covariance matrix of aggregation space M is PSD and has a finite trace.
Proof. First recall that
M G.X.
By Assumption 3.1, have that X is SD. Similarly, by Assumption 3.4, have that G is SD. We immediately obtain that M is PSD.
Now, it remains to show that M has finite trace.
(T(M) S tr(G)
Again, by Assumption 3.1 and Assumption 3.4, we have that tr(X) and tr(G) are finite and therefore, tr(M) finite.
The analysis in (Bartlett et al., 2020; Zou et al., 2021b) established sharp analysis for SGD and Ridge with bounded fourth-moment assumption. However, the setting considered in these two studies assumes linear model without non non-linear activation. In other words, the SGD update given by,
O++1 0, (m, 0,-1 -y:) m.;
In our study, we consider GNN layers with ReLU activation and the update is given by,
0++1 0: y. (ReLU(m,
0, 0.-1) - ye) m
We adopt the following result from (Wu et al., 2023) relate the excessive risk landscape of SGD and SGD with ReLU activation. Lemma A.4 (Restatement Lemma 4.2 in (Wu et al., 2023)). The excessive risk landscape of ReLU updates is given by:
0.25| 0 0* M S A
0 0* M
Lemma A.4 suggest that even though the excess risk induced by ReL.U activation could be non-convex locally, the landscape of the excess risk on large scale is "approximately" quadratic in the sense of ignoring some multiplicative factors. This landscape enables us to build sharp upper and lower bounds on the excess risk by bounding simpler quadratic,
0
0- Il--
14

---

Learning Algorithm on Graph
A.2. SGD Excessive Risk
Next, we present proof for the excessive risk profile, Theorem 4.1, for SGD under GNN. For this, we decompose the proof and the results of the theorem into two parts: upper bound and lower bound that involve different results.
The overall proof structures are as follows: 1) we first derive the learning dynamic with the aggregation space under the linear model and 2) we relate the excessive risk landscape of the above learning dynamic with ReLU activation with the lemma proved above.
Next, we start with considering a simplified linear model where the response is generated by the aggregation space without the ReLU activation, which amount the following generation model,
m 0 +e, m M,
(A.1)
Let Og be the t-iteration of the SGD under the generation model Eq. A.I which amounts the following process,
θ 0 7 vi(O,; m, Br),
0, - (m, 0,-1 yr) m.
(A.2)
Then, we denote
7i = 0, - 0",
as the centered SGD iterate, and,
1 NN N
Σ n
Then, we want to decompose the SGD iterate into bias and variance, denoted as 17 vpbis and Th respectively. The corresponding update rules are given by,
? bias
(I mm
bias )m-
bias
bias
77
770
variance
(I mm )m, Mr
variance
variance
variance
70
770
Thanks to (Jain et al., 2017), we have the following results for the excessive risk decomposition
Lemma A.S. Consider SGD iterates with linear model. Then, the excessive risk of the SGD under linear model can be decomposed into bias and variance as follows,
MM, E & NN)) < (v VViiss-. + v variaace)
(A.3)
2
where
v vbias
MM, E(nn
bias
biiss]).
and
V Variance
M, EI
Proof. The result can be obtained by simply following the procedure in (Jain al., 2017) by treating M as the data covariance matrix.
Then, thanks to the analysis (Zou et al., 2021b), we have a comprehensive understanding of the above iterative process of SGD and have the following results.
15

---

Learning Algorithm on Graph
Lemma A.6. Under The bias and variance of the SGD iterates with respect M is upper bounded by,
bias: = (M, E M
bias
@
ON
hins
B::
2
1 N-1N-1
I N
ΣΣ (M
@ 17
biass])
1=0 k=t
and
variance = (M, Elmn' & 'N'
N-1N-1
$ N
Σ Σ (I-
MM E El @ n m)""))
k=t
Proof. The result can be obtained by simply following the proof for Lemma B.3 in (Zou et al., 2021b) by treating M as the new data covariance matrix.
Next, we present the proof for the upper bound and lower bound for the excessive risk of SGD.
Lemma A.7 (SGD Excessive Risk Upper Bound). Consider SGD with tail-averaging with initialization Og- = 0. Suppose Assumptions 3.1, 3.2, 3.3 and 3.4 hold and stepsize satisfies y S 1/ tr(M). Then the excessive risk SGD under one-layer GNN can be upper-bounded as follows:
A(0 agd (N, G:7)) & SGDBias SGDVariance,
SGDBias
>2
exp
NrM) 0
Mp
+
-10011122 M
0² 1
SGDVariance
M
h2
N2?2
Σ H3
N
k2
where k1, h2 E [d] are arbitrary.
Proof. Consider the SGD iterates without ReLU activation that is given by,
0.11 0. - (m, 0, ye)
m.
m, M.
The SGD iterates above amounts linear model with respect to the aggregation space M. Then, by Lemma A.1, Lemma A.3 and Lemma A.2, we get that the above SGD iterates with respect to M also has bounded fourth-moment and model noise.
This means that we can immediately apply the results from By Lemma A.4, we can derive the excessive risk by considering the simplified iterates without the ReLU activation that is given by Eq. A.2.
By Lemma 1, and Lemma A.2, we have that the math-moment and the modelling noise of the SGD iterate with respect to the aggregation space is bounded. This means that we can immediately apply the bias variance decomposition and the SGD iterate bound process above with respect to M.
Then, we can follow the arguments in (Zou et al., 2021b) and obtain the desired result by involving Theorem 5.1 in (Zou et al., 2021b).
The ReLU activation does not affect the overall excessive risk landscape as given by Lemma A.4.
Lemma A.8 (SGD Excessive Risk Lower Bound). Suppose the stepsize satisfies y S 1/p Then the excess risk can be lower-bounded as follows:
A(Oaga (N, G; SGDBias SGDVariance,
16

---

Learning Algorithm on Graph
SGDBias
exp -N |
72
SGDVariance
o²
kk* N2
Σ
1100
M
7
Σ p
N
M1 E>
1>
where k* max(k: : Pa 2 1/(N))), and kt = max(k: pi 2 2/(3
Proof. The results are obtained through a similar argument as the upper but involving Theorem 5.2
Then, combining the two lemmas, upper bound and lower bound above, immediately obtain the result for Theorem 4.1.
B. Excessive Risk of Ridge
In this appendix, we present proof for characterizing the excessive risk of Ridge in our setting.
We denote G X be the data matrix associated with the aggregation space. Then, recall that the standard ridge regression equivalent the following least square problem,
arg min DO -y11 + 211011
We denote Rrddee (N; A) to be the solution to the optimization problem above. Then, we have the following bias-variance decomposition of Ridge with respect to the aggregation space. Lemma B.1. For any O, have that
A (N;; RidgeBias + Variance,
where
RidgeBias =
2
Ridge Variance =
.. [tr ((D + '' -XI)
where the expectations are taken over the randomness of the training data matrix
Proof. First, it is known and easy to derive that the solution of ridge regression takes the form
i Ridge A) (D -D
where D is the data matrix and y is the response vector. Then, according to the definition of the loss function L(0), we have
E L O Riidge AN:]
= E (v ORidgo (N; A), m)
E [00 m) (RRidgo (N: A), m) 2 + E (v- (0' mm)²
+ 2E k00 m) (ORidgo (N: A), m\] (y (0' m))
ORidoo (N; 0 11 L(0")
17

---

Learning Algorithm Graph
where the last equation follows from the modelling assumption that the expected value of noise is zero. Then, regarding 0* M let y (0", m) be the model noise vector, have
B Ridde (Neigge(NNN)) (N
Riige (N; A) 0* l[
I -IY- -0
[I AI (D0* + 0- 1
M
[I DO
DØ 001
bias
(I
AD) D 2
M
variance
where in the last inequality again follow from the modelling assumption that E(e 0. More specifically, the bias error can be reformulated
RidgeBias
E (D [D D
DD Ill 0-)
B [[ D
(I) -100
MMD D + XI)
In of the variance error, note that by Lemma A.2 we have E/cc" D I²I, then
RidgeVariance E || AI) -D cl
T cc' D(D T + AI) =E [tr (D AI) LD = = E [tr (D - D(D D AM)]
With the bias-variance decomposition above, can follow simple extension of Lemmas 2 & 3 in (Tsigler & Bartlett, 2023) for characterizing the excessive risk of ridge regression. Next, we show how to extend their results into our setting. To do so, we decompose the result of Theorem 4.2 into upper bound and lower bound in similar manner.
Lemma B.2. Let 2 be the regularization parameter, v the training sample size, f Pa be the eigenvalues of M in descending order and Oridge (N; be the output of ridge regression. Then
A(Bridge (N; A)) RidgeBias + Ridge
and there some absolute constant b L. such that for
A -.>*
k = min
k bppt1
n
the following holds:
A A Σ
Eiskiidee
RidgeBias z
-10011
N
+ -1001122 IRMaiae 100
{
kridge
k*
N Dishe Jade
RidgeVariance o².
N
(A Eist Lizie 11)
Proof. By involving Lemma A.4, we can relate the excessive risk of ReLU Ridge regression with the linear model. Then, by Lemma B.I and applying Lemmas & in (Tsigler & Bartlett, 2023) for characterizing the excessive risk ridge regression and the extension Theorem B.2 in (Zou et al., 2021a) on the aggregation space M, we immediately obtain the result above.
18

---

Learning Algorithm Graph
Lemma B.3. Let X 2 0 be the regularization parameter, be the training sample size and Origge (N; be the output of
ridge regression. Then
A rirrigo (N: A)) S RidgeBias RidgeVariance,
where,
+ Σ ki M1) 2
RidgeBias
-1001 014 zidge
N
M-
+110"1
Myiidgn 100
Kfidge
N NE Nii Di>k Kiidge
Pi
RidgeVariance 0²
(A+ Eisk
m.)
where Krddge == min {k: buu+1 S (A+ Hi)e4/))/
Proof. The argument similar to the lower bound above. Since the choice kidge is to ensure the sharpness the upper bound, we can relax this condition to an arbitrary [d] and still maintain valid upper bound.
C. Proof of the Effect of Graph Structure
In this section, we present proof for the Theorem 4.3. We decompose the proof for Theorem 4.3 into two parts: 1) for the power-law graph and 2) for the regular graph. We start with restating the results of Theorem 4.3 into two corresponding lemmas and proof.
Lemma C.1. Consider a power-law graph 9p with graph matrix Gp whose eigen-spectrum is characterized by Eq. 4.1 with a large enough 3. Then for every \ for ridge regression, there exists a choice for " for SGD such that for sufficiently large N, we have
(Noad((N, 7p) & A ((Oridge Gpi A)).
Proof. By Theorem 4.1, we know the excessive risk of SGD under our setting is given by the following.
SGDRisk S
N2
1 1
+
100 ||2
Mey
SGDBiae
(C.I)
h
(02
0
Nn
Σ
i>k2
SGDVare
where the parameter kı, k2 E [d] can be arbitrarily chosen.
Then recall the lower of the risk achieved by ridge regression with parameter A:
X
RidgeRisk >
| 1| 1 1
+
1|00112 M
+
RidgeBias
(C.2)
2
N
2
RidgeVariance
where ā x 14 and min(k: Nyp < 2}.
For the following analysis, we set k,, ho 1* for the excessive risk of SGD and divide the analysis into bias and variance.
19

---

Learning Algorithm on Graph
Bias. By (C.1) The bias of SGD is given follows,
SGDBias S 12222
||exp(-NNMM00 lM + +1001| Mu
From the equation above, can observe that the bias of SGD can be decomposed into two intervals: 1) i I k* and 2)
i >> k*.
We start with the second interval. For i > kt, we have that,
SGDBias(k's oo] = |10"1| M
RidgeBias(k"" oo]-
For i S k", the order of the eigenvalue and eigenvectors are preserved and we can decompose each term of bias as follows,
SGDBias[i] = (1)) N2 exp (- 21, (221
Similarly, we can decompose each term of the bias as of Ridge as,
RidgeBias(i] X (1
p4
Now, we can divide the analysis into cases: Case I: '> tr(M) and Case II: x s tr(M).
For Case It, we can pick v = 1/2 and obtain that that,
X
SGDBias[i] (i)
2
exp
RiageBias(i] exp
2
because 2NNp; >> 0, have that,
RidgeBias[i]
For Case II: we can pick 1/ Lr(M) and obtain that that,
(0" [1)) tr)
SGDBias
exp
-2N (2NN)/t((M)
N2
X tr LM)²
(0
exp
22 (aNNu/Lr(M)
N2N
tr(M)
[iage
exp
(-2N
(2(N)/tr(())
By definition of X, we have that À $ Nuw- and obtain that
RidgeBias[i] tr(M)
exp 22 (r())
(Nu=-)²
By the choice of model 1 33 as B increase, we have that tr tr(M)/Px decrease. Therefore, we can set 3 large enough so that
(N exp 22Nu/ttr(M) (NNu)tr(M)).
tr(M)²
20

---

Learning Algorithm on Graph
Then, arrive that,
SGDBias[i| 2 RidgeBias(]]
tr(M)
exp (- p// (-2Npt/tr((M))
(Nux-)}
RidgeBias(i].
Therefore, combining the results above, have that
SGDBias S
RidgeBiasBoud.
Next, let's consider variance. Again, by the excessive risk upper bound of SGDD, we have that
(1
0 l
SGDVariance
+
Nup Σ 1
N
1>
Similar to the bias analysis, divide the analysis into cases: Case I: X 2 tr(M) and Case II: A S tr(M). For Case I: A 2 tr(M), we pick 7 = 1// as for the bias:,
0
k*
N
SGDVariance 1
M
0
2
N
2
substitute the premise that 0
((1):
2 ((1) 0²
Σ
X
i>
O(1 Ridge Variance
RidgeVarians Variance
For Case II: 5 tr(M);, we can pick 1) = /rLM as for the bias and obtain that
0
k-
N
SGDVariance (1 +
M
Σ
m3
G2
N
tr(
0
2
k.
N
$ (1+
Σ
02
N
X
i>
Similarly, by the premise:
k-
N
S
00)1)
0²
Σ
X
i>
+11) Ridge Variance
S Ridge Varianar
Therefore, have that
SGDVariance X
RidgeVariance
Combining all the result above, we have that so long as 3 is large enough, there always exists an r such that
SGDRisk X RidgeRisk.
This completes the proof.
21

---

Learning Algorithm Graph
Lemma C.2. consider regular graph 9r with graph matrix G. whose eigen-spectrum is characterized by Eq. 4.1 with small B. Then for every choice of Y for SGD, there exists a X such that,
A(Oridee (N, G X²) & (0g (N, Gr;
Proof. Recall that to show that ridge is comparable with SGD in regular graph is enough show that there exist 8 small enough, so that for every y for SGD can always find À for Ridge to achieve
RidgeRisk X SGDRisk.
Similarly, by Theorem 4.1, we have the excess risk lower bound of SGD given by,
SGDRisk
122 N2
exp
(-
01
M..
+
+10011
|
M2
SGDBias
o²
kt
N2
Σ S>
Σ
N
M
ES
SGDVariance
where f1.... Pd are sorted eigenvalues for M, max X L/(Nn)), and k max(k: du 2 2/(3Nn)) Similarly, by Theorem 4.2, we have the excess risk upper bound of ridge given by.
À N
RidgeRisk
110
M
+
1 1
ridge
zidge
RidgeBias
Kridge
NExx DisRi
+ o².
vidge
N
X
RidgeVariance
where J1.... Pa are the sorted eigenvalues for M in descending order, and
Kidge == min k: bA++1 S (A+ Eni/mn
1>k
Similar to the previous proof, we can decompose the risk profile into bias and variance and then compare them separately.
We start with aligning the risk profiles of SGD and ridge by picking the ridge regression regularization
X
Σ Pi.
1>
Doing so leads to kidge k*
Variance. Then start by comparing the variance. We denote,
x- Σ
By the choice of X", we have that,
x
π
22

---

Learning Algorithm on Graph
Then, have the variance for Ridge as,
RidgeVarians Variance $
S0².
k-*
+
N
Σ
N
(X+)2 s>k*
2/
k* + N21 Σ 11
N
1>k"
0²
k-
+ N2 Σ 1
N
1>k
0
M
Mi
P1
VarVaaiecce
Therefore, we have that
RidgeVariance S
SGDVariance
Next, we focus on the bias. Under same set up as the variance, the Ridge bias is given by,
RidgeBias S
110
+ |10 |10 M
N
M
Bias. Similar to the previous analysis, we can decompose the bias of Ridge into two intervals: 1) S k- and 2) i k
We start with the second interval. For i k*, ., immediately obtain,
RidgeBias(kk* oo] = | 1| M
=SGDBias(k* o0].
For i I k.",,, similar to the previous analysis, decompose each term of bias bound follows,
X
RidgeBias [i] (0 (0)
N2 f1
X² n
(0 (1))
N μu r72
exp (2nNpx)
exp
2nNNis ps)
(i)
N2
exp
- 1-2n/N1 pi)
82212 exp N2
SGDBias exp 22/NN1
Similar to the analysis of variance, we have that,
X- 1
11
and consequently, we have,
0()=
Then, we have that,
RidgeBias(i] SGDBias exp 2n/N14
SGDBias exp (2):HH))
23

---

Learning Algorithm on Graph
By definition of Xt, have that,
n/ S n x ((1)
Then, we arrive
RidgeBias[i] x SSGDBias
RidgeBias S SGDBias
Combining all the results above, we have that there exists an À such that
RidgeRisk & SGDRisk.
Then, combining the result from the two lemmas above, we immediate obtain proof for Theorem 4.3.
D. Stacking GNN Layers
In this appendix, we present a proof for Proposition 4.5 and further discussion on the over-smoothing of GNNs.
Proof of Proposition 4.5. First recall that the definition of G()) is given by,
G(I) II G.
i=1
Without loss of generality, we may assume that
(G 2 (G).
Then, by the definition above, we have that,
ui( (G((++))
M1 G(l + 1))
p
(G)
1 (G)
m (G(()) (G)
My (G()) (G)
Then, by Assumption 3.4 and the premise that
(G) 2 (G),
then we have that,
(G +1)) (ā())) (G)
My G + 1)) (G (G)
m. (G(I)
M, ((())
(G()))
P3 (G(()
24

---

Learning Algorithm on Graph
E. Extended Related Work
In this section, we provide a comprehensive overview of key literature closely related to the theoretical analysis presented in this paper. Specifically, we discuss three primary areas: (1) theoretical understanding of Graph Neural Networks (GNNs), (2) excessive risk analysis of learning algorithms, and (3) spectral graph theory.
Theoretical Understanding of GNNs. Due to the empirical success of GNNs, there is a growing body of theoretical work that investigates their expressive power and generalization capability. The expressive power of GNNs, referring to their capacity to distinguish different graph structures, is often assessed by comparing GNN models to classical graph isomorphism tests, such as the Weisfeiler-Lehmar (WL) test (Leman & Weisfeiler, 1968; Jegelka, 2022; Sato, 2020; Zhang et al., 2023a;b; Xu et al., 2018). Generalization analyses explore how GNNs perform on unseen data, under different architecture (Tang & L Liu, 2023) or using complexity measures (e-g.. VC-dimension, Rademacher complexity)LL., 2021; Ma et al., 2021; Liao al., 2021), Neural Tangent Kernel (NTK)(Du et al., 2019), and information-thheoreie tools (mutual information, entropy) (Verma& & Zhang, 2019; Zhu et al., 2021). These studies primarily focus on factors like architecture and input graph characteristics, and remain orthogonal to our analysis. In addition, there is a recent works that tries to establish a theoretical connection between the topology-an -awaeey-swareness (how well graph structure is captured) of GNN and its generalization performance (Su & Wu, 2024).
A related line of research examines the convergence behavior of GNN learning algorithms (Chen et al., 2017; Huang et al., 2018; Chen et al., 2018; Awasthi al., 2021; Li al., 2018; Oono & Suzuki, 2020). Such studies typically provide convergence rates but remain restricted to the interpolation (noise-free) setting and offer limited insights into how graph structures influence algorithmic performance. It remains largely unexplored how different graph characteristies (e.g., power-law vs. regular) systematically affect the generalization performance of algorithms when noise is present. Our work addresses precisely this gap. providing a novel framework linking graph structure explicitly to the generalization performance of learning algorithms such as SGD and Ridge regression.
Furthermore, a significant practical challenge in GNN design includes issues of oversmoothing (Rusch et al., 2023) and oversquashing (Topping et al., 2021). Oversmoothing occurs when deep message-passingg leads to indistinguishable node representations, reducing model performance in tasks that require distinct embeddings. Oversquashing refers to the over- compression of information from distant nodes, impeding long-range dependency capture in deep networks. Our theoretical analysis of learning algorithm behavior with respect to graph structure can also provide new perspectives and analytical tools for investigating such phenomena, particularly oversmoothing.
Excessive Risk of Learning Algorithms. The analysis of excessive risk is central learning theory literature (Dhillon et al., 2013; Lakshminarayanan & Szepesvari, 2018; Jain al., 2017; Zou et al., 2021b; 2023; Tsigler & Bartlett, 2023). Extensive research investigates the generalization properties of classic learning algorithms, notably Stochastic Gradient Descent (SGD) and Ridge regression. Non-asymptotic risk bounds have been thoroughly characterized for SGD and Ridge in both under- and over-parameterized regimes (Hsu et al., 2012; Kobak et al., 2020; Dieuleveut et al., 2017; Bach & Moulines, 2013; Jain et al., 2018; Défossez& & Bach, 2015; Paquette et al., 2022; Tsigler & Bartlett, 2023). For instance, constant-stepsize SGD with tail-averaging achieves minimax-optimal rates for least-squares tasks (Jain et al., 2017). Recent works also provided detailed excess-risk characterizations for Ridge regression, depending critically on spectral properties of data covariance matrices (Dobriban & Wager, 2018; Hastie al., 2022: Wu & Xu, 2020; Xu & Hsu, 2019). Nevertheless, how these theoretical insights extend to graph learning scenarios, particularly within GNN frameworks, remains largely unexplored. We expand this knowledge by explicitly analyzing and comparing the excessive risk of SGD and Ridge regression in graph-structured settings, thereby shedding new light on the impact of structural characteristics on learning algorithm performance.
Spectral Graph Theory. Spectral graph theory studies graph properties via eigenvalues and eigenvectors of associated matrices (e.g., adjacency, Laplacian matrices))Chung, 1997: Spielman, 2012: Pósfai & Barabási, 2016; Van Mieghem, 2023; Gera et al., 2018). Foundational results, including the Earron-Frobenius theorem and Cheeger's inequality, provide insights into the connectivity, robustness, and spectral characteristics of graphs. For example, power-law graphs (characterized by heterogencous degree distributions and heavy-tailed eigenspectra) differ markedly from regular graphs (uniform degree distributions and evenly spaced eigenspectra)(aalouu 2001; Easley et al., 2010). These contrasting spectral profiles are essential for interpreting network structure, influencing information propagation dynamics, robustness, and learning behavior. Our theoretical framework leverages spectral graph
et al., 1999; Chung et al., 2003; Farkas et al., 2001; Goh et al.,
25

---

Learning Algorithm Graph
theory to explicitly relate eigenvalue decay patterns (e-g., power-law versus uniform) the performance characteristies of learning algorithms. Thus, spectral graph theory forms a foundational tool in analysis, directly linking structural properties of graphs to algorithmic performance differences.
Overall, this paper synthesizes these theoretical domains- GNN expressivity and generalization, excessive risk of algorithms,, and spectral graph theory-to provide new insights into the interplay between graph structures and learning algorithms. Our work represents a step towards a deeper theoretical understanding graph-based learning, offering tools and analyses applicable broadly across various graph learning contexts.
F. Experiment Details
In this appendix, we present additional details on our experimental study. This appendix focuses on additional details on the lestbed, graph generation model and hyper-parameter search.
F.I Testbed
Our experiments were conducted on a Dell PowerEdge C4140, The key specifications of this server, pertinent to our research, include:
CPU: Dual Intel Xeon Gold 6230 processors, each offering 20 cores and 40 threads.
GPU: Four NVIDIA Tesla V100 SXM2 units, each equipped with 32GB of memory, tailored for NV Link.
Memory: An aggregate of 256GB RAM, distributed across eight 32GB RDIMM modules.
Storage: Dual 1. 1.92TB SSDs with 6Gbps SATA interface.
Networking: Features dual 1Gbps NICs and Mellanox ConnectX-5 EX Dual Port 40/100GbE QSFP28 Adapter with GPUDirect support.
Operating System: Ubuntu 18. 18.04LTS.
F.2 Graph Generation Model
For our experiment, we rely on the NetworkX python (Hagberg et al., 2008) library. In particular, we use the default implementation regular graph generation and Barabasi-Alben model (P6sfai & Barabási, 2016) from the Networkx library. The Barebási-Albert (BA) model a widely used generative model for creating scale-free networks, which are networks characterized by a power-law degree distribution. The core idea behind the BA model is to capture the "preferential attachment" mechanism, where new nodes more likely to connect existing nodes that already have high degree of connections. This reflects many real-world networks, such as social networks, where popular individuals (nodes) tend to attract more connections.
Rough Procedure of Barabási- model. The Barabási-Allert model generates a network through the following steps:
1. Initialization: Start with small connected network of mo nodes.
2. Growth: Add one new node at time. Each new node forms edges that link it to existing nodes.
3. Preferential Attachment: The probability that new node will connect existing node i is proportional the degree of node i. Formally, the probability P(i) that the new node connects to node i is given by:
k
P(i)
Σ,ky ky
where k; is the degree of node i and the sum is over all existing nodes.
Hyperparameters
The BA model has two key hyperparameters:
.m The initial number of nodes in the network.
26

---

Learning Algorithm on Graph
The number of edges that each new node will add when it is introduced the network. This parameter influences the density and the structure of the resulting network.
These hyperparameters directly affect the network's 's topology and are crucial in determining the characteristics of the scale-free network generated by the BA model. We adopt the default mo from the implementation of NetworkX library, and set m to be 3, which is commonly used value to model real-life network.
F.3. Hyper Parameter Search for Learning Algorithm
The main syper-parameter for SGD is the learning rate 77. In the statement of the results for the excessive risk of SGD, there requirement for the learning that relates to the eigenspectrum of the data covariance. For our experiment, we have access to the full information of the data covariance. As such, we simply infer a possible range for the learning rate and do grid research for the learning rate in the range. The search process is done through an independent (validation) dataset. Therefore, there is interference to the testing process.
Similarly, the main pyper-paramend for Ridge is the regularization parameter X. For X, there is no theoretical guidance from the analysis on its possible values. Therefore, we do a grid research on a large array of À values ranging from [0.1, 1000). The research process is similar to the one for the learning rate.
G. A Additional Discussion
In this section, we present some additional discussion on the formulation of the problem.
G.1. Problem Formulation and GNNs
Message-Passing Graph Neural Networks. The computation in GNNs can be viewed message-passing along graph structure (Jegelka, 2022). At each round 1, the new embedding x for vertex is updated through a series of aggregate and combine steps as outlined below:
AGGREGATE((x) (1-1) (N))))
( COMBINE(X (1-1) .m: (m)),
(1)
where 2r(0) is initialized as the feature vector x (ii represents the neighbors of vertex i, and m, denotes the aggregated representation round I. Different GNNs differ in specific implementation of the AGGREGATE and COMBINE functions. Essentially, a GNN serves as an embedding function that integrates the graph structure and node features to produce an aggregated representation vector of node c. This representation is subsequently processed by read-out function (e.g., a ReLU layer) to generate predictions.
One-round Graph Neural Network. In this study, we follow a similar setting to (Awasthi et al., 2021) and focus our main discussions on one-round GNN that consists of an aggregation operation followed by a readout operation. We interpret the aggregation step graph matrix G acting upon the feature matrix X. Formally, we decompose the one-round GNN into two distinct components. The first component aggregates node features via specified aggregation operator and the chosen graph matrix G. producing an intermediate representation space denoted by M:
M = G
(G.I)
Here, . represents the intermediate aggregated feature space, and assume without loss of generality that it is subspace of Hilbert space H. Different choices of the aggregation matrix G and the aggregation operation o allow us to recover various canonical graph neural network architectures. Below, we provide comprehensive discussion of several prominent examples:
Graph Convolutional Networks (GCN), When the graph matrix is chosen as the symmetrically normalized adjacency matrix A = D-1 AD 1122, where À = A + I and D is the degree matrix of A, and the aggregation operator simple matrix multiplication, recover the standard GCN formulation proposed by (Kipf & Welling, 2017):
MaeN = Ax.
(G.2)
27

---

Learning Algorithm Graph
GraphSAGE (Mean Aggregation). When the graph matrix G corresponds to row-normalized adjacency matrix Arw = D- where A again denotes adjacency with self-loops, recover the mean-aggregation variant of Graph- SAGE (Hamilton et al., 2018). Specifically:
MSAGE = A. X.
(G.3)
Here, each node's representation updated using the average of its neighbors' features, incorporating self-information well.
Graph Attention Networks (GAT). For Graph Attention Networks (Veličković al., 2017), the aggregation achieved by learned attention mechanism rather than fixed normalization. Here, the aggregation operator represents element-wise multiplication weighted by attention scores, resulting in data-dependent and adaptive G(X):
MGAT Gau X,
(G.4)
where Gatt (X) encodes attention-based weights, dynamically computed through neural attention mechanism.
Simplified Graph Convolution (SGC). By extending the GCN aggregation step to multiple rounds but merging linear operations into a single step, the simplified graph convolutional network (SGC) (Wu et al., 2019) is recovered. Formally, if the K-th power of A, we have:
MsGc A
(G.5)
This corresponds to applying multiple rounds of smoothing/aagrregation a simplified, efficient manner without interme- diate nonlincarities.
This comprehensive discussion demonstrates how the choice of graph matrix G and aggregation operation yields various canonical GNN variants, each capturing different relational structures and neighborhood aggregation strategies.
28


Reviews:
[{"review_id": "YdlBfDEhqx", "reviewer": "Reviewer_mnhf", "summary": "This paper explores the interplay between graph structure and learning algorithms in Graph Neural Networks (GNNs), focusing on generalization performance (excessive risk) in the presence of noise. Extending learning theory to GNNs, it derives excessive risk profiles for Stochastic Gradient Descent (SGD) and Ridge regression, and linking these to graph structure via spectral graph theory. Key findings include: (1) SGD outperforms Ridge on power-law graphs, while Ridge excels on regular graphs; (2) stack GNNs introduce non-isotropic effects on excess risk, offering new insights into over-smoothing. Empirical results on synthetic graphs support the theory.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for the positive comments and thoughtful questions! These greatly help us in making our paper better, and we appreciate the opportunity to address your concerns and questions here.\n\n## Related Works in Over-smoothing\n\nThank you for recommending relevant literature. We will incorporate the suggested references into our revision to enrich the discussion around the over-smoothing phenomenon in multi-layer GNNs.\n\n## How the power-law decay $\\beta$ and graph size affect the results\n\n- The parameter $\\beta$ controls the rate of eigenvalue decay in the graph matrix spectrum. A larger $\\beta $ results in a faster decay of the eigenspectrum, similar to that seen in power-law graphs, while a smaller $\\beta$ leads to a more uniform eigen-spectrum, akin to that of regular graphs. We utilize $\\beta$ to interpolate between these two regimes. Our theoretical results (Theorem 4.3) show that when $\\beta$ is large(the graph exhibits stronger power-law behavior), SGD outperforms Ridge regression. Conversely,  when $\\beta$ is small (the graph is more regular), Ridge regression becomes preferable.\n- Regarding the graph size $N$, it corresponds directly to the number of learning samples in our setting. Our analysis focuses explicitly on the generalization regime, requiring sufficiently large sample sizes for meaningful theoretical comparisons. Once this condition is met, increasing $N$ further does not affect the relative performance of SGD and Ridge—their comparison is primarily governed by the graph spectrum, not the graph size.\n\n## Idealize eigenvalue model and sensitivity of results\n\nThank you for the insightful question. Our theoretical results are not tightly dependent on the exact form of the power-law decay model. We adopt this model primarily for analytical clarity, but the core insights extend to a broader class of spectral decay behaviors.\n\nThe essence of our findings (e.g., Theorem 4.3) lies in the rate at which the eigenvalues of the graph matrix decay, regardless of whether this follows a strict power-law. A faster-decaying spectrum—as often observed in graphs with power-law-like structures—tends to favor SGD. In contrast, a slower-decaying spectrum—as seen in more regular graphs—makes Ridge more favorable.\n\nTherefore, even in real-world graphs (e.g., social or internet networks) that only approximately follow a power-law and may contain additional noise or structural irregularities, our main theoretical tools (Theorems 4.1-4.2) remain applicable, and our theoretical conclusions regarding the relative performance of SGD and Ridge remain qualitatively valid. Extending our analysis to incorporate more flexible spectral models is an interesting direction for future work (please also see our response to the potential extension to the random graph model for Reviewer 8EPb).\n\nThank you again for your diligent review, and we will incorporate the discussion above into the revision. We hope our response has satisfactorily addressed your questions and concerns.", "claims_and_evidence": "The claims are generally supported by clear and convincing evidence. The paper derives excess risk bounds (Theorems 4.1 and 4.2) for SGD and Ridge, connecting these to graph structure through spectral properties (Theorem 4.3), and extends the analysis to stacked GNNs (Proposition 4.4). These are backed by mathematical proofs and empirical validation using synthetic graphs.", "methods_and_evaluation_criteria": "Overall, the methods are well-founded. Using synthetic graph models (e.g., Barabási-Albert) as benchmarks is reasonable for controlled theoretical validation, though incorporating real-world datasets could enhance practical relevance.", "theoretical_claims": "I reviewed the proofs for Theorems 4.1 (SGD excessive risk), 4.2 (Ridge excessive risk), 4.3 (graph structure effects), and Proposition 4.4 (multi-layer GNNs) in the main text and corresponding Appendix. To my knowledge, the proofs appear mathematically sound, though the reliance on idealized eigenvalue models (Eq. 4.1) could limit real-world applicability.", "experimental_designs_or_analyses": "Overall experiments on synthetic datasets can support the theoretical findings to some degree. \n\nHowever, as mentioned earlier, the paper lacks validation on real-world datasets, which could help identify practical limitations. \n\nThe author should also conduct a sensitivity analysis on graph structure hyperparameters, such as performance variations under different β for graph generation and different graph sizes.", "relation_to_broader_scientific_literature": "Existing theoretical studies mainly focus on the convergence rates of learning algorithms in the interpolation regime (noise-free), providing only a coarse link between graph structure (e.g., maximum degree) and learning algorithms. In contrast, this paper offers a deeper exploration of how regular and power-law graphs influence SGD and Ridge, connecting their spectral properties to generalization bounds.", "essential_references_not_discussed": "I think the author conducted a relatively comprehensive literature review in both the paper and the appendix. However, some relevant papers on the over-smoothing problem in multi-layer GNNs could further enrich the discussion:\n\n[1] Oono, K., & Suzuki, T. (2020). 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.\n\n[2] Li, Qimai, 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, vol. 32, no. 1. 2018.", "other_strengths_and_weaknesses": "Overall, this paper is well-written, with a clear organization and a logical proof structure that makes it easy to follow. The author effectively links graph structure and learning algorithms through spectral graph theory, deriving interesting insights that are validated by empirical studies.\n\nAs partially noted earlier and acknowledged by the authors—a commendable practice that should be encouraged—this paper also exhibits certain limitations:\n\n(1) The idealized eigenvalue model (Eq. 4.1) may not adequately capture the complexity of real-world graph structures. Furthermore, the absence of evaluations on real-world datasets restricts the applicability of the theory to practical use cases.\n\n(2) The theoretical analysis primarily focuses on the interplay between graph structure and learning algorithms, overlooking the role of node features. A future study jointly examining the interactions among all three—graph structure, learning algorithms, and node features—would be a valuable extension.\n\n(3) The theory is limited to one-layer or linearized GNNs and does not extend to more complex models, which could broaden its scope and relevance.", "other_comments_or_suggestions": "no", "questions_for_authors": "(1)\tEquation 4.1 assumes a power-law decay (β). I am curious about how this parameter affects the results, as well as the impact of other hyperparameters, such as graph size.\n\n(2)\tHow sensitive are your results to deviations from this model in real graphs? For example, some graphs sampled from social or internet data exhibit power-law characteristics, but they may also contain more noise. I would be interested in seeing an analysis of this.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TPCyJNB65X", "reviewer": "Reviewer_ERj6", "summary": "The authors analyze the excess risk of stochastic gradient descent (SGD) and ridge regression for certain GNNs. Their theoretical analysis, grounded in graph spectral theory and theoretical results from Benign overfitting, demonstrates that SGD can outperform ridge regression on power-law graphs, while ridge regression can be more effective on regular graphs. They validate these findings through experiments on synthetic data.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for thoughtful comments and questions. These greatly help us in making our paper better, and we appreciate the opportunity to address your concerns and questions here. (Please note that the order of our responses may not exactly follow the sequence of your comments.)\n\n## GNN Formulation and Transferability of Results\n\nWe would like to clarify that our formulation is applicable to one-layer GNNs, as also noted by other reviewers. In lines 204–207, we show that it recovers standard GCNs and generalizes the one-layer GNN setting presented in [1]. Furthermore, our empirical studies use standard GCN layers from DGL, and the observed consistency with our theoretical predictions demonstrates that the conclusions are transferable to real-world GNN architectures.\n\n## Graph Topology and Spectrum of $\\mathbf{M}$\n\nThank you for pointing this out. While $\\mathbf{M}$ denotes the covariance of aggregated representations, it is directly shaped by the graph matrix used in the aggregation step. Since the spectrum of graph matrices is known to reflect graph topology, the spectrum of $\\mathbf{M}$ inherits key structural properties of the graph. This enables our graph-dependent theoretical results (e.g., Theorem 4.3 and Proposition 4.4). This connection is also empirically illustrated in Figure 2(c,d), where the spectrum of $\\mathbf{M}$ reflects structural differences in the graph (e.g., power-law vs. regular).\n## Suggested Reference\n\nThank you for pointing out these relevant references. While the cited works share a similar goal of understanding GNN generalization, our paper explores a distinct direction—specifically, the interaction between graph structure and learning algorithm. As a result, our theoretical tools, assumptions, and insights differ significantly. We will include these references in the revised manuscript to enrich the related work section.\n\n\n## Discussion on Over-smoothing\n\nThank you for the thoughtful comment. We believe there may be a slight misunderstanding. Our theory does not contradict the established connection between oversmoothing and the spectrum of the graph Laplacian. Rather, our work offers a complementary perspective, focusing on how oversmoothing manifests in model performance, particularly excess risk, as GNN depth increases.\n\nA key insight of our analysis is that the effect of oversmoothing on generalization can also depend on the learning algorithm and the alignment of the ground truth with the spectral components. Specifically, our analysis shows that when the ground truth is concentrated in the head of the eigenspectrum, increasing GNN depth can actually benefit learning algorithms such as SGD, rather than harm performance. This is supported by our empirical results in Figure 3(c,d), where alignment significantly alters the impact of increasing GNN layers under SGD.\n\nWe appreciate the opportunity to clarify this and will revise the manuscript to highlight this distinction more clearly.\n\n## Missing Impact Statement\n\nThank you for noting this. We will make sure to include the impact statement in the revision. As this is a theoretical study, we do not see any potential negative societal impacts that need to be highlighted.\n\n## Assumptions 3.1–3.4\n\nDue to space constraints, please refer to our response to Reviewer 8EPb for a detailed discussion of these assumptions.\n\n## Clarification on Theorem 4.1\n\nThank you for the questions.\n\n- In line 243, we state that “$k_1,k_2 \\in [d]$ are arbitrary,” which means that $k_1$ and $k_2$ can be freely chosen within the valid index range $[1, d]$.\n- The definition of $k^*$ is given in lines 258–259, where it is explicitly constrained by the condition $\\mu_k \\geq 1/(N\\gamma)$. This threshold depends on the sample size $N$ and the step size $\\gamma$. In the asymptotic regime where $N$ is very large, $k^*$ could indeed approach the full matrix dimension, and Theorem 4.1 then recovers the asymptotic behavior of learning algorithms. However, in the finite-sample regime—which is our primary focus- we have $k^∗<d$.\n- As mentioned in lines 834–835, we omitted the lower bound proof because it is structurally symmetric to the upper bound, differing only in the use of Theorem 5.2 from [2]. We apologize for missing the reference for Theorem 5.2 and will correct this in the revision. If helpful, we are happy to include the full proof of the lower bound in the revision.\n\nWe appreciate the feedback and will revise the paper to clarify these points.\n\nAgain, thank you so much for the detailed comments, questions and suggestions. They are really helpful for improving our paper, and we hope our response has addressed the concerns and questions you had.\n\n[1] \"A convergence analysis of gradient descent on graph neural networks.\" Advances in Neural Information Processing Systems\n\n[2] “Benign overfitting of constant-stepsize sgd for linear regression”. In Conference on Learning Theory", "claims_and_evidence": "Some claims/statements are overstated. For example,\n- the authors do not analyze GNNs\n- The authors do not show clear connections between the graph topology and SGD/Ridge regression, but rather between the spectrum of the second moment of the aggregated features ,which liein  a latent space, and the learning algorithms", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked some of the proofs.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "see below", "essential_references_not_discussed": "see below", "other_strengths_and_weaknesses": "### Strenghts\n\n- The paper addresses an important and interesting question: How does graph topology affect learning? This is a fundamental problem in graph-based learning and has broad implications.\n- The results appear convincing and align with experimental observations. In particular, the authors provide clear and practical recommendations on when to use ridge regression versus SGD.\n- The paper is well-structured and clearly written, making the theoretical analysis accessible to readers.\n\n### Weaknesses\n- The authors claim that their \"generating model is very general,\" but this is misleading. The model does not allow for learnable parameters in graph convolutions, only in the final linear prediction head, meaning no real-world GNNs fall under this framework.\n- The assumptions (e.g., 3.1–3.4) are not clearly discussed or justified. It is unclear how restrictive they are or how they impact the conclusions.\n- Most of the assumptions and dependencies are formulated in the latent space rather than the graph space. While this simplifies the proofs (by leveraging prior work from non-graph domains), it raises concerns about whether the authors actually answer their original research question regarding graph topology.\n- The discussion on oversmoothing seems problematic. Oversmoothing is inherently tied to the spectrum of the graph Laplacian, independent of the learnable algorithm. The authors do not provide sufficient evidence to support their claims in this regard. \n\n### Minor\n- The observation that increasing the number of layers can be beneficial is not novel. Prior work has shown that a certain level of smoothing is useful when the ground truth is dominated by low-frequency components (see, e.g., [1]).\n- Many works on generalization explicitly depend on graph topological features, such as degree [2] or graph size [3], which the paper does not sufficiently acknowledge.\n- The impact statement is missing\n\n\n[1] Keriven, N. (2022). Not too little, not too much: a theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems, 35, 2268-2281.\n[2] Liao, R., Urtasun, R., & Zemel, R. (2020). A pac-bayesian approach to generalization bounds for graph neural networks. arXiv preprint arXiv:2012.07690.\n[3] Maskey, S., Kutyniok, G., & Levie, R. (2024). Generalization bounds for message passing networks on mixture of graphons. arXiv preprint arXiv:2404.03473.", "other_comments_or_suggestions": "See above", "questions_for_authors": "1. Why do the eigenvalues of $M$ correspond to the graph topology? Could you clarify this connection?\n2. How restrictive are assumptions 3.1–3.4? Could you provide concrete examples where they hold in real-world scenarios?\n3. In Theorem 4.1, how can $k_1, k_2$​ be chosen arbitrarily? What happens if $k_1$​ is larger than the matrix dimension itself?\n4. The proof of the lower bound in Theorem 4.1 is missing. Is $k^∗$ the maximum over all such $k$? Wouldn’t the maximum always be the matrix dimension, or would it be undefined in certain cases?\n5. How could your results generalize to actual GNNs used in practice? For example, do you see experimental evidence supporting this claim?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0RWjMTaIoy", "reviewer": "Reviewer_ECHh", "summary": "The paper studies how graph structure influences the learning dynamics and generalization performance of GNNs, going beyond traditional noise-free settings to analyze SGD and Ridge regression under moew realistic conditions. Using spectral graph theory, it establishes connections between excess risk and the graph structure, explores the impact of different graph types (regular vs. power-law), and offers guidance for algorithm design and selection.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for the positive comments and thoughtful questions. These greatly help us in making our paper better, and we appreciate the opportunity to address your concerns and questions here.\n\n## **Suggested Reference**\n\nThank you for highlighting this relevant work. While both papers aim to understand the generalization of GNNs, our focus and methodology differ significantly.\n\nTang and Liu (ICML 2023) study the impact of GNN architectures under the interpolation regime with noiseless labels in a transductive setting. In contrast, our work investigates the interaction between graph structure and learning algorithms (e.g., SGD vs. Ridge) in a noisy, classical generalization setting.\n\nAs a result, the two papers adopt different theoretical frameworks—stability and Lipschitz analysis in their case, versus bias-variance decomposition and spectral analysis in ours—and offer complementary insights: theirs on GNN architecture and ours on the interplay between learning algorithm and graph structure.\n\nWe will include this reference in the revised paper to enrich the related work section.\n\n## Specific G used in Section 4.4 and impact of architecture on the spectrum.\n\nThank you for the great question!\n\nIn our empirical study (Section 4.4), we use the normalized adjacency matrix, aligning with the standard GCN setup.\n\nYou're absolutely right — the choice of GNN architecture does influence how spectral information is processed. However, our paper focuses on isolating the coupled effect of graph structure and learning algorithms under a fixed architecture. This design choice allows us to clearly attribute differences in generalization behavior to variations in graph structure and learning algorithms, rather than architectural differences. Therefore, the comparison analysis (Theorem 4.3) studies the effect of graph structure with respect to the learning algorithm under an arbitrary fixed architecture.\n\nThat said, the theoretical results on excess risk profiles (Theorems 4.1 and 4.2) are general and remain applicable regardless of the specific GNN architecture. Therefore, the core insights of our comparison framework still hold. Extending this framework to jointly analyze how graph structure and architecture together influence the performance of learning algorithm is an exciting direction for future work and can offer a more comprehensive understanding of GNN.\n\n## Loss function\n\nThank you for the question. The loss function we use is the standard squared error loss, as specified in lines 170–177. This is a common choice in the learning theory literature [1,2] as well as prior GNN analytical works [3]. \n\n## Additional experiments with benchmark datasets\n\nThank you for the suggestion. We agree that evaluating on real-world benchmark datasets is valuable. While it is challenging to fully verify all aspects of our theory due to the lack of controllability in real-world data, we conducted additional experiments to assess the robustness of our conclusions on two widely used benchmark datasets with power-law structure: Cora (homophilic) and Chameleon (heterophilic), both available via the DGL library.\n\nFor these experiments, we followed the same experimental setup as in the main paper: a regression task was constructed following our analytical framework, and a vanilla GCN was used as the model. According to our theory, so long as the feature matrix satisfies our assumptions, the distinction between homophily and heterophily should not significantly affect the comparative performance of learning algorithms. Moreover, since both datasets exhibit power-law structure, we expect SGD to outperform Ridge.\n\nThe results below support this prediction: SGD consistently outperforms Ridge regression on both datasets. This provides further evidence that our theoretical insights hold across a range of graph structures, including both homophilic and heterophilic settings.\n\nCora\n\n| Sample Size (x10) | 1 | 5 | 10 | 50 | 100 |\n| --- | --- | --- | --- | --- | --- |\n| SGD | 5.68 | 2.67 | 1.32 | 1.08 | 1.03 |\n| Ridge | 9.68 | 3.85 | 1.53 | 1.12 | 1.06 |\n\nChameleon\n\n| Sample Size (x10) | 1 | 5 | 10 | 50 | 100 |\n| --- | --- | --- | --- | --- | --- |\n| SGD | 8.68 | 3.33 | 1.85 | 1.03 | 0.99 |\n| Ridge | 12.5 | 5.54 | 2.25 | 1.10 | 1.02 |\n\nWe will include these results in the revision to further strengthen the empirical support for our theoretical claims.\n\nThank you again for your diligent review, and we hope our response has satisfactorily addressed your questions and concerns.\n\n[1] “Benign overfitting of constant-stepsize sgd for linear regression”. In Conference on Learning Theory\n\n[2] “Benign overfitting in ridge regression.” Journal of  Machine Learning Research.\n\n[3] \"A convergence analysis of gradient descent on graph neural networks.\" *Advances in Neural Information Processing Systems*", "claims_and_evidence": "Evidence needed for the claim \"Most real-life graphs, particularly those used for academic benchmarks, are power-law graphs\" in line 340-341.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not check the proof.", "experimental_designs_or_analyses": "Yes. The experimental designs and analyses seem fine to me.", "relation_to_broader_scientific_literature": "Understanding the generalization ability of neural networks is a fundamental problem in learning theory. How would graph structure affects it is a meaningful question to study.", "essential_references_not_discussed": "The key contribution is to understand the geneneralization of GNNs, but it missed to discuss a paper on the very same topic: Towards Understanding the Generalization of Graph Neural Networks by Tang and Liu in ICML 2023. The paper also discussed how would different GNN architectures affect the generalization bound. I wonder what ditinguishes your result from theirs?", "other_strengths_and_weaknesses": "The paper is very well written.", "other_comments_or_suggestions": "Besides synthetic data, I wonder if you could verify your result on standard small benchmark datasets, including both homophilic and heterophilic ones?", "questions_for_authors": "1. What is the sepecific G used in Section 4.4? Also I wonder besides graph structure, isn't what architecture one uses also affects the spectrum (say GCN vs GIN).\n\n2. What is the loss function $l$ used in the analysis (line 264-266)? Are you just using the direct difference between the output and the label $y_t$?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bQlj9CSwDw", "reviewer": "Reviewer_8EPb", "summary": "This paper explores the relationship between graph structure and learning algorithms in Graph Neural Networks (GNNs), particularly in the context of generalization performance. Unlike prior work that primarily focuses on convergence rates in noise-free settings, this study extends those analysis to scenarios with noise, providing a more comprehensive understanding of learning dynamics in GNNs. To me, the paper's main contributions include:\n\n1. Theoretical Analysis of Excess Risk: The authors derive excess risk profiles for two learning algorithms, i.e., Stochastic Gradient Descent (SGD) and Ridge regression, when applied to GNNs. By leveraging spectral graph theory, they manage to establish a direct connection between excess risk and the underlying graph structure.\n\n2. Impact of Graph Structure: The study systematically compares different types of graph structures, particularly regular graphs and power-law graphs, to determine their effects on learning performance. The analysis reveals that graph topology plays an important role in influencing the behavior of learning algorithms in GNNs.\n\n3. Insights on Multi-Layer GNNs and Over-Smoothing: The authors uncover a growing non-isotropic effect in excess risk, which leads to a new perspective on the well-known over-smoothing issue in deep GNNs.\n\n4. Empirical Validation: Their theoretical findings are further supported by empirical experiments.\n\nOverall, the paper provides a rigorous theoretical framework that deepens our understanding of how learning algorithms interact with graph structures in GNNs. The results can have implications for both theory and practice.\n\n##update after rebuttal", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your positive comments and thoughtful questions! These greatly help us in making our paper better, and we appreciate the opportunity to address your questions here.\n\n## Explanation and Realism of Assumption\n\nOur assumptions are mild and broadly applicable in both theoretical and practical settings.\n\nAssumption 3.1 is a standard and mild assumption in statistical learning theory. Here, $\\mathbf{H} = \\mathbb{E}[\\mathbf{x}\\mathbf{x}^\\top]$ represents the second moment (or covariance) matrix of the input features. By definition, $\\mathbf{H}$ is always positive semidefinite. The condition $\\text{tr}(\\mathbf{H}) < \\infty$ is satisfied so long as the feature distribution has finite energy, which holds for most real-world data, including bounded, Gaussian, and sub-Gaussian/sub-exponential distributions.\n\nAssumption 3.2 is the fourth-moment control of feature vectors. It ensures that the covariance of quadratic forms of $\\mathbf{x}$ is not too \"wild\". This is a standard assumption used in the analysis of generalization, stability, and convergence in learning theory[2,3], and is equivalent to the commonly used bounded second moment assumption of the stochastic gradient in SGD analysis [1]. In particular, this assumption holds for Gaussian, sub-Gaussian and sub-exponential settings common in GNN applications.\n\nAssumption 3.3 states that the noise-weighted covariance $\\mathbb{E}[\\epsilon^2 \\mathbf{x}\\mathbf{x}^\\top]$ is bounded by $\\sigma^2 \\mathbf{H}$. This condition ensures that the noise remains controlled relative to the signal, which is a standard assumption in the analysis of both SGD and Ridge regression [2, 3]. It reflects the fundamental learnability of the problem under noisy supervision and guarantees that the problem is well-posed.\n\nAssumption 3.4 requires the graph matrix $\\mathbf{G}$ to be symmetric positive definite with bounded norm. This is a practically realistic and widely satisfied condition, as most commonly used graph matrices in GNNs (e.g., adjacency matrix, Laplacian, or their normalized variants) are PSD and have bounded norms.\n\nTogether, these assumptions are well-supported by prior work and satisfied by a wide range of data and GNN settings.\n\n## Random Graphs\n\nThank you for the interesting question. Our framework and results can indeed be extended to the setting of random graphs.\n\nIf we consider individual realizations from a random graph model (e.g., Erdős–Rényi or stochastic block models), our analysis still applies directly, as it is based on the spectrum of the graph matrix, which can be computed for any given instance. In this case, our theoretical results hold conditionally on the observed graph realization.\n\nTo generalize our results to the entire random graph model, the spectral properties of the graph matrix would need to be treated in a probabilistic manner. For example, rather than working with deterministic eigenvalues, we would analyze their behavior in expectation or with high probability. In such cases, our bounds and excess risk decomposition could be extended by incorporating concentration inequalities or spectral properties of random matrices.\n\nThis is a promising direction for future work, especially since random graph families are expressive and widely used in modeling real-world networks.\n\nThank you again for your diligent review, and we will incorporate the above discussion in the revision. We hope our response has satisfactorily addressed your questions.\n\n[1] \"SGD: General analysis and improved rates.\" *International conference on machine learning*. \n\n[2] “Benign overfitting in ridge regression.” Journal of  Machine Learning Research.\n\n[3] “Benign overfitting of constant-stepsize sgd for linear regression”. In Conference on Learning Theory", "claims_and_evidence": "The theoretical contributions of the paper are presented rigorously -- several theorems and propositions outlining the connections between excess risk and graph structure. While the full proofs are given in the appendix, their proof sketches appear correct to me. Moreover, the paper includes empirical results that validate the theoretical predictions. The experiments are designed to test key claims, such as the influence of graph structure on excess risk and the non-isotropic effects in multi-layer GNNs.", "methods_and_evaluation_criteria": "The theoretical analysis of this paper is grounded in spectral graph theory. The choice of excess risk as a key metric is reasonable, as it directly measures the generalization performance of learning algorithms in GNNs.", "theoretical_claims": "The proofs seem good me, although I didn't check every step of the proofs in the appendix.", "experimental_designs_or_analyses": "For empirical validation, the authors use synthetic graphs with well-controlled structural properties (i.e., regular vs. power-law). While I believe real-world datasets could further support the practical relevance of the findings, the use of synthetic graphs is justified given the study’s theoretical nature.", "relation_to_broader_scientific_literature": "1. This paper bextends several key areas of existing research in graph neural networks, learning theory, and spectral graph theory. Prior work on GNNs has primarily focused on understanding their expressivity, convergence rates, and oversmoothing issues. This paper advances the field by shifting the focus toward generalization performance and excess risk in noisy settings. The authors provide new insights into how graph topology influences learning dynamics in GNNs, complementing prior work that has focused on message passing and feature propagation.\n\n2. In terms of learning theory, previous studies have extensively analyzed the behavior of SGD and Ridge regression in standard machine learning settings. This paper extends these classical results to the GNN setting, providing a novel perspective on how these algorithms interact with graph structures.\n\n3. The analysis of over-smoothing in multi-layer GNNs builds upon existing literature on the depth limitations of GNNs, this paper provides a new theoretical lens on the issue by framing it in terms of non-isotropic excess risk effects.", "essential_references_not_discussed": "No. The references seem sufficient to me.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I have the following two questions.\n\n1. The main results of the paper rely on the four assumption in Section 3. Please better explain the assumptions and how realistic they are.\n2. The paper focuses on regular and power-law graphs. How about random graphs? What results can be expected?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates how graph structure influences the generalization of learning algorithms in GNN, with a focus on excess risk. The authors connects pectral properties of graphs to the learning behavior of stochastic gradient descent and Ridge regression. They analyze how graph topologyy impacts algorithm performance. Empirical results on synthetic and small real-world graphs support their findings.

Some reviewers noted that the scope of GNN models considered is limited. There are concerns about the realism of certain assumptions and the reliance on spectral properties derived from latent representations rather than directly from the graph topology. 
Despite these limitations, the paper offers a solid theoretical contribution that links learning algorithms and graph structure. Its insights are valuable for understanding algorithm performance under different graph regimes and provide a foundation for future extensions. I recommend (weakly) acceptance.
Decision: Accept (poster)