A factor graph is a bipartite graph that represents how a function of many variables decomposes into a product of functions involving smaller subsets of those variables. It contains two kinds of nodes: variable nodes, representing the arguments of the function, and factor nodes, representing the functions in the product. An edge connects a variable to a factor exactly when that variable belongs to the factor’s scope. Factor graphs are particularly important as probabilistic graphical models, but they also describe deterministic constraints and optimization problems. Their explicit representation of local interactions supports efficient computation by message passing.
Mathematical definition
Suppose a function admits the factorization
where indexes the factors, is the scope of factor , and denotes the collection of variables indexed by .
The corresponding factor graph has:
- a variable node for each ;
- a factor node for each ;
- an undirected edge between and whenever .
Variable nodes are conventionally drawn as circles and factor nodes as squares. There are no edges directly joining two variable nodes or two factor nodes.
For example,
has three variable nodes and three factor nodes. The unary factor is connected only to ; connects to and ; and connects to and . This graph is a tree.
A factor graph represents a particular factorization, not a unique representation of a function. Factors can be combined or decomposed, sometimes with the introduction of auxiliary variables. Such transformations can change the graph’s cycles and the cost of inference without changing the function represented.
Probabilistic interpretation
For probabilistic modeling, the variables represent random variables and the factors are nonnegative. A joint probability distribution can be written as
where, for discrete variables,
The constant , called the partition function or normalizing constant, must be finite and positive. For continuous variables, the sum is replaced by an appropriate integral. Individual factors need not be probability distributions or sum to one: only the normalized product must define a valid distribution.
Factors can encode several kinds of information:
- Prior information, through factors derived from a prior distribution.
- Observations, through likelihood factors.
- Interactions, through compatibility functions that assign relative weights to combinations of values.
- Hard constraints, through factors that are zero for forbidden assignments and positive for permitted ones.
Conditioning on an observed variable amounts to fixing its value in every adjacent factor. A factor involving both observed and unobserved variables then becomes a function of the remaining unknowns.
Two central tasks are marginalization and joint optimization. Marginalization computes quantities such as
where the notation means summing over every variable except . Maximum a posteriori estimation instead seeks an assignment maximizing the joint posterior probability. These tasks use the same factorization but require different computational operations.
Relationship to other graphical models
Bayesian networks
A Bayesian network represents a distribution using a directed acyclic graph and a product of local conditional distributions:
where denotes the parents of node .
Its factor-graph representation introduces one factor for each conditional distribution, connected to the child variable and all its parents. This preserves the product but does not retain the directed parent–child structure as part of the factor graph itself. In particular, a factor graph does not by itself specify a causal interpretation.
A Bayesian network with no directed cycles can nevertheless yield a factor graph with undirected cycles. The two notions of acyclicity are different.
Markov random fields
A Markov random field uses an undirected graph on variables, with a distribution commonly expressed as a product of clique potentials. A factor graph makes those potential functions explicit.
This distinction is useful for higher-order interactions. A single factor is represented by a factor node connected to three variables—a tree-shaped graph. In a variable-only undirected representation, the same factor induces a triangle among those variables. The triangle records their interaction but does not identify whether it arose from one three-variable factor or several pairwise factors.
For nonnegative factorizations defining valid distributions, separation of variable sets by another variable set in the factor graph implies the corresponding conditional independence. The converse need not hold: special parameter values or algebraic cancellations may produce independences not apparent from the graph.
Sum-product message passing
The best-known inference procedure on factor graphs is the sum-product algorithm, a form of belief propagation. It exploits the distributive law to reorganize a large sum of products into local computations.
Let denote the factor nodes adjacent to variable . A variable-to-factor message is
A factor-to-variable message is
Each message is a function of the variable associated with its edge. The exclusion of the recipient from the incoming messages prevents immediate reuse of information in the opposite direction.
After suitable messages have been computed, the single-variable belief is
Normalizing this expression produces a candidate marginal distribution.
Exactness on trees
If the factor graph is a tree, sum-product computes exact marginals through a finite inward-and-outward message schedule. Removing an edge separates the graph into two components, and each message summarizes the contribution from one component as a function of the variable at the boundary. This separation explains why the local updates recover the global result.
For a forest, the same reasoning applies independently to each connected component. With consistent handling of message normalization constants, tree-based message passing can also recover the partition function.
Tree structure alone does not guarantee low computational cost. A factor connecting discrete variables with possible values each may require work proportional to if treated as an unstructured table. Efficient inference therefore depends both on graph structure and on the internal form of the factors.
Loopy belief propagation
On a graph containing cycles, the same equations can be applied iteratively. This procedure is known as loopy belief propagation. Updates may be synchronous, sequential, or scheduled adaptively.
Unlike the tree case, loopy belief propagation has no general guarantee of convergence. Even when it converges, its beliefs need not equal the exact marginals. The quality of the approximation depends on the model, interaction strengths, graph structure, and update procedure. Damping—mixing new messages with previous ones—is often used to moderate oscillations, but it does not provide a universal correctness guarantee.
Messages can be rescaled without changing normalized beliefs. Implementations often normalize messages or work with logarithms to improve numerical stability.
A chain example
Consider a three-variable distribution
Direct computation of sums over both and . The factorization allows these sums to be evaluated separately:
The desired marginal is then
The functions and are the messages arriving from the two sides of the chain. The same principle extends to larger trees: each branch is compressed into a function of the variable through which it joins the remainder of the graph.
Optimization and related algorithms
Replacing summation by maximization yields max-product message passing. In logarithmic form, products become sums, producing max-sum updates. If the factors are written as
maximizing their product is equivalent to minimizing the total energy
The corresponding algorithm is commonly called min-sum.
On trees, these algorithms can find a globally optimal assignment. Recovering a consistent assignment generally requires storing local maximizing or minimizing choices and tracing them back through the graph. Independently selecting the best value of each variable from its max-marginal can fail when ties produce incompatible choices.
Several familiar algorithms fit this framework:
- Forward–backward inference in a hidden Markov model is sum-product computation on a chain.
- The Viterbi algorithm is a chain-structured max-product or max-sum computation.
- Linear-Gaussian models support Gaussian messages represented by means and precision matrices; appropriate chain models recover Kalman filtering and smoothing.
The operations can also be generalized algebraically, yielding related algorithms for counting, feasibility, and other forms of local computation.
Exact inference beyond trees
Cycles do not prevent exact inference, but they usually require more expensive representations. Variable elimination sums out variables successively, creating intermediate factors. Its cost depends strongly on the elimination order and the scopes of these factors.
A junction-tree algorithm organizes groups of variables into a tree of clusters, permitting exact message passing between clusters. The relevant structural quantity is treewidth, commonly measured on the associated variable-interaction graph. For discrete variables, computation is generally exponential in the size of the largest required cluster.
Thus, a sparse-looking factor graph is not necessarily easy to solve. Large factor scopes, unfavorable connectivity, or complex local functions can dominate the computational cost.
Applications and limitations
Factor graphs are widely used in communication systems. In error-correcting codes, variable nodes may represent transmitted bits and factor nodes parity constraints. For low-density parity-check codes, this representation is commonly called a Tanner graph. Iterative message passing combines channel evidence with the constraints to estimate transmitted bits.
In machine learning and statistical modeling, factor graphs represent structured distributions in which local dependencies must be combined to infer unobserved variables. They are also used in robotics and estimation, where factors can encode measurements, motion constraints, and prior information. For nonlinear least-squares models, the graph describes residual dependencies, while numerical optimization—not necessarily sum-product—is used to obtain a solution.
Their principal limitation is that a clear factorization does not by itself make inference tractable. Continuous messages may be functions that cannot be represented exactly in finite form; practical methods then use analytic families, discretization, sampling, or other approximations. Strong interactions and many cycles can make iterative inference unreliable.
Factor graphs also describe a model rather than validate it. Missing dependencies, unsuitable noise assumptions, or incorrect local factors remain modeling errors even when inference is exact.
Historical development
Factor graphs draw on earlier work in graphical modeling, decoding, and local computation. Tanner graphs provided an important precursor in coding theory. The modern factor-graph framework and its presentation of the sum-product algorithm were developed prominently by Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger in their 2001 paper Factor Graphs and the Sum-Product Algorithm. This formulation helped establish a common language for algorithms previously developed in different fields, including probabilistic inference, signal processing, and error-correcting codes.