Bures-Wasserstein Flow Matching for Graph Generation
Authors: Keyue Jiang
Jiahao Cui
Xiaowen Dong
Laura Toni
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Generation
Flow Matching
Diffusion Models
Primary area: generative models

Abstract: Graph generation has emerged as a critical task in fields ranging from drug discovery to circuit design. Contemporary approaches, notably diffusion and flow-based models, have achieved solid graph generative performance through constructing a probability path that interpolates between reference and data distributions. However, these methods typically model the evolution of individual nodes and edges independently and use linear interpolations in the disjoint space of nodes/edges to build the path. This disentangled interpolation breaks the interconnected patterns of graphs, making the constructed probability path irregular and non-smooth, which causes poor training dynamics and faulty sampling convergence. To address the limitation, this paper first presents a theoretically grounded framework for probability path construction in graph generative models. Specifically, we model the joint evolution of the nodes and edges by representing graphs as connected systems parameterized by Markov random fields (MRF). We then leverage the optimal transport displacement between MRF objects to design a smooth probability path that ensures the co-evolution of graph components. Based on this, we introduce BWFlow, a flow-matching framework for graph generation that utilizes the derived optimal probability path to benefit the training and sampling algorithm design. Experimental evaluations in plain graph generation and molecule generation validate the effectiveness of BWFlow with competitive performance, better training convergence, and efficient sampling.

Published as a conference paper at ICLR 2026
TURES-WASSERSTE FLOW MATCHING FOR GRAPH GENERATION
Keyue Jiangl. Jiahao Cui Xiaowen Dong
Laura Toni
1 AI Centre, University College London
2 Department of Electronic and Electrical Engineering, University College London
3 Department of Computer Science, University College London
4 Department of Engineering Science, University of Oxford keyue. j jiang. 18 @8uccl ac.
ABSTRACT
Graph generation has emerged as critical task in fields ranging from drug discov- ery to circuit design. Contemporary approaches, notably diffusion and bosed models, have achieved solid graph generative performance through constructing probability path that interpolates hetween reference and data distributions. How- ever, these methods typically model the evolution of individual nodes and edges independently and use linear interpolations in the disjoint space of nodes/edges to build the path. This disentangled interpolation breaks the interconnected patterns of graphs, making the constructed probability path irregular and non-sm smooth, which causes poor training dynamics and faulty sampling convergence. To address the limitation, this paper first presents theoretically grounded framework for prob- ability path construction in graph generative models. Specifically, we model the joint evolution of the nodes and edges by representing graphs as connected systems parameterized by Markov random fields (MRF). We then leverage the optimal transport displacement between MRF objects design smooth probability path that ensures the co-evolution of graph components. Based on this, we introduce BWFlow, www-matching framework for graph generation that utilizes the derived optimal probability path to benefit the training and sampling algorithm design. Experimental evaluations in plain graph generation and molecule generation vali- date the effectiveness of BWFlow with competitive performance, better training convergence, and efficient sampling.
INTRODUCTION
Thanks to the capability of graphs in representing complex relationships, graph generation (Zhu et al.
2022
Liu et al. (023a) has become an essential task in various fields such as protein design (Ingraham
al. 2019), drug discovery (Bilodeau al. 2022). and social network analysis (Li et al. (023).
Among contemporary generative models, diffusion and flow models have emerged as two compelling
approaches for their ability to achieve ofate-of-thh-ar performance in graph generation (Niu al.
2020: VVinac et al. 2023a Eijkelboom et al. 20244] Qin et al.) 2024 Hou et al. 2024). In particular,
these generative models can be unified under the framework of stochastic interpolation (Albergo
& VVanden-Eijnden Eijnden 2023), which consists of four procedures (Lipman et al. 2024): 1) Drawing
samples from the reference (source) distribution po(-) and/or the data (target) distribution PI( (-). for training set assembly: 2) Constructing time-continoous probability path p. (-), 0 < < interpolating
between po and 3) 3) Training model to reconstruct the probability path by either approximating the score function velocity fields (ratio matrix in the discrete case); and 4) sampling from po and transforming it through the learned probability path to get samples that approximately follow P1.
A core challenge in this framework is constructing the probability path Pt. Existing text and image
generative models, operating either in the continuous (Ho et al. 2020 Song et al. 2021 1 Lipman et al. 2023 Liu al. 2023b) discrete (Campbell et al. 2022; Sun al.
| [023 Campbell et al. [2024] Gat et al. 2024; Minello et al. 2025) space, typically rely on linear interpolation between source and
target distributions to construct the path. Graph generation models, including diffusion (Niu et al.

---

Published as a conference paper at ICLR 2026
Estraaed velodit
MNDRUD PAA for Craghh 2441000
Mdal
Liwer intepplation
Linear Interpolation
Uner starpeieiin
Tore Desention 20R et
Ideal Interpolation
(Oin at
Bryst Quesance 1D
interpplationn (Dura)
Staps
(a) Training path comparison
(b) Training path manipulation
(c) Sampling path comparision
Figure/ I:
Probability path visualization. Since the probability is intractable, the average maximum mean discrepancy ratio (y-axis) of graph statistics between interpolants and the data points is used as proxy for the probability. Lower means closer to the data distribution (details in Section I.6
2020, Vignac al. 2023a Haefeli al. 2022 Xu et al., 2024| Siraudin al. 2024) and flow-based 2024 Qin et al.] [024] Hou et al. 2024). inherit this design by modeling every single node and edge independently and linearly build paths in the disjoint space. However, we argue this approach to be inefficient because it neglects the strong interactions and relational structure inherent in graphs, i.c., the significance of node heavily depends on the configuration of its neighbors. We first show the negative impact of linear path through motivating example.
models (Fijkelboom et al.
The limitation of linear interpolation. In flow model intuitively, the velocity is trained by approximating the tangent of the probability path in the training set, while generation follows the learned velocity to reconstruct the path toward the data distribution. The blue line in Fig. Ta illustrates the training path obtained by linear interpolation: it remains flat until transition point at = 0.8 after which it drops sharply. This non- non-smooth path leads to poor velocity estimation (red arrow) as: 1) the critical transition region 0.8 < t is less explored, causing potential underfitting, and 2) the velocities trained in the flat region t 0.8 fail to guide the model toward the target distribution. Consequently, sampling struggles to converge the data distribution shown in Fig. [c Ideally,
need a smooth probability path like the green line in Fig. Ta to ensure that at every time t, the model takes stable, meaningful steps toward the target distribution. More evidence in App. [.]]
We attribute this issue to the linear path construction that fails to capture global co-evolution (Haasler & Frossard 2024) of the graph components, and cannot guarantee optimal transport displacement between non-Euclidean graph distributions (Formal explanations in Section 2.2). Thus, the con- structed path suboptimal with sharp transition from reference data distribution even deviates from the valid graph domain (Kapusniak et al., (2024). Though not explicitly mentioned, Qin et al. (2024) mitigates this issue through heuristic strategies smooth the path, which we conceptually visualize in Fig. D and discussed in App. F.I This shows a potential benefit in manipulating the path and we aim at building theoretically grounded framework for probability path construction.
Proposed solution. To this end, we draw on statistical relational learning and model graphs using Markov Random Fields (MRFs) (Taskar et al., [2077] Qu et al. (019)). MRFs organize the nodes/edges as interconnected system and interpolating between two MRFs captures the joint evolution of the graph system. Extending Haasler Frossard (2024), we derive a closed-form Wasserstein distance between graph distributions and leverage it construct Bures Wasserstein (BW) interpolation that ensures the OT displacement between graph objects. We then integrate these insights into a How-matching framework called BWFlow. Specifically, BWFlow operates smooth, globally coherent velocity fields, exclusively constructed by BW interpolation, to generate graphs (see Fig. Ic]. Crucially, BWFlow admits simulation-Fin computation of densities and velocities along the entire path, which translates into efficient, stable training and sampling.
Contributions. First, observing that the linear interpolation used in existing models suboptimal, we propose a theoretically grounded framework for probability path construction and velocity estimation in graph generation. Second, through parameterizing graphs as MRFs, we introduce BWFlow, flow-maton now-matching model for graph generation that constructs probability paths respecting the graph geometry and develops smooth velocities without heuristic path manipulations. Third, BWFlow was
'This work focus on flow models and the generalization to diffusions in App. F2
"The specific value is an empirical observation and does not have theoretical significance. Fig. + illustrates that it differs across datasets.
2

---

Published as a conference paper at ICLR 2026
tested plain graph and molecule generation, exhibiting better performance and dynamics, such as fast and stable training convergence and efficient sampling.
2
PRELIMINARIES
2.1 FLOW MATCHING FOR GRAPH GENERATION
Flow matching (FM). Generative modeling considers fitting a mapping from state space S - S that transforms the samples from source distribution, Xg ~ Pn. to samples from target data distribution, X1 p. Continuous normalizing flow (Chen al. 2018 parameterizes the transformation through a push-forward equation that interpolates between po and P1 and constructs a probability path Pc (x() [ttPo] (2) through time-dependent function Ur, (a.k.a flow). vector field u, defined the (2)) Wy (1h2 (x)) with who (x) X. is said to generate Pt if th, satisfies X, := 1/2 (Xo)
Pe for Xo ~ Po- The FM (Lipman et al. 2023) is designed to match the real velocity field through:
LFM( (0) xx) (X,) u. (X.)ll
where vo()) S - S is the parameterized velocity field and : 1100 1].
Conditional flow matching (CFM). Given that the actual velocity field and the path are not tractable (Tong al. 2024). one construct the per-sample conditional flow. We condition the probability paths on variable Z (-) (for instance, a pair of source and target points Z = (Xo: X2)) and re-write (x()) PP (X' Z) and (x() ( u. " Z) where the conditional path and the velocity field are tractable. The CFM aims at regressing velocity (-).) to u, (X' 2) by the loss,
(CF := E, (2.. (X,, ue (x(x, 2)
where it is shown that the CFM optimization has the same optimum as the FM (Tong et al. 2024).
Graphs as statistical objects. When considering graph generation with CFM, the very first step is to model graphs as statistical objects. For notation. we let G = E,, denote an undirected graph random variable with edges & }ean]. nodes V = {v], and node features X = {zx). A graph realization is denoted G EV, X p(g). We consider group of latent variables that controls the graph distribution, specifically the node feature mean X = [1 22 TMy R|V|* the weighted adjacency matrix W R///<DD, and the Laplacian matrix L D W R RPHM, with D diag( (W)) being the degree matrix (and 1 the all-one vector). In a nutshell, graphs are sampled from G G); E(X;E; X, W).
Generation with CFM. The new graphs are sampled through iteratively building Gtadr G. + (G,) with initial Gu ~ po and trained velocity field of ). so that the medium points follows G ~ (9( and terminates at Pt. The velocity can be trained either via numerical approximation (i.e., (Gt) x (Gitdt - Gt)/dt df) or through z z-prediction (Gat et al. 2024) which parameterize of (Gx) as,
of (Gt) (Goo-oo()) (IG)) [12 (G, Go. G1)]
As such, training the velocity fields is replaced by a denoiser pf (. Gt) to predict the clean datapoint, which is equivalent to maximizing the log-likelihood (Qin et al. 2024 Campbell al. 2024).
LCFM BBGL- ()..)))))))))))aaa) (ttrpp/((...M0o1.....) G.... [logr (G, G.]
where is sampled from uniform distribution U(u,1j and G, Ptjo,1 can be obtained in a simulation- free manner. This framework avoids the evaluation of the conditional vector field at training time, which both increases the model robustness and training efficiency.
To proceed, a closed form of Pe(- | Go, G1) is required to construct both the probability path and the velocity field U, (G,l | Go, G.). A common selection decompose the probability density assumes independency for each node and edge (Hou et al. 2024 Qin et al. 2024 Eijkelboom et al.
For clarity, we denote the calligraphic style X heing the random variable, the plain X the relevant realizations and the bold symbol X the latent variables (parameters) that controls the distributons, i.c. X ~ p(2; X).
3

---

Published as a conference paper at ICLR 2026
p(..) Ne p(ece). Choosing TT-) Po (9) p1 (9). the boundary conditions follow (t( = 0(2; x.) 8 - W.), vi= {0.1} } with 6 the dirac function. This decomposition is further combined with linear interpolation to build the path, as introduced in (Tong et al. 2024), where,
2024) giving p())==(())p())====))) p(X))(())=
(r Go: G1) = our + or and uz (x Xo, X1) [ (Xolus
(5)
Pr (r(ewe) Go, G1) J.lEi oe Bo[Bolue and us (ewo Go. G1) [Li]uv [Eo]
where 0g and d₁ are two parameters to make the boundary condition satisfied, the selection is discussed in App. F.2 Similarly, discrete flow matching frameworks for graph generation (Qin et al. 2024, (Siraudin et al. 2024, Xu et al. (2024) is also based on linear interpolation, where the interpolant sampled from a categorical distribution whose probabilities are simply linear interpolation between the boundary conditions.
2.2 WHY WE NEED MORE THAN LINEAR INTERPOLATIONS FOR GRAPH GENERATION?
When we can use linear interpolation? Existing literature (Liu et al. 2023b Albergo & Vanden Eijnden 2023) argues that the probability path p. (X' Z) should be chosen to recover the optimal transport (OT) displacement interpolant (McCann, 1997). The (Kantorovich) optimal transport problem is to find the transport plan between two probability measures, Yo and 7/, with the smallest associated transportation cost defined as follows.
Definition 1 (Wasserstein Distance). Denote the possible coupling as II( m)), which is joint measure on x S whose marginals are no and 171 respectively. With of X(X,Y Y) being the cost of transporting the mass between X and Y, the Wasserstein distance is defined as,
inf SsLs c(X,Y) dx (x.
We(no, m))
rell(ro.m)
When the data follow Euclidean geometry and both boundary distributions po, Pl follow isotropic Gaussians, the path shown in Eq. (5) with or + 0 becomes solution to Eq. (Tong et al.) 2024).
However, given that graphs are non- Euclideen and interconnected objects violating the aformentioned conditions, linearly interpolating nodes/edges with Eq. (5) cannot guarantee the OT displacement in graph generation. Blindly using the approach will result in suboptimal probability path and lead to a problematic velocity estimation (Chen & Lipman 2024 Kapusniak et al., 2024). To illustrate, recall that the velocity is trained via either approximating a)
For both strategies, approximating the path similar to Fig. Ia two issues: 1) Most of the training points (G,) center around areas with high ratio, while the critical part for sampling is the region with intermediate ratio, i.c. the points corresponding to 0.8 < < 1. The velocity model has the risk of underfitting in those regions, posing a risk when deployed for sampling. 2) Especially for strategy a, when is small, the velocity through numerical approximation (Gz+dt G.) /dt may not even point correctly to the data distribution. Thus, when sampling, the model is difficult to determine the correct direction in the early stage, which will lead to convergence failure.
Grodtt - /fl or b) (G1 (G)--()
To establish a good velocity estimation that yields better training and generation dynamics, an ideal training probability path should: 1) adequately explore the landscape of G. that the velocity at intermediate points is well-trained. 2) correctly estimate the velocity pointing to the data distribution. is worth noting that the superior performance achieved by previous work (Siraudin et al.] 2224|] Qin et al. 2024) is partially attributed to their implicit manipulation of the path to satisty these conditions. The techniques used, including target guidance, time distortion, and stochasticity injection, are conceptually visualized in Fig. 1b with discussions in App. F.
3 METHODOLOGY
In this paper, we aim to build theoretically grounded framework for probability path construction in graph generative models without the reliance on heuristic path manipulations. To this end, we introduce Bures-Wa Wasserstein Flow Matching (BWFFlow), novel graph generation framework that built upon the OT displacement when modeling graphs with Markov Random Fields (MRFs). We begin by casting graphs in an MRF formulation in Section 3.1
We then derive the BWFlow
4

---

