# Exact discovery is polynomial for certain sparse causal Bayesian networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 21 Jun 2024.

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

- [Parameter Priors for Directed Acyclic Graphical Models and the Characterization of Several Probability Distributions](https://mlsanity.com/paper/1301.6697/) (2013)
- [Addendum on the scoring of Gaussian directed acyclic graphical models](https://mlsanity.com/paper/1402.6863/) (2014)
- [Partition MCMC for inference on acyclic digraphs](https://mlsanity.com/paper/1504.05006/) (2015)
- [Efficient Sampling and Structure Learning of Bayesian Networks](https://mlsanity.com/paper/1803.07859/) (2018)
- [Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm](https://mlsanity.com/paper/1301.6696/) (2013)
- [Learning Bayesian Networks: A Unification for Discrete and Gaussian Domains](https://mlsanity.com/paper/1302.4957/) (2013)
- [Bayesian structure learning and sampling of Bayesian networks with the R package BiDAG](https://mlsanity.com/paper/2105.00488/) (2021)
- [Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis](https://mlsanity.com/paper/2004.14724/) (2020)
- [Benchpress: A Scalable and Versatile Workflow for Benchmarking Structure Learning Algorithms](https://mlsanity.com/paper/2107.03863/) (2021)
- [Novel Ordering-based Approaches for Causal Structure Learning in the Presence of Unobserved Variables](https://mlsanity.com/paper/2208.06935/) (2022)
- [Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets, and Complexity](https://mlsanity.com/paper/1605.04071/) (2016)
- [Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming](https://mlsanity.com/paper/2106.12269/) (2021)

## Abstract (arXiv)

Causal Bayesian networks are widely used tools for summarising the dependencies between variables and elucidating their putative causal relationships. By restricting the search to trees, for example, learning the optimum from data is polynomial, but this does not guarantee finding the optimal network overall. Without similar restrictions, exact discovery of the optimum is computationally hard in general and no polynomial results are known. The current state-of-the-art approaches are integer linear programming over the underlying space of directed acyclic graphs, dynamic programming and shortest-path searches over the space of topological orders, and constraint programming combining both. For dynamic programming over orders, the computational complexity is known to be exponential base 2 in the number of variables in the network. We demonstrate how to use properties of Bayesian networks to prune the search space and lower the computational cost, while still guaranteeing exact discovery of the provably optimal network. We also include new path-search and divide-and-conquer criteria. Without a priori constraining the search to certain types of networks, the algorithm completes in quadratic time when the optimum is a matching, and in polynomial time when the optimum belongs to any network class with logarithmically-bound largest connected components. In simulation studies we observe the polynomial dependence for sparse networks and that, beyond some critical value, the logarithm of the base grows with the network density. Our approach then out-competes the state-of-the-art at lower densities. These results therefore pave the way for faster exact causal discovery in larger and sparser networks.