Most causal inference algorithms in the literature (e.g., Pearl (2000),
Spirtes et al. (2000), Heckerman et al. (1999)) exploit an assumption usually
referred to as the causal Faithfulness or Stability condition. In this paper,
we highlight two components of the condition used in constraint-based
algorithms, which we call "Adjacency-Faithfulness" and
"Orientation-Faithfulness". We point out that assuming Adjacency-Faithfulness
is true, it is in principle possible to test the validity of
Orientation-Faithfulness. Based on this observation, we explore the consequence
of making only the Adjacency-Faithfulness assumption. We show that the familiar
PC algorithm has to be modified to be (asymptotically) correct under the
weaker, Adjacency-Faithfulness assumption. Roughly the modified algorithm,
called Conservative PC (CPC), checks whether Orientation-Faithfulness holds in
the orientation phase, and if not, avoids drawing certain causal conclusions
the PC algorithm would draw. However, if the stronger, standard causal
Faithfulness condition actually obtains, the CPC algorithm is shown to output
the same pattern as the PC algorithm does in the large sample limit. We also
present a simulation study showing that the CPC algorithm runs almost as fast
as the PC algorithm, and outputs significantly fewer false causal arrowheads
than the PC algorithm does on realistic sample sizes. We end our paper by
discussing how score-based algorithms such as GES perform when the
Adjacency-Faithfulness but not the standard causal Faithfulness condition
holds, and how to extend our work to the FCI algorithm, which allows for the
possibility of latent variables.

本文研究因果推断算法中所使用的 Faithfulness 条件，并提出了 Adjacency-Faithfulness 和 Orientation-Faithfulness 两个组成部分。我们发现，只需假设满足 Adjacency-Faithfulness 条件，就可以测试 Orientation-Faithfulness 的有效性，并通过修改 PC 算法使其在该条件下更为正确。与 PC 算法相比，在 Adjacency-Faithfulness 条件下，修改后的保守 PC 算法能够减少输出虚假因果关系的个数，并在大样本限制下具有相同的结果。