Weighted First-Order Model Counting in the Two-Variable Fragment With Counting Quantifiers

In this paper we study weighted first-order model counting (WFOMC), which is an important problem (not only) because it can be used for probabilistic inference in most statistical relational learning models [Van den Broeck et al., 2011; Getoor and Taskar, 2007]. Probabilistic inference is in general intractable and the same holds for probabilistic inference in relational domains and therefore also for WFOMC. Lifted inference refers to a set of methods developed in the probabilistic inference literature which exploit structure and symmetries of the problems for making inference more tractable, e.g.