Structural Intervention Distance (SID) for Evaluating Causal Graphs

Jonas Peters, Peter BühlmannarXiv 2013 · DOI · arXiv

Abstract

Causal inference relies on the structure of a graph, often a directed acyclic graph (DAG). Different graphs may result in different causal inference statements and different intervention distributions. To quantify such differences, we propose a (pre-) distance between DAGs, the structural intervention distance (SID). The SID is based on a graphical criterion only and quantifies the closeness between two DAGs in terms of their corresponding causal inference statements. It is therefore well-suited for evaluating graphs that are used for computing interventions. Instead of DAGs it is also possible to compare CPDAGs, completed partially directed acyclic graphs that represent Markov equivalence classes. Since it differs significantly from the popular Structural Hamming Distance (SHD), the SID constitutes a valuable additional measure. We discuss properties of this distance and provide an efficient implementation with software code available on the first author's homepage.

Introduction

In causal discovery, the primary objective is to learn the "true" Directed Acyclic Graph (DAG) from observational data. Traditionally, the performance of discovery algorithms is evaluated using the Structural Hamming Distance (SHD), which counts the number of edge additions, deletions, or reversals required to transform one graph into another.

However, SHD is often "causally blind." In a causal system, not all edges carry equal weight. For instance, reversing a critical edge at the top of a causal hierarchy can fundamentally alter the predicted effects of interventions, whereas adding an extraneous edge between two nodes might have negligible impact. Researchers who intend to use discovered graphs for predicting the effects of actions (using Pearl's do-calculus) require a metric that reflects the accuracy of these causal predictions rather than mere structural similarity.

The Structural Intervention Distance (SID)

To address this, we introduce the Structural Intervention Distance (SID). Unlike SHD, SID quantifies the number of variable pairs $(i, j)$ for which an estimated graph $H$ fails to correctly predict the intervention distribution of $j$ given an intervention on $i$, relative to the true graph $G$.

Example of a complex Directed Acyclic Graph (DAG) used for causal inference.

The metric is built on several key technical foundations:

  • Parent Adjustment: SID assumes that the effect of an intervention is calculated via the "adjustment for parents" formula. If the set of parents for a variable in the estimated graph $H$ is a valid adjustment set in the true graph $G$, the prediction is considered correct.
  • Graphical Criterion: SID can be computed using a purely graphical approach based on paths and descendants, eliminating the need for data simulation during evaluation.
  • CPDAG Compatibility: Since many algorithms identify Markov equivalence classes (CPDAGs) rather than unique DAGs, the paper provides efficient methods to calculate lower and upper bounds for SID within these classes.

Key Insights and Properties

The most significant takeaway is that SHD does not equal SID. A low SHD does not guarantee a low SID, and vice versa.

Comparison of a true graph $G$ with two estimates, $H_1$ and $H_2$.

As illustrated in the figure above:

  1. The Subgraph Property: If the true graph $G$ is a subgraph of the estimate $H$ (as seen in $H_1$), the SID is zero. From a causal perspective, over-fitting (adding extra edges) is "safer" than missing edges or misidentifying directions, as extra edges do not necessarily invalidate parent adjustment.
  2. Asymmetry: SID is a "pre-metric" and is not symmetric. The distance from $G$ to $H$ is not the same as from $H$ to $G$, reflecting the privileged status of the "ground truth" in causal analysis.
  3. Utility-Driven Evaluation: SID provides a practical roadmap. A high upper-bound SID indicates that even a structurally "close" graph could lead to erroneous policy interventions. In the example above, $H_2$ reverses a top-level edge, leading to a high SID despite having the same SHD as $H_1$.

Experimental Validation

The SID was validated using 10,000 pairs of random DAGs and Linear Gaussian Structural Equation Models (SEMs). In 20,000 test cases, the SID perfectly matched the number of incorrectly estimated numerical causal effects, confirming that the graphical criterion is a reliable proxy for actual inference errors.

Benchmarking established algorithms like the PC algorithm and Greedy Equivalence Search (GES) revealed that while the PC algorithm often achieves low SHD by correctly identifying the graph "skeleton," it can suffer from high SID due to difficulties in edge orientation.

Conclusion and Future Work

SID offers a more meaningful metric for causal discovery by prioritizing the functional utility of graphs. Future work includes extending SID to handle multiple simultaneous interventions and relaxing the assumption of causal sufficiency to include hidden variables via Maximal Ancestral Graphs (MAGs). Currently, the implementation scales efficiently ($O(p^3)$ for dense graphs), making it suitable for practical research applications.

Summary updated

Abstract

Causal inference relies on the structure of a graph, often a directed acyclic graph (DAG). Different graphs may result in different causal inference statements and different intervention distributions. To quantify such differences, we propose a (pre-) distance between DAGs, the structural intervention distance (SID). The SID is based on a graphical criterion only and quantifies the closeness between two DAGs in terms of their corresponding causal inference statements. It is therefore well-suited for evaluating graphs that are used for computing interventions. Instead of DAGs it is also possible to compare CPDAGs, completed partially directed acyclic graphs that represent Markov equivalence classes. Since it differs significantly from the popular Structural Hamming Distance (SHD), the SID constitutes a valuable additional measure. We discuss properties of this distance and provide an efficient implementation with software code available on the first author's homepage (an R package is under construction).
BibTeX
@misc{peters2013structural,
  author = {Jonas Peters and Peter Bühlmann},
  title = {{Structural Intervention Distance (SID) for Evaluating Causal Graphs}},
  year = {2013},
  eprint = {1306.1043},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1306.1043},
}
Figure