A Manifold Perspective on the Statistical Generalization of Graph Neural Networks
Authors: Zhiyang Wang
Juan Cervino
Alejandro Ribeiro
Venue: ICML 2025 poster (2025)
Keywords: graph neural networks
generalization
Primary area: deep_learning->graph_neural_networks
TL;DR: We leverage manifold theory to analyze the generalization gap of GNNs sampled from manifolds in the spectral domain.

Abstract: Graph Neural Networks (GNNs) extend convolutional neural networks to operate on graphs. Despite their impressive performances in various graph learning tasks, the theoretical understanding of their generalization capability is still lacking. Previous GNN generalization bounds ignore the underlying graph structures, often leading to bounds that increase with the number of nodes – a behavior contrary to the one experienced in practice. In this paper, we take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain. As demonstrated empirically, we prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions. Notably, our theory explains both node-level and graph-level tasks. Our result has two implications: i) guaranteeing the generalization of GNNs to unseen data over manifolds; ii) providing insights into the practical design of GNNs, i.e., restrictions on the discriminability of GNNs are necessary to obtain a better generalization performance. We demonstrate our generalization bounds of GNNs using synthetic and multiple real-world datasets.

A Manifold Perspective on the Statistical Generalization of Graph Neural Networks
Zhiyang Wang"
Juan Cerviño 2
Alejandro Ribeiro
Abstract
empirical success across various fields, including but not limited to weather prediction (Lam et al. (023). protein structure prediction in biochemistry (Jumper et al. 2021 Strokach et al. 2020), resource allocation in wireless com- munications (Wang et al. 2022a), social network analysis in sociology (Fan et al.
Graph Neural Networks (GNNs) extend convolu- tional neural networks to operate on graphs. De- spite their impressive performances in various graph learning tasks, the theoretical understand- ing of their generalization capability is still lack- ing. Previous GNN generalization bounds ignore the underlying graph structures, often leading to bounds that increase with the number of nodes- behavior contrary to the one experienced in prac- tice. In this paper, we take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain. As demonstrated empirically, prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions. Notably, our theory explains both node-level and graph-level tasks. Our result has two implications: i) guaranteeing the generalization of GNNs to un- seen data over manifolds; ii) providing insights into the practical design of GNNs, i.e., restrictions on the discriminability of GNNs are necessary to obtain a better generalization performance. We demonstrate our generalization bounds of GNNs using synthetic and multiple real-world datasets.
2020). point cloud in 3D model recon-
struction (Shi & Raj Rajkumar
2020) and learning simulators
(Fortunato et al. 2022).
The effectiveness of GNNs relies on their empirical ability to predict over unseen data. This capability is evaluated theoretically with statistical generalization in deep learning theory (Kawaguchi et al., 2017), which quantifies the dif- ference between the empirical risk (i.c. training error) and the statistical risk (i.e. testing error). Despite the abundant evidence of GNNs' generalization capabilities in practice, developing concrete theories to explain their generaliza- tion is an active area of research. Many recent works have studied the generalization bounds of GNNs without any dependence on the underlying model responsible for gen- erating the graph data (Scarselli et al. 2018; Garg al.) 2020 Verma & Zhang 2019). Generalization analysis on graph classification, when graphs are drawn from random limit models, is also studied in a series of works (Ruiz et al.,
2023 Maskey et al. 2022 2024 Levie 2024). In this work, we take the manifold perspective to formulate graph data on continuous topological spaces, i.c., manifolds. We empha- size that manifolds are realistic models to generate graph data that enable rigorous theoretical analysis and deep understanding of the behaviors of GNNs.
1. Introduction
We explore the generalization bound of GNNs through the lens of manifold theory on both node-level and graph-level tasks in the spectral domain. The graphs are constructed based on points randomly sampled from underlying mani- folds, indicating that the manifold can be viewed as a sta- tistical model for these discretely sampled points. As deep learning architectures have been established over manifolds (Wang et al.) 2022b] Chew et al. (2024), the convergence of GNNs to manifold neural networks (MNNs) and the al- gebraical equivalence of these two frameworks facilitate a detailed generalization understanding of GNNs through spectral analysis. We demonstrate that, with an appropriate graph construction based on the sampled points from the
Graph convolutional neural networks (GNNs) (Scarselli jet al.) 2008 Defferrard et al., 2016; Bruna et al. 2014) have emerged as one of the leading tools for processing graph-structured data. There is abundant evidence of their
"Equal contribution 'Department Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, USA LLaboratory of Information and Decision Systems (LIDS), Mas- sachusetts Institute of Technology, Cambridge, USA. Correspon- dence to: Zhiyang Wang <zhiyangw @ wcas.ccannnnn... edun,, Juan Cerviño <jeervino@ mit.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
manifold, the generalization gap between empirical and sta- tistical risks decreases with the number of sampled points in the graphs (Figure Icp on both node-level and graph-level tasks. More importantly, the generalization gap increases linearly with the continuity constants of frequency response functions of graph filters composing the GNN (Figure ld). We observe that with spectral continuous filters, the GNNs are generalizable across different nodes or graphs generated from the same underlying manifold. This provides insight into the practical graph filter design from a spectral perspec- tive. Moreover, the theoretical results indicate a trade-off between the discriminability and generalization capability of GNNs, suggesting that restrictions on the discriminability of GNNs are necessary to maintain generalization perfor- mance.
The authors in (Verma & Zhang 2019) analyze the gener- alization of a single-layer GNN based on stability analysis, which is further extended to multi-layer GNN in ZZou & Wang (021). In 4Ma et al. (021), the authors give a novel PAC-Bayesian analysis on the generalization bound of GNNs across arbitrary subgroups of training and test- ing datasets. The authors derive generalization bounds for GNNs via transductive uniform stability and transductive Rademacher complexity in (Esser et al. [021 Cong et al.,
2021 Tang & Liu 2023). The authors in Yehudai et al. 2021) propose a size generalization analysis of GNNs cor- related to the discrepancy between local distributions of graphs. Different from these works, we consider a continu- ous manifold model when generating the graph data, which is theoretically powerful and realistic when characterizing worldw data. Furthermore, the generalization bounds proved in these works either grow with the size of the graph (Esser et al. 2021 Tang & Liu 20233 Scarselli et al. with the node degree of the graphs (Cong et al. 2021 or the
We introduce novel unified analysis of the generaliza- tion of GNNs to unseen nodes and graphs, by relating the GNNs with MNNs in the spectral domain. We further pro- pose restrictions on the discriminability of GNNs from the spectral perspective which results from assumptions on the continuity of the filter frequency response functions. We provide extensive experiments both on synthetic and real- world datasets verify our generalization conclusions. Our contribution is four-fold:
201 8),
maximum eigenvalues of the graph (Verma & Zhang 2019).
Notably, our generalization bound decreases with the size of the graph given that it depends on the spectral properties of the filter functions over the manifold.
1. We prove the generalization bound of GNNs graphs generated from an underlying manifold on both node- level (Theorem I and graph-level (Theorem 2 by relating the algebraically equivalent GNNs and MNN in the spectral domain.
Graph level tasks There are also related works on the gen-
eralization analysis of GNNs on graph-level tasks. In (Garg ct al. 2020). the authors form the generalization bound via Rademacher complexity. The authors in (Liao et al., 2020) build PAC-Bayes framework to analyze the generaliza- tion capabilities of graph convolutional networks (Kipf & Welling 2016) and pressage-passingg GNNs (Gilmer et al.
2.
We provide novel generalization gap bounds that de- crease linearly with the nodes of the graph in the log- arithmic scale, and increase linearly with the spectral continuity constants (Assumption) I of the filter func- tions.
2017), based on which the authors in (Ju et al. 2023) im-
prove the results and prove a lower bound. The bounds either grow with the number of nodes (Liao ct al. 2020) or the degree of the graphs (Garg et al., 2020) while our bound decreases with the number of nodes in the graph given that it better approximates the underlying model the manifold.
3. We uncover an important trade-off between the discrim- inability and the generalization gap of GNNs, which guides practical GNN designs.
The works in (Maskey et al. 2022 2024 Levie 2024) are most related to ours, which also consider the generalization of GNNs on a graph limit model, in their case graphon. Different from our setting, the authors see the graph limit as a random continuous model. They study the generaliza- tion of graph classification problems with message-passinng GNNs with graphs belonging to the same category sampled from a continuous limit model. The generalization bound grows with the model complexity and decreases with the number of nodes in the graph. We show that GNN trained on a single graph sampled from each manifold is enough, and can generalize and classify unseen graphs sampled from the manifold set.
4. We verify the dependence of our generalization gaps on parameters, especially the continuity parameter, with a synthetic dataset- - chair manifold- - and eight real- world datasets- ArXiv, Citeseer, etc.
2. Related works
2.1. Generalization bounds of GNNS
Node level tasks We first give a brief recap of the gener- alization bounds of GNNs on node level tasks. In (Scarselli et al. 2018), the authors give a generalization bound of GNNs with a Sopnik-Chervonentee dimension of GNNs.
2

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Nadee 6o Nadee
135
Spearal Corlinity Candrut 26.72 Spedrall Contiality cansrurt
138 20
339 10
Contanaty Conalark.
(a) Chair Manifold
(b) Sampled Chair
(c) Gen. Gap vs. Num. of Nodes
(d) Gen. Gap vs. Continuity Constants
Figure 1: Synthetic experimental results are shown on the uniformly sampled chair manifold. We construct a graph with different numbers of nodes, fix the weights of a GNN, and compute the generalization gap. We construct the graph by computing the edges for nodes that are c close (cf. equation 3) In Figure [c] we fix the spectral continuity constant (see Assumption D and vary the number of nodes. As our theory predicts, we see that smaller spectral continuity constant translates into smaller generalization gap the blue line is below the green line which is below the orange line. In Figure ld we fix the number of nodes in the graph and vary the spectral continuity constant in the GNN. For the same number of nodes, larger spectral continuity constant translates into a larger generalization gap.
2.2. Neural networks on manifolds
define the graph Laplacian == diag (A1) A where A E RN is the weighted adjacency matrix. Graph signals are functions mapping nodes to a feature value. We write vector E R&,, with each entry [x]; representing the function value node i.
Geometric deep learning has been proposed in (Bronstein et al. 2017) with neural network architectures raised in manifold space. The authors (Monti et al. 2017) and
(Chakraborty et al., 2020) provide neural network archi-
tectures for caanifold-valueee data. In (Wang et al.) 2024b) and (Wang al.) 2022b), the authors define convolutional operation over manifolds and see the manifold convolution as generalization of graph convolution, which establishes the limit of neural networks on large-scale graphs as mani- fold neural networks (MNNs). The authors in (Wang al.] 2024a Chew et al., 2023 Johnson al.] 2025) further es- tablish the relationship between GNNs and MNNs with non-asymptotic convergence results for different graph con- structions. Some studies have used graph samples to infer properties of the underlying manifold itself. These proper- ties include the validity of the manifold assumption (Feffer- man et al. 2016), the manifold dimension (Farahmand et al. 2007) and the complexity of these inferences (Narayanan & Niyogi 2009 Aamari & Knop 202T). Other research has focused prediction and classification using manifolds and manifold data, proposing various algorithms and methods.
Graph convolutions and frequency response A graph convolutional filter be is composed of consecutive graph shifts by graph Laplacian, defined as ha hc Σ k== L with { as filter parameters. We re- place L with eigendecomposition L = VAV", where V is the eigenvector matrix and A is a diagonal matrix with eigenvalues {As,Nv IN as the entries. The spectral represen- tation of graph filter is
V ha
(I)
This leads to a point-wise frequency response of the graph convolution as h((A) = Σk hg
Graph neural networks A graph neural network (GNN) is a layered architecture, where each layer consists of bank of graph convolutional filters followed by point-wise nonlinearity
Impressive examples include the Isomap algorithm (Choi
& Choil 2004 Wu & Chan 2004 Yang et al. 201 6a) and other manifold learning techniques (Talwalkar et al.) 2008).
R + R. Specifically, the 1-th layer of GNN that produces Fi output features {x() with Fi-1 input features
These techniques aim infer manifold properties without analyzing the generalization capabilities of GNNs operated on the sampled manifold.
Fi { is written as
x = a
Σ 9=1
log (L)x h
(2)
3. Preliminaries
3.1. Graph neural networks
for each layer = 1,2 L. The graph filter h (L) maps the q-th feature of layer 1 to the p-th feature of layer I. We denote the GNN as a mapping & (H, x). where E H. RRP denotes set of the graph filter
Setup An undirected graph G = (V,E, W) contains a node set V with N nodes and an edge set C V x V. The weight function W: E R assigns values the edges. We
3

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
coefficients with a finite P dimension all layers and ' denotes the set of all possible parameter sets.
Manifold neural networks A manifold neural network (MNN) is constructed by cascading I. layers, each of which contains a bank of manifold convolutional filters and a point- wise nonlinearity a R - R. The output manifold function of each layer / = 1,2 can be explicitly denoted as
3.2. Manifold neural networks
Setup We consider d-dimensional compact, smooth and differentiable Riemannian submanifold . embedded in M-dimensional space Ie with finite volume. This induces measure μ which has a non-vanishing Lipschitz continuous density with respect to the Riemannian volume over the manifold with p .M- + oo), assumed to be bounded as 0 < Pmin I p(x) S Pmaz < Do for all æ E .M. The manifold data supported on each point x E .M is defined by scalar functions f . - TR. (Wang al. (024b). We use L2(M) to denote L functions over M with respect to measure μ.. The manifold with probability density function is equipped with a weighted Laplace operator (Grigor'yan yan 2006). generalizing the Laplace- Laplace-Beltrami operator as
Fi Σ 9=1
f(x)= =0
h nd
(6)
where 12-1 S q S FI-1 is the q-th input feature from layer - 1 and ff. S Fi is the p-th output feature of layer 1. We denote MNN as a mapping ( Lp. f), where H E H C R. is collective set of filter parameters in all the manifold convolutional filters.
4. Generalization analysis of GNNs based on manifolds
cpf --
-iv
1 2p
(3)
We consider manifold M defined in Section 3.2 with weighted Laplace operator Lp as defined in equation Since functions f E L²(M) characterize information over manifold .M, we restrict our analysis to a finite-dimensional subset of (2M up to some eigenvalue of Lp. defined as a bandlimited signal.
3
with div denoting the divergence operator of M and V denoting the gradient operator of M (Bronstein al., 2017
Gross& & Meinrenken 2023
Manifold convolutions and frequency responses The manifold convolution operation is defined relying on the Laplace operator Lp and on the heat diffusion process over the manifold 4Wang et al., 20246). For a function f e (MM as the initial heat condition over M, the heat condition diffused by a unit time step can be explicitly writ- f. f. A manifold convolutional filter (Wang al. ten -L
Definition 1. A manifold signal f E (MM is bandlimited if there exists some > O such that for all eigenpairs ()i, Φ.) 1 of the weighted Laplacian Lep when X X, we have (f, d.) 0.
Suppose we given set of N i.i.d. randomly sampled points XN = { over M, with x; M sampled ac- cording to measure μs. We construct a graph G(V,E, W) on these N sampled points XN. where each point x, is a vertex of graph G, i.e. V =XN- Each pair of vertices (Iz 23y) is connected with an edge while the weight attached to the edge W(x,, 22y) is determined by kernel function K,, The kernel function is decided by the Euclidean distance ||x; 22y between these two points. The graph Laplacian denoted as LN can be calculated based on the weight func- tion (Meriis 1995). The constructed graph Laplacian with an appropriate kernel function has been proved to approxi- mate the Laplace operator E, of M (Calder & Trillos 2022] Belkin & Niyogil 20088) Dunson et al., 2021). We present the following two definitions of K., Definition 2 (Gaussian kernel based graph (Belkin & Niyogi 2008)). The graph G(XN, E,W, W) can be con- structed in (I), E E, as dense graph degree when the kernel function is defined as
2024b) can be defined in diffuse-ande -nd--anddnmmm manner as
K-1
-(z)= = h(Ca)(())
Σ huE kKp [xx) k=
(4)
with the k-th diffusion scaled with a filter parameter ha E IR. We consider the case in which the Laplace operator is self- adjoint, positive-semidefintte and the manifold M is com- pact. In this case, Cp has real, positive and discrete eigenval- ues ( written L, d where Φ, is the eigen- function associated with eigenvalue >ç The eigenvalues are ordered in increasing order as 0- = A < A2 < Xa < .... and the eigenfunctions are orthonormal and form an eigen- basis of (.M). When mapping a manifold signal onto the eigenbasis Ifl. = (f, Φ.) M = JM (z)))((z)d)(11) the manifold convolution can be seen in the spectral domain as
K-
G =
Σ h&e k=
RA
[fk.
(5)
|12 13112
||
W(z,,;)) = Ke,
E
Hence, the frequency response of manifold filter is given by R(>)= = Σk= h
1
1 1,
(8)
N e/2++ (AT))

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
b(A)
AS 1. The frequency response function of the filter satisfies
[(Aa| = -
|R'CN| S CCL X (0),
(12)
A/a
X
with CL a spectral continuity constant that regularizes the smoothness of the filter function.
Figure 2: Frequency response illustration
To introduce the first of our two main results, require introducing two assumptions.
The weight function of a Gaussian kernel based graph is defined on unbounded support (i.e. [0, oo)), which connects I; and zj regardless of the distance between them. This results in a dense graph with N2 edges. In partieular, this Gaussian kernel based graph has been widely used define the weight value function due to the good approximation properties of the corresponding graph Laplacians to the manifold Laplace operator (Dunson et al. 2021 Belkin &
AS 2. (Normalized Lipschitzz nonlinearity) The nonlinearity is normalized Lipschitz continuous, i.e., lo(a) o(b) S
la b), with (0) =
AS 3. (Normalized Lipschitz loss function) The loss func- tion E is normalized Lipschitz continuous, i.e., |E(ye,,) V) f(y.. v)l S 111 -3gl. with Ely, y) =0. O.
Assumption is satisfied by most activations used in prac- tice such as ReLU, modulus and sigmoid.
Niyogi 2008 Xie et al. 2013).
Definition (e-graph (Calder & Trillos 2022 The graph G(XN, E, W) can be constructed as an c-graph with the kernel function defined as
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 μ over the manifold. The empirical risk over the sampled graph that we trained to minimize is therefore defined as
| -2,11
W(a; Ke,2
(9)
2
1 1 B3 23
(10)
ed/2+1 and
e
1 N
with (z) E. where aa is the volume of unit ball of dimension d and 1 is the characteristic funcciooo
Ra =
e (( Lx,),, ()))
(13)
The weight function of an c-graph is defined on bounded support, i.e., only nodes that are within a certain distance of one another can be connected by an edge. It has also been shown to provide a good approximation of the manifold Laplace operator (Calder & Trillos 2022).
The statistical risk over the manifold is defined as
(M = SN ( (p) du(x).
(14)
The generalization gap is defined to be
4.1. Manifold label prediction via node label prediction
GA = sup RR (H) (H))
(15)
Suppose we have an input manifold signal f E (2(M) and a label (i.e. target) manifold signal g E (MM over M. With MNN (H, Lp: +). we predict the target value g(z) based input fxx) at each point e M. By sam- pling N points NN over this manifold, we can approximate this problem in a discrete graph domain. Consider a graph E W) constructed with X,v as either a Gaussian kernel based graph (Definition 2 or an e-graph (Definition B equipped with the graph Laplacian Ly. Suppose we are given graph signal y) sampled from {ffgg} to train GNN & (H, LN, -), explicitly written as
HER
Theorem 1. Suppose the GNN and MNN filters satis- fying Assumption 2 Thave L layers with F features in each layer and the imput signal is bandlimited (Definition 77 Un- der Assumptions 3nd holds in probability at least that
log log N 1
GA GASF Ca
(16)
N
+ LPL-1
E + (CICC +2) N
x² Vlog(L/o)
6N
[x]; = f(ar))
[y]: g(x;) for all x, E XN. (11)
when d > 3. If = 2, the first term would be FLCC (log NY3/0 (logN)a/0
We assume that the filters in MNN & Lp. and GNN @G (H, .). satisfy a continuity assumption as follows, which is illustrated in Figure?)
with C₁, Cz. and Cg depending on the geometry M, CL is the spectral continuity constant in Assumption
N1/2
5

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
1. When the graph is constructed with Gaussian kernel
yk R as the scalar target label. The final output of the GNN is set to be the average of the output signal values each node while the output of MNN (H, Sp. f.) is the statistical average value of the output signal over the manifold. A loss function evaluates the difference between the output of GNN and MNN with the target label. The empirical risk of the GNN
equation 7 then [og(C/5)
2. When the graph is constructed an e-graph as equa- tion then [
Proof. See Appendix D for proof and the definitions of C1. C2 and C3.
I1
Nx
RG (H) Σe
8
1
Σ
+ (H, LNN, xx)](s
N
Theorem [ shows that the generalization gap decreases ap- proximately linearly with the number of nodes N in the logarithmic scale, that is, log(GA) Ó log N) with O the O notation that ignores logarithmic orders, 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,. (Assumption D a smaller Ct leads to a smaller generalization gap bound, and thus a better generalization capability. While smaller Cz leads smoother GNN, it discriminates fewer spectral com- ponents and, therefore, possesses worse discriminability. Consequently, we may observe a larger training loss with these smooth filters, as filters with worse discriminability encompass a smaller hypothesis function class and deterio- rate the GNNs' approximation to the target functions during training. Since the testing loss can be upper bounded by the sum of training loss and the bound of generalization gap, on smoother GNN (a smaller Cz),, the performance on the unseen training data will be closer to the performance testing data. Therefore, having GNN with a smaller spec- tral continuity constant Cz can guarantee more generaliz- able performance over unseen data from the same manifold. This also indicates that similar testing performance can achieved by either GNN with smaller training loss and worse generalization 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 discrim- inability, resulting in a smaller testing loss decided by the spectral continuity constant of the GNN.
(17)
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
K (o(
RM (H) Σe
D(H, (R)
Mr
1=
(18)
The generalization gap is therefore
GA sup |RM ( RG(H)) HEW
(19)
Theorem 2. Suppose the GNN and MNN with filters satis-
fying Assumption I havee L layers with F features in each layer and the input signal bandlimited (Definition 77 Un- der Assumptions and B holds in probability at least 1 5 that
GA SLF
Σ [CGCL (12l0+C5((1
Ck Nk
(20)
k=
GNN with larger training loss and
FL Σ vlog(1/0)
K
log No
6N
N
when d 2
3. If d = 2, the last term would be ,with C₁, Cz. and C3 depending on
CL. ExE the geometry of M, Cr is the spectal continuity constant in Assumption 7
(log 3/4
N1/2
4.2. Manifold classification via graph classification
Suppose we have a set of manifolds {M&]K each of which is de-dimensional, smooth, compact, differentiable and embedded in RM with measure Pk- Each manifold Mr equipped with weighted Laplace operator Lpu.k is labeled with yk E R. We assume to have access to N₂ randomly sampled points according to measure (4 over each manifold M2 and construct K graphs { [G+JK, jkzi with graph Laplacians LN The GNN G
When the graphs are constructed with Gaussian ker- nel equation 7 then ex
(Iog(C/0)
Nx
2. When the graphs are constructed as e-graphs as equa- tion 9 then ck (1og(CNe/8))
3414
Nv
Ly..,x)) is trained on this set of graphs with X as the input graph signal sampled from the manifold signal fa E 1 (M2)) and
Proof. See Appendix F for proof and the definitions of C1, C2 and Ca.
6

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
No Accoroa 1%6
bcc Caroyy (%6)
Number of nodes in training
Number of nodes in training
Number nodes in training set
Number nodes in training set
Train 64 hidden units
Thain 128 hidden units
Train 256 hidden units
-+- Train 512 hidden units
128 hidden
512 hidden
Accuracy Difference 186
Accunicy Difference (K6)
Loss Diffornnc
Locs Di Hortence
Number of nodes in training set
Number of nodes in sea
Number nodes in training set
Number nodes in training set
(a) Arxiv: Two Layers
(b) Arxiv: Three Layers
(c) Arxiv: Two Layers (Loss)
(d) Arxiv: Threc Layers (Loss)
Accuracy diference 1%6
Accurasy difference (%))
Accuress difference
3x12
10 Number of nodes in training set
10
33'
Number of nodes in training set
Number of nodes in training set
Difference layers hidden units
Difference layers hidden units
Difference 3 layers 32 hidden units
Difference layers hidden units
Linear Fit layers hidden units
Linear layers 64 hidden units
Linear Fit layers 32 hidden units
Linear Rit layers hioden units
Loss ritternncc
Loss dffference
Loss dffference
Number of nodes in training set
Number of nodes in training set
Number of nodes in training set (g) PubMed
(e) Cora
CiteSeer
Accueaao dffeeerce
127
20
17
10"
Diffeence 2 layens sidden unts
Difference 2 layers 54 hidden unit
. Differnce layers nizden uniss Uneer 11.3 layam 32 hisses units
Differnnce layers hoden uniti Lineer TE. layera d4 hidden unts
Uneer 1.8 layerra hidden un
Linea TV layen 64 hidden unis
(h) Amazon- Amazon-Ratings
Roman- Empire
ii CoAuthors CS
(k) CoAuthors Physics
Figure 3: Merged visualization of all datasets: Arxiv (top row), Planetoid (middle row), and Heterophilic and CoAuthors datasets (bottom row). Each row provides accuracy and loss generalization gaps across different configurations and datasets.
Theorem shows that single graph sampled from the un- derlying manifold with large enough sampled points N₂ from each manifold M2 can provide an effective approx- imation classify the manifold itself. The generalization gap also attests that the trained GNN can generalize clas- sify 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 sam-
pled over each manifold while increasing with the manifold dimension. A higher dimensional manifold, i.e. higher com- plexity, needs more samples to guarantee the generalization. The generalization gap also shows a trade-off between the generalization and discriminability the bound increases linearly with the spectral continuity constant Cy,- That is, to guarantee that a GNN for graph classification generalize effectively, we must impose restrictions on the continuity of

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Accuracs Differnnce (IN)
Tes Accurscy (85)
Accuraco Difference
Accurney (1%)
Number modes training set
Number ofnedes traininng
Spectral regularizer mullipier
Spectral regulariznr muliipirr
+ Muttpller
-4-
Multplier 0.001
-4- Muttpller 0.01
90941 nodes
45670 rodes
22735 nodes
11367 nodes
(a) Accuracy gap vs nodes
(b) Test accuracy vs nodes
(c) Accuracy gap regularizer (d) Test accuracy vs regularizer
Figure 4: Spectral continuity constant effect on generalization gap and test accuracy.
its filter functions, which turn limits the filters' ability to discriminate between different graph features.
whose training accuracy is below 95%. Also, we validate that the bound increases both with the number of features and the number of layers.
We note that our assumption of constant number of fea- tures can be generalized to include different number of features in each layer for both node and graph classification.
To measure the impact of the spectral continuity constant Cz, we add regularizer to the cross-entropy loss (see Ap- pendix J.3) We vary the value of the regularizer, noting that a larger regularizer translates into a smaller Ct and therefore a smoother function. In Figures [4a and we see the empirical manifestation of the bound that we showed (cf. Theorem D -a a GNN with a smaller Cr. (a larger reg- ularizer) will attain a smaller generalization gap. We can see that a larger regularizer (smaller continuity constant CL. green line, regularizer 0.01) attains a smaller generalization gap, and as the regularization decreases (Cz, increases), the generalization gap increases. The effect of having smaller spectral continuity constants C22 the lack of discriminabil- ity of the GNN. As be seen in Figures 4b) and [4] the test error decreases when the multiplier is too large (Cz too small). Therefore, spectral regularize not too large can be shown to guarantee good test accuracy, but if the regularizer is too large, the test accuracy will be hurt by the lack of discriminability of the GNN as shown in Figure 4d In all, we verify the fact that GNN with a smoother spectral response will have smaller generalization gap as shown in Theorem
5. Experiments
In this section, we empirically study the generalization gap in 8 real-world datasets. The task is to predict the label of a node given set of features. The datasets vary in the number of nodes from 169, 343 to 3, 327, and in the number of edges from 1, 166, 243 to 9, 104. The feature dimension also varies from 8, 415 to 300 features, and the number of classes of the node label from 40 to 3. In all cases, we vary the number of nodes in the training set by partition- ing it in {1, 2, 4, 8, 16, 32, 64, 32, 64, 128, 256, 512, 1024) partitions when possible. For both the training and testing sets, we computed the loss in cross-entropy loss, and the accuracy in percentage (%). Our main goal is to show that the rate presented in Theorem [ holds in practice. In Figure 3] we plot the generalization gap of the accuracy the loga- rithmic scale for a two-layered GNN (FigureBar 3aj, and for a three-layered GNN (Figure 3b). On the upper side, we can that the generalization bound decreases with the number of nodes and that outside of the strictly overfitting regime (when the training loss is below 95%), the generalization gap shows a linear decay, as depicted in the dashed line. The same behavior can be seen in Figures 33 and(3l which cor- respond to the loss for and 3 layered GNNs. As predicted by our theory, the generalization gap increases with the num- ber of features and layers in the GNN. The behavior of the training and testing accuracy as a function of the number of nodes is intuitive. For the training loss, when the number of nodes in the training set is small, the GNN can overfit the training data. As the number of features increases, the GNN's capacity to overfit also increases. In Figures Be to we present the accuracy generalization gaps for and layers with 32 and 64 features. In the overfitting regime, the rate of our generalization bound seems to hold - decreases linearly with the number of nodes in the logarithmic scale. In the non-ovenee overfiiiii regime, our rate holds for the points
12,
6. Conclusion
We study the statistical generalization of GNNs from a man- ifold perspective. We consider graphs sampled from man- ifolds and prove that GNNs could effectively generalize to unseen data from the manifolds when the number of sampled points is large enough and the filter functions are continuous in the spectral domain. We verify our theoreti- cal results on both synthetic and real-world datasets. The impact of this paper is to show a better understanding of GNN generalization capabilities from a spectral perspective relying on a continuous model. Our work also motivates the practical design of large-scale GNNs. Specifically, in order to achieve a better generalization, it is essential to restrict the discriminability of GNNs by putting assumptions on the spectral continuity of the filter functions in the GNNs.
3k
8

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Impact Statement
References
In this work, we explore the statistical generalization of GNNs from manifold perspective by considering graphs sampled from manifolds. The impact of our work relies showing that GNNs effectively generalize to unseen data from the manifolds when the number of sampled points is large enough and the filter functions are continuous in the spectral domain. Our work also motivates the practical design lcrge-scale GNNs given that training on larger graphs attains a smaller generalization gap. Lastly, we ob- serve that other than training on larger graphs, is essential to restrict the discriminability of GNNs by putting assump- tions on the spectral continuity of the filter functions in the GNNs.
Aamari, E. and Knop, A. Statistical query complexity of manifold estimation. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 116-122, 2021.
Arendt, W., Nittka, R., Peter, W., and Steiner, F. Weyl''s law: Spectral properties of the Laplacian in mathematics and physics. Mathematical analysis of evolution, information, and complexity, pp. 1-71, 2009.
Belkin, M. and Niyogi, Towards a theoretical founda- tion for laplacian- based manifold methods. Journal of Computer and System Sciences, 74(8): 2008.
Billio, M., Getmansky. M., Lo, A. W., and Pelizzon, L. Econometric measures of connectedness and systemic risk the finance and insurance sectors. Journal of financial economics, 104(3):535 559, 2012.
Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., and Van- dergheynst, P. Geometric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34 (4):18 42, 2017.
Bruna, J., Zaremba, W. Szlam, A., and Lecun, Y. Spectral networks and locally connected networks graphs. In International Conference on Learning Representations (ICLR2014), CBLS, April 2014, 2014.
Calder, and Trillos, N. G. Improved spectral convergence rates for graph Laplacians on E-graphs and k-NN graphs Applied and Computational Harmonic Analysis, 60:123- 175, 2022.
Cervino, J., Ruiz, L., and Ribeiro, A. Learning by transfer- ence: Training graph neural networks on growing graphs. IEEE Trunsactions on Signal Processing, 71:233-247, 2023.
Chakraborty, R., Bouza, J., Manton, J. H., and Vemuri, B. C. Manifoldnet: A deep neural network for manifold-valued data with applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(2):799-811 2020.
Chew, J., Him, M., Krishnaswamy, S., Needell, D., Perl- mutter, M., Steach, H., Viswanath, S., and Wu, H.-T. Geometric scattering on measure spaces. Applied and Computational Harmonic Analysis, 70:101635, 2024.
Chew, J. A., Needell, D.,, and Perlmutter, M. A conver- gence rate for manifold neural networks. In 2023 Interna- tional Conference Sampling Theory and Applications (SumpTA), pp. 1-5. IEEE, 2023.
Choi, H. and Choi, S. Kernel Isomap. Electronics letters, 40125):1612-1613, 2004.

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Cong, W., Ramezani, M., and Mahdavi, M. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34: 9936-9949, 2021.
Gilmer, J., Schoenholz, S. S., Riley, F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International conference machine learning, pp. 1263-1272 PMLR, 2017.
Defferrard, M., Bresson, X., and Vandergheynst, P. Con- volutional neural networks on graphs with fast localized spectral filtering. Advances in neural information pro- cessing systems, 29, 2016.
Grigor' yan, A. Heat kernels weighted manifolds and applications. Cont. Math, 398(2006):93-91, 2006.
Grano
Gross, G. and Meinrenken, E. Manifolds, vector fields, and differential forms: an introduction to differential geometry. Springer Nature, 2023,
Degroot, M. H. Reaching consensus. Journal of the American Statistical Association, 69(345)118-121,, 1974. doi: 10. 01000000006244999999444444440000 URL
He, J., Kanatsoulis, C. I., and Ribeiro, A. Network alignment with transferable graph autoencoders. arXiv preprint arXiv:2310.03272, 2023.
attps::/www.tandffonlle 10. ww.100000162145..00
Dunson, D. B., Wu, H.-T., and Wu, N. Spectral conver- gence of graph Laplacian and heat kernel reconstruction in L from random samples. Applied and Computational Harmonic Analysis, 55:282-333 336,, 2021.
Johnson, D. R., Chew, J. A., Brouwer, E. D., Krishnaswamy. S., Needell, D., and Perlmutter, M. Manifold filter-
combine networks, 2025. URL https:
org abs/ 230/ 04056
Esser, P., Chennuru Vankadara, I.., and Ghoshdastidar, D. Learning theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Informa- tion Processing Systems, 34:27043-2700 2021.
Ju, H., Li, D., Sharma, A., and Zhang, H. R. Generaliza- tion in graph neural networks: Improved PAC-Bayesian bounds on graph diffusion. International Conference Artificial Intelligence and Statistics, pp. 6314-634 PMLR, 2023.
Evans, L. Measure theory and fine properties of functions. Routledge, 2018.
Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Zidek, A., Potapenko, A., et al. Highly accurate protein structure prediction with AlphaFold. Nature, 596(7873):533-589 2021.
Fan, W., Ma, Y., Li, Q. Wang. J., Cai, G., Tang, J., and Yin, D. graph neural network framework for social recommendations. IEEE Transactions on Knowledge and Data Engineering, 34(5):2033-2047 2020.
Kawaguchi, K., Kaelbling, L. P., and Bengio, Y. Generaliza- tion in deep learning. arXiv preprint 17100:1710.05468, 1(8), 2017.
Farahmand, A. M., Szepesvári, C., and Audibert, J.-Y. Manifoll-adaptive dimension estimation. In Proceed- ings of the 24th international conference on Machine learning, pp. 265-272, 2007.
Keriven, N., Bietti, A., and Vaiter, S. Convergence and stability of graph convolutional networks on large ran- dom graphs. Advances in Neural Information Processing Systems, 33:21512 21523, 2020.
Fefferman, C., Mitter, S., and Narayanan, H. Testing the manifold hypothesis. Journal of the American Mathemat- ical Society, 29(4):983-1049 2016.
Fortunato, M., Pfaff, T., Wirnsberger, P., Pritzel, A., and Battaglia, P. Multiscale meshgraphnets. In ICML 2022 2nd Al for Science Workshop, 2022.
Kipf, T. N. and Welling, M. Semi semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2016.
García Trillos, N., Gerlach, M., Hein, M., and Slepčev, D. Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace- Laplace-Beltrami
Lam, R., Sanchez-Gonzalez, A., Willson, M., Wirnsberger, P., Fortunato, M., Alet, F., Ravuri, S., Ewalds, T., Eaton- Rosen, Z., Hu, W., et al. Learning skillful medium-rane range global weather forecasting. Science, (82(6677):1416 1421, 2023.
Beltrami operator. Foundations of Computa- tional Mathematics, 20x4):827-887, 2020.
Garg, V., Jegelka, S., and Jaakkola, T. Generalization and representational limits of graph neural networks. In In- ternational Conference on Machine Learning, pp. 3419- 3430. PMLR, 2020.
Le, T. and Jegelka, S. Limits, approximation and size trans- ferability for GNNs on sparse graphs via graphops. Ad- vances in Neural Information Processing Systems, 36, 2024.
10

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Lee, J., Kim, H., Lee, J., and Yoon, S. Transfer learning for deep learning graph-structured data. In Proceed- ings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
Osher, S., Shi, Z., and Zhu, W. Low dimensional manifold model for image processing. SIAM Journal on Imaging Sciences, 1064):1699-160, 2017.
Parada-Mayorga, A., Wang, Z., and Ribeiro, A. Graphon pooling for reducing dimensionality of signals and con- volutional operators on graphs. IEEE Transactions on Signal Processing, 2023.
Levie, R. A Sapphon-signal analysis of graph neural net- works. Advances in Neural Information Processing Sys- tems, 36, 2024.
Peyré, G. Manifold models for signals and images. Com- puter vision and image understanding, 113(2):249-660, 2009.
Levie, R., Huang, W. Bucci, I.., Bronstein, M., and Ku- tyniok, G. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22(272):1-59, 2021.
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. A critical look at the evaluation of gnns under heterophily: Are we really making progress? International Conference on Learning Representations, 2023.
Liao, R., Urtasun, R., and Zemel, R. A PAC-Bayesian approach to generalization bounds for graph neural net- works. In International Conference on Learning Repre- sentations, 2020.
Ramakrishna, R., Wai, H.-T., and Scaglione, A. A user guide to low-pass graph signal processing and its appli- cations: Tools and applications. IEEE Signal Processing Magazine, 37(6))74-85, 2020.
Lovász, L. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
Ma, J., Deng, J., and Mci, Q Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34:1048-100 1061, 2021.
Ruiz, L., Chamon, L., and Ribeiro, A. Graphon neural networks and the transferability of graph neural networks. Advances in Neural Information Processing Systems, 33: 1702-1712, 2020.
Maskey, S., Levie, R., Lee, Y., and Kutyniok, G. General- ization analysis of message passing neural networks on large random graphs. Advances in neural information processing systems, 35:4805-4888 2022.
Ruiz, L., Chamon, L. F., and Ribeiro, A. Transferability properties of graph neural networks. IEEE Transactions Signal Processing, 2023.
Maskey, S., Levie, R., and Kutyniok, G. Transferability of graph neural networks: an extended graphon approach. Applied and Computational Harmonic Analysis, 63:48- 83, 2023.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
Maskey, S., Kutyniok, G., and Levie, R. Generalization bounds for message passing networks on mixture of graphons. arXiv preprint arXiv:2404.03443, 2024.
Scarselli, F., Tsoi, A. C., and Hagenbuchner, M. The Vapnik- Chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-2521 2522, 2018.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 101kvv:181..08000 1.05668, 2018.
Merris, R. A survey of graph Laplacians. Linear and Multilinear Algebra, (9( (9(1-)):1933 1995.
Mikolov, T.. Sutskever, I., Chen, K., Corrado, G. S.. and Dean, J. Distributed representations of words and phrases and their compositionality. Advances in neural informa- tion processing systems, 26, 2013.
Shi, W. and Rajkumar, R. Point-GNN: Graph neural network for 3D object detection in point cloud. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1711 2020.
Monti, F., Boscaini, D., Masci, J., Rodola, E., Svoboda, J., and Bronstein, M. M. Geometric deep learning on graphs and manifolds using mixture model CNNs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.
Shi, Y. and Xu, B. Gradient estimate an eigenfunction on a compact Riemannian manifold without boundary. An- nals of Global Analysis and Geometry, 38:21-26. 2010.
2017.
Strokach, A., Becerra, D., Corbi-Verge, C., Perez-Riba A., and Kim, P. M. Fast and flexible protein design using deep graph neural networks. Cell systems, 11(4):402-44 411, 2020.
Narayanan, H. and Niyogi, P. On the sample complexity of learning smooth cuts on a manifold. COLT, 2009.

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Talmon, R., Mallat, S., Zaveri, H., and Coifman, R. Man- ifold learning for latent variable inference in dynamical systems. IEEE Transactions Signal Processing, 63 (15):3843-3856, 2015.
Xie, Y., Ho, J., and Vemuri, B. C. Multtipee atlas construction from heterogeneous brain MR image collection. IEEE transactions medical imaging, 32(3):628-66) 6332, 2013.
Yang, B., Xiang, M., and Zhang, Y. Multi-manifold discrim- inant Isomap for visualization and classification. Pattern Recognition, 55:215-230 2016a.
Talwalkar, A., Kumar, S., and Rowley, H. Large-scale man- ifold learning. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8. IEEE, 2008
Yang, Z., Cohen, W., and Salakhudinov, R. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48.
Tang, H. and Liu, Y. Towards understanding generalization of graph neural networks. In International Conference on Machine Learning, pp. 33674-33719. PMLR, 2023.
PMLR, 2016b.
Verma, S. and Zhang, Z.-L. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Yehudai, G., Fetaya, E., Meirom, E., Chechik, G., and Maron, From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pp. 11975-11986. PMLR, 2021.
Zhou, X. and Wang, H. The generalization error of graph convolutional networks may enlarge with more layers. Neurocomputiig. 424:97-106, 2021.
Von Luxburg, U., Belkin, M., and Bousquet, O. Consistency of spectral clustering. The Annals of Statistics, pp. 555- 586, 2008
Zhu, Q., Yang. C., Xu, Y., Wang. H., Zhang, C., and Han, J. Transfer learning of graph neural networks with ego- graph information maximization. Advances in Neural Information Processing Systems, 34:1766 1779, 2021.
Wang, K., Shen, 7., Huang, C.,, Wu, C.-H., Dong, Y., and Kanakia, A. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-413, 2020.
Wang, Z., Eisen, M., and Ribeiro, A. Learning decentralized wireless resource allocations with graph neural networks. IEEE Transactions on Signal Processing, 70:18 1888-88633) 2022a.
Wang, Z., Ruiz, L., and Ribeiro, A. Convolutional neu- ral networks on manifolds: From graphs and back. In 2022 56th Asilomar Conference Signals, Systems, and Computers, pp. 356-360. IEEE, 2022b.
Wang, Z., Ruiz, L., and Ribeiro, A. Geometric graph filters and neural networks: Limit properties and discriminabil- ity trade-offs. IEEE Transactions on Signal Processing, 2024a.
Wang, Z., Ruiz, L., and Ribeiro, A. Stability to deformations of manifold filters and manifold neural networks. IEEE Transactions on Signal Processing, pp. 1-15, 2024b. doi: ALL109/TSPP2224333787777
Wu, Y. and Chan, I.. An extended Isomap algorithm for learning multi-class manifold. In Proceedings of 2004 International Conference on Machine Learning and Cy- bernetics (IEEE Cat. No. 04EX826), volume 6, pp. 3429- 3433. IEEE, 2004.
Wu, Z., Song, S., Khosla, A., Yu, F., Zhang, L., Tang, X., and Xiao, J. 3D Shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1912- 1920, 2015.
12

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Contents
Introduction
2
Related works
Generalization bounds of GNNs
2.2
Neural networks on manifolds
Preliminaries
Graph neural networks
3.2
Manifold neural networks
Generalization analysis of GNNs based on manifolds
Manifold label prediction node label prediction
Manifold classification via graph classification
6
Experiments
Conclusion
Induced manifold signals
15
Convergence of GNN to MNN
15
Local Lipschitz continuity MNNs
19
Proof of Theorem I
21
Corollary of Theorem
23
F
Proof of Theorem 2
24
Further references
25
Filter Assumption
25
Manifold Assumption
25
Experiment details and further experiments
25
ModelNetI0 and ModelNet40 graph classification tasks
26
Node classification training details and datasets
27
J.3
Spectral Continuity Constant Regularizer
28
Arxiv dataset
28
13

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
13.2
Cora dataset
28
CiteSeer datasel
31
J.344
PubMed dataset
32
133.5
Coauthors CS dataset
32
J.3.6
Coauthors Physics dataset
33
J.3.7
Heterophilous Amazon ratings dataset
34
1.3.8
Heterophilous Roman Empire dataset
35
14

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
A. Induced manifold signals
The graph signal attached to this constructed graph G can be seen as the discretization of the continuous function over the manifold. Suppose f (MM, the graph signal x composed of discrete data values of the function f evaluated at Xv. ie. [ fx;)) for 1,2...,A ,N.. With sampling operator N L2(M) - (Xxx,, the discretization can be written
xN Pxʃ.
(21)
Let Jy be the empirical measure of the random sample as
N
JN =
dz.-
(22)
N
1=1
Let (V:) be the decomposition (García Trillos et al. denotes the closed metric ball of radius r centered at z E M with respect to the Euclidean distance in the Euclidean ambient space. The decomposition can be achieved by the optimal transportation map T M - XN, which is defined by the oo-Optimal Transport distance between j and JAN.
2020 of M with respect to XN with V, C (xx),, where (x();)
doc (14, pN) min esssup 2e T(x)),
(23)
T=T
where TH = jaN indicates that - for every V; M. This transportation map induces the partition V1, V2 --- Vi of M, where V; == 1' ({2:3) with v(V;) N for all 1,... NN. The radius of V; can be bounded as r S Allog N/N) when the manifold dimension d 2 3 and r < A(log //)3////// //1 when d = 2 with related to the geometry of M (Gareía Trillos al., [Theore 2].
The manifold function induced by the graph signal xN over the sampled graph G is defined by
(INxN)(x) = E Lx,,, for all M
(24)
where we denote Iy: (xx > (M) as the inducing operator.
B. Convergence of GNN to MINN
The convergence of GNN on sampled graphs to MNN provides the support for the generalization analysis. We first introduce the inner product over the manifold. The inner product of signals f.g E (MM is defined as
(f.9) = S. f(z)g())dx(z))
(25)
where dz( is the volume element with respect the measure μ over M. Similarly, the norm of the manifold signal is
|1 = (f.f)m
(26)
Proposition 1. Let M C IRM be embedded manifold with weighted Laplace operutor L. and a bandlimited manifold signal f. Graph GN is constructed based on a set of N i.i.d. randomly sampled points X = {11, ,2N' according to measure μ over M. A graph signal x is the sampled manifold function values at Xx. The graph Laplacian LN is calculated based on equation 7 or equation 9 with as the graph parameter. Let (H, Lp: be a MNN on M equation with I. layers and F features each layer. & (H, LN. -) be the GNN with the same architecture applied to the graph Gv. Then, with the filters satisfy Assumption 7 and nonlinearities as normalized Lipschitz continuous, it holds in probability at least 8 that
N LN,
LFL-1 (Cive+ C2p log(1/o)
Σ
(27)
N
N
where C1, O2 are constants defined in the following proof.
15

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Proposition 2. Wang al. 2024a ( Prroposition 2, Proposition 4] Let M IRM be equipped with Laplace operator Lp whose eigendeccompositon given by (ii; Let LN be the discrete graph Laplacian of graph weights defined equation (or equation (.. with spectrum {>i.N, (i.N..r. Fix K E N+ and assume that <(N) z
(log(C/6)/))) 22: (or E = =<(N)= 2 (log(CN/6)/N) 2 Then, with probability at least - 6, we have
X Ve.
{) -.,N S CM.IAIE, ||:. - 0:1l - S CM.2
(28)
0;
with at E {-1,1] for all K and 0 the eigengap of C, i.e., 8, min(A, A1-1. A++1 )1}. The constants Cm,1- CM22 depend d and the volume, the injectivity radius and sectional curvature of M.
Proof. Because (ai, (2,,,,, ... NNN } is set of randomly sampled points from M, based on Theorem 19 in (Von Luxburg et al. 2008) can claim that
(N - (f. (f. = ( (0/(1/
(29)
N
This also indicates that
11 = 1og(1/0) |P -I1fIP
(30)
N
which indicates ||P N fl = IlfllM - (L)6 We suppose that the input manifold signal is Ax--bandimited with M spectral components. We first write out the filter representation as
[h(L))PNS - Pxh(CA)/1 (( Σ
Σ
(31)
M
MWNUANNMPP +
Σ H(N.N)KPNS..W.NO.
(32)
i=M+1
|
N
Σ
(33)
i=M+1
The first part of equation 33 can be decomposed with the triangle inequality as
M
M
(P
M +
((AmN)- (PNf
(34)
In equation 34 the first part relies on the difference of eigenvalues and the second part depends on the eigenvector difference. inequality as
The first term in equation 34 is bounded with
(35)
M [((AA)IAANN- -
< P N fll
(36)
M
< P fll
CMICIVON
(37)
|PN\/CCCMMIV
Σ i-2
(38)
< IIfllI + (10g(1/00)²
22
- A((N)
(39)
16

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
In equation 37 it depends the filter assumption in Assumption I In equation 38 we implement Weyl's law (Arendt et al. 2009) which indicates that eigenvalues of Laplace operator scales with the order X f2/d, The last inequality comes from the fact that -;=1"
T. The second term equation 34 can be bounded with the triangle inequality as
((A)) (PN (1, (U.
M
Σ
M
+
Σ
(40)
The first term in equation 40 can be bounded with inserting the eigenfunction convergence result in Proposition
2 as
Σ
h(x) (PPNS) -aw.://..-((.,......... (PNI,
M
i(xi))
[PNSIlloNN PNdill
(41)
(x---1) d-1 Cmave [1fllm + ( N
( (log(1/0) 3
(18((100) 8)
(42)
02
) max 0, CM.ve [1ffliu + i1.,.., .M
(43)
N
N),
(44)
Considering the filter assumption in Assumption T. the second term in equation 40 can be written as
M
((LnN)
(P (f, mi)ml PN
(45)
M (f, (1)m (1 (109/110) t
(46)
M
(log(1/8) 1
Σ (P
(1+ CL.vV) (PPF. DuN) (f, 0i)ml 1
(47)
N
x² (Px (1 (1((11(110)) 8) Aa(N)
(48)
The term [PNN, mi) can be decomposed by inserting term (P PN PN.)) as
(PNN.D.NN - (. < (PNS. (PNS.P + (Px xv)) - (f.di)ml
(49)
< (PNf.ou.N
+ (P.
(i)
(50)
< (PP//Ill PNOill |PWN,, (J,
(51)
< [Ifll.+ (10((1/0) #) C...divee +
Tog(1/8)
(52)
0,
17

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Then equation equation 47 can be bounded as
Σ i(A.N) O PNO: -x ((.D))MPNNs))
M
(1 + C..IVO) ((IrIla + (oNN
(188(1/61)
#) CM2deVe
()(()/))
(1+()0(/)))
(og((/0)
#) ))
+
(53)
0,
N
N
CMRVe
(IITIou+ (108(1/0)) $ +
π
log(1 (6))
max
(54)
N
The second term in equation
33
can be bounded with the eigenvalue difference bound Proposition
2 as
(IIFIIMt
(10g(1/5)
$
Σ
S
Σ
(55)
N
km 1+1
im M
(NNN))IfIM
(56)
t= M+1
$ (1 + CM.IVE)
Σ 1F
(57)
i=++
S < = Aa(M).
(58)
We note that the bound made up by terms (NN + A2(M, + Aa(N) + Aa(M). related to the bandwidth of manifold signal M and the number sampled points N. This makes the bound scale with the order
(og(1/5) C'yy
[N(LN)PNS
+ +CM-
(59)
N
Il C2 = CM C2 =C and C₁ = 1I.fll.. As N goes to infinity, for every 0, there with Ci = C,O L
6 exists some Mo. such that for all M Mo it holds that A4(M) 6/2. There also exists no, such that for all N no. holds that A₁ (N)) AM N) + ANN) < 6/2. We conclude that the summations converge N goes to infinity. We see M large enough to have M-1 v 8', which makes the eigengap OM also bounded by some constant. We combine the first two terms as
22
log(1/6)
PNN PN S + +
(60)
6
N
with C = CM. = Il and C2 CM. of 0z To bound the output difference of MNNs, we need to write in the form of features of the final layer
F
F
F
LN, PN Cp. fi)l
Σ
Σ
P
cq
X
PNJi
(61)
9=1
By inserting the definitions, we have
F Σ
P PN
PA
(
(NN)
P No
Σ
(62)
q=1
point-wise with x,.0 = ff as the input of the first layer. With normalized point- wise Lipschitz nonlinearity, we have
|| 2
PNIfII
<
Σ h P [ [NN)x
PN
Σ h (Cp))1
(63)
F
h
(L x 1 - PNN
(64)
18

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
The difference can be further decomposed
1b"" LN)x P (cp)
(L PNLL - PNN [IN)x h PN 5 h
(65)
LN hf
L P fi=
| (LN (LNN - Pf
(66)
The second term can be bounded with equation 59 and we denote the bound as AN for simplicity. The first term can be decomposed by Cauchy-Sehwartz inequality and non-amplifying of the filter functions as
F
F
PNJP &
ΣAN
AN
1 ll +
Σ
- PNNLL
(67)
To solve this recursion, we need to compute the bound for |x] ||. By normalized Lipschitz continuity of a and the fact that (0) 0, we can get
F Σ
|x|||
Σ h[
[L |x|=م||
F
|
(68)
9=1
q=1
g=1
Insert this conclusion back to solve the recursion, we can get
| - PN
S
S1F 11F-1AN11
(69)
Replace / with L we can obtain
@ LN, PN PH Lp. fi)1l LF
(70)
when the input graph signal is normalized. By replacing I we conclude the proof.
C. Local Lipschitz continuity of MNNs
We propose that the outputs of MNN defined in equation 6 are locally Lipschitz continuous within a certain area, which is stated explicitly as follows.
Proposition 3. (Local Lipschitz continuity of MNNs) Assume that the assumptions in Theorem I hold. Let MNN be layers with features in each layer, suppose the manifold filters are nonamplifying with [k(A] S and the nonlinearities normalized Lipschitz continuous, then there exists a constant C' such that
(H, -(()))()))),,,,,))))))))(()) f)()) < F''Cddist - y), for all x, B,
(71)
where (M) is a ball with radius over M with respect to the geodesic distance.
Proof. The output of MNN can be written explicitly as
hi (
F
F (CC - ( (En(CC))LL
(HH Cp. - Cp, Mp).
Σ
(72)
10=1
F <
F (C - Σ
hi (Cp)f (v)
SF max (((())) (((())
(73)
We have (z) = a (Σn hy 11 The process can be repeated recursively by expanding (2) and (2) and finally, we can have
fp.x)) &HH, f)(i s F² (C,) ... h (c,)
-n (74)
19

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
With X-bandlimited manifold signal, suppose y = (,,,)))...((..,,1 As (S, Φ,) for all i M. is also
bandlimited and possesses M spectral components. The gradient be bounded according (Shi & Xu 2010) combined with the non-amplifying property of the filter function as
Vglloo SC
Σ A.SA
[aa X
C
Σ X - MM A.SA
(75)
From Theorem 4.5 in (Evans 2018), g is locally Lipschitz continuous
[g(x) g(v)l - C"dist(æ y), with y, (MM,),
(76)
where (MM is closed ball with radius with C" depending on the geometry of M. Combining the above, we have the continuity of the output of MNN as
(H, Cp: ()) (H, Cp. f)(v) S
- 4), with 2, (,
(77)
which concludes the proof.
20

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
D. Proof of Theorem 1
Proof. To analyze the difference between the empirical risk and statistical risk, we introduce an intermediate term which the induced version of the sampled MNN output. We define IN the inducing operator based on the decomposition This intermediate term is written explicitly as
{Vi) defined in Section A
H Lp. IyPN (g
Σ 2 @H, flai)tee,, for all e M,
(78)
where z; E X are sampled points from the manifold.
Suppose H E arg minHen (H), we have
GA = sup (H) (M)
(79)
HEH
The difference between RG (H) and RM(H) can be decomposed as
(R)(H) RM (H)
x));: yyl)) S/L Lg. du(x))
(80)
N
E( c LN, / (p. du(xx)
N
#/1 l Lo, du(x) - ())2) dp(x)
(81)
8( (H, x))i yyl) S 8
<
du(x))
N
J,, l Cg,
du(x) S.
du(x)
(82)
We analyze the two terms in equation 32 separately, with the first term bounded based on the convergence of GNN to MNN and the second term bounded with the smoothness of manifold functions.
The first term in equation can be written as
N H,
x)). - / e (H Cp. du(x)
8( Pe
(83)
N
N
N
1
L. [.. Σ ( (0t)
(
H.
(84)
N
1
[L, (( ().))
(85)
N
Σ
[ Ly, x)); (H, Cp: (xx)
(86)
N
1
La H. Lv. - PH, C,r INx)]l1
(87)
N
x² _
log(1/6)
LF (CICr+
(88)
From equation 83 to equation 84
we use the definition of induced manifold signal defined in equation
78
We utilize the
Lipsehitz continuity assumption on loss function from equation 85 to equation 86 From equation 86 to equation 87
21

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
depends on the fact that a single-entry vector and that [y]: is the value sampled from target manifold function g evaluated on x;- Finally the bound depends the convergence of GNN on the sampled graph to the MNN stated in Proposition
The second term is decomposed as
1
dp(x) / (
(H,
du(x)
(89)
N
8 (g(),L,. du(z)
Σ
/ v/
dp(x))
(90)
18 (g(H,L,.)(()))g())) (H cp. f) (pz)) dp(x))
(91)
N
H Cp. (2) ( Cp. (z) du((r)
(92)
(H, - (()
-
(93)
V
From equation 89 to equation 90 it relies on the decomposition of the MNN output over (V.). From equation 91 equation 92 (HH, Cp. f). Proposition indicates that the MNN outputs Lipschitz continuous within certain range, which leads to
the Lipschitz continuity of loss function. From equation 92 to equation 93
the definition of
N
4 (H, fp: (HH Cp. (x:) dp(x)
log
S
FLCs
du(xx)
(94)
N
log N N
N Σ
Fa
du(x)
(95)
V.
loog N N
< C'Cs
(96)
when d. If 2, the bound would be
N
(log N)
Σ
@ ((x))))))))) DH, Cp. ()x) du(z)) < F4C,
(97)
N
Combining equation 88 and equation 96 (or equation 97p. we can conclude the proof.
22

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
E. Corollary of Theorem 1
Corollary 1. Suppose the GNN with filters satisfying Assumption 7 have L layers with features in each layer and the imput signal bandlimited (Definition()). Suppose graphs G with N1 nodes and G2 with N₂ nodes are sampled from the same underlying manifold M. Under Assumptions and it holds in probability at least ô that
N₁ E (H, x:)b
N2
1
Σ
e {( G (H, LN,, x2)1i, (y2]6) S
sup HER
N
N₂
VE(VN + (N2)
2N + N2) (ool//log)/))
log N1 1/
log N₂
LF
(CICL 02)
+ F'OOs
F'Oss
VN
621
N1
N2
(98)
with C₁, C2 and C3 depending on the geometry of M, Ct is the spectral continuity constant in Assumption
Proof. By importing the statistical risk over the manifold (H) in equation 14 the bound can derived with a triangle inequality as
Ni
N22 Σ
sup HEH
l (1 G. (H, Lx2, x2)l (v2le)
N
2
i=1
N;
N₂
sup HEи
8 f (H, LN
RM + RM(H)
G (H. (H, x2))i (y2li)
(99)
N1
N₂ 1=1
1=1
sup HEN
( (H, LN,, (H)
sup HEH
( P (H, LNg: x2)];; (Y2]i) RM
t=1
(100)
Inserting the result in Theorem D concludes the proof.
23

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
F. Proof of Theorem
Proof. We can write the difference as
Ra H)
RM
(H, LN xx)li, ) - (ee)eee) (M,, D(H, Cp.e Sa)dpu (a), yk
(101)
Based the property of absolute value inequality and the Lipschitz continuity assumption of loss function (Assumption we have
3
N
-e(SA.
a (H. LN. &
Xa)le.
@(H, Sp.ks fo (x)dp(((), yk
N
Mr
J
Pa LN,,, xx)]
(HH, Cp.ker fx)dpa((x)
(102)
MM
We insert an intermediate term (HH, Pp (I;) as the value evaluated on the sampled point v,, which leads to
N
Po LN,,, /
fa fa)duu(z)
(103)
ME
N
D (H,
Φ fx) +
N
1=1
1
& Cp.k fz)
&HH Cp, fx)d
(104)
M
The first term in equation 104
can be bounded similarly as equation
87 which is explicitly written as
N
1 N Σ
1
LN,,,
(H, Cp.ks fx)ks
(105)
N
PG (H. LN.
PN 1 H. Lp. f1)ll1
(106)
@ (N, PN P (H, Lp, f2
(107)
VN
x² (CICr.
log(1/o)
(108)
VN
N
The second term is
(H. fo), L/L
Me
((H, Cp.ks fx)dpa(z)
(109)
N (HH, Ce.e (d)ss)
Σ
/ @(H. Lp.ks (z)
(110)
N
( Sx)xa) &H, (p),)))))) (x)(())
(111)
llog N
- FLCs
(112)
N
This depends the Lipschitz continuity of the output manifold function in Proposition
24

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
G. Further references
Graphon theory Different from the manifold model we are using, some research constructs graphs derived from graphons, which can be viewed as a random limit graph model. This research has focused on their convergence, stability, as well as transferability (Ruiz et al. 2020; Maskey et al., 2023 Keriven et al. (020). In (Parada-Mayorga et al., 2023), a graphon is used as pooling tool in GNNs. Despite its utility, the graphon presents several limitations compared to the manifold model we use. Firstly, the graphon model assumes an infinite degree at every node (Lovász) 2012), which is not the case in the manifold model. Additionally, graphons offer limited insight into the underlying model; visualizing a graphon is challenging, except in the stochastic block model case. Manifolds, however, are more interpretable, especially when based on familiar shapes like spheres and 3D models (see Figures ?? and ??). Finally, the manifold model supports a wider range of characterizable models, making a more realistic choice.
Transferability of GNNs The transferability of GNNs has been extensively studied by examining the differences in GNN outputs across graphs of varying sizes as they converge to a limit model. This analysis, however, often lacks statistical generalization. Several studies have explored GNN transferability with graphon models, proving bounds on the differences in GNN outputs (Ruiz et al. 2023 2020 Maskey et al. 2023 Other research has demonstrated how increasing graph size during GNN training can improve generalization to large-scale graphs (Cervino et al., 2023). The transferability of GNNs has also been investigated in the context of graphs generated from general topological spaces (Levie et al. 202 and manifolds (Wang et al., (2024a). Furthermore, novel graphop operator has been proposed
limit model for both dense and sparse graphs, with proven transferability results (Le & Jegelkal 2024). Further research has focused on transfer
learning for GNNs by measuring distances between graphs without assuming a limit model (Lee et al.. 2017 Zhu et al.
2021 Finally, a transferable graph transformer has been proposed and empirically validated (He et al. 2023
H. Filter Assumption
In the main results, we assume that the filters in GNN and MNN satisfy Assumption [ This may lead limited discriminability in high-frequency spectrum. While this is reasonable assumption, high-frequency signals on graphs or manifolds can fluctuate significantly between adjacent entries, leading to instability and learning challenges. We expect a degree of local homogeneity, which translates to low-frequency signals. This assumption is supported by empirical evidence in various domains, including opinion dynamics, econometrics, and graph signal processing (Degroot 1974 Billio et al., 2012, Ramakrishna et al. 2020). Moreover, several other effective learning techniques, such as Principal Component Analysis (PCA) and Isomap, implicitly employ low-pass filtering. Therefore, we believe that the filter assumption is not restrictive and is well-supported by both practical applications and theoretical considerations.
I. Manifold Assumption
In this paper, we considered the case in which graphs are sampled from manifolds. This is an assumption that has been widely used in practice. From dynamical systems (Talmon et al. 2015) to images (Peyré 2009 Osher et al. 2017), assuming an underlying low dimensional manifold is a common practice. Real-world graphs, like the ones considered in the node prediction experiments, can be assumed to be sampled from d-dimensional manifolds. To support this argument, in Figure 5] we plot the 100 largest eigenvalues of the Laplacian matrix associated with each graph. By doing this, we show fast decay in the values of the cigenvalues progress. This decay shows that the information is mostly supported on a subset of the eigenvalues thus reinforcing the idea that it comes from low dimensional manifold.
J. Experiment details and further experiments
We consider the following datasets: OGBN-Arxiv (Wang et al. 2020 Mikolov et al.)
2013).
Cora (Yang et al., 6b).
CiteSeer (Yang et al., (0166)), PubMed Yang et al. 2016b), Coauthors CS (Shchur al.
2018
Coauthors Physics (Shchur
et al. 2018), Amazon-rating (Platonov et al. 2023). and Roman-Empire (Platonov et al. found in [
2023
details of the datasets can be
All experiments were done using a NVIDIA GeForce RTX 3090, and each set of experiments took at most 10 hours to complete. In total, we run 10 datasets, which amounts for around 100 hours of GPU use. All datasets used in this paper are public, and free to use. They can be downloaded using the pytorch package (https: httppytoocc--geeneeee readthedocs. http//e/aatttt/odiieie dataassseeeeasasssssss.sss html), the ogh package ftttps://ogb.ataffor stanford
25

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
(a) Amazon
(b) CiteSeer
(c) CS
(d) Physics
(c) Cora
(f) OBGN-Arxiv
(g)
PudMed
(h) Roman
Figure 5: Top 100 eigenvalues of the graph for each dataset considered in the node classification problem.
and the Princeton ModelNet project (https://modde net.. cs www.prinncteo ....prrrneett..eee............ In total, the datasets occupy around 5 gb. However, they do not need to be all stored at the same time, as the experiments that we run can be done series.
edu/ /wwp///cod/dddoeeee
J.1. ModelNet10 and ModelNet40 graph classification tasks
ModelNet10 dataset (Wu et al. 2015) includes 3,991 meshed CAD models from 10 categories for training and 908 models for testing as Figure shows. NetelNet40 dataset includes 38,400 training and 9,600 testing models as Figure shows.. In each model, points are uniformly randomly selected to construct graphs to approximate underlying model, such as chairs, tables.
Figure 6: Point cloud models in ModelNet10 with N 300 sampled points in each model, corresponding bathtub, chair, desk, table, toiler, and bed.
Figure 7: Point cloud models from ModelNet40 with N 300 sampled points in each model, corresponding to airplane, person, car, guitar, plant, and bottle.
The weight function of the constructed graph is determined as equation 7 with e 0.1. We calculate the Laplacian matrix for each graph as the input graph shift operator. In this experiment, we implement GNNs with different numbers of layers
26

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
1.0
32 units, layers
32 units, layers
Diferences of Average Graph Outputs
0.8
64 hidden units, 3 layers
Differences of Average Graph Outputs
64 hioden units, layers
128 hidden units. 3 layers
128 hidden units. layers
0.7
hidden units, layers
0.8
256 hidden units layers
0.6
0.6
0.4
0.2
0.2
0.1
10
20
30
40
50
70
80
10
20
30
40
50
60
70
Number
Number Nodes
(a) Differenees the outputs of 3-layer GNNs.
(b) Differences of the outputs 4-layer GNNs.
Figure 8: Graph outputs differences of GNNs with different architectures ModelNet40 dataset.
and hidden units with K filters in each layer. All the GNN architectures are trained by minimizing the cross-entropy loss. We implement an ADAM optimizer with the learning rate set as 0.005 along with the forgetting factors 0.9 and 0.999, We carry out the training for 40 epochs with the size of batches set as 10. We run 5 random dataset partitions and show the average performances and the standard deviation across these partitions.
J.2. Node classification training details and datasets
In this section, we present the results for node classification. In this paragraph we present the common details for all datasets, we will next delve into each specific detail inside the dataset subsection that follows.
Number of Classes
Name
Nodes
Edges
Features
Reference
Arxiv
169, 343
1, 166, 243
128
40
(Wang et al.
2020
Mikolov et al.
2013)
Cora
2, 708
10, 556
1, 1,433
7
Yang et al.
2016b)
CiteSeer
3, 327
9, 104
3, 703
6
Yang al.
2016b
PubMed
19, 717
88, 648
500
3
Yang al.
2016b)
Coauthor Physics
18, 333
163, 788
8,505
15
Shchhr et al.
2018)
Coauthor CS
34, 493
495, 924
8, 415
5
Shchur al. 2018)
Amazon-ratings
24, 492
93, 050
300
5
Platonov et al.
2023)
Roman-empire
22, 662
32, 927
300
18
Platonov et al.
2023)
Table 1: Details of the datasets considered in the experiments.
In all datasets, we used the graph convolutional layer GCN, and trained for 1000 epochs. For the optimizer, we used Adamk, with using a learning rate of 0.01, and 0 weight decay. We trained using the graph convolutional layer, with a varying number of layers and hidden units. For dropout, we used 0.5. We trained using the cross-entropy loss. all cases, we trained 2 and 3 layered GNNs.
To compute the linear approximation in the plots, used the mean squared error estimator of the form
y log (n) p.
(113)
Where is the slope, p is the point, and is the vector with the nodes in the training set for each experiment. Note that we repeated each experiment for 10 independent runs. In all experiments, we compute the value of and p that minimize the mean square етror over the mean of the experiment runs, and we compute the Pearson correlation index over those values.
Our experiment shows that our bound shows the same rate dependency as the experiments. That is to say, in the logarithmic scale, the generalization gap of GNNs linear with respect to the logarithm of the number of nodes. In most cases, the
27

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Pearson correlation index is above 0.9 in absolute value, which indicates strong linear relationship. We noticed that the linear relationship changes the slope in the overfitting regime, and in the non-overfitiing regime. That is say, when the GNN is overfitting the training set, the generalization gap decreases at much slower rate than it does with the GNN does not have the capacity to do so. Therefore, in the case in which the GNN overfits the training set for all nodes when computed 8 using all the samples in the experiment. On the other hand, when the number of nodes large enough that the GNN cannot overfit the training set, then we computed the and with the nodes in the non overfitting regime.
J.3. Spectral Continuity Constant Regularizer
We add a regularization term to the loss to better control the value of the spectral continuity constant (defined in Assumption while training. To do so, given a convolutional filter E RK its associated spectral continuity constant is
K-1
R(h) = Σ
k: l/ k--1
(114)
k=
Where Amaz is the largest eigenvalue of the graph G.
J. 1. ARXIV DATASET
For this datasets, trained 2, 3, 4 layered GNN. We also used learning rate scheduler ReduceLRROnP lateau with mode min, factor 0.5, patience 100 and minimum learning rate of 0.001.
100
100
Actroxy 261
80
Acorric 2611
89
3-2
Tran
52-
last
Tant
Trch
Tais
Tran
42-
40
valring
Humber
2.00
Roareey dftirencc
Acquney diteerre
14550
120 Svurrt
3.00
hodper
hoden
734 hitters ort.
512 saleen
172 www.............
16F
(a) Two Layers
(b) Three Layers
(c) Four Layers
Figure 9: Generalization gap for the OGBN-Arxiv dataset on the accuracy as function of the number of nodes in the
training set.
J.3.2. CORA DATASET
For
we used corch_geametric.om Planetood (root=" //data" name= mora"" )
the
Cora
dataset,
the standard one, which can be obtained running
Cora')
28

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Tot
1.75
125
1.25
Tran Baa
Teh-100
2.00
Ter
1.0
1.0
0.75
0.59
0.59
0.59
0.00
10a
109
10
10a
10"
LU7
Number nodes in traiting
Number rodes craining
traking
10
160
Loak difi 00100
10"
20"
54 Eden
728 tiliis wett
228 hocee
255 vddan unta Inarrt
258 hocket unti thsert
hocen
10
10-4
107
162
10
Number of motee traiting
Number nodee criining
(a) Two Layers
(b) Three Layers
(c) Four Layers
Figure 10: Generalization gap for the OGBN-arxiv dataset the loss (cross-entropy) as function of the number of nodes in the training set.
Value OF
Valuee
1910 Hidden Un Size
3127 Year
1010
Hidden Units Size
Hidden Units Size
Hidden Units Size
layers
3 layers
4layers
(a) Accuracy
(b) Loss
Figure 11: Values of slope (a) and point (b) corresponding to the linear fit (a log(N) b) of Figures 10 and
29

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Pearson
Type
Lay.
Feat.
Slope
Point
Correlation
Coefficient
Accuracy
64
6.301e
01
3.621e 00
-..800 01
Accuracy
128
6.034e
01
3.663e + 00
9.985e 01
Accuracy
256
5.347e
01
3.493e
00
9.952e 01
Accuracy
512
5.328e
01
3.605e
00
9.975e 01
Accuracy
64
6.27le
01
3.600e
00
9.987e 01
Accuracy
128
5.730e
01
3.567e
00
9.970e 01
Accuracy
256
4.986e
01
3.393e
00
9.910e 01
Accuracy
512
4.529e
01
3.315e
00
9.934e 01
Accuracy
64
5.343e
01
3.236e
00
9.971e 01
Accuracy
128
5.096c
01
3.299c 00
9.987e 01
Accuracy
256
4.827e
01
3.337e
00
9.920e 01
Accuracy
512
4.264e
01
3.229c
00
9.927e
01
Loss
2
64
6.853e
01
2.265e
00
9.975c 01
Loss
128
6.562e
01
2.311e
00
9.988e
01
Loss
2
256
5.907e
01
2.174c
00
9.968c
01
Loss
2
512
5.848c
01
2.280e
00
9.989e
01
Loss
3
64
6.739e
01
2.228e
00
9..80e
T1
Loss
128
6.229c
01
2.224c
00
-9.966
01
Loss
3
256
5,581e
01
2.11le 00
-9.942e
01
Loss
512
- 5.14le
01
2.057e
00
-9.955e 01
Loss
64
6.039e
01
1.964e 00
-9.980 01
Loss
4
128
5.701e
01
2.014e 00
-9.99e 01
Loss
4
256
5.379e
01
2.051e 00
-9.55ee
01
Loss
4
512
4.810e
01
1.957e 00
-9.37e
01
Table 2: Details of the linear approximation of the Arxiv Dataset. Note that in this case, used only the values of the generalization gap whose training error is below 95%.
Pearson
Type
Lay.
Feat.
Slope
Point
Correlation
Coefficient
Accuracy
2.839e 01
2.022e + 00
-9.03e
Accuracy
32
2.917e
01
2.014e + 00
-9.90e 01
Accuracy
3.006e 01
2.021e + 00
-9.866
Accuracy
2.6566
01
1.996e + 00
-9.99e
Accuracy
2.637e
01
2.008e + 00
99.77e
Accuracy
64
2.581e
01
1.981e + 00
99.870
Loss
3.631e
01
9. 9.406e 01
99.250
Loss
4.228e
01
9.638e 01
99.657
Loss
4.991e 01
1.067e + 00
99.776
Loss
4.13le 01
1.276e + 00
99.73e
Loss
4.605e
01
1.385e + 00
99.73e
Loss
4.589e
01
1.455e + 00
99.76e
Table 3: Details of the linear approximation of the Cora Dataset. Note that in this case we used all the values given that the training accuracy 100% for all nodes.
30

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
24
36
10
37
(a) Generalization Gap.
(b) Layers
(c) Layers
Figure 12: Generalization gap, testing, and training losses with respect to the number of nodes in the Cora dataset. The top row is in accuracy, and the bottom row is the cross-entropy loss.
J.3.3. CITESEER DATASET
For the CiteSeer dataset, corch_geemeete datasets. www.ssetsslaaaetttiiioooo Planetoid (root=". /datta name= Citeserr)"
we used the standard one, which can
obtained
running
6:30
44-
22-
Sumber
Mumber
(a) Generalization Gap
(b) Layers
(c) Layers
Figure 13: Generalization gap. testing, and training losses with respect to the number of nodes in the CiteSeer dataset. The top row is in accuracy, and the bottom row is the cross-entropy loss.
31

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Pearson
Type
Lay.
Feat.
Slope
Point
Correlation
Coefficient
Accuracy
16
1.699e
01
1.972e 00
-9.518e 01
Accuracy
1.856e
01
1.978e + 00
-9.714e 01
Accuracy
64
1.749e
01
1.966e
00
-9.534 01
Accuracy
16
1.585e
01
1.956e
00
9.722e 01
Accuracy
32
1.659e
01
1.963e
00
99.72e 01
Accuracy
64
1. 1.658e
01
1.967e 00
99.70e
01
Loss
16
1.049e
01
7.757e 01
5.924e
01
Loss
32
1.762e
01
7.646e 01
-7.981e
01
Loss
64
2.186e
01
8.384e 01
99.120e 01
Loss
16
1.802e
01
1.169c 00
8.345e 01
Loss
32
1. 1.629e
01
1.200e 00
8.767e
01
Loss
64
5.917e
02
1.283e 00
2.562e 01
Table Details of the linear approximation of the CiteSeer Dataset. Note that in this case we used all the values given that the training accuracy is 100% for all nodes.
J.3.4. PUBMED DATASET
For the PubMed dataset, torch_gecmet ritetricc
we used the standard one, which
can be
obtained
running
(root=". /data name= PubMed') )
03
0.-
Exp
1xppl
32
10
10-
(a) Generalization Gap
(b) 2 Layers
(c) 3 Layers
Figure 14: Generalization gap, testing, and training losses with respect to the number of nodes in the PubMed dataset. The top row is in accuracy, and the bottom row is the cross-entropy loss.
J.3.5. COAUTHORS CS DATASET
obtained running this case, given that there are no training and testing sets, we randomly partitioned the datasets and used 90% of the samples for training and the
For the CS dataset, we used the standard one, which can datasets. Coauthor (root=". /data", name= CS')) ). torch heccc__eemeerriieee witattric.daasstsss
CS').
32

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Pearson
Type
Lay.
Feat.
Slope
Point
Correlation Coefficient
Accuracy
2
16
2.523e
01
1.834e + 00
-9.942 01
Accuracy
32
2..33e
01
1.812e + 00
-9.583 01
Accuracy
2
64
-2.764
01
1.869e + 00
-9766e 01
Accuracy
16
-2.748e
01
1.844e 00
9.910e 01
Accuracy
32
-2.66le
01
1.86le + 00
9.771e 01
Accuracy
64
-2.58e
01
1.827e
00
9..90e
01
Loss
2
16
4.166c
01
7.695e
01
9.718e
01
Loss
32
4.733e
01
7.852e 01
-9.137 01
Loss
2
64
4.368e
01
7.547e 01
99.718e 01
Loss 3
16
4.424c
01
1.067e
00
9.549e 01
Loss
32
5.518e
01
1.223e + 00
99655e
01
Loss
64
5.246c
01
1.169c 00
99.32e
01
Table Details of the linear approximation of the PubMed Dataset. Note that in this case we used all the values given that the training accuracy is 100% for all nodes.
remaining 10% for testing.
Hilpe
100
100
loves
Prices
holice wits layers
Accunnyy
Artumnry
80
list loo. aa rilce tiyers
lndt los la rocce units, a ligers Fidcer
Them lens
12" Number of modes maaiing S4t
12F
122
12
12" Yumber of nodes in turiing sot
122
Ap"
Nurrber of nodes in Mariing
Yein ticce
25
Yeir rilden
"hat toleen lavers
That rilken layers
20'
224 daln
list loos 64 riice layers
bist readen layers
diffrrence
ficeen wnts lovers
12
10
122 Mumber of modes in nuriing
122
12
202
322
201
Number of nodes traning sot
Number of rodes training
(a) Generalization Gap
(b) Layers
Layers
Figure 15: Generalization gap, testing, and training losses with respect to the number of nodes in the CS dataset. The top row is in accuracy, and the bottom row is the cross-entrope loss.
J.3.6. COAUTHORS PHYSICS DATASET
For the Physics dataset, we used the standard one, which can be obtained running torch aarch_gecmeericce datasets Coauthor (root=". /data", name= Physichssss In this case, given that there are no training and testing sets, we randomly partitioned the datasets and used 90% of the samples for training and the remaining 10% for testing.
33

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
hidden layers
hidden layyers
4x
32 hidden units,
tayers linear fit hidden layers
loyers linear ftt hidden layers
hidden units,
10
3x
64 hidden units,
toyers linear fit
64 hidden units,
loyers linear fit layers
Accuracy difference (%))
units.
layers
hidden
32 h hidden units,
toyers linear
52 hidden units,
loyers linear fit hidden layers
Loss difference
hidden units. layers
64 hidden units,
loyens linear fit
64 hidden units, layers linear fit
10a
10
102
10*
Number of nodes in training set
Number of nodes in training set
Linear fit for accuracy generalization gap
(b) Linear fit for loss generalization gap
Figure 16: Generalization gaps function of the number of nodes in the training set in the CS dataset.
Pearson
Type
Lay.
Feat.
Slope
Point
Correlation Coefficient
Accuracy
2.138e
01
1.659e + 00
9.007e 01
Accuracy
64
2,250e
01
1.685e + 00
8.969e
Accuracy
32
1.9779
01
1.695e + 00
9.000e
01
Accuracy
-1862e
01
1.646e + 00
8.980e
Loss
-2.23e
01
6.273e 01
88.44e 01
Loss
64
-2.33e
01
7.762e 01
-7.925
01
Loss
3.558e
01
1.207e + 00
8.924e
01
Loss
64
3..66e
01
1.256e + 00
-.568e
Table Details of the linear approximation of the CS Dataset. Note that in this case we used all the values given that the training accuracy 100% for all nodes.
Pearson Correlation
Type
Lay.
Feat.
Slope
Point
Coefficient
Accuracy
32
1.524e
01
1.235c + 00
9.0644 01
Accuracy
64
11.778
01
1.218e + 00
-9.15e 01
Accuracy
32
11227e
01
1.190e + 00
-9.328e
01
Accuracy
64
11.268e
01
1.200e + 00
-8.826c
01
Loss
32
-1.1le
01
-5.257e
02
-7.99l 01
Loss
64
9.684e
02
-7.335e
02
-7,996e
01
Loss
32
11.10e
01
2.875e
01
-8.280c
01
Loss
64
-1.668e
01
2.388e
01
-7.779e
01
Table 7: Details of the linear approximation of the Physics Dataset. Note that in this case we used all the values given that the training accuracy is 100% for all nodes.
J.3.7. HETEROPHILOUS AMAZON RATINGS DATASET
For the Amazon dataset, torch_geemetric deweeetrrccddteeetee.. Hwwerophi htsarssteteeterooosssssppppaaeee (root=". (root="./data", name= Ama Amazon') )
we used the standard one, which
can
obtained running
datasets.
34

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
24 rikce ardi layes raaces
100
2x301
Lan lusee ligers
57.
relor anti. Layer
25.0
201
hotcen unto
Actursyy
62.5
07.5
hotenunts, so tiyns
307
lnis takee laymn
calie layee
talao layer
157
Number nodea busiigg
Number Bubringa
Number nedea Dusiing
Kar bos, tasm loyes liver
koa las, raken ants, layes loyer
3.50
724
ynd layer
bnd tayen
1.3
107
10a
10
127
207
Number of nodes traming
Number traniig set
Number trasiing
(a) Generalization Gap
(b) Layers
(c) Layers
Figure 17: Generalization gap, testing, and training losses with respect to the number of nodes in the Physics dataset. The top row is in accuracy, and the bottom row is the cross-entropy loss.
Nodeen
hilden
Notenn layertineer
Niddin
Nidden
10l
109
Accurary differanca
liddinn
10-1
6 10
40
10
3 10-1
10a
103
10
Number of nodes in training set
Number of nodes training set
(a) Linear fit for accuracy generalization gap
(b) Linear fit for loss generalization gap
Figure 18: Generalization Gaps as a function of the number of nodes in the training set in the Physies dataset.
In this case, used the 10 different splits that the dataset has assigned.
J.3.8. HETEROPHILOUS ROMAN EMPIRE DATASET
For the Roman dataset, we used the standard one, which can be obtained running sarch_geometric datasets, this case, we used the 10 different splits that the dataset has assigned.
(root=". "rcoot".//daa""" "//att", name- Roman' ) In
35

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
100
100
70
Teln lavey bis hoder unts,
Höder kaye
20
30
12"
30"
12
10a
127
10'
121
301
10" Number nodes ring
12t
Number aodes
nodes trariin
-4- This los 22 Hodee anta layaa
12-
Tae 64 hidce 2agar taken
diferrnce
Tear hidder kaye
18 lpaee Habdn
2
lagars
10?
10"
10
10
122
10"
10
10
10"
12'
Number of nodes traningstt set
Mumber burinngs
Numbut Buaiinggg
(a) Generalization Gap
(b) Layers
(c) Layers
Figure 19: Generalization gap, testing, and training losses with respect to the number of nodes in the Amazon dataset, The top row is in accuracy, and the bottom row is the cross-entropy loss.
32 units, layers
hidden units. layers
32 hidden units.
layers linear ft
32 hidden units. layers linear ftt
hidden units, layers
10a
hidden units. layers
64 hidden units. layers linear ft
64 hidden units. layers linear ft
Accuracy difference (%)
10a
32 hidden units, layers
hidden units, layers
32 hidden units. layers linear ft
hidden units, layers
Loss difference
10a
32 hidden units, layers linear Rt
hidden units, layers
64 hidden units,
layers linear ft
64 hidden units.
layers linear Rt
10a
10a
10a
10a
103
10a
10a
104
Number nodes training
Number of nodes in training set
(a) Linear fit for accuracy generalization gap
(b) Linear for loss generalization gap
Figure 20: Generalization Gaps function of the number of nodes in the training set in the Amazon dataset.
36

---

Hilln A Manifold Perspective the Statistical Generalization of Graph Neural Networks
Pearson Correlation Coefficient
Type
Lay.
Feat.
Slope
Point
Accuracy
7.693e
01
4.236e + 00
99.914 01
Accuracy
64
7.788e
01
4.404e + 00
99.722 01
Accuracy
32
-7.268e
01
4.101e + 00
-9.868e
01
Accuracy
64
-7.35de
01
4.257e + 00
-9.921e 01
Loss
-.0866 + 00
3.971e + 00
-9.968e 01
Loss
64
1.096e + 00
4.189e + 00
-9.985e 01
Loss
32
1.134e + 00
4.339e + 00
-9.965e
01
Loss
64
1.154e + 00
4.629e + 00
9.991e
01
Table 8: Details of the linear approximation of the Amazon Dataset. Note that in this case we used only the values of the generalization gap whose training error is below 95%.
102
ACCuRCY dffrrece
03-
82-
-8. Tain less 33 hicee unts leyers
-8. Tep las 33 Hoce irt, Toves
Yer lods kit tivie layes
Ive los i4 rerakm ants Alges
heaan Jnta. kyas
-4- That Hleee loyers
-4- Hdden layer
128 biker untt layes
retmo leym
20
22
20 Number of todes traiting sit
124
12
127
12
104
10
10' Tamber of rodes intiiiingg on
207
304
Number of rodec in training set
Tex lris, raker untt, laye
14
Toy liis haker only layes
Tex lrss bidee leye
12
Loss difarrncc
128 hader unlts
Neten leym
107
10a
707
102
107
30
10P
307
305
Number of nodes in training set
Mumber of nodee intreining
Number of rodee intriiiing oet
(a) Generalization Gap
(b) 2 Layers
(c) 3 Layers
Pearson Correlation Coefficient
Type
Lay.
Feat.
Slope
Point
Accuracy
2
32
8.408e
01
4.644e + 00
-9.963e 01
Accuracy
2
64
7.435e
01
4.477e 00
-
-1.00e + 00
Accuracy
3
32
9.476c
01
5.049e + 00
-9.956e
01
Accuracy
3
64
99.155
01
5.182e + 00
-1.000e + 00
Loss
2
32
1.006e + 00
3.829c + 00
-9.992e
01
Loss
2
64
9.656c
01
3.915e + 00
-1.000e + 00
Loss
3
32
1.244e + 00
4.764e + 00
-9.994e 01
Loss
3
64
1.225c + 00
5.011e + 00
- -1.000e + 00
Table 9: Details of the linear approximation of the Roman Dataset. Note that in this case we used only the values of the
generalization gap whose training error is below 95%
37

---

A Manifold Perspective the Statistical Generalization of Graph Neural Networks
layers
layers
32 hidden units loyers linear ftt
32 hidden units, layers linear ftt
layers
layers
64 hidden units
layers linear
10a
64 hidden units, layers linear ftt
Accuracy difference (%)
hidden layers
32 hilden units
layers linear fit
Loss difference
32 hidden units, layers linear ftt layers
layers
10²
64 hidden units, layers linear ftt
10a
64 hidden units, 3 layers linear ftt
10a
10a
10a
Number of nodes in training set
Number nodes training set
Linear fit for accuracy generalization gap
(b) Linear fit for loss generalization gap
Figure 22: Generalization Gaps function of the number of nodes in the training set in the Roman dataset.
38


Reviews:
[{"review_id": "leYfZFgPEF", "reviewer": "Reviewer_r3TG", "summary": "This paper examines the generalizability of Graph Neural Networks (GNNs) from a manifold perspective. Leveraging spectral analysis, the authors introduce a novel generalization bound for GNNs, demonstrating that when trained on graphs sampled from a manifold, the generalization error decreases logarithmically with the number of graph nodes and is proportional to the spectral continuity constant of the graph filter. Experimental results on multiple real-world datasets (e.g., ArXiv, Citeseer) validate the theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> **Does non-uniform sampling matter?** \n\nThe 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:\n\n$$ 0<\\rho_{min} \\leq \\rho(x) \\leq \\rho_{max}<\\infty \\quad \\forall x \\in \\mathcal{M}$$ \n\n\n\n>**What concrete suggestions can be made to impose restrictions on the continuity of filter functions?**\n\nThe 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.\n\n>**Why does accuracy decrease with more nodes (Figure 5(a))?**\n\nThe 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. \n\n>**Are the proposed bounds or the manifold perspective applicable to various types of GNNs?**\n\nYes, 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\n\n>**Additionally, the font embedded in the figure is too small and should be adjusted for better readability.**\n\nThank you for the suggestions and other comments to help us improve the paper. We will update these.\n\n>**Figure 2 may be incorrect, as the Gaussian kernel graph should be fully connected, but the figure does not reflect this.**\n\nThank you. We will update the Figure accordingly.", "claims_and_evidence": "Most of the claims are supported by proof or numerical evidence.", "methods_and_evaluation_criteria": "The authors considered 10 different datasets and two common metrics for numerical evaluation, making the results generally convincing.", "theoretical_claims": "Overall, the authors provide comprehensive proofs, and to my knowledge, there are no significant flaws.\n\nHowever, it seems that the authors assume that the graph is uniformly sampled from the underlying manifold, which is a strong assumption. It is unclear how deviations from uniform sampling would impact the conclusions. Some discussion may be needed. \n\nAdditionally, the authors may need to be more explicitly discussed whether the generalization bounds of all GNNs align with the manifold assumption.", "experimental_designs_or_analyses": "Overall, the experimental designs seem sound to me.", "relation_to_broader_scientific_literature": "The authors provide a comprehensive discussion and comparison with existing literature, highlighting that while traditional generalization bounds grow with graph size or node degree, the proposed bound decreases with the number of nodes, driven by the spectral properties of filter functions over the manifold. Additionally, they demonstrate that a GNN trained on a single graph from each manifold can generalize to unseen graphs from the same manifold set.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I find the paper is a little bit difficult to follow, as many definitions and mathematical symbols require multiple steps to trace. For example, the chain of C1 spans Theorem 1 → Appendix D → Proposition 1. Additionally, the definition of the generalization gap (as well as discriminability) does not appear until page 5, despite being referenced multiple times earlier without citation. The authors should consider reminding readers where key definitions can be found.\n\nThe authors mention the trade-off between generalizability and discriminability, suggesting that restrictions should be imposed on the continuity of the filter functions. However, it is unclear how this restriction should be implemented—whether it should be based on dataset characteristics, selected model architectures, or other factors. Further clarification on this would be helpful.", "other_comments_or_suggestions": "Figure 2 may be incorrect, as the Gaussian kernel graph should be fully connected, but the figure does not reflect this. \n\nAdditionally, the font embedded in the figure is too small and should be adjusted for better readability.\n\nOne point I missed regarding Figure 5(a) is why the accuracy decreases as the number of nodes in the training set increases. Further explanation of this trend would be useful.", "questions_for_authors": "Please address the following points of confusion:\n\n(1) Does non-uniform sampling matter?\n\n(2) What concrete suggestions can be made to impose restrictions on the continuity of filter functions?\n\n(3) Why does accuracy decrease with more nodes (Figure 5(a))?\n\n(4) Are the proposed bounds or the manifold perspective applicable to various types of GNNs?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LGNFfH8X3K", "reviewer": "Reviewer_3hav", "summary": "This paper provides a new perspective the analyze the generalisation of GNN from manifold and manifold neural networks. By considering a graph as samples from a manifold, this paper shows that the generalisation ability of GNNs decrease with number of nodes and increases with the spectral contiuity constant (an indicator of model complexity).", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**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.**\n\nThe 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.\n\n>**The spectral contiuity term can be impractical to compute. why do you use a regulariser to indicate spectral contiuity. It seems very indirect.**\n\nThe reviewer is right that calculating the spectral continuity constant might be computationally expensive. However, approximations to it might allow an efficient implementation. \nThis are for example: \n[1] Stability properties of graph neural networks\nF Gama, J Bruna, A Ribeiro\nIEEE Transactions on Signal Processing 68, 5680-5695\n[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\n\n>**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).**\n\nWe will add these latest references for discussion in our updated version. We thank the reviewers for the suggestions.\nWe 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. \n\nIn 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.\n\n\n>**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.**\n\nThe 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. \nWe 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.", "claims_and_evidence": "The claims are mostly supported. \nHowever, I find the claim about GNN discriminability somewhat hand-wavy. The authors claim this based on spectral contiuity which is a indicator for spectral filter complexity. But complexity and discriminability are not equal, e.g. a model can perfectly discriminate all data points but have low complexity such as linear classifier, and a model can have high complexity but still cannot discriminate data points. To properly claim this, I feel the authors should define discriminability first to make the claim rigorous.\n\nAlso, I noted the definition of generalisation gap (eq 15) is slightly different to other literature.", "methods_and_evaluation_criteria": "Yes. The methods are evaluated on both synthetic and real-world datasets.", "theoretical_claims": "The theoretical claims seems correct. However, I am not able to follow some proofs so I could be missing things.\nFor example, I cannot find definition of $C_1$, $C_2$ and $C_3$. I checked the appendix but can only find $C_1$ and $C_2$ depend on $C_{\\mathcal{M},1}$ and $C_{\\mathcal{M},2}$, but could not find what $C_{\\mathcal{M},1}$ and $C_{\\mathcal{M},2}$ are.", "experimental_designs_or_analyses": "Using a regulariser to indicate spectral contiuity feels indirect and there are many uncontrolled factors, e.g. whether the regulariser works or not depends on many factors such as training settings and the weight coefficient.", "relation_to_broader_scientific_literature": "My main concern is the novelty of this paper. While analysing generalisation from manifold neural network is novel, the landed results are not so. In particular, the conclusion that generalisation decreases with spectral contiuity (model complexity) is well-known traditional wisdom in statistically 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. \nAlso, the results regarding size of graph is known from (Maskey et al., 2022; 2024; Levie, 2024).\n\n[1] Weisfeiler–Leman at the margin: When more expressivity matters. ICML 2024\n[2] Towards bridging generalization and expressivity of graph neural networks . ICLR 2025", "essential_references_not_discussed": "[1][2][3] should be discussed. The two papaers are very recent so it is understandable that the authors may have missed them by the time of submission.\n\n[3] Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs. ICLR 2025", "other_strengths_and_weaknesses": "Strengths:\n* The analysis works for both graph and node level tasks.\n* Manifold perspective is interesting.\n\nOther weaknesses:\n* As  $C_1$, $C_2$ and $C_3$ depends 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.\n* The introduction of convolution and spectral filters is a bit convoluted and can be simplified.\n* The spectral contiuity term can be impractical to compute.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "* can you please briefly describe  $C_1$, $C_2$ and $C_3$ and their implication?\n* why do you use a regulariser to indicate spectral contiuity. It seems very indirect.\n*", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OZRVcA60n2", "reviewer": "Reviewer_EGQX", "summary": "This paper considers GNNs where on graphs which arise from subsampling a manifold (with non-uniform density), building off of a number of recent works which have analyzed the convergence of such networks.\n\nHowever, this paper adds an exciting new dimension to this line of works by incorporating ideas from statistical learning theory to analyze the generalization gap. As a practical take away, Corollary 1 provides transfer learning guarantees between two graphs G_1 and G_2 sampled from the same manifold.\n\nCurrently, there is a significant number of minor errors in the proof. I believe that all of them are easily fixable, but some require minor modifications to the results. (Notably, I think that the statement of the theorem might not apply when $d=1$ and may need minor changes in the case $d=3). These are detailed below.\n\nI think that this paper makes a significant contribution and am recommending acceptance. However, since these contributions are primarily theoretical, it is CRITICAL that the proofs be 100% correct. Therefore, I am noting the at my positive score is conditioned on the assumption that all of errors noted below be fixed in the camera copy. (Except for in any cases where I am incorrect, which should be discussed in reviewer discussion.) All of the errors are easily fixable, so I do not anticipate the authors having difficulty with them.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n- 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}$.\n- 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.\n- 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.\n- $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. \n- 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.\n- 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. \n- 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.\n- 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$.\n- 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.\n- 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.\nIt 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.\n- 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.\n- 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.\n- 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.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "Proofs were thoroughly checked. Mostly correct. However, there are a large number of (easily fixable errors) as detailed below. My score is predicated on the assumption that the authors will fix these mistakes in the camera copy.", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "Good discussion of GNNs and an okay review of manifold neural networks and manifold learning with some missing references noted below", "essential_references_not_discussed": "First paper (to my knowledge) to provide convergence rates for LBO derived deep networks as the number of samples -> \\infty\nhttps://www.sciencedirect.com/science/article/pii/S1063520324000125\n\nExtension of the previous work to more general deep networks. (To the best of my knowledge) this was the first paper to do this with a quantitative convergence rate (although Wang 2024a established a similar result without a rate) https://ieeexplore.ieee.org/abstract/document/10301407 \n\nWork extending MNN guarantees to non-uniform sampling which shows that the convergence rate can be improved via proper normalization and also applies to k-NN graphs (with a different weighted manifold Laplacian) https://arxiv.org/abs/2307.04056", "other_strengths_and_weaknesses": "3.1 In Setup – should specify that D and A are weighted degree matrices and weighted adjacency matrices\nShould also explain why a graph signal is a vector. (This is a slight abuse of notation since it is nominally a function. I understand that this is “standard” in GSP, but I think it is best to clarify that you are equating the function x:VR with the vector x_i = x(v_i).\n3.2 – Unclear what is meant by a ``Hausdorff Probability Measure.” The term Hausdorff measure usually refers to fractal (non-integer) dimensions. I think you mean that the measure is absolutely continuous with respect to the Riemannian  volume for\n4.1 - The assumption A.3 that the loss function is Lipschitz continuous doesn’t hold for common loss-functions such as the MSE or cross-entropy. This is okay, but should be properly discussed, especially since the cross-entropy loss was used in your experiments \n5. The current experiments are good, but it would be better to include some graphs that are clearly derived from a manifold. I understand that the authors show that there is a rapid decay of the graph Laplacian, but this does not directly indicate that the graph is a subsample of a manifold. Weyl’s law says that if the graph is from a manifold, then the Laplacian eigenspectrum will decay rapidly, but there is not a converse to this. (The modelnet experiments are good, but 2-d surfaces in 3-d space are fairly non-generic manifolds, which may not have co-dimension 1. Additionally, those shapes are likely not true manifolds because of corners.)\n\nIt is useful that the authors show that their theory applys to non-manifold graphs, but a direct illustration of the theory would also be beneficial. Perhaps the authors could look at the experimental setup in Johnson et al. https://arxiv.org/abs/2307.04056 where graphs are constructed via subsampling an ellipsoid (embedded in high-dimensional space). \n\nAppendix A: should clarify whether B_r is a ball with respect to the Euclidean distance (in ambient space) or the geodesic distance. \n\nAppendix A: VERY IMPORTANT – looking at Garcia Trillos et al, it appears that the bound on r only applies to d >= 3. There is a different result for d=2 and no result for d=1. Please update the theorem of your statement accordingly.\n\nAppendix A: VERY IMPORTANT The bounds in Prop 1 appear to depend on the bandlimit M. Please update the statement of the theorem (as well as Theorem 1) to reflect this.\n\nAppendix A: VERY IMPORTANT: The result you recall from Wang 2024a appears to be off (see (20) and (23) of Wang2024a) it looks like the result there features a square root epsilon and doesn’t have the lambda_i. Pleas also update all downstream results accordingly. Less importantly, Prop 4 of Wang 2024a appears to be a restatement of Calder and Trillos. Please make this more clear.\n\nEquation (36): shouldn’t |h’(\\lambda_i)| be replaced with \\sup_{lambda in [lambda_i,N – lamda_i| h’(\\lambda)? (This won’t affect the next step, but should still be fixed)\n\nEquation 42: I get lambda_i^{-d+1} rather than lambda_i^{-d}. Since there is a lambda^{-d} in the estimate of h and an lambda in your bound on ||phi_i,N – P_N phi_i||. Please double check this calculation. Notably, this means that the series will no longer be summable from 1 to infinity if d=2, but this is okay since it is a finite sum and A_2(M,N) already depends on the bandlimit \n\nShould recall Weyls law after the statement of 58 in order to make life easier for the reader\n\nProposition 3, why is there a C in the statement but a C’ in (71)? \n\nIt appears that the Lipschitz constant C depends on the bandlimit M.  This should be made clear in the statement of the proposition\n\nI don’t see how (74) follows from 72. It seems like there should be various sup’s there. I am confident that the result is true, but I think a simple induction proof would be much better. This should be fixed for the camera copy. (I think it this case, you can prove the result for L = 1 and then say that the general case follows by induction.)\n\nProp 3: The statement of the proposition should make clear that you are assuming f is bandlimited. I understand you make this assumption in theorem 1, but someone might read Prop 3 independently. (Alternatively, a good way to avoid this is to start Prop 3 with “assume the assumptions of theorem 1 hold”)\n\nProp 3: What is B_r(M)? I think you mean y \\in B_r(x)? (B_r(M) could mean the points in the ambient space which are close to the manifold)\n\nIn the Proof of Theorem 1, it is incorrect to call the V_i “Voronoi cells”, if you had actually used the Voronoi decomposition, as opposed the the V_i induced by the OT map, then the V_i would not all have the same measure.\n\nMinor\nSome notational inconsistency with subscripts. For example, in equation (1) there is a subscript G, but there is no subscript M in equation (4).\n\nThere are some uncapitalized words like Laplacian and Euclidean in the references. Please double check your bibtex entries\n\nAppendix A: To help the reader, it would be good to note that P_NI_Nx = x but that the we don’t have I_NP_N f = f. (This is a common source of confusion.)\n\nAppendix A: Line 862 “equation equation” (please check for this throughout)", "other_comments_or_suggestions": "N/A", "questions_for_authors": "It appears that you are assuming a single input channel. Is this restriction necessary? It appears that most of the theory can be extended to multiple input channels. I don’t think you should re-do the analysis, but maybe make add a remark to increase the impact of your theory \n\nSimilarly, in theorem 1, it appears you could remove the assumption that there is a constant number of filters per layer. Is this correct? If so, this could be a good thing to comment on briefly\n\nShould there be a 1/K in the definition of the risk functions in (17) and (18)? This would seem to be consistent with the 1/N_k\n\nPlotting the decay of the eigenvalues is interesting. Would it be possible to use this infer the manifold dimension via Weyl’s law via plotting the eigenvalues on a log plot?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vtDL420R1t", "reviewer": "Reviewer_k2or", "summary": "The paper addresses the question of generalization in GNNs when the graph is a discrete sample from the graph. They prove this theoretically, as well as experiment with several existing datasets.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**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.**\n\nThe 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. \nIn terms of novelty, let us point out 3 aspects that to the best of our knowledge are novel and insightful about our work:\n1. 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.*\n2. 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. \n3. 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. \n\n>**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\"**\n\nOur work and [1] have important differences. \n1. 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. \n2. 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.\n3. 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.\nIn all, although related, our paper is novel with respect to [1].\n\n[1] \"Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs\", Zhiyang Wang, Luana Ruiz, Alejandro Ribeiro\n\n>**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.**\n\nIn 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.\nWith 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. \nThe problem that we are considering is what it is called generalization in machine learning, see for example:\n[Chapter 3] Understanding Machine Learning: From Theory to Algorithms\nBy Shai Shalev-Shwartz and Shai Ben-David\nCambridge University Press; \n[Chapter 2] Foundations of Machine Learning\nMehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar\nMIT Press, Second Edition, 2018. https://cs.nyu.edu/~mohri/mlbook/; \n[Equations 1,2,3] Generalization analysis of message-passing neural networks on large random graphs\nS Maskey*, R Levie*, Y Lee, G Kutyniok\nNeurIPS 2022", "claims_and_evidence": "I have an issue with the empirical evidence. 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.", "methods_and_evaluation_criteria": "As stated before, not sure how the experiment support the theoretical part.", "theoretical_claims": "I did check the correctness, but I did not have time to comb over every part of the proofs. To the best of my understanding the proofs are ok.", "experimental_designs_or_analyses": "Discussed previously", "relation_to_broader_scientific_literature": "The claims in the paper sem very similar to theorem 2&3 from Weng et al \"Geometric Graph Filters and Neural Networks:\nLimit Properties and Discriminability Trade-offs\". Please state the exact difference between these results.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "I have a few concerns regarding this paper:\n- I am not sure about the novel contribution of this paper w.r.t Weng et al \"Geometric Graph Filters and Neural Networks:\nLimit Properties and Discriminability Trade-offs\"\n-  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. The graph level results only shows results on graphs on the seen manifolds, and no results on generalization to new manifolds. I do not think the way the authors present their results is aligned with what they actually show. S", "other_comments_or_suggestions": "Small remark- Fig. 2&3 are very unclear and should be improved or removed.", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents generalisation error bounds for graph neural networks (for both node-level and graph-level tasks) under the assumption that the graph is constructed on samples from a manifold. The bounds demonstrate the dependence of the generalisation error on the spectral continuity and the number of nodes. The work presents a new-dimension to the learning theory literature on GNNs by incorporating the manifold assumption, which could lead to further theoretical analysis for GNNs using the manifold connection. However, the immediate impact of the work could be limited due to lack of insight provided by generalisation bounds for NNs, and restriction of the work to convolutional GNNs.
Decision: Accept (poster)