2022

GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation

Huang, Han, Sun, Leilei, Du, Bowen et al.

Understand

Graph generative models have broad applications in biology, chemistry and social science.

However, modelling and understanding the generative process of graphs is challenging due to the discrete and high-dimensional nature of graphs, as well as permutation invariance to node orderings in underlying graph distributions.
Current leading autoregressive models fail to capture the permutation invariance nature of graphs for the reliance on generation ordering and have high time complexity.
Here, we propose a continuous-time generative diffusion process for permutation invariant graph generation to mitigate these issues.

Built on

P. Erdős, A. Rényi et al. , “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci , vol. 5, no. 1, pp. 17–60, 1960
1960
Earlier work this paper cites.
B. Weisfeiler and A. Leman, “The reduction of a graph to canonical form and the algebra which appears therein,” NTI, Series , vol. 2, no. 9, pp. 12–16, 1968
1968
Earlier work this paper cites.
G. Parisi, “Correlation functions and computer simulations,” Nuclear Physics B , vol. 180, no. 3, pp. 378–384, 1981
1981
Earlier work this paper cites.
B. D. Anderson, “Reverse-time diffusion equation models,” Stochastic Processes and their Applications , vol. 12, no. 3, pp. 313–326, 1982
1982
Earlier work this paper cites.
U. G. Haussmann and E. Pardoux, “Time reversal of diffusions,” The Annals of Probability , pp. 1188–1205, 1986
1986
Earlier work this paper cites.
D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” nature , vol. 393, no. 6684, pp. 440–442, 1998
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.
I. Schomburg, A. Chang, C. Ebeling, M. Gremse, C. Heldt, G. Huhn, and D. Schomburg, “Brenda, the enzyme database: updates and major new developments,” Nucleic acids research , vol. 32, no. suppl_1, pp. D431–D433, 2004
2004
Earlier work this paper cites.
P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, “Collective classification in network data,” AI magazine , vol. 29, no. 3, pp. 93–93, 2008
2008
Earlier work this paper cites.
J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani, “Kronecker graphs: an approach to modeling networks.” Journal of Machine Learning Research , vol. 11, no. 2, 2010
2010
Earlier work this paper cites.
P. Vincent, “A connection between score matching and denoising autoencoders,” Neural computation , vol. 23, no. 7, pp. 1661–1674, 2011
2011
Earlier work this paper cites.
A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola, “A kernel two-sample test,” The Journal of Machine Learning Research , vol. 13, no. 1, pp. 723–773, 2012
2012
Earlier work this paper cites.
S. R. De Groot and P. Mazur, Non-equilibrium thermodynamics . Courier Corporation, 2013
2013
Earlier work this paper cites.
B. Uria, I. Murray, and H. Larochelle, “A deep and tractable density estimator,” in ICML , 2014, pp. 467–475
2014
Earlier work this paper cites.
J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli, “Deep unsupervised learning using nonequilibrium thermodynamics,” in ICML , 2015, pp. 2256–2265
2015
Earlier work this paper cites.
D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in ICLR , Y. Bengio and Y. LeCun, Eds., 2015
2015
Earlier work this paper cites.
T. N. Kipf and M. Welling, “Variational graph auto-encoders,” arXiv preprint arXiv:1611.07308 , 2016
Original
2016
Earlier work this paper cites.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in NeurIPS , 2017
2017
Earlier work this paper cites.
M. Newman, Networks . Oxford university press, 2018
2018
Earlier work this paper cites.
Y. Li, O. Vinyals, C. Dyer, R. Pascanu, and P. Battaglia, “Learning deep generative models of graphs,” arXiv preprint arXiv:1803.03324 , 2018
Original
2018
Earlier work this paper cites.

Similar

B. Chen, L. Sun, and X. Han, “Sequence-to-action: End-to-end semantic graph generation for semantic parsing,” arXiv preprint arXiv:1809.00773 , 2018
Original
2018
Cited alongside, same era.
M. Simonovsky and N. Komodakis, “Graphvae: Towards generation of small graphs using variational autoencoders,” in ICANN . Springer, 2018, pp. 412–422
2018
Cited alongside, same era.
Q. Liu, M. Allamanis, M. Brockschmidt, and A. Gaunt, “Constrained graph variational autoencoders for molecule design,” in NeurIPS , 2018
2018
Cited alongside, same era.
A. Bojchevski, O. Shchur, D. Zügner, and S. Günnemann, “Netgan: Generating graphs via random walks,” in ICML , 2018, pp. 610–619
2018
Cited alongside, same era.
N. De Cao and T. Kipf, “Molgan: An implicit generative model for small molecular graphs,” arXiv preprint arXiv:1805.11973 , 2018
Original
2018
Cited alongside, same era.
J. You, R. Ying, X. Ren, W. Hamilton, and J. Leskovec, “Graphrnn: Generating realistic graphs with deep auto-regressive models,” in ICML , 2018, pp. 5708–5717
2018
Cited alongside, same era.
R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. Duvenaud, “Neural ordinary differential equations,” in NeurIPS , 2018
2018
Cited alongside, same era.
P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in ICLR , 2018
2018
Cited alongside, same era.
S. Xie, A. Kirillov, R. B. Girshick, and K. He, “Exploring randomly wired neural networks for image recognition,” in ICCV , 2019, pp. 1284–1293
2019
Cited alongside, same era.
J. Liu, A. Kumar, J. Ba, J. Kiros, and K. Swersky, “Graph normalizing flows,” in NeurIPS , 2019, pp. 13 556–13 566
2019
Cited alongside, same era.
R. Liao, Y. Li, Y. Song, S. Wang, W. L. Hamilton, D. Duvenaud, R. Urtasun, and R. S. Zemel, “Efficient graph generation with graph recurrent attention networks,” in NeurIPS , 2019, pp. 4257–4267
2019
Cited alongside, same era.
Y. Song and S. Ermon, “Generative modeling by estimating gradients of the data distribution,” in NeurIPS , vol. 32, 2019
2019
Cited alongside, same era.

