The free energy of a factor graph: local free energies of the factors plus a counting correction at the variables. On a tree, at exact beliefs, it is of the data. On a loopy graph it is the Bethe approximation, whose stationary points are the fixed points of belief propagation.
Sources: Yedidia, Freeman & Weiss, Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms, IEEE Trans. Inf. Theory 51(7), 2005 (the Bethe free energy and its stationary points); Riegler, Kirkelund, Manchon, Badiu & Fleury, IEEE Trans. Inf. Theory 59(1), 2013, eq. (17) (the merged free energy with mean-field nodes); code:
lib/Mycelium.jl/src/free_energy.jl, tests:test/runtests.jl(“the chain is exact at every length”),lib/Lenticulum.jl/test/gaussian_oracle.jl,lib/Lenticulum.jl/test/lp020.jlBibliography: Yedidia et al. 2005 · Riegler et al. 2013
Theory (CT-ML wiki): Statistical Game · Variational Free Energy
The formula
Each factor has a belief over its own variables and a local free energy
Each variable has a marginal and the term . With counting numbers and , where counts the factors at ,
Energies add. Entropies add with a correction: a variable of degree appears in factor beliefs, so its entropy is counted times and copies are removed.
The factor belief is built from the messages into the factor, not from the variables’
marginals. Using the marginals would multiply the factor’s own outgoing message in again
(messages_into, free_energy.md §7).
Why it is exact on a tree
On a tree with exact beliefs the joint factorises as
the junction-tree factorisation. Substituting it into gives
the formula above, and that quantity is . AutoBayes’ chain rule (Theorem 23), folded
along any elimination order of the tree, telescopes to the same sum: the chain rule and the
Bethe form are one computation written in two orders. chain_free_energy is the first,
bethe_free_energy the second; the second has no order in it and is the one to report.
The total counting number is the Euler characteristic of the graph,
which is 1 for a connected tree and with independent loops. It counts loops; it
does not measure the error of the approximation, which depends on the potentials
(Finding a Factor Graph measures it for Gaussian couplings). The suite asserts
total_counting_number(g) == euler_characteristic(g) for graphs of belief-propagation nodes.
What “exact” requires
Exactness on a tree holds when every message is in a family its receiver takes exactly.
| situation | exact? |
|---|---|
| Gaussian, Dirac and categorical messages between the Gaussian, constraint and table factors | yes (lib/Lenticulum.jl/test/gaussian_oracle.jl: random trees against the dense joint, means, covariances, free energy and gradient) |
| a rank-deficient (flat) Gaussian message, e.g. from a partial observation | yes since 2026-11-10; before, GaussianFactor threw or returned wrong marginals (LP-024 Findings of the review of 2026-11-09) |
| a mixture message from a switching factor into a Gaussian or constraint factor | no: the receiver collapses the mixture to its moments. The fixed point is then one of assumed-density filtering and is not a stationary point of this free energy |
| the same graph with the switch and the variables its mixture reaches in one cluster node | yes (cluster; lib/Lenticulum.jl/test/cluster.jl against enumeration) |
NonlinearFactor | no: its messages and its free energy are those of a local linear model (nonlinear) |
MixtureReduction nodes | no free energy is defined; refused |
propagate! checks this table at run time (P13): after the one sweep of a tree schedule it sets
report.exact only when every node that sends a message declares exact messages, none is a
MixtureReduction node, and no factor received a mixture on one edge while sending on another;
otherwise its reason names each of these (lib/Mycelium.jl/src/passing.md, “Exactness checked
at run time”; tests lib/Lenticulum.jl/test/exact_report.jl). It is cautious in one case: a
MixtureReduction budget that no message exceeds is exact, and is reported as not exact.
On a loopy graph
The same formula is the Bethe approximation. Fixed points of loopy belief propagation are its
stationary points (Yedidia, Freeman & Weiss), not necessarily minima, and belief propagation
need not converge (Loopy Message Passing, Composing Optimisers). For Gaussian graphs
the means at a fixed point are exact and the variances are not (Weiss & Freeman 2001;
test/runtests.jl, “acausal and loopy”).
The gradient
At a fixed point the beliefs are stationary, so the derivative of in the parameters is the sum of the factors’ partial derivatives at fixed beliefs (the envelope theorem):
free_energy_gradient computes this (factor_belief, belief_free_energy;
LP-020 The fixed-message parameter gradient is not the free-energy gradient). On a tree
where the table above says “yes” it is the gradient of . Where the table says “no”
the beliefs are not stationary points of the reported free energy and the envelope argument
does not apply; fit_em then need not descend.
Other node rules
- Mean-field nodes contribute an average energy and no entropy, and the variable counting numbers count belief-propagation neighbours only: (Riegler et al., eq. 17; L-SPEC-005 The Hybrid Free Energy). The total is then no longer the Euler characteristic.
- Expectation-propagation nodes are counted like belief-propagation nodes (L-SPEC-008 Expectation Propagation and Mixture Reduction).
RelayFactor(an equality between two variables) has zero energy and the entropy of the pooled belief, : without it the relayed variable’s extra degree is uncounted (LP-019 Defects found in the review of the core packages).
Entropy conventions
variable_entropy is the differential entropy relative to Lebesgue measure for a Gaussian,
the Shannon entropy for a categorical, and 0 for a DiracBelief
(LP-006 Gaussian entropies are relative to Lebesgue measure). The value 0 for a point is
the convention for a clamped variable: the factor beliefs then range over the other variables
only, and the sum is of the clamped values (checked in lib/Lenticulum.jl/test/gaussian_oracle.jl).
The same convention extends to beliefs that a relation fixes in some directions only
(ExtendedGaussians with hard directions, from a HardConstraintFactor): each entropy is taken
relative to Lebesgue measure on the belief’s own support (support_entropy), and a point gets 0
as before. The relation’s own term is the finite limit of the noisy relation’s,
. With these the sum is on trees
(lib/Lenticulum.jl/test/hard_free_energy.jl; hard_constraint “Free energy”).
Two consequences:
- Free energies are comparable across graphs only when the same variables are clamped. A variable clamped in one graph and given a narrow Gaussian in another differs by an amount that grows without bound as the Gaussian narrows. Structure searches that compare free energies (Finding a Factor Graph, RQ-004 Is the Bethe Criterion Consistent for Structure Learning) must keep the data clamped in every candidate.
- Factors that pass points on unclamped variables (
message = :pointof the diffusion factor) run at zero temperature inside a formula written for temperature one: the entropy term vanishes and what remains is the energy of Energy-Based Factor Graphs §3.2.
The grading
factor_free_energies returns the per-factor terms keyed by factor name, and each factor’s
own scalarisation is applied to its own term (Scalar and Multivariate Energy). The
Gaussian family grades each term as (fit, complexity, negentropy).
Related: Loopy Message Passing, free_energy, Energy-Based Factor Graphs, Finding a Factor Graph, The Linear Gaussian Chain