Fine-grained Expressivity of Graph Neural Networks
Authors: Jan Böker
Ron Levie
Ningyuan Teresa Huang
Soledad Villar
Christopher Morris
Venue: NeurIPS 2023 poster (2023)
Keywords: graphons
universal approximation
weisfeiler-leman
graph metric
tree homomorphisms
tree distance
optimal transport
GNNs
TL;DR: We quantify which distances MPNNs induce, leading to a more fine-grained understanding of their expressivity and separation capabilities.

Abstract: Numerous recent works have analyzed the expressive power of message-passing graph neural networks (MPNNs), primarily utilizing combinatorial techniques such as the $1$-dimensional Weisfeiler--Leman test ($1$-WL) for the graph isomorphism problem. However, the graph isomorphism objective is inherently binary, not giving insights into the degree of similarity between two given graphs. This work resolves this issue by considering continuous extensions of both $1$-WL and MPNNs to graphons. Concretely, we show that the continuous variant of $1$-WL delivers an accurate topological characterization of the expressive power of MPNNs on graphons, revealing which graphs these networks can distinguish and the level of difficulty in separating them. We identify the finest topology where MPNNs separate points and prove a universal approximation theorem. Consequently, we provide a theoretical framework for graph and graphon similarity combining various topological variants of classical characterizations of the $1$-WL. In particular, we characterize the expressive power of MPNNs in terms of the tree distance, which is a graph distance based on the concept of fractional isomorphisms, and substructure counts via tree homomorphisms, showing that these concepts have the same expressive power as the $1$-WL and MPNNs on graphons. Empirically, we validate our theoretical findings by showing that randomly initialized MPNNs, without training, exhibit competitive performance compared to their trained counterparts. Moreover, we evaluate different MPNN architectures based on their ability to preserve graph distances, highlighting the significance of our continuous $1$-WL test in understanding MPNNs' expressivity.

Expressivity of Graph Neural Networks
Jan Böker
Ron Levie
RWTH Aachen University
Technion Israel Institute of Technology
Ningyuan Huang Johns Hopkins University
Soledad Villar
Christopher Morris
Johns Hopkins University
RWTH Aachen University
Abstract
Numerous recent works have analyzed the expressive power of pesssag-ppassing graph neural networks (MPNNs), primarily utilizing combinatorial techniques such as the I-dimensional Weisfeiler-Leman test (1-WL) for the graph isomorphism problem. However, the graph isomorphism objective is inherently binary, not giving insights into the degree of similarity between two given graphs. This work resolves this issue by considering continuous extensions of both 1-WL and MPNNs to graphons. Concretely, we show that the continuous variant of 1-WL delivers an accurate topological characterization of the expressive power of MPNNs on graphons, revealing which graphs these networks can distinguish and the level of difficulty in separating them. We identify the finest topology where MPNNs separate points and prove a universal approximation theorem. Consequently, we provide a theoretical framework for graph and graphon similarity combining various topological variants of classical characterizations of the 1-WL. In particular, we characterize the expressive power of MPNNs terms the tree distance, which a graph distance hased the concept of fractional isomorphisms, and substructure counts via tree homomorphisms, showing that these concepts have the same expressive power as the 1-WL and MPNNs on graphons. Empirically, we validate our theoretical findings by showing that randomly initialized MPNNs, without training, exhibit competitive performance compared to their trained counterparts. Moreover, evaluate different MPNN architectures based on their ability to preserve graph distances, highlighting the significance of our continuous 1-WL test in understanding MPNNs' expressivity.
Introduction
Graph-structured data is widespread across several application domains, including chemo- and bioinformatics [11, 101], image analysis [107], and social-network analysis [38], explaining the recent growth in developing and analyzing machine learning methods tailored to graphs. In recent years, weessage-passingg graph neural networks (MPNNs) [25, 50, 92] emerged as the dominant paradigm, and alongside the growing prominence of MPNNs, numerous works [89, 115] analyzed MPNNs' expressivity. The analysis, typically based on combinatorial techniques such as the 1-dimensional Weisfeiler- test (1-WL) for the graph isomorphism problem [113, 1 114) provides explanations of MPNNs' limitations (see [92] for a thorough survey). However, since the graph isomorphism problem only concerns whether the graphs are exactly the same, it only gives insights into MPNNs' ability to distinguish graphs. Hence, such approaches cannot quantify the graphs' degree of similarity. Nonetheless, understanding the similarities induced by MPNNs is crucial for precisely quantifying their generalization abilities [82, 94], stability [44], or robustness properties [60].
Present work. To address these shortcomings, we show how to integrate MPNNs into the theory of iterated degree measures first developed by Grebík and Rocha [52], which generalizes the 1-WL and its characterizations to graphons [78]. Integrating MPNNs into this theory allows us to identify the finest
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

topology in which MPNNs separate points, allowing us to prove universal approximation theorem for graphons. Inspired by the Peiseillr-Leman distance [26], we show that metrics on measures also integrate beautifully into the theory of iterated degree measures. Concretely, we define metrics öp via the Prokhorov metric [99] and dw via an unbalanced Wasserstein metric [97] that metrize the compact topology of iterated degree measures, By leveraging this theory, we show that two graphons are close in these metrics if. and only if. the output of all possible MPNNs, up to a specific Lipschitz constant and number of layers, is close as well. This refines the result of Chen et al. [26], which shows only one direction of this equivalence, i.e., graphs similar in their metric produce similar MPNN outputs.
We focus on graphons without node feature information to focus purely on MPNNs' ability to distinguish their structure. Our main result offers a topological generalization of classical characterizations of the 1 1-WL, showing that the above metrics represent the optimal approach for defining a metric variant of the 1-WL. Informally, the main result states the equivalence of our metrics 6p and åw: the tree distance 83 of Böker [18], the Fuclidean distance of MPNNs output, and tree homomorphism densities. These metrics arise from the topological variants of the 1-WL test, fractional isomorphisms, MPNNs, and tree homomorphism counts.
Theorem (informal). The following are equivalent for all graphons U and W:
1. U and W are close in óp (or alternatively ów). 2. U and W are close in 82.
3. MPNN outputs on U and W are close for all MPNNs with Lipschitz constant C' and L layers.
4. Homomorphism densities in U and W are close for all trees up to order k.
Up to now, except for the connection between the tree distance and tree homomorphism densities by Böker [18), these equivalences were only known to hold on discrete level where graphs are either exactly isomorphic or not. The "closeness" statements in the above theorem are epsilon-delta statements, i.e., for every 0, there is 5 > 0 such that, if graphons are 8-close in one distance measure, they are c-close in the other distance measures, where the constants are independent of the actual graphons. In particular, for graphs, these constants are independent of their number of vertices. Theorem is formally stated and proved in Appendix C.4. A key point the proof is to consider compact operators (graphons) as limits of graphs. Empirically, we verify our findings by demonstrating that untrained MPNNs yield competitive predictive performance on established graph-level prediction tasks. Further, we evaluate the usefulness of derived metrics for studying different MPNN architectures. Our theoretical and empirical results also provide an efficient lower bound of the graph distances in Böker [18], Chen et al. [26] by using the Euclidean distance of MPNN outputs.
In summary, we quantify which distance MPNNs induce, leading to a more fine lne-grained understanding of their expressivity and separation capabilities. Our results provide deeper understanding of MPNNs' capacity to capture graph structure, precisely determining when they can and when they cannot assign similar and dissimilar vectorial representations to graphs. Our work establishes the first rigorous connection between the similarity of graphs and their learned vectorial presentations, paving the way for more detailed understanding of MPNNs' expressivity and their connection graph structure.
1.1 Related work and motivation
In the following, we discuss relevant related work and provide additional background and motivation.
MPNNs. Following Gilmer et al. [50], Scarselli et al. [105], MPNNs learn a vectorial representation, i.e., d-dimensional real-valued vector, representing each vertex in a graph by iteratively aggregating information from neighboring vertices. Subsequently, MPNNs compute a single vectorial representation of given graph by aggregating these vectorial vertex representations. Notable instances of this architecture include, c.g., Duvenaud et al. [36]. Hamilton et al. [61], and Velickovic et al. [111], which can be subsumed under the mnessage-aassingg framework introduced in Gilmer et al. [50]. In parallel, approaches based on spectral information were introduced in, e.g., Bruna et al. [23], Defferrard et al. [33], Gama et al. [43], Kipf and Welling [73]. Levie et al. [75], and Monti et al. [87] of which descend from early work in Baskin et al. [14], Goller and Küchler [51]. Kireev [74], Merkwirth and Lengauer [84], Micheli [85], Micheli and Sestito [86], Scarselli et al. [105]. and Sperduti and Starita [108].
Expressivity and limitations of MPNNs. The expressivity of an MPNN is the architecture's ability to express or approximate different functions over a domain, e.g., graphs. High expressivity means the neural network can represent many functions over this domain. In the literature, the expressivity of MPNNs is modeled mathematically based on two main approaches, algorithmic alignment with graph
2

---

(A)
(C)
(D)
(E)
h
Do
2/5
h
1/
a/Tb/e
2/8
Dy
1/4
2/5
2/5
1/5
2/4
h 2
D2
1/4
1/6
1/5
Ogf
000
3/4 R/1 1/4
2/G
Grapb-Sevel rond-utt
Figure Illustration of the procedure to compute the distance öp between graphs G and H. Columns and C show the colors obtained by 1-WL iterations graphs G and H, respectively. Columns B and D show the iterated degree measures (IDMs) ic., and i for iterations h = 1,2 (see Eq. (1)), and the output distributions of iterated degree measures (DIDMs) VG and vy (see Eq. (2)). Column E depicts the recursive construction to compute the distance 6p between the IDMs from columns B and (outlined in Section 3, detailed in Appendix C.2.2).
isomorphism test [88] and universal approximation theorems [7, 48). Works following the first approach study if an MPNN, by choosing appropriate weights, can distinguish the same pairs of non- -somoooo graphs the 1-WL its more powerful generalization the k-WL. Here, MPNN distinguishes two non-isomorphic graphs if it can compute different vectorial representations for the two graphs. Specifically, Morris et al. [89] and Xu al. [115] showed that the 1-WL limits the expressive power of any possible MPNN architecture in distinguishing non-isomorphic graphs. In turn, these results have been generalized to the W-W see, e.g., Azizian and Lelarge [7], Geerts [47], Maron et al. [81], Morris et al. [89, 91, 93]. Works following the second approach study, which functions over the domain of graphs, can be approximated arbitrarily close by MPNN [7, 28, 48, 79]; see also next paragraph. Further, see Appendix B for an extended discussion of related works about MPNNs' expressivity.
Limitations of current universal approximation theorems for MPNNs. Universal approximation theorems assume that the domain of the network is a compact metric space and show that a neural network approximate any continuous function over this space. Current approaches studying MPNNs' universal approximation capabilities employ the (graph) edit distance to define the metric on the space of graphs, e.g., see [7]. However, the edit distance is not natural notion of similarity for practical machine learning on graphs. That is, any two graphs on a different number vertices are far apart, not fully reflecting the similarity of real-world graphs. More generally, the same holds for any pair of non-isomorphic graphs. Hence, any rewiring of a graph leads to far-away graph. However, we would like to interpret the rewiring of small number of edges in large graph as small perturbation close to the original graph. Additionally, since the edit metric is not compact, the Stone-Weierstrass theorem, the primary tool in universal approximation analysis, cannot be applied directly to the whole space of graphs. For example, [26] uses other non-compact metrics to circumvent this, artificially choosing a compact subset of graphs from the whole space by uniformly limiting the size of the graphs and the edge weights. Alternatively, Chen et al. [28] resorted to the graph signal viewpoint, allowing real-valued edge features, and showed that the algorithmic alignment of GNNs with graph isomorphism algorithms can be utilized to prove universal approximation theorems for MPNNs. In contrast, here we suggest using graph similarity measures from graphon analysis, for which simple graphs of arbitrarily different sizes can be close to each other and by which the space of all graphs is dense in the compact metric space of graphons, allowing us to use the Weiersssssssssss theorem directly; see also Appendix B.2 for an extended discussion on graph metrics beyond the edit distance.
3

---

