Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling
Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling
复制标题
DOI：
10.48550/arxiv.2305.04111
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Xiaohui Chen;Jiaxing He;Xuhong Han;Liping Liu
中科院分区：
文献类型：
--
作者：
Xiaohui Chen;Jiaxing He;Xuhong Han;Liping Liu
基于扩散的生成图模型已被证明可以有效生成高质量的小图。然而，它们需要更具可扩展性才能生成包含数千个需要图形统计的节点的大型图形。在这项工作中，我们提出了 EDGE，这是一种新的基于扩散的生成图模型，可解决大型图的生成任务。为了提高计算效率，我们通过使用离散扩散过程来鼓励图稀疏性，该过程在每个时间步随机删除边缘，最终获得一个空图。 EDGE 在每个去噪步骤中仅关注图中的部分节点。与之前基于扩散的模型相比，它进行的边缘预测要少得多。此外，EDGE 承认对图的节点度进行显式建模，进一步提高了模型性能。实证研究表明，EDGE 比竞争方法更有效，并且可以生成具有数千个节点的大型图。它在生成质量方面也优于基线模型：我们的方法生成的图具有与训练图更相似的图统计数据。
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.