Markov Random Fields and the Intractability of the Partition Function

Some dependencies have no natural direction. The pixels of an image, the sites of a lattice, the variables of a constraint problem: asking which of a pair comes first is meaningless, and a directed acyclic graph can only fake the symmetry by orienting edges arbitrarily, which changes the set of independencies it can assert. The undirected alternative replaces parent sets with potentials over cliques. Writing $C$ for the cliques of an undirected graph $G$, the model is

$$p(x) = \frac{1}{Z} \prod_{C \in \mathcal{C}} \psi_C(x_C), \qquad Z = \sum_{x} \prod_{C \in \mathcal{C}} \psi_C(x_C)$$

The potentials are arbitrary non-negative functions of their clique’s variables. They are not probabilities and have no reason to sum to one, so a normalizing constant is required, and that constant is the only non-local quantity in the definition.

The factorization follows from, not precedes, the independencies

For a strictly positive distribution, the graph and the factorization are two views of the same thing. If $p$ is positive on every assignment and satisfies the Markov property of $G$ — each variable is independent of the rest given its neighbours — then $p$ factorizes over the maximal cliques of $G$, and conversely any such factorization satisfies the Markov property. This is the Hammersley-Clifford result, and the positivity requirement is what makes it a theorem rather than a definition; without it, deterministic relationships can satisfy the independencies while admitting no clique factorization.

The graph’s edges carry a precise reading in the pairwise case: two variables are missing an edge exactly when they are independent given all the other variables. That is a weaker statement than the directed version, where d-separation can report independence for sets of variables rather than just neighbours, as covered in Directed Graphical Models: D-Separation and the Markov Blanket. Any positive directed model can be converted to an undirected one by marrying the parents of each node and dropping directions, but the conversion is lossy in a specific way: the independence of two parents given no evidence, which the directed graph asserts whenever they share a child, is not representable in the undirected graph, and the moralization adds the edge that destroys it. The undirected graph is therefore at least as dense as the directed one, and its treewidth — the quantity that sets the cost of exact inference in Exact Inference by Variable Elimination and the Cost of Treewidth — is at least as large.

Pairwise potentials are not the whole story

It is tempting to define the model as a product over edges, one pairwise potential each. That restricts the class. A positive distribution whose independencies are exactly those of the graph factorizes over maximal cliques, and a clique of three or more variables may require a potential that is not the product of pairwise terms. Encoding a hard constraint that at most one of three variables is active is easy with a ternary potential and impossible with pairwise potentials alone. The practical consequence is that a model specified as an edge potential list has already assumed conditional independence structure inside every clique.

The equivalent formulation as an energy over the graph is the one most implementations use. Writing $\psi_C(x_C) = \exp\bigl(-E_C(x_C)\bigr)$ turns the product into a sum of energies, and a further restriction to linear combinations of sufficient statistics gives

$$p(x) = \exp\bigl(\theta \cdot f(x) - A(\theta)\bigr), \qquad A(\theta) = \log \sum_{x} \exp\bigl(\theta \cdot f(x)\bigr)$$

This is an exponential family with natural parameter $\theta$ and log-normalizer $A$, and it makes the partition function a familiar object: $Z = e^{A(\theta)}$, convex in $\theta$, with gradient equal to the expectation of the sufficient statistics under the model, $\nabla A(\theta) = \mathbb{E}_\theta[f(x)]$. That gradient identity is why fitting such a model requires expectations rather than counts, and why every learning algorithm for it faces the same integral.

A count in disguise

For binary variables the sum defining $Z$ runs over $2^n$ assignments, and $n = 100$ means about $1.27 \times 10^{30}$ terms, each a product over cliques. The number of terms is large in the same way a counting problem is large, and the reduction is literal: evaluating $Z$ for a model built from a propositional formula yields the number of satisfying assignments, so exact evaluation is P-hard in the counting class for general graphs. Restricted structure can rescue it. On planar lattices with no external field the partition function of the Ising model can be computed in polynomial time by a Pfaffian argument, and that tractability disappears when the graph is non-planar or the field is nonzero; treewidth again separates the two cases, since a lattice of $n$ sites has treewidth growing with the side length and any exact elimination pays for it.

