2020

A Systematic Survey on Deep Generative Models for Graph Generation

Guo, Xiaojie, Zhao, Liang

Understand

Graphs are important data representations for describing objects and their relationships, which appear in a wide diversity of real-world scenarios.

As one of a critical problem in this area, graph generation considers learning the distributions of given graphs and generating more novel graphs.
Owing to their wide range of applications, generative models for graphs, which have a rich history, however, are traditionally hand-crafted and only capable of modeling a few statistical properties of graphs.
Recent advances in deep generative models for graph generation is an important step towards improving the fidelity of generated graphs and paves the way for new kinds of applications.

Built on

S. Kullback and R. A. Leibler, “On information and sufficiency,” The annals of mathematical statistics , vol. 22, no. 1, pp. 79–86, 1951
1951
Earlier work this paper cites.
M. J. Kusner, B. Paige, and J. M. Hernández-Lobato, “Grammar variational autoencoder,” in ICML’2017 , 2017, pp. 1945–1954
1954
Earlier work this paper cites.
J. Giráldez-Cru and J. Levy, “A modularity-based random sat instances generator,” in IJCAI’2015 , 2015, pp. 1952–1958
1958
Earlier work this paper cites.
P. Erdös, A. Rényi et al. , “On random graphs,” Publicationes mathematicae , vol. 6, no. 26, pp. 290–297, 1959
1959
Earlier work this paper cites.
L. C. Freeman, “Centrality in social networks conceptual clarification,” Social networks , vol. 1, no. 3, pp. 215–239, 1978
1978
Earlier work this paper cites.
P. Bonacich, “Power and centrality: A family of measures,” American journal of sociology , vol. 92, no. 5, pp. 1170–1182, 1987
1987
Earlier work this paper cites.
B. W. SUTER, “The multilayer perceptron as an approximation to a bayes optimal discriminant function,” IEEE Transactions on Neural Networks , vol. 1, no. 4, p. 291, 1990
1990
Earlier work this paper cites.
C. J. Watkins and P. Dayan, “Q-learning,” Machine learning , vol. 8, no. 3-4, pp. 279–292, 1992
1992
Earlier work this paper cites.
D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” nature , vol. 393, no. 6684, p. 440, 1998
1998
Earlier work this paper cites.
M. Rarey and J. S. Dixon, “Feature trees: a new molecular similarity measure based on tree matching,” Journal of computer-aided molecular design , vol. 12, no. 5, pp. 471–490, 1998
1998
Earlier work this paper cites.
R. S. Sutton, A. G. Barto et al. , Introduction to reinforcement learning . MIT press Cambridge, 1998, vol. 135
1998
Earlier work this paper cites.
R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Reviews of modern physics , vol. 74, no. 1, p. 47, 2002
2002
Earlier work this paper cites.
X. Yan and J. Han, “gspan: Graph-based substructure pattern mining,” in ICDM’2002 , 2002, pp. 721–724
2002
Earlier work this paper cites.
P. D. Dobson and A. J. Doig, “Distinguishing enzyme structures from non-enzymes without alignments,” Journal of molecular biology , vol. 330, no. 4, pp. 771–783, 2003
2003
Earlier work this paper cites.
I. Schomburg, A. Chang, C. Ebeling, and et al, “Brenda, the enzyme database: updates and major new developments,” Nucleic acids research , vol. 32, no. suppl_1, pp. D431–D433, 2004
Original
2004
Earlier work this paper cites.
C. M. Bishop, Pattern recognition and machine learning . springer, 2006
2006
Earlier work this paper cites.
G. Robins, T. Snijders, and P. Wang et al, “Recent developments in exponential random graph (p*) models for social networks,” Social networks , vol. 29, no. 2, pp. 192–215, 2007
2007
Earlier work this paper cites.
D. Silver, R. S. Sutton, and M. Müller, “Reinforcement learning of local shape in the game of go.” in IJCAI’2007 , vol. 7, 2007, pp. 1053–1058
2007
Earlier work this paper cites.
F. Scarselli, M. Gori, and A. C. Tsoi et al, “The graph neural network model,” IEEE Transactions on Neural Networks , vol. 20, no. 1, pp. 61–80, 2008
2008
Earlier work this paper cites.
J. Degen, C. Wegscheid-Gerlach, and A. Zaliani et al, “On the art of compiling and using’drug-like’chemical fragment spaces,” ChemMedChem: Chemistry Enabling Drug Discovery , vol. 3, no. 10, pp. 1503–1507, 2008
2008
Earlier work this paper cites.
P. Sen, G. Namata, and M. e. a. Bilgic, “Collective classification in network data,” AI magazine , vol. 29, no. 3, pp. 93–93, 2008
2008
Earlier work this paper cites.
S. Ranu and A. K. Singh, “Graphsig: A scalable approach to mining significant subgraphs in large graph databases,” in ICDE’2009 , 2009, pp. 844–855
2009
Earlier work this paper cites.
J. Leskovec, D. Chakrabarti, and J. Kleinberg et al, “Kronecker graphs: An approach to modeling networks,” Journal of Machine Learning Research , vol. 11, no. Feb, pp. 985–1042, 2010
2010
Earlier work this paper cites.
T. Mikolov, M. Karafiát, and et al, “Recurrent neural network based language model,” in INTERSPEECH , 2010, pp. 1045–148
2010
Earlier work this paper cites.
I. Sutskever, J. Martens, and G. E. Hinton, “Generating text with recurrent neural networks,” in ICML’2011 , 2011, pp. 1017–1024
2011
Earlier work this paper cites.
N. Shervashidze, P. Schweitzer, and E. J. Van Leeuwen et al, “Weisfeiler-lehman graph kernels,” Journal of Machine Learning Research , vol. 12, no. 77, pp. 2539–2561, 2011
2011
Earlier work this paper cites.
J. Hachmann, R. Olivares-Amaya, and et al, “The harvard clean energy project: large-scale computational screening and design of organic photovoltaics on the world community grid,” The Journal of Physical Chemistry Letters , vol. 2, no. 17, pp. 2241–2251, 2011
2011
Earlier work this paper cites.
A. Gretton, K. M. Borgwardt, and M. J. Rasch et al, “A kernel two-sample test,” Journal of Machine Learning Research , vol. 13, no. Mar, pp. 723–773, 2012
2012
Earlier work this paper cites.
U. Kang, H. Tong, and J. Sun, “Fast random walk graph kernel,” in SDM’2012 , 2012, pp. 828–838
2012
Earlier work this paper cites.
J. J. Irwin, T. Sterling, M. M. Mysinger, and et al, “Zinc: a free tool to discover chemistry for biology,” Journal of chemical information and modeling , vol. 52, no. 7, pp. 1757–1768, 2012
2012
Earlier work this paper cites.
D. P. Kingma and M. Welling, “Auto-encoding variational bayes,” 2014
2014
Earlier work this paper cites.
I. Goodfellow, J. Pouget-Abadie, and M. Mirza et al, “Generative adversarial nets,” in NeurIPS’2014 , 2014, pp. 2672–2680
2014
Earlier work this paper cites.
M. Mirza and S. Osindero, “Conditional generative adversarial nets,” NeurIPS’2014 Workshop , 2014
2014
Earlier work this paper cites.
C. Maddison and D. Tarlow, “Structured generative models of natural source code,” in ICML’2014 , 2014, pp. 649–657
2014
Earlier work this paper cites.
Z. Newsham, V. Ganesh, and et al, “Impact of community structure on sat solver performance,” in SAT’2014 , 2014, pp. 252–268
2014
Earlier work this paper cites.
R. Ramakrishnan, P. O. Dral, M. Rupp, and O. A. Von Lilienfeld, “Quantum chemistry structures and properties of 134 kilo molecules,” Scientific data , vol. 1, no. 1, pp. 1–7, 2014
2014
Earlier work this paper cites.
J. Liu, Y. Chi, and C. Zhu, “A dynamic multiagent genetic algorithm for gene regulatory network reconstruction based on fuzzy cognitive maps,” IEEE Transactions on Fuzzy Systems , vol. 24, no. 2, pp. 419–431, 2015
2015
Earlier work this paper cites.
K. Sohn, H. Lee, and X. Yan, “Learning structured output representation using deep conditional generative models,” in NeurIPS’2015 , 2015, pp. 3483–3491
2015
Earlier work this paper cites.
D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” 2015
2015
Earlier work this paper cites.
G. Jurman, R. Visintainer, and M. Filosi et al, “The him glocal metric and kernel for network comparison and classification,” in DSAA’2015 , 2015, pp. 1–10
2015
Earlier work this paper cites.
A. T. Nguyen and T. N. Nguyen, “Graph-based statistical language model for code,” in ICSE’2015 , vol. 1, 2015, pp. 858–868
2015
Earlier work this paper cites.
E. L. Denton, S. Chintala, and R. Fergus et al, “Deep generative image models using a laplacian pyramid of adversarial networks,” in NeurIPS’2015 , 2015, pp. 1486–1494
2015
Earlier work this paper cites.
V. Mnih, K. Kavukcuoglu, and D. Silver et al, “Human-level control through deep reinforcement learning,” Nature , vol. 518, no. 7540, pp. 529–533, 2015
2015
Earlier work this paper cites.
A.-L. Barabási et al. , Network science . Cambridge university press, 2016
2016
Earlier work this paper cites.
T. N. Kipf and M. Welling, “Variational graph auto-encoders,” NeurIPS’2016 Workshop , 2016
2016
Earlier work this paper cites.
V. Golkov, M. J. Skwark, and et al, “Protein contact prediction from amino acid co-evolution using convolutional networks for graph-valued images,” in NeurIPS’2016 , 2016, pp. 4222–4230
2016
Earlier work this paper cites.
L. Livi, E. Maiorino, and A. Giuliani et al, “A generative model for protein contact networks,” Journal of Biomolecular Structure and Dynamics , vol. 34, no. 7, pp. 1441–1454, 2016
2016
Earlier work this paper cites.
L. Dong and M. Lapata, “Language to logical form with neural attention,” in ACL’2016 , vol. 1, 2016, pp. 33–43
2016
Earlier work this paper cites.
R. Jia and P. Liang, “Data recombination for neural semantic parsing,” in ACL’2016 , vol. 1, 2016, pp. 12–22
2016
Earlier work this paper cites.
A. Radford, L. Metz, and S. Chintala, “Unsupervised representation learning with deep convolutional generative adversarial networks,” 2016
2016
Earlier work this paper cites.

