Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs
Authors: Levi Rauchwerger
Stefanie Jegelka
Ron Levie
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Graphon Neural Networks
Machine Learning Theory
1-WL test for Graphons
Generalization
Expressivity
Universal Approximation
Wasserstein Distance
Optimal Transport
Computation Trees
Primary area: learning on graphs and other geometries & topologies
TL;DR: We analyze the generalization, expressivity, and universality of graph neural networks on attributed graphs via a metric defined through computation trees of attributed graphons, which are based on an extension of the graphon 1-WL test.

Abstract: We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs, i.e., with node attributes. To this end, we propose pseudometrics over the space of all attributed graphs that describe the fine-grained expressivity of GNNs. Namely, GNNs are both Lipschitz continuous with respect to our pseudometrics and can separate attributed graphs that are distant in the metric. Moreover, we prove that the space of all attributed graphs is relatively compact with respect to our metrics. Based on these properties, we prove a universal approximation theorem for GNNs and generalization bounds for GNNs on any data distribution of attributed graphs. The proposed metrics compute the similarity between the structures of attributed  graphs via a hierarchical optimal transport between computation trees. Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points but the space of graphs is not relatively compact, which prevents universal approximation and generalization analysis.

Published as a conference paper at ICLR 2025
GENERALIZATION, EXPRESSIVITY, AND UNIVERSAL- ITY OF GRAPH NEURAL NETWORKS ON ATTRIBUTED GRAPHS
Levi Rauchwerger', Stefanie Jegelka 2.33 Ron Levie*
Technion IIT, Faculty of Mathematics, MIT, Dept of EECS and CSAIL, TTUM, School of CIT, MCML, MDSI levi rrcampus. tww.pion.teeciiionnnommm ac.il, stefanie. jegelkeetuunnnne levieron@feechiion..cc
ABSTRACT
We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs, i.e., with node attributes. To this end, we propose pseu- dometries over the space of all attributed graphs that describe the fine-grained expressivity of GNNs. Namely, GNNs are both Lipschitz continuous with re- spect to our pseudometries and can separate attributed graphs that are distant the metric. Moreover, we prove that the space of all attributed graphs is rela- tively compact with respect to our metrics. Based on these properties, we prove a universal approximation theorem for GNNs and generalization bounds for GNNs on any data distribution of attributed graphs. The proposed metrics compute the similarity between the structures of attributed graphs via hierarchical optimal transport between computation trees. Our work extends and unites previous ap- proaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, derived metrics under which GNNs continuous and separate points but the space of graphs is not relatively compact, which prevents universal approximation and generalization analysis.
INTRODUCTION
Graph neural networks (GNNs) have become widely used tool in science and industry due to their ability to capture complex relationships in graph-structured data. This makes them particularly useful (Zhou et al., 2020) in domains such as computational biology (Stokes et al., 2020; Atz al., 2021), molecular chemistry (Wang et al., 2023), network analysis (Yang et al., 2023), recommender systems (Fan et al., 2019), weather forecasting (Keisler, 2022) and learnable optimization (Qian et al., 2024; Cappart et al., 2023). As result, there has been substantial interest in understanding theoretical properties of GNNs, such as expressivity (Xu et al., 2019), stability (Ruiz et al., 2021) robustness (Ruiz et al., 2021), and generalization (Verma & Zhang, 2019; Yehudai et al., 2020; Oono & Suzuki, 2020; Li et al., 2022; Tang & Liu, 2023; Levie, 2023; Maskey et al., 2022; 2024).
Initial works analyzing expressivity of GNNs focused the Weisfeiler-LLman (WL.) graph isomor- phism test as a criterion to distinguish graphs (Xu et al., 2019; Morris et al., 2019; Zhang et al., 2023a; 2024b), others used criteria such as subgraph or homomorphism counts or biconnectivity (Zhang et al., 2024a; 2023b; Chen et al., 2020; Tahmasebi et al., 2023). However, the WL test merely considers distinguishability of graphs, while analyses of robustness or generalization need metric, i.e., a quantification of similarity. Usually, for graphs, this is pseudometric, since GNNs typically cannot distinguish all graphs.
In this paper, we define a pscudometric for attributed graphs which is highly related to the type of computation message passing GNNs (MPNNs) perform. Our construction enables unified anal- ysis of expressivity, universal approximation and generalization of MPNNs on graphs with node attributes. This work extends and unifies several prior approaches and, to the best our knowledge, this is the first work to enable this analysis in such general setting. Both generalization and expres- sivity analysis rely on a few prerequisites that we need to attain via an appropriate (pseudo-)metric) )metric: one must identify the finest topology in which (1) MPNNs separate points, i.e., for any two different points in space, there exists an MPNN that can distinguish between them; (2) MPNNs are Lipschitz continuous; (3) the space of inputs, i.e., attributed graphs, is a compact space.

---

Published as a conference paper at ICLR 2025
Given the interest in understanding GNN robustness and generalization, few recent works studied pseudometrics on graphs. Most of them reflect the computation structure of MPNNs in defining the distance, essentially aiming to view graphs from the viewpoint of the GNN. Message passing, when unrolled, leads to a tree-structured computation free rooted at each node for computing the feature of that node. The pseudometries then define distances between computation trees, often via optimal transport (Wasserstein distance). Chen et al. (2022; 2023) prove that MPNNs separate points and are Lipschitz continuous over the Weisfeiler-Lehman (WL) distance between hierarchies of probability measures. Since the space of graphs is not compact under their metric, they achieve universal upproximation by limiting the analysis to an arbitrary compact subspace. To quantify stability and domain transfer of GNNs, Chuang & Jegelka (2022) define the Tree Mover's Distance between finite attributed graphs. However, the above pseudometries on finite graphs do not yield the desired compactness, and hence no universal approximation over the entire space of attributed graphs. Moreover, a robustness-type generalization theorem over the entire space, which depends on the space having a finite covering number, is not attainable. To solve this, we focus on graph limit theories in which the space of graphs is completed to a compact space, i.e., graphon theory. Inspired by Chen et al. (2022), Böker al. (2023) took the first steps towards solving the aforementioned problem, by extending the expressivity analysis to graphons and using iterated degree measures (Grebik & Rocha, 2021) represent an analog of computation trees and the 1-WL test on infinite objects. While this enables proofs that MPNNs separate points and are Lipschitz over a compact space, and hence have universal upproximation, their pseudometric is restricted to graphs without attributes. In contrast, Levie (2023) defined limit object of attributed graphs, i.c., graphon-signals. Their pseudometrie, an extension of the cul distance, a common metric between attributed graphs, allows to analyze generalization via compactness and Lipschitz continuity, but is too fine to allow MPNNs to separate points, so does not allow universal approximation. The position paper (Morris et al., 2024) identifies these limitations, posing them as open problems. For additional related work, see Appendix B.
In this work, we close these gaps via a unified approach that allows for an analysis of expressivity, universal approximation, and generalization. Inspired by prior works, we too base our pseudometrics on Wasserstein distance (or Prokhorov metric) between distributions of computation tree analogs. To accommodate attributed graphs and graphons, we extend the theory of iterated degree measures- a hierarchy of measures that reflects computation tree structure to graphon-signale and then de- fine an appropriate extension of MPNNs and appropriate distance between our continuous analogs of computation trees. We then prove that our pseudometric leads to topology with the three desider- ata above: (1) MPNNs separate points; (2) MPNNs are Lipschitz continuous; and (3) the input space of attributed graphons compact. This enables us to invoke the Stone Weieeeeiessssssss theorem to show universal approximation for continuous functions on attributed graphons, and hence, graphs. Compactness and Lipschitzness enable a uniform Monte Carlo estimate to compute a generalization bound for MPNNs. Our generalization bound makes no distributional assumptions on the data and number of parameters of the MPNN. Empirically, our pseudometric correlates with output perturba- tions of the MPNN, allowing to judge stability.
Contributions. We propose the first metric for attributed graphs under which the space of attributed graphs is compact and MPNNs are Lipschitz continuous and separate points. Our construction leads to the first theory of MPNNs that unifies expressivity, universality, and generalization on any data distribution of attributed graphs. In detail:
We show a fine-graieed metric version of the separation power of MPNNs, extending the results of Böker et al. (2023) to attributed graphs: two graph-signals are close in our metric and only if the outputs of all MPNNs on the two graphs are close. Hence, the geometry of graphs (with respect to our metric) is equivalent to the geometry of the graphs' representations via MPNNs (with respect to the Euclidean metric).
We prove that the space of attributed graphs with our metric is compact and MPNNs are Lipschitz continuous (and separate points). This leads to two theoretical applications: (1) universal approximation theorem, i.e., MPNNs can approximate any continuous function over the space of attributed graphs; (2) a generalization bound for MPNNs, akin to robustness bounds (Xu & Mannor, 201 2). requiring no assumptions on the data distribution or the number of GNN weights.
2

---

