Discrete Diffusion Schrödinger Bridge Matching for Graph Transformation

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.

Thank you for your thoughtful feedback. We deeply appreciate your detailed comments, as they provide valuable insights that will surely elevate the quality of our work.

[Weakness 1] Globally, the structure is complete but the writing is not easy to follow.

As the reviewer pointed out, there are indeed parts of the manuscript where readability should be improved. We greatly appreciate the suggestions for improving these aspects.

After a careful review of the draft, we realized that the transition between the continuous setting and the extension to the discrete setting was not been clearly explained. Specifically, the beginning of Section 2 introduces notations primarily related to discrete càdlàg paths, while Section 2.1 follows with a description of the Schrödinger Bridge (SB) in the continuous setting. This lack of clarity hinders to adequately convey our main contribution, which is an “extension of the SB problem from the continuous to the discrete setting”.

To address this, we are revising the manuscript to first provide a thorough explanation of previous work and solution methods for SB in the continuous setting, before extending to the discrete setting. In addition, we plan to move the related work section after the introduction to allow for a clearer comparison between previous work and our contribution. We are actively working on improving the manuscript’s readability. Once these revisions are complete and the updated results are incorporated, we will upload the revised version and provide further comments.

[Weakness 2]

As the reviewer mentioned, DDSBM is a framework designed to solve the Schrödinger Bridge problem specifically for discrete data, especially graph data. However, DDSBM's performance has not been evaluated on graph datasets outside of the chemical domain.

Based on the reviewer’s valuable suggestion, we conducted an additional evaluation of DDSBM on a pure generation task. This evaluation was performed on the community-20, planar, and QM9 datasets, and the performance comparisons are summarized in the table below. For these additional experiments, we used the DiGress [1] graph transformer as the backbone network for DDSBM. To ensure consistency, we adopted the same hyperparameter settings and training configurations as in DiGress, except for the noise scheduling as detailed in Appendix C.2. Training, validation, and test splits were kept consistent across all tasks, but early stopping based on the validation set was not employed, similar to the main tasks (ZINC, Polymer).

We also clarify the comparison between DDSBM and other baseline models, such as DBM and DiGress:

• All models share the same backbone neural network.
• Both DDSBM and DBM share the same reference diffusion process.
• The key difference between DDSBM and DBM lies in the application of the IMF algorithm, while both involve the same Markov projection.

For each task, both the DDSBM and DBM were trained for the same number of epochs, with sampling from the prior distribution repeated five times. The results were averaged across the five for the Maximum Mean Discrepancy (MMD) of graph features. Additionally, for the planar and QM9 datasets, further metrics such as Validity/Uniqueness/Novelty (V.U.N.) were evaluated.

[Results of Community-20]

\begin{array}{l|cccc} \text{Model} & \text{Degree} \downarrow & \text{Clustering} \downarrow & \text{Orbit} \downarrow & \text{NLL} \downarrow \newline \hline \text{GraphRNN} & 8.00\text{e-}02 & 1.19\text{e-}01 & 4.00\text{e-}02 & - \newline \text{GRAN} & 6.00\text{e-}02 & 1.12\text{e-}01 & 1.00\text{e-}02 & - \newline \text{GG-GAN} & 8.00\text{e-}02 & 2.17\text{e-}01 & 8.00\text{e-}02 & - \newline \text{SPECTRE} & 1.00e-02 & 1.89\text{e-}01 & 2.00\text{e-}02 & - \newline \text{DiGress} & 2.00\text{e-}02 & 6.30\text{e-}02 & 1.00\text{e-}02 & - \newline \hline \text{DBM} & 1.80\text{e-}02 & \underline{3.80\text{e-}02} & 5.14e-03 & \underline{3.26\text{e+}02} \newline \text{DDSBM} & \underline{1.75\text{e-}02} & 2.78e-02 & \underline{5.81\text{e-}03} & 2.87e+02 \newline \end{array}

