Bidirectional Heuristic Search for Bayesian Network Structure with Ancestral Partition
Xiangyuan Tan, Xiaoguang Gao, Zidong Wang, Xiaohan Liu · 2022
Exact algorithms for learning optimal Bayesian networks require much more time and are used in small Bayesian networks. This paper adds ancestral partition constraints into the bidirectional heuristic search algorithm based on the order graph. The ancestral partition can be obtained by extracting strongly connected components from possible parent sets. Experiments show that ancestral partition can significantly improve the efficiency and scalability of bidirectional heuristic search. In addition, with ancestral partition constraints, bidirectional heuristic search has better efficiency and can search larger Bayesian networks than state-of-the-art algorithms.