A Manifold Perspective on the Statistical Generalization of Graph Neural Networks

The main thing one can see is that the gap between the training and test loss decreases with the number of training examples. This is not very surprising or insightful, and as the real graphs are not generated in a way that is congruent with the theory, I am not sure how do they relate to the theoretical part.

The reviewer states that the decrease in the generalization gap with respect to the training examples is not very surprising or insightful. This is an empirical observation, and what our paper provides is a theoretical explanation of why this can be the case. That is to say, given that the decrease happens in practice, we aim to explain it. To do so, we leverage a geometric model for graphs that is insightful and interpretable -- the manifold. In terms of novelty, let us point out 3 aspects that to the best of our knowledge are novel and insightful about our work:

1. Our conclusions are not only that there is a decrease in the gap as a function of the number of nodes, but rather that the rate of decrease is consistent with what our theory predicts. This experiment, to the best of our knowledge, is novel in the literature for real world graphs. Z: We further introduce the spectral continuity and reveals its relationship with the generalization ability. The provides a novel complexity measure over GNN models.
2. A second novelty of our work relies on the fact that there is a unifying theory that explains both node prediction (Theorem 1) as well as graph prediction (Theorem 2). To the best of our theory, our work is the one that allows both problems to be explained.
3. Our theory relies on manifolds, which are a more intuitive model that better captures the geometry of the data. In Appendix I, Figure 7, we plot the spectral decay in the graph eigenvalues for 8 datasets. As can be seen, in the Figure, the sharp decay in the eigenvalues aligns with the underlying manifold assumption.

I am not sure about the novel contribution of this paper w.r.t Weng et al "Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs"

Our work and [1] have important differences.

1. In terms of the problem, our paper looks into a different problem than the one in [1]. In the case of [1] there is no performance measurements (i.e. loss functions) of machine learning involved. That is to say, the problem [1] tackles is the output function approximation of GNNs, and not the generalization ability of GNNs.
2. In terms of theory, our results differ from [1]. Instead of providing a probability bound depending on a sampled graph from the manifold as in [1], we derive a uniform bound over the space of functions of the sampled graphs, which is akin to the setting of machine learning generalization analysis.
3. In terms of architecture, in [1] they consider graph input/graph output architectures. In our case, we consider both node level classification as well as graph level classification problems. In all, although related, our paper is novel with respect to [1].

[1] "Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs", Zhiyang Wang, Luana Ruiz, Alejandro Ribeiro

I wouldn't say the results are really about generalization, this is more approximation results that show how the function on the manifold can be approximated with a finite sample.

In our work, we interpret the distribution of graph nodes as lying on an underlying manifold. This perspective aligns with the standard assumption in machine learning, where the data points (in our case, nodes) are sampled from a certain distribution (in our case, manifold). Unlike purely abstract or discrete distributions, our manifold-based interpretation explicitly captures and leverages geometric and structural relationships intrinsic to the nodes and their interactions in the graph. With this perspective, the statistical risk — the expected loss of our neural network — is naturally expressed as the integral or average of the loss over this node manifold. The work in "Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs" focus on the output difference analysis over the sampled points from the manifold, ignoring the unseen or unsampled points over the manifold. Our work complements this by providing this statistical analysis view. The problem that we are considering is what it is called generalization in machine learning, see for example: [Chapter 3] Understanding Machine Learning: From Theory to Algorithms By Shai Shalev-Shwartz and Shai Ben-David Cambridge University Press; [Chapter 2] Foundations of Machine Learning Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar MIT Press, Second Edition, 2018. https://cs.nyu.edu/~mohri/mlbook/; [Equations 1,2,3] Generalization analysis of message-passing neural networks on large random graphs S Maskey*, R Levie*, Y Lee, G Kutyniok NeurIPS 2022

