PaperlayerView exact revision on arXiv

Source-linked AI summary

DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization

Kevin Bello, Bryon Aragam, Pradeep Ravikumar

arXiv:2209.08037v3cs.LGstat.MEstat.ML

TL;DR

Learning DAGs from data is computationally difficult, and existing continuous acyclicity functions have practical weaknesses. The paper introduces an M-matrix-based log-det characterization and the DAGMA central-path method, which are reported to improve cycle detection, gradients, runtime, and structural accuracy across linear and nonlinear SEMs.

  • Problem

    DAG structure learning is generally NP-hard, while existing continuous acyclicity characterizations based on trace functions have practical limitations.

  • Method

    The paper defines a smooth exact log-det acyclicity characterization over M-matrices and uses it in DAGMA, a central-path method replacing augmented Lagrangian optimization.

  • Results

    DAGMA obtains better accuracy, measured by lower SHD, and much faster computation than state-of-the-art methods on linear and nonlinear SEMs.

  • Takeaways & Limitations

    The log-det characterization offers better large-cycle detection, better-behaved gradients, and about an order-of-magnitude faster computation than hexpm and hpoly.

  • Takeaways & Limitations

    The approach assumes sufficiency, meaning no hidden variable is a common cause of two or more observed variables, an assumption the authors note is difficult to satisfy in practice.

Abstract

from arXiv · show

The combinatorial problem of learning directed acyclic graphs (DAGs) from data was recently framed as a purely continuous optimization problem by leveraging a differentiable acyclicity characterization of DAGs based on the trace of a matrix exponential function. Existing acyclicity characterizations are based on the idea that powers of an adjacency matrix contain information about walks and cycles. In this work, we propose a new acyclicity characterization based on the log-determinant (log-det) function, which leverages the nilpotency property of DAGs. To deal with the inherent asymmetries of a DAG, we relate the domain of our log-det characterization to the set of $\textit{M-matrices}$, which is a key difference to the classical log-det function defined over the cone of positive definite matrices. Similar to acyclicity functions previously proposed, our characterization is also exact and differentiable. However, when compared to existing characterizations, our log-det function: (1) Is better at detecting large cycles; (2) Has better-behaved gradients; and (3) Its runtime is in practice about an order of magnitude faster. From the optimization side, we drop the typically used augmented Lagrangian scheme and propose DAGMA ($\textit{DAGs via M-matrices for Acyclicity}$), a method that resembles the central path for barrier methods. Each point in the central path of DAGMA is a solution to an unconstrained problem regularized by our log-det function, then we show that at the limit of the central path the solution is guaranteed to be a DAG. Finally, we provide extensive experiments for $\textit{linear}$ and $\textit{nonlinear}$ SEMs and show that our approach can reach large speed-ups and smaller structural Hamming distances against state-of-the-art methods. Code implementing the proposed method is open-source and publicly available at https://github.com/kevinsbello/dagma.

1 Introduction

The paper introduces a smooth, exact log-det characterization of DAG acyclicity and the DAGMA central-path method, reporting faster computation and improved structural accuracy than prior approaches.

  • Motivation: Learning DAG structure from passively observed data is generally NP-hard, motivating continuous score-based optimization methods.The paper frames DAG learning as finding a DAG minimizing a given score.
  • Contributions: The proposed log-det function is an exact, smooth acyclicity characterization whose domain uses M-matrices to account for DAG asymmetry.The authors present this as a novel connection between M-matrices, acyclicity, and DAG structure learning.
  • Contributions: The log-det function is invex, so all stationary points are global minima, and those stationary points correspond to DAGs.This establishes a global-optimality property for the characterization's stationary points.
  • Contributions: The log-det characterization is better at detecting large cycles, has better-behaved gradients, and runs about an order of magnitude faster than hexpm and hpoly.Prior trace-based functions detect cycles through powers of the weighted adjacency matrix.
  • Contributions: DAGMA replaces the commonly used augmented Lagrangian scheme with a central-path approach whose limiting solution is guaranteed to be a DAG.Each central-path point solves an unconstrained problem regularized by the log-det function.
  • Experiments: Experiments on linear and nonlinear SEMs report lower SHD and substantially faster results than state-of-the-art methods.The experiments use least-squares and log-likelihood score functions.

2 Notation and background

