Efficient Identification in Linear Structural Causal Models with Instrumental Cutsets

Daniel Kumor, Bryant Chen, Elias Bareinboim

One of the most common mistakes made when performing data analysis is attributing causal meaning to regression coefficients. Formally, a causal effect can only be computed if it is identifiable from a combination of observational data and structural knowledge about the domain under investigation. This paper tackles the challenge of identifying causal effects in linear systems without needing to run expensive experiments. The authors introduce "Instrumental Cutsets" (IC), a new polynomial-time algorithm that is more powerful than previous efficient methods, and they prove that one of the most popular high-power alternatives is actually NP-Complete.

The Challenge of Causal Identification

In data science, we often want to know the "causal effect" of one variable on another—for example, how much a specific drug dosage changes a patient's blood pressure. In a perfect world, we’d run a randomized controlled trial. In the real world, we often only have observational data and a "causal graph" representing our domain knowledge.

Examples of causal graphs used to determine identifiability.

The process of calculating these effects from observational data is called identification. For linear Structural Causal Models (SCMs), researchers have developed a "ladder" of methods, ranging from simple Instrumental Variables (IVs) to complex algebraic approaches. However, there has always been a frustrating trade-off:

  1. Efficient methods (like IVs) are fast but often fail to find effects in complex graphs.
  2. Powerful methods (like TSID or Gröbner bases) can find almost any identifiable effect but are "exponential-time," meaning they become impossibly slow as the number of variables grows.

The authors aim to bridge this gap by creating a method that is both highly powerful and computationally efficient (polynomial-time).

Core Contributions and Methods

The paper introduces three major technical contributions to advance the field of causal discovery:

1. Match-Blocking Algorithm

Many previous algorithms were slow because they tried to check every possible subset of a node's parents to find "instruments." The authors developed a clever algorithm based on max-flow (a standard graph theory technique) that finds these subsets in polynomial time, bypassing the need for exhaustive searching. The realization that the search for valid instrumental sets can be framed as a network flow problem allows researchers to use decades of optimized graph theory research to solve causal problems.

2. NP-Completeness Proof

They formally prove that finding a "tsIV" (the core of the powerful TSID method) is NP-Complete. This is a "stop sign" for researchers, showing that we shouldn't expect to find a perfectly efficient algorithm for that specific criterion. By proving this, the authors provide a clear boundary for what is computationally feasible in causal inference, steering the field toward more practical solutions.

3. Instrumental Cutsets (IC)

This is the paper's "hero" method. It combines the idea of auxiliary variables (using previously identified causal links to help find new ones) with flow constraints in the causal graph.

Complex causal graphs illustrating flow constraints and instrumental cutsets.

By looking for "bottlenecks" (cutsets) in the flow of information through the graph, the IC criterion can identify causal parameters that previous efficient algorithms would miss. The authors prove that their new IC criterion is strictly more powerful than several existing standards, specifically the generalized Half-Trek Criterion (gHTC) and Auxiliary Variable Sets (AVS). If those methods can find an effect, IC can too—and it can find even more.

Key Results

  • Efficiency Gains: The paper transforms several algorithms that were previously exponential-time (due to subset enumeration) into polynomial-time algorithms.
  • Identification Power: The authors demonstrate that IC has "very high" power and is "efficient", a combination previously thought to be out of reach for such a broad class of models.
  • Algorithmic Implementation: The authors provide concrete pseudocode for finding maximal match-blocks and solving for edges using Instrumental Cutsets, making the theory ready for practical software implementation.

Limitations and Future Work

While Instrumental Cutsets are a major step forward, they aren't a "silver bullet" for every causal problem:

  • Non-Linearity: This work is strictly for linear models. While linear models are common in economics and social sciences, they don't capture the complex, non-linear interactions found in many biological or physical systems.
  • The "cAV" Gap: The authors acknowledge that a method called "conditional Auxiliary Variables" (cAV) can still identify some effects that IC cannot. However, finding a way to automate cAV efficiently remains an open challenge.
  • Graph Accuracy: Like all graphical identification methods, IC is only as good as the causal graph you give it. If your structural knowledge of the domain is wrong, the identified causal effects will be biased.

Summary updated

Abstract

One of the most common mistakes made when performing data analysis is attributing causal meaning to regression coefficients. Formally, a causal effect can only be computed if it is identifiable from a combination of observational data and structural knowledge about the domain under investigation (Pearl, 2000, Ch. 5). Building on the literature of instrumental variables (IVs), a plethora of methods has been developed to identify causal effects in linear systems. Almost invariably, however, the most powerful such methods rely on exponential-time procedures. In this paper, we investigate graphical conditions to allow efficient identification in arbitrary linear structural causal models (SCMs). In particular, we develop a method to efficiently find unconditioned instrumental subsets, which are generalizations of IVs that can be used to tame the complexity of many canonical algorithms found in the literature. Further, we prove that determining whether an effect can be identified with TSID (Weihs et al., 2017), a method more powerful than unconditioned instrumental sets and other efficient identification algorithms, is NP-Complete. Finally, building on the idea of flow constraints, we introduce a new and efficient criterion called Instrumental Cutsets (IC), which is able to solve for parameters missed by all other existing polynomial-time algorithms.
BibTeX
@inproceedings{kumor2019efficient,
  author = {Daniel Kumor and Bryant Chen and Elias Bareinboim},
  title = {{Efficient Identification in Linear Structural Causal Models with Instrumental Cutsets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=rR47VHy-v1O},
}
Figure