We thank the reviewer for giving us a thorough check of our proof and all the suggestions. We are glad to find the reviewer think our work as ''exciting'' and ''significant''. We have carefully considered and addressed all the minor concerns that the reviewer has pointed out and we will make the accordant updates to guarantee that our results are 100% correct. We are addressing some of the questions to further clarify our points.

• In Section 3.2, the reviewer is correct that we are assuming the measure is absolutely continuous with respect to the Riemannian volume. We will change the ''Hausdorff probability measure'' to a non-vanishing Lipschitz continuous density $\rho$ with respect to the Riemannian volume on $\mathcal{M}$.
• The reviewer is correct that some common loss functions such as cross-entropy loss that we used is not strictly globally Lipschitz continuous. While it can be locally Lipschitz continuous if restricted to subsets where probabilities are bounded strictly away from 0 and 1. This can be realized with activation functions like sigmoid that naturally produce outputs away from 0 or 1. We will add this discussion to the main context. We thank the reviewer for pointing out this important point. We will add these notes following Assumption 3.
• We totally agree with the reviewer that it would be better to include some graphs that are clearly derived from a manifold. We have the synthetic manifold examples shown in Figure 1 to show the results on graphs derived from a practical manifold. We will implement the subsampling from an ellipsoid in [3] to apply to non-manifold graphs to make our work more general.
• $B_r$ is a ball with respect to the Euclidean distance in the Euclidean ambient space, while $B_r(\mathcal{M})$ is defined as a ball in $\mathcal{M}$ with respect to geodesic distance on $\mathcal{M}$. We will add these explanations in the updated version.
• We thank the reviewer for pointing out that the bound on $r$ only applies to $d \geq 3$. We will add the case for $d=2$ separately.
• The bounds in Prop 1 appear to depend on the band limit $M$ -- We suppose $M$ to be large enough such that $M^{-1}\leq \delta'$ and $C_2$ is related to $\delta'$ as we stated in line 967. We will make more elaborations on this.
• We will add the statement that Prop 4 of Wang 2024a as a restatement of Calder and Trillos, and we will update the $\epsilon$ term. For the $\lambda_i$ terms, we are replacing the upper bound $\lambda_K$ in Prop 4 of Wang 2024a as we are now assuming a bandlimited scenario and can have a point-wise analysis.
• The reviewer is right that in equation (42), we need to discuss about the case $d=2$ separately. We will add this explanation after equation (44) that the constant is different for the case $d=2$.
• For Proposition 3, the upper bound of the norm of gradient does not need to be the same with the Lipshitz constant of $g$. While we could assume it the same for the ease of presentation. We will update this and we thank the reviewer for pointing this out.
• For how (74) follows from (72), we are iteratively repeating the process for each layer and this would finally reduce to the single dimension input of the GNN. We will add explanations in the updated version. It is not necessary to assume a single input channel, but it is for ease of presentation. We will add a remark to state this potential expansion.
• The assumption that there is a constant number of filters per layer is also for ease of presentation and we will add a remark to this as well. We thank the reviewer for helping us improve our work.
• We agree that adding a $1/K$ in the definition of the risk functions in (17) and (18) can help with the normalization of the definition and does not have impact on the proof process.
• It would be interesting to explore the possibility of using the eigenvalue plot to infer the manifold intrinsic dimension. This would help to alleviate the restriction of the prior manifold information.

As C1, C2 and C3 depend on the geometry of the manifold, they are potentially important and might be a good contribution so it is a pity that the authors didn't discussed them in depth.

The parameters are related to the geometry of the manifold. We thought it distracting to expand in the main context. We totally agree with the reviewer that this would be a good contribution to discuss. We will add the details in the appendix to address these impacts.

The spectral contiuity term can be impractical to compute. why do you use a regulariser to indicate spectral contiuity. It seems very indirect.

The reviewer is right that calculating the spectral continuity constant might be computationally expensive. However, approximations to it might allow an efficient implementation. This are for example: [1] Stability properties of graph neural networks F Gama, J Bruna, A Ribeiro IEEE Transactions on Signal Processing 68, 5680-5695 [2] Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, Pan Li, ON THE STABILITY OF EXPRESSIVE POSITIONAL ENCODINGS FOR GRAPHS, ICLR 2024

