Turbocharging Treewidth-Bounded Bayesian Network Structure Learning

Bayesian network structure learning is the notoriously difficult problem of discovering a Bayesian network (BN) that optimally represents a given set of training data [4]. Since the exact inference on a BN is exponential in the BN's treewidth [14], one is particularly interested in learning BNs of bounded treewidth. However, learning a BN of bounded treewidth that optimally fits the data (i.e., with the largest possible score) is, in turn, an NPhard task [13]. This predicament caused the research on treewidth-bounded BN structure learning to split into two branches: 1. Heuristic Learning (see, e.g., [5, 17, 23, 24]), which is scalable to large BNs with thousands of nodes (but with a score that can be far from optimal), and 2. Exact Learning (see, e.g., [2, 13, 19]), which learns optimal BNs (but is scalable only to a few dozen nodes). In this paper, we combine heuristic and exact learning and take the best of both worlds.