Determinantal Generalizations of Instrumental Variables

Luca Weihs, Bill Robinson, Emilie Dufresne, Jennifer Kenkel, Kaie Kubjas, McGee Ii Reginald, Nhan Nguyen, Elina Robeva, Mathias Drton

TL;DR

This paper expands our ability to identify causal effects in complex linear models by generalizing the classic "Instrumental Variable" formula into a framework of determinantal ratios. By moving from a node-centric to an edge-centric approach, the authors provide new sufficient and necessary conditions that successfully identify causal parameters in many graphs where previous state-of-the-art methods failed.

What Problem Does This Paper Address?

In the world of Linear Structural Equation Models (L-SEMs), researchers use mixed graphs to represent how variables interact. Directed edges ($v \to w$) represent direct causal effects, while bidirected edges ($v \leftrightarrow w$) represent unobserved confounding—hidden factors that influence both variables.

The big question is generic identifiability: can we uniquely recover the numerical values of these causal effects (the edge coefficients) just by looking at the observed covariance matrix of the data?

For years, the Half-Trek Criterion (HTC) was the gold standard for answering this. It uses "treks" (paths through the graph) to find systems of linear equations that can be solved for the parameters. However, the HTC is often "inconclusive"—it might say a graph could be identifiable, but it can't prove it. This paper tackles that gap, providing more powerful tools to "crack" these inconclusive graphs.

Methods

The authors introduce two primary innovations that extend the HTC:

  1. Identification by Ratios of Determinants: The classic Instrumental Variable (IV) formula is actually a simple ratio of covariances. The authors show that in more complex graphs, edge coefficients can be recovered as quotients of subdeterminants of the covariance matrix. They use "trek separation" (t-separation) to characterize the rank of these submatrices, allowing them to find the right "determinantal constraints" to isolate specific edge weights.
  2. The Edgewise Half-Trek Criterion (EID): The original HTC is "all-or-nothing"—it tries to identify all incoming edges to a node simultaneously. The authors propose an edgewise version that operates on subsets of a node's parents. This "divide and conquer" strategy allows the algorithm to iteratively solve for edges one by one, building on previously identified parameters.

They combine these into a unified algorithm (EID+TSID) that alternates between determinantal identification and edgewise HTC steps.

Datasets

As a theoretical and algorithmic paper, it does not use real-world observational datasets. Instead, it evaluates its methods using established benchmarks of small, complex graphs:

  • 112 Acyclic Mixed Graphs: A set of 5-node graphs identified by Foygel et al. (2012b) as being generically identifiable but "inconclusive" under the standard HTC.
  • 75 Cyclic Mixed Graphs: A set of randomly chosen 5-node graphs containing feedback loops that are known to be identifiable but fail the HTC.

Key Insights and Ideas

  • The IV Generalization: The most elegant "aha moment" is the realization that the IV method is just the $1 \times 1$ case of a much broader determinantal rule. By looking at $k \times k$ submatrices, we can find "generalized instruments" even in highly confounded networks.
  • Breaking the Symmetry: Traditional methods often treat all parents of a node as a single block. By focusing on individual edges, the authors show that you can leverage "partial" information. If you can identify one parent's effect, it simplifies the problem for the remaining parents.
  • Trek-Separation as a Rank Tool: The paper masterfully uses the "Trek Rule" (which relates graph paths to covariance entries) to transform graphical separation properties into matrix rank properties, which are then used to build solvable equation systems.

Key Results

The authors implemented their algorithms in the R package SEMID and tested them against the "hard" cases where the standard HTC failed:

  • Acyclic Success: Out of the 112 "inconclusive" acyclic graphs, the new EID+TSID algorithm successfully identified 98 (87.5%).
  • Cyclic Success: Out of the 75 "inconclusive" cyclic graphs, it identified 34 (45.3%).
  • Synergy Matters: Interestingly, the "Edgewise" (EID) method alone only solved 23 acyclic graphs, and the "Trek-Separation" (TSID) method alone solved 0. It was the combination of the two that provided the massive jump in performance, showing that these two mathematical perspectives are highly complementary.

Limitations and Future Work

  • Computational Complexity: Finding the optimal sets of variables ($S$ and $T$) to form the determinants is a search problem that the authors suspect might be NP-hard. Currently, they handle this by limiting the search to small subsets, which works for 5-node graphs but might struggle as models scale up.
  • Beyond Single Edges: While the paper focuses on identifying edges one at a time, Example 7.1 hints at a $2 \times 2$ system where two edges are identified simultaneously through a more complex determinantal equation. Developing the mathematical theory to certify these multi-edge systems is a clear next step.
  • Necessary vs. Sufficient: While they provide a new necessary condition for non-identifiability (Theorem 5.2), there is still a gap between what we can prove is identifiable and what we can prove is not. Closing this gap remains the "holy grail" of the field.

Summary updated

Abstract

Abstract Linear structural equation models relate the components of a random vector using linear interdependencies and Gaussian noise. Each such model can be naturally associated with a mixed graph whose vertices correspond to the components of the random vector. The graph contains directed edges that represent the linear relationships between components, and bidirected edges that encode unobserved confounding. We study the problem of generic identifiability, that is, whether a generic choice of linear and confounding effects can be uniquely recovered from the joint covariance matrix of the observed random vector. An existing combinatorial criterion for establishing generic identifiability is the half-trek criterion (HTC), which uses the existence of trek systems in the mixed graph to iteratively discover generically invertible linear equation systems in polynomial time. By focusing on edges one at a time, we establish new sufficient and new necessary conditions for generic identifiability of edge effects extending those of the HTC. In particular, we show how edge coefficients can be recovered as quotients of subdeterminants of the covariance matrix, which constitutes a determinantal generalization of formulas obtained when using instrumental variables for identification. While our results do not completely close the gap between existing sufficient and necessary conditions we find, empirically, that our results allow us to prove the generic identifiability of many more mixed graphs than the prior state-of-the-art.
BibTeX
@article{weihs2017determinantal,
  author = {Luca Weihs and Bill Robinson and Emilie Dufresne and Jennifer Kenkel and Kaie Kubjas and McGee II Reginald and Nhan Nguyen and Elina Robeva and Mathias Drton},
  title = {{Determinantal Generalizations of Instrumental Variables}},
  journal = {Journal of Causal Inference},
  year = {2017},
  doi = {10.1515/jci-2017-0009},
}

Loading related content...

Figure