Lifted Weighted Mini-Bucket
Many graphical models, such as Markov Logic Networks (MLNs) with evidence, possess highly symmetric substructures but no exact symmetries. Unfortunately, there are few principled methods that exploit these symmetric substructures to perform efficient approximate inference. In this paper, we present a lifted variant of the Weighted Mini-Bucket elimination algorithm which provides a principled way to (i) exploit the highly symmetric substructure of MLN models, and (ii) incorporate high-order inference terms which are necessary for high quality approximate inference. Our method has significant control over the accuracy-time trade-off of the approximation, allowing us to generate any-time approximations. Experimental results demonstrate the utility of this class of approximations, especially in models with strong repulsive potentials.
The paper presents a lifted version of the weighted mini-bucket elimination algorithm.   Exploiting symmetries within probabilistic inference is important. In particular, with respect to the present paper, the standard approach for inference in probabilistic formalisms with first-order constructs is lifted variable elimination (LVE) for single queries. To handle multiple queries efficiently, the lifted junction tree algorithm (LJT) employs a first-order cluster representation of a model and LVE as a subroutine. The present paper extends this family of approach towards a lifted variant of  weighted mini-bucket. That is, it shows how to employ its tighter bounds for probabilistic inference. This is interesting.  And yes, the paper mentions major related work. However, it doe not discuss some important related work at a sufficient level of details. Consider e.g. [5, 13] but also   Prithviraj Sen, Amol Deshpande, Lise Getoor: Bisimulation-based Approximate Lifted Inference. UAI 2009: 496-505  In terms of the bound used, as it is closely related to counting numbers, the authors should clarify the connection to [13] and related approaches in more details.  This line of research has also shown that symmetries can be exploited for concave  energies and for variational optimization of them. This discussion is missing.  Also, the authors should mention  Seyed Mehran Kazemi, David Poole: Knowledge Compilation for Lifted Probabilistic Inference: Compiling to a Low-Level Language.  KR 2016: 561-564   David B. Smith, Parag Singla, Vibhav Gogate: Lifted Region-Based Belief Propagation.  CoRR abs/1606.09637 (2016)   As far as I see it, the underlying theory presented, next to the join operations, are very similar if not identical. The authors should develop where (on the underlying algebraic level) the differences are. As far as I see it, the present paper introduces a novel approach to compute counting numbers, which could then be used e.g. in Theorem 9 of [13].  This is also related to the asymmetric case presented. The sequential case is interesting but not discuss in detail. The unary evidence case is very much related to the domain graph presented by Bui et al. (see above) as well as by   Martin Mladenov, Kristian Kersting, Amir Globerson: Efficient Lifting of MAP LP Relaxations Using k-Locality.  AISTATS 2014: 623-632  Overall, however, the contribution and also the particular combination appears to be very interesting. The experimental evaluation falls a little bit too short as no real world data has been considered. Would be great to add something evaluations here.   Nevertheless, overall, the paper makes a nice progress for lifted inference. The main downside is the weak discussion of related work, which makes it hard to see the novel contributions. This is also reflected in the fact that now summary of the results are presented. The experimental evaluation is too short for the claims raised in the intro, but still kind of fine. I am confident that this will work on other models, too.   Furthermore, there are forthcoming IJCAI 2018 papers such as   Tanya Braun, Ralf Möller Parameterised Queries and Lifted Query Answering IJCAI 2018  They introduce the idea of parameterised queries as a means to avoid groundings,  applying the lifting idea to queries. Parameterised queries enable LVE and LJT  to compute answers faster, while compactly representing queries and answers. Would be great if the authors can mention them, although the work was indeed done independently.