1 Overview of Undirected Graphical Models

1.1 Core definitions and intuition

An undirected graphical model (UGM) is a probabilistic model in which variables are represented by vertices of an undirected graph and dependencies are represented by edges. The key idea is that the graph encodes which variables interact directly, while more distant relationships are mediated through intermediate vertices.

UGMs are also referred to as Markov random fields (MRFs). Both terms emphasize that uncertainty is modeled through a joint probability distribution over variables, with the distribution reflecting the structure implied by the graph. Instead of describing dependence through directed arrows, UGMs use an undirected structure together with local compatibility functions to define global behavior.

1.2 Relationship to conditional independence

In a UGM, conditional independence relationships are determined by graph separation. Intuitively, if a set of vertices separates two other sets in the graph, then information does not need to flow directly between the separated parts once the separating variables are known.

This makes UGMs useful for representing “who talks to whom” in probabilistic terms. The same separation logic can be used to reason about independence without explicitly manipulating the full joint distribution.

1.3 Graphical representation basics

A standard UGM uses:

  • Vertices (nodes) for random variables.
  • Edges for direct interaction or potential dependency.
  • Cliques (fully connected subgraphs) to define groups of variables that share a common potential.

Although edges suggest pairwise interaction, many UGMs are most naturally described using clique-based potentials, which can involve more than two variables at a time.

1.4 Markov properties in UGMs

Markov properties describe when conditional independence holds based on the graph. In UGMs, common formulations include local statements (conditioning on a node’s neighbors) and global statements (conditioning on separating sets).

These properties provide the bridge between graph structure and probabilistic semantics. They justify using the graph to simplify inference and learning, since many computations depend only on local neighborhoods rather than the entire variable set.

2 Graph Structure and Factorization

2.1 Cliques and clique potentials

A clique is a set of vertices in which every pair is connected by an edge. Cliques capture higher-order interactions that cannot be expressed by pairwise terms alone.

A clique potential is a nonnegative function defined on the variables in that clique. The collection of clique potentials defines the overall joint distribution. In many practical models, these potentials are chosen to reflect prior knowledge, such as smoothness in images or local consistency in sensor networks.

2.2 Factorization of the joint distribution

UGMs represent the joint distribution as a product of clique potentials, typically written in the form \[ P(x) \propto \prod_{C \in \mathcal{C}} \psi_C(x_C), \] where \(\mathcal{C}\) is the set of cliques, \(\psi_C\) is the potential for clique \(C\), and \(x_C\) denotes the variables in \(C\).

The proportionality constant is determined by normalization, often expressed via a partition function. This factorization is the main computational advantage of UGMs: it restricts dependence to the clique structure.

2.3 Local Markov property vs global Markov property

The local Markov property states that a node is conditionally independent of all other non-neighbor nodes given its neighbors. The global Markov property uses separation: if two regions of the graph are separated by a third region, then variables in those regions are conditionally independent given the separating variables.

In well-behaved UGMs, these local and global forms correspond, allowing equivalent reasoning depending on which is more convenient. Local properties tend to be easier to interpret and implement, while global separation is useful for theoretical guarantees.

The Hammersley–Clifford theorem provides a conceptual correspondence between:

  • conditional independence encoded by the graph, and
  • factorization of the joint distribution into clique potentials.

At a high level, it explains when the presence of certain conditional independences implies that the joint probability can be written as a product over clique terms. This connection underpins the use of graph structure as a design tool for probabilistic modeling.

3 Common Model Families

3.1 Pairwise Markov random fields

A pairwise Markov random field restricts clique size to at most two. The joint distribution is then determined by unary terms (single-variable potentials) and pairwise terms (edge potentials). This structure is common in simplified treatments of spatial models and statistical mechanics-inspired formulations.

Pairwise models are attractive because they reduce the complexity of specifying potentials and can enable efficient inference in certain graph topologies.

3.2 Exponential family random fields (general form)

