2019

DAG-GNN: DAG Structure Learning with Graph Neural Networks

Yu, Yue, Chen, Jie, Gao, Tian et al.

Understand

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.

Built on

Approximating discrete probability distributions with dependence trees
Chow, C. and Liu, C · 1968
Earlier work this paper cites.
Probabilistic reasoning in intelligent systems: networks of plausible inference
Pearl, J · 1988
Earlier work this paper cites.
Learning Bayesian networks: The combination of knowledge and statistical data
Heckerman, D., Geiger, D., and Chickering, D. M · 1995
Earlier work this paper cites.
Bayesian graphical models for discrete data
Madigan, D., York, J., and Allard, D · 1995
Earlier work this paper cites.
Causal inference in the presence of latent variables and selection bias
Spirtes, P., Meek, C., and Richardson, T · 1995
Earlier work this paper cites.
Nonlinear Programming
Bertsekas, D. P · 1999
Earlier work this paper cites.
Data analysis with Bayesian networks: A bootstrap approach
Friedman, N., Goldszmidt, M., and Wyner, A · 1999
Earlier work this paper cites.
Computation, Causation, and Discovery
Spirtes, P., Glymour, C. N., and Scheines, R · 1999
Earlier work this paper cites.
Optimal structure identification with greedy search
Chickering, D. M · 2002
Earlier work this paper cites.
Being Bayesian about network structure. a Bayesian approach to structure discovery in Bayesian networks
Friedman, N. and Koller, D · 2003
Earlier work this paper cites.
Causality: models, reasoning, and inference
Pearl, J · 2003
Earlier work this paper cites.
Time and sample efficient discovery of markov blankets and direct causal relations
Tsamardinos, I., Aliferis, C. F., and Statnikov, A · 2003
Earlier work this paper cites.
Large-sample learning of Bayesian networks is NP-hard
Chickering, D. M., Heckerman, D., and Meek, C · 2004
Earlier work this paper cites.
Exact Bayesian structure discovery in Bayesian networks
Koivisto, M. and Sood, K · 2004
Earlier work this paper cites.
Finding optimal models for small gene networks
Ott, S., Imoto, S., and Miyano, S · 2004
Earlier work this paper cites.
Causal protein-signaling networks derived from multiparameter single-cell data
Sachs, K., Perez, O., Peer, D., Lauffenburger, D. A., and Nolan, G. P · 2005
Earlier work this paper cites.
Finding optimal Bayesian networks by dynamic programming
Singh, A. P. and Moore, A. W · 2005
Earlier work this paper cites.

Similar

A simple approach for finding the globally optimal Bayesian network structure
Silander, T. and Myllymaki, P · 2006
Cited alongside, same era.
The max-min hill-climbing Bayesian network structure learning algorithm
Tsamardinos, I., Brown, L., and Aliferis, C · 2006
Cited alongside, same era.
Improving the structure MCMC sampler for Bayesian networks by introducing a new edge reversal move
Grzegorczyk, M. and Husmeier, D · 2008
Cited alongside, same era.
On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias
Zhang, J · 2008
Cited alongside, same era.
Learning Bayesian network structure using LP relaxations
Jaakkola, T., Sontag, D., Globerson, A., and Meila, M · 2010
Cited alongside, same era.
Bayesian network learning with cutting planes
Cussens, J · 2011
Cited alongside, same era.
Learning Bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhood
Gámez, J., Mateo, J., and Puerta, J · 2011
Cited alongside, same era.
Bayesian structure learning using dynamic programming and MCMC
Original
Eaton, D. and Murphy, K · 2012
Cited alongside, same era.
Structured learning of Gaussian graphical models
Mohan, K., Chung, M., Han, S., Witten, D., Lee, S.-I., and Fazel, M · 2012
Cited alongside, same era.
Partial order MCMC for structure discovery in Bayesian networks
Original
Niinimaki, T., Parviainen, P., and Koivisto, M · 2012
Cited alongside, same era.
Annealed importance sampling for structure learning in Bayesian networks
Niinimäki, T. M. and Koivisto, M · 2013
Cited alongside, same era.
Learning optimal Bayesian networks: A shortest path perspective
Yuan, C. and Malone, B · 2013
Cited alongside, same era.

Then

Learning Bayesian networks with thousands of variables
Scanagatta, M., de Campos, C. P., Corani, G., and Zaffalon, M · 2015
Later among the works it cites.
Representing text for joint embedding of text and knowledge bases
Toutanova, K., Chen, D., Pantel, P., Poon, H., Choudhury, P., and Gamon, M · 2015
Later among the works it cites.
Learning Bayesian networks with ancestral constraints
Chen, E. Y.-J., Shen, Y., Choi, A., and Darwiche, A · 2016
Later among the works it cites.
Polyhedral aspects of score equivalence in Bayesian network structure learning
Cussens, J., Haws, D., and Studenỳ, M · 2016
Later among the works it cites.
Convolutional neural networks on graphs with fast localized spectral filtering
Defferrard, M., Bresson, X., and Vandergheynst, P · 2016
Later among the works it cites.
Structure learning in Bayesian networks of a moderate size by efficient sampling
He, R., Tian, J., and Wu, H · 2016
Later among the works it cites.
Gated graph sequence neural networks
Li, Y., Tarlow, D., Brockschmidt, M., and Zemel, R · 2016
Later among the works it cites.
Joint causal inference from multiple contexts
Original
Mooij, J. M., Magliacane, S., and Claassen, T · 2016
Later among the works it cites.
Neural message passing for quantum chemistry
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E · 2017
Later among the works it cites.
Inductive representation learning on large graphs
Hamilton, W. L., Ying, R., and Leskovec, J · 2017
Later among the works it cites.
Semi-supervised classification with graph convolutional networks
Kipf, T. N. and Welling, M · 2017
Later among the works it cites.
Automatic differentiation in PyTorch
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A · 2017
Later among the works it cites.
A million variables and more: the fast greedy equivalence search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images
Ramsey, J., Glymour, M., Sanchez-Romero, R., and Glymour, C · 2017
Later among the works it cites.
FastGCN: Fast learning with graph convolutional networks via importance sampling
Chen, J., Ma, T., and Xiao, C · 2018
Later among the works it cites.
SAM: Structural agnostic model, causal discovery and penalized adversarial learning
Original
Kalainathan, D., Goudet, O., Guyon, I., Lopez-Paz, D., and Sebag, M · 2018
Later among the works it cites.
Graph attention networks
Velic̆ković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y · 2018
Later among the works it cites.
DAGs with NO TEARS: Continuous optimization for structure learning
Zheng, X., Aragam, B., Ravikumar, P., and Xing, E. P · 2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…