DAGs with NO TEARS: Continuous Optimization for Structure Learning

Abstract

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 \emph{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. Code implementing the proposed algorithm is open-source and publicly available at https://github.com/xunzheng/notears.

22 pages, 8 figures, accepted to NIPS 2018

Cited by in corpus (74)

• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings
• Causal Discovery with Reinforcement Learning
• Causal Inference-Based Root Cause Analysis for Online Service Systems with Intervention Recognition
• D-VAE: A Variational Autoencoder for Directed Acyclic Graphs
• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
• Causal Modeling of Twitter Activity During COVID-19
• Causal Discovery in Physical Systems from Videos
• Learning Neural Causal Models from Unknown Interventions
• Optimizing regularized Cholesky score for order-based learning of Bayesian networks
• gCastle: A Python Toolbox for Causal Discovery
• CASTLE: Regularization via Auxiliary Causal Graph Discovery
• Towards Efficient Local Causal Structure Learning
• Learning Sparse Nonparametric DAGs
• Discrete Graph Structure Learning for Forecasting Multiple Time Series
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Differentiable Causal Discovery Under Unmeasured Confounding
• Estimation of Structural Causal Model via Sparsely Mixing Independent Component Analysis
• Towards Human-like Perception: Learning Structural Causal Model in Heterogeneous Graph
• Learning Neural Causal Models with Active Interventions
• Nonlinear Causal Discovery with Confounders
• Gradient-Based Neural DAG Learning
• BeFair: Addressing Fairness in the Banking Sector
• Computably Continuous Reinforcement-Learning Objectives are PAC-learnable
• A Local Method for Identifying Causal Relations under Markov Equivalence
• Learning big Gaussian Bayesian networks: partition, estimation, and fusion
• Graphical Normalizing Flows
• Causal Inference in the Presence of Interference in Sponsored Search Advertising
• Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game
• Variational Causal Networks: Approximate Bayesian Inference over Causal Structures
• Towards Federated Bayesian Network Structure Learning with Continuous Optimization
• Data Generating Process to Evaluate Causal Discovery Techniques for Time Series Data
• Causal Adversarial Network for Learning Conditional and Interventional Distributions
• FSPN: A New Class of Probabilistic Graphical Model
• Unsuitability of NOTEARS for Causal Graph Discovery
• Simultaneously Reconciled Quantile Forecasting of Hierarchically Related Time Series
• On the Convergence of Continuous Constrained Optimization for Structure Learning
• Systematic Evaluation of Causal Discovery in Visual Model Based Reinforcement Learning
• Learning DAGs without imposing acyclicity
• Discovery and inference of a causal network with hidden confounding
• Learning linear non-Gaussian directed acyclic graph with diverging number of nodes
• Sparse Cholesky covariance parametrization for recovering latent structure in ordered data
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• Multi-task Learning of Order-Consistent Causal Graphs
• Fine-Grained System Identification of Nonlinear Neural Circuits
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Supervised Whole DAG Causal Discovery
• Causal Discovery with Multi-Domain LiNGAM for Latent Factors
• Efficient Neural Causal Discovery without Acyclicity Constraints
• Causal Autoregressive Flows
• Structure Mapping for Transferability of Causal Models
• NOTMAD: Estimating Bayesian Networks with Sample-Specific Structures and Parameters
• Efficient Bayesian network structure learning via local Markov boundary search
• Typing assumptions improve identification in causal discovery
• On Constraint Definability in Tractable Probabilistic Models
• Deconfounded Score Method: Scoring DAGs with Dense Unobserved Confounding
• Testing Mediation Effects Using Logic of Boolean Matrices
• Using Unsupervised Learning to Help Discover the Causal Graph
• Differentiable TAN Structure Learning for Bayesian Network Classifiers
• Autoregressive flow-based causal discovery and inference
• ACRE: Abstract Causal REasoning Beyond Covariation
• Relate and Predict: Structure-Aware Prediction with Jointly Optimized Neural DAG
• Temporal Point Process Graphical Models
• Causality and Generalizability: Identifiability and Learning Methods
• Learning Bayesian Networks through Birkhoff Polytope: A Relaxation Method
• Prequential MDL for Causal Structure Learning with Neural Networks
• Identifiability of AMP chain graph models
• Causal policy ranking
• GAETS: A Graph Autoencoder Time Series Approach Towards Battery Parameter Estimation
• Causal Discovery from Conditionally Stationary Time Series
• On the Role of Entropy-based Loss for Learning Causal Structures with Continuous Optimization
• Testing Directed Acyclic Graph via Structural, Supervised and Generative Adversarial Learning
• Physical System for Non Time Sequence Data
• Differentiable Causal Backdoor Discovery
• Learning Gaussian DAGs from Network Data