Source-linked AI summary
DAGs with NO TEARS: Continuous Optimization for Structure Learning
Xun Zheng, Bryon Aragam, Pradeep Ravikumar, Eric P. Xing
TL;DR
Learning DAGs is difficult because acyclicity creates an NP-hard combinatorial constraint. NOTEARS reformulates score-based structure learning as continuous optimization using a smooth, exact acyclicity characterization. The resulting method uses standard numerical optimization and achieves scores comparable to the exact global minimizer in practice.
Problem
DAG structure learning is NP-hard because the acyclicity constraint creates a difficult combinatorial optimization problem.
Method
NOTEARS replaces the discrete DAG constraint with a smooth equality constraint that exactly characterizes acyclicity over real matrices, enabling standard numerical solvers.
Results
The method attains scores comparable to the exact global minimizer in practice, although it is guaranteed only to find stationary points.
Takeaways & Limitations
Continuous optimization provides a simple, easily implemented approach to DAG learning without specialized combinatorial search algorithms.
Takeaways & Limitations
Because the continuous program is nonconvex, the method is designed to find stationary points rather than guaranteed global optima.
Abstract
from arXiv · showhide
Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint. In this paper, we introduce a fundamentally different strategy: We formulate the structure learning problem as a purely \emph{continuous} optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting problem can be efficiently solved by standard numerical algorithms, which also makes implementation effortless. The proposed method outperforms existing ones, without imposing any structural assumptions on the graph such as bounded treewidth or in-degree. Code implementing the proposed algorithm is open-source and publicly available at https://github.com/xunzheng/notears.
1 Introduction
DAG structure learning is difficult because acyclicity creates an NP-hard combinatorial constraint. NOTEARS replaces that constraint with an exact smooth characterization, enabling standard optimization and strong empirical performance.
- DAG learning is NP-hard because enforcing acyclicity requires optimization over a difficult combinatorial space.DAGs remain important models in biology, genetics, machine learning, and causal inference.
- NOTEARS converts score-based DAG learning from a combinatorial optimization problem into a continuous program over real matrices.The formulation uses a smooth function whose zero level set exactly characterizes acyclic graphs.
- A smooth equality constraint with computable derivatives replaces the discrete DAG constraint, allowing standard numerical solvers such as L-BFGS.The resulting program remains nonconvex, but avoids specialized combinatorial search algorithms.
- The method jointly estimates sparse DAG structure and parameters using an equality-constrained program and standard numerical solvers.The approach is designed to handle possibly high-dimensional data and find stationary points.
- The method is empirically effective against existing state-of-the-art methods and attains scores comparable to the exact global minimizer in practice.Its guarantees are limited to finding stationary points.
- NOTEARS emphasizes implementation simplicity, requiring about 50 lines of Python code and providing publicly available open-source code.
2 Background
The paper formulates DAG learning through weighted adjacency matrices and smooth score functions, while prior methods face combinatorial complexity and structural or data assumptions. Its continuous formulation addresses the acyclicity constraint without abandoning sparse score-based modeling.
- DAG learning represents n observations of d variables with a weighted adjacency matrix W in R^d×d.The induced graph is obtained from the nonzero pattern of W, which also parameterizes a structural equation model.
- The framework supports linear structural equation models, generalized linear models, and non-Gaussian noise, although experiments focus on linear SEMs.For binary variables, conditional distributions can be modeled with logistic regression.
- The paper uses least-squares loss with ℓ1 regularization to score sparse DAGs and estimate their structure and parameters.The least-squares loss is studied for both Gaussian and non-Gaussian SEMs.
- The central obstacle is that the continuous score still requires enforcing the discrete constraint G(W) ∈ D, making the optimization combinatorial and NP-hard.The number of acyclic structures grows superexponentially with d.
- Existing methods trade off exactness, scalability, and structural assumptions through global combinatorial search, order search, or local edge-wise updates.Exact methods scale poorly, while local approaches often rely on bounded in-degree, bounded treewidth, or edge constraints.
- The paper motivates black-box continuous optimization as a simpler alternative that requires little graphical-model expertise and is easy to implement.This contrasts with existing methods described as conceptually complex and dependent on specialized heuristics.
3 A new characterization of acyclicity
The paper replaces combinatorial acyclicity with a smooth equality constraint that exactly characterizes DAGs over real weighted adjacency matrices. The resulting matrix-exponential formulation is computable, differentiable, and suitable for continuous optimization.
- Binary case: For binary adjacency matrices, traces of matrix powers count closed walks, so vanishing traces characterize acyclicity.An infinite-series characterization requires spectral radius less than one, while finite series can be numerically unstable.
- Binary case: The matrix exponential reweights closed walks by factorial terms, improving numerical manageability over the unweighted infinite-series approach.The paper motivates this construction because rapidly growing closed-walk counts can make alternative characterizations ill-conditioned.
- General characterization: Applying the Hadamard square W ◦W makes the characterization valid for matrices with both positive and negative edge weights.The same acyclicity argument applies first to nonnegative weighted matrices, then extends to signed weights through squared entries.
- General characterization: The proposed function h(W) equals zero if and only if the graph induced by W is acyclic.This extends the binary characterization to arbitrary real-valued matrices using the Hadamard product W ◦W.
- General characterization: The resulting h(W) is smooth, nonnegative, diagnostically informative, and has a simple gradient involving matrix-exponential evaluation.Larger h(W) reflects more cycles or more heavily weighted cycles, and the matrix exponential can be computed in O(d3).
- Algorithm: The NOTEARS algorithm uses the equality constraint h(W)=0, augmented-Lagrangian updates, and thresholding to produce a sparse numerical adjacency matrix.The outlined procedure initializes W and α, solves successive primal subproblems, and returns a thresholded matrix.
4 Optimization
The exact acyclicity constraint yields an equivalent nonconvex equality-constrained program that can be solved with classical numerical optimization. NOTEARS uses augmented-Lagrangian subproblems, smooth or composite solvers, and thresholding, while targeting stationary points rather than guaranteed global optima.
- Equality-constrained program: The equality-constrained program h(W)=0 is equivalent to the original DAG structure-learning problem and is amenable to classical optimization techniques.The constraint remains nonconvex, so the method seeks stationary points rather than generally solving a convex program.
- Augmented Lagrangian: The augmented Lagrangian converts the constrained problem into a sequence of unconstrained subproblems without requiring the penalty parameter to approach infinity.The algorithm is described as a dual-ascent method for the resulting formulation.
- Augmented Lagrangian: For sufficiently large ρ and an initial point near the solution, the augmented-Lagrangian update converges linearly.In experiments, typically fewer than 10 augmented-Lagrangian steps are required.
- Unconstrained subproblems: Low-rank L-BFGS structure and active-set shrinking reduce computation by limiting updates to influential coordinates.The L-BFGS precomputation costs O(m2p + m3), each coordinate update costs O(m), and active-set updates replace O(p) dependence with O(|S|).
- Thresholding: After reaching a stationary point, hard thresholding removes small edge weights and rounds the numerical solution.This post-processing is motivated by reductions in false discoveries reported for thresholded regression coefficients.
5 Experiments
The experiments evaluate NOTEARS on simulated Erdős-Rényi and scale-free graphs under multiple noise models, comparing structure recovery and parameter estimation with existing methods and global optima. NOTEARS improves especially as graph density and size increase, while ℓ1-regularization helps in small-sample settings.
- NOTEARS was compared with FGS, while PC and LiNGAM results were omitted because their accuracy was significantly lower than FGS or NOTEARS.FGS was selected as a state-of-the-art method that scales to large problems.
- Experiments generated Erdős-Rényi or scale-free graphs with random edge weights and Gaussian, Exponential, or Gumbel SEM noise.
- Parameter estimation: NOTEARS produced empirically consistent parameter estimates of the true weight matrix without thresholding, while ℓ1-regularization improved accuracy when samples were insufficient.The thresholding step was needed for structure-learning accuracy, not for the qualitative parameter estimates.
- Structure recovery: NOTEARS significantly improved over FGS on scale-free graphs with more edges, with the difference growing as the number of nodes increased.FGS was competitive for sparse ER-2 graphs but deteriorated rapidly for SF-4 graphs.
- Structure recovery: NOTEARS performed uniformly better across Exponential, Gaussian, and Gumbel noise models, and ℓ1-regularization helped significantly in the small-n setting.
- Structure recovery: Figure 3 reports SHD and FDR relative to the true graph across graph types and SEM noise types, with error bars showing standard errors over 10 simulations.Lower SHD and FDR are better.
6 Discussion
The discussion emphasizes that NOTEARS replaces combinatorial local search with smooth global optimization using standard numerical solvers. Its main limitations are nonconvexity, reliance on smooth scores, cubic matrix-exponential cost, and a fixed suboptimal threshold.
- NOTEARS uses a continuous optimization program and global updates, avoiding assumptions about local graph structure such as bounded in-degree or treewidth.
- Limitations: The equality-constrained program is nonconvex, so black-box solvers can at best find stationary points rather than guaranteed global optima.The paper contrasts this smooth global search with combinatorial local search.
- Limitations: The method relies on a smooth score function to use gradient-based numerical solvers; applying it to nonsmooth or discrete scores remains future work.
- Limitations: Matrix-exponential evaluation gives NOTEARS computational complexity O(d^3), although the constant is small for sparse matrices.The paper reports that roughly 10 iterations are often sufficient but provides no worst-case iteration-complexity result.
- Limitations: The experiments used a fixed, suboptimal thresholding value ω, motivating data-driven choices that adapt to noise-to-signal ratios and graph types.
- The implementation is publicly available, and the method is described as implementable in about 50 lines of Python code.
B Sensitivity of threshold
The threshold controls the trade-off between false discovery rate and true positive rate while preserving acyclicity. A fixed threshold of 0.3 is suboptimal but reasonable across many settings.
- Threshold variation traces an ROC curve of FDR and TPR while ensuring the resulting graph remains a DAG.
- Sorted estimated weights usually contain many zero or near-zero values alongside a smaller set of signal weights.
- With enough samples, a sudden change in the weight distribution can separate near-zero values from signals.
- With insufficient samples, the breakpoint is less clear and the threshold balancing TPR and FDR depends on the setting.
- A fixed threshold ω = 0.3 is suboptimal yet reasonable across many settings because predictive performance is relatively insensitive to threshold value.
C Sensitivity of weight scale
Weight-scale sensitivity experiments show that the minimum threshold needed for acyclicity changes little as edge weights shrink. Accuracy decreases as the signal-to-noise ratio falls.
- Across weight scales α ∈ {1.0, 0.9, 0.8, . . . , 0.1}, the smallest threshold required to obtain a DAG varies minimally.
- Lowering α decreases the signal-to-noise ratio and correspondingly reduces NOTEARS accuracy.
D.1 Experiment details
Experiments use simulated Erdős–Rényi and scale-free DAGs with varied graph sizes, sample sizes, edge densities, and noise models. NOTEARS is compared with FGS, PC, and LiNGAM under stated evaluation and tuning procedures.
- Experiments generate random graphs from Erdős–Rényi or scale-free ensembles and assign independent edge weights.
- Datasets use Gaussian, Exponential, or Gumbel noise and include graphs with d ∈ {10, 20, 50, 100} nodes and n ∈ {20, 1000} samples.
- NOTEARS is evaluated alongside FGS, PC, and LiNGAM for reconstructing the simulated DAGs.
- PC and LiNGAM are omitted from reported comparisons because their accuracy was significantly lower than FGS or NOTEARS.
- FGS receives favorable treatment by counting undirected CPDAG edges as true positives when the true graph contains a directed edge.
- NOTEARS uses threshold ω = 0.3, while its regularization parameter λ is tuned to match FGS's selected edge count as closely as possible.
D.2 Metrics
The experiments evaluate learned DAGs using four graph-reconstruction metrics. SHD summarizes edge additions, deletions, and reversals needed to recover the true DAG.
- The evaluation uses false discovery rate, true positive rate, false positive rate, and structural Hamming distance.
- SHD counts the total edge additions, deletions, and reversals required to convert the estimated DAG into the true DAG.
D.3 Further evaluations
Further evaluations show that NOTEARS generally outperforms FGS across graph types, sample sizes, and SEM noise types, while ℓ1-regularization improves recovery when samples are insufficient. Its estimates also remain close to globally optimal solutions across tested cases.
- With n = 1000, both regularized and unregularized NOTEARS recover ER1 and ER4 graphs well compared with FGS.
- With n = 20, unregularized NOTEARS suffers significantly from identifiability, whereas ℓ1-regularization still enables accurate recovery of the true graph.
- NOTEARS generally outperforms FGS across random graph types and SEM noise settings for both n = 1000 and n = 20.This trend holds without tuning ω optimally for each setting.
- The difference between NOTEARS estimates and globally optimal solutions is small across random graph types and sample sizes.Table 2 defines the comparison as ∆(WG, c W) = F(WG) −F(c W).