Diffusion Models for Graphs Benefit From Discrete State Spaces
This work addresses graph generation for domains like chemistry or social networks, offering a more efficient and effective method, though it is incremental as it builds on existing diffusion models.
The paper tackles the problem of generating discrete graphs using diffusion models by proposing a discrete noise process instead of continuous Gaussian perturbations, resulting in higher quality samples with an average MMD reduced by a factor of 1.5 and a 30 times faster sampling procedure by reducing steps from 1000 to 32.
Denoising diffusion probabilistic models and score-matching models have proven to be very powerful for generative tasks. While these approaches have also been applied to the generation of discrete graphs, they have, so far, relied on continuous Gaussian perturbations. Instead, in this work, we suggest using discrete noise for the forward Markov process. This ensures that in every intermediate step the graph remains discrete. Compared to the previous approach, our experimental results on four datasets and multiple architectures show that using a discrete noising process results in higher quality generated samples indicated with an average MMDs reduced by a factor of 1.5. Furthermore, the number of denoising steps is reduced from 1000 to 32 steps, leading to a 30 times faster sampling procedure.