Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs

## Abstract

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

## 1 Introduction

GNNs have become a widely used tool in science and industry for their ability to capture complex relationships and inter-dependencies in graph-structured data. This makes them particularly useful (Zhou et al., ) in domains such as computational biology (Stokes et al., ; Atz et al., ), molecular chemistry (Wang et al., ), network analysis (Yang et al., ), recommender systems (Fan et al., ), weather forecasting (Keisler, ) and learnable optimization (Qian et al., ; Cappart et al., ). As a result, there has been substantial interest in understanding theoretical properties of GNNs, such as expressivity (Xu et al., ), stability (Ruiz et al., ) or robustness (Ruiz et al., ), and generalization (Verma and Zhang, ; Yehudai et al., ).

Initial works analyzing expressivity of GNNs focused on the Weisfeiler-Leman (WL) graph isomorphism test as a criterion to distinguish graphs (Xu et al., ; Morris et al., ; Zhang et al., , ), others used criteria such as subgraph or homomorphism counts or biconnectivity (Zhang et al., , ; Chen et al., ; Tahmasebi et al., ). However, the WL test merely considers distinguishability of graphs, while analyses of robustness or generalization need a metric, i.e., a quantification of similarity. Usually, for graphs, this is a pseudometric, since GNNs typically cannot distinguish all graphs. In this paper, we define a pseudometric for attributed graphs, which is suitable to enable a unified analysis of expressivity, universal approximation and generalization of message passing GNNs (MPNNs) on graphs with node attributes. This work extends and unifies several prior approaches and, to the best of our knowledge, this is the first work to enable this analysis in such a general setting.

Both generalization and expressivity analysis rely on a few prerequisites that we need to attain via an appropriate (pseudo-)metric: one must identify the finest topology in which (1) MPNNs *separate points*, i.e., for any two different points in space, there exists an MPNN that can distinguish between them; (2) MPNNs are *Lipschitz continuous*; (3) the space of inputs, i.e., attributed graphs, is a *compact space*. Given the interest in understanding GNN robustness and generalization, a few recent works studied pseudometrics on graphs. Most of them reflect the computation structure of MPNNs in defining the distance, essentially aiming to view graphs from the viewpoint of the GNN. Message passing, when unrolled, leads to a tree-structured *computation tree* rooted at each node for computing the feature of that node. The pseudometrics then define distances between computation trees, often via optimal transport (Wasserstein distance).
To quantify stability and domain transfer of GNNs, Chuang and Jegelka () define the *Tree Mover’s Distance* between finite attributed graphs. However, pseudometrics on finite graphs do not yield the desired compactness, and hence no universal approximation. To this end, we focus on graph limits, i.e., graphons. Böker et al. () extend the view to graphons and use *iterated degree measures* (Grebík and Rocha, ) to represent an analogon of computation trees and the 1-WL test on infinite objects. While this enables proofs that MPNNs are Lipschitz and have universal approximation, their pseudometric is restricted to graphs without attributes. In contrast, Levie () defines a limit object of attributed graphs, i.e., *graphon-signals*. His pseudometric, an extension of the *cut distance*, a common metric between attributed graphs, allows to analyze generalization via compactness and Lipschitzness, but is too fine to allow MPNNs to separate points, so does not allow universal approximation. The position paper (Morris et al., ) identifies these limitations, posing them as open problems.

In this work, we close these gaps via a unified approach that allows for an analysis of expressivity, universal approximation and generalization. Inspired by prior works, we too base our pseudometrics on Wasserstein distance (or Prokhorov metric) between distributions of computation tree analogs. To accommodate attributed graphs and graphons, we extend the theory of iterated degree measures – a hierarchy of measures that reflects a computation tree structure – to graphon-signals, and then define an appropriate extension of MPNNs and appropriate distance between our continuous analogs of computation trees. We then prove that our pseudometric leads to a topology with the three desiderata above: (1) MPNNs separate points; (2) MPNNs are Lipschitz continuous; and (3) the input space of attributed graphons is compact. This enables us to invoke the Stone-Weierstrass theorem to show universal approximation for continuous functions on attributed graphons, and hence, graphs. Compactness and Lipschitzness enable a uniform Monte Carlo estimate to compute a generalization bound for MPNNs. Our generalization bound makes no distributional assumptions on the data and number of parameters of the MPNN. Empirically, our pseudometric correlates with output perturbations of the MPNN, allowing to judge stability.

Contributions. In short, we make the following contributions:

- •
We show a *fine-grained* metric version of the separation power of MPNNs: two graphon-signals are close in our metrics if and only if the outputs of all MPNNs on the two graphs are close. This makes our metrics a valid trustworthiness and robustness estimation tool.
- •
We prove a theorem for universal approximation, i.e., that MPNNs can approximate any function over the space of graphs/graphons.
- •
We show a generalization bound for MPNNs which requires no assumptions on the data distribution.

### 1.1 Related Work

Several recent works consider (pseudo)metrics on graphs, especially aiming to capture structural properties of the graph and the computational procedure of message passing. The latter is often described by *computation trees*, hierarchical structures resulting from unrolling message passing (Morris et al., ; Arvind et al., ; Garg et al., ; Xu et al., ; Chuang and Jegelka, ; Jegelka, ). Similarly, hierarchical structures of measures have been used for the analysis of MPNNs (Chen et al., ; Böker et al., ; Maskey et al., ). Although these structures may look different at first glance, they can describe the same iterative message passing mechanism. Other approaches include Titouan et al. () graph metric defined a using both Wasserstein distance and Gromov-Wasserstein distance Mémoli (). This approach, just like classic graph metrics Bunke and Shearer (); Sanfeliu and Fu () requires using approximation. In addition, several graph kernels have been proposed Vishwanathan et al. (); Borgwardt et al. (). Here, we focus on the viewpoint of computation trees, as they closely align with MPNNs.
A number of existing works study generalization for GNNs, e.g., via VC dimension, Rademacher complexity or PAC-Bayesian analysis (Garg et al., ; Maskey et al., ; Morris et al., ; Maskey et al., ; Liao et al., ). Most need assumptions on the data distribution, and often on the MPNN model too. Levie () uses covering number, for a wide range of data distributions. We expand this result to a more general setting.

## 2 Background

We begin with some background and notation, for additional background see Appendix A, and Appendix B for fundamental concepts in topology. An index is available in Appendix L.

Basic Notation. Throughout this text, $\lambda$ denotes the Lebesgue measure on $[0,1]$, and we consider measurability with respect to the Borel $\sigma$-algebra. For any metric space $\mathcal{X}$, we denote by $\mathcal{B}(\mathcal{X})$ its standard Borel $\sigma$-algebra. Given a measure $\mu$ on $\mathcal{X}$, we define its total mass as $\|\mu\|:=\mu(\mathcal{X})$. For a standard Borel space $(\mathcal{Y},\mathcal{B}(\mathcal{Y}))$ and a measurable map $f:\mathcal{X}\to\mathcal{Y}$, we define the *push-forward* $f_{*}\mu$ of $\mu$ via $f$ as $f_{*}\mu(\mathcal{A}):=\mu(f^{-1}(\mathcal{A}))$ for any $\mathcal{A}\in\mathcal{B}(\mathcal{Y})$. Inequality between two measures $\mu\leq\nu$ on some space $\mathcal{X}$ means that for any set $\mathcal{A}\subseteq\mathcal{X}$, it holds that $\mu(\mathcal{A})\leq\nu(\mathcal{A})$. Given a vector $\vec{x}=(x_{\alpha})_{\alpha\in\Lambda}$, where $\Lambda$ can be any countable set, we denote by $x_{\alpha_{0}}$ and $x(\alpha_{0})$ the element at index $\alpha_{0}\in\Lambda$ of $\vec{x}$. For a finite set $\mathcal{A}$, $|\mathcal{A}|$ is the cardinality. For $K\in\mathbb{N}$, we denote $[K]=\{0,1,\ldots,K\}$.

In our notation, a function is denoted by $f:\mathcal{A}\to\mathcal{C}$. When $f$ is evaluated at a point $x\in\mathcal{A}$ we write $f(x)$ or $f_{x}$. We may also write $f(-)$ or $f_{-}$, which simply mean $f$. We define $\|f\|_{\infty}:=\sup_{x\in[0,1]}|f(x)|$. We use $\mathcal{K}^{d}$ to denote any compact subspace of $(\mathbb{R}^{d},\|\cdot\|_{2})$, where $\|\cdot\|_{2}$ is shorthand for the metric $d(x,y)=\|x-y\|_{2}$. An example for $\mathcal{K}^{d}$ is $\mathbf{Sphere}^{d}_{r}(0):=\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq r\}$. Finally, $\mathcal{K}$ without an index can represent any compact space.

The Weak* Topology. Let $\mathscr{M}_{\leq 1}(\mathcal{X})$ and $\mathscr{P}(\mathcal{X})$ denote the space of all nonnegative Borel measures with total mass at most one, and the space of all Borel probability measures on $\mathcal{X}$, respectively. We use $C_{b}(\mathcal{X})$ to denote the set of all bounded continuous real-valued functions on $\mathcal{X}$. We endow $\mathscr{M}_{\leq 1}(\mathcal{X})$ and $\mathscr{P}(\mathcal{X})$ with the topology generated by the maps $\mu\mapsto\int_{\mathcal{X}}fd\mu$ for $f\in C_{b}(\mathcal{X})$, called the weak* topology in functional analysis (Kechris, , Section 17.E), (Bogachev, , Chapter 8). Under this topology, both spaces are standard Borel spaces, and if $\mathcal{K}$ is a compact metric space, then $\mathscr{M}_{\leq 1}(\mathcal{K})$, $\mathscr{P}(\mathcal{K})$ are compact metrizable (Kechris, , Theorem 17.22). See Appendix B.2 for more details.
Under the weak* topology, for a sequence of measures $(\mu_{i})_{i}$ and a measure $\mu$, we have convergence $\mu_{i}\to\mu$ if and only if $\int_{\mathcal{X}}fd\mu_{i}\to\int_{\mathcal{X}}fd\mu$ for every $f\in C_{b}(\mathcal{X})$. Similarly, for measures $\mu$ and $\nu$, we have equality $\mu=\nu$ if and only if $\int_{\mathcal{X}}fd\mu=\int_{\mathcal{X}}fd\nu$ for every $f\in C_{b}(\mathcal{X})$.

Optimal Transport. We will use Optimal Transport to construct a metric between graphs and between graph limits. Unbalanced Optimal Transport (Séjourné et al., ), also called Unbalanced Earth Mover’s Distance and Unbalanced Wasserstein Distance, is a distance function defined by the minimal transportation cost between two distributions. The transport is described by a *coupling* $\gamma$ between two measures $\mu$, $\nu$ on measure spaces $\mathcal{X}$, $\mathcal{Y}$, respectively, i.e., a nonnegative joint measure on $\mathcal{X}\times\mathcal{Y}$ such that $(p_{\mathcal{X}})_{*}\gamma=\mu$, $(p_{\mathcal{Y}})_{*}\gamma\leq\nu$, given that $\left\|\mu\right\|\leq\left\|\nu\right\|$. Here, $p_{\mathcal{X}}$ and $p_{\mathcal{Y}}$ are the projections from $\mathcal{X}\times\mathcal{Y}$ to $\mathcal{X}$ and $\mathcal{Y}$ , i.e., to the first and the second component, respectively, $(p_{\mathcal{X}})_{*}\gamma(A)=\gamma(A\times\mathcal{Y})$ and $(p_{\mathcal{Y}})_{*}\gamma(B)=\gamma(\mathcal{X}\times B)$.

###### Definition 1 (Unbalanced Optimal Transport/Wasserstein Distance) .

Let $(\mathcal{X},d)$ be a metric Polish space. The *Unbalanced Earth Mover’s Distance* between two measures $\mu,\nu$ $\in\mathscr{M}_{\leq 1}(\mathcal{X},d)$ is

$$ $\mathbf{OT}_{d}(\mu,\nu)=\underset{\gamma\in\Gamma(\mu,\nu)}{\mathrm{inf}} \left(\int_{\mathcal{X}\times\mathcal{X}}d(x,y)\text{d}\gamma(x,y)\right)+ \left|\left\|\mu\right\|-\left\|\nu\right\|\right|,$ $$

where $\Gamma(\mu,\nu)$ is the set of all couplings of $\mu$ and $\nu$.

An intuitive way to think about such couplings is as transportation plans from one distribution of points in a space to another, where the cost is given by the overall travel distance.

Product Metric. A product metric $d$ is a metric on the Cartesian product of finitely many metric spaces
$(\mathcal{X}_{1},d_{X_{1}}),\ldots,(\mathcal{X}_{n},d_{X_{n}})$ which metrizes the product topology (see Appendices A.3.4 and A.3.2). Here we use product metrics that are defined as the $\ell_{1}$-norm of the vector of distances measured in $n$ subspaces:

$$ $d((x_{1},\ldots,x_{n}),(y_{1},\ldots,y_{n})):=\|(d_{X_{1}}(x_{1},y_{1}),\ldots ,d_{X_{n}}(x_{n},y_{n}))\|_{1}.$ $$

Graph- and Graphon-signals.
A graph $G=(V,E)$ consists of a set of nodes (vertices) $V=V(G)$ connected by edges $E=E(G)\subseteq V\times V$. We denote by $\mathcal{N}(v)$ the set of neighbors of $v\in V$. A *graph-signal* (alternatively attributed graph) $(G,\mathbf{f})$ is a graph $G$ with node set $V=\{1,\ldots,N\}$, and a signal $\mathbf{f}=(\mathbf{f}_{j})_{j=1}^{N}\in\mathcal{K}^{N\times d}$ that assigns the value $\mathbf{f}_{j}\in\mathcal{K}^{d}$ to each node $j\in\{1,\ldots,N\}$.

A graphon (Lovász, ) may be viewed as a generalization of a graph, where instead of discrete sets of nodes and edges, there are an infinite sets indexed by the sets $V(W):=[0,1]$ for nodes and $E(W):=V(W)^{2}=[0,1]^{2}$ for edges. A graphon is defined as a measurable symmetric function $W:E(W)\rightarrow[0,1]$, i.e., $W(x,y)=W(y,x)$. Each value $W(x,y)$ describes the probability or intensity of a connection between points $x$ and $y$. The graphon is used to study limit behavior of large graphs (Lovász, ).
A graphon-signal (Levie, ) is a pair $(W,f)$ where $W$ is a graphon and $f:V(W)\mapsto\mathcal{K}^{d}$ is a measurable function with respect to the Borel $\sigma$-algebra $\mathcal{B}(V(W))$. Note that any graph/graphon without a signal can be seen as a graph/graphon-signal by simply setting the signal to the constant map, i.e., $\forall x\in V(W):f(x)=c$. We denote by $\mathcal{WS}^{d}$ the space of all *graphon-signals* with signals $f:V(W)\mapsto\mathcal{K}^{d}$.

Any graph-signal can be identified with a corresponding graphon-signal as follows. Let $(G,\mathbf{f})$ be a graph-signal with node set $\{1,\ldots,N\}$ and adjacency matrix $\mathbf{A}=\{a_{i,j}\}_{i,j\in\{1,\ldots,N\}}$.
Let $\{I_{k}\}_{k=1}^{N}$ with $I_{k}=[(k-1)/N,k/N)$ be the equipartition of $[0,1]$ into $n$ intervals. The graphon-signal $(W,f)_{(G,\mathbf{f})}=(W_{G},f_{\mathbf{f}})$ induced by $(G,\mathbf{f})$ is defined by
$W_{G}(x,y)=\sum_{i,j=1}^{N}a_{ij}\mathbbm{1}_{I_{i}}(x)\mathbbm{1}_{I_{j}}(y)$ and $f_{\mathbf{f}}(z)=\sum_{i=1}^{N}f_{i}\mathbbm{1}_{I_{i}}(z)$, where $\mathbbm{1}_{I_{i}}$ is the indicator function of the set $I_{i}\subset[0,1]$. We write $(W,f)_{(G,\mathbf{f})}=(W_{G},f_{\mathbf{f}})$ and identify any graph-signal with its induced graphon-signal.

Message Passing Neural Networks. Message Passing Neural Networks (MPNNs) (Gilmer et al., ) are a class of neural networks designed to process graph-structured data, where nodes may have attributes. Via a message passing process, MPNNs iteratively update each node’s features by aggregating (processed) features from its neighbors. Various aggregation methods exist, e.g., summation, averaging, or coordinate-wise maximum. Our focus is on normalized sum aggregation, which in practice achieves comparable performance to standard sum aggregation (Levie, ).

Computation Trees. Computation trees capture and characterize local structure of graphs by describing the data propagation through neighboring nodes via MPNNs’ successive layers (Morris et al., ; Arvind et al., ; Garg et al., ; Xu et al., ). Since graphons can be seen as graphs with uncountable number of nodes, the concept of computation trees can be extended in a natural way to graphons, by recursively defining computation trees as objects composed of a root node and a distribution of sub-trees induced by the node adjacency of the graphon. The resulting hierarchy of probability measures (Chen et al., ; Böker et al., ) connects to iterated degree measures. These easily integrate with MPNNs and allow us to identify the finest topology in which MPNNs separate points, which is needed to prove a universal approximation theorem for graphons.

Iterated Degree Measures and the $1$-WL Test for Graphons. Grebík and Rocha () define iterated degree measures (IDMs) to generalize the $1$-Weisfeiler-Leman graph isomorphism test (1-WL) (Appendix A.1) and its characterizations to graphons. The 1-WL test performs message passing to uniquely encode (color) the type of computation tree rooted at each node. The collection of trees helps determine graph isomorphism for many pairs of graphs. Initially, the unattributed nodes are indistinguishable, and the test starts with a constant coloring. For graphons, measures replace node colorings, and iterated measures encode computation trees. Analogous to constant colorings, the base measure is defined as $\widetilde{\mathcal{M}}^{0}:=\{*\}$, where $*$ is any value, e.g., 0 0. At level $L\geq 0$, the tree is encoded as the product $\widetilde{\mathcal{H}}^{L}:=\prod\nolimits_{j\leq L}\widetilde{\mathcal{M}}^{j}$ over levels, and the space of next-level features as a measure over features of level $\leq L$: $\widetilde{\mathcal{M}}^{L+1}:=\mathscr{M}_{\leq 1}(\widetilde{\mathcal{H}}^{L})$. We endow $\widetilde{\mathcal{H}}^{L}$ with the product topology and $\widetilde{\mathcal{M}}^{L+1}$ with the weak* topology, as these are natural topologies for product spaces and spaces of measures.

Grebík and Rocha () connect each graphon $W$ with its corresponding node colorings through the maps $\widetilde{\gamma}_{W,L}:[0,1]\mapsto\widetilde{\mathcal{H}}^{L}$, which we call *computation iterated degree measures* (computation IDMs). This differs from both Grebík and Rocha () and Böker et al. () use the name IDM for infinite sequences of Borel measures. These maps send each graphon node $x\in[0,1]$ to its iterated degree measure, i.e., its coloring. We start with a constant map to a tree that encodes a single color, $\widetilde{\gamma}_{W,0}:[0,1]\mapsto\widetilde{\mathcal{H}}^{0}$. The “color” $\widetilde{\gamma}_{W,L}(x)$ at level $L>0$ is a vector, where the $j$-th entry encodes the color of node $x$ after $j$ coloring iterations. That is, letting $\alpha(x)(j)$ be the $j$-th entry of the vector $\alpha(x)$, we set $\widetilde{\gamma}_{W,L}(x)(j)=\widetilde{\gamma}_{(W,f),L-1}(x)(j)$, for every $j<L$. Reflecting the WL-test, the last entry $\widetilde{\gamma}_{W,t}(x)(L)$ is a measure recursively defined as $\widetilde{\gamma}_{W,t}(x)(L)(A)=\int\nolimits_{\widetilde{\gamma}_{W,L-1}^{-
1}(A)}W(x,-)\,d\mu$ for any subset $\mathcal{A}\subseteq\widetilde{\mathcal{H}}^{L-1}$ of the $(L-1)$-th level colors. Namely, we are aggregating colors over the neighborhood of node $x$, according to the connectivity encoded by $W(x,-)$, obtaining a measure over level $(L-1)$ colors, analogous to the discrete 1-WL algorithm. Analogously to computation trees, computation IDMs capture the graphons’ connectivity. In Section 3, we generalize IDMs to additionally incorporate signal information, thus moving from graphon analysis to graphon-signal analysis. We note that this definition is taken from Grebík and Rocha (). It differs from the 1-WL test in Böker et al. (), where they do not concatenate all previous coloring.

###### Definition 1 (Unbalanced Optimal Transport/Wasserstein Distance) .

## 3 Graphon-Signal Metrics through Iterated Degree
Measures

To analyze expressivity and generalization, we need to define an appropriate metric between attributed graphons. Hence, in this section, we first extend the IDM definition in Section 2 to capture both signal values and graphon topology. We then define distributions of iterated degree measures (DIDMs) and metrics between IDMs and DIDMs. These induce distance measures on the space of attributed graphs/graphons, which are polynomial time computable. We essentially transition from our computation trees that capture only graphon structure to computation trees that capture attributes as well. In Section 4, we will see how this allows us to analyze MPNNs on attributed graphs.

Figure: Figure 1: Measuring similarity between graph-signals on the left is translated into measuring similarity between graphon-signals and, lastly, to computing optimal transport between two IDMs, which comprise in the figure of a signal value and a distribution over signal values induced by the graphon’s adjacency. Edges colors depict edge weights and node colors depict signal values.
Refer to caption: x1.png

Computation IDMs and Distributions of IDMs. We first expand the definitions of IDM and computation IDM of Section 2 from unattributed to attributed graphons. In hindsight, our approach is in line with an idea outlined in Section 5 of Böker et al. ().
We change the IDMs’ base space from a one point space, $\{*\}$, to the space of node attributes $\mathcal{K}^{p}$, thus incorporating signal values inherently into the IDMs’ structure. Explicitly, we define the space of iterated degree measures of order-$L$, $\mathcal{H}^{L}$, inductively by first defining $\mathcal{M}^{0}:=\mathcal{K}^{p}$ for $p\in\mathbb{N}$. Then, for every $L\geq 0$, let $\mathcal{H}^{L}=\prod_{i\leq L}\mathcal{M}^{i}$ and $\mathcal{M}^{L+1}=\mathscr{M}_{\leq 1}(\mathcal{H}^{L})$, where the topologies of $\mathcal{H}^{L}$ and $\mathcal{M}^{L+1}$ are the product and the weak* topology, respectively. We call $\mathscr{P}(\mathcal{H}^{L})$ the space of distributions of iterated degree measures (DIDMs) of order-$L$. We denote by $p_{L,j}:\mathcal{H}^{L}\mapsto\mathcal{H}^{j}$ and $p_{L}:\mathcal{H}^{L}\rightarrow\mathcal{M}^{L}$ the canonical projections where $j\leq L<\infty$. Recall that $\alpha(x)(j)$, refers to the $j$-th entry of the vector $\alpha(x)$. Next, we define a graphon-signal 1-WL analog.

