DAGs with NO TEARS: Continuous Optimization for Structure Learning

By Xun Zheng, Bryon Aragam, Pradeep Ravikumar, Eric P. Xing. 2018

1,439 citations recorded by the source corpus.

Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint. In this paper, we introduce a fundamentally different strategy: we formulate the structure learning problem as a purely continuous optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting problem can be efficiently solved by standard numerical algorithms, which also makes implementation effortless. The proposed method outperforms existing ones, without imposing any structural assumptions on the graph such as bounded treewidth or in-degree.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Model Architectures, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Model Architectures

In Graph Learning

Citations in the corpus

Bayesian Structure Learning with Generative Flow Networks (2022, methodology): “We follow the experimental setup of Zheng et al. (2018) & Lorch et al. (2021), and sample synthetic data from linear-Gaussian Bayesian networks with randomly generated structures; details about this data generation process are given in Appendix D.2.”
Differentiable Causal Discovery from Interventional Data (2020, methodology): “[52] in the context of linear models: Tr eθ − d = 0 .”
An Analysis of the Adaptation Speed of Causal Models (2020, methodology): “, 2000) or score-based methods using greedy search (Chickering, 2002) or more recently continuous optimization (Zheng et al., 2018; Lachapelle et al., 2020).”
Gradient-Based Neural DAG Learning (2019, methodology): “In the original method named NOTEARS [18], the directed graph is encoded as a weighted adjacency matrix W which represents coefficients in a linear structural equation model (SEM) [7].”
Learning Neural Causal Models from Unknown Interventions (2019, methodology): “…comparisons: Cross entropy (lower is better) for edge probability on learned and ground-truth edges on Asia graph. compared to to Peters et al. (2016), (Eaton & Murphy, 2007a) and (Zheng et al., 2018) Our method (Eaton & Murphy, 2007a) (Peters et al., 2016) (Zheng et al., 2018) 0.0 0.0 10.7”
A Meta-Transfer Objective for Learning to Disentangle Causal Mechanisms (2019, background): “This constraint can be enforced as an extra penalty to the meta-transfer objective (Zheng et al., 2018).”
Causal Discovery with Reinforcement Learning (2019, methodology): “Here we use the result from [34] which introduced a smooth characterization for the acyclicity constraint.”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, methodology): “We now proceed, in a reverse thought ﬂow, to establish the connection between the loss function of the linear SEM considered in Zheng et al. (2018) and that of ours.”
Differentiable Causal Discovery Under Latent Interventions (2022, methodology): “…constraint of Zheng et al. (2018), enables formulating causal discovery under latent interventions as the following optimization problem: Following Zheng et al. (2018), we use the augmented Lagrangian (AL) method (Hestenes, 1969; Powell, 1969; Glowinski and Marroco, 1975) to address this problem…”
Variational Causal Networks: Approximate Bayesian Inference over Causal Structures (2021, methodology): “For the DAG bootstrap method, we ran Lingam [33] and NOTEARS [38] by resampling (with replacement) 50 points at random for 1000 different times for n = 100 and 252 times with 5 points for n = 10 .”
Knowledge Augmented Deep Neural Networks for Joint Facial Expression and Action Unit Recognition (2020, background): “The structure is acyclic if and only if tr ( e A ( w ) ◦ A ( w ) ) − N = 0 ([57]).”
Discrete Graph Structure Learning for Forecasting Multiple Time Series (2021, methodology): “Gradient-based approaches in this context include NOTEARS (Zheng et al., 2018), DAG-GNN (Yu et al., 2019), and GraN-DAG (Lachapelle et al., 2020).”
Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings (2020, background): “Other related works include structure inference in probabilistic graphical models [9, 62, 59], and graph generation [36, 47], which have a different goal from ours.”
BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery (2021, methodology): “This includes recent approaches which relax the DAG constraint to a larger, continuous set of adjacency matrices, such as Rd×d in [62] or the Birkhoff polytope of doubly-stochastic matrices in [5], which enables the use of gradient-based optimization.”
Causal Reasoning and Large Language Models: Opening a New Frontier for Causality (2023, background): “…is low (12), we are able to conduct an experiment to discover the full graph using LLMs. Huang et al. (2021) evaluate the accuracy of three recent discovery algorithms: temporal causality discovery framework (Nauta et al., 2019), NOTEARS (Zheng et al., 2018), and DAG-GNN (Yu et al., 2019).”
DiBS: Differentiable Bayesian Structure Learning (2021, methodology): “In this special case, DiBS with SVGD recovers some of the existing continuous structure learning methods: gradient ascent on a linear Gaussian likelihood solves an optimization problem similar to NOTEARS [9].”
CausalVAE: Disentangled Representation Learning via Neural Structural Causal Models (2020, methodology): “[34] proposed NOTEARs with a fully differentiable DAG constraint for causal structure learning, which drastically reduces a very complicated combinatorial optimization problem to a continuous optimization problem.”