# Characterization and Learning of Causal Graphs with Small Conditioning Sets

arXiv: https://arxiv.org/abs/2301.09028 · HTML: https://mlsanity.com/paper/2301.09028/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 42 references that are in the map.
- First posted on arXiv 22 Jan 2023.

## Builds on (most cited first, 5 of 5)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Probabilistic Evaluation of Sequential Plans from Causal Models with Hidden Variables](https://mlsanity.com/paper/1302.4977/) (2013)
- [On the Equivalence of Causal Models](https://mlsanity.com/paper/1304.1108/) (2013)
- [Recovering Causal Structures from Low-Order Conditional Independencies](https://mlsanity.com/paper/2010.02675/) (2020)
- [Learning from Pairwise Marginal Independencies](https://mlsanity.com/paper/1508.00280/) (2015)

## Built on by (most cited first, 11 of 11)

- [Separation-based distance measures for causal graphs](https://mlsanity.com/paper/2402.04952/) (2024)
- [Differentiable Constraint-Based Causal Discovery](https://mlsanity.com/paper/2510.22031/) (2025)
- [SNAP: Sequential Non-Ancestor Pruning for Targeted Causal Effect Estimation With an Unknown Graph](https://mlsanity.com/paper/2502.07857/) (2025)
- [On Different Notions of Redundancy in Conditional-Independence-Based Discovery of Graphical Models](https://mlsanity.com/paper/2502.08531/) (2025)
- [Causal Discovery-Driven Change Point Detection in Time Series](https://mlsanity.com/paper/2407.07290/) (2024)
- [Cluster-Dags as Powerful Background Knowledge For Causal Discovery](https://mlsanity.com/paper/2512.10032/) (2025)
- [Meta-Dependence in Conditional Independence Testing](https://mlsanity.com/paper/2504.12594/) (2025)
- [On the Number of Conditional Independence Tests in Constraint-based Causal Discovery](https://mlsanity.com/paper/2603.21844/) (2026)
- [Consistency evaluation of benchmarks used for causal discovery](https://mlsanity.com/paper/2606.01789/) (2026)
- [Fair Data Pre-Processing with Imperfect Attribute Space](https://mlsanity.com/paper/2603.26456/) (2026)
- [Relaxing Faithfulness with Intervention-Only Causal Discovery](https://mlsanity.com/paper/2607.11816/) (2026)

## Abstract (arXiv)

Constraint-based causal discovery algorithms learn part of the causal graph structure by systematically testing conditional independences observed in the data. These algorithms, such as the PC algorithm and its variants, rely on graphical characterizations of the so-called equivalence class of causal graphs proposed by Pearl. However, constraint-based causal discovery algorithms struggle when data is limited since conditional independence tests quickly lose their statistical power, especially when the conditioning set is large. To address this, we propose using conditional independence tests where the size of the conditioning set is upper bounded by some integer k for robust causal discovery. The existing graphical characterizations of the equivalence classes of causal graphs are not applicable when we cannot leverage all the conditional independence statements. We first define the notion of k-Markov equivalence: Two causal graphs are k-Markov equivalent if they entail the same conditional independence constraints where the conditioning set size is upper bounded by k. We propose a novel representation that allows us to graphically characterize k-Markov equivalence between two causal graphs. We propose a sound constraint-based algorithm called the k-PC algorithm for learning this equivalence class. Finally, we conduct synthetic, and semi-synthetic experiments to demonstrate that the k-PC algorithm enables more robust causal discovery in the small sample regime compared to the baseline algorithms.