Inference in Higher Order Undirected Graphical Models and Binary Polynomial Optimization.

This article addresses the problem of inference in higher order binary undirected graphical models (UGMs) by formulating it as a binary polynomial optimization problem and proposing several linear programming (LP) relaxations. It introduces and theoretically compares four LP relaxations—standard, flower, running intersection, and clique relaxations—and further develops a multiclique relaxation incorporating lifted odd-cycle inequalities to strengthen the approach for complex clique structures. The effectiveness of these relaxations is demonstrated through computational studies in two key applications: image restoration, including synthetic images and QR code recovery, and decoding of low-density parity check (LDPC) error-correcting codes. Results indicate that the clique LP often yields exact solutions efficiently in image restoration, while the multiclique LP provides the strongest bounds for decoding, though improvements over existing methods are modest and computational costs vary across relaxations.