The Bethe Partition Function of Log-supermodular Graphical Models

Introduction

Graphical models have proven to be a useful tool for performing approximate inference in a wide variety of application areas including computer vision, combinatorial optimization, statistical physics, and wireless networking. Computing the partition function of a given graphical model, a typical inference problem, is an NP-hard problem in general. Because of this, the inference problem is often replaced by a variational approximation that is, hopefully, easier to solve. The Bethe approximation, one such standard approximation, is of great interest both because of its practical performance and because of its relationship to the belief propagation (BP) algorithm: stationary points of the Bethe free energy function correspond to fixed points of belief propagation . However, the Bethe partition function is only an approximation to the true partition function and need not provide an upper or lower bound.

In certain special cases, the Bethe approximation is conjectured to provide a bound on the true partition function. One such example is the class of attractive pairwise graphical models: models in which the interaction between any two neighboring variables places a greater weight on assignments in which the two variables agree. Many applications in computer vision and statistical physics can be expressed as attractive pairwise graphical models (e.g., the ferromagnetic Ising model). Sudderth, Wainwright, and Willsky used a loop series expansion of Chertkov and Chernyak in order to study the fixed points of BP over attractive graphical models. They provided conditions on the fixed points of BP under which the stationary points of the Bethe free energy function corresponding to these fixed points is a lower bound on the true partition function. Empirically, they observed that, even when their conditions were not satisfied, the Bethe partition function appeared to lower bound the true partition function, and they conjectured that this is always the case for attractive pairwise binary graphical models.

Recent work on the relationship between the Bethe partition function and the graph covers of a given graphical model has suggested a new approach to resolving this conjecture. Vontobel demonstrated that the Bethe partition function can be precisely characterized by the average of the true partition functions corresponding to covers of the base graphical model. The primary contribution of the present work is to show that, for graphical models with log-supermodular potentials, the partition function associated with any graph cover of the base graph, appropriately normalized, must lower bound the true partition function. As pairwise binary graphical models are log-supermodular if and only if they are attractive, combining our result with the observations of resolves the conjecture of .

The key element in our proof, and the second contribution of this work, is a new variant of the “four functions” theorem that is specific to log-supermodular functions. We state and prove this variant in Section 3.1, and in Section 4.1, we use it to resolve the conjecture. As a final contribution, we demonstrate that our variant of the “four functions” theorem has applications beyond log-supermodular functions: we use it to show that the Bethe partition function can also provide a lower bound on the number of independent sets in a bipartite graph.

Undirected Graphical Models

where $x_{\alpha}$ is the subvector of the vector $x$ indexed by the set $\alpha$.

We will express the hypergraph $G$ as a bipartite graph that consists of a variable node for each $i\in V$, a factor node for each $\alpha\in\mathcal{A}$, and an edge joining the factor node corresponding to $\alpha$ to the variable node representing $i$ if $i\in\alpha$. This is typically referred to as the factor graph representation of $G$.

Every function that admits a log-supermodular factorization is necessarily log-supermodular as products of log-supermodular functions are easily seen to be log-supermodular, but the converse may not be true outside of special cases. If $|\alpha|\leq 2$ for each $\alpha\in\mathcal{A}$, then we call the factorization pairwise. For any pairwise factorization, $f$ is log-supermodular if and only if $\psi_{ij}$ is log-supermodular for each $i$ and $j$.

Pairwise graphical models such that $\psi_{\alpha}(x_{\alpha})$ is log-supermodular for all $\alpha\in\mathcal{A}$ are referred to as attractive graphical models. A generalization of attractive interactions to the non-pairwise case is presented in : for all $\alpha\in\mathcal{A}$, $\psi_{\alpha}$, when appropriately normalized, has non-negative central moments.

Graph covers have played an important role in our understanding graphical models .

A graph $H$ covers a graph $G=(V,E)$ if there exists a graph homomorphism $h:H\rightarrow G$ such that for all vertices $v\in G$ and all $w\in h^{-1}(v)$, $h$ maps the neighborhood $\partial w$ of $w$ in $H$ bijectively to the neighborhood $\partial v$ of $v$ in $G$. If $h(w)=v$, then we say that $w\in H$ is a copy of $v\in G$. Further, $H$ is a $k$-cover of $G$ if every vertex of $G$ has exactly $k$ copies in $H$.

