Towards Effective Causal Partitioning by Edge Cutting of Adjoint Graph
Hao Zhang, Yixin Ren, Yewei Xia, Shuigeng Zhou, Jihong Guan
Abstract
<i>Causal partitioning</i> 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 <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula>-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 <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> of the true causal graph <inline-formula><tex-math notation="LaTeX">$G_{\mathcal {T}}$</tex-math></inline-formula> by performing a set of low-order CI tests on the observed data <inline-formula><tex-math notation="LaTeX">$D$</tex-math></inline-formula>. Then, we leverage point-line duality to obtain a graph <inline-formula><tex-math notation="LaTeX">$G_\mathcal {A}$</tex-math></inline-formula> adjoint to <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula>. We show that the solution of <i>minimizing edge-cut ratio</i> on <inline-formula><tex-math notation="LaTeX">$G_\mathcal {A}$</tex-math></inline-formula> can lead to a valid causal partitioning with <i>smaller causal-cut ratio</i> on <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula> and <i>without violating <inline-formula><tex-math notation="LaTeX">$d$</tex-math><alternatives><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math><inline-graphic xlink:href="zhang-ieq9-3435503.gif" xmlns:xlink="http://www.w3.org/1999/xlink"/></alternatives></inline-formula>-separation</i>. We design an efficient algorithm to solve this problem. Extensive experiments show that the proposed method can achieve significantly better causal partitioning without violating <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula>-separation than the existing methods.