Abstract
Diffusion models represent a leading paradigm for graph generation, especially impactful in domains like molecular design. However, scaling these models to large graphs remains an open problem. We approach this question through graphons, the size-agnostic limit objects of dense graph sequences, to study how structural graph statistics behave across node-size scales.
DiPhon Framework
We introduce DiPhon, a diffusion framework for size-scalable graph generation. Specifically, we formulate a continuous diffusion process in the graphon space via a Jacobi stochastic differential equation (SDE) and propose DiPhon, a discretized graph-level process that mimics these dynamics on finite graphs.
Reverse Process Derivation
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.
Theoretical Proof
We prove that DiPhon matches exactly the first moment of the marginal distributions induced by the continuous graphon process and approximates the second moment up to a closed-form discrepancy. Thus, DiPhon inherits key size-agnostic statistical properties of the graphon dynamics, providing a principled route toward scalable graph generation.
Empirical Results
We empirically demonstrate this scalability by training on small graphs and generating progressively larger graphs at inference time, without retraining, while preserving their core topological properties.
Blogger's Review: The introduction of DiPhon offers a fresh perspective in the graph generation domain, especially in handling large-scale graphs. By leveraging graphons, this method not only ensures the statistical properties of generated graphs but also enhances the model's flexibility and practicality, signifying its importance in research and potential applications.