The idea of uprooting and rerooting graphical models was introduced specifically for binary pairwise models by Weller (2016) 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. 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 of uprooting and rerooting graphical models was introduced specifically for binary pairwise models by Weller (2016) 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.