Graph Representational Learning: When Does More Expressivity Hurt Generalization?
Authors: Sohir Maskey
Raffaele Paolino
Fabian Jogl
Gitta Kutyniok
Johannes F. Lutzeyer
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Neural Networks
Generalization
Expressivity
PAC-Bayes
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce a family of pseudometrics that capture different degrees of structural similarity between graphs and relate these similarities to generalization and performance of expressive GNNs.

Abstract: Graph Neural Networks (GNNs) are powerful tools for learning on structured data, yet the relationship between their expressivity and predictive performance remains unclear. We introduce a family of pseudometrics that capture different degrees of structural similarity between graphs and relate these similarities to generalization, and consequently, the performance of expressive GNNs. By considering a setting where graph labels are correlated with structural features, we derive generalization bounds that depend on the distance between training and test graphs, model complexity, and training set size.  These bounds reveal that more expressive GNNs may generalize worse unless their increased complexity is balanced by a sufficiently large training set or reduced distance between training and test graphs.  Our findings relate expressivity and generalization, offering theoretical insights supported by empirical results.

Published as a conference paper at ICLR 2026
GRAPH REPRESENTATIONAL LEARNING: WHEN DOES
MORE EXPRESSIVITY HURT GENERALIZATION?
Sohir Maskey!- Raffaele Paolino 2.3 Fabian Jogl
Gitta Kutyniok 2,3,5,6
Johannes F. Lutzeyer'
1 Aleph Alpha Research
2 Department of Mathematics, LMU Munich
3 Munich Center for Machine Learning (MCML)
4 Maahhnee Learning Research Unit, CAIML, TU Wien
6 "Institute for Robotics and Mechatronics, DIeR-German Aerospace Center
"Department of Physics and Technology, University of Tromsø
7 LIX, CNRS, École Polytechnique, Institut Polytechnique de Paris, France
ABSTRACT
Graph Neural Networks (GNNs) are powerful tools for learning structured data, yet the relationship between their expressivity and predictive performance remains unclear. We introduce a family of pseudometrics that capture different degrees of structural similarity between graphs and relate these similarities to generalization, and consequently, the performance of expressive GNNs. By considering setting where graph labels are correlated with structural features, we derive generalization bounds that depend on the distance between training and test graphs, model com- plexity, and training set size. These bounds reveal that more expressive GNNs may generalize worse unless their increased complexity is balanced by sufficiently large training set or reduced distance between training and test graphs. Our findings relate expressivity and generalization, offering theoretical insights supported by empirical results. Our code is available on GitHub
INTRODUCTION
Graph Neural Networks (GNNs) (Scarselli et al. 2009 Bronstein et al.) (017)) have become central tool for learning representations structured data. A major line of research has focused on improving their expressivity, that is, their capacity to distinguish non-isomorphic graphs, often evaluated with respect the Weisfeiler-Lehman (WL.) hierarchy of graph isomorphism tests (Weisfeiler Lehman 1968
Xu et al. 2019 Morris et al. 2020b 2023b).
The relationship between expressivity and performance of GNNs remains poorly understood. While more expressive models are theoretically capable of distinguishing broader range of non-isomorphic graphs, their practical effectiveness in real-world tasks is not always apparent. On the one hand, more expressive models have been shown to outperform standard architectures (Maron al. 2019a Bodnar et al. 2021 Bouritsas et al.) 2023). even when their additional expressive power does not result in separating more non-isomorphic graphs in the benchmarks at hand (Zopf 2022). For instance, the 1-WL test, and by extension simple message-passing neural networks (MPNNs) such as GIN (Xu al., 2019), can separate all graphs in widely used datasets (Zopf) 2022; Kriege al. 2020) and almost all random graphs (Babai et al., 1980), but performance is still far from saturated. On the other hand, less expressive models can outperform their more expressive counterparts. For example, Bechler-Speicher et al. (2024) show that models which completely discard the graph structure (hence, less-expressive than W-L..) can outperform sophisticated GNNs in certain tasks.
These contrasting observations suggest a complex and nuanced relationship between expressivity and performance, raising two critical questions:
1. When does increased expressivity in GNNs help, and when does it hurt performance?
EEaill: schi ma maskaaa leph-a a gigh-researeee com. Work done while LMU Munich.

---