Many UGM potentials can be expressed using the exponential family. In this view, the joint distribution takes a log-linear form where features correspond to clique configurations.

This representation is helpful for learning, as parameters can weight features that capture patterns such as agreement/disagreement on edges or higher-order consistency constraints in larger cliques.

3.3 Ising model

The Ising model is a canonical binary pairwise model. Variables typically represent spins taking values such as \(\{-1, +1\}\). The probability of a configuration increases when neighboring spins align, controlled by coupling strengths and possible external fields.

Ising models illustrate how local interactions produce global behavior, and they serve as a foundation for reasoning about sampling and approximate inference in UGMs.

3.4 Gaussian Markov random fields

Gaussian Markov random fields model continuous variables with a joint multivariate normal distribution constrained by an undirected graph. In this setting, edges correspond to nonzero entries in the precision matrix (the inverse covariance matrix).

A key property is that conditional distributions remain Gaussian, and conditional independence can be read off from the sparsity pattern in the precision matrix, enabling efficient computations in many linear-Gaussian applications.

3.5 Conditional random fields (brief contrast)

Conditional random fields (CRFs) are closely related but differ in what is modeled. Instead of describing a joint distribution over all variables in an undirected manner, CRFs model conditional distributions of labels given observed features.

This distinction makes CRFs particularly common in sequence labeling and vision tasks, where one wants to incorporate observed data without modeling its full generative distribution.

4 Inference in UGMs

4.1 Marginal inference goals

Inference in UGMs often aims to compute:

  • Marginals \(P(x_i)\) or \(P(x_i \mid \text{evidence})\),
  • Joint marginals for subsets of variables,
  • Partition functions or expectations under the model.

Exact inference is generally computationally expensive for large graphs, which motivates approximate and structured methods.

4.2 MAP inference vs marginal distributions

Two common targets are:

  • MAP (maximum a posteriori): find the most probable configuration.
  • Marginals: compute distributions that reflect uncertainty across configurations.

MAP inference can be easier to reason about for decision-making, while marginal inference is better when calibrated probabilities or uncertainty estimates are required.

4.3 Belief propagation (sum-product)

Belief propagation is an iterative message passing algorithm used to compute marginals in factorized graphical models. For tree-structured graphs, it yields exact results.

In UGMs, belief propagation can be viewed as sum-product over clique factors, where messages summarize how local potentials influence beliefs about neighboring variables.

4.3.1 Message passing on trees

On trees, message passing proceeds from leaves inward (and possibly back outward). Each node updates outgoing messages using incoming messages and its local potentials. Because there are no cycles, information is incorporated without double-counting, producing correct marginals.

This setting provides an important conceptual baseline for understanding approximate inference on more complex graphs.

4.3.2 Approximate inference on loopy graphs

When the graph contains cycles, belief propagation becomes approximate. The algorithm may still converge, but convergence is not guaranteed and results can be biased.

Despite these limitations, loopy belief propagation is widely used in practice because it often provides good approximations, especially in sparse graphs or when interactions are weak.

4.4 Sampling-based inference

When deterministic algorithms are costly, sampling can approximate expectations under the target distribution. Sampling-based inference trades exactness for computational feasibility.

Common approaches include Markov chain Monte Carlo (MCMC) and specialized sampling strategies tailored to the structure of the model.

4.4.1 Markov chain Monte Carlo overview

MCMC constructs a Markov chain whose stationary distribution matches the desired UGM distribution. After a “burn-in” period, samples can be used to estimate marginals and other quantities.

Performance depends on mixing behavior: chains that explore the space slowly can yield high variance estimates.

4.4.2 Gibbs sampling in UGMs

Gibbs sampling updates variables one at a time by drawing from their conditional distributions given the rest. In a UGM, these conditionals are determined by the neighboring cliques, making Gibbs updates local.

For pairwise models, each update depends only on the immediate neighborhood, which can be efficient. Still, strong dependencies can slow down mixing.

