PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Role of Sparsity and DAG Constraints for Learning Linear DAGs

Ignavier Ng, AmirEmad Ghassami, Kun Zhang

arXiv:2006.10201v3cs.LGstat.ML

TL;DR

DAG learning faces a large graph search space, and continuous least-squares approaches can require hard acyclicity constraints that complicate optimization. This paper studies the roles of sparsity and DAG constraints, then proposes a likelihood-based objective with soft penalties. Under mild assumptions, it can asymptotically recover a DAG quasi equivalent to the ground truth while avoiding hard DAG constraints.

  • Problem

    Existing continuous DAG-learning methods use least-squares objectives with hard acyclicity constraints, creating optimization difficulties and leaving the roles of sparsity and DAG constraints unresolved.

  • Method

    The paper analyzes sparsity and DAG constraints across linear Gaussian and non-Gaussian models and formulates a likelihood-based score with soft sparsity and DAG penalties.

  • Results

    Under mild assumptions, the likelihood-based objective with soft sparsity and DAG constraints asymptotically returns a DAG quasi equivalent to the ground truth.

  • Takeaways & Limitations

    The proposed unconstrained likelihood-based optimization removes the need for hard DAG enforcement and is reported to scale to thousands of nodes while retaining high accuracy.

  • Takeaways & Limitations

    For equal-noise-variance Gaussian models, whether sparsity or DAG constraints are necessary remains theoretically unclear, despite empirical and bivariate evidence suggesting their usefulness.

Abstract

from arXiv · show

Learning graphical structures based on Directed Acyclic Graphs (DAGs) is a challenging problem, partly owing to the large search space of possible graphs. A recent line of work formulates the structure learning problem as a continuous constrained optimization task using the least squares objective and an algebraic characterization of DAGs. However, the formulation requires a hard DAG constraint and may lead to optimization difficulties. In this paper, we study the asymptotic role of the sparsity and DAG constraints for learning DAG models in the linear Gaussian and non-Gaussian cases, and investigate their usefulness in the finite sample regime. Based on the theoretical results, we formulate a likelihood-based score function, and show that one only has to apply soft sparsity and DAG constraints to learn a DAG equivalent to the ground truth DAG. This leads to an unconstrained optimization problem that is much easier to solve. Using gradient-based optimization and GPU acceleration, our procedure can easily handle thousands of nodes while retaining a high accuracy. Extensive experiments validate the effectiveness of our proposed method and show that the DAG-penalized likelihood objective is indeed favorable over the least squares one with the hard DAG constraint.

1 Introduction

DAG structure learning is important but difficult because the graph space is large and existing continuous methods use hard acyclicity constraints with least-squares objectives. This paper studies these constraints and develops GOLEM, a likelihood-based unconstrained alternative.

  • Motivation: DAG structure learning has applications in biology and healthcare, but learned graphical models are not automatically causal.They can still compactly decompose joint distributions and may acquire causal interpretations under additional conditions.
  • Existing approaches: Constraint-based methods recover Markov equivalence classes using conditional independence tests, whereas score-based methods optimize graph scores and often use local heuristics.The large graph search space motivates heuristic procedures such as GES.
  • Existing approaches: NOTEARS casts linear DAG learning as continuous constrained optimization using an algebraic DAG characterization, but commonly uses least squares with hard acyclicity constraints.The approach has also been extended to nonlinear models through neural networks.
  • Contributions: GOLEM uses soft sparsity and DAG penalties in an unconstrained optimization problem, aiming to recover a DAG equivalent to the ground truth.The paper validates the objective through extensive experiments and bivariate Gaussian analysis.
  • Contributions: The paper compares regression- and likelihood-based objectives and studies sparsity and DAG constraints asymptotically and in finite samples.The analysis covers general linear Gaussian, linear non-Gaussian, and equal-noise-variance Gaussian models.

2 Background

Linear DAG models represent variables through linear structural equations and encode graph structure in a weighted adjacency matrix. NOTEARS instead uses least squares, an ℓ1 penalty, and a hard DAG constraint, whose enforcement can create optimization difficulties.

  • DAG models: A DAG model combines a graph encoding conditional independences with a Markov joint distribution that factorizes according to the graph.The graph and distribution jointly define the model.
  • Linear DAG models: In a linear DAG model, each variable is a linear function of the variables and an exogenous noise term.The corresponding structural equations provide an equivalent representation of the graphical model.
  • Linear DAG models: The nonzero coefficients of the weighted adjacency matrix define graph edges, so estimating the matrix recovers the DAG structure.Given i.i.d. samples, the goal is to infer the coefficient matrix or the graph.
  • NOTEARS: NOTEARS formulates linear DAG learning as continuous optimization with a least-squares loss, ℓ1 penalty, and hard DAG constraint.It solves the constrained problem with an augmented Lagrangian method followed by thresholding.
  • NOTEARS: Hard DAG enforcement requires parameter tuning and can cause numerical and ill-conditioning difficulties as the penalty coefficient approaches infinity.The least-squares objective also omits the likelihood’s log-determinant term.

