Discrete Diffusion Schrödinger Bridge Matching for Graph Transformation
Schrödinger Bridge;Discrete Diffusion Model;Molecular Optimization
Thank you for your constructive feedback. We appreciate your detailed comments, as they provide valuable insights that will certainly help improve the quality of our work.

W1: We acknowledge the need for clearer structure and presentation. We will revise the manuscript to clearly highlight our strengths. As soon as the revisions are complete, we will reply with an official comment.

W2: We understand the importance of providing additional experimental evidence as proposing a discrete model for DSBM. To address this, we plan to extend our experiments on additional datasets proposed in SPECTRE [1] for graph generation task. The datasets include synthetic graph dataset (**Community-small**) and widely-used molecular dataset (**QM9**). Additionally, we will conduct graph generation on larger synthetic graph dataset (**Planar**), to further validate our approach. We will also include the generation trajectories for our previously conducted experiments to provide deeper insights. Specifically, we will compare DBM and DDSBM with DiGress in terms of degree, cluster and orbit for all datasets, while additionally evaluating VUN (valid, unique & novel graphs) for the planar dataset. We will share experimental results as they become available. Please let us know if there are any additional results or analyses that the reviewer would find helpful for a more comprehensive evaluation of DDSBM.

W3: We will conduct experiments to compare the effects of graph matching algorithms displayed in Appendix table 4.

We will provide an official comment once these revisions are finalized. Thank you again for your valuable feedback.

Reference

[1] Martinkus, Karolis, et al. "Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators." *International Conference on Machine Learning*. PMLR, 2022.
**[Additional Experiment Plan]**

Our proposed method is not limited to mappings between molecular graphs alone with its theoretical support. To further substantiate this claim, we plan to conduct additional experiments applying our approach to a more diverse set of general graphs beyond molecular structures.

Specifically, we plan to extend our experiments on additional datasets proposed in SPECTRE [6] for graph generation task. The datasets include synthetic graph dataset (**Community-small**) and widely-used molecular dataset (**QM9**). Additionally, we will conduct graph generation on larger synthetic graph dataset (**Planar**), to further validate our approach.

We believe this review process will constructively enhance the quality of the manuscript. If there are any additional aspects you would like us to discuss, please feel free to let us know.

**[References]**

[1] Campbell, Andrew, et al. "Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design." Forty-first International Conference on Machine Learning.

[2] Gat, Itai, et al. "Discrete flow matching." arXiv preprint arXiv:2407.15595 (2024).

[3] Harchaoui, Zaid, Lang Liu, and Soumik Pal. "Asymptotics of discrete Schrödinger bridges via chaos decomposition." Bernoulli 30.3 (2024): 1945-1970.

[4] Chow, Shui-Nee, et al. "A discrete Schrodinger bridge problem via optimal transport on graphs." calculus of variations 20.33 (2021): 34.

[5] https://openreview.net/forum?id=rMyfMS5nMt

[6] Martinkus, Karolis, et al. "Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators." *International Conference on Machine Learning*. PMLR, 2022.
Thank you for your thoughtful review and suggestions on related works. Here, we would like to briefly explain the primary task of this work. Our focus lies in transformations between graphs, specifically including molecular graphs. Rather than addressing the transportation between distributions defined over topological spaces of graphs, we tackle the problem of transporting the source graph to the target graph through structural edits (graph transformations).

**[Regarding Weakness 1 & Question 2]**

As you suggested, comparing flow matching models (FM) and diffusion bridge models (DBM) would indeed be an interesting study. In essence, FM and DBM approaches are similar in that they share the objective of training a transportation between two distributions.

The proposing method defines a reference process as a continuous-time Markov chains (CTMC) in a discrete metric state space, then solves the associated “Schrödinger bridge problem” (SBP). The SBP can be interpreted as an entropy-regularized optimal transport problem (EOT), making it closely related to optimal transport-flow matching (OT-FM). However, it is important to emphasize that, while both DBM and SBP aim to transport between distributions, SBP aims to find the optimal joint distribution (paired data distribution) in contrast to DBM, whose objective is to learn transportation map based on a given joint distribution. This distinction also parallels the difference between FM and OT-FM.

Due to these differences, it would be challenging to conduct a controlled comparison between FM and our method, as several variables in the methodology—such as deep learning model architecture, SDE vs. ODE formulations, sampling algorithms, and training of joint distributions—would be difficult to control. Additionally, the two FM papers [1, 2] you suggested focus on transporting node feature distributions within a fixed graph structure rather than addressing the transformation of the graph structure itself. Reflecting image and text data inherently form sequences or grid structures, the suggested references do not alter these underlying structures. For these reasons, we believe the suggested references may not align closely with the main focus of our manuscript.

