A Manifold Perspective on the Statistical Generalization of Graph Neural Networks

## \thesubsection Manifold label prediction via node label prediction

Suppose we have an input manifold signal $f\in L^{2}(\ccalM)$ and a label (i.e. target) manifold signal $g\in L^{2}(\ccalM)$ over $\ccalM$. With an MNN $\bm\Phi(\bbH,\ccalL_{\rho},\cdot)$, we predict the target value $g(x)$ based on input $f(x)$ at each point $x\in\ccalM$. By sampling $N$ points $X_{N}$ over this manifold, we can approximate this problem in a discrete graph domain. Consider a graph $\bbG(X_{N},\ccalE,\ccalW)$ constructed with $X_{N}$ as either a Gaussian kernel based graph (Definition 1) or an $\epsilon$-graph (Definition 1) equipped with the graph Laplacian $\bbL_{N}$. Suppose we are given graph signal $\{\bbx,\bby\}$ sampled from $\{f,g\}$ to train a GNN $\bm\Phi_{\bbG}(\bbH,\bbL_{N},\cdot)$, explicitly written as

$$ $[\bbx]_{i}=f(x_{i}),\qquad[\bby]_{i}=g(x_{i})\quad\text{forall}x_{i}\in X_{N}.$ (3) $$

We assume that the filters in MNN $\bm\Phi(\bbH,\ccalL_{\rho},\cdot)$ and GNN $\bm\Phi_{\bbG}(\bbH,\bbL_{N},\cdot)$ are low-pass filters, which are defined explicitly as follows.
{definition}
A filter is a low-pass filter if its frequency response function satisfies

$$ $\left|\hat{h}(\lambda)\right|=\ccalO\left(\lambda^{-d}\right),\quad\left|\hat{ h}^{\prime}(\lambda)\right|\leq C_{L}\lambda^{-d-1},\quad\lambda\in(0,\infty),$ (4) $$

with $C_{L}$ a *spectral continuity constant* that regularizes the smoothness of the filter function.
To introduce the first of our two main results, we require introducing two assumptions.
{assumption}(Normalized Lipschitz nonlinearity)
The nonlinearity $\sigma$ is normalized Lipschitz continuous, i.e., $|\sigma(a)-\sigma(b)|\leq|a-b|$, with $\sigma(0)=0$.
{assumption}(Normalized Lipschitz loss function)
The loss function $\ell$ is normalized Lipschitz continuous, i.e., $|\ell(y_{i},y)-\ell(y_{j},y)|\leq|y_{i}-y_{j}|$, with $\ell(y,y)=0$.
Assumption 4 is satisfied by most activations used in practice such as ReLU, modulus and sigmoid.
The generalization gap is evaluated between the *empirical risk* over the discrete graph model and the *statistical risk* over manifold model, with the manifold model viewed as a statistical model since the expectation of the sampled point is with respect to the measure $\mu$ over the manifold.
The empirical risk over the sampled graph that we trained to minimize is therefore defined as
{align}
R_\bbG(\bbH) = 1N∑_i=1^Nℓ( [\bmΦ_\bbG(\bbH, \bbL_N, \bbx)]_i , [\bby]_i ).
The statistical risk over the manifold is defined as
{align}
R_\ccalM(\bbH) =∫_\ccalMℓ( \bmΦ(\bbH, \ccalL_ρ, f)(x), g(x)) \textdμ(x).
The generalization gap is defined to be
{align}
GA = sup_\bbH∈\ccalH — R_\ccalM(\bbH) - R_\bbG(\bbH)—.
{theorem}
Suppose the GNN and MNN with low-pass filters (Definition 1) have $L$ layers with $F$ features in each layer and the input signal is bandlimited (Definition 1). Under Assumptions 4 and 4 it holds in probability at least $1-\delta$ that