Because $Z$ is a sum of products of local functions, it is also computable by variable elimination with no evidence: eliminate every variable, and the normalizer that accumulates is exactly $Z$. That is a useful equivalence. A directed network never needs $Z$, because the conditional distributions are already normalized and the product sums to one, but after conversion to undirected form the constant returns, and the directed inference problem becomes a partition function computation on the moral graph.

Structures where the sum collapses

Undirected models are not uniformly hard, and the cases where $Z$ is available are worth naming, because they show what the hardness depends on. A chain of $n$ variables with pairwise potentials has a partition function computable by multiplying matrices, one per edge: a $d \times d$ transfer matrix holds the potentials for each pair of values, the sum over all $d^n$ assignments collapses into $n - 1$ matrix products, and the trace of the product is $Z$ at a cost of $O(n,d^3)$ operations. A tree generalizes the same calculation through message passing, as described in Belief Propagation on Trees and Why Loopy Message Passing Fails.

A Gaussian Markov random field avoids the sum entirely. Writing the joint as a multivariate normal with precision matrix $Q$ (the inverse of the covariance), the normalizing constant is analytic, $Z^{-1} = (2\pi)^{n/2}\lvert Q \rvert^{-1/2}$, so the partition function reduces to a determinant, computed in $O(n^3)$ operations or faster when $Q$ is sparse. Sparsity in $Q$ is not cosmetic: a zero entry there means the two variables are conditionally independent given all the others, so the graph is a picture of the zeros of the precision matrix rather than of the covariance. What the chain, the tree, and the sparse Gaussian have in common is low treewidth, and the exponential cost appears only when that fails.

Scale and identifiability defects

Two failure modes come from the constant rather than from the model. The first is numeric. Potentials multiply, so their values can underflow to zero long before the model is large, and $Z$ can exceed the representable range even though the probabilities it normalizes are ordinary. Working in log space with a stabilized accumulation of exponentials keeps the arithmetic finite; summing raw potentials does not. The second is identifiability. Multiplying every potential by a constant $c$ multiplies $Z$ by $c$ a fixed number of times and leaves every probability unchanged, so the parameters of an unnormalized potential list are not identifiable, and any fitting procedure that reports them must fix the scale by convention.

# Two binary variables joined by one pairwise potential.
psi = {(0, 0): 4.0, (0, 1): 1.0, (1, 0): 1.0, (1, 1): 2.0}

for c in (1.0, 10.0):
    Z = sum(c * v for v in psi.values())          # rescaling moves entirely into Z
    p = {k: c * v / Z for k, v in psi.items()}
    print(sorted(p.items()))
    # both iterations print the same probabilities: 0.5, 0.125, 0.125, 0.25

What remains tractable

Not every query needs $Z$. A maximum a posteriori assignment maximizes the product of potentials, and the constant cancels between candidate assignments, so the maximization is normalization free and only the maximization cost of the elimination order applies. Conditional probabilities of one sub-event against another also cancel the constant, which is why sampling methods that estimate ratios rather than levels remain useful. What cannot be avoided is the marginal likelihood of a model class, the quantity used to compare structures; it is a partition function and inherits both the counting hardness and the numeric fragility.

Approximations of $\log Z$ split into two families, both of which reappear in later articles. Message passing on a graph with loops minimizes an approximate free energy whose stationary points give estimates of $\log Z$; its guarantees and its failures are the subject of Belief Propagation on Trees and Why Loopy Message Passing Fails. Optimization over a restricted family of distributions, instead of a restricted graph, produces a lower bound on $\log Z$ rather than an estimate, as treated in Variational Inference and the Evidence Lower Bound.