In the Community-20 task, both DBM and DDSBM demonstrated superior performance compared to DiGress in terms of degree, clustering, and orbit metrics. This result highlights the strengths of DBM and DDSBM in pure generation tasks as well. Notably, DDSBM achieved the best performance in clustering (2.78.E-02) and competitive results in orbit (5.81.E-03) while also significantly reducing the NLL value (2.87.E+02) compared to DBM. These findings underscore the capacity of the DDSBM to generate high-quality graph structures at a minimal cost, even when bridging noisy distribution to data distribution.

[Results of QM9] \begin{array}{l|ccccc} \text{Model} & \text{Validity} \uparrow & \text{Uniqueness} \uparrow & \text{Novelty} \uparrow & \text{FCD} \downarrow & \text{NLL} \downarrow \newline \hline \text{GraphAF} & 74.43 & 88.64 & 86.59 & 5.27\text{e+}00 & - \newline \text{MoFlow} & 91.36 & 98.65 & \underline{94.72} & 4.47\text{e+}00 & - \newline \text{GraphDF} & 93.88 & \underline{98.58} & 98.54 & 1.09\text{e+}01 & - \newline \text{GDSS} & 95.72 & 98.46 & 86.27 & 2.90\text{e+}00 & - \newline \text{GraphArm} & 90.25 & 95.62 & 70.39 & 1.22\text{e+}00 & - \newline \text{GLAD} & 97.12 & 97.52 & 38.75 & 2.01\text{e-}01 & - \newline \text{DiGress} & 99.00 & 96.66 & 33.40 & 3.60\text{e-}01 & - \newline \hline \text{DBM} & 99.87 & 96.59 & 36.54 & 9.90e-02 & \underline{7.55\text{e+}01} \newline \text{DDSBM} & \underline{99.67} & 96.83 & 38.06 & \underline{1.05\text{e-}01} & 5.38e+01 \newline \end{array}

For the QM9 task, both DBM and DDSBM demonstrated significant improvements in FCD compared to DiGress, as reported in reference [2]. Additionally, enhancements in validity and novelty were also observed. While DBM showed slightly better performance in FCD (9.90.E-02) and validity (99.87%), DDSBM exhibited strengths in novelty (38.06%) compared to DBM. For other metrics, DDSBM and DBM displayed comparable performance.

[Results of Planar] \begin{array}{l|ccccc} \text{Model} & \text{Degree} \downarrow & \text{Clustering} \downarrow & \text{Orbit} \downarrow & \text{V.U.N} \uparrow & \text{NLL} \downarrow \newline \hline \text{GraphRNN} & 4.90\text{e-}03 & 2.79\text{e-}01 & 1.25\text{e+}00 & 0 & - \newline \text{GRAN} & 7.00\text{e-}04 & \underline{4.34\text{e-}02} & \underline{9.00\text{e-}04} & 0 & - \newline \text{SPECTRE} & \underline{5.00\text{e-}04} & 7.75\text{e-}02 & 1.20\text{e-}03 & 25 & - \newline \text{ConGress} & 4.76\text{e-}03 & 2.73\text{e-}01 & 1.30\text{e+}00 & 0 & - \newline \text{DiGress} & 2.80e-04 & 3.72e-02 & 8.50e-04 & 75 & - \newline \hline \text{DBM} & 9.35\text{e-}04 & 8.95\text{e-}02 & 8.67\text{e-}03 & 81.5 & \underline{1.96\text{e+}03} \newline \text{DDSBM} & 7.39\text{e-}04 & 5.81\text{e-}02 & 9.60\text{e-}04 & \underline{76} & 1.51e+03 \newline \end{array}

In contrast to other tasks, we observed that DBM/DDSBM demonstrated lower performance than DiGress on the Degree, Cluster, and Orbit metrics. We regard this to two primary reasons.

