Non-negative Weighted DAG Structure Learning

Samuel Rey, Seyed Saman Saboksayr, Gonzalo Mateos

TL;DR

Researchers have developed a new way to learn the structure of Directed Acyclic Graphs (DAGs) by assuming all edge weights are non-negative. This assumption allows them to transform a traditionally "messy" non-convex optimization problem into a well-behaved convex one, providing the first method in this field that guarantees finding the global optimal solution.

What Problem Does This Paper Address?

Learning the "who-points-to-whom" structure of a network (a DAG) from raw data is a cornerstone of causal inference, biology, and machine learning. However, it is notoriously difficult because of the acyclicity constraint: you have to ensure the graph contains no loops (e.g., A points to B, B points to C, and C points back to A).

Historically, this was a combinatorial nightmare (NP-hard). A few years ago, a breakthrough called "NOTEARS" turned this into a continuous optimization problem using a clever mathematical trick. While this made the problem solvable with standard tools, the resulting math was non-convex. This meant algorithms could easily get stuck in "local minima"—essentially giving you a "pretty good" graph that isn't actually the best fit for the data.

Methods

The authors introduce a specialized approach for non-negative weighted DAGs. By assuming that all influences in the network are positive (or zero), they leverage properties of M-matrices to create a new acyclicity function.

  1. The Convex Constraint: They propose a function based on the log-determinant of the adjacency matrix: $h_{ldet}(W) = d \log(s) - \log \det(sI - W)$ They prove that for non-negative matrices, this function is convex and equals zero if and only if the graph is a DAG.

  2. The Optimization Model: They frame the learning task as an abstract convex optimization problem that balances data fidelity (how well the graph explains the observations) with sparsity (keeping the graph simple).

  3. The Algorithm: To solve this, they use the Method of Multipliers (an iterative Augmented Lagrangian approach). Because the underlying problem is convex, this algorithm is guaranteed to converge to the global minimum, rather than just a local heuristic.

Datasets

The paper evaluates the algorithm using reproducible synthetic datasets:

  • Erdős-Rényi (ER) graphs: Random graphs where edges are placed with a fixed probability.
  • Scale-Free (SF) graphs: Graphs that follow a power-law degree distribution, mimicking many real-world social and biological networks.
  • The data is generated using a Linear Structural Equation Model (SEM), where each node's value is a weighted sum of its parents plus some Gaussian noise.

Key Insights and Ideas

  • Non-negativity is a Powerful Prior: While it seems restrictive, many real-world systems (like certain gene regulatory networks or information flow models) naturally have non-negative interactions. Accepting this constraint buys you the "holy grail" of optimization: convexity.
  • Avoiding "Flat" Gradients: Unlike previous methods (like the matrix exponential used in NOTEARS), the proposed log-det function doesn't have stationary points at the solution. This prevents the algorithm from "stalling" near the correct answer.
  • Infinite Sample Consistency: The authors provide a theoretical proof that in the "infinite sample regime" (where you have perfect knowledge of the data distribution), their method is guaranteed to recover the exact true DAG structure.

Key Results

The authors compared their "Logdet" method against state-of-the-art baselines like NOTEARS, DAGMA, and CoLiDE:

  • Superior Accuracy: In terms of Normalized Frobenius Error (how close the estimated weights are to the real ones), the Logdet method's error approaches zero as the number of samples increases, while other methods saturate at a higher error level.
  • Structural Precision: On ER graphs with 100 nodes, the method achieved a Normalized Structural Hamming Distance (SHD) of zero, meaning it perfectly recovered the graph's skeleton and directions in the small-sample regime.
  • Robustness to Noise: The method remained stable even as the variance of the exogenous noise increased, especially when the noise covariance was known or estimated.

Limitations and Future Work

  • The Non-Negativity Constraint: The most obvious limitation is that the method cannot model "inhibitory" relationships (negative weights). If a system has both positive and negative influences, this specific convex relaxation doesn't apply.
  • Linearity: The current framework assumes a linear SEM. While common, many real-world causal relationships are non-linear.
  • Future Directions: The authors suggest that the global optimality of this approach provides a new foundation for characterizing the statistical properties of DAG estimators, which was previously difficult due to the "black box" nature of non-convex solvers. They also hint at extending these convex functions to broader classes of graphs.

Summary updated

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.
BibTeX
@inproceedings{rey2025non,
  author = {Samuel Rey and Seyed Saman Saboksayr and Gonzalo Mateos},
  title = {{Non-negative Weighted DAG Structure Learning}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2025},
  doi = {10.1109/icassp49660.2025.10888302},
}

Loading related content...

Figure