Roughly, if a graph $H$ covers a graph $G$, then $H$ looks locally the same as $G$. For an example of a graph cover, see Figure 1.

Notice that if $f^{G}$ admits a log-supermodular factorization over $G$ and $H$ is a $k$-cover of $G$, then $f^{H}$ admits a log-supermodular factorization over $H$.

2 Bethe Approximations

for $\tau$ in the local marginal polytope,

We resolve this conjecture in the affirmative, and show that it continues to hold for a larger class of log-supermodular functions. Our results are based, primarily, on two observations: a variant of the “four functions” theorem and the following, recent, theorem of Vontobel :

where $\mathcal{C}^{k}(G)$ is the set of all $k$-covers of $G$.

The “Four Functions” Theorem and Related Results

The “four functions” theorem is a general result concerning nonnegative functions over distributive lattices. Many correlation inequalities, such as the FKG inequality, can be seen as special cases of this theorem .

The following lemma is a direct consequence of the four functions theorem:

The four functions theorem can be generalized to more than four functions, and a special case of the more general “2k functions” theorem is as follows :

A natural generalization of Theorem 3.3 would be to replace the product of functions on the left-hand side of Equation 1 with an arbitrary function over $x^{1},\ldots,x^{k}$. While the conclusion of the theorem may not continue to hold for arbitrary choices of such a function, we will show that we can replace this product with an arbitrary log-supermodular function while preserving the conclusion of the theorem. The key property of log-supermodular functions that makes this possible is the following lemma:

This follows directly from the log-supermodularity of $g$. ∎

The proof of our variant of the “$2k$ functions theorem” uses the properties of weak majorizations:

For the purposes of this paper, we will only need the following result concerning weak majorizations:

We now state and prove our variant of the $2k$ functions theorem in two pieces. First, we consider the case where $n=1$:

for all $c\in\{0,\ldots,k\}$ and $M\leq{k\choose c}$, then we must have that $\log G\prec_{w}\log F$.

Now, fix $c\in\{0,\ldots,k\}$, $T\in\{1,\ldots,{k\choose c}\}$, and let $V^{c}=\{v\in\{0,1\}^{k}\hskip 2.84544pt|\hskip 2.84544ptv_{1}+\ldots+v_{k}=c\}$. Suppose $v^{1},\ldots,v^{T}\in V^{c}$ are $T$ distinct vectors. By Lemma 3.4, we must have

where $w^{t}_{j}=z^{j}(z^{t}(v^{1},\ldots,v^{T})_{1},\ldots,z^{t}(v^{1},\ldots,v^{T})_{k})$ for each $j\in\{1,\ldots,k\}$. Given any such $v^{1},\ldots,v^{T}\in V^{c}$, we will show how to construct distinct vectors $\overline{v}^{1},\ldots,\overline{v}^{T}\in V^{c}$ such that $\prod_{t=1}^{T}f(w^{t})\leq\prod_{t=1}^{T}f(\overline{v}^{t})$. Consequently, we will have

As our construction will work for any choice of distinct vectors $v^{1},\ldots,v^{T}\in V^{c}$, it will work, in particular, for the $T$ distinct vectors in $V^{c}$ that maximize $\prod_{t=1}^{T}g(v^{t})$, and the lemma will then follow as a consequence of our previous arguments.

where the equality follows from the definition of $f$ as a product of the $f_{i}$. In addition, the vector $z^{t}(v^{1},\ldots,v^{T})$ is simply a permuted version of the vector $z^{t}(\overline{v}^{1},\ldots,\overline{v}^{T})$ which means that their $j^{th}$ largest elements must agree:

and the lemma follows as a consequence . ∎

Notice that $g^{\prime}$ is log-supermodular because it is the marginal of a log-supermodular function (see Lemma 3.2). If we can show that

We can easily check that $\overline{g}(s^{1},\ldots,s^{k})$ is log-supermodular and that $\overline{g}(s^{1},\ldots,s^{k})\leq\prod_{i=1}^{k}\overline{f}_{i}(z^{i}(s^{1},\ldots,s^{k}))$ for all $s^{1},\ldots,s^{k}\in\{0,1\}$. Hence, by Lemma 3.7,

