Covered Forest: Fine-grained generalization analysis of graph neural networks
Authors: Antonis Vasileiou
Ben Finkelshtein
Floris Geerts
Ron Levie
Christopher Morris
Venue: ICML 2025 spotlightposter (2025)
Keywords: MPNNs
generalization
bounds
theory
Weisfeiler
Leman
Lehman
Primary area: deep_learning->graph_neural_networks
TL;DR: We provide tighter generalization bounds for MPNNs by considering the pseudometric geometry of MPNNs' feature space

Abstract: The expressive power of message-passing graph neural networks (MPNNs) is reasonably well understood, primarily through combinatorial techniques from graph isomorphism testing. However, MPNNs' generalization abilities---making meaningful predictions beyond the training set---remain less explored. Current generalization analyses often overlook graph structure, limit the focus to specific aggregation functions, and assume the impractical, hard-to-optimize $0$-$1$ loss function. Here, we extend recent advances in graph similarity theory to assess the influence of graph structure, aggregation, and loss functions on MPNNs' generalization abilities. Our empirical study supports our theoretical insights, improving our understanding of MPNNs' generalization properties.

Covered Forest: Fine-grained generalization analysis of graph neural networks
Antonis Vasileiou
Ben Finkelshtein Floris Geerts 3 Ron Levie Christopher Morris'
Abstract
pressivity is analyzed via algorithmic alignment with the 1-dimensional Weisfeiler- Leman algorithm (1-WL) (We- isfeiler & Leman, 1968; Weisfeiler, 1976; Morris et al., 2023b), a heuristic for graph isomorphism, or universal approximation theorems (Azizian & Lelarge, 2021; Böker et al., 2023; Chen et al., 2019; Geerts & Reutter, 2022; Maehara & NT, 2019; Rauchwerger et al., 2024). For in- stance, Morris et al. (2019); Xu et al. (2019) showed that the 1-WL bounds MPNNs' expressivity in distinguishing non-isomorphic graphs, while recent work (Böker al., 2023; Chen et al., 2022; 2023; Rauchwerger et al., 2024) refines expressivity using advances in graph similarity, such as the Tree distance (Böker, 2021).
The expressive power of pessage-passing graph neural networks (MPNNs) is reasonably well un- derstood, primarily through combinatorial tech- niques from graph isomorphism testing. How- ever, MPNNs' generalization abilities-making meaningful predictions beyond the training set- remain less explored. Current generalization anal- yses often overlook graph structure, limit the focus specific aggregation functions, and as- sume the impractical, hard-to-optimize 0-1 loss function. Here, we extend recent advances in graph similarity theory to assess the influence of graph structure, aggregation, and loss functions on MPNNs' generalization abilities. Our empiri- cal study supports our theoretical insights, improv- ing our understanding of MPNNs' generalization properties.
Understanding when MPNNs generalize to unseen graphs is equally crucial but understudied (Morris et al., 2024). Recent works (Franks et al., 2023; Liao et al., 2021; Mor- ris et al., 2023a; Scarselli et al., 2018 () often use Vapnik- Chervonenkis dimension (VC dimension) (Vapnik, 1995) or related formalisms to derive generalization bounds based on simplistic graph parameters, c.g., maximum degree. For example, Morris al. (2023a, Proposition and 2) linked 1- WL expressivity with VC dimension, assuming the 0-1 loss function and specific aggregation functions. Their reliance on 1 1-WL implies simplistic notion of graph similarity, where graphs are either equivalent or entirely dissimilar, leading to vacuous bounds irrelevant to practice. Moreover, in general, most analyses overlook architectural variations like aggregation functions.
1. Introduction
Graphs represent interactions across life, natural, and for- mal seiences, such as atomistic systems (Duval et al., 2023; Zhang et al., 2023) or social networks (Fasley & Kleinberg, 2010; Lovász, 2012), highlighting the need for machine learning methods for graph data. Message-passing graph neural networks (MPNNs) (Gilmer et al., 2017: Scarselli et al., 2009) have recently gained attention, achieving suc- cess in areas like drug design (Wong et al., 2023), weather forecasting (Lam et al., 2023), and combinatorial optimiza- tion (Cappart et al., 2023; Scavuzzo et al., 2024; Qian et al., 2024).
Present work Here, we extend modern generalization frameworks based on (data-dependent) covering num- bers (Xu & Mannor, 2012; Kawaguchi et al., 2022) to ad- dress the above shortcomings. Specifically, we investigate how refined notions of graph similarity, or pseudo-metrin on graphs, enable smaller graph coverings and tighter anal- yses of MPNNS' generalization error. See Figure for an illustration of how pseudo-metries induce distinct ge- ometries, leading to improved generalization analysis. Our analysis also incorporates various architectural choices and loss functions.
Despite their success, MPNNs' theoretical properties are underexplored (Morris et al., 2024), with most studies fo- cusing on expressiviry, i.e., their ability to separate graphs or approximate permutation-invarial graph functions. Ex-
'RWTH Aachen University, Germany University of Oxford, UK è "University of Antwerp. Belgium "Technion - Israel Institute of Technology, Isracl. Correspondence to: Antonis Vasileiou <antonis. vasileiou <antonis.vasilcioue tog.rwth-aacher dec.
Concretely, (I) we demonstrate that the choice of pseudo- metric on n-order graphs significantly affects generaliza- tion analysis. For instance, the Tree distance (Böker, 2021) yields strictly tighter generalization error bound
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Covered Forests
than Morris al. (2023a). We provide a general proof tech- nique for this improvement, covering loss functions such as cross-entropy and mean absolute error, unlike Morris et al. (2023a). (2) We link our pseudo-metre mettriss to the Tree Mover's distance (TMD) (Chuang & Jegelka, 2022), deepening the understanding of TMD, originally defined via a recursive transportation formula. (3) We define the 1-MWL, a heuris- tic for graph isomorphism that characterizes the expressivity of MPNNs with mean aggregation and satisfies the Lips- chitz property required for our generalization analysis. We also derive corresponding pseudo-metric on graphs equiva- lent to 1-WLL in distinguishing von-isomorphie graphs. (4) Empirically, our theoretical findings translate into practice, offering nuanced insights into MPNN generalization.
of the covering number, there is subset {3 (K1,-..,,K RK} C X' representing an 6-cover of X. We define partition {Ci,..., Ck} where C₁ = for E X' d(z,z;) = mi] d(z,, ((z,2))} 22)). for E [K]. To break ties, we take the smallest in the above. Note that X' = =Ueek] C. The diameter of set is the maximal distance between any two elements in the set. Implied by the definition of an e-cover and the triangle inequality, each C2 has a diameter of most 2e.
Supervised learning on graphs We define supervised learning on graphs as follows. Let 9 be the set of all graphs and y' set. Unless specified otherwise, 9 includes graphs of varying orders with vertex features in arbitrary domains. Later, we restrict G by bounding graph order or vertex fea- ture domains. Similarly, Y' varies depending on the task, e.g., regression or binary classification. We consider classes H S X of graph embeddings, ie.., mappings from G to X' for some set X. A graph learning algorithm learns such embeddings from data samples. More formally, let 2 == 9 x y with a probability distribution Jr. A data sample S is a collection of elements from Z, drawn i.i.d. according to μr. We denote (G. y) ~ f for an element drawn from Z under and S ~ n² for a sample of size k E N. A graph learning algorithm for H maps each sample S to a graph embedding hs E H. The "goodness" of his is assessed using a loss function E: X x + R., assumed bounded by some M > O. That is, (e(M(G),, .v)l S M for all h H. EE G, and y y. We define the expected and em- pirical error as: toxp (hs) = [((ss(()))))() v)] and [8) Eic.nes (hs(G)),) v). where S ~ ju for k E N. The generalization error, 1eex (hs)) (hs)) is what we aim to bound in this work.
In summary, our results highlight how refined graph similar- ity notions improve the understanding of MPNNs' general- ization, considering graph structure, architectural choices, and loss functions.
See Appendix A for a detailed discussion of related work.
1.1. Background
In the following, we provide the necessary background on (pseudo-) metric spaces, covering numbers, and MPNNs. We use standard notation for graphs and norms; see Appendix B.
Metric spaces and coverings In the remainder of the paper, "distances" between graphs play essential role, which we make precise by defining a pseudo-metric (on the set of graphs) Let X' be set equipped with a pseudo- metric d: X x X + R+, i.e., d is a function satisfying d(x,,) = 0 and d(x,y) y) = d(y.z) x) for 2, y E X, and d(x, v) S d(x, 2) + d(2.y) for x, E X. The latter property is called the triangle inequality. The pair (X is called a pseudo-metric space. For (X, d) to be metric space, d additionally needs to satisfy d(x, y) = 0 + y, for 2. E X.! See Appendix B for the definition of (Lips- chitz/uniform) continuity of a function between pseudomet- ric spaces. Let (X, d) be a pseudo- metric space. Given an E > 0, an E-cover of X is a subset C S X' such that for all elements E X there an element y E C' such that and meeudo-metric d on the set X. we define the covering number of X. (x
Cemp (hs)
Pressage-passingg graph neural networks One particular, well-known class of graph embeddings is MPNNs. Follow- ing Gilmer et al. (2017). let G be an attributed graph with initial vertex-feature h E Rdo do E N, for e V(G). An MPNN architecture consists of a stack of L neural net- work layers for some L >> 0. In each layer, t E N, we compute vertex feature h =
d(ar, y) S e. Given
UPD (1) [ (t)) (GG (fh u ( E ER..
min(m m there is an s-cover of X' of cardinality m),
d, N. for E V(G). where (P and ! parameterized functions, e.g., neural networks. In the case of graph-level tasks, e.g., graph classification, one uses a readout,
i.c., the smallest number m such that there exists a E-cover of cardinality m of the set X with regard to the pseudo-
metric d.
The covering number provides a direct way of constructing a partition of X. Let K == NVX d, E) so that, by definition
hg = READOUT (h!44) | E V(G)B) Rd.
Observve that computing a metric on the set of graphs G up to isomorphism is at least as hard as solving the graph isomorphism problem on g.
a single vectorial representation based on learned vertex features after iteration L. Again, READOUT may be a parameterized function.
to compute
2

---

Covered Forests
MPNNIGG
MPNN(G:)
MPNNIGG
MPNNI(GS)
GP
MPNNIGG
(a) A set of padded (b) Geometry under the trivial 1-WL discrete pseudo- metric. All graphs equally far apart, not taking
(c) Geometry under the Tree distance 8jj-1-- The similarity of graphs is preserved under MPNNs. leading smaller covering and tighter general- ization analysis.
binary trees.
into account their similarity, mapping each graph to unique e-ball.
Figure 1. Illustrating how the choice of pseudo-metrics influences the geometry and the size of coverings, leading to a tighter generalization analysis.
Special cases of MPNN layers In the following, we dis- cuss special cases of MPNNs, which we will subsequently use in our analyses of MPNNs' generalization abilities. First, for an unlabeled n-order graph G, we assume all initial vertex-features are identical, i.e., h. = -hw' for U, w E V(G). this case, we define an MPNN layer using order-normalized sum aggregation and order-normalized readout, where
MPNN classes Based on the above three types of MPNN layers, we consider the following classes of MPNNs. Let G be a class of graphs, we denote the class of all L-layer MPNNs following Equation (1) where 1b is represented by feed-forward neural network (FNN) (See Appendix B.1 for formal definition of FNNs) with Lipschitz constant LFNN and bounded by M' E R by MPNN ",,' (9), i.e.
MPNN T., T.,M',,A F.NNN (9) =
h 91 (Y/VIO1)
Σ No
(1)
h: 9h:9-40 NGG) = FNN# o hG where O E }}.
uEN(w)
where ④ is the parameter set of FNNs. Analogously, for Equation (3) and Equation (5), we define the classes MPNN LLnms (9) and MPNN L.M"
hg = & (1VVGI)
Σ n(4)
(2)
NEV(G)
respectively. Finally, we denote the class of all MPNN architectures con- sisting of L layers with a readout layer represented by an FNN at the (L. + tth- by MPNN,
inean Lemn(1) L..'',
for u E V(G), where sp:: Rdd-1 + Rd is a Lup, -ipschitz continuous function, with respect to the 2-norm-induce metric, for d E N and f E [Z], and v:: Be + Rd is a La- Lipschitz continuous f 2 Secondly, for an attributed n-order graph (G, a). i.e. we set h = a(v), for v E VG),, we define an MPNN layer using sum aggregation and porer-normmlized readout, where
In Appendix C, we provide the formal definition of the 1- -eisfeiilrr-Lmann algorithm (1-WL), characterizing the distinguishing power of sum aggregation MPNNs (Morris et al., 2019). We also introduce 1-MWL, a variant of 1-WL, characterizing the distinguishing power of mean aggrega- tion MPNNs.
h = se (n!! (w( +
Σ uEN(v)
hg = 2 (1//(CH)
Σ
(1)
(4)
2. Pseudo-metrics on the set of graphs
GEV(G)
We define and study (pseudo-)metrice on the set of graphs, which we later use for a fine-grained generalization analysis of MPNNs; see Appendix D for an extended discussion. These pseudo-metrics are designed to align with MPNNs, reflecting their computational properties. Since the expres- siveness of MPNNs bounded by the 1-WL, we aim to define meeudo-mtriics such that two graphs have distance of O if, and only if, they are 1-WL indistinguishable.
where 6e and 1/ are defined as in Equation (1) and w 22 are d x de matrices over IR. Under the additional assumption of positive homogeneity of sp, i.c., <p:(Ax) = (x), for À >>0 O, we define an MPNN layer us- ing mean aggregation and normalzzd readout, where
h = 4t (1( w. 0+ 2/1N(O)) Σ
h (111) (2))
(5)
(NN(v)
Building on Böker (2021), we define the Tree distance, as follows. A matrix S E [0,1]mxm is doubly-stochastic matrix if ||S = 1, for E [n]. and |SS. = 1, for j E [n]. Let D,, denote the set of n x n doubly-stochaste matrices. Given matrix norm ||-||, for two graphs G and
hg = 1 (VIICH))
Σ
h(4)) &
(EV(G)
1Implied by Morris al. (2019), choosing the function yor appropriately, leads to 1-WL-equivalent -aNN-layer.
3

---

Covered Forests
H. with adjacency matrices A(G) and AH), respectively, we define the Tree distance
forest, by FG.L. We perform the same procedure for the graph (H). resulting in the forest FH...- Note that the forests FG,L and FR, have the same structure but are pos- sibly non-isomorphic due to their vertex labels not matching, However, we can always find an edge-preserving bijection between VFF..)) and V LFH,L). Finally, given a vertex u E ((Fa,r.), we denote by I(u) E [4] the level of ver- tex u in the forest FG,L. Now given weight function N- + R+, we define the Forest distance of depth L and weights w, between G and H as FDD.,. H)
(G, (), = min |AG)) SAHHI- SED,
(7)
Similarly, we extend the above definition to labeled graphs in 9 resulting in the labeled Tree distance, TT (G,
min |AG)) SA(H)I + TT(SS (8) SED=
where L(G, = [dist(Eo(t), Eu (evio))eevv))) for
min
Σ m(((u) (o(()))[[aa(V)) [[ac(u) - a (+(2)))) (EV(F..L)
(9)
some distance function dist between node features (see Ap-
pendix D). The following result shows that Equations (7) and (8) are valid pseudo-metrics for many norms.
where the minimum is taken over all edge- preeeerrsg bijec- tions yp between (Fc.,t) and (FFH,,.)) When w(() = 1, for l E N, we denote the Forest distance by FD,. See Fig- ure for an illustration of the distance. The following result shows that FD( (w) is valid -eeuio-metric.
Proposition 1. For every entry-wise matrix norm or the cur norm I1-Il, (1 is a pseudo-metric on g Additionally, for
two vertex- labeled graphs G and H in G7.0 5T (T, 0 if. and only, if G and H are 1- L-WL indistinguishable. D
Lemma 2. For every w: N + Rt, L E N, the Forest
Although the Tree distance and its extension to labeled graphs match the 1-WL algorithm in expressivity, they do not consider the number of iterations needed to distinguish two graphs. This limits our ability to provide tighter gen- eralization error bounds for MPNNs with a fixed number of layers. To address this, we define the Forest distance on S. which matches the expressivity of 1-WL up to L. iterations for fixed L E N.
distance FDL.s is a well-defined pseudo-metre on P In addition, for two graphs, G, H, (G,,,(G, H) ()= = 0 if and only if G, H are 1-WL indistinguishable after L iterations.
Now the following result shows that the Forest distance is simplified version of the TMD defined by Chuang & Jegelka (2022), see Appendix F, providing a streamlined, easy-to- understand definition of the TMD distance while preserving all the essential properties required for our analysis.
To define the Forest distance, formally, let (G, ag) and (H, aH) ) be attributed graphs of order nt, where
Forest distance
Lemma 3. The Forest distance is equivalent to the Tree Mover's distance. That is, for all n, d, L E N,w: N + IRt, and for all graphs G, H E P
ag: V(G) + Fd \ {og=) } and ag: V(H) + Rd {og*); }. for d N.* Given a graph G, a node u E V(G). and a depth L E N. we define the unrolling tree of u at depth L as a rooted tree u with depth L, where each node has as children its neighbors in the graph G. This tree is also called the computation tree (see Appendix C for formal definition). Now, for fixed L E N, consider the following multiset of unrolling trees:
TMD (w) (G, H) = (D,
where w(n) II (1), E.
While mathematically equivalent, the Forest distance and TMD have distinct advantages. TMD allows more efficient computation, making it practical for applications, whereas the Forest distance intuitively captures structural differences between graphs.
TØ == --[[uunrGG u,, L)) | V(G))-
To account for unrolling trees of different orders, we per- form a padding process on all trees in Tg. That is, for each vertex of each unrolling tree in the multiset Tg. we add children with the label o until each vertex has exactly 1 children. Hence, after padding, all trees in To will have the exact same structure, though the vertices will have different labels, and we denote their disjoint union, i.e.,
Mean Forest distance The Forest distance motivates the definition of the mean-Forest distance, based on mean unrolling (computation) trees (see Appendix G). This is the first graph pseudo-metric that precisely captures the distinguishing power of mean aggregation MPNNs (see Lemma 29). These MPNNs also satisfy a Lips- chitz property regarding the mean-Forest distance (see
NNte that this pseudometric can also be detined the space Sh.d. which includes graphs with continuous vertex features. How- ever, we restrict our proof to Boolean features to establish the equivalence with the 1-WL algorithm.
'In the definition of the Forest distance, we use the Euclidean norm following Chuang & Jegelka (2022). However, we note that any other norm could also be used, all norms are equivalent in finite-dimensional spaces.
"Without loss of generality, we use the vector for padding purposes.
4

---

Covered Forests
have that for all ô E (0,1), with probability least 8,
fexp(hs)=femp(he (hs)l S M 2K(S) log(2) 2 log( 1/6)
S
where hg. as before, denotes a graph embedding from H. returned by the learning algorithm given the data sample S of Z. We recall that M is the bound on the loss function f.
G1
G2
See Appendix I for the refined results of Kawaguchi et al. (2022) and our extension allowing for different radii within each partition set.
Connecting robustness, continuity, and expressivity A natural approach to ensure the robustness of the learning algorithm impose continuity assumptions on both the loss functions and the graph embeddings. To formalize this, let us consider two pseudo-metric spaces (X, dx) and (V, dy), and define the pseudo-metric dxc: (X x 3) x (X' )) - IR+ as
Figure 2. An illustration of the computation of the Forest distance for depth for two labeled graphs G1 and G2. Grey vertices indicate the padded vertices in the unrollings, and represents an edge-preserving bijection between the two forests.
((x, B), (I', .v)) = max(dx(2; x' dy(y.
Let l: X x - R+ be a ce-Lipschitz continuous loss function concerning the metric do and (G, be pseudo- metrie space over set of graphs. If the covering numbers for the spaces (G. dg) and (Y, dy) can be bounded above, then uniform continuity implies robustness, as shown next.
Lemma 48). We remark that Chuang & Jegelka (2022) (Ap- pendix B.1) introduced the unnormalized tree mover's 's dis- tance (TMD and proved its Lipschitz property for mean aggregation MPNNs. However, TMD* is more powerful than the 1-MWL, as it relies on optimal transport between unrolling trees, capturing 1-WL's distinguishing power in- stead of 1-MWL's.
Proposition 5. Let (G,dg), (X, and (V,dy) be pseudo-metrie spaces, and let H denote the class of uniformly continuous graph embeddings from (G.dg) to (X, dx). E X x - Rt is a ce r--Liscchtz continuous loss function, regarding day, then for any > 0, a graph learning algorithm for H on G y
3. Robustness framework
In the following, we introduce the generalization framework for studying the generalization abilities of MPNNs. We refer to Section 1.1 for the formal setup and notation. Slightly modifying the notation from Xu & Mannor (2012), we say that (graph) learning algorithm for the hypothesis class H. e.g., a class of graph embeddings, on G := X' x y, is (K,s). s)- robust, for and e, mappings from the set of all possible samples to N and IR+ respectively, if for all samples S, z can be partitioned into K(S) > 0 sets, {C the following holds. If (G,y) E Ci, for some i E [K] then for all (G',8')= E C..
(N dg. ((,, -N(Y, dy, e.yyy/// E/2), (.5) robustt
Here, = YE, hs) depends on both e and S is the positive function used in the definition of the uniform continuity of hi E H.
Lipschitzness and equicontinuity of the hypothesis class By Proposition and Theorem 4, we observe that the gener- alization bound depends on the function 7, which, in turn, depends on the specific choice of the MPNN hs. Ideally, we aim to eliminate this dependency on S by deriving uni- form bound for all uniformly continuous MPNNs. This can be achieved by showing the existence of a "uniform" choice of ((e) that satisfies the uniform continuity definition for all possible MPNNs within a hypothesis class. This prop- erty is also known as equicontinuity of the hypothesis class.
K(S) such that
[ v) ((ss(G)) <((),,
where hi is the graph embedding the learning algorithm returns regarding the data sample S. Intuitively, the above definition requires that the difference of the losses of two data points in the same part of the partition is small. Xu & Mannor (2012) showed that (K,e)-robbe -robustt learning algo- rithm implies a bound on the generalization error.
*Since is a function in the definition of robustness, we clarify that here refers to constant function from the set of all possible samples to positive real numher. For simplicity and with slight abuse notation, we also denote this constant by s.
Theorem (Theorem 3 in Xu & Mannor (2012)). For any (K, -r-oouust (graph) learning algorithm for Ht on 2, we
5

---

Covered Forests
For instance, this holds for all the hypothesis classes of all c-Lipschitz MPNNs, sharing the same Lipschitz constant G, in which case we can set ((s) = =//c.
i.e., the Tree distance. This leads Proposition 9, The- orem 10, and Proposition 12 (for class of binary trees). Next, we consider labeled graphs and analyze MPNN lay- ers defined in Equation (3), i.e., -agagggeettion MPNNs, using the pseudo-metrics defined in Equation (9), i.e., the Forest distance. This yields Proposition 15 and Proposi- tion 16. These results can be extended to mean-aggregation MPNNs using the mean-Forest distance, as described in Ap- pendix M.
Corollary 6. Let (g, dg), (X, dx), and (V,dy) dyy) be pseudo- metric spaces, and let H. denote the class of oH -ippschtii continuous graph embeddings from (G,dg) to (X, x, Assume that the loss function is cx-Lipschitz. regard- ing doc. Then, graph learning algorithms for H are D
(N(G, d2.x)(2cx))
dy, 2/2, rrobust.
We first consider unlabeled n-order graphs, i.e., every vertex has the same label. We analyze the binary classification setting. Following Section 1.1 and Equation (1), here we investigate the class MPNNL, Lrw. (Gn). We further con- sider the binary cross-entropy loss E: IRx [0,1} - IR, where ((z, 3) == y (z)( + +11 -11-1) y) log - (x)), where is the sigmoid function. It is known that É is Lipschitz on the first argument (since it has bounded first-order derivative) for some Lipschitz constant Lg.
As will become clear later, we will use Corollary 6 to de- rive our generalization bounds in the regression setting, assuming Lipschizz-continuuus loss function. However, for the classification setting, we will specifically use the cross-entropy loss, which is Lipschitz-cooninnuus, concern ing only one argument. In this case, we will need a slightly modified version of Corollary to establish our generaliza- tion bounds, resulting in the following proposition, which follows from Xu & Mannor (2012, Theorem 14)
In Proposition 1 in Section 1.1, we observed that the Tree distance of Equation (7) induces various pscudo-metrics that are equivalent to the 1-WL in terms of expressivity. Utilizing the analysis in Böker et al. (2023), we show that the Tree distance using the cut norm satisfies the uniform continuity property using the same MPNN L.M'' L,M Frmm (Gn), i.e., it is equicontinuous. Formally, we consider the following variant of the Tree distance on Gn.
Proposition 7. Let (G.dg), (X, dx), and (), dy) be pseudo-metric spuces, let H be a class of graph embed- dings from (G.dg) to (X, dx), and let E: X x y + R+ be a loss function. For a graph learning algorithm for H. on G x D, assume that there exists positive Y > O such that for all samples S and G1,G2 E g, 91.92 E y. max[dg(G, G2), (y(()182)) S Y =
(E) for all MPNNs in
[((hs(G)).))) - (Ghs(G2), 82)1 < c(S), then, H. is (N().dy, 7/2) NN dg. (22), eorroustt.
GG = min - SED,
See Appendix J.1 for more details on the relationship be- tween robustness and continuity.
where [1-1|a denotes the cut norm, see Equation (11) in Ap- pendix B for details.
4. Fine-grained generalization analysis of MPNNs
The following result shows the equicontinuity property of MPNNs.
Theorem 8. For all > 0, L N there exists 7E) O such that for E M' R. G, H 9n, and all MPNN architectures in MPNN L,M' Lrun (Gn). we have
In this section, we derive the main generalization results of this work using the robustness framework described in Sec- tion 3. First, in Appendix L. we recover the VC-dimension bounds from Morris et al. (2023a) within the robustness framework, showing that these bounds can be obtained using trivial discrete mseudo-metric between graphs, defined as when the graphs are 1-WL, distinguishable and 0 otherwise, leading to vacuous generalization bounds. This motivates us to analyze the impact of alternative pseudo-metrics that yield more fine-grained generalization bounds within the robustness framework compared to the trivial 1-WL-based pseudo-metric. Our analysis considers different aggregation functions, vertex labeling schemes, and loss functions.
& H) < n² 77() = lin hu hull2 S1
The proof is direct implication of Theorems 29 and 31 in Böker et al. (2023) using the uniform continuity of MPNNs concerning the Prokhorov metric (Theorem 29) and then the e-Ō equivalence between the Prokhorov metric and the Tree distance o6 (Theorem 31). It is important to note that, in the above result, we proved that all func- tions in MPNN LLow (Gn), are uniformly continuous sharing the same 7()), or equivalently the hypothesis class L.M
MPNN Lrwn (9m) satisfies the equicontinuity property. This property is our primary motivation for choosing the tree distance as the pscudo-metric.
We begin by exploring the generalization abilities of MPNN architectures using sum aggregation. Specifically, we con- sider unlabeled graphs and analyze MPNN layers defined in Equation (1), i.c. order- normalized sum aggggegrenn MPNNs, using the pseudo-ment metiies defined in Equation (7),
Based on the above result, we define the following non- decreasing function 7: R+ U (+00) + I U {+00]
6

---

Covered Forests
where 7(+00) = too, for all G,H H. E Gns for all h E MPNN L.M Low (9n);
1 Ö, we have
88
(eex((hs) - femp(hs) S Le LFNN .5
7(() = sup > 00 0185(G, H) S n²8 = M S e)
n2?
(10)
and define its generalized inverse function -=: RR U {+oo} R U [+oo), where R$ (0, t00),
ma (2g +
log (2)
+ M
|S]
7-(1) = inf > 0 7()) 2 v)-
for k E N. where M is upper bound on the loss function f, and my, 19-/~m|
Note that 7t is also non-decreasing. We further make the convention that [n] = +oc. We now establish the following family of generalization bounds for the class MPNN L,M" Lewn (Gn) based on the results from Proposi- tion 7.
In Appendix in Proposition 36, we combine the extended robustness definition along with Theorem 35 to extend the generalization bounds from Theorem 10 to the class of unla- beled graphs with at most a vertices, denoted as Ggn. The proof of Proposition 36 is omitted, as it directly follows from the tree construction described in the proof of Theorem 10.
Proposition 9. For n, E N. M' E R. and E > _dd", where d' is the minimum non-zero 8I, distance between two graphs in G any graph learning algorithm for the class MPNN L,M,, Leen (9n) is
Tighter bounds on the covering number The proof of Theorem 10 establishes an upper bound on the cover- ing number, decreasing linearly with the radius. We can use this bound determine the optimal radius minimizing the generalization bound in Equation (10). However, it remains unclear if this upper bound on the covering number is tight or if the linear decay can be improved. Moreover, the bound mn///k + relies on the number of equivalence classes max which is hard to compute.
(2E) n2
(2N(Gm. G,E), Le- LENN 77
rrobust.
Hence, for any sample S and E (0,1), with probability at least 1 8.
(box)(hs) - (hs) S Le- LFNN- 77
122
To address this, we analyze specific graph classes that yield tighter bounds and simplify the computation of 1- WL-distinguishable graphs. First, consider the class of un- ordered, unlabeled, full binary trees n vertices, denoted (2 where n 2j + 1 and j E N. This class includes rooted trees where each non-root vertex has 0 or 2 children. The root need not be explicitly specified here since it is the only vertex with degree 2; all others have degree 1 or 3.
AN(Gn, e) E) (2) + 2 log(1/6)
+ M
|S]
where Mi is an upper bound for the loss function and L is the Lipschitz constant of E(,,)), and y E {0,1).
As can be observed by Proposition 9, the tree distance- more fine-grained metric compared to the trivial 1-WL met- ric (which is for L-WL-distinguishable graphs and 0 oth- erwise)-enables deriving a wider range of generalization bounds by allowing any real number as the radius for the covering number. Choosing the radius & is critical for tight generalization bounds: larger reduces the covering number but increases the first term of the bound, while smaller has the opposite effect. Balancing this trade-off is impor- tant, though computing the covering number as function of & is an extremely hard problem. For a given n, the cov- cring number can instead be bounded in terms of e and m, = |C./~mal, yielding covering number bounds depen- dent on e. For n-order graphs Gn and E 4k, cover of size ma/(k 1) can be constructed for all is E N, leading to family of bounds parametrized by k.
The graphs in Tr(3) are also called Otter trees, named after Richard Otter's work on their enumeration (Otter, 1948). The total number of Otter trees n vertices, for n 2j+ is given by the WeldderbummFFihhriingge number wy, with j E N. Although no closed-form formula exists for Wj. re- cursive methods enable efficient computation. Additionally, the following asymptotic result holds.
Lemma 11 ((inchh, 2005, p. 295)). The asymptotic growth of wn is given by wn, ~ A.n 3/22. for a positive constant A whose precise value is not relevant for our purposes and b 2.4832.
Based on this lemma, we show that for sufficiently large n, we can bound the covering number of the set of Otter trees with a function that decreases exponentially regarding the radius of the cover leading. This results in the following (tighter) generalization bounds for MPNNs on the space of Otter trees.
Theorem 10. For n, L E N, and M' E R. for any graph learning algorithm for the class MPNNord L.M", Lew (9x) and for any sample S and 8 E (0,1), with probability at least
Proposition 12. For L E N,M' E R and sufficiently large n E N. for any graph learning algorithm on
7

---

Covered Forests
MPNNE. L.M', Leun' (2n+1) and for any sample S, with 6 E )) with probability at least 1 we have
erty of MPNNS in MPNN L.M Lew (In,d.g) concerning the Forest distance. While our analysis restricted to Gn,d,q. we state and prove the following result in the more general set- ting of graphs in I i.e., with real-valued vertex features.
16k
(esp((hs) - lamp(hs) S Le- LENN 7- (2n + 1)2
Lemma 14. For L, n, E N, e R and for all MPNNs M in MPNN L.M' Lannn (Dr,)) we have
4wn /620 log(2) + log(1/))
+ M
[
L Top II FD, 1=1
where & E N, M is an upper bound on the loss function t, b 2 2.4832, and Wn IT
|| - h I C(L)
for G, 11 E In where C(L) is constant that depends on L and the Lipschitz constants of the MPNN layers.
Note that using the above bound with a radius mildly depen- dent n, say (n), we can derive upper bound the covering number that decreases quadratically with n.
We are now ready present the generalization bound exten- sion for labeled graphs.
Additionally, in Appendix N, we derive a graph class (de- noted as Fr) that leads to non-constant improvement for a constant and lift the above results to the regression setting.
Proposition 15. For & > 0 and n. L,d,g E N, E R. any graph learning algorithm for MPNNI, Loow (gn,d.a) is
Vertex-labeled graphs Finally, in this section, we aim to extend the previous results to the space of discretely- labeled n-order graphs, where vertex features are drawn from a finite collection of dl elements, i.e., I For ease of notation, we consider one-hot encoding of the labels. Thus, all vertices are initially labeled with d-dimensional vector, having a in one position and O elsewhere. Furthermore, we consider the set of graphs with bounded-degree q, for q E N. We denote this set as In.d.q. and the number of equivalence classes induced by the 1-WL after L iterations on this set by L. simply mn,d.q when L = n 1.
(2N(Gn.d.g) FDL, Le- LENN CFD. )robbut
Hence, we have the following generalization bounds. For any sample S and 5 E (0,1), with probability at least 1 - 8,
(eep((h)) lemp(hs) (hs) S CCE
N N(9nd.: E)4, + llog(!/)
+ M
[S]
for E O, where Č OFN CFD C(L) Ly II'm Ipp is the Lipschitz constant in Lemma 14 and M is an upper bound of the loss function f.
To establish our generalization bounds based on the robust- ness framework, we use the Forest distance F'D, as defined in Section 2. We begin with the following simple lemma, bounding the Forest distance between two graphs differing by either one edge or one label. Moreover, the following lemma explains the assumption of bounded degree in our graph class. Without this assumption, the bound below would grow with n. making it impossible to establish uni- form generalization bounds.
Using a similar construction as Theorem 10, below, we up- per bound the covering number in the generalization bound by a function of the corresponding radius and Mn.dq.LL leading to the following generalization bound.
Proposition 16. For n, d, L E N, and M' E R. for any graph learning algorithm for the class MPNN L.M'', (9n.d.) and for any sample S and 8 e (0,1), with probability at least 1 - 8, we have
Lemma 13. For d, q E N, there exists a constant b(d, q, L) such that for E N and G. H E Gudd.g if G can be de- rived by either deleting an edge or changing a single ver- tex feature of H, then HG, < b(d, q, L). where bld, q, L) = =2a 1-9"
(lox)(hs) - -oempppssss < 2cb(d, q, L)k
1-9
A. 4 4ogg(2) 2) + 2 log (1/1) k+1
+ M
In the following, we analyze the generalization power of MPNN L,M, Lenn (Gn,gg). Similar to the case of unlabeled graphs, we consider the cross- entropy function L: RRR. x {0,1} ((x,v) (z))(a(x)) + (1 v) log(1 - (xx), where (x)) is the sigmoid function. As with unlabeled graphs, our generalization analysis requires MPNNs to be Lipschitz continuous with respect to the chosen pseudo-metric The following result demonstrates the Lipschitz continuity prop-
S
for K N. where Č 2/nLgLENNCEDa: CFDs C(L) IT' Lpp is the Lipschitz constant Lemma 14 and M is an upper bound of the loss function l.
R, defined by
In Appendix M, we lift the results to MPNNs using mean aggregation. Additionally, in Section 5, we discuss our analysis's limitations and future work.
8

---

Covered Forests
5. Limitations, possible road maps, and future work
Table 1. The empirical generalization gap computed using the 1- norm and our generalization bound based on estimates of the Lipschitz constant and the upper bound on the loss function.
While our results are the first to successfully incorporate non-trivial graph similarities, architectural choices, and loss functions into the generalization analysis, many open questions remain regarding MPNN generalization proper- ties. First, our techniques are tailored towards discretely- labeled graphs, e.g.. not accounting for real-valued labels. While Rauchwerger al. (2024) did first step in this direc- tion, their generalization bounds are implicit or existential, i.e., they do not derive concrete upper bounds on the size of the covering, only showing the existence of a finite cover- ing via the compactness of the investigated pseudo-metric spaces. Secondly, while our analysis can be extended to other aggregation functions, e.g., weighted mean, it does not account for other commonly used architectural choices, such normalization layers or skip connections. Thirdly, although the experimental results in Section 6 indicate that our generalization analysis holds in practice to some extent, it does not explain why gradient descent-based based algorithms converge to generalizing solutions. Hence, future work should extend our results to graphs with real-valued features and study whether gradient descent-based algorithms can converge to parameter assignments inducing the desired coverings.
Dataset
MUTAG
NCI1
MCF-7H
OcBG-Me MOBG-MMLHIV
Train Test loss Generalization gap Our bound (Opiinal e)
=wars
0.535 20lmn
0.327 2102s
ause
1,546 _noos
0.588 10151
0.325 insto
0.151 103e
0.344 20005
0.053 15
0.002 2000
0.007 20:0
0.705
0.060
0.007
0.015
Our bound (c 0)
0.946
0.079
0.008
0.019
serve that the covering number increases with larger graph orders or smaller radii, aligning with the expected behavior. Figure 10 in the appendix demonstrates that the covering number bound presented in Theorem 10 is tighter than the number of 1-WL indistinguishable graphs, Ma, when com- pared to the optimal cover. (V. 57 æ). highlighting the usefulness of our upper bound. This observation holds even though the optimal cover is based on the 1-norm while our bound is derived using the cut norm, further solidifying the improved bound introduced in Theorem 10.
Q2 See Figure 11 in the appendix. We observe a strong correlation between the Forest distance and the MPNN out- put variations, indicated by high Pearson correlation co- efficient across varying datasets and MPNN layers. This finding supports the validity of defining the Forest distance's Lipschitz constant in Lemma 14, showing that it captures the computation of MPNNs.
6. Experimental study
In the following, we investigate to what extent our theoreti- cal results translate into practice. Specifically, we answer the following questions.
See Table 1. The results demonstrate that the cover- ing number bound presented in Proposition 15 is tight in real-world settings, in the sense that the empirical general- ization gap and the computed bound are of the same order of magnitude, closely reflecting the real-world generalization behavior. Furthermore, incorporating the upper bound pre- sented in Proposition 16 yields an even tighter bound over simply equating the covering number to the total number of 1-WL indistinguishable graphs.
Q3
Q1 To what extent do the empirical covering numbers for different graph families match the theoretical upper bounds derived in Section 4?
Q3 How are the Forest distance and MPNN outputs corre- lated?
Q3 How does the covering number influence the general- ization performance of MPNNs?
7. Conclusion
See https: https://github.. com foom/bes benf waikkesshheinn CoveredForests for source code and instructions to reproduce all results.
Here, we focused on understanding how choosing different pseudo-metrics on the set of graphs and capturing the com- putation of different MPNN architectures allow for a tighter analysis the generalization error of MPNNs. Unlike pre- vious works, our refined analysis allows us account for non-trivial graph similarities, the impact of different ag- gregation functions, and various practically relevant loss functions. Our empirical study confirmed the validity of our theoretical findings. Overall, our theoretical framework constitutes an essential initial step in unraveling how graph structure and architectural choices influence the MPNNs generalization properties.
See Appendix P for an overview of employed data sets, neural architectures, experimental protocols, and model con- figurations.
Results and discussion In the following, we answer Q1- Q3.
Q1 See Figures& 8 and 9 in the appendix. Across the graph classes In. T Fa, and all real-world datasets, we ob-

---

Covered Forests
Acknowledgements
Bartlett, L.,, Foster, D. J., and Telgarsky, M. Spectrally- normalized margin bounds for neural networks. In Ad- vances in Neural Information Processing Systems, 2017. 15
Antonis Vasileiou is funded by the German Research Foun- dation (DFG) within Research Training Group 2236/2 (Un- RAVeL). Ben Finkelshtein is supported by the Clarendon Scholarship. Christopher Morris is partially funded by DFG Emmy Noether grant (468502433) and RWTH Junior Principal Investigator Fellowship under Germany's ' Excel- Ience Strategy. Ron Levie is supported by a grant from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel, and the United States National Science Foundation (NSF), (NSF-BSF, grant No. 2024660), and by the Israel Science Foundation (ISF grant No. 1937/23). We thank Erik Müller for crafting the figures.
Baskin, I. L., Palyulin, V. A., and Zefirov, N. S. A neural device for searching direct correlations between struc- tures and properties of chemical compounds. Journal of Chemical Information and Computer Sciences, 37(4): 715-721, 1997. 15
Bento, J. and loannidis, S. A family of tractable graph metrics. Applied Network Science, 4(1):107, 2019. 22
Böker, J. Graph similarity and homomorphism densities. Bansal, N., Merelli, E., and Worrell, J. (eds.), Inter- national Colloquium on Automata, Languages, and Pro- gramming, 2021. 1, 3, 16, 35
Impact statement
This paper aims to advance the field of machine learning by providing tight bounds that enhance the theoretical un- derstanding of MPNNs. While findings hold significant potential for societal impact, this discussion is beyond the immediate scope of this work.
Borgwardt, K. M., Ghisu, M. E., Llinares-López, F., O' J'Bray, L., and Rieck, B. Graph kernels: State-of-the-ar and future challenges. Foundations and Trends in Machine Learning, (3, 2020. 16
References
Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. Spectral networks and deep locally connected networks graphs. In International Conference on Learning Representation, 2014. 15
Alon, N. and Naor, A. Approximating the cut-norm via grothendieck's 's inequality. In Conference Proceedings of the Annual ACM Symposium on Theory of Computing. 2004. 32
Böker, J., Levie, R., Huang, N., Villar, S., and Morris, C. Fine-grained expressivity of graph neural networks. In Ad- vances in Neural Information Processing Systems, 2023. 1, 6, 16, 32, 34, 35, 40
Alon, N., Vega, W. D. L., Kannan, R., and Karpinski, M. Random sampling and approximation of max-esp problems. Conference Proceedings of the Annual ACM Symposium Theory of Computing, 2002. 32
Cai, J., Fürer, M., and Immerman, N. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389 410, 1992. 18
Andrews, G. E. and Eriksson, K. Integer Partitions. Cam- bridge University Press, 2004. 39
Arvind, V., Köbler, J., Rattan, G., and Verbitsky, O. On the power of color refinement. In International Symposium on Fundamentals of Computation Theory, 2015. 18
Cappart, Q., Chételat, D., Khalil, E., Lodi, A., Morris, C., and Veličković, Combinatorial optimization and rea- soning with graph neural networks. Journal of Machine Learning Research. 14:130:1-130:::: 2023.
Azizian, W. and Lelarge, M. Characterizing the expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. 1
Chen, S., Lim, S., Mémoli, F,, Wan, Z., and Wang, Y. Weisfeiler-Lehman meets Gtomov--Wsseesee In Inter- national Conference on Machine Learning, 2022. 1
Babai, I. and Kucera, L. Canonical labelling of graphs in linear average time. In Symposium Foundations of Computer Science, 1979. 18
Chen, S., Lim, S., Mémoli, F., Wan, Z., and Wang, Y. The Weisfeiler- Lehmaan distance: Reinterpretation and con- nection with GNNs. In Topological, Algebraic and Geo- metric Learning Workshop, 2023.
Baranwal, A., Fountoulakis, K., and Jagannath, A. Graph convolution for semi- supervise classification: Improved linear separability and -iit----iittiuttionn generalization. In International Conference on Machine Learning, 2021.
Chen, Z., Villar, S., Chen, L., and Bruna, J. On the equiv- alence between graph isomorphism testing and function approximation with GNNs. Advances in Neural Infor- mation Processing Systems, 2019.
15
10

---

Covered Forests
Chuang, C. and Jegelka, S. Tree mover's distance: Bridg- ing graph metrics and stability of graph neural networks. In Advances in Neural Information Processing Systems, 2022. 2, 4, 5, 16, 27, 28, 31
Feng, J., Chen, Y., Li, F., Sarkar, A., and Zhang, M. How powerful are k-hop message passing graph neural net- works. In Advances in Neural Information Processing Systems, 2022. 48
Chuang, C.-Y., Mroueh, Y., Greenewald, K., Torralba, A., and Jegelka, S. Measuring generalization with optimal transport. In Advances in Neural Information Processing Systems, 2021. 16
Fey, M. and Lenssen, J. B. Fast graph representation learning with PyTorch Geometric. In International Conference on Learning Representations, Workshop Representation Learning on Graphs and Manifolds, 2019. 48
Daniëls, N. and Geerts, F. A note the VC dimension of 1-dimensional GNNs. arXiv preprint, 2024. 15
Finch, S. R. Mathematical constants, volume 94 of Ency- clopedia of mathematics and its applications. Cambridge University Press, 2005. 7
Defferrard, M., Bresson, X., and Vandergheynst, P. Con- volutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, 2016. 15
Franks, B. J., Anders, M., Kloft, M., and Schweitzer, P. A systematic approach universal random features in graph neural networks. Transactions on Machine Learning Research, 2023.
Dell, H., Grohe, M., and Rattan, G. Lovász meets Weisfeiler and Leman. In International Colloquium on Automata, Languages, and Programming, 2018. 16
Franks, B. J., Morris, C., Velingker, A., and Geerts, F. Weisfeiler-leman at the margin: When more expressivity matters. In International Conference on Machine Learn- ing, 2024. 15
D' IIvverno. G. A., Bianchini, M., and Scarselli, F. Ve di- mension of graph neural networks with pfaffian activation functions. arXiv preprint, 2024. 15
Frieze, A. M. and Kannan, R. Quick approximation to matrices and applications. Comb., 1999. 32, 34
Duval, A., Mathis, S. V., Joshi, C. K., Schmidt, V., Miret, S., Malliaros, D., Cohen, T., Lio, P., Bengio, Y., and Bronstein, M. M. A hitchhiker's guide geometric GNNs for 3d atomic systems. arXiv preprint, 2023.
Gama, F. Marques, A. G., Leus, G., and Ribeiro, A. Con- volutional neural network architectures for signals sup- ported graphs. IEEE Transactions Signal Process- ing,
2019. 15
Duvenaud, D., Maclaurin, D.. "gguller-Iparrrguiin J., R., Hirzel, T., Aspuru-Guzik, A.,
Garg, V. K., Jegelka, S., and Jaakkola, S. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, 2020. 15
and Adams, R. P. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, 2015. 15
Geerts, F. and Reutter, J. L. Expressiveness and approxima- tion properties of graph neural networks. In International Conference on Learning Representations, 2022. 1
Dvorák, Z. On recognizing graphs by numbers of homomor- phisms. Journal of Graph Theory, 64(4):330-342, 2010. 16
Gilmer, J., Schoenholz, S. S., Riley, F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In International Conference on Machine Learning,
Fasley, D. and Kleinberg, J. Networks, Crowds, and Mar- kets: Reasoning About a Highly Connected World. Cam- bridge University Press, 2010.
2017. 1, 2, 15
Goldreich, O. Introduction testing graph properties. In Property Testing. Springer, 2010. 16
Eisner, T., Farkas, B., Haase, M., and Nagel, R. Operator Theoretic Aspects of Ergadic Theory. Published: Gradu- ate Text in Mathematics, 2015. 35
Goller, C. and Küccher, A. Learning task-dependent distributed representations by backpropagation through structure. In International Conference on Neural Net-
Ca-Yaniv, R. and Pechyony, D. Transductive rademacher complexity and its applications. In Annual Conference on Learning Theory, 2007. 15
works, 1996. 15
Grohe, M. Descriptive Complexity, Canonisation, and De- finable Graph Structure Theory. Cambridge University Press, 2017. 18, 26
Esser, P. M., Vankadara, L. C., and Ghoshdastidar, D. Learn- ing theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Infor- mation Processing Systems, 2021. 15
Grohe, M. The logic of graph neural networks. In Sympo- sium on Logic Computer Science, 2021. 18

---

Covered Forests
Hamilton, W. L., Ying. Z., and Leskovec, J. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017. 15
weather forecasting. Science, 382(6677)
2023.
Lee, J., Hwang, M., and Whang, J. J. PAC-Bayesian gen- eralization bounds for knowledge graph representation learning. In International Conference on Machine Learn- ing. 2024. 15
Hammer, B. Generalization ability of folding networks. IEEE Transactions on Knowledge and Data Engineering, 13(2):196-206, 2001. 15
Hu, W. Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 2020. 48
Levie, A graphon-signal analysis of graph neural net- works. In Advances in Neural Information Processing Systems, 2023. 15, 16
Levie, R., Monti, F., Bresson, X., and Bronstein, M. M. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):97-109 2019. 15
Ju, H., Li, D., Sharma, A., and Zhang, H. R. Generaliza- tion in graph neural networks: Improved PAC-Bayesing bounds on graph diffusion. arXiv preprint, 2023. 15
Karczewski, R., Souza, A., and Garg, V. On the general- ization of equivariant graph neural networks. In Interna- lional Conference on Machine Learning, 2024. 15
Li, S., Geerts, F., Kim, D., and Wang. Q. Towards bridging generalization and expressivity of graph neural networks. arXiv preprint, 2024. 16
Karpinski, M. and Macintyre, A. Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks. Journal of Computer and System Sciences, 54
Liao, R., Urtasun, R., and Zemel, R. S. A PAC-Bayesian approach to generalization bounds for graph neural net- works. In International Conference on Learning Repre- sentations, 2021. 1, 15
(0::169-77,, 1997. 15
Kawaguchi, K., Deng, Z., Luh, K., and Huang. J. Robust- ness implics gencralization via data-dependent general- ization bounds. In International Conference on Machine Learning, 2022. 1, 5, 15, 32
Lovász, Large Networks and Graph Limils. American Mathematical Society, 2012. 1, 34
Maehara, T. and NT, H. A simple proof of the universality invarian//qquivariant graph neural networks. arXiv preprint, 2019.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. 48
Mao, A., Mohri, M., and Zhong, Y. Cross-entropy loss functions: Theoretical analysis and applications. In Inter- national Conference on Machine Learning, 2023.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2017. 15
Maskey, S., Lee, Y., Levie, R., and Kutyniok, G. General-
ization analysis of message passing neural networks on large random graphs. Advances in Neural Information Processing Systems, 2022. 15
Kireev, D. B. Chemnet: A novel neural network based method for graph/property mapping. Journal of Chemi- cal Information and Computer Sciences, 35(2):175-180, 1995. 15
Maskey, S., Kutyniok, G., and Levie, R. Generalization bounds for message passing networks on mixture of graphons. arXiv preprint, 2024. 15
Kriege, N. M., Morris, C., Rey, A., and Sohler, C. prop- erty testing framework for the theoretical expressivity of graph kernels. In International Joint Conference on Artificial Intelligence, 2018. 16
Merkwirth, C. and Lengauer, T. Automatic generation of complementary descriptors with molecular graph net- works. Journal of Chemical Information and Modeling, 45(5):1159-1166) 2005. 15
Kriege, N. M., Johansson, F. D., and Morris, C. survey on graph kernels. Applied Network Science, 5(1):6, 2020. 16
Micheli, A. Neural network for graphs: A contextual con- structive approach. IEEE Transactions on Neural Net- works, 20(3):498-511 2009. 15
Lam, R., Sanzaez-Gonzalez,, A., Willson, M., Wirnsberger, P., Fortunato, M., Alet, F., Ravuri, S., Ewalds, T., Eaton- Rosen, Z., Hu, W., Merose, A., Hoyer, S., Holland, G., Vinyals, O., Stott, J., Pritzel, A., Mohamed, S., and Battaglia, P. Learning skillful medium-range global
Micheli, A. and Sestito, A. S. A new neural network model for contextual processing of graphs. In Italian Workshop on Neural Nets Neural Nets and International Workshop on Natural and Artificial Immune Systems, 2005. 15
12

---

Covered Forests
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- fions of Machine Learning. MIT Press, 2018. 15
Rauchwerger, L.,, Jegelka, S., and Levie, R. Generalization, expressivity, and universality of graph neural networks attributed graphs. arXiv preprint, 2024. 1, 9, 15, 16
Monti, F., Boscaini, D., Masci, J., Rodolå, E., Svoboda, J., and Bronstein, M. M. Geometric deep learning on graphs and manifolds using mixture model enns. In IEEE Conference on Computer Vision and Puttern Recognition, 2017. 15
Satorras, V. G., Hoogeboom, E., and Welling, M. E(n) equiv- ariant graph neural networks. In International Conference on Machine Learning. 2023. 15
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61 2009. 1,
Morris, C., Ritzert, M., Fey, M., Hamilton, W. I.,, Lenssen, E., Rattan, G., and Grohe, M. Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, 2019. 1, 3. 18, 19, 21, 34, 37
15
Scarselli, F., Tsoi, A. C., and Hagenbuchner, M. The Vapnik- Chervonenkis dimension of graph and recursive neural networks. Neural Networks, pp. 248-259, 2018. 1, 15
Morris, C.,, Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. TUDataset: A collection of benchmark datasets for learning with graphs. arXiv preprint, 2020a. 18, 48
Scavuzzo, L., Aardal, K. I., Lodi, A., and Yorke-Smith, N. Machine learning augmented branch and bound for mixed integer linear programming. arXiv preprint, 2024.
Morris, C., Rattan, G., and Mutzel, P. Weisfeiler and Le- man go sparse: Towards higher-order graph embeddings. In Advances in Neural Information Processing Systems, 2020b. 18
Sokolic, J., Giryes, R., Sapiro, G., and Rodrigues, M. R. D. Generalization error of invariant classifiers. In Interna- tional Conference on Artificial Intelligence and Statistics, 2017. 15
Morris, C., Geerts, F., Tönshoff, J., and Grohe, M. WL meet VC. In International Conference on Machine Learning, 2023a. 2, 6, 15, 22, 36, 37
Sperduti, A. and Starita, A. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 8(3): 1997. 15
Morris, C., L.,, Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M., Fey, M., and Borgwardt, K. Weisfeiler and
Sverdlov, Y., Davidson, Y., Dym, N., and Amir, T. FSW- GNN: A bi-lipschitz wl-equivalent graph neural network. arXiv preprint, 2024. 16
Leman go machine learning: The story so far. Journal of Machine Learning Research, 24:333:1-333:5, 2023b. 1, 18
Morris, C., Frasca, F., Dym, N., Maron, H., Ceylan, i. i., Levie, R., Lim, D., Bronstein, M. M., Grohe, M., and Jegelka, S. Future directions in the theory of graph ma- chine learning. In International Conference Machine Learning, 2024.1 1
Tang, H. and Liu, Y. Towards understanding generalization graph neural networks. In International Conference on Machine Learning, 2023. 15
Tinhofer, G. Graph isomorphism and theorems Birkhoff type. Computing, pp. 285-300, 1986. 25
Nesterov, Y. and Nemirovskii, Interior-Point Polyno- mial Algorithms Convex Programmingg Interior-Poin Polynomial Algorithms in Convex Programming, 1994. 32
Tinhofer, G. note on compact graphs. Discrete Applied
Matematics, pp. 253-264, 1991. 16, 22
Tolstikhin, O. and Lopez-Paz, D. Minimax lower bounds for realizable transductive classification. arXiv preprint, 2016. 15
Otter, R. The number of trees. The Annals of Mathematics, 49, 1948.
Pellizzoni, P., Schulz, T., Chen, D., and Borgwardt, K. M. On the expressivity and sample complexity of node- individualized graph neural networks. In Advances in Neural Information Processing Systems, 2024. 15
van der Vaart, A. W., JA Wellner, J., der Vaart, A. V., and JA Wellner, J. Weak Convergence and Empirical Processes: With Applications to Statistics. 1996. Springer, 1996. 33
Qian, C., Manolache, A., Ahmed, K., Zeng, Z., den Broeck, G. V., Niepert, M., and Morris, C. Probabilistically rewired message- message-passing neural networks. In Interna- tional Conference on Learning Representation, 2024.
Vapnik, V. Statistical learning theory. Wiley, 1998. 15, 36
Vapnik, N. The Nature of Statistical Learning Theory.
Springer, 1995. 1, 15
13

---

Covered Forests
Vapnik, V. N. and Chervonenkis, A. A note one class of perceptrons. Avtomatika Telemekhanika, 24(6):937-945,
M. M., Zitnik, M., Anandkumar, A., Ermon, S., Liò, P., 1964. 15, 36
Yu, R., Günnemann, S., Leskovec, J., Ji, H., Sun, J., Barzilay, R., Jaakkola, T. S., Coley, C. W., Qian, X., Qian, X., Smidt, T. E., and Ji, S. Artificial intelligence for science in quantum, atomistic, and continuum systems. arXiv preprint, 2023.
Vapnik, V. N. and Chervonenkis, Y. On the uniform convergence of relative frequencies of events their probabilities. Theory of Probability & Its Applications, 16(2):264-25) 280, 1971. 15
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference Learning Representations, 2018. 15
Verma, S. and Zhang, Z. Stability and generalization of graph convolutional neural networks. In International Conference on Knowledge Discovery & Data Mining, 2019. 15
Weisfeiler, B. On Construction and Identification of Grapps. Springer, 1976.
Weisfeiler, B. and Leman, A. The reduction of graph to canonical form and the algebra which ap- pears therein. Mtuchno-Technichene (9):12-16, 1968. English translation by G. Ryabov is available at https: /ttp:://wwww.. htww. iti. zcu oz/ ww//18/ httpll_pppe___aa_a_aeee
Informatsia, 2
pdf. 1, 18
Wong, F., Zheng, E. J., Valeri, J. A., Donghia, N. M., Anahtar, M. N., Omori, S., Li, A., Cubillos-Ruiz, A., Krishnan, A., Jin, W., Manson, A. L., Friedrichs, J., Hel- big, R., Hajian, B., Fiejtek, D. K., Wagner, F., Soutter, H. H., Earl, A. M., Stokes, M., Renner, D., and Collins, J. Discovery of structural class of antibiotics with explainable deep learning. Nature, 2023. 1
Xu, H. and Mannor, S. Robustmess and generalization. Machine Learning, 86(3):391 2012. 5, 6, 15, 32
Xu, K., Hu, W., Leskovec, J., and Jegelka, How powerful are graph neural networks? International Conference on Learning Representations, 2019. 1, 18
Ychudai, G., Fetaya, E., Meirom, A., Chechik, G., and Maron, H. From local structures to size generalization in graph neural networks. International Conference on Machine Learning, 2021. 16
Zhang, X., Wang, L., Helwig, J., Luo, Y., Fu, C., Xie, Y., Liu, M., Lin, Y. Xu, Z., Yan, K., Adams, K. Weiler, M., Li, X., Fu, T., Wang. Y. Yu, H., Xie, Y., Fu, X., Strasser, A., Xu, S., Liu, Y., Du, Y., Saxton, A., Ling, H., Lawrence, H., Stärk, H., Gui, S., Edwards, C., Gao, N., Ladera, A., Wu, T. Hofgard, E. F., Tehrani, A. M., Wang, R., Daigavane, A., Bohde, M., Kurtin, J., Huang, Q., Phung, T., Xu, M., Joshi, C. K., Mathis, V., Azizzadenesheli,
K., Fang, A., Aspuru-Guzik, A., Bekkers, E. J., Bronstein,
14

---

Covered Forests
A. Related work
In the following, we discuss relevant related work.
MPNNS Recently, MPNNs (Gilmer et al., 2017; Scarselli et al., 2009) emerged the most prominent graph machine learning architecture. Notable instances of this architecture include, e.g., Duvenaud et al. (2015); Hamilton et al. (2017); Kipf & Welling (2017), and Veličković et al. (2018) 8), which can be subsumed under the message- message-passing framework introduced in Gilmer et al. (2017). In parallel, approaches based on spectral information were introduced in, e.g., Bruna et al. (2014); Defferrard et al. (2016); Gama et al. (2019); Kipf& & Welling (2017); Levie et al. (2019), and Monti et al. (2017) all of which descend from early work in Baskin et al. (1997); Goller & Küchler (1996); Kireev (1995); Merkwirth & Lengauer (2005); Micheli & Sestito (2005); Micheli (2009); Scarselli et al. (2009), and Sperduti & Starita (1997).
Generalization frameworks Vapnik & Chervonenkis (1964; 1971); Vapnik (1998) laid out the theory of statistical learning, introducing the VC dimension and its strong connection to uniform convergence; see also Mohri et al. (201 8). Xu & Mannor (2012) introduced an alternative approach based on a notion of "robustness.". ". Here, if a testing sample is "close" to a training sample, then the expected error is close to the training error, implying a bound on the generalization error; see Section 3. They also showed that so-called weak robustness is sufficient and necessary for generalization. Recently, Kawaguchi et al. (2022) proposed data-driven variations of the framework of Xu & Mannor (2012), allowing for a tighter analysis in practice. Sokolic al. (2017) used Xu & Mannor (2012) to showcase how invariant machine learning architectures, regarding some group action, exhibit smaller generalization error than their non-invariant counterparts.
Generalization abilities of MPNNS and GNNs Scarselli et al. (2018) used classical techniques from learning the- ory (Karpinski & Macintyre, 1997) to show that MPNNs' VC dimension (Vapnik, 1995) with piece-wise polynomial activation functions on a fixed graph, under various assumptions, is in O(P2n log n), where P is the number of parameters and n is the order of the input graph; see also Hammer (2001). We note here that Scarselli et al. (2018) analyzed a different type of MPNN not aligned with modern MPNN architectures (Gilmer al., 2017); see also D' Inverno et al. (2024). Garg et al. (2020) showed that the empirical Rademacher complexity (see, e.g., Mohri al. (2018)) of a specific, simple MPNN architecture, using sum aggregation and specific margin loss, is bounded in the maximum degree, the number of layers, Lipschitz constants of activation functions, and parameter matrices' norms. We note here that their analysis assumes weight sharing across layers. Recently, Karczewski et al. (2024) lifted this approach to E(n))equivvriaat MPNNs (Satorras et al., 2023). Liao et al. (2021) refined the results of Garg et al. (2020) via a PAC-Bayesian approach, further refined in Ju et al. (2023). See Lee et al. (2024) for (transductive) PAC-Bayesian generalization bounds for knowledge graphs. Maskey et al. (2022; 2024) assumed that data is generated by random graph models, leading to MPNNs' generalization analysis depending on the (average) number of vertices of the graphs. In addition, Levie (2023) and Rauchwerger et al. (2024) defined metrics on attributed graphs, resulting in generalization bound for MPNNs depending the covering number of these metrics. Verma& & Zhang (2019) studied the generalization abilities of 1-layer MPNNs in a transductive setting based on algorithmic stability. Similarly, Esser et al. (2021) used stochastic block models to study the transductive Rademacher complexity (Eniva & Pechyony, 2007; Tolstikhin & Lopez-Paz, 2016) of standard MPNNs. See also Tang & Liu (2023) for refined results. For semi-supervised vertex classification, Baranwal et al. (2021) studied the classification of a mixture of Gaussians, where the data corresponds to the vertex features of a stochastic block model, deriving conditions under which the mixture model is linearly separable using the GCN layer (Kipf & Welling, 2017). Recently, Morris et al. (2023a) made progress connecting MPNNs' expressive power and generalization ability via the Weisfeiler-Leman hierarchy. They studied the influence of graph structure and the parameters' encoding lengths on MPNNs' generalization by tightly connecting 1-WL's expressivity and MPNNs' VC dimension. They derived that MPNNs VC dimension depends tightly on the number of equivalence classes computed by the 1-WL over given set of graphs. Moreover, they showed that MPNNs' VC dimension depends logarithmically on the number of colors computed by the 1-WL and polynomially on the number of parameters. Since relying on the 1-WL, their analysis implicitly assumes a discrete pseudo-metric space, where two graphs are either exactly equal or far apart. One VC lower bound reported in Morris al. (2023a) was tightened in Daniëls & Geerts (2024) to MPNNs restricted to using a single layer and a width of one. In addition, Pellizzoni et al. (2024) extended the analysis of Morris et al. (2023a) to node-individuallzed MPNNs and devised a cademacher-complexityy based approach using a covering number argument (Bartlett et al., 2017). Similar to us, they also assume MPNNs that are (Lipschitz) continuous regarding a given pseudo-metric However, unlike the present work, they do not derive such pseudo-metre and do not provide an explicit bound on the covering number. Franks et al. (2024) studied MPNNs' VC dimension assuming linearly separable data and showed a tight relationship to the data's margin, also partially explaining when more expressive
15

---

Covered Forests
architectures lead to better generalization. Li al. (2024) build on the margin-based generalization framework proposed by Chuang al. (2021); which is based k- Variance and the Wasserstein distance. They provide a method to analyze how expressiveness affects graph embeddings" inter- and intra-class concentration. Kriege et al. (2018) leveraged results from graph property testing (Goldreich, 2010) to study the sample complexity of learning to distinguish various graph properties, e.g., planarity or triangle freeness, using graph kernels (Borgwardt et al., 2020; Kriege et al., 2020). Finally, Yehudai et al. (2021) showed negative results for MPNNs' generalization ability to larger graphs.
Graph (pseudo-)distances Based on older ideas in Dell al. (2018); Dvorák (2010); Tinhofer (1991), Böker (2021) defined the Tree distance, pseudo-metric on the set of graphs, and showed tight correspondence between the former and homomorphism densities regarding trees, which also implies equivalence to the 1-WL. Böker et al. (2023) later lifted the result to specific MPNNs using sum aggregation, deriving uniform continuity. Based on this, Sverdlov et al. (2024) defined an extension of the Tree distance to account for labeled graphs and derived a specific MPNN architecture that exhibits a bi-Lipschitz property. Chuang & Jegelka (2022) defined the TMD distance between the computation graphs of specific MPNNs via a hierarchical optimal transport problem, showed equivalence to the 1-WL, and derived Lipschitz constants. In addition, they studied MPNNs' generalization abilities under distribution shifts. Levie (2023) defined the graphon-signal cut distance, showed that MPNNs are Lipschitz continuous concerning this metric, and derived bound on the covering number of the space of attributed graphs under this metric. As result of the Lipschitz continuity and finite covering, he derived generalization bound for MPNNs. However, the graphon-signal cut distance topology does not give the coarsest topology under which MPNNs are continuous. At the same time, in the present work, we find such a maximally coarse topology, which, in principle, reduces the covering number (asymptotically in the radius). Most recently, Rauchwerger et al. (2024) extended Böker et al. (2023) to attributed graphs, i... the vertex features are in R deriving a universal approximation theorem for MPNNs over such graphs and generalization bounds for MPNN using a covering number argument based on the technique from Levie (2023). Unlike the present work, they do not derive explicit bounds on the covering number and only study specific MPNN layers.
B. Detailed notation
Here, we outlined our notation in more detail.
Basic notations Let N == (1. and No = No (0). The set IR+ denotes the set of non-negative real numbers. For n N, let [n] = [I.......] , C N. We use B to denote multisets, i.c., the generalization of sets allowing for multiple. finitely many instances for each of its elements. For two non-empty sets X and Y, let Y denote the set of functions from X to Y. Given set X and subset A C X, we define the indicator function 1 X + {0,1] such that ax(x) = if & E A, and (x) = 0 otherwise. Let M be an n X m matrix, n > 0 and m > 0, over IR, then M.., M. E [m]. j E [m]. are the ith row and jth column, respectively, of the matrix M. Let N be an n X n matrix, n > O, then the trace Tr(N)= = Eie(n) N₁. In what follows, o denotes an all-zero vector with an appropriate number of components.
Norms Given a vector space V, norm is function 11 - R+ which satisfies the following properties. For all vectors u. v E V and scalar E I, we have (i) non-negativiry, || 2 0 with ||e||| = 0 if, and only, if v = o, (ii) scalar multiplication, ||sa|| = |s| ||w]] and the (iii) triangle inequality holds, I|u + all I || + || When V is some real vector space, say Rixdd for d > 0, here, and the remainder of the paper, || ||| and || ||2 refer to the 1-norm
||0||| = |2 + |zal and 2-norm ||0|||- = / +.... x². respectively. for x E R 1x
When considering the vector space R.x= of square n X n matrices, matrix norm || is a norm described above, with the additional property that ||MN]| < [|]]]|| for all matrices M and N E R A matrix norm is called induced, or operator norm, if M == SUPZER= |=||=1 M for some vector norm || I| on IR... A matrix norm is called element-wise if it is defined in terms of a vector norm || by interpreting M as a vector in IR"". However, not every vector norm results in an element-wise matrix norm. For instance, the norm | ||x maxx,jejn] [mal is a valid norm on R= but does not satisfy the conditions of a matrix norm on Rax* Later in the paper, we use the cut norm on p=x= defined by
M Ilo :=
max
Σ
mij
(11)
Sc|))TC()]]
VES
Finally, for p E glxd d >> 0, and E > O, the ball (p e, d) = {s gixd the context, we omit the subscript.
||p - s|l <E}; when the norm is clear from
16

---

Covered Forests
Graphs An (undirected) graph G is a pair (V(G), E(G) with finite sets of vertices V(G) and edges E(G) S { v) S V(G) & v}. vertices or nodes V(G) and edges E(G) _ {{u C V(G) u * v). The order of graph G is its number [V(G) of vertices. If not stated otherwise, we set n == IV(G) and call G an n-order graph. We denote the set of all n-order (undirected) graphs by Gn and the set of all (undirected) graphs up to n vertices by ggn. In a directed graph, we define F[G) _ V(G)², where each edge (u, v) has a direction from u to v. Given a directed graph G and vertices u, V E V(G), we say that v is a child of u if (u, v) E EGG). A (directed) graph G is called connected if, for any u, v E V(G), there exist r E N and (ui,..., } S V(G), such that (u, u1), (u), u2),..., (u,, v) E E(G), and analogously for undirected graphs by replacing directed edges with undirected ones. We say that a graph G is disconnected if it is not connected. For a graph G and an edge e E E(G), we denote by G \ the graph induced by removing the edge& from G. For an n-order graph G' E Gn. assuming V(G) [n], we denote its adjacency matrix by AG) E {0,1) (0,1)axn, where A(G) on 1 if, and only, if {u, w) E F(G). The neighhorhood of vertex v E VVG) is denoted by Nc(v)= == {u E (GG I {u, u} E E(G)), where we usually omit the subscript for ease of notation, and the degree of a vertex u is [a(()] A graph G is a tree if it is connected, but G \ c is disconnected for any e E E(G). A tree or a disjoint collection of trees is known as a forest.
rooted tree (G,r) r) is tree where specific vertex r marked as the root. For rooted (undirected) tree, we can define an implicit direction on all edges as pointing away from the root; thus, when refer to the children of vertex u in rooted tree, we implicitly consider this directed structure. For S C V(G), the graph G[S] == (S, Eg) is the subgraph induced by S, where Es- == {(u, v) E E(G) u, E S). A (vertex-)labedd Jlabeled graph is pair (G, fG) with a graph G = (V)G), E(G)) and a (vertex-)label function la: V(G) + Σ, where Σ is an arbitrary countable label set. For a vertex V E (G), (((v) denotes its label. A Boolean (vertex- jd-rex---dllbeled graph is a pair (G.LG) with a graph G =
and a label function c:: V(G)- + {0,1]d We denote the set of all n-order Boolean d-labeled graphs as G nn,d An attributed graph is a pair aG) with a graph G = (V)G), E(G)) and an (vertex-)attribute Jattribute function ac: V(G) + Rixd, xd for d > 0. That is, contrary to labeled graphs, vertex annotations may be from an uncountable set. The attribute or feature of v E V(G) is (G()). We denote the class of all n-order graphs with d-dimensional, real-valued vertex features by I
Two graphs G and H are isomorphic there exists bijection ip: VGG) - ((H) that preserves adjacency, i.e., (u, v) E(G) if, and only, if (f(u), ((b)) E(H) In the case of labeled graphs, we additionally require that (a(v) = 6n (p()) for (G). Moreover,
call the equivalence classes induced by isomorphism rypes and denote the isomorphism type of G by (G). A graph class is set of graphs that is closed under isomorphism. Given two graphs G and H with disjoint vertex sets, we denote their disjoint union by GÚH.
B.I. Continuity on metric spaces
Let (X, dx) and (),, dy) be two pseudo-metric spaces. A function f: X + y is called cy-Lipschitz continuous if, for x E X,
dy(f(z), sq
We also define a weaker notion of continuity. known as uniform continuity. Specifically, we say that f is uniformly continuous if, for every e > 0, there exists (e,, f) > O. possibly dependent on e and f. such that, for x, E X,
(x x¹) S (e, f) = (f(x, Se.
It is easy to check that Lipscchit continuity implies uniform continuity with y(E,f) = 5/eg.
Feed-forward neural networks An L-layer foed-forward neural network (FNN), for L E N, is a parametric function
FNN!") gg + R, d > O, where 0 = (w(1).... (1l)).....ld) C e and W e Rdxd, for i E [L- 11, and ((4) e pdx1
where
x + ( (.... (a((ww w(e) ... w(l)) E R.
for x E B Xd Here, the function a: IR + R is an activation cectivatiofuunctiionn function, applied samponent-wiselyy e.g., a rectified linear unit (ReLUU, where a (x) = max(0, .r.. For an FNN where we do not need to specify the number of layers, we write FNN,.
17

---

Covered Forests
C. The 1-dimensional Weisfeiler-Leman algorithm
The 1-dimensional Weisfeiler-Leman algorithm (1-WL) or color refinement is a well-studied heuristic for the graph isomorphism problem, originally proposed by Weisfeiler & Leman (1968).² Intuitively. the algorithm determines if two graphs are non-isomorphic by iteratively coloring or labeling vertices. Given an initial coloring or labeling of the vertices of both graphs, e.g., their degree or application-specife information, in each iteration, two vertices with the same label get different labels if the number of identically labeled neighbors is unequal. These labels induce vertex partition, and the algorithm terminates when, after some iteration, the algorithm does not refine the current partition, i.c., when a stable coloring or stable partition is obtained. Then, if the number of vertices annotated with a specific label is different in both graphs, we can conclude that the two graphs are not isomorphic. It is easy to see that the algorithm cannot distinguish all non-isomorphic graphs (Cai et al., 1992). However, is a powerful heuristic that can successfully decide isomorphism for a broad class of graphs (Arvind et al., 2015; Babai & Kucera, 1979).
Formally, let (G, lG) be labeled graph. In each iteration, t >> O, the 1-WL computes vertex coloring C.:: V(G) - N, depending on the coloring of the neighbors. That is, in iteration t > O, we set
C/ (v) = RELABEL (CCL-(0), (C) JE E (()))).
for vertex v E V(G,, where RELABEL injectively maps the above pair to a unique natural number, which has not been used in previous iterations. In iteration O, the coloring Cj == lg is used. 8 To test whether two graphs G and H are non-isonee non-isomorphic, we run the above algorithm in "parallel" on both graphs. If the two graphs have a different number of vertices colored e E N at some iteration, the 1-WL distinguishes the graphs as non-isomorphic. Moreover, if the number of colors between two iterations, / and (L 1), does not change, i.e., the cardinalities of the images of Ct and C++, are equal, or, equivalently,
(v) = ()w) = C(+2(1) (w))
for all vertices v, w E V(GHH), then the algorithm terminates. For such 4, we define the stable coloring C.e C2.(v) = (v), for a E (GÚH), The stable coloring is reached after at most max[VV(G)) VV } iterations (Grohe, 2017). Finally, when considering graphs of a fixed order n, we define the equivalence class of a graph E Gn induced by 1-WL as [G] (G' E Gn G. G' are 1-WL indistinguishable) and the quotient space consisting of the equivalence classes as Gn/-m = [ G Gn). We similarly, use Ca/~m, for the quotient space of equivalences classes after I. iterations, for LEN.
Connection between the 1-WL and MPNNs Morris et al. (2019) and Xu et al. (2019) showed that any possible MPNN architecture is limited by the 1-WL in terms of distinguishing non- -oomooooopppc graphs. Furthermore, for the MPNNs defined in Equation (3), Morris et al. (2019) showed that, under appropriate parameter selections, they can achieve expressivity equivalent to that of the 1-WL: see Grohe (2021) and Morris et al. (2023b) for details. Similarly, building on Morris et al. (2019), it is straightforward to show that the MPNNs defined in Equation (1) can distinguish the same pairs of non-isomorphic n-order graphs as the 1-WL.
Unrollings characterization for 1-dimensional Weisfeiler-Leman algorithm Following Morris et al. (2020b), given an n-order labeled graph (G, (G), we define the unrolling tree of depth L E No for vertex V(G), denoted as unr(G, u, L), inductively as follows.
1. For L 0, we consider the trivial tree as an isolated vertex labeled la(u).
2. For > O, we consider the root vertex with label (u) and, for o E NN)), we attach the subtree unr(G, u, L - 1) under the root.
The above unrolling tree construction characterizes the 1-WL algorithm through the following lemma.
Lemma 17 (Folklore, see, c.g., Morris et al. (2020a)). For L E No. given a labeled graph (G, EG) and vertices u, v E (G),
the following are equivalent.
SStrictyy speaking, the 1-WL and color refinement are two different algorithms. That is, the 1-WL considers neighhors and non- neighhors to update the coloring, resulting in a slightly higher expressive power when distinguishing vertices in given graph; see (Grohe, 2021) for details. Following customs in the machine learning literature, we consider both algorithms to he equivalent. Heere, we implicitly assume an injective function from Σ, to N.
18

---

Covered Forests
1. The vertices u and have the same color after L iterations of the I-WL.
2. The unrolling trees unr(G, u, L) and unr(G, v, L) are isomorphic.
C.1. The mean 1-dimensional Weisteiler-LLema algorithm
Similarly to 1-WL, we can define the meen-aggregation 1-WL (1-MWL) on a labeled graph (G, (G) and give a similar characterization based on unrolling trees denoted as m-unr(G, u, L). We will later use the 1-MWL to characterize the expressive power of MPNN layers using mean aggregation. Before we describe the 1-MWL algorithm and the unrolling construction, we introduce some notation. For given multiset X, we denote by set(X) the consisting of all distinct elements of X. Additionally, for each x set(X), we denote by mulx the multiplicity of the element x E X in the multiset. We define
(X) == mulx [X]
|x )
mapping each multiset set of pairs, encoding the frequency of each element in the multiset. Also, given a directed tree T, for each vertex E VTT), we denote by chr(u) the of children of the vertex (T",, i.e., vertices that are one level below and are connected u. Moreover, for vertex (TT), we denote by subr(u) the rooted directed subtree under vertex with root u. Finally, for vertex u E ((T), we define desr(u) {[ {r(sub((e)
chr(u)):
Given labeled graph (G, la), the 1-MWL computes a vertex coloring C. V(G) - N. That is, in iteration > 0, we set
C. RELABEL(C("T(0) freq(M(-1())))
for v E V(G), where RELABEL injectively maps the above pair unique natural number, which has not been used in previous iterations, and (v) = [C. (u) u (ub) B. In iteration 0, we set Co = la.
Unrolling characterization for the 1-MWL. Given a labeled graph (G, E) and a vertex u E V(G), we define the mean unrolling tree of depth I. m-unr((, u, L), characterizing the 1-MWL up to L iterations. For a vertex u E V(G), starting from the original unrolling tree = unr(G, u, L) depth L, considering the root as level 0, we prune the tree as follows.
1. Starting from level
2. For all vertices at level 1, we consider the multiset desr(u). Let be the greatest common factor of the elements in (muldecr((w) (a) E set(desy(u)) (u))}. then for each E set(decr (u)), we drop s=ع (m)des copies of from decr (u), and we also prune the corresponding subtrees from T, leading to an updated tree.
3. I = 0, the pruning is done; otherwise, we set l 1 1 and repeat step 2 with the updated tree T.
We call the above-described algorithm the mean-pruning of the tree T. See Figure 3 for illustration of the mean- wean--runinn process and the mean-unrollin unrolling tree. The above mean unrolling tree construction characterizes the 1-MWL through the following result.
Proposition 18. For L E No. given a labeled graph (c) and vertices u, E VVG), the following are equivalent.
1. The vertices have the same color after L iterations of the 1-MWL.
2. The (rees m-unr(G, u, L.) and m m-unr(G, v, L.) are isomorphic.
Connection between the 1-MWL and MPNNs Similarly to the results by Morris al. (2019), we show in Proposition 21 in Appendix C.2 that any possible MPNN architecture described by Equation (5) is limited by 1-MWL in terms of distinguishing non-isomorphic graphs. Furthermore, again, for the MPNNs considered in Equation (5), we show that, under appropriate parameter selection, they can achieve expressivity equivalent to 1-MWL.
C.2. Mean 1-WL unrollings characterization
Here, we show the correspondence between mean unrollings, the 1-MWL, and mean-aggregation MPNNs. We begin by showing a characterization of the 1-WL through the mean unrollings defined in Appendix C.I
We first show the following auxiliary lemma, which shows that the computation of m-unr(-) at depth + induces a finer partition of the set of vertices compared to the partition induced by m-unr(:) at depth T..
19

---

Covered Forests
unr(G, u3, 3)
m-unr(G, u3,
mean-pruning
G
unr(G, u4, 3)
m-unr(G, u4, 3)
mean-pruning
Figure 3. An illustration of the unrolling trees and the process of obtaining the mean unrolling trees from the unrolling through mean pruning.
Lemma 19. For L. E N. given labeled graph (G, and vertices u, E V(G), the following holds,
m-unr(G, u, L 1) = m-unr v, L = m-unr(G, u, L) = un, v,
Proof. As described in Appendix C.I, m-unr(G, u, +++1 is derived by applying the mean-pruminn process to unr(G, v, L+ 1). Consider the labeled tree (T1, ) = unr(G, v, L + 1). We define the L-depth labeled tree (T), lT;) induced by (Ti, (T,) by relabeling all vertices at level L of Ti and then remove all leaves, i.e., vertices at level L We relabel vertices level as follows.
For vertex level L of Tr with label En (z), let Mr,,, denote the multiset of labels of its children, i.e.,
Mr ( (v) y E chr, (x)
We compute the new label
Exy (1) = RELABEL (eTs (x), freq(Mn.
(12)
Similarly, let (T2, Exy) unr(G, u, + 1), and define (Tz, lTy) analogously. By definition, m-unr(G, u, L 1) ~ m-unr(G, L + 1) if, and only if, the trees T and TV obtained by applying the mean-pruning process Ti and Ty. respectively, isomorphic. Now, if T Th it directly follows that m-unr(G, u, T.) = m-unr(G, u, L). The reasoning is as follows: the trees TV and TV up to level L 1 are structurally identical to unr(G, u, L 1) and unr(G, v, L + 1), respectively. Furthermore, if two vertices in layer L of Ty have the same label, then these vertices must have also had the same label before the relabeling step (i.e., in unr(G, u, L. + 1)). This follows directly from Equation (12). Therefore, applying the mean-prn mean--runing process to T and T3 results in isomorphic graphs, applying the mean-pruning process to unr(G, u, L) and unr(G, v, L) must also yield isomorphic graphs.
We next show the correspondence between mean unrollings and the 1-MWL.
Proposition 20 (Proposition 18 in the main paper). For E No. given a labeled graph (G, tG) and vertices u, v E V(G), the following are equivalent.
1. Vertices u and u have the same color after I. iterations of the 1-WWL.
2. The trees m-unr(G, u, L.) and m-unr(G, I.) are isomorphic.
Proof. For the proof of both directions of the proposition, we will need the following observation.
Observation (Recursive formulation of mean unrolling). For each E N, u E V(G), the mean unrolling m-unr u, L+ 1) can be constructed by considering a root vertex with label lo(w) and attaching to this root vertex all m-unr(G, w, for E (u), and finally performing the process described in step 2 of the m-unrolling construction on level
20

---

Covered Forests
We now prove the two directions.
I = 2: By induction on L. For L 0, the result is clear. For the induction hypothesis, we assume that for some L E N, and for all vertices u, U V(G), if C,.
Ct."("), (v), then m-unr(G, u, L) = m-unr(G, v, L). Now, for vertices u, V(G), if CLi (u) Cli L+1(1) (v), then by definition, freq (Mz(M)) E (.) We consider the tree T. with root and attach all m-unr(G, L). for w E Nu)). Analogously, we consider the tree Tr with root By the observation above, we drop (if necessary) all the subtrees rooted at level of T. as described in step 2 of the m-unr operation, leading to new tree T5 which is isomorphic to m-unr(G, L + 1). We do the same on T., leading to T = m-unr(G, v, L + 1). Now, using the induction hypothesis, since freq(ML (u)) = (r))(M(())) there exists a bijection a between the subtrees / rooted at level of Th and the subtrees rooted at level 1 of TV such that = ((), for all subtrees t. Finally, because C (u) = C (v) implies C (u) = CO the roots of T3 and TV have the same color, implying that m-unr(G, u, L + 1) m-unr(G, u, L, -+
( (v))), where M. ((CL'"
2 + 1: For the reverse direction, we again proceed by induction. If m-unr(G, u, L + 1) = m-unr v, L + 1), the observation above and the inductive hypothesis directly imply that freq (u)) freq(Mz(v)). Furthermore, by Lemma 19, m-unr(G, u, L + 1) = m-unr(G, v, L + 1) implies m-unr(G, u, L) = m-unr(G, v, L), which concludes the proof.
Next, we show that mean-aggregation MPNNs as defined in Equation (5) are limited by 1-MWL in distinguishing non- isomorphic graphs. In addition, we prove that under an appropriate parameter selection, both algorithms can achieve exactly the expressivity of the 1-MWL. Formally,
Proposition 21. Let (G, lG) E Gha be a labeled graph and C. be the coloring function of 1-MWL on iteration t >> 0. Then for all I 0, u, v E (G) and for all MPNNs described by Equation (5), we have that,
(l. cl.m(())
h h
Additionally, for L O, there exists a choice of parameters Wil), w s [4]. such that if h( is the MPNN induced by ( W!? bb, we have that:
h (t)
h(())
Cl. (T.).......
Proof. We recall that for a multiset X, freq X) is defined as
freq(X)= = {( mulx(x))
x set(x)]
We now define the following class of MPNN architectures:
UPD (t) (AGG())))))) (freq (n | E N(w)))))
(13)
where (*) and (t) are two parameterized functions. It suffices to show that the MPNNs described by Equation (5) are a special case of the MPNNs in Equation (13). The proof then proceeds by induction exactly as in Morris et al. (2019, Theorem 1). To verify this, we set
AG = Σ
a1 02 (2)
(11, = sp x1
(())
W + x22
The other direction follows by straightforward adaption of the proof of Morris et al. (2019, Theorem 2) by adapting Lemma 11 and 14.
21

---

Covered Forests
D. Pseudo-metries graph
First, let us consider (pseudo-)mettre
on the set of n-order unlabeled graphs In, for n E N. The straightforward way to define a metric on Gn is through the adjacency matrices of the graphs. To that, for n E N, a matrix P E [0,1]=x= is permutation matrix if P.P.P 1 I, for i [na], and P || I, for [n]] More generally, matrix S E [0,1] is for j [n]. Let P, and D,, denote the sets of n
doubly-stochastie matrix if s, 1, for i [n], and || permutation and doubly- Soubly-stochastic matrices, respectively. Now observe that graphs G and H E Gn are isomorphic if, and only, if there exists a permutation matrix P E Pn such that A(G) (H). Similarly, from Tinhofer (1991), it follows that the graphs G and !/ are not distinguished by 1-WL if, and only, if there exist of a doubly-stochastic matrix S such that A(G)S = SA(H.
Based on the above, for N, let G, H In and ||-I| a norm in Rax", we define the following pseudo-metris on 9n.
6 H)
min PEP, ||())) A(G))-PA(H)])
By definition, it holds that 61-n H) 0 if, and only, if G and H. are isomorphic.
Secondly, we extend the above definition to the set of labeled n-order graphs. For simplicity and to be aligned with Morris et al. (2023a), we consider d- d-dimensional Boolean features, though the following distance can also be defined the set of real- valued features. Given two labeled n-order graphs (G, la), EH) E g and a distance function dist: {0,1) x {0,1] + RR+ assuming V(G) = V(H) = [m)] we define the distance matrix L(G, H) = [dist((a(i),, en (i Following Bento & loannidis (2019), we define the following metric on G d: for any entry-wise operator norm |-|||
b (G, H) = min |A(G)) PA(H)) + ((G))- Tr(PTT(G,
PEP,
To see the effect of the second term, suppose that dist is the discrete distance function. Then, pin, Tr,PTL(G, H)) finds label-preserving vertex permutation. Again, we can easily verify that 6|-1 H) = 0 if, and only, if (G, {c) and (H, EH) are isomorphic.
E. Proof of the pseudo-metric property and 1-WL equivalence
In this section, prove that the family of distances defined in 9 by Equation (8) constitutes well-defined eseudo-metric on the set of graphs. We then show that this family of pseudo-metrics is equivalent in expressivity to the 1-WL algorithm, i.e, we show Proposition 1.
To establish the pseudo-metric property, we use the result by Bento & Ioannidis (2019) showing that for every entry-wise norm, the following distance defines a pssuddommetic on G
(G, min SED,
|A(G)S- +(S
where
= dis=(((((()))
for some distance function dist (e.g., en if (1) # (5) and 0 otherwise.)
However, the cut norm is not entry-wise norm, and thus, we need to prove the pseudo-metric property separately. Nevertheless, we follow the argumentation used for entry-wise norms. To achieve this, we first establish the following auxiliary lemma.
Lemma 22. Let A be the adjacency matrix of an n-order graph, then for all doubly matrices S E Dn, the following inequalities hold,
|| | |a S || Al
||S Io S ||llo-
Proof. By the Saachoff-oon-Neummnn theorem, each doubly- stochastic matrix can be written as a convex combination of permutation matrices. That is, if S D,, there exist a N, A1.... Ag E [0,1], and permutation matrices Pt,..., Pt.
22

---

Covered Forests
such that S = P,Ps Therefore, if A is the adjacency matrix of n-order graph, then
h |AS| |A Σ A.POI S Σ Arll AP ==1
& Σ ArlAlo ==1
||Al|o:
where the first inequality is derived from the sub-additivity and the absolute homogenicity property of the cut norm. In addition, because the cut norm is invariant under permutations, it holds that |.P.lllo = || We similarly can prove the second inequality.
We are now ready to show the pseudo-metric property of oz on Ph.
Proposition 23 (First part of Proposition I in the main paper). The distance functtin 02 defines pseudo-melric on G n. for d N
Proof. Let the graphs (Ga, la.), (GB, (Gx) (Gc. (Go) E g Symmetry. To prove the symmetry property, i.e. (G Gn) = 50 (Gn. GA), we use the following properties:
1. For all adjacency matrices A, || la = |
2. For all S D,;; ST D..
3. Tr(ATB) = Tr(BB)).
We then have,
J7 G
min |A(G)) STGGG) SED, min [SA(Gn) AGG SED,
min SED,
|A(Gn) - STA
min STED.
[A(Gn) - ST +
min STED.
|A(GB) ST A
min |A(GB) I SEP,
(GB, GA),
desired.
Triangle inequality. We define S' = argminsen, agginsen.lAA(GA) SA(Gn)lln + Tr(ST A, Gn)) and S" arg minsep, (G SA(Go)llo+ m, A Gc)). It is easy to verify that the product of two doubly-stochastic matrices is a doubly-stochastic matrix and, therefore,
GG < |A(GA))'SS' S'S A
Therefore, suffices to show that
S'S A'G''l |A(GA)S - + A(Gc)ll -
and,
(S((S'S"))LLC Gc)) S Tr((S') LG GB)) + (C(S"" Gc)).
For the first inequality, we use Lemma 22 and the triangle inequality for the cut norm,
S'GG) s's"'' A(G))ln & |A(GA))''S" - S' S'A(G)) In
+ +I ([S'A(G))S"" S'SS" ln < ||AGA))S - S'A(GG) [A(GB) AGGoll)
23

---

Covered Forests
For the second inequality, we the notation dist(E (i)) for the distance between the label of vertex i V(G) and the label of vertex j E ((H) (e.g., ( En (n(i)) (1) where 1 is the indicator function.)
T((A'S"))L(AAGGG)) = Σ
Σ
& dist(fG. (G),
SJlMn kE[n]
Σ
E
s (1), (i), (k)) + dist(fan,()) (i))
Jefl ke(m]
= Σ
sLAR dist(La CG, (1), &Go (k))
Σ
Kki
ke
jEIn]
Σ
thi dist (fG (k), (())
Σ de
KJEM
iE(n)
$ (I((S)) + "T(((") Gc)),
where the first incquality follows from the triangle inequality of metric dist, and the last inequality from || || S and ||S I 1.
We now show the equivalence of the pseudo-metric of and the 1-WL in distinguishing non-isomorphic graphs. Lemma 24 (Second part of Proposition in the main paper). For all n. d E Nand G, H G we have that (G, H) = 0 if, and only, if G and H are 1-WL indistinguishable
Proof. For all n, d E N and G, Hl E Gh. we simplify the notation as follows. Once an adjacency matrix A(G) is fixed for an n-order graph G, we refer to the i-th vertex of G as the vertex corresponding to the i-th row of A(G), for i E [n]. We define an injection 0: I + {n + 2, n + J... Then, we introduce transformation Te: G + Gsm's which maps graphs G E Gh.d unlabeled graphs G' E Ggm', where m' is sufficiently large. The transformation Ta is defined as follows.
Given (G) E Gh for each u E V(G), we add (()) new vertices, denoted u1...., (o()a(u))) to the graph G. These new vertices form a clique and one of them (without loss of generality, u1) ) connected u. Formally, we define:
To((G)(a)) =
where
(((att))
fuit )
V(G')=V(G)
U LEV(G)
U i=1
and
((E((N))
E(G') U(G)U
U NEV(G)
fu,ui}
u
U
fus
uz}
(EV(G)
Let m denote the number of added vertices, i.e., Enevioy ((lo(u)). The adjacency matrix A('") of the transformed graph G' can then be represented in the following block structure:
A(GG) B
A(G')
B D
where B E Raxm and D E m are symmetric.
Now, let G, E G. and their transformed graphs be G' = =Go(G) and H' (H)). We aim to prove the equivalence of the following statements, completing the proof.
1. (G', H') =
2. G' and H' are WL-innistinguuihable.
24

---

Covered Forests
44
34
22
u
G
(o(G)
To
(0(o) 5, 0(0)= 6)
17
w
V1
V2
W1
W2
96
V3
W6
W3
V5
U4
W55
WA
Figure 4. An illustration of the Th transformation of labeled graph G' into unlabeled graph (G). For illustration reasons the colors red and blue have chosen as the initial node features in R.--
3. G and H are I----indiitinguishable.
4. (G, 0.
The equivalences follow outlined below:
1. This a direct result of Tinhofer (1986).
2. 3. Let C2(2) and cP2) represent the coloring functions of the 1-WL algorithm applied to the graphs G' and (G, LG). respectively. We aim to show that for all E V(G), if CkC) (u) CnO) (v), then it follows that c. (w) = c2 (v).
To do this, we will prove by induction that for each if (4)(2)) c( then c(") (u) (( (c).
(1)
For t = 0, if CK (u) = C22y (v)) we conclude that (a(u) = la(v). Otherwise, the vertices u and would have different cliques attached to them, resulting in distinet colors the second iteration. Now, assume the induction hypothesis, i.e., (4)
C( = C( (u) = (v). for t E N. Next, suppose that (++3(u) = C (v). We further note that the added vertices in G', even from the first iteration, have different colors from those of the original vertices since their degrees are strictly larger than n + 1, while the original vertices have degrees strictly smaller than n + That is, No (w:) > n and No [N)( < n + for all E V(G), [0())(u))] By the definition of the 1-WL algorithm and applying the induction hypothesis, obtain the following,
cf (c). (C (w) No (w) = (C.
No
By the second equality and the fact that the added vertices, namely (u. (us)veotec(u)) for u V(G), will always have distinct stable colors from the original vertices (i.e., vertices in V(G)), we deduce that
(f (w) w No(w)) = (Cf (w) w No(u)).
This completes the induction.
3. = suffices to show that c ( (w) = (. (v) implies the following three equalities.
(a) (u) ",
(o), for all u, V(),,
(b) ((0 (m))
(c) = (1)),, for all i,j ((((()))
25

---

Covered Forests
We can prove (a) = (b) and (b) = (c) by induction. First, we show that if C( (w1) = c (m)) then
(4 - c (13) for all u, v E (G) and é.j E [0((a(u))] (implying (b) = (c)). Similarly, we can show by
induction that C _( (u) c (v) implies C/41 (ui) ((4((1)) for all U. V(G) (implying (a) (b))
Next, we use again induction to prove (() (w) = ()) (v) = (a). If (+1 (u) = C++1 (v), by the induction hypothesis and the definition of the 1-WL algorithm, we obtain.
(t) (v),
(N) Hence, have c WE E Nc(u) = (cttt w E No(u))
By (b) and (c), conclude that (()
(o(()) (w)
((O) (u) = (v), completing the proof.
11 4.: Assume 0% (G', H') = ||A(')) - A = 0 for some doubly stochastic matrix S". By Theorem
3.5.11 in Grohe (2017), if Coo denotes the stable coloring under the 1-WL algorithm on G", H' then S' can be explicitly expressed
C C/ (ob if Ci) (j) c for some color e,
0,
otherwise.
The newly added vertices in G' and H' always have stable colors distinct from those of the original vertices since their degrees are strictly larger than - 1, while the original vertices have degrees strictly smaller than n + 1. Consequently, S' has a block diagonal structure
S 0
$
where S E Da and S E Dm. Substituting into the equation ||A(G") - S'A(H') O, we deduce that
|A(G)) SA(H) =0.
The term Tr(ST L(G can be written as
Tr(ST H))
E
Stg LGG H)
(EV(G))EV(M))
If Eievio) LG, * O, then, there exists i E V(G) and j E V(H) for which S. > 0 and fa(i) # EH(I) which is contradiction since St,, S' b.j 0 and if (a(1) # (H(i), there would have been attached different vertices to vertices i and j. implying that they would have different stable colors. Hence, 8G H) = 0.
4. + 1.: Suppose T.. (G. H) = O. We construct block diagonal doubly stochastic matrix S' E Dn consisting of two blocks in D, and Dm respectively, such that |A(G') S'A(H') 0.
Assume (G, H) = 0. This implies that there exists S E Dn. s.t. ||A())S - SA(H) = 0 and Tr(ST H))
0.
We choose to order the vertices being ordered by their colors vertices in G and H. That is, a vertex u E V comes before vertex v (G) the stable coloring satisfies Coo (u) < Cv)(v.. Following the described ordering, and Theorem 3.5. 1. Grohe (2017), then symmetric, satisfying St,, 0 if, and only, vertices i, have the same color when the 1-WL algorithm acts on G and H, without considering initial labels. Moreover, Tr(ST L(G, H)) 0 implies that St > 0 = la(i) Lo( Therefore, if two vertices have the same stable color after 1-WL without considering initial labels, then these two vertices also have the same initial labels. This implies that the adjacency matrices of G', H' can be written as follows,
A(G)
B
A(G")
BT D
A(H)
B
A(H') =
BT
D
26

---

Covered Forests
where B Raxm such that
1, E (2. and 1- 1 ((Ca()))
Biy 0, otherwise,
and D Rm a block diagonal symmetric matrix of attached cliques. We now define S' to
S
0 S
s'
0
where S is defined as follows,
K1,1
K1.1
K
K2
K2
K
5
Kn,1
Kn,
Knn
where Kij (R(( is
0
Ki,
0
is then easy to verify that, S is doubly stochastic and symmeerrc matrix satisfying ŠBT = BTS which by symmetry
implies B$ SB. Finally, it is easy to verify that DS = SD, by showing that DS is symmetric and using the symmetry of D and S. All together, this implies
A(G)S B
B$
[A(H))
SB
A(G')S'- =
= S'')
DS
SBT
SD
as desired.
This concludes the proof.
F. The Tree Mover's distance
The following introduces the Tree Mover's Distance (TMD), defined through the optimal transport problem. Following the notation from the original paper by Chuang Jegelka (2022), we introduce the optimal transport problem and the Wasserstein distance. We then define optimal transport problem between the sets of unrolled computation trees corresponding the vertices of two labeled graphs. Next, we define distance between labeled rooted trees and extend this definition to the space of labeled graphs, using the optimal transport problem and the unrolling trees of graphs' vertices.
The Optimal Transport We begin with brief introduction to Optimal Transport (OT) and the Wasserstein distance. Let X = {a; _ and Y = {yy 1 be two multisets of m elements each. Let C' E IR mm be the transportation cost for each pair, i.e., Cj = d(z,, ,j), where d is distance function between X and Y. The Wasserstein distance is defined through the following minimization problem,
(C.r) T(X,Y) = { E R pm
(X))) min YET(X.Y)
Yym = 1m 1m
where ( is defined the sum of the elements resulting from the entry-wise multiplication of two matrices with equal dimensions, and 1m denotes the all ones m-dimensional column vector. In the following, we use the unnormalized version of the Wasserstein distance,
OT OT^(X,Y) = min (C, = (X,)).
yEr(X,Y)
27

---

Covered Forests
Distance between rooted trees via hierarchical OT Let rT) denote rooted tree. We further let Ty be the multiset of subtrees of T consisting of subtrees rooted at the children of u. Determining whether two trees are similar requires iteratively examining whether the subtrees in each level are similar. By recursively computing the optimal transportation cost between their subtrees, we define the distance between two rooted trees (Ta, ra): (Tb, rb). However, the number of subtrees could be different for ra and rb. i.e., [T., * |- To compute the OT between sets with different sizes, we augment the smaller set with blank trees.
Definition 25, A blank tree To is a tree (graph) that contains a single vertex and no edge, where the vertex feature is the zero vector 0, E R2, and T denotes a multiset of n blank trees.
Definition 26. Given two multisets of trees Ta Tu. define p to be function that augments a pair of trees with blank trees as follows,
p: (Tv: Tw. + TT U (7u Ta (
We now recursively define a distance between rooted trees using the optimal transport problem. Definition 27. The distance between two trees rooted (Ta: Ta), (Tb, r6) is defined recursively as:
(Ta, ||arr,
Fr, + (L) OTTD., (p(Tr., Tr.)) if L otherwise,
||=rr- - Ira
where ||-I| is norm on the feature space, L max Depth(Tb)) and wi N + Rt is depth-dependent weighting function.
Extension to labeled graphs Below, we extend the above distance between rooted trees to the TMD on labeled graphs by calculating the optimal transportation cost between the graphs' unrolling trees.
Definition 28, Given two graphs G, H and I. >> O, the tree mover's distance between G and H is defined as
TMD H)) = (P(T& TH)),
where Th and TH are multisets of the de unrolling trees of graphs G and H, respectively.
G. Mean-Forest distance
Normalized Tree Mover's distance We can scale the vertex features of the forests to extend the definition of the Forest distance the normalized TMD; see Chuang & Jegelka (2022). This distance satisfies the Lipschitz property of mean aggregation MPNNs, shown in Chuang & Jegelka (2022, Appendix B.). However, this distance is strictly more expressive than the mean-1-WL algorithm, meaning that there are graphs that are not distinguished by the 1-MWL but have a positive normalized TMD. To see this, consider the distance between two star graphs, one with root labeled 1 and two neighbors labeled 1 and 2, and the other with a root labeled 1 and four neighbors, two of which are labeled 1 and the other two with 2. is clear that the 1-MWL cannot distinguish these two simple graphs. However, the normalized TMD between these graphs positive because the number of vertices at the first level differs. This motivates us to define the mean-Foree distance through the mean unrollings defined in Section 1.1.
Mcan-Forest distance aggregation MPNN models and preserving the expressivity of the 1-MWL. That is, for a given attributed n-order graph (G, fa) with labels in IR. xx and a fixed L E N, consider the following multiset of mean-unrolling trees.
Here, we define the mean-Forest distance, providing a pseudo-metric aligned with the mean-
Thd = T (m-unr(G, u, L)) u E (
In analogy the use of the normalized Wasserstein distance to define the normalized TMD Chuang & Jegelka (2022), here scale all vertex features to align distance with the mean aggregation scheme described by Equation (5), thereby ensuring the Lipschitz property. For each vertex u in each tree, we divide its vertex feature by s(u), where su)) is defined inductively as follows. For the root r, s(r) = 1. For any other vertex u, with parent we define s(u) as the product of the number of children of u and s(v). Next, we perform a padding process on all trees in T6 as follows. For each vertex of each tree, we add children with the vertex feature o until each vertex has exactly n - children. We then construct the forest consisting of all n trees and denote this forest by F
28

---

Covered Forests
The wean--oorest distance between labeled graphs G and H. is defined as
FD, H) min
Σ
1era, (u) E (F(u)))l2
(EV(F
where the minimum is taken over all edge-preserving bijections between V(FE.L) and V(FB,)) Now, the following result shows that the mecan-Forest distance is valid pscudo-metric.
Lemma 29, The mean- Forest distance FDE is well-defined pseudo-metric on I for E N. Additionally, for two graphs G, H, FDT, (G, H) = -0 if. and only, if G, H are 1-MWL indistinguishable after L iterations.
H. Properties of the Forest distance and the mean-Forest distance
Here, prove the main results regarding the Forest distance and Fora- distance defined in Section 2. We start by showing the equívalence between the Forest distance and the Tree Mover's distance, as stated in Lemma 3. Next, we establish that the mean-Forest distance is well-defined pseudo-metric on the set of graphs and has equivalent expressivity to Lipschitz-continuiig continuity property of sum and mean aggregation MPNNs concerning the Forest distance and Beean-Foeest distance, respectively. i.c., Lemma 14 and Lemma 48, Finally, we derive an upper bound for the covering number of graph class In.d.g regarding the Forest distance, as stated Proposition 16.
1-MWL: see Lemma 29. We then show the Lipschitz
We begin by showing the equivalence between the Forest distance and the TMD. Specifically, we prove Lemma using recursive formula for the Forest distance for the simple where the weight = 1. The proof for general weight function remains the same. To proceed, we will introduce some further notations. Recall the definition of the Forest distance, for E N and graphs G, H E Gh the Forest distance
FD H) min Σ
[[((()) - (n(s(()))
wEV(PG.L)
where FG,z denotes the forest consisting of all padded trees in Téé and the minimum is taken all edge-preserving bijections between (FFG, and V (FH,).) We denote the set of forests consisting of depth-L complete trees (i.e., non-leaf vertex has exactly
children), with vertex labels from Rd by FL. For two forests F1, F2 E FL. we define iso [1, F2) as the set of edge-preserving bijections between V(F1) and (. If F1 and F2 contain a different number of trees, we pad the smaller forest with depth-L. complete trees with o vertex labels. The forest transport function FTL between two forests in Fr, then defined as
FF) =
min (E)
Σ
[
x (Fz) ((())
(EV(FF)
where zu (F) E IBixd represents the label of vertex a in Pj for j E (1,2). Observing this, we immediately find that FDz(G, FTr FT FH.L).
Now, for rooted tree T with root let T, denote the multiset containing all subtrees rooted at the children of r in T. and let F, represent the forest of padded (with o labeled vertices) subtrees rooted at r's children. Additionally, given forest F composed of rooted trees, denote by roots(F) F") the set of roots of the trees in F. The following lemma provides a recursive formula for the Forest distance.
Lemma 30. For forests F2 FL.
(F,,FI,F)
min
(Ix(/)) (P3)) + FFT-1(Fr,Fo())
a: roots(Fi (Fo)ss) (Er) bijection
Proof. We prove the lemma by substituting the definition of F'TL-1(FF Fa(r)) into the recursive formula. By definition of the forest transport function, we have,
FT FT Fo(r))=
min (Eiso(FF..Fco))
(Fz) p(u) 12
(EV(FF)
29

---

Covered Forests
Substituting this into the recursive formula yields that
Σ
(1
(F))
la + FFFF FT--II (atn))))))))
min roots (i) ())-tooss(FF))
d(())
bijection
rEroots(F) Fi)
equal to
Σ
||x|
(P%)
min
2o(r)
a: roots( (-roots(Pp) bijection
(Eroots(FF)
min (e
[xx(ft)
(Foco) p(u)
12
(EEV(Fr,))
which is equal to
min
min (Erroos((P)) (E(so(F...ett)))
Σ
[1a(
(Fa) Tr(()
x
(F2)
Σ
x
(Fa(r)) pp(()))
roots( Pi 1 rrootss P2)
bijection
aEV(F.)
which turn is equal to (Fi, F2). Here, the last equality follows from the fact that computing bijection between the roots of the trees in two forests and then computing edge-preserving bijections between the subtrees of these roots equivalent to directly computing adge-preseering bijections between the two forests.
Next, using Lemma 30, show the equivalence of Forest distance and TMD.
Lemma 31 (Lemma (for = in the main paper). The Forest distance is equivalent the TMD when 1. That is, for graphs G, H. E G.
TMD H. = FD,(GGH)
Proof. We prove by induction on L that Ti and To are multisets of n depth-L. trees, and Fj and F2 are the padded forests induced by Ti and T2, respectively, then
OTT T2)) (F,,
where ОT, TD, and P denote the optimal transport problem, Tree distance, and padding function, respectively, as defined in Appendix F. Setting Ti = T and Tz T implies the equivalency between the two distances. For L = 0, consider
multisets Tı, Tz of trivial "trees," " i.e., isolated vertices. By the optimal transport problem definition, we assume
Ti = To = [ni], we have
OTTD(P(TT: T2)) min
Σ NETI,
S (2)
ar("))l l|2
SED.
which is minimization problem with convex feasible set and linear objective function. Therefore, the minimum attained on an extreme point. The Birkhoff-von Neumann theorem shows that the extreme points for doubly stochastic matrices are the permutation matrices. Since to isL(FG.L, PH.L) is equivalent to choosing permutation matrix, we conclude that,
OTT(((Ti,TT)) = min PEP.
Σ
Pu,vll=( 20(21112 = FTo(FI, F2).
For the inductive hypothesis, assume that
OTTD(P(TI T2)) (F,
for multisets Tı, To of (L 1) depth trees and their corresponding forests F1, Fg. Now, let us consider two multisets of T--dpphh trees, Ti and Tz, with associated forests F, and Fz. With slight abuse of notation, we introduce canonical ordering
30

---

Covered Forests
for the elements in the multisets 7I and T2 such that each / Ti be used interchangeably or index for the entries of the permutation matrix. Additionally, for each rooted tree & 'T, denote the root by ra. We compute the optimal transport O'TT(p(TT T2)) using the definition from Appendix F as follows,
OTTT(A(TI,7)) = min PEP,
Σ 1ETi,'ET2
Pee TD((,
Σ TETI,NETa
Pae (1ae! - -x// oTTDll(Te Tr.)))
min PEP.
Σ TETiNTE2
Pee (la!! - -x afff112 FFTE- Fre))
min PEPa
(F,,
where the last two equalities follow from the inductive hypothesis and from Lemma 30, respectively.
The following results relate the mean Forest distances to the 1-MWL in distinguishing non non-isomorphic graphs.
Lemma 32 (Lemma 29 in Appendix G). For I E N, the mean-Forest distance FD. (m)) is well-defined pseudo-metric on GR.a- Additionally, FD[ (m) (G, H) = 0 if. and only, if G, H are 1-MWL indistinguishalee after L iterations.
Proof. We recall the definition of the mean-Forest distance between two graphs G, H &n.d which can be written as
FG, H)
min PEP A A(P PA
(Tr(PTL(G,
where (G (n 1) 1)1 1.
|| (B)
12, and np is the total number of vertices in the forest after the padding process i.e.
is easy to verify that FD. (G, G) and FD(T (G, FH, G) for all G, H E G2 Now, for the triangle inequality, consider GA, GB. Ge E G and P', P" as the permutation matrices arising from the minimization formula of (m) (GB, Gc), respectively. Note that p' p'p" is permutation matrix satisfying
FD( (GA, GB) and (D(
A ( P'P" A(F
(m)
(m) L.
implying that
FD(T"(G (G Gc) T((P'P"')
Following the same derivations as in Proposition 23, show that
TI((P'P") Go)) TT((P') +
which proves the triangle inequality.
The additional property: FD)(T)) (G, (1) 0 if, and only if, Gnd are 1-MWL indistinguishable after L iterations, follows directly from the unrolling characterization of 1-MWL described in Proposition 18.
Computational complexity Throughout the paper, we discuss two main distances: the tree distance (with either the cut norm or the -²-norm) and the forest distance. As shown in Lemma 3, the forest distance is equivalent to the Tree Mover's Distance (TMD) introduced by Chuang & Jegelka (2022). This equivalence allows for efficient computation via dynamic programming (as described in the original paper), with a time complexity of O(t(n) + Lnt(g)), where q is the maximum degree of a node (in both graphs), n the number of nodes, and ((m) (m log(m)).
31

---

Covered Forests
The tree distance with the ---n can be computed in polynomial time (specifically, e-approximation) as detailed in (Nesterov & Nemirovskii, 1994, Section 6.3.3). In contrast, computing the tree distance with the norm involves significantly harder combinatorial optimization problem. One of the most well-known approximation techniques for this case is described in (Alon & Naor, 2004). Additional relevant works include Alon et al. (2002); Frieze & Kannan (1999). It is worth mentioning that for the theoretical results in our paper, either the tree distance with the cut norm or with the 2-norm can be used interchangeably. as they define the same topology as discussed in (Böker et al., 2023).
I. Extended robustness framework
Kawaguchi al. (2022) improved the generalization bound in Theorem by establishing data-dependent bound that reduces the dependency on K from VK to log (K), as shown in the following theorem.
Theorem 33 (Theorem 3 in Kawaguchi et al. (2022)). For any (K, (KK,))-robbl ---oobustt (graph) learning algorithm for H on Z, with ((S), we have that for all (0.1), with probability at least for sample S drawn from Z according partition [Ck]==1]
μe, it holds that
(hs) S (emp(hs) + c(() + ((hs) ((2
Ts log(2K/6)
2| log (2K
[8]
[
where x = li E [|S|]] (zi, E C.J. ((hs) (z (f (((ss(x),)) and Ts - {k E [K]
21.
Here, we introduce an extended definition of robustness that allows us to choose different radii for the various partition sets. This modification makes the first term of the generalization bounds in Theorem 4 data-dependent.
Definition 34. A (graph) learning algorithm for H is (K, e)-robust, with K, E = (g) mapping from the set of all possible samples to N and (0, oo) (((), respectively, if Z can be partitioned into ((S) sets, {C.) K(S) such that for all samples S, and for any (G, y) E S, the following holds. If (G. y) E C. for some i E {I....,K' K} then for all (G,,)") E C.. we have
(((hs(G),)) v) - E (G') < (S),
where hs is the graph embedding the learning algorithm returns concerning the data sample S.
Building on our refined definition of robustness, we derive the following generalization bound. The proof is nearly identical to that of Theorem 3 in Xu & Mannor (2012); however, for completeness, we provide the proof in Appendix J. Theorem 35. For any (K, e--oousst (graph) learning algorithm for HH on Z, we have that for all ö E (0,1), with probability at least 5,
[SES||ECH S)
2K log(2) + 2 llog(1//)
(esp(hs) Lemp (hs)
(.(S) M
S
where his as before, denotes a graph embedding from H returned by the learning algorithm given the data sample S of Z. We recall that M is the bound on the loss function f.
Based on Theorem 35 and the proof technique outlined in Theorem 10, we present the following generalization bound for the class of unlabeled graphs consisting of at most n vertices (i.e., Ggn)
Proposition 36. For n, L E N,M M' E for any graph learning algorithm for the class MPNN Lenn (G5n) and for any sample and 5 (0,1), with probability at least 1 8, we have
IsE x 3/1
8k
4m / + log(2) + 2 (1/)
(hs) (em)((s)) S LE LFNN
V
M
|S|
12
S
for k E N, where M is an upper bound on the loss function E, and miga == |5en/ /Bsn/~mll
J. Missing proofs from Section 3
The following results extends the robustness based generalization bounds utilizing the generalized robustness property.
32

---

Covered Forests
Theorem 37 (Theorem 35 in Appendix 1). we have (K, e)-robust (graph) learning algorithm for H 2, then for all ō E (0,1), with probability at least 5, for sample S drawn from 2 according μs, it holds that
K(8)
KsES|sECal SS|
2K(S) log(2) + 2 log(1/))
(exp - lemp (hs))
((()) + MV
S
where his as before, denotes a graph embedding from H returned by the learning algorithm given the data sample S of 2. We recall that M is the bound on the loss function E.
Proof. N, = {s S s C.). Note that ((Ni),..... [N is an i.d multinomial random variable with parameters [S] and (n( by the Hetngnolle-Huber-CCee inequality (see Proposition A.6 of van der Vaart et al. (1996)),
where μ is the unknown distribution on 2 from which our sample is drawn. The following holds
K
N. S
s 2K exp (
nd² (-2
Pr
Σ
m(Ci) 2
Thus, with probability at least 6, we have:
[
2K log 2 (1(8))
p(Ci)) S
S
SS|
The discrepancy between the expected and empirical losses can be bounded as follows:
(exp(hs) lemp(hs)
K
E
Σ
()
|8]
#ES
Nr [S]
B(e(hs; 2 E;)
((hs 8)
|S]
#ES
K
K
N₂
B(E(hs, =)1; (c))((a))
B(e(hs, 2))= Ci)
[
max (((hs,)) SEC,
E(hs; 22)1
max (chs,
Σ
((C))
:E2
S
sEN.
K
{s |
2K log(2)
+ 2 log(1/6)
(S) + M
S
[S]
where the first inequality is due to triangle inequality, the second by definition of N₁, the third by definition of the generalized robustness property and the bound M.
The following result links continuity and robustness.
Proposition 38 (Proposition 5 in the main paper). Let (G, dg), (X, dx), and (Y,dy) be pseudo-metric spacees and let H. denote the class of uniformly continuous graph embeddings from (g, d,)g) (X,dx), Ift: X x y - RR.t is a et- -ipschiii continuous loss function, regarding doe, then for any 0, graph learning algorithm for H on y
(N(g. dg. 7/2) NN dy,
dy,e/2),,)))) e/2), cxe))
Where h) be the positive function used in definition of the uniform continuity of h E H
Proof. Let KK be a partition corresponding to 7(,, /2//// of G. and let {Y,) ing to an e/2-cover of y. Then we have Ki N Te, h2) and K₂ = ~N(2,, dy, E/2). Letting K == K₁ K2, we
1-ر be partition of y correspond-
33

---

Covered Forests
define the partition Drg C y,, for i [Kg] and j [K2] of g x V We now verify that this partition satisfies the robustmess conditions.
To this end, consider sample v) E S from G and assume (G, v) E Di.j. along with another element (G', E Dis-
We need to show that
[((hs(G),)) - ((ss(G") v0 S ege.
Since G and G' both belong to Ct,, we have dg(G, G') S (E, hs) and this implies that dx (hs(G), (hs()))ss(())) S c. Similarly, since y and y' both belong to Yj. we have dy(u.v') S e. Thus, using the fact that the loss function é is ce-Lipschitz continuous, we obtain
[((hs(G),)) ( s c max dxx (hs(()),ss(G)) dy(u.
S cr max {} = cce,
as desired.
J.1. Robustness and expressiveness
To apply Theorem 4 in our analysis, we must choose our pseudo-metric dg, the class of graph embeddings H. and the loss function so that the Lipschitzness of the graph embeddings and the loss function guarantee robustness; see Corollary 6. Since we are primarily interested in the generalization abilities of MPNN architectures, the chosen pseudo-metric should be aligned with the MPNN outputs to satisfy a Lipschitz property. A minimal requirement is that whenever the distance between two graphs through the chosen pseudo-metric is zero, the MPNN outputs should be identical. We derive the following result by combining this observation with the results from Morris et al. (2019) regarding the equivalence of MPNNs and the 1-WL algorithm.
Observation 2. Let (G, dg) be a set of graph G paired with a pseudo dg and H. be the hypothesis class of all possible MPNNs. Then, if h is Ch.-Lipschitz for all h E H. we have that the pseudo-metric dg is at least as expressive as the 1- WL ie., for all G1, G2 E 9 with dg(Gi, G2) = 0, we have that G1, G2 are 1-WL indistinguishable.
The observation shows some minimal expressivity requirements for the yseudo-metric must be met to satisfy the Lipschitz property MPNNs. Thus, for the rest of this work, we focus on pscudo-metrics that are at least as expressive as the 1-WL or its variants such that the 1-MWL.
K. Graphon analysis
In the following section, we define graphons. the extension of graphs to graphs with infinitely many (and uncountable) vertices. Formally, the space of graphons is the completion of the space of graphs to compact space concerning the cut-distance; see Frieze& & Kannan (1999) and Lovász (2012, Theorem 9.23), Next, we extend the tree distance to the space of graphons such that the graphon tree distance between two induced graphons is precisely the tree distance between the original graphs. We further introduce the Prokhorov pseudo-metric 8p on the space of graphons as defined in (Böker et al., 2023). We proceed by describing a message- paagggg-painnggggg mechanism on the space of graphons such that applying this mechanism to graphon induced by a graph equivalent to using the MPNN defined Equation (1) to the original graph. Finally, we present Theorems 29 and 31 from Böker et al. (2023), showing the equicontinuity of MPNNs on graphons concerning the Prokhorov pseudo-metric and the uniform continuity of the Prokhorov pseudo-metric concerning the graphon tree distance, respectively. Combining these two results, we establish the equicontinuity of MPNNs concerning the tree distance, as stated in Theorem 8 of the main paper.
Graphons We begin with the definition of a graphon, which is just a symmetric measurable function W: [0,1]² + [0,1]. We denote the set of all graphons by W. Graphons generalize graphs in the following sense. Every n-order graph G can be viewed as a graphon We by partitioning [0.1] into n intervals (I,) ([))))(()) each of mass 1/n, and letting WG(a;, y) for E Iu.3 y E I, be one if {u, u) E E(G) and zero otherwise. We call We the induced graphon by graph G.
Graphon tree distance A graphon W defines operator Tw: ('((0))) + (²0,)) on the space L²((0))) of square- integrable functions modulo equality almost everywhere as
(z) = 1/1 W(z, v) dX(y), x [0.1, f e =L'((.1))
34

---

Covered Forests
Following Böker (2021) define the graphon distance of two graphons U and W as
(U, W) inf sup (f.. (Ty o o Tw))g) )
S f.g
where the supremum is taken over all measurable functions f.g [0.1] + [o,1] and the infimum is taken over all Markov operators S. ie.. operators S [[(, - [[o,1] such that S(f) 2 for every f 2 0, ((L = 1o. and (1)o)) [ also for the Hilbert adjoint S*. Markov operators are the mnfnite-dimensional analog doubly stochastic
matrices (Eisner al., 2015).
The following result by Böker (2021) shows that the graphon tree distance specializes to the tree distance defined graphs when applied to the corresponding induced graphons.
Lemma 39 (Bökerr 2021, Lemma 15)). Let G, H for some E N. Then,
(G, = -0WG,
Prokhorov pseudo-metric on graphons Without delving into technical details, we denote the Prokhorov pseudo-metric on W as óp. The formal definition can found in Böker et al. (2023). Intuitively, the Prokhorov pseudo-metra is a pseudo-metric on the space of graphons and is based on the Prokhorov distance between the color histograms produced by a continuous counterpart of the 1-WL algorithm applied graphons.
Message passing graph neural networks on graphons For graphon W W, an L-layer MPNN initializes feature (0) = Go E Iedo for x E [0,1]. Then, for t E [L], we compute h [0,1] + IR4 and the single graphon-level feature hw 1 after layers by
()) (Jo ((x,
axii) and hw = vb t6 (1 (1) dx(x)
h ( Pe
(14)
Where, (4) 1. ab are the functions of Equation (1). This definition generalizes Equation (1) on graphons. More precisely, we have the following result.
Lemma 40 (Böökrr et al., 2023, Theorem 9)). Let E Gn. some n E N, let (uffa)) be an L-layer MPNN model, and +i be Lipschitz. Then,
hg
hwa.
We are ready to present Theorems 29 and 31 from (Böker et al., 2023), presenting the uniform continuity of MPNNs on graphons for the Prokhorov pseudo-metric and the uniform continuity of the Prokhorov mseudo-metric for the graphon tree distance, respectively.
Theorem 41 ((Böker et al., 2023, Theorem 29)). For all L E E, E and W, if (U, W) < 8, then || hw S for every L' L'-layer MPNN model given by Equation (14) with L S L'. O Theorem 42 (Böker et al., 2023, Theorem 31)). For every >> 0, there exists a 82 0 such that, for all graphons U and W, if (U, W) < 82, then (U, W) S.
O, there exists a 8 > 0 such that, for all graphons U
We now combine the above two results to show the equicontinuity of MPNNord main paper.
L.M', Levn (Gn), stated in Theorem in the
Theorem 43 (Theorem 8 in the main paper). For all > O and N, there exists 7 > 0 such that for n N, M' e R. G, H Gn. and all MPNN architectures in MPNNodd L.M', (9n), ) the following implication holds,
(G, 11) < n² 7E) = lig h S.
Proof. Given E > 0, let (E) be as described in Theorem 41. Set this (1(E) as the e in Theorem 42 and compute (z) = 52 (e). Now, by setting 7(E) = 5z (z), we have that for all n E N and G, H E Gn. if & WH) S 7(E), or equivalently, by Lemma 39 if,
(G, H) < n² 7(),
35

---

Covered Forests
then ( WH) S (e)) Hence, by Theorem 41, |lewe hwalle ll2 S e, for all L-layer MPNN models given by Equation (14). Finally, by Lemma 40, the last inequality can equivalently be written
|io - h l|2 S e,
completing the proof.
L. Robustness and VC dimension bounds
Here, show how we can recover previously obtained bounds on the generalization abilities of MPNNs of Morris et al. (2023a) through the generalization framework of Section 3. That is, we show how the robustness framework of Section 3 allows us to recover the results in Morris et al. (2023a, Proposition 1 and 2) by fixing particular pseudo-metric on the set of n-order graphs. Unlike Morris et al. (2023a), our results not only hold for the binary classification setting using the 0-1 loss but, under mild assumptions, for arbitrary loss functions, such as the cross entropy loss and also standard loss functions for the regression case.
Analysis of generalization abilities of MPNNS of Morris et al. (2023a) To state the results of Morris al. (2023a), we first introduce the VC dimension of MPNNs. That is, for class of MPNNS MPNN(X') operating set of graphs X' e.g.. MPNN,, the VC dimension VC-dim (CCdii(MPNN((T)) is the maximal number of graphs Gi,..., G. in X' that can be shattered by MP'.(X).. Here, Gt...., Gm are shattered if for any T in {0,1)* there exists a MPNN mpnn E MPNN(22) such that for all i in [m],
Gpn = Ts.
By standard learning theoretic results, bounding the VC dimension of a class of functions directly implies a bound on the generalization error. 9
Theorem 44 (Vapnik & Chervonenkis (1964); Vapnik (1998, adapted to MPNNs)). Let be a set of graphs and let d oc. Then, for all 8 E (0,1), with
(P) be a class of MPNNs operating on X, with (CC-iimMMPNN)) probability least 8. the following holds for all mpnn E MMNNN(X).
(exp(mpnn) S kemp((ppn)) + / 2d 2og
(eN (eN
log (1/6) 2N
To bound the VC dimension of MPNNs, Morris al. (2023a) consider X' G the set of n-order graphs with d- dimensional Boolean vertex features and ) = {0.1). Like Morris et al. (2023a), for d > O, by Mn.d.L we denote the number of unique graphs in - distinguishable by 1-WL after L iterations. Now, Morris et al. (2023a) proved the following upper and lower bounds for the VC dimension of I-laaer MPNNs on the set G of graphs, showing that the VC dimension is bounded by the ability of the 1-WL to distinguish n-order graphs.
Proposition 45 (Moriis et al. (2023a, Proposition 1)). For all n, d and L E N, it holds that
VC-dim MPNNN, (GR,a) S Mnnd,L
This upper bound holds regardless of the choice of aggregation, update, and readout functions used in the MPNN architecture. They also show a matching lower bound.
Proposition 46 (Moriis et al. (2023a, Proposition 2)). For all n, d, and L E N, all mn,d,L 1- WL-distinguishable n-order graphs with d-dimensional boolean features can be shattered by sufficiently wide L-layer MPNNs. Hence,
VC-dim MPNN (
(Gh.))
-.,d.LL
Hence, combining the above result with Theorem 44 implics that for all samples S, with probability at least 8,
(osp(hs) S (omp(ss) + 2m. log (e S 1//m...L..
log (2/5)
S
2|S]
FFor of exposition, compared to Morris al. (2023a), use a slightly different definition of MPNNs' VC dimension. However, the proofs of Propositions and 2 also work the case of the above definition.
36

---

Covered Forests
Note that the logarithm must be positive for the above bound to be meaningful. This requires the assumption that the sample size is significantly larger than the total number of 1--L-distinguishable graphs, which is generally not feasible, especially for large graphs. We now largely recover the above generalization bound without any assumptions the sample size through the theory outlined in Section 3 and extend it to the case of regression.
Recovering Morris et al. (2023a) via the robustness framework Let us consider the binary classification setting with V/ = { and the 0-1 loss function E: y x y + {0,1}, where E(y), 3/2) = if, and only if, 3/1 = 1/2. Given that the expressive power of any MPNN with L layers bounded by 1-WL after L iterations (Morris et al., 2019), it is straightforward to verify that any graph learning algorithm for MPNN (Ph,a) on Z = g y is (2mm, -rrbuus,, leading to the following generalization bound. For d (0.1) and for all samples S, with probability at least 1 6, we have
4mn.d. 22 + +2 1og((16)
Reep (hs) - lmpp (hs)l S
S
To see this, observe that we can construct partition of 2 using the sets C = G (0), for G E au/~ma: J E {0,1).
Regression setting In contrast to Morris et al. (2023a), the robustness framework is flexible enough to accommodate different loss functions straightforwardly. For example, consider the set of graphs G we now extend to the regression setting where y = (0,1), with the loss function f: y x y - (0,1), defined by E(g). y22 = y U2|- We then define the pseudo-metric WL1, on Ihd as follows,
1, if 1-WL distinguishes G and H after L iterations, (L, =
0, otherwise.
We further consider the metric| |. | on (0,1) as the absolute difference metric. Observing that: (1) the covering number (((O))), 1,e) < 2/c, for e < 1, (2) the covering number VV I, WL1,L. c) = Mn,d,L, for E < 1, (3) the loss function E(x, v) = | - y/ is 2-Lipschitz, and (4) L-layer MPNNs are 1-Lipschitz with respect to the WL1.7 pseudo-metric, we can apply Corollary 6 to obtain the following bound. For E (0.1). for all samples S, with probability at least 1 - and for 1, we have
2/c dn log(2) + 2 llg(t//)
(exp(hs)) Lemp S 4e +
[S]
M. Fine-grained analysis of MPNNS with other aggregation functions
In this section, we extend the previous results analyzing MPNN layers using mean aggregation according to Equation (5). Let L denote the number of equivalence classes induced by the 1-MWL after L iterations on Gn,d.q- For the case when L = n - 1, we simply write mn.d.q. To establish generalization bounds, we rely on the mean-Forest distance FD"" defined in Section 2. Similar to the Forest distance, we can bound the mean-Food Forest distance between two graphs that differ by either a single edge or vertex label change, as shown the following lemma, the proof proceeds identically to the proof of Lemma 13.
Lemma 47. For d, L E N, there exists a constant ((m) q, L) such that for n E N and G, E Gn,d.g if G can be obtained from H by either deleting an edge or by replacing vertex feature with a new one, then
FD( (G, H) S b(mm) (d, q, L).
We next analyze the generalization power of the MPNN class MPNN menn T.M Leway (Gn, (n)w.g). Again, we consider the loss function É: R {0,1) R. defined by f(x, v) y log(a(=)) + (1 y) log (z)), where (xx) is the sigmoid function. The following result shows the Lipschitz continuity property of MPNNs in MPNNE E,,d" .em (G),..g) concerning the mean-Forest distance. Similarly to sum aggregation MPNNs, we state and prove the Lipschitz property below for the more general setting with graphs in Gh.
Lemma 48. For every L,n, d E N, e R and all MPNNs in MPNN L.M', LLonn (G we have
L. L., FD, H), for all G. H E Gh
1 Lg II lha - hu 12 <
37

---

Covered Forests
where (( (L) is constant depending on L.
We now state the generalization bound for mean aggregation MPNNs.
Proposition 49. For 0 and n, q, d, L M' I and any graph learning algorithm for MPNN mucan
L.M' Leao (9n,d.g) is
(2N(9m, FDL
(m)) .E), Le LFNN CrDE 25) -robust.
Hence, for any sample S and (0,1), with probability at least 5.
2N 2N(9n.u.g FD( ,e)2 2 2log(1/)) for e > O,
(exp(hs)) - (emp(hs) S ((m)) + MV
S]
where ((m) 2/1 FD(() ODD( ((m) I Emly, the Lipschitz constant by Lemma 48, and M, is an upper bound of the loss function l.
We similarly bound the covering number concerning the mean-Forest distance, deriving the following bound.
Proposition 50. For n. 9, d, L N, and M' R. for any graph learning algorithm for the class MPNN I.M L.ew (ew (9n.d.)) for any sample S and E (0,1), with probability at least
have
mn a.a. (og + 2 2lg((1/) k+1
(exp(hs) Cemp (hs) < ( (d. 9, L)k + MV
for l E N,
S
N. Covering number dependency on graphs' -order
In previous sections, we showed that for different choices of e, the covering number can be bounded by a function that always increases scales on as ma, i.e., the number of L-WL-indistinguishabll classes. Specifically, when estimating the limit
lim
71-000
m70
the result will always be a constant that depends on e. While one could use Equation (10) with radius 4n to obtain a bound that scales as m,/(0 1) in n, such an increase in radius would impact the first term in the generalization bound. Hence, the question arises of whether it is possible to derive bound that grows more slowly with than m, for some sufficiently interesting graph class, using either constant radius radius that depends only mildly on
More formally, a natural question is whether we can establish tighter bounds for the covering number for given constant that does not depend, or mildly depends, on n. For instance, is there a choice of > and a graph class F, such that
|m//me bn
N(Fn,, 65,5) S
(15)
where bn + 20 as n grows? If such a graph class exists, then MPNNs could effectively handle the growth in graph size without significantly impacting their generalization performance. Below, we present a class of graphs Fn that satisfies Equation (15) for radius e = 4.
We define the class Fn as follows, let Pa denote path on vertices, with vertex set V(P.) (v . Sn and edge set (un-1, E(p,) { {e1, ", }. We denote by P(n) the set consisting of disjoint unions of paths on vertices. Then, we define the graph class
Jr = ((V,)) V = V(P.) E == -(P)UE(()()) for Pe P(n),
We VPP), and v E V(P.).
We will now show that for the graph class Fr and e = 4, Equation (15) holds. Proposition 51. For the the graph class Fn C On constructed above. we have
N(F, ().4) < 2 /
38

---

Covered Forests
Note that in the above proposition, established that the covering number is bounded by (P(n), which has interesting combinatorial interpretation. Specifically, [P(n)] represents the integer partition of n, i.e., the number of distinct ways express sum of positive integers. While there is no known closed formula for the integer partition, it can be accurately approximated through asymptotic expansions and computed precisely via recurrence relations, making the bound efficiently computable (Andrews & Friksson, 2004).
Regression setting Here, we lift the results from the previous section to the regression setting. Specifically, we use consider the loss function E(x, y) = [ - yl, resulting the following results.
Proposition 52. For every L,n E N, M' R and for all MPNNs in MPNN L,M', Levm (9n), we have the following generalization bound. For any sample S, and any ô (0,1), with probability least for 2M',
N(9n 04 e) 1M log(2) (og((/))
23 n
(eep (hs) (hs)) S 2. LFNN 5-
M
S
O. Missing proofs from section Section 4
The following result links robustness with the generalization error of order-normalized MPNNs.
Proposition 53 (Proposition the main paper). For > 1/2 inf
(G H), n, L E N, and M' E R, any graph (G
learning algorithm for the class MPNNor L,M" Levn (9n) is
(2N(Gm. E).), Le LFNN 7
2s n²
-robust.
Hence, for any sample S and E (0,1), with probability at least 1 - 5.
(25 + M
4N 87, log(2) (
(hs) (hs)) S Le LFNN 7
122
[
where, M is an upper bound for the loss function and Lg the Lipschitz constant of v). E {0,1).
Proof. We first note that since FNN bounded by M', we know that the loss function is also bounded from some M E R. Now, let = Gn {0.1). For given > 0, graphs G1, G2 Gn. and yı, y/2 E {0,1), (G,, G2), 8()),8)) < ?())n?, where 5 is the Krolecker-delta metric on {0.1}. i..,
00,
y # 3/2 and
6(y1. U2)
if y1 y2.
we have that 8(y1, 12) < <>(E)n?, implies y11 1/2 and therefore, for any sample S, [((hs(Gi). v1) ((bs(G2)) = (((hs(G)), v1) - ((hs(G2),
I Lu (n(()si))))))))))))))r())) - hs hG()
S Le LFNN
Therefore, by Proposition 7, any learning algorithm for MPNNord L.M' Lonnn (Gn) is
(2N(g.. o. 7(5)n² ), Le LFNN $) rrobsst.
Now, we replace- E with 7- (25. By definition of -h, if (" (2z # O, we have 7(7* (2g
Thus,
n²
N(Gn, o6. 1(1" (z²) < <N(G,, e), leading the following generalization bound:
2c + M
4N e) log(2) + 2 log ! e)
(exp(hs) lemp(hs) S Le LFNN 7
S
39

---

Covered Forests
remains check the case where 7- (xt 0.
7 12 0, then 7(x)) 2 2: for all x > 0. Thus, for all graphs G1, G2, with (GG G2)
< n² n2, we have:
lIk.. hG2 la S x, for all O, h E MPNN |Ik. - hG, ll 0, for all h MPNN M.M, (9n),
L.M' Lrnn (9n)
which, following Böker et al. (2023), implies that (G) G2) = 0. Now, observe that since for all G1. G2 E In with (G1, G2) 2e, we have (G1, G2) 0. implying
E 2 G.HE9 (G,
inf (G,
which leads to contradiction, since we have assumed e > 1 inf G.HEg, (G.H))
GG, H).
The following results provide a generalization bound using the number of graphs distinguished by 1-WL to derive an upper bound on the covering number.
Theorem 54 (Theorem 10 in the main paper). For n, L E M, E R. for any graph learning algorithm for MPNN L,M,, LLean (9n) and for any sample S and 8 E (0,1), with probability at least 8, we have
8k n
mn k+1
log(2) + log(
leep((ss - (omp((s)) S Te TENN 75
+ M
S
for k E N, where M an upper bound on the loss function
Proof. First, note that of (G, H) 0 and only, if the graphs G, H In are 1-WL-equivalent. By the triangle inequality, we also have that if G, H1 Gn. and G' [G], H' E [H] are two arbitrarily chosen graphs from their respective equivalence classes, then
IG H) o H²).
Thus, we can define the Tree distance between two equivalence classes as the Tree distance between two randomly chosen representatives. Moreover, computing the covering number on G, is equivalent to computing the covering number on the pseudo-metric space (9./~wm,, 2
We now construct a labeled directed tree with labels from 9./~m. level-wise, starting from the root (level 0), as follows.
1. The root corresponds to the complete graph on n vertices denoted as Kn, which unique in its equivalence class.
2. The first level consists of single vertex corresponding the graph derived by deleting an edge from the complete graph n vertices. Denote this graph K,,, which is also unique in its equivalence class.
3. In the next level, we compute all graphs obtained by deleting an edge from K,, Denote these graphs as GI..., Gr. for r E N. We then de-duplicate the set [G....., Gr) for the 1-WL, keeping one representative for each equivalence class. This reduces the set [G]]..... [.,), where r' < r. These equivalence classes form the children of the vertex at level 1.
4. For each vertex corresponding graph class [G.] in level 2, we compute its children follows. We first compute all graphs in the set.
[G.]e (G' 3 [G.], E(G) such that G {e} G
We connect these graphs to the vertex [G.]. We then prune the tree by arbitrarily dropping all 1 I-WL-equivalent graphs, keeping only one as the representative.
5. We continue this process until we reach the vertex corresponding to the empty graph.
40

---

Covered Forests
Observe that in the resulting tree, the total number of vertices is exactly Ma, since for each / E -(n=1) level I contains all
L-WL-equivalence classes for graphs with n vertices and m(n-1) edges. Additionally, the tree satisfies the following two properties:
1. Each parent is at most at a distance from its children.
2. All siblings are at most at a distance of from each other.
To verify this, consider the following. If [G1] is a child of [G], then there exists G1 E [G1], G E [G], and an edge E E(G) such that G {e} = G1. By the triangle inequality and the fact that
GG) 0,
since G and G' are I-WL-indistinguiihalle, we have
(GG = [[G)), (
Similarly, if [G1] and [Gy] are siblings, the triangle inequality gives
(GG)) (G2)) & ( (G.)) + (G). S
This follows from the fact that if the adjacency matrices of graphs differ in exactly two entries, then their Tree distance is bounded above by 2. Now, construct cover of ////m. follows.
1. We start from the leaves of the and merge each leaf with its parent. We repeat this step & times. The resulting graph is still tree.
2. In this induced tree, we create as many disjoint sets of 1-WL-equivalence classes as there are leaves in the induced tree by considering all classes corresponding to leaf as a set. Each group contains at least A + elements.
3. We then remove all leaves, creating a new tree T". For each leaf in T', we repeat the merging process as many times as necessary until each leaf contains at least + equivalence classes (requiring at most merges).
At the end of this process, each group will have at least + 1 elements, and the Tree distance between any two elements in same group will be at most 4k. To see this, note that for any two graph classes [G] and [H] in the same partition set, we consider the tree be undirected, there exists a path of length at most 2k in the initial tree connecting [G] and [H]. Thus,
can find graphs G [G] and H [H], differing by at most 2k edge additions deletions, implying that G and H are Tree distance most 4k: This implies that the covering number
N 63, 4k) < mn
k+1
The following result derives tighter bounds for Otter trees.
Proposition 55 (Proposition in the main paper). For L E N, M' E and sufficiently large n. E for any gruph learning
algorithm on MP L,M, Lran (T224 and for any sample S, with E (0,1), with probability at least 1 - 8, we have
16k
4tm 222 log (2) + 2 log (1/))
1eepp cemp (hs)l S Le LFNN 77'
V
(2n + 1)2
S
where & E N, M is an upper bound on the loss function E, b Rz 4832, and Wn. = T2
Proof. As in the proof of Theorem 10, we begin by constructing a rooted, labeled, directed tree. However, the labels are
now graphs from Ü T(2)
j=1 22/+1 and we do not need to use 1-WL equivalence classes, as 1-WL can distinguish any pair of
non-isomorphic trees.
1. The root (level () corresponds to the isolated vertex graph.

---

Covered Forests
X
X
(a) An illustration of tree construction described in the proof (b) An illustration of the grouping process applied the chosen of Theorem 10. On left. we show all possible trees that can be tree, which leads to desired upper bound for the covering number. computed according to the description in the proof, represented in a All vertices belong to a group with at least two elements (possibly directed acyclic graph (DAG) format. On the right, we display an excluding from the root). arbitrarily chosen tree from this set.
Figure 5. Illustrations related to tree construction and the grouping process.
2. The first level consists of single vertex corresponding to the 3-path graph.
3. At level [++ 1, we compute the children of vertices at level as the graphs obtained by connecting a leaf vertex of the graphs in level I with two additional vertices. We then prune the tree by removing isomorphic graphs.
4.
We continue this process until all binary trees the current level have + vertices.
The above construction shows that level I consists of all Otter trees with + vertices. Additionally, each child is at most
cover 2 using T balls of radius at Tree distance 4 from its parent and most 8 from its siblings. Therefore, balls of radius 8k. Using the asymptotic formula 8. Recursively, we can show that 2n+1 can be covered using T 21 from Lemma I,, we obtain
Wn - 2k
Wn.
(T 8k) S Wnn 2h
Wn
Wn
The following result derives tighter bounds for a specialized graph class constructed from paths.
Proposition 56 (Proposition 51 in the main paper). For the the graph class Fr C In constructed above, we have
N(F 83. 3.4) 2/Fm//wul
Proof. First note that since 1-WL is complete in the space of forests, /T./~ull is exactly the number of non-isomorphic graphs in F,. We prove that F, can be partitioned into [P(n)] subsets, each containing at least n/2 non-isomorphic graphs. Furthermore, within each partition set, all graphs are pairwise Tree distance of at most This result implies that while the total number of non-isomorphic graphs in Fr greater than IP(n)] n/2,, we can cover them using only (P(n)) sets.
Now, for each P P(n), define set Sp containing n/2 non-isomorphic graphs from F, such that for all P, P E P(n), we have Sp O Sp = 9. We construct Sp as follows. For each P E P(m), let Pmux denote the largest connected component of P. Choose, without loss of generality, vertex E ((Pmx) with degree 1, i.e., a non-interior vertex) and define
Sp = (V, V = (VPP))((PP) = E(P):((P)E())) U {u, v}, where vy for j E [1/2]]
42

---

Covered Forests
m
12
Figure 6. An illustration related to tree construction (left) and the grouping process for Otter trees (right) asymptotically leading to an exponential decrease the covering number with the radius.
Clearly, [Sp] n/2. We now verify the following claims.
1. For all G1, G2 Sp, G1 and G2 non-isomorphic.
2. For all P, P' E Spn)
Proof (1). Let G1, G2 E Sp with edge sets E(G,)= E(P))) 2, and B(G2)= E(P) {u, 1 where ji # j2 and J1. E [=]. Assume further that j1.12 * 1. If j1 < f2, then in G2, starting from vertex on, we can trace path of length j2 [E((Pm))] G₁, however, such path does not exist. If ji 1 + j2, evident that G1 has connected (Pmaa)). which is absent in G2.
component consisting of path of length
Proof (2). If P and P' have different numbers of disconnected components, then for all G1 Sp and G2 E Spi, G1 and G2 will differ in edge count. Furthermore, if P and P' have the same number of connected components but |Paax] * P then the size the largest connected component in G1 will differ from that in G2. Finally, P and have identical numbers of connected components and | = I then the connected component size histograms of G2 and G2 must differ; otherwise, P and p' would be isomorphic.
The following result establishes that MPNNs using sum aggregation are Lipschitz continuous regarding the Forest distance.
Lemma 57 (Lemma 14 in the main paper). For I,, n, d E N, M R and for all MPNNs in MPNN L,M Lewn (R have
L
lhc hall2 < C(L)L II L. FDr(G,H), for all G, H R where C(L) is a constant depending on
1=1
Proof. Let 8 be an dege--preeervng bijection between the padded forests FG,L and FH.L. This bijection induces another bijection, (()) between vertices at layer of trees FG.1 and vertices layer I of trees Fu.L. for each 1 (0...., L.). We
43

---

Covered Forests
0-0-
0.0000
80
0000
Figure 7. An example of graphs within the class Fu, for n=7.
further define (u, v) = 1 iff (1) = v and elsewhere. present the proof for the case = 2 and let W( w!( be identical matrices; for I, > 2 and any choice of matrices Wi1) w-(2)
(2) the proof is analogous, though the notation
becomes more complex. Specifically, one may generalize by replacing w(ll) and W: with Lipschitz continuous functions, and the proof would still hold. We show the Lipschitz property by recursively bounding the following difference:
|In hull
h (2)
Σ
h
WEV(G)
DEV(HI)
Ls
Σ
g vi) 1!!
w||l
h
(EV(G)
where in the last step, we applied the triangle inequality, as implied by the bijection (()) between the roots. Thus, we have that |ag h is less than
Σ
(u,
92
h
(1)
+
Σ
92
h
+
Σ
h
(EV
('EN(u)
v'EN(v)
Ly
Σ
g(0) (u,0) v)
(2) h
Σ
(
Σ
WEV(C)
w'EN(u)
*'E((O)
Lag. TipT
Σ
( (u,
(1) h
(EV(
Lu
Σ
g (u,
Σ
(u', n00
(EV w'
where, in the last step, we again applied the triangle inequality, this time induced by the bijection (()) between the vertices at the first layer. Note that is possible that [N))] > [N(]), meaning some neighbors of u are mapped by ((1) to padded vertices. In this case, Next, we bound term A:
trivially apply the triangle inequality by setting (1) 0 in the expression above.
5
L L Lip
Σ
g (u, v)
(())
(0) +
Σ
100
Σ
h
n
u (EV(G)
w'EN(w)
N'E((v)
1
L Tapp Tupi
Σ
0 (u, v)
(0) h
n
(EV
44

---

Covered Forests
Li Ly Aepslirr Lups
Σ WEV(C))
(1, v)
E
('' 1/)
1
16
''E((u),''E((o)
Similarly, the term B is bounded by
Las Lo Li
Σ (u, E (ul,"))
10 - h + Σ
Σ ""EN(o")
11
" (EV(C), ('EN(W),
"NEN(u')
1 Lobbippuup
E (u, E (u',
(0)
(EV(C), ('EN(W).'MM)))
1 + - Liphlegrip Lups 00) E (00 NEV(C),EV(M)) WEE(())."EEN))
E (12) o0" /
11
Therefore, choosing 0 the edge-preserving bijection minimizes Equation (9) we get,
|| hH |l s 2 L. FD, H).
71
The following result derives a bound on the generalization error for MPNNs using aggregation. Proposition 58 (Proposition 52 in the main paper). For every L, n. E N, M' E IR and all MPNNs in MPNN L.M'' LLwo (Gn)). we have the following generalization bound: For any sample S, and any E (0,1), with probability at least 1
(25 12
N (3,,),
4M' log(2) + log
(exp(hs)) - (emp((ss) S2 LFNN 77
+ M'
S
for < 2M'
Proof. Similarly to the classification setting we apply Proposition 7. First note that l 2-Lipschitz since,
[e(x1, v1) - ((22, 3/23 = || - y1l - |x2 -22l
|z| x2 + 1y y2l
max [|m1 221. ly y213-
Now, let 2 In x I-" M'). For a given 8 > 0, graphs G1, G2 E Gn. and yr.32 3/2 E [0,1], max (o G2), 11, < )E))??, we have that for any sample S,
[((hs(G:). v1) ((h))G2), 82)1 s 2 max (hs(( ho((G)))))) 181. 3213
2 LFNN
Therefore, by Proposition 7, any learning algorithm for MPNN2
L.M' Levn (9n) is
( ((1..).1111 7(m)m² . -v(( Gn. o5. 7(E)m²
2 LFNN -robust.
2
Similarly we replace s with 7" (23 and we get WV oT. * 1/3 ( S NN 5T. leading to the following
generalization bound: For any sample S, and any d (0,1), with probability at least 1 - ó, | (hs) - bemp is less than
22 M' n
N([ M, M7.1 1,e)) NN
67, (222))2loo2 + (og
2 LFNN 7
[S]
or,
25 -25 + M
NCG So, 03,5) 1M log(2) + 2 log
(hs)
5 2. LFNN 77
for & < 2M'.
45

---

Covered Forests
The following results upper bounds the covering number regarding the Forest distance using the number of 1-WL- distinguishable graphs after L iterations.
Proposition 59 (Proposition 16 in the main paper). For q, d, T. E N, and M' IR, for any graph learning algorithm for the class MPNNL,M L,M', (9n,d.a) and for any sample S and E (0,1), with probability at least 1 - ô, we have
me.d k+1
for E N, log 1/g((/5)
L)k MV (exp((s) - (hmp - 22Obld,
S
where C 2 CTD, Cg I Tup; is the Lipschitz constant in Lemma 14 and M is an upper bound of the loss function t.
Proof. It suffices to show that for all n, L,, d, E N, we have the following bound for the covering number.
Un.d.q.I.
dg FD,, 2b(d, L)k) <
k+1
Let / be the quotient space defined by 1-WL after iterations on In.d.gs i.e. Mn...g.L = (nndu//m. We denote
the equivalence classes in this space by [.] Following the proof in Theorem 10, it suffices construct rooted tree with labels from Sn,aa/~m, satisfying the following properties,
The total number of vertices is mn,d.g.L. and each vertex has unique label.
The graph corresponding to each parent vertex is most at Forest distance (depth L) b(d, q. L) from the graphs corresponding its children.
Graphs corresponding to sibling vertices are at most at Forest distance (depth L) 2b(d, q, L).
We construct such a tree as follows:
1. The root (at level = 0) corresponds to the empty graph on n vertices, where each vertex has the same feature. Without loss of generality, we assume this feature to be (1.0,....0) E lxd
2. At the next level (1 + 1), for vertex at level with label, say. [G,] we compute its children as follows. We first calculate all graphs in the set
[GoL, = [G.] U [G
where
G.IL (G' In,d,g 3 [ E(G') such that G' (c) G),
and
[Gil = fG's Gn,d.y 3G E [G||,, u E V(G), it V(G') such that
changing la(u) to lo (u') implies G 2 G
We connect all graphs in [G.]..c to the vertex [G Then, we prune the tree by arbitrarily removing all I-WL-equivalent (after L iterations) graphs, retaining only one as the representative.
3. We continue this process until all graph classes in Gndan/mm, have been used as labels.
The following result shows the Lipschitz continuity property of MPNNs using mean aggregation regarding the mean-Forest distance.
Lemma 60 (Lemma 48 in the main paper). For L, n, d E N' e R and for all MPNNs in MPNN L,,d'', ( we have
L II
(L)) T.p (D H), for all G, H E Gh.a
ha - hu s n
1=1
where ((m) (T.) a constant depending on
46

---

Covered Forests
Proof. Let 0 be an aade-preseervnng bijection between the padded forests F. and PlT) This bijection induces another bijection, ((0) between vertices at layer 1 of trees in F(m) and vertices at layer of trees in p(m) for I E {o,..., L.). and 0 elsewhere. We present the proof for the case L = 2 with (2) as identical matrices; for L > 2 and any choice of matrices wi",, w the proof is analogous, though the notation becomes more complex. Specifically,
Similarly, we define (u, 1 iff (u)
W( (
may generalize by replacing w and w( with Lipschitz continuous
and positive homogeneous functions, and the proof would still hold. For each u E V(G), we denote by Nu, the number of neighbors of u (i.e., N₂ = [u)). Then.
|| - hall
1
Σ
(22)
1
(2) DEV(H)
h
n
a
(EV(G)
g (u. (2)
/
S L
(EV(G))
where we have just applied the triangle inequality, as implied by the bijection ((0) between the roots. Thus, we have that |ha h is bounded by
)
1
L
Σ
g10) (u,
92
(1)
+
1
Σ
P2
h
1
Σ ('EN(u)
h
Nu.
No
(G
('EN(u)
Lagh Lp2
Σ
010) (u, v)
h - h
(1)
Σ
(1)
Σ
Nu
No
(EV(C),EVV())
a'EN(u)
"EN("))
S Tap Jupa
Σ
e (u, v)
(1) h
n1
ae WEV(C),EV(I))
h
+ Lo Laps
Σ " (EV(C),
7 (u,u) v)
Σ (EN("),EEN()))
7u) v')
Nu
N,
where, in the last step, we again applied the triangle inequality induced by the bijection ((1) between the vertices at the first layer. Note that it is possible that No, Nv, meaning some neighbors of are mapped by g(1) to padded vertices. In this case, we can trivially apply the triangle inequality by setting h!" = O in the expression above. Next, we bound term A, i.e.,
A < Log Lups Lups
1
Σ
( (u.v)
(0)
(0) + h
(0) h
1
Σ
O
Nu
N N'E((1)
u (C)
N'))
S n
1
Lag Tups Tups
Σ
g (u, v)
(0) (0))
u (GV
1 + Lo Lir
Σ
(10)
Σ
h
(0) N₂
h
(0)
n
No
WEN(W),''N(()
Similarly, we can bound the term B by
1 T
Tups
Σ
O (u, v)
Σ
n
(EV
d'EN(W).
47

---

Covered Forests
( h Nu
[1
0
91 (v',
v')
Σ
h
Σ
Nu
No
No
n"EN(")
v"EN(r)
where we have used the positive homogeneity property of (p: Therefore,
1
h (0)
h
B S Lopipatip
Σ
B(0) (u,
Σ
0 (ul, (C0
1')
o'
Nu
No
weV NEV()))
(E((W),EEN())
+ - n1
1
Σ
g10) (u,
E
(u',''
(EV(C),EV((H)
WEN(W),
h o"'
h 4" No
E
@l2) (u","")
N.
Hence, choosing as 0 the edge preserving bijection minimizes Appendix we get,
l - hul /1 s La Lup FD,
as desired.
P. Experimental results
In the following section, describe the experiments in detail and report the results.
Datasets To investigate Q1, we conducted experiments using the graph classes Gn. Trl?), and (defined Appendix N). Additionally, we experimented with the binary classífication real-world datasets MUTAG, NCT1, MCF-7H (Morris et al., 2020a), and OGBG-MOLIE (Hu al., 2020), match our theoretical setup and address Q1, Q2, and Q3. For real-world datasets analyzed under Q1, we computed the covering number across all graphs up a specified order, with smaller graphs being padded with isolated vertices, aligning their order. Similarly, for Q3, graphs were padded to match the order of the largest graph in the dataset; see Table 2 for dataset statistics and properties.
Neural architectures To address Q2, we used randomly initialized GIN architectures (Feng et al., 2022) with varying numbers of layers and matching parameters for the Forest distance. Conversely, for Q3, we trained GIN architecture with three layers across five random seeds to estimate variance, Both architectures incorporated ReLU activation functions and sum pooling, disregarding potential edge labels. We tuned the feature dimension across the set 32, 64, 128, 256 based on validation set performance, training MUTAG and NCI] for 100 epochs and MCF-7H and OGBG-MOLIN using the Adam optimizer (Kingma & Ba, 2015). The training setup included a learning rate of 0.001, batch size of 1 128, and no learning rate decay or dropout across all datasets. All models were implemented with PyTorch Geometric (Fey & Lenssen, 2019) and executed on system with 128GB of RAM and an Nvidia Tesla A100 GPU with 48GB of memory.
for 20 epochs
Experimental protocol and model configuration For Q1, we calculated the covering number W(, FD,, E) for various datasets, graph orders, and radii by solving the corresponding set cover problem. We also compare the bound on the covering number presented in Theorem 10 against the covering number (V, 6[ using the 1-norm instance of the cut norm as computing the cut norm is MaxSNP-hard For Q2. we measure whether the Forest distance input perturbations lead to perturbations in the MPNN outputs expected Lemma 14. We used random 80/10/10 split for siiminng/vlidatioo//sstnngg Each plot included 1 000 data points generated by selecting random graph size. The Forest distance for two graphs of the chosen size, randomly sampled from the dataset, can be compared with the Fuclidean distance between their MPNN outputs. For Q3, we evaluated the generalization gap by estimating the train and test losses and compared it against our generalization bound derived for the Forest distance in Proposition 15. We utilized an upper estimate of the Lipschitz constant obtained from Q2 and an L = 1 (Mao et al., 2023) to compute the bound. We selected the radii that yielded the tightest bound. See Table for the values of C, CrDy, and ma,d.3 used in the computation of our bound.
48

---

Covered Forests
Gn
Fn
20
160
20
Covering number
18
90
18
140
18
100
120
14
75
16
14
100
120
14
12
60
12
12
80
80
45
10
60
8
60
8
40
30
40
20
4
15
20
2
12
14
16
18
10
15
6
19
16
120
Covering number
140
18
18
105
14
120
15
13
100
16
12
80
15
60
11
60
14
45
40
4
30
9
20
12
15
0
3
10
15
20
11
10
20
6
E
Figure 8. The covering number (-, FD3, s) and the number of 1-WL indistinguishable graphs (upper black) for the graph families Gn. T and Fr across different graph sizes n and radii
MUTAG
NC11
MCF-7H
MOLHIV
135
20
20
16
20
20
Covering number
120
105.
16
16
14
16
120
16
s0
15
14
12
12
12
10
12
60
10
10
8
10
10
20
7.0
7.5
8.0
8.5
9.0
7.0
7.5
8.0
8.5
9.0
Covering number
90
22
18
120
75
100
60
18
8
8
6
14
4
20
0
20
10
10
15
20
10
15
20
0
5
10
15
20
E
E
Figure The covering number (1 FD2, s) and the number of 1 1-WL indistinguishable graphs m. (upper row, black) for real-world datasets across varying graph sizes and radii e.
Q. Dataset statistics
The statistics of the real-world datasets can be found in Table and estimates of the coefficients in Theorem 10 can be found in Table 3.
49

---

Covered Forests
MUTAG
MCF-7H
MOLHIV
135
16
Covering numbe
120
105
75
90
7%
bound
18
12
15
mi
our bound
12
10
me
bound
100
140
120
5%
set
hound
60
80
45
60
30
40
15
20
0
10
Figure 10. The covering number (',, FDD,,00 07) bound, the 1-norm set and the number of 1-WL indistinguishable graphs me for real-world datasets with varying graph orders.
MUTAG
NC11
MCF-7H
MOLHIV
[lH -GG2
0.57
42
0.68.
4
layers
30
18
2.5
FDe
FDo
FD,
FDg
45
[| -GG2llz
0.84
0.67
0.63
40
r= 0.54
N W a U. 0h
35
30
layers
25
0
0.0
2.5
5.0
7.5
0
10
15
0
10
20
0
50
100
150
FD
FD:
FD)
FD)
[|MG;) I 10)--hee -GGa)llz
SENWA 0 68
10
12
14
0.49
8
10
36
layers
30
24
4
12
20
250
500
750
FD2
FD2
FD2
FD;
AGG.)ll
12
0.78
18
16
0.64
0.61
0.53
C5 09
10
12
12
48
40
3 layers
[lhi,,)
24
16
2
20
40 FD3
60
0
100
200
0
200
400
0
1000
2000
3000
FDg
FD3
FD;
Figure 11. Correlation between MPNN outputs and the Forest distance FD across real-world datascts using varying number of MPNN
layers. The Pearson correlation coefficient between [lh(G,) A(G2)1l2 and the Forest distance FDy are shown on the top left of the figures
Table 2. Statistics for the MUTAG, NCII, NCII, MCF-7H, and MOLLIVV datasets.
Datasel
MUTAG
NCI1
MCF-11 7H
OGBG-MOLHIV
Graphs
188
4110
27770
117
Classes
Avg. vertices
17.9
29.9
26.4
25.5
Avg. edges
39.6
32.3
28.5
27.5
50

---

Covered Forests
Table 3. Estimates of the coefficients in Proposition 15 for real-world datasets. We compute Wh,,d,3 in a data-dependent fashion for each datasct, i.c., not for the whole graph class.
Dataset
MUTAG
NC11
MCF-7H
OGBG-MOLHIV
150
288
22216
902
M,34.3
139
808
25448
34
M
5,890
2.389
0.497
1.704
CFD,
0.377
0.202
0.101
0.107
28
244
222
51


Reviews:
[{"review_id": "jqWdr5HjB7", "reviewer": "Reviewer_LBby", "summary": "This paper studies the generalization bound for message passing network. The author extend the generalization framework of using pseudo-metric to graph, with a focus on studying what graph pseudo metric is suitable to obtain a tight bound for the generalization error of MPNNs. Specifically, the author studied tree distance for non-labeled case and tree mover's distance for labeled case, showing that fine-grained and 1-WL expressive graph distance can provide much tighter generalization bound comparing to 1-WL discrete metric. The main contribution contains several parts: 1) successfully applied the generalization framework of Xu & Mannor to graph setting, with defining graph pseudo metric. 2) based on the framework, the key part of tight the bound is to find proper metric with smaller covering number; the author have show the advantage of using tree distance and tree mover's distance. 3) the author also have done fine-grained study for different model architecture and loss function. In the experiment section, the paper shows that their bound is tight for the empirical generalization gap.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for their detailed and constructive review.**\n\n> Some part is not clear enough, and the main content is not self contained without looking at the appendix. For example, the equation  in line 187 does not explain what is the definition of unr. Also, the Figure 4 referenced in line 211 are essential for understanding the > presented metric, I think the author should move it to the main paper. \n> In the meantime, I think many claims and theorms can be improved with presentation, with simplifying notification and moving minor > bounds to appendix. This will make the reading and understanding much better. \n> The section 4, while being the main section of the paper, lacks good structure. The author presents all findings and derivations >sequentially in a single flat level. I think this make the reading harder. The author should think about how to present this section much \n> structured and simpler.\n\nThank you for pointing out these omissions. We will use an additional page in the camera-ready version to explain the unrolling trees in the main text and refer the reader to their definition in Appendix C. \n\nGiven the extra page available, we will include an introductory paragraph in Section 4 highlighting the main results and guiding the reader through the section's flow to improve readability.\n\n> I think the author can consider adding additional experiments to cover the influence of graph structure, aggregation, and loss function, which is claimed in theory and contribution but not empirically studied in the experiments.\n\nThank you for this suggestion, we will try our best to include these experiments to align theory and practice more. \n\n**Please consider updating your score if you are satisfied with our answer. We are happy to answer any remaining questions.**", "claims_and_evidence": "Without checking the correctness of proofs, I do think the author have made their claims supported, both theoretically and empirically.", "methods_and_evaluation_criteria": "1. The author have designed several experiments to show that their derived bounds and insights can provide guidance in real-world graph MPNN setting. \n2. Nevertheless, it would be interesting to see how sum and ordinary aggregation differ in theory and experiment.", "theoretical_claims": "No I have not checked. I will not provide confident review on their theorems.", "experimental_designs_or_analyses": "Yes I have checked. I think the experiments, while being limited, are aligning with the theory presented in the paper.", "relation_to_broader_scientific_literature": "I think the author made a good step of linking several previous works of generalization bound, and make a forward step for MPNN's generalization bound. I value the theory contribution of it to make the generalization study of GNNs more complete.", "essential_references_not_discussed": "I'm not aware of that. But I should also acknowledge that I'm not very familiar with generalization bound literature. \nWhen I check the related work section in appendix, I feel the author have mentioned many recent papers of the area.", "other_strengths_and_weaknesses": "### Strength\n1. The author successfully applied modern generalization framework to graph setting, and linked the framework with many recent graph metrics. With good theoretical contribution, the author also confirms that the derived bound is relatively tight in empirical setting. \n2. Comparing with previous literature, the usage of fine-grained graph similarity metric moves a great step forward for this GNN generalization area. If all claims and theories shown are correct, the contribution should be great for future studies. \n3. The author did great job in literature review and background introduction.\n4. Figures presented in the paper are very helpful for understanding equations and key ideas. \n\n### Weakness \n1.  Some part is not clear enough, and the main content is not self contained without looking at the appendix. For example, the equation in line 187 does not explain what is the definition of unr. Also, the Figure 4 referenced in line 211 are essential for understanding the presented metric, I think the author should move it to the main paper. \n2. In the meantime, I think many claims and theorms can be improved with presentation, with simplifying notification and moving minor bounds to appendix. This will make the reading and understanding much better. \n3. The section 4, while being the main section of the paper, lacks good structure. The author presents all findings and derivations sequentially in a single flat level. I think this make the reading harder. The author should think about how to present this section much structured and simpler.", "other_comments_or_suggestions": "I think the author can consider add additional experiments to cover the influence of graph structure, aggregation and loss function. Which is claimed in theory and contribution, but not empirically studied in experiment.", "questions_for_authors": "N/A", "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": "qOaDncPXps", "reviewer": "Reviewer_QFxN", "summary": "This paper first defines three pseudo-distances on graphs compatible with 1-WL or its variants. First, the labeled tree distance, which is an extension of the tree distance to graphs with node features, is defined, and the equivalence with 1-WL indistinguishability is shown. Next, the forest distance is defined using graph unrolling, and the equivalence with 1-WL indistinguishablity up to L-time unrolling is shown. Finally, the mean forest distance is defined as a variant of the forest distance, and the equivalence with 1-MWL is shown.\n\nThe generalization error bounds for MPPNs are derived using these distances by showing that MPPNs are equicontinuous with respect to the tree distance and Lipschitz continuous with respect to the forest distance. These guarantee the robustness of MPPNs, which in turn gives generalization error bounds in terms of the covering number.\n\nNumerical experiments evaluate the relationship between the covering number and WL-indistinguishable graphs, the relationship between the forest distance and the output of MPN, and the relationship between the generalization performance and the generalization bounds.\n\n\n## update after rebuttal\n\nI thank the authors for responding to my review comments. I am satisfied with them. Although the numerical evaluations align with theoretical analyses, I think we need more significance to be eligible for strong acceptance. Therefore, I keep my score (4. accept)", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for their fair and constructive review.**\n\n> Q1. We can expect the experiment's results from the definition of the covering number and WL-indistinguishability. Therefore, I have a question whether the observations from this experiment are new.\n\nYou are correct that, by definition, we expect the covering number to decrease with the radius and increase with the order. What is new in our work is that we derive explicit upper bounds on the covering number for different graph families (n-order graphs, otter trees, and an artificial graph class), capturing how it scales with radius and graph order.\n\nSpecifically: \n\ni) Proposition 10 shows that for n-order graphs, the covering number is upper bounded by $m_n/(k+1)$, showing a linear decrease with the radius, and an $\\mathcal{O}(m_n)$ increase with $n$.\n\nii) Proposition 12 establishes a stronger bound for Otter trees, showing exponential decay in the radius and again O(m_n) dependence on n.\n\niii) Appendix N introduces an artificial graph class where the covering number scales with m_n/n instead of m_n.\n\nHence, we empirically compute covering numbers in Figure 8 and observe trends that align with the theoretical bounds. These results help validate the tightness of our derived bounds. Indeed, for n-order graphs, the covering number can be bounded by a linear function on the radius, and for otter trees, it can be bounded by an exponential function on the radius. \n\nHowever, the current phrasing of Q1 may not fully reflect this. We will revise it to “To what extent do the empirical covering numbers for different graph families match the theoretical upper bounds derived in Section 4?.”\n\n> Q3. The experiment shows that the generalization performance gap and theoretical upper bounds have the same scale. However, we cannot say the tightness of the bound from this observation.\n\nOur goal in Q3 was not to claim that the bound is tight in the formal sense, but to show that the bound and the generalization gap are of the same scale in practice. We will clarify this point.\n\n> I checked Sections Q and R.\n> Although $\\mathcal{F}_n$  is referred to as a set of graphs, it is not defined in the main text or appendix. I suggest adding its definition.\n\nThank you for pointing this out. $\\mathcal{F}_n$  is an artificial graph class defined in Appendix N. We will include its definition in the main text of the revised papers. \n\n> One of the weaknesses of this paper is the excessive appendix (37 pages), which reduces its clarity. For example, as this paper mainly focuses on generalization of MPNNs, the discussion on the mean forest distance seems to be different from its main scope.\nOn the other hand, I am positive about adding explanations on the cut norm, graphon, and WL algorithm in the appendix because they allow readers unfamiliar with these concepts to understand the paper in a self-contained manner.\n\nWe acknowledge that the appendix is quite extensive. However, our goal was to ensure that all notations and definitions used in the proofs are rigorously defined and that the paper remains self-contained for readers with varying backgrounds. For that reason, we will provide some additional discussion on Appendices D, K, and C about the intuition behind cut-norm, graphons, and the WL algorithm, respectively.  \nWe defined the mean forest distance to show that mean aggregation MPNNs satisfy the Lipschitz property for a coarser pseudo-metric (mean forest distance), leading to tighter generalization bounds. We will clarify this motivation in the main paper. \n\nOverall, we will use the additional page to make the main part more self-contained.\n\n> this paper uses two terms (labeled and attributed) to describe a node with a feature. I want to clarify whether they are different concepts.\n> l.400(right): Unless I am missing something, $\\mathcal{F}_n$ is undefined.\n> L.431(left): How are the Forest distance and MPNN outputs correlated? is better\n> L.1652 : The above generalization bound: I could not identify the bound this sentence refers to.\n> L.1696: Theorem 35 in the main paper: Theorem 35 is not in the main text but in the appendix.\n\nThank you for pointing this out. \n1. The terms labeled and attributed refer to the same underlying concept, with a minor distinction noted in the background section: labeled typically refers to discrete labels drawn from a finite set, whereas attributed generally refers to continuous feature vectors in $\\mathbb{R}^d$.\n\n2.,5. Thank you. We will correct this in the camera-ready version. \n\n3. Thank you for the suggestion.\n\n4. Should have been “improved the generalization bound in \\cref{robustness_bound}” referring to the one introduced by Xu & Manor.  We will correct this in the camera-ready version.\n\n**Please consider updating your score if you are satisfied with our answer. We are happy to answer any remaining questions.**", "claims_and_evidence": "The main claim of this paper is that introducing similarity-based distances, such as the labeled tree and forest distances, makes generalization bounds tighter than existing VC-dimension-based bounds. This claim is supported by Proposition 9 (for MPPNs with order-normalized sum aggregation on unlabelled $n$-order graphs), Proposition 15 (for MPPNs with sum aggregation on attributed bounded-degree graphs), and their corollaries.\n\nIt is claimed that these theoretical results provide insight into the generalization performance of empirical MPPNs. However, as discussed below, I have questions about the design and interpretation of the numerical experiments in Section 5 and think that they are not sufficient as evidence.", "methods_and_evaluation_criteria": "The theoretical analysis is appropriate to support the claim because, in general, the generalization bounds by the covering number are tighter than that by the VC dimension. In addition, Appendix L, in which the bound using the VC dimension is derived from the result of this paper, justifies the claim.\n\nOn the other hand, the three numerical experiments in Section 5 are not convincing. In particular, I have questions about Q1 and Q3:\n\nQ1. We can expect the experiment's results from the definition of the covering number and WL-indistinguishability. Therefore, I have a question whether the observations from this experiment are new.\nQ2. We see that forest distance and changes in the MPNN output are correlated and that small changes in forest distance do not significantly change output. This observation is consistent with Lemma 14.\nQ3. The experiment shows that the generalization performance gap and theoretical upper bounds have the same scale. However, we cannot say the tightness of the bound from this observation.", "theoretical_claims": "I read the proofs of the theorems in this paper, specifically Section E, Propositon 38 in Section J, Propositon 43 in Section K, and Section O, and the lemmas associated with them. However, due to time constraints, I could not carry out a detailed check line by line.", "experimental_designs_or_analyses": "I checked Sections Q and R.\n\nAlthough $\\mathcal{F}_n$ is referred to as a set of graphs, it is not defined in the main text or appendix. I suggest adding its definition.", "relation_to_broader_scientific_literature": "This paper extends the tree distance proposed in [Böker, 2021] and defines labeled tree distance and forest distance. Then, as analogs of the tree distance, the equivalence between these distances and 1-WL indistinguishability (or its variants).\n\nFurthermore, the robustness of MPNNs with respect to those pseudo distances is used to show the generalization performance bound of MPNNs for the covering number. This result is a refinement of the bound obtained in [Morris et al. (2023a)], which uses VC dimension.", "essential_references_not_discussed": "As far as I checked the related studies, the coverage of existing studies on generalization analysis for the node and graph prediction tasks is OK. However, I may have missed some important literature since I am less familiar with graph prediction tasks.", "other_strengths_and_weaknesses": "One of the weaknesses of this paper is the excessive appendix (37 pages), which reduces its clarity. For example, as this paper mainly focuses on generalization of MPNNs, the discussion on the mean forest distance seems to be different from its main scope.\n\nOn the other hand, I am positive about adding explanations on the cut norm, graphon, and WL algorithm in the appendix because they allow readers unfamiliar with these concepts to understand the paper in a self-contained manner.", "other_comments_or_suggestions": "1. this paper uses two terms (labeled and attributed) to describe a node with a feature. I want to clarify whether they are different concepts.\n2. l.400(right): Unless I am missing something, $\\mathcal{F}_n$ is undefined.\n3. L.431(left): *How are the Forest distance and MPNN outputs correlated?* is better\n4. L.1652 : *The above generalization bound*: I could not identify the bound this sentence refers to.\n5. L.1696: *Theorem 35 in the main paper*: Theorem 35 is not in the main text but in the appendix.", "questions_for_authors": "N.A.", "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": {"ethical_review_concerns": "N.A."}}, {"review_id": "0yqVNcVLMk", "reviewer": "Reviewer_e2Pe", "summary": "This paper presents a new framework for analyzing generalization properties of Message-Passing Neural Networks (MPNNs) via fine-grained graph pseudo-metrics. These distances capture subtle structural similarities that the usual 1-WL equivalence classes overlook. The key theoretical results show that MPNNs of varying aggregation schemes (sum, mean) remain Lipschitz with respect to these distances, allowing the authors to derive covering number based generalization bounds that account for partial graph similarity rather than a purely binary (same/different) classification. Empirically, the paper demonstrates that these refined metrics yield more accurate coverings and tighter bounds, thereby better predicting real-world generalization gaps.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for their detailed and constructive review.**\n\n> One potential weakness is the computational complexity of computing pseudo-metrics at scale on large graphs. The authors do mention computational complexity but might elaborate more on possible approximations.\n\nThank you for highlighting computational complexity. Throughout the paper, we discuss two main distances: the tree distance (with either the cut norm or the l2-norm) and the forest distance. \n\nAs shown in Lemma 3, the forest distance is equivalent to the Tree Mover’s Distance (TMD) introduced by Chuang et al. This allows us to compute it efficiently using dynamic programming (as shown in the original paper) in time: $\\mathcal{O}(t(n) + Lnt(q))$, where $q$ is the maximum degree of a node (in both graphs), $n$ the number of nodes, and $t(m) = O(m^3 log(m))$.\n\nThe tree distance with the L2-norm can be computed in polynomial time (more precisely, an $\\varepsilon$-solution), as detailed in “Interior-Point Polynomial Algorithms in Convex Programming” (Section 6.3.3). \n\nOn the other hand, the cut norm poses a much more difficult combinatorial optimization problem. Its computation is indeed challenging. One of the most well-known approximation techniques is given in “Approximating the Cut-Norm via Grothendieck’s Inequality”. Additional relevant works will be added to the main paper (“Random Sampling and Approximation of MAX-CSP Problems”, Alon et al., “Quick Approximation to Matrices and Applications”, Frieze & Kannan.) \n\nIt is worth mentioning that for the theoretical results in our paper, either the tree distance with the cut norm or with the l2-norm can be used interchangeably, as they define the same topology—this is discussed in “Fine-Grained Generalization Analysis.”\n\nThe revised paper will add a detailed discussion regarding the pseudo-metrics computational complexity. \n\n> The paper’s experimental scope is somewhat narrow, focusing on a small set of molecules/graphs; the empirical portion might be strengthened by more extensive analysis, including for other graph topologies\n\nThis is a good point. However, we view our work as theoretical work. We will try our best to include experiments with other graph structures,\n\n**Please consider updating your score if you are satisfied with our answer. We are happy to answer any remaining questions.**", "claims_and_evidence": "The authors provide clear definitions and statements of theoretical results and provide proofs for all theoretical claims.\n\nTheir experiments, while somewhat limited in scope and scale, show results consistent with the theoretical discussion; in particular, the coverage size shrinks significantly under these pseudo-metrics, which corresponds to smaller generalization gaps (Tab. 1). This addresses (though does not exhaustively prove) the claim of better real-world bounds.\n\nOverall, the main claims are supported by theoretical analysis and experiments, prior work on 1-WL alignment and generalization bounds is discussed in detail.", "methods_and_evaluation_criteria": "The theoretical analysis is overall sound. The data selected for experiments seems appropriate (though somewhat limited in scale and scope).", "theoretical_claims": "The paper provides clear statements of theoretical claims and proves. Proof sketches/ short descriptions of the proof idea are given in the main text, more detailed analysis is in the appendix. \n\nWhile I have not checked every detail in the proofs in the appendix, the arguments and line of reasoning seems correct, I did not see any obvious gaps or errors.", "experimental_designs_or_analyses": "The experiments mostly use standard GNN benchmarks (MUTAG, NCI1, etc.) and includes a demonstration of how the covering number changes with the radius parameter. The authors show correlations (Figures 8–11 in appendix) between the distances and MPNN output differences, which supports the Lipschitz-type claim.\n\nWhile sample sizes in these experiments are typical for classification tasks on molecular graphs, it might be useful to see a broader range of data sets, possibly with more variety in graph topologies. But the presented experiments are overall adequate and support the theoretical results.", "relation_to_broader_scientific_literature": "The paper clearly connects to the established line of work about 1-WL expressivity (Morris et al., Xu et al.). It complements prior work that used coarser, purely discrete distances (i.e., 0 vs. 1 if the graphs are 1-WL distinguishable). The authors also provide comprehensive references to relevant works on GNN generalization. I did not notice major omissions in related literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n- The introduction of refined metrics that preserve WL-like expressivity but provide more “granularity” is conceptually novel and addresses gaps in prior analyses.\n- The Lipschitz continuity argument for sum- and mean-aggregation MPNNs is handled neatly and supports a variety of common network layers.\n- The paper is well-written.\n\nWeaknesses:\n- The paper’s experimental scope is somewhat narrow, focusing on a small set of molecules/graphs; the empirical portion might be strengthened by more extensive analysis, including for other graph topologies.\n- One potential weakness is the computational complexity of computing pseudo-metrics at scale on large graphs. The authors do mention computational complexity but might elaborate more on possible approximations.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "see weaknesses", "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": "DzEQe70L3K", "reviewer": "Reviewer_EBjh", "summary": "This paper presents a study on the generalization abilities of sum-aggregation message passing graph neural networks (GNNs) based on a covering number approach. Towards this goal, they employ the so-called forest distance pseudometric, which is an intuitive re-formulation of the tree mover’s distance by Chuang and Jegelka. In particular, they exploit the Lipschitzness of GNNs wrt this pseudometric, and use the results from Xu and Mannor to obtain generalization bounds. Moreover, the paper deals with GNNs with mean (rather than sum) aggregation by defining a slightly modified metric.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We thank the reviewer for their fair and constructive review.**\n\n> the paper is very heavy and difficult to understand, and at times it lacks clarity in what it wants to achieve and how to prove it. It might be beneficial to add some more intuitive discussion between the various propositions. For example:\nan intuition of the behavior of \\widebar{\\gamma}^{\\leftarrow} would help understand the results of Proposition 9 and its consequences\nan explanation on the choice of using the Tree distance rather than the Forest distance (see also questions) \n\nWe agree that the paper is relatively dense. We will use the additional page in the camera-ready version of the paper to add more intuition and guide the reader. For example, we will add intuitive explanations before a theorem/proposition. \n\n> the fact that an estimated Lipschitz constant (rather than an upper bound for the entire GNN class) is used in the results of Table 1 should be stated clearly, and not hidden in Section Q.\n\nWe will explicitly mention that we do not compute the uniform Lipschitz constant for our experiments but instead use an empirical Lipschitz constant.\n\n>Minor comments:\n>In eq. 7, A(G) is never defined (only in the Appendix). Please double check that everything is defined properly.\n>in lemma 2 the comma in the \"only if\" is misplaced\n>the footnote 7 on the \"technical reasons\" should really be part of the Proposition.\n\nThank you for your comments. We will consider all minor comments.\n\n> Why do you use the Tree distance for unlabeled graphs and the Forest distance for labeled graphs? Could one not use always the Forest distance? This distinction should be clarified. \n\nThe decision to use both the tree distance and forest distance is motivated by:\n\n(i) Computational complexity: The tree distance with the L2-norm can be computed in polynomial time (see our response to Reviewer e2Pe), and we will move this explanation to the main text.\n\n(ii) The tree distance allows us to derive generalization bounds for graph classes without requiring bounded degree assumptions on graphs, which are necessary for the finiteness of the covering number using the forest distance.\n\n> I don't understand the relevance of the subsection on Otter trees, as this is an artificial setting with little practical relevance. Could you motivate your choice of inserting this in the main paper? I think that, e.g., the construction of Theorem 10 that allows you to obtain a cover of size m/(k+1) is much more interesting.\n\nThe motivation was to show that in this specific graph class, the covering number admits an upper bound that decreases exponentially with the radius. This shows that our framework yields significantly tighter generalization bounds to structurally more simple graphs. \n\n\n**Please consider updating your score if you are satisfied with our answer. We are happy to answer any remaining questions.**", "claims_and_evidence": "All claims are supported by formal proofs. Moreover, the theoretical results are supported by experimental evidence.", "methods_and_evaluation_criteria": "The proposed theoretical approach of combining a metric for graphs such that GNNs are Lipschitz (or equicontinuous) to it with the robustness framework of Xu and Mannor indeed makes sense for deriving data-dependent generalization bounds for GNNs. \nThe datasets chosen for the experimental evaluation are few, but for a theory-driven paper this is not a problem.", "theoretical_claims": "I checked the proofs for most of the claims in the main paper, albeit not in depth, and as far as I can tell they seem correct.", "experimental_designs_or_analyses": "The datasets chosen for the experimental evaluation are few, but for a theory-driven paper this is not a problem. The experimental setup described in section Q is sensible, and the code is available.", "relation_to_broader_scientific_literature": "The paper addresses a gap in the literature, namely obtaining tight data-dependent generalization bounds for GNNs. The results are non-trivial, but somewhat incremental on the papers it is based on. In particular, the tree distance is obtained from Böker 2021 and the forest distance is a re-formulation of the tree over distance by Chuang and Jegelka 2022. Moreover, the generalization bounds are obtained from the pre-existing work of Xu and Mannor. Nonetheless, I think this is an important advancement in the learning theory of GNNs.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths:\n- the paper seems to be technically sound, far as I can tell the proofs seem correct. \n- the paper addresses a very relevant problem, obtaining tight generalization bounds for GNNs.\n\n Weaknesses:\n- as already mentioned, the paper is somewhat incremental on the papers it is based on.\n- the paper is very heavy and difficult to understand, and at times it lacks clarity in what it wants to achieve and how to prove it. It might be beneficial to add some more intuitive discussion between the various propositions. For example:\n    -  an intuition of the behavior of $\\bar\\gamma^{\\leftarrow}$ would help understand the results of Proposition 9 and its consequences\n    - an explanation on the choice of using the Tree distance rather than the Forest distance (see also questions)\n    - an intuition on the construction of Theorem 10 (again, see questions)\n- the fact that an estimated Lipschitz constant (rather than an upper bound for the entire GNN class) is used in the results of Table 1 should be stated clearly, and not hidden in Section Q.", "other_comments_or_suggestions": "Minor comments:\n* In eq. 7, A(G) is never defined (only in the Appendix). Please double check that everything is defined properly.\n* in lemma 2 the comma in the \"only if\" is misplaced\n* the footnote 7 on the \"technical reasons\" should really be part of the Proposition.", "questions_for_authors": "- Why do you use the Tree distance for unlabeled graphs and the Forest distance for labeled graphs? Could one not use always the Forest distance? This distinction should be clarified. \n- I don't understand the relevance of the subsection on Otter trees, as this is an artificial setting with little practical relevance. Could you motivate your choice of inserting this in the main paper? I think that, e.g., the construction of Theorem 10 that allows you to obtain a cover of size m/(k+1) is much more interesting.\n\n\n----\n#### Update\nAfter the rebuttal, my recommendation remains mostly positive.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a generalization analysis framework for MPGNNs by introducing new graph pseudometrics aligned with 1-WL expressivity. Building on prior robustness frameworks, the authors derive covering number-based generalization bounds that reflect structural similarities between graphs more accurately than discrete WL-based metrics. Theoretical results are complemented by empirical observations.

I recommend acceptance. The paper offers a meaningful advance in our understanding of GNN generalization, wit theoretical contributions in recent developments in graph similarity. The analysis is rigorous & the chosen metrics are well-motivated.
Decision: Accept (spotlight poster)