Gauge-free cluster variational method by maximal messages and moment matching

We present an implementation of the cluster variational method (CVM) as a message passing algorithm. The kind of message passing algorithm used for CVM, usually named generalized belief propagation (GBP), is a generalization of the belief propagation algorithm in the same way that CVM is a generalization of the Bethe approximation for estimating the partition function. However, the connection between fixed points of GBP and the extremal points of the CVM free energy is usually not a one-to-one correspondence because of the existence of a gauge transformation involving the GBP messages. Our contribution is twofold. First, we propose a way of defining messages (fields) in a generic CVM approximation, such that messages arrive on a given region from all its ancestors, and not only from its direct parents, as in the standard parent-to-child GBP. We call this approach maximal messages. Second, we focus on the case of binary variables, reinterpreting the messages as fields enforcing the consistency between the moments of the local (marginal) probability distributions. We provide a precise rule to enforce all consistencies, avoiding any redundancy, that would otherwise lead to a gauge transformation on the messages. This moment matching method is gauge free, i.e., it guarantees that the resulting GBP is not gauge invariant. We apply our maximal messages and moment matching GBP to obtain an analytical expression for the critical temperature of the Ising model in general dimensions at the level of plaquette CVM. The values obtained outperform Bethe estimates, and are comparable with loop corrected belief propagation equations. The method allows for a straightforward generalization to disordered systems.

Figure 1

Example of regions surrounding the central spin $s_1$ in the cube approximation for the 3D square lattice model. Left: the 8 cubic regions $Q_1,...,Q_8$. Center: the 12 faces (plaquettes) $P_1,...,P_{12}$ shared by the maximal cubic regions. Right: the 6 vertices shared by the plaquettes and the central spin. The cube $Q_1$ is highlighted for later use.

Figure 2

Regions on whose beliefs the message $m_{Q_1\to s_1}\left(s_1\right)$ from the cubic region $Q_1$ to the central spin $s_1$ appear. On the leftmost diagram, $Q_1$ is still represented to help guiding the eye, but it does not belong to $\partial m_{Q_1\to s_1}$. The cube opposing $Q_1$, the three plaquettes and the three edges and $s_1$ itself, all intersect with $Q_1$ only at $s_1$, and therefore are in $\partial m_{Q_1\to s_1}$.

Figure 3

Consistency equation between link beliefs and spin beliefs. Mathematically, it corresponds to the first two equations in (15) for $d=2$.

Figure 4

Consistency equation between plaquette beliefs and link beliefs. Mathematically, it corresponds to the first two equations in (15) for $d=2$.

Figure 5

Estimated intensive thermodynamic quantities for the Ising 2D model using gauge-free message passing on the plaquette-CVM approximation. The vertical line marks the plaquette-CVM approximate critical temperature for this model.

Figure 6

Hasse diagram of the regions in the 3D cube approximation, for the 3D Ising model. Variables live in the nodes of a tridimensional cubic lattice. Maximal regions are the cubes (basic cell), and from them all intersections generate new regions, as prescribed by cluster variational method (see also Fig. 1). In this representation, all regions containing one central spin $s_1$ are depicted. Central spin $s_1=\alpha$ is surrounded by eight maximal cubic regions $Q_1,...,Q_8$. We represent the partially ordered set defined by the inclusion relations among the ancestors of $s_1$. Arrows point in the parent-to-child direction. Bottom figures are the eight cubes, next level are all the square plaquettes that intersect among these cubes, the third layer is made of the six links containing spin $s_1$. We consider $Q_1=r_0$ to be the region sending message to spin $s_1$. Shapes correspond to the position in the ancestry of $s_1$ with respect to the message $m_{Q_1\to s_1}$. All circular regions represent elements of $B_{r_0,\alpha }$, and therefore their intersection with $Q_1$ is exactly $s_1$ (represented also in Fig. 2, except for $Q_1$). Angular regions are those in ${\overline{B}}_{r_0,\alpha }^o$ (the absent part of Fig. 2, including $Q_1$).

Figure 7

Allowed (left) and not allowed (right) situations for the relation of $\partial m_{r_i\to r_0}$ with respect to the full ancestry of region $r_0$ (see Corollary t10). The message $m_{r_i\to r_0}$ appears in the belief equations of all the ancestors of region $r_0$ (light gray area), and $r_0$ itself, except for those who are ancestors of $r_i$ (dark gray area).

Figure 8

Moment matching Definition 2. Right: all the ancestry of $r_0$ sends messages to this region. Left: if a particular type of field, let us say $U_q^{r_i\to r_0}$, is present in the message of one the covers $r_i$ of $r_0$, then that field is present in all the messages from the ancestry of $r_i$, marked in gray in the figure, and is not present in the rest of the messages coming from other ancestors. This can be rationalized as if the region $r_i$ and its ancestors are using a set of Lagrange multipliers $U_q^{p\to r_0}$ to coordinate their correlation among the variables $q$.