DeFoG: Discrete Flow Matching for Graph Generation
Authors: Yiming QIN
Manuel Madeira
Dorina Thanou
Pascal Frossard
Venue: ICML 2025 oral (2025)
Keywords: Graph Generation
Flow Matching
Primary area: deep_learning->generative_models_and_autoencoders
TL;DR: We propose DeFoG, a discrete flow matching-based framework for graph generation with improved sampling efficiency and state-of-the-art performance across synthetic and molecular datasets.

Abstract: Graph generative models are essential across diverse scientific domains by capturing complex distributions over relational data. Among them, graph diffusion models achieve superior performance but face inefficient sampling and limited flexibility due to the tight coupling between training and sampling stages. We introduce DeFoG, a novel graph generative framework that disentangles sampling from training, enabling a broader design space for more effective and efficient model optimization. DeFoG employs a discrete flow-matching formulation that respects the inherent symmetries of graphs. We theoretically ground this disentangled formulation by explicitly relating the training loss to the sampling algorithm and showing that DeFoG faithfully replicates the ground truth graph distribution. Building on these foundations, we thoroughly investigate DeFoG's design space and propose novel sampling methods that significantly enhance performance and reduce the required number of refinement steps. Extensive experiments demonstrate state-of-the-art performance across synthetic, molecular, and digital pathology datasets, covering both unconditional and conditional generation settings. It also outperforms most diffusion-based models with just 5–10\% of their sampling steps.

DeFoG: Discrete Flow Matching for Graph Generation
Yiming Qin Manuel Madeira
Dorina Thanou' Pascal Frossard
Abstract
proaches, demonstrating pioneering performance in appli- cations such molecular generation (Irwin et al., 2024), reaction pathway design (Igashov et al., 2024), neural ar- chitecture search (Asthana et al., 2024), and combinatorial optimization (Sun & Yang. 2024). Recently, continuous- time discrete diffusion frameworks have further advanced the domain of discrete graph diffusion (Xu al., 2024; Siraudin et al., 2024). These frameworks leverage the ro- bustness and flexibility of continuous-time modeling, while preserving the natural alignment with the discrete structure of graphs.
Graph generative models are essential across diverse scientific domains by capturing complex distributions over relational data. Among them, graph diffusion models achieve superior perfor- mance but face inefficient sampling and limited flexibility due to the tight coupling between training and sampling stages. We introduce DeFoG, novel graph generative framework that disentangles sampling from training, enabling broader design space for more effective and efficient model optimization. DeFoG employs a discrete flow-matching formulation that respects the inherent symmetries of graphs. We theo- retically ground this disentangled formulation by explicitly relating the training loss to the sampling algorithm and showing that DeFoG faithfully replicates the ground truth graph distribution. Building on these foundations, we thoroughly investigate DeFoG's design space and propose novel sampling methods that sig- nificantly enhance performance and reduce the required number of refinement steps. Extensive experiments demonstrate state-of-the-art perfor- mance across synthetic, molecular, and digital pathology datasets, covering both unconditional and conditional generation settings. also outperforms most diffusion-based models with just 5-10% of their sampling steps.
Despite their state-of-the-art performance, the training and sampling stages of diffusion-based models is tightly entangled, restricting sampling options training-phase choices. Thus, optimizing components such noise schedules rate matrices requires re-training for each configuration, resulting in prohibitive computational costs. Consequently, these models often adopt single configura- tion across graph datasets. This one-size-fits-a approach fails to accommodate the diverse structural characteristics of different datasets, leaving room for further improvement.
In this work, present DeFoG, novel graph genera- tive framework that disentangles the training and sampling stages (Figure la), addressing the inefficiencies in graph diffusion models and achieving state-of-the-art (SOTA) performance. DeFoG leverages a discrete flow matching (DFM) inspired formulation (Campbell et al., 2024) that we tailor to graph settings. features linear interpola- tion noising process and continuous-time Markov chain (CTMC)-based denoising process, while ensuring node permutation equivariance and addressing the model expres- sivity limitations inherent to this data modality (Morris et al., 2019). We demonstrate that training-sampling de- coupling not only enhances flexibility but is also provably sound. By theoretically establishing that training loss op- timization leads to improved sampling dynamics, DeFoG enables faithful replication of the ground truth graph dis- tribution. To navigate the expanded design space enabled by such disentanglement, we take critical step by "defog- ging" this space. Specifically, we explore and propose var- ious sampling methods, including time-adaptive methods and modifications to CTMC rate matrices, to better govern denoising trajectories and align with the unique character- isties of graph datasets.
1. Introduction
Graph generation has become a fundamental task across diverse fields, from molecular chemistry to social net- work analysis, due to graphs' capacity to represent com- plex relationships and generate realistic structured data. Diffusion-based graph generative models (Niu et al., 2020; Jo al., 2022), particularly those tailored for discrete data (Vignac et al., 2022), have emerged as compelling ap-
'Equal contribution 'EPFL, Lausanne, Switzerland. Cor- respondence to: Yiming Qin <<yiming.ii@eepflch>> Manuel Madeira manuel epfl.ch>>.
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

DeFoG: Discrete Flow Matching for Graph Generation
State
Po (x)
(x) Noising P = (1 - t) Po + +tp
(m)
Continoous
Discrete
Pi
Disernt
Initial
Dicreteness
Fransoork
Replitaaion
Time
Continnons
(m)
n Rg/l At
[nl
(w) Firds
Pe-aate
Plodible
SOTA
Sampling
Sumple
DeFoG
Entangled
Gt
Denoising
G++at
Decoupled Training & Sampling
(HG.)
(a) Motivation of DeFoG.
Overview of DeFoG.
Figure 1: (a) DeFoG enhances graph generation by introducing training-sampling decoupling, an orthogonal improvement within graph iterative refinement models, while preserving the sampling flexibility and inherent discreteness exploitation of prior SOTA models.
(b) One node, x((1) is selected to illustrate both noising and denoising processes. For noising, DeFoG follows a straight path from the one-hot encoding P1 of the clean node to the initial distribution po- For denoising, a network parameterized by predicts the marginal distributions of the clean graph, there the node's distribution (..0%) (-I+.)
Pij used compute its rate matrix R²x()) and, subsequently, its probability at the next time point + At.
Our experiments show that DeFoG achieves SOTA perfor- mance across diverse datasets, with near-saturated validity of 99.5%, 96.5%, and 90% on planar, tree, and stochas- tic block model (SBM) datasets, respectively. On com- plex molecular data, it achieves 92.8% validity on MOSES (Polykovskiy et al., 2020), surpassing the previous SOTA of 90.5%. Moreover, DeFoG achieves 95.0% and 86.5% validity on planar and SBM datasets, respectively, with only 5-10% of the sampling steps used by diffusion mod- els. This performance surpasses all but one diffusion model on the planar dataset and ranks best SBM, highlighting substantial efficiency gains. To further highlight the versa- tility of DeFoG, we also test it in conditional generation tasks for digital pathology, where it largely outperforms existing unconstrained models. Ablation studies further confirm the need of each proposed sampling method and highlight the importance of -ppasct- sampling pro- cedures to effectively address diverse data characteristics.
crative models in real-world applications.
2. Background
In generative modeling, the primary goal is to generate new data samples from the underlying distribution that pro- duced the original data, Paata An effective approach is to learn a mapping between a simpler distribution p. that can be easily sampled, and pdata.
Iterative refinement models achieve this mapping through a stochastic process over the time interval t [0, 1) for vari- ables in discrete state spaces. For the sake of simplicity, we describe here an univariate formulation. At any time t, we consider discrete variable with Z possible values, denoted by 2 E 2 = f1..... : Z}. The marginal distri- bution of 2, is represented by the vector Pt. E A2, with A { E RR2 Σ in 1, u, 2 0, Vi). Vi The ini- tial distribution is set to a predefined noise distribution, Po Pr. while p1 = Paata represents the target data distri- bution. We refer to the mapping t : + 0 as the noising process and t: - 1 as the denoising process.
Our main contributions are as follows:
We introduce DeFoG, novel graph generative model that effectively exploits the raining-sampling decou- pling enabled by its flow-based formulation, signifi- cantly enhancing sampling flexibility and efficiency.
DFM (Campbell al., 2024) builds upon streamlined noising process. In particular, the noising trajectory Piji 21) E [o, 1] is defined through a simple linear in- terpolation starting from a chosen datapoint 21:
We provide a theoretical foundation for both our train- ing and sampling algorithms, validating the soundness of the disentanglement framework;
Peji (=) = t 5(2,, =1) + (1 - (1) po(=))
(1)
We comprehensively explore DeFoG's design space with novel training and sampling approaches, high- light critical configurations for graph data and attain state-of-the-art performance across diverse datasets.
where 5(2,, 21) is the Kronecker delta (1 when 2, = =1). A usual choice for the initial distribution is the uniform distribution over the state space, Po [1/Z..., 1/2].
Overall, DeFoG enables more effective graph generation with reduced computational costs under theoretical guar- antees, paving the way for broader adoption of graph gen-
In the denoising stage, DFM leverages a CTMC formula- tion. In general, a CTMC is characterized by an initial dis- tribution, Po, and a rate matrix, R, E R. xx that governs
2

---

