Bayesian belief propagation in graphical models has been recently shown to have very close ties to inference methods based in statis- tical physics. After Yedidia et al. demonstrated that belief prop- agation (cid:12)xed points correspond to extrema of the so-called Bethe free energy, Yuille derived a double loop algorithm that is guar- anteed to converge to a local minimum of the Bethe free energy. Yuille’s algorithm is based on a certain decomposition of the Bethe free energy and he mentions that other decompositions are possi- ble and may even be fruitful. In the present work, we begin with the Bethe free energy and show that it has a principled interpre- tation as pairwise mutual information minimization and marginal entropy maximization (MIME). Next, we construct a family of free energy functions from a spectrum of decompositions of the original Bethe free energy. For each free energy in this family, we develop a new algorithm that is guaranteed to converge to a local min- imum. Preliminary computer simulations are in agreement with this theoretical development.