Abstract
Markov Logic Networks (MLNs) are a powerful framework for combining first-order logic and probabilistic graphical models. However, this research demonstrates significant theoretical limitations in their ability to represent "aggregators"—functions like XOR or Majority that summarize information from multiple parents—without distorting the underlying data distribution. By introducing the concept of "S-saturated" aggregators and utilizing an infinite-limit proof technique, the authors show that standard MLNs without auxiliary variables are restricted to a narrow class of dependencies. This work highlights the mathematical necessity of auxiliary variables for complex relational modeling and points toward more flexible alternatives like Relational Logistic Regression.
Introduction
In probabilistic modeling, a common requirement is adding a new "dependent" variable to an existing model. For instance, in a social network model, one might add a variable to identify "super-connectors" based on their friendship counts. Ideally, this new variable should act as a "leaf node" or a pure effect, leaving the original distribution of friendships unchanged.
While this is straightforward in directed models like Bayesian Networks, undirected relational models such as Markov Logic Networks (MLNs) present a challenge. In MLNs, adding a new variable and its defining rules often creates "side effects" that inadvertently alter the correlations between original variables. This paper investigates whether common logical aggregators (AND, OR, XOR, Majority) can be represented in MLNs as true dependent variables without these distorting side effects.
Theoretical Framework
To analyze these representational limits, the authors developed several key theoretical tools:
- DI-MLNs (Distinct-Individuals MLNs): A normal form for MLNs where logical variables are constrained to refer to different individuals. This form maintains the full power of standard MLNs while simplifying mathematical analysis.
- Parametric Representation: Complex logical formulas are converted into a simplified form based on counts—specifically, how many parents are true versus false.
- Infinite-Limit Proof Technique: The core methodology involves analyzing the behavior of model weights as the population size grows toward infinity. This allows the authors to determine if a specific aggregator is mathematically permissible within the MLN framework.
The "Saturation" Constraint
The study's most significant finding is that MLNs without auxiliary variables are limited to representing S-saturated aggregators. An aggregator is considered "saturated" if, once a certain threshold (S) of true and false parents is reached, the probability of the output variable remains constant regardless of additional parents.
This constraint explains why aggregators like XOR and Majority are impossible to represent perfectly in standard MLNs. XOR flips its output with every single input change, and Majority requires knowledge of every parent's state; neither ever "saturates" because every parent always matters to the final result. While quantifiers like "exists" ($\exists$) or "for all" ($\forall$) can handle small populations, they fail to escape this saturation trap as population sizes increase.
Key Results and Representability
The authors provide a comprehensive map of which aggregators can be successfully integrated into MLNs. As shown in the table below, deterministic AND/OR functions are representable because they saturate once a single 0 or 1 is encountered. In contrast, XOR and Majority cannot even be approximated.
Probabilistic aggregators like Noisy OR and Logistic Regression occupy a middle ground: they cannot be represented perfectly but can be approximated with high accuracy. The research also highlights Relational Logistic Regression (RLR) as a more flexible alternative that avoids these representational dead ends by design.
Comparative Analysis and the Role of Auxiliary Variables
By comparing their results with existing literature, the authors clarify the necessity of auxiliary variables. Previous methods that successfully represented complex aggregators relied on adding $O(n)$ extra variables. This paper proves that such variables are not merely a convenience but a mathematical requirement for representing non-saturated logic.
Conclusion and Future Work
This research establishes rigorous bounds on the representational capacity of MLNs. While standard MLNs are highly effective for many tasks, they struggle with global aggregators unless augmented with auxiliary variables. Future work may explore "Adaptive MLNs," where formula weights change based on population size, or focus on optimizing the inference complexity introduced by the necessary auxiliary variables.
Summary updated