DAG-GNN: DAG Structure Learning with Graph Neural Networks

By Yue Yu, Tian Gao, Mo Yu. 2019

689 citations recorded by the source corpus.

Learning a faithful directed acyclic graph (DAG) from samples of a joint distribution is a challenging combinatorial problem, owing to the intractable search space superexponential in the number of graph nodes. A recent breakthrough formulates the problem as a continuous optimization with a structural constraint that ensures acyclicity (Zheng et al., 2018). The authors apply the approach to the linear structural equation model (SEM) and the least-squares loss function that are statistically well justified but nevertheless limited. Motivated by the widespread success of deep learning that is capable of capturing complex nonlinear mappings, in this work we propose a deep generative model and apply a variant of the structural constraint to learn the DAG. At the heart of the generative model is a variational autoencoder parameterized by a novel graph neural network architecture, which we coin DAG-GNN. In addition to the richer capacity, an advantage of the proposed model is that it naturally handles discrete variables as well as vector-valued ones. We demonstrate that on synthetic data sets, the proposed method learns more accurate graphs for nonlinearly generated samples; and on benchmark data sets with discrete variables, the learned graphs are reasonably close to the global optima. The code is available at \url{this https URL}.

Subfields: 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 Graph Learning

Citations in the corpus

Differentiable Causal Discovery from Interventional Data (2020, methodology): “In terms of scoring, most methods rely on maximum likelihood or variants like implicit maximum likelihood [21] and evidence lower bound [49].”
Gradient-Based Neural DAG Learning (2019, methodology): “On both synthetic and real-world tasks, we show GraN-DAG outperforms other approaches which leverage the continuous paradigm, including DAG-GNN [16], a recent nonlinear extension of [18] independently developed which uses an evidence lower bound as score.”
Learning Neural Causal Models from Unknown Interventions (2019, methodology): “[15] 10 19 7 14 16 12 77 Heinze-Deml et al.”
Causal Discovery with Reinforcement Learning (2019, neutral): “, 2018), DAG-GNN (Yu et al., 2019), and GraNDAG (Lachapelle et al.”
Causal Induction from Visual Observations for Goal Directed Tasks (2019, neutral): “In addition, adversarial learning (Kalainathan et al., 2018), graph neural networks (Yu et al., 2019), and gradient-based DAG learning (Lachapelle et al., 2019) have been recently introduced to causal discovery, but largely focusing on small synthetic datasets.”
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).”
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).”
BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery (2021, methodology): “Originally the penalty h(W ) = Tr e W was used, and subsequently different penalties have been proposed [61].”
Variational Causal Networks: Approximate Bayesian Inference over Causal Structures (2021, methodology): “Both these approaches strongly rely on the identiﬁability of SCM. Zheng et al. [38], Yu et al. [37], Lachapelle et al. [24] use a score-based objective with global search over DAG space to learn the structure.”
Masked Gradient-Based Causal Structure Learning (2019, methodology): “…[31], PC-KCI (with kernel-based conditional independence tests) [40], GES [5], GES-GS (with generalized score) [10], CAM [3], NOTEARS [43], DAG-GNN [37], SAM [12], NOTEARS-MLP [44], and For synthetic data, experiments are conducted on data models varying along graph size, degree, and causal…”
Deep Learning for Time Series Anomaly Detection: A Survey (2022, neutral): “We presume that the anomalous subsequences are less likely to be reconstructed compared to normal subsequences in the test phase since anomalies are rare.”
CausalVAE: Disentangled Representation Learning via Neural Structural Causal Models (2020, methodology): “The function attains 0 if and only if the adjacency matrix A corresponds to a DAG [32], i.e.”
D-VAE: A Variational Autoencoder for Directed Acyclic Graphs (2019, background): “BNSL is still an active research area [41, 43, 49, 50, 51].”
Parameter Prediction for Unseen Deep Architectures (2021, background): “[120, 121, 46], can be one way to create the training dataset F .”
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.”
Learning Sparse Nonparametric DAGs (2019, methodology): “• DAG-GNN (GNN) (Yu et al., 2019) learns a (noisy) nonlinear transformation of a linear SEM using neural networks.”
DiBS: Differentiable Bayesian Structure Learning (2021, methodology): “[24], who show that a graph with adjacency matrix G ∈ {0, 1}d×d does not have any cycles if and only if h(G) = 0, where h(G) := tr [ (I + 1 dG) d ] − d .”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, methodology): “They provide an overview of the gradual evolution from NO TEARS (which assumes linear SEMs), via DAG-GNN [272], GAE [178] and GraNDAG [139] (which handle non-linear SEMs), but highlight that these methods do not provide an in depth discussion about identifiability.”