###### Definition 2 .

Let $[0,1]$ be the interval with the standard Borel $\sigma$-algebra $\mathcal{B}$ and let $(W,f)$ be a graphon-signal. We define $\gamma_{(W,f),0}:[0,1]\rightarrow\mathcal{H}^{0}$ to be the map $\gamma_{(W,f),0}(x):=f(x)$ for every $x\in[0,1]$. Inductively, we define $\gamma_{(W,f),L+1}:[0,1]\rightarrow\mathcal{H}^{L+1}$ such that

- (a)
$\gamma_{(W,f),L+1}(x)(j)=\gamma_{(W,f),L}(x)(j)$, for every $j\leq n$ and
- (b)
$\gamma_{(W,f),L+1}(x)(L+1)(A)=\int_{\gamma_{(W,f),L}^{-1}(A)}W(x,-)\,d\mu$, whenever $\mathcal{A}\subseteq\mathcal{H}^{n}$ is a Borel set.

Finally, for every $L\in\mathbb{N}$, let $\Gamma_{(W,f),L}$ be the push-forward of $\lambda$ via $\gamma_{(W,f),L}$. We call $\gamma_{(W,f),L}$ a *computation iterated degree measure (computation IDM)* of order-$L$ and $\Gamma_{(W,f),L}$ a *distribution of computation iterated degree measures (computation DIDM)* of order-$L$.

In appendix B.2 we prove that the spaces of IDMs and DIDMs are compact, which, together with the continuity of MPNNs (Theorem 4), and the separation power of MPNNs (Theorem 5), allows us to use the Stone-Weierstrass theorem (Theorem A.4) to show universality and to use uniform Monte Carlo estimation to compute a generalization bound for MPNNs.

###### Theorem 1 .

The spaces $\mathcal{H}^{L}$ and $\mathscr{P}(\mathcal{H}^{L})$ are compact spaces for any $L\in\mathbb{N}$.

The proof of Theorem 1 inductively uses the fact that given any compact space $\mathcal{K}$, the spaces $\mathscr{M}_{\leq 1}(\mathcal{K})$ and $\mathscr{P}(\mathcal{K})$ endowed with the weak* topology are compact metrizable spaces. Tychonoff’s theorem, which states that the product of any collection of compact topological spaces is compact with respect to the product topology, completes the argument.

DIDM Mover’s Distance. Next, we define a distance between graphons, viewed as distributions of computation IDMs. Inspired by the tree mover’s distance of Chuang and Jegelka (), we do this by optimal transport with a ground metric between IDMs, i.e., trees. As both computational IDMs and trees can be seen to represent the same thing i.e. MPNNs’ computational procees. Thus, we explicitly construct a metric that metrizes the topology of $\mathcal{H}^{L}$. We define the IDM distance of order-0 0 on $\mathcal{M}^{0}=\mathcal{H}^{0}=\mathcal{K}^{p}$, for $p\in\mathbb{N}$, by $d_{\rm IDM}^{0}:=\left\|x-y\right\|_{2}$, and denote by $\mathbf{OT}_{d_{\rm IDM}^{0}}$ the optimal transport distance on $\mathcal{M}^{1}=\mathscr{M}_{\leq 1}(\mathcal{H}^{0}).$ We define $d_{\rm IDM}^{L}$ recursively as the product metric on $\mathcal{H}^{L}=\prod_{j\leq L}\mathcal{M}^{j}$ when the distance on $\mathcal{M}^{j}=\mathscr{M}_{\leq 1}(\mathcal{H}^{j-1})$ for $0<j<L-1$ is $\mathbf{OT}_{d_{\rm IDM}^{j-1}}$. Explicitly written,

$$ $d_{\rm IDM}^{L}(\mu,\nu):=\begin{cases}\left\|\mu_{0}-\nu_{0}\right\|_{2}+\sum ^{L}_{j=1}\mathbf{OT}_{d_{\rm IDM}^{j-1}}(\mu_{j},\nu_{j})&\text{ }:\text{if } \infty>L>0\\ \left\|\mu_{0}-\nu_{0}\right\|_{2}&\text{ }:L=0\end{cases}$ $$

for $\mu=(\mu_{j})^{L}_{j=0}$, $\nu=(\nu_{j})^{L}_{j=0}\in\mathcal{H}^{L}.$ The next theorem states that, for every $L\in\mathbb{N}$, both the IDM distance $d_{\rm IDM}^{L}$ and optimal transport distance $\mathbf{OT}_{d_{\rm IDM}^{L}}$ fit naturally to the topologies of IDMs and DIDMs defined in Section 2.

###### Theorem 2 .

Let $L\in\mathbb{N}$. The metrics $d_{\rm IDM}^{L}$ on $\mathcal{H}^{L}$ and $\mathbf{OT}_{d_{\rm IDM}^{L}}$ on $\mathscr{P}(\mathcal{H}^{L})$ and $\mathscr{M}_{\leq 1}(\mathcal{H}^{L})$ are well-defined. Moreover, $\mathbf{OT}_{d_{\rm IDM}^{L}}$ metrizes the weak* topologies of $\mathscr{M}_{\leq 1}(\mathcal{H}^{L})$ and $\mathscr{P}(\mathcal{H}^{L})$.

We now use the distance between IDMs to define a distance between graphons, viewed as distributions of computation IDMs. Specifically, we define the DIDM Mover’s Distance between graphons as the optimal transport cost between their DIDMs, with ground metric $d_{\rm IDM}^{L}(\cdot,\cdot)$:

###### Definition 3 (DIDM Mover’s Distance) .

Given two graphon-signals $(W_{a},f_{a})$, $(W_{b},f_{b})$ and $L\geq 1$, the *DIDM Mover’s Distance* between $(W_{a},f_{a})$ and $(W_{b},f_{b})$ is defined as

$$ $\delta_{\rm DIDM}^{L}((W_{a},f_{a}),(W_{b},f_{b})):=\mathbf{OT}_{d_{\rm IDM}^{ L}}(\Gamma_{(W_{a},f_{a}),L},\Gamma_{(W_{b},f_{b}),L}).$ $$

Intuitively, $\delta_{\rm DIDM}^{L}$ is the minimum cost required to transport node-wise IDMs from one graphon to another. Given two attributed graphs, $(G,\mathbf{f})$ and $(H,\mathbf{g})$, the DIDM mover’s distance, $\delta_{\rm DIDM}^{L}((G,\mathbf{f}),(H,\mathbf{g})):=\delta_{\rm DIDM}^{L}((W
_{G},f_{\mathbf{f}}),(W_{H},f_{\mathbf{g}}))$ can be computed in polynomial time, as shown next.

###### Theorem 3 .

For any fixed $L\in\mathbb{N}$, $\delta_{\rm DIDM}^{L}$ between any two graph-signals $(G,\mathbf{f})$ and $(H,\mathbf{g})$
can be computed in time polynomial in $L$ and the size of $G$ and $H$, namely $O(L\cdot N^{5}\log(N))$ where $N=\max(\left|V(G)\right|,\left|V(H)\right|)$.

We define $\delta_{\rm DIDM}$ using the induced graphon, but we compute it directly on the graph. We do not actually use a data-structure for IDMs. Instead, we compute each time cost matrices derived from the cost matrices of the previous layer, avoiding the need to explicitly represent the IDMs via some data-structure. We first compute a cost matrix $D_{0}$, containing the $L_{2}$ distances between the nodes’ attributes, and then use it as a cost matrix of an OT problem. We repeatedly solve OT problems based on the previous cost matrix and the adjacency matrices of the graphs using linear programming and sum the results with the previous cost matrix to get the next cost matrix. Each OT problem is solved in $O(N^{3}\log(N))$ time (Flamary et al., ; Chapel et al., ). At each step we solve $N^{2}$ problems. This means $O(N^{2}\cdot N^{3}\log(N))$ per step. After computing $D_{L}$, we use it to solve a single OT problem between two uniform distributions, one over $V(G)$ and the other over $V(H)$ to get $\delta_{\rm DIDM}^{L}$’s value, which again takes $O(N^{3}\log(N))$. Hence, the total computation time is $O(L\cdot N^{2}\cdot N^{3}\log(N))$. For more details on computation see Appendix J.2. In Section 5, we evaluate our metric empirically.

Alternative Approach. For the sake of completeness, we present in Appendix J the Prokhorov metric $\mathbf{P}$, which can be used for defining alternative metrics to optimal transport which metrize $\mathcal{H}^{L}$, as done in Böker et al. (). In Appendix J, we use $\mathbf{P}$ to define sch alternative metrics, namely, $\mathbf{PD}^{L}$, $\mathbf{P}_{\mathbf{PD}^{L}}$, and $\mathbf{TPD}^{L}$, which correspond to and induce the same topologies as $d_{\rm IDM}^{L}$, $\mathbf{OT}_{d_{\rm IDM}^{L}}$, and $\delta_{\rm DIDM}^{L}$, respectively. All of our results can be equivalently stated with $\mathbf{PD}^{L}$, $\mathbf{P}_{\mathbf{PD}^{L}}$, and $\mathbf{TPD}^{L}$, where the computational complexity increases from $O(L\cdot N^{5}\cdot\log(N))$ to $O(L\cdot N^{7})$.

###### Definition 2 .

###### Theorem 1 .

###### Theorem 2 .

###### Definition 3 (DIDM Mover’s Distance) .

###### Theorem 3 .

## 4 MPNNs and Their Relation to DIDM Mover’s Distance

We next integrate MPNNs into our framework and define a general message passing scheme for computing features of attributed graphons, which generalizes standard graph MPNNs. Equivalently, by defining aggregated features via IDMs and DIDMs, we can define the MPNN directly on IDMs and DIDMs. In Appendix D, we show the equivalency between MPNNs defined on graphon-signals and MPNNs defined on IDMs and DIDMs. By analyzing MPNNs on IDMS and DIDMs, we prove Theorems 4 and 5, which state that two graphon-signals are close to each other in our metrics if and only if the two outputs
of any MPNN on the two graphon-signals are close-by in $\ell_{2}$ distance.

An MPNN consists of features initialization, which is a learnable Lipschitz continuous mapping $\varphi^{(0)}:\mathbb{R}^{p}\mapsto\mathbb{R}^{d_{0}}$, followed by $L$ layers, each of which consists of two steps: a message passing layer (MPL) that aggregates neighborhood information, followed by a node-wise update layer. Here, we assume the MPL to be normalized sum pooling, when applied on graph-signals or graphon-signals. The update layer consists of a learnable Lipschitz continuous mapping $\varphi^{(t)}:\mathbb{R}^{2d_{t-1}}\mapsto\mathbb{R}^{d_{t}}$ where $0<t\leq L$ is the layer’s index. Each layer computes a representation of each node. For predictions on the full graph, a readout layer aggregates the node representations into a single graph feature and transforms it by a learnable Lipschitz function $\psi:\mathbb{R}^{d_{L}}\mapsto\mathbb{R}^{d}$ for some $d\in\mathbb{N}$. For the readout, with use average pooling.

###### Definition 4 (MPNN Model) .

Let $L\in\mathbb{N}$ and $p,d_{0},\ldots,d_{L},d\in\mathbb{N}$. We call any collection $\varphi=(\varphi^{(t)})_{t=0}^{L}$ of Lipschitz continuous functions $\varphi^{(0)}:\mathbb{R}^{p}\mapsto\mathbb{R}^{d_{0}}$ and $\varphi^{(t)}:\mathbb{R}^{2d_{t-1}}\mapsto\mathbb{R}^{d_{t}}$ for $1\leq t\leq L$, an *$L$-layer MPNN model*, and call $\varphi^{(t)}$ *update functions*. For Lipschitz continuous $\psi:\mathbb{R}^{d_{L}}\mapsto\mathbb{R}^{d}$, we call the tuple $(\varphi,\psi)$ an *MPNN model with readout*, where $\psi$ is called a *readout function*. We call $L$ the *depth* of the MPNN, $p$ the *input feature dimension*, $d_{0},\ldots,d_{L}$ the *hidden feature dimensions*, and $d$ the *output feature dimension*.

An MPNN model processes graph-signals as a function as follows.

###### Definition 5 (MPNNs on graph-signals) .

Let $(\varphi,\psi)$ be an $L$-layer MPNN model with readout, and $(G,\mathbf{f})$ be a graph-signal where $\mathbf{f}:V(G)\mapsto\mathbb{R}^{p}$. The *application* of the MPNN on $(G,\mathbf{f})$ is defined as follows: initialize $\mathfrak{g}_{-}^{(0)}:=\varphi^{(0)}(\mathbf{f}(-))$ and compute the hidden node representations $\mathfrak{g}_{-}^{(t)}:V(G)\to\mathbb{R}^{d_{t}}$ at layer $t$, with $1\leq t\leq L$ and the graph-level output $\mathfrak{G}\in\mathbb{R}^{d}$ by

$$ $\mathfrak{g}_{v}^{(t)}:=\varphi^{(t)}\Big{(}\mathfrak{g}^{(t-1)}_{v},\frac{1}{ |V(G)|}\sum_{u\in\mathcal{N}(v)}\mathfrak{g}_{u}^{(t-1)}\Big{)}\quad\text{and} \quad\mathfrak{G}:=\psi\Big{(}\frac{1}{|V(G)|}\sum_{v\in V(G)}\mathfrak{g}_{v} ^{(L)}\Big{)}.$ $$

To clarify the dependency of $\mathfrak{g}$ and $\mathfrak{G}$ on $\varphi$ and $(G,\mathbf{f})$, we often denote $\mathfrak{g}(\varphi)_{v}^{(t)}$ or $\mathfrak{g}(\varphi,G,\mathbf{f})_{v}^{(t)}$, and $\mathfrak{G}(\varphi,\psi)$ or $\mathfrak{G}(\varphi,\psi,G,\mathbf{f})$. Here, we use normalized sum aggregation over neighborhoods to be directly compatible with the graphon version.
To extend this MPNN to graphons, we transition from a discrete set of nodes to a continuous set by converting the normalized sum into an integral.

###### Definition 6 (MPNNs on Graphon-signals) .

Let $(\varphi,\psi)$ be an $L$-layer MPNN model with readout, and $(W,f)$ be a graphon-signal where $f:V(W)\mapsto\mathbb{R}^{p}$. The *application* of the MPNN on $(W,f)$ is defined as follows: initialize $\mathfrak{f}_{-}^{(0)}:=\varphi^{(0)}(f(-))$, and compute the hidden node representations $\mathfrak{f}_{-}^{(t)}:V(W)\to\mathbb{R}^{d_{t}}$ at layer $t$, with $1\leq t\leq L$ and the graphon-level output $\mathfrak{F}\in\mathbb{R}^{d}$ by

$$ $\displaystyle\mathfrak{f}^{(t)}_{x}:=\varphi^{(t)}\Big{(}\mathfrak{f}_{x}^{(t- 1)},\int_{[0,1]}W(x,y)\mathfrak{f}^{(t-1)}_{y}\text{d}\lambda(y)\Big{)}$ and $\displaystyle\mathfrak{F}:=\psi\Big{(}\int_{[0,1]}\mathfrak{f}(\varphi)^{(L)}_ {x}\text{d}\lambda(x)\Big{)}.$ $$

As before, we often denote $\mathfrak{f}(\varphi)_{v}^{(t)}$ or $\mathfrak{f}(\varphi,W,f)_{v}^{(t)}$, and $\mathfrak{F}(\varphi,\psi)$ or $\mathfrak{F}(\varphi,\psi,W,f)$. The following definition generalizes MPNNs to IDMs and DIDMs using the canonical projections $p_{L,j}:\mathcal{H}^{L}\mapsto\mathcal{H}^{j}$ and $p_{L}:\mathcal{H}^{L}\rightarrow\mathcal{M}^{L}$, where $j\leq L<\infty$.

###### Definition 7 (MPNNs on IDMs and DIDMs) .

Let $(\varphi,\psi)$ be an $L$-layer MPNN model with readout. The *application* of the MPNN on IDMs and DIDMs is defined as follows: initialize $\mathfrak{h}(\varphi)_{-}^{(0)}:=\varphi^{(0)}_{-}$, and compute the hidden IDM node representations $\mathfrak{h}(\varphi)^{(t)}_{-}:\mathcal{H}^{t}\rightarrow\mathbb{R}^{d_{t}}$ on any order-$t$ IDM $\tau$, and the DIDM-level putput $\mathfrak{H}\in\mathbb{R}^{d}$ on an order-$L$ DIDM $\nu$, by

$$ $\displaystyle\mathfrak{h}^{(t)}_{\tau}:=\varphi^{(t)}\left(\mathfrak{h}^{(t-1) }_{p_{t,t-1}(\tau)},\int_{\mathcal{H}^{t-1}}\mathfrak{h}_{-}^{(t-1)}\text{d}p_ {t}(\tau)\right)$ and $\displaystyle\mathfrak{H}:=\psi\left(\int_{\mathcal{H}^{L}}\mathfrak{h}^{(L)}_ {-}\text{d}\nu\right).$ $$

We also denote $\mathfrak{h}(\varphi)_{\tau}^{(t)}$ or $\mathfrak{h}(\varphi,\tau)^{(t)}$, and $\mathfrak{H}(\varphi,\psi)$ or $\mathfrak{H}(\varphi,\psi,\nu)$. When $\tau$ depends on some parameter $x$ (see definition 2), we can also use $\mathfrak{h}(\varphi,\tau(x))^{(t)}:=\mathfrak{h}(\varphi,\tau)^{(t)}_{x}$.

We name MPNNs’ hidden representations and outputs *features*. MPNNs on IDMs and DIDMs are canonical extensions of MPNNs on graphon-signals as follows. Let $(W,f)$ be a graphon-signal and $(\varphi,\psi)$ an $L$-layers MPNN model with readout. Then, given the computation IDMs $\{\gamma_{(W,f),t}\}_{t=0}^{L}$ and DIDM $\Gamma_{(W,f),L}$ from the graphon-signals 1-WL algorithm (Definition 2), we have that $\mathfrak{f}(\varphi,W,f)^{(t)}_{x}=\mathfrak{h}(\varphi)_{\gamma_{(W,f),t}(x)
}^{(t)}$ for any $t\in[L]$,
$x\in[0,1]$. Similarly, $\mathfrak{F}(\varphi,\psi,W,f)=\mathfrak{H}(\varphi,\psi,\Gamma_{(W,f),L})$. That is, graphon-signals’ hidden representations are computed through their computation IDMs and DIDMs. Similarly, if $(G,\mathbf{f})$ is a graph-signal, then, $\mathfrak{g}(\varphi,G,\mathbf{f})^{(t)}_{v}=\mathfrak{f}(\varphi,W,f)^{(t)}_{
x_{v}}$ for any $t\in[L],$ $v\in V(G)$, and $\mathfrak{G}(\varphi,\psi,G,\mathbf{f})=\mathfrak{F}(\varphi,\psi,W_{G},f_{
\mathbf{f}})$ when $(W_{G},f_{\mathbf{f}})$ is $(G,\mathbf{f})$’s induced graphon-signal and $x_{v}\in I_{v}$.

Corollary 1 is a consequence of Theorem 6, one of our main results, presented in Section 5. It reveals a strong connection between MPNN features and the topology of $\mathscr{P}(\mathcal{H}^{L})$, i.e., the weak* topology.

###### Corollary 1 .

Let $L\in\mathbb{N}$ and $d>0$ be fixed. Let $\nu\in\mathscr{P}(\mathcal{H}^{L})$ and $(\nu_{i})_{i}$ be a sequence with $\nu_{i}\in\mathscr{P}(\mathcal{H}^{L})$. Then, $\nu_{i}\rightarrow\nu$ if and only if $\mathfrak{H}(\varphi,\psi,\nu_{i})\rightarrow\mathfrak{H}(\varphi,\psi,\nu)$ for all $L$-layer MPNN models $\varphi$ with a readout function $\psi:\mathbb{R}^{d_{L}}\rightarrow\mathbb{R}^{d}$.

We now present Theorem 4 and Theorem 5. Together, they establishe a bidirectional fundamental connection between our metrics and the outputs of all possible MPNNs, where the second direction is phrased as a delta-epsilon relation. Specifically, Theorem 4 states a Lipschitz bound for MPNNs with respect to the IDM and DIDM Mover’s distance. This quantifies stability as in the finite case in Chuang and Jegelka ().

###### Theorem 4 .

Let $\varphi$ be an $L$-layer MPNN model. Then, there exists a constant $C_{\varphi}$, that depends only on $L$, the number of layers, and the Lipschitz constants of model’s update functions, such that

$$ $\|\mathfrak{h}(\varphi,\alpha)^{(L)}-\mathfrak{h}(\varphi,\beta)^{(L)}\|_{2} \leq C_{\varphi}\cdot d_{\rm IDM}^{L}(\alpha,\beta)$ $$

for all $\alpha,\beta\in\mathcal{H}^{L}$. If $\varphi$ has a readout function $\psi$, then, for all $\mu,\nu\in\mathscr{P}(\mathcal{H}^{L})$, there exists a constant $C_{(\varphi,\psi)}$, that depends only on $C_{\varphi}$ and the Lipschit constant of the model’s readout function, such that

$$ $\|\mathfrak{H}(\varphi,\psi,\mu)-\mathfrak{H}(\varphi,\psi,\nu)\|_{2}\leq C_{( \varphi,\psi)}\cdot\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu,\nu).$ $$

In our analysis, Theorem 4 is vital for the generalization analysis in Section 5. The following theorem is roughly the converse of Theorem 4, and is based on Corollary 1.

###### Theorem 5 .

Let $d>0$ be fixed. For every $\varepsilon>0$, there are $L\in\mathbb{N}$, $C>0$, and $\delta>0$ such that, for all DIDMs $\mu$, $\nu$ $\in\mathscr{P}(\mathcal{H}^{L})$, if $\|\mathfrak{H}(\varphi,\psi,\mu)-\mathfrak{H}(\varphi,\psi,\nu)\|_{2}\leq\delta$ holds for every $L$-layer MPNN model $\varphi$ with readout function $\psi:\mathbb{R}^{d_{L}}\to\mathbb{R}^{d}$ when $C_{(\varphi,\psi)}\leq C$, then $\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu,\nu)\leq\varepsilon$.

