📊 statistics

Conditional Independence Tests for Constraint-Based Causal Discovery: A Survey

This survey reviews six families of conditional independence tests used in constraint-based causal discovery, analyzing their assumptions, robustness, and scalability to connect test-level properties with graph-level errors and identify open challenges in high-dimensional and mixed-type biomedical settings.

Original authors: Pavel Averin, Theodoros Moysiadis, Ioannis Katakis

Published 2026-08-12

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Pavel Averin, Theodoros Moysiadis, Ioannis Katakis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but instead of finding a culprit, you are trying to figure out why things happen. You have a pile of clues—data points about people, genes, or weather patterns. The easy way to look at this data is to spot "coincidences." If you see that ice cream sales and shark attacks both go up in July, you might think they are linked. But a smart detective knows that correlation isn't causation; a hidden third factor, like hot summer weather, is likely causing both. To find the real cause, you need to ask a very specific question: "If I already know the weather, does ice cream sales still tell me anything about shark attacks?" If the answer is "no," then the link between ice cream and sharks is just a coincidence. In the world of science, this specific question is called a "Conditional Independence" test. It's the statistical engine that powers a method called "constraint-based causal discovery," which tries to build a map of cause-and-effect relationships directly from data. This is crucial in fields like medicine, where knowing the true cause of a disease can mean the difference between a life-saving treatment and a harmful mistake.

This paper is a massive survey—a "field guide"—for the detectives who use these tests. The authors, Pavel Averin, Theodoros Moysiadis, and Ioannis Katakis, noticed that while scientists have built many different tools to ask this "if I know X, does Y matter?" question, there is no single manual that explains which tool works best for which job. They organized the most popular tools into six distinct families, ranging from simple math tricks (like partial correlation) to complex machine learning models. Their main finding is that there is no "one-size-fits-all" solution. The best tool depends entirely on the shape of your data (is it numbers, categories, or a mix?), how much data you have, and how many variables you are juggling at once.

The paper suggests that choosing the wrong tool is like trying to cut a steak with a spoon or a cake with a chainsaw. If you use a simple tool on messy, complex data, you might miss real connections. If you use a super-complex tool on a tiny dataset, you might find fake connections that don't exist. The authors warn that as you try to account for more and more variables (a "conditioning set"), even the best tools start to lose their power, especially if your sample size is small. They also point out that many current software packages don't handle mixed data types (like combining temperature readings with yes/no answers) very well without forcing the data into a box it doesn't fit, a process called "discretization" that can ruin the accuracy of the results.

Ultimately, the paper argues that the quality of your final "cause-and-effect map" is only as good as the quality of the individual tests you used to build it. They provide a set of decision trees and guidelines to help researchers pick the right tool for their specific situation, whether they are working with continuous numbers, categories, or a messy mix of both. While they don't claim to have solved every problem in the field, they highlight that the biggest challenges right now are handling mixed data without losing information, working with very small amounts of data, and making these complex tests fast enough to run on modern, high-dimensional datasets. The goal is to help scientists move from just guessing what might be related to confidently understanding what actually drives the world around us.

Technical Summary: Conditional Independence Tests for Constraint-Based Causal Discovery: A Survey

Problem Statement
Constraint-based causal discovery algorithms (e.g., PC, FCI) rely fundamentally on Conditional Independence (CI) tests to prune graph skeletons and orient edges. While these algorithms are widely used in biomedical domains to move from correlation to causation, the literature lacks a focused synthesis of the CI testing component itself. Existing surveys treat CI testing as merely one sub-component of broader causal discovery frameworks, leaving practitioners without a systematic guide to the assumptions, robustness properties, and computational trade-offs of different CI test families. Furthermore, there is a gap in understanding how test-level behaviors—such as power decay with increasing conditioning set size or asymmetric Type I/II error consequences—propagate to graph-level errors in skeleton recovery and v-structure orientation. This is particularly critical in high-dimensional, mixed-type settings common in biomedicine, where incorrect CI decisions can lead to misleading causal claims and harmful downstream interventions.

Methodology
This paper presents a comprehensive survey of CI tests used in constraint-based causal discovery from independent and identically distributed (i.i.d.) observational data. The methodology involves:

