# Bayesian Network Constraint-Based Structure Learning Algorithms: Parallel and Optimised Implementations in the bnlearn R Package

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2014.

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

- [D'ya like DAGs? A Survey on Structure Learning and Causal Discovery](https://mlsanity.com/paper/2103.02582/) (2021)
- [A Survey on Causal Discovery: Theory and Practice](https://mlsanity.com/paper/2305.10032/) (2023)
- [Integrating Large Language Model for Improved Causal Discovery](https://mlsanity.com/paper/2306.16902/) (2023)
- [Learning Bayesian Networks in the Presence of Structural Side Information](https://mlsanity.com/paper/2112.10884/) (2021)
- [Partitioned hybrid learning of Bayesian network structures](https://mlsanity.com/paper/2103.12188/) (2021)
- [Scalable Causal Domain Adaptation](https://mlsanity.com/paper/2103.00139/) (2021)
- [Fast Parallel Bayesian Network Structure Learning](https://mlsanity.com/paper/2212.04259/) (2022)
- [Benchmarking Bayesian Causal Discovery Methods for Downstream Treatment Effect Estimation](https://mlsanity.com/paper/2307.04988/) (2023)
- [Explaining and visualizing black-box models through counterfactual paths](https://mlsanity.com/paper/2307.07764/) (2023)
- [Fast-PGM: Fast Probabilistic Graphical Model Learning and Inference](https://mlsanity.com/paper/2405.15605/) (2024)
- [Framework for inferring empirical causal graphs from binary data to support multidimensional poverty analysis](https://mlsanity.com/paper/2205.06131/) (2022)
- [BigBraveBN: algorithm of structural learning for bayesian networks with a large number of nodes](https://mlsanity.com/paper/2208.10312/) (2022)
- [Improving the Efficiency of the PC Algorithm by Using Model-Based Conditional Independence Tests](https://mlsanity.com/paper/2211.06536/) (2022)
- [Linking Model Intervention to Causal Interpretation in Model Explanation](https://mlsanity.com/paper/2410.15648/) (2024)
- [KG-SoftMAP: Soft Knowledge-Graph Priors for Bayesian Network Structure Learning from Sparse Discrete Data](https://mlsanity.com/paper/2606.10358/) (2026)
- [WiseR: An end-to-end structure learning and deployment framework for causal graphical models](https://mlsanity.com/paper/2108.07046/) (2021)
- [Generating Bayesian Network Models from Data Using Tsetlin Machines](https://mlsanity.com/paper/2305.10538/) (2023)
- [Causal Discovery on Dependent Binary Data](https://mlsanity.com/paper/2412.20289/) (2024)
- [Preserving Data Privacy in Learning Causal Structure with Fully Homomorphic Encryption](https://mlsanity.com/paper/2606.05129/) (2026)

## Abstract (arXiv)

It is well known in the literature that the problem of learning the structure of Bayesian networks is very hard to tackle: its computational complexity is super-exponential in the number of nodes in the worst case and polynomial in most real-world scenarios. Efficient implementations of score-based structure learning benefit from past and current research in optimisation theory, which can be adapted to the task by using the network score as the objective function to maximise. This is not true for approaches based on conditional independence tests, called constraint-based learning algorithms. The only optimisation in widespread use, backtracking, leverages the symmetries implied by the definitions of neighbourhood and Markov blanket. In this paper we illustrate how backtracking is implemented in recent versions of the bnlearn R package, and how it degrades the stability of Bayesian network structure learning for little gain in terms of speed. As an alternative, we describe a software architecture and framework that can be used to parallelise constraint-based structure learning algorithms (also implemented in bnlearn) and we demonstrate its performance using four reference networks and two real-world data sets from genetics and systems biology. We show that on modern multi-core or multiprocessor hardware parallel implementations are preferable over backtracking, which was developed when single-processor machines were the norm.