Finding All Bayesian Network Structures within a Factor of Optimal

A Bayesian network is a widely used probabilistic graphical
model with applications in knowledge discovery and predic-
tion. Learning a Bayesian network (BN) from data can be cast
as an optimization problem using the well-known score-and-
search approach. However, selecting a single model (i.e., the
best scoring BN) can be misleading or may not achieve the
best possible accuracy. An alternative to committing to a sin-
gle model is to perform some form of Bayesian or frequentist
model averaging, where the space of possible BNs is sam-
pled or enumerated in some fashion. Unfortunately, existing
approaches for model averaging either severely restrict the
structure of the Bayesian network or have only been shown
to scale to networks with fewer than 30 random variables. In
this paper, we propose a novel approach to model averaging
inspired by performance guarantees in approximation algo-
rithms. Our approach has two primary advantages. First, our
approach only considers credible models in that they are op-
timal or near-optimal in score. Second, our approach is more
efficient and scales to significantly larger Bayesian networks
than existing approaches.