$$ $GA\leq LF^{L-1}\left((C_{1}C_{L}+C_{2})\frac{\epsilon}{\sqrt{N}}+\frac{\pi^{2} \sqrt{\log(1/\delta)}}{6N}\right)+F^{L}C_{3}\left(\frac{\log N}{N}\right)^{ \frac{1}{d}},$ (5) $$

with $C_{1}$, $C_{2}$, and $C_{3}$ depending on the geometry of $\ccalM$, $C_{L}$ is the spectral continuity constant in Definition 1.

- 1.
When the graph is constructed with a Gaussian kernel \eqrefeqn:gauss_kernel, then $\epsilon\sim\left(\frac{\log(C/\delta)}{N}\right)^{\frac{1}{d+4}}$.
- 2.
When the graph is constructed as an $\epsilon$-graph as \eqrefeqn:compact_kernel, then $\epsilon\sim\left(\frac{\log(CN/\delta)}{N}\right)^{\frac{1}{d+4}}$.

See Appendix LABEL:app:proof-node for proof and the definitions of $C_{1}$, $C_{2}$ and $C_{3}$.
Theorem 4 shows that the generalization gap decreases approximately linearly with the number of nodes $N$ in the logarithmic scale and that it also increases with the dimension of the underlying manifold $d$.
Another observation is that the generalization gap scales with the size of the GNN architecture.
Most importantly, we note the bound increases linearly with the spectral continuity constant $C_{L}$ (Definition 1) – a smaller $C_{L}$ leads to a smaller generalization gap bound, and thus a better generalization capability. While a smaller $C_{L}$ leads to a smoother GNN, it discriminates fewer spectral components and, therefore, possesses worse discriminability. Consequently, we may observe a larger training loss with these smooth filters, presenting a trade-off between generalization and discriminative capabilities. Since the testing loss can be upper bounded by the sum of training loss and the bound of generalization gap, on a smoother GNN (a smaller $C_{L}$), the performance on the training data will be closer to the performance on unseen testing data.
Therefore, having a GNN with a smaller spectral continuity constant $C_{L}$ can guarantee more generalizable performance over unseen data from the same manifold. This also indicates that similar testing performance can be achieved by either a GNN with smaller training loss and worse generalization or a GNN with larger training loss and better generalization.
In all, this indicates that there exists an optimal point to take the best advantage of the trade-off between a smaller generalization gap and better discriminability, resulting in a smaller testing loss decided by the spectral continuity constant of the GNN.
{wrapfigure}r0.6

5cm!
{tikzpicture}[x = 1*1cm, y=1*1cm]
{axis}[scale only axis,
width = 2.4*1cm,
height = 0.8*1cm,
xmin = -0.5, xmax=7.5,
xtick = -0.5, 0, 2.63, 7.5,
xticklabels = 0, \red$\lambda_{1}$,
\red$\lambda_{i}$,
$\qquad\lambda$,
ymin = -0, ymax = 1.15,
ytick = 1.15,
yticklabels = $\hat{h}(\lambda)$,
enlarge x limits=false]
\node[color = blue] at (600, 0.002) $\ccalO(\lambda^{-2})$;
\addplot+[samples at = 0.00, 0.91, 1.57,
2.63,
color = red!60,
ycomb, thick,
mark=otimes*,
mark options=red!60]
0.7*exp(-(0.8*(x-0.5))^2)+ 0.5* 1/((x+3)^2)+0.3*exp(-(0.8*(x-2))^2) +0.3*exp(-(0.8*(x))^2)
;
\addplot[ domain=-0.5:7.5,
samples = 80,
color = black,
line width = 1.2]
0.7*exp(-(0.8*(x-0.5))^2)+ 0.5* 1/((x+3)^2)+0.3*exp(-(0.8*(x-2))^2) +0.3*exp(-(0.8*(x))^2)
;
\addplot[ dashed, domain=-0.5:7.5,
samples = 80,
color = blue,
line width = 1.2]
0.8 * 1/(0.3*(x)^2)
;

