A Manifold Perspective on the Statistical Generalization of Graph Neural Networks

We thank the reviewer for their review. We will address the Weaknesses in what follows.

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?

The reviewer points out the connection between equation (2) and GNN architectures. Let us point out that equation (2) expresses the diffusion over the graph in matrix form and it is very general and it includes GIN, and GCN among other architectures. To show that GCN and equation (2) are indeed equivalent, this is another way of expressing equation (2),

where $\mathbf{H_{lf}}\in \mathbb{R}^{F_{l-1}\times F_l}$ is the coeficient matrix assocaited with layer $l$, and $\mathbf{X_{l}}$ is the feature matrix of layer $l$. Analogously, the GCNconv layer from pytorch geometric, which is based on the paper Semi-Supervised Classification with Graph Convolutional Networks can be written as follows:

Note that when $k=1$, the two equations are equivalent. When the previous equation is applied $k$ times, it is equivalent to $k$ in our equation (2).

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?

The assumption that graphs are sampled from manifolds is always valid in practice because it is well-known that any graph can be modeled as the discretization of a manifold. More to the point, any graph can be modeled as the sampling of a manifold embedded in $R^3$. Thus, when our experiments consider the subsampling of a graph, this is equivalent to considering the sampling of a manifold at different resolutions. This is, incidentally, an advantage of manifold models compared with graphon models.

A separate question concerns the complexity of the manifold. To explore this question, we have added a new section in the Appendix (Appendix I - Manifold Assumption) in which we plot the largest eigenvalues of each graph that we use in our node classification experiments. We see a quick decay in the magnitude of eigenvalues, which showcases the validity of our low-dimensional assumption.

We further note that the differences between graphon and manifold models are well known. A graphon models the limits of graphs that share structural connectivity properties as described by homomorphism densities. A manifold describes the limits of graphs that share geometric properties as described by the geometric properties of the underlying manifold. In general, manifold limits are considered more general because all graphs are samples of manifolds, as we have already stated.

Sorry for the later answer, and thanks for the response. I appreciate the emprical verification that generalization improves with the number of nodes.

There are several elements in your response which I do not find satisfying:

• I could not find in the "diffusion maps" reference you provided any justification for the claim "The assumption that graphs are sampled from manifolds is always valid in practice because it is well-known that any graph can be modeled as the discretization of a manifold." I suggest you provide a more specific pointer for the claim, or retract it.

• Regarding "we introduce the filter frequency response function as a general form while the polynomial function and exponential function are examples." This claim does not seem to me consistent with the wording in the paper. The wording can be changed, but ultimately the case of polynomial graph filters is the common case, certainly for GCN, used for the experiments in the paper, and other standard MPNN where the response function is linear in the eigenvalues.

• The claim that graphs have a finite number of eigenvalues is of course correct, but I don't see how it helps your case, where your proofs aim towards approximating a manifold with unbounded eigenvalues, so seems like graph size, and graph eigenvalues, are going to infinity. Overall, I feel that there is a mathmatical issue here that needs to be fixed and not swept under the rug: "is the theoretical analysis applicable to standard MPNN"? In my opinion, you should fix this and submit to the next conference... I will retain my rating.

We thank the reviewer for their positive review of our work.

Regarding Weakness 1, indeed these assumptions are not difficult to satisfy in practice. For Definition 1, it is practical to satisfy due to the fact that in practice the graph size is finite and the input signal possesses finite energy, thus the spectrum of the input graph signal is also bounded. Furthermore, in many practical applications, considering high-frequency components are often associated with noise or fluctuations without useful information, preprocessed data are commonly bandlimited. For Definition 4, we would like to clarify that in the experiments we add a regularizer to ensure the filters in GNNs satisfy the conditions in Definition 4. To do so, we can compute equation (108) in the appendix as the penalty term that we add to the loss function during the training process as a continuity regularization:

with $\alpha$ as the regularizer term shown in Figure 7.

Regarding Weakness 2, we construct the graph in a theoretical way, but in practice, we work with existing graphs. That is to say, we propose a way of constructing graphs from manifolds which is indeed expensive, but in practice, we assume that the graph is already sampled from an underlying model. Furthermore, leveraging the generalization result of GNNs, a finite-sized graph can effectively generalize to any points or graphs sampled from the underlying manifold. This eliminates the need to directly compute over a very large graph representing the manifold, thereby avoiding the significant computational complexity associated with such operations. This is also an insight into our generalization results. We added a section to the appendix (Appendix I) where we show that the assumption that graphs come from an underlying low-dimensional manifold holds in practice.