The paper formulates nonlinear SEMs through variable-dependence functions and converts their graphical structure into a weighted adjacency matrix for score-based learning.

  • Structural equation models: A nonlinear SEM assigns each variable through a function of other variables and an exogenous error, inducing a graphical structure.The Markovian model assumes the exogenous variables are independent.
  • Learning objective: The learning goal is to recover the graph induced by the SEM from n independent samples of the observed-data distribution.The induced graph records dependencies among the variables' structural functions.
  • Score-based formulation: Score-based learning minimizes a quality score over a chosen family of SEM functions using a data matrix of observations.The score sums per-variable losses and can use least-squares or log-likelihood losses with penalties such as BIC or ℓ1.
  • Graph representation: Under the Sobolev-function setup, a variable Xj is independent of Xk exactly when the L2 norm of the partial derivative ∂kfj is zero.This derivative criterion links functional dependence to graph edges.
  • Graph representation: The SEM graph is represented by a weighted adjacency matrix W(f), with G(f) acyclic exactly when W(f) is acyclic.In practice, the functions are replaced by a finite-dimensional parametrized family such as deep neural networks.

3 A new characterization of acyclicity via log-determinant and M-matrices

The paper characterizes acyclicity with a differentiable log-determinant function defined on an M-matrix-related domain. This characterization is exact, has analytically tractable optimization properties, and improves cycle detection, gradients, and runtime over trace-based alternatives.

  • Log-determinant characterization: DAGs are identified through nilpotency: a nonnegative weighted adjacency matrix represents a DAG exactly when all eigenvalues are zero.This motivates converting the spectral condition into a log-determinant characterization.
  • Log-determinant characterization: M-matrices define the domain where the log-determinant implication is exact, using matrices of the form A = sI − B with B ≥ 0 and s > ρ(B).The resulting set W_s contains DAGs, is path-connected, and expands as s increases.
  • Log-determinant characterization: The log-determinant acyclicity function satisfies h_ldet(W) = 0 if and only if W is a DAG.Its domain and definition rely on the positive determinant of the associated M-matrix.
  • Properties: The function is invex: all stationary points are global minima, and those stationary points correspond to DAGs.At DAGs, the Hessian is positive semidefinite; gradient and Hessian structure also links nonzero entries to directed walks and cycles.
  • Preference over existing regularizers: At d = 13, h_exp(W) ≈ 10^-9 and h_poly(W) ≈ 10^-14, whereas the log-determinant remains bounded away from zero and can detect larger cycles.The log-determinant can remain away from zero even for a 100-node cycle graph and is computed about 10x faster than h_exp and h_poly.
  • Preference over existing regularizers: At s = 1, the log-determinant gradient does not diminish walks of any length, unlike the factorial or polynomial attenuation affecting h_exp and h_poly.This gives larger gradients for optimization and helps retain signals from long cycles.

4 Optimization

DAGMA replaces the augmented Lagrangian approach with a central-path-like sequence of unconstrained problems regularized by the log-determinant acyclicity function. As the central-path coefficient tends to zero, the method is guaranteed to return a DAG.

  • 4 Optimization: DAGMA minimizes a score function with an ℓ1 penalty while using the log-determinant acyclicity function as a regularizer.The method solves a sequence of unconstrained problems rather than the usual constrained formulation.
  • 4 Optimization: The algorithm initializes W(θ(0)) inside the domain Ws and repeatedly solves unconstrained subproblems while decreasing µ(t).The zero matrix lies in the interior of Ws, so experiments initialize θ(0) = 0.
  • 4 Optimization: As µ(t) → 0, Algorithm 1 is guaranteed to return a DAG.This guarantee distinguishes DAGMA from methods that often require post-processing such as thresholding to obtain a DAG.
  • 4 Optimization: The parameter s may be any positive value because DAGs lie in Ws for every s > 0, and it may also vary across iterations.The paper gives an example schedule s = {1, 0.9, 0.8, 0.8}.

5 Experiments

The experiments evaluate DAGMA against established methods on linear and nonlinear SEMs across graph sizes and data types. DAGMA generally achieves faster computation and improved structural accuracy, while matching SHD comparably in neural-network settings.

  • 5 Experiments: DAGMA is compared with GES, PC, NOTEARS, and GOLEM on linear and nonlinear SEMs without hyperparameter optimization.The authors use reasonable fixed settings to avoid unintentionally biased comparisons.
  • 5 Experiments: The main text presents only a subset of experiments, with full settings and method comparisons provided in Appendix C.Results are reported against the most competitive methods when some methods perform substantially worse.
  • 5 Experiments: The evaluation covers linear SEMs with Gaussian, Gumbel, and exponential noises, plus nonlinear SEMs with binary and continuous data.The nonlinear settings use logistic models for binary data and continuous additive-noise models with multilayer perceptrons.
  • 5 Experiments: On ER4 and SF4 graphs, DAGMA shows significant speedups and lower SHD than NOTEARS and GOLEM for linear SEMs across both moderate and large node counts.The reported linear regimes span d ∈ [20, 100] and d ∈ [200, 1000].
  • 5 Experiments: For logistic nonlinear SEMs, DAGMA attains major speedups and SHD improvements against NOTEARS.For neural-network nonlinear models, DAGMA is comparable in SHD to NONLINEAR NOTEARS while obtaining significant speedups.