The $x$-axis stands for the spectrum, with each sample representing an eigenvalue. The black line illustrates a low-pass filter with red lines initiating the frequency responses of a filter on a given manifold. The blue dotted line shows the upper bound of the frequency response in Definition 1.

## \thesubsection Manifold classification via graph classification

Suppose we have a set of manifolds $\{\ccalM_{k}\}_{k=1}^{K}$, each of which is $d_{k}$-dimensional, smooth, compact, differentiable and embedded in $\reals^{\mathsf{M}}$ with measure $\mu_{k}$. Each manifold $\ccalM_{k}$ equipped with a weighted Laplace operator $\ccalL_{\rho,k}$ is labeled with $y_{k}\in\reals$. We assume to have access to $N_{k}$ randomly sampled points according to measure $\mu_{k}$ over each manifold $\ccalM_{k}$ and construct $K$ graphs $\{\bbG_{k}\}_{k=1}^{K}$ with graph Laplacians $\bbL_{N,k}$. The GNN $\bm\Phi_{\bbG}(\bbH,\bbL_{N,\cdot},\bbx_{\cdot})$ is trained on this set of graphs with $\bbx_{k}$ as the input graph signal sampled from the manifold signal $f_{k}\in L^{2}(\ccalM_{k})$ and $y_{k}\in\reals$ as the scalar target label. The final output of the GNN is set to be the average of the output signal values on each node while the output of MNN $\bm\Phi(\bbH,\ccalL_{\rho,\cdot},f_{\cdot})$ is the statistical average value of the output signal over the manifold. A loss function $\ell$ evaluates the difference between the output of GNN and MNN with the target label.
The empirical risk of the GNN is
{align}
R_\bbG(\bbH) = ∑_k=1^K ℓ( 1Nk∑_i=1^N_k [\bmΦ(\bbH, \bbL_N,k, \bbx_k)]_i , y_k ).
While the output of MNN is the average value over the manifold, the statistical risk is defined based on the loss evaluated between the MNN output and the label as
{align}
R_\ccalM(\bbH) = ∑_k=1^Kℓ( ∫_\ccalM_k \bmΦ(\bbH, \ccalL_ρ,k, f_k)(x) \textdμ_k(x), y_k).
The generalization gap is therefore
{align}
GA = sup_\bbH∈\ccalH — R_\ccalM(\bbH) - R_\bbG(\bbH)—.
{theorem}
Suppose the GNN and MNN with low-pass filters (Definition 1) have $L$ layers with $F$ features in each layer and the input signal is bandlimited (Definition 1). Under Assumptions 4 and 4 it holds in probability at least $1-\delta$ that

$$ $GA\leq LF^{L-1}\sum_{k=1}^{K}(C_{1}C_{L}+C_{2})\left(\frac{\epsilon}{\sqrt{N_{ k}}}+\frac{\pi^{2}\sqrt{\log(1/\delta)}}{6N_{k}}\right)+F^{L}C_{3}\sum_{k=1}^{ K}\left(\frac{\log N_{k}}{N_{k}}\right)^{\frac{1}{d_{k}}},$ (6) $$

with $C_{1}$, $C_{2}$, and $C_{3}$ depending on the geometry of $\ccalM$, $C_{L}$ is the spectal continuity constant in Definition 1.

- 1.
When the graph is constructed with a Gaussian kernel \eqrefeqn:gauss_kernel, then $\epsilon\sim\left(\frac{\log(C/\delta)}{N_{k}}\right)^{\frac{1}{d_{k}+4}}$.
- 2.
When the graph is constructed as an $\epsilon$-graph as \eqrefeqn:compact_kernel, then $\epsilon\sim\left(\frac{\log(CN_{k}/\delta)}{N_{k}}\right)^{\frac{1}{d_{k}+4}}$.

