can be an accurate approximation for this spanning subgraphs and the resulting approximation method would also provide bounds on the exact result.

## Acknowledgments

We acknowledge J. M. Mooij for providing the libDAI framework and A. Windsor for the planar graph functions of the boost graph library. We also thank V. Y. Chernyak, J. K. Johnson and N. Schraudolph for interesting discussions and A. Globerson for providing the Matlab sources of PDC. This research is part of the Interactive Collaborative Information Systems (ICIS) project, supported by the Dutch Ministry of Economic Affairs, grant BSIK03024. The work at LANL was carried out under the auspices of the National Nuclear Security Administration of the U.S. Department of Energy at Los Alamos National Laboratory under Contract No. DE-AC52-06NA25396.

## Appendix A: Converting A Factor Graph To A Forney Graph.

A probabilistic model is usually represented as a Bayesian Network or a Markov Random Field. Since bipartite factor graphs subsume both models, we show here how to convert a factor graph model defined in terms of binary variables to a more general Forney graph representation, for which the presented algorithm can be directly applied to.

On a bipartite factor graph GF = (VF , EF ) the set VF **is composed of a set of variable**
nodes I and a set of factor nodes J . Each variable node i ∈ I, i := {1, 2, . . . } **represents**
a variable which takes values σi = {±1}**. We label factor nodes using capital letters so**
that a = {A, B, . . . }, a ∈ J **denotes a factor node which has an associated function** fa(σa)
defined on a subset of variables ¯a ∈ I**. An (undirected) edge exists between two nodes** (a, i) ∈ EF if i ∈ a¯.

Given GF , a direct way to obtain an equivalent Forney graph G **is: first, to create a**
node δi ∈ V for each variable node i ∈ VF **, and second, to associate a new binary variable**
δia with values σδia = {±1} to edges (δi, a) ∈ E. Nodes δi ∈ V are *equivalent factor nodes* denoting the characteristic function: δi(σa) = 1 if σδia = σδib, ∀a, b ∈ ¯δi **and zero otherwise.**
Finally, factor nodes c ∈ VF correspond to the same factor nodes c in V **but defined in**
terms of the new variables δic, ∀i ∈ c¯.

Figure 10 shows an example of this transformation. Notice that, although we impose an direction in the edge labels, they remain undirected: (δi, a) = (a, δi), ∀δi, a ∈ V**. For** variables i ∈ VF **which only appear in two factors, such as variable 3, the corresponding** δ3 node is redundant and can be removed. The joint distribution of GF **is related to the joint**
distribution of G by:

1 Z fA(σ1)fB(σ2)fC(σ1, σ2)fD(σ1, σ3)fE(σ2, σ3) (7) ≡ 1 Z fA(σδ1A)fB(σδ2B)fC(σδ1C, σδ2C)fD(σδ1D, σδ3D)fE(σδ2E, σδ3E) fδ1 (σδ1A, σδ1C, σδ1D)fδ2 (σδ2B, σδ2C, σδ2E)fδ3 (σδ3D, σδ3E).
Once G **has been generated following the previous procedure it may be the case that the** nodes δi ∈ V have degree three or larger. This happens if a variable i **appears in more than**

$$\quad(7)$$
