easy, with no local fields, to very hard, with small local fields, and then decays again as external fields become larger.

The Z∅ **correction turns out to be competitive with other state of the art methods for**
approximate inference of the partition function. First of all, we showed that Z∅**is much**
more accurate than upper bounds based methods such as TRW or PDC. This illustrates that such methods come at the cost of less accurate approximations. We have also shown that for the case of grids with attractive interactions, the **lower bound provided by** Z∅is the most accurate.

Secondly, we found that Z∅ **performs much better than treeEP for weak and intermediate**
couplings and shows competitive results for strong interactions. Concerning CVM, we showed that using larger outer clusters does not necessarily lead to better approximations.

In general, the Z∅ correction presented better results than CVM for our choice **of regions.**
Finally, we have presented a comparison of Z∅ **with TLSBP, which is another algorithm**
for the BP-based loop series using the loop length as truncation parameter. On the one hand, the calculation of Z∅**involves a** *re-summation* **of many loop terms which in the case**
of TLSBP are summed individually. This consideration favors the Z∅ **approach. On the** other hand, Z∅**is restricted to the class of 2-regular loops whereas TLSBP also accounts**
for terms corresponding to more complex loop structures in which nodes can have degree larger than two. Overall, for planar graphs, we have shown evidence that the Z∅ **approach is**
better than TLSBP when the size of the graphs is not very small. We emphasize, however, that TLSBP can be applied to non-planar binary graphical models too.

Currently, the shortcoming of the presented approach is in its relatively costly implementation. However, since the bottleneck of the algorithm is the Pfaffian calculation and not the algorithm itself (used to obtain the extended graphs **and the associated matrices),** it is easy to devise more efficient methods than the one used here. Thus, one may substitute brute-force evaluation of the Pfaffians by a smarter one available for planar graphs. This reduces the cost from O(N3) to O(N3/2**) (Galluccio et al., 2000; Loh and Carlson, 2006).**
Besides, the Pfaffian of Bˆ **is binary, see Eq. (6), making it possible to improve using a**
bit-matrix representation (Schraudolph and Kamenetsky, 2008). Alternatively one could think of a strategy which does not require the Pfaffian of B**ˆ. All these technical issues are**
the focus of our continuing investigation.

In this manuscript we have focused on inference problems defined on planar graphs with symmetric pairwise interactions and, to make the problems difficult, we have introduced local field potentials. Notice however, that the algorithm can also be used to solve models with more complex interactions, i.e. more than pairwise as in the case of the Ising model
(see Chertkov et al., 2008, for a discussion of possible generalizations). This makes our approach more powerful than other approaches, namely, (Globerson and Jaakkola, 2007; Schraudolph and Kamenetsky, 2008), designed specifically for the pairwise interaction case.

Although planarity is a severe restriction, we emphasize that planar graphs appear in many contexts such as computer vision and image processing, **magnetic and optical recording, or network routing and logistics. It would also be interesting (and possible) to consider**
extensions of the algorithm developed in the manuscript for **approximate inference of some** class of non-planar graphs. Thus, following the approach of **Globerson and Jaakkola (2007),** one can think of other types of spanning subgraphs more general than "easy" planar graphs for which exact computation can be performed using perfect matching. The correction Z∅