Identifiability of homoscedastic linear structural equation models using algebraic matroids

Mathias Drton, Benjamin Hollering, Jun Wu

TL;DR

This paper introduces a novel algebraic approach using matroids to determine if different causal graph structures can be uniquely identified from observational data, even when these graphs contain feedback loops (cycles). The authors provide new graphical criteria that can distinguish between these complex causal models, extending previous work that was limited to acyclic graphs.

What Problem Does This Paper Address?

The core problem this paper tackles is structural identifiability in the context of linear structural equation models (SEMs). In essence, can we uniquely determine the underlying causal graph structure of a system given data generated by that system? While previous work has made significant progress for directed acyclic graphs (DAGs), this paper focuses on the more challenging scenario where feedback loops (cyclic graphs) are allowed. This is crucial because many real-world systems, like biological networks or economic markets, exhibit feedback mechanisms. The challenge lies in distinguishing between different cyclic graph structures that might produce statistically indistinguishable data distributions, especially under the simplifying assumption of homoscedastic errors (errors with equal variance).

Methods

The authors employ an algebraic statistics approach, moving beyond purely statistical methods. Their key innovation is the use of algebraic matroids, specifically the Jacobian matroid, derived from the parameterization of the SEMs.

Here's a breakdown of their approach:

  • Algebraic Variety: Each SEM is associated with an algebraic variety, which is essentially the set of all possible parameter values that generate the model.
  • Jacobian Matrix: The Jacobian matrix of the parameterization map captures how changes in the model parameters affect the observed data distribution.
  • Jacobian Matroid: A matroid is a combinatorial structure that captures notions of linear independence. The Jacobian matroid is derived from the linear independence of the columns of the Jacobian matrix.
  • Identifiability Criterion: The core idea is that if two different graphs (and thus two different SEMs) have different Jacobian matroids, then their corresponding statistical models are generically distinguishable. This means that, with probability one, data generated from one graph will not be explainable by the other.
  • Graphical Conditions: The paper translates these matroid properties into concrete, checkable graphical conditions, making the identifiability results more accessible.

This approach is novel because it leverages the combinatorial structure of matroids to avoid computationally intensive Gröbner basis calculations, which are often required in algebraic geometry for identifiability proofs.

Datasets

Not discussed in the paper. The paper focuses on theoretical conditions for identifiability based on graph structures rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Matroids as a Powerful Tool: Algebraic matroids provide a surprisingly effective way to characterize and prove identifiability for complex statistical models, even those with cyclic dependencies.
  • Bridging Algebra and Causality: The paper elegantly connects abstract algebraic concepts (matroids) to concrete causal structures (directed graphs), offering a new lens for understanding causal inference.
  • Cyclic Graphs are Distinguishable: The work demonstrates that even with homoscedastic errors, many cyclic graph structures are distinguishable, a significant step beyond previous limitations.
  • Graphical Criteria for Identifiability: The translation of matroid properties into graphical conditions (like out-degree sequences and transitive triangle-freeness) makes these theoretical results practically applicable.
  • Limitations of Graphical Criteria: The paper also highlights that while graphical criteria are useful, they are not always sufficient, especially for complete graphs, suggesting that more advanced techniques might be needed in some cases.

Key Results

The paper establishes several key results:

  • Sufficient Conditions for Distinguishability: They derive sufficient graphical conditions that guarantee two simple directed graphs (and their corresponding SEMs) have different Jacobian matroids, implying they are generically identifiable. These conditions include:
  • Graphs with different out-degree sequences.
  • Graphs that are "transitive triangle-free" (a specific structural property).
  • A more general condition based on "parentally closed sets."
  • Generic Identifiability of Subclasses: They identify subclasses of graphs, including those with directed cycles, that are generically identifiable using their criteria.
  • Conjectures for Broader Applicability: The authors propose conjectures that suggest their graphical criteria can distinguish many more non-complete graphs and explore the conditions under which complete graphs might share the same matroid.

Limitations and Future Work

  • Focus on Homoscedastic Errors: The current framework is specifically for homoscedastic linear SEMs. Extending these methods to heteroscedastic errors or nonlinear models would be a significant future direction.
  • Sufficient, Not Necessary Conditions: The graphical conditions derived are sufficient for distinguishability, meaning if the conditions are met, the graphs are distinguishable. However, if the conditions are not met, it doesn't necessarily mean the graphs are indistinguishable.
  • Complete Graphs: The paper notes that for complete graphs, their matroid-based approach may not be sufficient to distinguish all models, even if they are statistically different. This suggests a need for new graphical criteria or alternative methods for these cases.
  • Computational Complexity: While the matroid approach is more efficient than Gröbner bases, checking the more general graphical conditions can still be computationally intensive for very large graphs.
  • Conjectures: The paper explicitly states conjectures that require further theoretical or computational validation, particularly regarding the distinguishability of non-complete graphs and the behavior of complete graphs.

Summary updated

Abstract

We consider structural equation models (SEMs), in which every variable is a function of a subset of the other variables and a stochastic error. Each such SEM is naturally associated with a directed graph describing the relationships between variables. When the errors are homoscedastic, recent work has proposed methods for inferring the graph from observational data under the assumption that the graph is acyclic (i.e., the SEM is recursive). In this work, we study the setting of homoscedastic errors but allow the graph to be cyclic (i.e., the SEM to be non-recursive). Using an algebraic approach that compares matroids derived from the parameterizations of the models, we derive sufficient conditions for when two simple directed graphs generate different distributions generically. Based on these conditions, we exhibit subclasses of graphs that allow for directed cycles, yet are generically identifiable. We also conjecture a strengthening of our graphical criterion which can be used to distinguish many more non-complete graphs.
BibTeX
@article{drton2025identifiability,
  author = {Mathias Drton and Benjamin Hollering and Jun Wu},
  title = {{Identifiability of homoscedastic linear structural equation models using algebraic matroids}},
  journal = {Adv. Appl. Math.},
  year = {2025},
  doi = {10.1016/j.aam.2024.102794},
}
Figure