Published as a conference paper at ICLR 2026
framework in Section 3.2 by formulating and solving the OT displacement problem the MRF, thereby yielding the fundamental components, interpolations and velocity fields, for 7M-based graph generation. Finally, in Section 3.3] extend BWFlow to discrete FM regimes, enabling its application across broad spectrum of graph-generation tasks. A schematic overview of the entire BWFlow is illustrated in Fig.
3.1 GRAPH MARKOV RANDOM FIELDS
We borrow the idea from MRF as a remedy modeling the complex system organized by graphs. which intrinsically captures the underlying mechanism that jointly generates the nodes and edges. Mathematically, we assume the joint probability density distribution (PDF) of node features and graph structure as p(: p(X, E; X, W) p(2; X, W WEp(E; E W) where the node features and graph structure are interconnected through latent variables X and W. For node features X, we follow the MRF assumption in Zhu et al. (003)) and decompose the density into the node-wise potential SPi (v), , Vu e V and pair-wise wise potential 42 u, v), Vege E::
p(x: (,WW, W) of I exp (- Vo), moll2) II exp (woo [VVx (m) (VV - mc)]
vP(())
(2((.)))
with | the T/ norm, (.) the pseudo-inverse, V the transformation matrix modulating the graph feature emission, and μa, the node-specific latent variable mean. Eq. 7 can be expressed as colored Gaussian distribution in Eq. (8 given that Vx, ~ NN (vI + L)-1) ). We further assume that edges are emitted via Dirac delta, & ((W), yielding our definition of Graph Markov Random Fields (GraphMRF). The derivation can be found in App. A.2
Definition 2 (Graph Markov Random Fields). GraphMRF statistically describes graphs w) p(2;; ; X, W) p(E; W) where & ~ 5 (W) and
p(:: G) voc(At) ~ / (x, with X = vee( V 11) A (vI L) @ VV.
The is the Kronecker product, vec(.) is the vectorization operator and I is the identity matrix.
Remark 1. GraphMRF explicitly captures node-edge dependencies and preserves the advantages of colored Gaussian distributions. Section 3.2 will soon show that this yields closed-forn interpolation and velocity, and the probability path constructed from GraphMRFs remains on the graph manifold that respects the underlying non- Non-Euclidean geometry.
Remark 2. We emphasize that transforming a graph into the MRF domain actually enhances the modeling ability of global information encoded in the fow-frequency part of graph spectra. This parallels the behavior observed in diffusion models with latent space, where latent representations retain a larger proportion of low- www-freguency information, which is proven helpful in generative models. We refer to App. A.3 for discussion.
3.2 BURES- WASSERSTEIN FLOW MATCHING FOR GRAPH GENERATION
The optimal transport displacement between graph distributions. Given that the joint prob- ability of graphs decomposed as p()) = p(x; X, W)) W) and the measure factorized to Ms 1x, "ee with j (0, 1), the graph Wasserstein distance between 7io and rJ2, is written as,
(Graph Wasserstein Distance) dnw 91) W. (nG., n1,)) Wo(nx,, nx,) We Ne, )
We extend Haasler & Frossard (2024) and analytically derive the graph Wasserstein distance using the OT formula between Gaussians Dowson & Landau (1982); Olkin & Pukelsheim (1982); Takatsu (2010) (see Lemma proved in App. B.1 follows.
5

---

Published as a conference paper at ICLR 2026
Generation: sample with velocly; Gradi va(G)dt
the velocity (c
a. Sample Gu.
Go
Gradt
G
Convert back to Graph domain
b. Convert
graphs to MRFs
7o. (X)
Ma. (,7
Mig (7")
c. BW Interpolation between Nc; and Mc. to get
Schematic overview of BWFlow, which consists of: a) Sample the marginal graph condition Gg and G1; Convert graphs to MRFs; c) Interpolate to get intermediate points; d) Convert back to get GG e) Train velocity based on G₁ and f) Generate new points with the trained velocity.
Figure 2:
Proposition 1 (Bures-Ward Wasserstein Distance). Consider two same-sized graphs Go (No, Eo. and G1 pp &i) with V shared for two graphs, described by the distribution in Definition equipped with graph Laplacian matrices Lo and Lı satisfying 1) is
When the graphs Positive Semi-Defe Definite (PSD) and 2) has only one zero eigenvalue. The Bures- Wasserstein distance between these two random graph distributions is given by
dew(So. 91) = =1x XIl trace L Li 2
1/2
as V and a constant related to the norm of V The proof can be found in Section B.2
Based the Mares--Wasserstiin (BW) distance, we then derive the OT interpolant for two graphs, which is the solution of the displacement minimization problem described as,
G2 arg min (1 (Gu 9) tduw (9, 91).
(10)
The probability path. defined in Proposition [ prove the minimizer of the above problem has the form in Proposition 2 The proof can be found in App.
The interpolation is obtained through solving Eq. 10 with the BW distance
Proposition 2 (Bures- Wasserstein interpolation). The graph minimizer of Eq. 100,, G. (V,,,,% X.), have its node features following a colored Gaussian distribution, X, ~ NNX,, A!) with A, (vI L.) @ V and edges following & 5(W.), specifically.
1/2 E 1/2 (1- + | 112)
L 1/2
X, -1-1)xx
(11)
The interpolant provides a closed form for the induced probability path p(G. Go, G1) and the velocity v(G, Go. G1) that is easy to access without any simulation.
The velocity. We consider the reparameterization as in Eq. 33) and derive the conditional velocity (Ge) G1, Go) as in Proposition

---

Published as a conference paper at ICLR 2026
Proposition 3 (Bures-Wassee Wansersnasn velocity). For the graph G. following BW interpolation in Proposition 2
the conditional velocity time with observation G. is given as,
(r Gi).Gi W, diag(L, Le. Vr (X Go, Gi) 1-t (Xi X.)
(12)
with L, 2 TL, L.T and T = L (L L L
1/2 f/2 )1/ L
where W, = D: Lt and L, defined in Eq. 11I Derivation can be found in Section C.2
With Proposition 2 and Proposition 3 we are now able to formally construct the algorithms for Bures- Wasserstein flow matching. Taking continuous flow matching as an example, Algorithm and respectively introduce the training and sampling pipelines for our BWFlow.
Remark: Similar to denoiser/noise- prediicciooeiiooinnno parameterization, there exist multiple ways to establish numerically approximate the BW interpolation and velocity for training and inference. The choice will have an impact on training and sampling dynamics, such as stability and efficiency. We provide discussion of the design space and the trade-offs in App.
3.3 DISCRETE WERES-WWSSERSEEN FLOW MATCHING FOR GRAPH GENERATION
Up now working the scenario when p(X X, W) is Gaussian and p(E W) is Dirac distribution. However, previous studies have observed a significant improvement of the discrete counterpart the continuous graph generation models Vignac al. (2023a); Xu al. (2024): Qin it al. 2024). To benefit our model from such a nature, we derive the discrete Bures- Wasserstein llow matching for graph generation.
The discrete probability path. We design the probability path as discrete distributions,
(x, | Go. G₁) Categorical((Xx]))) Pe(euv Go, G,) B.Brnooll(([..)..mmm s.t. Po( ((Go, PI)()) 5(G1,-)
(13)
where W, = D. - L; with X, and L, defined the same in Eq. II We consider the fact that the Dirac distribution is special case when the Categorical/Bermoulii distribution has probability 1 or O, so the boundary condition (g) = 8(Go.) (g)) = 5(G1, holds. Even though we are not sampling from Gaussian distributions anymore, it is possible to approximate the Wasserstein distance between two multivariate discrete distributions with the Gaussian counterpart so the conclusions, such as optimal transport displacements, still hold. We left the discussion in App. D.2
The discrete velocity fields. The path of node features X', can be re-written Pe (2) (1 t) X,) + t- X2) so the conditional velocity can be accessed through v, (X, Go G (o(:X,) ())x))--i -(,, (1)]/(1-1)) However, the probability path of edges & shown in Eqs. 11 and 13 mixture of two boundary conditions given the non-linear interpolation. To this
cannot be written end, we derive in App. D.3 that the discrete velocity follows,
W.
v/ Go) = 21
(14)
W. W.)
where W, D: L, W. = diag( L.) L, with L,, L, defined in Eqs. and 12 respectively. With the interpolation and velocity defined, the discrete flow matching is built in Algonthms and
4 EXPERIMENTS
We evaluate BWFlow through both the plain graph generation and real-world molecule generation tasks. We first outline the experimental setup in Section followed by general model comparison in Section 4.2 Next, we conduct behavior analysis in Section 4.3) to understand the superior training/sampling dynamics BWFlow can bring.
7

---

