

![0_image_0.png](0_image_0.png)

3 factor nodes on GF . It is easy to convert G to a graph were all δi **nodes have maximum**
degree three by introducing new auxiliary variables δi1
, δi2
, ... **and new equivalent nodes.**
For instance, if variable i ∈ VF appears in 4 factors **A, B, C, D**:
fδi

(σδiA, σδiB, σδiC, σδiD) ≡ fδi1
(σδiA, σδiB, σδi1
)fδi2
(σδi1
, σδiC, σδiD).

Notice that although the models are equivalent, the number of loops in G **may be larger**
than in GF . In the case that a factor in GF **involves more than three variables, as sketched in**
Chertkov et al. (2008), one could split the node of degree N **into auxiliary nodes of degree**
N −1 and compute Z∅ on the transformed model. Alternatively, one can reduce the **number**
of variables that enter a factor by clamping.

## References

F. Barahona. On the computational complexity of Ising spin glass models. *Journal of Physics A: Mathematical and General***, 15(10):3241–3253, 1982. URL**
http://stacks.iop.org/0305-4470/15/3241.

M. Chertkov and V. Y. Chernyak. Loop series for discrete statistical models on graphs.

Journal of Statistical Mechanics: Theory and Experiment**, 2006(06):P06009, 2006a.**
M. Chertkov and V. Y. Chernyak. Loop calculus helps to improve Belief Propagation and linear programming decodings of LDPC codes. In *invited talk at 44th Allerton Conference*, September 2006b.

M. Chertkov, V. Y. Chernyak, and R. Teodorescu. Belief propagation and loop series on planar graphs. *Journal of Statistical Mechanics: Theory and Experiment***, 2008(05):** P05003 (19pp), 2008. URL http://stacks.iop.org/1742-5468/2008/P05003.

G. Elidan, I. McGraw, and D. Koller. Residual belief propagation: Informed scheduling for asynchronous message passing. In *Proceedings of the 22nd Annual Conference on* Uncertainty in Artificial Intelligence (UAI-06)**, Boston, Massachussetts, July 2006. AUAI** Press.