High-dimensional consistency in score-based and hybrid structure learning

By Preetam Nandy, Alain Hauser, Marloes H. Maathuis. 2015

151 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Causal Generative Neural Networks (2017, methodology): “Following [Tsamardinos et al. , 2006; Nandy et al. , 2015], we assume known skeleton for G , obtained via domain knowledge or a feature selection algorithm [Yamada et al. , 2014] under standard assumptions such as causal Markov, faithfulness, and sufﬁciency.”
Causal Discovery with Reinforcement Learning (2019, background): “GES is known to find the global minimizer with infinite samples under suitable assumptions (Chickering, 2002; Nandy et al., 2018), but this is not guaranteed in the finite sample regime.”
Causal Structure Learning (2017, methodology): “Nandy et al. (2017a) showed a close connection between score-based and constraint-based meth-ods for multivariate Gaussian data.”
Structure Learning in Graphical Modeling (2016, methodology): “These ideas can be combined with the structure learning methods that we discuss in Section 4 to estimate (bounds on) causal eﬀects from observational data (Maathuis et al., 2009, 2010; Perkovi´c et al., 2015; Nandy et al., 2016b).”
Explainable and Interpretable Models in Computer Vision and Machine Learning (2017, unknown): “According to Nandy et al. (2015), such methods often use a greedy search like the GES method on a restricted search space for the sake of computational efﬁciency.”
Structural Agnostic Modeling: Adversarial Learning of Causal Graphs (2018, methodology): “According to Nandy et al. (2015), such methods often use a greedy search like the GES method on a restricted search space for the sake of computational efficiency.”
Efficient Sampling and Structure Learning of Bayesian Networks (2018, methodology): “Nandy et al. (2018) recently investigated the consistency properties of hybrid approaches using GES in high dimensional settings.”
A survey of Bayesian Network structure learning (2021, methodology): “Nandy et al. (2018) proposed Adaptively Restricted GES (ARGES) for continuous variables which uses MMPC for the restrict step and then a modified GES (see subsection 3.2.2) for the maximise step.”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, background): “[260] 2020 score Granger – – no Bi Order-MCMC [60] 2003 sampling yes yes yes no DAG OG [53] 2008 sampling yes yes yes yes DAG EE-DAG [281] 2011 sampling yes yes yes yes DAG ZIPBN [35] 2020 sampling yes no yes no DAG LiNGAM [221] 2006 asymmetries yes no yes no DAG LV LiNGAM [101] 2008 asymmetries no ”