Belief Propagation, Bethe Approximation and Polynomials
Damian Straszak, Nisheeth K. Vishnoi · IEEE Transactions on Information Theory · 2017
Factor graphs are important models for representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems, such as computing marginals and computing partition functions, arise when working with factor graphs. Bethe approximation is an optimization-based framework for computing partition functions and is known to be related to belief propagation, as the stationary points of the Bethe approximation coincide with the fixed points of belief propagation. However, the relation between the Bethe approximation and the true partition function is not well understood and has been recently a topic of study. It has been observed that for a few classes of factor graphs, Bethe approximation gives a lower bound on the partition function. This observation has been rigorously proved for permanents and for attractive models. Here we show that if the local constraints satisfy a certain geometric property, then Bethe approximation is a lower bound to the partition function. We arrive at our result by viewing factor graphs through the lens of polynomials. We reformulate the Bethe approximation as a polynomial optimization problem and state a sufficient condition for the lower bound to hold inspired by recent developments in the theory of real stable polynomials. We believe that this new way of viewing factor graphs might lead to a better understanding of the belief propagation algorithm and factor graphs in general.