Towards Bridging Generalization and Expressivity of Graph Neural Networks
Authors: Shouheng Li
Floris Geerts
Dongwoo Kim
Qing Wang
Venue: ICLR 2025 Poster (2025)
Keywords: gnn
expressivity
generalization
Primary area: learning on graphs and other geometries & topologies
TL;DR: Generaliation of GNNs are influenced by embedding distribution of its upper-bounded graph encoders.

Abstract: Expressivity and generalization are two critical aspects of graph neural networks (GNNs). While significant progress has been made in studying the expressivity of GNNs, much less is known about their generalization capabilities, particularly when dealing with the inherent complexity of graph-structured data.
In this work, we address the intricate relationship between expressivity and generalization in GNNs. Theoretical studies conjecture a trade-off between the two: highly expressive models risk overfitting, while those focused on generalization may sacrifice expressivity. However, empirical evidence often contradicts this assumption, with expressive GNNs frequently demonstrating strong generalization. We explore this contradiction by introducing a novel framework that connects GNN generalization to the variance in graph structures they can capture. This leads us to propose a $k$-variance margin-based generalization bound that characterizes the structural properties of graph embeddings in terms of their upper-bounded expressive power. Our analysis does not rely on specific GNN architectures, making it broadly applicable across GNN models. We further uncover a trade-off between intra-class concentration and inter-class separation, both of which are crucial for effective generalization. Through case studies and experiments on real-world datasets, we demonstrate that our theoretical findings align with empirical results, offering a deeper understanding of how expressivity can enhance GNN generalization.

Published as a conference paper at ICLR 2025
TOWARDS BRIDGING GENERALIZATION AND EXPRES- SIVITY OF GRAPH NEURAL NETWORKS
Shouheng Li Floris Geerts", Dongwoo Kim', Qing Wang'
School of Computing, Australian National University, Australia
2 Department of Computer Science, University of Antwerp. Belgium
CSE GSAL POSTECH, South Korea
4 Data61, CSIRO, Australia
shouheng. li@anu. au, floris set.eeetttttttrerrrrerr dongwoo k m@@postechh.ee kc.kk, qing. wang@anu edeaaaauuudduu....
ABSTRACT
Expressivity and generalization are two critical aspects of graph neural networks (GNNs). While significant progress has been made in studying the expressivity of GNNs, much less is known about their generalization capabilities, particularly when dealing with the inherent complexity of graph-structun data. In this work, we address the intricate relationship between expressivity and generalization in GNNs. Theoretical studies conjecture trade-off between the two: highly expres- sive models risk overfitting, while those focused on generalization may sacrifice expressivity. However, empirical evidence often contradicts this assumption, with expressive GNNs frequently demonstrating strong generalization. We explore this contradiction by introducing a novel framework that connects GNN generalization the variance in graph structures they can capture. This leads us to propose k-variance margin-based gencralization bound that characterizes the structural properties of graph embeddings in terms of their upper- bounded expressive power. Our analysis does not rely on specific GNN architectures, making broadly ap- plicable across GNN models. We further uncover a trade-off between intra-class concentration and inter-class separation, both of which are crucial for effective generalization. Through case studies and experiments demonstrate that our theoretical findings align with empirical results, offering a deeper understanding of how expressivity can enhance GNN generalization.
upper-bounded
real-world datasets, we
INTRODUCTION
Graph Neural Networks (GNNs) (Scarselli et al., 2008) have become pivotal in modern machine learning, anchored two main pillars: expressivity and generalization. Expressivity refers to a GNN's capacity distinguish between diverse graph structures, thereby determining the scope of problems it can address (Xu et al., 2019; Morris et al., 2019). Highly expressive GNNs can capture intricate dependencies, essential for tasks like molecular property prediction (Gilmer al., 2017), drug discovery (Gaudelet et al., 2021), and protein-protein interaction prediction (Zitnik et al., 2018), where minor structural variations have significant implications. Generalization, on the other hand, reflects a GNN's ability to transfer learned knowledge to unseen graphs. Given the diversity in graph structures, sizes, and complexities, GNNs that generalize well maintain consistent performance across varying datasets. Together, these properties enable GNNs to model complex graph structures while remaining effective across new, unseen data, making them invaluable for graph-based analysis.
Theoretically, trade-off is expected between expressivity and generalization: highly expressive models can capture complex graph structures but may overfit and generalize poorly without proper regularization. Conversely, models focused on generalization often sacrifice some expressivity to perform better across diverse, unseen graph structures. Recent work indeed shows a strong correlation between GNN's VC dimension and its ability to distinguish non-isomorphic graphs (Morris et al., 2023). A more nuanced theoretical analysis is needed, however. Indeed, empirical evidence frequently contradicts the above view. Highly expressive models often exhibit strong generalization performance

---

Published as a conference paper at ICLR 2025
in practice (Bouritsas et al., 2023; Wang et al., 2023). In the restricted context of linear separability, margin- based bounds offer partial aligmment between theory and practice (Franks et al., 2024), yet broader understanding of how expressivity influences generalization remains incomplete. This raises two key questions: (i) How does the structured nature of graphs affect GNN generalization? (ii) How does GNN's expressivity influence ity ability to generalize across tasks and unseen data? Addressing these questions is vital for ad advancing GNN applications in real-world scenarios.
Present work. Building on the foundational work of Chuang et al. (2021), we explore how the con- centration and separation of learned features, key factors in multiclass classification generalization, translate to graph-based models. Their bound, derived from vvvariance (Solomon al., 2022) and the expected optimal transport cost between two random subsets of the training distribution, motivates our adaptation to graph embeddings. Leveraging these insights, we extend their framework to capture the structural properties of graph embedding distributions and contribute the following:
For arbitrary graph encoders, including GNNs, we show that their generalization can be bounded in terms of the generalization bound of any more expressive graph encoder. This allows capturing structural properties of graph embedding distributions with respect to their bounding encoders.
Under certain margin conditions, we demonstrate that the downstream classifier generalizes well if (1) embeddings within class well-clustered and (2) classes separable in the embedding space in the Wasserstein sense, extending Chuang et al. (2021)'s results to graphs.
On the real-world PROTEINS dataset (Morris al., 2020a), empirically show how more expressive model influences generalization by measuring variance in graph embedding distributions.
We apply the empirical sample-based bound of Chuang et (2021) to graph classification tasks, verifying that empirical findings align with our theoretical insights, thus demonstrating the applicability of our approach to predict generalization.
Our results offer flexible framework for analyzing generalization properties of complex graph encoders via simpler encoders, such as those based on 1-WL, its higher-order variants k-WL (Cai et al., 1992; Grohe, 2017), homomorphism counts (Zhang et al., 2024), or F-WL (Barceló al., 2021), provided they upper-bound the encoders under consideration. Overall, we present versatile tool for evaluating whether increased expressiveness improves or worsens generalization.
2 RELATED WORK
Regarding generalisation of GNNs, Scarselli al. (2018) utilize VC dimension to study the gener- alization of an older GNN architecture, distinct from modern MPNNs (Gilmer al., 2017). Garg et al. (2020) show that the Rademacher complexity of simple GNNs depends maximum degree, layer count, and parameter norms, while Liao et al. (2021) develop PAC-Bayesian bounds relying on node degree and spectral norms; Karczewski et al. (2024) for extensions. Improved bounds using the largest singular value of the diffusion matrix are proposed by Ju et al. (2023). Transductive PAC-Bayesian bounds for knowledge graphs are discussed by Lee et al. (2024). Random graph models are leveraged by Maskey et al. (2022), who show GNN generalization improves with larger graphs. Connections between VC-dimension and the 1-WL algorithm are made by Morris al. (2023), who bound it by the number of 1-WL colors. Levie (2023) provide bounds based on covering numbers and specialized graph metrics.
For GCNs, Verma and Zhang (2019) derive generalization bounds using algorithmic stability, with Zhang et al. (2020) focusing on single-layer GCNs and accelerated gradient descent. Zhou and Wang (2021) extend this to multi-layer GCNs, showing that generalization gaps increase with depth. Similarly, Cong et al. (2021) highlight this trend in deeper GNNs and propose detaching weight matrices to improve generalization. Further analyses of transductive Rademacher complexity using stochastic block models are offered by Oono and Suzuki (2020); Esser et al. (2021). Tang and Liu (2023) establish bounds involving node degree, training iterations, and Lipschitz constants, while Li et al. (2022) study topology sampling and its impact on generalization. Lastly, Franks et al. (2024) explore margin-based bounds.
2

---

