Discrete Diffusion Model Enables Large-Scale Graph Generation with Structural Candidate Restriction

Summary

Generating realistic large graphs is difficult because many diffusion-based methods have quadratic computational complexity and are generally limited to networks of up to about 3,000 nodes. The paper introduces a discrete graph diffusion model that trains only on observed edges and wedge non-edges, a structurally motivated subset of node pairs, reducing training complexity below quadratic in the number of nodes. It also proposes a three-class absorbing forward process with a degree-aware, floored cosine noise schedule. Unlike a structure-blind schedule that perturbs every pair identically, the schedule adapts noise to node degree and prevents the graph’s structure from being completely erased during the trajectory. The design is intended to keep the noisy graph informative for both forward and reverse diffusion. The authors target sparse graphs whose degree distributions, clustering, and path lengths resemble those of real-world graphs without memorizing training examples. Experiments on diverse datasets place the method consistently among the strongest approaches for structural fidelity relative to existing discrete diffusion baselines for large graph generation. The abstract does not report specific numerical scores or identify the datasets used.