Efficient Structure Learning and Sampling of Bayesian Networks.

Jack Kuipers, Polina Suter, Giusi Moffa

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.

Comparison of Bayesian network representations: (a) Directed Acyclic Graph (DAG), (b) topological order, and (c) node partition.

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

Abstract

Bayesian networks are probabilistic graphical models widely employed to understand dependencies in high dimensional data, and even to facilitate causal discovery. Learning the underlying network structure, which is encoded as a directed acyclic graph (DAG) is highly challenging mainly due to the vast number of possible networks. Efforts have focussed on two fronts: constraint based methods that perform conditional independence tests to exclude edges and score and search approaches which explore the DAG space with greedy or MCMC schemes. Here we synthesise these two fields in a novel hybrid method which reduces the complexity of MCMC approaches to that of a constraint based method. Individual steps in the MCMC scheme only require simple table lookups so that very long chains can be efficiently obtained. Furthermore, the scheme includes an iterative procedure to correct for errors from the conditional independence tests. The algorithm not only offers markedly superior performance to alternatives, but DAGs can also be sampled from the posterior distribution enabling full Bayesian modelling averaging for much larger Bayesian networks.
BibTeX
@article{kuipers2022efficient,
  author = {Jack Kuipers and Polina Suter and Giusi Moffa},
  title = {{Efficient Structure Learning and Sampling of Bayesian Networks.}},
  journal = {J. Comput. Graph. Stat.},
  year = {2022},
  doi = {10.1080/10618600.2021.2020127},
}
Figure