Generic Identifiability of Linear Structural Equation Models by Ancestor\n Decomposition

Mathias Drton, Luca Weihs

Abstract

Linear structural equation models, which relate random variables via linear interdependencies and Gaussian noise, are a popular tool for modeling multivariate joint distributions. These models correspond to mixed graphs that include both directed and bidirected edges representing the linear relationships and correlations between noise terms, respectively. A question of interest for these models is that of parameter identifiability, whether or not it is possible to recover edge coefficients from the joint covariance matrix of the random variables. For the problem of determining generic parameter identifiability, we present an algorithm that extends an algorithm from prior work by Foygel, Draisma, and Drton (2012). The main idea underlying our new algorithm is the use of ancestral subsets of vertices in the graph in application of a decomposition idea of Tian (2005).

Introduction

In fields ranging from biology to economics, researchers use Linear Structural Equation Models (SEMs) to represent complex causal relationships. These models are visualized as mixed graphs where directed arrows ($\to$) represent causal effects and bidirected arrows ($\leftrightarrow$) represent correlations between noise terms. A fundamental challenge in using these models is identifiability: determining if the strength of every arrow (the parameters) can be uniquely recovered from the observed covariance matrix of the variables.

While the Half-Trek Criterion (HTC) has long served as a standard test for identifiability, it often remains inconclusive for dense or complex graphs. This paper introduces a new algorithm that extends the HTC by breaking down complex graphs into smaller, more manageable "ancestral" sub-components, effectively shrinking the gap of inconclusive cases without increasing computational complexity.

Methodology: Ancestor Decomposition

The authors' primary innovation lies in combining the HTC with Tian Decomposition, a method that partitions a graph into "mixed components" based on noise term connectivity. The core theoretical breakthrough is a "local-to-global" property: if a subgraph induced by an ancestral set (a subset of variables including all their ancestors) is identifiable, then those specific edge coefficients are also identifiable in the original, larger graph.

Decomposition of an HTC-inconclusive graph into ancestral sub-components.

The resulting Algorithm 1 iteratively performs the following steps:

  1. Identifies ancestral subsets within the graph.
  2. Applies Tian decomposition to these subsets to create mixed components.
  3. Uses the HTC to solve for coefficients within these smaller pieces.

Experimental Evaluation

To evaluate the algorithm, the authors employed a simulation-based approach rather than real-world datasets. They developed Algorithm 2 to generate thousands of random acyclic mixed graphs with varying node counts ($n=6$ to $12$) and edge densities. To rigorously test their innovation, they specifically filtered for 1,000 "HTC-inconclusive" cases—graphs where the standard HTC algorithm failed to provide a definitive answer—and applied their new decomposition method to this difficult subset.

Key Results and Insights

  • Strict Improvement over HTC: The new algorithm is a proper extension of the HTC. It successfully identifies all cases the original HTC can, plus a significant number of cases where the previous standard was inconclusive.
  • Quantifiable Gains in Complexity: In the targeted simulations of inconclusive graphs, the algorithm successfully identified between 0.5% and 2.5% of previously unsolvable cases. The most pronounced improvements occurred in graphs with high directed edge density, where ancestral structures are more complex and beneficial for decomposition.
  • Computational Efficiency: Despite its increased power, the algorithm maintains a worst-case time complexity of $O(|V|^5)$, ensuring it remains practical for moderately sized models used in empirical research.

Conclusion

By nesting Tian's decomposition within an ancestral search, the authors have provided a more powerful tool for causal inference. While the gains are described as "modest," they represent a mathematically sound advancement in solving previously intractable structural models. Future work may explore whether polynomial-time algorithms can consider even broader classes of ancestral subsets or if further decomposition rules can be integrated to further reduce the number of inconclusive graphs.

Summary updated

Abstract

Linear structural equation models, which relate random variables via linear\ninterdependencies and Gaussian noise, are a popular tool for modeling\nmultivariate joint distributions. These models correspond to mixed graphs that\ninclude both directed and bidirected edges representing the linear\nrelationships and correlations between noise terms, respectively. A question of\ninterest for these models is that of parameter identifiability, whether or not\nit is possible to recover edge coefficients from the joint covariance matrix of\nthe random variables. For the problem of determining generic parameter\nidentifiability, we present an algorithm that extends an algorithm from prior\nwork by Foygel, Draisma, and Drton (2012). The main idea underlying our new\nalgorithm is the use of ancestral subsets of vertices in the graph in\napplication of a decomposition idea of Tian (2005).\n
BibTeX
@inproceedings{drton2016generic,
  author = {Mathias Drton and Luca Weihs},
  title = {{Generic Identifiability of Linear Structural Equation Models by Ancestor\textbackslash\{\}n Decomposition}},
  booktitle = {Scandinavian},
  year = {2016},
  doi = {10.1111/sjos.12227},
}
Figure