Causal discovery aims to recover the true Directed Acyclic Graph (DAG) underlying a set of observed variables. Historically, constraint-based algorithms relied purely on conditional independence (CI) tests to prune and orient edges. However, CI tests can only resolve a graph up to its Markov equivalence class, leaving the direction of many edges fundamentally ambiguous.
Modern causal discovery overcomes these limitations by exploiting statistical asymmetries, geometric structures, and algebraic constraints hidden within observational data.
Exploiting Statistical Asymmetries
If you fit a linear regression $Y = \beta X + \epsilon$, the residual $\epsilon$ is always mathematically uncorrelated with the regressor $X$. But correlation is not independence. If the underlying data generation process is non-Gaussian, the residual will be statistically independent of the regressor only in the true causal direction.
Shimizu et al. leveraged this asymmetry in their Linear Non-Gaussian Acyclic Model (LiNGAM), using Independent Component Analysis (ICA) to uniquely identify the causal ordering of variables without requiring prior temporal information.
This principle of statistical asymmetry extends far beyond continuous linear data:
- Discrete Count Data: For zero-inflated count data common in genomics, Choi introduced ZiG-DAGs (Model-Based Causal Discovery for Zero-Inflated Count Data), utilizing generalized hypergeometric distributions to resolve nonlinear causal links. For branching structures, Xiang et al. developed a framework (On the Identifiability of Poisson Branching Structural Causal Model Using Probability Generating Function) that analyzes Probability Generating Functions (PGFs). These higher-order distributional shapes uniquely expose the causal direction where standard correlations fail.
- Time-Series Dynamics: In temporal settings like neuroimaging, Zhu et al. demonstrated that second-order temporal statistics—specifically autocorrelations—can break instantaneous causal ambiguities (Second-order instantaneous causal analysis of spontaneous MEG), allowing robust direction inference even with limited sample sizes.
Navigating the Combinatorial Graph Space
Searching for the optimal DAG is an NP-hard problem because the number of possible graphs scales exponentially with the number of variables. Score-based methods try to find the graph that maximizes a reward function, but continuous relaxations of this search space often yield invalid "almost-DAGs" containing cycles.
To guarantee structural validity during optimization, Zantedeschi et al. proposed shifting the optimization landscape to the Permutahedron—the geometric polytope of all possible node orderings (DAG Learning on the Permutahedron). By optimizing over smooth permutations rather than discrete edge matrices, their framework ensures that every step of the optimization corresponds to a strictly valid, cycle-free DAG.
Continuous Edge Optimization ──► Can introduce invalid cycles (Ouroboros problem)
Permutahedron Optimization ──► Restricts search to node orderings (Guaranteed DAGs)
Alternatively, discrete search can be guided by reinforcement learning. Darvariu et al. introduced CD-UCT (Tree search in DAG space with model-based reinforcement learning for causal discovery), which pairs a tree search strategy with an explicit cycle-detection mechanism. This allows an agent to efficiently navigate the massive graph space and scale to complex networks without getting trapped in cyclic configurations.
Bypassing the Blind Spots of Independence Tests
Traditional constraint-based discovery relies heavily on conditional independence (CI) tests to prune edges. However, these tests suffer from two fatal flaws: they have weak statistical power in high dimensions, and they fail completely when unobserved variables (latent confounders) act as hidden common causes.
To address weak test sensitivity, Wang et al. developed PowerKCI (Practical Kernel Selection for Kernel-based Conditional Independence Test). Instead of relying on arbitrary heuristics to choose kernel parameters, they dynamically maximize a proxy for the test's statistical power, drastically reducing regression bias and uncovering complex, nonlinear dependencies.
When latent confounders are present, standard independence tests cannot distinguish between a direct causal link ($X \rightarrow Y$) and a shared hidden cause ($X \leftarrow H \rightarrow Y$). Dong et al. bypassed this limitation by introducing Rank-based Latent Causal Discovery (A Versatile Causal Discovery Framework to Allow Causally-Related Hidden Variables).
Instead of testing for independence, they analyze rank constraints on the data's covariance matrices. Because a latent variable restricts the algebraic rank of specific sub-matrices, tracking these rank deficiencies allows the algorithm to mathematically pinpoint where hidden variables reside and map the true causal skeleton around them.