This work proposes the structure of First Order dtrees (FO-dtrees) for inference in probabilistic logical models (PLMs), which is analogue to dtrees for propositional graphical models. The authors show how to determine from the structure if a lifted solution exists, how to read a lifted solution analogously to dtrees, and how the structure determines the complexity of inference.

The definition of FO-dtree is possible through the definition of a new type of node, DPG node - a triplet of logvars with same domain, a set of objects and a constraint. As in dtrees for propositional models, the leaves are factors. For lifting, the isomorphic is captured in the DPG nodes, and counting can be done in the same way as in lifted variable elimination. The proofs for determining if a model is liftable, how to read a solution and determine complexity - all seem analogue to dtrees.

The contribution of this work is by allowing lifted inference in PLMs, analyzing complexity and providing the infrastructure for approximate lifted inference. While this incrementally adding upon existing works, the exact formulation of the model seems as an important step.
The writing provides the required definitions and background.

This work provides an exact formulation of FO-dtrees, that compactly represent PLMs. They exploit symmetries and allow to use lifted inference as for dtrees for propositional graphical models. The contribution is the exact formulation for a model that mostly seems analogue to previous works.

The paper presents a lifted generalization of decomposition trees used
to analyze and effective specify a computation tree for the analysis
of lifted graphical models.

The paper is exceptionally well-written -- it uses a clean notation
and is full of examples to guide the reader's understanding. From a
quality perspective, this paper is among the top rank of papers I've
reviewed for NIPS.

The idea is also novel and seemingly worthy of publication --
first-order decision trees (FODTs) strike me as a useful internal data
structure for guiding the application of lifted inference. Yet, on
the other hand, it should be pointed out that FODTs don't permit
novel lifted computations, they only help one organize them and
analyze a notion of width which bounds the computational complexity
of evaluation w.r.t. an FODT.

In some sense the ability to do this computational analysis would have
been implicit in any prior implementation that had to recursively
break down a model and apply operations, namely the cited work of
Milch et al, but again this paper formalizes the recursive structure
and analysis in a way that I'm not aware has been done before.

It seems to me that while newcomers to lifted inference will find this
paper very informative (although perhaps still requiring a lot of
background reading), I would say that those who have implemented a
lifted inference system would not at all be surprised by what is being
presented here. Yet the latter group consists of a quite small group
of people.

In the end, my decision on this paper comes down to a few competing
issues:

(1) The usefulness of having this paper in the literature to present a
clean formalism for the implementation and analysis of lifted
inference.

(2) The computational analysis would have been implicit in previous
approaches (that certainly had to use a recursive decomposition of the
problem and for which computation at each step could be bounded).

(3) The paper does not enable any novel efficient inference, it simply
provides a clean way to implement and analyze existing inference
techniques.

A novel and clean formalism for the implementation and analysis of lifted inference, but lacking the ability to do novel lifted inference over prior work and a formalization of ideas implicit in previous work.

I weakly vote for acceptance simply because AI and ML have often made progress when notations have been introduced that allow the community to discuss and reason about complex systems, and this paper offers one such useful notational formalism.

The paper revolves around formally analyzing the complexity of exact lifted inference algorithms such as lifted variable elimination and lifted weighted model counting using special structures called lifted (or first-order) decomposition trees (or d-trees). D-trees, developed by Darwiche are a useful tool for formally analyzing the complexity of exact propositional inference schemes; the paper extends them to the first-order level. The paper also presents a notion of lifted width which is analogous to the notion of "width" in propositional inference.

Quality: Overall the paper is well-written and correct. The quality of writing is also excellent

Clairty: The paper is clear. However, since I'm an expert on this topic, I don't know if outsiders will understand it well unless they have some background on lifted inference.

Originality: I would give it a slightly lower originality score because such ideas have been mentioned before in a number of earlier papers on exact lifted inference. However, this is the first paper that gives it a thorough and formal treatment.

Significance: The paper presents several important, formal results which can prove to be quite useful to the lifted inference community. I would suggest a journal paper on this topic however since it may be hard for a non-expert to understand some subtleties.

Overall, this paper is quite useful, theoretically correct and will advance the state-of-the-art in lifted inference. It should be included in the program.

We thank the reviewers for their valuable and generally positive comments.

Reviewer 2 (Assigned_Reviewer_8) mentions that FO-dtrees are largely analogous to dtrees, making the work somewhat incremental.

We would like to emphasize that there are significant differences between FO-dtrees and their propositional counterparts. FO-dtrees require the ability to explicitly represent symmetries (i.e., either due to isomorphic decomposition or counting) that occur in the probabilistic logical models. As a consequence, the standard tree-width bound is not as precise as it could be. Thus, we propose a lifted notion of width that allows one to formally characterize the improvements over standard propositional inference due to liftability.

Reviewer 3 (Assigned_Reviewer_9) raises the following two points:
(1) the paper does not introduce novel lifted inference operators, and
(2) the computational analysis would have been implicit in previous approaches, and is thus not that surprising to those who have implemented a lifted inference system.

Despite the first publication on lifted inference being 10 years old, few theoretical results on this topic exist. The goal of this paper is to provide rigorous analysis and theoretical results that help put the state of the art in lifted inference on formal grounds. To the best of our knowledge, existing results either (1) take a local view and specify the complexity of individual operators in a specific algorithm or (2) show the complexity of solving a problem in a lifted way (without grounding the model) is polynomial in the domain size. In contrast, our work is the first that allows for a global, formal, detailed complexity analysis based on the structure of a model. We believe this is an important contribution by itself, which is orthogonal to the introduction of new operators.

While those few people who have implemented a lifted inference system may have come up with a complexity analysis of their algorithm, currently no such result explicitly exists in the literature. We are unaware of any structure-based complexity analysis that applies to PLMs in general, any notion similar to the lifted-width introduced in the paper, and any proposals based on decomposition trees (d-trees) or any other formal structure. Moreover, our proposed structure (FO-dtree) is not bound to a specific algorithm (or formalism) and allows for analyzing many exact lifted inference algorithms in a unified way. This should be valuable for understanding the relationship among them (note that most previous comparisons have been performed empirically on select models).

In our opinion, the fact that these results are implicit in previous approaches does not mean that they are obvious to everyone who has ever implemented a lifted inference system: at least to us, they were not, any time soon after implementing a lifted inference system.