Exploiting Non-Negativity in DAG Structure Learning

The gist This work addresses the problem of learning directed acyclic graphs (DAGs) from nodal observations generated by a linear structural equation model by exploiting non-negativity in edge weights to obtain a simpler characterization of acyclicity and develop an augmented-Lagrangian algorithm based on the method of multipliers.

Exploiting Non-Negativity in DAG Structure Learning

The paper focuses on DAGs with nonnegative edge weights, which removes sign cancellations that occur in powers of signed matrices, enabling acyclicity to be characterized through simpler smooth functions that do not require the Hadamard product and avoids the degeneracy of KKT conditions. This structure allows for a more amenable optimization landscape compared to formulations based on Hadamard-product acyclicity constraints. When observations follow the linear SEM in (1), an estimator is proposed by combining a least-squares data-fitting term with a sparsity-promoting penalty, constrained by non-negativity and a spectral-radius condition.

Proposed Algorithm and Formulation

The paper proposes an augmented Lagrangian algorithm based on the method of multipliers to solve the regularized non-negative DAG learning problem. The augmented Lagrangian is formulated as Lc(W, λ):= Fn(W) + λh(W) + c squared h(W) squared, where Fn(W) is the score function and h(W)=0 defines the acyclicity constraint. The algorithm proceeds in three steps:

1. Update W by solving W(k+1) = arg min W≥0, ρ(W)<s Lc(k) (W, λ(k)) using projected first-order iterations.

2. Update the Lagrange multiplier according to λ(k+1) = λ(k) + c(k)h(W(k+1)).

3. Update the penalty parameter adaptively using a rule that increases c when the acyclicity violation is not reduced sufficiently.

Population Optimization Landscape Analysis

The analysis of the population augmented Lagrangian reveals a favorable landscape under standard identifiability assumptions. The key findings regarding the population augmented Lagrangian L¯c(W, λ) are:

the true DAG W0 is the unique global minimizer of L¯c(·, λ) over W1

Furthermore, Theorem 2 proves that there are no spurious interior stationary points of the population augmented Lagrangian. The analysis shows that for the threshold case λ = 2, the only classical stationary point is W0. This indicates that every acyclic KKT point is the true DAG.

Numerical Evaluation and Performance

Numerical experiments on synthetic and real-world data support these theoretical findings, showing that the proposed method improves over state-of-the-art continuous DAGlearning alternatives. The results demonstrate that the proposed Logdet method consistently attains the lowest estimation error among compared methods as the number of samples increases. Specifically, for ER graphs, Logdet recovers the correct support with essentially zero normalized SHD across considered graph sizes. On the Sachs protein-signaling benchmark, NOMAD attains the lowest SHD and FDR while matching CoLiDE-Fix in TPR.

Conclusions

The non-negativity assumption provides a modeling prior by ruling out sign cancellations, enabling a simple smooth characterization of acyclicity that keeps the gradient informative at feasible DAGs. The proposed method, NOMAD, is an augmented-Lagrangian algorithm based on the method of multipliers. The analysis confirms that under identifiability, the true DAG is the unique global minimizer of the augmented Lagrangian with no spurious interior stationary points. Experiments validate that exploiting non-negativity can improve both weighted estimation and structural recovery relative to established continuous DAG-learning baselines.

APPENDIX A

PROOF OF THEOREM 1

The proof establishes a technical lower bound for the augmented Lagrangian, showing L¯c(W, λ) ≥ ϕλ,c(h(W)). This bound reduces the analysis to a scalar function of the acyclicity value t = h(W). The function ϕλ,c is shown to be strictly convex and minimized at t = 0 over [0,∞), yielding a strict lower bound of d for L¯c(W, λ). This proves that W0 is a global minimizer of L¯c(·, λ) over W1.

APPENDIX B

PROOF OF THEOREM 2

The proof analyzes the first-order equation ∇WL¯c(W, λ) = 0 by transforming it into a scalar condition involving the common singular values of C. This leads to the scalar equation 2e−2h(W)/d = λ + ch(W). When λ > 2, this equation has no solution on [0,∞), proving no classical stationary point exists in W1. When λ = 2, the only solution is h(W) = 0, which implies W = W0.

APPENDIX C

PROOF OF THEOREM 3

The proof uses KKT conditions to derive a necessary inequality F¯(W) ≤ d(1 + c squared h(W)). For acyclic KKT points, this forces F¯(W) = d, which combined with the identifiability condition implies W = W0.

REFERENCES

[1] S. Rey, S. S. Saboksayr, and G. Mateos, “Non-negative weighted dag structure learning,” in IEEE Intl. Conf. Acoustics, Speech and Signal Process (ICASSP). IEEE, 2025.

[6] K Sachs, O. Perez, D. Pe’er, D. A. Lauffenburger, and G. P Nolan, “Causal protein-signaling networks derived from multiparameter singlecell data,” Science, vol 308.

[18] X Zheng, B Aragam, P K Ravikumar, and E P Xing, “DAGs with NO TEARS: Continuous optimization for structure learning,” Conf. Neural Inform. Process. Syst., vol 31.

[21] K Bello, B Aragam, and P Ravikumar, “DAGMA: Learning DAGs via M-matrices and a log-determinant acyclicity characterization,” Conf. Neural Inform. Process. Syst., vol 35.

[23] S S Saboksayr, G Mateos, and M Tepper, “CoLiDE: Concomitant linear DAG estimation,” Intl. Conf. Learn Repr (ICLR), 2024.

[17] P.-L Loh and P Buhlmann, “High-dimensional learning of linear causal networks via inverse covariance estimation,” J Mach Learning Res., vol 15.

[26] H Ajorlou, S Rey, G Mateos, G Leus, and A G Marques, “Build With Precision: Bottom-Up Inference of Linear DAGs,” in IEEE Intl Conf Acoustics Speech Signal Process (ICASSP). IEEE, 2026.

[15] D M Chickering and D Heckerman, “Efficient approximations for the marginal likelihood of Bayesian networks with hidden variables,” Mach. Learn., vol 29.

[16] D M Chickering, D Heckerman, and C Meek, “Large-sample learning of Bayesian networks is NP-hard,” J Mach. Learning Res., vol 5.

1. No-negative DAG learning systems can be improved by replacing difficult non-convex optimization landscapes with a simpler characterization of acyclicity through a smooth function that does not rely on Hadamard products. This allows the system to avoid the degeneracy of KKT conditions, leading to more robust first-order methods.

2. A system employing the proposed method can perform structure learning by solving a regularized non-negative DAG learning problem using an augmented-Lagrangian algorithm based on the method of multipliers. This formulation is specifically designed to handle DAGs with nonnegative edge weights and provides a principled mechanism for promoting acyclicity.

3. The improved AI system can achieve superior accuracy in structure recovery, as numerical experiments show that the proposed method improves over state-of-the-art continuous DAGlearning alternatives, specifically by achieving lower normalized Frobenius error and structural Hamming distance on benchmarks like the Sachs protein-signaling dataset.

4. The system can be enhanced to operate effectively in finite-sample regimes, as the proposed method exhibits consistent finite-sample behavior where the estimation error decreases as n grows, unlike baselines that show saturation, suggesting better convergence toward the true population solution.

5. The improved system can utilize a favorable population optimization landscape where the true DAG is the unique global minimizer of the proposed augmented Lagrangian, ensuring that structure inference converges to the correct topology under standard identifiability assumptions.

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.