Firstly, for DDSBM, the Planar task requires relatively more epochs to converge compared to other tasks. The values reported in the table correspond to the results from 100K epochs, which have not yet reached convergence. Second, we observed a slight trade-off between validity and the graph feature MMD metrics on each IMF iteration during training. We are currently continuing the training process for this task and will include the fully converged results in the manuscript at a later stage.

As evidenced by the NLL metric, DDSBM involves minimal changes compared to DBM, which we also confirmed with the chain visualization. Following the reviewer's suggestion, we plan to include this in the paper and will incorporate it while revising the manuscript.

We appreciate the reviewer’s understanding and patience as we refine our analysis for this specific task.

[Reference]

[1] Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., & Frossard, P. (2022). Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.14734.

[2] Nguyen, V. K., Boget, Y., Lavda, F., & Kalousis, A. (2024). GLAD: Improving Latent Graph Generative Modeling with Simple Quantization. arXiv preprint arXiv:2403.16883.

[Question 1 Graph matching ablation]

As suggested by the reviewer, we have analyzed the effect of graph matching on the performance of DDSBM by comparing the results of using four different graph matching algorithms. This experiment was conducted on the ZINC dataset, and the evaluation was performed after six IMF iterations (See Table 5 in Appendix).

The performance differences across graph matching algorithms were not significant, as shown in the following table. We attribute this to DDSBM's ability to preserve the permutation of the original graph based on our reference process. This property enables the generation of pairs with reduced NLL by Markovian projection during IMF iterations. Due to this effect, the model converges in a similar manner regardless of the specific graph matching algorithm applied at each IMF iteration, resulting in minor differences as shown in the table.

\begin{array}{l|ccc|ccc|ccc} \text{Algorithm} & \text{Val.} \uparrow & \text{Uniq.} \uparrow & \text{Nov.} \uparrow & \text{FCD} \downarrow & \text{NLL} \downarrow & \text{NSPDK} \downarrow & \text{LogP } W_1 \downarrow & \text{QED MAD} \downarrow & \text{SAScore MAD} \downarrow \newline \hline \text{(1) SM} & 94.6 & \mathbf{100.0} & 99.9 & 0.837 & 163.931 & 1.17\text{e-}3 & 0.159 & 0.122 & \mathbf{0.388} \newline \text{(2) MPM} & \mathbf{95.8} & \mathbf{100.0} & \mathbf{100.0} & 0.773 & \mathbf{155.378} & 6.95\text{e-}4 & 0.164 & \mathbf{0.110} & 0.401 \newline \text{(3) MPM + Randomness} & 95.3 & \mathbf{100.0} & 99.9 & 0.759 & 158.534 & 6.78e-4 & \mathbf{0.130} & 0.116 & 0.424 \newline \text{(4) Our setting} & 94.1 & \mathbf{100.0} & 99.9 & \mathbf{0.747} & 164.480 & 7.49\text{e-}4 & 0.139 & 0.124 & 0.392 \newline \end{array}

Based on the observation that the performance of DDSBM is not strongly related to the algorithm of graph matching, one can infer that DDSBM can generate pairs that reduce NLL, minimizing the effect of graph matching. With this perspective, we also compared the results of two scenarios: 1) one without using any graph matching throughout the whole training process, and 2) another with graph matching both on the initial data and during the IMF iterations. Note that the latter is the same experimental setup as in the current manuscript.

Interestingly, similar to the ablation study of the graph matching algorithm, we found that the use of graph matching merely affected the result after a sufficient number of IMF iterations. However, we found that both the training loss and the NLL between the original and generated data values were initially higher in the absence of graph matching than in the presence of graph matching, and they gradually converged to similar levels as iterations progressed. This indicates that graph matching algorithms, while not essential for the eventual convergence of DDSBM, can accelerate convergence during the IMF iterations, providing an additional benefit beyond the Tanimoto coupling discussed in the manuscript.

