# Efficient Learning of Bounded-Treewidth Bayesian Networks from Complete and Incomplete Data Sets

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2018.

## Built on by (most cited first, 2 of 2)

- [KG-SoftMAP: Soft Knowledge-Graph Priors for Bayesian Network Structure Learning from Sparse Discrete Data](https://mlsanity.com/paper/2606.10358/) (2026)
- [High-Dimensional Inference in Bayesian Networks](https://mlsanity.com/paper/2112.09217/) (2021)

## Abstract (arXiv)

Learning a Bayesian networks with bounded treewidth is important for reducing the complexity of the inferences. We present a novel anytime algorithm (k-MAX) method for this task, which scales up to thousands of variables. Through extensive experiments we show that it consistently yields higher-scoring structures than its competitors on complete data sets. We then consider the problem of structure learning from incomplete data sets. This can be addressed by structural EM, which however is computationally very demanding. We thus adopt the novel k-MAX algorithm in the maximization step of structural EM, obtaining an efficient computation of the expected sufficient statistics. We test the resulting structural EM method on the task of imputing missing data, comparing it against the state-of-the-art approach based on random forests. Our approach achieves the same imputation accuracy of the competitors, but in about one tenth of the time. Furthermore we show that it has worst-case complexity linear in the input size, and that it is easily parallelizable.