Fine-grained Expressivity of Graph Neural Networks
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.
Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, Christopher Morris
# Fine-grained Expressivity of Graph Neural Networks

###### 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 concepts 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.

## 1 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, _message-passing 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-Leman test_ (\(1\)-WL) for the graph isomorphism problem [113, 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 Grebik 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 topology in which MPNNs separate points, allowing us to prove a universal approximation theorem for graphons. Inspired by the Weisfeiler-Leman distance [26], we show that metrics on measures also integrate beautifully into the theory of iterated degree measures. Concretely, we define metrics \(\delta_{\mathsf{P}}\) via the _Prokhorov metric_[99] and \(\delta_{\mathsf{W}}\) 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\)-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 \(\delta_{\mathsf{P}}\) and \(\delta_{\mathsf{W}}\) on iterated degree measures, the tree distance \(\delta_{\Box}^{\mathcal{T}}\) of Boker [18], the Euclidean 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 1** (informal).: The following are equivalent for all graphons \(U\) and \(W\):

1. \(U\) and \(W\) are close in \(\delta_{\mathsf{P}}\) (or alternatively \(\delta_{\mathsf{W}}\)).
2. \(U\) and \(W\) are close in \(\delta_{\Box}^{\mathcal{T}}\).
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 Boker [18], these equivalences were only known to hold on a 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 \(\varepsilon>0\), there is a \(\delta>0\) such that, if graphons are \(\delta\)-close in one distance measure, they are \(\varepsilon\)-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 1 is formally stated and proved in Appendix C.4. A key point in 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 our derived metrics for studying different MPNN architectures. Our theoretical and empirical results also provide an efficient lower bound of the graph distances in Boker [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-grained understanding of their expressivity and separation capabilities. Our results provide 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. _Our work establishes the first rigorous connection between the similarity of graphs and their learned vectorial presentations, paving the way for a more detailed understanding of MPNNs' expressivity and their connection to graph structure._

### 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., a \(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 a given graph by aggregating these vectorial vertex representations. Notable instances of this architecture include, e.g., Duvenaud et al. [36], Hamilton et al. [61], and Velickovic et al. [111], which can be subsumed under the message-passing 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]--all of which descend from early work in Baskin et al. [14], Goller and Kuchler [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 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-isomorphic graphs as the \(1\)-\(\mathsf{WL}\) or its more powerful generalization the \(k\)-\(\mathsf{WL}\). Here, an MPNN distinguishes two non-isomorphic graphs if it can compute different vectorial representations for the two graphs. Specifically, Morris et al. [89] and Xu et al. [115] showed that the \(1\)-\(\mathsf{WL}\) limits the expressive power of any possible MPNN architecture in distinguishing non-isomorphic graphs. In turn, these results have been generalized to the \(k\)-\(\mathsf{WL}\), 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 an 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 can 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 a natural notion of similarity for practical machine learning on graphs. That is, any two graphs on a different number of vertices are far

Figure 1: Illustration of the procedure to compute the distance \(\delta_{\mathsf{P}}\) between graphs \(G\) and \(H\). Columns A and C show the colors obtained by \(1\)-\(\mathsf{WL}\) iterations on graphs \(G\) and \(H\), respectively. Columns B and D show the iterated degree measures (IDMs) \(\mathsf{i}_{G,h}\) and \(\mathsf{i}_{H,h}\) for iterations \(h=1,2\) (see Equation (1)), and the output distributions of iterated degree measures (DIDMs) \(\nu_{G}\) and \(\nu_{H}\) (see Eq. (2)). Column E depicts the recursive construction to compute the distance \(\delta_{\mathsf{P}}\) between the IDMs from columns B and D (outlined in Section 3, detailed in Appendix C.2.2).
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 a far-away graph. However, we would like to interpret the rewiring of a small number of edges in a large graph as a 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 Stone-Weierstrass theorem directly; see also Appendix B.2 for an extended discussion on graph metrics beyond the edit distance.

Graphon theory.The book of Lovasz [78] provides a 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], Lovasz and Szegedy [77]. These limit objects allow the completion of the space of all graphs to a compact metric space. When endowed with the _cut distance_, first introduced by Frieze and Kannan [41], the space of graphons is compact [78, Theorem 9.23]). We can interpret graphons in two ways. First, as a weighted graph on the continuous vertex set \([0,1]\). Secondly, we can think of every point from \([0,1]\) as an infinite set of vertices and two points \([0,1]\) as 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. Grebik and Rocha [52] generalized the \(1\)-WL test and various of its characterizations to graphons, while Boker [19] did this for the \(k\)-WL 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 a single fixed graphon generating the data, i.e., any graph from the dataset is randomly sampled from this graphon, and showed that spectral MPNNs on 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 \(L_{\infty}\) distance between graphons as functions. However, the paper does not directly characterize the separation power of the studied classes of MPNNs, and it requires the choice of an arbitrary compact subset to perform the analysis. In contrast, in the current paper, we use 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 \(\lambda\) and consider measurability w.r.t. the Borel \(\sigma\)-algebra on \([0,1]\). Let \((X,\mathcal{B})\) be a standard Borel space, where we sometimes just write \(X\) when \(\mathcal{B}\) is understood and then use \(\mathcal{B}(X)\) to explicitly denote \(\mathcal{B}\). For a measure \(\mu\) on \(X\), we let \(\|\mu\|\coloneqq\mu(X)\) denote its _total mass_, and for a standard Borel space \((Y,\mathcal{C})\) and a measurable map \(f\colon X\to Y\), let the _push-forward \(f_{*}\mu\) of \(\mu\) via \(f\)_ be defined by \(f_{*}\mu(A)\coloneqq\mu(f^{-1}(A))\) for every \(A\in\mathcal{C}\). Let \(\mathscr{P}(X)\) and \(\mathscr{M}_{\leq 1}(X)\) denote the spaces of all probability measures on \(X\) and all measures of total mass at most one on \(X\), respectively. Let \(C_{b}(X)\) denote the set of all bounded continuous real-valued functions on \(X\). We endow \(\mathscr{P}(X)\) and \(\mathscr{M}_{\leq 1}(X)\) with the topology generated by the maps \(\mu\mapsto\int_{X}fd\mu\) for \(f\in C_{b}(X)\), the _weak topology_ (_weak* topology_ in functional analysis); see [63, Section 17.E] or [17, Chapter 8]. Then, \(\mathscr{P}(X)\) and \(\mathscr{M}_{\leq 1}(X)\) are again standard Borel spaces, and if \(K\) is a compact metric space, then \(\mathscr{P}(K)\) and \(\mathscr{M}_{\leq 1}(K)\) are compact metrizable; see [63, Theorem 17.22]. For a sequence \((\mu_{i})_{i}\) of measures and a measure \(\mu\), we have \(\mu_{i}\to\mu\) if and only if \(\int_{X}fd\mu_{i}\to\int_{X}fd\mu\) for every \(f\in C_{b}(X)\), and for measures \(\mu,\nu\), we have \(\mu=\nu\) if and only if \(\int_{X}fd\mu=\int_{X}fd\nu\) for every \(f\in C_{b}(X)\). In both statements, we may replace \(C_{b}(X)\) by a dense (w.r.t. the sup norm) subset. See Appendix A.3 for basics on topology.

