Research map / Image generation / Fast diffusion sampling
Discrete Diffusion Schrödinger Bridge Matching for Graph Transformation
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 DDSBM, which extends Iterative Markovian Fitting to discrete state spaces via CTMCs to solve Schrödinger bridge problems, and applies it to graph/molecular transformation with a GED-linked cost.
Problem
Schrödinger bridge and diffusion bridge models need a joint coupling between distributions, and existing SB methods focus on continuous spaces, leaving discrete domains such as graphs and molecules underexplored.
Approach
Extends Iterative Markovian Fitting to discrete state spaces using continuous-time Markov chains with independent node/edge reference dynamics, with a permutation matching step; the resulting entropic OT cost is interpreted as graph edit distance, enabling minimal-change molecular optimization.
Key results
- On ZINC250K, DDSBM reaches NLL 160.461 versus 288.572 for DBM and 344.458 for HierG2G, with FCD 0.833 versus 1.046 for DBM.
- On Polymer, DDSBM achieves validity 97.4% versus 43.4% for DBM and GAP W1 0.127 versus 0.249.
- DDSBM attains the lowest QED MAD (0.120) and SAscore MAD (0.402) on ZINC250K among compared models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · ZINC250K | NLL: 288.572 -> 160.461 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · ZINC250K | NSPDK: 8.04e-4 -> 7.30e-4 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · ZINC250K | FCD: 1.046 -> 0.833 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · ZINC250K | QED MAD: 0.141 -> 0.120 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · ZINC250K | SAscore MAD: 0.608 -> 0.402 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · Polymer | validity: 43.4 -> 97.4 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · Polymer | FCD: 2.230 -> 1.074 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · Polymer | NLL: 580.415 -> 212.047 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · Polymer | GAP W1: 0.249 -> 0.127 | Helped |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · Polymer | uniqueness: 99.8 -> 94.5 | Hurt |
| Use DDSBM with iterative Markovian fitting instead of DBM bridge matching | Molecular graph transformation · Polymer | novelty: 97.4 -> 71.3 | Hurt |
| Dynamically update training pairs through IMF rather than retain fixed initial pairs | DDSBM · ZINC250K | NLL | Helped |
Surprising findings
- The reference process based on uniform-prior diffusion makes the NLL-based permutation matching key; without a meaningful alpha-bar retention, the SB cost would be uniform across pairs.
Limitations
- IMF requires iterative sampling from the learned Markov process, increasing computational cost.
- Baselines and DDSBM rely on a predefined initial coupling; pseudo-optimal coupling needed for others.
- Graph matching via max-pooling plus Hungarian is approximate and GED computation is NP-hard.
Experimental setup
Datasets: ZINC250K Polymer
Benchmarks: ZINC250K Polymer
Metrics: validity uniqueness novelty NLL NSPDK LogP W1 QED MAD SAscore MAD FCD GAP W1
Baselines: AtomG2G HierG2G DBM
Builds on: Iterative Markovian Fitting Diffusion bridge models D3PM discrete diffusion Bridge matching
Closest papers by meaning
- Feedback Schrödinger Bridge Matching (ICLR 2025 · similarity 0.90)
- Light and Optimal Schrödinger Bridge Matching (ICML 2024 · similarity 0.90)
- Schrödinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres (NeurIPS 2025 · similarity 0.89)
- Categorical Schrödinger Bridge Matching (ICML 2025 · similarity 0.89)
- Graph Diffusion that can Insert and Delete (NeurIPS 2025 · similarity 0.88)
- Generalized Schrödinger Bridge Matching (ICLR 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.