Conditions and Assumptions for Constraint-based Causal Structure Learning

We formalize constraint-based structure learning of the true causal graph from observed data when unobserved variables are also existent. We provide conditions for a natural family of constraint-based structure-learning algorithms that output graphs that are Markov equivalent to the causal graph. Under the faithfulness assumption, this natural family contains all exact structure-learning algorithms. We also provide a set of assumptions, under which any natural structure-learning algorithm outputs Markov equivalent graphs to the causal graph. These assumptions can be thought of as a relaxation of faithfulness, and most of them can be directly tested from (the underlying distribution) of the data, particularly when one focuses on structural causal models. We specialize the definitions and results for structural causal models.

Automated summary

This paper formalizes the constraint-based structure learning of the true causal graph from observed data with the existence of unobserved variables. It presents a natural family of constraint-based structure-learning algorithms that output graphs that are Markov equivalent to the causal graph. Under the faithfulness assumption, this natural family encompasses all exact structure-learning algorithms. A set of assumptions is also provided, under which any natural structure-learning algorithm can output Markov equivalent graphs to the causal graph. These assumptions can be considered as a relaxation of faithfulness and can be directly tested from the underlying distribution of the data, especially in the context of structural causal models. The definitions and results in this paper are specialized for structural causal models.