Note that the constants $L$, $C$, and $\delta$ are independent of the DIDMs $\mu$ and $\nu$. The combination of Theorem 4 and Theorem 5 implies that we can not only bound MPNNs’ output perturbations with $\mathbf{OT}_{d_{\rm IDM}^{L}}$, but also estimate them, and vice versa, estimate $\mathbf{OT}_{d_{\rm IDM}^{L}}$ with MPNNs’ output perturbations.

Empirical Evaluation. As a proof of concept, we empirically test the correlation between the $\delta_{\rm DIDM}$ and the output of MPNNs. Using stochastic block models $\text{SBM}(p,q_{i})$, with $p=0.5$ and $q_{i}\in[0.1,0.5]$ increasing equidistantly, we generated, a sequence of $50$ random graphs $\{G_{i}\}^{49}_{i=0}$, each with 30 vertices. We compare $\delta_{\rm DIDM}^{2}(G_{i},G)$, computed via a linear program, with random MPNNs’ outputs. Note that the limit graph, $G_{49}$, is sampled from an Erdős Rényi model, i.e., $G\sim\text{ER}(p).$ We conducted the experiment twice, once with a constant signal attached and once with signal values sampled from a normal distribution $\mathcal{N}(\mu,\sigma)$ with $\mu=1$ and $\sigma=\frac{50-i}{50}$, i.e., signal values that converge to a constant signal when $i\to\infty$ and are close to it for $i=49$. Figure 2, shows the results when varying hidden dimension. The results show a strong correlation between input distance and GNN outputs. More empirical results may be found in Appendix K.

Figure: Figure 2: In the six leftmost figures, a convergent sequence of graphs without attributes, in the six rightmost figures, the same graph sequence with signal values sampled from a normal distribution.
Refer to caption: x2.png

###### Definition 4 (MPNN Model) .

###### Definition 5 (MPNNs on graph-signals) .

###### Definition 6 (MPNNs on Graphon-signals) .

###### Definition 7 (MPNNs on IDMs and DIDMs) .

###### Corollary 1 .

###### Theorem 4 .

###### Theorem 5 .

## 5 Main Results

Next, we state our main results. First, we show a universal approximation theorem for MPNNs on IDMs and DIDMs, which means that MPNNs can approximate any continuous function on IDMs and DIDMs. This entails universal approximation of MPNNs on attributed graphs/graphons as well, generalizing the results of Böker et al. () to attributed graphs. Second, we introduce a uniform generalization bound for MPNNs.

Universal Approximation. We define the set
$\mathcal{N}^{d_{L}}_{L}:=\{\mathfrak{h}(\varphi)^{(L)}_{-}:\mathcal{H}^{L}
\mapsto\mathcal{K}^{d_{L}}|\varphi\text{ is an $L$-layer MPNN model}\}
\subseteq C(\mathcal{H}^{L},\mathbb{R}^{d_{L}})$, where $C(\mathcal{H}^{L},\mathbb{R}^{d_{L}})$ is the set of all continuous functions, $\mathcal{H}^{L}\mapsto\mathbb{R}^{d_{L}}$. Similarly we define the set $\mathcal{NN}^{d}_{L}:=\{\mathfrak{H}(\varphi,\psi,-):\mathscr{P}(\mathcal{H}^{
L})\mapsto\mathcal{K}^{d}|(\varphi,\psi)\text{ is an $L$-layer MPNN model with
readout}\}\subseteq C(\mathscr{P}(\mathcal{H}^{L}),\mathbb{R}^{d})$.

###### Theorem 6 (Universal Approximation) .

Let $L\in\mathbb{N}$. Then, the set $\mathcal{N}^{1}_{L}$ is dense in $C(\mathcal{H}^{L},\mathbb{R})$ and the set $\mathcal{N}\mathcal{N}^{1}_{L}$ is dense in $C(\mathscr{P}(\mathcal{H}^{L}),\mathbb{R})$.

Our theory implies that if we use all MPNNs, we can distinguish between all attributed graphs with positive graph distance (since they could take different function values). Indeed, Table 1 and 3 in Böker et al. () illustrate that using sufficiently many MPNNs provides enough discriminative power for graph classification tasks on both attributed and unattributed graphs. Our results supply the theoretical background for their experiments with attributed graphs.

Generalization Bounds for MPNNs.
We consider $C$-class classification, i.e., the data is drawn from a distribution $(\mathscr{P}(\mathcal{H}^{L})\times\{0,1\}^{C},\Sigma,\tau)$ and let $\mathcal{L}$ be a Lipschitz loss function. We denote by $\mathrm{Lip}(\mathscr{P}(\mathcal{H}^{L}),L_{1})$, the space of Lipschitz continuous mappings $\mathfrak{L}:\mathscr{P}(\mathcal{H}^{L})\to\mathbb{R}^{C}$ with Lipschitz constant $L_{1}$. We aim to minimize the *statistical risk*, $\mathcal{R}(\mathfrak{L})=\int\mathcal{E}(\mathfrak{L}(\nu),y)d\tau(\nu,y)$, where $\mathfrak{L}\in\mathrm{Lip}(\mathscr{P}(\mathcal{H}^{L}),L_{1})$, by minimizing the *empirical risk* $\hat{\mathcal{R}}_{\mathbf{X}}(\mathfrak{L}_{\mathbf{X}})=\frac{1}{N}\sum_{i=1
}^{N}\mathcal{E}(\mathfrak{L}_{\mathbf{X}}(\nu_{i}),Y_{i})$ on identically distributed (i.i.d) samples $\mathbf{X}=(X_{1},\ldots,X_{N})$ from the data distribution $(\mathscr{P}(\mathcal{H}^{L})\times\{0,1\}^{C},\tau)$ where $0<i\leq N:X_{i}=(\nu_{i},Y_{i})$ and $\mathfrak{L}_{\mathbf{X}}$ is a model with some possible dependency on the sampled data, e.g. through training.

###### Theorem 7 (MPNN generalization theorem) .

Consider the above classification setting, and let $L=L_{1}(L_{2}+1)$. Let $\{X_{i}\}^{N}_{i=1}$ be independent random samples from the data distribution $(\mathscr{P}(\mathcal{H}^{L})\times\{0,1\}^{C},\Sigma,\tau)$. Then, for every $p>0$, there exists an event $\mathcal{U}^{p}\subset(\mathscr{P}(\mathcal{H}^{L})\times\{0,1\}^{C})^{N}$, regarding the choice of $\mathbf{X}=(X_{1},\ldots,X_{N})$ with probability $\nu^{N}(\mathcal{U}^{p})\geq 1-Cp-2\frac{C^{2}}{N}$, in which for every function $\mathfrak{L}_{\mathbf{X}}$ in the hypothesis class $Lip(\mathscr{P}(\mathcal{H}^{L}),L_{1})$, with we have

