Juan Alvarado
email: juan.alvarado@cs.kuleuven.be

Yuyi Wang
email: yuwang@ethz.ch

Jan Ramon
email: jan.ramon@inria.fr

Limits of Multi-relational Graphs

Keywords: Large multigraph, Graphon Theory, Markov Logic Network, Large Deviation Principle

Graphons are limits of large graphs. Motivated by a theoretical problem from statistical relational learning, we develop a generalization of basic results from graphon theory into the "multi-relational" setting. We show that their multi-relational counterparts, which we call multi-relational graphons, are analogically limits of large multi-relational graphs. We extend the cutdistance topology for graphons to multi-relational graphons and prove its compactness and the density of multi-relational graphs in this topology. In turn, compactness enables to prove the large deviation principle for Multi-Relational Graphs (LDP) which enables to prove the most typical random graphs constrained by marginal statistics converge asymptotically to constrained multirelational graphons with maximum entropy. We show the equivalence between a restricted version of Markov Logic Network and Multi-Relational Graphons with maximum entropy.

Introduction

Statistical Relational Learning (SRL, [START_REF] Getoor | Introduction to statistical relational learning[END_REF]) deals with learning probabilistic models from relational data. Many popular SRL frameworks, for instance, Markov Logic Networks (MLNs, Richardson and Domingos [START_REF] Richardson | Markov logic networks[END_REF]), use weighted logical formulas to encode statistical regularities that hold for the considered problem. Typically, maximum (pseudo-)likelihood estimation is used to compute the weights of the formulas based on training data, which is often a single large example (e.g. a social network). This is problematic because the weights that are learned from this single training example are in general not optimal for examples of different sizes. Jain et al. [START_REF] Jain | Extending Markov logic to model probability distributions in relational domains[END_REF] show a detailed example of a MLN that does not scale on data from different sizes. This turns out to be a fundamental problem, which cannot simply be solved by rescaling the weights. Using statistical terminology, the issue is that models such as MLNs are not projective. Shalizi et al. [START_REF] Shalizi | Consistency under sampling of exponential random graph models[END_REF] show that projectivity is essential condition to ensure consistency of estimated probability distribution along samples of different sizes. Jaeger et al. [START_REF] Jaeger | Inference, learning, and population size: Projectivity for SRL models[END_REF] shows some examples of non-projective relational models. An alternative approach to modelling relational structures using MLNs studied in detail in Kuzelka et al. [START_REF] Kuželka | Relational marginal problems: Theory and estimation[END_REF] exploits the fact that MLNs can be seen as maximum-entropy models constrained by so called relational marginal statistics. Here, the relational marginal statistics are given by firstorder logic formulas. In particular, given a first-order logic formula α without quantifiers, the respective relational marginal statistic, denoted t(α, ω), is the probability that a randomly drawn grounding of the formula α will be satisfied in a given relational structure ω (here, grounding of a formula is a formula obtained by replacing all its variables by constants). For instance, if α = friends(x, y) then the respective relational marginal statistic "measures" the density of the friends relation. Now suppose that we are given formulas α 1 , α 2 , . . . , α m and real numbers t 1 , t 2 , . . . , t m and we formulate the following optimization problem: find the distribution P (ω) on possible worlds over some given set of domain constants ∆ that (i) satisfies E ω∼P [t(α i , ω)] = t i for each of the formulas α 1 , . . . , α m and (ii) has maximum entropy among all distributions satisfying (i). When ω has infinite number of nodes, Radin et al. [START_REF] Radin | Phase transitions in a complex network[END_REF] show, in the context of Exponential Random Graphs (ERGM), that the most typical worlds ω of MLN, described by one binary and symmetry relation, are the graphons with maximum entropy constrained by t(α i , W ) = t i where W is a graphon.

Equipped with the view of MLNs as maximum-entropy models constrained by relational marginal statistics, the following problem naturally arises when approximately modelling very large relational structures. Let us fix a set of first order-logic formulas α 1 , α 2 , . . . , α m and the values t 1 , t 2 , . . . , t m and let us consider the same maximum entropy problem as in the previous paragraph, however, this time we let |∆| → ∞. What can we say about the resulting distribution in the limit? It turns out this is a difficult question and at the moment we do not have much to say about it. However, we can take a look into the theory of graphons [START_REF] Lovász | Large networks and graph limits[END_REF] and see what it can offer for problems like this one.

Graphon theory deals with limits, called graphons, of large dense graphs. A graphon is any symmetric function W : [0, 1] 2 → [0, 1]. From a procedural point of view, a graphon can be seen as a probabilistic model for graphs. To sample a random graph G(n, W ) on n vertices from a given graphon W . The 8.3, we show an example of a MLN that is modeled by multi-relational graphon based on friends and acquaintances relations. Our results may also be potentially useful in the context of the very recently introduced framework called the AHK model [START_REF] Jaeger | Inference, learning, and population size: Projectivity for SRL models[END_REF], which is a rather general probabilistic model for relational data. Thus a natural open question would be the generalization of our results about the limits of constrained sequences of random undirected multirelational graphs to arbitrary-arity relational data. This generalization would give us a principled way to learn AHK models. This paper is organized as follows. Section 2 introduces Markov logic, multirelational graphs, and graphon theory. Section 3 introduces multi-relational graphon space, graph homomorphism density, and cut-distance topology. Section 4 proves the compactness of cut-distance topology. Section 5 is devoted to prove that the set of multi-relational graphs is dense in the cut-norm topology. To prove that, we extend the sampling lemmas given by Lovász in his book [START_REF] Lovász | Large networks and graph limits[END_REF]. Section 6 introduces the large deviation principle for multirelational Erdős-Rényi random graphs. This principle enables proving that the most typical infinite random graphs constrained by any closed region in the space of multi-relational graphons are solutions of a maximum entropy problem. Section 7 contains the largest proofs of this paper. In this section, we need to introduce yet more mathematical preliminaries oriented to show Alaoglu's Theorem. This theorem states that the unit ball in the dual space of any topological vector space is compact. This theorem enables proving an alternative definition of cut-distance based on couplings. With this alternative definition, the large deviation principle is proven. Section 8 discusses the equivalence of probabilistic models based on multi-relational graphons and a restricted version of MLNs. After that, we show an example of the equivalence between multi-relational graphons and MLNs. In this section, we also show why multi-relational graphon models based on Boltzmann entropy are more natural than maximum entropy models based on Gibbs entropy for modelling multi-relational data. Section 9 describes the relationship to other works with multi-relational graphons. First, we show how multi-relational graphs limits are a special case of Compact Decorated graphs due to Lovász and Szegedy [START_REF] Lovász | Limits of compact decorated graphs[END_REF]. Second, we show the AHK model is a generalization of multi-relational graphons. Third we discuss the work of constrained graphons with maximum entropy done in the field of Statistical Mechanics. These works can be seen as a special case of constrained multi-graphons with maximum entropy. Finally, Section 10 gives the conclusions of this paper.

Background

In this section we cover the necessary background material. Some basic concepts of Topology and Measure Theory are also reviewed in the appendix.

Basic Notation

We use 1 X to denote the indicator function, i.e., if x ∈ X then 1 X (x) = 1 else 1 X (x) = 0. For any positive integer n, we denote by [n] the set of all positive integers smaller than or equal to n. We denote by ⌈x⌉ the least integer greater than or equal to x. For a function f : X × X → Z, we denote by f ⊤ the function which is its transpose, i.e., ∀x, y ∈ X :

f ⊤ (x, y) = f (y, x). A sequence x : N → X is denoted by (x i ) ∞ i=1 .

First Order Logic

We assume a restricted function-free first-order language defined by a set of constants ∆, a set of variables V and a set R of binary predicates. Variables start with lowercase letters and constants start with uppercase letters. A term is a variable or a constant. An atom is r(a 1 , a 2 ) with a 1 , a 2 ∈ ∆ ∪ V and r ∈ R. A literal is an atom or its negation. An expression is ground if it contains no variables. A substitution is a mapping {a 1 /t 1 , . . . , a n /t n } where the a i are distinct variables and the t i are terms. If e is an expression and θ = {a 1 /t 1 , . . . , a n /t n } a substitution, then eθ is the expression e where one has replaced simultaneously the variables a i with the corresponding terms t i .

A possible world ω is represented as a set of ground atoms that are true in ω. The satisfaction relation |= is defined in the usual way: ω |= α means that the first-order logic formula α is true in ω. When x is a list of first-order logic variables then |x| is used to denote the length of this list.

Markov Logic Networks

A Markov logic network [START_REF] Richardson | Markov logic networks[END_REF] (MLN) is given as a set of weighted first-order logic formulas (α, w), where w ∈ R and α is a function-free and quantifierfree first-order formula. The semantics are defined w.r.t. the groundings of the first-order formulas, relative to a given finite set of constants ∆, called the domain. An MLN Φ induces the probability distribution over possible worlds ω ∈ Ω:

p Φ (ω) = 1 Z exp   (α,w)∈Φ w • N (α, ω)   ,
where N (α, ω) is the number of groundings of α from ∆ satisfied in ω, and Z, called the partition function, is a normalization constant to ensure that p Φ is a probability distribution.

In the context of the present paper, we replace N (α, ω) in the definition of MLNs by the fraction of groundings of α satisfied in ω, i.e.,

Q(α, ω) = 1 |∆| |vars(α)| ϑ∈Θ(α,∆) 1(ω |= αϑ),
where vars(α) is the set of variables occurring in α, Θ(α, ∆) is the set of all grounding substitutions of α's variables using constants from ∆ and 1(ω |= αϑ) is the indicator function, which is equal to 1 when αϑ is true in the possible world ω, 0 otherwise. Thus, Q(α, ω) is the fraction of the groundings of α satisfied in ω. With this notation we will write the probability of a possible world ω ∈ Ω as:

p Φ (ω) = 1 Z exp   (α,w)∈Φ w • Q(α, ω)   .
The reason this representation is more convenient for us is that Q(α, ω) is closer to the homomorphism densities used in graphon theory, as we discuss in Section 2.5.

Another way to look at Markov logic networks is to view them in the maxentropy framework as a maximum entropy distribution satisfying the given marginal constraints E[Q(α i , .)] = θ i (along the lines of [START_REF] Wainwright | Graphical models, exponential families and variational inference[END_REF]). Assuming we are given constraints on the expected values of the statistics E[Q(α i , .)] for a set of formulas Φ = {α 1 . . . α |Φ| }, we can define the following max-entropy problem of finding a maximum entropy distribution satisfying the constraints on the expected values.

Relational Marginal Problem (Formulation):

min {Pω : ω∈Ω} ω∈Ω P ω log P ω s.t. (1)
∀i = 1, . . . , m :

ω∈Ω P ω • Q(α i , ω) = θ i (2)
∀ω ∈ Ω : P ω ≥ 0,

ω∈Ω P ω = 1 (3)
Here, the P ω 's are the problem's decision variables, each of which represents the probability of one possible world ω ∈ Ω. Line (1) is the maximum Gibbs entropy criterion, which is shown here as the minimization of the negative entropy; Line [START_REF] Aubin | Optima and equilibria: an introduction to nonlinear analysis[END_REF] shows the constraints given by the statistics; and Line (3) provides the normalization constraints for the probability distribution.

