Learning the unique directed acyclic graph corresponding to an unknown causal
model is a challenging task. Methods based on functional causal models can
identify a unique graph, but either suffer from the curse of dimensionality or
impose strong parametric assumptions. To address these challenges, we propose a
novel hybrid approach for global causal discovery in observational data that
leverages local causal substructures. We first present a topological sorting
algorithm that leverages ancestral relationships in linear structural equation
models to establish a compact top-down hierarchical ordering, encoding more
causal information than linear orderings produced by existing methods. We
demonstrate that this approach generalizes to nonlinear settings with arbitrary
noise. We then introduce a nonparametric constraint-based algorithm that prunes
spurious edges by searching for local conditioning sets, achieving greater
accuracy than current methods. We provide theoretical guarantees for
correctness and worst-case polynomial time complexities, with empirical
validation on synthetic data.

在观测数据中进行因果发现是一项具有挑战性的任务，本研究提出了一种新颖的混合方法，结合局部因果子结构，通过引入拓扑排序算法和非参数约束算法，在线性和非线性设置中实现了全局因果推断，并在合成数据中进行了验证。

带有局部搜索的混合全局因果发现

Hybrid Global Causal Discovery with Local Search

Identification of causal direction between a causal-effect pair from observed
data has recently attracted much attention. Various methods based on functional
causal models have been proposed to solve this problem, by assuming the causal
process satisfies some (structural) constraints and showing that the reverse
direction violates such constraints. The nonlinear additive noise model has
been demonstrated to be effective for this purpose, but the model class is not
transitive--even if each direct causal relation follows this model, indirect
causal influences, which result from omitted intermediate causal variables and
are frequently encountered in practice, do not necessarily follow the model
constraints; as a consequence, the nonlinear additive noise model may fail to
correctly discover causal direction. In this work, we propose a cascade
nonlinear additive noise model to represent such causal influences--each direct
causal relation follows the nonlinear additive noise model but we observe only
the initial cause and final effect. We further propose a method to estimate the
model, including the unmeasured intermediate variables, from data, under the
variational auto-encoder framework. Our theoretical results show that with our
model, causal direction is identifiable under suitable technical conditions on
the data generation process. Simulation results illustrate the power of the
proposed method in identifying indirect causal relations across various
settings, and experimental results on real data suggest that the proposed model
and method greatly extend the applicability of causal discovery based on
functional causal models in nonlinear cases.

提出了一种级联非线性加性噪声模型，可以发现难以被非线性加性噪声模型正确揭示的因果关系。该研究还在变分自编码器框架下提出一种方法来估计该模型并克服了实践中存在的一些问题。