6 Final Remarks

The paper assumes sufficiency and highlights that this assumption is difficult to satisfy in practice. It also notes that continuous DAG-learning methods still lack formal guarantees for learned structures.

  • 6 Final Remarks: The work assumes sufficiency, meaning no hidden variable is a common cause of at least two observed variables.The authors note that scenarios satisfying this assumption are difficult to find in practice.
  • 6 Final Remarks: The continuous framework for learning DAGs still lacks formal guarantees that predicted edges correspond to causal relations.Because real applications lack the ground-truth DAG, uncertainty remains about the causal meaning of learned edges.

Checklist

The checklist records affirmative responses for claim coverage, limitations, theoretical assumptions and proofs, reproducibility materials, training details, and error bars. It also records that the paper addresses societal impacts and asset-related documentation where applicable.

  • Checklist: The authors report that the paper accurately reflects its main claims and describes its limitations.The checklist refers readers to Section 6 for the limitations discussion.
  • Checklist: The paper reports discussing potential negative societal impacts and conforming to ethics review guidelines.The checklist marks both items affirmatively and refers to Section D for societal impacts.
  • Checklist: The paper reports its theoretical assumptions and includes complete proofs of its theoretical results.The checklist refers to Sections 2 and 3 for assumptions and Appendix A for proofs.
  • Checklist: The authors report providing code, data, instructions, training details, and error bars for the main experiments.The checklist points to Appendix C for reproducibility and training information.
  • Checklist: Existing assets are cited, their licensing is marked not applicable, and new assets are included through a URL or supplemental material.Consent and personally identifiable information questions are marked not applicable.

A.1 Proof of Theorem 1

The proof establishes that the log-determinant characterization is well-defined on its M-matrix domain and vanishes exactly at DAGs, which are its local and global minima. It also shows that the domain is path-connected and that the central-path limit yields a DAG.

  • ldet(W)=0 if and only if W corresponds to a DAG, so DAGs are stationary points and local and global minima of the characterization.
  • The log-determinant gradient is well-defined inside Ws because I −W ◦W is an M-matrix with an existing inverse.
  • DAGs belong to the domain Ws because their weighted adjacency matrices are nilpotent, giving ρ(W ◦W)=0.
  • The domain Ws is path-connected because every W in Ws can be continuously scaled to the zero matrix while remaining in Ws.
  • At the limit of the central path, invexity of the log-determinant function guarantees that the resulting solution is a DAG.

B.2 Further Details for Section 3.2

The log-determinant characterization avoids the cycle-detection and gradient problems of alternative series-based functions while enabling faster computation through standard matrix-factorization routines.

  • The log-determinant function does not diminish cycles of any length, unlike exponential and polynomial characterizations whose values can decay toward numerical zero.
  • The alternative trace-inverse characterization is numerically unstable because walks of length k receive weights proportional to k+1, causing potentially exploding gradients.
  • For s=1, the log-determinant gradient weights cycles of every length equally, whereas exponential and polynomial gradients can suffer from vanishing gradients.
  • The log-determinant characterization is empirically faster because log-determinants and inverses use optimized matrix factorizations and linear-system solvers.

C Detailed Experiments

The experiments evaluate DAG learning across graph types, noise distributions, SEM classes, and node counts using SHD, runtime, TPR, and FDR. Across these settings, DAGMA generally achieves lower SHD and substantially faster runtimes than competitive methods, while biased data remain a misuse-related limitation.

  • Experimental setup: Experiments sample ER and SF DAGs, simulate linear and nonlinear SEMs with Gaussian, exponential, or Gumbel noise, and usually generate n=1000 observations.
  • Metrics: Performance is evaluated using SHD, TPR, FDR, and runtime across graph and noise settings, with lower values preferred except for TPR.
  • Small to moderate graphs: 74.9% and 76.5% SHD improvements at d=100 accompany 7.7x and 19.1x speedups over GOLEM and NOTEARS, respectively.
  • Large graphs: 90.2% and 65.5% SHD improvements at d=800 accompany 6.2x and 25x speedups over GOLEM and NOTEARS, respectively.
  • Sparse graphs: 22.5% lower SHD and an 8.5x speedup over GOLEM occur at d=1000 in the sparser-graph comparison.
  • Dense graphs: 73.1% and 44.5% SHD improvements at d=100 accompany 4.8x and 20.6x speedups over GOLEM and NOTEARS on denser ER6 graphs.
  • Nonlinear models: On nonlinear models, DAGMA and NOTEARS have similar SHD while DAGMA achieves 3x to 10x speedups; GOLEM is excluded because it only handles linear models.
  • Broader impacts: Applying the method to biased data can produce relationships absent from reality and support incorrect causal claims because dataset bias is not formally addressed.
Loading 2209.08037v3…