Testing Edges by Truncations

Ilya Shpitser, Thomas S. Richardson, James M. RobinsIJCAI 2009 · OpenReview

Abstract

We consider the problem of testing whether two variables should be adjacent (either due to a direct effect between them, or due to a hidden common cause) given an observational distribution, and a set of causal assumptions encoded as a causal diagram. In other words, given a set of edges in the diagram known to be true, we are interested in testing whether another edge ought to be in the diagram. In fully observable faithful models this problem can be easily solved with conditional independence tests. Latent variables make the problem significantly harder since they can imply certain non-adjacent variable pairs, namely those connected by so called inducing paths, are not independent conditioned on any set of variables. We characterize which variable pairs can be determined to be non-adjacent by a class of constraints due to dormant independence, that is conditional independence in identifiable interventional distributions. Furthermore, we show that particular operations on joint distributions, which we call truncations are sufficient for exhibiting these non-adjacencies. This suggests a causal discovery procedure taking advantage of these constraints in the latent variable case can restrict itself to truncations.

Introduction

In the field of causal discovery, identifying the structure of a system from observational data is a fundamental challenge. Under the assumption of causal sufficiency—where all common causes of observed variables are themselves observed—the task is relatively straightforward: conditional independence tests can reveal the absence of direct causal edges. However, real-world systems are frequently characterized by latent variables (unobserved common causes).

The Verma graph (a), a canonical example where latent variables create inducing paths that necessitate higher-order constraints for edge testing.

Latent variables introduce "inducing paths" that can maintain dependencies between variables regardless of the conditioning set. This complexity gives rise to Verma constraints—statistical restrictions that are more complex than simple conditional independences. This paper addresses the formal identification of which edges can be tested (proven absent) using these higher-order constraints.

Methodology: Truncations and Dormant Independence

The authors propose a framework based on Probabilistic Causal Models (PCMs) and do-calculus to systematically uncover hidden constraints. The core of their approach lies in two concepts:

  1. Dormant Independence: A conditional independence that holds only in an interventional distribution (e.g., $P(y | do(x), z)$) rather than the original observational distribution.
  2. The Truncation Operation: A mathematical operation defined as dividing a joint distribution by a conditional distribution: $P(v) / P(x | nd(x))$, where $nd(x)$ are the non-descendants of $x$. This operation mimics the effect of an intervention without requiring actual experimental data.

The paper introduces the Test-Edge algorithm, a recursive procedure that searches for a sequence of truncations and marginalizations to reveal hidden independences. To isolate the relationship between target nodes, the algorithm utilizes the Maximum Ancestral Confounded Set (MACS), a graphical construct that identifies the necessary variables to "fix" or truncate.

Example causal diagrams (a, b, c) used to demonstrate the Test-Edge algorithm's ability to identify non-adjacencies through truncation.

Key Insights and Results

A critical insight of this work is the avoidance of "circular logic": a dormant independence cannot be used to test an edge if the identification of that independence itself assumes the edge is absent. The authors provide graphical criteria to identify "testable" edges that avoid this pitfall.

Furthermore, the authors prove that truncations are sufficient. They demonstrate that any constraint reachable through a combination of marginalization and truncation can be reached by performing truncations first. This algebraic simplification significantly reduces the search space for causal discovery.

The main theoretical results (Theorems 3 and 4) provide necessary and sufficient graphical conditions for when a directed edge can be identified using dormant independence. The Test-Edge algorithm is proven to be sound and complete for all edges satisfying these criteria. The authors demonstrate these findings using specific "gadget" graphs, such as the famous Verma Graph and more complex five-node examples.

Discussion and Future Work

While the proposed framework offers a powerful tool for latent variable models, it currently assumes a "valid graph" (a supergraph of the true model) is provided as input. It does not yet perform full structure discovery from scratch. Additionally, the results rely on a strong version of the faithfulness assumption across interventional distributions.

Future work involves integrating these truncation-based tests into comprehensive causal discovery algorithms that can recover structure directly from observational data without prior graphical knowledge. Computational complexity also remains a challenge for large-scale graphs with numerous latent variables.

This paper was originally presented at UAI 2009.

Summary updated

Abstract

We consider the problem of testing whether two variables should be adjacent (either due to a direct effect between them, or due to a hidden common cause) given an observational distribution, and a set of causal assumptions encoded as a causal diagram. In other words, given a set of edges in the diagram known to be true, we are interested in testing whether another edge ought to be in the diagram. In fully observable faithful models this problem can be easily solved with conditional independence tests. Latent variables make the problem significantly harder since they can imply certain non-adjacent variable pairs, namely those connected by so called inducing paths, are not independent conditioned on any set of variables. We characterize which variable pairs can be determined to be non-adjacent by a class of constraints due to dormant independence, that is conditional independence in identifiable interventional distributions. Furthermore, we show that particular operations on joint distributions, which we call truncations are sufficient for exhibiting these non-adjacencies.This suggests a causal discovery procedure taking advantage of these constraints in the latent variable case can restrict itself to truncations.
BibTeX
@inproceedings{shpitser2009testing,
  author = {Ilya Shpitser and Thomas S. Richardson and James M. Robins},
  title = {{Testing Edges by Truncations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=rkWeHVG_br},
}
Figure