$$ $\displaystyle\left|\mathcal{R}(\mathfrak{L}_{\mathbf{X}})-\hat{\mathcal{R}}_{ \mathbf{X}}(\mathfrak{L}_{\mathbf{X}})\right|\leq\xi^{-1}(N/2C)\left(2L+\tfrac {1}{\sqrt{2}}(L+\mathfrak{L}(0,0))(1+\sqrt{\log(2/p)}\right),$ (1) $$

where $\xi(\epsilon)=\frac{\kappa(\epsilon)^{2}\log(\kappa(\epsilon))}{\epsilon^{2}}$, $\kappa$ is the covering number of $\mathscr{P}(\mathcal{H}^{L})\times\{0,1\}^{C}$ and $\xi^{-1}$ is the inverse function of $\xi$.

This essentially means that when minimizing the empirical risk on $N$ data points drawn from the data distribution $\tau$, with probability $1-Cp-2C^{2}/N$, we have the above bound on the generalization error. Moreover, the term $\xi^{-1}(N/2C)$ in Equation 1 approaches zero when we take $N$ to infinity. This means that, even with no assumptions on the data and number of parameters of the MPNN (apart from lipschitzness), we have a generalization bound that decays to zero as the training set size goes to infinity. Because the space $\mathscr{P}(\mathcal{H}^{L})\times\{0,1\}^{C}$ is compact (Theorem 8), its covering number, $\kappa$, which is here implicit, is finite. Further details of our construction are provided in Appendix I. In comparison to other recent works on generalization, Garg et al. (); Liao et al. () assume bounded degree graphs, Morris et al. () assumes graphs with bounded color complexity, and Maskey et al. (), assumes the graphs are sampled from a small set of graphons. Moreover, Garg et al. (); Liao et al. (); Morris et al. () do not allow a general MPL as presented in this paper, so their dependency on $N$ is $N^{-1/2}$ (in contrast to $\xi^{-1}(N)$ in our work and in Levie ()), which means their generalization bound decays faster as a function of the training set size $N$. Both our work and Levie () do not make any assumptions on the graphs and allow a general MPL scheme, but our classification learning setting generalizes that in Levie (), which assumes a ground truth classifier. We, in contarst, remove this assumption by defining data distributions as joint distributions over both the input and label space.

Empirical Evaluation. Our generalization result depends on the covering number, which is constant, and on the Lipschitz constant, which depends on the model, i.e., the number of parameters and layers as well as the update functions. We checked the extent to which $\delta_{\rm DIDM}^{2}$ correlates with the maximal distance of 100 MPNNs’ vectorical representation distances on MUTAG dataset and marked the Lipschitz relation (see Figure 3). See Appendix K for more details and experimental results. The code for all experiments will be publicly available upon acceptance of this paper.

Figure: Figure 3: GraphConv embeddings preserve graph distance better than GIN. The Lipschitz bound is marked by the red line. GIN is more affected by the number of layers and hidden dimensions.
Refer to caption: x3.png

###### Theorem 6 (Universal Approximation) .

###### Theorem 7 (MPNN generalization theorem) .

## 6 Conclusion

This work provides a deeper understanding of the properties of GNNs on attributed graphs. We considered the completion of the space of attributed graphs to the space of attributed graphons, to obtain a compact space to use the Stone-Weierstrass theorem for universal approximation, and obtain a finite covering number for generalization analysis. Through the theory of iterated degree measures, we define pseudometrics that allow us to formulate the fine-grained expressivity of GNNs on attributed graphs. Our results state that two graphon-signals are close in our metrics if and only if the outputs of all any MPNN on the two graphs are close. Moreover, the space of attributed graphons is compact under our metrics. As a result, we proved a universal approximation theorem by iteratively applying the Stone-Weierstrass theorem, and a generalization theorem. Since our proofs are specific to GNNs with normalized sum aggregation, future research could provide extension of our theory to other aggregation functions. Another interesting direction could be to focus on extending the tree distance and tree homomorphism densities in Böker et al. () to graphon-signals. This presents a challenge as both metrics do not readily generalize to attributed graphons. Lastly, our theory is meaningful only for dense graphs, as sparse graphs are always considered close to the empty graph under our metrics. Future work may focus on deriving fine-grained expressivity analyses for sparse attributed graphs.

## 7 Ethics Statement

As this paper mainly focuses on theory, and uses only datasets that do not involve humans or animals, it does not present an apparent ethical problem.

## 8 Reproducibility Statement

We hereby declare that the proofs of all theorems presented in the article are available in the appendix. The code we used in this paper will be available upon the acceptence of this paper, with full explanation on how to perform all the experiments present in this article. This means that all the experiments presented both in the main article and the appendix could be reproduced.

## Appendix A Additional Background

### A.1 Weisfeiler Leman Graph Isomorphism Test

The Weisfeiler-Leman-$1$ (WL-$1$) test, which was developed by Boris Weisfeiler and Andrei Leman, also known as color refinement, is an algorithm which aimed to effectively approximate the solution of the graph isomorphism problem.As graph isomorphism problem is not known to be solvable in polynomial time, the algorithm cannot distinguish all non-isomorphic graphs.

Given a graph $G=(V,E)$ with initial labeling $L_{0}:V\mapsto\mathbb{N}$ (also referred to as coloring), composed of $V$, a the set of nodes and $E\subseteq V\times V$, a the set of edges, the WL-$1$ algorithm iteratively updates the nodes labels based on the labels of neighboring vertices.

###### Definition 8 (Weisfeiler-Leman Iteration) .

Given a graph $G=(V,E)$ with an initial labeling $L_{0}:V\to\mathbb{N}$, each iteration $t>0$ of the WL algorithm computes a new labeling $L_{t}$ as follows:

$$ $L_{t}(v)=\text{Hash}\left(L_{t-1}(v),\{\!\!\{L_{t-1}(u):u\in\mathcal{N}(v)\}\! \!\}\right)$ $$

where $\mathcal{N}(v)$ denotes the neighbors of vertex $v$, and Hash is an injective function mapping the previous label and multiset of neighbor labels to a new unique label.

This process runs on two graphs in parallel and continues on until a stable labeling of one of the two graphs is achieved, meaning that for some $t\in\mathbb{N}$ the label of one of the graphs doesn’t change, or a discrepancy is found between the label of the two graphs being compared. One of these two events is always reached.

###### Definition 8 (Weisfeiler-Leman Iteration) .

### A.2 Message Passing Neural Networks

Message Passing Neural Networks (MPNNs) Gilmer et al. [] are a neural networks class designed to process graph-structured data with and without attributes. Given a graph $G=(V,E)$, and a signal $\mathbf{f}:V\mapsto\mathbb{R}^{d}$ (in the case of a graph without attributes the signal is the constant function $\mathbf{f}(v)=1$, MPNNs iteratively update node embeddings through the exchange of messages between nodes through edges. We restate here Definition 4.
See 4
Let $\varphi$ be an $L$-layers MPNN model. Each node $v\in V$ starts with an initial feature vector $\mathfrak{g}(\varphi)_{v}^{(0)}=\mathbf{f}(v)$, which are updated iteratively through the the layer of the message passing model. Each layer consists of two main steps: aggregation and update.

At each layer $0<t\leq L$, each node $v$ aggregates information from its neighbors by:

$$ $\mathfrak{m}(\varphi,G,\mathbf{f})^{(t)}_{v}:=\text{Agg}\left(G,\mathfrak{g}( \varphi,G,\mathbf{f})_{-}^{(t-1)}\right),$ (2) $$

where Agg is a differentiable aggregation function. In this article we focus on
normalized sum aggregation which process on each layer the graph and its hidden node representations as follows, $Agg(G,\mathfrak{g}(\varphi,G,\mathbf{f})^{(t)}_{-})(v)=\frac{1}{|V|}\sum_{u\in
\mathcal{N}(v)}\mathfrak{g}(\varphi,G,\mathbf{f})^{(t)}_{u}$ where $\mathcal{N}(v)$ denotes the set of neighbors of node $v$.

The node embeddings are then updated based on the message $\mathfrak{m}(\varphi,G,\mathbf{f})^{(k)}_{v}$ and the node feutures from the privious layer $\mathfrak{g}(\varphi,G,\mathbf{f})_{v}^{(k-1)}$:

$$ $\mathfrak{g}(\varphi,G,\mathbf{f})_{v}^{(k)}=\varphi^{(k)}\left(\mathfrak{g}( \varphi,G,\mathbf{f})_{v}^{(k-1)},\mathfrak{m}(\varphi,G,\mathbf{f})^{(k)}_{v} \right),$ (3) $$

where $\varphi^{(k)}$ is called the update function which is a learnable Lipschitz function like an MLP (Multi-Layer Perceptron). After $L$ layers, the last layer’s hidden node representations $\mathfrak{g}(\varphi,G,\mathbf{f})_{-}^{(L)}$ are processed by an update layer. This layer is computed by applying a readout function $\psi:\mathbb{R}^{d_{L}}\mapsto\mathbb{R}^{d}$ and outputs a single graph-signal-level representation:

$$ $\mathfrak{G}(\varphi,\psi,G,\mathbf{f}):=\psi\left(\frac{1}{|V(G)|}\sum_{v\in V (G)}\mathfrak{g}(\varphi,G,\mathbf{f})_{v}^{(L)}\right)$ (4) $$

$\psi$ is typically a permutation-invariant function, that ensures the graph features is independent of any node ordering.

#### A.2.1 Graph Isomorphism Network (GIN)

Graph Isomorphism Network (GIN) Xu et al. [] is a popular MPNN model for graphs, which is as expressive as the Weisfeiler-Lehman graph isomorphism test. GIN is defined with sum aggregation but we use normalized sum aggregation. As an update function,it uses a multi layer preceptron (MLP) composed on addition of the massage $\mathfrak{m}(\varphi,G,\mathbf{f})^{(t)}_{-}:=\mathfrak{m}^{(t)}_{-}$ and $\mathfrak{g}(\varphi,G,\mathbf{f})^{(t-1)}_{-}:=\mathfrak{g}^{(t-1)}_{-}$ that depends on a contant $\epsilon$, that controls the weighting between the node’s own embedding and its neighbors’ embeddings, as follows:

$$ $\mathfrak{m}_{v}^{(t)}:=\frac{1}{|V|}\sum_{u\in\mathcal{N}(v)}\mathfrak{g}_{u} ^{(t-1)},$ (5) $$

$$ $\mathfrak{g}_{v}^{(t)}:=\text{MLP}^{(t)}\left((1+\epsilon)\mathfrak{g}_{v}^{(t -1)}+\mathbf{m}_{v}^{(t)}\right).$ (6) $$

The readout after $L$ layers (which we also normalize in contrast to the original definition) is:

$$ $\mathfrak{G}(\varphi,\psi,G,\mathbf{f}):=\mathfrak{G}:=\frac{1}{|V|}\sum_{v\in V }\mathfrak{g}_{v}^{(L)}.$ (7) $$

GIN’s ability to distinguish between non-isomorphic graphs makes it compatible for tasks, such as graph classification and node-level prediction.

### A.3 Topology Basics

Topology is a fundamental branch of mathematics, in which spatial properties that remain unchanged under continuous deformations are studied formally. Here, we introduce key concepts of topology.

###### Definition 9 (Topological Space) .

A topological space is a pair $(\mathcal{X},\tau)$, where $\mathcal{X}$ is a set and $\tau$ is a collection of subsets of $\mathcal{X}$ satisfying:

- 1.
Both $\emptyset$ and $\mathcal{X}$ are in $\tau$
- 2.
$\tau$ is closed under finite intersections
- 3.
$\tau$ is closed under arbitrary unions

The elements of $\tau$ are called open sets.

###### Definition 9 (Topological Space) .

#### A.3.1 Continuity

Continuity, in topology, generalizes the notion of continuity from calculus to any arbitrary topological space.

###### Definition 10 (Continuous Function) .

Given topological spaces $(\mathcal{X},\tau_{X})$ and $(\mathcal{Y},\tau_{Y})$, a function $f:\mathcal{X}\to\mathcal{Y}$ is continuous if the preimage of every open set in $\mathcal{Y}$ is open in $\mathcal{X}$. Formally, $f^{-1}(U)\in\tau_{X}$ for all $U\in\tau_{Y}$.

###### Definition 10 (Continuous Function) .

#### A.3.2 Product Topology

The product topology is a topology which is naturally defined on a Cartesian product topological spaces. Although it can be defined for Cartesian products of any number of spaces, in our analysis, we are only interested in the finite case.

Let $\{(\mathcal{X}_{i},\tau_{i})\}_{i\in I}$ be an finite set of topological spaces, then the product space of the set $\{(\mathcal{X}_{i},\tau_{i})\}_{i\in I}$ is denoted by $\prod_{i\in I}\mathcal{X}_{i}$ and defined as the set of all vectors $(x_{i})_{i\in I}$ where $x_{i}\in\mathcal{X}_{i}$ for each $i\in I$.
The product topology is then generated by the basis $\{(U_{i})_{i\in I}:U_{i}\in\tau_{i}\}.$

For each $i\in I$, the projection map $\pi_{i}:\prod_{j\in I}\mathcal{X}_{j}\to\mathcal{X}_{i}$ is defined by $\pi_{i}((x_{j})_{j\in I})=x_{i}$. In the product topology, all projection maps $\pi_{i}$ are continuous. Moreover, a sequence in the product space converges if and only if its projections onto each factor space converge.

#### A.3.3 Compactness and Separability

Compactness and separability are both important properties in topology.

###### Definition 11 (Compact Space) .

A topological space $(\mathcal{X},\tau)$ is compact if every open cover of $\mathcal{X}$ has a finite subcover.

###### Definition 12 (Separable Space) .

A topological space is separable if it contains a countable dense subset.

###### Theorem 8 (Tychonoff’s Theorem) .

Let $\{X_{i}\}_{i\in I}$ be a family of compact topological spaces. Then the product space
$\prod_{i\in I}X_{i}$
is compact in the product topology.

###### Definition 11 (Compact Space) .

###### Definition 12 (Separable Space) .

###### Theorem 8 (Tychonoff’s Theorem) .

#### A.3.4 Metric Spaces and Topology

A metric space is a topological space, where the topology is induced by a distance function called a metric.

###### Definition 13 (Metric Space) .

A metric space is a pair $(\mathcal{X},d)$ where $\mathcal{X}$ is a set and $d:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ is a function satisfying:

- 1.
$d(x,y)\geq 0$ for all $x,y\in\mathcal{X}$, with equality if and only if $x=y$
- 2.
$d(x,y)=d(y,x)$ for all $x,y\in\mathcal{X}$
- 3.
$d(x,z)\leq d(x,y)+d(y,z)$ for all $x,y,z\in\mathcal{X}$

The topology induced by a metric is generated by a base containing all open balls defined by $B(x,r)=\{y\in\mathcal{X}:d(x,y)<r\}$.

###### Definition 14 (Metrizable Space) .

A topological space $(X,\tau)$ is called *metrizable* if there exists a metric $d:X\times X\to\mathbb{R}$ such that the topology induced by the metric $d$ coincides with the topology $\tau$ on $X$.

In other words, the open sets in the topology $\tau$ are exactly the open sets with respect to the metric $d$.

###### Definition 13 (Metric Space) .

###### Definition 14 (Metrizable Space) .

#### A.3.5 Complete Metric Space

###### Definition 15 (Complete Metric Space) .

A metric space $(X,d)$ is called *complete* if every Cauchy sequence in $X$ converges to a point in $X$. A sequence $\{x_{n}\}\subset X$ is a *Cauchy sequence* if for every $\epsilon>0$, there exists an integer $N\in\mathbb{N}$ such that for all $m,n\geq N$, the following holds:

$$ $d(x_{n},x_{m})<\epsilon.$ (8) $$

In other words, if the elements of a sequence get arbitrarily close to each other as the sequence progresses, then that sequence also converges to a point within the space. If a topological space is metrizable to a complete metric space, we say that it is *completely metrizable*.

###### Definition 15 (Complete Metric Space) .

#### A.3.6 Measure Spaces and Borel Sets

Measure theory generalizes and formalizes geometrical measures such as length, area, and volume as well as other notions, such as magnitude, mass, and probability of events.

###### Definition 16 ( $\sigma$ -algebra) .

Let $\mathcal{A}$ be a set. A collection $\mathcal{F}$ of subsets of $\mathcal{A}$ is called a *$\sigma$-algebra* if the following properties are satisfied:

- 1.
$\mathcal{A}\in\mathcal{F}$.
- 2.
$\mathcal{F}$ is closed under complement, i.e., if $\mathcal{A}\in\mathcal{F}$, then $X\setminus\mathcal{A}\in\mathcal{F}$,
- 3.
$\mathcal{F}$ is closed under countable unions, i.e., if $\{\mathcal{A}_{n}\}_{n=1}^{\infty}$ is a countable collection of sets in $\mathcal{F}$, then
$\bigcup_{n=1}^{\infty}\mathcal{A}_{n}\in\mathcal{F}.$
(9)

The pair $(\mathcal{A},\mathcal{F})$ is called a *measurable space*.

A $\sigma$-algebra provides the foundation for the construction of measures,

###### Definition 17 (Measure) .

Let $(\mathcal{A},\mathcal{F})$ be a measurable space, where $\mathcal{A}$ is a set and $\mathcal{F}$ is a $\sigma$-algebra on $\mathcal{A}$. A function $\mu:\mathcal{F}\to[0,\infty]$ is called a *measure* if it satisfies the following properties:

- 1.
*Non-negativity*: For all $A\in\mathcal{F}$, $\mu(A)\geq 0$.
- 2.
*Null empty set*: $\mu(\emptyset)=0$.
- 3.
*Countable additivity (or $\sigma$-additivity)*: For any countable collection of pairwise disjoint sets $\{\mathcal{A}_{n}\}_{n=1}^{\infty}\subset\mathcal{F}$, the measure of their union is the sum of their measures:
$\mu\left(\bigcup_{n=1}^{\infty}\mathcal{A}_{n}\right)=\sum_{n=1}^{\infty}\mu(
\mathcal{A}_{n}).$
(10)

A measure $\mu$ assigns a non-negative extended real number to each set in the $\sigma$-algebra $\mathcal{F}$. The triple $(X,\mathcal{F},\mu)$ is called a *measure space*.

###### Definition 16 ( σ 𝜎 \sigma italic_σ -algebra) .

###### Definition 17 (Measure) .

#### A.3.7 Polish Spaces

Polish spaces are topological spaces, that have a ”nice” topology in the following way.

###### Definition 18 (Polish Space) .

A topological space is Polish if it is separable and completely metrizable, i.e., there exists a complete metric that generates its topology.

###### Definition 18 (Polish Space) .

### A.4 Stone–Weierstrass Theorem

We present a variation of the Stone-Weierstass Theorem (see [Rudin, , Theorem 7.32]) we use in Appendix F to prove a universal approximation theorem.

###### Theorem 9 (Real Stone–Weierstrass) .

Let $\mathcal{K}$ be a compact metric space and $A\subseteq C(\mathcal{K},\mathbb{R})$ be a sub-algebra that contains $1_{\mathcal{K}}$ and separates points, i.e., for every $k\neq l\in\mathcal{K}$ there is $f\in A$ such that $f(k)\neq f(l)$. Then $A$ is uniformly dense in $C(\mathcal{K},\mathbb{R})$.

The following corollary (taken from Grebík and Rocha []) is another useful description of the Stone-Weierstrass theorem, and is used as well in the universal approximation proof in Appendix F.

###### Corollary 2 (Separating Measures) .

Let $\mathcal{K}$ be a compact metric space and $\mathcal{E}\subseteq C(\mathcal{K},\mathbb{R})$ be closed under multiplication, contain $1_{\mathcal{K}}$, and separate points. Then for every $\mu\neq\nu\in\mathscr{M}_{\leq 1}(\mathcal{K})$ there is $f\in\mathcal{E}$ such that

$$ $\int_{\mathcal{K}}fd\mu\neq\int_{\mathcal{K}}fd\nu$ $$

i.e., the linear functionals that correspond to elements of $\mathcal{E}$ separate points in $\mathcal{M}_{\leq 1}(\mathcal{K})$.

###### Theorem 9 (Real Stone–Weierstrass) .

###### Corollary 2 (Separating Measures) .

### A.5 The cut distance

The *cut distance* was introduced by Frieze and Kannan [] and provides the central notion of convergence in the theory of dense graph limits. Here we define the cut distance on graphons although it can be extended to a more general objects.

###### Definition 19 .

Let $W$ be a graphon, its *cut norm* is defined as:

$$ $\|W\|_{\square}:=\sup_{A,B\in[0,1]}\left|\int_{A\times B}W(x,y)\,dxdy\right|$ $$

Built upon this, the *cut distance* between two graphons is defined as:

###### Definition 20 .

Let $U$, $V$ be graphons, the cut distance is between $U$, $V$ is

$$ $\delta_{\square}(U,V):=\inf_{\sigma\in\mathcal{S}_{[0,1]}}\|U^{\sigma}-V\|_{\square}$ $$

where $\mathcal{S}_{[0,1]}$ is the space of measure preserving bijections from the interval $[0,1]$ to itself and $U^{\sigma}(x,y):=U(\sigma(x),\sigma(y))$.

###### Definition 19 .

###### Definition 20 .

### A.6 Weighed Product Metric

We say that a product metric is weighed if there is a vector of weights $\vec{w}=\{w_{i}\}^{n}_{i=1}$ with positive entries ($w_{i}>0$) such that

$$ $d_{1}((x_{1},\ldots,x_{n}),(y_{1},\ldots,y_{n})):=\|(w_{1}\cdot d_{X_{1}}(x_{1 },y_{1}),\ldots,w_{n}\cdot d_{X_{n}}(x_{n},y_{n}))\|_{1}.$ $$

## Appendix B Basic Metric Properties

### B.1 The Weak* Topology

Let $L\in\mathbb{N}$. we motivate the need to prove that $d_{\rm IDM}^{L}$ and $\mathbf{OT}_{d_{\rm IDM}^{L}}$
are well-defined, by the fact that the measures in $\mathcal{M}^{L}=\mathscr{M}_{\leq 1}(\mathcal{H}^{L})=\mathscr{M}_{\leq 1}(
\mathcal{H}^{L},\mathcal{B}(\mathcal{H}^{L}))$ (and $\mathscr{P}(\mathcal{H}^{L})=\mathscr{P}(\mathcal{H}^{L},\mathcal{B}(\mathcal{
H}^{L}))$) are defined as functions $\mu:\mathcal{B}(\mathcal{H}^{L})\to\mathbb{R}$. But for any topological space $\mathcal{X}$, its $\sigma$-algebra $\mathcal{B}(\mathcal{X})$ depends on the topology of $\mathcal{X}$. In the case of $\mathcal{H}^{L}$, the topology is the product topology, when $\mathcal{M}^{i}$, for $i\in[L]$ has the weak* topology, which makes it crucial for $\mathbf{OT}_{d_{\rm IDM}^{i}}$ to metrize the weak*
topology on $\mathscr{M}_{\leq 1}(\mathcal{H}^{L})$ and $\mathscr{P}(\mathcal{H}^{L})$; otherwise the sets $\mathscr{M}_{\leq 1}(\mathcal{H}^{L},\mathcal{B}(\mathcal{H}^{L}))$ and $\mathscr{M}_{\leq 1}(\mathcal{H}^{L},d_{\rm IDM}^{L})$ might be two different sets.

The well definiteness of the metric $d_{\rm IDM}^{L}$ on $\mathcal{H}^{L}$
and $\mathbf{OT}_{d_{\rm IDM}^{L}}$ on $\mathscr{P}(\mathcal{H}^{L})$ follow similar arguments used in Böker et al. []. Let $(\mathcal{X},d)$ be a complete separable metric space. Böker et al. [] showed that the unbalaced optimal transport, as we define it (see Definition 1) is indead a metric on $\mathscr{M}_{\leq 1}(S)$ by following the proof of Pele and Werman [].

Moreover, they show that metrizes the weak* topology of $\mathscr{M}_{\leq 1}(S)$ by proving inequalities that are known to hold for probability measures, to measures with total mass smaller then one. they follow proofs
outlined in Schay [] and García-Palomares and Giné [], which use the duality of linear programming.

###### Lemma 1 .

Let $(\mathcal{X},d)$ be a complete separable metric space with Borel $\sigma$-algebra $\mathcal{B}$. Then $\mathbf{OT}_{d}$ is well defined and metrizes the weak* topology of $\mathscr{M}_{\leq 1}(\mathcal{X})$ and $\mathscr{P}(\mathcal{X})$.

We can now follow the proof of Lemma 24. in Böker et al. [] and prove Theorem 2.
See 2

###### Proof.

We start with the fact that $(\mathcal{H}^{0},d_{\rm IDM}^{0})=(\mathcal{K}^{p},\left\|\cdot\right\|_{2})$ and therefore $d_{\rm IDM}^{0}$ is well defined. As $\mathcal{K}^{p}$ is a complete separable metric space (a compact sub space of $\mathbb{R}^{p}$), by Lemma 1,
convergence in $\mathbf{OT}_{d_{\rm IDM}^{0}}$ is equivalent to weak* convergence on $\mathscr{M}_{\leq 1}(\mathcal{H}^{0},d_{\rm IDM}^{0})$ and $\mathscr{P}(\mathcal{H}^{0},d_{\rm IDM}^{0})$ which is just weak* convergence on $\mathscr{M}_{\leq 1}(\mathcal{H}^{0},\mathcal{B}(\mathcal{H}^{0}))$ and $\mathscr{P}(\mathcal{H}^{0},\mathcal{B}(\mathcal{H}^{0}))$, respectively. Hence, the topology induced by $\mathbf{OT}_{d_{\rm IDM}^{0}}$ is equal to the weak* topology on $\mathscr{M}_{\leq 1}(\mathcal{H}^{0},\mathcal{B}(\mathcal{H}^{0}))$ and $\mathscr{P}(\mathcal{H}^{0},\mathcal{B}(\mathcal{H}^{0}))$ as both spaces are metrizable.
The induction step follows the same arguments with the additional claim that $d_{\rm IDM}^{L}$ is a product metric, which metrizes the product topology.
∎

###### Lemma 1 .

###### Proof.

### B.2 Compactness

Let $\mathcal{K}$ be a compact space. A well-established result [Kechris, , Section 17] in measure theory states that the space, $\mathscr{M}_{\leq 1}(\mathcal{K})$, is equivalent to the set of non-negative Radon measures of total mass at most $1$. The Riesz Representation Theorem [Rudin, , Theorem 6.19] establishes that these measures correspond precisely to the non-negative linear functionals with norm at most 1 in the dual space of continuous real-valued functions on $\mathcal{K}$, $C(\mathcal{K},\mathbb{R})$.
The weak* topology on $\mathscr{M}_{\leq 1}(\mathcal{K})$ is defined as the minimal topology that ensures continuity of the mappings:

$$ $\int_{\mathcal{K}}fd\nu_{n}\mapsto\int_{\mathcal{K}}fd\nu$ $$

for all continuous real-valued functions $f$ on $\mathcal{\mathcal{K}}$. A fundamental result asserts that $\mathscr{M}_{\leq 1}(\mathcal{K})$, when endowed with the weak* topology, forms a compact metrizable space. Moreover, the Borel $\sigma$-algebra generated by this weak* topology is identical to the conventional Borel structure on $\mathscr{M}_{\leq 1}(\mathcal{K})$ induced by the mappings:

$$ $\mathcal{A}\mapsto\nu(\mathcal{A}),\quad\mathcal{A}\in\mathcal{B}(\mathcal{K})$ $$

where $\mathcal{B}(\mathcal{K})$ denotes the Borel sets of $\mathcal{K}$ [Kechris, , Section 17].

See 1

###### Proof.

Recall that $\mathcal{H}^{0}=(\mathcal{K}^{p},\left\|\cdot\right\|)$ is a compact metric space. As unbalanced optimal transport metrizes the weak* topology on $\mathscr{M}_{\leq 1}(\mathcal{H}^{0})$ and $\mathscr{P}(\mathcal{H}^{0})$, they are both compact spaces. For the induction step, let $L\in\mathbb{N}$ and presume the statment is true for $i\in[L-1]$. Tychonoff’s theorem (see Theorem 8) states that the product of any collection of compact topological spaces is compact with respect to the product topology, which leads $(\mathcal{H}^{t},d_{\rm IDM}^{L})$ to be compact. We can therefore use the same argument as in the induction space and get that $\mathscr{M}_{\leq 1}(\mathcal{H}^{L})$ nad $\mathscr{P}(\mathcal{H}^{L})$ with the topology induced by $\mathbf{OT}_{d_{\rm IDM}^{L}}$ are both compact.
∎

###### Proof.

## Appendix C Computability

We first prove Proposition 4.5 [Schmitzer and Schnörr, ],by follows the steps in the original proof, for our own setting. We emphasize that in Proposition 1, $\Gamma$ and $\gamma$ do not refer to Definition 2.

###### Proposition 1 .

For two discrete sets $\mathcal{A}$, $\mathcal{C}$ and two measurable maps $\phi_{a}:\mathcal{X}\rightarrow\mathcal{A}$, $\phi_{b}:\mathcal{Y}\rightarrow\mathcal{C}$ denote by $\phi$ the product map $\phi(x,y)=(\phi_{a}(x),\phi_{b}(y))$. Then one finds

$$ $\phi_{*}\Gamma(\mu,\nu)=\Gamma({\phi_{a}}_{*}\mu,{\phi_{b}}_{*}\nu)$ $$

when $\phi_{*}\Gamma(\mu,\nu):=\{\gamma:\gamma=\phi_{*}\gamma^{\prime}:\gamma^{
\prime}\in\Gamma(\mu,\nu)\}.$

###### Proof.

Assume $\left\|\mu\right\|\leq\left\|\nu\right\|$. For any $\gamma\in\Gamma(\mu,\nu)$ we get

$$ $\displaystyle(\phi_{*}\gamma)(\mathcal{S})$ $\displaystyle=\gamma(\phi^{-1}(\mathcal{S}))\geq 0.$ $$

when $\mathcal{S}\subseteq\mathcal{A}\times\mathcal{C}$ a measurable subset, and

$$ $\displaystyle(\phi)_{*}\gamma(\mathcal{S}_{\mathcal{A}}\times\mathcal{C})$ $\displaystyle=\gamma(\phi_{a}^{-1}(\mathcal{S}_{\mathcal{A}})\times\mathcal{X} )=(p_{1})_{*}\gamma(\phi_{a}^{-1}(\mathcal{S}_{\mathcal{A}}))$ $\displaystyle=\mu(\phi_{a}^{-1}(\mathcal{S}_{\mathcal{A}}))=(\phi_{a})_{*}\mu( \mathcal{S}_{\mathcal{A}})$ $$

when $\mathcal{S}_{\mathcal{A}}\subseteq\mathcal{A}$ a measurable subset
and analogous for $\mathcal{S}_{\mathcal{C}}\subseteq\mathcal{C}$ a measurable subset

$$ $\displaystyle(\phi)_{*}\gamma(\mathcal{A}\times\mathcal{S}_{\mathcal{C}})$ $\displaystyle=\gamma(\mathcal{X}\times\phi_{b}(\mathcal{S}_{\mathcal{C}})=(p_{ 1})_{*}\gamma(\phi_{a}^{-1}(\mathcal{S}_{\mathcal{C}}))$ $\displaystyle\leq\nu(\phi_{a}^{-1}(\mathcal{S}_{\mathcal{C}}))=(\phi_{a})_{*} \nu(\mathcal{S}_{\mathcal{C}}).$ $$

Thus $(\phi)_{*}\Gamma(\mu,\nu)\subseteq\Gamma((\phi_{a})_{*}\mu,(\phi_{b})_{*}\nu)$.

We now show by construction for any $\rho\in\Gamma({\phi_{a}}_{*}\mu,{\phi_{b}}_{*}\nu)$ the existence of some $\gamma\in\Gamma(\mu,\nu)$ such that $\rho=(\phi)_{*}\gamma$. For any
element $(a,c)\in\mathcal{A}\times\mathcal{C}$ construct the pre-image measure

$$ $\gamma_{(a,c)}(x,y)=\begin{cases}0&\text{if }\rho(a,c)=0\vee(a,c)\neq\phi(x,y) \\ \frac{\mu(x)\nu(y)}{((\phi_{a})_{*}\mu)(a)((\phi_{b})_{*}\nu)(c)}\rho(a,c)& \text{else}\end{cases}$ $$

where this element wise definition for each $(x,y)$ is extended to all subsets of $\mathcal{X}\times\mathcal{Y}$ by

$$ $\gamma_{(a,c)}(\mathcal{S})=\sum_{(x,y)\in\mathcal{S}}\gamma_{(a,c)}(x,y)$ $$

when $\mathcal{S}$ is any measurable subset of $\mathcal{X}\times\mathcal{Y}$. Now consider $\gamma=\sum_{(a,c)\in\mathcal{A}\times\mathcal{C}}\gamma_{(a,c)}$. First verify that it is indeed contained in
$\Gamma(\mu,\nu)$:

$$ $\gamma(\mathcal{S})\geq 0:\forall\text{ measurable }\mathcal{S}\subseteq \mathcal{X}\times\mathcal{Y}.$ $$

since $\gamma(x,y)\geq 0$ for all $(x,y)$. Furthermore

$$ $\displaystyle\gamma(\mathcal{S}_{\mathcal{X}}\times\mathcal{Y})$ $\displaystyle=\sum_{\begin{subarray}{c}x\in\mathcal{S}_{\mathcal{X}}\\ y\in\mathcal{Y}\end{subarray}}\sum_{\begin{subarray}{c}\\ (a,c)\in\mathcal{A}\times\mathcal{C}:\\ \phi(x,y)=(a,c),\\ \rho(a,c)>0\end{subarray}}\frac{\mu(x)\nu(y)}{((\phi_{a})_{*}\mu)(a)((\phi_{b} )_{*}\nu)(c)}\rho(a,c)$ $\displaystyle=\sum_{x\in\mathcal{S}_{\mathcal{X}}}\sum_{\begin{subarray}{c}c \in\mathcal{C}:\\ \rho(\phi_{a}(x),c)>0\end{subarray}}\frac{\mu(x)(\sum_{y:\phi_{b}(y)=c}\nu(y)) }{((\phi_{a})_{*}\mu)(\phi_{a}(x))((\phi_{b})_{*}\nu)(c)}\rho(\phi_{a}(x),c)$ $\displaystyle=\sum_{x\in\mathcal{S}_{\mathcal{X}}}\sum_{\begin{subarray}{c}c \in\mathcal{C}:\\ \rho(\phi_{a}(x),c)>0\end{subarray}}\frac{\mu(x)\nu(\phi_{b}^{-1}(c))}{((\phi_ {a})_{*}\mu)(\phi_{a}(x))((\phi_{b})_{*}\nu)(c)}\rho(\phi_{a}(x),c)$ $\displaystyle=\sum_{x\in\mathcal{S}_{\mathcal{X}}}\frac{\mu(x)}{((\phi_{a})_{* }\mu)(\phi_{a}(x))}\sum_{\begin{subarray}{c}c\in\mathcal{C}:\\ \rho(\phi_{a}(x),c)>0\end{subarray}}\rho(\phi_{a}(x),c)$ $\displaystyle=\sum_{x\in\mathcal{S}_{\mathcal{X}}}\frac{\mu(x)}{((\phi_{a})_{* }\mu)(\phi_{a}(x))}(p_{1})_{*}\rho(\phi_{a}(x))$ $\displaystyle=\sum_{x\in\mathcal{S}_{\mathcal{X}}}\frac{\mu(x)}{((\phi_{a})_{* }\mu)(\phi_{a}(x))}(\phi_{a})_{*}\mu(\phi_{a}(x))=\sum_{x\in\mathcal{S}_{ \mathcal{X}}}\mu(x)=\mu(\mathcal{S}_{\mathcal{X}})$ $$

for all measurable subsets $\mathcal{S}_{\mathcal{X}}\subseteq\mathcal{X}$ and likewise
$\gamma(X\times\mathcal{S}_{\mathcal{Y}})\leq\nu(\mathcal{S}_{\mathcal{Y}}).$

$$ $\displaystyle\gamma(\mathcal{X}\times\mathcal{S}_{\mathcal{Y}})$ $\displaystyle=\sum_{\begin{subarray}{c}y\in\mathcal{S}_{\mathcal{Y}}\\ x\in\mathcal{X}\end{subarray}}\sum_{\begin{subarray}{c}(a,c)\in\mathcal{A} \times\mathcal{C}:\\ \phi(x,y)=(a,c),\\ \rho(a,c)>0\end{subarray}}\frac{\mu(x)\nu(y)}{((\phi_{a})_{*}\mu)(a)((\phi_{b} )_{*}\nu)(c)}\rho(a,c)$ $\displaystyle=\sum_{y\in\mathcal{S}_{\mathcal{Y}}}\sum_{\begin{subarray}{c}a \in\mathcal{A}:\\ \rho(a,\phi_{b}(y))>0\end{subarray}}\frac{(\sum_{x:\phi_{b}(x)=a}\mu(x))\nu(y) }{((\phi_{a})_{*}\mu)(a)((\phi_{b})_{*}\nu)(\phi_{b}(y))}\rho(\phi_{a}(x),c)$ $\displaystyle=\sum_{y\in\mathcal{S}_{\mathcal{Y}}}\sum_{\begin{subarray}{c}a \in\mathcal{A}:\\ \rho(a,\phi_{b}(y))>0\end{subarray}}\frac{\mu(\phi_{a}^{-1}(a))\nu(y)}{((\phi_ {a})_{*}\mu)(a)((\phi_{b})_{*}\nu)(\phi_{b}(y))}\rho(a,\phi_{b}(y))$ $\displaystyle=\sum_{y\in\mathcal{S}_{\mathcal{Y}}}\frac{\nu(y)}{((\phi_{b})_{* }\nu)(\phi_{b}(y))}\sum_{\begin{subarray}{c}a\in\mathcal{A}:\\ \rho(a,\phi_{b}(y))>0\end{subarray}}\rho(a,\phi_{b}(y))$ $\displaystyle=\sum_{y\in\mathcal{S}_{\mathcal{Y}}}\frac{\nu(x)}{((\phi_{b})_{* }\nu)(\phi_{b}(y))}(p_{2})_{*}\rho(\phi_{a}(y))$ $\displaystyle\leq\sum_{y\in\mathcal{S}_{\mathcal{Y}}}\frac{\nu(y)}{((\phi_{b}) _{*}\nu)(\phi_{b}(y))}((\phi_{b})_{*}\nu)(\phi_{b}(y))=\sum_{y\in\mathcal{S}_{ \mathcal{Y}}}\nu(x)=\nu(\mathcal{S}_{\mathcal{A}})$ $$

for all measurable subsets $\mathcal{S}_{\mathcal{Y}}\subseteq\mathcal{Y}$.
Now check whether $\phi_{*}\gamma=\rho$:

$$ $\displaystyle(\phi)_{*}\gamma(\mathcal{S})$ $\displaystyle=\gamma(\phi^{-1}(\mathcal{S}))=\sum_{(x,y)\in\phi^{-1}(\mathcal{ S})}\gamma(x,y)$ $\displaystyle=\sum_{\begin{subarray}{c}(x,y)\in\phi^{-1}(\mathcal{S}):\\ \rho(\phi(x,y))>0\end{subarray}}\frac{\mu(x)\nu(y)}{((\phi_{a})_{*}\mu)(\phi_{ a}(x))((\phi_{b})_{*}\nu)(\phi_{b}(y))}\rho(\phi(x,y))$ $\displaystyle=\sum_{\begin{subarray}{c}(a,c)\in\mathcal{S}\\ \rho((a,c))>0\end{subarray}}\sum_{(x,y)\in\phi^{-1}((a,c))}\frac{\mu(x)\nu(y)} {((\phi_{a})_{*}\mu)(a)((\phi_{b})_{*}\nu)(c)}\rho(a,c)$ $\displaystyle=\sum_{\begin{subarray}{c}(a,c)\in\mathcal{S}\\ \rho((a,c))>0\end{subarray}}\frac{(\sum_{x\in\phi_{a}^{-1}(a)}\mu(x))(\sum_{y \in\phi_{b}^{-1}(c)}\nu(y))}{((\phi_{a})_{*}\mu)(a)((\phi_{b})_{*}\nu)(c)}\rho (a,c)$ $\displaystyle=\sum_{\begin{subarray}{c}(a,c)\in\mathcal{S}\\ \rho((a,c))>0\end{subarray}}\rho(a,c)=\rho(\mathcal{S})$ $$

when $\mathcal{S}$ is a measurable subset of $\mathcal{X}\times\mathcal{Y}$. Consequently any $\rho\in\Gamma((\phi_{a})_{*}\mu,(\phi_{b})_{*}\nu)$ is also contained in $\phi_{*}\Gamma(\mu,\nu)$ and the two sets are equal.
∎

Lemma A.1 [Chen et al., ] is now easly proven for the space $\mathscr{M}_{\leq 1}(\mathcal{Z})$ where $\mathcal{Z}$ is a complete separable space with proposition 1. Although the proof is equivalent to the one in Chen et al. [], we will add it here for completeness.

###### Lemma 2 .

Let $\mathcal{X},\mathcal{Y}$ be finite metric spaces and let $(\mathcal{Z},d_{\mathcal{Z}})$ be a complete and separable metric space. Let $\phi_{\mathcal{X}}:\mathcal{X}\to\mathcal{Z}$ and $\phi_{\mathcal{Y}}:\mathcal{Y}\to\mathcal{Z}$ be measurable maps. Consider any $\mu_{\mathcal{X}}\in\mathcal{M}_{\leq 1}(\mathcal{X})$ and $\mu_{\mathcal{Y}}\in\mathcal{M}_{\leq 1}(\mathcal{Y})$. Then, we have that

$$ $\mathbf{OT}_{d}((\phi_{\mathcal{X}})_{*}\mu_{\mathcal{X}},(\phi_{\mathcal{Y}}) _{*}\mu_{\mathcal{Y}})=\inf_{\gamma\in\Gamma(\mu_{\mathcal{X}},\mu_{\mathcal{Y }})}\int_{\mathcal{X}\times\mathcal{Y}}d(\phi_{\mathcal{X}}(x),\phi_{\mathcal{ Y}}(y))\gamma(dx\times dy).$ $$

###### Proof.

Since $\mathcal{X}$ and $\mathcal{Y}$ are finite, $\phi_{\mathcal{X}}(\mathcal{X})$ and $\phi_{\mathcal{Y}}(\mathcal{Y})$ are discrete sets. Then, if we let $\phi:=\phi_{\mathcal{X}}\times\phi_{\mathcal{Y}}$,

$$ $(\phi)_{*}\Gamma(\mu_{\mathcal{X}},\mu_{\mathcal{Y}})=\Gamma((\phi_{\mathcal{Y }})_{*}\mu_{\mathcal{X}}.(\phi_{\mathcal{Y}})_{*}\mu_{\mathcal{Y}})$ $$

follows directly from Proposition 1. Hence,

$$ $\displaystyle\mathbf{OT}_{d}((\phi_{\mathcal{X}})_{*}\mu_{\mathcal{X}},(\phi_{ \mathcal{Y}})_{*}\mu_{\mathcal{Y}})$ $\displaystyle=\inf_{\gamma\in\Gamma((\phi_{\mathcal{X}})_{*}\mu_{\mathcal{X}}, (\phi_{\mathcal{Y}})_{*}\mu_{\mathcal{Y}})}\int_{\mathcal{Z}\times\mathcal{Z}} d_{Z}(z_{1},z_{2})\gamma(dz_{1}\times dz_{2})$ $\displaystyle=\inf_{\gamma\in\Gamma(\mu,\nu)}\int_{\mathcal{Z}\times\mathcal{Z }}d_{\mathcal{Z}}(z_{1},z_{2})\phi_{*}\gamma(dz_{1}\times dz_{2})$ $\displaystyle=\inf_{\gamma\in\Gamma(\mu,\nu)}\int_{\mathcal{X}\times\mathcal{Y }}d_{\mathcal{Z}}(\phi_{\mathcal{X}}(x),\phi_{\mathcal{Y}}(y))\gamma(dx\times dy).$ $$

∎

Now, based on the algorithm used to compute the Weisfeiler-Lehman metric in Chen et al. [], we phrase a similar algorithm for computing $\delta_{\rm DIDM}^{L}$ for $L\in\mathbb{N}$. We note that instead of using a min-cost-flow algorithm Pele and Werman [] to solve the unbalanced optimal transport problem, we use linear programming Flamary et al. [] as it is more convenient when working with real values (instead of integers). The unbalaced optimal transport problem can casted into a regular OT problem by adding reservoir points in which the surplus mass is sent Chapel et al. []
See 3

###### Proof.

From Lemma 2 we have that

$$ $\displaystyle\delta_{\rm DIDM}^{L}((G,\mathbf{f}),(H,\mathbf{g}))$ $\displaystyle:=\mathbf{OT}\left(\Gamma_{(G,\mathbf{f}),L},\Gamma_{(H,\mathbf{g }),L}\right)=\mathbf{OT}\left(\left(\gamma_{(G,\mathbf{f}),L}\right)_{*} \lambda_{V(G)},\left(\gamma_{(H,\mathbf{g}),L}\right)_{*}\lambda_{V(H)}\right)$ $\displaystyle=\inf_{\gamma\in\Gamma(\lambda_{V(G)},\lambda_{V(H)})}\int_{V(G) \times V(H)}d_{\rm IDM}^{L}\left(\gamma_{(G,\mathbf{f}),L}(x),\gamma_{(H, \mathbf{g}),L}(y)\right)\gamma(dx\times dy).$ $$

In order to compute $\delta_{\rm DIDM}^{L}((G,\mathbf{f}),(H,\mathbf{g}))$, we must first compute
$d_{\rm IDM}^{L}\left(\gamma_{(G,\mathbf{f}),L}(x),\gamma_{(H,\mathbf{g}),L}(y)\right)$ for each $x\in V(G)$ and $y\in V(H)$. To do this, we introduce some notation. For each $i=1,\ldots,L$, we let $C_{i}$, $D_{i}$ denote the $|V(G)|\times|V(H)|$ matrices such that for each $x\in V(G)$ and $y\in V(H)$,

$$ $\displaystyle C_{i}(x,y):=d_{\rm IDM}^{i}\left(\gamma_{(G,\mathbf{f}),i}(x), \gamma_{(H,\mathbf{g}),i}(y)\right),D_{i}(x,y):=\mathbf{OT}^{i}\left(\gamma_{( G,\mathbf{f}),i}(x)(i),\gamma_{(H,\mathbf{g}),i}(y)(i)\right).$ $$

We also let $C_{0}$ denote the matrix such that $C_{0}(x,y):=\|\mathbf{f}(x)-\mathbf{g}(y)\|$ for each $x\in V(G)$ and $y\in V(H)$. Then, our task is to compute the matrix $C_{L}$. For this purpose, we consecutively compute the matrices $C_{i}$ and $D_{i}$ for $i=1,\ldots,L$. Given matrix $C_{i-1}$, since $\gamma_{(G,\mathbf{f}),i}(x)(i)=\left(\gamma_{(G,\mathbf{f}),i-1}(x)\right)_{*
}\nu_{(G,\mathbf{f})}$ and $\gamma_{(H,\mathbf{g}),i}(y)(i)=\left(\gamma_{(H,\mathbf{g}),i-1}(y)\right)_{*
}\nu_{(H,\mathbf{g})}$, computing

$$ $\displaystyle\mathbf{OT}^{i}$ $\displaystyle\left(\gamma_{(G,\mathbf{f}),i}(x)(i),\gamma_{(H,\mathbf{g}),i}(y )(i)\right)$ $\displaystyle=\inf_{\gamma\in\Gamma(\nu_{(G,\mathbf{f})},\nu_{(H,\mathbf{g})}) }\int_{V(G)\times V(H)}d_{\rm IDM}^{i-1}\left(\gamma_{(G,\mathbf{f}),i-1}(x), \gamma_{(H,\mathbf{g}),i-1}(y)\right)\gamma(dx\times dy).$ $$

is reduced to solving the optimal transport problem with $C_{i-1}$ as the cost matrix and $\nu_{(G,\mathbf{f})}$ and $\nu_{(H,\mathbf{g})}$ as the source and target distributions, which can be done in $O(N^{3}\log(N))$ time [Flamary et al., , Chapel et al., ]. Thus, for each $i$, computing $D_{i}$ given that we know $C_{i-1}$ requires $O(N^{2}\cdot N^{3}\log(N))$. To get $C_{i}$, all that remains is to compute the sum $D_{i}+C_{i-1}$. Finally, we need $O(N^{3}\log(N))$ time to compute $\delta_{\rm DIDM}^{L}((G,\mathbf{f}),(H,\mathbf{g}))$ based on solving an optimal transport problem with cost matrix $C_{L}$ and with $\lambda_{V(G)}$ and $\lambda_{V(H)}$ being the source and target distributions.

Therefore, the total time needed to compute $\delta_{\rm DIDM}^{L}((G,\mathbf{f}),(H,\mathbf{g}))$ is

$$ $L\cdot O(N^{5}\log(N))+O(N^{3}\log(N))=O(L\cdot N^{5}\log(N)).$ $$

For any $N\in\mathbb{N}$, $\delta_{\rm DIDM}^{L}$ generates a distance between two graph-signls with number of vertices bounded by $N$.
∎

###### Proposition 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

###### Proof.

## Appendix D MPNN Features Equivalency

Here, we show that, first, for a graph-signal $(G,\mathbf{f})$, the output of an MPNN on $G$ equals the output of the MPNN on the corresponding graphon-signal $(W_{G},f_{\mathbf{f}})$ similarly as done in Appendix C.1 of Böker et al. [].

###### Theorem 10 .

Let $(G,\mathbf{f})$ be a graph-signal and $\varphi$ be an $L$-layer MPNN model. Let $(I_{v})_{v\in V(G)}$ be the partition of $[0,1]$ used in the construction of $(W_{G},f_{\mathbf{f}})$ from $(G,\mathbf{f})$. Then, for all $t\in[L],v\in V(G)$, and $x\in I_{v}$,

$$ $\mathfrak{f}^{(t)}_{x}:=\mathfrak{f}(\varphi,W_{G},f_{\mathbf{f}})_{x}^{(t)}= \mathfrak{g}(\varphi,G,\mathbf{f})_{v}^{(t)}=:\mathfrak{g}_{v}^{(t)}.$ $$

###### Proof.

We prove the claim by induction on $t$.

Base of the induction. For all $v\in V(G)$ and $x\in I_{v}$,

$$ $\mathfrak{f}_{x}^{(0)}=\varphi^{(0)}\circ f_{\mathbf{f}}(x)=\varphi^{(0)}\circ \mathbf{f}(v)=\mathfrak{g}_{v}^{(0)}.$ $$

Induction step. The induction assumption is that $\mathfrak{f}_{x}^{(t-1)}=\mathfrak{g}_{v}^{(t-1)}$ for all $v\in V(G)$ and $x\in I_{v}$. Then, for all $v\in V(G)$ and $x\in I_{v}$, we have

$$ $\displaystyle\mathfrak{f}_{x}^{(t)}=\varphi^{(t)}\left(\mathfrak{f}_{x}^{(t-1) },\int_{[0,1]}W_{G}(x,y)\mathfrak{f}_{y}^{(t-1)}d\lambda(y)\right)$ $\displaystyle=\varphi^{(t)}\left(\mathfrak{f}_{x}^{(t-1)},\sum_{u\in V(G)}\int _{I_{u}}W_{G}(x,y)\mathfrak{f}_{y}^{(t-1)}d\lambda(y)\right)$ $\displaystyle=\varphi^{(t)}\left(\mathfrak{g}^{(t-1)}_{v},\sum_{u\in V(G)}\int _{I_{u}}W_{G}(x,y)\mathfrak{g}_{u}^{(t-1)}d\lambda(y)\right)$ $\displaystyle=\varphi^{(t)}\left(\mathfrak{g}_{v}^{(t-1)},\frac{1}{\left|V(G) \right|}\sum_{u\in\mathcal{N}(v)}\mathfrak{g}_{u}^{(t-1)}\right)=\mathfrak{g}_ {v}^{(t)}.$ $$

∎

###### Theorem 11 .

Let $(G,\mathbf{f})$ be a graph, let $(\varphi,\psi)$ be an $L$-layer MPNN model with readout. Let $(I_{v})_{v\in V(G)}$ be the partition of $[0,1]$ used in the construction $(W_{G},f_{\mathbf{f}})$ from $(G,\mathbf{f})$. Then,

$$ $\mathfrak{G}:=\mathfrak{G}(\varphi,\psi,G,\mathbf{f})=\mathfrak{F}(\varphi, \psi,W_{G},f_{\mathbf{f}})=:\mathfrak{F}.$ $$

###### Proof.

With Theorem 10, we get

$$ $\displaystyle\mathfrak{F}$ $\displaystyle=\psi\left(\int_{[0,1]}\mathfrak{f}_{x}^{(L)}d\lambda(x)\right)= \psi\left(\sum_{v\in V(G)}\int_{I_{v}}\mathfrak{f}_{x}^{(L)}d\lambda(x)\right)$ $\displaystyle=\psi\left(\sum_{v\in V(G)}\int_{I_{v}}\mathfrak{g}_{v}^{(L)}d \lambda(x)\right)$ $\displaystyle=\psi\left(\frac{1}{|V(G)|}\sum_{v\in V(G)}\mathfrak{g}_{v}^{(L)} \right)=\mathfrak{G}.$ $$

∎

Second, we show that the output of a MPNN on a graphon-signal $(W,f)$ equals the output of the
MPNN on the corresponding distribution
of computation IDMs $\Gamma_{(W,f)}$ of $(W,f)$.

###### Lemma 3 .

[Billingsley, , Theorem 16.11.]
Let $\delta:[0,1]\mapsto\mathbb{R}$ be a nonnegative measurable function. Define the measure $\nu_{\delta}$ by $\nu_{\delta}(A)=\int_{A}\delta\text{d}\lambda$ or measurable $A\subseteq[0,1]$. Then, a measurable
function $f:[0,1]\mapsto\mathbb{R}$ is integrable with respect to $\nu_{\delta}$ if and only if $f_{\delta}$ is integrable with respect to $\lambda$, in which case

$$ $\int_{A}fd\nu_{\delta}=\int_{A}f\delta\text{d}\lambda$ $$

holds for every measurable $A$.

###### Theorem 12 .

Let $(W,f)\in\mathcal{WS}$ and $\varphi$ be a $L$-layer MPNN model. Then, for every $t\in[L]$ and almost every $x\in[0,1]$,

$$ $\displaystyle\mathfrak{f}^{(t)}_{x}:=\mathfrak{f}(\varphi,W,f)^{(t)}_{x}= \mathfrak{h}^{(t)}(\varphi,\gamma_{(W,f),t}(x))=:\mathfrak{h}^{(t)}_{\gamma_{( W,f),t}(x)}.$ $$

###### Proof.

Induction Base. We have by definition

$$ $\mathfrak{f}^{(0)}_{x}=\varphi^{(0)}\circ f(x)=\mathfrak{h}^{(0)}_{\gamma_{(W, f),0}(x)}.$ $$

Induction Assumption. We assume that

$$ $\displaystyle\mathfrak{f}^{(t-1)}_{x}=\mathfrak{h}^{(t-1)}_{\gamma_{(W,f),t-1} .(x)}$ $$

for almost every $x\in[0,1]$ and $t>0$.

Induction Step. We have

$$ $\displaystyle\mathfrak{f}^{(t)}_{x}=\varphi^{(t)}\left(\mathfrak{f}_{x}^{(t-1) },\int_{[0,1]}W(x,y)\mathfrak{f}_{y}^{(t-1)}(x,y)\text{d}\lambda(y)\right)$ $$

Recall that for any $A\in\mathcal{B}(\mathcal{H}^{L})$,

$$ $(\gamma_{(W,f),t}(x)(t))(A)=\int_{\gamma_{(W,f),t-1}^{-1}(A)}W(x,y)\text{d} \lambda(y),$ $$

so, by the notation $\nu_{W(x,-)}$ introduced in Lemma 3,

$$ $\gamma_{(W,f),t}(x)(t)=(\gamma_{(W,f),t-1})_{*}\nu_{W(x,-)}.$ $$

Hence, by Lemma 3 with $\delta=W(x,-)$ and $f=\mathfrak{h}^{(t-1)}_{-}$, we have

$$ $\displaystyle\mathfrak{h}^{(t)}_{\gamma_{(W,f),t}(x)}$ $\displaystyle=\varphi^{(t)}(\mathfrak{h}^{(t-1)}_{p_{t,t-1}(\gamma_{(W,f),t})} ,\int_{\mathcal{H}^{t-1}}\mathfrak{h}_{-}^{(t-1)}dp_{t}(\gamma_{(W,f),t}(x)))$ $\displaystyle=\varphi^{(t)}(\mathfrak{h}^{(t-1)}_{\gamma_{(W,f),t-1}},\int_{ \mathcal{H}^{t-1}}\mathfrak{h}_{-}^{(t-1)}d\gamma_{(W,f),t}(x)(t))$ $\displaystyle=\varphi^{(t)}(\mathfrak{h}^{(t-1)}_{\gamma_{(W,f),t-1}},\int_{ \mathcal{H}^{(t-1)}}\mathfrak{h}_{-}^{(t-1)}d(\gamma_{(W,f),t-1})_{*}\nu_{(W,f )(x,-)})$ $\displaystyle=\varphi^{(t)}(\mathfrak{h}^{(t-1)}_{\gamma_{(W,f),t-1}},\int_{[0 ,1]}\mathfrak{h}_{-}^{(t-1)}\circ\gamma_{(W,f),t-1}(y)d\nu_{(W,f)(x,-)}(y))$ $\displaystyle=\varphi^{(t)}(\mathfrak{h}^{(t-1)}_{\gamma_{(W,f),t-1}},\int_{[0 ,1]}W(x,y)\mathfrak{h}^{(t-1)}_{\gamma_{(W,f),t-1}(y)}d\lambda(y))$ $$

Hence, by the induction assumption,

$$ $\displaystyle\mathfrak{f}^{(t)}_{x}=\mathfrak{h}^{(t)}_{\gamma_{(W,f),t}(x)}$ $$

∎

###### Theorem 13 .

Let $(W,f)\in\mathcal{WS}$, let $(\varphi,\psi)$ be an $L$-layer MPNN model with readout, then

$$ $\mathfrak{F}:=\mathfrak{F}(\varphi,\psi,W,f)=\mathfrak{H}(\varphi,\psi,\Gamma_ {(W,f),L})=:\mathfrak{H}$ $$

###### Proof.

Recall that for any $A\in\mathcal{B}(\mathscr{M}_{t-1})$,

$$ $\Gamma_{(W,f),L}(A)=\int_{\gamma^{-1}_{(W,f),L}(A)}\lambda(y).$ $$

So,

$$ $\Gamma_{(W,f),L}=(\gamma_{(W,f),L})_{*}\lambda.$ $$

Equality follows from the above remark and Theorem 12.

$$ $\displaystyle\mathfrak{H}$ $\displaystyle=\psi\left(\int_{\mathcal{H}^{L}}\mathfrak{h}^{(L)}_{-}d\Gamma_{( W,f),L}\right)$ $\displaystyle=\psi\left(\int_{\mathcal{H}^{L}}\mathfrak{h}^{(L)}_{-}\text{d}( \gamma_{(W,f),L})_{*}\lambda\right)$ $\displaystyle=\psi\left(\int_{[0,1]}\mathfrak{h}^{(L)}_{\gamma_{(W,f),L}(x)} \text{d}\lambda(x)\right)$ $\displaystyle=\psi\left(\int_{[0,1]}\mathfrak{f}^{(L)}_{x}\text{d}\lambda(x)\right)$ $\displaystyle=\mathfrak{F}.$ $$

∎

Hence, it suffices to consider MPNNs on DIDMs.

###### Theorem 10 .

###### Proof.

###### Theorem 11 .

###### Proof.

###### Lemma 3 .

###### Theorem 12 .

###### Proof.

###### Theorem 13 .

###### Proof.

## Appendix E MPNNs Lipschitz Constant

In this section, we prove that MPNNs are Lipschitz, following the proofs in Appendix C.2.5. Grebík and Rocha [].

###### Definition 21 .

Let $\mathcal{X}$, $\mathcal{Y}$ be two metric spaces. Let $\mathfrak{L}\in{\rm Lip}(\mathcal{X},\mathcal{Y})$, where ${\rm Lip}(\mathcal{X},\mathcal{Y})$ is the space of Lipschitz continuous mappings $\mathcal{X}\mapsto\mathcal{Y}.$
We define the function $\left\|\cdot\right\|_{\rm L}$ as follows,

$$ $\left\|\mathfrak{L}\right\|_{\rm L}=\min_{\rm L}\{L:\text{L is a Lipschitz constant of }\mathfrak{L}\}.$ $$

Note that $\left\|\cdot\right\|_{\rm L}$ is a seminorm over ${\rm Lip}(\mathcal{X},\mathcal{Y})$.

###### Definition 22 .

Let $\mathcal{X}$, $\mathcal{Y}$ be two metric spaces. Let $\mathfrak{L}\in{\rm Lip}(\mathcal{X},\mathcal{Y})$, where ${\rm Lip}(\mathcal{X},\mathcal{Y})$ is the space of Lipschitz continuous mappings $\mathcal{X}\mapsto\mathcal{Y}.$ We define the $\ell_{\infty}$-norm over $Lip(\mathcal{X},\mathcal{Y})$ to be

$$ $\|\mathfrak{L}\|_{\infty}=\sup_{x\in\mathcal{X}}|\mathfrak{L}(x)|$ $$

###### Definition 23 .

Let $\mathcal{X}$, $\mathcal{Y}$ be two metric spaces. Let ${\rm Lip}(\mathcal{X},\mathcal{Y})$ be the space of Lipschitz continuous mappings $\mathcal{X}\mapsto\mathcal{Y}.$ We define the Bounded-Lipschitz function over ${\rm Lip(\mathcal{X},\mathcal{Y})}$ as

$$ $\|\cdot\|_{\rm BL}:=\left\|\cdot\right\|_{\infty}+\left\|\cdot\right\|_{\rm L},$ $$

when $\left\|\cdot\right\|_{\rm L}$ and $\left\|\cdot\right\|_{\infty}$ are defined in Definition 21 and Definition 22, respectively. We note that as $\left\|\cdot\right\|_{\infty}$ is a norm and $\left\|\cdot\right\|_{\rm L}$ is a semi norm then $\left\|\cdot\right\|_{\rm BL}$ is a seminorm as well.

The next claim is a trivial result of Claim 23. in Böker et al. [].

###### Claim 1 .

Let $f:S\to\mathbb{R}^{n}$ be Lipschitz. Then,

$$ $\left\|\int_{S}fd\mu-\int_{S}fd\nu\right\|_{2}\leq\|f\|_{BL}\cdot\left((\|\mu \|-\|\nu\|)+\int_{S\times S}d(x,y)d\gamma(x,y)\right)$ $$

for every $\gamma\in\mathcal{M}(\mu,\nu)$, where $\|\cdot\|_{\rm BL}$ is the Bounded-Lipschitz seminorm over ${\rm Lip(\mathcal{S},\mathbb{R}^{n})}$, when ${\rm Lip(\mathcal{S},\mathbb{R}^{n})}$ is the space of Lipschitz continuous mappings ${\mathcal{S}\mapsto\mathbb{R}^{n}}$.

For an $L$-layer MPNN model $\varphi=(\varphi^{(t)})_{t=0}^{L}$, we define a Lipschitz constant of $\varphi$ by
$C_{\varphi}:=C^{L}_{\varphi}$, when $C^{t}_{\varphi}\geq 0$ is inductively defined for $t\in\{0,\ldots,L\}$ by

$$ $\displaystyle C^{t}_{\varphi}:=\begin{cases}2\cdot\left\|\varphi^{(t)}\right\| _{L}\cdot(\|\mathfrak{h}_{-}^{(L-1)}\|_{\infty}+C^{t-1}_{\varphi})&\text{ }: \text{if }L>t>0\\ \|\varphi^{(0)}\|_{L}&\text{ }:\text{if }t=0\end{cases}$ $$

If additionally the MPNN model has a readout function $\psi$, then

$$ $C_{(\varphi,\psi)}:=\left\|\psi\right\|_{L}(\left\|\mathfrak{h}^{(L)}_{-} \right\|_{\infty}+C_{\varphi}).$ $$

We now use Claim 1 to prove MPNNs Lipschitz property. We show that, given an L-layers MPNN model $\varphi$ and a readout function $\psi$, $C_{\varphi}$ and $C_{(\varphi,\psi)}$ are indeed Lipschitz constants of $\varphi$ and $(\varphi,\psi)$, respectively.
See 4

###### Proof.

Let us now prove the first inequality by induction on $L$. In the following statements, we use the notation $\mathfrak{h}_{-}^{(L)}$ instead of $\mathfrak{h}(\varphi,-)^{(L)}$.
Induction Base. For $L=0$, the statement trivially holds since $\varphi^{(0)}$ is lipschitz and $\mathfrak{h}^{(0)}_{\alpha}=\varphi^{(0)}(\alpha)$.
Induction Assumption. We assume that the statement hold for $L-1$ for $L>0$
Induction Step. For the inductive step, we have, by Claim 1 and the induction hypothesis, for all $\alpha$, $\beta$ $\in\mathcal{H}^{L}$

$$ $\displaystyle\|\mathfrak{h}_{\alpha}^{(L)}-\mathfrak{h}_{\beta}^{(L)}\|_{2}$ $\displaystyle=\left\|\varphi^{(L)}\left(\mathfrak{h}^{(L-1)}_{p_{L,L-1}(\alpha )},\int_{\mathcal{H}^{L-1}}\mathfrak{h}_{-}^{(L-1)}\text{d}p_{L}(\alpha)\right )-\varphi^{(L)}\left(\mathfrak{h}^{(L-1)}_{p_{L,L-1}(\beta)},\int_{\mathcal{H} ^{L-1}}\mathfrak{h}_{-}^{(L-1)}\text{d}p_{L}(\alpha)\right)\right\|_{2}$ $\displaystyle\leq\left\|\varphi^{(L)}\right\|_{L}\left(\left\|\mathfrak{h}^{(L -1)}_{p_{L,L-1}(\alpha)}-\mathfrak{h}^{(L-1)}_{p_{L,L-1}(\beta)}\right\|_{2}+ \left\|\int_{\mathcal{H}^{L-1}}\mathfrak{h}_{-}^{(L-1)}dp_{L}(\alpha)-\int_{ \mathcal{H}^{L-1}}\mathfrak{h}_{-}^{(L-1)}dp_{L}(\beta)\right\|_{2}\right)$ $\displaystyle\leq\left\|\varphi^{(L)}\right\|_{L}(\|\mathfrak{h}_{-}^{(L-1)}\| _{L}\cdot d_{\rm IDM}^{L-1}(p_{L,L-1}(\alpha),p_{L,L-1}(\beta))+\|\mathfrak{h} _{-}^{(L-1)}\|_{\text{BL}}\cdot\mathbf{OT}_{d_{\rm IDM}^{L}}(p_{L}(\alpha),p_{ L}(\beta))$ $\displaystyle\leq 2\cdot\left\|\varphi^{(L)}\right\|_{L}\cdot\|\mathfrak{h}_{- }^{(L-1)}\|_{\text{BL}}\cdot d_{\rm IDM}^{L}(\alpha,\beta)=2\cdot\left\| \varphi^{(L)}\right\|_{L}\cdot(\|\mathfrak{h}_{-}^{(L-1)}\|_{\infty}+\| \mathfrak{h}_{-}^{(L-1)}\|_{L})\cdot d_{\rm IDM}^{L}(\alpha,\beta)$ $\displaystyle=2\cdot\left\|\varphi^{(L)}\right\|_{L}\cdot(\|\mathfrak{h}_{-}^{ (L-1)}\|_{\infty}+C^{L-1}_{\varphi})\cdot d_{\rm IDM}^{L}(\alpha,\beta)=C^{L}_ {\varphi}\cdot d_{\rm IDM}^{L}(\alpha,\beta)=C_{\varphi}\cdot d_{\rm IDM}^{L}( \alpha,\beta).$ $$

Hence, we get the first inequality. The second equality then follows from the first by a similar reasoning as in the inductive step above. For all $\mu$, $\nu$ $\in\mathscr{P}(\mathcal{H}^{L})$ we have

$$ $\displaystyle\|h(\varphi,\psi,\mu)-h(\varphi,\psi,\nu)\|_{2}$ $\displaystyle=\left\|\psi\left(\int_{\mathcal{H}^{L}}\mathfrak{h}_{-}^{(L)}d \mu\right)-\psi\left(\int_{\mathcal{H}^{L}}\mathfrak{h}_{-}^{(L)}d\nu\right) \right\|_{2}\leq\left\|\psi\right\|_{L}\left\|\int_{\mathcal{H}^{L}}\mathfrak{ h}_{-}^{(L)}d\mu-\int_{\mathcal{H}^{L}}\mathfrak{h}_{-}^{(L)}d\nu\right\|_{2}$ $\displaystyle\leq\left\|\psi\right\|_{L}\left\|\mathfrak{h}^{(L)}_{-}\right\|_ {\text{BL}}\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu,\nu)=\left\|\psi\right\|_{L}\left (\left\|\mathfrak{h}^{(L)}_{-}\right\|_{\infty}+\left\|\mathfrak{h}^{(L)}_{-} \right\|_{\text{L}}\right)\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu,\nu)$ $\displaystyle=\left\|\psi\right\|_{L}\left(\left\|\mathfrak{h}^{(L)}_{-}\right \|_{\infty}+C^{L}_{\varphi}\right)\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu,\nu)== \left\|\psi\right\|_{L}\left(\left\|\mathfrak{h}^{(L)}_{-}\right\|_{\infty}+C_ {\varphi}\right)\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu,\nu)$ $\displaystyle=C_{(\varphi,\psi)}\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu,\nu)$ $$