Assuming there is a feasible solution satisfying ∀ω : P ω > 0, the optimal solution of the above maximum entropy problem is an MLN

P ω = 1 Z exp (αi,wi)∈Φ w i • Q(α i , ω)
where the parameters w = (w 1 , . . . , w m ) are obtained by maximizing the dual criterion, which also happens to be equivalent to the log-likelihood of the MLN (we refer to [START_REF] Kuželka | Relational marginal problems: Theory and estimation[END_REF] for details in the MLN context).

Graphs and Multi-Relational Graphs

An undirected graph G is a pair (V, E) where V is a finite set of vertices and E ⊆ {e ⊆ V||e| = 2} is a set of edges. Two vertices are said to be adjacent (in G) if they are connected by an edge (of the graph G). A multi-relational undirected graph is a triple (V, E, λ), where (V, E) is an undirected graph and λ : E → 2 Σ is a function assigning a set of labels from a finite alphabet Σ = {l 1 , . . . , l r } to every element of E. Alternatively, a multi-relational graph can be represented as a tuple (V, E 1 , E 2 , . . . , E r ) where E i consists of the edges e for which l i ∈ λ(e), i.e. which have label l i among their labels. We will use this latter representation in this paper because it will turn out to be convenient for constructing limits of multi-relational graphs. Note that simple graphs are a special case of multi-relational graphs. Given a multi-relational graph G = (V, E 1 , E 2 , . . . , E r ) we use the notation V(G) = V to refer to the set of vertices of G. The set of multi-relational graphs is denoted by G [r] .

A homomorphism from a multi-relational graph

F = V F , E F 1 , . . . , E F r to a multi-relational graph G = (V, E 1 , . . . , E r ) is a mapping φ : V F → V such that for all i ∈ {1, 2, . . . , r} it holds that if {u, v} ∈ E F i then {φ(u), φ(v)} ∈ E i .
Informally, homomorphisms are mappings that preserve edges and their labels. The set of all homomorphisms between F and G is denoted Hom(F, G).

Next we define homomorphism density of F in G, denoted t(F, G), as:

t(F, G) = | Hom(F, G)| |V(G)| |V(F)| . (4)

Graphons

A graphon is the limit of a sequence of growing undirected graphs w.r.t. a certain topology that we describe below. It can be represented as a measurable function W : [0, 1] 2 → [0, 1] satisfying W = W ⊤ . The space of graphons W is defined as

W := {W : [0, 1] 2 → [0, 1] | W is measurable and W = W ⊤ }. The space W is a subspace of W R = {W : [0, 1] 2 → R | W is measurable and W = W ⊤ }.
The space W R is endowed with the topology induced by the cut-norm,

∥W ∥ 2 := sup S,T ⊆[0,1] S×T W (x, y)dxdy .
Let Σ be the set of bijective measure preserving maps σ :

[0, 1] → [0, 1]. Let W ∈ W and let σ ∈ Σ. Then W σ : [0, 1] 2 → [0, 1] is defined by W σ (x, y) := W (σ(x), σ(y)).
The space of unlabeled graphons W, shortly called the graphon space, is the quotient of the space of graphons W w.r.t. the equivalence relation ∼ on W defined by W ∼ V iff there is σ ∈ Σ such that W = V σ . Hence we can also write W := W/ ∼.

The Unlabeled Graphon Space W is endowed with a topology induced by the cut-distance:

δ 2 (W, V ) = inf σ∈Σ ∥W -V σ ∥ 2
where V, W ∈ W.

Lovász [START_REF] Lovász | Limits of dense graph sequences[END_REF] shows that ( W, δ 2 ) is a compact topological space. Hence any sequence (x n ) ∞ n=1 in W has a convergent subsequence.

Graphons as Random-Graph Models

Graphons can also be seen as non-parametric random graph models. Given a graphon W and a positive integer n, we can use W to sample random graphs on n vertices as follows:

1. Let V = {v 1 , v 2 , . . . , v n }.
2. Sample uniformly n numbers x 1 , x 2 , . . . , x n from the interval [0, 1]. 3. For every v i , v j , where i < j, sample uniformly a number y i,j from [0, 1]. 4. Let E = {{v i , v j }|i < j and y i,j ≤ W (x i , x j )}. 5. Return G = (V, E).

Hence, intuitively, we can view a graphon as defining a "probabilistic" adjacency matrix over an uncountable set of vertices.

Stepfunctions

Stepfunctions are graphons that can be described by a finite number of parameters. First, the probability polytope P (m) , where m is a positive integer, is defined by

P (m) := π ∈ [0, 1] m i π i = 1 .
Next we define the notion of m-stepfunction, which will be a central tool in the next sections, Definition 1 Let λ be the Lebesgue measure on R, let

P = {P 1 , • • • , P m } be a partition of [0, 1], let π ∈ P (m) such that λ(P i ) = π i , let A ∈ [0, 1] m×m be a symmetric m × m matrix on [0, 1]. Then an m-stepfunction (A, π) : [0, 1] 2 → [0, 1] is a function locally constant on P i × P j for all i, j ∈ [m], more precisely (A, π) := m i,j=1 A i,j 1 Pi×Pj .
The set of stepfunctions is denoted by W (m) .

Multi-Relational Graphons

In this section we introduce multi-relational graphons, which, as we show later, are limits1 of convergent series of multi-relational graphs. The multi-relational graphons introduced here can also be seen as special cases of the decorated graphons given in Lovász [START_REF] Lovász | Limits of compact decorated graphs[END_REF]. However, as we will show, they are simpler to work with.

Multi-relational Graphon Space

We start by defining multi-relational graphons, which are the multi-relational counterparts of graphons. First, let us recall that the space of graphons W from Section 2.5 is the following

W := {W : [0, 1] 2 → [0, 1] | W is measurable, W = W ⊤ }
Since every multi-relational graph G can be represented as a vector of graphs [G 1 , • • • , G r ] with a common node set, intuitively we might expect that the limit of a sequence of multi-relational graphs can be represented as a vector of graphons. Later we will see that this definition makes sense and gives us all the desired theoretical properties. Hence, we identify the space of multi-relational graphons, denoted W [r] , with the cartesian product of r copies of the graphon space W:

Definition 2 (Graphon space)

W [r] := {W : [0, 1] 2 → [0, 1] r | W k : [0, 1] 2 → [0, 1] is measurable, W k = W ⊤ k for all k ∈ [r]}.
Moreover we extend the cut-norm to the multi-relational graphon space by

∥W ∥ [r] 2 = r i=1 ∥W i ∥ 2 . (5)
Note that when r = 1, W [r] is reduced to the graphon space W. Hereafter, we assume that every multi-relational graphon is a vector of r graphons. Moreover later we need some additional notations for graphon and multirelational graphon whose values are in [-1, 1].

W [-1,1] := {W : [0, 1] 2 → [-1, 1] | W is measurable and W = W ⊤ }. and W [r] [-1,1] := {W : [0, 1] 2 → [-1, 1] r | W is measurable and for all i ∈ [r]W i = W ⊤ i }.

Unlabeled Multi-Relational Graphon Space

Next we define the space of unlabeled multi-relational graphons, completely analogously to how the space of unlabeled graphons is defined.

Definition 3 Let W ∈ W [r] and let σ ∈ Σ then the action of σ on W is defined by,

[W 1 , • • • , W r ] σ = [W σ 1 , • • • , W σ r ].
We define the space of unlabeled multi-relational graphons W [r] as the quotient of W [r] by the equivalence relation ∼ on W [r] defined by W ∼ V iff there exists an action σ ∈ Σ such that W = V σ , Hence W [r] := W [r] / ∼.

Multi-Relational Graphons as Probabilistic Models

Like graphons, multi-relational graphons can also be seen as non-parametric multi-relational random graph models. Given a multi-relational graphon W = (W 1 , W 2 , . . . , W r ) and a positive integer n, we can use W to sample random multi-relational graphs on n vertices as follows (we highlight the differences from sampling from simple graphons using text in italics):

1. Let V = {v 1 , v 2 , . . . , v n }.
2. Sample n numbers x 1 , x 2 , . . . , x n uniformly from the interval [0, 1]. 3. For every v i , v j , where i < j, sample r numbers y

i,j . . . , y

i,j uniformly from [0, 1]. 4. For all k ∈ {1, 2, . . . , r}, let E k = {{v i , v j }|i < j and y

(k) i,j ≤ W k (x i , x j )}. 5. Return G = (V, E 1 , E 2 , . . . , E r ).

Counting Multi-Relational Graph homomorphisms

Let F and G be multi-relational graphs with the same number of relations r. Additionally, we assume that G has node and edges weights. To compute |Hom(F, G)|, we extend the formulas given in Section 5.2.1 in Lovász [START_REF] Lovász | Large networks and graph limits[END_REF] to count graph homomorphism on weighted graphs to the multi-relational case. For any k ∈ [r] and vertices i, j ∈ V (G), let α i ∈ R + and let β k,ij ∈ R + be non-negative weights.

To every map ϕ : V (F) → V (G), we assign the weights

α ϕ = u∈V (F ) α ϕ(u) (G)
and

|Hom ϕ (F, G)| = r k=1 (uv)∈E k (F) β k,ϕ(u)ϕ(v) .
Moreover, we define

|Hom(F, G)| = ϕ:V (F)→V (G) α ϕ |Hom ϕ (F, G)|. (6)
In the sequel of this paper, unless explicitly stated otherwise we will assume that α v = 1 for all v ∈ V (G). In particular, if we set the node weights α ϕ = 1, there follows from Equations ( 4) and ( 6) that

t(F, G) = m x1=1 1 m • • • m xn=1 1 m r k=1 uv∈E k (F) β k,xuxv (7)
where m = |V (G))| and n = |V (F))|. G can be seen as a vector of stepfunctions on the unit square whose value for the relation k at the square

[(i-1)/|V (G)|, i/|V (G)|)×[(j -1)/|V (G)|, j/|V (G)|) is β k,ij for i, j ∈ [|V (G)|].
In this way G is a measurable function, hence when V (G) → ∞ in a converging sequence we have that G → W converges to a measurable function W by Lebesgue's Dominated Convergence Theorem. Hence we arrive to the formula to compute the density of multi-relational graph homomorphisms,

t(F, W ) = [0,1] |V (F)| r k=1 (uv)∈E k (F ) W k (x u , x v ) u∈V (F) dx u . (8)
Note that the above formula computes the density of multi-relational graph homomorphism from F into a multi-relational graph W with uncountable many nodes from [0, 1].

In this paper, it is convenient to define F as a generalization of signed graphs from Lovász [START_REF] Lovász | Large networks and graph limits[END_REF] in the context of multi-relational graphs. Suppose that the edges of each relation E i of a multi-relational graph F are partitioned into two sets E + i and

E - i . Then the tuple F = (V, E + 1 , E - 1 , • • • , E + r , E - r
) will be called a multi-relational signed graph. The subgraph density of F in a multi-relational graphon is,

