Autoregressive Diffusion Model for Graph Generation
Lingkai Kong Jiaming Cui Haotian Sun Yuchen Zhuang B. Aditya Prakash Chao Zhang
Diffusion-based graph generative models have recently obtained promising
results for graph generation. However, existing diffusion-based graph
generative models are mostly one-shot generative models that apply Gaussian
diffusion in the dequantized adjacency matrix space. Such a strategy can suffer
from difficulty in model training, slow sampling speed, and incapability of
incorporating constraints. We propose an \emph{autoregressive diffusion} model
for graph generation. Unlike existing methods, we define a node-absorbing
diffusion process that operates directly in the discrete graph space. For
forward diffusion, we design a \emph{diffusion ordering network}, which learns
a data-dependent node absorbing ordering from graph topology. For reverse
generation, we design a \emph{denoising network} that uses the reverse node
ordering to efficiently reconstruct the graph by predicting the node type of
the new node and its edges with previously denoised nodes at a time. Based on
the permutation invariance of graph, we show that the two networks can be
jointly trained by optimizing a simple lower bound of data likelihood. Our
experiments on six diverse generic graph datasets and two molecule datasets
show that our model achieves better or comparable generation performance with
previous state-of-the-art, and meanwhile enjoys fast generation speed.