∎

For the sake of completeness, we state Theorem 4 as an epsilon-delta statement.

###### Theorem 14 .

Let $d>0$ be fixed. For every $L\in\mathbb{N}$, $C>0$, and $\varepsilon>0$, there is a $\delta>0$ such that, for all order-$t$ DIDMs $\mu$ and $\nu$, if $\mathbf{OT}_{d_{\rm IDM}^{t}}(\mu,\nu)\leq\delta$, then $\|\mathfrak{H}(\varphi,\psi,\mu)-\mathfrak{H}(\varphi,\psi,\nu)\|_{2}\leq\varepsilon$ for every $L$-layer MPNN model $\varphi$ with readout function $\psi:\mathbb{R}^{d_{L}}\to\mathbb{R}^{d}$ with $C_{(\varphi,\psi)}\leq C$.

###### Proof.

Follows immediately from Theorem 4.
∎

###### Definition 21 .

###### Definition 22 .

###### Definition 23 .

###### Claim 1 .

###### Proof.

###### Theorem 14 .

###### Proof.

## Appendix F Universality Of Message-Passing Graph Neural Networks

In this section we prove our universal approximation theorem for MPNNs on IDMs and DIDMs, showing the sets $\mathcal{N}^{1}_{t}$ and $\mathcal{N}\mathcal{N}^{1}_{t}$ are dense in $C(\mathcal{H}^{t},\mathbb{R})$ and $C(\mathscr{P}(\mathcal{H}^{t}),\mathbb{R})$, respectively. The proofs of Lemma 4, Theorem 6, follow the proofs of Lemma 25, Theorem 4, and Theorem 6 in Böker et al. [], respectively. This follows by inductively applying Stone–Weierstrass theorem, cf. Appendix A.4, to the set $\mathcal{N}^{1}_{t}.$ Given that $\mathcal{N}^{1}_{t}$ satisfies all requirements of the Stone–Weierstrass theorem, Corollary 1 yields that $\mathcal{N}^{1}_{t+1}$ separates points, which allows us to show that $\mathcal{N}^{1}_{t+1}$ again satisfies all requirements of the Stone-Weierstrass theorem. We recall the canonical projections were denoted by $p_{L,j}:\mathcal{H}^{L}\mapsto\mathcal{H}^{j}$ and $p_{L}:\mathcal{H}^{L}\rightarrow\mathcal{M}^{L}$, when $j\leq L<\infty$.

