Minimal I-MAP MCMC for Scalable Structure Discovery in Causal DAG Models

Learning a Bayesian network (BN) from data can be useful for decision-making or discovering causal relationships. However, traditional methods often fail in modern applications, which exhibit a larger number of observed variables than data points. The resulting uncertainty about the underlying network as well as the desire to incorporate prior information recommend a Bayesian approach to learning the BN, but the highly combinatorial structure of BNs poses a striking challenge for inference. The current state-of-the-art methods such as order MCMC are faster than previous methods but prevent the use of many natural structural priors and still have running time exponential in the maximum indegree of the true directed acyclic graph (DAG) of the BN. We here propose an alternative posterior approximation based on the observation that, if we incorporate empirical conditional independence tests, we can focus on a high-probability DAG associated with each order of the vertices. We show that our method allows the desired flexibility in prior specification, removes timing dependence on the maximum indegree and yields provably good posterior approximations; in addition, we show that it achieves superior accuracy, scalability, and sampler mixing on several datasets.

• Publication year

  2018

• Venue

  International Conference on Machine Learning

• Publication date

  2018-03-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1803.05554
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Graphical Models

  2020cited by this paper
• Consistency Guarantees for Permutation-Based Causal Inference Algorithms

  2017influential reference
• Generalized Permutohedra from Probabilistic Graphical Models

  2016cited by this paper
• Counting Linear Extensions of Sparse Posets

  2016cited by this paper
• Structure Discovery in Bayesian Networks by Sampling Partial Orders

  2016cited by this paper
• A Soft Intelligent Risk Evaluation Model for Credit Scoring Classification

  2015cited by this paper
• Partition MCMC for Inference on Acyclic Digraphs

  2015influential reference
• Addendum on the scoring of Gaussian directed acyclic graphical models

  2014influential reference
• Learning directed acyclic graphs based on sparsest permutations

  2013influential reference
• Geometry of the faithfulness assumption in causal inference

  2012influential reference
• Bayesian Methods for Data-Dependent Priors

  2011cited by this paper
• Computing Posterior Probabilities of Structural Features in Bayesian Networks

  2009cited by this paper
• Improving the structure MCMC sampler for Bayesian networks by introducing a new edge reversal move

  2008cited by this paper
• Network inference using informative priors

  2008influential reference
• Learning Causal Bayesian Network Structures From Experimental Data

  2008influential reference
• The max-min hill-climbing Bayesian network structure learning algorithm

  2006influential reference
• Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm

  2005influential reference
• Being Bayesian About Network Structure. A Bayesian Approach to Structure Discovery in Bayesian Networks

  2004influential reference
• Exact Bayesian Structure Discovery in Bayesian Networks

  2004cited by this paper
• Causation, Prediction, and Search

  2003influential reference
• Optimal Structure Identification With Greedy Search

  2002influential reference
• Strong Faithfulness and Uniform Consistency in Causal Inference

  2002influential reference
• Using Bayesian Networks to Analyze Expression Data

  2000cited by this paper
• Marginal Structural Models and Causal Inference in Epidemiology

  2000cited by this paper
• Parameter Priors for Directed Acyclic Graphical Models and the Characteriration of Several Probability Distributions

  1999cited by this paper
• Data Analysis with Bayesian Networks: A Bootstrap Approach

  1999cited by this paper
• A characterization of Markov equivalence classes for acyclic digraphs

  1997influential reference
• Bayesian Graphical Models for Discrete Data

  1995cited by this paper
• An Algorithm for Deciding if a Set of Observed Independencies Has a Causal Explanation

  1992cited by this paper
• Probability and Bayesian Statistics

  1987influential reference
• FREQUENCY DISTRIBUTION OF THE VALUES OF THE CORRELATION COEFFIENTS IN SAMPLES FROM AN INDEFINITELY LARGE POPU;ATION

  1915cited by this paper
• Causality : Models , Reasoning , and Inference

  year unknowninfluential reference

• Identifiability of the minimum-trace directed acyclic graph and hill climbing algorithms without strict local optima under weakly increasing error variances

  2025cites this paper
• PROCA: Programmable Probabilistic Processing Unit Architecture with Accept/Reject Prediction & Multicore Pipelining for Causal Inference

  2025cites this paper
• Large-Scale Bayesian Causal Discovery with Interventional Data

  2025cites this paper
• Greedy equivalence search for nonparametric graphical models

  2024cites this paper
• Gene regulatory network inference from CRISPR perturbations in primary CD4+ T cells elucidates the genomic basis of immune disease

  2023cites this paper
• Causal structure learning with momentum: Sampling distributions over Markov Equivalence Classes of DAGs

  2023cites this paper
• Active learning for optimal intervention design in causal models

  2022cites this paper
• Causal Structure Learning: A Combinatorial Perspective

  2022cites this paper
• BCDAG: An R package for Bayesian structure and Causal learning of Gaussian DAGs

  2022cites this paper
• Order-based Structure Learning without Score Equivalence

  2022influential citation
• Tractable Uncertainty for Structure Learning

  2022cites this paper
• Active Bayesian Causal Inference

  2022cites this paper
• Bayesian Multi-Task Variable Selection with an Application to Differential DAG Analysis

  2022influential citation
• Rapid Convergence of Informed Importance Tempering

  2021cites this paper
• On the Scalability of Informed Importance Tempering

  2021cites this paper
• Variational Causal Networks: Approximate Bayesian Inference over Causal Structures

  2021cites this paper
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes

  2021cites this paper
• ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery

  2019cites this paper
• Optimal experimental design via Bayesian optimization: active causal structure learning for Gaussian process networks

  2019cites this paper