Graphs and graphons.A _graph_\(G\) is a pair \((V(G),E(G))\) with _finite_ sets of _vertices_ or _nodes_\(V(G)\) and _edges_\(E(G)\subseteq\{\{u,v\}\subseteq V(G)\mid u\neq v\}\). If not otherwise stated, we set \(n\coloneqq|V(G)|\), and the graph is of _order_\(n\). We also call the graph \(G\) an \(n\)-order graph. For ease of notation, we denote the edge \(\{u,v\}\) in \(E(G)\) by \(uv\) or \(vu\). The _neighborhood_ of \(v\) in \(V(G)\) is denoted by \(N(v)\coloneqq\{u\in V(G)\mid vu\in E(G)\}\) and the _degree_ of a vertex \(v\) is \(|N(v)|\). Two graphs \(G\) and \(H\) are _isomorphic_ and we write \(G\simeq H\) if there exists a bijection \(\varphi\colon V(G)\to V(H)\) preserving the adjacency relation, i.e., \(uv\) is in \(E(G)\) if and only if \(\varphi(u)\varphi(v)\) is in \(E(H)\). Then \(\varphi\) is an _isomorphism_ between \(G\) and \(H\).

A _kernel_ is a measurable function \(U\colon[0,1]^{2}\to\mathbb{R}\), and a symmetric measurable function \(W\colon[0,1]^{2}\to[0,1]\) is called a _graphon_. The set of all graphons is denoted by \(\mathcal{W}\). Graphons generalize graphs in the following way. Every graph \(G\) can be viewed as a graphon \(W_{G}\) by partitioning \([0,1]\) into \(n\) intervals \((I_{v})_{v\in V(G)}\), each of mass \(1/n\), and letting \(W_{G}(x,y)\) for \(x\in I_{u},y\in I_{v}\) be one or zero depending on whether \(uv\) is an edge in \(G\) or not. The _homomorphism density_\(t(F,W)\) of a graph \(F\) in a graphon \(W\) is \(t(F,W)\coloneqq\int_{[0,1]^{V(F)}}\prod_{ij\in E(F)}W(x_{i},x_{j})\,d(\bar{x})\), where \(\bar{x}\) is the tuple of variables \(x_{v}\) for \(v\in V(G)\).
Iterated measures.Here, we define _iterated degree measures (IDMs)_, which is basically a sequence of measures, by adapting the definition of Grebik and Rocha [52]. Let \(\mathbb{M}_{0}\coloneqq\{1\}\) and inductively define \(\mathbb{M}_{h+1}\coloneqq\mathscr{M}_{\leq 1}(\mathbb{M}_{h})\) for every \(h\geq 0\). Then, the spaces \(\mathbb{M}_{0},\mathbb{M}_{1},\dots\) are all compact metrizable.

