Exploiting Non-Negativity in DAG Structure Learning

• URL: http://arxiv.org/abs/2605.19947v1
• Date: Tue, 19 May 2026 15:03:33 GMT
• Title: Exploiting Non-Negativity in DAG Structure Learning
• Abstract summary: This work addresses the problem of learning directed graphs (DAGs) from nodal observations generated by a linear structural equation model.<n>We formulate a regularized non-negative DAG learning problem and develop an algorithm based on the method of multipliers.<n>Experiments on synthetic and real-world data show that the proposed method improves over state-of-the-art continuous DAG-learning alternatives.
• Score: 25.970789484705318
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work addresses the problem of learning directed acyclic graphs (DAGs) from nodal observations generated by a linear structural equation model. DAG learning is a central task in signal processing, machine learning, and causal inference, but it remains challenging because acyclicity is a global combinatorial property. Continuous acyclicity constraints have led to important algorithmic advances by replacing the discrete DAG constraint with smooth equality constraints. However, existing formulations still involve difficult non-convex optimization landscapes and may suffer from degenerate first-order optimality conditions. Here, we restrict attention to DAGs with non-negative edge weights and exploit this additional structure to obtain a simpler characterization of acyclicity. Building on this characterization, we formulate a regularized non-negative DAG learning problem and develop an algorithm based on the method of multipliers. We further analyze the benign optimization landscape induced by non-negativity. In the population regime, we show that the true DAG is the unique global minimizer of the proposed augmented-Lagrangian formulation; moreover, the landscape contains no spurious interior stationary points, and the true DAG is the only acyclic KKT point. Numerical experiments on synthetic and real-world data show that the proposed method improves over state-of-the-art continuous DAG-learning alternatives.

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)
• 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)
• Reinforcement Learning for Causal Discovery without Acyclicity Constraints [35.753289086012224]
  We introduce ALIAS, a novel approach to causal discovery powered by the reinforcement learning machinery.<n>Our method features an efficient policy for generating DAGs in just a single step with an optimal quadratic complexity.<n>We provide compelling empirical evidence for the strong performance of ALIAS in comparison with state-of-the-arts in causal discovery.
  arXiv  Detail & Related papers  (2024-08-24T03:12:21Z)
• Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning [71.9954600831939]
  Positive-Unlabeled (PU) learning is vital in many real-world scenarios, but its application to graph data remains under-explored. We unveil that a critical challenge for PU learning on graph lies on the edge heterophily, which directly violates the irreducibility assumption for Class-Prior Estimation. In response to this challenge, we introduce a new method, named Graph PU Learning with Label Propagation Loss (GPL)
  arXiv  Detail & Related papers  (2024-05-30T10:30:44Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Discovering Dynamic Causal Space for DAG Structure Learning [64.763763417533]
  We propose a dynamic causal space for DAG structure learning, coined CASPER. It integrates the graph structure into the score function as a new measure in the causal space to faithfully reflect the causal distance between estimated and ground truth DAG.
  arXiv  Detail & Related papers  (2023-06-05T12:20:40Z)
• On the Sparse DAG Structure Learning Based on Adaptive Lasso [39.31370830038554]
  We develop a data-driven DAG structure learning method without the predefined threshold, called adaptive NOTEARS [30] We show that adaptive NOTEARS enjoys the oracle properties under some specific conditions. Furthermore, simulation results validate the effectiveness of our method, without setting any gap of edges around zero.
  arXiv  Detail & Related papers  (2022-09-07T05:47:59Z)
• 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)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints. We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
  arXiv  Detail & Related papers  (2021-06-14T07:11:36Z)
• Learning DAGs without imposing acyclicity [0.6526824510982799]
  We show that it is possible to learn a directed acyclic graph (DAG) from data without imposing the acyclicity constraint. This approach is computationally efficient and is not affected by the explosion of complexity as in classical structural learning algorithms.
  arXiv  Detail & Related papers  (2020-06-04T16:52:01Z)

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.