Nonlinear Causal Discovery through a Sequential Edge Orientation Approach
This work addresses the challenge of causal discovery in nonlinear settings for researchers and practitioners in fields like statistics and machine learning, offering an incremental improvement over existing methods by enhancing efficiency and robustness.
The authors tackled the problem of learning causal directed acyclic graphs (DAGs) under nonlinear additive noise models by proposing a sequential edge orientation algorithm that sorts edges based on adherence to a pairwise additive noise model and uses a statistical test for direction. The result is a method that is computationally efficient, robust to model misspecification, and outperforms existing nonlinear DAG learning methods in experiments.
Recent advances have established the identifiability of a directed acyclic graph (DAG) under additive noise models (ANMs), spurring the development of various causal discovery methods. However, most existing methods make restrictive model assumptions, rely heavily on general independence tests, or require substantial computational time. To address these limitations, we propose a sequential procedure to orient undirected edges in a completed partial DAG (CPDAG), representing an equivalence class of DAGs, by leveraging the pairwise additive noise model (PANM) to identify their causal directions. We prove that this procedure can recover the true causal DAG assuming a restricted ANM. Building on this result, we develop a novel constraint-based algorithm for learning causal DAGs under nonlinear ANMs. Given an estimated CPDAG, we develop a ranking procedure that sorts undirected edges by their adherence to the PANM, which defines an evaluation order of the edges. To determine the edge direction, we devise a statistical test that compares the log-likelihood values, evaluated with respect to the competing directions, of a sub-graph comprising just the candidate nodes and their identified parents in the partial DAG. We further establish the structural learning consistency of our algorithm in the large-sample limit. Extensive experiments on synthetic and real-world datasets demonstrate that our method is computationally efficient, robust to model misspecification, and consistently outperforms many existing nonlinear DAG learning methods.