3 Asymptotic Role of Sparsity and DAG Constraints

The paper analyzes when sparsity and DAG penalties identify the ground-truth structure under different linear models. Its results support replacing hard acyclicity with soft penalties in a likelihood-based objective under mild assumptions.

  • Score formulation: The score combines a likelihood term with penalties encouraging sparsity and DAGness, with penalty coefficients selectable by cross-validation.This formulation enables continuous optimization over weighted adjacency matrices.
  • Model classes: The general linear Gaussian model is not identifiable from the data distribution alone, whereas some identifiable models remain identifiable under specific assumptions.The paper distinguishes nonequal-noise Gaussian models from settings such as linear non-Gaussian and equal-noise-variance Gaussian models.
  • General linear Gaussian case: Under Assumptions 1–3, sparsity-penalized maximum likelihood asymptotically returns a DAG quasi equivalent to the ground truth.This result applies when the triangle assumption holds.
  • General linear Gaussian case: Without the triangle assumption, global minimizers of the likelihood-plus-sparsity objective can be cyclic, although some global minimizers remain acyclic.A second theorem guarantees asymptotic edge-count agreement with the ground truth under Assumptions 1 and 2.
  • General linear Gaussian case: Adding a soft DAG penalty prefers an acyclic solution among solutions with the same edge count, yielding quasi-equivalent DAG recovery under Assumptions 1 and 2.Thus, hard restriction of the search space to DAGs is unnecessary for the likelihood-based objective under the stated assumptions.
  • Identifiable models: For linear non-Gaussian models, asymptotic likelihood maximization can identify the ground-truth DAG without sparsity or DAG constraints, while finite samples still benefit from both penalties.This follows from identifiability over acyclic and cyclic graphical models under the stated noise condition.
  • Identifiable models: For equal-noise-variance Gaussian models, identifiability constrains the estimated graph to DAGs, but the need for sparsity or DAG penalties remains theoretically unclear.The paper points to empirical results and bivariate analysis suggesting that such constraints are needed.

4 GOLEM: A Continuous Likelihood-Based Method

GOLEM replaces NOTEARS’ hard acyclicity constraint with a likelihood-based objective using soft sparsity and DAG penalties. The resulting unconstrained problem is optimized with gradient methods, while asymptotic analysis motivates its recovery behavior.

  • 4.1 Maximum Likelihood Objectives with Soft Constraints: The likelihood objectives correspond to Gaussian models with nonequal or equal noise variances and are related to BIC scores without complexity penalties.The two variants are likelihood-NV and likelihood-EV.
  • 4.1 Maximum Likelihood Objectives with Soft Constraints: GOLEM optimizes likelihood-based objectives with soft ℓ1 sparsity and DAG penalties instead of imposing a hard DAG constraint.The objectives are called GOLEM-NV and GOLEM-EV for nonequal and equal noise-variance settings, respectively.
  • 4.2 Optimization: GOLEM solves the unconstrained objectives with Adam, automatic differentiation, and GPU acceleration, then thresholds near-zero weights to round solutions into discrete graphs.The LogDet and matrix-inverse operations have O(d^3) computational complexity.
  • 4.4 Connection with NOTEARS and Least Squares Objective: The LogDet term distinguishes the likelihood objective from least squares, which decomposes into independent regression tasks and can introduce cycles.The likelihood formulation directly accounts for the determinant term that least squares omits.
  • 4.4 Connection with NOTEARS and Least Squares Objective: In the bivariate asymptotic case, likelihood-EV recovers the ground-truth DAG under a soft ℓ1 or DAG constraint, whereas unconstrained least squares returns a cyclic graph.Least squares recovers the ground truth only with a hard DAG constraint in this proposition.

5 Experiments

