Lifted variable elimination with arbitrary constraints

Lifted inference methods exploit regularities in the structure of probabilistic models: they perform inference once for an entire group of interchangeable objects, instead of for each object in the group. Existing lifted inference methods use a specific constraint language for defining the groups. In this work we generalize lifted variable elimination to work with arbitrary constraints. We empirically demonstrate that this improves inference efficiency by orders of magnitude, allowing exact inference on problems for which until now only approximate inference was feasible.