Abstract
We address the problem of learning the topology of directed acyclic graphs (DAGs) from nodal observations, which adhere to a linear structural equation model. Recent advances framed the combinatorial DAG structure learning task as a continuous optimization problem, yet existing methods must contend with the complexities of non-convex optimization. To overcome this limitation, we assume that the latent DAG contains only non-negative edge weights. Leveraging this additional structure, we argue that cycles can be effectively characterized (and prevented) using a convex acyclicity function based on the log-determinant of the adjacency matrix. This convexity allows us to relax the task of learning the non-negative weighted DAG as an abstract convex optimization problem. We propose a DAG recovery algorithm based on the method of multipliers, that is guaranteed to return a global minimizer. Furthermore, we prove that in the infinite sample size regime, the convexity of our approach ensures the recovery of the true DAG structure. We empirically validate the performance of our algorithm in several reproducible synthetic-data test cases, showing that it outperforms state-of-the-art alternatives.
Introduction
Learning the structure of Directed Acyclic Graphs (DAGs) from observational data is a fundamental challenge in causal inference and machine learning. The primary difficulty arises from the acyclicity constraint, which requires the resulting graph to be free of loops. While recent breakthroughs, such as the NOTEARS framework, transformed this combinatorial problem into a continuous optimization task, they introduced non-convexity. Consequently, existing algorithms often converge to local minima, failing to guarantee the recovery of the globally optimal graph structure.
Methodology
This research introduces a novel approach specifically designed for non-negative weighted DAGs. By assuming that all edge weights in the latent DAG are non-negative—a common characteristic in many physical and biological systems—the authors utilize the properties of M-matrices to develop a convex acyclicity function:
$$h_{ldet}(W) = d \log(s) - \log \det(sI - W)$$
It is mathematically demonstrated that for non-negative matrices, this function is convex and equals zero if and only if the graph is a DAG. This allows the structure learning problem to be formulated as a convex optimization task that balances data fidelity with sparsity. The authors propose a recovery algorithm based on the Method of Multipliers, which is guaranteed to converge to the global minimizer due to the underlying convexity of the problem.
Experimental Results
The proposed "Logdet" method was evaluated against state-of-the-art baselines, including NOTEARS, DAGMA, and CoLiDE, using synthetic Erdős-Rényi (ER) and Scale-Free (SF) graphs generated via Linear Structural Equation Models (SEM).
As illustrated in the figure above:
- Sample Efficiency: In plot (a), the Logdet method's error consistently decreases toward zero as the number of samples increases, whereas competing methods saturate at higher error levels.
- Scalability and Precision: Plot (b) shows that on ER graphs, the method achieves a Normalized Structural Hamming Distance (SHD) of zero across various graph sizes, indicating perfect structural recovery.
- Robustness: Plot (c) highlights the method's stability under increasing exogenous noise variance, particularly when the noise covariance is estimated (Logdet-$\sigma$).
Discussion and Conclusion
The assumption of non-negativity provides a powerful prior that enables the use of convex optimization in DAG learning. This ensures global optimality, a significant advancement over previous non-convex heuristics. While currently limited to linear models and non-negative weights, this framework establishes a rigorous foundation for future research into the statistical properties of DAG estimators and potential extensions to non-linear causal relationships.
Summary updated