Abstract
Causal discovery aims to infer causal relationships from observational data. While Directed Acyclic Graphs (DAGs) are the standard tool, they struggle with categorical data where relationships are often context-dependent. This paper introduces a framework using staged tree models, providing a graphical equivalence criterion, a novel interventional distance metric (CID), and demonstrating superior performance over DAG-based methods in capturing asymmetric causal structures.
Introduction: Beyond Symmetric DAGs
Standard causal discovery algorithms typically assume symmetric relationships: if $X$ causes $Y$, the functional relationship is assumed constant across all contexts. However, categorical data frequently exhibits context-specific independence. For instance, a person's behavior might depend on a specific factor only under certain conditions. Standard DAGs fail to represent these nuances without excessive complexity. Staged trees offer a rooted tree representation of the entire outcome space, allowing for a more granular and flexible approach to causality.
Methodology: Staged Trees and the CID Metric
Staged tree models represent variables as depths in a tree. A key innovation is staging: grouping vertices at the same depth into "stages" if they share the same conditional probability distribution for the subsequent variable. This "collapses" identical causal effects and identifies context-specific independencies, as shown in the complex branching and coloring of a staged tree.
To compare these models, the authors introduce the Context-Specific Interventional Discrepancy (CID). Inspired by the Structural Intervention Distance (SID) used for DAGs, CID quantifies differences in causal statements between two staged trees. This metric is robust even in the complex, asymmetric relationships where traditional metrics falter.
Experimental Evaluation and Results
The framework was tested on synthetic data and real-world datasets, including COVID-19 patient trajectories and climate phenomena. The authors compared staged tree learning algorithms—specifically Backward Hill-Climbing (BHC) and a k-means clustering approach—against established DAG-based algorithms like Tabu search and MMHC.
The results consistently showed that staged tree methods, particularly BHC, outperformed DAG-based algorithms in recovering true causal orders and minimizing interventional discrepancy. In a SARS-CoV-2 application, the staged tree model provided a significantly better fit (lower BIC) than the best DAG, highlighting its ability to capture the "messy" reality of medical data.
Conclusion
Staged trees represent a significant advancement in causal discovery for categorical data. By embracing asymmetry rather than smoothing it over, these models provide more accurate and explainable causal insights. Future work will focus on improving the scalability of these search algorithms for higher-dimensional datasets.
Summary updated