On Searching for Generalized Instrumental Variables

Benito van der Zander, Maciej LiskiewiczAISTATS 2016 · OpenReview

Abstract: Instrumental Variables are a popular way to identify the direct causal effect of a random variable X on a variable Y. Often no single instrumental variable exists, although it is still possible to find a set of generalized instrumental variables (GIVs) and identify the causal effect of all these variables at once. Till now it was not known how to find GIVs systematically or even test efficiently, if given variables satisfy GIV conditions. We provide fast algorithms for searching and testing restricted cases of GIVs. However, we prove that in the most general case it is NP-hard to verify if given variables fulfill the conditions of a general instrumental sets.

The Challenge of Causal Identification

In causal inference, a primary goal is to estimate the direct effect of a treatment variable $X$ on an outcome $Y$. In real-world scenarios, this estimation is frequently confounded by unobserved variables that influence both $X$ and $Y$, leading to biased results. The traditional solution is the use of an Instrumental Variable (IV): a third variable $Z$ that is correlated with $X$ but affects $Y$ only through its influence on $X$.

However, in complex systems, finding a single variable that satisfies these strict criteria is often impossible. Researchers have turned to instrumental sets—groups of variables that collectively allow for the identification of multiple causal effects. While the theoretical foundations for these sets were established by Brito and Pearl, the field lacked efficient algorithms to search for these sets in large graphs or even to verify if a proposed set was valid. This research addresses that gap by providing a systematic algorithmic framework for Generalized Instrumental Variables (GIVs).

A Hierarchy of Instrumental Sets

The authors categorize instrumental sets into three distinct layers of increasing complexity, providing specific algorithmic solutions for each:

  1. Simple Instrumental Sets: These are the most direct extensions of the single IV to multiple variables. The authors present an $O(nm)$ algorithm to identify these sets.
  2. Simple Conditional Instrumental Sets: These sets allow for "conditioning" on a set of covariates $W$ to block non-causal paths. The authors utilize a "nearest separator" technique to identify $W$ efficiently.
  3. Generalized Instrumental Sets: This is the most flexible category, where each instrument in the set can have its own unique conditioning set.
Figure 2: Comparison between a standard instrumental variable (A) and a conditional instrumental set (B) where variable W is used to block confounding paths.

Algorithmic Framework and Complexity

To solve the path-finding requirements inherent in GIV conditions, the paper introduces a method to transform a causal Directed Acyclic Graph (DAG) into a specialized flow graph. This transformation allows the application of standard computer science techniques, such as max-flow and vertex-disjoint path algorithms, to causal inference problems.

Figure 5: The transformation of a causal graph G into a flow graph F(G) to facilitate the use of path-finding algorithms.

A major contribution of the paper is the proof that testing whether a set is a "Generalized Instrumental Set" is NP-complete. This explains why systematic discovery has been historically difficult. However, the authors demonstrate that the problem is Fixed-Parameter Tractable (FPT). If the size of the instrumental set $k$ is small—which is common in practical applications—the problem can be solved in polynomial time ($O(n^{4k+1})$).

Key Results

  • Simple Sets: Can be identified in $O(nm)$ time.
  • Simple Conditional Sets: Testing a candidate set is $O(nm)$; finding a set of size $k$ is $O(n^{d+3})$ if $k$ is bounded by $d$.
  • Generalized Sets: While testing is NP-complete in the general case, the authors provide a polynomial-time algorithm for cases where the set size $k$ is constant.
  • The Nearest Separator Shortcut: For conditional instruments, the authors show that searching all possible conditioning sets is unnecessary. A "nearest separator" can be found greedily in $O(nm)$ time, which is guaranteed to be valid if any such set exists.

Limitations and Future Work

While this work provides a robust algorithmic foundation, several challenges remain. The algorithm for generalized sets, while polynomial for constant $k$, becomes computationally expensive as the set size grows. Furthermore, the current framework is specifically designed for linear Structural Equation Models (SEMs). Extending these algorithmic efficiencies to non-parametric or non-linear models remains a significant frontier for future research. Finally, while the paper provides methods for testing sets, the problem of finding the optimal or maximal generalized set without exhaustive enumeration is still an open question.

Summary updated

Abstract

Instrumental Variables are a popular way to identify the direct causal effect of a random variable X on a variable Y. Often no single instrumental variable exists, although it is still possible to find a set of generalized instrumental variables (GIVs) and identify the causal effect of all these variables at once. Till now it was not known how to find GIVs systematically or even test efficiently, if given variables satisfy GIV conditions. We provide fast algorithms for searching and testing restricted cases of GIVs. However, we prove that in the most general case it is NP-hard to verify if given variables fulfill the conditions of a general instrumental sets.
BibTeX
@inproceedings{zander2016searching,
  author = {Benito van der Zander and Maciej Liskiewicz},
  title = {{On Searching for Generalized Instrumental Variables}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=cfnyVYJ66Dl},
}
Figure