The aim in many sciences is to understand the mechanisms that underlie the
observed distribution of variables, starting from a set of initial hypotheses.
Causal discovery allows us to infer mechanisms as sets of cause and effect
relationships in a generalized way -- without necessarily tailoring to a
specific domain. Causal discovery algorithms search over a structured
hypothesis space, defined by the set of directed acyclic graphs, to find the
graph that best explains the data. For high-dimensional problems, however, this
search becomes intractable and scalable algorithms for causal discovery are
needed to bridge the gap. In this paper, we define a novel causal graph
partition that allows for divide-and-conquer causal discovery with theoretical
guarantees. We leverage the idea of a superstructure -- a set of learned or
existing candidate hypotheses -- to partition the search space. We prove under
certain assumptions that learning with a causal graph partition always yields
the Markov Equivalence Class of the true causal graph. We show our algorithm
achieves comparable accuracy and a faster time to solution for
biologically-tuned synthetic networks and networks up to ${10^4}$ variables.
This makes our method applicable to gene regulatory network inference and other
domains with high-dimensional structured hypothesis spaces.

我们定义了一种新颖的因果图分区方法，利用超结构的概念对搜索空间进行划分，证明了使用因果图分区进行学习总是得到真实因果图的马尔可夫等价类，我们的算法在生物调节网络推断和其他高维结构假设空间中实现了可比较的准确性和更快的解决时间。

在高维结构假设空间上的因果发现与因果图分区

Causal Discovery over High-Dimensional Structured Hypothesis Spaces with  Causal Graph Partitioning

Gene regulatory network inference (GRNI) is a challenging problem,
particularly owing to the presence of zeros in single-cell RNA sequencing data:
some are biological zeros representing no gene expression, while some others
are technical zeros arising from the sequencing procedure (aka dropouts), which
may bias GRNI by distorting the joint distribution of the measured gene
expressions. Existing approaches typically handle dropout error via imputation,
which may introduce spurious relations as the true joint distribution is
generally unidentifiable. To tackle this issue, we introduce a causal graphical
model to characterize the dropout mechanism, namely, Causal Dropout Model. We
provide a simple yet effective theoretical result: interestingly, the
conditional independence (CI) relations in the data with dropouts, after
deleting the samples with zero values (regardless if technical or not) for the
conditioned variables, are asymptotically identical to the CI relations in the
original data without dropouts. This particular test-wise deletion procedure,
in which we perform CI tests on the samples without zeros for the conditioned
variables, can be seamlessly integrated with existing structure learning
approaches including constraint-based and greedy score-based methods, thus
giving rise to a principled framework for GRNI in the presence of dropouts. We
further show that the causal dropout model can be validated from data, and many
existing statistical models to handle dropouts fit into our model as specific
parametric instances. Empirical evaluation on synthetic, curated, and
real-world experimental transcriptomic data comprehensively demonstrate the
efficacy of our method.

基因调控网络推断是一个具有挑战性的问题，尤其是由于单细胞 RNA 测序数据中存在零值：一些是表示没有基因表达的生物学上的零值，而其他一些是由测序过程（也称为缺失）产生的技术性零值，可能通过扭曲所测量的基因表达的联合分布来偏移基因调控网络推断。