Abstract. Many state of the art algorithms to discover causal networks or local causal structures within a network rely on conditional independence tests. Hence, having a solid independence test is crucial for a good performance. As part of this work, we formulate a conditional independence test for discrete data, called SCI, in terms of algorithmic independence. We show theoretically as well as empirically that our test performs favourable compared to the commonly used \(G^2\) test and the conditional mutual information.

Towards our actual goal, we use SCI to develop the Climb algorithm for discovering causal Markov Blankets, i.e. directed Markov Blankets that identify which are the parents, children and spouses of the target variable. Last, but not least, we introduce the Kloor algorithm that based on the causal Markov Blankets reconstructs the complete causal graph. Extensive empirical evaluation shows that both Climb and Kloor perform very well in practice, scale to large networks, and achieve very high precision and recall.