Generalization of Spectral Graph Neural Networks
graph learning;graph neural networks;generalization;node classification;uniform stability
Yes
No ethics review needed.
See weaknesses.
- Relevance: Since generalization is one of the most important theoretical aspects of ML, the paper studies a very relevant problem in graph representation learning.

- Novelty: As far as I know, this is the first paper to theoretically investigate connections between generalization and homophily.  

- Another positive aspect is that the empirical assessment considers five popular spectral GNNs.
The paper explores the generalization capabilities of spectral GNNs, examining how graph homophily and architectural choices affect GNN generalization in node classification tasks. The paper leverages the notion of $\gamma$-uniform transductive stability to obtain stability guarantees and, consequently, generalization bounds for spectral GNNs. From the theoretical analysis, the paper claims that spectral GNNs perform well on graphs with strong homophily or heterophily. Experimental results on synthetic and real-world datasets aim to support the theoretical insights.
**Generality**: The proposed analysis is valid for SBM-based graphs, which limit the generality of the paper's claims. Overall, the paper fails to discuss the impact of this choice --- how limiting is that choice? How well does such a class capture the distribution of real-world graph data?

**Inconsistent results**: Based on Figures 1 and 2, there is a clear difference in behavior for the experiments using synthetic and real-world datasets. I found the justification based on the number of training samples quite hand-wavy. The authors could strengthen the discussion with additional empirical analysis to confirm the proposed explanation.

**Missing related works**: The paper should acknowledge other prior works on the stability/generalization properties of GNNs, e.g., "Stability properties of GNNs by F. Gama, J. Bruna, and A. Ribeiro".

**Tightness**. The paper lacks a discussion regarding the tightness of the obtained generalization bounds. Also, how well do the obtained bounds correlate with observed generalization gaps? 

**Parallel with prior results**: What parallel can one establish between the paper's findings and existing results regarding the stability/generalization of (spectral) GNNs? While I understand that comparing generalization bounds is challenging (e.g., due to different assumptions), the authors could try to connect their findings with what is known about the generalization capabilities (and stability properties) of GNNs.

**Impact**: The paper does not discuss how the theoretical results could be used to inform practitioners in designing better models. Thus, I found the overall impact of this contribution in practice limited.
Yes
No ethics review needed.
- Theorem 6 is odd to me, it seems to not be specific to spectral GNNs none of the parameters of the graph (n,f, Pi, Q) seem to affect the transductive stability. In fact nothing except the size of the dataset m seems to affect the result. What am I missing?
- Theorem 6 What is beta_2?
- Have you validated how well you can fit the cSBM model to the real world datasets?
- Clear presentation
- Significant technical machinery is introduced (though unclear how interesting or relevant it is given the assumptions and results)
- The authors attempt to validate their high-level conclusion empirically, which is nice!
The paper provides generalisation bounds for a specific class of spectral GNNs and assuming a particular graph model (cSBM) derives the stability of the spectral GNN training in terms of generalisation for differrent homophily and heterophily values.
TLDR: The assumptions and restrictions of the theoretical analysis are high (full-batch gradient descent and a specific spectral GNN architecture). And it's unclear whether the derived bounds are tight enough to be interesting. The empirical validation is only at a very high-level. If the authors can demonstrate that the bounds are tight, I am willing to raise my score to acceptance.

