Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction

Yassin Mohamadi; Zeno Geradts; Marcel Worring

cs.AIOct 2, 2026

Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction

Authors: Yassin Mohamadi, Zeno Geradts, Marcel Worring

Abstract

Synthesizing realistic graphs at scale is vital when the graphs of interest are large and real-world samples are limited or access-sensitive. Diffusion-based generators have recently driven much of the progress, offering high modeling capacity, but most such methods have quadratic computational complexity and are hence restricted to small-scale networks, currently up to 3k nodes. Existing non-quadratic methods remain limited by memorization issues and a trade-off between scalability and generation quality. Our goal is to generate large graphs whose structural statistics --- e.g., degree distribution, clustering, and path length --- faithfully reflect those of real-world sparse graphs, without resorting to memorizing the training data. We introduce a discrete graph diffusion model that restricts training to a structurally motivated subset of node pairs --- observed edges and their wedge non-edges --- reducing training complexity below quadratic in the number of nodes. To keep the noisy graph informative throughout both the forward and reverse trajectories, we design a three-class absorbing forward process governed by a \emph{degree-aware, floored} cosine noise schedule: unlike a structure-blind schedule that adds noise to every pair identically, ours adapts to each node's degree and never fully erases the graph's structure, keeping the noisy graph informative at every step. Experiments across diverse datasets show that our model consistently ranks among the top methods for structural fidelity against existing discrete diffusion baselines in large graph generation.

Figures & tables

Figure 1: Overview of the proposed method. (a) Diffusion is confined to the structural candidate set. (b) Pairs in

Q_{t}

follow a partial absorbing process over {0, 1, M} with a degree-aware masking exponent

\beta^{ij}

. (c) The predictor passes messages only over visible edges

E_{t}

, then decodes each queried pair independently. (d) The three pair populations are recombined, giving an estimator that covers all

\binom{N}{2}

pairs at

O(N\mu_{2})

cost per step.

Figure 2

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Training (per step)	Sampling (per step)
DiGress	$O(N^{2})$	$O(N^{2})$
SparseDiff	$O(m)$ a	$O(N^{2})$ b
EDGE	$O(\max(m,K^{2}))$ c	$O(\max(m,K^{2}))$ c
Ours	$\bm{O(N\mu_{2})}$ d	$O(N^{2})$

Appendix

Table 4: Per-step complexity, diffusion-based graph generative models only. Assumes constant per-call network cost, so candidate-pair count and per-step training complexity coincide.

N

is number of nodes and

m

is number of edges. Bold denotes complexity improved by our method relative to the diffusion baselines.

Method	Paradigm	Generation Process	Overall Complexity	Per-step Complexity
GraphRNN	Flat AR	Row-by-row	$O(N^{2})$ a	$O(N)$
BiGG	Flat AR (tree)	Tree traversal	$O((N+m)\log N)$	$O(1)$
HiGen	Hierarchical AR	Cluster-wise	$O(n_{c}\log^{2}N)$ b	$O(N^{2})$ b
HGGT ( $K^{2}$ -trees)	Compressed AR	Sequence	$O(L_{\rm seq}^{2})$ c	$O(L_{\rm seq}^{2})$ c

Appendix

Table 5: Comparison of autoregressive (AR) graph generation methods. Complexity values are adopted from the original papers for consistency.

N

is number of nodes and

m

is number of edges. Note that “per-step” here denotes one autoregressive generation step (row/node/token), whose number scales with

N

m

, which is not directly comparable to the fixed-

T

diffusion timestep used as “per-step” in Table 4 .

Figure 3: Cora: degree-aware masking analysis

Figure 4: Citeseer: degree-aware masking analysis

Figure 5: Pubmed: degree-aware masking analysis

Figure 6: Alpha: degree-aware masking analysis

Figure 7: OTC: degree-aware masking analysis

Figure 8: Polblogs: degree-aware masking analysis

Panel of Figure 9 — Figure 9: Degree distribution comparison across six datasets; plot width indicates node density.

Panel of Figure 10 — Figure 10: Degree distribution comparison across six datasets; plot width indicates node density.

Figure 11: Sampling time across various graph sizes, averaged over 16 runs per model under identical conditions.

Figure 12: Structural statistics of generated graphs vs. inference-time diffusion steps.

Explore similar work

Jul 8, 2026stat.ML

DiPhon: Diffusion on Graphons for Scalable Graph Generation

Diffusion models represent 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 objects of dense graph sequences, to study how structural graph statistics behave across node-size scales. This perspective leads to DiPhon, a diffusion framework 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 graph-level process that mimics these dynamics on finite 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 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. Empirically, we demonstrate this scalability by training on small graphs and generating progressively larger graphs at inference time, without retraining, while preserving their core topological properties.

Sergio Rozada, Yiming Qin, Manuel Madeira +2

King Juan Carlos University · EPFL, Lausanne, Switzerland · University of Pennsylvania

Graph Generation Graph Diffusion

Ask PDF

Oct 9, 2026cs.LG

Your Discrete Graph Diffusion Model is Secretly Memorizing

Discrete graph diffusion models (GDMs) corrupt the graph structure by adding noise independently to nodes and edges under a Markovian noise model. In the unconditional setting without node features, an equivariant denoiser trained on a single graph is able to generate novel graphs and sample-level metrics such as edge overlap and WL kernel similarity find no evidence of memorization. In this work, we challenge this view and show for the first time that graph diffusion models indeed exhibit memorization. Analyzing the reverse diffusion trajectories of GDMs trained on two-block stochastic block models (SBMs), we find a strong train-data bias: the model recovers a corrupted training graph almost perfectly compared to a held-out test graph. We term this conditional memorization, as it surfaces only when the reverse trajectory is conditioned on a corrupted training graph and is not apparent during inference. It coincides with a growing generalization gap, where the training loss improves as the loss on held-out graphs degrades, and it cannot be mitigated by early stopping. The onset of memorization always precedes the emergence of community structure in the generated graphs, thus every checkpoint earlier produces structureless graphs. This behavior holds across all node sizes we test.

Adarsh Jamadandi, Nicolas Keriven

CNRS, IRISA, Rennes, France

Memorization in Generative Models Graph Diffusion

Ask PDF

Mar 9, 2026cs.LG

Local Message-Passing for Discrete Graph Generation

Discrete graph generation has emerged as a powerful paradigm for modeling graph-structured data, yet state of the art models often rely on Graph Transformers or higher order architectures. We revisit this design assumption by introducing GenGNN, a modular message passing backbone for graph generation. GenGNN enables powerful generation by persisting edge fields through latent refinement of coupled node edge graph states, all without requiring global attention. Diffusion models integrating GenGNN achieve over 90 percent validity on standard benchmark datasets, performing within margins of Graph Transformer backbones and achieving up to 2x or even 5x faster inference. Systematic ablations isolate how GenGNN is resilient to oversmoothing during generative denoising, indicating each GenGNN component is necessary for downstream generation quality. Finally, representation-space analysis suggests GenGNN learns functionally similar representations to more theoretically-expressive architectures; even at deeper layers. As such, GenGNN uplifts local message-passing to challenge prevailing assumptions that performant discrete graph generation requires global attention or higher-order representations. Source Code Available Here

Jay Revolinsky, Harry Shomer, Jiliang Tang

Michigan State University East Lansing, Michigan, USA · University of Texas - Arlington Arlington, Texas, USA

Graph Neural Networks Graph Generation Message Passing Neural Networks

Ask PDF