Sparse Training of Discrete Diffusion Models for Graph Generation

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. 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. Random graph models have been foundational in graph generation, with a rich legacy spanning several decades (Erdős et al., 1960; Aiello et al., 2000; Barabási, 2013). However, recent interest has gravitated towards learned graph models, primarily due to their enhanced ability to represent intricate data distributions. Traditional frameworks like generative adversarial networks (De Cao & Kipf, 2018) and variational autoencoders (Simonovsky & Komodakis, 2018) predominantly addressed graphs with a maximum of 9 nodes. This limitation was somewhat alleviated with the advent of denoising diffusion models (Niu et al., 2020; Jo et al., 2022; Vignac et al., 2023a), elevating capacity to roughly 100 nodes. However, these models are still not scaled for broader applications like transportation (Rong et al., 2023) or financial system anomaly detection (Li et al., 2023).