For \(0\leq h<\infty\), inductively define the _projection_\(p_{h+1,h}\colon\mathbb{M}_{h+1}\to\mathbb{M}_{h}\) by letting \(p_{1,0}\) be the trivial map and, for \(h>0\), letting \(p_{h+1,h}(\alpha)\coloneqq(p_{h,h-1})_{*}\alpha\) for every \(\alpha\in\mathbb{M}_{h+1}=\mathscr{M}_{\leq 1}(\mathbb{M}_{h})\). This extends to \(p_{h,\ell}\colon\mathbb{M}_{h}\to\mathbb{M}_{\ell}\) for \(0\leq\ell\leq h<\infty\) by composition in the intuitive way. Let

\[\mathbb{M}\coloneqq\mathbb{M}_{\infty}\coloneqq\{(\alpha_{h})_{h}\in\prod_{h \in\mathbb{N}}\mathbb{M}_{h}\mid p_{h+1,h}(\alpha_{h+1})=\alpha_{h}\text{ for every }h\in\mathbb{N}\}\]

be the _inverse limit_ of \(\mathbb{M}_{0},\mathbb{M}_{1},\dots\); see the Kolmogorov Consistency Theorem [63, Theorem 17.20]). Then, \(\mathbb{M}\) is compact metrizable [52, Claim 6.2]. For \(0\leq h<\infty\), let \(p_{\infty,h}\colon\mathbb{M}\to\mathbb{M}_{h}\) denote the projection to the \(h\)-th component. We remark that we slightly simplified the definition of Grebik and Rocha [52] by not including previous IDMs from \(\mathbb{M}_{h^{\prime}}\) for \(h^{\prime}\leq h\) in \(\mathbb{M}_{h+1}\) and directly defining \(\mathbb{M}\) as the inverse limit; corresponding to the definition of the space \(\mathbb{P}\) in [52]. These changes yield equivalent definitions that simplify the exposition.

The \(1\)-WL for graphons.See Appendix A.1 for the standard definition of \(1\)-WL on graphs. Grebik and Rocha [52] generalized \(1\)-WL to graphons by defining a map \(\mathrm{i}_{W}\colon[0,1]\ \to\mathbb{M}\), mapping every point of the graphon \(W\in\mathcal{W}\) to an iterated degree measure as follows. First, inductively define the map \(\mathrm{i}_{W,h}\colon[0,1]\to\mathbb{M}_{h}\) by setting \(\mathrm{i}_{W,0}(x)\coloneqq 1\) for every \(x\in[0,1]\) and

\[\mathrm{i}_{W,h+1}(x)\coloneqq A\mapsto\int_{\mathrm{i}_{W,h}^{-1}(A)}W(x,y)d \mu(y), \tag{1}\]

for all \(x,y\in[0,1],A\in\mathcal{B}(\mathbb{M}_{h})\), and \(h\geq 0\). Intuitively, \(\mathrm{i}_{W,h}(x)\) is the color assigned to point \(x\) after \(h\) iterations of \(1\)-WL. Observe that \(\mathrm{i}_{W,1}(x)\) encodes the degree of point \(x\), and \(\mathrm{i}_{W,h}(x)\) for \(h>1\) represents the iterated degree sequence information. Then, we define \(\mathrm{i}_{W}\coloneqq\mathrm{i}_{W,\infty}\colon[0,1]\to\mathbb{M}\) by \(\mathrm{i}_{W}(x)\coloneqq\mathrm{i}_{W,\infty}(x)\coloneqq\prod_{h\in\mathbb{ N}}\mathrm{i}_{W,h}(x)\) and let

\[\nu_{W}\coloneqq\nu_{W,\infty}\coloneqq(\mathrm{i}_{W})_{*}\lambda\in \mathscr{P}(\mathbb{M}) \tag{2}\]