Graphon theory. The book of Lovász [78] provides thorough treatment of graphons, which emerged as limit objects for sequences of graphs in the theory of dense graph limits developed by Borgs et al. [20, 21], Lovász and Szegedy [77]. These limit objects allow the completion of the space of all graphs to a compact metric space. When endowed with the cul distance, first introduced by Frieze and Kannan [41], the space of graphons is compact [78, Theorem 9. 9.2 We can interpret graphons in two ways. First, as weighted graph on the continuous vertex set [0, 1]. Secondly, we can think of every point from [o, 1] as an infinite set of vertices and two points in [0, 1J being connected by a random bipartite graph with edge density given by the graphon. This second point of view naturally leads to using graphons as generative models of graphs and the theory of graph limits. Our work follows the first point of view, and emphasize that we do not use graphons as a generative model. This also means that we do not need large graphs for the asymptotics to work since every graph rrpphand, in particular, every small graph is also graphon. Grebík and Rocha [52] generalized the 1-WL test and various of its characterizations to graphons, while Böker [19] did this for the k-WW test.
Graphon theory in graph machine learning. Keriven et al. [64], Maskey et al. [83], Ruiz et al. [103] use graphons to analyze graph signal processing and MPNNs. These papers assume single fixed graphon generating the data, i.c., any graph from the dataset randomly sampled from this graphon, and showed that spectral MPNNs graphs converge to spectral MPNNs on graphons as the size of the sampled graphs increases. Maskey et al. [82] developed a generalization analysis of MPNNs, assuming a pre-defined finite set of graphons. Further, Keriven et al. [65] compared the expressivity of two types of spectral MPNNs on spaces of graphons, assuming graphons are Lipschitz continuous kernels. To that, the metric on the graphon space is taken as the Lo distance between graphons functions. However, the paper does not directly characterize the separation power of the studied classes of MPNNs, and it requires the choice of arbitrary compact subset to perform the analysis. In contrast, in the current paper, we graphon analysis to endow the domain of definition of MPNNs, the set of all graphs, with a "well-behaved" structure describing a notion of natural graph similarity and allowing us to analyze properties of MPNNs regardless of any model of the data distribution.
2
Background
Here, we provide the necessary background and define notation.
Analysis. We denote the Lebesgue measure on [0, 1] by À and consider measurability w.r.t. the Borel o-algebra on [0, 1]. Let (X, B) be standard Borel space, where we sometimes just write X when B is understood and then use (() to explicitly denote B. For a measure μ on X, we let |||a||| == (XX denote its total mass, and for standard Borel space (Y, and measurable map f: X + Y. let the push-forward faj1 of μ via ff be defined by (A) == uf (A)) for every A E C. Let (X) and Mci (X) denote the spaces of all probability measures on X and all measures of total mass at most one on X, respectively. Let (x) denote the set of all bounded continuous real-valued functions on X. We endow 3 (XX and (X) with the topology generated by the maps μ + fxx fdp for E (x)X,, the weak topology (weak** topology in functional analysis); see [63, Section 17.E] or [17, Chapter 8). Then, P ((X) and Mçi (X) are again standard Borel spaces, and if K is a compact metric space, then P {(K) and Msi (K) are compact metrizable; see [63, Theorem 17.22]. For a sequence (14); of measures and a measure μ., have (4g + fa if and only if Jx s'dp; + fx fdu for every S E Cx(X), and for measures U.v, we have μ = V if and only if fx fd = Sx fdv for every f E Cx(X). In both statements, we may replace (x) by a dense (w.rt. the sup norm) subset. See Appendix A.3 for basics on topology. We denote a function f: A + B also by [--) or f- in case the evaluation of f on a point a E A is denoted by f(()) or fa. respectively.
Graphs and graphons. A graph G is a pair (G), E(G)) with finite sets of vertices or nodes (G) and edges E(G) C {(u,v) C (G)) u + v}. If not otherwise stated, we set == (G)), and the graph is of order n. We also call the graph G an n--rder graph. For ease of notation, we denote the edge {u, o in E(G) by ue or vu. The neighborhood of v in (GG is denoted by (Ct) {u V(G) vu E EG) and the degree of a vertex V is (.)). Two graphs G and H are isomorphic and we write G ~ H there exists bijection :o: V(G) + V(H) preserving the adjaceney relation, i.e., wu is in E(G) if and only if (()))p()) is in E(H). Then y is an isomorphism between G and H.
A kernel is measurable function U: [0, 1J + IR, and a symmetric measurable function W: |0. 1j2 - [0, 1] is called graphon. The set of all graphons is denoted by W. Graphons generalize graphs the following way. Every graph G can be viewed graphon We by partitioning [0, 1] into intervals
4

---

(o)), each of mass 1/n, and letting Wo y) for z E Iu, y E Ig be one or zero depending on whether we is an edge in G or not. The homomorphism density t(F, W) of graph F in a graphon W is t(P, W) = Jo. (F)E W (Z),zz) d(z), where is the tuple of variables z. for E V(G).
The tree distance. A graphon W defines an operator Tw: [10 1J) - ( 1J) on the space ([0, 11) of square-integrable functions modulo equality almost everywhere by setting (Tw (x) = Ju.11 (a, (v) d'(y) for every I E X and every f E (10, 1)). Böker [18] defined the free distance of two graphons U and W by (U, W) == inf sup K(,, ; (Ty o S S o Tw)g)), where the supremum is taken over all measurable functions f.g: [0. 1] + [o, 1] and the infimum is taken over all Markov operators S, i.e., operators S: ( 11) + (20, 1]) such that S(J) 2 0 for every f 2 O, ((1 = [0.1], and 5 (1.11) = [u,1] also for the Hilbert adjoint S Markov operators are the infinitediimensionall analog to doubly stochastic matrices, see [39] for thorough treatment of Markov operators. One can verify that the tree distance is a lower bound for the cut distance [18].
Iterated measures. Here, we define iterated degree measures (IDMs), which is basically a sequence of measures, by adapting the definition of Grebík and Rocha [52]. Let Mg == {1} and inductively define MA-11 == Me1 (Mb,, for every h 2 0. Then, the spaces Ma, M are all compact metrizable. For S < oc, inductively define the projection 11+11h: : M4++1 -> Mi, by letting PL.0 be the trivial map and, for h > 0, letting 1, (a) = (Ph,a-1) for every a E MM++1 = Mei (M,), This extends to
pa.e: MA + M. for 0 S l S < oo by composition in the obvious way. Let
M Mox = { (an)n ) E II
Mr 1,++1,000441 = ar, for every h EN]
MEN
be the inverse limil of Ma, MI, MI,...: : see the Kolmogorov Consistency Theorem [63, Theorem 17.20). Then, M is compact metrizable [52, Claim 6.2]. For 0 S h oc, let Px. M Ml, denote the projection to the hth component. We remark that we slightly simplified the definition of Grebik and Rocha [52] by not including previous IDMs from My. for h' S h in MA++1 and directly defining MI as the inverse limit; corresponding to the definition of the space P in [52]. These changes yield equivalent definitions that simplify the exposition.
The 1-WL for graphons. See Appendix A. for the standard definition of 1-WL on graphs. Grebík and Rocha [52] generalized 1 1-WL to graphons by defining map iw: [0, 1] + M, mapping every point of the graphon W E W to an iterated degree measure as follows. First, inductively define the map iw.:: [0, 1] - M, by setting (w:)(z) = 1 for every x E [0, 1] and
iw)+1(0) = A
W(x, (I))))d)())
for all x E [0, 1]. A E B(M,), and h 2 0. Intuitively. i (x) is the color assigned to point x after
h iterations of 1- 1-WL. Observe that (z) encodes the degree of point x, and iw.s for h > 1
represents the iterated degree sequence information. Then, we define iw := iw, [0, 1] - M by
iw iw)) == iw. (x) == lh iw. (1) and let
(2) be the distribution of iterated degree measures (DIDM) of W. In other words, ew (w(A) is the volume that the colors in A occupy in the graphon domain [0, 1]. Then, the 1-WL test on graphons is the mapping that takes graphon W E W and returns Vw. In addition to Vw, we also define Vw.A- == (iw,k..) E P (M,) for 0 S h < co, corresponding to running 1-WL for l rounds.
Vw == 1W == (Iw).d E (M)
While every DIDM of a graphon is a measure from the compact space P (M.), not every measure in (M is the DIDM of a graphon. Grebik and Rocha [52] address this by giving a definition of a DIDM that is independent of a specific graphon. For us, it suffices to remark that the set DA == {PW&a W graphon} S (M,) is compact as is the image of the compact space of graphons [78, Theorem 9.23] under a continuous function [52]. For us, this means that WD, and P (Ml), can be used interchangeably in our arguments, and we do not have to be overly careful with distinguishing them. For simplicity, we simply stick to 9 (M,, and refer to all elements of 3 (MI, as DIDMs.
Message-passing graph neural networks. MPNNs learn a dd-dimensional real-valued vector for each vertex in a graph by aggregating information from neighboring vertices; see Appendix A.2 for more details. Here, we consider MPNNs where both the update functions and the readout functions are Lipschitz continuous and use sum aggregation normalized by the order of the graph. Formally, we first let
5

---

x = ( denote tuple of continuous functions (P R - Ro and PP: R4 + Rd for t E [L], where we simply view Po as an element of Rd Furthermore, let v denote continuous function ;: d + R. For graph G, MPNN initializes feature h!") Pu R Then, for t [L], we compute ( V(G) - IR and the single graph-level feature lng E Rd after L layers by
(
h = 9: [
Σ h(-")) (EN(2)
and bg = d/ [[G)
Σ VEV(G)
For a graphon W E W, an MPNN initializes a feature h = Po E R for x E [0, 1]. Then, for t e [L], we compute h : [0, 1] + Rd and the single graphon-level feature hw Rd after L layers by (")
h Pe (1 y) ((a.)))n->)aa(i dX(w))
and hw = 16 (
D... 1 ((o))
This generalizes the previous definition, i.e., for a graph G and its (induced) graphon Wa, we have bg = hwo and b! (o) for all E [r], E V(G), and E To; see Appendix C.I.
We now extend the definition of MPNNs IDMs. While the above definition of h depends specific graphon W. an IDM already carries the aggregated information of its neighborhood. Hence, the initial feature h.
Po de for E M. and h(),, M. - Rd defined for all IDMs at once. The intuition is that MPNNs cannot assign at layer t different feature values to nodes that have the same color at step l of the graphon 1-WL algorithm. Hence, it is enough to only consider an assignment between colors and feature values, and not consider the graph/graphon structure directly. Then, for a DIDM @ (M,), we define the single DIDM-level feature h, IRd Formally, we let
1 9p (L h (t-1) da M
and h 16 (re
h du
That is, messages are aggregated via the IDM itself. In addition to h (1) Mr -> Rdd, and and h: (ML)) - Rdd we define h [2 MI - Red and h (MM) - Rdd by setting h = h pa.a(a) for every a E M and h, == h (p...) ). for every v E (M,); it will always be clear from the context which of these functions we mean. These definitions of MPNNs on IDMs extend the previous definitions of MPNNs on graphons via the following identities. For a graphon W E W. we have hw how.L h and
(w) for almost every E [0, 1]; see Appendix C.I. That is, the feature values of an MPNN on graphon W are equal to the feature values of that MPNN on the (D)IDM computed by the 1-WL on W. We call a tuple sp as defined above an (L-layer) MPNN model sp: is Lipschitz continuous
(0)
(w:)(w) = hi
(t)
} for every i E [L]. and we call s/s as defined above Lipschitz if it is Lipschitz continuous on [.hr, h4 du II P (Mr)). We use ||- to denote the Lipschitz constants on these sets. this paper, & and & always denote an MPNN model and Lipschitz function, respectively. We use the term layer MPNN model to refer to an L-layer MPNN model for an arbitrary L.
on [UM (1-1) da a E Mc}
3 Metrics on iterated degree measures
Chen et al. [26] recently introduced the Weisfeiler-Lemun distance, a polynomial-tine computable pseudometric on graphs combining the 1-WL test with the well-known Wasserstein metric from optimal transport [1] where their approach resembles that iterated degree measures as introduced by Grebik and Rocha [52]. To use metrics from optimal transport, Chen et al. [26] resorted to mean aggregation instead of sum aggregation to obtain probability measures instead finite measures with total mass at most one. Using mean aggregation, however, is different from the 1-WL test, which relies sum aggregation. That is, sum aggregation allowed the algorithm to start with a constant coloring, something impossible with mean aggregation, potentially leading to constant coloring. Chen et al. [26] circumvented this problem by encoding vertex degrees and the total number of vertices in the initial coloring.
Here, we show that the Prokhorov metric [99] and unbalanced variant of the Wasserstein metric can be beautifully integrated into the theory of iterated degree measures, eliminating the need to work around the limits of mean aggregation. Both metrics metrize the weak topology, which is precisely the topology of the

---

space MA of IDMs is endowed with; see Section 2. In modern-day literature, the Prokhorov metric is usually only defined for probability measures [35, Section 11.3), yet the original definition by Prokhorov [99] already was for finite measures. That is, let (S, d) be complete separable metric space with Borel g-algebra B. For a subset A S S and & 2 0, let A == {y e S d(x,y) y) < & for some x E A}, and define the Prokhorov metric P on Mg (S) by
P(,, in > 0 p(A)= S v(A9) + and (A) S ((AA)+ + E for every A E B).
As the name suggests, P is a metric on (S) 199, Section 1.4), and moreover, convergence in is equivalent to convergence in the weak topology [99, Theorem 1.11]. For the unbalanced Wasserstein metric let u. V E (S), where we assume || 2 |n|| without loss of generality, and define
Sniit..,sss. SSxS d(x, y) dy(x,)),
W(U, = ||e|| || +
inf >EM(u..)
where M(H, 2) is the set of all measures E Msi(S x S) such that (pi)-7 S Ja and (p2).7 = v. Here, P1 and P2 are the projections from S x upon S to the first and the second component, respectively, i.e. (AA) = ((A x S) and (44) (S x A). We prove that W is a well-defined metric on (5 B) that coincides with the Wasserstein distance [35, Section 11 11.8] on probability measures. Furthermore, it satisfies W(p. v) I 2P(,. I 4 4W((p, v) for all μ.v E Mc1(5), which implies that it metrizes the weak topology; see Appendix C.2.
The metric is used to define the metric dp,,. on MI, for 0 S h S o0 as follows. Let dp.o be the trivial metric on the one-point space Mg and, for h 2 O. inductively let dp be the Prokhorov metric on (MI,+1, de, Then, define cp on M by setting de(a, (3] = dp, (a, B) == suPMEN h dp,, (ch,, (3)) for a, 8 E M. The factor of 1/h is included in this definition on purpose to ensure that dp, scc metrizes the product topology and not the uniform topology. The metric dw,a on M, is defined completely analogously via W instead of P.
1
The metrics dp,,A and dw.i on M,, allow us, for example, to compare the IDM of a point in a graphon to the IDM of point in another graphon. To compare two graphons' distributions on iterated degree measures, we let 6p, be the Prokhorov metric on (Mis), dp.a. )) for 0 < h S. oc and again define dw,n analogously via the distance W. We note that these metrics directly apply graphons U, W E W by simply comparing their DIDMs VU. and PWCh-
Theorem 2. Let 0 S h S co. The metrics dp and dw,s are well-defined and metrize the topology of Mi, The metrics y and dw.n are well-defined and metrize the topology of 9 (Mr). Moreover, these metries are computable on graphs in time polynomial in the size of the input graphs and h, up to an additive error of in the case of oo and ów.
While these metrics are polynomial time computable, in Appendix C.2, we derive the same impractical upper bound of O(h n²" log n) for dw. as Chen et al. [26] get for their Weisfeiler-Leman distance and the even worse bound of O(h n²) for ōp. This means that these metrics are not suitable as computational tool practice. Theorem hints that we can instead use easy-to-come co-mopute MPNNs to lower-bound these metrics, which leads to our experiments in Section 6.
MPNNs are Lipschitz in the metrics we defined, where the Lipschitz constant only depends basic properties of the MPNN model. That is, if two graphons are close in our metrics, then MPNNs outputs for all MPNN models up specific Lipschitz constant are close. Formally, let şP = ( be an MPNN model with L layers, and for t E {O..... LJ. let s == (9:)) Then, we inductively define the Lipschitz constant C.p 2 0 of sp by C.p, = for t and Cip, == llvelle (1 llco + C....) for t> 0. This essentially depends on the product of the Lipschitz constants of the functions in 4p, and the bounds for the MPNN output values, which are finite since a continuous function on a compact set attains its maximum. Including these bounds in the constant is necessary since we consider sum aggregation. That is, a constant function mapping all inputs to some E IR has Lipschitz constant zero, but when integrated with measures of total mass zero and one, for example, the difference of the outputs is c. We define C(p.,)) for Lipschitz & analogously by essentially viewing (4,, 1h) as an MPNN model.
Lemma 3. Let yp be an L-layer MPNN model for L E N and 1b be Lipschitz. Then,
[b_ (L) n 112 I Cp dw,,(a,) B) and
||b - hrlla S C(e.,)) Ów,
for all a, 3 E M, and all μr, u E (M,,,, respectively. These inequalities also hold for dw and dw with additional factor of L in the Lipschitz constant.
7

---

4 Universality of message-passing graph neural networks
In this section, we prove a universal approximation theorem for MPNNS on IDMs and DIDMs, deriving our main result from it. For 0 I L S oc, let NE S C,M,, denote the set of all functions h bo) Mr- - _2 for an L-layer MPNN model yp with dz = n. Similarly, let
NNT = (h- 4 L-layer MPNN model, uh: R - IR" Lipschitz] C (())
be the set of all functions computed by MPNN after a global readout. Our universal approximation theorem, Theorem 4, shows that all continuous functions on IDMs and DIDMs, iee, functions on graphons that are invariant w.r.t. the (colors of) the 1-WL test, can be approximated by MPNNs. Hence, our result extends the universal approximation result of Chen et al. [26] for measure Markov chains in two ways. First, measure Markov chains are restricted to finite spaces by definition, which is not the case for graphons and our universal approximation theorem. Secondly, the spaces MI, and 9 (MIr, are compact, which means obtain universal approximation theorem for the whole space of graphons, including all graphs, not restricted to an artificially chosen compact subset.
Theorem 4. Let 0 < L S 00. Then, N1. is dense in C(MI, I)) and NNV dense in (MP(M)) R).
The proof of Theorem is elegant and does not rely on encoding the 1-WL test as an MPNN. That is, it follows by inductive applications of the Stone- Weierstrass theorem [35, Theorem 2.4.11] 11] combined with the definition of IDMs. It is strikingly similar to the proof of Grebík and Rocha [52] for a similar result concerning tree homomorphism densities; see Appendix D.
While the second statement of Theorem 4, i.c., the graphon- level approximation, is interesting in its own right, the crux of Theorem 4 lies in its first statement, namely, that VV is dense in C(ML,, R), immediately implying that the topology induced by MPNNs on (MLL) is the weak topology, i.c, the topology endowed this space within Section 2.
Corollary 5. Let 0 < L S oo and n >> O. Let V E (MML) and (2:), ) be sequence with v4 E (ML)) Then, in - v if and only if h,, - h, for all L-layer MPNN models so and Lipschitz yh: RRd + R".
By combining standard compactness arguments with Theorem 2 and Corollary 5, can now prove that two graphons are close in our metrics and only if the output of all possible MPNNs, up to a specific constant and number of layers, is close. Formally, the forward direction of this equivalence is just Lemma 3, while the backward direction reads as follows.
Theorem 6. Let n 0 be fixed. For every > O, there are L E EN,,C> and 8 > such that, for all graphons U and W, if || - hw ll2 S 6 for every L'-layer MPNN model and Lipschitz 2) 1d + R" with L' < L and C((p.)) S C, then 6p W) S.
We stress that the constants L, C, and 5 in the theorem statement independent of the graphons U and W. The proof of Theorem is simple: one assumes that the statement does not hold to obtaín two sequences of counterexamples, which have to have convergent subsequences by compactness, and the limit graphons allow us to derive a contradiction. This establishes the equivalence between our metrics and MPNNs stated in Theorem 1. Analogous reasoning together with the universality of tree homomorphism densities [52), cf. Appendix D, yields the equivalence between our metrics and tree homomorphism densities. Then, the missing equivalence the tree distance follows from the result of Böker [18]. which connects the tree distance to tree homomorphism densities. See Appendix C.4 for the formal statements of all these equivalences
mesilon-delta-stateen
and their proofs.
5 Extension to graphons with signals
Our focus in this work lies on MPNNs' ability to distinguish the structure of graphons. However, the definitions of IDMs, MPNNs, and our metrics can be adapted graphons with signals, i.e., graphons W equipped with measurable signal function & [0. 1] + K, where (K, d) is some fixed compact metric space. In the following, we briefly sketch how do this. First, replace the one-point space M, by (K, d) and modify the 1-WL for graphons by setting i,w.)).0 = E, i.c., use the signal function as the initial coloring. For > 0, adapt the definition of the IDM spaces Ml, and of the refinement rounds i(w O., of the 1 1-WL for graphons to include the previous IDM of point in its new IDM, like in the original definition of Grebík and Rocha [52]. Omitting the previous IDM, as we have done before in our definition, is only reasonable if the initial coloring is constant. Then, since Ml (K, d) is compact metric space,
8

---

the spaces M,, are compact metrizable as before. Modify the definition of an MPNN model 4p such that Po is Lipschitz function K + R. Finally, adapt the definition of the metries dp.,. and dw, h. by letting dp.o == dw.n == d be the metric of the compact metric space [K, d) and then adapting dp,, and dw, for > 0 to the modified definition of M., by using the product metric. Then, the proofs our results can be adapted to this more general setting. In particular, one can prove a universal approximation theorem since Lipschitz functions on K are dense in C(K).
6 Experimental evaluation
In the following, we investigate the applicability of our theory on real-world prediction tasks. Specifically, we answer the following questions.
Q1 To what extent do our graph metrics óp and dw act as a proxy for distances between MPNNs vectorial representations?
Q2 Our theoretical results imply that untrained MPNNs can be as effective as their trained counterparts when using enough of them. Can untrained MPNNs remain competitive when only using finite number of them (measured by the hidden dimensionalityy)
The source code of all methods and evaluation protocols are available at https: /ttp:p:///gii //github com/ moneg337/finegrain expressivite _GNN. We conducted all experiments on a server with 256 GB RAM and four NVIDIA RTX A5000 GPU cards.
To answer Q1, we construct graph sequence that converges in our graph metrics. Given an MPNN, we compute the sequence of its embeddings on such graphs and the corresponding embedding distance using the fn-norm. Hence, comparing different MPNNs amounts to comparing the convergence rate of their Euclidean embedding distances concerning the graph distances. Concretely, we simulate a sequence of 50 random graphs {G.} for i E [50] with 30 vertices using the stochastic block model, where G, ~ SBM(p. 9t), with p p= 0.5 and & E [0.1. 0.5] increases equidistantly. Let G denote the last graph in the sequence, and observe that G is sampled from an Erdōs-Red Renósi model, i.c., G ~ ER(p) For e [50], compute the Wasserstein distance ow, (G,, G) and the Euclidean distance || |h.. he 2 For demonstration purposes, we compare two common MPNN layers, GIN [115] and GraphConv [89], using sum aggregation normalized by the graph's 's order, varying the hidden dimensions and the number of layers.
Fine-grained expressivity comparisons of MPNNs.
Figure 2 visualizes their normalized embedding distance and normalized graph distance, with an increasing number of hidden dimensions, from left to right. GIN, top-row, and GraphConv, bottom-row, produce more discriminative embeddings as the number of hidden dimensions increases, supporting Theorem 4. Each point corresponds to a different (untrained) MPNN. Note that we interpret the hidden dimension w (i.e., width) as concatenating w random MPNNs. We observe similar behavior when increasing the number of layers; see Figure 3 in the appendix. Untrained GraphConv embeddings are more robust than untrained GIN embeddings regarding the choice of hidden dimensions and number of layers. Figure in the appendix shows the same experiments on the real-world dataset MUTAG, part of the TUDataset [90]. We observe that increasing the number of hidden dimensions improves performance. Nonetheless, increasing the number of layers seems to first improve and then degrade performance. This observation coincides with the downstream graph classification performance, as discussed in the next section.
The surprising effectiveness of untrained MPNNs. To answer Q2, we compare popular MPNN architectures, i.e., GIN and GraphConv, with their untrained counterparts. For untrained MPNNs, we freeze their input and hidden layer weights that are randomly initialized and only optimize for the output layer(s) used for the final prediction. We benchmark on a subset of the established TUDataset [90]. For each dataset, we paired experiments of trained and untrained MPNNs on the same ten random splits (train/test) and 10-fold valis-validation splits, using the evaluation protocol outlined in Morris et al. [90]. We report the test accuracy with 10-run standard deviation in Table and the mean training time per epoch with standard deviation in Table 2 in the appendix. Table I and Table 2 show that untrained MPNNs with sufficient hidden dimensionality perform competitively as trained MPNNs while being significantly faster, with 20%-46% time savings. As shown in Figure 6 in the appendix, increasing the hidden dimension (i.e., the number of MPNN models) improves the performance of untrained MPNNs. Our theory states that it is
We compute Sw.r via min-cost- flow algorithm and terminate at most 3 iterations after the Weisfeiler-Lent colors stabilize.

---

Table 1: Untrained MPNNS show competitive performance as trained MPNNS given sufficiently large hidden dimensionality (3-layer, (iz-iidden-dimensionn)) To be consistent with our theory. we use standard architectures with sum aggregation, layer-wise GGV normalization, and mean pooling, denoted by "MPNN-m." We report the mean accuracy + std over ten data splits.
Accuracy 1
METAG
INIn-RINARY
IMDS-MrunL
NCT1
PRomUNS
REDDOE-RRNAAR
(rainol)
46.20
7861
7A51
89.73
GIN-an (untraino))
78.70 1
47.59 103
7782
73.45 0:00
82.32 1,
Ga GrrphCorr-m (rained)
8162
30.14 1:
38.75 183
63.28 1.
71,49 0.8
82.4 2: 0.19
GraphCouv (untrined)
62.36
71.83
0.29
(2-layer, 1-d)
(2-layer, 8-d)
12-layer, 16-d)
WWW dizt. 1911020
Graph dst
Graph "
Graph dist. 1
GC (2-layer, 1-d)
GC (2-layer, 8-4)
GC (2-layer, 16:d)
MPNN DIEE PRARICT "tt
MPNNN dist Jwct 201
WANN dist 1416
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
Graph
Graph
Graph dist.
Figure 2: MPNNs preserve graph distance hetter when increasing the number of hidden dimensions. Comparatively, untrained GIN embeddings are more sensitive than untrained GraphConv to changes in the number of hidden dimensions.
necessary to use all MPNNS to preserve graph distance, which is impossible compute in practice. Nonetheless, our experiment shows that using enough of them suffices for graph classification tasks.
We also investigate the effect of the number of layers, i.e., the 1 1-WL iteration in IDM. As shown in Figure 7 in the appendix, increasing the number of layers first improves and then degrades untrained MPNNs performance, which is likely due to the changes in MPNNs ability preserve graph distance observed as Figure 5 in the appendix.
7 Conclusion
This work devised deeper understanding of MPNNs' capacity to capture graph structure, precisely determining when they learn similar vectorial representations. To that, we developed a comprehensive theory of graph metrics on graphons, demonstrating that two graphons are close in our metrics if, and only if, the outputs of all possible MPNNs are close, offering more nuanced understanding of their ability to capture graph structure similarity. In addition, we established connection between the continuous extensions of 1 1-WL and MPNNs to graphons, tree distance, and tree homomorphism densities. Our experimental study confirmed the validity of our theory in real-world prediction tasks. In summury, our work establishes the first rigorous connection between the similarity of graphs and their learned vectorial presentations, paving the way for a more nuanced understanding of MPNNs' expressivity and robustness abilities and their connection to graph structure.
Looking forward, future research could focus on extending all characterizations of Theorem graphons with signals. While we briefly sketched in Section 5 how to do this for MPNNs and the metrics we defined, this still presents challenge as tree distance and tree homomorphism densities do not readily generalize to graphons with signals. A different direction could be an extension of our theory to different aggregation functions like max- or mean- mean-aggregattin. Since the 1-WL paradigm of summing over neighbors is crucial in our proofs, it is not clear how one would approach this. Additionally, further quantitative versions of equivalences in Theorem 1, not resorting to epsilon- -ariinta statements, and generalizing our results to the k- WL are interesting avenues for future exploration.
10

---

Acknowledgments and disclosure of funding
This research project was started the BIRS 2022 Workshop "Deep Exploration of non-Euclidean Data with Geometric and Topological Representation Learning" held at the UBC Okanagan campus in Kelowna, B.C. Jan Böker is funded by the European Union (ERC, SymSim, 101054974). Views and opinions expressed are, however those of the author only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Ron Levie is partially funded by ISF (Israel Science Foundation) grant # 1937/23. Ningyuan Huang is partially supported by the MINDS Data Science Fellowship from Johns Hopkins University. Soledad Villar is partially funded by the NSF-Simons Research Collaboration on the Mathematical and Scientific Foundations of Deep Learning (MoDL.) (NSF DMS 2031985), NSF CISE 2212457, ONR N00014-22-1-22
and an Amazon AI2AI Faculty Research Award. Christopher Morris is partially funded by a DFG Emmy Noether grant (468502433) and RWTH Junior Principal Investigator Fellowship under Germany's s Excellence Strategy.
References
[1] A. Aamand, J. Y. Chen, P. Indyk, S. Narayanan, R. Rubinfeld, N. Schiefer. S. Silwal, and T. Wagner. Exponentially improving the complexity of simulating the Weiseeiler-Lchman test with graph neural networks. ArXiv preprint, 2022. 20
[2] R. Abboud, I. Ceylan, M. Grohe, and T. Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Joint Conference Artificial Intelligence, pages
2112-2118, 2021. 20
[3] V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky. On the power of color refinement. In International Symposium on Fundamentals of Computation Theory, pages 339-350, 2015. 17
[4] V. Arvind, F. Fuhlbrück, J. Köbler, and O. Verbitsky. On Weisfeilen-Leman invariance: Subgraph counts and related graph properties. In International Symposium Fundamentals of Computation Theory, pages 11 1-125, 2019. 17
[5] A. Atserias and E. N. Maneva. Sherali-adame relaxations and indistinguishability in counting logics. SIAM Journal on Computing, 12-3331, 2013. 17
[6] A. Atserias, L. Mancinska, D. E. Roberson, R. Sámal, S. Severini, and A. Varvitsiotis. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, pages 289-328, 2019. 17
[7] W. Azizian and M. Lelarge. Characterizing the expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. 3, 20
[8] L. Babai. Lectures on graph isomorphism. University of Toronto, Department of Computer Science. Mimeographed lecture notes, October 1979, 1979, 17
[9] L. Babai. Graph isomorphism in quasipolynomial time. In Symposium on Theory of Computing, pages 684-697, 2016. 17
[10] L. Babai and L. Kucera. Canonical labelling of graphs in linear average time. In Symposium on Foundations of Computer Science, pages 39 46, 1979. 17
[11] A.-L. Barabasi and Z. N. Oltvai. Network biology: Understanding the cell's functional organization.
Nature Reviews Genetics, 5(2):101-113, 2004. 1
[12] P. Barceló, E. V. Kostylev, M. Monet, J. Pérez, J. L. Reutter, and J. P. Silva. The logical expressiveness of graph neural networks. International Conference on Learning Representations,
2020. 20
[13] P. Barceló, F. Geerts, J. L.. Reutter, and M. Ryschkov. Graph neural networks with local graph parameters. In Advances in Neural Information Processing Systems, pages 15280-25293, 2021. 20
[14] I. Baskin, V. A. Palyulin, and N. S. Zefirov. A neural device for searching direct correlations between structures and properties of chemical compounds. Journal of Chemical Information and Computer Sciences, 37(4):715-721 1997. 2
[15] C. Berkholz, P. S. Bonsma, and M. Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems, 60(4))581-614, 2017. 17
[16] P. Billingslcy. Probability and Measure. Wiley, May 1995. 21

---

[17] V. I. Bogachev. Measure Theory. Springer Science & Business Media, Jan. 2007. 4, 28
[18] J. Böker. Graph Similarity and Homomorphism Densities. In 48th International Colloquium on Automala, Languages, and Programming, volume 198, pages 32:1-32:17, 2021. 2, 5, 8, 20, 34, 35
[19] J. Böker. Weisfeiler-Leman Indistinguishabiliyy of Graphons. ArXiv preprint, 2021. 4
[20] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 219(6): 1801-1851, Dec. 2008. 4, 20
[21] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Annals of Mathematics, 176(1):111219, 2012.
[22] G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. ArXiv preprint. 2020. 20
[23] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and deep locally connected
networks on graphs. In International Conference Learning Representation, 2014. 2
[24] J. Cai, M. Fürer, and N. Immerman, An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389 410, 1992. 17
[25] I. Chami, S. Abu-El-Haija, B. Perozzi, C. Ré, and K. Murphy. Machine learning graphs: A model and comprehensive taxonomy. ArXiv preprint, 2020.
[26] S. Chen, S. Lim, F. Mémoli, Z. Wan, and Wang. Peisfeiler-Lehmall meets Gromov-Wasserster Wasserstein. In International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 3371-3416, 2022. 2, 3, 6, 7, 8, 20, 25, 30, 43
[27] S. Chen, S. Lim, F. Mémoli, Z. Wan, and Y. Wang. The Weisfeiler-Lemman distance: Reinterpreta- tion and connection with GNNs. ArXiv preprint, 2023, 20
[28] Z. Chen, S. Villar, L. Chen, and J. Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pages I 15868-15876, 2019. 3, 20
[29] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems, 2020. 17
[30] Z. Chen, L. Chen, S. Villar, and J. Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33: 10383-10395, 2020. 20
[31] C.-Y. Chuang and Jegelka. Tree mover's distance: Bridging graph metries and stability of graph neural networks. ArXiv preprint, 2022. 20
[32] G. Dasoulas, L. D. Santos, K. Scaman, and A. Virmaux. Coloring graph neural networks for node disambiguation. In International Joint Conference on Artificial Intelligence, pages 2126-2132, 2020. 20
[33] M. Defferrard, X. Bresson, and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3837-3845, 2016. 2
[34] H. Dell, M. Grohe, and G. Rattan. Lovász meets Weisfeiler and Leman. In International Colloquium Automata, Languages, and Programming, pages 40:1-40: 14,10 2018. 17, 18
[35] R. M. Dudley. Real Analysis and Probability. Cambridge Studies in Advanced Mathematics. Cambridge University Press, edition, 2002. 7, 8, 18, 19, 26. 27, 28,28,771. 30
[36] D. Duvenaud, D. Maclaurin, J. Guzik, and R. P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, pages 2224-2233 2015. 2
R. Gómez- Bombarelli, T. Hirzel, A. Aspuru-
[37] 7. Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64 (4):330-342, 2010. 18
[38] D. Easley and Kleinberg. Nenworks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
[39] T. Fisner, B. Farkas, M. Haase, and R. Nagel. Operator Theoretic Aspects of Ergodic Theory. Springer, Nov. 2015. 5
[40] J. Elstrodt. Maß- und Integrationstheerie. Springer, Feb. 2011. 23
12

---

[41] A. Frieze and R. Kannan. Quick Approximation to Matrices and Applications. Combinatorica, 19
(2):175-220, Feb. 1999. 4, 20
[42] M. Fürer. On the combinatorial power of the Weisfeiler-Lehman algorithm. In International Conference on Algorithms and Complexity, pages 260-271, 2017. 17
[43] F. Gama, A. G. Marques, G. Leus, and A. Ribeiro. Convolutional neural network architectures for signals supported graphs. IEEE Transactions on Signal Processing, 67(4):1034-1049) 2019.
[44] F. Gama, J. Bruna, and A. Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processiong. 68:5680-5695. 2020.
[45] U. García-Palomarrs and M. Evarist Giné. On the linear programming approach the optimality property of Prokhorov's s distance. Journal of Mathematical Analysis and Applications, 60(3):
596 596-600, Oct. 1977. 24, 28, 29
[46] B. Garel and J.-C. Massé. Calculation of the Prokhorov distance by optimal quantization and maximum flow. ASIA Advances in Statistical Analysis, 93(1):73-88, Mar. 2009. 24
[47] F. Geerts, The expressive power of kth-order invariant graph networks. ArXiv preprint, 2020. 3, 20
[48] F. Geerts and L. Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2022. 3, 20
[49] F. Geerts, Mazowiecki, and G. A. Pérez. Let's agree to degree: Comparing graph convolutional networks in the message-passing framework. In International Conference on Machine Learning, pages 3640-3649, 2021. 20
[50] J. Gilmer, S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for
quantum chemistry. In International Conference Machine Learning, pages 1263-1272 2017. 1,
2, 18
[51] C. Goller and A. Küchler. Learning task-dependent distributed representations by backpropagation through structure. In International Conference Neural Networks, pages 347-352, 1996. 2
[52] J. Grebík and I. Rocha. Fractional Isomorphism of Graphons. ArXiv preprint, Feb. 2021. 1, 4, 5, 6,
8, 19. 34, 36
[53] M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Cambridge University Press, 2017. 17
[54] M. Grohe. Word2vec, Node2vec, Graph2vee, X2vee: Towards a theory of vector embeddings of structured data. In Symposium Principles of Database Systems, pages 1-16, 2020. 18
[55]
M. Grohe. The logic of graph neural networks. In Symposium on Logic in Computer Science, pages 1-17, 2021. 17
[56] M. Grohe. The descriptive complexity of graph neural networks. ArXiv preprint, abs/2303.04613, 2023. 20
[57] M. Grohe and M. Otto. Pebble games and linear equations. Journal of Symbolic Logic, 80(3): 797-844, 2015. 17
[58] M. Grohe, P. Schweitzer, and D. Wiebking. Deep Weisfeiler Leman. ArXiv preprint. 2020. 17
[59] M. Grohe, M. Lichter, and D. Neuen. The iteration number of the Weisfeiler-Leman algorithm. CoRR, abs/2301. 13317, 2023. 17
[60] S. Günnemann. Graph neural networks: Adversarial robustness. In L. Wu, P. Cui, J. Pei, and
L. Zhao, editors, Graph Neural Networks: Foundations, Frontiers, and Applications, pages 149-176 Springer, 2022.
[61] W. L.. Hamilton, 7. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017. 2
[62] N. Immerman and F. Lander. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59-81, 1990. 17
[63] A. S. Kechris. Classical Descriptive Set Theory. Springer, 1995. 5,
[64] N. Keriven, A. Bietti, and S. Vaiter. Convergence and stability of graph convolutional networks on large random graphs. In Advances Neural Information Processing Systems, pages 21512-21523.
2020. 4
13

---

[65] N. Keriven, A. Bietti, and S. Vaiter. On the universality of graph neural networks on large random graphs. In Advances in Neural Information Processing Systems, 2021.
[66] S. Kiefer. Power and Limits of the Weisfeiler-Leman Algorithm. PhD thesis, Department of Computer Science, RWTH Aachen University, 2020. 17
[67] S. Kiefer and B. D. McKay. The iteration number of Colour Refinement. In International Colloquium on Automata, Languages, and Programming, pages 73:1-73:19, 2020. 17
[68] S. Kiefer and D. Neuen. The power of the Weisfeiler-Leman algorithm to decompose graphs. SIAM Journal on Discrete Mathematics, 36(1):252-25) 222522222,,222 2022. 17
[69] S. Kiefer and P. Schweitzer. Upper bounds on the quantifier depth for graph differentiation first order logic. In Symposium Logic in Computer Science, pages 287-296, 2016. 17
[70] S. Kiefer, P. Schweitzer, and F. Selman. Graphs identified by logics with counting. In International Symposium on Mathematical Foundations of Computer Science, pages 319-330, 2015.
[71] S. Kiefer, I. Ponomarenko, and P. Schweitzer. The Weisfeiler-Leman dimension of planar graphs at most 3. Journal of the ACM, 66(6):44:144::3) 2019. 17
[72] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference
on Learning Representations, 2015. 18
[73] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[74] D. B. Kireev, Chemnet: A novel neural network based method for graph/property mapping. Journal of Chemical Information and Computer Sciences, 35(2):175-180, 1995. 2
[75] R. Levie, F. Monti, X. Bresson, and M. M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):
97-109, 2019. 2
[76] M. Lichter, I. Ponomarenko, and P. Schweitzer. Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm. Symposium on Logic in Computer Science, pages
1-13, 2019, 17
[77] L. Lovász and B. Szegedy, Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933 957, Nov. 2006. 4, 20
[78] L. Lovász. Large Networks and Graph Limits., volume 60 of Colloquium Publications. American Mathematical Society, 2012. 1, 4, 5, 19
[79] T. Maehara and H. NT. A simple proof of the universality of invariant/eqqiivarant graph neural networks. ArXiv preprint, 2019. 3, 20
[80] P. N. Malkin. Sherali-adams relaxations of graph isomorphism polytopes. Discrete Optimization, pages 73-97, 2014. 17
[81] Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In
Advances in Neural Information Processing Systems, pages 2153-2164, 2019. 3, 20
[82] S. Maskey, R. Levie, Y. Lee, and G. Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022. 1, 4
[83] S. Maskey, R. Levie, and G. Kutyniok. Transferability of graph neural networks: An extended graphon approach. Applied and Computational Harmonic Analysis. 63:48-88 83, 2023. 4
[84] C. Merkwirth and T. Lengauer. Automatic generation of complementary descriptors with molecular graph networks. Journal of Chemical Information and Modeling,
2005. 2
[85] A. Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):498- 11-988-51.. 2009. 2
[86] A. Micheli and A. S. Sestito. A new neural network model for contextual processing of graphs. In Italian Workshop on Neural Nets Neural Nets and International Workshop on Natural and Artificial Immune Systems, pages 10-17, 2005. 2
[87] F. Monti, D. Boscaini, J. Masci, E. Rodolà, J. Svoboda, and M. M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In IEEE Conference on Computer Vision and Pattern Recognition, pages 5425-5434, 2017. 2
14

---

[88] C. Morris. The power of the BaisfellerLeemal algorithm for machine learning with graphs. In International Joint Conference on Artificial Intelligence, pages 4543-4550, 2021. 3
[89] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, E. Lenssen, Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence, pages 4602-4609, 2019. 1, 3, 9, 20
[90] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann, TUDataset: A collection of benchmark datasets for learning with graphs. CoRR, 2020. 9, 43
[91] C. Morris, G. Rattan, and P. Mutzel. Weisfeiler and Leman go sparse: Towards higher-order graph embeddings. In Advances in Neural Information Processing Systems, 2020. 3, 20
[92] C. Morris, Y. L., H. Maron, B. Rieck, N. M. Kriege, M. Grohe, M. Fey, and K. Borgwardt. Weisfeiler and Leman go machine learning: The story far. ArXiv preprint, 2021. 1, 18, 20
[93] C. Morris, G. Rattan, S. Kiefer, and S. Ravanbakhsh. SpeqNets: Sparsity-aware permutation- equivariant graph networks. In International Conference on Machine Learning, pages 16017-16042, 2022. 20
[94] C. Morris, F. Geerts, J. Tönshoff, and M. Grohe. WL meet VC. ArXiv preprint, abs/2301.11039, 2023.
[95] H. Nguyen and T. Maehara. Graph bomomorphism convolution. In International Conference on Machine Learning, pages 7306-7316, 2020. 20
[96] J. B. Orlin. Max flows O(mm) time, or better. Symposium on Theory of Computing, pages 765-774, 2013. doi: 10. 44444/88800.2488777800 26
[97] O. Pele and M. Werman. A Linear Time Histogram Metric for Improved SIFT Matching. In Computer Vision - ECCV 2008, pages 495-508, 2008. ISBN 778-3-540-88690-7. 2, 26
[98] O. Pele and M. Werman. Fast and robust Earth Mover's Distances. In IEEE International Conference on Computer Vision, pages 460-467, Sept. 2009. 26, 30
[99] Y. V. Prokhorov. Convergence of Random Processes and Limit Theorems in Probability Theory. Theory of Probability & Its Applications, 1956. 2, 6, 23
[100] O. Puny, D. Lim, B. T. Kiani, H. Maron, and Y. Lipman. Equivariant polynomials for graph neural networks. ArXiv preprint, abs/2302. 1556, 2023. 20
[101] P. Reiser, M. Neubert, Eberhard, L. Torresi, C. Zhou, C. Shao, Metni, C. van Hoesel,
H. Schopmans, T. Sommer, et al. Graph neural networks for materials science and chemistry. Communications Materials, 3(1:933, 2022. 1
[102] E. Rosenbluth, J. Tönshoff, and M. Grohe. Some might say you need is sum. ArXiv preprint, abs/2302. 1 1603, 2023. 20
[103] L. Ruiz, I.. F. O. Chamon, and A. Ribeiro. Graphon signal processing. IEEE Transactions on Signal Processing, 69:4961-4976 2021. 4
[104] R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In SIAM International Conference on Data Mining, pages 333-341, 2021. 20
[105] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network
model. IEEE Tronsactions on Neural Networks, 20(1): 2009. 2, 18
[106] G. Schay. Nearest Random Variables with Given Distributions. The Annals of Probability, 2(1):
163-166, 1974. 24, 28, 29
[107] M. Simonovsky and N. Komodakis. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In IEEE Conference on Computer Vision and Pattern Recognition, pages 29-38, 2017. 1
[108] Sperduti and A. Starita, Supervised neural networks for the classification of structures. JEEE
Transactions on Neural Networks, 8(3):714-35, 1997. 2
[109] G. Tinhofer. Graph isomorphism and theorems of Birkhoff type. Computing, 36(4):285-300, Dec. 1986. 18
[110] G. Tinhofer. A note on compact graphs. Discrete Applied Mathematics, 30(2):5532264, Feh. 1991.
18
15

---

[111] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention
networks. In International Conference on Learning Representations, 2018.
[112] C. Villani. Optimal Trunsport: Old and New. Springer Science & Business Media, Oct. 2008.
[113] B. Weisfeiler. On Construction and Identification of Gruphs. Springer, 1976. 1, 17
[114] B. Weisfeiler and A. Leman. The reduction of graph to canonical form and the algebra which appears therein. Nauchno- Technicheshaaaaa Informatsia. 2(9):12-16, 1968. English translation by G. Ryabov is available at https: //www. iti zcu. cz/ tttcc///wwwwe wttp///11111///// /aalf//l__ppppp translation. pdf. 1, 17
[115] K. Xu, W. Hu, J. Leskovee, and S. Jegelka. How powerful are graph neural networks? In
International Conference on Learning Representations, 2019. 1, 3, 9, 20
16

---

A
Additional background
Here, we provide additional background.
A.1 The Weisfeiler-LLeman algorithm and related topics
The 1-WL or color refinement is a well-studied heuristic for the graph isomorphism problem, originally proposed by Weisfeiler and Leman [1 14]. Intuitively, the algorithm determines if two graphs are non-isomorphic by iteratively coloring or labeling vertices. Given an initial coloring or labeling of the vertices of both graphs, e-g., their degree application-specife information, in each iteration, two vertices with the same label get different labels if the number of identically labeled neighbors is unequal. These labels induce a vertex partition, and the algorithm terminates when some iteration, the algorithm does not refine the current partition, i.c., when stable coloring or stable partition is obtained. Then, if the number of vertices annotated with a specific label is different in both graphs, we can conclude that the two graphs are not isomorphic. It is easy to see that the algorithm cannot distinguish all non-isomorphic graphs [24]. Nonetheless, it a powerful heuristic that can successfully test isomorphism for broad class of graphs [10].
Formally, let G (V(G), F(G), E) be a labeled graph, i.e., graph equipped with (vertex-)label function f: ((G) -> N. In each iteration, > 0, the 1-WL computes a vertex coloring C2 V(G) - N, depending on the coloring of the neighbors. That is, in iteration > O, we set
(u) = RELABEL ((CL) (o), (CC, |
E N()))))
for all vertices v in V(G), where RELABEL injectively maps the above pair to a unique natural number, which has not been used in previous iterations. In iteration 0, the coloring Cj == E. To test if two graphs G and H are non-isomorphic, we run the above algorithm in "parallel" on both graphs. If the two graphs have different number of vertices colored e in N at some iteration, the 1-WL distinguishes the graphs as non- non-isomorphic. Moreover, if the number of colors between two iterations, and (f + 1), does not change, i.e., the cardinalities of the images of C/ and C.+e are equal, or, equivalently,
(o) = C( + (++(()) = (w+)(w),
for all vertices and w in V(G), the algorithm terminates. For such t, we define the stable coloring Ch (v) = C. (v), for e in (G).. The stable coloring is reached after at most m IV [V))) iterations [53]. The algorithm can be generalized to the k--W,, leading strict boost in expressive power in distinguishing non-isomorphic graphs.
Properties of the Weisfeiler-Leman algorithm The Ceisfeiler-Lemane algorithm constitutes of the earliest and most natural approaches to isomorphism testing [113, 1 114), and the theory community has heavily investigated it over the last few decades [53]. Moreover, the fundamental nature of the k-WL is evident from various connections to other fields such as logic, optimization, counting complexity, and quantum computing. The power and limitations of the k-WL can be neatly characterized in terms of logic and descriptive complexity [8, 62), Sherali-Adams relaxations of the natural integer linear optimization problem for the graph isomorphism problem [5, 57, 80J, homomorphism counts [34], quantum isomorphism games [6], graph decompositions [68]. In their seminal paper, Cai et al. [24] showed that, for each k, pair of non-isomorphic graphs of size O(k) exists not distinguished by the k-WL. Kiefer [66] thoroughly surveys more background and related results concerning the expressive power of the k-W For 1, the power of the algorithm has been completely characterized [3, 70].
Moreover, upper bounds on the running time [15] and the number of iterations for h = [67]. for the folklore A: = 2 [69, 76], and general k [59] have been shown. For le in 2), Arvind et al. [4] studied the abilities of the folklore k-WL to detect and count fixed subgraphs, extending the work of Fürer [42]. The former was refined in [29]. Kiefer et al. [71] showed that the folklore 3-WL completely captures the structure of planar graphs. The algorithm for logarithmic k plays prominent role in the recent result of [9] improving the best-known rumning time for the graph isomorphism problem. Recently, Grohe et al. [58] introduced the framework of Deep Weisfeiler-Leman algorithms, which allow the design of more powerful graph isomorphism test than Leisnni type algorithms. Finally, the emerging
PStrictly speaking, the 1- 1-WL and color refinement are two different algorithms. That is, the 1- 1-WL considers neighbors and non- neignees to update the coloring. resulting in slightly higher expressive power when distinguishing vertices in given graph; see [55] for details. For brevity, consider both algorithms be equivalent.
17

---

connections between the Weisfeiler-Lemaal paradigm and graph learning are described in two recent surveys [54, 92].
Fractional isomorphisms A matrix X E R is called doubly stochastic if all entries are nonnegative and we have Lier Xıj = I for every j E J and Ejer Xsj = for every E I, i... all columns and rows sum to 1. Note that such a matrix is necessarily square. A fractional isomorphism between graphs G and H a doubly stochastic matrix X (Q)x such that Aç X AAH where AG and Aи are the adjacency matrices of G and H. respectively. G and H are called fractionally isomorphic if there a fractional isomorphism between G and H. A result due to Tinhofer [109, 110] states that the 1-WL test does not distinguish G and H if and only if they are fractionally isomorphic.
Graph homomorphisms Given two graphs F and G, a homomorphism from G a mapping h: V(F) - V(G) such that h(u)h(v) E (GG) for every uv E F(F). Let hom(F, F, G) denote the number of homomorphisms from F to G. Then, F(F, G) = hom (F, (G)) homomorphism density of F in G. We have t(F, G) = t(F, Wa) for the graphon We induced by G. A result due Dvořák [37] and Dell al. [34] states that the 1-WL test does not distinguish G and H and only if we have t(T,, G) ((T, H) for every tree T.
is called the
A.2 Message-passing graph neural networks
Intuitively, MPNNs learn vectorial representation, i.e., a d-dimensional real-valued vector, representing each vertex in graph by aggregating information from neighboring vertices. Formally, let G be graph with initial vertex features h! in Rd for u E V(G). An MPNN architecture consists of stack of neural network layers, i.e., a composition of permutation-invarian parameterized functions. Similarly to the 1-WL, each layer aggregates local neighborhood information, i.e., the neighbors' features, around each vertex and then passes this aggregated information on to the next layer. Following Gilmer et al. [50] and Scarselli al. [105], in each layer, > we compute vertex features
(P) (n(-"), AGG ((h(-1) u I (())))))) TR."
where (PD( and !G may be differentiable parameterized functions, e.g., neural networks." In the case of graph-level tasks, e.g., graph classification, one uses
hg = READOUT ((h!") u ((G))) E R
to compute single vectorial representation based on learned vertex features after iteration L. Again, READOUT may be a diffcrentiable parameterized function. To adapt the parameters the above three functions, they are optimized end-to-end, usually through variant of stochastic gradient descent, e.g. [72], together with the parameters neural network used for classification or regression.
A.3 Topology
We recall some basics from Dudley [35]. Given a set X, topology on X is a collection T C 2 of subsets of X with Ø, X E T such that T is closed under finite intersections and arbitrary unions. Then, the elements of T are called open sety and (X, T) is called topological space. Given two topological spaces, (X, T) and (Y,4), function f: X > Y is called continuous f-) E T for every U E U. If S and I are any sets and f;: S X, function, where (X,, T,) is a topological space, for every i E I, then there is a smallest topology T on S for which every f, is continuous, called the topology generated by the Jr. Given topological space (X, T), of a net; nets do in general topological spaces what sequences do in metric spaces.
define nets and the notion of convergence
Given pseudometric space (X, d), the collection T of all unions of open balls Ba X d(x, y) < r). where æ X and r > 0, is a topology, and T called metrizable and metrized by d. IfT is metrizable, then set U C S is open if and only if for every U and sequence x; + 2, there is some j with I; E for every 2 j. Hence, two metrizable topologies are equal if they have the same convergent sequences. A topological space (X, T) is called Hausdorff if, for all # y in X, there
'Strictly speaking, Gilmer et al. [50] consider a slightly more general setting in which vertex features are computed by h = (PD(1) hh (t11) ( (H (h) (!-) he (t-1) ,[(,, u)) | No(u))))
18

---

open sets U and V with I E U. E V, and U nV- 2. A pseudometric space (X, d) is Hausdorff if and only d metric. A topological space (X, T) is called separable if X has countable dense subset, where subset of X is called dense if its closure is X.
A topologcaal space (X, 'T) is called compact if whenever U T and X = U2, there is a finite V _ 2 such that X = V.. If (X, T) is compact topological space and f: X - Y surjective continuous function from X to another topological space (Y,4), then (Y, is compact. By Tychonoff's theorem, the product of any collection of compact topological spaces is compact w.r.t. the product topology. A metric space (X, d) is compact if and only if (X, d) is complete and totally bounded. Every compact metric space is separable.
Given a set X, o o-algebra is collection A C 2 of subsets of X with 2, E A such that A is closed under complements and countable unions. Then, (X,A) is called a measurable space. For every collection C S 2*, there is smallest r-algebra including C, called the o-algebra generated by C. A o-algebra that is generated by a topology is called a Borel o-algebra; its elements are called Borel sets. A measurable space (X, B) is called standard Borel space if there is separable completely metrizable topology T on X such that B is the o-algebra generated by T. Here, topology is called completely metrizable if there a metric d such that (X, d) is a complete metric space and metrizes T. Hence, every compact metric space with its Borel o-algebra is a standard Borel space.
Let (X be a measurable space. A function μ: A [0] is called measure if p(Ø) 0 and it is countably additive, i.c., if whenever An E A for n = 1,2.... are pairwise disjoint, then n(Uu2) A,) Enzr (.)).. The measure y is called finite if ((X) < 2o.
A.4 The Stone-Weierstrass theorem
The theorem. Here, state the formulation from [35, Theorem 2.4.11]. An algebra is vector space that is additionally closed under multiplication. Recall that, for a compact Hausdorff space K, we denote by C(K, IR) the set of all real-valued continuous functions on K and dau (f (ff.g)) g) = sup=ek|f(e for f.g E C(K, IR).
theorem is the primary tool we use for proving our universal approximation
g(x)
Theorem 7 Ciione-Weierstrass theorem). Let K be compact Hausdorff space and let F be an algebra included in C(K, R) such that F separates points and contains the constants. Then, F dense in C(K, R) for dup-
A.5
The cut distance
The cut norm of kernel U is ||0 || sups.rlJsxr W(x,y) dzdy), where the supremum taken over all measurable sets 5. S [0, 1]. The cut distance of two graphons U and W defined by
(U, W) == inf U W where the infinum is taken over all invertible measure- preservin maps :o: [0, 1] + [0, 1] and U (xx v) = U(((x), (vy)) for all x, y E X. See the book of Lovász [78]
for thorough exposition.
A.6 Distributions on iterated degree measures
Grebík and Rocha [52] give the following definition of DIDM, which slightly adapt to our definitions. The Kolmogorov Consistency Theorem yields that, for every a E MI, there is a unique N4, E MM (MI) such that (Poc,t) ..Jaaa a 0h++1 for every h E N. Then, probability measure
9 (MT is called a distribution on iterated degree measures (DIDM) if Pa is absolutely continuous w.r.t. v with the Radon-Nikodym derivative satisfying 0 < dec
< 1 for u-almost every ar; intuitively. this ensures that, if
de
we have some mass m of points of color c, then every point in the graph may have at most m neighbors of color c. Then, VW for a graphon W satisfies this definition, and conversely, that every DIDM defines a kernel on WI MI that is bounded by one almost everywhere.
B Extended related work
Here, we provided extended discussion on related work.
19

---

B.1 Limitations of MPNNS and the 1-WL
Recently, connections between GNNs and Weisfeiler-Leman type algorithms have been shown [12, 49, 89, 115]. Specifically, Morris et al. [89] and Xu et al. [115] showed that the 1-WL limits the expressive power of any possible GNN urchitecture distinguishing non-isomorphic graphs. turn, these results have been generalized to the k- k-WL, see, e-g., Azizian and Lelarge [7], Geerts [47]. Maron et al. [81]. Morris al. [89, 91, 93], and connected to permutaioon-equivaiinn functions approximation over graphs, see, e.g., Azizian and Lelarge [7]. Chen et al. [28]. Geerts and Reutter [48], Maehara and NT [79]. Further, Aamand et al. [1] devised an improved analysis using randomization. Recent works have extended the expressive power of GNNs, e.g. by using random features [2. 32, 104], equivariant graph polynomials [100], or homomorphism and subgraph counts [13, 22, 30, 95], see Morris et al. [92] for a thorough survey. Recently, Grohe [56] showed tight connections between GNNs' expressivity and circuit complexity. Moreover, Rosenbluth et al. [102] investigated the expressive power of different aggregation functions beyond sum aggregation.
B.2 Graph metries beyond edit distance
As discussed before, the edit distance does not capture the structural similarity graphs well. metric that arguably captures the similarity of graphs well is the cut distance, which was introduced by Frieze and Kannan [41] and provides the central notion of convergence in the theory of dense graph limits. Graph similarity can also be defined via graph homomorphism densities, and as part of the aforementioned theory, Borgs et al. [20]. Lovász and Szegedy [77] proved that this is equivalent to the cut distance. Böker [18] introduced variant of the cut distance based the well-known system of linear equations defining fractional isomorphism, the free distance, which is equivalent to similarity defined via tree homomorphism densities. To study MPNNs' stability properties, Chuang and Jegelka [31] introduced Tree Mover's Distance to compare two graphs via hierarchical optimal transport between their computation trees. Similarly, Chen et al. [26] introduced the Weisfeiler-Lent distance, a polynomial-time computable pseudometric on graphs by combining techniques from optimal transport with the 1-WL, and gave an interpretation in terms of stochastic processes [27].
20

---

C
Proofs
Here, collect proofs that omitted from the main body of the paper.
C.1
Equivalence of message-passing graph neural networks
Here, we show that, first, for graph G. the output of MPNN on equals the output of the MPNN on the corresponding graphon We and, second, the output of an MPNN graphon W equals the output of the corresponding MPNN on corresponding DIDM vW of W. Hence, suffices to consider MPNNs on DIDMs. We note that, while is an MPNN model and y is Lipschitz in the following theorems, we actually do need Lipschítz continuity and continuous functions would suffice.
Theorem 8. Let G be a graph and &p be an L-layer MPNN model. Let (Io) be the partition of [0, 1] used in the construction of We from G. Then, for all E [L]. E V(G), and x L.
h
(()
Proof. We prove the claim by induction on t.
Base of the induction. The first space of colors is M, (1). Then, for all E VVG) and To,
h
P0 h
Induction step. The induction assumption is that h!-1) h(-1) for all V(G) and æ E Ig. Then, for all E V(G) and To, we have
(t-1)
h upc (1/ Wo(e, ()h ax(u)
Σ
/
Wo(e,y) ax(v))
(EV(G)
J. Wo(z,y)h (1-1) d2(x)
Σ WEV(G)
I.
Pr (
Σ
h b((1))
h
NEN(2)
Theorem 9. Let be graph, let &o be L-layer MPNN model, and & be Lipschitz. Let (Lo)vev(C) be the partition of [0, 1] used in the construction We from G. Then,
hg hwo
Proof. With Theorem 8, we get
hwo = 2b ( h d2(x))
h dx(1o) /
= 1
Σ
I.
OEV(G)
1b Σ
1 dX(z))
VEV(G)
I.
([[G)
b(4)) vEV(G)
Σ
-he-
To prove the equivalence of an MPNN on a graphon W and the corresponding DIDM Pw. we need the following definition. Let d: [0, 1] + R be nonnegative measurable function. Then, define the measure Vs by
j,0aA add
(A(
for measurable C [o, 1]. The following lemma, which can interpreted as the "well-definedness of the change of variable 8(y)", is taken from [16, Theorem 16.11].
21

---

Lemma 10. Let o: [0, 1] + R be a nonnegative measurable function. Then, measurable function
f: [0 R is integrable with respect to V/ if and only if fô is integrable with respect to in which case
J f dvs = / fôdd
holds for every measurable A.
Theorem 11. Let W E W and yp be an L-layer MPNN model. Then, for every t E [Z] and almost every 10,
h (0 h
h (m)
(w)
Proof. We only have to show the first equality. Then, the second follows directly from the definitions of h (0) MI + Rd and iw.
Base of the induction. The first space of colors is M, = {1]. Then,
( an
= Po h (x)"
Induction step. The induction assumption that ( (1(12) (iw,e-(()) for almost every æ E [0, 1]. Let us prove the induction step for t. We have
h up (fo W(a.whhh-1 dx(e)).
Recall that for any A E B(M 1),
(iw;())))(A) -fc (()
W(x, v) da(y),
so, by the notation (w,--) introduced before Lemma 10.
iw, = (iw.o-)
Hence, by Lemma 10 with 5 (zz -) and = h (1-1) we have
(.((=) spa (1/ ( h (1-1) diw:((x)) 5r (Fr Jm h (e-1) d(iw.e- 1) (as-)
st (f (e-1) o 1i duw
(fon 10.11
W(x, 1) (t-1)
1-- (w.)-(()) dX(v)
Hence, by the induction assumption, h h (x)"
Theorem 12. Let W W, let yp be L-layer MPNN model, and let be Lipschitz. Then,
hw how. how
Proof. We only have to prove the first inequality; the second follows from the first and the definition of Vw. The first inequality follows from Theorem 11:
how = # (Lo ( dow.r.)
(// h d(iw:))e))
4 (fo (10)) 2 dx(x))
v v n dd(x))
hw-
22

---

C.2 Metries on iterated degree measures
We first prove Theorem for the metrics based on the Prokhorov metric. Then, we prove the inequalities between the Prokhorov metric P and the unbalanced Wasserstein metric W from Section 3 and deduce Theorem for the unbalanced Wasserstein metric from it. After that, we prove Lemma 3.
C.2.1 The Prokhorov metric
To begin, let us restate Theorem 2 for better readability.
Theorem 2. Let 0 < h S cc. The metrics dp, .s and dw,r are well-defined and metrize the topology of Mr. The metries öp, A and dw,A are well-defined and metrize the topology of P (M,)) Moreover, these metries are computable on graphs in time polynomial in the size of the input graphs and h, up to an additive error of & the case of dw and 8w
Let (S,d) be a complete separable metric space with Borel o-algebra B. Recall that, for subset A C S and 2 0, one defines A == { E S S1 d(z, y) < e for some x E A}. Then, the Prokhorov metric on Mgi (S, B) is given by
P(p.v) inf(= > 0 ((A) S ((A + and ((A) S ((AA) + e for every A E B}.
It is not hard to that we can replace A by A = E d(x, y) < for some E A} in the above definition without changing the value P(u, Moreover, if ||||| 2 ||z]|| then the definition simplifies to
P(p.v) v) in > 0 (AA)
- ((A) + E for every A }3}
since, if ((A) < ((A)) + for every A E B, then v( () - 1 (3) + E + ||||| - || & ((B²) + e for every BE B [40, Lemma 4.30].
As the name suggests, P is a metric on (S) [99, Section 1.4], and Prokhorov also proved that convergence in P is equivalent to convergence in the weak topology.
Theorem 13 (199, Theorem 1.11D. Let (S, d) be complete separable metric space. Then, (S), P) a complete separable metric space, and convergence is equivalent to weak convergence of measures.
The well-definedness of dp,,, and 6p, follows from an inductive application of this theorem.
Lemma 14. Let 0 < h S oc. The metric dp.,. is well-defined and metrizes the topology of MI.. The metric dp., R. is well-defined and metrizes the topology of S (M,).
Proof. First, we consider dp. A. Let h E N. To see why even have prove that dp,, is well-defined, note that the measures in MA+1 = M=1 (M,) = Mui (M,, B(M).) by definition are functions the topology of MI, which is the weak topology in case.
μ: B(Mla) + R, where B(M,) depends Hence, it is crucial that dp.,, metrizes the weak topology on M2, otherwise the sets Ms (MI,, ((M)) and Ms (M,, d might not even be the same.
For the induction basis O, this claim trivially holds. Then, the induction hypothesis yields that de, a is well-defined and metrizes the weak topology on M,. Then, dp. is well-defined as the Borel o-algebra of (Mr, dp,,.) equals B(Ml), and, by Theorem 13, convergence in dp, 1 is equivalent to weak convergence on Mz (M,, dp.x. ).). which is just weak convergence Hence, the topology induced by dp .+11 1 is equal to the weak topology on M,+1 1 as both spaces are metrizable. For dp pos the claim directly follows since de, is just variant of the product metric, which metrizes the product topology.
M (Ma, B(M,))
MA
The claim for ōp, then follows from the just proven claim for de by the same reasoning as in the inductive step.
The following lemma states that the distances de behave expected, i.c., the distance of IDMs can only increase when increases.
Lemma 15. Let 0 < h < N'' < co. Then, de (l)) Ph S dp, (a, 3) for all a, Mip-
Proof. It suffices to show that
de, de,(Pp--LM()), Ph+,, S (a, 3),
23

---

for all a, 3 E MA+11 where h 2 O. We prove this by induction on h, where for h = 0, the statement trivially holds. For the inductive step, we assume without loss of generality that ||a ||3 which
directly implies 1,pA+1,a 2 (1=++1a(3)]] We show that if & >> 0 such that (<A) S ((AF) for every ((M then also (1)) S 1h (3) + For such an E, we have
(A) = (P))a)))aa(A) = a(pr))-((A))
S ((P)))- +E
I ((p + Ph+1.( + tE,
where (((PT)h1 S ((P holds by the induction hypothesis: We show that (P -h (A))f (A)) C P Let x E (P (A)) Then, there is a E (Ph,h-1(A)) such that dp, v) < By the inductive hypothesis, we have
dp (ph.1(Pnn-1)) Pp.- S dp, v) <6.
Since (V) E A, we have (x)) E A and thus, x E - ph
C.2.2 Computability of the Prokhorov metric
remains to prove that dp.,, and 6p., are polynomial-time computable. A paper of Garel and Massé [46] is concerned with computing the Prokhorov metric of (possibly non-discrete) probability distributions. To this end, they first quantize the distributions and then show that the Prokhorov metric of finitel-ssuporree probability distributions can be computed exactly by solving series of maximum maximmum-flow problems; this latter part is based on results by Schay [106] and essentially shows how the Prokhorov metric can be formulated generalizing this linear program to finite measures, we can adapt the algorithm of Garel and Massé [46] to obtain algorithm for computing the Prokhorov distance of finite measures.
and Evarist Giné [45], which imnearoptimization problem. By
Theorem 16. Let μr, v E M (5), where (S, d) a finite metric space with S (æi,,... In Then, the Prokhorov metric P(μ, v) can be computed in time polynomial in and the number of bits needed to encode d. μi, and v.
Proof. Without loss of generality, assume that ||л/|| 2 ||||| Then,
P(,, = inf > 0 ((A) s v(AF) + for every A S S} = inf > 0 ({A) S <v(A=) + for every A C S} inf(e 2 0 p(e))
where
p(e) = inf > 0 ((A) S ((Al)) + r for every A S S}
for > 0. The following claim generalizes an observation of Schay [106, Theorem 1] and Gareía-
Palomares and Evarist Giné [45, Lemma] to finite measures and shows that the value of p(E) can be expressed as a linear program.
Claim 17. Let > 0. Then,
ple) |||||| max [d(s,, S [] Fij.
where the maximum taken over variables may such that Σ Fnj = u((r,)) for every j E [n],
Ej=1 Fig S (((x;)) for every i E [n], and æij 2 0 for all i E [n].
Proof. For the sake of brevity, define pa = (x(x;))) and qi = v(fa;}) for E [n] and d; = 1[((x, S E] for all i.j E [n]. We have
p(E) max (a() m(A=l))
Σ (pmw, g.v%) kE(m)
max v, (0,(0,1)
AÇS
wie (0.1).
" 2 -1#
max 050, 31, 05 ar $1,
Σ kE(n)
(pews 9.7%)
By 22 -1+w;
24

---

where the first equality holds by definition of p(=), the second since one can view the sets A and A as vectors ö and w. respectively, and the third. since the optimum value of a linear program is attained on an extreme point of the convex polytope specifying the feasible solutions, which are 0-1-vectors for this specific linear program. Moreover, since values " > and w, < can always be set and O, respectively, without decreasing the value of the target function, this further equals to
max 1y
Σ (p:n - (:2z) = |1 kE(m)
min 20,
E(pau
(peu, + 9:0),
20,
my 20, <E(m!
wi 244
where the second cquality results from the substitution = 1 w. Then, considering the dual to the linear minimization problem yields that this further equals
p |a max
dip Fijs
+J=1
where the maximum is taken over variables Tij such that Σx= Tiy S qj for every j E [m], Ei= Zij S
P; for every E [m]. and mij 2 0 for all i.j E [n]] Since we can always increase the variables Zij such that Σx=1 Taj- = di for every E [m]] holds without decreasing the target function, we obtain the claim.
With this claim, we can use polynomial-tine method for solving linear programs to compute p(s) in time polynomial in n and the number of bits needed to encode d. μr, and v. Alternatively, it is straightforward to express this linear program as a maximum-fiie
problem, which can also be solved in polynomial time. The mapping + p(e) is non- -oc-enncegsin step function whose jumps can only occur at points in D = (d(I), 2,) i,j E [n]]. Let D' = D U {0}. Then, we have
P(u, v) = inf(= 2 0 p()) ( S e}
= min E D' plE) S E { e D' with p(s) > $}),
which can be computed in time polynomial in n and the number of bits needed to encode d, pu and 1/ since D contains at most n values.
Theorem 16 can then be used to compute the distance óp,6 of two given graphs. Intuitively, we run the 1-WL on these graphs in parallel and additionally, after the ith refinement round, compute a matrix D; containing the distances dp,; between any pair of colors. This matrix can be computed from the new colors and D the end, we use D), to compute up. This essentially the same approach that Chen computable. Theorem 18. Let 0 < h < co, and let G and H be graphs. Then, 6p, (G, H) can be computed in time polynomial in h and the size of G and H.
et al. [26] use for showing that their Weisfeiler-Lemall distance is polynomial
Proof. We inductively compute DR E RV(G)XV(H) with Da. = (ic. In practical setting, it makes sense to index D₂ by the colors/IDMs of the vertices instead in practical setting to reduce the size of the matrix and avoid unnecessary computations of the same value. However, for the sake of simplicity, we stick to this definition of Dr. here. For h O. this is just the all-zero matrix. After having computed D... for all pairs of vertices u E (G),, u E V(H), we use the matrix Dn to compute the measures ig,A+1 (u) and (H,++I()) and then use Theorem 16 to compute their distance w.r.t. dp, d--1+1 We note that we do not need the distances between the IDMs of two vertices U E (G) or u, U E V(H) for this. Hence, the matrix Dr E RV(G)xV(H) suffices to compute DA+1 E (G))) Furthermore, we note that we actually do not need to know the precise element of Ml. assigned a vertex do so: we basically run color refinement parallel and its renamed colors after / rounds as our space S. From the coloring after refinement rounds and the matrix D,, another application of Theorem 16 yields the distance 6p,n H) = ôp (VG. VH,)).
Let give rough analysis of the running time of the algorithm from Theorem 18. Let be the maximum number of vertices in the two graphs G and H. Then, we have to compute the Prokhorov metric of two IDMs h n² times and once for the final distance åp, G, H). To compute a single such Prokhorov metric, we have solve n² maximum-flov problems graph with n vertices and n?
25

---

edges, where single maximum-fio flow problem takes time Onn") [96]. Hence, the overall running time is (h n² n² n²) O n²); We will see that the distance ów,r can be computed in time O(h n² log n), which is much better, but nevertheless not ideal for practical purposes. This shows why we need different way of approximating these distances for practical purposes and leads to our experiments in Section 6.
For two graphs G and H on n and m vertices, respectively, the 1-WL test converges after at most max m) refinement rounds, i.e., the color partitions stable and cannot further be refined in subsequent rounds. For dp.A. however, it is conceivable that dp., still changes even after having obtained stable color partitions. More precisely, by Lemma 15, dp,6 may still increase, i.e., we have a second convergence step where the distances dp.a. converge after the color partitions have already stabilized. However, for the Prokhorov distance,
argue that this takes, most, polynomially many steps.
Theorem 19. Let G and H be graphs. Then, oo (G,
(G,H) .)) can be computed in polynomial time.
Proof. Let n and m be the number of vertices of G and H, respectively. Then, the masses that an IDM assigns to a color class are all the form i/(n m) for a natural number i, which implies that the resulting Prokhorov distance between such IDMs also is of this form. This inductively yields that all entries of the distance matrices in the computation of 6p, (G, H) for E are of this form and, with the monotonicity of Lemma 15, we get that all m entries can increase at most n times, i.c., the distance matrix stays constant after at most (n - m)² steps. Thus, the claim follows.
When combined with the previous analysis, this yields that (G, H) can be computed in time On n²) () where n is the maximum number of vertices the two input graphs
C.2.3 The unbalanced Wasserstein metric
Let us now turn our attention to our unbalanced Wasserstein metric. To this end, let (S, d) be complete separable metric space with Borel r-algebra B. We first note that the Wasserstein distance of two probability measures n. E (S) is
/ d(x, dy
W(a, = inf >EC(a.) sxs
where 2(,,)) is the set of all couplings of and v, i.e., probability measures PS S) with marginals and v or, formally, (p1).7 = ju and (p2).7 = v. Section 3, for finite measures U,v E Ms1(S), where where assume || 2 ||]| without loss of generality, defined the unbalanced Wasserstein distance
inf rEM((N) / d(a, u) d7(2,)),
W(n, v) = ||||| - ||-||| +
where M(U, v) is the set of all measures 7 E Ms x 5) such that (P1) S l and (p2)<)= v. We first note that W is well-defined as MM v/) is non-empty since THl (1 x v) E EM(,, v). On probability measures, this definition coincides with the Wasserstein distance [35, Section 1 11.8], and on finite histograms, it coincides with the Earth Mover's Distance EMD, introduced by Pele and Werman [97, 98]. To prove that W indeed is a metric on (S), we follow the proof of Pele and Werman [97] and relate our definition of W to the classical definition on probability measures as follows: For complete separable metric space (S, d) where any two elements have distance at most one and
measure μ (S, d) we define the space (S*,d") dd) and the probability measure μ E (S* d²) by adding new element of mass 1 || that has distance one to all other elements. Formally, we let S = SU {+),
[d(z,g) if S otherwise
d' (x, = {1
for all x; y E S. and
(A) (1 (|]])
if E A, otherwise
(u(A)
for every A E B(S", d²). For measures obtained this way, we have the following.
26

---

Lemma 20. Let (S, d) be complete separable metric space where any two elements have a distance at most one and v.v M1 (S, d). Then, W(n", v²) W(p.)). v).
Proof. Without loss of generality, we assume that || 2 ||]| To show that W(A", v²) S W(J,, v), we show that a 7 E &M(, v) yields ay* E C(u", such that
d' (e) dr (z, ||a||| || - [
d(z,8)
(3)
5xS
To this end, we define 7" C(p,, (1') by
('(C) = >Cn x 5)) + (y
+ (1
EC]
for every C' C BS S). It is easy to verify that 7" actually is probability measure with marginals μ and v². Then,
Joxs: d' d' () dy (2, = {
/
d' dy +
d'(z,))
sx8
1oxxs
(x(()) Soxis d7
S (1
= d(r, y) dr v) 0+ + ||I (p1) +0
|||||| - |||| + f 888
d(z, dy(x, v)-
For the other direction W(n", v*) > W(H, v), we show that a 7 E C(u,, v²) restricts to 7 E &Mu, v) such that (3) holds. Let y denote the restriction of of to B(S x 5). We prove that y E MM(H v). First, we have
= (p)) = = x 5) < (A 5*) = ()) ((()),
and, analogously, (A2)>>(A) - (AA) for every B(S). Now, assume that (p2). (AA) < v(A) for some A E B(S). Then,
||||| = >SS A) 7 A) < u(A) + +(A) = ||oll
which is contradiction. Next, observe that
>" (((+)xx
(+)) = 1 7S 5*) 1 ~S) 1- -11111
-|p/| and also (+)))(())+ 1-|||] By the previous paragraph, we have (5 ( = |||||
which yields that
((*) x 5) + (S ++)) =
= = - 1-||-|
We get >" ((+) S) 0 and, hence, (1+)) x (+)) = ||^4| and, thus, 7 (+)) =ll=|| -||-| From this we obtain
f d' v) dy (x,
{ d(z, v) dz v) + ([+} x x) + 7S x (+))
Jsxs
= |||m|| ||l||| + Jsxs
d(a,y) dy(
Corollary 21. Let (S,d) be separable metric space. Then, W is metric on (gi(Sdd).
Proof. Follows immediately from Lemma 20 and the fact that W a metric on PS* .d"), ) cf. [35. Lemma 11.8.3].
0
27

---

To show that W also metrizes the weak topology. we show that it is upper- bounded by the Prokhorov metric and lower-bounded by another metric that define in the following, For two p. v E Ms (S), let
/ Sdu -
f sdv and V) =
// sdu sdu
K(U, u) = sup S1, 11
sup Iff
be the Cantorovich--Rbbinshhee distance and the Bounded-Lipschit distance of μ1 and u, respectively, where |/ == +| for f:: S RR. We clearly have v) S K( v) < (1, v). (S,d) separable, then K andd /3 metrize the weak topology [17, Theorem 8.3.2).
We lower-bound the unbalanced Wasserstein distance W by the Kkatorovich-RRuinnsttiin distance and upper-bound it by the Prokhorov distance P (with factor of two). This directly implies that W metrizes the weak topology. These incqualities for probability measures are easily found in the literature. Dudley [35], and generalize them to finite measures of total mass most one. There are two ways to go on about this. First, one could use Lemma 20 and show that the analogous statement holds for the Prokhorov distance P; then, these inequalities follow from the ones for probability measures. Secondly, one can prove these inequalities directly, which is what we do here as the proofs provide a better understanding of these metrics, although they are not as straightforward one might expect. In particular, the proof of upper-bounding the Wasserstein distance by the Prokhorov distance [35] is quite complicated. and we follow the simpler proofs outlined in Schay [106] and Garcia-Palomaree and Evarist Giné [45]. which use the duality of linear programming, We remark that the incqualities between the Prokhorov distance P and the unbalanced Wasserstein distance W presented in Section 3 are special case of the following lemma.
Lemma 22. Let (S, d) be complete separable metric space. Then, for all p. (s)
BL( S K(u,)) S W(u, S 2P(u, S 4v BVBLL
Proof. In the following, we assume || 2 immediately from the definition. For the second inequality, we first prove the following claim.
|||||| without loss of generality. The first inequality follows
Claim 23. Let f: S IR" be Lipschitz. Then,
1 fdu - S (dv S I11floo (lell - -I|/ + Ilfllz SSxS d(a, v) dy(z,))
for every y M(H,v))
Proof. Let E MMH, v). Then,
11 fdu 1 fdv
fdp | ddlpp)e + / d(p)) fdv
=
2
5
+ 115 fd(p)) fd(p2)
fdlu - (p)).T)
5
J fulp (0) (1)).r))
+ 11 exs (f(x) (2
<
J [1fllad(w (p1)a7)
[1f(x) f(v)llad7xx.))
5xS
< / [1. (p1).)) I
llfll - -dl,,d((,))) v) dz(
sxS
|1 1111-~1p1 (p:))1 + +1/11
d(a, dr(a, v)
Sx8
= If (Ilx)) - ||||] + llfll
1xxs d(x,y) dy(x, 8)
28

---

The claim implies that, for an f: + R with Il S 1 and ol I 1, we have [[s fdu Is fdul - W(2, vr), and since this holds for every such f. we get K(H, S W(H,
For the third inequality, follow Schay [106] and Garcia-Palomare and Evarist Giné [45], who proved this inequality for probability measures by using the duality of linear programming in the finite case and then lifting this result to the infinite case. Note that we already used this connection to linear programming in as Claim 17 to show that the Prokhorov metric is efficiently computable in Theorem 16.
Assume that || 2 ||/| without loss of generality. If S is finite (or and are finitely supported), we use that P(μ,,) = inf(= > 0 p(e) S }} for the function p defined in the proof of Theorem 16. Claim 17 expresses the value p(e) for an E >> O linear program and we can interpret the solution to this linear program as measure " E MM,,, v) that satisfies p(e) || - Y/ (A,), where
Ag == {(z,)) E x Then,
S d(x,3) 3) S E}. Choose sequence En with En + P(u, v) and ((=n) En
En 2 p(En) = |||||| Tea (4..) |all -lneal + Tea (Dem) || - ||l|| + Yea (A..)
and, hence,
W(n S ||l|| ||||| + / d(x, v) diaa (I,11
Ssx
= ||||| - ||//| + / d(x, v) dY (I, + / d(x, dren, (z,8)
D.n.
Den
3 |al| 110--11 -||/ll + En ll + |ld|ooo Ten (Aen) S 22.6m
which yields that W(H, S 2P,
We can also consider the limit of the Ye.. More precisely, since (S x S) is compact, the sequence Te., by possibly considering subsequence, converges measure 7 of the same total mass, which is ||r]] For this, note that results for probability measures apply since we can just rescale a sequence since all measures have the same total mass. We then have y E M(,, v). ef. the case for S infinite, and for E > P(,, v).
|ell - ||i|| + 7 (e) < |||||| - ||||| + lim inf Yea. (4c)
||||| ||||| + inl Tea (
lim inl e,, P(H, n-+00
n-000
where the first inequality holds by the Portmanteau theorem, which again implies W(H, S 2P v) as before.
The infinite case works by approximating μ and by finite measures and is mostly analogous to [45] as we can rescale a sequence of measures of the same total mass to probability measures. More precisely, one weakly approximates l and by sequences of measures f4, and Vn of total mass || and ||w/|| respectively, supported by the finite set Sn for n 2 1. Then, lim,- P( vn)) P(14, v) by the triangle inequality.
For n 2 0, take "Yo E MMiun, vn) of total mass |||||| for phn and V/ as defined in the finite case, i.e., we S P(un, px) for every 6 >> ((H,, v.). Since fl, and Vn are uniformly tight as weakly convergent sequences, the sequence 7ne is also uniformly tight and, by possibly considering subsequence, converges to a measure y of total mass ||M||| By continuity of p2. we then have that (p2)*% converges to (p2).y. Since (p2)+ Tn Vo converges
have || - ||v|| +
(4x))
get that (p2) y
Morcover,
one can show that (P2).7x Yn I pn, implies that (p2). S μu: For a closed set C' B(S) and an 17 > 0, approximate C by the Lipschitz function fxx max(0, d(n.C)) J. Then, 1 S f < 1c and, hence,
"
(p2)~>(C)= / lod(p2)
/ [d(pe):
lim ( fd(p2)
( 000 Js
lim [ fdpm
n
fdp.
< | 1ondp 1l(r)).
29

---

Since this holds for every 1) > 0 and C' is closed, we get (p2)~7(C) S (CC).. Then, since (p2)~ is
regular by Ulam's 's theorem. we get
(p2)-7(A) = (p2)
| K compact, K A. E B(S) - ((A)
for every A E ((S). All in all, we have 7 E M(H,
For every 8 P(u, v), have P(ung Un) if is large enough since P( pn) converges to P(u, v). Then,
|| - ||||| + (4:) S |Al| - |||||
lim inf Ti (4x) S lim inf P(un; Un)) = P(u, v), n=0000
n-000
where the first inequality follows from the Portmantcau theorem. Then, we get
W(H, v) = ||||| - ||||| + 8 Ibi + ||d]|s r(4.) S e P(U, v),
similarly to the finite case. Since this holds for every s P(u, v). the claim follows.
For the last inequality, show that P(u, v/) s 2vBL((,,)) v) by following the proof of [35, Theorem 11.3.3] for probability measures. We have
P(u, v) = inf ((A) S v(At) + for every A E B(S))
and fix an A E B(S) and an O. Let fx) max(0, 1 d(u.A) }. Then, [[ + and, hence,
m(A) S / fdp
5 fdv + (S, fdy fdv)
/ fdv + 11flBBL BLBBL.BLET BB((,,)
$ J
$ | fdu + (1+1)) BL( S ((AA) (1+ VL(H,
which implies that P( v) S max (1+ + )) (L(,, v)}. For E = BLL v), this yields that P(u,v) < VL, + / BBL v). Hence, if BL v) 1, then P(u,v) I 2 /BL(H, v). If (L( v) > 1, then P(u, v) s 2- /BL(u, v) trivially holds since P(u, S 1 as is and have total mass at most one.
Lemma 24. Let 0 < h < co. The metric dw,r is well-defined and metrizes the topology of M,, The metric Sw.s is well-defined and metrizes the topology of 9 (M,,)
Proof. By Theorem 13 and Lemma 22, for a complete separable metric space (S, d), we have that (S),, W) is a complete separable metric space and convergence in is equivalent to weak convergence of measures. Then, the proof is analogous Lemma 14.
C.2.4 Computability of the unbalanced Wasserstein metric
only remains to argue that dw,, and ōw. are polynomial-time computable. This can be done the way in Theorem 16. i..,, one again constructs matrix of distances that one updates while running the 1-WL in parallel on the two input graphs. Here, the metric W can be computed in polynomial-tine -tme by using the same flow network [98] Chen et al. [26] did in their proof for the polynomial-timg computability of their Weisfeiler-Leman distance. Following their arguments, one then obtains a running time of Oh n² logn) for dw,.. where h E N and is the maximum number of vertices in the two input graphs.
For dw.oo and ow. in contrast to Theorem 16, we cannot argue that all distances are of the form i/(n m)) where n and m are the numbers of vertices the input graphs: with every iteration, we possibly get additional factor of 1/(n m). However, we can start rounding the distances after log(1/s) iterations to integer multiples of 1/(n- m) (1//(), which results in additive error of s.
30

---

C.2.5 Continuity of message-passingg graph neural networks
It remains to prove Lemma 3. Recall that, for an L-layer MPNN model vp (Pi)) we inductively defined the Lipschitz constant Ci 2 0 of &p by Cp. for and
Cp, = 11s (llb (Ihh->1/ls 1100 + Cs, 1)
for > 0. If additionally & is Lipschitz, then
C(e,#) = || (I]b 11 1ls0 + C.p).
Lemma 3. Let up be L-layer MPNN model for L E N and y be Lipschitz. Then,
h hg5 12 S Cip da, () and
||ا hall2 & ((p)))) (w,
for all a, 3 E M, and all μr, (ML), respectively. These inequalities also hold for dw. and ów.oc with an additional factor of L in the Lipschitz constant.
Proof. We first note that, by Claim 23, for complete separable metric space (S, d) and a Lipschitz function f: + R", we have
fddu
11g fdu
S fdv
12 S llfllBz W(p,v).
for all u (.) Let prove the first inequality by induction on L. For L 0, the statement trivially holds since My is the one-point space. For the inductive step, we have
(1
-pa(/r h
(
hg 112
112
p2
h h -h dada)
1) dB
11 11 114-11 da /
(1
2
l|pelle
(1 BL W(a, B3
1|pr.11.
(11h1--1)1 111h (|x.) dw. (a, B)
< ||
(11h("->)) + Cpp..) do,
= Cp dw,
for all a. Mr by the induction hypothesis. Hence, we get the first inequality. The second equality then follows from the first by the same reasoning as in the inductive step above.
It remains prove the inequalities for dw and ōw These follow from the two just-proven inequalities. First, for all a, 8 E Mzi (M), we have
h (L( h 122
( (2) (2)
112 S Cp (Po, Poo
Pa) Pm)
< Cpp L d. (a, 3).
Second, for all nt v E (MI), we have
||b h [l((pe.)).. h(pso.)) S C(pp,) Sw.L(PPoe,Lddl (Poo.L)eM)
S C(pp,) L (w,
C.3 Universality message-passingg graph neural networks
Here, we prove our universal approximation theorem for MPNNs on iterated degree measures, which states that the sets N/ and AN? are dense in C(M,, R) and C(P(M,). R), respectively. follows, by simple inductive applications of the -eiirsressss theorem, ef. Appendix A.4, to the set N? Essentially, we show that Ni satisfies all requirements of the Srone-Weierstrass theorem. Then, an application of the Stone- Weieessrssssssss theorem combined with the definition of iterated degree measures
31

---

yields that that 1 separates points, which allows us to show that N again satisfies all requirements of the Stone-Weienseee Weierstrass theorem. In the following, to stress the dependence of h and h_ on the MPNN model yp and on the MPNN model yp and the Lipschitz function g), we sometimes write so (t) and (4p, 4))
instead, respectively.
Lemma 25. Let O I t S cc. The set Nf is closed under multiplication and linear combinations, contains 1M, and separates points of Mr.
Proof. Base of the induction. For t = 0, the claim trivially holds as No contains precisely the constant functions and Mlo {1} is the one-point space.
Induction step. Let t 0. Clearly, contains the all-one function 1M, since we can always choose yr in an MPNN model to be the all-one function. Next, consider two functions _ and yp' (t) from Nf for t-layer MPNN models ip and yp'. Define (mr ")² x y and riadd (I, v) I, E R, where e E IR is fixed. Then, define the MPNN model
c y for all
mul == (Po x 400 -P0....,PP.. Pt-1 4 Umul o (ype x 44))
and define aad analogously via vadd Note that mul is in fact MPNN model since multiplication compact, and hence, a bounded subset of IR² is Lipschitz continuous. Then,
6 cc (0) addd_
4 mull-
and
which implies that N2 is closed under multiplication and linear combinations.
Finally, let a, 3 M, = 1 (Ml-1) with a + 3.. By the induction hypothesis, the W/-_ ] is closed under multiplication and linear combinations, contains 1M.- and separates points of M, Hence, it is a subalgebra of C(M4-11 that separates points and contains the constants. By the -eierWeiesss theorem, Mt_ is dense in ((Mi-1),, which means that there is a (t 1l-layer MPNN model sp with output dimension one such that
/ M,-1
- dex + 1
/
40hh ((-11)
Define the I-layer MPNN model sp' == (po..... ;8P--111---- Vir),, where via((x) == for every x E R. Then, sp' EN,, separates a and B3 since
4 (1) = /
1!1-t) der # I 03 =40²""
Mc-1
cf. Section 2.
The claim for N1 now easily follows: Ao. contains the all-one function ly = IM o Poo,0 E N and separates points of MI since, if we have a, 3 E M with ل 3, there is some & N such that a # 3r. By the already proven claim for N7, there a f-layer MPNN model yp with output dimension one such (t) (t) that you + P3.. Hence, 40 (a) Ga # 4 9,
(2) (9) ( for sp!h) (t) Poo.t E EN
To see that N2 is closed under multiplication and linear combinations, let _h Poo,t and up'_ (f)) Poo.s be two functions from Ml where &p and yp' are I-layer and l' l'layer MPNN models with output dimension one, respectively. We assume that 2 l': the other case analogous. Then,
pp (C) Poe,t' sp" (1') o Pt.t' Poo.t
by the definition of Mlx. For now, assume that vp__ (t') o Pr E Ng. Then, by the already proven claim for N7, we have sp (4p (1) pr,)) op.r) E A7, which means that
(40 (1) o po..t) (4p2 (t') Poo.)) = ( (vp' (t') p.,))) o Poo. E Na-
This implies that N1. is closed under multiplication, and by analogous reasoning, we get that it is closed under linear combinations. To finish the proof, remains to show that yp" (t') Pt, E Ma. which follows from the following claim.
32

---

Claim 26. Let 1, 0. Let yp be t-layer MPNN-model with d, Then, h opti1 E EN t+1
Proof. We prove the claim by induction on
Base of the induction.
1 = 0, we have ha = so for every a E Mo, i.e., the only element of Mr mapped to PP E IR". Let yP R - IR" be the constant function that maps all inputs to yPo and define the 1-layer MPNN model yp' = (50. sF1). Then,
(0.1((a) = =po +p0==11 = godax
g (0)
Pa
for every a E M,, i.e, _0 o P1.0 =p'-00 (1) NN.
Induction step. Let t > 0 and &p be a t-layer MPNN model. Then, for every a E M4-1, we have
(40 oa))))))) (1
- dprriala)) -v (1
_ (111) d(pr.-1)+(aa)
PPr
M
By the induction hypothesis, we have s0th Pr NNt ie., 1p (t-1) MPNN model sp'. Hence, we have
Pt,t11 sp'_ (4) for t-layer
(s0 o oett,))a)) = = (11 sp_ (1) 12""dcy do
for every a M4++1, where sp" = . (P)) is an MPNN model with + 1 layers. Hence, pit1. E N
With Lemma 25, we immediately obtain Theorem which we restate here for better readability. Theorem 4. Let & L S co. Then, N3 is dense CMML, I)) and NNT dense in C( (MM)), R).
theorem is applicable to N₁, and hence, Nt. is dense in C(M,, R... We can then use this show that ANV is dense C (3) (M)(M,, R). By the same arguments as in the inductive step in the proof of Lemma 25, NNV is closed under multiplication and linear combinations, contains the all-one function, and separates points of (M,,) Hence, an application of the Stone-Weierstrass theorem yields that NSV2 is dense in C( (MM)))
Proof. By Lemma 25, the
Theorem then yields Corollary 5.
Corollary Let E I. S co and Let (M,,) and (ui); sequence with is E (M,,) Then, vi if and only if h,, h, for all L-layer MPNN models &p and Lipschitz ; Rdd 1
Proof. First, let n 1. When restricted to functions h NNF of the form h, -SM, (D) dv, i...
the function v is the identity, the claim follows since A² is dense in C(MI,. R) by Theorem 4 and the definition of the weak topology on (M,,, cf. Section Since the function & the definition of h E ANV. which, in general, is of the form h v/ ( h (2) du). is continuous, the equivalence also holds when considering all functions in the set ANN Finally, since one can always consider the projection to single component and conversely map a single real number to a vector of these numbers. the cquivalence also holds in the case 1.
33

---

C.4 Equivalence of distances
Here, we formally state and prove Theorem Let us first recall the informal statement from the main body of the paper.
Theorem (informal). The following are equivalent for all graphons U and W:
1. U and W are close in öp (or alternatively ōw).
2. U and W are close in 62.
3. MPNN outputs on U and W are close for all MPNNs with Lipschitz constant and L. layers.
4. Homomorphism densities in U and W are close for all trees up to order k.
Let us give an overview of the proof. The implication (1) + (3) is just Lemma 3, and its converse is Theorem 6. Convergence of measures in (M in the weak topology is equivalent to convergence in óp (or Rw) by Theorem 2, convergence of all MPNN outputs by Corollary 5, convergence tree homomorphism densities by Grebík and Rocha [52]. cf. Appendix D, and thus, convergence in the tree distance by Böker [18]. Therefore, the remaining equivalences
follow with a compactness argument similar to the in Theorem 6; this was also used by Böker [18] prove the equívalence of (2) and (4). Let us formally state the equivalence of all mentioned notions of convergence in the following theorem.
Theorem 27. Let (Wa); sequence of graphons W [0, 1]2 + [0, 1]. and let W [0, 1]2 - [0, 1] be graphon. Then, the following are equivalent:
1. (W, W) + (or equivalently (w, W) -> 0).
2. (W,, 2. W) - O.
3. hw, + hw for every MPNN model op and Lipschitz sh: Rd RD. where 0.
4. t(T, W.) + t(T, W) for every tree T.
5. VW, + VW.
Proof. (1) and (3) are equivalent to (5) by Theorem 2 and Corollary 5. (2) equivalent (4) by [18]. which in turn is equivalent to (5) by the result of Grebik and Rocha [52], cf. Appendix D.
We note that we only state Theorem 27 for graphons and not elements of (M since the tree distance of [18] only defined for graphons and not for probability measures. We further note that the following non-approximative variant of Theorem 27 also holds.
Theorem 28. Let U and W be graphons. Then, the following are equivalent:
1. (U W) 0 (or equivalently dw(U, W) 0).
2. o (U, W) O.
3. hy hw for every MPNN model y and Lipschitz vh: Rd - R", where n > 0.
4. (TTU) = (T, W) for every tree T.
5. vy = kw-
Proof. (2) is equivalent to (4) by [18]. The other equivalences follow as in Theorem 27 since P ((M) is Hausdorff.
Let us now demonstrate how compactness can be used to deduce Theorem from Theorem 27, For the direction (1) = (3), we actually do not need compactness since Lemma 3 already is slightly stronger statement. For the sake completeness, we nevertheless state it as an epsilon-delta statement.
Theorem 29, Let n >> be fixed. For every L E C 0, and 0, there a such that, for all graphons U and W, if 8p (U, W) < 8, then || hwll2 S e for every T/- I'-layer MPNN model &p and Lipschitz eb dR + 1n with L' < L and O(p.v) < C.
Proof. Follows immediately from Lemma 3.
Let us formally prove the converse direction (3) (3)+(1)
Theorem 6. Let n > 0 be fixed. For every > 0, there are L E N, C > 0, and 8 > such that, for all graphons U and W, if ||h hw 2| < 8 for every L' L'-layer MPNN model 6p and Lipschitz bb: 1d + R with L' < L and C(ip.v) C, then 6p W)) S.
34

---

Proof. Assume that there is an E > 0 such that such LE N. C > 0, and 5 > 0 do not exist. Then, for every & 0, there are graphons Ux and Wx with | hw, 2l 1/k for every MPNN model ip and Lipschitz ve with output dimension at most k layers and ((p),v) I k but also óp W&) > E. By the compactness of the graphon space, there are subsequences (U%, ) and (Wa,) of (UR)a and (Wa)a converging to graphons U and W, respectively, in the cut distance and, hence, also in the tree distance. Let &p be an I.-layer MPNN model and th: Rdi + R2 be Lipschitz. Then, by Theorem 27, also (hus, ) and (hw,, ) converge to hy and hw. respectively. Hence,
bb hw S | hu: ||2 + llbu: -hw,, lll + llbw:, -hw 112
k k
by the assumption, i.e., hy = hw Since this holds for every MPNN model and Lipschitz eb we have Óp W) 0 by Theorem 28. Then, however
(U W:.) S óp(U,,, , U) + dp (0( + (w, W..) k-oc,, 0
since (Us+), )a and (W wgg)s ) converge to Ü and W, respectively, also in 6p by Theorem 27. This contradicts the assumption that dp (Uk, W&) > for every & 2 O.
In the above theorem, we could simply replace op by dw or o the proof is analogous. We can also state the equivalence of these metries explicitly, e.g. graphons that are close in óp are close in &z and vice versa.
Theorem 30. For every & > 0, there is a > 0 such that, for all graphons U and W, if (U, W) & 5, then (U, e.
Proof. Assume that there is a a > 0 such that such a 5 > 0 does not exist. Then, for every k 2 0, there are graphons Uy and Wx with (Uk, Ws) S 1/k k but 8 (Uk. W₂) > E. By the compactness of the graphon space, there are subsequences (U..). ) and (W..): ) of (U*)): and (Wk),, weakly converging to graphons U and W, respectively, in the cut distance and, hence, also in the tree distance, which in turn by Theorem 27 means that they also converge in óp. Combining this with the assumption yields that (ū W) 0, which implies of (Ū, W) 0 by Theorem 28, This, however, is contradiction to (Uk, Wx) > since (U )x and (W; converge to Ú and W. respectively, in oG.
Theorem 31. For every E > 0, there is an 8 > 0 such that, for all graphons U and W, if (U,,) s 5, then 6p (U, W) S.
Proof. Analogous to Theorem 30.
The equivalence between the tree distance and tree homomorphism densities was proven [18]. Let us state them here for the sake of completeness. Note that the statements are essentially the same as Theorem 29 and Theorem 6, where the constant and number of layers is replaced by the order & of the trees.
Theorem 32 ([18, Corollary 20]). For every tree T and every > 0, there is a d > 0 such that, for all graphons U and W, if (U, W) < 8, then [[T,, U) (T, W) S
Theorem 33 (118, Corollary 21D. For every e O, there k > 0 and 8 such that, for all graphons U and W. if [(T,, U) (T, W)] for every tree T on ls vertices, then ([(U, W) S 8.
35

---

D Tree homomorphism densities
We briefly repeat the proof of Grebík and Rocha [52] for universal approximation theorem for (linear combinations) of tree homomorphism density functions. The purpose of this is twofold. First, it serves as reference since we use this result for part of the proof Theorem I. Secondly, however, illustrates the striking similarities between tree homomorphism densities and MPNNs. Not only do both tree homomorphism densities and MPNNs satisfy a universal approximation theorem, but the theorem statements and proofs in this section for tree homomorphism densities and in Appendix C.3 for MPNNs are nearly identical. Hence, tree homomorphism densities and MPNNs are two different ways of arriving at the same end goal, set of functions that has certain properties and, in particular, describes the similarity of graphons modulo the 1-WL test.
The following definition is implicit in Grebík and Rocha [52]. For rooted tree T of height at most E N. we inductively define the homomorphism density function tn (T, MI. - [0, 1] by letting ta (T.-) = 1M, if the height of T is zero and
ta (T, = (SS tn 1n-1 (n
( in 1n-1(TK,)) do
for every a E Mr if > O, where Ti..... . Ta are the trees rooted in the children of the root of T. Intuitively, to (T, a) is the homomorphism density of T when the root of T is mapped to point of color a. Additionally, we define (T., :): M + [0. 1] by (T, -) = Ln (T, o poo.h- One can show that this is well defined, i.e., that the definition is independent of h. by simple induction.
Lemma 34. Let T be rooted tree of height at most h. Then, t (T, fx (T. Ph+1,A-
Let O < h < co. For a rooted tree T of height at most h and v E (M,), define t(T, v/) = SM, to (T, dv. For the DIDM FW, associated to graphon W, this then simply equals the homomor- phism density of in W when viewing T as unrooted.
Lemma 35 ([52, Proposition 7.3]). Let 0 < h S oc, let T be rooted tree of height at most h, and let W E W be a graphon. Then,
(T, W) (w;)) ((T, uw),
where T in the expression t(T, W) treated as unrooted.
For 0 < h < 00, let
To = (T, T rooted tree of height at most h3 S C(MA,
and let T/ be the set of linear combinations of functions in Th. The set Th is not closed under linear combinations, which is why we have to consider the set T% to obtain a sub-algebra of C(MI,, R) to which the Coone-Weierstrass theorem is then applicable. In fact, Ti, is clearly not dense in CMM,, R) since the codomain of every function in T% [0, 1]. Other than that, the proof of the following lemma identical to the proof of Lemma 25.
Lemma 36 (152, Proposition 7.5)). Let 0 < h S co. The set Th, is closed under multiplication, contains IM, and separates points of Ml,.
Proof. Essentially, the proof is analogous to Lemma 25, When showing that T, separates points of M,, cannot apply the Weierssrrssss theorem directly since the set of Tr, is not closed under linear combinations. However, one can apply it to Th instead and obtain that there always is a separating linear combination. Then, if linear combination separates two points, function in the linear combination has to separate these points, too.
For < S oc, let
TTe = (v
rooted tree of height at most h}} S C(P(M,
and let TTK be the set of linear combinations of functions in TT,, We then obtain the following universal approximation theorem for linear combinations of tree homomorphism density functions.
Theorem 37. Let 0 < h < co. Then, Ty is dense in C(M,, IR) and TTV, is dense in C(P R).
36

---

Proof. Th has all the properties as listed in Lemma 36 and is additionally closed under linear combinations, which means that the -eiiesrsssssss Theorem is applicable, which immediately yields the first claim. The first claim together with another application of the claim, where we in the proof of Lemma 36 use that if function TT, separates two probability measures μ. E P (M,,, then so does a function in TTh
Seieeeesssssssss Theorem then yields the second
L
Lemma 38. Let 0 S h S 0o. Let (v:), be a sequence of measures from P (M,). and v E (MM.)) Then, 2/ - if and only if tTT, p4) > t(T, v) for every rooted tree T of height at most h.
Proof. Follows from Theorem 37 and the definition of the weak topology. Here, we use that the integral and the limit are linear, which means that we can replace the set Tk by the set Th in order to obtain the exact statement of this lemma.
Let us conclude this section with what is known as the "counting lemma" in the world of graph homomorphisms, or in other words, tree analogue to Lemma 3. Formally, we prove that tree homomorphism density functions are Lipschitz in the metrics we defined in Section 3, where the Lipschitz constant only depends our metrics, then all tree homomorphism densities for trees up to a certain order are close. Hence, in comparison to Lemma 3, the order of the tree takes the place of the constant and number of layers of an MPNN model.
the order of the tree. This implies that if two graphons
close in one of
Lemma 39. Let E and T a rooted tree of height at most h. Then,
It. a) to (T. 3)1 = [TT) da, B) and [t(T t(T, w)1 S (V( ów.n for all a; 3 E Ml, and all p. P (M,)), respectively. These inequalities also hold for dw and òw with an additional factor of h in the Lipschitz constant.
Proof. We prove the first inequality by induction the height of T. If it is zero, the statement trivially holds. For the inductive step, let Ti...., Th denote the trees rooted in the children of T' Then,
M (T, a) - (T, = II RE(A)]
/ (n-I(Ti,)doo da
II xE(ki
/ Ma-1
1n-1(T;,) :) dB
Ma-1
1n-1 do
th- (1..
(E(R]
M,
Mnn
< ||ta-1 (TT, )BBB
BL((a,
kE[k]
x Σ (1 + |[ta- W(a,
(E(k]
< Σ (1 E(T))) W(a,
<E(M)
[E()) W(a, 3) = [E(T) dw.i 3),
which proves the claim. The second incquality then follows from the first. We have
1f (T,, S/a. (n(T,-) del
< ||ta (I. BL(,,))
< (1 + [E(T))
Let (TT) denote the height of T. Then.
(TT, tTT, |t[T, |t,T, (o))) - tTT.T(TTT.. Poo, (8))
< [E(T) dw.arr (Poc, (Poc, (a), Poe Por (8))
< [E(T) h(TT) (a,
37

---

for all a, B E Mcx and
= (Poc, E(T, (Poo.ieT)) (12) SIV(I)) (w..cr)((PP (Poc))(T)) <IV(T)) -h(T) &w (1,, v);
for all n. V E (MMoo)) where the last inequality follows from the definition of do
38

---

E
Additional experimental results
Here, we provide additional experimental results.
E.1
Graph distance preservation
GIN (2-layer, 8-d)
GIN (3-layer, 8-d)
GIN (4-layer, 8-d)
Mariy dist max 166 1i6d
MPNN dist. Iw6.. s(
1.00
I9iG.l <(G
mesl- Aedo 100 "e Tre dist NNdW
maxipe,
0.75
0.50
0.25
0.00
Graph dist. max (G,
Graph dist, 6w1G. max Ow (G,
Graph dist. Bwl., G)
GC (2-layer, 8-d)
GC (3-layer, 8-d)
GC (4-layer, 8-d)
MPNN dist. Iyle) [
11.00
sere Look
191 - (lle]
1991 mox
0.75
MNGGM dist pood
0.50
dist. MNdW
0.25
0.00
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Graph dist.
GelG,
Graph dist.
GulG, G)
Graph dist.
6y13, G)
&ec (G.
(G. G1
6n (G.G)
Figure 3: Increasing the number of layers first improves and then degrades the ability of MPNNs to preserve graph distance. Comparatively, untrained GIN embeddings are more sensitive than untrained GraphCony to changes in the number of layers.
39

---

GIN (2-layer, 4-d)
GIN (2-layer, 16-d)
GIN (2-layer, 64-d)
Ipion Tofee pell
max (e0 1994
MPNN dist. [ela. [
11.00
Lilee
Jole] eeee Dex
0.75
0.50
MONN dist.
MPNN dist.
0.25
0.00
Graph dist. Ge(G.G]
Graph dist.
delG, GJ
Graph dist. 0y13, G)
max
max
GC (2-layer, 4-d)
GC (2-layer, 16-d)
GC (2-layer, 64-d)
MPNN dist. IvG..) (16J--p ||
1.00
- 164
1994 199 ween
0.75
PPNNN dist. man
W00 8
0.50
MMdW disc.
0.25
MPPA
0.00
0.0
0.5
0.5
0.0
0.5
Graph dist.
6w10.
Graph dist.
Graph dist. 6w1G.
max maxxBllG.
max Ow (C), GT
max Dw (G,
Figure 4: For MUTAG, MPNNs preserve graph distance better when increasing the number of hidden dimensions.
GIN (1-layer, 64-d)
GIN (2-layer, d4
GIN (3-layer, 64-d)
mox ((( - plill
MPNN dist. [yle)- |
1.00
see Lolel
0.75
0.50
MPNN dist.
ais N. MMNvi Mi
0.25
0.00
Graph dist. 6w1G..
Graph dist.
&wiG. G1
Graph dist.
6w13 .G
G]
GC (1-layer, 64-d)
GC (2-layer, 64-d)
GC (3-layer, 64-d)
lis
I (oo beeu
MPNN dist. (p(a)) ||G||
1.00
llel - (994)
Seee -
max]pic.)
0.75
WOM 8
0.50
PPNN dist
dist NNdW
0.25
0.00
0.0
0.5
Graph dist.
Graph dist.
fwGG. max Oer (G. GT
Graph dist.
6w1G,
max Dy
max Dwe (G.
Figure 5: For MUTAG, MPNNs preserve graph distance worse when depth increases beyond a certain threshold.
40

---

E.2
Untrained MPNNS
Table 2: Untrained MPNNs are significantly faster than trained MPNNs. We report the mean training time (in milliseconds) per epoch + std over 200 epochs.
Time
MUTAG
IMDB-Brnh BINARY
IMDE-MULTI
NCI1
PROTEINS
REDDIT- REDDIT-BINARY BINARY
GIN (trained)
17.09 0.04
101.23 i: 0.07
148.09 1: 0.03
321.52 = 0.07
90.31 0.06
291.41 = 0.18
(untrained)
9.17 +
65.09 + 0.01
98.49 0.17
180.54 0.02
48.52 0.00
210.29 0.03
GraphCCnv (trained)
12.02 0.01
80.59 + 0.07
118.28 + 0.03
226.31 = 0.07
65.01 0.06
228.08 = 0.18
GraphCConv (untrained)
+
64.44 + 95.41 0.17
163.08 0.02
0.00
185.76 0.03
Table 3: When the hidden dimensionality is smaller (3-layer, 128-hiddeenddmmnsioon)) untrained GIN-m still competitive as trained GIN-m, whereas untrained GraphConv-ny is less competitive as trained GraphConv-ni We report the mean accuracy + std over 10 data splits.
Accuracy
MUTAG
IMDB BINARY
MULTI
NC11
PROTEINS
REDDIT BINARY
GIN-m (trained)
78.8 :: 2,05
69.76
1.44
45 55.63 d: 1.07
78.8
0.58
73.11 + 0.7
84.15 1: 0.71 78.8 +: 0.5
GIN-m (untrained)
78.34 +: 2.0
70.31 + 0.74
46.75 :: 1.17
71.86 0.29
73.17 1: 0.63
GraphConn (trained)
81.96 J. 1.78
67.69
1,56
44.71 1. 0.98
64.06
0.45
71.37
0.61
81.9 0.35
GraphConv-m (untrained)
66.75 :: 0.42
62.33 + 0.87
42,54 + 1.47
62.31
0.35
71.51 1: 0.58
74.09 + 0.34
Table 4: For standard MPNNs using sum aggregation, sum pooling, and without I/V(G) normalization (denoted as "MPNN-s"), the untrained ones also show competitive performance trained ones (3-layer, 228-hiddeen-dimension)) We report the mean accuracy + std over 10 data splits.
Accuracy
MUTAG
BINA-B
MMDB-MULTT
NCTI
PROTBINS
REDDrT- BINARY
GIN-s (Irained)
80.99 1. 3.57
69.06 1 1.31
44.59
0.91
76.91
0.44
72.72 0.93
80.33 1. 1.62
GIN-s (unirained)
81.78 +:
0.86
77.59
0.45
0.80
83.22 +
GraphCony-s (trained)
70.74 d: 2.47
$7.39 1: 2.20
35.89
2,00
56.89
1.14
63.6 1: 0.97
$4.82 :: 2.35
GraphiConv-s (untrained)
71.35 +
$2.06
1.09
1.88
1,26
52.45 + 1.63
Table 5: Trained and Untrained MPNNs (3-layer, 512-hicdenndimmension with mean aggregation and mean (graph-level) pooling, denoted by "MPNN-mean -ean".. We report the mean accuracy std over ten data splits. Although theoretical results do not apply to mean aggregation, still that untrained MPNNs are competitive compared to their trained counterparts.
Accuracy
MLTAG
BIDB-BINARY
INDS-MULTI
NCI1
PROTEINS
REDDIT- BINARY
GIN-menn (traind))
74.63 + 2.93
49.48 1,56
33,70 1.35
73.74 + 0.45
71,53 0.93
50.04 0,70
GIN-mean (intrained)
49.18
+:
77.16
70.33
49.90
GraphComm onv (mained)
33.15
54.39 1.25
49.68 0.82
GraphConv mean (untrained)
63.30 4: 3.55
48.50 1.91
32.51 4: 0.90
55.84 d: 0.53
70.73 4: 0.69
49.39 d: 0.48
41

---

GIN (3-layer, normalized)
GraphConv (3-layer, normalized)
trained
trained
untrain
untrain
accuracy
accuracy
102
10a
hidden dimension (log scale)
hidden dimension (log scale)
Figure Increasing hidden dimension (number of functions) improves untrained MPNN performance, supporting Theorem 6.
GIN (128 1-28-hid-dae dim, nomallizdd
GraphConv (126 1128-hid-dae dim, normalized) trained untrain
trained
untrain
accuracy
75
accuracy
number of layers
number of layers
Figure 7: Increasing the number of pessage-passsing layers (number of 1-WL iterations) first improves and then degrades the performance of untrained MPNNs.
42

---

Table 6: Classification accuracy of 1-NN graph distances. Results of dwL. taken from [26] using node degrees as initial labels.
Accuracy
MUTAG
IMDB-BINARY
WLL [26]
91.1 = 4.3
69.4 + 3,9
dLLB [26]
85.2 = 3.5
69.8 +
8w,3 3
87.89 +: 4.11
66.50 + 4.15
8w 6w.23"
86.32 1: 4.21
66.60 1 3.93
E.3 Evaluating graph distances in graph classification task
Our main theoretical results and empirical validation focus on the relationship between MPNNs and their induced graph distances, suggesting that the Euclidean distance between MPNN embeddings an efficient lower bound of these graph distances. More precisely, the time complexity of computing ôp, ōw.n. is O(h n log 12) (the same order as the WL distance in [26]). In contrast, the time complexity of computing fi-layer, d-dimensional MPNN embedding distance (with the, & chosen as the composition of linear maps and pointwise nonlincarities) is Oh n [E) + n d), which is massively cheaper, especially for large, sparse graphs that are ubiquitous in real- applications.
For ablation purposes, we evaluate our graph distances 6p As 8w, in graph classification tasks to examine how well they can separate graphs. For comparison, we follow the same set-up from Chen et al. [26]. Specifically, for each selected graph dataset in the TUDataset [90], we compute the pairwise distances for all graphs in the dataset. We then perform graph classification via 1-nearest-neighbor classifier (I-NN), which classifies the test graph based on the label of the closest training graph (measured by our graph distance). We use 90/10 training/test random split and repeat ten times, following the same random data split in [26].
Table 6 shows the mean classification accuracy of 1-NN using our graph distances and demonstrates that our graph distances achieve competitive classification performance as the WL distance in [26].
'ów computed up at most three iterations after color stabilizes.
43


Reviews:
[{"review_id": "3sP3XmdfZd", "reviewer": "Reviewer_yRbN", "summary": "The authors propose a novel way to generalize the expressivity of graph neural networks (and other general message passing algorithms) to the graphon case.\nFurthermore, they identify metrics on graphons (and, consequently graphs) which allow to bound the distance of any MPNN representation of the graphons.\n", "questions": "I wonder if you can give some insights regarding the issue mentioned above?\n\nAlso, it is not clear to me how the discussion of Q2 in the experiments is connected to the theory in the previous sections. I might have missed the connection, but to me it is unintuitive why the Lipschitz-arguments should imply that larger $L$ should result in more similar outputs. \n\nMinor Issues:\nl 299: 'in an MPNNs'\np7 and p8 mention in relatively close distance two 'elegant' proofs. That struck me as a bit odd.\n", "limitations": "The authors discuss technical limitations such as the current restriction to discretely labeled graphs and 1-WL. \nI don't see immediate negative societal impact of this work. \n", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper provides an important step towards a more realistic analysis of MPNN expressivity.\nThis paper goes beyond both common approaches to measure expressivity of MPNNs, presenting an epsilon delta result for two metrics on graph(on)s and MPNNs with Lipschitz constant and fixed number of layers.\nThis properly generalizes the discrete setting and has potentially high impact sparking further research.\n", "weaknesses": "It seems to me that the definition of GNNs in Line 212 1/2 is a rather severe deviation from most MPNN formulations, as it requires activations to grow linearly with the graph size to offset the normalization $\\frac{1}{|V(G)|}$. This seems to be generally only possible for dense graphs when e.g. a fixed set of (one hot encoded) categorical labels is present. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their fair and constructive review.\n\n> It seems to me that the definition of GNNs in Line 212 1/2 is a rather severe deviation from most MPNN formulations, as it requires activations to grow linearly with the graph size to offset the normalization. This seems to be generally only possible for dense graphs when e.g. a fixed set of (one hot encoded) categorical labels is present.\n\n> I wonder if you can give some insights regarding the issue mentioned above?\n\nThe experiments show that normalized sum aggregation performs comparably to sum aggregation, and better than average aggregation. We have included the average aggregation experiments in the new Table 5 in the global response PDF:\n* Table 1 (main text) studies MPNNs with sum aggregation and $1/|V(G)|$ normalization, corresponding to our theory\n* Table 4 (appendix) studies MPNNs with sum aggregation without $1/|V(G)|$ normalization\n* new Table 5 (global response PDF) studies MPNNs with mean aggregation without $1/|V(G)|$ normalization\n\nAll of above use the same MPNN backbone ($3$-layer, $512$-hidden-size) and experimental setup\n\nHowever, if you have a dataset of graphs with sizes that range from very small to very large, and the large graphs are sparse, then normalized sum aggregation is not appropriate. Luckily, most datasets consist of graphs of sizes that do not vary too much. Normalized sum aggregation is appropriate for such datasets, even if the graphs are sparse, as the normalization can be compensated by larger weights. We will add a comment about this in the camera ready version, and include experiments with average aggregation for comparison.\n\nOn the theory side, the normalization by the number of vertices stems from viewing graphs as graphons. Requiring activations to grow linearly with the graph size makes sense in this context. For a very large graph, a small individual part of the graph does not play a significant role. More generally, if the size of our graphs grows towards infinity, then the importance of a set of fixed size goes towards zero. The activations have to grow with the graph size to identify these differences between graphs still. Hence, the Lipschitz constant we defined for an MPNN model has to grow to identify these differences. This is also what our theoretical result states: to guarantee $\\varepsilon$-similarity of graph(on)s in our distances, we need similarity of MPNN models up to some Lipschitz constant $C$, where $C$ goes towards infinity as $\\varepsilon$ goes to zero.\nMoreover, when taking an activation function from our setting to the usual, non-normalized setting, the normalization would have to become part of the function (to yield the same output), which would offset the linear growth.\n\n> Also, it is not clear to me how the discussion of Q2 in the experiments is connected to the theory in the previous sections. I might have missed the connection, but to me it is unintuitive why the Lipschitz-arguments should imply that larger $L$ should result in more similar outputs. \n\nIntuitively, you should equate the depth $L$ with the number of steps in 1-WL. With more layers you can separate graphs that can only be separated with more steps of 1-WL. Hence, larger $L$ can separate more graphs.\nOur theory states: two graphs are close in our graph distance if and only if all $L$-layer $C$-Lipschitz MPNN embeddings are close. We want to apply it for the context of graph classification (Q2), which translates to: two graphs are in the same class if and only if all MPNN embeddings are close—this includes both trained and untrained embeddings. This thus motivates us to examine the effectiveness of untrained MPNN embeddings.  Moreover, in practice, we cannot compute **all** MPNN embeddings, so we seek to test how well using a subset of them as an approximation (to graph distance) for graph classification. Our experiments demonstrate that using a subset of untrained MPNN embeddings does achieve competitive performance, illustrating the utility of our theoretical results.\n"}, {"review_id": "p4ROIwMKoC", "reviewer": "Reviewer_Svzd", "summary": "The paper studies the classes of MPNNs on graphons, ultimately showing that the MPNN representations are sufficiently close (up to constants depending on Lipschitz regularity and layers) _if and only if_ the graphons are close according to several metric distances, mainly the Prokhorov metric and the unbalanced Wasserstein metric.", "questions": "- As far as I understand, extending these type of results to GNNs that do not follow the 1-WL paradigm of summing over the neighbours is possibly non-trivial right? I think that it would be interesting in general to see how quantitative $\\delta$-bounds depend on different paradigms for using the graph information (from structural encoding, to Graph-Transformers).\n\n- I find that restricting to the feature-less case is a little detrimental to the overall message and I wonder in fact how challenging is extending this formalism to graphons with signals? I am not expecting a revision but am curious to hear comments here to gauge if this direction is actually pursuable or not.\n\n- In the experiments you claim that your results support Corollary 4? What is Corollary 4 and where in the manuscript you have mentioned the role of the hidden dimension? Besides, is it in general really surprising that MPNNs with more hidden dimension may be better at separating graphs?\n\nI think the paper has technical merits despite some mild concerns on the overall impact to the broader GNN community, and the score reflects this. The results are, on a qualitative level, intuitive, while on a quantitative level it is hard to extract some insight. The experimental section needs some revision as per my previous comments ---evaluating over a more structural-oriented task such as ZINC is perhaps a plus but not a must. \n\nDisclaimer: I have not checked the mathematical proofs in the appendix.", "limitations": "Yes, limitations have been discussed and no societal impact can be foreseen.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper addresses a direction of research which is quite relevant, namely studying the response of GNNs and their dependence on properties of the input. In fact, the widely studied and adopted WL test is often a blunt yardstick for measuring the sensitivity of GNNs and investigating their dependence on metric functions defined on the space of graphs is worth looking into.\n- The exposition of the paper and overview of the related works is well executed. The setup is clear.\n- On a mathematical level, the works extends the results of [26] in several non-trivial ways and expands the efforts to understand GNNs through graphons in meaningful directions.", "weaknesses": "- The fact that MPNNs exhibit a Lipschitz property compared to distances on graphons does not seem surprising to me (i.e. Lemma 3) given their regularity. The converse statement (Theorem 6) is perhaps less obvious, although I fail to see how can this be used in practice? In fact, it is not the qualitative $\\epsilon-\\delta$ statements that are that interesting in my opinion, but rather the quantitative bounds which seem though to be lacking any significant insight? For example in Lemma 3 the constant depends on the fact that the features \"have to\" be bounded on a compact metric space, which is ultimately not enlightening. More generally, it would be interesting not to prove some Lipschitz property of MPNNs, but perhaps how some more transparent properties of the graph structure translate _quantitatively_ into the Lipschitz bounds.\n- The analysis focuses on the case where graph(ons) are taken without features, which can be limiting although this setup is often conventional in the literature on expressivity of GNNs.\n- There is an impractical cost for computing the distances which should be explicitly reported in the main text -- as it stands, mentioning the polynomial running time in Theorem 2 is a little too vague. While this is probably minor compared to the other points, it also contributes to reducing the impact of the submission. \n- The experimental part is a little confusing. First, experiments on untrained MPNNs should be much better motivated, as it stands one can mainly guess what are you are trying to accomplish here. Second, validating that MPNNs can separate better with increased hidden dimension, is not surprising; besides, where is the role of the hidden dimension been discussed before? The fact that you can be competitive on some TUdataset \"without\" training over the layers is again not that surprising. These datasets are quite sensitive to hyperparameter tuning and I suspect that even removing the weights from the layer altogether and only train for the encoder and or decoder would be quite competitive. Maybe using different datasets -- more structural ones -- such as ZINC could be a little more indicative for a comparison. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their fair and constructive review.\n\n> The fact that MPNNs exhibit a Lipschitz property compared to distances on graphons does not seem surprising to me (i.e. Lemma 3) given their regularity. The converse statement (Theorem 6) is perhaps less obvious, although I fail to see how can this be used in practice? [...]\n\nGood point. Proving a quantitative version of Theorem 6 is, in fact highly non-trivial, cf. the very involved proof of the \"Inverse Counting Lemma\" in the book of Lovász [78]. We mainly view our work as a theoretical contribution establishing the first step of defining the appropriate notions. Lemma 3 and Theorem 6 show that our definitions are applicable in this sense. Then, proving quantitate bounds is the logical next step in this line of work. Additionally, we think that stating that the constant in Lemma 3 depends on the fact that the features \"have to\" be bounded on a compact metric space undermines the actual statement of Lemma 3: this is rather a technical detail that stems from the fact that graphons are normalized, but our MPNN functions are not. The vital part of the constants are the Lipschitz constants of the individual functions.\n\n> The analysis focuses on the case where graph(ons) are taken without features, which can be limiting although this setup is often conventional in the literature on expressivity of GNNs.\n\n> I find that restricting to the feature-less case is a little detrimental to the overall message and I wonder in fact how challenging is extending this formalism to graphons with signals? [...]\n\nThat is an interesting question that fell victim to the page limit. In the camera-ready version, we will clarify better that the analysis is restricted to graphons without signals and add a remark on how this can be extended to graphons with signals.\n\nHere is what one has to adapt: Fix some compact metric space $K$ and consider graphons $W$ with a measurable signal function $\\\\ell \\\\colon [0,1] \\\\to K$. Replace the one-point space $\\mathbb{M}_0$ by $K$ and adapt the definition of IDMs to include the old color in the new color (see the original definition of Grebík and Rocha [52]; including the old color in the new color becomes necessary also for 1-WL when the initial coloring is not constant since, otherwise, the second coloring would not include the initial coloring and so on).\n\nThen, the IDM spaces $\\\\mathbb{M}_{h}$ are still compact metrizable.\n\nModify the 1-WL for graphons by setting $\\\\mathsf{i}_{(W,\\\\ell),0} \\coloneqq \\\\ell$. In an MPNN model, $\\\\varphi_0$ is now a Lipschitz function $K \\\\to \\\\mathbb{R}^{d_0}$. Then, the universality result still holds since Lipschitz functions on $K$ are dense in $C(K)$. Finally, adapt the metrics by using the metric of the compact metric space $K$.\n\nSince the definitions of IDMs and our distances become more complicated and less intuitive, we did not directly include this in the main body. Moreover, homomorphisms and the tree distance do not have meaningful definitions for graphs with signals (as far as we are aware). Hence, we stated our main result for graphons without signals.\n\n> There is an impractical cost for computing the distances which should be explicitly reported in the main text -- as it stands, mentioning the polynomial running time in Theorem 2 is a little too vague. [...]\n\nGood point; we will make sure to point out the upper bounds, which we derived in the appendix, in the main body of the camera-ready version ($\\mathcal{O}(h \\cdot n^5 \\cdot \\log n) \\text{ for } \\delta_{\\mathsf{W},h},\\, \\mathcal{O}(h \\cdot n^7) \\text{ for } \\delta_{\\mathsf{P},h}$). Moreover, we will stress that we do not propose computing the metrics in practice as a computational tool. The paper aims to hint that MPNNs can replace these metrics. The metrics are meaningful but hard to compute. On the other hand, MPNNs are mainly seen as black-box models but are easy to compute. The paper shows that *practical* MPNNs have the separation power of the *theoretical* metrics.\n\n> The experimental part is a little confusing. [...]\n\nWe will clarify better in the camera-ready version the motivation behind the experiments. The theory says that we must run over all possible MPNNs, and take the largest distance in the output space. In our experiments, we instead run over a finite set of random MPNNs. We did not provide any “Monte Carlo” theory that relates the full MPNN space to the finite sample, and the theory in previous sections should be seen as heuristically motivating the experiments, not rigorously justifying them. We will clarify this in the camera-ready version.\n\n> As far as I understand, extending these type of results to GNNs that do not follow the 1-WL paradigm of summing over the neighbours is possibly non-trivial right? [...]\n\nThese are interesting directions that we aim at exploring in future work. Currently, the 1-WL paradigm of summing over the neighbors is crucial in our proofs.\n\n> In the experiments you claim that your results support Corollary 4? What is Corollary 4 and where in the manuscript you have mentioned the role of the hidden dimension? Besides, is it in general really surprising that MPNNs with more hidden dimension may be better at separating graphs?\n\nWe apologize for the typo and clarify that “Corollary 4” refers to Corollary 5, which states that two graph(on)s are close in our distance if and only if all their MPNN embeddings (of $L$-layer, $\\psi$-Lipschitz) are close in the Euclidean metric. The wording “all” can be interpreted as using infinitely-many MPNNs, or collecting them into one MPNN with infinite hidden dimension size. In the experiment (Q2), we investigate the performance of increasing hidden size and observe that the performance of untrained MPNNs increases with hidden size, supporting our theory. "}, {"review_id": "edDJQUgpYs", "reviewer": "Reviewer_oM2o", "summary": "The paper considers the continuous variant of the 1-WL test and leverages it to characterize the expressive power of MPNNs on graphons.\n\nThe authors show that if two graphons have similar MPNN outputs then they are close in their metric, extending the existing result proving the opposite implication (graphons similar in their metric have similar MPNN outputs).\nThey establish a connection between the continuous variant of the 1-WL test and MPNNs to tree distance and tree homomorphism densities, where equivalences were only known to hold on a discrete level. Empirically, they show that untrained MPNNs (paired with a trained final classifier) obtain competitive performances on graph-level tasks. Finally, they experimentally compare different models in their ability to preserve graph distances.", "questions": "1. Can you discuss the implications of this work? While I understand that the theoretical claims hold, what can we do knowing that they hold? \n2. Similarly to the above question, what is the take-home message of the experimental evaluation? I am unsure of the relevance of the questions you set to answer.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper refines existing results on metrics and MPNNs outputs.\n2. The paper aims at closing the gap between results that were known to hold on a discrete level (where graphs are exactly isomorphic), but that were under explored at the continuous level.", "weaknesses": "1. The paper is hard to read, as it introduces a lot of existing concepts and builds on them. Maybe it is inevitable due to intrinsic theoretical nature of the paper. However, I believe some extra effort is needed to remind the reader that a concept or theorem that is going to be introduced is, in simpler words, what has been presented in the introduction as a contribution.\n2. I am unsure of the implications of this work. The theory is beautiful, but I am left unsure of what we can do with this gained knowledge. I don't see how this can help experimentally, or in real world cases. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their fair and constructive review.\n\n> The paper is hard to read, as it introduces a lot of existing concepts and builds on them. Maybe it is inevitable due to intrinsic theoretical nature of the paper. However, I believe some extra effort is needed to remind the reader that a concept or theorem that is going to be introduced is, in simpler words, what has been presented in the introduction as a contribution.\n\nThank you, we agree, we will use the additional page for the camera ready, to add some intuitions and make it more accessible to the wider GNN community.\n\n1. We will define and discuss tree distance in the main paper instead of the appendix.\n2. In *Message-passing graph neural networks* we will add a more extensive discussion about the relation between the formulation of MPNNs on IDMs and standard MPNNs on graphons/graphs. We agree that seeing the connection between the two formulation is critical for the understanding of our paper.\n3. We will extend some of the formulas, opting for clearer longer explicit formulas rather than shorter implicit ones. For example, the formulas in line 253 can be replaced by explicit formulations.\n\nWe kindly ask you to provide additional suggestions on specific parts that were hard to understand and should be improved.\n\n> I am unsure of the implications of this work. The theory is beautiful, but I am left unsure of what we can do with this gained knowledge. I don't see how this can help experimentally, or in real world cases.\n\n> Can you discuss the implications of this work? While I understand that the theoretical claims hold, what can we do knowing that they hold? \n\nWe mainly view our work as a theoretical contribution, leading to a better understanding of what kind of functions GNNs express, potentially leading to a better understanding of their predictive performance. We think that our work is a necessary first step of defining the desired notion of graph similarity for GNNs, which then enables future work that is focused on better understanding these notions and the expressivity of GNNs.\nOne main practical implication that the theory hints at is that we can use untrained MPNNs to solve various graph machine learning problems. In the camera-ready version, we will add a section discussing this.\n\n> Similarly to the above question, what is the take-home message of the experimental evaluation? I am unsure of the relevance of the questions you set to answer.\n\nOur experimental evaluation intends to show (Q1) how MPNN embedding Euclidean distance correlates with our proposed graph metrics, which illustrates Corollary 5; (Q2) how useful are untrained MPNN embedding to discriminate graphs, since our main results state that two graphs are close in our graph metrics if and only if all $L$-layer $C$-Lipschitz MPNN embeddings are close, which includes both trained and untrained MPNNs. Our experiments demonstrate that using a subset of untrained MPNN embeddings does achieve competitive performance, illustrating the utility of our theoretical results.\n\nAn important implication for practitioners is to use MPNN embedding (distance) as an efficient lower bound to compute distances of large graphs. More precisely, the time complexity of computing $\\delta_{\\mathsf{W}, h}$ is $\\mathcal{O}(h \\cdot n^5 \\cdot \\log n)$ (the same order as the WL distance in [26], even worse for $\\delta_{\\mathsf{P}, h}$). In contrast, the time complexity of computing $h$-layer, $d$-dimensional MPNN embedding distance (with $\\varphi_t$, $\\psi$ chosen as the composition of linear maps and pointwise nonlinearities) is $\\mathcal{O}(h · n · |E(G)| + n · d)$, which is massively cheaper, especially for large, sparse graphs that are ubiquitous in real-world applications."}, {"review_id": "JcmROm0hPa", "reviewer": "Reviewer_xsds", "summary": "This work aims at a fine-gined metric to characterize representation differences from MPNNs. Specifically, they first generalize MPNN to iterative degree measures and prove that Prokhorov metric and unbalanced Wasserstein metric can be used to bound the node/graph representation difference. This relation is validated in their experiments on random graphs. ", "questions": "- Could you provide an intuitive explanation for Theorem 4, the universal theorem? Does it essentially mean that MPNNs have the same separation power as 1-WL on graphons?\n", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": " - [significance] This work builds a connection between the GNN representations and the graph similarity,  and makes a solid theoretical contribution to understand GNN expressivity. \n - Empirical results well support the theory.", "weaknesses": "- The motivation and the conclusion of untrained GNNs experiments are not very clear to me. How is \"an untrained GNN can outperform trained GNN\" related to the previous conclusions and what message does this part try to convey?\n- Besides, TUDataset could be too small to faithfully evaluate the performance. Results on other datasets such as ZINC or OGB may further improve the evaluation. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their fair and constructive review.\n\n> The motivation and the conclusion of untrained GNNs experiments are not very clear to me. How is \"an untrained GNN can outperform trained GNN\" related to the previous conclusions and what message does this part try to convey?\n\nOur theory states: two graphs are close in our graph distance if and only if all L-layer C-Lipschitz MPNN embeddings are close. We want to apply it for the context of graph classification (Q2), which translates to: two graphs are in the same class if and only if all MPNN embeddings are close --- this includes both trained and untrained embeddings. This thus motivates us to examine the effectiveness of untrained MPNN embeddings.  Moreover, in practice, we cannot compute *all* MPNN embeddings, so we seek to test how well using a subset of them as an approximation (to graph distance) for graph classification. Our experiments demonstrate that using a subset of untrained MPNN embeddings does achieve competitive performance, illustrating the utility of our theoretical results.\n\nWe will clarify better in the camera ready version the motivation behind the experiments. The theory says that we need to run over all possible MPNNs, and take the largest distance in the output space. In our experiments, we instead run over a finite set of random MPNNs. We indeed did not provide any “Monte Carlo” theory that relates the full MPNN space to the finite sample, and the theory in previous sections should be seen as heuristically motivating the experiments, not rigorously justifying them. We will clarify this in the camera ready version.\n\n> Besides, TUDataset could be too small to faithfully evaluate the performance. Results on other datasets such as ZINC or OGB may further improve the evaluation.\n\nGood point, we will try to add them in the camera ready.\n\n> Could you provide an intuitive explanation for Theorem 4, the universal theorem? Does it essentially mean that MPNNs have the same separation power as 1-WL on graphons?\n\nIntuitively, it says that every continuous function on graphons that is invariant under 1-WL colors can be approximated by an MPNN. This is in some sense a “continuous” or “metric” (and hence stronger) variant of the statement that MPNNs and 1-WL have the same separation power on graphons. "}, {"review_id": "ucPGPlQ2X3", "reviewer": "Reviewer_7umZ", "summary": "With graphon theory, this work quantifies which distance MPNNs induce and thus provides a deeper understanding of MPNNs’ capacity to capture graph structure, precisely determining when they can and when they cannot assign similar and dissimilar vectorial representations to graphs.", "questions": "Can you generalize the theory to max and mean aggregation?", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Strong universality results on graphon.\n2. The iterated degree measure is intuitive and insightful.", "weaknesses": "1. Graphon focus on graph limit. While in real world settings like graph classfication, the graph is small and MPNN still lacks expressivity.\n\n2. Only the sum aggregation is analyzed. While in application, max and mean aggregation are also important.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their fair and constructive review.\n\n> Graphon focus on graph limit. While in real world settings like graph classfication, the graph is small and MPNN still lacks expressivity.\n\nYou are correct that graphons are used in the GNN literature via large graphs. These works use graphons to formulate a generative model of the data. That is, graphs in the dataset are seen as sampled from some (usually small) set of graphons. In that approach, you need large graphs for the asymptotics to work. However, our work does not fall under this category, and does not define any generative model of graphs. In general, graphons are not limits of only large graphs. Any graph is a graphon, so graphons are also “limits” of small graphs. The space of graphs is a dense subset of the space of all graphons. The reason to consider graphon analysis is that we want to work with a compact metric space for results like the Stone–Weierstrass theorem to work. The space of graphons is the completion of the space of graphs to a compact metric space. To conclude, any probability distribution of graphs, including distributions restricted to small graphs, is a valid probability distribution of graphons. In the camera-ready version of the paper, we will clarify this point and the different philosophical approach from other GNN papers that use graphon analysis.\n\n> Only the sum aggregation is analyzed. While in application, max and mean aggregation are also important.\n\n> Can you generalize the theory to max and mean aggregation?\n\nGood question. Currently, the 1-WL paradigm of summing over the neighbors is crucial in our proofs, and extending our theory to max/mean aggregation functions is not straightforward. We are aiming to explore this in future work."}]

Author rebuttal:
We thank the reviewers for their fair and constructive reviews and appreciate that they recognize that we present a beautiful theory for graph similarity. Combined with a novel generalization of message-passing graph neural networks (MPNNs) to graphons, our theory allows us to prove that graph(on)s are close in a continuous variant of the 1-WL if and only if their MPNN outputs are close, an equivalence that was only known to hold in the discrete case (where graphs are either distinguished or not).

We mainly view our work as a theoretical contribution, leading to a better understanding of what kind of functions MPNNs express, potentially leading to a better understanding of their predictive performance. We further think that our work is a necessary first step of defining the desired notion of graph similarity for MPNNs, which then enables future work that is focused on better understanding these notions and the expressivity of MPNNs.

To illustrate our theory, we empirically investigate the relationship between MPNN embedding Euclidean distances and our proposed graph distances. Our experiments show that untrained MPNNs can be surprisingly effective, as our theory predicts, as long as we use **many** of them. Ideally, we would use **all** to preserve the graph distance (as our theoretical result states), but this is not possible of course. Our experiment shows that using enough of them (measured by the hidden size) suffices for downstream classification. Moreover, one can view MPNN embedding distances as an efficient lower bound for our graph distances since the time complexity of computing $h$-layer, $d$-dimensional MPNN embedding distances is massively cheaper than the time complexity of computing our distances $\delta_{\mathsf{W},h}$ and $\delta_{\mathsf{P},h}$, which is still polynomial but with an impractical exponent.

Meta-review: The reviewers unanimously recommended to accept the paper.
Decision: Accept (poster)