Lifted MAP Inference for Markov Logic Networks

Somdeb Sarkhel, Deepak Venugopal, Parag Singla, Vibhav GogateAISTATS 2014 · OpenReview

Abstract

In this paper, we present a new approach for lifted MAP inference in Markov Logic Networks (MLNs). Our approach is based on the following key result that we prove in the paper: if an MLN has no shared variables between different atoms in a formula (non-shared MLNs), MAP inference is domain liftable. We demonstrate that these networks can be reduced to much smaller propositional problems, enabling efficient inference on massive datasets.

Introduction

Markov Logic Networks (MLNs) provide a powerful framework for combining first-order logic with probabilistic graphical models. Despite their expressive power, MLNs face a significant scalability challenge known as the "grounding bottleneck." Standard propositional algorithms require creating a random variable for every possible grounding of every predicate. For instance, a predicate like Friends(x, y) with a domain of 1,000 individuals results in 1,000,000 variables. This combinatorial explosion makes Maximum A Posteriori (MAP) inference—finding the most likely state of the world—computationally prohibitive for real-world datasets. This paper addresses this challenge by introducing a method for "lifted" inference, which reasons about groups of objects collectively to avoid explicit grounding.

Theoretical Framework

The proposed approach for Lifted MAP inference is built upon two primary theoretical contributions:

  1. Non-Shared MLNs: The authors define "non-shared" MLNs as those where no logical variable is shared between different atoms in a formula (e.g., $R(x) \lor S(y)$ is non-shared, whereas $R(x) \lor S(x)$ is shared). They prove that for such networks, MAP inference is "domain liftable," meaning its complexity is polynomial relative to the size of the object domains.
  2. Reduction to Propositional MAP: Non-shared MLNs can be reformulated as standard Markov networks where the number of variables corresponds to the number of first-order atoms rather than the total number of groundings.
  3. Extreme Point Property: For MLNs without "self-joins" (where a predicate appears only once per formula), the authors prove that the MAP solution lies at "extreme points." This implies that for any predicate, either all its groundings are true or all are false, reducing the search space from exponential in domain size to $2^n$, where $n$ is the number of predicates.

The researchers implemented two lifted solvers: L-ILP, utilizing the Gurobi Integer Linear Programming solver, and L-MWS, a lifted version of the MaxWalkSAT local search algorithm.

Experimental Setup

The performance of the lifted solvers was evaluated on three benchmarks:

  • Student MLN: A synthetic benchmark designed to test scalability across varying domain sizes.
  • WebKB: A real-world dataset involving web page categories and link structures.
  • Citation Information-Extraction (IE): A real-world dataset used for deduplicating and extracting information from research citations.

Results

The experimental results highlight the massive scalability and efficiency of the proposed lifted approach. On the Student benchmark, the lifted algorithms successfully handled domains resulting in 62 billion ground clauses. In contrast, traditional propositional solvers like Tuffy or standard MaxWalkSAT ran out of memory at significantly smaller scales, typically around 100 million clauses.

Relative gap vs domain size for Student and WebKB datasets.

As shown in the figure above, as domain sizes increased, the "relative gap" (error) of propositional solvers increased significantly, while the lifted solvers remained highly accurate or exact. Furthermore, L-ILP was able to find exact solutions in less than 10 seconds for problems where ground solvers failed entirely.

Cost optimization over time for various solvers.

The speed and quality of the solutions are further illustrated in the cost-over-time analysis. The lifted solvers reach lower costs much faster than state-of-the-art propositional solvers like TUFFY.

Conclusion

The power of this approach lies in exploiting symmetry. In non-shared MLNs, many "worlds" have identical probabilities, allowing the solver to check only a fraction of the total space. Because the method reduces the lifted problem back into a propositional format, it allows for "plug-and-play" use of existing high-performance SAT or ILP solvers. While the efficiency degrades as more variables are shared, the authors provide a path for arbitrary MLNs through partial grounding. Future work will explore handling more complex structures, including symmetry breaking and the inclusion of function symbols.

Summary updated

Abstract

In this paper, we present a new approach for lifted MAP inference in Markov Logic Networks (MLNs). Our approach is based on the following key result that we prove in the paper: if an MLN has no sha...
BibTeX
@inproceedings{sarkhel2014lifted,
  author = {Somdeb Sarkhel and Deepak Venugopal and Parag Singla and Vibhav Gogate},
  title = {{Lifted MAP Inference for Markov Logic Networks}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=dps8QTgbOu},
}
Figure