  We consider the problem of approximate Bayesian inference in log-supermodular
models. These models encompass regular pairwise MRFs with binary variables, but
allow to capture high-order interactions, which are intractable for existing
approximate inference techniques such as belief propagation, mean field, and
variants. We show that a recently proposed variational approach to inference in
log-supermodular models -L-FIELD- reduces to the widely-studied minimum norm
problem for submodular minimization. This insight allows to leverage powerful
existing tools, and hence to solve the variational problem orders of magnitude
more efficiently than previously possible. We then provide another natural
interpretation of L-FIELD, demonstrating that it exactly minimizes a specific
type of R\'enyi divergence measure. This insight sheds light on the nature of
the variational approximations produced by L-FIELD. Furthermore, we show how to
perform parallel inference as message passing in a suitable factor graph at a
linear convergence rate, without having to sum up over all the configurations
of the factor. Finally, we apply our approach to a challenging image
segmentation task. Our experiments confirm scalability of our approach, high
quality of the marginals, and the benefit of incorporating higher-order
potentials.
