How can we determine if one event causes another using only observational data? For decades, the standard scientific consensus was that correlation does not imply causation, and that without randomized controlled experiments or a clear temporal sequence, mapping a true causal network was impossible.
However, foundational work by Geiger et al. in Learning Causal Trees from Dependence Information overturned this intuition. They demonstrated that the "arrows" of causality leave distinct statistical footprints directly within observational data. By systematically analyzing patterns of conditional independence, we can reverse-engineer the underlying directed acyclic graph (DAG) that governs a system. As Peter Spirtes explains in Causal discovery and inference: concepts and recent methodological advances, this constraint-based approach allows us to move beyond mere correlation by mapping which variables effectively "screen off" the influence of others.
The Core Intuition: Screening Off vs. Conditioning On
To understand why this works, consider three variables: Atmospheric Pressure ($A$), a Barometer Reading ($B$), and a Storm ($C$).
If we look only at pairs, Atmospheric Pressure and Storms are highly correlated. However, if we condition on the Barometer Reading—meaning we group our data by specific barometer values—the statistical association between Pressure and Storms vanishes. The Barometer Reading screens off the dependency. This tells us that the information flows through a chain ($A \rightarrow B \rightarrow C$).
Constraint-based causal discovery scales this intuition up to complex networks using a two-phase strategy:
- Skeleton Discovery: Find which variables are directly connected, ignoring the direction of influence.
- Edge Orientation: Determine the direction of the causal arrows by exploiting statistical asymmetries.
Phase 1: Pruning the Graph to Find the Skeleton
The search space for all possible directed graphs grows exponentially with the number of variables. To bypass this bottleneck, constraint-based algorithms begin with a fully connected, undirected graph where every variable is tentatively linked to every other variable.
The algorithm then systematically prunes edges by performing conditional independence tests. As highlighted by Glymour et al. in Review of Causal Discovery Methods Based on Graphical Models, if any conditioning set $Z$ can be found that renders two variables $X$ and $Y$ independent ($X \perp Y \mid Z$), the edge between $X$ and $Y$ is permanently removed.
[Fully Connected Graph]
A — B
\ /
C
Test: Is A independent of C given B?
If Yes -> Prune edge A — C
[Discovered Skeleton]
A — B — C
To make this computationally feasible, algorithms like the classic PC algorithm—detailed in the open-source library overview by Zheng et al. (Causal-learn: Causal Discovery in Python)—organize these tests hierarchically. They start by testing marginal independence (conditioning on the empty set), and then progressively increase the size of the conditioning set.
As Rohekar et al. demonstrate in Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias, this iterative approach allows the algorithm to act as an "anytime algorithm," gradually refining the graph's skeleton while keeping the conditioning sets as small as possible. Similarly, Yu et al. leverage this skeleton search in Causal-Driven Skill Prerequisite Structure Discovery to map out educational dependencies, demonstrating how an initial neighborhood map drastically reduces the downstream search space.
Phase 2: Orienting Edges via Collider Asymmetry
Once the skeleton is established, how do we turn undirected lines into directed arrows? The magic of constraint-based discovery lies in identifying v-structures (or colliders).
Consider three variables connected as $A - B - C$, where $A$ and $C$ are not directly linked. There are four possible ways these arrows could point:
| Type | Graphical Structure | Status of $A$ and $C$ when unconditioned | Status of $A$ and $C$ when conditioning on $B$ |
|---|---|---|---|
| Chain | $A \rightarrow B \rightarrow C$ | Dependent | Independent (Screens off) |
| Chain | $A \leftarrow B \leftarrow C$ | Dependent | Independent (Screens off) |
| Fork | $A \leftarrow B \rightarrow C$ | Dependent | Independent (Screens off) |
| Collider | $A \rightarrow B \leftarrow C$ | Independent | Dependent (Explaining away) |
Notice the stark asymmetry of the Collider. If $A$ and $C$ are independent normally, but become dependent when we condition on $B$, the structure must be a collider ($A \rightarrow B \leftarrow C$).
Peter Spirtes proves in Detecting Causal Relations in the Presence of Unmeasured Variables that detecting these colliders provides the exact statistical leverage needed to orient edges without experimental interventions. Once these initial v-structures are oriented, a set of logical rules (known as Meek rules) propagates directionality to the remaining edges to avoid creating spurious colliders or directed cycles. This mechanism is utilized across diverse domains, from establishing label hierarchies in multi-label classification (Sun et al. in Polytree-Augmented Classifier Chains for Multi-Label Classification) to refining neural connectomics maps (Shlizerman et al. in Statistical Perspective on Functional and Causal Neural Connectomics: A Comparative Study).
Real-World Nuances and Adaptations
While the core logic of constraint-based discovery is elegant, real-world data introduces significant statistical and structural hurdles.
Latent Confounders and Selection Bias
In practice, we rarely observe every relevant variable. If an unmeasured variable causes both $X$ and $Y$, a standard constraint-based algorithm might mistakenly infer a direct causal link. To combat this, advanced algorithms like Fast Causal Inference (FCI) interpret stable edge patterns to guarantee whether a causal path exists despite hidden confounders or non-random sampling bias (Spirtes et al. in Causal Inference in the Presence of Latent Variables and Selection Bias).
The Sensitivity of Statistical Cutoffs
Traditional constraint-based methods rely on frequentist significance tests (like $\chi^2$ or partial correlation tests) to evaluate independence. As Dai et al. point out in A Study of Causal Discovery With Weak Links and Small Samples, relying on rigid $p$-value thresholds makes these algorithms highly sensitive to sample sizes and weak causal links. If a single early test yields a false negative, an edge is permanently deleted, causing an error that cascades through the orientation phase.
To mitigate this, modern frameworks often prioritize precision by requiring robust statistical evidence before retaining or pruning links (Raghu et al. in Evaluation of Causal Structure Learning Methods on Mixed Data Types). Others combine constraint-based pruning with functional or deep learning techniques—such as using Normalizing Flows to prune latent representations (Hoang et al. in Enabling Causal Discovery in Post-Nonlinear Models with Normalizing Flows) or utilizing path queries to bypass full conditional independence testing entirely (Bello et al. in Computationally and statistically efficient learning of causal Bayes nets using path queries).
Non-Standard Data Structures
Data does not always arrive in a clean, continuous tabular format:
- Mixed Data: Real-world datasets frequently mix continuous and categorical variables, requiring specialized independence tests to prevent structural distortion (Tsagris et al. in Correction to: Constraint-based causal discovery with mixed data).
- Relational Data: When data is organized in complex relational databases rather than flat tables, standard independence assumptions break down. Frameworks must adapt by testing independence across interconnected entity subgraphs (Maier et al. in Learning Causal Models of Relational Domains).
- Time Series: In temporal settings, the constraint-based skeleton phase is often augmented by directing edges from past variables to future variables, aligning statistical constraints with the arrow of time (Assaad et al. in Survey and Evaluation of Causal Discovery Methods for Time Series (Extended Abstract)).
By systematically mapping out what screens off what, constraint-based discovery transforms observational data from a static record of correlations into a dynamic blueprint of cause and effect.
Key Foundational Work
Learning Causal Trees from Dependence Information (1990) — contributed 1 concept elements to this direction.
The Recovery of Causal Poly-Trees from Statistical Data (1987) — contributed 1 concept elements to this direction.