Random coloured digraphs defined by a Markov logic network

A Markov Logic Network (MLN) is a probabilistic relational model used in Statistical Relational Artificial Intelligence for defining a probability distribution on the set of possible worlds with domain D for an arbitrary finite domain D. An MLN consists of soft constraints with associated weights which are nonnegative real numbers. In this study we consider a language speaking about a property P(x) and a relation R(x, y). We consider an MLN for which every Boolean combination of P(x) and R(x, y) is a soft constraint (with associated weight). Let n denote the size (cardinality) of the domain. We show that, for every choice of weights, if the weights are scaled by 1/n then, for every first-order sentence varphi, the probability that varphi holds tends to either 0 or 1 as n → ∞; that is, a 0-1 law for first-order logic holds. Morover, the limit probability does em not depend on the weights. If we instead use the standard semantics of MLNs, in the case of which the weights are em not scaled, then the limit behaviour is more complicated and em depends on the weights. With unscaled weights we get 7 qualitatively different cases which depend on the weights. In some cases we have a 0-1 law for first-order logic, in some cases not, but we may still have a convergence law. The influence of the weights on the asymptotic probability of a first-order sentence may be in the form of a sudden ``phase transition'' from one of the 7 cases to another. The presence of a convergence law has positive implications for inference on large domains.