Published as a conference paper at ICLR 2026
Algorithm 1: BWFlow Training
Algorithm 2: BWFlow Sampling
Input:
Ref. dist po and dataset D ~ pl. Output: Trained model So(Gr,
Input: Reference distribution po- Trained Model
Jo(G., Small time step dt,
Initialize model (C... I):
Output: Generated Graphs {Gi}.
while fo not converged do Sample batched {Gu} po. {G1)~ ~
Initialize samples (Go} -oo
Initialize the model pije (-1 C.) fo(C,, for
*+ Construct Prob. path Sample - (O, 1);
I +- 0 to 1 dt by di do
Calculate the BW interpolation
/+ x-prediction
p(G,, Go, G1) via Eq. (1]
Predict G1 + (- G.);
/x x-prediction
/* Velocity calculation
*/
( fa(G., t);
Calculate up (C, Co. G1) via Eq.
4
Loss calculation via Eq. optimizer.stepO;
/+ Numerical Samp ling
+/
Sample Greas G. + to G, Ct)dt
4.1 EXPERIMENT SETTINGS
Dataset. We evaluate the models' ability of plain graph generation on three benchmark datasets following Martinkus et al. 2022); Vignac et al. (023a);Berggmeiii et al. (2024), specifically, planar, tree, and SBM (stochastic blocking models) graphs. Two datasets, namely MOSES (Polykovskiy et al. 2018) and GUACAMOL (Brown al. 2019), are benchmarked to test the model performance on 2D molecule generation. For 3D molecule generation with coordinate data, we test the model on QM9 (Ramakrishnan al. 2014) and GEOM-DRUGS (Axelrod &
2020).
Metrics. In plain graph generation, the evaluation metrics include the percentage of Valid, Unique, and Novel (V.U.N.) graphs, and the average maximum mean discrepancy ratio (A.Ratio) of graph statistics between the set of generated graphs and the test set are reported (details in Section [.6). For molecule generation, we test two scenarios with and without bond type information, where the latter validates the capacity of our methods in generating the graph structures. To this end, we develop new relaxed metric to measure the stability and validity of atoms and molecules when bond types are not available. Specifically, the atom- atom-wise stability is relaxed as:
Stability of Atom i: s; = [13 E II Buy= JEN,
Σ big EV,], with the identity function II. JEN:
This means atom i is "relaxed-stable" if there is at least one way to pick allowed bond types (Bij) to its neighbors Nr so that their total exactly matches the expected valences EV, Such a relaxed stability of atoms (Atom.Stab.) inherently defines molecule stability (Mol.Stab.) and the validity of a molecule. addition to these metrics, distribution metrics including charge distributions and total variation for atom and angles are also used. Details in App. I.6
Setup. To isolate the impact from model architecture, we follow Qin et al. 2024 to fix the backbone model the same graph transformers. To fairly compare the impact of probability path construction, we disabled the path manipulation strategies such as time distortion and target guidance from Qin et al. (2024) and predictor-corrector in [Siraudin al. (2024) (the general comparison with all strategies enabled is left in App. I.2). More experimental details can be found in App. I.1
4.2 MAIN RESULTS FOR GRAPH GENERATION
Plain graph generation. Given that the training dynamics on these benchmarks are extremely unstable and performance continues to fluctuate significantly even after convergence (the transparent jagged curve in Fig. 3c gives visualization), we calculate the average results over the last 5 checkpoints (CAVG) to reflect the model behaviour after convergence. The exponentially moving average (EMA) with decay 0.999 is applied to the model. As illustrated in Table BWTlow consistently outperforms other benchmarks terms of A.Ratio and exceeds most competitors on Planar and SBM in V.U.N. The lone exception is the tree graphs, where model falls short. We attribute this gap to the fundamentally different spectral pattern for tree graphs, which we provide a discussion in App. A.3
8

---

Published as a conference paper at ICLR 2026
Table 1: Plain graph generation performance. The path manipulation methods, e.g. target guidance
in Qin et al. (2024) and predictor-correcto in (iraarud et al. (2024), are disabled to purely evaluate the impact of path construction. This table unifies the path distortion designs as in Table T and presents the CAVG results. We reproduce the tfateoof-the-ar art diffusion/llow model for comparison, while other models evaluated on best-checkpoint results are in the Table I1
The full statisties Table 13
Planar
Tree
SBM
Model
VUN.1
V.N.1.
A.Ratio
VUN.1
Ratio
Train sct
100
1.0
100
85.9
1.0
DiGress (CAVG) Vienac et al. 2023a
Diffasion
61.Saaa
a.9
a6.0
8,9a32
56.0as3
3.Suas
DisCo (CAVG) Na 2021
Diffasion
57,5425
9.0x14
55.0239
11.622
HSpeetre (Beggiicaler
2024
82.5
GraM (CAV per C hdre
Diflasion
45.4
3.2e0
52.5ex2
2-4a02
73.5
2.6e31
Cometh (CAVG) D Nirmaiin m
2124
Diffasion
80.5-5.
3.00os
84.5-74
2.0+e4
77.5+57
4,7-06
DeFuG (CAVG) Q2n
Flow
77.5ts37
3.5
83,5am0
1,9anc
85.0c11
3/424
BWFlow
81.5tas
Dataset
Interpolation
Metries
V.U.N(%)
Sta.
Atom, Stab.
Connected( %))
Charge(10
Atom(10"")
Anglest")
QM9
MiDi
1.01
13
93.98
99.60 .6.0
99.21
0.2
3.7
2.21
FlowMol
1.01
87.53
88.45
99.13
99.09
0.4
4.2
2.72
(with
BWFlow
1.01
96.45
97.84
99.84
99.24
2.3
GEOM
78.23
(with
FlowMol BWFlow
87.75
73.53
3.96
Table 2: Quantitative experimental results on 3D Molecule Generation with explicit hydrogen.
Molecule generation. Table gives the results on the 3D molecule generation task with explicit hydrogen, where we ignore the bond type but just view the adjacency matrix as a binary one for validating the power of generating graph structures. Interestingly. the empirical results show that even without edge type, the models already can capture the molecule data distribution. And our B WFloww significantly outperforms the SOTA models, including MiDi Vignac et al. (2023b) and FlowMol Dunn & Koes (2024). We believe a promising future direction is incorporate the processing of multiple bond types into our framework, which would potentially raise the performance by a margin.
4.3 BEHAVIOR ANALYSIS
BWFlow provides smooth velocity in probability paths. To illustrate how BWFlow models the smooth evolution of graphs, we compute the A.Ratio on SBM datasets (the figures for the others are in Fig. O be- tween generated graph interpolants and test data for i e [0, 1J, as shown Fig. 3al In contrast to the linear (arithmetic) interpolation, BW interpolation initially exposes the model to more out- -istriibuiutn sam- ples with increased A. Ratio. After this early explo- ration, the A. Ratio monotonously converges, yielding smooth interpolation between the reference graphs and the data points. This behavior enhances both the model robustness and velocity estimation, which helps in covering the convergence gap in the generation stage as in Fig. Ic In comparison, harmonic and geometric interpolations step outside the valid graph domain, making the learning ill -oo-pdsed.
Table 3: Model performance in small sam- pling steps. DeFoG-1 and DeFoG 2 are with- out and with path manipulation respectively.
Planar
Model
V.U.N.1
A.Ratio
V.U.N.I 1
A.Ratio.
Cometh
17.0=
7,5x27
43.0+
3.3+00
DeFoG-1
24.5
6.6an9
32.5
7.9
DeRoG-2
72.0274
6.3a19
47.522n
3.1209
BWFlow
77.0.37
4.1
52.0.s.
2.61n9
The impact of interpolation methods on the model performance. Fig. 3b illustrated bar plot that compares interpolation methods on the ability of generating valid plain graphs measured by V.U.N., which shows the superiority of BW interpolation in capturing graph distributions (full results in Table 7) Fig. 3e illustraaed an example (in planar graph generation) of the convergence curve at the training stage, which suggests that BWFlow can bring faster convergence speed compared to FM methods constructed with linear (arithmetic) interpolations. Additionally, we test when the sampling step size is only 3% of the original one (30 vs 1k), and report the results in Table The results show that BWFlow significantly succeeds in generating high-quality graphs when sampling steps small.

---

Published as a conference paper at ICLR 2026
(a) evolution graph statistics ra-(b) impact of interpolation (c) Convergence analysis of BW-Flow tio along the probability path.
methods on the performance. and flows with linear interpolations.
Figure 3: Ablation studies for Bures-Wassenee Flow Matching.
5 DISCUSSION AND FUTURE WORK
In this paper, we introduce BWFlow, a flow matching model that intergrates the non-Euclidean and interconnected properties of graphs for graph generation. While show BWFlow exhibits outstanding performance in various graph generation tasks, there still remains few solid future work.
Extension to multiple relation types. As our framework is built upon the interpolation parameterized by the Graph Laplacian, is not casily generalizable to the graph generation with multiple edge types. We made preliminary attempts in App. F.5 but comprehensive design is still required.
Efficient Probability Path Construction. Our BW interpolation induces an extra 0(N3) linear algebra operations (noted not reflecting the model complexity) in path construction. When scaled up to large but sparse graphs, the complexity can be reduced to O(TN2) (with T the iteration steps) through iterative solving such as least-squares with QR factorization. We conduct preliminary experiment for this in App. and leave further development as future work.
The generality of GMRF. As diseussed in App- A.3 GMRF enhances algorithm's 's ability in modelling graphs with narrow spectral spread while does not improve on graphs with wide spectral spread. Thus, adapting GMRF to graphs with more complex spectral patterns remains promising direction.
ACKNOWLEDGEMENTS
K.J. supported by the UKRI Engineering and Physical Sciences Research Council (EPSRC) [grant number EP/R5131433 43/1]. The authors thank Jinmei Zhang, Yiming Pascal Frossard for the valuable inspirations and discussions at the early stage of this project, as well as the anonymous reviewers for their helpful comments and insights.
Qin, Isabel Haasler, and
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Michael S. Albergo and Eric Vanden-Eijnden. Building normalizing flows with stochastic interpolants. In ICLR. OpenReview.ne,, 2023.
Simon Axelrod and Rafael Gómez- Bombarelli. GEOM: energy-annotated molecular conformations for property prediction and molecular generation. CoRR, 0os/2000.005531 2020.
Eric Bach, Simon Rogers, John Williamson, and Juho Rousu. Probabilistic framework for integration
of mass spectrum and retention time information in small molecule identification. Bioinformatics, 17113) 2020. ISSN 1367-4803. doi: 10. 10.003/hionfommaicc//aaaaaaa URL
https://doi.org 16. 1093/bio1 http://loo.normmma.cs///.b...oe o.t.://ooooooooooooooooooooooooa
Andreas Bergmeister, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Efficient and scalable graph generation through iterative local expansion. In ICLR. OpenReview.net, 2024.
Rajendra Bhatia, Tanvi Jain, and Yongdo Lim. the busse-wwse distance between positive definite matrices. Expositiones Mathematicae, 37(2):165-191, 2019. ISSN 0723-0869. doi: rect com/
https///oo..rgg//0000066/eeemmah scckence/arriclleg//////2228
002. URL htttps://ww.sce..e.
Camille Bilodeau, Wengong Jin, Tommi Jaakkola, Regina Barzilay, and Klavs Jensen. Generative models for molecular discovery: Recent advances and challenges. Wiley Interdisciplinary Reviews: Computational Molecular Science, 12(5):e1608) 2022.
Nathan Brown, Marco Fiscato, Marwin H. S. Segler, and Alain C. Vaucher. Guacamol: Benchmarking models for de novo molecular design. J. Chem. Inf. Model., 599)) 2019.
Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. A continuous time framework for discrete denoising models. In NeurlPS, 2022.
Andrew Campbell, Jason Yim, Regina Barzilay, Tom Rainforth, and Tommi Jaakkola. Generative flows on discrete state-spaces: Enabling multimodal flows with applications to protein co-design. In ICML. OpenReview.net, 2024.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. CoRR, abs/1805. 1973, 2018
Ricky T. Q. Chen and Yaron Lipman. Flow matching on general geometries. In ICLR. OpenReview.net, 2024.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential equations. In NeurIPS, pp. 6572-6583, 2018.
Xiaohui Chen, Jiaxing He, Xu Han, and Liping Liu. Efficient and degree-guided graph generation discrete diffusion modeling. In ICML, volume 202 of Proceedings of Machine Learning Research, pp. 4615- PMLR, 2023.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans, Scalable deep generative modeling for sparse graphs. In ICML, volume 119 of Proceedings of Machine Learning Research, pp. 2302-2312 PMLR, 2020.
Nathaniel Lee Diamant, Alex M. Tseng, Kangway V. Chuang, Tommaso Biancalani, and Gabriele Scalia. Improving graph generation by restricting graph bandwidth. In ICML, volume 202 of Proceedings of Machine Learning Research, pp. 7959-7959. PMLR, 2023.
D.C Dowson and B.V Landau. The fréchet distance berween multivariate normal distributions. Journal of Multivariate Analysis, 12(3):450-455, 1982. ISSN 0047-259X. doi: https://doi.or// 10. 00.0066/0047-250xx88)99007777777 URL /ttp://wweeeeeeeeeee.ooooooo//oo
Brricleep11/00077522820000
Ian Dunn and David Ryan Koes. Mixed continuous and categorical flow matching for 3d novo molecule generation. ArXiv, pp. arXiv-2404, 2024.

---

Published as a conference paper at ICLR 2026
Floor Eijkelboom, Grigory Bartosh, Christian Andersson Naesseth, Max Welling, and Van-Willem van de Meent. Variational flow matching for graph generation. In NeurlPS, 2024.
Itai Gat, Tal Remez, Neta Shaul, Felix Kreuk, Ricky T. Q. Chen, Gabriel Synnaeve, Yossi Adi, and Yaron Lipman. Discrete flow matching. In NeurlPS, 2024.
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: A scalable approach to domain- agnostic labeled graph generation. In WWW, pp. 1253-1263. ACM / IW3C2, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pp. 855-864. ACM, 2016.
Isabel Haasler and Pascal Frossard. Proceedings of Machine Learning Research, pp. 1873-1881. PMLR, 2024.
means of graphs. In AISTATS, volume 238 of
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. In The First Leurning Graphs Conference, 2022. URL https: wtt.///tseeppeeeeeeeeeeeeee//e/e
d KKC.en/IIMAACCKKKKIIKK
Doron Haviv, Aram-Alexandre Pooladian, Dana Pe'er, and Brandon Amos. Wasserstein flow matching: Generative modeling over families of distributions. CoRR, abs/2411.0066 1,00698, 2024.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. NeurIPS, 2020.
Xiaoyang Hou, Tian Zhu, Milong Ren, Dongbo Bu, Xin Gao, Chumming Zhang, and Shiwei Sun. Improving molecular graph generation with flow matching and optimal transport. CoRR, abs/2411 1.05676, 2024.
John Ingraham, Vikas K. Garg, Regina Barzilay, and Tommi S. Jaakkola. Generative models for graph-based protein design. In NeurIPS, pp. 15794-15805, 2019.
Keyue Jiang, Bohan Tang. Xiaowen Dong, and Laura Toni. Heterogeneous graph structure learn- ing through the lens data-generating processes. In The 28th International Conference on Artificial Intelligence and Statistics, 2025. URL hattps://openreeeeee JHKOQBKAYу
Jaehyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with diffusion mixture. In ICML. OpenReview.net, 2024.
Kacper Kapusniak, Peter Potaptchik, Teodora Reu, Leo Zhang, Alexander Tong, Michael M. Bron- stein, Avishek Joey Bose, and Francesco Di Giovanni. Metric flow matching for smooth interpola- tions on the data manifold. NeurIPS, 2024.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/ abs/1611.073008 2016.
Mufei Li, Eleonora Kreacic, Vamsi K. Potluru, and Pan Li. Graphmaker: Can diffusion models generate large attributed graphs? CoRR, 13.333,,, 2023.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William I.. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks. In NeurlPS, pp. 4257-4267, 2019.
Yaron Lipman, Ricky T. Q. Chen, Heli Ben-Hamu, Maximilian Nickel, and Matthw Le. Flow matching for generative modeling. In The Eleventh International Conference Learning Repre- sentations, 2023. URL h / http://pppneeeeee..eeeee wwwp:/vwwwwweeetooouuutieeee wot.ee//oooididddoweo.o....r.. PQVMRDCJT9E
Yaron Lipman, Marton Havasi, Peter Holderrieth, Neta Shaul, Matt Le, Brian Karrer, Ricky T. Q. Chen, David Lopez-Paz, Heli Ben-Hamu, and Itai Gat. Flow matching guide and code. CoRR, abs/2412.062644, 2024.
Chengyi Liu, Wenqi Fan, Yunqing Liu, Jiatong Li. Hang Li, Hui Liu, Jiliang Tang, and Qing Li. Generative diffusion models on graphs: Methods and applications. In IJCAI, pp. 1702-6711. ijcai.org, 2023a.
12

---

Published as a conference paper at ICLR 2026
Xingchao Liu, Chengyue Gong, and Qiang Liu. Flow straight and fast: Learning generate and transfer data with rectified flow. In ICLR. OpenReview.net, 2023b.
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. SPECTRE: spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 15199, PMLR. 2022.
Robert J. McCann. A convexity principle for interacting gases. Advances in Mathematics, 128(1): 153-179, 1997. ISSN 0001-8708. doi: https://ooooor/00.00006vvaaa111. w/www.scien.n rect. com htt.://deee..c.cocccooococee//re wwtp/////ccieeeeerrr.a//////////
URL https:
Giorgia Minello, Alessandro Bicciato, Luca Rossi, Andrea Torsello, and Luca Cosmo. Gener- ating graphs via spectral diffusion. In The Thirteenth International Conference on Learning Representations, 2025. URL https:::: http::::////peeevvee.. wtt.:arrewiieee.eeeoorrreae wtt.:/ee....oommeaaaaa.........
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permu- tation invariant graph generation via score- based generative modeling. In AISTATS, volume 108 of Proceedings of Machine Learning Research, pp. 4474 4484. PMLR, 2020.
I. Olkin and F. Pukelsheim. The distance between two random vectors with given dispersion matrices, Linear Algebra and its Applications, 48:257-263, 1982 ISSN 0024-3795. doi: https://dii.or 10. 10.1001660224-3775988)0011144444 URL http:////.........te//////..eee.
brriccle//111022433522991111 10110000000011000222333333333120
com/ science/
Nagham Osman, Keyue Jiang, Davide Buffelli, Xiaowen Dong, and Laura Toni. LGDC: Latent graph diffusion via spectrum-preeseriing coarsening. In New Perspectives in Graph Machine Learning, 2025. /tt. wtwp://wwwwweeeeeeeeooooooeee... 765oou
Yong-Hyun Park, Mingi Kwon, Jaewoong Choi, Junghyo Jo, and Youngjung Uh. Understanding the latent space of diffusion models through the lens of riemannian geometry. In NeurIPS, 2023.
Daniil Polykovskiy, Alexander Zhebrak, Benjamín Sánchez-Lengeling Sergey Golovanov, Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, Artur Kadurin, Sergey I. Nikolenko. Alán Aspuru-Guzik, and Alex Zhavoronkov. Molecular sets (MOSES): A benchmarking platform for molecular generation models. CoRR, ab8/ 2018.
Lram-Alexandee Pooladian, Heli Ben- Gen-Hamu, Carles Domingo-Enrich Brandon Amos, Yaron Lipman, and Ricky T. Q. Chen. Multisample flow matching: Straightening flows with minibatch couplings. In ICML, volume 202 of Proceedings of Machine Learning Research, pp. 28100-28 201227 PMLR, 2023.
Yiming Qin, Manuel Madeira, Dorina Thanou, and Pascal Frossard. Defog: Discrete flow matching for graph generation. CoRR, abs/2410.04263, 2024.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: graph markov neural networks. ICML, volume 97 of Proceedings of Machine Learning Research, pp. 5241-5250 PMLR, 2019.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):17,,200 2014.
Antoine Siraudin and Christopher Morris. Principled latent diffusion for graphs via laplacian autoencoders, 2026. URL httphppps//aeadk.orr///////22...
Antoine Siraudin, Fragkiskos D. Malliaros, and Christopher Morris. Cometh: A continuous-time discrete-state graph diffusion model, 2024.
Yang Song, Jascha Sohl-Dickstein. Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In ICLR. OpenReview.net, 2021.
13

---

Published as a conference paper at ICLR 2026
Hannes Stärk, Bowen Jing, Chenyu Wang, Gabriele Corso, Bonnie Berger, Regina Barzilay, and Tommi S. Jaakkola. Dirichlet flow matching with applications to DNA sequence design. In ICML. OpenReview.net, 2024.
Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous-time discrete diffusion models. In ICLR. OpenReview.net, 2023.
Asuka Takatsu. On wasserstein geometry of gaussian measures. Probabilistic approach to geometry. 57:463 472, 2010.
Ben Taskar, Picter Abbeel, Ming-Fai Wong, and Daphne Koller. Relational markov networks. Introduction statistical relational learning, 175:200, 2007.
Alexander Tong, Kilian Fatras, Nikolay Malkin, Guillaume Huguet, Yanlei Zhang, Jarrid Rector- Brooks, Guy Wolf, and Yoshua Bengio. Improving and generalizing flow-based generative models with minibatch optimal transport. Trans. Mach. Learn. Res., 2024, 2024.
Clément Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang. Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In ICLR. OpenReview.net, 2023a.
Clément Vignac, Nagham Osman, Laura Toni, and Pascal Frossard. Midi: Mixed graph and 3d denoising diffusion for molecule generation. In ECML/PKDD (2), volume 14170 of Lecture Notes in Computer Science, pp. 560-576. Springer, 2023b.
C. Villani and American Mathematical Society. Topics in Optimal Transportation. Graduate studies in mathematics. American Mathematical Society, 2003, ISBN 9781470418045. URL
https://booke wwwpooooooooooe.o.oooooooooooo.. google. Co. www..uu/boon ww/books//// 2
Fu-Yun Wang, Ling Yang. Zhaoyang Huang, Mengdi Wang. and Hongsheng Li. Rectified diffusion: Straightness is not your need in rectified flow. CoRR, abs/2410.07303, 2024.
Martin Weigt, Robert A. White, Hendrik Szurmant, James A. Hoch, and Terence Hwa. Identification of direct residue contacts in protein-proted interaction by message passing. Proceedings of the National Academy of Sciences, 106(1):67-72, 2009. doi: 10. 10107///paaa.0005223100000 URL 000.3231080333333
https: www http://wwwwap.a..ooooo/////////a
Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng. Ma-
hashweta Das, and Hanghang Tong. Discrete-ste state continuous-time diffusion for graph generation. arXiv preprint arXiv:2405. 1416, 2024.
Menglin Yang, Min Zhou, Zhihao Li, Jiahong Liu, Lujia Pan, Hui Xiong, and Irwin King. Hyperbolic graph neural networks: review of methods and applications. CoRR, abs/2202.118552 2022.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In ICML, volume 80 of Proceedings Machine Learning Research, pp. 5694-5703. PMLR, 2018.
Meng Yu and Kun Zhan. Bias mitigation in graph diffusion models. In The Thirteenth International Conference on Learning Representations, 2025. URL
view. net/ forum?
id==S
Xiaojin Zhu, John Lafferty, and Zoubin Ghahramani. Semi-supervised learning: From Gaussian fields to Gaussian processes. School of Computer Science, Carnegie Mellon University, 2003.
Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. A survey on deep graph generation: Methods and applications. In LoG, volume 198 of Proceedings of Machine Learning Research, pp. 47. PMLR, 2022.
14

---

With such a modelling, the Published as a conference paper at ICLR 2026
A GRAPH MARKOV RANDOM FIELDS: BACKGROUND AND THEORY
A.1 BACKGROUND OF MARKOV RANDOM FIELDS
Markov random fields (MRFs) were originally developed to describe the dynamics of interconnected physical systems such as molecules and proteins (Weigt et al.) 2009. Bach et al. 2020). MRFs are energy-based models that have the following probability density:
1 Z (Fee) Z
p(2)
(15)
where the energy (X) is used to describe the whole connected system. For instance, in the molecule system that consists of atoms and bonds, the overall energy is decomposed into the atom-wise potential yo (v), Ve V/ and bond-wise potential Φ22(u, v), Veuv E. MRFs serve as a natural and elegant way to describe general graph systems.
The energy-based models have an intrinsic relationship with generative models. As an example, et al.) (202T) derived the relationship between diffusion models and the Langevin dynamics, which is used to describe the evolution of an energy-based based model. It is shown that the diffusion models are trying approximate the score function V lo)) In the energy-based models, the score function is just the gradient of energy, V logp(2) -VxU(X) and the Langevin dynamics becomes transiting between states with different energies.
The idea of our paper originated from the two facts: MRFs are energy based model describing con- nected systems, and the energy-based models have their intrinsic relationship with the diffusion/flow models. Thus, if model is required to describe the evolution of the whole graph system, we believe is natural to consider constructing a probability path for two graph distributions with MRFs as the backbone.
A.2 DERIVATION OF GRAPH MARKOV RANDOM FIELDS
The hierarchical graphical model for GraphMRF visualized in Fig. following decomposition holds:
p(g G) = =(X,E W.)
= 1 E X, W) X, W)
= =(( X, W))(( W)
where the node features and graph structure interconnected through latent variables X and W.The first step follows the chain rule, and the second steps utilize the properties of the Markov Random Fields, i.e 1) the graph structure serves as prior and is generated first, and 2) the node features are emitted based on that structure. This makes W alone governs the structural prior, i.c. P(E X) P(ε W). For notation clarity, we distinguish the dependency along same hierarchy in the graphical model by using p(- I-) with the difference hierarchies as p(::)) (1'' v.s. ";").
We then show the derivation of Definition 2 which is restated here:
Definition 3 (Graph Markov Random Fields). GraphMRF statistically describes graphs as, p(: G) E p(x; X X, W) p(E; W) where & 8 ((W) and voc(X) .V (x,At) with X vec( V 14), = (vI L) & V.. The the Kronecker product, vec(-) is the vectorization operator and I the identity matrix.
(16)
Derivation:
We start from X. xc I exp (- do)l -,o1
II exp (wav [(Vx, x, (
x, [w)]}
(17)
We assume that the linear transformation matrix has dimension V e K' given that x, k and define a transformed variable
h V T.a 1by E TR
stacking as H DIKK""
(18)
15

---

Published as a conference paper at ICLR 2026
W
X
3
X
Figure 4: The graphical model for GraphMRR.
The probability becomes
P(H:X,W) oc
II exp (v de) do)llhel? [3] II exppfeen Wao Nilkie)
(19)
Then, the terms inside the exponent in Eq. 19 become
E(v (v+ do)llhee?
Σ
Wav h E( + h.) + Σ
Wer highe
u,
=- E -- (v du))mu Wwo Ihw
where the Kronecker delta uv 1 if u and O else. We define squared matrix A to arrange the inner term, which can be written as,
A' = vI L with A = (v du) du) Wwe- is the identity matrix. Thus, the exponent in compact matrix form gives
(20)
h1
h2
Tr(H' Tr(H'A'A) A'H), where H.
(21)
:
hpy
is possible to rearrange the exponent as
Tr(H A'H) vec(H)) (A @ I) voc(?(),
(22)
where a denotes the Kronecker product. This is exactly in the form of multivariate colored Gaussian.
Thus, the joint distribution of vec(H) (of dimension (V(K") is given by
vec(Ht) NN(0, (vI +)) Ik.).
(23)
Recall that N. = x. Mun we obtain
vec(H) (I a V) vec(2)) - vec(p))
(24)
Since the transformation is linear, the distribution over X' remains Gaussian. By the properties of linear transformations of Gaussians, if
vec(?) ~ (Vve(((), En). vec(2) (I Vt) vec(?),
(25)
then
vec(x') AV ( (I)v vec(u), (I, Vi) En (Ln Vi))). Thus, using the mixed-product property of the Kronecker product,
(26)
(T ( L)-1 @ [) @ Vt) -L (L+ o (viV') (V Finally, the joint distribution over X' is
(27)
voo(X)~N(X ~ ~N(X,
with X (I Vt) voc(H) = ())
(28)
and Σ= (vI+ @ (viv'),
We the following lemma:
Lemma 1, Given two invertible matrices A and B, their Kronecker product satisfies (A B)
A @ B
So that get
~ (o((2)~N(XXX))) with X
(29)
which ends the derivation.
16

---

Published as a conference paper at ICLR 2026
A.3 THE APPLICABILITY OF GRAPH MARKOV RANDOM FIELDS
In the experiments, we realize that our BWFlow does not achieve satisfactory results in tree dataset. This evokes to investigate why this happened, and what properties tree graphs preserve that Graph Markov random fields fail to capture. In what follows, we will provide comprehensive analysis on the GMRF and show why GMRF achieves slightly worse performance in trees. We summarize the finding as,
Take-home Message: Modelling Graphs with GMRF enhance algorithm's 's ability in capturing the global properties encoded in the low-frequency components of the spectra, while retaining a similar capacity in capturing the high frequency components that encodes the fine-grained structures. With such behavior, graphs with narrow spectral spread are more suitable to be modelled by GraphMRF. In datasets requiring less global modeling ability, BWFlow still preserves comparable capacity to the SOTA models.
We now formally analyze GMRF, Given that our GMRF have an explicit form to constrain the graph distribution, it inherits certain inductive biases and we have to properly understand their generality, ie., when could use GraphMRF to model the distribution.
Plain graph Markov random fields. To understand the scenarios which we can utilize MRF to model graphs, we first consider the simplest case when V is rectangular orthogonal (semi semi-orthogonal) matrix such that VVV = and the mean O, the probability density becomes,
P(X,L) x exp(-X (L x)
exp(- Σ (u,r)eE
Wwo - xx)²² 22 -v - "
(30)
As 0, the exponent term inside becomes
S(X, L)
Wur( -xx)² =trace X XX LX), (u,n)eE
Σ
(31)
where we name S(X, L) as the smoothness of the graph features. The smoothness measures how similar the neighbors connected are. For instance, there exists an edge between node u and v weighted as W... the likelihood will be higher if x, and x. be similar, that | =x.l² are small. This suggests that the probability will be higher the ((X,L, L) is small.
With this pattern, it can be already shown that GMRF capture the graphs with high smoothness. In the literature of spectral graph theory, the smooth graphs are commonly preserve highly dense low-frequencey components, which mainly responsible for representing the global properties. Such a pattern can model the homophily, smoothness, planarity, and clustering of graphs, which suggest why BWFlow excels in modeling distributions such as SBM and planar graphs
Graph Markov random fields with embeddings. Now we move one step further to consider the graphs with linear transformer matrix V. we can consider alinear transformer from By to hop i.e., giving hy Vx.- je which gives the probability density as,
P(H. oc exp(- trace(H (L+ + +I))() exp(- wwell he 1-12- 222- Σ ha 12)
(32)
where, 76- [ h NN
Linear transformation provides a map from the feature space to the latent space, which can be considered as an embedding method to empower the models with better expressiveness. As simple example, when the provides negative projection, the mapping can capture the heterophily relationships, which means the nodes connected are dissimilar.
Coincidently, this aligns well with the famous embedding method Node2Vec as in Grover Leskovec (2016), where the edge weights are proportional to the negative distance, or the inner product of the embeddings. i.e..
W.. exp(-I/Va.,, Va. Va,
(33)
In Diang et al. (2025) it is derived that learning the parameters of MRFs is intrinsically equivalent to learning embeddings similar to Node2Vec. As such, the expressiveness of MRFs are as good as Node2Vec, which grants its usage to molecule graphs, protein interaction networks, social networks,
17

---

Published as a conference paper at ICLR 2026
and knowledge graphs. In our paper make the assumption is that the linear mapping from X the observation is shared. This requirement translates to that the two graphs should have the same embedding space and feature space, which is practical if the reference distribution and data distributions share the same space.
Graphs without features. We wish to emphasize that even though the GraphMRF is constructed under the assumption that graph features exist, it is capable of modeling the non-attributed graphs, such planar and SBM graphs. To do so, consider the optimization over the Rayleigh function: is shown that, if U1,.... Uk-1 are orthonormal cigenvectors for ......,ARRJ1 then the eigenvalues satisfy,
x² Lac
A
min R(x), with R(x) x: x
(34)
2=0
In such scenario, the graphs eigenvectors Us serve as an intrinsic graph feature. noted that R(x) is the normalized form of the smoothness in Eq. (30). This means that if the graphs are smooth (the spectrum of the graph Laplacian focuses on the low-frequency components), the MRF model would give higher probability compared to the graphs with wider spectral spread. This pattern emphasizes the low- frequency components when building the graph interpolations, which makes the whole algorithm succeed in modelling the graph distributions of most plain graph datasets, such Planar, SBM, TLS, COMM20 datasets. There is no surprise that our algorithm gives better training and sampling dynamics in those datasets.
longer related to the actual node features, but instead, the
It is also worth pointing out that there exists exceptions that GraphMRF is less capable of modelling. Tree graphs are an example of graphs with wider spectral spread. They are acyelic and minimally connected, lacking local clustering and cycles that would result in a highly concentrated spectrum. For this type of graphs, BWFlow will not have a significant benefit in modelling capacity. However, graphs with wider spectral concentration are relatively rare and most are artificial, such as scale-free and expander graphs. In contrast, real-world graphs, such as social networks, citation graphs, traffic networks, and molecular graphs, often contain cycles and densely connected subgraphs. They exhibit strong community structure, local regularity and high redundancy. These characteristics contribute to highly concentrated Laplacian spectrum, with most eigenvalues clustered together, which aligns well with the GraphMRF prior. Thus, we believe using GMRF and BWFlow to solve graph generation in general a valuable method.
Connection to Latent Generative Models. Although BWFlow not directly formulated as a latent diffusion/flow model, it shares strong conceptual connection with this family of generative approaches, especially for graphs (Siraudin & Morrs 2026, Osman et al. 2025). Latent diffusion typically aims to 1) improve computational efficiency and 2) map data into smoother space where modeling becomes easier. BWFlow does not perform dimensionality reduction, but is motivated by similar principle: transforming graphs into smoother domain can stabilize training and improve sampling efficiency. In BWFlow, this domain is the MRF space, which is manually constructed rather than learned, but exhibits properties desirable in latent diffusion. As discussed previously, transforming a graph into the MRF representation amplifies low- now-frequeccy (global) components, paralleling observations in latent diffusion where early latent representations retain larger proportion of low-frequency information-as an effect known to benefit generative modeling Park et al. (2023). This perspective provides an alternative interpretation of why BWFlow yields robust and efficient generation dynamics.
Furthermore, this viewpoint suggests a promising direction for simplifying our current design. In the present implementation, the MRF representation is mapped back to the graph domain before learning the velocity field via graph transformer. From a latent-diffusion standpoint, an alternative would be to directly parameterize the velocity in the MRF space and train via KL divergence between colored Gaussian distributions, potentially improving efficiency. We leave this direction for future exploration.
18

---

Published as a conference paper at ICLR 2026
B PROOFS
B.1 WASSERSTEIN DISTANCE BETWEEN TWO COLORED GAUSSIAN DISTRIBUTIONS
We first prove the lemma that captures the Wasserstein distance between colored Gaussians, which will be used in deriving our
distances in graph generations.
Consider two measures Too ~ -N (μo: Eo) and - (11, E1), describing two colored Gaussian distributions with mean μoo li and covariance matrices Ea, Et. Then the Wasserstein distance between these probability distributions is given by
Lemma 2.
(W2 (100 m))² I| - m1ll Tr Eo + 21 - 2 22000 2, 20000 20/22/ )
Proof. We first state the following proposition.
Proposition 4. (Translation Invariance of the 2- 2-Wasserstein Distance for Gaussian Measures) Consider two measures no -V (Jon En) and rp -N Et) and their centered measure t = N (0, En) and in = N (0, E1), the squared Wasserstein distance decomposes as
W (no, m) ) = 11400 1--1 1112 W (No, in)
Proof:
Consider two random vectors X.Y y distributed as 7ju. 71-
X= no X.Y- ) μr + D, with X .n.. 5 7n For any coupling (X,)), we consider the expected squared Euclidean distance,
Ex X - y1 Ex,y 1400 1 (& - 5)
(35)
| - 111 2 [n #l, - -5) + 1x
Since X and y both have zero mean, we have B| - - 0 the cross-term vanishes. Thus,
E|xx 20 140 11 1 BI 5112
(36)
Take the definition of 2- Wasserstein distance, the infimumm over all couplings directly yields
S ||x 1 dx(x.)).
(W)((oom))) inf rell(
(37)
p4 - |411111 2 W (fj. i1))
This completes the proof of Proposition
Now prove the flowing proposition, which will give Proposition 5. Given two centered measures as ño = - (0, En) and in = =N En)
lemma.
W (ñ.. mn) Tr
- TT
- 2 22z) 2
(38)
proof. The coupling x of n and in is a joint Gaussian measure with zero mean and covariance matrix
Σ ( Σ, )
Eg 20,
(39)
where C' the cross-covariance and means the matrix is positive semi-definitive (PSD). The expected squared distance between the two random vectors (X,)) drawn from i is then described as,
E| - 2 Tx -)) =TrEEo) Tr(En) -2 Tr(C).
(40)
The definition of Wasserstein distance gives,
We(%oom))= inf rell(7o.m)
E| - 2
(41)
19

---

Published as a conference paper at ICLR 2026
Thus, minimizing the Wasserstein distance is equivalent to maximizing Tr(C) over all C' subject to the joint covariance is positive semi definief (PSD). It turns out (see Dowson & Landau (1982);
Olkin & Pukelsheim [1982;
Takatsu 2010) that the condition in Eq. (39 is equivalent to.
En" 1/1/33 CE; 1/2 has operator norm s 1
(42)
So we denote
K 20 1/2 C with K op $ 1. Then
Tr(C)= Tr (2) 1 )= = Tr TI(KE//2"'
Using von Neumann trace inequality, its trace inner- umerr-prdduct with K is maximized by choosing K I on the support.
Tr(KA)= (TKK))))(MM2))) M VAT x E 1//
max klys1
Hence the optimal value of Tr(C) is
Tr(C") Ir (1r(( 2, 1/2
Substituting this optimal value into the expression of Wasserstein distance, we obtain
W (No. 7n) Tr +Tr())) Tr - U2
(43)
This completes the proof of proposition 5 Taking Proposition and Proposition 5 together, we proved Lemma
B.2 DERIVATION THE GRAPH WASSERSTHIN DISTANCE UNDER MRF
We then prove the Bures-Wasserstein distance for two graph distributions. We restate Proposition
Proposition 6 (Bures-Wasserster Wasserstein Distance). Consider two same-sized graphs Go =p (Xo, En) and G1 p (1) with V shared for two graphs, described by the distribution in Definition 2 When the graphs Positive Semi- Meni-Definite (PSD) and 2) has only one zero eigenvalue. The Bures- Wasserstein distance between these random graph distributions is given by
equipped with graph Laplacian matrices Lo and L1 satisfying 1) is
daw dew 91) Xo -x,1- BTT L' L 2 112 1
1/2)
(44)
as 0 and is constant related the norm of V.
Specifically, Definition 2 uses graph Markov random fields to describe graph as
p(; = X, W) p(x;; X, W) p(E; W) where 8( (W) and vec(X)) - (()))~(((XX)))))) (X) with X = vec V 4)) A = (vl L
(45)
With the graph Wasserstein distance defined as,
(Graph Wasserstein Distance) Agw(Gu) G1) We (1g.. m1g,) (e 1x,) W (T (T)))
We first consider calculating Wc(nx, nx, Specifically, this is the distance between two colored Gaussian measures where
" N (14 Σx
i= 0,
(46)
where u = V, 2 and 2 A₁ = (vI +.)+ L)
where we first assume that these two Gaussians are emitted from different linear transformation matrices Vo and V, This will bring us the most general and flexible form that could be universally applicable, and potentially can bring more insights to future work. Next, we will inject a few assumptions arrive at practical form for building the flow matching models.
20

