Bayesian networks: Exact inference via macro-node polytrees
Do Le Minh · Communication in Statistics- Theory and Methods · 2026
.We introduce the Macro-node polytree algorithm (MPA), an efficient framework for exact inference in Bayesian networks. MPA transforms a directed acyclic graph (DAG) into a minimal, family-preserving macro-node polytree (F-polytree). Like the junction tree algorithm (JTA), MPA passes messages between neighboring macro-nodes during the inward and outward phases. However, MPA fundamentally differs by preserving edge directionality and by extensively exploiting distributive laws to enhance computational efficiency. A central innovation of MPA is the notion of evidence cores (ECs), which are the substructures within the F-polytree where inference is concentrated. This structural localization significantly reduces redundant computation during the inward phase and simplifies the outward phase.In contrast to JTA, whose complexity scales with the largest cluster in the entire network, MPA’s complexity depends only on the largest macro-node within the EC. This leads to substantial performance improvements in large networks with localized evidence.