marginalization in general graphs is called the junction tree algorithm, which is simply belief propagation on a modified graph guaranteed to be a tree. The basic premise is to eliminate cycles by clustering them into single nodes. Related algorithm and complexity issues A similar algorithm is commonly referred to as the Viterbi algorithm, but also known as a special case of the max-product or min-sum algorithm, which solves the related problem of maximization, or most probable explanation. Instead of attempting to solve the marginal, the goal here is to find the values that maximizes the global function (i.e. most probable values in a probabilistic setting), and it can be defined using the arg max: An algorithm that solves this problem is nearly identical to belief propagation, with the sums replaced by maxima in the definitions. It is worth noting that inference problems like marginalization and maximization are NP-hard to solve exactly and approximately (at least for relative error) in a graphical model. More precisely, the marginalization problem defined above is #P-complete and maximization is NP-complete. The memory usage of belief propagation can be reduced through the use of the Island algorithm (at a small cost in time complexity). Relation to free energy The sum-product algorithm is related to the calculation of free energy in thermodynamics. Let Z be the partition function. A probability distribution (as per the factor graph representation) can be viewed as a measure of the internal energy present in a system, computed as The free energy of the system is then It can then be shown that the points of convergence of the sum-product algorithm represent the points where the free energy in such a system is minimized. Similarly, it can be shown that a fixed point of the iterative belief propagation algorithm in graphs with cycles is a stationary point of a free energy approximation. Generalized belief propagation (GBP) Belief propagation algorithms are normally presented as message update equations on a factor graph, involving messages between variable nodes and their neighboring factor nodes and vice versa. Considering messages between regions in a graph is one way of generalizing the belief propagation algorithm. There are several ways of defining the set of regions in a graph that can exchange messages. One method uses ideas introduced by Kikuchi in the physics literature, and is known as Kikuchi's cluster variation method. Improvements in the performance of belief propagation algorithms