Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming

Bayesian networks are probabilistic graphical models with a wide range of\napplication areas including gene regulatory networks inference, risk analysis\nand image processing. Learning the structure of a Bayesian network (BNSL) from\ndiscrete data is known to be an NP-hard task with a superexponential search\nspace of directed acyclic graphs. In this work, we propose a new polynomial\ntime algorithm for discovering a subset of all possible cluster cuts, a greedy\nalgorithm for approximately solving the resulting linear program, and a\ngeneralised arc consistency algorithm for the acyclicity constraint. We embed\nthese in the constraint programmingbased branch-and-bound solver CPBayes and\nshow that, despite being suboptimal, they improve performance by orders of\nmagnitude. The resulting solver also compares favourably with GOBNILP, a\nstate-of-the-art solver for the BNSL problem which solves an NP-hard problem to\ndiscover each cut and solves the linear program exactly.\n