###### Lemma 4 .

Let $0\leq t<\infty$. The set $\mathcal{N}^{1}_{t}$ are closed under multiplication and linear combinations, contains ${1}_{\mathcal{H}^{t}}$ and separates points of $\mathcal{H}^{t}$.

###### Proof.

We will now prove the lemma inductively.
Induction Base. For $t=0$, the claim trivially holds as $\mathcal{N}^{1}_{0}$ contains precisely the functions $f:\mathcal{H}^{0}\mapsto\mathbb{R}$ that are Lipschitz continuous which contains $1_{\mathcal{H}^{0}}$, and closed to multiplication and addition.
Induction Assumption. We assume the sets $\mathcal{N}^{1}_{t}$ is closed under multiplication and linear combinations, contains ${1}_{\mathcal{H}^{t}}$ and separates points of $\mathcal{H}^{t}$.
Induction Step. Let $t+1$. Clearly $\mathcal{N}^{1}_{t+1}$ contains the all-one function $1_{\mathcal{H}^{t+1}}$ since we can always choose $\varphi^{(t+1)}$ in an MPNN model to be the all-one function on any of the two inputs. Let $\varphi$, $\varphi^{\prime}$ be two $(t+1)$-layer MPNN models. Define $\Xi_{\text{mul}}(x,y):=x\cdot y$ and $\Xi_{\text{add}}(x,y):=x+c\cdot y$ for all $x,y\in\mathbb{R}$, where $c\in\mathbb{R}$ is fixed . Then, define the MPNN model

$$ $\varphi_{\text{mul}}:=(\varphi^{(0)}\times{\varphi^{\prime}}^{(0)},\ldots, \varphi^{(t)}\times{\varphi^{\prime}}^{(t)},\Xi_{\text{mul}}\circ(\varphi^{(t+ 1)}\times{\varphi^{\prime}}^{(t+1)}))$ $$

and define $\varphi_{\text{add}}$ analogously via $\Xi_{\text{add}}$. Note that $\Xi_{\text{mul}}$ and $\Xi_{\text{add}}$ are in fact MPNN models since multiplication and addition on a compact, and hence, a bounded subset of $\mathbb{R}^{2}$ is Lipschitz continuous

Let $\alpha,\beta\in\mathcal{H}^{t+1}$ with $\alpha\neq\beta$. We consider two cases: either $p_{t+1}(\alpha)\neq p_{t+1}(\beta)$ or $p_{t+1,t}(\alpha)\neq p_{t+1,t}(\beta)$. We start with the first case, i.e., $p_{t+1}(\alpha)\neq p_{t+1}(\beta)$. By the induction hypothesis, the set $\mathcal{N}^{1}_{t}$ is closed under multiplication and linear combinations, contains $1_{\mathcal{H}^{t}}$, and separates points of $\mathcal{H}^{t}$. Hence, it is a sub-algebra of $C(\mathcal{H}^{t},\mathbb{R})$ that separates points and contains the constants. By the Stone–Weierstrass theorem, $\mathcal{N}^{1}_{t}$ is dense in $C(\mathcal{H}^{t},\mathbb{R})$. Corollary 2 then entails that there is a $t$-layer MPNN model $\varphi$ with output dimension one such that

$$ $\int_{\mathcal{H}^{t}}\mathfrak{h}(\varphi)^{(t)}_{-}dp_{t+1}(\alpha)\neq\int_ {\mathcal{H}^{t}}\mathfrak{h}(\varphi)^{(t)}_{-}dp_{t+1}(\beta).$ $$

Define the $(t+1)$-layer MPNN model $\varphi^{\prime}:=(\varphi^{\prime(i)})^{t+1}_{i=0}$, where $\varphi^{\prime(i)}=\varphi^{(i)}$ for $i\in[t]$ and $\varphi^{\prime(t+1)}(x,y):=y$ for every $(x,y)\in\mathbb{R}^{2}$. Then, $\varphi^{\prime}\in\mathcal{N}^{1}_{t}$ , separates $\alpha$ and $\beta$ since

$$ $\displaystyle\mathfrak{h}^{(t+1)}(\varphi^{\prime},\alpha)$ $\displaystyle=\int_{\mathcal{H}^{t}}\mathfrak{h}(\varphi^{\prime})^{(t)}_{-}dp _{t+1}(\alpha)$ $\displaystyle=\mathfrak{h}(\varphi)^{(t)}_{-}dp_{t+1}(\alpha)\neq\int_{ \mathcal{H}^{t}}\mathfrak{h}(\varphi)^{(t)}_{-}dp_{t+1}(\beta)$ $\displaystyle=\int_{\mathcal{H}^{t}}\mathfrak{h}(\varphi^{\prime})^{(t)}_{-}dp _{t+1}(\beta)=\mathfrak{h}^{(t+1)}(\varphi^{\prime},\beta).$ $$

In the second case, where $p_{t+1,t}(\alpha)\neq p_{t+1,t}(\beta)$, we have that, from the induction assumption, there exists a $t$-layer MPNN model $\hat{\varphi}$ such that $\mathfrak{h}(\hat{\varphi})^{(t)}_{p_{t+1,t}(\alpha)}\neq\mathfrak{h}(\hat{
\varphi})^{(t)}_{p_{t+1,t}(\beta)}.$ Define the $(t+1)$-layer MPNN model $\hat{\varphi}^{\prime}:=(\hat{\varphi}^{\prime(i)})^{t+1}_{i=0}$, where $\hat{\varphi}^{\prime(i)}=\hat{\varphi}^{(i)}$ for $i\in[t]$ and $\hat{\varphi}^{\prime(t+1)}(x,y):=x$ for every $(x,y)\in\mathbb{R}^{2}$. Then, $\hat{\varphi}^{\prime}\in\mathcal{N}^{1}_{t}$ separates $\alpha$ and $\beta$ since

$$ $\displaystyle\mathfrak{h}(\hat{\varphi}^{\prime})^{(t+1)}_{\alpha}$ $\displaystyle=\mathfrak{h}(\hat{\varphi}^{\prime})^{(t)}_{p_{t+1,t}(\alpha)}$ $\displaystyle=\mathfrak{h}(\hat{\varphi})^{(t)}_{p_{t+1,t}(\alpha)}\neq \mathfrak{h}(\hat{\varphi})^{(t)}_{p_{t+1,t}(\beta)}$ $\displaystyle=\mathfrak{h}(\hat{\varphi}^{\prime})^{(t)}_{p_{t+1,t}(\beta)}= \mathfrak{h}(\hat{\varphi}^{\prime})^{(t+1)}_{\beta}.$ $$

∎

With Lemma 4, we immediately obtain Theorem 6, which we restate here for better readability.
See 6

###### Proof.

By Lemma 4, the Stone–Weierstrass theorem is applicable to $\mathcal{N}^{1}_{L}$, and hence, $\mathcal{N}^{1}_{L}$ is dense in $C(\mathcal{H}^{L},\mathbb{R})$. We can then use this to show that $\mathcal{N}\mathcal{N}^{1}_{L}$ is dense in $C(\mathscr{P}(\mathcal{H}^{L}),\mathbb{R})$. By the same arguments as in the first case of the inductive step in the proof of Lemma 4, $\mathcal{N}\mathcal{N}^{1}_{L}$ is closed under multiplication and linear combinations, contains the all-one function, and separates
points of $\mathscr{P}(\mathcal{H}^{L})$. Hence, an application Corollary 2 yields that $\mathcal{N}\mathcal{N}^{1}_{L}$ is dense in $C(\mathscr{P}(\mathcal{H}^{L}),\mathbb{R})$.
∎

Theorem 6 then yields Corollary 1. To prove Corollary 1, we follow the proof of Corollary 5. in Böker et al. [].

See 1

###### Proof.

First, let $n=1$. When restricted to functions $\mathfrak{H}(\varphi,\psi,-)\in\mathcal{N}\mathcal{N}_{L}^{n}$ of the form $\mathfrak{H}(\varphi,\psi,\nu)=\int_{\mathbb{M}_{L}}\mathfrak{h}^{(L)}_{-}d\nu$, i.e., the readout $\psi$ is the identity, the claim follows since $\mathcal{N}_{L}^{1}$ is dense in $C(\mathbb{M}_{L},\mathbb{R})$ by Theorem 6 and the definition of the weak* topology on $\mathscr{P}(\mathbb{M}_{L})$, cf. Section 2. Since the readout function $\psi$ is continuous, the equivalence also holds when considering all functions in the set $\mathcal{N}\mathcal{N}_{L}^{d}$. Finally, since one can always consider the projection to a single component and conversely map a single real number to a vector of these numbers, the equivalence also holds in the case $n>1$.
∎

###### Lemma 4 .

###### Proof.

###### Proof.

###### Proof.

## Appendix G Lipschitz Property Converse Theorem

The proof of Theorem 5
See 5

###### Proof.

Assume that there is an $\varepsilon>0$ such that such $L\in\mathbb{N}$, $C>0$, and $\delta>0$ do not exist. Then, for every $L\in\mathbf{N}$ and $C>0$ $\delta_{k}:=1/k\geq 0$, there are $L$-layers DIDMs $\mu_{k}$ and $\nu_{k}$ such that $\|\mathfrak{H}(\varphi,\psi,\mu_{k})-\mathfrak{H}(\varphi,\psi,\nu_{k})\|_{2}
\leq\delta_{k}$ for every
$L$-layers MPNN model $(\varphi,\psi)$ with readout and output dimension $d$, and $C_{(\varphi,\psi)}\leq C$ but also $\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu_{k},\nu_{k})>\varepsilon$. By the compactness of $\mathscr{P}(\mathcal{H}^{L})$, there are subsequences $(\mu_{k_{i}})_{i}$ and $(\nu_{k_{i}})_{i}$ converging to DIDMs $\widetilde{\mu}$ and $\widetilde{\nu}$, respectively, in the weak* topology. Let $\hat{\varphi}$ be an $L$-layer MPNN model and a readout fucntion $\hat{\psi}:\mathbb{R}^{d_{L}}\to\mathbb{R}^{d}$. Then, by Corollary 1, also $(\mathfrak{H}(\hat{\varphi},\hat{\psi},\mu_{k_{i}}))_{i}$ and $(\mathfrak{H}(\hat{\varphi},\hat{\psi},\nu_{k_{i}}))_{i}$ converge to $\mathfrak{H}(\hat{\varphi},\hat{\psi},\widetilde{\mu})$ and $\mathfrak{H}(\hat{\varphi},\hat{\psi},\widetilde{\nu})$, respectively. Hence,

