B1115
Title: The dual PC algorithm for structure learning of Bayesian networks
Authors: Enrico Giudice - University of Basel (Switzerland) [presenting]
Jack Kuipers - ETH Zurich (Switzerland)
Giusi Moffa - University of Basel (Switzerland)
Abstract: Learning the graphical structure of Bayesian Networks from observational data is a computationally challenging task and key to understanding data generating processes in complex applications. The Directed Acyclic Graph (DAG) of the Bayesian Network model is generally not identifiable from observational data, and a variety of methods exist to estimate the equivalence class of the DAG. Under certain assumptions, the popular PC algorithm can consistently recover the correct equivalence class by recursively testing for conditional independence (CI), starting from marginal independencies and progressively expanding the conditioning set. We propose the dual PC algorithm, a novel scheme to carry out the CI tests within the PC algorithm by leveraging the inverse relationship between covariance and precision matrices. Notably, the elements of the precision matrix coincide with partial correlations for Gaussian data. The algorithm then exploits block matrix inversions on the covariance and precision matrices to simultaneously perform tests on partial correlations of complimentary (or dual) conditioning sets. The multiple CI tests of the PC algorithm, therefore, proceed by first considering marginal and full-order CI relationships and progressively moving to central-order ones. Simulation studies indicate that the dual PC algorithm outperforms the classical PC algorithm both in terms of run time and in recovering the underlying network structure.
