# Turbocharging Treewidth-Bounded Bayesian Network Structure Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2020.

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

- [Learning Bayesian Networks in the Presence of Structural Side Information](https://mlsanity.com/paper/2112.10884/) (2021)
- [Recursive Causal Discovery](https://mlsanity.com/paper/2403.09300/) (2024)
- [On the Parameterized Complexity of Polytree Learning](https://mlsanity.com/paper/2105.09675/) (2021)
- [Propositional Encodings of Acyclicity and Reachability by using Vertex Elimination](https://mlsanity.com/paper/2105.12908/) (2021)
- [SAT-based Circuit Local Improvement](https://mlsanity.com/paper/2102.12579/) (2021)
- [LLM-Guided Graph Generation for Structure-Based Local Improvement Methods](https://mlsanity.com/paper/2608.13333/) (2026)

## Abstract (arXiv)

We present a new approach for learning the structure of a treewidth-bounded Bayesian Network (BN). The key to our approach is applying an exact method (based on MaxSAT) locally, to improve the score of a heuristically computed BN. This approach allows us to scale the power of exact methods -- so far only applicable to BNs with several dozens of random variables -- to large BNs with several thousands of random variables. Our experiments show that our method improves the score of BNs provided by state-of-the-art heuristic methods, often significantly.