The max-min hill-climbing Bayesian network structure learning algorithm

By Ioannis Tsamardinos, Laura E. Brown, Constantin F. Aliferis. 2006

2,195 citations recorded by the source corpus.

We present a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). The algorithm combines ideas from local learning, constraint-based, and search-and-score techniques in a principled and effective way. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. In our extensive empirical evaluation MMHC outperforms on average and in terms of various metrics several prototypical and state-of-the-art algorithms, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search. These are the first empirical results simultaneously comparing most of the major Bayesian network algorithms against each other. MMHC offers certain theoretical advantages, specifically over the Sparse Candidate algorithm, corroborated by our experiments. MMHC and detailed results of our study are publicly available at http://www.dsl-lab.org/supplements/mmhc_paper/mmhc_index.html.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

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 Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Learning Neural Causal Models from Unknown Interventions (2019, background): “A lot of prior work has examined learning causal structure based on observational data (Chickering, 2002; Tsamardinos et al., 2006; Goudet et al., 2017; Hauser & Bühlmann, 2012; Spirtes et al., 2000; Sun et al., 2007; Zhang et al., 2012; Shimizu et al., 2006; Hoyer et al., 2009; Daniusis et al.,…”
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.”
DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, methodology): “This is consistent with previous work on score-based learning (Aragam and Zhou, 2015), which also indicates that FGS outperforms other techniques such as hill-climbing and MMHC (Tsamardinos et al., 2006).”
Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm (2005, methodology): “For an extensive numerical comparison study of different algorithms, we refer to Tsamardinos et al. (2006).”
Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs (2011, methodology): “The structural Hamming distance or SHD (Tsamardinos et al., 2006; we use the slightly adapted version of Kalisch and B¨uhlmann, 2007) is used to measure the distance between an estimated I -essential graph ˆ G and a true I -essential graph or DAG G .”
Causal Discovery with Reinforcement Learning (2019, methodology): “There are hybrid methods that use constraint-based approaches to reduce the search space before applying score-based methods, e.g., [28].”
Order-independent constraint-based causal structure learning (2012, background): “vits (1992); Heckerman et al. (1995); Spiegelhalter et al. (1993)), as well as hybrids of the different approaches (e.g., Dash and Druzdzel (1999); Singh and Valtorta (1993); Spirtes and Meek (1995); Tsamardinos et al. (2006); van Dijk et al. (2003)). A Markov equivalence class of DAGs can be unique”
Structural Intervention Distance (SID) for Evaluating Causal Graphs (2013, background): “1 Structural Hamming Distance The Structural Hamming Distance (Acid and de Campos, 2003; Tsamardinos et al., 2006) considers two partially directed acyclic graphs (PDAGs, see appendix) and counts how many edges do not coincide.”
Causal Structure Learning (2017, methodology): “Limiting ourselves to algorithms with an implementation in R (R Core Team, 2017), we obtain the following selection of methods, with assumptions summarized in Table 1: • Constraint-based methods: PC (Spirtes et al., 2000), rankPC (Harris and Drton, 2013), FCI (Spirtes et al., 2000), and rankFCI • Sc”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, methodology): “We demonstrate the use of DAG-GNN on three discrete benchmark data sets: Child, Alarm, and Pigs (Tsamardinos et al., 2006).”
Does agriculture really matter for economic Growth in Developing Countries (2015, methodology): “Monte Carlo evidence suggests that when the sample size is small, GES algorithm performs better in identifying DAGs (Tsamardinos et al 2006; Wang and Rettenmaier 2008; Ramsey et al 2011).”
Big data for cyber physical systems in industry 4.0: a survey (2019, methodology): “Typical heuristic methods include genetic algorithm (Deb et al. 2002), simulated annealing (Kirkpatrick, Gelatt, and Vecchi 1983), hill climbing (Tsamardinos, Brown, and Aliferis 2006), tabu search (Glover and Laguna 2013), and colony optimization (Dorigo, Birattari, and Stutzle 2006).”
Learning Graphical Model Structure Using L1-Regularization Paths (2007, methodology): “The first DAG learning method that we improve is called max-min hill-climbing (MMHC) ( TBA06 ) which was shown to outperform many other methods, in a series of extensive experiments.”
Local Causal and Markov Blanket Induction for Causal Discovery and Feature Selection for Classification Part I: Algorithms and Empirical Evaluation (2010, methodology): “This prior knowledge may come from domain knowledge, experiments, or may be the result of running GLL-PC on variable X and finding that T is in PC(X) when conducting local-to-global learning (Aliferis et al., 2009; Tsamardinos et al., 2006).”
Explainable and Interpretable Models in Computer Vision and Machine Learning (2017, neutral): “( Spirtes et al., 2000; Tsamardinos et al., 2006; Pearl, 2009) On the other hand, the T¨ubingen School has proposed new and powerful functional causal models (FCM) algorithms exploiting the asymmetries in the joint distribution of cause-effect pairs.”
Estimating the effect of joint interventions from observational data in sparse high-dimensional settings (2014, methodology): “valence class, and i jin the CPDAG if the Markov equivalence class contains a DAG for which i!jas well as a DAG for which i j. CPDAGs can be estimated from observational data using various algorithms [29; 5; 32]. The PC-algorithm [29] is one such algorithm, and is consistent in sparse high-dimension”
A Survey of Learning Causality with Data (2018, methodology): “For each iteration, given the current graph, the triple 𝑥 ,𝑗 ,𝑥 ,𝑗 ′ , 𝒛 with the highest score is selected to update the graph with the delete operator.”
Structural Agnostic Modeling: Adversarial Learning of Causal Graphs (2018, methodology): “…ranging in [0,1], with 1 being the optimum.13 Structural Hamming Distance Another performance indicator used in the causal graph discovery framework is the Structural Hamming Distance (SHD) (Tsamardinos et al., 2006), set to the number of missing edges and redundant edges in the found structure.”
Learning Bayesian Networks with the bnlearn R Package (2009, methodology): “It has been widely used (see for example Tsamardinos et al. (2006) and Friedman et al. (1999)) as a case study to evaluate the performance of new structure learning algorithms.”