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