Lifting aims at improving the efficiency of probabilistic inference by exploiting symmetries in the model. Various methods for lifted probabilistic inference have been proposed, but our understanding of these methods and the relationships between them is still limited, compared to their propositional counterparts. The only existing theoretical characterization of lifting is a completeness result for weighted first-order model counting. This paper addresses the question whether the same completeness result holds for other lifted inference algorithms. We answer this question positively for lifted variable elimination (LVE). Our proof relies on introducing a novel inference operator for LVE.

@inproceedings{TaghipourStarAI13,
  author = "Taghipour, Nima and Fierens, Daan and Van den Broeck, Guy and Davis, Jesse and Blockeel, Hendrik",
  title = "On the completeness of lifted variable elimination",
  booktitle = "International Workshop on Statistical Relational AI (StarAI-13), Bellevue, Washington",
  month = Jul,
  year = "2013",
  url = "http://starai.cs.ucla.edu/papers/TaghipourStarAI13.pdf",
  keywords   = {workshop}
}