DiPhon: Diffusion on Graphons for Scalable Graph Generation

Diffusion models are a leading paradigm for graph generation, with notable impact in domains such as molecular design. Yet, scaling these models to large graphs remains an open problem. We approach this question in the dense-graph setting through the lens of graphons, the size-agnostic limit object of dense graph sequences, to study how structural graph statistics behave across node-size scales. This perspective leads to DiPhon, a diffusion process for size-scalable graph generation. Specifically, we formulate a continuous diffusion process on the graphon space via a Jacobi stochastic differential equation (SDE), and propose DiPhon, a discretized scheme that imitates it on graphs. We further derive the corresponding reverse-time process, which requires access to the marginal score. For the Jacobi process, this score interestingly admits a tractable form, which we estimate from data via graph denoising and plug into the reverse process to generate graph samples. We prove that DiPhon matches the first moment of the marginal distributions induced by the continuous graphon process exactly, and approximates the second moment up to a closed-form discrepancy. In this way, DiPhon inherits the size-agnostic statistical properties of the graphon dynamics can be used to solve the scaling bottleneck. Empirically, we demonstrate the scalability of DiPhon by training on small graphs and generating substantially larger ones at inference time, without retraining on large graphs.