# Optimal Clustering with Dependent Costs in Bayesian Networks

arXiv: https://arxiv.org/abs/2308.03970 · HTML: https://mlsanity.com/paper/2308.03970/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 49 references that are in the map.
- First posted on arXiv 8 Aug 2023.

## Builds on (most cited first, 7 of 7)

- [Recent Advances in Graph Partitioning](https://mlsanity.com/paper/1311.3144/) (2013)
- [Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm](https://mlsanity.com/paper/1301.6696/) (2013)
- [Learning big Gaussian Bayesian networks: partition, estimation, and fusion](https://mlsanity.com/paper/1904.10900/) (2019)
- [Join-Graph Propagation Algorithms](https://mlsanity.com/paper/1401.3489/) (2014)
- [Object-Oriented Bayesian Networks](https://mlsanity.com/paper/1302.1554/) (2013)
- [Exploiting Causality for Selective Belief Filtering in Dynamic Bayesian Networks (Extended Abstract)](https://mlsanity.com/paper/1907.05850/) (2019)
- [Partitioned hybrid learning of Bayesian network structures](https://mlsanity.com/paper/2103.12188/) (2021)

## Abstract (arXiv)

Background: 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. It typically involves partitioning the underlying Directed Acyclic Graph (DAG) into cliques or optimising for some cost or criteria. Objectives: We focus on a critical but understudied aspect of optimal clustering involving cost dependency. This is where inference outcomes and hence clustering costs depend on both nodes within a cluster and the mapping of clusters that are connected by at least one arc. Methods: We propose a novel algorithm called Dependent Cluster MAPping (DCMAP) which can, given an arbitrary, positive cost function, iteratively and rapidly find near-optimal, then optimal cluster mappings. Results: DCMAP is shown analytically to be optimal in terms of finding all of the least cost cluster mapping solutions and with no more iterations than an equally informed algorithm. Demonstrated on a complex systems seagrass DBN with 9.91×109 and 1.51×1021 possible cluster mappings for 25 and 50 node configurations, it took 856 and 1569 iterations on average to find the first optimal solution, respectively. Conclusions: The effectiveness of DCMAP enables future research in BN learning using optimisation, such as through enhancing computational efficiency or minimising entropy for learning. This is critically important as computation of marginal distributions or updating model parameters is NP-hard.