Factor graph

A factor graph is a bipartite graph representing the factorization of a function. In probability theory and its applications, factor graphs are used to represent factorization of a probability distribution function, enabling efficient computations, such as the computation of marginal distributions through the sum-product algorithm. One of the important success stories of factor graphs and the sum-product algorithm is the decoding of capacity-approaching error-correcting codes, such as LDPC and turbo codes. Factor graphs generalize constraint graphs. A factor whose value is either 0 or 1 is called a constraint. A constraint graph is a factor graph where all factors are constraints. The max-product algorithm for factor graphs can be viewed as a generalization of the arc-consistency algorithm for constraint processing. A factor graph is a bipartite graph representing the factorization of a function. Given a factorization of a function , where , the corresponding factor graph consists of variable vertices factor vertices , and edges . The edges depend on the factorization as follows: there is an undirected edge between factor vertex and variable vertex if . The function is tacitly assumed to be real-valued: . Factor graphs can be combined with message passing algorithms to efficiently compute certain characteristics of the function , such as the marginal distributions. Consider a function that factorizes as follows: with a corresponding factor graph shown on the right. Observe that the factor graph has a cycle. If we merge into a single factor, the resulting factor graph will be a tree. This is an important distinction, as message passing algorithms are usually exact for trees, but only approximate for graphs with cycles. A popular message passing algorithm on factor graphs is the sum-product algorithm, which efficiently computes all the marginals of the individual variables of the function. In particular, the marginal of variable is defined as where the notation means that the summation goes over all the variables, except .