Determinantal Generalizations of Instrumental Variables

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

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 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.

Introduction: The Challenge of Causal Identification

In Linear Structural Equation Models (L-SEMs), researchers utilize mixed graphs to represent the complex web of interactions between variables. In these graphs, directed edges ($v \to w$) signify direct causal effects, while bidirected edges ($v \leftrightarrow w$) represent unobserved confounding—hidden factors that influence multiple observed variables simultaneously.

A simple mixed graph illustrating directed causal effects (blue) and unobserved confounding (red).

The fundamental problem in this domain is generic identifiability: determining whether the numerical values of these causal effects (the edge coefficients) can be uniquely recovered from the observed covariance matrix of the data. For years, the Half-Trek Criterion (HTC) served as the primary tool for this task, using "trek systems" to identify systems of linear equations. However, the HTC often remains inconclusive for many complex graphs. This paper introduces a more powerful framework to address these gaps.

Methods: Extending the Half-Trek Criterion

The authors propose two primary innovations that significantly extend the capabilities of the HTC:

1. Identification by Ratios of Determinants (TSID)

The classic Instrumental Variable (IV) formula is a simple ratio of covariances. This paper demonstrates that in more complex graphs, edge coefficients can be recovered as quotients of subdeterminants of the covariance matrix. By utilizing "trek separation" (t-separation), the authors characterize the rank of specific submatrices, allowing them to identify the "determinantal constraints" necessary to isolate individual edge weights.

2. The Edgewise Half-Trek Criterion (EID)

While the original HTC attempts to identify all incoming edges to a node simultaneously, the authors propose an edgewise version. This "divide and conquer" strategy operates on subsets of a node's parents, allowing the algorithm to iteratively solve for edges one by one. This approach leverages previously identified parameters to simplify the identification of remaining edges.

Transformation of a mixed graph (a) into a bipartite representation (b) used for trek-separation and half-trek analysis.

The authors combine these methods into a unified algorithm (EID+TSID) that alternates between determinantal identification and edgewise HTC steps, creating a synergistic effect that outperforms either method used in isolation.

Results and Discussion

The effectiveness of the EID+TSID algorithm was evaluated using benchmarks of small, complex graphs known to be "inconclusive" under the standard HTC. The algorithms were implemented in the R package SEMID and tested against these hard cases:

  • Acyclic Graphs: Out of 112 inconclusive acyclic graphs, the new algorithm successfully identified 98 (87.5%).
  • Cyclic Graphs: Out of 75 inconclusive cyclic graphs (containing feedback loops), it identified 34 (45.3%).

The results highlight that the "Edgewise" (EID) and "Trek-Separation" (TSID) methods are highly complementary. While EID alone solved 23 acyclic graphs and TSID alone solved none, their combination provided a massive jump in performance. This suggests that the two mathematical perspectives—one focusing on iterative local identification and the other on global determinantal constraints—are both necessary for solving complex causal models.

Conclusion and Future Work

This research expands the frontier of causal identification by generalizing the IV method into a framework of determinantal ratios. By shifting from a node-centric to an edge-centric approach, the authors provide new sufficient and necessary conditions for identifiability.

Future work will address the computational complexity of searching for optimal variable sets to form determinants, which may be NP-hard. Additionally, extending the theory to certify multi-edge systems—where multiple parameters are identified simultaneously through complex determinantal equations—remains a key objective in closing the gap between what is identifiable and what can be proven.

Summary updated

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 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.
BibTeX
@article{weihs2017determinantal,
  author = {Luca Weihs and Bill Robinson and Emilie Dufresne and Jennifer Kenkel and Kaie Kubjas and Reginald L. McGee 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},
}
Figure