Published as a conference paper at ICLR 2026
GNN error cycle task
Training loss (MUTAGENICITY)
Test error vs. noise
Label moise
LF-G
0.0
0.5
L-G
0.6
Sub-G
0.5
0.4
F7-MPNN
F MMPNN
Train
Text
0.4
0.8
1.0
0.3
Mutagenicity
Fa FMMM
0.2
MPNN
0.2
10
15
50
100
0
0.5
Error (%)
Epoch
Noise p
Train-tes test errors for several GNN variants synthetic cycle-counting task; moderately expressive models such as FA-MPNN (Barceló et al.) 202I). i.c., MPPNN augmented with eycle counts, generalize best, while more expressive ones tend to overfit. Center: Training-los curves of a MPNN on MUTAGENICITY under increasing label noise Right: Corresponding test errors on BZR, MUTAGENICITY, and NCI109 rises sharply as label-structure correlation essential for generalization (mean + standard deviation across five seeds). See Appendix [.I
Figure 1: Left:
for more details.
2. If a more expressive GNN performs better on a given task, is it due to its improved expres- sivity in terms of graph separability?
To explore these questions, we begin with synthetic graph-classification task in which the labels are designed to depend on a known structural feature, namely the number of cycles. We train a sequence of models whose expressive power increases from plain MPNN to an LF-GNN (Zhang al., 2024). As Figure [ (left) shows, moderately expressive models achieve the lowest test error, while the most expressive ones overfit, and performance deteriorates on unseen graphs. The result echoes a well-documented phenomenon in Euclidean deep learning: large neural networks can memorize arbitrary labels. yet they generalize only when there genuine correlation between data and labels. Classical complexity measures such as the VC dimension or Rademacher complexity cannot account for this behavior over- wverpparametrized regimes (Zhang et al., 2017). A more plausible explanation that generalization requires a balance between the model's s inductive bias (in our case, its expressivity) and the structure-label correlation present in the data.
We further test this hypothesis on three real-world graph datasets: BZR, MUTAGENICITY, and NC1109 (Morris et al.) (2000a). We follow the setup from Zhang et al. (2017) by progressively resampling the labels uniformly random, i.c., introducing label noise, while leaving the graphs untouched. Figure [ (center and right) shows that the training loss still converges to zero, confirming the network's 's ability to memorize, yet the test error rises sharply soon as the correlation between the graphs and labels is destroyed. Together, these experiments indicate that expressivity by itself is neither strictly harmful nor helpful; model performance ultimately is determined by the model's ability to measure similarity in way that reflects the task-relevant relation between graphs and labels. In this work, set out better understand this phenomenon.
1.1 OUR CONTRIBUTION
We formalize the empirical insight that generalization heavily depends on structure-label correlation as follows. We introduce a family of pseudometrics, called Ç-Tree Mover Distances (C-TMDs each parameterized by a graph invariant (e.g.. degree distributions or k-WL colors), which measure specific level of expressivity. We then consider a graph classification setting where labels correlate with fixed C-TMD: two graphs are likely to share the same label if they are similar under the chosen pscudometric. This captures structure-label alignment, property empirically validate across several roaldworld graph learning tasks, where generalization depends critically on such alignment.
Within this framework, we derive data-dependent generalization bounds for models with fixed encoders (e.g., random GNN features) and expressive, end-to-end trainable GNNs (e.g., GIN, GAT, k-GNNs). Our bound (Theorem 4.1 Equation 4 decomposes the generalization gap into two terms: a capacity term, depending on model width, weight norms, and maximum node degree, and structural similarity term, which measures the distance between training and test graphs under
2

---

Published as a conference paper at ICLR 2026
the chosen (-TMD. This decomposition highlights that generalization improves when the model maps structurally similar graphs (with respect to the Ç-TMD that correlates with the labels) to similar representations while keeping model capacity in check.
This perspective not only explains existing empirical observations but also guides model design. Deeper or more expressive GNNs improve performance but only if they enhance the structural similarity between train and test graphs. Otherwise, increased complexity may fail to improve label alignment, thereby degrading both generalization and computational efficiency. This trade-off is especially relevant since higher-order methods often introduce significant computational overhead. In Section | we formalize this phenomenon and show that, in a concrete setting, the optimal GNN is precisely as expressive as required to capture the relevant structure-labe correlation no more, no less.
1.2 RELATED WORK
Expressivity in GNNs. A common benehmark for GNN expressivity is the Weisfeiler-Leman (k- (k-WL) hierarchy, which measures the ability to distinguish -oomisomopphic graphs. Standard MPNNs are provably limited by 1-WI. expressivity (Xu al. 2019; Morris et al., 2019). while higher-order k-GNNs (Morris et al. 2020b) and subgraph-based models (Frasca et al.) 2022) extend this by incorporating higher-order structural interactions. Structural and positional encodings (Vignac et al.) 2020 Barceló et al.) 2021) enhance expressivity by injecting global features into node representations.
Jogl al. (2024) offer unifying view by showing that many expressive architectures can be simulated via input transformations followed by standard message passing.
However, expressivity often comes at a computational cost: while MPNNS scale linearly with edges (0( E!)). subgraph-based and higher-order models scale super-linearly (e.g., O(V]][F) or O(VV))), making them less viable for large-scale graphs.
Generalization in GNNs. Generalization theory for GNNs traditionally relied on classical complexity measures such as VC-dimension (Scarselli et al. 2018 Rademacher complexity (Garg et al. [0020] Abbahaddou et al. 2025), ) and PAC-Bayes bounds (Liao et al. [202]) Graphon-based frameworks
[Levie|[0224 establish bounds using covering numbers in continuous function spaces. Similarly, Maskey et al. 2202a 2025) establish tighter bounds using graphon models, but under stronger assumptions on the data distribution and their analysis does not directly handle expressive GNNs.
Recent works increasingly focus the interplay between expressivity and generalization. Morris et al. (2023)) relate 1-WL to VC-dimension in MPNNs. [i et al. (2025) analyze a trade-off between intra-class concentration and inter-class separation, but only for fixed graph encoders. [Wang et al. (2024) study graphs sampled from manifolds, and Ma et al. 2021) model label-feature correlations node classification, but neither framework extends graph-level tasks expressive GNNs.
Most recently, Vasileiou et al. (025) derive tighter generalization bounds by combining covering number arguments with the robustness framework offXu & Mannor (2012), using the fact that MPNNs are Lipschitz with respect to Tree and Forest distances. Their analysis does not model structure-label correlation and is limited to standard MPNNs. We refer to Appendix for further discussion.
Comparison with Prior Work. While existing approaches have deepened our understanding of GNN generalization, many rely on idealized assumptions such as known graphon distributions or fixed feature maps that limit applicability to real- real-world graph learning. The work most closely related to ours Ma al. (202)). which models label-feature alignment does not support graph-level tasks or trainable GNNs. In contrast, our framework explicitly models structure-label correlation using task-alia aask-aligned pseudometrics and supports expressive, end-to-end trainable GNNs. enables a fine-grai fine-grained analysis of how architectural expressivity and task alignment interact. Our generalization bounds identify when increased expressivity may improve performance and when it leads to overfitting addressing key open question posed by Morris et al. (202)).
2 PRELIMINARIES
Let G denote the set of all simple, undirected graphs, and let G = (V, G, where V, or V(G), is the set of nodes and E is the set of edges. For any node E V, the neighborhood is defined as: (( = (u V (v. u) E F.).
3

---

Published as a conference paper at ICLR 2026
Definition 2.1 (Graph Invariant and CRA). A graph invariant is function Ç : C that assigns value to each graph such that for any isomorphic graphs G and H, it holds that ((G) = ((H).
A color refinement algorithm (CRA) (()) is mapping that assigns to each graph G a function Co V(G) + P such that for any graph H isomorphic to G, and any isomorphism h V(H) + V(G), the CRA satisfies (a(v)) (H (b()) for all v E (G)..
We note that every CRA ((-) induces graph invariant ( by aggregating the vertex labels into multiset. Specifically, the induced graph invariant is defined as ((G) == (((a(e)))evv where {t- denotes multiset. Throughout this work, we use the terms "graph invariant" and "CRA" interchangeably when the context allows.
Graph invariants vary in their ability to distinguish between graphs. We say that a graph invariant is more expressive than another graph invariant 0 if ((G) ((H) implies ((G) ((H) for all G,H E g.
Definition 2.2 (Message Passing Neural Networks (MPNNs)), For graph = (V, E) with node features I E RIV[X an MPNN updates node v E V at layer as:
((+1) !) f(4+1) (1l²) (u,N(N)()))
{( (1 }))
where f(++1) and g ((+1) are MLPs, and D denotes permutation permutaaion-invariinn aggregation function.
We focus on sum aggregation, but our framework naturally extends to mean or weighted sum aggregation. After the final message passing layer, node features are typically aggregated into graph-level representation, followed by a final MI..
Similar to MPNNs, the / l-Weisfeiler--ehmman (I-WL) Test updates the node features of input graphs through local neighborhood aggregation. However, a key distinction is that in I-WL, both the message and update functions necessarily injective. 1-WL provides a tight upper bound the expressivity of MPNNs (Xu et al. 2019 Morris et al. 2020b).
To quantify similarity between graphs, we use the notion of pseudometrics. In particular, every graph invariant naturally induces a pseudometric (G, H) with de H) = 0 if C(G) = ((H) and dc(G. H) = otherwise. However, such pseudometries only indicate whether two graphs are distinguishable by (distance 0 or 1). To capture finer structural similarities, general pseudometrics are often employed. Conversely, any pseudometric can induce graph invariant Ça by anchoring comparisons to fixed graph A E G with Ça. (G) d(G,A) A). Thus, pseudometrics can be seen as generalizations of graph invariants, offering richer measures of graph similarity.
The Tree Mover's Distance (TMD) (Chuang & Jegelka| 2022) is pseudometric that quantifies the dissimilarity between two graphs. Formally, for graphs G and H, and a depth t, the TMD is defined as the Wasserstein distance between their distributions of rooted trees up to depth t:
TMD' H) Wasserstein (T'(G), (H)))
where (G) and (H) are the multisets of rooted trees of depth generated by the 1-WL test for G and H, respectively. For further details, we refer to Appendix C
3 GENERALIZED TREE MOVER'S ' DISTANCE FOR STRONGLY SIMULATABLE COLORINGS
We now extend the concept of the TMD to a broader class of CRAs that can be strongly simulated by the 1-WL test. For detailed proofs of the results presented in this section, refer to Appendix C.2
A CRA is said to be strongly simulatable if, for any graph G, running iterations of the CRA G can be simulated by running iterations of the 1-WL test on a suitably transformed graph R2 (G). This transformation, called the strong simulation under Ç, ensures that the colorings at each 1-WL iteration on RS (G) are at least as expressive as those of ( (Jogl et al. 2024) on G. See Appendix B for more details and examples of CRAs and their corresponding transtormed graphs.
For any strongly simulatable CRA Ç. we define a generalized pseudometric as the TMD between the strong simulations of the graphs under Ç.
4

---

Published as a conference paper at ICLR 2026
Definition 3.1. Let Ç be strongly simulatable CRA. For any depth t 0, the Ç-TMD is defined as: <-TMD' H)) = TMD' (I& (G), (H)).
(1)
where BS GG) and RS (H) are the strong simulations of G and И under Ç. respectively.
Proposition 3.2. Let Ç be strongly simulatable CRA. For every > Ç-TMD' is a pseudometric.
Similar to the standard TMD, (-TMD' H) can zero even * H, as is a pseudometric. Nonetheless, it can distinguish graphs that are differentiable by the color refinement algorithm within iterations.
Proposition 3.3. Let Ç be a strongly simulatable CRA. If two graphs G and are distinguished by after T iterations, then C-TMDT+ +G,, H)
Another immediate consequence is that MPNNs corresponding to the CRA Ç, referred to as Ç (-MPNNs, are Lipschitz continuous with respect to the (-TMD. Specifically, we have the following result:
Theorem 3.4. Let Ç be strongly simulatable CRA, and let h - RK be a C-MPNN with T layers, where the message and update functions are Lipschitz continuous with Lipschitz constants bounded by ligto and I. Tog,,, respectively. Suppose h includes global sum pooling layer followed by Lipschitz continuous classifier with Lipschitz constant Le. Then, for any graphs G and H,
[I(G) h(H)ll < L L-
where L = L.2 ITT=1 Lec Lgto and
denotes the Euclidean vector norm.
The Lipschitz property established in Theorem 3.4 plays a key role in deriving the generalization bounds for (MMPNNs presented in Section Next, we illustrate the Lipschitz continuity using the example of J-MPNNs.
3.1 EXAMPLE: F-MPNNS
The F- F-Weisfeiler-Leme (F-WL) test generalizes the 1-WL test by incorporating features derived from a finite family graphs, F C G. These features, often referred to as motifs or patterns, are used to enhance node representations.
Specifically, for each node v in graph G, the feature vector of u augmented with counts patterns in F that include Formally, the augmented feature vector is defined as:
Fe (xv, ent( P1, G:
ent ()F( G:
where cnt(P, G;v) represents the number of occurrences the pattern P in G such that is part of the pattern. These counts can for example be (injective) homomorphism counts (Bouritsas et al. 2023 or cycle basis counts Yan et al. 2024).
If C F. then F-WL more expressive than F-WL Barceló et al. 2021 Bouritsas et al. 2023
Correspondingly, F-MPNNs incorporate these motif counts into their message-passing scheme. Clearly, WL can be strongly simulated via transformed graph R (G) that includes the motif counts as node features.
Corollary 3.5. Let h be an F-MPNN with T layers. Then, there exists constant L such that for any graphs and H,
[[(GG) - h(H) L F--MMD+++(( HG.
We emphasize that this is just one example; analogous definitions C-TMDs and corresponding versions of Corollary 3.5 can be derived for other GNN architectures, such k-GNNs (Morris et al. 2019), see Appendix
4 GENERALIZATION BOUNDS WITH RESPECT TO TREE MOVER'S DISTANCE
In this section, establish generalization bounds for GNNs using our generalized TMD framework.
5

---

Published as a conference paper at ICLR 2026
4.1 PROBLEM SETUP AND ASSUMPTIONS
We consider a classification task where each data point is a graph equipped with node features. Formally, let Gür and Gie denote the fixed of training and test graphs, respectively. We assume that there exists a constant > 0 such that the norm of each node feature is bounded, i.e.,
|ax(G),ll B AG Gu U Gre, Vi V(G).
Each graph G is assigned label yc {1, (.,,....e K].. We assume that, for each class there exists Lipschitz continuous function 7) : + [0, with respect to some pseudometric pm such that
Pr(uc k G) (G),
and set C m (I....k) Lip(n)). If the labels are sampled according to such functions T)k- we say that the labels y are strongly correlated with pm and write pm.
Furthermore, we define Epm the distance between the training set and the test set:
Epm pm (G Gu. = max min pm(G, H). GESt HES,
Given the set labeled graphs Ger the task of graph-level supervised learning is learn classifier h: 9 + RK from function family H. Given classifier h H. the classification for graph G is obtained by
jG argmax [G))[k).
ke(I....KK
where [K] refers to the k-th entry of (G)).
For the observed graph labels (yc)aeg.. the empirical margin loss of h on Gur for margin 2 0 defined as
1
(h)
Σ I[h(G)[ya] s (7 max (G))
Ni
kसya
GED
Here, 1 is the indicator function. The empirical margin loss of h Gie is defined equivalently. The expected margin loss is defined as follows, C% (h) := Prva-
[ (h)
4.2 MAIN RESULTS
In this section, we derive generalization bounds for GNNs, where we focus on the standard approach involving end-to-end trainable GNNs.
We consider the GNN to be the composition of two functions. Specifically, let e : G + R² denote the graph embedding network, which maps graph G' G into b-dimensional latent space, and let c: TR >> IR K denote the classifier, which maps embeddings to class scores. Consequently, the hypothesis space for these models can be written as:
Co
where ε represents the space of graph embedding networks and C represents the class of MLP classifiers. For end-to-end learnable GNNs, both & and C are trainable. In contrast, for models with fixed encoders, only C is trainable, while & remains fixed.
4.2.1 END-TO-END LEARNABLE GNNs
Let represent a CRA that can be strongly simulated by 1-WL, In this context, we consider the hypothesis space Hg- = C o Eg. where Eg is the set of all Ç-MPNNs of depth T, where each layer consists of message function (()) and update function f(4), Both g(t) and f()) are MLPs with maximum hidden dimension and may contain an arbitrary number of layers. The weight matrices across all message and update functions are denoted by (Wi)-
Let denote the set of MLP classifiers with L layers and maximum hidden dimension of b. The weight matrices in the MLP classifier are denoted by (W,)
We now present the generalization bound for end-to-end learablee GNNs.

---

Published as a conference paper at ICLR 2026
Theorem 4.1. Suppose that y (-TMDT+1 Under mild assumptions (see Appendix D for any Y > and < a < 3. with probability at least - 5 over the sample of training labels yuu we have for any E Hc
b E, 1 + E, IIIBB
2/D In (2bDC(2DB)VP) 12211/66 + +CKE
(1) S (h)(h)
No (7/8)2/D
where &c = --TMD (Gre. Gir) is defined in Equation 3 D represents the total number of learnable weight matrices, b denotes the maximum hidden dimension, is the maximum degree of nodes in the graphs, and C serves an upper bound on the spectral norm of all weight matrices.
Theorem highlights key factors influencing generalization in learnable graph classifiers, which are the structural similarity & under (-TMD, model complexity (D,& b, (1lWll22). (1 graph properties such maximum degree d. and training set size Nir- The structural similarity term & emphasizes the importance of diverse training data. This agrees with empirical observations by Southern et al. (2025), who demonstrated that augmenting graph representation maximize TMD dissimilarity improves predictive performance and generalization. These findings underscore the significance of diverse training data (via task task-specific augmentations) and balancing model complexity to achieve robust graph- graph-based learning.
The proof of Theorem 4.1 given in Appendix E follows standard PAC-Bayesian approach (Neyshabur et al. 2018) and extends it to the correlated setting, following the approach (Mal al.] [2021) It leverages the Lipschitz continuity of C-MPNNs, established in Theorem [34] derive the generalization bound. Throughout the remainder of this paper, we use the following simplified version of the bound from Theorem 4.1
cle(h) S (b) + of N 31/0
MC(CoE.)
C structural similarity term
(4)
complexity term
Here, MC(Co captures the model complexity, i.e., spectral norms of all learnable weight matrices, hidden dimensions, and maximal node degree of the graphs. Notably, the model complexity may increase the graph transformation f8 enlarges the size, maximum degree, or node feature dimension of the original input graphs.
The structural similarity term, &c, depends on the alignment between training and test graphs under <-TMD. Whether & increases decreases with more expressive networks depends the task.
The same PAC-Bayes machinery yields analogous bounds when the graph encoder is frozen and only the MLP head is trained. We relegate the formal statement and proof Appendix Fto keep the main exposition focused on the end-to-end learnable case.
5 WHEN DOES MORE EXPRESSIVITY HURT?
In this section, we explore two scenarios within our framework: first, we identify conditions under which augmenting expressivity beyond task-specific requirements negatively impact generaliza- tion. Second, we highlight conditions where increasing expressivity to accurately capture task-specific features does not degrade the bound in Theorem 4.1 This gives a possible explanation of why such graph classifiers achieve an optimal balance between expressivity and generalization, resulting in superior performance.
To formalize this, consider a classification task where the labels are strongly correlated with the pseudometric F-TMD for a specific set of substructures F C G. Assume that all MPNNs considered in this section have layers. Let F F Ç F C G be finite sets of graphs, where F'-MPNNs are less expressive than F-MPNNs, which in turn are less expressive than F-MPNNs. Denote the corresponding hypothesis spaces H.., H1. and Hz.
Our analysis shows that increasing expressivity to the level required to capture task relevanlevant features (e.g., transitioning from J'-MPNNs J-MPNNs) generally preserves generalization. However,
7

---

Published as a conference paper at ICLR 2026
further increasing expressivity beyond this necessary level (e.g., to F-MPNNs) degrade general- ization significantly.
Theorem 5.1. Consider the setting above. Then, for any y > and a < with probubility at least
1 6 over the sample of training labels yhr.
i) the test loss of any F' FMMPNN classifier h', satisfies
MC 2/D Cio( - (1)) + N2a + CEF
where C is described in Theorem 4.1 and E FF-MDD (9tr: Gto)- ii) the test loss of any F-MPNN classifier h, satisfies
Fle(h) S (h) + o M 1/D
(MCCH))))))
N2a + CEF
tii) the test loss of any F-MPNN classifier h, satisfies
M 3/D N2 + CEF
clo(h) (2)(h) o
where Ey = F-TMD Gre).
Theorem 5.1 highlights the critical role of structural alignment between training and test graphs in determining generalization performance. In cases i) and ii), the same F-TMD governs the similarity between training and test graphs, ensuring that the bound remains controlled. However, in case iii), introducing a more expressive GNN that captures features beyond those captured by F-TMD (with which the labels are strongly correlated) leads to a higher structural discrepancy & 2 &x, see Lemma G.1 These findings underscore the importance of aligning model expressivity with the structural requirements of the task, excessive expressivity can increase our generalization bound in Theorem
EXPERIMENTS
In this section, we evaluate GNNs on both synthetic and real-world graph datasets. We introduce two tasks to evaluate how structural similarity between training and test graphs, well task-relevant expressivity, impact classification performance and generalization. All experiments use 10-fold cross-valide cross-validation, and report the mean accuracy error. Additional experiments and tasks, details and extended results are provided in Appendix[]
Task 1: Median-Based Labeling with Cycle Counts. We generate 3,000 random graphs from Erdōs-Rényi, Barabási-Allbrrt, and Stochastic Block Model distribu- tions. The sum of 3-cycle and 4-cycle counts is computed for each graph, and graphs with counts below the dataset's median receive label 0, while those above receive label
Table I:
Test accuracy on Erdös-Rényi graphs for Task All GNNs achieve train accuracy greater than 0.99. More results Table 4 in Appendix
Model
Test Accuracy
We evaluate multiple GNN variants, including stan- dard MPNNs, Fr-MPNNs where Fi contains cycles up to length I, Subgraph GNNs (Sub-G), Local 2-GNNs (I.-G), and Local Folklore 2-GNNs (LF-G). Model expressivity increases strictly in this order. We report training and test accuracies both the final and the epoch with the best validation performance, Results can be found in Table and more details and experiments in Appendix [[]
LF-G
0.8450 = 0.0135
L-G
0.8543 0.0063
Sub-G
0.8623 = 0.0058
J7-MPNN
0.9660 = 0.0065
F-MMPNN
0.9793 = 0.0068
F--MPNN
0.8657 0.0085
MPNN
0.8490 0.0045
Task 2: World Datasets We evaluate our framework on six graph classification datasets from the TUDataset Morris et al. 2020a). Results BZR, MUTAGENICITY, and NCI109 include:
8

---

Published as a conference paper at ICLR 2026
BZR
Mutagenicity
NCT109
Blyyers
0.9
Flayers ery
0.9
Flayers
Accuracy
0.85
0.9
0.8
0.8
0.8
0.7
10
10a
10
10
10
10a
10
10
10
10a
10a
10
TMD to training set
TMD training
TMD training set
Figure 2: Accuracy of a GIN with 1, 3, and 5 layers versus TMD (log scale) to the training dataset.
Mutagenicity
NCT109
10a
-104
2
1.4
Empirical Error
0.2
Empirical Error
Error Bound
0.1
Error Bound
1.2
0.15
1.5
5 10-2
0.1
10-2
0.8
0 200 400 600 800
500
1,000
TMD to training dataset
TMD to training dataset
Figure 3: Error-bound curves for Mutagenicity, and NCI109. Each plot shows theoretical bound (blue, left axis) and the empirical generalization error (red, right axis) as a function of TMD to the training set. Shaded areas indicate +1 standard deviation across 10 random splits.
Figure 2
which plots test accuracy versus (-TMD distance, and Figure which compares our bound to the observed generalization gap. Additional results PROTEINS. S, AIDS, COX2, and experiments on fixed encoders via molecular fingerprints (Gainza et al. 2019 appear Appendix []
Results and Discussion. In Task GNNs that explicitly incorporate task-relevant cycle information, in particular F4-MPNNs, outperform MPNNs and expressive GNNs like Local Folklore 2-GNNs. Since the labels in Task strongly correlated with Fa-TMD, these results align with our theoretical findings in Section S GNNs that effectively leverage features strongly correlated with the task generalize better than more expressive models. On real-world datasets, we observe that classification accuracy declines as test graphs become more distant from the training set, in line with our theoretical insights in Theorem 4.1 Importantly, our bound closely aligns with the observed generalization gap across these datasets. By explicitly capturing structure-label correlation, our framework yields significantly tighter generalization bounds compared standard PAC-Bayes bounds (Liao al. 2021), which are often orders of magnitude larger (e.g., on the order of 10 compared to our 10*).
CONCLUSION
We introduced a framework for analyzing GNN generalization in settings where graph labels correlate with different pseudometrics. Our analysis provided generalization bounds that emphasize the role of structural similarity between training and test data. We show that increasing expressivity does not necessarily degrade generalization if it aligns with the task. However, both theoretical and empirical worsen generalization and predictive performance.
results show that excessive expressivity
Empirical results confirm that GNNs whose embeddings align with task-relevant structures, i.e., those that proven to be Lipschitz continuous with respect to pseudometries strongly correlated with the labels, achieve better generalization. We show that performance degrades for test graphs that structurally distant from the training set, supporting theoretical findings. Additionally,

---

Published as a conference paper at ICLR 2026
identify cases where increased expressivity can either improve hinder generalization, depending on task alignment, providing insights for GNN design.
Limitations. While our framework enables comparisons between F-MPNNs, in general the depen- dence of our bound in Theorem 4.1 on different TMDs makes direct model comparisons challenging. These bounds serve as qualitative guidelines rather than precise estimates, they are not tight and may not reflect practical performance. Moreover, the relevant pseudometric is often unknown and possibly expensive compute, limiting direct applicability and leaving the identification of suitable metrics an open problem.
Future Work. Our generalization bounds improve with increased structural similarity between test and train graphs. Future work could explore augmentation techniques that generate synthetic graphs improve this similarity, thereby boosting generalization.
ETHICS STATEMENT
This work focuses theoretical analysis of GNNs and does not involve experiments on human subjects, sensitive personal data, or applications with direct societal risks. The datasets referenced publicly available benchmark graphs, and private restricted data was used. Potential ethical concerns related to misuse are minimal, as the contributions are mainly theoretical and methodological. We explicitly acknowledge that LLMs were used only for polishing sentence clarity and grammar, not for generating research ideas, proofs, or results.
REPRODUCIBILITY STATEMENT
We have taken multiple steps to ensure reproducibility of our results. All theoretical claims are accompanied by rigorous proofs, presented in detail in the appendix. Assumptions underlying the theorems are explicitly stated, and definitions are given in full allow independent verification. In addition, provide open-source code to reproduce illustrative experiments and examples, which is available at GitHub
REFERENCES
Yassine Abbahaddou, Fragkiskos Malliaros, Johannes Lutzeyer, Amine M Aboussalah, and Michalis Vazirgiannis. Gaussian Mixture Models Based Augmentation Enhances GNN General- ization. International Conference on Machine Learning (ICMI., 2025.
Ralph Abboud, Ismail Ilaa Ceylan, Martin Grohe, and Thomas Lukasiewicz. The Surprising Power of Graph Neural Networks with Random Node Initialization. In International Joint Conference on Artificial Intelligence (ICCA). pp- 2112-2118. 2021.
Ralph Abboud, Radoslav Dimitrov, and Ismail Ilkn Ceylan. Shortest Path Networks for Graph Property Prediction. In Learning on Graphs Conference (LoG), pp. 5:1-5:25, 2022.
László Babai, Paul Erdös, and Stanley M. Selkow. Random Graph Isomorphism. SIAM J. Comput., 9,628-635, 1980.
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph Neural Networks with Local Graph Parameters. In Advances in Neural Information Processing Systems (NeurIPS), pp. 22880-25293, 2021.
Franka Bause, Fabian Jogl, Patrick Indri, Tamara Drucks, David Penz, Nils Kriege, Thomas Gärtner, Pascal Welke, and Maximilian Thiessen. Maximally Expressive GNNs for Outerplanar Graphs. In NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023.
Maya Bechler-Speicher, Ido Amos, Ran Gilaa-Bachrach, and Amir Globerson. Graph Neural Networks Use Graphs When They Shouldn't. International Conference on Machine Learning (ICML), 2024.
10

---

Published as a conference paper at ICLR 2026
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant Subgraph Aggregation Networks. In International Conference Learning Representations (ICLR), 2021.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montufar, and Michael M. Bronstein. Weisfeiler and Lehman Go Cellular: CW Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45:657-668, 2023.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric Deep Learning: Going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18-42 2017.
Lars Buitinck, Gilles Louppe, Mathieu Blondel, Fabian Pedregosa, Andreas Mueller, Olivier Grisel, Vlad Niculae, Peter Prettenhofer, Alexandre Gramfort, Jaques Grobler, Robert Layton, Jake VanderPlas, Arnad Joly, Brian Holt, and Gaël Varoquaux. API Design for Machine Learning Software: Experiences from the scikit-learn Project. ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pp. 108-122, 2013.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the Equivalence Between Graph Isomorphism Testing and Function Approximation With GNNs. In Advances in Neural Information Processing Systems (NeurIPS), pp. 15868-15876, 2019.
Ching- Cho Chuang and Stefanie Jegelka. Tree Mover's Distance: Bridging Graph Metries and Stability of Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
George Cybenko.
Approximation by Superpositions of a Sigmoidal Function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring Graph Neural Networks for Node Disambiguation. In International Joint Conference Artificial Intelligence (IJCAI), pp. 2126-2132, 2020.
Yair Davidson and Nadav Dym. On the Hölder Stability of Multiset and Graph Neural Networks. In International Conference on Learning Representations (ICLR), 2025.
Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. In International Colloquium on Automata, Languages, and Programming (ICALP), volume 107, pp. 40:1-40:14, 2018.
Radoslav Dimitrov, Zeyang Zhao, Ralph Abboud, and Ismail Ilkan Ceylan. PlanE: Representation Learning over Planar Graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
Simon S. Du, Kangcheng Hou, Barnabás Póezos, Ruslan Salakhutdinov, Ruosong Wang. and Keyulu Xu. Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels. Advances in Neural Information Processing Systems, 2019.
Matthias Fey and Jan E. Lenssen. Fast Graph Representation Learning with PyTorch Geometric, In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
Billy Joe Franks, Christopher Morris, Ameya Velingker, and Floris Geerts. Weisfeiler-Lent Leman at the Margin: When More Expressivity Matters. In Forty-first International Conference Machine Learning, 2024.
Fabrizio Frasca, Beatrice Bevilacqua. Michael Bronstein, and Haggai Maron. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries. In Advances in Neural Information Processing Systems (NeurIPS), pp. 31376-31390, 2022.

---

Published as a conference paper at ICLR 2026
Pablo Gainza, Freyr Sverrisson, F. Monti, Emanuele Rodolà, Davide Boscaini, Michael M. Bronstein, and Bruno E. Correia. Deciphering Interaction Fingerprints From Protein Molecular Surfaces Using Geometric Deep Learning. Nature Methods, 17:184 192, 2019.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and Representational Limits of Graph Neural Networks. Proceedings of the 37th International Conference on Muchine Learning (ICML), 11::3419-3430 2020.
Floris Geerts and Juan L Reutter. Expressiveness and Approximation Properties of Graph Neural Networks. In International Conference on Learning Representations (ICLR), 2022.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. International Conference on Machine Learning (ICML), pp. 1263-1272, 2017.
Caterina Graziani, Tamara Drucks, Fabian Jogl, Monica Bianchini, franco scarselli, and Thomas Gärtner. The Expressive Power Path-Bat Bashd Graph Neural Networks. In Forty-first International Conference Machine Learning (ICML), 2024.
Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring Network Structure, Dynamics, and Function Using NetworkX. Technical report, Los Alamos National Lab,(LAN)), Los Alamos, NM (United States), 2008
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer Feedforward Networks Are Universal Approximators. Neural Networks, 2(5):359- 1989.
Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the Cycle Counting Power of Graph Neural Networks with I-GNNs. In International Conference on Learning Representations (ICLR), 2022.
Emily Jin, Michael Bronstein, Ismail Ilkan Ceylan, and Matthias Lanzinger. Homomorphism Counts for Graph Neural Networks: All About That Basis. In International Conference on Machine Learning (ICML), 2024.
Fabian Jogl, Maximilian Thiessen, and Thomas Gärtner. Expressivity- Sppressivity-PPeeevving GNN Simulation. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024.
Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7090-7099, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations (ICLR), 2015.
Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. A Survey on Graph Kernels. Applied Network Science, 5:1-42, 2020.
J. B. Kruskal. Nonmetric Multidimensional Scaling: A Numerical Method. Psychometrika, 29(2): 115-129, 1964.
Ron Levie. Graphon-Signal Analysis of Graph Neural Networks. Advances Neural Information Processing Systems (NeurIPS), 36, 2024.
Shouheng Li. Floris Geerts, Dongwoo Kim, and Qing Wang. Towards Bridging Generalization and Expressivity of Graph Neural Networks. In International Conference on Learning Representations (ICIR), 2025.
Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks. In International Conference on Learning Representations (ICLR), 2021.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and Basis Invariant Networks for Spectral Graph Representation Learning. In International Conference on Learning Representations (ICLR), 2022.
12

---

Published as a conference paper at ICLR 2026
László Miklós Lovász. Operations With Structures. Acta Mathematica Academiae Scientiarum Hungarica, 18:321-328, 1967.
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup Generalization and Fairness of Graph Neural Networks. Advances in Neural Information Processing Systems(Neur(PS), 2021.
Haggai Maron, Heli Ben-Hamu Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. In International Conference on Learning Representations (ICLR), 2018.
Haggai Maron, Heli Ben-Bame Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 2153-21666 2164, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks. In International Conference Machine Learning (ICML), pp. 4363-4371, 2019b.
Sohir Maskey, Ron Levie, Yunscok Lee, and Gitta Kutyniok. Generalization Analysis of Message Passing Neural Networks Large Random Graphs. Advances in Neural Information Processing Systems(NeurlPSS, 35, 2022a.
Sohir Maskey, Ali Parviz, Maximilian Thiessen, Hannes Stärk, Ylli Sadikaj, and Haggai Maron. Generalized Laplacian Positional Encoding for Graph Representation Learning. In NewrlPS 2022 Workshop on Symmetry and Geometry in Neural Representations, 2022b.
Sohir Maskey, Gitta Kutyniok, and Ron Levie. Generalization Bounds for Message Passing Networks on Mixture of Graphons. SIAM Journal on Mathematics of Data Science, 7(2):802-825, 2025.
Gaspard Michel, Giannis Nikolentzos, Johannes F, Lutzeyer, and Michalis Vazirgiannis. Path Neural Networks: Expressive and Accurate Graph Neural Networks. In International Conference on Machine Learning (ICML), pp. 24737-24755, 2023.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In AAAI Conference on Artificial Intellignnce (AAAI), pp. 4602 4609, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A Collection of Benchmark Datasets for Learning With Graphs. ICML Workshop: Graph Representation Learning and Beyond, 2020a.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and Leman Go Sparse: Towards Scalable Higher-Order Graph Embeddings. In Advances in Neural Information Processing Systems (NeurIPS), pp. 21824-21840, 2020b.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permutation-eqquivrraan graph networks. In International Conference on Machine Learning (ICML), pp. 16017-16042. PMLR, 2022.
Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe, WL Meet VC. Proceedings of the 40th International Conference Machine Learning (ICML), pp. 25275-25302, 2023a.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and Leman Go Machine Learning: The Story so Far. Journal of Muchine Learning Research, 24:333:1-333:57 2023b.
Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, ismail ilkan Ceylan, Ron Levie, Derek Lim, Michael Bronstein, Martin Grohe, and Stefanie Jegelka. Future Directions in the Theory of Graph Machine Learning. In International Conference Machine Learning (ICML), 2024.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian Approach to Spectrally- Spectrally-Normaaizee Normalizdd Margin Bounds for Neural Networks. In International Conference on Learning Representations (ICLR), 2018.
13

---

Published as a conference paper at ICLR 2026
Hoang Nguyen and Takanori Machara. Graph Homomorphism Convolution. In International Conference on Machine Learning (ICML), pp. 7306-7316, 2020.
Raffaele Paolino, Sohir Maskey, Pascal Welke, and Gitta Kutyniok. Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
Pál András Papp and Roger Wattenhofer. A Theoretical Comparison of Graph Neural Network Extensions. In International Conference on Machine Learning (ICML), pp. 17323-17345, 2022.
Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered Subgraph Aggregation Networks. Advances in Neural Information Processing Systems (NeurIPS), pp. 21030-21045, 2022.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation Ratios of Graph Neural Networks for Combinatorial Problems. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Features Strengthen Graph Neural Networks. In SIAM International Conference Data Mining (SDM), pp. 333-341, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1))61-80, 2009.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The of Graph and Recursive Neural Networks. Neural Networks, 108:248-2571 2018.
Dimension
Joshua Southern, Yam Eitan, Guy Bar-Shalom, Michael Bronstein, Haggai Maron, and Fabrizio Frasca. Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Basee Centrality. International Conference Machine Learning (ICML), 2025.
Gottfried Tinhofer. Graph isomorphism and theorems of birkhoff type. Computing, 36:285-300, 1986.
Gottfried Tinhofer. A Note on Compact Graphs. Discrete Applied Mathematics, 30:253-264, 1991.
Joel A. Tropp. An Introduction to Matrix Concentration Inequalities. Found. Trends Mach. Learn., 8 (1-2), 2015.
Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing. Transactions on Machine Learning Research, 2023.
Antonis Vasileiou, Ben Finkelshtein, Floris Geerts, Ron Levie, and Christopher Morris. Covered Forest: Fine-Grained Generalization Analysis of Graph Neural Networks. International Conference on Machine Learning (ICML), 2025.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building Powerful and Equivariant Graph Neural Networks With Structural Passing- In Advances in Neural Informatinn P Processing Systems (NeurIPS), pp. 14143-14155, 2020.
Zhiyang Wang, Juan Cervino, and Alejandro Ribeiro. Manifold Perspective on the Statistical Generalization of Graph Neural Networks. arXiv preprint arXiv:2406.05222 2024.
Boris Weisfeiler and A. A. Lehman. A Reduction of Graph to a Canonical Form and an Algebra Arising During This Reduction. Vauchno-Technichene
Informatsia, pp. 12-16, 1968.
Pascal Welke, Maximilian Thiessen, Fabian Jogl, and Thomas Gärtner. Expectation-Compler Graph Representations with Homomorphisms. In International Conference on Machine Learning (ICML), pp. 36910-36925, 2023.
Asiri Wijesinghe and Qing Wang. A New Perspective on "How Graph Neural Networks Go Beyond Weisfeiler-Lehmann." In International Conference Learning Representations (ICLR), 2022.
Huan Xu and Shie Mannor. Robustness and generalization. Machine Learning, 86(3):391 12.3911-23,,0 2012.
14

---

Published as a conference paper at ICLR 2026
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful Are Graph Neural Networks? In International Conference on Learning Representations (ICLR), 2019.
Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, Chao Chen, and Yusu Wang. Cycle Invariant Positional Encoding for Graph Representation Learning. In Learning on Graphs Conference. PMLR, 2024.
Jiaxuan You, Jonathan M. Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-Aware Graph Neural Networks, AAAI Conference on Artificial Intelligence (AAAI), pp. 10737-10745, 2021.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the Expressive Power of GNNs via Graph Biconnectivity. In The Eleventh International Conference Learning Representations (ICLR), 2023.
Bohang Zhang, Jingehu Gai, Yiheng Du, Qiwei Ye, Di Hc, and Liwei Wang. Beyond Weisfeiler- Lehman: A quantitative framework for GNN expressiveness. In International Conference on Learning Representations (ICLR), 2024.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding Deep Learning Requires Rethinking Generalization. International Conference on Learning Representations (ICLR), 2017.
Markus Zopf. 1-WL Expressiveness Is (Almost) All You Need. In International Joint Conference Neural Networks (IJCNN), 2022.
15

---

Published as a conference paper at ICLR 2026
NOTATION
(MLP) classifier
G
graph G (V,E)
G N(e)
The set of all graphs
Neighborhood of vertex v in graph G Feature of node
Te
Frobenius norm Spectral norm
|-
TD
Tree Distance weighted by function w
TMD
Tree Mover's Distance at depth T with weight
Te
Multiset of depth-7 computation trees for graph
P
Prior distribution in PAC-Bayes framework Posterior distribution in PAC-Bayes framework Expected margin loss with margin y Empirical margin loss with margin Y Classifier function (c.g., a MPNN + MLP) Hypothesis space
Q
L
H.
Graph embedding networks (e.g., a MPNN)
Final classifer (e.g., MLP)
Pr(-)
Probability function
Ger
Training graphs
Gre
Test graphs
TMD (Gu.s Gte)
Distance between Gur and Gte
Nu
Number of training graphs
Nu
Number of test graphs Maximal hidden dimension of classifier func- tion
B
Maximum L of input node features Maximum degree of all graphs in training or test set
a(A)
Depth of MLP f Number of MPNN layers
T
c
Maximum Frobenius norm any learnable weight matrix Number of learnable weight matrices in hypoth- esis space
D
g(()
Message function in layer t
f(
Update function in layer è
16

---

Published as a conference paper at ICLR 2026
A DETAILED RELATED WORK
A.1 EXPRESSIVITY OF GNNS
Expressivity in standard neural networks is often associated with their ability to approximate functions within specific function class. For example, early works showed that MI.Ps approximate any continuous function (Cybenko, 1989. Hornik et al. 1989). In the context of GNNs, however, expressivity is more commonly measured by the ability distinguish between non-isomorphic graphs. This focus stems from computational challenges associated with achieving universality in GNNs and is further supported by the Stone- Weierstrass theorem: a GNN that can distinguish all graphs is also capable of approximating any continuous function on graphs (Chen et al. (209:) Dasoulas et al. 2020). Consequently, practical research often centers on characterizing the distinguishing power of specific GNN architectures (Xu et al. 2019 Morris et al. 2023b).
Xu et al. ): Morris et al. 2019 established that the expressive power of standard MPNNs is
limited by the 1-WL test. To overcome this limitation, later works introduced higher-order GNNs
based on k-WL and its local variants (Maron et al. 2018 Morris et al., 2020b; Geerts & Reutter
2022). These models are theoretically universal (Maron et al. 2019b; Keriven & Peyré 2019).
meaning they can distinguish any non-isomorphic graphs and approximate continuous functions on graphs. However, their expressivity comes the cost of exponential time and space complexity with respect to k; making them impractical for large-scale applications. To reduce this complexity, Morris et al. (2020b); Zhhng et al.] (2024) proposed local k-WI. variants, while Abboud et al. (2022) introduced k-hop GNNs, which expand the receptive field to k-hop neighborhoods. Despite these improvements, the computational complexity of these approaches remains exponential in k.
Subgraph-based models further enhance expressivity by decomposing graphs into subgraphs and aggregating their information (Papp & Wattenhofer [0222] Bevilacqua et al., [02T You al. 202T Frasca et a 2022; Huang et al.] [2022). Although these models are more expressive than 1-WL, their power is bounded by 3-WI. (Frasea et al. [022). Moreover, subgraph GNNs increase computational
complexity significantly, often scaling quadratically or cubically with the number of nodes N, which worsens the computational complexity of standard MPNNs by a factor of N.
Most subgraph- based GNNs associate family of subgraphs with specific nodes or edges by either deleting or marking nodes. However, other strategies for subgraph representation have also been
explored. For instance, Michel et al. (2023): Graziani et al. (2024); Paolino et al. (2024) focus
on paths to enhance expressivity, while Tönshoff et al. (2023 leverage random walks for similar
purposes.
Positional encodings (PEs) and structural encodings (SEs) have emerged as effective strategies to enhance the expressivity of MPNNs. PEs augment node representations with additional information, such as unique node identifiers (Vignac et al. 2020), random features (Abboud et al.) 2021 Sato et al.,
2021). or spectral features like eigenvectors (Lim al. 2022 Maskey al. 2022b). In contrast, SEs enrich MPNNs by embedding structural information about the graph. Examples of SEs include
subgraph counts (Bouritsas et al. 2023) and homomorphism counts (Nguyen & Machara 2020
Barceló et al. 2021: Welke et al.
2023 Jin et al. 22044).
While PEs and SEs enhance the expressivity of MPNNs by modifying the initial node features, another line of research focuses on using computational graphs that differ from the input graph. For Jsstatee,Dmmirov et al. al. (2023) and Bause et al. (2023) propose graph transformations that enable MPNNs to achieve universality for specific classes of graphs, such as (outer-) graphs. More broadly, Jogl et al. (2024) demonstrate that many expressive GNN variants, including k-GNNs and subgraph GNNs, can be simulated by applying suitable graph transformations followed by standard message passing.
While incorporating SEs does not increase the forward- forward-pass complexity of MPNNs, it introduces significant preprocessing overhead. For instance, computing homomorphism counts for graphs with treewidth l requires O (N)) operations, where N is the number of nodes. This preprocessing com- plexity becomes exponential in k; making it computationally prohibitive for achieving expressivity beyond k-WL.
Most prior work evaluates GNN expressivity using the k-WL hierarchy, which provides a qualitative measure of distinguishing power but does not quantify the specific substructures GNN can encode.
17

---

Published as a conference paper at ICLR 2026
To address this gap, Zhang et al. (2024) proposed homomorphism counts a quantitative measure of expressivity. Building on the work of Lovász (1967). they demonstrated that homomorphism counts are complete graph invariant, meaning that two graphs are isomorphic if and only if their homomorphism counts are identical. [Tinhofer (1986) 1991) showed that 1-W1. is equivalent to counting homomorphisms from graphs with treewidth one, while Deel et al. (20T8) extended this to prove that k- WL corresponds to counting homomorphisms from graphs with treewidth k.
Recent studies have further explored the relationship between homomorphism counts and GNN expressivity. For example, Barceló et al. (2021) showed that MPNNs augmented with homomorphism counts as initial node features can count homomorphisms of trees augmented with the included patterns. Similarly, Paolino et al. (2024) demonstrated that MPNNs enriched with specific path information can count homomorphisms cactus graphs.
A.2 GENERALIZATION BOUNDS FOR GNNS
The generalization capabilities of Graph Neural Networks (GNNs) have been studied from various theoretical perspectives. Scarselli et al. (2018) provided an early understanding of GNN capacity by deriving generalization bounds for implicitly defined GNNs based on their VC-dimension. Building on this, Du et al. (2019) analyzed the generalization behavior of GNNs in the infinite-widht limit using the Graph Neural Tangent Kernel (GNTK), offering insights into their asymptotic performance as network width grows unbounded.
Focusing on data-dependent approaches, Garg et al. (2020) and Liao et al. (202I) investigated the generalization properties of specific MPNNs with sum aggregation. By employing Rademacher com- plexity and PAC-Bayes methods, they established bounds that depend the observed training data, shedding light on how factors like data distribution and architectural choices influence generalization.
Levie 2024) introduced the graphon-signal cut distance, metric for measuring similarity between graph-signal distributions, and demonstrated that MPNNs are Lipschitz-contimuuus with respect to this distance. This insight enabled the derivation of generalization bounds for MPNNs in the context of arbitrary graph-signal distributions. However, these bounds exhibit slow convergence rate of (11/ log log( generality of their assumptions, which accommodate highly flexible graph-signal distributions.
log(vm) /m)). where is the number of training graphs. This slow rate arises from the
The connection between GNN expressivity and generalization was further explored by MMorri et al.) (2023)), who showed that the number of graphs distinguishable by the 1-WI. test is directly linked to VC-dimension of GNNs. This result highlights the role of the Weisfeiler-Lehman hierarchy in understanding both the combinatorial expressivity and theoretical capacity of GNNs. In the restricted setting of linear separability, margin-base based bounds have been proposed to partially bridge theory and practice (Franks et al. 2024), yet our broader understanding of how expressivity influences generalization remains incomplete.
Li cietal al. (2225) provide novel perspective on the generalization behavior of graph neural networks by decoupling the representation learning component from the classification step. Their framework considers fixed graph encoders such MPNNs, W-W homomorphism-bane based modelsswhiel map graphs into an embedding space. A separate, typically parametric, classifier (e.g.. a softmax- based MLP) is then applied these embeddings. This setting allows for focused study of the generalization ability of classifiers conditioned on precomputed graph representations, shifting attention away from the learning dynamics of the GNN and toward the geometry and concentration properties of the induced embedding distributions.
Their analysis formalizes how generalization depends on two key factors: intra-class concentration. i..., how tightly embeddings from the same class cluster, and inter-class separation. i.e., how well embeddings of different classes are separated. These are quantified using the W-Wasserstein dis- tance between class-conditional embedding distributions. The main theoretical result establishes a generalization bound on the classifier's margin loss, showing can be upper-bounded in terms of these geometric quantities. Importantly, the bound incorporates the expressivity of the graph encoder through a Lipschitz constant that quantifies how much the embedding distribution a more expressive encoder (bounding in distinguishing power) can distort the geometry of a less expressive one (that is used for calculating the graph embeddings). This captures how changes in expressivity influence intra-class concentration and inter-class separation, and thus directly affect generalization.
expressivy
18

---

Published as a conference paper at ICLR 2026
Although the results elegantly characterize the trade-off between expressivity and generalization, a central limitation is that the graph encoders are fixed. They are fixed feature extractors, often derived from CRAs fixed GNN architectures. As such, the framework does not directly reflect the behavior of trainable GNNs in practical deep learning pipelines, where representation learning and classifier fitting tightly coupled. Additionally, in contrast our correlation- baadd analysis, the generalization bounds in Li et al. (2025) require the existence of a fixed positive margin, which is strong assumption that may not hold in practice. Our framework is more general, as does not rely on margin separability and can quantify generalization even in the presence of label noise or overlapping classes. Nonetheless, the insights are valuable: they reveal conditions under which more expressive encoders can improve generalizaioonssecffillll concentration without excessively harming inter-class separation. In this way, the paper offers a principled theoretical basis for interpreting empirical phenomena observed in GNN performance across datasets and model classes.
when expressivity increases intra-class
Related to our work, Maskey al. (2022a 2025) analyzed scenarios where graph labels are correlated with random graph models, based on graphons. They demonstrated that MPNNs generalize better as the size of the sampled graphs increases, since the statistical properties of larger graphs more closely approximate those of the underlying random graph models.
The approach by Maskey al. (2022a 2025) is limited because it assumes labels are linked to random graph models, where many specific assumptions are made about the underlying graphon governing the data. These assumptions may not hold in practical scenarios, making their results less general and potentially less applicable to real-world tasks. In contrast, our framework accommodates arbitrary correlations between graph labels and structural features, as long as they can be described by a Lipschitz-continun a wide variety of graph datasets, including those where the graph generation process not well understood or where random graph model assumptions are too restrictive.
distribution. This broader scope makes our method suitable for analyzing
The work most closely related to ours is (Ma al. 202I). which studies generalization in a semi- supervised node classification setting. Their analysis considers a scenario where node labels are correlated with features derived from the node's local neighborhood and its attributes. Using a PAC-Bayes approach that heavily inspired our work, they show that generalization improves when the extracted features are similar between the training and test sets. However, their framework is limited by the assumption of fixed, non-learnable graph encoder, and their results do not generalize to mulli-graphe settings or models with learnable parameters.
In contrast, our approach provides general framework to analyze GNN generalization in settings where graph labels are correlated with structural features. This is achieved by introducing a pseu- dometric, such the Tree Mover's Distance, which captures structural differences between graphs. Unlike prior works, our framework does not rely on restrictive assumptions about the underlying graph distribution. Instead, we assume only that the labels are generated by Lipschitz-contnnouus probability distribution with respect to the pseudometric. This allows us to analyze a broad range of tasks where the graph structure plays a critical role determining labels. By explicitly comnecting generalization bounds to structural alignment between training and test graphs, our framework offers a flexible and robust method to study GNN performance in diverse applications.
Our framework overcomes these limitations by supporting learnable GNN architectures and extending naturally to multi-graph settings. This allows for broader analysis of generalization, including GNNs beyond 1-WL expressivity. Moreover, our approach bridges the gap between theory and practice by providing insights into how the interplay between model capacity, structural similarity, and feature alignment affects performance.
B SIMULATABLE COLOR REFINE ALGORIHTM
possible to represent many different GNNs as MPNNs without loss in expressivity. For this, Jogl et al. (2024) developed the concept of simulation. Intuitively, a GNN with t >> 0 layers can be simulated if we can map its input domain to the set of graphs and achieve the same expressivity with a (-layer MPNN on this adapted set of graphs. To generalize to different types of GNNs, one represents GNNs @ as color refinement functions that iteratively refine a coloring on some relational structure X.
19

---

Published as a conference paper at ICLR 2026
Definition B.1. Let á be color update function. Let R be mapping from the domain of the set of graphs We consider two arbitrary relational structures from the domain of Ø, say X and X'. We say can be strongly simulated under R if for every 2 i holds that WL' (L(()( = WL' (X(X)) implies that (0(x)= = (X')..
As an example, consider 3-WL from Section C.3 It can be seen as a color update function c that operates on set of labeled 3-tuples, i.c., iteration > 0 it refines the coloring of tuple (U1, 22 23) E 3 by utilizing the coloring c(t-1);
HASH
( (IL.Va)s)) (ff 02 Uz)) Uy))...., C.. ((11. U2, va)))
(21:92:05)
where
C (1) ((11, U22 Uz)) = HASH He (o (w))2,a))
w vV))
C (111 U2, 03)) = HASH
[1 (1-1)
1 (VE))
C ((V1, U2 03)) = HASH
w E VJ)
Instead of using 3-WL, we can create the graph G with vertices (0), V2, 03) E v and three types of edges
F1 U2, (((11, 12, 1z), (1e, 02, 03)} w V),
F2 Uo (((11, U2 03); (01, w. 03)) w V}, U2, w)} w E V..
Eg = Uo {[(1), U2 0z), (0), 12
Observe, that for a tuple (vi, 02 V3) the neighborhood Ej contains exactly those tuples as aggregated in the definition of Cy. We merge these three edge sets E₁. E2, E3 into single edge set E by using edge features that encode from which of the three sets the edge originates. Such transformation R allows for the strong simulation of 3-WL.
B. OTHER STRONGLY TURONGLY-SIMULAAE SIMULATABLE ARCHITECTURES
A GNN/WL variant is strongly simulated when there exists structure-to sooocturr--t-graph encoding R such that applying R to the input and running a depth-t MPNN reproduces-layy by layer- the colors (or hidden states) produced by the original depth-t model (Definition [B.]] J some architectures that admit such a simulation and sketches the key transformation behind R; full proofs in oogl et al. 2024).
C TREE MOVER'S S DISTANCE
We summarize some important results from BoomChuang& & Jegelka (2022) and Davidson Dym (2025). We first start with the definition of the tree mover's s distance which provides us with a tool to compare two graphs based on their computational trees quantitatively.
C.I TREE MOVER'S S DISTANCE
The definition and notations in this section largely follow (Chuang & Jegelka 2022).
Definition C.I. Let G (V, E) be a graph. We define the depth-T computational tree T of node recursively by connecting the neighbors of the leaf nodes of T to the tree. We set T. = v as the single node tree without any edges. The multiset of depth-T computation trees defined by G is denoted by T = {[T Hrevv. Additionally, for tree T with root we denote by T, the multiset of subtrees that root at the descendants of
In other words, the depth-T' computational T. of node v the I-WL computational tree of node e after T' - iterations. To compare two multisets of computational trees we need to augments trees.
Jogl al. 2024 introduces some additional restrictions on that we omit for the sake of simplicity.
20

---

Published as a conference paper at ICLR 2026
Table 3: GNN families whose per-layer updates can be exactly reproduced by a I-WL-equivalent MPNN on the transformed graph R(G).
Model Algorithu
Graph transformation R(G)
VVC-GNN Sate ct 2019
For given port ordering. write on each edge direction the port the source and target node.
k-WL/ K-GNN
Morris all
2019
Compute all k-tuples of nodes. Create node for each l-tuple and encode the isemorphissm class of each tuple as mode fenture. Connect tuples differing in one position encoding this postion edge feature.
5-L-LLIWL / GNN Morris ct al.
Similar as the k-tuple graph above: when connecting tuples add local/global flag encoding whether nodes that ditter
20206
edge in original graph. 6-R-LWL. only connect tuples when these nodes de form an edge. Similar as 5-k-WL above: keep only tuple-vertices whose induced subgraph has S a components.
tuple
[k.6)-LWL
SpegNet Morris
< al. 2022
GSN 2 GSN.v Bouritsas et al.
For pre computed subgraph pattern counts, augment original mode and edge features with these counts.
2023
DS-WI
DS-GNN Bevilacqua
For given policy it to geacrate subgraphs, create a graph by taking the disjoiat union of all extracted subgraphs (G).
2021
k K WL
OSAN Qian al.
For each & tuple of vertices in the graph ("k ordered subgraphs"), "), create a copy of all vertices in the original graph use node features encode atomic type of node this ordered subgraph. In each subgraph, either link all vertices only neighhors in the original graph.
MI-GNN
Papp Wattenhofer
For given of marked nodes, each edge encode whether the target node is marked unmarked.
2022
Wijesinghe & Wang 2022
or edge featurrss. encade feature that edge.
Atlach structural cueflicients
Shortest Path Nets (Ahhoud et al.
For i E 1,... & add an edge between pair of nodes with shortest path distance and
2022
Geberalised-Da Soodraliid-Distance WL Zhang
For given distance metric d and graph G. add edge between every pair of nodes
c5 al.
2023
and encode the metric (u, u) as feature on this edge.
Definition C.2. A blank tree To is defined as tree graph that contains a single node and no edge,
where the node feature is the zero vector Op E RP. We define T5 as the multiset of n blank trees. Definition C.3. Let To, Tu be two multisets of trees. We define p as function that augments pair of trees with blank trees as follows:
p: (Te, Tw) + To UT Tv U 177000007711111111000
(5)
Definition C.4. Let N + IR+ be depth-dependent weighting function. For two trees Tap To. we define the tree distance TD (Ta, Tb) between Ta and TV recursively as
TD (Ta, Tb) = | 2n.1 + wT) OTTD, (p(Ta,
if
(6)
x where T max (Depth(T.)) Depth((T)))
|
otherwise,
We note that the optimal transport OT with respect to some metric between two multisets x {[2 [(21...., } and y f(y...... yn}} of the same size defined via
OT (x = min Σ (o()))
Definition C.5. Let G, E G. w : + and 2 0. The tree mover's distance between G and H is defined as
TMD au (G, H) = OTTD.. (p(Ta) (H)),
(8)
where Te and Tff multisets of the depth-T computation trees of graphs G and H, respectively.
We note that, for simplicity, we omit the weighting function w the corresponding subscript in the definition of TMD and simply write TMD" in the main part of this manuscript.
C.2 PROOFS IN SECTION 3
Theorem 6), TMD', in is a pseudometric. It is easy to that (-TMD is also pseudometric. Given G, H G, we have
Proof of Proposition 3.2
By (Chuang & Jegelka
2022
(TTMD HI)
TMD (5), (TM( (()))
(9)
= =CTMMD(H, G),
21

---

Published as a conference paper at ICLR 2026
showing the symmetry of Ç-TMD
Proof of Proposition 3.3 By (Chuang & Jegelka 2022 Theorem 7), two graphs G' and H' are determined be non-isomorphie in WL iteration 7 and w(t) > for all < t S T + then TMD*++ H² > 0.
If Ç distinguishes and H after T iterations, then WL. determines RG( and R$ (H) to be non- isomorphic, i.e., ( (S)) > 0. Then,
Ç-TMD (G, 0.
We reformulate and prove more general version of Theorem 3.4 where we consider general message functions on multisets that are Lipschitz continuous on the multiset domain, and update function that are Lipschitz on the standard Euclidean latent space. This follows the approach (Davidson & Dym 2025). where similar version was proved in Theorem F.2. in their manuscript. However, in contrast, we calculate the explicit constant of the Lipschitz constant which we will need for later proofs.
Theorem 3.4 then follows as a corollary as permutations-invariie aggregation functions composed of a MLP followed by sum aggregation are Lipschitz continuous on multisets.
Lemma C.6. Consider a MPNN of form
x = (I! (2
(HueN()))
(10)
with message and s functions ((0)) 1-11 Consider also a global readous function of the form
((0)
M(G)= = (1x
Suppose that for allt=1.... T, the message and update functions are Lipschitz continuous with Lipschitz constants bounded by g and L respectively. Suppose that the readout function is Lipschitz continuous with Lipschitz constants bounded by Le- Then, for all layers = 1...., and for all pairs of graphs G, H E & and all pairs of nodes u E (V) and E (HH, we have
|0:00 - =c00|=
II ===
L Leeer
2'TD (I((+1), (((+)))))))
(11)
For the global output, we have
T
[[h(G) - h(H) $ Le
II L Let
2 TTMDD-+1 (G, H)
(12)
Proof. Without loss of generality, suppose that Lic, Lyto 2 1. We show Equation For t = 0 Equation (TT) holds trivially.
by induction.
Step 1: Bound the difference between message function outputs.
|1000 (1z! ((a((-""))senc" (0)) (Ita! (H**5-"))een "DeeNww)l
00 WD1H-1
(((2((11))) bift-)) (1-1)
Lygo min
Σ
7(*)
TES.
$ c0 Σ
x
(13)
[-1 II
Lgg
L
2--1 Σ TD (T:0) T()
1-1
Lgws
I Lycer L Li
2r 2 (1IT!") (TT!HH)NN..)
22

---

Published as a conference paper at ICLR 2026
where 7" is the optimal permutation in the definition of WD1D (HIT.) HSEEOY (I
HrEN(W)
Step 2: Bound the difference between update function outputs.
1 - x
= =1(000 (t) [[t, (----111
"oo""HBoo HaeNrws) f(()
(e (Ha Beel-DDrrea "ieev()))
(0(0-1) - -x! 1 + 11000 (((x!--1) HoEN g00 (
(-1
$ Lyc
[|af-1)- -1!h Lyte)
II
L gier L 2 2 (1IT!" H1T22 NweN(w)
Wil
(
L lpeer lpterr (ilLger
S Lyy
2"-ITD (ITO, IT!))
(==l
A-1 Loe
22-1WDID (11T)" (1T (il BreN(w)
+ Lg00
ygter bigeer
2'TD (T(+)))
(14)
This finishes the proof of the first claim.
Step 3: Bound the different between global outputs. The second claim follows by calculating,
[|h(G) h(H))l | (a.")))rrra)
c (1(x Hoevia))
S WD
(t (T) ((x"""))evo)) Hevv()))
min
Σ |
7()
(T)
(15)
T
Th
II
T. ggu Tigars
2 Σ TD (((T+1), T(T+1))
W=1
T
Le
II #=1
L gee Lisss
2 TTMMDT+ (G,
where 7* is the optimal permutation in the definition of TMD T+1 (G,
We now consider the case where Lipschitz continuous functions multisets implemented via sum aggregation, followed by Lipschitz continuous functions on the Euclidean domain. This includes scenarios where the message. update, and readout functions are MLPs with Lipschitz continuous activation functions, such as ReLU.
Corollary C.7. Consider a MPNN of the form
(I.00) (1.0))
(t+1) = ((+11)
(0) Σ ((++))
nEA(w)
with message and update functions f()) f(1) T form
1= Consider also a global readout function of the
h(G) =
Σ (((T)
vEV(G)
23

---

Published as a conference paper at ICLR 2026
Suppose that for all = 1..... T, the message and update functions are Lipschitz continuous with Lipschitz constants bounded by gg and L respectively. Suppose that the readout function is Lipschitz continuous with Lipschitz constants bounded by Le. Then. for all layers t = 0, ......TT and for all pairs of graphs G, H E 9 and all pairs of nodes u E (V) and E (HH), we have
| - 2
II r'==
L Leees
2'TD (T((+1), (((t1)I(++))) I((+1)).
(16)
For the global output, we have
[[M(G) - M(G) & Le II L g0o ges 2TTMDD++ (G, H).
Proof. This follows directly from Lemma C.6, since for any Lipschitz continuous function f with Lipschitz constant L,, the induced multiset function f X + ExEx f(x remains Lipschitz continuous with Lipschitz constant bounded by L.g.
Theorem C.8. Let S be a strongly simulatable CRA, and let h 9 1--4 + IR be a C-MPNN with T layers, where the message and update functions are Lipschitz continuous with Lipschitz constants bounded by Ligee and fes, respectively. Suppose h includes global sum pooling layer followed by a Lipschitz continuous classifier with Lipschitz constant Le. Then, for any graphs G and H,
[M(G) h(H))l S T. I.. D.G-TMDD* H),
where L = Lc2 II Liv Lgw.
Proof. Let 1 be the underlying MPNN of h. The proof of theorem follows from Corollary C.7 by
[|([G) b(G))( =Ilh (IE(G))
h1 (H))
T
S Le
II
Loier Lytcs)
TTD (G),
T
= Le
Ly(er Let))
2 3"<CTTDD++ (G,H).
C.3 EXAMPLE II: k-GNNS
The Weisfeiler-Leman (k- WL) test enhances the expressive power of the 1-WL test by considering interactions between k-tuples of nodes. To strongly simulate k- k-WL, product graph G is con- structed, where each node represents k-tuple of nodes from the original graph G, and edges are defined based the adjacency relationships in G.
Similarly, k-MPNNs operate directly on the product graph G achieving the same level expres- sivity the k-WL.
Corollary C.9. Let h be an k-MPNN with T layers. Then, there exists a constant L such that for any graphs and H,
[[([G) (((H)) s L. (G,
(17)
D GRAPH CLASSIFICATION SETTING
We consider classification problem with K classes over fixed set of training graphs Gur and test graphs G.e. Each graph G is equipped with node features x, and we assume there exists a constant B 0 such that | < B for every node V(G) and every G E Gue U Gte. Let N,, Guul and No, 1 Each graph G has label y sampled from an unknown distribution p. Moreover, likely share the same label.
assume that graphs closer in given pseudometric pm
24

---

Published as a conference paper at ICLR 2026
Concretely, for each class &o E {I....,Ay K), there is Lipschitz continuous function The (with respect to some pseudometric pm) such that
Pr(y -ly=k|G]
(G)
and we denote by C = maxg Lip(n)) the maximum Lipschitz constant among all {mk Let be an upper bound on the distance (with respect to pm) between any training graph in Sur and any test graph in Pie-
We now introduce a PAC-Bayes framework to derive a generalization bound for classifiers under this setting. We consider two different setups for learning graphs:
1. C-MPNNs: Let Ç be a strongly simulatable color-refinement algorithm (see Definition B.1 A Ç-MPNN has fixed depth T and a final MLP e as the classifier. Each layer f e (I,...,7) ,T} has message and update functions denoted by g( and ( each with fixed depths (()()) and d(f(t)), respectively. The corresponding weight matrices are written (wo(g(0, )))a(a")) ") and (w(s(0, ()))=
=))) The final MLP classifier has parameters {uo(e, dfe) Define b to be the maximum hidden dimension across these modules, and let Hg be the class of all such (-MPNN classifiers.
2. MLPs non- non-learnable graph embeddings: Here, the final MLP classifier has the same notations for its parameters as above, and we denote the hypothesis set by Haatent-
We assume that all non-linearities in the MLPs Lipschitz continuous and homogeneous.
Finally, we adapt the following assumption from Ma al. 20211)
Assumption D.1 (Assumption on Concentrated Expected Loss Difference.). Let P be a distribution over H. obtained by sampling D (vectorized) trainable weight matrices from (00, of1), with
(7/(8E)) 2/D
o² S 2 + In(2bD))
For any classifier h E H. with model parameters {wj}}. define Tn == max //yll/llll Assume there exists an 0 < such that
Pram p (cre (t) 211 No + CKE TP 3) N20.
This assumption posits that when the model parameters sampled from P do not exceed a certain norm threshold (i.e., T & S } and the number of training samples Nrr is sufficiently large, then the expected margin loss on the test set will not exceed that on the training set by more than N + cKg. Informally, once the training set grows large enough (and model weights are not too large), the test performance cannot deviate significantly from the training performance. This property becomes trivially true if all samples in Ger and Gie are i..dd since CT/2 CT/ < 0 in that case.
E PROOFS OF THE RESULTS SECTION
In this section, we provide detailed proof's of the theoretical results presented in the Section
note that the proof of Theorem 4. follows the proof of Theorem in (Ma et al., 2021), carefully adapted for graph classification tasks and learnable graph encoders.
Specifically, the proof leverages the PAC-Bayes framework, properties of the chosen pseudometric, and structural constraints on the hypothesis space. For clarity, we decompose into series of steps, each contributing to the final result.
In Appendix E. we present intermediate results that are independent of the choice of pseudometric and hypothesis space. To emphasize this generality, we denote the pseudometric by pm and the hypothesis space by H. This ensures that the results in Appendix E. Jappy regardless of whether the pscudometric is defined in the graph space or latent space, and whether the classifier an end-to- end learnable GNN deterministic graph encoder followed by learnable MI. classifier. This
25

---

Published as a conference paper at ICLR 2026
approach allows us establish in Appendix E.2 the generalization bound for end-to-end learnable GNNs, and the following subsection, the bound for graph classifiers with fixed encoders- derived from the results in Appendix E.1
We note that pm defined on G, the corresponding classifier h: G - + (I......K) is assumed to be Lipschitz with respect pm. If instead pm is defined R the classifier h R {1,.... K). typically an MLP, assumed to be Lipschitz with respect to pm. In the latter case, classification is performed via h e(G), where e + R is deterministic graph embedding network.
E. PRELIMINARIES FOR THE PROOFS IN SECTION
Step 1: Deterministic Bound via PAC-Bayes. We begin by establishing deterministic bound on the test loss in terms of the training loss and the Kullback-Leinn (KL) divergence between the posterior and prior distributions over the hypothesis space H.
H. be any classifier and let P be a prior distribution on independent of the training data. For any X 0 and y 2 0, with probability at least - 8 over the training sample yu. for any posterior distribution Q on H satisfying
Lemma E.1. Let
Ph- max GEEHL
[|h(G) - -(G) < 8 -/
the following bound holds:
clo(h) < (h) x (Dkk)(Q1P))+)) +1) +
X2
+D? DieleliN)))
+ +2//
(18)
4N
where D2/2 ( (P;)) In Enpr exp (2 (F26 -2) (1))
Proof of Lemmal E.1
The proof adapts Theorem from Ma et al. (021) from the node the graph classification setting. We present the proof for completeness.
First, define subset Hig C H as:
H₁ = h NEHI
71 $8 [MGG] S
max GEGU
(19)
Using this subset Hg, define the modified distribution Q' over Hj, as:
('(h) Pn-- ( Q(h), if Hz.
(20)
0, otherwise.
We aim to show
cie(h) < c2( and 2T! s (T).
(21)
The first inequality holds since
(ha(h) L2/3 (h)
Clo (h)( - E (m)
[
0 0+ max To(G.) ]]
-Eynntiyics,ciee..
Ni GLEGen
kzya,
M(G:)
7/4 max (G.)([
Nie GLEGue
kfta;
max T(G))Kk) ]
1 h(G.))ba)) 0+
No G.eG.o
26

---

Published as a conference paper at ICLR 2026
-1
S (7/4+ MG.)lul
max M(G)) [b]
}
kyyG.
i.e. it remains to show that if ((G & (0 maxk/va, (G)((1)) holds, then also hG::)(y))) 2 (7/4 + max hkG.))k)). This is clear by Equation 19
A(G.)ll S 1//8 h(G.)uul
1 < + max h(G:)[A)
kaya;
1 4//4 max h[.
RAVO
Similarly, prove the second inequality in Equation 21
Therefore, with probability at least over the samples Mtr. we get
(h) < En-oy (76 (1)
(1)) $ Bn-q ( (1)+ + (KI.(0'1P))
In
1
+ Dich(PP:))
4N
s (h) 1 (DKL(0)1P)) + In 4N
1
2
+D (ilth(P:s)
+
The second inequality applies Theorem 1 from Ma et al. (202T), while the first and last inequalities follow directly from (11 and the definitions of Hij and Q The remaining steps align with the proof of Theorem 2 from Ma et al. (202I.
Step 2: Bounding the discrepancy term. Next in Step we will bound the term D (P: A) from Equation (88 in Lemma E.I which captures the difference in expected losses between the test and training distributions under the prior P. We begin by bounding C//² (h) f. (h) in this step.
Lemma E.2. Let h E H. be any classifier with Lipschitz constant L with respect to the pseudometric pm. For any y if LE < 3. then
(712(1) CT,(h) S CKE,
where K is the number of classes and C is the maximum Lipschitz constant of the functions me--
Proof of Lemma
E.2 We
L7 (G, =1
[O] < max h(G)(K key
where [K] denotes the output score for class k.
27

---

Published as a conference paper at ICLR 2026
Then, write (422(1)) L.,(0) (1)
Byyt
Σ G5ESto
1 L2/2 (G,,
-Eyle
Σ
f* Vi.
Noc
Ntr
GiESu
Σ
Th (C)
mhe (G:) (G
Noo GyESia
Nw GLED.
k=1
11 E Noo Nur
E
E Th (G,,))
Nur No Σ Gy GrEg.
E
K Σ
G.Ege GyEgun
Σ
(G
Ni
G.E9e GyEgen
1
Σ
Σ
NI
G.E9 GyE9cn
+ +Tm(G)
Th (G)
Σ Σ
Σ
Σ mn()) ( L (m(())))))))))))) mG.)))
No
GrEat G, EGe k=1
1
EE
( LG ( (G.))-
Nor
G.E9 G,E0ra
(22)
The last inequality holds since 2 and m7 are bounded by 1. We have, by assumption on the probability distribution,
(),) (G.) CC pm (Gj, G.) S Cg.
(23)
Furthermore, by assumption,
| - (G; S L. pm (G,, Gi) s LE 7
(24)
Then, for any K.
CT (b(G,)) S C (N(G.),
(25)
This is true since both L1/2 (h(G,), k) and L (k(G.),k) are O-1-valued. IF L3/2 (h(G)), k) we have by Equation (24
h(G.)[k] S 7/44+ [(;)
< + 7/2 + max h(G I.....,KK K
5 < + 7/2 + + max A(G)([] EII...KK
= ? + max h(G)))1)
I....,K K
ie.. LT (h(G.), k) = 1 as well. Finally, we continue with the calculation in Equation 22
(12 - (1) < 1
Σ E Σ
(G)))) + (nx(G))) - mh (G.))
Nee
G.EGv Gr km
<
Nu G.EGor
Nue CyEtrokml
= -CKE,
(26)
28

---

Published as a conference paper at ICLR 2026
where the second inequality holds by Equation (23 and Equation 25
Step Bounding the discrepancy term Di (P:
Lemma E.3. Let O. For any 0 < X S 2 and O, assume the "prior" P Pnn H. is defined by sampling the vectorized trainable weight matrices from (00,0 for some o² S 26(AN 2bD)bD) We have
(7/88))80
D1 S In3 ACKE,
(27)
where Di = In En (M))(()))
Proof. First, set Tı = max,=1..... || 112- We prove this lemma by partitioning into two events: one with high probability, where the spectral norms of the model parameters satisfy the conditions in Lemma E.2 and its complement. For the latter event, we use Assumption D.
For any 1,..., D, we have, by (rrpp 2015), for any 0,
Pr (1llwyl S 2bc 2bo
7 I/D
where b is the maximum width of all hidden layers of the considered classifier. We set t Applying a union bound leads to
88
Pr T 8) 2)= = Pr Th
7
1/D
2bDe
(t/lae22/D 2/D
S e -ANi
(28)
8E
(//8))2/D
where the last inequality uses the condition σ²
26( +In 26D)
we have > (1) (7)))/
For any h satisfying T S g. by Lemma E.2
S cAOKE
The complement event, i.., T.P occurs with probability at most e " We decompose D2/2 (P; A) follows,
D2/2 (P; In Enppe (ct/ (1)
Pr TPPS 2) ACKE + Pr (TRE> 2) EE ( (1))/1)))
$ In
ACKE + t ANT BI -EL2
< In
ACKE + e ANT" (e-Nir _ + +1-11-11 (1- edoi (sCkE)
< In
In (CCKE& + C--N - -NN + te ~NN=" ((1-e-vay) - (2NN
In (OCKS + t Noo
N-N -NNT- + ((1-e-M) eACCE))
< In AKKE +1)
In3+ ACKE.
(29)
The first inequality holds by decomposing the domain over the expectation/integral into the event in which T < holds and its complement. The second inequality holds by Pr (T,P5 7) <
and Equation 28 The third inequality holds by Assumption D.I The second-to-last inequality holds by the assumption < A E 22o, The remaining equations and inequalities are algebraic reformulations.
29

---

Published as a conference paper at ICLR 2026
E.2 PROOF OF THEOREM 4.1
We first present auxiliary results for the proof of Theorem 4.1 end-to-end learnable. At the end of this chapter, we provide the full proof of Theorem 4.1 building on the results from this and the previous section. For simplicity, we derive the results for MPNNs; the corresponding results for Ç-MPNNs applied to graph G follow by applying the derived results for standard MPNNs to the strong simulation Ç. Let denote the hypothesis space MPNNS by Hmpon- where the parameters follow the assumptions in Theorem 4.1
focusing MPNNs, which may be
Step 4: MPNNS are stable under weight pertubations. We proceed by proving the following result that shows that MPNNs are stable under small pertubations of their weights.
Lemma E.4. Let h be any classifier in Hmpmn with learnable weight matrices w (w(s s
Di ; " {w(e, s) and 3 O. Let Ga,a be the set of graphs
with maximum degree d and input node features in ball of radius B. Then,
max [Aw+u(G) (w) (G)
GEGB,
d(e) [w[e s)[l2
((((0e12)) II
(1 (1+ d( II Iw(o .sll)) B
dlg ((ghte12)
II
(w(r(ttt),,)) ,)]1
T-1
|u(g (1())(+t)) 8)
| 8)
[10g((+11) (g((g(((+),,,
l(((f(t(),s))
t=0
(30)
Proof. We denote by Ia the representation of node v after & layers of the MPNN h with standard weights and a!! is the representation of node u after / layers of the MPNN h with perturbed weights w + u. We similarly define the message terms m. and mi We further define
6,+1 = max [(++)) x ((+1))
We calculate
8, = max
((+1)
x ((+1)
((tt)) (o10 m m((+1)) (x(t)) my (+11))
max
Juru (a(0) m ((+1)) s((t1) (a) m [
+ sutu (a m (1+1))) - (((+1) (1) m (2+1))
(A) + (B).
where o² is the node where the maximum is taken.
Bound (A). We begin by bounding the first term (A). It holds
(A) < (((())))
(5((]) - x(()
||
+ ! - ml())
< L( (lttt)
8 +
Σ
(++1) (5 - g
(++1) (x (1)
(31)
kEN(1)
< T (((2)))
8,
max (N(
butt (z((1)) (= - g (++ (c= (1) (1)0)1))
30

---

Published as a conference paper at ICLR 2026
We calculate,
11 (-!!)) - Ii (x!!))
S 11 (I
Iwtu (1 1ottt (c
(xx?))
x 1 1++T D
die ((g
ENN(1) | 2
looy (10()((t)) ,]]l
max
|| Σ
|u[g (t(g) m]]l
|xo(g(t11),s) 8)
(32)
((gtttt a' (N)
max
Hence,
be + d (1+ 1 d(g())))
[|((g(et1), 8]ll
(A) S L(FWF))
II (1( []]]
||=:0011 Σ
D)
[[((((+11, .8]
L(gutu (1 )ot
(33)
Bound (B). We continue by bounding the first term (B). holds
1 d(p(t12))
|u (u(rat)),cc b)]l
(B) S 1 +
II Mam p(tt)) s))1
(1=:991 (m
Σ
D
1 ((tt))))) s)ll
(34)
Together, we have
[+ 1 d(oatt))
| (+(g(++1), s))l
5e41 S I(fl(41)
8 +
II | [1o(g)tt2) |]]l ||
Σ
(gg0041)00 )o:
D
[1o(g(++1), 8)]
+ 1+
1
depietely
II I [ .3]1] (1e250 || + ll 10-
Σ
|u(f((+1),,))
D
((++1)))) 8)
I(((tt))
(1+ (( oz
+ I(1(t22)
d
1 D)
d(g(ett))
II [1w (+1) .011) |1:0011 Σ
||u(g ||)l
[[ |))ه
1 d(p(tt)))
Σ (1+(((+1)). ا]ه
+ 1
II [w( s]]l
(11=59 + (
D
(c+11) s)]l
(35)
We solve this recurrence relation get
8y
II
A Bi,
t=0
Ak=++1
where
A. = L(((+1)) (1 + M(uuth)
(36)
31

---

Published as a conference paper at ICLR 2026
dolint (eglett))
B, ((fattl)) d (1+ 1)
II (
B Σ || | الlه
(( (1+d((e
[[ lل)ه
(37)
afunnn (
+ (1+ b)
II Iw (((((t))),,)) ااll
[ s)]
(1 +lHdL dl(g
II (((()))) (1
B
where
L(F#+2)
II |w((()) s) + u(f( I]]ه
(38)
/d(g(t+)))
L(g(+t1)= =
II [w(( + u(g s)]l
(39)
T-1
and the product
II k=-++11
Aş is taken to be 1 when T (empty product).
Final step. As final step we need to incorporate the MLP classifier after the T message passing layers. For this we calculate,
N
5r+1
(T)
fw
N
N
==1
==1
N
N
((T)
fwtu
10 u
N
N
1=1
w=1
+
f futu
1
(T)
fw
(T)
N
1
+
1
d(f)
(a(f)
II [w(c, s)ll2
8q + (1+ 1)
(())
(d(f)
II
s)1l2
|
a(f)
D
[w(c,))le
<1+ 1+
1 D
d())
(dLf)
II |ule,
s)112
Σ II Ak B.
+ 1+ 1 d()
II I( (1 (1+02(01))
U
| 8)1lz
II [[wc s)
B
_
D
lw(c,))ll
= (C') + (D).
(40)
32

---

Published as a conference paper at ICLR 2026
For the term (O), we calculate
die)
d(e)
T-1
T-1
1 + D
II
[wwc
s)|l
Σ
II As
Bt
1=
k=t+1
1 d(e)
dic)
L(fta (lttt) (1 + U uolttt)) Be
$ 1 ++ D
II [wv[e,))]
L
d(c)
die)
acple122g
=
1 D
II [ulc, s)l
Σ A=1-1
1+ D
lI
| [w((((tt), ,]]1
[ + 1+
D)
d(g
d(gihtti)
a(glat2))
II
(0))))
B.
(41)
For B,, we calculate
dightin Moluurin
B. (ubttt) (a (1+
II ((((
II (V(0)) (1+ ( D Σ ||u(g(+t)) ال]ه
[[(gg(+t)), ا||l
+ (1+ 1 afuttn /alglettn)
II |w ((((tttt)) s))
D
II ((SS)) (1 (1+ )((i6T)) D Σ /u(( |u(((42),8)) [)]
(1+ dL(g 1))
(10((((tt)),
(appstt)
=1+ 1
(I (1 di(ohT)) B
II Iew (e((t(t ,s)]
/d(g(t+1))
|lu(o (tt)( ا]]ه
1 - 11 2
II
11 (10( .))
Σ
|10(g((+1), s)ll
((fpet1))) (
|u( (u(F(tt),, اi)l
d pt1
II
110 (((+)()))))))) s)|l
( (a aageniy
< (1 [1+ 1
II lew ((e()(tt)), ||ll
[ (1 d((l((1))
an (dggectt))
| (f((tt)))) (
II I (1o(((tt)))))11 .0)))
|2(a((+1) 8)ll
|u( |])6
B 1 1+d ( + bb
[]]
lelgit+)), I)]
S <(1+ + } dis +d (ett))
r+1
II ((S((t (1+dTio( B | s)]l
|| ||a(f(tt |i)s
l1)(g((11), s]
1 (((((t)) |]]]
(42)
since L(gh++11) = [[dig" ( [ s) and L(f((-))
= II. ( mnll (|((((++ (f(t+)))s)) .)]|,
respec-
tively.
33

---

Published as a conference paper at ICLR 2026
Together, we get
II Balllll Moneeeerre .1)) (
d(e)
II I plocr (011 (1 +
dig d(a(at3))
(C) s 1 )
II
[o(c
Σ
==
(1 + b)
ai d
u d B.
l s)ll
+ +Σ /u(ffect1),, ال)l
((g(t+1), s)]l
(f((tt)))) ا])ه
1 b) D d(e)
[--1 /d(r(+2)
( ا|]l (1 d d(glht11)
II
lwlc, S]ll2
II
II
II |
B
(ulg(tt)) ا]ll
|lu( |lu(((tt))) ,))l
Σ
[oo I|
[ s)ll
d(e)
(acple+1)
1o (((((tt)), |i)l (1+ d( II u l (1to , B
((g(t++))
e
[wlc, s)ll2
II
II
T-1
(u(a((+)) s)
[ s)ll
[w(g((+1),s) s)
[(oftttt), s]ll
t=0
(43)
where = d(f) + Eimi (d (f(k)) + d (g(+))) Hence,
5T+1 $ (C) + (D)
[(c)
T-1 II k=
[ (w(((tt),s))) .1]l (1 + d II
d(g 1)
e
[,o(c, s]1l2
II
|wwg(t- .s]l) B
(u(g()+1), s)ll
| (u(s()+1),00)
[1(g(++3)) s)ll
[(((((+)))
1=0
+
(1
D
a(n) (a(s)
II
[ww[c, l)|
II (ISsS (1 (102)))))
T
a( | +))1 l12 1il 8) 1|2
((c)
II aagittt km
II ( (1]l] (+ (++ a(
d(g (et
e
[w(c,))ll
II
I ( (.).)) B
(1u((((t1),, s]]l
[ [ ا)]l
|lu(f ll2
(g((((11), I)
+
[wlc s) 1
(44)
We proceed with the following lemma that gives sufficient conditions under which the conditions of Lemma E.I are satisfied.
Step 5: Derive sufficient conditions for Lemma E.1
Lemma E.5. Let h be any classifier in Hmpnn with learnable weight matrices w [ww(fl) s)) (wig((),s))) s))da"")) {w(c, s) sie and 3
> 0. Consider random perturbations
to w given by u = [fu((() ()))) ")) (u(g(o) s)) ")la"""))) ") fu(c, ())[() ). where each perturbation
follows an independent Gaussian distribution NN0 II). Suppose the following conditions hold:
The variance of the perturbation satisfies
5
(45)
eB (3D (30-0Ch 1 d( + dT dT-13D-11 2h In(4Dh)
34

---

Published as a conference paper at ICLR 2026
All weights w w satisfy ||l||| with 13- 3| - B.
Then, with respect to the random draw of
hw-u(G))lo < < 2
Pr
max GE94:U91
[lw(GG)
Proof. By 13 - 3. we get
- -D-1 < 3011 S e-
We can bound the spectral norm of each perturbation matrix E u, by Tropp 2015)) as follows:
Pr ([lul22 t) s 26 ebexp
2bo
where represents the hidden dimension. Applying union bound over all layers, we obtain that with probability least 1/2, the spectral norm of each perturbation is bounded by
/ 2h (4Db).
35

---

Published as a conference paper at ICLR 2026
Substituting this spectral norm bound into Lemma E.4. we have with probability at least 1/2.
[lw+u(G)- - Pow (G)
max GEGT-U9er
d(c)
T-1
(d(f(et)))
(11 + d II (w((g(tt), B
d(ggk+tb)
Se
II k=
II
1 (w((tt+t),s))
(et() 11, I|
| ا]1
d(
| s)ll2
[e(g(e+)) ا]]l
(f(tttt)), l]]l
d(e)
T-1 /dcg(et2) II
a(g
e
w(c, و](ا
II
|ml( f(( 1) .]]l
d
II
|
( .)][BB
|lu(o((+))) II
||u(f((t)) .]]=
d(
| s)ll2
[(((g(())) ال]l
1/0 ((((()))), |]]e
[e, s)|ا2
t=0
d(e)
e
[oo s)1(2
II
II
[ ,)]l sill B
k=
((2)()+1), I)
| .|]l (c((((t))) ,0]
d(
| s)l(2
[(((g((+1)
ا]]
Welc, s)1ا2
a(s)
= -- -I
Σ
( ا]lه + Ellup(ttt)) ا||ه
+ Σ
| 8)(l
1=
s=1
d(s)
((
Σ
Σ [1(g((+t)) +s]1 + Σ llu Ilu(f(tt1) s]]l
+ Σ |lu({,))
a(
2 (T B.
3
Σ (+ ,,),, + Σ (lu(r(ct()) s)]1 + Σ ||([,
a(
+ +0200 d(g (1) 11
Σ [l((g(tt2) ,,)e,,),,s]= + > ( |ل]l
+ Σ
|e(t sلll
1=0
e² (30- d(g()))) + d= ---13--11 130-1) B. Σ
[
())l + Σ | ((((((tt),,))) ,ل]ه
+ Σ |lu[f s]]l
S e² (g))))) + (1-0--1) Bo 2n (4Db)
$ 7
4''
where for the last inequality we used Equation
Step 6: Putting everything together. We finish this section by reformulating and proving Theo- remb 4.1
Theorem E.6. Let h be any classifier in Hmpan with parameters {w.}p For any 7 2 0. 2 1/4 and large enough Nu., with probability at least 5 over the sample of Yer, we have
(h) (h) 50 ( 6 bE 1/
DC D2(BB))
2/D + N2a (7/8)2/D
N2a 112 In 2h
+ CKE
/1/58
N 2a
2a
(46)
36

---

Published as a conference paper at ICLR 2026
Proof. 2021
The proof follows the proof of Theorem 1 in (Neyshabur al. 2018) Theorem 6 in (Ma et al.
There two main steps in the proof. In the first step, for given constant & > 0, first define the "prior" P and the "posterior" Q on H. in a way complying with conditions in Lemmal E. Lemmal E.3 and Lemma E.55 Without loss of generality (due to the homogeneity of the activation function),
can assume that || ll2 = 3 for some 2 0. Then, for all classifiers with parameters satisfying 3
| 3 13 and 3 being some value on predefined grid in the parameters space, we can derive generalization bound by applying Lemma E.1 Lemma
E.3 and Lemma E.5
In the second step, we investigate the number of 3 we need to cover all possible relevant classifier parameters and apply a union bound to get the final bound. The two steps are essentially the same as Neyshabur et al. (2018) with the first step differing by the need for incorporating Lemma E.
Step 1. We begin by showing the first step. Given a choice of 3 independent of the training data, let
(7/8E))/D
? d dr-13D-11) ( In(4D))
= min
22 26 (ANi + In 26D) e²B (
(47)
Assume the "prior" Pon H is defined by sampling the vectorized MLP parameters from (0, o I). 1D
The "posterior" Q on H is defined by first sampling set of random perturbations {u:),-1 and then adding them to {w:)ee By Lemma E.5 we have
Pr
max GEG
(G)((G) - hw) 1000
2
(48)
8
2
Therefore, by applying Lemma E.1
we get with probability at least - 6,
(h) - (h) - x
2 (DkI, +
X2
+
+Dd (P:
1//2
4N
1
X²
< X
2
2
P) +
In
+ (In3 + +In3+ACKE) ACCEE)
(49)
4Nu
2
1
2 In3
$ DKL(Q[P)) + N2
In
+
+
+ CCK.
N
4N
2a
20 tr
where we chose X = N2a
Moreover, since both P and Q are normal distributions, we know that
Σ 1w:113
DKL (Qll =
(50)
20
Per assumption, both B and D are constant with respect to No. Hence, for large enough Nu.
(//8 V 26 (AN + +l1D) 4(e2 + 1)e² d' B 30 / 2h In (4Dh)'
(51)
which implies,
(7/8E)
(52)
26 (AN + +lm
and hence
b(Na + In 2bD) E,
| 12 22/D
DKLL Dkl(Q|
(53)
(7/8)2/D
Therefore, with probability at least 1 5,
2
2n3
cl.(h) - Ch.(h) <
(KL(Q[
+
In
+
+
+ +CKE
N220
8
4N1-
-
22x
N220
tr
(54)
b b;
0
2/D
In
+
+ CKK)
Ng (7/88)2/D
2/D
N2n
N
20
37

---

Published as a conference paper at ICLR 2026
Step 2. Then show the second step, ie.. finding out the number of 3 we need to cover all possible relevant classifier parameters. Similarly as Neyshabur et al. (2018), we will show that we only need L/D
consider 2B < 3 C' (recall that the spectral norm of all weight matrices is bounded by C). then for any graph G E Gir U Gte. we get [ S 3 which implies that the bound trivially holds. Since we only consider / in the above range, sufficient condition to make
1/D
3 2n
| 31 < & hold would be |3 3 D
1/D Therefore, suffices to find a covering for all 27
possible weight matrices with radius 1
D (2 1/D for a ball in Rx of radius C. This can be satisfied
82
by (2 ( balls. Taking union bound, get, with probability at least 1 - 6,
(h) (h) s 1
4 '3 E, EE
Iwili 2/D + N
DC (2B)
b² In 2b
N 11-22 2a + CKŞ
2 (7/8)2/D
g1/D6
(55)
F FIXED GRAPH ENCODERS
Next, we apply our analysis to GNNs with fixed encoders. Here, the embedding function : 9 - R& is fixed, and only the classifier R + IK is trainable. Let H C E, where & now represents fixed graph embedding network. The generalization bound in this setting simplifies to the following.
Corollary F.1. Let lat be any pseulometric the latent space TRd.. Under mild assumptions (see Appendix D). for any >> O and O < < 1.2 with probability at least 1 - 5 over the sample of training labels yer, the test loss of any classifier
Cle S (h) + of
MCCC N RIDD
+
C Slat
(56)
complexxity term
structural similarity
where Eist maxces, mingeg, lat ((()),((H) and the other constants are defined in Theo- rem 4.7
Proof. The proof follows the same steps as in the proof of Theorem E.6 For example, Lemma
can
be shown for MLPs by simply assuming that there are no MPNN layers in Lemma E.4 can then proved for the hypothesis space H by defining the variance as
Theorem E.6
(D/8E)
7
min
2b (AN +ln2bD)
eBB PB30-1 2b In
In this case, the complexity of the graph embedding model no longer contributes to the bound, and only the complexity of the MLP classifier affects generalization. This reduced complexity underscores promise of fixed graph encoders.
G PROOF OF LEMMA ON COMPARISON OF TMD AND F-TMD
Lemma G.1. For any G, H. E G and any non-empty family of features F' C FF C. G, we have F' F'MMMD(G, H) S F-TMD(G. H)
Proof. Starting from the definitions, we have:
F'-TMD(G, H)
min
Σ TD (IG"" (Tul
38

---

Published as a conference paper at ICLR 2026
TD (T TT61)
F-TMD(G, H) min dES
where Sn the set of all permutations node set {1, ....,,,,,, n). .22,..,,,,,, and T denotes the subtree of
GF (the graph G augmented with additional features F) at node j.
Let o' be the optimal assignment for F-TMD(G,H): i),
F-TMD(G, HI)
Σ TD (15" IT
Since FT-MMD H) optimizes over all assignments, follows that
H' S
Σ
TD (15" TT
(57)
j=1
Our goal is to show that for every j:
(T o')
S TD (IO² .Tol))
TD
(58)
Together, Equation (77 and Equation
58
lead to
F'TMMD(G, H)
TD TO Tol
==1
(T THI
TD
j=1
F F-TMD(G, H).
proceed to prove Equation (88 via induction. fact, we show a more general version: for every assignment between nodes of G and H and any node j. we have
TD (T
TD T I
pb)
Base Case (1 0).
At depth 0, the trees consist only of root nodes. The tree distance is the difference between node features, i.e.,
TD T
Tols
||ay =
||ē ا
TD (TI² Ip(ti)
where =
and ā₁ = (æj, (F),, Cg (Fpz))
include the additional
features.
Induction Step (1 - + l).
Assume that for every tree of depth t 1, we have, for every assignment p and every j 1, 1,...,
TD (TG TH TD TT T
Let o' be any assignment of trees and let 7 be the optimal assignment in WTD (TT,TT..))
39

---

Published as a conference paper at ICLR 2026
Then, for any j 1, ..
TD (I95t (I = || - -oors)
Σ
TD (1OT) .I4(6)
+ min
T'ES,
j=1
< 110// 2' +
TD (TO" :(7)
$ 11 -i1 + Σ TD TT50² .T(i)
(59)
= 1l - E' + WID (T
TT
< 1 - To'n))l + WTD (p (TJ (T(TTo))
= TD (I TT'
The second inequality follows by the induction hypothesis as the considered trees are of depth t 1. Hence, by induction, the inequality TD (IT" TTT)) s TD proof.
(I T holds, completing the
Proof of Theorem 6.1. Assume that y ~ F-TMD.
Since any F-GIN classifier h Lipschitz continuous with respect to F-TMD and is stable with respect to weight perturbations, by Theorem 4.1, we have
6 Σ, Σ. 11 22/D + 122 1I122))DC(2BB)U N2 (1/8)2// (h) S (h) +0
N 1- + +CKE
1/87
with & = max Cu, Gue F-TMD L+1 (
(Gir, Gia) and B maxe |X (G))
2. By Lemma G.I every F' classifier h' is Lipschitz continuous with respect to F-TMD, as
[I'(GG) H(HH)| L'F H) H L'F-TMD(G, H).
(60)
Hence, applying Theorem 4.1 we have
b E; E. |
h2 DI
Cla - (T) +
2/D +
CKÊ)
N2 (1/8)2/D
N2ay1/D5
N1-20
where B' = maxg |XX(R (G))(i,:) Note that B' is the only difference compared to the previous bound.
3. Assume y ~ F-TMD, but apply a F-GIN classifier h. Since h not necessarily Lipschitz continuous with respect F-MMD, we cannot directly apply Theorem 4.1
However, if y F-MMD, then y F-TMD as well. Specifically, if y F-MMD, there exists for every class i some 7) such that 7), (G) = Pr(yc = k G), and me is Lipschitz
continuous with constant T.gh. Then, by Lemma G.T
[Txx nh (ff) S Lyg F-TMD H1 < Ly F-TMD(G,H)) Consequently, we can now apply Theorem
(61)
to obtain
(" E, ( E, N (1/8)2/D
22/D 122 DC22))C(()
(2e(h) < (T)(0)) +0 (7,
N N1-2n 2a CK.
1/221/D8
where & maxG EIr. T-D I+ IGG Gue) and B maxe ( (G))
Ille. Note that i and are now different compared to the previous bounds Item I and 2.
40

---

Published as a conference paper at ICLR 2026
Training loss
Test error vs. noise
Time to Overfit vs Noise
Label noise
100
0.5
0.6
0.4
0.4
50
1.0
0.3
0.2
0.2
0
50
100
0.5
0.5
Epoch
Noise
Noise P
Figure 4: Left: Training-los trajectories of GIN MUTAGENICITY under increasing label noise p. Center: Corresponding test errors on MUTAGENICITY sharply as label-structure correlation is essential for generalization (mean + standard deviation across five seeds). Right: Number of epochs to overfit, i.e., reach 99% training accuracy under increasing label noise
H OTHER RESULTS
The following lemmata easy to prove.
Lemma H.1. Given MPNN with layers such that the message and update functions gi and (() are Lipschitz continuos with Lipschitz constant L(f(k) and L(g)t)), respectively. Then for any graph G with maximum node degree we have
I (C (1+dL(g())) B,
1001 S eEV(G)
max
(62)
where x/ denotes the oulput of the MPNN after layers node v.
Lemma H.2. Given a MPNN with t + layers such that the message and update functions (8)) and ((0 are Lipschitz continuos with Lipschitz constant L(P()) and L(glk)), respectively. Then for any graph G with maximum node degree v, we have
(1 (1= B.
max [ (++1) S dl (e44)
(63)
(1) denotes the message of the MPNN at the (t + 1) 'h layer at node v. Lemma H.3 (Lemma in (Nyshabur al. 2018).. Let fw R RRt be a neural network with Lipschitz continuous and homogenous activations and d(f) layers For any D, Then for any w, XB and any perturbation vee( ([U,}² such that [1ll222 S 2ll sll2. the change the output of the network can be bounded follows:
where my
U.
[l [w(x)]12 eB
II W &
W
I ADDITIONAL EXPERIMENTAL RESULTS AND DETAILS
This appendix provides comprehensive overview of our experimental setup, including dataset generation, model architectures, training procedures, evaluation metrics, and additional analyses. All experiments were run on an internal cluster with Intel Xeon CPUs (28 cores, 192GB RAM) and GeForee RTX 3090 Ti GPUs (4 units, 24GB memory each), well as Intel Xeon CPUs (32 cores, 192GB RAM) and NVIDIA RTX A6000 GPUs (3 units, 48GB memory each). Each subsection corresponds to of the three experimental tasks.
I.1 LABEL NOISE EXPERIMENTS
To investigate how MPNNs behave under noisy supervision. we conducted controlled label corruption experiments three benchmark molecular graph classification datasets from the TUDataset collection
41

---

Published as a conference paper at ICLR 2026
Training loss
Test error vs. noise
Time to Overfit vs Noise
Label noise
0.8
0.5
20
0.6
0.4
0.4
1.0
0.3
10
0.2
0.2
10
20
30
0.5
0.5
Epoch
Noise
Noise P
Figure 5: Left: Training- loss trajectories of GIN on BZR under increasing label noise p. Center: Corresponding test errors on BZRrises sharply as struc-structure correlation is essential for general- ization (mean + standard deviation across five seeds). Right: Number of epochs overfit, i.e., reach 99% training accuracy under increasing label noise p.
Training loss
Test error noise
Time to Overfit vs Noise
Label noise
0.0
0.5
0.6
0.2
200
0.5
0.4
0.4
0.8
100
0.3
0.2
0.2
0
0
200
400
0
0.5
0.5
Epoch
Noise p
Noise p
Figure 6: Left: Training-loss trajectories of a GIN on NCI109 under increasing label noise p. correlation is essential
Center: Corresponding errors NCI109 rises sharply for generalization (mean standard deviation across five seeds). Right: Number of epochs to overfit, i.e. reach 99% training accuracy under increasing label noise p.
(Morris et al. 2020a): MUTAGENICITY, NCT109, and BZR. For each dataset, we randomly corrupted fixed proportion of the training labels by replacing them with uniformly sampled class labels.
We employed a MPNN with four layers, ReLU activations, GraphNorm, and a two-layer MLP head, Each message and update function in the MPNN is given by an MLP with two layers. The models were trained for up to 5000 epochs with early stopping once 99% training accuracy was achieved. Label noise levels were varied in 0.0, 0.2, 0.4, 0.6, 0.8, 1.0, and results were averaged over five random seeds per setting.
We track the per-epoch training and test accuracy/loss, the number of epochs until memorization. and total training time. This setup closely follows the protocol of Zhang et al. (2017), adapted to the graph setting, and enables us to study not only final generalization but also how memorization unfolds over time under increasing label noise.
Figure 5 and visualize the results on MUTAGENICITY. BZR, and NCI109, respectively. Each figure presents from left to right: (left) the full training curves, (middle) final test accuracy versus noise level, and (right) the number of epochs required reach 99% training accuracy. These plots collectively illustrate the sharp transition from generalization to memorization and the datasct-specific sensitivity of MPNNs to label corruption.
As the label noise increases, the time required to reach 99% training accuracy increases moder- ately suggesting that fitting corrupted labels is harder, but still feasible. However, all models eventually reach near-perfer pear-et training accuracy across all noise levels, even for fully randomized labels (p = 1.0), underscoring the high memorization capacity of GNNs. In stark contrast, the test accuracy consistently deteriorates with increasing noise and converges chance level at p 1.0,
42

---

Published as a conference paper at ICLR 2026
where labels entirely uninformative. This gap between training and test performance confirms that GNNs can overfit to pure noise and emphasizes the need for principled regularization and early stopping to preserve generalization.
1.2 TASK MEDIAN-BASHE LABELING WITH CYCLE COUNTS
To investigate the role of local structural patterns in graph classification, we generate 3,000 random graphs using three common models: Erdós Erdós-Rényi (ER). Barabási-Albert (BA), and Stochastic Block Model (SBM). Each graph's 's label is related to the sum of its 3-cycle and 4-cycle counts, which are computed using NetworkX (Hagherg al. 2008). The total cycle count is then used to assign labels: graphs with counts below the dataset median are labeled 0, while those above receive label 1.
For synthetic graphs, we sample the number nodes randomly between 35 and 55. For each random graph model, we chose the following parameters.
Erdōs-Rényí (ER) Graphs: We generate an ER graph with edge probability 0.1.
Barabási-Alless (BA) Graphs: Each new node is connected to m 2 existing nodes
following the BA preferential attachment process.
Stochastic Block Model (SBM) Graphs: We randomly select between and blocks, ensuring each block has at least 3 nodes. The probability of an edge within the same block is sampled uniformly between [0.1, 0.3), while inter-block connections have probability in the range [0.001, 0.02].
We evaluate multiple GNN variants to assess the impact of different levels of expressivity:
MPNN: A standard Message Passing Neural Network (Gilmer et al. 2017
Fi-MPNN: MPNNs enriched with cycle counts of cycles up to length (Bouritsas et al. 2023
Barceló et al. 2021).
Subgraph GNN: Incorporates subgraph structures (Frasca et al. 2022).
Local 2-GNN: A local variant of 2-GNN (Morris et al. 2019).
Local Folklore 2-GNN: A local variant 2- 2-Folklore-GNN (Zhag et al. 2024).
Each model is implemented in PyTorch Geometric (Fey & Lenssen, 2019), using the implementation details of Zhang et al. 2024). We trained the models using the Adam optimizer (Kingma & Ba 2015)
with learning rate of 10 for 100 epochs and cosine scheduler. We fix the test set, and we perform 10-fold cross-validation, reporting mean accuracy (ACC) and standard deviation. Performance is measured at both the final epoch and the best validation epoch.
We present additional experimental results in Table 1 in this appendix. To further illustrate the strong correlation between labels and FMM,D we provide qualitative visualization of the dataset structure (see Figure 7). Specifically, we select 50 graphs of the ER dataset and project them into wwo-dimensional space using Multidimensional Scaling (MDS), with distances computed based on standard TMD, F--TMD, F-MMMD, and F12- FMD. Among these, the projection using F4-TMD exhibits the clearest class separation, visually reinforcing its alignment with the classification task.
1.3
TASK 2: REAL-WORLD DATASETS
We evaluate our generalization framework on six real-world datasets from the TU Dataset collection (Morris et al.) 2020a), spanning both biological and chemical graph classification tasks:
Mutagenicity: 4,337 molecular graphs labeled mutagenic non-mutagenic.
PROTEINS: 1.113 protein graphs classified by their enzymatic function.
BZR: 405 graphs representing benzodiazepine receptor ligands labeled for activity.
COX2: 467 graphs labeled based on activity against the COX2 enzyme.
NCT109: 4,127 graphs representing chemical compounds screened for anti-cancer activity.
AIDS: 2,000 graphs with binary activity labels relevant AIDS antiviral screening.
43

---

Published as a conference paper at ICLR 2026
ost o cOMEEcIO th
Figure 7: cow-dimensional embeddings via MDS for Task in Section MDS projects the graphs into R² while preserving the pairwise Fi-TMDs between graphs in the dataset. From left to right: TMD, F3-TMD, FMMMDD and Fi2-TMD. Visually, F4-TMD achieves the best class separation, highlighting that the labels strongly correlate with F4-TMD. As result, F₃-MPNNs provide the best generalization and predictive performance.
To assess whether generalization MPNNS and MLPs with fixed feature extractors depends on the structural similarity between test and training graphs, as predicted by our generalization bound in we conduct two complementary evaluations:
Theorem
(i) GIN with TMD: We train GINs (Xu et al. 2019) and measure distances between graphs using the TMD.
(ii) Fixed encoder with Hamming distance: We compute molecular fingerprints (Gainza et al.
2019) for each graph, apply an MLP classifier, and measure distances in the resulting feature space via Hamming distance.
We analyze two key properties:
Error TMD Distance. To quantify the relationship between structural proximity and model performance, we report cumulative accuracy. Test graphs are ordered by increasing distance to the training set, and compute the cumulative average accuracy. Specifically, given the ordered test G GN we define
Σ (GG))ua.)) S max h(G)
where Y represents the average accuracy over the first i graphs. For end-to-end trained GIN models, Figure and Figure & illustrate that test accuracy consistently decreases the structural distance from the training distribution increases. similar trend is observed for MLP+fingepprin models in Figure These empirical results align with our theoretical insights presented in Theorem 4.1 which predict this performance degradation.
Theoretical vs. Empirical Generalization Bound. We further examine how well our bound from Theorem 4.1 predicts the actual generalization behavior. For each dataset and model, compute the theoretical bound using the empirical training loss and the graph distances to the training set as prescribed by Theorem 4.1 We compare this bound to the observed test error across all datasets. Results are presented in Figure and and in the appendix (Figure TOp. While our bound is not tight, does track the empirical error trends well across datasets, substantiating our claim that structural similarity with respect to the right pseudometric governs generalization in graph learning.
1.4 TASK 3: MDS-BASE LABELING VIA F5-TMD DISTANCES
For the second synthetic task, we construct 500 random graphs and compute pairwise distances using the J3-TMD pseudometric, where Fs includes cycles up length 5. Labels are assigned using clustering algorithm, ensuring that graphs closer in F; TMD likely share the same label. We test different GNNs and summarize the results in Figure [I
Details. For the second synthetic task, generate 500 random graphs between 15 and 35 nodes using ER graphs with edge probability p = 0.1. We use the F5-TMD pseudometrie, where Fs consists of cycles up to length 5. We compute pairwise graph distances with respect to F-MMM
44

---

Published as a conference paper at ICLR 2026
Table 4: Train and test accuracy, Erdós Renis graphs. The task is predict if the count of cycles of length at most in the cycle basis of each graph is above or below the median the whole dataset. The node features (suby) subgraph-counts of cycles up to length N, and (basx) number of cycle graphs up to length N in the cycle basis.
augmented with (homx) homomorphism-counts of cycles up to length N,
(a) w/ early stopping.
(b) w/o early stopping.
Num, byyer
Num. layer
Model
3
L.G
0.8707 + 0.0106
6.9180 + 0.0179
0.8707 = 0.0110
0.8216 =
0.8637 + 0.0106
+ 0.0318
0.8543 + 0.0063
0.9904
0.8620 + 0.0073
0.8363
1,0000
0.0102
0.0001
LFG
0.9162 + 0.0165
0.8647 1: 0.0098
0.8683 1: 0. 0.0086
0.9148 = 0.0409
0.8623 1 0.0112
0.9226 + 0.0391
0.8450 1: 0.0135
0.9868 = 0.0051
0. 0.9089 + 0.0003
0.8540 1 0.0121
0.8543
1.0000
0.0001
0.0116
MP
0.9050 + 0.0094
0.8737 + 0.0091
0.8894
0.9135 + 0.0256
0.0165
0.9255 + 0.04D3
0.8597 4 0.0126
0.8490
0.9906 + 0.0033
0.0045
0.8667 + 0.00ST
1.0000 + 0.000
0.8637
0.9998 = 0.0000
0.D138
MP+homg
0.8993 1: 0. 0.0123
0.8783 1 0.0105
0.9115 + 0.0316
0.8710
0.0116
0.8750 1 0.0098
0.9335 + 0.0462
0.9886 :: 0.0039
8480
0.0108
0.9999 1 0.0002
0.8537 1 0.0107
0,8673 0.0141
1.0000 +: 0.0000
MP+hom4
0.8993 + 0.0121
0.8998 + 0.0120
0.9185 + 0.0408
0,9302 + 0.0039
0.9978 + 0.0018
0.9990 + 0.0011
0.8783
0.0138
MP-homy
0.8913 1: 0.0117
0.8740
0.5693
0.9002 + 0.0198
0.8915 1 0.0286
0.8700 0.0097
9090 + 0.0081
0.9795 1: 0.0040
0.0123
0.9897 O. 0058
MP+barg
0.9210 0.0201
0.9465
0.0376
0.9436 0.0393
0.0028
0.9999 0.0002
0.8717 + 0.0173
0.8778
0.0168
0.8783 + 0.0096
863677 = 0.0085
0.8670 + 0.0097
0.8723 0.0049
MP4box
0.9754
0.9761
0.9841 0.0081
0.0034
0
0.0004
0.9870 1: 0.0046
0,9700 :: 0.0154
0.9603 1: 0.0048
0,9793 :: 0.0068
0.9587 1 0.0072
0.9523
0.0102
MP+basy
0.9720 + 0.0111
6.9782 + 0.0087
0.9804
0.9373
0.0077
0.9850 +
0.9490 + 0.0083
0,9860
0,9958
0.0063
0.9650 + 0.0062
0.9999 0.0003
0.0072 0.9337
0.0005
MPswubg
0.8979 1: 0.0174
0.8827 1 0.0123
0.9340 +: 0 0.0473
0.8697 1: -0135
0.9166 4: 0,0320
0.8747 1 0.0144
0. 0.9933
0. 8510 : 0.0078
0.0029
1. 1.0000 1 0.0001
0.8547 1 0.0075
0,8683
1,0000
0.0080
0,0000
MP+sub4
0.8976 +: 0.0111
0.9090 + 0.0270
0.9233 + 0.0287
U.9833 + 0.0034
0.9995 + 0.0009
0.9998
0.0004
6.8780 + 0.0031
0.8717
0.0098
0.8733 + 0.0108
0. 8487
0.01
0.8613 + 0.0127
0.8623
0.0130
MPssuby
0.8963 1: 0. 0059
0.8790 1 0.0067
0.8760
0.9140 + 0.0174
0.0092
0.9312 1 0.0304
0.8657 1 0.0075
0.9018 + 0.0035
8803
0.0070
0. 0.9670 +: O. 0.0070
0.8660 + 0.0121
0.9815 = 0 0.0090
0.8553 0.0135
Sub-G
0.9194 4: 0. 0.0238
0.9060 à 0. 0033
0.9561 + 0.0411
0. 0.9887 + 0.0048
1.0000 4: 0.0001
1.0000 E 0.0000
0.8710 0.0088
0.86G3
0.0074
0.8640
0.0099
0.0058
0.8G33 0.0088
0.8680
0.0100
45

---

Published as a conference paper at ICLR 2026
Table 5: Train and test accuracy, Barabasi-Albert graphs. The task is to predict if the count of cycles of length at most 4 in the cycle basis of each graph is above or below the median of the whole dataset. The node features are augmented with (homy) homomorphism-coue cooomutphism-coutss conntss of cycles up to length N. (subx) subgraph-counts of cycles up to length N, and (bas number of cycle graphs up to length N the cycle basis.
(a) w/ carly stopping.
(b) w/o early stopping.
Nom. lnyer
Num. layers
Model
L-G
0.819 + 0.013
0.794 0.017
0.793 + 0.019
0.928 + 0.009
0.827 + 0.00G
0,983 + 0.003
0.767 + 0.014
0.751 0.013
0.747 + 0.010
0.747 4 0.007
0.737 + 0.014
0.719 + 0.011
LFG
0.818 + 0.018
0.775 0.008
0.807 = 0.021
0.770 0.012
0.822 + 0.051
0.747 + 0.015
0.846 + 0.008
0.773 1 0.013
0.902 + 0.006
0.745 0.010
0.978 + 0.006
0.730 0.018
MP
0.771 0.015
0.811 + 0.015
0.802 0.013
0.767 0.011
0.757 0.009
0.798 + 0.022
0.849 + 0.004
0.762 1 0.009
0. 0.909 + 0.011
0.740
0,011
0.751 0.025
1.000 + 0.000
MP+homa
0.777 + 0.010
0.700 0.010
0.789 + 0.019
0.787 + 0.004
0.760 + 0.00G 0.759
0,908 + 0.012 0.737
0.774 0.019
0.749
0.772 0.01
0.778 0.006
MP-bwwg
0,840 :: 0.010
0.020
0.801 0.021
0.847 0.017
0.863 1: 0.039
0.798 0.016
0.962 1: 0.003
0.609 0.016
0,982
0.005
0.015
0, 0.998 0.001
0.006
MP4bax
0.963 0.012
0.905 = 0.003
0.970 0.005
0.994 0.003
0.950 + 0.008
0.963 0.008
0.984 + 0.004
0.005
0.977 0.007
0.006 0.991
0.973 = 0.003
0.992 0.005
MP-bwsg
00.008
0.976 0.014
0.961 0.016
0.982 0.004
0.994
0.003
0.998
0.989 0.005
0.977 0.007
0.953 + 0.006
0.989 + 0.007
0.971 0.009
0.954 + 0.004
Sub-G
0.7G0 3 0.015
0.705
0.013
0.814
0.730 0.015
0.030
0.733 + 0.016
0.821
0.060
0.918 + 0.004
0.755 + 0.015
0.728 + 0.011
0.011
0.712 + 0.026
0.992 0.004
Table 6: Train and test accuracy, Stochastic Block Model graphs. The task is to predict if the count of cycles of length at most 4 in the cycle basis of each graph is above or below the median of the whole dataset. The node features are augmented with (homyy homomorphism-coume N. (subx) subgraph-coung of cycles up to length N, and (bas number of cycle graphs up to length in the cycle basis.
of cycles up length
(a) w/ early stopping.
(b) w/o early stopping.
Num. lnyer
Nar loyers
Model
2
L-G
0.961 : 0. 007
0.972
0.009
0.960 + 0.011
0.968 0.003
0.981
: 0.002
0.998 + 0.001
0.961 à: 0.003
0.949
0.003
0.943 4: 0.010
0.961 #: 0.005
0.948
4: 0.005
0.923 4: 0.004
LPG
0.965 : 0.005
0.948 # 0.0G5
0.969
0.004 0.942
0.020
0.963 + 0.D11
0.962
+ 0.020
0.968 + 0.003
0.957 0.002
0.941
0.979
+ 0.005
0.006
0.M37 + 0.005
0.099 + 0.001
MP
0.967 4: 0. 000
0.955 0.008
0.962
0.973
0.007
0.004
0.967 + 0.004
0.955 + 0.006
0.951 0.005
0.973 4: 0.006
0.975
0.963
4: 033
0.005
0.991 4: 0. 0.002
0.955 1 0.007
MP+hom4
0.947 + d.uG5
0.900 0.007 0.946
0.963 + U.D13
0.958 0.003
0.963 + U.
0.vT3 + U.D0G
0.953 0.006
0.953
0.004
0.953 0.008
0.938
0.008
+ 0.006
MP-tawg
0.966 :: 0. 00007
0.958 0.012
0.958 0. 007
0.973 1: 0.012
0.959 0.007
0.979 0.003
0.960 0.005
0.991 1: 001
0.007
994944 1: 0. 0..03 0.959 1 0.007
MP+bas
0.957
0.981 0.005
0.958
0.977 0.011
0.976 + 0.005
0.979 0.012
0.980 0.001
0.989 0.003
0.988
0.954 = 0.003
0.995 + 0.002
0.971 + 0.010
MP4basg
0.964 0.006
0.959
0.955 0.005
0.962 0.
0.995
0.999 1 0.001
0.982 1: 0.007
0.973 0.004
0.975 4: 0.008
0.978 0.003
0.967 1: 0.003
0.966 1: 0.006
Sub-G
0.961 3: 0.012
0.957 + 0.006
0.959 0.010
0.943 0.00G
0.977 + 0.00G
0.934 +: 0.008
0.970 0.006
0.964 + 0.004
0.975
0.948 :: U.
O. 002
0.931 + 0.009
0.994 + 0.003
and embed the graphs into a two-dimensional space via Multidimensional Scaling (MDS) (Kruskal 1964). MDS embeds the graphs into wio-dimensional space while preserving the initial F5- Tree Mover's Distances from the raw graph space, i.c., one can formulate as the optimization problem
given by
Σ - -(1a===ll-C-MDDGG (-MDD(G, 2,
arg
min
2o ER3
i<j
46

---

Published as a conference paper at ICLR 2026
COX2
AIDS
PROTEINS
Alayors
0.9
Accuracy
0.8
0.9
0.8
0.7
0.98
10
102
10a
10
10a
10
10a
10a
10
TMD to training set
TMD to training set
TMD to training set
Figure& 8: Accuracy of GIN with 1, 3, and 5 layers versus Tree Mover's Distance (log scale) to the training dataset.
Mutagenicity
0.86
layer
2 layer
3 layer
0.85
Cumulative test avg accuracy
0.84
0.83
0.82
0.81
2
3
5
6
FPD
-10
Figure 9: Cumulative test accuracy of MLP vs. Fingerprint Distance (FPD).
Labels are assigned using 2-means clustering, ensuring that structurally similar graphs remain same class. MDS and 2-means clustering are implemented via scikit-learn (Buitinck et al. 2013).
The experimental setup identical to Task 1, with models trained and evaluated under the same protocol: We perform 10-fold cross validation with training/ valiitiio/llitttio/tssstttt set with 80/10/10 splits. We report the test accuracy at the epoch with the highest validation accuracy. This task tests the ability of different GNN architectures generalize. The task is generated such that labels strongly correlate with F--M We present classification performance, showing that Fs-MPNNs perform better than MPNNs and more expressive GNN variants.
47

---

Published as a conference paper at ICLR 2026
BZR
COX2
-104
-104
0.1
3
Empirical Error
0.1
Empirical Error
Error Bound
Error Bound
2.6
2.8
0
2.6
2.4
-0.1
0.1
2.4
2.2
200
400
0
100
200
TMD to training dataset
TMD to training dataset
AIDS
PROTEINS
-10*
-10-2
-10
-104
1.5
6
Empirical Error
5 10-2
Empirical Error
Error Bound
1.4
Error Bound
0
1.3
4
0
1.2
5 10
2
1.1
0.1
0
200
400
0
1
2
TMD to training dataset
TMD to training dataget
Figure 10: Error-bound curves for BZR, COX2, AIDS, and PROTEINS. Each plot shows theoretical bound (blue, left axis) and the empirical generalization error (red, right axis) as a function of TMD to the training set. Shaded areas indicate +1 standard deviation across 10 random splits.
Train Error
Test Error
LF-G
15.6
11.01
Sub-G
17
12.1
F3-MPPN
13.2
10.37
MPNN
16.8
11.36
Error (%)
Figure 11: Performance of different GNNs for ~ FT-TMDD where Fs includes cycles up to length 5. Fs-NPNN achieves the best performance, supporting our claim that incorporating task-relevant features outperforms excessive expressivity.
48


Reviews:
[{"review_id": "uIp968cHYs", "reviewer": "Reviewer_cYcW", "summary": "This paper explores the complex relationship between the expressivity of Graph Neural Networks (GNNs) and their generalisation. It suggests that generalisation depends on model capacity and the alignment between task labels and graph similarity. To capture this, the authors introduce a family of pseudometrics called ζ-Tree Mover Distances (ζ-TMDs), which extend the Tree Mover’s Distance by using “strongly simulatable” colour refinement algorithms to transform graphs before distance computation.\n\nTheoretical results show that ζ-MPNNs (MPNNs consistent with a given CRA ζ) are Lipschitz with respect to ζ-TMD and yield PAC-Bayes based generalisation bounds. The test loss decomposes into a capacity term involving layer widths, spectral norms, and graph degree, and a structural similarity term that measures the distance between the training and test sets under ζ-TMD.\n\nThe paper emphasises that “more expressivity” can have both positive and negative effects. Increased expressivity improves performance if it reduces structural similarity term (i.e., better label-structure alignment), but it can degrade otherwise due to added capacity without alignment gains. The paper supports this through synthetic cycle-counting tasks and several TUDatasets, showing that moderately expressive, task-aligned models (e.g., F4-MPNN) generalise best, and empirical errors increase with the TMD distance from the training graphs, tracking the bound’s qualitative trend.", "questions": "1. How would you recommend practitioners choose ζ in real tasks?\n\n2. What is the complexity of computing ζ-TMD at depth T for the CRAs considered? Can you provide scalable approximations (e.g., subsampling rooted trees, contrastive encoders trained to approximate TMD distances)?\n\n3. Assumption and robustness:\nHow sensitive are your bounds and empirical trends to violations of $y \\sim \\zeta-TMD^{T+1}$ and Assumption D.1? Could you adopt alternative robustness frameworks to relax or complement D.1?\n\n4. Does your Lipschitz analysis extend to attention-based graph transformers or alternative poolings (e.g., mean/max, Set2Set)? What constraints would be required?\n\n5. Empirical alignment tests:\nCould you add a diagnostic that measures the correlation between label distributions and ζ-TMD distances to training graphs, to operationalize “alignment” before model design?\n\n6. Experiments: in Fig 2 and 3, the accuracy/empirical error increases/stabilises after certain TMD, can you think of any reasons?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The idea of task-aligned pseudometrics for graphs, formalized as ζ-TMDs, is novel and compelling. Extending TMD through strong simulation of CRAs unifies diverse expressive GNNs (k-GNNs, subgraph models, motif-augmented MPNNs) under a single stability/robustness lens.\n\n- Proofs are extensive and careful, showing Lipschitz continuity of ζ-MPNNs and deriving PAC-Bayes style bounds where the generalization gap depends on $\\xi_\\zeta$. The synthetic and real-world experiments are well targeted to the claims (memorization under label noise, alignment-driven generalization, expressivity vs. overfitting).\n\n- Definitions of CRAs, strong simulation, and ζ-TMD are clearly laid out. The decomposition of the bound into “capacity” and “structural similarity” terms makes the trade-offs intuitive. The paper situates itself well among WL-expressivity, graphon bounds, and robustness literature.", "weaknesses": "- Identifying the right ζ (task-aligned pseudometric) can be hard:\nThe framework presumes labels are “strongly correlated” with a chosen $\\zeta-TMD$. In practice, discovering the right ζ is nontrivial and can be expensive (e.g., motif counts, product graphs).\n\n- The paper assumes the CRA to be strongly simulatable, but did not mention under what condition is a CRA strongly simulatable, some examples would be good. \n\n- Bound looseness and constants:\nThe PAC-Bayes bound involves many constants (widths, spectral norms, degrees) and uses assumptions (e.g., Assumption D.1) that can be stringent. The bound is qualitative and not tight.\n\n- Computational overhead of ζ-TMD and strong simulation:\nMany expressive CRAs require transformations (e.g., k-tuple product graphs) that scale poorly, and computing TMD itself is nontrivial. This, together with the looseness of the bound, greatly hinders the practicality of the results.\n\n- Experimental scope:\n The authors empirically shows the bound demonstrates similar trend as empirical error in Fig 3, but this is not quantitative. If possible, I would like to see the correlation between the bound and empirical error on a wider range of datasets.\n\n- Presentation polish:\nSome minor issues (placeholder captions, typographical glitches, compressed figure axes) impact readability, e.g. \n  * missing caption is Fig 10\n  * P in L157 is not defined.\n  * L165-167 \"We say that a graph invariant ζ is more expressive than another graph invariant θ if ζ(G) = ζ(H) implies θ(G) = θ(H) for all G, H ∈ G.\" This doesn't feel right, if ζ and θ have the same expressivity, then ζ(G) = ζ(H) implies θ(G) = θ(H), according to this definition, ζ is more expressive than θ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "2JwJEOHbev", "reviewer": "Reviewer_uzRa", "summary": "This paper studies when increased GNN expressivity helps or hurts generalization by introducing ζ-Tree Mover Distances (ζ-TMDs), task-aligned pseudometrics built via strong simulation of color refinement algorithms. It proves ζ-MPNNs are Lipschitz w.r.t. ζ-TMD, then derives PAC-Bayes bounds that decompose into a capacity term and a structural similarity term (distance between train/test under ζ-TMD). The analysis shows that expressivity improves generalization only when it enhances structure–label alignment; otherwise, it can worsen the bound. Empirically, synthetic and TU datasets support the theory and illustrate tighter (though still loose) bounds than standard PAC-Bayes.", "questions": "Please refer to weakness.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Clear metric → stability → generalization pipeline with non-trivial derivations. he paper defines task-aligned pseudometrics ζ-TMDs (Def. 3.1; Prop. 3.2–3.3), proves Lipschitz stability of ζ-MPNNs with respect to ζ-TMD (Theorem 3.4; e.g., “∥h(G) − h(H)∥ ≤ L · ζ-TMDT+1(G, H)”), and derives PAC-Bayes generalization bounds that separate a capacity term from a structural-similarity term (Theorem 4.1 and its simplified Eq. (4)). These steps connect distance between graphs → Lipschitz robustness → generalization in a coherent chain and require several technical lemmas (Appendix E, e.g., Lemmas E.2–E.5). The framework extends beyond standard MPNNs via strong simulation (Appendix B), covering F-MPNNs (Cor. 3.5) and k-GNNs (Cor. C.9).\n\nζ-TMD extends the TMD framework to strongly simulatable color refinements, sharpening the bounds via task-aligned structure–label correlation. The ζ-TMD pseudometrics let the bound depend on structure–label alignment, not just model capacity: “generalization improves when the model maps structurally similar graphs (with respect to the ζ-TMD that correlates with the labels) to similar representations while keeping model capacity in check” (Sec. 4; Eq. (4)). This is a principled and flexible way to encode task-relevant structure.\n\nWhen more expressivity helps vs. hurts is theoretically clarified and empirically supported. heorem 5.1 shows that moving from an under-expressive F′-MPNN to a task-aligned F-MPNN preserves the bound, whereas going beyond the task (to F˜-MPNN) can worsen the structural term since ξF˜ ≥ ξF (Lemma G.1), yielding a looser bound. This matches the experiments (Fig. 1 left; Table 1), where overly expressive models overfit. The paper even articulates the design principle: “the optimal GNN is precisely as expressive as required… no more, no less” (Sec. 5). Tighter-than-standard PAC-Bayes: the authors report their bounds are “significantly tighter,” often orders of magnitude smaller than standard PAC-Bayes bounds (e.g., 10^16 vs. 10^4; Sec. 6). To be precise, this is an orders-of-magnitude improvement (not necessarily “exponential” in a formal sense).", "weaknesses": "Choosing ζ is nontrivial and can be the bottleneck; once ζ is fixed, several proofs become mechanical.  The main benefit hinges on picking a ζ that actually aligns with labels. The authors acknowledge this: “the relevant pseudometric is often unknown and possibly expensive to compute” (Limitations), and Rζ can inflate size/degree/features (Eq. (4) discussion: “model complexity may increase if the graph transformation Rζ enlarges…”). Since many results follow from strong simulation plus known Lipschitz/OT arguments, the conceptual challenge is predominantly in selecting/designing ζ.  \n\nThe “increasing expressivity hurts generalization” conclusion rests on upper bounds and monotone dependence on ξ, not a tight characterization.  Theorem 5.1 compares upper bounds; it shows that a more expressive model can have a larger ξ term (ξF˜ ≥ ξF), hence a looser bound, but this is not a lower-bound or necessity result. Comparing two upper bounds does not prove a performance drop must occur—only that it may, given ξ and capacity growth. A converse or data-dependent lower bound (or a matching rate) would strengthen the claim.\n\nBound tightness and trend-shape mismatch in the empirical validation; limited breadth of alternatives. Fig. 3 shows the bound tracks trends but is very loose in scale (theoretical curves on the order of 10^4 vs. empirical errors below 1—i.e., ~4 orders of magnitude gap). Moreover, as TMD-to-train grows, empirical error often saturates/plateaus, whereas the bound’s dependence on ξζ is monotone and cannot capture this flattening. The paper notes the bounds are “qualitative guidelines rather than precise estimates” (Limitations), but some calibration (e.g., data-dependent Lipschitz constants, local smoothness, or normalized structural terms) would help. The empirical scope, while decent (synthetic + six TU datasets), is still limited relative to alternatives: few large-scale graphs, no runtime/compute study for ζ-TMD, and limited comparison to other distance-based theories (e.g., graphon cut metrics, Gromov–Wasserstein) or strong baselines beyond the selected GNN family variants. Ablations on the choice of ζ (how sensitive are results to different CRAs?) would also strengthen the evidence. Practitioner guidance is limited because the bounds are quite loose (often several orders of magnitude above empirical error). Adding one or two strong, actionable experiments—e.g., a ζ-selection/augmentation protocol that measurably improves test accuracy by reducing ξζ, or a procedure to choose model expressivity based on estimated ζ-TMD alignment—would better demonstrate practical utility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "gLZKhgvnwv", "reviewer": "Reviewer_wMWG", "summary": "The paper studies when higher expressivity in Graph Neural Networks improves or harms generalization performance. It introduces a family of pseudometrics called ζ Tree Mover Distances that quantify structural similarity between graphs at varying expressive levels, and uses these metrics to model structure–label correlation. The authors derive data dependent generalization bounds that decompose into a model capacity term and a structural similarity term, showing that increased expressivity can worsen generalization when it does not align with task relevant structure. Empirically, they demonstrate that moderately expressive GNNs outperform both vanilla MPNNs and highly expressive higher order GNNs on synthetic and real datasets when label signals correlate with specific structural features. Their results show that accuracy decreases as test graphs become structurally farther from the training graphs under the relevant pseudometric, matching the theoretical predictions.", "questions": "- In practice, how should one determine the correct pseudometric ζ for a given task? Does the proposed theory offer any algorithmic method or diagnostic criteria to identify such a metric when the relevant structural signal is not known a priori?\n- Why are the empirical evaluations limited to synthetic tasks and relatively small TU datasets? Can the authors provide results on larger and more challenging graph benchmarks such as OGB or heterophilic datasets to demonstrate generality and real world relevance?\n- How does this framework relate to other established causes of generalization failure in GNNs, such as over smoothing, over squashing, and information bottlenecks? Are these phenomena orthogonal to the expressivity alignment perspective, or can the proposed theory explain or incorporate them?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper tackles a central open problem in graph learning: understanding when increased GNN expressivity improves versus harms generalization. This is a core theoretical theme highlighted in recent GNN survey and workshop discussions, and the paper makes progress on a topic with clear community interest.\n- The ζ-TMD construction formalizes the intuition that model expressivity should match task relevant structural signals. By connecting GNN expressivity to pseudometrics that capture structural similarity, the paper provides a structured way to reason about alignment between graph structure and supervision.\n- The paper demonstrates cases where moderately expressive models outperform both simpler and more expressive architectures, consistent with the theory. The experiments, though modest in scale, validate the predicted trade-off between expressivity and structure–label alignment and show trends consistent with the generalization bounds.", "weaknesses": "- Although the paper proposes a ζ-TMD framework, the incremental contribution over closely related analyses of structure label alignment and robustness in recent literature (for example Ma et al., 2021; Li et al., 2024; Vasileiou et al., 2024) is not entirely explicit. The manuscript would benefit from a sharper articulation of what new theoretical insight is enabled beyond these frameworks, particularly given that alignment based perspectives have been explored previously.\n- The approach assumes access to an appropriate ζ that correlates with label structure. However, identifying such a metric in practice is nontrivial, and the paper does not provide a principled procedure to select or estimate it. This limits practical applicability, especially when the relevant structural signal is unknown.\n- Experiments are conducted primarily on synthetic tasks and small scale TU datasets. These benchmarks do not fully stress the claimed benefits, and are not representative of modern large scale or heterophilic graph learning settings. Validation on more challenging datasets such as OGB or heterophilic graphs would strengthen empirical support.\n- The generalization bounds are informative but rely on constants and assumptions that are difficult to estimate or control, which limits actionable guidance for model selection in practice. The paper frames the results as qualitative, but clearer direction on how practitioners should use the theory would increase impact.\n- The narrative focuses on expressivity alignment, but does not explicitly connect to orthogonal failure modes such as over-smoothing, over-squashing, and information bottlenecks in deep GNNs. Clarifying how the proposed theory relates to or differs from these phenomena would improve conceptual clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "0f33uNioZT", "reviewer": "Reviewer_iyDd", "summary": "This paper conducts an theoretical analysis on the tradeoffs between model expressiveness in the graph neural network context and empirical performance (seen through the lens of generalization). To this end, the paper studies the generalization of GNNs vis-a-vis their expressiveness by introducing and basing their theoretical analysis on variants of a tree-movers distance, which indicates correlations between structural features learnable / detectable by models and the ultimate classification output. The paper introduces the necessary concepts early in the paper, and explains how expressiveness affects TMDs (with more expressive models increasing them, potentially harmfully to performance), and them produces a bound combining model complexity and structural similarity.\n\nFrom this bound, the authors produce a simplified version that more accessibly explains the main contributors to worse generalization between training and testing. In particular, the paper highlights model complexity as a negative factor, relating this to overfitting, as well as worsening similarity between training and testing sets and worsening TMDs, which decreases model alignment. \n\nFinally, the paper conducts an empirical analysis of GNNs of varying expressiveness against both synthetic and real-world baselines, showing empirically that expressiveness indeed offers a \"sweet spot\", in which too little expressiveness can undermine performance, but excessive, uncorrelated expressiveness can lead to overfitting.", "questions": "None, please see weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper's methodology is sound and its arguments and experiments are well-designed. \n- The exposition of the paper is balanced, despite the highly involved nature of the proofs and of the subject matter as a whole.\n- The authors do well in extracting key insights from the paper and maintaining a high-level narrative despite the high technicality of the work.", "weaknesses": "- The results derived in this paper need significant contextualization and connection to practical phenomena to become more beneficial to the community. Naturally, I appreciate the derivations and constructions behind the theorems being proven in this paper. However, the connection, say, between $\\zeta$-TMDs as a theoretical construct and the choices of datasets and synthetic targets in the paper are not clear. I fully recognize that this is not a simple concept or connection to make, but I feel it is essential to better understand the underlying mechanics that are qualitatively being presented. It would also substantially strengthen the takeaway message of the paper.\n\n- At a high level, the insights drawn in this paper align with intuition, but, in keeping with my point above, lack accompanying guidance or support to be more widely applicable. For instance, $\\zeta$-TMDs and structural similarity are reasonable and plausible (if not perfectly quantifiable) metrics to want to estimate when selecting a model for a graph representation learning task, but it's not clear where to start. This may be a somewhat trivial exercise compared to the theoretical derivations themselves, but I feel that more curated examples with concrete choices for the pseudometrics and guidance on identifying appropriate choices more broadly would substantially increase the appeal of this work, and take it from being a theoretical result confirming widely held intuitions to the start of a framework or heuristic that informs model selection, much like algorithmic alignment [1]\n\n- Speaking of algorithmic alignment, I feel that that nuance is missing in this work. This is not a fundamental limitation, as the work in itself is already substantial, but I do still think that a comparison with intuitive alignment arguments would be beneficial for grounding your intuitions and conclusions, and would add good color. Most prominently, adding features that align with the task being learned, e.g., cycle counting, is well explained as a performance improvement through algorithmic alignment, and is compatible with your results. However, alignment captures a complementary subtlely, namely that being able to learn cycles as an expressive model is typically worse for generalization versus having explicit cycling representations. This also lines up with your work: A more expressive model capturing cycles among other cycles would weaken the correlation with the target signal, worsening generalization, whereas an aligned cycle-only model wouldn't. I would add some discussion on this as a minor improvement to the nuance of your analysis.\n\n[1] Xu et al., What Can Neural Networks Reason About? ICLR 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)