See Appendix LABEL:app:proof-graph for proof and the definitions of $C_{1}$, $C_{2}$ and $C_{3}$.
Theorem 1 shows that a single graph sampled from the underlying manifold with large enough sampled points $N_{k}$ from each manifold $\ccalM_{k}$ can provide an effective approximation to classify the manifold itself. The generalization gap also attests that the trained GNN can generalize to classify other unseen graphs sampled from the same manifold. Similar to the generalization result in node-level tasks, the generalization gap decreases with the number of points sampled over each manifold while increasing with the manifold dimension. A higher dimensional manifold, i.e. higher complexity, needs more samples to guarantee the generalization. The generalization gap also shows a trade-off between the generalization and discriminability as the bound increases linearly with the spectral continuity constant $C_{L}$. That is, to guarantee that a GNN for graph classification can generalize effectively, we must impose restrictions on the continuity of its filter functions, which in turn limits the filters’ ability to discriminate between different graph features.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: Please refer to the Weaknesses section. 

If my questions can be addressed, I will consider increasing the score :)
soundness: 2
strengths: 1. The paper is well-structured, and the experiments respond well to each part of the theorem.

2. The paper presents two theorems, which contribute to the study of GNN generalization.

3. The two theorems provide practical guidance for the selection of filters.
summary: This paper discusses the generalization of GNNs from a manifold perspective. In this setup, the graph is considered as sampled from an underlying manifold equipped with a Hausdorff probability measure. 

The authors aim to investigate the generalization gap between the following: A **GNN** trained on a sampled instance of the graph, and an **MNN** (Manifold Neural Network) that has the same structure and parameters as the GNN mentioned above.
Here, GNN and MNN specifically refer to low-pass filters.

The core of the paper lies in two theorems, which provide generalization gaps for both node-level and graph-level tasks. The main findings of the theorems are:
- The GNN trained on the sampled graph can generalize to the MNN on the original manifold.
- The trained GNN can generalize to other graphs sampled from the same manifold.
- The generalization error of the GNN is primarily influenced by several **key factors**: the number of nodes, the manifold dimension, and the spectral continuity constants $C_{L}$. Practically, this implies:
  - As the manifold dimension increases, more nodes are required to obtain a model with good generalization.
  - (**Important**) A larger $C_{L}$ represents stronger discriminative power but results in weaker generalization. This is a critical trade-off to consider when choosing a model.

The paper uses experiments to demonstrate the impact of these key factors.
weaknesses: 1. The relationship between the experimental and theoretical settings is not clearly explained. In the appendix, the authors mention that the experiments use a graph convolutional layer (GCN). **Does GCN fall under Definition 4** as required by the theorems? Moreover, does the input used in the experiments meet the requirements of **Definition 1**? Also, GCN does not seem to match the filter structure that is analyzed in the paper.

2. The explanation of MNNs is insufficient for me. Are MNNs implemented by sampling graphs and running GNNs on them?

3. If the answer to (2) is yes, then shouldn't the paper provide a generalization bound between two separate runs of MNNs (effectively GNNs on two different sampled graphs)?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: In Eqn 7 and 8, there are $K_\epsilon(||x_i-x_j||^2/\epsilon)$ in both first steps. Is it a typo, otherwise isn't it a notation abuse of two different kernel functions?
soundness: 3
strengths: 1. The paper is clear and well-written.

2. The theoretical analysis is solid and correct based on my understanding.
summary: This work studies the generalization bound of GNN by comparing the bound of the corresponding manifold neural networks. The results show that the generalization gap decreases as the number of nodes increases or the spectral continuity constant decreases. The experiments justify the theory, especially including the discussion about the regularize of the training.
weaknesses: 1. Some definitions are not clear enough. For example, it is better to relate Eqn 16 to the expectation of Eqn 15 so that the generalization gap definition in Eqn 17 is aligned with the classical definition. Please let me know if my understanding is incorrect.

2. The contribution of the trade-off between discriminability and generalization gap is weak. I find that better discriminability is interpreted as a smaller regularizer, which is indicated by a larger continuity constant. This explanation is quite indirect. A stronger analysis of discriminability could be a discussion based on some quantity to measure the discriminability.

