Predicting the behavior of complex systems is critical in many scientific and engineering domains, and hinges on the model's ability to capture their underlying dynamics. Existing methods encode the intrinsic dynamics of high-dimensional observations through latent representations and predict autoregressively. However, these latent representations lose the inherent spatial structure of spatiotemporal dynamics, leading to the predictor's inability to effectively model spatial interactions and neglect emerging dynamics during long-term prediction. In this work, we propose SparseDiff, introducing a test-time adaptation strategy to dynamically update the encoding scheme to accommodate emergent spatiotemporal structures during the long-term evolution of the system.

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).