Sparse GNNs Make Strong Backbones for Discrete Graph Generation

Leading discrete graph generators use Graph Transformers or dense message-passing networks as their denoising backbone, processing all $N^2$ node pairs at every layer despite typically sparse output graphs. We present SGen (Sparse-backbone Graph Generation), which restricts intermediate message passing to the current non-null edges and predicts the full adjacency matrix only at the output through a bilinear head. We interpret SGen through conditional link prediction: a Bayes analysis decomposes edge denoising into structural prediction and current-edge information, and further bounds the error when SGen approximates this target. Integrated into DiGress and SimGFM, SGen achieves competitive generation quality on molecular and structural benchmarks, with metric-dependent trade-offs. On Tree and Planar, it delivers approximately $2.8$–$3.9\times$ training speedups and $86\%$–$92\%$ lower peak training memory than the corresponding Graph Transformer backbones. Architecture-matched ablations show that sparse communication itself reduces runtime and memory, with the operator and model size held fixed. Reusing shared representations across terminal output blocks further enables SGen to extend an existing graph generation method to Proteins and Point Clouds with up to 5,037 nodes, without any algorithm specifically designed for large graphs.