# SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2013.

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

- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [A Fast Non-parametric Approach for Local Causal Structure Learning](https://mlsanity.com/paper/2111.14969/) (2021)
- [On the Number of Conditional Independence Tests in Constraint-based Causal Discovery](https://mlsanity.com/paper/2603.21844/) (2026)
- [Estimating large causal polytrees from small samples](https://mlsanity.com/paper/2209.07028/) (2022)
- [Membership Testing in Markov Equivalence Classes via Independence Query Oracles](https://mlsanity.com/paper/2403.05759/) (2024)

## Abstract (arXiv)

We give a new consistent scoring function for structure learning of Bayesian networks. In contrast to traditional approaches to scorebased structure learning, such as BDeu or MDL, the complexity penalty that we propose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot exist. What really distinguishes this new scoring function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data increases. We prove a polynomial sample complexity result, showing that maximizing this score is guaranteed to correctly learn a structure with no false edges and a distribution close to the generating distribution, whenever there exists a Bayesian network which is a perfect map for the data generating distribution. Although the new score can be used with any search algorithm, we give empirical results showing that it is particularly effective when used together with a linear programming relaxation approach to Bayesian network structure learning.