A bipartite graphical representation of the factorization of a multivariate function (typically a joint probability or likelihood) in which variable nodes connect to factor nodes that represent local functions; this structure makes local dependencies explicit and directly supports message-passing algorithms such as sum–product and max–product for marginalization or MAP inference.

Principle

Local computation principle: global quantities (marginals or argmax assignments) can be computed by local messages exchanged between variable and factor nodes; exactness holds on trees and practical approximations arise from iterative message passing on loopy graphs.

Demonstration

Illustrative scenario → Decoding a binary linear error-correcting code: the parity-check factorization is represented as a factor graph where variable nodes are code bits and factor nodes enforce parity checks; belief propagation (sum–product) passes messages to estimate bit marginals and guide decoding decisions.

Misapplication

Interpreting beliefs produced by iterative (loopy) belief propagation as exact marginals without acknowledging approximation; on graphs with many short cycles the algorithm can converge to biased or unstable beliefs while still producing plausible but unjustified estimates.

Consequence

When the factorization is explicit and graph structure is amenable (tree-like or sparse), message-passing yields efficient marginal or MAP estimates; when applied beyond those conditions it offers scalable approximations but requires empirical validation or alternative methods (variational inference, sampling) when accuracy guarantees are needed.

Reversal

The message-passing principle loses exactness on graphs with nontrivial cycles or high treewidth; in such cases one must use junction-tree exact inference (possibly infeasible), variational approximations, or Monte Carlo methods — or redesign the factorization to exploit conditional independences.

Boundary

Clearly within: discrete variables with local factors that multiply to the joint function and a sparse bipartite factor graph. Boundary case: densely connected factors that imply large factor scopes or hybrid discrete–continuous variables. Clearly outside: representations that do not factorize the target function or models where factors are nonlocal and cannot be expressed as node-level functions.

Semantic Tension

Explicit modularity (clear factorization and local algorithms) versus model complexity (large factors or dense connectivity increase computational cost and may erase modular benefits).

Synthesis

Factor graphs expose the algebraic factorization underlying a model and translate it into an algorithmic template: when locality holds, message passing leverages factorization for efficient inference; when locality breaks down, the same representation clarifies why exact inference becomes intractable.