AI Glossary / AI and machine learning / Advanced

Factor graph

Definition

A factor graph represents how a function of several variables can be written as a product of smaller functions called factors. It has two kinds of nodes: variables and factors, with an edge connecting a factor to each variable on which it depends.

What it means

Complicated probability models often contain reusable local relationships. One factor may describe a measurement, another a relationship between neighboring states and another a constraint. A factor graph makes that decomposition visible.

It is called bipartite because connections run between the two kinds of nodes. In probabilistic uses, the product may need normalization to become a probability distribution. The graph shows the stated mathematical structure; it does not automatically prove that the model describes the real world correctly or establish causal relationships.

How it works

First write the overall function as a product of local factors. Add a node for each variable and factor, then connect the dependencies. Inference algorithms can exchange messages along those connections to calculate quantities such as marginal probabilities.

The sum-product algorithm is a central example. On a cycle-free factor graph, appropriate message passing can compute exact marginals. On graphs with cycles, similar updates are commonly approximate and may not converge or produce exact answers. The size and form of each factor also affect computational cost, so a small-looking diagram can still represent a difficult calculation.

Three practical examples

1. A communications system can represent relationships between transmitted bits and parity constraints, supporting decoding algorithms.

2. A robot-localization model can combine motion relationships and sensor measurements to estimate a sequence of positions.

3. A probabilistic monitoring system can represent dependencies among hidden equipment states and observed signals. Its usefulness depends on the accuracy of those modeled relationships, not on drawing the graph alone.

Think of it this way

Imagine a project board with variable cards and rule cards. Each rule card touches only the variables it needs. You can see which pieces of information must be combined without writing one enormous rule for every possible configuration.

The analogy stops at the arithmetic. Factors can be numerical compatibility functions rather than simple yes-or-no rules, and inference must combine them according to the model.

Worked example

Let two binary variables X and Y take values zero or one. Define a factor a(X) with values a(0) = 1 and a(1) = 2. Define b(X,Y) to equal 3 when X and Y match and 1 when they differ.

The product gives unnormalized weights: (0,0) has 3; (0,1) has 1; (1,0) has 2; and (1,1) has 6. Their total is 12. Therefore P(X = 1) = (2 + 6) / 12 = 2/3.

The graph connects factor a only to X, and factor b to both X and Y. This small example can be enumerated directly; larger models use their factorization to avoid unnecessary repeated calculations where possible.

Illustrative case study

Fictional warehouse-robotics team RouteSense combines wheel-motion estimates with occasional position observations. It represents each position as a variable and each measurement or motion relationship as a factor.

When estimated paths drift, the team checks measurement uncertainty and timestamps instead of assuming the graph structure guarantees accuracy. A duplicated sensor observation had been counted as separate evidence. Correcting that modeling mistake matters more than changing the display of the graph. The scenario illustrates why a clear decomposition supports debugging while remaining dependent on valid assumptions.

Common misconceptions and mistakes

A factor graph is not a neural network merely because it contains nodes and edges. Nor must every factor be a normalized probability distribution by itself. The combined model determines how normalization is handled.

Do not assume the absence of a direct variable-to-variable edge means independence: factor graphs connect variables through factors. Another mistake is assuming message passing is always exact. Graph cycles and difficult factors complicate inference. Finally, using the same evidence twice can create unjustified confidence even when every individual factor seems reasonable.

Business use

Factor graphs are mainly relevant to systems involving structured uncertainty, sensing, decoding or constrained inference. For managers, their value lies in making model components explicit and helping specialists reuse efficient inference methods.

Ask which variables are observed, which are estimated and where each factor comes from. Determine whether inference is exact or approximate and how results are checked. If the application depends on confidence estimates, test calibration and sensitivity to uncertain measurements. A transparent model diagram is a useful communication aid, but it is not an independent validation of the model.

People also ask

Is a factor graph the same as a Bayesian network?

No. Both can represent probabilistic structure, but a factor graph explicitly displays the factorization using variable and factor nodes.

Can factors describe hard constraints?

Yes. A factor can assign zero weight to forbidden configurations, provided the resulting overall model remains meaningful.

Does every factor graph represent a probability distribution?

No. Factorization and message-passing ideas can also apply to other mathematical functions and computational settings.

Check your understanding

A factor depends on X and Z but not Y. Which variables should connect directly to that factor node?

Answer: X and Z. Adding an edge to Y would imply a dependency not present in the stated factor. Connections describe the factor's arguments, not visual proximity.

Related terms

• Belief propagation
• Marginal probability
• Bayesian network
• Markov random field
• Constraint satisfaction
• Graphical model
• sum-product algorithm
• partition function

Learn next

Factor a small joint distribution into local terms and draw its two kinds of nodes. Compute a marginal by enumeration, then follow how message passing would reuse those local calculations. Compare a tree with a graph containing a cycle.

• Message passing

More in AI and machine learning

• Experience replay - Experience replay is a training technique where a reinforcement learning agent stores its past experiences and repeatedly trains on random samples of them...
• Extremal Ensemble Learning - Extremal Ensemble Learning, or EEL, is a research approach that iteratively updates an ensemble of candidate solutions using their relative quality.
• Extremal optimization - Extremal optimization is a heuristic search method that preferentially changes poorly performing components of a candidate solution.
• Farthest-first traversal - Farthest-first traversal orders points by repeatedly selecting the point whose distance to its nearest previously selected point is greatest.
• Feature - A feature is one measurable input field a model learns from, such as a customer's age, an order's total or the hour a call arrived.
• Feature cross - A feature cross is a new input made by combining two or more existing fields, so the model can learn patterns that only appear when the fields interact.

Sources

Kschischang, Frey and Loeliger, Factor Graphs and the Sum-Product Algorithm, IEEE Transactions on Information Theory, 2001: https://web.stanford.edu/~montanar/TEACHING/Stat375/papers/sumprod.pdf. The two-variable calculation and RouteSense scenario are original illustrations, separate from the paper's examples.

Previous: Factor analysis Next: Factor level