Experiments examine constraint roles, comparative accuracy, scalability, and weight robustness across synthetic and biological data. GOLEM performs strongly across identifiable and nonidentifiable settings and scales to large graphs.

  • 5.1 Role of Sparsity and DAG Constraints: In Gaussian-EV experiments, GOLEM-EV and GOLEM-EV-L1 approach the ground-truth DAGs with high TPR as sample size increases, while the unpenalized variant performs poorly.The shrinking gap between GOLEM-EV-L1 and GOLEM-EV suggests sparsity can suffice asymptotically in this setting.
  • 5.1 Role of Sparsity and DAG Constraints: In Gaussian-NV experiments, removing the DAG penalty degrades GOLEM-NV-L1 performance, especially TPR, while both penalties produce solutions close to DAGs.The reported DAG penalty values remain low across settings with soft sparsity and DAG penalties.
  • 5.2 Numerical Results: Identifiable Cases: Gradient-based methods consistently outperform other methods, with GOLEM-NV and GOLEM-EV usually best, including under Exponential and Gumbel noise.FGS, PC, and DirectLiNGAM remain competitive on sparse ER1 graphs but degrade as edge density rises.
  • 5.3 Numerical Results: Nonidentifiable Cases: GOLEM-NV substantially outperforms GOLEM-EV in most Gaussian-NV settings and beats NOTEARS-L1 by a large margin on denser ER2 and ER4 graphs.NOTEARS-L1 is strongest on sparse ER1 graphs, whereas GOLEM-EV performs better on ER4 in the reported comparison.
  • 5.4 Scalability: GOLEM-EV remains competitive as graph size increases, while NOTEARS-L1 degrades and cannot scale beyond 1600 nodes in the reported experiment.GOLEM-EV takes 12.4 hours on 3200-node graphs using GPU parallelization.
  • 5.5 Sensitivity Analysis: GOLEM-EV maintains consistently low normalized SHD and SID across weight scales, whereas NOTEARS-L1 is unstable with low TPR at small scales and high SHD at large scales.The sensitivity analysis uses 50-node ER2 graphs with Gaussian-EV noise.

6 Conclusion

The paper studies the asymptotic and finite-sample roles of sparsity and DAG constraints, then develops a likelihood-based method from those results. GOLEM estimates linear DAG structures accurately and scales to thousands of nodes.

  • 6 Conclusion: The study analyzes sparsity and DAG constraints across general Gaussian, non-Gaussian, and equal-noise-variance linear DAG models.It considers both asymptotic behavior and finite-sample usefulness.
  • 6 Conclusion: GOLEM estimates linear DAG structures efficiently at thousands-node scale while retaining high accuracy.The conclusion presents scalability and accuracy as properties of the proposed method.

Broader Impact

The paper frames DAG structure learning as useful for applications such as biology and healthcare, while emphasizing that estimated structures require expert verification before decision-critical use.

  • Broader Impact: Continuous optimization enables gradient-based solvers and GPU acceleration for structure learning despite the large graph search space.This computational framing supports the scalability discussed for GOLEM.
  • Broader Impact: Decision-critical applications should involve domain-expert verification because estimates may contain spurious edges or reflect confounding, latent variables, measurement errors, or selection bias.Healthcare is given as an example of a decision-critical application.

Appendices

The appendix constructs an example of quasi-equivalent structures and derives an algebraic constraint governing whether one structure can represent the other’s precision matrix.

  • Quasi equivalence: G1 is a complete DAG and can generate any precision matrix, while G2 must represent that matrix through a constrained factorization.The factorization is written as Θ = QQ⊤ with Q following a specified sparsity pattern.
  • Quasi equivalence: The factorization entries impose equations linking a, b, c, d, e, and f to the precision-matrix entries and structural parameters.These relations yield σ1, σ2, σ3 and β13, β21, β32 from the factorization variables.
  • Quasi equivalence: The resulting quartic constraint in e need not have a real root and is satisfied only for a non-measure-zero subset of distributions.Thus, the proposed representation is not generally available across all distributions generated by the complete DAG.

B Proofs of Theorems 1 and 2

The proofs show that likelihood-based optimization with sparsity and DAG penalties recovers a graph with the ground-truth edge count and establishes acyclicity under the paper’s assumptions. They also analyze why least squares behaves differently under hard or absent DAG constraints.

  • Proof setup: Asymptotic likelihood dominance produces parameters whose induced precision matrix matches the observed precision matrix, yielding a candidate graph ˆG containing the distributional structure.The candidate satisfies (I −ˆB)ˆΩ−1(I −ˆB)T = Θ and Θ ∈ Θ(ˆG).
  • Acyclicity: Any cycle in ˆG contradicts quasi equivalence or the triangle condition, with separate arguments for cycles of length greater than three, three, and two.The proof uses conditional independences from v-structures for longer cycles and adjacency contradictions for shorter cycles.
  • Theorem proofs: The sparsity argument combines H(ˆG) ⊆ H(G∗) with opposing edge-count inequalities to conclude |E(ˆG)| = |E(G∗)|.The lower bound follows from Assumption 2, while the upper bound follows from the sparsity penalty.
  • Least squares: In the bivariate example, least squares without a DAG constraint returns a cyclic graph, whereas a hard DAG constraint makes B(b0, 0) the asymptotically unique global minimizer.The hard constraint selects between stationary solutions, and the comparison uses the AM-GM inequality.
  • Least squares: Under a hard DAG constraint, B(b0, 0) is asymptotically the unique global minimizer of the least squares objective.The result holds for b0 ≠ 0 as stated in the proof.
  • Likelihood objectives: For the likelihood-EV objective, the ℓ1 penalty favors B(b0, 0), while the DAG penalty removes cyclic alternatives and makes the acyclic solution unique globally.The analysis also identifies three stationary points, including a saddle point and local minimizers, before adding the DAG penalty.

