variables. One may use either the Boltzmann machine representation xv ∈ {0,1}, or that of the Ising model xv ∈
{−1,+1}. These models can be represented as in (1) with

$$f(x;\theta)=\sum_{E\in\mathcal{G}}\theta_{E}\phi_{E}(x_{E}),\ \ \phi_{E}(x_{E})=\prod_{v\in E}x_{v}\tag{2}$$

This defines an *exponential family* [4] of probability distributions based on model features φ and parameterized by θ. Φ(θ) , logZ(θ) is the *log-partition function* and has the *moment-generating property*:
∂Φ(θ)
∂θE= Eθ {φE(x)} , ηE.

Here, η are the *moments* of the distribution, which serve both as an alternate parameterization of the exponential family and, in graphical models, to specify the marginal distributions on cliques of the model. Inference in discrete models using junction tree methods, either to compute the mode or the marginals, is generally linear in the number of variables n but grows exponentially in the *width* of the graph [2], which is determined by the size of the maximal cliques in a junction tree representation of the graph. Hence, exact inference is only tractable for *thin* graphs, that is, where one can build an equivalent junction tree with small cliques.

Gaussian Models. We also consider Gaussian graphical models [5], [6] represented in *information form*:

$$p(x)=\exp\{-{\frac{1}{2}}x^{T}J x+h^{T}x-\Phi(h,J)\}$$
Tx−Φ(h,J)} (3)
where J is the *information matrix*, h a potential vector and Φ(h,J) = 12
{h TJ
−1h−logdetJ +nlog2π}. This corresponds to the standard form of the Gaussian model specified by the covariance matrix P = J
−1and mean vector ˆx = J
−1h. This translates into an exponential family where we identify (h,J)
with the parameters θ and (xˆ,P) with the moments η. In general, the complexity of inference in Gaussian models is O(n 3). The fill pattern of J determines the Markov structure of the Gaussian model: (i, j) ∈ G if Ji, j 6= 0. Using more efficient recursive inference methods that exploit sparsity, such as junction trees or sparse Gaussian elimination, the complexity is linear in n but cubic in the width of the graph, which is still impractical for many large-scale estimation problems.

## Iii. Discrete Lagrangian Relaxation

To begin with, consider the problem of maximizing the following objective function, defined over a hypergraph G ⊂
2 V based on a vertex set V = {1,...,n} corresponding to discrete variables x = (x1,...,xn).

$$f(x)=\sum_{E\in{\mathcal{G}}}f_{E}(x_{E})$$
$$\left(4\right)$$
fE (xE) (4)
For instance, this may be defined as f(x) = hθ,φ(x)i in an exponential family graphical model, such that each term corresponds to a feature fE (xE) = θEφE(xE ). Then, we seek x
∗to maximize f(x) to obtain the MAP estimate of (1).

An Illustrative Example. To briefly convey the basic concept, we consider a simple pairwise model defined on a 3node cycle G represented in Fig. 1. Here, the augmented graph G
′is a 4-node chain, where node 4 is a replica of node 1. We copy all the potentials on the nodes and edges

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

Fig. 1. A simple illustrative example of Lagrangian relaxation.

from G to G
′. For the replicated variables, x
′1 and x
′4
, we split f1 between f
′1 and f
′4 such that f1(y) = f
′1
(y) + f
′4
(y)
for y ∈ {0,1}. Now the problem maxx f(x) is equivalent to maximizing f
′(x
′) subject to the constraint x
′1 = x
′4
. To solve the latter we relax the constraint using Lagrange multipliers:
L(x
′,λ) = f
′(x
′)+λ(x
′1−x
′4
). The additional term λ(x
′1−x
′4
)
modifies the self-potentials: f
′1 ← f
′1
(x
′1
) + λx
′1 and f
′4 ←
f
′4
(x
′4
)−λx
′4
, parameterizing a family of models on G
′all of which are equivalent to f under the constraint x
′1 = x
′4
. For a fixed λ, solving maxx L(x,λ) , g(λ) gives an upper bound on f
∗ = maxx f(x), so by optimizing λ to minimize g(λ),
we find the tightest bound g
∗ = minλ g(λ). If the constraint x
′1 = x
′4 is satisfied in the final solution, then there is strong duality g
∗ = f
∗and we obtain the correct MAP assignment for f(x).

We now discuss the general procedure and develop our approach to optimize g(λ) in more difficult cases.

## A. Obtaining A Tractable Graph By Vertex Replication

In this section, we consider approaches that involve *replicating* variables to define the augmented model. The basic constraints in designing G
′are as follows: G
′is comprised of replicas of nodes and edges of G . Every node and edge of G must be represented at least once in G
′. Finally, G
′
should be a thin graph, which relates to the complexity of our method.

To help illustrate the various strategies, we consider a pairwise model f(x) defined on 5 × 5 grid, as seen in Fig. 2(a). A natural approach is to break the model up into small subgraphs. The simplest method is to break the graph up into its composite interactions. For pairwise models, this means that we split the graph into a set of disjoint edges as shown in (b). Here, each internal node of the graph is replicated four times. To reduce the number of replicated nodes, and hence the number of constraints, it is also useful to merge many of these smaller subgraphs into larger thin graphs. One approach is to group edges into *spanning trees* of the graph as seen in (c). Here, each edge must be including in at least one tree, and some edges are replicated in multiple trees. The TRMP approach is based on this idea. One could also allow multiple replicas of a node in the same connected component of G
′. For instance, by taking a spanning tree of the graph and then adding an extra leaf node for each missing edge we obtain the graph seen in (d).

It is also tractable to use small subgraphs that are not trees. We can break the graph into a set of short loops as in (e) or a set of induced subgraphs as in (f) where we select a set of 3 × 3 subgraphs that overlap on their