Factor graph

Factor graph is a bipartite graphical representation that makes the factorization structure of a probability distribution explicit. Unlike standard Bayesian networks or Markov random fields, which conflate variables and their interactions in a single graph type, a factor graph separates the two: variable nodes represent random variables, and factor nodes represent the functions — typically conditional probability tables or potential functions — that couple those variables. An edge connects a variable node to a factor node if and only if the variable is an argument of that factor.

This separation is not merely notational. It is computational. The factor graph is the data structure on which message-passing algorithms operate: each factor node sends messages to its neighboring variable nodes summarizing the marginal influence of the factor, and each variable node aggregates incoming messages to compute its posterior. The sum-product algorithm — the engine of exact inference in tree-structured graphs — is naturally expressed on factor graphs, as is the expectation propagation framework for approximate inference.

Factor graphs generalize beyond probability. In coding theory, they represent the parity-check structure of error-correcting codes; the iterative decoding algorithms that make modern communication systems possible are message-passing on factor graphs. In constraint satisfaction, factor nodes encode constraints and variable nodes encode variables to be assigned, and the survey propagation algorithm that solves random k-SAT instances operates on a factor graph representation. The same mathematical object governs probabilistic inference, error correction, and combinatorial search — not by analogy, but because all three problems are instances of marginalization on a factorized structure.