# Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets, and Complexity

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2016.

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

- [BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery](https://mlsanity.com/paper/2112.02761/) (2021)
- [Benchmarking and Explaining Large Language Model-based Code Generation: A Causality-Centric Approach](https://mlsanity.com/paper/2310.06680/) (2023)
- [DCILP: A Distributed Approach for Large-Scale Causal Structure Learning](https://mlsanity.com/paper/2406.10481/) (2024)
- [Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming](https://mlsanity.com/paper/2106.12269/) (2021)
- [Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models](https://mlsanity.com/paper/2404.12592/) (2024)
- [Enabling Causal Discovery in Post-Nonlinear Models with Normalizing Flows](https://mlsanity.com/paper/2407.04980/) (2024)
- [Probabilistic Multi-Dimensional Classification](https://mlsanity.com/paper/2306.06517/) (2023)
- [Exact discovery is polynomial for certain sparse causal Bayesian networks](https://mlsanity.com/paper/2406.15012/) (2024)
- [Empirical Bayes for Dynamic Bayesian Networks Using Generalized Variational Inference](https://mlsanity.com/paper/2406.17831/) (2024)

## Abstract (arXiv)

The challenging task of learning structures of probabilistic graphical models is an important problem within modern AI research. Recent years have witnessed several major algorithmic advances in structure learning for Bayesian networks---arguably the most central class of graphical models---especially in what is known as the score-based setting. A successful generic approach to optimal Bayesian network structure learning (BNSL), based on integer programming (IP), is implemented in the GOBNILP system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the IP based approach to BNSL is still somewhat lacking. Understanding fundamental aspects of cutting planes and the related separation problem( is important not only from a purely theoretical perspective, but also since it holds out the promise of further improving the efficiency of state-of-the-art approaches to solving BNSL exactly. In this paper, we make several theoretical contributions towards these goals: (i) we study the computational complexity of the separation problem, proving that the problem is NP-hard; (ii) we formalise and analyse the relationship between three key polytopes underlying the IP-based approach to BNSL; (iii) we study the facets of the three polytopes both from the theoretical and practical perspective, providing, via exhaustive computation, a complete enumeration of facets for low-dimensional family-variable polytopes; and, furthermore, (iv) we establish a tight connection of the BNSL problem to the acyclic subgraph problem.