Source-linked AI summary
Learning Sparse Nonparametric DAGs
Xun Zheng, Chen Dan, Bryon Aragam, Pradeep Ravikumar, Eric P. Xing
TL;DR
Learning DAGs generally requires choosing specialized model assumptions and algorithms, especially for nonlinear and nonparametric settings. This paper extends continuous acyclicity characterization using partial-derivative-based sparsity, yielding a generic optimization framework for broad SEM classes; off-the-shelf solvers produce competitive and often superior stationary-point solutions despite nonconvexity.
Problem
Existing DAG-learning methods typically rely on specific model assumptions and specialized algorithms, creating a need for a general framework spanning different DAG models.
Method
The paper extends smooth acyclicity characterization to nonparametric SEMs using partial derivatives and formulates finite-dimensional differentiable programs solvable with generic optimization routines.
Results
The framework applies to nonlinear and nonparametric SEMs, including additive and index models, while off-the-shelf solvers return stationary points that outperform other state-of-the-art methods in experiments.
Takeaways & Limitations
The resulting framework subsumes many parametric, semiparametric, and nonparametric models and updates the entire graph simultaneously using standard optimization algorithms.
Takeaways & Limitations
The optimization program is nonconvex and can, at best, be solved to stationarity; identifiability can also fail for jointly Gaussian variables with linear structural functions.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces a general continuous framework for score-based learning of sparse DAGs across nonlinear, nonparametric, and semiparametric models. It extends algebraic acyclicity characterization beyond weighted adjacency matrices and supports generic optimization routines.
- Motivation: Existing DAG-learning methods typically require specific model assumptions and specialized algorithms, placing substantial model-selection burden on users.The paper motivates a framework spanning linear, parametric, and nonparametric DAG models without specialized algorithms.
- Core contribution: The resulting optimization problem applies to nonlinear and nonparametric SEMs, including additive models and index models, and can be solved to stationarity with generic solvers.This removes the necessity for specialized algorithms and models in the stated framework.
- Core contribution: The framework extends smooth algebraic characterization of acyclicity from linear SEMs to general nonparametric models without weighted-adjacency-matrix parametrization.Partial derivatives provide the basis for this extension, while linear parametrization remains a special case.
- Evaluation: The paper studies neural-network and orthogonal-basis nonparametric estimators and evaluates the framework across nonparametric and semiparametric models against recent methods.The empirical evaluations are intended to demonstrate effectiveness and generality.
- Results: Although the score-based program is nonconvex, off-the-shelf solvers return stationary points that outperform other state-of-the-art methods in the reported experiments.The implementation can use standard machine-learning libraries such as PyTorch.
2 Background
The background formulates DAG learning through structural equation models and identifies acyclicity and sparsity as central constraints. The paper addresses the lack of a weighted adjacency matrix in general nonparametric models by using partial derivatives to construct a suitable surrogate.
- SEM formulation: The SEM represents each variable through a function of all variables, while parent structure determines which inputs each function may depend on.The functions can include non-additive errors through known transformations and encompass additive noise, linear, generalized linear, and additive models.
- SEM formulation: Given observations and a loss such as least squares or negative log-likelihood, the goal is to learn functions whose induced graph matches the dependency graph encoded by the data.The approach uses a score-based optimization formulation.
- Problem formulation: DAG learning must enforce both acyclicity and sparsity, but the weighted adjacency-matrix representation used by linear and generalized linear models is unavailable for general nonparametric models.The paper therefore develops a surrogate that permits the trace exponential regularizer to be applied.
- Identifiability: Existing approaches commonly assume a specific model, establish identifiability for it, and design a specialized learning algorithm, whereas this framework is intended for any identifiable model.The paper positions its approach as generic rather than tied to one model form or algorithm.
- Identifiability: Identifiability is not universal: jointly Gaussian variables with linear structural functions can yield a graph that is not uniquely specified.Under additive noise, non-Gaussian linear errors or nonlinear functions generally restore identifiability.
- Nonparametric structure: Partial derivatives measure dependence on each variable without assuming a particular nonparametric form, enabling estimators such as multilayer perceptrons and basis expansions.For Sobolev functions, independence from a variable is characterized by a zero L2 norm of the corresponding partial derivative.
3 Characterizing acyclicity in nonparametric SEM
The paper extends continuous acyclicity characterization from linear DAGs to nonparametric SEMs by encoding variable dependence through partial derivatives. This yields a general framework covering nonparametric, parametric, and semiparametric models, including ANMs, GLMs, additive models, and index models.
- Nonparametric acyclicity: The linear trace-exponential characterization is generalized by replacing the weighted adjacency matrix with a derivative-based dependence matrix W(f).For Sobolev functions, ∥∂_k f_j∥_L2 = 0 exactly when f_j is independent of X_k, so W(f) encodes nonparametric dependencies.
- Nonparametric acyclicity: The resulting continuous program is a genuine generalization of the linear formulation and reduces to it when all structural functions are linear.The same acyclicity constraint can therefore be used across linear and nonparametric settings.
- Special cases: The framework applies to general nonparametric models and includes additive noise models, generalized linear models, additive models, and index models as special cases.The paper also discusses identifiability conditions for these model classes.
- Special cases: For additive noise models, derivative-based dependence cannot generally be simplified without additional assumptions, although sufficiently smooth nonlinear models are identifiable under the cited conditions.The ANM formulation is a special case with g_j(s) = s.
- Special cases: For GLMs, the framework recovers the parametric adjacency condition for linear mean functions and encompasses known identifiable cases including Poisson and non-Gaussian models.The paper gives logistic regression as an example of a GLM link function.
4 Optimization
The infinite-dimensional nonparametric program is made tractable by choosing differentiable approximation families and translating both the loss and dependence constraint into finite-dimensional parameterizations. The resulting smooth, sparsity-penalized program can be handled with generic optimization routines, including neural-network and basis-expansion implementations.
- Optimization framework: The optimization recipe selects a conditional-expectation model, chooses an approximation family, parameterizes the loss and constraint, and solves the resulting finite-dimensional problem.This plug-and-play procedure supports neural networks, orthogonal series, and other differentiable models.
- Optimization framework: Approximating f_j with parameters θ replaces the infinite-dimensional dependence quantity W(f) with W(θ), whose dimension may depend on n.This replacement is the key step enabling tractable optimization.
- Multilayer perceptrons: Multilayer perceptrons can approximate any f_j ∈ H1(R^d) arbitrarily well by increasing hidden-layer or hidden-unit capacity.The paper characterizes independence from an input coordinate through zeros in the corresponding first-layer column.
- Multilayer perceptrons: The MLP independence constraint removes dependence on an input coordinate without sacrificing the expressive power of multiple hidden layers.The proposition establishes equality between MLPs independent of u_k and MLPs whose kth first-layer column is zero.
- Basis expansions: Orthogonal basis expansions provide an alternative approximation route for additive and index models, with finite-series truncation controlling approximation error.For sufficiently smooth functions, the stated overall approximation error is O(d / min_k R_k).
- Empirical illustration: Figure 1 compares SHD across sample sizes, graph models, and SEM types, with NOTEARS-MLP performing broadly and NOTEARS-Sob performing well on additive models.SHD is lower-is-better and the right panel averages over configurations.
- Solving the continuous program: The finite-dimensional objective is an ℓ1-penalized smooth minimization under a differentiable equality constraint, allowing generic solvers such as L-BFGS-B.The program is nonconvex and can be solved at best to stationarity, although experiments report competitive or superior practical performance.
5 Experiments
The experiments evaluate structure recovery across nonlinear and nonparametric SEMs, graph types, sample sizes, and hidden-layer sizes. NOTEARS-MLP generally performs strongly, while estimator choice, preprocessing, and sample size affect results.
- Structure learning: NOTEARS-MLP or NOTEARS-MLP++ achieves competitive SHD relative to CAM across sample sizes, graph models, and SEM types.Adding neighborhood selection and pruning improves NOTEARS-MLP and NOTEARS-Sob on additive GP and GP settings, matching or improving against CAM.
- Structure learning: The evaluation covers ER and scale-free DAGs with 10, 20, or 40 nodes, 200 or 1000 samples, and four nonlinear data-generation mechanisms.The mechanisms are additive GP, index, MLP-based ANM, and GP-based ANM.
- Structure learning: NOTEARS-MLP attains the best SHD across a wide range of settings, especially for MLP and index data-generating mechanisms.Its performance remains stable across graph types with varying density and degree distribution.
- Structure learning: NOTEARS-Sob performs well for additive GP SEMs but degrades when the ground truth is not additive, whereas GSGES performs better on GP settings.The GP advantage is accompanied by O(n^3) complexity, compared with linear dependence on n for the NOTEARS estimators.
- Runtime and scalability: On ER2 with d = 40 and n = 1000, GSGES averages over 90 minutes, whereas NOTEARS-MLP averages under five minutes.NOTEARS-MLP requires O(nd^2m+d^2m+d^3) flops per L-BFGS-B iteration.
- Sensitivity to number of hidden units: Increasing hidden units improves SHD through 20 units, but with n = 200, further increases deteriorate SHD while n = 1000 remains similar.The result reflects a trade-off between greater representational flexibility and the samples required to estimate larger networks.
- Real data: On the Sachs dataset, NOTEARS-MLP reports SHD 16 with 13 estimated edges, compared with SHD 22 for NOTEARS and SHD 19 for GNN.Seven predicted edges agree with the consensus network, while three true-positive edges are not found by the other methods.
6 Discussion
The discussion presents the framework as a broad continuous approach to sparse DAG learning. It emphasizes generality, simultaneous graph updates, and strong empirical performance despite nonconvex optimization.
- Generality: The framework subsumes many parametric, semiparametric, and nonparametric models as special cases.Its nonparametric acyclicity characterization leverages partial derivatives.
- Optimization: With a suitable approximation family, estimation becomes a finite-dimensional differentiable program solvable by standard optimization algorithms.The continuous algorithm updates all edges simultaneously using global information about the network state.
A Proofs
The proofs establish equivalence between two neural-network function classes: functions constrained to omit an input and functions with a corresponding first-layer column removed.
- Assumption: Bias terms are omitted because they do not affect the proposition's statement.
- Proposition 1: The proof of Proposition 1 proceeds by showing both inclusions, F0 ⊆ F and F ⊆ F0.This establishes equality between the two function classes.
- F0 ⊆ F: For F0 ⊆ F, zero entries in the relevant first-layer column make the linear map, and therefore the MLP, independent of uk.The proof uses the first-layer parameterization to preserve independence from the omitted input.
- F ⊆ F0: For F ⊆ F0, the proof constructs a modified first-layer matrix by setting the weights associated with the omitted input to zero.The resulting network remains in the restricted function class.
B Experiment details
The experiment details define the simulated SEMs, baseline methods, and evaluation setup. Baselines span linear, generalized-score, neural-network, continuous-optimization, and additive-model approaches.
- Baselines: The baselines include FGS, GSGES, DAG-GNN, linear NOTEARS, and CAM, covering specialized linear and general nonlinear dependencies.CAM uses additive SEMs, nonparametric regression, and greedy edge search.
- Experimental settings: CAM uses preliminary neighborhood selection and pruning in all experiments, while other methods use default parameter settings.
- Simulation: The simulations generate Xj = fj(Xpa(j)) + zj in topological order, with four specified instances for fj.The listed settings include additive GP, index, MLP-based ANM, and GP-based ANM constructions.
- Data-generating functions: The simulated MLP uses one hidden layer with 100 sigmoid units, while the GP uses an RBF kernel with length-scale one.All settings use independent standard Gaussian noise.
C Additional results
The additional results compare structure-recovery metrics across graph and SEM settings, benchmark NOTEARS variants against CAM, and report runtime and hyperparameter sensitivity. NOTEARS-MLP generally achieves strong recovery, while runtime scales linearly with sample size and fixed tuning can be suboptimal.
- Full comparison: NOTEARS-MLP has low FDR/FPR and high TPR across the reported graph and SEM settings.NOTEARS-Sob shows the same pattern on additive GP settings, while GNN has low FDR and low TPR because it predicts few edges.
- Complexity: With m/d = O(1), NOTEARS-MLP objective and gradient evaluation has complexity comparable to the linear case apart from nonlinear-function costs.The stated complexity is O(nd^2m+d^2m+d^3), versus O(nd^2+d^3) for the linear case.
- Runtime: O(n) sample-size dependence distinguishes NOTEARS-MLP and NOTEARS-Sob from the kernel-based GSGES approach, which has O(n^3) computational complexity.Runtime comparisons on ER2 with n = 1000 samples show GSGES has significantly longer runtime.
- Hyperparameter tuning: Fixed λ and weight-threshold values were used across configurations even though different settings may prefer different regularization strengths.The authors report substantially improved performance in some settings after changing hyperparameters.