# Probability-graphons: Limits of large dense weighted graphs

Romain Abraham, Jean-François Delmas, Julien Weibel

<figure><img src="image_1.png" /></figure>

## To cite this version:

Romain Abraham, Jean-François Delmas, Julien Weibel. Probability-graphons: Limits of large dense weighted graphs. Innovations in Graph Theory, 2025, 2, pp.25-117. 10.5802/igt.7. hal-04361443v2

HAL Id: hal-04361443

https://hal.science/hal-04361443v2

Submitted on 18 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
PROBABILITY-GRAPHONS: LIMITS OF LARGE
DENSE WEIGHTED GRAPHS

by Romain ABRAHAM,
Jean-François DELMAS & Julien WEIBEL

ABSTRACT. — We introduce probability-graphons which are probability kernels that generalize graphons to the case of weighted graphs. Probability-graphons appear as the limit objects to study sequences of large weighted graphs whose distribution of subgraph sampling converge. The edge-weights are taken from a general Polish space, which also covers the case of decorated graphs. Here, graphs can be either directed or undirected. Starting from a distance $d_m$ inducing the weak topology on measures, we define a cut distance on probability-graphons, making it a Polish space, and study the properties of this cut distance. In particular, we exhibit a tightness criterion for probability-graphons related to relative compactness in the cut distance. We also prove that under some conditions on the distance $d_m$, which are satisfied for some well-known distances like the Lévy–Prokhorov distance, and the Fortet–Mourier and Kantorovitch–Rubinshtein norms, the topology induced by the cut distance on the space of probability-graphons is independent from the choice of $d_m$. Eventually, we prove that this topology coincides with the topology induced by the convergence in distribution of the sampled subgraphs.

# 1. Introduction

## 1.1. Motivation and literature review

Networks appear naturally in a wide variety of contexts, including for example: biological networks [19, 45], epidemics processes [21, 40], electrical power grids [1] and social networks [2, 50]. Most of those problems involve large dense graphs, that is graphs that have a large number of vertices and a number of edges that scales as the square of the number of vertices. Those graphs are too large to be represented entirely in the targeted applications.

**Keywords:** random graphs, stochastic networks, graphons, probability-graphons, dense graph limits, weighted graphs, decorated graphs.

2020 Mathematics Subject Classification: 05C80, 60B10.
The idea is then to go from a combinatorial representation given by the graph to an infinite continuum representation.

In the case of unweighted graphs (i.e. graphs without edge-weights), a theory was developed to study the asymptotic behaviour of large dense graphs, with the limit objects being the so-called *graphons*. The properties of graphons were studied in a series of articles started by [47, 26, 15, 16, 18]. We shall refer to the monograph [46] which exposes in details the theory of graphons developed in this series of articles. Graphons can be used to define models of random graphs with latent vertex-type variables (called *W*-random graphs) generalizing the Erdös-Rényi graph and the stochastic block model (SBM). The space of graphons can be equipped with the so-called *cut distance*, making it a compact space, and whose topology is that of the convergence in distribution for all sampled subgraphs, or equivalently of the convergence for subgraph homomorphism densities.

In recent years, graphons have been used in several application context: non-parametric estimation methods and algorithms for massive networks [17], SIS epidemic models [20], the study of transferability properties for Graph Neural Networks [39]. Furthermore, there has been recent developments in the study of mean-field systems using graphons: stochastic games and their Nash equilibria [43], opinion dynamic on a graphon [3], cooperative multi-agent reinforcement learning [32], to cite a few.

However, most real-world phenomena on the above networks involve weighted networks, where each edge in the graph carries additional information such as intensity or frequency of interaction, or transfer capacity.

There exists many models of random weighted graphs. For example configuration models with edges having independent exponential weights have been considered in [10, 5, 6], see also [29, 34] where the distribution of the weight of an edge depends on the types of its end-points. Random geometric graphs with vertices and edges having independent Gaussian weights have been considered in [4].

Weighted SBMs (sometimes also called labeled SBMs), in which each edge independently receives a random weight whose distribution depends on the community labels of its end-points, have been studied to solve community detection in [44] (see also [53] for more general models where vertex-labels come from a compact space), and exact community recovery in [36], and to get bounds on the number of misclassified vertices in [55, 54]. Note that weighted SBMs correspond to a special case of the probability-graphons we study in this article where the space of vertex-labels is finite.
(they correspond to the stepfunction probability-graphons we define in Section 3).

Concomitantly to our work, in [9], the authors studied mean-field equations on large real-weighted graphs modeling interactions with a probability kernel from $[0, 1]^2$ to $M_1(\mathbb{R})$ the set of probability measures on $\mathbb{R}$, but they did not study the topological properties of the set of those probability kernels. Recently, in [31], the authors studied the limit of the total weight of the minimum spanning tree (MST) for a sequence of random weighted graphs. Following what has been done for the uniform spanning tree in [30, 7], one expects the local and scaling limits of the MST to be directly constructed from the limit of the random weighted graphs.

Motivated by those examples, we shall consider probability-graphons as possible limits of large weighted graphs; they are defined as maps from $[0, 1]^2$ to the space of probability measures $M_1(\mathbb{Z})$ on a Polish space $\mathbb{Z}$. When $\mathbb{Z}$ is compact, this question has been considered in [49] and in [46, Section 17.1] using convergence of homomorphism densities of subgraphs decorated with real functions defined on $\mathbb{Z}$, see also [41] on multigraphs where $\mathbb{Z} = \mathbb{N}$, but the metric properties of the set of probability-graphons $W_1$ have only been established when $\mathbb{Z}$ is finite, see [25]. Concomitantly to our work, in [8], the authors established the metric properties for the set of probability-graphons $W_1$ when $\mathbb{Z} = [-1, 1]$, where they consider the Kantorovitch-Rubinshtein cut distance (denoted here by $\delta_{\square,KR}$). However their proof can not be extended directly to a general Polish space. The work [42] is an extension of [49] where $M_1(\mathbb{Z})$ is replaced by the dual space $\mathcal{Z}$ of a separable Banach space $\mathcal{B}$. As $M_1(\mathbb{Z})$ is a subset of the dual of the space $C_b(\mathbb{Z})$ of real-valued continuous bounded functions on $\mathbb{Z}$, this approach covers our setting when $C_b(\mathbb{Z})$ is separable, that is, $\mathbb{Z}$ compact (see Section 2 below). The norm introduced on the space of $\mathcal{Z}$-valued graphons therein implies the convergence of homomorphisms densities of $\mathcal{B}$-decorated sub-graphs, however there is no equivalence *a priori*. In [28], probability-graphons with $\mathbb{Z} = [0, 1]$ are used as a part of latinons, which are limit objects for latin squares (square matrix of size $n \times n$ where each row and column contains each integer from 1 to $n$ exactly once). The authors propose an interesting method to prove compactness of the space of latinons for the cut distance; but this does not extend directly to the case of a general Polish space $\mathbb{Z}$.

In this paper we study the topological properties of the space of probability-graphons $\tilde{W}_1$ when $\mathbb{Z}$ is a general Polish space: the space $\tilde{W}_1$ is
a Polish topological space and we give “natural” cut distances on $\tilde{W}_1$ which are complete. One of the main difficulties is that the space of probability measures $M_1(\mathbb{Z})$ can be endowed with many distances which induce the topology of weak convergence, each of them giving rise to a different cut distance on $\tilde{W}_1$. Our main result is:

a) The topology induced on $\tilde{W}_1$ does not depend on the initial choice of the distance on $M_1(\mathbb{Z})$, provided this distance satisfies some simple general conditions. Those conditions are satisfied if the distance is *quasi-convex* (a property that generalizes the convexity of a norm).

b) This topology coincides with the topology induced by the convergence in distribution of the sampled subgraphs with random weights on the edges (or equivalently the convergence of the homomorphism densities of $C_b(\mathbb{Z})$-decorated subgraphs).

c) Similarly to the graphon setting, the sequence of large sampled weighted subgraphs from a probability-graphon $W$ convergence in distribution to $W$.

d) We also provide a tightness criterion for studying the convergence of weighted graphs towards probability-graphons.

In conclusion, we believe that the unified framework developed here is easy-to-work-with and will allow to use probability-graphons to study large (random) weighted graphs.

## 1.2. New contribution

Through the article, *measure* will always be used to denote a positive measure.

### 1.2.1. Definition of probability-graphons

In this article, we define an analogue of graphons for weighted graphs, which we call *probability-graphons*, and study their properties. To avoid any confusion, in the rest of the article we say *real-valued graphons* instead of graphons. We consider the general case where weighted graphs take their edge-weights in a Polish space $\mathbb{Z}$ (e.g. $\mathbb{Z}$, $\mathbb{R}$ or $\mathbb{R}^d$), which thus also covers the case of decorated graphs, multi-graphs (graphs with possibly multiple edges between two vertices) and dynamical graphs (where edge-weights evolve over time).

We define a *probability-graphon* as a probability kernel $W : [0, 1]^2 \rightarrow M_1(\mathbb{Z})$, where $M_1(\mathbb{Z})$ is the space of probability measures on $\mathbb{Z}$. A
probability-graphon can be interpreted as follows: for two “vertex type”
$x$ and $y$ in $[0, 1]$, the weight $z$ of an edge between two vertices of type
$x$ and $y$ is distributed as the probability measure $W(x, y; dz)$. In partic-
ular, the special case $\mathbb{Z} = \{0, 1\}$ allows to recover real-valued graphons:
as any real-valued graphon $w : [0, 1]^2 \to [0, 1]$ can be represented as a
probability-graphon $W(x, y; \cdot) = w(x, y)\delta_1 + (1 - w(x, y))\delta_0$, where $\delta_z$
denotes the Dirac mass located at $z$. Let us mention that it is possible to de-
fine the probability-graphons on a more general probability space $(\Omega, \mathcal{A}, \mu)$
than $[0, 1]$ for the vertex-types, see Remark 3.4 for details. In this article,
we also define and study the properties of *signed measure-valued kernels*
which are bounded (in total mass/total variation norm) measurable func-
tions $W : [0, 1]^2 \to \mathcal{M}_{\pm}(\mathbb{Z})$ whose values are signed measures, but for
brevity we mainly focus on probability-graphons in this introduction.

As probability-graphons are measurable functions, we identify
probability-graphons that are equal for almost every $(x, y) \in [0, 1]^2$, and
we denote by $W_1$ the space of probability-graphons. Moreover, as we con-
sider weighted graphs that are unlabeled (that is vertices are unordered),
we need to consider probability-graphons up to “relabeling”: for a measure-
preserving map $\varphi : [0, 1] \to [0, 1]$ (relabeling map for probability-graphons),
we define $W^\varphi(x, y; \cdot) = W(\varphi(x), \varphi(y); \cdot)$; we say that two probability-
graphons are weakly isomorphic if there exists measure-preserving maps
$\varphi, \psi : [0, 1] \to [0, 1]$ such that $U^\varphi = W^\psi$ for a.e. $(x, y) \in [0, 1]^2$. We denote
by $\tilde{W}_1$ the space of probability-graphons where we identify probability-
graphons that are weakly isomorphic.

We can always assume that weighted graphs are complete graphs by
adding all missing edges and giving them a weight/decoration $\partial$ which is a
cemetery point added to $\mathbb{Z}$. Any weighted graph $G$ can be represented as a
probability-graphon $W_G$ in the following way: denote by $n$ the number of
vertices of $G$ and divide the unit interval $[0, 1]$ into $n$ intervals $I_1, \cdots, I_n$ of
equal lengths, then $W_G$ is defined for $(x, y) \in I_i \times I_j$ as $W_G(x, y; \cdot) = \delta_{M(i,j)}$,
where $M(i, j)$ is the weight on the edge $(i, j)$ in $G$. Thus a weighted graph
$G$, with its edges decorated by elements of $\mathbb{Z}$, is associated with a $M_1(\mathbb{Z})$-
valued graphon $W_G$ where the decorations are replaced by the correspond-
ing Dirac masses. Note that weighted graphs can be either directed or
undirected, in the case of undirected weighted graphs their limit objects
are symmetric probability-graphons, that is probability-graphons $W$ such
that $W(x, y; \cdot) = W(y, x; \cdot)$.
### 1.2.2. The cut distance for probability-graphons and its properties

While there is a usual distance on the field of reals $\mathbb{R}$, this is not the case for probability measures, measures or signed measures endowed with the weak topology. Some commonly used distances include the Lévy–Prokhorov distance $d_{LP}$ which can be defined on measures, and the Kantorovitch–Rubinshtein norm $|| \cdot ||_{KR}$ (sometimes also called the bounded Lipschitz norm) and the Fortet–Mourier norm $|| \cdot ||_{FM}$ defined on signed measures but metrizing the weak topology on measures. (Note that in general the weak topology is not metrizable on signed measures, see Section 2 below.) We also use a norm $|| \cdot ||_{F}$ based on a convergence determining sequence $F \subset C_b(\mathbf{Z})$ (that is, a sequence containing enough functions to characterize the convergence of measures for the weak topology, see page 37 for a more formal definition). See Section 3.8 for definitions of those distances. To define an analogue of the cut norm for probability-graphons, we first need to choose a distance $d_m$ that metrizes the weak topology on the space of sub-probability measures $M_{\le 1}(\mathbf{Z})$ (i.e. measures with total mass at most 1); we then define the cut distance $d_{\square,m}$ for probability-graphons as:

$$d_{\square,m}(U, W) = \sup_{S,T \subset [0,1]} d_m(U(S \times T; \cdot), W(S \times T; \cdot)),$$

where the supremum is taken over all measurable subsets $S$ and $T$ of $[0, 1]$, and where $W(S \times T; \cdot) = \int_{S \times T} W(x, y; \cdot) dxdy$ is a sub-probability measure, and similarly for $U$. Moreover, if the distance $d_m$ is derived from a norm $N_m$ defined on the space of signed measures $M_{\pm}(\mathbf{Z})$, then the cut distance $d_{\square,m}$ derives from the cut norm $N_{\square,m}$ defined on signed measure-valued kernels:

$$N_{\square,m}(W) = \sup_{S,T \subset [0,1]} N_m(W(S \times T; \cdot)).$$

We then define the unlabeled cut distance $\delta_{\square,m}$ on the space of unlabeled probability-graphons $\tilde{W}_1$ as:

$$\delta_{\square,m}(U, W) = \inf_{\varphi} d_{\square,m}(U, W^{\varphi}) = \min_{\varphi, \psi} d_{\square,m}(U^{\varphi}, W^{\psi}),$$

where the infimum is taken over all measure-preserving maps $\varphi$ and $\psi$, see Proposition 3.18 for alternative expressions of $\delta_{\square,m}$ (including proof that the minimum exists for the second expression) and see Theorem 3.17 that states that $\delta_{\square,m}$ is indeed a distance on $\tilde{W}_1$. In Proposition 4.13, we prove an equivalent of the weak regularity lemma for probability-graphons.

We define the notion of a quasi-convex distance, which generalizes the convexity of a norm.
**DEFINITION 1.1 (Quasi-convex distance).** — Let $(X, d)$ be a metric space which is a convex subset of a vector space. The distance $d$ is quasi-convex if for all $x_1, x_2, y_1, y_2 \in X$ and all $\alpha \in [0, 1]$, we have:

$$d(\alpha x_1 + (1 - \alpha)x_2, \alpha y_1 + (1 - \alpha)y_2) \leq \max(d(x_1, y_1), d(x_2, y_2)).$$

In particular, any distance (on a convex subset of a vector space) which
derive from a norm is quasi-convex. Moreover, the Lévy–Prokhorov distance
$d_{LP}$ is quasi-convex (see Lemma 3.21).

An interesting fact is that under some conditions on $d_m$ (including the
case when $d_m$ is quasi-convex), the topology induced by the associated cut
distance $\delta_{\square,m}$ does not depend on the particular choice of $d_m$. The following
proposition is a particular case of Theorem 5.5 together with Corollary 4.14.

**PROPOSITION 1.2.** — Let $d_m$ be a quasi-convex distance on $M_{\le 1}(\mathbb{Z})$ that induces the weak topology. The cut distances $\delta_{\square,m}$, $\delta_{\square,LP}$, $\delta_{\square,KR}$, $\delta_{\square,FM}$ and $\delta_{\square,F}$ induce the same topology on the space of probability-graphons $\widetilde{W}_1$.

Recall that $\mathbb{Z}$ is a Polish space. We now state that $\widetilde{W}_1$ is also Polish for the distance $\delta_{\square,LP}$ (but not for $\delta_{\square,F}$!), and we refer to Theorem 5.10 for other distances.

**THEOREM 1.3.** — The space of probability-graphons $(\widetilde{W}_1, \delta_{\square,LP})$ is a Polish metric space.

We prove an analogue of Prokhorov’s theorem with a tightness criterion for probability-graphons. We say that a subset of probability-graphons $\mathcal{K} \subset \widetilde{W}_1$ is *tight* if the set of probability measures $\{M_W : W \in \mathcal{K}\}$ is tight (in the sense of probability measures), where $M_W(\cdot) = W([0, 1]^2; \cdot)$. This tightness criterion appears in [41] for multigraphs, corresponding to the particular case $\mathbb{Z} = \mathbb{N}$. The next result is consequence of Theorem 5.1 and Proposition 5.2 as well as Corollary 4.14.

**THEOREM 1.4 (Compactness property).** — Consider the topology on $\widetilde{W}_1$ from Proposition 1.2.

(i) If a sequence of elements of $\widetilde{W}_1$ is tight, then it has a converging subsequence.

(ii) A subset $\mathcal{K} \subset \widetilde{W}_1$ is relatively compact is and only if it is tight.

(iii) If $\mathbb{Z}$ is compact, then the space $\widetilde{W}_1$ is compact.
1.2.3. Sampling from probability-graphons and its link with the cut distance

Finally, we link the topology of the cut distance $\delta_{\square,m}$ with subgraph sampling. The probability-graphons allow to define models of random weighted graphs (the W-random graph model) which generalize weighted SBM random graphs, and which plays the role of sampled subgraphs for probability-graphons. The W-random graph (or sampled subgraph of size $k$) $\mathbb{G}(k, W)$ has two parameters, a number of vertices $k$ and a probability-graphon $W$ for edge-weights, and is defined as follows: first let $X_1, \cdots, X_k$ be $k$ independent random “vertex-types” uniformly distributed over $[0, 1]$; then given $X_1, \cdots, X_k$, each edge receives a weight independently, where the weight of the edge $(i, j)$ is distributed as $W(X_i, X_j; \cdot)$. By identifying $z \in \mathbb{Z}$ with the Dirac mass at $z$, we can identify the random weighted graph $\mathbb{G}(k, W)$ with its corresponding probability-graphon (see Section 1.2.1), notice that this random probability-graphon is unique up to a weak isomorphism, and with a slight abuse we shall denote it by $\mathbb{G}(k, W)$.

We also provide the a.s. convergence of sampled subgraphs for the topology from Proposition 1.2, see Theorem 6.13 together with Corollary 5.6.

**THEOREM 1.5.** — Let $W$ be a probability-graphon. Then, a.s. the sequence of sampled subgraphs $(\mathbb{G}(k, W))_{k \in \mathbb{N}^*}$ converges to $W$ for the topology from Proposition 1.2.

To prove this theorem, we adapt the proof scheme of [46, Sections 10.5 and 10.6] relying on the first and second sampling lemmas for real-valued graphons. The proof is done using the cut distance $\delta_{\square,\mathcal{F}}$ because of the good approximation properties of $\| \cdot \|_{\mathcal{F}}$.

In the case of unweighted graphs, the homomorphism numbers $\text{hom}(F, G)$ count the number of occurences of a graph $F$ (often called a *motif* or a *graphlet*) as an induced subgraph of $G$, and their normalized counterparts, the homomorphism densities $t(F, G)$ allow to characterize a graph (up to relabeling and twin-vertices expansion), and also characterize the topology on real-valued graphons. In the case of weighted graphs and probability-graphons, we need to replace absence/presence of edges (which is 0-1 valued) by test functions from $C_b(\mathbb{Z})$ decorating the edges. Hence, we define the *homomorphism density* of a *G*-graph $F^g$ which is a finite graph $F = (V, E)$ whose edges are decorated with a family of functions $g = (g_e)_{e \in E}$ from a subset $\mathcal{G} \subset C_b(\mathbb{Z})$ (in practice, we only consider the cases $\mathcal{G} = C_b(\mathbb{Z})$ or $\mathcal{G} = \mathcal{F} \subset C_b(\mathbb{Z})$ a convergence determining sequence),
in a probability-graphon W as:

$$t(F^g, W) = M_W^F(g) := \int_{[0,1]^V} \prod_{(i,j) \in E} W(x_i, x_j; g_{i,j}) \prod_{i \in V} dx_i,$$

where $W(x, y; f) = \int_Z f(z) W(x, y; dz)$. Moreover, $M_W^F$ defines a measure on $Z^E$ (which we still denote by $M_W^F$) which is defined by $M_W^F(\otimes_{e \in E} g_e) = M_W^F(g)$ for $g = (g_e)_{e \in E}$. Note that when $F$ is the complete graph with $k$ vertices, $M_W^F$ is the joint measure of all the edge-weights of the random graph $G(k, W)$, and thus characterizes the random graph $\mathbb{G}(k, W)$.

In the counting Lemma 7.5 and the weak counting Lemma 7.7, we prove that the cut norm $\| \cdot \|_{\square, \mathcal{F}}$ allows to control the homomorphism densities. Conversely, in the inverse counting Lemma 7.8, we prove that the cut norm $\| \cdot \|_{\square, \mathcal{F}}$ can be controlled by the homomorphism densities. In particular, the topology of the cut distance turns out to be exactly the topology of convergence in distribution for sampled subgraphs of any given size; the next result is a direct consequence of Theorem 7.11.

**THEOREM 1.6 (Characterization of the topology).** — Let $(W_n)_{n \in \mathbb{N}}$ and $W$ be unlabeled probability-graphons from $\widetilde{W}_1$. The following properties are equivalent:

(i) $(W_n)_{n \in \mathbb{N}}$ converges to $W$ for the topology from Proposition 1.2.

(ii) $\lim_{n \to \infty} t(F^g, W_n) = t(F^g, W)$ for all $C_b(Z)$-graphs $F^g$.

(iii) $\lim_{n \to \infty} t(F^g, W_n) = t(F^g, W)$ for all $\mathcal{F}$-graphs $F^g$, for some convergence determining sequence $\mathcal{F}$.

(iv) For all $k \ge 2$, the sequence of sampled subgraphs $(\mathbb{G}(k, W_n))_{n \in \mathbb{N}}$ converges in distribution to $\mathbb{G}(k, W)$.

Now, we can turn back to the initial problem of finding a limit object for a convergent sequence of weighted graphs $(G_n)_{n \in \mathbb{N}}$; here convergent means that for all $k \ge 2$, the sequence $(\mathbb{G}(k, G_n) = \mathbb{G}(k, W_{G_n}))_{n \in \mathbb{N}}$ of sampled subgraphs of size $k$ (defined above) converges in distribution (to some limit random graph). Note that the tightness criterion for a sequence of probability-graphons $(W_n)_{n \in \mathbb{N}}$ can be equivalently rephrased as tightness of the sequence $(\mathbb{G}(2, W_n))_{n \in \mathbb{N}}$ of sampled subgraphs of size 2. Hence, the convergence in distribution of the sequence $(\mathbb{G}(2, G_n))_{n \in \mathbb{N}}$ implies its tightness, and thus the tightness of the sequence of probability-graphons $(W_{G_n})_{n \in \mathbb{N}}$. Then, Theorem 1.4 guarantees the existence of a probability-graphon $W$ which is a subsequential limit of the sequence $(W_{G_n})_{n \in \mathbb{N}}$ in the cut distance $\delta_{\square, \mathcal{F}}$, and then Theorem 1.6 guarantees that for all $k \ge 2$, the sequence $(\mathbb{G}(k, G_n))_{n \in \mathbb{N}}$ converges in distribution to $\mathbb{G}(k, W)$.
As a consequence, probability-graphons are precisely the limit objects for sequences of weighted graphs $(G_n)_{n \in \mathbb{N}}$ (and also for random weighted graphs) whose number of vertices goes to infinity (otherwise the limit would simply be a weighted graph) and such that for each size $k \ge 2$, the sequence of sampled subgraphs $(\mathbb{G}(k, G_n))_{n \in \mathbb{N}}$ converges in distribution.

**Remark 1.7 (Extension to vertex-weights).** — The framework we have developed for probability-graphons could easily be extended to add weights on the vertices, or equivalently to allow for self-loops (i.e. edges linking a vertex to itself). In this case, weighted graphs and probability-graphons have a two-variable kernel (probability-graphon) $W^e$ for edge-weights as before, and a one-variable kernel $W^v : [0, 1] \to \mathcal{M}_1(\mathbf{Z})$ for vertex-weights. Note that this implies, as expected, that the same measure-preserving map $\varphi : [0, 1] \to [0, 1]$ must be used for both kernels $W^v$ and $W^e$ when relabeling.

### 1.3. Organization of the paper

The rest of the paper is organized as follows. In Section 2, we define some notations used throughout the paper, and recall some properties of the weak topology on the space of signed measures. In Section 3, we define probability-graphons and signed-measure valued kernels, we then define the cut distance and the cut norm and study their properties, and we also give some exemple of distances with the Lévy–Prokhorov distance $d_{LP}$, the Kanrorovitch-Rubinstein and Fortet–Mourier norms $\|\cdot\|_{KR}$ and $\|\cdot\|_{FM}$, and the norm $\|\cdot\|_{\mathcal{F}}$ based on a convergence determining sequence. In Section 4, we define the steppings of a probability-graphon (which are stepfunction approximations corresponding to conditional expectations on $[0, 1]^2$), we define the tightness criterion for probability-graphons, and we prove the weak regularity property of the cut distance. In Section 5, we prove the theorem linking the tightness criterion with relative compactness for the cut distance, we prove that under some conditions the topology of the cut distance does not depend on the choice of the initial distance $d_m$, and we prove that the space of probability-graphons with the cut distance is a Polish space. In Section 6, we define the subgraph $\mathbb{G}(k, W)$ sampled from a probability-graphon $W$, we then prove approximation bound in the cut norm $\|\cdot\|_{\square, \mathcal{F}}$ between probability-graphons and their sampled subgraphs. In Section 7, we prove the counting lemmas linking the cut distance with the homomorphism densities, and prove that the topology induced by the cut distance coincides with the topology of convergence in distribution for all the sampled subgraphs.
An index of notations used in the paper is provided in Section 9.

CONTENTS

<table><tr><td>1. Introduction</td><td>25</td></tr><tr><td>1.1. Motivation and literature review</td><td>25</td></tr><tr><td>1.2. New contribution</td><td>28</td></tr><tr><td>1.2.1. Definition of probability-graphons</td><td>28</td></tr><tr><td>1.2.2. The cut distance for probability-graphons and its properties</td><td>30</td></tr><tr><td>1.2.3. Sampling from probability-graphons and its link with the cut distance</td><td>32</td></tr><tr><td>1.3. Organization of the paper</td><td>34</td></tr><tr><td>2. Notations and topology on the space of signed measures</td><td>36</td></tr><tr><td>3. Measure-valued graphons and the cut distance</td><td>42</td></tr><tr><td>3.1. Definition of measure-valued graphons</td><td>42</td></tr><tr><td>3.2. The cut distance</td><td>44</td></tr><tr><td>3.3. Graphon relabeling, invariance and smoothness properties</td><td>46</td></tr><tr><td>3.4. The unlabeled cut distance</td><td>49</td></tr><tr><td>3.5. Weak isomorphism</td><td>50</td></tr><tr><td>3.6. The cut norm for stepfunctions</td><td>51</td></tr><tr><td>3.7. The supremum in S and T in the cut distance d<sub>□,m</sub></td><td>52</td></tr><tr><td>3.8. Examples of distance d<sub>m</sub></td><td>54</td></tr><tr><td>3.8.1. The Lévy–Prokhorov distance d<sub>LP</sub></td><td>55</td></tr><tr><td>3.8.2. The Kantorovitch–Rubinshtein and Fortet–Mourier norms</td><td>55</td></tr><tr><td>3.8.3. A norm based on a convergence determining sequence</td><td>56</td></tr><tr><td>4. Tightness and weak regularity</td><td>58</td></tr><tr><td>4.1. Approximation by stepfunctions</td><td>59</td></tr><tr><td>4.2. Tightness</td><td>61</td></tr><tr><td>4.3. Weak regularity</td><td>63</td></tr><tr><td>4.3.1. An example of cut distance regular w.r.t. the stepping operator</td><td>64</td></tr><tr><td>4.3.2. An example of weakly regular cut distance</td><td>65</td></tr><tr><td>4.4. A stronger weak regularity lemma for d<sub>□,F</sub></td><td>68</td></tr><tr><td>4.4.1. Comparison between ||·||<sub>□,F</sub> and an Euclidian norm</td><td>68</td></tr><tr><td>4.4.2. The weak regularity lemma for ||·||<sub>□,F</sub></td><td>69</td></tr><tr><td>5. Compactness and completeness of W&#771;<sub>1</sub></td><td>70</td></tr><tr><td>5.1. Tightness criterion and compactness</td><td>70</td></tr><tr><td>5.2. Equivalence of topologies induced by δ<sub>□,m</sub></td><td>72</td></tr><tr><td>5.3. Completeness</td><td>76</td></tr><tr><td>6. Sampling from probability-graphons</td><td>79</td></tr><tr><td>6.1. M<sub>1</sub>(Z)-Graphs and weighted graphs</td><td>80</td></tr><tr><td>6.2. W-random graphs</td><td>82</td></tr><tr><td>6.3. Estimation of the distance by sampling</td><td>83</td></tr><tr><td>6.3.1. The first sampling lemma</td><td>83</td></tr><tr><td>6.3.2. Approximation with random weighted graphs</td><td>85</td></tr><tr><td>6.4. The distance between a probability-graphon and its sample</td><td>87</td></tr><tr><td>7. The Counting Lemmas and the topology of probability-graphons</td><td>88</td></tr><tr><td>7.1. The homomorphism densities</td><td>88</td></tr><tr><td>7.2. The Counting Lemma</td><td>90</td></tr><tr><td>7.3. The Inverse Counting Lemma</td><td>91</td></tr><tr><td>7.4. Subgraph sampling and the topology of probability-graphons</td><td>93</td></tr><tr><td>8. Proofs of Theorem 5.1 and Theorem 5.5</td><td>96</td></tr><tr><td>9. Index of notations</td><td>111</td></tr><tr><td>Acknowledgement</td><td>113</td></tr><tr><td>Bibliography</td><td>113</td></tr></table>
## 2. Notations and topology on the space of signed measures

