High-dimensional consistency in score-based and hybrid structure learning (Q1991699)

The main approaches for learning Bayesian networks can be classified as constrained-based, score-based or hybrid methods. Constrained-based methods, such as the PC algorithm and its variants, are the most popular applied methods in high-dimensional methods. This popularity is explained since score-based and hybrid methods lack consistency results in high-dimensional settings and/or they do not scale well to large graphs. In this paper, the authors propose a high-dimensional consistency of Greedy equivalence search (GES), which is a popular score-based method. Moreover, they propose new hybrid algorithms based on GES that are consistent in several sparse high-dimensional settings and scale well to large sparse graphs. In particular, the authors show that the consistency of hybrid algorithms based on GES can be achieved by imposing a restriction on the search space that changes depending on the current state of an algorithm. This new method is called adaptively greedy equivalence search (ARGES). The consistency of GES and ARGES is proved in several sparse high-dimensional settings (multivariate Gaussian, linear structural equation models with sub-Gaussian error variables, nonparanormal setting). A simulation study indicates that both GES and ARGES generally outperform the PC algorithm. It is worth to mention that all proofs and additional simulation results can be found in the Supplementary material, while an implementation of ARGES is available in the R-package pcalg.