Conditions and Assumptions for Constraint-based Causal Structure Learning

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