A factor graph is a bipartite graph representing a factorization of a function
 |
where 
and 
denotes the arguments
with indices in 
. It has a variable graph
vertex for each 
, a factor graph
vertex for each 
, and a graph
edge between them iff 
(Kschischang et al. 2001).
For variables with finite domains, the sum-product algorithm seeks to compute a marginal function
 |
by passing messages along the graph edges. A variable-to-factor message is the product of the incoming messages from the other adjacent factors. A factor-to-variable message is obtained by multiplying the factor by the incoming messages from its other variables and summing out those variables. On a tree, a pass toward a root followed by a pass away from it gives all marginal functions exactly. Iterating these rules on a graph with cycles is generally approximate and need not converge (Kschischang et al. 2001).
When 
is nonnegative
with positive total sum, normalization
gives a probability mass function, and
the normalized 
give its marginal distributions. A Tanner
graph represents parity-check constraints in this form. A cluster
graph permits messages involving several variables
jointly.