t(F, W ) = [0,1] |V (F)| r k=1 (uv)∈E + k (F ) W k (x u , x v ) (uv)∈E - k (F ) (1-W k (x u , x v )) u∈V (F) dx u . (9)
3.4 Cut Distance on W [r] We already have a topology based on the cut norm for the space of multirelational graphons W [r] that we defined in (5) above. Now, we use it to also endow the space of unlabeled multi-relational graphons W [r] with a topology by defining the cut-distance on it.

Let W, V ∈ W [r] δ [r] 2 (W, V ) = inf σ∈Σ ∥W -V σ ∥ [r] 2
The following lemma shows bounds for δ

[r]

2 .

Lemma 1 Let W, V ∈ W [r] be unlabeled multi-relational graphons, then

r k=1 δ 2 (W k , V k ) ≤ δ [r] 2 (W, V ) ≤ ∥W -V ∥ [r] 2 Proof Note that r k=1 δ 2 (W k , V k ) = r k=1 inf σ k ∈Σ ∥W k -V σ k k ∥ 2 = inf σ1,••• ,σr∈Σ r k=1 ∥W k -V σ k k ∥ 2 ≤ inf σ∈Σ r k=1 ∥W k -V σ k ∥ 2 = δ [r] 2 (W, V ).
Hence we obtain

r k=1 δ 2 (W k , V k ) ≤ δ [r] 2 (W, V ) ≤ r k=1 ∥W k -V k ∥ 2 . ⊓ ⊔ Remark 1 Note that the norm ∥ • ∥ [r]
2 is the sum of ∥ • ∥ 2 . Hence every result that shows an upper bound for the norm ∥ • ∥ on W for graphons can be extended easily to an upper bound for multi-relational graphons by the sum of individual upper bounds.

4 Compactness on W [r] In this section we prove that the space (

W [r] , δ [r]
2 ) is compact. To do that we extend the weak regularity lemma for graphons given Corollary 9.13 in Lovász [START_REF] Lovász | Large networks and graph limits[END_REF].

Weak Regularity Lemma for multi-relational Graphons

The weak regularity lemma, which is known to hold for graphons, asserts that every graphon can be arbitrarily approximated by stepfunctions. Here we extend the weak regularity lemma to multi-relational graphons.

To state the weak regularity lemma, we need the notion of a stepping operator. Intuitively, a stepping operator for multi-relational graphons takes an arbitrary multi-relational graphon and produces a multi-relational graphon which approximates the original graphon and which is a step function.

Definition 4 (Stepping Operator for graphons) Let

P := {P 1 , • • • , P m } be a partition of [0, 1] and W ∈ W. Then T P (W ) is the m-stepfunction defined by T P (W )(x, y) = 1 λ(P i )λ(P j ) Pi×Pj W (u, v)dudv
where (x, y) ∈ P i × P j and λ(A) is the Lebesgue measure of A.

It is clear that the stepping operator T P is a map from W to W (m) where m = |P |. Now we generalize the stepping operator T P (W ) for multi-relational graphons.

Definition 5 (Stepping Operator for Multi-relational graphons) Let P = [P 1 , • • • , P r ] be a vector of partitions of [0, 1] and W ∈ W [r] be a multirelational graphon then

T P (W ) = [T P1 (W 1 ), • • • , T Pr (W r )].
The next theorem from [START_REF] Lovász | Large networks and graph limits[END_REF] can be proven using the weak regularity lemma (Lemma 9.9 in Lovász [START_REF] Lovász | Large networks and graph limits[END_REF]).

Theorem 1 (Corollary 9.13 in Lovász [START_REF] Lovász | Large networks and graph limits[END_REF]) For every function W ∈ W and k ≥ 1 there is a partition P of [0, 1] into at most k sets with positive measure for which

∥W -T P (W )∥ 2 ≤ 2 log 2 k Definition 6 Let P = {P 1 , • • • , P k } be a partition of [0, 1]. We say that P is an equipartition P with k classes if λ(P i ) = 1/k for all i ∈ [k].
Lemma 2 (Lemma 9.15 in Lovász [START_REF] Lovász | Large networks and graph limits[END_REF] )

Let W ∈ W [-1,1] and 1 ≤ m < k. (a) For every m-partition Q of [0, 1] and k > m there is a partition with k classes P refining Q such that ∥W -T P (W )∥ 2 ≤ 2 log 2 (k/m) .
(b) For every m-partition Q of [0, 1] and k > m there is an equipartition P with k classes such that

∥W -T P (W )∥ 2 ≤ 2∥W -T Q (W )∥ 2 + 2m k Definition 7 (ϵ-partition) Let P = [P 1 , P 1 , . . . , P 1 ]
r times be a vector of partitions of [0, 1] with the same classes. Let ϵ > 0 and let W ∈ W [r] . We say that P is an ϵ-partition for W if

∥W -T P (W )∥ [r] 2 ≤ ϵ.
The next theorem proves the existence of an ϵ-partition for any W ∈ W [r] .

Theorem 2 For every graphon W ∈ W [r] and k ≥ 1 such that k 1/r ∈ N.

Then, there exists a partition P such that

∥W -T P (W )∥ [r] 2 ≤ 2r 3/2 log 2 k . Proof Let k 1 ≥ 1 be an integer. By Theorem 1, for every i ∈ [r] there is a k 1 -partition Q i of [0, 1] such that ∥W i -T Qi (W i )∥ 2 ≤ 2 log 2 k 1 . For s ∈ [k 1 ] r let Q ∩ s ⊆ [0, 1] be the set of all x ∈ [0, 1] such that for all i ∈ [r] the point x is in the s i -th partition class of Q i . The set Q ∩ = {Q ∩ s | s ∈ [k 1 ] r } is a partitioning of [0, 1]. Let k = k r 1 = |Q ∩ | be the number of classes of |Q ∩ |. Q ∩ is a refinement of Q i for each i ∈ [r], so there holds ∀i ∈ [r] : ∥W i -T Q ∩ (W i )∥ 2 ≤ 2 log 2 k 1 = 2r 1/2 log 2 k
and hence

∥W -T Q ∩ (W )∥ 2 ≤ 2r 3/2 log 2 k ⊓ ⊔ 4.2 Compactness on W [r]
We have all ingredients to prove compactness of W [r] .

Theorem 3 The space ( W [r] , δ [r]
2 ) is compact.

This proof is almost identical to the proof of Theorem 5.1 in Lovász [START_REF] Lovász | Szemerédi's lemma for the analyst[END_REF] except that we use a vector of stepfunctions instead of a single stepfunction and we make use of ϵ-partitions.

Proof Let W 1 , W 2 , • • • be a sequence of vectors of graphons in W [r] . We will construct a subsequence that has a limit in W [r] .

For each k and n, using Theorem 2, we construct an ϵ-partition P n,k such that these partitions and the corresponding stepfunctions W n,k = T P n,k (W ) ∈ W [r] satisfy the following.

-∥W n -W n,k ∥ [r] 2 ≤ 1/k. -|P n,k | = m k (where m k depends only on k).
-The partition P n,k+1 refines P n,k for every k.

The rest of the proof follows verbatim from the analogous proof of Theorem 5.1 from [START_REF] Lovász | Szemerédi's lemma for the analyst[END_REF] except that we use a vector of stepfunctions instead of one stepfunction.

⊓ ⊔ Any multi-relational graph G [r] has a natural representation as multirelational graphon in terms of adjacency matrices: r] in W [r] . From Eqs. ( 7) and [START_REF] Dudley | Real analysis and probability[END_REF], it is not difficult to verify t(F, G) = t(F, f G ).