Published as a conference paper at ICLR 2025
2 BACKGROUND
We begin with some background and notation, for additional background and fundamental concepts in topology see Appendix A. An index is available in Appendix N.
Basic Notation. Throughout this text, À denotes the Lebesgue measure on [0, 1], and we consider measurability with respect to the Borel o-algebra. For any metric space X, we denote by B())) its standard Borel a o-algebra, Given a measure μ on X, we define its total mass as ||म|| := {((x)). For standard Borel space (),, (B))) and measurable map f X + Vr we define the push-forward fa of y via f as f-u((A) := (((f"((A) for any A E B()). Inequality between two measures u // on some space X' means that for any set A X, it holds that p(A) S v(AA). Given a vector T = (Za)) where A can be any countable set, we denote by Tog and x((o) ) the element at index ag E A of Σ. For a finite set A, | is the cardinality. For K No, we denote [K] {0, 1.....K) K}.
In our notation, a function is denoted by f A C. When f is evaluated at a point x E A we write f(z) or fa. We may also write f(-) or f-, which simply means f. We define Il := suPzejo.1] [x)]]. The covering number of metric space (X, d) is the smallest number of open balls of radius needed to cover X. The notation IC represents any compact space, i.e., topological space X' in which every cover that consists only of open sets of X has finite subcover. Note that compact spaces always have finite covering number. We consider throughout the paper the following fixed compact space: B := {a R" || S C. Rd for fixed 0.
The weak* Topology. Let (x(()) and (X*) denote the space of all nonnegative Borel measures with total mass at most one, and the space of all Borel probability measures on X, respectively. We use (X') to denote the set of all bounded continuous real-valued functions on X. We endow Mai (X)) and (2) with the topology generated by the maps μ + [x fdp for f E (X)) called the weak" topology in functional analysis (Kechris, 2012, Section 17.E), (Bogachev, 2007, Chapter 8). Under this topology, both spaces are standard Borel spaces, and if K. a compact metric space, then (K)), 9 (IC) are compact metrizable (Kechris, 2012, Theorem 17.22). See Appendix E.2 for more details. Under the weak' topology, for a sequence of measures (Ht); and a measure μ. we have convergence 14 + μ if and only if 1xx Idps, - Sx fd for every f E Cz( Similarly, for measures μ and v, we have equality μ if and only if x fdp = Jx fv for every S E Cx))..
Optimal Transport. We will use Optimal Transport to construct a metric between graphs and be- tween graph limits. Unbalanced Optimal Transport (Séjourné al., 2023), also called Unbalanced Earth Mover's ' Distance and Unbalanced Wasserstein Distance, is a distance function defined by the minimal transportation cost between two distributions. The transport is described by coupling between two measures μ,, // on measure spaces X, V/ respectively, i.c., a nonnegative joint mea- sure on X' x y such that (px)~y = μ.. (py) S 1/, given that || S ||i|]. Here, Px and py are the projections from X x y to X' and y i.e., to the first and the second component, respectively, ((A)+ = 7A x )) and (B)) = 7(' x B).
Definition 1 (Unbalanced Optimal Transport/Wasserseeie Distance). Let dX,d) be metric Polish space. The Unbalanced Earth Mover's Distance between two measures u,v E Mai (Xx,),
V Me, ((o.)))(z.))) + +Illa|| - -||lll
OTa(p, = inf TEL(HA))
where ((,, v) is the sei of all couplings of and v.
An intuitive way to think about such couplings is as transportation plans from one distribution of points in a space to another, where the cost given by the overall travel distance.
Product Metric. A product metric d is a metric on the Cartesian product of finitely many metric spaces (X1, dx,xxx),.. ...., (Xn, dx which metrizes the product topology (see Appendix A.4.5 and Ap- pendix A.4.2). Here we use product metrics that are defined as the fn-orrm of the vector of distances measured in n subspaces: d((21,... ..., Ix (y1..... ),.) == [l(dx, y1), dx,, (In. yn. )) 1-
Graph- and Graphon-Signals. A graph G = (V, E') consists of set of nodes (vertices) V = (G) connected by edges E = E{G) C V x V. We denote by A(x)) the set of neighbors of e E V. A graph-signal (alternatively attributed graph) (f. is graph G with node set V = =I....,,N) N), and signal (1)))1 E I1 By that assigns the value f, E By to each node E (1,...,N..
3

---

Published as a conference paper at ICLR 2025
A graphon (Lovász, 2012) may be viewed generalization of graph, where instead of discrete sets of nodes and edges, there are an infinite sets indexed by the sets V(W)= := [0. 1] for nodes and E(W) == 2 [o. 1] for edges. A graphon is defined as measurable symmetric function W F(W) + (0, 1), i.e. W (a,,y) = W(y.r) Each value ((r,, y) describes the probability or intensity of a connection between points and y. The graphon is used to study limit behavior of large graphs (Lovász, 2012). A graphon-signal Levie (2023); Rauchwerger & Levie (2025) is a pair f) where W is a graphon and f V(W) + Bd is a measurable function with respect to the Borel a o-algebra (VV(W)). Note that any graph/graphon without signal can be seen as a graph//rappoon-iiggn signal by simply setting the signal to the constant map, i.e., Vz E V(W): f(x) =c We denote by WCy. the space of all craphon-signalee with signals f: V(W) + Ry
Any graph-signal can be identified with corresponding graphon-signal as follows. Let (G, f) be graph-signal with node set {I...., } and adjaceney matrix A =
Let { IN
with 14- = [(k - 1)/N, be the equipartition of [o, 1] into N intervals. The graphon- signal (w..) = (Wa,fr) induced by (G, f) is defined by Wo(r,y) y) = Eiy= Gzy (x) fill,
and fr(2) = fi where 1,, is the indicator function of the set 4, C [0, 1]. We write fr) and identify any graph-signal with its induced graphon-signal.
- (G.))
Message Passing Neural Networks. Message Pussing Neural Networks (MPNNs) (Gilmer et al., 2017) are class of neural networks designed to process graph-structured data, where nodes may have attributes. Via a message passing process, MPNNs iteratively update each node's features by aggregating (processed) features from its neighbors. Various aggregation methods exist, e.g., summation, averaging, or coordinate-wise maximum. Our focus is on normalized sum aggregation, which in practice achieves comparable performance standard sum aggregation (Levie, 2023).
Computation Trees. Computation trees capture and characterize local structure of graphs by de- scribing the data propagation through neighboring nodes via MPNNs' successive layers (Morris et al., 2019; Arvind et al., 2020; Garg et al., 2020; Xu et al., 2020). Since graphons can be seen as graphs with uncountable number of nodes, the concept of computation trees can be extended in a natural way to graphons, by recursively defining computation trees as objects composed of root node and a distribution of sub-trees induced by the node adjacency of the graphon. The resulting hierarchy of probability measures (Chen et al., 2022; Böker et al., 2023) connects to iterated degree measures. These easily integrate with MPNNs and allow us to identify the finest topology in which MPNNs separate points, which is needed to prove universal approximation theorem for graphons.
Iterated Degree Measures and the 1-WL Test for Graphons. Grebík & Rocha (2021) define iterated degree measures (IDMs) to generalize the 1- 1-Weisfeiler-Leman graph isomorphism test (1- WL) (Appendix 1) and its characterizations to graphons. The 1-WL test performs message passing to uniquely encode (color) the type of computation tree rooted at each node. The collection of trees helps determine graph isomorphism for many pairs of graphs. Initially, the unattributed nodes are indistinguishable, and the test starts with a constant coloring. For graphons, measures replace node colorings, and iterated measures encode computation trees. Analogous to constant colorings, the base measure is defined as M == (*), where * is any value, e.g., O. At level T. 2 0, the tree encoded as the product H. == II Mi over levels, and the space of next-level features as a measure over features of level S L: ML+1
(7t4). We endow HL- with the product topology and M with the weak* topology, as these are natural topologies for product spaces and spaces of measures.
Grebík & Rocha (2021) connect each graphon W with its corresponding node colorings through the maps 7w., [0.1] + HLL, which we call computation iserated degree measures (computation IDMs). This differs from both Grebík & Rocha (2021) and Böker et al. (2023) use the name IDM for infinite sequences of Borel measures. These maps send each graphon node x E [0, 1] to its iterated degree measure, i.e., its coloring. We start with a constant map to a tree that encodes a single color, Tw.o: [0, 1] + 72. The "color" (x) at level L > 0 is a vector, where the j-th entry encodes the color of node x after j coloring iterations. That is, letting (i) be the j-th entry of the vector a (xx, we set 7w,L (i) = "(w.), (i), for every << L. Reflecting the WL-test, the last entry (Z) is a measure recursively defined as (w.r(z) = J
W W(x, -) du for
any subset A C - of the (L- - 1)-th level colors. Namely, we are aggregating colors over the
4

---

Published as a conference paper at ICLR 2025
neighborhood of node according to the connectivity encoded by W(x, -), obtaining a measure over level (L -) colors, analogous to the discrete 1-WL algorithm. Analogously to computation trees, computation IDMs capture the graphons' connectivity. In Section 3, generalize IDMs to additionally incorporate signal information, thus moving from graphon analysis to graphon-signal analysis. We note that this definition is taken from Grebík & Rocha (2021). It differs from the 1-WI. test in Böker et al. (2023), where they do not concatenate all previous colorings.
GRAPHON-SIGNAL METRICS THROUGH ITERATED DEGREE MEASURES
To analyze expressivity and generalization, we need to define an appropriate metric between at- tributed graphons. Hence, in this section, we first extend the IDM definition in Section 2 to capture both signal values and graphon topology. We then define distributions of iterated degree measures (DIDMs) and metrics between IDMs and DIDMs. These induce distance measures the space of attributed praphs/graphons, which are polynomial time computable. We essentially transition from computation trees that capture only graphon structure computation trees that capture attributes as well. In Section 4, we will see how this allows us to analyze MPNNs on attributed graphs.
Attributad
Optimal
Graphs
Attributed
transport
Similarity
Graphons similarity
between ilerated
degree
Figure 1:
Measuring similarity between graph-signale on the left is translated into measuring similar- ity between graphon-signal and, lastly, to computing optimal transport between two IDMs, which comprise in the figure a signal value and a distribution over signal values induced by the graphon's adjacency. Edges colors depict edge weights and node colors depict signal values.
Computation IDMs and Distributions of IDMs. We first expand the definitions of IDM and computation IDM of Section 2 from unattributed attributed graphons. In hindsight, our approach is in line with an idea outlined in Section 5 of Böker et al. (2023). We change the IDMs' base space from one point space, {+]. ). the space of node attributes By far R ||ж||a S < R (for fixed > 0). Thus, incorporating signal values inherently into the IDMs structure. Explicitly, define the space of iterated degree measures of order-Z. L., HL, inductively by first defining M Bd Then, for every L 0, let H² Il M and M4+1 =?tth where the topologies of H and M are the product and the weak" topology, respectively. distributions of iterated degree measures (DIDMs) of order-L. We denote by pr.j H- + Hi and Pt H1 -> _ the canonical projections where j S I, < cc. Recall that (z) refers to the j-th entry of the vector a(x). Next, we define graphon-sight 1-WI. analog.
call P(H))) the space of
[0, 1] be the interval with the standard Borel a-algebra B and let (W, f) be Definition We define 7(W.)), : [0,1] + H to be the map ((..),,lz) == f(x) for every E [0, 1]. Inductively, we define 7(W.f),44 [0, + H such that
graphon-signal.
(a) (w..).+H1)) = (w.n) for every j S I. and (b) (W))) + 1)(A) = I ( (A) W(x,
du, whenever A C H4 is Borel set.
Finally, for every L No. let L' be the fush-forward of X via (W, We call YWW,).L a computation iterated degree measure (computation IDM) of order-L and I L(..).L distribution of computation iterated degree measures (computation DIDM) of order-L.
In Appendix E.2 we prove that the spaces of IDMs and DIDMs are compact, which, together with the continuity of MPNNs (Theorem 13), and the separation power of MPNNs (Theorem 14), allows us to use the Stone- Weierstrass theorem (Appendix A.5) to show universality and to use uniform Monte Carlo estimation compute generalization bound for MPNNs.
5

---

Published as a conference paper at ICLR 2025
Theorem 3. The spaces HP and (H) are compact spaces for any L E No-
The proof of Theorem 3 inductively uses the fact that given any compact space K, the spaces (AC and (XC) endowed with the weak" topology are compact metrizable spaces. Tychonoff's theorem, which states that the product of any collection of compact topological spaces is compact with respect to the product topology, completes the argument.
DIDM Mover's Distance. Next, we define a distance between graphons, viewed as distributions of computation IDMs. Inspired by the tree mover's distance of Chuang & Jegelka (2022), do this by optimal transport with a ground metric between IDMs, i.e., trees, as both computational IDMs and trees can be seen represent the MPNNs' computational procees. Thus, we explicitly construct metric that metrizes the topology of Ht. We define the IDM distance of order-0 on M = 7t = B,, for p E No. by dIDM ==
I|.- Ull2. and denote by OT the optimal transport distance on M = M11 ).. We define dfMM recursively as the product metric on 7 = Is M when the distance M Mzi(H(-1) for < I. is OT IDM Explicitly written,
(FDM(H,V) := |110 roll2 2 プラ= OT di (1))))) 11100 voll2
: >>0 L =0 0
for for (1=) (uz)fzo HLL The next theorem states that, for every E No. both the IDM distance diDM and optimal transport distance OT dfo fit naturally to the topologies of IDMs and DIDMs defined in Section 2.
Theorem 4. Let L E No. The metrics dinw on Ht and OT dio (H))) and M (gg(Ht) are well-defined. Moreover, OT diss metrizes the weak" topologies of (Hll) and 20 (HL).
We now use the distance between IDMs to define a distance between graphons, viewed as distribu- tions of computation IDMs. Specifically, we define the DIDM Mover's Distance between graphons as the optimal transport cost between their DIDMs, with ground metric df
Definition (DIDM Mover's Distance). Given two graphon-signai (Wa, fa), (Wo, fo) and L Z 1, the DIDM Mover's Distance between (Wa, fa) and (W,, fo) is defined as
(a), (Wb, fb)) == OT di (T(Wa.fa). I (Wo.f))...
Intuitively, TIDM is the minimum cost required to transport node-wise IDMs from one graphon to another.
Given two attributed graphs, (G, and (H,g). the DIDM mover's distance, (BIDM((G,)) (H, as shown next.
(bDDa(WW fr), fe)) can be computed in polynomial time,
Theorem 6. For any fixed L No. &IDM between any two graph-signals (G.f) and (H, g) can be computed in time polynomial in I and the size of G and H, namely O No No log(N)), where N max (H))).
The theorem is proven in Appendix L.2 with the following reasoning. While &IDM is defined using the induced graphon, it is computed directly on the graph. Moreover, we do use a data-structure for representing IDMs directly. Instead, each time, we compute cost matrices derived from the cost matrices of the previous layer, avoiding explicit representations of the IDMs. We first compute cost matrix Do. containing the Lg distances between the nodes' attributes, and then use it as cost matrix of an OT problem. We repeatedly solve OT problems based on the previous cost matrix and the adjacency matrices of the graphs using linear programming and sum the results with the previous cost matrix to get the next cost matrix. Each OT problem is solved in O(N3 O(N3 log(N)) time (Flamary et al., 2021; Chapel et al., 2020). At each step 3 log(N)) per step. After computing Dr. we use it to solve a single OT problem between two uniform distributions, one over V(G) and the other over V(H) to get di value, which again takes ( Jog(N)). Hence, the total computation time is O(L N N log)))). In Section 5, evaluate the DIDM Mover's Distance empirically.
solve N2 problems. This means O(N2.
Alternative Approach. For the sake of completeness, we present in Appendix L the Prokhorov metric, which can be used for defining alternative metrics to optimal transport which metrize HP_

---

Published as a conference paper at ICLR 2025
similarly to the constuction of Böker et al. (2023). All of our results can be equivalently stated with the alternative metrics.
4 MPNNS AND THEIR RELATION TO DIDM MOVER'S S DISTANCE
We next integrate MPNNs into our framework and define a general message passing scheme for computing features of attributed graphons, which generalizes standard graph MPNNs. Equivalently, by defining aggregated features via IDMs and DIDMs, we can define the MPNN directly on IDMs and DIDMs. In Appendix G, we show the equivalence between MPNNS defined on graphon-signals and MPNNs defined on IDMs and DIDMs. By analyzing MPNNs on IDMS and DIDMs, we prove Theorem 13 and Theorem 14, which state that two graphon signals are close to each other in our metrics if and only if the two outputs of any MPNN on the two graphon-signals are close-by in L2 distance.
An MPNN consists of feature initialization, which is learnable Lipschitz continuous mapping <p(0) : IP + IRd, followed by L layers, each of which consists of two steps: a message passing layer (MPL) that aggregates neighborhood information, followed by a node-wise update layer. Here, we assume the MPL to be normalized sum pooling when applied on graph-signals or graphon-sigh sighass. The update layer consists of a learnable Lipschitz continuous mapping sp(t) ; [R2 + RR where 0 t S L is the layer's index. Each layer computes a representation of each node. For predictions on the full graph, a readout layer aggregates the node representations into a single graph feature and transforms it by a learnable Lipschitz function vp Rdd2 + IRd for some E Ng. For the readout, with use average pooling.
Definition 7 (MPNN Model). Let L E No and p. do....,, .I. E No. We call any collection 10 (f) of Lipschitz continuous functions (l() Bp" Rd and wlt) RR2 + R for ists L, L-layer MPNN model, and call (t update functions. For Lipschitz continuous F + R", we call the tuple (4, 1) an MPNN model with readout, where & is called a readout function. We call L, the depth of the MPNN, p the input feature dimension, do....;d, dr the hidden feature dimensions, and d the output feature dimension.
An MPNN model processes graph-signan as a function as follows.
Definition 8 (MPNNs graph-signals). Let (1p, 1b) be L-layer MPNN model with readout, and (G, be a graph-signal where f : V(G) + BP. The application of the MPNN on (G, is defined follows: initialize (0) = (0)( (f(-)) and compute the hidden node representations
VVG)) + IR at layer t, with 1 1 S L and the graph-level output & E Rd by
0l!) == (() (o!
1 [VG
Σ
o and :: vt
1
Σ DEV(G)
[VG)
(o)
To clarify the dependence of g and @ on &o and (G,f), we often denote s(w) or s(1p G, f) and ((p, 3) or ((G,, 1b, G. f). Here, directly compatible with the graphon version. To extend this MPNN to graphons, we transition from discrete set of nodes to a continuous set by converting the normalized sum into an integral.
normalized sum aggregation neighborhoods to be
Definition 9 (MPNNs on Graphon-Signals), Let (4,, v) be an L-layer MPNN model with readout, and (W.fl f) be paphon-signal where f V(W) 1 Br. The application of the MPNN on (W, f) is defined as follows: initialize ( == (f(-)) and compute the hidden node representations (1)) :VW + gd: at layer t, with 1 St & L and the graphon- output B = Rd by
10 = (()) (14 (11-1) 0..1
W(x, W(a,0)) -
and 3: + ( 0.11 1())
As before, often denote (( or i(p, W, () and 3(p,, v) or 3(p, t W.f). The following definition generalizes MPNNs to IDMs and DIDMs using the canonical projections PL.: H + Hi and PL H + M where < L < 00.
Definition 10 (MPNNs on IDMs and DIDMs). Let (4p, 1) be an L-layer MPNN model with readout.
The application of the MPNN IDMs and DIDMs is defined as follows: initialize ( (-),
7

---

Published as a conference paper at ICLR 2025
and compute the hidden IDM representations 6 H² RR on any order-I IDM H', and the DIDM-level putput 3) E IR on an order-L DIDM v E (HL.), by
6 = p01t (1pt.
( 1(7)'
/ Ine-1 6th bl=")d((7))
and
5 5=
bl
v., v). We name MPNNs' hidden representations and outputs features. MPNNs on IDMs and DIDMs are canonical extensions of MPNNs on graphon- signals as follows.
We also denote b (gp); ()) and (1p, e)) or ()p,
Lemma 11. Let (W,f) be graphon-signal and (e, 4) an L-layer MPNN model with readout.
Then, given the computation IDMs (row.),,) and DIDM T (.W.).L. we have that f(ip, W, W b(()) (9)
(ww.).t)) for any & [L], [0, 1). Similarly, ((p, 16, W, J) 5y b, P(w.D.L).
That is, cupphon-signabe hidden representations are computed through their computation IDMs and DIDMs, i.e. the product of the graphon-signals I-WL algorithm (Definition 2). Similarly, graph- signals' hidden representations are computed through their induced graphon-signal
Corollary 12 is consequence of Theorem 15, one of our main results, presented in Section 5. It reveals a strong connection between MPNN features and the weak" topology of (HL))
Corollary 12. Let L E Ny and d > 0 be fixed. Let v E (HH)) and (vt); be sequence with Vs E (H.)). Then, V/ - V if and only if h1 v) - Shlp, 2b, v) for all L-layer MPNN models (p with readout function functionn vb: R + Rd
We now present Theorem 13 and Theorem 14. Together, they establishe a bidirectional fundamental connection between metries and the outputs of all possible MPNNs, where the second direction is phrased as a delta-epsilon relation. Specifically, Theorem 13 states a Lipschitz bound for MPNNs with respect to the IDM and DIDM mover's distance. This quantifies stability as in the finite case in Chuang & Jegelka (2022).
Theorem 13.
Let yp be L-layer MPNN model. Then there exists a constant Cip that depends only on the number of layers L and the Lipschitz constants of the update functions, such that
[h(sp, ai) - h/ () la S &Co (..M(a.
for all ar, E.BEH 4 has readout function vh, then, for all p., v E (HH)), there exists a constant O(ppi) that depends only on Cip and the Lipschitz constant of the model's 's readout function,, such that
(sp, 1h, n1) 5(1,, v. 2)2 I C(ppa) OT d (p.v).
In analysis, Theorem 13 is vital for the generalization analysis in Section 5. The following theorem is roughly the "topological converse" of Theorem 13, and is based on Corollary 12.
Theorem 14. Let d > be fixed. For every s O, there are L No. C> O, and 8 > O such that, for all DIDMs μ. v E (HL", if (1,),,, V. 519 w. v) < holds for every L-layer MPNN model ip with readout function RRd Hd when C(p,v) S C, then OT d/ose (H,2) S
Note that the constants L, C, and 5 are independent of the DIDMs μ and The combination of Theorem 13 and Theorem 14 implies that we can not only bound MPNNs output perturbations with OT uffass but also estimate closeness in OT OT& di via MPNNs output closeness.
Empirical Evaluation. As proof of concept, we empirically test the correlation between & and distance in the output of MPNNs. For the graphs, we use stochastic block models (SBMs), which are random graph generative models. We generated a sequence of 50 random graphs [G,)49 each with 30 vertices. Each graph generated from a SBM with two blocks (communities) of size 15 with p 0.5 and
0.1 + 0.4i/49 probabilities of having an edge between each pair of nodes from the same block different blocks, respectively. We denote model. We plot 6% (G;; G) against distance in the output of randomly initialized MPNNs. We conducted the experiment twice, once with a constant feature for all nodes and once with a signal which has different constant value each community of the graph. Each of these two values is randomly sampled from a uniform distribution over [0, 1]. Figure 2 shows the results when varying the hidden dimension of the GNN. The results show strong correlation between input distance and GNN output distance. More empirical results are presented in Appendix M. The code is available at https: : ///itttbs com/ levi 676/GNN G E-U.
G49, which is an Rénös-Rényi
8

---

Published as a conference paper at ICLR 2025
GiN |2 laye: di
(2 layer, 0 c)
GIN 12 layer. 10
GIN (2-2yer, 1:d)
GIN (2-layar, B-C)
GIN (2-layer, 164)
0.5
0.50
0.23
36. (Alayar 1-0)
6C Oskayer B-4
CC P-aayer 16-1)
CC Dlayer, 1-d)
GC (Ilbyor,, 8-0
GC (24aver: 16:i
0.75
022
00
0.5
10. 0.5 3.0 0.0
0.5
1.0 0.0
0.5 1.0
Figure 2: Correlation between BIDM and distance in the output of randomly initialized MPNN. convergent sequence of graphs. The graphs are generated by stochastic block models. In the six leftmost figures the signal is constant. In the six rightmost figures, the signal values are constant each graph's s community. Each signal value is sampled from a uniform distribution over [0, 1].
5 THEORETICAL APPLICATIONS
Next, state the main theoretical applications of the compactness of the space of attributed graphs and the Lipschitz and separation power of MPNNs with respect to DIDM mover's ' distance. First, we show universal approximation theorem for MPNNs on IDMs and DIDMs, which means that MPNNs can approximate any continuous function on IDMs and DIDMs. This entails universal approximation of MPNNS on attributed graphs/graphons as well, generalizing the results of Böker et al. (2023) to attributed graphs. Second, we introduce uniform generalization bound for MPNNs.
He Rd is an L-layer MPNN model) S C(H., Rd),, where C(H., Rd) is the set of all contin- uous functions, He T2 Similarly we define the set NNd, == (5(p, v. (HL))
Universal Approximation.
We define the set Nr. == (b(r)
1 v) is L-layer MPNN model with readout) C CH
Theorem 15 (Universal Approximation). Let L E No. Then, the set N2, is uniformly dense in C(HL, R) and the set NN7, is uniformly dense in C( C(P(H)) IR.
Combining Theorem 15 with Lemma 11 leads in a very straightforward way to universal approxima- tion of continuous functions from graph-signals to graph-signals embeddings. Our theory implies that we use all MPNNs, we can distinguish between all attributed graphs with positive graph distance (since they could take different function values). Indeed, Table and 3 in Böker et al. (2023) illustrate that using sufficiently many MPNNs provides enough discriminative power for graph classification tasks on both attributed and unattributed graphs. Our results supply the theoret- ical background for their experiments with attributed graphs.
Note that Theorem 15 states that any continuous function from DIDMs to scalars can be approxi- mated by MPNN on DIDMs. To infer universal approximation result for functions from graph- signals to vectors we emphasize the following considerations. Define the set A (WCC;) := (8 -)) W + Rd [ vb) is an L-llaee MPNN model with readout]. First, note that the space of computation DIDMs, ((w.),L (w.rt (IDM) in view of Theorem 64. Indeed, there are DIDMs that do not come from any graphon- signal, and closed strict subset cannot be dense. So, the space of DIDMs of graph-signals is also not dense. Hence, Theorem 15 does not imply that any continuous function (w.r.t )DDD)) from graph- signal to vector can be approximated using an MPNN model. Rather, any function on graph-signals that can be extended to continuous function on DIDMs can be approximated can be approximated using an MPNN model, which is a weaker form of universality. Fortunately, we can directly prove universal approximation theorem directly for the space W WLd which in terms gives a universal ap- proximation theorem for continuous functions from graph-signals to vectors by a density argument. For this, in Appendix 1.3 we prove that signals are dense WCF w.r.t. dDDM-
is strict subset of 3 (H++), which is not dense
Theorem 16. Let L E No. Then. the set NN is uniformly dense in C(WC,, R).
Generalization Bounds for MPNNs. Consider K K-class classification, i.c., the data is drawn from distribution (X (0, 1)K E, 7), where E is the Borel o-algebra and is probability mea-

---

Published as a conference paper at ICLR 2025
sure, where d' is either (HH)).. OT OTdipal or (WC,, &IDM), and E is a Lipschitz loss fune- tion with a Lipschitz constant Ce. Define the formal bias of a function f : IR4, + Rd: to be (O)]l (Maskey et al., 2022) and denote the smallest Lipschitz constants of f by [l, (see Ap- pendix A.12). Fix L E N and AI, A2 > O. Let e be the set of all L-layer MPNN models with readout ((1(1)) xE(2),.)) 2)) such that the Lipschitz constants || and I| are bounded by A and the formal biases || (0)(l ||2 and [|x5(0]]22 are bounded by A2. Let Lip(X', C) be the set of all continuous functions/ f X + udde with bounded Lipschitz constants |lffll, S C and bounded norms [I S B. In Appendix K.3, we show that there exist Ce, Bg > 0 that depend on L, A1, A2 such that θ C Lip(X, Ce, Ba). As result, if we prove generalization bound for the hypothesis class Lip Be) the bound would also be satisfied for the hypothesis class θ. The following generalization theorem uses techniques from Levie (2023), deriving generalization bounds for Lip- schitz continuous functions over domains with finite covering. For us, both the spaces of DIDMs and of suphon-signalle have finite covering numbers as they are compact, and MPNNs are Lipschtiz over these domains. The technique is also similar to robustness-tyy typp bounds (Xu & Mannor, 2012).
Theorem 17 (MPNN generalization theorem). Consider the above classification setting with X being either (9H(H)), OT ofoos) or (WL,, bIDDa)- Let C == C& max(Ce,1) 1), B Ce(Be + 1) + (0, 0)), and { be independent random samples from the data distribution (X' x (0,1) T). Then, for every p > O, there exists an event UP C (X x {0, 1}K}NN regarding the choice xf = (X1..... .x.....x)).. ). with probability T" ((())) 2 1 - p. in which for every function Mx in the hypothesis class Lip(X, Ce. Be), we have
RR(Dxx) -R (2Ix) (N) 2C
1
1 1 (1 (Tog(2/0))
V2
where E(e) = x(O) -(0'log(((e))) is the covering number of the compact space X x (0, 13k and g-1 is the inverse function E.
Theorem 17 means that when minimizing the empirical risk on a training set drawn from the data distribution, the statistical risk guaranteed to be close to the empirical risk in high probability, where no assumptions on the data and number of parameters of the MPNN is required (the only as- sumption is Lipschitz continuity of the update and readout functions). Indeed, the term g-1 (N/2C) in Equation (I) approaches zero when we take N to infinity. Moreover, since the space X' x (0, 1 is compact (Theorem 26), for X E
{ (HL)), W.C, its covering number is finite.
6 DISCUSSION
MPNNs were historically defined constructively, as specific types of computations on graphs, with- out a proper theory of MPNN function spaces over properly defined domains. Our work provides a functional basis for MPNNs, which leads to machine learning results like universal approximation and generalization for attributed graphs.
The only sta-stadd part of our construction is the choice of normalized sum aggregation in our MPNN architecture, while most MPNNs use sum, mean, or maximum aggregation. We justify this choice as follows. First, experimentally, in Böker et al., 2023, Tables 1, 3 and Levie, 2023, Table 2, it is shown that MPNNs with normalized sum aggregation generalize well, compared to MPNNs with sum aggregation. We believe that this is the case since in most datasets most graphs have roughly the same order of vertices. Hence, the normalization by N2 is of a constant order of magnitude and can be swallowed by the weights of the MPNN, mimicking the behavior of an MPNN with sum aggregation. Future work may explore extensions of our theory to other aggregation schemes (see Appendix A.3 and Appendix C.2 for more details).
Our theory is meaningful only for dense graphs, as sparse graphs are always considered close to the empty graph under our metrics (see Appendix 1) Future work may focus on deriving fine-grained expressivity analyses for sparse attributed graphs. Moreover, the current theory is designed around graph level tasks. However, potentially, one can also use IDMs to study node level tasks, as IDMs represent the computational structure corresponding to each node. For example, one can potentially use our construction for analyzing the stability of node-level GNNs to perturbations to the structure of the graph and its features, where the magnitude of the perturbation is modeled via IDM distance. Lastly, since our proofs are specific to MPNNs with normalized sum aggregation, future research could provide extension of our theory to other aggregation functions.
10

---

Published as a conference paper at ICLR 2025
7 ETHICS STATEMENT
As this paper mainly focuses on theory, and uses only datasets that do not involve humans or animals, does not present an apparent ethical problem.
REPRODUCIBILITY STATEMENT
We hereby declare that the proofs pendix. The code used in this paper will be available upon the acceptance of this paper, with full explanation on how to perform all the experiments present in this article. This means that all the experiments presented both in the main article and the appendix could be reproduced.
theorems presented the article are available in the ap-
ACKNOWLEDGMENTS
This research was 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), by the Israel Science Foundation (ISF grant No. 1937/23), and by an Alexander von Humboldt professorship.
REFERENCES
Miklós Abért, Andreas Berthold Thom, and Bálint Virág. Benjamini-schramm convergence and pointwise convergence of the spectral measure. Arxiv, 2014.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sci- ences, volume 113, pages 42-59. Elsevier, 2020.
Kenneth Atz, Francesca Grisoni, and Gisbert Schneider. Geometric deep learning on molec- ular representations. Nature Machine Intelligence, 3(12):1023-1022 2021. doi: 10.1038
>42256-001-004418-8
Patrick Billingsley. Probability and Measure. A Intes-interecceecee publication. publiccaoon Wiley, New York u.a., third edition edition, 1995. ISBN 0471007102.
Vladimir I. Bogachev. Measure Theory. Springer Science & Business Media, 2007.
Christian Borgs, Jennifer Chayes, Henry Cohn, and Yufei Zhao. 1" theory of sparse graph convergence Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society, 372, 201 4a. doi: 10. 10.109//ran/5533.
Christian Borgs, Jennifer Chayes, Henry Cohn, and Yufei Zhao. An 1" theory of sparse graph convergence ii: Ld convergence, quotients, and right convergence. The Annals of Probability, 46, 08 2014b. doi: 10. 10.1214/17-A0P113
Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López. Leslie O'Bray, and Bastian Rieck. Graph kemels:: State-of-the-art and future challenges. Found. Trends Mach. Learn., 13(5-6): 531-712, December 2020. ISSN 1935-8237.
Horst Bunke and Kim Shearer. A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters, 19(3):255-259, 1998. ISSN 0167-8655. doi: https://doi.org/10.uu 501167-8555(77000199777
Béla and Oliver Riordan. Sparse graphs: Metrics and random models. Random Structures & Algo- rithms, 39, 08 2011. doi: 10. 10022/sa..2334.
Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, and Christopher Morris. Fine-grained expressivity of graph neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2023.
11

---

Published as a conference paper at ICLR 2025
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24:1-61, 2023.
Laetitia Chapel, Mokhtar Z. Alaya, and Gilles Gasso. Partial optimal transport with applications positive-umlabeled learning. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Samantha Chen, Sunhyuk Lim, Facundo Memoli, Zhengchao Wan, and Yusu Wang- Weisfeiler- Kamalika Chaudhuri, Stefanie Jegelka, Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Int. Conference on Machine Learning (ICML), volume 162 Proceedings of Machine Learning Research, pp. 3371-3416. PMLR, 17-23 Jul 2022.
Lehman meets
Samantha Chen, Sunhyuk Lim, Facundo Memoli, Zhengchao Wan, and Yusu Wang. The Weisfeiler- Lehman distance: Reinterpretation and connection with GNNs. In Timothy Doster, Tegan Emer- son, Henry Kvinge, Nina Miolane, Mathilde Papillon, Bastian Rieck, and Sophia Sanborn (eds.), Proceedings of 2nd Annual Workshop Topology, Algebra, and Geometry in Machine Learning (TAG-ML), volume 221 of Proceedings of Machine Learning Research, pp. 404 425. PMLR, 28 Jul 2023.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems (NeurIPS), 2020.
Ching-Yo Chong-Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and sta- bility of graph neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Wenqi Fan, Yao Ma. Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural net- works for social recommendation. In The World Wide Web Conference, WWW '19, pp. 417-426, New York, NY. USA. 2019. Association for Computing Machinery. ISBN 978 1450366748 doi: URL btttps:///ole http::///oiooog//////// www.oo.ggoooooooooooooooo 000.001111///31500 33////3388588838 3313488
10.1145/3308558.33
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanis- las Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy. Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica Sutherland, Romain Tavenard, Alexander Tong. and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78): 1-8, 2021.
A. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19 (2):175-220, Feb. 1999.
U. Garefa-Palomares and M. Evarist Giné. On the linear programming approach to the optimality property of prokhorov's distance. Journal of Mathematical Analysis and Applications, 60(3): 596-600, Oct 1977.
B. Garel and J.-C. Massé, Calculation of the prokhorov distance by optimal quantization and maxi- mum flow. AStA Advances in Statistical Analysis, 93(1):73-88, March 2009.
Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In Int. Conference Machine Learning (ICML), ICML'20. Jor.. 2020.
J. Gilmer, S. S. Schoenholz, F. Riley, O. Vinyals. and G. E. Dahl. Neural message passing for quantum chemistry. Int. Conference on Machine Learning (ICML), pp. 1263-1272, 2017.
Jan Grebík and Israel Rocha. Fractional isomorphism of graphons. arXiv: 0ath:/999.0000 /909904/299 2021.
Hamed Hatami, László Lovász, and Balázs Szegedy. Limits of bocally-globally convergent graph sequences. Geometric and Functional AnalyisnalAnallsss,, 24(1):269-29) 296, February 2014, ISSN 1420-8970. doi: 10. 10.10077.00039-01440338..
12

---

Published as a conference paper at ICLR 2025
Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.07697, 2022.
Feng Ji, Xingchao Jian, and Wee Peng Tay. Modeling sparse graph sequences and signals using generalized graphons. IEEE Transactions on Signal Processing, PP:1-16, 01 2024. doi: 10.1109/ TSSP22024.4822550
Xingchao Jian, Feng Ji, and Wee Peng Tay. Generalized graphon process: Convergence of graph frequencies in stretched cut distance. Arxiv, 09 2023. doi: 10.48550/4aXX12230005566..
Alexander S. Kechris. Classical Descriptive Set Theory. Graduate Texts in Mathematics. Springer New York; 2012. ISBN 9781461241904.
Ryan Keisler. Forecasting global weather with graph neural networks. NrXiv:2202.07555..22 2022.
arXiv preprint
Ron Levie. A graphon-signal analysis of graph neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2023.
Hongkang Li, M. Wang. Sijia Liu, Pin-Yu Chen, and Jinjun Xiong. Generalization guarantee of training graph convolutional networks with graph topology sampling. In International Conference on Machine Learning, 2022.
R. Liao, R. Urtasun, and Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. Int. Conf. on Learning Representations (ICIR), 2021a.
R. Liao, Urtasun, and R. Zemel. PAC-bayesian approach to generalization bounds for graph neural networks. In Int. Conf. Learning Representations (ICLR), 2021b.
L. Lovász. Large Networks and Graph Limits, volume 60 Colloquium Publications. American Mathematical Society, 2012.
L. Lovász. Compact graphings. Acta Mathematica Hungarica, 161(():185-196, June 2020. ISSN 1588-2632. doi: 10.10077/114474-019-000111
Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks large random graphs. In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc., 2022.
Sohir Maskey, Gitta Kutyniok, and Ron Levie. Generalization bounds for message passing networks on mixture of graphons, 2024.
C. Morris, F. Geerts, Tönshoff, and M. Grohe. WI meet ve. In Int. Conference Machine Learning (ICML). Proceedings of Machine Learning Research (PMLR), 2023.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. The Thirty-hird AAA! Conference on Artificial Intelligence (AAAI-19), 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, Ismail IIkan Ceylan, Ron Levie, Derek Lim, Michael M. Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future direc- tions in the theory of graph machine learning. Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller. Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceed- ings of the 41st International Conference on Machine Learning, volume 235 Proceedings of Machine Learning Research, pp. 36294-36307. PMLR, 21-27 Jul 2024.
Facundo Mémoli. Gromov wasserseen distances and the metric approach to object matching. Foun- dations of Computational Mathematics, 11:417-487, 08 201 1. doi: 10. 1007/s 10208-011 12000001--093-55
13

---

Published as a conference paper at ICLR 2025
Kenta Oono and Taiji Suzuki. Optimization and generalization analysis of transduction through gra- dient boosting and application to multi-scale graph neural networks. H. Larochelle, M. Ran- zato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 18917-18930. Curran Associates, Inc., 2020.
O. Pele and M. Werman. A linear time histogram metric for improved sift matching. In Computer Vision-ECCV 2008, pp. 495-508. Springer, 2008. ISBN 118-3-540-88660-17
Ofir Pele and Michael Werman. Fast and robust earth mover's distances. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 460-467. IEEE, September 2009.
Yu. V. Prokhorov. Convergence of random processes and limit theorems in probability theory. The- ory of Probability & Its Applications, 1(2):2, 9, 10, 34, 1956. doi: 10.1137/1101016
Chendi Qian, Didier Chételat, and Christopher Morris. Exploring the power of graph neural networks in solving linear optimization problems. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 1440. PMLR, 02-04 May 2024.
Levi Rauchwerger and Ron Levie. A note on graphon-signal analysis of graph neural networks. arXiv preprint, 2025.
W. Rudin. Principles of mathematical analysis. McGraw-Hill, New York-Auckuan-Diiseeloorf 1976.
W. Rudin, Real and Complex Analysis. McGraw-Hill, New York, May 1986.
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph neural networks: Architectures, stabil- ity, and transferability. Proceedings of the IEEE. 109(5):660-622, 2021. doi: 10.1109/IPROC. 2021.3055400.
Alberto Sanfeliu and King-Sun Fu. distance measure between attributed relational graphs for pattern recognition. IEEE Transactions Systems, Man, and Cybernetics, SMC-13(3)3333-333 1983. doi: 10. 00.1099/SMC..198....33
G. Schay. Nearest random variables with given distributions. The Annals of Probability, 2(1): 163-166, 1974.
Bernhard Schmitzer and Christoph Schnörr. Modelling convex shape priors and matching based on the aesomov-wwsserseee distance. Journal of Mathematical Imaging and Vision, 46(1):143-159, 2013.
Thibault Séjourné, Gabriel Peyré, and François-Xavier Vialard. Unbalanced optimal transport, from theory to numerics. arXiv preprint arXiv:2211.08775. 2023, doi: 11.48550/rxx..2211..0777
Shai Shalev-Shwarzz and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014. ISBN 978-1-10-70551335
Jonathan M. Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M. Donghia, Craig R. MacNair, Shawn French, Lindsey A. Carfrae, Zohar Bloom-Ackermann, Vie- toria M. Tran, Anush Chiappino-Pepe, Ahmed H. Badran, Ian W. Andrews, Emma J. Chory, George M. Church, Eric D. Brown, Tommi Jaakkola, Regina Barzilay, and James J. Collins. A deep learning approach to antibiotic discovery. Cell, 180(4)6688772.c11. 2020. ISSN 0092- 8674. doi: https://doi.org orro/ioor//// 10. (0166f.cell..220..o
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. The power of recursion in graph neural networks for counting substructures. In Francisco Ruiz, Jennifer Dy. and Jan Willem van de Meent (eds.), Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 Proceedings of Machine Learning Research, pp. 11023-11044 PMLR, 25-27 Apr 2023.
14

---

Published as a conference paper at ICLR 2025
Huayi Tang and Yong Liu. Towards understanding the generalization of graph neural networks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.). Int. Conference Machine Learning (ICML), volume 202 of Proceed- ings of Machine Learning Research, pp. 33679-33719. PMIR, 23-29 Jul 2023.
Vayer Titouan, Nicolas Courty, Romain Tavenard, Chapel Laetitia, and Rémi Flamary. Optimal transport for structured data with application on graphs. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Int. Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 0275-6280 PMLR, 09-15 Jun 2019.
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works. The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2019.
S.V.N. Vishwanathan, Nicol N. Schraudolph, Risi Kondor, and Karsten M. Borgwardt. Graph ker- nels. Journal of Machine Learning Research, 1140)):201-1222, 2010.
Yuyang Wang, Zijie Li, and Amir Barati Farimani. Graph Neural Networks for Molecules, pp. 21- 66. Springer International Publishing, Cham, 2023. ISBN 978-3-031-37196-7 doi: 10.1007/ 978-3-033--37196-722
Huan Xu and Shic Mannor. Robustness and generalization. Conference on Learning Theory (COLT), 86(3):391-477 2012. ISSN 1573-0565. doi: 10. 10.11007/.-0994--11-556--
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Inf. Conf. on Learning Representations (ICI.R), 2019.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. Int. Conf. on Learning Representations (ICI.R) 2020.
Yi Yang, Hejie Cui, and Carl Yang. PTGB: Pre-train graph neural networks for brain network analysis. Conference on Health, Inference, and Learning (CHIL), 2023.
Gilad Yehudai, Ethan Fetaya, Eli Meir, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. Int. Conference on Machine Learning (ICML), 2020.
Bohang Zhang, Guhao Feng. Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hier- archy for subgraph GNNs via subgraph weisfeiler-lehman tests. In Int. Conference on Machine Learning (ICML), ICML'23, JMLR.org, 2023a.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. Int. Conf. on Learning Representations (ICLR), 2023b.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for GNN expressiveness. Int. Conf. on Learning Representa- tions (ICLR), 2024a.
Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the expressive power of spectral invariant graph neural networks. ICMI. 2024, 2024b.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al Open, 1:57-81, 2020. ISSN 2666-6510. doi: http:///oi.orr//1. 101 a016/j.aiopen.2000 2021.... 001.
Ágnes Backhausz and Balázs Szegedy. Action convergence of operators and graphs. Canadian Journal of Mathematics, 74:1-52, 09 2020. doi: 104/33/000084442200000..
15

---

Published as a conference paper at ICLR 2025
A
ADDITIONAL BACKGROUND
We provide here additional background.
A.1 WEISFEILER LEMAN GRAPH ISOMORPHISM TEST ON GRAPHS
The Weisfeiler-Lemant (WL-1) test, which was developed by Boris Weisfeiler and Andrei Leman, also known as color refinement, is an algorithm which aimed to effectively approximate the solution of the graph isomorphism problem.As graph isomorphism problem is not known to be solvable in polynomial time, the algorithm cannot distinguish all non-isomorphic graphs.
Given a graph G = (V, E) with initial labeling Lo V + No (also referred to as coloring), composed of V, the set of nodes and E V V, the set of edges, the WL-1 algorithm iteratively updates the nodes labels based on the labels of neighboring vertices.
Definition 18 WWeiseeiler-Lean Iteration). Given a graph G (V, E) with an initial labeling Lo + No, each iteration t >> 0 of the WL algorithm computes new labeling Lt follows:
L₁(1) Hash (I+-1(U), (L)- E
where (v) denotes the neighbors of vertex v, and Hash is injective,uunction mapping the previ- ous label and multiset of neighbor labels to a new unique label.
This process runs on two graphs in parallel and continues on until a stable labeling of one of the two graphs is achieved, meaning that for some E No the label of one of the graphs doesn't change, or discrepancy found between the label of the two graphs being compared. One of these two events is always reached.
A.2 MESSAGE PASSING NEURAL NETWORKS ON GRAPHS
Message Passing Neural Networks (MPNNs) Gilmer et al. (2017) are neural networks class de- signed to process graph-structured data with and without attributes. Given a graph G (V, E), and graph-staphhhhha
a signal f V + R² (in the case of graph without attributes the signal is the constant function f(v) 1, MPNNs iteratively update node embeddings through the exchange of messages between nodes through edges. We restate here Definition 7.
Definition 7 (MPNN Model). Let L E No and di. E No- We call any collection P (L) of Lipschitz continuous functions pp(0) 12 Rd, and (plt) -gdd- + Rd for ist an L-layer MPNN model, and call (0 update functions. For Lipschitz continuous 3 R + Rd, we call the tuple (4, w) an MPNN model with readout, where & is called a readout function. We call the depth of the MPNN. p the input feature dimension, do...., dr, the hidden feature dimensions, and d the output feature dimension.
Let & be an L-layer MPNN model. We recall that (v) denotes the set of neighbors of node v. Each node u E V starts with initial feature vector (())) f(v), which updated iteratively through the the layer of the message passing model. Each layer consists of two main steps: aggregation and update.
At each layer 0 < L. each node aggregates information from its neighbors by:
m(p, G. f) = Agg g (()
where Agg is a differentiable aggregation function that process the graph and its hidden node repre- sentations on each layer. In this article we focus on normalized sum aggregation, which is defined as follows.
Definition 19 (Normalized Sum Aggregation on Graph-Signals). Let (G, f) be a graph-signal, then normalized sum aggregation with respect the (G, f) and node v E (G) is defined
Agg(G, ( G, (o)
a(3a, G, () mEA(e)
Σ
16

---

Published as a conference paper at ICLR 2025
The node embeddings are then updated based the message m(y;, G, f)a and the node feutures from the privious layer g G, f) (
pp. G. =! Gg( m(p, G, G,
(2)
where sp(A) called the update function which is learnable Lipschitz function like an MLP (Multi-
Layer Perceptron). After I. layers, the last layer's hidden node representations g(p,, G, G, (7) are
processed by update layer. This layer is computed by applying readout function e IRd,, H R and outputs a single graph-signal-level representation:
(ve, vb G, = vi
[VG
Σ VEV(G)
a(ve G, f)
& typically a permutation-invatie function, that ensures the graph features is independent of any node ordering.
A.2.1 GRAPH ISOMORPHISM NETWORK (GIN)
Graph Isomorphism Network (GIN) Xu et al. (2019) is a popular MPNN model for graphs, which is as expressive as the Ceisseiler-Lehmae graph isomorphism test. GIN is defined with sum aggrega- tion but we use normalized sum aggregation. As update function,it uses multi layer preceptron (MLP) composed on addition of the massage m(y; G, r) == m (t) and g(vp, G, G,r) ()()))) == a (
that depends on contant that controls the weighting between the node's s own embedding and its neighbors' embeddings, as follows:
m (8)
(1-1) (e)(
V
0 = MLP(1)
((1 (1) (1-1) + m!?).
(t
The readout after layers (which we also normalize in contrast to the original definition) is:
6 v G. f) 6
Σ
00
(L)
V
VEV
GIN's ability distinguish between non-isomorphic graphs makes it compatible for tasks, such as graph classification and node-level prediction.
A.3 SUM AND MEAN AGGREGATION
We present here sum and mean aggregation schemes on graph-signals. This allows further discussion on the different aggregation schemes in Appendix D.
Definition 20 (Sum Aggregation Graph-Signals). Lel up be an L-layer MPNN model, (G,f) be a graph-signal, and i E [T.-1 1] then sum aggregation of (G, f)'s I-level features with respect to the node E (G) is defined as
Agg(G,ale.G.ff)
Σ (EN(e)
g(yp, !,
Definition 21 (Mean Aggregation Graph Siaph-Signals). Let sp be L-layer MPNN model, (G,f) be a graph-signal, and f E [L- 1] then mean aggregation of (G, f)'s t-level features with respect to the node E V(G) is defined as
Σ Agg aly, G. () = Noo meA(())
1
alva, ())
17

---

Published as a conference paper at ICLR 2025
A.4 TOPOLOGY BASICS
Topology is a fundamental branch of mathematics, in which spatial properties that remain unchanged under continuous deformations studied formally. Here, introduce key concepts of topology. Definition (Topological Space). topological space is a pair (X, T), where X is a set and collection of subsets of X satisfying:
1. Both @ and X are in
2. is closed under finite intersections
3. is closed under arbitrary unions
The elements of are called open sets.
A.4.1 CONTINUITY
Continuity, in topology, generalizes the notion of continuity from calculus to any arbitrary topolog- ical space.
Definition 23 (Continuous Function). Given topological spaces Tx) and Ty), a function f X + y is continuous if the preimage of every open set in Y is open in X. Formully, (U) Tx for all U rY.
A.4.2 THE PRODUCT TOPOLOGY
The product topology is topology which is naturally defined Cartesian product topological spaces. Although it can be defined for Cartesian products of any number spaces, in our analysis, are only interested in the finite case.
Let {(K,, }i) Jee be an finite set of topological spaces, then the product space the set {(t, TÚ) TT) is denoted by Iher X; and defined the set of all vectors (æt)aes where X; for each i I. The product topology is then generated by the basis {(Ui)srr U, E m.).
For each J, the projection map क, IIjer X2 - X; defined by (;((()))er) Iy. In the product topology, projection maps n, are continuous. Moreover, sequence in the product space converges if and only if its projections onto each factor space converge.
A.4.3 COMPACTNESS AND SEPARABILITY
Compactness and separability are both important properties in topology.
Definition 24. [Compact Space] topological space (X,+) is compact if every open cover of X has finite subcover.
Definition 25 (Separable Space). topological space separable if contains a countable dense subset.
Theorem 26 (Tychonoff's Theorem). Let (Xihie be a family of compact topological spaces. Then the product space llier X; is compact in the product topology.
A metric space a topological space, where the topology is induced by a distance function called metric.
A.4.4 NORM SPACES
A normed vector space is vector space over the real or complex numbers on which norm is defined.
Definition 27. A normed vector space is a pair (V, II where V a vector space over R or and
|| IR is a.function, called the norm, satisfying for all x. y V and all scalars
1. |||||| 0 and
||>||| if and only if
2. ||ax||| |ac| [<]]]]=]]
3. || vll < |a||| + ||a]]]
18

---

Published as a conference paper at ICLR 2025
A.4.5 METRIC AND PSEUDOMETRIC SPACES
pseudometric space is topological space, where the topology is induced by distance function called pseudometric.
Definition 28 (Pseudometric Space), A metric space is a pair (X.)) where & is set and d X' x X + R is a function satisfying:
1. d(x, v) 2 for all x, X.
2. d(x, d(y, x). for all I, E X.
3. d(x, 2) v d(z, v) d(y, for all a, 2, X.
Notice that it is possible that d(. y) for some * y, meaning distinet points can have zero distance. A metric is pseudometric that satisfy the following additional requirement.
vx, E X d(r, y) = 0 > x =
The pair (X,d) d), where X' a set and d X X' + IR metric called a metric space. The topology induced by metric/pseudomeericc is generated by base containing all open balls defined by B(x,r) = {y E X: d(x, y) < r).
A.4.6 COVERING NUMBER
Definition 29. A metric space X is said to have a covering number (0, No if. for any é > 0, X can be covered by x(e) balls of radius (see Appendix A.4.6).
Note that if metric space X' is compact (see Definition 24), then it can be covered by finite number balls of radius e, for any O.
A.4.7 METRIC IDENTIFICATION
Let (X,d) be pseudometric space. Consider the equivalence relation:
Vx, E X ~dd y if d(z, y) 0.
Any equivalence relation ~d is part of a class of equivalence relations called metric identifications. metric identification converts pscudometric space into metric space, while preserving the induced topologies. This identification is captured through the quotient map :~ X/ ~ defined as the map x -> [x:]. The open sets in the pseudometric space are exactly the sets of the form o (AA), where A E X/ is open. Namely, if an open set A E X' contains z, it has to contain all of the other elements in [æ:]. The pseudometric topology is the topology generated by the open balls
By(p) {x X d(p,z) <r),
which form a basis for the topology.
A.4.8 COMPLETE METRIC SPACES
Definition (Complete Metric Space), A metric space (X,d) d) is called complete if every Cauchy sequence in X converges to point in X. A sequence {Ia} X is Cauchy sequence ifr every e <> 0, there exists an integer E Ny such that for all m, n 2 N, the following holds:
d(zn, Fm) <.C.
In other words, if the elements of sequence get arbitrarily close to each other as the sequence progresses, then that sequence also converges to a point within the space. a topological space is metrizable to complete metric space, say that it is completely metrizable.
A.4.9 METRIZABLE SPACES
Definition 31 (Metrizable Space). A topological space (x.T) is called metrizable if there exists metric d: x X' R such that the topology induced by the metric d coincides with the topology
T on X.
In other words, the open sets in the topology т exactly the open with respect to the metric d.
19

---

Published as a conference paper at ICLR 2025
A.4.10 MEASURE SPACES
Measure theory generalizes and formalizes geometrical measures such as length, area, and volume as well as other notions, such as magnitude, mass, and probability of events.
Definition 32 (o-algebra). Let X be set. A collection Σ of subsets of X is called a o-algebra if the following properties are satisfied:
1. X
2. Σ is closed under complement, i.e., if then X AEE
3. E is closed under countable unions, i.e., if (m countable collection of sets in Σ, then
A EN
(5)
n=1
The pair (X', E) is called measurable space. A o-algebra provides the foundation for the construc- tion of measures,
Definition (Measure). Let (X,E) measurable space, where X is set and E is a o-algebra on X. A function E [0, oo) is called measure if it satisfies the following properties:
1. Non-negativity: For all A E E, p(A) 20.
2. Null empty set: μ(() = O.
3. Countable additivity (or o-additivity): For any countable collection of pairwise disjoint sets (== C E, the measure of their union is the sum of their measures:
U An
= Σ ((A)).
(6)
measure y assigns non-negative extended real number to each set the o-algebra Σ. The triple (X,E, p) is called measure space.
A.4.11 POLISH SPACES
Polish spaces topological spaces, that have "nice" topology in the following way. Definition 34 (Polish Space). A topological space is Polish if it is separable and completely metriz- able, iee, there exists a complete metric that generates its topology.
A.5 STONE- WEIERSTRASS THEOREM
Given A, denote by 1 A non-zero constant function. We present variation of the Stone- Weierstass Theorem (see Rudin, 1976. Theorem 7.32) we use in Appendix to prove universal approximation theorem.
Theorem 35 (Real Weie--Weesstraass. Let K. be compact metric space and A C C(K, RR) be sub-algebra that contains 1xc and separates points, i.e., for every k # I E K. there is f E A such that [k) # f(l). Then uniformly dense in C).,
The following corollary (taken from Grebfk & Rocha (2021)) is another useful description of the Stone- Weierstrass theorem, and is used as well the universal approximation proof in Appendix I.
Corollary 36 (Separating Measures). Let KC be a compact metric space and & C CCC,, RR be closed under multiplication, contain 1g, and separate points. Then for every μ + V Ms)(K) there is E E such that
J fdu
[
fdv
Lee., the linear functionals that correspond elements of & separate points in Mgi (K).
20

---

Published as a conference paper at ICLR 2025
A.6 THE CUT NORM AND THE CUT METRIC
The cul norm was introduced by Frieze & Kannan (1999) and provides the central notion of conver- gence in the theory of dense graph limits. Levie (2023); Rauchwerger & Levie (2025) extended the norm to graphons with d-channel signals, i.e., graphon-signals in W W.G.
Definition 37 (Cut Norm and Cut Metric). The cut norm of measurable W [0, 1]2 + R. and the cut norm of a measurable function [0, 1] + Rd is defined as
J (1x,, v) drdy and A,
I1 == sup 1/ [(x) ((()) ((1)))(00) d sc
[Wllo = sup
AXB
where the supremum taken over the measurable subsets A, B S [0, and S [0, 1]. respectively. define the graphon-signal cut norm, for a graphon signal (W,J) E WCT. by
IIWW == || Il We name the metric induced by the cut nom the cut metric, which is defined to be do((W, (V,9)) [I(W (V.9)la
for any two graphon-signals signals (W, (V,g) e WCJ
A.7 THE CUT DISTANCE
Lovász (2012) first defined the cul distance graphons through the graphon cut norm. The cut norm was later extended to graphon-signal by Levie (2023); Rauchwerger & Levie (2025) using the graphon-signal cut norm.
Let So.1] be the space of measurable bijections between co-null sets of [0, 1]. Namely,
S/o.1) == tØ A + B A, B co-null in [0, 1], and AS E A, ((S) m()(S)))
where Φ is measurable bijection and A, B,S are measurable. Let ø be measurable bijection in S/,1). for any graphon, W, and signal f, we define W (x, v) == W (ø(x), d(y)) and (=) = f(((2)) respectively. We then define fW up to null-set, therefore, we (arbitrarily) set W, W " to in this null-set. This does not affect analysis, the cut norm is not affected by changes the values of functions on null sets.
(Vo.g)) Note that W and f are only define
Definition 38 (Cut Distance). The cut distance is defined to be
(OW, (V,g)) = inf
f).
6E
A.8 THE QUOTIENT METRIC SPACES OF GRAPHON RRAPHON-SIGNALS
The graphon-signal cut distance i is a pseudometric. Consider the equivalence relations: (WJ)) ~ (V.g) if 8 f), g)) 0. For any graphon-signals (W, e WL denote the equivalent class of (W, with respect to -i, as [(W f)]. Then, the quotient space
WC : WC/-
of the equivalence classes (WWJ)) is metric space, with the metrie &=(((W,)) (), ( f), (V.g)). Notice that the equivalence relation ~ is a metric identification (Ap- pendix A.4.7).
A.9 THE COMPACTNESS OF THE CUT DISTANCE
The space of graphon-signals is compact w.r.t. the cut distance d (Definition 38), as proven in Levie (2023); Rauchwerger & Levie (2025).
Theorem 39 (Levie (2023), Theorem Rauchweerrrre & Levie (2025), Theorem 4.4.). The Pseu-
dometric space (WC,, ôn) and the metric space (WL/ dn) are compact. Moreover, given r > 0 and c for every sufficiently small > they can covered by
<(() = 2h²
(7)
balls of radius e, where k -
21

---

Published as a conference paper at ICLR 2025
A.10 THE CUT METRIC REGULARITY LEMMA FOR
To formulate our regularity lemma, we first define spaces of step functions, based on Levie (2023); Rauchwerger Levie (2025).
Definition 40 (Levie (2023), Definition 3.3.; Rauchwerger & Levie (2025), Definition 4.1.). Given a partition Pk, and No, we define the space Sp-' of step functions R >> IRd over the partition Pe to be the space of functions F: [0, 1]2 + Rdd of the form
Σ
I \=
Ip, (2i) Cj.
(8)
for any choice of (ez E R BEEE
We call any graphon, that also belongs to the set S7,+1 step graphon (also called stochastic block model (SBM)) with respect to Px. We call any signal, that also belongs the set Spp"d step signal. We define the space of (graphon-signal SBMs with respect to Py as W n (5 x -pard) Next, define the projection of graphon-signal upon a partition.
Definition 41 (Levie (2023) Definition B. B010; Rauchwerger & Levie (2025), Definition 4.2.). Let be partition of [0, 1), and (W. W.C. We define the projection of (W. f) upon W (S7,11 Sp.a)) be the step graphon-signal f),,)p. = (WP,,fr, that attains the value
P. {P....., ...... P.
(2) Sr, (x) = S. pz)d
Wp, (2, = 1.11
0.11
for every (r,y) E P. x P3 and < in
Note that we use the notation (Wp. and the notation ([)),, [flp.) interchangeably. The following version of the regularity lemma states that any graphon-signal can be approximated using the average values of both the graphon and the signal within some partition.
Theorem 42 (Levie (2023), Theorem 3.4 and Corollary B.11; Rauchwerger & Levie (2025), Theo- rem 4.3, Regularity Lemma for Graphon-Signan
For any > > and any sufficiently small
e > for every n 2 2 3/ and every (W, E WCT. we have
d (W, f), (W, ) Scc
where In is the equipartition of [0, 1] into intervals.
A.11 WEIGHED PRODUCT METRIC
We say that product metric is weighed if there is vector of weights v (wi) with positive entries (w, > 0) such that
di (( In), (Wi....,y., = [1( dx, (11,81),... wn dx, (I yn 1l.)
A.12 THE BOUNDED-LIPSCHRS DISTANCE
Definition 43. Let X, y be two metric spaces. Let f E Lip(X, where Lip(X. is the space of Lipschitz continuous mappings X' + Y. We define the function [1-11, Lip(X',) R4 by
|l inf (L : i. Lipschitz constant of f}-
L
Note that ||. is seminorm over Lip(X, ).) Moreover, notice that [|] can also be expressed as
[f(z) f(v)
fl
sup æ+y d(z, v)
22

---

Published as a conference paper at ICLR 2025
Since the set of all valid Lipschitz constants is closed from below in R and non-empty (for Lips- chitz function), the infimum attainable in the sense that it still satisfies the Lipschitz condition:
[f(z) f(y) S Ill d(z,y).
Thus, ll. is indeed a Lipschitz constant it is the smallest one, also known as the optimal Lipschitz constant or the best Lipschitz constamt of f.
Definition 44. Let (X, E, po) be a measure space and (3;11-lly) be a complete normed vector space and let f : X + y be measurable function. The -oom of f is defined as
|| = ess sup =eX
(x))l>)
Definition 45 (The Bounded-L Lipschitz Function). Let (X, E. fr. d) be a measure space, with a met- ric d and (V, Il-lly) be complete normed space. Ler Lip(X,)) be the space of Lipschitz continuous mappings X + Y. We define the Sounded-Lipschie function over Lip(X, as
|| |BLL == =111100 + IH
when ||-1l,, and ol are defined in Definition 43 and Definition 44, respectively,
Note that I/ is norm and I1-1l, is semi norm then BI. is seminorm well. Definition 46 (The Bounded Bounded-Lipschitz Distance). Let X be a measurable metric space, y be metric space, p1, -M) and - be a p-measurable and v-mesurable function. Let
I |sdp-
-f sdv
BI(
sup
11
be the Bounded- Lipschtt distance of and v, respectively, where [l is the Bounded Lipsshhit function.
A.13 THE KANTOROVICH RUBIIIHHHH-RINNHENEN DISTANCE
Definition 47 (The Rubbishhhennnnn Distance). Let X be measurable metric space, Y be a metric space, μ,v E (x).). and f + R be y-measurable and v-mesurable function. Let
K(μ, v) = sup 11
/ [dy
[dd=]]
-
Idu
be the Kantonovich-Rubinhheis distance of μ and respectively.
A.14 THE PROKIIOROV METRIC
Definition 48 (The Prokhorov Metric), Let (X, B(X) be a measurable metric space with Borel a- algebra. We define A {y S d(x. v) for some E A} for subset A C X and 0. Then, the Prokhorov metric P on Mei (X, B) is given by
P( > 0 m(A) S ((()) + and u(A) S M(A7) + for every A E B).
B ADDITIONAL RELATED WORK
We provide here extended discussion on related work. Several recent works consider pseudo met- rics on graphs, aiming to capture structural properties of the graph and the computational procedure of message passing. The latter is often described by computation frees, hierarchical structures result- ing from unrolling message passing (Morris et al., 2019; Arvind et al., 2020; Garg et al., 2020; Xu et al., 2020; Chuang & Jegelka, 2022; Jegelka, 2022). Similarly, hierarchical structures of measures have been used for the analysis of MPNNs (Chen et al., 2022: 2023; Böker et al., 2023; Maskey et al., 2022). Although these structures may look different first glance, they describe the same iterative message passing mechanism. Other approaches include Titouan et al. (2019) graph metric defined using both Wasserstein distance and Gromov- Wassovsteisnrniinnnnn distance Mémoli (2011). This
23

---

Published as a conference paper at ICLR 2025
approach, just like classic graph metries Bunke & Shearer (1998); Sanfeliu & Fu (1983) requires using approximation. In addition, several graph kernels have been proposed Vishwanathan et al. (2010); Borgwardt et al. (2020). Here, focus on the viewpoint of computation trees, they closely align with MPNNs. A number of existing works study generalization for GNNs, e.g., via VC dimension, Rademacher complexity
PAC-Bayesian analysis (Oono & Suzuki, 2020; Tang & Liu, 2023; Li et al., 2022; Garg et al., 2020; Maskey et al., 2022: Morris et al., 2023; Maskey et al., 2022; Liao al., 2021b). Most need assumptions on the data distribution, and often on the MPNN model too. Levie (2023); Rauchwerger & Levie (2025) use covering number (Definition 29), for wide range of data distributions. We expand this result more general setting.
C ADDITIONAL DISCUSSION
Here, we provide additional high level discussion on different aspects of our construction.
C.I. THE LIMITATION OF OUR CONSTRUCTION TO DENSE GRAPHI
For sparse graphs, the number E of edges is much smaller than the number N2 of vertices squared. As a result, the induced graphon is supported on a set of small measure. Since graphon are bounded by 1, this means that induced graphons from sparse graphs are close in Li ([0, 1 to the graphon. DIDM mover's distance gives a courser topology than cut distance, which is courser than L ([0, 1J²). Hence, since all sparse graph sequences converge to O in ([0, 1J2), they also converge to 0 in DIDM distance.
Therefore, we can only use our theory for datasets of graphs that roughly have the same sparsity level S E Ny. i.e., 2 E' is on the order of some constant S for most graphs in the dataset. For this, one can scale our distance by S, making appropriate to graphs with E < N2 edges, in the sense that the graphs will not all be trivially close to O. Our theory does not solve the problem of sequences of graph asymptotically converging to O.
In future work, one may develop a fine-grained expressivity theory based sparse graph limit theo- ries. There are several graph limit theories that apply to sparse graphs, including Graphing theory Lovász (2020), Cettamini-Shhrmmn limits Abért et al. (2014); Béla & Riordan (201 I); Hatami et al. (2014), stretched graphons Jian et al. (2023); et al. (2024), L graphons Borgs et al. (2014a;b), and graphop theory Ágnes Backhausz & Szegedy (2020), which extends all of the aforementioned approaches.. Future work may extend our theory to sparse graph limits.
C.2 COMPARISON OF SUM MEAN, AND NORMALIZED SUM AGGREGATIONS
See Appendix A.3 for the definition of sum and mean aggregation on attributed graphs. First, (un- normalized) sum aggregation (Definition 20) does work in the context of our analysis. Indeed, given an MPNN that simply sums the features of the neighbors and given the sequence of complete graphs of size N No. then, the output of the MPNN on these graphs diverges to infinity as n + co. As a result, equivalency of the metric at the output space of MPNNs with a compact metric on the space of graphs is not possible.
Another popular aggregation scheme is mean aggregation, defined canonically on graphon-signal as follows (Maskey et al., 2022: 2024).
Definition 49 (Mean Aggregation be a graph-signal, and t E [L (L--1 11. Then mean aggregation of (W. f)'s 's t-level features with respect to the node (WW) is defined
Graphon-Signals), Let tp be L-layer MPNN model, (W, f)
I
Agg(W,f(pp W. ())))))))))))))+>-))))))))))))))
(2x,y)(ee W. ((9g))))))
JO.1 ()),))
[..]
The theory could potentially extend to mean aggregation using two avenues. One approach is to do this under a limiting assumption: restricting the space to graphs/graphons with minimum node degree bounded from below by a constant. This is like an idea outlined in Maskey et al. (2024).
A second option is to redefine δDIDM using balanced OT. In this paper, δDIDM highly relates to the type of computation MPNNs with normalized sum aggregation perform. We used unbalanced OT
24