We sincerely appreciate the reviewer’s constructive feedback, which allowed us to identify the effect of graph matching on the performance of DDSBM. This investigation has provided us with a clearer understanding of DDSBM’s capabilities, and we are pleased to have been able to confirm and clarify its performance more thoroughly. We will include the contents of this discussion in appendix of our revised manuscript.

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.

[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 thoughtful review and recommendations regarding related works.

We have revised the Methods section to address reference [1], as suggested: "The SB problem in discrete setting has recently been studied by Chow et al. (2021) [1], which formulates an optimal transport problem on graphs as the SB problem. Graph transformation can be seen as a analogous problem in terms of the data states are discrete, but the fact that each data is also an individual graph requires distinct formulation for transition between one another."

In response to reviewers’ suggestions, we have performed additional experiments to further validate our approach and enhance the robustness of our results. Specifically, we included error bars calculated over multiple training runs and introduced three new evaluation metrics: NSPDK, Uniqueness, and Novelty. These additions offer a more comprehensive and reliable assessment of our method.

Furthermore, we expanded the scope of our experiments to include unconditional generations in several widely-used datasets: QM9 (a molecular dataset), as well as Comm20 and Planar (general graph datasets). These additional evaluations provide a more comprehensive validation of our approach. The detailed results of these additional experiments have been provided in our official comments to other reviewers.

We are also actively revising the manuscript to improve its clarity and readability. We welcome further discussion or suggestions regarding the additional results and are committed to incorporating feedback to strengthen the manuscript.

[Reference]

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

Could please acknowledge and respond to the rebuttal.

Dear Reviewer 7pXr,

We have thoroughly revised the manuscript to address all the suggested changes.

We have summarized the major revisions made in the revised manuscript, from ”General Response” and “Summary of Additional Experiments and Results”.

This is a gentle reminder, as we approach the final stages of the discussion period.

We sincerely hope for a valuable and constructive conclusion to the discussions regarding our paper.

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.

We would like to thank the reviewer for valuable feedback.

[Weakness 1, 2]

We conducted additional experiments and included error bars across different training runs.

Table 1 (ZINC) and Table 2 (Polymer) will be updated based on three independent training runs. We confirmed that the trends remain consistent across multiple experiments, further demonstrating the robustness of DDSBM. See the revised ZINC table and revised Polymer table.

Additionally, we included NSPDK as a metric. Similar to other metrics, DDSBM demonstrated superior performance. We are grateful to the reviewer for guiding us to further validate our approach.

[Weakness 3]

We are currently reorganizing Sections 2, 3, and 4 to better convey our insights.

In addition, based on the reviewer's suggestion, we plan to include an introduction to the Schrödinger Bridge problem and CTMC in the appendix to help readers better understand the context.

We are also preparing a graphical item—chain visualizations—to provide an intuitive explanation of how DDSBM operates on graphs.

We aim to ensure that this addition makes the concepts more accessible and comprehensible to potential readers.

[Question 2]

To clearly highlight the performance differences in the validity metric between the baseline and DDSBM, we conducted evaluations on novelty and uniqueness. While the baselines achieved almost 100% validity, their novelty and uniqueness scores were significantly lower compared to DDSBM. Thanks to the reviewer’s suggestions, we were able to clarify the distinctions between the baseline and our method and further reaffirm the strengths of DDSBM.

Thank you once again for your valuable feedback, which has helped us clarify the key arguments of our paper.

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

Dear Reviewer AZ9a,

We have added a tutorial on the Schrödinger Bridge problem and Iterative Markovian Fitting in Appendix A.

This tutorial includes detailed explanations of the theoretical background and links each part directly to the relevant sections of the manuscript, making it more accessible to readers.

In addition, we have provided insights showing that SB in discrete spaces can be intuitively understood as finding a coupling that best preserves the initial states, which aligns with the core motivation behind the development of DDSBM.

We hope that this tutorial will help general readers to understand the Schrödinger Bridge problem and our work better.

We look forward to your feedback and sincerely thank you once again.

Could please acknowledge and respond to the rebuttal.