Research map / Graph learning / Graph self-supervised learning
Discrete-state Continuous-time Diffusion for Graph Generation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DisCo, the first discrete-state continuous-time graph diffusion model, trained with a cross-entropy objective motivated by a rate-matrix approximation bound and sampled via tau-leaping, with GT and MPNN backbones.
Problem
Graph diffusion models for generation of categorical graphs are either continuous-state (losing topological sparsity) or discrete-time (DiGress), so the number of sampling steps is fixed to training steps and cannot be traded off for quality/efficiency.
Approach
Formulate one-shot graph diffusion as a discrete-state CTMC with factorized node/edge forward processes, derive a cross-entropy upper bound on reverse-rate approximation error to justify an unweighted CE training loss, and sample with tau-leaping so the step count is decoupled from training; also a lightweight MPNN backbone that is permutation-equivariant.
Key results
- On SBM, DisCo-GT reaches Deg. 0.8 and Validity 66.2%, close to DiGress's 67.5% validity and better on Deg. (1.6).
- On QM9, DisCo-GT achieves 99.3% validity and DisCo-MPNN 68.7% novelty versus DiGress 99.0% validity and 31.8% novelty.
- On MOSES, DisCo-GT gets FCD 1.44 versus DiGress 1.19, so DisCo-GT is on par but not better than DiGress; DisCo-MPNN is weaker on GuacaMol (FCD 36.4 vs 68.0).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DisCo-GT instead of DiGress | Graph generation · QM9 | Valid (%): 99.0 -> 99.3 ± 0.6 | No clear effect |
| use DisCo-MPNN instead of DisCo-GT | DisCo · SBM | Validity (%): 66.2 ± 1.4 -> 41.9 ± 2.2 | Hurt |
| use DisCo-GT instead of DisCo-MPNN | DisCo · MOSES | Validity: 83.9 -> 88.3 | Helped |
| reduce sampling steps from 500 to 30 (ablation) | DisCo-GT with marginal reference · QM9 | Valid (%): 99.3 ± 0.6 -> 97.9 ± 1.2 | Hurt |
| reduce sampling steps from 500 to 1 (ablation) | DisCo-GT with marginal reference · QM9 | Valid (%): 99.3 ± 0.6 -> 76.1 ± 2.3 | Hurt |
| reduce sampling steps from 500 to 30 (ablation) | DisCo-GT with marginal reference · QM9 | Valid unique novel (%): 56.2 ± 0.4 -> 59.2 ± 0.8 | Helped |
| use uniform instead of marginal reference distribution (ablation) | DisCo-GT with 500 sampling steps · QM9 | Valid (%): 99.3 ± 0.6 -> 94.1 ± 0.9 | Hurt |
| use uniform instead of marginal reference distribution (ablation) | DisCo-GT with 500 sampling steps · QM9 | Valid unique novel (%): 56.2 ± 0.4 -> 56.6 ± 0.4 | No clear effect |
| replace the Graph Transformer backbone with an MPNN | DisCo · QM9 | Valid unique novel (%): 56.2 ± 0.4 -> 68.7 ± 0.2 | Helped |
Surprising findings
- The MPNN backbone, with no self-attention, matches or beats the graph transformer on Deg./Clus./Orb. and novelty on several datasets.
- Validity on SBM/Planar is very hard to learn: DiGress and DisCo-GT sometimes need more than 10,000 epochs to exceed 50% validity.
Limitations
- MPNN backbone has lower validity than the GT backbone on several datasets (e.g., Planar 33.8% vs 83.6%).
- Performance is on par with rather than clearly above DiGress on most benchmarks.
- Permutation analysis and sampling-error connection are theoretical; empirical gains are modest.
Experimental setup
Datasets: SBM Planar Community QM9 MOSES GuacaMol
Benchmarks: SBM Planar QM9 MOSES GuacaMol Community
Metrics: Deg. MMD Clus. MMD Orb. MMD Uniqueness Novelty Validity FCD SNN Scaf Filters
Baselines: GraphRNN GRAN GG-GAN MolGAN SPECTRE ConGress DiGress GDSS EDGE GRAPHARM
Builds on: DiGress D3PM Campbell et al. continuous-time discrete diffusion tau-leaping PNA
Closest papers by meaning
- Graph Generation with Diffusion Mixture (ICML 2024 · similarity 0.91)
- SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion (ICML 2025 · similarity 0.90)
- Smooth Interpolation for Improved Discrete Graph Generative Models (ICML 2025 · similarity 0.90)
- Advancing Graph Generation through Beta Diffusion (ICLR 2025 · similarity 0.90)
- Generative Modelling of Structurally Constrained Graphs (NeurIPS 2024 · similarity 0.90)
- Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generation (ICML 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.