Context-Specific Causal Discovery for Categorical Data Using Staged Trees

Manuele Leonelli, Gherardo VarandoAISTATS 2023

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.

Figure 6: A staged tree model where nodes are grouped into colored stages representing shared conditional probability distributions, allowing for the representation of asymmetric causal relationships.

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.

Figure 5: Performance comparison of staged tree algorithms (BHC, k-means) vs. DAG-based methods (Tabu, MMHC) across varying sample sizes (N) and complexity (k), showing lower interventional discrepancy (CID) for the proposed methods.

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

BibTeX
@inproceedings{leonelli2023context,
  author = {Manuele Leonelli and Gherardo Varando},
  title = {{Context-Specific Causal Discovery for Categorical Data Using Staged Trees}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
}
Figure