---

Published as a conference paper at ICLR 2026
An important property of Kronecker product: Given two invertible matrices A and B, their Kronecker product satisfies (A @ B) 1 A @ B Using such a property, in the limit as V + 0, we have
A L, (V, Vi)
Σ, = L V,)
(47)
According to Lemma by
2 the squared 2- 2-Wasserstein distance between two Gaussian measures is given
1/2
(1 114- w11l 12112+ TT 2o 11 2(20) د1 20
(48)
Mean term
Covariance Term
Mean Term.
Since μ¹ V @ pt the mean difference becomes
11 μ1 11 11
Voooo Vi
1
Xo X
(49)
Covariance term.
Using the property of the Kronecker product, the square root of Eq.
47 factors
in as
1/1² L," 1/2 L (V. VV),,)-1
(50)
and
1
2:1/2
L 1/2 & (vo Vo) 1/2 (VoV)
(51)
first look into the term related to Vo V1, which is,
vo) 112) -T(((v/1))-(V111>)
Vo)
(52)
As () Tr(A) + Tr(B) the covariance term becomes
Covariance Term
= =Tr(Eo E1 - (// 2n ////)) 1/2 1/2
- -Tr(Eo) Tr(E,) - Tr (I)) Σ, 2
= =TY(Lo' @ (V vo) L @ (V 2 -2( | 12) 1/2
Vo) -1/2
@
(53)
Given that Tr @ B) can further derive,
Tr B) and TV(VVV) V for any real-valued matrix V, we
Covariance Term
(V, Vo) 1 T
1/2 TTi((V -1/ (V, (o) 1o2-
(54)
12 L 11)) -2Th 0
Unfortunately, to simplify this equation, we have to make the two gram matrix, (V²VV)-= (V/TV3)- agree, i.e., (V) -1 = (V. V This will be satisfied if and only if there exists an orthogonal matrix Q such that
Vo) and
Vi=V
Thus, to further process, simply consider the case when V1 and Vo are exactly the same, i.e., Vi = V V (we have already discussed how realistic this assumption is in Section[A.3] So that we 3, which simplify the trace as
work under the assumptions that || Vi = IV
1/2 Covariance Term 3- Tr Li L (1)
(55)
Combining the mean term and the covariance term, we obtain the Wasserstein distance of Wa(nx,
For calculating W. W. ne, ). we have the freedom to choose the cost function when obtaining the Wasserstein distance. Note that W serves the prior for the Gaussian covariance matrix Σ, where
21

---

Published as a conference paper at ICLR 2026
the covariance has to be positive-semi definite. Thus, according to Bhatia al. (2019) proper distance between two positive semi-definite matrices is measured by
W(ne. 7E, )= -
1/2
(56)
Coincidently, this is another usage case when the Bures- Wasserstein metric is utilized. Putting everything together, the Wasserstein distance in the limit v - 0
daw 91) = -Vo4o Vimill (8 (B+1) Tr L L 2 1
Tr Ly D 2 L _ L 1//2 1/2 - - x, x111 x (3+
(57)
(xx...x1)
This expression separates the contribution of the mean difference (transformed by V) and discrepancy between the covariance structures (encoded in Lo and L1). This could be further used to derive BW interpolation, which we will show in Section C.1 In the main body, constant actually corresponds to 3 here. This complete derivation in Proposition]
C DERIVATION OF BURES- WASSERSTEIN FLOW MATCHING
In order build the flow matching framework, we need derive the optimal interpolation and the corresponding velocities for the probability path p Go, G1). This is achieved via the OT displacement between two graph distributions.
C.1 THE BURES- WASSERSTHIN GRAPH INTERPOLATION
We aim to recover the proposition stated follows.
Proposition 7 (Bures- Wasserstein interpolation). The graph minimizer of Eq. (10p, G. (V,& &,, X.), have its node features following colored Gaussian distribution, X, N NX,, AT) with A, (vI + L.) @ V V and edges following & 5(W.), specifically,
1/2
E 1/2 (1- ())
1/2
(1-
(58)
The interpolation is an extension of the concept of mean, where in the optimal transport world, the Wasserstein barycenter (mean) measures .ju:... under weights λg.... ..-11 can be derived over the following optimization problem:
= arg min
E A (Wa (n, 3=0
(59)
7
When based the Bures- wassersesnnn (BW) distance, we can define the OT displacement minimization problem on graphs described as,
G. arg min ())ddnw(Go, (dd
(60)
G
where dew G1) is described in Proposition The optimal graph interpolation is the solution to the problem.
In the setting of graph, this becomes two-variable optimization problem, where
X2, E, = arg min (1-t)daw(C) 9) + td (.G)).
(61)
&,
Fortunately, recall in Eq. 57 that our distance measurement dnw(Sn, (Go, G1) is decomposed into dx (xo, X1) and dr Lo. L1), then the optimization over node and edges disentangleable into
22

---

Published as a conference paper at ICLR 2026
solving the two sub optimization problem,
Sub-question 1:
X arg min
(1-t)l - x + t/ X X111?
x
(62)
Sub-question 2: L, arg min
mig
(1 (1-t)dz(Lo. Ł) tdz ( (L1, L)
L
This two problems are completely disentangled thus we can solve them separately. Sub-question 1
For the first problem, simply set the derivate to 0 and get, - Xi) =0 X, = (1- + +(Xi)
(1 ( + +
(63)
Subquestion 2 The second subproblem is equivalent in deriving the covariance of Bures-
Wasserstein interpolation between two Gaussian measures, Y/o //' (0. Lg) and ?n N (0, Lj)- This problem has been properly addressed in Haasler & Frossard (2024) and here we just verbose their results. For more details we refer the reader to HHasler & Frossard (2024) for further discussion.
The optimal transport geodesic between no N (0, L)) and mn N (0, L)) is defined by d ((1- + #7/0 where the symbol "#" denotes the push-forward of measure by mapping, T a linear map that satisfies T L
We define new matrix M and do normalization, which leads to,
T= 1/2 T ML 1/2
(64)
Plug in gives,
T -Lo M 1/2 Li
/ M !2)
(65)
Lo MM L0¹
So that we obtain
1 Lo 1/2
MM 122 M (L) 9/2 D L0 1/33111
(66)
Replace T and we get.
1/2 ( T= L.
12 1
1/2 1/2
L
(67)
Given that the geodesic 7h ((1+t)I + (TT) #7o0 which also has a Gaussian form the ~ N (0, Ex), We can then write the covariance matrix and obtain
E E, = ((1 (1-1)) (T) L ((1 ((1- IT)
= 1/2 (1) L 12 2 1 2/2 1/2
1/2 L 1/2 (1) 1 13 1/2)
L
-I!! (1) & (I 2 1 112 2
(68)
Which ends the derivation.
Remark Even though the GraphMRF in Definition does rely on an implicit linear emission matrices V. the BW interpolation in Proposition 2 can be obtained without explicitly accessing the V matrices. The property was attractive as in practice we can construct the probability path without explicitly fitting V beforehand.
C.2 DERIVING THE VELOCITY OF BW INTERPOLATION
We first show the general form of the velocity term for the Gaussian and Dirac measures.
Gaussian measure. For a parmeeraraee Gaussian density Px(x) N (z;44, E,), the velocity field (z) satisfies the continuity equation
O,p, + V (prt)) = 0, an affine function of And the instantaneous velocity field follows,
vy (x))
pha + - - (X p.).
2
23

---

Published as a conference paper at ICLR 2026
Dirac measure. When the measure is Dirac function,
(r(x) 8 ò (t)
We can just consider it as the limited case of the Gaussian measure, when E, - 0. So that the velocity at simply takes
Uy (3) jdg-
We then move to prove the following proposition for
velocity.
Proposition 8 (Bures-Wasserseiin velocity). For the graph G. following BW interpolation in Proposition the conditional velocity time with observation G2 given as,
(E G1) We diag(L) - L. (x Go. G1) 1 1-t (X1 Xi)
(69)
with L. 2L, TL; L,T and T Lo (L. L
)/2 1/2
where W. DD= -D- Lt and L, defined in Eq. 11
Proof:
As we assume the edges, E, ~ 8(, Wi), following dirac distribu- The graph structure velocity. tion. the velocity is defined
ve (<(Ee) = W..
Given that, W, = diag( L.) L,, we transit fo deriving the derivative of the Laplacian matrix, L. Using the fact that,
d (A-')=-A"
dA A
dt
dt
we obtain the derivate of Laplacian matrix,
L. d(E)
d3
dE, L
Σ
L,
(70)
dt
dt
dt
According to Eq. 688 and Eq.
(67). the covariance matrix is defined through the interpolation,
Σ, ((1 I)T (1) (1
R.
(71)
where R2 = (1- IT. Taking the derivative, we get,
ΣS = d
(R. R. -T R,
(72)
dl
Using the fact that R. RsEo E,, we obtain the covariance gradient
(73)
So that,
d(Et)
1 1Σ, 1 L
dE Lr
L,
dt
dt
dt
L.((T L, (T L
(74)
= (. (T -T-
L,T LLT+TL,-21,
Thus, L. 2L: L,T TL,
Given that L, = D.-W, W, so that W, = diag( L,) L,, taking the derivative gives W, diag(L;) - L. As we assume the edges, Fe, 8(, W.), the derivate directly yields the velocity,
v1 F2 Go, G1) W, diag(L., L..
24

---

Published as a conference paper at ICLR 2026
The node feature velocity.
The instantaneous velocity field follows,
1
ex (x Go. G1) jur E (x+)
The mean gradient interpolating oo and 7/1 can be written as f = X1 -xo and X, = (1-t) So that the velocity leads to,
ty (x Go. G1) -1- Xo+ L. (X- X;).
However, in practice, we do not need such a complicated velocity term. We wish avoid the estimation of complex mradient-inverse term so that we can escape from the complicated computation. Under the assumption that the amplitude of covariance much smaller than the mean difference, we can omit the second term and just keep the mean difference. Hence the instantaneous velocity is simply described as
1y (X, x1 X1 - 1 1- (X1 X1)
(75)
D DISCRETE BURES- WASSERSTEIN FLOW MATCHING FOR GRAPH GENERATION
D.1 PROBABILITY PATH CONSTRUCTION FOR DISCRETE BURES- WASSERSTEIN FLOW MATCHING
The discrete probability path.
We design the probability path as discrete distributions,
pr( | Go. G1) Categorical((x)1)) Pe(Euv Go, G1) = (ernoull([[]]]] s.t. Po( 8(Gu-)), = -
(76)
where W, = DD L, with X, and L, defined the same in Eq. [I We consider the fact that the Dirac distribution is a special case when the Categorical/ermoull distribution has probability or 0, so the boundary condition (g)
5(Go, P, ()) = 8(G1, holds. As such, X, X +X1 E [o, 1| Since the boundary condition for each entry, [Xo] and [X1]e are two one-hot embeddings, [X.] X J. + (1 +)[ X Je would sum one, which works as valid probability vector. Thus, Categorical ([x,)) is K-class categorical distribution.
For the edge distribution, we just consider euo is conditionally independent of the other given [Wr].r. One thing to emphasize is that, given the nature of Bures-Wae Wasserstein interpolation, the yielded We is not always bounded by [0, 1] thus we have to hard-clip the boundary.
D.2 APPROXIMATING WASSERSTEIN DISTANCE IN BERNOULLI DISTRIBUTIONS
To make sure that the individual nodes are structured and developed jointly while doing flow matching, assume that the vec(X)) still maintains covariance matrix similar Eq. (8), which gives A (vI+L) @ V V given that X' is emitted from a latent variable H through an affine transformation and the latent variable has covariance matrix (vI + L) Different from the Gaussian case, the latent variable would still be discrete distribution, so that the affine transformation carries the covariance matrix out.
Unfortunately, the Wasserstein distance between two discrete graph distributions that follow Eq. [3) does not have a closed-form solution given the complex interwined nature. However, it is possible to use the central limit theorem applied to X' so that we can approximate the Wasserstein distance of two Bernoulli distributions with the Gaussian counterpart. This approximation works when we in high-dimenniionll case (high dimension means Vid is moderately large.), and the OT-distance between two such Bernoulli distributions is well-captured by the corresponding Gaussian formula, which we already introduced in Eq. (57).
With such nature, even though we are not sampling from Gaussian distributions anymore, it is possible to approximate the Wasserstein distance between two multivariate discrete distributions with the Gaussian counterpart, so the conclusions, such as optimal transport displacements, still hold. And we similarly derive the Bures- Wassersesnn velocity in the next section.
25

---

Published as a conference paper at ICLR 2026
D.3 VELOCITY FOR DISCRETE WAESESSSSSRST FLOW MATCHING
Node velocity. For node-wise, the path of node features X, can be re-written as pa = () Xo) + 16(;, X1) the conditional velocity be accessed through ve ve(e Go, Go)
[6( x1) ())((1))))) similar as the derivation in Gat et al. (2024).
Edge velocity. For edge-wiss wise, we look into each entry of the adjacency matrix W, and consider nime-dependent Bernoulli distribution, the probability density function is:
(ewe) ) = [W (1 [W.
1-ear
Eue E {0, 13.
(77)
To properly define velocity vxx, 1), should follow the continuity equation
0 at pi(ee)) + (po)c((uv) 0.
(78)
We x and y to denote states of Cuv (p(erv x) p())) p(eur = =)) == p(u)). then the divergence term is
V (pu)) = vs
()(x))1(2 v2( 8)].
(79)
gez
As we are working on a Bernoulli distribution, then the forward equations become
[0.p(0) = p(1) (1 or 1), (0.(11)= p(0) o. p()) 0).
(80)
Since pc(1)= ((1==WW]]ar) cuui, we have 0,p(1) [w] and 0,p(0) = [W]uu- Hence
(0)) 0/ (0- - 1) p(1) (1 - 0) = [We]ue-
There are many solutions the above equation. We chose a symmetric solution so that the transition of Cuv - Cav with
[W]ee vy (0 1) 1 [W.lev'
v1 0)
[W Juv
Finally for concise, we can write write it as velocity field on states Cuv and -1 at Cuv 1. Thus, we have
{0, 1}, note 1 - 2cwv is +1
[W
e (Cau, t) = (1 26ar)
Cuv {0.1),
[W,]an uv (1 --Wo)oo)
which in matrix forn gives
W.
(E Go) (1,)5,) (1 W,)
(81)
Combine the node velocity and the edge velocity, we can now introduce the Discrete Bures- Wasserstein Flow matching algorithm, with the training and inference part respectively introduced
in Algorithm 3 and Algorithm
E DESIGN SPACE FOR BURES WASSERSTEIN INTERPOLATION AND VELOCITY
In the introduction part, we have already compared different probability paths and how they are impacting the inference time sampling. While the Bures- Wasserstein flow path is shown to produce better probability path for the model to learn, we illustrated in Fig. la we have to point out that linear interpolation and the corresponding probability path can still converge to the data distribution with sufficiently large flow steps. As if we conduct sampling with infinite flow steps during the later stage of flow, the samples are still able to arrive at the target distributions. A similar pattern exists in diffusion models when they are considered as Monte- Monte-Carlo Markov Chain, and they need sufficiently large steps to converge. We emphasize that the convergence gap in Fig. Ic would be slowly recovered the number of flow steps increases.
26

---

Published as a conference paper at ICLR 2026
Algorithm 3: Discrete BWFlow Training
Algorithm 4: Discrete BWFlow Sampling
Ref. dist po and dataset Pr- Trained model fo(Gr,t). Initialize model fo(G,, ():
Input:
Input: Reference distribution Po- Trained
Output:
Model (o,G, 1), Small time step dt,
Output: Generated Graphs (G1).
while fa not converged do
Initialize samples (Go) Pos
Sample Boundary Graphs
Initialize the model ( G.) + fo(G
*/
Sample batched (Gp} Pu. (G1) D; /* Prob. path Construction
for t + 0 to 1 by dt do
Denoising x-prediction
Sample ~~ (0, 1); Calculate the BW interpolation to obtain
Predict G - r G.)::
/ Velocity calculation
Xt, W. via Eq. [II;
Calculate us (G, Go, G1) via Eq. 14
Sample G, p To, according
/ Numerican cal Sampling
Eq. 13:
Sample G
G, vo (C (Gt)
Denoising
r-prediction
t G. - fo(G..t)
Loss calculation via Eq. (4)
optimizer.stepO;
Given that different sampling algorithms can all bring the samples to the data distributions under certain conditions, we wish to understand the huge design space of Bures Wasserstein interpolation. We list the advantages and disadvantages in different techniques and discuss further when each techniques should be used.
In general, consider two important steps to construct the flow matching for graph generation, specifically, training and sampling. training, the main challenge is to obtain a valid real velocity u(G,) to be regressed to, we listed few strategies that can help with that. In sampling, the challenge becomes how to reconstruct the probability path through the velocity estimated.
E. THE TRAINING DESIGN
In general, the learning objective in flow matching depends on regressing the velocity term. There are several way to obtain the velocity.
1. Exact velocity estimation. Use Eq. 3 as the parameterization and learn pa (G G+)
2. Numerical approximation. In the implementation of Stärk al. (2024). the derivative is calculated through numerical approximation. To achieve better efficiency in calculating velocity, we simply consider numerical estimation in Stärk al. (2024). where the velocity term obtained as, L, (e+4r--,)// Regressing on the numerical difference can provide an estimation for the velocity.
3. AutoDiff. In Chen & Lipman (024), the derivative of the probability path is evaluated through Pytorch AutoDiff. However, in practice we find this method unstable.
We summarized the training stage model parameterization in Table 4
Continuous Flow Matching
Discrete Flow Matching
r-prediction
o (G.) + (G)) Gi] 5. (G.) = Gi-dt Gt
(G.) H pip (G1 G.) - (0)))-8(,000 G.)
Numerical Approximation
G.. +
* p(Gr+a Discrete velucity introduced in Eq.
p(G, Go. G
AutoDiff
((. & G.
Table 4: The model parameterization for flow matching in training stage
27

---

Published as a conference paper at ICLR 2026
E.2 THE SAMPLING DESIGN
As we described in the Eq. 33. in our training framework, we actually train denoised pa ( Gr). With such parameterization and taking discrete flow matching an example, the sampling can be done through one of the following design choices:
1. Velocity sampling with x-prediction. The velocity designed as,
(G,) - (pe - -((G))))
This design directly moves the current point G2 towards the direction pointing to the predicted G1. The target-guided velocity guaranteed converge to the data distribution, but the interpolant might lie outside the valid graph domain.
2. BW velocity sampling. We use Eq. (4) to directly estimate the velocity and flow the Btures-aasersseiit probability path generate new data points. This path is smooth in the sense of graph domain. However, this path requires more computational cost.
3. Probability path reconstruction. The third option is directly reconstructing the probability path, i.e., we first obtain an estimated point,
G Po (91 G.) and then construct the data point at + dt, which gives
Gi-at p(g, Go,
through Eq. 12.. This is the most computationally costly method, which is obtained through the diffusion models. But this method also provide accurate probability path reconstruction.
In Section 4 we show BW velocity follows path that minimizes the Wasserstein distance thus provides better performance, but sampling following linear velocity also provides convergence with much lower computational cost. So it is a trade-off to be considered in the real-world application.
Continuous Flow Matching
Discrete Flow Matching
BW Velocity Target-guided Velocity
Eq. 12
Eq. 14
vo G.) T
G+
(G.).) T (po (91 G.) 5 ((Gr.))
Path Reconstruction
Gz-dt 8(Gr+dt) G1, Go)
Gevat ~ pl Gtt+d G1, Go)
Table 5: Reconstructing probability path choices in flow matching during inference
F DISCUSSION AND LIMITATIONS
F.1 THE IMPLICIT MANIPULATION OF PROBABILITY PATH
Though not explicitly mentioned, Qin et al. (224)) makes huge efforts to manipulate the probability path for better velocity estimation by extensively searching the design space, and their finding aligns well with the statement that the velocity should smooth and consistently directing to the data points: 1) Time distortion: (The oragne line in Fig. 5b) the polynomial distortion of training and sampling focus on the later stage of the probability trajectory. providing better velocity estimation in this area. This uneven sampling strategy is equivalent to pushing the probability path left to make it smooth.
2) Target guidance: (The green line in Fig. 5b) the target guidance directly estimate the direction from a point along the path towards the termination graph, so that the manipulated probability could smoothly pointing to the data distribution. and 3) Stochasticity injection: Stochasticity explores the points aside from the path, which avoid the path be stuck in the platform area.
F.2 POTENTIAL EXTENSION TO DIFFUSION MODELS
The probability path construction can be denoted
G pl Go, G1) o4 + o.Go
(82)
28

---

Published as a conference paper at ICLR 2026
Graah Statietics
Average Ratio for Graph Statistics
Estimated velocity
22
Ideal Velocity
30
-0
Average
Linear Interpolation
interpolation
Ideal Interpolation
lime distortion (Qin et al)
Target Guidance (Qin et al.)
1.0
Flow steps
Flow steps t
(a) Lincar training path
(b) Training path with manipulation
Figure 5: Techniques for manipulating probability path.
At the scenario of flow matching, simply use a; = and o; 1-t
and or 1- The optimal transport flow matching
on the other hand, variance-pres prreerriii diffusion models constructed the noisy input through scheduled process, which can be described as,
G = V a
(83)
However, existing diffusion models are still based the local interpolation, i.c. an element-wise interpolation. This will not compensate the "late convergence" scenario thus we still suffer from the same problem.
Under such an understanding that diffusion is also based on stochastic interpolation, we can easily extend our method diffusion models by interpolating on the whole graph systems instead of doing so locally. In order to extend the flow matching algorithms with diffusion models, one important thing is to convert the pair-conditioned probability path and velocity to single boundary conditions. For instance, the probability path in flow matching has the form p(G, G,, Go) and the velocity follows oGG, Go). As suggested in Siraudin et al. (2024): Campbell et al. (2022); Xu et al. (2024), the discrete graph diffusion models require velocity (which is equivalent to ratio matrix) to perturb the data distribution conditioned on the data points, which we denote as v v(G, G1). As long the unilateral conditional velocity has tractable form, can first sample G and get G, through iteratively doing to:
Gt-di= = G u G1)
starting from G So that one can easily construct the probability path p(G, G1) to fit into the diffusion model framework. In practice, given that we know the explicit form of v(G, G1, Gp) (just replace Go in the expression), the unilateral conditional velocity can be obtained through taking the limitation,
(G G1) = v(G G1,G,) lim v(G, GT,
Both linear interpolation and our Bures-Wasserse Wasserstein interpolation can achieve this easily. We just provide discussion here and will leave this as future work this paper does focus diffusion models but on flow matching models.
F.3 PERMUTATION INVARIANCE.
The Bures- Wasserstein distance between two graph distributions is not permutation invariant, and the minimal value is obtained through the graph alignment. So ideally, to achieve optimal transport, graph alignment and mini-batce matching could provide a better probability path. However, permutation invariance is not always a desired property since we only want to find path that better transforms from the reference distribution to the data distributions. As illustration, the widely used linear interpolation to construct graph flow (Qin et al.) 2024) does not guarantee permutation invariance well. And it is proved that, if the measurement based Wasserstein distance between two
29

---

Published as a conference paper at ICLR 2026
Gaussian distributions.
dpw(1 (1go ng, ) Arrithmmttic (1/90 112,
with dpw (Tg ng. ) X X1 X112 + trace
Lo + _ (2 (P' PP (P))))))))))))))
and dasithmetic (7G.. mg.) |X - -11l + Lo P, vP potential permutation set (84)
F.4 MITIGATING THE COMPUTATION COMPLEXITY
When constructing the path, our BW interpolation induces an extra O(N3) linear algebra operations in calculating the matrix inverse graph Laplacian. We wish to emphasize that this the basic linear algebra operations in matrix multiplication and does not reflect the model complexity, i.e., the forward/backward propagation and gradient calculation.
Though this computation does not always improve the training clock-time, as we illustrated in Table 9 we feel it valuable to further reduce the computational complexity as the matrix inverse is not properly supported by current GPU design. When the graph size scales up, it also becomes problematic. In order to improve the efficiency, we propose two promising direction:
Disentangle the probability path construction from the training and move it to pre-training stage.
2. Approximate the matrix inverse calculation through iterative solving methods.
We provided a preliminary experiment for the second point via solving the inverse by least-squares with QR factorization (LSQR).
LSQR algorithm, When given large, sparse matrix L, directly computing - yields O(N*) linear algebra operations. As remedy, we do not compute the matrix L itself, but rather solve via the linear system:
La
The solution to this system, L- provides the desired result without forming the inverse matrix. In order to solve the problem, we formalize the objective as
min
La bl2
and conduct least squared minimization for the above problem. The minimization of the above objective can replace the original inverse matrix calculation. THis method especially useful when L is large, sparse, and potentially ill-conditioned.
LSQR's effectiveness stemas from the factor that algorithm does not require access to the individual elements of L. Instead, it only requires computing the matrix-vector products Læ. For sparse matrix with non-zero elements (exactly the edge number), these products are typically in O(E) time, opposed to O(N²) for dense matrix.
We can use LSQR to find the j-th column, Cj. of L-1, we solve the linear system:
Lej- Ee
where ej is the j-th standard basis vector (a vector of all zeros with a I in the j-th position).
ej [O. 0, 0,1,0....,00 00"
The resulting solution vector will be the j-th column of L- To construct the full inverse, we repeat N times.
When scaled up to large but sparse graphs, the complexity can be reduced to O(TNE) (the previous methods are ((N2)) through iterative solving such as LSQR.
Newton-Schulz Iteration. is also possible to utilize Newton-Schulz Iteration to solve the problem, where the complexity if O(TN2).
30

---

Published as a conference paper at ICLR 2026
Preliminary experiment with LSQR .To show that LSQR does not negatively impact the perfor- mance, we conduct preliminary experiments with
Table 6: Model performance using LSQQ to approximate the graph Laplacian inverse
LSQR instead of the exact pseudo-inverse calculation of the Laplacian matrix. Results clearly show that we could achieve lower complexity without impacting the quality of the generative model.
Planar
Tree
Model
V.EN..
A.Raii
V.U.N.
A.Ratio
BWF
85.0+ sn
2,74
80.1 +00
1.32.05
BWFlow
84.8c
2.4609
81.3
1.3e03
F,5 EXTENSION TO NULTI-RELATIONAL GRAPHS
A limitation of our method is that it cannot easily capture the generation of graphs with multiple relation types, which we name hetemgeneous graphs. Even though utilize an intuitive solution in the experiment to produce Table [4] we first sample the pure graph structure without edge types to produce the graph backbone, and then sample the edge types via liner interpolated probability on top of the backbone. The solution provides preliminary results for the graph generation in multi-relational graphs, but still requires improvements. Fortunately, there exists a few ways to extend the GraphMRR to heterogeneous graphs (Jiang et al.] (2025). An interesting future work can be generalizing our model to heterogeneous graphs by considering GraphMRR variants, such as the H2MN proposed in Jiang et al. (2025).
G RELATED WORKS
G.1 DIFFUSION AND FLOW MODELS
Among contemporary generative models, diffusion (Ho et al. 2020) and flow models (Lipman et al. 2023) have emerged as two compelling approaches for their superior performance in generating text and images. In particular, these generative models can be unified under the framework of stochastic interpolation (Albergo & Hunden-Eijjdde
2023), which consists of four procedures (Lipman et al. 2024) as we introduced in Section | These contemporary generative models rely on constructing probability path between data points of an aasy-to-sample reference distribution and of the data distribution, and training a machine learning model to simulate the process (Lipman al.. 2024). So that one can sample from the reference (a.k.a source) distribution and iteratively transform it to approximate data samples from the target distribution. Diffusion models construct the probability the data distribution, where one start sampling from
path with unilateral path conditioned data point X, and construct the path p(x, X1). While flow models can condition on either two boundary conditions, (X1, Xo) just one-side boundary condition X1.
Depending on the space that the algorithm operates on, both models can be categorized into continuous or discrete models. The continuous generative models assume the data distributions are themself lying in continuous space (such as Gaussian) and build models, with examples in diffusion (Ho et al., 2020: Song al., 2021 Wang al. 2024) and flow (Lipman al., 2023 Liu et al.. (023b). The discrete generateive models assume the data follows a discrete distribution, for instance categorical or Bernoulli distributions. Examples include discrete diffusion (Campbell et al. [022 [unn al., 2023)
and discrete flow models (Campbell et al. 2024 Gat et al. 2024 Minello et al. 2025).
Under the stochastic interpolation framework, the interpolation methods are commonly selected through optimal transport (OT) displacement interpolant (Liu et al., 2023b] Albergo & Vanden Eijnden| 2023 McCann 1997). Optimal transport is a classical topic in mathematics that was originally used in economics and operations research (Villani & Society 2003). and has now become a popular tool in generative models. OT aims for finding the best transport plan between two proba- bility measures with the smallest associated transportation cost. It has been shown that generative models can be combined with technologics such as iterative matching (Tong et al., (024)) and mini batching (Pooladian et al. 2023) to approximate the OT cost, and get significant boost in their performance in generative modeling.
Another relevant work is Haviy et al. (2024), where the authors explore the flow matching technolo- gies between two Gaussian measures, there they try to interpolate between two Gaussian measures. Our work focuses different task of graph generation.
31

---

Published as a conference paper at ICLR 2026
G.2
GRAPH CENERATION MODELS
Thanks to the capability of graphs in representing complex relationships, graph generation (Zhu et al.
2022 Liu al. (023a) has become an essential task in various fields such as protein design (In- graham et al.] 2019), drug discovery (Bilodeau et al. (022), and social network analysis (Li et al. 2023). The intiial attempt at graph generation formalized through autoregression. For instance. GraphRNN (You et al. 2018) organizes the node interactions into series of connection events and conducts autoregressive prediction for generation. Later, one shot generation methods such as Variational Graph Auto-Enetr Encoder were proposed (Kipf & Welling 2016; Cao & Kipi 2018).
Among various generative models, diffusion models and flow-based models have emerged as two compelling approaches for their ability to achieve state-of-the-ard performance in graph generation tasks (Niu et al.) 2020) Vignac et al.; 2023a Eijkelboom et al. 2024] Qin et al., 2024 Hou et al. 2024). In the early stage, continuous diffusion models were first extended to the task of graph generation (Niu et al.) (020), where they just view the adjacency matrix as a special signal living on the RR MMM domain. However, these methods fail to capture the natural discreteness of graphs, and Vignac et al. (2023a) first brings discrete diffusion into graph generation. After that, more work (Siraudin et al. 22024] Xu et al., 2024) starts to focus on designing better discrete diffusion models for graph generation.
On the other hands, with the development of flow matching techniques, a few works have been developed utilize flow models for graph generation and they have achieved huge success. Eij Eijkel boom et al. 2024) utilizes variational flow matching to process categorical data and Qin et al. (024) developed discrete flow matching for graph generation tasks.
In parallel, there are a number of work that have managed to respect the intrinsic nature of graphs, such global patterns. For instance, JT et al. (2024) brings a mixture of graph technique to enhance the performance by explicitly learning final graph structures: Yu & Zhan (2025) mitigates exposure bias and reverse-start bias in graph generation: Hou et al. (2024) improves graph generation through optimal transport flow matching techniques but they still assumee the independence between nodes and edges and use hamming distance to measure the transport cost; and [Li et al. (2023) gives the large-scale attributed graph generation framework through batching edges.
However, there remain core challenge: constructing the probability path p.. Existing text and image
generative models, operating either in the continuous (Ho et al. [020 Song et al. [202]] Lipman et al.
2023] Liu et al. 2023b) or discrete (Campbell et al.] [022] Sun et 20223 Campbell et al. [2244
Gat et al. (2024; Minello al. (025) space, typically rely on linear interpolation between source and
target distributions to construct the path. Graph generation models, including diffusion (Niu et al.
2020 Vignac al. 2023a Haefeli et al. 2022 Xu et al., 2024 Siraudin al. 2024) and flow-
models (Eijkelboom et al. 2024 Qin et 2024 Hou et al. 2024). inherit this design by modeling
every single node and edge independently and linearly build paths in the disjoint space. However, this approach is inefficient because it neglects the strong interactions and relational structure inherent in graphs, i.e., the significance of node heavily depends on the configuration of its neighbors. While empirical success have been achieved via fine-grained searching on the training and sampling design QQin et al., (024) such as target guidance and time distortion, we argue that there remains a fundamental issue of the linear probability path construction, and these strategies only mitigate the problem by manipulating the probability path.
H COMPARISON WITH OTHER INTERPOLATION METHODS
In the experimental part, we compare our methods with arithmetic (linear) interpolation, geometric
interpolation and harmonic interpolation. We state the equation of them respectively as follows.
We consider the boundary graph Gp and G1 with Xo, X, E RR/ and Wo, W1 e R MMMM Let t é [0. 1]. we fixed the feature interpolation as,
X, = (1- (1-)) Xo + tX,,,
the graph structure interpolation can be expressed as,
Linear interpolation:
W (1- () Wo 1 WW.
32

---

Published as a conference paper at ICLR 2026
V.U.N metrics
Spectral Metries
Dalaset
IM type
Interpolation
Novelty
Uniqueness
Validity
Orbit
Spoc
Clustering
Degree
Wavelet
Arg. Ratio
DeL'g
100
100
78.25
8.98
1.45
2.09
2.38
3.51
Planar
Discrete
Linear
100
100
73.25
4519.63
10.83
1.33
1.74
2.24
2.39
3.70
Geometric
100
100
23.25
655.66
1.61
10.17
13.25
6.68
137.47
Defog
100
100
61.53
1.17
1.27
1.51
1.32
Discrete
Lincar
100
100
56,91
1,16
1.04
1.45
1.22
harmonic
100
100
0.53
2.32
1.93
3.31
2.52
Geometric
100
100
48,38
1.62
2.13
2.10
1.94
Linear
100
100
44,63
2.57
1.40
1.46
15.55
7.88
5.77
SBM
Discrese
Geometric
100
100
0.0
3.11
4.45
1.80
150.41
60.60
54.65
BW
100
100
58.70
2.03
1,50
1.50
9.04
8.41
4.51
Table 7: Ablation study on interpolation methods when probability path manipulation techniques are all disabled. The clustering and orbit ratios in tree graphs are omitted, given that the training set, the corresponding statistics are O. The results go over exponential moving average (decay 0.999) for the last checkpoints. The table is produced with Marginal boundary distributions, without time distortion.
Table 8: Comparison of interpolation methods on 3D Molecule generation with explicit hydrogen in QM9 dataset.
Flow Type
Interpolation
Metrics
P
V.U.N(()
Stable
Connected(
Charge(10 9)
Angles(")
MiDi
L.1
93.13
93.98
90.60
99.21
0.2
3.7
2,21
99.
Diserete
harmonic
1.01
94.91
94,54
99.65
99.03
0.6
6.4
2.21
Goometrie
91.26
91.29
3.63
BW
1.01
96.45
97.84
99.84
99.24
0.1
2.3
1.96
Linear
2.15
25.45
10.23
76.85
28.82
0.7
5.6
14.47
Contimuous
harmomic
1.01
11.38
11.64
73.48
99.65
1.2
17.2
15.04
Geometric
1,00
42.07
46.08
91.13
99.87
1.0
12.7
8.03
1.02
62.02
61.76
95.99
97.72
0.6
7,80
Clearly, continuous matching models comparative discrete flow matching models.
Geometric interpolation:
W W (Wo 1/2 W, w w
Harmonic interpolation:
W. ((1 tW,')"
Each interpolation methods actually handle each special manifold assumption, which should be designed under a comprehensive understanding of the task. In our experimental part, we conduct intensive analysis on the impact of interpolation methods to the graph generation quality.
H.1 EMPIRICAL COMPARISON
In T illustrate the numerical results for comparing the interpolation methods in plain graph generation without node features. It is clear that BWFlow outperforms other methods in planar and SBM graphs. But the performance was good in tree graph generations. In Table 8 we compare the interpolation methods in molecule generation.
I ADDITIONAL EXPERIMENT RESULTS
I.1 EXPERIMENT SETUPS AND COMPUTATIONAL COST
The training and sampling computation time provided in Table The experiments
single NVIDIA A100-SXM4-80GH GPU. The hyperparameter configuration in producing Tables
2 and is reported in Table 10
33

---

Published as a conference paper at ICLR 2026
Table Training and sampling time on each dataset. TG means using target-guided velocity; BW means using BW velocity.
Datuset
Min Nodes
Max Nodes
Training Time (h)
Graphs Sampled
Sampling Time (h)
Planar
64
64
45 (1.55x)
0.07) 0.13 (BW) 0.07(TG);0. 1..(BW)) 0.07(TG) 0. 0.14(BW)
Tree
64
64
10 (1.25x)
40
SBM
44
187
74 (0.98x)
40
Moses
8
27
35 (0.76x)
25000
5(TG); 6/BW) 7(TG): (1(BW)
Guacamol
2
88
251 (188)
10000
QM9
3
29
15
25000
SCTG) 6(BW) 7(TG) 14(BW)
GEOM
181
141
10000
Table 10: Best Configuration for Training and Sampling when producing Tables
and
Training
Sampling
Dataset
Initial Distribation
Train Distortion
Sample Distortion
Sampling steps
Stochasticity
Marginal
Identity
Identity
Tree SBM
Marginal
Polydec
Polydec
1000
0
Absorbing
Identity
Identity
1000
MOSES
Marginal Marginal
Idenity
Identity
200
GUACAMOL
Identity
Identity
500
300
QM9
Marginal Marginal
Identity
Identity
500
0
GEOM
Identity
Identity
500
1.2
BEST CHECKPOINT RESULTS IN PLAIN GRAPH GENERATION
We present the best checkpoint results in plain graph generation Table
1.3 FULL EXPERIMENT RESULTS FOR PLAIN GRAPH GENERATION
We provide the full experiment results Table with exisitng graph generation models' perfor- mance reported. Most of the results are taken from Qin et al. (2024). We reported the detailed ratios for each model that we reproduced in Table
1.4 ADDITIONAL RESULTS FOR 2D MOLECULE GENERATION
We wish to note that the 2D molecule generation task is relatively simple and are near saturated with most state-of-the-art models.
Setup. In 2D molecular generation, two scenarios with and without bond types information are considered better evaluate the ability of generating graph structures.
Metrics: In addition to the novelty and uniqueness of moecules, also utilize the relaxed stability of atoms Stabb, the relaxed molecule stability (Mol.Stab.) and the validity of a molecule, are used for 2D molecule generation. In addition these metrics, distribution metrics are also used for 2D molecules, which includes 1) Frécher ChemNet Distance (FCD): whichMeasures the distance between the statistical distributions of generated and real molecules, and Similarity to Nearest Neighbor (SNN), which measures the average similarity (e.g.. Tanimoto) of each generated molecule to its closest neighbor in reference dataset. Also, practicality & diversity metrics, including Filters Percentage of molecules passing medicinal chemistry filters (e.g., drug-likenee synthetic accessibility). andScaffold Diversity (Scaf) that measures the diversity of the core molecular frameworks (scaffolds), indicating structural variety.
Model peformance. The model performance is illustrated in Table 14 In both datasets, BWllow
can achieve competitive results near the ofate-of-the-aat (SOTA) flow matching models (Qin et al. 2024), and outperforms the diffusion models. Given that MOSES and GUACAMOL benchmarks approaching saturation, the fact that BWFlow achieves results on par with the SOTA models serves strong evidence of its effectiveness.
34

---

Published as a conference paper at ICLR 2026
Table 11: The best-checkpoint plain graph generation Performance. Results are obtained through tuning the probability path manipulation techniques. The remaining values are obtained from Qnn al. 22024).
Planar Dataset
Model
Ratio
Valid
Unique
Novelt
V.U.N.
Train set
100
0.0
GRAN Lino al. 2019
97.5
2.5
SPECTRE MManin ii et
2022
3.0
25.0
100
100
25.0
DiGress Vignac di A0450
77.5
100
77.5
EDGE
431.4
100
BwR Diamani al 4045
251.9
0.0
100
100
0.0
2020
16.0
62.5
GraphCen Goyyl o1
2070
210.1
7.5
100
100
7.5
HSppecrre (Dne-shox) [Berniecsterr
2024
67.5
100
100
67.5
HSpectre Bergmeister
2.1
95.0
100
100
95.0
GruM Jo.ct 2024
90.0
CatFlo
2024
80.0
DisCo (Xi ot 2024
83.6 62.1
100.0
100.0 40.0
83.6 st.1
Cometh - PC Straudin at 2024
99.5 20.9
100.0 40.0
100.0 400
99.5 20.9
DeFoG
1.6 20.4
91.5
100.0
100.0
99.5
BWFlow
1.3 20.4
97.5 $2.5
100.0
100.0 20.0
97.5a25
Tree Dataset
Train set
0.0
al. 2019
DiGress
Vignne al
A023g
1.6
90.0
100
100
90.0
EDGE Cien al. 2025
850.7
BwR Diamanl
2025
11.4
0.0
100
100
BiGG (Ua at 2020
5.2
100
87.5
50.0
75.0
GraphGen Goyal
2020
33.2
95.0
HSpectre (mnc- [eerymeister
1024
2.1
82.5
100
100
82.5
HSpectre Bergmeister ef
Cometh
Strandin
75.0
100.0
100.0
75.0
DeRoG
1.6 40.4
96.5
62.6
100.0 +0.0
100.0
600
96.5 #2.6
BWFlow
1.4
95.5 +2.4
100.0+0
100.0-0
95.5-244
Stochastic Block Model (num
187, May
104)
Ratio
Valid
Unique
Novel
Training
GraphRNN You
14.7
GRAN | Jan mr. 2019)
9.7
25.0
100
100
25.0
SPECTRE Mariinkus of
52.5
52.5
DiGress Vignne di A0450
1.7
60.0
100
100
60.0
EDGB hen et ml 20241
51.4
0.0
100
100
0.0
BwR
38.6
BiGG LUa el 2020
11.9
10.0
100
100
10.0
GraphGen Goyal
HSSpectre [cac-3]a)]] Beremeisee
2024
10.5
75.0
100
100
75.0
HSppectre [Brymeister
2024
10.2
45.0
100
45.0
GruM al 2114
85.0
CatFlow (arkkllonooooo et 2024
85.0
DisCo al.
66.2
100.0
Cometh Straudin at 2024
75.0 a3.7
100.0
100.0 400
75.0 a3.7
DeFoG
4.9 +1.3
90.0 25.1
100.0 400
100.0 40.0
90.0 25.1
BWFlow
3.8
92.5 $4.0
100.0 400
100.0 40.0
92.5 .4.0
I.5 ADDITIONAL RESULTS FOR THE TRAINING PATHS
We elaborate on the detailed experimental setting for training path comparison. Fig. Ta and are generated using representative plain graph dataset, SBM. At cach time step t, we compute the average maximum mean discrepancy ratio (A.Ratio) between the interpolants and the real data graphs multiple graph statistics, including orbit, clustering, spectral, wavelet, and degree ratios. The "ideal velocity" (green curve) in Fig. Ta a synthetic reference path used purely for conceptual illustration.
Fig. gives the training probability path construction for planar graphs and tree graphs. While planar graphs have similar pattern the SBM datasets in Fig. [3| the probability path constructed for
35

---

Published as a conference paper at ICLR 2026
Table 12: Plain Graph generation performance. Given that the synthetic datasets are usually unstable in evaluation, we applied an exponential moving average to stabilize the results and sampled 5 times (each run generates 40 graphs) to calculate the mean and standard deviation. The experiment settings are in Table I0 The full version with explicit ratio numbers can be found in Table I1
Planar
Tree
SBM
Model
Class
V.C.N.f
A.Ratio
V.U.N.f
A.Ratio
V.U.N.f
A.Ratio
Train set
100
1.0
100
1.0
85.9
1.0
DiGress (EMA) (Vinnac
2023a
Diffusion
61.5a10.1
9.9
26.0
8.9.1
56.0s85
3.5a05
DisCo (CAVG) et al. 2024
Diffusion
57.5
9.0=
/
55.0259
11.6=29
HSpectre [Bergmeister ot ai. 2024
Diffusion
67.5
3.0
82.5
2.1
75.0
10.5
GruM (EMA) (J al. 2024
Diffusion
74.4
3,2404
52.5
2.4
73.5
2.62a6
Cometh (EMA) (Straudi ct
2024
Diffusion
80.5
3.0206
84.5
2.0+0.4
77.5257
4.7+00
DeFoG (EMA) Qui ct al. 2024
Flow
77.5s8.37
3.5x177
83,5210.8
1.9.04
85,0s7.
3.420.
BWFlow (EMA)
Flow
84.8:6.44
2.4:09
81,5
1.3
84,5:80
2,3
Dataset
Model
Validity Metrics
Spectral Metries
Avg. Ratio
V.U.N
Orhit
Spec
Clustering
Degree
Wavelet
Training
0.0005
0,0038
0,0300
0,0002
0.0012
Digress
(.1126255200)
0.0100 (2.63)
0.1204 (3.85)
(15.50)
0.0031 (2.55)
9.95
Hspectm (One-shot)
67.5
3.0
Planar
GruM
74.39
0.0445 (8.90)
0.00755 (1 .99
0,804288 (0 14)
0.00775 (3.75)
0.00558 (2.15)
3.20
Comerh
80.50
0.0038 (7.60)
0.0080 (2.09)
0,0334 (1 08)
0.0001334 (1 12)
0.0036 (2.97)
3.00
DeFag
77.50
0.0045
0.0055 (1.45)
0.0648 (2.09)
0.0005
0.0029
3.51
(5.14)
0.0048 (1.27)
(1.69)
0.0034 (1.78)
0.0024 (2.02)
Training set
100
0.0000
0.0075
0.00000
0.0001
0.0030
Digress Hepectm (Ono-shot)
$6.00
0,0002 ()
0.0126 (1.68)
0,0025 ())
0.0018 (17.80)
0.0088 (7.30)
8
Thee
GraM
52.50
82.50
0.000/00.00)
0.0045
0.80000)
0.0044
00047(3.91)
2.
2.41
Cometh
(.0102(1.36)
0.0000 (/)
(3.20)
0.044(1.46)
DeFog
83.50
0.0001 (1)
0.0126 (1.68)
0.0000 (1)
0.0002 (1.87)
0.0066 (2.21)
1.92
BWFlow
81,50
0.0000 (0.00)
(1.197
0,0000 (0.00)
0.0001 (1.27)
0.0016(1.51
1.31
Training
85,90
0,0255
0,0027
0.0332
0,0008
0,0007
Digress
$6.00
0.0748
0.0061 (2.26)
0.0584 (1.76)
0.0018
0,048
3.51
Hspectm (One-shot)
SBM
GraM
73.50
0.0412 (1.62)
0.0068 (2.52)
0.0495 (1.49)
0.0028 (3.50)
0.0017 (2.43)
2.60
Cometh
77.50
0.076 (2.98)
0.0114 (4.22)
0,052 (1.56)
0.0063 (7.58)
0.0048 (6.86)
4,70
DeFog
85.00
0.0122(1.67)
0.0045
0,0501 (1.51)
0.0062 (7.71)
0.0030 (1.33)
3.39
BWFlow
84.50
0.05 (2.02)
0.0030 (1.10)
0,0478
0.0028 (3.50)
0.0025 (3.52)
2.32
Table 13: We reported the detailed ratios in three plain graph generation datasets. We omit the orbit and clustering ratio calculation in tree datasets as the training set values are close to 0 which makes the calculation unreliable.
tree graphs does not follow a similar pattern. We attribute this to the different geometry of tree graphs that reside in hyperbolic space (Yang al. 2022), and different statistics evolution pattern as we discussed in Section A.3]
1.6 MORE EXPERIMENTS ON PLAIN GRAPH GENERATIONS
Additional results for sampling paths. We then give the sampling path construction in Fig. 7 To better illustrate the advantage BWFlow, we fix the sampling steps to as small as 50. clear that in planar and SBM dataset, the BW velocity can still provide a smooth probability and stable convergence towards the data distribution. While the lincar velocity does not give a good probability path and fails to converge the optimal value, especially when the sampling size is small.
The maximum mean discrepancy (MMD) of four graph statistics between the set of generated graphs and the test set is measured, including degree (Deg.), clustering coefficient (Clus.), count of orbits with 4 nodes (Orbit), the eigenvalues of the graph Laplacian (Spec.), wavelet ratio ( (Wavelet.). To verify that the model learns generate graphs with valid topology, gives the percentage of valid, unique, and novel (V.U.N.) graphs for where a valid graph satisfies the corresponding property of each dataset (Planar, Tree, SBM, etc.)
Full results for plain graph generation. Table II gives the full results with other generative models aside from the diffusion and flow models. Table 16 gives the results on smaller datasets, i.c., comm20
36

---

Published as a conference paper at ICLR 2026
Table 14: Large molecule generation results. Only diffusion and flow models are reported. Table 15 gives further experiments with binary edge types.
Guacamol
MOSES
Model
Val.
f
V.U.N.1
Unique.
Novelty
FCD
Training set
100.0
100.0
0.0
92.8
100.0
100.0
0.0
100.0
0.01
0.64
99.1
DiGress
DisCo Nu 8L 2024
86.6
86.6
86.5
59.7
88.3
100.0
97.7
95.6
1.44
0.50
15.1
Cometl
2024
98.9
98.9
6
72.7
90.5
99.9
92.6
99.1
1.27
0.54
DeFoC Qu ot a. 2024
99.0
99.0
97.9
73.8
92.8
99.9
92.1
98.9
1.95
0.55
14.4
BWFlow
98.8
98.9
97.4
69.2
92.0
100.0
94.5
98.4
1.32
0.56
15.3
Table 15: Large molecule generation results. Only comparing the representative diffusion and flow models. B.E. is the scenario that only considers binary edge types. The results are almost saturated, thus not very informative.
Guacamol
MOSES
Model
Val. f
V.U. f
V.U.N.1
Val. f
Unique.
Novelty 1
Digress (B.E.)
96.0
98.9
97.4
96.1
100
100
Defog (B.E.)
98.4
98.4
97.9
99.3
100
100
BWFlow (B.E.)
98.0
98.0
97.7
99.6
100
100
(Planar Grapho The exclution grash statistics flow
Grophs) evolution statietics
Statatic
1000
800
Interpokiion
K00
Aithrrat (Lireer)
lurbo
155
400
Jearage
200
Inter solation Type
Arth Sunwar)
(a) Training-time Probability Path for Planar Graphs
(b) Training-time Tree Graph Probability Path
moleculesi evolution by over flow
-0.4
Reggthe Atom Wild
-0.8
Artresctic Buiea- Wessentenn
2.0
Fow steps
(c) Training- time QM9 Molecule Probability Path. We use negative validity for clear comparison.
Figure 6: Training-time probability path comparisons for planar, tree and QM9.
1.7 3D MOLECULE GENERATION: QM9 WITHOUT EXPLICIT HYDROGEN
In Table 17 report the results of QM9 without explicit hydrogen. This task is relatively easy compared to the generation task with explicit hydrogen, and both Midi and our BWFlow have achieved near-saturated performance with validity to 100%.
37

---

Published as a conference paper at ICLR 2026
The avolution statietics flo time (SBM
Comeeggence Gap
Average Ratoo
23
Linear Interpolation
Time Distortion (Qin et al.)
Target IQin
BW Interpoletion (Durs)
08 02
08
1.0
Flow Steps
(a) Sampling path comparision on Planar dataset
(b) Sampling path comparision SBM dataset
Figure 7:
The probability path reconstruction in the sampling stage on a) Planar graphs and b) SBM
graphs.
The Training Curve on QM9 with explicit Hydrogen
0.8
0.4
0.4
0.2
Training steps
200
400
800
500
Homossi
Bures Warestee
Arthaseic
33c
60c
(a) QM9 with explicit hydrogen
(b) Planar
Figure 8: Training curves on QM9 and planar datasets with explicit hydrogen.
1.8 CONVERGENCE ANALYSIS
Fig. 8 are the training convergence analysis Planar and QM9 dataset, showing that BWFlow provides a fast convergence speed than others.
J USAGE OF LARGE LANGUAGE MODELS (LLMS)
used large language model to assist with writing and editing this manuscript, primarily for grammar, style, and clarity. The authors are fully responsible for the content and scientific integrity of the work.
comm-20
FM type
Interpolation
Deg.
Clus.
Orbit.
Linear
0.071
0.115
0.037
Harmonic
0.011
0.036
0.027
Discrete
Geometric
0.047
0.083
0.02
BW
0.009
0.013
0.017
Table 16: Quantitative experimental results on COMM20
(smaller dataset).
38

---

Published as a conference paper at ICLR 2026
Metries
Dataset
Interpolation
Connected((5) V.U.N(%)
Charges(10
Atom(10
Angles(")
MiDi
1.00
98.0
100.0
0.4
5.1
1.49
QM9 (w/o h)
Linear Flow
1.60
79.33
52.3
0.7
14.0
8.77
BWW
1.02
99.8
100.0
0.4
4.8
1.53
Table 17: Quantitative experimental results on QM9 datasets without explicit hydrogen in 3D molecule generation.
Symbol
Meaning
General flow matching
S
State space of variables (c.g., X 6 S)
X/ //X// X (with ~ x(2;;
Random variable realization latent parameters Source and target distributions over X
Po, P1
Pt(2)) [x)
Time-continuous probability path between and P1 Time- deeendepndd flow map (CNF flow)
True velocity field generating Pt.
e
Parameterized velocity field Probability measures S in OT formulation Set of couplings between ?/ and !h1 Transport plan (joint measure on S S) Transport cost between X and Y
no. 71
[ 1/))
[( m)
(X,Y) Wc(no:p)
Wasserstein distance associated with cost e
Graphs and Graph Markov Random Fields
9= -V,EEX))
Random graph (nodes, edges, node features)
G (V,
Realization of G, with nodes, edges and node features Random node set, edge set, and feature set Weighted adjacency matrix of the graph distribution Node feature matrix of the graph distribution
V {u),E= {E {xr}
W R. PNNV
X [1,-..., xpp.
D diag(W1)
Degree matrix (1: all-one vector) of the graph distribution Graph Laplacian matrix of the graph distribution Node-wise and pair- wise MRF potentials Node-specific latent mean for Vrg
D W
PI (2,)))))(
Pv
A
Covariance Matrix
Bures-Wassee Wasserstein Flow Matching
11 Te, dyw 91)
Measure over graphs (factorized as node and edge measure) Mures-Wasserssthi distance between two graph distributions Intermediate random graph along BW interpolation Conditional probability path induced by BW interpolation Conditional velocity graph state G₃ Conditional edge velocity
G. = &V)
p(Gr G1)
GG Go, G1)
2 E, Go, G1)
" (Xe G1)
Conditional node-feature velocity Parameterized velocity used training sampling
of (G.)
Categorical (v) (ornoull([W]]]]
Categorical distribution over node feature states at node
Bernoulli edge distribution between nodes u and
o(G,,))
Dirac distribution concentrated at graph G; (i = 0,
Table 18: Notation Table.
39


Reviews:
[{"review_id": "zUpwPSddNL", "reviewer": "Reviewer_mpf9", "summary": "This paper studies the graph generation problem, via flow (matching) model. The notable point is that this paper formulates the graph with Markov Random Fields (MRFs) so that the interpolation on GraphMRFs can include the interaction between nodes and edges, greatly different from the previous work, whose node and edge interpolations are independent (Eq. 5). Some followup results, e.g., what is the closed-form interpolation, and the velocity at the interpolation point, are presented.", "questions": "Please check the above questions.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. Good motivation. \"MRFs organize the nodes/edges as an interconnected system and interpolating between two MRFs captures the joint evolution of the graph system\" sounds reasonable to me.\n\nS2. This paper's presentation is nice. Even without checking the detailed mathematical derivations, I can still follow the story in the main content.\n\nS3. The experimental results seem impressive.", "weaknesses": "Generally, i am satisfied about the quality of this paper. Here are some questions/suggestion which might be able to improve this paper.\n\nQ1. From lines 66 to 82, it introduces the motivating example of this paper. It is a bit confusing why t=0.8 is such an important point. If this is purely empirical observation, or there are some mathematical reasons?\n\nQ2. Can we understand the proposed method as a kind of latent diffusion/flow method, just like the stable diffusion did? I understand that the proposed method does not include an explicit encoder/decoder, and the I like the interpolations/velocity derived based on the colored\nGaussian distribution. Asking because the Figure 2 somewhat shows such a connection between flows in raw graph space and latent space.\n\nQ3. About the OT paths. To be specific,\n\nQ3.1. According to the Algorithm 1, the interpolation is on the OT path between a pair of G_0 and G_1, but not the in-batch OT coupling between a batch of {G_0} and {G_1}, is that right? But I think it should be easy to generalize to the mini-batch OT coupling setting as [1] did, is that right?\n\nQ3.2 I can buy the story that \"capture global co-evolution (Haasler & Frossard, 2024) of the graph components\" for the interpolation is important, but whether the OT interpolation/path really matters? Asking because in many recent flow model studies, the straight line interpolation's best advantage is more on the efficiency (so fewer sampling steps), but not on the effectiveness.\n\n[1] Improving and generalizing flow-based generative models with minibatch optimal transport", "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": "v0YvXgj3h6", "reviewer": "Reviewer_W2yQ", "summary": "The paper proposes BWFlow, a flow-matching framework for graph generation that constructs a smooth, joint probability path by modeling graphs as Markov random fields (MRFs) and leveraging optimal transport between MRFs. It argues that existing diffusion/flow methods use independent, linear node/edge interpolations that disrupt graph dependencies, leading to irregular paths and unstable training. By enforcing co-evolution of nodes and edges along the derived optimal path, BWFlow aims to improve training dynamics and sampling convergence. Experiments on plain graph and molecular generation report competitive or better performance, faster convergence, and more efficient sampling.", "questions": "Given the computational overhead, would a hybrid schedule be feasible—one that leverages linear interpolation for early stages and switches to the proposed BWFlow when most beneficial?\n\n\nIn Section A.3 there are cases where GraphMRF may be suboptimal for certain graph structures. Can structural information be injected to improve performance—for example, via higher-order graph features, subgraph/ motif features, or structural role embeddings?\n\nline 479 \"When scaled up to large\nbut sparse graphs, the complexity can be reduced to O(TN2)\", what is T", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, clear, and methodologically sound, presenting complex ideas with precision and rigor.\n\nIt establishes a theoretical framework for probability-path construction directly within Markov Random Field (MRF) space, enabling coherent joint node–edge evolution that respects graph-structured dependencies.\n\nIt introduces a novel integration of MRFs with optimal transport, using MRFs as the ambient representation space for probability paths in a way that naturally aligns with graph topology and conditional dependencies.", "weaknesses": "While acknowledged in the limitations, BWFlow incurs substantial computational overhead, and reducing this cost appears non-trivial.\n\nThe experimental evaluation omits several GNN-based baselines, including DisCo (Xu et al., 2024), limiting the completeness of the comparison.", "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": "bLTfLduOb4", "reviewer": "Reviewer_sj7x", "summary": "This paper proposes Bures–Wasserstein Flow Matching (BWFlow), a generative modeling framework for graphs that integrates flow matching with the Bures–Wasserstein (BW) geometry on a Graph Markov Random Field (GraphMRF) representation. The authors first formalize graphs as random fields on nodes and edges (GraphMRF), establishing a Gaussian joint distribution whose covariance is tied to the graph Laplacian. They then derive a closed-form expression of the Bures–Wasserstein distance between two graphs, together with an analytical interpolation path and conditional velocity field, which enable flow matching without simulation. The method is further extended to a discrete version (with categorical node features and Bernoulli edges), and training/inference procedures are given. Comprehensive experiments on graph generation benchmarks are reported.", "questions": "1. In Fig. 1(c), when flow steps = 1.0, the Time Distortion method yields a slightly smaller value than the BW interpolation. Does this imply that Time Distortion is comparably efficient in this setting?\n\n2. Could the authors elaborate on the modeling assumption $p(\\mathcal{G};\\mathbf{G})=p(\\mathcal{X};\\mathbf{X},\\mathbf{W})\\cdot p(\\mathcal{E};\\mathbf{W})$? Why are the node features and edge structures conditionally independent, except for the coupling through 𝑊? How critical is this assumption for the GraphMRF formulation?\n\n3. Does the model scale to large graphs?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper presents a mathematically coherent framework connecting graph optimal transport and flow matching. The closed-form derivations of the BW interpolation and velocity fields are valuable theoretical contributions.\n\n2. Using the BW metric on graph Laplacians provides a geometrically meaningful way to measure and interpolate between graph distributions, which addresses a long-standing issue of linear interpolation violating graph manifold constraints.\n\n3. The experimental section is relatively comprehensive, covering various types of graph data, including plain graphs, molecular graphs, and 3D molecular structures.", "weaknesses": "1. The methodological novelty is mainly compositional: the work combines existing Bures–Wasserstein distance (already applied to graph covariance learning) with the established flow-matching framework under a Graph MRF formulation, resulting in limited originality.\n\n2. The empirical evaluation lacks consistency with standard benchmarks (e.g., DiGress, GruM, DeFoG) and omits common molecular-graph metrics such as Validity, Uniqueness, and Novelty. The results would be more convincing if experiments used the same datasets and evaluation metrics as prior baselines.\n\n3. The paper does not isolate the effect of replacing Euclidean interpolation with the BW distance, nor does it provide a systematic comparison between the continuous and discrete variants. Without such analysis, it is unclear whether BW geometry truly contributes to the observed performance.\n\n4. The notation system is heavy, and some equations are symbolically dense without intuitive explanation or visualization.\n\n5. The paper does not mention a code release to ensure reproducibility.", "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": "G9Z3ijYiU0", "reviewer": "Reviewer_PTxT", "summary": "This paper proposes a novel graph generation method using flow matching. First, it is pointed out that methods generating graphs via linear interpolation fail to smoothly change graph statistics, leading to poor flow velocity estimation accuracy and convergence gaps. Building upon this, the proposed method models a graph using Markov Random Field, estimates a vector field derived by the optimal transport on this model using the flow matching. Numerical experiments applied the proposed method to three graph generation tasks, 2D and 3D molecular graph generation tasks, verifying its generation performance.", "questions": "1. I would like to clarify the experimental setting details for Figure 1a in the Introduction.\n2. I would like the authors to address the question regarding the discussion of the results in Figure 3a, which is the second point under Weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. (Originality) In graph generation tasks using flow matching, incorporating graph structure is non-trivial. This paper solves this issue by modeling a graph using the Markov Random Field. To my knowledge, this is the first paper to propose such a solution.\n2. (Quality) There is design flexibility in how to set the velocity field in flow matching. This paper provides a theoretical background by employing the Optimal Transport. Furthermore, while optimal transport computations are typically high, the proposed method overcomes this problem using the Markov Random Field. This makes the approach practically implementable.\n3. (Clarity) The writing is clear. It explains the necessary background knowledge (Markov Random Fields, Optimal Transport) to understand the proposed method. The mathematical descriptions are also appropriate. Therefore, I had no significant difficulties in understanding the paper's main points.\n4. (Significance) Numerical experiments demonstrate generation performance of the proposed method surpasses existing methods, which strengthens the significance of the work in the area of graph generation research.", "weaknesses": "1. The paper points out that the problem with the existing methods is that they ignore graph structure and generate nodes and edges independently. However, the experiments verify the limitations of linear interpolations. Therefore, it seems unclear whether the problem lies in ignoring graph structure or in using linear interpolations.\n2. I have a question about the interpretation of the results in Figure 3a. Looking at Figure 1a of the introduction, the authors assume that ideal interpolation changes graph statistics linearly. However, the discussion on Figure 3a suggests that it is desirable that statistics first increase and then decay. It seemingly contradicts the claim in Figure 1a and it would be more natural to claim that linear interpolation is preferable.", "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)