$$ $\displaystyle\|\mathfrak{H}(\hat{\varphi},\hat{\psi},\widetilde{\nu})- \mathfrak{H}(\hat{\varphi},\hat{\psi},\widetilde{\mu})\|_{2}\leq$ $\displaystyle\|\mathfrak{H}(\hat{\varphi},\hat{\psi},\widetilde{\nu})- \mathfrak{H}(\hat{\varphi},\hat{\psi},\nu_{k_{i}})\|_{2}$ $\displaystyle+\|\mathfrak{H}(\hat{\varphi},\hat{\psi},\nu_{k_{i}})-\mathfrak{H }(\hat{\varphi},\hat{\psi},\mu_{k_{i}})\|_{2}$ $\displaystyle+\|\mathfrak{H}(\hat{\varphi},\hat{\psi},\mu_{k_{i}})-\mathfrak{H }(\hat{\varphi},\hat{\psi},\widetilde{\mu})\|_{2}\xrightarrow{i\to\infty}0$ $$

by the assumption, i.e., $\mathfrak{H}(\hat{\varphi},\hat{\psi},\widetilde{\mu})=\mathfrak{H}(\hat{
\varphi},\hat{\psi},\widetilde{\nu})$. Since this holds for every MPNN model and Lipschitz $\psi$, we have $\mathbf{OT}_{d_{\rm IDM}^{L}}(\widetilde{\mu},\widetilde{\nu})=0$ by Corollary 1 and Theorem 2 with the fact that $\mathscr{P}(\mathcal{H}^{L})$ is Hausdorff. Then, however

$$ $\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu_{k_{i}},\nu_{k_{i}})\leq\mathbf{OT}_{d_{\rm IDM }}(\mu_{k_{i}},\widetilde{\mu})+\mathbf{OT}_{d_{\rm IDM}^{L}}(\widetilde{\mu}, \widetilde{\nu})+\mathbf{OT}_{d_{\rm IDM}^{L}}(\widetilde{\nu},\nu_{k_{i}}) \xrightarrow{k\to\infty}0$ $$

since $(\nu_{k_{i}})_{i}$ and $(\mu_{k_{i}})_{i}$ converge to $\widetilde{\nu}$ and $\widetilde{\mu}$, respectively, also in $\mathbf{OT}_{d_{\rm IDM}^{L}}$ by by Corollary 1 and Theorem 2. This contradicts the assumption that $\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu_{k_{i}},\nu_{k_{i}})>\varepsilon$ for every $k\geq 0$.
∎

###### Proof.

## Appendix H Proximity Relations of MPNNs

Here, we prove how proximity of any MPNN’s output on any two different DIDMs and proximity of the two DIDMs connect.–

###### Theorem 15 .

Let $L\in\mathbb{N}$ and $(\mu_{i})_{i}$ be a sequence of order-$L$ DIDMs, and let $\mu\in\mathscr{P}(\mathcal{H}^{L})$ be a DIDM. Then, the following are equivalent:

- 1.
$\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu_{i},\mu)\to 0$.
- 2.
$\mathbf{h}_{\mu_{i}}\to\mathbf{h}_{\mu}$ for all MPNN model $\varphi$ with readout $\psi:\mathbb{R}^{d_{L}}\mapsto\mathbb{R}^{n}$, where $n>0$.
- 3.
$\mu_{i}\to\mu$.

###### Proof.

The implication $(1)\Rightarrow(2)$ is just a result of Theorem 4, and its converse is Theorem 5. (1) and (2) are equivalent to (3) by Theorem 2 and Corollary 1.
∎

We further note that the following variant of Theorem 15 holds as well.

###### Theorem 16 .

Let $\mu$, $\nu\in\mathscr{P}(\mathcal{H}^{L})$. Then, the following are equivalent:

- 1.
$\mathbf{OT}_{d_{\rm IDM}^{L}}(\mu,\nu)=0$.
- 2.
$\mathfrak{h}_{\mu}=\mathfrak{h}_{\nu}$ for every MPNN model $\varphi$ and a readout function $\psi:\mathbb{R}^{d}\to\mathbb{R}^{n}$, where $n>0$.
- 3.
$\mu=\nu$.

###### Proof.

The equivalences follow as in Theorem 15 since $\mathscr{P}(\mathcal{H}^{L})$ is Hausdorff.
∎

###### Theorem 15 .

###### Proof.

###### Theorem 16 .

###### Proof.

## Appendix I Generalization Theorem for MPNN

We expand the generalization analysis in Levie [] to a more general setting and adjust it to meet our definitions.

### I.1 Statistical Learning and Generalization Analysis

In statistical learning theory, usually we consider a product probability space $\mathcal{P}=\mathcal{X}\times\mathcal{Y}$, which represents all possible data. We call any arbitrary probability measure on $(\mathcal{P},\mathcal{B}(\mathcal{P}))$ a *data distribution*. We presume we have a fixed and unknown data distribution $\tau$. As the completeness of our measure space does not affect our construction, we may assume that we complete $\mathcal{B}(\mathcal{P})$ with respect to $\tau$ to a complete $\sigma$-algebra $\Sigma$ or just denote $\Sigma=\mathcal{B}(\mathcal{P}).$ Additionally, let $\mathbf{X}\subseteq\mathcal{P}$ be a dataset of independent random samples from $(\mathcal{P},\tau)$. Additionally, we presume $\mathcal{Y}$ contains values that relate to every point in $\mathcal{X}$, according to a fixed and unknown conditional distribution function $\tau_{\mathcal{Y}|\mathcal{X}}\in\mathscr{P}(\mathcal{Y})$. In it’s essence, the problem of learning is choosing from some set of function, the one that best approximate the relation between the points in $\mathcal{Y}$ and the points in $\mathcal{X}$.

Let $\mathcal{E}$ be a Lipschitz loss function. Note that the loss $\mathcal{E}$ can have a learnable component that depends on the dataset $\mathbf{X}$ as long as it is Lipschitz with a constant $L_{2}$. Our objective is to find the optimal model $\mathfrak{L}$ from some hypothesis space $\mathcal{Z}$ that has a low *statistical risk*

$$ $\mathcal{R}(\mathfrak{L})=\mathbb{E}_{(\nu,y)\sim\tau}[\mathcal{L}(\mathfrak{L }(\nu),y)]=\int\mathcal{E}(\mathfrak{L}(\nu),y)d\tau(\nu,y),\quad\mathfrak{L} \in\mathcal{Z}$ $$

However, as stated before, the true distribution $\tau$ is not directly observable. Instead, we have access to
a set of independent, identically distributed (i.i.d) samples $\mathbf{X}=(X_{1},\ldots,X_{N})$ from the data distribution $(\mathcal{P},\tau)$. Instead of minimizing the statistical risk with an unknown data distribution $\tau$, we try to approximation the optimal model by minimizing the *empirical risk*:

$$ $\hat{\mathcal{R}}_{\mathbf{X}}(\mathfrak{L}_{\mathbf{X}})=\frac{1}{N}\sum_{i=1 }^{N}\mathcal{E}(\mathfrak{L}_{\mathbf{X}}(\nu_{i}),Y_{i}),$ $$

where $0<i\leq N:X_{i}=(\nu_{i},Y_{i})$ and $\mathfrak{L}_{\mathbf{X}}$ is a model with some possible dependency on the sampled data, e.g., through training.

Generalization analysis goal is to show that low empirical risk of a a network entails low statistical risk as well. One approach to bounding the statistical risk involves using the inequality:

$$ $\mathcal{R}(\mathfrak{L})\leq\hat{\mathcal{R}}(\mathfrak{L})+E$ $$

where $E$ is called the generalization error, defined as:

$$ $E=\sup_{\Theta\in\mathcal{H}}|\mathcal{R}(\Theta)-\hat{\mathcal{R}}(\Theta)|$ $$

It’s important to note that the trained network $\mathfrak{L}:=\mathfrak{L}_{\mathbf{X}}$ depends on the dataset $\mathbf{X}$. This essantially means that the empirical risk is not truly a Monte Carlo approximation of the statistical risk in the learning context, as the network is not constant when varying the dataset. If the model $\mathfrak{L}$ was fixed, Monte Carlo theory would provide us an order $\mathcal{O}(\sqrt{\kappa(p)/N})$ bound for $E$ with probability $1-p$, where $\kappa(p)$ depends on the specific inequality used (e.g., $\kappa(p)=\log(2/p)$ in Hoeffding’s inequality).

Such events are called good sampling events and depend on the model $\mathfrak{L}$. This dependence, result in the requirement of intersecting all good sampling events in $\mathcal{Z}$, in order to compute a naive
bound to the generalization error.

Uniform convergence bounds are employed to intersect appropriate sampling events, allowing for more efficient bounding of the generalization error. This intersection introduces a term in the generalization bound called the complexity or capacity.This concept describes the richness of the hypothesis space $\mathcal{Z}$ and underlies approaches such as VC-dimension, Rademacher dimension, fat-shattering dimension, pseudo-dimension, and uniform covering number (see, e.g., Shalev-Shwartz and Ben-David []).

### I.2 Uniform Monte Carlo Estimation for Lipschitz Continuous Functions

The proof of Theorem 7 relies on Theorem 18, which examines uniform Monte Carlo estimations of Lipschitz continuous functions over metric spaces with finite covering. The next theorems are taken from Levie [].

###### Definition 24 .

A metric space $\mathcal{X}$ is said to have a covering number $\nu:(0,\infty)\to\mathbb{N}$ if, for any $\delta>0$, $\mathcal{X}$ can be covered by $\nu(\delta)$ balls of radius $\delta$.

###### Theorem 17 (Hoeffding’s Inequality) .

Let $X_{1},\ldots,X_{N}$ be independent random variables such that $a\leq X_{i}\leq b$ almost surely. Then, for any $k>0$,

$$ $\mathbb{P}\left(\left|\frac{1}{N}\sum_{i=1}^{N}(X_{i}-\mathbb{E}[X_{i}])\right |\geq k\right)\leq 2\exp\left(-\frac{2k^{2}N}{(b-a)^{2}}\right).$ $$

Theorem 18 is an extended version of Lemma B.3 in Maskey et al. [].

###### Theorem 18 (Uniform Monte Carlo Estimation for Lipschitz Continuous Functions) .

Let $\mathcal{P}$ be a probability metric (^1^11A metric space with a probability Borel measure, where we either take the completion of the measure space with respect to $\mu$ (adding all subsets of null-sets to the $\sigma$-lgebra) or not.) space with probability measure $\mu$ and covering number $\kappa(\epsilon)$.
Let $X_{1},\ldots,X_{N}$ be drawn i.i.d. from $\mathcal{P}$. Then, for any $p>0$, there exists an event $\mathcal{E}^{p}_{Lip}\subset\mathcal{P}^{N}$ (regarding the choice of $(Y_{1},\ldots,Y_{N})$), with probability

$$ $\mu^{N}(\mathcal{E}^{p}_{Lip})\geq 1-p$ $$

such that for every $(X_{1},\ldots,X_{N})\in\mathcal{E}^{p}_{Lip}$, for every bounded Lipschitz continuous function $\mathfrak{F}:\mathcal{P}\to\mathbb{R}^{d}$ with Lipschitz constant $L_{\mathfrak{F}}$, we have

$$ $\left\|\int\mathfrak{F}(x)d\mu(x)-\frac{1}{N}\sum_{i=1}^{N}\mathfrak{F}(X_{i}) \right\|_{\infty}\leq 2\xi^{-1}(N)L_{\mathfrak{F}}+\frac{1}{\sqrt{2}}\xi^{-1}( N)\|\mathfrak{F}\|_{\infty}(1+\sqrt{\log(2/p)}),$ $$

where $\xi(r)=\frac{\kappa(r)^{2}\log(\kappa(r))}{r^{2}}$ and $\xi^{-1}$ is the inverse function of $\xi$.

###### Definition 24 .

###### Theorem 17 (Hoeffding’s Inequality) .

###### Theorem 18 (Uniform Monte Carlo Estimation for Lipschitz Continuous Functions) .

### I.3 A generalization theorem for MPNNs

In classification tasks our goal is to classify the input space into C classes. In this analysis we look at the product probability space $\mathcal{P}=\mathscr{P}(\mathcal{H}^{L})\times\mathbb{R}^{C}$ and use $L$-layers MPNNs with readout. Our DIDM features are $\mathfrak{h}_{\nu}=\int_{\mathcal{H}}^{L}\mathfrak{h}^{(L)}_{-}d\nu.$ Each entry $(\vec{v})_{c}$ of the output vector $\vec{v}\in\mathbb{R}^{C}$ depicts the probability the input belongs to class $c\in C$. We thus consider the readout function $\psi:\mathbb{R}^{p}\to\mathbb{R}^{C}$ as part of the loss function and assume the combined loss to be Lipschitz continuous. Although loss functions like cross-entropy are not Lipschitz continuous, composing cross-entropy on softmax is Lipschitz, which is usally how cross-entropy is being used.

We denote by $\Theta_{L}$ the set of all MPNN models of depth-$L$ with a readout function, s.t. $\mathfrak{h}:\mathscr{P}(\mathcal{H}^{L})\mapsto\mathbb{R}^{C}$ and by $\mathrm{Lip}(\mathscr{P}(\mathcal{H}^{L}),L_{1})$ the space of Lipschitz continuous mappings $\mathfrak{L}:\mathscr{P}(\mathcal{H}^{L})\to\mathbb{R}^{C}$ with Lipschitz constant $L_{1}$. Notices that, by Theorem 4, our hypothesis class $\Theta_{L}$ of depth-$L$ MPNNs is contained in $\mathrm{Lip}(\mathscr{P}(\mathcal{H}^{L}),L_{1})$ for some given Lipschitz constant $L_{1}$.

Following the proof of Theorem Theorem G.4 in Levie [], we prove the next theorem via Theorem 18.

See 7

###### Proof.

For each $i\in[C]$, let $S_{i}$ be the number of samples of $\mathbf{X}$ that falls within $B_{i}$. The random variable $(S_{1},\ldots,S_{C})$ is multinomial, with expected value $(N/C,\ldots,N/C)$ and variance $(\frac{N(C-1)}{C^{2}},\ldots,\frac{N(C-1)}{C^{2}})\leq(\frac{N}{C},\ldots,
\frac{N}{C})$. We now use Chebyshev’s inequality, which states that for any $a>0$,

$$ $P(|S_{i}-N/C|>a\sqrt{\frac{N}{C}})<a^{-2}.$ $$

We choose $a\sqrt{\frac{N}{C}}=\frac{N}{2C}$, so $a=\frac{N^{1/2}}{2C^{1/2}}$, and

$$ $P(|S_{i}-N/C|>\frac{N}{2C})<\frac{2C}{N}.$ $$

Therefore,

$$ $P(S_{i}>\frac{N}{2C})>1-\frac{2C}{N}.$ $$

We intersect these events of $i\in[C]$, and get an event $\mathcal{E}_{\text{mult}}$ of probability more than $1-2\frac{C^{2}}{N}$ in which $S_{i}>\frac{N}{2C}$ for every $i\in[C]$. In the following, given a set $B$, we consider a realization $M=S_{i}$, and then use the law of total probability.

From Theorem 18 we get the following. For every $p>0$, there exists an event $\mathcal{E}_{i}^{p}\subset B_{i}^{M}$ regarding the choice of $(X_{1},\ldots,X_{M})\subseteq B^{M}_{i}$, with probability

$$ $\nu^{M}(\mathcal{E}^{p}_{\text{Lip}})\geq 1-p,$ $$

such that for every function $\mathfrak{L}^{\prime}$ in the hypothesis class $\text{Lip}(\mathscr{P}(\mathcal{H}^{L}),L_{1})$, we have

