Complex Markov Logic Networks: Expressivity and Liftability

Ondrej KuzelkaUAI 2020 · OpenReview

Abstract

We study expressivity of Markov logic networks (MLNs). We introduce complex MLNs, which use complex-valued weights, and show that, unlike standard MLNs with real-valued weights, complex MLNs are "fully expressive". We then observe that discrete Fourier transform can be computed using weighted first order model counting (WFOMC) with complex weights and use this observation to design an algorithm for computing "relational marginal polytopes" which needs substantially less calls to a WFOMC oracle than an existing recent algorithm.

Introduction: The Expressivity Gap in MLNs

In Statistical Relational Learning (SRL), the goal is to develop models that are both expressive and computationally efficient. Markov Logic Networks (MLNs) have long been a cornerstone of this field. However, they face a significant trade-off. To maintain "liftability"—where inference time is polynomial relative to domain size—researchers often restrict MLNs to specific classes, such as those using only two logical variables.

This paper identifies a fundamental limitation: these restricted MLNs are surprisingly weak. For a fixed set of logical formulas, varying the real-valued weights can only produce a very narrow range of distributions, typically resembling simple binomial distributions. Mathematically, the paper proves the "Measure Zero" problem: the set of distributions representable by standard MLNs is a measure-zero subset of all possible distributions. In practice, this means standard MLNs are almost never able to represent a target distribution exactly if the formulas are fixed.

Complex Markov Logic Networks (C-MLNs)

To bridge this gap, the author introduces Complex MLNs (C-MLNs). This framework incorporates two major shifts:

  1. Complex-Valued Weights: Weights are allowed to be complex numbers ($a + bi$).
  2. Sum-of-Exponentials: While a standard MLN defines probability using a single exponential function, a C-MLN uses a sum of $d$ exponentials.

By allowing complex weights, the model can leverage the power of the Discrete Fourier Transform (DFT). The partition function of an MLN with specific complex weights becomes mathematically equivalent to a point in the Fourier transform of the model's count distribution.

Expressivity and Fourier Logic

The shift to the complex domain allows for "Fourier logic," where weights act as frequencies. This enables the model to "pick out" or "cancel out" specific configurations of the world. For instance, a C-MLN can easily represent a distribution that is only non-zero for even numbers of a certain property, a task that standard MLNs struggle with.

Distributions of formula counts for standard MLNs (colored) vs. a complex MLN (black dots).

As shown in the figure above, standard MLNs (represented by the colored dots for different real weights $w$) produce smooth, unimodal distributions. In contrast, a C-MLN with complex weights (black dots) can represent much more complex, multi-modal distributions. Theorem 1 in the paper proves that any C-MLN containing a tautology formula is "fully expressive," meaning it can represent any distribution over the counts of its formulas.

Liftability and Efficiency

Crucially, moving to the complex domain does not sacrifice efficiency. The author demonstrates that Weighted First-Order Model Counting (WFOMC)—the primary engine for lifted inference—can be extended to handle complex weights without increasing algorithmic complexity. If a problem is solvable in polynomial time with real weights, it remains so with complex weights.

This insight leads to a new algorithm for computing Relational Marginal Polytopes, which define the limits of what a model can represent. The proposed algorithm requires significantly fewer calls to the WFOMC oracle, reducing the complexity from a factor exponential in the number of formulas to a polynomial factor ($|\Delta|^m$ vs $|\Delta|^{|\Psi| \cdot m}$).

Conclusion

Complex MLNs provide a path to full expressivity without losing the computational benefits of lifted inference. While practical implementation will require careful handling of numerical stability and potentially large weight vectors, the framework offers a powerful tool for class-level modeling. Future work may explore the statistics of entire populations where these expressive capabilities are most needed.

Summary updated

Abstract

We study expressivity of Markov logic networks (MLNs). We introduce complex MLNs, which use complex-valued weights, and show that, unlike standard MLNs with real-valued weights, complex MLNs are"fully expressive". We then observe that discrete Fourier transform can be computed using weighted first order model counting (WFOMC) with complex weights and use this observation to design an algorithm for computing "relational marginal polytopes" which needs substantially less calls to a WFOMC oracle than an existing recent algorithm.
BibTeX
@inproceedings{kuzelka2020complex,
  author = {Ondrej Kuzelka},
  title = {{Complex Markov Logic Networks: Expressivity and Liftability}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=zgSlkgAFj4},
}

Loading related content...

Figure