Then

N. Goyal, H. V. Jain, and S. Ranu, “Graphgen: a scalable approach to domain-agnostic labeled graph generation,” in WWW , 2020, pp. 1253–1263
2020
Later among the works it cites.
H. Dai, A. Nazi, Y. Li, B. Dai, and D. Schuurmans, “Scalable deep generative modeling for sparse graphs,” in ICML , 2020, pp. 2302–2312
2020
Later among the works it cites.
C. Niu, Y. Song, J. Song, S. Zhao, A. Grover, and S. Ermon, “Permutation invariant graph generation via score-based generative modeling,” in AISTATS , 2020, pp. 4474–4484
2020
Later among the works it cites.
J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” in NeurIPS , 2020
2020
Later among the works it cites.
V. P. Dwivedi and X. Bresson, “A generalization of transformer networks to graphs,” arXiv preprint arXiv:2012.09699 , 2020
Original
2020
Later among the works it cites.
P. Li, Y. Wang, H. Wang, and J. Leskovec, “Distance encoding: Design provably more powerful neural networks for graph representation learning,” in NeurIPS , vol. 33, 2020, pp. 4465–4478
2020
Later among the works it cites.
Y. Luo, K. Yan, and S. Ji, “Graphdf: A discrete flow model for molecular graph generation,” in ICML , vol. 139, 2021, pp. 7192–7203
2021
Later among the works it cites.
X. Chen, X. Han, J. Hu, F. J. R. Ruiz, and L. Liu, “Order matters: Probabilistic modeling of node sequence for graph generation,” in ICML , 2021, pp. 1630–1639
2021
Later among the works it cites.
Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole, “Score-based generative modeling through stochastic differential equations,” in ICLR , 2021
2021
Later among the works it cites.
C. Morris, Y. Lipman, H. Maron, B. Rieck, N. M. Kriege, M. Grohe, M. Fey, and K. Borgwardt, “Weisfeiler and leman go machine learning: The story so far,” arXiv preprint arXiv:2112.09992 , 2021
Original
2021
Later among the works it cites.
D. Kreuzer, D. Beaini, W. Hamilton, V. Létourneau, and P. Tossou, “Rethinking graph transformers with spectral attention,” in NeurIPS , vol. 34, 2021
2021
Later among the works it cites.
V. P. Dwivedi, A. T. Luu, T. Laurent, Y. Bengio, and X. Bresson, “Graph neural networks with learnable structural and positional representations,” arXiv preprint arXiv:2110.07875 , 2021
Original
2021
Later among the works it cites.
M. M. Bronstein, J. Bruna, T. Cohen, and P. Velickovic, “Geometric deep learning: Grids, groups, graphs, geodesics, and gauges,” arXiv preprint arXiv:2104.13478 , 2021
Original
2021
Later among the works it cites.
J. Song, C. Meng, and S. Ermon, “Denoising diffusion implicit models,” in ICLR , 2021
2021
Later among the works it cites.
A. Q. Nichol and P. Dhariwal, “Improved denoising diffusion probabilistic models,” in ICML , 2021, pp. 8162–8171
2021
Later among the works it cites.
H. Cui, Z. Lu, P. Li, and C. Yang, “On positional and structural node features for graph neural networks on non-attributed graphs,” arXiv preprint arXiv:2107.01495 , 2021
Original
2021
Later among the works it cites.
L. O’Bray, M. Horn, B. Rieck, and K. Borgwardt, “Evaluation metrics for graph generative models: Problems, pitfalls, and practical solutions,” in ICLR , 2022
2022
Closest in time.
R. Thompson, B. Knyazev, E. Ghalebi, J. Kim, and G. W. Taylor, “On evaluation metrics for graph generative models,” in ICLR , 2022
2022
Closest in time.
J. Jo, S. Lee, and S. J. Hwang, “Score-based generative modeling of graphs via the system of stochastic differential equations,” in ICML , 2022, pp. 10 362–10 383
2022
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…