  Bayesian network structure learning is often performed in a Bayesian setting,
evaluating candidate structures using their posterior probabilities for a given
data set. Score-based algorithms then use those posterior probabilities as an
objective function and return the maximum a posteriori network as the learned
model. For discrete Bayesian networks, the canonical choice for a posterior
score is the Bayesian Dirichlet equivalent uniform (BDeu) marginal likelihood
with a uniform (U) graph prior, which assumes a uniform prior both on the
network structures and on the parameters of the networks. In this paper, we
investigate the problems arising from these assumptions, focusing on those
caused by small sample sizes and sparse data. We then propose an alternative
posterior score: the Bayesian Dirichlet sparse (BDs) marginal likelihood with a
marginal uniform (MU) graph prior. Like U+BDeu, MU+BDs does not require any
prior information on the probabilistic structure of the data and can be used as
a replacement noninformative score. We study its theoretical properties and we
evaluate its performance in an extensive simulation study, showing that MU+BDs
is both more accurate than U+BDeu in learning the structure of the network and
competitive in predicting power, while not being computationally more complex
to estimate.
