Structural learning for Bayesian networks by testing complete separators in prime blocks

In this paper, we consider how to recover the structure of a Bayesian network from a moral graph. We present a more accurate characterization of moral edges, based on which a complete subset (i.e., a separator) contained in the neighbor set of one vertex of the putative moral edge in some prime block of the moral graph can be chosen. This results in a set of separators needing to be searched generally smaller than the sets required by some existing algorithms. A so-called structure-finder algorithm is proposed for structural learning. The complexity analysis of the proposed algorithm is discussed and compared with those for several existing algorithms. We also demonstrate how to construct the moral graph locally from, separately, the Markov blanket, domain knowledge and d-separation trees. Simulation studies are used to evaluate the performances of various strategies for structural learning. We also analyze a gene expression data set by using the structure-finder algorithm.Bayesian network Complete separator Conditional independence Moral edge Prime block Structural learning