Optimal Clustering with Dependent Costs in Bayesian Networks

Clustering of nodes in Bayesian Networks (BNs) and related graphical models such as Dynamic BNs (DBNs) has been demonstrated to enhance computational efficiency and improve model learning. Typically, it involves the partitioning of the underlying Directed Acyclic Graph (DAG) into cliques, or optimising for some cost or criteria. Computational cost is important since BN and DBN inference, such as estimating marginal distributions given evidence or updating model parameters, is NP-hard. The challenge is exacerbated by cost dependency, where inference outcomes and hence clustering cost depends on both nodes within a cluster and the mapping of clusters that are connected by at least one arc. We propose an algorithm called Dependent Cluster MAPping (DCMAP) which is shown analytically, given an arbitrarily defined, positive cost function, to find all optimal cluster mappings, and do so with no more iterations than an equally informed algorithm. DCMAP is demonstrated on a complex systems seagrass DBN, which has 25 nodes per time-slice, and captures biological, ecological and environmental dynamics and their interactions to predict the impact of dredging stressors on resilience and their cumulative effects over time. The algorithm is employed to find clusters to optimise the computational efficiency of inferring marginal distributions given evidence. For the 25 (one time-slice) and 50-node (two time-slices) DBN, the search space size was $9.91\times10^9$ and $1.51\times10^{21}$ possible cluster mappings, respectively, but the first optimal solution was found at iteration number 856 (95\% CI 852,866), and 1569 (1566,1581) with a cost that was 4\% and 0.2\% of the naive heuristic cost, respectively. Through optimal clustering, DCMAP opens up opportunities for further research beyond improving computational efficiency, such as using clustering to minimise entropy in BN learning.