Factor Graph
- A factor graph is a bipartite graph representing the factorization of a function.
- Enabling efficient computations, such as the computation of marginal distributions
A factor graph is a bipartite graph representing the factorization of a function.
Given a factorization of a function \(g(X_1, X_2, … , X_n)\)
\(g(X_{1},X_{2},\dots ,X_{n})=\prod _{j=1}^{m}f_{j}(S_{j})\)
where \(S_{j}\subseteq \{X_{1},X_{2},\dots ,X_{n}\}\), the corresponding factor graph G=(X, F, E) consists of
- variable vertices \(X=\{X_{1},X_{2},\dots ,X_{n}\}\),
- factor vertices \(F=\{f_{1},f_{2},\dots ,f_{m}\}\),
- and edges E.
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.
The messages of the sum-product algorithm are conceptually computed in the vertices and passed along the edges.
