Bayesian Network Structure Learning with Integer Programming:
Polytopes, Facets and Complexity (Extended Abstract)
Abstract
Developing accurate algorithms for learning structures of probabilistic graphical models is an important problem within modern AI research. Here
we focus on score-based structure learning for
Bayesian networks as arguably the most central
class of graphical models. A successful generic
approach to optimal Bayesian network structure
learning (BNSL), based on integer programming
(IP), is implemented in the GOBNILP system. Despite the recent algorithmic advances, current understanding of foundational aspects underlying the
IP based approach to BNSL is still somewhat lacking. In this paper, we provide theoretical contributions towards understanding fundamental aspects
of cutting planes and the related separation problem in this context, ranging from NP-hardness results to analysis of polytopes and the related facets
in connection to BNSL