On Pruning for Score-Based Bayesian Network Structure Learning

Many algorithms for score-based Bayesian net-
work structure learning (BNSL), in particular
exact ones, take as input a collection of po-
tentially optimal parent sets for each variable
in the data. Constructing such collections
naively is computationally intensive since the
number of parent sets grows exponentially
with the number of variables. Thus, pruning
techniques are not only desirable but essen-
tial. While good pruning rules exist for the
Bayesian Information Criterion (BIC), current
results for the Bayesian Dirichlet equivalent
uniform (BDeu) score reduce the search space
very modestly, hampering the use of the (often
preferred) BDeu. We derive new non-trivial
theoretical upper bounds for the BDeu score
that considerably improve on the state-of-the-
art. Since the new bounds are mathematically
proven to be tighter than previous ones and
at little extra computational cost, they are a
promising addition to BNSL methods.