DeFoG: Discrete Flow Matching for Graph Generation
its evolution across time E [0, I]. Specifically, the rate matrix defines the instantaneous transition rates between states, such that:
replicate graph distributions. Then, we discuss the ex- panded design space enabled by DeFoG's disentanglement, which drives key improvements in graph generation perfor- mance. Finally, we establish the node permutation equiv- ariance/invariance guarantees of DeFoG.
P(+dl1(((44aelz)) 0(2,, #t4de) + Re(E2, ac+ae)d(, (2)
where Re(zz,,2440) denotes an entry in the rate matrix. Intuitively, Re(z,, )tt yields the probability that a transition from state 2, state Ze will occur in the next infinitesimal time step dt. By definition, we have Re (Z,, a++dt) 2 O for # dt Consequently, we fur- ther have Re(2,, zt) = -E (artt, Re(zz, Zt+dt) to en- sure normalization Exsta Pt- (2ta)e(2(=a 2x) = 1. Under this definition, the marginal distribution and the rate ma- trix of a CTCM are related by conservation law, the Kol- mogorov equation, given by d.p: = R2 Pt- If expanded, this expression unveils the time derivative of the marginal distribution as the net balance between the inflow and out- flow of probability mass at that state.
3.1. Learning Discrete Flows over Graphs
We instantiate undirected graphs with N nodes as G (=1m:N elitej:A), where 2= = (x(")) and clucs::N = -(((9)) (elssss denote the node and edge sets, respectively, with x(() E X = {l....,X} and e(i)) e & fl..... EE.. Following standard practice in the field (Vignac et al., 2022; Xu et al., 2024; Siraudin al., 2024), we consider edge between every pair of nodes, where one of the edge categories explicitly represents the absence of an edge (i.e., "non-existing" edge).)
Noising We now define the noising process of DeFoG, According to Eq. (1), with shared initial distributions across nodes and edges, denoted as p and pÊ. respec-
Similarly to the noising process of Eq. (1), the denoising is also performed under conditioning on 21. Specifically, we consider a ø1 -onnditional rate matrix, Re(,,-121) E R that will govern the denoising in DFM. Under mild assump- tions, Campbell et al. (2024) present a closed-form for a valid conditional rate matrix, i.c., a matrix that verifies the corresponding Kolmogorov equation, for 2t F ze-dt- de- fined as:
tively, we formulate the noising trajectory by independently adding noise to each node and each edge:
Paja (G) II Paji
(n) (x
(1)) x
II Pan (& (p
(c"0)e(())
(c( (e(()))
icj
Different pe and pf are further discussed in Appendix C.I.
Sampling As formulated in Sec. 2, the denois- ing process requires simulating a CTMC, driven by its rate matrix R2. We start by sampling purely noisy graph Go from the predefined initial distribution po = II rd (# (e))). Then, we progress in the denoising process by employing independent Euler steps for each node and edge, with a finite time step At, i.e., we iteratively sample progressively denoised graphs from (eet
R7 (2t, 2+4de|21)= = ReLU (zc+del=)) P.pen1 (2x|²1)]
27 Ptp1 (/p(21/20) (2)
(3) and 2,70 = 1izz (en > 0H- Again, normaliza- tion is performed for the case dt+ = 2t Intuitively, R; applies a positive rate to states needing more mass than the current state 24 (details in Appendix B.5). Finally, it can be shown that (2,,, 2t+at) = Bepneessee.) (R((rrttt 2e =)), which is employed in Eq. (2) for denoising.
given by:
Il (n) n
PEtAN (F Go) 140
II
10) PHAA (Cte Ge).
(4)
While the DFM paradigm enables training-sampling dis- entanglement, it lacks a complete formulation and empiri- cal validation on graph data. Moreover, how to effectively leverage this disentanglement to enhance sampling per- formance remains underexplored, particularly for graph- specific tasks. We introduce DeFoG to address these gaps.
G.) corresponds to the Euler step given in Eq. (2), where the transition dynamics governed by the rate matrix computed as:
(n) Each term p (
(n) R((") [2) (etar) = E Min (e
[R("] (alm). (o
(m)
3. DeFoG Framework
(5)
(00) and similarly for Pr+ (c (Gt)..)))
In this section, we present DeFoG (Discrete Flow Match- ing on Graphs), a novel iterative refinement framework for graph generation that leverages the decoupling of training and sampling stages. We begin by describing its noising and denoising processes, highlighting how they enable this disentangiement, as illustrated in Figure lb. We theoret- ically demonstrate that this flexible framework is also ro- bust by proving that optimizing the training loss improves sampling dynamics, ensuring that DeFoG can faithfully
Training The rate matrix used in the denoising steps above requires the knowledge of the marginal distributions ((m) (-IG.) E A and p (-IG.) E A for all nodes and all edges, respectively. Both are gathered in PHx(-IG,)) = lakkj:N (IG.)). Each of these compo- nents consists of the clear marginal distribution predic- tion given a noisy graph G,. However, the computation
[ Pit
3

---

DeFoG: Discrete Flow Matching for Graph Generation
Algorithm/ 1 DeFoG Training
Algorithm 2 DeFoG Sampling
1: Input: Graph dataset = "G*,..., GM}
1: Input: # graphs to sample S
2: while fo not converged do
2: for i 1 to S do
3: Sample G DD
3: Sample N from train set
# Nodes
4: Sample t ~ T
4: Sample Go po Poo)
5: Sample G2 ~ (Gp(G
Noising
5: for 0 to 1 At with step At do
6: h + RRWP(G,)
> Extra features
6:
h t- (--RRPP(G.)
Extra features
7: (GG.) + fo(G,, t)
Di Denoising prediction
7:
(-G)) fo(G,, h,t) Denoising prediction
8: loss + CEx(G, p/ (-GG,) (ptimizer.step(loss)
8:
GztAr De+anr(G+aallG))
P Eg. (4)
9:
Store G1
of these terms is generally intractable. Instead, we train neural network, parameterized by 0, to approximate them, p (-Gr). To cover different noise levels, we sample t ~ T, where T is an arbitrary distribution over [0, 1]. In DFM, T is typically set to the uniform distribution, though alter- native choices can enhance performance, as later explored in Sec. 3.2. The training loss is naturally formulated as:
By taking the expectation over t T and summing over G2, minimizing the derived upper bound of rate matrix es- timation error in Theorem with respect to @ corresponds directly to minimizing the loss function of DeFoG with À = 1. Therefore, we guarantee that our training loss min- imization is aligned with accurate rate matrix estimation.
Upon this result, we are now in conditions of justifying De- FoG's approximated denoising algorithm.
DDF LETT pu (GL). (G. CEA(GI, (GI, P(je(-))))
Corollary 2 (Bounded deviation of the generated graph distribution). Let P1 be the marginal distribution at of a groundtruth CTMC, {Gr)osesı, and fí be the marginal distribution at dimensional Euler sampling approximation, with maximum step size At. Then, under Theorem 6, the following total variation bound holds:
where CEx(GI,, P (-) is defined as:
(.)m (x)(")(((""))) (n) (.) - A Eies log (Fije - En log (Pile (zl
0.000 (8)) (e (())))
of its independent-
Here, A E R is introduced to weight nodes and edge differently to more flexibly capture varying topologies.
Decoupled Training and Sampling DeFoG exhibits a clear disentanglement of training and sampling. The train- ing phase focuses on predicting the marginal probabilities of the clean graph p (-IG.), while sampling relies the rate matrix formulation. Importantly, the training process is agnostic to the choice of the 21 21-conditional rate ma- trix. Thus, different 21 condiiiiao rate matrices can be employed at sampling time, such as R (; in Eq. (3). This decoupling of sampling from training provides addi- tional flexibility in DeFoG's design, which can be lever- aged to further enhance performance. Notably, further demonstrate that, upon this decoupling, optimizing De- FoG's training loss improves its sampling dynamics, en- suring the soundness of our framework.
[Ip(G,) -Pounall rV SO (XN+ F.
N(N 1)
+ B XN+E N(N 1)
AL O(A(),
2
where U and are constant upper bounds for the bound from Theorem I and for the denoising process relative to noising counterpart, respectively, for any 1 E [0,11)
The first term of the bound captures the estimation er- ror introduced by using the neural network approximation Rt (G., Gt+de). From Theorem 1, this term is bounded. The remaining terms arise from the discretization of the CTMC and can be controlled by reducing the step size At. Consequently, the deviation introduced by this approxima- tion can be made arbitrarily small, ensuring that the gener- ated distribution remains close to the groundtruth and vali- dating our graph sampling scheme.
Corollary (Bounded estimation error of rate matrix for graphs). Given E [0, 1] and graphs G., Gr-at and G2 (G1)), there exist constants Co C1, C3 > 0 such that the rate matrix estimation error can be upper bounded by:
[R,, (GG,Ge+aa)
R2, (Gi, ? < Co+
The resulting training and sampling processes are detailed in Algs. 1 and 2. The proofs of Theorems and are pro- vided in Appendix D.
+ Ō (p)(G)
Pil (G
Σ log (2(")(((())) (a(ma) Gi) (G)
(m(m)
3.2. Design Space of DeFoG
+ C2 (p.(
(GrlG) Σ - log P11t
0.(1) (1))
(e) Gi)
As described in the previous section, DeFoG benefits from greater flexibility due to its sampiinng decoupling.

---

DeFoG: Discrete Flow Matching for Graph Generation
For example, it allows the number and size of sampling steps to be adjusted dynamically, unlike the fixed steps in discrete-time diffusion (Vignac et al., 2022), and enables adjustment of the rate matrix without retraining, address- ing limitations of continuous-time diffusion graph mod- els (Siraudin et al., 2024; Xu et al., 2024). This decoupling supports extensive, training-free performance optimization during the sampling stage, which is crucial for improving performance and reducing the number of sampling steps. Below, we propose the key components of DeFoG that are enabled by this disentanglement.
tion arises from the goal of better guiding the generation process toward the clean data distribution (Song et al., 2020a). This also aligns with the fundamental design of diffusion and flow matching models, which are structured to predict clean data directly and subsequently use that pre- diction to generate the denoising trajectory (Ho et al., 2020; Lipman et al., 2023; Vignac et al., 2022). Inspired by these principles, we propose an alternative sampling mechanism that seeks to further amplify the influence of the denois- ing neural network's predictions in the designed rate ma- trices, by setting Re(=; #++a(/z1) = Rī (2x, #t+at/=1) + Rij (1,22+))(21) for 21 F Ze+dr, such that:
Sample Distortion In DFM's sampling process, the discretization is performed using equally sized time steps (Alg. 2. line 5). However, this uniformity may fail to preserve key properties during critical intervals where finer control is needed. For instance, smaller steps are essential near the final stages of sampling to prevent sudden edge alterations that could compromise global properties such as planarity. To overcome this limitation, we propose using variable step sizes, allocating smaller, more frequent steps during these critical intervals to better capture essential graph characteristics. Specifically, we apply to each timestep a bijective, increasing distortion function f defined for & E [0, 1], yielding L' ((t). For example, the choice ft) 2t (referred to polydec) creates mono- tonically decreasing step sizes, emphasizing the final stages of sampling, where error correction can be most critical. The specific distortion functions employed are described in Appendix B.I. Importantly, we can efficiently (i.c., without re-training) adjust the sample distortion adopted for each dataset to better accommodate its graphs characteristics, leading to significant performance improvements.
R7 244 = w (((++de) #1) 2,-0 (zri(z)
(6)
This adjustment increases the weight of transitions in the rate matrix when Ze-di 21, where 21 is the predicted clean data. While moderate increases in w significantly en- hances performance by steering the generation toward high confidence domains, excessively high w leads to perfor- mance drop. This behavior is explained in Theorem 10, in Appendix B.2, where we show that target guidance in- troduces an O(w) violation of the Kolmogorov equation. Consequently, finding an optimal value for is essential
Stochasticity Orthogonal to target guidance, there also exists unexplored potential in the design space of condi- tional rate matrices that preserve the Kolmogorov equa- tion as the standard formulation of R (zc. 2t4a|/2) does not fully capture this space. As demonstrated by Camp- bell et al. (2024), for any rate matrix I2P8 satisfying the detailed balance condition Ptt (2t (21 (2 RRD
( (st, =+4r| Pepi (#++ar|2)) RDB ( (Ee+ 21|21), the modified rate matrix R = R + nRP", with E Rt. is also valid. In- tuitively, increasing facilitates more transitions to other states while reducing the likelihood of remaining in the same state, thereby increasing stochasticity in the trajectory of the denoising process. This approach can be interpreted as correction mechanism, as it draws transitions back to states that would otherwise be forbidden according to the rate matrix formulation, as described in Appendix B.5. Ad- ditionally, different designs of RPB encode different priors for preferred transitions between states, which we investi- gate in detail Appendix B.3.
Train Distortion Once the optimal sampling distortion is identified, it can guide training by highlighting the critical time ranges for graph generation in a specific dataset. This enables adjustments to the training distribution T, skew- ing it toward these ranges to focus the model's capacity on the most relevant regions. The skewed distributions are ob- tained by passing uniformly sampled times t through the same distortion functions. While similar strategies in other modalities, such as image generation (Esser et al., 2024), often emphasize intermediate time ranges, we find that op- timal time ranges in graph generation vary across datasets. Aligning the distortion function in training with sampling typically enhances the algorithm by focusing on critical time ranges. For instance, for larger datasets, such as drug- sized molecular graphs, the polydec distortion function ac- celerates convergence significantly and provides noticeable performance improvements.
3.3. Permutation Invariance Guarantees
Graph generative models should respect the inherent per- mutation symmetries of graphs. Accordingly, DeFoG's s training and sampling algorithms should be independent of node ordering. This requires that both DeFoG's loss func- tion during training and its probability of generating a spe- cific graph during sampling be permutation invariant. We formally demonstrate these results in Theorem 3, whose proof is in Appendix 1.2.
Target Guidance The application of time distortions is not the sole avenue for optimizing the sampling process; the design of the conditional rate matrices also offers sig- nificant potential for improvement. One promising direc-
5

---

DeFoG: Discrete Flow Matching for Graph Generation
Lemma 3 (Node Permutation Equivariance and Invariance Properties of DeFoG). For any permutation equivariant denoising neural network, the loss function of DeFoG is permutation invariant, and its sampling probability is per- mutation invariant.
Discrete Flow Matching Flow matching (FM) models emerged a compelling alternative to diffusion models among iterative refinement generative approaches for con- tinuous state spaces (Lipman et al., 2023; Liu et al., 2023). FM frameworks have been empirically shown to enhance performance and efficiency in image generation (Esser et al., 2024; Ma et al., 2024). To address discrete state spaces, DFM formulation has been introduced (Campbell et al., 2024; Gat et al., 2024). This approach streamlines its diffusion counterpart by employing linear interpolation noising process and more flexible CTMCCbaaee denois- ing process, whose rate matrices, unlike diffusion models, need not be fixed during training. While other flow-based formulations for graphs have been proposed (Eijkelboom et al., 2024), DeFoG stands out as the first DFM-based model for graphs, leveraging training-sampling decou- pled formulation for improved performance.
We further describe the permutation equivariant denoising neural network of DeFoG in Sec. 5.
4. Related Work
Graph Generative Models Graph generation has ap- plications across various domains, including molecular generation (Mercado et al., 2021), combinatorial optimiza- tion (Sun& & Yang, 2024), and inverse protein folding (Yi et al., 2024). Existing methods for this task generally fall into two main categories. First, autoregressive models progressively grow the graph by inserting nodes and edges (You et al., 2018; Liao et al., 2019). Although these methods offer high flexibility in sampling and facilitate the integration of domain-specific knowledge (e.g.. for molecule generation, Liu et al. (2018) perform valency checks at each iteration), they suffer from a fundamental drawback: the need to learn node ordering (Kong et al., 2023; Han et al., 2023), or use a predefined node ordering (You et al., 2018) to avoid the overly large learning space. In contrast, one-shot models circumvent such limitation by predicting the entire graph in single step, enabling the straightffrward incorporation of node permutation equivarianceelivatiannee properties. Examples of these approaches include graph-adapted versions of VAEs (Kipf & Welling, 2016), GANs (De Cao & Kipf, 2018), or normalizing flows (Liu et al., 2019). Among one- shot methods, diffusion models have gained prominence for their state-of-the-an performance, attributed to their iterative mapping between noise and data distributions.
5. Experiments
This section highlights DeFoG's SOTA performance, en- abled by its highly decoupled framework and effective sam- pling methods. We present DeFoG's performance in gen- erating graphs with diverse topological structures and in molecular datasets with rich prior information. We also provide ablations to showcase the effectiveness and neces- sity of each proposed sampling method. We highlight the best result and the second-best method. Results for gen- eration with 5-10% of steps used by previous SOTA dif- fusion models are also provided to demonstrate DeFoG's s sampling efficiency. We show DeFoG's versatility on con- ditional generation for digital pathology in Appendix G.I.
Setup To isolate the effect of the network architecture, we build DeFoG on the best-performing graph transformer on generative tasks (Vignac et al., 2022). To enhance ex- pressivity, we incorporate Relative Random Walk Proba- bilities (RRWP) (Ma et al., 2023; Siraudin et al., 2024) as node and edge features. More details on the archi- tecture in Appendix F.I. Our ablations in Appendix G.4 show that, while RRWP features encode structural proper- ties more efficiently and effectively than prior alternatives, DeFoG's ss disentangled framework is the primary driver of performance gains. Importantly, the overall architecture, together with RRWP features, is guaranteed to be permuta- tion equivariant (see Appendix D.2.1).
Graph Diffusion One of the initial research directions in graph diffusion sought to adapt continuous diffusion frameworks (Sohl-Dickstein et al., 2015; Ho et al., 2020; Song et al., 2020b) for graph-structured data (Niu et al., 2020: Jo et al., 2022; 2024). Those however faced chal- lenges in preserving the inherent discreteness of graphs. In response, discrete diffusion models (Austin et al., 2021) were effectively extended to the graph domain (Vignac et al.. 2022; Haefeli et al., 2022), utilizing Discrete-Time Markov Chains to model the stochastic diffusion process. However, this method restricts sampling to the discrete time points used during training. To address this limitation, continuous-time discrete diffusion models incorporating CTMCs have emerged (Campbell et al., 2022), and have been recently applied to graph generation (Siraudin et al., 2024; Xu et al.. 2024). Despite employing a continuous- time framework, their optimization space is constrained choices like fixed-rate matrices, by limiting further performance gains.
5.1. Graph Generation Performance
Synthetic Graph Generation We evaluate DeFoG using the widely adopted Planar, SBM (Martinkus et al., 2022), and Tree datasets (Bergmeister et al., 2023), along with the associated evaluation methodology. In Tab. 1, we report the proportion of generated graphs that are valid, unique,
"oode at github, wttp//oom/////////t//t/a mmlaaaeeemmmmmmmmmmmmmm ra reeoF....
6

---

DeFoG: Discrete Flow Matching for Graph Generation
Table I:
Graph generation performance on the synthetic datasets: Planar, Tree and SBM. We present the results from five
sampling runs, each generating 40 graphs, reported as the mean + standard deviation. Full version Tab. 7.
Planar
Tree
SBM
Model
Class
V.U.N.1 f
Ratio 4
V.U.N. f
Ratio
V.U.N. f
Ratio
Train
100
1.0
100
1.0
85.9
1.0
GrahRRNN (You et
Autoregressive
490.2
607.0
GRAN (Liao et al., 2019)
Autoregressive
0.0
2.0
0.0
607.0
25.0
9.7
SPECTRE (Martinkus
2022)
GAN
25.0
3.0
52.5
2.2
DiGress (Vignac al., 2022)
Diffusion
77.5
5.1
90.0
1.6
60.0
1.7
EDGE (Chen al., 2023)
Diffusion
0.0
431.4
0.0
850.7
0.0
51.4
BwR (EDP-GNN) (Diamant et al., 2023)
Diffusion
0.0
251.9
0.0
11.4
7.5
38.6
BiGG (Dai et al., 2020)
Autoregressive
5.0
16.0
75.0
5.2
10.0
11.9
GraphGen (Goyal al., 2020)
Autoregressive
7.5
210.3
95.0
33.2
5.0
48.8
HSpectre (Bergmeister al., 2023)
Diffusion
25.0
2.1
100.0
4.0
75.0
10.5
GruM (Jo et al., 2024)
Diffusion
90.0
1.8
85.0
1.1
CatFlow (Eijkelboom et al., 2024)
Flow
80.0
85.0
DisCo (Xu et al., 2024)
Diffusion
83.612.1
66.2s14
Cometh (Siraudin et ul., 2024)
Diffusion
99.5an.
75.0
DeFoG (5% steps)
Flow
95.0a12
3.2a11
73.5
2.5e1
86.5
2,2
DeFoG
Flow
99.511.0
1.6:04
96.5.2.
1.6:0.4
90.0.5.1
4.9.13
Table 2: Large molecule generation performance. Only iterative denoising-basee based methods are reported here. Respective full versions in Tab. 10 (Guacamol) and Tab. (MOSES), Appendix G.3.
Guacamol
MOSES
Model
Val.
V.U.
V.U.N.t
KL div f
FCD f
Val.
Unique.
Novelty
Filters t
FCD
SNN >
Scaf f
Training set
100.0
100.0
0.0
99.9
92.8
100.0
100.0
0.0
100.0
0.01
0.64
99.1
DiGress (Vignac 2022)
85.2
85.2
85.1
92.9
68.0
85.7
100.0
95.0
97.1
1.19
0.52
14.8
DisCo (Xu 2024)
86.6
86.6
86.5
92.6
59.7
88.3
100.0
97.7
95.6
1.44
0.50
15.1
Cometh (Siruudin 2024)
98.9
98.9
97.6
96.7
72.7
90.5
99.9
92.6
99.1
1.27
0.54
16.0
DeFoCi (10% steps)
91.7
96.9
96.5
1.87
23.5
DeFoG
99.0
99.0
97.9
97.7
73.8
92.8
99.9
92.1
98.9
1.95
0.55
14.4
and novel (V.U.N.), as well as the average ratio of the usual distances between graph statistics of the generated and test sets relative to the train and test sets (Ratio) to assess sample quality. As shown in Tab. 1, for the Planar dataset, DeFoG achieves the best performance across both metries, with a nearly saturated V.U.N. value of 99.5%. On the Tree dataset, it is only surpassed by HSpectre, which leverages local expansion procedure particularly well-suited to hierarchical structures like trees. On the SBM dataset, DeFoG achieves the highest V.U.N. score among all methods, even with just 50 steps.
spectively, with results in Tabs. 9 and 10. As illustrated in Tab. 2, on Guacamol, it ranks best across all metries, achieving a nearly saturated validity of 99.0%. Notably, DeFoG achieves over 90% validity with just 10% of the sampling steps, surpassing the well-established baseline DiGress with 500 steps. On MOSES, DeFoG also outper- forms diffusion models, achieving SOTA validity of 92.8% while maintaining high uniqueness of 99.9%.
5.2. Efficiency Improvement
We show that DeFoG enhances both training and sam- pling efficiency significantly across diverse datasets.
Molecular Graph Generation Molecular design is
Sampling Efficiency Figure 2a highlights the cumula- tive benefits of sampling approaches from Sec. 3.2. Start- ing with a vanilla DeFoG model (initially slightly below DiGress), each optimization step, denoted by + symbols, progressively improves performance, culminating in signif- icant gains using only 50 steps the Planar dataset. This demonstrates that the three sampling approaches are each essential components for optimizing generation.
prominent real-world application of graph generation. We evaluate DeFoG's performance on this task using the QM9 (Wu et al., 2018), ZINC250K (Sterling & Irwin, 2015). MOSES (Polykovskiy et al., 2020), and Guacamol (Brown al., 2019) datasets. For QM9, we follow the dataset split and evaluation metrics from Vignac et al. (2022), present- ing the results in Appendix F.2.2, Tab. 8. For ZINC250K, we provide the experimental setup in Appendix F. For the larger MOSES and Guacamol datasets, we adhere to the training setup and evaluation metrics established by Polykovskiy et al. (2020) and Brown et al. (2019), re-
Training Efficiency Figure 2b illustrates convergence curves for the tree and MOSES datasets. We observe that incorporating sampling distortion enhances performance
7

---

significantly beyond the vanilla implementation, making it particularly useful for generation with undertrained mod- els in resource-constrained settings (see Appendix B.6). Additionally, applying the same optimal distortion found in sampling during training typically yields further gains in convergence (see Appendix C.2). The convergence DeFoG: Discrete Flow Matching for Graph Generation
Valiity (Q200)
100
V.U.N.
Tagged Geltaaon
15 88
VIN
Saa Nisturtice
Vouills
20 03
10
Strpp
1000
1o
Staps
Pulster
Mesilly
Pubtiee
Hestity
Oi
(a) Sampling efficiency improvement.
Sample Distoction (1000 steps)
Sample Distortion (50 scepe)
(a) Sample Distortion.
Valsitt (MOSEES)
V.U.N. (22ce)
0.4
V.U.N.
Parto
Thiin Tistoriio Snappe Datoeika
0.4
Varilla D151
DXGre
100
Training Eie (6)
10 Thiiing time (h)
20
015
100
(b) Training efficiency improvement.
0.3 00-000000005-1 6a 63 du as
DO O 010 022005 0.1 es ea 64 0.5 Targot Guiduner (50 strps)
Target Guidaane & (1000 stepe)
Figure 2: DeFoG's improvements on efficiency.
(b) Target guidance.
V.U.N.
Rotto
0.0
0388
100
0005
030
0000
0.0 5b Boa 150 sie cadn asi
00
5.0
10.0
25.0
M0a noto 2010
Stochasticity 1 (1000 steps)
Stochasticity y stepe)
(c) Stochasticity.
some graph datasets may also benefit from an appropriate initial distribution, as shown for SBM in Appendix C.I.
Figure 3: Effect of proposed sampling approaches on the Planar dataset. Higher values on the vertical axis corre- spond to more favorable values for both V.U.N. and Ratio.
5.3. Ablations
Here, we focus on evaluating the impact of different sam- pling approaches. We start from the vanilla sampling setup and sweep over sample distortion, target guidance, or stochasticity independently. More details in Appendix B.4. For illustration, here we focus on the Planar dataset:
tion process becomes more challenging due to larger tran- sitions, as steers the model toward higher-confidence re- gions, safeguarding generative performance.
Stochasticity As shown in Figure 3c, a moderate level of stochasticity benefits both metrics, while extreme values introduce excessive noise, disrupting the generation pro- cess. This indicates sweet spot exists between effective error correction and over-stochasticcity Furthermore, the V.U.N. of generated graphs decreases with increasing 7) val- ues when more steps are utilized (drop after v = 100 for 1000 steps vs. 7) = 10 for 50 steps). As this approach preserves the Kolmogorov equation, it benefits from more sampling steps to mitigate simulation errors.
Sample Distortion In Figure 3a, we observe that cos and polydec distortions which emphasize refinement at later steps, perform better on the Planar dataset. This aligns with the intuition that, unlike continuous data undergoing gradual refinement, graphs often experience abrupt transi- tions due to the random sampling of categorical data. These transitions can violate hard constraints, such as planarity, as categorical values shift abruptly (e.g., from 0 to 1 in one- hot encoding) when t approaches 1. These later steps are thus critical for error detection and correction. On the con- trary, for datasets like SBM, where properties are not deter- ministic and such strict constraints are absent, this refine- ment does not provide any advantage (see Appendix B.
6. Conclusion
We introduce DeFoG, a novel discrete flow matching framework for graphs. This formulation enables training- sampling decoupling, which we ground theoretically to en- sure faithful graph distribution modeling. Extensive ex- periments demonstrate the importance of our proposed strategies in achieving state-of-the-ar performance syn- thetic and molecular graph generation tasks. DeFoG cur- rently employs a simple but efficient hyperparameter search for sampling, yielding impressive results and underscoring its potential for further improvement with more advanced search algorithms. Future work will further explore purely
Target Guidance As shown in Figure 3b, w improves both V.U.N. and Ratio by biasing generation toward pre- dicted clean data. However, excessive ws skews the gen- erated distribution ing set distribution, leading higher planarity (reflected by V.U.N.) but increased divergence from test graphs (re- flected by Ratio). We also observe that the Ratio only begins to worsen at 0.1 with 50 steps, compared to 0.02 with 1000 steps. This demonstrates that target guidance is particularly effective with fewer steps, where the genera-
the high density regions of train-
8

---

DeFoG: Discrete Flow Matching for Graph Generation
sampling-stage methods enhance performance. Generat- ing high-quality graphs in even fewer steps and sealing to larger graphs also remain key challenges.
Cao. Y., Chen, J., Luo, Y., and Zhou, X. Exploring the optimal choice for generative processes in diffusion models: Ordinary vs stochastic differential equations. In Advances in Neural Information Processing Systems (NewrIPS), 2023.
Acknowledgements
Chen, X., He, J., Han, X., and Liu, L.-P. Efficient and degree-guided graph generation via discrete diffusion modeling. In International Conference on Machine Learning (ICML), 2023.
We would like to thank Clément Vignac and Andrew Campbell for the useful discussions and suggestions.
Impact Statement
Chung, H., Sim, B., and Ye, C. Come-closerdifffse- faster: Accelerating conditional diffusion models for in- verse problems through stochastic contraction. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
The primary objective of this paper is to advance graph generation under a more flexible framework, with appli- cations spanning general graph generation, molecular de- sign, and digital pathology. The ability to generate graphs with discrete labels can have broad-reaching implications for fields such drug discovery and diagnostic technolo- gies. While this development has the potential to bring about both positive and negative societal or ethical impacts, particularly in areas like biomedical and chemical research, we currently do not foresee any immediate socictal con- cerns associated with the proposed methodology.
Dai, H., Nazi, A., Li. Y., Dai, B., and Schuurmans, D. Scalable deep generative modeling for sparse graphs. In International Conference on Machine Learning (ICML), 2020.
De Cao, N. and Kipf, T. Molgan: An implicit generative model for small molecular graphs. In International Con- ference on Machine Learning (ICML) Workshops, 2018.
References
Diamant, N. L., Tseng, A. M., Chuang, K. V., Biancalani, T., and Scalia, G. Improving graph generation by re- stricting graph bandwidth. In International Conference on Machine Learning (ICML), 2023.
Asthana, R., Conrad, J., Dawoud, Y., Ortmanns, M., and Belagiannis, V. cunti-conditioned graph diffusion for neural architecture search. In Transactions Machine Learning Research (TMLR), 2024.
Dockhorn, T., Vahdat, A., and Kreis, K. Score-based gen- erative modeling with critically-dampel langevin diffu- sion. In International Conference on Learning Repre- sentations (ICLR), 2022.
Austin, J., Johnson, D. D., Ho, J., Tarlow, D., and Van Den Berg, R. Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems (NeurIPS). 2021.
Eijkelboom, F., Bartosh, G., Andersson Naesseth, C., Welling, M., and van de Meent, J.-W. Variational flow matching for graph generation. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Bergmeister, A., Martinkus, K., Perraudin, N., and Watten- hofer, R. Efficient and scalable graph generation through iterative local expansion. In International Conference on Learning Representations (ICLR), 2023.
Esser, P., Kulal, S., Blattmann, A., Entezari, R., Müller, J., Saini, H., Levi, Y., Lorenz, D., Sauer, A., Boesel, F., et al. Scaling rectified flow transformers for high- resolution image synthesis. In International Conference Machine Learning (ICML), 2024.
Brown, N., Fiscato, M., Segler, M. H., and Vaucher, A. C. Guacamol: benchmarking models for de novo molecular design. In Journal of Chemical Information and Model- ing. 2019.
Gat, I., Remez, T., Shaul, N., Kreuk, F., Chen, R. T., Syn- nacve, G., Adi, Y., and Lipman, Y. Discrete flow match- ing. In Advances in Neural Information Processing Sys- tems (NeurIPS), 2024.
Campbell, A., Benton, J., De Bortoli, V., Rainforth, T., Deligiannidis, G., and Doucet, A. A continuous time framework for discrete denoising models. In Advances in Neural Information Processing Systems (NeurIPS). 2022.
Gillespie, D. T. A general method for numerically simu- lating the stochastic time evolution of coupled chemical reactions. In Journal of Computational Physics, 1976.
Campbell, A., Yim, J., Barzilay, R., Rainforth, T., and Jaakkola, T. Generative flows on discrete state-spaces: Enabling multimodal flows with applications to protein co-design. In International Conference on Machine Learning (ICML), 2024.
Gillespie, D. T. Exact stochastic simulation of coupled chemical reactions. In The Journal of Physical Chem istry, 1977.

---

DeFoG: Discrete Flow Matching for Graph Generation
Gillespie, D. T. Approximate accelerated stochastic simu- lation of chemically reacting systems. In The Journal of Chemical Physics, 2001.
Jolicoeu--Marineau, A., Li, K., Piché-Taillefer, R., Kach- man, T., and Mitliagkas, I, Gotta go fast when generating data with score-based models. In ArXiv, 2021.
Goyal, N., Jain, H. V., and Ranu, S. Graphgen: A scalable approach to domain-agnostte labeled graph generation. In The Web Conference, 2020.
Karras, T., Aittala, M., Aila, T., and Laine, S. Elucidating the design space of diffusion-based generative models. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Haefeli, K. K., Martinkus, K., Perraudin, N., and Watten- hofer, R. Diffusion models for graphs benefit from dis- crete state spaces. In Learning on Graphs Conference (LOG) Extended Abstracts, 2022.
Kingma, D. P. and Welling, M. Auto-encoding variational bayes. In ArXiv, 2013.
Kipf, T. N. and Welling, M. Variational graph auto- encoders. In ArXiv, 2016.
Han, X., Chen, X., Ruiz, F. J., and Liu, L.-P. Fitting au- toregressive graph generative models through maximum likelihood estimation. In Journal of Machine Learning Research (JMLR), 2023.
Kong. L.., Cui, J., Sun, H., Zhuang, Y., Prakash, B. A., and Zhang. C. Autoregressive diffusion model for graph gen- eration. In International Conference on Machine Learn- ing (ICML), 2023.
Ho, J. and Salimans, T. Classifier-free diffusion guidance. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Kuratowski, C.
Sur le probleme des courbes gauches en topologie. Fundamenta Mathematicae, 1930.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. In Advances in Neural Information Pro- cexsing Systems (NeurIPS), 2020.
Kwon, Y., Lee, D., Choi, Y.S.., Shin, K., and Kang, S. Compressed graph representation for scalable molecular graph generation. In Journal of Cheminformatiic, 2020.
Hochreiter, S. and Schmidhuber, J. Long short-term mem- ory. In Neural computation, 1997.
Liao, R., Li, Y., Song, Y., Wang. S., Hamilton, W., Du- venaud, D. K., Urtasun, R., and Zemel, R. Efficient graph generation with graph recurrent attention net- works. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Igashov, I. Schneuing, A., Segler, M., Bronstein, M. M., and Correia, B. Retrobridge: Modeling retrosynthesis with markov bridges. In International Conference on Learning Representations (ICLR), 2024.
Lipman, Y., Chen, R. T., Ben-Hamu, H., Nickel, M., and Le, M. Flow matching for generative modeling. In International Conference on Learning Representations (ICLR), 2023.
Irwin, R., Tibo, A., Janet, J. P., and Olsson, S. Efficient 3d molecular generation with flow matching and scale opti- mal transport. In International Conference on Machine Learning (ICML) Workshops, 2024.
Liu, J., Kumar, A., Ba, J., Kiros, J., and Swersky, K. Graph normalizing flows. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Jaume, G., Pati, P., Bozorgtabar, B., Foncubierta- Rodríguez, A., Feroce, F., Anniciello, A. M., Rau, T., Thiran, J.-P., Gabrani, M., and Goksel, O. Quantify- ing explainers of graph neural networks in computational pathology. In IEEE/CVF Conference on Computer Vi- sion and Pattern Recognition (CVPR), 2020.
Liu, Q. Allamanis, M., Brockschmidt, M., and Gaunt, A. Constrained graph variational autoencoders for molecule design. Advances Neural Information Processing Systems (NeurIPS), 2018
Jin, W., Barzilay, R., and Jaakkola, T. Junction tree vari- ational autoencoder for molecular graph generation. In International Conference on Machine Learning (ICML), 2018.
Liu, X., Gong, C., and Liu, Q. Flow straight and fast: Learning to generate and transfer data with rectified flow. In International Conference on Learning Representa- tions (ICLR), 2023.
Jo, J., Lee. S., and Hwang, S. J. Score-based generative modeling of graphs via the system stochastic differen- tial equations. In International Conference on Machine Learning (ICML), 2022.
Liu, X., He, Y., Chen, B., and Zhou, M. Advancing graph generation through beta diffusion. In International Con- ference on Learning Representations (ICLR), 2024.
Jo, J., Kim, D., and Hwang. S. J. Graph generation with diffiusion mixture. In International Conference on Ma- chine Learning (ICMI), 2024.
Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N Graph induc- tive biases in transformers without message passing. In
10

---

DeFoG: Discrete Flow Matching for Graph Generation
International Conference on Machine Learning (ICML), 2023.
Pati, P., Jaume, G., Foncubierta-Rodtiiuezz A., Feroce, E., Anniciello, A. M., Scognamiglio, G., Brancati, N., Fiche, M., Dubruc, E., Riccio, D., et al. Hierarchical graph representations in digital pathology. In Medical Image Analysis, 2022.
Ma, N., Goldstein, M., Albergo, M. S., Boffi, N. M., Vanden-Eijnden E., and Xie, S. Sit: Exploring flow and diffusion-based generative models with scalable inter- polant transformers. In European Conference on Com- puler Vision (ECCV), 2024.
Polykovskiy, D., Zhebrak, A., Sanchez-Lengeling, B., Golovanov, S., Tatanov, O., Belyaev, S., Kurbanov, R., Artamonov, A., Aladinskiy, V., Veselov, M., et al. Molecular sets (moses): benchmarking platform for molecular generation models. In Frontiers in Pharma- cology, 2020.
Madeira, M., Thanou, D., and Frossard. P. Tertiary lym- phoid structures generation through graph-based diffu- sion. In International Conference on Medical Image Computing and Conputer-Assisted Intervention (MIC- CAI) Workshops, 2023.
Qin, Y., Vignac, C., and Frossard, P. Sparse training of discrete diffusion models for graph generation. In ArXiv, 2023.
Madeira, M., Vignac, C., Thanou, D., and Frossard, P. Generative modelling of structurally constrained graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Ruddigkeit, L., Van Deursen, R., Blum, L. C., and Rey- mond, J.-L. Enumeration of 166 billion organic small molecules in the chemical universe database gdb- 17. In Journal of Chemical Information and Modeling, 2012.
Madhawa, K., Ishiguro, K., Nakago, K., and Abe, M. Graphnvp: An invertible flow model for generating molecular graphs. In ArXiv, 2019.
Salimans, T. and Ho, J. Progressive distillation for fast sam- pling of diffusion models. In International Conference on Learning Representations (ICLR), 2022.
Martinkus, K., Loukas, A., Perraudin, N., and Wattenhofer, R. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In In- ternational Conference on Machine Learning (ICML), 2022.
Sanchez, G., Spangher, A., Fan, H., Levi, E., and Bider- man, S. Stay on topic with classifier-free guidance. In International Conference on Machine Learning (ICML), 2024.
Shaul, N., Gat, I., Havasi, M., Severo, D., Sriram, A., Hold- errieth, P., Karrer, B., Lipman, Y., and Chen, R. T. Flow matching with general discrete paths: A kinetic-optimal perspective. In International Conference on Learning Representations (ICLR), 2025.
Mendez, D., Gaulton, A., Bento, A. P., Chambers, J., De Veij, M., Félix, E., Magariños, M. P., Mosquera, J. F., Mutowo, P., Nowotka, M., et al. Chembl: towards direct deposition of bioassay data. In Nucleic Acids Research, 2019.
Siraudin, A., Malliaros, F. D., and Morris, C. Cometh: A continuous-time discrete-state graph diffusion model. In ArXiv, 2024.
Mercado, R., Rastemo, T., Lindelöf, E., Klambauer, G.,
Engkvist, O., Chen, H., and Bjerrum, E. J. Graph net- works for molecular design. In Machine Learning: Sci- ence and Technology, 2021.
Sohl-Dickstein. J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International Conference on Machine Learning (ICML), 2015.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence, 2019.
Song. J., Meng, C., and Ermon, S. Denoising diffusson im- plicit models. In International Conference on Learning Representations (ICLR), 2020a.
Nisonoff, H., Xiong, J., Allenspach, S., and Listgarten, J. Unlocking guidance for discrete state-space diffusion and flow models. In International Conference on Learn- ing Representations (ICLR), 2025.
Song, Y., Sohl-Dickster J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. Score-based generative model- ing through stochastic differential equations. In Interna- tional Conference on Learning Representations (ICLR), 2020b.
Niu, C., Song, Y., Song, J., Zhao, S., Grover, A., and Ermon, S. Permutation invariant graph generation via basee generative modeling. In International Con- ference on Artificial Intelligence and Statistics (AIS- TATS), 2020.
Sterling, T. and Irwin, J. J. Zinc 15 15-ligand discovery for everyone. In Journal of Chemical Information and Mod- eling, 2015.

---

DeFoG: Discrete Flow Matching for Graph Generation
Sun, H., Yu, L., Dai, B., Schuurmans, D., and Dai, H. Score-based continuous-time discrete diffusion models. In International Conference Learning Representa- tions (ICLR), 2023.
You, Ying, R., Ren, X., Hamilton, W., and Leskovee, J. Graphrnn: Generating realistic graphs with deep auto- regressive models. In International Conference Ma- chine Learning (ICML), 2018.
Sun, 7. and Yang, Y. Difusco: Graph-based diffusion solvers for combinatorial optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Zhang, Q. and Chen, Y. Fast sampling of diffusion models with exponential integrator. In International Conference Learning Representations (ICLR), 2023.
Zhu, W., Wen, T., Song, G., Wang, L.,, and Zheng, B. On structural expressive power of graph transformers. In ACM SIGKDD Conference Knowledge Discovery and Data Mining (KDD), 2023.
Tseng, A. M., Diamant, N., Biancalani, T., and Scalia, G. Complex preferences for different convergent priors discrete graph diffusion. In International Conference on Machine Learning (ICML) Workshops, 2023.
Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, P. Digress: Discrete denoising diffu- sion for graph generation. In International Conference on Machine Learning (ICML), 2022.
Vignac, C., Osman, N., Toni, L., and Frossard, P. Midi: Mixed graph and 3d denoising diffusion for molecule generation. In Joint European Conference on Ma- chine Learning and Knowledge Discovery in Databases (ECML/PKDD), 2023.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: benchmark for molecular machine learn- ing. In Chemical Science, 2018.
Wu, 7., Trevino, A. E., Wu, E.,, Swanson, K., Kim, H. J., D' Angio, H. B., Preska, R., Charville, G. W., Dalerba, P. D., Egloff, A. M., et al. Graph deep learning for the characterization of tumour microenvironments from spatial protein profiles tissue specimens. In Nature Biomedical Engineering, 2022.
Xu, K., Hu, W., Leskovee, J., and Jegelka, How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
Xu, Y., Deng, M., Cheng, X., Tian, Y., Liu, Z., and Jaakkola, T. Restart sampling for improving generative processes. In Advances in Neural Information Process- ing Systems (NeurIPS), 2023.
Xu, 7.,, Qiu, R., Chen, Y., Chen, H., Fan, X., Pan, M., Zeng, Z.. Das, M., and Tong, H. Discrete-state continuous-time diffusion for graph generation. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Yi, K., Zhou, B., Shen, Y., Liò, P., and Wang, Y. Graph denoising diffusion for inverse protein folding. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
12

---

DeFoG: Discrete Flow Matching for Graph Generation
Appendix Overview
In the Appendix, we provide additional details organized as follows:
1. Appendix A: Contextualizing Related Research.
2. Appendix B: Sample Optimization.
3. Appendix C: Train Optimization.
4. Appendix D: Theoretical Results.
5. Appendix E: Conditional Generation.
6. Appendix F: Experimental Details.
7. Appendix G: Additional Results.
13

---

DeFoG: Discrete Flow Matching for Graph Generation
A. Contextualizing Related Research
In this section, we further contextualize DeFoG within the scope related work. We begin by introducing the methods used for comparison with DeFoG in Appendix A.I. Subsequently, we outline the key distinctions between DeFoG and existing diffusion-based graph generative models in Appendix A.2.
A.1. Overview of Compared Methods
In Sec. 5, we evaluate DeFoG against a diverse of graph generative models, which we introduce below:
GraphRNN (You et al., 2018) and GRAN (Liao et al., 2019), two pioneering autoregressive models for graph genera-
tion;
SPECTRE (Martinkus et al., 2022), spectrally conditioned GAN-based model for graph generation;
DiGress (Vignac et al.. 2022), the first discrete diffusion model for graph generation;
EDGE (Chen et al., 2023), a discrete diffusion model leveraging graph sparsity and degree guidance for scalability,
BwR (Diamant et al., 2023), which focuses on efficient graph representations via bandwidth restriction schemes that are compatible with various graph generation models. We report its results in combination with EDP-GNN (Niu al., 2020), which was the first graph diffusion model;
BiGG (Dai et al., 2020), autoregressive model that exploits graph sparsity and training parallelization to scale to larger graphs;
GraphGen (Goyal et al., 2020), a scalable autoregressive approach utilizing graph canonization with minimum DFS codes, notable for being domain-agnostic and inherently supporting attributed graphs;
HSpectre (Bergmeister et al., 2023), a hierarchical graph generation method that utilizes a score-based formulation for iterative local expansion steps;
DisCo (Xu et al., 2024) and Cometh (Siraudin al., 2024), two continuous-time discrete diffusion models for graph generation;
GruM (Io et al., 2024), which employs diffusion mixture to explicitly learn the final graph topology and structure;
CatFlow (Eijkelboom et al., 2024), which results from the instantiation of variational flow matching to graph genera- tion.
A.2. DeFoG and Graph Diffusion Models
In this section, we contextualize DeFoG in relation to existing graph diffusion models.
1. FROM CONTINUOUS TO DISCRETE STATE-SPACES
Early diffusion- bassed graph generative models extended continuous diffusion and score-based methods from image gener- ation to graphs by relaxing adjacency matrices into continuous state-spaces (Niu et al., 2020; Jo et al., 2022). However, this approach overlooks the inherent discreteness of graph-structured data, resulting in topologically uninformed noising pro- cesses. For instance, these methods often destroy graph sparsity and generate noisy complete graphs (Vignac al., 2022; Xu et al., 2024; Siraudin et al., 2024), making it more challenging for denoising neural networks to recover meaningful structural properties from the noisy inputs. Some recent formulations operating on continuous spte-spaces have tried to overcome these limitations: GruM (Jo et al., 2024) introduces an endpoint-condittoned diffusion mixture strategy to en- hance accuracy by explicitly learning final graph structures, while CatFlow (Eijkelboom et al., 2024) proposes variational flow matching to handle categorical data more effectively.
Alternatively, discrete diffusion models have emerged as more natural solution, directly preserving the discrete nature of graph data (Vignac et al., 2022; Haefeli et al., 2022). These models have demonstrated -fate-ofthhe-ee the-art performance across variety of applications, including neural architecture search (Asthana et al., 2024), combinatorial optimization (Sun & Yang, 2024), molecular generation (Irwin et al., 2024), and reaction pathway design (Igashov et al., 2024).
DeFoG aligns with this second family of methods, modeling nodes and edges in discrete state-spaces to leverage the structural properties of graph data effectively.
14

---

DeFoG: Discrete Flow Matching for Graph Generation
A.2.2. FROM DISCRETE TO CONTINUOUS TIME
The initial discrete-time diffusion frameworks for graph generation (Vignac et al., 2022: Haefeli et al., 2022) were built upon Discrete Denoising Diffusion Probabilistic Models (D3PMs) (Austin et al., 2021), which operate with fixed parti- tioning of time. This discretization constrains the model to denoise at specific time points and ties the sampling process to the same fixed time steps used during training, leading to rigid coupling between the training and sampling stages. Such inflexibility in time discretization can limit the quality of generated graphs.
In contrast, continuous- discrete diffusion frameworks (Campbell et al., 2022; Sun et al., 2023) overcome these lim- itations by enabling the model to denoise at arbitrary time points within a continuous interval (typically between 0 and 1). This flexibility allows the time discretization strategy for sampling to be selected post-training, enabling the use of ad- vanced sampling techniques (Jolicoeur-aartinee 2022; Song et al., 2020b; Dockhorn et al., 2022) to improve generation performance. These continuous-time frameworks have been successfully extended to graph generative models (Xu et al., 2024; Siraudin et al., 2024), achieving notable improvements.
et al., 2021; Zhang & Chen, 2023; Salimans & Ho, 2022; Chung al.,
DeFoG follows a continuous-time formulation, leveraging its flexibility in sampling to achieve enhanced performance while maintaining the strengths of discrete state-space modeling.
A.2.3. FROM CONTINUOUS-TIMAA TIME DISCRETE DIFFUSION TO DISCRETE FLOW MATCHING
While both continuous-tim time discrete diffusion and discrete flow matching (DFM) share the CTMC formulation for the denoising process, they differ fundamentally in the formulation of the noising process. Continuous-ting discrete diffusion- based graph generative models (Xu et al., 2024; Siraudin et al., 2024) define the noising process as a CTMC, akin to the denoising process. However, this approach imposes two significant limitations:
1. Incomplete Coupling of Training and Sampling: The rate matrices of the noising and denoising processes are explicitly interrelated, and the noising rate matrix must be fixed during training. This restricts the sampling stage, preventing full decoupling of training and sampling.
2. Limited Design Space: The noising process must be derived analytically, which is not straightforward and is only feasible for rate matrices suitable for matrix exponentiation. Additionally, the denoising rate matrix is implicitly defined during training, constraining the flexibility of the denoising trajectory at sampling time (e.g., fixing the level of stochasticity).
In contrast, DeFoG allows for direct prescription of the noising process, Pej1- without these constraints. The rate matrix for the denoising process is selected exclusively at sampling time, fully decoupling the training and sampling stages. This flexibility enables performance optimization during sampling, such as tuning the stochasticity of the denoising trajectory via RPB or adjusting target guidance magnitude with Ryy
The benefits of this decoupled framework are evident Figures 2, 7 and 8, which demonstrate that the vanilla DeFoG con- figuration alone does not outperform existing diffusion- based graph generative models. However, our extensive sampling optimization pipeline capitalizes on DeFoG's flexible design space achieve state-of-the-arr results. These observations align with findings in iterative refinement methods across other data modalities. For instance, Karras et al. (2022) elaborate on the benefits of stochasticity adjustment in denoising trajectories within diffusion models for image generation.
For comprehensive discussion of the differences between continuous-time discrete diffusion and DFM frameworks, see Appendix H of Campbell et al. (2024).
A.2.4. MIXED INTEGRATION OF CONTINUOUS AND DISCRETE STATE-SPACES
Integrating continuous and categorical data within graph generative models an important challenge. as many real-world applications involve heterogeneous data types (e.g., molecular graphs containing atomic coordinates alongside categorical atom and bond types). A recent example addressing this challenge is GBD (Liu et al., 2024), which incorporates beta diffusion to jointly model both continuous and discrete variables. Similarly, DeFoG is amenable to formulations involving mixed data types by leveraging an approach akin to MiDi (Vignac et al., 2023), independently factorizing continuous and discrete variables. However, explicitly exploring this integration is beyond the scope of this work.
15

---

DeFoG: Discrete Flow Matching for Graph Generation
B. Sample Optimization
In this section, we explore the proposed sampling optimization more detail. We start by analysing the different time distortion functions in Appendix B.1. Next, in Appendix B.2, we prove that the proposed target guidance mechanism actually satisfies the Kolmogorov equation, thus yielding valid rate matrices and, in Appendix B.3, we provide more details about the detailed balance equation and how it widens the design space of rate matrices. In Appendix B.4, also describe the adopted sampling optimization pipeline. Finally, in Appendix B.5, we provide more details to better clarify the dynamics of the sampling process.
B.1. Time Distortion Functions
In Sec. 3, we explore the utilization of different distortion functions, i.e., functions that are used to transform time. The key motivation for employing such functions arises from prior work on flow matching in image generation, where skewing the time distribution during training has been shown to significantly enhance empirical performance (Esser et al., 2024). In practical terms, this implies that the model is more frequently exposed to specific time intervals. Mathematically, this transformation corresponds to introducing time-dependent re-weighting factor in the loss function, biasing the model to achieve better performance in particular time ranges.
In our case, we apply time distortions the probability density function (PDF) by introducing function that transforms the original uniformly sampled time I, such that L' = f(() for / E [0, 1]. These time distortion functions must satisfy certain conditions: they must be monotonic, with f() = 0 and f(1) = 1. Although the space of functions that satisfy these criteria is infinite, we focus on five distinct functions that yield fundamentally different profiles for the PDF of t'. Our goal is to gain intuition about which time ranges are most critical for graph generation and not to explore that function space exhaustively. Specifically:
Polyine: f(t) = t?, yielding PDF that decreases monotonically with t';
Cos: f(t) 1-cos creating PDF with high density near the boundaries t' Onnd t' 1, and low for intermediate t';
Identity: f(() = 1, resulting in a uniform PDF for i' E 10;
Revcos: f(f) 2t 1-cos and 1' 1;
leading to high PDF density for intermediate t' and low density at the extremes
2
Polydec: f(t) = 2t t?, where the PDF increases monotonically with t'.
The PDF resulting from applying a monotonic function f to random variable t is given by:
dt (
6i (t) = (x(())
where (t) and de (t') denote the PDFs of and t', respectively. In our case, de(() for t E [0, 11. The distortion functions and their corresponding PDFs are illustrated in Figure 4.
One of the strategies the proposed in sampling optimization procedure is the use of variable step sizes throughout the denoising process. This is achieved by mapping evenly spaced time points (DeFoG's vanilla version) through a transfor- mation that follows the same constraints as the training time distortions discussed earlier. We employ the same set of time distortion functions, again not to exhaustively explore the space of applicable functions, but to gain insight into how vary- ing step sizes affect graph generation. The expected step sizes for each distortion be directly inferred from Figure 4. For instance, the polydec function leads to progressively smaller time steps, suggesting more refined graph edits in the denoising process as l' approaches 1.
Note that even though we apply the same time distortions for both training and sample stages, in each setting they have different roles: in training, the time distortions skew the PDFs from where t' is sampled, while in sampling they vary the denoising step sizes.
16

---

DeFoG: Discrete Flow Matching for Graph Generation
Distorlions
PDFs for Different Distortions
1.0
5
Polyine
Polyine
0.8
Cos
Punction vallie
Identity
Identity
0.6
Reveos
PDFs
3-
Revops
0.4
Polydec
2-
Polydec
0.2
1
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
f(1
(a)
(b)
Figure 4: (a) The five distortion functions explored. (b) The resulting PDFs for the five distortion functions. For polydec, identity, and polyine, they were computed in closed-form. For revcos and cos, they were simulated with 10* repetitions.
B.2. Target Guidance
In this section, we demonstrate that the proposed largel guidance design for the rate matrices violates the Kolmogorov equation with an error that is linear w. This result indicates that small guidance factor effectively helps fit the distri- bution, whereas larger guidance factor, shown in Figure 9, while enhancing topological properties such as planarity, increases the distance between generated and training data synthetic datasets according the metries of average ratio. Similarly, for molecular datasets, this also leads to an increase in validity and decrease in novelty by forcing the generated data to closely resemble the training data.
Lemma 10 (Rate matrices for target guidance). Let R (ze, 214d(l21) be defined as:
8(21, 204d1)
By (Zt, 2140(/21) = w 27 Prp1 (011(2z11 (1)
Then, the univariate rate matrix ( zetall21) R2 (2x, Z44 (1) + Ry (ze, z44ael21) violates the Kolmogorov equa- tion with an error of 7,00
2,201
w when 2 # 21, and an error of w 2,20
when = Z1.
Proof. In the remaining of the proof, we consider the case 2 # 21. We consider the same assumptions Campbell al. (2024):
(1)(2)))1) + (ze, 2z1dr(21)
(1)(z)221)= + 0 ("dead states cannot ressurect").
The 21-conditioned Kolmogorov equation is given by:
(zPe1()) = Σ
Re 22/21) (ta (z)+aa)z1)
Σ
Relas,
(8)
We denote by RHS and LHS the right-hand side and left-han hand side, respectively, of Eq. (8). For the case in which Pe1(21/21) > we have:
17

---

DeFoG: Discrete Flow Matching for Graph Generation
RHS
Σ
(Z + Ry (e =x(21) =2)
ac paatza Peede (F
Σ
(zael1)) + Ry (Ze, Fetai 21 (1)
Σ
R (2c+des 24 21 Pr (2t+di (21) - R2 (2t, 4 21 )p11 (2el21)
Reade se (2044t1)2)))
Σ
(2 24 21 Pe+at (26+del21). RG (2t, 24 21 Pr (21121),
For the first sum, we have:
Σ
(E Pear)) (Z+tal/21))))) R2 (et, #etal (teae//))prn(ztt
Peppp (=)l2))))
since the zj-conditioned R2 generates Pt[1-
For the second sum, we have:
Σ
Re (ze4ats ( (Estaelz1) R2 set (1 (z112)))
Rt4-de of Pe (Se4dela1)3
8(21, ze)
Σ
Peoaup
Z 0
Petde/1 (Z++del21)
ai of Pe (Re (al3)))0
8(21, 21ddr)
Σ
Ptjp (2ol21)
2,25 Pid (24 21
Re4ae Pea (eseallt
Σ
(8(21, 2))
Z 20
#1 (814
If 21 24, we have:
Σ
(2 (a - (2 Ze Pap (Z)l
#t Pe (#c4aelz))00
Σ
(8(21, xx) - 8(21, ze+ar))
2
Σ
8(21, Z44a()
Z,2
Here, we apply the property that 2, * ø1, which indicates that 8(21, 0 and that there exists one and only one 244d (214dt, dt # =e) such that 244d 21, which verifies that Pe+d (2 > 0 condition satisfied by any initial distribution proposed in this work when t strictly positive- the sum simplifies to 2.50
w
If 21 2t, we have:
18

---

DeFoG: Discrete Flow Matching for Graph Generation
( Pett (Z+tael2)) (1 Ry (2e, Re+ (2)
(=)20
Σ
(6(21, 24) 2(4e))
Σ
(1- 0)
Z
F1ta1 Pr.paat (
2700 11
w Z
Intuition The aim of target guidance is reinforce the transition rate to the state predicted by the probabilissti model, 21- The w term is an hyperparameter used to control the target guidance magnitude.
B.3. Detailed Balance, Prior Incorporation, and Stochasticity
Campbell et al. (2024) show that although their 21 21-conditional formulation of R generates Pet1. it does not span the full space of valid rate matrices those that satisfy the conditional Kolmogorov equation (Eq. (8)). They derive sufficient conditions for identifying other valid rate matrices. Notably, they demonstrate that matrices of the form
: + R
with 7 E R22 and RB any matrix that verifies the detailed balance condition:
(z) (2e, 20-0l (1) Pej1 (B44d//21) R (ze+de, 21(21)
The detailed balance condition ensures that the outflow, Paja (2e/21 ( RR 2()d:/21,, and inflow, Pan (#++arl 21) RP (2ztde, of probability mass any given state perfectly balanced. Under these conditions, this additive component's contribution to the Kolmogorov equation becomes null (similar to the target guidance, as shown in the proof of of Theorem 10, in Appendix B.2).
still satisfy the Kolmogorov equation.
A natural question is how to choose a suitable design for Re from the infinite space of detailed balance rate matrices. As depicted in Figure 5, this flexibility can be leveraged to incorporate priors into the denoising model by encouraging specific transitions between states. By adjusting the sparsity of the matrix entries, additional transitions beyond those prescribed by Rł can be introduced. In the general case, transitions between all states possible; in the column case, specific state centralizes all potential transitions; and in the single-entry case, only transitions between two states permitted. These examples merely illustrate some possibilities and do not exhaust the range of potential R2p8 designs. The matrix entries can be structured by considering the following reorganization of terms of Eq. (9):
DB (#e+de, 21/21) = (:11(ze(21) R. (2e, 2t- 21)2))
Paj Paj (2 (21)
Therefore, a straightforward approach is to assign the lower triangular entries of the rate matrix I2DB (#x, R+ [21) Paja (t)+))))) and the upper triangular entries as RRD (zz4at, 2 = Pep (2 (2)).)) The diagonal entries are computed last to ensure that Re(z,, z1) = -E (ztz))))dr)
We incorporated various types of priors into RDB by preserving specific rows or entries in the matrix. Specifically, we experimented with retaining the column corresponding to the state with the highest marginal distribution (Column Max Marginal), the column corresponding to the predicted states (Column .,), and the columns corresponding to the state with the highest probability in Prj1- Additionally, we tested the approach of retaining only RD i) where i is the state with the highest marginal distribution (Entry Max Marginal). For instance, under the absorbing initial distribution, this state is the one to which all data is absorbed at = 0. We note that there remains significant space for exploration by adjusting the weights assigned to different positions within RDB as the only condition that must be satisfied that
19

---

DeFoG: Discrete Flow Matching for Graph Generation
P1
P2
Pi
0
0
Po
P2
Po
P2
0
Po
P1
Pi
0
General
Column
Single entry
stochasticity
Full matrix
Preserve one column/row
Preserve two entries
All
R DH sparsity
0.7
0.1
0.7
0
0
0
-
0.2
0.1
0.2
0.1
0
0
0.2
0.7
0
0.7
0
0.7
0
0
Space of exploration
Figure 5: Examples of different rate matrices from the space of x matrices that satisfy the detailed balance condition.
Here p; denotes Pep1 (i)
R Design Planar
R Design QM9
0.75
getena
Valday
gineral
Colamn
Mix Marginal
Columa Max Marginal
Column 21
Colurza 3
Column
Column
Entry Max Margunal
Entry Marginal
4.00
Noodre
Rute
2.00
0.76
0.75
0.0
5.0
10.0
25.0
50.0
100.0
2000
0.0
5.0
10.0
25.0
5000
100.0
200.0
Planar dataset.
(b) QM9 dataset.
Figure 6: Impact of RDB with different level of sparsity.
symmetrical positions adhere specific proportionality. However, in practice, none of the specific designs illustrated in Figure showed clear advantage over others in the settings we evaluated. As a result, we chose the general case for our experiments, as it offers the most flexibility by incorporating the least prior knowledge.
Orthogonal to the design of R&p8, we must also consider the hyperparameter 7,, which regulates the magnitude of stochas- ticity in the denoising process. Specifically, setting 7) = (thereby relying solely on Ri) minimizes the expected number of jumps throughout the denoising trajectory under certain conditions, as shown by Campbell et al. (2024) in Proposition 3.4. However, in continuous diffusion models, some level of stochasticity has been demonstrated to enhance performance (Kar- ras et al., 2022; Cao et al., 2023; Xu et al., 2023). Conversely, excessive stochasticity can negatively impact performance. Campbell et al. (2024) propose that there exists an optimal level of stochasticity that strikes a balance between exploration and accuracy. In our experiments, we observed varied behaviors as increases, resulting different performance outcomes across datasets, as illustrated Figure 10.
B.4. Hyperparameter Optimization Pipeline
significant advantage of flow matching methods their inherently greater flexibility in the sampling process compared to diffusion models, as they are more disentangled from the training stage. Each of the proposed optimization strategies exposed in Sec. 3.2 expands the search space for optimal performance. However, conducting full grid search across all those methodologies is impractical for the computational resources available. To address this challenge, our sampling optimization pipeline consists of, for each of the proposed optimization strategies, all hyperparameters at their default values except for the parameter controlling the chosen strategy, over which we perform sweep. The optimal values obtained for each strategy are combined to form the final configuration. In Tab. 5, we present the final hyperparameter values obtained for each dataset. This pipeline is sufficient to achieve state-of-the-ane performance, which reinforces the expressivity of DeFoG. We expect to achieve even better results a more comprehensive search of the hyperparameter space was carried out.
held constant
20

---

DeFoG: Discrete Flow Matching for Graph Generation
V.U.N. (Planar)
0.9
Ratio (Planar)
251
Stochnetieity
Tanget Guidaacce
0.6
40
Sample Distortion
Vanilla DPM
0.3
6
DiGress
0.0
10
100
1000
5
10
50
100
1000
# Steps
Steps
(a) Planar dataset.
0.9
251
V.U.N. (TTree
Ratio (Tree)
0.6
40
0.3
6
0.0
5
10
50
100
1000
10
50 # Steps
100
1000
# Steps
(b) Tree dataset.
0.9
100
V.U.N. (SBM)
Ratio (SBM)
0.6
32-
10-
0.3
3
0.0
10
50
100
1000
5
10
50
100
1000
Steps
Steps
(c) SBM dataset.
Figure 7: Sampling efficiency improvement over all synthetic datasets.
To better mode detailedly illustrate the influence of each sampling optimization, show in Figures 7 and in present the impact of varying parameter values across the synthetic datasets Figure 7 and molecular datasets in Figure 8 used in this work.
While Figures and are highly condensed, we provide a more fine-grained version that specifically illustrates the influ- ence the hyperparameters 7) and w. This version highlights their impact when generating with the full number of steps (500 and 1000 for molecular and synthetic data, respectively) and with 50 steps. As emphasized in Figures and 10, the influence of these hyperparameters varies across datasets and exhibits distinct behaviors depending the number of steps used.
Several key observations can be made here. First, since the stochasticity is designed around the detailed balance condition, which holds more rigorously with increased precision, it generally provides greater benefits with the full generation steps but leads to a more pronounced performance decrease when generating with only 50 steps. Additionally, for datasets behavior, indicating the
such as Planar, MOSES, and Guacamol, the stochasticity shows an mncressing-then-derreaad presence of an optimal value. Furthermore, while target guidance significantly improves validity across different datasets, it negatively affect novelty and the average ratio when set too high. This suggests that excessive target guidance may promote overfitting to high-probability regions of the training set, distorting the overall distribution. In conclusion, each hyperparameter should be carefully chosen based on the specific objective.
To demonstrate the benefit each designed optimization step, we report the step-wise improvements by sequentially adding each tuned step across the primary datasets - synthetic datasets in Figure 11 and molecular datasets in Figure 12 used in this work.
21

---

DeFoG: Discrete Flow Matching for Graph Generation
100-
75
Stochasticity
Validity (QM9)
Novelty (QM9)
Target Guidance
Stachusticity
60-
Sample Distortion
Target Guidance
Viniilla DFM
Somple Distortion
DiGress
60
Vanilli DFM
DiGress
30
G0
100
1000
10
50
100
500
# Steps
Steps
(a) QM9 dataset.
100-
Validity (MOSES)
Novelty (MOSES)
988
60
30
94
5
10
50
100
1000
10
50
100
500
# Steps
# Stops
(b) MOSES dataset.
Validity (Guacsmoll)
90
Novelty (Guacamol)
100
30
96
94
500
# Steps
Steps
(c) Guacamol dataset.
Figure 8: Sampling efficiency improvement over all molecular datasets. The Guacamol and MOSES datasets are evaluated with 2,000 samples, and validity and novelty are computed using local implementations for efficiency instead of the original benchmarks. For the Guacamol dataset, we apply validity metrics that account for charged molecules, reflecting the dataset's intrinsic characteristic of containing significant number of such molecules.
B.5. Understanding the Sampling Dynamics of Ri
In this section, we aim to provide deeper intuition into the sampling dynamics imposed by the design of R2, as proposed by (Campbell et al., 2024). The explicit formulation of Rt can be found in Eq. (3). Notably, the denominator in the expression serves normalizing factor, meaning the dynamics of each sampling step are primarily influenced by the values in the numerator. Specifically, we observe the following relationship:
dep: (2)21)) = 8(2,, 21) + Po(2:),
derived by directly differentiating Eq. (1). Based on this, the possible values of R2 for different combinations of and Zrdde are outlined in Tab. 3.
Table 3: Values of the numerator of R, for different 2, and 2e4d1-
CONDITION
NUMERATOR OF R ((z1
INTUITION
2t 21, Zt4dt = 21
ReLU(pp(21) Po(21)) =
No TRANSITION
2t 21, Zitd # 21
ReLU (po
po po (2((24d)))
No TRANSITION
# 21, Zitdi 21
ReLU(po(2) po(2(-de) + 0
TRANSITION TO
2t # ž1, dt # 21
(eLU(po(2z) - do(
TRANSITION TO ž+ IF po(2)) > po(2)tat)
From the first two lines of Tab. 3, we observe that once the system reaches the predicted state 21, remains there. If not, R
22

---

DeFoG: Discrete Flow Matching for Graph Generation
only encourages transitions other states under conditions: either the target state is 21 (third line), the corresponding entries in the initial distribution for potential next states have smaller values than the current state (fourth line). As result, the sampling dynamics are heavily influenced by the initial distribution, as discussed further in Appendix C.1.
For instance, with the masking distribution, the fourth line facilitates transitions to states other than the virtual "mask" state, whereas for the uniform distribution, no transitions are allowed. For the marginal distribution, transitions are directed toward less likely states, Note that while these behaviors hold when the rate matrix consists solely of Rú additional tran- sitions can be introduced through R RDB (as detailed in Appendix B.3) by applying target guidance (see Appendix B.2).
B.6. Performance Improvement for Undertrained Models
In this section, we present the performance model trained on the QM9 dataset and the Planar dataset using only 30% of the epochs compared to the final model being reported. We employ the same hyperparameters as in Tab. 8 and Tab. for the sampling setup, as reported in Tab. 5.
Compared to fully trained models, our model achieves 99.0 Validity (vs 99.3) and 96.4 Uniqueness (vs 96.3) the QM9 dataset. For the Planar dataset, it attains 95.5 Validity (vs 99.5) and an average ratio of 1.4 (vs 1.6). These results demonstrate that, even with significantly fewer training epochs, the model maintains competitive performance under well-designed sampling procedure, although extended training can still further improve performance. Notably, all metrics surpass the discrete-time diffusion benchmark DiGress (Vignac et al., 2022). As a result, the optimization in the sam- pling stage proves particularly beneficial when computational resources are limited, by enhancing the performance of an undertrained model.
23

---

DeFoG: Discrete Flow Matching for Graph Generation
@ (Tagee Guidance) Plauee
85
Tattn
10
V.U.N.
0.15
033
0.00 01
0012
05
w- 1000 steps
w- 1000 stegs
50 strpp
ar 50 stege
at (Tangel Guidance) Tree
VON.
Batio
Batto
0. 6.1 0.2 035 0.1
62
0.1
0.5
0.0
000
062
085
0.1
52
03
04
05
0.0
0.1
002
DGS
O.L.
0.2
0.
04
100
0. 0.0
0.02 D02 0.1 02
08 04 05 10 uP stree
1009 strge
1000 strge
50
(Targes Guidance)
SBM
0.
V.UXX
V-I.N.
Hadio
0. 001 0.6.
0.0 0.7
b3
0.01
9:05
03
0.4
000 02
(Target Guidance)
0.31
0.95
0.42
Valilte
0980
Novelty
Nowelty
022
8:93
6i ea
stopo
steys
stepa
stoge
(Target Guidunee)
MOSES
0.58
Valaiig
0.50
Noadly
0.910
Vadially
8:70
0.57
8:999
60 0.20
012
nl6 0.
65
10
08 tod
0312 300 steps
82 us 14
1.0
00
0dl 012
1.26
02
us
04
0.s
3/1 GilL
u5 64 u.
ue-
500 staps
50 vbge
(Target Guidance)
Guacarnol
(L908
Novlly
Valiiio
Noedly
0094
060 8.2 0.1 02.
03.
03
L.
60 nés 0.2 nce n. 02 03
044 04
0/2 1.36 0. 02 as 04 0. GOL 50
30
5OL 012
008
02 0S
0.4 0.5 1.5
500
Figure 9: Influence of target guidance over all datasets.
24

---

DeFoG: Discrete Flow Matching for Graph Generation
Y (Stodaaliciy)) Planar
V.0.
0.58
210
0.50
110
25.0
960
1000
2001
1901
000
2000
1000
2000
13
1300/
strge
0' 1000 strps
9- 50 steps
9- steps
v (Stochnelkitt)) Tree
0.50
24
0.30
0.72
Hotio
0.00
Hotto
0154
0.00
0.0
5.0
10.0
35.0
10.0
1869
200.
0.0
5.0
10.0
25.0
00.0
100.0
200.0
0.0
5.0
10.0
25.0
00.0
100.0
200.0
0.0
5.0
1000
25.0
30.0
100.0
2060
1000
1000
50 strpe
strgie
(Stochasticity)
SBM
0.7%
Tariin
1008
0.
5.0
10.0
500/
30.0
1000
50.0
2000
(Stochasticity)
0.0
Noodly
0,1500
0,000
0.5676
5.0
1000
stogo
4 atopa
0-
steps
1) stopo
(Stochastirity)-
MOSES
Vilaitt
Noodly
2.06
Velaill
Nowdly
0.588
0.575
0.530
0.0
5.0
100.0
25.0
$6.0
100.0
200.3
3000
20.01
50.0
$30.0
2010
0.0
10.0
20.0
50.2
1OLD
200LD
06
10.0
25.0
50,0
1000
20003
500
stare
7V- 300 steps
50
stag+
50
stapp
(Stochasticity)
Guacamol
0.990
Velaite
0.50
Vallite
0.4
Novelty
8.996
3,003
0.58
0.
10.0
25.3
$0.1
1060
2000
3.0
100
21,1
SLD
1000
2010
0.0
10.0
25.0
500
1000
200.
10.5
25.0
100.
2500
500
50
50
Figure 10: Influence of stochasticity level over all datasets.
25

---

DeFoG: Discrete Flow Matching for Graph Generation
Sampling Iteettnn Planer
(Tange Grsdanee) Flanaz
(Studuackitt)) Planer
BA0
0.90
0:00
0.00
EAC
0.00
000
3000
4.00-
4.0-
3000
300-
900
10
20
103
1000
10
20
100
1003
90
1930
Strge
Stryys
(a) Planar dataset.
Sumplieg Dicarion
(Targel Chilinne))
(Hocdhsstictt) Tiee
0.00
50
0.30
30.8
25.0
0.00
3000
3000
1.80
300
1.00
1.50
10
100
1000
1000
(A]
J00
1000
Skye
Stap
(h) Tree dataset.
(Tugge Caidance) SBM
(Stochaetbrity)
11511
0.50
0.50
0.40
0.00
0.00
3.90
2.00
1.50
1000
(c) SBM dataset.
Figure 11: Stepwise parameter search for sampling optimization across synthetic datasets.
26

---

DeFoG: Discrete Flow Matching for Graph Generation
Sampling Denomin QUP
(Tregrt Guidhnns) - Q289
(Moochestirtt)) QMD
11.00-
0.90
0.00
EXC
0.88
100
3000
3000
0.00
0.00
25
110
501
10
21
100
500
Stze
Stegs
(a) QM9 dataset.
Samplnn Dicortion MOSIS
(Targel Chblinace)
(Stodmastiit)) MUSES
01:00
0.50
50
30.8
25.8
0.00-
0.00
1.00-
3000
3000
0.00
0.9
0.00
8100
0.8
100
100
100
60
100)
100
Size
Stepe
Stipe
(b) MOSES dataset.
Grneanai
(Taget Gridanee) Caucaad
y (Seot boatriity Gracamel
000
1.300
0.40
6.40
1.00
1.00
1.00
1.00-
0.50
0.99
0.99
Guacamol dataset.
Figure 12: Stepwise parameter search for sampling optimization across molecular datasets.
27

---

DeFoG: Discrete Flow Matching for Graph Generation
C. Train Optimization
In this section, we provide a more detailed analysis of the influence the various training optimization strategies intro- duced in Sec. 3. In Appendix C.I, we empirically demonstrate the impact of selecting different initial distributions on performance, while in Appendix C.2, we examine the interaction between training and sampling optimization.
C.1. Initial Distributions
Under DeFoG's framework, the noising process for each dimension modeled linear interpolation between the clean data distribution (the one-hot representation of the current state) and an initial distribution, Po- As such, intuitive that different initial distributions result in varying performances, depending particular, they have a direct impact on the sampling dynamics through Rł (see Appendix B.5) and may also pose tasks of varying difficulty for the graph transformer. In this paper, we explore four distinct initial distributions":
the denoising dynamics they induce. In
Uniform: po = [2: 1 2 (Campbell et al., 2024).
21 E A Here, the probability mass is uniformly distributed across all states, as proposed by
Masking: Po [0, .....
, 0, 1] E A In this setting, all the probability mass collapses into a new "mask" state at O. introduced by (Campbell et al., 2024).
Marginal: Po [m², .i...... mzz 2 where my denotes the marginal probability of the i-th state in the dataset. This approach is widely used in state-of-the-art graph generation models (Vignac et al., 2022; Xu et al., 2024; Siraudin et al., 2024).
Absorbing: Pa = [O..... ..... 1....,0.0 0] E 22, representing a one-hot encoding of the most common state (akin to applying an argmax operator the marginal initial distribution).
We apply each of these initial distributions to both node and edges, with the corresponding dimensionalities. In Figure 13, we present the training curves for each initial distribution for three different datasets.
Validity (Planner)
0.8
Validity (QAI0)
Valiiiy (SBM)
0.98
Marpinal Usiform Masling Abworbing
0.4
0.4
0.96
0.0
0.0
0
25000
50000
75000
100000
1000
2000
20000
440000
Streus
# Stops
Soops
Figure 13: Influence of initial distribution over different datasets at different training steps.
We observe that the marginal distribution consistently achieves at least as good performance as the other initial distributions. This is supported by two key observations in previous work: first, Vignac et al. (2022) demonstrate that, for any given distribution, the closest distribution within the aforementioned class of factorizable initial distributions is the marginal one, thus illustrating its optimality properties throughout the noising process, maintaining graph-theoreticn characteristies like sparsity (Qin et al., 2023). We conjecture that this fact facilitates the denoising task for the graph transformer. This reinforces its use the default initial distribution for DeFoG. The only dataset where marginal was surpassed was the SBM dataset, which we attribute to its inherently different nature (stochastic, instead of deterministic). In this case, the absorbing distribution emerged as the best-performing choice. Interestingly, the absorbing distribution tends to converge faster across datasets.
prior. Second, the marginal initial distribution preserves the dataset's marginal
Lastly, it is worth noting that in discrete diffusion models for graphs, predicting the best limit noise distribution based solely on dataset characteristics remains, to our knowledge, open question (T'seg al., 2023). We expect this complexity to extend to discrete flow models well. Although this is outside the scope of our work, we view this as an exciting direction for future research.
Recall that 7 represents the cardinality of the state space, and A z the associated prohahility simplex.
28

---

DeFoG: Discrete Flow Matching for Graph Generation
415
66
6:01
4:0
011
40
1.23
4:21
3379
0443
LM0
1:M
4000
6.00
0605
2001
New
loogle Buter
(a) QM9 Validity
(b) QM9 FFC
(c) Planar- Validity
(d) Planar- Average Ratio
Figure 14: Interaction between training and sampling time distortions.
C.2. Interaction between Sample and Train Distortions
From Appendix B.4, we observe that time distortions applied during the sampling stage can significantly affect perfor- mance. This suggests that graph discrete flow models do not behave evenly across time and are more sensitive to specific time intervals, where generative performance benefits from finer updates achieved by using smaller time steps. Building on this observation, we extended our analysis to the training stage, exploring two main questions:
Is there a universally optimal training time distortion for graph generation across different datasets?
How do training and sampling time distortions interact? Is there alignment between the two? Specifically, if we understand the effect of time distortion at one stage (training sampling), can we infer its impact at the other?
To investigate these questions, we conducted a grid search. For two datasets, we trained five models, each with a different time distortion applied during training. Subsequently, we tested each model by applying the five different distortions at the sampling stage. The results are presented in Figure 14.
The results vary by dataset. For QM9, validity appears primarily influenced by the sampling distortion method, with preference for distortions that encourage smaller steps at the end of the denoising process (such as polydec and cos). However, for FCD?, the training distortion plays more significant role.
For the planar dataset, we observe a near-perfect alignment between training and sampling distortions in terms of validity, with a clear preference for more accurate training models and finer sampling predictions closer to t = 1. The results for the average ratio metric, however, are less consistent and show volatility.
These findings help address our core questions: The interaction between training and sampling distortions, as well as the best training time distortion, is dataset-dependent. Nonetheless, for the particular case of the planar dataset, we observe a notable alignment between training and sampling distortions. This alignment suggests that times close to t = 1 which are critical for correctly generating planar graphs. We conjecture that this alignment can be attributed to planarity being a global property that arises from local constraints, as captured by Kuratowski's Theorem, which states that a graph is non-planar if and only if contains a subgraph reducible to K₂ or K3,3 through edge contraction (Kuratowski, 1930).
To determine if the structural properties observed in datasets like the planar dataset can be detected and exploited without requiring an exhaustive sweep over all possibilities, we propose developing a metric that quantifies the difficulty of predicting the clean graph for any given time point E [0, 1). For this, we perform a sweep over for a given model, where for each f, we noise sufficiently large batch of clean graphs and evaluate the model's training loss on them. This yields curve that shows how the training loss varies as function of t. We then track how this curve evolves across epochs. To make the changes more explicit, we compute the ratio of the loss curve relative to the fully trained model's values. These curves are shown in Figure 15.
Loss Tracker
As expected, the curve of training loss as a function of t (left in Figure 15) is monotonically decreasing, indicating that as graphs are decreasingly noised, the task becomes simpler. However, the most interesting insights arise from the evolution of this curve across epochs (right in Figure 15). We observe that for smaller values of t, the model reaches its maximum capacity early in the training process, showing no significant improvements after the initial few epochs. In contrast, for
'FCD is calculated only for valid molecules, so this metric may inherently reflect survival bias.
29

---

DeFoG: Discrete Flow Matching for Graph Generation
CE Tracker Across Training Steps
Ratio to 100k
1.5
2.0
2k
100k Truin
2k
CB loss
1.0
40k
40k
60k
60k
80k
80k
100k
Ratio
1.0
100k
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.6
0.8
10
Figure 15: In the left figure, present the cross-entropy (CE) loss used for training different time steps across various stages of the training process. The right figure shows the ratio of each CE loss trajectory relative to the last one, illustrating the overall training trend and emphasizing which parts of the model are predominantly learned over time.
larger values of & (closer to = 1), the model exhibits substantial improvements throughout the training period. This suggests that the model can continue to refine its predictions the time range where the task easier. These findings align with those in Figure 14, reinforeing our expectation that training the model be more precise this range or providing more refined sampling steps will naturally enhance performance in the planar dataset.
These insights offer valuable understanding of the specific dynamics at play within the planar dataset. Nevertheless, the unique structural characteristics of each dataset may influence the interaction between training and sampling time distortions in ways that are not captured here. Future work could explore these dynamics across a wider range of datasets to assess the generalizability of our findings.
30

---

DeFoG: Discrete Flow Matching for Graph Generation
D. Theoretical Results
In this section, we provide the proofs the different theoretical results the paper. First, we provide results that are domain agnostic, i.e. that hold for general discrete data, and then instantiate them for the specific case of graphs, yielding Theorems I and 2. Then, we proceed the permutation invariance/equiivriance guarantees of DeFoG, and some remarks on the expressivity of the RRWP additional features.
D.I. Theoretical Results on the Generative Framework
In Appendix D.I.I, we provide a proof of the bounded estimation error of the rate matrix for general discrete data, and instantiate it for graphs, yielding Theorem 1. Then, in Appendix D.1.2, we prove the bounded deviation of the generated distribution for general discrete data as well, and instantiate it for graphs, yielding Theorem 2.
Importantly, for general discrete data, we jointly model D discrete variables, (z()) , = E Z
D.1.1. BOUNDED ESTIMATION ERROR OF UNCONDITIONAL MULTIVARIATE RATE MATRIX
We start by introducing two important concepts, which will reveal useful for the proof of the intended result.
Unconditional Multivariate Rate Matrix
As exposed in Sec. 2, the marginal distribution and the rate matrix of a CTMC
related by the Kolmogorov equation:
aep: R Pt
Σ Re
Ra(zetat, 2e)e
Re(2,, (x.)
Probubility Inllow
Probubility Outllow
The expansion in the second equality reveals the conservation law inherent in the Kolmogorov equation, illustrating that the time derivative of the marginal distribution represents the net balance between the inflow and outflow of probability mass at given state.
Importantly, in the multivariate case, the (joint) rate matrix can be expressed through the following decomposition:
D
1:D. Re(=)
Σ
8(2)
1:DV(d)
(.D((d)) R!dd (=t 1.D (d)
(10)
D (:D)(d) 1:D)(d) E
Σ
5(2
E44e 1= Rh (x1 ( ((fuel((1))
(d)
(11)
In the first equality, 1: D (d) refers to all dimensions except d and the 8 term restricts contributions to rate matrices that account for at most one dimension transitioning at a time, since the probability of two or more independently noised dimensions transitioning simultaneously zero under a continuous time framework (Campbell et al., 2022; 2024). In the second equality, the unconditional rate matrix is retrieved by taking the expectation over the 2 z1-conditioned rate matrices. (d) (df) =(fdel=[( denotes the univariate rate matrix corresponding to dimension d (see Eq. (3))
Specifically, R2 (d)) (2t
Total Variation The total variation (TV) distance is a distance measure between probability distributions. While it can be defined more generally, this paper focuses on its application to discrete probability distributions over a finite sample space 2. In particular, for two discrete probability distributions P and Q, their total variation distance defined as:
1 Σ [()))
P QIITv
Q())
(12)
2
We are now prepared to proceed with the proof of Theorem 11.
Theorem 11 (Bounded estimation error of unconditional multivariate rate matrix). Given E [0, 1],
2,D,, .1:D 2D
and 2 I.D ())) les Re(2)-D 1:D be the groundtruth rate matrix of the CTMC, which we approximate with
31

---

DeFoG: Discrete Flow Matching for Graph Generation
(=)- .. The corresponding estimation error is upper-bounded as follows:
| (+aut)) R2 =++a))1 <o + CI (= Ed-1 - -ogg 0,1d)
(2) (4) |2
(13)
where
10 P (sf (2) ()) log Pile (z) l2):))
C1=2D C:=DDuupd<(L.....
() 102 200) / :x
(:D)(d) 1:D((d) with Czco- 8(2) #
[R (z(
(1) 2t (z( )}
sup
Proof. This proof is an adaptation of the proof of Theorem 3.3 from Xu et al. (2024) to the discrete flow matching setting.
By definition (Eq. (11)), we have:
D
Rx(2 (2tt))
L.D.)
Σ
8(2
(:D)(d)
244at R (2) 2(ffee)
=
d=1
((1
1:D)(d)
2:Di(d)) E (, 1. R2 (zt
(=! (d)
d=1
D
Σ
8(1
1:D)(d)
1-Di(d))
Σ
pip (z1 2,
I:D R( ( 200 (
=
d=1
Thus:
RR(e
1.D I.D (
(= I:D
Σ 8(2
(:D\(d) I-D((d))
(d) (d) (e)))
(0) (pip) (=
0,600
(2) 24 2(:D))
24di
,
Pije
d=1
(4)
D
<
(1.D1007 5(2)
1:D((d)
Σ
RD (2( (d) ((0 (1)0 21:00
Pije (2
0.(0) (d) 2 (2(0) 22:00) }]
d=1
1:D)(d) 1:D)(d)
(R
(d) (z) (d) (00 (10m)1111) )3
Σ
Pije (21 11
(d) (d)
Pije (2) 24 |:D)
0,(d)
(d)
244
d=1
2(
D
Σ 2020
11 (d) (=1 1
Pije
(.(d) (d)
(z1 || ||T
(14)
d=1
Σ Cluss V 2DI.. (p (1(()) (>!!') |1 P
0.(d) (z) |=!
(15)
pl (112g (d) (ل!
Σ
2 C2 Σ
Paje (1(00) ) log
(d)
Pije (2)=) |2!:D
(d)))
d=1
2(10
32

---

DeFoG: Discrete Flow Matching for Graph Generation
In Eq. (14), use the definition of TV distance as defined in Eq. (12) and Eq. (15) results from direct application of Pinsker's inequality. Now, we change the ordering of the sum and of the square root through the Cauchy-Schwand
inequality: Ed=1 VoLivaa ra V Eds aa 1 S V
vT s VVDEL zd-
So, we obtain:
Pije (2) (2( (2) (z] log Pilt (1 e((
(2 1:D, (2
R2
(z) 1: 2 S
2D Σ
C
Epile
(d)
200
Pilt (z) (d) (2
#1
D
2D sup
} 2(0) dE(1 ()
(C210
Σ
Σ
(d) pl (2)
|2 D) [og
Pile (d)
(=(0) |1 log 0,(d)
(=|01 [c]
D Σ
C2
C3
Pile (2) 12)
(d) (10) (2)
0.(4) log Pile (z) (=(") 12)
where in the last step we rearrange the terms independent of the approximation parametrized by 0 as constants: C2
2D supue ( J. C3 = -g(d) E2 (= log Pije (=) 12))).
We now develop the underbraced term in the last equation":
D
ΣΣ ile
(d) (1)
|2
1.D) log Pile (21
0.(d) (d) 12!1))
d=1
(2)
D
p(z (d) 1:D
logPijc (=(0) (2:D))
log 0.(d) (11)
(2
d=1
(
D
Σ
p(z ,2 21
(d) 1.D 1:Di(d) log Pig (2)
0.(d) (10) 12 (2
d=1
(Dd)()
D
1:D
2
1:D
logP (2) (2() (2:0)
log
0.(d)
pr(()
d=1 2
D
Σ
(2)
1:17
(2] (2 log Pile (z) 12
1:
log
0.(d) [d]
D)
d=
Σ
p1(2
1:D Pet1
log Pite (2)
8.(d) (d) )::D)
pr
:T:0
-4 E P)
(e (2 1:D
log log Pijs
0.(d)
(
(=(1))
Cross-cntropy
where C4 1/p(
'In this step, we omit some subscripts from joint prohahility distributions as they not defined in the main paper, but they can be inferred from context.
33

---

DeFoG: Discrete Flow Matching for Graph Generation
Replacing back the obtained expression into the original equation, obtain:
[=] 22ide) (
= < C2C3 + C2 [ 12 Ex=1 logg1 (2) (2) (z10)) 24 ((:
0,(4)
retrieving the intended result.
Corollary (Bounded estimation error of unconditional rate matrix for graphs). Given t E [0, 11, graphs G2, G and G1 ~ PippirGG (L1), let (G, G(+dt) be the groundtruth rate matrix of the CTMC, which we approximate with R (Gr G(tdt). Then, there exist constants Co: C1, C33 such that:
Re Ge4dt) (Ge, Gr4de)12
N
Sōu + C2 (G.)
(tn(G(/Gr) Σ
- -logPij (2) (x)
(z)
+ C2 Ep((C.)
Pol((rr/Gi)
Σ
log (.10))
0.(0)) (1)) G+)
ISKJSN
Proof. Recall that a graph G is defined as the set of nodes and edges G = (wlmn: editksii such that a(()) E X
{1...., X}, clt)) E = (1..... E), so we can develop Eq. (11) as follows:
Re (G1, Getdt)
Σ (G)(
G2tat)
E
pnelaf")
R1 (a , (n) (x(
Be(xfio (alppa)))
Σ
(c)
(Md) (tdtt
E Pl
[e (10) (90 -)
(16)
ISKJJ
where (ln)) and G\OO) denote the whole graph except the node n and the edge connecting node i to node j, respectively, Therefore, the result from Theorem 11 implies:
(Gr Gz+de) (Gr, Gz4de) S
< Re (x N Jm:N
Rt (2!in:N xx(Ta) + [R((e, Lisj.N (eiai-
(e) , ,rddi (
N Σ
S O/ + +C (p)(
(t]((G
lig (s) (.(m)(2((()
log 8.(m) (n)
(Gt)
n=1
+
C + C
E Ep((C.)
G1)((.](())
Σ
(, e.( llog
(G))
IgiKiSN
DE Idi derived from the Cauchy-Schwarz inequality in the proof of We now apply the identity Ee Vaa S V Theorem 11, with D 2 to obtain:
[R Getai) RR (Gr, Grtadls
N
< 0 C, Ep)(i))
(G.
Σ
log 1|1
(.(m)
(z) (a(")
))
1/2
+ Cg (G1)
GG)(G(
Σ
( log P Pıt
(e) (c(()) (Gi)
ISiKjEN
with Co = 2(C + +CE), C 20 and O2 205, yielding the intended result.
34

---

DeFoG: Discrete Flow Matching for Graph Generation
1.1.2. BOUNDED DEVIATION OF THE GENERATED DISTRIBUTION
As in Appendix D.I.I, we start by introducing the necessary concepts that will reveal useful for the proof of the intended result.
On the Choice of the CTMC Sampling Method Generating new samples using DFM amounts to simulate a multivariate
CTMC according to:
Petdeje ( :D = ((z ! =(4)))) + (2) ( )
(17)
where R= xx44a) denotes the unconditional multivariate rate matrix defined in Eq. (11). This process can be sim- ulated exactly using Gillespie's Algorithm (Gillespie, 1976; 1977). However, such an algorithm does not scale for large D (Campbell et al., 2022). Although r-leaping is a widely adopted approximate algorithm to address this limitation (Gille- spie, 2001), it requires ordinal discrete state spaces, which is suitable for cases like text or images but not for graphs. Therefore, we cannot apply it in the context of this paper. Additionally, directly replacing the infinitesimal step dt in Eq. (11) with a finite time step At à la Euler method is inappropriate, as [z **+de) prevents state transitions in more than one dimension per step under the continuous framework. Instead, Campbell et al. (2024) propose an approximation where the Euler step is applied independently to each dimension, as seen in Eq. (4).
In this section, we theoretically demonstrate that, despite its approximation, the independent-dimmnsioonn Euler sampling method error remains bounded and can be made arbitrarily small by reducing the step size At or by reducing the estimation error of the rate matrix.
Markov Kernel of a CTMC For this proof, we also introduce the notion of Markov kernel of a CTMC. The Markov kernel, Re-++A1 is a function that provides the transition probabilities between states over a finite time interval, At:
Pe+ai = R.
(18)
For example, for univariate CTMC with state space Z of cardinality Z, the Markov kernel Re-14 is a matrix where each entry R2()) t- represents the probability that the single variable transitions from state i at time t to state j at time + At, i.e., (il))
The definition of Markov kernel contrasts with the of rate matrix (or generator), Rg, which instead characterizes the infinitesimal transition rates between states at given time t. Thus, while the rows of the rate matrix sum to O, the Markov kernel matrices are stochastic, i.e., Σjez R(5)) R 1, Vi. This contrasts with the rate matrix where rows sum to 1. Additionally, Markov kernels must also respect the initial condition Re-,- I, where T denotes the identity matrix.
Recall from Sec. 2 that the evolution of CTMC is governed by the rate matrix through the equation:
O.p: R Pt:
which represents a first-order differential equation. Here, we focus on the home-homogeneous case, where R₂ = R in the time interval [4; 1+ At], i.e., the rate matrix remains constant within the time interval. In that case, its solution is given by:
P++Ai = R At Pt
Therefore the result above sets, by definition, the corresponding Markov kernel of a constant rate matrix in finite time interval At as:
R = (e ATTT = RAA
(19)
where the second equality is direct consequence of the definition of the matrix exponential as series expansion.
We are now in conditions of proceeding to the proof of Theorem 8. We start by first proving that, in the univariate case, the time derivatives of the conditional rate matrices are upper bounded.
Lemma 5 (Upper bound time derivative of conditional univariate rate matrix). For t (0, 1), 2t, 24tde, 21 Z, with # dt then we have:
|0 R, (zz, #+tde|21)1 S 22)
35

---

DeFoG: Discrete Flow Matching for Graph Generation
Proof. Recall that Paja (1) (z =1) (1 1) Po(z)) (from Eq. (I)). Two different cases must then be considered.
In the first case, Pej1 (zel 21) 0. This implies that both extremes of the linear interpolation are O. In that case, the linear interpolation will be identically 0 for t E (0, Thus, by definition, R2 (2,, Zz4de(21) = 0 for t E (0, 1), which implies that |0 R7 (2e, 2240r|21)1 = O.
Otherwise (pin( > 0), we recall that Ry (zt, Eetai (1) with 24 * 2t has the following form:
ReLU (Oepr) 1 (2e+ael (=1) (epan(zelz1))
Rt (3,, =1dde(21)=
(20)
2 Pat (21l21)
where z7 = (2 (=)l2)))1 0J}.
By differentiating the explicit form of Pip Ptp1 (z)l2),, we have that ( = 0. As consequence, the numerator of Eq. (20) has zero derivative. Additionally, also note that 27 is constant. Again, since (1p(2122) is linear interpolation between and Po and, therefore, it is impossible for Pap (2)(2)) to suddenly become 0 for t E (0, 1).
Consequently, we have:
O, R2 (Zt, 2(4aol21) ReLU (dipen (244al222) dep:l ( (20122)) 0:
1
2
Pei (2)1(1)))))
ReLU (d:peji (344d)221)
Ospm (spa)(
depeji (2e (2)
2
Paj1 (2el2))
We necessarily have |O.pap (z])=)) 16(2,, 21) - po po())) s 1, ReLU (0.p(z44rlz1) - 2, 2, 2 1, and, necessarily, p(2e(21) > 0. Thus:
ReLU (0)P (2(2))))))1)) (z 21) po(
|0, Rg (Zt, 214ae/=1)
2
Pei (2)(21²
2
Peji (2)22)2
We now upper bound the time derivative of the unconditonal multivariate rate matrix. We use Theorem 5 as an intermediate result to accomplish so. Additionally, consider the following assumption.
Assumption 6. For 2.D E 22,2 (d) Z and t [0, 1J. for each variable (d) of joint variable z II: there exists constant ((dd) > 0 such that (1)e(2] l2 1:D) & a.d) Pen (2 1100)
This assumption states that the denoising process is upper bounded by quadratic term the noising process. This assumption is reasonable because, while the noising term applies individually to each component of the data, the denoising process operates on the joint variable, allowing for more comprehensive and interdependent correction that reflects the combined influence of all components.
Proposition 7 (Upper bound time derivative of unconditional multivariate rate matrix), For 2 I:D. :tdtt 1), under Theorem 6, have:
2 and
|0, R...D (2) 1:: 21R $ 2B,2D
with B, sup B dEL.....
36

---

DeFoG: Discrete Flow Matching for Graph Generation
Proof. From Eq. (11), the unconditional rate matrix is given by:
Re(2! :F(+dt)
(
1:D)()) (.D)(d))
Fetde
:Pt+dt)
(4)
Σ d=1
8(2t
1:D)(d) (:D((d)
E (={")))))
(R (2) (2(()) (d)
b+dl
Pilt
8(zt
(:D)(d) 1:D((d)
Σ
Pije (21 |z, 1 ) (zt (4)
(d) (d)
(()
244del=1 )
d=1
1 EZ
So, by linearity of the time derivative, we have:
D
1:D
IID
=
(z)
(:D)(d) 1:D((d))
*2tde
Σ
Pile (21 |=| (=
(d) (4)
0, (2(
:44 (2)))
d=1
8( (:D)(d) 1:D((d)
Σ
(d) (c) (=(0)))1:))
|0) (x(
(a1) ((4d)1=(1)))
:4d
Pile (21
d=1
8(2t (:D)(d) (:D((d))
B ()) (2 12 12
2
Piji 12(
d=1
#1 2 EZ
D
< 8(2)
(:D)(d) 1:DD((d)
2B.2
d=1
< 2B,DD
where in the first inequality triangular we apply triangular inequality; in the second inequality, we use Theorem 5 and (4) (d) (d)) and [1 respectively.
Theorem 6 to upper bound |,, (7 (
(z!4)) =
Now, we finally start the proof of Theorem 8.
Theorem 8 (Bounded deviation of the generated distribution). Let Jee[o,1) 2D x [0, be CTMC starting with (t)-D)ejjo,)
po(z):D) Pe and ending with pi (z}:D) Paota whose groundtruth rate matrix is R. Additionally, let (yk:P))o 0 ..... be Euler sampling approximation of that CTMC, with maximum step size At = sup; At& and an approximate rate matrix R.. Then, under Theorem 6, the following total variation bound holds:
(l .D - Pduta Il I UZD + B(ZD) at O(At),
where U
sup [E E2D
Co + CiEp(t) |111(1-'1111
El - logriic [x])]] and B
B(d)
sup 1E(0.1), x (Z)
2 E2D
Proof. We start the proof by clarifying the notation for the Euler sampling approximation process. We denote its dis- cretization timesteps by 0 = to < 1 <... < lx = 1, with Att = 1 f It is initiated at the same limit distribution as the groundtruth CTMC, Pe, and the bound to be proven will quantify the deviation that the approximated procedure incurs comparison to the groundtruth CTMC. To accomplish so, we define R.E R. 1- as the Markov kernel that corresponds to applying Euler sampling with the approximated rate matrix R moving from t to ty. Therefore, R. -R R R.E and P) R Pe.
37

---

DeFoG: Discrete Flow Matching for Graph Generation
We first apply the same decomposition the left-hand side of Theorem as (Campbell et al., 2022), Theorem 1:
(lp(kk) Pdiata TV = || D. Pdataal |TV
||
P. Ce-Pijo22
Pijode ||TV + lipe - -p(=0 llv
(21)
|
Pe -e-Fiioe PijoPelTT lTv
K
sup | TT
(22)
k=
where, in Eq. (21), P1j0 denotes the path measure of the exact groundtruth CTMC and the difference between limit dis- tributions (second term from Eq. (21)) is zero since in flow matching the convergence to the limit distribution via linear interpolation is not asymptotic, constrast to diffusion models (Austin et al., 2021), but actually attained at f = 0. In Eq. (22), we introduce the stepwise path measure, i..., Pk = Prelte-1> such that Proo = PiP2... ... Pk- Therefore, finding the intended upper bound amounts to establish bounds on the total variation distance for each interval [f tx]-
For any distribution v::
|. v Pj u/|TV S ||...T v R-R u + R2. v u|TV
$ IPT v- R2 T ullTv + [R v - R v VlTv,,
(23)
where Ry denotes the resulting Markov kernel of running CTMC with constant rate matrix R between t and t.. For the first term, Proposition 5 from (Campbell al., 2022) to relate the total variation distance imposed by the Markov kernels with the difference between the corresponding rate matrices:
IPT v RR u1/TV= S
sup REz
Σ
1:D
1:D 1.D Re (2) ,
dl
1x-1 2
L:D #2
K
sup pi EDD
Σ
[e ID - Ri (2) I:D IID
1x-1 #
Pc A2liD 10
Discretization Error
Σ
I:D I.D - R2 (2) 1 cthhee B (2) :itdd))
1.D
sup D2D2
di
Estimation Error
The first term consists of the discretization error, where we compare the chain with groundtruth rate matrix changing continuously between f;-1 and t; with its discretized counterpart, i.c., a chain where the rate matrix is held constant to its value at the beginning of the interval. The second corresponds to the estimation error, where we compare the chain
generated by the discretized groundtruth rate matrix with an equally discretized chain but that uses an estimated rate matrix instead. For the former, we have:
38

---

DeFoG: Discrete Flow Matching for Graph Generation
sup PEZD
Σ
[a(2t I.D sAtdd))
Rie
(27 - jau
1--1 of
I:D *(td #
sup EDD
Σ
Re 12::D. 2t tk tt-1 dt
(24)
14-1
ZD
sup
(e, 1:D = 11 4x-1/ dl
(25)
14-1
1:0
1 dil EZD
< 227
Be 1k-1 1/1
(26)
14-1
(ZDAA
(27)
where, in Eq. (24), we use the Mean Value Theorem, with to E (tx-1, bx); in Eq. (25), we use the fact that there are ZD values of .I:D Et+de that differ at most only one coordinate from 2!:D; in Eq. (26), we use the result from Theorem 7 to upper bound the time derivative of the multivariate unconditional rate matrix; and finally, in Eq. (27), we define Bg sUPre(te Br.
For the estimation error term, we have:
sup # I. D
Σ
1:D Rl (21 :2 dt (2):D. (
R
du DtZ
(28)
14-1 < U.ZDAL
(29)
where, in Eq. (28), we use again the fact that there are ZD values of 2ID 2t+ that differ at most in only one coor- dinate from 2t I:: along with the estimation error upper bound from Theorem 11. In particular, consider U2
sup 1E(42-1,42).
U
1.D
+ with:
11:0 E E2
D
U
1:D
Co + C.E
log Pite (21
0.(d) (d) (=[=)
i.e., the square root of the right-hand side of Eq. (13).
remains to bound the second term from Eq. (23). We start by analyzing the Markov kernel R$ corresponding to a Markoy chain with constant rate matrix R between fę-1 and tg. that case, from Eq. (19) we obtain:
R₂
AtL
[ -
A/a)
i!
i=0
(R
Atx)²
(RR
Atx)² 3
I + R4-
Atp
+
+
2!
3!
On the other hand, we have from Eq. (4) that sampling with the Euler approximation multivariate Markov chain corre- sponds to:
39

---

DeFoG: Discrete Flow Matching for Graph Generation
Ptu 1
(2/x 1-
1:D| (210-1=12-1)
(d)
(d)
P Palls
(=tz (
d=1
D
= -II
6(2(2_)
2tx
[d))
+ R..(al
1:D
Ats
(30)
d=1
= 8 tt t4
I:D
I:D) + At
2 :t 2:D( R.,la)
1:D((d)
J.D (2 + O(Atx))
where in Eq. (30) have that the approximated transition rate matrix is computed according to Eq. (11) but using (.(d)
Pije (z) ()):D) instead of Pile (21
(id (d) ))):D.. To obtain R.E we just need to convert Ptulee-1
into matrix
form. Note that:
8(2 24 2:D) corresponds to in matrix form;
From Eq. (10), Ea=1 d (
1:D((d) Dittt) (tt-- Rtz
R2.(0)) (21:D 1:D ( 22)) (Atx²
=(a1) corresponds to R2,_, in matrix form.
These correspondences yield:
E. 1 Ar R
Consequently, we have:
R2 v RBEE
w U E =Atxt²?
(31)
Therefore, we get the intended result by gathering the results from Eq. (27), Eq. (29), and Eq. (31).
(1p(1: Pdata 1l S
(URZDAL + BL(ZDA() + O(A43))
k=
SUZD B(ZD)AL+ O(a)),
where At = sup, At the maximum step size, ΣK Al. = - sup, Us and = sups Br.
Below we provide corollary of Theorem 8, which consists of its instantiation for graphs.
Corollary 2 (Bounded deviation of the generated graph distribution). Let {Grheej,,1 be a CTMC over graphs starting with (o) Pe and ending with (G1) = Paitas whose groundtruth rate matrix is R4. Additionally, let (Gk)k=u,1...f
be a Euler sampling approximation of that CTMC. Then, we have:
N(N- N + XN+E
N(N 1)
[lp(Gz) - Pdatall lizv S 0 XNN+E
At + O(At)
2
2
where B is defined similarly to B from Theorem 8 but for gruphs: B
sup x6(0.1
sup a ex of Ef
(B("), ((())) with
G.
B(n)) (( > defined according to Theorem 6:
Pni(a("))aa ( < B(()) (an (((m)²² (1))
Go) < Bl0a) (1))
40

---

DeFoG: Discrete Flow Matching for Graph Generation
and
N Σ
U
sup te(o.]], Ge GradeE20
Co + (p)))
(tn((G
0.(m) log 1og (x) (z] (G,)
==
(ef()))H)) 1)
#
Pipi (tp( (())))
Σ
log
ISicJEN
Proof. Considering the definition of a graph as G = (pimaNatsttssss) we proceed through the different steps of the proof of Theorem 8. In particular, for the discretization error, we obtain:
N(N 1)
sup 1 G.
Σ
[R G(tae) Gi+ai) dt Bx
XN E
Atk
2
since there are XN + E NN-1 values of G24de that differ most in only one coordinate (node or edge) from C., with Bg s1)) B..
For the estimation error:
f sup (2- G.
fx
(XN+E)
N(N -
! Atk.
Re (Ge, G++ae) Ryg (G,, G(aa) dt =t=uu U. XN - E
2
Grtat*
since, again, there are XN + N(N11) values of G1+de that differ at most in only one coordinate from G, and Un
2
sup UGG-G where:
relta Itth)
Ge. Getde
N (G,
GGi+Gu = Co + O Ep((.)
Σ
log Pils (s) Gt)
8,(m) (n)
n=l
1) 1
+ C2 (p)()))
(G/((
Σ
- -logP 0.100) (c/00 (cl (69)))))))))
ISigjSN
i... the square root of the right-hand side of Theorem
The term ||Rg T v リ- RR. Therefore, by finally aggregating the terms above as in Theorem 8, we obtain:
F. v/|TY remains O (Atk ?)
-Paaa ll SO OXNN+E N(N-1)) + B XN+ E
N(N 1) 2
(lp(Gz) - Pauaal
At+ O(at)
1.1.3. CRITICAL ANALYSIS AND POSITIONING OF THEOREM AND THEOREM 2
Theorem I establishes that minimizing the cross-entropy (CE) loss directly corresponds minimizing upper bound on the rate matrix estimation enror. This result provides a direct and principled justification for using the CE loss, as it promotes accurate sampling from the underlying CTMC.
Prior work derive an ELBO loss and motivate using only the CE loss based on approximations upon the derived ELBO by dropping the rate matrix-de dependett terms (see Appendix C.2 in (Campbell et al., 2024)). In contrast, our bounds do

---

DeFoG: Discrete Flow Matching for Graph Generation
require such simplifications and agnostic rate matrix design choices (e.g., stochasticity level), reinforcing our training- sampling decoupling claim. Additionally, we note that concurrent work also derives tractable ELBO (Shaul et al., 2025); however, it addresses different family of conditional rate matrices.
Theorem 2 complements our theoretical analysis by bounding the deviation of the generated distribution from the target distribution, combining two sources of error: the discretization error from CTMC sampling, which is O()t), and the rate matrix estimation error, captured by Theorem 1. This type of bound a standard objective in generative modeling, aiming to guarantee that the generation process remains faithful to the underlying data distribution. For instance, Theorem in Campbell et al. (2022) presents an analogous bound in the context of discrete diffusion, though with significant differences (e.g., they assume bounded rate matrix estimation error, while explicitly prove it).
D.2. Theoretical Results on Architectural Expressivity
We now proceed to the graph specific theoretical results.
D.2.1. NODE PERMUTATION EQUIVARIANCE AND INVARIANCE PROPERTIES
The different components of a graph generative model have to respect different graph symmetries. For example, the permu- tation equivariance of the model architecture ensures the output changes consistently with any reordering of input nodes, while permutation-innariie
loss evaluates the model's performance consistently across isomorphic graphs, regardless of node order. We provide a proof for related properties included Lemma 3 as follows.
Lemma 3 (Node Permutation Equivariance and Invariance Properties of DeFoG). For any cettuttation-uuvvvrrtt de- noising neural network, the loss function of DeFoG is permulation invariant, and its sampling probability is permulation invariant.
Proof. Recall that we denote an undirected graph with N nodes by = (x.n eliik(NN) Here, each node variable is (1...., E}. We also treat G as multivariate
represented x" E X' (1,..., X,, and each edge variable ((v)) data point consisting of D discrete variables including all nodes and all edges.
We then consider a permutation function which is applied to permute the graph's 's node ordering. Under this permutation, the index n will be mapped to (n). We denote the ordered set of nodes and edges in the original ordering by ((1:m:N) and e(I:io::N) respectively, and by (1:=:N and e((Iiij::)) after permutation. Additionally, (aa) denotes the n-th entry of the corresponding ordered set (and analogously for edges). By definition, the relationship between the original and permuted entries of the ordered sets is given by: [n(n) = -0" -m)) and el(ts) = (1),0 (1)).
Permutation Equivariant Model We begin by proving that the DeFoG architecture is permutation-equivarine includ- ing the network architecture and the additional features employed.
Permutation Equivariance of RRWP Features: RRWP(M) = M, ... KM Raxax, where M = (D" 0
Recall that the RRWP features until K 1 steps are defined as
K.
We first prove that M(A) = D-1 is permutation equivariant:
((A) = -D'-1
(()
=(IDD(o 1(0, (A) 200) 2())
= -(D-1A)10-0))
= (1)
To facilitate notation, in the following proofs, we consider the matrix π E {0, NNNN representing the same per- mutation function a, with the permuted features represented as T We then prove that RRWP is permutation
42

---

DeFoG: Discrete Flow Matching for Graph Generation
equivariant.
P(TM*²) |TIm", TM ..... (TMTT) [n|=" <MMT (TM MII,,,.... ............ 1
since x TT x IN
=xP(M)m'
Permutation Equivariance of Model Layers: The model layers (MLP, FiLM, PNA, and self-attention) preserve per- mutation equivariance, as shown in prior work (c.g., Vignac et al. (2022) in Lemma 3.1).
Hence, since all of its components permutation-cquiivrriant, equivariant, so is the DeFoG full architecture. The next results hold for any permutation equivariant denoising neural network.
Permutation Invariant Loss Function DeFoG's loss consists summing the cross-entropy loss between the predicted clean graph and the true clean graph (node and edge-wise). Vignac et al. (2022), Lemma 3.2, provide a concise proof that this loss is permutation invariant.
Permutation Invariant Sampling Probability Given noisy graph Go sampled from the initial distribution, Po. the rate matrix at any time point & E [0, 1] defines the denoising process.
Recall that the conditional rate matrix for a variable b at each time step / is defined as:
ReLU [O.p.] ( (21) (
R2 (Zt, 244a (21)
2770 Peji (2
In our multivariate formulation, we compute this rate matrix independently for each variable inside the graph. We denote the concatenated rate matrix entries for all nodes with R2 (x:( " (2/ (2.))))))
(I:N) ((1:N)
In the following part, we demonstrate the node permutation equivariance of the rate matrix predicted by the trained equiv-
ariant network, denoted by fe- The proof for edges follows a similar logic. Suppose that the noisy graph Ge permuted, and the permuted graph has nodes denoted by xt (I:N) i.e., x. xt (nx) We have:
(1:N) ((:NN (1:20) (m)
R2
Iz
Fitde la
=R
Km)
(1)
(m)
(appu ((m)m) 1o ((())))))))) O.payi (2) (o((()))
ReLU
27 Pep (x ((m) 21 (m))
ReLU Oppap
(1
(1)) 12
(1))
-Pepqp (xg
1(x)
(10
(32)
2720 Pen (x;
1(n) ( (m())))
ReLU
O.pepp
((m)) -..pell11
(mm)
((m)) 12] (m0))
(33)
2720 Pejl (2)
[m1) 12 (mm)
= -R (n) - (m))
Fetet |x] (m))
(2 (1:N) (1:N)
(1:N)
# [ (1:N) (m)
In Eq. (32), we use the definition of permuted ordered set for af and de and, in Eq. (33), we use that fo is equivariant.
43

---

DeFoG: Discrete Flow Matching for Graph Generation
Furthermore, the transition probability at each time step / is given by:
D (d)
P P D
II
Pitaeee
d=1
D II (o(Gk dm1
G(fAe) + E vic Cid) [n(0 G | ai).
The transition probability Pi+ doje ( (+ ( G):D) is expressed a product all nodes and edges, operation that is inherently permutation invariant function with respect to node ordering. Furthermore, demonstrated earlier, the term E pp (G(D)) R (G( G4fAIGh is permutation equivariant since R,()) and [ are both per- mutation equivariant model fo permutation equivariant. Consequently, since the composition of these components yields permutation invariant function, we conclude that the transition probability of the considered CTMC permutation invariant.
We finally verify the final sampling probability, ýí (GI:D), is permutation-invarian. To simulate G over K time steps [0 = to. txx = 1], we can marginalize it first by taking the expectation over the state at the last time step tx Specifically, we have pı (G = Pi (Gig_ P1 fi (G): G )] Since the process is Markovian, this expres- sion can sequentially extended over the T steps through successive expectations.
( Bp. (aik-))
Pilex (GT-DIGtx
ix-1
E 2 (G 2)
Epec 1ltk 2 100 10t2 2) (GF
(G G 2
E (2 [.. 1lx 2 (O (o | G
Due to the fact that each function in the sequence is itself permutation invariinn and that the initial distribution po PC is permutation invariant (see Appendix C.1). the composition of cermutation-invarian functions preserves this invariance throughout. Thus, the final sampling probability is invariant over isomorphic graphs.
D.2.2. ADDITIONAL FEATURES EXPRESSIVITY
This section explains the expressivity of the RRWP features used in DeFoG. We summarize the findings of Ma et al. (2023) in Theorem 7, who establish that, by encoding random walk probabilities, the RRWP positional features can be used to arbitrarily approximate several essential graph properties when fed into an MLP. Specifically, point 1 shows that RRWP with steps encodes all shortest path distances for nodes up to K - 1 hops. Additionally, points 2 and 3 indicate that RRWP features effectively capture diverse graph propagation dynamics.
Proposition 7 (Expressivity of an MLP with RRWP encoding (Ma et al., 2023)). For any n E N, let Gn S {0, 10.1 denote all adjacency matrices of n-node graphs. For K E N, and A E Gns consider the RRWP:
P M,,,.... "MM...,,.--1 MK RaXaXK
Then, for any >
O, there exists an MLP : K- + R acting independeently across each n. dimension such that MLP(P) approximates any of the following to within e error:
1. MTP((P), R SPDK-1((.).)
2. MLP(P) = K- 0 (D) (D-1A)* A)*
3. MLP((P) x 0 + A
44

---

DeFoG: Discrete Flow Matching for Graph Generation
in which SPDK-1(i,J) is the K Iruncated shortest path distance, and 0g E R are arbitrary coefficients.
Siraudin al. (2024) experimentally validate the effectiveness RRWP features for graph diffusion models and propose extending their proof additional graph properties that GNNs fail to capture (Xu et al., 2019; Morris et al., 2019). For example, MLP with input M with & = N - -1 for an N- graph can approximate the connected component of each node and the number of vertices in the largest connected component. Additionally, RRWP features can be used to capture cycle-related information.
45

---

DeFoG: Discrete Flow Matching for Graph Generation
E. Conditional Generation
In this section, we describe how to seamlessly integrate DeFoG with existing methods for CTMC-based conditioning mechanisms. In this setting, all the examples are assumed to have a label. The objective of conditional generation is to steer the generative process based on that label, that sampling time we can guide the model to which class of samples are interested in obtaining.
We focus classifier-free guidance methods, as these models streamline training by avoiding task-specific classifiers. This approach has been widely adopted for continuous state-space models, c.g., for image generation, where it has been shown to enhance the generation quality of the generative model (Ho & Salimans, 2021; Sanchez et al., 2024). Recently, Nisonoff et al. (2025) extended this method discrete flow matching in a principled manner. In this paper, we adopt their formulation.
In this framework, 90% of the training is performed with the model having access the label of each noisy sample. This allows the model to learn the conditional rate matrix, R,] (t+dll)) In the remaining 10% of the training procedure, the labels of the samples are masked, forcing the model to learn the unconditional generative rate matrix R2 (2t, 2t+ds). The conditional training enables targeted and accurate graph generation, while the unconditional phase ensures robustness when no conditions are specified. The combination both conditional and unconditional training offers a more accurate pointer to the conditional distribution, typically descrihed by the distance between the conditional and unconditional prediction. In our framework, this pointer is defined through the ratio between the conditional and unconditional rate matrices, as follows:
R (z, Tlw)) R (xr .)
R (x, = (1,) ((x H2 (2, Ily)
where y denotes the guidance weight. In particular, the case with y corresponds to standard conditional genera- tion, while y represents standard unconditional generation. As y increases, the conditioning effect described by (2.5)))))) is strengthened, thereby enhancing the quality of the generated samples. We observed = 2.0 to be the (2.5)
best performing value for our digital pathology experiments (Appendix G.1), detailed in Tab.
Overall, conditional generation is pivotal for guiding models to produce graphs that meet specific requirements, offering
tailored solutions for complex real-world tasks. The flexibility of DeFoG, being well-suited for conditional generation, marks an important step forward in advancing this direction, promising greater adaptability and precision in future graph- based applications.
46

---

DeFoG: Discrete Flow Matching for Graph Generation
F. Experimental Details
This section provides further details on the experimental settings used the paper.
F.1. Architecture and Additional Features
Denoising Neural Architecture DeFoG's denoising neural network takes a noisy graph G, as input and predicts the clean marginal probability for each node x!(7) via Pijs pi (+GG. (-IG,) and for each edge e(f) via Pijt 0.(35) (+).,) This formula- tion boils down the graph generative task to graph-to-graph mapping. While both message-passing layers and graph transformers can be used for this task, graph transformers have empirically outperformed cessage-passing layers in graph generation (Qin et al., 2023). DeFoG thus adopts the transformer architecture of Vignac et al. (2022), using multi-head attention layers which encode node, edge, and graph-level features while preserving node permutation equivariance.
Enhancing Model Expressivity Graph neural networks, including graph transformers, have inherent limitations in their expressive power (Xu et al., 2019; Zhu et al., 2023). An usual approach to overcome the limited representation power of graph neural networks consists of explicitly augmenting the inputs with features that the networks would otherwise struggle to learn. We adopt Relative Random Walk Probabilities (RRWP) encodings that are proved to be expressive for both discriminative (Ma et al., 2023) and generative settings (Siraudin et al., 2024). RRWP encodes the likelihood of traversing from one node to another a graph through random walks of varying lengths, offering insights into graph dynamics across different hop distances. In particular, given graph with an adjacency matrix A, we generate
1 powers of its degree- normalized adjacency matrix, M D-1 A, i.e., [T, M, M2...., ...., MK-1]- We concatenate the diagonal entries of each power to their corresponding node embedding, while combining and appending the non-diagonal to their corresponding edge embeddings. In addition to their enhanced expressiveness, RRWP features are easy to compute and thus offer a notably more efficient and scalable alternative to the resource-intensive spectral and cycle features (Vignac et al., 2022) commonly employed in prior works (see Appendix G.4).
F.2. Dataset Details
F.2.1. SYNTHETIC DATASETS
Here, we describe the datasets employed in our experiments and outline the specific metrics used to evaluate model perfor- mance on each dataset. Additional visualizations of example graphs from each dataset, along with generated graphs, are provided in Figures 16 to 18.
Description We use three synthetic datasets with distinct topological structures. The first the planar dataset (Martinkus et al., 2022), which consists of connected planar graphs graphs that can be drawn plane without any edges crossing. The second dataset, tree (Bergmeister et al., 2023), contains tree graphs, which are connected graphs with no cycles. Lastly, the Stochastic Block Model (SBM) dataset (Martinkus et al., 2022) features synthetic clustering graphs where nodes within the same cluster have a higher probability of being connected.
The planar and tree datasets exhibit well-defined deterministic graph structures, while the SBM dataset, commonly used in the literature, stands out due to its stochasticity, resulting from the random sampling process that governs its connectivity.
Metrics
We follow the evaluation procedures described by Martinkus et al. (2022); Bergmeister et al. (2023), using both dataset-agnostic and dataset-specific metrics.
First, dataset-agnostic metrics assess the alignment between the generated and training distributions for specific general graph properties. We map the graphs to their node degrees (Deg.), clustering coefficients (Clus.), orbit count (Orbit), eigenvalues of the normalized graph Laplacian (Spec.), and statistics derived from a wavelet graph transform (Wavelet). We then compute the distance to the corresponding statistics calculated for the test graphs. For each statistic, we measure the distance between the empirical distributions of the generated and test sets using Maximum Mean Discrepancy (MMD). These distances are aggregated into the Ratio metric. To compute this, we first calculate the MMD distances between the training and test sets for the same graph statistics. The final Ratio metric is obtained by dividing the average MMD distance between the generated and test sets by the average MMD distance between the training and test sets. A Ratio value of is idcal, as the distance between the training and test sets represents a bound reference for the generated data's 's performance.
47

---

DeFoG: Discrete Flow Matching for Graph Generation
Next, we report dataset-specific metries using the V.U.N. framework, which assesses the proportion of graphs that are valid (V), unique (U), and novel (N). Validity is assessed based dataset-specific properties: the graph must be planar, tree, statistically consistent with an SBM for the planar, tree, and SBM datasets, respectively. Uniqueness captures the proportion of non-isomorphic graphs within the generated graphs, while novelty measures how many of these graphs are non-isomorphic to any graph in the training set.
F.2.2. MOLECULAR DATASETS
Description Molecular generation is a key real- application of graph generation. It poses a challenging task to current graph generation models their rich chemistry-specific information, involving several nodes and edges classes and leaning how to generate them jointly, and more complex evaluation pipelines. To assess DeFoG's s performance on molecular datasets, we use three benchmarks that progressively increase in molecular complexity and size.
First, we use the QM9 dataset (Wu et al., 2018), a subset of GDB9 (Ruddigkeit et al., 2012), which contains molecules with up to 9 heavy atoms.
Next, we evaluate DeFoG on the Moses benchmark (Polykovskiy et al., 2020), derived from the ZINC Clean Leads collec- tion (Sterling& & Irwin, 2015), featuring molecules with 8 to 27 heavy atoms, filtered by specific criteria.
Then, we include the Guacamol benchmark (Brown et al., 2019), based on the ChEMBL 24 database (Mendez et al., 2019). This dataset comprises synthesized molecules, tested against biological targets, with sizes ranging from 2 to 88 heavy atoms.
Lastly, we also include the ZINC250K dataset (Sterling & Irwin, 2015), which contains 249,455 molecules with up to 38 heavy atoms from 9 element types. We evaluate DeFoG's performance under the same setting of previous works (Jo et al., 2024).
Metrics For the QM9 dataset, we follow the dataset splits and evaluation metries outlined by Vignac et al. (2022). For the Moses and Guacamol benchmarks, we adhere to the training setups and evaluation metrics proposed by Polykovskiy al. (2020) and Brown et al. (2019), respectively. Note that Guacamol includes molecules with charges; therefore, the generated graphs are converted to charged molecules based on the relaxed validity criterion used by Jo et al. (2022) before being translated to their corresponding SMILES representations. The validity, uniqueness, and novelty metrics reported by the Guacamol benchmark are actually V. V.U., and V.U.N., and are referred to directly as V, V.U., and V.U.N. in the table for clarity. For ZINC250K, we adopt the standard evaluation metrics commonly used for this benchmark (see, e.g., Jo et al. (2024); Eijkelboom et al. (2024)), which comprise a subset of the metrics described above.
F.2.3. DIGITAL PATHOLOGY DATASETS
Description Graphs, with their natural ability represent relational data, are widely used capture spatial biological dependencies in tissue images. This approach has proven successful in digital pathology tasks such microenvironment classification (Wu et al., 2022), cancer classification (Pati et al., 2022), and decision explainability (Jaume et al., 2020). More recently, graph-based methods have been applied to generative tasks (Madeira et al., 2023), and an open-source dataset was made available by Madeira et al. (2024). This dataset consists of cell graphs where the nodes represent biological cells, categorized into 9 distinct cell types (node classes), and edges model local cell-cell interactions (a single class). For further details, refer to Madeira et al. (2024).
Metrics Each cell graph in the dataset can be mapped to a TLS (Tertiary Lymphoid Structure) embedding, denoted as K = i,o...., ]s]] E R6, which quantifies its TLS content. A graph G classified as having low TLS content if N1 (G) 0.05, and high TLS content if (G) 0.05. Based on these criteria, the dataset is split into two subsets: high TLS and low TLS. In prior work, TLS generation accuracy was evaluated by training generative models on these subsets separately, and verifying if the generated graphs matched the corresponding TLS content label. We compute TLS accuracy as the average accuracy across both subsets. For DeFoG, we conditionally train it on both subsets simultaneously, as described in Appendix E, and compute TLS accuracy based on whether the generated graphs adhere to the conditioning label. Additionally, we report the V.U.N. metric (valid, unique, novel), similar to what is done for the synthetic datasets (see Appendix 12.1). A graph is considered valid in this case if it is a connected planar graph, as the graphs in these datasets were constructed using Delaunay triangulation.
48

---

DeFoG: Discrete Flow Matching for Graph Generation
Table 4: Training and sampling time on each dataset.
Dataset
Min Nodes
Max Nodes
Training Time (h)
Graphs Sampled
Sampling Time (h)
Planar
64
64
29
40
0.07
Tree
64
64
8
40
0.07
SBM
44
187
75
40
0.07
QM9
6.5
10000
0.2
QM)(H)
55
10000
0.4
Moses
27
46
25000
5
Guacamol
2
88
141
10000
7
TLS
20
81
38
80
0.15
ZINC250K
38
14
10000
4.8
Table 5: Training and sampling parameters for full-step sampling (500 respectively).
1000 steps for molecular and synthetic datasets,
Train
Sampling
Conditional
Dataset
Initial Distribution
Train Distortion
Sample Distortion
(Target Guidance)
(Stochasticity)
Planar
Marginal
Identity
Polydec
0.05
50
Tree
Marginal
Polydec
Polydec
SBM
Absorbing
Identity
Identity
0,0
0.0
QM9
Marginal
Identity
Polydec
QM9(H)
Marginal
Identity
Polydec
0.05
0.0
Moses
Marginal
Polydee
Polydec
200
Guacamol
Marginal
Polydec
Polydec
0.1
300
Marginal
Identity
Polydec
0.05
2.0
ZINC250K
Marginal
Identity
Polydec
0.0
200
F.3. Resources
The training and sampling times for the different datasets explored in this paper are provided in Tab, 4. All the experiments in this work were
single NVIDIA A100-SXM4-80GB GPU.
DeFoG's memory usage matches existing diffusion models, with quadratic complexity in node number due to complete- graph modeling. Rate matrix overhead is negligible, and RRWP features are more efficient to compute than previous alternatives (Vignac et al., 2022; Xu et al., 2024), as shown Appendix G.4.
E4. Hyperparameter Tuning
The default hyperparameters for training and sampling for each dataset can be found in the provided code repository. In Tab. 5, we specifically highlight their values for the proposed training and sampling strategies (Sec. and Appendix C.1), and conditional guidance parameter (see Appendix E). As the training process is by far the most computationally costly stage, we aim to minimize changes to the default model training configuration. Nevertheless, we demonstrate the effec- tiveness of these modifications on certain datasets:
1. SBM performs particularly well with absorbing distributions, likely due to its distinct clustering structure, which differs from other graph properties. Additionally, when tested with a marginal model, SBM can achieve a V.U.N. of 80.5% and an average ratio of 2.5, which also reaches state-of-the-ar performance.
2. Guacamol and MOSES are trained directly with polydec distortion to accelerate convergence, as these datasets are very large and typically require a significantly longer training period.
3. For the tree dataset, standard training yielded suboptimal results (85.3% for V.U.N. and 1.8 for average ratio). How- ever, quick re-training using polydec distortion achieved state-of-thee-rt performance with 7 hours of training.
49

---

DeFoG: Discrete Flow Matching for Graph Generation
(a) Planar dataset.
(b) Tree dataset.
(c) SBM dataset.
Figure 16: Uncurated of dataset graphs (top) and generated graphs by DeFoG (bottom) for the synthetic datasets.
50

---

DeFoG: Discrete Flow Matching for Graph Generation
0H
OH
OH
HO
OH
(a) QM9 dataset.
(b) MOSES dataset.
(c) Guacamol dataset.
Figure 17: Uncurated set of dataset graphs (top) and generated graphs by DeFoG (bottom) for the molecular datasets.

---

DeFoG: Discrete Flow Matching for Graph Generation
(a) Low TLS dataset.
High TL.S dataset.
Figure 18: Uncurated set of dataset graphs (top) and generated graphs by DeFoG (bottom) for the TLS dataset.
52

---

DeFoG: Discrete Flow Matching for Graph Generation
G. Additional Results
First, we discuss conditional generation for real-world digital pathology graph generation. Next, we provide comprehensive tables detailing results on synthetic datasets Appendix G.2. Then, Appendix G.3 focuses on molecular generation tasks, including results for the QM9 dataset and the full tables for MOSES and Guacamol, Finally, in Appendix G.4, we analyze the time complexity of various additional features that enhance expressivity in graph diffusion models.
G.1. Conditional Generation
Setup Tertiary Lymphoid Structure (TLS) graph datasets have been recently released with graphs built from digital pathology data (Madeira et al., 2024). These graphs are split into two subsets low TLS and high TLS - based on their TLS content, biologically informed metric reflecting the cell organization in the graph structure. Previously, models were trained and evaluated separately for each subset. To demonstrate the flexibility of DeFoG, we conditionally train it across both datasets simultaneously, using the low/high TLS content as a binary label for each graph. More details on the used conditional framework in Appendix E.
Table 6: TLS conditional generation results.
TLS Dataset
Model
V.U.N.
ILS Val.
Train set
0.0
100
GraphGen (Goyal et al., 2020)
40.2a18
25.1
BIGG (Dai et al., 2020)
0.6:14
16.7+16
SPECTRE (Martinkus et al., 2022)
7.9
25.3an8
DiGress+ (Madeira et al., 2024)
13.2+34
12.6250
ConStruct (Madeira al., 2024)
92.1413
DeFoG steps = 50)
44.5.4.
93.0s56
DeFoG steps = 1,000)
94.5
95.8e1.5
We evaluate two main aspects: first, how frequently the conditionally generated graphs align with the provided labels (TLS Validity); and, second, the validity, uniqueness, and novelty the generated graphs (V.U.N.). Graphs are considered valid if they are planar and connected. For comparison, we report the average results of existing models across the two subsets, as they were not trained conditionally.
From Tab. 6, DeFoG significantly outperforms the unconstrained models (all but ConStruct). Notably, we out- perform ConStruct on TLS validity with even 50 steps. For V.U.N., while ConStruct hard-constrained achieve 100% graph planarity, making strongly biased toward high validity, DeFoG remarkably approaches these values without relying on such rigid constraints.
Results
G.2. Synthetic Graph Generation
In Tab. 7, present the full results for DeFoG for the three different datasets: planar, tree, and SBM.
53

---

DeFoG: Discrete Flow Matching for Graph Generation
Table 7: Graph Generation Performance on Synthetic Graphs. We present the results of DeFoG across five sampling runs, each generating graphs, reported as mean standard deviation. The remaining values are obtained from Bergmeister al. (2023). Additionally, we include results for Cometh (Siraudin al., 2024) and DisCo (Xu al.. 2024). For the average ratio computation, adhere to the method outlined by (Bergmeister et al., 2023), excluding statistics where the training set MMD is zero.
Model
Deg.
Clus.
Orbit J
Spec. 4
Wavelet J
Rati
Valid
Unique
Novel |
V.U.N.
0.0300
0,0038
0,0112
100
100
G (You et 2018)
0.009
0.2779
1,2543
010459
0.1034
400.2
0.0
100
100
0.0
GRAN (Lino 2019)
0,0007
0.0426
0.0075
0.0019
2.0
97.5
85.0
2.5
SPECTRE (Martinkus et al., 2022)
0.0005
0.0785
0.0012
0.0112
0,0059
3.0
25.0
100
100
25.0
DiGress (Vignac 2022)
0.0780
0.0079
0.0099
0.0031
5.1
77.5
100
EDGE (Chen al., 2023)
0.0761
0.3229
0.7737
0.0957
0,3627
431.4
0.0
100
100
0.0
BwR (Diamunt 2023)
0.0231
0.2596
0.5473
0,0111
0.1314
251.9
0.0
100
100
BiGG (Dai al., 2020)
0.0007
0.0570
0.0367
0.0105
0,0052
16.0
62.5
85.0
42.5
5.0
GraphGen (Goyal 2020)
0.0328
0.2106
0.1236
0
0.0989
210.3
7.5
100
100
7,5
HSpectre (onc-shot) (Bergmeister al., 2023)
0.0245
0,0006
0.0104
0,0030
1.7
67.5
100
100
67.5
HSppectr (Bergmeister
2023)
0.0005
0.0626
0.0017
0.0075
0.0013
2.1
95.0
100
100
95.0
GruM (Jo al., 2024)
0.0004
0.000
0,0002
0.0104
0.0020
1.8
90.0
CatPlow (Fijkelboom ol., 2024)
0.0003
0,0403
0,0008
80.0
DisCo at... 2024)
auotes
83.6
w/o
Cometh- PC (Sirandin al., 2024)
0,0006 40000
0.0434 woomn
0.0016 -0006
0.0049-a0ee
99.5 +0
100.0
100.0 w08
99.5
4u01-9
-2000
Tree Dataser
100
GRAN (Lino et al., 2019)
0.1884
0.0080
0.0199
0.2751
0.3274
607.0
0.0
100
100
0.0
(Vignac 2022)
90.0
100
EDGE (Chen al., 2023)
0.2678
0,0000
0.7357
0.2247
0,4230
850.7
0.0
7.5
100
0.0
(Diamant
BiGG (Dai sl., 2020)
0.0014
0.0000
0,0000
0.0119
0.0058
5.2
100
87.5
50.0
75.0
GraphGen (Goyal al., 2020)
100
HSpectre (onc-shot) (Bergmeister et al., 2023)
0.0004
0.0000
0,0000
0.0080
0.0055
2.1
82.5
100
100
82.5
HSpectre (Bergmeister ol., 2023)
010001
0,01177
100
100
DeFoG
0.0002 10000
0.0000 20000
0.0000 a00000
0.0108 aAиiS
0.0046 2004
166 214
96.5
100.0
100.0 208
96.5
Stochastic Model (neas
Ruy
Model
Deg.
Clus.
Orbit
Spec. 4
Wavelet
Rati
Valid
Unique
Novel
V.U.N.
Training sot
0.0332
0.0027
85.9
GraphRNN (You 2018)
0.0055
0.0581
0.0785
0.0065
0.0431
14.7
5.0
100
100
5.0
GRAN 2019)
DO053
0.0054
25.0
100
SPECTRE (Mastinkus et al., 2022)
0.0015
0.0521
0.0112
0.0056
0.0028
2.2
52.5
100
100
52.5
DiGress (Vignac 2022)
0,0045
0.0144
600
100
EDGE (Chen al., 2023)
0.0279
0.1113
0.0854
0.0251
0.1500
51.4
0.0
100
100
0.0
BwR (Diamant 2023)
00633
0.01699
BiGG (Dai al., 2020)
0.0012
0.0044
0.0667
0.0059
0,0370
11.9
10.0
100
100
10.0
GraphGen (Goyal 2020)
0.0550
0.0623
0.1189
0,0182
0.1193
48.8
5.0
100
100
5.0
HSppecte (ome-shot) (Bergmeister al., 2023)
0.0141
0.0528
0.0809
0.0071
0.0205
10.5
75.0
100
100
75.0
HSppccre (Bergmeister
2023)
19
0.05
0.0669
0.0067
0.0219
10.2
45.0
100
100
45.0
GruM (Jo al., 2024)
0.0015
0.0589
0.0150
0.0077
0.0812
1.1
85.0
CalFlow (Eijkelloom al., 2024)
0.0012
0,0988
0.0357
85.0
DisCo (Xu 2024)
0.0006 a0000
0.0266 monss
0.0510 200123
66.2 21.
100.0 ab0)
100.0 208
66.2 11A
Cometh (Sirmdiin 2014)
0,0020
0.0498
0.0333
0,0024
75.0
100.0
100.0
75.0
DeFoG
0.0006 a0.025
0.0517 s0001
0,0566 s00733
20/012
0.0080 28 0004
=5
90.0
90.0 as1
90.0 2511
54

---

DeFoG: Discrete Flow Matching for Graph Generation
G.3. Molecular Graph Generation
For the molecular generation tasks, we begin by examining the results for QM9, considering both implicit and explicit hydrogens (Vignac al., 2022). In the implicit case, hydrogen atoms inferred to complete the valencies, while in the explicit case, hydrogens must be explicitly modeled, making it inherently more challenging task. The results presented in Tab. 8. Notably, DeFoG achieves training set validity in both scenarios, representing the theoretical maximum. Furthermore, DeFoG consistently outperforms other models in terms of FCD. Remarkably, even with only 10% of the sampling steps, DeFoG surpasses many existing methods.
Table Molecule generation on QM9. We present the results over five sampling runs of 10000 generated graphs each, in the format mean standard deviation. We include the results of Relaxed Validity, which accounts for charged molecules facilitate comparison, different methods may report varying types of validity.
Without Explicit Hydrogenes
With Explicit Hydrogenes
Model
Valid
Relaxed Valid
Unique
FCD
Valid
Relaxed Valid
Unique t
FCD 4
Training set
99.3
99.5
99.2
0.03
97.8
98.9
99.9
0.01
SPECTRE (Martinkus al., 2022)
87.3
35.7
GraphNVP (Madhawa et al., 2019)
83.1
99.2
GDSS (Jo et al., 2022)
95.7
98.5
2.9
DiGress (Vignac et al., 2022)
99.0.a.
96.240.1
95.4+1.1
97.6.04
GruM(Jo al. 2024)
99.2
96.7
0.11
CafFlow(jjjkclooom al., 2024)
99.8
100.0
0.44
DisCo (Xu al., 2024)
99.3
Cometh (Siraudin al., 2024)
99.6.a11
96.8st.2
0.25 s001
DeFoG (# sampling steps 50)
98.9
99.2
96.2+n.2
0.26=0.0
97.1-0a
98.0
94.8-0.0
0.3
DeFoG sampling steps 500)
99.3a00
99.420.1
96.3an.3
0. 12.2.0000
98.020.
98.8.00
96.0
0.0520.00
Additionally, we provide the complete version of Tab. presenting the results for MOSES, Guacamol and ZINC250K datasets separately in Tab. 9, Tab. 10 and Tab. 11, respectively. We include models from classes beyond diffusion models to better contextualize the performance achieved by DeFoG. We analyze the performance of diffusion and flow-based methods on MOSES and Guacamol in the main paper (see Sec. 5.1). Here, we focus on the same analysis for ZINC550k. As shown in Tab. 11, DeFoG achieves state-of-the-ar performance on this benchmark. Notably, it also attains superior FCD scores with only 50 sampling steps, surpassing existing diffusion and
methods.
Table 9: Molecule generation on MOSES.
Model
Class
Val.
Unique.
Noveltyt
Filters
FCD
SNN
Scaf ?
Training set
100.0
100.0
0.0
100.0
0.01
0.64
99.1
VAE (Kingma & Welling, 2013)
Smiles
97.7
99.8
69.5
99.7
0.57
0.58
5.9
TAE (Jin et al., 2018)
Fragment
100.0
100.0
99.9
1.00
0.53
GraphInvent (Mercado et al., 2021)
Autoreg.
96.4
99.8
95.0
1.22
0.54
12.7
DiGress (Vignac et al., 2022)
Onc-shot
85.7
100.0
95.0
97.1
1.19
0.52
14.8
DisCo (Xu et al., 2024)
One-shot
88.3
100.0
97.7
95.6
1.44
0.50
15.1
Cometh (Siraudin al., 2024)
One-shot
90.5
99.9
92.6
99.1
1.27
0.54
16.0
DeFoG (# sampling steps 50)
One-shot
83,9
99.9
96.9
96.5
1.87
0.50
23.5
DeFoG (# sampling steps 500)
One-shot
92.8
99,9
92.1
98.9
1.95
0.55
14.4
55

---

DeFoG: Discrete Flow Matching for Graph Generation
Table 10: Molecule generation on GuacaMol. We present the results over five sampling runs of 10000 generated graphs each, in the format mean + standard deviation.
Model
Class
Val.
V.U. f
V.U.N.
KT. divd
FCD
Training set
100.0
100.0
0.0
99.9
92.8
LSTM (Hochreiter & Schmidhuber, 1997)
Smiles
95.9
95.9
87.4
99.1
91.3
NAGVAE (Kwon al., 2020)
One-shot
92.9
88.7
88.7
38.4
0.9
MCTS (Brown al., 2019)
One-shot
100.0
100.0
82.2
DiGress (Vignac et al., 2022)
One-shot
85.2
85.2
85.1
92.9
68.0
DisCo (Xu et al., 2024)
One-shot
86.6
86.6
86.5
92.6
59.7
Cometh (Siraudin al., 2024)
One-shot
98.9
98.9
97.6
96.7
72.7
DeFoG (# steps = 50)
One-shot 91.7
91.7
91.2
92.3
57.9
DeFoG (# steps 500)
One-shot
99.0
99.0
97.9
97.7
73.8
Table 11: Molecular generation on ZINC250K dataset.
Model
Val.
Uniqueness
FCD 4
NSPDK 1
Scaffold
GruM (Jo et al., 2024)
98.65
2.257
0.0015
0.5299
GBD (Liu et al., 2024)
97.87
2.248
0.0018
0.5042
CatFlow (Eijkelboom al., 2024)
99.21
100.00
13.211
DeFoG (50 steps)
96.65#0.1
99,99+0.01
2.12300.029
0.0022+0.0001
0.4245=00.000
DeFoG
99.2210.08
99.99a0.01
1.425e0.022
0.000840.0001
0.5903=0.0099 0099
56

---

DeFoG: Discrete Flow Matching for Graph Generation
Table 12: Performance comparison of RRWP-based graph encoding within the DiGress framework.
Method
Planar
SBM
QM9
V.U.N. f
Ratio 1
V.U.N.
Ratio
Valid
Unique
FCD
DiGress
77.5
5.1
60.0
1.7
99.0 + 0.0
96.2 011
DiGress (RRWP)
90.0
4.0
70.0
1.7
99.1
96.6 :: 0.2
DeFoG (RRWP, 50 steps)
95.0 3.2
3.2 - 1.1
86.5 - 5.3
2.2 = 0.3
98.9
96.2 :.2
0.26 + 0.00
DeFoG (RRWP)
99.5 + 1.0
1.6 + 0.4
90.0 + 5.1
4.9 + 1.3
99.3 + 0.0
96.3 + 0.3
0.12 + 0.00
Table 13: Computation time for different additional features. The RRWP features are computed with 12 steps.
Datasct
Min Nodes
Max Nodes
RRWP (ms)
Cycles (ms)
Spectral (ms)
Moses
8
27
0.6
1.2
2.5
Planar
64
64
0.5
1.2
93.0
SBM
44
187
0.6
2.7
146.9
G.4. Impact of Additional Features
In graph diffusion methods, the task of graph generation is decomposed into a mapping of graph to a of marginal probabilities for each node and edge. This problem is typically addressed using Graph Transformer architecture, which augmented with additional features to capture structural aspects that the base architecture might struggle to model effectively (Vignac et al., 2022; Xu et al., 2024; Siraudin et al., 2024) otherwise.
In this section, we evaluate the impact of using RRWP encodings as opposed to the spectral and cycle encodings (up to 6-cycles) proposed in DiGress (Vignac et al., 2022).
In Tab. 12, we present performance comparison of these two variants across three datasets: QM9, Planar, and SBM. The results show that RRWP achieves comparable superior performance within the DiGress framework, validating its effec- tiveness as graph encoding method. Notably, despite these improvements, DiGress's performance remains significantly below that of DeFoG on the Planar and SBM datasets, while achieving similar validity and uniqueness on the QM9 dataset.
To further demonstrate the impact of using RRWP on sampling efficiency, we compare the performances of DeFoG, DiGress, and DiGress augmented with RRWP (replacing the original additional features) across a varying number of sampling steps. These results are shown in Figure
We observe that, while RRWP provides improvements the Planar and SBM datasets with fewer generation steps, it is still significantly outperformed by the optimized DeFoG framework. This highlights that although RRWP is efficient and effective graph encoding method, the primary performance gains of DeFoG stem from its continuous-time formulation featuring fully decoupled training and sampling stages.
We then perform a time complexity analysis of these methods. While both cycle and RRWP encodings primarily involve matrix multiplications, spectral encodings require more complex algorithms for eigenvalue and eigenvector computation. As shown in Tab. 13, cycle and RRWP encodings are more computationally efficient, particularly for larger graphs where eigenvalue computation becomes increasingly costly. These results also support the use of RRWP encodings over the combined utilization of cycle and spectral features.
For the graph sizes considered in this work, the additional feature computation time remains relatively small compared to the model's 's forward pass and backpropagation. However, as graph sizes increase a direction beyond the scope of this paper - this computational gap could become significant, making RRWP a suitable encoding for scalable graph generative models.
57

---

DeFoG: Discrete Flow Matching for Graph Generation
75
DiGress DiGres(RRWV)
Validity (QMA9)
90
Novelty (QM9)
60
DeFoGi
DiGress
DiGress DiGressRRWW
DeFoG
30
100
1000
10
50
100
500
Steps
Steps
(a) QM9 dataset.
V.U.N, (Planar)
0.9
Ratin (Planar)
251
0.6
0.3
6
0.0
10
50
100
1000
50 Steps
100
1000
# Steps
(b) Planar dataset.
V.U.N. (SBM)
0.75
Ratio (SBM)
32
0.50
10
0.25
0.00
5
50
100
1000
10
100
1000
# Steps
Steps
SBM dataset.
Figure 19: Impact of RRWP features for sampling efficiency.
58


Reviews:
[{"review_id": "PUf5qjaHmY", "reviewer": "Reviewer_kmNp", "summary": "The authors apply discrete flow matching to graph generation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. We address the raised concerns below:\n\n**Claims And Evidence**. \n\nWe agree with the reviewer that the training-sampling disentanglement is a contribution of DFM. In this regard, our contribution lies in making this decoupling effective for graph generation, where it had not been previously formulated, implemented, or empirically validated (as acknowledged in lines 145–150). Crucially, notice that applying existing DFM methods to graphs does not lead to improved performance (see Fig. 2 ablations). DeFoG addresses this by providing a graph tailored formulation that *effectively* leverages the decoupling between training and sampling, resulting in significant improvements in both sampling flexibility and efficiency.\n\nWe understand that the original phrasing could be misleading and so we propose the revised formulation:\n```\nWe introduce DeFoG, a novel graph generative model that effectively exploits the training-sampling decoupling inherited from its flow-based formulation, significantly enhancing sampling flexibility and efficiency.\n```\nWe hope this effectively addresses the reviewer’s concerns and remain available for further discussion.\n\n**Theoretical claims**:\n\n- Our Corollary 1 does not relate to the CTMC sampling error. Instead, it establishes that minimizing the CE loss directly corresponds to minimizing an upper bound on the rate matrix estimation error, directly promoting accurate sampling. This justifies the use of the CE loss without requiring ELBO-derived approximations (more on this below).\n\n- Corollary 2 is not solely about the discretization error resulting from the CTMC sampling - which, as correctly noted by the reviewer is $O(\\Delta t)$ (same as $O(h)$). Instead, it combines this term with the estimation error that results from Corollary 1 to bound the deviation of the generated graph distribution. Notice that this type of result is commonly sought in generative modeling to guarantee generation accuracy. For instance, Theorem 1 in [5] presents an analogous bound in the context of discrete diffusion, though with significant differences (e.g., they assume a bounded rate matrix estimation error, while we explicitly prove it).\n\nRegarding the connection between DeFoG’s loss (CE) and ELBO, [1] derives an ELBO loss suitable to our chosen rate matrices (decomposed into three terms weighted CE, KL divergence, rate matrix regularizer). However, they motivate using only the CE loss based on approximations upon the derived ELBO by dropping the rate matrix-dependent terms (see App. C.2 from [1]). In contrast, our bounds do not require such simplifications and are agnostic to rate matrix design choices (e.g., stochasticity level), reinforcing our training-sampling decoupling claim. Additionally, [2], which is a contemporaneous submission under ICML guidelines (alongside [3]), also establishes an ELBO loss; however, on our understanding, it applies to a different family of conditional rate matrices. \n\nWe have included the discussion above, as well as the mentioned references, into the revised manuscript. We hope this clarifies the raised concern; if not, we remain open to further feedback.\n\n**Questions For Authors**: \n\nWe use $x^{(n)}$ for the $n$-th node ($1 \\leq n \\leq N$) and $e^{(ij)}$ for the edge between nodes $x^{i}$ and $x^{j}$ ($1 \\leq i < j \\leq N$). Nodes are gathered as $x^{1:n:N}$, edges as $e^{1:i<j:N}$. Node and edge state spaces are denoted by $\\mathcal{X}$ and $\\mathcal{E}$ (cardinalities $X$, $E$, respectively), meaning nodes take values in $\\\\{ 1,\\dots,X \\\\}$ and edges in $\\\\{ 1,\\dots,E \\\\}$. Following standard practice in the field [6,7,8], we keep the number of nodes fixed throughout trajectories and explicitly model a complete graph, connecting all node pairs by edges. During diffusion trajectories, only node and edge classes change, not their structural existence. Crucially, one of the edge classes represents the absence of an edge (\"non-existing” edge), but there is no “non-existing” class for nodes. Hence, each edge is always associated with its two vertices (there can be “floating” nodes, but no “floating edges”). We thank the reviewer for raising this important remark; we have made this more explicit in the updated manuscript.\n\nOverall, we appreciate the reviewer’s constructive feedback, and we think their questions improved our work. We remain open to any further suggestions.\n\n\n[5] - A Continuous Time Framework for Discrete Denoising Models, Campbell et al., NeurIPS 2022\n\n[6] - Digress: Discrete denoising diffusion for graph generation, Vignac et al., ICLR 2023\n\n[7] - Discrete-state Continuous-time Diffusion for Graph Generation, Xu et al., NeurIPS 2024\n\n[8] - Cometh: a Continuous-time Discrete-state Graph Diffusion Model, Siraudin et al., ArXiv 2024", "claims_and_evidence": "Claimed contribution 1:\n> We introduce DeFoG, a novel flow-based graph generative model that effectively disentangles training and sampling for improved flexibility and efficiency;\n\nI feel this is misleading. DFM already decouples training and sampling (see [1] and [2]).\n\nIn fact, the authors themselves dismiss their own contribution later in the introduction (lines 145 to 147): \"While the DFM paradigm enables training-sampling disentanglement, it lacks a complete formulation and empirical validation on graph data. [...]\".\n\nI will happily adjust my score if the authors adjust their claims, or can provide a convincing argument that the reasoning above is incorrect.\n\n[1] https://arxiv.org/abs/2402.04997\n\n[2] https://arxiv.org/abs/2412.03487\n\n[3] https://arxiv.org/abs/2412.06264\n\n[4] https://arxiv.org/abs/2407.15595", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Somewhat.\n\n> Corollary 1 and 2\n\nI don’t fully understand the need for these statements, given what is already known about sampling errors in the CTMC literature. Is having $O(\\Delta t)$ error any different from the usual $O(h)$ error from using Euler’s method (see [2], [3] and [4])? To be more specific: the DeFoG loss is an evidence lower bound (ELBO) (see [2]).", "experimental_designs_or_analyses": "The experiments make sense.", "relation_to_broader_scientific_literature": "This relates to the flow matching, as well as graph generation, literature.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "See other boxes.", "other_comments_or_suggestions": "See other boxes.", "questions_for_authors": "> 3.1. Learning Discrete Flows over Graphs\n\nThe notation in this section is a bit odd. It seems like the node and edge sets are completely unrelated? Both nodes and edges are integers. I would expect the edge set to be something like $\\mathcal{X}^2$.\n\nGiven the definition of $p_{t|1}$ in this section, it is theoretically possible to have “floating” edges at any time t. In other words, edges that are not connected to any nodes. Is this correct?", "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": "rkn9YoDadX", "reviewer": "Reviewer_8xvx", "summary": "The authors adapt discrete flow matching for graph generation, replacing the usual SOTA discrete diffusion framework. This authors also utilize the flexibility of flow matching to further tune the sampling process to make it more efficient and generate higher quality samples in much fewer steps. This is primarily achieved by tuning the influence of target guidance and sample distortion (de-noising schedule)", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback, as well as for recognizing the importance of our algorithmic improvements, the thoroughness of our experimental validation, and the practical value of our contributions to the graph generation community. Aligned with the reviewer's perspective, we are committed to releasing a clean, well-documented, and easy-to-use codebase upon publication to facilitate adoption and further developments by the community.\n\nWe remain open to any further suggestions or questions that may arise.", "claims_and_evidence": "The authors perform extensive benchmarks and ablation studies. They clearly support their claims of improved efficiency and sample quality.", "methods_and_evaluation_criteria": "Authors rely on well established benchmarks for graph generation with standard datasets and metrics that match best practices in the literature.", "theoretical_claims": "I didn't check the proofs/derivations in the appendix in detail, but the theory in the paper heavily relies on previous established works and looks sound.", "experimental_designs_or_analyses": "All the experimental design is quite standard and looks good. The experiments and ablations are extensive and cover all introduced modifications", "relation_to_broader_scientific_literature": "The paper tackles a very important and widely studied problem of graph generation. It builds on the SOTA approaches (discrete diffusion) changing the diffusion framework with discrete flow matching. While the model is overall similar to previous discrete diffusion approaches and while discrete flow matching has been used in other contexts before, the multiple various minor improvements presented in the paper, do noticeably improve upon existing SOTA. The potential choices are extensively experimentally evaluated, which is very valuable for the community, extending our knowledge of how best to build these graph generative models in practice. If the paper comes with a nicely written and easy to work with and understand codebase I can see it becoming a go-to graph/molecule generative model people develop upon, replacing DiGress in this role, that is currently used as a main building block in variety of graph and molecule generation papers.", "essential_references_not_discussed": "References look good to me.", "other_strengths_and_weaknesses": "I already covered the main strengths and weaknesses above. While novelty is not super high, as it's just a combination of existing ideas, not straying off the common path, I think it's a very valuable work in that it does a great job refining this current standard recipe and noticeably improving the resuls.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "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": "7Q7j36TPwF", "reviewer": "Reviewer_2q2N", "summary": "This paper proposed a novel graph generative model via discrete flow matching. This framework provides flexible and efficient training and sampling methods. The paper also provides theoretical guarantee for this disentanglement framework. With rich empirical validation, the proposed DeFoG shows powerful modeling ability and robust generation quality.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback. Below, we address the raised concerns in detail.\n\n**Essential Reference**:\nWe thank the reviewer for proposing this interesting reference. We will expand our related work section to include a discussion over methods that support both continuous and discrete data. Specifically, we propose to integrate the following in the revised manuscript:\n\n```\nIntegrating continuous and categorical data within graph generative models is an important challenge, as many real-world applications involve heterogeneous data types (e.g., molecular graphs containing atomic coordinates alongside categorical atom and bond types). A recent example addressing this challenge is GBD [1], which incorporates beta diffusion to jointly model both continuous and discrete variables. Similarly, DeFoG is amenable to formulations involving mixed data types by leveraging an approach akin to MiDi [2], independently factorizing continuous and discrete variables. However, explicitly exploring this integration is beyond the scope of this work.\n```\n\n**Results on ZINC250 dataset**: \nTo further support our empirical findings on real-world datasets, we provide results on the ZINC250k. We evaluate DeFoG’s performance on this dataset after 14 hours of training under the same setting of previous works [3] and compare it, to the best of our knowledge, against the strongest-performing methods currently reported in the literature [1,3,4].\n\n| Model | Validity ($\\uparrow$) | Uniqueness ($\\uparrow$) | FCD ($\\downarrow$) | NSPDK ($\\downarrow$) | Scaffold ($\\uparrow$) |\n|---|---|---|---|---|---|\n| GruM | 98.65 | - | 2.257 | 0.0015 | 0.5299 |\n| GBD | 97.87 | - | 2.248 | 0.0018 | 0.5042 |\n| CatFlow | 99.21 | **100.00** | 13.211 | - | - |\n| DeFoG (50 steps) | 96.65 ± 0.16 | 99.99 ± 0.01 | 2.123 ± 0.029 | 0.0022 ± 0.0001 | 0.4245 ± 0.0109 |\n| DeFoG | **99.22** ± 0.08 | 99.99 ± 0.01 | **1.425** ± 0.022 | **0.0008** ± 0.0001 | **0.5903** ± 0.0099 |\n\nDeFoG accomplishes state-of-the-art performance for this dataset. Notably, it also attains superior FCD performance using only 50 sampling steps, outperforming existing methods. We thank the reviewer for suggesting the ZINC250k benchmark. These results further demonstrate DeFoG’s generalization capabilities in molecular graph modeling, strengthening our contribution, and, thus, have been included into the updated manuscript.\n\n**Standard Deviation for Synthetic Graphs** In the Experiments section, we report VUN and the average ratio of MMDs for all the synthetic datasets, with both mean and standard deviation (std). We can observe DeFoG’s stable performance, in particular for a large number of steps. Additionally, we provide the full results for all the original graph-specific metrics, including Degree, Orbit, Wavelet, Spectral, and Cluster MMDs, with mean and std, in Table 7.\n\n**Sampling Distortion** The original DFM paper [6] considers evenly spaced sampling timesteps without any distortion. In contrast, we investigate how breaking this uniformity can yield more refined generative trajectories, especially at timesteps crucial for capturing specific graph properties.\nOur results (Sec. 5.3 – Sampling Distortion) demonstrate that, for graphs with strict structural constraints (e.g., planarity), it is beneficial to emphasize refinement at later steps, as categorical variables may abruptly transition as $t \\rightarrow 1$, potentially violating the required structure. Refining these late steps thus helps detect and correct such errors. Conversely, for datasets without strict constraints (e.g., SBM), this refinement is not necessary.\nMoreover, we provide insights into the interplay between training and sampling distortions, observing that aligning these distortions typically yields the best generative performance, although this is not universally true. We also propose a simple heuristic to determine the optimal sampling distortion (see App C.2.).\nFinally, similar beneficial effects of distorted scheduling have been reported for other data modalities, such as image generation and language modeling [6].\n\nOverall, sampling distortion allows us to exploit DeFoG's training-sampling decoupling to further enhance generative performance by adapting the generative process to different graph characteristics, refining the corresponding crucial timesteps.\n\n[1] - Advancing Graph Generation through Beta Diffusion, Liu et al., ICLR 2025\n\n[2] - Midi: Mixed graph and 3d denoising diffusion for molecule generation, Vignac et al., ECML-PKDD 2023\n\n[3] - Graph Generation with Diffusion Mixture, Jo et al., ICML 2024\n\n[4] - Variational Flow Matching for Graph Generation, Eijkelboom et al., NeurIPS 2024\n\n[5] - Digress: Discrete denoising diffusion for graph generation, Vignac et al., ICLR 2023\n\n[6] - Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design, Campbell et al., ICML 2024\n\n[7] - Discrete Flow Matching, Gat et al., NeurIPS 2024", "claims_and_evidence": "The paper is easy to follow and extensive experiments demonstrate its effectiveness on graph modeling.", "methods_and_evaluation_criteria": "The proposed method follows the widely used evaluation process.", "theoretical_claims": "I verified that the sampling and training algorithms are consistent with Equations 4 and 5.\nFor the permutation invariance in graph modeling, I check the Appendix D.2.1 and the derivation is correct.", "experimental_designs_or_analyses": "This paper provides rich experiments to validate its powerful graph modeling ability. The high V.U.N. performance on general graph shows its robustness in generation quality. This paper also conducted extensive ablation on training and sampling efficiency.", "relation_to_broader_scientific_literature": "Graph generation has always been a meaningful topic in machine learning / generation tasks and it has a broader impact on scientific discovery. This paper provides a practical implementation in graph modeling and theoretical foundation for this as well.", "essential_references_not_discussed": "This paper has discussed many related works in diffusion / flow matching based graph generative models. Recently I notice an interesting graph modeling method, which applies beta diffusion on graph modeling. I think the author could discuss it a little bit because the beta diffusion can handle both of continuous and discrete elements in graph, while your method aims to disentangle the graph modeling process with flexible training and sampling method.\n- Advancing Graph Generation through Beta Diffusion ICLR'25", "other_strengths_and_weaknesses": "## Strengths\n- Well discussion of related literature and connection to previous results.\n- Important and useful empirical / theoretical results and their discussion.\n- Extensive discussion about related works on continuous-time discrete diffusion and discrete flow matching. \n- Sufficient analysis on sampling optimization.\n\n## Weaknesses\n- Could you provide some results on ZINC250k, I think this benchmark is important for molecule graph modeling task.\n- Could you provide mean and standard deviation for synthetic graph generation. I'd like to know how stable the proposed method is.", "other_comments_or_suggestions": "How is the sampling distortion specific to the graph modeling, instead of usage in DFM.", "questions_for_authors": "All of my questions are above.", "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": "QYrhrbWBsy", "reviewer": "Reviewer_kK3Q", "summary": "This paper introduces **DeFoG**, a novel **graph generative framework** that decouples the **training and sampling** processes to improve efficiency and flexibility. The key innovation is the **discrete flow-matching (DFM) formulation**, which ensures **node permutation equivariance** and allows more expressive sampling methods tailored for graph structures. The paper provides **theoretical guarantees** linking training loss optimization to improved sampling dynamics. Extensive experiments across synthetic, molecular, and digital pathology datasets show that DeFoG achieves **state-of-the-art performance**, significantly reducing the required number of refinement steps compared to graph diffusion models.\n\nThe main contributions of the paper are:\n- **A novel training-sampling disentanglement framework** for graph generative models.\n- **Theoretical justification** demonstrating that DeFoG faithfully replicates ground truth graph distributions.\n- **Exploration of novel sampling strategies**, improving efficiency while maintaining performance.\n- **Empirical validation** across various datasets, demonstrating superior performance compared to existing diffusion models.\n\n## update after rebuttal\nThe authors have addressed my concerns, so I raise my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for positively assessing our framework’s novelty, theoretical grounding, and empirical results. Below, we address the raised concerns:\n\n**I - Methods And Evaluation Criteria**:\n1) *Hyperparameters sensitivity*: In the paper, we perform extensive hyperparameter sensitivity analyses covering $R^\\omega$, $R^\\text{DB}$, target guidance, stochasticity level, initial distributions, and training-sampling distortion (Sec. 5.3, App. B.1–B.4, C.1–C.2, Figs. 9, 10, 13, 14), as acknowledged by Reviewers 8xvx and 2q2N. These analyses sufficiently cover the key factors affecting generation and we provide supporting intuitions (Sec. 3.2, 5.3).\n2) *Computational trade-offs*: We report training/sampling runtimes for DeFoG across datasets (App. F.3) and compare them with SOTA methods in Sec. 5.2. Note that step count scales linearly with runtime. Regarding memory usage, we propose to clarify in App. F.3:\n```\n\"DeFoG’s memory usage matches existing diffusion models, with quadratic complexity in node number due to complete-graph modeling. Rate matrix overhead is negligible, and RRWP features are more efficient to compute than previous alternatives [3,4].\"\n```\n\n**II - Theoretical Claims**:\n1) Whether \"noise schedules\" refers to the choice of initial distribution or distortion functions, our theoretical results explicitly link training loss to sampling accuracy. Strong empirical results validate the practical relevance of these results, and the observed performance deterioration with fewer sampling steps confirms the theoretical predictions (Tables 1,2; Figs. 7,8,11,12).\n\n**III - Experimental Designs Or Analyses**:\n1) *Scalability*: We believe our efficiency claims are well-supported: DeFoG reduces sampling steps to 5–10% of the original total (Tables 1,2) and uses more efficient additional features (Table 12). Moreover, DeFoG's memory usage matches existing diffusion models (see I.2), enabling similar graph scales as competing methods. Scaling these methods to larger graphs is an interesting and challenging problem by itself (e.g., [5] leverages sparsity to scale existing graph diffusion models, an approach also applicable to DeFoG), thus beyond this work's scope.\n2) *Ablations*: See I.1.\n3) *OOD Generalization*: Unlike conventional OOD tasks, graph generation typically aims to maintain distributional similarity [3,4] rather than handle distributional shifts. Thus, while an interesting direction, it is beyond our scope. For standard generalization, see VII-2.\n\n**IV - Supplementary Material**:\n1) We ensure reproducibility via the provided code and detailed hyperparameters (App. B.4, F.4).\n\n**V - Broader Literature**:\n1) *Graph flows/autoregressive models:* We extensively discuss key autoregressive models (GraphRNN, GRAN, BiGG, GraphGen) (Sec.4, App.A.1, Table 1). Regarding normalizing flows, we acknowledge their relevance (Sec. 4) but are unaware of recent graph-specific advances directly relevant to our work; any suggestions are welcome.\n\n**VI - Essential References**:\n1) We included [1] in our related work, where we already discuss similar (autoregressive) models.\n2) [2] is only a tutorial description on generative models for molecular graphs. Arguably, it is not an “essential reference'' on graph generative models. In case this was not a mistake, we kindly invite the reviewer to motivate this request.\n\n**VII - Other Strengths And Weaknesses**:\n1) *Scalability*: See III.1.\n2) *Generalization*: DeFoG generalizes across diverse domains (synthetic, molecular, digital pathology), going beyond typical benchmarks in graph generation studies [4,5]. The additional ZINC250k results requested by Reviewer 2q2N further support this, making our generalization analysis comprehensive.\n3) *Hyperparameter studies*: See I.1\n\n**VIII - Other Comments or Suggestions**:\n1) *Efficiency*: DeFoG incurs no additional overhead per sampling step (Alg. 2), and RRWP features are computed more efficiently than in prior work [3,4] (App. G.4).\n2) *Scalability*: See III.1.\n3) *Flow/autoregressive comparison*: See V.\n\n**IX - Questions For Authors**:\n1) *Imbalanced graph structures*: DeFoG implicitly captures distributional heterogeneity, confirmed by superior performance on very diverse structural graph statistics (degree, clustering, orbits, spectral, wavelet distributions; e.g., Table 7) and datasets.\n2) *Computational decoupling trade-offs*: Per-step sampling efficiency matches/exceeds existing models (See VIII.1). Additionally, training-sampling decoupling enables optional independent tuning, potentially further improving performance at minimal extra cost via an optimized hyperparameter selection pipeline (App.B.4).\n3) *Hyperparameter sensitivity*: See I.1.\n\n[3] - Digress: Discrete denoising diffusion for graph generation, Vignac et al., ICLR 2023\n\n[4] - Discrete-state Continuous-time Diffusion for Graph Generation, Xu et al., NeurIPS 2024\n\n[5] - Sparse Training of Discrete Diffusion Models for Graph Generation, Qin et al., ArXiv 2023", "claims_and_evidence": "The paper makes strong claims about:\n1. **Training-Sampling Disentanglement**: Theoretical grounding is provided, but additional empirical comparisons with diffusion-based methods under different training configurations would strengthen the claim.\n2. **Improved Sampling Efficiency**: The results show significant reductions in sampling steps (5–10% of diffusion models), but additional ablations on time-adaptive methods would clarify the practical efficiency gains.\n3. **State-of-the-Art Performance**: DeFoG outperforms most existing diffusion models across various datasets. However, detailed breakdowns on dataset-specific improvements would be helpful.\n\nOverall, the claims are well-supported, though further empirical comparisons and ablations could enhance the robustness of the results.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria make sense for the task:\n- **Synthetic, molecular, and pathology datasets** are well-chosen, covering diverse graph generation scenarios.\n- **Comparison with strong baselines**, including diffusion-based models, ensures fairness.\n- **Metrics such as validity, uniqueness, and novelty** are appropriate for generative models.\n\nHowever, additional analysis on the impact of different hyperparameters and computational trade-offs (e.g., memory and runtime comparisons) would be beneficial.", "theoretical_claims": "The paper provides **mathematical derivations** linking the discrete flow-matching formulation to graph generation performance. The proof structure appears sound, but verifying its correctness in practical implementations (e.g., sensitivity to noise schedules) would further validate its robustness.", "experimental_designs_or_analyses": "The experimental setup is well-structured, but there are some areas for improvement:\n- **Scalability Analysis**: Given the paper's emphasis on scalability, it would be useful to include an explicit study on how DeFoG scales with increasing graph size.\n- **Ablation Studies**: The ablation studies justify the importance of each component, but additional experiments on varying training configurations would be informative.\n- **Generalization to Out-of-Distribution Data**: Evaluating how DeFoG performs on unseen graph structures would enhance its applicability.", "relation_to_broader_scientific_literature": "The paper is well-grounded in the existing literature on **graph generative models**, particularly diffusion-based methods. However, connections to recent advances in **graph normalizing flows and autoregressive models** could be further discussed.", "essential_references_not_discussed": "Some essential references about graph generative models are not discussed, such as the following references:\n\n[1] Han X, Chen X, Ruiz F J R, et al. Fitting autoregressive graph generative models through maximum likelihood estimation[J]. Journal of Machine Learning Research, 2023, 24(97): 1-30.\n\n[2] Xu M, Liu M, Jin W, et al. Graph and geometry generative modeling for drug discovery[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 5833-5834.", "other_strengths_and_weaknesses": "### Strengths:\n- **Novel formulation** that decouples training and sampling, offering greater flexibility.\n- **Theoretical justification** enhances confidence in the approach.\n- **Empirical validation across multiple domains**, demonstrating SOTA performance.\n\n### Weaknesses:\n- **Scalability analysis is missing**, despite claims of efficiency.\n- **Limited analysis on generalization** beyond the tested datasets.\n- **Additional hyperparameter studies** would further validate robustness.", "other_comments_or_suggestions": "1. **Clarify the computational efficiency trade-offs**—while fewer sampling steps are needed, does DeFoG require significantly more compute per step?\n2. **Include additional experiments on scalability**—how does DeFoG perform on very large graphs compared to diffusion models?\n3. **Compare with other flow-based and autoregressive models**—this would help position DeFoG within the broader space of graph generation.", "questions_for_authors": "1. **How does DeFoG handle highly imbalanced graph structures?** Some datasets may have extreme degree distributions—does this affect the sampling process?\n2. **What are the computational trade-offs of training-sampling decoupling?** While DeFoG reduces sampling steps, does it increase per-step complexity?\n3. **How sensitive is DeFoG to hyperparameter choices?** Particularly in terms of the interpolation and rate matrices.", "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:

Meta-review: All reviewer suggested to accept the paper and the rebuttal could clarify a few remaining points, leading to reviewers increasing their score. The reviewers particularly liked the systematic empirical evaluation and hope for an easy to use code-base.
Decision: Accept (oral)