4.5 Variational inference approaches

Variational inference approximates the true posterior with a simpler distribution by optimizing an objective that balances fit and complexity. A common approach is mean-field variational methods, where dependencies are broken in a controlled way.

Variational methods are often faster than MCMC for large problems, but the approximation quality depends strongly on the chosen variational family.

5 Learning and Parameter Estimation

5.1 Maximum likelihood learning

Maximum likelihood learning fits parameters to maximize the probability of observed data under the model. For UGMs, the log-likelihood includes a normalization term, which depends on the partition function.

That normalization requires summing (or integrating) over all configurations, which is typically intractable for large graphs.

5.1.1 Partition function challenges

The partition function couples all variables through global normalization. As a result, computing gradients for maximum likelihood often involves expectations that are difficult to obtain exactly.

Practical solutions use approximate inference inside the learning loop, such as belief propagation, sampling, or variational bounds.

5.2 Pseudolikelihood methods

Pseudolikelihood replaces the intractable joint likelihood with a product of local conditional likelihoods. Each variable’s conditional distribution is modeled given its neighbors, which avoids computing the full partition function.

While pseudolikelihood can be computationally efficient and robust, it may underutilize global information compared with full maximum likelihood.

5.3 Structure learning (learning edges/cliques)

Structure learning aims to infer the graph connectivity or clique structure from data. This is often harder than parameter learning because it involves discrete decisions about which potentials to include.

Methods may use greedy search, penalized objectives, or constraint-based tests to propose candidate edges, followed by parameter estimation and model selection.

5.4 Regularization and sparsity

Regularization discourages overly complex models and helps prevent overfitting. In UGMs, sparsity-promoting penalties encourage fewer edges or weaker interactions.

Such constraints are especially important when data are limited or when the feature set is large, since otherwise the learned potentials can fit noise rather than signal.

5.5 Model selection and evaluation

Model selection compares candidate UGMs using criteria such as held-out likelihood, predictive accuracy, or information-theoretic scores. Because exact likelihood is often difficult, evaluation may rely on approximate measures or surrogate tasks.

Cross-validation and careful assessment of generalization are common, particularly when inference is approximate and introduces additional uncertainty.

6 Constraints, Symmetries, and Practical Modeling

6.1 Handling missing or noisy observations

Real data frequently include missing measurements or uncertainty. UGMs can incorporate missingness explicitly by treating unobserved variables as latent and performing inference over them.

For noisy observations, potentials can be designed to reflect measurement reliability, often through likelihood terms or robustness-oriented potentials.

6.2 Incorporating prior knowledge

Prior knowledge can guide the selection of clique structure and potential forms. Examples include enforcing smoothness, symmetry, or consistency constraints suggested by the application domain.

This can reduce the search space for learning and improve interpretability, since learned interactions can be aligned with known local patterns.

6.3 Scalability considerations

Large graphs create computational bottlenecks in both inference and learning. Scalability is influenced by:

  • graph sparsity,
  • clique size,
  • inference method choice,
  • and the cost of updating messages or sampling states.

Techniques such as restricting to pairwise models, using approximate inference, and exploiting sparse linear algebra for Gaussian models are common strategies.

6.4 Approximation trade-offs

Approximate inference introduces errors that depend on model structure and algorithm settings. Message passing on loopy graphs can be fast but potentially biased. Sampling can be more faithful but may require many iterations for low variance estimates.

Good practice involves diagnosing approximation quality using convergence checks, stability across runs, and comparison to smaller-scale exact computations when feasible.

6.5 Diagnostics and convergence issues

Inference algorithms may fail to converge or converge to poor fixed points. Diagnostics can include monitoring message norms, tracking changes in beliefs, or evaluating consistency between iterations.

In learning, unstable optimization may arise when expectations are noisy or when gradients rely on approximate inference. Careful tuning, learning-rate schedules, and alternative objectives can mitigate these issues.

7 Applications and Use Cases

