Romain Abraham

AND Jean-François Delmas
email: jean-francois.delmas@enpc.fr

Julien Weibel
email: julien.weibel@normalesup.org

PROBABILITY-GRAPHONS: LIMITS OF LARGE DENSE WEIGHTED GRAPHS

Keywords: Mathematics Subject Classification. 05C80, 60B10 random graphs, stochastic networks, graphons, probability-graphons, dense graph limits, weighted graphs, decorated graphs

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 dm 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 dm, which are satisfied for some well-know distances like the Prohorov distance, and the Fortet-Mourier and Kantorovitch-Rubinstein norms, the topology induced by the cut distance on the space of probability-graphons is independent from the choice of dm. 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 context, including for example: biological networks [START_REF] Bornholdt | Handbook of Graphs and Networks: From the Genome to the Internet[END_REF][START_REF] Gyle | Network Science: Theory and Practice[END_REF], epidemics processes [START_REF] Draief | Epidemics and Rumours in Complex Networks[END_REF][START_REF] István | Mathematics of Epidemics on Networks: From Exact to Approximate Models[END_REF], electrical power grids [START_REF] Albert | Structural vulnerability of the North American power grid[END_REF] and social networks [START_REF] Albert | Statistical mechanics of complex networks[END_REF][START_REF] Newman | The Structure and Function of Complex Networks[END_REF]. 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. 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 [LS06, FLS06, BJR10, BCL + 08, BCL + 12]. We shall refer to the monograph [START_REF] Lovász | Large networks and graph limits[END_REF] 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 [START_REF] Borgs | Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks[END_REF], SIS epidemic models [START_REF] Delmas | An infinite-dimensional metapopulation SIS model[END_REF], the study of transferability properties for Graph Neural Networks [START_REF] Keriven | What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding[END_REF]. Furthermore, there has been recent developments in the study of mean-field systems using graphons: stochastic games and their Nash equilibria [START_REF] Lacker | A Label-State Formulation of Stochastic Graphon Games and Approximate Equilibria on Large Networks[END_REF], opinion dynamic on a graphon [START_REF] Aletti | Opinion dynamics on graphon: The piecewise constant case[END_REF], cooperative multi-agent reinforcement learning [START_REF] Hu | Graphon mean-field control for cooperative multi-agent reinforcement learning[END_REF], to cite a few. However, most real-world phenomenon 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 [BVDHH10, [START_REF] Amini | Flooding in Weighted Sparse Random Graphs[END_REF][START_REF] Amini | The diameter of weighted random graphs[END_REF], see also [START_REF] Garlaschelli | The weighted random graph model[END_REF][START_REF] Hurd | On Watts' cascade model with random link weights[END_REF] 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 [START_REF] Alonso | Weighted randomgeometric and random-rectangular graphs: Spectral and eigenfunction properties of the adjacency matrix[END_REF].

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 [START_REF] Lelarge | Reconstruction in the labeled stochastic block model[END_REF] (see also [START_REF] Xu | Edge label inference in generalized stochastic block models: from spectral theory to impossibility results[END_REF] for more general models where vertex-labels come from a compact space), and exact community recovery in [START_REF] Jog | Recovering communities in weighted stochastic block models[END_REF], and to get bounds on the number of misclassified vertices in [START_REF] Yun | Optimal cluster recovery in the labeled stochastic block model[END_REF][START_REF] Xu | Optimal rates for community estimation in the weighted stochastic block model[END_REF]. 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 [START_REF] Ayi | Graph Limit for Interacting Particle Systems on Weighted Random Graphs[END_REF], the authors studied mean-field equations on large realweighted graphs modeling interactions with a probability kernel from [0, 1] 2 to M 1 (R) the set of probability measures on R, but they did not study the topological properties of the set of those probability kernels. Recently, in [START_REF] Hladký | Random minimum spanning tree and dense graph limits[END_REF], 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 [START_REF] Hladký | The local limit of the uniform spanning tree on dense graphs[END_REF][START_REF] Archer | The GHP scaling limit of uniform spanning trees in high dimensions[END_REF], 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 (Z) on a Polish space Z. When Z is compact, this question has been considered in [START_REF] Lovász | Limits of compact decorated graphs[END_REF] and in [Lov12, Section 17.1] using convergence of homomorphism densities of subgraphs decorated with real functions defined on Z, but the metric properties of the set of probability-graphons W 1 have only been established when Z is finite, see [START_REF] Falgas-Ravry | Multicolour containers and the entropy of decorated graph limits[END_REF]. The work [START_REF] Kunszenti-Kovács | Multigraph limits, unbounded kernels, and Banach space decorated graphs[END_REF] is an extension of [START_REF] Lovász | Limits of compact decorated graphs[END_REF] where M 1 (Z) is replaced by the dual space Z of a separable Banach space B. As M 1 (Z) is a subset of the dual of C b (Z), this approach covers our setting when C b (Z) is separable, that is, Z compact (see Section 2 below). The norm introduced on the space of Z-valued graphons therein implies the convergence of homomorphims densities of B-decorated sub-graphs, however there is no equivalence a priori.

In this paper we study the topological property of the space of probability-graphons W 1 when Z is a general Polish space: the space W 1 is a Polish topological space and we give "natural" cut distances on W 1 which are complete. One of the main difficulty is that the space of probability measures M 1 (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 W 1 . We prove that the topology induced on W 1 does not depend on the initial choice of the distance on M 1 (Z), provided this distance satisfies some simple general conditions. However, we stress that not all of these cut distances are complete. We also check that this topology characterizes 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 (Z)-decorated subgraphs. Similarly to the graphon setting, we prove the convergence in distribution of large sampled weighted subgraphs from a probability-graphon W to itself. 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 Z (e.g. Z, R or 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 → M 1 (Z), where M 1 (Z) is the space of probability measures on 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 particular, the special case Z = {0, 1} allows to recover real-valued graphons: as any real-valued graphon w : [0, 1] 2 → [0, 1] can be represented as a probability-graphon W (x, y; •) = w(x, y)δ 1 + (1w(x, y))δ 0 , where δ z denote the Dirac mass located at z. Let us mention that it is possible to define the probabilitygraphons on a more general probability space (Ω, A, µ) 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 measurevalued kernels which are bounded (in total mass/total variation norm) measurable functions W : [0, 1] 2 → M ± (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) ∈ [0, 1] 2 , and we denote by W 1 the space of probability-graphons. Moreover, as we consider weighted graphs that are unlabeled (that is vertices are unordered), we need to consider probability-graphons up to "relabeling": for a measure-preserving map ϕ : [0, 1] → [0, 1] (relabeling map for probability-graphons), we define W ϕ (x, y; •) = W (ϕ(x), ϕ(y); •); we say that two probability-graphons are weakly isomorphic if there exists measure-preserving maps ϕ, ψ : [0, 1] → [0, 1] such that U ϕ = W ψ for a.e. (x, y) ∈ [0, 1] 2 . We denote by W 1 the space of probability-graphons where we identity 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 ∂ which is a cemetery point added to 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 , • • • , I n of equal lengths, then W G is defined for (x, y) ∈ I i × I j as W G (x, y; •) = δ M(i,j) , where M (i, j) is the weight on the edge (i, j) in G. 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; •) = W (y, x; •). 1.2.2. The cut distance for probability-graphons and its properties. While there is a usual distance on the field of reals R, this is not the case for probability measures, measures or signed measures endowed with the weak topology. Some commonly used distances include the Prohorov distance d P which can be defined on measures, and the Kantorovitch-Rubinstein norm • KR (sometimes also called the bounded Lipschitz norm) and the Fortet-Mourier norm • 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 • F based on a convergence determining sequence F ⊂ C b (Z). See Section 3.8 for definition 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 ≤1 (Z) (i.e. measures with total mass at most 1); we then define the cut distance d ,m for probability-graphons as:

d ,m (U, W ) = sup S,T ⊂[0,1] d m U (S × T ; •), W (S × T ; •) ,
where the supremum is taken over all measurable subsets S and T of [0, 1], and where W (S × T ; •) = S×T W (x, y; •) 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 ± (Z), then the cut distance d ,m derives from the cut norm N ,m defined on signed measure-valued kernels:

N ,m (W ) = sup S,T ⊂[0,1] N m W (S × T ; •) .
We then define the unlabeled cut distance δ ,m on the space of unlabeled probability-graphons W 1 as:

δ ,m (U, W ) = inf ϕ d ,m (U, W ϕ ) = min ϕ,ψ d ,m (U ϕ , W ψ ),
where the infimum is taken over all measure-preserving maps ϕ and ψ, see Proposition 3.18 for alternative expressions of δ ,m (including proof that the minimum exist for the second expression) and see Theorem 3.17 that states that δ ,m is indeed a distance on W 1 . In Proposition 4.13, we prove an equivalent of the weak regularity lemma for probability-graphons. An interesting fact is that under some conditions on d m , the topology induced by the associated cut distance δ ,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.1. The cut distances δ ,P , δ ,KR , δ ,FM and δ ,F induce the same topology on the space of probability-graphons W 1 .

Recall that Z is a Polish space. We now state that W 1 is also Polish for the distance δ ,P (but not for δ ,F !), and we refer to Theorem 5.10 for other distances.

Theorem 1.2. The space of probability-graphons ( W 1 , δ ,P ) is a Polish metric space.

We prove an analogue of Prohorov's theorem with a tightness criterion for probability-graphons. We say that a subset of probability-graphons K ⊂ W 1 is tight if the set of probability measures {M W : W ∈ K} is tight (in the sense of probability measures), where M W (•) = W ([0, 1] 2 ; •). The next result is consequence of Theorem 5.1 as well as Corollary 4.14.

Theorem 1.3 (Compactness property). Consider the topology on W 1 from Proposition 1.1.

(i) If a sequence of elements of W 1 is tight, then it has a converging subsequence. (ii) If Z is compact, then the space 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 δ ,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 probabilitygraphons. The W -random graph (or sampled subgraph of size k) 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 , • • • , X k be k independent random "vertex-types" uniformly distributed over [0, 1]; then given X 1 , • • • , X k , each edge receive a weight independently, where the weight of the edge (i, j) is distributed as W (X i , X j ; •).

We also provide the a.s. convergence of sampled subgraphs for the topology from Proposition 1.1, see Theorem 6.13 together with Corollary 5.6. Theorem 1.4. Let W be a probability-graphon. Then, a.s. the sequence of sampled subgraphs (G(k, W )) k∈N * converges to W for the topology from Proposition 1.1.

To prove this theorem, we adapt the proof scheme of [Lov12, 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 δ ,F because of the good approximations properties of • F .

In the case of unweighted graphs, the homomorphism numbers hom(F, G) count the number of occurence 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 realvalued 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 (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∈E from a subset G ⊂ C b (Z) (in practice, we only consider the cases G = C b (Z) or G = F ⊂ C b (Z) a convergence determining sequence), in a probability-graphon W as:

t(F g , W ) = M F W (g) := [0,1] V (i,j)∈E W (x i , x j ; g i,j ) i∈V dx i , where W (x, y; f ) = Z f (z) W (x, y; dz). Moreover, M F W defines a measure on Z E (which we still denote by M F W ) which is defined by M F W (⊗ e∈E g e ) = M F W (g) for g = (g e ) e∈E .
Note that when F is the complete graph with k vertices, M F W is the joint measure of all the edge-weights of the random graph G(k, W ), and thus characterizes the random graph G(k, W ).

In the counting Lemma 7.5 and the weak counting Lemma 7.7, we prove that the cut norm • ,F allows to control the homomorphism densities. Conversely, in the inverse counting Lemma 7.8, we prove that the cut norm • ,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.5 (Characterization of the topology). Let (W n ) n∈N and W be unlabeled probabilitygraphons from W 1 . The following properties are equivalent:

(i) (W n ) n∈N converges to W for the topology from Proposition 1.1. (ii) lim n→∞ t(F g , W n ) = t(F g , W ) for all C b (Z)-graph F g . (iii) lim n→∞ t(F g , W n ) = t(F g , W ) for all F -graph F g , for some convergence determining sequence F . (iv) For all k ≥ 2, the sequence of sampled subgraphs (G(k, W n )) n∈N converges in distribution to 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∈N ; here convergent means that for all k ≥ 2, the sequence (G(k, G n ) = G(k, W Gn )) n∈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∈N can be equivalently rephrased as tightness of the sequence (G(2, W n )) n∈N of sampled subgraphs of size 2. Hence, the convergence in distribution of the sequence (G(2, G n )) n∈N implies its tightness, and thus the tightness of the sequence of probability-graphons (W Gn ) n∈N . Then, Theorem 1.3 guarantees the existence of a probability-graphon W which is a sub-sequential limit of the sequence (W Gn ) n∈N in the cut distance δ ,F , and then Theorem 1.5 guarantees that for all k ≥ 2, the sequence (G(k, G n )) n∈N converges in distribution to G(k, W ).

As a consequence, probability-graphons are precisely the limit objects for sequences of weighted graphs (G n ) n∈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 ≥ 2, the sequence of sampled subgraphs (G(k, G n )) n∈N converges in distribution.

Remark 1.6 (Extension to vertex-weights). The framework we have developed for probabilitygraphons 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 probabilitygraphons have a two-variable kernel (probability-graphon) W e for edge-weights as before, and a one-variable kernel W v : [0, 1] → M 1 (Z) for vertex-weights. Note that this implies, as expected, that the same measure-preserving map ϕ : [0, 1] → [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 remind 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 Prohorov distance d P , the Kanrorovitch-Rubinstein and Fortet-Mourier norms • KR and • FM , and the norm

• 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 G(k, W ) sampled from a probability-graphon W , we then prove approximation bound in the cut norm • ,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. 2. Notations and topology on the space of signed measures Through the article, measure will always be used to denote a positive measure.

Let N = Z + be the set of non-negative integers, N * = N\{0} the set of positive integers, and, for n ∈ N * , we define the integer set [n] = {1, . . . , n}. For k ∈ N * , the set [0, 1] k is endowed with the Borel σ-field and the Lebesgue measure λ k ; and we write λ for λ k when the context is clear. The supremum of a real-valued function f defined on [0, 1] k is denoted by

f ∞ = sup x∈[0,1] k f (x).
Let d be a distance on a topological space (X, O).

(i) The distance d is continuous w.r.t. the topology O if the identity map from (X, O) to (X, d) is continuous. (ii) The distance d is sequentially continuous w.r.t. the topology O if for any sequence (x n ) n∈N in X which converges to some limit x for the topology O, we also have that lim n→∞ 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 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 O if and only if for every sequence with values in X, convergence for d is equivalent to convergence for O (see [Eng89, 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 [Eng89, 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 ϕ : Ω 1 → Ω 2 between two probability spaces (Ω i , A i , π i ), i = 1, 2, is measure-preserving if it is measurable and if for every A ∈ A 2 , π 2 (A) = π 1 (ϕ -1 (A)). In this case, for every measurable non-negative function f : Ω 2 → R, we have:

(1) Ω1 f (ϕ(x)) π 1 (dx) = Ω2 f (x) π 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 S[0,1] the set of measure-preserving maps from [0, 1] with the Lebesgue measure to itself.

Let (Z, O Z ) be some (non-empty) Polish space, and let B(Z) be the Borel σ-field on Z generated by the topology O Z . We denote by C b (Z) the space of real-valued continuous bounded functions on (Z, O Z ). We denote by M ± (Z) the space of finite signed measures on (Z, B(Z)); M + (Z) the subspace of measures; M ≤1 (Z) the subspace of measures with total mass at most 1; and M 1 (Z) the subspace of probability measures. We have:

M 1 (Z) ⊂ M ≤1 (Z) ⊂ M + (Z) ⊂ M ± (Z).
For a signed measure µ ∈ M ± (Z), we remind the definition of the Hahn-Jordan decomposition µ = µ +µ -where µ + , µ -∈ M + (Z) are mutually singular measures (that is µ + (A) = 0 and µ -(A c ) = 0 for some measurable set A), as well as the total variation measure of µ which is defined as |µ| = µ + + µ -∈ M + (Z). Note that for a measure µ ∈ M + (Z), we simply have |µ| = µ. For a signed-measure µ ∈ M ± (Z) and a real-valued measurable function f defined on Z, we write µ(f ) = µ, f = f dµ = Z f (x) µ(dx) the integral of f w.r.t. µ whenever it is well defined. For a signed measure µ ∈ M ± (Z), we denote by µ ∞ = µ + (Z) + µ -(Z) its total mass, which is also equal to the supremum of µ(f ) over all measurable functions f with values in [-1, 1].

We endow M ± (Z) with the topology of weak convergence, that is the smallest topology for which the maps µ → µ(f ) are continuous for all f ∈ C b (Z). In particular, a sequence of signed measures (µ n ) n∈N weakly converges to some µ ∈ M ± (Z) if and only if, for every function f ∈ C b (Z), we have lim n→+∞ µ n (f ) = µ(f ). Let us recall that M + (Z) and M 1 (Z) endowed with the topology of weak convergence are Polish spaces.

Remark 2.3 (The weak topology on M ± (Z)). The topology of weak convergence on the set of signed measures M ± (Z) is equivalent to the weak- * topology on M ± (Z) seen as a subspace of the topological dual of C b (Z) (see the paragraph after Definition 3.1.1 in [START_REF] Bogachev | Weak Convergence of Measures[END_REF]). As usual in probability theory, this topology will be simply called the weak topology (this is also consistent with [START_REF] Bogachev | Weak Convergence of Measures[END_REF]).

We recall that a sequence of [0, 1]-valued functions

F = (f k ) k∈N in C b (Z), with f 0 = 1 the constant function equal to one, is: (i) Separating if for every measures µ, ν from M ± (Z) (or equivalently just from M + (Z)) such that for every k ∈ N, µ(f k ) = ν(f k ), then µ = ν. (ii) Convergence determining if for every (µ n ) n∈N and µ measures from M + (Z) such that we have lim n→+∞ µ n (f k ) = µ(f k ) for all k ∈ N, then (µ n ) n∈N weakly converges to µ.
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 [START_REF] Stewart | Markov processes: characterization and convergence[END_REF]Theorem 3.4.5]). There always exists a convergence determining sequence on Polish spaces, see [START_REF] Bogachev | Weak Convergence of Measures[END_REF]Corollary 2.2.6] or the proof of Proposition 3.4.4 in [START_REF] Stewart | Markov processes: characterization and convergence[END_REF] (which are stated for probability measures but can be extended to finite positive measures as we required that 1 belongs to F ). Note that there does not exist a convergence determining sequence for M ± (Z) as the weak topology is not metrizable on M ± (Z) (see Remark 2.6 below).

Remark 2.4 (The Borel σ-field on M ± (Z)). By [Bog18, Corollary 5.1.9], the Borel σ-field on M ± (Z), associated with the weak topology, is countably generated and can be generated by either:

• the family of maps µ → µ(f n ) where the sequence (f n ) n∈N of functions from C b (Z) is separating; • the family of maps µ → µ(B) where B ∈ A and the subset A ⊂ B(Z) is countable and generates the whole σ-field B(Z) (such subset A always exists, see [Bog07b, Corollary 6.7.5]). Note that the Borel σ-field of a Polish space is generated by any family of Borel functions that separates points (see [START_REF] Bogachev | Measure Theory[END_REF]Theorem 6.8.9]).

Furthermore, the maps µ → µ + and µ → µ -(and thus also µ → |µ|) are measurable (see [DF64, Theorem 2.8] and Remark 2.4). As a consequence, the map µ → µ ∞ is also measurable (in fact it is even lower semicontinuous by [Bog18, Theorem 2.7.4]). Note that M 1 (Z) and M + (Z) are closed, and thus measurable, subsets of M ± (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 M ⊂ M ± (Z) be a subset of signed measures.

(i) The set M is bounded (in total variation) if:

sup µ∈M µ ∞ < +∞.
(ii) The set M is tight if for all ε > 0, there exists a compact set K ⊂ Z such that:

sup µ∈M |µ|(K c ) ≤ ε.
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 [START_REF] Veeravalli | Weak convergence of measures on separable metric spaces[END_REF]Theorem 4.1]), which happens only when the initial space Z is finite (see [Bog18, Proposition 3.1.8]). Moreover, the closed norm ball {µ ∈ M ± (Z) : µ ∞ ≤ 1} of M ± (Z) is metrizable if and only if Z is compact (see [Bog18, Proposition 3.1.8 and Theorem 3.1.9]).

Let M ⊂ M ± (Z). The following properties are equivalent (see [Bog18, Theorems 2.3.4 and 3.1.9]):

(i) M is weakly compact (i.e. M is compact for the weak topology);

(ii) M is sequentially weakly compact (that is every sequence (µ n ) n∈N in M has a subsequence that converges to some limit µ ∈ M); (iii) 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, M is tight, bounded, and metrizable in the weak topology. Furthermore, the Kantorovitch-Rubinstein and Fortet-Mouriet norms • KR and • FM (defined in Section 3.8.2) can be used to generate the weak topology on a weakly compact set (see [Bog18, Remark 3.2.5]).

Nevertheless, the weak topology on the unit sphere {µ ∈ M ± (Z) : µ ∞ = 1} of M ± (Z) is always metrizable with a complete metric, making the unit sphere a Polish space, however, the Kantorovitch-Rubinstein and Fortet-Mouriet norms • KR and • FM do not provide a complete metrization in this case (see [Bog18, Theorem 3.2.8]).

Remark 2.7 (On the compactness of M 1 (Z)). Let M be either M 1 (Z), M ≤1 (Z) or the closed norm ball {µ ∈ M ± (Z) : µ ∞ ≤ 1} of M ± (Z). Then, M is weakly compact if and only if Z is compact.

We give a short proof of this statement. As M 1 (Z) is closed in M ± (Z) for the weak topology, if M is weakly compact, then M 1 (Z) is also weakly compact, and thus Z is compact by [START_REF] Veeravalli | Weak convergence of measures on separable metric spaces[END_REF]Theorem 3.4]. Conversely, if Z is compact, then by [Bog18, Theorem 1.3.3], we know that M ± (Z) (endowed with the weak topology) is the topological dual space of C b (Z) (endowed with the uniform convergence topology), thus using Banach-Alaoglu theorem (see [Bog18, Theorem 1.3.6]), we get that the closed unit norm-ball of M ± (Z), and thus M, are compact for the weak topology.

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

Lemma 2.8 (Prohorov's theorem for signed measures, [Bog18, Theorems 2.3.4 and 3.1.9]). Let Z be a Polish space, and let M ⊂ M ± (Z) be a subset of signed measures on Z. Then the following conditions are equivalent:

(i) M is relatively sequentially compact, that is every sequence (µ n ) n∈N in M contains a subsequence which weakly converges in M ± (Z). (ii) M is relatively compact for the weak topology, that is the closure of M is compact for the weak topology. (iii) The family 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 M ± (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 M ± (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 M ± (Z).

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

(i) Remind 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)) * = M ± (Z) (see [Bog18, Theorem 1.3.3]). Thus, using [HS96, Theorem 2.5], we get the existence of a countable subset which is weak sequentially closed yet weak dense in M ± (Z). In particular, the weak sequential topology and the weak topology do not coincide on M ± (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 [Bog18, Remark 3.1.7], the weak topology on M ± (F ) for a closed subset F coincides with the trace of the weak topology on the whole space. By [Bog18, Section 3.1, p. 102], M ± (F ) is homeomorphic to ℓ 1 both endowed with their weak topology, weak convergence on ℓ 1 is equivalent to norm convergence, and the weak topology on ℓ 1 is not sequential, even on the unit norm ball. Hence, the weak topology on M ± (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 ∈ X and all α ∈ [0, 1], we have:

d(αx 1 + (1 -α)x 2 , αy 1 + (1 -α)y 2 ) ≤ 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.

Lemma 2.11. Let d m be distance on M ǫ (Z) with ǫ ∈ {+, ±} which is quasi-convex and sequentially continuous with respect to the weak topology. Then, d m is uniformly continuous with respect to • ∞ on M ǫ (Z).

Proof. We shall simply consider the case M = M + (Z), the other case being simpler. We first check that for all µ ∈ M and ε > 0, there exists η > 0 such that for all ν ∈ M, we have that µν ∞ < η implies d m (µ, ν) < ε. As d m is sequentially continuous w.r.t. the weak topology, it is also (sequentially) continuous w.r.t. the strong topology. Let µ ∈ M and ε > 0. Then, the set {ν ∈ M : d m (µ, ν) < ε} is an open set of M containing µ both for d m and for the strong topology. Thus, it contains a neighborhood of µ for the strong topology {ν ∈ M : µ-ν ∞ < η} for η > 0 small enough. This proves the claim.

As d m is quasi-convex and M is a cone, for µ, ν ∈ M we have:

d m (µ, µ + ν) = d m 1 2 • (2µ + 0), 1 2 • (2µ + 2ν) ≤ max(d m (2µ, 2µ), d m (0, 2ν)) = d m (0, 2ν).
Let ε > 0 be fixed. We choose η ∈ (0, 1) such that

ν ∞ < η, with ν ∈ M, implies d m (0, ν) < ε. Let µ, ν ∈ M be such that µ -ν ∞ < η/2. Let λ ′ = µ + ν and f (resp. g) the density of µ (resp. ν) with respect to λ ′ . We set π = min(f, g) λ ′ , µ ′ = (f -g) + λ ′ and ν ′ = (f -g) -λ ′ so that π, µ ′ , ν ′ ∈ M, µ = π + µ ′ and ν = π + ν ′ . Since µ ′ -ν ′ = µ -ν
and µ ′ and ν ′ are mutually singular, we deduce that µ ′ ∞ + ν ′ ∞ < η/2. We get:

d m (µ, ν) = d m (π + µ ′ , π + ν ′ ) ≤ d m (π, π + µ ′ ) + d m (π, π + ν ′ ) ≤ d m (0, 2µ ′ ) + d m (0, 2ν ′ ) ≤ 2ε.
Hence, the distance d m is uniformly continuous with respect to • ∞ on M.

Measured-valued graphons and the cut distance

In Section 3.1, we introduce the measure-valued graphons, which are a generalization of realvalued graphons (i.e. [0, 1]-valued measurable functions defined on [0, 1] 2 ). We refer to the monography [START_REF] Lovász | Large networks and graph limits[END_REF] on real-valued graphons for more details. In Sections 3.2, 3.3 and 3.4, we introduce the cut distance, and its unlabeled variant, on the space of measure-valued graphons which are analogous to the ones for real-valued graphons (see [START_REF] Lovász | Large networks and graph limits[END_REF]Chapter 8]). In Section 3.5, we define a weak isomorphism relation for measure-valued graphons based on this distance. 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 Z is a Polish space and M ± (Z) is the space of finite signed measures.

Definition 3.1 (Signed measure-valued kernels). A signed measure-valued kernel or M ± (Z)- valued kernel is a map W from [0, 1] 2 to M ± (Z), such that: (i) W is a signed-measure in dz: for every (x, y) ∈ [0, 1] 2 , W (x, y; •) belongs to M ± (Z). (ii) W is measurable in (x, y): for every measurable set A ⊂ Z, the function (x, y) → W (x, y; A) defined on [0, 1] 2 is measurable. (iii) W is bounded: (2) W ∞ := sup x,y∈[0,1] W (x, y; •) ∞ < +∞.
We denote by W 1 (resp. W ≤1 , resp. W + , resp. W ± ) the space of probability measurevalued 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, (2) 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 ∞ is also the essential supremum of (x, y) → W (x, y; •) ∞ .

For M ⊂ M ± (Z), we denote by W M the subset of signed measure-valued kernel W ∈ W ± which are M-valued: W (x, y; •) ∈ M for every (x, y) ∈ [0, 1] 2 . Remark 3.2 (On real-valued kernels). Let 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 ∈ [0, 1] by W (x, y; dz) = w(x, y)δ 1 (dz) + (1w(x, y))δ 0 (dz), where δ z is the Dirac mass located at z. In particular we have that w(x, y) = W (x, y; {1}) for x, y ∈ [0, 1].

Let W ∈ W ± be a signed measure-valued kernel. Define the map W + : [0, 1] 2 → M + (Z) to be the positive part of W , i.e. for every (x, y) ∈ [0, 1] 2 , W + (x, y; •) is the positive part of the measure W (x, y; •). Similarly define W -: [0, 1] 2 → M + (Z) the negative part of W ; and then define |W | = W + + W -the total variation of W and W = |W |(Z) the total mass of W .

Lemma 3.3 (The positive part W + of a kernel). The maps W + , W -and |W | are all measurevalued kernels, and the map W : (x, y) → W (x, y; •) ∞ 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) ∈ [0, 1] 2 , W + (x, y; •) is a measure in M + (Z). Thus, we are left to prove the measurability of W + in (x, y). By [DF64, Proposition 2.1] and Remark 2.4, a signed measure-valued kernel U is measurable in (x, y) (i.e. for every A ∈ B(Z), the map (x, y) → U (x, y; A) is measurable) if and only if the map (x, y) → U (x, y; •) is measurable from [0, 1] 2 (with its Borel σ-field) to M ± (Z) equipped with the Borel σ-field generated by the weak topology. By [DF64, Theorem 2.8], the map µ → µ + , that associate to a signed measure the positive part of its Hahn-Jordan decomposition, is measurable from M ± (Z) to M + (Z) both endowed with the Borel σ-field generated by the weak topology. Considering the composition of W and µ → µ + , we get that W + is measurable in (x, y) and is thus a measure-valued kernel.

Remark 3.4 (Probability-graphons W : Ω × Ω → M 1 (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 (Ω, A, π) that might be more appropriate to represent vertex-types for some applications, and to consider probability-graphons of the form W : Ω × Ω → M 1 (Z). We recall that a standard probability space (Ω, A, π) is a probability space such that there exists a measure-preserving map ϕ : [0, 1] → Ω, where [0, 1] is endowed with the Borel σ-field and the Lebesgue measure. In particular, every Polish space endowed with its Borel σ-field is a standard probability space. As an example, the space [0, 1] 2 equipped with the Borel σ-field and the Lebesgue measure λ 2 is a standard probability space; we will reuse this fact later.

Using the measure preserving map ϕ, it is then possible to consider an unlabeled version W ϕ of W constructed on Ω ′ = [0, 1], and to modify the definition of the cut distance δ ,m similarly as in [Jan13, Theorem 6.9] to allow each probability-graphons 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 Ω = [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 ∈ [0, 1], W (x, y; •) = W (y, x; •).

We define stepfunctions measure-valued kernel which are often used for approximation. Definition 3.6 (Signed measure-valued stepfunctions). A signed measure-valued kernel W ∈ W ± is a stepfunction if there exists a finite partition of [0, 1] into measurable (possibly empty) sets, say P = {S 1 , • • • , S k }, such that W is constant on the sets S i × S j , for 1 ≤ i, j ≤ k. We say that W and the partition P are adapted to each other. We write |P| = k the number of elements of the partition P.

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 [START_REF] Lovász | Large networks and graph limits[END_REF]Chapter 8]. For a signed measure-valued kernel W ∈ W ± and a measurable subsets A ⊂ [0, 1] 2 , we denote by W (A; •) the signed measure on Z defined by:

W (A; •) = A W (x, y; •) dxdy.
Definition 3.7 (The cut distance d ,m ). Let d m be a quasi-convex distance on M a convex subset of M ± (Z) containing the zero measure. The associated cut distance d ,m is the function defined on W 2 M by:

(3) d ,m (U, W ) = sup S,T ⊂[0,1] d m U (S × T ; •), W (S × T ; •) ,
where the supremum is taken over all measurable subsets S and T of [0, 1].

Notice that the right-hand side of (3) is well defined as M contains the zero measure (and thus if U belongs to W M then U (A; •) belongs to M). Definition 3.8 (The cut norm N ,m ). The cut norm N ,m associated with a norm N m on M ± (Z) is the function defined on W ± by:

N ,m (W ) = sup S,T ⊂[0,1] N m W (S × T ; •) ,
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 M + (Z) and M ± (Z) is immediate.

Proposition 3.9 (d ,m is a distance, N ,m is a norm). The cut distance d ,m associated with a distance d m on M ≤1 (Z) (resp. M + (Z)) is a distance on W 1 (resp. W + ). The cut norm N ,m associated with a norm N m on M ± (Z) is a norm on W ± .
Moreover, when the distance d m on M ≤1 (Z) (resp. M + (Z)) derives from a norm N m on M ± (Z), then the distance d ,m derives also from the norm N ,m .

Proof. Let d m be a distance on M ≤1 (Z) (the proof for the case M + (Z) is similar). It is clear that d ,m is symmetric and satisfies the triangular inequality. Thus, we only need to prove that d ,m is separating. Let U and W be two probability-graphons such that d ,m (U, W ) = 0. Then, for every measurable subsets S, T ⊂ [0, 1], we have U (S × T ; •) = W (S × T ; •). Let F = (f k ) k∈N be a separating sequence. For every k ∈ N, and for every measurable subsets S, T ⊂ [0, 1], we have that U (S × T ; f k ) = W (S × T ; f k ). This implies that U (x, y, f k ) dxdy = W (x, y, f k ) dxdy for all k ∈ N. Hence, we deduce that for all k ∈ N, U (x, y; f k ) = W (x, y; f k ) for almost every (x, y) ∈ [0, 1] 2 . Thus, U (x, y; •) = W (x, y; •) for almost every (x, y) ∈ [0, 1] 2 . This implies that d ,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 measurepreserving map from Section 2, and in particular (1). Recall S[0,1] denotes the set of measurepreserving (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 ϕ, is the signed measure-valued kernel W ϕ defined for every x, y ∈ [0, 1] and every measurable set A ⊂ Z by: W ϕ (x, y; A) = W (ϕ(x), ϕ(y); A) for x, y ∈ [0, 1] and A ⊂ Z measurable.

We say that a subset K ⊂ W ± is uniformly bounded if:

(4) sup

W ∈K W ∞ < +∞.
Definition 3.10 (Invariance and smoothness of a distance on kernels). Let d be a distance on W 1 (resp. W + or W ± ). We say that the distance d is:

(i) Invariant: if d(U, W ) = d(U ϕ , W ϕ ) for every bijective measure-preserving map ϕ ∈ S [0,1] and U, V ∈ W 1 (resp. U, V belongs to W + or W ± ). (ii) Smooth: if a.e. weak convergence implies convergence for d, that is, if (W n ) n∈N and W
are kernels from W 1 (resp. kernels from W + or W ± that are uniformly bounded and) such that for a.e. (x, y)

∈ [0, 1] 2 , W n (x, y; •) weakly converges to W (x, y; •) as n → ∞, then lim n→∞ d(W n , W ) = 0.
We say that a norm

N on W ± is invariant (resp. smooth) if its associated distance d on W ± is invariant (resp. smooth).
We shall see in Section 3.8 some examples of distances d m for which the associated cut distance d ,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 ,m is invariant). Let d m be a distance on M ≤1 (Z) (resp. M + (Z), resp. M ± (Z)). Then the cut distance d ,m on W 1 (resp. W + , resp. W ± ) is invariant.
Proof. For a signed measure-valued kernel W , a bijective measure-preserving map ϕ ∈ S [0,1] , and measurable sets S, T ⊂ [0, 1], we have thanks to (1):

S×T W ϕ (x, y; •) dxdy = S×T W (ϕ(x), ϕ(y); •) dxdy = ϕ(S)×ϕ(T ) W (x, y; •) dxdy.
Hence, taking the supremum over every measurable sets S, T ⊂ [0, 1], we get that the cut distance d ,m is invariant.

When a smooth distance on W 1 or W + derives from a distance on M 1 (Z) or M + (Z), we have the following result. Lemma 3.12 (Smoothness and the weak topology). Let d m be a distance on

M ≤1 (Z) (resp. M + (Z) or M ± (Z)) such that the distance d ,m on W 1 (resp. W + or W ± ) is smooth. Then, the distance d m is continuous w.r.t. the weak topology on M 1 (Z) (resp. M + (Z)).
Proof. Let (µ n ) n∈N , and µ be measures from M 1 (Z) (resp. M + (Z)) such that (µ n ) n∈N weakly converges to µ. Consider the constant measure-valued graphons (resp. kernels) W n ≡ µ n , n ∈ N, and W ≡ µ. Then, for every x, y

∈ [0, 1], W n (x, y; •) weakly converges to W (x, y; •) as n → ∞. As the distance d ,m is smooth, we get that lim n→∞ d ,m (W n , W ) = 0. Considering S = T = [0, 1] in the cut distance, we deduce that lim n→∞ d m (µ n , µ) = 0.
The next lemma is a partial converse of Lemma 3.12, it gives sufficient conditions for d ,m to be smooth. Remind the definition of a quasi-convex distance in Definition 2.10. Proposition 3.13 (d ,m is smooth). Let d m be distance on M ǫ (Z) with ǫ ∈ {+, ±} which is quasi-convex and sequentially continuous w.r.t. the weak topology (on M ǫ (Z)). Then, the cut distance d ,m is smooth.

Moreover, for all U, W ∈ W ǫ , and for all measurable A ⊂ [0, 1] 2 , we have:

(5) d m (U (A; •), W (A; •)) ≤ essup (x,y)∈A d m (U (x, y; •), W (x, y; •)).
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 ∈ W ± and a subset A ⊂ [0, 1] 2 . There exists a sequence (W n ) n∈N in W ± such that (W n (A; •)) n∈N weakly converges to W (A; •) and for all n ∈ N, W n is finitely valued and takes its values in {W (x, y; •) : (x, y) ∈ A}.
Proof. By scaling, we may assume that W ∞ ≤ 1. Let (f k ) k∈N be a convergence determining sequence with f 0 = 1 and f k takes values in [0, 1]. Thus, for all (x, y)

∈ [0, 1] 2 , ǫ ∈ {±1} and k ∈ N, we have W ǫ (x, y; f k ) ∈ [0, 1]. For all n ∈ N, let (C n,i ) 1≤i≤dn 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 ∈ N and i ∈ [d n ], define B n,i = A ∩ (W + (•; (f i ) 0≤i≤n , W -(•; (f i ) 0≤i≤n ) -1 (C n,i ); thus we get a partition (B n,i ) 1≤i≤dn of A. If B n,i = ∅, fix some µ n,i ∈ {W (x, y; •) : (x, y) ∈ B n,i }. If A = [0, 1] 2 , fix some µ ∂ ∈ {W (x, y; •) : (x, y) ∈ [0, 1] 2 \ A}. For n ∈ N, we define W n = 1 A c µ ∂ + dn i=1 1 Bn,i µ n,i ,
which is finitely valued and takes its values in {W (x, y; •) : (x, y) ∈ A}.

Let k ∈ N and ǫ ∈ {±}. For all n ≥ k, we have:

|W ǫ (A; f k ) -(W n ) ǫ (A; f k )| ≤ dn i=1 Bn,i |W ǫ (x, y; f k ) -(µ n,i ) ǫ | dxdy ≤ 1 n • As (f k ) k∈N is convergence determining, this implies that ((W n ) ǫ (A; •)) n∈N weakly converges to W ǫ (A; •) for ǫ ∈ {±}. Hence, (W n (A; •)) n∈N weakly converges to W (A; •).
Proof of Proposition 3.13. As d m is quasi-convex, (5) is immediate when U and W take only finitely many values. Now, assume that U and W are arbitrary M ǫ (Z)-valued kernels. Let ε > 0. As d m is sequentially continuous w.r.t. the weak topology, using Lemma 3.14, there exist two M ǫ (Z)-valued kernel U ′ and W ′ such that d m (U ′ (A; •), U (A•)) < ε and U ′ is finitely valued and takes its values in {U (x, y; •) : (x, y) ∈ A}, and similarly for W ′ and W . Thus, we have:

d m (U (A; •), W (A; •)) ≤ 2ε + essup (x,y)∈A d m (U (x, y; •), W (x, y; •)),
and this being true for all ε > 0, we get (5).

Let (W n ) n∈N and W be M ǫ (Z)-valued kernels which are uniformly bounded by some constant C < ∞ and such that for a.e. (x, y) ∈ [0, 1] 2 , the sequence ((W n (x, y; •)) n∈N converges to W (x, y; •) for the weak topology, and thus also for d m . Let ε > 0 and S, T ⊂ [0, 1]. As d m is quasi-convex and sequentially continuous w.r.t. the weak topology, using Lemma 2.11, there exists η > 0 such that for all µ, ν ∈ M ǫ (Z), we have that µν ∞ < η implies d m (µ, ν) < ε. For all n ∈ N, define the measurable set:

A n = {(x, y) ∈ S × T : d m (W n (x, y; •), W (x, y; •)) < ε}.
By assumption, we have that lim n→∞ λ(

A n ) = λ(S × T ). Let N ∈ N be such that for n ≥ N , we have λ((S × T ) \ A n ) < η/C. Let n ≥ N . Remark that W n ((S × T ) \ A n ; •) and W ((S × T ) \ A n ; •) have total mass at most Cλ(A c n ) < η. Thus, we have that d m (W n (A n ; •), W n (S × T ; •)) < ε and d m (W (A n ; •), W (S × T ; •)) < ε.
Hence, using (5) we get that:

d m (W n (S × T ; •), W (S × T ; •)) ≤ 2ε + d m (W n (A n ; •), W (A n ; •)) ≤ 2ε + essup (x,y)∈An d m (W n (x, y; •), W (x, y; •)) ≤ 3ε.
Taking the supremum over S, T ⊂ [0, 1], we get d ,m (W n , W ) ≤ 3ε. This being true for all ε > 0, we conclude that (W n ) n∈N converges to W for d ,m , and thus d ,m is smooth.

The unlabeled cut distance.

We can now define the cut distance for unlabeled graphons.

Definition 3.15 (The unlabeled cut distance δ ,m ). Set K ∈ {W 1 , W + , W ± }. Let d be an invariant distance on the kernel space K. The premetric δ on K, also called the cut distance, is defined by:

(6) δ (U, W ) = inf ϕ∈S [0,1] d(U, W ϕ ) = inf ϕ∈S [0,1] d (U ϕ , W ) .
Notice that δ satisfies the symmetry property (as d is invariant) and the triangular inequality. Hence, δ induces a distance (that we still denote by δ ) on the quotient space

K d = K/ ∼ d of kernels in K associated with the equivalence relation ∼ d defined by U ∼ d W if and only if δ (U, W ) = 0. When the metric d = d ,m on K = W 1 (resp. W + , resp. W ± ) derives from a metric d m on M ≤1 (Z) (resp. M + (Z), resp. M ± (Z))
, and is thus invariant thanks to Lemma 3.11, we write δ ,m for δ and K m for K d ,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 M ≤1 (Z), lead to the same quotient space, then simply denoted by W 1 , with the same topology.

3.5. Weak isomorphism. Similarly to Theorem 8.13 in [START_REF] Lovász | Large networks and graph limits[END_REF], when the distance d m is such that d ,m is invariant and smooth, we can rewrite the cut distance δ ,m as a minimum instead of an infimum using measure-preserving maps, see the last equality in (7).

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 ∼ W ) if there exists two measure-preserving maps

ϕ, ψ ∈ S[0,1] such that U ϕ (x, y; •) = W ψ (x, y; •) for a.e. x, y ∈ [0, 1].
We denote by W ± = W ± / ∼ (resp. W 1 = W 1 / ∼) the space of unlabeled signed measurevalued kernels (resp. probability-graphons) i.e. the space of signed measure-valued kernels (resp. probability-graphons) where we identify signed measure-valued kernels (resp. probability-graphons) that are weakly isomorphic.

Notice that U ∼ W implies that U ∞ = W ∞ (we recall that signed measure-valued kernels are only defined for a.e. x, y ∈ [0, 1] and that W ∞ in (2) is an essup in general). In particular, the notion of uniformly bounded subset defined in (4) naturally extends to W ± . The last part of this section is devoted to the proof of the following key result. Theorem 3.17 (Weak isomorphism and δ ). Let d be a distance defined on W 1 (resp. W + or W ± ) which is invariant and smooth. Then, two kernels are weakly isomorphic, i.e. U ∼ W , if and only if

U ∼ d W , i.e. δ (U, W ) = 0. Furthermore, the map δ is a distance on W 1 = W 1,d (resp. W + = W +,d or W ± = W ±,d ).
As a first step in the proof of Theorem 3.17, following [START_REF] Lovász | Large networks and graph limits[END_REF], we give a nice description of δ using couplings. We say that a measure µ 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 components τ, ρ : [0, 1] 2 → [0, 1] (where [0, 1] 2 is equipped with the measure µ and [0, 1] with the Lebesgue measure λ) are measure-preserving. Thus for every kernel W on ([0, 1], B([0, 1]), λ), the function W τ is a kernel on the probability space ([0, 1] 2 , B([0, 1] 2 ), µ), and similarly for the projection ρ.

Let ϕ be a given measure-preserving map from [0, 1] with the Lebesgue measure to [0, 1] 2 with a coupling measure µ. For an invariant distance d on W 1 (resp. W ± ), we define a distance, say d µ , on kernels on ([0, 1] 2 , B([0, 1] 2 ), µ) by:

d µ (U ′ , W ′ ) = d(U ′ϕ , W ′ϕ ).
It is easy to see that, for U and W kernels on [0, 1], we have

d µ (U τ , W τ ) = d(U, W ) as d is invariant and τ • ϕ is a measure-preserving map from [0, 1] to itself; and similarly d µ (U ρ , W ρ ) = d(U, W ).
A straightforward adaptation of the proof of [Lov12, Theorem 8.13] gives the next result.

Proposition 3.18 (Minima in the cut distance δ ). Let d be a distance defined on W 1 (resp. W + or W ± ) which is invariant and smooth. Then, we have the following alternative formulations for the cut distance δ on W 1 (resp. W + or W ± ):

(7) δ (U, W ) = inf ϕ∈S [0,1] d(U, W ϕ ) = inf ϕ∈ S[0,1] d(U, W ϕ ) = inf ψ∈S [0,1] d(U ψ , W ) = inf ψ∈ S[0,1] d(U ψ , W ) = inf ϕ,ψ∈S [0,1] d(U ψ , W ϕ ) = min ϕ,ψ∈ S[0,1] d(U ψ , W ϕ ), and
δ (U, W ) = min µ d µ (U τ , W ρ )
where µ range over all coupling measures on [0, 1] 2 .

Proof of Theorem 3.17. We deduce from the last equality in (7) that δ (U, W ) = 0 if and only if there exist measure-preserving maps ϕ, ψ ∈ S[0,1] such that U ψ (x, y; •) = W ϕ (x, y; •) for a.e.

x, y ∈ [0, 1]. This gives that the equivalence relations ∼ d and ∼ are the same.

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 P, denote by σ(P) the σ-field generated by P.

Lemma 3.19 (Combinatorial optimization of quasi-convex d m for stepfunctions). Let d m be a quasi-convex distance on M a convex subset of M ± (Z) containing the zero measure. Let U, W ∈ W M be M-valued stepfunctions adapted to the same finite partition P. Then, there exists S, T ∈ σ(P) such that:

d ,m (U, W ) = d m (U (S × T ; •), W (S × T ; •)). Proof. Let P = {S 1 , . . . , S k } with k = |P| the size of the partition P. First, remark that the quantity d ,m (U, W ) = d m (U (S ′ × T ′ ; •), W (S ′ × T ′ ; •)) depends on S ′ and T ′ only through the values of λ(S ′ ∩ S i ) and λ(T ′ ∩ S i ) for 1 ≤ i ≤ k.
Thus, the cut distance between U and W can be reformulated as:

d ,m (U, W ) = sup 0≤αi,βi≤λ(Si); 1≤i≤k d m   1≤i,j≤k α i β j µ i,j (•), 1≤i,j≤k α i β j ν i,j (•)   ,
where µ i,j (resp. ν i,j ) is the constant value of U (x, y; •) (resp. W (x, y; •)) when x ∈ S i and y ∈ S j . Moreover, when we fix the value of β = (β i ) 1≤i≤k , the quantity

d m   1≤i,j≤k α i β j µ i,j (•), 1≤i,j≤k α i β j ν i,j (•)   is a quasi-convex function of α = (α i ) 1≤i≤k
, and thus realizes its maximum on the extremal points of the hypercube k i=1 [0, λ(S i )], i.e. when α i equals 0 or λ(S i ) for every 1 ≤ i ≤ k. By symmetry, a similar argument holds for β. The cut distance can thus be reformulated as the combinatorial optimization:

d ,m (U, W ) = max I,J⊂[k] d m   i∈I,j∈J µ i,j (•), i∈I,j∈J ν i,j (•)   .
Let I, J ⊂ [k] that maximizes this combinatorial optimization, and take S = ∪ i∈I S i and T = ∪ j∈J S j to conclude.

3.7.

The supremum in S and T in the cut distance d ,m . In this section, we prove that the supremum in the cut distance d ,m is achieved by some subsets S, T ⊂ [0, 1].

For W ∈ M ± (Z) and f, g : [0, 1] → [0, 1] measurable, we define the signed measure:

W (f ⊗ g; •) = [0,1] 2 W (x, y; •)f (x)g(y) dxdy. Remark that if we have W ∈ W ǫ with ǫ ∈ {1, ≤ 1, +, ±}, then we have W (f ⊗ g; •) ∈ M ǫ (Z).
Lemma 3.20 (The supremum in the cut distance d ,m for quasi-convex distance d m ). Let d m be a quasi-convex distance on M ǫ (Z) with ǫ ∈ {+, ±} that is sequentially continuous w.r.t. the weak topology. Let U, W ∈ W ǫ . Then, there exist measurable subsets S, T ⊂ [0, 1] such that f = 1 S and g = 1 T achieve the supremum in:

sup f,g d m U (f ⊗ g; •), W (f ⊗ g; •)
where the supremum is taken over measurable functions f, g from [0, 1] to itself.

Proof. Define the map Ψ :

(f, g) → d m (U (f ⊗ g; •), W (f ⊗ g; •)), and denote C = sup f,g Ψ(f, g),
where the supremum is taken over measurable functions f, g from [0, 1] to itself. Let (f n ) n∈N and (g n ) n∈N be sequences of measurable functions from [0, 1] to itself such that lim n→∞ Ψ(f n , g n ) = C. As the unit ball of L ∞ ([0, 1], λ) is compact for the weak- * topology (with primal space L 1 ([0, 1], λ)), upon taking subsequences, we may assume that (

f n ) n∈N (resp. (g n ) n∈N ) weak- * converges to some f (resp. g) which take values in [0, 1]. Thus, (f n ⊗ g n ) n∈N weak- * converges to f ⊗ g in L ∞ ([0, 1] 2 , λ 2 ). In particular, for every h ∈ C b (Z), as W [h] is a real-valued kernel, this implies that lim n→∞ W (f n ⊗ g n ; h) = W (f ⊗ g; h). This being true for every h ∈ C b (Z), we get that the sequence (W (f n ⊗ g n ; •)) n∈N in M ǫ (Z) weakly converges to W (f ⊗ g; •) ∈ M ǫ (Z);
and similarly for U . As d m is sequentially continuous w.r.t. the weak topology on M ǫ (Z), we get that C = lim n→∞ Ψ(f n , g n ) = Ψ(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≤f . Remark that we have

E[W (1 X≤f ⊗ g; •)] = W (f ⊗ g; •)
, and similarly for U . As d m is quasi-convex and sequentially continuous w.r.t. the weak topology, we have:

C ≥ sup x∈[0,1] d m (U (1 x≤f ⊗ g; •), W (1 x≤f ⊗ g; •)) ≥ d m E[U (1 X≤f ⊗ g; •)], E[W (1 X≤f ⊗ g; •)] = d m (U (f ⊗ g; •), W (f ⊗ g; •)) = C,
where in the second equality we used the quasi-convex supremum inequality from (5) with the

M ǫ (Z)-valued kernels U ′ (x, y; •) = U (1 x≤f ⊗ g; •) and W ′ (x, y; •) = W (1 x≤f ⊗ g; •)
, and A = [0, 1] 2 . All inequalities being equalities, this imposes:

C = sup x∈[0,1] d m (U (1 x≤f ⊗ g; •), W (1 x≤f ⊗ g; •)) = lim n→∞ d m (U (1 rn≤f ⊗ g; •), W (1 rn≤f ⊗ g; •)),
for some sequence (x n ) n∈N in [0, 1]. Upon taking a subsequence, we may assume that the sequence (x n ) n∈N monotonically converges to some x ∈ [0, 1]. In particular, the sequence of functions (1 xn≤f ) n∈N (monotonically) converges to the function

f ′ = 1 x≤f (resp. f ′ = 1 x<f ) if (x n ) n∈N
is non-decreasing (resp. decreasing), and thus also weak- * converges in L ∞ ([0, 1], λ). Using, as in the first part of the proof, the sequential continuity of the function Ψ w.r.t. the weak- * topology on

L ∞ ([0, 1], λ), we get that Ψ(f ′ , g) = d m (U (f ′ ⊗ g; •), W (f ′ ⊗ g; •)) = C,
that is we can replace f by the indicator function f ′ . The same argument allows to replace g by an indicator function.

3.8. Examples of distance d m . We consider usual distances and norms on M + (Z) or M ± (Z) that induce the weak topology on M + (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 ± (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 0 ) is a Polish metric space, and remind that B(Z) denotes its Borel σ-field.

3.8.1. The Prohorov distance d P . The Prohorov distance d P is a complete distance defined on the set of finite measures M + (Z) that induces the weak topology (see [Bil99, Theorem 6.8]). It is defined for µ, ν ∈ M + (Z) as:

(8) d P (µ, ν) = inf{ε > 0 : ∀A ∈ B(Z), µ(A) ≤ ν(A ε ) + ε and ν(A) ≤ µ(A ε ) + ε},
where A ε = {x ∈ Z : ∃y ∈ A, d 0 (x, y) < ε}. For probability measures, we only need one inequality in (8) to define the Prohorov 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 P , we use the subscript m = P. We now prove that the Prohorov distance is quasi-convex.

Lemma 3.21. The Prohorov distance d P is quasi-convex on M + (Z).

Proof. Let µ 1 , µ 2 , ν 1 , ν 2 ∈ M + (Z) and let α ∈ [0, 1]. Let ε > max(d P (µ 1 , ν 1 ), d P (µ 2 , ν 2 )), then for all i ∈ {1, 2} and B ∈ B(Z), we have that µ i (B) ≤ ν i (B ε ) + ε and ν i (B) ≤ µ i (B ε ) + ε.
Taking a linear combination of those inequalities, we get that for all B ∈ B(Z), we have that αµ

1 (B) + (1 -α)µ 2 (B) ≤ αν 1 (B ε ) + (1 -α)ν 2 (B ε ) + ε,
and similarly when swapping the role (µ 1 , µ 2 ) and (ν 1 , ν 2 ). Hence, we get that

d P (αµ 1 + (1 -α)µ 2 , αν 1 + (1 -α)ν 2 ) ≤ ε, and taking the infimum over ε, we get that d m (αµ 1 + (1 -α)µ 2 , αν 1 + (1 -α)ν 2 ) ≤ max(d m (µ 1 , ν 1 ), d m (µ 2 , ν 2 )).
3.8.2. The Kantorovitch-Rubinshtein and Fortet-Mourier norms. The Kantorovitch-Rubinshtein norm • KR (sometimes also called the bounded Lipschitz distance) and the Fortet-Mourier norm • FM are two norms defined on M ± (Z) that induce the weak topology on M + (Z) (see Section 3.2 in [START_REF] Bogachev | Weak Convergence of Measures[END_REF] for definition and properties of those norms). They are defined for µ ∈ M ± (Z) by:

µ KR = sup Z f dµ : f is 1-Lipschitz and f ∞ ≤ 1 , µ FM = sup Z f dµ : f is Lipschitz and f ∞ + Lip(f ) ≤ 1 , where f ∞ = sup x∈Z |f (x)| is the infinite 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 [START_REF] Bogachev | Weak Convergence of Measures[END_REF]:

(9) µ FM ≤ µ KR ≤ 2 µ FM .
Note that we have µ KR ≤ µ ∞ , and thus those two norms are sequentially continuous w.r.t. the weak topology on M ± (Z). An easy adaptation of the proof for Theorem 3.2.2 in [START_REF] Bogachev | Weak Convergence of Measures[END_REF] gives the following comparison between d P , • KR and • FM .

Lemma 3.22 (Comparison of d P , • KR and • FM ). Let µ, ν ∈ M + (Z)
. Then, we have:

d P (µ, ν) 2 1 + d P (µ, ν) ≤ µ -ν FM ≤ µ -ν KR ≤ 2 + min(µ(Z), ν(Z)) d P (µ, ν).
In particular, the Prohorov distance d P is uniformly continuous w.r.t. For the special choice N m = • KR (resp. N m = • FM ), we use the subscript m = KR (resp. m = FM).

3.8.3.

A norm based on a convergence determining sequence. From a convergence determining sequence F = (f k ) k∈N , where f 0 = 1 and f k ∈ C b (Z) takes values in [0, 1], we define a norm on M ± (Z) metrizing the weak topology on M + (Z), for µ ∈ M ± (Z), by: (10)

µ F = k∈N 2 -k |µ(f k )|.
Note that we have µ F ≤ 2 µ ∞ , and thus • F is sequentially continuous w.r.t. the weak topology on M ± (Z). For the special choice N m = • F , we use the subscript m = F . Even though the norm • F is not complete when Z is not compact (see Lemma 3.23 below), the cut norm • ,F and the cut distance δ ,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 F is the distance derived from the norm • F .

Lemma 3.23 (d F is not complete in general). Let F be a convergence determining sequence. Then, the distance d F is complete over M 1 (Z) if and only if M 1 (Z) is a compact space, i.e. , if and only if Z is compact.
Proof. Theorem 3.4 in [START_REF] Veeravalli | Weak convergence of measures on separable metric spaces[END_REF] states that Z is compact if and only if M 1 (Z) is compact. When this is the case, any distance metrizing the weak topology on M 1 (Z) is complete.

Reciprocally, assume that d F is a complete metric over M 1 (Z) and write F = (f m ) m∈N . Let (µ n ) n∈N be an arbitrary sequence of probability measures from M 1 (Z). For every m ∈ N, as f m takes values in [0, 1], we have for every n ∈ N that µ n (f m ) ∈ [0, 1]. Hence, using a diagonal extraction, there exists a subsequence (µ n k ) k∈N of the sequence (µ n ) n∈N such that for every m ∈ N, the sequence (µ n k (f m )) k∈N converges, that is, (µ n k ) k∈N is a Cauchy sequence for the distance d F . As we assumed the distance d F to be complete, this implies that the sequence (µ n ) n∈N has a convergent subsequence. The sequence (µ n ) n∈N being arbitrary, we conclude that the space M 1 (Z) is sequentially compact, and thus compact by Remark 2.6.

For W ∈ W ± and f ∈ C b (Z), we denote by W [f ] the real-valued kernel defined by:

(11) W [f ](x, y) = W (x, y; f ) = Z f (z) W (x, y; dz).
We denote by • ,R (resp. • + ,R ) the cut norm (resp. one-sided version of the cut norm) for real-valued kernels defined as:

(12) w ,R = sup S,T ⊂[0,1] S×T w(x, y) dxdy and w + ,R = sup S,T ⊂[0,1] S×T w(x, y) dxdy,
where w is a real-valued kernel w (see [Lov12, Section 8.2], resp. [Lov12, Section 10.3], for definition and properties of those objects).

The following two remarks link the cut norm • ,F of a signed measure-valued kernel W with the cut norm • ,R of the real-valued kernels W [f ] for some particular choices of functions f ∈ C b (Z). We will reuse those facts in Section 6. Remark 3.24 (Link between • ,F and • + ,R ). For µ ∈ M ± (Z) we have:

(13) µ F = sup ε∈{±1} N n∈N 2 -n ε n µ(f n ) = sup ε∈{±1} N µ n∈N 2 -n ε n f n , with ε = (ε n ) n∈N .
Hence, for a signed measure-valued kernel W ∈ W ± , we have:

(14) W ,F = sup ε∈{±1} N sup S,T ⊂[0,1] W S × T ; n∈N 2 -n ε n f n = sup ε∈{±1} N W n∈N 2 -n ε n f n + ,R
.

Remark 3.25 (Inequality with • ,F and • ,R ). For a signed measure-valued kernel W , we have:

W ,F = sup S,T ⊂[0,1] ∞ n=0 2 -n S×T W (x, y, f n ) dxdy ≤ ∞ n=0 2 -n sup S,T ⊂[0,1] S×T W (x, y, f n ) dxdy = ∞ n=0 2 -n W [f n ] ,R . (15)

Tightness and weak regularity

In this section, using a conditional expectation approach as in [Lov12, Chapter 9], we provide approximations of signed measure-valued kernels and probability-graphons by stepfunctions with an explicit bound on the quality of the approximation. This procedure takes into account that signed measure-valued kernels are infinite-dimensional valued.

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 ∈ W ± be a signed measure-valued kernel and

P = {S 1 , • • • , S k } be a finite partition of [0, 1].
We define the kernel stepfunction W P adapted to the partition P by averaging W over the partition subsets:

W P (x, y; •) = 1 λ(S i )λ(S j ) W (S i × S j ; •) for x ∈ S i , y ∈ S j ,
when λ(S i ) = 0 and λ(S j ) = 0, and W P (x, y; •) = 0 the null measure otherwise. We call the map W → W P defined on W ± the stepping operator (associated with the finite partition P).

Since the signed measure-valued kernel are defined up to an a.e. equivalence, the value of

W P (x, y; •) for x ∈ S i , y ∈ S j when λ(S i )λ(S j ) is unimportant.
Remark 4.2 (Link with conditional expectation). The stepfunction W P can be viewed as the conditional expectation of W w.r.t. the (finite) sigma-field σ(P ×P) on [0, 1] 2 , where W : [0, 1] 2 → M ± (Z) is seen as a random signed measure in M ± (Z) and the probability measure on [0, 1] 2 is the Lebesgue measure.

Remark 4.3 (Steppings are convex stable). Let M ⊂ M ± (Z) be a convex subset of measures, for instance M is M 1 (Z), M ≤1 (Z), M + (Z) or M ± (Z). Whenever W ∈ W ± is a M-valued
kernel, then by simple computation its stepping W P is also a M-valued kernel.

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

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

Indeed, assume that (P k ) k∈N separates points, and consider the countable family of Borelmeasurable functions F = {1 S : S ∈ P k , k ∈ N} which separates points. Thus, by [Bog07b, Theorem 6.8.9] (remark that a Polish space is a Souslin space, see [Bog07b, Definition 6.6.1]), the family F generates the Borel σ-field of [0, 1]. This implies that the family of Borel sets {S : S ∈ P k , k ∈ N} generates the Borel σ-field of [0, 1].

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

Recall the definition of the norm • ∞ on W ± defined in (2). The following lemma allows to approximate any signed measure-valued kernel by its steppings. Lemma 4.5 (Approximation using the stepping operator). Let W ∈ W ± be a signed measurevalued kernel (which is bounded by definition). Let (P n ) n∈N be a refining sequence of finite partitions of [0, 1] that generates the Borel σ-field on [0, 1]. Then, the sequence (W Pn ) n∈N is uniformly bounded by W ∞ , and weakly converges to W almost everywhere (on [0, 1] 2 ).

Proof. Set W n = W Pn for n ∈ N. By definition of the stepping operator, we have for every n ∈ N and every (x, y) ∈ [0, 1] 2 that the total mass of W n (x, y; •) is upper bounded by W ∞ .

Recall that for W ∈ W ± and f ∈ C b (Z), the real-valued kernel W [f ] is defined by (11). First assume that W ∈ W + . Let F = (f k ) k∈N be a convergence determining sequence, with by convention f 0 = 1. For every k ∈ N and n ∈ N, an immediate computation gives

W n [f k ] = (W [f k ]) Pn . For every k ∈ N, as W [f k ] is a real-valued
W n [f k ] = W [f k ]
almost everywhere, since (P n ) n∈N generates the Borel σfield. Hence, as the sequence (f k ) k∈N is convergence determining, the sequence (W n ) n∈N weakly converges to W almost everywhere. Now, for W ∈ W ± , write W = W + -W -where W + , W -∈ W + (see Lemma 3.3). By linearity of the stepping operator, remark that we have W n = (W + ) Pn -(W -) Pn for all n ∈ N. By the first case, we have that the sequence ((W + ) Pn ) n∈N weakly converges a.e. to W + , and similarly for ((W -) Pn ) n∈N and W -. Hence, the sequence (W n ) n∈N weakly converges to W almost everywhere.

We first provide a separability result on the space of probability-graphons.

Proposition 4.6 (Separability of W 1 and W 1 ). Let d be a smooth distance on W 1 (resp. W + or W ± ). Then, the space

(W 1 , d) (resp. (W + , d) or (W ± , d)) is separable. If furthermore d is invariant (which implies that δ is a distance), then the space ( W 1 , δ ) (resp. ( W + , δ ) or ( W ± , δ )) is separable.
Proof. We shall consider the space of probability-graphons W 1 , as the proofs for W + and W ± are similar. Applying Lemma 4.5 with the sequence of dyadic partitions, for every probabilitygraphon 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 [Bil99, Theorem 6.8]). Let A ⊂ M 1 (Z) be an at most countable dense (for the weak topology) subset. Then, for any stepfunction W ∈ 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 ∈ W 1 , there exists a sequence (W n ) n∈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.

Remind that by Theorem 3.17, when the distance d is invariant and smooth, then the premetric δ is a distance on W 1 . In that case, convergence for d implies convergence for δ , and thus the space ( W 1 , δ ) is also separable. 4.2. Tightness. Similarly to the case of signed measures (remind 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 ∈ W ± , we define the measure

M W ∈ M + (Z) by: (16) M W (dz) = |W |([0, 1] 2 ; dz) = [0,1] 2 |W |(x, y; dz) dxdy,
where for every x, y ∈ [0, 1], |W |(x, y; •) is the total variation of W (x, y; •) (see Lemma 3.3). In particular, if W is a probability-graphon then M W is a probability measure from M 1 (Z). Notice also that if W and U are weakly isomorphic, then M W = M U , so that the application W → M W can be seen as a map from W 1 (resp.

W ± ) to M 1 (Z) (resp. M + (Z)). Definition 4.7 (Tightness criterion). A subset K ⊂ W ± (resp. K ⊂ W ± ) is said to be tight if the subset of measures {M W : W ∈ K} ⊂ M + (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 W ± are discussed after Definition 3.16. Recall also λ 2 is the Lebesgue measure on [0, 1] 2 . Proposition 4.8 (Alternative tightness criterion). Let K ⊂ W ± (or K ⊂ W ± ) be a uniformly bounded subset of signed measure-valued kernels. The set K is tight if and only if for every ε > 0, there exists a compact set K ⊂ Z, such that for every W ∈ K we have:

(17) λ 2 {(x, y) ∈ [0, 1] 2 : |W |(x, y; K c ) ≤ ε} > 1 -ε.
Proof. As the left hand side of ( 17) is invariant by relabeling, it is enough to do the proof for W ± . Let K ⊂ W ± be uniformly bounded and set C = sup W ∈K W ∞ < ∞. Assume that for every ε > 0, there exists a compact set K ⊂ Z, such that (17) holds for every W ∈ K. Let 1 > ε > 0. Thus, there exists a compact subset K ⊂ Z such that for every W ∈ K there exists a subset A W ⊂ [0, 1] 2 with (Lebesgue) measure at least 1ε, such that for every (x, y) ∈ A W , we have |W |(x, y; K c ) ≤ ε. We have that for all W ∈ K:

M W (K c ) = [0,1] 2 |W |(x, y; K c ) dxdy ≤ W ∞ λ 2 (A c W ) + ελ 2 (A W ) ≤ (C + 1)ε.
Hence, the subset of measures

{M W : W ∈ K} ⊂ M + (Z) is tight, that is K is tight.
Conversely, suppose that K is tight. Let ε > 0. There exists a compact set K ⊂ Z such that for every W ∈ K, we have

M W (K c ) < ε 2 . For W ∈ K, define A W = {(x, y) ∈ [0, 1] 2 : |W |(x, y; K c ) ≤ ε}.
We have:

ε 2 > M W (K c ) = [0,1] 2 |W |(x, y; K c ) dxdy ≥ ελ 2 (A c W ).
Hence, λ 2 (A W ) > 1ε, and consequently Equation (17) holds.

We end this section on a continuity result of the map W → M W .

Lemma 4.9 (Regularity of the map

W → M W ). Let d m be a distance on M ≤1 (Z) (resp. M + (Z)). Then the map W → M W is 1-Lipschitz, and thus continuous, from ( W 1,m , δ ,m ) (resp. ( W +,m , δ ,m )) to (M 1 (Z), d m ) (resp. (M + (Z), d m )).
Proof.

Taking S = T = [0, 1] in Definition (3) of d ,m , we get that d m (M U , M W ) ≤ d ,m (W, U ).
As M U ϕ = M U for any measure-preserving map ϕ thanks to (1), we deduce from Definition (6) of δ ,m that d m (M U , M W ) ≤ δ ,m (U, W ).

Weak regularity.

We shall consider the following extra regularities of distances on the set of signed measure-valued kernels w.r.

C 0 > 0 such that for every W, U in W 1 (resp. in W + or W ± , with W ∞ ≤ C and U ∞ ≤ C)
and every finite partition P of [0, 1], then we have:

(18) d(W, W P ) ≤ C 0 d(W, U P ).
We say that a norm N on W ± is weakly regular (resp. regular w.r.t. the stepping operator) if its associated distance d on W ± is weakly regular (resp. regular w.r.t. the stepping operator).

The weak regularity property is an analogue to the weak regularity lemma for real-valued graphons (see [START_REF] Lovász | Large networks and graph limits[END_REF]Lemma 9.15]). If a distance d is weakly regular, then for a subset K ⊂ M ± (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. Remind 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 ,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 M a convex subset of M ± (Z) containing the zero measure. Then, the stepping operator associated with a given finite partition of [0, 1] is 1-Lipschitz on W M for the cut distance d ,m .

Proof. Let U, W ∈ W M be M-valued kernels, and let P be a finite measurable partition of [0, 1]. As U P and W 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 ∈ σ(P) that:

d ,m (U P , W P ) = d m (U P (S × T ; •), W P (S × T ; •)) = d m (U (S × T ; •), W (S × T ; •)) ≤ d ,m (U, W ),
where the second equality comes from the fact that the integrals are equals as S, T ∈ σ(P) and thus the integration is over full steps of the partition. Hence, the stepping operator is 1-Lipschitz on W M for the cut distance d m .

For a quasi-convex distance d m , the cut distance d ,m is regular w.r.t. the stepping operator with C 0 = 2 in (18) (and one can take C = +∞ in Definition 4.10 (ii)).

Lemma 4.12 (d ,m is regular w.r.t. the stepping operator). Let d m be a quasi-convex distance on M a convex subset of M ± (Z) containing the zero measure. Let W, U ∈ W ǫ be W M -valued kernels, and let P be a finite partition of [0, 1]. Then, we have:

d ,m (W, W P ) ≤ 2d ,m (W, U P ).
Proof. The proof is similar to the proof of [Lov12, Lemma 9.12]. As d m is quasi-convex, using Lemma 4.11, we get:

d ,m (W, W P ) ≤ d ,m (W, U P ) + d ,m (U P , W P ) ≤ 2d ,m (W, U 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 ǫ , with ε ∈ {+, ±}, being 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 ,m on W ǫ is invariant, smooth and regular w.r.t. the stepping operator. We are left to prove that d ,m is weakly regular on W ǫ . 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 ⊂ W ǫ be a subset of M ǫ (Z)-valued kernels that is tight and uniformly bounded by some finite constant C. Let M ⊂ M ǫ (Z) be the subset of elements of M ǫ (Z) with total mass at most C; in particular M is a convex set containing 0 and K ⊂ 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 ǫ (Z), we have that (M, d m ) is sequentially compact, and thus compact.

Denote by

B(µ, r) = {ν ∈ M : d m (µ, ν) < r} the open ball centered at µ ∈ M with radius r > 0. Let ε > 0. As M is compact, there exist µ 1 , . . . , µ n ∈ M, n ∈ N * , such that M = ∪ n i=1 B(µ i , ε). For 1 ≤ i ≤ n, define A i = B(µ i , ε) \ ∪ j<i B(µ j , ε
), so that {A 1 , . . . , A n } is a finite partition (with possibly some empty sets) of M.

Every M-valued kernel W can be approximated by a {µ 1 , . . . , µ n }-valued kernel U defined for every (x, y) ∈ [0, 1] 2 by U (x, y; •) = µ i for i such that W (x, y; •) ∈ A i . Thus, by construction, we have that for every (x, y) ∈ [0, 1] 2 , d m (W (x, y; •), U (x, y; •)) < ε. Applying the quasi-convex supremum inequality from (5) to W and U , we get that:

d ,m (W, U ) ≤ essup (x,y)∈[0,1] 2 d m (W (x, y; •), U (x, y; •)) ≤ ε.
Then, as the stepping operator is 1-Lipschitz for the cut norm, see Lemma 4.11, we have for any finite partition P of [0, 1] that:

d ,m (W, W P ) ≤ d ,m (W, U ) + d ,m (U, U P ) + d ,m (U P , W P ) ≤ 2ε + d ,m (U, U P ). (19)
Hence, to get the weak regularity property for M-valued kernels, we are left to prove it for the much smaller set of V-valued kernels, where V is the convex hull of {µ 1 , . . . , µ n }.

As d m is quasi-convex and sequentially continuous w.r.t. the weak topology, using Lemma 2.11, there exists η > 0 such that for all µ, ν ∈ M ǫ (Z), we have that µν ∞ < η implies that d m (µ, ν) ≤ ε.

As V is a subset of a vector space with finite dimension n, the norm

• ∞ seen over V is equivalent to the L 1 -norm µ = n i=1 α i µ i → α 1 = n i=1 |α i |.
We can now see V-valued kernel as R n -valued graphon with a cut norm derived from the L 1 -norm • 1 , and in this case the proof for the weak regularity Lemma 9.9 in [START_REF] Lovász | Large networks and graph limits[END_REF] can easily be adapted. Hence, we have the weak regularity property for V-valued kernels: there exists m ∈ N * , such that for every V-valued kernel U ′ , and for every finite partition Q of [0, 1] there exists a finite partition P of [0, 1] that refines Q, and such that |P| ≤ m|Q| and sup 19), we get that d ,m (W, W P ) ≤ 3ε and |P| ≤ m|Q|. This concludes the proof of the lemma when Z is compact.

S,T ⊂[0,1] (U ′ -U ′ P )(S × T ; •) ∞ < η, and thus d ,m (U ′ , U ′ P ) ≤ ε. Taking U ′ = U in (
Step 2. We consider the general case Z Polish. We now prove that d ,m is weakly regular on W ǫ . Let K ⊂ W ǫ be a subset of M ǫ (Z)-valued kernels that is tight and uniformly bounded, and denote by

C = sup W ∈K W ∞ < ∞.
Let ε > 0. As d m is quasi-convex and sequentially continuous w.r.t. the weak topology, using Lemma 2.11, there exists η > 0 such that for all µ, ν ∈ M ǫ (Z), we have that µ-ν ∞ < η implies that d m (µ, ν) < ε. Without loss of generality, we assume that η ≤ ε. Let η C = min(η, η/C).

As K is tight, using Proposition 4.8, there exists a compact set K ⊂ Z, such that for every

W ∈ K the subset A W = {(x, y) ∈ [0, 1] 2 : |W |(x, y; K c ) ≤ η C /2}
has Lebesgue measure at least 1η C /2. Let W ∈ K, and define the signed measure-valued kernel U by: U (x, y; •) = W (x, y; • ∩ K) for every (x, y) ∈ A W , and U (x, y; •) = 0 otherwise. Let S, T ⊂ [0, 1]. We have:

(W -U )(S × T ; •) ∞ ≤ S×T W (x, y; •) -U (x, y; •) ∞ dxdy ≤ AW ∩(S×T ) |W |(x, y; K c ) dxdy + A c W ∩(S×T ) W (x, y; •) ∞ dxdy ≤ η C /2 + C • η C /2 ≤ η. Thus, we have that d m (W (S × T ; •), U (S × T ; •)) < ε. Since this holds for all S, T ⊂ [0, 1], we get that d ,m (W, U ) ≤ ε.
Notice that the M ± (Z)-valued kernel U is also a M ± (K)-valued kernel, where K ⊂ Z is a compact set, and that U ∞ ≤ W ∞ ≤ C. Further remark that, using Lemma 4.11, for every W ∈ K and every finite partition P of [0, 1], we have that:

d ,m (W, W P ) ≤ d ,m (W, U ) + d ,m (U, U P ) + d ,m (U P , W P ) ≤ 2ε + d ,m (U, U P ).
Hence, to get the weak regularity property for d ,m on K (see Definition 4.10 (i)), it is enough to prove that d ,m restricted to M ǫ (K)-valued kernels is weakly regular, which is true by Step 1. As a consequence, we get that d ,m on W ǫ is weakly regular.

4.4.

A stronger weak regularity lemma for d ,F . In this subsection, we prove a stronger version of the weak regularity lemma for the special case of the cut distance d ,F . We shall use this result for the proof of the second sampling Lemma 6.12.

Let F = (f n ) n∈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.

Comparison between • ,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 • ,F is given by Lemma 4.15. We define the scalar product

•, • F on signed measure-valued kernels for U, W ∈ W ± by:

U, W F = n≥0 2 -n U [f n ], W [f n ] ,
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 , λ 2 ) for real-valued kernels:

U [f n ], W [f n ] = [0,1] 2 U [f n ](x, y)W [f n ](x, y) dxdy.
The scalar product •, • F induces a norm on W ± which we denote by • 2,F . Let 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 •, • F for signed measure-valued kernels, we have that the stepping operator for signed measure-valued kernels is linear, idempotent and symmetric for •, • F . Moreover, the stepping operator is the orthogonal projection for •, • F onto the space of stepfunctions with steps in P.

Note that for a probability-graphon W ∈ W 1 , we have W 2,F ≤ √ 2 as each f n takes values in [0, 1]. The following technical lemma gives a comparison between • ,F and • 2,F . Lemma 4.15 (Comparison between • ,F and • 2,F ). For a signed measure-valued kernel

W ∈ W ± , we have W ,F ≤ √ 2 W 2,F .
Proof. Let S, T ⊂ [0, 1] be measurable subsets. By the Cauchy-Schwarz inequality, we have

| W [f n ], 1 S×T | 2 ≤ W [f n ] 2 2 = W [f n ], W [f n ]
for every n ≥ 0. Using this inequality along with Jensen's inequality, we get for every S, T ⊂ [0, 1] that:

  n≥0 2 -n |W (S × T, f n )|   2 =   n≥0 2 -n | W [f n ], 1 S×T |   2 ≤ n≥0 2 -n+1 | W [f n ], 1 S×T | 2 ≤ n≥0 2 -n+1 W [f n ], W [f n ] = 2( W 2,F ) 2 .
Taking the supremum over every measurable subsets S, T ⊂ [0, 1] gives the desired inequality.

W -W P ,F ≤ √ 8 log(k) W 2,F .
In particular, if W ∈ W 1 is a probability-graphon, (as W 2,F ≤ √ 2) we have:

W -W P ,F ≤ 4 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 [Lov12, Lemma 9.15]. Lemma 4.17 (Weak regularity lemma for • ,F , with extra requirements). Let W ∈ W 1 be a probability-graphon, and let 1 ≤ m < k.

(i) For every partition Q of [0, 1] into m classes, there is a partition P with k classes refining Q and such that:

W -W P ,F ≤ 4 log(k/m) • (ii) For every partition Q of [0, 1] into m classes,
there is an equipartition (i.e. a finite partition into classes with the same measure) P of [0, 1] into k classes and such that:

W -W P ,F ≤ 2 W -W Q ,F + 2m k •

Compactness and completeness of W 1

In Section 5.1, we link the tightness criterion for measure-valued kernels with the relative compactness w.r.t. the cut distance δ ,m . In Section 5.2, we compare the topologies induced by the cut distance δ ,m for different choice of the distance d m , and state that under some conditions on d m , those topologies coincide. In Section 5.3, we investigate the completeness of W 1 endowed with the cut distance δ ,m and prove that the space of probability-graphons W 1 is a Polish space (Theorem 5.10), and that it is compact if and only if Z is compact (Corollary 5.13). The technical proofs are postponed to Section 8.

Tightness criterion and compactness.

Let M ⊂ M ± (Z) be a subset of signed measures on Z. Recall that W M ⊂ W ± denote the subset of signed measure-valued kernels which are M-valued. In this section, we shall denote by W M the quotient of W M identifying signed measure-valued kernels that are weakly isomorphic.

Remind from Definition 3.15 and Theorem 3.17 that for an invariant, smooth and weakly regular distance d on W 1 (resp. W + , W ± ), δ is defined as δ (U, W ) = inf ϕ∈S [0,1] d(U, W ϕ ), and is a distance on W 1 (resp. W + , W ± ).

We are now ready to formulate the important following 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 W 1 ). Let d be an invariant, smooth and weakly regular distance on W 1 (resp. W ± ).

(i) If a sequence of elements of W 1 or W 1 (resp. W ± or W ± ) is tight (resp. tight and uniformly bounded), then it has a subsequence converging for δ .

(ii) If M ⊂ M 1 (Z) (resp. M ⊂ M ± (Z)) is convex

and compact (resp. sequentially compact)

for the weak topology, then the space ( W M , δ ) is convex and compact. (iii) If Z is compact, then the space ( W 1 , δ ) is compact.

We deduce from this theorem a characterization of relative compactness for subsets of probabilitygraphons.

Proposition 5.2 (Characterization of relative compactness). Let d m be a distance on M ≤1 (Z) (resp. M + (Z) or M ± (Z)) that induces the weak topology on M ≤1 (Z) (resp. M + (Z)). Assume that the distance d ,m on W 1 (resp. W + or W ± ) is (invariant) smooth and weakly regular.

(i) If a sequence of elements of W 1 or W 1 (resp. W + or W + ) is converging for δ ,m , then it is tight. (ii) Let K be a subset of W 1 (resp. a uniformly bounded subset of W + ). Then, the set K is relatively compact for δ ,m if and only if it is tight. (iii) Let M be a subset of M + (Z) which is bounded, convex and closed for the weak topology.

Then the set W M is convex and closed in W + .

Remark that convergence for δ ,m does not necessarily imply tightness on W ± or on W ± .

Proof. We consider the case where d m is a distance on M + (Z) or M ± (Z), the case with M ≤1 (Z) is similar. We prove Point (i). Let (W n ) n∈N be a convergent sequence of W + (and thus of W + ) for δ ,m . We deduce from the continuity of the map W → M W , see Lemma 4.9, that the sequence (M Wn ) n∈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∈N is tight.

We prove Point (ii). If K ⊂ W + is tight and uniformly bounded, then by Theorem 5.1 (i) every sequence in K has a subsequence converging for δ ,m , which implies that K is relatively compact in the metric space ( W + , δ ,m ) (see Remark 2.1).

Conversely, assume that K ⊂ W + is uniformly bounded and relatively compact for δ ,m . Define M = {M W : W ∈ K} ⊂ M + (Z). By Lemma 4.9, the mapping W → M W is continuous from ( W 1 , δ ,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 ⊂ M + (Z) is tight, and by Definition 4.7, the set K ⊂ W + is tight.

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

Equivalence of topologies induced by δ ,m .

The following lemma allows to show a first result on equivalence of the topologies induced by the cut distance δ ,m for different distances d m , where the sub-script m is used to distinguish different distances. Its proof is given below. Remind from Theorem 3.17 that d ,m must be smooth for δ ,m to be a distance. (iv) Assume that the distance d m ′ induces the weak topology on M ≤1 (Z), and that the distance d ,m is smooth and weakly regular. In particular, the distance d m also induces the weak topology on M ≤1 (Z). Then, the distances δ ,m and δ ,m ′ induce the same topology on W 1 .

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

Remark 5.4 (Extension to W ± for topology comparisons). In Lemma 5.3 (i)-(iii), one can replace W 1 and W 1 by W + and W + or by W ± and W ± as soon as the distances d m and d m ′ are defined on M + (Z) or M ± (Z); in this case comparisons of topologies only apply on uniformly bounded subsets. In Lemma 5.3 (iv), one can replace W 1 by W M with a bounded subset M ⊂ M + (Z) as soon as the distances d m and d m ′ are defined on M + (Z).

Proof of Lemma 5.3. We prove Point (i). Let ε > 0. As d m ′ is uniformly continuous w.r.t. d m , there exists η > 0 such that for every µ, ν

∈ M ≤1 (Z), if d m (µ, ν) < η, then d m ′ (µ, ν) < ε. Let U, W ∈ W 1 such that d ,m (U, W ) < η.
Then, for every subsets S, T ⊂ [0, 1], we have:

d m ′ (U (S × T ; •), W (S × T ; •)) < ε. Thus, d ,m ′ (U, W ) ≤ ε. Hence, d ,m ′ is uniformly continuous w.r.t. d ,m .
We prove Point (ii). Assume that d ,m is smooth. Let (W n ) n∈N and W be probabilitygraphons such that W n (x, y; •) weakly converges to W (x, y; •) for almost every x, y ∈ [0, 1]. Since the cut distance d ,m is smooth, we get that d ,m (W n , W ) → 0. As d ,m ′ is uniformly continuous (and thus also continuous) w.r.t. d ,m , we have that d ,m ′ (W n , W ) → 0. Hence, d ,m ′ is smooth.

Furthermore, let ε > 0. Let η > 0 be such that for every µ, ν

∈ M ≤1 (Z), d m (µ, ν) < η implies d m ′ (µ, ν) < ε. For every U, W ∈ W 1 such that δ ,m (U, W ) < η, there exists ϕ ∈ S [0,1] such that d ,m (U, W ϕ ) < η, which implies that d ,m ′ (U, W ϕ ) < ε, which then implies that δ ,m ′ (U, W ) < ε. That is, δ ,m ′ is uniformly continuous w.r.t. δ ,m .
We prove Point (iii). Assume that d ,m is weakly regular. Let K ⊂ W 1 be tight. Let ε > 0. As d ,m ′ is uniformly continuous w.r.t. d ,m , there exists η > 0 such that for every U, W ∈ W 1 , if d ,m (U, W ) < η, then d ,m ′ (U, W ) < ε. Since d ,m is weakly regular, there exists m ∈ N * , such that for every probability-graphon W ∈ K, and for every finite partition Q of [0, 1], there exists a finite partition P of [0, 1] that refines Q and such that |P| ≤ m|Q| and d ,m (W, W P ) < η; and thus we also have d ,m ′ (W, W P ) < ε. Hence, d ,m ′ is weakly regular.

We prove Point (iv). Assume that d m ′ induces the weak topology on M ≤1 (Z) and that d ,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 ,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 ≤1 (Z). By Points (ii) and (iii), we get that d ,m ′ is also smooth and weakly regular. By Point (ii), the distance δ ,m induces a finer topology than δ ,m ′ on W 1 .

We now prove that the topology of δ ,m ′ is finer than the topology of δ ,m . Let (W n ) n∈N and W be probability-graphons in W 1 , such that W n converges to W for δ ,m ′ . By Proposition 5.2 (i), we deduce that the sequence (W n ) n∈N is tight. As d ,m is smooth and weakly regular, Theorem 5.1 gives that every subsequence (W n k ) k∈N of the sequence (W n ) n∈N has a further subsequence (W n ′ k ) k∈N that converges for δ ,m to a limit, say U ∈ W 1 . Since δ ,m is finer than δ ,m ′ , we deduce that (W n ′ k ) k∈N converges also to U for δ ,m ′ ; but, as a subsequence, it also converges to W for δ ,m ′ . As δ ,m ′ is a distance on W 1 thanks to Theorem 3.17, we get U = W . Hence, every subsequence of (W n ) n∈N has a further subsequence that converges to W for δ ,m , therefore the whole sequence itself converges to W for δ ,m . Consequently, δ ,m ′ is finer than δ ,m , and thus those two distances induce the same topology on W 1 .

The following theorem states that the topology induced by δ ,m does not depend on d m under some hypothesis. We prove this theorem in Section 8. Recall that under suitable conditions satisfied in the next theorem, the quotient space 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 δ ,m on W 1 ). The topology on the space probability-graphon W 1 induced by the distance δ ,m does not depend on the choice of the distance d m on M ≤1 (Z), as long as d m induces the weak topology on M ≤1 (Z) and the cut distance d ,m on W 1 is (invariant) smooth, weakly regular and regular w.r.t. the stepping operator.

Remind 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 ,m is invariant, smooth, weakly regular and regular w.r.t. the stepping operator. This is in particular the case of d P ,

• F , Remark 5.7 (Extension to uniformly bounded subsets of W + ). In Theorem 5.5 and also in Corollary 5.6 (iii), one can replace W 1 by W M with a bounded subset M ⊂ M + (Z) as soon as the distance d m is defined on M + (Z). (One has in mind the case M = M ≤1 (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 M to the case of M ≤1 (Z), and then adding a cemetery point (for missing mass of measures) to Z to further reduce to the case of M 1 (Z). ,m on the space of M ǫ (Z)-valued kernels W ǫ as:

d c ,m (U, W ) = d ,m (U, W ) + d c (M U , M W )

, and the cut (pseudo-)distance δ c

,m on the space of unlabeled M ǫ (Z)-valued kernels W ǫ as:

δ c ,m (U, W ) = inf ϕ∈S [0,1] d c ,m (U, W ϕ ) = δ ,m (U, W ) + d c (M U , M W ).
Notice that by Lemma 3.11 and the definition of M W , the distance d c ,m is invariant. Proof. Let (W n ) n∈N and W be elements of W ≤1 such that (W n (x, y; •)) n∈N weakly converges to W (x, y; •) for almost every x, y ∈ [0, 1]. Since the distance d ,m is smooth, we have that lim n→∞ d ,m (W n , W ) = 0. Using Lemma 4.9 on the continuity of the map W → M W and that d c is continuous w.r.t. d m , we obtain that lim n→∞ d c ,m (W n , W ) = 0. This gives that the distance d c ,m is smooth. Since we have already seen that d c ,m is invariant, we deduce from Theorem 3.17 that δ c ,m is a distance on W 1 . We now prove that the two distances d ,m and δ c ,m induce the same topology (which implies that this is also true for δ ,m and δ c ,m ). As d ,m ≤ d c ,m , convergence for d c ,m implies convergence for d ,m . Conversely, let (W n ) n∈N be a sequence in W ǫ that converges for d ,m to a limit, say W ∈ W ǫ . Using again Lemma 4.9 and the continuity of d c w.r.t. d m , we obtain that lim n→∞ d c (M Wn , M W ) = 0. This clearly implies that the sequence (W n ) n∈N converges to W for d c ,m . Then, the two distances have the same convergent sequences and thus induce the same topology (see Remark 2.1).

Recall Z is a Polish space. We already proved in Proposition 4.6 that the space ( W 1 , δ ,m ) is separable; and we now investigate completeness of this space.

Theorem 5.10 ( W 1 is a Polish space). Let d m and d c be two distances on M ≤1 (Z) such that d c induces the weak topology on (Z), d c is complete and continuous w.r.t. d m , and d ,m is (invariant) smooth and weakly regular on W 1 . Then, the space ( W 1 , δ c ,m ) is a Polish metric space.

Note that the assumptions in Theorem 5.10 imply that d m also induces the weak topology on M ≤1 (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 ,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 ≤1 (Z). Also note that Theorem 5.10 can easily be extended to W ≤1 or the space of unlabeled Mvalued kernels W M when M is a bounded convex closed subset of M + (Z).

Proof. From Lemma 5.9, we have that δ c

,m is a distance on W 1 which induces the same topology as δ ,m , and from Proposition 4.6, we have that ( W 1 , δ ,m ), and thus ( W 1 , δ c ,m ), is separable. To get that this latter space is Polish, we are left to prove that the distance δ c ,m is complete. Let (W n ) n∈N be a sequence of probability-graphons that is Cauchy for δ c ,m . By definition of the cut distance δ c ,m , the sequence of probability measures (M Wn ) n∈N is Cauchy in M 1 (Z) for the complete distance d c . Thus, the sequence (M Wn ) n∈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∈N is tight. By Theorem 5.1 (i), there exists a subsequence (W n k ) k∈N that converges for δ ,m to a limit, say W ∈ W 1 . This subsequence also converges for δ c ,m to W as δ ,m and δ c ,m induce the same topology. Finally, because the sequence (W n ) n∈N is Cauchy for δ c

,m and has a subsequence converging to W for δ c ,m , the whole sequence must also converge to W for δ c ,m . Consequently, the distance δ c ,m is complete.

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

Lemma 5.11 (M 1 (Z) seen as a closed subset of W 1 ). Let d m be a distance on M ≤1 (Z) such that d ,m is (invariant and) smooth on W 1 . Then, the map µ → W µ ≡ µ is an injection from (M 1 (Z), d m ) to ( W 1 , δ ,m ) with a closed range and continuous inverse.

Proof. For any µ ∈ M 1 (Z) consider the constant probability-graphon W µ ≡ µ, and notice that M Wµ = µ, that W µ (S × T ; •) = λ(S)λ(T ) µ for all measurable S, T ⊂ [0, 1], and that W ϕ µ = W µ for any measure-preserving map ϕ. This readily implies that for µ ∈ M 1 (Z) and W ∈ W 1 :

(20) δ ,m (W µ , W ) = d ,m (W µ , W ) = sup S,T ⊂[0,1] d m (λ(S)λ(T )µ, W (S × T ; •)) ≥ d m (µ, M W ).
In particular, taking W = W ν for ν ∈ M 1 (Z) we get that δ ,m (W µ , W ν ) ≥ d m (µ, ν). This implies that the map I : µ → W µ ≡ µ is an injection, and its inverse, given by the map W µ → µ, is 1-Lipschitz.

Let (µ n ) n∈N be a sequence in M 1 (Z) such that the sequence (W µn ) n∈N converges for δ ,m to a limit, say W . We deduce from (20) that (µ n ) n∈N converges for d m to µ = M W and that for all measurable S, T ⊂ [0, 1], (λ(S)λ(T )µ n ) n∈N converges for d m to W (S × T ; •). This implies that W (S × T ; •) = λ(S)λ(T )µ(•) for all measurable S, T ⊂ [0, 1], that is, W = W µ . This implies that the image by I of any closed subset of M 1 (Z) is a closed subset of W 1 , and thus the range of I is closed.

Remark 5.12 (Extension to isometric representation of M 1 (Z)). If the distance d m , in addition to the hypothesis of Lemma 5.11, is sub-homogeneous, that is, for all µ, ν ∈ M 1 (Z) we have

d m (µ, ν) = sup r∈[0,1] d m (rµ, rν) (which is the case if d m is quasi-convex), then we deduce from (20) that the map µ → W µ ≡ µ is isometric from (M 1 (Z), d m ) to ( W 1 , δ ,m ).
We now state characterization of compactness and completeness for the space of probabilitygraphons. Recall Z is a Polish space.

Corollary 5.13 (Characterization of compactness and completeness for W 1 ). Let d m be a distance on M ≤1 (Z), which induces the weak topology on M ≤1 (Z), and such that d ,m is (invariant) smooth and weakly regular on W 1 . We have the following properties.

(i) Z is compact ⇐⇒ (M ≤1 (Z), d m ) is compact ⇐⇒ ( W 1 , δ ,m ) is compact. (ii) If (M ≤1 (Z), d m ) is complete then ( W 1 , δ ,m ) is complete. (iii) Assume furthermore that d m is sub-homogeneous (see Remark 5.12). If ( W 1 , δ ,m ) is complete, then (M 1 (Z), d m ) is complete.
Proof. We prove Point (i). rom Remark 2.7, we already know that Z is compact if and only if M ≤1 (Z) is weakly compact, i.e. compact for d m as d m induces the weak topology on M ≤1 (Z). Now, assume that (M ≤1 (Z), d m ) is compact. Applying Theorem 5.1 (iii), we get that the space ( W 1 , δ ,m ) is also compact.

Conversely, assume that ( W 1 , δ ,m ) is compact. By Lemma 4.9, the mapping W → M W is continuous from ( W 1 , δ ,m ) to (M 1 (Z), d m ), and as ( W 1 , δ ,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 µ ≡ µ is M Wµ = µ. Hence, (M 1 (Z), d m ) (and thus (M ≤1 (Z), d m )) is compact.
We prove Point (ii). Assume that (M ≤1 (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 (

W 1 , δ c ,m ) is complete. As d c = d m , we have δ ,m ≤ δ c ,m ≤ 2δ ,m . Hence, ( W 1 , δ ,m
) is also complete. We prove Point (iii). Assume that ( W 1 , δ ,m ) is complete. Let (µ n ) n∈N be a Cauchy sequence of probability measures in (M 1 (Z), d m ). By Remark 5.12, the sequence of constant probabilitygraphons (W µn ) n∈N is also Cauchy for δ ,m . As ( W 1 , δ ,m ) is complete, there exists a probabilitygraphon W ∈ W 1 such that (W µn ) n∈N converges to W for the cut distance δ ,m . Thanks to Lemma 5.11, W is constant equal to some µ ∈ M 1 (Z), and (µ n ) n∈N converges to µ for d m . Hence, (M 1 (Z), d m ) is complete.

Sampling from probability-graphons

Measured-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 δ ,F , where F = (f k ) k∈N (with f 0 = 1) is a convergence determining sequence.

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 this 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.

6.1. M 1 (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 × 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 X be a non-empty set. A X -graph is a triplet G = (V, E, Φ) where (V, E) is a graph and Φ : E → X is a map that associates a decoration x = Φ(e) ∈ X to each edge e ∈ E. When X = 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 Φ is a symmetric function, i.e. for every edge (x, y) ∈ E, we have (y, x) ∈ E and Φ(x, y) = Φ(y, x). Remark 6.2 (M 1 (Z)-Graphs as probability-graphons). Any labeled M 1 (Z)-graph G can be naturally represented as an M 1 (Z)-valued graphon, which we denote by W G , in the following way

. Let G = (V, E, M ) be a M 1 (Z)-graph, with v(G) = n ∈ N * . Denote by V = [n] = {1, . . . , 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 (Z)-valued graphon stepfunction W G associated with the M 1 (Z)-graph G by: ∀(i, j) ∈ E, ∀(x, y) ∈ J i × J j , W G (x, y; dz) = Φ(i, j)(dz);

and W G (x, y; dz) equals the Dirac mass at ∂ otherwise, where ∂ is an element of 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 ≤1 (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 ,m (G, H) = d ,m (W G , W H ).
When G and H does 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:

δ ,m (G, H) = δ ,m (W G , W H ).
Remind that when the distance d m derives from a norm N m on M ± (Z), Lemma 3.19 applies, and the cut distance d ,m (G, H) can be rewritten as a combinatorial optimization over whole steps.

Remark 6.3 (Weighted graphs as M 1 (Z)-graphs). We will sometimes need to interpret a weighted graph G as a M 1 (Z)-graph where a weight x on an edge is replaced by δ x the Dirac mass laocated at x. Notation 6.4 (The real-weighted graph G[f ]). For a M 1 (Z)-graph (resp. weighted graph) G and a function f ∈ C b (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 Φ G[f ] (i, j) = Φ G (i, j; f ) = Z f (z)Φ G (i, j; dz) (resp. Φ G[f ] (i, j) = f (Φ G (i, j)))
, where Φ G is the decoration of the M 1 (Z)-graph G.

6.2. W -random graphs. Let W be a probability-graphon, and x = (x 1 , . . . , x n ), n ∈ N * , be a sequence of points from [0, 1]. We define the M 1 (Z)-graph H(x, W ) as the complete graph whose vertex set is [n] = {1, . . . , n}, and with each edge (i, j) decorated by the probability measure W (x i , x j ; dz).

Let H be any M 1 (Z)-graph. We can define from H a random weighted (directed) graph 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 β 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 = H(x, W ), we simply note G(x, W ) = G(H(x, W )).
An important special case is when the sequence X is chosen at random: X = (X i ) 1≤i≤n where the X i are independent and uniformly distributed on [0, 1]. For this special case, we simply note H(n, W ) = H(X, W ) and G(n, W ) = G(X, W ), that are conditionally on X = x, distributed respectively as H(x, W ) and G(x, W ). The random graphs H(n, W ) and 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 (Z)-graph H(x, W ) is also symmetric. From a symmetric M 1 (Z)graph H, the random weighted graph G(H) is not necessarily symmetric, but we can define a random symmetric weighted graph G sym (H) whose vertex set V (H) and E(H) are the same as H, and with independent weights β i,j = β j,i on each edge (i, j) = (j, i) distributed according to Φ H (i, j; •). For H = H(x, W ) we simply note G sym (x, W ) and G sym (n, W ).

For a weighted graph G, and for 1 ≤ k ≤ v(G), we can define the random weighted graph 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] → 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 var (G(k, G), G(k, W G )) ≤ k 2 1 v(G) ,
where d 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 [START_REF] Lovász | Large networks and graph limits[END_REF]. The main consequence of the following lemma is that the cut distance d ,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 realvalued kernel w) and a vector X = (X i ) 1≤i≤k composed of k independent random variables uniformly distributed over [0, 1], we denote by W X = W H(k,W ) (resp. w X ) the random measurevalued (resp. real-valued) stepfunction with k steps of size 1/k, and where the step (i, j) has value W (X i , X j ; •) (resp. w(X i , X j )).

Lemma 6.7 (First Sampling Lemma). Let F be a convergence determining sequence. Let k ∈ N * , and U, W ∈ 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 - √ k/10 , we have:

- 2 k 1/4 ≤ U X -W X ,F -U -W ,F ≤ 9 k 1/4 •
An immediate consequence of Lemma 6.7 is that the decorated graphs with probability measures on their edges H(k, U ) and H(k, W ) can be coupled in order that d ,F (H(k, U ), H(k, W )) is close to d ,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 • ,F can be approximated by the maximum of the one-sided cut norm using a finite number of function. Remind from Remark 3.24 the definition of the one-sided version of the cut norm • + ,R .

Lemma 6.8 (Approximation bound with • ,F and

• + ,R ). Let U, W ∈ W 1 and let N ∈ N. For every ε = (ε n ) 1≤n≤N ∈ {±1} N , define g N,ε = N n=1 2 -n ε n f n . Then, we have: U -W ,F -2 -N ≤ max ε∈{±1} N (U -W ) [g N,ε ] + ,R ≤ U -W ,F .
Proof. First remark that for n ∈ N, f n takes values in [0, 1], and thus

U [f n ] -W [f n ] takes values in [-1, 1]. Remind that f 0 = 1, and thus U [f 0 ] -W [f 0 ] ≡ 0.
Upper bounding integrals by 1 for indices n > N , we get:

U -W ,F ≤ sup S,T ⊂[0,1] N n=1 2 -n S×T (U -W )[f n ](x, y) dxdy + 2 -N .
And adding the non-negative terms for n > N , we get:

sup S,T ⊂[0,1] N n=1 2 -n S×T (U -W )[f n ](x, y) dxdy ≤ U -W ,F .
Using the same idea as in (13) and ( 14), we get:

sup S,T ⊂[0,1] N n=1 2 -n S×T (U -W )[f n ](x, y) dxdy = max ε∈{±1} N (U -W ) [g N,ε ] + ,R ,
which concludes the proof.

Proof of Lemma 6.7.

Remark that for f ∈ C b (Z) and W ∈ W ± , we have (W X )[f ] = (W [f ]) X ,
and we thus write W [f ] X without any ambiguity. Assume that k ≥ 2 4 (otherwise the lower bound in the lemma is trivial

). Set N = ⌈log 2 (k 1/4 )⌉, so that 2 -1 k -1/4 < 2 -N ≤ k -1/4 . Let ε ∈ {±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,ε ] also take values in [-1, 1]. Applying Lemma 10.7 in [START_REF] Lovász | Large networks and graph limits[END_REF] to the real-valued kernel (U -W ) [g N,ε ], we get with probability at least 1 -2 e - √ k/10 that:

(21) - 3 k ≤ (U -W )[g N,ε ] X + ,R -(U -W )[g N,ε ] + ,R ≤ 8 k 1/4 , where remind that • +
,R is the one-sided version of the cut norm for real-valued kernels defined in (12). Hence, with probability at least 1 -2 N +1 e - √ k/10 ≥ 1 -4k 1/4 e - √ k/10 , we have that the bounds in (21) holds for every ε ∈ {±1} N simultaneously; and when all of this holds, applying Lemma 6.8 to U, W and to U X , W X , we get:

U X -W X ,F ≤ max ε∈{±1} N (U -W )[g N,ε ] X + ,R + 2 -N ≤ max ε∈{±1} N (U -W )[g N,ε ] + ,R + 9 k 1/4 ≤ U -W ,F + 9 k 1/4 ,
and similarly:

U -W ,F ≤ max ε∈{±1} N (U -W )[g N,ε ] + ,R + 2 -N ≤ max ε∈{±1} N (U -W )[g N,ε ] X + ,R + 1 k 1/4 + 3 k ≤ U X -W X ,F + 2 k 1/4 •
This concludes the proof. 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 H(k, U ) and 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 G(k, W ) is close to H(k, W ) in the cut distance d ,F , and thus the cut distance between the random weighted graphs G(k, U ) and G(k, W ) is also close to d ,F (U, W ).

Recall from Section 6.2 the definition of the random weighted graph G(H) when H is a M 1 (Z)graph. Following Remarks 6.3 and 6.2, we shall see the weighted graph G(H) as a M 1 (Z)-graph or even as a probability-graphon. Lemma 6.9 (Bound in probability for d ,F (G(H), H)). For every M 1 (Z)-graph H with k vertices, and for every ε ≥ 10/ √ k, we have:

P d ,F (G(H), H) > 2ε ≤ e -ε 2 k 2 . Remark 6.10 (Bound in expectation for d ,F (G(H), H)). Remind that d ,F (G(H), H) ≤ 1.
Applying Lemma 6.9 with ε = 10/ √ k, we get the following bound on the expectation of d ,F (G(H), H):

E[d ,F (G(H), H)] ≤ 20 √ k + e -100k < 21 √ k •
Proof of Lemma 6.9. Let H and ε be as in the lemma. Assume that ε ≤ 1/2 (otherwise the probability to bound in the lemma is null). To simplify the notations, denote by

G = G(H) through this proof. Define N = ⌈log 2 (ε -1 )⌉, so that ∞ n=N +1 2 -n ≤ ε.
Upper bounding by 1 the terms for n > N in (15), we get for U, W ∈ W 1 :

d ,F (U, W ) ≤ N n=1 2 -n U [f n ] -W [f n ] ,R + ε,
where remind that • ,R is the cut norm for real-valued kernels defined in (12). Using this equation with the graphs G and H, we get:

P(d ,F (G, H) > 2ε) ≤ P N n=1 2 -n d ,R (G[f n ], H[f n ]) > ε ≤ N n=1 P d ,R (G[f n ], H[f n ]) > ε , ( 22
)
where d ,R denotes the cut distance associated to the cut norm • ,R for real-valued graphons and kernels. Remark that for every n ∈ 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 [Lov12, Lemma 10.11], we get:

(23) ∀n ∈ [N ], P(d (G[f n ], H[f n ]) > ε) ≤ 2 • 4 k e -2ε 2 k 2 .
Combining ( 22) and ( 23), we get for ε > 10/ √ k:

P(d ,F (G, H) > 2ε) ≤ 2N 4 k e -2ε 2 k 2 ≤ e -ε 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 G(k, W ): Corollary 6.11 (First Sampling Lemma for G(k, W )). Let U, W ∈ W 1 be two probabilitygraphons, and k ∈ N * . Then, we can couple the random weighted graphs G(k, U ) and G(k, W ) such that with probability at least 1 -(4k 1/4 + 1) e - √ k/10 , we have:

d ,F (G(k, U ), G(k, W )) -d ,F (U, W ) ≤ 13 k 1/4 • Proof.
Assume that k ≥ 13 4 (otherwise the bound in the corollary is trivial). Then, we have with probability at least 1 -4k 1/4 e - √ k/10 -2 e -100k > 1 -(4k 1/4 + 1) e - √ k/10 :

d ,F (G(k, U ), G(k, W )) -d ,F (U, W ) ≤ d ,F (G(k, U ), G(k, W )) -d ,F (H(k, U ), H(k, W )) + d ,F (H(k, U ), H(k, W )) -d ,F (U, W ) ≤ d ,F (G(k, U ), H(k, U )) + d ,F (G(k, W ), H(k, W )) + 9 k 1/4 ≤ 40 √ k + 9 k 1/4 ≤ 13 k 1/4
, 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 = H(k, U ) and W X = H(k, W )) for the second inequality, the upper bound from Lemma 6.9 with ε = 10/ √ k with both U and W for the third inequality, and that 1 √ k ≤ 1 13k 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 (Z)-graph is close to its original probability-graphon with high probability. Note that we use the unlabeled cut distance δ ,F rather than d ,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 [Lov12, Lemma 10.16] (replacing the weak regularity lemma and the first sampling lemma by their counterparts for probabilitygraphons, 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 F be a convergence determining sequence. Let W ∈ W 1 be a probability-graphon and k ∈ N * . Then, with probability at least 1-exp(-k/(2 ln(k))) we have:

δ ,F (H(k, W ), W ) ≤ 21 ln(k) and δ ,F (G(k, W ), W ) ≤ 22 ln(k) •
In the above lemma, the asymmetric random graph G(k, W ) can be replaced by the symmetric random graph G sym (k, W ) without changing the proof. Similarly, the results in Section 6.3.2 can be reformulated with symmetric random graphs G sym (k, W ) and G 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 -ε 2 k 2 /2 , see also [START_REF] Lovász | Large networks and graph limits[END_REF]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 δ ,F . Theorem 6.13 (Convergence of sampled subgraphs). Let F be a convergence determining sequence. Let W ∈ W 1 be a probability-graphon. Then, a.s. the sequence of sampled subgraphs (G(k, W )) k∈N * converges to W for the cut distance δ ,F , and thus for any cut distance δ ,m from Theorem 5.5.

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 δ ,F through the Counting Lemma and the Inverse Counting Lemma. Those results are analogous to the case of real-valued graphons, see [START_REF] Lovász | Large networks and graph limits[END_REF]Chapter 7] for the definition of homomorphism densities and [Lov12, Chapter 10] for the Counting Lemma and Inverse Counting Lemma. The main differences with [START_REF] Lovász | Large networks and graph limits[END_REF] are: the decoration of the edges of the graphs with functions from C b (Z); the Counting Lemma for the decorations belonging only in the convergence determining sequence F ; the more technical proof of the Inverse Counting Lemma. Note that we need to work with δ ,F here as the proof of the Inverse Counting Lemma relies on the second sampling Lemma 6.12. 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 probabilitygraphons, we need to replace the absence/presence of edges (which is 0-1 valued) by test functions from C b (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 (Z)-graph and to vary only the C b (Z)-decorating functions g = (g e ) e∈E , thus we will write F g = (V, E, g) for a C b (Z)-graph. Moreover, when there exists a convergence determining sequence F such that g e ∈ F for every edge e ∈ E, we say that F g is a F -graph and use the same notation conventions. Definition 7.1 (Homomorphism density). We define the homomorphism density of a C b (Z)graph F g in a signed measure-valued kernel W ∈ W ± as:

(24) t(F g , W ) = M F W (g) = [0,1] V (F ) (i,j)∈E(F ) W (x i , x j ; g i,j ) i∈V (F ) dx i .
Moreover, M F W defines a measure on Z E (which we still denote by M F W ) which is characterized by M F W (⊗ e∈E g e ) = M F W (g) for g = (g e ) e∈E . Remark 7.2 (Invariance under relabeling of homomorphism densities). Let ϕ : [0, 1] → [0, 1] be a measure-preserving map. As ϕ ⊗k : (x 1 , . . . , x k ) → (ϕ(x 1 ), . . . , ϕ(x k )) is a measure-preserving map on [0, 1] k , applying the transfer formula (see (1)), we get that for every C b (Z)-graph F g and every signed measure-valued kernel W ∈ W ± , we have t(F g , W ϕ ) = t(F g , W ). Thus t(F g , •) can be extending to W ± .

Remark 7.3. When W ∈ W + is a measure-valued kernel, and F is the graph with two vertices and one edge, we get that M F W = M W the measure defined in (16). 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 (Z)-graph F g in G as t(F g , G) = t(F g , W G ) (remind from Remark 6.2 the definition of W G ), that is: t(F g , G) = 1 v(G) k (x1,••• ,x k )∈V (G) k (i,j)∈E(F ) g (i,j) (Φ G (x i , x j )),
where k = v(F ) and Φ 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 δ ,F for some convergence determining sequence F = (f n ) n∈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 [START_REF] Lovász | Large networks and graph limits[END_REF]). Recall that by Remark 7.2, t(F g , •) is defined on W ± . Lemma 7.5 (Counting Lemma). Let F = (f n ) n∈N be a convergence determining sequence (with f 0 = 1 and f n takes values in [0, 1]). Let F g be a F -graph, and for every edge e ∈ E(F ), let n e ∈ N be such that g e = f ne . Then, for every probability-graphons W, W ′ ∈ W 1 , we have:

|t(F g , W ) -t(F g , W ′ )| ≤   e∈E(F ) 2 ne   δ ,F (W, W ′ ).
Remark 7.6 (W → 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 → t(F g , W ) is Lipschitz on the space of unlabeled probability-graphons W 1 equipped with the cut distance δ ,F .

Proof of Lemma 7.5. To do this proof, we will apply Lemma 10.24 from [START_REF] Lovász | Large networks and graph limits[END_REF], which applies to graphs F whose edges are decorated with (possibly different) real-valued graphons w = (w e : e ∈ E(F )), and the associated homomorphism density is defined as

(25) t(F, w) = [0,1] V (F ) (i,j)∈E(F ) w e (x i , x j ) i∈V (F ) dx i .
Remind from (11) that for a probability-graphon W ∈ W 1 and a function f ∈ 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 ∈ E(F )) and w ′ = (W ′ [g e ] : e ∈ E(F )). Notice from (24) and (25) that we have t(F, w) = t(F g , W ) and t(F, w ′ ) = t(F g , W ′ ). Applying [Lov12, 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 ′ )| ≤ e∈E(F ) W [g e ] -W ′ [g e ] ,R ,
where the norm • ,R in the upper bound is the cut norm for real-valued graphons (see (12) for definition of this object). For e ∈ E(F ), by definition of the cut distance d ,F and using (10), we have:

W [g e ] -W ′ [g e ] ,R ≤ 2 ne d ,F (W, W ′ ).
Hence, combining all those upper bounds, we get the bound in the lemma but with d ,F instead of δ ,F . Since t(F g , •) is invariant under relabeling by Remark 7.2, taking the infimum other all relabelings allows to replace d ,F by δ ,F and to get the bound in the lemma.

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

Lemma 7.7 (Weak Counting Lemma). Let F be a convergence determining sequence (with f 0 = 1). Let (W n ) n∈N and W be probability-graphons such that lim n→∞ t(F g , W n ) = t(F g , W ) for all F -graph F g (which in particular the case if lim n→∞ δ ,F (W n , W ) = 0 by the Counting Lemma 7.5). Then, for every C b (Z)-graph F g we have:

t(F g , W n ) -→ n→∞ t(F g , W ).
Proof. Let F = (V, E) be some fixed (directed) graph. By assumption, we have for all edgedecorations g = (g e ) e∈E in F that lim n→∞ M F Wn (⊗ e∈E g e ) = M F W (⊗ e∈E g e ) (see Definition 7.1). By [EK09, Chapter 3, Proposition 4.6], F ⊗E is a (countable) convergence determining family on M + (Z E ). Thus, the sequence of measures (M F Wn ) n∈N converges to M F W for the weak topology on M + (Z E ). And in particular, for every edge-decoration function g = (g e ) e∈E (here for every e ∈ E, g e ∈ C b (Z) is arbitrary) we have

M F Wn (⊗ e∈E g e ) = t(F g , W n ) → t(F g , W ) = M F W (⊗ e∈E g e )
as n → ∞. This being true for all choices of the graph F , it concludes the proof. 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 δ ,F . Lemma 7.8 (Inverse Counting Lemma). Let F = (f n ) n∈N be a convergence determining sequence (with f 0 = 1 and f n takes values in [0, 1]). Let U, W ∈ W 1 be two probability-graphons, and let k, n 0 ∈ N * . Assume that we have |t(F g , U )t(F g , W )| ≤ 2 -k-n0k 2 for every (complete) C b (Z)graph F g with k vertices and such that the edge-decoration functions g = (g e ) e∈E(F ) are products (without repetition) of the functions (f n ) 1≤n≤n0 and (1f n ) 1≤n≤n0 . Then, we have:

δ ,F (U, W ) ≤ 44 log(k) + 2 -n0 .
To prove Lemma 7.8, we first need to prove the special case where the space Z is finite.

Lemma 7.9 (Inverse Counting Lemma, case with finite space Z). Assume that the space Z is finite with cardinality n 1 , for simplicity say Z = [n 1 ]. Define the indicator functions f n : z → 1 {z=n} for n ∈ [n 1 ], in particular H = (f n ) 1≤n≤n1 is a finite convergence determining sequence. Let U, W ∈ W 1 be two probability-graphons, and let k ∈ N * . Assume that we have |t(F g , U )t(F g , W )| < 2 -k-log 2 (n1)k 2 for every (complete) H-graph F g with k vertices.

Then, for any (possibly finite) convergence determining sequence F , we have:

δ ,F (U, W ) ≤ 44 log(k) •
Abusing notations, we can identify a weight-value n ∈ Z with its indicator functions f n , and doing this identification for edge-decoration functions, we can identify a F -graph F g with its corresponding weighted graph. In particular, doing so we get t(F g , W ) = P(G(k, W ) = F g ) for every F -graph F g with k vertices. The proof of Lemma 7.9 is then a straightforward adaptation of the proof of [Lov12, Lemma 10.31 and Lemma 10.32].

Proof of Lemma 7.8. As the functions (f n ) n∈N take value in [0, 1], for all ϕ measure-preserving map, for all S, T ⊂ [0, 1] measurable sets and for all n ∈ N, we have:

U (S × T ; f n ) -W ϕ (S × T ; f n ) ≤ 1.
Using this bound, we get the following bound (remind that f 0 = 1):

(26) δ ,F (U, W ) ≤ inf ϕ∈S [0,1] sup S,T ⊂[0,1] n0 n=1 2 -n U (S × T ; f n ) -W ϕ (S × T ; f n ) + 2 -n0 .
Hence, for a point z ∈ Z, the upper bound in (26) uses only the information given by (f n (z)) n∈ [n0] . In order to discretize the space [0, 1] n0 , we replace a point p = (p 1 , . . . , p n0 ) ∈ [0, 1] n0 by a random point (Y 1 , . . . , Y n0 ) ∈ {0, 1} n0 where the Y i are independent random variables with Bernoulli distribution of parameter p i . This leads us to replace a M 1 (Z)-valued kernel W by the M 1 ({0, 1} n0 )-valued kernel W defined for all (x, y) ∈ [0, 1] 2 , and for all s = (s 1 , . . . , s n0 ) ∈ {0, 1} n0 as: W (x, y; {s}) = W (x, y; f s ) where

f s = n0 n=1 f sn n (1 -f n ) 1-sn .
Fix some enumeration (s m ) m∈[2 n 0 ] of the points in {0, 1} n0 , and define the indicator functions hm : s → 1 {s=s m } for m ∈ [2 n0 ], in particular H = ( hm ) 1≤m≤2 n 0 is a finite convergence determining sequence on M + ({0, 1} n0 ). Let F g be a H-graph with vertex set V (F ) = [k], and for every edge e ∈ E(F ), let m e ∈ [2 n0 ] be such that ge = hme . Define the edge-decoration functions g = (g e ) e∈E(F ) for every edge e ∈ E(F ) as g e = f s me , then we get:

t(F g , W ) = [0,1] k (i,j)∈E(F ) W (x i , x j ; {s me }) k i=1 dx i = t(F g , W ).
Thus, the M 1 ({0, 1} n0 )-valued graphons Ũ and W inherit the bounds on the homomorphism densities: for every H-graph F g, we have

|t(F g, Ũ ) -t(F g , W )| ≤ 2 -k-n0k 2 .
Define for all n ∈ [n 0 ] the function fn : s → 1 {sn=1} , and let F be the concatenation of ( fn ) n∈[n0] and H, in particular F is a finite convergence determining sequence on M + ({0, 1} n0 ). Finally, as δ , F ( Ũ , W ) upper bounds the first term in the upper bound of (26), applying Lemma 7.9 with the finite space Z = {0, 1} n0 and n 1 = 2 n0 , the finite convergence determining sequences F and H, and the M 1 ({0, 1} n0 )-valued graphons Ũ and W , we get:

δ ,F (U, W ) ≤ 44 ln(k) + 2 -n0 ,
such that U ϕ = W ψ almost everywhere on [0, 1] 2 . (iii) t(F g , U ) = t(F g , W ) for all C b (Z)-graph F g . (iv) t(F g , U ) = t(F g , W ) for all F -graph 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 F ). Hence, we have the desired equivalence.

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 δ ,m on the space of unlabeled probability-graphons W 1 in terms of homomorphism densities Theorem 7.11 (Characterization of the topology induced by δ ,m ). Let (W n ) n∈N and W be unlabeled probability-graphons from W 1 . The following properties are equivalent:

(i) lim n→∞ δ ,m (W n , W ) = 0 for some (and hence for every) choice of the distance d m on M ≤1 (Z) such that d m induces the weak topology on M ≤1 (Z) and the cut distance d ,m on W 1 is (invariant) smooth, weakly regular and regular w.r.t. the stepping operator. (ii) lim n→∞ t(F g , W n ) = t(F g , W ) for all C b (Z)-graph F g . (iii) lim n→∞ t(F g , W n ) = t(F g , W ) for all F -graph F g . (iv) For all k ≥ 2, the sequence of sampled subgraphs (G(k, W n )) n∈N converges in distribution to G(k, W ).

In particular, the topology induced by the cut distance δ ,F on the space of unlabeled probability-graphons W 1 coincides with the topology generated by the homomorphism densities functions W → t(F g , W ) for all C b (Z)-graph F g . Proof. By Theorem 5.5, convergence for δ ,F is equivalent to convergence for δ ,m for every choice of the distance d m on M ≤1 (Z) such that d m induces the weak topology on M ≤1 (Z) and the cut distance d ,m on W 1 is (invariant) smooth, weakly regular and regular w.r.t. the stepping operator. Taking d m = d P , 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 F ). Notice that when F is the complete graph with k vertices, M F W is the joint measure of all the edge-weights of the random graph G(k, W ), and thus characterizes the distribution random graph G(k, W ). Thus (remind Definition 7.1), Property (ii) and Property (iv) are equivalent. Hence, we have the desired equivalence. Question 7.12 (Do the distances d ,F all induce the same topology?). Even though every distance δ ,F generates the same topology on the space of unlabeled probability-graphons W 1 , it is an open question whether or not this is also the case that every distance d ,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 probabilitygraphon it is enough to prove that there exists a convergence determining sequence F such that for every F -graph F g the homomorphism densities t(F g , •) converge. Proposition 7.13 (Existence of a limit unlabeled probability-graphon). Let d m be a distance on M ≤1 (Z) such that d m induces the weak topology on M ≤1 (Z) and the cut distance d ,m on W 1 is (invariant) smooth, weakly regular and regular w.r.t. the stepping operator.

Let (W n ) n∈N be sequence of unlabeled probability-graphons in W 1 that is tight. Let F be a convergence determining sequence such that for every F -graph F g the sequence (t(F g , W n )) n∈N converges. Then, there exists an unlabeled probability-graphon W ∈ W 1 such that the sequence (W n ) n∈N converges to W for δ ,m .

Proof. Since the sequence (W n ) n∈N is tight, by Theorem 5.1, there exists a subsequence (W n k ) k∈N of the sequence (W n ) n∈N that converges to some W for δ ,m . By Theorem 7.11, we have for every F -graph F g that lim k→∞ t(F g , W n k ) = t(F g , W ); and as we already know that the sequence (t(F g , W n )) n∈N converges, we have that lim n→∞ t(F g , W n ) = t(F g , W ). Hence, by Theorem 7.11, we get that the sequence (W n ) n∈N converges to W for δ ,m .

Remark 7.14. For the special case 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 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 subsequence 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 δ and δ ′ . Remind from Definition 4.1 the definition of the stepfunction W P for a signed measure-valued kernel W and a finite partition P of [0, 1]. For a finite partition P of [0, 1], define its diameter as the smallest diameter of its sets, i.e. diam(P) = min S∈P diam(S) = min S∈P sup x,y∈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 ± ). Let (W n ) n∈N be a sequence in W 1 (resp. W + or W ± ) which is tight (resp. uniformly bounded and tight). Further assume that we are given, for every n, k ∈ N, partitions P n,k of [0, 1], such that these partitions and the corresponding stepfunctions W n,k = (W n ) P n,k satisfy the following conditions:

(i) the partition P n,k+1 is a refinement of P n,k , (ii) diam(P n,k ) ≤ 2 -k and |P n,k | = m k depends only on k (and not on n), (iii) d(W n , W n,k ) ≤ 1/(k + 1).
Then, there exists a subsequence (W n ℓ ) ℓ∈N of the sequence (W n ) n∈N and a measure-valued kernel

W ∈ W 1 (resp. W ∈ W + or W ∈ W ± ) such that (W n ℓ ) ℓ∈N converges to W for δ .
Moreover, assume that d ′ is another invariant smooth distance on W 1 (resp. W + or W ± ) such that for every n ∈ N and k ∈ N, W n,k also satisfies:

(iv) d ′ (W n , W n,k ) ≤ 1/(k + 1).
Then, there exists a subsequence (W n ℓ ) ℓ∈N of the sequence (W n ) n∈N and a measure-valued kernel W ∈ W 1 (resp. W ∈ W + or W ∈ W ± ) such that (W n ℓ ) ℓ∈N converges to the same measure-valued kernel W simultaneously both for δ and for δ ′ , the cut distance associated with d ′ .

Proof. We adapt here the general scheme from the proof of Theorem 9.23 in [START_REF] Lovász | Large networks and graph limits[END_REF], but the argument for the convergence of the U k , defined below, takes into account that measure-valued kernels are infinite-dimensional valued. We set (remind from (2) the definition of • ∞ ):

C = sup n∈N W n ∞ < +∞.
The proof is divided into four steps.

Step 1: Without loss of generality, the partitions P n,k are made of intervals. For every n ∈ N, we can rearrange the points of [0, 1] by a measure-preserving map so that the partitions P n,k are made of intervals, and we replace W n by its rearranged version.

An argument similar to the next lemma is used in the proof in [Lov12, Proof of Theorem 9.23] without any reference. So, we provide a proof and stress that diameters of the partitions shrinking to zero is an important assumption (see Remark 8.3 below).

Lemma 8.2 (Kernel rearrangement with interval partitions). Let (P k ) k∈N be a refining sequence of finite partitions of [0, 1] whose diameter converges to zero. Then, there exist a measurepreserving map ϕ ∈ S[0,1] and a refining sequence of partitions made of intervals (Q k ) k∈N such that for all k ∈ N, and all set S ∈ P k there exists a set R ∈ Q k such that a.e. 1 R = 1 ϕ -1 (S) .

In particular, if W is a signed measure-valued kernel, then for U = W ϕ , we have that a.e.

U Q k = (W ϕ ) Q k = (W P k ) ϕ for all k ∈ N.
Notice that, according to Remark 4.4, the sequence of refining partition (P k ) k∈N , with a partition diameter converging to 0, separates points and thus generates the Borel σ-field of [0, 1].

Proof. Consider the infinite Ulam-Harris tree

T ∞ = {u 1 • • • u k : k ∈ N, u 1 , . . . , u k ∈ N * },
where for k = 0 the empty word u = ∂ is called the root node of the tree; for a node u = u 1 • • • u k ∈ T ∞ , we define its height as h(u) = k, and if k > 0 we define its parent node as p(u) = u 1 • • • u k-1 and we say that u is a child node of p(u). We order vertices on the tree T ∞ with the lexicographical (total) order < lex . As a first step, we construct a subtree T ⊂ T ∞ that indexes the sets in the partitions (P k ) k∈N , such that for every k ∈ N, P k = {S u : u ∈ T , h(u) = k}, and such that if S v ⊂ S u with S v ∈ P k and S u ∈ P k-1 , then p(v) = u.

Without loss of generality, we may assume that P 0 = {[0, 1]}, and we label its only set by the empty word ∂, and we set S ∂ = [0, 1]. Then, suppose we have already labeled the sets from P 0 , . . . , P k , and we proceed to label the sets from P k+1 . Because the partition P k+1 is a refinement of P k , we can group the sets of P k+1 by their unique parent set from P k , i.e. for every S u ∈ P k , let O u = {S ∈ P k+1 : S ⊂ S u }, then S u = ∪ S∈Ou S. For S u ∈ P k , we fix an arbitrary enumeration of O u = {S 1 , . . . , S ℓ } with ℓ = |O u |, then label the set S j by uj, and set S j = S uj ; remark that the parent node of w = uj is p(w) = u, and the height of node w is h(w) = h(u) + 1 = k + 1. Hence, we have labeled every set from P k+1 . To finish the construction, we set T = {u : ∃k ∈ N, ∃S ∈ P k , S has label u}.

We now proceed to construct a measure-preserving map ψ such that the image of every set S u is a.e. equal to an interval, and such that those intervals are ordered w.r.t. to the order of their labels in T .

Define the map σ : [0, 1] → T N by σ(x) = (u k (x)) k∈N ∈ T N where u k (x) is the only node of T with height k such that x ∈ S u k (x) (and thus u k+1 (x) is a child node of u k (x)). Remark that if u k0 (x) < lex u k0 (y) for some k 0 ∈ N, then u k (x) < lex u k (y) for every k ≥ k 0 . We extend naturally the total order < lex from T to a the total order on T

N : for (u k ) k∈N , (v k ) k∈N ∈ T N , (u k ) k∈N < lex (v k ) k∈N if u k0 < lex v k0 where k 0 is the smallest k such that u k = v k .
For every u ∈ T , define:

A -(u) = v< lex u : h(v)=h(u) S v and A + (u) = A -(u) ∪ S u ,
and then define C -(u) = λ(A -(u)) and C + (u) = λ(A + (u)). Now, define ψ as, for x ∈ [0, 1]:

ψ(x) = λ(A -(x)) where A -(x) = {y ∈ [0, 1] : σ(y) < lex σ(x)} = ∪ k∈N A -(u k (x)).
Moreover, as the sequence of partitions (P k ) k∈N has a diameter that converges to zero, and thus separates points, the map σ is injective. Thus, we also have:

ψ(x) = λ(A + (x)) where A + (x) = {y ∈ [0, 1] : σ(y) ≤ lex σ(x)} = A -(x) ∪ {x}.
Remark that both A -(x) and A + (x) are Borel measurable.

Remark that for every k ∈ N, we have

A -(u k (x)) ⊂ A -(x) ⊂ A + (x) ⊂ A + (u k (x)).
In particular, for every u ∈ T , we have ψ(S u ) ⊂ [C -(u), C + (u)]; however ψ(S u ) is not necessarily an interval, but we shall see that λ

(ψ(S u )) = C + (u) -C -(u), i.e. ψ(S u ) is a.e. equal to [C -(u), C + (u)]. Remark that, as the sequence of partitions (P k ) k∈N is refining, we get that [C -(u), C + (u)] = ∪ v : p(v)=u [C -(v), C + (v)] for every u ∈ T \ {∂}.
As the diameter of the partitions (P k ) k∈N converges to zero, we have the following alternative formula for ψ:

ψ(x) = lim k→∞ C -(u k (x)) = lim k→∞ C + (u k (x)).
For every k ∈ N, the map x → C -(u k (x)) is a simple function (constant on each S ∈ P k and takes finitely-many values), and thus ψ is measurable as a limit of measurable maps.

We outline the rest of the proof. We first prove that ψ is measure-preserving. Secondly, we prove that ψ is a.e. bijective and construct its a.e. inverse map ϕ. Thirdly, we prove that (ϕ -1 (P k )) k∈N is a refining sequence of partitions. And lastly, we approximate almost everywhere the sequence of partitions (ϕ -1 (P k )) k∈N by a sequence of refining partitions composed of intervals.

We now prove that ψ is measure preserving. Remark that ψ(x) is a non-decreasing function of σ(x) for the total relation order < lex , i.e. ψ(y) ≤ ψ(x) if and only if σ(y) ≤ lex σ(x). Hence, ψ -1 ([0, ψ(x)]) = {y ∈ [0, 1] : σ(y) ≤ lex σ(x)}, and we have:

λ(ψ -1 ([0, ψ(x)])) = λ({y ∈ [0, 1] : σ(y) ≤ lex σ(x)}) = ψ(x).
Thus, to show that ψ is measure preserving we just need to show that ψ([0, 1]) is dense in [0, 1]. For every u ∈ T , as ψ(S u ) ⊂ [C -(u), C + (u)], we know that the interval [C -(u), C + (u)] contains at least one point of the form ψ(x). Remark that for all k ∈ N, we have [0

, 1] = ∪ u∈T :h(u)=k [C -(u), C + (u)]. Hence, as λ([C -(u), C + (u)]) = λ(S u ) ≤ diam(P h(u)
) for every u ∈ T , and as the diameter of the partitions (P k ) k∈N converges to zero, we know that each interval of positive length contains a point of the form ψ(x) for some x ∈ [0, 1], which implies that ψ([0, 1]) is indeed dense in [0, 1].

We now prove that ψ is a.e. bijective and construct its a.e. inverse map ϕ. Without loss of generality, assume that there is no set S u with null measure. Consider two distinct elements x, y ∈ [0, 1] such that σ(x) < lex σ(y). Assume that ψ(x) = ψ(y), and let N ∈ N be the last index k such that u k (x) = u k (y). Then, for every k > N , we have

u k (x) < lex u k (y), which implies that ψ(x) ≤ C + (u k (x)) ≤ C -(u k (y)) ≤ ψ(y); and thus ψ(x) = ψ(y) = C + (u k (x)) = C -(u k (y)),
which in turn implies that there is no node of T between u k (x) and u k (y). Remark that this situation is analogous to the terminating decimal versus repeating decimal situation. Hence, we proved that there is no node between u N +1 (x) and u N +1 (y) and that for every k > N , u k+1 (x) is the right-most child of u k (x), and u k+1 (y) is the left-most child of u k (y) (i.e. u k+1 (x) = u k (x)|O u k (x) | and u k+1 (y) = u k (y)1). Remind that the map σ is injective. Putting all of this together, we get that the set {(x, y) ∈ [0, 1] : ψ(x) = ψ(y), x < y} can be indexed by the nodes of T , and is thus at most countable. Hence, the map ψ is injective on a subset D ⊂ [0, 1] with measure one (indeed [0, 1] \ D is at most countable), and as ψ is measure preserving, we get that ψ(D) has measure one, and thus ψ is bijective from D to ψ(D), that is, ψ is a.e. bijective. We construct the map ϕ as the inverse map of ψ for x ∈ ψ(D) and ϕ(x) = 0 for x ∈ [0, 1] \ ψ(D). Without loss of generality, we assume that 0 ∈ D. Thus, ϕ is the a.e. inverse map of ψ, that is, ϕ

• ψ(x) = ψ • ϕ(x) = x for almost every x ∈ [0, 1].
We are left to prove that ϕ is measurable and measure preserving. As we saw that each point z ∈ [0, 1] as a pre-image ψ -1 (z) = {x ∈ [0, 1] : ψ(x) = z} at most countable (indeed of cardinal at most 2), thus [START_REF] Purves | Bimeasurable functions[END_REF] insures that ψ is bimeasurable (i.e. ψ is (Borel) measurable and for all Borel set B ⊂ [0, 1], ψ(B) is also a Borel set). Let B ⊂]0, 1] be a Borel set. We have that ϕ -1 (B) = ϕ -1 (B ∩ D) = ψ(B ∩ D) is a Borel set, where the first equality uses that ϕ([0, 1]) = D ∪ {0}, the second equality uses that ψ is the inverse of ϕ on D, and lastly we used that ψ is bimeasurable. We also have that ϕ

-1 (B ∪ {0}) = ϕ -1 (B) ∪ ([0, 1] \ ψ(D)) is a Borel set. Moreover, we have: λ(ϕ -1 (B)) = λ(ψ(B ∩ D)) = λ(ψ -1 (ψ(B ∩ D))) = λ(B ∩ D) = λ(B),
where we used that ϕ -1 (B) = ψ(B ∩ D) for the first equality, that ψ is measure preserving for the second equality, that ψ is bijective from D to ψ(D) for the third equality, and that D has measure one for the last equality. We also have:

λ(ϕ -1 (B ∪ {0})) = λ(ϕ -1 (B)) + λ([0, 1] \ ψ(D)) = λ(B) = λ(B ∪ {0}),
where we used that ϕ -1 (B) ⊂ ψ(D) and [0, 1] \ ψ(D) are disjoint sets for the first equality, that λ(ϕ -1 (B)) = λ(B) and that ψ(D) has measure one for the second equality. Hence, the map ϕ is measurable and measure preserving.

We now prove that (ϕ -1 (P k )) k∈N is a refining sequence of partitions. For k ∈ N, as P k is a finite partition of [0, 1], we have that ϕ -1 (P k ) = {ϕ -1 (S u ) : u ∈ T , h(u) = k} is also a finite partition of [0, 1]. Moreover, as (P k ) k∈N is a refining sequence of partitions, we get that the sequence of partitions (ϕ -1 (P k )) k∈N is also refining. Remark that the sets ϕ -1 (S u ) are not necessarily intervals, they are intervals minus some at most countable sets (this is similar to the unit line minus the Cantor set).

To finish the proof, we are left to construct a refining sequence of partitions made of intervals (Q k ) k∈N that agrees almost everywhere with the refining sequence of partitions (ϕ -1 (P

k )) k∈N . For u ∈ T , define R u = [C -(u), C + (u)[ (and R u = [C -(u), C + (u)] if u is the unique node such that v ≤ lex u for every v ∈ T with h(v) = h(u)).
As ψ is measure preserving, and as ψ(S u ) ⊂

[C -(u), C + (u)] with λ(S u ) = C + (u) -C -(u), we get that λ([C -(u), C + (u)] \ ψ(S u )) = 0.
As ϕ is the a.e. inverse map of ψ, we have that a.e.

1 ϕ -1 (Su) = 1 ψ(Su) = 1 [C -(u),C + (u)] = 1 Ru , i.e.
R u agrees almost everywhere with ϕ -1 (S u ). For k ∈ N, define the finite partition Q k = {R u : h(u) = k}. Then, by definition of the sets R u , the sequence of partitions (Q k ) k∈N is refining. This concludes the proof.

Remark 8.3 (The shrinking diameter assumption is important). Even if it is not stressed in [Lov12, Proof of Theorem 9.23], the measure preserving map ϕ (a fortiori an a.e. inversible one) in Lemma 8.2 cannot be obtained without any assumption on the refining sequence of partitions (P k ) k∈N (in our case, we assumed that their diameter converges to zero). Indeed consider the sequence of partitions where for every k ∈ N, P k is composed of the sets:

S k,j = [j2 -k-1 , (j + 1)2 -k-1 [ ∪ [1/2 + j2 -k-1 , 1/2 + (j + 1)2 -k-1 [, 0 ≤ j < 2 k ,
i.e. S k,j is the union of two dyadic interval translated by 1/2, (also add 1 to the set S k,0 to get a complete partition). Then, for every x ∈ [0, 1/2[, x and x + 1/2 belong to the same set of P k for every k ∈ N; in particular the diameter of the partitions (P k ) k∈N does not converge to zero. By contradiction, assume there exist a measure preserving map ϕ ∈ S[0,1] and a sequence of interval partitions (Q k ) k∈N such that for all k ∈ N and all set S k,j ∈ P k with 0 ≤ j < 2 k , there exists a interval set I k,j ∈ Q k such that a.e. 1 I k,j = 1 ϕ -1 (S k,j ) . In particular, the set I k,j must be an interval of length 2 -k . Hence, Q k is a dyadic partition with stepsize 2 -k , and thus the diameter of the partitions (Q k ) k∈N converges to zero. For every x ∈ [0, 1/2[, we get that diam(ϕ -1 ({x, so that almost everywhere:

x + 1/2})) ≤ diam(Q k ) = 2 -k for all k ∈ N; this implies that ϕ -1 ({x, x + 1/2}) is a singleton, i.e. either x ∈ ϕ([0, 1]) or x + 1/2 ∈ ϕ([0, 1]). Hence, we have λ([0, 1/2[∩ϕ([0, 1])) = λ([1/2, 1[\ϕ([0, 1])) and λ([0, 1/2[\ϕ([0, 1])) = λ([1/2, 1[∩ϕ([0, 1])). As λ([0, 1/2[) = λ([0, 1/2[∩ϕ([0, 1]))+λ([0, 1/2[\ϕ([0, 1])) = 1/2 because ϕ is measure preserving, we get that λ(ϕ([0, 1])) = λ([0, 1/2[∩ϕ([0, 1])) + λ([1/2, 1[∩ϕ([0, 1])) = 1/2,
W ′ n,k = (W n ) P n,k ϕn = (W ϕn n ) P ′ n,k = (W ′ ) P ′ n,k .
As d and d ′ are invariant, we have for every n, k

∈ N that d(W n , W n,k ) = d(W ′ n , W ′ n,k
), and similarly for d ′ . This insures that the signed measure-valued kernels (W ′ n ) n∈N and (W ′ n,k ) n∈N , k ∈ N, still satisfy (iii)-(iv). Remind that for a measure-valued kernel W and a measurepreserving map ϕ, δ ,m (W, W ϕ ) = 0. Hence, we can replace the signed measure-valued kernels

(W n ) n∈N and (W n,k ) n∈N , k ∈ N, by (W ′ n ) n∈N and (W ′ n,k ) n∈N , k ∈ N,
and assume that the partitions P n,k are made of intervals.

Step 2: There exists a subsequence (W n ℓ ) ℓ∈N such that for every k ∈ N and ǫ ∈ {+, -}, the subsequence (W ǫ n ℓ ,k ) ℓ∈N weakly converges, as ℓ → ∞, almost everywhere to a limit, say U ǫ k which is a stepfunction adapted to a partition with m k elements (some elements might be empty sets).

Fix some k ∈ N. The stepfunctions (W n,k = (W n ) P n,k ) n∈N all have the same number of steps m k . For n ∈ N, denote by P n,k = {S n,k,i : 1 ≤ i ≤ m k } the interval partition adapted to W n,k where the intervals are order according to the natural order on [0, 1] (note that some intervals might be empty, simply put them at the end). For n ∈ N and 1 ≤ i ≤ m k , let λ(S n,k,i ) denote the length of the interval S n,k,i ∈ P n,k . As the lengths of steps take values in the compact set [0, 1], there exists a subsequence of indices (n ℓ ) ℓ∈N such that for every 1 ≤ i ≤ m k , there exists s k,i ∈ [0, 1] such that lim ℓ→∞ λ(S n ℓ ,k,i ) = s k,i . Denote by P k = {S k,i : 1 ≤ i ≤ m k } the interval partition composed of m k intervals where the i-th interval S k,i has length s k,i (note that some intervals might be empty). Up to a diagonal extraction, we can assume that the convergence holds for every k ∈ N simultaneously. Remark that for all n, k ∈ N, the fact that P n,k+1 is a refinement of P n,k can be simply restated as linear relations on the interval lengths (λ(S n,k,i )) 1≤i≤m k and (λ(S n,k+1,i )) 1≤i≤m k+1 . As linear relations are preserved when taking the limit, we get that the partition P k+1 is a refinement of P k for all k ∈ N. We assume from now on that (W n ) n∈N and (W n,k ) n∈N , k ∈ N, are the corresponding subsequences.

For every n ∈ N, we decompose W n = W + n -W - n into its positive and negative kernel parts, see Lemma 3.3. For n, k ∈ N and ǫ ∈ {+, -}, we define

W ǫ n,k = (W ǫ n ) P n,k . In particular, remark that W n,k = W + n,k -W - n,k and for all ℓ ≥ k, that W ǫ n,k = (W ǫ n,ℓ ) P n,k . Let ǫ ∈ {+, -} and 1 ≤ i, j ≤ m k such that s k,i s k,j > 0 be fixed. For every n ∈ N, we have on S n,k,i × S n,k,j that W ε n,k = µ i,j,ǫ n,k ∈ M + (Z) with: µ i,j,ǫ n,k (•) = 1 λ(S n,k,i )λ(S n,k,j ) W ǫ n (S n,k,i × S n,k,j ; •).
We have that:

µ i,j,ǫ n,k ∞ ≤ W n ∞ ≤ C.
This gives that the sequence (µ i,j,ǫ n,k ) n∈N in M ± (Z) is bounded. We now prove it is tight. Let ε > 0. As lim n→∞ λ(S n,k,ℓ ) = s k,ℓ > 0 for ℓ = i, j, we deduce that there exists c > 0 such that for every n ∈ N large enough and ℓ = i, j, we have λ(S n,k,ℓ ) > c. Set ε ′ = c 2 ε. As the sequence (W n ) n∈N in W ± is tight, there exists a compact set K ⊂ Z such that for every n ∈ N, M Wn (K c ) ≤ ε ′ . Hence, for every n ∈ N large enough, we have:

µ i,j,ǫ n,k (K c ) ≤ 1 λ(S n,k,i )λ(S n,k,j ) M Wn (K c ) ≤ ε.
This gives that the sequence (µ i,j,ǫ n,k ) n∈N in M + (Z) is bounded and tight, and thus by Lemma 2.8, it has a convergent subsequence. By diagonal extraction, we can assume there is a subsequence (W n ℓ ) ℓ∈N such that for all k ∈ N, all 1 ≤ i, j ≤ m k such that s k,i s k,j > 0, and all ǫ ∈ {+, -}, the subsequence (µ i,j,ǫ n ℓ ,k ) ℓ∈N weakly converges to a limit say µ i,j,ǫ k . Define the stepfunction U ǫ k ∈ W + adapted to the partition P k which is equal to µ i,j,ǫ k on S k,i ×S k,j (if s k,i s k,j = 0, set µ i,j,ǫ k = 0). We have in particular obtained that, for every k ∈ N, the subsequence (W ǫ n ℓ ,k ) ℓ∈N weakly converges a.e. to U ǫ k which is a stepfunction adapted to a partition with m k elements; this implies that the subsequence (W n ℓ ,k ) ℓ∈N also weakly converges a.e. to U k = U + k -U - k . We now assume that (W n ) n∈N is such a subsequence. With this convention, notice that for all k, n ∈ N and ǫ ∈ {+, -}:

(27) U ǫ k ∞ ≤ sup n∈N W ǫ n,k ∞ ≤ sup n∈N W n ∞ = C < +∞.
Step 3: There exists a subsequence of (U k ) k∈N which weakly converges to a limit U ∈ W ± almost everywhere on [0, 1] 2 . The proof of this step is postponed to the end. Without loss of generality we still write (U k ) k∈N for this subsequence.

Step 4: We have lim n→∞ δ (U, W n ) = lim n→∞ δ ′ (U, W n ) = 0. Let ε > 0. As the cut distances d is smooth, we deduce from Step 3, that for k large enough d(U, U k ) ≤ ε. By hypothesis (iii) on the sequence (W n,k ) n∈N , we also have that for k large enough d(W n , W n,k ) ≤ ε. For such large k, as by step 2 the sequence (W n,k ) n∈N weakly converges almost everywhere to U k , and again as the cut distances d is smooth, there is a n 0 such that for every n ≥ n 0 , d(U k , W n,k ) ≤ ε. Then for all n ≥ n 0 , we have:

δ (U, W n ) ≤ δ (U, U k ) + δ (U k , W n,k ) + δ (W n,k , W n ) ≤ d(U, U k ) + d(U k , W n,k ) + d(W n,k , W n ) ≤ 3ε.
This gives that lim n→∞ δ (W n , U ) = 0.

If we consider a second distance d ′ as in the lemma, then similarly lim n→∞ δ ′ (W n , U ) = 0.

Proof of Step 3. Assume that the claim is true for measure-valued kernels. Then, if (U k ) k∈N is a sequence of signed-measure valued kernels, applying the claim to (U ǫ k ) k∈N , for ǫ ∈ {+, -}, we get a measure-valued U ǫ ∈ W + such that the sequence (U ǫ k ) k∈N weakly conveges a.e. to U ǫ . Thus, the sequence (U k ) k∈N weakly conveges a.e. to U = U + -U -.

Hence, we are left to prove the claim for measure-valued kernels. The proof is divided in four steps. The first three steps also work for signed-measure valued kernels, but the last argument of step 3.d. only works for measures.

Step 3.a: The sequence (U k ) k∈N inherit the tightness property from the sequence (W n ) n∈N . Let ε > 0. Since the sequence (W n ) n∈N is tight, there exists a compact set K ⊂ Z such that for every n ∈ N, we have M Wn (K c ) ≤ ε. Remark that:

M W n,k =
1≤i,j≤m k λ(S n,k,i )λ(S n,k,j )µ i,j n,k = M Wn and M U k = 1≤i,j≤m k s k,i s k,j µ i,j k .

For all k ∈ N and 1 ≤ i, j ≤ m k , as the sequence (µ i,j n,k ) n∈N weakly converges to µ i,j k , using [Bog18, Theorem 2.7.4] with the open subset K c ⊂ Z, we get that µ i,j k (K c ) ≤ lim inf n→∞ µ i,j n,k (K c ). As lim n→∞ λ(S n,k,i ) = s k,i for all 1 ≤ i ≤ m k , and summing those bounds, we get:

M U k (K c ) ≤ lim inf n→∞ M W n,k (K c ) = lim inf n→∞ M Wn (K c ) ≤ ε.
Consequently, the sequence (U k ) k∈N is tight.

Step 3.b: Convergence of the measures Ûk in M + ([0, 1] 2 × Z) defined for k ∈ N as:

(28) Ûk (dx, dy, dz) = U k (x, y; dz) λ 2 (dx, dy).

Since the sequence (M U k ) k∈N in M + (Z) is tight, for all ε > 0, there exists a compact set K ⊂ Z such that for every k ∈ N, M U k (K c ) ≤ ε; thus Ûk ( Kc ) = M U k (K c ) ≤ ε where K = [0, 1] 2 ×K is a compact subset of [0, 1] 2 × Z, that is, the sequence ( Ûk ) k∈N in M + ([0, 1] 2 × Z) is tight. The sequence ( Ûk ) k∈N is also bounded as Ûk ∞ ≤ U k ∞ ≤ C thanks to (27). Hence, using Lemma 2.8, there exists a subsequence ( Ûk ℓ ) ℓ∈N of the sequence ( Ûk ) k∈N that converges to some measure, say Û , in M + ([0, 1] 2 × Z). Remark that, when considering the subsequence of indices (k ℓ ) ℓ∈N , the subsequences (W n,k ℓ ) ℓ∈N , n ∈ N, still satisfy properties (i)-(iv) of Lemma 8.1, and for all ℓ ∈ N, the sequence (W n,k ℓ ) n∈N still weakly converges to U k ℓ . Without loss of generality, we now work with this subsequence and thus write k instead of k ℓ .

Step 3.c: The measure Û (dx, dy, dz) can be disintegrated w.r.t. λ 2 (dx, dy) giving us an element of W + . To prove this, we need the following disintegration theorem for measures, see [Kal17, Theorem 1.23] (stated in more the general framework of Borel spaces) which generalizes the disintegration theorem for probability measures [Kal02, Theorem 6.3]. The notation µ ∼ ν for two measures µ and ν means that µ ≪ ν and ν ≪ µ, where µ ≪ ν means that µ is absolutely continuous w.r.t. ν. Lemma 8.4 (Disintegration theorem for measures, [Kal17, Theorem 1.23]). Let ρ be a measure on S × T , where S is a measurable space and T a Polish space. Then there exist a measure ν ≡ ρ(• × T ) on S and a probability kernel µ : S → M 1 (T ) such that ρ = ν ⊗ µ (i.e. ρ(ds, dt) = ν(ds)µ(s; dt)). Moreover, the measures µ s = µ(s; •) are unique for ν-a.e. s ∈ S.

Using Lemma 8.4 with S = [0, 1] 2 and T = Z, we get that there exists a probability kernel U ′ in W 1 such that: Û(dx, dy, dz) = U ′ (x, y; dz) π(dx, dy), where π = Û (• × Z) is a measure on [0, 1] 2 . We now need to prove that π ≪ λ 2 . By contradiction, assume this is false, then there exists a measurable set A ∈ B([0, 1] 2 ) such that λ 2 (A) = 0 and π(A) > 0. As the measure A U ′ (x, y; •) π(dx, dy) is not null, there exists f ∈ C b (Z) such that A U ′ (x, y; f ) π(dx, dy) = 0. As the sequence ( Ûk ) k∈N weakly converges to Û in M + ([0, 1] 2 × Z) by step 3.b, we have that the sequence of measures Ûk (dx, dy; f ) = U k (x, y; f ) λ 2 (dx, dy) weakly converges as k → ∞ to Û (dx, dy; f ) = U ′ (x, y; f ) π(dx, dy) in M + ([0, 1] 2 ). Moreover, as the maps x, y → U k (x, y; f ) are uniformly bounded (by f ∞ U k ∞ ≤ C f ∞ , see (27)), they are also uniformly integrable (w.r.t. λ 2 ), and applying [Bog07a, Corollary 4.7.19] there exist a subsequence (U k ℓ ) ℓ∈N and a bounded function g f on [0, 1] 2 such that for every bounded measurable function h ∈ L ∞ ([0, 1] 2 ), we have: lim ℓ→∞ U k ℓ (x, y; f )h(x, y) λ 2 (dx, dy) = g f (x, y)h(x, y) λ 2 (dx, dy).

In particular, the sequence of measures (U k ℓ (x, y; f ) λ 2 (dx, dy)) ℓ∈N weakly converges to the measure g f (x, y) λ 2 (dx, dy), which imposes the equality between measures: Û (dx, dy, f ) = U ′ (x, y; f )π(dx, dy) = g f (x, y) λ 2 (dx, dy).

Hence, taking h = 1 A , we get: Û(A, f ) = A U ′ (x, y; f )π(dx, dy) = A g f (x, y)λ 2 (dx, dy) = 0, which yields a contradiction. Consequently, the measure π is absolutely continuous w.r.t. λ 2 , with density still denoted by π, and we set λ 2 -a.e. on [0, 1] 2 : (29) U (x, y; dz) = π(x, y) U ′ (x, y; dz) and thus Û (dx, dy, dz) = U (x, y; dz) λ 2 (dx, dy).

Step 3.d: The sequence (U k ) k∈N weakly converges to U almost everywhere on [0, 1] 2 . Recall that by construction, the stepfunction U k is adapted to the partition P k defined in Step 2, and that P k+1 is a refinement of P k . A closer look at Step 2 yields that for all ℓ ≥ k, since W n,k = (W n,ℓ ) P n,k , we also get:

(30) U k = (U ℓ ) P k .
We prove (30) for ℓ = k + 1, the other cases follow by As P n,k+1 is a refinement of P n,k , we already know that U k and (U k+1 ) P k are both stepfunctions adapted to the finite partition P k . Thus, we only need to verify that U k and (U k+1 ) P k take the same value on each step. For every n ∈ N, the fact that W n,k = (W n,k+1 ) P n,k implies that for all 1 ≤ i, j ≤ m k such that λ(S n,k,i )λ(S n,k,j ) > 0, we have:

µ n,k i,j = i ′ ∈Ii,j ′ ∈Ij λ(S n,k+1,i ′ )λ(S n,k+1,j ′ ) λ(S n,k,i )λ(S n,k,j ) µ n,k+1 i ′ ,j ′ , and this equation is preserved when taking the limit n → ∞, which gives us:

µ k i,j = i ′ ∈Ii,j ′ ∈Ij
s k+1,i ′ s k+1,j ′ s k,i s k,j µ k+1 i ′ ,j ′ , for all 1 ≤ i, j ≤ m k such that s k,i s k,j > 0.

This proves that the stepfunctions U k and (U k+1 ) P k take the same value on each step S k,i × S k,j with positive size s k,i s k,j > 0 (on a step with null size s k,i s k,j = 0, U k and (U k+1 ) P k are both equal to the null measure). This gives that U k = (U k+1 ) P k . Let f ∈ C b (Z) be a bounded continuous function, and X, Y be independent uniform random variables on [0, 1]. Then (30) and (27) imply that the sequence N f = (N f k = U k (X, Y ; f )) k∈N is a martingale bounded by C f ∞ for the filtration (F k ) k∈N , where the σ-field F k is generated by the events {X ∈ S k,i } ∩ {Y ∈ S k,j } for 1 ≤ i, j ≤ m k and S k,ℓ ∈ P k . By the martingale convergence theorem, the martingale N f is almost surely convergent, that is, the sequence (U k [f ]) k∈N converges λ 2 -a.e. to a bounded measurable function u f . Let g : [0, 1] 2 → R be a bounded measurable function. We get: where we used the definition (29) of U for the first equality, that ( Ûk ) k∈N weakly converges to Û for the second, the definition (28) of Ûk for the third, and the convergence of the martingale N f for the last. Since g is arbitrary, we deduce that λ 2 -a.e. U (•, •; f ) = u f and thus that the sequence (U k [f ]) k∈N converges λ 2 -a.e. to U [f ]. Applying this result for all f ∈ F = (f m ) m∈N a convergence determining sequence (with the convention f 0 = 1), we deduce that the sequence (U k ) k∈N weakly converges to U almost everywhere on [0, 1] 2 . Remind from Section 2 that convergence determining sequences exist only for measures and not for signed measures in general, this is why we worked with measures in Step 3. This ends the proof of Step 3, and thus ends the proof of the lemma.

We are now ready to prove Theorem 5.1.

Proof of Theorem 5.1. We first prove Point (i) on W ± (the proof on W 1 is similar). Since the distance d is weakly regular and the sequence (W n ) n∈N is uniformly bounded and tight in W ± , we can construct inductively for every n ∈ N a sequence (P n,k ) k∈N of partitions of [0, 1] such that hypothesis (i)-(iii) of Lemma 8.1 are satisfied: P n,k+1 being obtained by applying the weak regularity property (see Definition 4.10-(i)) with starting partition Q n,k = P n,k ∧ D k , where D k is the dyadic partition with stepsize 2 -(k+1) . (We may assume that the partitions P n,k for all n ∈ N have the same size m k by adding empty sets.) Then as d is also invariant and smooth on W ± , the first part of Lemma 8.1 directly gives Point (i).

Before proving Point (ii), we first need to prove the following lemma.

Lemma 8.5 (Compactness theorem for W M ). Let d be an invariant, smooth and weakly regular distance on W 1 (resp. W + or W ± ). Let M be a convex and weakly closed subset of M 1 (Z) (resp. M + (Z) or M ± (Z)). Let (W n ) n∈N be a sequence of M-valued kernels which is tight and uniformly bounded. Then, (W n ) n∈N has a subsequence that converges for δ to some M-valued kernel.

Proof. First remark that, as M is convex, the image of W M by the stepping operator W → W P , where P is a finite partition of [0, 1], is a subset of W M . Hence, a close look at the proof of Lemma 8.1 (the partitions are constructed as in the proof of Point (i) from Theorem 5.1), and using the notation therein, shows that, up to taking subsequences, one can take the stepping kernels W n,k and U k in W M , such that (U k ) k∈N weakly converges to U a.e. and the subsequence (W n ℓ ) ℓ∈N converges to U w.r.t. δ . Since U k (x, y; •) ∈ M weakly converges to U (x, y; •) for almost every x, y ∈ [0, 1] and since M is weakly closed (and thus sequentially weakly closed), we deduce that U (x, y; •) belongs to M for almost every x, y ∈ [0, 1]. This means that U ∈ W M .

We prove Point (ii) for M ⊂ M ± (Z) (the proof for M ⊂ M 1 (Z) is identical). The fact that W M and W M are convex is clear as M is convex. Let (W n ) n∈N be a sequence of elements of W M . Since M is convex, we deduce that (M Wn ) n∈N is a sequence in M. As M is sequentially compact for the weak topology, M is tight and bounded by Lemma 2.8, and thus the sequence (W n ) n∈N is tight and uniformly bounded (remind Definition 4.7). Hence, using Lemma 8.5, we get that from any sequence in W M , we can extract a subsequence which converges for δ to an element in W M . This implies that ( W M , δ ) is compact.

Point (iii) is a direct consequence of Point (ii) as if Z is compact, so is M 1 (Z).

Proof of Point (iii) from Proposition 5.2. We prove Point (iii). The fact that W M and W M are convex is clear as M is convex. To prove that W M is closed, we consider a sequence (W n ) n∈N in W M that converges for δ ,m to some W ∈ W ± . As (W n ) n∈N is a Cauchy sequence for δ ,m , by Lemma 4.9, (M Wn ) n∈N is a Cauchy sequence for d m and thus is tight. Hence, (W n ) n∈N is uniformly bounded and tight. Applying Lemma 8.5, there exists a subsequence (W n k ) k∈N of the sequence (W n ) n∈N which converges for δ ,m to some M-valued kernel U ∈ W M . But as a subsequence, (W n k ) k∈N must also converge for δ ,m to W . This implies that W = U is a M-valued kernel.

In order to prove Theorem 5.5, we first prove a lemma that allows to construct the partitions needed to use Lemma 8.1. Lemma 8.6 (Construction of partitions for two distances). Let d and d ′ be two distances on W 1 (resp. W + or W ± ) which are invariant, smooth, weakly regular and regular w.r.t. the stepping operator (see Definitions 3.10 and 4.10). Let (W n ) n∈N be a sequence in W 1 (resp. W + or W ± ) which is tight (resp. uniformly bounded and tight). Then, there exists sequences (P n,k ) k∈N , n ∈ N, of partitions of [0, 1] such that hypothesis (i)-(iv) of Lemma 8.1 are satisfied.

Proof. We prove the result on W ± (the proof on W 1 and W + is similar). To simplify notations, write d 1 = d and d 2 = d ′ . We proceed by induction on k ∈ N ∪ {-1}. For every n ∈ N, set P n,-1 = {[0, 1]} the trivial partition with size 1. Let k ∈ N and assume that we have already constructed partitions (P n,k-1 ) n∈N that have the same size m k-1 . Now we proceed to construct partitions (P n,k ) n∈N that satisfy hypothesis (i)-(iv).

Set C = sup n∈N W n ∞ , which is finite as the sequence (W n ) n∈N is uniformly bounded. As d i , with i = 1, 2, are regular w.r.t. the stepping operator, there exists a finite constant C 0 > 0 such that for every W, U ∈ W ± , with W ∞ ≤ C and U ∞ ≤ C, and U a stepfunction adapted to a finite partition Q:

(31) d i (W, W Q ) ≤ C 0 d i (W, U ).
Set ε = 1/C 0 (k + 1). Since d i , with i = 1, 2, are weakly regular and the sequence (W n ) n∈N is tight and uniformly bounded, there exists r k ∈ N * , such that for every n ∈ N, there exists a partition R i n,k of [0, 1] that refines Q n,k = P n,k-1 ∧ D k , where D k is the dyadic partition with stepsize 2 -k , such that:

(32) |R i n,k | ≤ r k |Q n,k | ≤ 2 k r k |P n,k-1 | and d i W n , (W n ) R i n,k ≤ ε.
(Indeed, a close look at the proof shows that P n,k-1 refines D k-1 by construction, thus Q n,k cuts each set of P n,k-1 in at most 2 sets, and we get |Q n,k | ≤ 2|P n,k-1 |.) Now, let P n,k be the common refinement of R 1 n,k and R 2 n,k ; it is a refinement of P n,k-1 , has diameter at most 2 -k and size:

|P n,k | ≤ 2 2k r 2 k |P n,k-1 | 2 = 2 2k r 2 k m 2 k-1 .
If necessary, by completing P n,k with null sets, we may assume that |P n,k | = m k , where m k = 2 2k r 2 k m 2 k-1 . As (W n ) R i n,k is a stepfunction adapted to the partition P n,k , we deduce from (31) and (32) that for i = 1, 2 and n ∈ N:

d i (W n , (W n ) P n,k ) ≤ C 0 d i W n , (W n ) R i n,k ≤ C 0 ε = 1 k + 1 • -W M the

Proposition 4 .

 4 13 (Weak regularity of d ,m ). Let d m be a quasi-convex distance on M ǫ (Z), with ǫ ∈ {+, ±}, which is sequentially continuous w.r.t. the weak topology. Then, the cut distance d ,m on W ǫ 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 ,P and the cut norms • ,F , • ,KR and • ,FM . Corollary 4.14 (Weak regularity of usual distances and norms). The cut norms • ,F , • ,KR and • ,FM (resp. the cut distance d ,P ) on W ± (resp. W + ) are invariant, smooth, weakly regular and regular w.r.t. the stepping operator.

5. 3 .

 3 Completeness. Let d m be a distance on M ≤1 (Z) or M + (Z). We shall consider a slight modification of the cut distances d ,m and δ ,m to achieve completeness. Recall the measure M W ∈ M + (Z) defined by (16) associated to W ∈ W + . Definition 5.8 (The cut distances d c ,m and δ c ,m ). Let d m and d c be two distances on M ǫ (Z) with ǫ ∈ {≤ 1, +}. We define the cut distance d c

  Lemma 5.9 (Topological equivalence of δ ,m and δ c ,m ). Let d m and d c be two distances on M ǫ (Z), with ǫ ∈ {≤ 1, +}, such that d c is continuous w.r.t. d m and that d ,m is (invariant and) smooth on W ǫ . Then, the cut distance d c ,m is invariant and smooth and δ c ,m is a distance on W ǫ . Moreover, the distances d ,m and d c ,m (resp. δ ,m and δ c ,m ) induce the same topology on the space W ǫ (resp. W ǫ ).

  , y) U (x, y; f ) λ 2 (dxdy) = [0,1] 2 ×Z g(x, y) f (z) Û(dx, dy, dz) = lim k→∞ [0,1] 2 ×Z g(x, y) f (z) Ûk (dx, dy, dz) = lim k→∞ E [g(X, Y )U k (X, Y ; f )] = [0,1] 2 g(x, y) u f (x, y) λ 2 (dxdy),

  set of M-valued kernels with M ⊂ M ± (Z) -W 1 the set of unlabeled probability-graphons -W + the set of unlabeled measure-valued kernels -W ± the set of unlabeled signed measurevalued kernels -W M the set of unlabeled M-valued kernelsKernels and graphons-W + and W -the positive and negative part ofW ∈ W ± -|W | = W + + W - -W (A; •) = A W (x, y; •) dxdy for A ⊂ [0, 1] 2 -W [f ](x, y) = W (x, y; f ) for f ∈ C b (Z) -W P the stepping of W w.r.t. a partition P -W ∞ := sup x,y∈[0,1] W (x, y; •) ∞ -M W (dz) = |W |([0, 1] 2 ; dz) -W G the probability-graphon associated to a M 1 (Z)-graph or a weighted graph G -H(k, W ) the M 1 (Z)-graph with k vertices sampled from W ∈ W 1 -G(k, W ) the M 1 (Z)-graph with k vertices sampled from W ∈ W 1 -F g afinite graph whose edges are decorated with functions in C b (Z) -t(F g , W ) = M F W (g) the homomorphism density of F g in W Distances/norms on graphon spaces -d ,m the cut distance associated to d m -N ,m the cut norm associated to N m -δ the unlabeled distance associated to an arbitrary distance d -δ ,m the unlabeled cut distance associated to d ,m or N ,m -• ,R the cut norm for real-valued kernels -• + ,R the positive part of the cut norm for real-valued kernels Definitions weak isomorphism of kernels and graphons in Definition 3.16 on page 16 tightness for sets of kernels or graphons in Definition 4.7 on page 23 invariant and smooth for a distance d on graphon spaces in Definition 3.10 on page 14 weakly regular and regular w.r.t. the stepping operator for a distance d on graphon spaces in Definition 4.10 on page 24 ✂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  • KR and • FM on M + (Z); and • KR and • FM are uniformly continuous w.r.t. d P on M ≤1 (Z).

  kernel, we can apply the closed martingale theorem (as (W [f k ]) Pn can be viewed as a conditional expectation, see Remark 4.2), and we get that lim n→∞

  Lemma 5.3 (Comparison of topologies induced by d ,m and δ ,m ). Let d m and d m ′ be two distances on M ≤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 ≤1 (Z)). Then, we have the following properties. (i) The distance d ,m ′ is uniformly continuous w.r.t. d ,m on W 1 . In particular d ,m induces a finer topology than d ,m ′ on W 1 . (ii) If the distance d ,m on W 1 is smooth, then the distance d ,m ′ is also smooth and δ ,m

′ is uniformly continuous w.r.t. δ ,m . In particular, δ ,m induces a finer topology than δ ,m ′ on W 1 . (iii) If the distance d ,m on W 1 is weakly regular, then the distance d ,m ′ is also weakly regular.

  • KR and • 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 ,F induces the same topology on the space of labeled probability-graphons W 1 as the one induced by d ,P , d ,FM or d ,KR . (Topological equivalence of the cut distances associated to d P , • FM , • KR and • F ). The cut distances d ,P on W + and d ,KR , d ,FM and d ,F on W ± 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 • ,FM and • ,KR (resp. the cut distances δ ,FM and δ ,KR ) are metrically equivalent on W ± (resp. W ± ). (ii) The cut distances δ ,FM , δ ,KR and δ ,P (resp. d ,FM , d ,KR and d ,P ) are uniformly continuous w.r.t. one another, and thus induce the same topology on W 1 (resp. W 1 ) and on every uniformly bounded subset of W + (resp. W + ). (iii) The cut distances δ ,FM , δ ,KR , δ ,P and δ ,F , for every choice of the convergence determining sequence F , induce the same topology on W 1 . Rubinshtein distances. As d P is uniformly continuous w.r.t. d KR (see Lemma 3.22), applying Lemma 5.3 (remind Corollary 4.14) with Remark 5.4 in mind, we get that δ ,P (resp. d ,P ) is uniformly continuous w.r.t. δ ,KR (resp. d ,KR ) on every uniformly bounded subset of W + (resp. W + ) As d KR is also uniformly continuous w.r.t. d P (see Lemma 3.22), applying again Lemma 5.3, we have that δ ,KR (resp. d ,KR ) is uniformly continuous w.r.t. δ ,P (resp. d ,P ) on every uniformly bounded subset of W + (resp. W + ).

	consequence of (9). We now prove Point (ii). Thanks to (9) and Point (i), it is enough to consider only the Prohorov and the Kantorovitch-Point (iii) is an immediate consequence of Corollary 4.14 and Theorem 5.5, together with Corollary 5.6 Proof. The first part of the corollary is a re-statement of Corollary 4.14. Point (i) is an immediate Point (ii).

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 W 1 .

	7.4. Proposition 7.10 (Characterization of equality for δ ,m ). Let U, W ∈ W 1 be two probability-graphons. The following properties are equivalent:
	(i) δ ,m (U, W ) = 0 for some (and hence for every) choice of the distance d m on M ≤1 (Z) such that the cut distance d ,m on W 1 is (invariant) smooth. (ii) There exist ϕ, ψ ∈ S[0,1]
	which concludes the proof.

  which contradicts the fact that ϕ is measure preserving. Now, for every n ∈ N, applying Lemma 8.2 to (P n,k ) k∈N and W n , we get a measure-preserving map ϕ n and a refining sequence of partitions (P ′ n,k ) k∈N made of intervals such that for all k ∈ N, and all set R ∈ P ′ n,k there exists a set S ∈ P n,k such that a.e. 1 R = 1 ϕ -1 n (S) . In particular, for all k ∈ N, the sequence of partitions (P n,k ) k∈N still satisfy (i)-(ii). Set W ′

	n = W ϕn n and W ′ n,k = W ϕn n,k

Acknowledgement

We thank Pierre-André Zitt for some helpful discussion in particular on Lemma 3.20. ✂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Hence, for every n ∈ N, the partition P n,k satisfies the hypothesis (i)-(iv) of Lemma 8.1. Thus, the induction is complete.

Proof of Theorem 5.5. Let d m and d m ′ be as in Theorem 5.5.

Let (W n ) n∈N be a sequence of probability-graphons that converges to some W ∈ W 1 for δ ,m . By Lemma 4.9, the sequence of probability measure (M Wn ) n∈N converges to M W for the distance d m . As d m induces the weak topology on M ≤1 (Z), we have that the sequence (M Wn ) n∈N is tight, and thus the sequence (W n ) n∈N is also tight (remind Definition 4.7). The sequence (W n ) n∈N is also uniformly bounded as a sequence in W 1 . Applying Lemma 8.6 with the distances d = d ,m and d ′ = d ,m ′ , which are invariant, smooth, weakly regular and regular w.r.t. the stepping operator, we get sequences of partitions (P n,k ) k∈N , n ∈ N, that satisfy hypothesis (i)-(iv) of Lemma 8.1. We then deduce from the last part of Lemma 8.1 that any subsequence of (W n ) n∈N has a further subsequence which converges to the same limit for both δ ,m and δ ,m ′ , this limit must then be W . This implies that the sequence (W n ) n∈N converges to W for δ ,m ′ .

The role of d m and d m ′ being symmetric, we conclude that the distances δ ,m and δ ,m ′ induce the same topology on W 1 .

Index of notation

Measures