To the best of our knowledge, the only work on OT-FM for graphs is [5], which is currently under peer review at ICLR 2025, and code for this work has not yet been released.

**[Regarding Weakness 2 & Question 1]**

As the reviewer mentioned, our proposed DDSBM is not the first to address the Schrödinger bridge problem in discrete states. Reference [3] addresses the SBP between two distributions based on empirical datasets realized from each distribution, and shows that as the number of observations grows, the solution converges to the SB between the true distributions. Since DDSBM is also framed as an SBP between empirical distributions, this work could indeed be a useful reference. However, our work focuses on the transport problem between graph structures (”*discrete*-states”) rather than the fact that the problem is addressed with sampled (”*discretized*”) distributions. Also, we propose a solution method for the SBP in discrete setting, called DDSBM, while the reference [3] does not. Due to these aspects, the reference [3] differs from the central objective of DDSBM.

Reference [4] defines the Schrödinger bridge problem *on* graphs and provides a numerical solution, establishing SBP on a graph space where nodes have defined probabilities and edges have defined weights. Within the context of this reference, our work could be considered an SBP for graph transformations: each node represents a graph dataset, such as a molecular graph, and edge weights are defined through a reference stochastic process (CTMC). Unlike the reference [4], which cannot generate new data, our work aims to produce transformed data for novel cases through generative modeling, addressing the transportation of data distributions. Nevertheless, the reference [4] indeed provides a valuable perspective on defining and solving the Schrödinger bridge problem in discrete spaces, and we will reference it in our manuscript.
We thank you for your thoughtful feedback and valuable suggestions, which have significantly contributed to the clarity and rigor of our work. Below, we outline our planned revisions and responses to each point raised.

W1: We will incorporate the NSPDK metric as suggested.

W2: We agree that presenting error bars would enhance the robustness of our results. To address this, we will conduct additional experiments and include error bars across different training runs.

W3: We acknowledge that the current version may sound overly technical to the typical graph machine learning practitioner. In response, we will revise this section to improve clarity and accessibility, reflecting your suggestion. Once the revisions are complete, we will provide an official comment.

Q1: We apologize for omitting a reference for the Hungarian algorithm. The Hungarian algorithm, also known as the Kuhn-Munkres algorithm [1], is a combinatorial optimization technique for solving the assignment problem. We used the Hungarian algorithm implemented in the Pygmtools package [2]. In the revised manuscript, we will add the references.

Q2: We acknowledge that the baseline models show higher validity compared to our method. However, we observed that these models also demonstrate relatively low uniqueness, which suggests that their validity scores may be overestimated due to potential redundancy in generated structures. In this regard, we will conduct a thorough re-evaluation to verify these findings, and we will add a detailed discussion on this point in the revised manuscript.

Once these revisions are complete, we will provide an official comment. Thank you once again for your constructive comments.

If there are any additional requests, please feel free to let us know.

References

[1] Kuhn, H. W. (1955). The Hungarian method for the assignment problem. *Naval research logistics quarterly*, *2*(1‐2), 83-97.

[2] Wang, R., Guo, Z., Pan, W., Ma, J., Zhang, Y., Yang, N., ... & Yan, J. (2024). Pygmtools: A python graph matching toolkit. *Journal of Machine Learning Research*, *25*, 1-7.
Yes
No ethics review needed.
- What is the Hungarian algorithm ? You mention it in section 3.3. I'd appreciate if you could drop a reference or give some details in appendix.
- The baselines outperform your approach in terms of Validity. Even though the results on FCD and NLL indicate that your method is stronger, I'd appreciate if you could comment on this metric.
- The Schrödinger bridge problem is well studied in the continuous-state diffusion literature, but has, to the best of my knowledge, not yet been applied to the discrete setting. The paper nicely bridges this gap, hence proposing a valuable contribution to the discrete diffusion literature.
- The paper looks sound and technically strong.
- Empirical results seem to indicate that this approach outperforms previous baselines by a large margin.
This work presents Discrete Diffusion Schrödinger Bridge Matching (DDSBM), a framework that adapts continuous-time Markov chains (CTMCs) to address the Schrödinger Bridge (SB) problem within high-dimensional discrete spaces. Using the Iterative Markovian Fitting (IMF) technique, DDSBM enables optimal graph modifications by minimizing structural changes, which is particularly valuable for molecular optimization tasks in drug and material discovery. In this context, the framework aligns with graph edit distance (GED), allowing efficient property-driven modifications while preserving the molecule's structure. Experiments show DDSBM achieves minimal structural shifts and successfully maintains desirable molecular properties, outperforming traditional graph translation methods.
- The choice of the FCD metric the evaluate the graph structure distributions is surprising, since it is typically used to assess distribution learning from a chemical perspective. Why not use NSPDK for example ?
- I’d like to see some error bars on your results.
- The method description is quite technical, and might be hard to understand for the average graph machine learning practioner. It could be worth it to include a short tutorial on the Schrödinder Bridge problem to ease the reader understanding.
Yes
No ethics review needed.
1. What is the relevance and difference between the proposed method and existing discrete SB models in Weakness?

