# Fast Parallel Bayesian Network Structure Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 44 references that are in the map.
- First posted on arXiv 8 Dec 2022.

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

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [A fast PC algorithm for high dimensional causal discovery with multi-core PCs](https://mlsanity.com/paper/1502.02454/) (2015)
- [A Discovery Algorithm for Directed Cyclic Graphs](https://mlsanity.com/paper/1302.3599/) (2013)
- [A Comprehensive Scoping Review of Bayesian Networks in Healthcare: Past, Present and Future](https://mlsanity.com/paper/2002.08627/) (2020)
- [Bayesian Network Constraint-Based Structure Learning Algorithms: Parallel and Optimised Implementations in the bnlearn R Package](https://mlsanity.com/paper/1406.7648/) (2014)
- [cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPU](https://mlsanity.com/paper/1812.08491/) (2018)
- [A Branch-and-Bound Algorithm for MDL Learning Bayesian Networks](https://mlsanity.com/paper/1301.3897/) (2013)
- [Learning Bayesian Networks from Incomplete Data with Stochastic Search Algorithms](https://mlsanity.com/paper/1301.6726/) (2013)

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

- [Fast-PGM: Fast Probabilistic Graphical Model Learning and Inference](https://mlsanity.com/paper/2405.15605/) (2024)
- [FastBO: Fast HPO and NAS with Adaptive Fidelity Identification](https://mlsanity.com/paper/2409.00584/) (2024)
- [Preserving Data Privacy in Learning Causal Structure with Fully Homomorphic Encryption](https://mlsanity.com/paper/2606.05129/) (2026)

## Abstract (arXiv)

Bayesian networks (BNs) are a widely used graphical model in machine learning for representing knowledge with uncertainty. The mainstream BN structure learning methods require performing a large number of conditional independence (CI) tests. The learning process is very time-consuming, especially for high-dimensional problems, which hinders the adoption of BNs to more applications. Existing works attempt to accelerate the learning process with parallelism, but face issues including load unbalancing, costly atomic operations and dominant parallel overhead. In this paper, we propose a fast solution named Fast-BNS on multi-core CPUs to enhance the efficiency of the BN structure learning. Fast-BNS is powered by a series of efficiency optimizations including (i) designing a dynamic work pool to monitor the processing of edges and to better schedule the workloads among threads, (ii) grouping the CI tests of the edges with the same endpoints to reduce the number of unnecessary CI tests, (iii) using a cache-friendly data storage to improve the memory efficiency, and (iv) generating the conditioning sets on-the-fly to avoid extra memory consumption. A comprehensive experimental study shows that the sequential version of Fast-BNS is up to 50 times faster than its counterpart, and the parallel version of Fast-BNS achieves 4.8 to 24.5 times speedup over the state-of-the-art multi-threaded solution. Moreover, Fast-BNS has a good scalability to the network size as well as sample size. Fast-BNS source code is freely available at https://github.com/jjiantong/FastBN.