Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting

Eric Gribkoff, Guy Van Den Broeck, Dan Suciu UW
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:805-814, 2014.

Abstract

In this paper we study lifted inference for the Weighted First-Order Model Counting prob- lem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic (FOL); it has applications in Statisti- cal Relational Learning (SRL) and Probabilis- tic Databases (PDB). We present several results. First, we describe a lifted inference algorithm that generalizes prior approaches in SRL and PDB. Second, we provide a novel dichotomy result for a non-trivial fragment of FO CNF sentences, showing that for each sentence the WFOMC problem is either in PTIME or #P- hard in the size of the input domain; we prove that, in the first case our algorithm solves the WFOMC problem in PTIME, and in the second case it fails. Third, we present several proper- ties of the algorithm. Finally, we discuss limi- tations of lifted inference for symmetric proba- bilistic databases (where the weights of ground literals depend only on the relation name, and not on the constants of the domain), and prove the impossibility of a dichotomy result for the complexity of probabilistic inference for the en- tire language FOL.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-gribkoff14a, title = {Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting}, author = {Gribkoff, Eric and Broeck, Guy Van Den and UW, Dan Suciu}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {805--814}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/gribkoff14a/gribkoff14a.pdf}, url = {https://proceedings.mlr.press/r12/gribkoff14a.html}, abstract = {In this paper we study lifted inference for the Weighted First-Order Model Counting prob- lem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic (FOL); it has applications in Statisti- cal Relational Learning (SRL) and Probabilis- tic Databases (PDB). We present several results. First, we describe a lifted inference algorithm that generalizes prior approaches in SRL and PDB. Second, we provide a novel dichotomy result for a non-trivial fragment of FO CNF sentences, showing that for each sentence the WFOMC problem is either in PTIME or #P- hard in the size of the input domain; we prove that, in the first case our algorithm solves the WFOMC problem in PTIME, and in the second case it fails. Third, we present several proper- ties of the algorithm. Finally, we discuss limi- tations of lifted inference for symmetric proba- bilistic databases (where the weights of ground literals depend only on the relation name, and not on the constants of the domain), and prove the impossibility of a dichotomy result for the complexity of probabilistic inference for the en- tire language FOL.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting %A Eric Gribkoff %A Guy Van Den Broeck %A Dan Suciu UW %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-gribkoff14a %I PMLR %P 805--814 %U https://proceedings.mlr.press/r12/gribkoff14a.html %V R12 %X In this paper we study lifted inference for the Weighted First-Order Model Counting prob- lem (WFOMC), which counts the assignments that satisfy a given sentence in first-order logic (FOL); it has applications in Statisti- cal Relational Learning (SRL) and Probabilis- tic Databases (PDB). We present several results. First, we describe a lifted inference algorithm that generalizes prior approaches in SRL and PDB. Second, we provide a novel dichotomy result for a non-trivial fragment of FO CNF sentences, showing that for each sentence the WFOMC problem is either in PTIME or #P- hard in the size of the input domain; we prove that, in the first case our algorithm solves the WFOMC problem in PTIME, and in the second case it fails. Third, we present several proper- ties of the algorithm. Finally, we discuss limi- tations of lifted inference for symmetric proba- bilistic databases (where the weights of ground literals depend only on the relation name, and not on the constants of the domain), and prove the impossibility of a dichotomy result for the complexity of probabilistic inference for the en- tire language FOL. %Z Reissued by PMLR on 04 October 2026.
APA
Gribkoff, E., Broeck, G.V.D. & UW, D.S.. (2014). Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:805-814 Available from https://proceedings.mlr.press/r12/gribkoff14a.html. Reissued by PMLR on 04 October 2026.

Related Material