Tightening Bounds for Bayesian Network Structure Learning

Xiannian Fan, Changhe Yuan, Brandon M. MaloneAAAI 2014 · DOI

Abstract

Learning the optimal structure of a Bayesian network (BN) from data is a fundamental challenge in machine learning, characterized by an exponentially growing search space. This paper introduces novel techniques to significantly accelerate the search process by "tightening" the mathematical bounds used in Breadth-First Branch and Bound (BFBnB) algorithms. By implementing sophisticated variable grouping strategies for lower bounds and anytime search for upper bounds, the authors achieve speedups of two to three orders of magnitude, effectively solving complex models that were previously computationally intractable.

Introduction

Learning the optimal structure of a Bayesian Network is a classic "needle in a haystack" problem. As the number of variables increases, the number of possible network structures grows exponentially, making the search for the structure that best fits the data an NP-hard problem. State-of-the-art exact algorithms typically employ Breadth-First Branch and Bound (BFBnB), which treats the problem as a shortest-path search through a massive graph of possible variable sets.

The search space for Bayesian Network Structure Learning represented as a lattice of variable subsets.

To prune this search space effectively, BFBnB relies on two critical "guards":

  1. Lower Bound ($h$-cost): An optimistic estimate of the remaining cost to reach the goal.
  2. Upper Bound ($ub$): The cost of the best solution found so far.

If the sum of a path's current cost and its lower bound exceeds the upper bound, the path is discarded. However, "loose" bounds—where the lower bound is too pessimistic or the upper bound is too high—hinder pruning, leading to memory exhaustion or excessive computation time.

Methods: Tightening the Pruning Vise

The authors propose tightening both ends of this pruning mechanism to improve efficiency.

1. Tightening Lower Bounds via Informed Variable Grouping

Lower bounds are often calculated using pattern databases that relax network rules (e.g., allowing cycles between groups of variables). Traditional methods grouped variables naively. This paper introduces three "informed" grouping strategies:

  • Family Grouping (FG): Uses statistical independence tests to group variables likely to have parent-child relationships.
  • Parents Grouping (PG): Groups variables based on their optimal parent sets in a simplified version of the problem.
  • Topology Grouping (TG): Utilizes the structure of a sub-optimal network to determine variable ordering.

Instead of a simple greedy hill-climbing search, the authors utilize Anytime Window A (AWA). AWA* quickly identifies a good initial solution and iteratively improves it. A lower initial upper bound allows for more immediate and aggressive pruning of the search space.

Key Results and Insights

The researchers evaluated these methods on standard benchmark datasets, ranging from small (Parkinsons, 23 variables) to large (Spectf, 45 variables). In BNSL, the number of variables ($n$) is the primary driver of complexity.

The combination of AWA and informed grouping (particularly FG and PG) resulted in massive speedups of 100x to 1,000x* compared to the original BFBnB algorithm. On the Steel Plates dataset, the number of expanded nodes was reduced from 246 million to just 2 million.

Performance comparison of different grouping strategies (SG, FG, PG, TG) across the Parkinsons and SteelPlates datasets.

A key insight is the cooperative effect: tightening both bounds simultaneously provides a synergistic boost. For instance, on the WDBC dataset, better upper bounds alone doubled the speed, but combined with better lower bounds, the search became over 10 times faster. Furthermore, the most effective strategies (FG and PG) work by keeping highly correlated variables in the same group, forcing the lower bound to account for expensive dependencies.

Conclusion

By tightening the mathematical bounds in BFBnB, this work successfully "breaks the memory wall" for several large datasets like Alarm, Bands, and Spectf, which were previously unsolvable due to memory constraints. While static grouping methods proved highly successful, future work will focus on refining dynamic approaches and integrating expert domain knowledge to further scale exact search methods for even larger "big data" scenarios.

Summary updated

BibTeX
@inproceedings{fan2014tightening,
  author = {Xiannian Fan and Changhe Yuan and Brandon M. Malone},
  title = {{Tightening Bounds for Bayesian Network Structure Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9061},
}
Figure