Confidence Sets for Causal Orderings

Y. Samuel Wang, Mladen Kolar, Mathias DrtonarXiv 2023 · DOI · arXiv

Abstract

Causal discovery procedures aim to deduce causal relationships among variables in a multivariate dataset. While various methods have been proposed for estimating a single causal model or a single equivalence class of models, less attention has been given to quantifying uncertainty in causal discovery in terms of confidence statements. A primary challenge in causal discovery of directed acyclic graphs is determining a causal ordering among the variables, and our work offers a framework for constructing confidence sets of causal orderings that the data do not rule out. Our methodology specifically applies to identifiable structural equation models with additive errors and is based on a residual bootstrap procedure to test the goodness-of-fit of causal orderings. We demonstrate the asymptotic validity of the confidence set constructed using this goodness-of-fit test and explain how the confidence set may be used to form sub/supersets of ancestral relationships as well as confidence intervals for causal effects that incorporate model uncertainty.

Introduction

In the field of causal discovery, the primary objective is to move beyond simple correlation to identify the underlying "who-causes-whom" structure, typically represented as a Directed Acyclic Graph (DAG). A fundamental hurdle in this process is determining the causal ordering: a sequence of variables where parents always precede their children.

While existing algorithms can output a single "best guess" DAG, they frequently fail to provide a measure of certainty. In scenarios where the data signal is weak, multiple graphs might fit the observations equally well. Ignoring this uncertainty can lead to overconfidence and erroneous scientific conclusions. This research addresses the "frequentist" gap in causal discovery by providing a framework to construct confidence sets—identifying all variable permutations that the data cannot statistically reject.

Methodology: Inverting Goodness-of-Fit

The core of the proposed procedure is the inversion of a goodness-of-fit (GoF) test. The intuition is straightforward: if a specific causal ordering is correct, regressing a variable on its predecessors should yield residuals that are independent of those predecessors.

Visualizing the goodness-of-fit test: Residuals from a correct model show no pattern, whereas an incorrect model exhibits clear structure.

Technical Components

  • Residual Bootstrap Test: Traditional independence tests often rely on Gaussian assumptions. However, causal direction is frequently only identifiable when noise is non-Gaussian. The authors employ a residual bootstrap procedure to estimate the null distribution, ensuring the test is robust across various error distributions (e.g., Gamma, Laplace, Lognormal).
  • Branch-and-Bound Search: Searching through all possible orderings is computationally prohibitive, as the number of permutations ($p!$) grows factorially. The authors implement a pruning strategy: if a partial ordering fails the GoF test, the algorithm discards all full orderings beginning with that sequence.
  • Post-processing for Causal Effects: By aggregating results across the entire confidence set of valid orderings, researchers can calculate confidence intervals for causal effects that honestly account for model uncertainty.

Key Insights and Results

The framework leverages non-Gaussianity as a feature rather than a nuisance, using it to distinguish cause from effect. Furthermore, the occurrence of an empty confidence set serves as a diagnostic tool; it suggests that none of the possible orderings fit the data under the assumed model class (e.g., additive noise), prompting a re-evaluation of modeling assumptions.

Performance and Scalability

  • Computational Efficiency: The proposed GoF test is significantly faster than state-of-the-art alternatives like the Hilbert-Schmidt Independence Criterion (HSIC), showing speedups of 40x to 9000x.
  • Scalability: The branch-and-bound approach allows the method to handle up to approximately 20 variables on standard hardware.
  • Statistical Validity: Simulations confirm that the method maintains nominal coverage, ensuring that a 90% confidence set contains the true ordering at least 90% of the time.

Limitations and Future Directions

While the method represents a significant step forward for frequentist uncertainty quantification in causal discovery, challenges remain. The factorial nature of permutations limits scalability for datasets with hundreds of variables. Additionally, the current framework assumes causal sufficiency (no unobserved confounders) and a DAG structure (no feedback loops). Future research may extend these methods to accommodate latent variables and cyclic models.

Summary updated

Abstract

Causal discovery procedures aim to deduce causal relationships among variables in a multivariate dataset. While various methods have been proposed for estimating a single causal model or a single equivalence class of models, less attention has been given to quantifying uncertainty in causal discovery in terms of confidence statements. A primary challenge in causal discovery of directed acyclic graphs is determining a causal ordering among the variables, and our work offers a framework for constructing confidence sets of causal orderings that the data do not rule out. Our methodology specifically applies to identifiable structural equation models with additive errors and is based on a residual bootstrap procedure to test the goodness-of-fit of causal orderings. We demonstrate the asymptotic validity of the confidence set constructed using this goodness-of-fit test and explain how the confidence set may be used to form sub/supersets of ancestral relationships as well as confidence intervals for causal effects that incorporate model uncertainty.
BibTeX
@misc{wang2023confidence,
  author = {Y. Samuel Wang and Mladen Kolar and Mathias Drton},
  title = {{Confidence Sets for Causal Orderings}},
  year = {2023},
  eprint = {2305.14506},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.14506},
}
Figure