# Effective and efficient structure learning with pruning and model averaging strategies

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 30 references that are in the map.
- First posted on arXiv 1 Dec 2021.

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

- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [Learning Equivalence Classes of Bayesian Networks Structures](https://mlsanity.com/paper/1302.3566/) (2013)
- [Large-scale empirical validation of Bayesian Network structure learning algorithms with noisy data](https://mlsanity.com/paper/2005.09020/) (2020)
- [Properties of Bayesian Belief Network Learning Algorithms](https://mlsanity.com/paper/1302.6792/) (2013)
- [Evaluating structure learning algorithms with a balanced scoring function](https://mlsanity.com/paper/1905.12666/) (2019)
- [Learning Bayesian Networks that enable full propagation of evidence](https://mlsanity.com/paper/2004.04571/) (2020)
- [Approximate learning of high dimensional Bayesian network structures via pruning of Candidate Parent Sets](https://mlsanity.com/paper/2006.04753/) (2020)

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

- [Open problems in causal structure learning: A case study of COVID-19 in the UK](https://mlsanity.com/paper/2305.03859/) (2023)
- [Robust Causal Discovery under Imperfect Structural Constraints](https://mlsanity.com/paper/2511.06790/) (2025)
- [Dynamic Expert-Guided Model Averaging for Causal Discovery](https://mlsanity.com/paper/2601.16715/) (2026)
- [Tuning structure learning algorithms with out-of-sample and resampling strategies](https://mlsanity.com/paper/2306.13932/) (2023)
- [Investigating the validity of structure learning algorithms in identifying risk factors for intervention in patients with diabetes](https://mlsanity.com/paper/2403.14327/) (2024)
- [Integrating Probabilistic Trees and Causal Networks for Clinical and Epidemiological Data](https://mlsanity.com/paper/2501.15973/) (2025)
- [Stable Causal Discovery via Directed Acyclic Graph Aggregation](https://mlsanity.com/paper/2605.18633/) (2026)

## Abstract (arXiv)

Learning the structure of a Bayesian Network (BN) with score-based solutions involves exploring the search space of possible graphs and moving towards the graph that maximises a given objective function. Some algorithms offer exact solutions that guarantee to return the graph with the highest objective score, while others offer approximate solutions in exchange for reduced computational complexity. This paper describes an approximate BN structure learning algorithm, which we call Model Averaging Hill-Climbing (MAHC), that combines two novel strategies with hill-climbing search. The algorithm starts by pruning the search space of graphs, where the pruning strategy can be viewed as an aggressive version of the pruning strategies that are typically applied to combinatorial optimisation structure learning problems. It then performs model averaging in the hill-climbing search process and moves to the neighbouring graph that maximises the objective function, on average, for that neighbouring graph and over all its valid neighbouring graphs. Comparisons with other algorithms spanning different classes of learning suggest that the combination of aggressive pruning with model averaging is both effective and efficient, particularly in the presence of data noise.