Several causal discovery algorithms have been proposed. However, when the
sample size is small relative to the number of variables, the accuracy of
estimating causal graphs using existing methods decreases. And some methods are
not feasible when the sample size is smaller than the number of variables. To
circumvent these problems, some researchers proposed causal structure learning
algorithms using divide-and-conquer approaches. For learning the entire causal
graph, the approaches first split variables into several subsets according to
the conditional independence relationships among the variables, then apply a
conventional causal discovery algorithm to each subset and merge the estimated
results. Since the divide-and-conquer approach reduces the number of variables
to which a causal structure learning algorithm is applied, it is expected to
improve the estimation accuracy of causal graphs, especially when the sample
size is small relative to the number of variables and the model is sparse.
However, existing methods are either computationally expensive or do not
provide sufficient accuracy when the sample size is small. This paper proposes
a new algorithm for grouping variables based the ancestral relationships among
the variables, under the LiNGAM assumption, where the causal relationships are
linear, and the mutually independent noise are distributed as continuous
non-Gaussian distributions. We call the proposed algorithm CAG. The time
complexity of the ancestor finding in CAG is shown to be cubic to the number of
variables. Extensive computer experiments confirm that the proposed method
outperforms the original DirectLiNGAM without grouping variables and other
divide-and-conquer approaches not only in estimation accuracy but also in
computation time when the sample size is small relative to the number of
variables and the model is sparse.

该论文提出了一种基于变量的祖先关系分组的新算法 CAG，通过分组变量减少计算量和提高估计准确性，特别是在样本量相对较小且模型稀疏的情况下，在计算时间和估计准确性方面优于原始的直接 LiNGAM 方法和其他分治算法。