Definition 8 f G [r] k (x, y) = 1 if (v ⌈nx⌉ , v ⌈ny⌉ ) ∈ E k (G [r] ) 0 otherwise where n = |V (G [r] )|. Hence f G [r] k (x, y) is a representation of G [
Compactness of W [r] ensures that any sequence of growing multi-relational graphs (G

[r] n ) ∞ n=1 represented by (f G [r] n ) ∞ n=1
has at least a subsequence with a limit. In the next section, we will prove that such limits of sequences of multi-relational graphons (f r] are solutions of a maximum entropy problem.

G [r] n ) ∞ n=1 constrained to a closed set H ⊂ W [

Density of multi-relational graphs

The weak regularity lemma shows that the set of stepfunctions ∪ m>0 W (m) is dense in W [r] and the set of multi-relational graphs is a subset of W (m) via the representation G → f G . To show the space of unlabeled multi-relational graphons is the appropriate limit space for multi-relational graphs, we need to prove that the set of multi-relational graphs G [r] is dense in W [r] via the identification G → f G . To do that, we extend Theorem 4.7 [START_REF] Borgs | Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing[END_REF] due to Borgs, Chayes, Lovász, Sós and Vesztergombi to the multi-relational setting. This theorem states that a sample is close to the original graphon with high probability.

We start by extending the notion of W -sampling for multi-relational graphons.

β k,ij (H(S, W )) = W k (x i , x j ) If i ̸ = j 0 If i = j .
for all 1 ≤ k ≤ r. If S is a random k-subset of [0, 1] drawn uniformly then we write H(n, W ) instead of H(S, W ).

Definition 10 (Sampling of random graphs from weighted multirelational graphs) Let H be a weighted multi-relational graph. Then G(H) is a random multi-relational graph obtained by connecting different nodes i and j by an edge of class k with probability β k,ij (H) ∈ [0, 1] independently of the sampling of other edges. Hence, we can construct a random graph G(S, W ) = G(H(S, W )).

Definition 11 (Sampling of random graphs from multi-relational graphons) Let W ∈ W [r] and let n be a positive integer. Let S be a random k-subset of [0, 1] sampled uniformly. Then G(n, W ) is a random graph obtained by G(S, W ).

Note that the sampling from G(n, W ) extends the sampling procedure of graphs from a graphon given in Section 2.5.1.

Definition 12 (Multi-relational graph parameter) Recall that G [r] is the set of multi-relational graphs. A multi-relational graph parameter is a function f : G [r] → R defined on multi-relational, not necessarily loop-free graphs which is invariant under graph isomorphism. For example any multirelational subgraph density t(F, •) is a multi-relational graph parameter.

Hence it is clear that f (G(n, W )) is a random variable. The next lemma shows a concentration measure inequality for the multi-relational graph parameters.

Lemma 3 (Lemma 4.1 [START_REF] Borgs | Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing[END_REF]) Let k be a positive integer, and let

C > 0. Let Z = (Z 1 , • • • , Z s ),
where Z 1 , • • • , Z s are independent random variables, and Z i takes values in some measure space

(Ω i , A i ). Let f : Ω 1 × • • • × Ω s → R be a measurable function. Suppose that |f (x)-f (y)| ≤ C whenever x = (x 1 , • • • , x s ) and y = (y 1 , • • • , y s ) differ only in one coordinate. Then P(f (Z) > E[f (Z)] + λC) < exp(- λ 2 2s ) Remark 2 Let f : G [r]
→ R be a multi-relational graph parameter and suppose

f is bounded. Let f q : [0, 1] q → R with f q (S) = f (G(S, W )).
Then f q satisfies the condition of the above lemma since there is a

C such that |f q (x) -f q (y)| ≤ C whenever x = (x 1 , • • • , x q ) and y = (y 1 , • • • , y q ) differ
only in one coordinate.

Sampling Lemmas

The goal of this section is the extension of Theorem 4.7 [START_REF] Borgs | Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing[END_REF] to the multirelational setting. To do that, we extend a set of lemmas from Chapter 10 in [START_REF] Lovász | Large networks and graph limits[END_REF] and finally extend Theorem 4.7. We name this extension the second sampling lemma for multi-relational graphons.

Lemma 4 (The First Sampling Lemma for graphons. Lemma 10.6 in [START_REF] Lovász | Large networks and graph limits[END_REF]) Let U ∈ W [-1,1] and let X be a random ordered k-subset of [0, 1]. Then with probability at least 1 -4 exp(-√ k/10),

- 3 k ≤ ∥U [X]∥ 2 -∥U ∥ 2 ≤ 8 k 1/4 .
From the first sampling lemma, we prove the following.

Lemma 5 Let k > 1 be a positive integer. Let U ∈ W [r] [-1,1] and let X be a random ordered k-subset of [0, 1]. Then, E ∥U [X]∥ [r] 2 -∥U ∥ [r] 2 ≤ 14r k 1/4 .
Proof From Remark 1 and the linearity of the expectation, it is sufficient to prove that

E [∥V [X]∥ 2 -∥V ∥ 2 ] ≤ 14 k 1/4 . for any V ∈ W [-1,1] . Let z = ∥V [X]∥ 2 -∥V ∥ 2 , thus E[z] = E z - 3 k ≤ z ≤ 8 k 1/4 P - 3 k ≤ z ≤ 8 k 1/4 +E z z < - 3 k ∨ z ≥ 8 k 1/4 P z < - 3 k ∨ z ≥ 8 k 1/4
In the second term we can bound

E z|z < -3/k ∨ z ≥ 8/k 1/4 ≤ 1 because z ∈ [-1, 1],
and by applying Lemma 4 on V and k > 1 we can bound

P z < -3/k ∨ z ≥ 8/k 1/4 ≤ 4 exp(- √ k/10
). In the second term, from Lemma 4 we can bound E z| -3/k ≤ z ≤ 8/k 1/4 ≤ 8/k 1/4 and the probability is at most 1. There follows

E[z] ≤ 8 k 1/4 + 4 exp(- √ k 10 ) ≤ 14 k 1/4 .
where the last inequality can be verified numerically.

⊓ ⊔

We also extend a consequence of Lemma 10.11 [START_REF] Lovász | Large networks and graph limits[END_REF].

Lemma 6 (Lemma 10.11 [START_REF] Lovász | Large networks and graph limits[END_REF]) For every edge-weighted multi-relational graph H with k nodes and edge weights in [0, 1], and for every ε ≥ 10/ √ k, we have

P rob(∥G(H) -H∥ 2 > ε) ≤ exp(-ε 2 k 2 /100).
First we prove a consequence of the above lemma in the setting of simple graphs.

Lemma 7 For every edge-weighted simple graph H with k nodes and edge weights in [0, 1], we have

E [∥G(H) -H∥ 2 ] ≤ 11 √ k
Proof By applying Lemma 6 with ε = 10/ √ k, we have

P ∥G(H) -H∥ 2 > 10 √ k ≤ exp(-k). ( 10
)
We abbreviate ∥G(H) -H∥ 2 by z. Hence

E[z] = E z z > 10 √ k P z > 10 √ k + E z z ≤ 10 √ k P z ≤ 10 √ k
From [START_REF] Jaeger | Inference, learning, and population size: Projectivity for SRL models[END_REF] and knowing the distance z = ∥G(H) -H∥ 2 in bounded by 1, we have

E[z] ≤ E z z > 10 √ k exp(-k) + E z z ≤ 10 √ k ≤ exp(-k) + 10 √ k ≤ 11 √ k .

⊓ ⊔

We can extend the above lemma to the multi-relational setting.

Lemma 8 For every edge-weighted multi-relational graph H with k nodes and edge weights in [0, 1], we have

E(∥G(H) -H∥ [r] 2 ) ≤ 11r √ k
Proof From Lemma 7 and Remark 1, the proof is immediate. ⊓ ⊔ Lemma 9 Let V ∈ W [r] be a stepfunction of q steps and let k be a positive integer. Then

E[δ 2 (V, H(k, V ))] ≤ r q k
Proof We follow the same ideas as the proof of Theorem 4.7 in [START_REF] Borgs | Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing[END_REF].

Let V have steps J 1 , • • • , J q ⊆ [0, 1], and λ(J i ) = α i . Let X 1 , • •
• , X k be independent random variables that are uniformly distributed on [0, 1], and let Z i be the number of points X j that fall into the set J i . Hence we have

E[Z i ] = α i k, V ar(Z i ) = (α i -α 2 i )k ≤ α i k. Construct a partition of [0, 1] into measurable sets J ′ 1 , • • • , J ′ q such that λ(J ′ i ) = Z i /k and λ(J ′ i ∩ J i ) = min(α i , Z i /k).
We define a symmetric function V ′ ∈ W such that the value of V ′ on J ′ i × J ′ j is the same as the value of V on J i ×J j . Then V ′ is a step function representation of H(k, V ), and it agrees with V on the set

Q = ∪ q i,j=1 (J i ∩ J ′ i ) × (J j ∩ J ′ j ). Let ∥W ∥ [r] 1 = i ∥W i ∥ 1 be the extension of the L 1 norm to W [r] . Thus we have δ 2 (V, H(k, V )) ≤ ∥V -V ′ ∥ [r] 2 ≤ ∥V -V ′ ∥ [r] 1 ≤ r(1 -λ(Q)) = r   1 - i min α i , Z i k 2   ≤ 2r 1 - i min α i , Z i k = r i α i - Z i k ≤ r q i α i - Z i k 2 1/2 .
Thus we have

δ 2 (V, H(k, V )) 2 ≤ qr 2 i α i - Z i k 2 .
It follows,

E[δ 2 (V, H(k, V )) 2 ] ≤ qr 2 i E α i - Z i k 2 = qr 2 k 2 i V ar(Z i ) < qr 2 k 2 i kα i = qr 2 k .
Because δ 2 (V, H(k, V )) ≥ 0 there follows by Cauchy-Schwartz

E[δ 2 (V, H(k, V ))] ≤ r q k .

⊓ ⊔

Now, we have all the ingredients to extend the second sampling lemma.

Lemma 10 Extension of Theorem 4.7 in [START_REF] Borgs | Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing[END_REF] (Second Sampling Lemma for Multi-Relational Graphons). Let k ≥ 1, and let W ∈ W [r] be a multi-relational graphon. Then with probability at least 1 -exp(-kr/(2 log 2 k)),

δ [r] 2 (G(k, W ), W ) ≤ 36r 3/2 log 2 k (11)
One direct consequence of Lemma 10 is that the set of multi-relational graphs is dense in ( W [r] , δ

[r]

2 ).

Theorem 4 The set of multi-relational graphs is dense in ( W [r] , δ

[r]

2 ).

Proof It is sufficient to prove that for any W ∈ W [r] and ϵ > 0, there is a multi-relational graph G such that δ 2 (G(k, W ), W ) ≤ ϵ with probability at least 1 -exp(-k/(2 log k)) > 0 so at least one of the multirelational graphs which can be obtained by sampling from G(k, W ) has the required property.

⊓ ⊔

From the above theorem, any multi-relational graphon can be seen as the limit of a sequence of multi-relational graphs.

Large Deviation Principle and the Principle of Maximum-Entropy

The large deviation principle (LDP) establishes lower and upper bounds for the limiting behaviour of a sequence of probability distributions. More precisely [START_REF] Dembo | Large deviations techniques and applications[END_REF], let X be a topological space. A sequence of probability distributions (P n ) ∞ n=1 satisfies LDP when there is a function I : X → R, called the rate function such that for every Γ ⊂ X and sequence (ϵ n ) n∈N with limit ϵ n → 0, the probability measure of the set Γ , P n (Γ ), satisfies the following inequality. Recall Γ and Γ • are closure and interior of Γ ⊂ X .

-inf

x∈Γ • I(x) ≤ lim inf n→∞ ϵ n log P n (Γ ) ≤ lim sup n→∞ ϵ n log P n (Γ ) ≤ -inf x∈Γ I(x).
In this section, we extend the large deviation principle for Erdős-Rényi random graphs due to Chatterjee and Varadhan [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF] to multi-relational Erdős-Rényi random graphs.

The negative of the rate function can be interpreted as an entropy function. We will see that -I(W ) is a density of entropy of multi-relational random graphs sampled from W . Note that if inf x∈Γ • I(x) = inf x∈Γ I(x) then the limiting probability distribution is the probability distribution with maximum entropy. We prove this property for any closed region constrained by densities of multi-relational subgraphs.

Based on the compactness of graphon space, Chatterjee and Varadhan [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF] developed the large deviation principle for limiting behavior of the probability measure P n,p induced by Erdős-Rényi random graphs G(n, p) on the unlabeled graphon space W.

Here, we first need to extend the Erdős-Rényi random-graph model G(n, p) to multi-relational graphs and define the rate function.

Definition 13 (Erdős-Rényi multi-relational random graphs) Let p ∈ [0, 1]. Then Erdős-Rényi multi-relational random graphs G [r] (n, p) are r-tuple of independent draws of G(n, p), where we identify the vertices across all r graphs. Definition 14 (Rate function) Let p ∈ (0, 1). Then the rate function

I [r] p : W [r] → R is defined by, I [r] p (W ) = 1 2 r k=1 [0,1] 2 I 0,p (W k (x, y))dxdy where I 0,p (u) = 1 2 u log u p + 1 2 (1 -u) log 1-u 1-p .
Remark 3 Note that the negative of I 0,p is the entropy of the Bernoulli distribution. Hence -I p (W ) can be seen as a density of entropy produced by large random graphs sampled from W . From a statistical mechanics point of view [START_REF] Radin | Phase transitions in a complex network[END_REF], -I p (W ) corresponds to the Boltzmann entropy of the microcanonical ensemble of random edges W .

Let P n,p be the probability measure on W induced by f G(n,p) and more generally let P

[r] n,p be the probability measure on W [r] induced by f G [r] (n,p) . In the same way, let P

[r] n,p be the probability measure on W [r] induced by f G [r] (n,p) , where f G is the equivalence class of f G induced by the permutations of rows/columns on f G . Now we state our main technical result which is a generalization of the corresponding large deviation result from [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF],

Theorem 5 (Extension of Theorem 2.3 [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF]) For each fixed p ∈ (0, 1), the sequence P

[r]

n,p satisfies a large deviation principle in the cut-distance topology. That is, for every closed set F ⊂ W lim sup n→∞ 1 n 2 log P [r] n,p (F ) ≤ -inf

W ∈F I [r] p (W ) (12)
and for any open set U ⊂ W,

lim inf n→∞ 1 n 2 log P [r] n,p (U ) ≥ -inf W ∈U I [r] p (W ). (13)

Constraint systems for quantum graphs

In the context of the present paper, it is convenient to define regions of Multi-Relations Graphons by linear combinations of multi-relational graph densities.

Definition 15 (Multi-relational quantum graphs) We say that F is a multi-relational quantum graph if it is the linear combination of a finite number of multi-relational graphs F i with real coefficients, more precisely

F = i α i F i and α i ∈ R
Hence the definition of t(F, W ) extends to multi-relational quantum graphs linearly, i.e. t(F, W ) = i α i t(F i , W ).

Quantum graphs generalize the notion of signed multi-relational graph and offer a convenient way to write succinctly linear combinations of subgraph densities specially when we represent horn clauses using linear combinations of conjunctions.

Let F = [F 1 , • • • , F k ]
be a finite vector of multi-relational quantum graphs and let u ∈ R k + . We let correspond to (F, u) a system of constraints ∀i ∈ [k] : t(F i , W ) = u i on the multi-relational quantum graphs F 1 , . . . , F k , where we call u the density vector. Then we define the feasible region

S(F, u) = {W ∈ W [r] | t(F i , W ) = u i , for 1 ≤ i ≤ |F|} (14)
We also define an approximate feasible region. In particular, for ϵ > 0,

S(F, u, ϵ) = {W ∈ W [r] | |t(F i , W ) -u i | ≤ ϵ, for 1 ≤ i ≤ |F|} (15)

The most typical multi-relational graph of S(F, u)

We need an additional ingredient to prove the main result of this section which is is the extension of the counting lemma of graphons (Lemma 10.23 in [START_REF] Lovász | Large networks and graph limits[END_REF]) to multi-relational graphons.

Lemma 11 (Counting lemma for multi-relational graphons) Let F be a multi-relational graph and let W and V be multi-relational graphons, then

|t(F, W ) -t(F, V )| ≤ max k |E(F k )| δ [r] 2 (W, V )
Thus if F is a quantum multi-relational graph then the map W → t(F, W ) is continuous.

We now define the notion of the most typical multi-relational graphs in S(F, u). Let (G [r] (n, 1/2)) ∞ n=1 be a sequence of multi-relational Erdős-Rényi random graphs. From Theorem 4 and the compactness of W [r] , there is a subsequence (G [r] (n i , 1/2)) ∞ i=1 and a sequence of positive numbers (ϵ i ) ∞ i=1 with lim i→∞ ϵ i = 0 such that G [r] (n i , 1/2) ∈ S(F, u, ϵ i ). By Theorem 4, G [r] is dense in W [r] , hence the condition G [r] (n i , 1/2) ∈ S(F, u, ϵ i ) holds since S(F, u, ϵ i ) is open for any ϵ i > 0. Therefore the limit of random multi-relational graphs G [r] (n i , 1/2) satisfying the constraints t(F i , W ) = u ∀i ∈ [k] is defined. We call these limits as the most typical random multi relational graphs

We prove that any typical multi-relational Erdős-Rényi random graph W * is a solution of min W ∈ S(F ,u) I

[r] p (W ), where p = 1/2. First we prove the following.

Theorem 6 Take any p ∈ (0, 1). Then

inf W ∈ S(F ,u) • I [r] p (x) = inf W ∈ S(F ,u) I [r] p (x). ( 16
)
and

lim n→∞ 1 n 2 P [r] n,p ( S(F, u)) = -min W ∈ S(F ,u) I [r] p (W ).
Proof Let δ > 0. Then we define •) is continuous under the cut-distance topology, hence U δ and V δ are open and closed sets.

