Learning Sparse Nonparametric DAGs

Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, Eric P. Xing

TL;DR

This paper introduces a general framework for learning sparse, nonlinear directed acyclic graphs (DAGs) by transforming the traditionally combinatorial problem into a continuous optimization task. By leveraging partial derivatives to characterize acyclicity in nonparametric models, the authors enable the use of powerful tools like neural networks and standard black-box solvers to uncover complex causal structures from data without requiring model-specific assumptions.

What Problem Does This Paper Address?

Learning the structure of Directed Acyclic Graphs (DAGs) is a fundamental challenge in machine learning, essential for tasks like causal inference and understanding complex systems. Historically, this problem has been plagued by two major hurdles:

  1. Combinatorial Complexity: The space of possible DAGs grows super-exponentially with the number of variables, traditionally forcing researchers to use greedy search or constraint-based algorithms that can easily get stuck in local optima.
  2. Restrictive Assumptions: Most efficient methods assume linear relationships between variables. While nonlinear extensions exist, they often rely on very specific model forms (like additive noise models) or specialized, non-standard optimization routines.

This paper builds on the "NOTEARS" approach, which famously turned linear DAG learning into a continuous optimization problem. The authors aim to bring that same "continuous magic" to the nonparametric world, where relationships can be arbitrarily nonlinear and complex.

Methods

The authors propose a framework that replaces the discrete search for a graph with a smooth optimization over a class of functions. The key components are:

  • Nonparametric Acyclicity via Partial Derivatives: In a linear model, an edge exists if a weight is non-zero. In a nonparametric model, the authors show that an edge $X_k \to X_j$ exists if and only if the partial derivative of the function $f_j$ with respect to $X_k$ is non-zero. They use the $L^2$-norm of these partial derivatives to construct a surrogate "weighted adjacency matrix" $W(f)$.
  • Continuous Constraint: They apply the trace exponential constraint from the original NOTEARS paper—$h(W) = \text{tr}(e^{W \circ W}) - d = 0$—to this new derivative-based matrix. This ensures the learned structure is a DAG.
  • Flexible Estimators: The framework is "plug-and-play." The authors demonstrate it using two main types of nonparametric estimators:
  • NOTEARS-MLP: Uses Multi-Layer Perceptrons (neural networks). They prove a key proposition showing that zeroing out the columns of the first layer's weight matrix is sufficient to enforce sparsity and acyclicity, preserving the network's deep expressivity.
  • NOTEARS-Sob: Uses orthogonal basis expansions (Sobolev spaces), which is particularly effective for additive models.
  • Optimization: The problem is solved using the augmented Lagrangian method, which converts the constrained problem into a sequence of unconstrained ones that can be handled by standard solvers like L-BFGS-B.

Datasets

The authors evaluated their framework on both synthetic and real-world data:

  • Synthetic Data: They generated graphs using Erdos-Renyi (ER) and Scale-Free (SF) models. The underlying functional relationships included Additive Gaussian Processes (GP), Index models, and Multi-Layer Perceptrons.
  • Real-World Data: The classic Sachs protein signaling network dataset, which contains 7,466 measurements of 11 proteins. This is a standard benchmark in the causal discovery community because there is a widely accepted "ground truth" consensus network.

Key Insights and Ideas

  • Derivatives as the Universal Language of Edges: The most elegant insight is that partial derivatives provide a mathematically rigorous way to define "graph weights" for any differentiable function. This bridges the gap between high-capacity machine learning models and structural causal models.
  • Proposition 1 (The MLP Shortcut): A potential concern with using deep networks for DAGs is that the dependency might be buried deep in the layers. The authors proved that you only need to look at the input layer. If the $k$-th column of the first weight matrix is zero, the entire network is independent of the $k$-th input. This makes enforcing sparsity computationally efficient.
  • Generality: Unlike previous methods that required specific loss functions or additive noise assumptions, this framework works with any differentiable loss and any differentiable function class.

Key Results

The authors compared their methods (NOTEARS-MLP and NOTEARS-Sob) against several state-of-the-art baselines, including FGS, GNN, and GSGES.

  • Superior Accuracy: NOTEARS-MLP consistently achieved the lowest Structural Hamming Distance (SHD)—a measure of how many edges are wrong—across a wide range of nonlinear settings.
  • Efficiency at Scale: While kernel-based methods like GSGES have $O(n^3)$ complexity, NOTEARS-MLP scales linearly with the number of samples $n$. In one experiment ($d=40, n=1000$), NOTEARS-MLP finished in under 5 minutes, while GSGES took over 90 minutes.
  • Real-World Performance: On the Sachs dataset, NOTEARS-MLP identified a graph with an SHD of 16, outperforming the linear NOTEARS (SHD 22) and the graph neural network baseline GNN (SHD 19).
Figure 1: Structure recovery measured by SHD (lower is better) to ground truth. Left: n = 1000. Middle: n = 200. Right: Average over all configurations. Rows: random graph model (Erdos-Renyi and scale- free). Columns: different types of SEM. NOTEARS-MLP performs well on a wide range of settings, while NOTEARS-Sob shows good accuracy on additive models.

Limitations and Future Work

  • Non-convexity: The optimization problem is non-convex. While the authors found that standard solvers work well in practice, they only guarantee convergence to a stationary point, not necessarily the global optimum.
  • Hyperparameter Sensitivity: The performance can be sensitive to the choice of the regularization parameter ($\lambda$) and the number of hidden units in the MLP. The authors noted that while they used fixed values for their main experiments, tuning these could further improve results.
  • Identifiability: The framework assumes the underlying model is identifiable. In cases where it isn't (e.g., linear Gaussian with equal variances), no score-based method can uniquely recover the DAG without additional information.
  • Future Directions: The authors suggest that integrating more sophisticated nonparametric estimators and exploring different optimization schemes could further enhance the framework's power.

Summary updated

Abstract

We develop a framework for learning sparse nonparametric directed acyclic graphs (DAGs) from data. Our approach is based on a recent algebraic characterization of DAGs that led to a fully continuous program for score-based learning of DAG models parametrized by a linear structural equation model (SEM). We extend this algebraic characterization to nonparametric SEM by leveraging nonparametric sparsity based on partial derivatives, resulting in a continuous optimization problem that can be applied to a variety of nonparametric and semiparametric models including GLMs, additive noise models, and index models as special cases. Unlike existing approaches that require specific modeling choices, loss functions, or algorithms, we present a completely general framework that can be applied to general nonlinear models (e.g. without additive noise), general differentiable loss functions, and generic black-box optimization routines. The code is available at https://github.com/xunzheng/notears.
BibTeX
@inproceedings{zheng2020learning,
  author = {Xun Zheng and Chen Dan and Bryon Aragam and Pradeep Ravikumar and Eric P. Xing},
  title = {{Learning Sparse Nonparametric DAGs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=4BjUbEzUwN},
}
Figure