$$ $\displaystyle\left|\int{\mathcal{E}}(\mathfrak{L}^{\prime}(\nu),y)d\tau(\nu,y) -\frac{1}{M}\sum_{i=1}^{M}\mathbb{E}(\mathfrak{L}^{\prime}(\nu_{i}),Y_{i})\right|$ (11) $\displaystyle\leq 2\xi^{-1}(M/L+\frac{1}{\sqrt{2}}\xi^{-1}(M))(\|\mathcal{E}( \mathfrak{L}^{\prime}(\cdot),\cdot)\|_{\infty}(1+\sqrt{\log(2/p)})$ (12) $\displaystyle\leq 2\xi^{-1}(N/2C)L+\frac{1}{\sqrt{2}}\xi^{-1}(N/2C)(L+\mathcal {E}(0,0))(1+\sqrt{\log(2/p)}),$ (13) $$

where for $0<i\leq N:(\nu_{i},Y_{i})=X_{i}$, $\xi(r)=e^{(r)^{2}\log(e(r))}$, $\kappa$ is the covering number of $\mathscr{P}(\mathcal{H}^{L})\times\{0,1\}^{C}$, and $\xi^{-1}$ is the inverse function of $\xi$. In the last inequality, we use the bound, for every $(\nu,y)\in\mathscr{P}(\mathcal{H}^{L})\times\{0,1\}^{C}$,

$$ $|\mathcal{E}(\mathfrak{L}^{\prime}(\nu),y)|\leq\mathcal{E}(\mathfrak{L}^{ \prime}(\nu),y)-\mathcal{E}(0,0)|+|\mathcal{E}(0,0)|\leq L_{2}|(L_{1}+1)-0|+| \mathcal{E}(0,0)|.$ $$

Since 11 is true for any $\mathfrak{L}^{\prime}\in\text{Lip}(\mathscr{P}(\mathcal{H}^{L}),L_{1})$, it is also true for $\mathfrak{L}_{\mathbf{X}}$ for any realization of $\mathbf{X}$, so we also have

$$ $|\mathcal{R}(\mathfrak{L}_{\mathbf{X}})-\hat{\mathcal{R}}_{\mathbf{X}}( \mathfrak{L}_{\mathbf{X}})|\leq 2\xi^{-1}(N/2C)L+\frac{1}{\sqrt{2}}\xi^{-1}(N/ 2C)(L+\mathcal{E}(0,0))(1+\sqrt{\log(2/p)}).$ $$

Lastly, we denote

$$ $\mathcal{E}^{p}=\mathcal{E}_{\text{mult}}\cap\left(\bigcup_{i=1}^{C}\mathcal{E }_{i}^{p}\right).$ $$

∎

###### Proof.

## Appendix J Tree Prokhorov’s Distance:

For completeness, we show an alternative approach to define a metric on graphons through IDMs and DIDMs using Prokhorv metric.

### J.1 Basic Metric Properties

Let $\mathcal{X}$ be a complete separable metric space with Borel $\sigma$-algebra $\mathcal{B}$. We define $A^{\epsilon}:=\{y\in S\mid d(x,y)\leq\epsilon\text{ for some }x\in A\}$ for a subset $A\subseteq\mathcal{X}$ and $\epsilon\geq 0$. Then, the Prokhorov metric $P$ on $\mathscr{M}_{\leq 1}(\mathcal{X},\mathcal{B})$ is given by

$$ $P(\mu,\nu):=\inf\{\epsilon>0\mid\mu(A)\leq\nu(A^{\epsilon})+\epsilon\text{ and }\nu(A)\leq\mu(A^{\epsilon})+\epsilon\text{ for every }A\in\mathcal{B}\}.$ $$

The following theorem shows that Prokhorov metric is topologically equivalent to $OT_{d}$ on any complete separable metric space $(\mathcal{X},d)$.

###### Lemma 5 .

[Prokhorov, , Theorem 1.11] Let $(\mathcal{X},d)$ be a complete separable metric space. Then, $(\mathscr{M}(\mathcal{X}),P)$ is a complete separable metric space, and convergence in $P$ is equivalent to weak* convergence of measures.

We can define in the same fashion as done in Section 3 alternative metrics $\mathbf{PD}^{n}$ on $\mathcal{H}^{n}$ and $\mathbf{P}_{\mathbf{PD}^{n}}$ on $\mathscr{M}_{\leq 1}(\mathcal{H}^{n})$ by replacing optimal transport in the definitions with Prokhorov metric. Then a distance between two graphon-signals can be define too as

###### Definition 25 (Tree Prokhorov’s Distance) .

Given two graphon-signals $(W_{a},f_{a})$, $(W_{b},f_{b})$ and $L\geq 1$, the tree prokhorov’s distance between $(W_{a},f_{a})$ and $(W_{b},f_{b})$ is defined as

$$ $\mathbf{TPD}^{L}((W_{a},f_{a}),(W_{b},f_{b}))=\mathbf{P}_{\mathbf{PD}^{L}}( \Gamma_{(W_{a},f_{a}),L},\Gamma_{(W_{b},f_{b}),L}),$ $$

Lemma 5 lets us prove the next theorem which is proven similarly to Theorem 2.

###### Theorem 19 .

Let $L\in\mathbb{N}$. The metrics $\mathbf{PD}^{L}$ on $\mathcal{H}^{L}$, $\mathbf{P}_{\mathbf{PD}^{L}}$ on $\mathscr{P}(\mathcal{H}^{L})$ and $\mathscr{M}_{\leq 1}(\mathcal{H}^{L})$ are well-defined. Moreover, $\mathbf{P}_{\mathbf{PD}^{L}}$ metrizes the weak* topology of $\mathscr{M}_{\leq 1}(\mathcal{H}^{L})$ and $\mathscr{P}(\mathcal{H}^{L})$.

This essentially means, that all our results in this paper can be rephrased by replacing $d_{\rm IDM}^{L}$, $\mathbf{OT}_{d_{\rm IDM}^{L}}$, and $\delta_{\rm DIDM}^{L}$ with $\mathbf{PD}^{L}$, $\mathbf{P}_{\mathbf{PD}^{L}}$, and $\mathbf{TPD}^{L}$ respectively. The only thing remains, is to discuss $\mathbf{TPD}^{L}$ compatibility.

###### Lemma 5 .

###### Definition 25 (Tree Prokhorov’s Distance) .

###### Theorem 19 .

### J.2 Computability

It remains to prove that $\mathbf{TPD}^{L}$ is polynomial-time computable. Böker et al. [] prove the Lemma 6 by generalizing an observation in Theorem 1 Schay [] and Lemma García-Palomares and Giné [] to finite measures to finite measures and showing that the
value of $\rho(\varepsilon):=\inf\{\eta>0\mid\mu(A)\leq\nu(A^{\varepsilon})+\eta\text{
for every }A\subseteq S\}$
can be expressed as a linear program. Additionally, he based his conclusions on Garel and Massé [], which is concerned with computing the Prokhorov metric of (possibly non-discrete) probability distributions.

###### Lemma 6 .

[Böker et al., , Theorem 16.] Let $\mu,\nu\in\mathcal{M}(\mathcal{X})$, where $(\mathcal{X},d)$ is a finite metric space with $\mathcal{X}=\{x_{1},\dots,x_{n}\}$. Then, the Prokhorov metric $P(\mu,\nu)$ can be computed in time polynomial in $n$ and the number of bits needed to encode $d$, $\mu$ and $\nu$.

This allows us to prove Theorem 20 following the same steps as in the proof of Theorem 3.

###### Theorem 20 .

For any fixed $k\in\mathbb{N}$, $\delta_{\rm DIDM}^{k}$ between any two graph-signals $(G,\mathbf{f})$ and $(H,\mathbf{g})$
can be computed in time polynomial in $h$ and the size of $G$ and $H$, namely $O(kn^{7})$ where $n=\max(\left|V(G)\right|,\left|V(H)\right|)$.

The computational advantage of using unbalanced optimal transport, tipped the scales in favor it, making it the main focus of this paper.

###### Lemma 6 .

###### Theorem 20 .

## Appendix K Experimental Evaluation

We present here additional experimental results. We evaluate $\delta_{\rm DIDM}^{2}$ in graph classification
tasks, i.e., graphs separation tasks.
We follow the same set up in Chen et al. [], Böker et al. [] for comparison.

### K.1 1-nearest-neighbor classifier

Specifically, we use MUTAG dataset [Morris et al., ] and follow the
same random data split(^2^22we use 90 percent of the data for training and 10 percent of the data for testing.) in Chen et al. [], Böker et al. []. We use random split and repeat ten times. We start by computing the pairwise distances for all the graphs in each of the mentioned datasets. We continue by performing graph classification using a 1-nearest-neighbor classifier ($1$-NN). This classifier classifies
the test graph using the label of the closest training graph. Table 1 shows the mean classification accuracy of 1-NN using $\delta_{\rm DIDM}^{2}$, $\delta_{\text{W},3}$ and $\delta_{\text{W},\geq 3}$ from Böker et al. [], $d^{(3)}_{\text{WL}}$ and $d^{(3)}_{\text{WLLB},\geq 3}$ from Chen et al. [] using node degrees as initial labels and $\delta_{\rm DIDM}^{3}$ from Chuang and Jegelka [].

**Table 1: Graph distances classification accuracy of $1$-NN. $\delta_{\text{W},3}$ and $\delta_{\text{W},\geq 3}$ results are taken from Böker et al. []. $d^{(3)}_{\text{WL}}$ and $d^{(3)}_{\text{WLLB},\geq 3}$ results are taken from Chen et al. [] using node degrees as initial labels.**
| Accuracy $\uparrow$ | MUTAG |
| --- | --- |
| Chen et al. [] $d^{(3)}_{\text{WL}}$ | 91.1 $\pm$ 4.3 |
| Chen et al. [] $d^{(3)}_{\text{WLLB},\geq 3}$ | 85.2 $\pm$ 3.5 |
| Böker et al. [] $\delta_{\text{W},3}$ | 87.89 $\pm$ 4.11 |
| Böker et al. [] $\delta_{\text{W},\geq 3}$ | 86.32 $\pm$ 4.21 |
| Chuang and Jegelka [] $\mathbf{TMD}^{3}$ | 89.47 $\pm$ 7.81 |
| $\delta_{\rm DIDM}^{2}$ | 89.47 $\pm$ 7.81 |

Figure: Figure 4: in the top six figures, a convergent sequence of graphs with a constant signal, in the button six figures, the same graph sequence with signal values sampled from a normal distribution.
Refer to caption: x4.png

Figure: Figure 5: On the top row of figures, the correlation graph of a single MPNN is presented. On the middle row of figures, the correlation graph of the max of 100 MPNNs is presented. On the bottom row of figures, the correlation graph of the mean of 100 MPNNs is presented.
Refer to caption: x5.png

### K.2 mean versus max

We notice the graphs generated from one random MPNN and the graph generated from the maximum of 100 MPNNs, are not very far apart from each other. Therefore, we decided to compare the MUTAG correlation graph of normalized $\delta_{\rm DIDM}^{2}$ with the maximal normalized distance of $100$ MPNNs’ vectorical representation distances, with the MUTAG correlation graphs of normalized $\delta_{\rm DIDM}^{2}$ with the normalized distance of a single MPNNs’ vectorical representation and the mean normalized distance of $100$ MPNNs’ vectorical representation distances. The results are presented in Figure 5. Surprisingly, The mean and the max graphs look similar. This leads us to the hypothesis that ramdomly initialized MPNNs behave closely in the same way.

### K.3 Varying the Number of Layers

As in Section 4, we empirically test the correlation between $\delta_{\rm DIDM}$ and the output of MPNNs. Using stochastic block models $\text{SBM}(p,q_{i})$, with $p=0.5$ and $q_{i}\in[0.1,0.5]$ increasing equidistantly, we generated, a sequence of $50$ random graphs $\{G_{i}\}^{49}_{i=0}$, each with 30 vertices. We compare $\delta_{\rm DIDM}^{2}(G_{i},G)$, computed via a linear program, with random MPNNs’ outputs. Note that the limit graph, $G_{49}$, is sampled from an Erdős Rényi model, i.e., $G\sim\text{ER}(p).$ We conducted the experiment twice, once with a constant signal attached and once with signal values sampled from a normal distribution $\mathcal{N}(\mu,\sigma)$ with $\mu=1$ and $\sigma=\frac{50-i}{50}$, i.e., signal values that converge to a constant signal when $i\to\infty$ and are close to it for $i=49$. Figure 4, shows the results when varying the number of layers. The results show a strong correlation between input distance and GNN outputs.

## Appendix L List of Notations

Sets and Graphs

| $\displaystyle\mathcal{A}\times\mathcal{C}$ | The cartesian product of two sets $\mathcal{A}$ and $\mathcal{C}$ |
| --- | --- |
| $\displaystyle\mathbb{N}$ | The set of natural numbers (including 0) |
| $\displaystyle\mathbb{R}$ | The set of real numbers |
| $\displaystyle\mathbb{R}^{d}$ | The set of real vectors of length d |
| $\displaystyle\mathcal{K}^{d}$ | A compact sub-set of $\mathbb{R}^{d}$, (page 2) |
| $\displaystyle\mathcal{X}$ | A space (either metric, topological, or measure) |
| $\displaystyle\mathcal{Y}$ | A space (either metric, topological, or measure) |
| $\displaystyle C_{b}(\mathcal{X})$ | The set of all bounded continuous real-valued functions on $\mathcal{X}$, (page 2) |
| $\displaystyle C(\mathcal{X},\mathcal{Y})$ | The set of all continuous functions from $\mathcal{X}$ to $\mathcal{Y}$ |
| $\displaystyle\mathcal{K}$ | A compact space |
| $\displaystyle\{0,1\}$ | The set containing 0 and 1 |
| $\displaystyle\{0,1,\dots,n\}$ | The set of all integers between 0 0 and $n$ |
| $\displaystyle[n]$ | The set of all integers between 0 0 and $n$ |
| $\displaystyle[a,b]$ | The real interval including $a$ and $b$ |
| $\displaystyle I$ | A real interval |
| $\displaystyle(a,b]$ | The real interval excluding $a$ but including $b$ |
| $\displaystyle(G,\mathbf{f})$ | A graph-signal |
| $\displaystyle(H,,\mathbf{f})$ | A graph-signal |
| $\displaystyle(W,f)$ | A graphon-signal |
| $\displaystyle(Q,g)$ | A graphon-signal |
| $\displaystyle V(G)$ | The set of nodes of the graph G |
| $\displaystyle V(W)$ | The set of nodes of the graphon W |
| $\displaystyle E(W)$ | The set of edges of the graphon W |
| $\displaystyle\mathcal{N}(v)$ | The set of all neighboring nodes of a graph node $v$ |

Calculus

| $\displaystyle\int f({\bm{x}})d{\bm{x}}$ | Definite integral over the entire domain of ${\bm{x}}$ |
| --- | --- |
| $\displaystyle\int_{\mathcal{S}}f({\bm{x}})d{\bm{x}}$ | Definite integral with respect to ${\bm{x}}$ over the set $\mathcal{S}$ |

Numbers and Arrays

| $\displaystyle x$ | Element of a set, can be both a scalar or a vector |
| --- | --- |
| $\displaystyle{a}_{i}$ | Element $i$ of vector or a sequence |
| $\displaystyle C$ | A matrix |
| $\displaystyle D$ | A matrix |
| $\displaystyle{\bm{X}}$ | A random (either multi or single) variable |

Measure Theory and Iterated degree Measures

| $\displaystyle\mu$ | Either a measure or a iterated degree measure (DIDMs are measures) |
| --- | --- |
| $\displaystyle\nu$ | Either a measure or a iterated degree measure (DIDMs are measures) |
| $\displaystyle\gamma$ | Either a measure or a iterated degree measure (DIDMs are measures) |
| $\displaystyle f_{*}\mu$ | the push-forward of a measure $\mu\in\mathscr{M}(\mathcal{X})$ via a measurable map $f:\mathcal{X}\to\mathcal{Y}$ |
| $\displaystyle\mu_{i}$ | Element $i$ of an IDM $\mu$ |
| $\displaystyle\mu(i)$ | Element $i$ of an IDM $\mu$ |
| $\displaystyle\mathcal{F}$ | A $\sigma$-algebra |
| $\displaystyle\Sigma$ | A $\sigma$-algebra |
| $\displaystyle\mathcal{B}(\mathcal{X})$ | The standard Borel $\sigma$-algebra of a measurable space $\mathcal{X}$ |
| $\displaystyle(\mathcal{X},\Sigma)$ | a mesurable space |
| $\displaystyle(\mathcal{X},\Sigma,\mu)$ | a measure space |
| $\displaystyle\mathscr{M}_{\leq 1}(\mathcal{X})$ | The space of all non negative Borel measures with total mass at most one on $(\mathcal{X},\mathcal{B}(\mathcal{X}))$ |
| $\displaystyle\mathscr{P}(\mathcal{X})$ | The space of all Borel probability measures on $(\mathcal{X},\mathcal{B}(\mathcal{X}))$ |
| $\displaystyle\mathcal{H}^{d}$ | The space of iterated degree measures (IDMs) of order d |
| $\displaystyle\mathscr{P}(\mathcal{H}^{d})$ | The space of distributions of iterated degree measures (DIDMs) of order d |

Metrics

| $\displaystyle d$ | A metric |
| --- | --- |
| $\displaystyle||{\bm{x}}||_{p}$ | $\ell_{p}$ norm of ${\bm{x}}$ |
| $\displaystyle||{\bm{x}}||_{\infty}$ | the infinity norm of ${\bm{x}}$ |
| $\displaystyle\mathbf{OT}_{d}$ | Optimal transport with respect to the distance function $d$ |
| $\displaystyle d_{\rm IDM}$ | IDM Mover |
| $\displaystyle\delta_{\rm DIDM}$ | DIDM Mover’s distance |
| $\displaystyle\mathbf{P}_{d}$ | Prokhorov metric with respect to the distance function $d$ |
| $\displaystyle\mathbf{PD}$ | Prokhorov distance |
| $\displaystyle\mathbf{TPD}$ | Tree Prokhorov’s distance |

Probability and Information Theory

| $\displaystyle\mathcal{N}({\bm{\mu}},{\bm{\Sigma}})$ | Gaussian distribution with mean ${\bm{\mu}}$ and covariance ${\bm{\Sigma}}$ |
| --- | --- |

Functions

| $\displaystyle f:\mathcal{A}\rightarrow\mathcal{C}$ | The function $f$ with domain $\mathcal{A}$ and range $\mathcal{C}$ |
| --- | --- |
| $\displaystyle f(x)$ | The function $f$ evaluated at a point $x$ |
| $\displaystyle f(-)$ | The function $f$ evaluated at some point |
| $\displaystyle f_{-}$ | The function $f$ evaluated at some point |
| $\displaystyle f\circ g$ | Composition of the functions $f$ and $g$ |
| $\displaystyle\log x$ | Natural logarithm of $x$ |
| $\displaystyle\mathbbm{1}_{\mathrm{condition}}$ | is 1 if the condition is true, 0 otherwise |
| $\displaystyle\hat{\mathcal{R}}$ | the empirical risk |
| $\displaystyle\mathcal{R}$ | the statistical risk |

Message Passing Neural Networks

| $\displaystyle\varphi$ | A $L$-layer MPNN model |
| --- | --- |
| $\displaystyle(\varphi,\psi)$ | A $L$-layer MPNN model with $\psi$ a readout function |
| $\displaystyle\varphi^{(t)}$ | An update function |
| $\displaystyle\psi$ | An readout function |
| $\displaystyle\mathfrak{g}^{(t)}_{-}$ | $L$-layer MPNN model graph-signal feutures for $t\in[L]$ |
| $\displaystyle\mathfrak{G}$ | $L$-layer MPNN model with readout graph-signal feutures |
| $\displaystyle\mathfrak{f}^{(t)}_{-}$ | $L$-layer MPNN model graphon-signal feutures for $t\in[L]$ |
| $\displaystyle\mathfrak{F}$ | $L$-layer MPNN model with readout graphon-signal feutures |
| $\displaystyle\mathfrak{h}^{(t)}_{-}$ | $L$-layer MPNN model IDM feutures for $t\in[L]$ |
| $\displaystyle\mathfrak{H}$ | $L$-layer MPNN model with readout DIDM feutures |

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 2
questions: 1. The proposed metric considers attributed graphs, but in Fig 2, why is the alignment worsen when added attributes? 
2. Can the results be used to analyse more power GNNs? e.g. k-GNN, F-MPNN, etc
3. Unifying graph and graphon MPNN means you have to assume normalised sum aggregation, can this assumption be removed?
4. If not considering graphons, can this results apply to sparse graphs?
5. How is the metric related to the metric in "Weisfeiler-lehman meets gromov-Wasserstein."?
6. Why do you use Unbalance OT instead of OT?
soundness: 4
strengths: * The proposed a noval pseudometric for graphs based on iterated degree measures and optimal transport.
* The authors show MPNNs are universal and Lipschitz under this pseudometric.
* The authors show a bidirectional connections between the metric and MPNN output.
* A generalisation theorem is developed based the metric.
* The framework unifies MPNNs on graph and graphon.
summary: The authors propose a metric based on optimal transport distances between graph representations.
Under this metric, the authors show the MPNNs are Lipschitz and graph rerpesentations are compact. They establish that GNNs are capable of separating attributed graphs that are distant in the defined metric, leading to a universal approximation theorem and generalization bounds for MPNNs. Building on these, the authors further developed a generalisation theorem.  Empirical results demonstrate the correlation between the new metric and MPNN output.
weaknesses: * The proposed metric only applies to MPNN/1-WL GNNs, and cannot be used to analyse more powerful GNNs. 
* Related works are insufficiently discussed. In particualr, the proposed metric seems realted to [1][2], but this connection has not been discussed.
* The metric is expensive to compute, while its complexity is linear to $L$, it is in the order of $n^5$ which hinders its practicality
* The MPNN analysis limits to normalized sum aggregation, which is less commonly used.
* There are too many similar notations and symbols, making it difficult to follow. 
* The graphon-based approach means the results do not apply to sparse graphs.
* Emperiments are limited to one small real-world dataset (MUTAG), which makes the results less convincing.




[1] Chen, Samantha, et al. "The Weisfeiler-Lehman distance: Reinterpretation and connection with gnns." Topological, Algebraic and Geometric Learning Workshops 2023. PMLR, 2023.
[2] Chen, Samantha, et al. "Weisfeiler-lehman meets gromov-Wasserstein." International Conference on Machine Learning. PMLR, 2022.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: 1.  While the paper provides some empirical results, the evaluation could be expanded to offer deeper insights into practical applications and better demonstrate the efficacy of the proposed method. Have the authors considered evaluating TMD on additional graph classification benchmarks beyond MUTAG? Comparing TMD against other graph similarity metrics on tasks like graph matching or clustering could also strengthen the empirical evaluation. Furthermore, could the authors provide more detailed explanations of the experimental settings and parameter choices？

2. In Table 1, it would be helpful to clarify the organization and naming of the columns, as the label “Accuracy” appears to represent results across multiple methods. Providing a clearer breakdown of the results, along with an analysis that contextualizes each method’s performance, would enhance understanding. For example, if the statistics below MUTAG represent accuracy scores, they suggest that TMD does not significantly outperform some existing methods, such as Chen et al. (2022)’s  d^{(3)}_{WL} . A discussion of how TMD compares to these methods and whether additional datasets were considered may add further depth to the results.

3.  Structuring the manuscript to more prominently summarize the major findings and their impact would improve readability. Perhaps revise the contribution part in the introduction to better summarize the major findings. Also, perhaps adding a section to state the broader impact of these findings more clearly and how each finding advances the field of GNN theory to better illustrate the importance of this work. 

4. The methods primarily focus on dense graphs, as noted in the conclusion that “sparse graphs are always considered close to the empty graph under our metrics.” A further explanation of this limitation—specifically, why sparse graphs exhibit this behavior under TMD—would benefit the reader. Additionally, a discussion of whether this limitation affects the method’s generality and its potential applications to sparse graph domains would strengthen the paper.
soundness: 4
strengths: 1. The theoretical analysis is solid and thorough.
2. This work enhances the understanding of GNNs. The work introduces a new framework that unifies generalization and expressivity theories for attributed graphs, a notable achievement in GNN research.
3. The idea of introducing OT to this problem is quite novel and fancy.
summary: This paper develops a comprehensive theoretical framework that enhances the understanding of generalization, expressivity, and universality in Graph Neural Networks (GNNs) when applied to attributed graphs (graphs with node features). The central contribution is the introduction of a new metric, the Tree Mover’s Distance (TMD), designed to precisely measure the similarity between graphs by capturing both their structural and attribute-based characteristics. Key findings of this paper include the design of TMD,  the universal approximation of GNNs, and the analysis of the expressivity of GNNs.
weaknesses: See the questions below.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Can your theoretical analysis extend to the node classification problem?

2. Is Theorem 7 related to any distance metric proposed in Sections 3 and 4? If not, can the analysis in Sections 3 and 4 be used to derive a generalization bound?
soundness: 3
strengths: 1. The theoretical analysis is solid and strong. Especially, this work tries to provide an analysis that is as universal as possible with the fewest assumptions. 
2. The discussion of MPNNs and tree mover's distance in Section 4 is interesting and novel to me.
summary: This paper theoretically shows that the closeness of two graphs by MPNNs can be represented by the proposed metrics based on Wasserstein Distance. This work also shows the existence of MPNNs that can separate two graphs with non-zero distance and can approximate any functions over the space of graphs. A bound of generalization gap is also provided for MPNNs with milder assumptions.
weaknesses: 1. The presentation is a bit strange. The main results in Section 5 appear too late on almost page 9 in the main body of the paper. Moreover, the universal approximation and the generalization bound seem independent of the previous analysis of graph/graphon distances. It is better to move Section 5 earlier and elaborate more about the connections with previous sections. 

2. Section 5 is not insightful enough. For example, although Theorem 7 makes contributions by requiring fewer assumptions, experiments in Figure 3 show that the generalization error is still related to the covering number and the Lipschitz constant, which is unsurprising and known in generalization theory. 

3. Some references on the generalization error of MPNNs are missing. 

Oono, K. and Suzuki, T. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. Neurips 2020.

Li et al., 2022. Generalization guarantee of training graph convolutional networks with graph topology sampling. ICML 2022.

Tang et al., 2023. Towards understanding the generalization of graph neural networks. ICML 2023.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: Can the authors provide a motivation for the choice of GINs and GraphConvs for the empirical evaluation?
Can the authors provide a short discussion of the results of the empirical evaluation over the generalization bound?
soundness: 4
strengths: This manuscript provides a solid theoretical analysis of message passing GNNs under the framework of attributed graphons. The framework studies many properties, from universal approximation to generalization capabilities, therefore yielding a comprehensive overview of message passing GNNs that integrates in several ways the contribution already present in literature.
summary: The present manuscript studies the approximation and generalization capabilities of message passing GNNs on attributed graphs under the lens of  proposed pseudometrics, based on the Wasserstein distance between distributions of computation tree analogs over graphons. It is demonstrated that such a pseudo metric leads to the characterization of a topology that allows to prove that message passing GNNs are universal approximations over attributed graphons, which are the fine-grained version of attributed graphs. Furthermore,  bounds on the generalization capability are provided exploiting the compactness and the lipschitzness of the retrieved topology. The theoretical findings are supported by an extensive experimental framework.
weaknesses: It is not explained why GINs and GraphConvs where chosen for the empirical evaluation, among the large class of message passing GNNs present in literature. I would suggest to discuss whether GIN and GraphConv are representative of different types of MPNNs, or if they have properties that make them particularly suitable for evaluating the theoretical results. 

A (short) discussion of the results of the empirical evaluation over the generalization bound is missing. I would suggest to discuss how closely the empirical results align with the theoretical bound, also considering the statistical nature of the task, or if there are any unexpected patterns or discrepancies that needs some careful consideration and warrant further investigation.

Meta-review: This paper proposes a new pseudo-metric on message passing GNNs on attributed graphs, based on the Wasserstein distance between distributions of computation tree analogs over graphons. The paper proves that message passing GNNs are universal approximations over attributed graphons. A generalization capability bound is derived exploiting the compactness and the Lipschitzness properties of the model. A experimental evaluation is proposed.


Strengths:  
- a new pseudometric metric on graphs based on optimal transport,   
- message passing GNNs are universal and lipschitz,  
- generality of the framework, 
- solid theoretical work with a generalization bound,  
- unifies generalization and expressivity for GNN.  

Weaknesses:   
- framework limited to a subclass of GNN and better suited to dense graph,   
- the metric is costly,  
- experiments limited,  
- discussion with related work could be improved,  
- the presentation can be improved. 

During the rebuttal, authors have provided multiple answer to the issues raised by the reviewers.  
The reviewers have acknowledged the various answers provided and they were all satisfied with the answers.  

Overall, there was a consensus for saying that the paper must be accepted.  
I propose then acceptance.  

I encourage the authors to include in the final version all the comments provided by the reviewers.

Decision: Accept (Poster)