3. The theoretical contribution and the novelty of this work are not very clear. It is better to provide a table or a list to show the comparison between this work and existing theoretical works.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 3
questions: - L.261: Is it correct to assume that the feature vector (input to the first layer of GNN or MNN) at each point $x$ is 1-dimensional because the input signal $f$ belongs to $L^2(\mathcal{M})$.
- l.293: I think $GA$ is different from the generalization gap in the usual statistical machine learning theory. Usually, the generalization gap is the difference between the empirical and statistical risks of the same model (i.e., hypothesis). In contrast, this paper uses GNNs for the empirical risk and MNNs for the statistical risk: when a new data point $x$ is sampled, the prediction value for $g(x)$ is computed using MNN $\Phi(\mathbf{H}, \mathcal{L}_\rho, \cdot)$ not GNN $\Phi_G(\mathbf{H}, \mathbf{L}_N, \cdot)$. This setting may be justified if we interpret $\mathcal{H}$ as a hypothesis space. However, I do not think it is a very popular setting.
- l.308: *Theorem 1 shows that the generalization gap decreases approximately linearly with the number of nodes $N$ in the logarithmic scale.*: I want to clarify what this means mathematically. Does it mean that the main term of $\log (GN)$ is $\tilde{O}(-\log N)$, where $\tilde{O}$ is the O-notation that ignores logarithmic orders.
- l.311: *More importantly, we note the bound increases linearly with the spectral continuity constant $C_L$ [...].*: I have a question about this claim. In Theorem 1, the left-hand side $GA$ is uniform with respect to the hypothesis space $\mathcal{H}$, that is, independent of the specific hypothesis $h\in \mathcal{H}$. On the other hand, the upper bound on the right-hand side depends on the specific hypothesis $h$ (or specific MNN/GNN) through spectral continuity constant $C_L$. In particular, let $C_\mathcal{H}$ be the infimum of the spectral continuity constant over $\mathcal{H}$: $C_{\mathcal{H}}:= \inf_{h\in \mathcal{H}} C_L$. The inequality replacing $C_L$ with $C_\mathcal{H}$ on the right-hand side must also hold and is a tighter uniform bound independent of specific hypothesis $h$.
- l.378: In Figure 4, the linear fitting is applied only on a region with a training accuracy of over 95%. However, I wonder whether this is justifiable. In fact, since the previous argument for l.311 provides a tighter uniform bound on the hypothesis space $\mathcal{H}$, the inequality holds regardless of the training accuracy.
- l.378: Related to the previous, as the theoretical analysis applies to untrained GNNs, I suggest conducting numerical experiments using untrained GNNs to see if the implication from the theory is valid numerically for them.
- l.474: *In all cases, we vary the number of nodes in the training set by partitioning it in $\\{1, 2, [...], 1024 \\}$ partitions when possible.*: Does this mean that when the whole dataset is divided into $k$ partitions, the training dataset is one of those partitions? If so, how is the test dataset chosen if the number of partitions is one? I also want to check whether this experiment is a transductive problem, i.e., the test dataset is available during training, and the training data is available during the test.
- l.478: In the theoretical analysis, the generalization gap is defined as the difference in risk between MNN and GNN. However, interpreting the generalization gap in numerical experiments in that way is questionable for the following two reasons: first, numerical experiments use GNN for both training and testing. Second, assuming my understanding of the previous question about l.474 is correct, it is a transductive problem, which is different from the assumption in the theory. I want to ask the authors why it is justifiable to interpret the generalization gap in the numerical experiments as $GA$ in the theoretical analysis.
- l.497: If we want to make a statistical claim that there is a linear correlation, it is more appropriate to apply hypothetical testing such as t-test and ANOVA rather than using an arbitrary threshold of 0.95.
- l.506: In the experiment in Figure 7, it is claimed that the relationship between the spectral continuity constant $C_L$ and the generalization gap is verified. However, the experiment does not measure the value of $C_L$ is not directly and assumes that increasing the regularizer reduces $C_L$, which shoulde be verified.
- l.506: Even if we do not take the tight uniform bound as we discuss in the question about l.311, I still have a question about the validity of Theorem 1 in numerical experiments. In Theorem 1, the dominant term in the upper bound, when $N$ is sufficiently large, is the last term $F^LC_3(\log N/N)^{1/d}$. However, this term is independent of the value of $C_L$. It implies that the generalization gap should be almost independent of $C_L$ when the number of nodes is large; this is not the case in Figure 7.

