  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.
