Domain size asymptotics for Markov logic networks

• URL: http://arxiv.org/abs/2509.04192v1
• Date: Thu, 04 Sep 2025 13:15:02 GMT
• Title: Domain size asymptotics for Markov logic networks
• Abstract summary: A Markov logic network (MLN) determines a probability distribution on the set of structures.<n>We study the properties of such distributions as the domain size tends to infinity.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A Markov logic network (MLN) determines a probability distribution on the set of structures, or ``possible worlds'', with an arbitrary finite domain. We study the properties of such distributions as the domain size tends to infinity. Three types of concrete examples of MLNs will be considered, and the properties of random structures with domain sizes tending to infinity will be studied: (1) Arbitrary quantifier-free MLNs over a language with only one relation symbol which has arity 1. In this case we give a pretty complete characterization of the possible limit behaviours of random structures. (2) An MLN that favours graphs with fewer triangles (or more generally, fewer k-cliques). As a corollary of the analysis a ``$\delta$-approximate 0-1 law'' for first-order logic is obtained. (3) An MLN that favours graphs with fewer vertices with degree higher than a fixed (but arbitrary) number. The analysis shows that depending on which ``soft constraints'' an MLN uses the limit behaviour of random structures can be quite different, and the weights of the soft constraints may, or may not, have influence on the limit behaviour. It will also be demonstrated, using (1), that quantifier-free MLNs and lifted Bayesian networks (in a broad sense) are asymptotically incomparable, roughly meaning that there is a sequence of distributions on possible worlds with increasing domain sizes that can be defined by one of the formalisms but not even approximated by the other. In a rather general context it is also shown that on large domains the distribution determined by an MLN concentrates almost all its probability mass on a totally different part of the space of possible worlds than the uniform distribution does.

Related papers

• Dynamics of Gradient Descent with Large Step Size Near a Manifold of Flat Minima [39.50927136881194]
  An important quantity in the theory of gradient descent (GD) is the emphsharpness, defined as the largest eigenvalue of the objective Hessian.<n>Recent work bridges this gap in the setting of overparametrised least-squares with a emphsingle scalar output<n>We show that our framework applies to deep matrix factorisation under mild assumptions, yielding several new structural results.
  arXiv  Detail & Related papers  (2026-07-09T11:58:44Z)
• Random coloured digraphs defined by a Markov logic network [0.0]
  An MLN consists of soft constraints with associated weights which are nonnegative real numbers.<n>We consider a language speaking about a property $P(x)$ and a relation $(x, y)R.<n>For every choice of weights, if the weights are scaled by $1/n$ then for every first-order $varphi$ the probability that $varphi$ holds tends to either 0 or 1 as $n to in relational; that is, a 0-1 law for first-order logic holds.
  arXiv  Detail & Related papers  (2026-06-16T11:49:14Z)
• The Polynomial Counting Capabilities of Message Passing Neural Networks [4.61988967916659]
  We study the counting capabilities of MPNN beyond linear arithmetic.<n>We show that global counting constraints in node-labelled graphs can be checked using mean MPNN.<n>We also show how formulas with nested modalities can be captured by mean MPNN over graphs with tree-like structures.
  arXiv  Detail & Related papers  (2026-05-11T11:38:11Z)
• Stronger Welch Bounds and Optimal Approximate $k$-Designs [0.13048920509133805]
  A fundamental question asks how uniformly finite sets of pure quantum states can be distributed in a Hilbert space.<n>Welch bounds address this question, and are saturated by $k$-designs, i.e. sets of states reproducing the $k$-th Haar moments.<n>We derive strengthened Welch-type inequalities that remain sharp in this regime by exploiting rank constraints from partial transposition and spectral properties of the partially transposed Haar moment operator.
  arXiv  Detail & Related papers  (2026-02-13T17:05:26Z)
• Unitary Designs from Random Symmetric Quantum Circuits [0.8192907805418583]
  We study distributions of unitaries generated by random quantum circuits containing only symmetry-respecting gates. We obtain an equation that determines the exact design properties of such distributions.
  arXiv  Detail & Related papers  (2024-08-26T17:52:46Z)
• Understanding Domain-Size Generalization in Markov Logic Networks [1.8434042562191815]
  We study the generalization behavior of Markov Logic Networks (MLNs) across relational structures of different sizes. We quantify this inconsistency and bound it in terms of the variance of the MLN parameters. We observe that solutions known to decrease the variance of the MLN parameters, like regularization and Domain-Size Aware MLNs, increase the internal consistency of the MLNs.
  arXiv  Detail & Related papers  (2024-03-23T21:16:56Z)
• Causal Bandits with General Causal Models and Interventions [38.112806687145344]
  This paper considers causal bandits (CBs) for the sequential design of interventions in a causal system. The objective is to optimize a reward function via minimizing a measure of cumulative regret with respect to the best sequence of interventions in hindsight.
  arXiv  Detail & Related papers  (2024-03-01T02:28:49Z)
• Recurrent Neural Language Models as Probabilistic Finite-state Automata [66.23172872811594]
  We study what classes of probability distributions RNN LMs can represent. We show that simple RNNs are equivalent to a subclass of probabilistic finite-state automata. These results present a first step towards characterizing the classes of distributions RNN LMs can represent.
  arXiv  Detail & Related papers  (2023-10-08T13:36:05Z)
• Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems [46.71914490521821]
  This paper introduces a new extragradient-type algorithm for a class of non-nonconcave minimax problems. The proposed algorithm is applicable to constrained and regularized problems.
  arXiv  Detail & Related papers  (2023-02-20T08:37:08Z)
• A Functional-Space Mean-Field Theory of Partially-Trained Three-Layer Neural Networks [49.870593940818715]
  We study the infinite-width limit of a type of three-layer NN model whose first layer is random and fixed. Our theory accommodates different scaling choices of the model, resulting in two regimes of the MF limit that demonstrate distinctive behaviors.
  arXiv  Detail & Related papers  (2022-10-28T17:26:27Z)
• On Projectivity in Markov Logic Networks [7.766921168069532]
  Logic Logic Networks (MLNs) define a probability distribution on structures over varying domain sizes. Projective models potentially allow efficient and consistent parameter learning from sub-sampled domains.
  arXiv  Detail & Related papers  (2022-04-08T11:37:53Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)
• GANs with Conditional Independence Graphs: On Subadditivity of Probability Divergences [70.30467057209405]
  Generative Adversarial Networks (GANs) are modern methods to learn the underlying distribution of a data set. GANs are designed in a model-free fashion where no additional information about the underlying distribution is available. We propose a principled design of a model-based GAN that uses a set of simple discriminators on the neighborhoods of the Bayes-net/MRF.
  arXiv  Detail & Related papers  (2020-03-02T04:31:22Z)
• Generalized Sliced Distances for Probability Distributions [47.543990188697734]
  We introduce a broad family of probability metrics, coined as Generalized Sliced Probability Metrics (GSPMs) GSPMs are rooted in the generalized Radon transform and come with a unique geometric interpretation. We consider GSPM-based gradient flows for generative modeling applications and show that under mild assumptions, the gradient flow converges to the global optimum.
  arXiv  Detail & Related papers  (2020-02-28T04:18:00Z)
• Domain-Liftability of Relational Marginal Polytopes [18.320433800967]
  We study computational aspects of relational marginal polytopes. In particular, we show that weight learning of MLNs is domain-liftable whenever the computation of the partition function of the respective MLNs is domain-liftable.
  arXiv  Detail & Related papers  (2020-01-15T09:45:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.