Zhang Hao, Ren Yixin, Xia Yewei, Zhou Shuigeng, Guan Jihong
IEEE Trans Pattern Anal Mach Intell. 2024 Dec;46(12):10259-10271. doi: 10.1109/TPAMI.2024.3435503. Epub 2024 Nov 6.
Causal partitioning is an effective approach for causal discovery based on the divide-and-conquer strategy. Up to now, various heuristic methods based on conditional independence (CI) tests have been proposed for causal partitioning. However, most of these methods fail to achieve satisfactory partitioning without violating d-separation, leading to poor inference performance. In this work, we transform causal partitioning into an alternative problem that can be more easily solved. Concretely, we first construct a superstructure G of the true causal graph G by performing a set of low-order CI tests on the observed data D. Then, we leverage point-line duality to obtain a graph G adjoint to G. We show that the solution of minimizing edge-cut ratio on G can lead to a valid causal partitioning with smaller causal-cut ratio on G and without violating d-separation. We design an efficient algorithm to solve this problem. Extensive experiments show that the proposed method can achieve significantly better causal partitioning without violating d-separation than the existing methods.
因果划分是一种基于分治策略进行因果发现的有效方法。到目前为止，已经提出了各种基于条件独立性（CI）检验的启发式方法用于因果划分。然而，这些方法中的大多数在不违反d-分离的情况下无法实现令人满意的划分，导致推理性能较差。在这项工作中，我们将因果划分转化为一个更容易解决的替代问题。具体来说，我们首先通过对观测数据D进行一组低阶CI检验来构建真实因果图G的一个超结构G。然后，我们利用点线对偶性得到一个与G相邻的图G。我们表明，在G上最小化边割比的解可以导致在G上具有更小因果割比且不违反d-分离的有效因果划分。我们设计了一种高效算法来解决这个问题。大量实验表明，与现有方法相比，所提出的方法在不违反d-分离的情况下能够实现显著更好的因果划分。
