# Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 32 references that are in the map.
- First posted on arXiv 23 Jun 2021.

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

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [A Survey on Computational Propaganda Detection](https://mlsanity.com/paper/2007.08024/) (2020)
- [Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets, and Complexity](https://mlsanity.com/paper/1605.04071/) (2016)
- [Entropy-based Pruning for Learning Bayesian Networks using BIC](https://mlsanity.com/paper/1707.06194/) (2017)
- [Using New Data to Refine a Bayesian Network](https://mlsanity.com/paper/1302.6826/) (2013)

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

- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [Causal Structure Learning Supervised by Large Language Model](https://mlsanity.com/paper/2311.11689/) (2023)
- [Machine learning interatomic potential can infer electrical response](https://mlsanity.com/paper/2504.05169/) (2025)
- [Learning the Finer Things: Bayesian Structure Learning at the Instantiation Level](https://mlsanity.com/paper/2303.04339/) (2023)
- [Exact discovery is polynomial for certain sparse causal Bayesian networks](https://mlsanity.com/paper/2406.15012/) (2024)

## Abstract (arXiv)

Bayesian networks are probabilistic graphical models with a wide range of application areas including gene regulatory networks inference, risk analysis and image processing. Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task with a superexponential search space of directed acyclic graphs. In this work, we propose a new polynomial time algorithm for discovering a subset of all possible cluster cuts, a greedy algorithm for approximately solving the resulting linear program, and a generalised arc consistency algorithm for the acyclicity constraint. We embed these in the constraint programmingbased branch-and-bound solver CPBayes and show that, despite being suboptimal, they improve performance by orders of magnitude. The resulting solver also compares favourably with GOBNILP, a state-of-the-art solver for the BNSL problem which solves an NP-hard problem to discover each cut and solves the linear program exactly.