2. How does the performance of molecular optimization compare with discrete flow matching models?
Strong performance compared to diffusion bridge model.
This paper introduces discrete diffusion Schrödinger bridge model using continuous-time Markov chains. The proposed model was validated on molecular optimization problem.
Overall, this paper failed to distinguish its own contributions from existing work and to compared itself with relevant works. First of all, the proposed discrete diffusion Schrödinger bridge matching (DDSBM) highly relies on continuous-time Markov chains (CMTC). However, this paper failed to refer flow matching models [1, 2] which introduce CMTC for discrete data domains. 

[1] Campbell, Andrew, et al. "Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design." Forty-first International Conference on Machine Learning.

[2] Gat, Itai, et al. "Discrete flow matching." arXiv preprint arXiv:2407.15595 (2024).

And, this is not the first paper that solving Schrödinger bridge (SB) problem in discrete state spaces. There are works for discrete SB [3, 4]. However, the relevance and difference between the proposed method were not discussed.

[3] Harchaoui, Zaid, Lang Liu, and Soumik Pal. "Asymptotics of discrete Schrödinger bridges via chaos decomposition." Bernoulli 30.3 (2024): 1945-1970.

[4] Chow, Shui-Nee, et al. "A discrete Schrodinger bridge problem via optimal transport on graphs." calculus of variations 20.33 (2021): 34.
Yes
No ethics review needed.
How significantly does the choice of graph-matching algorithm impact the overall performance of the method?
If it has a substantial influence, there is another reason that experiments for some simpler modalities without such complex matching may help to clarify the contribution.
1. This method adapts diffusion Schrodinger bridge matching which opens a new avenue for this task.
2. The experimental setting for molecular optimization is a very relevant downstream task for the discrete domain, and it builds up some baselines for that task.
3. The work provides corresponding theoretical guarantees.
Adapt diffusion Schrodinger bridge matching to the discrete domain and instantiate it through molecular optimization
1. Globally, the structure is complete but the writing is not easy to follow. The writing can be enhanced at least in the following way:
* The square brackets around the citation should not appear twice.
* The name of section 2.2 'SOLUTION METHOD' needs to be optimized.
* The supplementary material also contains the body part of the paper.
* The structure section 2/3 is a bit confusing:
  * There should be an introduction to the continuous methods (IPF, IMF) as prior knowledge since the method highly dependent on them, then a transition to the method for the discrete domain. Here, section 2 starts by discussing the discrete domain and introducing the definitions together, which makes it a bit confusing which parts come from previous work and which part comes from this work.
  *  Consequently, the insights about the transition from continuous domain to discrete domain are missing.

2. Under the claim of proposing a discrete model for DSBM, the results only contain 2 molecule datasets with few supportive ablation experiments being given. It will support better the contribution of this work to give toy results for examples except for molecule optimization such as toy datasets with discrete features, or results on other types of graphs, or more ablations, or pure generation results (as in continuous SB papers), or more visualizations of the resulting optimization chain. No need to have them all, but similar supportive evidence would definitely make the experiments more complete.
We propose DDSBM, a framework for solving the Schrödinger Bridge problem in high-dimensional discrete spaces, applied to graph-based molecular optimization.
@inproceedings{
anonymous2024discrete,
title={Discrete Diffusion Schr\"odinger Bridge Matching for Graph Transformation},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=tQyh0gnfqW},
note={under review}
}
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ödinger 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.
Code is available [here](https://anonymous.4open.science/r/DDSBM-1353).
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Schrödinger Bridge Discrete Diffusion Model Molecular Optimization
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/c8e59f4a54a67b5efc6a4867dacc26e1a487c78d.pdf
generative models
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/e1577d6c8dba7e067696381baf2b19617b1bcb89.pdf
Discrete Diffusion Schrödinger Bridge Matching for Graph Transformation
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission