While it is known that the stationary points of the Bethe approximation coincide with the fixed points of belief propagation, the relation between the Bethe approximation and the partition function is not well understood. It has been shown that for a few classes of factor graphs, e.g. permanents and attractive graphical models, the Bethe approximation always gives a lower bound to the partition function, which distinguishes them from the general case, where neither a lower bound, nor an upper bound holds universally.

We consider bipartite normal factor graphs and show that if the local constraints satisfy a certain "analytic" property, the Bethe approximation is a lower bound to the partition function. We arrive at this result by viewing factor graphs through the lens of polynomials. In this process, we reformulate the Bethe approximation as a capacity-like polynomial optimization problem. Our sufficient condition for the lower bound property to hold is inspired by recent developments in the theory of real stable polynomials.

Based on a joint work with Damian Straszak available at https://ieeexplore.ieee.org/document/8653402