Sparse Training of Discrete Diffusion Models for Graph Generation
Yiming Qin Clement Vignac Pascal Frossard
Generative models for graphs often encounter scalability challenges due to
the inherent need to predict interactions for every node pair. Despite the
sparsity often exhibited by real-world graphs, the unpredictable sparsity
patterns of their adjacency matrices, stemming from their unordered nature,
leads to quadratic computational complexity. In this work, we introduce
SparseDiff, a denoising diffusion model for graph generation that is able to
exploit sparsity during its training phase. At the core of SparseDiff is a
message-passing neural network tailored to predict only a subset of edges
during each forward pass. When combined with a sparsity-preserving noise model,
this model can efficiently work with edge lists representations of graphs,
paving the way for scalability to much larger structures. During the sampling
phase, SparseDiff iteratively populates the adjacency matrix from its prior
state, ensuring prediction of the full graph while controlling memory
utilization. Experimental results show that SparseDiff simultaneously matches
state-of-the-art in generation performance on both small and large graphs,
highlighting the versatility of our method.