We consider constraint-based methods for causal structure learning, such as
the PC-, FCI-, RFCI- and CCD- algorithms (Spirtes et al. (2000, 1993),
Richardson (1996), Colombo et al. (2012), Claassen et al. (2013)). The first
step of all these algorithms consists of the PC-algorithm. This algorithm is
known to be order-dependent, in the sense that the output can depend on the
order in which the variables are given. This order-dependence is a minor issue
in low-dimensional settings. We show, however, that it can be very pronounced
in high-dimensional settings, where it can lead to highly variable results. We
propose several modifications of the PC-algorithm (and hence also of the other
algorithms) that remove part or all of this order-dependence. All proposed
modifications are consistent in high-dimensional settings under the same
conditions as their original counterparts. We compare the PC-, FCI-, and
RFCI-algorithms and their modifications in simulation studies and on a yeast
gene expression data set. We show that our modifications yield similar
performance in low-dimensional settings and improved performance in
high-dimensional settings. All software is implemented in the R-package pcalg.

本研究考虑基于约束的因果结构学习方法，特别关注 PC 算法在高维数据中存在的顺序依赖性并提出多种改良方法，模拟实验和酵母基因表达数据验证表明改良后的算法在高维数据中表现更优。

基于约束的无序因果结构学习

Order-independent constraint-based causal structure learning

We consider the PC-algorithm Spirtes et. al. (2000) for estimating the
skeleton of a very high-dimensional acyclic directed graph (DAG) with
corresponding Gaussian distribution. The PC-algorithm is computationally
feasible for sparse problems with many nodes, i.e. variables, and it has the
attractive property to automatically achieve high computational efficiency as a
function of sparseness of the true underlying DAG. We prove consistency of the
algorithm for very high-dimensional, sparse DAGs where the number of nodes is
allowed to quickly grow with sample size n, as fast as O(n^a) for any
0<a<infinity. The sparseness assumption is rather minimal requiring only that
the neighborhoods in the DAG are of lower order than sample size n. We
empirically demonstrate the PC-algorithm for simulated data and argue that the
algorithm is rather insensitive to the choice of its single tuning parameter.

本文考虑了使用 PC 算法来估计具有相应高斯分布的高维无向无环图骨架的计算问题，并证明了算法对非常高维的稀疏 DAG 的一致性。