Learning DAGs by continuous optimization

I keep thinking about directed acyclic graphs (DAGs) because they sit one step before the questions I am interested in. Ask which variables cause which, and I am already assuming a causal graph; but before that graph exists, someone has to recover a set of dependencies that are directed and don’t loop back on themselves. They also turn up in other places: e.g., a knowledge graph in education is a DAG over concepts, arithmetic points to algebra, and never need algebra to get back to arithmetic.

Curriculum prerequisites are directed and acyclic almost by definition – which is exactly why learning one from student data runs into the same wall as causal discovery.

What surprised me is how badly the usual machine-learning playbook fails on it. Almost everything that scaled deep learning runs on gradients. However, asking “Is this graph acyclic?” is a yes-or-no question over a discrete space that explodes super-exponentially – there is no slope to descend. So structure learning stayed in the world of combinatorial search and independence tests, more or less watching the gradient-powered rest of the field pull away.

Why structure learning is hard

Given data over variables, score-based structure learning looks for the graph that best explains the data under some scoring function. The trouble is the search space. Two properties make a naive search intractable:

  1. Directedness means the graph is described by an asymmetric weight matrix .
  2. Acyclicity is a combinatorial constraint. The number of DAGs grows super-exponentially in , and “is this matrix a DAG?” is a discrete, non-smooth question.

This pushed the field toward combinatorial search and conditional-independence tests. Most such methods return a single graph, or the Markov equivalence class (MEC) of graphs that imply the same independencies.

AIn a linear–Gaussian structural equation model (SEM), the least-squares estimator and the maximum-likelihood estimator coincide – which is why early continuous methods could lean on a simple squared-error loss.

Make acyclicity smooth

The 2018 paper NOTEARS (Zheng et al.),instead of searching over discrete graphs, expresses acyclicity as a single smooth equality constraint, turning the whole problem into continuous optimization that off-the-shelf solvers can handle:

For a linear SEM , the score is just least squares,

and the interesting part is in the constraint:

where is the elementwise (Hadamard) product. This quantity is exactly zero if and only if encodes a DAG, and crucially, it is smooth, with an analytic gradient.

Three directions the follow-ups took

The literature after NOTEARS roughly splits along three axes.

1. Beyond linearity

A nonlinear SEM no longer exposes a clean adjacency matrix, so the challenge becomes re-encoding acyclicity when the structure is hidden inside a neural network.

A recurring contrast: GraN-DAG-style methods optimize a log-likelihood, while the NOTEARS line optimizes a least-squares error which matters more than it first appears (see below).

2. Better objectives and constraints

The original least-squares-plus-augmented-Lagrangian method has known pain points.

3. From a single graph to a posterior

Returning one DAG hides genuine uncertainty because many graphs are plausible with finite data. Bayesian structure learning instead targets a posterior,

and methods such as DiBS (Lorch et al., NeurIPS 2021) make this differentiable by working in a continuous latent space over graphs. This is, in a sense, the natural marriage of the smoothness that made NOTEARS work also makes gradient-based Bayesian inference over structures feasible.

How do we measure success?

Two metrics dominate evaluation, and they answer different questions:

SHD tells whether you drew the right picture, SID whether the picture supports the right causal conclusions.

Open problems (and where I think it’s interesting)

  1. Bayesian + continuous optimization. Output a posterior over DAGs, approximated with a neural network keeping the differentiability of NOTEARS while honestly representing uncertainty.
  2. Incomplete data. Jointly learn features and structure when observations are missing. EM is the obvious baseline, but the real question is the inductive bias: e.g., an underlying stochastic process governing how features are distributed over the graph (cf. Kemp’s work on structured priors), and whether the node set is fixed or grows over a lifetime.
  3. Scaling. The adjacency matrix is ; everything about high-dimensional structure learning – optimization stability, identifiability, compute – gets harder as grows.

The throughline of this whole literature is a single reframing: acyclicity, the discrete obstacle, can be made smooth. Almost every advance since has been about choosing a better objective to put on top of that smooth constraint, or a better way to represent uncertainty about the graph underneath it.

References