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.

本文提出了一种名为 EDGE 的新型扩散生成图模型，通过在每个时间步骤随机删除边并最终获得空图的离散扩散过程，鼓励图结构的稀疏性，使其更有效率地生成包含上千节点的大型图，并明确将图中节点度数建模，与基线模型相比，生成的图像质量更高，具有更相似的图统计特征。