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 方法和其他分治算法。

根据祖先关系进行变量分组的因果图学习

Learning causal graphs using variable grouping according to ancestral  relationship

Markov chain Monte Carlo methods are often deemed too computationally
intensive to be of any practical use for big data applications, and in
particular for inference on datasets containing a large number $n$ of
individual data points, also known as tall datasets. In scenarios where data
are assumed independent, various approaches to scale up the Metropolis-Hastings
algorithm in a Bayesian inference context have been recently proposed in
machine learning and computational statistics. These approaches can be grouped
into two categories: divide-and-conquer approaches and, subsampling-based
algorithms. The aims of this article are as follows. First, we present a
comprehensive review of the existing literature, commenting on the underlying
assumptions and theoretical guarantees of each method. Second, by leveraging
our understanding of these limitations, we propose an original
subsampling-based approach which samples from a distribution provably close to
the posterior distribution of interest, yet can require less than $O(n)$ data
point likelihood evaluations at each iteration for certain statistical models
in favourable scenarios. Finally, we have only been able so far to propose
subsampling-based methods which display good performance in scenarios where the
Bernstein-von Mises approximation of the target posterior distribution is
excellent. It remains an open challenge to develop such methods in scenarios
where the Bernstein-von Mises approximation is poor.

本文综述了最近在机器学习和计算统计学领域提出的两类解决元数据分析中基于独立假设的马尔科夫链蒙特卡罗方法的方法：分而治之的方法和基于子采样的算法，并提出了一种新颖的基于子采样的方法，并在某些统计模型的有利情况下，每次迭代可以要求少于 $O (n)$ 数量级的数据点似然性评估，然而，在目标后验分布的 Bernstein-von Mises 逼近存在缺陷的情况下，我们目前只能提出能在基于子采样的方法中表现良好的方法，而在其他情况下这仍然是一个未解决的挑战。