Research map / Graph learning / Graph self-supervised learning
DeFoG: Discrete Flow Matching 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 DeFoG, a discrete flow matching framework for graph generation that decouples training from sampling and adds sampling-time design choices (time distortion, target guidance, stochasticity) to reach SOTA validity on planar, tree, SBM, and molecular benchmarks with far fewer steps.
Problem
Graph diffusion models tightly couple training and sampling, so sampling choices (noise schedule, rate matrices, step counts) require retraining, and they need many sampling steps for good quality.
Approach
Use a discrete flow matching formulation tailored to graphs with a linear noising process and CTMC denoising, where the training loss only learns marginal clean-data predictions and the rate matrix is chosen at sampling time; add time distortion, target guidance, and detailed-balance stochasticity as training-free sampling knobs.
Key results
- Achieves 99.5% V.U.N. on Planar and 90.0% on SBM, and 96.5% on Tree, with a 5% step variant reaching 95.0% on Planar.
- Reaches 92.8% validity on MOSES, surpassing the prior SOTA of 90.5% (Cometh), and 99.0% validity on Guacamol.
- On Guacamol, DeFoG with 10% of sampling steps exceeds 90% validity, surpassing DiGress with 500 steps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DeFoG instead of the strongest baseline | Graph generation · Planar | V.U.N.: 99.5 vs 99.5 | No clear effect |
| Use DeFoG instead of the strongest baseline | Graph generation · Tree | V.U.N.: 100.0 -> 96.5 | Hurt |
| Use DeFoG instead of the strongest baseline | Graph generation · SBM | V.U.N.: 85.0 -> 90.0 | Helped |
| Use DeFoG instead of the strongest baseline | Molecular graph generation · MOSES | Val.: 90.5 -> 92.8 | Helped |
| Use DeFoG instead of the strongest baseline | Molecular graph generation · Guacamol | Val.: 98.9 -> 99.0 | Helped |
| Reduce sampling steps to 5% | DeFoG · Planar | V.U.N.: 99.5 -> 95.0 | Hurt |
| Reduce sampling steps to 5% | DeFoG · SBM | V.U.N.: 90.0 -> 86.5 | Hurt |
| Reduce sampling steps to 10% | DeFoG · MOSES | Val.: 92.8 -> 83.9 | Hurt |
| Emphasize later sampling steps with cos or polydec distortion (ablation) | DeFoG sampling on Planar · Planar | V.U.N. | Helped |
| Apply later-step refinement distortion (ablation) | DeFoG sampling on SBM · SBM | V.U.N. | No clear effect |
| Add moderate target guidance (ablation) | DeFoG sampling on Planar · Planar | V.U.N. | Helped |
| Increase target guidance excessively (ablation) | DeFoG sampling on Planar · Planar | Ratio | Hurt |
Surprising findings
- The vanilla DeFoG configuration alone does not outperform existing diffusion-based graph models; gains come mainly from the sampling optimization pipeline.
- Target guidance improves validity but increases distance to test graphs (Ratio) when omega is too large, and time distortions help on Planar but not on SBM.
Limitations
- Vanilla DeFoG does not beat diffusion baselines without sampling tuning, and sampling hyperparameters are chosen via a simple search pipeline.
- Scaling to larger graphs and reducing steps further are stated as open challenges.
- Mixed continuous-discrete graph data is not explored.
Experimental setup
Datasets: Planar Tree SBM QM9 ZINC250k MOSES Guacamol
Benchmarks: Planar Tree SBM Guacamol MOSES QM9 ZINC250k
Metrics: V.U.N. Ratio validity uniqueness novelty FCD KL divergence SNN Scaffold similarity Filters
Baselines: GraphRNN GRAN SPECTRE DiGress EDGE BwR (EDP-GNN) BiGG GraphGen HSpectre GruM CatFlow DisCo
Builds on: discrete flow matching DiGress relative random walk probabilities continuous-time discrete diffusion
Closest papers by meaning
- Variational Flow Matching for Graph Generation (NeurIPS 2024 · similarity 0.89)
- Smooth Interpolation for Improved Discrete Graph Generative Models (ICML 2025 · similarity 0.89)
- Simple and Critical Iterative Denoising: A Recasting of Discrete Diffusion in Graph Generation (ICML 2025 · similarity 0.89)
- Discrete-state Continuous-time Diffusion for Graph Generation (NeurIPS 2024 · similarity 0.89)
- Flow Matching with General Discrete Paths: A Kinetic-Optimal Perspective (ICLR 2025 · similarity 0.88)
- Graph Generation with Diffusion Mixture (ICML 2024 · similarity 0.88)
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.