Entropy Estimation in Cluster Graphs

Probabilistic graphical models (PGMs) provide a powerful framework for modelling complex systems, but inference over loopy graphs requires approximate methods whose accuracy depends on how factors are clustered in the graphical representation. Existing factor clustering methods rely on the number of variables in a cluster to bound its memory footprint, or on the maximal possible entropy as a proxy for how informative a merged cluster would be—both loose approximations that can lead to suboptimal merging decisions. We address this limitation by proposing an efficient algorithm for estimating the joint entropy of a group of clusters directly, without explicitly multiplying out the constituent factors, thereby avoiding the exponential computational cost that makes exact computation prohibitive. The algorithm integrates naturally with both static and dynamic graph restructuring methods, and reduces to a specific case of the Kikuchi entropy approximation when applied to the complete graph. Building on the entropy estimation algorithm, we further propose an algorithm for estimating the number of non-zero probabilities in a factor product, again without explicit multiplication. Experiments on models with up to 24 variables demonstrate that the algorithm produces accurate entropy estimates (when compared with ideal junction tree performance) across diverse model types, with errors remaining within tight bounds. Scalability is further validated on a substantially larger model defined over 2640 random variables. Our results confirm that accurate entropy estimation is achievable wherever reliable probabilistic inference is possible, and that the proposed estimation algorithm yields approximations objectively close to the true entropy values, thereby supporting improved clustering decisions in PGM structuring algorithms.