Source-linked AI summary
Bayesian Network Constraint-Based Structure Learning Algorithms: Parallel and Optimised Implementations in the bnlearn R Package
Marco Scutari
TL;DR
Bayesian-network structure learning is computationally difficult, and constraint-based algorithms lack the optimisation advances available to score-based methods. The paper analyses backtracking in bnlearn, proposes a parallel architecture for constraint-based learning, and reports efficient scaling with low overhead on reference and real-world data.
Problem
Bayesian-network structure learning is computationally hard, while constraint-based algorithms have mainly relied on backtracking despite concerns about speed and stability.
Method
The paper analyses backtracking in bnlearn and implements a software architecture and framework that parallelises the shared structure of constraint-based algorithms.
Results
Parallel implementations scale efficiently, perform the same conditional independence tests as the original algorithms, and show low overhead on real-world data, including normalised running times of 0.062 for mice and 0.076 for adenocarcinoma with 20 slave processes.
Takeaways & Limitations
On modern multi-core or multiprocessor hardware, parallel implementations are preferable to backtracking for constraint-based Bayesian-network structure learning.
Takeaways & Limitations
The current implementation may benefit from dynamic task allocation in settings where the underlying Bayesian network is not sparse, such as some gene regulatory networks.
Abstract
from arXiv · showhide
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.
1. Background and notations
Bayesian networks encode conditional dependencies with directed acyclic graphs, and learning their structure is computationally difficult. Constraint-based, score-based, and hybrid methods address this task, while optimisation and parallelisation target scalability.
- Bayesian networks combine random variables with a directed acyclic graph whose nodes and arcs encode the model structure.Each node corresponds to a variable, and directed arcs represent direct stochastic dependencies.
- The global distribution decomposes into local distributions, so many computations use only a node and its parents rather than all variables.The Markov blanket similarly separates a node from the rest of the network and consists of its parents, children, and spouses.
- Structure learning finds a DAG encoding conditional independencies, whereas parameter learning estimates the global distribution after the graph is known.Constraint-based, score-based, and hybrid algorithms have all been used for structure learning.
- Structure learning and inference can be computationally hard, creating particular challenges for high-dimensional genetics and systems-biology applications.Learning BNs from more than a few hundred variables is often impractical without restrictive assumptions about the DAG or local distributions.
- Parallel implementations split learning across multiple cores or processors to use modern hardware more effectively.
- Score-based methods use optimisations such as caching, parallel meta-heuristics, and integer programming, while constraint-based methods have relied mainly on backtracking.The paper argues that backtracking offers modest speed gains and increases variability in learned DAGs, motivating parallel implementations.
2. Constraint-based structure learning and backtracking
Constraint-based structure learning follows a three-phase template for Markov blankets, neighbours, and arc directions, with backtracking reducing redundant tests through symmetry. However, backtracking makes learned structures depend on variable ordering and can increase variability, while offering only modest speed gains over parallel execution.
- Three-phase learning: Constraint-based algorithms can use an optional Markov-blanket phase, followed by neighbour learning and arc-direction learning, to produce a completed partially directed acyclic graph.The template checks Markov-blanket symmetry, learns the DAG skeleton from neighbours, then applies rules for v-structures and remaining arc directions.
- Three-phase learning: The skeleton phase identifies adjacent variable pairs by searching for separating sets and uses Markov blankets to restrict those searches.Neighbourhoods represent parents and children; asymmetries are checked and corrected after neighbourhood learning.
- Backtracking: Backtracking exploits symmetry in Markov blankets and neighbourhoods to skip redundant independence tests and initialise or exclude candidates across nodes.The bnlearn implementation exposes node-level backends such as learn.mb and learn.nbr, while its current approach can initialise candidates without permanently whitelisting them.
- Three-phase learning: The direction phase first identifies v-structures, then recursively orients remaining arcs using directed-path and adjacency rules.Some arcs remain undirected when multiple DAGs represent equivalent decompositions of the global distribution.
- Backtracking: Backtracking makes structure learning depend on variable order, increases learned-structure variability, and provides only a modest speed increase over parallel steps 1–4.In one example, reversing variable order yielded Hamming distances of 0 without backtracking and 10 with it; across simulations, backtracking generally produced larger distances.
- Evaluation: The evaluation focuses on skeleton stability across reversed variable orderings using five reference Bayesian networks and repeated simulations.The comparison isolates the effect of backtracking rather than comparing learned skeletons with each reference network’s true skeleton.
3. A framework for parallel constraint-based learning
The framework parallelises the independent phases of constraint-based Bayesian-network learning while preserving the original algorithm’s tests and results. Benchmarks show low overhead and useful scaling on reference networks and large biological data sets.
- Architecture: Steps 1, 3, and 5 are embarrassingly parallel, while synchronisation is required only in steps 2, 4, and 6.Markov blankets, neighbourhoods, and v-structures can be learned independently; step 6 remains inherently sequential.
- Architecture: The parallel implementation preserves Algorithm 1, performs exactly the same conditional-independence tests, and returns the same Bayesian network.Large batches of tests reduce information exchange and communication overhead between processes.
- Implementation: bnlearn exposes parallel implementations transparently through a cluster object, distributing Markov blankets, neighbourhoods, and v-structures to slave processes.The master process executes the synchronisation steps and distributes the computationally intensive phases.
- Reference-network simulations: Increasing slave processes reduces the number of tests performed by each process, improving overall algorithm performance despite topology-dependent workload differences.With two slaves on ALARM, the test counts were 3637 and 3743, or 49.3% and 50.7% of tests.
- Reference-network simulations: Figure 3 compares normalised and raw skeleton-learning times for four algorithms on the MUNIN and LINK reference networks across backtracking and parallel configurations.The benchmark averages running times over 10 runs using generated data sets of size 20000 and shows diminishing gains as slave counts increase.
- Real-world simulations: Optimised learning is at best competitive with 2 slaves and can degrade performance, whereas real-world SI-HITON-PC reaches normalised times of 0.062 for mice and 0.076 for adenocarcinoma with 20 slaves.The real-world results are close to the theoretical 1/20 = 0.05 and show overhead between 0.02 and 0.08 across 2 to 20 slaves.
4. Discussion and conclusions
The paper presents a bnlearn framework for parallelising constraint-based Bayesian-network structure learning, exploiting shared algorithmic structure while preserving the original conditional-independence tests. Its discussion indicates that parallelism generally offers better speed-quality trade-offs than backtracking, although overhead depends on network complexity and sparsity.
- Parallel architecture: The shared IC-derived layout of constraint-based algorithms enables a common architecture for parallel implementations in bnlearn.Several algorithmic steps can be split into independent parts and executed simultaneously.
- Parallel architecture: Parallel execution preserves the conditional-independence tests performed by the original algorithms, unlike backtracking approaches.This avoids changing the tested evidence while improving sequential performance through parallel hardware.
- Comparison with backtracking: Backtracking can increase variability in learned DAGs, while its speed gains are at most competitive with parallel execution using two slave processes.Because modern computers commonly provide at least two cores, the parallel approach can outperform backtracking.
- Overhead and scope: Sparse Bayesian networks are expected to have low parallel overhead because Markov blankets remain small, but gene regulatory networks may violate this assumption.When blanket sizes are not bounded, replacing static allocation or changing the parallel backend may provide substantial improvements.
- Overhead and scope: The number of conditional-independence tests typically scales quadratically with variables, whereas each test is typically linear in sample size.Data copying occurs only once, so sample-size changes are expected to have little effect on parallel-learning overhead.
- Overhead and scope: Large networks can create significant overhead when Markov-blanket and neighbourhood sizes vary substantially across nodes.Network topology, rather than variable count alone, determines complexity; sparsity can keep these sets small and comparable.
Journal of Statistical Software http://www.jstatsoft.org/
The supplied publication metadata identifies the Journal of Statistical Software and gives placeholder volume, issue, submission, acceptance, and publication fields.
- Publication metadata: The paper is associated with the Journal of Statistical Software website.The supplied metadata includes http://www.jstatsoft.org/.
- Publication metadata: The volume, issue, submission date, acceptance date, and publication date remain placeholder fields.The metadata uses VV, II, yyyy-mm-dd, and MMMMMM YYYY placeholders.