- Please include proof sketches in the main paper and add links to where the full proof is in the Appendix.
- The work assumes that the GNN is trained with gradient descent and a fixed learning rate. When this is not true in practice, and it is generally known that some optimizers in fact work very poorly. This is fine given the theoretical nature of the paper, but this limitation should be more explicitly addresssed.
- It should be shown that the generalization bound is not vacuous, i.e. that for some realistic values of n and other parameters the the value out of the bound is precise enough to be interesting. In particular it seems to me that assuming a fixed ratio between m and n the generalisation bound quickly gets worse as it relies on the absolute difference of n-m and not the ratio. Even worse in practice the labelled samples m is often quite small compared to n, so much so that O(n-m) approx O(n), which makes for an uninteresting generalisation bound. (I might be missing something here.)
- For the experimental results: it only validates the very high-level conclusion, which is less interesting. Ideally, the generalisation bound and it's tightness would be empirically validated, i.e. plot the generalisation bounds on the graph as a reference else the theory is not very useful.
- Also the presentation of the results could be improved please label the points in Figure 2 for instance to show which datapoint represents which dataset.
- The architecture restriction is quite severe.
Yes
No ethics review needed.
See section weaknesses.
1. The paper's topic is relevant. 
2. To the best of my knowledge, the theoretical results of the paper are correct.
The paper introduces a generalization study of the GNNs based on transductive learning and homophily/heterophily. The paper's results are relevant, and the topic is important. However, the paper's presentation can be improved, and a better discussion of the results should be added. The author's results are not novel per se, given that there were similar results before. Also, the link between homophily/heterophily and generalization is independent of GNNs and only depends on the walk on the graph, which provides little intuition on the implications of them. The numerical experiments are almost uninformative, and the results show a large amount of noise. I believe the topic paper is relevant, but I fail to understand what novelty this paper brings to the community.
1. The paper's theory is separated - the generalization results are on one side, and the homophily/heterophily on the other one. This undermines the importance of the results. That is to say, the authors present two relevant results that are disjoint and use different theoretical assumptions. I believe this undermines the importance of the paper given that it should be two different papers, and the novelty and contributions of each should be evaluated separately.  

2. Regarding the generalization results based on transductive learning, these results are not novel, and similar results exist in the literature:

 - Transductive Robust Learning Guarantees, Montasser et al. 
 - On Inductive–Transductive Learning With Graph Neural Networks Ciano et al. 
 - Towards Understanding Generalization of Graph Neural Networks Tang et al.

The authors should explain why their results are important, and how they fit in the crowded landscape. 

3. The previous point is regarding novelty, but there is also something to be said about this transductive analysis in and of itself. The graph is completely and almost entirely ignored. Why is this analysis even relevant to the context of GNNs? Why is it valid to analyze GNN while ignoring the graph completely? Even by looking at the assumptions for Theorem 6, the is not a single mention of the graph. The graph could have no edges (be a set of samples) and the results would still hold. In particular, Theorem 6 is a known result. 

4. The paper uses a very strong assumption regarding uniform transductive stability. In particular, Theorem 9 is valid because of the strong assumption \gamma-uniform transductive stability. When does this assumption hold? The authors should explain why using this assumption is valid. 

4. The graph is introduced in the second part of the paper, and the only relevant features of it are community and label. This largely ignores the progress in graph theory, and graph models that have been used in the last 10+ years. The authors utilize an extremely simple model that does not appear in any real-world problem. What is even worse, in this extremely simple model, the results are impossible to digest; Theorem 13 is unintuitive, and the explanation given with the bullets after it is largely trivial and uninformative. I fail to understand the contribution of these theoretical results. 

