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.

Published 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 (4)

• Estimating high-dimensional intervention effects from observational data
• Strong Faithfulness and Uniform Consistency in Causal Inference
• A Uniformly Consistent Estimator of Causal Effects under the $k$-Triangle-Faithfulness Assumption
• Perfect Tree-Like Markovian Distributions

Cited by in corpus (23)

• Causal Structure Learning: a Combinatorial Perspective
• 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
• Learning linear non-Gaussian directed acyclic graph with diverging number of nodes
• ASP-based Discovery of Semi-Markovian Causal Models under Weaker Assumptions
• Complexity analysis of Bayesian learning of high-dimensional DAG models and their equivalence classes
• A Weaker Faithfulness Assumption based on Triple Interactions
• Perturbation graphs, invariant prediction and causal relations in psychology
• Nonparametric causal structure learning in high dimensions
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Conditionally-additive-noise Models for Structure Learning
• Obtaining Causal Information by Merging Datasets with MAXENT
• A Topological Perspective on Causal Inference
• Efficient Bayesian network structure learning via local Markov boundary search
• Learning Bayesian Networks from Ordinal Data
• Faithfulness and learning hypergraphs from discrete distributions
• Causality and Robust Optimization
• Causality and Generalizability: Identifiability and Learning Methods
• Definite Non-Ancestral Relations and Structure Learning
• A General Framework on Conditions for Constraint-based Causal Learning
• KL-BSS: Rethinking optimality for neighbourhood selection in structural equation models
• Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge