Introduction
Generating random structures that satisfy specific logical constraints is a fundamental task in computer science, with applications ranging from software verification to statistical relational learning. In the context of first-order logic, this task is known as model sampling. However, as the number of objects (the domain size) increases, the state space of possible configurations grows exponentially, making traditional sampling methods computationally intractable.
This paper presents a breakthrough in the field: the first "domain-lifted" algorithm capable of exact sampling from the full two-variable fragment of first-order logic ($FO^2$). By utilizing a domain recursion strategy, the proposed Weighted Model Sampler (WMS) maintains efficiency even as systems scale, bypassing the limitations of traditional grounding-based approaches.
The Challenge of Scale in Logical Sampling
The core difficulty in sampling models of first-order logic lies in the "grounding" process. Traditional samplers convert logical rules into massive Boolean formulas. For a domain of size $n$, a simple binary relation can result in $n^2$ variables, leading to a search space that is $2^{n^2}$. This "propositional explosion" renders approximate samplers like UniGen ineffective for even moderately sized domains.
"Lifted" algorithms aim to solve this by exploiting symmetries. If objects are indistinguishable under the logic, they can be treated as a single unit. While lifted sampling was previously achieved for simpler fragments (such as Universal First-Order Logic, $UFO^2$), incorporating existential quantifiers ($\exists$) and counting constraints (e.g., "each node has exactly $k$ neighbors") remained a significant bottleneck.
Methodology: Domain Recursion and Lifted Sampling
The authors introduce a Weighted Model Sampler (WMS) designed for the two-variable fragment ($FO^2$) and its extension with counting constraints ($SC^2$). The innovation lies in Domain Recursion, which allows the algorithm to avoid the pitfalls of Skolemization—a process that often introduces negative weights or complex functions that break sampling probabilities.
The Sampling Pipeline
- Normalization: The input logic is converted into Scott Normal Form (SNF), a standard representation for $FO^2$.
- Domain Partitioning: The algorithm identifies "unary types"—sets of properties that elements can possess—and partitions the domain into cells based on these types.
- Recursive Reduction: Instead of solving the entire domain at once, the WMS picks a single object, samples its relationships to all other objects, and then "relaxes" the logical requirements for the remaining $n-1$ objects.
- Base Case Resolution: This recursion continues until the problem is reduced to a simpler fragment ($UFO^2$) that can be solved using existing lifted inference techniques.
By processing existential constraints one object at a time, the algorithm ensures that the running time is polynomial in the domain size $n$, a property known as domain-liftability.
Experimental Evaluation
The WMS was evaluated against UniGen, a state-of-the-art approximate sampler for Boolean formulas, across two primary domains:
- Combinatorial Structures: The researchers tested the sampler's ability to generate complex mathematical objects, including graphs without isolated vertices, $k$-regular graphs, and various functional permutations (with and without fixed points).
- Statistical Relational Models: The algorithm was applied to Markov Logic Networks (MLNs), specifically the "friends-smokers" social network model and employment models, which are standard benchmarks in the AI community.
Key Results
The experiments yielded three major findings:
- Superior Scalability: For tasks such as generating graphs without isolated vertices, the WMS handled domain sizes exceeding 75 objects with ease. In contrast, the propositional baseline (UniGen) timed out or struggled at much smaller scales.
- Statistical Exactness: Using the Kolmogorov-Smirnov statistical test, the authors verified that the samples produced by WMS are statistically indistinguishable from a true uniform distribution.
- Efficiency: In nearly all benchmarks, the WMS outperformed grounding-based samplers by several orders of magnitude as the domain size increased, proving that counting constraints do not fundamentally change the complexity class of the sampling problem when recursion is used.
Discussion and Future Directions
The development of a lifted sampler for $FO^2$ marks a significant milestone, yet it also highlights the boundaries of the field. The complexity of $FO^3$ (the three-variable fragment) is known to be #P-hard, suggesting that $FO^2$ may be the limit for efficient lifted sampling.
Future research may focus on extending this framework to handle negative weights, which are common in certain physical simulations, or incorporating more complex axioms such as linear orders and tree structures. Such advancements would enable the exact sampling of even more sophisticated data structures, like hierarchical taxonomies or temporal sequences.
Summary updated