On Hybridizing Complete Bayesian Network Structure Search with Independence Tests

Bayesian Networks (BN) are probabilistic graphical models used to encode in a compact way a joint probability distribution over a set of random variables. The NP-complete problem of finding the most probable BN structure given the observed data has been largely studied in recent years. In the literature, several complete algorithms have been proposed for the problem; in parallel, several tests for statistical indepen- dence between the random variables have also been proposed, in order to reduce the size of the search space. In this work, we propose to hy- bridize the algorithm representing the state-of-the-art in complete search with two types of independence tests, and assess the performance of the hybrid algorithms in terms of both solution quality and computational time. Experimental results show that hybridization with both indepen- dence tests results in a substantial gain in computational time, against a limited loss in solution quality, and that none of the two independence tests consistently dominates the other in terms of computational time gain.