Similar

J. Li, W. Monroe, and A. Ritter et al, “Deep reinforcement learning for dialogue generation,” in EMNLP’2016 , 2016, pp. 1192–1202
2016
Cited alongside, same era.
G. Papamakarios, T. Pavlakou, and I. Murray, “Masked autoregressive flow for density estimation,” in NeurIPS’17 , 2017, pp. 2338–2347
2017
Cited alongside, same era.
M. Guarino, A. Shah, and P. Rivas, “Dipol-gan: generating molecular graphs adversarially with relational differentiable pooling,” 2017
2017
Cited alongside, same era.
J. Gilmer, S. S. Schoenholz, and P. F. Riley et al, “Neural message passing for quantum chemistry,” in ICML’2017 , 2017, pp. 1263–1272
2017
Cited alongside, same era.
E. Jang, S. Gu, and B. Poole, “Categorical reparametrization with gumble-softmax,” in ICLR’2017 , 2017
2017
Cited alongside, same era.
C. J. Maddison, A. Mnih, and Y. W. Teh, “The concrete distribution: A continuous relaxation of discrete random variables,” in ICLR’2017 , 2017
2017
Cited alongside, same era.
T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” 2017
2017
Cited alongside, same era.
J. Kawahara, C. J. Brown, and S. P. Miller et al, “Brainnetcnn: Convolutional neural networks for brain networks; towards predicting neurodevelopment,” NeuroImage , vol. 146, pp. 1038–1049, 2017
2017
Cited alongside, same era.
B. M. Lake, T. D. Ullman, and J. B. Tenenbaum et al, “Building machines that learn and think like people,” Behavioral and brain sciences , vol. 40, p. e253, 2017
2017
Cited alongside, same era.
L. Chen, S. Srivastava, and Z. Duan et al, “Deep cross-modal audio-visual generation,” in Proceedings of the on Thematic Workshops of ACM Multimedia , 2017, pp. 349–357
2017
Cited alongside, same era.
L. Dinh, J. Sohl-Dickstein, and S. Bengio, “Density estimation using real nvp,” in ICLR’2017 , 2017
2017
Cited alongside, same era.
H. Wang, J. Wang, and J. Wang et al, “Graphgan: Graph representation learning with generative adversarial nets,” in AAAI’2018 , 2018, pp. 2508–2515
2018
Cited alongside, same era.