U δ = ∩ k i=1 {W ∈ W [r] | |t(F i , W ) -u i | < δ} and V δ = ∩ k i=1 {W ∈ W [r] | |t(F i , W ) -u i | ≤ δ} From Lemma 11, t(F i ,
Let

P [r]
n,p (U δ ) and P

[r]

n,p (V δ ) be the probability measure of U δ and V δ . From Theorem 5, it follows that lim sup

n→∞ 1 n 2 log P [r] n,p (V δ ) ≤ -inf W ∈V δ I [r] p (W ) and lim inf n→∞ 1 n 2 log P [r] n,p (U δ ) ≥ -inf W ∈U δ I [r] p (W )
and therefore we may write

-inf W ∈U δ I [r] p (W ) ≤ lim inf n→∞ 1 n 2 log P [r] n,p (U δ ) ≤ lim sup n→∞ 1 n 2 log P [r] n,p (U δ ) ≤ lim sup n→∞ 1 n 2 log P [r] n,p (V δ ) ≤ -inf W ∈V δ I [r] p (W ) ≤ -inf W ∈U δ+δ 2 I [r] p (W ) By taking the limit δ → 0 + , inf W ∈U δ I [r] p (W ) and inf W ∈U δ+δ 2 I [r]
p (W ) are the same and V δ → S(F, u). Thus we have, inf

W ∈ S(F ,u) • I [r] p (W ) = inf W ∈ S(F ,u) I [r] p (W ).
Since S(F, u) is compact and Chatterjee and Varadhan proved the function

I [r]
p is lower semi-continuous, it follows that we may replace inf by min (c.f. appendix, Theorem 9) and deduce

lim n→∞ 1 n 2 P [[r] n,p ( S(F, u)) = -min W ∈ S(F ,u) I [r] p (W ).

⊓ ⊔

Theorem 6 shows that the limiting distribution of the most typical multirelational Erdős-Rényi random graphs holds the condition

lim n→∞ 1 n 2 P [r]
n,1/2 ( S(F, u)) = -min W ∈ S(F ,u)

I [r] 1/2 (W ).
The next theorem shows that the limiting distribution of the most typical random graphs is a solution of min W ∈ S(F ,u) I

[r]

1/2 (W ). To do that, we extend a concentration inequality for growing sequences (G [r] (n, p)) ∞ n=1 given by Chatterjee and Varadhan, Theorem 3.1 in [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF].

Theorem 7 (Concentration inequality for constrained and multi-relational Erdős-Rényi random graphs) Take any p ∈ (0, 1) (in our case p = 1/2). Let H ⊂ W [r] be a compact set such that the condition of Eq. 16 holds. Let H * be the subset of H where I

[r]

p (•) is minimized. Then H * is non-empty and compact, and for each n, and each ϵ > 0,

P rob(δ 2 (G [r] (n, p), H * ) ≥ ϵ | G [r] (n, p) ∈ H) ≤ exp(-C(ϵ, H)n 2 )
where C(ϵ, H) is a positive constant depending only on ϵ and H. In particular, if H * contains only one element h * , then the conditional distribution of G [r] (n, p) given H converges to the point mass at h * as n → ∞.

The original statement of the above theorem includes the condition inf

W ∈ S(F ,u) • I [r] p (x) = inf W ∈ S(F ,u) I [r] p (x). ( 17
)
which is proven in Theorem 6. The proof of the theorem is omitted since it is identical to the proof of Theorem 3.1 found in Chatterjee and Varadhan [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF].

Note that if H is compact the sequence (G [r] (n, 1/2)) ∞ n=1 |(H) samples uniformly random graphs constrained by H. Hence from the above theorem, we conclude the solutions of min x∈H I

[r] 1/2 (x) are the most typical infinite multirelational random graphs constrained to H.

Finally from Theorems 5 and 6, it is straightforward to prove that Theorem 8 Let F be a vector of finite vector of multi-relational quantum graphs

F = [F 1 , • • • , F k ]
and let u ∈ R k be a vector of multi-relational subgraph densities. Then the limit W * (F, u) of the sequence (G [r] (n, 1/2)) ∞ n=1 of growing random multi-relational graphs which are uniformly sampled such that lim n→∞ G [r] (n, 1/2) ∈ S(F, u) satisfies

W * (F, u) = min W ∈ S(F ,u) I [r] p (W ) ( 18
)
7 Technical Results and Proofs

Proof of the Second Sampling Lemma

Proof of Lemma 10.

Let us abbreviate ∥W -V ∥ 2 by d 2 (W, V ). Recall Theorem 2, for any U there a stepfunction U P with partition P of q classes such that,

d 2 (U, U P ) ≤ 2r 3/2 log 2 q
We can also write

E[|d 2 (H(k, U ), H(k, U P ))|] ≤ E[|d 2 (H(k, U ), H(k, U P )) -d 2 (U, U P )|] + d 2 (U, U P )
By Lemma 5 and Theorem 2, we have that

E[d 2 (H(k, U ), H(k, U P ))] ≤ 14r k 1/4 + 2r 3/2 log 2 q Thus E[δ 2 (H(k, U ), H(k, U P ))] ≤ 14r k 1/4 + 2r 3/2 log 2 q
There follows

E[δ [r] 2 (U, H(k, U ))] ≤ δ [r] 2 (U, U P ) + E[δ [r] 2 (U P , H(k, U P ))] + E[δ [r] 2 (H(k, U P ), H(k, U ))] ≤ 2r 3/2 log 2 q + E[δ [r] 2 (U P , H(k, U P )] + 14r k 1/4 + 2r 3/2 log 2 q = 14r k 1/4 + 4r 3/2 log 2 q + E[δ [r] 2 (U P , H(k, U P )]
Lemma 9 shows an upper bound for E[δ 2 (U P , H(k, U P )] , thus

E[δ [r] 2 (U, H(k, U ))] ≤ 14r k 1/4 + 4r 3/2 log 2 q + r q k .
By setting q = ⌈k 1/4 ⌉ we get

E[δ [r] 2 (U, H(k, U ))] ≤ 14r k 1/4 + 8r 3/2 log 2 k + r k -3/4 + k -1 , hence (since k ≥ 1). E[δ [r] 2 (U, H(k, U ))] ≤ 24r 3/2 log 2 k . ( 19
)
In order to get an upper bound for

E[δ [r] 2 (U, G(k, U ))] we write E[δ [r] 2 (U, G(k, U ))] ≤ E[δ [r] 2 (U, H(k, U ))] + E[δ [r] 2 (H(k, U ), G(k, U ))]
By Lemma 8 and Eq [START_REF] Lovász | Limits of compact decorated graphs[END_REF], we have

E[δ [r] 2 (U, G(k, U ))] ≤ 24r 3/2 log 2 k + 11r √ k ≤ 35r 3/2 log 2 k (20) Let f (G) = v(G)δ [r]
2 (G, W ) be the multi-relational graph parameter. Note that |f (G) -f (G ′ )| ≤ r when G and G ′ differ in only one edge. Hence we can apply Lemma 3 on f , by setting

C = r, f (Z) = kδ [r] 2 (G(k, W ), W ), E[f (Z)] = kδ [r] 2 (G(k, W ), W ) and s = k. P(kδ [r] 2 (G(k, W ), W ) > kE[δ [r] 2 (G(k, W ), W )] + λr) < exp(- λ 2 2k ) hence P(δ [r] 2 (G(k, W ), W ) > E[δ [r] 2 (G(k, W ), W )] + λr k ) < exp(- λ 2 2k ) If λ = kr 1/2 √ log 2 k
then we have

P(δ [r] 2 (G(k, W ), W ) ≤ E[δ [r] 2 (G(k, W ), W )] + r 3/2 log 2 k ) ≥ 1 -exp(- kr 2 log 2 k
).

From [START_REF] Nešetřil | First-order limits, an analytical perspective[END_REF] we know that

E[δ [r] 2 (W, G(k, W ))] ≤ 35r 3/2 √ log 2 k
. Thus there also must hold

P(δ [r] 2 (G(k, W ), W ) ≤ 35r 3/2 log 2 k + r 3/2 log 2 k ) ≥ 1 -exp(- kr 2 log 2 k
), and hence

P(δ [r] 2 (G(k, W ), W ) ≤ 36r 3/2 log 2 k ) ≥ 1 -exp(- kr 2 log 2 k
).

⊓ ⊔

Proof of Counting Lemma for Multi-Relational Graphons

Proof of Lemma 11. This proof follows the same ideas as the proof of Lemma 4.1 in [START_REF] Lovász | Limits of dense graph sequences[END_REF].

Let n = |V (F )|. Let E * = {(k, i, j) | s ∈ [r] ∧ {i, j} ∈ E k ∧ i <
, i s , j s ). We define X t : [0, 1] n → R as X t (x) = t s=1 W ks (x is , x js ) e * s=t+1 V ks (x is , x js )
Subtracting the integral of two such polynomials for consecutive indices t,

[0,1] n X t (x) -X t-1 (x) ≤ [0,1] n t-1 s=1 W ks (x is , x js ) |W kt (x it , x jt ) -V kt (x it , x jt )| e * s=t+1 V ks (x is , x js ) ≤ [0,1] n |W kt (x it , x jt ) -V kt (x it , x jt )| ≤ 1 0 1 0 |W kt (x it , x jt ) -V kt (x it , x jt )| dx it dx jt ≤ ∥W kt -V kt ∥ 2 .
The last inequality follows from the fact that [0,1] 2 W kt (x, y) -V kt (x, y) is at most the cut norm of W kt -V kt (since it uses the rectangle [0, 1] 2 , rather than sup S×T ). As t(F, W ) = [0,1] n X e * (x) and t(F, V ) = [0,1] n X 0 (x), we can use the above inequality to bound

|t(F, W ) -t(F, V )| = e * t=1 [0,1] n X t (x) -X t-1 (x) ≤ e * t=1 [0,1] n X t (x) -X t-1 (x) ≤ e * t=1 ∥W kt -V kt ∥ 2 = r k=1 |E k |∥W k -V k ∥ 2 ≤ max k |E k |∥W k -V k ∥ r[ 2
Now, noting that t(F, V ) = t(F, V σ ) for all σ ∈ Σ, we find

|t(F, W ) -t(F, V )| ≤ max k |E k | inf σ∈Σ ∥W k -V σ k ∥ r[ 2 . ⊓ ⊔ 7.
3 Proof of the Large Deviation Principle for G [r] (n, p)

Here we prove Theorem 5. Our proof technique is inspired by the proof of Theorem 2.3 in Chatterjee and Varadhan [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF].

Proof of the upper bound of Theorem 5

Let

B [r] ( h, η) := {W ∈ W [r] | δ [r]
2 (W, h) ≤ η}. First, we claim that to prove the upper bound [START_REF] Jain | Extending Markov logic to model probability distributions in relational domains[END_REF], it is sufficient to prove that for any h ∈ W [r] ,

lim η→0 lim sup n→∞ 1 n 2 log P [r] n,p ( B [r] ( h, η)) ≤ -I [r] p ( h). (21)
Since F is compact, for each η > 0 we can construct a finite cover { B [r] ( h 1 , η), . . . , B [r] ( h k , η)} where ∪ k i=1 B [r] ( h i , η) ⊇ F and ∀i : h i ∈ F . Thus

P [r] n,p (F ) ≤ k i=1 P [r] n,p ( B [r] ( h i , η)).
From ( 21), there are functions g 1 , g 2 : R ≥0 → R such that

1 n 2 log P [r] n,p ( B [r] ( h, η)) ≤ -I [r] p ( h) + g 1 (η) + g 2 (n).
with lim η→0 g 1 (η) = 0 and lim sup n→∞ g 2 (n) = 0. Hence

P [r] n,p ( B [r] ( h, η) ≤ exp(-n 2 (I [r] p ( h) -g 1 (η) -g 2 (n))
) for any n and η > 0. We can thus bound

P [r] n,p (F ) ≤ k i=1 P [r] n,p ( B [r] ( h i , η)) ≤ k i=1 exp(-n 2 (I [r] p ( h i ) -g 1 (η) -g 2 (n)) ) ≤ k max i exp(-n 2 (I [r] p ( h i ) -g 1 (η) -g 2 (n))) = k exp -n 2 min i I [r] p ( h i ) -g 1 (η) -g 2 (n) . Hence 1 n 2 log( P [r] n,p (F )) ≤ min i I [r] p ( h i ) -g 1 (η) -g 2 (n) + 1 n 2 log(k)
. Note that k is finite for any η > 0 since F is compact. Then by taking the sup limit n → ∞ when η > 0, we get lim sup n→∞ 1 n 2 log( P [r] n,p (F )) ≤ min i

I [r] p ( h i ) -g 1 (η)
By taking the limit η → 0, we get lim sup

n→∞ 1 n 2 log( P [r] n,p (F )) ≤ inf h∈F I [r] p ( h).
Thus we have proven that ( 21) implies [START_REF] Jain | Extending Markov logic to model probability distributions in relational domains[END_REF].

With

B [r] ( h, η) := {W ∈ W [r] | W ∈ B [r] ( h, η)}, Eq (21) is equivalent to lim η→0 lim sup n→∞ 1 n 2 log P [r] n,p (B [r] ( h, η)) ≤ -I [r] p ( h). (22)
Since G [r] (n, p) has the distribution of an r-tuple of independent G(n, p) random variables, it is not difficult to see that for h ∈ W [r] with h = ( h 1 . . . h r ),

P [r] n,p ( h) = r k=1 P n,p ( h k ) and hence log P [r] n,p (B [r] ( h, η)) ≤ log r k=1 P n,p prj k B [r] ( h, η) ≤ log r k=1 P n,p B( h k , η) = r k=1 log P n,p B( h k , η)
where prj k (•) is the projection onto the k-th coordinate and B( h, η) = {W ∈ W | δ 2 (W, h) ≤ η}. Eq. ( 11) in the proof of the upper bound of Theorem 2.3 in Chatterjee and Varadhan [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF] states that for h ∈ W,

lim η→0 lim sup n→∞ 1 n 2 log P n,p (B( h, η)) ≤ -I p ( h)
Combining these two last inequalities, we get

lim η→0 lim sup n→∞ 1 n 2 log P [r] n,p (B [r] ( h, η)) ≤ lim η→0 lim sup n→∞ 1 n 2 r k=1 log P n,p (B( h k , η))) ≤ - r k=1 I p (prj k ( h)) = -I [r]
p ( h) This proves Eq [START_REF] Radin | The asymptotics of large constrained graphs[END_REF] and hence the upper bound.

Proof of the lower bound of Theorem 5

It is sufficient to prove for any h ∈ W [r] and arbitrary η > 0 that lim inf

n→∞ 1 n 2 log P [r] n,p ( B [r] ( h, η)) ≥ -I [r] p ( h). (23)
Since

B [r] ( h, η) ⊃ r k=1 B( h k , η/r), there holds lim inf n→∞ 1 n 2 log P [r] n,p ( B [r] ( h, η)) = lim inf n→∞ 1 n 2 log P [r] n,p (B [r] ( h, η)) ≥ lim inf n→∞ 1 n 2 log P [r] n,p r k=1 B( h k , η/r) = k k=1 lim inf n→∞ 1 n 2 log P n,p B [r] ( h k , η/r)
Applying the lower bound of Theorem 2.3 in Chatterjee and Varadhan [START_REF] Chatterjee | The large deviation principle for the erdős-rényi random graph[END_REF] we get that for each k;

lim inf n→∞ 1 n 2 log P n,p B [r] ( h k , η) ≥ -I p ( h k )
Combining these inequalities, we get

lim inf n→∞ 1 n 2 log P [r] n,p ( B [r] ( h, η)) ≥ - r k=1 I p (h k ) = -I [r] p (h)
This proves Eq [START_REF] Radin | Phase transitions in a complex network[END_REF] and hence the lower bound of the theorem.

Markov Logic Networks and Multi-Relational Graphons: Two Maximum-Entropy Models

In this section, we discuss the translations between probabilistic models represented in first-order logic and models represented in the multi-relational graph formalism. In particular, we focus on models constrained by relational statistics Q(α, ω) (the FOL setting) and homomorphism densities (the multirelational graph setting). As explained in Section 2.2, MLNs are maximum entropy models constrained by expected values of the statistics Q(α, ω).

From Multi-Relational Graph Representations to FOL Representations

There is a simple relationship between homomorphism densities t(F, G) and the statistics Q(α, ω) that we introduced for Markov logic networks in Section 2.2. First, we show that any multi-relational graph G = (V, E 1 , . . . , E m ) can be trivially represented as a first-order logic possible world ω. This is done as follows. We identify the domain ∆ with the set of vertices, i.e. ∆ = {v|v ∈ V}.

Then we set

ω G = {λ i (v 1 , v 2 )|v 1 , v 2 ∈ ∆ and {v 1 , v 2 } ∈ E i and i ∈ {1, 2, . . . , m}}.
The possible world ω G plays the same role in the statistic Q(α, ω) as G plays in the homomorphism density t(F, G). It remains to show how to construct a formula α as a counterpart of the graph F. One way to construct such an α is as follows. Given a graph F = (V F , E F 1 , . . . , E F m ), we define α as a conjunction of the following set of first-order logic atoms

A = {λ i (x v , x w )|v, w ∈ V F and {v, w} ∈ E F i and i ∈ {1, 2, . . . , m}}.
Indeed, it is not difficult to see that if we let α F = a∈A a, then

Q(α F , ω G ) = t(F, G).
Remark 4 For Markov logic networks, it is more common to use formulas in the form of a disjunction of atoms rather than a conjunction. If we construct

α ′ F = {¬a|a ∈ A} then it follows that Q(α ′ F , ω G ) = 1 -t(F, G)
. Hence, we can express the same type of constraints using also disjunctions.

It follows from the discussion above that for any set of constraints expressed using homomorphism densities of multi-relational graphs, we can formulate an equivalent set of constraints using first-order logic conjunctions or disjunctions.

From FOL Representations to Multi-Relational Graph Representations

Next we discuss the other direction. We describe when it is possible to represent constraints in the "world" of relational structures by constraints on multi-relational graphs. One obvious restriction is that we can only represent constraints on possible worlds where all relations are symmetric, irreflexive and binary. That is we will only be able to model distributions over possible worlds where the following first-order logic sentences are satisfied for all relations r that we use: ∀x : ¬r(x, x) (irreflexivity) ∀x, y : r(x, y) ⇒ r(y, x) (symmetry) .

From now on we will assume that all possible worlds ω satisfy these two constraints and we will not always state this explicitly if there is no risk of confusion.

Let α be a conjunction of first-order logic atoms without constants and ω be a possible world on a domain ∆ which satisfies the irreflexivity and symmetry constraints. We first show how to construct graphs F α and G ω such that Q(α, ω) = t(F α , G ω ). We define V F = {v x |x is a FOL variable contained in α} and V G = {v c |c ∈ ∆}. Then we define

F α = (V F , {{v x , v y }|λ 1 (x, y) ∈ α or λ 1 (y, x) ∈ α}, . . . , {{v x , v y }|λ m (x, y) ∈ α or λ m (y, x) ∈ α}) G ω = (V G , {{v x , v y }|λ 1 (x, y) ∈ ω or λ 1 (y, x) ∈ ω}, . . . , {{v x , v y }|λ m (x, y) ∈ ω or λ m (y, x) ∈ ω})
Next we illustrate the above outlined translation on an example. We now construct the respective graphs F α and G ω , following the steps outlined above. For F α we get

V F = {v x , v y , v z } E F = {{v x , v y }, {v y , v z }},
and for G ω :

V G = {v Alice , v Bob , v Eve } E G = {{v Alice , v Bob }, {v Alice , v Eve }, {v Bob , v Eve }}.
It is easy to check that Q(α, ω) = t(F, G) = 12/27, as expected.

So far we have only explained how to represent constraints which are specified using conjunctions of positive first-order logic literals. It is not difficult to also represent constraints specified by formulas in the form of disjunctions of negative first-order logic literals. If we are given a constraint E[Q(¬a 1 ∨ . . . ¬a m , .)] = t, where a 1 , . . . , a m are first-order logic atoms, then we can replace it by E[Q(a 1 ∧ • • • ∧ a m , .)] = 1 -t, which we already know how to represent using multi-relational graphs.

Finally, what remains is to show how to encode constraints represented using either disjunctions or conjunctions of first-order logic literals without the restriction that the literals in them must be all negative or positive, respectively. For this we can exploit the inverse Moebius transform (see e.g. [START_REF] Lovász | Large networks and graph limits[END_REF][START_REF] Kennes | Computational aspects of the mobius transform[END_REF][START_REF] Schulte | Modelling relational statistics with bayes nets[END_REF], in particular for homomorphism densities, see Eq. 7.11 in Lovász [START_REF] Lovász | Large networks and graph limits[END_REF]).

Let α = ¬a 1 ∧ • • • ∧ ¬a l ∧ a l+1 ∧ • • • ∧ a m
be a conjunction of first-order logic literals. We now need to show how to represent Q(α, ω) in the graph domain.

Let

F α = (V F , E + 1 , E - 1 , • • • , E + r , E - r
) be a signed multi-relational graph where V F is defined above, E + i = {{v x , v y }|λ i (x, y) ∈ α or λ i (y, x) ∈ α} and E - i = {{v x , v y }|¬λ i (x, y) ∈ α or ¬λ i (y, x) ∈ α}. With this notation we can then write: Q(α, ω) = t(F α , G ω ), where t is the subgraph density of signed multi-relational graphs defined in Eq. 9 and G ω is defined above.

In conclusion, we have shown that for every constraint that we can write using function-free quantifier-free first-order logic formulas, we can write the equivalent constraint in the graph domain. Note, however, that we restrict ourselves to possible worlds represented over symmetric non-reflexive binary relations.

An example on how a MLN is represented by Multi-relational Graphons

Using the equivalence between MLN and multi-relational graphs, we transform a MLN Φ into multi-relational graphons with maximum entropy. Φ contains two binary and symmetric relations f riends(x, y) and acquitances(x, y) with the following formulas, ∞ : f riends(x, y) ⇒ f riends(y, x) ∞ : acquitances(x, y) ⇒ acquitances(y, x)

∞ : ¬f riends(x, x) ∞ : ¬acquitances(x, x) w 1 : f riends(x, y) ∧ f riends(y, z) ⇒ f riends(x, z) (24)
w 2 : f riends(x, y) ∧ acquitances(y, z) ⇒ acquitances(x, z)

where w 1 , w 2 ∈ R. The probability distribution of the possible worlds ω of Φ is the Gibbs distribution is given by, I [2] (W ) subject to

p Φ (ω) = 1 Z exp(w 1 • Q 1 (ω) + w 2 • Q 2 (ω))
u 1 = 1 -t(F 1 , W ) and u 2 = 1 -t(F 2 , W )
where E[Q(α 1 , .)] = u 1 and E[Q(α 2 , .)] = u 2 where α 1 is the formula given by Eq. 24 and α 2 is the formula given by Eq. 25, and F 1 and F 2 are signed multi-relational graphs which are shown in Figure 1. Note that the constraints

u i = 1-t(F i , W ) i = 1, 2 come from the Boolean identity p ⇒ q = 1-(p∧¬q).
Once the optimization problem is solved, computing marginal probability of a logical formula ϕ, which is represented by the signed graph F ϕ , is easy. It is just to compute 1 M i t(F ϕ , W * i ) where M is the number of global minimizers W * i of the above optimization problem.

The key point in the estimation of the most typical worlds from a given set of formulas is to solve the optimization problem in the space of multi-relational graphons. This is a problem posed in a space of infinite many dimensions. Although it is not clear that the problem is computable, prior work on constrained graphons with maximum entropy described in Section 9.3, found by numerical experiments that the global solutions of the maximum entropy problem seem to be stepfunctions.

Maximum Entropy Distributions

As described in Section 2.3, MLNs are maximum entropy models. In particular they are the model with given statistics Q(α, .), that maximize Gibbs entropy. As we described in detail in the previous sections, constraints equivalent to those on the statistics Q can be also represented in the graph domain using homomorphism densities. If we fix the number of vertices and find the model that maximizes Gibbs entropy in the graph domain, we end up with a multirelational variant of exponential random graph model2 [START_REF] Wasserman | Logit models and logistic regressions for social networks: I. an introduction to markov graphs andp[END_REF]. However, we are not interested in finite graphs and finite relational structures since the large deviation principle shows that graphons maximize the Boltzmann entropy. Let us consider some first-order language with binary relations and denote by Ω n the set of all possible worlds on a domain of size n, for which the binary relations are symmetric and non-reflexive. It follows from the large deviation principle that if we select from the relational structures Ω n that violate the given Q-statistics constraints the least and then pick one of them uniformly at random, the limit of this sequence will be a multi-relational graphon that has maximum Boltzmann entropy among the graphons satisfying the constraints that we obtain by transforming the Q-constraints into the graph domain. This is an important result on its own because it justifies the use of maximum-Boltzmann-entropy models for modelling multi-relational data. It could also be potentially relevant as an answer to a question raised in Jaeger and Schulte [START_REF] Jaeger | Inference, learning, and population size: Projectivity for SRL models[END_REF] asking which distributions, satisfying some given constraints one should choose. We answer this question (for undirected multi-relational graphs): one should choose the multi-relational graphons that maximize Boltzmann entropy. 9 Related Work

Multi-Relational Graphs as Compact Decorated Graphs

Compact Decorated Graphs (CDG) are a generalization of simple graphs due to Lovász and Szegedy [START_REF] Lovász | Limits of compact decorated graphs[END_REF]. CDG are defined as follows.

Definition 16 (Compact decorated graphs) Let K be a compact separable topological space such that K contains an element 0 representing no edge. A graph decorated with K is a symmetric function G :

[n] × [n] → K.
Equivalently, CDG is a complete graph K n with each edge by an element of K. The set of all F-decorated graphs with n nodes is denoted by G n (F) and G(F) = ∪ n>0 G n (F).

Definition 17 (K-graphon) Let P (K) be the set of Borel probability measures on K. We denote by W(K) the set of symmetric functions W (K) : [0, 1] 2 → P (K). The elements of W(K) are called K-graphons.

Intuitively, the idea of K-decorated graph is to model complex relations for every pair of nodes. Hence the element of K associated with an edge can be seen as a random variable and as the number of nodes goes to infinity, the distribution of the random variable between two nodes x, y ∈ [0, 1] converges to W (x, y) ∈ P (K).

Graph homomorphism density on W(K)

Graph homomorphism densities on W(K) may be defined using C-decorated graphs. Let C be the set of functions K → R. Hence a C -decorated graph F = (V, E) is a simple graph on which each edge ij is associated with a function

F ij : K → R. Definition 18 Let W be a K-graphon and let f ∈ C. Define W f : [0, 1] 2 → R by W f (x, y) = K f dW (x, y).
The graph homomorphism density on W(K) is computed by,

t CDG (F, W ) = [0,1] k 1≤i≤j≤k W Fij (x i , x j ) i∈V (F ) dx i ( 26
)
where F is a C-decorated graph with k nodes and W is a K-graphon. Note that ( 26) is generalizing the earlier formula (8) when r = 1.

Convergence on CDG

Loväsz in [START_REF] Lovász | Large networks and graph limits[END_REF] shows that any graphon can be seen as the limit of a sequence of growing graphs such that (

G n ) ∞ n=1 converges to W ∈ W iff (t(F, G n )) ∞ n=1
converges to t(F, W ) for every simple graph F . For CDG, there is a similar result. Instead of simple graphs, it uses the notion of Generation system of decorated graphs.

Definition 19 (Generation system. (Definition 2.2 in [START_REF] Lovász | Limits of compact decorated graphs[END_REF])) We say that a set F ⊆ C is dense if for every ϵ > 0 and f ∈ C there is a g ∈ F such that |g(x) -f (x)| ≤ ϵ for every x ∈ K. We say that F ⊆ C is a generating system if the linear space generated by the elements of F is dense.

Theorem 9 (Convergence on CDG Theorem 2.6 in [START_REF] Lovász | Limits of compact decorated graphs[END_REF]) Let F be a countable generating set and let (W n ) ∞ n=1 be a sequence of F-graphons such that (t(F, W n )) is a convergent sequence for every F ∈ G(F). Then there is a F-graphon W such that t(F, W n ) → t(F, W ) for every F ∈ G(C).

Note that in graphon space the graphs converge to a graphon function W such that W (x, y) ∈ [0, 1] for all x, y ∈ [0, 1] 2 and in F-graphon space, the CDG converge to a Borel probability measure on F instead a number in [0, 1].

Multi-Relational Graphs as Compact Decorated Graphs

Any multi-relational graph can be represented as a compact K-decorated graph. As follows, Lovász and Szegedy describe a special case of CDG, Parallel Colored Graphs (P CG) where K = {0, 1} r , shown in Example 2.10 [START_REF] Lovász | Limits of compact decorated graphs[END_REF]. Each edge of a P CG is a general probability distribution on {0, 1} r . From Theorem 9, the limits of growing P CG are K-graphons, W : [0, 1] 2 → [0, 1] 2 r -1 since a probability distribution on {0, 1} r can be represented using a vector in [0, 1] k for k = 2 r -1.

A multi-relational graphon can be seen as a restricted version of the limit of a sequence of P CGs in which the probability distribution for every W (x, y) is the product of r independent Bernoulli distributions. Hence the limit object of a convergent sequence of growing multi-relational graphs is a symmetric and measurable function W : [0, 1] 2 → [0, 1] r .

Remark 5

The formula for subgraph density on multi-relational graphons (8) can be obtained from the formula for homomorphism density of a CDG [START_REF] Shalizi | Consistency under sampling of exponential random graph models[END_REF]. We use two F-decorated graphs,

F = {g 1 , g 2 : [0, 1] r → [0, 1] | g 1 (x) = k x k and g 2 (x) = 1}
where g 1 and g 2 decorate every edge and non-edge. To see that, this yields the subgraph density formula for multi-relational graphs let F CDG be the multirelational graph F in the form of a F-graph. By a simple computation we have

W F CDG ij (x, y) = r k=1 W k (x, y) if ij is connected in F CDG 1 otherwise
Hence it is easy to see that t CDG (F CDG , W ) = t(F, W ).

The AHK Model

The AHK Model given in Jaeger and Schulte [START_REF] Jaeger | A complete characterization of projectivity for statistical relational models[END_REF] is an infinite exchangeable array which characterizes the probability distributions that are projective on relational structures. A probability distribution is projective when the marginal of the distribution for size-n structures on induced sub-structures of size k < n is equal to the given distribution for size-k structures. More precisely AHK is defined as follows.

U i = (U ∅ , U i1 , • • • , U im , U (i1,i2) , • • • , U (im-1,im) , • • • , U (i1,••• ,im) ) (27)
is a vector containing all U i ′ -variables with i ′ ⊂ i in lexicographic order. f m is invariant under permutations, in the sense that for any permutation σ :

[m] → [m] of [m] f m (U σ i ) = f m (U i ) σ
where U σ i is the new multi-dimensional array obtained from U i where the dimensions i are replaced by the ordered tuple whose entries are (σ(i 1 ), • • • , σ(i m )).

Relation between AHK model and Multi-Relational Graphons

Recall that G(n, W ) was mentioned in the Introduction and it is the random graph of n vertices from a given graphon W sampled by picking n numbers x 1 , x 2 , . . . , x n from [0, 1] uniformly at random and connecting every possible edge x i and x j with probability W (x i , x j ).

Let X = G(n, W ). The random variable X i1i2 can be written as

X i1i2 = g(U ∅ , U i1 , U i2 ) ( 28
)
where U ∅ , U i1 , U i2 ∈ [0, 1] are uniform random variables and g W (x 0 , x 1 , x 2 ) = 1 x 0 ≤ W (x 1 , x 2 ) 0 otherwise .

Note that (28) omits the random variable U (i1i2) so that X is a general 2dimensional random array. This is because the sampling process of G(n, W ) does not consider the combination of values of i 1 and i 2 to sample X i1i2 . For multi-relational random graphs X = G [r] (n, W ) where W ∈ W [r] , X i1i2 can be represented by the vector (g W1 (U ∅ , U i1 , U i2 ), • • • , g Wr (U ∅ , U i1 , U i2 )). Hence it is clear that any multi-relational graphon is an AHK model with maximum arity 2 where the random variable U i1i2 in the representation is omitted.

Prior work on constrained graphons with maximum entropy

Radin et al. [START_REF] Radin | Phase transitions in a complex network[END_REF] proposed graphons with maximum entropy to model large graphs constrained by subgraph density. Radin et al. [START_REF] Radin | The asymptotics of large constrained graphs[END_REF] showed through numerical experiments that graphons with maximum entropy constrained subgraph densities of edges and triangles are stepfunctions.

Kenyon et al. [START_REF] Kenyon | Multipodal structure and phase transitions in large constrained graphs[END_REF] prove rigorously the optimal constrained graphon are stepfunctions when the constraints are on subgraph densities of edge and kstar graphs.

Aristoff et al. [START_REF] Aristoff | Asymptotic structure and singularities in constrained directed graphs[END_REF] prove the large deviation principle for random directed graphs when the constraints are on edge and outward p-star densities.

However it is an open problem to prove that the conjecture is correct. If the conjecture is true, then the maximum entropy graphons can be obtained by solving a finite dimensional non-linear optimization problem.

Conclusions

The Large Deviation Principle for Erdős-Rényi multi-relational graphs enables proving the Principle of Maximum Entropy (PME) for multi-relational graphs. This principle states that the most typical random multi-relational graphs constrained by any closed region in the space of multi-relational graphons are multi-relational graphons with maximum Boltzmann entropy. These Boltzmann entropy maximizers, unlike MLN which are Gibbs entropy maximizers, are a projective model. Thus, multi-relational graphons with maximum entropy are consistent statistical models, in the sense that when the number of nodes of an observed multi-relational network goes to infinity then the network converges to a multi-relational graphon. We show that PME on multi-relational graphs enables the notion of the most typical worlds of a MLN by picking the global solutions of an optimization problem. If Radin's conjecture holds, the optimal computation of the most typical graphons (worlds), constrained by the expectation of logical formulas, can be obtained by a non-linear optimization of finite dimension.

As a candidate theory for MLNs, multi-relational graphon theory has two main issues. The first one is that there is no a rigorous proof of the conjecture raised by Radin et al. in [START_REF] Radin | The asymptotics of large constrained graphs[END_REF], neither for graphons nor multi-relational graphons. However this conjecture has been proved for a special case [START_REF] Kenyon | Multipodal structure and phase transitions in large constrained graphs[END_REF]. The second limitation is that Multi-relational graphon theory is only for symmetric and binary relations. We think that it is possible to extend Multi-relational graphons to higher order relations as long as the relations are symmetric. For non-symmetric relations, the problem is more difficult since it is not clear what is a suitable limiting space for sequences of growing non-symmetric relations [START_REF] Nešetřil | First-order limits, an analytical perspective[END_REF].

Declarations

5. 1 W

 1 -sampling for multi-relational graphons Definition 9 (Sampling weighted multi-relational graphs) Let W ∈ W [r] and let S = {x 1 , • • • , x n } ⊂ [0, 1] be an ordered set, then we denote by H(S, W ) the multi-relational weighted graph [H ! , • • • , H r ] obtained from W = [W 1 , • • • , W r ] by assigning the common node set to V (H(S, W )) = {1, • • • , n} and the weight for H k is equal to

[r] 2 (

 2 G, W ) ≤ ϵ. There is a sufficient large k such that ϵ ≥ 37r √ log k . Then, from Lemma 10 there holds δ[r]

Example 1

 1 Let α = friends(x, y) ∧ friends(y, z) and ω = {friends(Alice, Bob), friends(Bob, Alice), friends(Alice, Eve), friends(Eve, Alice), friends(Bob, Eve), friends(Eve, Bob)}.

Fig. 1

 1 Fig. 1 Two signed muulti-relational graphs. The blue edges correspond to 'friends' relations and the red one is 'acquitances' relation.

Definition 20 Example 2

 202 Let [n] d ̸ = be the set of d-tuples with distinct entries from [n] d . Let ⟨n⟩ d be the set of d-tuples with distinct and ordered entries from [n] d . Definition 21 Let ω be a relational structure with maximal arity(ω) = a ≥ 1. Let D m (ω) m = 1, • • • , a be the arity-m data of ω. D m (ω) can be seen as a collection of adjacency matrices referring the connections of m distinct elements. Let D m (ω ↓ i) be the projections of D m (ω) in terms of i ∈ ⟨n⟩ m distinct elements where n is number of elements of ω. Let T m be the space of possible values of D m (ω ↓ i) when |i| = m. Figure 2 shows an example of AHK model. a) The relational structure ω : symmetric and irreflexive relations

Fig. 2 a

 2 Fig. 2 a) shows a relational structure with 2 unary predicates and 2 binary relations. The circles represent the elements of the domain, boxes attached to the nodes indicate the values of the unary relations, and edges (with arrows) represent the binary relations.

  j} be the collection of all edges of the multi-relational graph. Number the elements in E

* from 1 to e * = |E * | and for s ∈ E * we denote the s-th triple in E * by (k s

What precisely we mean by being a limit is explained later.

Exponential random graph models are very similar to Markov logic networks.

Acknowledgements. This work is partially supported by a PhD student scholarship from SENESCYT (Ecuador) and by ERC-StG 240186 MiGraNT: Mining Graphs and Networks, a theory-based approach. The authors would like to thank Ondrej Kuzelka and all the anonymous reviewers for reviewing this work and providing very insightful comments.

Appendix

In this section we provide the necessary concepts from topology, measure theory and compactness on vector spaces. We mostly follow notation and definitions from [START_REF] Dudley | Real analysis and probability[END_REF] and [START_REF] Pedersen | Analysis now[END_REF], except for the definitions of measure preserving map from [START_REF] Walters | An introduction to ergodic theory[END_REF].

Some concepts of topology

Definition 23 (Topological Closure and Interior of a set) Let X be a topological space and let A ⊂ X . The topological closure of A and denoted by A is the intersection of all closed sets that contain A. The interior of A and denoted by A • is the union of all open sets are contained in A. Now we define compact spaces which are a type of topological spaces.

Definition 24 (Compact space) Let X be a topological space. We say that X is compact if for every sequence (x i ) ∞ i=1 in X there is a subsequence (x ni ) ∞ i=1 that is convergent. Another alternative definition for compactness is the following. We say that the family of open sets

Compactness of a space S ensures the existence of limit points i.e. limits of convergent subsequences of any sequence on S. For instance, every closed and bounded subset of R n is compact.

Lower-continuity is a sufficient condition to state that inf x∈X f (x) and min x∈X f (x) are equivalent when X is a compact set.

Some concepts of measure theory

Next we define σ-algebras, which are building blocks of probability theory.

Definition 26 (σ-Algebra) Let X be a set. We say that a collection of subsets of X, A X ⊂ P(X), is a σ-algebra on X if (i) A X includes ∅, (ii) is closed under complement, and (iii) is closed under countable unions.

Having defined σ-algebras, we now define the following notions that we will need in the technical arguments in this paper: measure functions, outer measures and measurable sets, measure spaces, measure functions and measurepreserving maps.

Definition 27 (Measure function) Let A X be a σ-algebra on X. We say that a function µ :

Definition 28 (Outer measure) Let A X be a σ-algebra and let µ X be a measure on X. For E ⊂ X the outer measure of E is defined by,

(Here we note that the infimum of an empty set is +∞.)

Next we define measurable sets using the just introduced notion of outermeasure.

Definition 29 (Measurable set) We say set F ⊂ X is a µ * -measurable, where µ * us an outer-measure, iff for every set E ⊂ X, we have

Let M X (µ * X ) be the collection of sets in X that are measurable. Then M X (µ * ) is σ-algebra and µ * is a measure function on it (see e.g. Lemma 3.1.8 [START_REF] Dudley | Real analysis and probability[END_REF]): hence (X, M X (µ * X ), µ * X ) is a measure space.

Definition 30 (Measure space) We say that the triple (X , A, µ) is a measure space if X a topological space, A is the Borel σ-algebra generated by the open sets of X , and µ is a measure function on A.

Definition 31 (Measurable function) Let (X i , A i , λ i ), i = 1, 2 be measure spaces. Then f : X 1 → X 2 is a measurable function if for any Borel set A ∈ A 2 then its preimage f -1 (A) is a Borel set.

Definition 32 (Measure preserving map) Let (X i , A i , λ i ), i = 1, 2 be two measure spaces. Then the measurable function σ : X 1 → X 2 is a measure preserving map or Measure preserving transformation if for any Borel set A ∈ A 2 we have λ 1 (σ -1 (A)) = λ 2 (A).