Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models
<|reference_start|>Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models: 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.<|reference_end|>
@article{hiremath2024hybrid,
    title={Hybrid Top-Down Global Causal Discovery with Local Search for Linear and
  Nonlinear Additive Noise Models},
    author={Sujai Hiremath, Jacqueline R.M.A. Maasch, Mengxiao Gao, Promit Ghosal,
  Kyra Gan},
    journal={arXiv preprint arXiv:2405.14496},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.14496},
    primaryClass={cs.LG}
}