Then

J. Lim, S.-Y. Hwang, and K. et al, “Scaffold-based molecular design using graph generative model,” in The 2019 Asia-Pacific Association of Theoretical and Computational Chemists , 2019
2019
Later among the works it cites.
S. Kearnes, L. Li, and P. Riley, “Decoding molecular graph embeddings with reinforcement learning,” ICML’2019 Workshop , 2019
2019
Later among the works it cites.
R. Liao, Y. Li, and Y. Song et al, “Efficient graph generation with graph recurrent attention networks,” in NeurIPS’2019 , 2019, pp. 4257–4267
2019
Later among the works it cites.
X. Gu, “Explore deep graph generation,” 2019
2019
Later among the works it cites.
S. Pölsterl and C. Wachinger, “Likelihood-free inference and generation of molecular graphs,” arXiv preprint arXiv:1905.10310 , 2019
Original
2019
Later among the works it cites.
X. Bresson and T. Laurent, “A two-step graph convolutional decoder for molecule generation,” NeurIPS’2019 Workshop , 2019
2019
Later among the works it cites.
S. Honda, H. Akita, and K. Ishiguro et al, “Graph residual flow for molecular graph generation,” arXiv preprint arXiv:1909.13521 , 2019
Original
2019
Later among the works it cites.
K. Madhawa, K. Ishiguro, and K. Nakago et al, “Graphnvp: An invertible flow model for generating molecular graphs,” arXiv preprint arXiv:1905.11600 , 2019
Original
2019
Later among the works it cites.
L. Zhang, “Stggan: Spatial-temporal graph generation,” in SIGSPATIAL’19 , 2019, pp. 608–609
2019
Later among the works it cites.
V. Caridá, A. Jalilifard, and A. Mansano et al, “Can netgan be improved on short random walks?” in The 8th Brazilian Conference on Intelligent Systems (BRACIS’2019) , 2019, pp. 663–668
2019
Later among the works it cites.
D. Zou and G. Lerman, “Encoding robust representation for graph generation,” in IJCNN’2019 , 2019, pp. 1–9
2019
Later among the works it cites.
J. Liu, A. Kumar, and J. Ba et al, “Graph normalizing flows,” in NeurIPS’2019 , 2019, pp. 13 556–13 566
2019
Later among the works it cites.
G. Salha, S. Limnios, and R. Hennequin et al, “Gravity-inspired graph autoencoders for directed link prediction,” in CIKM’2019 , 2019, pp. 589–598
2019
Later among the works it cites.
K. Do, T. Tran, and S. Venkatesh, “Graph transformation policy network for chemical reaction prediction,” in KDD’2019 , 2019, pp. 750–760
2019
Later among the works it cites.
D. Zhou, L. Zheng, and J. Xu et al, “Misc-gan: A multi-scale generative model for graphs,” Frontiers in Big Data , vol. 2, p. 3, 2019
2019
Later among the works it cites.
Z. Zhou, S. Kearnes, and L. Li et al, “Optimization of molecules via deep reinforcement learning,” Scientific reports , vol. 9, no. 1, pp. 1–10, 2019
2019
Later among the works it cites.
C. Yang, P. Zhuang, and W. Shi et al, “Conditional structure generation through graph variational generative adversarial nets,” in NeurIPS’2019 , 2019, pp. 1338–1349
2019
Later among the works it cites.
E. Jonas, “Deep imitation learning for molecular inverse problems,” in NeurIPS’2019 , 2019, pp. 4991–5001
2019
Later among the works it cites.
S. Amizadeh, S. Matusevych, and M. Weimer, “Learning to solve circuit-sat: An unsupervised differentiable approach,” 2019
2019
Later among the works it cites.
X. Guo, L. Zhao, and C. Nowzari et al, “Deep multi-attributed graph translation with node-edge co-evolution,” in ICDM’2019 , 2019, pp. 250–259
2019
Later among the works it cites.
K. Xu, W. Hu, and J. Leskovec et al, “How powerful are graph neural networks?” 2019
2019
Later among the works it cites.
B. Samanta, D. Abir, and et al, “Nevae: A deep generative model for molecular graphs,” in AAAI’2019 , vol. 33, 2019, pp. 1110–1117
2019
Later among the works it cites.
F. Fancellu, S. Gilroy, and A. Lopez et al, “Semantic graph parsing with recurrent neural network dag grammars,” in EMNLP-IJCNLP’2019 , 2019, pp. 2769–2778
2019
Later among the works it cites.
J. You, H. Wu, and C. Barrett et al, “G2sat: Learning to generate sat formulas,” in NeurIPS’2019 , 2019, pp. 10 552–10 563
2019
Later among the works it cites.
H. Wu and R. Ramanujan, “Learning to generate industrial sat instances,” in SoCS’2019 , 2019, pp. 206–207
2019
Later among the works it cites.
E. Noutahi, D. Beani, and J. Horwood et al, “Towards interpretable sparse graph representation learning with laplacian pooling,” arXiv preprint arXiv:1905.11577 , 2019
Original
2019
Later among the works it cites.
N. Stoehr, M. Brockschmidt, and J. Stuehmer et al, “Disentangling interpretable generative parameters of random and real-world graphs,” NeurIPS’2019 Workshop , 2019
2019
Later among the works it cites.
T. Karras, S. Laine, and T. Aila, “A style-based generator architecture for generative adversarial networks,” in CVPR’2019 , 2019, pp. 4401–4410
2019
Later among the works it cites.
X. Guo, S. Tadepalli, and L. Zhao et al, “Generating tertiary protein structures via an interpretative variational autoencoder,” arXiv preprint arXiv:2004.07119 , 2020
Original
2020
Closest in time.
A. Bonifati, I. Holubová, A. Prat-Pérez, and S. Sakr, “Graph generators: State of the art and open challenges,” ACM Computing Surveys (CSUR) , vol. 53, no. 2, pp. 1–30, 2020
2020
Closest in time.
Z. Wu, S. Pan, and F. Chen et al, “A comprehensive survey on graph neural networks,” IEEE Transactions on Neural Networks and Learning Systems , pp. 1–21, 2020
2020
Closest in time.
Z. Zhang, P. Cui, and W. Zhu, “Deep learning on graphs: A survey,” IEEE Transactions on Knowledge and Data Engineering , 2020
2020
Closest in time.
N. Goyal, H. V. Jain, and S. Ranu, “Graphgen: a scalable approach to domain-agnostic labeled graph generation,” in WWW’20 , 2020, pp. 1253–1263
2020
Closest in time.
D. Bacciu, A. Micheli, and M. Podda, “Edge-based sequential graph generation with recurrent neural networks,” Neurocomputing , 2020
2020
Closest in time.
M. Podda, D. Bacciu, and A. Micheli, “A deep generative model for fragment-based molecule generation,” 2020
2020
Closest in time.
D. Flam-Shepherd, T. Wu, and A. Aspuru-Guzik, “Graph deconvolutional generation,” arXiv preprint arXiv:2002.07087 , 2020
Original
2020
Closest in time.
C. Niu, Y. Song, and J. Song et al, “Permutation invariant graph generation via score-based generative modeling,” 2020
2020
Closest in time.
A. Gamage, E. Chien, and J. Peng et al, “Multi-motifgan (mmgan): Motif-targeted graph generation and prediction,” in ICASSP’2020 , 2020, pp. 4182–4186
2020
Closest in time.
C. Shi, M. Xu, and Z. Zhu et al, “Graphaf: a flow-based autoregressive model for molecular graph generation,” 2020
2020
Closest in time.
Ł. Maziarka, A. Pocha, and J. Kaczmarczyk et al, “Mol-cyclegan: a generative model for molecular optimization,” Journal of Cheminformatics , vol. 12, no. 1, pp. 1–18, 2020
2020
Closest in time.
W. Jin, R. Barzilay, and T. Jaakkola, “Composing molecules with multiple property constraints,” arXiv preprint arXiv:2002.03244 , 2020
Original
2020
Closest in time.
S. Yang, J. Liu, and K. Wu et al, “Learn to generate time series conditioned graphs with generative adversarial nets,” arXiv preprint arXiv:2003.01436 , 2020
Original
2020
Closest in time.
X. Guo, L. Zhao, and Z. Qin et al, “Interpretable deep graph generation with node-edge co-disentanglement,” 2020
2020
Closest in time.
F. Faez, Y. Ommi, M. S. Baghshah, and H. R. Rabiee, “Deep graph generators: A survey,” IEEE Access , 2021
2021
Closest in time.
X. Guo, Y. Du, and L. Zhao, “Deep generative models for spatial networks,” in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining , 2021, pp. 505–515
2021
Closest in time.
Y. Du, X. Guo, A. Shehu, and L. Zhao, “Interpretable molecular graph generation via monotonic constraints,” in Proceedings of the 2022 SIAM International Conference on Data Mining (SDM) . SIAM, 2022, pp. 73–81
2022
Closest in time.
X. Guo, L. Wu, and L. Zhao, “Deep graph translation,” IEEE Transactions on Neural Networks and Learning Systems , 2022
2022
Closest in time.
Y. Zhu, Y. Du, Y. Wang, Y. Xu, J. Zhang, Q. Liu, and S. Wu, “A survey on deep graph generation: Methods and applications,” arXiv preprint arXiv:2203.06714 , 2022
Original
2022
Closest in time.
Y. Du, X. Guo, and et al, “Disentangled spatiotemporal graph generative models,” arXiv preprint arXiv:2203.00411 , 2022
Original
2022
Closest in time.
D. Bouchacourt, R. Tomioka, and S. Nowozin, “Multi-level variational autoencoder: Learning disentangled representations from grouped observations,” in AAAI’2018 , 2018, pp. 2095–2102
2095
Closest in time.

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…