Learning the structure of Bayesian networks with ancestral and/or heuristic partition

Abstract Developing efficient strategies for searching larger Bayesian networks in exact structure learning is an open challenge. In this study, ancestral and heuristic partition constraints are proposed to develop a series of exact learning algorithms, in which an ancestral partition is used to prune the order graph of a Bayesian network, and a heuristic partition is utilized to improve the tightness of the heuristic function. Algorithms for calculating these two types of constraints are established through thorough theoretical proof. Comparative experiments have been undertaken with state-of-the-art algorithms. It has been demonstrated that an algorithm improved with the proposed ancestral partition or combined ancestral and heuristic partition outperforms the algorithm in its original form, and it can have lower running time, fewer expanded states, and higher accuracy, as well as the ability to search larger networks within 100 nodes.