**Minor Comments**
- l.161: $P$ is undefined.
- l.165: $M$ is undefined.
- l.184: I think it is not appropriate for the main text to refer to Equation (23), which appears only in the Appendix.
- l.187: The fact that the Laplacian eigenvalue is discrete and, at most, countable should be proved. We can derive it from the fact that $\mathcal{M}$ is compact.
- l.329: Since $\rho$ indicates the density of the manifold $\mathcal{M}$ in the previous sections, it is not recommended to use $\rho$ as a general symbol for the Laplace operator such as $\mathcal{L}\_{\rho, k}$. The same applies to the graph Laplacian $\mathbf{L}\_{N, k}$ in l.333.
- l.334: Figure 3 is not referenced from the main text.
- l.359: $\epsilon$ is undefined in this section. Also, the dependence of $\epsilon$ on $k$ should be made explicit.
soundness: 2
strengths: - A single methodology can be applied to the analyses of both regression and classification tasks. Furthermore, for classification, the analysis can be extended to the case where data points with different labels are on different manifolds.
- This paper provides detailed background knowledge on spectral theory on compact Riemannian manifolds, in particular, the Laplace-Bertlami operator, and MNN based on it. It is intended for those who are not familiar with the field, making it accessible to them.
summary: This paper considers the generalization performance of GNNs when the data lies in a manifold. Consider the problem of predicting target value $g$ from a one-dimensional graph signal $f$ on a compact Riemannian manifold $\mathcal{M}$. Two types of models are considered: the Manifold Neural Networks (MNN) induced from the Laplace-Beltrami operator on $\mathcal{M}$, and the GNN constructed on a finite number of i.i.d. sampled data points using a graph kernel. 
This paper evaluates the generalization performance of GNNs when the similarity graph is a Gaussian kernel-based graph and a $\epsilon$-graph, respectively. Here, the generalization performance is defined as the difference between the statistical risk in the sense of the average risk on $\mathcal{M}$ when applying the MNN and the empirical risk using the GNN on a finite number of points $\{(x_i, y_i)\}$. In particular, the rate of generalization gap with respect to the number of sampled data points and its dependence on the dimension of the underlying manifold $\mathcal{M}$ are derived. Furthermore, the generalization gap for node classification tasks is derived when we assume that data points with different labels are on different manifolds.
In numerical experiments, GNNs are applied to node prediction tasks on synthesis and real networks, and node classification tasks on point clouds. The dependence of generalization on data points and spectral continuity constants is also evaluated.
weaknesses: - I have a question about the significance of Theorem 1, especially about the dependence of the upper bound on the spectral continuity constant.
- If I understand correctly, the definition of generalization performance in theoretical analysis differs from that in the usual statistical learning theory.
- I have a question about whether the generalization gap in numerical experiments appropriately corresponds to that in the theoretical analyses.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please refer to weaknesses.
soundness: 3
strengths: 1.First to analyze GNN generalization from a manifold perspective, providing a new theoretical viewpoint that is more relevant to practical applications compared to previous work.
2. Not only presents theoretical framework and generalization bounds, but also validates theoretical results through extensive experiments and provides practical guidelines for GNN design.
summary: This paper investigates the statistical generalization capabilities of Graph Neural Networks (GNNs) from a manifold perspective. The authors propose a theoretical framework proving that when graphs are sampled from manifolds, the GNN's generalization error bound decreases logarithmically with the number of nodes and increases linearly with the spectral continuity constants of filter functions. The theory applies to both node-level and graph-level tasks, providing guidance for practical GNN design. The theoretical results are validated through eight real-world datasets.
weaknesses: - The paper requires input signals to be bandlimited (Definition 1) and filters to be low-pass (Definition 4). Please clarify that these assumptions are not difficult to satisfy in practical applications.