be the _distribution of iterated degree measures (DIDM) of \(W\)_. In other words, \(\nu_{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 a graphon \(W\in\mathcal{W}\) and returns \(\nu_{W}\). In addition to \(\nu_{W}\), we also define \(\nu_{W,h}\coloneqq(\mathrm{i}_{W,h})_{*}\lambda\in\mathscr{P}(\mathbb{M}_{h})\) for \(0\leq h<\infty\), corresponding to running \(1\)-WL for \(h\) rounds.

While every DIDM of a graphon is a measure from the compact space \(\mathscr{P}(\mathbb{M})\), not every measure in \(\mathscr{P}(\mathbb{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 simply remark that also the set \(\mathbb{D}_{h}\coloneqq\{\nu_{W,h}\mid W\text{ graphon}\}\subseteq\mathscr{P}( \mathbb{M}_{h})\) is compact as it is the image of the compact space of graphons [78, Theorem 9.23] under a continuous function [52]. For us, this means that \(\mathbb{D}_{h}\) and \(\mathscr{P}(\mathbb{M}_{h})\) 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 \(\mathscr{P}(\mathbb{M}_{h})\) and refer to all elements of \(\mathscr{P}(\mathbb{M}_{h})\) as _DIDMs_.

Message-passing graph neural networks.MPNNs learn a \(d\)-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 \(\mathbf{\varphi}=(\varphi_{i})_{i=0}^{L}\) denote a tuple of continuous functions \(\varphi_{0}\colon\mathbb{R}^{0}\to\mathbb{R}^{d_{0}}\) and \(\varphi_{t}\colon\mathbb{R}^{d_{t-1}}\to\mathbb{R}^{d_{t}}\) for \(t\in[L]\), where we simply view \(\varphi_{0}\) as an element of \(\mathbb{R}^{d_{0}}\). Furthermore, let \(\psi\) denote a continuous function \(\psi\colon\mathbb{R}^{d_{L}}\to\mathbb{R}^{d}\). For a graph \(G\), an MPNN initializes a feature \(\mathbf{h}_{v}^{(0)}\coloneqq\varphi_{0}\in\mathbb{R}^{d_{0}}\). Then, for \(t\in[L]\), we compute \(\mathbf{h}_{-}^{(t)}\colon V(G)\to\mathbb{R}^{d_{t}}\) and the single graph-level feature \(\mathbf{h}_{G}\in\mathbb{R}^{d}\) after \(L\) layers by

\[\mathbf{h}_{v}^{(t)}\coloneqq\varphi_{t}\bigg{(}\frac{1}{|V(G)|}\sum_{u\in N (v)}\mathbf{h}_{u}^{(t-1)}\bigg{)}\quad\quad\text{and}\quad\quad\mathbf{h}_{G} \coloneqq\psi\bigg{(}\frac{1}{|V(G)|}\sum_{v\in V(G)}\mathbf{h}_{v}^{(L)} \bigg{)}.\]

For a graphon \(W\in\mathcal{W}\), an MPNN initializes a feature \(\mathbf{h}_{x}^{(0)}\coloneqq\varphi_{0}\in\mathbb{R}^{d_{0}}\) for \(x\in[0,1]\). Then, for \(t\in[L]\), we compute \(\mathbf{h}_{-}^{(t)}\colon X\to\mathbb{R}^{d_{t}}\) and the single graphon-level feature \(\mathbf{h}_{W}\in\mathbb{R}^{d}\) after \(L\) layers by

\[\mathbf{h}_{x}^{(t)}\coloneqq\varphi_{t}\bigg{(}\int_{[0,1]}W(x,y)\mathbf{h}_ {y}^{(t-1)}\,d\lambda(y)\bigg{)}\quad\quad\text{and}\quad\quad\mathbf{h}_{W} \coloneqq\psi\bigg{(}\int_{[0,1]}\mathbf{h}_{x}^{(L)}\,d\lambda(x)\bigg{)}.\]

This generalizes the previous definition, i.e., for a graph \(G\) and its (induced) graphon \(W_{G}\), we have \(\mathbf{h}_{G}=\mathbf{h}_{W_{G}}\) and \(\mathbf{h}_{v}^{(t)}=\mathbf{h}_{x}^{(t)}\) for all \(t\in[L]\), \(v\in V(G)\), and \(x\in I_{v}\); see Appendix C.1.

We now extend the definition of MPNNs to IDMs. While the above definition of \(\mathbf{h}_{-}^{(t)}\) depends on a specific graphon \(W\), an IDM already carries the aggregated information of its neighborhood. Hence, the initial feature \(\mathbf{h}_{\alpha}^{(0)}\coloneqq\varphi_{0}\in\mathbb{R}^{d_{0}}\) for \(\alpha\in\mathbb{M}_{0}\) and \(\mathbf{h}_{-}^{(t)}\colon\mathbb{M}_{t}\to\mathbb{R}^{d_{t}}\)_are defined for all IDMs at once_. Then, for a DIDM \(\nu\in\mathscr{P}(\mathbb{M}_{L})\), we define the single DIDM-level feature \(\mathbf{h}_{\nu}\in\mathbb{R}^{d}\). Formally, we let

\[\mathbf{h}_{\alpha}^{(t)}\coloneqq\varphi_{t}\bigg{(}\int_{\mathbb{M}_{t-1}} \mathbf{h}_{-}^{(t-1)}\,d\alpha\bigg{)}\quad\quad\quad\text{and}\quad\quad \quad\mathbf{h}_{\nu}\coloneqq\psi\bigg{(}\int_{\mathbb{M}_{L}}\mathbf{h}_{-} ^{(L)}\,d\nu\bigg{)}.\]

That is, messages are aggregated via the IDM itself. In addition to \(\mathbf{h}_{-}^{(t)}\colon\mathbb{M}_{t}\to\mathbb{R}^{d_{t}}\), and \(\mathbf{h}_{-}\colon\mathscr{P}(\mathbb{M}_{L})\to\mathbb{R}^{d}\), we define \(\mathbf{h}_{-}^{(t)}\colon\mathbb{M}\to\mathbb{R}^{d_{t}}\) and \(\mathbf{h}_{-}\colon\mathscr{P}(\mathbb{M})\to\mathbb{R}^{d}\) by setting \(\mathbf{h}_{\alpha}^{(t)}\coloneqq\mathbf{h}_{p_{\infty,t}(\alpha)}^{(t)}\) for every \(\alpha\in\mathbb{M}\) and \(\mathbf{h}_{\nu}\coloneqq\mathbf{h}_{(p_{\infty,L})\ast\nu}\) for every \(\nu\in\mathscr{P}(\mathbb{M})\); it will always be clear from the context which of these functions we mean. These definitions for IDMs further generalize the previous definitions for graphons. For a graphon \(W\in\mathcal{W}\), we have \(\mathbf{h}_{W}=\mathbf{h}_{\nu_{W,L}}=\mathbf{h}_{\nu_{W}}\) and \(\mathbf{h}_{x}^{(t)}=\mathbf{h}_{i_{W,t}(x)}^{(t)}=\mathbf{h}_{i_{W}(x)}^{(t)}\) for almost every \(x\in[0,1]\); see Appendix C.1. We call a tuple \(\mathbf{\varphi}\) as defined above an _(L-layer) MPNN model_ if \(\varphi_{t}\) is Lipschitz continuous on \(\{\int_{\mathbb{M}_{t-1}}\mathbf{h}_{-}^{(t-1)}\,d\alpha\mid\alpha\in\mathbb{M }_{t}\}\) for every \(t\in[L]\), and we call \(\psi\) as
defined above _Lipschitz_ if it is Lipschitz continuous on \(\{\int_{\mathbb{M}_{L}}\mathbf{h}_{-}^{(L)}\,d\nu\mid\nu\in\mathscr{P}(\mathbb{M}_ {L})\}\). We use \(\|-\|_{L}\) to denote the Lipschitz constants on these sets. In this paper, \(\boldsymbol{\varphi}\) and \(\psi\) always denote an MPNN model and a Lipschitz function, respectively. We use the term \(\infty\)-layer MPNN model to refer to an \(L\)-layer MPNN model for an arbitrary \(L\).

## 3 Metrics on iterated degree measures

Chen et al. [26] recently introduced the _Weisfeiler-Leman distance_, a polynomial-time computable pseudometric on graphs combining the \(1\)-WL test with the well-known _Wasserstein metric_ from optimal transport [112], where their approach resembles that of 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 of finite measures with total mass at most one. Using mean aggregation, however, is different from the \(1\)-WL test, which relies on sum aggregation. That is, sum aggregation allowed the algorithm to start with a constant coloring, something impossible with mean aggregation, potentially leading to a 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 an 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 the space \(\mathbb{M}_{h}\) 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 a complete separable metric space with Borel \(\sigma\)-algebra \(\mathcal{B}\). For a subset \(A\subseteq S\) and \(\varepsilon\geq 0\), let \(A^{\varepsilon}\coloneqq\{y\in S\mid d(x,y)<\varepsilon\text{ for some }x\in A\}\), and define the _Prokhorov metric_\(\mathsf{P}\) on \(\mathscr{M}_{\leq 1}(S)\) by

\[\mathsf{P}(\mu,\nu)\coloneqq\inf\{\varepsilon>0\mid\mu(A)\leq\nu(A^{ \varepsilon})+\varepsilon\text{ and }\nu(A)\leq\mu(A^{\varepsilon})+\varepsilon\text{ for every }A\in\mathcal{B}\}.\]

As the name suggests, \(\mathsf{P}\) is a metric on \(\mathscr{M}_{\leq 1}(S)\)[99, Section 1.4], and moreover, convergence in \(\mathsf{P}\) is equivalent to convergence in the weak topology [99, Theorem 1.11]. For the _unbalanced Wasserstein metric_ let \(\mu,\nu\in\mathscr{M}_{\leq 1}(S)\), where we assume \(\|\mu\|\geq\|\nu\|\) without loss of generality, and define

\[\mathsf{W}(\mu,\nu)\coloneqq\|\mu\|-\|\nu\|+\inf_{\gamma\in\mathcal{M}(\mu,\nu )}\int_{S\times S}d(x,y)\,d\gamma(x,y),\]

where \(\mathcal{M}(\mu,\nu)\) is the set of all measures \(\gamma\in\mathscr{M}_{\leq 1}(S\times S)\) such that \((p_{1})_{*}\gamma\leq\mu\) and \((p_{2})_{*}\gamma=\nu\). We prove that \(W\) is a well-defined metric on \(\mathscr{M}_{\leq 1}(S,\mathcal{B})\) that coincides with the Wasserstein distance [35, Section 11.8] on probability measures. Furthermore, it satisfies \(\mathsf{W}(\mu,\nu)\leq 2\mathsf{P}(\mu,\nu)\leq 4\sqrt{\mathsf{W}(\mu,\nu)}\) for all \(\mu,\nu\in\mathscr{M}_{\leq 1}(S)\), which implies that it metrizes the weak topology; see Appendix C.2.
The metric \(\mathsf{P}\) is used to define the metric \(d_{\mathsf{P},h}\) on \(\mathbb{M}_{h}\) for \(0\leq h\leq\infty\) as follows. Let \(d_{\mathsf{P},0}\) be the trivial metric on the one-point space \(\mathbb{M}_{0}\) and, for \(h\geq 0\), we inductively let \(d_{\mathsf{P},h+1}\) be the Prokhorov metric on \((\mathbb{M}_{h+1},d_{\mathsf{P},h})\). Then, we define \(d_{\mathsf{P},\infty}\) on \(\mathbb{M}_{\infty}\) by setting \(d_{\mathsf{P}}(\alpha,\beta)\coloneqq d_{\mathsf{P},\infty}(\alpha,\beta) \coloneqq\sup_{h\in\mathbb{N}}\frac{1}{h}\cdot d_{\mathsf{P},h}(\alpha_{h}, \beta_{h})\) for \(\alpha,\beta\in\mathbb{M}_{\infty}\). The factor of \(1/h\) is included in this definition on purpose to ensure that \(d_{\mathsf{P},\infty}\) metrizes the product topology and not the uniform topology. The metric \(d_{\mathsf{W},h}\) on \(\mathbb{M}_{h}\) is defined completely analogously via \(\mathsf{W}\) instead of \(\mathsf{P}\).

The metrics \(d_{\mathsf{P},h}\) and \(d_{\mathsf{W},h}\) on \(\mathbb{M}_{h}\) allow us, for example, to compare the IDM of a point in a graphon to the IDM of a point in another graphon. To compare two graphons' distributions on iterated degree measures, we let \(\delta_{\mathsf{P},h}\) be the Prokhorov metric on \((\mathscr{P}(\mathbb{M}_{h}),d_{\mathsf{P},h})\) for \(0\leq h\leq\infty\) and again define \(\delta_{\mathsf{W},h}\) analogously via the distance \(\mathsf{W}\). We note that these metrics directly apply to graphons \(U,W\in\mathcal{W}\) by simply comparing their DIDMs \(\nu_{U,h}\) and \(\nu_{W,h}\).

**Theorem 2**.: Let \(0\leq h\leq\infty\). The metrics \(d_{\mathsf{P},h}\) and \(d_{\mathsf{W},h}\) are well-defined and metrize the topology of \(\mathbb{M}_{h}\). The metrics \(\delta_{\mathsf{P},h}\) and \(\delta_{\mathsf{W},h}\) are well-defined and metrize the topology of \(\mathscr{P}(\mathbb{M}_{h})\). Moreover, these metrics are computable on graphs in time polynomial in the size of the input graphs and \(h\), up to an additive error of \(\varepsilon\) in the case of \(d_{\mathsf{W},\infty}\) and \(\delta_{\mathsf{W},\infty}\).

MPNNs are Lipschitz in the metrics we defined, where the Lipschitz constant only depends on basic properties of the MPNN model. That is, if two graphons are close in our metrics, then MPNNs outputs for _all_ MPNN models up to a specific Lipschitz constant are close. Formally, let \(\boldsymbol{\varphi}=(\varphi_{i})_{i=0}^{L}\) be an MPNN model with \(L\) layers, and for \(t\in\{0,\ldots,L\}\), let \(\boldsymbol{\varphi}_{t}\coloneqq(\varphi_{i})_{i=0}^{t}\). Then, we inductively define the _Lipschitz constant_\(C_{\boldsymbol{\varphi}}\geq 0\) of \(\boldsymbol{\varphi}\) by \(C_{\boldsymbol{\varphi}_{0}}\coloneqq 0\) for \(t=0\) and \(C_{\boldsymbol{\varphi}_{t}}\coloneqq\|\varphi_{t}\|_{L}\cdot(\|\mathbf{h}_{- }^{(t-1)}\|_{\infty}+C_{\boldsymbol{\varphi}_{t-1}})\) for \(t>0\). This essentially depends on the product of the Lipschitz constants of the functions in \(\boldsymbol{\varphi}\), 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: a constant function mapping all inputs to some \(c\in\mathbb{R}\) 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_{(\boldsymbol{\varphi},\psi)}\) for Lipschitz \(\psi\) analogously by essentially viewing \((\boldsymbol{\varphi},\psi)\) as an MPNN model.

**Lemma 3**.: Let \(\boldsymbol{\varphi}\) be an \(L\)-layer MPNN model for \(L\in\mathbb{N}\) and \(\psi\) be Lipschitz. Then,

\[\|\mathbf{h}_{\alpha}^{(L)}-\mathbf{h}_{\beta}^{(L)}\|_{2}\leq C_{\boldsymbol{ \varphi}}\cdot d_{\mathsf{W},L}(\alpha,\beta)\quad\quad\text{and}\quad\quad\| \mathbf{h}_{\mu}-\mathbf{h}_{\nu}\|_{2}\leq C_{(\boldsymbol{\varphi},\psi)} \cdot\delta_{\mathsf{W},L}(\mu,\nu)\]

for all \(\alpha,\beta\in\mathbb{M}_{L}\) and all \(\mu,\nu\in\mathscr{P}(\mathbb{M}_{L})\), respectively. These inequalities also hold for \(d_{\mathsf{W},\infty}\) and \(\delta_{\mathsf{W},\infty}\) with an additional factor of \(L\) in the Lipschitz constant.

## 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\leq L\leq\infty\), let \(\mathcal{N}_{L}^{n}\subseteq C(\mathbb{M}_{L},\mathbb{R}^{n})\), denote
the set of all functions \(\mathbf{h}_{-}^{(L)}\colon\mathbb{M}_{L}\to\mathbb{R}^{n}\) for an \(L\)-layer MPNN model \(\boldsymbol{\varphi}\) with \(d_{L}=n\). Similarly, let

\[\mathcal{N}\!\mathcal{N}_{L}^{n}\coloneqq\{\mathbf{h}_{-}\mid\boldsymbol{ \varphi}\ L\text{-layer MPNN model, }\psi\colon\mathbb{R}^{d_{L}}\to\mathbb{R}^{n}\text{ Lipschitz}\} \subseteq C(\mathscr{P}(\mathbb{M}_{L}),\mathbb{R}^{n})\]

be the set of all functions computed by an MPNN after a global readout. Our universal approximation theorem, Theorem 4, shows that all continuous functions on IDMs and DIDMs, i.e., 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 \(\mathbb{M}_{L}\) and \(\mathscr{P}(\mathbb{M}_{L})\) are compact, which means we obtain a universal approximation theorem for the whole space of graphons, including all graphs, not restricted to an artificially chosen compact subset.

**Theorem 4**.: Let \(0\leq L\leq\infty\). Then, \(\mathcal{N}_{L}^{1}\) is dense in \(C(\mathbb{M}_{L},\mathbb{R})\) and \(\mathcal{N}\!\mathcal{N}_{L}^{1}\) is dense in \(C(\mathscr{P}(\mathbb{M}_{L}),\mathbb{R})\).

The proof of Theorem 4 is elegant and does not rely on encoding the \(1\)-WL test in an MPNNs. That is, it follows by inductive applications of the Stone-Weierstrass theorem [35, Theorem 2.4.11] combined with the definition of IDMs. It is strikingly similar to the proof of Grebik and Rocha [52] for a similar result concerning tree homomorphism densities; see Appendix D.

While the second statement of Theorem 4, i.e., the graphon-level approximation, is interesting in its own right, the crux of Theorem 4 lies in its first statement, namely, that \(\mathcal{N}_{L}^{1}\) is dense in \(C(\mathbb{M}_{L},\mathbb{R})\), immediately implying that the topology induced by MPNNs on \(\mathscr{P}(\mathbb{M}_{L})\) is the weak topology, i.e., the topology we endowed this space within Section 2.

**Corollary 5**.: Let \(0\leq L\leq\infty\) and \(n>0\). Let \(\nu\in\mathscr{P}(\mathbb{M}_{L})\) and \((\nu_{i})_{i}\) be a sequence with \(\nu_{i}\in\mathscr{P}(\mathbb{M}_{L})\). Then, \(\nu_{i}\to\nu\) if and only if \(\mathbf{h}_{\nu_{i}}\to\mathbf{h}_{\nu}\) for all \(L\)-layer MPNN models \(\boldsymbol{\varphi}\) and Lipschitz \(\psi\colon\mathbb{R}^{d_{L}}\to\mathbb{R}^{n}\).

By combining standard compactness arguments with Theorem 2 and Corollary 5, we can now prove that two graphons are close in our metrics if 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 \(\varepsilon>0\), there are \(L\in\mathbb{N},C>0\), and \(\delta>0\) such that, for all graphons \(U\) and \(W\), if \(\|\mathbf{h}_{U}-\mathbf{h}_{W}\|_{2}\leq\delta\) for every \(L^{\prime}\)-layer MPNN model \(\boldsymbol{\varphi}\) and Lipschitz \(\psi\colon\mathbb{R}^{d_{L^{\prime}}}\to\mathbb{R}^{n}\) with \(L^{\prime}\leq L\) and \(C_{(\boldsymbol{\varphi},\psi)}\leq C\), then \(\delta_{\mathsf{P}}(U,W)\leq\varepsilon\).

We stress that the constants \(L\), \(C\), and \(\delta\) in the theorem statement are independent of the graphons \(U\) and \(W\). The proof of Theorem 6 is simple and elegant. That is, one assumes that the statement does not hold to obtain two sequences of counterexamples, which have to have convergent subsequences by compactness, and the limit graphons allow
us to derive a contradiction. The other equivalences of Theorem 1 can be formalized as similar but simpler epsilon-delta-statements. They follow by the same reasoning together with the universality of tree homomorphism densities [52] and the result of Boker [18]. See Appendix C.4 for the formal statements and their complete proofs.

## 5 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 \(\delta_{\mathsf{P}},\delta_{\mathsf{W}}\), act as a proxy for distances between MPNNs' vectorial representations?
**Q2**: How do untrained MPNNs compare to their trained counterparts in terms of predictive performance?

The source code of all methods and evaluation protocols are available at [https://github.com/nhuang37/finegrain_expressivity_GNN](https://github.com/nhuang37/finegrain_expressivity_GNN). We conducted all experiments on a server with 256 GB RAM and four NVIDIA RTX A5000 GPU cards.

Fine-grained expressivity comparisons of MPNNs.To answer Q1, we construct a 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 \(\ell_{2}\)-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_{i}\}\) for \(i\in[50]\) with 30 vertices using the stochastic block model, where \(G_{i}\sim\operatorname{SBM}(p,q_{i})\), with \(p=0.5\) and \(q_{i}\in[0.1,0.5]\) increases equidistantly. Let \(G\) denote the last graph in the sequence, and observe that \(G\) is sampled from an Erdos-Renyi model, i.e., \(G\sim\operatorname{ER}(p)\). For \(i\in[50]\), we compute the Wasserstein distance \(\delta_{\mathsf{W},h}(G_{i},G)\) and the Euclidean distance \(\|\mathbf{h}_{G_{i}}-\mathbf{h}_{G}\|_{2}\).1 For demonstration purposes, we compare two common MPNN layers, GIN [115] and GraphConv [89], using sum aggregation normalized by the graph's order, varying the hidden dimensions and the number of layers. 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 Corollary 4. 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 to the choice of hidden dimensions and number of layers. In Figure 4 in the appendix shows the same experiments on a 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.

Footnote 1: We compute \(\delta_{\mathsf{W},h}\) via a min-cost-flow algorithm and terminate at most 3 iterations after the WL colors stabilize.
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 layers 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 run _paired_ experiments of trained and untrained MPNNs on the same ten random splits (train/test) and 10-fold cross-validation splits, using the evaluation protocol outlined in Morris et al. [90]. We report the test accuracy with 10-run standard deviation in Table 1 and the mean training time per epoch with standard deviation in Table 2 in the appendix. Table 1 and Table 2 show that untrained MPNNs perform competitively as trained MPNNs while significantly faster, with 20%-46% time savings.

We also investigate the effect of the hidden dimension, i.e., the number of MPNN models in Theorem 6 and the number of layers, i.e., the 1-WL iteration in IDM. Figure 6 in the appendix shows that increasing the hidden dimension improves the performance of untrained MPNNs, while the effect of the number of layers is more nuanced. 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 to preserve graph distance observed as in Figure 5 in the appendix.

## 6 Conclusion

This work devises a 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 a more nuanced understanding of their ability to capture graph structure similarity. In addition, we established a connection between the continuous extensions of 1-WL and MPNNs to graphons, tree distance, and tree homomorphism densities. Our experimental study confirmed the applicability of our theory in real-world prediction tasks. _In summary, 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

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline
**Accuracy**\(\uparrow\) & Mutag & Imdb-Binary & Imdb-Multi & NCI1 & Proteins & Reddit-Binary \\ \hline GIN-m (trained) & 79.01 \(\pm\) 2.24 & 69.96 \(\pm\) 1.43 & 46.29 \(\pm\) 0.76 & **78.61 \(\pm\) 0.34** & **73.51 \(\pm\) 0.47** & **89.73 \(\pm\) 0.37** \\ GIN-m (untrained) & **82.56 \(\pm\) 3.12** & **70.70 \(\pm\) 0.60** & **47.59 \(\pm\) 0.96** & 77.82 \(\pm\) 0.55 & 73.45 \(\pm\) 0.30 & 82.32 \(\pm\) 0.45 \\ \hline GraphConv-m (trained) & **81.62 \(\pm\) 2.08** & 59.14 \(\pm\) 1.93 & 38.75 \(\pm\) 1.62 & **63.28 \(\pm\) 0.6** & 71.49 \(\pm\) 0.67 & **82.4 \(\pm\) 0.19** \\ GraphConv-m (untrained) & 78.03 \(\pm\) 1.57 & **65.77 \(\pm\) 1.32** & **43.29 \(\pm\) 0.96** & 62.36 \(\pm\) 0.45 & **71.83 \(\pm\) 0.42** & 77.15 \(\pm\) 0.29 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Untrained MPNNs show competitive performance as trained MPNNs given sufficiently large hidden dimensionality (3-layer, 512-hidden-dimension). To be consistent with our theory, we use standard architectures with sum aggregation, layer-wise \(1/V(G)\) normalization, and mean pooling, denoted by “MPNN-m.” We report the mean accuracy \(\pm\) std over ten data splits.
graph structure._

Looking forward, future research could focus on extending our theory to labeled graphs and graphons with labels from some compact metric space, namely, graphs and graphons with signals. This presents a challenge, as tree distance and tree homomorphism densities do not readily generalize to labeled graphons. Additionally, further quantitative versions of equivalences in Theorem 1, not resorting to epsilon-variants statements, and generalizing our results to the \(k\)-\(\mathsf{WL}\) are interesting avenues for future exploration.

## Acknowledgements

This research project was started at 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 Boker 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. 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

Figure 2: MPNNs preserve graph distance better 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.
Foundations of Deep Learning (MoDL) (NSF DMS 2031985), NSF CISE 2212457, ONR N00014-22-1-2126 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 Excellence Strategy.