5. The numerical results are difficult to process and understand. Given that the authors provide a theoretical framework that is very difficult to follow, the numerical results shed no light on any real-world conclusion. Looking at Figure 2, there is little connection to the theory. Even more so, the theory is so detached from practical implementations, that new metrics have to be introduced (H_{edge}, order K for example). On top of that, the results are noisy and no statistical bands are being provided.
Yes
No ethics review needed.
Please see the sections above
- Analysing the connection between generalization bound, dataset caracteristiques ( degree of homophily/heterophiliy..) and architecture (polynom’s degree) is an interesting topic that can help developing more powerful architectures, better tuned for a specific problem.
- The paper is well-structured, with a smooth progression from one finding to the next one. Significant effort has been made to present the findings in an intuitive and practical manner.
- The design of the experiments is well aligned with the theoretical findings.
The paper studies the generalization capabilities of spectral graph neural network. The analysis  is based on the theory of uniform transductive stability. The paper theoretically show that generalisation bound is influenced by graph homophily, the polynomial order of the spectral GNN and the cardinality of the training set as follow: 1) a spectral GNN with polynoms of order K performs better on strongly homophilic and strongly heterophilic datasets; 2) if the spectral GNN parameters fulfill certain conditions, the generalisation error bound increases with the order of polynom K (which might explain the poor performance of spectral GNN with high K, despite the increase in expressivity) and 3) increased in the number of training samples improves generalisation. The theoretical results are validated both on synthetic and real-world datasets, for 5 different spectral GNN architectures.
- While the synthetic experiments clearly match the theoretical results, for the real-world datasets some discrepancies are present. In Figure 2, models with medium degree of heterophily has a similar gap of accuracy compared to strongly homophilic/heterophilic datasets. The authors motivate these results by the influence of training set cardinality, since the datasets not only differ in the homophily level, but also in size.  Indeed, since the generalisation gap is influence by both number of training samples and homophily level, it is hard to disentangle the individual effect of each one of them in the presented real-world experiments. However, this makes it considerably harder  to asses if the theoretical results correlates or not with the practical findings. Does repeating the experiments with a different train-val-split such that the number of training samples remains the same alleviates these discrepancy? Or, given the assumption that n→ infinity it is better to focus on having comparable percentages of nodes in the training set when splitting the data?
- The results in Figure 4 are hard to correlate with the theoretical findings. The theorems show that, under certain assumptions, the gap in accuracy increases with the order of the polynom used by the spectral GNN. However, that is not the case in the experiments provided in Figures 3 and 4. The explanation is that the assumptions might not be fulfilled in some of the scenarios. Is it possible to check or impose that assumption such that the experiments can match the theoretical findings?
- While the paper provide interesting insights into what influence the generalisability of spectral GNNs, it does not provide any guidance towards how can we benefit from these findings.
Yes
No ethics review needed.
Please refer to the weakness
- This work builds the bridge between generalization and uniform transductive stability on spectral GNNs, and explores the effect of graph homophily/heterophily and polynomial order on stability, which is overall original and provides some insight into this area. 
- The paper is and well-organised and easy to follow.
This work analyzes the generalization ability of spectral GNN in node classification tasks. The authors first bound the generalization error with uniform transductive stability, then analyze the effect of graph homophily/heterophily and polynomial order on stability. Specifically, the authors prove that graphs with strong homophily/heterophily improve model generalization by stabilizing models, while increased polynomial order will increase generalization error when specific conditions hold, leading to varying behavior in real world datasets. Finally, the authors provide experiments to support their findings.
This work does provide insight into the effect of graph homophily/heterophily and polynomial order K on generalization. However, I would suggest the following weaknesses:

1. The conditions for K may or may not hold in real-world datasets. As a result, this finding may not offer substantial guidance for future improvements. 
2. The authors do not provide sufficient explanation or intuitive reasoning regarding the conditions for K.
3. Although the authors acknowledge that the work is limited to a specialized cSBM, I would suggest the authors include explanations on why this specialized cSBM is useful when analyzing generalization.
Yes
n/a
No ethics review needed.
- Regarding the condition in Theorem 14 "when $\sum_{k=2}^K\theta_k(k-1)!/2^{k-1}$ increases more slowly than $\sum_{k=2}^K\theta_k^2(k-1)!/2^{k}$": it is not clear what this means in practice, e.g., how likely this is to hold? Could the authors provide more details about this?
- The paper is well-written and contributions are clearly highlighted
- The theoretical results are interesting, well introduced and clearly explained
- The experiments on synthetic datasets validate the theoretical claims
This paper studies the impact of node label distribution and polynomial degree on the generalization capability of spectral GNNs for the task of node classification. 

Through a uniform transductive stability analysis of spectral GNNs, the authors provide a generic error bound for spectral GNNs, highlighting the impact of expected prediction error and $k$-length walks on the stability and generalization of the GNNs. Then, the authors specify the bound in the case of a graph with 2 classes, showing that in this case high or low homophily correspond to good generalization, while medium homophily hinders generalization, and they prove that, under some assumptions, increasing the order of the polynomial in the spectral GNN leads to worse generalization.
- Throughout the paper, both in the theoretical and in the experimental results, no analysis of the depth and width of these spectral GNNs is conducted. It seems at some that the work focuses on a single layer GNN but this is not explicit. As such, the claims of the paper do not hold for a general setting as GNNs are typically deeper and wider (multiple features), which imply layers of filter banks. The effect of these filter banks and how their combined spectrum affects generalisation abilities is unclear.
- The experiments on real-world datasets show, in some cases, inconsistent results compared to the theoretical claims (e.g., as the authors point out in lines 484-485, the accuracy and loss gaps do not decrease as $H_{edge}$ increases from high to medium heterophily). One possible explanation of this is the varying dataset size, as the authors mention, but a more thorough analysis of this behavior would increase the understanding of how the theoretical results apply in practice. One aspect to consider in this sense might be the fact that the final generalization bound is computed in the case of a graph with 2 classes, whereas the real-world graphs used in experiments contain more. This might have a relevant impact, since homophily itself does not characterize GNNs' behavior well and more sophisticated measures of label distributions provide deeper insights, especially when there are more than 2 classes [1,2]. 
- The above as well as the limitation of the generalisation in terms of transitive stability and node classification, limit drastically the impact of this contribution
Yes
No ethics review needed.
Refer to Weaknesses.
1. The structure of the paper is clear and easy to read, and it is well-organized；

