A novel hybrid approach for positive-valued DAG learning

Causal discovery from observational data is fundamental to statistics and machine learning, yet determining causal direction without interventions necessitates structural assumptions. Existing identifiability research primarily focuses on continuous variables under additive noise models, often neglecting mixed datasets containing ordinal scales, counts, and continuous measurements. This paper investigates causal discovery in Directed Acyclic Graphs (DAGs) where nodes follow either an ordinal distribution (via an ordered logit model) or a regular one-parameter exponential family distribution. We prove that the edge direction between an ordinal and an exponential family node is distributionally identifiable for generic parameter values. Our findings generalize previous Ordinal-Poisson results to the broader exponential family. Computationally, we introduce a score-based exhaustive search and a masked continuous optimization framework using DAGMA for larger graphs. Numerical results validate the theory, recovering edge orientations within a Markov equivalence class that are unidentifiable under classical structural equation models.

Learning causal relations from observational data is challenging because the graph search space grows super-exponentially with the number of variables. Ordering-based methods reduce this space by first identifying the topological ordering, whereas continuous optimization methods explore most likely regions of the space by casting DAG learning as a differentiable objective with an acyclicity constraint. Despite their conceptual appeal, both paradigms face significant scalability limitations in high-dimensional settings, restricting their practical applicability. In this work, we introduce a new formulation for linear causal discovery that tightly integrates these two paradigms to achieve substantial gains in scalability without sacrificing accuracy. Our approach, TriOpt, decomposes the problem into two efficient stages. First, it recovers the topological ordering by exploiting the Sherman-Morrison rank-1 downdate together with the additive structure of linear kernels, enabling fast and scalable ordering estimation. Second, given this ordering, we reformulate structure learning as a convex continuous optimization problem that entirely avoids the need for enforcing costly acyclicity constraints. We theoretically show that, under the true ordering, TriOpt exactly recovers the underlying linear DAG. Empirically, across synthetic, semi-synthetic, and real-world datasets, TriOpt achieves orders-of-magnitude speedups over state-of-the-art linear causal discovery methods in high-dimensional regimes, while maintaining comparable or superior accuracy.

This work addresses the problem of learning directed acyclic graphs (DAGs) from nodal observations adhering to a linear structural equation model. DAG structure learning is a central task in signal processing, machine learning, and causal inference, but it remains challenging because acyclicity is a global combinatorial property and the search space grows superexponentially in the number of nodes. Continuous acyclicity characterizations have led to important algorithmic advances by replacing the discrete DAG restriction with smooth equality constraints on the candidate adjacency matrix. 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 acyclicity characterization devoid of Hadamard products. We propose a new non-negative constrained DAG estimator and develop a tractable, locally convergent algorithm based on the method of multipliers. We further analyze the benign optimization landscape induced by the non-negativity constraints. In the large-sample regime, we show that the true DAG is the unique global minimizer of the population augmented Lagrangian. Moreover, the landscape contains no spurious interior stationary points, and the true DAG is the only acyclic Karush--Kuhn--Tucker (KKT) point. Critically, this allows us to guarantee local convergence to the true DAG given infinite samples. Comprehensive numerical experiments show that the proposed structure identification method improves over state-of-the-art continuous DAG-learning baselines.