Regarding Weakness 3, the result indeed depends on the spectral continuity constant $C_L$. Note that in practice, a regularizer can be added to the loss such that this constant is reduced. We have included an experiment (Figures 7c and Figure 8d), where we vary the value of the regularizer (a larger regularizer implies a smaller spectral continuity constant), and show that our theoretical results indeed manifest in practice. The focus of this work is to highlight this observation of the trade-off between discriminability and generalization, uniquely analyzed in the spectral domain. This is a novel contribution to the field. Additionally, we recognize that it would be an interesting extension to investigate methods for selecting an appropriate continuity constant to achieve some optimal balance, ensuring both satisfying discriminability and generalization.

We thank the reviewer for their questions and suggestions. We have corrected the minor comments in the updated version. In what follows we will address the reviewer's questions.

Questions

Question L.261 Yes, it is safe to assume it.

Question L.293 The reviewer points out that we are using GNNs and MNNs for ERM and SRM respectively. This is part of our contribution, that is, we see the distribution of graph nodes as the manifold and in turn, the GNN can generalize to unseen data over the manifold. As in practice, it is unrealistic to operate in the continuous manifold space, while this generalization bound provides a guarantee that a GNN trained on a finite sampled graph can approximate the performance of the MNN.

Question L.308 Yes, that is true.

Question L.311 This is a good point by the reviewer. What we assume here is that the $C_L$ holds over the function class, and therefore the bound is valid.

Question L.378 The reviewer makes a good point. Note that we have plot one curve, which is the one that better approximates the points after the training accuracy is below $95$. Alternatively, we can fit the points before $95$. In both cases, the bound will be linear (in log scale), and will be an upper bound to the GA as our theory predicts. As the reviewer points out, the plots show that the GA presents a switching behavior (which is very interesting!), but that our theory does not model. This would be an interesting future direction.

Question L.378 Related to the previous We have run experiments on untrained GNN for the toy examples, and the same properties hold.

Question L.474 Yes it is the so-called transductive learning. The test set is given, we do not modify it.

Question L.478 The reviewer raises two points. The first one is that we used GNNs for both training and testing. We cannot use a MNN given that in practice, the datasets are finite without full access to the underlying continuous model. We added a new section in the appendix (Appendix I) which shows that these graphs are low dimensional and therefore the manifold assumption is valid. That is why we believe that running GNNs on unseen data is a valid way to estimate the performance of the MNN. The second point the reviewer makes is regarding transductive learning. Please note that our theory does accommodate transductive learning. To see this note that the dimension of x (number of points in the graph), and the dimension of the labeled points (dimension of y), need not be the same. Plus, the expression in equation (11) is pointwise and the loss is over the dimension of y. In the main body of the paper, we considered these two the same for simplicity, but they do not need to be. By using different values for $x$ and $y$, the transductive learning framework is accommodated. We thank the reviewer for this point.

Question L.497 We agree with the reviewer that there might be better ways of computing the linear correlation. We would like to point out that our bound is an upper bound, which holds in practice, and the trends (increasing with continuity constant and decreasing with the number of nodes) are correct with the support of this correlation test.

Question L.506 The reviewer raises the point that it should be verified that increasing the regularizer decreases the value of $C_L$. Note that measuring the proper value of $C_L$ is very computationally costly in practice given that we are using large graphs whose spectral decomposition requires large amounts of memory, and can only be done partially. The idea behind the regularizer is that it will reduce the norm of the weights in the GNN (penalizing different layers differently), and this will translate into a smaller Lipschitz constant. Having said that, for regular MLPs it is shown that increasing the value of weight decay decreases the Lipschitz constant. The precise computation of the Lipschitz constant is itself a research topic. We do not believe that we are making a big claim here, and these experiments are a way to showcase the spectral continuity effect on the generalization gap.

Question L.506 Related to the previous We note that there is the probability term $\delta$ in Theorem 1. If we take $\delta$ as the order $1/N$, the term with $C_L$ also takes the lead compared with the term $(\log N/N)^{1/d}$. In the logarithmic scale, being that $C_L$ is a multiplicative factor, it should not change the rate but it should change the position of the curve. The fact that a curve with larger $C_L$ is above one with smaller $C_L$ is proof that indeed an indication that the theory is correlated with what is seen in practice.

We thank the reviewer for their comments.

Regarding Weakness 1, the generalization definition we employed aligns with the classical generalization definition. Typically, generalization gaps state that for all functions in the hypothesis class, the difference between empirical and statistical errors is bounded. See the following references:

