  Main approaches for learning Bayesian networks can be classified as
constraint-based, score-based or hybrid methods. Although high-dimensional
consistency results are available for constraint-based methods like the PC
algorithm, such results have not been proved for score-based or hybrid methods,
and most of the hybrid methods have not even shown to be consistent in the
classical setting where the number of variables remains fixed and the sample
size tends to infinity. In this paper, we show that consistency of hybrid
methods based on greedy equivalence search (GES) can be achieved in the
classical setting with adaptive restrictions on the search space that depend on
the current state of the algorithm. Moreover, we prove consistency of GES and
adaptively restricted GES (ARGES) in several sparse high-dimensional settings.
ARGES scales well to sparse graphs with thousands of variables and our
simulation study indicates that both GES and ARGES generally outperform the PC
algorithm.
