Uprooting and Rerooting Higher-Order Graphical Models
The idea of uprooting and rerooting graphical models was introduced specifically for binary pairwise models by Weller [19]  as a way to transform a model to any of a whole equivalence class of related models, such that inference on any one model yields inference results for all others. This is very helpful since inference, or relevant bounds, may be much easier to obtain or more accurate for some model in the class. Here we introduce methods to extend the approach to models with higher-order potentials and develop theoretical insights. In particular, we show that the triplet-consistent polytope TRI is unique in being 'universally rooted'. We demonstrate empirically that rerooting can significantly improve accuracy of methods of inference for higher-order models at negligible computational cost.
This paper presents a reparametrization method for inference in undirected graphical models. The method generalizes the uprooting and rerooting approach from binary pairwise graphical models to binary graphical models with factors of arbitrary arity. At the heart of the method is the observation that all non-unary potentials can be made symmetric, and once this has been done, the unary potentials can be changed to pairwise potentials to obtain a completely symmetric probability distribution, one where x and its complement have the exact same probability. This introduces one extra variable, making the inference problem harder. However, we can now "clamp" a different variable from the original distribution, and if we choose the right variable, approximate inference might perform better in the new model than in the original. Inference results in the reparametrized model easily translate to inference results in the original model.
The idea is supported by a number of theorems. I believe the results, but I did not study the proofs in the supplementary material. In addition to the main result, which is that inference results in the new model can be mapped back to inference results in the original model, the authors also discuss how the reparametrized problems relate to each other in the marginal polytope and how factors can be decomposed into sums of "even" factors -- basically, parity over k variables.
There are also some basic experiments on small, synthetic datasets which demonstrate that rerooting can yield better approximations in some cases.
Given that the negligible cost of reparametrization and mapping the results, this seems like a promising way to improve inference. There's no guarantee that the results will be better, of course -- in general, rerooting could lead to better or worse results. Furthermore, we can clamp variables without rerooting, at the cost of doubling the inference time for each clamped variable. (Just run inference twice, once with each value clamped.) If rerooting is only done once, then you're getting at best a factor-of-two speedup compared to clamping. A factor of two is a small constant, and I didn't see any discussion of how rerooting could be extended to yield better results. So the practical benefit from the current work may be marginal, but the ideas are interesting and could be worth developing further in future work.
Quality: I believe the quality is high, though as I mentioned, I have not studied the proofs in the supplementary material. The limitations are not discussed in detail, but this is typical for conference papers.
Clarity: The writing was fairly clear. Figure 2 has very small text and is uninterpretable in a black and white printout.
Originality: I believe this is original, but it's a natural evolution of previous work on rerooting. This is a meaningful increment, supported by theoretical results and token empirical results, but not transformative.
Significance: As stated earlier, it's not clear that these methods will yield any improvements on real-world inference tasks (yet). And if they do, it's at best a factor-of-two speedup. Thus, this work will mainly be relevant to people working in the area of graphical models and probabilistic inference. It's still significant to this group, though, since the results are interesting and worthy of further exploration.