@inproceedings{MaloneKJKM:AAAI2014, title = {Predicting the Hardness of Learning {B}ayesian Networks}, author = {Brandon Malone and Kustaa Kangas and Matti J\"arvisalo and Mikko Koivisto and Petri Myllym\"aki}, editor = {Carla E. Brodley and Peter Stone}, booktitle = {Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014)}, pages = {2460--2466}, publisher = {AAAI Press}, year = {2014}, } Abstract: There are various algorithms for finding a Bayesian network structure (BNS) that is optimal with respect to a given scoring function. No single algorithm dominates the others in speed, and, given a problem instance, it is a priori unclear which algorithm will perform best and how fast it will solve the problem. Estimating the runtimes directly is extremely difficult as they are complicated functions of the instance. The main contribution of this paper is characterization of the empirical hardness of an instance for a given algorithm based on a novel collection of non-trivial, yet efficiently computable features. Our empirical results, based on the largest evaluation of stateof- the-art BNS learning algorithms to date, demonstrate that we can predict the runtimes to a reasonable degree of accuracy, and effectively select algorithms that perform well on a particular instance. Moreover, we also show how the results can be utilized in building a portfolio algorithm that combines several individual algorithms in an almost optimal manner.