Throughout the article, *measure* will always be used to denote a positive measure.

Let $\mathbb{N}$ be the set of non-negative integers, $\mathbb{N}^* = \mathbb{N}\{0\}$ the set of positive integers, and, for $n \in \mathbb{N}^*$, we define the integer set $[n] = \{1, \dots, n\}$. For $k \in \mathbb{N}^*$, the set $[0, 1]^k$ is endowed with the Borel $\sigma$-field and the Lebesgue measure $\lambda_k$; and we write $\lambda$ for $\lambda_k$ when the context is clear. The supremum of a real-valued function $f$ defined on $[0, 1]^k$ is denoted by $\|f\|_{\infty} = \sup_{x \in [0,1]^k} f(x)$.

Let $d$ be a distance on a topological space $(X, \mathcal{O})$.

(i) The distance $d$ is *continuous* w.r.t. the topology $\mathcal{O}$ if the identity map from $(X, \mathcal{O})$ to $(X, d)$ is continuous.

(ii) The distance $d$ is *sequentially continuous* w.r.t. the topology $\mathcal{O}$ if for any sequence $(x_n)_{n \in \mathbb{N}}$ in $X$ which converges to some limit $x$ for the topology $\mathcal{O}$, we also have that $\lim_{n \to \infty} d(x_n, x) = 0$.

