Discrete Diffusion Schrödinger Bridge Matching for Graph Transformation
Authors: Jun Hyeong Kim
Seonghwan Kim
Seokhyun Moon
Hyeongwoo Kim
Jeheon Woo
Woo Youn Kim
Venue: ICLR 2025 Poster (2025)
Keywords: Schrödinger Bridge
Discrete Diffusion Model
Molecular Optimization
Primary area: generative models
TL;DR: We propose DDSBM, a framework for solving the Schrödinger Bridge problem in high-dimensional discrete spaces, applied to graph-based molecular optimization.

Abstract: 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. Source code is available [here](https://github.com/junhkim1226/DDSBM).

Published as a conference paper at ICLR 2025
DISCRETE DIFFUSION SCHRÖDINGER MATCHING FOR GRAPH TRANSFORMATION
BRIDGE
Jun Hyeong Kim!; Seonghwan Kim-; Seokhyun Moon'; Hyeongwoo Kim";
Jeheon Woo Woo Youn Kim!
KAIST
ABSTRACT
Transporting between arbitrary distributions fundamental goal in generative modeling. Recently proposed diffusion bridge models provide potential solu- tion, 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 Fit- ting to discrete domains, and we have proved its convergence to the SB. Further- more, we adapt framework for the graph transformation and show that our de- sign choice of underlying dynamics characterized by independent modifications of nodes and edges can be interpreted 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 opti- mization in the field of chemistry. Experimental results demonstrate that DDSBM effectively optimizes molecules' property-of-intere with minimal graph trans- formation, successfully retaining other features. Source code is available at here
INTRODUCTION
Transporting initial distribution to a target distribution is a foundational concept in modern gen- crative modeling. Denoising diffusion models (DDMs) have been highly influential in this area, with primary focus generating data distributions from simple prior (Sohl-Dickstein al. 2015) Song & Ermon 2019: Ho et al.) 22020) [Song et al.) [2000] Kim et al. 2024b). Despite their promising results, setting the initial distribution as a simple prior makes DDMs hard work in tasks where the initial distribution becomes a data distribution, such as image-to-image translation. To tackle this, diffusion bridge models (DBMs) extend DDMs to transport data between arbitrary distribu- tions (Liu & Wu 2023 Liu et al. 2023 Zhou et al. 2023). However, training DBMs requires a coupling between the initial and target distributions, which is often difficult obtain in practice. The Schrödinger Bridge (SB) provides an attractive framework for constructing joint distribution of two data distributions while aligning with the underlying stochastic dynamics (Pariset al., 2023
Kim et al. 2023 Dong et al. 2024)).
Formally, the SB problem seeks the stochastic process that connects two distributions and is closest to reference process, measured by the Kullback-Leibhe (KI.) divergence (Schrödinger) 1932). The SB problem can be described as an roguoiy-regulariieed optimal transport (EOT) problem, which in- troduces an entropy term to the optimal transport (OT) objective, resulting in randomness in the transport process (Léonard, (013).. Here, the transportation cost is determined by the system's nat- ural dynamics; for example, in the case of Brownian motion, the transportation cost becomes I (De Bortoli et al. 2021). The SB/EOT can be computed efficiently using the Sinkhorn algorithm, though high-dimensional or large-scale data applications remain challenging (Sinkhorn) 1967 Cu- turi 2013). In recent, many methods have been proposed to approximate SB via distribution learn-
"Equal contribution
Coorespondence waoyoun @ kaist.ac.kr

---

Published as a conference paper at ICLR 2025
r(
E(X,)
DDSBM
(a) Bridge process
(b) Schrödinger Bridge
Figure I: A schematic illustration of DDSBM transforming (a) bridge process to (b) Schrödinger
Bridge in discrete spaces.
ing, utilizing techniques developed in DBM and DDM (De Bortoli et al. 2021 Liu et 2022 Somnath et al. 2023 Liu et al. 2023 Peluchetti 2023a
Shi et al. 2024 Lee et al. (222))
Despite the progress, most of the methods focus on the continuous spaces, where diffusion processes are represented by Brownian motion, and SB problems in discrete domains are less explored. It is particularly significant in fields that handle discrete state data, such as graphs or natural language (Austin al. 2021 Vignac al., 2022). Directly applying frameworks for approximating SB formulated in continuous spaces to these domains limits its potential since it does not reflect the intrinsic properties of discrete data space. To bridge the gap, propose novel framework called Discrete Diffusion Schrödinger Bridge Matching (DDSBM) utilizing the continuous-time Markov chains (CTMCs) to solve the SB problem in high-dimensional discrete setting. Our approach leverages Iterative Markovian Fitting (IMF), which was originally proposed for the SB problem in continuous domain (Peluchetti 2023a Shi al. 2024).
We then extend our formulation to the graph domain, where the underlying process can be inter- preted independent modifications to both the nodes and edges (Vignac et al., (022). In this case, the cost function of the corresponding EOT can then be regarded as the graph edit distance (GED), which especially suited for systems where preserving graph similarity is crucial (Sanfeliu & Fu, 1983). The molecular optimization in drug/material discovery is such a case in that molecules are represented as graphs. addition, the goal is obtain the molecules with desired molecular prop- erties while retaining favorable properties in acclaimed molecules. Since molecular structures are closely related to their properties, it highly advantageous to minimize structural changes (or graph editing) during the optimization.
To validate our framework, we evaluated the performance of DDSBM on molecular optimization tasks, with criteria of demonstrating optimal structural modifications achieve desired property. DDSBM shows promising results in molecular distribution shift with minimum structural change compared the previous graph-to-graph translation models. As direct result of this, DDSBM retains multiple properties of the initial molecules, along with desired property. Lastly, we applied DDSBM for a more challenging task, where proper joint pairing between two molecular spaces can not be defined properly.
Our contributions as follows:
We propose a novel framework, DDSBM, for the SB problem discrete state spaces by exploiting the IMF procedure and prove its convergence to the SB solution.
We extend our framework the graph domain, demonstrating connection between the objective function and the GED.
By reformulating molecular optimization as the SB problem, we show that our approach successfully addresses molecular optimization tasks.
2

---

graph transformation Published as a conference paper at ICLR 2025
2 RELATED WORKS
Diffusion Bridge Models. Diffusion bridge models (DBMs) have recently shown state-of-the-art results in variety of continuous domains, such as images, biology, and chemistry (Liu & Wu, 2023 Liu et al. 2023, Somnath et al., 2023 Zhou et al. 2023 Lee et al. 2024). While Lgashov al. [023]; : Yang et al. (2023) have extended these models discrete domains, they focused on settings where well-defined data pairs exist. To the best of our knowledge, we are the first to study DBM in discrete domains where proper joint distributions between data points are not provided or well-defined.
Schrödinger Bridge Problem. The Schrödinger Bridge (SB) problem is an important concept in recent generative modeling (Liu et al.) 2022, Somnath et al. 2023 Peluchetti 2023a Shi et al.) 2024). In particular, incorporating the SB problem into DBM can address scenarios where no ap-
propriate joint distribution is available, demonstrated by recent works (Pariset al., 2023 Kim et al. [023] Dong et al., 2024). For example, SSomnath et al. (2033) proposed learning an SB based on an assumed (partial) true coupling, while Shi et al. (2024) showed that it is possible generate high-quality samples from arbitrary couplings that are well-aligned with the initial data. However, most existing approaches focus on continuous spaces. To the best of our knowledge, are the first to propose framework for solving the SB problem in nigh-dimenssonal discrete spaces.
Molecular Optimization. Molecular optimization is a promising strategy drug/material discov- ery that aims to improve acclaimed molecules to satisfy multiple domain-specific properties. One major approach to the molecular optimization problem to formulate problem, which can be categorized into latent- based and graph-editing approach. The latent based approaches such as JA-VAE by Jin al. (2018) and HierG2G by Din et al. (2020) encode an input graph into a single latent vector and then decode it into a whole graph that follows certain data dis- tribution. The graph-cditing approaches such as Modof by Chen et al. (202I) and DeepBioisostere by Kim et al. 2024a) learn a graph editing procedure transport given molecule to another. De- spite their promising results in optimizing molecular graphs, their training schemes rely on paired data created by predefined rules, which limits not only the general applicability but also the opti- mality of the transformations. In this work, we propose a more flexible framework for molecular optimization by formulating it as graph SB problem, leading more optimal graph transformation accompanying less structural changes.
3 THEORETICAL BACKGROUND
3.1 SCHRÖDINGER BRIDGE PROBLEM
Consider the standard Brownian motion (X,)oses+ defined in Fuclidean space, taken as a reference process with given transition density. Given initial distribution I' for Xo. the distribution for X, is subsequently determined by and the transition density of the reference process. Suppose not only preseribe the initial distribution I but also specify a terminal distribution E at == In this scenario, the reference process X, generally fails to hold the boundary conditions. Schrödinger Bridge (SB) problem finding the process that closely resembles the reference process while satis- fying the boundary conditions on initial and terminal distributions. For an intuitive introduction to the SB problem, please refer Appendices A.I and A.2
Specifically, the reference process with the path measure Q is given, the SB problem is finding a process with path measure P by minimizing Kullback-Leibler (KL) divergence to the reference process, DKL. (IP]]Q) (Q). The SB solution is characterized as below:
PSB arg min DEL (PIIQ) : P. T.P. E}.
If we additionally fix the initial and terminal coupling (joint distribution) Po,r, the optimality can be found easily as a mixture of bridges Po.rQ.10. jo.r (see formal definition at Definition 3.1.. which
implies that finding the SB solution is equivalent to finding optimal coupling PSB (Léonard) 2013). In particular, such optimal coupling is called static SB solution, which could be defined as Tollows:
SB 0,7
= arg min ( (P (Fo,r Qo.r) Po = Ir,,, = E}.
(2)
Fo,-
3

---

Published as a conference paper at ICLR 2025
Note that the KL-diieegencce is decomposed into the entropy term (Po,r) and the cross-entropy term E2..- |- log ( [2)]], where denotes the transition density of Q The transition density in cross-entropy term is I,2 distance when the reference process is the standard Brownian motion. In general, the static SB problem is equivalent the entropy-regularizedd optimal transport (EOT) problem with the cost function c(2, y) = - log (-)o(y|2)) (Léonard 2013).
3.2 STOCHASTIC PROCESS OVER DISCRETE SPACE
To extend the SB problem to discrete state spaces, a suitable stochastic process necessary. Un- like continuous spaces, where Brownian motion serves as the canonical reference process, discrete spaces require a distinct approach that aligns with their structure.
Let the state space (X, dx) be finite metric space, where X' is the finite set of states, and dx represents the distance between states. The corresponding path space f = D[ +l,x) consists of all left-limited and right-continuous (cádlág) paths over X' within the time interval [0, r]. A path w E Ω represents a sequence of states indexed by time, where wi E X' denotes the state at time The space of path measures is denoted ((2)) and the set of Markov path measures is denoted as M C P(?).
In this work, model the reference path measure for the SB problem, Q M,, continuous-time Markov chains (CTMCs). A CTMC describes the stochastic evolution over X' in continuous time, which is characterized by transition rates. The transition rate A, u) defines the instantaneous rate of transition from x' to at time t. This rate satisfies A((x, y) 2 0 for x # y, and Σyex A (I, y) = 0. The time evolution of the stochastic process is governed by the Kolmogorov forward equation:
OP.: (x. v) Ot
Σ EE
Par(a, (e)(c,))A((z.)) ())
(3)
where (1. y) is the probability of transitioning from r at time to at time t. To ensure that the reference process Q suitable for constructing the SB problem, we assume that the reference process is an irreducible CTMC, meaning that every state in X' can be reached from any other state. More specifically, for any pair of states x, y E X, (ro(y)=) == (a- y) >
3.3 EXTENSION OF ITERATIVE MARKOVIAN FITTING METHOD TOWARD DISCRETE SPACE
Recently, there have been many studies to solve the SB problem with diffusion processes smooth manifolds using denoising score matching (Peluchetti 2023a Shi et al. 2024]. We refer to Ap- pendix A.3 for brief description of the method. While these approaches primarily focus on con- tinuous spaces, we here aim to address the SB problem in discrete spaces, specifically dealing with left limited and right continuous (càdlàg) paths over finite state spaces. While it is known that the
SB problem can be solved in finite state spaces (Sinkhorn 1967, Cuturi 2013 Chow et al. 2021) existing methods face limitations when handling -igh-diiensional or large-scale data and are not suitable for generative modeling applications. For an intuitive explanation and our insights into the discrete SB problem, refer to Appendix(A.4
Overcoming these challenges, we extend the Iterative Markovian Fitting (IMF) method, originally formulated on continuous diffusion processes, to the discrete setting of Markov chains over fi- nite state spaces. The IMF method and projection operations were introduced in previous work (Peluchetti] 2023a Shi et al. 2024); we adopt these concepts without conceptual changes. Our con- tribution lies in providing the theoretical extension toward the discrete setting, which to the best of our knowledge, has not been previously established.
In this subsection, introduce the previously developed IMF method and prove convergence theorem specific to the discrete-state problem setting, with detailed proofs provided in Appendix B Despite extending the IMF method to discrete spaces, our approach is still fundamentally rooted in the intrinsic properties of the SB solution. Specifically, we rely on the representation of the unique Markov measure as a mixture of bridges Po Q (o,7 (see Theorem B.I.
According to Theorem B.I the SB solution is mixture of pinned-down measures of Q(-
Ip. X, = ), where the pair (Do, xT) is drawn from the coupling IPSR Based on this, the projection method first constructs reciprocal measure, which is mixture of pinned-down processes from
4

---

Published as a conference paper at ICLR 2025
given initial coupling. Although each pinned-down process is Markov, the mixture generally loses the Markov property in general as a collection of Markov processes is non-convex (Léonard et al. 2014). Thus, it then identifies the Markov measure that is closest to the mixture. This yields an improved coupling, and the process iterated to obtain a measure that is both the mixture of pinned- down measures and Markov-the desired SB solution.
In this context, we define the reciprocal projection to describe the construction of a reciprocal mix- ture from given coupling (see Definition (.T). Similarly, the term Markov projection is used to describe the approximation of reciprocal process with Markov process (see Definition 3.2) Definition 3.1. (Reciprocal Projection)
A E P(t) is in the reciprocal class R(Q) with respect to Markov measure Q if Q/,.r For a measure A E P(2), its reciprocal projection with respect to Q
(R(() = 11 Mdra, dx, (cdr (5o T.7).
Among the measures with the coupling Ao.- * 0,r, the minimizer of the KL-divergence to the ref- erence process is the (non-Markov) reciprocal projection R (A). The reciprocal projection consists of a mixture of bridges, where each bridge derived from Doob's h-transform with the realization of an end-point pair (z,z) Ao,r (Levin & Peres 2017). Obviously, it preserves the initial-terming coupling. Although each pinned-down bridge is Markov (see Lemma B.4). the mixture generally not Markov.
Definition 3.2. (Markov Projection)
Given path measure A E R(Q), Markov path measure that minimizes the reverse KL-divergence to A is called as Markov projection of A.
IIM(A) arg min (Dk( M MM. M
The Markov projection preserves the marginal distribution at all times t, but does not preserve the coupling. Furthermore, the generator of the projected Markov measure and the reverse KL- divergence DxL. (A||[TTMAA))) are explicitly derived in the Proposition B.2
For given reciprocal process (0) E R(Q).. we consider a sequence (A (A(m))ne ((N) which is defined by the recurrence relation:
A 12n+1) [I (22)),,
(4)
A (2n+2) T (A (2m+1)).
where 0000 = and A Under mild assumptions, the resulting sequence of measures of iterative projection converges psB in law (see Theorem 3.3 and Appendix B.5 Theorem 3.3. (Convergence of Iteration)
Assume that DxL (A ||PST < co, A(") < pSB for all n e N. Then the sequence of KL-divergence psn is non non-increasing.
(0)
(AL(A | > (KL(A (2 (15))) 2 DRL (2
DxL (2x) [ = DRI (A (1PS8) if and only if (2n) = (2n+1) = TPSB Moreover, A(r)
converges 1ps in law as n + Do.
4 METHODS
Here, we propose the Discrete Diffusion Schrödinger Bridge Matching (DDSBM) framework, which solves the SB problem in discrete state spaces with a diffusion generative modeling, supported by our theoretical background in Section 3.3 Approaches to the SB problem in continuous spaces are based on stochastic differential equations, while our method uses continuous-time Markov chains (CTMCs) in discrete state spaces. We first propose the DDSBM framework that adjusts the Itera- tive Markovian Fitting (IMF) to càdlåg paths in discrete spaces, whose convergence is ensured by Theorem 3.3 (Section 4.1). We then discuss how the DDSBM framework can be implemented for graph transtormation problem (Section 4.2) and introduce a graph permutation matching algorithm to reflect the permutation-invarian nature of graphs (Section 4.3
5

---

Published as a conference paper at ICLR 2025
4.1 ALGORITHM FOR SOLVING SCHRÓDINGER BRIDGE PROBLEM ON DISCRETE STATES
The IMF algorithm begins with a random initial coupling such that To = and nT E. Following the definition of the reciprocal class in Definition 3.1 we construct the initial reciprocal bridge to obtain the measure ( Given reciprocal measure A (2m) R(Q), the step is compute its The exact form of the transition rate for M(a++1) is
Markov projection M(2++1) (m(A)²)).
provided in Proposition B.2 In practice, the transition rate is approximated by a neural network.
To achieve this, it first samples pairs (Io, from (2m) and samples intermediate states by constructing the bridge QC X,). The sampled pairs (z,, are distributed according to (2x) Using these realizations, the rate matrix (2n+1) is approximated by parameterized Markov measure M by minimizing the following loss function:
A
Gr (Xe, v) A
(())
E (2m)
(A, - (Xx,))
E X
A. log
dt, (5)
where 1.1r denotes the generator of pinned down process of Q(-1;)), explicitly defined in From the approximated generator A,"", we can sample 2, given zg, where (æo, x+)
Lemma B.4
M = M (2++1). Note that, until the sequence of measures converges, the new joint coupling
M = M (2n+1) will differ from the previous one A
Once the Markov measure M(2++1) is obtained, we proceed to compute the corresponding recip- rocal measure A (2n+1)) through reciprocal projection, ((n++1)
(AM(2++1)) In theory, as shown in Proposition B.2 the time marginal distributions are preserved under Markov projection, meaning that A (2n) M, (2n+1) for all /. E [0, However, in practice, since the Markov projec- tion is approximated using neural network, repeatedly applying this approximation can lead to an accumulation of errors in the time marginals. Such accumulated errors may violate the marginal condition of the SB problem, particularly leading to potential failure satisfying the terminal condition P. =.
To compensate these errors, the next Markov measure (2n++2) := (m(+(2+))) is approximated in time-reversal way (see Proposition B.8 Based the time-symmetric nature of Markov mea-
sures, we can leverage the time-reversed generator A (2(++))) which enables the sampling zo conditioned Zy. where (I), M (2x+2) The approximation of (2 achieved by
minimizing the following loss function:
(()) = L' EA
A. A log
Σ D
(Xe,
v) dt,
(6)
A
where A denotes the time-reversal generator of the pinned down process of Q(-IXxo), and represents the parameters of the neural network approximating the time-reversed generator AM"
In this manner, the iterative Markov projection following the reciprocal projection performed alternately in forward and backward (time-reversal) fashion (see Algorithm Finally, this process yields sequence of measures (A (A(m))ner and (n))nt which converge to JpSB in theory.
4.2 APPLY DDSBM ON GRAPHS
We present method for applying the previously described solution to graph transformation. Here, we represent graph as = (V, E). where V = (u(1), and E = (e()) )y denote node and edge features, respectively. In molecular graph, for example, the node and edge features correspond to atomic types and edge features, respectively. Here, V and E are modeled as products of categorical random variables.
As the reference process, we define a jump process in which the nodes and edges of the graph vector change discretely, assuming that all nodes and edges independent. Therefore, the transition

---

Published as a conference paper at ICLR 2025
probability P and the rate A of the reference process is described follows: (6))
G1 G2)
II P
(1))
(0)
(1)
II
P (c )
0.1 (2,
E (2,))
=EX
(x, y) = 0,P (z, v) 1=
where denotes or E, G1 denotes EV,, (e(0)) G2 denotes (V2, E2)
=
((w5")) (c (c and X and X denote the state space of the nodes and edges, respectively. More specifically, we use monotonically decreasing function for the signal noise ratio, a [0, - (0, 1J. in which the transition rate is defined as:
1 (x. v) (,(In((1) (B... - m m())))
where yay denotes the Kronecker delta, and (V) and m(4) denote the prior distribution of nodes and edges as proposed in the previous discrete diffusion work (Vignac et al. 2022). According to the Kolmogorov equation, we get the transition probability as,
p9 (I, v) (2,
a(t) a(s)
8zn + (1 a(t) ((x)) m (y).
Note that the choice of m(-) uniform is associated to the diffusion the state space X, where the X' is considered fully-connected graph. Morcover, the stationary distribution of the associated gener- ator always becomes m(-). Although non non-uniform choice of m(-) breaks the diffusion formulation on X, it does not harm SB formulation.
The reference process defined above, Q, is permutation--cquivrrian process since each node and edge changes independently. Formally,
Que G G2) Qeal
Vo E S., 05 stttt
(10)
where Sn is the permutation group for n elements. Although we represented a graph as vectorized form, G. the graph itself must be intpuutttiooninvaiian To reflect this, we define a graph with n nodes as a set of graph vectors,
= {o(G))o S.}.
(11)
where is an arbitrary vectorization of The nature choice of a joint probability between & and G is to define it with an indicator function,
{pss
Pis if i E G., otherwisc,
p();, G,) = ,(G (G, l. =
Pij
(12)
[
where G is the number of distinct graph vectors in a graph G.. Now, can define the transition kernel between graphs with an associated stochastic process of graph vectors as follows:
:
Σ
( (o(G'), u (G)) plu (G)l9)
(13)
dESgr.uEs
Σ
1g (a(G') (oll'))Q@rrraaaaaa (a (
(14)
[
oES
Σ Sg
(w. G),
(15)
where Sg and Sgr permutatiion groups of G and g', and G and G' are arbitrary graph vectors of and G", respectively. Equation (15) connects the transition kernels on graphs and their vectorized forms.
7

---

Published as a conference paper at ICLR 2025
4.3 GRAPH PERMUTATION MATCHING
The transition probability of the reference process depends on graph permutations (see Equation so graph permutation matching must be considered beforehand. Although this issue does not affect the sampling phase, it becomes problematic when computing the likelihood of the reference process for two given graphs G and G'. or when constructing reciprocal process, which is a mixture of Markov bridges between the two graphs (see Appendix D
One way handle this selecting a graph permutation that maximizes the likelihood under the reference process. Finding the optimal permutation can be formulated as a quadratic assignment problem (QAP), where the objective is to minimize the negative log- likeliiiiioood (NLL), consisting of the sum of the NLLs for both the nodes and edges. While exact solutions are possible through mixed integer programming. the problem NP-hard, so alternative methods are preferred. Specifi- cally, we employ max max-pooling algorithm by Cho al. (2014). which is approximation method categorized by continuous relaxation. After obtaining an approximate solution, we use the Hungar- ian algorithm (Kuhn 1955), implemented in the Pygmtools (Wang et al., 2024). to discretize the assignment vector to the final solution. We observed that the graph matching is highly accurate in molecular graph matching (see Appendix D.5). The details of the algorithm deseribed in Ap- pendix D.4 We utilized the graph matching algorithm for every reciprocal bridge construction and likelihood computation.
Recall that the SB problem could be interpreted to the EOT problem, where the cost function cor- responds to the NLL. Thus, defining the reference process can be interpreted as defining distance (cost) on the set of graphs. Interestingly, we found that the likelihood of optimal permutation is interpreted as the graph edit distance (see Appendix D.6). This leads to the conclusion that the SB problem, with the Q as Equation (9). is analogous to an OT problem over the metric space of graphs equipped with graph edit distance (GED) as metric, where the GED computation is well known to be Na-hard problem.
5 RESULTS AND DISCUSSIONS
Here, we demonstrate the effectiveness of the Discrete Diffusion Schrödinger Bridge Matching (DDSBM) framework on graph transformation tasks. Specifically, we apply DDSBM to chem- ical domain, where the graph transformation task nontrivial due to additional constraints imposed by molecular graphs and their associated properties. We conducted experiments on two different molecule datasets: ZINC250K (Kusner et al., 2017) and Polymer (St. John et al. 2019). Through- out this section, we first elaborate on the common experimental setups and metries for evaluation. The second and third sections provide a detailed analysis of ZINC250K and Polymer experiments. Also, we discuss ablation studies for graph matching algorithms and the initial data coupling method to analyze their effects on the overall performance of DDSBM and the convergence of the Iterative Markovian Fitting (IMF) iteration (see Appendix F.2). Furthermore, for readers who might be inter- ested in the performance of DDSBM on unconditional graph generation tasks, i.e. synthetic graph data such as Community-209 Planar, or the small molecule graph dataset, QM9, we present the DDSBM results for them in Appendix G
5.1 EXPERIMENTAL SETUP AND METRICS
Experimental Setup. To train the models on graph transformation problems, an initial coupling between two distributions is necessary. We randomly coupled the data of initial and terminal distri- butions to obtain paired data. The molecular pairs are divided into training and test datasets in a ratio of 8:2. All the following reported values are average of three independent training runs with differ- ent random seeds. For standard deviation, please refer to Appendix Also, detailed explanations about model architectures and hyperparameters can be found in Appendix
Metries. By definition of SB shown in Equation (I) both joint and marginal distributions at each side must be examined to assess the degree to which the SB has been successfully achieved. We eval- uate these distributions from two perspectives: graph structural properties and molecular properties. Analysis on graph structural properties examines whether our model could capture the data-intrinsie features and the optimality of transporting between given data distributions. Since the graph struc- tural features might exhibit weak correlation with the molecular properties, we also analyze the
8

---

Published as a conference paper at ICLR 2025
Table 1: Distribution shift performance on ZINC. Reference refers to metrics from the initial coupling, used as a standard to evaluate each model's graph translation. For both AtomG2G and HierG2G, we've excluded the generated molecules that are too large with more atoms than the maximum number of atoms in our dataset for computing metrics other than validity, 1 and & denote higher and lower values are better, respectively. The best performance highlighted in bold.
Model
Type
val(()
Unight)
Nowift:
NLLA)
NSPDK(L)
Logp Wi(4:
QED MAIX))
SAscore MAD())
PCD(
Reference!
360.862
1.47c4
2.007
0.153
0.595
4,807
/0.279
AtomCi26i
Latent
99.9
64.4
9.70e-1
0.162
5.199
HierG2G
Latent
100.0
73.7
99.5
344.458
2.10e-2
0.113
0.146
0
5.742
DBM
Bridge
87.6
100.0
100.0
288.572
8.04c44
0.150
0.141
0.60K
1.46
DDSBM
Schnodinger Bridge
94.8
100.0
99.9
160.461
7,30x-4
0.139
0.120
0.402
0,833
NLL, Wi, and MADs were calcutioed esing radeom parss from the lest set, Two PCD values are proviced: the trxt comppares the ininal molecales is the test set with the tenmizal modocalos in the trsining sch, and the snarad compars the tumiizal moleculao in both scts. Ales, the refercnas NSPDK compated with the lomiinal mutoaales frems training and lod acts
molecular properties to validate the effectiveness of the DDSBM framework on the molecular opti- mization tasks. Besides the basic metrics for molecular generative models-validiy, (Val.), unique- ness (Uniq.). and novelty (Nov.> we evaluate molecular properties with Wasserstein- I distance (W1) and Fréchet ChemNet Distance (FCD). On ZINC250K, mean absolute differences (MAD) of drug-likeness (QED), and synthetic accessibility (SAscore) are also evaluated. For graph structural properties, we analyze negative log-likeling likelihood (NLL) and neighborhood subgraph pairwise distance kernel (NSPDK). More details about the metrics are explained in Appendix E.4
5.2 SMALL MOLECULE TRANSFORMATION
First, validate our proposed methods on the SB problem between two molecule distributions constructed from the standard ZINC250K dataset. We constructed two sets of molecules whose log P values are largely different. Molecules from the ZINC250K dataset were randomly selected and divided into two sets whose log P values follow the Gaussian distributions centered at and with variance of 0.5, respectively (see Appendix [E.2] for more details). We compared methods with three baseline models that perform graph-to-grap translation. AtomG2G and HierG2G are latent-based models that encode an input graph into latent vector and decode it into another graph JJi et al. 2020). Diffusion Bridge Model (DBM) is a bridge model trained with the same refer- ence process as DDSBM, which is equivalent to the first Markov projection in DDSBM. We refer readers to Appendix F..3 for more details about the baselines and implementation of our models. We note that, for these three baseline models, the initial coupling utilized during the whole training procedure without change, while DDSBM dynamically alters the training data pair by IMF.
Table D shows overall results of our method compared to the three baseline models. DDSBM con- sistently outperforms the other models in terms of both NSPDK, NLL, and FCD. The lower NSPDK and FCD suggest that while the minimal NLL indicates that DDSBM applies minimal structural change on initial graphs. This result demonstrates that DDSBM achieves more optimal graph transformation between fixed initial and terminal distributions. When it comes to the model type, bridge models shows superior in FCD, NI.., and NSPDK, compared to the latent-based models. The bridge models, DBM and DDSBM, dynamically transform a graph based on the reference dynamics, favoring the retention of the given structure, whereas whole-graph reconstruction using latent vector does not. This leads to lower NLL values for the bridge models, which ensured by the Definition 3.2 Additionally, the lower NSPDK and FCD values of the bridge models highlight that constructing dynamic bridge within the graph domain enhances the performance of distribution learning for the target distribu- tion. The latent models have a higher validity, but given that their uniqueness is significantly lower compared to the bridge models, which achieve 100% uniqueness, the bridge models are better suited for tasks that require distinct and diverse molecule generation. Furthermore, we attribute the best performance of DDSBM to the gradual updating of training pairs, which become more similar than the random initial pairs, simplifying the graph transportation process.
molecules are more similar to those the target dataset,
Next, we analyze the molecular properties of the source and generated molecules. DDSBM resulted in the lowest MAD in QED and SAscore, meaning the deviation of molecular properties other than log P is the smallest for DDSBM. It is noteworthy that DDSBM achieves minimal changes in various molecular properties despite being trained solely optimize graph transformations with minimal

---

Published as a conference paper at ICLR 2025
structural alterations, without explicit knowledge on molecular properties. Meanwhile, the latent- based models exhibited larger MAD values in QED and SAscore, indicating that they are vulnerable to losing other properties of the initial molccules. This can be inferred from the result of HierG2G; although HierG2G achieves the lowest W1 value in log P so that it modulates log P the best to the desired degree, its much larger NLL. value suggests that it could generate graph with less consideration of the initial graph constraint, as illustrated in Figure [4] For a better understanding of the overall results, we provide the corresponding distributions of properties of the models in Figure T0
Despite the promising results, we observe that all models except DDSBM have a high reliance on a predefined initial coupling. Thus, we conducted additional experiments using pseudo-optimal initial coupling based on Tanimoto similarity, which is detailed in Appendix F.2.2 Interestingly, we found that introducing the pseudo-optimal initial coupling not only accelerated the training of DDSBM in practice but also allowed it to achieve performance on par with the previous results.
5.3 POLYMER GRAPH TRANSFORMATION
The Polymer dataset (St. John et al. 2019) consists of 91,000 monomer molecules with their optical excitation energies (GAPs) obtained by time-dependent density functional theory calculations. We reconstructed the Polymer dataset for a transport problem between two sets of molecules with dis- tinct GAPs, corresponding to green and blue optical colors, respectively. The reconstructed dataset contains 7,603 molecular pairs. This task is considered as a more challenging application because the relationship between the graph structure and the target GAP property is highly non-linear, mak- ing it hard to predict the effect of specific structural changes on the GAP. In this context, we apply our DDSBM model to find the optimal transformation between the two sets of molecules.
The performance of DDSBM is compared to DBM, which serves as a baseline. The GAPs of the molecules generated by the models were obtained using the pre-trained MolCLR model (Wang et al.) 2022). which has a mean absolute error (MAE) of 0.027 eV for the GAP prediction. Table shows the overall results of our method on the Polymer dataset. DDSBM outperforms DBM on most of the metries evaluated, which is consistent with the results of the experiments on ZINC In terms of validity. DBM shows significantly lower scores, which contrasts with the results observed on the ZINC250K dataset. This can be attributed to the characteristics of the molecules in the Polymer dataset, which have relatively large sizes and multiple ring structures. In this context, minimal transformations are advantageous for achieving high validity, and DBM may have struggled to learn these changes from the randomly paired data. Examples of the generated molecular graphs are visualized in Figure 15
Table 2: Distribution shift performance on Polymer. Reference refers metrics from the initial coupling, used as a standard to evaluate each model's 's graph translation. 1 and + denote higher and lower values are better, respectively. The best performance is highlighted bold.
Model
Type
Val(())
Uniq.(1)
Now.(f)
FCD(L)
NLJI(L)
NSPDK(.)
GAP (L)
Reference!
1.469 0.384
749.800
5.64e
0.312
DBM
Bridge
43.4
99.8
97.4
2,230
580.415
5.820-3
0.249
DDSBM
Schrödinger Bridge
97.4
94.3
1,074
212.047
4.18c-3
0.127
NB2 and Wis som ralottadd sding medden pains from the and on. Two PCD valaes ar prstiiet the fire compone the inmii medecrles tot with the temitaa miiiing compore mobaeske
compandd with modocalts toiniin
DISCUSSION
In this paper, we propose Discrete Diffusion Schrödinger Bridge Matching (DDSBM), a novel framework utilizing continuous-time Markov chains to solve the SB problem in high-dimensional discrete state space. To this end, we extend Iterative Markovian Fitting (IMF), proving its conver- gence to SB. We successfully apply our framework to graph transformation, specifically for molec- ular optimization. Experimental results demonstrate that DDSBM effectively transforms molecules to achieve the desired property with minimal graph transformation, while retaining other features. However, the IMF requires iterative sampling from the learned Markov process, which can be more computationally intensive than simple bridge matching.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by the Korea Environmental Industry and Technology Institute (Grant No. RS202300219144 the Technology Innovation Program funded by the Ministry of Trade, Industry & Energy. MOTIE, Korea (Grant No. 20016007), and Basic Science Research Programs through the National Research Foundation of Korea funded by the Ministry of Science and ICT (Grant No. RS-2023-00257479, Grant No. 2018R A5A 1025208 and Grant No. NRF-2022M33JA 1063021).
REFERENCES
Kurt M Anstreicher. Recent advances in the solution of quadratic assignment problems. Mathemat- ical Progranming, 97:27-42, 2003.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:1 7981-17993, 2021.
G Richard Bickerton, Gaia V Paolini, Jérémy Besnard, Sorel Muresan, and Andrew L Hopkins. Quantifying the chemical beauty of drugs. Nature chemistry, 4(2):90-98, 2012.
Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, 2013.
Sébastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzere, and Mario Vento. A quadratic assignment formulation of the graph edit distance. arXiv preprint 1512.005 2015.
Jean-René Chazottes, Cristian Giardina, and Frank Redig. Relative entropy and waiting times for continuous-time markov processes. 2006.
Ziqi Chen, Martin Renqiang Min, Srinivasan Parthasarathy, and Xia Ning. deep generative model for molecule optimization via one fragment modification. Nature machine intelligence, 3(12): 1040-1049, 2021.
Minsu Cho. Jian Sun, Olivier Duchenne, and Jean Ponce. Finding matches in haystack: A max- pooling strategy for graph matching in the presence of outliers. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2083-2090, 2014.
Shui-Nee Chow, Wuchen Li, Chenchen Mou, and Haomin Zhou. A discrete schrodinger bridge problem via optimal transport graphs. calculus of variations, 20(33):34, 2021.
Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In Pro- ceedings of the 27th International Conference International Conference Muchine Learning, pp. 255-262, 2010.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
Valentin De Bortoli, James Thornton, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications to score-based generative modeling. Advances in Neural Information Processing Systems, 34:17695-1777 2021.
Xuanzhao Dong, Vamsi Krishna Vasa, Wenhui Zhu, Peijie Qiu, Xiwen Chen, Yi Su, Yujian Xiong. Zhangsihao Yang, Yanxi Chen, and Yalin Wang. Cunsb-rfie: Context-aware unpaired neural (c) (o) dinger bridge in retinal fundus image enhancement. arXiv preprint 1XXi:24499.00666, 2024.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks graphs. arXiv preprini arXiv:2012.09699, 2020.
Peter Ertl and Ansgar Schuffenhauer. Estimation of synthetic accessibility score of drug dike molecules based on molecular complexity and fragment contributions. Journal of cheminfor- matics, 1:1-11, 11 2009.
11

---

Published as a conference paper at ICLR 2025
Stewart N Ethier and Thomas G Kurtz. Markov processes: characterization and convergence. John Wiley & Sons, 2009.
Paul C Gilmore. Optimal and suboptimal algorithms for the quadratic assignment problem. Journal of the society for industrial and applied mathematics, 10(2):305 -33, 1962.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
Ilia Igashov, Arne Schneuing, Marwin Segler, Michael Bronstein, and Bruno Correia. Retrobridge: Modeling retrosynthesis with markov bridges. arXiv preprint (ntn:2308.112222 2023.
Benton Jamison. Reciprocal processes. Zeitschrift für Wabrschheinlichkeissseeeri und Verwandte Gebiete, 30(1):65-86, 1974.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference machine learning, pp. 2323-2332. PMLR, 2018.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Hierarchical generation of molecular graphs using structural motifs. International conference on machine learning, pp. 4839-4848. PMLR, 2020.
Beomsu Kim, Gihyun Kwon, Kwanyoung Kim, and Jong Chul Ye. Unpaired image-to-image trans- lation via neural schr\ odinger bridge. arXiv preprint arXiv:2305. 15086, 2023.
Hyeongwoo Kim, Seokhyun Moon, Wonho Zhung, Jaechang Lim, and Woo Youn Kim. Deep- bioisostere: Discovering bioisosteres with deep learning for a fine control of multiple molecular properties. arXiv preprint arXiv:2403.02776, 2024a.
Seonghwan Kim, Jeheon Woo, and Woo Youn Kim. Diffusion-based generative ai for exploring transition states from 2d molecular graphs. Nature Communications, 15(1):341, 2024b.
Claude Kipnis and Claudio Landim. Scaling limits of interacting particle systems, volume 320. Springer Science Business Media, 2013.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Matt Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoen- coder. In International conference machine learning, pp. 1945-1954. PMLR, 2017.
Danyeong Lee, Dohoon Lee, Dongmin Bang, and Sun Kim. Disco: Diffusion schrödinger bridge for molecular conformer optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 38(12):13365-1337, March 2024. ISSN 2159-5399.
doi: 10. (1609/aaai.v38812.222..
Christian Léonard. survey of the schr " odinger problem and some its connections with optimal transport. arXiv preprint :00i:::300..2//1 2013.
Christian Léonard, Sylvie Rellyy and Jean-Claude Zambrini. Reciprocal processes. measure- theoretical point of view. 2014.
Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. In Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, volume 2, pp. 1482-1489. IEEE, 2005.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017.
Guan-Horn Liu, Tianrong Chen, Oswin So, and Evangelos Theodorou. Deep generalized schrödinger bridge. Advances in Neural Information Processing Systems, 35:9374-9336 93888, 2022.
Guan-Homg Liu, Arash Vahdat, De-An Huang, Evangelos A. Theodorou. Weili Nie, and Anima Anandkumar. Ss::: Image-to-image schrödinger bridge. arXiv preprint 2.8.0222000.08872. 2023.
12

---

Published as a conference paper at ICLR 2025
Xingchao Liu and Lemeng Wu. Learning diffusion bridges constrained domains. In international conference on learning representations (ICLR), 2023.
Eliane Maria Loiola, Nair Maria Maia De Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and Tania Querido. A survey for the quadratic assignment problem. European journal of operational research, (76(2)x657-690 2007.
Van Khoa Nguyen, Yoann Boget, Frantzeska Lavda, and Alexandros Kalousis. Glad: Improving latent graph generative modeling with simple quantization, 2024.
Matteo Pariset, Ya-Ping Hsieh, Charlotte Bunne, Andreas Krause, and Valentin De Bortoli. Unbal- anced diffusion schr\" " odinger bridge. arXiv preprint arXiv:2306.09099, 2023.
Stefano Peluchetti. Diffusion bridge mixture transports, schrödinger bridge problems and generative modeling. Journal of Machine Learning Research, 24 2023a.
Stefano Peluchetti.
Non-denoising forward-time diffusions. arXiv preprint arXiv:2312.14589,
2023b.
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Gunter Klambauer.
Fréchet chemnet distance: metric for generative models for molecules in drug discovery. Journal of chemical information and modeling, 58(9):1736-1444 2018.
Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM
(JACM), 23(3):555-565, 1976.
Alberto Sanfeliu and King-Sun Fu. distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics, (3):353-362, 1983.
Erwin Schrödinger. Sur théorie relativiste de l'électron et l'interprétation de la mécanique quan- tique. In Annales de I' l'institut Henri Poincaré, volume 2, pp. 269-310, 1932.
Yuyang Shi, Valentin De Bortoli, Andrew Campbell, and Arnaud Doucet. Diffusion schrödinger bridge matching. Advances in Neural Information Processing Systems, 36, 2024.
Richard Sinkhorn. Diagonal equivalence to matrices with prescribed row and column sums. The American Mathematical Monthly, 74(4)-402-405, 1967.
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learn- ing, pp. 2256-2265. PMLR, 2015.
Vignesh Ram Somnath, Mattco Pariset, Ya-Ping Hsich, Maria Rodriguez Martinez, Andreas Krause, and Charlotte Bunne. Aligned diffusion schrödinger bridges. arXiv preprint 1rxiv:2302.11419, 2023.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456 2020.
Peter C. St. John, Caleb Phillips, Travis W. Kemper, A. Nolan Wilson, Yanfei Guan, Michael E. Crowley, Mark R. Nimlos, and Ross E. Larsen. Message-passing neural networks for high- throughput polymer screening. The Journal of Chemical Physics, 150(23), June 2019, ISSN 1089-7690.
Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.1477 2022.
Cédric Villani. Optimal Transport. Springer Berlin Heidelberg, 2009. ISBN 9783540710509 doi: 10.1007/998 00.10079978-3-50--1005.00
13

---

Published as a conference paper at ICLR 2025
Runzhong Wang, Ziao Guo, Wenzheng Pan, Jiale Ma, Yikai Zhang, Nan Yang, Qi Liu, Longxuan Wei, Hanxue Zhang, Chang Liu, et al. Pygmtools: python graph matching toolkit. Journal of Machine Learning Research, 25:1-7,2024
Yuyang Wang, Jianren Wang, Zhonglin Cao, and Amir Barati Farimani. Molecular contrastive learning of representations via graph neural networks. Nature Machine Intelligence, 4(3):279~ 287. 2022.
Peter Willett, John M Barnard, and Geoffrey Downs. Chemical similarity searching. Journal of chemical information and computer sciences, 38(6):9839996, 1998.
Yong Xia. Gilmore-lawler bound of quadratic assignment problem. Frontiers of Mathematics in China, 3:109-118, 2008.
Dongchao Yang, Jianwei Yu, Helin Wang, Wen Wang, Chao Weng, Yuexian Zou, and Dong Yu. Diffsound: Discrete diffusion model for text-to-sound generation. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 31:1720-1733, 2023.
Linqi Zhou, Aaron Lou, Samar Khanna, and Stefano Ermon. Denoising diffusion bridge models. arXiv preprint arXiv:2309. /6948, 2023.
14

---

Published as a conference paper at ICLR 2025
A INTROUDCTION TO SCHRÖDINGER BRIDGE
In this section, we will begin with thought experiment to briefly understand the Schrödinger Bridge problem (SBP), followed by simple toy example in continuous space. Specifically, we will focus on intuitively understanding how the Iterative Markovian Fitting (IMF) method works through toy example. Building on this, we aim to gain insight into the Schrödinger bridge problem and explore its application in discrete spaces.
A.1
THE LAZY GAS EXPERIMENT AND THE SCHRÖDINGER BRIDGE PROBLEM
How do gas particles move?
t=0
t=t
Figure 2: A schematic illustration of the lazy gas experiment
Imagine a gas, collection of non-interacting particles confined to a specific region of space. At time 0, these particles are distributed according given distribution. By time T, the gas must reorganize itself to match different distribution.
a. Busy Gas
t=0
1=t
b. Lazy Gas
t=0
Figure 3: A schematic comparison between lazy gas and busy gas
Busy gas will find a way to perform the given transition regardless of the amount of work required. In contrast, lazy gas will seek make the transition while minimizing the total work, following the principle of least action. This simple yet proooigp scenario, known as the lazy gas experi- SBP. Proposed by Erwin Schrödinger,
ment, provides an intuitive starting point for understanding the SBP seeks to identify the most natural probabilistic process that connects two probability distri- butions under certain constraints. At its core, the problem is to find a probabilistic interpolation that minimizes the cost.
In essence, the SBP addresses the following question: Given the initial and final distributions of stochastic process, what is the optimal way to probabilistically interpolate between these two distributions? This process must satisfy two important principles. First, the process must exactly match the given initial and final distributions (boundary condition). Second, it must minimize some
15

---

Published as a conference paper at ICLR 2025
properly defined cost. This cost is typically defined as the Kullback-Leible (KL) divergence with respect to a reference process representing the underlying dynamics.
In the example of the lazy gas experiment, if the gas particles moving according to the reversible Brownian motion (a Wiener process with zero drift), the cost can be defined as the total distance traveled by the partieles. This principle of cost minimization ensures that the particles follow the optimal paths that most efficiently (in terms of L norm) connect the initial and final distributions. This analogy intuitively captures the essence of the SBP's goal: achieve a natural and efficient transition between given marginal distribution.
A.2 SCHRÖDINGER BRIDGE WITH TOY EXAMPLE IN CONTINUOUS SPACE
To better understand the SBP in real-world context, consider simple toy example involving prob- abilistic transitions between two probability distributions in a mee-iimeniional continuous space. Here, we use reversible Brownian motion the reference process. This example allows us con- trast the optimal transition process (Schrödinger bridge) between the initial and final distributions with inefficient, suboptimal one. By visualizing these differences, standing of the SBP. In particular, this example illustrates how the central goal of the problem minimizing costs is achieved in practice by reducing the Kullback-Leibler (KL) divergence rela- tive to the reference process.
gain intuitive under-
Schrödinger Bridge
Arbitrary Bridge
t=0
1=T
Figure A schematic comparison between Schrödinger bridge and aribtrary bridge
In Figure 4 the trajectory labeled Schrödinger Bridge on the left represents the optimal probabilistic path connecting the two distributions. These paths are carefully structured not only to satisfy the given boundary condition, but also to adhere to optimal cost, achieving balance between efficiency and regularity. On the right, the trajectories labeled Arbitrary Bridge illustrate suboptimal transport process. While the boundary condition still satisfied, the intermediate paths are not optimal for the given cost. In this context, the cost, defined by the L norm, highlights the differences in the distances traveled by each point. As shown in the figure, the movements the optimal paths are significantly more efficient compared to those in the arbitrary paths.
Considering these differences, the next question is: how can the Schrödinger Bridge be found in practice?
A.3 SOLVING SCHRÖDINGER BRIDGE PROBLEM IN CONTINUOUS SPACE
Since the SBP does not admit closed-form solution, iterative algorithms such Iterative Propor- tional Fitting (IPF) and Iterative Markovian Fitting (IMF) are used to approximate it. Both methods adopt the Markovian projection for a given stochastic process minimize the KL divergence.
IPF algorithm iteratively fits their marginal distribution to the given distribution, while preserving the reciprocal class and Markovian properties of the given process. In contrast, IMF method alternates between reciprocal projection and Markovian projection to refine the process while keeping the marginal distributions fixed.
'The experiments presented in this section are based informed by [.conard 2013).
Villani 2009), with the associated explanations
16

---

Published as a conference paper at ICLR 2025
IPF
P(T,)
IPF
IPF
IMF
P(T,3)
IMF"!
IME#
Ap
P(.E)
IPF
IPF
PSB
Figure 5: A schematic comparison between Iterative Proportional Fitting (IPF) and Iterative Marko- vian Fitting (IMF) method. The image are reproduced based on Peluchetti (2023a). In the notation, P(T,-) represents the collection of path measures where only the initial distribution is fixed at I', P(..)) represents the collection of path measures where only the terminal distribution is fixed at E, and P(T, E) represents the collection of path measures where both the initial and terminal distribu- tions are fixed at and E, respectively.
At this point, reciprocal projection is the process of constructing mixture bridge using the refer- ence process and Doob's ' h-transform based on the given joint distribution. Markovian projection, on the other hand, is performed by generative modeling with neural networks produce Markov process similar to the given one in terms of the KI. divergence. In practice, training occurs dur- ing the Markovian projection phase, which plays the same role as bridge matching in refining the probabilistic process.
In this section, we will focus on IMF since is the main reference method for our DDSBM frame- work. We will explore the interchange between the two projections and the principles by which they work together refine the given process.
First, when reversible Brownian motion is given as the reference process in one dimensional contin- uous space, our goal is find the Schrödinger bridge between the marginal distributions. We start by obtaining the initial coupling between the marginal distributions. For visualization purposes, we assume an initial joint distribution which points opposite in space are coupled.
Next, we use reciprocal projection to construct reciprocal mixture bridge connecting the marginal distributions (Figure (a). While this bridge has reciprocal property, the Markov property is generally lost. Moreover, it shows significant differences from the joint distribution of the SB, which resembles the left side of Figure
We then apply Markov projection to this mixture bridge to derive the Markov process that is closest in terms of KL divergence (Figure(pp) (b)) The obtained process reduces the KL divergence compared to the previous process, bringing it closer to the Schrödinger bridge (see Figure 5). In addition, the joint distribution becomes more similar to the SB joint distribution than the initial coupling. as reflected by the reduced cost.
By iteratively repeating this process, the obtained Markov process converges to the Schrödinger bridge, as guaranteed by the convergence theorem (Shi al. 2024 Peluchetti 2023a). Through IMF iterations, we progressively refine the process, eventually arriving at the Schrödinger bridge (Figure (c).
A.4 SCHRÖDINGER BRIDGE PROBLEM IN DISCRETE SPACE
So far, have described the SBP in the context of continuous space. Since the Wiener process used in continuous space cannot reflect the characteristics of discrete space well, we need to introduce a new diffusion process solve SBP in discrete space.
17

---

Published as a conference paper at ICLR 2025
Reciprocal Projection A
Initial Joint
Reciprocal Mixture Bridge
b. Markovian Projection Ad
New Joint
Markov Approximation
Markovian Projection 1h pso
Figure 6: A schematic illustration Iterative Markovian Fitting method.
Discrete Diffusion Process
b
transition
if
b a
transition
Bridge
b
a
Schnodingar Bridge
b
b
a
Figure 7: A schematic illustration of the discrete diffusion process and a comparison between the initial bridge and the Schrödinger bridge
Let us consider discrete random variables with three categories (a. b, c). In this context, we can adopt the discrete diffusion process proposed in Austin et al. (202T). such as the uniform transition process. Unlike processes where all information about state is lost (a- = 0), we define discrete diffusion process that retains partial information about its initial state (ā, * 0). This approach is visualized Figure 4. highlighting the retained structure.
In the case of continuous space, the cost is typically represented by the L norm. In discrete space, however, the cost can be thought as the dissimilarity between discrete states. Thus, minimizing the L norm in the continuous space is equivalent to minimizing the negative log-likelihood (NLL) of the joint distribution in the discrete state space, given by the reference diffusion process we used. The a, be interpreted parameter that indicates how much of the original structure is retained
18

---

Published as a conference paper at ICLR 2025
during the diffusion process. If the original discrete diffusion process (ä, 0) is used, the NLL assigns the same value to all pairs, making it impossible to define the SBP.
By solving the SBP using our DDSBM framework. it is possible to refine from initial non- optimal coupling to the optimal coupling, i.c. the Schrödinger bridge, from the perspective of NLL. be understood finding the coupling that
As shown in Figure 7 and Figure 7 this procedure best preserves the current state. This insight is a major reason for introducing DDSBM into graph domains, especially for molecular optimization.
Figure illustrates the initial bridge and the Schrödinger bridge in the graph domain. The initial bridge shows non-optimal coupling between two graphs, where the structural consistency is not well preserved. In contrast, the Schrödinger bridge shows an optimal coupling that preserves the core structure of the graph while transforming to the target graph, reflecting the principle of minimal change.
Initial Bridge
Schrödinger Bridge
Figure 8: schematic comparison between the initial bridge and the Schrödinger Bridge in graph domain
B PROPOSITIONS AND PROOF
B.1 NOTATIONS
In this section, we introduce the notations that will be used throughout the proofs of the propositions. Ω = D(00, r). X) denotes the space of all left-limited and right-continuou (cådlàg) paths over finite space X. We assume state space has connected finite graph structure (fully-connected graph), which imply it becomes metric space with graph distance metric dx(.,)). Accordingly, the sample space Ω is equipped with Skorokhod topology with Skorokhod metric dg(:;)) -), and associated Borel olagebbra. X = (Xr) denotes the canonical process given by:
X,(w) = Wey te [0. w (w.)
The reference measure Q is an irreducible Markov measure on S with its associated canonical filtration. Assume that the transition probability of Q denoted by Pase y), from (s, [0, r| x to (t,y) E [0, r] x X, is continuous and differentiable over time. The measure is generated by the transition rate function A, (2, y), which gives the rate of transition from X to y X' time
19

---

Published as a conference paper at ICLR 2025
E (0. and satisfies the Kolmogorov forward equation:
0P (P..(
Σ
(a. 2),((z.)).
(16)
Ot
=E
aa y)
(z
t=
We also assume that Q can construct a bridge Q0 H, Xx y) for all v,y E X. For any Markov measure M, the corresponding generator is denoted as A (M).
B.2 THEOREM B.1
Theorem B.1. (Uniqueness of the Schrödinger Bridge Solution) the reference process Qs Markov, then under mild conditions the Schrödinger Bridge solution pasa exists and is unique. Furthermore, the solution is mixture with static Schrödinger Bridge solution represented as T TPSB Q 10,r E ERR(Q), and also is in M. Conversely, process IP = Po, Po 10, Markov if and only if pSB
Proof. This direct consequence of Theorem 2.12 of (Léonard] 2013).
B.3 MARKOV PROJECTION
Proposition B.2, (solution of Markov projection)
Let M (A),)) A E R(Q)) and the generator of Q be Ae(x,)) v) with transition probability
Psa(2, y). Under mild assumptions, the generator of the Markov measure M becomes
A (Xesy) = -Barie A(( X²)
X
x
Po: (y) 2) Po:t (x,,
Per (u, Per (x. 2)
A1(x,112)= Ac(o, v)
8zy Σ Acly, u)
where E X.
The reverse KL-divergence is
A (Aa)
(xl(A))M") = S( Es..
Σ
A (A1a)
log
(ee, v) de,
A (M))
V#X,
where the Ao is the generator for the conditioned measure o which is defined as
A Aoo (X,,)) = =EA, 10.1
Moreover, for any I E [0,7],A, = M,-
B.3.1
KL-DIVERGENCE OF MARKOV MEASURE
Consider two Markov path measure M < M. Based on the Girsanov's formula, we can express the Radon-Nikodym derivative follow:
d.M (w)
d.Mo (wa) exp (J.
['oog
AM (wi wi wi)dN((w) [ (AA A (ws, ) AM
d.
dMo
where N. (w) the number of jumps of the path w up to time and w; the left limit of the path at time Note that, due to the compactness of time interval, the number of jumps of each path in
See Chazottes al. 2006) Appendix of Kipnis & Landim 2013
20

---

Published as a conference paper at ICLR 2025
Ω is at most finite, and thus No (w) is bounded. Also, the escape rate of the state associated to M -A, (z, Thus, we can construct a natural martingale
N₂ L As(ws, ws)ds
which is zero-mean process.
For any continuous and bounded function Φ - R, we can change the integrator dN, as follow:
EM J (Ws))dN EM I./ (bww)w A (Wa)
Eg- [-0(x)A (xc x)] ds.
The KL-divergence expectation of logarithm of Kadon-Nikodye derivative, which leads
Jo log A.
A. (k)-:())) + [- (A A (wrs wi)dt
DxL (M) (Ko + Eas
(Mo !'" ERNM
AA (x,x) Σ Pa Pa log
A. (z, v)
ds
A
S Be.... [A42 (A" ds,
where (2, y) the probability of jump from x to y given that a jump occurs, which is A (2.w)
-A
By applying this, we obtain KL-divergence represented solely in terms of transition rate A M n
and
DEL (M) (Mu L Een,, Ms
AM Σ AM (z, y) log (2.1) (AM AM x) ds.
A
(17)
B.3.2 KL- KLEDIVERGENCE OF RECIPROCAL MEASURE TO MARKOV MEASURE
Lemma B.3, If reciprocal measure E R(Q) is conditioned on Xo being a.s. constant, then the corresponding measure A.jo is Markov. For any M M such that Mu Ao and A < M, the KL-divergence (xI(A])) disintegrates as follow:
DRl(A| EA, (oll
Proof. According to proposition 2.5 of Léonard et al. (2014) and lemma 1.4 of Jamison (197)). conditioning on X₂ not only preserves its reciprocal property, but also transforms into a Markov process. Due to the absolute continuity together with | < oo, the KL-divergence is finite. Then, the KL-divergence can be reformulated as follows:
dA
(RL(A| = EAA
dM
dAA 10
= EAA
d.M.jo. to
dA. 0
EA EA,0
dMM 10
EAD M.
while reciprocal measure A R(Q) is in general non-Markov, the conditional measure A.jo is Markov. Note that we can compute the KL-divergence between two Markov measure based on Equation
According Lemma B.3
See Lemma 5.1 of Kipnis & Landim 2013
21

---

Published as a conference paper at ICLR 2025
B.3.3 GENERATOR OF CONDITIONED PROCESS
To compute DKL(A (AllM) based on Lemma B.3 Equation 17 we need the generator of the condi- tioned process j.jo. Before deriving the generator of A.o. we first consider the pinned process of Q conditioned on X- 2 in prior.
Lemma B.4. Let (X))osisT be Markov process under the reference measure Q with transition probability P. () ( t). and generator A,(:,)). ). Consider the process conditioned on X, with corresponding measure denoted by Q((e) Then, the conditioned process is also Markov, and its generator is given by:
Pa: (1,2) Per (Ir,z)
As u) Pair (u,2)
(Z, Ao 1)
8ay
Poir (1,z2)
Proof. The conditional probability of X, given the natural filtration Fu and Xs with u S8515T under the measure ()(2) is as follows:
(X = y|_,, = F.) = Q(x, = y|X, = I, 2,
Q(X, y|x,, =I,X,
(:00EM)
= (X, = -m|xx= =
which confirms ((+) is Markov.
Next, the transition probability of ((#), denoted by (2: y; 2), is derived as:
Parl vi = y|X. - x),
Q(X, = =2|X, = y) Q(X, = 2|X,, = x)
=Q(X, = y|X,= =
Pe:( 8) Pe: (2,
Pei (2,
Note that, we assumed the measure Q construct bridge everywhere, the probability ratio has finite value.
Finally, the corresponding generator A, (I, yi 2) is obtained using the Kolmogorov forward equation:
θ 01 Pa. (2, (2, z)
t=s
As(x, v) Pa.r (1)
Ox.x((Us+ Pa: (x,, 2)
+ 8ay
Psr (I,
As(x v) Ps.r (J,
Ps. (1,2)
8ay
Σ As(x, u)
Ps.r (I,
Po: (x,2)
We now consider the transition probability and generator of conditioned measure A. of A E R(Q).
Lemma B.5. For reciprocal measure A E RRQ)), the conditioned process with X, Do is denoted by A A.j0=z-- The generator of A..0==a is given by the conditional expectation:
A A jo=o
(I. y) EZ~A,,... [A, y: x) = Fu, X, = x²]
where As 2) is the generator of the conditioned process of Q with X, =
Proof. We denote the transition probability conditioned on Xo Do by paioo which is com- puted follows:
s:t
A 1-=0 (I. = / A. A. (X, =| 10 (X, - x, X, =2)dz.
sct
22

---

Published as a conference paper at ICLR 2025
The first term in the integrand is
10m2o (X, 2|X, 2)
A(X, 2|X0 Iu. X x),
A(X, 2 zo))((x = =x = 20. X, 2)
A(X, = x z|_o = =xo)
(2;300
Po:o (TO, x;2)
(0)
Vr (2;
Psi (1, Po:r (zo. 2)
Po:s (ru, x)
Vo (z; zo)
Vr (2) us Fol
Pe: (1)
V. (o; 1,,
(2;
where va( (o)z)),, pa(:1 20) are the probability mass functions of Asja: Q.jo- respectively, with Xo To. Given the initial-terminal condition, A is equivalent to the reference Q based on the definition of reciprocal class Definition 3.1 Similarly, the second term is same as Q(X, X| zo, X, x, X, 2), which can be expressed as Pa:e (2, y: 2) due to the Markov property of Q Therefore, the transition probability is:
2x (23 dz. (o P Poo(er / Pur(us Va (1;
P PA (Λ,4)
Me (2; xo)
Accordingly, the generator is derived as:
A 10-x0
(x,z) O.P 100000 (z. y)
1=8
Mo (2( 2a)
(=(2; vo) dz
O.Postt (2, v)
Per (2)
vs (2;; mo)
(2; x0) Vr (2; dz,
1=0
(e(2;; xX)
Past (x, 11)
OpPer(U,
(, (0)
1=s M (z; 200
Mo 2o)
1/ (21DD) dz
(Z, v)
(1)
(2 xo)
Me (2; 20)
6ay Me (2( x0)
[As(U, u) u (s: 2) Σ
V/ (2) x0) de, Me (2: xpp)
V. v1 Fo)
x u
(1;
vr xo) dz, M-(2; 20)
A, A, B)
Pa.r Pa.r (y. - 8uy Σ A.(y, u)
x U. (z) Øo)
Mr (2;
Mo (1;
Po.r (I, 2) (I, yi 2)22,
Me (2; (=(20
x Aj((x, =|X, x:) A, (3r y/3 2)dz,
EZ-A- -.. [A. ys I) No, X, =]]
In conclusion, the generator of 1 is given as the conditional expectation,
A (z. y) EA, Xx) X, z].
B.3.4 MARGINAL DISTRIBUTION OF MIXTURE OF MARKOV CHAANNS A reciprocal process A E R(Q) can be represented mixture of Markov chains as:
A(-)
Σ Q(11x x, X, No (2., v))
2,9
We here propose the mixture representation of Markov chain similar to theorem of Peluchetti 2023b) which describing mixture of diffusion process over Fuclidean space.
23

---

Published as a conference paper at ICLR 2025
Proposition B.6. Consider a famity of Markov measures Ω indexed by I
O,P v) Σ Par (z, (2,
(x) 0, (r.
t=
where P and A" is the transition probability and generator for each measure associated to the process X (Xx)eel)
here assume that A is finite for every u. Let the corresponding Markov measure be M and Pi be the density of My, the marginal distribution of Xy. Let mixture of M with the index distribution U over be
AC) J- ()du))
We denote mixture marginal density pe and mixture initial distribution Ag as:
pe(-) [ p p-))dd)
No(-) = [ M..))
Let X (X))e(oor) be another Markov chain generated by:
0 0,Ps:(I.3)
Σ (2.(22))A((2..)))
Ar v) = Me(x) J ()(
Xo ~ Ao-
Then, the marginal density of X2 uu. is assumed that exchange of 0₂ and (dd( is justified.
Proof. We start from verifying Ac(a, v) admits conditions of transition rate function. For A y is trivial that Ag (z, y) is finite and non-negative. Also, Eyex Ac(a, y) becomes zeros for all æ and t as:
me( / A7(r,)))((())((an)
Σ Ax = Σ VEX
BEX
1 (x(x)
/ Σ ((
yEX
Thus, mixture of generators Ar y) holds the condition for generator of Markov measures. Next, for E (0,
0xp((x)= = 02 [ (()))(ddu),
/ (x)
(assumption)
f E Al
Kolmogorov equation)
VEX
(L AN(
VEX
Σ A(,,)))u()). VEN
The equality of the left-hand side and the final line corresponds to the Kolmogorov equation for the process X generated by A, This shows that μr is the marginal distribution of X,.
n
24

---

Published as a conference paper at ICLR 2025
B.3.5 MINIMIZER OF THE KL-DIVERGENCE
The Markov projection reciprocal process A, denoted (A), is a Markov process M* which minimizes the reverse KL-divergence DRL. (A.(A, M)) We here characterize M by specifying its gen- erator. While the generator A, of jo represented as a conditional expectation given Xo, X, as noted in Lemma BB5] that of the M is supposed to be represented as the conditional expectation A A- (Xt.v)
without Xo condition. The following lemma says that Asooe
is the generator.
Lemma B.7. Let the Markov projection of reciprocal process R(Q) be M (A). Then the generator of M is AQd (Xx.9) EAr, 3; X
Proof. Because Q is assumed to be able to construct bridge everywhere, A,( = -0 > (x(x,)) = Vx # y, E X, t (0,
We claim that the Markov measure M generated by AM v) EA,I [At(X,, y;X,)| x| with My = Ao is a.s. M We can re-formulate the generator as:
AM (X,,8) = Ex, (A, X.)]
= -EA( x (x,) A (x
Σ A(Xo X, =x Ix1 (x,,3 v:
Σ A(Xo = xx) ΣA(x = 2,1 = zo. (Xe,
= =
A(Xo xo =o)x:)A (Xt,1)),
EAoss (x,.)(
(18)
which conclude that it becomes conditional expectation of the generator of A Also, based on the Proposition B.6 the M2 = A, for all f.
Note that A (x, y) BAro. [A v. X Xo, X, zr). which implies AM (x. y) 0 = A, (x,y) v) of KL-divergence (All)). we can assume Mj Ag. Based on this, we want to show that
Vr * v, E X,t [0, r). Thus, A < M. Because M is the minimizer
DRL (AI DKL (A] O. Recall that Equation 17 where the KL-divergence formulated as
DKL (AIIM) = =f[" EAa.
A. AA110 (Xe,v) dt,
(A Noo - 1
(x),
(X,, Xt) + Σ
1 No log
A
V=
A A
E
Σ
A A.10 log
A
A.10 10
+ AM
(Xerv) dl
AM
X X.
f(t.A.
25

---

Published as a conference paper at ICLR 2025
Then, (A (AI(A) TU,A,M,
So Adt 0 by definition, where A f(t,A, Mr)
AM AM
A EAo.
Σ
AM AW
A
10 log
(Xx.
L
AM
EA, Aoie
Σ
A A.
AAe
A.10
log
(X,,
A
UUXX
A
EA. Σ EAgis
AN A
+AA log
(Xc.
A
X
Ea, Σ
A
A.
EsOI |A log
APr ) (X,,)),
A,M
(. E
A
EA. Σ
AM A AM log
(Xt.v),
( Equation 18
A.
V
AM
E..
Σ
AM
A + AM
log
(X,,
(: Mr = Ad)
A.
X
We can deduce that So Adi DRi(MM]|M') 2 0, which conclude that M = M
B.3.6 PROOF PROPOSITION B.2
Now we prove the proposition Proposition B.2 using above lemmas.
Proof. Proposition B.2
By the Lemma B.3 and Equation 17 the KL.-divergence of A any Markov measure M e M disintegrates as:
DKL (AIIM)
L. E.o.
(AM) X,)+
Σ A Aio log
A A.
Ao (X.:v)
dl,
VAN.
where the 1-110 is the generator of pinned process of A.jo stated by Lemma B.5
According to
Lemma B.7 the Markov measure M* generated by A, y) = EAA, [A, y: X,) X, = x) the
minimizer of (A][AA||MM for M e M.. In last, Proposition B.6 ensure the time marginals of A, M for all E [0, 7] are equivalent.
B.4 TIME-REVERSAL MARKOV PROJECTION
Proposition B.8. Let M = A A E R(Q) and the forward generator of Q be A,(a, y) with the transition probability Psa(x,y). Let X (X1) be the canonical process and Y (Yi)ee o.r) be the time reversal of X, where Ye X,-r- Under mild assumptions, the time-reversal generator of M becomes
AM (Y1, Eoje A, Vi
Ao(y, -.ePoity 2)
1=8
= v) Po:r-s
8zy Σ A Po--=(2z,1 Po.- (2,
Po---(2.23)
26

---

Published as a conference paper at ICLR 2025
where 2 E X, and (..:222) is the generator for the conditioned process of Y with Y,
The
reverse di-divereence
Adir AM (V,, x)) dt,
Ox((AIM))
EAr, (AAI EA.
AM )& YJ)+ + Σ A log
x
where the A is the time-reversal generator for the conditioned measure A which is defined
A (Y,, x) = Eagt.. A(Y,, Y,, Xo
Proof. Follow the proof of Proposition B.2
Note that the Markov measure is time-symmetric.
B.5 PROOF OF THEOREM
Proof. With iterative projection, we have sequence of measure A such that:
A (2n+1) (A(2))))))
A (2n+2) (l (A (2n+1)).
where ( E R(Q). Let (1(") = (2)) and (()) A (2n+1), We will omit the superscription (()) there no confusion.
Let P E M be Markov process generated by a generator A (xx y) < oo with initial distribution
My with the Kolmogorov forward equation. Assuming that DxL (II (P) < oo, then
dM
DKL (II P) - DKL (II M) = En
log
< oc,
dP
which implying the Radon-Nikodym derivative dM oo over the support of II. Then we will first show the equality:
dM
dM
En
log
=
EM
log
dP
dP
As 1l1 = Mo. it is sufficient to show
d.M.jo 10
d.M. 10 dIP .10
En
log
EM
log
dIP.
where
dM 10
/ log
AM AP (w)_,w))dN(( + (AM (we wat
log
(w)
dlP
is given from Appendix
B.3.1 Since 11 is Markov from Lemma B.3 with generator
U10 (z, v) En, i.. [Ae(,, y: Xx X, x). A
which is derived the Lemma B.5
Then,
AM A
En
log
(X X,)dN,
AM (Xt, v)dl
En
Σ
A Io log
A.
y
AM (Xe, y)
En
En [Ar(X,, yr X, Xo. Xz] log
Ap
X
log AM
Em
En (x
(X v).
A
X
27

---

Published as a conference paper at ICLR 2025
by the tower property of conditional expectation. From the Lemma B.7 and Proposition B.6 replace the En [Aa(XA yi X,) Xxx] as A, (X,,
En X,) log A A
En
(X,,
v)
AM (X yddl
En
Σ Xt
A log
Ap
A
EM
Σ XrX
A log
(X,, y)dt
A
where the last equation justified since II, M1 for all t E [0, The other term, So (A (Xe, dtt can be treated as the same way, which establishes the equality. From the result, we get DKL (P) DrL (II + DRL (M [PP). The equality is derived for other diffusion processes (Peluchetti 2023a; Shi et al. 2024, Liu & Wu 2023), but in this paper we extended to continuous
Markov chain with discrete state space case.
By letting P = pSn,, we get
DKL (1I[(SS)) 2 DKL (MilPSS))
the equality holds if and only IT = M. By the assumption DKL (A((0) < co, the sequence of KL--dieereence (DxL (A [[S)))) is non-increasing and bounded, which implies the KL- divergence converges. Thus,
lim DEL (II(m) DKL (M = lim DKL (n) (M(() = 0. 12+000
n-000
We here utilize Aldous' tightness criteria for showing the tightness of TSSB Since the state space is finite it is sufficient show the following: For any 0, there exists ō > 0 such that for all stopping time 4
pSB (Sx (dx((Xoo Xt) S
for arbitrary small r) > and 0 < 0 A<< f To check the criteria, we will show that the leaving rate of PSB is bounded. From the Lemma B.5 and Lemma B.7 we know the analytic form of the transition
rate Ar. Since Theorem B.1 ensure that the pSB Markov as well as in reciprocal class,
A (xr, x) = Espan [Ac( 2; X To, X. = =x],
Σ X-EX
p (X, |X, x. x, X, = 20)
p (X-IX, = x, Xo)
PSB
Σ ((z,
PE, Xx)
uext
Σ
PSB (X 1X, = (x,)
X-EX
PSB
(X, = Xo)
Σ A((z, A(z, uer
Pt. (I,
WEX
JSS
(X,IXX = xr, Xo)
= =A(xxx)) Σ
Σ
A(x, ur. (u, (x)
Per (x,
X.EX
wEX
dbSB 1.T
- Σ
(a, x,) Σ A(x, u) Per (u, Xx)
dQu,
N, E.
NEX
*See section 16 of Billingsley 2013) and section of Ethier & Kurtz 2009
28

---

Published as a conference paper at ICLR 2025
The Radon-Nikodie derivative is finite and positive for æ, such that psd (X, pS, =)) 0. Because the state space A' finite, there is finite upper bound dy for every possible pair (x, xz). Thus,
A (x, x) 2 Ae(x, x))
Σ
A(r, u) u) (M, X+)
X,EX
uEA
A((z,,) - Ut Σ A(I,u)
Σ
NEA
X,EX
= A(( 4t
Σ uEX
A(r,u),
= =A(
The leaving rate (x) of pss at x1) is bounded by that of Q, ca(a). Assuming the leaving rate of Q is uniformly bounded by c, ot is uniformly bounded by c. Back the Aldous' tightness criteria, by choosing 8 E/c we see that pSB is tight.
The sequence (II(") MeN is tight. Since pSB is tight, for any > O we can choose compact and measurable (under Skorokhod topology and associated Borel a algebra). For any measurable K,
dPSB
dpss
DKL (II"
pSs) En(.)
log dTT(m)
Ke (I() + E
log
K II()
d
PSB
K()
J (K) (2) (K),
2 - log
(T( (K²) - log (K)
(K')
by the Jensen inequality. If (II") IeE not tight, for each compact K and X > O, there is least one n E N where (T(m)
) 2 X, (T(()()())) < A. Thus, for there exists N, such that
sss (?) (7 (KT) 2 log(s/A)A,
log 11()) (K9)
which implies that the lower bound of DRL (IISS) can be arbitrary large. However, the KL- divergence is non-increasing and upper bounded by Dxr. (II0))ppS < cc, contradiction occurs. Thus, the sequence of measure should be tight. Similarly, we can show the {M(*) [M(m))en is tight.
The space (2, dg) is Polish space and therefore, by Prokhorov's theorem, the collections of measures (II(") IeE and {M(") Jeen relatively compact. Each subsequence of (M()) Ine has sub-subsequence (TT() )20 weakly converges [T())) í co. Similarly, there is sub-subsequence (i) 120 that converges in law ( By the lower semi-continuity of the KL-divergence, DKL (II
O, which implies the two con- vergence point is equal p(x=), The resulting measure is Markov and in R(Q), because the space is finite, which deduce pss p(+)) We choose an arbitrary convergent point of sub- subsequence resulting in pSB the convergence is ensured
lim inf (II))
C ALGORITHM
Algorithm Iterative Discrete Markovian Fitting
Require: Joint distribution क, tractable bridge Q.jo.r. number of outer iterations N E N
1: Let (0) =Q.10. 10.- 2: for n = O,..., ....N do
3: Learn using Equation with A (2m)
4: Let A (2m+1) = M (2++
5: Learn A using Equation
with A (2++1)
6: Let A (2n+2) M (2m+2)
0,r
7: end for
8:
return 0"
"See section 12 of Billingsly (203)) or section 3.5 of Ethier & Kurtz 2009 "See Theorem 2.6 of Billingsley (2113
29

---

Published as a conference paper at ICLR 2025
D GRAPH PERMUTATION MATCHING
D.1 INTRODUCTION
graph G (V,8) is defined as the set of nodes V { and the set of edges {eyz where and j denote the node indices. Under a permutation a Sn. the structure of the graph g remains unchanged, as the node and edge sets are invariant to indexing:
o(V) {vo(1)} = V, oEE) = (Eo())(1)) = E,
However, the vectorized representation of graph, G (V, E) is affected by the permutation because V and E are treated as ordered sets. Thus, a graph g can considered as a set of all permuted version of its vectorized representation:
g = fo(G) : S.h.
where the an arbitrarily indexed vectorization of G.
The likelihood of transitioning from initial graph G (V, E) to terminal graph G' (V', E"), denoted pl GG = Q(x, = G' Xo = G). depends on both node and edge correspondences, whereas the likelihood G(G' which is permutation-invariant, does not. More specifically, for any permutation a, the likelihood ((a' changes, even though the underlying graph g' re- mains unchanged. Calculating the likelihood of the graph itself (as opposed the graph vector) would require summing the likelihoods of all possible permutations G', but this approach is computationally prohibitive due the factorial number of permutations.
This dependency on graph permutation introduces challenges not only in computing likelihoods but also in constructing reciprocal measures. Ideally, reciprocal measure over graph domain would account for all permutations of graph vectors. However, as with likelihood computations, the con- struction of reciprocal measures is highly sensitive on the alignment of graph vectors, making proper handling of these permutations essential for the iterative Markovian fitting (IMF) algorithm.
D.2 SUB-OPTIMAL VS. OPTIMAT. PERMUTATION
In practice, the key insight is that the likelihood difference of graph vectors between the optimal permutation a² and sub-optimal permutations is substantial, allowing permutations. The design choice of the reference process Q, particularly its signal to noise ratio a(r) 2(0) >> 0 (see Equation ().) ensures the transitions preserving the initial states are far more proba- ble. As result, the likelihood for sub-optimal permutations, where node and edge correspondences are mismatched, is expected to be significantly lower than for the optimal permutation. The reason that even small mismatch in node alignment between o² and can cause large number of edge state mismatches, leading to a dramatic decrease in the total likelihood.
neglect sub-optimal
Thus, the likelihood p(a'''' G' G)) > P(oG') and the contribution of sub-optimal permutation in calculating P(g (G) is negligible. It is sufficient that focus solely on the optimal permutation o" for the likelihood computation, the probability of sub-optimal arrangements is effectively zero in practical terms.
The prioritization of optimal permutation could be also utilized in the construction of reciprocal measures. Suppose we have only one graph for initial and terminal, where the one is G and g', respectively. Without loss of generality, we assume an even distribution over graph vectors G G, P According
and then consider permutations over oG' E G'. Note that p(oG'|G) to the static SB solution, the graph vectors oG' G' are distributed according to the likelihood p(o [G) for each graph vector G G, where the optimal permutation is selected most frequently. In this context, neglecting sub-optimal permutation can be viewed as the static OT solution.
As the original SB problem is formulated with the dynamics over graph vector domain, arranging the graph vectors is a part of the SB problem. However, by relying on the optimal permutation, we reduce complexity of the SB problem aroused by the graph vectors alignment. This strategy ensures the transition from a graph vector to the optimally permuted graph vector, resulting in more reliable convergence of the iterative algorithm.
30

---

Published as a conference paper at ICLR 2025
D.3 STANDARD FORMULATION OF GRAPH MATCHING PROBLEM
In this section we will discuss about the standard formulation of the graph matching problem and how the task of finding the optimal permutation o², which minimizes the negative log-likelihood (NLL) - p(o GG), GG) can be framed as a graph matching problem.
Consider two graph vectors G (V, E) and G' (V', E') along with the cost function cº and c which define the cost of mapping nodes and edges, respectively. The binary assignment matrix X E (0, 1 represents the matching between nodes, where and n' denote the number of nodes of and G', respectively. vs E V matches vng E V', then X., = 1, while all other entries for node Vy are zero.
The total node matching cost is given by Σx cost of matching from E V to va E V Similarly, the total edge matching cost is =xx.=1X,,,-11<(e dab) where (eig, dab)) the cost of matching from Cij to Enbb E E'.
cV (vi, (v), where c (uy, vn) denotes the
We define the cost matrix A E IR where the diagonal components Aja,ia cV cV(u,, "n) represent node costs and the off-diagonal components Aiu.jb c (eaj, <ab)) represent edge costs. By flattening the assignment matrix be x E (0, 1)m0,, we can write the total cost function f as
f(x)
Σ
Σ c² (vx, va))
Xia x
=x Ax.
Thus, the graph matching problem is find the optimal assignment that minimizing cost fxx), which is written in formal:
x = arg min x T
Ax,
(19)
x
Xio S
Dia S 1,
where the inequalities become equalities if = n'. This formulation corresponds to the well-known quadratic assignment problem (QAP), which is NP-hard.
The NLL - log p( GG) can be decomposed by the sum of the NLLs nodes and edges:
log (G'
Σ 51a=1,65 1,6
log P
(Cig, Cab +
Σ log PV- (v, v.)) 8ia
By interpreting the NLLs of nodes and edges as cost function c" and c respectively, the problem of finding the optimal permutation o" can be formulated QAP, in Equation (19).
D.4 SOLUTION METHOD
Exact solution methods for the QAP, such mixed integer programming (MIP), requires combina- torial optimization, which incurs prohibitive computational costs (Sahni Gonzalez, 1976). Many accelerated algorithms adopt franch-and-boune strategies that utilize bounds of objective functions (Anstreicher] 2003 Gilmore 1962 Loiola et al. 2007 Xia 2008), reducing the exploration space. However, the combinatorial optimization cannot be avoidable in these strategy. Alternatively, tinuous relaxation methods (Cho et al.) 2014 Leordeanu & Hebert (005) solve the QAP Equa- tion (19) using a continuous vector bypassing combinatorial explorations. However, the continu- ous relaxation yields non-binary vectors, which require a discretization step, potentially introducing errors.
In our work, we compared two continuous relaxation methods: spectral method (SM) and maximum polling method (MPM), followed by the Hungarian algorithm for post-discretization Both methods iteratively update the continuous version of assignment vector x as:
X2
A O X
Xk+1
(20)
31

---

Published as a conference paper at ICLR 2025
where @ denotes matrix multiplication for SM and max- max-ppoled matrix multiplication for MPM, and & denotes step size, and v denotes the normalizer. Specifically, the A @ x for SM is described as
(A ia
Xio Aaria + Σ Σ
Xjt.Aissb
JEA;
In the MPM case, the operation is defined as
(A X) Aisia +
Σ JEA;
max Xyn A bEN.
In practice, we modified the cost matrix A slightly for efficiency. To accelerate the process, we neglect all edges corresponding to dummies in G', which significantly reduces computational cost, making [Wal scale linearly with n'.. Additionally, a small Gaussian perturbation was applied to A, slightly altering the minima the continuous vector space. We solved each QAP ten times to compensate the effects of randomness, improving performance with reasonable computational costs (see Appendix D.5).
D.5 PERFORMANCE OF GRAPH MATCHING ALGORITHM
In this section, we compare the performance of the following algorithms under different conditions: (I) SM algorithm, (2) MPM algorithm, and (3) MPM algorithm with randomness. The hyper- parameters (()) 0.3 for the reference process Q
To evaluate the effectiveness of QAP solvers on molecular graphs, we selected 100 molecules from the ZINC test set. In all experiments, the source molecule dummy types), while the target molecule retained only its original edges. We performed up to 1,000 iterations of updates according to Equation (20) with a specified tolerance.
treated fully connected (with
To assess the performance of the algorithms, we permuted the molecular graphs and then tested whether the original indices could be recovered, where optimality is achieved with the inverse per- mutation. For this task, we evaluated the exact matching ratio, which indicates the proportion of cases where the original indices molecular graphs, multiple optimal permutations may exist. Therefore, instead of relying solely on exact index recovery. we base the success criterion on the objective function value. If the Negative Log-L Ligeliikll (NLL) error falls below 1e-2, the solution is considered successful.
successfully recovered. Due the inherent symmetry in
For different molecule pairs where no optimal permutation available, which common in practical scenarios, exact solvers become computationally prohibitive even with relatively small molecular graphs. As such, we evaluated the performance of the QAP solvers by measuring the reduction in NLL between the initial and optimized permutations.
We conducted experiments with various hyperparameters, and the results are illustrated in Table 3 All algorithms successfully found exact matches for the same molecules, but the MPM algorithm performed better than the SM algorithm when applied to different molecule pairs. For all subsequent experiments, adopted the MPM algorithm with randomness in the cost matrix as the QAP solver.
Table 3: Comparison of different algorithms based on configuration parameters. NLL drop represents the improvement in likelihood between randomly paired molecules, while exact match reflects the percentage of permutations successfully recovered after applying a random permutation the molecules. and I denote higher and lower values are better, respectively.
Configuration
Algorithu
NLL drop(t)
Exact matching(t)
Pooling
Tolerunce
Precision
Max it iterations
Nuise coefficient
A trials
(M-SM SM
Sum
Ic-9
FP64
1000
2.251
100
Max
le-5
13.256
(3) MPM Randomness
Max
le-5
FP32
1000
1c.6
10
13:256
100
(4) Our setting
Max
1o-4
FP32
2500
1e-6
10
14.324
100
D.6 RELATION TO GRAPH EDIT DISTANCE
The graph edit distance (GED) is a widely used and flexible metric for measuring the dissimilarity between two graphs. It is defined as the minimum cost required to transform one graph into another
32

---

Published as a conference paper at ICLR 2025
through sequence of unit operations. Each unit operation be removal, substitution, or inser- tion, and can be applied to either node or edges. The total cost the transformation the sum of the costs assigned to these components.
According to Bougleux et al. (2013), finding the minimal-cost transformation between two graphs equivalent to the QAP problem with associated cost function. Though both problems are NP- hard, the equivalence is meaningful in that there are numerous approximation algorithms for the QAP problem that operate within polynomial time.
The basic idea for re-formulation into QAP problem involves the introduction of dummy nodes and dummy edges, where removal (insertion) operations could be replaced by substitution into (from) dummies. The cost function of unit operation is defined as c² (Ut, v'a and e (eij. eaa)) for node re- placement and edge replacement, respectively. Let a(T) (0). the cost replacement is defined as:
loog (d -1)++1 if Us = 1/2 otherwise,
(U),1))
log
-a+
d (d 1)+1 if ef = e'ab otherwise,
c (eig; eaab))
log
log
d
where d' and d denote the cardinality of XV and X respectively. Similar to Equation (19), can formulate it to a quadratic problem with the objective function f as:
f(x)=
Σ
c (eyy Car) +
Σ cv (1i, v(a),
x===1xx6==1
Xia=1
Σ
log PE (e.j. (eij.cat)) +
Σ
llg PV (1,, ())
1,x,,=1
= p(oG'/)),
where, the is the graph permutation associated to the assignment vector X.
However, the GED is not same to the NLL. Note that the edit cost functions penalize every operations with same cost - log - except for the identity operation. Though the cost of identity operation lesser than the others, the optimal transformation would not contains any identity operation. In real, the cost of identity operation does not affect the optimal edit path, implying that GED is not equal but proportion to the NLL, where the difference proportional to the number of the nodes and edges that are equal under the optimal graph matching a². Though the GED is not exactly same to the NLL, the problem is equivalent to the graph matching problem.
This observation provides revealing that the associated OT cost is effectively the GED. Therefore, solving the SB problem can be understood finding the OT plan between graph distributions, where the transport cost is defined by the GED.
clear interpretation of the underlying dynamics of the SB problem,
E IMPLEMENTATION DETAILS
E. PARAMETERIZZTTIN
In this section, we briefly describe the neural network parameterization and the practical training loss. According to Equations (5) and 6 the neural network approximates the generator A (a, v) and AA (v, which are formulated as conditional expectation of A(x, y5 and Å(y, x;; z), re- spectively (see Lemma B.5).
The target generator takes the form:
A (2, y) (1:(( (T.r(2.2)
if + y if =
A, y:
(21)
Enjer Ao u) Par(u.)) (2,0)
33

---

Published as a conference paper at ICLR 2025
where Ag and Pa:r are tractable attributes of Q Let the the transition probability matrix be P(*,T) r) 702 + R with (x, v) = e P(s, T eey- Thus, the neural network pre- dicts the distribution of given X, = I, denoted 20(5, E R and our parameterization
choice is as follows:
A (1r, y: 0) (a of ((s,T))o(s,,) 0, P(s, T =0
for y * x. The time reverse generator is also defined similarly.
Though the loss formulation defined continuous manner, approximate it with the dis- cretizations. Firstly, we will replace A, (X,,, x,;2) AM (X,, with as follows:
+ A, 2)
A Ac(Xe, A." (X,, ~ At
A1+ Xx log
1+ AN" (X,, X.) At
P (X,, X,)
E++At
EittA (X,; Xi)
PM
tHt X1)
Similarly,
A, 2/2
p P
1+++A (I,
(z ys 2) log
~ p At a+
(z, v) log
AA (xx v)
PMd4
(I.
t:f+
Thus the discretized loss function corresponding to Equation
5 is:
p p
I(0)= -00=-M1
1 E
BAG
Σ Puttai log
tu++ (2, y)
The time reversed loss can be discretized same way.
E.2 DATA PROCESSING FOR ZINC250K DATASET EXPERIMENT
In Section 5.2 we experimented with the standard ZINC250K dataset. In our molecular graph representation, G (V, E), the node vectors V = (v()); represent the atomic types, and the edge vectors E = (e(t)) ky represent bond orders. Due to this implementation choice, node features other than the atomic type cannot be represented, causing occasional failures in decoding into molecules. Still, to focus on the SB problem itself, we filtered out molecules whose graph representations are not directly converted into molecules by the RDKit package. Among the node features, formal charge and explicit hydrogen information is crucial in decoding process since, without them, each atom's valency cannot be inferred, that corresponding molecule cannot be uniquely determined. Thus, the following criteria were applied to filter molecules from the ZINC250K dataset: (1) all atoms do not possess formal charge and (2) all aromatic atoms do not have an explicit hydrogen. Our final training and test dataset contain 23,936 and 5,984 molecule pairs, respectively.
E.3 NEURAL NETWORK PARAMETERIZATION AND HYPERPARAMETER SETTINGS
DDSBM and DBM. Our neural network parameterization is based on Vignac et al. (2022). which uses a graph transformer network (Dwivedi & Bresson 2020). In short, it takes as input noisy graph G; = (V,, E,) and predicts a distribution over the target graphs. Structural and spectral features also used inputs to improve the expressivity of neural networks. We refer the reader to Vignac et al. (2022) for more details.
For noise scheduling,
employ a slightly different strategy than Vignac et al. 2022
While
Vignac et al. (2022) uses a cosine schedule for āt, we implement a symmetric scheduling of ag by incorporating Olmin. defined below:
0,ā(() a(t)
cos f//T+s T T)²² (1 O 1 2
(xt)
Gminn
(22)
for 0 5 with att) = a(T t) for the remaining half of the schedule. For instance, with 100 diffusion steps, a(T) R 0.95 when Omin 0.999, and ((() 0.90 when a'in 0.99795.
34

---

Published as a conference paper at ICLR 2025
ā.(amin 0.999)
Cre Vr(amin -0.99)
1.00
1.0000
0.99
0.9998
0.98
0.9996
0.97
0.9994
0.96
0.9992
0.95
0.9990
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
timestep
timestep (t)
Figure 9: Plot of (tt) and @(t) as functions of timestep / where O'min 0.999
We trained DDSBM models with IMF iterations, and DBM models, an one-directional variant of DDSBM with fixed joint molecular pairs. were trained with the same number of gradient updates to ensure consistency. Both DBM and DDSBM reported in this work were trained using four RTX A4000 GPUs The detailed hyperparameters for training are shown in Table
Table 4: Training hyperparmeters of DBM and DDSBM for graph transformation.
Task
Model
diffusion steps
Qmmin
epoch
SB iterations
ZINC250K
DBM
100
0.999
1800
ZINC250K
DDSBM
100
0.999
300
6
Polymer
DBM
100
0.999
1250
Polymer
DDSBM
100
0.999
250
5
Graph-to-Gran Graphh Translation. For HicrG2G and AtomG2G, we used the default settings provided on the official GitHub repository. Both models were trained until maximum epochs by default with a single RTX A4000 GPU.
E.4 DETAILS ABOUT METRICS
We here provide detailed explanations about each metric used in the results section. They are clas- sified into two groups; the first to evaluate the marginal distribution of the generated data (data- wise) and the other is to evaluate the joint distribution between initial and generated data (pair-wise). Among the metrics explained below, Validity, Uniqueness, Novelty, NSPDK. W,, and FCD are metrics that evaluate the marginal distributions, while NLL and MAD are metrics that evaluate the joint distribution.
E.4.1 BASIC METRICS
Validity: Measures the proportion of chemically valid molecules generated by the model.
A valid molecule adheres to fundamental chemical rules, such as valency constraints.
Represents the fraction of unique molecules in the generated This metric ensures the diversity of the generated molecules and prevents redundancy.
Uniqueness:
Novelty: Quantifies the fraction of generated molecules that not present in the training dataset. This evaluates the ability the model to explore new regions of the chemical space.
35

---

Published as a conference paper at ICLR 2025
E.4.2 GRAPH STRUCTURAL METRICS
Negative Log-Likelihou (NLL): Evaluates the quality of the joint distribution by mea- suring the cost of transforming graph into another based the reference process. This metric closely related to the graph edit distance (GED), which quantifies the minimal number of modifications required to transform graph into another (see Appendix D.6.
Neighborhood Subgraph Pairwise Distance Kernel (NSPDK); Computes the distance between graph distributions using mean maximum discrepancy (MMD). NSPDK evalu- ates similarity based local neighborhood subgraphs, which incorporate node and edge features as well as the underlying graph structure (Costa Grave 2010).
E.4.3 MOLECULAR PROPERTIES METRICS
Wasserstein-1 Distance (W1): Measures the distance between the property distributions the target and generated molecules for the properties to be modified, focusing on the marginal distribution. This metric reflects how closely the generated molecular properties match the desired target distribution.
Mean Absolute Difference (MAD): Quantifies the average absolute difference in key properties within each molecular pair of initial and generated molecules. Low MAD value ensures that critical molecular properties such as drug-likeness (QED) and synthetic acces- sibility (SAscore) remain consistent during graph transformation (Bickerton et al., 2012
Ertl & Schuffenbauer 2009).
Calculates the similarity between the target molecule distribution and the generated molecules, focusing on the marginal distribution of the molecules (Preuer et al. (2088). It is based on comparing the feature distributions of molecules embedded using pre-trained neural network.
Fréchet ChemNet Distance (FCD):
F SUPPLEMENTARY RESULTS
F.1 MORE STATISTICAL RESULTS FOR MAIN EXPERIMENTS
Tables 5 and 6 show average and standard deviation for all the metrics of ZINC and polymer exper- iments from three different training runs, respectively. For clarity, we plot the raw values of each molecular property-loe P. QED, and SAscore in Figure 10
Table 5: Distribution shift performance ZINC. 1 and 1 denote higher and lower values better, respectively. Standard deviation values for three independent runs included compared to the original table in the main result.
Model
Val(1)
Uniq
Nov(1)
NLL(-)
NSPDK(J)
LegP Wi(4;
QLD MAD(J)
SAscore MAD())
[CD(1)
Reference
360.662
1-47c-4
2,077
0.153
0.595
4,807 /0279
AtvnCi3C1
99.9-0.1
644-26
99.3-0.1
3550255-04444
9.0003322.01-3
0 0.162-00144
0.14300.011
0:607-0.019
5.11--05722
HierG2G
100,01000
73.7-1.
99.510.11
344/5884454
3.4.55e
0.13100005
0.146.10.005
0.68710.032
5.74210.378
DBM
87.62122
100.0:0.0
10001000
288
388.572433327
8.0.e-412.23c
0.15010.012
0.141100002
0.608.0.013
1,066100043
Table 6: Distribution shift performance on polymer. and denote higher and lower values are better, respectively. Standard deviation values for three independent runs included compared the original table in the main result.
Model
Val.(1)
Un)
Nov.(t)
NLI(-)
NSPDK(L)
GAP Wi(L)
FCD(J)
Reference
749,800
5.64e-4
0.312
1.469 / 0.384
DBM
43.420:155 97.4-0.004
99.8=0.002
97,420.003
580.455:11.279
5.826-343.624. 626err
0.249--0.019
2.230:0.175
DDSBM
94.5+0.011
71.3++0.08
212.047 - 18.444
4.18e-3 1.55e-4
0.017
1.074+0.038
36

---

Published as a conference paper at ICLR 2025
0.8
3.5
10
0.6
3.0
0.8
Dersky
2.5
Density
0.4
0.6
0.4
0.2
0.2
0.0
0.0
-0.6
-0.4
-0.2
0.0
0.2
0.4
0.6
-4
-2
0
log
AQED
ASAscore
Initial Pair
HerG2G
DDSBM
Figure 10: Density plots comparing the distributions of three molecular properties (log P, AQED, and ASAscore) across four different molecular generation methods: AtomG2G, Hi- erG2G, DBM, and DDSBM.
F.2 ABLATION STUDIES
We conducted ablation studies about the effects of graph matching algorithm and initial coupling of data on the distribution shift performance and the convergence of IMF iteration. Note that the former and the latter affect graph vectors and graphs, respectively.
F.2.1 THE EFFECT OF GRAPH MATCHING ALGORITHMS
We first conducted experiment about graph matching algorithms' effects on the performance of DDSBM. As Table shows,, the performance variations across graph matching algorithms were not significant. We attribute this outcome to the inherent characteristics of the DDSBM framework. As the SB iterations progress, the differences between initial and generated graphs would be decreased, in other words, they become increasingly similar. This is due to reference process employs non-zero a, to assign low probabilities to dissimilar data pairs. Consequently, the influence of the graph matching algorithm diminishes, as supported by the Figure II This effect causes the model to converge in similar manner regardless of the specific graph matching algorithm applied each IMF iteration, resulting in minor differences on the final values as shown in the Table 7
the optimality of graph data for each Markovian projection gradually
Table 7: Ablation study on graph matching. and J. denote higher and lower values are better, respectively.
Algoritha
Val(f))
Uniqu(t))
Nov(t)
NLL(
NSPDK(L)
LogP Wg(l)
MAD(L)
SAscore MAD(J)
FCD(J)
(1) SM
94.6
100.0
99.99
163.931
1.17e-3
0.159
0.122
0.388
0.837
(2) MPM
95.8
100.0
100.0
155.378
6.95e-4
0.164
0.110
0.401
0.773
MPM Rundomness
95.3
100.0
99.9
158.534
6.78e-4
0.130
0.116
0.424
(4) Our setting
94.1
100.0
99.9
164,480
7.49-44
0.139
0.124
0.392
0.747
Furthermore, we additionally examined two scenarios on our main expeirment with the ZINC250K dataset: training with graph matching during the IMF iterations, and training without any graph matching algorithm during the whole training process. For the former, the graph matching setup used our main ZINC experiment in Section 5.2 was used without change. Figure [2 shows that, similar to the comparison of several graph matching algorithm, the use of graph matching merely affected the convergence DDSBM after sufficient number of IMF iterations. Still, we observed that, without graph matching, both the training loss and the negative ligllikel (NLL) between the original and generated data start at higher values and require more iterations to reach levels comparable those achieved with graph matching. This indicates that graph matching algorithms, while not essential for the eventual convergence DDSBM, can accelerate the convergence through the IMF iterations, providing additional benefit.
37

---

Published as a conference paper at ICLR 2025
Suboptimal permutation ratio
Average NLL drop
15
13
Ratio (%)
Ratio (%)
11
2
3
4
5
IMF iteration
IMF iteration
(a) The of suboptimal initial pairs
(b) The average drop
Figure 11: The effect of graph matching algorithm graph permutation matching versus the IMF iterations. The result computed from training data from single run of our graph matching algorithm, which updated during an IMF iteration.
(a) The ratio of suboptimal initial permutation pairs, found by the graph matching algorithm. For each iteration, this amount of graph data pairs modified in their permutations.
(b) The average NLL drop percentage for the data pairs whose permutations were changed by the graph matching algorithm, ie. (NLL NLL /NLL
Effect of Graph Matching on convergence IMF iteration
Effect Graph Matching on NLL between original generated data
1.4
Masching
260
Gneh Manching
NOT USE
NOT USE
Average KL Loss
1.2
USE
240
USE
1.0
220
0.8
200
0.6
180
0.4
160
IMF iteration
IMF iteration
(a) Comparison of DRI. D (A
(b) Comparison NLL.
Figure 12: Comparison of training loss, [A] and NLL between original and generated data across IMF iterations of experiment setup with and without graph matching algorithm. Here for graph matching, we used algorithm (4) in Table Also, note that NLL in Figure [26 is calculated directly from original data and generated data without permutation alignment.
F.2.2 THE EFFECT OF INITIAL COUPLING
We further analyze the molecular optimization task in Section 5.2 with different initial couplings. In that section, we used randomly coupled molecules the intial coupling for all the models. However, except for DDSBM, all of them assume that suitable molecule pairs have already been identified to be provided. To meet this, we adopted Tanimoto similarity (Willett et al., 1998) as a pseudo-metric find similar molecule pairs between the two molecule distributions, denoted as Tanimoto similarity-base based coupling. We note that the similarity- based coupling is another optimal transport problem of maximizing the sum of pair-wise molecular similarities, where we employed the Hungarian method to obtain sub-optimal solution.
Using the Tanimoto iimilarity-basee coupling, we retrained all models discussed Section 5.2 and compared their performance. Here, denote newly trained DDSBM model DDSBM-T to deviate from the model trained on the randomly coupled data. From Table g we observe that all models achieved lower NLL values compared to when they were trained with random coupling. The
38

---

Published as a conference paper at ICLR 2025
HierG2G model exhibits much lower FCD and NLL values compared those of random coupling, indicating that previous graph transformation methods can be improved more optimal pairs are provided as training data.
Effect of Initial Coupling on
convergence of IMF iteration
1.2
Initial Coupling
Tanimoto
Random
Average KL Loss
1.0
0.8
0.4
2
3
5
6
7
IMF iteration
Figure 13: Comparison of DKL. (A|M) across IMF iterations for two types of initial couplings:
Random and Tanimoto similarity.
The distinct feature of DDSBM-Tis that all baseline models learn graph transformations between the molecule pairs with high Tanimoto similarity, while DDSBM-T learns graph transformations with minimal cost defined by its reference process Q. It cannot be guaranteed that the distance defined by our reference process is better than the Tanimoto similarity from the perspective of molecular optimization. Essentially, the success of molecular optimization should be measured by how well the target property is adjusted while preserving other key properties. Apparently, Table & shows that DDSBM-T outperforms the other baselines in terms of molecular property metrics. This suggests that the graph transformation from DDSBM retains other molecular properties, attaining the goal of the molecule optimization task.
Finally, we analyze the effect of initial coupling on the training process, especially focusing on the approach to convergence. We illustrate the training losses of DDSBM models from two different initial couplings, random and Tanimoto similarity-based. in Figure 13 respectively. DDSBM-T shows consistently lower loss values up to the sixth IMF iteration and reaches convergence at the third IMF iteration.
Table 8: Distribution shift performance on ZINC with initial coupling based on the Tanimoto similarity. As in Table [] reference refers to metrics from the initial coupling, used as a stan- dard to evaluate each model's graph translation. The experimental setting is the same as described Section 5.2 except for the initial coupling. and J denote higher and lower values are better, respectively.
Type
Val,())
Unig.!?)
Newit)
NLL(L)
NSPDK(L)
LogP Wi(4)
QED MADIJ)
MADI))
PCD(
Reference!
245.065
1.63e-4
2.011
4.81
AlomGDG
Latent
108.0
99.9
5.23-3
0.315
1,578
HierG2G
Lasent
100.0
99.7
99.9
264,072
1.33e
0.189
0.127
0.446
1.71
DRM
Bridge
90.
100.0
99.9
220 504
5.91e-4
0.141
0.127
0 105
0.749
DDSBM T
Schnidinger Bridge
95.6
100,0
99,9
152.856
6.23e
0.103
0.110
0.393
0.911
NLLL W. and MADs ware calculaned wing rudiom from aoil set. Two FCD values prosled: the fast compara die inttal melocules is the upt with the tennisal meteralos in the tniiing set, and the worrd compans the tnmiral molecales in both vate. Also, the miternoe NSTD is compate with the tominall molenales from tmining bott ses.
F.3 EXAMPLES FOR GENERATED MOLECULES ON MOLECULE OPTIMIZATION TASKS
To show the difference between molecules generated from DDSBM and others, we visualized some selected examples for the ZINC. and polymer datasets, respectively (see Figures 14 and 15 As
39

---

Published as a conference paper at ICLR 2025
expected from the superior performance of DDSBM compared to other methods in terms of joint distribution metrics (NLL and properties MAD), the generation result from DDSBM gives more similar graph structure compared to source molecules in both ZINC and polymer datasets. We also present generation trajectories for different molecules in ZINC and polymer datasets Figures 16 and[1
Qooor
Source
DDSBM
DBM
HierGi2G
Figure 14: Visualization of molecules generated by DDSBM, DBM, and HierG2G compared to the source molecule.
40

---

Published as a conference paper at ICLR 2025
Source
DDSBM
DBM
Source
DDSBM
DBM
Source
DDSBM
DBM
Visualization of molecules generated by DDSBM and DBM with the source molecule. The samples generated by DBM and DDSBM were selected from the molecules pre- dicted to have a blue color with GAP values in the range of 2.56-2.75 eV..
Figure 15:
G UNCONDITIONAL GRAPH GENERATION
G.1 EXPERIMENTAL SETUP AND METRICS
We conducted an additional evaluation of DDSBM on an unconditional graph generation task. To ensure consistency, adopted the same hyperparameter settings and training configurations in DiGress (Vignac et al.) 2022), except for the noise scheduling as detailed in Table 4 Training, validation, and test splits not employed, similar to the main tasks. The training hyperparameters are detailed in Table
DiGress, but early stopping based on the validation set was
For each task, both the DDSBM and DBM were trained for the number of epochs, with sam- pling from the prior distribution repeated five times. The results were averaged across the five for the Maximum Mean Discrepancy (MMD) of graph features (degree distributions, clustering coef- ficients, and orbit counts). Additionally, for the planar and QM9 datasets, further metrics such as Validity/Uniqqueees//oovlyl (V.U.N.) were evaluated.
G.2 SYNTHETIC GRAPH GENERATION
In the Community- 20 task, both DBM and DDSBM demonstrated superior performance compared DiGress in terms of degree, clustering, and orbit metrics. This result highlights the strengths of
41

---

Published as a conference paper at ICLR 2025
11/4
1=1/2
t=3/4
Figure 16: Trajectory visualization of ZINC molecule optimization task generated by DDSBM. Note that t=0 and t=1 are the original and generated molecules, respectively.
Table Training hyperparameters DBM and DDSBM for unconditional graph generation
Task
Model
diffusion steps
O'min
cpoch
SB itcrations
QM9
DBM
100
0.999
200
QM9
DDSBM
100
0.999
100
2
Community-22
DBM
500
0.9998
1000k
Community-20
DDSBM
500
0.9998
200k
5
Planar
DBM
1000
0.9999
100k
Planar
DDSBM
1000
0.9999
10k
10
DBM and DDSBM in unconditional graph generation tasks well. Notably, DDSBM achieved the best performance clustering and competitive results in orbit while also significantly reducing the NLL value compared to DBM. These findings underscore the capacity of the DDSBM gen- crate high-quality graph structures at minimal cost, even when bridging noisy distribution to data distribution.
G.3 SMALL MOLECULAR GRAPH GENERATION
For the QM9 task, both DBM and DDSBM demonstrated significant improvements in FCD com- pared to DiGress, as reported in Nguyen et al. (2024). Additionally, enhancements in validity and novelty were also observed. While DBM showed slightly better performance in FCD and validity, DDSBM exhibited strengths in novelty compared to DBM. For other metrics, DDSBM and DBM displayed comparable performance.
42

---

Published as a conference paper at ICLR 2025
1=0
11/
1=1/
t=3/4
Figure 17: Trajectory visualization of Polymer optimization task generated by DDSBM. Note that t=0 and t=1 are the original and generated molecules, respectively.
Unconditional graph generation performance on Community-22 1 and J denote higher and lower values are better, respectively. The best performance is highlighted in bold, and the second-best performance is underlined.
Table 10:
Model
Degree
Clustering
Orbit 4
NLL 1
GraphRNN
8.00e-2
1.19e-1
4.00e-2
GRAN'
6.00e-2
1.12e-1
1.00e-2
GG-GAN
8.00e-2
2.17e-1
8.00e-2
SPECTRE
1.00e-2
1.89e-1
2.00e-2
DiGress
2.00e-2
6.30e-2
1.00e-2
DBM
1.80e22 1.75e-2
3.80e-2
5.14e-3
3.26e+2
DDSBM
2.78e-2
5.81e -3
2.87e+2
These results are taken from Vignac
2022
G.4 EXAMPLES FOR GENERATED GRAPH ON UNCONDITIONAL GRAPH GENERATION
To illustrate how graph structure is preserved in DDSBM, we visualized selection of examples from the Planar, Community-22 20, and QM9 unconditional generation tasks. For all three tasks, the generation trajectories were visualized in Figures 18 to 20 In the of planar graphs, plotted the initial and generated graphs using the trained DDSBM and the public checkpoints of Digress (see Figure 21p.
43

---

Published as a conference paper at ICLR 2025
Table 11: Unconditional graph generation performance on Planar. and & denote higher and lower values are better, respectively. The best performance is highlighted in bold, and the second- best performance underlined.
Model
Degree
Clustering +
Orbit 4
V.U.N.
NLI.
GraphRNN
4.90e-3
2.79e-1
1.25e+0
0.0
GRAN!
7.00e-4
4.34e-2
9.00c-4
0.0
SPECTRE
5.00e-4
7.75e-2
1.20e-3
25.0
ConGress!
4.76c-3
2.73e-1
1.30c+0
0.0
DiGress
2.80e-4
3.72e-2
8.50e-4
75.0
DBM
9.35c-4
8,95c-2
8.67c-3
81.5
1.96c+3
DDSBM
7.39e-4
5.81e-2
9.60e-4
76.0
1.51e+3
These results are taken from Vignac al.
2022
Table 12: Unconditional graph generation performance on QM9, + and 4 denote higher and lower values better, respectively. The best performance is highlighted in bold, and the second- best performance underlined.
Model
Val. f
Uniq. f
Nov. f
FCD & NLL
GraphAF!
74.43
88.64
86.59
5,27c+0
MoFlow!
91.36
98.65
94.72
4.47e+0
GraphDF
93.88
98.58
98.54
1.09e+1
GDSS
95.72
98.46
86.27
2.90c+0
GraphArm
90.25
95.62
70.39
1.22e+0
GLAD
97.12
97.52
38.75
2.01e-1
Digress'
99.00
96.66
33.40
3.60e-1
DBM
99.87
96.59
36.54
9.90e-2
7.55e+1
DDSBM
99.67
96.83
38.06
1.05e-1
5.38e+1
These results taken from Nguyen
2024).
G.5 COMPARISON OF GENERATION PERFORMANCE ACROSS VARYING NFES
We compared the generation performance, specifically validity and FCD, of DDSBM and DBM on the QM9 task across different the number of function evaluations (NFEs), set at 5, 10, 20, 25, 50, and 100. The results show that DDSBM maintains performance reasonably well even low NFEs, whereas DBM shows a more pronounced performance degradation under the same conditions (Figure 22p. We attribute this DDSBM finding optimal generation paths that can be predicted with fewer NFEs.
44

---

Published as a conference paper at ICLR 2025
1=0
1//
1=1/2
t=3/4
t=1
Figure 18:
Trajectory visualization of planar graph generated by DDSBM. Note that t=0 and t=1 are the prior and generated graphs, respectively.
1=0
1/4
1=1/
t=3/4
t=1
Figure 19: Trajectory visualization of community-20 graph generated by DDSBM. Note that t=0 and t=l the prior and generated graphs, respectively.
45

---

Published as a conference paper at ICLR 2025
H
H
NHG
NHz
HN
CH2
CH2
MH.
CH
CH2
CH.
NH
NH.
NH
NHg
NH
HN
HN
H2O
HO
HO
OH
-OH
CH2
CH
1
1/4
1=1/2
t=3/4
Figure 20: Trajectory visualization of QM9 graph generated by DDSBM. Note that t=0 and t=1 are the prior and generated graphs, respectively.
Prior
DDSBM
Prior
Digress
Figure 21: Visualization of planar graph generated by DDSBM and Digress with the source prior graph. The color of each node is assigned based on the spectral features of the prior graph. Graphs generated by DDSBM tend to better preserve the graph structures of the source prior graph compared to those generated by Digress.
46

---

Published as a conference paper at ICLR 2025
1.0
Type
Type
DBM
DBM
DOSDM
0.9
2.5
Validity
0.8
2.0
FCD
0.7
1.0
0.6
0.5
10
20
50
100
5
10
20
50
100
Number Function Evaluation
Number Function Evaluation
(a) Validity NFE.
(b) FCD NFE.
Figure 22: Comparison of DBM and DDSBM in terms of generation performance with respect to number of diffusion steps (NFE) in QM9 experiment. Here, we used NFE of 5, 10, 15, 20, 25, and 100 timesteps.
47


Reviews:
[{"review_id": "s2U6098Ipr", "reviewer": "Reviewer_AZ9a", "summary": "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.", "questions": "- 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.\n- 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.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- 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.\n- The paper looks sound and technically strong.\n- Empirical results seem to indicate that this approach outperforms previous baselines by a large margin.", "weaknesses": "- 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 ?\n- I’d like to see some error bars on your results.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "C9F7ByqqyC", "reviewer": "Reviewer_7pXr", "summary": "This paper introduces discrete diffusion Schrödinger bridge model using continuous-time Markov chains. The proposed model was validated on molecular optimization problem.", "questions": "1. What is the relevance and difference between the proposed method and existing discrete SB models in Weakness?\n\n2. How does the performance of molecular optimization compare with discrete flow matching models?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Strong performance compared to diffusion bridge model.", "weaknesses": "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. \n\n[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.\n\n[2] Gat, Itai, et al. \"Discrete flow matching.\" arXiv preprint arXiv:2407.15595 (2024).\n\nAnd, 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.\n\n[3] Harchaoui, Zaid, Lang Liu, and Soumik Pal. \"Asymptotics of discrete Schrödinger bridges via chaos decomposition.\" Bernoulli 30.3 (2024): 1945-1970.\n\n[4] Chow, Shui-Nee, et al. \"A discrete Schrodinger bridge problem via optimal transport on graphs.\" calculus of variations 20.33 (2021): 34.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DoxIdKEtUL", "reviewer": "Reviewer_b65H", "summary": "Adapt diffusion Schrodinger bridge matching to the discrete domain and instantiate it through molecular optimization", "questions": "How significantly does the choice of graph-matching algorithm impact the overall performance of the method?\nIf 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.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This method adapts diffusion Schrodinger bridge matching which opens a new avenue for this task.\n2. 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.\n3. The work provides corresponding theoretical guarantees.", "weaknesses": "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:\n* The square brackets around the citation should not appear twice.\n* The name of section 2.2 'SOLUTION METHOD' needs to be optimized.\n* The supplementary material also contains the body part of the paper.\n* The structure section 2/3 is a bit confusing:\n  * 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.\n  *  Consequently, the insights about the transition from continuous domain to discrete domain are missing.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)