Geometry of the faithfulness assumption in causal inference

Abstract

Many algorithms for inferring causality rely heavily on the faithfulness assumption. The main justification for imposing this assumption is that the set of unfaithful distributions has Lebesgue measure zero, since it can be seen as a collection of hypersurfaces in a hypercube. However, due to sampling error the faithfulness condition alone is not sufficient for statistical estimation, and strong-faithfulness has been proposed and assumed to achieve uniform or high-dimensional consistency. In contrast to the plain faithfulness assumption, the set of distributions that is not strong-faithful has nonzero Lebesgue measure and in fact, can be surprisingly large as we show in this paper. We study the strong-faithfulness condition from a geometric and combinatorial point of view and give upper and lower bounds on the Lebesgue measure of strong-faithful distributions for various classes of directed acyclic graphs. Our results imply fundamental limitations for the PC-algorithm and potentially also for other algorithms based on partial correlation testing in the Gaussian case.

arXiv commentPublished in at http://dx.doi.org/10.1214/12-AOS1080 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (8)

• Estimating high-dimensional directed acyclic graphs with the PC-algorithm
• Estimating high-dimensional intervention effects from observational data
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• Strong Faithfulness and Uniform Consistency in Causal Inference
• Trek separation for Gaussian graphical models
• Hypersurfaces and their singularities in partial correlation testing
• A Uniformly Consistent Estimator of Causal Effects under the $k$-Triangle-Faithfulness Assumption
• Perfect Tree-Like Markovian Distributions

Cited by in corpus (48)

• Identifiability of Gaussian structural equation models with equal error variances
• Causal Discovery with Continuous Additive Noise Models
• ${\ell }_0$-penalized maximum likelihood for sparse directed acyclic graphs
• Experimental Test of Nonlocal Causality
• Learning Large-Scale Bayesian Networks with the sparsebn Package
• Causality in cognitive neuroscience: concepts, challenges, and distributional robustness
• Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression
• Causal Structure Learning: a Combinatorial Perspective
• Hypersurfaces and their singularities in partial correlation testing
• Nonlinear Causal Discovery with Confounders
• A Uniformly Consistent Estimator of Causal Effects under the $k$-Triangle-Faithfulness Assumption
• Estimating causal structure using conditional DAG models
• Direct Estimation of Differences in Causal Graphs
• The Reduced PC-Algorithm: Improved Causal Structure Learning in Large Random Networks
• Learning Loosely Connected Markov Random Fields
• Ordering-Based Causal Structure Learning in the Presence of Latent Variables
• Model selection and local geometry
• Calculation of Entailed Rank Constraints in Partially Non-Linear and Cyclic Models
• A review of Gaussian Markov models for conditional independence
• Learning directed acyclic graphs based on sparsest permutations
• Minimal I-MAP MCMC for Scalable Structure Discovery in Causal DAG Models
• Causal Discovery with Unobserved Confounding and non-Gaussian Data
• High-Dimensional Joint Estimation of Multiple Directed Gaussian Graphical Models
• Causal inference in degenerate systems: An impossibility result
• ASP-based Discovery of Semi-Markovian Causal Models under Weaker Assumptions
• Identifiability Assumptions and Algorithm for Directed Graphical Models with Feedback
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
• A Weaker Faithfulness Assumption based on Triple Interactions
• Learning linear non-Gaussian directed acyclic graph with diverging number of nodes
• Nonparametric causal structure learning in high dimensions
• Perturbation graphs, invariant prediction and causal relations in psychology
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Generalized Permutohedra from Probabilistic Graphical Models
• Conditionally-additive-noise Models for Structure Learning
• An algorithm for reconstruction of triangle-free linear dynamic networks with verification of correctness
• Obtaining Causal Information by Merging Datasets with MAXENT
• A Topological Perspective on Causal Inference
• Efficient Bayesian network structure learning via local Markov boundary search
• Identifiability of Gaussian Structural Equation Models with Homogeneous and Heterogeneous Error Variances
• A General Framework on Conditions for Constraint-based Causal Learning
• KL-BSS: Rethinking optimality for neighbourhood selection in structural equation models
• Definite Non-Ancestral Relations and Structure Learning
• Causality and Generalizability: Identifiability and Learning Methods
• Learning Bayesian Networks from Ordinal Data
• Causal Model Analysis using Collider v-structure with Negative Percentage Mapping
• Faithfulness and learning hypergraphs from discrete distributions
• Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge
• Causality and Robust Optimization