2. The paper is highly theoretical, offering a rigorous theoretical derivation process for its research problem；

3. The paper is somewhat pioneering, providing a great perspective on the study of the generalization performance of spectral GNNs.
This paper explored the generalization capabilities of Spectral GNNs, focusing on the relationship between generalization capabilities, graph homophily, and node class distribution in node classification tasks. It also investigated the connection between the polynomial order in the architecture of spectral GNNs and generalization error. Through rigorous theoretical analysis and experimental validation, the paper showed that spectral GNNs performed worse on graphs with weak homophily or heterophily but generalized well on graphs with strong homophilic or heterophilic structures. At the same time, it also provided a detailed analysis of the relationship between polynomial order and generalization error.
1. The research is based on generalization error. In my opinion, the authors should also incorporate additional metrics to validate the accuracy of their theory. For instance, comparing training and test loss over a specific number of epochs would closely align with the notion of generalization error. Additionally, computing one or two sets of generalization error on both synthetic and real-world datasets used in the paper would further illustrate their point effectively.

2. Datasets are small in experiments. The authors might consider using larger datasets, such as those mentioned in link [1], to further validate their theory. Only a few additional experiments, perhaps just one or two, would be sufficient to make the point, as certain properties of Spectral GNNs may differ when applied to larger datasets.

3. In line 512-571, the author wrote that "These observations align with our theoretical analysis." However, in Figure 4, the test accuracy for JacobiConv and in Figure 4 for ChebNet does not show a linear relationship with the K value, and the curves exhibit significant fluctuations. This seems inconsistent with the conclusions drawn by the authors in Proposition 16. Could the authors provide an explanation for the discrepancy between their conclusions and the experimental results observed in Figure 3 and Figure 4?

4. It would be better to provide codes to ensure the reproducibility.

&nbsp;&nbsp;&nbsp;[1] https://ogb.stanford.edu/docs/nodeprop/
We study the generalization of spectral graph neural networks in node classification tasks, especially how the generalization is affected by the graph homophily and the architecture of spectral GNNs.
@inproceedings{
anonymous2024generalization,
title={Generalization of Spectral Graph Neural Networks},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=UAEmF5O8J3},
note={under review}
}
Despite the success of spectral GNNs in practical applications, their generalization capabilities remain poorly understood in theory. In particular, node classification tasks are influenced by node class distribution and graph homophily, yet the relationship between these factors and the generalization of GNNs is largely unexplored. In this paper, we address this gap by analyzing how graph homophily and architectural choices impact the generalization of spectral GNNs. We first derive a general form of uniform transductive stability for spectral GNNs and then provide an explicit stability on graphs with two node classes, offering a comprehensive framework for understanding their generalization properties. Based on this stability analysis, we establish a generalization error bound, demonstrating that spectral GNNs with better stability exhibit better generalization. Our theoretical results reveal that spectral GNNs generalize effectively on graphs with strong homophily or heterophily, while their generalization degrades on graphs with weaker homophilic or heterophilic structures. Furthermore, we identify the conditions under which increasing the polynomial order in the architecture of spectral GNNs can increase the generalization error. To support our theoretical insights, we conduct experiments on synthetic and real-world benchmark datasets, and empirical results closely align with our theoretical analysis.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
graph learning graph neural networks generalization node classification uniform stability
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/9f62a72ff961c4c4f673c09983c929a87d9c2214.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/29ffb5b3b2b6196757d0de17e99f5c60038a46c1.pdf
Generalization of Spectral Graph Neural Networks
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission