Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formula

Sagar Malhotra, Luciano Serafini

Abstract

Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order logic theory on a given finite domain. First-Order Logic theories that admit polynomial-time WFOMC w.r.t domain cardinality are called domain liftable. We introduce the concept of lifted interpretations as a tool for formulating closed-forms for WFOMC. Using lifted interpretations, we reconstruct the closed-form formula for polynomial-time FOMC in the universally quantified fragment of FO2, earlier proposed by Beame et al. We then expand this closed-form to incorporate cardinality constraints, existential quantifiers, and counting quantifiers (a.k.a C2) without losing domain-liftability. Finally, we show that the obtained closed-form motivates a natural definition of a family of weight functions strictly larger than symmetric weight functions.

Introduction: The Grounding Bottleneck

In Artificial Intelligence, combining formal logic with probability is essential for modeling complex, uncertain environments. A core task in this domain is Weighted First-Order Model Counting (WFOMC), which involves calculating the total weight of all possible "worlds" (models) satisfying a set of logical rules.

The primary challenge is the "Grounding Bottleneck." For a rule involving $n$ individuals, a naive approach checks every possible combination of relationships, leading to exponential complexity as $n$ grows. Lifted inference addresses this by exploiting symmetries—treating groups of individuals as interchangeable "types" rather than distinct entities. While previous methods for the two-variable fragment ($FO^2$) existed, they often relied on fragmented mathematical tools like Lagrange interpolation or Discrete Fourier Transforms. This research proposes a unified, purely combinatorial closed-form formula that handles $FO^2$ alongside existential quantifiers, cardinality constraints, and counting quantifiers.

Methodology: Lifted Interpretations and Combinatorial Counting

The cornerstone of this approach is the introduction of Lifted Interpretations. Unlike standard interpretations that assign truth values to every ground atom (e.g., "Is Alice friends with Bob?"), lifted interpretations assign truth values to "types" of atoms based on variables.

Lifted interpretation table showing assignments to types of atoms for variables $x$ and $y$.

By counting these lifted interpretations, the authors reconstruct and extend the closed-form formula for $FO^2$. The methodology involves three key technical steps:

  1. Combinatorial Cardinality: Using multinomial coefficients to count assignments of individuals to "1-types" and "2-types," avoiding calculus-based transforms.
  2. Principle of Inclusion-Exclusion: This principle is used to handle existential ($\exists$) and counting quantifiers ($\exists^{=m}$), reducing them to simpler universal formulas.
  3. Scott’s Normal Form: Complex formulas are reduced to a manageable structure that preserves model counting properties.
Table of counts $n_{ij}$ representing the number of pairs for different type combinations.

Key Insights: Beyond Symmetry

A significant contribution of this work is the expansion of weight functions. Most WFOMC methods assume "symmetric weight functions," where weights depend only on the predicate. This paper proves that their formula works for a strictly larger family of weight functions, enabling the modeling of count distributions (e.g., distributions where the probability of an odd number of "heads" in coin tosses is zero). Furthermore, by assuming distinct variables are assigned to distinct objects, the logic of equality ($x=y$) is handled in constant time relative to domain size.

Results: The "Grand Formula"

The research culminates in Theorem 3, providing a complete closed-form expression for $C^2$ (the two-variable fragment with counting). This formula is domain-liftable, meaning its computation time is polynomial relative to the number of individuals ($n$) in the domain.

The approach demonstrates significant expressive power, capturing "Complex Markov Logic Networks" using intuitive, real-valued combinatorial weights rather than complex-valued weights. The computational efficiency is maintained as the complexity depends on the domain size only through multinomial coefficients and simple multiplications.

Limitations and Future Work

While powerful, the formula is currently restricted to $FO^2$. Extending this combinatorial approach to $FO^3$ or beyond remains a major challenge, as those fragments are generally not domain-liftable. Additionally, while polynomial in domain size, the formula's scaling relative to the number of predicates and the "width" of counting quantifiers can be expensive. Future work will focus on practical software implementation and benchmarking against existing algorithmic solvers like Forclift to evaluate real-world performance.

Summary updated

Abstract

Weighted First-Order Model Counting (WFOMC) computes the weighted sum of the models of a first-order logic theory on a given finite domain. First-Order Logic theories that admit polynomial-time WFOMC w.r.t domain cardinality are called domain liftable. We introduce the concept of lifted interpretations as a tool for formulating closed-forms for WFOMC. Using lifted interpretations, we reconstruct the closed-form formula for polynomial-time FOMC in the universally quantified fragment of FO2, earlier proposed by Beame et al. We then expand this closed-form to incorporate cardinality constraints, existential quantifiers, and counting quantifiers (a.k.a C2) without losing domain-liftability. Finally, we show that the obtained closed-form motivates a natural definition of a family of weight functions strictly larger than symmetric weight functions.
BibTeX
@inproceedings{malhotra2022weighted,
  author = {Sagar Malhotra and Luciano Serafini},
  title = {{Weighted Model Counting in FO2 with Cardinality Constraints and Counting Quantifiers: A Closed Form Formula}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=u6n3pKquHgc},
}
Figure