Nonlinear Causal Discovery through a Sequential Edge Orientation Approach

• URL: http://arxiv.org/abs/2506.05590v1
• Date: Thu, 05 Jun 2025 21:08:13 GMT
• Title: Nonlinear Causal Discovery through a Sequential Edge Orientation Approach
• Authors: Stella Huang, Qing Zhou,
• Abstract summary: We propose a sequential procedure to orient undirected edges in a completed partial DAG.<n>We prove that this procedure can recover the true causal DAG assuming a restricted ANM.<n>We develop a novel constraint-based algorithm for learning causal DAGs under nonlinear ANMs.
• Score: 5.807183284468881
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Analytic DAG Constraints for Differentiable DAG Learning [83.93320658222717]
  We develop a theory to establish a connection between analytic functions and DAG constraints.<n>We show that analytic functions from the set $f(x) = c_0 + sum_i=1inftyc_ixi | forall i > 0, c_i > 0; r = lim_irightarrow inftyc_i/c_i+1 > 0$ can be employed to formulate effective DAG constraints.
  arXiv  Detail & Related papers  (2025-03-24T23:51:35Z)
• Addressing pitfalls in implicit unobserved confounding synthesis using explicit block hierarchical ancestral sampling [1.7037247867649157]
  We show that state-of-the-art protocols have two distinct issues that hinder unbiased sampling from the complete space of causal models.<n>We propose an improved explicit modeling approach for unobserved confounding, leveraging block-hierarchical ancestral generation of ground truth causal graphs.
  arXiv  Detail & Related papers  (2025-03-12T09:38:40Z)
• Non-negative Weighted DAG Structure Learning [12.139158398361868]
  We address the problem of learning the true DAGs from nodal observations. We propose a DAG recovery algorithm based on the method that is guaranteed to return ar.
  arXiv  Detail & Related papers  (2024-09-12T09:41:29Z)
• BayesDAG: Gradient-Based Posterior Inference for Causal Discovery [30.027520859604955]
  We introduce a scalable causal discovery framework based on a combination of Markov Chain Monte Carlo and Variational Inference. Our approach directly samples DAGs from the posterior without requiring any DAG regularization. We derive a novel equivalence to the permutation-based DAG learning, which opens up possibilities of using any relaxed estimator defined over permutations.
  arXiv  Detail & Related papers  (2023-07-26T02:34:13Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Enhancing Few-shot NER with Prompt Ordering based Data Augmentation [59.69108119752584]
  We propose a Prompt Ordering based Data Augmentation (PODA) method to improve the training of unified autoregressive generation frameworks. Experimental results on three public NER datasets and further analyses demonstrate the effectiveness of our approach.
  arXiv  Detail & Related papers  (2023-05-19T16:25:43Z)
• Practical Algorithms for Orientations of Partially Directed Graphical Models [5.833272638548153]
  In observational studies, the true causal model is typically unknown and needs to be estimated from available observational and limited experimental data. In such cases, the learned causal model is commonly represented as a partially directed acyclic graph (PDAG) The main focus of this paper is on the maximal orientation task, which, for a given PDAG, aims to orient the undirected edges maximally.
  arXiv  Detail & Related papers  (2023-02-28T08:15:49Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  We propose a novel doubly accelerated gradient descent (ADSGD) method for sparsity regularized loss minimization problems. We first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity.
  arXiv  Detail & Related papers  (2022-08-11T22:27:22Z)
• MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models [78.72682320019737]
  We develop a general method, which we call MissDAG, to perform causal discovery from data with incomplete observations. MissDAG maximizes the expected likelihood of the visible part of observations under the expectation-maximization framework. We demonstrate the flexibility of MissDAG for incorporating various causal discovery algorithms and its efficacy through extensive simulations and real data experiments.
  arXiv  Detail & Related papers  (2022-05-27T09:59:46Z)
• Sequential Learning of the Topological Ordering for the Linear Non-Gaussian Acyclic Model with Parametric Noise [6.866717993664787]
  We develop a novel sequential approach to estimate the causal ordering of a DAG. We provide extensive numerical evidence to demonstrate that our procedure is scalable to cases with possibly thousands of nodes.
  arXiv  Detail & Related papers  (2022-02-03T18:15:48Z)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  A structural equation model (SEM) is an effective framework to reason over causal relationships represented via a directed acyclic graph (DAG) Recent advances enabled effective maximum-likelihood point estimation of DAGs from observational data. We propose BCD Nets, a variational framework for estimating a distribution over DAGs characterizing a linear-Gaussian SEM.
  arXiv  Detail & Related papers  (2021-12-06T03:35:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.