Algebraic Equivalence Class Selection for Linear Structural Equation Models

Thijs van Ommen, Joris M. MooijUAI 2017 · OpenReview

Introduction

In causal discovery, inferring the underlying structure of a system from observed data is a fundamental challenge. Traditionally, researchers have relied on Markov equivalence, where two graphs are considered indistinguishable if they imply the same conditional independence relationships. However, linear structural equation models (SEMs) often impose "hidden" algebraic equality constraints that are not captured by standard conditional independence tests. This paper introduces the concept of algebraic equivalence, providing a more refined framework to distinguish between causal models by leveraging these additional signatures.

Beyond Markov Equivalence

Standard algorithms like PC or FCI often miss signals from non-independence equality constraints, such as the famous Verma constraint. By focusing solely on vanishing correlations, these methods fail to exploit the full set of constraints imposed by a graph. The authors demonstrate that conditional independence is merely a subset of a broader class of equality constraints that can be used for model selection.

Hierarchy of equality constraints in linear SEMs, showing that vanishing correlations are a subset of broader algebraic constraints.

Methodology: The Half-Trek Criterion

The proposed framework is built upon the half-trek criterion (HTC), a graphical tool used to determine the identifiability of parameters in linear SEMs.

  1. Constraint Enumeration: For HTC-identifiable graphs, the authors provide an efficient method to derive a complete list of rational and polynomial equality constraints, moving beyond simple independence.
  2. Defining Algebraic Equivalence: Two models are defined as algebraically equivalent if they share the same Zariski closure. This means they are indistinguishable based on any equality constraints, even if they differ in terms of measure-zero inequality constraints.
  3. Graphical Criteria: The paper proves theorems that allow for the identification of equivalence classes based on graph structure alone, avoiding computationally expensive algebraic geometry tools like Gröbner bases.
Examples of algebraically equivalent mixed graphs, demonstrating how different structures can impose identical equality constraints.

Experimental Results and Insights

The authors evaluated their approach using simulated datasets and a complete enumeration of 4-node acyclic mixed graphs.

  • Massive Search Space Reduction: For 4-node graphs, the 34,752 possible structures collapse into only 389 algebraic equivalence classes. This reduction drastically simplifies the "menu" a model selection algorithm needs to evaluate.
  • Improved Precision: In experiments detecting "Y-structures," using algebraic equivalence as a filter improved precision by approximately 0.1 compared to standard Markov-based filtering, with minimal impact on recall (maintaining over 98%).
  • Computational Efficiency: By selecting the most computationally "easy" representative (such as a DAG) from an equivalence class to calculate scores like BIC, the method avoids the convergence issues common when fitting models with many bidirected edges.

Conclusion and Future Work

This work demonstrates that accounting for algebraic signatures significantly boosts the accuracy of causal discovery in linear SEMs. While currently limited to linear models and constrained by the completeness of the HTC, the transition from Markov to algebraic equivalence represents a major step forward in identifying causal structures from observational data. Future research will focus on scaling these insights to larger graphs and exploring non-linear extensions.

Summary updated

BibTeX
@inproceedings{ommen2017algebraic,
  author = {Thijs van Ommen and Joris M. Mooij},
  title = {{Algebraic Equivalence Class Selection for Linear Structural Equation Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=Z5yvOwXLp_Y},
}
Figure