Published as a conference paper at ICLR 2025
Moving to the expressivity of GNNs, MPNNs' expressivity is bounded by 1-WL (Xu al., 2019; Morris et al., 2019), showing the need for more expressive methods. Many such models have been put forward. For example, the F-MPNNs (Barceló et al., 2021) enhance expressivity via homomorphism counts, similar to Bouritsas et al. (2023). Homomorphism counts have become a popular mechanism in graph learning (Nguyen and Maehara, 2020; Welke al., 2023; Zhang et al., 2024; Jin et al., 2024; Lanzinger and Barcelo, 2024), and will be central to our analysis. Additional discussion on related work can be found in Appendix A.
PRELIMINARIES
Graphs and homomorphisms. We begin by considering undirected graphs G = (Va, Eg), where Ve represents the set of vertices and Fg S Ve VG forms the edge set, symmetric relation. For any vertex u E Va, its set of neighbors is given by Na(v)) == {u E Va (u,u) E Faj. A homomorphism from a graph G to another graph H is a mapping h VG + VH such that each edge (v, w) E Eg is mapped to an edge (h(v), h(w)) E Éи. An isomorphism, on the other hand, is a bijective function f : VG + VH that preserves adjacency: (v,w) E Eg if and only E Eg. The notation Hom G, H) refers to the number of homomorphisms from G to H, and the function Homa(.) maps any graph to Hom(G, H). Given a sequence F (Fi, ..)...) of graphs, we define (- as (Homp, (-), Hom (.)...). a tuple of homomorphism counts. graph invariant is any function & on graphs that is unchanged under isomorphisms, i.e., {(G) {(H) when G and H are isomorphic. For instance, Homy(.) serves as a graph invariant for any graph sequence F. Moreover, we introduce the concept of rooted graphs, where each graph G" has distinguished root vertex r E Vg. For two rooted graphs G" and H homomorphism must also map the root r of G the root of H. The notation Hom p~ captures the number of homomorphisms Hom(F", G²) from rooted graph J" to any rooted pair (G, v), where v is treated as the root of G. Similarly, Hom_e-() (-) is defined, capturing important vertex invariants for pairs (G, v). We illustrate some of the above concepts by examples in Appendix B.
Graph neural networks and WL. We extend the above notions to featured graphs G (Vg, Eg, Sa), where each vertex is endowed with feature vector Co VG Edo of some fixed dimension dg E N. We focus on Pessage--aasiigg Neural Networks (MPNNs) (Gilmer et al., 2017). enhanced with homomorphism counts from F (Barceló al., 2021). For a sequence of rooted graphs F = (FT, ..),,,,, .), the initial vertex representation for a vertex E Va in an J-MPNN is:!
3 (G, v) = (Sa(v), Hom G"), Hom F2, G*). G")....).
At each iteration (layer) 0 < f < L, this representation is updated as follows:
oftt) (G.)) = up (0 v), agg ( (G,u) | Nc(()))).
where B denotes multiset, and ( and agg are differentiable update and aggregation functions, respectively. After L iterations, a final pooling operation produces the graph-level represen- tation: (G) ;= readout( ( (G,e) v) E Va)),, with readout being a differentiable function. This construction defines a graph invariant. We also consider the F-WL algorithm, as introduced by Barceló et al. (2021)
extension of the one-dimensional Weisfeiler-Leman algorithm. The F-WL algorithm iteratively updates vertex colors. Initially, each vertex is assigned a color:
wl 100 (G, v) = (Sa(v), Hom G"), (Fm, G").....
At each iteration < E L, new colors are assigned as follows:
w (G, (wl (G, v), 8 (G, (uEN)())))
The final graph invariant is wl w/ (G) : { (G. | VG}. This invariant can be viewed as a color histogram in No, where is the number of distinct colors, assuming canonical ordering colors. When the list F is empty we recover the 1-WL algorithm (Weisfeiler and I Leman, 1968).
We ignore vertex features when considering homomorphisms.
3

---

Published as a conference paper at ICLR 2025
Graph encoders. Graph encoders are mappings from the set 9 of graphs to some embedding space 2, typically residing in RR, for k E N. The space Z is assumed to be a metric space for a metric dz. Examples of graph encoders are Hom F-MPNNS and F-WL, for any sequence F of graphs and number I. E N of iterations. We will develop bounds for general graph encoders.
Wasserstein distance. Let ||-I| denote the Euclidean norm in R4, for some d N. Given two distributions f and on RS the p- w-Wassesstein distance between μt and v is defined as:
Wp(u, =etl(a.))
inf (B(a.y))= || 2l(") 1/p "
where I1(, 1/) denotes the set of all couplings of and V, i..., distributions π on Rd x Id with and v as marginals. In what follows, we restrict our attention to the 1-Wasserttein distance.
GRAPH ENCODERS: KEY PROPERTIES
Before presenting our generalization gap bounds, we first establish crucial properties of (classes of) graph encoders that play a significant role in our analysis. In particular, we revisit the relationship between classes of graph encoders in terms of their distinguishing power, i.e., their ability map distinct graphs in G to distinct embeddings in their embedding spaces.
Definition 4.1. Let Φ 9 + ZΦ and ø' 9 > Z be two graph encoders. We say that & bounds d' in distinguishing power, denoted by Φ E ø', if for any two graphs G and H in g.
(' + (HH) (GG) o(H).
In other words, ø' cannot distinguish more graphs than Φ
Similarly, for classes T and o' of graph encoders, we say that & bounds ' in distinguishing power, denoted by & = &' if no encoder &' can distinguish more graphs than any of the encoders in o. That is, for all ø' E Φ', there exists Φ E & such that 6 _ 6'. If both 4 C &' and 4' _ ④ hold, then we write = G and say that both classes have the same distinguishing power.
From the seminal papers by Morris et al. (2019) and Xu et al. (2019), we know that MPNN(L) = 1-WL((), where the argument L refers to the number of layers/iterations F-WL(L) (Barceló et al., 2021). It is also known that Homy _ MPNN where T consists of all trees (Dell et al., 2018), and HomT C J-MPNN(L) where T o F consists of trees joined with copies of graphs in F (Barceló et al., 2021). Recent work by Neuen (2024) provides valuable insights comparing Hom for various F (see also (Lanzinger and Barcelo, 2024)).
Fimilarly.-MMPNN
When graph encoders are comparable in terms of distinguishing power, one recover the least expressive encoder from the most expressive one. This is formalized in the following lemma. The proofs of the results in this section can be found in Appendix C.
Lemma 4.2. Let & 9 Z4 and 6' G + Za be two graph encoders such that Φ = o' holds. Then there exists a function Z + Zay such that o' = fo @.
As an illustration, consider an L-layer MPNN M; we know that 1-WL(L) E M. now suffices to define f such that it maps a color histogram M(G), the embedding of by M. where is a graph satisfying (1))))
(G) = h. This is well-defined due to the earlier observation that 1-WL(L) E M.
For some classes of graph encoders, the function satisfies additional desirable properties, explain next. We say that a graph encoder Φ G + Zg is B-hounded if dz, (ø(G), (H)) < B for any G, H E G. Furthermore, graph encoder Φ : + Zg is S-separating if dzz (Ø(G), o( ()) 2 S for any G, H. E G such that (G)) # ((H). We recall that function f between metric spaces Z and #2).
2' is Lipschitz with constant Lip(J) if for any 21, 22 E Z, dz (f(=1), [(z))) < For simplicity, we set Lip(S) = xo when f is not Lipschitz for any finite constant.
Proposition 4.3. Let G + Zg be S-separating graph encoder and o' G Zy be B-bounded graph encoder such that ò _ H. Then ø' = f o @ for a function f Z + Zω which is Lipschitz with constant Lip(f) = B/S.
There are plenty of bounded graph encoders; indeed. just consider any GNN employing bounded- range activation functions such as sigmoid, tanh, truncated ReLU (Hamilton et al., 2017). Other
4

---

Published as a conference paper at ICLR 2025
examples include normalized homomorphism count vectors color histograms (Lovász and Szegedy, 2006). Similarly, any graph encoder mapping graphs into a discrete subset of IR is S-separating, For example, any Hom, is 1-separating since whenever (G) & Hom=(HH, there exists an F F such that Hom F, G) o Hom( F. H). Since the latter are natural numbers, and assuming a discrete metric d, di [Ho (F' G), Hom (F, H)) 2 1. A similar argument applies to graph encoders based on 1-WL or its higher-order variant k-WL.
Our generalization bounds use the I-Wasserstein distance between distributions, as we will see shortly. Using Proposition 4.3, and in particular the Lipschitz property, we relate the Wasserstein distance between the pushforward distributions of distributions of & on the embedding spaces of the graph encoders. Formally, let G - Zø be a graph encoder and let y be distribution g. Then the pushforward distribution of μ under Φ is the distribution on 2g. given by
(z(1))2)= = 1d(G E 9 ((G)) = =]),
where 2 is an element in the embedding space Zz. We can now state the proposition.
Proposition 4.4. Let Φ 9 Za and ạ¹ Zy be two graph encoders such that &' = =sor d. Then for any distributions and v' over 9, we have that the inequality Wi (d((V) (,(11) S Lip(f) Wi (o( oz(1/) holds.
We remark that the inequality above becomes vacuous when f is not Lipschitz and hence Lip(S) oo.
Corollary 4.5. Let di : + Za be an S-separating graph encoder and &' G + Zn a B-bounded graph encoder such that Φ = o' holds. Then for any distributions v and v' over G, we have
(1( o((()) $ (B/S)
Indeed, Proposition 4.3 implies Lip(J) = B/S. Combined with Proposition 4.4, this gives W1 ((d((v) & Lip(f) (1( (y(1))) = (B/S) (i
As an example, consider B-bbuuded graph encoder @ : + Z, which is bounded distinguishing power by the 1-separating encoder Homy, for some sequence F of graphs. Then for any two distributions v and v' on 9, we have
(i(or()) (x())) (B/1) (i
(Hom)=)((z))).
More broadly, our observations suggest that the variance of embedding distributions in ZØ. produced by a complex graph encoder, can be effectively upper bounded by the variance of simpler, combinato- rial graph invariants-sun homomorphism counts, Weisfeiler-Leeme descriptors, provided that the latter bound the former in terms of distinguishing power.
tests, and other structural
GENERALIZATION ANALYSIS
We use the setup from Chuang et al. (2021) but translated to the graph setting. More precisely. let G represent the input space of graphs, 2 the embedding space in T& for some d E N, and K classes. We define a set of graph encoders
y (1,..., K) the output space consisting + = to: + Z} and set of predictors v { = (VI...., "uy,....,,,, vx)) Z + gK J. A score-based graph classifier & & simply returns arg max wh (o(G)) on input G. The graph encoders in are assumed to be graph invariants, such as, e.g., ....FMM F-MPNNs, F-WL, or Hom
We define the margin of a graph classifier vp & for a graph sample (G,y) E g x as Pe (o()(G),)) == (d()) max by (o(G))
N' y'
The graph classifier th & misclassifies G if pv (o(G), < Let μ be distribution over y, and S = {[G,, me be a set of m graph samples drawn i.i.d. from μ., i.e., S ~ nr" The empirical distribution ps defined as ps := 1 Em &(G..))) where &(G...)) denotes the Dirac delta measure centered at (G,, v.). The expected zero-one loss R2 o o) and the 7-margin empirical zero-one loss Rr, s, o Φ) are defined as Ry (1b o Φ) E(G.via ( and R o Φ) = EGG I [
We aim to bound the generalisation gap (xb a Φ)- R (rb ()) for the graph classifier o db
5

---

Published as a conference paper at ICLR 2025
5.1 GENERALIZATION BOUND
We are now ready to present the generalization bounds. Our results build on the margin bounds of Chuang al. (2021), which are themselves based on generalized notion of variance that involves the Wasserstein distance (Solomon et al., 2022). This notion more effectively captures the structural properties of the feature distribution. Crucially, we fully exploit the properties of graph encoders and, in particular, use Proposition 4.4 to derive an upper bound the generalization gap of any graph encoder Φ g 2Φ in terms of any graph encoder bounding & in distinguishing power!
In order to formally state our results, some additional definitions are needed. Recall that we consider graph classifiers (V1,.... , 42)) a & where Φ G + Z& is graph encoder and the predictor & = (111-... $bx) consists of functions v/y : Z - IR. Recall also that the output space y = (1,.... K} and that is a distribution over G x V. We denote by [Ar the marginal distribution on G. i.e., Me (G) J[G, y)dy and by My the marginal distribution on V/ i.e, My (cy(c) == [-[[(a u(x, c)dr. Then, for each E yr Pe (G) is the conditional distribution on G defined by p(G, c))p,(c).
Theorem 5.1. 7 O and a graph encoder Φ - ZΦ. x: - 2x be graph encoder that bounds 6 in distinguishing power; i.e., - Φ. Then, for every distribution i on G y. for every predictor &o = (Vey key and every 8 E (0,1), with probability at least 1 - ô over all choices of S ~ pm,, we have that the generalization gap Ry Φ) s (1b b) is upper bounded by
Lip (pa((,)) Lip(S) Ey Tm (Ma(He))))) d4 (1
log(1/8)
Exowpiy
(t)
?
2m
where & o λ and for each e V, me denotes the number of pairs (G,c) in S. Also, recall that for T ~ pete Pe,T is the empirical distribution P.,T == "GET 8g: similarly for He,
The proof is consequence of Theorem 2 in Chuang al. (2021) and Proposition 4.4. As also observed by those authors. the expectation term over T, 10== is intractable in general. To address this drawback, Chuang et al. (2021) show how to estimate the expectation by means of sampling, provided that encoders are B-bounded. A similar approach works in our specifically, we show in Appendix D how an efficient, sample-based bound can be used instead of the theoretical bound presented Theorem 5.1. Notably, this practical bound is used in our experiments.
well. More
Theorem 5.1 highlights several key factors that influence the generalization of graph classifiers: (i) the learning behavior of the predictors th, captured by Lip (p e)): (ii) the learning behavior of graph encoder ø, relative to X, described by Lip(f); and (iii) the variance of graph structures, in the Wasserstein distance Wi (As(Ho,T), A >x(,,,))) for graph samples T,P T =
5.2 CONCENTRATION AND SEPARATION
S (m/d1/) (Chuang et al., 2021). large sample size m and a small dimension d of the embedding space 2, lead to smaller generalization bound. For instance, when μ is concentrated on graphs (Morris et al., 2023)-i.c., the 1-WL test requires only a small number of colors for the graph's 's vertices combinatorial graph encoders like Hom and F-WL(L) can operate spaces. This observation is consistent with earlier findings (Kiefer and McKay, 2020; Garg et al., 2020: Liao et al., 2021; Ju et al., 2023; Cong et al., 2021; Esser et al., 2021; Morris et al., 2023) about the effect of graph size, degree, and maximum degree on generalization performance.
In terms of concentration, since E T.iT" [Wi (M((ee) >4((,,))) (1
with low color complexity
Of particular interest is the case when the bounding graph classifier X is assumed to have a large margin. A larger margin is generally associated with better generalization (Elsayed et al., 2018; Chuang et al., 2021). we assume the margin is satistied for & o X, for all graph samples, and for each Y, the predictor the ạ Lipschitz, then (see Lemma 10 in Chuang et al. (2021)) have
S min Wi(Ap(u)), )4(pe))) (min Lip( cy ofe
cEy
By replacing 1/4 in Equation (+) by this bound, we obtain Proposition 5.2, see Appendix D for details. We hereby revealing trade-off between concentration and separation.

---

Published as a conference paper at ICLR 2025
Initial Vertex Colors
Afler One Iteration
Graph Embeddings (Difference)
Wasserstein Distance
G
G'
G
G'
1-WL
4.796
(b) Ct-WL
G
4.123
(c) KL
5.000
Table 1: Two graphs G and G' with the initial vertex colors (including input vertex features and homomorphism counts) and the vertex colors after iteration, and the dimension-win difference [G) >x(G") and Wasserstein distance Wi Wi(A (Ar()) >²(G") between their graph embeddings for three models: (a) 1-WL, (b) CI-WI, and (c) KL-
Proposition 5.2. Under the same assumptions as in Theorem 5.1, but with the additional requirement that the predictors the in th are Lipschitz, and that the bounding graph classifier X has large margin, i.e. (x)) y) 2 for all (G.y) ~ μ. then for any E (0, 1), with probability at least 8 over all choices S ~ nt, we have that the generalization bound given in Theorem 5.1 1 is lower bound by
Lip(f) Bewwy (ip(pp((.c) [wss (.(He))),(((a..))))
), (min.ey Lip(wa)) (min Wi Ap(He))
log(1/0)
2m
The above proposition highlights that, to achieve low generalization bound, is crucial to ensure good concentration between embeddings of the same class, i.e.. Wi():(Me,r) )4(M,,z)), while maintaining large separation between emheddings of different classes, i.e., Wi Wi (>y(Hc),))(()) where # c'. This can be achieved when À learn embeddings in the "right" directions, where embeddings of different classes are "more separated" than those of the same class, or when the distribution j is concentrated on graphs for which this separation happens for X.
Remarks. In our bounds, identify three Lipsehitz constants: ( c)). Lip(t))), and Lip(f). First, note that (s.c) depends on th. and therefore it is Lipschitz in its first argument if the is Lipschitz. For simplicity, assume that the predictor Lipschitz constant 1. For general v Lip(pe(s,c) can be approximated empirically using the Jacobian, suggested by (Chuang al., 2021).
(#e)eey softmax function with
Furthermore, Corollary 4.5 states that the connecting function f between the graph encoders À E Lipschitz with constant B/S, provided that Φ B-bounded and is separating. Therefore, when é is B-bounded, Lip(f) decreases as S increases. We also note that S can increase with added expressivity in which enhances its separation ability. In practice, both B and can be computed empirically, We discuss the effect of added expressivity of À in more detail in the next section.
CASE STUDIES
In this section, we present case studies to illustrate how our generalization bound captures complex scenarios the generalization of graph encoders, influenced by their model expressivity and driven by two key factors: intra-class concentration and inter-class separation. Recall, discussed in Theorem 5.1 and Proposition 5.2: (i) intra-class concentration, which quantifies the variance of graph structures within class, measured by the Wasserstein distance W; (A4 (Mc,T) (x()= for graph

---

Published as a conference paper at ICLR 2025
samples T, T p and (ii) inter-class separation, which measures the distinction between classes, represented by the Wasserstein distance maxe,e' W1(22(H)) >:(ee))))))
For simplicity, consider the following graphs {G, G", H,, H') from the PROTEINS dataset (Morris et al., 2020a), uniformly selected by the distribution μ.,
G
G'
H
H
Here, G and G' belong to the class while H and H' belong to the class c', where * d. Assuming the margin condition satisfied for all classes, including and d', and that embeddings of graphs within each class cluster around the embeddings of G, G', and H, H', we estimate Wi (A4 (x(().))) using Wi Wi (Aa(G), Az(")) Since there are only two classes this dataset,
we estimate ef eVoete Wi (Ne(Me),, (p(e)) by Wi by C"),
For the bounding graph encoders A, we use 1-WL as the base model. Then, following the approach by Barceló et al. (2021) ) we consider two simple rooted graphs L and X and append their homo- morphism counts (om and Hom(2... -) to the vertex feature of each rooted pair (- v) in the graphs G. G", . and H', respectively. This leads to slight increase in model expressivity, compared with 1-WL, allowing us to analyze how these differences impact key factors generalization. We refer to these two graph encoders as C4,WI,, where homomorphism counts of I are added, and K4-WL, where homomorphism counts of M are added, respectively. Table presents graphs G and G' with their initial vertex colors and the updated colors after one iteration, where the Wasserstein distance Wi (Ax(G), >p(G") estimates the intra-class concentration class c. As model expressivity increases from 1-WL to C1-WL and WLL two distinet scenarios for intra-class concentration arise:
(1) More expressivity leads to better generalization: Compared to the graph embeddings from 1-WL, incorporating C₁ improves intra-class concentration. The homomorphism counts of C4 reduce the variance between graph embeddings shown in Table 1, resulting in distance of 423, smaller than 4.796 for 1-WL.
(2) More expressivity leads worse generalization: When K4 is used, the graph embeddings of G and G' yield a distance of 5.000, which is larger than its 1-WL counterpart 4.796. Compared to CL-WI., each dimension of the K4-WL embeddings has the same or larger magnitude, reflecting higher variance in the graph embeddings.
When measuring inter-class separation using Wi (p))) the models 1-WL, C1- and K4-WL WL achieve distances 4.582, 4.511, and 4.840, respectively. These results suggest a narrowing in the gaps of these models, compared to intra-class concentration alone. The trends in inter- class separation may change depending on the graph structure. For instance, if graphs of class d' cluster around the embedding of H', i.e., estimating Wi (Ar(Me).Ag(ue)) with μec = {G, G') and He = {H'), the reverse trend may occur, with 1-WL achieving a distance of 4.796 and K₃-WI achieving 4.583. This highlights the importance of inter-class separation balancing a model's generalization performance alongside intra-class concentration.
7 EXPERIMENTS
Tasks and Datasets We conduct graph classification experiments on six widely used benchmark datasets: ENZYMES, PROTEINS, and MUTAG from the TU dataset collection (Morris et al., 2020a), as well as SIDER and BACE from the molecular dataset collection (Wu et al., 2017). For SIDER, which comprises classification tasks, we focus specifically on the 21 task. Each dataset randomly divided into training and test sets following a 90%/10% split.
Setup and Configuration runs to report the mean and standard deviation of the results. Consistent with the setup in Tang and Liu (2023); Morris et al. (2023): Cong et al. (2021), 1), we eliminate the use of regularization techniques such dropout and weight decay. batch size of 128 is utilized, with learning rate set to 10 and the hidden layer dimension fixed at 64. The margin loss function is employed with a margin parameter
Each classification task is trained for 400 epochs, with five independent
y 1. To compute the generalization gap, utilize the sasple-based variant of the bound as
8

---

Published as a conference paper at ICLR 2025
Table 2: Left: Graph classification gaps and bounds with different numbers of MPNN layers. Right: Correlation matrices of empirical gaps and bounds.
Datasel
ENDYYMS
# Layers
ENZYMES
PROTEINS
MUTAG
SIDER
BACE
Loss gap
0.248
0.029aas015
-0.070sa007
0.037s0003
0.01810017
Our Bound
7.926m1
20
1.216 51
0.51 1+0
1.479
VC dimension
586
929
960
621
VC bound
1.302a0000
1. 1.29220001
1.100
1.30240000
1,30110000
CepOura
PAC bound
3,48
5.04
3,06
52.39
21.525
PPO TENS
Loss gup
0.242
0,032saumo
-0.074:0mr
0.038a
0.037
Our bound
7.425an02
1,404a0.14
1.247.0018
0.620an463
1.7291m25
900 VC D0
1
VC dimension
595
996
121
1300
1060
20
bound
1.302-000
1.292
1.302+0000
1.30240000
PAC bound
12.75
31.94
8.17
132.79 79taa12
$1.573
Cop VC IMC
Loss gap
a.237
0.025
-0.088
0.038
0.03210001
MUUWA
Our Bound
6.513
1.421
1.64929.18
0.409
1.789
196 VC Onn OR
VC dimension
595
996
135
1309
1069
VC hound
1.302+0mm
1.2934cmm
1.286-omm
1.302+n000
1. 1.302+00000
PAC bound
56.98
276.78
21.96a
341.04
124.605
Loss gap
0. 0.235a0008
0.027am.05
0.073
0.03610001
0.022xn630
Our Bound
6.825eo
1,4344,227
15535
1. 1.686+1 171
Gap Ourn VC PAC
VC dimension
VC bound
1.302a0000
595
1.292a0001
996
1.291
139
1.30210000
1309
1.30240000
1093
SWG Ovn Opp
SIDCR
1.0
PAC bound
308.43
2331,63
57.69
845.62
310,732
-55
Loss gup
0, 0,256auu
0.020ssuum
=0.07
0.035
0.020#tuzo
Our Bound
6,384ka0313
1.308
1.773
0.3692n172
1.6621n.20
0.
5
VC dimension
595
996
139
1309
1093
hound
1.302=m
1.292
1.292=amm
1.302+0000
1.302+0000
Cup
PAC bound
1615.10
17992.81
155.74
2179.21
744.08
Loss gap
0.264a0ns
0.030
-0.078:00i
0.034an008
0.022xn016
P0c VC Surs
Our Bound
6.
1.340a2331
1.627:2038
0.3534n155
1.78520227
-85
VC dimension
595
996
139
1309
1093
VC bound
mm302+0m
1.292eam
1,291
1.30240000
1.302+5.70
PAC bound
8931.00
135762.52
410.31
5254.88
1860.94
VC. PAC
outlined in Theorem 1. as given in Theorem D.2 of the appendix. For the graph encoder c, we adopt both MPNNs and J-MPNNs, with expressivity constraints defined by 1-WL and F-WL, respectively, as described in Section 4. The predictor (=)) is modeled using the softmax function, which has a Lipschitz constant of 1 (Gao and Pavel, 2017), ensuring that (ip(p c)) is also 1. We estimate Lip(f) [2, (o()) as: Lip(J) max Tzy (X(G),((H) where G and H are sampled from the training set Grain. For all experiments, we set the confidence level 5 to 0.1, yielding bounds with high probability.
7.1 RESULTS AND DISCUSSION
How well can the proposed bound predict the generalization ability of MPNNs? We compare our bound with empirical generalization gaps, measured by loss, while varying the number of layers (see Table 2). For comparison, we include the VC bound from Morris et al. (2023), based on unique color histograms (VC dimension) from 1-WL. and the PAC-Bayesian bound from Ju et al. (2023). Changes in loss gaps are shown in Figure 2 of Appendix F. Our bound strongly correlates with empirical gaps across datasets and depths, effectively predicting generalization eтrors and reflecting performance changes as model depth increases. In contrast, the VC bound stabilizes after three layers and remains nearly constant, failing to capture the observed variations. Furthermore, our bound surpasses the PAC-Bayesian bound in both tightness and correlation to empirical gaps, notably on deeper MPNNs, since the PAC-Bayesiaa bound grows exponentially with the number of layers. Similarly, our bound is less vacuous compared to other bounds, such as those proposed by Garg et al. (2020); Liao et al. (2021), which tend to be on the order of 10a.
We further evaluate J-MPNNs across different homomorphism patterns, as shown in Figure 1. Here, Pa. Kn, and C22 denote n-path, n-clique, and n-cycll graphs, respectively, and "no pattern" refers to the MPNN without a specific pattern. Overall, the generalization bound aligns with the empirical gap across patterns, with some exceptions in ENZYMES. In ENZYMES, cycle patterns yield larger gap than cliques or paths, whereas in PROTEINS, paths and cliques increase the gap and cycles reduce it. These variations are largely captured by the corresponding bounds.
Why does more expressive power sometimes lead to better generalization? In Figure 1, we observe contrasting cases where increased expressivity worsens generalization (ENZYMES) and

---

Published as a conference paper at ICLR 2025
PROTEWS, byerNPKN
PROTERS blayer MPMM
ENZYNES, d:lye
ENZYINES, НРиN
patten
0
PLP.PLPs
30 02
3.0
10
10
0.4-
0.4
Ke
0.
0.2
0.2-
Gep
Bound
Gaa
Bound
Bound
GeD
Bound
ENZYMES
PROTEINS
ENZYMES
PROTEINS
0.4
C,C.C.CC
patten
0.04
1/6
6.0
S
4.5
-06
0--
3.0
Layors 3 Loss gops
Layers Bounds
3.0
Layers-3 distance
Layers Lip())
Layers 3 distance
Layers 3 Lifff)
0.0
Loss gaps
Bounds
Figure 1: Top: Loss gaps and bounds of different patterns. Bottom: Loss gaps, bounds, Wasserstein distance and Lip( of different layers. The data sets used are PROTEINS and ENZYMES.
improves it (PROTEINS). To explore this further, plot the changes of two major factors from the proposed bound in Theorem D.2: the I-Wasserstein distance and Lip(f), both shown in Figure 1. The 1- W-Wassesttein distance (W1) is computed as: 3 Σÿ= Wi Wi (DE((()TTT)) graph classes. We plot these factors over four layers for both MPNN and (Ca, C., Cs. Co -MMNN. We observe that the inclusion of homomorphism counts worsens generalization in ENZYMES but improves it in PROTEINS. This can be attributed to the joint influence of the Wasserstein distance and Lip(f)) In ENZYMES, both the 1- I-Wasserstein distance and Lip(f) increase slightly when homomorphism counts are added. While this additional expressivity leads to better separation between graphs, in ENZYMES, this increased separation hinders the ability to achieve good concentration within each graph class, ultimately worsening generalization. In contrast, for PROTEINS, although the inclusion of homomorphism counts leads to greater graph separation, it also slightly reduces the 1- W-Wasersteinn distance within each class, allowing for better concentration. This improved separation significantly reduces Lip(f), resulting in enhanced generalization.
(e((e.))) averaged over all
Can generalization be improved by controlling the Lipschitz constants? Last but not least, since Lip(f) plays a crucial role in the proposed bound, we aim to investigate whether controlling Lip(.) serve effective strategy to enhance generalization. A straightforward approach to control Lip(S) is through normalization techniques. As demonstrated earlier, normalization effectively bounds the diameter of (p)), which, in turn, constrains the encoder's boundedness and subsequently Lip(S). To test this, we apply 1 ly-normalisation in the last layer of the MPNN. See Table 3 for results. is evident that normalization reduces the generalization gap across all datasets. This improvement is also reflected in the computed bounds. Interestingly, the least improvement is observed in the SIDER dataset, where Lip(f) is already relatively small, and the embeddings are well-concentrated even before normalization. This suggests that the impact of normalization is more pronounced when Lip(/) is large or when the embeddings are not already well-concentrated.
CONCLUSION AND LIMITATIONS
In this work, we examine the generalization of GNNs from a margin-based perspective, based on the work by Chuang et al. (2021). The bounds use 1-variance and optimal transport to analyze graph embeddings. We establish a relationship between generalization and the expressive capacity of GNNs, deriving generalization bound that demonstrates how well-clustered embeddings and separable classes lead to improved generalization. Through case studies on a real-world dataset, we empirically validate these theoretical findings. We also apply empirical sample-based bounds to graph classification tasks, confirming that our theoretical results align with empirical evidence. Our work enables analyzing the generalization of graph encoders through their bounded expressive power.
Nonetheless, our work has some limitations. While we validate the framework on real-world datasets, further large-scale studies across wider range of datasets and applications are needed to fully establish the proposed approach's 's general applicability.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This research was supported partially by the Australian Government through the Australian Research Council's & Discovery Projects funding scheme (project DP210102273) and by the National Research and
Foundation of Korea (NRF) grant funded by the Korea RS-202300211286).
REFERENCES
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In Advances in Neural Information Processing Systems, volume 34, pages 25280-25293, 2021.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. International Conference on Learning Representations, 2022.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trans. Pattern Anal. Mach. Intell., 45(1) 2023.
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389 410, 1992.
Ching- Yao Chuang, Youssef Mroueh, Kristjan Greenewald, Antonio Torralba, and Stefanie Jegelka. Measuring generalization with optimal transport. In Advances in Neural Information Processing Systems, pages 8294 8306, 2021.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. In Advances in Neural Information Processing Systems, pages 9936-9949, 2021.
Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In International Conference Machine Learning, pages 255-262, 2010.
Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets Weisfeiler and Leman. International Colloquium Automata, Languages, and Programming, pages 40: 40:1-40:14 14, 2018.
Gamaleldin Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. In Advances in neural information processing systems, volume 31, pages 850-860, 2018
Pascal Mattia Esser, Leena C. Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation graph neural networks. Advances in Neural Information Processing Systems, pages 27043-27056, 2021.
Billy Joe Franks, Christopher Morris, Ameya Velingker, and Floris Geerts. Weisteiler-Leman at the margin: When more expressivity matters. In International Conference Machine Learning, 2024.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. CoRR, abs/ wbs//104/... 704.00805, 2017.
Vikas K. Garg, Stefanie Jegelka, and Tommi S. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, volume 119, pages 3419 3430, 2020.
Thomas Gaudelet, Ben Day, Arian Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy BR Hayter, Richard Vickers, Charles Roberts, Jian Tang, et al. Utilizing graph ma- chine learning within drug discovery and development. Briefings bioinformatics, bbbb),bb 2021.
11

---

Published as a conference paper at ICLR 2025
Floris Geerts and Juan L. Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2022.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference Machine Learning. volume 70, pages 1272, 2017.
Martin Grohe. Descriptive complexity, canonisation, and definable graph structure theory, volume 47.
Cambridge University Press, 2017.
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, volume 30, pages 1024-1034, 2017.
Tamás Horváth, Thomas Gärtner, and Stefan Wrobel. Cyclic pattern kernels for predictive graph mining. In International Conference on Knowledge Discovery and Data Mining, pages 158-167, 2004.
Emily Jin, Michael M. Bronstein, ismail ilkan Ceylan, and Matthias Lanzinger. Homomorphism counts for graph neural networks: All about that basis. In International Conference on Machine Learning, 2024.
Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang R. Zhang. Generalization in graph neural networks: Improved PAC-bayesian bounds on graph diffusion. In International Conference on Artificial Intelligence and Statistics, volume 206, pages 6314-6341, 2023.
Rafal Karczewski, Amauri H Souza, and Vikas Garg. On the generalization of equivariant graph neural networks. In International Conference on Machine Learning. 2024.
Sandra Kiefer and Brendan D. McKay. The iteration number of colour refinement. In International Colloquium on Aulomata, Languages, and Programming, volume 168, pages 73:1-73:19, 2020.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Matthias Lanzinger and Pablo Barcelo. On the power of the Weisfeiler-Leman test for graph motif parameters. In International Conference on Learning Representations, 2024.
Jaejun Lee, Minsung Hwang, and Joyce Jiyoung Whang. PAC-Bayesian generalization bounds for knowledge graph representation learning. In International Conference on Machine Learning. 2024.
Ron Levie. A graphon-signne signal analysis of graph neural networks. In Conference on Neural Information Processing Systems, 2023.
Hongkang Li, Meng Wang, Sijia Liu, Pin- Yu Chen, and Jinjun Xiong. Generalization guarantec of training graph convolutional networks with graph topology sampling. In International Conference Machine Learning, volume 162, pages 13014-13051, 2022.
Renjie Liao, Raquel Urtasun, and Richard S. Zemel. A PAC- approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2021.
László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory Series B, 96(6):333 2006.
Haggai Maron, Heli Bam-H Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
Sohir Maskey, Ron Levie, Yunscok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In Advances in Neural Information Processing Systems, 2022.
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 Intelligence, volume 33, pages 4602-4609, 2019.
12

---

Published as a conference paper at ICLR 2025
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 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020), 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, volume 33, 2020b.
Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe WL meet VC. In International Conference on Machine Learning, volume 202, pages 25275-25302. 2023.
Daniel Neuen. pianomoophismm-dsiingiiihhh closedness for graphs of bounded tree-width. In International Symposium on Theoretical Aspects of Computer Science, 2024.
Hoang Nguyen and Takanori Maehara. Graph homomorphism convolution. In International Confer- ence on Machine Learning, volume 119, pages 7306-7316, 2020.
Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Advances in Neural Information Processing Systems, 33, 2020.
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, 2008.
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The Shnnik-Chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248 259, 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Justin Solomon, Kristjan H. Greenewald, and Haikady N. Nagaraja. k-variance: A clustered notion of variance. SIAM J. Math. Data Sci., 4())9977-778, 2022.
Huayi Tang and Yong Liu. Towards understanding the generalization of graph neural networks. In International Conference on Machine Learning, 2023.
Erik H. Thiede, Wenda Zhou, and Risi Kondor. Autobahn: automorphism-based graph neural nets.
In Annual Conference on Neural Information Processing Systems, pages 29922-29934, 2021.
V. N. Vapnik and A. Chervonenkis. note on one class perceptrons. Avtomatika i 'Velemekhanika, 24(6):937-945, 1964.
Vladimir Vapnik. Statistical learning theory. Wiley, 1998.
Saurabh Verma and 7hi-Li Li Zhang. Stability and generalization of graph convolutional neural networks.
In International Conference on Knowledge Discovery & Data Mining, pages 1539-1548, 2019.
Qing Wang, Dillon Chen, Asiri Wijesinghe, Shouheng Li, and Muhammad Farhan. N-WL: A new hierarchy of expressivity for graph neural networks. International Conference on Learning Representations, 2023.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. Neuchno-Technicheeee Informatsia, 2:12-16, 1968.
Pascal Welke, Maximilian Thiessen, Fabian Jogl, and Thomas Gärtner. Expectation-compllte graph representations with homomorphisms. In International Conference Machine Learning. 2023.
Asiri Wijesinghe and Qing Wang- A new perspective "how graph neural networks go beyond Weisfeiler-Lehmmnn.. International Conference on Learning Representations, 2022.
Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay S. Pande. Moleculenet: A benchmark for molecular machine learning. CoRR, abs/1703.00564, 2017.
13

---

Published as a conference paper at ICLR 2025
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for GNN expressiveness. In International Conference on Learning Representations, 2024.
Muhan Zhang and Pan Li. Nested graph neural networks. In Advances in Neural Information Processing Systems, pages 15734-15747, 2021.
Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yo Chen, and Jinjun Xiong, Fast learning of graph neural networks with guaranteed generalizabilty:: one-hidden-layer case. In International Conference on Machine Learning. 2020.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference Learning Representations, 2022.
Xianchen Zhou and Hongxia Wang. The generalization error of graph convolutional networks may enlarge with more layers. Nearocomputing. 424:97-106, 2021. 2021.
Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13)i447-i466, 2018.
A ADDITIONAL RELATED WORK
We provide additional references related to the expressiveness of Graph Neural Networks (GNNs). The connection with the Weisfeiler-Leman (1-WL) test has led to the development of high-order GNNs that surpass 1-WL and are bounded by the k-dimensional Weisfeiler-Leman test (k-WL) (Mor- ris et al., 2019; Maron et al., 2019; Morris et al., 2020b; Geerts and Reutter, 2022). The method by Morris et al. (2019; 2020b) is strictly weaker than k-WL, whereas the method by Maron et al. (2019) can match the expressiveness of &L. However, these higher-order GNNs incur significant computational costs, rendering them impractical for large-scale datasets.
Incorporating substructure counts has been shown to be an effective strategy for enhancing GNN expressivity beyond 1-WL. (Bouritsas et al., 2023; Barceló et al., 2021). Bouritsas et al. (2023) integrate isomorphism counts of small subgraph patterns into the node and edge features of graphs, while Barceló et al. (2021) employ a similar approach using homomorphism counts. Building this concept, Thiede et al. (2021) implemented convolutions on automorphism groups of subgraph patterns. Rather than directly using subgraph counts, Wijesinghe and Wang (2022): Wang al. (2023) propose integrating local structural information into neighbor aggregation. This approach suggests that the expressivity of the model increases with the subgraph pattern size and aggregation radius.
Taking a different approach, Nguyen and Maehara (2020) explore the use of graph homomorphism counts directly in convolutions without message passing, demonstrating their universality in approxi- mating invariant functions. Welke et al. (2023) propose combining homomorphism counts with GNN outputs in the final layer improve expressivity. Additionally, Bevilacqua al. (2022) represent graphs as collections of subgraphs derived from a predetermined policy. Zhao et al. (2022) and Zhang and Li (2021) extend this idea by representing graphs with a set of induced subgraphs. These methods are closely related to graph kernel techniques that utilize subgraph patterns (Shervashidze et al., 2011; Horváth et al., 2004; Costa and Grave, 2010).
Since the WL-based GNN expressivity hierarchy is inherently coarse and qualitative, Zhang et al. (2024) propose homomorphism-bass expressivity framework, which enables direct comparisons of expressivity between common GNN models. As 1-WL and k-WL have equivalent translations in homomorphism embeddings (Dell et al., 2018), both MPNNs and higher-order GNNs can be expressed using homomorphism representations within this framework. Given that homomorphism embeddings are theoretically matmoohhism-coopllee. this framework offers not only a unified but also complete description of GNN expressivity.
14

---

Published as a conference paper at ICLR 2025
B ADDITIONAL DETAILS OF SECTION 3
We provide some examples illustrating the key concepts introduced in Section 3.
Example B.1 (Homomorphism counts and graph invariants). Consider the following three graphs Fi, F2 and G:
F2 = X
G=
Suppose that we want to extract graph features from G based on the graph patterns F1 and F2- One way of doing so is by means of counting how many homomorphisms from the patterns to G exist. We recall that a homomorphism is just an edge-preserving mapping between the vertex sets. For example, here, one can verify that the number of homomorphisms from F1 to G' is 120, i.e. Hom G) = 120, and the number of homomorphisms from F2 to is 8, i.., Hom F2. G) = These homomorphism counts be used as features to enrich the data representation of G. The process maps to set numerical features derived from the counts. Importantly, this mapping is a graph invariant, meaning that if G' is replaced by isomorphic graph (one structurally identical to G), the homomorphism counts remain the same. Using homomorphism counts as features allows us capture structural information, making them valuable for tasks like classification or regression in graph-based machine learning.
Example B.2 (Rooted homomorphism counts and vertex invariants). Now consider the following three rooted graphs FT, F7 G":
=
F =
GO
The in the graph allow to connect homomorphism counts locally around each vertex. Indeed, for rooted graphs, the homomorphisms also have to preserve the roots. In this example one can verify that the number of homomorphisms from Fÿ G" 78, i.e., Hom(FT, of homomorphisms from F to G is 4, i.e., Hom F. GD) = 4. We can enrich the local graph structure around v in this way. The mapping that associates with graphs and vertices such rooted homomorphism counts is example of vertex invariant.
78, and the number
Example B.3 (Wasserstein distance). Finally we illustrate the notion of Wasserstein distance. Con- sider the four graphs presented in Section 6:
G'
H
H'
The vector representations of the four graphs after one iteration of 1-WL are
1, X(G) (1100311111000000001111.00000000
X(G") (0.100.0111100022.1.0..2.
A(H) = (10088.110.000000001100000.00
X(H') = (0, 10,10,0,,1,1,000,,,,
These lead to
||A[G) X(H)II 5.0990.
|A(G") A(H'' 4.7958.
||{[)) - A(HI')I 5.2915.
||AG') - -(HH 3.8730.
p (G, G') and H'. Then I(n,v) = {[( (F),
Thus, we have
Bew))-((...n.crrrr))) -vl = [[I((G) - X(X)II + I[X(G)) X(H'Il))
= 4.9474;
(1a,))(((), vl1 1 [[1 - [IX(G) ((H'II)
-4.8823.
15

---

Published as a conference paper at ICLR 2025
Since 4.5823 4.9474, we obtain
W(n, v) BBe.))-((GG.H))....... yll
1 - +(E')) -(HHI))
4.5823.
C PROOFS OF SECTION 4
Lemma 4.2. Let Φ 9 + 26 and Ø' : - Zωr be two graph encoders such that Φ E ø' holds. Then there exists a function f: Zs + ZΦ such that &' f
Proof. We define the function f 2 Zø, follows. Let E Z and G such that d(G) Then, define f(=) == d' E Zz. Observe first that f is well-defined. Indeed, if we take another G' E such that ((G') 2, then (GG) ((G)) and hence also ø' dG) ø' (G') f(2) since & C of by assumption. Clearly, f Φ d', by definition
Proposition 4.3. Let Φ 9 + 2g be an S-separating graph encoder and e' + Zy be B- B-bounded graph encoder such that 5.. Then o' f o for a function Z Zω which is Lipschitz with constant Lip(f)= = B/S.
Proof. We need to show that for any 2,z' Zg. d2, (((), (B/S) dz dz,(z,=') holds.
Clearly, if z' then also f()) = f(z') and hence d2 (f(2). = 0, for which the desired
inequality trivially holds. For z + z' and using that = -GG) and d(H) for some graphs G' and И in G, we know that S S (2,2)) and hence 1 < (1/S) dz, (2,2)) It now suffices to observe that dz (f(z), f(=') = dz (((())) = d2 (G). o' (H) S B, from which d2 (f(2). f22)) S (B/S) dz, (2, 2') follows.
Proposition 4.4. Let Φ : G Zo and ø' > Zy be two graph encoders such that ø' = food Φ. Then for any distributions v and v' over G, we have that the inequality Wi (d(()) o((1)) S holds.
Lip(f) Wi
Proof. We first show that f o ø' implies the fy(()(p)) ((( of the corresponding pushfor- ward distribution of any distribution μ om G. Indeed, this simply follows from the definitions. One the one hand, for I C Z
+(M(1)== : ())
On the other hand,
ft (e(((())) (1(() Z (f(2)
E))
The equality then follows from fo 6 ø'. We assume that f is Lipschitz-continuous with Lip(f) < oo (otherwise the inequality is satisfied by default and there is nothing to prove). We show that
Wi (1), (((1) < Lip(S) Wi (#=(n), (b(()).
Let (Zx)) be the set of I-Lipschitz functions on Z We use the Ceattorovic-Ruubistte dual form of W1, follows:
(b((())) = sup gEL,(Z,)
Eendr(w)l(())) E (v)
g(=) d(d)(n) (b())))=).
sup gELr(Z,)
2,
fog E (2) as well. Then, using our earlier observation about Note that if g E (2) then LI ogg pushforward distributions,
Wi (Ob(k) = (A)))
16

---

Published as a conference paper at ICLR 2025
g(2) (()) (a(((()))
sup g
2 ((2)df(((:(1) )+()))())
sup
geLi(Ze) 22
sup gELi(Ze)
((dy - (x)))22)
2
[ d(p (=)
sup = =Lip(s) DEL, (EL1(Z 22 Lip(f)
/ Mxx ())=)
sup S LLi(( hEL,(26) Lip(S) Wi (0b(k)
as desired.
D PROOFS AND DETAILS OF SECTION
We start by restating Theorem 2 from Chuang et al. (2021) using encoders & from some general set X' to Z.
Theorem D.1 (Theorem 2 in Chuang al. (2021)). Fix y O and an encoder X Z. Then, for every distribution μ. on X' x y. for every predictor ab = (dy)iey and every 8 E (0, 1), with probability at least 1 6 over all choices of S pm we have that the generalization gap Ry Φ) s 6) is upper bounded by
Lip (p)(,,c)
log(1/5)
Exc-py
E E..
(Wi de (n( +
2m
where for each E y, me denotes the number of pairs (X, c) in S. Also, recall that for T ~ p Po,T is the empirical distribution M..T Exer dx; similarly for Pe,f-
To obtain Theorem 5.1 we replace by and consider graph encoders Φ : : + Zo and X g + 2, such that À upper bounds é in expressive power. Then, Lemma 4.2 ensures the existence of f such that Φ = f À and Proposition 4.4 consequently implies Wi (6), (( s Lip(f) (Me,T), Φz (P,,r) for any T,T pete Plugging this into the bound above results in the bound given in Theorem 5.1.
While the bound in Theorem 5.1 is theoretically useful, the expectation term over T,P p is intractable in general. To address this drawback, we derive another bound in Theorem D.2, which be computed via sampling in practice and is the used in experiments.
Theorem D.2. Let (Tú, yz be pairs of graph samples where each Ti, pl |mme/2n
m Σ mm//nn. and (()) be the diameter of a space. For any Lipschitz continuous function f: 2 Zn such that o X, with probability least - 8 for samples S pm have
1og(2/6)
Ry (v x) Ry 0)
2m
c))
log log(2K/0) no mlmm// /2m]
Eo-py
wi (Ae(Me,TO), ( + =2A(A=(Ho))
The proof again consequence of Lemma 4.2 and Proposition 4.4, but this time relying on Corollary 6 in Chuang al. (2021). We note that the diameter will be bounded when B- B-bounded graph encoders are considered.
We conclude with the proof of Proposition 5.2.
17

---

Published as a conference paper at ICLR 2025
Algorithm 1: An algorithm to compute the bound in Theorem D.2
Input :d, mes n, Y K, S, A. & and Lp (Lipschitz constant (a()
Output :Bound
1.g < 0:
// Estimate Lip(f)
for all G.H H. E S and X(G) & X(H) do
[[((G) -(F))
4
L max(r, Ly);
end
<-
0:
for
4- ,.... do
We
+- 0:
for f- I,...,, do
Randomly sample {= 2m from graphs the class e S: // Compute 1- I-Wasserstein using the Hungarian method
10
We + we W1 (I J HTm +1);
end
W. f we/n;
AC f 0: I/ Estimate A(}2(1e)
15
for all G, H E S and G, H belong to the class c do
A. max(A |A(G)) A(H)ll;
17
end
b b= b +
Lr (we + 2D.
log(2K/0 8))
m_ 2n
19 end
[mme/2n]
log(2/0).
return
K
2m
Proposition 5.2. Under the same assumptions in Theorem 5.1, but with the additional requirement that the predictors the in th are Lipschitz, and that the bounding graph classifier X has a large margin, iee, P& (A()) y) 2 y for all (G, y) 14, then for any E (0, 1), with probability at least 8 over all choices S ~ jt" we have that the generalization bound given in Theorem 5.1 is lower bound by
Lip(f) BBowty
[wrs (((H (mingey Lip(Ha)) (min EM Wi (e((H)))xp(Hee))
log(1/0)
2m
Proof. Since we assume the margin y is satisfied for db o X, for all graph samples, and for each e E y, the predictor the E eb is Lipschitz, then (see Lemma 10 in Chuang et al. (2021)) we have
7 S min Wi(Ag(u)), (q(ue))) (min Lip()))). c cfc
cey
In other words,
mnyyy Ey Wi Wi(N((H)) Ag(Me) (mincey Lip( cyle
Furthermore, know from Theorem 5.1 that for every (0, 1), with probability least 1 over all choices of S nt we have that the generalization gap R2 Ø) R Φ) is upper bounded by
Lip (pp((cc)c (o) Lip(f) E TT.
log(1/8)
+
?
2m
18

---

Published as a conference paper at ICLR 2025
Since Lip(f) and c,ce) W1(As(He), A²(pe))) (mincey Lip(1>)) are independent of Myy
apte
we can take them out of the expectation, that is we rewrite the upper bound as
Lip(S) Berpy (ps(, Br. (ws (A
log(1/8)
2m
Finally, by replacing & with the lower bound (*) we get that the generalization upper bound is lower bounded by
Lip(pu(: B)) [wn A((He.)))(((oo)))) +
Lip(f) Bowwy
(og(1/0)
(mingey Lip( (min Wi (Ap(He), )p(Hte)))
2m
as desired.
E COMPUTATION OF GENERALIZATION BOUNDS
VC based bound (Morris et al., 2023): We use the classical bounds on the generalisation gap based the VC-dimension Vapnik and Chervonenkis (1964); Vapnik (1998). That is, with probability ò, the generalisation gap is bounded by
((log(2SS/D)) + log((/4))
S
where |S| the sample size and D the VC dimension. In our setting, results by Morris al. (2023) implies that D is bounded by the number of graphs, distinguishable by the hypothesis class. In our experiments, we computed the latter as the number of graphs in S distinguishable by 1-WL at each iteration.
PAC-Bayesian bound (Ju et al., 2023) We follow Ju et al. (2023) to compute the bound, that is, with probability 5, the generalisation gap is bounded by
C (maxda(maxx-- X A 221- I1 + 0 log(6 8-1) ΣV
S
SS/3/4
where is the number of MPNN layers. Buss is a cap on the value the loss function, is fixed Lipschitz constant depending the activation and loss functions, and [S] is again the sample size. Moreover, de is the second dimension of the weight matrix ((()) layer E, X is the vertex feature matrix G and Ag the adjacency matrix of G. For MPNNs, the Frobenius norm of (()).
= rz (( F where (|
Our bound practice, we estimate Lip(f) and (Ax(1te)) in Theorem D.2 using data in the training
sets, thus both be computed in ([ The I-Wasserstein distance be computed in ( m. )3) using the Hungarian method (Kuhn, 1955). Normally we have |S] << ( m, )²
2n
2n
mm//nn] and m. 1. So the total time complexity to compute the bound is O(( me )²) which is tractable most datasets. For very large datasets, practitioners can 2n
because S
choose to use smaller m. and a larger to reduce the computational cost. An algorithm to compute the bound sketched in Algorithm
F ADDITIONAL EXPERIMENTAL RESULTS
The results of graph classification with embedding normalization are shown in Table The empirical loss gaps are plotted alongside our bounds in Figure 2. In Table 4, we list the correlation coefficients between the empirical loss gaps and the three generalization bounds for different F-MPNN variants. Our bounds consistently show positive correlation with the empirical loss gaps, while the VC and PAC bounds show negative correlation most cases. The code implementation is available at https: /////////// thub. con/ sean leeennnnaa./e 111/hhmmmmmmmmm http/hhomeeeeee gen.
19

---

Published as a conference paper at ICLR 2025
Table 3: Graph classification gaps with different numbers of MPNN layers. The MPNN embeddings normalized.
Dataset
Layers
ENZYMES
PROTEINS
MUTAGi
SIDER
BACE
Loss gap
0.105an010
-0.118a009
L.001
0.013
-0.004aa010
Our bound
0.800
2.203e00134
1.101
1.137e0552
1.147
VC dimension
586
929
51
960
621
bound
1.302
1.292an001
1.100
1.302e0000
1.30
PAC bound
3.4820.01
5,0420.00
3,0620.05
52.39
21.525m1.02
Loss gup
0.098tm.ezz
-0.02320011
-00997
S.015
0.000
Our bound
0.586am
1.01620025
1.208
1.01720.44
2.089
VC dimension
595
996
121
1300
1060
bound
1.302
1.292:0000
1.302e0000
1.30220000
PAC bound
12.75ea
31.9441.9
8.17+012
132.7948
51,573=1841
Loss gap
0.1184m023
00027
0.083
0.030en008
0.006ea.05
Our bound
0.572
0.834+0015
0. 0.993
1,221 =0.977
1.16 1.16700610
dimension
595
996
135
1309
1089
VC hound
1.302+0000
1,293+0000
1.286
1.302e0000
1.302=0000
PAC bound
56.982106
276.78a0.00
21.9640.0
341.04219.9
124.605
Loss gup
0.129200007
-0.00420005
-0.0872a011
0.0262a.015
1.001
Our bound
0.573an.27
0.847an027
0.84822.055
1.03920.895
0.705
dimension
1309
1093
VC hound
1.30240000
1.292s0001
1.291
1.302ea000
1.302
PAC bound
308 43
2331063
57.69+185
845.62 6247511
3 310,732+12.50
Loss gap
0. 1.16990014
0.003=+005
0.086ea003
0.006eams
0.002=0.014
Our bound
0.575
0.713
0.799
0.923aa.
0.703mu012
VC dimension
996
139
1309
1093
VC bound
1.302a0.000
1.292an001
1.292a0.002
1.30220000
1.30220.00
PAC bound
1615. 10
17992.8
1a449.0
155.74as.ss
2179.2 1
744.08a3112
Loss gap
0.16 0.1692n.023
-0.002an.az
-0,10422.005
0.029
-0.01320.015
Our bound
0.603an.022
0.793an.136
0.778
1.192en:51
0.6792a018
VC dimension
1.30240.000
1.292:a0001
1,29
1.302e0.000
1.30220.00
VC hound
1.302+0000
1.292+u001
1,291
#0002
1.302enom
1.302=5 870
PAC bound
8931.00eou
135762.52a:909571
417
5254.88tnne 8845888
1860.944s.90 96
SIDER
PROTEINS
RACE
MUTAG
ENZYMES
1.8
0.45
Durbound
Bound vabue
0.05
0.03
0.01
0.04
-0.56
0.0
Layer
Layer
Layer
Layer
Layer
Figure 2: Loss gaps and bounds of MPNNs of different layers
Table 4: Correlation coefficients between the empirical loss gaps and three generalization bounds on difference J-MPNN variants.
J. J-MNN variants
Dataset
CcJ-MPNN
(C.-MMPNN
[C.)-MPNN
[Ca)-MPNN
(K.J-MPNN
(K.)-MPNN (Ko]-MPNIN
VC hound
0.347
-0.352
-0.388
-0.327
-0.800
-0.164
-0.731
SIDER
PAC hound
0.421
.0889
0.770
0.623
00904
.0.73
.0.65
Our bound
0.545
0.414
0.464
0.537
0.897
0.539
0.925
VC bound
-0.469
-0.251
-0.292
-0.448
-0,251
-0.251
-0.251
bound
.0.990
BACE
Our bound
0.902
0.104
0.303
0.238
0,340
0.221
0.502
20


Reviews:
[{"review_id": "v2S2jx4brD", "reviewer": "Reviewer_iUbN", "summary": "This work present a practical framework for analyzing the generalization property of GNNs via their expressivity. The main result is an extension of previous works to graph representation learning. The theoretical results are accompanied by case studies and experimental verifications to demonstrate the tightness of the proposed bound.", "questions": "Is it possible to do a priori analysis on how a specific message aggregation scheme, e.g., k-WL or attention, can quantitively influence the terms in the bound?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The proposed framework is empirically effective to estimate the generalization of GNNs. The bound is given by the regularity and expressivity of the graph encoder itself, which are accessible measures in practice. This method has the potential to assess the generalization of real-world models.\n\n2. The presentation of the paper is clean and easy to follow.", "weaknesses": "1. The verification and discussion are limited to MPNNs. Empirically, higher-order information and/or attention mechanism are widely adopted to enhance GNNs. While the results in this work are applicable to these models in a straightforward way, it does not provide insights how these architectures improve the B/S constants in the bound.", "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": "vK4SpIBKCN", "reviewer": "Reviewer_yEuE", "summary": "This paper studies the generalization of graph neural networks. The paper is based on three technical tools. The first one is margin bound, which is common in deriving generalization bound. The second is the Wasserstein distance, which is implicitly linked to the Lipschitzness property of a neural network. The third one, which is the major novelty in this paper, it to bridge between a continuous GNN to a discrete graph embedding that has more separation power, such as 1-WL or homomorphism vectors. Combining the three types of techniques yields a meaningful generalization bound. The authors gave a concrete case showing that how improved expressivity benefits/harms generalization, which is quite interesting. They also conduct experiments to support the theory.", "questions": "See the comments above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall the theoretical result is sound and help gain better understanding for how expressivity is related to generalization in GNNs. The paper is clearly written, with rigorous math notations and theorems. While not checking the proof, I feel the results are correct and make sense to me. The concrete example is quite interesting and makes this paper potentially useful in practice.", "weaknesses": "One major weekness of this paper is that, similar to most of the previous generalization papers, the bound given by this paper is quite sophisticated, intractable to compute, and potentially lose. It may be hard to draw the conclusion that this **upper bound** indeed reflects the real case. Another weakness is the readability. The authors did not explain the insights behind this bound clearly. I think it's not intuitive to understand why generalization error can be bounded by the discrete classifier with better separation power. What does the better separation power play a role in the bound? Also, why do the authors rely on Wasserstein distance? I should acknowledge that I am not an expert in generalization theory, but it would be nice to make the paper friendly to the expressivity community as well.", "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": "wNCUKIutac", "reviewer": "Reviewer_31fD", "summary": "The authors in this paper study the connection between expressivity and generalization ability of GNNs in the graph classification task. They first show that the generalization ability of a graph encoder can be upper bounded by that of graph more encoders with higher expressivity . After that, they establish generalization bounds for GNNs from a optimal transfer viewpoint. Concretely, the derived bound contain the Wasserstein distance of embeddings between two random subsets sampled from training nodes within the same class. In this way, the generalization ability of GNNs in the graph classification task can be depicted by the concentration of intra-class embeddings and the separation of inter-class embeddings. Finally, the authors also provide empirical bounds that adopting sampling to computed the Wasserstein distance and verify their theoretic results on real-world datasets. The experimental results generally support their derived bounds.", "questions": "Q1: In the experiments you only compare your bounds with VC bounds. It is encouraged to also compare with PAC-Bayesian bounds presented in (Ju et al. 2023).\n\nQ2: Providing some examples to illustrate some definitions could help the readers better understand their meanings, e.g., the definitions of homomorphism and graph invariant in Section 3. You could add some figures to demonstrate these definitions more intuitively.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem studied in this paper is pivotal in the theory of GNNs, i.e., revealing the connection between expressivity and generalization ability of GNNs. This paper makes a non-trivial progress in this problem, and the derived results are convinced and sound. As for the generalization bounds for GNNs in graph classification task, the derived results extend previous results (Chuang et al. 2021) to graph data, which also provides a new perspective to understand the generalization ability of GNNs. And, the experimental results show that the numerical values of the derived empirical bounds are significant sharper than that of VC bounds.", "weaknesses": "- The derived generalization bounds for GNNs contain the Lipschitz constants of graph encoders. These constants could be easily evaluated for shallow models, e.g., GCN with two or three layers, yet it may be difficulty to evaluate for more complex GNNs such as graph transformer [1,2].\n- The derived bounds do not take the optimization into consideration and thus could not reflect the impact of optimization algorithms on generalization ability. It has been shown that the training trajectory could also affect the generalization ability of models [3]. Although this observation is not yet verified for GNNs, I believe that improving the generalization bounds by involving the analysis of training dynamics could be a promising direction.\n\n\n[1] Chen et al., Structure-Aware Transformer for Graph Representation Learning. ICML 2022.\n\n[2] Rampášek et al., Recipe for a General, Powerful, Scalable Graph Transformer. NeurIPS 2022.\n\n[3] Fu et al., Learning Trajectories are Generalization Indicators. NeurIPS 2023.", "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": "UADQUyyC9F", "reviewer": "Reviewer_UQK4", "summary": "This paper theoretically studies the relationship between the generalization of GNN and the expressive power of GNN in terms of the variance of graph structures. This work especially shows a trade-off between intra-class concentration and inter-class separation, which is the key insight into the generalization gap. Some experiments are conducted to support the theory.", "questions": "In Figure 2 (a), why not show both the loss gap and the bound for each dataset? In Figure 2 (b), why not show both $W_1$ and $Lip(f)$ for each dataset?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. Some theoretical results seem solid and strong.\n2. The problem to study is very interesting and important to the community to bridge the gap between the generalization and expressive power of GNN.", "weaknesses": "1. The theoretical proof is not complete. The proof of Corollary 4.5 and Proposition 5.2 are missing.\n2. The paper is full of equations. Section 3 is not easy to follow when introducing so many terminologies with any examples. \n3. The practical insights are limited. Section 6 is quite confusing. This section shows that different graphs can lead to opposite effects on inter-class separation by the expressive power. Then, what should we do in practice based on this knowledge? Moreover, Section 6 seems irrelevant to intra-class concentration. Then, is the case study of Section 6 meaningful enough?\n4. Results in Table 2 look weak. I cannot see that the proposed bound is better than VC bound in simulating the trend of accuracy or loss gap. \n\nMinor: 1. at the end of line 482, it shall be \"Figure 2(b)\" instead of \"Figure 2(a)\"?\n2. Please resize Figure 2 to make it look nicer.", "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)