Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling

Xiaohui Chen, Jiaxing He, Xu Han, Liping Liu
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:4585-4610, 2023.

Abstract

Diffusion-based generative graph models have been proven effective in generating high-quality small graphs. However, they need to be more scalable for generating large graphs containing thousands of nodes desiring graph statistics. In this work, we propose EDGE, a new diffusion-based generative graph model that addresses generative tasks with large graphs. To improve computation efficiency, we encourage graph sparsity by using a discrete diffusion process that randomly removes edges at each time step and finally obtains an empty graph. EDGE only focuses on a portion of nodes in the graph at each denoising step. It makes much fewer edge predictions than previous diffusion-based models. Moreover, EDGE admits explicitly modeling the node degrees of the graphs, further improving the model performance. The empirical study shows that EDGE is much more efficient than competing methods and can generate large graphs with thousands of nodes. It also outperforms baseline models in generation quality: graphs generated by our approach have more similar graph statistics to those of the training graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-chen23k, title = {Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling}, author = {Chen, Xiaohui and He, Jiaxing and Han, Xu and Liu, Liping}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {4585--4610}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/chen23k/chen23k.pdf}, url = {https://proceedings.mlr.press/v202/chen23k.html}, abstract = {Diffusion-based generative graph models have been proven effective in generating high-quality small graphs. However, they need to be more scalable for generating large graphs containing thousands of nodes desiring graph statistics. In this work, we propose EDGE, a new diffusion-based generative graph model that addresses generative tasks with large graphs. To improve computation efficiency, we encourage graph sparsity by using a discrete diffusion process that randomly removes edges at each time step and finally obtains an empty graph. EDGE only focuses on a portion of nodes in the graph at each denoising step. It makes much fewer edge predictions than previous diffusion-based models. Moreover, EDGE admits explicitly modeling the node degrees of the graphs, further improving the model performance. The empirical study shows that EDGE is much more efficient than competing methods and can generate large graphs with thousands of nodes. It also outperforms baseline models in generation quality: graphs generated by our approach have more similar graph statistics to those of the training graphs.} }
Endnote
%0 Conference Paper %T Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling %A Xiaohui Chen %A Jiaxing He %A Xu Han %A Liping Liu %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-chen23k %I PMLR %P 4585--4610 %U https://proceedings.mlr.press/v202/chen23k.html %V 202 %X Diffusion-based generative graph models have been proven effective in generating high-quality small graphs. However, they need to be more scalable for generating large graphs containing thousands of nodes desiring graph statistics. In this work, we propose EDGE, a new diffusion-based generative graph model that addresses generative tasks with large graphs. To improve computation efficiency, we encourage graph sparsity by using a discrete diffusion process that randomly removes edges at each time step and finally obtains an empty graph. EDGE only focuses on a portion of nodes in the graph at each denoising step. It makes much fewer edge predictions than previous diffusion-based models. Moreover, EDGE admits explicitly modeling the node degrees of the graphs, further improving the model performance. The empirical study shows that EDGE is much more efficient than competing methods and can generate large graphs with thousands of nodes. It also outperforms baseline models in generation quality: graphs generated by our approach have more similar graph statistics to those of the training graphs.
APA
Chen, X., He, J., Han, X. & Liu, L.. (2023). Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:4585-4610 Available from https://proceedings.mlr.press/v202/chen23k.html.

Related Material