Taxonomy Construction: Organizing widely used CI methods into six distinct families: partial-correlation, contingency-table, regression, nearest-neighbor, kernel, and machine-learning–based.
Theoretical Analysis: Examining the assumptions (e.g., Gaussianity, linearity, faithfulness) and statistical properties of each family, specifically focusing on when CI decisions reflect the true data-generating distribution and when they fail.
Error Propagation Mapping: Linking test-level properties (calibration, power decay, error asymmetry) to specific graph-level failure modes, such as spurious edge removal, missing edges, and incorrect v-structure orientations.
Software Ecosystem Review: Comparing the implementation of these test families and constraint-based algorithms across major R and Python libraries (including bnlearn, pcalg, MXM, causal-learn, gCastle, pgmpy, and Tigramite).
Practical Synthesis: Developing heuristic decision frameworks and trade-off tables to guide practitioners in selecting CI tests based on data type (continuous, categorical, mixed), sample size, conditioning set depth, and computational budget.

Key Contributions
The paper makes four primary contributions:

CI Test-Centric Synthesis: It provides a focused review treating CI testing as the primary design choice governing skeleton pruning and edge orientation in constraint-based discovery, rather than a secondary component.
Test-to-Graph Error Linking: It systematically connects test-level properties (assumptions, calibration, power decay) to graph-level failure modes, offering a clearer understanding of how statistical errors translate into structural errors in the learned causal graph.
Consolidated Software Landscape: It consolidates scattered information regarding the availability of constraint-based algorithms and CI test families across major R and Python ecosystems, including details on conditioning set limits, logging, customization, parallelization, and prior-knowledge support.
Practitioner Guidance: It translates theoretical findings into actionable guidance via trade-off tables and heuristic decision frameworks (Figures 6–8) for selecting CI tests under varying data-type, sample-size, and computational regimes.

Results and Findings
The survey identifies several critical trade-offs and limitations across CI test families:

Partial-Correlation (e.g., Fisher's Z): Fast and transparent but strictly requires Gaussianity and linearity; invalid under distributional violations.
Contingency-Table (e.g., $\chi^2$ , $G^2$ ): Effective for categorical data but suffers from rapid power degradation and table sparsity as conditioning set size increases.
Regression-Based: Flexible via Generalized Linear Models (GLMs) but relies on correct model specification; misspecification leads to biased decisions.
Nearest-Neighbor (KNN) & Kernel-Based: Non-parametric and capable of detecting nonlinear dependencies but suffer from high computational costs ( $O(n^3)$ for kernels) and variance issues in high-dimensional conditioning sets.
Machine-Learning-Based (e.g., GCM, DML): Model-agnostic and flexible but require large sample sizes and careful calibration (e.g., cross-fitting) to avoid overfitting biases; currently lack native support in major production libraries.
Mixed-Type Data: Discretization is a common but flawed strategy that alters the statistical object being tested. While robustness layers (shrinkage, permutation) exist, unified, distribution-free tests for mixed data without ad hoc discretization remain an open challenge.
Scalability: The combinatorial growth of conditioning sets makes exhaustive CI testing prohibitive in high-dimensional settings ( $p \gg n$ ). Strategies like parallelization, stable ordering, and divide-and-conquer (local discovery) are necessary but introduce their own computational and statistical complexities.

Significance and Claims
The paper argues that the reliability of constraint-based causal discovery is directly limited by the validity of its underlying CI decisions. It posits that "graph quality is only as good as the validity of its CI decisions." The significance of this work lies in its ability to:

Bridge the Gap: Connect abstract statistical properties of CI tests to the practical reliability of causal graphs in high-stakes biomedical applications.
Guide Selection: Provide a structured framework for practitioners to navigate the trade-offs between flexibility, computational cost, and statistical power, particularly when dealing with mixed-type data and limited samples.
Highlight Open Challenges: Identify critical unresolved issues, including the need for robust mixed-type CI testing without discretization, better error control in small-sample regimes, and the integration of domain knowledge (potentially via LLMs) to orient partially directed graphs.

The authors maintain a modest stance, noting that while heuristic frameworks are proposed, systematic empirical validation across diverse data regimes is still required to confirm these guidelines. The paper serves as a foundational reference for researchers and practitioners aiming to improve the transparency, interpretability, and accuracy of causal discovery pipelines.

More like this