An Experimental Comparison of Hybrid Algorithms for Bayesian Network Structure Learning

Maxime Gasse, Alex Aussem, Haytham Elghazel

Introduction

Learning the structure of a Bayesian Network (BN)—a directed acyclic graph representing conditional dependencies between variables—is a notoriously difficult combinatorial problem. Historically, two main approaches have dominated the field: Constraint-Based (CB) methods and Search-and-Score (SS) methods. CB methods are fast and scalable but brittle, as early errors can cascade. SS methods are highly accurate but computationally intractable for large networks.

Hybrid methods, such as the popular Max-Min Hill-Climbing (MMHC) algorithm, attempt to combine the strengths of both. They typically use a fast CB method to build an undirected "skeleton" to restrict the search space, followed by an SS method to orient the edges. However, a critical flaw exists: if the CB phase misses a true edge (a false negative), the SS phase cannot recover it. This paper introduces Hybrid HPC (H2PC), a novel hybrid algorithm designed to minimize these false-negative errors during the skeleton-building phase to improve overall structural accuracy.

Methodology

The H2PC algorithm shares the same Search-and-Score phase as MMHC—a greedy hill-climbing search with a TABU list—to ensure a fair comparison. The primary innovation lies in the initial skeleton-learning phase. Instead of the MMPC algorithm used in MMHC, H2PC utilizes a subroutine called Hybrid Parents and Children (HPC).

HPC acts as an ensemble method combining incremental and divide-and-conquer constraint-based techniques. It aggressively filters variables to handle high-dimensional data and performs a "decentralized search" by examining the neighborhoods of a target node's neighbors. This approach is specifically designed to catch complex dependencies that standard methods might miss, prioritizing higher recall at the cost of slightly more computational effort.

Experimental Setup

The performance of H2PC was evaluated against MMHC using eight well-known benchmark Bayesian networks from the bnlearn repository. These networks vary significantly in size and complexity, providing a robust testbed for the algorithms.

Table 1: Characteristics of the benchmark Bayesian networks used for evaluation.

To test the algorithms across different data regimes, datasets were generated with sample sizes ranging from 50 to 5000 for each network listed in Table 1.

Results and Discussion

The experimental results highlight several key advantages of the H2PC approach:

  • Superior Skeleton Quality: HPC consistently increased edge recall and reduced false negatives compared to MMPC. It reduced the Euclidean distance from perfect precision/recall by approximately 30% for larger sample sizes (500-5000) while maintaining a negligible increase in the false-positive rate.
  • Structural Accuracy: H2PC outperformed MMHC in Structural Hamming Distance (SHD), indicating that the final graphs were significantly closer to the ground-truth networks.
  • Generalization and Goodness-of-Fit: H2PC achieved better BDeu and BIC scores on both training and holdout test sets, demonstrating superior generalization capabilities.
  • Computational Trade-off: The primary trade-off for this increased accuracy is speed. H2PC was found to be roughly 8 times slower than MMHC at 5000 samples. However, the authors argue that the gain in structural accuracy justifies the additional computational cost.

The core insight is that prioritizing recall over precision in the initial phase is beneficial. While the SS phase is effective at filtering out false positives, it cannot compensate for edges missed during skeleton construction.

Conclusion

H2PC represents a significant advancement in hybrid BN structure learning by demonstrating that a more thorough constraint-based search pays off in final model quality. Future work will focus on improving computational efficiency through global optimizations, such as dependency caching, which could reduce costs by an estimated 30%. Additionally, exploring alternative conditional independence tests may further enhance performance on diverse data types.

Summary updated

BibTeX
@inproceedings{gasse2012experimental,
  author = {Maxime Gasse and Alex Aussem and Haytham Elghazel},
  title = {{An Experimental Comparison of Hybrid Algorithms for Bayesian Network Structure Learning}},
  booktitle = {ECML/PKDD},
  year = {2012},
  url = {https://openreview.net/forum?id=Hu_ENfvxeZq},
}
Figure