---

Published as a conference paper at ICLR 2025
(Definition 1) do not average incoming messages, which means they can separate nodes of different degrees within graph. MPNNS with mean aggregation, in contrast, do average incoming messages. Hence, an ap- propriate version of optimal transport, in this case, could be based on averaging. lee., using balanced OT on normalized measures could serve base for defining metrics in the analysis of MPNNs with mean aggregation.
the basis of ÓDIDM due to the fact that MPNNS with normalized sum aggregation
C.3 CONPARISON OF OUR GENERALIZATION BOUND TO RELATED WORKS
Both our work and Levie (2023); Rauchwerger & Levie (2025) do not make any assumptions on the graphs and allow a general MPL scheme. Our classification learning setting generalizes that of Levie (2023), which assumes a ground truth deterministic class per input, while we consider a joint distribution over the input and label as Rauchwerger & Levie (2025).
In comparison to other recent works on generalization, Garg et al. (2020); Liao et al. (2021a) as- sume bounded degree graphs. Morris et al. (2023) assumes graphs with bounded color complexity, and Maskey et al. (2022; 2024) assume the graphs are sampled from small set of graphons. More- over, Garg et al. (2020): Liao et al. (2021a); Morris et al. (2023) do not allow general MPL presented in this paper, so their dependence on N is N-1/2 This means their generalization bound decays faster as a function of the training set size N. et al. (2022) analysis is restricted to graph convolution networks which are a special case of MPNNs. Tang & Liu (2023) does not focus on graph classification tasks but on node classification. Oono & Suzuki (2020) focus on transductive learning in contrast to our inductive learning analysis.
D MPNN ARCHITECTURES: STANDARD AND ALTERNATIVE FORMULATIONS
Levie (2023) suggest a different MPNN definition for the analysis of MPNNs on graphon-signals. This definition includes, in addition to update and readout functions, functions called message func- tions. In this section we show that, although our MPNNs definition is, in it essence, a simplified version of the MPNNs in Levie (2023), the two definition are equivalent in terms of expressivity. We start with a recap on our standard MPNNs definition.
D.1 STANDARD MPNNS
An MPNN as defined in Definition 7 consists of an initial layer which updates the features, via a learnable Lipschitz continuous mapping (0) RP + Rd followed by L layers, each of which con- sists of two steps: a message passing layer (MPL) that aggregates neighborhood information, fol- lowed by a node-wise update layer. Here, when we apply the MPNN on graph-signals or graphon- signals, we assume the MPL to be normalized sum pooling or integration pooling, respectively. The normalized sum we use can be defined for graphon-signals as follows.
Definition 50 (Normalized Sum Aggregation on Graphon-Signals), Let be an L-layer MPNN model, (W. be a graph-signal, and t E [L - 1] then normalized sum aggregation of (W, f) (-level features with respect to the node x E V(W) is defined as
Agg(W,f(pp W. Ac) = f( W(x, W. W.DDddxw
The update layer consists of a learnable Lipschitz continuous mapping ((t)) RR2d-1 + Rd where S f < L is the layer's index. Each layer computes a representation for each node. For predictions on the full graph, readout layer aggregates the node representations into single graph feature and transforms it by a learnable Lipschitz function & Rdd. + Rd for some d E Ng. For the readout graph-signal, and graphon-signale we average pooling. The readout layer aggre- gates representations across all nodes when a single graph representation is required (e.g. for graph classification).
25

---

Published as a conference paper at ICLR 2025
D.2 ALTERNATIVE MPNNS
We next show how to extend our normalized sum aggregation, used in this paper, to an aggregation scheme with function called message function. This aggregation scheme is used in Levie (2023), for the analysis of MPNNs on graphon-signals. The idea is that general message functions depend both and the feature at the transmitting node and the feature a the receiving node of the message, i... Φ(a, b). In Levie (2023), such general ő(a, b) was approximated by linear combination of simple tensors of the form Sree (araana (a) to accommodate the analysis.
Definition 51 (Message Function). Let K N. For every S k S K, let Ex.ree, Ex.trans RR H IºP be Lipschitz continuous functions that we call the receiver and transmitter message functions, respectively. The corresponding message function Φ Iddd + R is the function
K
Φ(a,
Σ
(a) (b),
where the multiplication is element-wise along the feature dimension.
Given some signal f over the domain X, we see the point x E X as the receiver of the message (f)()), fz)), and as the transmitter, and call o(f(-), X22 + R" the message kernel.
Just like with MPNN models, for predictions on the full graph, readout layer aggregates the node representations into single graph feature and transforms it by learnable Lipschitz function TR + Id for some d No- For the readout, we use average pooling. We now define the alternative MPNN model.
Definition 52 (Alternative MPNN Model), Ler L E No and p. p.do...., Po..... Pr. d E No. We call the tuple (pp,)) such that & is any collection & (f(()) of Lipschitz contimuous functions (0))) IR + Redo and wltt) Rec-1x9--11 + R for 1 < t L, and 6 is any collection Φ (o(t)) ) of (Lipschitz continuous) message functionn ((9) 2 RP--1, for Stt S L, an L-layer alternative MPNN model, and call ( update functions. For Lipschitz continuous vi : Rd + IRd, we call the tuple (4p, db 1b) an alternative MPNN model with readout, where vi is called a readout function. We call the depth of the MPNN, p the input feature dimension, do..... dr the hidden node feature dimensions, ,o...,PL-I the hidden edge feature dimensions, and d the output feature dimension.
possible to define the application of alternative MPNN models not only on graphon-signals, but on graph-signals, IDMs and DIDMs well. In this discussion our purpose is to show that our aggregation schemes are equivalent on graph-signals and graphon-signals.
For our purpose, the application of the alternative MPNN model on graph-signals and graphon- signals is enough.
Definition 53 (Alternative MPNNs on Graph-Signals). Let (4p, o, t) be an L-layer alternative MPNN model with readout, and (G, be a graphon-signal where f V(G) + RP. The appli- cation of the MPNN on (G, f) is defined as follows: initialize (00) == (00(0((((())))))))))))))))())( (f(-)), and compute the hidden node representations g V(G) - Rd at layer t, with S S L and the graphon-level output & Rdd by
a : (0 (ah-1)
Σ [VG)) (EN())
(o6- (60 1)- and & : (
) (EV(G)
Σ
Definition 54 (Alternative MPNNs on Sraphon-Signals) Let (vp, Φ. 1b) be an T--layer alternative MPNN model with readout, and (W,f) be a graphon-signe where f V(W) - RR. The applica- tion of the MPNN on (W is defined as follows: initialize ((0) = (f(-)) and compute the hidden node representations' p1.) -VWW) + Rd at layer with S 1 L and the graphon-level
output & ddd by
((t) = (0) -000((1 (1--1) 10.11
W(2, ( (ft-1)) "0,,(tt-) ((t- (d(y)) and $:= ( [f.
26

---

Published as a conference paper at ICLR 2025
As with the standard MPNN features, to clarify the dependence of and & on (p. 6) and (w, f), often denote flp, o) or f(yp, 6, W, f)d² and flv,, o, v) or 3(p, o, w. W.
Definition 55 (Alternative Normalized Sum Aggregation on Traphon-SSinally Let ip be an L-layer MPNN model, (W, be graph-signal, and t I. 1] then normalized sum aggregation of (W, 's t-level features with respect to the node E V(W) is defined as
Ww flpp, W. W. (x) foo.1] W(x, (0 (P: (f 1) P ( DdX()-
Many well-known MPNNS architectures can be easily expressed as alternative MPNNs. We now present an examples taken from Levie (2023) of spectral convolutional network. Definition 56 (Vector Concatenation). Let E Th and b R be vectors. The concatenation of and b, denoted as a b), is vector in mR=+ defined as:
Q1
(a: b]
Qm
b1
b2
bn
Given graph-signal (G,f), with f E Raxd with adjacency matrix A Rux,, spectral convolu- tional layer based on polynomial filter filter(A) Σÿ= NC2, where C E R is defined to be
J Σ ArCC, n
ilter(A)f
1=
followed by pointwise non-linearity like ReLU, Such convolutional layer can be seen MPLs, where each MPL is of the form
f - Af).
Notice that the action f - 1 Af Af (9) as the identity function, and then, we define (( = [++] and ((t) b) = b for 0 < t J, to get the desired action. Lastly, we define
simply the action of a normalized sum aggregation. We first define
( = ReLu(fC)
for some C E (J++))xx where ReLu(x) max( 0) is pointwise non-linearity.
D.3 AGGREGATION SCHEMES EXPRESSIVITY EQUIVALENCY
We now show that alternative MPNN models have the same expressive power as MPNNs with our normalized sum aggregation. Denote Add = f((p 6) H4
HL + Rd= Φ) is an I-llaee MPNN model} and Sdi Rd is L-layer MPNN model). It is clear that the alternative MPNN models as our standard MPNN models. we set the message function to be Φ(a, b) = b, the alternative nor- malized sum aggregation (Definition 55) is equal the in Definition 50. This means that A C Sdi. We now prove Proposition 58, that shows Sds. AAd It follows immediately that the sets (3(p, d. - (HL + (sp, ó, 1b) is an L-layer alternative MPNN model with readout) and (3(p, v. -) Ht + dd ((p, v) is an L-layer MPNN model) equal. We start by defin- ing function concatenation and function Cartesian product, which we use in the proof of Proposi- tion 58.
(f(()
expressive
27

---

Published as a conference paper at ICLR 2025
Definition 57 (Function Concatenation). Let f X H y and g X + Z be two functions. We define function concatenation as the function g : X + y x Z such that py o (f g) = f and Pz (f 11 g) where py, Pz the canonical projections from y x Z to y and 2, respectively.
Given (f a set of functions f : X2 + Vk. we shortly denote fill II as I Proposition 58, Let (), be an L-layer alternative MPNN model. Then, there exists an MPNN model 4f such that,
- - =
Proof. The proof is by induction.
Induction Base. For L = O, (p, ()) = (o)))), that is, the feature do not depend of the aggregation and therefore, the statement is trivial and we can jsut define s = -(o"(0) such that yp(0) sp
Induction Assumption. Presume that for any L-layer alternative MPNN model (se, Φ) there exists L-layer MPNN model şp such that f(yp, Φ, - -) = -())'.--))_-
((=))) be an L+1- alternative MPNN model. Then, ((gll)) )ee[L) (f())) is L-layer MPNN model. By the induction assumption, there ists an I--layer MPNN model yp' such that f(vo, 0, - -) = i(y', -. ()) Following the message function definition, we can write (a, b) = Ek=l (a) (b) for some Lipschitz contin- uous functions (Ex.ree and (En,transs 1==
Induction Step. Let (fp, Φ) = ((y(())
Define 4", an L+I-layers MPNN model, as follows: for S t L set go((t) == (l(t), and set (P(()) == (o (LL), when ((x) = (x) (ll re))) || ( E R((K+1)p, Define (((L+1) (l++1) o a, where a 222 R2D is defines follows; let v (m:)==1
2(K++))p
R2(2K+1ip be a vector, then (vv) ((v)) ΣØ= (3K+((k)))++))
Let (W, be graphon-signal. In the following equations we use shorten notation and do not write explicitly the dependence of the features on the graphon-signt signal, as all features depend on f). Then,
(1+1) = =((")(t)) (F(D") 1.11
/ w ((a,"))
(((()) o oo(((f()'))) / ((.
= (((((e)))))) f (
10.1
K (((,,))
Se (iee () / W(z, v) (1lp, dy))
(PL+))((((,))))) / w(x,v) Σ ro (ppp, () En, (1p ()
p..)
p((+1)) (occt)((iee,0))) (1()))) L Waz (o () "000),(pp
()) )dy
()((+11)
D.4 LIPSCHITZ CONTINUITY WITH RESPECT THE CUT NORM
Levie, 2023, Theorem 4.1 (also Rauchwerger & Levie, 2025, Theorem 5.1.) states that alternative MPNNs (Definition 52) over the space of graphon- with respect to the cut distance d (Defi- nition 38), without the Lipschitz continuous function ())), are Lipschitz continuous. Definition 52
28

---

Published as a conference paper at ICLR 2025
without the first update function (0 is equivalent to the definition of MPNNs in Levie (2023); Rauchwerger & Levie (2025). The existence of the Lipschitz continuous function eo()) in the model does affect the Lipschitz constant value, but does not affect its existence, since a composition of two Lipschitz continuous functions is Lipschitz continuous function.
Since any standard MPNN (Definition 7) can easily formulated as an alternative MPNN (Def- inition 52), Rauchwerger & Levie, 2025, Theorem 5.1 holds for standard MPNNs. Therefore, we rephrase Rauchwerger Levie, 2025, Theorem 5.1 in terms of our definition of standard MPNNs. We slightly adjust the notations to be consistent with our own notations.
Theorem 59 (MPNN Lipschitz Continuity with Respect to the Cut Distance). Let (4p, 1)) be an L- Layer MPNN with readout. Then, there exists constant Cie,wy. that depends only on L, the number of layers, and the Lipschitz constants of model's update functions, such that
18 v; W) - 3(p, vh, V,g)ll2 S C(ppe) 60((W,), (V, for all (W. (V. E W.C.
E BASIC METRIC PROPERTIES
E.1 THE WEAK" TOPOLOGY
Let L E No. we motivate the need to prove that dfDM and OT di are well-defined, by the fact that the measures in M M=1(H²) = MHItHH. ) (and (HL*) = (H ((H)) are defined as functions μ1: BB7(") + R. But for any topological space X, its o-algebra ((X) depends on the topology of X. In the case of H-, the topology is the product topology, when M', for i E [4] has the weak* topology, which makes it crucial for OT dipsa to metrize the weak* topology on M and (HL otherwise the sets Mz1 M two different sets.
B(H+))
and MstHH ,dfom) might be
The well definiteness of the metric dfDM on H. and OT diss P (H. follow similar arguments used in Böker et al. (2023). Let (X, be complete separable metric space. Böker al. (2023) showed that the unbalaced optimal transport, as we define it (see Definition 1) is indead metric on Mes (S) by following the proof of Pele & Werman (2008).
Lemma 60 (Böker et al. (2023), Corollary 21.). Let (S, d) be separable metric space. Then, OT a metric on Mz1(5, d).
Moreover, they show that this metric metrizes the weak* topology of (S) by proving inequali- ties, that are known hold for probability measures, for measures with total mass smaller then one.
Lemma 61 (Böker et al. (2023), Lemma 22.). Let (X,d) be a complete separable metric space. Then, for all μ.v E Mz)(X).
BL( S K(H,P) S OTa(U)) S 2P(,, v) S BLLLU,)).
Here K is the Kantorovich- -ethroiiichuuubssheeinn distance (Definition 47, BL is the Bounded Jounded-Lipschitz dis- tance (Definition 46), P the Prokhorov metric (Definition 48). To prove Lemma they follow proofs outlined in Schay (1974) and Garcfa-Palomares & Giné (1977), which use the duality of linear programming.
A direct result of Bogachev, 2007, Theorem 8.3.2 and Prokhorov, 1956, Theorem 1.11 is that if (X, d) is a complete separable space, then K and P metrize the weak* topology on (x') and P (X)) These facts together with Lemma 61 entail the following. If (X, d) is separable, then OTa metrize the weak' topology on Mc1(X') and (XX). We summarize this result in Lemma 62.
Lemma 62. Let (X, d) be complete separable metric space with Borel o alageerra B. Then OT is well defined and metrizes the weak" topology of MM (X) and (XX).
We can now follow the proof of Lemma 24. in Böker et al. (2023) and prove Theorem 4. Theorem 4, Let L E No. The metrics dfOM on H and OT diss on (HL and (g) are well-defined. Moreover, OT d metrizes the weak" topoloiies of Mr ( and (HL
29

---

Published as a conference paper at ICLR 2025
Proof. We start with the fact that (H,, dDDM) (B,, 11-11)) and therefore d'DM is well defined. As B. is complete separable metric space (a compact sub space of R"), by Lemma 62, convergence in OT dips is equivalent to weak' convergence on M (H4 diDM) and (H ((HH)dDDM) dfDM) which is just weak* convergence on Mgi(H.) B((")) and (HL B)H respectively. Hence, the topology induced by OT OTdiDM is equal the weak topology on mMHHH B)H()) and P ((H))) as both spaces metrizable. The induction step follows the same arguments with the additional claim that dDM is product metric, which metrizes the product topology.
E.2 THE COMPACTNESS THE SPACES OF IDMS AND DIDMS
Let IC be compact space. A well-established result (Kechris, 2012, Section 17) in measure theory states that the space, Me1 (IC), is equivalent to the set of non-negative Radon measures total mass at most 1. The Riesz Representation Theorem (Rudin, 1986, Theorem 6.19) establishes that these measures correspond precisely to the non-negative linear functionals with norm at most 1 in the dual space of continuous real-valued functions K. C(K, RR. The weak" topology on MMgi is defined as the minimal topology that ensures continuity of the mappings:
Je fdv + Jec fdv
for all continuous real-valued functions on K. A fundamental result asserts that M1 (KC,, when endowed with the weak' topology, forms a compact metrizable space. Moreover, the Borel a- algebra generated by this weak topology is identical the conventional Borel structure on Ms. (KC
induced by the mappings:
A *(A,,,, A B(K)
where (IC) denotes the Borel sets IC (Kechris, 2012, Section 17).
Theorem 3. The spaces H³ and (HL4) are compact spaces for any T. E No-
Proof. The proof is done using induction.
Induction Base. Recall that 7D (BB, II-II) is a compact metric space. As unbalanced optimal transport metrizes the weak" topology (7H and (H(), they both form compact metriz- able spaces.
Induction Assumption. Presume that for any 0 < L, the spaces H', Msi(H'), and (HL') compact spaces for E [L-1] 1].
Induction Step. Let 0 < L. Tychonoff's theorem (see Theorem 26) states that the product of any collection of compact topological spaces is compact with respect to the product topology. As dfim metrize the product topology, and conclude that 7 = -losieL-Mss Mgi(H()) (H(') is compact. We can now use the same argument as in the induction base, i.e., unbalanced optimal transport metrizes the weak* topology on Mrs (HO) and S (H²), to conclude that both Ms ( and (HL with the topology induced by OT dios form compact spaces.
combine Tychonoff's theorem with the induction assumption
E.3 THE COMPACTNESS OF THE SPACE OF GRAPIION-SIGNALS
We now show that the space of graphon-signals is compact under the DIDM mover's distance. The compactness of the graphon-signal space makes it possible to rephrase our generalization analy- sis directly on the graphon-signal space. More importantly, allows us to approximate any real continuous function over the space of graphon-signale rather than only functions over the space of graphon-signals that can be extended as real continuous functions over a space of DIDMs (see Appendix I).
To do so, we use results from Levie (2023); Rauchwerger & Levie (2025). Note that in our setting, signals functions that map the interval [0, to general compact subset of Rd rather than sphere around 0, as in Levie (2023); Rauchwerger Levie (2025). Nevertheless, their results are not affected by this change.
30

---

Published as a conference paper at ICLR 2025
The DIDM mover's distance MiDM is pseudometric WCF. Consider the equivalence relation: (W. ~n (V.g) if BIDM (WW, (V, g)) = 0. Then, the quotient space
WC ///DM == WL/ ~
of the equivalence classes f))x is metric space, with the metric BIDM ([(W,) ((V g))
SIDD (WW, f), (V,g)) Notice that the equivalence relation is a metric identification (Ap- pendix A.4.7). Notice that the equivalence relation ~L metric identification (Appendix A.4.7).
Recall that we similarly denote by WC2 the graphon-signal space under metric identification ~ (Appendix A.8) of the graphon-signal cut distance 6= (Definition 38).
The following theorem relates the convergence in (WC,, (IDM) to the convergence in (WC,, dn).
Theorem 63. For any fixed L E No, sequence of graphon-signat, Jt))ie, WCJ and graphon-signal (W,f) f) the following holds,
(W bu (W,J) = Si
DIDM
(W.J)
$
(W,, o0 [(W,)) = I(W, fillz
DIDM, [(W,
Proof. Let fi) b (W, f), then, it follows from Theorem 59 that f(w..f) + f(wJ) for all MPNN model O with readout &b Rd + Rd, where d > O, which entails, using Lemma 11, that br or + br arr. for all MPNN model ip with readout & Rd + R where d > O. By Corollary 12, we have that I' L.,. + f(..f).. (in the weak' topology). According to
BIDD, (W. The L
Theorem 4, OT dfrma (Fow,.)).L. I (w.)).t) + O. By Definition 5, fi) other implications are straightforward,
Theorem 64. The pseudometric space (WC,, (IDD) and the metric space (WL, BIDM are compact.
(IDM)
Proof. For any E No, Theorem 63 implies that the pseudometric topology of (WL2, 8 ( cooraser than pseudometric topology of (WC,165). Thus, since (WC/, 8p) is compact (Theo- rem 39), (WC,, (DDM) must be compact.
Let (Ua be an open cover of W 6/nDar / the sets of the form π (AA), where A E X/ ~ is open, thus (r-)(u_)) }a is an open cover of W and thus has finite cover { 1 (U..) ). Since the quotient map is surjective,
The open sets in the pseudometric space are exactly
WC f
((π 1 (WCC)) क(" -U.U..) S U.U..
This means (Ua, Jy is finite cover of WCJ / óhDDs Thus, the quotient space (WC, //mm 8hIDA) also compact.
Corollary 65. The space of computation DIDMs I Iww, ç (H! is compact.
Proof. By Theorem 64, the space of graphon-signals, W is compact. By the definition of dii (Definition 5) the mapping I(W,)) WCd + ( is continuous. Thus [( (WW.) is compact, since a continuous function between two metric spaces sends compact sets to compact sets.
F COMPUTABILITY OF OUR METRICS
First, extend Schmitzer & Schnörr, 2013, Proposition 4.5 for couplings between measures with unequal mass, by follows the steps in the original proof. We emphasize that in Proposition 66, and y do not refer Definition 2.
31

---

Published as a conference paper at ICLR 2025
Proposition 66. For two discrete sets A. C and two measurable maps @a X - A Φb y C denote by & the product map Φ(x, y) = (0a( ob(y)) Then one finds
61I(H, = I( Øb.
when dh b) (7: 0.7 : V)).
Proof. Assume ||ا||| ||/|]. For any y E [(, 2/ we get
2 20. 0.
when S A x C a measurable subset, and
(0). C = =00 x X) = (p)).
(SA) (da)..(SA)
when SA A measurable subset and analogous for Se S C measurable subset
(0)- Sc) 7(x' (b(Sc) = (p:) Su(o (6.).
Thus (0).I(p,)) v) S (1)))))
We now show by construction for any [(0aaH, vb.v) the existence of some E T(H, such that p = (.). For any element (a, E construct the pre-image measure
if p(a, 0v (a. 6(x.8) else
Ma,,) (I,
a(z)v(y) (1l)),
where this element wise definition for each (x, y) is extended all subsets of X' y by
(S))(()) Σ
(2,,) y)
(x.y)e
when S is any measurable subset of X' x y. Now consider = ((a))xAx Ma,ej- First verify that it is indeed contained in T(H,
(S) 2 0: measurable S C X' x V
since >(x,)) v) 2 0 for all (x, v). Furthermore
32

---

Published as a conference paper at ICLR 2025
u(z)v(y)
7(5x x x3)
E E
JESx (a,c)EAx): yEy ((u,y)=(a,c),
p(ac))30
(I u(y)
Σ
E
(61))) ((a(()))
xESx
EEC:
((0u(1)))200
u(z)u(o;
Σ
Σ
((ab)) ((ou()))
zESx
CEC:
(1)))0)
11(x)
E
Σ (z))
FESx
DEC:
(()a(=).))>0
m(x)
(pI).p(d(<z))
(oo
SESx
m(x)
(00 = E m(x) = -((xx)
zESx
xE
for all measurable subsets Sx S X' and likewise
7X x Sy)s((()))
u(z)x(v)
xx Sy) = Σ Σ
(1 (100))00(()))))0)0000
VESy (xxc
EEt ((a.e)=(a.c),
pla,c)30
(()))()
Σ
Σ
((226))((((6))1110600000000000 P(o(o)))
yESy p(a.)r(y)>>0
Σ
(100)100(((0))000001111 do(,o)
VESy
p().)s(v))>0
v(y)
Σ
pla,
(())))))(((()))
yESy
de
p(a.ostv))>0
u(x)
(po).p(O.(v))
(())))))((((v))
VESy
v(y)
Σ
(()()))
Σ v(x) = v(SA)
((t)).)((((())
yeSy
JESy
for all measurable subsets Sy C Y. Now check whether 6.7 = pt
33

---

Published as a conference paper at ICLR 2025
( =
E
(2,
(2,))6-1(())
(()))(y)
Σ
(10000000000)0000000000o0.. plo(z,)))
(Nw))E (S):
(S):
p(o(a)))>0
m(z)x(y)
E
Σ
((01))1100((00))))))))
(a.o)ES ((a.c)) plla,c))>0
(o ((y)
Σ
((00)) p(a,c)
(a.0)ES p((a,c))>0
Σ p(a,c) - P(S) (a,c)ES p((a,c))>0
when S is measurable subset of X' x.. Consequently any E (((oa))15 (16). is also contained Φ. [(u, v) and the two sets are equal.
Chen al., 2022, Lemma A. is easily extended to measures with unequal mass. Although the proof is equivalent to the one in Chen et al. (2022), we will add it here for completeness.
Lemma 67. Let X,Y be finite metric spaces and let (z, dz) be complete and separable metric space. Let éx X > Z and dy : + Z be measurable maps. Consider any μ.x Mc1(x) and Jy E M,)( Then, we have that
inf J OTa((ox)<Mx ((x)))))))xx(())))))))) (e)( Jxxy d(ox(t), x dy).
Proof. Since and y are finite, ox (x) and (by are discrete sets. Then, if we let & = ox x by. ()).T((x,))) (((
follows directly from Proposition 66.
Hence,
inf OTa((ox)=ux, ) (xx(
dz(z), (x(21,22)7ds 22)7 x d22)
inf ( Ix2 dz(z1, dz(z), 220 x d22)
<EI((H.) Ixno inf I ">E((n))
x dy).
Now, following the constraction of the algorithms used to compute the Weisfeiler-Lehmar metric in Chen et al. (2022) and the metrics presented in Grebík Rocha (2021), we phrase an algorithm for computing &IDM for L Ny. We note that instead of using min-cost-flow algorithm Pele & Werman (2009) to solve the unbalanced optimal transport problem, we use linear programming Flamary al. (2021) as is more convenient when working with real values (instead of integers). The unbalaced optimal transport problem can casted into a regular optimal transport problem by adding reservoir points in which the surplus mass is sent Chapel et al. (2020).
Theorem 6. For any fixed L No. &DDD between any graph-signals (G.f) and (H, g) can be computed in time polynomial in L and the size of and H, namely O(L No log(N))) where N (V)
34

---

Published as a conference paper at ICLR 2025
Proof. From Lemma 67 have that
((G) = OT I. - OT ((a.n,)) Avia) (M(M)))))) Av(m)
inf Avul) (V(C) dfM (11a))))()))))))))))) 7(dx x dy).
(H.)),) In order to compute (DDDM((G.F gH, must first compute diD ( for each E V(G) and E (HH.. To do this, we introduce some notation. For each i = 1,.... J, we let C. Dr denote the |V(G)) x [V(H) matrices such that for each a E V(G) and E (
Ci(a, v) = diDM (*)))),))))
(H.)),l)) (())))))))))),))))
Di y) = OT
((0)
We also let Co denote the matrix such that Co == [[(()) g(y)ll for each e V(G) and y E V(H). Then, our task is to compute the matrix Ct.- For this purpose, we consecutively compute the matrices C and Dj for i I,..., L. Given matrix C--1, since (z) (xa))),-(z)) ((..) and (V) = (((H.))-- () computing
OT (0
inf TET(Mi..n)
Ivionven di (xG.)),-((4)) rdd x dy).
reduced to solving the optimal transport problem with C,-1 as the cost matrix and V(G.r) and (((Hx) as the source and target distributions, which can be done in O(Na log(N)) time (Flamary et al., 2021; Chapel al., 2020). Thus, for each i, computing D; given that we know C5-1 requires O(N2. N ()). To get C.. all that remains is to compute the sum D; + C2-1- Finally, we need O(N3 log( N)) time compute (DD f), (H, g)) based solving an optimal transport problem with cost matrix Ct and with (V) and λv(H) being the source and target distributions.
Therefore, the total time needed to compute &DDD ((G,f), (H, is
L O.O log(N)) + O(N
OoN" log(N)) O(L No8 log(N)).
For any N E No. dbDD generates a distance between two graph-signis with number of vertices bounded by N.
G EQUIVALENCY OF MPNNS ON GRAPHS, GRAPHONS, AND DIDMS
Here, we show that, first, for graph-signal fG, the output of an MPNN on G is equal to the output of the MPNN on the corresponding induced graphon-signal (Wa, Jr), similarly to Böker et al., 2023, Appendix C.1.
Lemma 68. Let (G, f) be graph-signal and yp be an Io-layer MPNN model. Let (To)eeV(c) be the partition of (0, 1] used in the construction of (Wa, fr) from (G,f). Then, for all E [4], E (G), and x E Ig.
F(t) = f(p, Wo. fo) g(v,, G. f) 9.
Proof. We prove the claim by induction on f.
Base of the induction. For all V(G) and x E I...
(00) ()) fr(x)) (0)) f(w) (0)))
35

