Orthogonal Structure Search for Efficient Causal Discovery from Observational Data

Anant Raj, Luigi Gresele, Michel Besserve, Bernhard Schölkopf, Stefan Bauer

TL;DR

This paper introduces "Orthogonal Structure Search" (OSS), a novel algorithm for efficiently discovering direct causal parents of a target variable, even with purely observational, partially nonlinear data. OSS significantly outperforms existing methods in terms of computational complexity and scalability, achieving linear time complexity with respect to the number of variables.

What Problem Does This Paper Address?

Identifying causal relationships is crucial across many scientific domains, but it's a notoriously difficult problem, especially when relying solely on observational data. Traditional methods often require strong assumptions like "faithfulness" or rely on data from multiple experimental settings (environments). While these methods offer theoretical guarantees, they suffer from a major bottleneck: computational complexity. Specifically, many state-of-the-art techniques involve searching through all possible subsets of variables, leading to an exponential increase in computation time with the number of potential causes. This makes them impractical for large, real-world datasets. The paper aims to bridge this gap by developing a method that is both computationally efficient and theoretically sound, even in the challenging scenario of observational data and partially nonlinear relationships.

Methods

The core of the proposed method, Orthogonal Structure Search (OSS), is built upon the principles of Double Machine Learning (DML) and Neyman Orthogonality. DML is a technique for estimating causal effects in the presence of confounding variables, particularly in partially linear models. Neyman Orthogonality provides a way to construct estimators that are robust to biases introduced by estimating nuisance parameters (like nonlinear functions of covariates).

Here's a breakdown of the approach:

  • One-vs-Rest Strategy: For each potential causal variable, OSS treats it as a "policy" variable and all other variables as "confounders" in a DML framework.
  • Orthogonalization: The key innovation is using Neyman orthogonality to ensure that the estimation of the causal effect of a variable on the target is unbiased, even when dealing with nonlinear relationships among other variables. This is achieved by constructing an "orthogonalized score function" that is insensitive to errors in estimating the nuisance parameters.
  • Statistical Testing: After estimating the causal effect of a variable, a statistical test (specifically, a z-test for Gaussianity of the estimated parameter distribution) is used to determine if the variable is a true causal parent. If the distribution is centered around zero, it's likely not a parent; otherwise, it is.
  • Scalability: The algorithm iteratively applies this process to each variable. Crucially, it avoids the exponential search over subsets of variables. Instead, it performs a linear number of estimations (one for each variable), resulting in a computational complexity that scales linearly with the number of variables ($O(d)$).

Datasets

The paper evaluates its method through extensive numerical simulations using synthetic datasets generated according to various structural equation models. These simulations are designed to test the algorithm's performance in scenarios with:

  • Linear and partially nonlinear relationships.
  • Different numbers of environments (for comparison with ICP).
  • Large graphs (up to 30 variables).
  • Hidden confounders.

No specific real-world datasets are used for evaluation, but the synthetic benchmarks are designed to mimic challenging aspects of real-world causal discovery problems.

Key Insights and Ideas

  • Observational Data is Enough (Sometimes): The paper demonstrates that for identifying direct causal parents, purely observational data can be sufficient, even in the presence of partially nonlinear relationships, which is a significant departure from many existing methods requiring interventional data.
  • Neyman Orthogonality as a Game-Changer: Applying Neyman orthogonality to the causal discovery problem allows for unbiased estimation of causal effects, making the algorithm robust to complex, nonlinear dependencies among non-causal variables. This is the technical backbone that enables efficiency.
  • Linearity for Direct Causes, Nonlinearity Elsewhere: The method cleverly leverages the assumption that the direct causal relationships to the target variable are linear, while allowing for arbitrary nonlinearities among other variables. This is a powerful simplification that doesn't over-restrict the model.
  • Efficiency Through Orthogonalization: By avoiding exhaustive subset searches and instead focusing on individual variable effects with an orthogonalized estimator, the algorithm achieves a dramatic reduction in computational complexity from exponential ($O(2^d)$) to linear ($O(d)$).

Key Results

  • Computational Efficiency: OSS achieves a linear time complexity ($O(d)$) with respect to the number of variables, significantly outperforming existing methods like Invariant Causal Prediction (ICP) which have exponential complexity ($O(2^d)$). For a 60-variable graph, OSS takes around 120 seconds, while ICP on a 10-variable graph takes ~230 seconds.
  • Scalability: The algorithm scales well to large graphs, demonstrating good performance on graphs with up to 30 variables. For 20 variables, the true discovery rate is 0.86 with a false positive rate of 0.0015. For 30 variables, the true discovery rate is 0.67 with a false positive rate of 0.017.
  • Accuracy in Challenging Scenarios: OSS correctly identifies causal parents in scenarios where ICP fails, particularly when only observational data is available or when interventions are limited.
  • Robustness to Nonlinearities: The method successfully identifies causal parents even when the relationships among non-causal variables are highly nonlinear.

Limitations and Future Work

  • Focus on Direct Parents: The current method focuses on identifying direct causal parents of a single target variable, not the entire causal graph. While this is a crucial sub-problem, full graph discovery is a more complex task.
  • Linearity Assumption for Direct Causes: The core assumption is that the direct causal relationships to the target variable are linear. While the paper shows this is sufficient for many cases, extending to nonlinear direct causes would be a valuable next step.
  • Hidden Confounders: While the paper explores the impact of hidden confounders, the method's performance can be affected, potentially returning a superset of true causal parents rather than a precise set. Further research into handling hidden confounders more robustly is suggested.
  • Assumptions on Noise: The method relies on certain assumptions about noise distributions (e.g., Gaussianity for statistical testing, though the core estimation is more general).
  • Future Work: The authors suggest exploring extensions to full causal graph discovery and investigating more sophisticated methods for handling hidden confounders. They also highlight the potential for this efficient algorithm in real-world applications like gene-phenotype analysis and system identification.

Summary updated

Abstract

The problem of inferring the direct causal parents of a response variable among a large set of explanatory variables is of high practical importance in many disciplines. Recent work exploits stability of regression coefficients or invariance properties of models across different experimental conditions for reconstructing the full causal graph. These approaches generally do not scale well with the number of the explanatory variables and are difficult to extend to nonlinear relationships. Contrary to existing work, we propose an approach which even works for observational data alone, while still offering theoretical guarantees including the case of partially nonlinear relationships. Our algorithm requires only one estimation for each variable and in our experiments we apply our causal discovery algorithm even to large graphs, demonstrating significant improvements compared to well established approaches.
BibTeX
@misc{raj2019orthogonal,
  author = {Anant Raj and Luigi Gresele and Michel Besserve and Bernhard Schölkopf and Stefan Bauer},
  title = {{Orthogonal Structure Search for Efficient Causal Discovery from Observational Data}},
  year = {2019},
  eprint = {1903.02456},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.02456},
}
Figure