My main concern is the novelty of this paper. -- [1][2][3] should be discussed. this is also known that a more complex GNN can sometimes achieve better generalisation [1][2]. In this regards, this paper doesn't provide much valuable insight. Also, the results regarding size of graph is known from (Maskey et al., 2022; 2024; Levie, 2024).

We will add these latest references for discussion in our updated version. We thank the reviewers for the suggestions. We propose to use spectral continuity to explain generalization when regular bounds indicate that we do not generalize. Our proposed approach leverages spectral continuity, shifting the notion of complexity from traditional parameter-based measures to a spectral domain, specifically considering filters with an infinite number of coefficients. Despite the infinite-dimensional nature of these filters, our spectral-based complexity measure still leads to meaningful, empirically validated bounds. This is consistent with the empirical observations the reviewer makes that high complexity may not lead to worse generalization. Our novelty lies in that we derived the generalization bounds based on spectral complexity measures. Furthermore, the bounds we have shown and proved match the empirical evidence in our plots.

In other words, our work suggests that complexity measured through a spectral lens captures essential aspects that traditional complexity measures overlook. This offers a deeper understanding of why specific complex GNN models generalize effectively.

In particular, the conclusion that generalisation decreases with spectral continuity (model complexity) is well-known traditional wisdom in statistical machine learning and is known that it doesn't reflect reality. Many models of high-complexity can achieve good generalisation. In the area of GNN, this is also known that a more complex GNN can sometimes achieve better generalisation [1][2]. In this regards, this paper doesn't provide much valuable insight.

The value of our work relies on our characterizing what 'model complexity' means in the context of GNNs. Model complexity measures for neural networks are, for example, VC-dimension and Rademacher complexity. However, these two well-studied measures do not readily apply to GNNs, given that they do not leverage the underlying geometric structure of the data. Therefore, the value of our work relies precisely on identifying the role of the spectrum of the graph (or manifold) in the model. We agree with the reviewer that our work is related to (Maskey et al., 2022; 2024; Levie, 2024). And we believe there is value in our work, given that our bounds depend on geometric measures that are more interpretable and understandable. Also, unlike (Maskey et al., 2022; 2024; Levie, 2024), we provide a bound for node classification, which was not offered before.

Does non-uniform sampling matter?

The sampling does not need to be uniform, but the points must be independently and identically distributed (i.i.d.) randomly sampled according to the measure $\mu$ over the manifold. We outline this condition at the beginning of section 3.2 -- the measure $\mu$ might not be uniform. The requirement is that the density is bounded below and above:

$0<\rho_{min} \leq \rho(x) \leq \rho_{max}<\infty \quad \forall x \in \mathcal{M}$

What concrete suggestions can be made to impose restrictions on the continuity of filter functions?

The spectral continuity could be impractical to compute accurately. Therefore, to address this, we add a penalty term to the loss function to impose this continuity constraint during the training process.

Why does accuracy decrease with more nodes (Figure 5(a))?

The training accuracy decreases with more nodes as the graph size grows. With the neural network size fixed, we expect a worse training accuracy as we train on a larger graph. This can result from the limited GNN model experiencing underfitting over the growing graph.

Are the proposed bounds or the manifold perspective applicable to various types of GNNs?

Yes, we prove for a general GNN convolutional form, and this can be extended to include other specific GNN convolutional models: https://pytorch-geometric.readthedocs.io/en/latest/modules/nn.html#convolutional-layers

Additionally, the font embedded in the figure is too small and should be adjusted for better readability.

Thank you for the suggestions and other comments to help us improve the paper. We will update these.

Figure 2 may be incorrect, as the Gaussian kernel graph should be fully connected, but the figure does not reflect this.

Thank you. We will update the Figure accordingly.