- The proposed Gaussian kernel-based graph construction method (Definition 2) requires computing the full adjacency matrix, which is computationally expensive for large-scale graphs with O(N^2) time complexity.

- The theoretical results heavily depend on the choice of spectral continuity constant C_L, but the paper lacks concrete guidance on how to select appropriate C_L values in practice.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Main issue is a more detailed discussion of Maskey and Levie- if you would like to try to convince me what your contribution is over those papers, I will be happy to listen.

In addition, here are some minor points which you don't have to discuss in the rebuttal, but could address in your next version of the paper:

* Line 155 instead of "with" should be "from"

* In definition 4, Is the low-pass filter defined with the same d as the manifold? If so why? 

* Line 280 you say assumption I makes sense, you can also explain why assumption II makes sense (e..g I believe it is satisfied by norm-based losses like MAE and RMSE)

* Line 370: not sure I understood your point about a single graph. As far as I recall, an alternative where several graphs were sampled from each manifold was not discussed.

* Mention in main text which GNN you use. I understand from the appendix that it is GCN.
soundness: 4
strengths: The paper is overall well written, and as far as I have checked the technical details seem to be correct. The experimental evidence that the generalization gap decreases as the number of nodes increases is interesting.
summary: This paper derives generalization bounds for spectral graph neural networks, based on the assumption that the graphs are obtained from a sampling procedure from an underlying manifold. The obtain generalization bound decreases with the number of nodes, and increases with the number of features and network depth. Experimental results corroborate the dependence of the generalization gap on these factors.
weaknesses: I don't like the assumptions made in this paper so much. It feels to me like they make the proof rather straightforward, but are rather far from reality. In particular, how common are the GNNs defined in equation (2)? How related are the GNNs in equation (2) to GCN, for which the experiments were carried out in practice? How likely is the assumption that the graphs are sampled from a manifold, for applications of interest (e.g., for the Cora, citeSeer datasets), and why is this assumption more reasonable than the assumption that the graphs were sampled from graphons as in previous work?

Overall, in comparison with the related work of Levie and Maskey cited in the paper,  I don't feel there is a significant upside. My impression that Maskey and Levie also showed generalization gaps which decrease with the number of node, and increase with model complexity (which can be equated with model complexity and  depth in this paper). True, these results were obtained for different GNNs and with a different limit model, but not clear to me why the manifold model, and spectral GNN, are  any "better"?

Meta-review: This paper tackles a problem of generalization error of graph neural network from a manifold perspective. That is, by assuming that the data are generated from manifold, the authors investigated how close the GNNs can be to manifold neural networks (MNNs). The theoretical investigation was supported by some numerical experiments.   

- Although the manifold perspective is interesting (and this kind of notion has been considered in the literature), this paper still requires some more revisions. As the reviewers raised, the writing can be much improved by adding more detailed and clear descriptions on the meaning of each mathematical notions and statements that the authors claimed. There are several unclear points that should be explained in more consistent way.   
- Moreover, the message derived from the theories are not necessarily well justified. In particular, the generalization and discriminability trade-off are discussed in a hand-wavy way. That is not so rigorous.  
- The connection of theory and numerical experiments is also unclear. For example, whether the GCNs employed as the ground truth satisfies the conditions or not is not rigorously justified.     

For these reasons, I think this paper is not mature enough for acceptance.

Decision: Reject