On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks

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.

Explanation and Realism of Assumption

Our assumptions are mild and broadly applicable in both theoretical and practical settings.

Assumption 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.

Assumption 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.

Assumption 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.

Assumption 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.

Together, these assumptions are well-supported by prior work and satisfied by a wide range of data and GNN settings.

Random Graphs

Thank you for the interesting question. Our framework and results can indeed be extended to the setting of random graphs.

If 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.

To 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.

This is a promising direction for future work, especially since random graph families are expressive and widely used in modeling real-world networks.

Thank 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.

[1] "SGD: General analysis and improved rates." International conference on machine learning.

[2] “Benign overfitting in ridge regression.” Journal of Machine Learning Research.

[3] “Benign overfitting of constant-stepsize sgd for linear regression”. In Conference on Learning Theory

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.

Suggested Reference

Thank you for highlighting this relevant work. While both papers aim to understand the generalization of GNNs, our focus and methodology differ significantly.

Tang 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.

As 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.

We will include this reference in the revised paper to enrich the related work section.

Specific G used in Section 4.4 and impact of architecture on the spectrum.

Thank you for the great question!

In our empirical study (Section 4.4), we use the normalized adjacency matrix, aligning with the standard GCN setup.

You'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.

That 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.

Loss function

Thank 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].

Additional experiments with benchmark datasets

Thank 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.

For 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.

The 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.

Cora

Chameleon

We will include these results in the revision to further strengthen the empirical support for our theoretical claims.

Thank you again for your diligent review, and we hope our response has satisfactorily addressed your questions and concerns.

[1] “Benign overfitting of constant-stepsize sgd for linear regression”. In Conference on Learning Theory

[2] “Benign overfitting in ridge regression.” Journal of Machine Learning Research.

[3] "A convergence analysis of gradient descent on graph neural networks." Advances in Neural Information Processing Systems

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.)

GNN Formulation and Transferability of Results

We 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.

Graph Topology and Spectrum of $\mathbf{M}$

Thank 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).

Suggested Reference

Thank 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.

Discussion on Over-smoothing

Thank 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.

A 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.

We appreciate the opportunity to clarify this and will revise the manuscript to highlight this distinction more clearly.

Missing Impact Statement

Thank 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.

Assumptions 3.1–3.4

Due to space constraints, please refer to our response to Reviewer 8EPb for a detailed discussion of these assumptions.

Clarification on Theorem 4.1

Thank you for the questions.

• 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]$.
• 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$.
• 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.

We appreciate the feedback and will revise the paper to clarify these points.

Again, 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.

[1] "A convergence analysis of gradient descent on graph neural networks." Advances in Neural Information Processing Systems

[2] “Benign overfitting of constant-stepsize sgd for linear regression”. In Conference on Learning Theory

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.

Related Works in Over-smoothing

Thank 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.

How the power-law decay $\beta$ and graph size affect the results

• 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.
• 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.

Idealize eigenvalue model and sensitivity of results

Thank 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.

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 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.

Therefore, 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).

Thank 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.