which completes the proof of the theorem. ∎

Graph Covers and the Partition Function

In this section, we show how to apply Theorem 3.8 in order to resolve Conjecture 2.4. In addition, we show that the theorem can be applied, more generally, to yield similar results for a class of functions that can be converted into a log-supermodular functions by a change of variables.

The following theorem follows easily from Theorem 3.8:

Let $H$ be a $k$-cover of $G$. Divide the vertices of $H$ into $k$ sets $S_{1},\ldots,S_{k}$ such that each set contains exactly one copy of each vertex $i\in V$. Let the assignments to the variables in the set $S_{i}$ be denoted by the vector $x^{i}$.

For each $\alpha\in\mathcal{A}$, let $y^{i}_{\alpha}$ denote the assignment to the $i^{th}$ copy of $\alpha$ by the elements of $x^{1},\ldots,x^{k}$. By Lemma 3.4,

From this, we can conclude that $f^{H}(x^{1},\ldots,x^{k})\leq\prod_{i=1}^{k}f^{G}(z^{i}(x^{1},\ldots,x^{k}))$. Now, by Theorem 3.8,

This theorem settles the conjecture of for any log-supermodular function that admits a pairwise binary factorization. Indeed, the above theorem solves the problem for a larger class of log-supermodular graphical models:

This follows directly from Theorem 4.1 and Theorem 2.5. ∎

where $\mathcal{C}^{k}(G)$ is the set of all $k$-covers of $G$.

2 Beyond Log-supermodularity

While Theorem 4.1 is a statement only about log-supermodular functions, we can use Theorem 3.8 to infer similar results even when the function under consideration is not log-supermodular. As an example of such an application, we consider the problem of counting the number of independent sets in a given graph, $G=(V,E)$. An independent set, $I\subseteq V$, in $G$ is a subset of the vertices such that no two adjacent vertices are in $I$. We define the following function:

which is equal to one if the nonzero $x_{i}$’s define an independent set and zero otherwise. As every potential function depends on at most two variables, $I^{G}$ factorizes over the graph $G=(V,E)$. Notice that $f^{G}$ is log-submodular, not log-supermodular.

In this section, we will focus on bipartite graphs: $G=(V,E)$ is bipartite if we can partition the vertex set into two sets $A\subseteq V$ and $B=V\setminus A$ such that $A$ and $B$ are independent sets. Examples of bipartite graphs include single cycles, trees, and grid graphs. We will denote bipartite graphs as $G=(A,B,E)$.

For any bipartite graph $G=(A,B,E)$, $I^{G}$ can be converted into a log-supermodular graphical model by a simple change of variables. Define $y_{a}=x_{a}$ for all $a\in A$ and $y_{b}=1-x_{b}$ for all $b\in B$. We then have

Similar observations can, for example, be used to show that the Bethe partition function provides a lower bound on the true partition function for other problems that factor over pairwise bipartite graphical models (e.g., the antiferromagnetic Ising model on a grid, counting the number of vertex covers of a bipartite graph, counting the number of satisfying assignments of a monotone 2-SAT instance whose corresponding graphical structure is bipartite).

Conclusions

While the results presented above were discussed in the case that the temperature parameter, $T$, was equal to one, they easily extend to any $T\geq 0$ (as exponentiation preserves log-supermodularity in this case). Hence, all of the bounds discussed above can be extended to the problem of maximizing a log-supermodular function. In particular, the inequality in Theorem 4.1 suggests that the maximizing assignment on any graph cover must correspond to a lift of a maximizing assignment on the base graph.

This work also suggests a number of directions for future research. While the above work provides lower bounds on the partition function, similar ideas may be able to provide upper bounds as well. We note that related work on the Bethe approximation for permanents has already begun to explore these possibilities . Similarly, an analog of Theorem 3.8 for log-submodular functions may also be useful in the pursuit of upper bounds. The primary difficulty is that marginal distributions of log-submodular functions are not necessarily log-submodular, but perhaps upper bounds can be obtained when restricting to families of log-submodular functions all of whose marginals are also log-submodular.

Acknowledgments

The author would like to thank Nicolas Macris, for many useful discussions about the ferromagnetic Ising model and correlation inequalities, and Pascal Vontobel, for his comments and suggestions during the preparation of this work.

References