Let $d$ and $d'$ be two distances on a space $X$. We say that $d'$ is continuous (resp. uniformly continuous) w.r.t. $d$ if the identity map from $(X, d)$ to $(X, d')$ is continuous (resp. uniformly continuous).

**Remark 2.1.** — If the topology $\mathcal{O}$ is metrizable (i.e. can be generated by a distance on the space $X$), then the topology on $X$ induced by the distance $d$ is equivalent to $\mathcal{O}$ if and only if for every sequence with values in $X$, convergence for $d$ is equivalent to convergence for $\mathcal{O}$ (see [23, Theorem 4.1.2]). Moreover, when the topology is metrizable, then topological notions and their sequential counterparts coincides (e.g. compact and sequentially compact sets, closed and sequentially closed sets, see [23, Proposition 4.1.1 and Theorem 4.1.17]).

**Remark 2.2.** — For a function, continuity always implies sequential continuity; and the converse is also true when the topology is metrizable.

A map $\varphi : \Omega_1 \to \Omega_2$ between two probability spaces $(\Omega_i, \mathcal{A}_i, \pi_i)$, $i = 1, 2$, is measure-preserving if it is measurable and if for every $A \in \mathcal{A}_2$, $\pi_2(A) = \pi_1(\varphi^{-1}(A))$. In this case, for every measurable non-negative function $f : \Omega_2 \to \mathbb{R}$, we have:

$$ (2.1) \qquad \int_{\Omega_1} f(\varphi(x)) \pi_1(dx) = \int_{\Omega_2} f(x) \pi_2(dx). $$

We denote by $S_{[0,1]}$ the set of bijective measure-preserving maps from $[0, 1]$ with the Lebesgue measure to itself, and by $\bar{S}_{[0,1]}$ the set of measure-preserving maps from $[0, 1]$ with the Lebesgue measure to itself.
Let $(\mathbf{Z}, \mathcal{O}_{\mathbf{Z}})$ be some (non-empty) Polish space, and let $\mathcal{B}(\mathbf{Z})$ be the Borel $\sigma$-field on $\mathbf{Z}$ generated by the topology $\mathcal{O}_{\mathbf{Z}}$. We denote by $C_b(\mathbf{Z})$ the space of real-valued continuous bounded functions on $(\mathbf{Z}, \mathcal{O}_{\mathbf{Z}})$. We denote by $M_{\pm}(\mathbf{Z})$ the space of finite signed measures on $(\mathbf{Z}, \mathcal{B}(\mathbf{Z}))$; $M_{+}(\mathbf{Z})$ the subspace of measures; $M_{\le 1}(\mathbf{Z})$ the subspace of measures with total mass at most 1; and $M_1(\mathbf{Z})$ the subspace of probability measures. We have:

$$M_1(\mathbf{Z}) \subset M_{\le 1}(\mathbf{Z}) \subset M_+(\mathbf{Z}) \subset M_{\pm}(\mathbf{Z}).$$

For a signed measure $\mu \in M_{\pm}(\mathbf{Z})$, we recall the definition of the Hahn–Jordan decomposition $\mu = \mu^{+} - \mu^{-}$ where $\mu^{+}, \mu^{-} \in M_{+}(\mathbf{Z})$ are mutually singular measures (that is $\mu^{+}(A) = 0$ and $\mu^{-}(A^{c}) = 0$ for some measurable set $A$), as well as the total variation measure of $\mu$ which is defined as $|\mu| = \mu^{+} + \mu^{-} \in M_{+}(\mathbf{Z})$. Note that for a measure $\mu \in M_{+}(\mathbf{Z})$, we simply have $|\mu| = \mu$. For a signed-measure $\mu \in M_{\pm}(\mathbf{Z})$ and a real-valued measurable function $f$ defined on $\mathbf{Z}$, we write $\mu(f) = \langle \mu, f \rangle = \int f \, d\mu = \int_{\mathbf{Z}} f(x) \, \mu(dx)$ the integral of $f$ w.r.t. $\mu$ whenever it is well defined. For a signed measure $\mu \in M_{\pm}(\mathbf{Z})$, we denote by $\|\mu\|_{\infty} = \mu^{+}(\mathbf{Z}) + \mu^{-}(\mathbf{Z})$ its total mass, which is also equal to the supremum of $\mu(f)$ over all measurable functions $f$ with values in $[-1, 1]$.

We endow $M_{\pm}(\mathbf{Z})$ with the topology of weak convergence, that is the smallest topology for which the maps $\mu \mapsto \mu(f)$ are continuous for all $f \in C_b(\mathbf{Z})$. In particular, a sequence of signed measures $(\mu_n)_{n \in \mathbb{N}}$ weakly converges to some $\mu \in M_{\pm}(\mathbf{Z})$ if and only if, for every function $f \in C_b(\mathbf{Z})$, we have $\lim_{n \to +\infty} \mu_n(f) = \mu(f)$. Let us recall that $M_{+}(\mathbf{Z})$ and $M_1(\mathbf{Z})$ endowed with the topology of weak convergence are Polish spaces.

**Remark 2.3 (The weak topology on $M_{\pm}(\mathbf{Z})$).** — The topology of weak convergence on the set of signed measures $M_{\pm}(\mathbf{Z})$ is equivalent to the weak-\* topology on $M_{\pm}(\mathbf{Z})$ seen as a subspace of the topological dual of $C_b(\mathbf{Z})$ (see the paragraph after Definition 3.1.1 in [14]). As usual in probability theory, this topology will be simply called the weak topology (this is also consistent with [14]).

We recall that a sequence of $[0, 1]$-valued functions $\mathcal{F} = (f_k)_{k \in \mathbb{N}}$ in $C_b(\mathbf{Z})$, with $f_0 = 1$ the constant function equal to one, is:

(i) *Separating* if for every measures $\mu, \nu$ from $M_{\pm}(\mathbf{Z})$ (or equivalently just from $M_{+}(\mathbf{Z})$) such that for every $k \in \mathbb{N}$, $\mu(f_k) = \nu(f_k)$, then $\mu = \nu$.

(ii) *Convergence determining* if for every $(\mu_n)_{n \in \mathbb{N}}$ and $\mu$ measures from $M_{+}(\mathbf{Z})$ such that we have $\lim_{n \to +\infty} \mu_n(f_k) = \mu(f_k)$ for all $k \in \mathbb{N}$, then $(\mu_n)_{n \in \mathbb{N}}$ weakly converges to $\mu$.
Notice that a convergence determining sequence is also separating. A sequence of functions is separating if and only if it separates the points of $Z$ (see [24, Theorem 3.4.5]). There always exists a convergence determining sequence on Polish spaces, see [14, Corollary 2.2.6] or the proof of Proposition 3.4.4 in [24] (which are stated for probability measures but can be extended to finite positive measures as we required that $1$ belongs to $\mathcal{F}$). Note that there does not exist a convergence determining sequence for $M_{\pm}(Z)$ as the weak topology is not metrizable on $M_{\pm}(Z)$ (see Remark 2.6 below).

**Remark 2.4** (The Borel $\sigma$-field on $M_{\pm}(Z)$). — By [14, Corollary 5.1.9], the Borel $\sigma$-field on $M_{\pm}(Z)$, associated with the weak topology, is countably generated and can be generated by either:

* the family of maps $\mu \mapsto \mu(f_n)$ where the sequence $(f_n)_{n \in \mathbb{N}}$ of functions from $C_b(Z)$ is separating;

* the family of maps $\mu \mapsto \mu(B)$ where $B \in \mathcal{A}$ and the subset $\mathcal{A} \subset \mathcal{B}(Z)$ is countable and generates the whole $\sigma$-field $\mathcal{B}(Z)$ (such subset $\mathcal{A}$ always exists, see [13, Corollary 6.7.5]).

Note that the Borel $\sigma$-field of a Polish space is generated by any family of Borel functions that separates points (see [13, Theorem 6.8.9]).

Furthermore, the maps $\mu \mapsto \mu^+$ and $\mu \mapsto \mu^-$ (and thus also $\mu \mapsto |\mu|$) are measurable (see [22, Theorem 2.8] and Remark 2.4). As a consequence, the map $\mu \mapsto \|\mu\|_{\infty}$ is also measurable (in fact it is even lower semicontinuous by [14, Theorem 2.7.4]). Note that $M_1(Z)$ and $M_+(Z)$ are closed, and thus measurable, subsets of $M_{\pm}(Z)$.

We define the following two important properties for subsets of signed measures, which are related to relative compactness (see Lemma 2.8 below).

**Definition 2.5.** — Let $\mathcal{M} \subset M_{\pm}(Z)$ be a subset of signed measures.

(i) The set $\mathcal{M}$ is bounded (in total variation) if:

$$ \sup_{\mu \in \mathcal{M}} \|\mu\|_{\infty} < +\infty. $$

(ii) The set $\mathcal{M}$ is tight if for all $\varepsilon > 0$, there exists a compact set $K \subset Z$ such that:

$$ \sup_{\mu \in \mathcal{M}} |\mu|(K^c) \le \varepsilon. $$

**Remark 2.6** (On the compact sets and metrizability of the weak topology). — Recall that $Z$ is a Polish space. We stress that the weak topology on signed measures is not metrizable unless it coincides with the
strong topology (see [52, Theorem 4.1]), which happens only when the initial space $\mathbf{Z}$ is finite (see [14, Proposition 3.1.8]).

Moreover, the closed norm ball $\{\mu \in \mathcal{M}_{\pm}(\mathbf{Z}) : \|\mu\|_{\infty} \le 1\}$ of $\mathcal{M}_{\pm}(\mathbf{Z})$ is metrizable if and only if $\mathbf{Z}$ is compact (see [14, Proposition 3.1.8 and Theorem 3.1.9]).

Let $\mathcal{M} \subset \mathcal{M}_{\pm}(\mathbf{Z})$. The following properties are equivalent (see [14, Theorems 2.3.4 and 3.1.9]):

(i) $\mathcal{M}$ is weakly compact (i.e. $\mathcal{M}$ is compact for the weak topology);

(ii) $\mathcal{M}$ is sequentially weakly compact (that is every sequence $(\mu_n)_{n \in \mathbb{N}}$ in $\mathcal{M}$ has a subsequence that converges to some limit $\mu \in \mathcal{M}$);

(iii) $\mathcal{M}$ is compact for the sequential weak topology (for which sets are closed if and only if they are closed under weak convergence).

Moreover, when any of those is true, $\mathcal{M}$ is tight, bounded, and metrizable in the weak topology. Furthermore, the Kantorovitch–Rubinshtein and Fortet-Mouriet norms $\| \cdot \|_{\text{KR}}$ and $\| \cdot \|_{\text{FM}}$ (defined in Section 3.8.2) can be used to generate the weak topology on a weakly compact set (see [14, Remark 3.2.5]).

Nevertheless, the weak topology on the unit sphere $\{\mu \in \mathcal{M}_{\pm}(\mathbf{Z}) : \|\mu\|_{\infty} = 1\}$ of $\mathcal{M}_{\pm}(\mathbf{Z})$ is always metrizable with a complete metric, making the unit sphere a Polish space, however, the Kantorovitch–Rubinshtein and Fortet-Mouriet norms $\| \cdot \|_{\text{KR}}$ and $\| \cdot \|_{\text{FM}}$ do not provide a complete metrization in this case (see [14, Theorem 3.2.8]).

**Remark 2.7 (On the compactness of $M_1(\mathbf{Z})$).** — Let $\mathcal{M}$ be either $M_1(\mathbf{Z})$, $M_{\le 1}(\mathbf{Z})$ or the closed norm ball $\{\mu \in \mathcal{M}_{\pm}(\mathbf{Z}) : \|\mu\|_{\infty} \le 1\}$ of $\mathcal{M}_{\pm}(\mathbf{Z})$. Then, $\mathcal{M}$ is weakly compact if and only if $\mathbf{Z}$ is compact.

We give a short proof of this statement. As $M_1(\mathbf{Z})$ is closed in $\mathcal{M}_{\pm}(\mathbf{Z})$ for the weak topology, if $\mathcal{M}$ is weakly compact, then $M_1(\mathbf{Z})$ is also weakly compact, and thus $\mathbf{Z}$ is compact by [52, Theorem 3.4]. Conversely, if $\mathbf{Z}$ is compact, then by [14, Theorem 1.3.3], we know that $\mathcal{M}_{\pm}(\mathbf{Z})$ (endowed with the weak topology) is the topological dual space of $C_b(\mathbf{Z})$ (endowed with the uniform convergence topology), thus using Banach–Alaoglu theorem (see [14, Theorem 1.3.6]), we get that the closed unit norm-ball of $\mathcal{M}_{\pm}(\mathbf{Z})$, and thus $\mathcal{M}$, are compact for the weak topology.

We recall the following result, which is an equivalent of Prokhorov's theorem for signed measures.

**LEMMA 2.8 (Prokhorov's theorem for signed measures, [14, Theorems 2.3.4 and 3.1.9]).** — Let $\mathbf{Z}$ be a Polish space, and let $\mathcal{M} \subset \mathcal{M}_{\pm}(\mathbf{Z})$ be a
subset of signed measures on $Z$. Then the following conditions are equivalent:

(i) $\mathcal{M}$ is relatively sequentially compact, that is every sequence $(\mu_n)_{n \in \mathbb{N}}$ in $\mathcal{M}$ contains a subsequence which weakly converges in $\mathcal{M}_{\pm}(Z)$.

(ii) $\mathcal{M}$ is relatively compact for the weak topology, that is the closure of $\mathcal{M}$ is compact for the weak topology.

(iii) The family $\mathcal{M}$ is tight and bounded.

**Remark 2.9 (On the weak sequential topology).** — When the space $Z$ is infinite, the weak topology does not coincide with the weak sequential topology on $\mathcal{M}_{\pm}(Z)$ (but recall from Remark 2.6 that their compact sets are the same). Recall that if the space $Z$ is compact, then the unit norm ball of $\mathcal{M}_{\pm}(Z)$ is metrizable, and thus the weak topology and the weak sequential topology coincide on it. However, if the space $Z$ is non-compact, then the weak topology and the weak sequential topology do not coincide on the unit norm ball of $\mathcal{M}_{\pm}(Z)$.

We give a short proof of those statements according to $Z$ being compact or not.

(i) Recall that when $Z$ is an infinite compact space (for instance $Z = [0,1]$), the Banach space $C_b(Z)$ is infinite-dimensional and separable (using Stone-Weierstrass theorem), and its topological dual is $(C_b(Z))^* = \mathcal{M}_{\pm}(Z)$ (see [14, Theorem 1.3.3]). Thus, using [33, Theorem 2.5], we get the existence of a countable subset which is weak sequentially closed yet weak dense in $\mathcal{M}_{\pm}(Z)$. In particular, the weak sequential topology and the weak topology do not coincide on $\mathcal{M}_{\pm}(Z)$.

(ii) Assume that the space $Z$ is non-compact. Thus, $Z$ contains a countable closed subset $F$ whose points are at mutual distances uniformly bounded away from zero. By [14, Remark 3.1.7], the weak topology on $\mathcal{M}_{\pm}(F)$ for a closed subset $F$ coincides with the trace of the weak topology on the whole space. By [14, Section 3.1, p. 102], $\mathcal{M}_{\pm}(F)$ is homeomorphic to $\ell^1$ both endowed with their weak topology, weak convergence on $\ell^1$ is equivalent to norm convergence, and the weak topology on $\ell^1$ is not sequential, even on the unit norm ball. Hence, the weak topology on $\mathcal{M}_{\pm}(Z)$ is not sequential, even on the unit norm ball.

We define the notion of a quasi-convex distance, which generalizes the convexity of a norm.
**DEFINITION 2.10 (Quasi-convex distance).** — Let $(X, d)$ be a metric space which is a convex subset of a vector space. The distance $d$ is quasi-convex if for all $x_1, x_2, y_1, y_2 \in X$ and all $\alpha \in [0, 1]$, we have:

$$d(\alpha x_1 + (1-\alpha)x_2, \alpha y_1 + (1-\alpha)y_2) \le \max(d(x_1, y_1), d(x_2, y_2)).$$

In particular, any distance (on a convex subset of a vector space) which derives from a norm is quasi-convex.

**LEMMA 2.11.** — Let $d_m$ be distance on $M_\epsilon(\mathbf{Z})$ with $\epsilon \in \{+, \pm\}$ which is quasi-convex and sequentially continuous with respect to the weak topology. Then, $d_m$ is uniformly continuous with respect to $\|\cdot\|_\infty$ on $M_\epsilon(\mathbf{Z})$.

*Proof.* — We shall simply consider the case $M = M_+(\mathbf{Z})$, the other case being simpler. We first check that for all $\mu \in M$ and $\epsilon > 0$, there exists $\eta > 0$ such that for all $\nu \in M$, we have that $\|\mu - \nu\|_\infty < \eta$ implies $d_m(\mu, \nu) < \epsilon$. As $d_m$ is sequentially continuous w.r.t. the weak topology, it is also (sequentially) continuous w.r.t. the strong topology. Let $\mu \in M$ and $\epsilon > 0$. Then, the set $\{\nu \in M : d_m(\mu, \nu) < \epsilon\}$ is an open set of $M$ containing $\mu$ both for $d_m$ and for the strong topology. Thus, it contains a neighborhood of $\mu$ for the strong topology $\{\nu \in M : \|\mu - \nu\|_\infty < \eta\}$ for $\eta > 0$ small enough. This proves the claim.

As $d_m$ is quasi-convex and $M$ is a cone, for $\mu, \nu \in M$ we have:

$$ \begin{aligned} d_m(\mu, \mu + \nu) &= d_m\left(\frac{1}{2} \cdot (2\mu + 0), \frac{1}{2} \cdot (2\mu + 2\nu)\right) \\ &\le \max(d_m(2\mu, 2\mu), d_m(0, 2\nu)) \\ &= d_m(0, 2\nu). \end{aligned} $$

Let $\epsilon > 0$ be fixed. We choose $\eta \in (0, 1)$ such that $\|\nu\|_\infty < \eta$, with $\nu \in M$, implies $d_m(0, \nu) < \epsilon$. Let $\mu, \nu \in M$ be such that $\|\mu - \nu\|_\infty < \eta/2$. Let $\lambda' = \mu + \nu$ and $f$ (resp. $g$) the density of $\mu$ (resp. $\nu$) with respect to $\lambda'$. We set $\pi = \min(f, g) \lambda'$, $\mu' = (f - g)_+ \lambda'$ and $\nu' = (f - g)_- \lambda'$ so that $\pi, \mu', \nu' \in M$, $\mu = \pi + \mu'$ and $\nu = \pi + \nu'$. Since $\mu' - \nu' = \mu - \nu$ and $\mu'$ and $\nu'$ are mutually singular, we deduce that $\|\mu'\|_\infty + \|\nu'\|_\infty < \eta/2$. We get:

$$ \begin{aligned} d_m(\mu, \nu) &= d_m(\pi + \mu', \pi + \nu') \\ &\le d_m(\pi, \pi + \mu') + d_m(\pi, \pi + \nu') \\ &\le d_m(0, 2\mu') + d_m(0, 2\nu') \\ &\le 2\epsilon. \end{aligned} $$

Hence, the distance $d_m$ is uniformly continuous with respect to $\|\cdot\|_\infty$ on $M$. $\square$
### 3. Measure-valued graphons and the cut distance

In Section 3.1, we introduce the measure-valued graphons, which are a generalization of real-valued graphons (i.e. $[0, 1]$-valued measurable functions defined on $[0, 1]^2$). We refer to the monography [46] on real-valued graphons for more details. Contrary to the case of $[0, 1]$ with its usual topology, there is no canonical distance inducing the weak topology on $M_1(\mathbb{Z})$. In Sections 3.2, 3.3 and 3.4, starting from a distance $d_m$ inducing the weak topology on measures, we introduce the cut distance, and its unla-beled variant, on the space of measure-valued graphons which are analogous to the ones for real-valued graphons (see [46, Chapter 8]). In Section 3.5, we define a weak isomorphism relation for measure-valued graphons based on this distance, which is analogous to the weak isomorphism relation for real-valued graphons (see [46, Sections 7.3 and 10.7]). Then, in Section 3.6, we give an alternative combinatorial formulation of the cut distance for stepfunctions.

#### 3.1. Definition of measure-valued graphons

We start by defining measure-valued kernels and graphons which are a generalization of real-valued kernels and graphons. Recall that $\mathbb{Z}$ is a Polish space and $M_{\pm}(\mathbb{Z})$ is the space of finite signed measures.

**DEFINITION 3.1** (Signed measure-valued kernels). — A signed measure-valued kernel or $M_{\pm}(\mathbb{Z})$-valued kernel is a map $W$ from $[0, 1]^2$ to $M_{\pm}(\mathbb{Z})$, such that:

(i) $W$ is measurable in $(x, y)$: for every measurable set $A \subset \mathbb{Z}$, the function $(x, y) \mapsto W(x, y; A)$ defined on $[0, 1]^2$ is measurable.

(ii) $W$ is bounded:

$$ (3.1) \qquad \|W\|_{\infty} := \sup_{x,y \in [0,1]} \|W(x,y; \cdot)\|_{\infty} < +\infty. $$

We denote by $W_1$ (resp. $W_{\le 1}$, resp. $W_+$, resp. $W_{\pm}$) the space of probability measure-valued kernels or simply probability-graphons (resp. sub-probability measure-valued kernels, resp. measure-valued kernels, resp. signed measure-valued kernels), where we identify kernels that are equal a.e. on $[0, 1]^2$, with respect to the Lebesgue measure. Then, (3.1) should be read with an essential supremum instead of a supremum. In what follows, we always assume for simplicity that we choose representatives of
measure-valued kernels such that $||W||_\infty$ is also the essential supremum of $(x, y) \mapsto ||W(x, y; \cdot)||_\infty$.

For $\mathcal{M} \subset \mathcal{M}_\pm(\mathbf{Z})$, we denote by $W_{\mathcal{M}}$ the subset of signed measure-valued kernels $W \in W_\pm$ which are $\mathcal{M}$-valued: $W(x, y; \cdot) \in \mathcal{M}$ for every $(x, y) \in [0, 1]^2$.

**Remark 3.2 (On real-valued kernels).** — Let $\mathbf{Z} = \{0, 1\}$ be equipped with the discrete topology. Every real-valued graphon $w$ can be represented using a probability-graphon $W$ defined for every $x, y \in [0, 1]$ by $W(x, y; dz) = w(x, y)\delta_1(dz) + (1 - w(x, y))\delta_0(dz)$, where $\delta_z$ is the Dirac mass located at $z$. In particular we have that $w(x, y) = W(x, y; \{1\})$ for $x, y \in [0, 1]$.

Let $W \in W_\pm$ be a signed measure-valued kernel. Define the map $W^+ : [0, 1]^2 \to M_+(\mathbf{Z})$ to be the positive part of $W$, i.e. for every $(x, y) \in [0, 1]^2$, $W^+(x, y; \cdot)$ is the positive part of the measure $W(x, y; \cdot)$. Similarly define $W^- : [0, 1]^2 \to M_+(\mathbf{Z})$ the negative part of $W$; and then define $|W| = W^+ + W^-$ the total variation of $W$ and $||W|| = |W|(\mathbf{Z})$ the total mass of $W$.

**LEMMA 3.3 (The positive part $W^+$ of a kernel).** — The maps $W^+$, $W^-$ and $|W|$ are all measure-valued kernels, and the map $||W|| : (x, y) \mapsto ||W(x, y; \cdot)||_\infty$ is measurable.

*Proof.* — The statements for $|W|$ and $||W||$ are immediate consequences of the statements for $W^+$ and $W^-$; and as the proof for $W^+$ and $W^-$ are similar, we only need to prove that $W^+$ is a measure-valued kernel. It is immediate that $W^+$ is bounded and that for every $(x, y) \in [0, 1]^2$, $W^+(x, y; \cdot)$ is a measure in $M_+(\mathbf{Z})$. Thus, we are left to prove the measurability of $W^+$ in $(x, y)$. By [22, Proposition 2.1] and Remark 2.4, a signed measure-valued kernel $U$ is measurable in $(x, y)$ (i.e. for every $A \in \mathcal{B}(\mathbf{Z})$, the map $(x, y) \mapsto U(x, y; A)$ is measurable) if and only if the map $(x, y) \mapsto U(x, y; \cdot)$ is measurable from $[0, 1]^2$ (with its Borel $\sigma$-field) to $M_+(\mathbf{Z})$ equipped with the Borel $\sigma$-field generated by the weak topology. By [22, Theorem 2.8], the map $\mu \mapsto \mu^+$, that associates to a signed measure the positive part of its Hahn–Jordan decomposition, is measurable from $M_+(\mathbf{Z})$ to $M_+(\mathbf{Z})$ both endowed with the Borel $\sigma$-field generated by the weak topology. Considering the composition of $W$ and $\mu \mapsto \mu^+$, we get that $W^+$ is measurable in $(x, y)$ and is thus a measure-valued kernel. $\square$

**Remark 3.4 (Probability-graphons $W : \Omega \times \Omega \to M_1(\mathbf{Z}))$.** — Similarly to the case of real-valued graphons, it is possible to replace the vertex-type space $[0, 1]$ by any standard probability space $(\Omega, \mathcal{A}, \pi)$ that might
be more appropriate to represent vertex-types for some applications, and to consider probability-graphons of the form $W : \Omega \times \Omega \rightarrow \mathcal{M}_1(\mathbb{Z})$. We recall that a standard probability space $(\Omega, \mathcal{A}, \pi)$ is a probability space such that there exists a measure-preserving map $\varphi : [0, 1] \rightarrow \Omega$, where $[0, 1]$ is endowed with the Borel $\sigma$-field and the Lebesgue measure. In particular, every Polish space endowed with its Borel $\sigma$-field is a standard probability space. As an example, the space $[0, 1]^2$ equipped with the Borel $\sigma$-field and the Lebesgue measure $\lambda_2$ is a standard probability space; we will reuse this fact later.

Using the measure preserving map $\varphi$, it is then possible to consider an unlabeled version $W^{\varphi}$ of $W$ constructed on $\Omega' = [0, 1]$, and to modify the definition of the cut distance $\delta_{\square,m}$ similarly as in [35, Theorem 6.9] to allow each probability-graphon to be constructed on different standard probability spaces. For simplicity, in this article we only consider the equivalent case where all probability-graphons are constructed on $\Omega = [0, 1]$.

**Remark 3.5 (Symmetric kernels).** — We shall consider non-symmetric measure-valued kernels and probability-graphons in order to handle directed graphs whose adjacency matrices are thus a priori non-symmetric. We say that a measure-valued kernel or graphon $W$ is symmetric if for a.e. $x, y \in [0, 1]$, $W(x, y; \cdot) = W(y, x; \cdot)$.

We define stepfunction measure-valued kernels which are often used for approximation.

**DEFINITION 3.6 (Signed measure-valued stepfunctions).** — A signed measure-valued kernel $W \in \mathcal{W}_{\pm}$ is a stepfunction if there exists a finite partition of $[0, 1]$ into measurable (possibly empty) sets, say $\mathcal{P} = \{S_1, \cdots, S_k\}$, such that $W$ is constant on the sets $S_i \times S_j$, for $1 \le i, j \le k$. We say that $W$ and the partition $\mathcal{P}$ are adapted to each other. We write $|\mathcal{P}| = k$ the number of elements of the partition $\mathcal{P}$.

Throughout the article, we shall only consider partitions composed of measurable subsets.

## 3.2. The cut distance

We define a distance and a norm on signed measure-valued graphons and kernels, called the *cut distance* and the *cut norm* respectively which are analogous to the cut norm for real-valued graphons and kernels, see [46, Chapter 8]. For a signed measure-valued kernel $W \in \mathcal{W}_{\pm}$ and a measurable
subsets $A \subset [0, 1]^2$, we denote by $W(A; \cdot)$ the signed measure on $\mathbb{Z}$ defined by:

$$W(A; \cdot) = \int_A W(x, y; \cdot) \, dxdy.$$

**DEFINITION 3.7** (The cut distance $d_{\square,m}$). — Let $d_m$ be a quasi-convex distance on $\mathcal{M}$ a convex subset of $\mathcal{M}_{\pm}(\mathbb{Z})$ containing the zero measure. The associated cut distance $d_{\square,m}$ is the function defined on $W_{\mathcal{M}}^2$ by:

$$(3.2) \quad d_{\square,m}(U, W) = \sup_{S,T \subset [0,1]} d_m(U(S \times T; \cdot), W(S \times T; \cdot)),$$

where the supremum is taken over all measurable subsets $S$ and $T$ of $[0, 1]$.

Notice that the right-hand side of (3.2) is well defined as $\mathcal{M}$ contains the zero measure (and thus if $U$ belongs to $W_{\mathcal{M}}$ then $U(A; \cdot)$ belongs to $\mathcal{M}$).

**DEFINITION 3.8** (The cut norm $N_{\square,m}$). — The cut norm $N_{\square,m}$ associated with a norm $N_m$ on $\mathcal{M}_{\pm}(\mathbb{Z})$ is the function defined on $W_{\square,m}$ by:

$$N_{\square,m}(W) = \sup_{S,T \subset [0,1]} N_m(W(S \times T; \cdot)),$$

where the supremum is taken over all measurable subsets $S$ and $T$ of $[0, 1]$.

The next proposition states that the cut distance (resp. norm) is indeed a distance (resp. norm); its extension to distances on $\mathcal{M}_+(\mathbb{Z})$ and $\mathcal{M}_-(\mathbb{Z})$ is immediate.

**PROPOSITION 3.9** ($d_{\square,m}$ is a distance, $N_{\square,m}$ is a norm). — The cut distance $d_{\square,m}$ associated with a distance $d_m$ on $\mathcal{M}_{\le 1}(\mathbb{Z})$ (resp. $\mathcal{M}_+(\mathbb{Z})$) is a distance on $W_1$ (resp. $W_+$). The cut norm $N_{\square,m}$ associated with a norm $N_m$ on $\mathcal{M}_{\pm}(\mathbb{Z})$ is a norm on $W_{\pm}$.

Moreover, when the distance $d_m$ on $\mathcal{M}_{\le 1}(\mathbb{Z})$ (resp. $\mathcal{M}_+(\mathbb{Z})$) derives from a norm $N_m$ on $\mathcal{M}_{\pm}(\mathbb{Z})$, then the distance $d_{\square,m}$ derives also from the norm $N_{\square,m}$.

*Proof.* — Let $d_m$ be a distance on $\mathcal{M}_{\le 1}(\mathbb{Z})$ (the proof for the case $\mathcal{M}_+(\mathbb{Z})$ is similar). It is clear that $d_{\square,m}$ is symmetric and satisfies the triangular inequality. Thus, we only need to prove that $d_{\square,m}$ is separating. Let $U$ and $W$ be two probability-graphons such that $d_{\square,m}(U, W) = 0$. Then, for every measurable subsets $S, T \subset [0, 1]$, we have $U(S \times T; \cdot) = W(S \times T; \cdot)$. Let $\mathcal{F} = (f_k)_{k \in \mathbb{N}}$ be a separating sequence. For every $k \in \mathbb{N}$, and for every measurable subsets $S, T \subset [0, 1]$, we have that $U(S \times T; f_k) = W(S \times T; f_k)$. This implies that $U(x, y; f_k) \, dxdy = W(x, y; f_k) \, dxdy$ for all $k \in \mathbb{N}$. Hence, we deduce that for all $k \in \mathbb{N}$, $U(x, y; f_k) = W(x, y; f_k)$ for almost every
$(x, y) \in [0, 1]^2$. Thus, $U(x, y; \cdot) = W(x, y; \cdot)$ for almost every $(x, y) \in [0, 1]^2$. This implies that $d_{\square,m}$ is separating on $W_1$, and thus a distance on $W_1$.

The proof for the cut norm is similar. The proof of the last part of the proposition is clear. □

### 3.3. Graphon relabeling, invariance and smoothness properties

The analogue of graph relabelings for graphons are measure-preserving maps. Recall the definition of a measure-preserving map from Section 2, and in particular (2.1). Recall $\tilde{S}_{[0,1]}$ denotes the set of measure-preserving (measurable) maps from $[0, 1]$ to $[0, 1]$ endowed with the Lebesgue measure, and $S_{[0,1]}$ denotes its subset of bijective maps.

The relabeling of a signed measure-valued kernel $W$ by a measure-preserving map $\varphi$, is the signed measure-valued kernel $W^\varphi$ defined for every $x, y \in [0, 1]$ and every measurable set $A \subset \mathbb{Z}$ by:

$W^\varphi(x, y; A) = W(\varphi(x), \varphi(y); A)$ for $x, y \in [0, 1]$ and $A \subset \mathbb{Z}$ measurable.

We say that a subset $K \subset W_\pm$ is uniformly bounded if:

$$ (3.3) \qquad \sup_{W \in K} \|W\|_{\infty} < +\infty. $$

**DEFINITION 3.10** (Invariance and smoothness of a distance on kernels). Let $d$ be a distance on $W_1$ (resp. $W_+$ or $W_\pm$). We say that the distance $d$ is:

(i) **Invariant**: if $d(U, W) = d(U^\varphi, W^\varphi)$ for every bijective measure-preserving map $\varphi \in S_{[0,1]}$ and $U, V \in W_1$ (resp. $U, V$ belongs to $W_+$ or $W_\pm$).

(ii) **Smooth**: if a.e. weak convergence implies convergence for $d$, that is, if $(W_n)_{n \in \mathbb{N}}$ and $W$ are kernels from $W_1$ (resp. kernels from $W_+$ or $W_\pm$ that are uniformly bounded and) such that for a.e. $(x, y) \in [0, 1]^2$, $W_n(x, y; \cdot)$ weakly converges to $W(x, y; \cdot)$ as $n \to \infty$, then $\lim_{n \to \infty} d(W_n, W) = 0$.

We say that a norm $N$ on $W_\pm$ is invariant (resp. smooth) if its associated distance $d$ on $W_\pm$ is invariant (resp. smooth).

We shall see in Section 3.8 some examples of distances $d_m$ for which the associated cut distance $d_{\square,m}$ is invariant and smooth. The invariance property from Definition 3.10 is always satisfied by the cut distance, and thus also by the cut norm.
LEMMA 3.11 ($d_{\square,m}$ is invariant). — Let $d_m$ be a distance on $M_{\le 1}(\mathbf{Z})$ (resp. $M_+(\mathbf{Z})$, resp. $M_\pm(\mathbf{Z})$). Then the cut distance $d_{\square,m}$ on $W_1$ (resp. $W_+$, resp. $W_\pm$) is invariant.

*Proof.* — For a signed measure-valued kernel $W$, a bijective measure-preserving map $\varphi \in S_{[0,1]}$, and measurable sets $S, T \subset [0,1]$, we have thanks to (2.1):

$$ 
\begin{aligned}
\int_{S \times T} W^{\varphi}(x, y; \cdot) \, dxdy &= \int_{S \times T} W(\varphi(x), \varphi(y); \cdot) \, dxdy \\
&= \int_{\varphi(S) \times \varphi(T)} W(x, y; \cdot) \, dxdy.
\end{aligned}
$$

Hence, taking the supremum over every measurable sets $S, T \subset [0,1]$, we get that the cut distance $d_{\square,m}$ is invariant. $\square$

When a smooth distance on $W_1$ or $W_+$ derives from a distance on $M_1(\mathbf{Z})$ or $M_+(\mathbf{Z})$, we have the following result.

LEMMA 3.12 (Smoothness and the weak topology). — Let $d_m$ be a distance on $M_{\le 1}(\mathbf{Z})$ (resp. $M_+(\mathbf{Z})$ or $M_\pm(\mathbf{Z})$) such that the distance $d_{\square,m}$ on $W_1$ (resp. $W_+$ or $W_\pm$) is smooth. Then, the distance $d_m$ is continuous w.r.t. the weak topology on $M_1(\mathbf{Z})$ (resp. $M_+(\mathbf{Z})$).

*Proof.* — Let $(\mu_n)_{n \in \mathbb{N}}$, and $\mu$ be measures from $M_1(\mathbf{Z})$ (resp. $M_+(\mathbf{Z})$) such that $(\mu_n)_{n \in \mathbb{N}}$ weakly converges to $\mu$. Consider the constant measure-valued graphons (resp. kernels) $W_n \equiv \mu_n$, $n \in \mathbb{N}$, and $W \equiv \mu$. Then, for every $x, y \in [0, 1]$, $W_n(x, y; \cdot)$ weakly converges to $W(x, y; \cdot)$ as $n \to \infty$. As the distance $d_{\square,m}$ is smooth, we get that $\lim_{n \to \infty} d_{\square,m}(W_n, W) = 0$. Considering $S = T = [0, 1]$ in the cut distance, we deduce that $\lim_{n \to \infty} d_m(\mu_n, \mu) = 0$. $\square$

The next lemma is a partial converse of Lemma 3.12, it gives sufficient conditions for $d_{\square,m}$ to be smooth. Recall the definition of a quasi-convex distance in Definition 2.10.

PROPOSITION 3.13 ($d_{\square,m}$ is smooth). — Let $d_m$ be distance on $M_\epsilon(\mathbf{Z})$ with $\epsilon \in \{+, \pm\}$ which is quasi-convex and sequentially continuous w.r.t. the weak topology (on $M_\epsilon(\mathbf{Z})$). Then, the cut distance $d_{\square,m}$ is smooth.

Moreover, for all $U, W \in W_\epsilon$, and for all measurable $A \subset [0, 1]^2$, we have:

$$ (3.4) \qquad d_m(U(A; \cdot), W(A; \cdot)) \le \underset{(x,y) \in A}{\text{essup}} d_m(U(x, y; \cdot), W(x, y; \cdot)). $$

To prove Proposition 3.13, we first need to prove the following lemma for approximation by $M$-valued kernels taking finitely many values.
**LEMMA 3.14.** — Let $W \in W_\pm$ and consider a subset $A \subset [0, 1]^2$. There exists a sequence $(W_n)_{n \in \mathbb{N}}$ in $W_\pm$ such that $(W_n(A; \cdot))_{n \in \mathbb{N}}$ weakly converges to $W(A; \cdot)$ and for all $n \in \mathbb{N}$, $W_n$ is finitely valued and takes its values in $\{W(x, y; \cdot) : (x, y) \in A\}$.

*Proof.* — By scaling, we may assume that $\|W\|_\infty \le 1$. Let $(f_k)_{k \in \mathbb{N}}$ be a convergence determining sequence with $f_0 = 1$ and $f_k$ taking values in $[0, 1]$. Thus, for all $(x, y) \in [0, 1]^2$, $\epsilon \in \{\pm 1\}$ and $k \in \mathbb{N}$, we have $W_\epsilon(x, y; f_k) \in [0, 1]$. For all $n \in \mathbb{N}$, let $(C_{n,j})_{1 \le j \le d_n}$ be a partition of $[0, 1]^{2(n+1)}$ into $d_n = n^{2(n+1)}$ hypercubes of edge-length $r_n = 1/n$. Then, for all $n \in \mathbb{N}$ and $j \in [d_n]$, define $B_{n,j} = A \cap (W_+(\cdot; (f_j)_{0 \le j \le n}), W_-(\cdot; (f_j)_{0 \le j \le n}))^{-1}(C_{n,j})$; thus we get a partition $(B_{n,j})_{1 \le j \le d_n}$ of $A$. If $B_{n,j} \ne \emptyset$, fix some $\mu_{n,j} \in \{W(x, y; \cdot) : (x, y) \in B_{n,j}\}$. If $A \ne [0, 1]^2$, fix some $\mu_\partial \in \{W(x, y; \cdot) : (x, y) \in [0, 1]^2 \setminus A\}$. For $n \in \mathbb{N}$, we define $W_n = 1_{A^c} \mu_\partial + \sum_{j=1}^{d_n} 1_{B_{n,j}} \mu_{n,j}$, which is finitely valued and takes its values in $\{W(x, y; \cdot) : (x, y) \in A\}$.

Let $k \in \mathbb{N}$ and $\epsilon \in \{\pm\}$. For all $n \ge k$, we have:

$$|W_{\epsilon}(A; f_k) - (W_n)_{\epsilon}(A; f_k)| \le \sum_{j=1}^{d_n} \int_{B_{n,j}} |W_{\epsilon}(x, y; f_k) - (\mu_{n,j})_{\epsilon}| \, dxdy \le \frac{1}{n}.$$

As $(f_k)_{k \in \mathbb{N}}$ is convergence determining, this implies that $((W_n)_\epsilon(A; \cdot))_{n \in \mathbb{N}}$ weakly converges to $W_\epsilon(A; \cdot)$ for $\epsilon \in \{\pm\}$. Hence, $(W_n(A; \cdot))_{n \in \mathbb{N}}$ weakly converges to $W(A; \cdot)$. $\square$

*Proof of Proposition 3.13.* — As $d_m$ is quasi-convex, (3.4) is immediate when $U$ and $W$ take only finitely many values. Now, assume that $U$ and $W$ are arbitrary $M_\epsilon(\mathbf{Z})$-valued kernels. Let $\epsilon > 0$. As $d_m$ is sequentially continuous w.r.t. the weak topology, using Lemma 3.14, there exist two $M_\epsilon(\mathbf{Z})$-valued kernels $U'$ and $W'$ such that $d_m(U'(A; \cdot), U(A; \cdot)) < \epsilon$ and $U'$ is finitely valued and takes its values in $\{U(x, y; \cdot) : (x, y) \in A\}$, and similarly for $W'$ and $W$. Thus, we have:

$$d_m(U(A; \cdot), W(A; \cdot)) \le 2\epsilon + \underset{(x,y) \in A}{\operatorname{essup}} d_m(U(x, y; \cdot), W(x, y; \cdot)),$$

and this being true for all $\epsilon > 0$, we get (3.4).

Let $(W_n)_{n \in \mathbb{N}}$ and $W$ be $M_\epsilon(\mathbf{Z})$-valued kernels which are uniformly bounded by some constant $C < \infty$ and such that for a.e. $(x, y) \in [0, 1]^2$, the sequence $((W_n(x, y; \cdot))_{n \in \mathbb{N}}$ converges to $W(x, y; \cdot)$ for the weak topology, and thus also for $d_m$. Let $\epsilon > 0$ and $S, T \subset [0, 1]$. As $d_m$ is quasi-convex and sequentially continuous w.r.t. the weak topology, using Lemma 2.11, there exists $\eta > 0$ such that for all $\mu, \nu \in M_\epsilon(\mathbf{Z})$, we have that $\|\mu - \nu\|_\infty < \eta$
implies $d_m(\mu, \nu) < \varepsilon$. For all $n \in \mathbb{N}$, define the measurable set:

$$A_n = \{(x, y) \in S \times T : d_m(W_n(x, y; \cdot), W(x, y; \cdot)) < \varepsilon\}.$$

By assumption, we have that $\lim_{n \to \infty} \lambda(A_n) = \lambda(S \times T)$. Let $N \in \mathbb{N}$ be such that for $n \ge N$, we have $\lambda((S \times T) \setminus A_n) < \eta/C$. Let $n \ge N$. Remark that $W_n((S \times T) \setminus A_n; \cdot)$ and $W((S \times T) \setminus A_n; \cdot)$ have total mass at most $C\lambda(A_n^c) < \eta$. Thus, we have that $d_m(W_n(A_n; \cdot), W_n(S \times T; \cdot)) < \varepsilon$ and $d_m(W(A_n; \cdot), W(S \times T; \cdot)) < \varepsilon$. Hence, using (3.4) we get that:

$$ \begin{aligned} d_m(W_n(S \times T; \cdot), W(S \times T; \cdot)) &\le 2\varepsilon + d_m(W_n(A_n; \cdot), W(A_n; \cdot)) \\ &\le 2\varepsilon + \underset{(x,y) \in A_n}{\operatorname{essup}} d_m(W_n(x, y; \cdot), W(x, y; \cdot)) \\ &\le 3\varepsilon. \end{aligned} $$

Taking the supremum over $S, T \subset [0, 1]$, we get $d_{\square,m}(W_n, W) \le 3\varepsilon$. This being true for all $\varepsilon > 0$, we conclude that $(W_n)_{n \in \mathbb{N}}$ converges to $W$ for $d_{\square,m}$, and thus $d_{\square,m}$ is smooth. $\square$

### 3.4. The unlabeled cut distance

We can now define the cut distance for unlabeled graphons.

**DEFINITION 3.15** (The unlabeled cut distance $\delta_{\square,m}$). — Set $\mathcal{K} \in \{W_1, W_+, W_\pm\}$. Let $d$ be an invariant distance on the kernel space $\mathcal{K}$. The pseudometric $\delta_{\square}$ on $\mathcal{K}$, also called the cut distance, is defined by:

$$(3.5) \qquad \delta_{\square}(U, W) = \inf_{\varphi \in S_{[0,1]}} d(U, W^{\varphi}) = \inf_{\varphi \in S_{[0,1]}} d(U^{\varphi}, W).$$

Notice that $\delta_{\square}$ satisfies the symmetry property (as $d$ is invariant) and the triangular inequality. Hence, $\delta_{\square}$ induces a distance (that we still denote by $\delta_{\square}$) on the quotient space $\tilde{K}_d = \mathcal{K} / \sim_d$ of kernels in $\mathcal{K}$ associated with the equivalence relation $\sim_d$ defined by $U \sim_d W$ if and only if $\delta_{\square}(U, W) = 0$.

When the metric $d = d_{\square,m}$ on $\mathcal{K} = W_1$ (resp. $W_+$, resp. $W_\pm$) derives from a metric $d_m$ on $\mathcal{M}_{\le 1}(\mathbf{Z})$ (resp. $\mathcal{M}_+(\mathbf{Z})$, resp. $\mathcal{M}_+(\mathbf{Z})$), and is thus invariant thanks to Lemma 3.11, we write $\delta_{\square,m}$ for $\delta_{\square}$ and $\tilde{K}_m$ for $\tilde{K}_{d_{\square,m}}$. We shall see in Theorem 5.5 and Corollary 5.6 that under some conditions, different choices of distance $d_m$, which induces the weak topology on $\mathcal{M}_{\le 1}(\mathbf{Z})$, lead to the same quotient space, then simply denoted by $\tilde{W}_1$, with the same topology.
### 3.5. Weak isomorphism

Similarly to Theorem 8.13 in [46], when the distance $d_m$ is such that $d_{\square,m}$ is invariant and smooth, we can rewrite the cut distance $\delta_{\square,m}$ as a minimum instead of an infimum using measure-preserving maps, see the last equality in (3.6).

We introduce a weak isomorphism relation that allows to “un-label” probability-graphons.

**DEFINITION 3.16 (Weak isomorphism).** — We say that two signed measure-valued kernels $U$ and $W$ are weakly isomorphic (and we note $U \sim W$) if there exists two measure-preserving maps $\varphi, \psi \in \bar{S}_{[0,1]}$ such that $U^\varphi(x, y; \cdot) = W^\psi(x, y; \cdot)$ for a.e. $x, y \in [0, 1]$.

We denote by $\tilde{W}_M = W_M / \sim$ the space of unlabeled $M$-valued kernels i.e. the space of $M$-valued kernels where we identify $M$-valued kernels that are weakly isomorphic. For $M = M_\epsilon(\mathbb{Z})$ with $\epsilon \in \{1, \le 1, +, \pm\}$, we simply write $\tilde{W}_\epsilon = \tilde{W}_M = W_\epsilon / \sim$.

Notice that $U \sim W$ implies that $\|U\|_\infty = \|W\|_\infty$ (we recall that signed measure-valued kernels are only defined for a.e. $x, y \in [0, 1]$ and that $\|W\|_\infty$ in (3.1) is an essup in general). In particular, the notion of uniformly bounded subset defined in (3.3) naturally extends to $\tilde{W}_\pm$. The last part of this section is devoted to the proof of the following key result.

**THEOREM 3.17 (Weak isomorphism and $\delta_\square$).** — Let $d$ be a distance defined on $W_1$ (resp. $W_+$ or $W_\pm$) which is invariant and smooth. Then, two kernels are weakly isomorphic, i.e. $U \sim W$, if and only if $U \sim_d W$, i.e. $\delta_\square(U, W) = 0$.

Furthermore, the map $\delta_\square$ is a distance on $\tilde{W}_1 = \tilde{W}_{1,d}$ (resp. $\tilde{W}_+ = \tilde{W}_{+,d}$ or $\tilde{W}_\pm = \tilde{W}_{\pm,d}$).

As a first step in the proof of Theorem 3.17, following [46], we give a nice description of $\delta_\square$ using couplings. We say that a measure $\mu$ on $[0, 1]^2$ is a coupling measure on $[0, 1]^2$ (between two copies of $[0, 1]$ each equipped with the Lebesgue measure) if the projection maps on each component $\tau, \rho: [0, 1]^2 \to [0, 1]$ (where $[0, 1]^2$ is equipped with the measure $\mu$ and $[0, 1]$ with the Lebesgue measure $\lambda$) are measure-preserving. In particular, for every kernel $W$ on $([0, 1], \mathcal{B}([0, 1]), \lambda)$, the function $W^\tau$ is a kernel on the probability space $([0, 1]^2, \mathcal{B}([0, 1]^2), \mu)$, and similarly for the projection $\rho$.

Let $\varphi$ be a given measure-preserving map from $[0, 1]$ with the Lebesgue measure to $[0, 1]^2$ with a coupling measure $\mu$. For an invariant distance $d$ on
$W_1$ (resp. $W_\pm$), we define a distance, say $d^\mu$, on kernels on $([0, 1]^2, \mathcal{B}([0, 1]^2), \mu)$ by:

$$d^\mu(U', W') = d(U'\varphi, W'\varphi).$$

It is easy to see that, for $U$ and $W$ kernels on $[0, 1]$, we have $d^\mu(U^\tau, W^\tau) = d(U, W)$ as $d$ is invariant and $\tau \circ \varphi$ is a measure-preserving map from $[0, 1]$ to itself; and similarly $d^\mu(U^\rho, W^\rho) = d(U, W)$.

A straightforward adaptation of the proof of [46, Theorem 8.13] gives the next result.

**PROPOSITION 3.18** (Minima in the cut distance $\delta_\square$). — Let $d$ be a distance defined on $W_1$ (resp. $W_+$ or $W_\pm$) which is invariant and smooth. Then, we have the following alternative formulations for the cut distance $\delta_\square$ on $W_1$ (resp. $W_+$ or $W_\pm$):

$$ \begin{align} \delta_\square(U, W) &= \inf_{\varphi \in S_{[0,1]}} d(U, W^\varphi) = \inf_{\psi \in S_{[0,1]}} d(U, W^\psi) \tag{3.6} \\ &= \inf_{\psi \in S_{[0,1]}} d(U^\psi, W) = \inf_{\psi \in S_{[0,1]}} d(U^\psi, W) \nonumber \\ &= \inf_{\varphi, \psi \in S_{[0,1]}} d(U^\psi, W^\varphi) = \min_{\varphi, \psi \in S_{[0,1]}} d(U^\psi, W^\varphi), \nonumber \end{align} $$

and

$$\delta_\square(U, W) = \min_\mu d^\mu(U^\tau, W^\rho)$$

where $\mu$ range over all coupling measures on $[0, 1]^2$.

*Proof of Theorem 3.17.* — We deduce from the last equality in (3.6) that $\delta_\square(U, W) = 0$ if and only if there exist measure-preserving maps $\varphi, \psi \in \bar{S}_{[0,1]}$ such that $U^\psi(x, y; \cdot) = W^\varphi(x, y; \cdot)$ for a.e. $x, y \in [0, 1]$. This gives that the equivalence relations $\sim_d$ and $\sim$ are the same. $\square$

### 3.6. The cut norm for stepfunctions

For a quasi-convex distance $d_m$, the cut distance $d_m$ for stepfunctions can be reformulated using a finite combinatorial optimization. For a collection of subsets $\mathcal{P}$, denote by $\sigma(\mathcal{P})$ the $\sigma$-field generated by $\mathcal{P}$.

**LEMMA 3.19** (Combinatorial optimization of quasi-convex $d_m$ for stepfunctions). — Let $d_m$ be a quasi-convex distance on $\mathcal{M}$ a convex subset of $\mathcal{M}_\pm(\mathbb{Z})$ containing the zero measure. Let $U, W \in \mathcal{W}_M$ be $\mathcal{M}$-valued stepfunctions adapted to the same finite partition $\mathcal{P}$. Then, there exists $S, T \in \sigma(\mathcal{P})$ such that:

$$d_{\square,m}(U, W) = d_m(U(S \times T; \cdot), W(S \times T; \cdot)).$$
Proof. — Let $\mathcal{P} = \{S_1, \dots, S_k\}$ with $k = |\mathcal{P}|$ the size of the partition $\mathcal{P}$. First, remark that the quantity $d_{\square,m}(U, W) = d_m(U(S' \times T'; \cdot), W(S' \times T'; \cdot))$ depends on $S'$ and $T'$ only through the values of $\lambda(S' \cap S_i)$ and $\lambda(T' \cap S_i)$ for $1 \le i \le k$. Thus, the cut distance between $U$ and $W$ can be reformulated as:

$$d_{\square,m}(U, W) = \sup_{\substack{0 \le \alpha_i, \beta_i \le \lambda(S_i) \\ 1 \le i \le k}} d_m \left( \sum_{1 \le i,j \le k} \alpha_i \beta_j \mu_{i,j}(\cdot), \sum_{1 \le i,j \le k} \alpha_i \beta_j \nu_{i,j}(\cdot) \right),$$

where $\mu_{i,j}$ (resp. $\nu_{i,j}$) is the constant value of $U(x, y; \cdot)$ (resp. $W(x, y; \cdot)$) when $x \in S_i$ and $y \in S_j$. Moreover, when we fix the value of $\beta = (\beta_i)_{1 \le i \le k}$, the quantity

$$d_m \left( \sum_{1 \le i,j \le k} \alpha_i \beta_j \mu_{i,j}(\cdot), \sum_{1 \le i,j \le k} \alpha_i \beta_j \nu_{i,j}(\cdot) \right)$$

is a quasi-convex function of $\alpha = (\alpha_i)_{1 \le i \le k}$, and thus realizes its maximum on the extremal points of the hypercube $\prod_{i=1}^k [0, \lambda(S_i)]$, i.e. when $\alpha_i$ equals 0 or $\lambda(S_i)$ for every $1 \le i \le k$. By symmetry, a similar argument holds for $\beta$. The cut distance can thus be reformulated as the combinatorial optimization:

$$d_{\square,m}(U, W) = \max_{I, J \subset [k]} d_m \left( \sum_{i \in I, j \in J} \mu_{i,j}(\cdot), \sum_{i \in I, j \in J} \nu_{i,j}(\cdot) \right).$$

Let $I, J \subset [k]$ be index sets that maximize this combinatorial optimization, and take $S = \cup_{i \in I} S_i$ and $T = \cup_{j \in J} S_j$ to conclude. $\square$

### 3.7. The supremum in $S$ and $T$ in the cut distance $d_{\square,m}$

In this section, we prove that the supremum in the cut distance $d_{\square,m}$ is achieved by some subsets $S, T \subset [0, 1]$.

For $W \in \mathcal{M}_{\pm}(\mathbb{Z})$ and $f, g : [0, 1] \to [0, 1]$ measurable, we define the signed measure:

$$W(f \otimes g; \cdot) = \int_{[0,1]^2} W(x, y; \cdot) f(x) g(y) \, dx dy.$$

Remark that if we have $W \in \mathcal{W}_{\epsilon}$ with $\epsilon \in \{1, \le 1, +, \le \pm\}$, then we have $W(f \otimes g; \cdot) \in \mathcal{M}_{\epsilon}(\mathbb{Z})$.
Note that a similar result was already known for real-valued kernels, see [46, Lemma 8.10].

LEMMA 3.20 (The supremum in the cut distance $d_{\square,m}$ for quasi-convex distance $d_m$). — Let $d_m$ be a quasi-convex distance on $M_\epsilon(\mathbb{Z})$ with $\epsilon \in \{+, \pm\}$ that is sequentially continuous w.r.t. the weak topology. Let $U, W \in W_\epsilon$. Then, there exist measurable subsets $S, T \subset [0, 1]$ such that $f = 1_S$ and $g = 1_T$ achieve the supremum in:

$$ \sup_{f,g} d_m(U(f \otimes g; \cdot), W(f \otimes g; \cdot)) $$

where the supremum is taken over measurable functions $f, g$ from $[0, 1]$ to itself.

In the proof and later on we shall use the following notation. For $W \in W_\pm$ and $f \in C_b(\mathbb{Z})$, we denote by $W[f]$ the real-valued kernel defined by:

$$ (3.7) \qquad W[f](x, y) = W(x, y; f) = \int_{\mathbb{Z}} f(z) W(x, y; dz). $$

Proof. — Define the map $\Psi : (f, g) \mapsto d_m(U(f \otimes g; \cdot), W(f \otimes g; \cdot))$, and denote $C = \sup_{f,g} \Psi(f, g)$, where the supremum is taken over measurable functions $f, g$ from $[0, 1]$ to itself. Let $(f_n)_{n \in \mathbb{N}}$ and $(g_n)_{n \in \mathbb{N}}$ be sequences of measurable functions from $[0, 1]$ to itself such that $\lim_{n \to \infty} \Psi(f_n, g_n) = C$. As the unit ball of $L^\infty([0, 1], \lambda)$ is compact for the weak-* topology (with primal space $L^1([0, 1], \lambda)$), upon taking subsequences, we may assume that $(f_n)_{n \in \mathbb{N}}$ (resp. $(g_n)_{n \in \mathbb{N}}$) weak-* converges to some $f$ (resp. $g$) which take values in $[0, 1]$. Thus, $(f_n \otimes g_n)_{n \in \mathbb{N}}$ weak-* converges to $f \otimes g$ in $L^\infty([0, 1]^2, \lambda_2)$. In particular, for every $h \in C_b(\mathbb{Z})$, as $W[h]$ is a real-valued kernel, this implies that $\lim_{n \to \infty} W(f_n \otimes g_n; h) = W(f \otimes g; h)$. This being true for every $h \in C_b(\mathbb{Z})$, we get that the sequence $(W(f_n \otimes g_n; \cdot))_{n \in \mathbb{N}}$ in $M_\epsilon(\mathbb{Z})$ weakly converges to $W(f \otimes g; \cdot) \in M_\epsilon(\mathbb{Z})$; and similarly for $U$. As $d_m$ is sequentially continuous w.r.t. the weak topology on $M_\epsilon(\mathbb{Z})$, we get that $C = \lim_{n \to \infty} \Psi(f_n, g_n) = \Psi(f, g)$.

Now, we show that we can replace the functions $f$ and $g$ by functions that only take the values 0 and 1 (i.e. indicator functions). We first fix $g$ and do this for $f$. Let $X$ be a random variable uniformly distributed over $[0, 1]$, and consider the random function $1_{X \le f}$. Remark that we have $E[W(1_{X \le f} \otimes g; \cdot)] = W(f \otimes g; \cdot)$, and similarly for $U$. As $d_m$ is quasi-convex
and sequentially continuous w.r.t. the weak topology, we have:

$$
\begin{align*}
C &\ge \sup_{x \in [0,1]} d_m(U(\mathbb{1}_{x \le f} \otimes g; \cdot), W(\mathbb{1}_{x \le f} \otimes g; \cdot)) \\
&\ge d_m(E[U(\mathbb{1}_{X \le f} \otimes g; \cdot)], E[W(\mathbb{1}_{X \le f} \otimes g; \cdot)]) \\
&= d_m(U(f \otimes g; \cdot), W(f \otimes g; \cdot)) \\
&= C,
\end{align*}
$$

where in the second equality we used the quasi-convex supremum inequal-
ity from (3.4) with the $\mathcal{M}_\epsilon(\mathbf{Z})$-valued kernels $U'(x, y; \cdot) = U(\mathbb{1}_{x \le f} \otimes g; \cdot)$
and $W'(x, y; \cdot) = W(\mathbb{1}_{x \le f} \otimes g; \cdot)$, and $A = [0, 1]^2$. All inequalities being
equalities, this imposes:

$$
\begin{align*}
C &= \sup_{x \in [0,1]} d_m (U(\mathbb{1}_{x \le f} \otimes g; \cdot), W(\mathbb{1}_{x \le f} \otimes g; \cdot)) \\
&= \lim_{n \to \infty} d_m (U(\mathbb{1}_{x_n \le f} \otimes g; \cdot), W(\mathbb{1}_{x_n \le f} \otimes g; \cdot)),
\end{align*}
$$

for some sequence $(x_n)_{n \in \mathbb{N}}$ in $[0, 1]$. Upon taking a subsequence, we may assume that the sequence $(x_n)_{n \in \mathbb{N}}$ monotonically converges to some $x \in [0, 1]$. In particular, the sequence of functions $(\mathbb{1}_{x_n \le f})_{n \in \mathbb{N}}$ (monotonically) converges to the function $f' = \mathbb{1}_{x \le f}$ (resp. $f' = \mathbb{1}_{x < f}$) if $(x_n)_{n \in \mathbb{N}}$ is non-decreasing (resp. decreasing), and thus also weak-* converges in $L^\infty([0, 1], \lambda)$. Using, as in the first part of the proof, the sequential continuity of the function $\Psi$ w.r.t. the weak-* topology on $L^\infty([0, 1], \lambda)$, we get that $\Psi(f', g) = d_m(U(f' \otimes g; \cdot), W(f' \otimes g; \cdot)) = C$, that is we can replace $f$ by the indicator function $f'$. The same argument allows to replace $g$ by an indicator function. $\square$

3.8. Examples of distance $d_m$

We consider usual distances and norms on $M_+(\mathbf{Z})$ or $M_\pm(\mathbf{Z})$ that induce
the weak topology on $M_+(\mathbf{Z})$. All the distances we consider are quasi-
convex, and all the norms we consider are sequentially continuous w.r.t. the
weak topology on $M_\pm(\mathbf{Z})$. Thus their associated cut distances are invariant
and smooth by Lemma 3.11 and Proposition 3.13. Properties for the cut
distances associated with those distances and norms are summarized in
Corollaries 4.14 and 5.6.

In this section, we assume that (Z, d₀) is a Polish metric space, and recall
that B(Z) denotes its Borel σ-field.
### 3.8.1. The Lévy–Prokhorov distance $d_{LP}$

The Lévy–Prokhorov distance $d_{LP}$ is a complete distance defined on the set of finite measures $M_+(Z)$ that induces the weak topology (see [11, Theorem 6.8]). It is defined for $\mu, \nu \in M_+(Z)$ as:

$$ (3.8) \quad d_{LP}(\mu, \nu) = \inf\{\varepsilon > 0 : \forall A \in \mathcal{B}(Z), \mu(A) \le \nu(A^\varepsilon) + \varepsilon \text{ and } \nu(A) \le \mu(A^\varepsilon) + \varepsilon\}, $$

where $A^\varepsilon = \{x \in Z : \exists y \in A, d_0(x, y) < \varepsilon\}$. For probability measures, we only need one inequality in (3.8) to define the Lévy–Prokhorov distance; however for positive measures we need both inequalities as two arbitrary positive measures might not have the same total mass. For $d_m = d_{LP}$, we use the subscript m = P. We now prove that the Lévy–Prokhorov distance is quasi-convex.

**LEMMA 3.21.** — The Lévy–Prokhorov distance $d_{LP}$ is quasi-convex on $M_+(Z)$.

*Proof.* — Let $\mu_1, \mu_2, \nu_1, \nu_2 \in M_+(Z)$ and let $\alpha \in [0, 1]$. Let $\varepsilon > \max(d_{LP}(\mu_1, \nu_1), d_{LP}(\mu_2, \nu_2))$, then for all $i \in \{1, 2\}$ and $B \in \mathcal{B}(Z)$, we have that $\mu_i(B) \le \nu_i(B^\varepsilon) + \varepsilon$ and $\nu_i(B) \le \mu_i(B^\varepsilon) + \varepsilon$. Taking a linear combination of those inequalities, we get that for all $B \in \mathcal{B}(Z)$, we have that $\alpha\mu_1(B) + (1-\alpha)\mu_2(B) \le \alpha\nu_1(B^\varepsilon) + (1-\alpha)\nu_2(B^\varepsilon) + \varepsilon$, and similarly when swapping the role $(\mu_1, \mu_2)$ and $(\nu_1, \nu_2)$. Hence, we get that $d_{LP}(\alpha\mu_1 + (1-\alpha)\mu_2, \alpha\nu_1 + (1-\alpha)\nu_2) \le \varepsilon$, and taking the infimum over $\varepsilon$, we get that $d_m(\alpha\mu_1 + (1-\alpha)\mu_2, \alpha\nu_1 + (1-\alpha)\nu_2) \le \max(d_m(\mu_1, \nu_1), d_m(\mu_2, \nu_2))$. $\square$

### 3.8.2. The Kantorovitch–Rubinshtein and Fortet–Mourier norms

The Kantorovitch–Rubinshtein norm $\| \cdot \|_{KR}$ (sometimes also called the bounded Lipschitz distance) and the Fortet–Mourier norm $\| \cdot \|_{FM}$ are two norms defined on $M_\pm(Z)$ that induce the weak topology on $M_+(Z)$ (see Section 3.2 in [14] for definition and properties of those norms). They are defined for $\mu \in M_\pm(Z)$ by:

$$ \|\mu\|_{KR} = \sup \left\{ \int_Z f \, d\mu : f \text{ is 1-Lipschitz and } \|f\|_{\infty} \le 1 \right\}, $$

$$ \|\mu\|_{FM} = \sup \left\{ \int_{Z} f \, d\mu : f \text{ is Lipschitz and } \|f\|_{\infty} + \text{Lip}(f) \le 1 \right\}, $$
where $\|f\|_{\infty} = \sup_{x \in \mathbf{Z}} |f(x)|$ is the infinity norm and Lip($f$) is the smallest constant $L > 0$ such that $f$ is $L$-Lipschitz. Those two norms are metrically equivalent, see beginning of Section 3.2 in [14]:

$$ (3.9) \qquad \|\mu\|_{\mathrm{FM}} \le \|\mu\|_{\mathrm{KR}} \le 2\|\mu\|_{\mathrm{FM}}. $$

Note that we have $\|\mu\|_{\mathrm{KR}} \le \|\mu\|_{\infty}$, and thus those two norms are sequentially continuous w.r.t. the weak topology on $M_{\pm}(\mathbf{Z})$.

An easy adaptation of the proof for Theorem 3.2.2 in [14] gives the following comparison between $d_{\mathrm{LP}}$, $\| \cdot \|_{\mathrm{KR}}$ and $\| \cdot \|_{\mathrm{FM}}$.

LEMMA 3.22 (Comparison of $d_{\mathrm{LP}}$, $\| \cdot \|_{\mathrm{KR}}$ and $\| \cdot \|_{\mathrm{FM}}$). — Let $\mu, \nu \in M_{+}(\mathbf{Z})$. Then, we have:

$$ \frac{d_{\mathrm{LP}}(\mu, \nu)^2}{1 + d_{\mathrm{LP}}(\mu, \nu)} \le \|\mu - \nu\|_{\mathrm{FM}} \le \|\mu - \nu\|_{\mathrm{KR}} \le (2 + \min(\mu(\mathbf{Z}), \nu(\mathbf{Z}))) d_{\mathrm{LP}}(\mu, \nu). $$

In particular, the Lévy–Prokhorov distance $d_{\mathrm{LP}}$ is uniformly continuous w.r.t. $\| \cdot \|_{\mathrm{KR}}$ and $\| \cdot \|_{\mathrm{FM}}$ on $M_{+}(\mathbf{Z})$; and $\| \cdot \|_{\mathrm{KR}}$ and $\| \cdot \|_{\mathrm{FM}}$ are uniformly continuous w.r.t. $d_{\mathrm{LP}}$ on $M_{\le 1}(\mathbf{Z})$.

For the special choice $N_{\mathrm{m}} = \| \cdot \|_{\mathrm{KR}}$ (resp. $N_{\mathrm{m}} = \| \cdot \|_{\mathrm{FM}}$), we use the subscript $\mathrm{m} = \mathrm{KR}$ (resp. $\mathrm{m} = \mathrm{FM}$).

### 3.8.3. A norm based on a convergence determining sequence

From a convergence determining sequence $\mathcal{F} = (f_k)_{k \in \mathbb{N}}$, where $f_0 = 1$ and $f_k \in C_b(\mathbf{Z})$ takes values in $[0, 1]$, we define a norm on $M_{\pm}(\mathbf{Z})$ metrizing the weak topology on $M_{+}(\mathbf{Z})$, for $\mu \in M_{\pm}(\mathbf{Z})$, by:

$$ (3.10) \qquad \|\mu\|_{\mathcal{F}} = \sum_{k \in \mathbb{N}} 2^{-k} |\mu(f_k)|. $$

Note that we have $\|\mu\|_{\mathcal{F}} \le 2\|\mu\|_{\infty}$, and thus $\| \cdot \|_{\mathcal{F}}$ is sequentially continuous w.r.t. the weak topology on $M_{\pm}(\mathbf{Z})$. For the special choice $N_{\mathrm{m}} = \| \cdot \|_{\mathcal{F}}$, we use the subscript $\mathrm{m} = \mathcal{F}$.

Even though the norm $\| \cdot \|_{\mathcal{F}}$ is not complete when $\mathbf{Z}$ is not compact (see Lemma 3.23 below), the cut norm $\| \cdot \|_{\square, \mathcal{F}}$ and the cut distance $\delta_{\square, \mathcal{F}}$ will turn out to be very useful in Sections 6 and 7 to link the topology of the cut distance to the homomorphism densities. Recall $d_{\mathcal{F}}$ is the distance derived from the norm $\| \cdot \|_{\mathcal{F}}$.

LEMMA 3.23 ($d_{\mathcal{F}}$ is not complete in general). — Let $\mathcal{F}$ be a convergence determining sequence. Then, the distance $d_{\mathcal{F}}$ is complete over $M_1(\mathbf{Z})$ if and only if $M_1(\mathbf{Z})$ is a compact space, i.e., if and only if $\mathbf{Z}$ is compact.
*Proof.* — Theorem 3.4 in [52] states that $\mathbf{Z}$ is compact if and only if $\mathcal{M}_1(\mathbf{Z})$ is compact. When this is the case, any distance metrizing the weak topology on $\mathcal{M}_1(\mathbf{Z})$ is complete.

Reciprocally, assume that $d_{\mathcal{F}}$ is a complete metric over $\mathcal{M}_1(\mathbf{Z})$ and write $\mathcal{F} = (f_m)_{m \in \mathbb{N}}$. Let $(\mu_n)_{n \in \mathbb{N}}$ be an arbitrary sequence of probability measures from $\mathcal{M}_1(\mathbf{Z})$. For every $m \in \mathbb{N}$, as $f_m$ takes values in $[0, 1]$, we have for every $n \in \mathbb{N}$ that $\mu_n(f_m) \in [0, 1]$. Hence, using a diagonal extraction, there exists a subsequence $(\mu_{n_k})_{k \in \mathbb{N}}$ of the sequence $(\mu_n)_{n \in \mathbb{N}}$ such that for every $m \in \mathbb{N}$, the sequence $(\mu_{n_k}(f_m))_{k \in \mathbb{N}}$ converges, that is, $(\mu_{n_k})_{k \in \mathbb{N}}$ is a Cauchy sequence for the distance $d_{\mathcal{F}}$. As we assumed the distance $d_{\mathcal{F}}$ to be complete, this implies that the sequence $(\mu_n)_{n \in \mathbb{N}}$ has a convergent subsequence. The sequence $(\mu_n)_{n \in \mathbb{N}}$ being arbitrary, we conclude that the space $\mathcal{M}_1(\mathbf{Z})$ is sequentially compact, and thus compact by Remark 2.6. $\square$

We denote by $\|\cdot\|_{\square, \mathbb{R}}$ (resp. $\|\cdot\|_{\square, \mathbb{R}}^{+}$) the cut norm (resp. one-sided version of the cut norm) for real-valued kernels defined as:

$$ (3.11) \qquad \begin{aligned} \|w\|_{\square, \mathbb{R}} &= \sup_{S, T \subset [0, 1]} \left| \int_{S \times T} w(x, y) \, dx dy \right| \\ \text{and} \quad \|w\|_{\square, \mathbb{R}}^{+} &= \sup_{S, T \subset [0, 1]} \int_{S \times T} w(x, y) \, dx dy, \end{aligned} $$

where $w$ is a real-valued kernel $w$ (see [46, Section 8.2], resp. [46, Section 10.3], for definition and properties of those objects).

Recall from (3.7) on page 53 the definition of the real-valued kernel $W[f]$ for $W \in \mathcal{W}_{\pm}$ and $f \in C_b(\mathbf{Z})$. The following two remarks link the cut norm $\|\cdot\|_{\square, \mathcal{F}}$ of a signed measure-valued kernel $W$ with the cut norm $\|\cdot\|_{\square, \mathbb{R}}$ of the real-valued kernels $W[f]$ for some particular choices of functions $f \in C_b(\mathbf{Z})$. We will reuse those facts in Section 6.

*Remark 3.24 (Link between $\|\cdot\|_{\square, \mathcal{F}}$ and $\|\cdot\|_{\square, \mathbb{R}}^{+}$).* — For $\mu \in \mathcal{M}_{\pm}(\mathbf{Z})$ we have:

$$ (3.12) \qquad \|\mu\|_{\mathcal{F}} = \sup_{\epsilon \in \{\pm 1\}^N} \sum_{n \in \mathbb{N}} 2^{-n} \epsilon_n \mu(f_n) = \sup_{\epsilon \in \{\pm 1\}^N} \mu \left( \sum_{n \in \mathbb{N}} 2^{-n} \epsilon_n f_n \right), $$
with $\varepsilon = (\varepsilon_n)_{n \in \mathbb{N}}$. Hence, for a signed measure-valued kernel $W \in W_{\pm}$, we have:

$$ (3.13) \qquad \begin{aligned} \|W\|_{\square, \mathcal{F}} &= \sup_{\varepsilon \in \{\pm 1\}^\mathbb{N}} \sup_{S, T \subset [0, 1]} W \left( S \times T; \sum_{n \in \mathbb{N}} 2^{-n} \varepsilon_n f_n \right) \\ &= \sup_{\varepsilon \in \{\pm 1\}^\mathbb{N}} \left\| W \left[ \sum_{n \in \mathbb{N}} 2^{-n} \varepsilon_n f_n \right] \right\|_{\square, \mathbb{R}}^{+} . \end{aligned} $$

Remark 3.25 (Inequality with $\| \cdot \|_{\square, \mathcal{F}}$ and $\| \cdot \|_{\square, \mathbb{R}}$). — For a signed measure-valued kernel $W$, we have:

$$ (3.14) \qquad \begin{aligned} \|W\|_{\square, \mathcal{F}} &= \sup_{S,T \subset [0,1]} \sum_{n=0}^{\infty} 2^{-n} \left| \int_{S \times T} W(x, y; f_n) \, dx dy \right| \\ &\le \sum_{n=0}^{\infty} 2^{-n} \sup_{S,T \subset [0,1]} \left| \int_{S \times T} W(x, y; f_n) \, dx dy \right| \\ &= \sum_{n=0}^{\infty} 2^{-n} \|W[f_n]\|_{\square, \mathbb{R}}. \end{aligned} $$

## 4. Tightness and weak regularity

In this section, using a conditional expectation approach as for real-valued kernels in [46, Chapter 9], we provide approximations of signed measure-valued kernels and probability-graphons by stepfunctions. In doing so, we prove that the space of probability-graphons (resp. the space of signed measure-valued kernels) is separable. We introduce a tightness criterion for signed measure-valued kernels and probability-graphons similar to the one for random measures; it will be used in the next section to characterise relatively compact subset of probability-graphons. We then prove a weak regularity property for cut distances which is a uniform approximation bound for tight subsets of signed measure-valued kernels and probability-graphons. This weak regularity property is an analogue of the weak regularity lemma for real-valued kernels from [27, Theorem 12] and [46, Lemma 9.15], but without an explicit bound on the quality of the approximation due to the lack of an Euclidean structure for signed measure-valued kernels. Lastly, we introduce some Euclidean structure on $W_{\pm}$ linked to the cut distance $d_{\square, \mathcal{F}}$, and we prove a weak regularity lemma with an explicit bound for signed measure-valued kernel.
## 4.1. Approximation by stepfunctions

We start by introducing the partitioning of a signed measure-valued kernel.

**DEFINITION 4.1 (The stepping operator).** — Let $W \in W_{\pm}$ be a signed measure-valued kernel and $\mathcal{P} = \{S_1, \dots, S_k\}$ be a finite partition of $[0, 1]$. We define the kernel stepfunction $W_{\mathcal{P}}$ adapted to the partition $\mathcal{P}$ by averaging $W$ over the partition subsets:

$$W_{\mathcal{P}}(x, y; \cdot) = \frac{1}{\lambda(S_i)\lambda(S_j)} W(S_i \times S_j; \cdot) \quad \text{for } x \in S_i, y \in S_j,$$

when $\lambda(S_i) \neq 0$ and $\lambda(S_j) \neq 0$, and $W_{\mathcal{P}}(x, y; \cdot) = 0$ the null measure otherwise. We call the map $W \mapsto W_{\mathcal{P}}$ defined on $W_{\pm}$ the stepping operator (associated with the finite partition $\mathcal{P}$).

Since the signed measure-valued kernel are defined up to an a.e. equivalence, the value of $W_{\mathcal{P}}(x, y; \cdot)$ for $x \in S_i, y \in S_j$ when $\lambda(S_i)\lambda(S_j)$ is unimportant.

**Remark 4.2 (Link with conditional expectation).** — The stepfunction $W_{\mathcal{P}}$ can be viewed as the conditional expectation of $W$ w.r.t. the (finite) sigma-field $\sigma(\mathcal{P} \times \mathcal{P})$ on $[0, 1]^2$, where $W : [0, 1]^2 \to \mathcal{M}_{\pm}(\mathbf{Z})$ is seen as a random signed measure in $\mathcal{M}_{\pm}(\mathbf{Z})$ and the probability measure on $[0, 1]^2$ is the Lebesgue measure.

**Remark 4.3 (Steppings are convex stable).** — Let $\mathcal{M} \subset \mathcal{M}_{\pm}(\mathbf{Z})$ be a convex subset of measures, for instance $\mathcal{M}$ is $\mathcal{M}_1(\mathbf{Z})$, $\mathcal{M}_{\le 1}(\mathbf{Z})$, $\mathcal{M}_+(\mathbf{Z})$ or $\mathcal{M}_{\pm}(\mathbf{Z})$. Whenever $W \in W_{\pm}$ is a $\mathcal{M}$-valued kernel, then by simple computation its stepping $W_{\mathcal{P}}$ is also a $\mathcal{M}$-valued kernel.

In the following remark, we give a characterization of refining partitions that generate the Borel $\sigma$-field of $[0, 1]$.

**Remark 4.4 (On refining partitions that generates the Borel $\sigma$-field).** — Let $(\mathcal{P}_k)_{k \in \mathbb{N}}$ be a sequence of refining partitions of $[0, 1]$. It generates the Borel $\sigma$-field of $[0, 1]$ (that is, $\{S : S \in \mathcal{P}_k, k \in \mathbb{N}\}$ generates the Borel $\sigma$-field of $[0, 1]$) if and only if $(\mathcal{P}_k)_{k \in \mathbb{N}}$ separates points (that is, for every distinct $x, y \in [0, 1]$, there exists $k \in \mathbb{N}$ such that $x$ and $y$ belong to different classes of $\mathcal{P}_k$).

Indeed, assume that $(\mathcal{P}_k)_{k \in \mathbb{N}}$ separates points, and consider the countable family of Borel-measurable functions $\mathcal{F} = \{1_S : S \in \mathcal{P}_k, k \in \mathbb{N}\}$ which separates points. Thus, by [13, Theorem 6.8.9] (remark that a Polish space
is a Souslin space, see [13, Definition 6.6.1]), the family $\mathcal{F}$ generates the Borel $\sigma$-field of $[0, 1]$. This implies that the family of Borel sets $\{S : S \in \mathcal{P}_k, k \in \mathbb{N}\}$ generates the Borel $\sigma$-field of $[0, 1]$.

Conversely, assume there exist $x, y \in [0, 1]$ which are not separated by $(\mathcal{P}_k)_{k \in \mathbb{N}}$, i.e. for all $k \in \mathbb{N}$, $x$ and $y$ belong to the same class of $\mathcal{P}_k$. This implies that the set $\{x\}$ does not belong to the $\sigma$-field generated by $(\mathcal{P}_k)_{k \in \mathbb{N}}$, and thus $(\mathcal{P}_k)_{k \in \mathbb{N}}$ does not generate the Borel $\sigma$-field of $[0, 1]$.

Recall the definition of the norm $\| \cdot \|_{\infty}$ on $W_{\pm}$ defined in (3.1). The following lemma allows to approximate any signed measure-valued kernel by its steppings.

**LEMMA 4.5** (Approximation using the stepping operator). — Let $W \in W_{\pm}$ be a signed measure-valued kernel (which is bounded by definition). Let $(\mathcal{P}_n)_{n \in \mathbb{N}}$ be a refining sequence of finite partitions of $[0, 1]$ that generates the Borel $\sigma$-field on $[0, 1]$. Then, the sequence $(W_{\mathcal{P}_n})_{n \in \mathbb{N}}$ is uniformly bounded by $\|W\|_{\infty}$, and weakly converges to $W$ almost everywhere (on $[0, 1]^2$).

*Proof*. — Set $W_n = W_{\mathcal{P}_n}$ for $n \in \mathbb{N}$. By definition of the stepping operator, we have for every $n \in \mathbb{N}$ and every $(x, y) \in [0, 1]^2$ that the total mass of $W_n(x, y; \cdot)$ is upper bounded by $\|W\|_{\infty}$.

Recall that for $W \in W_{\pm}$ and $f \in C_b(\mathbf{Z})$, the real-valued kernel $W[f]$ is defined by (3.7). First assume that $W \in W_+$. Let $\mathcal{F} = (f_k)_{k \in \mathbb{N}}$ be a convergence determining sequence, with by convention $f_0 = 1$. For every $k \in \mathbb{N}$ and $n \in \mathbb{N}$, an immediate computation gives $W_n[f_k] = (W[f_k])_{\mathcal{P}_n}$. For every $k \in \mathbb{N}$, as $W[f_k]$ is a real-valued kernel, we can apply the closed martingale theorem (as $(W[f_k])_{\mathcal{P}_n}$ can be viewed as a conditional expectation, see Remark 4.2), and we get that $\lim_{n \to \infty} W_n[f_k] = W[f_k]$ almost everywhere, since $(\mathcal{P}_n)_{n \in \mathbb{N}}$ generates the Borel $\sigma$-field. Hence, as the sequence $(f_k)_{k \in \mathbb{N}}$ is convergence determining, the sequence $(W_n)_{n \in \mathbb{N}}$ weakly converges to $W$ almost everywhere.

Now, for $W \in W_{\pm}$, write $W = W^{+} - W^{-}$ where $W^{+}, W^{-} \in W_{+}$ (see Lemma 3.3). By linearity of the stepping operator, remark that we have $W_n = (W^{+})_{\mathcal{P}_n} - (W^{-})_{\mathcal{P}_n}$ for all $n \in \mathbb{N}$. By the first case, we have that the sequence $((W^{+})_{\mathcal{P}_n})_{n \in \mathbb{N}}$ weakly converges a.e. to $W^{+}$, and similarly for $((W^{-})_{\mathcal{P}_n})_{n \in \mathbb{N}}$ and $W^{-}$. Hence, the sequence $(W_n)_{n \in \mathbb{N}}$ weakly converges to $W$ almost everywhere. $\square$

We first provide a separability result on the space of probability -graphons.
**PROPOSITION 4.6** (Separability of $W_1$ and $\tilde{W}_1$). — Let $d$ be a smooth distance on $W_1$ (resp. $W_+$ or $W_\pm$). Then, the space $(W_1, d)$ (resp. $(W_+, d)$ or $(W_\pm, d)$) is separable.

If furthermore $d$ is invariant (which implies that $\delta_{\square}$ is a distance), then the space $(\tilde{W}_1, \delta_{\square})$ (resp. $(\tilde{W}_+, \delta_{\square})$ or $(\tilde{W}_\pm, \delta_{\square})$) is separable.

In particular, this proposition can be applied when $d = \delta_{\square,m}$ and $d_m$ is a quasi-convex distance continuous w.r.t. the weak topology, as then $d_{\square,m}$ is invariant and smooth (recall Lemma 3.11 and Proposition 3.13).

*Proof*. — We shall consider the space of probability-graphons $W_1$, as the proofs for $W_+$ and $W_\pm$ are similar. Applying Lemma 4.5 with the sequence of dyadic partitions, for every probability-graphon $W$, we can find a sequence of probability-graphon stepfunctions adapted to finite dyadic partitions and converging to $W$ almost everywhere on $[0, 1]^2$.

As the space $Z$ is separable, the space of probability measures $M_1(Z)$ is also separable for the weak topology (see [11, Theorem 6.8]). Let $A \subset M_1(Z)$ be an at most countable dense (for the weak topology) subset. Then, for any stepfunction $W \in W_1$ adapted to a finite dyadic partition, we can approach it everywhere on $[0, 1]^2$ by a sequence of $A$-valued stepfunctions adapted to the same finite dyadic partition.

Hence, for every $W \in W_1$, there exists a sequence $(W_n)_{n \in \mathbb{N}}$ in the countable set of $A$-valued stepfunctions adapted to a finite dyadic partition that converges to $W$ almost everywhere on $[0, 1]^2$. As $d$ is smooth, we get that this convergence also holds for $d$. Thus, the space $(W_1, d)$ is complete.

Recall that by Theorem 3.17, when the distance $d$ is invariant and smooth, then the pseudometric $\delta_{\square}$ is a distance on $\tilde{W}_1$. In that case, convergence for $d$ implies convergence for $\delta_{\square}$, and thus the space $(\tilde{W}_1, \delta_{\square})$ is also separable. $\square$

## 4.2. Tightness

Similarly to the case of signed measures (recall Lemma 2.8), we introduce a tightness criterion for signed measure-valued kernels that characterizes relative compactness, see Proposition 4.8 below. For a signed measure-valued kernel $W \in W_\pm$, we define the measure $M_W \in M_+(Z)$ by:

$$ (4.1) \qquad M_W(dz) = |W|([0, 1]^2; dz) = \int_{[0,1]^2} |W|(x, y; dz) \, dxdy, $$

where for every $x, y \in [0, 1]$, $|W|(x, y; \cdot)$ is the total variation of $W(x, y; \cdot)$ (see Lemma 3.3). In particular, if $W$ is a probability-graphon then $M_W$ is a
probability measure from $M_1(\mathbf{Z})$. Notice also that if $W$ and $U$ are weakly isomorphic, then $M_W = M_U$, so that the application $W \mapsto M_W$ can be seen as a map from $\tilde{W}_1$ (resp. $\tilde{W}_\pm$) to $M_1(\mathbf{Z})$ (resp. $M_+(\mathbf{Z})$).

**DEFINITION 4.7 (Tightness criterion).** — A subset $\mathcal{K} \subset W_\pm$ (resp. $\mathcal{K} \subset \tilde{W}_\pm$) is said to be tight if the subset of measures $\{M_W : W \in \mathcal{K}\} \subset M_+(\mathbf{Z})$ is tight.

The following proposition shows the equivalence between a global tightness criterion and a local tightness criterion. Recall that uniformly bounded subsets of $\tilde{W}_\pm$ are discussed after Definition 3.16. Recall also $\lambda_2$ is the Lebesgue measure on $[0, 1]^2$.

**PROPOSITION 4.8 (Alternative tightness criterion).** — Let $\mathcal{K} \subset W_\pm$ (or $\mathcal{K} \subset \tilde{W}_\pm$) be a uniformly bounded subset of signed measure-valued kernels. The set $\mathcal{K}$ is tight if and only if for every $\varepsilon > 0$, there exists a compact set $K \subset \mathbf{Z}$, such that for every $W \in \mathcal{K}$ we have:

$$ (4.2) \qquad \lambda_2\left(\{(x, y) \in [0, 1]^2 : |W|(x, y; K^c) \le \varepsilon\}\right) > 1 - \varepsilon. $$

*Proof.* — As the left hand side of (4.2) is invariant by relabeling, it is enough to do the proof for $W_\pm$. Let $\mathcal{K} \subset W_\pm$ be uniformly bounded and set $C = \sup_{W \in \mathcal{K}} \|W\|_\infty < \infty$. Assume that for every $\varepsilon > 0$, there exists a compact set $K \subset \mathbf{Z}$, such that (4.2) holds for every $W \in \mathcal{K}$. Let $1 > \varepsilon > 0$. Thus, there exists a compact subset $K \subset \mathbf{Z}$ such that for every $W \in \mathcal{K}$ there exists a subset $A_W \subset [0, 1]^2$ with (Lebesgue) measure at least $1 - \varepsilon$, such that for every $(x, y) \in A_W$, we have $|W|(x, y; K^c) \le \varepsilon$. We have that for all $W \in \mathcal{K}$:

$$ \begin{aligned} M_W(K^c) &= \int_{[0,1]^2} |W|(x, y; K^c) \,dx dy \le \|W\|_\infty \lambda_2(A_W^c) + \varepsilon \lambda_2(A_W) \\ &\le (C+1)\varepsilon. \end{aligned} $$

Hence, the subset of measures $\{M_W : W \in \mathcal{K}\} \subset M_+(\mathbf{Z})$ is tight, that is $\mathcal{K}$ is tight.

Conversely, suppose that $\mathcal{K}$ is tight. Let $\varepsilon > 0$. There exists a compact set $K \subset \mathbf{Z}$ such that for every $W \in \mathcal{K}$, we have $M_W(K^c) < \varepsilon^2$. For $W \in \mathcal{K}$, define $A_W = \{(x, y) \in [0, 1]^2 : |W|(x, y; K^c) \le \varepsilon\}$. We have:

$$ \varepsilon^2 > M_W(K^c) = \int_{[0,1]^2} |W|(x, y; K^c) \,dx dy \ge \varepsilon \lambda_2(A_W^c). $$

Hence, $\lambda_2(A_W) > 1 - \varepsilon$, and consequently Equation (4.2) holds. $\square$

We end this section on a continuity result of the map $W \mapsto M_W$.
**LEMMA 4.9** (Regularity of the map $W \mapsto M_W$). — Let $d_m$ be a distance on $M_{\le 1}(\mathbf{Z})$ (resp. $M_+(\mathbf{Z})$). Then the map $W \mapsto M_W$ is 1-Lipschitz, and thus continuous, from $(\widetilde{M}_{1,m}, \delta_{\square,m})$ (resp. $(\widetilde{M}_{+,m}, \delta_{\square,m})$) to $(M_1(\mathbf{Z}), d_m)$ (resp. $(M_+(\mathbf{Z}), d_m)$).

*Proof.* — Taking $S = T = [0, 1]$ in Definition (3.2) of $d_{\square,m}$, we get that $d_m(M_U, M_W) \le d_{\square,m}(W, U)$. As $M_{U\phi} = M_U$ for any measure-preserving map $\phi$ thanks to (2.1), we deduce from Definition (3.5) of $\delta_{\square,m}$ that $d_m(M_U, M_W) \le \delta_{\square,m}(U, W)$. $\square$

## 4.3. Weak regularity

We shall consider the following extra regularities of distances on the set of signed measure-valued kernels w.r.t. the stepping operator. For a finite partition $\mathcal{P}$, denote by $|\mathcal{P}|$ the size of the partition $\mathcal{P}$, i.e. the number of sets composing $\mathcal{P}$.

**DEFINITION 4.10** (Regularities of distances). — Let $d$ be a distance on $W_1$ (resp. $W_+$ or $W_\pm$).

(i) **Weak regularity.** The distance $d$ is weakly regular if whenever the subset $\mathcal{K}$ of $W_1$ (resp. $W_+$ or $W_\pm$) is tight (resp. tight and uniformly bounded), then for every $\varepsilon > 0$, there exists $m \in \mathbb{N}^*$, such that for every kernel $W \in \mathcal{K}$, and for every finite partition $\mathcal{Q}$ of $[0, 1]$, there exists a finite partition $\mathcal{P}$ of $[0, 1]$ that refines $\mathcal{Q}$ such that:

$$ |\mathcal{P}| \le m|\mathcal{Q}| \quad \text{and} \quad d(W, W_{\mathcal{P}}) < \varepsilon. $$

(ii) **Regularity w.r.t. the stepping operator.** The distance $d$ is regular w.r.t. the stepping operator if (resp. for any finite constant $C \ge 0$) there exists a finite constant $C_0 > 0$ such that for every $W, U$ in $W_1$ (resp. in $W_+$ or $W_\pm$, with $\|W\|_\infty \le C$ and $\|U\|_\infty \le C$) and every finite partition $\mathcal{P}$ of $[0, 1]$, then we have:

$$ (4.3) \qquad d(W, W_{\mathcal{P}}) \le C_0 d(W, U_{\mathcal{P}}). $$

We say that a norm $N$ on $W_\pm$ is weakly regular (resp. regular w.r.t. the stepping operator) if its associated distance $d$ on $W_\pm$ is weakly regular (resp. regular w.r.t. the stepping operator).

The weak regularity property above is an analogue to the weak regularity lemma for real-valued graphons, see [27, Theorem 12] or [46, Lemma 9.15]. In those two references there is an explicit relation between $m$ and $\varepsilon$ (namely that $m = 2^{\lceil 1/\varepsilon^2 \rceil}$). This is not the case here because we shall consider it
for cut distances $d_{\square,m}$ associated to a general distance $d_m$, and they are not associated to an Euclidean structure (see also Section 4.4 for a stronger version of the weak regularity property with the cut distance $d_{\square,\mathcal{F}}$ which is indeed associated to an Euclidean structure).

If a distance $d$ is weakly regular, then for a subset $K \subset \mathcal{M}_{\pm}(\mathbf{Z})$ which is tight and uniformly bounded, every $K$-valued kernel can be approximated by a stepfunction with a uniform bound. The regularity w.r.t. the stepping operator states that the stepping operator gives an almost optimal way to approximate a signed measure-valued kernel using stepfunctions adapted to a given partition.

### 4.3.1. An example of cut distance regular w.r.t. the stepping operator

Recall the definition of a quasi-convex distance in Definition 2.10. We first show that the stepping operator is 1-Lipschitz for the cut distance $d_{\square,m}$ when the distance $d_m$ is quasi-convex.

**LEMMA 4.11** (The stepping operator is 1-Lipschitz). — Let $d_m$ be a quasi-convex distance on $\mathcal{M}$ a convex subset of $\mathcal{M}_{\pm}(\mathbf{Z})$ containing the zero measure. Then, the stepping operator associated with a given finite partition of $[0, 1]$ is 1-Lipschitz on $W_{\mathcal{M}}$ for the cut distance $d_{\square,m}$.

*Proof.* — Let $U, W \in W_{\mathcal{M}}$ be $\mathcal{M}$-valued kernels, and let $\mathcal{P}$ be a finite measurable partition of $[0, 1]$. As $U_{\mathcal{P}}$ and $W_{\mathcal{P}}$ are stepfunctions adapted to the same partition, and as $d_m$ is quasi-convex, we can use Lemma 3.19 to get for some $S, T \in \sigma(\mathcal{P})$ that:

$$ 
\begin{aligned}
d_{\square,m}(U_{\mathcal{P}}, W_{\mathcal{P}}) &= d_m(U_{\mathcal{P}}(S \times T; \cdot), W_{\mathcal{P}}(S \times T; \cdot)) \\
&= d_m(U(S \times T; \cdot), W(S \times T; \cdot)) \\
&\le d_{\square,m}(U, W),
\end{aligned}
$$

where the second equality comes from the fact that the integrals are equal as $S, T \in \sigma(\mathcal{P})$ and thus the integration is over full steps of the partition. Hence, the stepping operator is 1-Lipschitz on $W_{\mathcal{M}}$ for the cut distance $d_m$. $\square$

For a quasi-convex distance $d_m$, the cut distance $d_{\square,m}$ is regular w.r.t. the stepping operator with $C_0 = 2$ in (4.3) (and one can take $C = +\infty$ in Definition 4.10 (ii)).

**LEMMA 4.12** ($d_{\square,m}$ is regular w.r.t. the stepping operator). — Let $d_m$ be a quasi-convex distance on $\mathcal{M}$ a convex subset of $\mathcal{M}_{\pm}(\mathbf{Z})$ containing
the zero measure. Let $W, U \in W_\epsilon$ be $W_M$-valued kernels, and let $\mathcal{P}$ be a finite partition of $[0, 1]$. Then, we have:

$$d_{\square,m}(W, W_{\mathcal{P}}) \le 2d_{\square,m}(W, U_{\mathcal{P}}).$$

*Proof.* — The proof is similar to the proof of [46, Lemma 9.12]. As $d_m$ is quasi-convex, using Lemma 4.11, we get:

$$d_{\square,m}(W, W_{\mathcal{P}}) \le d_{\square,m}(W, U_{\mathcal{P}}) + d_{\square,m}(U_{\mathcal{P}}, W_{\mathcal{P}}) \le 2d_{\square,m}(W, U_{\mathcal{P}}).$$

□

### 4.3.2. An example of weakly regular cut distance

We have the following general result. Recall Definitions 3.10 and 4.10 on distances and norms on $W_\epsilon$, with $\epsilon \in \{+, \pm\}$, being invariant, smooth, weakly regular and regular w.r.t. the stepping operator.

**PROPOSITION 4.13 (Weak regularity of $d_{\square,m}$).** — Let $d_m$ be a quasi-convex distance on $M_\epsilon(Z)$, with $\epsilon \in \{+, \pm\}$, which is sequentially continuous w.r.t. the weak topology. Then, the cut distance $d_{\square,m}$ on $W_\epsilon$ is invariant, smooth, weakly regular and regular w.r.t. the stepping operator.

Using results from Section 3.8, we directly get the following weak regularity of the cut distance $d_{\square,LP}$ and the cut norms $\|\cdot\|_{\square,\mathcal{F}}$, $\|\cdot\|_{\square,KR}$ and $\|\cdot\|_{\square,FM}$.

**COROLLARY 4.14 (Weak regularity of usual distances and norms).** — The cut norms $\|\cdot\|_{\square,\mathcal{F}}$, $\|\cdot\|_{\square,KR}$ and $\|\cdot\|_{\square,FM}$ (resp. the cut distance $d_{\square,LP}$) on $W_\pm$ (resp. $W_+$) are invariant, smooth, weakly regular and regular w.r.t. the stepping operator.

*Proof of Proposition 4.13.* — We deduce from Lemmas 3.11 and 4.12, Proposition 3.13 and that the cut distance $d_{\square,m}$ on $W_\epsilon$ is invariant, smooth and regular w.r.t. the stepping operator. We are left to prove that $d_{\square,m}$ is weakly regular on $W_\epsilon$. We prove it by considering in the first step the case $Z$ compact and in a second step the general case $Z$ Polish.

**Step 1.** We assume $Z$ compact. As in the definition of weak regularity, let $K \subset W_\epsilon$ be a subset of $M_\epsilon(Z)$-valued kernels that is tight and uniformly bounded by some finite constant $C$. Let $M \subset M_\epsilon(Z)$ be the subset of elements of $M_\epsilon(Z)$ with total mass at most $C$; in particular $M$ is a convex set containing 0 and $K \subset W_M$. As $Z$ is compact, from Remarks 2.6 and 2.7, we know that the weak topology is metrizable on $M$ and that $M$ is compact, and thus sequentially weakly compact. Hence, as $d_m$ is sequentially
continuous w.r.t. the weak topology on $M_\epsilon(\mathbb{Z})$, we have that $(M, d_m)$ is sequentially compact, and thus compact.

Denote by $B(\mu, r) = \{\nu \in \mathcal{M} : d_m(\mu, \nu) < r\}$ the open ball centered at $\mu \in \mathcal{M}$ with radius $r > 0$. Let $\epsilon > 0$. As $\mathcal{M}$ is compact, there exist $\mu_1, \dots, \mu_n \in \mathcal{M}$, $n \in \mathbb{N}^*$, such that $\mathcal{M} = \cup_{i=1}^n B(\mu_i, \epsilon)$. For $1 \le i \le n$, define $A_i = B(\mu_i, \epsilon) \setminus \cup_{j<i} B(\mu_j, \epsilon)$, so that $\{A_1, \dots, A_n\}$ is a finite partition (with possibly some empty sets) of $\mathcal{M}$.

Every $\mathcal{M}$-valued kernel $W$ can be approximated by a $\{\mu_1, \dots, \mu_n\}$-valued kernel $U$ defined for every $(x, y) \in [0, 1]^2$ by $U(x, y; \cdot) = \mu_i$ for $i$ such that $W(x, y; \cdot) \in A_i$. Thus, by construction, we have that for every $(x, y) \in [0, 1]^2$, $d_m(W(x, y; \cdot), U(x, y; \cdot)) < \epsilon$. Applying the quasi-convex supremum inequality from (3.4) to $W$ and $U$, we get that:

$$d_{\square,m}(W,U) \le \underset{(x,y) \in [0,1]^2}{\operatorname{essup}} d_m(W(x,y;\cdot), U(x,y;\cdot)) \le \epsilon.$$

Then, as the stepping operator is 1-Lipschitz for the cut norm, see Lemma 4.11, we have for any finite partition $\mathcal{P}$ of $[0, 1]$ that:

$$d_{\square,m}(W, W_{\mathcal{P}}) \le d_{\square,m}(W, U) + d_{\square,m}(U, U_{\mathcal{P}}) + d_{\square,m}(U_{\mathcal{P}}, W_{\mathcal{P}}) \\ \le 2\epsilon + d_{\square,m}(U, U_{\mathcal{P}}). \tag{4.4}$$

Hence, to get the weak regularity property for $\mathcal{M}$-valued kernels, we are left to prove it for the much smaller set of $\mathcal{V}$-valued kernels, where $\mathcal{V}$ is the convex hull of $\{\mu_1, \dots, \mu_n\}$.

As $d_m$ is quasi-convex and sequentially continuous w.r.t. the weak topology, using Lemma 2.11, there exists $\eta > 0$ such that for all $\mu, \nu \in M_\epsilon(\mathbb{Z})$, we have that $\|\mu - \nu\|_\infty < \eta$ implies that $d_m(\mu, \nu) \le \epsilon$.

As $\mathcal{V}$ is a subset of a vector space with finite dimension $n$, the norm $\|\cdot\|_\infty$ seen over $\mathcal{V}$ is equivalent to the $L_1$-norm $\mu = \sum_{i=1}^n \alpha_i \mu_i \mapsto \|\alpha\|_1 = \sum_{i=1}^n |\alpha_i|$. We can now see $\mathcal{V}$-valued kernel as $\mathbb{R}^n$-valued graphon with a cut norm derived from the $L_1$-norm $\|\cdot\|_1$. In this case the proof for the weak regularity Lemma 9.9 in [46] in $\mathbb{R}$ can easily be adapted to $\mathbb{R}^n$ by first decomposing the $\mathbb{R}^n$-valued kernels into their $n$ dimensional marginals $(w_1, \dots, w_n)$ which are all real-valued kernels, then applying the weak regularity Lemma 9.9 in [46] to each of the $w_i$'s independently with precision $\epsilon' = \epsilon/n$ giving partitions $\mathcal{P}_i$ for $i \in \{1, \dots, n\}$, and lastly defining $\mathcal{P}$ as the common refinement of the $\mathcal{P}_i$'s and using Lemma 9.12 in [46] for regularity w.r.t. the stepping operator to conclude. Hence, we have the weak regularity property for $\mathcal{V}$-valued kernels: there exists $m \in \mathbb{N}^*$, such that for every $\mathcal{V}$-valued kernel $U'$, and for every finite partition $\mathcal{Q}$ of $[0, 1]$ there
exists a finite partition $\mathcal{P}$ of $[0, 1]$ that refines $\mathcal{Q}$, and such that $|\mathcal{P}| \le m|\mathcal{Q}|$ and $\sup_{S,T \subset [0,1]} \|(U' - U'_P)(S \times T; \cdot)\|_{\infty} < \eta$, and thus $d_{\square,m}(U', U'_P) \le \varepsilon$.

Taking $U' = U$ in (4.4), we get that $d_{\square,m}(W, W_P) \le 3\varepsilon$ and $|\mathcal{P}| \le m|\mathcal{Q}|$. This concludes the proof of the lemma when $\mathbb{Z}$ is compact.

**Step 2.** We consider the general case $\mathbb{Z}$ Polish. We now prove that $d_{\square,m}$ is weakly regular on $W_\epsilon$. Let $\mathcal{K} \subset W_\epsilon$ be a subset of $M_\epsilon(\mathbb{Z})$-valued kernels that is tight and uniformly bounded, and denote by $C = \sup_{W \in \mathcal{K}} \|W\|_\infty < \infty$.

Let $\varepsilon > 0$. As $d_m$ is quasi-convex and sequentially continuous w.r.t. the weak topology, using Lemma 2.11, there exists $\eta > 0$ such that for all $\mu, \nu \in M_\epsilon(\mathbb{Z})$, we have that $\|\mu - \nu\|_\infty < \eta$ implies that $d_m(\mu, \nu) < \varepsilon$. Without loss of generality, we assume that $\eta \le \varepsilon$. Let $\eta_C = \min(\eta, \eta/C)$.

As $\mathcal{K}$ is tight, using Proposition 4.8, there exists a compact set $K \subset \mathbb{Z}$, such that for every $W \in \mathcal{K}$ the subset $A_W = \{(x, y) \in [0, 1]^2 : |W|(x, y; K^c) \le \eta_C/2\}$ has Lebesgue measure at least $1 - \eta_C/2$. Let $W \in \mathcal{K}$, and define the signed measure-valued kernel $U$ by: $U(x, y; \cdot) = W(x, y; \cdot \cap K)$ for every $(x, y) \in A_W$, and $U(x, y; \cdot) = 0$ otherwise. Let $S, T \subset [0, 1]$. We have:

$$ \begin{aligned} \|(W - U)(S \times T; \cdot)\|_{\infty} &\le \int_{S \times T} \|W(x, y; \cdot) - U(x, y; \cdot)\|_{\infty} \,dx\,dy \\ &\le \int_{A_W \cap (S \times T)} |W|(x, y; K^c) \,dx\,dy \\ &\quad + \int_{A_W^c \cap (S \times T)} \|W(x, y; \cdot)\|_{\infty} \,dx\,dy \\ &\le \eta_C/2 + C \cdot \eta_C/2 \\ &\le \eta. \end{aligned} $$

Thus, we have that $d_m(W(S \times T; \cdot), U(S \times T; \cdot)) < \varepsilon$. Since this holds for all $S, T \subset [0, 1]$, we get that $d_{\square,m}(W, U) \le \varepsilon$.

Notice that the $M_\pm(\mathbb{Z})$-valued kernel $U$ is also a $M_\pm(K)$-valued kernel, where $K \subset \mathbb{Z}$ is a compact set, and that $\|U\|_\infty \le \|W\|_\infty \le C$. Further remark that, using Lemma 4.11, for every $W \in \mathcal{K}$ and every finite partition $\mathcal{P}$ of $[0, 1]$, we have that:

$$ \begin{aligned} d_{\square,m}(W, W_P) &\le d_{\square,m}(W, U) + d_{\square,m}(U, U_P) + d_{\square,m}(U_P, W_P) \\ &\le 2\varepsilon + d_{\square,m}(U, U_P). \end{aligned} $$

Hence, to get the weak regularity property for $d_{\square,m}$ on $\mathcal{K}$ (see Definition 4.10 (i)), it is enough to prove that $d_{\square,m}$ restricted to $M_\epsilon(K)$-valued kernels is weakly regular, which is true by Step 1. As a consequence, we get that $d_{\square,m}$ on $W_\epsilon$ is weakly regular. $\square$
## 4.4. A stronger weak regularity lemma for $d_{\square, \mathcal{F}}$

In this subsection, we prove a stronger version of the weak regularity lemma for the special case of the cut distance $d_{\square, \mathcal{F}}$. We shall use this result for the proof of the second sampling Lemma 6.12.

Let $\mathcal{F} = (f_n)_{n \in \mathbb{N}}$, with $f_0 = 1$ and $f_n$ takes values in $[0, 1]$, be a convergence determining sequence, which is assumed fixed in this section.

### 4.4.1. Comparison between $\| \cdot \|_{\square, \mathcal{F}}$ and an Euclidian norm

To better understand the stepping operator, we introduce a scalar product over signed measure-valued kernels. The link between this scalar product and the norm $\| \cdot \|_{\square, \mathcal{F}}$ is given by Lemma 4.15. We define the scalar product $\langle \cdot, \cdot \rangle_{\mathcal{F}}$ on signed measure-valued kernels for $U, W \in W_{\pm}$ by:

$$ \langle U, W \rangle_{\mathcal{F}} = \sum_{n \ge 0} 2^{-n} \langle U[f_n], W[f_n] \rangle, $$

where for all $n$ the scalar product taken for $U[f_n]$ and $W[f_n]$ is the usual scalar product in $L^2([0, 1]^2, \lambda_2)$ for real-valued kernels:

$$ \langle U[f_n], W[f_n] \rangle = \int_{[0,1]^2} U[f_n](x, y) W[f_n](x, y) \, dx dy. $$

The scalar product $\langle \cdot, \cdot \rangle_{\mathcal{F}}$ induces a norm on $W_{\pm}$ which we denote by $\| \cdot \|_{2, \mathcal{F}}$.

Let $\mathcal{P}$ be a finite partition of $[0, 1]$. As the stepping operator for measurable real-valued $L^2$ functions on $[0, 1]^2$ is a linear projection, and is idempotent and symmetric, and by definition of the scalar product $\langle \cdot, \cdot \rangle_{\mathcal{F}}$ for signed measure-valued kernels, we have that the stepping operator for signed measure-valued kernels is linear, idempotent and symmetric for $\langle \cdot, \cdot \rangle_{\mathcal{F}}$. Moreover, the stepping operator is the orthogonal projection for $\langle \cdot, \cdot \rangle_{\mathcal{F}}$ onto the space of stepfunctions with steps in $\mathcal{P}$.

Note that for a probability-graphon $W \in W_1$, we have $\|W\|_{2, \mathcal{F}} \le \sqrt{2}$ as each $f_n$ takes values in $[0, 1]$. The following technical lemma gives a comparison between $\| \cdot \|_{\square, \mathcal{F}}$ and $\| \cdot \|_{2, \mathcal{F}}$.

**LEMMA 4.15 (Comparison between $\| \cdot \|_{\square, \mathcal{F}}$ and $\| \cdot \|_{2, \mathcal{F}}$).** — For a signed measure-valued kernel $W \in W_{\pm}$, we have $\|W\|_{\square, \mathcal{F}} \le \sqrt{2}\|W\|_{2, \mathcal{F}}$.

*Proof.* — Let $S, T \subset [0, 1]$ be measurable subsets. By the Cauchy–Schwarz inequality, we have $|\langle W[f_n], 1_{S \times T} \rangle|^2 \le \|W[f_n]\|_2^2 =$
$\langle W[f_n], W[f_n] \rangle$ for every $n \ge 0$. Using this inequality along with Jensen's inequality, we get for every $S, T \subset [0, 1]$ that:

$$ \left( \sum_{n \ge 0} 2^{-n} |W(S \times T, f_n)| \right)^2 = \left( \sum_{n \ge 0} 2^{-n} |\langle W[f_n], 1_{S \times T} \rangle| \right)^2 \\ \le \sum_{n \ge 0} 2^{-n+1} |\langle W[f_n], 1_{S \times T} \rangle|^2 \\ \le \sum_{n \ge 0} 2^{-n+1} \langle W[f_n], W[f_n] \rangle \\ = 2(\|W\|_{2,\mathcal{F}})^2. $$

Taking the supremum over every measurable subsets $S, T \subset [0, 1]$ gives the desired inequality. □

4.4.2. The weak regularity lemma for $\| \cdot \|_{\square, \mathcal{F}}$

The following lemma gives an explicit bound on the approximation of a signed measure-valued kernel, say $W$, by its steppings $W_\mathcal{P}$, with $\mathcal{P}$ a finite partition on $[0, 1]$. Its proof is a straightforward adaptation of the proof of the weak regularity lemma for real-valued graphons in [46, Lemma 9.9].

LEMMA 4.16 (Weak regularity lemma for $\| \cdot \|_{\square, \mathcal{F}}$, simple formulation). For every signed measure-valued kernel $W \in W_\pm$ and $k \ge 1$, there exists a finite partition $\mathcal{P}$ of $[0, 1]$ such that $|\mathcal{P}| = k$ and:

$$ \|W - W_{\mathcal{P}}\|_{\square, \mathcal{F}} \le \frac{\sqrt{8}}{\sqrt{\log(k)}} \|W\|_{2, \mathcal{F}}. $$

In particular, if $W \in W_1$ is a probability-graphon, (as $\|W\|_{2,\mathcal{F}} \le \sqrt{2}$) we have:

$$ \|W - W_{\mathcal{P}}\|_{\square, \mathcal{F}} \le \frac{4}{\sqrt{\log(k)}}. $$

It is possible in the weak regularity lemma to ask for extra requirements, for instance to start from an already existing partition, or to ask the partition to be balanced, as stated in the following lemma. The proof is a straightforward adaptation of the proof of [46, Lemma 9.15].

LEMMA 4.17 (Weak regularity lemma for $\| \cdot \|_{\square, \mathcal{F}}$, with extra requirements). — Let $W \in W_1$ be a probability-graphon, and let $1 \le m < k$.
(i) For every partition $\mathcal{Q}$ of $[0, 1]$ into $m$ classes, there is a partition $\mathcal{P}$ with $k$ classes refining $\mathcal{Q}$ and such that:

$$ \|W - W_{\mathcal{P}}\|_{\square, \mathcal{F}} \le \frac{4}{\sqrt{\log(k/m)}}. $$

(ii) For every partition $\mathcal{Q}$ of $[0, 1]$ into $m$ classes, there is an equipartition (i.e. a finite partition into classes with the same measure) $\mathcal{P}$ of $[0, 1]$ into $k$ classes and such that:

$$ \|W - W_{\mathcal{P}}\|_{\square, \mathcal{F}} \le 2 \|W - W_{\mathcal{Q}}\|_{\square, \mathcal{F}} + \frac{2m}{k}. $$

# 5. Compactness and completeness of $\tilde{W}_1$

In this section, we study compactness and completeness properties of the space of probability-graphon $\tilde{W}_1$, as well as the relation between the topologies induced by the different cut distances $\delta_{\square,m}$ (associated to the distance $d_m$ on $M_{\le 1}(\mathbb{Z})$ which induces the weak topology). While the space of real-valued graphons equipped with the cut distance is compact (see [48] or [46, Section 9.3]), this is not true in general for probability-graphons as the space of probability measures on a Polish space is not compact in general. Then, using the tightness criterion introduced in Section 4.2, we characterize subsets of probability-graphons and measure-valued kernels that are relatively compact w.r.t. the cut distance $\delta_{\square,m}$, see in Section 5.1. Recall that unlike for $\mathbb{R}$ with its usual topology, there is no canonical distance $d_m$ on the space of signed measures $M_{\pm}(\mathbb{Z})$ inducing the weak topology. For this reason, it is necessary to consider cut distances $\delta_{\square,m}$ for signed measure-valued kernels and probability-graphons indexed by several distances $d_m$. Lastly, in Section 5.2, we compare the topologies induced by the cut distance $\delta_{\square,m}$ for different choice of $d_m$, and state that under some conditions on $d_m$, those topologies coincide. In Section 5.3, we investigate the completeness of $\tilde{W}_1$ endowed with the cut distance $\delta_{\square,m}$ and prove that the space of probability-graphons $\tilde{W}_1$ is a Polish space (Theorem 5.10), and that it is compact if and only if $\mathbb{Z}$ is compact (Corollary 5.13). The technical proofs are postponed to Section 8.

## 5.1. Tightness criterion and compactness

Let $M \subset M_{\pm}(\mathbb{Z})$ be a subset of signed measures on $\mathbb{Z}$. Recall that $W_M \subset W_{\pm}$ denotes the subset of signed measure-valued kernels which are
$\mathcal{M}$-valued. In this section, we shall denote by $\tilde{W}_M$ the quotient of $W_M$ identifying signed measure-valued kernels that are weakly isomorphic.

Recall from Definition 3.15 and Theorem 3.17 that for an invariant, smooth and weakly regular distance $d$ on $W_1$ (resp. $W_+$, $W_\pm$), $\delta_\square$ is defined as $\delta_\square(U, W) = \inf_{\varphi \in S_{[0,1]}} d(U, W^\varphi)$, and is a distance on $\tilde{W}_1$ (resp. $\tilde{W}_+$, $\tilde{W}_\pm$).

We are now ready to formulate the following important theorem, which relates tightness with compactness and convergence for signed measure-valued kernels. We prove this theorem in Section 8.

**THEOREM 5.1 (Compactness theorem for $\tilde{W}_1$).** — Let $d$ be an invariant, smooth and weakly regular distance on $W_1$ (resp. $W_\pm$).

(i) If a sequence of elements of $W_1$ or $\tilde{W}_1$ (resp. $W_\pm$ or $\tilde{W}_\pm$) is tight (resp. tight and uniformly bounded), then it has a subsequence converging for $\delta_\square$.

(ii) If $\mathcal{M} \subset \mathcal{M}_1(\mathbf{Z})$ (resp. $\mathcal{M} \subset \mathcal{M}_\pm(\mathbf{Z})$) is convex and compact (resp. sequentially compact) for the weak topology, then the space $(\tilde{W}_M, \delta_\square)$ is convex and compact.

(iii) If $\mathbf{Z}$ is compact, then the space $(\tilde{W}_1, \delta_\square)$ is compact.

In particular, this theorem can be applied when $d = d_{\square,m}$ and $d_m$ is a quasi-convex distance continuous w.r.t. the weak topology, as then $d_{\square,m}$ is invariant, smooth and weakly regular (recall Proposition 4.13).

We deduce from this theorem a characterization of relative compactness for subsets of probability-graphons.

**PROPOSITION 5.2 (Characterization of relative compactness).** — Let $d_m$ be a distance on $\mathcal{M}_{\le 1}(\mathbf{Z})$ (resp. $\mathcal{M}_+(\mathbf{Z})$ or $\mathcal{M}_-(\mathbf{Z})$) that induces the weak topology on $\mathcal{M}_{\le 1}(\mathbf{Z})$ (resp. $\mathcal{M}_+(\mathbf{Z})$). Assume that the distance $d_{\square,m}$ on $W_1$ (resp. $W_+$ or $W_\pm$) is (invariant) smooth and weakly regular.

(i) If a sequence of elements of $W_1$ or $\tilde{W}_1$ (resp. $W_+$ or $\tilde{W}_+$) is converging for $\delta_{\square,m}$, then it is tight.

(ii) Let $\mathcal{K}$ be a subset of $\tilde{W}_1$ (resp. a uniformly bounded subset of $\tilde{W}_+$). Then, the set $\mathcal{K}$ is relatively compact for $\delta_{\square,m}$ if and only if it is tight.

(iii) Let $\mathcal{M}$ be a subset of $\mathcal{M}_+(\mathbf{Z})$ which is bounded, convex and closed for the weak topology. Then the set $\tilde{W}_M$ is convex and closed in $\tilde{W}_+$.

Remark that convergence for $\delta_{\square,m}$ does not necessarily imply tightness on $W_\pm$ or on $\tilde{W}_\pm$.
*Proof.* — We consider the case where $d_m$ is a distance on $M_+(Z)$ or $M_\pm(Z)$, the case with $M_{\le 1}(Z)$ is similar.

We prove Point (i). Let $(W_n)_{n \in \mathbb{N}}$ be a convergent sequence of $W_+$ (and thus of $\tilde{W}_+$) for $\delta_{\square,m}$. We deduce from the continuity of the map $W \mapsto M_W$, see Lemma 4.9, that the sequence $(M_{W_n})_{n \in \mathbb{N}}$ is converging for $d_m$, and thus is tight as $d_m$ induces the weak topology on $M_+(Z)$. Then, by definition the sequence $(W_n)_{n \in \mathbb{N}}$ is tight.

We prove Point (ii). If $K \subset \tilde{W}_+$ is tight and uniformly bounded, then by Theorem 5.1 (i) every sequence in $K$ has a subsequence converging for $\delta_{\square,m}$, which implies that $K$ is relatively compact in the metric space $(\tilde{W}_+, \delta_{\square,m})$ (see Remark 2.1).

Conversely, assume that $K \subset \tilde{W}_+$ is uniformly bounded and relatively compact for $\delta_{\square,m}$. Define $M = \{M_W : W \in K\} \subset M_+(Z)$. By Lemma 4.9, the mapping $W \mapsto M_W$ is continuous from $(\tilde{W}_1, \delta_{\square,m})$ to $(M_+(Z), d_m)$. Hence, as $d_m$ induces the weak topology on $M_+(Z)$, the set $M$ is also relatively compact in $M_+(Z)$ for the weak topology. As the space $Z$ is Polish, applying Lemma 2.8, we get that $M \subset M_+(Z)$ is tight, and by Definition 4.7, the set $K \subset \tilde{W}_+$ is tight.

We postpone the proof of Point (iii) to Section 8 on page 109. □

## 5.2. Equivalence of topologies induced by $\delta_{\square,m}$

The following lemma allows to show a first result on equivalence of the topologies induced by the cut distance $\delta_{\square,m}$ for different distances $d_m$, where the sub-script m is used to distinguish different distances. Its proof is given below. Recall from Theorem 3.17 that $d_{\square,m}$ must be smooth for $\delta_{\square,m}$ to be a distance.

**LEMMA 5.3** (Comparison of topologies induced by $d_{\square,m}$ and $\delta_{\square,m}$). — Let $d_m$ and $d_{m'}$ be two distances on $M_{\le 1}(Z)$ such that $d_{m'}$ is uniformly continuous w.r.t. $d_m$ (in particular, $d_m$ induces a finer topology than $d_{m'}$ on $M_{\le 1}(Z)$). Then, we have the following properties.

(i) The distance $d_{\square,m'}$ is uniformly continuous w.r.t. $d_{\square,m}$ on $W_1$. In particular $d_{\square,m}$ induces a finer topology than $d_{\square,m'}$ on $W_1$.

(ii) If the distance $d_{\square,m}$ on $W_1$ is smooth, then the distance $d_{\square,m'}$ is also smooth and $\delta_{\square,m'}$ is uniformly continuous w.r.t. $\delta_{\square,m}$. In particular, $\delta_{\square,m}$ induces a finer topology than $\delta_{\square,m'}$ on $\tilde{W}_1$.
(iii) If the distance $d_{\square,m}$ on $W_1$ is weakly regular, then the distance $d_{\square,m'}$ is also weakly regular.

(iv) Assume that the distance $d_{m'}$ induces the weak topology on $M_{\le 1}(\mathbf{Z})$, and that the distance $d_{\square,m}$ is smooth and weakly regular. In particular, the distance $d_m$ also induces the weak topology on $M_{\le 1}(\mathbf{Z})$. Then, the distances $\delta_{\square,m}$ and $\delta_{\square,m'}$ induce the same topology on $\tilde{W}_1$.

We will see some application of Lemma 5.3 in Corollary 5.6 below.

**Remark 5.4 (Extension to $W_\pm$ for topology comparisons).** — In Lemma 5.3 (i)-(iii), one can replace $W_1$ and $\tilde{W}_1$ by $W_+$ and $\tilde{W}_+$ or by $W_\pm$ and $\tilde{W}_\pm$ as soon as the distances $d_m$ and $d_{m'}$ are defined on $M_+(\mathbf{Z})$ or $M_-(\mathbf{Z})$; in this case comparisons of topologies only apply on uniformly bounded subsets. In Lemma 5.3 (iv), one can replace $\tilde{W}_1$ by $\tilde{W}_M$ with a bounded subset $M \subset M_+(\mathbf{Z})$ as soon as the distances $d_m$ and $d_{m'}$ are defined on $M_+(\mathbf{Z})$.

**Proof of Lemma 5.3.** — We prove Point (i). Let $\varepsilon > 0$. As $d_{m'}$ is uniformly continuous w.r.t. $d_m$, there exists $\eta > 0$ such that for every $\mu, \nu \in M_{\le 1}(\mathbf{Z})$, if $d_m(\mu, \nu) < \eta$, then $d_{m'}(\mu, \nu) < \varepsilon$. Let $U, W \in W_1$ such that $d_{\square,m}(U, W) < \eta$. Then, for every subsets $S, T \subset [0, 1]$, we have:

$$d_{m'}(U(S \times T; \cdot), W(S \times T; \cdot)) < \varepsilon.$$

Thus, $d_{\square,m'}(U, W) \le \varepsilon$. Hence, $d_{\square,m'}$ is uniformly continuous w.r.t. $d_{\square,m}$.

We prove Point (ii). Assume that $d_{\square,m}$ is smooth. Let $(W_n)_{n \in \mathbb{N}}$ and $W$ be probability-graphons such that $W_n(x, y; \cdot)$ weakly converges to $W(x, y; \cdot)$ for almost every $x, y \in [0, 1]$. Since the cut distance $d_{\square,m}$ is smooth, we get that $d_{\square,m}(W_n, W) \to 0$. As $d_{\square,m'}$ is uniformly continuous (and thus also continuous) w.r.t. $d_{\square,m}$, we have that $d_{\square,m'}(W_n, W) \to 0$. Hence, $d_{\square,m'}$ is smooth.

Furthermore, let $\varepsilon > 0$. Let $\eta > 0$ be such that for every $\mu, \nu \in M_{\le 1}(\mathbf{Z})$, $d_m(\mu, \nu) < \eta$ implies $d_{m'}(\mu, \nu) < \varepsilon$. For every $U, W \in W_1$ such that $\delta_{\square,m}(U, W) < \eta$, there exists $\varphi \in S_{[0,1]}$ such that $d_{\square,m}(U, W^\varphi) < \eta$, which implies that $d_{\square,m'}(U, W^\varphi) < \varepsilon$, which then implies that $\delta_{\square,m'}(U, W) < \varepsilon$. That is, $\delta_{\square,m'}$ is uniformly continuous w.r.t. $\delta_{\square,m}$.

We prove Point (iii). Assume that $d_{\square,m}$ is weakly regular. Let $K \subset W_1$ be tight. Let $\varepsilon > 0$. As $d_{\square,m'}$ is uniformly continuous w.r.t. $d_{\square,m}$, there exists $\eta > 0$ such that for every $U, W \in W_1$, if $d_{\square,m}(U, W) < \eta$, then $d_{\square,m'}(U, W) < \varepsilon$. Since $d_{\square,m}$ is weakly regular, there exists $m \in \mathbb{N}^*$, such that for every probability-graphon $W \in K$, and for every finite partition $Q$
of $[0, 1]$, there exists a finite partition $\mathcal{P}$ of $[0, 1]$ that refines $\mathcal{Q}$ and such that
$|\mathcal{P}| \le m|\mathcal{Q}|$ and $d_{\square,m}(W, W_{\mathcal{P}}) < \eta$; and thus we also have $d_{\square,m'}(W, W_{\mathcal{P}}) < \varepsilon$. Hence, $d_{\square,m'}$ is weakly regular.

We prove Point (iv). Assume that $d_{m'}$ induces the weak topology on $M_{\le 1}(Z)$ and that $d_{\square,m}$ is smooth and weakly regular. In particular, the topology induced by $d_m$ if finer than the topology induced by $d_{m'}$, i.e. finer than the weak topology. As $d_{\square,m}$ is smooth, by Lemma 3.12, $d_m$ is continuous w.r.t. the weak topology (i.e. the weak topology if finer than the topology induced by $d_m$), and thus $d_m$ induces the weak topology on $M_{\le 1}(Z)$. By Points (ii) and (iii), we get that $d_{\square,m'}$ is also smooth and weakly regular. By Point (ii), the distance $\delta_{\square,m}$ induces a finer topology than $\delta_{\square,m'}$ on $\tilde{W}_1$.

We now prove that the topology of $\delta_{\square,m'}$ is finer than the topology of $\delta_{\square,m}$. Let $(W_n)_{n \in \mathbb{N}}$ and $W$ be probability-graphons in $\tilde{W}_1$, such that $W_n$ converges to $W$ for $\delta_{\square,m'}$. By Proposition 5.2 (i), we deduce that the sequence $(W_n)_{n \in \mathbb{N}}$ is tight. As $d_{\square,m}$ is smooth and weakly regular, Theorem 5.1 gives that every subsequence $(W_{n_k})_{k \in \mathbb{N}}$ of the sequence $(W_n)_{n \in \mathbb{N}}$ has a further subsequence $(W_{n'_k})_{k \in \mathbb{N}}$ that converges for $\delta_{\square,m}$ to a limit, say $U \in \tilde{W}_1$. Since $\delta_{\square,m}$ is finer than $\delta_{\square,m'}$, we deduce that $(W_{n'_k})_{k \in \mathbb{N}}$ converges also to $U$ for $\delta_{\square,m'}$; but, as a subsequence, it also converges to $W$ for $\delta_{\square,m'}$. As $\delta_{\square,m'}$ is a distance on $W_1$ thanks to Theorem 3.17, we get $U = W$. Hence, every subsequence of $(W_n)_{n \in \mathbb{N}}$ has a further subsequence that converges to $W$ for $\delta_{\square,m}$, therefore the whole sequence itself converges to $W$ for $\delta_{\square,m}$. Consequently, $\delta_{\square,m'}$ is finer than $\delta_{\square,m}$, and thus those two distances induce the same topology on $\tilde{W}_1$. $\square$

The following theorem states that under appropriate assumptions, the topology induced by $\delta_{\square,m}$ does not depend on $d_m$. We prove this theorem in Section 8. Recall that under suitable conditions satisfied in the next theorem, the quotient space $\tilde{W}_1$ does not depend on the choice of the distance $d_m$, see Theorem 3.17.

**THEOREM 5.5 (Equivalence of topologies induced by $\delta_{\square,m}$ on $\tilde{W}_1$).** —
The topology on the space of probability-graphons $\tilde{W}_1$ induced by the distance $\delta_{\square,m}$ does not depend on the choice of the distance $d_m$ on $M_{\le 1}(Z)$, as long as $d_m$ induces the weak topology on $M_{\le 1}(Z)$ and the cut distance $d_{\square,m}$ on $W_1$ is (invariant) smooth, weakly regular and regular w.r.t. the stepping operator.

Recall from Proposition 4.13 that when the distance $d_m$ is quasi-convex and continuous w.r.t. the weak topology on $M_+(Z)$ or $M_-(Z)$, then the
cut distance $d_{\square,m}$ is invariant, smooth, weakly regular and regular w.r.t. the stepping operator. This is in particular the case of $d_{LP}$, $\| \cdot \|_{FM}$, $\| \cdot \|_{KR}$ and $\| \cdot \|_{FM}$.

The next corollary is an immediate consequence of Lemma 3.22, Corollary 4.14, Lemma 5.3 and Theorem 5.5. This corollary gathers results comparing the topology induced by the cut distances associated with the distances introduced in Section 3.8. It is yet unclear if the distances $d_{\square,F}$ induce the same topology on the space of labeled probability-graphons $W_1$ as the one induced by $d_{\square,LP}$, $d_{\square,FM}$ or $d_{\square,KR}$.

**COROLLARY 5.6** (Topological equivalence of the cut distances associated to $d_{LP}$, $\| \cdot \|_{FM}$, $\| \cdot \|_{KR}$ and $\| \cdot \|_{F}$). — The cut distances $d_{\square,LP}$ on $W_{+}$ and $d_{\square,KR}$, $d_{\square,FM}$ and $d_{\square,F}$ on $W_{\pm}$ are invariant, smooth, weakly regular and regular w.r.t. the stepping operator. Moreover, we have the following comparison between the distances introduced in Section 3.8.

(i) The cut norms $\| \cdot \|_{FM}$ and $\| \cdot \|_{KR}$ (resp. the cut distances $\delta_{\square,FM}$ and $\delta_{\square,KR}$) are metrically equivalent on $W_{\pm}$ (resp. $\tilde{W}_{\pm}$).

(ii) The cut distances $\delta_{\square,FM}$, $\delta_{\square,KR}$ and $\delta_{\square,LP}$ (resp. $d_{\square,FM}$, $d_{\square,KR}$ and $d_{\square,LP}$) are uniformly continuous w.r.t. one another, and thus induce the same topology on $\tilde{W}_1$ (resp. $W_1$) and on every uniformly bounded subset of $\tilde{W}_+$ (resp. $W_+$).

(iii) The cut distances $\delta_{\square,FM}$, $\delta_{\square,KR}$, $\delta_{\square,LP}$ and $\delta_{\square,F}$, for every choice of the convergence determining sequence $\mathcal{F}$, induce the same topology on $\tilde{W}_1$.

*Proof*. — The first part of the corollary is a re-statement of Corollary 4.14. Point (i) is an immediate consequence of (3.9).

We now prove Point (ii). Thanks to (3.9) and Point (i), it is enough to consider only the Lévy–Prokhorov and the Kantorovitch–Rubinshtein distances. As $d_{LP}$ is uniformly continuous w.r.t. $d_{KR}$ (see Lemma 3.22), applying Lemma 5.3 (recall Corollary 4.14) with Remark 5.4 in mind, we get that $\delta_{\square,LP}$ (resp. $d_{\square,LP}$) is uniformly continuous w.r.t. $\delta_{\square,KR}$ (resp. $d_{\square,KR}$) on every uniformly bounded subset of $\tilde{W}_+$ (resp. $W_+$). As $d_{KR}$ is also uniformly continuous w.r.t. $d_{LP}$ (see Lemma 3.22), applying again Lemma 5.3, we have that $\delta_{\square,KR}$ (resp. $d_{\square,KR}$) is uniformly continuous w.r.t. $\delta_{\square,LP}$ (resp. $d_{\square,LP}$) on every uniformly bounded subset of $\tilde{W}_+$ (resp. $W_+$).

Point (iii) is an immediate consequence of Corollary 4.14 and Theorem 5.5, together with Point (ii). □

**Remark 5.7** (Extension to uniformly bounded subsets of $\tilde{W}_+$). — In Theorem 5.5 and also in Corollary 5.6 (iii), one can replace $\tilde{W}_1$ by $\tilde{W}_M$ with
a bounded subset $\mathcal{M} \subset \mathcal{M}_+(\mathbf{Z})$ as soon as the distance $d_m$ is defined on $\mathcal{M}_+(\mathbf{Z})$. (One has in mind the case $\mathcal{M} = \mathcal{M}_{\le 1}(\mathbf{Z})$.) This can be seen by an easy modification in the proof of Theorem 5.5. Alternatively, this can be seen using scaling to reduce the case of general $\mathcal{M}$ to the case of $\mathcal{M}_{\le 1}(\mathbf{Z})$, and then adding a cemetery point (for missing mass of measures) to $\mathbf{Z}$ to further reduce to the case of $\mathcal{M}_1(\mathbf{Z})$.

### 5.3. Completeness

Let $d_m$ be a distance on $\mathcal{M}_{\le 1}(\mathbf{Z})$ or $\mathcal{M}_+(\mathbf{Z})$. We shall consider a slight modification of the cut distances $d_{\square,m}$ and $\delta_{\square,m}$ to achieve completeness. Recall the measure $M_W \in \mathcal{M}_+(\mathbf{Z})$ defined by (4.1) associated to $W \in \mathcal{W}_+$.

**DEFINITION 5.8** (The cut distances $d_{\square,m}^c$ and $\delta_{\square,m}^c$). — Let $d_m$ and $d^c$ be two distances on $\mathcal{M}_\epsilon(\mathbf{Z})$ with $\epsilon \in \{\le 1, +\}$. We define the cut distance $d_{\square,m}^c$ on the space of $\mathcal{M}_\epsilon(\mathbf{Z})$-valued kernels $\tilde{W}_\epsilon$ as:

$$d_{\square,m}^c(U, W) = d_{\square,m}(U, W) + d^c(M_U, M_W),$$

and the cut (pseudo-)distance $\delta_{\square,m}^c$ on the space of unlabeled $\mathcal{M}_\epsilon(\mathbf{Z})$-valued kernels $\tilde{W}_\epsilon$ as:

$$\delta_{\square,m}^c(U, W) = \inf_{\varphi \in S_{[0,1]}} d_{\square,m}^c(U, W^\varphi) = \delta_{\square,m}(U, W) + d^c(M_U, M_W).$$

Notice that by Lemma 3.11 and the definition of $M_W$, the distance $d_{\square,m}^c$ is invariant.

**LEMMA 5.9** (Topological equivalence of $\delta_{\square,m}$ and $\delta_{\square,m}^c$). — Let $d_m$ and $d^c$ be two distances on $\mathcal{M}_\epsilon(\mathbf{Z})$, with $\epsilon \in \{\le 1, +\}$, such that $d^c$ is continuous w.r.t. $d_m$ and that $d_{\square,m}$ is (invariant and) smooth on $\tilde{W}_\epsilon$. Then, the cut distance $d_{\square,m}^c$ is invariant and smooth and $\delta_{\square,m}^c$ is a distance on $\tilde{W}_\epsilon$. Moreover, the distances $d_{\square,m}$ and $d_{\square,m}^c$ (resp. $\delta_{\square,m}$ and $\delta_{\square,m}^c$) induce the same topology on the space $\tilde{W}_\epsilon$ (resp. $\tilde{W}_\epsilon$).

*Proof.* — Let $(W_n)_{n \in \mathbb{N}}$ and $W$ be elements of $\mathcal{W}_{\le 1}$ such that $(W_n(x, y; \cdot))_{n \in \mathbb{N}}$ weakly converges to $W(x, y; \cdot)$ for almost every $x, y \in [0, 1]$. Since the distance $d_{\square,m}$ is smooth, we have that $\lim_{n \to \infty} d_{\square,m}(W_n, W) = 0$. Using Lemma 4.9 on the continuity of the map $W \mapsto M_W$ and that $d^c$ is continuous w.r.t. $d_m$, we obtain that $\lim_{n \to \infty} d_{\square,m}^c(W_n, W) = 0$. This gives that the distance $d_{\square,m}^c$ is smooth. Since we have already seen that $d_{\square,m}^c$ is invariant, we deduce from Theorem 3.17 that $\delta_{\square,m}^c$ is a distance on $\tilde{W}_1$.
We now prove that the two distances $d_{\square,m}$ and $\delta_{\square,m}^c$ induce the same topology (which implies that this is also true for $\delta_{\square,m}$ and $\delta_{\square,m}^c$). As $d_{\square,m} \le d_{\square,m}^c$, convergence for $d_{\square,m}^c$ implies convergence for $d_{\square,m}$. Conversely, let $(W_n)_{n \in \mathbb{N}}$ be a sequence in $W_\epsilon$ that converges for $d_{\square,m}$ to a limit, say $W \in W_\epsilon$. Using again Lemma 4.9 and the continuity of $d^c$ w.r.t. $d_m$, we obtain that $\lim_{n \to \infty} d^c(M_{W_n}, M_W) = 0$. This clearly implies that the sequence $(W_n)_{n \in \mathbb{N}}$ converges to $W$ for $d_{\square,m}^c$. Then, the two distances have the same convergent sequences and thus induce the same topology (see Remark 2.1). $\square$

Recall $\mathbf{Z}$ is a Polish space. We already proved in Proposition 4.6 that the space $(\tilde{W}_1, \delta_{\square,m})$ is separable; and we now investigate completeness of this space.

**THEOREM 5.10** $(\tilde{W}_1$ is a Polish space). — Let $d_m$ and $d^c$ be two distances on $M_{\le 1}(\mathbf{Z})$ such that $d^c$ induces the weak topology on $M_{\le 1}(\mathbf{Z})$, $d^c$ is complete and continuous w.r.t. $d_m$, and $d_{\square,m}$ is (invariant) smooth and weakly regular on $W_1$. Then, the space $(\tilde{W}_1, \delta_{\square,m}^c)$ is a Polish metric space.

Note that the assumptions in Theorem 5.10 imply that $d_m$ also induces the weak topology on $M_{\le 1}(\mathbf{Z})$. Indeed, as $d^c$ is continuous w.r.t. $d_m$, the topology induced by $d_m$ if finer than the topology induced by $d^c$, i.e. finer than the weak topology. As $d_{\square,m}$ is smooth, by Lemma 3.12, $d_m$ is continuous w.r.t. the weak topology (i.e. the weak topology if finer than the topology induced by $d_m$), and thus $d_m$ induces the weak topology on $M_{\le 1}(\mathbf{Z})$.

Also note that Theorem 5.10 can easily be extended to $W_{\le 1}$ or the space of unlabeled $M$-valued kernels $\tilde{W}_M$ when $M$ is a bounded convex closed subset of $M_+(\mathbf{Z})$.

*Proof.* — From Lemma 5.9, we have that $\delta_{\square,m}^c$ is a distance on $\tilde{W}_1$ which induces the same topology as $\delta_{\square,m}$, and from Proposition 4.6, we have that $(\tilde{W}_1, \delta_{\square,m})$, and thus $(\tilde{W}_1, \delta_{\square,m}^c)$, is separable. To get that this latter space is Polish, we are left to prove that the distance $\delta_{\square,m}^c$ is complete.

Let $(W_n)_{n \in \mathbb{N}}$ be a sequence of probability-graphons that is Cauchy for $\delta_{\square,m}^c$. By definition of the cut distance $\delta_{\square,m}^c$, the sequence of probability measures $(M_{W_n})_{n \in \mathbb{N}}$ is Cauchy in $M_1(\mathbf{Z})$ for the complete distance $d^c$. Thus, the sequence $(M_{W_n})_{n \in \mathbb{N}}$ is weakly convergent as $d^c$ induces the weak topology, which implies that it is tight (see Lemma 2.8). Hence, by definition, the sequence of probability-graphons $(W_n)_{n \in \mathbb{N}}$ is tight. By Theorem 5.1 (i), there exists a subsequence $(W_{n_k})_{k \in \mathbb{N}}$ that converges for $\delta_{\square,m}$ to a limit, say $W \in \tilde{W}_1$. This subsequence also converges for $\delta_{\square,m}^c$ to $W$ as $\delta_{\square,m}$ and $\delta_{\square,m}^c$ induce the same topology. Finally, because the sequence
$(W_n)_{n \in \mathbb{N}}$ is Cauchy for $\delta_{\square,m}^c$ and has a subsequence converging to $W$ for $\delta_{\square,m}^c$, the whole sequence must also converge to $W$ for $\delta_{\square,m}^c$. Consequently, the distance $\delta_{\square,m}^c$ is complete. $\square$

The following lemma shows that every probability measure can be represented as a constant probability-graphon.

**LEMMA 5.11** ($M_1(\mathbf{Z})$ seen as a closed subset of $W_1$). — Let $d_m$ be a distance on $M_{\le 1}(\mathbf{Z})$ such that $d_{\square,m}$ is (invariant and) smooth on $W_1$. Then, the map $\mu \mapsto W_\mu \equiv \mu$ is an injection from $(M_1(\mathbf{Z}), d_m)$ to $(\tilde{W}_1, \delta_{\square,m})$ with a closed range and continuous inverse.

*Proof*. — For any $\mu \in M_1(\mathbf{Z})$ consider the constant probability-graphon $W_\mu \equiv \mu$, and notice that $M_{W_\mu} = \mu$, that $W_\mu(S \times T; \cdot) = \lambda(S)\lambda(T)\mu$ for all measurable $S, T \subset [0, 1]$, and that $W_\mu^\varphi = W_\mu$ for any measure-preserving map $\varphi$. This readily implies that for $\mu \in M_1(\mathbf{Z})$ and $W \in W_1$:

$$ (5.1) \qquad \begin{aligned} \delta_{\square,m}(W_\mu, W) &= d_{\square,m}(W_\mu, W) \\ &= \sup_{S,T \subset [0,1]} d_m(\lambda(S)\lambda(T)\mu, W(S \times T; \cdot)) \\ &\ge d_m(\mu, M_W). \end{aligned} $$

In particular, taking $W = W_\nu$ for $\nu \in M_1(\mathbf{Z})$ we get that $\delta_{\square,m}(W_\mu, W_\nu) \ge d_m(\mu, \nu)$. This implies that the map $\mathcal{I}: \mu \mapsto W_\mu \equiv \mu$ is an injection, and its inverse, given by the map $W_\mu \mapsto \mu$, is 1-Lipschitz.

Let $(\mu_n)_{n \in \mathbb{N}}$ be a sequence in $M_1(\mathbf{Z})$ such that the sequence $(W_{\mu_n})_{n \in \mathbb{N}}$ converges for $\delta_{\square,m}$ to a limit, say $W$. We deduce from (5.1) that $(\mu_n)_{n \in \mathbb{N}}$ converges for $d_m$ to $\mu = M_W$ and that for all measurable $S, T \subset [0, 1]$, $(\lambda(S)\lambda(T)\mu_n)_{n \in \mathbb{N}}$ converges for $d_m$ to $W(S \times T; \cdot)$. This implies that $W(S \times T; \cdot) = \lambda(S)\lambda(T)\mu(\cdot)$ for all measurable $S, T \subset [0, 1]$, that is, $W = W_\mu$. This implies that the image by $\mathcal{I}$ of any closed subset of $M_1(\mathbf{Z})$ is a closed subset of $W_1$, and thus the range of $\mathcal{I}$ is closed. $\square$

**Remark 5.12** (Extension to isometric representation of $M_1(\mathbf{Z})$). — If the distance $d_m$, in addition to the hypothesis of Lemma 5.11, is sub-homogeneous, that is, for all $\mu, \nu \in M_1(\mathbf{Z})$ we have $d_m(\mu, \nu) = \sup_{r \in [0,1]} d_m(r\mu, rv)$ (which is the case if $d_m$ is quasi-convex), then we deduce from (5.1) that the map $\mu \mapsto W_\mu \equiv \mu$ is isometric from $(M_1(\mathbf{Z}), d_m)$ to $(\tilde{W}_1, \delta_{\square,m})$.

We now state a characterization of compactness and completeness for the space of probability-graphons. Recall $\mathbf{Z}$ is a Polish space.
COROLLARY 5.13 (Characterization of compactness and completeness for $\tilde{W}_1$). — Let $d_m$ be a distance on $\mathcal{M}_{\le 1}(\mathbf{Z})$, which induces the weak topology on $\mathcal{M}_{\le 1}(\mathbf{Z})$, and such that $d_{\square,m}$ is (invariant) smooth and weakly regular on $W_1$. We have the following properties.

(i) $\mathbf{Z}$ is compact $\iff (\mathcal{M}_{\le 1}(\mathbf{Z}), d_m)$ is compact $\iff (\tilde{W}_1, \delta_{\square,m})$ is compact.

(ii) If $(\mathcal{M}_{\le 1}(\mathbf{Z}), d_m)$ is complete then $(\tilde{W}_1, \delta_{\square,m})$ is complete.

(iii) Assume furthermore that $d_m$ is sub-homogeneous (see Remark 5.12). If $(\tilde{W}_1, \delta_{\square,m})$ is complete, then $(\mathcal{M}_1(\mathbf{Z}), d_m)$ is complete.

*Proof*. — We prove Point (i). From Remark 2.7, we already know that $\mathbf{Z}$ is compact if and only if $\mathcal{M}_{\le 1}(\mathbf{Z})$ is weakly compact, i.e. compact for $d_m$ as $d_m$ induces the weak topology on $\mathcal{M}_{\le 1}(\mathbf{Z})$.

Now, assume that $(\mathcal{M}_{\le 1}(\mathbf{Z}), d_m)$ is compact. Applying Theorem 5.1 (iii), we get that the space $(\tilde{W}_1, \delta_{\square,m})$ is also compact.

Conversely, assume that $(\tilde{W}_1, \delta_{\square,m})$ is compact. By Lemma 4.9, the mapping $W \mapsto M_W$ is continuous from $(\tilde{W}_1, \delta_{\square,m})$ to $(\mathcal{M}_1(\mathbf{Z}), d_m)$, and as $(\tilde{W}_1, \delta_{\square,m})$ is compact its image through this mapping is also compact. To conclude, it is enough to check that this mapping is surjective. But this is clear as the image of the constant probability-graphon $W_\mu \equiv \mu$ is $M_{W_\mu} = \mu$. Hence, $(\mathcal{M}_1(\mathbf{Z}), d_m)$ (and thus $(\mathcal{M}_{\le 1}(\mathbf{Z}), d_m)$) is compact.

We prove Point (ii). Assume that $(\mathcal{M}_{\le 1}(\mathbf{Z}), d_m)$ is complete. Thus, we can choose $d^c = d_m$ in Definition 5.8, and apply Theorem 5.10 to get that $(\tilde{W}_1, \delta_{\square,m}^c)$ is complete. As $d^c = d_m$, we have $\delta_{\square,m} \le \delta_{\square,m}^c \le 2\delta_{\square,m}$. Hence, $(\tilde{W}_1, \delta_{\square,m}^c)$ is also complete.

We prove Point (iii). Assume that $(\tilde{W}_1, \delta_{\square,m})$ is complete. Let $(\mu_n)_{n \in \mathbb{N}}$ be a Cauchy sequence of probability measures in $(\mathcal{M}_1(\mathbf{Z}), d_m)$. By Remark 5.12, the sequence of constant probability-graphons $(W_{\mu_n})_{n \in \mathbb{N}}$ is also Cauchy for $\delta_{\square,m}$. As $(\tilde{W}_1, \delta_{\square,m})$ is complete, there exists a probability-graphon $W \in \tilde{W}_1$ such that $(W_{\mu_n})_{n \in \mathbb{N}}$ converges to $W$ for the cut distance $\delta_{\square,m}$. Thanks to Lemma 5.11, $W$ is constant equal to some $\mu \in \mathcal{M}_1(\mathbf{Z})$, and $(\mu_n)_{n \in \mathbb{N}}$ converges to $\mu$ for $d_m$. Hence, $(\mathcal{M}_1(\mathbf{Z}), d_m)$ is complete. $\square$

## 6. Sampling from probability-graphons

Measure-valued graphons allow to define models for generating random weighted graphs that are more general than the models based on real-valued
graphons. We prove that the weighted graphs sampled from probability-graphons are close to their original model for the cut distance $\delta_{\square, \mathcal{F}}$, where $\mathcal{F} = (f_k)_{k \in \mathbb{N}}$ (with $f_0 = 1$) is a convergence determining sequence. In doing so, we prove analogues for probability-graphons of the first and second sampling lemmas for real-valued kernels and graphons (see [16] or [46, Sections 10.3 and 10.4]).

It would have been more natural to work in Sections 6 and 7 with the Kantorovitch–Rubinshtein norm or the Fortet–Mourier norm that both treats all test functions in a uniform manner. Unfortunately, the supremum in the definition of both of these norms does not behave well regarding the probabilities and expectations of graphs sampled from probability-graphons. We need in our proofs (and in particular that of the First Sampling Lemma 6.7 below) to consider simultaneously only a finite number of test functions in order to control the probability of failure for our stochastic bounds. The proof of the First Sampling Lemma 6.7 is based on applying the first sampling lemma for real-valued kernels to several one dimensional-valued projections of measure-valued kernels. The proof of the Second Sampling Lemma 6.12 is similar to the one for real-valued kernels and graphons.

## 6.1. $\mathcal{M}_1(\mathbb{Z})$-Graphs and weighted graphs

A graph $G = (V, E)$ is composed of a finite set of vertices $V(G) = V$, and a set of edges $E(G) = E$ which is a subset of $V \times V$ avoiding the diagonal. When its set of edges $E(G)$ is symmetric, we say that $G$ is *symmetric* or *non-oriented*. We denote by $v(G) = |V(G)|$ the number of vertices of this graph, and by $e(G) = |E(G)|$ its number of edges.

**DEFINITION 6.1 (X-graphs).** — Let $\mathcal{X}$ be a non-empty set. A $\mathcal{X}$-graph is a triplet $G = (V, E, \Phi)$ where $(V, E)$ is a graph and $\Phi : E \to \mathcal{X}$ is a map that associates a decoration $x = \Phi(e) \in \mathcal{X}$ to each edge $e \in E$. When $\mathcal{X} = \mathbb{Z}$, we say that $G$ is a weighted graph.

Furthermore, the graph $G$ is said to be symmetric if $(V, E)$ is a symmetric graph and if $\Phi$ is a symmetric function, i.e. for every edge $(x, y) \in E$, we have $(y, x) \in E$ and $\Phi(x, y) = \Phi(y, x)$.

**Remark 6.2 ($\mathcal{M}_1(\mathbb{Z})$-Graphs as probability-graphons).** — Any labeled $\mathcal{M}_1(\mathbb{Z})$-graph $G$ can be naturally represented as an $\mathcal{M}_1(\mathbb{Z})$-valued graphon, which we denote by $W_G$, in the following way. Let $G = (V, E, M)$ be a $\mathcal{M}_1(\mathbb{Z})$-graph, with $v(G) = n \in \mathbb{N}^*$. Denote by $V = [n] = \{1, \dots, n\}$ the
vertices of G. Consider intervals of length 1/n: for 1 ≤ i ≤ n, let $J_i = ((i - 1)/n, i/n]$. We then define the $M_1(\mathbf{Z})$-valued graphon stepfunction $W_G$ associated with the $M_1(\mathbf{Z})$-graph G by:

$$ \forall (i,j) \in E, \quad \forall (x,y) \in J_i \times J_j, \quad W_G(x,y; dz) = \Phi(i,j)(dz); $$

and $W_G(x, y; dz)$ equals the Dirac mass at $\partial$ otherwise, where $\partial$ is an element of $\mathbf{Z}$ used as a cemetery point for missing edges in graphs.

In this section, we investigate weighted graphs sampled from probability-graphons. Hence, using the cemetery point argument in the remark above, we only consider complete graphs for the rest of this section.

Let $d_m$ be a distance on $M_{\le 1}(\mathbf{Z})$. If G and H have the same vertex-set, the cut distance between them is defined as the cut distance between their associated graphons:

$$ d_{\square,m}(G, H) = d_{\square,m}(W_G, W_H). $$

When G and H do not have the same vertex-sets, as the numbering of the vertices in Remark 6.2 is arbitrary, we must consider the unlabeled cut distance between them defined as the cut distance between their associated graphons:

$$ \delta_{\square,m}(G, H) = \delta_{\square,m}(W_G, W_H). $$

Recall that when the distance $d_m$ derives from a norm $N_m$ on $M_{\pm}(\mathbf{Z})$, Lemma 3.19 applies, and the cut distance $d_{\square,m}(G, H)$ can be rewritten as a combinatorial optimization over whole steps.

**Remark 6.3 (Weighted graphs as $M_1(\mathbf{Z})$-graphs).** — We will sometimes need to interpret a weighted graph G as a $M_1(\mathbf{Z})$-graph where a weight $x$ on an edge is replaced by $\delta_x$ the Dirac mass located at $x$.

**Notation 6.4 (The real-weighted graph $G[f]$).** — For a $M_1(\mathbf{Z})$-graph (resp. weighted graph) G and a function $f \in C_b(\mathbf{Z})$, we denote by $G[f]$ the real-weighted graph with the same vertex set and edge set as G, and where the edge $(i, j)$ has weight $\Phi_{G[f]}(i, j) = \Phi_G(i, j; f) = \int_{\mathbf{Z}} f(z)\Phi_G(i, j; dz)$ (resp. $\Phi_{G[f]}(i, j) = f(\Phi_G(i, j))$), where $\Phi_G$ is the decoration of the $M_1(\mathbf{Z})$-graph G. This notation is consistent when one identifies the decoration $z \in \mathbf{Z}$ for a $\mathbf{Z}$-graph with the decoration given by the Dirac mass at $z$ for the corresponding $M_1(\mathbf{Z})$-graph. It is also consistent with the notation in (3.7) for probability graphons.
## 6.2. W-random graphs

Let $W$ be a probability-graphon, and $x = (x_1, \dots, x_n)$, $n \in \mathbb{N}^*$, be a sequence of points from $[0, 1]$. We define the $M_1(\mathbf{Z})$-graph $\mathbb{H}(x, W)$ as the complete graph whose vertex set is $[n] = \{1, \dots, n\}$, and with each edge $(i, j)$ decorated by the probability measure $W(x_i, x_j; dz)$.

Let $H$ be any $M_1(\mathbf{Z})$-graph. We can define from $H$ a random weighted (directed) graph $\mathbb{G}(H)$ whose vertex set $V(H)$ and edge set $E(H)$ are the same as $H$, and with each edge $(i, j)$ having a random weight $\beta_{i,j}$ distributed according to the probability distribution decorating the edge $(i, j)$ in $H$, all the weights being independent from each other. For the special case where $H = \mathbb{H}(x, W)$, we simply note $\mathbb{G}(x, W) = \mathbb{G}(\mathbb{H}(x, W))$.

An important special case is when the sequence $X$ is chosen at random: $X = (X_i)_{1 \le i \le n}$ where the $X_i$ are independent and uniformly distributed on $[0, 1]$. For this special case, we simply note $\mathbb{H}(n, W) = \mathbb{H}(X, W)$ and $\mathbb{G}(n, W) = \mathbb{G}(X, W)$, that are conditionally on $X = x$, distributed respectively as $\mathbb{H}(x, W)$ and $\mathbb{G}(x, W)$. The random graphs $\mathbb{H}(n, W)$ and $\mathbb{G}(n, W)$ are called W-random graphs.

**Remark 6.5 (The case of symmetric graphons).** — In the special case where $W$ is a symmetric probability-graphon, the $M_1(\mathbf{Z})$-graph $\mathbb{H}(x, W)$ is also symmetric. From a symmetric $M_1(\mathbf{Z})$-graph $H$, the random weighted graph $\mathbb{G}(H)$ is not necessarily symmetric, but we can define a random symmetric weighted graph $\mathbb{G}^{\text{sym}}(H)$ whose vertex set $V(H)$ and $E(H)$ are the same as $H$, and with independent weights $\beta_{i,j} = \beta_{j,i}$ on each edge $(i, j) = (j, i)$ distributed according to $\Phi_H(i, j; \cdot)$. For $H = \mathbb{H}(x, W)$ we simply note $\mathbb{G}^{\text{sym}}(x, W)$ and $\mathbb{G}^{\text{sym}}(n, W)$.

For a weighted graph $G$, and for $1 \le k \le v(G)$, we can define the random weighted graph $\mathbb{G}(k, G)$ as being the sub-graph of $G$ induced by a uniform random subset of $k$ distinct vertices from $G$. Then, upper bounding by the probability that a uniformly-chosen map $[k] \to V(G)$ is non-injective, we get the following bound on the total variation distance between the graphs obtained from $G$ and its associated graphon $W_G$:

$$d_{\text{var}}(\mathbb{G}(k, G), \mathbb{G}(k, W_G)) \le \binom{k}{2} \frac{1}{v(G)},$$

where $d_{\text{var}}$ is the total variation distance between probability measures.
6.3. Estimation of the distance by sampling

6.3.1. The first sampling lemma

In this subsection, we link sampling from graphons with the cut distance.
This result is the equivalent of Lemma 10.6 in [46]. The main consequence of
the following lemma is that the cut distance $d_{\square, \mathcal{F}}$ between two probability-
graphons can be estimated by sampling.

Notation 6.6 (The random stepfunction $W_X$). — For a measure-valued kernel $W$ (resp. a real-valued kernel $w$) and a vector $X = (X_i)_{1\le i\le k}$ composed of $k$ independent random variables uniformly distributed over $[0, 1]$, we denote by $W_X = W_{\mathbb{H}(k,W)}$ (resp. $w_X$) the random measure-valued (resp. real-valued) stepfunction with $k$ steps of size $1/k$, and where the step $(i, j)$ has value $W(X_i, X_j; \cdot)$ (resp. $w(X_i, X_j)$).

LEMMA 6.7 (First Sampling Lemma). — Let $\mathcal{F}$ be a convergence determining sequence. Let $k \in \mathbb{N}^*$, and $U, W \in \mathcal{W}_1$ be two probability-graphons, and let $X$ be a random vector uniformly distributed over $[0, 1]^k$. Then with probability at least $1 - 4k^{1/4} e^{-\sqrt{k}/8}$, we have:

$$
\left\| U_X - W_X \|_{\square, \mathcal{F}} - \| U - W \|_{\square, \mathcal{F}} \right\| \le \frac{11}{k^{1/4}}.
$$

An immediate consequence of Lemma 6.7 is that the decorated graphs
with probability measures on their edges $\mathbb{H}(k, U)$ and $\mathbb{H}(k, W)$ can be cou-
pled in order that $d_{\square, \mathcal{F}}(\mathbb{H}(k, U), \mathbb{H}(k, W))$ is close to $d_{\square, \mathcal{F}}(U, W)$ with high
probability.

To prove the first sampling lemma, we first need to prove the following
lemma which states that the cut norm $\| \cdot \|_{\square, \mathcal{F}}$ can be approximated by
the maximum of the one-sided cut norm using a finite number of functions.
Recall from Remark 3.24 the definition of the one-sided version of the cut
norm $\| \cdot \|_{\square, \mathbb{R}}^+$.

LEMMA 6.8 (Approximation bound with $\| \cdot \|_{\square, \mathcal{F}}$ and $\| \cdot \|_{\square, \mathbb{R}}^+$). — Let $U, W \in \mathcal{W}_1$ and let $N \in \mathbb{N}$. For every $\varepsilon = (\varepsilon_n)_{1 \le n \le N} \in \{\pm 1\}^N$, define $g_{N,\varepsilon} = \sum_{n=1}^N 2^{-n} \varepsilon_n f_n$. Then, we have:

$$
\|U - W\|_{\square, \mathcal{F}} - 2^{-N} \le \max_{\varepsilon \in \{\pm 1\}^N} \|(U - W)[g_{N,\varepsilon}]\|_{\square, \mathbb{R}}^{+} \le \|U - W\|_{\square, \mathcal{F}}.
$$

Proof. — First remark that for $n \in \mathbb{N}$, $f_n$ takes values in $[0, 1]$, and thus $U[f_n] - W[f_n]$ takes values in $[-1, 1]$. Recall that $f_0 = 1$, and thus
$U[f_0] - W[f_0] \equiv 0$. Upper bounding integrals by 1 for indices $n > N$, we get:

$$ \|U - W\|_{\square, \mathcal{F}} \le \sup_{S, T \subset [0, 1]} \sum_{n=1}^{N} 2^{-n} \left| \int_{S \times T} (U - W)[f_n](x, y) \, dx dy \right| + 2^{-N}. $$

And adding the non-negative terms for $n > N$, we get:

$$ \sup_{S, T \subset [0, 1]} \sum_{n=1}^{N} 2^{-n} \left| \int_{S \times T} (U - W)[f_n](x, y) \, dx dy \right| \le \|U - W\|_{\square, \mathcal{F}}. $$

Using the same idea as in (3.12) and (3.13), we get:

$$ \sup_{S, T \subset [0, 1]} \sum_{n=1}^{N} 2^{-n} \left| \int_{S \times T} (U - W)[f_n](x, y) \, dx dy \right| = \max_{\epsilon \in \{\pm 1\}^N} \|(U - W)[g_{N,\epsilon}]\|_{\square, \mathbb{R}}^{+}, $$

which concludes the proof.

<figure><img src="image_3.png" /></figure>

**Proof of Lemma 6.7.** — Remark that for $f \in C_b(\mathbb{Z})$ and $W \in W_\pm$, we have $(W_X)[f] = (W[f])_X$, and we thus write $W[f]_X$ without any ambiguity.

Assume that $k \ge 2^4$ (otherwise the lower bound in the lemma is trivial). Set $N = \lceil \log_2(k^{1/4}) \rceil$, so that $2^{-1}k^{-1/4} < 2^{-N} \le k^{-1/4}$. Let $\epsilon \in \{\pm 1\}^N$. Remark that as the $f_n$ take values in $[0, 1]$, the real-valued kernels $(U - W)[f_n]$ take values in $[-1, 1]$, and thus the real-valued kernel $(U - W)[g_{N,\epsilon}]$ also take values in $[-1, 1]$. Applying [16, Theorem 4.6] to the real-valued kernel $(U - W)[g_{N,\epsilon}]$, we get with probability at least $1 - 2e^{-\sqrt{k}/8}$ that:

$$ (6.1) \quad \left| \|(U - W)[g_{N,\epsilon}]_X\|_{\square, \mathbb{R}}^{+} - \|(U - W)[g_{N,\epsilon}]\|_{\square, \mathbb{R}}^{+} \right| \le \frac{10}{k^{1/4}}, $$

where recall that $\| \cdot \|_{\square, \mathbb{R}}^+$ is the one-sided version of the cut norm for real-valued kernels defined in (3.11). Hence, with probability at least $1 - 2^{N+1} e^{-\sqrt{k}/8} \ge 1 - 4k^{1/4} e^{-\sqrt{k}/8}$, we have that the bounds in (6.1) holds for every $\epsilon \in \{\pm 1\}^N$ simultaneously; and when all of this holds, applying Lemma 6.8 to $U, W$ and to $U_X, W_X$, we get:

$$ \begin{aligned} \|U_X - W_X\|_{\square, \mathcal{F}} &\le \max_{\epsilon \in \{\pm 1\}^N} \|(U - W)[g_{N,\epsilon}]_X\|_{\square, \mathbb{R}}^+ + 2^{-N} \\ &\le \max_{\epsilon \in \{\pm 1\}^N} \|(U - W)[g_{N,\epsilon}]\|_{\square, \mathbb{R}}^+ + \frac{11}{k^{1/4}} \\ &\le \|U - W\|_{\square, \mathcal{F}} + \frac{11}{k^{1/4}}, \end{aligned} $$
and similarly:

$$
\begin{align*}
\|U - W\|_{\square, \mathcal{F}} &\le \max_{\varepsilon \in \{\pm 1\}^N} \|(U - W)[g_{N,\varepsilon}]\|_{\square, \mathbb{R}}^+ + 2^{-N} \\
&\le \max_{\varepsilon \in \{\pm 1\}^N} \|(U - W)[g_{N,\varepsilon}]_X\|_{\square, \mathbb{R}}^+ + \frac{11}{k^{1/4}} \\
&\le \|U_X - W_X\|_{\square, \mathcal{F}} + \frac{11}{k^{1/4}}.
\end{align*}
$$

This concludes the proof.

<figure><img src="image_4.png" /></figure>

6.3.2. Approximation with random weighted graphs

As a consequence of the First Sampling Lemma 6.7, we get that the cut
distance between the sampled graphs $\mathbb{H}(k, U)$ and $\mathbb{H}(k, W)$ (with the proper
coupling) is close to the cut distance between the probability-graphons $U$
and $W$. The following lemma states that if $k$ is large enough, then $\mathbb{G}(k, W)$
is close to $\mathbb{H}(k, W)$ in the cut distance $d_{\square, \mathcal{F}}$, and thus the cut distance
between the random weighted graphs $\mathbb{G}(k, U)$ and $\mathbb{G}(k, W)$ is also close to
$d_{\square, \mathcal{F}}(U, W)$.

Recall from Section 6.2 the definition of the random weighted graph $\mathbb{G}(H)$ when $H$ is an $\mathcal{M}_1(\mathbf{Z})$-graph. Following Remarks 6.3 and 6.2, we shall see the weighted graph $\mathbb{G}(H)$ as a $\mathcal{M}_1(\mathbf{Z})$-graph or even as a probability-graphon.

LEMMA 6.9 (Bound in probability for $d_{\square, \mathcal{F}}(\mathbb{G}(H), H)$). — For every $\mathcal{M}_1(\mathbf{Z})$-graph $H$ with $k$ vertices, and for every $\varepsilon \ge 10/\sqrt{k}$, we have:

$$
\mathbb{P} \left( d_{\square, \mathcal{F}}(\mathbb{G}(H), H) > 2\varepsilon \right) \le e^{-\varepsilon^2 k^2}.
$$

Remark 6.10 (Bound in expectation for $d_{\square, \mathcal{F}}(\mathbb{G}(H), H)$). — Recall that $d_{\square, \mathcal{F}}(\mathbb{G}(H), H) \le 1$. Applying Lemma 6.9 with $\varepsilon = 10/\sqrt{k}$, we get the following bound on the expectation of $d_{\square, \mathcal{F}}(\mathbb{G}(H), H)$:

$$
\mathbb{E}[d_{\square, \mathcal{F}}(\mathbb{G}(H), H)] \le \frac{20}{\sqrt{k}} + e^{-100k} < \frac{21}{\sqrt{k}}.
$$

Proof of Lemma 6.9. — Let $H$ and $\varepsilon$ be as in the lemma. Assume that
$\varepsilon \le 1/2$ (otherwise the probability to bound in the lemma is null). To
simplify the notations, denote by $G = \mathbb{G}(H)$ throughout this proof. Define
$N = [\log_2(\varepsilon^{-1})]$, so that $\sum_{n=N+1}^{\infty} 2^{-n} \le \varepsilon$. Upper bounding by 1 the
terms for $n > N$ in (3.14), we get for $U, W \in \mathcal{W}_1$:

$$
d_{\square, \mathcal{F}}(U, W) \le \sum_{n=1}^{N} 2^{-n} \|U[f_n] - W[f_n]\|_{\square, \mathbb{R}} + \varepsilon,
$$
where recall that $\| \cdot \|_{\square, \mathbb{R}}$ is the cut norm for real-valued kernels defined in (3.11). Using this equation with the graphs $G$ and $H$, we get:

$$ (6.2) \qquad \begin{aligned} \mathbb{P}(d_{\square, \mathcal{F}}(G, H) > 2\varepsilon) &\le \mathbb{P}\left(\sum_{n=1}^{N} 2^{-n} d_{\square, \mathbb{R}}(G[f_n], H[f_n]) > \varepsilon\right) \\ &\le \sum_{n=1}^{N} \mathbb{P}(d_{\square, \mathbb{R}}(G[f_n], H[f_n]) > \varepsilon), \end{aligned} $$

where $d_{\square, \mathbb{R}}$ denotes the cut distance associated to the cut norm $\| \cdot \|_{\square, \mathbb{R}}$ for real-valued graphons and kernels. Remark that for every $n \in \mathbb{N}$, $H[f_n]$ and $G[f_n]$ are real-weighted graphs with weights in $[0, 1]$. Thus, by a straightforward adaptation of the proof of [46, Lemma 10.11], we get:

$$ (6.3) \qquad \forall n \in [N], \quad \mathbb{P}(d_{\square}(G[f_n], H[f_n]) > \varepsilon) \le 2 \cdot 4^k e^{-2\varepsilon^2 k^2}. $$

Combining (6.2) and (6.3), we get for $\varepsilon > 10/\sqrt{k}$:

$$ \mathbb{P}(d_{\square, \mathcal{F}}(G, H) > 2\varepsilon) \le 2N4^k e^{-2\varepsilon^2 k^2} \le e^{-\varepsilon^2 k^2}, $$

where the last bound derives from simple calculus. This concludes the proof. □

We can apply the First Sampling Lemma 6.7 along with Lemma 6.9 to get the following lemma, equivalent of the first sampling lemma for the random weighted graph $\mathbb{G}(k, W)$:

COROLLARY 6.11 (First Sampling Lemma for $\mathbb{G}(k, W)$). — Let $U, W \in W_1$ be two probability-graphons, and $k \in \mathbb{N}^*$. Then, we can couple the random weighted graphs $\mathbb{G}(k, U)$ and $\mathbb{G}(k, W)$ such that with probability at least $1 - (4k^{1/4} + 1) e^{-\sqrt{k}/8}$, we have:

$$ |d_{\square, \mathcal{F}}(\mathbb{G}(k, U), \mathbb{G}(k, W)) - d_{\square, \mathcal{F}}(U, W)| \le \frac{14}{k^{1/4}}. $$

Proof. — Assume that $k \ge 14^4$ (otherwise the bound in the corollary is trivial). Then, we have with probability at least $1 - 4k^{1/4} e^{-\sqrt{k}/8} - 2e^{-100k}$
$$> 1 - (4k^{1/4} + 1) e^{-\sqrt{k}/8}$$

$$ (6.4) \quad \begin{aligned} & |d_{\square, \mathcal{F}}(\mathbb{G}(k, U), \mathbb{G}(k, W)) - d_{\square, \mathcal{F}}(U, W)| \\ & \le |d_{\square, \mathcal{F}}(\mathbb{G}(k, U), \mathbb{G}(k, W)) - d_{\square, \mathcal{F}}(\mathbb{H}(k, U), \mathbb{H}(k, W))| \\ & \quad + |d_{\square, \mathcal{F}}(\mathbb{H}(k, U), \mathbb{H}(k, W)) - d_{\square, \mathcal{F}}(U, W)| \\ & \le d_{\square, \mathcal{F}}(\mathbb{G}(k, U), \mathbb{H}(k, U)) \\ & \quad + d_{\square, \mathcal{F}}(\mathbb{G}(k, W), \mathbb{H}(k, W)) + \frac{11}{k^{1/4}} \\ & \le \frac{40}{\sqrt{k}} + \frac{11}{k^{1/4}} \\ & \le \frac{14}{k^{1/4}}, \end{aligned} $$

where we used the upper bound from the First Sampling Lemma 6.7 (which gives the coupling with the same random vector X to define both graphs $U_X = \mathbb{H}(k, U)$ and $W_X = \mathbb{H}(k, W)$) for the second inequality, the upper bound from Lemma 6.9 with $\varepsilon = 10/\sqrt{k}$ with both U and W for the third inequality, and that $\frac{1}{\sqrt{k}} \le \frac{1}{14k^{1/4}}$ for the last inequality. □

## 6.4. The distance between a probability-graphon and its sample

In this section, we present the Second Sampling Lemma, that shows that a sampled $M_1(\mathbf{Z})$-graph is close to its original probability-graphon with high probability. Note that we use the unlabeled cut distance $\delta_{\square, \mathcal{F}}$ rather than $d_{\square, \mathcal{F}}$ as the sample points are unordered. The bound on the distance is much weaker than the one in the First Sampling Lemma 6.7, but nevertheless goes to 0 as the sample size increases.

The proof is a straightforward adaptation of the proof of [46, Lemma 10.16] (replacing the weak regularity lemma and the first sampling lemma by their counterparts for probability-graphons, that is Lemmas 4.17 and 6.7; the sample concentration theorem for real-valued graphons can easily be adapted to probability-graphons).

**LEMMA 6.12 (Second Sampling Lemma).** — Let $\mathcal{F}$ be a convergence determining sequence. Let $W \in \tilde{W}_1$ be a probability-graphon and $k \in \mathbb{N}^*$. Then, with probability at least $1 - \exp(-k/(2 \ln(k)))$ we have:

$$ \delta_{\square, \mathcal{F}}(\mathbb{H}(k, W), W) \le \frac{21}{\sqrt{\ln(k)}} \quad \text{and} \quad \delta_{\square, \mathcal{F}}(\mathbb{G}(k, W), W) \le \frac{22}{\sqrt{\ln(k)}}. $$
In the above lemma, the asymmetric random graph $\mathbb{G}(k, W)$ can be replaced by the symmetric random graph $\mathbb{G}^{\text{sym}}(k, W)$ without changing the proof. Similarly, the results in Section 6.3.2 can be reformulated with symmetric random graphs $\mathbb{G}^{\text{sym}}(k, W)$ and $\mathbb{G}^{\text{sym}}(H)$ (but with a slight modification of the proof for Lemma 6.9 to symmetrize the random variable $X_{i,j}$ and with the upper bound $e^{-\epsilon^2 k^2/2}$, see also [46, Lemma 10.11]).

As an immediate consequence of Lemma 6.12 and of the Borel–Cantelli lemma, we get the convergence of the sampled subgraphs for the cut distance $\delta_{\square, \mathcal{F}}$.

**THEOREM 6.13 (Convergence of sampled subgraphs).** — Let $\mathcal{F}$ be a convergence determining sequence. Let $W \in \tilde{W}_1$ be a probability-graphon. Then, a.s. the sequence of sampled subgraphs $(\mathbb{G}(k, W))_{k \in \mathbb{N}^*}$ converges to $W$ for the cut distance $\delta_{\square, \mathcal{F}}$, and thus for any cut distance $\delta_{\square, \mathcal{M}}$ from Theorem 5.5.

# 7. The Counting Lemmas and the topology of probability-graphons

In this section, we introduce the homomorphism densities for probability-graphons, and then we link those to the cut distance $\delta_{\square, \mathcal{F}}$ through the Counting Lemma and the Inverse Counting Lemma. Those results are analogous to the case of real-valued graphons, see [46, Chapter 7] for the definition of homomorphism densities and [46, Chapter 10] for the Counting Lemma and Inverse Counting Lemma. The main differences with [46] are: the decoration of the edges of the graphs with functions from $C_b(\mathbb{Z})$; the Counting Lemma for the decorations belonging only in the convergence determining sequence $\mathcal{F}$; the more technical proof of the Inverse Counting Lemma. Note that we need to work with $\delta_{\square, \mathcal{F}}$ here as the proof of the Inverse Counting Lemma relies on the second sampling Lemma 6.12.

Finally, we prove our main result, Theorem 7.11, which states that the topology on the space of probability-graphons, see Theorem 5.5, which can be induced by several choices of cut distances (e.g. $\delta_{\square, \text{LP}}$, $\delta_{\square, \text{KR}}$, $\delta_{\square, \text{FM}}$ and $\delta_{\square, \mathcal{F}}$) coincides with the topology of convergence for all sampled subgraphs.

## 7.1. The homomorphism densities

In the case of non-weighted graphs, the homomorphism densities $t(F, G)$ allow to characterize a graph (up to twin-vertices expansion), and also
allow to define a topology for real-valued graphons. In the case of weighted
graphs and probability-graphons, we need to replace the absence/presence
of edges (which is 0-1 valued) by test functions from $C_b(\mathbb{Z})$ decorating each
edge.

In this section, we often need to fix the underlying (directed) graph structure $F = (V, E)$ (which may be incomplete) of a $C_b(\mathbb{Z})$-graph and to vary only the $C_b(\mathbb{Z})$-decorating functions $g = (g_e)_{e \in E}$, thus we will write $F^g = (V, E, g)$ for a $C_b(\mathbb{Z})$-graph. Moreover, when there exists a convergence determining sequence $\mathcal{F}$ such that $g_e \in \mathcal{F}$ for every edge $e \in E$, we say that $F^g$ is a $\mathcal{F}$-graph and use the same notation conventions.

DEFINITION 7.1 (Homomorphism density). — We define the homomorphism density of a $C_b(\mathbb{Z})$-graph $F^g$ in a signed measure-valued kernel $W \in \mathcal{W}_{\pm}$ as:

$$
(7.1) \quad t(F^g, W) = M_W^F(g) = \int_{[0,1]^{V(F)}} \prod_{(i,j) \in E(F)} W(x_i, x_j; g_{i,j}) \prod_{i \in V(F)} dx_i.
$$

Moreover, $M_W^F$ defines a measure on $\mathbb{Z}^E$ (which we still denote by $M_W^F$)
which is characterized by $M_W^F(\otimes_{e \in E} g_e) = M_W^F(g)$ for $g = (g_e)_{e \in E}$.

Remark 7.2 (Invariance under relabeling of homomorphism densities). Let $\varphi : [0,1] \to [0,1]$ be a measure-preserving map. As $\varphi^{\otimes k} : (x_1, \dots, x_k) \mapsto (\varphi(x_1), \dots, \varphi(x_k))$ is a measure-preserving map on $[0,1]^k$, applying the transfer formula (see (2.1)), we get that for every $C_b(\mathbb{Z})$-graph $F^g$ and every signed measure-valued kernel $W \in \mathcal{W}_{\pm}$, we have $t(F^g, W^{\varphi}) = t(F^g, W)$. Thus $t(F^g, \cdot)$ can be extended to $\tilde{\mathcal{W}}_{\pm}$.

Remark 7.3. — When $W \in \mathcal{W}_+$ is a measure-valued kernel, and $F$ is the graph with two vertices and one edge, we get that $M_W^F = M_W$ the measure defined in (4.1).

Remark 7.4 (Adding missing edges to F). — When we work with probability-graphons, we can always assume the graph F to be complete, by adding the missing edges (i, j) and decorating them with the constant function g_{(i,j)} = 1.

For a finite weighted graph $G$, we define the *homomorphism density* of
the $C_b(\mathbb{Z})$-graph $F^g$ in $G$ as $t(F^g, G) = t(F^g, W_G)$ (recall from Remark 6.2
the definition of $W_G$), that is:

$$
t(F^g, G) = \frac{1}{v(G)^k} \sum_{(x_1, \dots, x_k) \in V(G)^k} \prod_{(i,j) \in E(F)} g_{(i,j)}(\Phi_G(x_i, x_j)),
$$
where $k = v(F)$ and $\Phi_G(x_i, x_j)$ is the weight of the directed edge from $x_i$ to $x_j$.

## 7.2. The Counting Lemma

The following lemma links the homomorphism densities with the cut distance $\delta_{\square, \mathcal{F}}$ for some convergence determining sequence $\mathcal{F} = (f_n)_{n \in \mathbb{N}}$ (with $f_0 = 1$ and $f_n$ takes values in $[0, 1]$). This lemma is a generalization to probability-graphons of the Counting Lemma for real-valued graphons (see Lemmas 10.22 and 10.23 from [46]). Recall that by Remark 7.2, $t(F^g, \cdot)$ is defined on $\tilde{W}_{\pm}$.

**LEMMA 7.5 (Counting Lemma).** — Let $\mathcal{F} = (f_n)_{n \in \mathbb{N}}$ be a convergence determining sequence (with $f_0 = 1$ and $f_n$ taking values in $[0, 1]$). Let $F^g$ be a $\mathcal{F}$-graph, and for every edge $e \in E(F)$, let $n_e \in \mathbb{N}$ be such that $g_e = f_{n_e}$. Then, for every probability-graphons $W, W' \in \tilde{W}_1$, we have:

$$|t(F^g, W) - t(F^g, W')| \le \left( \sum_{e \in E(F)} 2^{n_e} \right) \delta_{\square, \mathcal{F}}(W, W').$$

*Remark 7.6* ($W \mapsto t(F^g, W)$ is Lipschitz). — The Lipschitz constant given by the lemma is too large to be useful in practical cases. Nevertheless, the homomorphism density function $W \mapsto t(F^g, W)$ is Lipschitz on the space of unlabeled probability-graphons $\tilde{W}_1$ equipped with the cut distance $\delta_{\square, \mathcal{F}}$.

*Proof of Lemma 7.5.* — To do this proof, we will apply Lemma 10.24 from [46], which applies to graphs $F$ whose edges are decorated with (possibly different) real-valued graphons $w = (w_e : e \in E(F))$, and the associated homomorphism density is defined as

$$(7.2) \qquad t(F, w) = \int_{[0,1]^{V(F)}} \prod_{(i,j) \in E(F)} w_e(x_i, x_j) \prod_{i \in V(F)} dx_i.$$

Recall from (3.7) that for a probability-graphon $W \in \mathcal{W}_1$ and a function $f \in \mathcal{F}$ (which is $[0, 1]$-valued by our definition of convergence determining sequences), we have that $W[f]$ is a real-valued graphon. Define the collections of real-valued graphons $w = (W[g_e] : e \in E(F))$ and $w' = (W'[g_e] : e \in E(F))$. Notice from (7.1) and (7.2) that we have $t(F, w) = t(F^g, W)$ and $t(F, w') = t(F^g, W')$. Applying [46, Lemma 10.24]
to the graph $F$ and edge-decorations $w$ and $w'$, we get:

$$|t(F^g, W) - t(F^g, W')| = |t(F, w) - t(F, w')| \le \sum_{e \in E(F)} \|W[g_e] - W'[g_e]\|_{\square, \mathbb{R}},$$

where the norm $\| \cdot \|_{\square, \mathbb{R}}$ in the upper bound is the cut norm for real-valued graphons (see (3.11) for definition of this object). For $e \in E(F)$, by definition of the cut distance $d_{\square, \mathcal{F}}$ and using (3.10), we have:

$$\|W[g_e] - W'[g_e]\|_{\square, \mathbb{R}} \le 2^{n_e} d_{\square, \mathcal{F}}(W, W').$$

Hence, combining all those upper bounds, we get the bound in the lemma but with $d_{\square, \mathcal{F}}$ instead of $\delta_{\square, \mathcal{F}}$. Since $t(F^g, \cdot)$ is invariant under relabeling by Remark 7.2, taking the infimum other all relabelings allows to replace $d_{\square, \mathcal{F}}$ by $\delta_{\square, \mathcal{F}}$ and to get the bound in the lemma. $\square$

We have just seen that homomorphism densities defined using only functions from $\mathcal{F}$ are Lipschitz. We are going to see that the other homomorphism densities are nevertheless continuous.

**LEMMA 7.7 (Weak Counting Lemma).** — Let $\mathcal{F}$ be a convergence determining sequence (with $f_0 = 1$). Let $(W_n)_{n \in \mathbb{N}}$ and $W$ be probability-graphons such that $\lim_{n \to \infty} t(F^g, W_n) = t(F^g, W)$ for all $\mathcal{F}$-graphs $F^g$ (which in particular the case if $\lim_{n \to \infty} \delta_{\square, \mathcal{F}}(W_n, W) = 0$ by the Counting Lemma 7.5). Then, for every $C_b(\mathbf{Z})$-graph $F^g$ we have:

$$t(F^g, W_n) \xrightarrow{n \to \infty} t(F^g, W).$$

*Proof.* — Let $F = (V, E)$ be some fixed (directed) graph. By assumption, we have for all edge-decorations $g = (g_e)_{e \in E}$ in $\mathcal{F}$ that $\lim_{n \to \infty} M_{W_n}^F (\otimes_{e \in E} g_e) = M_W^F (\otimes_{e \in E} g_e)$ (see Definition 7.1). By [24, Chapter 3, Proposition 4.6], $\mathcal{F}^{\otimes E}$ is a (countable) convergence determining family on $M_+(\mathbf{Z}^E)$. Thus, the sequence of measures $(M_{W_n}^F)_{n \in \mathbb{N}}$ converges to $M_W^F$ for the weak topology on $M_+(\mathbf{Z}^E)$. And in particular, for every edge-decoration function $g = (g_e)_{e \in E}$ (here for every $e \in E$, $g_e \in C_b(\mathbf{Z})$ is arbitrary) we have $M_{W_n}^F (\otimes_{e \in E} g_e) = t(F^g, W_n) \to t(F^g, W) = M_W^F (\otimes_{e \in E} g_e)$ as $n \to \infty$. This being true for all choices of the graph $F$, it concludes the proof. $\square$

## 7.3. The Inverse Counting Lemma

The goal of this subsection is to establish a converse to the Counting Lemma: if two probability-graphons are close in terms of homomorphism densities, then they are close w.r.t. the cut distance $\delta_{\square, \mathcal{F}}$.
LEMMA 7.8 (Inverse Counting Lemma). — Let $\mathcal{F} = (f_n)_{n \in \mathbb{N}}$ be a convergence determining sequence (with $f_0 = 1$ and $f_n$ takes values in $[0, 1]$). Let $U, W \in \tilde{W}_1$ be two probability-graphons, and let $k, n_0 \in \mathbb{N}^*$. Assume that we have $|t(F^g, U) - t(F^g, W)| \le 2^{-k-n_0k^2}$ for every (complete) $C_b(\mathbf{Z})$-graph $F^g$ with $k$ vertices and such that the edge-decoration functions $g = (g_e)_{e \in E(F)}$ are products (without repetition) of the functions $(f_n)_{1 \le n \le n_0}$ and $(1 - f_n)_{1 \le n \le n_0}$. Then, we have:

$$ \delta_{\square, \mathcal{F}}(U, W) \le \frac{44}{\sqrt{\log(k)}} + 2^{-n_0}. $$

To prove Lemma 7.8, we first need to prove the special case where the space $\mathbf{Z}$ is finite.

LEMMA 7.9 (Inverse Counting Lemma, case with finite space $\mathbf{Z}$). — Assume that the space $\mathbf{Z}$ is finite with cardinality $n_1$, for simplicity say $\mathbf{Z} = [n_1]$. Define the indicator functions $f_n : z \mapsto 1_{\{z=n\}}$ for $n \in [n_1]$, in particular $\mathcal{H} = (f_n)_{1 \le n \le n_1}$ is a finite convergence determining sequence. Let $U, W \in \tilde{W}_1$ be two probability-graphons, and let $k \in \mathbb{N}^*$. Assume that we have $|t(F^g, U) - t(F^g, W)| < 2^{-k-\log_2(n_1)k^2}$ for every (complete) $\mathcal{H}$-graph $F^g$ with $k$ vertices.

Then, for any (possibly finite) convergence determining sequence $\mathcal{F}$, we have:

$$ \delta_{\square, \mathcal{F}}(U, W) \le \frac{44}{\sqrt{\log(k)}}. $$

Abusing notations, we can identify a weight-value $n \in \mathbf{Z}$ with its indicator function $f_n$, and doing this identification for edge-decoration functions, we can identify a $\mathcal{F}$-graph $F^g$ with its corresponding weighted graph. In particular, doing so we get $t(F^g, W) = \mathbb{P}(\mathcal{G}(k, W) = F^g)$ for every $\mathcal{F}$-graph $F^g$ with $k$ vertices. The proof of Lemma 7.9 is then a straightforward adaptation of the proof of [46, Lemma 10.31 and Lemma 10.32].

Proof of Lemma 7.8. — As the functions $(f_n)_{n \in \mathbb{N}}$ take value in $[0, 1]$, for all $\varphi$ measure-preserving map, for all $S, T \subset [0, 1]$ measurable sets and for all $n \in \mathbb{N}$, we have:

$$ |U(S \times T; f_n) - W^\varphi(S \times T; f_n)| \le 1. $$

Using this bound, we get the following bound (recall that $f_0 = 1$):
(7.3)

$$ \delta_{\square, \mathcal{F}}(U, W) \le \inf_{\varphi \in S_{[0,1]}} \sup_{S, T \subset [0,1]} \sum_{n=1}^{n_0} 2^{-n} \left| U(S \times T; f_n) - W^\varphi(S \times T; f_n) \right| + 2^{-n_0}. $$
Hence, for a point $z \in \mathbb{Z}$, the upper bound in (7.3) uses only the information given by $(f_n(z))_{n \in [n_0]}$. In order to discretize the space $[0, 1]^{n_0}$, we replace a point $p = (p_1, \dots, p_{n_0}) \in [0, 1]^{n_0}$ by a random point $(Y_1, \dots, Y_{n_0}) \in \{0, 1\}^{n_0}$ where the $Y_i$ are independent random variables with Bernoulli distribution of parameter $p_i$. This leads us to replace a $\mathcal{M}_1(\mathbb{Z})$-valued kernel $W$ by the $\mathcal{M}_1(\{0, 1\}^{n_0})$-valued kernel $\tilde{W}$ defined for all $(x, y) \in [0, 1]^2$, and for all $s = (s_1, \dots, s_{n_0}) \in \{0, 1\}^{n_0}$ as:

$$ \tilde{W}(x, y; \{s\}) = W(x, y; f^s) \quad \text{where} \quad f^s = \prod_{n=1}^{n_0} f_n^{s_n} (1 - f_n)^{1-s_n}. $$

Fix some enumeration $(s^m)_{m \in [2^{n_0}]}$ of the points in $\{0, 1\}^{n_0}$, and define the indicator functions $\tilde{h}_m : s \mapsto \mathbb{1}_{\{s=s^m\}}$ for $m \in [2^{n_0}]$, in particular $\tilde{H} = (\tilde{h}_m)_{1 \le m \le 2^{n_0}}$ is a finite convergence determining sequence on $\mathcal{M}_+(\{0, 1\}^{n_0})$. Let $F^{\tilde{g}}$ be a $\tilde{H}$-graph with vertex set $V(F) = [k]$, and for every edge $e \in E(F)$, let $m_e \in [2^{n_0}]$ be such that $\tilde{g}_e = \tilde{h}_{m_e}$. Define the edge-decoration functions $g = (g_e)_{e \in E(F)}$ for every edge $e \in E(F)$ as $g_e = f^{s_{m_e}}$, then we get:

$$ t(F^{\tilde{g}}, \tilde{W}) = \int_{[0,1]^k} \prod_{(i,j) \in E(F)} \tilde{W}(x_i, x_j; \{s^{m_e}\}) \prod_{i=1}^k dx_i = t(F^g, W). $$

Thus, the $\mathcal{M}_1(\{0, 1\}^{n_0})$-valued graphons $\tilde{U}$ and $\tilde{W}$ inherit the bounds on the homomorphism densities: for every $\tilde{H}$-graph $F^{\tilde{g}}$, we have $|t(F^{\tilde{g}}, \tilde{U}) - t(F^{\tilde{g}}, \tilde{W})| \le 2^{-k-n_0k^2}$.

Define for all $n \in [n_0]$ the function $\tilde{f}_n : s \mapsto \mathbb{1}_{\{s_n=1\}}$, and let $\tilde{\mathcal{F}}$ be the concatenation of $(\tilde{f}_n)_{n \in [n_0]}$ and $\tilde{H}$, in particular $\tilde{\mathcal{F}}$ is a finite convergence determining sequence on $\mathcal{M}_+(\{0, 1\}^{n_0})$. Finally, as $\delta_{\square, \tilde{\mathcal{F}}}(\tilde{U}, \tilde{W})$ upper bounds the first term in the upper bound of (7.3), applying Lemma 7.9 with the finite space $\mathbb{Z} = \{0, 1\}^{n_0}$ and $n_1 = 2^{n_0}$, the finite convergence determining sequences $\tilde{\mathcal{F}}$ and $\tilde{H}$, and the $\mathcal{M}_1(\{0, 1\}^{n_0})$-valued graphons $\tilde{U}$ and $\tilde{W}$, we get:

$$ \delta_{\square, \tilde{\mathcal{F}}}(U, W) \le \frac{44}{\sqrt{\ln(k)}} + 2^{-n_0}, $$

which concludes the proof. $\square$

<figure><img src="image_5.png" /></figure>

## 7.4. Subgraph sampling and the topology of probability-graphons

Thanks to the Weak Counting Lemma 7.7 and the Inverse Counting Lemma 7.8, we can formulate a new informative characterization of weak
isomorphism, i.e. equality in the space of unlabeled probability-graphons $\tilde{W}_1$. Note that the propositions and the theorem in this subsection can in particular be applied to $\delta_{\square,m}$ when $d_m$ is a quasi-convex distance continuous w.r.t. the weak topology, as then $d_{\square,m}$ is invariant, smooth, weakly regular and regular w.r.t. the stepping operator (see Proposition 4.13).

**PROPOSITION 7.10 (Characterization of equality for $\delta_{\square,m}$).** — Let $U, W \in W_1$ be two probability-graphons. The following properties are equivalent:

(i) $\delta_{\square,m}(U, W) = 0$ for some (and hence for every) choice of the distance $d_m$ on $M_{\le 1}(\mathbf{Z})$ such that the cut distance $d_{\square,m}$ on $W_1$ is (invariant) smooth.

(ii) There exist $\varphi, \psi \in \bar{S}_{[0,1]}$ such that $U\varphi = W\psi$ almost everywhere on $[0,1]^2$.

(iii) $t(F^g, U) = t(F^g, W)$ for all $C_b(\mathbf{Z})$-graphs $F^g$.

(iv) $t(F^g, U) = t(F^g, W)$ for all $\mathcal{F}$-graphs $F^g$.

*Proof.* — The equivalence between Properties (i) and (ii) is a consequence of Proposition 3.18 on the cut distance. Remark 7.2 gives that Property (ii) implies Property (iii). It is clear that Property (iii) implies Property (iv). The Inverse Counting Lemma 7.8 with the Weak Counting Lemma 7.7 give that Property (iv) implies Property (i) (with $d_m = d_{\mathcal{F}}$). Hence, we have the desired equivalence. $\square$

Thanks to the Weak Counting Lemma 7.7 and the Inverse Counting Lemma 7.8, we get the following characterization of the topology induced by the cut distance $\delta_{\square,m}$ on the space of unlabeled probability-graphons $\tilde{W}_1$ in terms of homomorphism densities

**THEOREM 7.11 (Characterization of the topology induced by $\delta_{\square,m}$).** — Let $(W_n)_{n \in \mathbb{N}}$ and $W$ be unlabeled probability-graphons from $\tilde{W}_1$. The following properties are equivalent:

(i) $\lim_{n \to \infty} \delta_{\square,m}(W_n, W) = 0$ for some (and hence for every) choice of the distance $d_m$ on $M_{\le 1}(\mathbf{Z})$ such that $d_m$ induces the weak topology on $M_{\le 1}(\mathbf{Z})$ and the cut distance $d_{\square,m}$ on $W_1$ is (invariant) smooth, weakly regular and regular w.r.t. the stepping operator.

(ii) $\lim_{n \to \infty} t(F^g, W_n) = t(F^g, W)$ for all $C_b(\mathbf{Z})$-graphs $F^g$.

(iii) $\lim_{n \to \infty} t(F^g, W_n) = t(F^g, W)$ for all $\mathcal{F}$-graphs $F^g$.

(iv) For all $k \ge 2$, the sequence of sampled subgraphs $(\mathbb{G}(k, W_n))_{n \in \mathbb{N}}$ converges in distribution to $\mathbb{G}(k, W)$.
In particular, the topology induced by the cut distance $\delta_{\square, \mathcal{F}}$ on the space of unlabeled probability-graphons $\tilde{W}_1$ coincides with the topology generated by the homomorphism densities functions $W \mapsto t(F^g, W)$ for all $C_b(\mathbf{Z})$-graphs $F^g$.

*Proof.* — By Theorem 5.5, convergence for $\delta_{\square, \mathcal{F}}$ is equivalent to convergence for $\delta_{\square,m}$ for every choice of the distance $d_m$ on $M_{\le 1}(\mathbf{Z})$ such that $d_m$ induces the weak topology on $M_{\le 1}(\mathbf{Z})$ and the cut distance $d_{\square,m}$ on $W_1$ is (invariant) smooth, weakly regular and regular w.r.t. the stepping operator. Taking $d_m = d_{LP}$, the Weak Counting Lemma 7.7 gives that Property (i) implies Property (ii). It is clear that Property (ii) implies Property (iii). The Inverse Counting Lemma 7.8 with the Weak Counting Lemma 7.7 give that Property (iii) implies Property (i) (with $d_m = d_{\mathcal{F}}$). Notice that when $F$ is the complete graph with $k$ vertices, $M_W^F$ is the joint measure of all the edge-weights of the random graph $\mathbb{G}(k, W)$, and thus characterizes the distribution random graph $\mathbb{G}(k, W)$. Thus (recall Definition 7.1), Property (ii) and Property (iv) are equivalent. Hence, we have the desired equivalence. $\square$

**QUESTION 7.12** (Do the distances $d_{\square, \mathcal{F}}$ all induce the same topology?). Even though every distance $\delta_{\square, \mathcal{F}}$ generates the same topology on the space of unlabeled probability-graphons $\tilde{W}_1$, it is an open question whether or not it is also the case that every distance $d_{\square, \mathcal{F}}$ induces the same topology on the space of labeled probability-graphons $W_1$.

The following proposition states that to prove existence of a limit unlabeled probability-graphon it is enough to prove that there exists a convergence determining sequence $\mathcal{F}$ such that for every $\mathcal{F}$-graph $F^g$ the homomorphism densities $t(F^g, \cdot)$ converge.

**PROPOSITION 7.13** (Existence of a limit unlabeled probability-graphon). Let $d_m$ be a distance on $M_{\le 1}(\mathbf{Z})$ such that $d_m$ induces the weak topology on $M_{\le 1}(\mathbf{Z})$ and the cut distance $d_{\square,m}$ on $W_1$ is (invariant) smooth, weakly regular and regular w.r.t. the stepping operator.

Let $(W_n)_{n \in \mathbb{N}}$ be sequence of unlabeled probability-graphons in $\tilde{W}_1$ that is tight. Let $\mathcal{F}$ be a convergence determining sequence such that for every $\mathcal{F}$-graph $F^g$ the sequence $(t(F^g, W_n))_{n \in \mathbb{N}}$ converges. Then, there exists an unlabeled probability-graphon $W \in \tilde{W}_1$ such that the sequence $(W_n)_{n \in \mathbb{N}}$ converges to $W$ for $\delta_{\square,m}$.

*Proof.* — Since the sequence $(W_n)_{n \in \mathbb{N}}$ is tight, by Theorem 5.1, there exists a subsequence $(W_{n_k})_{k \in \mathbb{N}}$ of the sequence $(W_n)_{n \in \mathbb{N}}$ that converges to
some $W$ for $\delta_{\square,m}$. By Theorem 7.11, we have for every $\mathcal{F}$-graph $F^g$ that $\lim_{k\to\infty} t(F^g, W_{n_k}) = t(F^g, W)$; and as we already know that the sequence $(t(F^g, W_n))_{n\in\mathbb{N}}$ converges, we have that $\lim_{n\to\infty} t(F^g, W_n) = t(F^g, W)$. Hence, by Theorem 7.11, we get that the sequence $(W_n)_{n\in\mathbb{N}}$ converges to $W$ for $\delta_{\square,m}$. $\square$

**Remark 7.14.** — For the special case $\mathbb{Z} = \{0,1\}$, which is compact, we find back that convergence for real-valued graphons is characterized by the convergence of the homomorphism densities. Notice the tightness condition of Proposition 7.13 is automatically satisfied as $\mathbb{Z}$ is compact.

## 8. Proofs of Theorem 5.1 and Theorem 5.5

We start by proving a lemma that allows to construct a convergent sub-sequence and its limit kernel for a tight sequence of measure-valued kernels. This lemma is useful for the proofs of both Theorem 5.1 and Theorem 5.5. For the proof of Theorem 5.5, we will also need the convergence to hold simultaneously for two distances $\delta_{\square}$ and $\delta'_{\square}$. Recall from Definition 4.1 the definition of the stepfunction $W_{\mathcal{P}}$ for a signed measure-valued kernel $W$ and a finite partition $\mathcal{P}$ of $[0,1]$. For a finite partition $\mathcal{P}$ of $[0,1]$, define its diameter as the smallest diameter of its sets, i.e. $\text{diam}(\mathcal{P}) = \min_{S\in\mathcal{P}} \text{diam}(S) = \min_{S\in\mathcal{P}} \sup_{x,y\in S} |x-y|$.

**LEMMA 8.1** (Convergence using given approximation partitions). — Let $d$ be an invariant smooth distance on $W_1$ (resp. $W_+$ or $W_\pm$). Let $(W_n)_{n\in\mathbb{N}}$ be a sequence in $W_1$ (resp. $W_+$ or $W_\pm$) which is tight (resp. uniformly bounded and tight). Further assume that we are given, for every $n, k \in \mathbb{N}$, partitions $\mathcal{P}_{n,k}$ of $[0,1]$, such that these partitions and the corresponding stepfunctions $W_{n,k} = (W_n)_{\mathcal{P}_{n,k}}$ satisfy the following conditions:

(i) the partition $\mathcal{P}_{n,k+1}$ is a refinement of $\mathcal{P}_{n,k}$,

(ii) $\text{diam}(\mathcal{P}_{n,k}) \le 2^{-k}$ and $|\mathcal{P}_{n,k}| = m_k$ depends only on $k$ (and not on $n$),

(iii) $d(W_n, W_{n,k}) \le 1/(k+1)$.

Then, there exists a subsequence $(W_{n_l})_{l\in\mathbb{N}}$ of the sequence $(W_n)_{n\in\mathbb{N}}$ and a measure-valued kernel $W \in W_1$ (resp. $W_+$ or $W_\pm$) such that $(W_{n_l})_{l\in\mathbb{N}}$ converges to $W$ for $\delta_{\square}$.

Moreover, assume that $d'$ is another invariant smooth distance on $W_1$ (resp. $W_+$ or $W_\pm$) such that for every $n \in \mathbb{N}$ and $k \in \mathbb{N}$, $W_{n,k}$ also satisfies:

(iv) $d'(W_n, W_{n,k}) \le 1/(k+1)$.