Many questions in science center around the fundamental problem of understanding causal relationships. However, most constraint-based causal discovery algorithms, including the well-celebrated PC algorithm, often incur an exponential number of conditional independence (CI) tests, posing limitations in various applications. Addressing this, our work focuses on characterizing what can be learned about the underlying causal graph with a reduced number of CI tests. We show that it is possible to a learn a coarser representation of the hidden causal graph with a polynomial number of tests. This coarser representation, named Causal Consistent Partition Graph (CCPG), comprises of a partition of the vertices and a directed graph defined over its components. CCPG satisfies consistency of orientations and additional constraints which favor finer partitions. Furthermore, it reduces to the underlying causal graph when the causal graph is identifiable. As a consequence, our results offer the first efficient algorithm for recovering the true causal graph with a polynomial number of tests, in special cases where the causal graph is fully identifiable through observational data and potentially additional interventions.

本研究旨在通过多项式数量的条件独立性测试来学习隐藏因果图的较粗糙表示，名为因果一致分区图（CCPG），它由顶点的一个分区和在其组件上定义的有向图组成，并满足方向性的一致性和其他有利于更细的分区的约束条件。此方法在因果图可识别的特殊情况下，通过多项式数量的测试，提供了首个有效的还原真实因果图的算法。

利用较少条件独立性检验进行因果发现