Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes tractable strategies for upper bounding the value of constrained MPE problems. Two strategies are developed based on Lagrangian relaxation. One is to completely eliminate the constraint, converting the problem to a straight MPE problem. The second one involves the strategic application of dual decomposition to convert the problem instance to one of a multiple choice knapsack problem. The approaches are evaluated on datasets from the UAI inference challenge as well as adversarial input modification tasks.
main_review: This is a very well written paper that addresses an reasonably important tasks through non-trivial means. The ideas are clearly communicated and easy to follow. Regarding novelty --- I found the MCKP bound to be rather clever and this thankfully translates to interesting computational results as well. 

I have a few points of criticism. 
First, the final paragraph on page 4 (lines 170 - 174) imply somehow that LP-based bounds are unworthy of consideration because of the weak polynomial complexity of linear programming. I find this point extremely contrived given that the first bound simply assumes that the unconstrained MPE problem will be tractable or otherwise the recourse are approximation algorithms with running time proportional to 2^i  If one is comfortable accepting MPE tractability, accepting LP tractability should be a much easier pill to swallow. This is actually not a minor point, since the domination of the LP bound by the first Lagrangian bound holds only if the MPE is solved exactly. Otherwise, no straightforward claims can be made. The LP bound should not only not be discarded so lightly but is probably the most natural baseline for the evaluations of this paper. 

Second, one thing that is actually confusing on first read is the way that the way that the algorithms under evaluation are introduced on page 7, section 4. At first I thought that MG/MM/JG are existing bounding approaches, since they were discussed in the prior art section  (which might leave a confusing impression as the reader might have forgotten exactly what the situation is at that point), then I wondered where are the evaluations of the first bound, so it took some back and forth until things clicked. I think it's worth calling this out explicitly in a single sentence that MG/MM/JG are evaluations of the bound in eq. 3.

Finally, I think it's worth considering to move all the tabular data to the appendix and instead having plots to illustrate the specific points that are made in section 4. I think going through all these tables multiple times makes for a rather tedious reading experience, yet there are rather interesting observations here that shouldn't be missed, so having a more condensed representation might make sense. 

Overall, I would say this is a solid paper. It can be further strengthened by the addition of an LP baseline. The other issues are cosmetic.


limitations_and_societal_impact: No concerns.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors present two novel approaches for upper bounding the constrained most probable explanation (CMPE) task in graphical models.  The CMPE is a variation of the MPE or MAP estimation problem in discrete graphical models, where one must find the most likely configuration of the graphical model subject to a constraint on the chosen configuration.  The authors make use of lagrangian relaxation to introduce two new methods.  One works by relaxing the CMPE to an MPE, which can be solved exactly or approximately, using the solution to compute the upper bound, tightening the bound via subgradient descent and repeating.  The other works in a similar fashion by relaxing the CMPE to a multi choice knapsack problem.  

As far as I can tell, these contributions are both novel and significant. 
main_review: Overall, I thought this was a very well written paper.  The problem was tightly described, the contributions (and limitations) were clearly presented, the technical results were clear and concise and the results conveyed the efficacy and limitations of the proposed approaches. And to the best of my knowledge, these appear to be the first generally tractable methods to upper bound the CMPE problem.

A few comments/questions:
-Is the assumption that the log linear models F (MPE) and G (constraint) have the same primal graph limiting? And does it obscure the real trade-off between the two methods?  If the graphs weren't the same, would you choose the MCKP approximation when the model G has higher treewidth and the MPE-based approximation when F has higher treewidth?   
-It was not obvious to me that \sum_{g \in G} g(x) <= q in the MPE based approximation when the MPE model is not tractable and must be approximated. Can you provide some additional color on this claim.
-Did you run into any convergence issues in the case where the MPE approximation was not tractable?  
-What is the relationship between i and k on lines 162 and 163, or is that a typo?
-Line 227 I don't think you mean "duplicating each variable two times". 

limitations_and_societal_impact: This doesn't seem relevant.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents two novel schemes for upper bounding the CMPE problem. The first relaxes the global constraint via Lagrangian relaxation and the second reduces the CMPE to an MCKP problem. 
main_review: The paper is well-written and contributions are solid. I personally like the paper but I have several minor concerns:

(1) How tight are the two new bounds? It is unclear to me how much these two new bounds are better than the naive upper bound obtained by removing the constraint in Eq (`1). 

(2) The paper claims the usages of the new upper bounds are  (1) generating heuristic
near-optimal solutions; and (2) pruning the search space of branch and bound methods and thus improving their efficiency. However, there are no experiments provided about these two usage cases in the paper. Therefore, I am not sure how much these two new bounds can help in practices. 

(3) The time and space complexities of the second scheme seem rather high, it looks to me that it will significantly hinder the use of such scheme in the usage of pruning search space in a complete search engine like branch and bound.
limitations_and_societal_impact: See my comments in "Main review"
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper considers the constrained most probable explanation task in probabilistic graphical models and develops new upper bounding schemes for it. Unlike MPE, the CMPE task is NP-hard even for tree-shaped graphical models and therefore finding good upper bounds for it is definitely called for. Specifically, the idea is to use the Lagrangian relaxation to generate either a standard MPE problem or a knapsack problem. Experimental results of several CMPE benchmark domains demonstrate the effectiveness of the proposed upper bounding schemes.

main_review: The paper is well written and organised. The quality of the presentation is overall very good. The two proposed upper bounding schemes are presented very clearly and examples provided help to get a better understanding. In the experimental section it may be worthwhile to include some plots of the computed upper bounds (as functions of the mini-bucket I-bounds for example).

Lagrangian relaxation is a well known technique that is widely used in operations research to deal efficiently with complicated constraints. Therefore, applying it to the CMPE task is quite natural. Although the extension is fairly straightforward it appears to be the first time it is done in this context. The experimental results demonstrate that the technique is quite effective in practice.

One thing the is perhaps missing is a discussion on the usefulness of these upper bounds. Although it is mentioned in the introduction that in principle they can be used to guide a heuristic search algorithm, it would be interesting to see how one would do it in practice (ie, precompile the heuristics in some way, generate them dynamically at each node in the search space, etc.).

Minor comment:
- In section 3.2 you also use a parameter "i" to bound the number of items in a partition. It's not exactly equivalent to the mini-bucket I-bound, so may be use a different letter for the parameter.

limitations_and_societal_impact: The limitations of the proposed method are well addressed and there's no potential societal impact.
review_title: null

Meta-review: The authors present two approaches for bounding "constrained" most probable explanation (CMPE) tasks in graphical models, in which we seek an MPE solution to one model, constrained to a subset of configurations by another model.  Both methods are simple (in a good way), relaxing the CMPE to an unconstrained MPE problem, or to a multi-choice knapsack problem, then using Lagrangian optimization to tighten the resulting bounds.  Reviewers were unanimously positive, highlighting the novelty of the work as a strength.  Several reviewers did bring up points that should be addressed in a final version, however, including comparison to LP-based techniques, and some issues with the presentation (see individual reviews for details).
Decision: Accept (Poster)