Discovering the causal structure of a system from observational data is a fundamental challenge in science. Typically, this structure is represented as a Directed Acyclic Graph (DAG), where nodes represent variables and directed edges represent cause-and-effect relationships.
The classic textbook approach to constraint-based causal discovery, exemplified by algorithms like the PC algorithm, splits the problem into two distinct, sequential phases:
- Skeleton Discovery: Perform statistical conditional independence tests to find which variables are connected, ignoring the direction of the connections to produce an undirected graph.
- Edge Orientation: Apply logical rules (such as identifying v-structures) to turn those undirected edges into directed arrows.
While conceptually clean, this sequential split suffers from a severe computational bottleneck. The search space of potential graph structures grows superexponentially with the number of variables. To determine whether an undirected edge exists between two variables, a sequential algorithm may have to condition on an exponentially large number of conditioning sets. If an error is made early in the skeleton phase due to statistical noise, it propagates catastrophically into the orientation phase.
To overcome this bottleneck, a powerful paradigm has emerged: integrating edge discovery and orientation. Instead of treating them as isolated steps, modern methods interleave orientation rules directly into the discovery process or use coarse undirected graphs to prune the search space before expensive directed searches begin. By establishing causal directions early, these algorithms drastically reduce the number of required statistical tests and prevent computational explosion.
The Intuition: Information Feedback Loops
Why does knowing an edge's direction help find other edges? In causal graphs, directionality dictates conditional independence. For example, if we discover that $X \rightarrow Y \leftarrow Z$ forms a v-structure, $X$ and $Z$ become dependent when conditioning on $Y$. Conversely, if the path is $X \rightarrow Y \rightarrow Z$, $X$ and $Z$ are independent given $Y$.
If we wait until the very end of the algorithm to orient edges, we waste thousands of expensive statistical tests exploring paths that are already causally impossible based on local directional constraints. Interleaving the two phases creates a feedback loop: early orientation decisions immediately rule out vast swaths of the graph search space, simplifying the remaining skeleton search.
Traditional Sequential Approach:
[ Find All Undirected Edges ] ──(No feedback)──> [ Orient All Edges ]
Integrated Interleaved Approach:
┌────────────────────────────────────────┐
│ ▼
[ Find Local Edges ] ──> [ Orient Local Edges ] ──> [ Prune Search Space ]
Static Pruning via Undirected Preprocessing
One manifestation of this idea is a two-stage pipeline where a fast, global undirected graph estimation acts as a strict constraint for the subsequent causal search.
In high-dimensional settings, Peter Bühlmann demonstrated this in High-dimensional learning of linear causal networks via inverse covariance estimation by first inferring a "moralized graph" using inverse covariance estimation. Because the true causal DAG must be a subgraph of this moralized graph, the search space for the directed network is immediately restricted to components consistent with this initial skeleton, making high-dimensional causal search computationally tractable.
This strategy is highly effective across diverse data distributions:
- Count Data: Park et al. applied a similar two-step framework to large-scale Poisson DAG models in Learning Large-Scale Poisson DAG Models based on OverDispersion Scoring. They estimated an undirected moralized graph as a preprocessing step to eliminate impossible parent-child relationships early on.
- Mixed Data Types: For datasets containing both continuous and categorical variables, Raghu et al. showed in Evaluation of Causal Structure Learning Methods on Mixed Data Types that initializing a causal search with a sparse undirected graph from a Mixed Graphical Model provides a reliable "warm start" that stabilizes the discovery process and improves final structural accuracy.
Dynamic Interleaving During Search
Rather than just preprocessing the graph once, many algorithms dynamically alternate between edge discovery and orientation at every step of execution.
Boaz Lerner pioneered this with the Recursive Autonomy Identification (RAI) algorithm in Recursive Autonomy Identification for Bayesian Network Structure Learning. The RAI algorithm recursively decomposes a large structure into smaller "autonomous sub-structures." By interleaving edge orientation with skeleton discovery, causal directions established early in the process are immediately used to simplify the search for remaining connections, drastically reducing the number of conditional independence tests required.
This dynamic pruning becomes even more critical when dealing with complex environments that include latent confounders (unobserved common causes) or selection bias:
- Iterative Causal Discovery: In Iterative Causal Discovery in the Possible Presence of Latent Confounders and Selection Bias, Rohekar et al. designed an anytime algorithm (ICD) that applies orientation rules at every single iteration of the skeleton search. Determining causal directions on the fly prevents the exponential explosion of tests typically triggered by latent variables.
- Autocorrelated Time Series: Time-series data introduces temporal dependencies that can inflate false positives. In High-recall causal discovery for autocorrelated time series with latent confounders, Gerhardus et al. interleaved edge detection and orientation to iteratively isolate causal parents, using them to "clear the noise" in subsequent statistical tests.
- Local Structure Learning: If a researcher only needs the causal neighborhood (the Markov blanket) of a specific target variable, mapping the entire global network is wasteful. In Towards Efficient Local Causal Structure Learning and its extended work Towards Efficient Local Causal Structure Learning, Wang et al. and Yang et al. introduced the ELCS algorithm. By identifying local topological patterns called "N-structures," the authors integrated edge orientation directly into the neighborhood discovery phase, immediately pruning irrelevant branches of the graph.
Pruning Search Spaces for Exact Optimization
The benefits of integrated pruning extend beyond constraint-based algorithms to score-based and exact optimization frameworks, such as Integer Programming (IP). Exact methods guarantee mathematical optimality but are notoriously constrained by exponential subgraph growth.
In Integer Programming for Causal Structure Learning in the Presence of Latent Variables, Chen et al. developed pruning rules to discard sub-optimal candidate components before the integer program even begins optimization. This preprocessing step keeps the search space manageable without sacrificing the global optimality of the final ancestral graph.
Similarly, to account for structural uncertainty in linear models, David Strieder utilized pruning subroutines in Confidence in Causal Inference under Structure Uncertainty in Linear Causal Models with Equal Variances to rapidly eliminate implausible causal orderings, focusing exact computation only on high-likelihood graph candidates.
Exploiting Structural Constraints
Other frameworks exploit specific structural properties to prune the search space:
- Targeted Downstream Pruning: In SNAP: Sequential Non-Ancestor Pruning for Targeted Causal Effect Estimation With an Unknown Graph, Schubert et al. integrated pruning directly into the skeleton search by alternating between edge discovery and the removal of nodes that cannot possibly be ancestors of the target variables.
- Graph Abstractions: When enumerating valid causal graphs from a generalized Partial Ancestral Graph (PAG), Subramani et al. showed in PAG2ADMG: A Novel Methodology to Enumerate Causal Graph Structures that utilizing the structural constraints inherent in the PAG allows an algorithm to prune invalid edge combinations early, reducing candidate models from tens of thousands to a small, verifiable shortlist.
- Overlapping Datasets: When merging disparate datasets that only share a subset of variables, Dhir et al. demonstrated in Integrating Overlapping Datasets Using Bivariate Causal Discovery that incorporating local causal directions early eliminates large sets of structurally equivalent graphs, preventing the algorithm from exploring configurations that contradict established local orientations.
- Rate-Agnostic Constraints: Even when time-series data is severely undersampled, Plis et al. showed in Rate-Agnostic (Causal) Structure Learning that if a simplified candidate graph is inconsistent with the data at any possible sampling rate, all more complex graphs containing that structure can be instantly discarded.
Summary
The shift from a rigid, sequential pipeline to an integrated, interleaved architecture represents a major milestone in making causal discovery scalable. Whether by using an undirected graph as a static filter or by dynamically updating edge orientations during execution, breaking down the wall between skeleton discovery and edge orientation allows algorithms to learn more accurate causal maps using significantly fewer statistical operations.
Key Foundational Work
Recursive Autonomy Identification for Bayesian Network Structure Learning (2005) — contributed 2 concept elements to this direction.
High-dimensional learning of linear causal networks via inverse covariance estimation (2014) — contributed 1 concept elements to this direction.