A cluster graph in probabilistic inference is an undirected graph whose vertices are labeled by sets 
of random
variables. Each factor in a product of nonnegative functions is assigned to a cluster containing all its arguments. Each graph edge 
is labeled by a separation set,
or sepset, 
(Koller and Friedman 2009, p. 346).
Messages between adjacent clusters are functions of the variables in their sepset. They can therefore
retain joint information about several variables, in
contrast to the single-variable messages of a factor
graph. The running intersection property requires that, for each variable 
, the clusters containing 
and the graph edges whose sepsets
contain 
form a tree. The whole cluster graph may still contain cycles, and a sepset need not be the full intersection
of its adjacent clusters (Koller and Friedman
2009, pp. 396-398).
When the whole cluster graph is a tree satisfying the running intersection property, it is called a junction tree or clique tree. Its clusters give a tree decomposition of the graph that joins variables occurring together in a factor. Sum-product message passing then computes exact marginal functions, which yield marginal distributions when the product of factors has positive finite total mass. In a cluster graph with cycles, convergence and exactness are not guaranteed (Koller and Friedman 2009, pp. 347-355 and 398-400).
Let 
be a connected
cluster graph with nonempty sepsets satisfying the running intersection property,
and let 
be the number of distinct variables in its clusters.
Counting occurrences of each variable in its tree
gives
 |
(1)
|
Indeed, a variable occurring in 
clusters occurs in exactly 
sepsets. The circuit rank 
consequently satisfies
 |
(2)
|
For fixed clusters, each unit of the sepset surplus 
therefore reduces the circuit
rank by one (Sadie et al. 2026).
In particular, construct a cluster graph from the unchanged parity-check factors of a low-density parity-check code,
using the layered trees construction that connects all occurrences of each variable
by a tree and overlays the resulting trees.
If both this cluster graph 
and the corresponding Tanner graph 
are connected,
then
 |
(3)
|
This is an identity for circuit rank, not a guarantee of improved decoding accuracy (Sadie et al. 2026).
In a different graph-theoretic usage, a cluster graph is a graph disjoint union of complete graphs (Shamir et al. 2004).
