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 PC algorithm.

本文提出了一种基于有限数据进行稳健因果发现的算法 $k$-PC，通过对两个因果图的条件独立性约束进行比较建立了 $k$-Markov 等价。实验表明，$k$-PC 算法相较于传统 PC 算法，可以在小样本环境中实现更强大的稳健性。