cs.AISep 4, 2025

Domain size asymptotics for Markov logic networks

Authors: Vera Koponen

Organizations: Department of Mathematics, Uppsala University, Sweden.

Abstract

A Markov logic network (MLN) M\mathbb{M} determines a probability distribution PnM\mathbb{P}_n^\mathbb{M} on the set Wn\mathbf{W}_n of structures, or ``possible worlds'', with domain {1,…,n}\{1, \ldots, n\}. We study the properties of such distributions as nn tends to infinity. We show that with mild assumptions on an MLN M\mathbb{M} with one soft constraint with an arbitrary positive weight the distribution PnM\mathbb{P}_n^\mathbb{M} will behave quite differently from the uniform distribution Pnuni\mathbb{P}_n^{uni} on Wn\mathbf{W}_n for all sufficiently large nn. For a language with only one relation symbol RR which has arity 1 we give an almost complete characterization of the possible asymptotic behaviours of PnM\mathbb{P}_n^\mathbb{M} as n→∞n \to \infty, where M\mathbb{M} may be any MLN for this language. The asymptotic behaviour depends on the soft constraints and weights of the MLN. This characterization is used to show that if the language under consideration contains at least one relation symbol of arity 1 then the following holds: (a) There is an MLN M\mathbb{M} such that for every lifted Bayesian network (LBN) G\mathbb{G} there are infinitely many nn such that M\mathbb{M} and G\mathbb{G} determine different distributions on Wn\mathbf{W}_n. (b) There is an LBN G\mathbb{G} such that for every MLN M\mathbb{M} there are infinitely many nn such that G\mathbb{G} and M\mathbb{M} determine different distributions on Wn\mathbf{W}_n. We also show that, in the limit, the weight dimension and the domain size dimension may behave completely differently.

Figures & tables

Explore similar work

Jun 16, 2026

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 DD for an arbitrary finite domain DD. 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)P(x) and a relation R(x,y)R(x, y). We consider an MLN for which every Boolean combination of P(x)P(x) and R(x,y)R(x, y) is a soft constraint (with associated weight). Let nn denote the size (cardinality) of the domain. We show that, for every choice of weights, if the weights are scaled by 1/n1/n then, for every first-order sentence φ\varphi, the probability that φ\varphi holds tends to either 0 or 1 as n→∞n \to \infty; 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.
May 10, 2026

Weighted Rules under the Stable Model Semantics

We introduce the concept of weighted rules under the stable model semantics following the log-linear models of Markov Logic. This provides versatile methods to overcome the deterministic nature of the stable model semantics, such as resolving inconsistencies in answer set programs, ranking stable models, associating probability to stable models, and applying statistical inference to computing weighted stable models. We also present formal comparisons with related formalisms, such as answer set programs, Markov Logic, ProbLog, and P-log.
Mar 10, 2026

Learning Bayesian and Markov Networks with an Unreliable Oracle

We study constraint-based structure learning of Markov networks and Bayesian networks in the presence of an unreliable conditional independence oracle that makes at most a bounded number of errors. For Markov networks, we observe that a low maximum number of vertex-wise disjoint paths implies that the structure is uniquely identifiable even if the number of errors is (moderately) exponential in the number of vertices. For Bayesian networks, however, we prove that one cannot tolerate any errors to always identify the structure even when many commonly used graph parameters like treewidth are bounded. Finally, we give algorithms for structure learning when the structure is uniquely identifiable.