Geometry of the faithfulness assumption in causal inference

By Caroline Uhler, Garvesh Raskutti, Peter Buhlmann, Bin Yu. 2012

260 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Epidemiology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/efd9b7030e97ba88257a3ebebef910dd4b32c270

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 Epidemiology

In Statistics and Probability

Citations in the corpus

Identifiability of Gaussian structural equation models with equal error variances (2012, background): “For consistency in the first step one necessarily requires a version of the strong faithfulness assumption, which can be very restrictive [Uhler et al., 2013].”
Causal network reconstruction from time series: From theoretical assumptions to practical estimation. (2018, background): “However, approximately vanishing partial correlations despite connectedness in the graph can also occur for a distribution that is faithful, but almost unfaithful, if we have only a limited sample size available as discussed in Uhler et al. (2013).”
High-dimensional consistency in score-based and hybrid structure learning (2015, background): “The most criticized assumption among these four assumptions is probably (A6) [Uhler et al., 2013], which is also known as the strong faithfulness condition.”
MAXIMUM LIKELIHOOD FOR SPARSE DIRECTED ACYCLIC GRAPHS (2013, methodology): “Our analysis with the penalized MLE is completely different and circumvents faithfulness and strong faithfulness conditions which are often very restrictive as shown by Uhler et al. (2013); see also below.”
Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression (2015, background): “3), which is a strong assumption that rarely holds in practice (Lin et al., 2014; Uhler et al., 2013).”
PC algorithm for nonparanormal graphical models (2013, unknown): “As shown in Uhler et al. (2013), this can be a restrictiveassumption, which provides an explanation for why consistency does not ‘kick-in’ quicker in simulationstudies such as the one in Kalisch and B̈uhlmann (2007) and also ours.”
Detecting Confounding in Multivariate Linear Models via Spectral Analysis (2017, background): “For practical purposes one needs to also exclude almost unfaithful distributions and assume that they occur only with small probability (although this is problematic [14]).”
Efficient Sampling and Structure Learning of Bayesian Networks (2018, background): “Despite its efficiency, because it can only delete edges by performing a large number of (correlated) independence tests, the PC algorithm tends to have a high rate of false negatives and only find a fraction of the edges in the true network (Uhler et al., 2013).”
Structure Learning in Graphical Modeling (2016, background): “This assumption is studied in depth by Uhler et al. (2013), who show that it can be restrictive.”
Automated Machine Learning: Methods, Systems, Challenges (2019, unknown): “16))) [33, 49] was limited to G = {X → Y , X ← Y}: { g = [X → Y ] : x ∼ P(X), ny ∼ P(Ny),X ⊥ Ny, y := f (x)+ ny g = [X ← Y ] : y ∼ P(Y ), nx ∼ P(Nx), Y ⊥ Nx, x := f (y)+ nx.”
$\ell_0$-penalized maximum likelihood for sparse directed acyclic graphs (2012, methodology): “Our analysis with the penalized MLE is completely diﬀerent and circumvents faithfulness and strong faithfulness conditions which are often very restrictive as shown by Uhler et al. (2013); see also below.”
UvA-DARE ( Digital Academic Repository ) Causal Discovery with Continuous Additive Noise Models (2014, unknown): “Uhler et al. (2013) argue that this is a restrictive condition.”
An empirical study of one of the simplest causal prediction algorithms (2015, methodology): “Nevertheless, using the techniques described in [Uhler et al., 2013], it may be possible to derive asymptotic results for the setting that we are interested in here.”
Type-II Errors of Independence Tests Can Lead to Arbitrarily Large Errors in Estimated Causal Effects: An Illustrative Example (2014, background): “[11] addressed the question of how restrictive the Strong Faithfulness assumption is in terms of the volume of distributions that do not satisfy this assumption.”