# Discrete Diffusion Schr"odinger Bridge Matching for Graph Transformation

arXiv: https://arxiv.org/abs/2410.01500 · HTML: https://mlsanity.com/paper/2410.01500/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Placed in Diffusion foundations and sampling, one of 14 directions in Diffusion models.
- Builds on 24 of its 58 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Placed in

- Diffusion models / [Diffusion foundations and sampling](https://mlsanity.com/diffusion/diffusion-foundations-and-sampling/)

## Builds on (most cited first, 24 of 24)

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [A survey of the Schr"odinger problem and some of its connections with optimal transport](https://mlsanity.com/paper/1308.0215/) (2013)
- [Diffsound: Discrete Diffusion Model for Text-to-sound Generation](https://mlsanity.com/paper/2207.09983/) (2022)
- [Hierarchical Generation of Molecular Graphs using Structural Motifs](https://mlsanity.com/paper/2002.03230/) (2020)
- [Fr'echet ChemNet Distance: A metric for generative models for molecules in drug discovery](https://mlsanity.com/paper/1803.09518/) (2018)
- [Denoising Diffusion Bridge Models](https://mlsanity.com/paper/2309.16948/) (2023)
- [Unpaired Image-to-Image Translation via Neural Schr"odinger Bridge](https://mlsanity.com/paper/2305.15086/) (2023)
- [Diffusion Bridge Mixture Transports, Schr"odinger Bridge Problems and Generative Modeling](https://mlsanity.com/paper/2304.00917/) (2023)
- [Non-Denoising Forward-Time Diffusions](https://mlsanity.com/paper/2312.14589/) (2023)
- [A Deep Generative Model for Molecule Optimization via One Fragment Modification](https://mlsanity.com/paper/2012.04231/) (2020)
- [RetroBridge: Modeling Retrosynthesis with Markov Bridges](https://mlsanity.com/paper/2308.16212/) (2023)
- [Message-passing neural networks for high-throughput polymer screening](https://mlsanity.com/paper/1807.10363/) (2018)
- [Diffusion-based Generative AI for Exploring Transition States from 2D Molecular Graphs](https://mlsanity.com/paper/2304.12233/) (2023)
- [CUNSB-RFIE: Context-aware Unpaired Neural Schr"odinger Bridge in Retinal Fundus Image Enhancement](https://mlsanity.com/paper/2409.10966/) (2024)
- [A Quadratic Assignment Formulation of the Graph Edit Distance](https://mlsanity.com/paper/1512.07494/) (2015)

## Built on by (most cited first, 21 of 21)

- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [ReDi: Rectified Discrete Flow](https://mlsanity.com/paper/2507.15897/) (2025)
- [Discrete Adjoint Matching](https://mlsanity.com/paper/2602.07132/) (2026)
- [Diffusion & Adversarial Schr"odinger Bridges via Iterative Proportional Markovian Fitting](https://mlsanity.com/paper/2410.02601/) (2024)
- [FragFM: Hierarchical Framework for Efficient Molecule Generation via Fragment-Level Discrete Flow Matching](https://mlsanity.com/paper/2502.15805/) (2025)
- [Categorical Schr"odinger Bridge Matching](https://mlsanity.com/paper/2502.01416/) (2025)
- [Branched Schr"odinger Bridge Matching](https://mlsanity.com/paper/2506.09007/) (2025)
- [Discrete Adjoint Schr"odinger Bridge Sampler](https://mlsanity.com/paper/2602.08243/) (2026)
- [Discrete diffusion samplers and bridges: Off-policy algorithms and applications in latent spaces](https://mlsanity.com/paper/2602.05961/) (2026)
- [NGDB-Zoo: Towards Efficient and Scalable Neural Graph Databases Training](https://mlsanity.com/paper/2602.21597/) (2026)
- [Learning Discrete Diffusion of Graphs via Free-Energy Gradient Flows](https://mlsanity.com/paper/2604.11311/) (2026)
- [Beyond Continuity: Simulation-free Reconstruction of Discrete Branching Dynamics from Single-cell Snapshots](https://mlsanity.com/paper/2605.00545/) (2026)
- [Generalized Schr"odinger Bridge on Graphs](https://mlsanity.com/paper/2602.04675/) (2026)
- [Discrete Bridges for Mutual Information Estimation](https://mlsanity.com/paper/2602.08894/) (2026)
- [Binomial flows: Denoising and flow matching for discrete ordinal data](https://mlsanity.com/paper/2605.00360/) (2026)
- [SynBridge: Bridging Reaction States via Discrete Flow for Bidirectional Reaction Prediction](https://mlsanity.com/paper/2507.08475/) (2025)
- [Entering the Era of Discrete Diffusion Models: A Benchmark for Schr"odinger Bridges and Entropic Optimal Transport](https://mlsanity.com/paper/2509.23348/) (2025)
- [Chemistry-Enhanced Diffusion-Based Framework for Small-to-Large Molecular Conformation Generation](https://mlsanity.com/paper/2511.12182/) (2025)
- [Minimal-Action Discrete Schr"odinger Bridge Matching for Peptide Sequence Design](https://mlsanity.com/paper/2601.22408/) (2026)
- [Timage: A Generative Text-in-Image Paradigm for Fine-Tuning Vision-Language Models](https://mlsanity.com/paper/2606.19944/) (2026)
- [A Time-Reparameterized Cumulative Intensity Extrapolation Sampler for Discrete Flow Matching](https://mlsanity.com/paper/2606.24140/) (2026)

## Abstract (arXiv)

Transporting between arbitrary distributions is a fundamental goal in generative modeling. Recently proposed diffusion bridge models provide a potential solution, but they rely on a joint distribution that is difficult to obtain in practice. Furthermore, formulations based on continuous domains limit their applicability to discrete domains such as graphs. To overcome these limitations, we propose Discrete Diffusion Schr"odinger Bridge Matching (DDSBM), a novel framework that utilizes continuous-time Markov chains to solve the SB problem in a high-dimensional discrete state space. Our approach extends Iterative Markovian Fitting to discrete domains, and we have proved its convergence to the SB. Furthermore, we adapt our framework for the graph transformation, and show that our design choice of underlying dynamics characterized by independent modifications of nodes and edges can be interpreted as the entropy-regularized version of optimal transport with a cost function described by the graph edit distance. To demonstrate the effectiveness of our framework, we have applied DDSBM to molecular optimization in the field of chemistry. Experimental results demonstrate that DDSBM effectively optimizes molecules' property-of-interest with minimal graph transformation, successfully retaining other features. Source code is available hrefhttps://github.com/junhkim1226/DDSBMhere.