---

Published as a conference paper at ICLR 2025
Induction step. The induction assumption is that f e(t-1)
(t-1)
for all E V(G) and I..
Then, for all v E V(G) and x E Jv. we have
I 12--1) 10.11
f( = p(())
Wo () 10 dyy
= pl0)
fx
p((-1)
1nn uEV(G)
Σ
Wo(z.u)f
(t)
00
Σ
Wo(a, y)
MEV(GG
g ((-1))
Σ
g
g!!)
[V(G)
NEN(F)
Lemma 69. Let (G, be a graph, let (p, be an L-layer MPNN model with readout, Let (Wa: fr) be the induced graphon of (G, f). Then,
@ = ((p, G, 3(p, v. Wa, =:
Proof. Let (Te)eev(c) be the partition of (0, 1] used in the construction (Wa, ff) from (G, f). With Lemma 68, we get
3
v6
(1
P
pg)d\(s))
=
Σ
J.
[0.1]
10
(EV(G)
Σ
0 dd(x)
VEV(G)
lu
Σ VEV(G)
D = 6.
[V(G]
Theorem 70 (Change of Variable Formula), Let X1, be two measurable spaces and a mea- sure on X1. measurable function g on X₂ integrable with respect to the pushforward measure (A) = (A) if and only if the composition go f is integrable with respect to the measure μ. that case, the integrals coincide, i.e.,
J gd(f+H)= = ( go go du. Xx.
x2
Note that in the previous formula X1 = = (X2).
The following lemma related to the absolute continuity of weighted Lebesgue measures with respect to the Lebesgue measure.
Lemma 71 (Billingsley (1995), Theorem 16.11.). Let 8 [0, be a nonnegative measurable function and A C [0, 1] be any measurable set. Denote the measure vs(A) = SA ddX. Then, measurable function [0, 1] r R is integrable with respect vs(A) and only if fō integrable with respect to X, in which case JA fdvs = IA fōd.
Now, we use Lemma 71 to show that the output of MPNN without readout on graphon-signal (W,f) equals the output of the MPNN on the corresponding distribution of computation IDMs ((w.)) (W, f).
Lemma 72, Let (W,J) W. a graphon-signal and yp be L-layer MPNN model. Then, for every [T.] and almost every x 10,
(() = f(p, W. W. = 51()) () (p)rc.))saa)))) = (1)
36

---

Published as a conference paper at ICLR 2025
Proof. We prove by induction on t. Induction Base. We have by definition
( ( f(x)
b (,,0"
(0)
Induction Assumption. Let st S L. We assume that
p(-1) ((-1)
for almost every x E [0, 1]. Induction Step. We have
10 = (00) [1--) / W(x,
[0,1]
Then, by Lemma 71 Vo E [0.1] ((--1) is integrable with respect to (w(z,-)(A)
La W(x, v)d((v) if and only if WWr v) is integrable with respect to A, in which case SA 1 ((-1)) duw(x,-)(u) = JA - v)dA(y). So.
= -000 |
/ [0.1)
1 dew (*)
Hence, by the induction assumption, i.c. Vo [0, ((111) b (ow.ss.e-ts)) we have
( (00) I (t-1)
(+) (01)
Pe in duw((.-))())
(x))
[011]
(00 ( ((
G(1-1)
kw.,),
10.11
p0t)) (1--)) (broen..-100))
btt drw...ss-))) = (**)
H1-1
Once again, by Lemma 71 Vz E [0. 1] x + x is integrable with respect to (W(,,-) if and only if W W(x, y) is integrable with respect to X, in which case SA duw(e.-) SA W(r, (d)))) So, for all C E B(H+-1)
W(z,z)dM1)
Jakkna (C))
duw(a,-)= = (700.))--)).
70k.)),--10)
= uww.Me... fw. (C)) is the push forward measure of ((w.)) The third equality result from the change of variable formula (Theorem 70). Therefore,
where C E H²-1
(C))
(**) (()) (b---1) (o I Ju--
6th (4="dxmen))=)())
= ()) (b (pp.ssttowmstee I ((--1) dp(rt(rs)))) = 500 ma
Hence, all all, we have
p(() (1) ((
37

---

Published as a conference paper at ICLR 2025
Next, use Lemma 72 show that the output of MPNN with readout graphon-signal f) equals the output of the MPNN on the corresponding distribution of computation IDMs
I [(w.)) of (W,
Lemma 73. Let (W, E WLJ let (p, be an L--layr MPNN model with readout, then
8 = B(p, v. W. f) S1p, v, I (w.f).)) =: $
Proof. Recall that for any A E 1(-
f
Tow.n.(A))
J y-
So.
TWW. = (row.).daad
Equality follows from the above remark and Lemma 72.
5 タ
6 (w
HL
(se
6 alxxeennne
He
(Saus
ble (e (())))
(1)n) (LDOx(1))
8.
Hence, it suffices to consider MPNNs on DIDMs. We can summerazie the results of this section in the following lemma.
Lemma 11. Let f) be graphon-signal and (e,, 1) an L-layer MPNN model with readout.
Then, given the computation IDMs (Tr(w,),) and DIDM T ((W.))L. we have that f(ip, W, W) (9)
b(4))
(ow. for any E [L]. x E [0,1], Similarly, B(yp, v. W, = Sh tb P(w.)).)).
H LIPSCHITZ CONTINUITY OF MPNNS
In this section, we prove that MPNNs are Lipschitz continuous. Note that here |I == ess sup [ 11z- for function X' r> TR. (see Definition 44 in Appendix A.12 for more general definition).
H.1 UPPER BOUNDS OF HIDDEN REPRESENTATIONS AND OUTPUTS OF MPNNS
We start by showing that the features of MPNNs bounded. A fact relay on, in the prof of Theorem 13. Recall that we defined the formal bias of a function f T&d +> IR to be [0)
Here, we use the notation B := [|))())))] denote the formal bias of any update function (l)) of an MPNN model & = (
Theorem 74. Let = ) be an L-layer MPNN model. Then there exists a constant B that depends only on L, the number of layers, [| II,, the Lipschitz constants of the update functions and Bets, the formal bias of the update functions, such that
(b(()) &
If up has a readout function vo, then, there exists a constant B that depends only on B and [ the Lipschitz constant of the model's readout function, such that
|5(5, v; l) & B(p,)))
38

---

Published as a conference paper at ICLR 2025
For L-layer MPNN model yp ((l define constant, which (we later show) bounds b(p)_ (4) by B = By when B 2 0 is inductively defined for E {O,..., by
r- 1r-1/o00/11 IL
B (0)) (1-1)
if = 0, 0 < < L,
B
|2 22|10600/1 |I. BB
B
p00
when || ||.. is defined in Appendix A.12 (Definition 43) and > 0 is the radius of H4 = Bd (see Section 2). If additionally the MPNN model has a readout function e., then we define another constant, which (we later show) bounds ( 1/ -)(4), by
B B(p.))) = l1vlle B + B
Proof. Let us now prove the first inequality of Theorem 13 by induction. Let L No and yp (P))e(()) L-layer MPNN model.
Induction Base, For = 0, let T E 7 Bd, the statement holds since
(0)
1000 (T) = (0) - -000/00) +
=
(00)
|| + |0 11 rr. (0)) ||. + B Bro
Induction Assumption. We assume
I B((-1).
for some <ts Induction Step. Let 7 E H', we have
(1)
(t()
b (t-1)
p()-((7): /
=
HC-1
(0())
6 (1-1) p H1--1
- -00) 00.0)
+ |
1()):
6 (1- (1--dpp(tt )) + B B
(0))
6 (
+
715-1
(b(-1)
/ ess sup
(b(-1)
dpu(t)) + Boce
ess sup
-1
7
VEH!-1
2
(00)
6 11-1)
+ <
|0(0
I(t-1) + B Bucc) = B
As this is true for any T, we have
116 S ((O0)
Notice that, for t = T., we get
||6 1lo0 S B.p
The second part then follows from the first by a similar reasoning.
[IMep, bb 12)122 1
-100 (/r (520aa)
(Sne bl
- 2b (0)
++|+((0) (0)ll2
s lwllle 11 6 du
|66000 +B S | B + B
B S |11/l1
39

---

Published as a conference paper at ICLR 2025
H.2 LIPSCHITZ CONTINUITY OF MPNNS WITH RESPECT TO OUR METRICS
To prove that MPNNs are Lipschitz continuous, we follow the proofs of Grebík & Rocha, 2021, Appendix C.2.5.. The next claim trivial result of Claim 23. in Böker al. (2023).
Lemma 75, Let S be Lipschitz. Then,
11 [du //dddd/faa S S 11.1lB ((IV))(--11)))) Ssxs d(x, u)d7(xr,
for every N E V(,, where & is coupling as defined in Section and || llBL is the Bounded- Lipschitz seminorm defined in Appendix A.12 (Definition 45) over Lip(S, IR*), when Lip(S, is the space of Lipschitz continuous mappings + RR".
Theorem 13. Let yp be L-layer MPNN model. Then there exists a constant Cip that depends only on the number of layers L and the Lipschitz constants of the update functions, such that
[b(s,, (1) h1p, (1) CCip
(aDM((,
for all 3, E HL ip has a readout function v/, then, for all u E (HHL), there exists a constant Cie that depends only Cip and the Lipschitz constant of the model's readout function, such that
|,5(,, 1h, 10) - 554,, v, 122 S C(ppa) OT dyose v).
For an L-layer MPNN model ip )= we define constant, which we later show is a Lipschitz constant of (()) by C.p == C,,, when C% 2 0 is inductively defined for (O..... L} by
11
if -1=00 0,
2 2||10()) lI. (116->1) C--1)
if L,
when ||- |I. is defined in Appendix A.12 (Definition 43). If additionally the MPNN model has readout function 4h, then we define another constant, which we later show is Lipschitz constant of ((p, v. ()4), by
C(o.v) == 11 11 || CCp)
Since the features of MPNNs are bounded (Theorem 74), these constants well defined. We now use Lemma 75 to prove the MPNN's Lipschitz property. We show that, given an L-layer MPNN model yo and readout function vb, C₁ and C(gea)) are Lipschitz constants of ((p) (4) and (1,, v. -), respectively.
Proof. Let us now prove the first inequality of Theorem 13 by induction. Let L E No and = (P)bEL4) L-layer MPNN model.
Induction Base. For = 0, y = (1) , the statement holds trivially since (( Lipschitz and 2 (0)
Induction Assumption. We assume that the statement hold for t for <ts L. Induction Step. For the inductive step, we have, by Lemma 75 and the induction hypothesis, for all a, B E H'
| (1)
(t) (()
ll
(a)) [ (1t-1)) dpx((s) p(0))
(16-1) /
byth (pnaaaaaa
H1-1
HC-1
p0/0
|1.
(11 (6 ()))(()) -b
((-11)
1 + g (t-1) dpi(a)
6thh dD-)
(3)
He-1
H1-1
(11 11-1) 1)
(t.c,)
||6 (1-1) BL OT (p((a),
(
|16 (66--1) / = -2|10(0 (1b 1oo + [1b (1 (a
(
(166--1)11> + c(-1) daDM(aa, B) = C CadiD
40

---

Published as a conference paper at ICLR 2025
The second inequality results from combining induction with Lemma 75. Hence, get the first part of Theorem 13. Notice that, for t = L, we get
l (L) b/3 2 1l2 S CodiDx
The second part then follows from the first by a similar reasoning. For all 14, u E P(LL) we have
[1 20, p1) h(2, 1h, 2) = 1 (Fre
dz)
- (Fr 6t5h dv
114/11..
b du
bl
H6
H4
|
OT
a (H,
BL
11
(
+ +1105%
OT ooffoon (1,
= 11
(65
+ +C+
OT
affere
(1.
1|
6
+ CGp)
OT
dibM (1,
C(v.v) OT
dion (1,
The second inequality is result of Lemma 75 and the Lipschitzness from the first part of Theo- rem 13. For the sake of completeness, we state Theorem 13 as an epsilon-delta statement.
there ō > 0 such that, for all order-t DIDMS μ and v, if OT dirs (1, S 5, then (15( Vi, 14) - 5tp, th, v) ll2 S for every L-layer MPNN model y with readout function vb IRdz. - Rd with C(e.,) C.
Theorem 76. Let d >> be fixed. For every I. No. C > and
Proof. Follows immediately from Theorem 13.
I UNIVERSALITY AND FINE-GRAING EXPRESSIVITY OF MESSAGE-PASSING NEURAL NETWORKS
In this section we first prove our universal approximation theorem for MPNNs on IDMs and DIDMs, showing the sets N2 and NN, are dense C(H', IR) and (H)), R), respectively. We then conclude universal approximation theorems for MPNNs on graph-signals and graphon-signals.
1.1 UNIVERSALITY MPNNs OVER THE SPACES OF IDMs AND DIDMS
The proofs of Lemma 78, Theorem 15, follow the proofs of Lemma 25, Theorem 4, and Theo- rem 6 in Böker et al. (2023), respectively. This follows by inductively applying Seierssessss theorem, cf. Appendix A.5, to the set N2- Given that N2 satisfies all requirements of the Stone-Weierstraal theorem, Corollary 12 yields that Ni separates points, which allows us show that Wt+1 again satisfies all requirements the Stone-Weierne Weierstrass theorem. We recall the canonical projections were denoted by Pt.j He + Hi and PL H M when j L < cc. We first introduce function Cartesian product.
Definition 77 (Function Cartesian Product). Let f Xi + y and g X2 + Z be two functions.
We define function Cartesian product as the function f x 9 X. x X₂ + y x Z such that (f x ()) x22) = (x(1), ((x))) ) for (I1, x2) E X2 x X2.
Given set A, recall that denote by 1A - R a non-zero constant function. Let s, of be two L-layer MPNN models. Define Emmi ((x, r) = x. y and Eada((x, == x + c y for all y, R. where IR is fixed. Then, define
Pmull (0) x (((")) ..... (() ((()) Emmil (1((+1) ((++2)))
and define Padd analogously via Endd-
41

---

Published as a conference paper at ICLR 2025
Lemma 78. Let 0 S cc. The set Ni are closed under multiplication and linear combinations, contains 1 and separates points of H."
Proof. We will now prove the lemma inductively.
Induction Base For 1 - O, the claim trivially holds as Ng contains precisely the functions f 7t0 + R that are Lipschitz continuous which contains 1 and closed multiplication and addition.
Induction Assumption. We assume the sets No is closed under multiplication and linear combina- tions, contains 1zt and separates points of 7t*
Induction Step. Let + 1. Clearly W1+1 contains the all-one function 1ge since we can always choose (c(++) in MPNN model to be the all-one function on any of the two inputs. Let y,, so' be two (t + 1l-layer MPNN models. Note that (mmul and Padd are in fact MPNN models since multiplication and addition on compact, and hence, a bounded subset of I is Lipschitz continuous.
Let a, B 7 with a + 3. We consider two cases: either Pr+1 (ax) + (3+1 or Pt+1,r(a) o (B). We start with the first case, i.e., Pt+i(a) * P3+1 By the induction hypothesis, the set .²2 is closed under multiplication and linear combinations, contains 1 and separates points of Ht. Hence, it is sub-algebra of C(H'' IR) that separates points and contains the constants. By the Stone-Woor Weieesesssssssss theorem, .V! is dense in C(H', R). Corollary 36 then entails that there is t-layer MPNN model y with output dimension one such that
da)+ # [ dp:+1.))))33)
(3).
Define the (t 1)-layer MPNN model s == yED where y((1) (l for i (((++1) (x,z) = y for every (a,y) RR2 Then, sp' EN separates a and since
[t] and
g1(+1) (8 xx) / h(v') dpi+i(a)
-h (a)+ * / h(y)) dp
74
-f (B) (1()
In the second case, where (a) F (B), we have that, from the induction assumption, there
exists 1-layer MPNN model & such that (((2) (1)
((a) # (())))))))) (()) Define the (1 + 1)-layer
MPNN model ø' == / where (²(+)) ((6)) for [1] and 1 (x, = for every
(a., v) E R.2 Then, & E N, separates and 8 since
b())) =b((')((()))) ((0)))
((() (4)
(a) # b(() (1)
(1)1,(0)
-b(0) b(0')p.... = b(()) (1+1) (1+1) (1))
With Lemma 78, we immediately obtain Theorem 15, which we restate here for better readability.
Theorem 15 (Universal Approximation). Let L E No. Then, the set N7, is uniformly dense in C(HL, R) and the set NN is uniformly dense in (HH(H)),
Proof. By Lemma 78, the Weierseissss theorem is applicable to N2, and hence, NE is dense in C(HL" R). We can then use this to show that .NN is dense C( (H!)) RR.. By the same arguments as in the first case of the inductive step in the proof of Lemma 78, NN is closed under multiplication and linear combinations, contains the all-one function, and separates points of (HH*). Hence, application Corollary 36 yields that NN2 is dense in (H² RR.
).)).
Theorem 15 then yields Corollary 12. To prove Corollary 12, we follow the proof of Corollary in Böker al. (2023).
42

---

Published as a conference paper at ICLR 2025
Let L Ny and d > 0 be fixed. Let (HL and (vt); be sequence with Vi E (H.)). Then, V4 - V if and only if (i 1, - Silp, v, for all L-layer MPNN models ip with readout functin vb R + Rd.
Corollary 12.
Proof. First, let = 1. When restricted to functions ((p, 4, -) E NNV of the form 51p, v.V) Ja.. 6l5h dv, i.e., the readout db is the identity, the claim follows since N2 is dense in C(M,, RR by Theorem 15 and the definition of the weak" topology on P (MLz). ef. Section 2. Since the readout function v is continuous, the equivalence also holds when considering all functions in the set .VV Finally, since one can always consider the projection to a single component and conversely map a single real number vector of these numbers, the equivalence also holds in the case n > 0
1.2 PROOF OF
EXPRESSIVITY OF MPNNS
Here, we present the proof of Theorem 14, which we copy here for the convenience of the reader.
Theorem 14. Let d > 0 be fixed. For every = > O. there are L E Ny. C' > O, and > 0 such that, for all DIDMs μ. P (HL). if [|S(,, v. b.H)) h1pp b.vill S holds for every L-layer MPNN model yp with readout function ub Rd + R when ((..)) S C, then OT diroa (H, v) S.
0 such that such T. No. C> O, and ē 0 do not exist. Then, for every T. E and C > 0 5c == 1/k 2 O, there are I.-layer DIDMS lAk and us such that [15 10, (4)) (5p vi, (b)l2 S 6g for every L-layer MPNN model (4p, with readout and output dimension d, and C(p.,) S C but also OT OT doo (HK, vk) > E. By the compactness of (H²), there are subsequences (mu)) and (uRz); converging to DIDMs jí and D, respectively, in the weak" topology. Let be an L-layer MPNN model and a readout fucntion & Idd Rd. Then, by Corollary 12, also (55 v. )), and (5(@, G vk.))s converge to S(@ &.. (D) and 55 d. (,7). respectively. Hence,
Proof. Assume that there is
|| (100))5(($10))))) Ml12 < <155(,,, - 5,(,, (k)
+ || &. vx.)) - -5( &i, /, )
+ || &. mk.) - 5569, & Ml i
5 $. D). Since this holds for every MPNN model and Lipschitz vb, we have OT foo (p, 0 by Corollary 12 and Theorem 4 with the fact that P (H!)) is Hausdorff. Then, however
by the assumption, i.e., 5(6, G. pi)
OT affors (1K,, Pk.) S OT (1k,, p:) + OT diDs (7,, 7) + OT
k00 0 difoms (ū, vk.)
since (Uk,)s and (Juz)); converge to V and jı, respectively, also in OT difoss by by Corollary 12 and Theorem 4. This contradicts the assumption that OT doo (Hi Uss)) for every 2 0.
1.3 UNIVERSALITY OF MPNNs OVER THE SPACES OF GRAPH-SIGNALS AND GRAPHON-SIGNAA
Note that Theorem 15 states that any continuous function from DIDMs to scalars can be ap- proximated by an MPNN on DIDMs. To infer a universal approximation result for functions from graph-signals vector we emphasize the following considerations. Recall we define the set NW (3(p, -) W.C. (d v)) an L-layer MPNN model with readout). First, note that the space of computation DIDMs, (WCC), which is not dense (w.r.t ofID in view of Theorem 64. Indeed, there are DIDMs that do not come from any graphon-signal, and a closed strict subset cannot be dense. Hence, the space of DIDMs of graph-signals is also not dense. Hence, Theorem 15 does not imply that any continuous function (w.rt (DDM)) from graph-signal to vector can be approximated by AN L. Rather, any function on graph-signals that can be extended to a continuous function DIDMs can be approximated by NNV, which is weaker form of universality. Fortunately, can directly prove universal ap- proximation theorem directly for the space WCJ, which in terms gives universal approximation
strict subset of (H!),
43

---

Published as a conference paper at ICLR 2025
theorem for continuous functions from graph-signals to vectors by density argument. For this, prove Theorem 79 stating that graph-signals are dense in WC, w.r.t 1DDD.
Theorem 16. Let L E No. Then, the set NNT,WWE.) is uniformly dense in C(W), R).
Proof. By Theorem 64, the space of graphon-signals compact. With similar arguments presented in the proof of Lemma 78, WNT,WWE" is a subalgebra of COWE,, Lemma 11 together with the fact that NN2 separate points (see the proof of Theorem 15) yields that (MWC( separate points. We can thus apply the Stone-Weierstrass, theorem to (MVC)) hence, (WW is uniformly dense in C(WC) R).
Theorem 79, Let No. Graph are dense W.O,, w.r.t. DDDD
Proof. A direct conclusion of the graphon-signals regularity lemma (Theorem 42) w.r.. the cut dis- tance, 8g, is that graph-signals are dense in the space of graphon-signals w.r.t. 8 i.e. (WC,, du). For any No. Theorem 63 implies that the pseudometric topology of (WC2 o (IDM) cooraser than pseudometric topology of (WC,, d Thus, since graph-signals are dense (WC,, on), graph-signals dense in raph-signals dense in the space of graphon-signals w.r.t. 6hmDM i.e., (WC), OIDM).
J PROXIMITY RELATIONS OF MPNNS
Here, we summarize how proximity of any MPNN's outputs on any two different DIDMs is related to the proximity of the two DIDMs.
Theorem 80. Let L No and (Hi) be sequence of order-L DIDMs, and let μ e (HL be DIDM. Then, the following are equivalent:
1. OT dios (1is 1)) + O.
2. hn, + for any MPNN model yp with readout vp Rd + R where d >> 0.
3. 14 - μ.
Proof. The implication (1) (2) just a result of Theorem 13, and its converse is Theorem 14.
Properties (1) and (2) are equivalent to (3) by Theorem 4 and Corollary 12.
We further note that the following variant of Theorem 80 holds as well. Theorem 81. Let u E (Hth). Then, the following are equivalent:
1. OT diss (H,V) = O.
2. h,. for every MPNN model ip and a readout function 1d - R2" where O.
3. μ =
Proof. The equivalences follow as in Theorem 80 since (H.*) is Hausdorff.
K GENERALIZATION THEOREM FOR MPNNS
We expand the generalization analysis in Levie (2023) to a more general setting as done in Rauch- werger & Levie (2025) and adjust it to meet our definitions.
44

---

Published as a conference paper at ICLR 2025
K.1 STATISTICAL LEARNING AND GENERALIZATION ANALYSIS
In statistical learning theory, usually we consider a product probability space P = X x V which represents all possible data. We call any arbitrary probability measure (P,B(P) a data dis- tribution. We presume we have a fixed and unknown data distribution т. As the completeness of our measure space does not affect our construction, we may assume that we complete (P) with respect to T to complete o-algebra D or just denote Σ = B(P). Additionally, let X C P be dataset of independent random samples from (P:7). Additionally, we presume y contains values that relate to every point in X, according to a fixed and unknown conditional distribution function Tylx E ())). ) its essence, the problem of learning is choosing from some set of function, the one that best approximate the relation between the points in y and the points in X'.
Let be a Lipschitz loss function with a Lipschitz constant denote by Ce. Note that the loss & can have a learnable component that depends on the dataset X as long as it is Lipschitz with constant Cg. Our objective is to find the optimal model D from some hypothesis space that has a low statistical risk
R(D) = (( v)] - E(MN(V), v) v), DN E Z
However, stated before, the true distribution 7 is not directly observable. Instead, have access to a set of independent, identically distributed (i.i.d) samples X = (X1...., Xx) from the data distribution (P. Instead of minimizing the statistical risk with unknown data distribution т, we try to approximation the optimal model by minimizing the empirical risk:
1 N = N
(x
Σ (v:),
where < i S N X, (u, Y,) and My model with some possible dependence on the sampled data, e.g., through training.
Generalization analysis goal is to show that low empirical risk of a network entails low statistical risk as well. One approach to bounding the statistical risk involves using the inequality:
( S R(M) + E
where E is called the generalization error, defined as:
E sup RR(0) - R())
BEH
It is important note that the trained network Dt Vix depends the dataset X. This essantially means that the empirical risk is not truly a Monte Carlo approximation of the statistical risk in the learning context, as the network not constant when varying the dataset. If the model 2 was fixed, Monte Carlo theory would provide us an order O ((V((p)/N) bound for with probability 1 where ((p) depends on the specific inequality used (e.g., ((p) = log(2/p) in Hoeffding's inequality).
Such events are called good sampling events and depend on the model Mt. This dependence, result in the requirement of intersecting all good sampling events in Z, order to compute a naive bound to the generalization error.
Uniform convergence bounds are employed to intersect appropriate sampling events, allowing for more efficient bounding of the generalization error. This intersection introduces a term in the gener- alization bound called the complexity or capacity. This This concept describes the richness of the hypothe- sis space Z and underlies approaches such as VC-dimension, Rademacher dimension, fat-shattering dimension, pseudo-dimension, and uniform covering number (see, e.g., Shalev-Shwartz & Ben- David (2014)).
K.2 UNIFORM MONTE CARLO ESTIMATION FOR LIPSCHITZ CONTINUOUS FUNCTIONS
Recall that the covering number of a metric space (X'd) is the smallest number of open balls of radius needed to cover A' (see Appendix A.4.6). We call any metric space with probability Borel
45

---

Published as a conference paper at ICLR 2025
measure (where we either take the completion of the measure space with respect to Jl, ie. we add all subsets of null-sets to the o-lgebra, or not) a probability metric spaces. The proof of Theorem 17 relies on Theorem 82, which examines uniform Monte Carlo estimations of Lipschitz continuous functions over probability metric spaces with finite covering. Theorem 82 is an extended version of Maskey al., 2022, Lemma B.3 taken from Levie (2023).
Theorem 82 (Levie (2023), Theorem G.3, Uniform Monte Carlo Estimation for Lipschitz Con- tinuous Functions). Lef P be probability metric space with probability measure l and covering number k((). Let Xı,..., "i...,,N be drawn i..d. from P. Then, for any p > 0, there exists an event Lip CPN (regarding the choice of (X1,..., .N))),)) with probability
n. (ELsp)) 21-P
such that for every (X1...., E Lág sor every bounded Lipschitz comtinuuus J :PP.
Ba with Lipschitz constant L,, we have
| ((x)du(z))
1 N
Σ f(X))
1 v2 ( (N)
(1+ vlog(2/p))
where E(r) k(r)) log((((())
g-1 1 is the inverse function of & and n(()) is the covering number P.
K.3 A GLOBAL LIPSCHITZ CONSTANT AND UPPER BOUND OF FEATURES OF MPNNS
Recall that we consider the space of IDMs of order-0 be 7 B (<r E Rd || 5r) Rd (for a fixed > 0). Moreover, recall that we defined the formal bias of function f Rd + Rd be [[ || (Maskey al., 2022; Levie, 2023) and the smallest Lipschitz constants of f as II (see Appendix 1.1 To apply Theorem 82 in our setting, we phrase the following theorems, which show that, under some assumptions, features of MPNNs are bounded Lipschitz Continuous Functions with a bound and Lipschitz constant that do not depend on the specific MPNN model. Theorem 74 and Theorem 13 straightforwardly lead to Corollary 83 and Corollary 84, respectively.
Corollary 83. Let r > O (such that 7 BB)). Assume there exist constants A > O and A2 > O, such that the Lipschitz constants || lr. of (p()) satisfy ||, I Aı and the formal biases (1((0)(()) (0))l of pl9) satisfy (])(1 I A2. for any t E [L] and any L-layer MPNN model up (10(0) ==-" Then there exists a constant B₁ that depends only on L, Ai and Az, such that
Ib(p) 1o: SB.
If. in addition, the Lipschitz constant |lll of db satisfies || I A₁ and the formal bias ([)(l of satisfies [|0)( & A2, for any readout function vb then, there exists constant Bg that depends only on L, Ai and A2, such that
|15(1,, v, -) B2.
Let A1, Ag. Define by B1 = B² and B2 = AiB1 + Ag, when B 2 0 is inductively defined for t te {O...., L} by
[AA + A2 [2A ((t-1) + A2
if = 0,
B
if0 <I
Based on Theorem 74, it easily follows that B, and B2 provide upper bounds for h(p) 5(p, v. -) for all (se, v) that satisfy the above assumptions, respectively.
(4) and
Corollary 84. Assume there exist constants A₁ > and Ag > O, such thas the Lipschitz constants (0)]l2 of satisfy (0) <
|| ll., opt) satisfy [| ||, A1 and the formal biases [p(()(
A2, for any [L] and any L--ayer MPNN model yp = ( Then there exists a constant C₁ that depends only on L and A and Az, such that
())(), byp, 1) C2 dafoaaaa 8),
for all 3 E H.. If. in addition, the Lipschitz constant lRbbll, of sb satisfies |R S A and the formal bias (b6(0) of va satisfies [[)(( S Az for any readout function v. then, for all p,, E (HL there exists a constant C2 that depends only on L,, A and B, such that
[1 1h, 14) 50yp, v. 2)]l2 C2 OT TTalov ().
46

---

Published as a conference paper at ICLR 2025
Let A1, A2 O. Define by C1 C² and C2 == A1(B1 C1), when C* 2 i inductively defined fort E {O....,L) by
A1
= 0, if < t L,
C² = (B
B is defined for (0,,,T] in Equation (9), and B₁ = B Based on Theorem 13, it easily follows that C₁ and C2 are Lipschitz constants of ((v) and $1 v: -) for all (1,, 1) that satisfy the above assumptions, respectively.
K.4 A GENERALIZATION THEBORE FOR MPNNS
In classification tasks our goal is to classify the input space into K classes. We look the product probability metric space p = X' x I when the metric space (X' d) is either (HH*) OT OT dhose or (WCy, fIDM). and use L-layer MPNNs with readout. Our loss & is a Lipschitz loss function with a Lipschitz constant Cş and our output vectors are vectors E RRK, Each entry (ū)s of an output vector U. depicts the probability that the input belongs to class 0 < k: S K. Although loss functions like cross-entropy are not Lipschitz continuous, composing cross-entropy on softmax is Lipschitz continuous, which is usually how cross-entropy is being used. Recall that defined the formal bias of a function f IR + IRda to be [[f())]2 (Maskey et al., 2022; Levie, 2023) and the smallest Lipschitz constants of f as || Il (see Appendix A.12).
Fix L E N and A2 > Let be the set of all L-layer MPNN models with readout ((o re(z) . wb)
such that the Lipschitz constants ||<] and _| are bounded by A1 and the formal biases (lx) and (0)]2 are bounded by Az. Consider a Lipschtiz continuous loss & with Lipschtiz constant Ćz. In Appendix K.3, We show that there exist Ce. B > 0 that depend on L, A1, A2 such that @ S Lip(X' Ce. Be). Here, Lip(X', Ce, Ba) is the set of all bounded Lips- chitz continuous functions f X' - RR with bounded Lipschitz constants Il/ S Cg and with bounded norms || < Be. As result, if we prove a generalization bound using Lip(X', Ce, Be) as the hypothesis class, the bound would also be satisfied for the hypothesis class O.
Lemma 85. Ler 27 Lip(X' Ce, Be) and & loss function with Lipschitz constant Cg. Then [E(2)(-), +1xx I Ca + 1) [8(0, 0)l and [|E(20(.), -Il... S Cg max(Ce, 1). Proof. For the first inequality,
|8 |8(2(()) v)1 |E(2N()),) v) E(0,0) (8(0,0) +(000))(1((00)
s C=()) + [Ivll2) + (E(0,0)
(c((( + 1)+ +)(0000)))
Thus,
([)))))))) 21.0 I C=(119 + +1)+ - CB + +1 (E(0,
For the second inequality,
[8(2)(z), y) - -((2(2')) (=(()2((=) - M())))
2| 2 + 11 v/ l12
I (=(Cd(( + |lv - s/ll2)
< Ce max Co, ()(d(z, + 11 v112).
Although the covering numbers of the DIDMs' spaces and the graphon-signals space are currently unknown, the graphon-signal space might have a smaller covering number. This can potentially improve the generalization bound, thus stating the theorem for the graphon-signal space is indeed a meaningful fact. Thus, we express our generalization bounds on the space of DIDMs, which is mathematically more general than formulation the space of graphon-signals and on the space of graphon-signan signals. Following the proof of Theorem G.4 in Levie (2023), we prove the next theorem via Theorem 82.
47

---

Published as a conference paper at ICLR 2025
Theorem 17 (MPNN generalization theorem). Consider the above classification setting with X being either (9H( OT diiDss ( DUDRA) Let C Cg max(Ce, 1). B Ce + 1) + [(,,0)) O)} and {Xsli=1 be independent random samples from the data distribution (X (0,1) 1, T, Then, for every p> O, there exists an event Up C (X x {0, 1)x)* regarding the choice of X (X1,..., .N), with probability T (UP) 2 1 p. in which for every function Mix in the hypothesis class Lip(X, Ce. Be), we have
R(22xx) Rx xXxxxx
<E 2C
J
(1+ Vlog(2/0))
where E(c)
x(e)² Log((e))))))
is the covering number of the compact space X {0, 1)x and {
is the inverse function of
Proof. From Theorem 82 we get the following. For every p > O, there exists an event Ef c x
regarding the choice of (X1....,.x) (X {0, {0.1)K)² where X, (vi, Yi) for is E X,
Y; {0, 13 and i < N, with probability
(ELL))) 2 1-ppp
such that for every function 2t in the hypothesis class Lip(X, Ce, Be), have
/ E(DT(V). (dd((,)))
1
{(2((s)) Yi)
(10)
N
(N) 2 (211((9T(() ()) (1), (2) (1 vlog(2/p))
(11)
1 B (1+ (1og(2/p))
(N) 220+
(12)
V2
where C(N) =(AN) x(() () is the covering number of X' x (0, 1}K and a N
1 is the inverse
function of ç. In the last inequality, we used Lemma 85.
Since Equation (10) is true for any M E Lip(A', Soll'CCa Ce, Be), it is also true for Mix for any realization of X, so we have
(N) 22C+ 1 B (1 (1+ /log(2/p)) v2
R(2xx) - (2 (N)
L PROKHOROV'S DISTANCE FOR DIDM METRICS
For completeness, we show an alternative approach to define metric graphons through IDMs and DIDMs using Prokhory metric.
L.1 DEFINITION AND BASIC PROPERTIES OF PROKHOROV'S DISTANCE
Let X be complete separable metric space with Borel o-algebra B. We define A : {y S d(æ, y) < for some x E A} for a subset A C X and 2 0. Then, the Prokhorov metric P on Ms1 (X, B) is given by
Pa(u, v) = inf 01 ((A) S ((Aa) + and v(A) S p(A)) + for every B}.
The following theorem shows that Prokhorov metric is topologically equivalent to OT, on any complete separable metric space (X,d).
Lemma 86 Prokhorov (1956), Theorem 1.11). Let (X, d) be complete separable metric space. Then, (X), is a complete separable metric space, and convergence in Pa is equivalent to weak" convergence measures.
48

---

Published as a conference paper at ICLR 2025
The following definition presents alternative metric to DIDM (see Section 3). Definition 87 (DIDM Prokhorov's Distance). Given two graphon-signate (Wa fa), (Wo, fo) and L I, the tree prokhorov's 's distance between (Wa: fa) and (Wo, f6) is defined as BbNDM(WW.. fa), (Wbr f6)) = Pfpbb
PfiD (WWa.Ja))Ls (.W.J.)).o.F(wo...)).....
(Wo...))..
By following the proof of Theorem 4, with Lemma 86, the following result is obtained.
Theorem 88. Let L E No. The metrics PiDM on Hi, P Pibu on (HH*) and Mzi(H!) are well- defined. Moreover, P Prie metrizes the weak" topology of (zHl" and (HL)).
Except for the computability (Theorem 6), all the results in this paper, can be rephrased using PIDM- P Pfoxx and PÉIDM instead of d'DM- OT dixx" and 6IDD-- The only that remains, is to discuss PÉIDM compatibility.
L.2 COMPUTABILITY
The metric PÉIDM is polynomial-time computable. Böker et al. (2023) prove the Lemma 89 by generalizing observation in Theorem 1 Schay (1974) and Lemma Garefa-Palomares & Giné (1977) to finite measures to finite measures and show that value of p(e) == inf > 0 и{A)) S + ((Af)
for every A C S] be computed through a linear program. Additionally, they based their conclusions on Garel & Massé (2009), which deals with the computation of P& on (possibly non-discrete) probability distributions.
Lemma 89 (Böker et al. (2023), Theorem 16.). Let u.v E M(X), where (X, d) is a finite metric space with X' { Jn Then, the Prokhorov metric Pa(p, v) can be computed in time polynomial in n and the number of bits needed to encode d, μ and v.
By following Theorem 6, with Lemma 89, the following result is obtained.
Theorem 90. For any fixed L E No, TbIDM between any two graph-signals (G, and (H,g) can be computed in time polynomial in h and the size of G and H,, namely O(L N2) where N (G))
The computational advantage of using unbalanced optimal transport, tipped the scales in favor it, making it the main focus of this paper.
M ADDITIONAL EXPERIMENTS AND DETAILS
We present here additional experimental results. We evaluate 3IDM in graph classification tasks, ie., graphs separation tasks. We follow the same set up in Chen et al. (2022); Böker et al. (2023) for comparison. The goal of our experiments is to support the theoretical results which formulate a form of equivalence between GNN outputs and DIDM mover's distance. We emphasize that our proposed DIDM mover's distance metric mainly a tool for theoretical analysis and the proposed experiments are not designed to compete with state-of-the-e not intended to be used directly as a computational tool, our results suggest that we can roughly approximate the DIDM mover's 's distance between two graphs by the Euclidean distance between their outputs under random MPNNs. This Euclidean distance can used in practice as less computationally expensive than DIDM mover's 's distance.
methods. Although our metric is
M.1 1 -.EAREST-NEIGHHOO CLASSIFIER
The goal of the experiment in this section to show that the geometry underlying the metric dDIDM captures in some sense the underlying data-driven similarity related to the classification task. We consider the problem of classifying attributed graphs, and a solution based on the 1-nearest neigh- bor.
The 1-Nearest Neighbor (1-NN) classifier is a non- non-parametric, instance-basee machine learning method. Given a dataset D {[(G,, (.) where (G,, f,) represents graph-signals and y C denotes class labels from a finite set C, the goal is to classify a new input (G,, f.). The classification process of classifying the input (G, involves:
49

---

Published as a conference paper at ICLR 2025
1. Computing the distance between the imput (G, f) and every point (G,, f.) in the dataset using a distance metric d.
2. Identifying the nearest neighbor (Gk, fiz) such that:
(Gk, fR) = arg min d((G, f), (.). FEn
3. Assigning the label ys of the nearest neighbor as the label y of (G,f):
-
based iteratively defined metries. Tree Mover's Distance TMD* from Chuang & Jegelka (2022) is defined via optimal transport between finite attributed graphs through so called computation trees. The Weisfeiler-Lchman (WL) distance d/ and its lower bound distance dWi) 2. from Chen et al. (2022; 2023) are defined via optimal transport between finite attributed graphs through hicrarchies of probability measures. The metric dw.L from Böker et al. (2023) is define via optimal transport on a variant of IDMs and DIDMs where the IDMs are not concatenated. The metric dw.2L. from Böker al. (2023), a variation of ów. where the maximum number of iterations performed after having obtained a stable coloring is bounded by 3. Unlike ÓDIDM, all the above metrics cannot be used to unify expressivity, uniform approximation and generalization for attributed graphs. Namely, the above pseudometrics are either restricted to graphs without attributes or are not compact.
Here we chose compare 6iDM with other
Table 1 compares the mean classification accuracy of 8w,3, 8w.23 (Böker et al., 2023), dWL (33) diL.R.23 (Chen et al., 2022; 2023), TMD (Chuang & Jegelka, 2022), and DIDM in a 1-NN classification task using node degrees as initial labels. We used the MUTAG dataset (Morris al., 2020) and followed the same random data split as in Chen et al. (2022); Böker et al. (2023): 90 percent of the data for training and 10 percent of the data for testing. We repeat the random split ten times. We started by computing the pairwise distances for all the graphs in the dataset. We continued by performing graph classification using a I mnearest-neighhee classifier (1-NN).
We note that the 1-NN classification experiment "softly" supports our theory, in the sense that this experiment shows that our metric clusters the graphs quite well with respect to their task-driven classes. We stress that this experiment does not directly evaluates any rigorous theoretical claim. We moreover note that while the metric in Chen er al. (2022) achieves better accuracy, the space of all graphs under their metric is not compact, this metric does satisfy theoretical requirements: a compact metric which clusters graphs well.
M.2 MPNNs INPUT AND OUTPUT DISTANCE CORRELATION
As proof of concept, we empirically test the correlation between 6iDM and distance in the output of MPNNs. We hence chose well-known and simple MPNN architectures, varying the hidden di- mensions and number of layers. We do not claim that GIN Xu et (2019) and GraphConv Morris et al. (2019) are representative of the variety of all types of MPNNs. Nevertheless, they are proper choices for demonstrating our theory in practice.
M.2.1 MPNN ARCHITECTURES
The GIN mtanmpalo model is variant of the Graph Isomorphism Network (GIN) (see Ap- pendix 1) designed for graph-level representation learning. Each layer consists of normalized sum aggregation and a multi layer perceptron (MLP). The first MLP consists of two linear transfor- mations, ReLUU activations, and batch normalization. Each MI.P that follows has additionally skip connection and summation of the input features and output features. The readout after T. layers mean pooling (with no readout function).
The GC GC.meanpool model a realization of graph convolution network (GCN) for graph-level representation learning. Each layer consists of normalized sum aggregation with linear message and update functions (see Appendix D for the definition of message function and for the equivalency between MPNNs that use message functions and MPNNs with message functions). All layers except the first layer have additionally a skip connection and a summation of the input features and output features. The readout after T. layers is pooling (with readout function).
50

---

Published as a conference paper at ICLR 2025
M.2.2 CORRELATION EXPERIMENTS ON GRAPHS GENERATED FROM STOCHASTIC BLOCK MODEL
We extend here the experiments presented in Section 4, with the same experimental proce- dure and also offer an extended discussion and description of the experiments. We empiri- cally test the correlation between o dIDD and the distance in the output distance of MPNN. We use stochastic block models (SBMs), which are generative models for graphs, to generate random graph sequences. We generated a sequence of 50 random graphs {G, each with 30 vertices. Each graph is generated from an SBM with two blocks (communities) of size 15 with p 0.5 and qi = 0.1 + 499 probabilities of having an edge between each pair of nodes from the same block different blocks, respectively. We denote G := G49, which is an Erdös-Réng model. We plot BinDa G) against distance in the output of randomly initialized MPNNs, i.e., once against [[5G meanpool, G,) 55GCC meappoll, Gl and once against G.) - (GGC meanpool, G) 2- Note that in each experiment, we initialize GTN meanpool 1 and GC mea npool only once with random weights and then compute the hidden representations of all graphs.
We conducted the entire procedure twice, once with a constant feature attached to all nodes and once with a signal which has a different constant value on each community of the graph. Each value is randomly sampled from a uniform distribution over [0, 1]. In Section 4 We present the results of the experiments when varying hidden dimension (see Figure 2). Figure 6 and Figure 7 show the results when varying the number of layers when the signal is constant and when the signal has different randomly generated constant value on each community, respectively. The results still show a strong correlation between input distance and GNN outputs. When increasing the number of layer, the correlation slightly weakens.
We conducted the experiment one more time with signal values sampled from a normal distribution 40_1 Figure 8 and Figure 9 show the results
(1,, o.) with mean = and variance a; 49 when varying the number of dimensions and the number of layers, respectively. The results still show a correlation between input distance and MPNN outputs, but with a higher variance, As we interpret this result, the increased variance could be an artifact of using random noise as signal in our experiments. The specific MPNNs we used, have either linear activation or a ReLU activation function. Thus, they have a "linear" averaging effect on the signal, which cancels contribution of the noise signal to the output of the MPNN, while the metric takes the signal into full consideration. This leads to a noisy correlation.
sense the
M.2.3 REAL DATASETS CORRELATION EXPERIMENTS
We empirically test the correlation between 1IDM and distance in the output of MPNNs on MUTAG and PROTEINS databases. In the following, we present the results that showcase insightful relations.
Correlation experiments using single randomized MPNN. Denote by D generic dataset. For the entire dataset we randomly initialized one MPNN with random weights. We randomly picked an attributed graph from the dataset (G, E D. For each (G, E D we computed D ((C, (),()),,,, ()).)) We plotted the distance in the output of the randomly initialized MPNNs on each ff E against IIDM((C f). (G, We conducted the experiment multiple times. Figure 4 and Figure 5 show the results on MUTAG when varying the number of dimensions and the number of layers, respectively. Figure 11 and Figure 12 show the results on PROTEINS when varying the number of dimensions and the number of layers, respectively.
Correlation between DIDM model's distance and maximal MPNN distance.
Corollary 12 states that "convergence in DIDM mover's distance" is equivalent to "conver- gence in the MPNN's output for all MPNNs". The previous experiment depicts Corollary 12 only vaguely, since the experiment uses single MPNN, and does not check the output dis- tance for all MPNNs. Instead, in this experiment we would like to depict the "for all" part of Corollary 12 more closely. Since one cannot experimentally apply all MPNNs on graph, we instead randomly choose 100 MPNNs for the whole dataset. Denote the set con- taining the 100 MPNNs by N'. To verify the "for all" part, given each pair of graphs, we evaluate the distance between the MPNN's outputs on the two graphs for each MPNN and return the maximal distance. We plot this maximal distance against the DIDM mover's
51

---

Published as a conference paper at ICLR 2025
and maxsex" [|5(GTN_meampoo]) G,) 50sc_mearpool,, G) against BIDM G). Note that in each experiment, we initialize @IN_mennpool and GC GC.meanpool only once with random weights and then compute the hidden representations of all graphs.
distance. Namely, plot maXgeN' [|5(GIN.meanpool, G²) -
In more details, we checked the extent to which & correlates with the maximal distance of 100 MPNNs' vectorial representation distances MUTAG dataset and marked the Lipschitz rela- tion. Here, we randomly generated 100 MPNNs for the entire dataset. Figure showcase different Lipschitz relation. Note that the results normalized.
From this, one can estimate bound on the Lipschitz constants all MPNNs from the family.
The Random MPNN Distance conjecture. Observe that in experiments MPNN's output distance for random MPNNs, not for "all MPNNs," " and still got a nice correla- tion akin to Corollary 12. This leads to the hypothesis that randomly initialized MPNNs have fine-grained expressivity property: for some distribution over the space of MPNNs, a sequence of graph-signals converges in DIDM mover's distance if and only if the output of the sequence under random MPNN converges in high probability. See Figure 10 for comparison of BIDM 's correlation with the maximal distance of 100 MPNNs' vectorial representation distances, with DIDM 's corre- lation with the mean distance of 100 MPNNs' vectorial representation distances, and with BIDM'S 's correlation with single MPNN's vectorial representation distances on MUTAG dataset.
plotted the
52

---

Published as a conference paper at ICLR 2025
Table I: Graph distances classification accuracy of 1-NN. 6w,3 and dw,23 results are taken from Böker et al. (2023). dw and (3) as initial labels. The table shows the mean classification accuracy of 1-NN using different graph distances using node degrees initial labels.
(i1.222 results are taken from Chen et al. (2022) using node degrees
Accuracy
MUTAG
Chen al. (2022) di
(3)
91.1 4.3
Chen et al. (2022) (3)
85.2 + 3.5
WLLB,23
Böker et al. (2023) 5w,3
87.89 4.11
Böker al. (2023) 6w,23
86.32 + 4.21
Chuang & Jegelka (2022) TMD
89.47 = 7.81
DIDM
89.47 = 7.81
GIN (2-layer, 4-d)
GIN (2-layer, 16-d)
GIN (2-layer, 64-d)
max of n. MPNN dist.
max of n. MPNN dist.
0.8
0.6
n.
0.2
0.0
n. Graph dist,
@vwv66. GI maxd (a
n. Graph dist, 8newlG, G.
n. Graph dist,
OnewlGG, mar GJ
maidhuse (o
(2-layer, 4-d)
GC (2-layer, 16-d)
GC (2-layer, 64-d)
1.0
max D. MPNN dis..
max of MPNN dist.
0.8
6
0.4
20.2
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0 CoewGG G:
n. Graph dist.
n. Graph dist.
8 DwiG,
n. Graph dist.
max G0
max Orsise Co,
max Cr. GJ
Figure 3: Correlation between D and the maximum over distances in the outputs of 100 ran- domly initialized MPNNs with varying number of hidden dimensions. The Lipschitz bound is marked by the red line.
53

---

Published as a conference paper at ICLR 2025
GIN (2-layer, 4-d)
Iloid -
GIN (2-layer, 16-d)
lole -ile--ioo Lood veu
GIN (2-layer, 64-d)
1.00
low 1o00 asst MPNN
MPNN dist. Tore)
0.75
(21d) vo..
0.50
0.25
0.00
Graph dist.
Graph dist.
Graph dist.
GC (2-layer, 4-d)
Iooe - (oad Soddrva
GC (2-layer, 16-d)
Ilne Cold Voldivenu
GC (2-layer, 64-d)
1.00
lish sesi
lloe Seeeeraa 199 rest add PPPN
MPNN dist. [eGG)
9.75
0.50
dies MMNN
0.25
0.00
60.0
40.0
n. Graph dist.
n. Graph dist. Steall: G)
n. Graph dist.
GreallS, GI
Figure 4: Correlation between DIDM and distance the output of a randomly initialized MPNN with varying number of hidden dimensions. GraphCony embeddings preserve graph distance better than GIN on MUTAG dataset.
GIN (1-layer, 64-d)
Rovd zóu
GIN (2-layer, 64-d)
Jooe - Cold veu dlse. SAMMN
GIN (3-layer, 64-d)
love 1996
lloye 1994
1.00
MPNN dist. le6a
0.75
0.50
dfst. MPNN
0.25
0.00
Graph dist. Beawl. 6f)
Graph dist.
01 mpx6eemeG...
Graph dist.
max6resuG..c
mpx
(1-layer, 64-d)
GC (2-layer, 64-d)
GC (3-layer, 64-d)
Iioul - cord Cord vii
MPNN dist. Tatsi el6l
lise visa dat NMMN
1.00
Core Lemn aas MPPMA
0.75
0.50
0.25
0.00
0.5
E0.0
0.5
6..00
n. Graph dist.
n. Graph dist.
Owalll GJ
n. Graph dist.
Osaullt G)
maxtesul6, GI
mpxdeeww 15,
mpx G)
Figure 5: Correlation between DIDM and distance in the output of randomly initialized MPNN with varying number of layers. GraphConv embeddings preserve graph distance better than GIN on MUTAG dataset.
54

---

Published as a conference paper at ICLR 2025
mortppa 2001
GIN (1-layer, 8-d)
Iooe Laidfaeu dlst Mpdd
GIN (2-layer, 8-d)
liot cotd dist Mwdw Mooe Bopa
GIN (3-layer, 8-d)
MPNN dist. Iplca - ploal
1.00
0.75
0.50
0.25
0.00
Graph dist. 6nsulG.G1
Graph dist.
Osevvl Cr
Graph dist.
Osnul G1
maxdggella 0)
mox stoll
GC (1-layer, 8-d)
GC (2-layer, 8-d)
GC (3-layer, 8-d)
MPNN dist. Leteo plo)
1.00
0.75
0.50
aitT MPPM
diss MddM
0.00
0.0
0.5
1,0
0.00
0.5
1.0
6000
0.5
1.0
Graph dist. GnaulG,
Graph dist. max
Graph dist.
Onnul
Figure 6: Correlation between BIDM and distance in the output of a randomly initialized MPNN with varying number of layers. A convergent sequence of graphs with constant signal. The graphs are generated by stochastic block models.
max PON
GIN (1-layer, 8-d)
max 2003 101
GIN (2-layer, 8-d)
GIN (3-layer, 8-d)
n. MPNN dist. Into] ploil
1.00
dist. (ets) ell
Intosl 9001 Mao--
0.75
MPNN dist. max
0.50
0.25
0.00
n. Graph dist.
dpawlo, Gi
Graph dist.
Aoevll G1 max Pan.uuell...o 03
Graph dist.
4oowl G1
Bean G1
max 951 S01
GC (1 layer, 8-d)
liow
GC (2 layer, 8-d)
GC (3 1ayleyyr, 8-d)
MPNN dist. Inio] (oo)-wlle vio
Inte) 4o0
MPNN dist. Iuto - slo
1.00
mpx SCT
0.75
MPP P dist. max 2o
0.25
0.00
0.0
0.5
1,0
0.00
0.5
1.0
0..0
0.5
1.0
Graph dist, 8n
Graph dist.
Graph dist.
Figure 7: Correlation between 6DDD and distance in the output of a randomly initialized MPNN with varying number of layers. convergent sequence of graphs with signal, such that the signal values are constant each graph's community. Each signal value sampled from a uniform distribution over [0, 1]. The graphs are generated by stochastic block models.
55

---

Published as a conference paper at ICLR 2025
mptigeii 901
GIN (2-layer, 1-d)
GIN (2-layer, 8-d)
MPNN dist. maxt (Pon (oo
GIN (2-layer, 16-d)
1.00
MPNN dist. [eis]
0.75
0.50
MPNN dist.
0.25
0.00
n. Graph dist.
Suollo 6) max GG
n. Graph dist. Aoar 0]
n. Graph dist.
makobar 16, G)
max (G, G)
GC (2-layer, 1-d)
GC (2-layer, 8-d)
mas[pt))- 1 pod
GC (2-layer, 16-d)
1.00
MPNIV dist. Iwie) elo
IwiG sldy
MPNN dist. [eic]
0.75
0.50
MPNN dist.
0.25
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.00
0.5
1.0
Graph dist, Aosulo,
Graph dist,
Graph dist,
Figure 8: Correlation between DiDm and distance in the output of a randomly initialized MPNN with varying number of hidden dimensions. A convergent sequence of graphs with signal, such that the signal values are sampled from normal distribution. (H, o;) with mean μ = and linearly decreasing variance. The graphs generated by stochastic block models.
GIN (1-layer, 8-d)
Rooe - 1ond so 209 PPNNA Itsee 1909
GIN (2-layer, 8-d)
Itoe Lioid
GIN (3-layer, 8-d)
MPNN disl. Ieic 96a
Iooe 1o0g cass SPONN
1.00
0.75
0.50
0.25
AMPPO
0.00
n. Graph dist.
Susr6G.0 mardgewlos,
n. Graph dist.
n. Graph dist.
GC (1-layer, 8-d)
GC (2-layer, 8-d)
GC (3-layer, 8-d)
MPNN disi. leGl 3611
1.00
APMN dist. leea -
APPN dist. Leci -a----
0.75
0.50
0.25
0.00
0.0
0.5
1.0
$0.0
0.5
1.0
60.0
0.5
1.0 6ncull GI
n. Graph dist.
EnevlG. mox3sewls,
n. Graph dist.
Orecult, GI
n. Graph dist.
Figure 9: Correlation between DDDM and distance in the output of a randomly initialized MPNN with varying number of layers. A convergent sequence of graphs with signal, such that the signal values are sampled from a normal distribution N (1,, o;) with mean a = and linearly decreasing variance. The graphs generated by stochastic block models.
56

---

Published as a conference paper at ICLR 2025
GIN (2-layer, 4-d)
max ppxxppp 1- plod
GIN (2-layer, 16-d)
GIN (2-layer, 64-d)
n. MPNN dist. I960 elc
n. MPNN dist. [o eGi
1.00
dist. popco
0.75
0.25
n. MOP
0.00
[n. Graph dist,
SoundG maw.Ruawl.
n. Graph dist.
n. Graph dist.
4ocul6 Gi maxdgewldi,
GIN (2-layer, 4-d)
GIN (2-layer, 16-d)
GIN (2-layer, 64-d)
max of MPNN dist.
1.0
max of n. MPNN dist.
max of MPNN dist.
0.8
0.6
0.4
Graph dist. fopul6, G) maxdueewl
Graph dist, 40nn6G, 0) maxeuualli, G)
n. Graph dist.
6ogul6, Gi ma GT
GIN (2-layer, 4-d)
GIN (2- (2-layer, 16-d)
GIN (2-layer, 64-d)
mean of n. MPNN dist.
1.0
mean of n. MPNN dist.
mean of n. MPNN dist.
0.8
0.6
n. Graph dist.
60an66. me DJ
Graph dist.
Banuli Gi maxdoewlG..C
Graph dist.
6spelGi maxdgeeelB. (a,
Figure 10: Correlation between dIDM and distance in the output randomly initialized MPNNs with a varying number of hidden dimensions. On the top row of figures, the correlation between BDDA and distance in the output of single randomly initialized MPNNs is presented. On the middle row of figures, the correlation between DiDM and the maximum over distances in the outputs of 100 randomly initialized MPNNs presented. On the bottom row of figures, the correlation between oh and the mean over distances in the outputs of 100 randomly initialized MPNNs is presented.
57

---

Published as a conference paper at ICLR 2025
mox mor 100
GIN (2-layer, 4-d)
GIN (2-layer, 16-d)
1oo1 outh ciu Inje - 1044
GIN (2-layer, 64-d)
MPMN dist. Infoi plog
1.00
0.75
0.50
MNNN dls.
diss MPPM
0.25
0.00
Graph dist.
Sosulfi G1
Graph dist.
Boerili. G1
Graph dist.
mpxcuueel6. 6)
maxdunelG.cc
mox 3 gtol
GC (2-layer, 4-d)
GC (2-layer, 16-d)
1:14
GC (2-layer, 64-d)
n. MPNN dist. (wtol plon
1.00
MPNN dist. mere (oos
0.75
0.50
MPNN dist.
0.25
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.00
0.5
100 max.foneeeeee G)
Graph dist.
Oboulit max mesfeenlG..o
Graph dist.
Roevioi max www.fmnel..... 6)
Graph dist.
Asoviii
Figure 11: Correlation between DIDM and distance in the output of randomly initialized MPNN with a varying number of dimensions. GraphConv embeddings preserve graph distance better than GIN on PROTEINS dataset.
GIN (1 la-layer, 64-d)
GIN (2-layer, 64-d)
1o1 10d--1220 2udi dls. Moddi
GIN (3-layer, 64-d)
MPNN dist. Untei vlog
Boja - Tile
1.00
IeGc - aid rippe So
0./5
0.50
MNNae dist.
0.25
0.00
Graph dist.
dp mezdeaniG..Gr
Graph dist.
doevio,.0r maxcbusele Gf
Graph dist.
4poul3i, 01
GC (1 layer, 64-d)
man gon gol
GC (2 laylr, 64-d)
Ley
GC (3 layer, 64 d)
MPNN dist. [eies) slo
1.00
[eG)) vig
Ietal Ieta)- slol
0.75
0.50
MPNN dist.
MPNN dist.
0.00
0.0
0.5
1.0
=0.0
0.5
1.0
-0.0
0.5
1.0
Graph disl. 3p
Greph
8pevl9..
Graph
8povlSi, mww.huseee.
max www.hoeelfee
Figure 12: Correlation between D and distance in the output of randomly initialized MPNN with a varying number of layers. GraphConv embeddings preserve graph distance better than GIN on PROTEINS dataset.
58

---

Published as a conference paper at ICLR 2025
N
LIST OF NOTATIONS
Sets and Graphs
A x C
The cartesian product of two sets A and The set of natural numbers including O. The set of real numbers The set of real vectors of length d A fixed compact sub-set of IRd, (Page 3)
No
R
Rd
By
Cs(2)
The set of all bounded continuous real-valued functions X, (Page 3)
C(X,3)
The set of all continuous functions from A' to y
K
A compact space
{0, 1}
The set containing and
{0, 1. n}
The set of all integers between (and including) 0 and n The set of all integers between (and including) 0 and The real interval including a and b A real interval
ml
ba
I
(a, b]
The real interval excluding but including b graph-signal (Page
(G,
(H
graph-signal
(W,
A graphon-signal (Page 4)
(Q.9)
graphon-signal
V(G)
The set of nodes of the graph G
V(W)
The set of nodes of the graphon W The set of edges of the graphon W The set of neighboring nodes of a graph node
E(W)
N(v)
Calculus
f(z)dx
Definite integral over the entire domain of
1 f(x)dx
Definite integral with respect to æ over the set S
Numbers and Arrays
Element of set, can be both scalar vector
Element of vector or sequence
C
A matrix
D
matrix
x
A random (either multi or single) variable
Measure Theory and Iterated degree Measures
59

---

Published as a conference paper at ICLR 2025
Computation iterated degree measure (Page 5)
Computation distribution of iterated degree measure
(Page 5)
fup
the push-forward of a measure E (X) via a measur- able map f X +
P4
The i'th element of an IDM μ
p())
The i' thth element of an IDM μ
F
o-algebra
o-algebra
B(2)
The standard Borel o-algebra of a measurable space X'
(X
mesurable space
(X, M)
a measure space
(2)(2))
The space of all non negative Borel measures with total mass most one on ((x)) (Page
(x)
The space all Borel probability measures on (()) (Page 3)
Ha
The space of iterated degree measures (IDMs) of order d (Page 5)
(HH))
The space of distributions of iterated degree measures (DIDMs) of order d (Page 5)
Metries
d
metric Ep norm of x
|
||=|
the infinity norm of æ
оTх
Optimal transport with respect to the distance function d (Page 3)
dIDM
IDM distance (Page 6)
8DIDM
DIDM mover's distance (Page
Pa
Prokhorov metric with respect to the distance function d (Page 48)
PIDM
IDM Prokhorov distance (Page 48)
PDIDM
DIDM Prokhorov's distance (Page 48)
Probability and Information Theory
N(p, E)
Gaussian distribution with mean fe and covariance Σ Functions
60

---

Published as a conference paper at ICLR 2025
f:A-C
The function f with domain A and range C The function f evaluated at point a The function evaluated some point The function f evaluated some point Composition of the functions f and Natural logarithm of if condition is true, otherwise the empirical risk (Page 9)
f(x)
f(-)
f-
fog
logæ x
condition
R
R
the statistical risk (Page 9)
Message Passing Neural Networks (Page
8
A L-layer MPNN model
(49, 2/
L-layer MPNN model with readout function An update function
(0)
An readout function
9
L-layer MPNN model graph-signal feutures for t [L]
I-layer MPNN model with readout graph-signal feutures
L-layer MPNN model graphon-signal feutures for t E [Z]
L-layer MPNN model with readout graphon-signal feu-
tures
6 60
L-layer MPNN model IDM feutures for t [4]
I--layer MPNN model with readout DIDM feutures
61


Reviews:
[{"review_id": "jwiq4Twm19", "reviewer": "Reviewer_Ku8V", "summary": "The authors propose a metric based on optimal transport distances between graph representations.\nUnder this metric, the authors show the MPNNs are Lipschitz and graph rerpesentations are compact. They establish that GNNs are capable of separating attributed graphs that are distant in the defined metric, leading to a universal approximation theorem and generalization bounds for MPNNs. Building on these, the authors further developed a generalisation theorem.  Empirical results demonstrate the correlation between the new metric and MPNN output.", "questions": "1. The proposed metric considers attributed graphs, but in Fig 2, why is the alignment worsen when added attributes? \n2. Can the results be used to analyse more power GNNs? e.g. k-GNN, F-MPNN, etc\n3. Unifying graph and graphon MPNN means you have to assume normalised sum aggregation, can this assumption be removed?\n4. If not considering graphons, can this results apply to sparse graphs?\n5. How is the metric related to the metric in \"Weisfeiler-lehman meets gromov-Wasserstein.\"?\n6. Why do you use Unbalance OT instead of OT?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "* The proposed a noval pseudometric for graphs based on iterated degree measures and optimal transport.\n* The authors show MPNNs are universal and Lipschitz under this pseudometric.\n* The authors show a bidirectional connections between the metric and MPNN output.\n* A generalisation theorem is developed based the metric.\n* The framework unifies MPNNs on graph and graphon.", "weaknesses": "* The proposed metric only applies to MPNN/1-WL GNNs, and cannot be used to analyse more powerful GNNs. \n* Related works are insufficiently discussed. In particualr, the proposed metric seems realted to [1][2], but this connection has not been discussed.\n* The metric is expensive to compute, while its complexity is linear to $L$, it is in the order of $n^5$ which hinders its practicality\n* The MPNN analysis limits to normalized sum aggregation, which is less commonly used.\n* There are too many similar notations and symbols, making it difficult to follow. \n* The graphon-based approach means the results do not apply to sparse graphs.\n* Emperiments are limited to one small real-world dataset (MUTAG), which makes the results less convincing.\n\n\n\n\n[1] Chen, Samantha, et al. \"The Weisfeiler-Lehman distance: Reinterpretation and connection with gnns.\" Topological, Algebraic and Geometric Learning Workshops 2023. PMLR, 2023.\n[2] Chen, Samantha, et al. \"Weisfeiler-lehman meets gromov-Wasserstein.\" International Conference on Machine Learning. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XmJumPIbQa", "reviewer": "Reviewer_uw7j", "summary": "This paper develops a comprehensive theoretical framework that enhances the understanding of generalization, expressivity, and universality in Graph Neural Networks (GNNs) when applied to attributed graphs (graphs with node features). The central contribution is the introduction of a new metric, the Tree Mover’s Distance (TMD), designed to precisely measure the similarity between graphs by capturing both their structural and attribute-based characteristics. Key findings of this paper include the design of TMD,  the universal approximation of GNNs, and the analysis of the expressivity of GNNs.", "questions": "1.  While the paper provides some empirical results, the evaluation could be expanded to offer deeper insights into practical applications and better demonstrate the efficacy of the proposed method. Have the authors considered evaluating TMD on additional graph classification benchmarks beyond MUTAG? Comparing TMD against other graph similarity metrics on tasks like graph matching or clustering could also strengthen the empirical evaluation. Furthermore, could the authors provide more detailed explanations of the experimental settings and parameter choices？\n\n2. In Table 1, it would be helpful to clarify the organization and naming of the columns, as the label “Accuracy” appears to represent results across multiple methods. Providing a clearer breakdown of the results, along with an analysis that contextualizes each method’s performance, would enhance understanding. For example, if the statistics below MUTAG represent accuracy scores, they suggest that TMD does not significantly outperform some existing methods, such as Chen et al. (2022)’s  d^{(3)}_{WL} . A discussion of how TMD compares to these methods and whether additional datasets were considered may add further depth to the results.\n\n3.  Structuring the manuscript to more prominently summarize the major findings and their impact would improve readability. Perhaps revise the contribution part in the introduction to better summarize the major findings. Also, perhaps adding a section to state the broader impact of these findings more clearly and how each finding advances the field of GNN theory to better illustrate the importance of this work. \n\n4. The methods primarily focus on dense graphs, as noted in the conclusion that “sparse graphs are always considered close to the empty graph under our metrics.” A further explanation of this limitation—specifically, why sparse graphs exhibit this behavior under TMD—would benefit the reader. Additionally, a discussion of whether this limitation affects the method’s generality and its potential applications to sparse graph domains would strengthen the paper.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The theoretical analysis is solid and thorough.\n2. This work enhances the understanding of GNNs. The work introduces a new framework that unifies generalization and expressivity theories for attributed graphs, a notable achievement in GNN research.\n3. The idea of introducing OT to this problem is quite novel and fancy.", "weaknesses": "See the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0c87Ze5atZ", "reviewer": "Reviewer_9Cqp", "summary": "This paper theoretically shows that the closeness of two graphs by MPNNs can be represented by the proposed metrics based on Wasserstein Distance. This work also shows the existence of MPNNs that can separate two graphs with non-zero distance and can approximate any functions over the space of graphs. A bound of generalization gap is also provided for MPNNs with milder assumptions.", "questions": "1. Can your theoretical analysis extend to the node classification problem?\n\n2. Is Theorem 7 related to any distance metric proposed in Sections 3 and 4? If not, can the analysis in Sections 3 and 4 be used to derive a generalization bound?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The theoretical analysis is solid and strong. Especially, this work tries to provide an analysis that is as universal as possible with the fewest assumptions. \n2. The discussion of MPNNs and tree mover's distance in Section 4 is interesting and novel to me.", "weaknesses": "1. The presentation is a bit strange. The main results in Section 5 appear too late on almost page 9 in the main body of the paper. Moreover, the universal approximation and the generalization bound seem independent of the previous analysis of graph/graphon distances. It is better to move Section 5 earlier and elaborate more about the connections with previous sections. \n\n2. Section 5 is not insightful enough. For example, although Theorem 7 makes contributions by requiring fewer assumptions, experiments in Figure 3 show that the generalization error is still related to the covering number and the Lipschitz constant, which is unsurprising and known in generalization theory. \n\n3. Some references on the generalization error of MPNNs are missing. \n\nOono, K. and Suzuki, T. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Neurips 2020.\n\nLi et al., 2022. Generalization guarantee of training graph convolutional networks with graph topology sampling. ICML 2022.\n\nTang et al., 2023. Towards understanding the generalization of graph neural networks. ICML 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HG60e9QB2G", "reviewer": "Reviewer_xDjn", "summary": "The present manuscript studies the approximation and generalization capabilities of message passing GNNs on attributed graphs under the lens of  proposed pseudometrics, based on the Wasserstein distance between distributions of computation tree analogs over graphons. It is demonstrated that such a pseudo metric leads to the characterization of a topology that allows to prove that message passing GNNs are universal approximations over attributed graphons, which are the fine-grained version of attributed graphs. Furthermore,  bounds on the generalization capability are provided exploiting the compactness and the lipschitzness of the retrieved topology. The theoretical findings are supported by an extensive experimental framework.", "questions": "Can the authors provide a motivation for the choice of GINs and GraphConvs for the empirical evaluation?\nCan the authors provide a short discussion of the results of the empirical evaluation over the generalization bound?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This manuscript provides a solid theoretical analysis of message passing GNNs under the framework of attributed graphons. The framework studies many properties, from universal approximation to generalization capabilities, therefore yielding a comprehensive overview of message passing GNNs that integrates in several ways the contribution already present in literature.", "weaknesses": "It is not explained why GINs and GraphConvs where chosen for the empirical evaluation, among the large class of message passing GNNs present in literature. I would suggest to discuss whether GIN and GraphConv are representative of different types of MPNNs, or if they have properties that make them particularly suitable for evaluating the theoretical results. \n\nA (short) discussion of the results of the empirical evaluation over the generalization bound is missing. I would suggest to discuss how closely the empirical results align with the theoretical bound, also considering the statistical nature of the task, or if there are any unexpected patterns or discrepancies that needs some careful consideration and warrant further investigation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)