Abstract
Learning the structure of Bayesian networks (BNs) is a fundamental problem in machine learning, yet it remains computationally daunting for high-dimensional data. This paper introduces a hybrid Markov Chain Monte Carlo (MCMC) framework that bridges the gap between fast constraint-based pruning and accurate score-based search. Through innovations such as "summed score tables" and iterative search space expansion, the authors demonstrate efficient, unbiased sampling of networks with hundreds of nodes, a significant advancement over previous state-of-the-art methods.
Introduction
Bayesian networks are essential for representing complex probabilistic dependencies and causal relationships. However, identifying the underlying Directed Acyclic Graph (DAG) structure from data is NP-hard. The search space for DAGs grows super-exponentially; for instance, a network with 21 nodes has more possible configurations than atoms in the observable universe.
Existing methodologies typically fall into two categories: constraint-based methods, which are fast but prone to errors, and score-based MCMC methods, which provide full posterior distributions but lack scalability. This work proposes a hybrid approach, implemented in the BiDAG R package, to achieve both scalability and Bayesian rigor.
Methodology
The core of the proposed framework lies in several algorithmic innovations designed to optimize the search process without sacrificing accuracy.
Restricted Search Space and Iterative Expansion
The algorithm initially restricts the search space using a skeleton generated by a constraint-based method (e.g., the PC algorithm). To prevent the propagation of errors from this initial pruning, the framework employs an iterative expansion mechanism. This "safety valve" allows the MCMC search to "soften" the space and discover true edges that were initially excluded.
Summed Score Tables
To accelerate the MCMC steps, the authors introduce "summed score tables." By precomputing partial sums of parent set scores using Hasse power set representations, the complexity of scoring during MCMC is reduced from an expensive calculation to a simple $O(1)$ or $O(n)$ lookup.
Order and Partition MCMC
The framework supports both Order and Partition MCMC. While Order MCMC is highly efficient, it can be biased because multiple topological orders can represent the same DAG. Partition MCMC addresses this by providing a unique representation for each DAG, ensuring unbiased sampling.
Experimental Evaluation
The authors evaluated the performance of BiDAG using synthetic datasets (Erdős-Rényi and Barabási-Albert models) with node counts ranging from 20 to 200. Additionally, the 223-node ANDES medical diagnostic network was used to benchmark performance on large-scale, realistic structures.
Results
- Accuracy: BiDAG consistently outperformed standard algorithms like Greedy Equivalence Search (GES) and the PC algorithm in skeleton recovery, particularly as network size and density increased.
- Scalability: The algorithm achieved near-perfect recovery for 200-node networks within a few hours. For smaller networks (20 nodes), results were obtained in seconds.
- Convergence: MCMC chains exhibited excellent convergence, scaling roughly as $O(n^2 \log n)$.
- Real-world Application: On the ANDES network, the method identified higher-scoring structures with significantly fewer false positives than competing categorical learners.
Conclusion
The hybrid MCMC framework presented in this paper offers a powerful tool for high-dimensional Bayesian network learning. By combining precomputation with iterative search space refinement, it overcomes the traditional trade-off between speed and accuracy. Future work will focus on addressing the exponential bottleneck of precomputation in extremely dense networks and extending the method to even larger systems.
Summary updated