7.1 Spatial statistics and image modeling

UGMs are used to model spatial dependencies, such as smoothing pixels or capturing local textures. Clique potentials can encode preferences for neighboring pixels to take similar values or follow structured patterns.

In image contexts, these models often support tasks like segmentation, denoising, and reconstruction where local consistency is essential.

7.2 Network and relational data

Graph-based data naturally align with UGMs. Entities connected by relationships can be represented as nodes, and interactions can be encoded along edges or within relational cliques.

Such models support inference about latent attributes, compatibility, or consistency across a network.

7.3 Error-correcting and constraint-based modeling

UGMs can represent constraints that favor consistent assignments, making them useful in error correction. Local checks can be encoded as potentials over sets of variables that must satisfy certain parity or agreement rules.

In these cases, inference effectively searches for the configuration that best satisfies constraints under uncertainty.

7.4 Robotics and sensor fusion (conceptual)

Sensor fusion combines multiple measurements subject to noise and partial observability. UGMs can represent latent states (e.g., positions or readings) and connect them via potentials reflecting physical or statistical relationships.

This allows integration of heterogeneous sensors through local compatibility terms, supporting robust estimation when individual sensors are unreliable.

8 Connections to Other Frameworks

8.1 Comparison with directed graphical models (DAGs)

Directed graphical models (Bayesian networks) factorize the joint distribution using conditional probabilities along directed edges, whereas UGMs use undirected factorization into clique potentials.

The contrast affects learning and inference: Bayesian networks often emphasize causal or generative structure, while UGMs emphasize neighborhood-based interactions and conditional independence via separation.

Factor graphs make the factorization explicit by using nodes for variables and factor terms. UGMs can be transformed into factor-graph representations by treating each clique potential as a factor node.

This representation clarifies message passing schedules and unifies the view of different inference algorithms.

8.3 Relationship to energy-based models

Many UGMs can be written in energy form, where the negative log of the unnormalized probability defines an energy function. Lower-energy configurations correspond to higher probability.

This connection links UGMs to the broader literature on energy-based models, where inference often involves optimization or sampling guided by an energy landscape.

When potentials are restricted to indicate compatibility (e.g., zero probability for disallowed configurations), UGMs resemble weighted constraint satisfaction problems.

Inference then becomes similar to finding assignments that satisfy constraints while maximizing overall compatibility, bridging probabilistic reasoning and combinatorial optimization.

9 Worked Example Workflow

9.1 Constructing the graph from assumptions

A typical workflow begins by specifying variables and deciding which conditional dependencies are plausible. For instance, one may assume that each variable directly interacts only with a small set of neighbors.

These assumptions determine the undirected edges and, consequently, which cliques will be used for potentials.

9.2 Defining clique potentials

Next, clique potentials are defined to reflect how variable configurations should be scored. Unary potentials encode preferences for individual variables, while pairwise or higher-order potentials encode interaction strengths or consistency rules.

Potentials can be set from domain knowledge or parameterized for learning.

9.3 Performing inference (high level)

Inference then computes quantities of interest given evidence. A practitioner selects an algorithm based on graph structure: belief propagation for tree-like cases, loopy belief propagation for approximate results, sampling when exact computation is infeasible, or variational methods when speed is crucial.

Outputs typically include marginal beliefs, MAP estimates, or derived expectations.

9.4 Learning parameters (high level)

If parameters are unknown, they are estimated from data. Depending on tractability and dataset size, learning may proceed via maximum likelihood with approximations, pseudolikelihood, or regularized objectives.

During learning, the chosen inference method is often embedded to evaluate gradients or local conditional terms.

9.5 Interpreting results and uncertainty

Finally, results are interpreted in terms of both predictions and uncertainty. Marginals help quantify confidence, while MAP outputs provide single best assignments.

When inference is approximate, uncertainty estimates should be treated cautiously and validated through diagnostics such as sensitivity to initialization, convergence behavior, or comparison with held-out data.