• Foundations of Machine Learning - Mohri et al. Chapter 2, Theorem 2.13
• The nature of statistical learning theory - Vapnik, Chapter 3, Theorem 3.1

The point raised by the reviewer is valid though. As we can see the manifold as the underlying distribution of the graph nodes, the expectation of the loss value in equation (15) over all the nodes sampled from the manifold can indeed be written as equation (16). This is because the expectation of the sampled point is taken with respect to the measure $\mu$ over the manifold.

Regarding Weakness 2, the discriminability of the filter can be practically measured through the training loss. The relationship between the continuity constant and the training loss can be understood as follows: filter functions with larger continuity constants encompass a larger hypothesis function class, allowing the GNNs to better approximate the target functions during training. This leads to a smaller training loss. We have added the explanation of discriminability in the updated version in Section 4.1.

Regarding Weakness 3, we thank the reviewer for the opportunity to showcase our novelty. Our result is novel in a variety of ways:

1. The analysis is based on manifolds and allows graphs constructed with geometric information. This improves upon graphon results with better physical interpretations in practice as data often does lie in some manifold. Our results show that under this assumption there are interesting consequences for GNN generalization that do not follow from other existing analyses.
2. Our work provides a unifying theory that allows us to explain both node classification and graph classification, which is unique and novel compared with other works.
3. We explicitly show that the statistical generalization of a GNN depends on the spectral properties of the graph filters that compose individual layers. The practical implication is that there is a tradeoff between generalization and discriminability of the GNN. This tradeoff is frequency-dependent (frequencies correspond to eigenvalues of the graph Laplacian operator). Features that are associated with large eigenvalues of the graph Laplacian (high-frequency components) are inherently more difficult to discriminate. It follows that one can improve generalization by using filters with smaller continuity constants. That is to say, one can give up discriminability to improve generalization, but this is only mainly sacrificing the discriminability of high-frequency features.

Regarding the questions, the reviewer makes a good point. We have changed the kernel function representation in Definition 2 and 3 by adding a subscript to avoid the abuse of notations. We thank the reviewer for pointing this out. We thank the reviewer for pointing this out.

We thank the reviewer for their time and effort.

Regarding Weakness 1, we would like to clarify that in the experiments we add a regularizer to ensure the filters in GNNs satisfy Definition 4. To do so, we can compute equation (108) in the appendix as the penalty term that we add to the loss function during the training process as a continuity regularization:

with $\alpha$ as the regularizer term shown in Figure 7.

Furthermore, for the graph signals considered in the paper, it is important to note that in practice, most signals possess finite energy, and the graphs used in our experiments have a finite number of nodes. Therefore, there exists a value $\lambda$ such that Definition 1 holds. Furthermore, in many practical applications, considering high-frequency components are often associated with noise or fluctuations without useful information, preprocessed data are commonly bandlimited. In all, both Definition 1 and 4 are fulfilled in practice given the finite size of the graphs, and GNNs are trained with continuity penalty terms in our experiments.

Regarding GCN not matching the filter structure analyzed on the paper, we believe it does. When GCN is applied successive times, it is equivalent to multiplying by the square of the graph shift operator matrix. Let us point out that equation (2) expresses the diffusion over the graph in matrix form and it is very general and it includes GIN, and GCN among other architectures. To show that GCN and equation (2) are indeed equivalent, this is another way of expressing equation (2):

where $\mathbf{H_{lf}}\in \mathbb{R}^{F_{l-1}\times F_l}$ is the coeficient matrix assocaited with layer $l$, and $\mathbf{X_{l}}$ is the feature matrix of layer $l$. Analogously, this is the GCNconv layer from pytorch geometric, which is based on the paper Semi-Supervised Classification with Graph Convolutional Networks can be written as follows:

Note that when $k=1$, the two equations are equivalent. When the previous equation is applied $k$ times, it is equivalent to $k$ in our equation (2).

Regarding Weakness 2, the reviewer is correct. Given that manifold signals are not available in most practical scenarios, we sample the manifold at a very fine resolution and we run GNNs on these large graphs.

Regarding Weakness 3, the reviewer suggests that we should study the separate runs of MNNs. We would like to point out that this is very similar to what we have shown in the paper. What the reviewer has suggested can be derived as a corollary of Theorem 1 by using the triangle inequality. We have added this in the appendix. In the experiments, we resampled the graphs for each run of the experiments as the reviewer suggested with the number of sampled points large enough to approximate the underlying manifold.

We thank the reviewer for the questions and we have added more explanations to the corresponding parts in the updated draft. We hope that the questions were addressed.