F Optimization Procedure and Implementation Details

The method solves likelihood-based objectives with soft ℓ1 sparsity and DAG penalties through unconstrained gradient optimization. Implementation choices include Adam, GPU acceleration, thresholding, and fixed penalty settings.

  • Optimization objectives: The unconstrained objectives combine likelihood terms with an element-wise ℓ1 penalty and the DAG penalty h(B), while diagonal entries of B are fixed to zero.The objectives cover nonequal- and equal-noise-variance cases.
  • Optimization procedure: Adam with automatic differentiation and GPU acceleration optimizes B from zero initialization for 1 × 10^5 iterations at learning rate 1 × 10^-3.The authors note that larger learning rates or early stopping could reduce the iteration count.
  • Post-processing: After optimization, weights are thresholded at ω = 0.3; any remaining cycles are removed by iteratively deleting the lowest-absolute-weight edges.Minibatch stochastic optimization may be used when all samples do not fit in memory.
  • Hyperparameters: The experiments use manually selected small penalty coefficients rather than cross-validation because the focus is empirical validation rather than optimal hyperparameter accuracy.The specified values are λ1 = 2 × 10^-3 and λ2 = 5.0 for GOLEM-NV, and λ1 = 2 × 10^-2 and λ2 = 5.0 for GOLEM-EV.

G.2 Experiment Setup

The experiments vary graph families, noise distributions, graph sizes, and sample sizes, then evaluate estimated structures with normalized graph-recovery metrics. Additional variants isolate the roles of sparsity and DAG penalties.

  • Graph generation: The setup uses Erdös–Rényi graphs with expected edge counts d, 2d, or 4d and scale-free graphs generated by preferential attachment.These are denoted ER1, ER2, and ER4 for the three Erdös–Rényi settings.
  • Data generation: Edge weights are sampled from [−2, −0.5] ∪ [0.5, 2], and data are generated with Gaussian-EV, Gaussian-NV, exponential, or Gumbel noise.Gaussian-EV uses unit variances, while Gaussian-NV samples σi from Unif[1, 2].
  • Identifiability: The first three noise models are identifiable in the linear case, and experiments generally use n = 1000 samples per setting.The identifiable models are Gaussian-EV, exponential, and Gumbel.
  • Evaluation: Performance is evaluated using SHD, SHD-C, and other graph metrics, with the first three metrics normalized by the number of nodes and results averaged over 12 simulations.SHD measures edge edits to the ground truth, while SHD-C evaluates recovery of the Markov equivalence class through CPDAGs.
  • Evaluation: CPDAG outputs receive favorable treatment for SHD and TPR, while SID is handled using bounds because it is defined on DAGs.This adjustment applies to FGS and PC outputs containing undirected edges.
  • Penalty ablations: Figures 4 and 5 compare GOLEM variants with both, only ℓ1, or no penalties across sample sizes in identifiable and nonidentifiable Gaussian settings.Lower is better except for TPR, and axes are logarithmic except for TPR.

H.2 Numerical Results: Identifiable Cases

The paper reports additional numerical results for identifiable and nonidentifiable cases, scalability, and sensitivity to weight scaling. These experiments use Figures 6–9 to organize results across noise types, graph densities, graph sizes, and weight scales.

  • Identifiable cases: Figure 6 reports identifiable-case results with sample size n = 1000, using noise types as columns and ER or SF graph densities as rows.ERk and SFk denote ER and SF graphs with kd edges on average.
  • Nonidentifiable cases: Figure 7 reports nonidentifiable Gaussian-NV results with sample size n = 1000 across ER1, ER2, and ER4 graph densities.Lower values are better except for TPR.
  • Scalability and optimization time: Figure 8 reports results for large ER2 graphs in identifiable Gaussian-EV cases with sample size n = 5000.The figure includes structure-learning results and optimization time, with x-axes and optimization time shown on a log scale.
  • Scalability and optimization time: Figure 8 scales NOTEARS-L1 only up to 1600 nodes because of its long optimization time.The caption identifies this as a limitation of the reported scalability experiment.
  • Sensitivity analysis: Figure 9 reports sensitivity-analysis results for different weight scales in identifiable Gaussian-EV cases with sample size n = 1000.Lower values are better except for TPR.
Loading 2006.10201v3…