Smooth Interpolation for Improved Discrete Graph Generative Models
Authors: Yuxuan Song
Juntong Shi
Jingjing Gong
Minkai Xu
Stefano Ermon
Hao Zhou
Wei-Ying Ma
Venue: ICML 2025 poster (2025)
Keywords: Graph Generation; Deep Generative Models; Bayesian Flow Networks;
Primary area: deep_learning->generative_models_and_autoencoders
TL;DR: A discrete graph generative model based on Bayesian Flow Networks

Abstract: Though typically represented by the discrete node and edge attributes, the graph topological information can be sufficiently captured by the graph spectrum in a continuous space. It is believed that incorporating the continuity of graph topological information into the generative process design could establish a superior paradigm for graph generative modeling. Motivated by such prior and recent advancements in the generative paradigm, we propose Graph Bayesian Flow Networks (GraphBFN) in this paper, a principled generative framework that designs an alternative generative process emphasizing the dynamics of topological information. Unlike recent discrete-diffusion-based methods, GraphBFNemploys the continuous counts derived from sampling infinite times from a categorical distribution as latent to facilitate a smooth decomposition of topological information, demonstrating enhanced effectiveness. To effectively realize the concept, we further develop an advanced sampling strategy and new time-scheduling techniques to overcome practical barriers and boost performance. Through extensive experimental validation on both generic graph and molecular graph generation tasks, GraphBFN could consistently achieve superior or competitive performance with significantly higher training and sampling efficiency.

Smooth Interpolation for Improved Discrete Graph Generative Models
Yuxuan Song 12 Juntong Shi
Jingjing Gong 12 Minkai Xu" Hao Zhou Wei-Ying Ma
Stefano Ermon
Abstract
Though typically represented by the discrete node and edge attributes, the graph topological infor- mation can be sufficiently captured by the graph spectrum in continuous space. It is believed that incorporating the continuity of graph topo- logical information into the generative process design could establish superior paradigm for graph generative modeling. Motivated by such prior and recent advancements in the generative paradigm, we propose Graph Bayesian Flow Net- works (GraphBFN) in this paper, principled generative framework that designs an alterna- tive generative process emphasizing the dynam- ies of topological information. Unlike recent diacret-diiffusion-aaaee methods, GraphBFN em- ploys the continuous counts derived from sam- pling infinite times from a categorical distribu- tion latent facilitate smooth decomposi- tion of topological information, demonstrating enhanced effectiveness.. To effectively realize the concept, we further develop an advanced sampling strategy and new time-scheduling tech- niques to overcome practical barriers and boost performance. Through extensive experimental validation both generic graph and molecular graph generation tasks, GraphBFN could con- sistently achieve superior competitive perfor- mance with significantly higher training and sam- pling efficiency. The code is available at https: / //git hub. SoomAAlgoMola haw.a/ooooeeeeeeae.....aa
GraphBFN
Spectral Gep
GruM
GraphBFNi
0.0
0.2
Time (t)
Figure 1: The top figures compares the sampling trajec- DiGress and GruM (Vignac al., 2022; Jo et al., 2024). A smaller spectral gap reflects better graph clusterability (i.e. clearer sample). Both the visualiza- tions and curves demonstrate that GraphBFN allows much smoother transformation of graph topology information.
tories of GraphBFN
1. Introduction
Generative modeling of graph-structured data is an impor- tant task with applications in various important scenarios, egg. molecule generation (Jin et al., 2018; 7ang & Wang, 2020), traffic modeling (Yu & Gu, 2019) and protein de- sign (Ingraham et al., 2019). With the development deep generative models, there have been fruitful lines of research conducted tackle the challenges, e.g., Generative Adver- sarial Networks (Martinkus al., 2022; De Cao & Kipf, 2018) 8), Variational Auto-encoders (Jin et al., 2018; 2020), and Autoregressive models (You et al., 2018).
Recently, diffusion models (DMs) (Song Ermon, 2019; Ho al., 2020) have emerged as a powerful generative model across various fields (Zeng et al., 2022; Li al., 2022). Learning DMs for graphs is challenging due the discrete and complex relational nature of graphs. Niu et al. (2020); Jo et al. (2022) propose to dequantize the node vector and adjacent matrix with and learn Gaussian DMs over the dequantized variables. However, these approaches face problems due to the in-
'Equal contribution 'Institute for Al Industry Research (AIR), Tsinghua University DDepariment of Computer Science and Tech- nology, Tsinghua University UUniversity of Southern California, USA Stanfood University, USA. Correspondence Hao Zhou <zhouhao air.tiigghua.cdu.cn..
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
noise

---

Smooth Interpolation for Improved Discrete Graph Generative Models
compatibility of continuous Gaussian diffusion processes with discrete data. For instance, they involve noisy graph samples that lack well-defined topological information, e.g., clusterability or connectivity. To alleviate these problems, Vignac et al. (2022) proposed discrete graph diffusion mod- els based on discrete DMs (Austin et al., 2021). It utilizes a structured categorical corruption process (corresponding to successive graph edit operations such as additions, dele- tions, and replacements) to destroy the graph and learns to generate by reverting this process. Such discrete formula- tion ensures noisy samples are valid discrete graphs with well-defined graph topologies. This enables the discrete DMs to extract rich graph spectral features, such as graph spectrums, that aid the generation process, thus achieving better performance.
logical features. like the graph spectrum, easily generalize the probabilistic adjacency matrix, enabling straightforward analysis and the implementaiion of effective techniques such as spectrum conditioning. Quantitative measurements in Fig. show that GraphBFN enables stabilized topological dynamics compared to diffusion- methods with the target graph topology being smoothly recovered during the generation process. Specifically, our contribution can be summarized as follows:
We firstly prove the concept of smooth transforma- tion over topological information could facilitate the discrete graph generation with a new method termed GraphBFN based on Bayesian Flow Networks. We empirically demonstrated the effectiveness of smooth topological recovery. GraphBFN could fit more gen- eral graphs with rich node and edge features.
However, though always ensuring valid graph topology, the discrete graph diffusion process is very unbalanced. Some graph editing steps can significantly change the adjacency matrix and unexpectedly perturb the graph topology, making difficult to Iearn a satisfactory model for the reverse diffu- sion process. Recently, utilizing certain kinds of topological information formed in continuous space to provide smooth and consistent information flow for the generative process has been demonstrated to be effective for graph generative model (Martinkus et al., 2022; Vignac et al., 2022: Jo et al., 2024). Based on such phenomena, we hold the intuition that stabilized dynamics of graph topological information during the generation process could be favorable for discrete graphs. Furthermore, we aim to design a new generative framework for discrete graphs that could conduct smooth transition from data to noise, where the smoothness is quantified by generalized graph topological features.
To successfully implement the method and boost em- pirical performance, we introduce several innovations sampling and training, including the adaptive sam- pling strategy which provides better tradeoff's between quality and diversity, a general time-scheduling that shows good compatibility with low entropy prior, and a novel graph spectrum conditioned strategy for large graphs.
We conduct extensive experiments and ablation stud- ies several benchmarks including both abstract and 2D molecules. 'he empirical results show that the GraphBFN can consistently achieve superior or com- petitive performance in generating realistic and diverse graphs Furthermore, GraphBFN also enjoys a high sampling efficiency with up to 10x speedup while matching the performance diffusion-based methods.
Well motivated by this philosophy, we bring the concept of Bayesian Flow Networks, a recent advancement of genera- tive paradigms, into the context of graph generation. Differ- ent from the discrete diffusion model whose latent variable is the discrete variable following predefined forward cate- gorical noisy distribution, the latent variable of the Bayesian Flow Network could be defined with the counts of discrete variables by sampling infinite times from the same forward categorical noisy distribution and is hence continuous. By projecting the continuous latent of BFN into probability simplex, we obtain a mixed-state representation of differ- ent discrete states which enables the smooth interpolation between uninformative prior to the concrete observation. Based on such appealing property, we propose new and general graph generative framework named Graph Bayesian Flow Networks (GraphBFN). By substituting the discrete variable to probability simplex in the intermediate state of the generative process, GraphBFN makes a probabilistic generalization of the adjacency matrix as probabilistic ad- jacency matrix whose entries represent the probability of corresponding edge type to emerge. Fortunately, graph topo-
2. Related Works
From the fruitful lines of research conducted on genera- tive modeling for graphs, we focus on the discussion over diffusion-based approaches as they are most related to our method. Recently, given the remarkable performance of diffusion models (Ho et al., 2020) in fields such as image generation. there has been a growing interest in graph dif- fusion models within the community. Research conducted by Jo et al. (2022); Niu et al. (2020); Luo et al. (2023) has successfully made the diffusion framework compatible with discrete graphs through the dequantization approach that adds continuous noise discrete node and edge features. Jo et al. (2024) demonstrate the advantage of explicitly learn- ing the final graph structures in the diffusion process:Liu et al. (2025) show the benefits of modeling the graph gener- ation process within a bounded space; Vignac et al. (2022); Kong et al. (2023) highlight the benefits of modeling the
2

---

Smooth Interpolation for Improved Discrete Graph Generative Models
original discrete data space; Qin al. (2023); Chen al. (2023) leverage the spasity nature of graphs and show the possibility to scale the models up to larger graphs; Karami (2024) introduce hierarchical graph generative framework that captures the hierarchical nature of graphs. Furthermore, Vignac et al. (2022) highlight the potential issue of topol- ogy information getting distorted by continuous noise and thereby suggests utilizing more compatible discrete diffu- sions, resulting in noteworthy performance improvement. Similarly, Liu et al. (2025) emphasize the importance of maintaining critical graph topology and realizes this using modulation technique.
take the form of latent variable models with a series of noisy samples y (1mm) (y1,... .yn) of observation are intro- duced as latent. We note that y1 of the start of the sequence refers to the uninformative sample of pure noise, which is the opposite of the diffusion literatures. Besides, BFNs also optimize the variational lower bound of the likelihood:
Pá (x ((1mm)) ) Poo (y(1m)))
lxg)x(X)=
2
E
log
Y ((1m) mug
g(y [x)
- DDL(gll Po (y(1m)))
E
log [po (x ((ans))
V (( mi
In the literature of Bayesian Flow Network (Graves et al., 2023), there are several recent applications to the structured multi-modality data (Song et al., 2023; Qu et al., 2024) while the topological information modeling is less explored. Drawing inspiration from Graves et al. (2023), we propose the concept of probabilistic graph space, where the rep- resentation of topological information can be generalized, allowing for a smoother decomposition of information of discrete graphs. We leave more detailed discussion over
where is a predefined distribution for creating the noisy samples similar to the noise-application distribution in the forward process of diffusion models (sender distribution) and Ps refers to the probabílistic distributionnreceivvr dis- tribution) implied by BFNs. From the graphical model perspective, BFNs differs from diffusion models in the con-
struction of latent variables [(:n] (y1,,.. Yv), which is defined as non Mon-Markovian and could be extended as:
discrete diffusion models in the Appendix K.2.
1
Pá (y....., yn) = (y II Po(y' 111a-11)
(2)
3. Preliminary
The Py ((1:0-13) could be further represented with a predefined deterministic aggregation function of the pro- cess as Po ((y(1=-1)))) The f is related to the con- crete Bayesian update rule for different distributions, and f ((((1=))) 13) is also notated as 0z- Putting Eq. 2 into Eq. 1, the ELBO of BFNs could be further expressed as:
3.1. Notations and Background
We define the space of undirected graphs as G = (V, E), where & represents a categorical edge space and V a node space. For a graph G with n nodes, the adjacency matrix E E 2xxxx and the node vector V E Raxe= are both represented using one-hot encoding. Here, ce and on de- note the respective cardinalities. The absence of an edge is treated as specific edge type. This framework encom- passes both abstract graphs and 2D molecules studied in this work.
((x)
CELBO
(3)
Σ t=1
DKL (etx)x))lpoxxxlee ((()s/llle((((())))))
f(y(1=))))))
log po po (x((n,))
Then, we introduce the basics of spectral graph theory for better illustration. Spectral graph theory explores the re- lationships between graph properties and the eigenvalues of associated matrices, such as the adjacency matrix Laplacian matrix. Previous works (Martinkus et al., 2022; Vignac et al., 2022) have demonstrated the effectiveness of conditioning on graph spectra in generating graphs. This motivates us to revisit the generative process from the per- spective of building graph spectra, as shown in Fig. 1. De- tailed discussions on spectral graph theory are presented in Appendix B.
The term log Po 0n. o) is also known as reconstruction loss, which is directly computed over the network predic- tion with 0, As the term is generally negligible as O,, is very close to x. we do not involve the term in training loss following (Graves et al., 2023).
4. Methodology
In this section, we first identify the key difference between the GraphBFN and discrete diffusion-basse approaches and discuss how the GraphBFN could generalize smooth dynam- ies of topological information for graph generation. Then, we provide detailed formulation of our GraphBFN, along with a visualization of the training and testing procedure in Fig. 2. Lastly, we delve into several innovations for success- fully realizing the concept and boosting the applications in graph generation.
3.2. Bayesian Flow Networks
In this section, we aim to provide a very intuitive introduc- tion to the Bayesian Flow Networks (BFNs) (Graves al., 2023) and leave an in-depth discussion and more details in Appendix A. Similar to the diffusion models, the BFNs also
3

---

Smooth Interpolation for Improved Discrete Graph Generative Models
4.1. Smoothing Topological Transformation via Infinite Noisy Discrete Graphs
is defined by applying the following update rule recursively:
e f ai 0
8: -(00-.1)))))
(7)
We consider the following specific case of the perturbation
K Ex
distribution over discrete variables:
Here 0 lies in the probability simplex, i. Σ K 0 = 1. In the above adjacency matrix setting, we use EY,, to denote the corresponding parameter. Given E.; is on the probability simplex, it could be naturally interpreted as the probability over whether there is an edge between node i and node j. We design a Probabilistic Adjacency Matrix P based on y we force E to symmetric by E = (E" + (E²) then, we derive the probability of whether there exist an edge at Eng from E and make it as the corresponding value for the P.y. Under this definition of P each entry Pi. E [0, 1] could be seen as the parameter of the Bernoulli distribution.
Puoise (ye x) = Cat (yx: + (1 wi) T))
(4)
Hence x refers to the one-hot representation over the K categories and æ is the uniform prior over the categories, L.e x ....................... }. For the discrete diffusion model (Vignac et al.. 2022: Austin et al., 2021), the Eq. 4 could be seen as continuous-time variant of the variational distribution /(y,/x) in Eq. 1, i.e. the extension of discrete-time uniform transition diffusion (Austin et al., 2021). In this scenario, the latent variable yI exists in a discrete space and is generated through random substitution or deletion of elements from the clean sample x, with a probability of wi. In the context of graphs, these operations can significantly alter the topology; for example, deleting a single edge in the adjacency matrix may impact the entire graph's 's connectivity.
Remark 4.1. The graph spectrum, which is defined as the eigenvalues or eigenvectors of the adjacency matrix or Lapla- cian matrix could be directly extended by viewing P as the generalization of the adjacency matrix. We leave the de- tailed discussion over the graph spectrum in Appendix B.
Bayesian Flow Networks introduce different concept of latent Yr: Given the noisy distribution Pnoise, we assume sam- ple noisy samples from the noise distribution for m times instead of once, thus incurring count variable over the dif- ferent categories as c = [cl.... .x.. Based on the normal- ized counts (c- m. ) and central limit theorem limm- e-mag //mii (00 I) (where Q wix + (1 - wi w)),)), we could construct a continuous latent variable y with the k-th dimension as as:
The probabilistic adjacency matrix can be viewed as a spe- cial case of random graphs as in Athreya et al. (2018), pro- viding bounds between the graph spectrum of sampled dis- crete graphs from P and the generalized spectrum directly over P (Chung Radeliffe, 2011). The theoretical discus- sion is in Appendix C. The generation process in GraphBFN defines transformation from E% to ES,, interpolating be- tween p",, prior probabilistic matrix with all entries of 0.5, and p0=, representing authentic graphs with binary entries. This interpolation enables GraphBFN to smoothly decom- pose complex discrete structures, as illustrated in Fig. 1. The detailed formulation of interpolation and training objectives will be introduced in the following section.
m K
In(1 + wK
lim Vi 10
(5)
1- we have q (yr x: an) = N (at (Kx- - 1). aKII
where mw² = a is condition and a is predefined finite number. The above is obtained by assuming sampling infinite samples from the noise distribution. Detailed dis- cussion is left as Appendix I.
4.2. Graph Bayesian Flow Networks
We elaborate on the components introduced in Sec. 3.2 to get complete formulation of GraphBFN, Recall that the graph variable is denoted G (V.E). Correspond- ingly, the latent variable at time step t is referred to as 9 = (V E*) and the corresponding aggregation pa- rameter G (Vo, E².). Then, we revisit the ELBOO training objective introduced in Eq. 3. To improve concise- ness, we use the adjacency matrix E the primary example for derivation. Below, we illustrate the concrete formula- tion for the two key elements in the Eq. 3, q (y: x) and Pe (y: 0, (x(1:-11)).
In the context of graph generative modeling, the x could refer to the unit component of the graph, e.g. a node in the node vector (V:) or edge entry in the adjacency matrix (E,,g). For topological analysis, we focus on the discussion of the adjacency matrix. We use Ex to denote the latent variable for the whole matrix E, where the latent variable for each entry is therefore referred to as E. Under the framework of GraphBFN, E is count- latent as shown in Eq. 5. Though the latent variable enjoys continuity and real-valued it could be hard to view the E as valid adjacency matrices and analyze the topological dynamics from the perspective of the latent variable. Fortunately, we could instead focus on the parameter variable 0, which is the aggregation of the latent variable as introduced in Sec. 3.2. The aggregation f in Eq. 3 for the discrete variable
Sender distribution The q (Yr x) in the context of BFN is termed sender distribution. To define the sender distri- bution, we need extra involve an accuracy parameter a as also mentioned above in Eq. 5. Note the sender distribution
4

---

Smooth Interpolation for Improved Discrete Graph Generative Models
Φ
G
Φ G Bess
+ 1)
G
Boyesion Flow
Naising
Network
G
Network
f/
0
Boyesion Update
G Q f
[GG))
E L(B,t) + ((V (-010.))
Aggregation
Bayesian Flow
Bayesian Flow
0
G (V, E)
G
Bayesian Flow
Figure 2: Diagram of GraphBFN. The solid lines and dashed lines denote the inference and training procedures, respectively. We note that A [ .t) ( .-
1)lla.
for the adjacency matrix is set as independent for different entries, then the sender distribution here takes the form
be illustrated as:
q 1 E, oz) = IT Tisisnn (E Eg.j (4t)
q
E
Ei
E.0 [i
11 sisss V ( at Ec 1). arcel)
(8)
6 .EW,
④
%
E 8
E
(10)
D(1)
Cr
(C
80
2k=1
Receiver distribution Pe (ye 0, f (1(1==1))) here also named as the receiver distribution. Intuitively, Pa (ye 0.) could be decomposed into first predict distri- bution of with neural network e based on Or and combine predicted distribution with the sender distribution above to get a distribution over y. In our case, the receiver distribu- tion takes the form of:
where D(1) N (E J ((,() 1), B(1c,,))
B(t) = Σ/= ay- Note that @ denotes the element- wise product between the vectors, and in e the exponential function is applied to each dimension individually. Such distribution is also noted as the Bayesian flow distribution. Putting Eq. 10, Eq. 9 and Eq. in Eq. 3, we could obtain the final training objective.
P& (E
G II (E G
Pa(E )
Continuous-time Training Objective The above discus- sion based on that the number of latent variables is n, which is finite. It could also be possible put n - oc, which could correspond to the continuous-time training. For convenience, we consider the value of timestep t in [0, 1]. In this case, B(t) fo (t).. For flexibility, we could use different scheduler of a(t) for edge and node, i.e. are and (l). With the following notations as:
Eaglo(G ( (EY) or (celk 1), arc.
1=1
Here eş is the one-hot vector with k-th dimension as 1 and the other c. - dimensions are all 0. Given the G. and as network input, here E (GG ,)](() is the probability on k-th category of the predicted categorical distributions for E.j. Note the network o usually has the final layer softmax and hence output could be naturally seen the probability of the predicted distribution, which is also referred to as output distribution.
(E* E, E%) = I1 IIsisnn EEG E E.g)
(V V, vo) 1Isisng (v. V., V
Simulation-free Training However, as mentioned above and also shown in Eq. 3, the network input is 9, which is de- termined by y1," ... y,, and the discrete update rule in Fq. 7. Fortunately, with the discrete update rule, we could do ag- gregation in the distribution level for xx), ... q(y, x) and directly obtain the analytic form of distribution over 0,, ((+x))). With the notation of E, the distribution could
9 G G, %))
(E
E. E.) ) q (vo: V Vo)
(11)
Under the continuous- timee steps, there is a very concise analytic form for the KL divergence between the sender distribution (Eq. and the receiver distribution (Eq. 9) over
5

---

Smooth Interpolation for Improved Discrete Graph Generative Models
time step as:
q (G (GG ( 1), Gou) here is the Bayesain flow distribution analogy to Eq. 10. We termed this approach as Flowback. Though the error accumulation is fixed, Flow- back sampling could collapse due to that the network output distribution (G t)) could hold low entropy practically. To balance exploration and exploitation, we combine the two sampling procedure and introduce the adaptive Flow- back: with a predefined constant c. for any time t, when ( G .) ((G
t(E,t)
= = (!l)
1
Σ 15t,5Sn
Ea,- - E OIll"
G,G%)
t(,,t)
1 = =c |GG/G.G.))
E
Σ Isisa
IV - "V(("""s))]
1)ll 2 c, we conduct vanilla sampling; when [Ø(G () dG , 1)]1² < the Flowback (Fq. 13) is conducted. Empirically, we find the adaptive Flowback could be approximately implemented by setting a threshold over t to determine which kind of sampling to conduct to improve efficiency. The detailed sampling process is presented in Algorithm 2.
Combining the above terms, our final objective for GraphBFN is as:
(GG)=(((EV)) = E +LV)) (12) (~U(011)
The detailed training and sampling algorithms are illustrated in Appendix E. And with perturbation equivariant archi- tecture for Φ, e.g., Graph Transformer, we have following properties:
Accuracy Scheduling for Any Prior The accuracy schedul- ing is defined by the function 3(t) I/ a(t). which repre- sents the level the sender distribution corrupted the original information of the data samples. The original BFN paper (Graves et al., 2023) defines the accuracy scheduling as 8(t) = (1) and, correspondingly, the accuracy rate as a(t) = (())tt. Such design relies on the intuition that, with a uniform prior, the expected entropy of could lin- early decrease along the Bayesian flow distributions. The scheduling also implies the fact that the accuracy is 0 for the prior Og as it is fully uninformative. However, in some scenarios of graph generation, an informative prior has been demonstrated to be effective (Vignac et al., 2022). To this end, we introduce a more general accuracy scheduling with a simple yet effective formulation:
Proposition 4.2. If é is permutation equivariant function, then for any permutation n,, we have:
* The objective in Eq. 12 is permutation invariant: L(G) = L((E, V)- = L(x''EE EsT, VV
*
The density function, Pa, implied by the generative process of GraphBFN is also permutation invariant, i.e., PE, = Pn En, n² V)
We leave the proof of the Proposition 4.2 in the Appendix J.
4.3. Improved Techniques for GraphBFN
a(t) (B(1) a) B(1) at + (1(1)-a))
(14)
Sampling with Adaptive Flowback The Bayesian Flow Networks conducted an autoregressive sampling procedure. For example, the i-th step vanilla sampling of BFN could be introduced as: first sample G.-1 according to the network output distribution o @ ,, - 1); and assuming G as the final generated targets to sample G: based on the sender distribution, and then apply the Bayesian update function to get G*., However, there exists a notable discrepancy between training and sampling: During training the noisy samples y are sampled based on real data; while at inference, the y are sampled based on model prediction which brings extra errors, especially for the initial steps where there lacks information in the model inputs. The error will always be kept in the inputs due the autoregressive Bayesian update, which could potentially hurt the performance.
(15)
Here, is a hyperparameter. One degenerate case of Eq. 14 is when a = B()), which assigns constant accuracy at each time. As shown in Fig. 3, our general accuracy scheduling exhibits more steady paces of information reconstruction. This scheduling could be compatible with low- low-entropy prior, iee. assigning nonzero accuracy for informative prior, and also have faster input entropy decrease.
Conditioned Graph Features on Output Distributions Previous literature (Beaini et al., 2021; Vignac et al., 2022) has demonstrated that incorporating extra features of input graphs can enhance the representation power of graph neu- ral networks. For example, Vignac al. (2022) computes various graph descriptors of the noisy graph and includes them in the input of the denoising network during both train- ing and sampling. In GraphBFN, we could also calculate the graph descriptors of the probabilistic adjacency matrix for the inclusion of the interdependency modeling network, i.e. Φ. We note that the extra graph feature is not necessarily used, and the choice determined by the data property and
To the end, we introduce another sampling procedure to make the sampling focus on the current prediction by using the Bayesian Flow distribution:
Pe f - = q (G (t t- 1-11) 1). Go))
(13)
6

---

Smooth Interpolation for Improved Discrete Graph Generative Models
complexity. For the usage of extra features, we apply different strategy compared to previous literature (Vignac et al., 2022) by conditioning the network output distribution. We denote the module for computing the extra features as M()), for example, obtaining the eigenvalues or eigenvec- tors of the adjacency matrix. The computation of the output distribution with the spectral feature conditioning is then formulated as:
has shown superior or competitive performance compared to all the baselines both datasets. Specifically, on the Pla- nar dataset, GraphBFN obtains a V.U.N. value approaching the limits, demonstrating the advantages of modeling the discrete graph in the probabilistic matrix space. We include more details of visualizations and analysis in Appendix R and Appendix G.
5.2. 2D Molecule Generations
o Msg o( (G .)))
(16)
For the molecule datasets, we conduct experiments on 2D molecule datasets with various scales: QM9 which in- cludes 100k molecules with up to 9 heavy atoms in the training set; ZINC250K which contains 250,000 drug-like molecules with maximum atom number of 38; MOSEs with 1,936,962 drug-like molecules whose atom number is up to 38. GraphBFN jointly models the node features V and the graph typologies E of the molecular graphs. Besides, for the experiments on QM9, we consider both the without- hydrogen version and the more challenging version where the hydrogen will be explicitly modeled. For QM9 with explicit hydrogen, we evaluate GraphBFN's performance with two additional metrics, the Atom Stability, i.e. the percentage of the atoms with valid valency, and Molecule Stability for the percentage of generated molecules whose atoms all have valid valency. For other datasets, we follow the evaluation of previous works (Jo et al., 2024; Vignac et al., 2022) and report the corresponding metries, including FCD, SNN, Scaffold similarity(Scaf), NSPDK, Novelty, and Validity, etc.
where sg is the stop gradient operator. The key motivation of the proposed method is related to the self condition as proposed in Chen et al. (2022), which helps to improve the inner consistency of the generated samples. Such techniques are only used in large graphs such as the SBM dataset.
5. Experiments
We empirically study the effectiveness of the proposed framework. We conduct extensive experiments on both the abstract graph datasets and 2D molecule datasets to compare the performance of GraphBFN against several competitive graph generation baselines, including diffusion/score match- ing based methods, such as Digress (Vignac et al., 2022), GruM (Jo et al.. 2024), GBD (Liu et al., 2025), GDSS (Jo et al., 2022) and EDP-GNN (Niu et al., 2020); latent vari- able models, such as JT-VAE (Jin et al., 2018). GAN-based method SPECTRE (Martinkus et al., 2022); flow-based methods such as GraphAF (Shi et al., 2020), MoFlow (Zang & Wang, 2020) and GraphDF (Luo et al., 2021). Please re- fer to Appendix for details about our experiment settings, the link our implementation, and additional experiment results.
The experiment results of QM9 can be found in Tab. 2 and Tab. 4. It could be found that GraphBFN shows superior or competitive performance compared with the previous method. In the challenging setting of QM9 with explicit hydrogen, the GraphBFN could beat the baselines with large margin and approach the empirical limits in the sense of molecule stability, which justifies the effectiveness of jointly modeling the distribution of node features and edge feature under the probabilistic parameter space.
5.1. Abstract Graph Generation
The abstract graph generation experiments test the model's ability to model complex graph topology. We conduct ex- periments on the benchmarks introduced in Vignac et al. (2022); Martinkus et al. (2022). should be noted that we only need to model edge connections for the generation tasks of abstract graphs. The benchmark consists of two datasets: Planar with the constant number of 64 nodes per graph and Stochastic Block Model (SBM) with up to 200 nodes per graph. We evaluate the maximum mean discrep- ancy (MMD) of four graph statistics, i.e. degree (Deg.), clustering coefficient (Clus.), count of orbits with 4 nodes (Orbit), and the eigenvalues of the graph Laplacian (Spec.) between the generated graphs and test sets. Besides, we also report the percentage of valid, unique, and novel (V.U.N.) graphs, where a graph is considered valid if it satisfies the statistical properties of the SBM model or being planar and connected for the Planar dataset (Martinkus et al., 2022). The experiment result can be found in Tab. 1. GraphBFN
The empirical results of ZINC250K and MOSES in Tab. 2 and Tab. show GraphBFN's consistently superior perfor- mance compared to the baselines, demonstrating its scala- bility to the large complex datasets. It should be noted that in Tab. 3, compared with other one-shot models, GraphBFN shows a slight decrease in novelty while maintaining high uniqueness. One possible explanation lies in that the proba- bility distribution learned with GraphBFN is so close to the training distribution that causes some overlap of the support. Despite this overfitting, the novelty still lies high level (89%). It also demonstrates the generalization ability of GraphBFN. We leave the visualization of generated samples in Appendix R.
7

---

Smooth Interpolation for Improved Discrete Graph Generative Models
Table 1: Main results on general graph generation. Best results are bolded, and the second-best results are underlined. GraphBFN consistently achieves either the best or competitive performance across all datasets.
Planar
SBM
Synthetic, |V|
64
Synthetic, 44
[V| S 187
Deg. 4
Clus. |
Orbit +
Spec. +
V.U.N. t
Deg. +
Clus. &
Orbit 4
Spec. +
V.U.N. f
Training set
0.0002
0.0310
0.0005
0.0052
100.0
0.0008
0.0332
0.0255
0.0063
100.0
GraphRNN
0.0049
0.2779
1.2543
0.0459
0.0
0.0055
0.0584
0.0785
0.0065
5.0
GRAN
0.0007
0.0426
0.0009
0.0075
0.0
0.0113
0.0553
0.0540
0.0054
25.0
SPECTRE
0.0005
0.0785
0.0012
0.0112
25.0
0.0015
0.0521
0.0412
0.0056
52.5
EDP-GNN
0.0044
0.3187
1,4986
0.0813
0.0
0.0011
0.0552
0.0520
0.0070
35.0
GDSS
0.0041
0,2676
0.1720
0.0370
0.0
0.0212
0.0646
0.0894
0.0128
5.0
DiGress
0.0003
0.0372
0.0009
0.0106
75.0
0.0013
0.0498
0.0434
0.0400
74.0
GBD
0.0003
0.0353
0.0135
0.0059
92.5
0.0013
0.0493
0.0445
0.0047
75.0
GruM
0.0005
0.0353
0.0009
0.0062
90.0
0.0007
0.0492
0.0448
0.0050
85.0
GraphBFN
0.0005
0.0294
0.0002
0.0046
96.7
0.0005
0.0560
0.0370
0.0053
87.5
Table 2: Main results on the QM9 with implicit hydrogens and ZINC250K. Best results are bolded, and the second-best results are underlined. GraphBFN consistently achieves the best or competitive results across all datasets.
QM9 (VI 9)
ZINC250K (IV) S 38)
Method
Valid (%)
FCD4
NSPDK]
Scalt
Valid (%)f
FCDJ
NSPDK
Scaf.f
Training set
100.0
0.0398
0.0001
0.9719
100.0
0.0615
0.0001
0.8395
MoFlow (Zang & Wang, 2020)
91.36
4.467
0.0169
0.1447
63.11
20.931
0.0455
0.0133
GraphAF (Shi et al., 2020)
74.43
5.625
0.0207
0.3046
68.47
16.023
0,0442
0,0672
GraphDF (Luo et al., 2021)
93.88
10,928
0.0636
0.0978
90.61
33,546
0.1770
0,0000
EDP-GNN (Niu et al., 2020)
47.52
2,680
0.0046
0.3270
82.97
16,737
0.0485
0,0000
GDSS (Jo et al., 2022)
95.72
2,900
0.0033
0.6983
97.01
14.656
0.0195
0.0467
DiGress (Vignac et al., 2022)
98.19
0.095
0.0003
0.9353
94.99
3.482
0,0021
0,4163
GBD (Liu et al., 2025)
99.88
0.093
0.0002
0.9510
97.87
2.248
0.0018
0.5042
GruM (Jo et al., 2024)
99.69
0.108
0.0002
0.9449
98.65
2.257
0.0015
0.5299
GraphBEN (Ours)
99.73
0.101
0.0002
0.9386
99.22
2.116
0.0013
0.5304
5.3. Ablation Studies
Adaptive Flowback Sampling We verified the effective- ness of the Adaptive Flowback sampling on the abstract graph dataset Planar. The experiment results can be found in Tab. 5. We note that with vanilla sampling (i.e., c 0.0, where the vanilla BFN sampling is used throughout the sam- pling process), the performance of V.U.N. is only 14.8%. With full Flowback, we could obtain a competitive perfor- mance with V.U.N. consistently outperforming the baseline, while the distribution-level metrics are still sub-optimal due to the collapse phenomenon. With adaptive Flowback, we could obtain the best quality-diversity tradeoff which makes adaptive Flowback more appealing strategy.
Sampling Steps We conduct extensive ablation studies of GraphBFN, We first consider GraphBFN's property of sampling any steps and then examine the improved tech- niques we claimed in Sec. 4.3. One appealing property of GraphBFN is that with continuous-time objectives, the GraphBFN could sample with any steps. We conduct an ablation study of sampling steps on the dataset of Q.99 with explicit hydrogen and Planar in Tab. 4. It could be found that the GraphBFN with as few as 25 and 50 sampling steps could be on par with diffusion models with 500 and 1000 steps. This result implies more than 10x increase in sampling efficiency.
Due to space limits, we defer the additional ablation stud- ies on Time Scheduler and Output Conditioned Feature to Appendix H. Furthermore, we conducted an empirical
8

---

Smooth Interpolation for Improved Discrete Graph Generative Models
Table 3: Main results on MOSES. We bold the best and underline the second-best results across all one-shot methods. GraphBFN outperforms other one-shot baselines on most metrics.
Model
Class
Val f
Uniquet
Novel
Filterst
FCD4
SNN1
Scaft
VAE
SMILES
97.7
99.8
69.5
99.7
0.57
0.58
5.9
JT-VAE
Fragment
100
100
99.9
97.8
1.00
0.53
10.0
GraphINVENT
Autoreg.
96.4
99.8
95.0
1.22
0.54
12.7
ConGress
83.4
99.9
96.4
94.8
1.48
0.50
16.4
DiGress
One-shot
85.7
100
95.0
97.1
1.19
0.52
14.8
GraphBFN
88.5
99.8
89.0
98.3
1.07
0.59
10.0
Voiill
DiGress Validity
Table 4: Ablation study on GraphBFN's ability to tradeoff sampling quality and efficiency. Our experiment QM9 with explicir hydrogen and Planar demonstrates that GraphBFN can produce equally good samples as the previously best models with only 10% their sampling steps (500 for QM9 and 1000 for Planar). few entries are left as blank because the corresponding experiment results are not implemented in the original works (Vignac al., 2022; Jo al., 2024).
Atom Stable
DiGres Atom Stable
Vect Stable
DiGress Noi Shable
100-
95
85
80
QM9 with H [V]
Planar [V] 64
% Sampll Steps log
% Sample Steps Valid (%)
Unique (%)
Atom Stab. (%) f Mol, Stab. (%t) 1
V.U.N. (%)
XU8 * DXCres KUl.
DruM MULN
100
99.2
94.9
99.4
94.7
96.7
98.8
95.6
99.1
91.4
93.8
95.9
98.7
71.1
94.2
96.4
98.1
79.7
14.8
100 (DiGress)
95.4
97.6
98.1
79.8
75.0
100 (GruM)
90.0
20
100
Sample Steps (in log scale)
Table 5: Ablation study on the impact of the adaptive Flowback threshold on generation quality and diversity. According to our experiment on Planar Graph, increaseing the use of Flowback sampling strategy always yields better sampling quality (as reflected in the strictly increasing V.U.N). However, overusing it might compromise sample diversity (as reflected the sub-optimal graph statisties of 1.0 in comparison to 0.5).
Planar
Deg. |
Clus. |
Orbit +
Spec. 4
V.U.N. +
Training Set
0.0002
0.0310
0,0005
0.0052
100.0
Flowback (1.0)
0.0015
0.0703
0.0017
0.0047
98.2
Adaptive Flowback (0.5)
0.0005
0.0294
0.0002
0.0046
96.7
Vanilla (0.0)
0.0051
0.1793
0.0278
0.0099
14.1
study that quantifies the benefits of smooth graph topology transformation, with details presented in Appendix G.2.
matrix space. We first identify the train-test discrepancy issues in the vanilla formulation of Bayesian Flow Net- works and propose several innovations under the frame- work. These appealing properties and improved techniques help GraphBFN achieve consistently superior performance extensive graph generation benchmarks. Furthermore, GraphBFN maintain decent sample quality while requir- ing much fewer sampling steps, thus largely improving the sample efficiency.
6. Conclusions
We introduce GraphBFN for the generative modeling of discrete graphs. GraphBFN is motivated by the intuitive idea of smoothly decomposing and modeling the informa- tion of the graph topology by introducing a probabilistic

---

Smooth Interpolation for Improved Discrete Graph Generative Models
Acknowledgments
G., and Liò, P. Directional graph networks. In Interna- tional Conference Machine Learning, pp- 748-758. PMLR, 2021.
This work supported the Natural Science Foundation of China (Grant No. 62376133) and sponsored by Bei- jing Nova Program (20240484682) and the Wuxi Research Institute of Applied Technologies, Tsinghua University
Chen, T., Zhang, R., and Hinton, G. Analog bits: Gen- erating discrete data using diffusion models with self- conditioning. arXiv preprint arXiv:2208. 2022.
(20242001120;
Impact Statement
Chen, X., He, J., Han, X., and Liu, L.-P. Efficient and degree-guided graph generation via discrete diffusion modeling, 2023. URL https: https///xxxvvooo abs/ 2305. 04111.
We confirm that our work complies with the ICML Publi- cation Ethics, and we have carefully considered potential ethics concerns relating the development and use of our proposed method GraphBFN for generative modeling of graph-structured data.
Chung, F. Spectral Gruph Theory. Number no. 92 in CBMS Regional Conference Series. Conference Board of the Mathematical Sciences, 2006. ISBN 9780821889367. URL https: //to////bkkkks google. com/books?id- MCuhAC.
Our model is designed for general graph generation tasks and does not involve the use of sensitive personal data. How- ever, we acknowledge that generative models, when applied to specific domains, such as molecular generation and social networking modeling, may inadvertently create synthetic data that could mimic private structures and details. Thus, we encourage users to apply our model in compliance with relevant privacy regulations and to critically evaluate its outputs.
Chung, F. and Radcliffe, M. On the spectra of general random graphs. Electr. Comb. 18, 10 2011. doi: 10.37236/702.
De Cao, N. and Kipf. T. Molgan: An implicit genera- tive model for small molecular graphs. arXiv preprint arXiv: 18855/1973,, 2018.
We are committed to full transparency in our research. All datasets used in our experiments are publicly available and documented in detail to ensure reproducibility and compli- ance with legal standards. The methods and assumptions made in our research are clearly documented, and we pro- vide substantial reproduction details in Appendix L. Further- more, there is no confict of interest, financial or otherwise, that could influence the development or presentation this work.
Graves, A., Srivastava, R. K., Atkinson, T, and Gomez, F. Bayesian flow networks. arXiv preprint arXhv:2308.070377 2023.
Grone, R., Merris, R., and Sunder, The laplacian spec- trum of graph. SIAM Journal on matrix analysis and applications, 11(2):218-25 1990.
Based these considerations, do not anticipate any violations of the ICMI. Publication Ethics through the devel- opment or application of this model. However, we empha- size again that GraphBFN should not be used for malicious purposes, such as generating mislcading data or creating harmful content.
Ho, J., Jain, A., and Abbeel, Denoising diffusion proba- bilistic models. arXiv preprint arXiv:2006.1 /239, 2020.
Ingraham, J., Garg, V., Barzilay, R., and Jaakkola, T. Gener- ative models for graph-based protein design. Advances in neural information processing systems, 32, 2019.
Jiang, J.
AN INTRODUCTION TO SPECTRAL GRAPH THEORY. The University of Chicago, 2012. URL https:/ /ttp://maahhh.e http://atat.....ooe.e.e -may/
References
uchicago.edu.
Athreya, A., Fishkind, E., Tang, M., Priebe, C. E.,, Park, Y., Vogelstein, J. T., Levin, K., Lyzinski, V., Qin, Y., and Sussman, D. L. Statistical inference random dot product graphs: survey, Journal of Machine Learning Research, (6(22)):1-92 2018.
Jin, W., Barzilay, R., and Jaakkola, T. Junction tree vari- ational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323- 2332. PMLR, 2018
Austin, J., Johnson, D. D., Ho, J., Tarlow, D., and Van Den Berg, Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34:17981-17993, 2021.
Jin, W., Barzilay, R., and Jaakkola, T. Hierarchical gen- eration of molecular graphs using structural motifs. In International conference on machine learning, pp. 4839 4848. PMLR, 2020.
Beaini, D., Passaro, S., Létourneau, V., Hamilton, W., Corso,
10

---

Smooth Interpolation for Improved Discrete Graph Generative Models
J., Lee, S., and Hwang, S. Score-based generative mod- eling of graphs via the system of stochastic differential equations. arXiv preprint
Qu, Y., Qiu, K., Song, Y., Gong, J., Han, J., Zheng, M., Zhou, H., and Ma, W.-Y. Molcraft: Structure-based drug design in continuous parameter space. arXiv preprint arXi::2404.1214 2024.
2022.
Jo, J., Kim, D., and Hwang, S. J. Graph generation with diffusion mixture. In Forty-first International Con- ference on Machine Learning, 2024. URL https: //ooenreview, www.leewnet/eeeee www.:nnun/eeoeeeeeeeeo c2Ipddxgg2.xxx.x.....
Shi, C., Xu, M., Zhu, Z., Zhang, W., Zhang, M., and Tang, J. Graphaf: flow-hased autoregressive model for molec- ular graph generation. arXiv preprint arXiv:2001.09382, 2020.
Karami, M. Higen: Hierarchical graph generative networks. In The Twelfth International Conference on Learning Representations, 2024, URL https: /pppreveneeeeeeeeeeeeeeeeeee.eee net/ wtw.eoiioooe..eee.........eiie.e ANuubydSS...
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. In Advances Neural Information Processing Systems, pp. 11918-1111 11930, 2019.
Kong, L.., Cui, J., Sun, H., Zhuang, Y., Prakash, B. A., and Zhang, C. Autoregressive diffusion model for graph generation, 2023. URL httttt:///axiis org/ / 2307. 08849.
Song, Y., Gong, J., Zhou, H., Zheng, M., Liu, J., and Ma, W.-Y. Unified generative modeling of 3d molecules with bayesian flow networks. In The Twelfth International Conference on Learning Representations, 2023.
Li, X. L., Thickstun, J., Gulrajani, I., Liang, P., and Hashimoto, T. Diffusion-LMM improves controllable text generation. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Pro- cessing Systems, 2022. URL https: /pppreeeeeeeeeeeeee net/forum? Eorum? -eeeenddddssssssse Lyy..
Vignac, C., Krawezuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, P. Digress: Discrete denoising diffusion for graph generation. arXiv preprint 2rXiv:2209.144: 14734, 2022.
Wyss-Gallifen.. J. Graph Theory.
The Uni-
versity of Maryland, 2021. //www. www.maahh...m umd. aedu/iimmortteeeeeeeeeeeeeeeeaee Lmmortaa/MAATALLL/ book ch www_gggrpphhhhhheee pdf.
URL https:
Liu, X., He, Y., Chen, B., and Zhou, M. Advancing graph generation through beta diffusion. In The Thirteenth International Conference on Learning Representations, 2025. URL httttp::///pereevviiice wwt. forum? id=x1An5a309I.
You, J.. Liu, B., Ying. Z., Pande, V., and Leskovee, J. Graph convolutional policy network for goal-directed molecular graph generation. In Advances in neural information processing systems, pp. 6410-6421, 2018
Loshchilov, I. and Hutter, F. Decoupled weight decay regu- larization, 2019.
Yu, J. J. Q. and Gu, J. Real-time traffic speed estimation with graph convolutional generative autoencoder. IEEE Transactions on Intelligent Transportation Systems, 20 (10):3940-3551, 2019.
Luo, T., Mo. Z., and Pan, J. Fast graph generation via spectral diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023.
Luo, Y., Yan, K., and Ji, S. Graphdf: A discrete flow model for molecular graph generation. In International Con- ference on Machine Learning, pp. 7102-7203. PMLR, 2021.
Zang, C. and Wang, F. Moflow: an invertible flow model for generating molecular graphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 617-626, 2020.
Martinkus, K., Loukas, A., Perraudin, N., and Wattenhofer, R. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In- ternational Conference on Machine Learning, pp. 15159- 15179. PMLR, 2022.
Zeng, X., Vahdat, A., Williams, F., Gojeic, Z., Litany, O., Fidler, S., and Kreis, LION: Latent point diffusion models for 3d shape generation. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https: / / /pppreeviii ew net. forum? dkt jp-
Niu, C., Song, Y., Song, J., Zhao, S., Grover, A., and Ermon, S. Permutation invariant graph generation via score-based generative modeling. In International Conference on Ar- tificial Intelligence and Statistics, pp. 4474-4484, PMLR, 2020.
Zhou, M., Chen, T., Wang, Z., and Zheng, H. Beta dif- fusion. In Thirty-seventh Conference on Neural In- formation Processing Systems, 2023. URL https: / //openreview ew net forum? d=zTS 1m4nmlH
Qin, Y., Vignac, C., and Frossard, P. Sparse training of discrete diffusion models for graph generation, 2023.

---

Smooth Interpolation for Improved Discrete Graph Generative Models
A. Detailed Introduction to Bayesian Flow Networks
In this section, we introduce the basic components of Bayesian Flow Networks (BFNs) (Graves et al., 2023). The graphical model of BFN could be expressed in the form of a latent variable model whose prior non-Markov autoregressive. distinguishing it from the diffusion models that have Markov priors. That is, for learning the probability distribution pe over sample space x, series of noisy versions Y ((s=) = (" yn) of x are introduced latent variables. Then the model seeks to optimize the variational lower bound of the likelihood:
Pa (xly ( log
log pe(())
E Y (1:m) 7
- -DKL (y(Lm)))
+
E log Ps (x
y(1m)))
( [x)
y ((mm) ma
(17)
The variational distribution g is defined by so-called sender distribution ps (y: x; x; The sender distribution could be understood as adding noise to the data sample x with predefined accuracy 0g. The variational distribution is the fixed mean-field combination of sender distribution by q (y (1:n] x) -I Ps (y: x;
For the autoregressive prior P& (y1,..., the joint distribution could be extended with Bayesian decomposition as:
" Pa (y1,.... -. ..) = po())) H ((rr-1))
(18)
Note in BFN, the y is non-Markov contrast to diffusion models. In BFN, a new variable is introduced based on a fix-form functional transformation f. e.g. weighted average function, as O. = [(y with & >> and 0, as a constant. We elaborate more on the definition of t, which is implied by successive Bayesian updates as O₂ h(0,-1. at). Yt, Given the constant prior Oo and a series noisy versions ((1m) of x, we could obtain 0 (1:m) through a sequence of Bayesian updates. The only randomness of the above process comes from y, hence it could be summarized
deterministic function f over 0 has the statistical interpretation as the parameter of the factorized distribution over the sample spaces by p(x 0) = 12 P (x(d) g ( The conditional distribution p Y Y(1a-1)) is defined as Po ((1=-1))= =
py(y: 01-1 = f (1a-)))) Thus, Eq. 18 could be rewritten as: Pe (y1,-.. yn) = II Py 0:-1). We then elarify po' 0t-1). To obtain this term, we will first input 0,-1 into the neural network & to capture the interdependency between different dimensions. Hence the distribution implied by 0--1. the neural network input, is also named as imput distribution. The output of the neural networks denoted 0 +(0,-1) still lies in the parameter space and the corresponding distribution is usually referred to output distribution. Combining the formulation and accuracy ag of sender distribution ps. the distribution p 0,-1) i) is defined as
poly: I 02-1) = Epo (8)) (y' (x)
(19)
Note the (yr 02-1) is also formulated as receiver distribution pnlye O.-1; a.)).
Integrate Eq. 19 to Eq. 17, with (x (x))))(mm)) = (x(0)),) we could get the objective as:
LELO = Σ DKz + px
(20)
Here (t) and px(t) is abbreviation for ps at) and (y 0 q oz). To conduct simulation- training on the ELBO, Graves et al. (2023) proposed to use the so-called Bayesian flow distribution pr (0m)) (x) formulated as
(0. I1 (x)) formulation.
E
f(y(1=)). which allows for teacher- forcin--kr training and generally has an analytical
B. Spectral Graph Theory
Following previous literature (Vignac et al., 2022; Martinkus et al., 2022), we consider the definition of graph spectrum as the eigenvalues of the Laplacian matrix. For a graph G with n nodes, the graph Laplacian matrix is defined as L D A, where is the n x n adjacency matrix with A,, = if the node v; and node vy are connected and A,, = 0 otherwise. D is the degree matrix, a diagonal matrix defined as diag (di, dn). Here d, denotes the degree of the node v;
12

---

Smooth Interpolation for Improved Discrete Graph Generative Models
d, = ش A..- Besides, the normalized Laplacian Matrix Leen is defined as porm I- D AD - For the symmetric positive semi-definite matrix L or Lnomn the eigen-decompositton is UAU* where U = | Un] is an orthogonal matrix for the eigenvectors and = diag (A1,... An) denotes the collection of eigenvalues. The eigenvalues and eigenvectors of the graph Laplacian imply some key properties of the graph topology structure, such as connectivity, clusterability, and distance between nodes (Grone al., 1990).
Spectral Gap and Graph Clusterability In this paragraph, we elaborate on the relationship between graph clusterability and the spectral gap that we' ve used to quantity graphs' topological information in Figure 1.
The spectral gap is computed by taking the difference between the first two smallest eigenvalues of graph matrices. Its definition varies slightly depending on whether the eigenvalues are taken from a graph's adjacency matrix or the Laplacian matrix. Nevertheless, regardless of which matrix it takes, the correlation holds that smaller spectral gap implies poor graph connectivity and good clusterability. In our paper, we stick to the definition according to the Laplacian Matrix.
The Laplacian matrix L is symmetric and has non-negative and real eigenvalues. The multiplicity of 0 in the eigenvalues of is equivalent to the number of connected components in the graph (Jiang, 2012).
Let 'I...., An denote the eigenvalues of L the increasing order. The spectral gap in this scenario defined as λ2 X1 (Martinkus et al., 2022). Since the smallest eigenvalue is always 0 (as the graph must have least one connected component), the spectral gap nothing but the second smallest eigenvalue of the Laplacian.
The second smallest eigenvalue is known as the Fiedler Value or the algebraic connectivity of graph, and it reflects the connectivity of graph (Wyss- Grass-Gal,,,et,,, 2021). Specifically, given a fixed graph volume, the second smallest eigenvalue lowerbonds the diameter of a graph (Chung, 2006), which a connectivity metric that measures the maximum distance between a pair of nodes in the graph. Therefore, if the second eigenvalue is small, the graph will contain nodes that are separated far apart from each other, implying loose connections and more clusters.
To gain more intuition for why a small spectral gap corresponds highly clustered graph, case where the spectral gap is O. A zero spectral gap means that the second smallest eigenvalue of the Laplacian is also O, implying the multiplicity of zero eigenvalues is at least 2. This means that the graph has at least 2 connected components (i.c. at least 2 clusters with no bridge between them).
think about the extreme
C. Spectral Features in the Space of Probabilistic Adjacency Matrices
Clarification on Probabilistic Adjacency Matrix Space Instead of focusing on the properties customized on the graph domain, generalize the graph featured by its adjacency matrix to the more general matrix domains. The eigenvalues or eigenvectors of the matrices could be effective tools to reflect the essential properties. Then there are the following facts that are proved in (Chung& & Radcliffe, 2011):
Theorem C.1. (Properties and Bounds of PAM) For DP defined as the A- D, iee. the expectation of the Degree matrix of the graph whose adjacency matrix A sampled from AP. Let 8 be the minimum expected degree of G. and
T= 1 D-1/2 A-1/2AD-11/ AD2 the (normalized) Laplacian matrix and similarly definition TP= = I- (DP) ->=1
Choose > 0:
for A > In(2n/c). Then with probability at least 1 - c, for n sufficiently large, the eigenvalues of A and AP satisfy
VI visssnMaa xxAA N V4A In(2n/e)
There exists constant l = k(()) such that if > ls In n, then with probability at least 1 - the eigenvalues of T. and LP satisfy
3 3ln(4n/e)
v1 <
3/
8
The above theorem helps us connect the probabilistic matrix space to the graph space with theoretical justification. In particular, the Laplacian matrix could also get a similar definition in the probabilistic space whose eigenvalues could relate to the graph spectrum of sampled discrete graphs.
13

---

Smooth Interpolation for Improved Discrete Graph Generative Models
D. Beyond Simple Undirected Graph
Our experiment shows that GraphBFN could handle the generation of undirected graphs. Furthermore, it could be naturally extended to other types of graphs, and we elaborate on how it could be adapted to them in the following.
Directed graphs Compared undirected graphs, directed graphs differ only in that they do not need the adjacency matrix to be symmetric. In our current implementation, we enforce the symmetricity on the network input E by the operation E. (E + (E%) (E), and on the final sample by Efinal fénal E finat/2. 2. To study the directed graphs, can simply remove these operations.
Weighted graphs For weighted graphs where each edge in the graph is assigned numerical value, the GraphBFN could still be applied by normalizing the numerical value the [0.1] space. In this way, could obtain reformatted adjacency matrix, where entry is set as the normalized numerical value if the corresponding edge exists and O otherwise. Then, we could apply the same objective of GraphBFN to such samples. It should be noted that the weighted graph is hybrid of continuous and discrete variables, we could also use a hybrid GraphBFN for modeling, i.e. continuous BFN for modeling continuous variables and discrete for other discrete types like node and edge types.
Attributed graphs When presenting our methodology. especially when we introduce the probabilistic adjacency matrix, we assume the edge type to be binary (existence and non-existence) for the simplicity of presentation. However, could be noted that the GraphBFN framework could be easily extended to the attributed graphs where the node and edge have categorical attributes, e.g., more than two node/edge types. Furthermore, BFN's effectiveness on this general type of graph has been empirically verified in our experiments molecule generation, where the graphical representations of molecules attributed graphs. Lastly, we could still obtain the topological information under this setting by accumulating the probability of all categories other than the no-edge category to build the probabilistic adjacency matrix space.
E. Algorithms
Algorithm Discrete Variable Bayesian Flow
1: Require: K E R
is the possible state number a discrete variable
2: function BayesianFlow(x I Px. B e I)
3: Y ~ N 1), 3KI)
4: 0 <- softmax(y)
5: Return 0
6: end function
Algorithm 3 Training procedure for one step
1: Require: function3,,t) = S av (t), Be(t)= = 1o (t,, E R, an NeuralNetwork ((-)
2: Input: V Rxxe, E E cx t [0
3: vo: <- BayesianFlow (V.)
4: Ed: +- BayesianFlow E,t)
5: V[o(G ,)), ( [)] (GG (vo, ),,),
6: L = ceto. (t) Eisiisn Egj - ( t)]l + c. fa. Eisis V V.(o(G"
7: Minimize loss L
F. Improved Techniques for GraphBFN
We introduced a more general accuracy scheduling with a simple yet effective formulation as in Eq. 14, we further suppliment a complehensive visualization of the entropy change of the input distribution when a non-uniform prior is used.
As shown in Fig. 3, Our general accuracy scheduling exhibits more steady paces of information reconstruction. This
14

---

Smooth Interpolation for Improved Discrete Graph Generative Models
Algorithm 2 Sampling procedure with Adaptive Flowback
Require: n. Z Cv, Ce E IR, (o))))))))))))))))))))))) (,()),))))) a.))), ar())
denotes the sampling step, N the number of nodes, Ce. Ce is the possible state of node and edge variable, ((-)
the optimized neural network.8 and a the corresponding scheduler functions.e is the predefined constant
2: Initialize: V E with Voh E
3: for = to 7 do
4: t f_
T
5: V[ø (0, E 1)] + (G = (Vo: E ),0)
6:
V.E ~ [V (G ,t)), Categorical Elo((G)) (+))
7:
Ia = 1. =t 1-
8:
if > 2 and Vol(G., (G (p))l 2 then
9:
V E ~ (V V, (t,)) )) ,g (E E, a,t)(t)))
von E. Bayesian Update( Vinn E Vo, Ed) as Eq.
else
12:
L BayesianFllow
(,,.((t)))
13: E + (ayesianFlowwBlo(CC (e,))(
14: end if
15: end for
16: Voo(G" .1). E|o (1]] =V , 1.
17: V, E- Categorical( (Ø(G)) 1)), Categorical G 1)])
Return: V.E
scheduling could be compatible with low-entropy prior, ie. assigning a nonzero accuracy for informative prior, and also have a faster input entropy decrease.
G. A Analysis of the Generation Process
G.1. Transformation of Graph Topology
GraphBFN and the siffusion-based models share the same advantage of gradually recovering the graph topological information in the generation process. However, diffusion-based models experience more fluctuations in recovering graph topology. The instability arises because the denoising steps in these models are conditioned on the atomic samples G' represented in binary adjacency matrices, and such samples could involve significant noises and randomness. In contrast, in GraphBFN, the intermediate steps are conditioned on the input distribution G represented in the probabilistic adjacency matrix, which changes smoothly across the Bayesian update at each time step.
Experiment Setup To verify this discrepancy, we train GraphBFN and the diffusion- based models, Digress and Grums, to overfit a 2-cluster community graph with 20 nodes. The topological information of the graph is captured by the spectral gap, as it reflects clusterability- the most important topological feature of our overfitting sample. Recall that the spectral gap is calculated by taking the difference between the 1st and 2nd cigenvalues of the Laplacian for diffusion- models and the probabilistic Laplacian for GraphBFN. The spectral gaps are measured on the intermediate noisy samples E for DiGress and the input distribution G for GraphBFN, and, for GruM, we use the quantized E,.
Results We plot the changes of the spectral gaps Figure. 4. In this figure, we see that GruM transforms information more smoothly than DiGress but not as smoothly as GraphBFN. Such observation is further confirmed by quantifying smoothness using the following metrics three metrics. The results of these metrics are shown in Table. 6.
Mean Absolute Second Derivative(MASDD) MASD calculates the second derivative of the data, the 2nd derivative Dial
(data;)
then averaged out, and the equation SMASD
Mean Local Standard Deviation(MLSTD) MLSTD computes standard deviation in small window, where, in our
case, the window set to 5 and then averages the local standard deviation. Intuitively, MLSTD captures relatively long-range smoothness in the window.
15

---

Smooth Interpolation for Improved Discrete Graph Generative Models
((t) = 5t
B(t) 3.5t + (5 3.
0.8
Input Dist. Entropy
0.6
0.4
0.2
0.0
0.25
0.5 Time (t)
0.75
1.0
Figure 3: The entropy change of the input distribution G along the Bayesian flow equipped with non-uniform prior.
Table 6: The smoothness of spectral gap transformation in the generation process of GraphBFN and the diffusion-basee basline models
Model
MLSTD(Ie-2)) MASD(Ie-2)
MVar(Ie-2)
DiGress
1.14
0.78
0.65
GruM
1.43
0.79
0.77
GraphBFN
0.39
0.25
0.26
Mean Variation(M Var): MVar calculates the difference between neighboring data points, and we report the average. It emphasizes more on short-range smoothness.
G.2. Advantages of "Smooth" Transformation
We further conduct an empirical study that quantized the benefit of smooth graph topology transformation toward generation quality, thus revealing issues of diffusion-base graph generation models. We follow the same measure of smoothness described in the previous subsection.
Experiment Setup The toy overfitting experiments in the previous experiment does not reflect sample quality well, so in this experiment, we employ a more generalized setting of training on complete dataset. In the first experiment, we train GraphBFN and DiGress (Vignac al., 2022) on the complete SBM dataset (using the best configuration for both) and let each sample 200 graphs with 1,000 sample steps. We then collect intermediate noise samples and compute the smoothness metrics MLSTD and Mar on the spectral gap as in Sec. G. For the final generated samples, we compute the sample quality metrics as in Tab. 1.
Furthermore, we investigate how smoothness transformation correlates with failure cases diffusion bassd approach. We equally partition the 200 samples generated by DiGress into two categories based on the smoothness metrie MLSTD, with one group containing the samples with the bottom 100 MLSTD and the other containing those with the top 100.
16

---

Smooth Interpolation for Improved Discrete Graph Generative Models
0.6
DiGress
Spectral Gap
GruM
0.4
GraphBFN
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Time (t)
Figure 4: Topology recovery of GraphBFN.
Table 7: The study of the advantages of smoothness topology transformation at generation by comparing GraphBFN and the diffusion-basee model DiGress. The smoothness metrics are in the scale of le-2
Model
MLSTD4
MVar 4
Deg. +
Clus. +
Orbit +
Spec. +
V.U.N. 1
DiGress 0.79
0.62
0.0015
0.0512
0.0396
0.0379
73.5
GraphBFN 0.23
0.25
0.0004
0.0509
0.0328
0.0050
90.0
Results According to the results of the above experiments, as shown in Tab. and Tab. 8, it is evident that there is a significant performance gap between the sample groups with different smoothness metrics. By selecting the smoother transformation trajectories during generation, the performance of diffusion- approaches be significantly improved. This finding better justifies the issues of unstable dynamics in traditional diffusion-basel methods.
G.3. Topology Recovery
We conducted similar analysis in Jo al. (2024) the recovery of graph topology in the generation process. The results of GraphBFN shown in Figure. 5. Comparing Figure.2 of Jo et al. (2024), could find that GraphBFN shares with GruM the advantage of more speedy topology recovery, with GraphBFN recovering the graph topology even faster.
H. A Ablation Studies
Output Distribution Conditioning We evaluate the role that the spectral features of graphs play the generation process. We conduct an ablation study on SBM by training GraphBFN with and without conditioning on the features. When conditioning the features, consider extracting the spectral features from GraphBFN's input distribution the output distribution. Results in Tab. 9 show that incorporating information on the spectral features is essential for correctly modeling the internal rules of larger graphs like SBM. Besides, the output distribution could be better source to extract the spectral features as shown by the further boost in performance. This
sources, either from the PAM of the
Table 8: The study of the advantages of smoothness topology transformation at generation through the failure cases of the diffusion-based model DiGress. The smoothness metries are in the scale of le-2.
Model
MLSTDL
MVar |
Deg.
Clus. +
Orbit J
Spec. +
V.U.N. 1
DiGress (original)
0.79
0.62
0.0015
0.0512
0.0396
0.0379
73.5
DiGress (highest 100)
1.04
0.76
0.0018
0.0518
0.0461
0.0450
63
DiGress (lowest 100)
0.54
0.48
0.0007
0.0498
0.0336
0.0212
84
17

---

Smooth Interpolation for Improved Discrete Graph Generative Models
Data
GraphBFN
GraphBFN V.U.N.
100
75
1960
Spec. MMD
10-14
-50
*
25
10-2
0
0
200
400
600
800
1000
Timesteps
Figure 5: A comparison of the transformation of graph topology between GraphBFN and the diffusion-based models, DiGress and GruM. The curves for GruM, DiGress, and others can be found in Figure of Jo et al. (2024).
Table Ablation study on the technique of conditioning GraphBFN's the training and generation processes on the extra graph features drawing from the PMA GraphBFN's output distribution. Experiments on SBM and Planar graph datasets show that this technique boosts performance terms of both generation quality and diversity.
Planar
SBM
Synthetic, |V|
64
Synthetic, 44
[V S 187
Deg. &
Clus. +
Orbit +
Spec. 4
V.U.N. f
Deg. 4
Clus. +
Orbit 4
Spec.
V.U.N. f
Training set
0.0002
0.0310
0.0005
0.0052
100.0
0.0008
0.0332
0.0255
0.0063
100.0
None 0.0647
0.3525
1.695
0.0794
0.0
0.0149
0.0748
0.125
0.0116
0.0
Input Dist.
0.0006
0.0288
0.0013
0.0058
87.5
0.0009
0.058
0.054
0.0057
75.0
Output Dist.
0.0005
0.0294
0.0002
0.0046
96.7
0.0005
0.056
0.037
0.0053
87.5
phenomenon is within expectation because the input distribution models the distribution of each edge in graph independently and thus offers less clear spectral information.
Accuracy Scheduling We experimented with how the accuracy scheduling of GraphBFN impacted its generation results. We set up the experiment on SBM, the abstract graph at scale, and trained GraphBFN with both the original quadratic scheduling and our generalized scheduling, with 331) set to 3.0 and a set to for the generalized. Results in Tab. 10 show that the generalized scheduling could improve the model's performance.
Derivation of BFN over Discrete Variable
To obtain the exact form of the sender distribution, the key is to apply the central limit theorem and take the condition of mw² = a and finite, which implies m - oo and + 0. Also with the first-order Taylor extension could obtain the final result. For a detailed derivation the BFN over discrete variables, we would like to suggest referring to the 1q.148 to 157 in (Graves et al., 2023).
18

---

Smooth Interpolation for Improved Discrete Graph Generative Models
Table 10: Ablation study on different accuracy scheduling of GraphBFN. According to our experiment on SBM, the scheduling with the general accuracy rate function a(t) = a + 2(3(1) - a)t outperforms that with the quadratic rate in the original paper of Graves al. (2023).
SBM
Synthetic, [V] = 187
Acc. Sched. Training Set
Deg.
Clus.
Orbit
Spec. 4
V.U.N.
0.0008
0.0332
0.0255
0.0063
100.0
att) 23(1)t
0.046
0.0574
0,069
0.0081
75.0
at)) a + ((3()) a)t
0.0005
0.056
0.037
0.0053
87.5
J. Proof of Proposition 4.2
We prove the proposition in the following:
Proof. We first prove the loss in Eq. 12 is permutation invariant. To this end, we first prove that
(G G. Go)
GT GG.
(21)
We take the same decomposition as in Eq. 11 of the term y (G G, G%)::
E E, ) = 11 Hssssnn
1 E. B%g
q (v&: V, vo) = Hssign (v. Ve. v.o)
(G G, G.
(E* E, E.) (v% V V.)
(22)
We take the q (V+: V, Voo) as example:
q (T VV, x Vo) = ग (llisinog (V.+ V., V²o) Misignd (v.) Vi, v.o)
(v V, vo))
(23)
Similar derivation could be applied to E. And hence could finish the proof.
Next, we take the L(V, t) as example to prove L(V, t) I(xV.t) f):
1 L( () = ( a.,
Σ
||V - V, ( [4] !]]
(24)
o( G G
Isign
For simplicity, we focus on the term related to RT, as o is permutation equivariant, we have
E
Σ
VV
V, (T ,]]]|
E
Σ
|V, - v,, [ (G ()))))]
(GG%//.G
E
T(
Σ ISi
|V. v. (G +]]1=
E
Σ I5i5
||. V, p (G ,I]
(25)
G
Then we could also apply the same process E. Then we finish the proof over permutation invariance of the loss function.
Next, we discuss the invariant density modeling of the Pa- This could be directly following the conclusion of Theorem 3.1 of Song et al. (2023). With permutation invariant prior G and a permutation equivariant interdependency network o, we only need to make sure the Bayesian Update function h is permutation equivariant. As we could find in Eq. 7.
e 0
h(T0,-1, Ty:) = 7(
= 7/((0-11 Vo)
(26)
Σ
(3) 2 1=
m
And then we could finish the proof.
19

---

Smooth Interpolation for Improved Discrete Graph Generative Models
K. Comparison with Diffusion-Based Approaches
K.1. Comparison with Diserete Diffusion Methods
The key intuition held by Bayesian Flow NeIworks(BFN) (Graves et al., 2023) is that the information in the generative process should be modeled in a smoothly increasing fashion for superior performance. Such intuition is shared by the BFN and diffusion in the continuous data and is also identified by several studies under the literature of diffusion models for image generations (Ho et al., 2020). GraphBFN is motivated by the compatibility of such "continuous information modeling" intuition and the special nature of graph data: that is, though generally represented in the discrete modality, the essential graph topology information could also be represented in the continuous manifold as implied by graph spectrum. This allows GraphBFN to better harness the inductive bias in modeling discrete data modality with continuous natures, compared to the previous discrete diffusion models (Vignac et al., 2022). Furthermore, compared to the methods that directly dequantized the data and applied continuous diffusion models, the GraphBFN needs no quantize/dequantize procedure and could be more compatible with the sparse adjacency matrix representation.
There are also some potential empirical advantages of GraphBFN. The input to the neural network of GraphBFN lies in the continuous manifold, which could enjoy the advantages of numerical stability. More importantly, the inputs to the continuous distribution hold considerably small variance compared to the previous discrete diffusion models (Graves et al., 2023). Also, such properties could lead to a speed-up in convergence during training.
K.2. Comparison with Diffusion Methods modeled within a Bounded Space
Beta diffusion models (Zhou et al., 2023; Liu et al., 2025) present a compelling alternative to the widely used Gaussian diffusion models (Ho et al., 2020; Jo et al., 2022). Like the Gaussian counterparts, it admits analytical forms for the marginal and conditional distributions of the diffiusion process. However, it offers the added advantage of modeling variables within a bounded domain between and I, which Gaussian diffusion does not naturally support. This boundedness is particularly beneficial in discrete settings such as graph generation, where the data is inherently constrained. Therefore, Graph Beta Diffusion (GBD) (Liu et al., 2025) is similar to GraphBFN in the sense that they both preserve the constrained nature of discrete graphs while modeling the evolution of continuous quantities.
Nevertheless, we would like to highlight the key similarities and distinctions between GraphBFN and GBD.
In the case of abstract graph generation, where there are only two edge types (has edge & no edge), it suffices to represent each entry of adjacent matrixes with a single variable within the range [O, 1J. In this simple setting, the variables modeled by GBD could be interpreted as the probability of edge existence. Therefore, both GBD and GraphBFN share the similar property of modeling the smooth interpolation of probabilistic matrices, although they differ in specific probability trajectories. As the results in Table indicate, both GBD and GraphBFN could obtain superior performance compared to the discrete-state- space models (e.g., DiGress (Vignac et al., 2022)) in abstract graph settings, which justifies the advantages of smooth interpolation, as we claimed.
However, for graphs with multiple edge types (c.g., molecular graphs), the modeling of GraphBFN and GBD have non- negligible differences. When the adjacency matrix contains i edge types, GraphBFN represents each matrix entry as a k-dimensional probability vector that lies on the simplex (i.e., the vector components sum to 1), making each dimension interpretable as the probability of particular edge type. In contrast, GBD models each dimension independently as value in [O, 1]. without enforcing normalization. The trajectory over simplexes of GraphBFN makes it more natural choice to model multiple-class discrete variables by making different dimensions contrastive. As the results in Table 2 indicate, GraphBFN achieves notably stronger performance in this setting, which justifiies the potential of simplex-bssed approaches in modeling multi-class discrete graphs.
L. Experiment Details and Additional Results
L.1. Experiment Details
The datasets, dataset splits, and evaluation metrics of QM9 with explicit hydrogen and MOSES follow from Vignac et al. (2022), those of SBM, Planar, QM9 with implicit hydrogen, and ZINC250K follow from Martinkus et al. (2022), and those of Community-small Ego-small, and Protein follow from Jo et al. (2022).
The network architectures and settings directly followed Vignac et al. (2022); Jo et al. (2024). The models are trained with
20

---

Smooth Interpolation for Improved Discrete Graph Generative Models
the A optimizer (Loshchilov & Hutter, 2019) until convergence. The most sensitive hyperparameters of GraphBFN SE and By that control the speed of information transmission in the generation process. We search them in the discrete linear space {1.0, 2.0,-. ..,,,................ 10.0}.
For all of our experiments, we use NVIDIA GeForce RTX 3090 with 24GB memory to train and evaluate our models, The batch sizes are adjusted to the maximum that can fit within the memory constraint.
All of our reported results are the average of three random runs, For a cleaner presentation and to follow the convention of previous work, we only add the error terms to the result of QM9 with Explicit Hydrogen.
For the results of QM9 with Explicit Hydrogen in Tab. 4, only compare to other method because, to our best knowledge, DiGress (Vignac et al., 2022) is the only previous graph generative model that has attempted model QM9 molecules with explicit hydrogen.
We use extra features for the inputs of the Graph Transforrnrr which directly follows (Vignac et al., 2022). Specifically, we have included cycle counts using pre-determined formulas to efficiently calculate cycles up to size 6. Node features count participation in up 5-cycles, while graph features tally up to 6-cycles, utilizing node degree vectors and the Frobenius norm. Additionally, we integrate spectral features, which involve an O (n²* gggendecompoiiioon-manne for our graphs with up 200 nodes. Key graph-level features derived from the graph Laplacian include the number of connected components and the first five nonzero eigenvalues. Node-level features estimate the largest connected component and include the first two eigenvectors associated with nonzero eigenvalues.
Extra Features:
Each spectral feature or structural feature could be categorized into node-level features and graph-level features. Specifically, a node-level feature holds the shape of match-off-graphe node-in-gee aade-in-graph), such as an estimation of the biggest connected component (using the eigenvectors associated with eigenvalue 0): ; a graph-level feature holds the shape of (batch-of-graphs 1). After computing the node-level features F F_n and graph-level features F_g based on V and E we concat V and all F node representations V feat. and concat all F _ the finally graph-level feature y. Then the inputs for the graph transformers in GraphBFN are the triple of (V V__aet., E y) similarly to Digress (Vignac et al., 2022)
Scheduling Function: In short, our scheduling design in Eq. 14 is an improvement upon the original design in vanilla BFN (Graves et al., 2023) that is determined empirically based on the intuitive of linearly increased entropy. Our design attempts to change the con-informative prior to the original design to be informative.
In Eq. 14, (() is the accumulative(interaa of (x) from f). The key intuition behind the design is that for informative prior, the initial step 0 already contains information of the ground truth sample. Then set (0) to positive constant Besides, we also follow the heuristic of vanilla BFN (Graves et al., 2023) to use the square scheduler for accumulated accuracy 3 to ensure the entropy of the input distribution approximately changes linearly along the timesteps. Eq. 14 is a very simple form that satisfies both properties.
21

---

Smooth Interpolation for Improved Discrete Graph Generative Models
L.2. Computation Efficiency
Training time for QM9 takes approximately 3 hours, and for large molecules and abstract datasets, the longest train- ing takes days.
Table 11: Comparing GraphBFN with other multistep genera- tion methods on the time to Sample 10, 000 QM9 with Explicit Hydrogen Graphs.
For the inference efficiency, conducted experiment that compares GraphBFN with two other multi-step graph generation models DiGress (Vignac et al., 2022) and GruM (Jo et al., 2024). We record the time for each model to sample 10000 graphs of QM9 with explicit hydrogen with the same sampling steps of 500, The results are shown in the Tab. 11.
Sampling Time (min.)
DiGress GruM GraphBFN
40
35
44
According the results, GraphBFN has approximately the same inference speed as the other two diffusion- based models. This result is expected, as all three methods require only one network evaluation at each iteration. GruM enjoys the fastest sampling speed. We speculate that this is because GruM operates in the space of continuous data, so it does not require the relatively costly procedure of sampling from categorical distributions.
Table 12: Additional results on smaller datasets. Most baseline performances are adapted from (Jo et al., 2022) and (Kong et al., 2023). Hyphens(-) denote unobtainable results due to either the reasons mentioned in (Jo et al., 2022) or the lack of official implementation.
Ego-small
Community small
Enzymes
Real, 4 s [V] < 18
Synthetic, 12 < [V] S 20
Real, 10 S [V] S 125
Deg.4
Clus.
Orbit
Deg-t
Clus.
Orbitl
Deg.t
Clus.t
Orbit
Training set
0.002
0.021
0.005
0.02
0.07
0.01
0.0003
0.01079
0.0003
De
0,040
0.100
0.020
0.220
0.950
0,400
GraphRNN
0.090
0.220
0.003
0.080
0.120
0.040
0.017
0.062
0.046
Autoreg.
GraphAF
0.03
0.11
0.001
0.18
0.20
0.02
1.669
1.283
0.266
GraphDF
0.04
0.13
0.01
0.06
0.12
0.03
1.503
1.061
0.202
Graph VAE
0.130
0.170
0.050
0.350
0.980
0.540
1.369
0.629
0.191
GNF
0.030
0.100
0.001
0.200
0.200
0.110
EDP-GNN
0.052
0.093
0.007
0.053
0.144
0.026
0.023
0.268
0.082
GDSS
0.021
0.024
0.007
0.045
0.086
0.007
0.026
0.061
0.009
One-shot
SPECTRE
0.078
0,078
0.007
0.020
0.210
0.010
0.136
0.195
0.125
DiGress
0.015
0.029
0.005
0.020
0.063
0.010
0.004
0.083
0.002
EDGE
0.008
0.011
0.026
GraphARM
0.019
0.017
0.010
0.034
0.082
0.004
0.029
0.054
0.015
HiGen
0.012
0.038
7.2e-4
GraphBFN
0.0034
0.0246
0.0057
0.0075
0.0095
0.0043
0.0064
0.0212
0.0051
L.3. Additional Results on Non-attributed Graphs
In Tab. 12, we provide results on non-attributed (i.e. graph with only one edge type and node type) graph datasets, along with comparisons to additional baselines (Chen et al., 2023; Kong al., 2023; Karami, 2024). Community-smai contains 100 randomly generated clustered graphs; Ego-small contains 200 small ego graphs; and Enzymes contains 587 chain-like graphs representing protein structures (Jo et al., 2022).
According to the table, GraphBFN has shown superior performance on Community and competitive performance on Ego-small and Enzymes. It should be noted that for -ommunity-small and Ego-small, the metrics are very saturated due to the limited complexity of datasets; as we can see, the SOTA results are very close to the training set's performance.
22

---

Smooth Interpolation for Improved Discrete Graph Generative Models
L.4. Code
More specific details about the experiment setting and our implementation GraphBFN can be found in our code http:p/www........ec//ooo/oottta
M. Flowback Sampling
The visualization of GraphBEN's generation process with the Flowback technique is in Figure.
Flowback
0.0
Time (t)
1.0
Figure 6: Visualization of GraphBFN's generation process with the Flowback technique. The sample graphs in the first row are sampled from the output distribution @ò( O 1) at different time steps, while those on the second line are representations of the probabilistic adjacency matrix the input distribution G The solid lines denote the network prediction, while the solid line denotes the flowback Bayesian update.
N. Derivation from Eq. 7 to Eq. 10
Here we provide a formal derivation of the Bayesian Flow Distribution (Eq. 10) which is essentially the Eq. 172 to Eq. 185 BFN (Graves al., 2023). Firstly, we consider marginalizing the y from the sender distribution with the Bayesian update function in Eq. which results in distribution over term as Bayesian update distribution:
(0 Pu (0) 0,)1,x;a)= (kllaKKe=1).ok) (o
e 0
E
8
(27)
Σk Cr (0
(0.-1))
-k=1
Then we derive the additive accuracy property with two consecutive Bayesian updates of noisy samples ya M (aa (Ke, - 1), an KT) and yb ~ N (as (Ke, -1) 1),,),k KTK as:
exp (vb) ΣK exp (Wa)) )(8-22)r
oxp(y=)0:-
h (y,, h (Ya. 02-2))
ΣK exp ((1b) v ΣR_, expl (ep((()))) )00= (0=-2)
exp((vo (0, 2)
exp (yb) exp (ya) 0i-2
Σ K -= exp ((yb) ab) exp (ya))) (0;-2)
(28)
exp (Va yb) 0:-2
k= exp ((y,, + vb)x) (0.2)xx
h (Ya yo, 0.-2).
With the property of Gaussian distribution, we have that:
Ya + N ((a, + an) (Kex - 1), (a. + as) KI).
(29)
Then the two-step update could be actually merged into one-step update of added accuracies, i.e.:
E
pu (0: 0 0;-1,x;00) Pu (0; 0;-2, x; 0a + ab)
(30)
Po - (0.0...__.
23

---

Smooth Interpolation for Improved Discrete Graph Generative Models
The the Bayesian flow distribution in Eq. 10:
P6 x;t)
E
PG (0,, O 0n-1, x; 0k.) pu On
Oo.
x;
04
(31)
per (0. pp (1:000))
pu (0 p
Note Σi=1 0g could be substituted as (t) as the integral of the a(t) from 0 to t in the continuous setting. Substituting Eq. 27 into Eq. 31, we could obtain that:
(0
e 0
Pp x; (ivl Changing the notation from y, 0 to E and E, we could finish the derivation.
E
(32)
2k=1 ex (0o)
O. Further Discussion over Adaptive Flowback
The generative process of BFN all start with the same initial points, e.g., vector [ ... .. for k-class discrete variable, and ends with various generated samples. Hence, the variance of the input distribution first grows and then decreases [2), which could be intuitively understood as first exploring the endpoint of the generative process and then finetuning towards that endpoint. Motivated by this fact, we suggest that when the generative endpoints are approximately determined, it could be more favorable to eliminate the extra variance in from sequential Bayesian Update and only focus on finetuning based on the Bayesian flow of the current step output prediction. The condition of || (G",,) é (G" 1, 1,t- test whether the predicted outputs of two consecutive steps are close enough, i.e. whether the steps and steps - 1 are generated towards the same targets. We use this as an indicator for whether the generation process is in a variance increase (exploration) or a variance decrease(finetuninng) state.
(tt-1)] 1)ll 2 is to
P. Continuous-state Approaches or Discrete-state Approaches for Graph Generation
There have been several works making notable progress in continuous state-based methods, specifically spectrum- baaed approaches such as (Martinkus et al., 2022; Luo et al., 2023). More recently, several discrete state-based approaches that directly model the discrete variable of edges/nodes, e.g. (Vignac et al., 2022; Jo et al., 2024), have shown that combining the continuous state (c.g., spectrum) as an extra feature, the discrete state approaches could further achieve better results.
There is the particularity of graph data, whose form discrete and important property enjoys continuity. And current empirical evidence (Vignac et al., 2022; Jo al., 2024) suggests it could be favorable to take both into consideration. The motivation for choosing BFN lies in the fact that it could actually model the discrete variable in continuous categorical parameter space, which perfectly fits the discrete form and continuous property of graph data.
Additionally, though GraphBFN lies in the category of discrete state approaches, we would like to clarify that there is still a lot of research in the field to be conducted to finally answer the discrete or continuous question.
Q. Relationship to Spectral Graph Theory
Here we hope to provide a more detailed discussion of the relationship of proposed methods to spectral graph theory. The framework aims to introduce new generative method that forms in the discrete state space and takes the intrinsic continuity of the topological information into consideration. The spectral graph theory provides an effective tool for us to implement and analyze the proposed approach.
From the implementation perspective, we use the spectral features of the input to enhance the network prediction follow- ing (Vignac et al., 2022). During both training and sampling, the spectral features of the parameters of the graphs are computed and directly appended the network as additional inputs.
Additionally, we use spectral theory to help analyze one key reason behind our method's performance improvement compared to previous approaches: the smooth transformation of graph topology leads to enhanced sample quality. As demonstrated in the ablation study in Appendix F, we use clustered graphs as an example to show that, for both diffusion- based methods and GraphBFN, a smoother transition of the sample's spectral features such as the spectral gap in the case of clustered graphs graphs-during during the generation process significantly improves sample quality.
24

---

Smooth Interpolation for Improved Discrete Graph Generative Models
R. Visualization of Generated Samples
NH
OH
HO
OH
Figure 7: Explicit Hydrogens
Figure 8: Implicit Hydrogens
Figure 9: Unfiltered samples generated by GraphBFN, trained on QM9
25

---

Smooth Interpolation for Improved Discrete Graph Generative Models
Figure 10: Planar
Figure 11: SBM
Figure 12: Unfiltered samples generated by GraphBFN, trained on abstract graph datasets
qajo plam
Figure Unfiltered samples generated by GraphBFN, trained on ZINC250K with implicit hydrogens
Figure 14: Unfiltered samples generated by GraphBFN, trained on MOSES graphs
26


Reviews:
[{"review_id": "gF2Jc83YLS", "reviewer": "Reviewer_xE9B", "summary": "The paper introduces Graph Bayesian Flow Networks (GraphBFN), a generative model for graphs based on Bayesian Flow Networks. The key idea is to represent the graph structure in a continuous latent space to generate discrete graphs more smoothly. In other words, instead of working directly with the adjacency matrix of a graph, the model creates a continuous representation of the graph structure using a probabilistic distribution. The paper also introduces a new sampling method, Adaptive Flowback, to reduce the train-test discrepancy.\n\n**Update after rebuttal**\nThe rebuttal brings some helpful clarifications but does not change my overall assessment of the paper, which was already positive.", "questions": "", "limitations": "", "rating": 3, "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": "> **W2: Towards how spectral features are used and how they improve the model**\n\nWe apologize for the confusion. Our use of extra features—including both spectral and structural—follows the setup in prior work [1]. The key difference is that GraphBFN computes these features over the output distribution $\\phi(G^{θ_t, t})$, a probabilistic matrix, instead of noisy intermediate samples.\n\nWe first clarify how extra features are used and implemented in the model. Each feature is categorized into node-level features and graph-level features. For graph-level features, we use\n1. graph level counts of cycles,\n2. the multiplicity of the eigenvalue 0, and\n3. the first 5 nonzero eigenvalues of the graph Laplacian.\n\nFor node-level features, we use \n1. node level counts of cycles.\n1. the eigenvectors corresponding to eigenvalue 0 and\n2. the first two eigenvectors associated with nonzero eigenvalues.\n\nFor molecular graphs, we include an additional graph-level feature — the molecular weight — and a node-level feature — the valency of each atom.\n\nThese choices follow DiGress [1]; more details are in their Appendix B.\n\nHow the extra features are used is included in Appendix.L.1, \"Experiment Details\". In short, we compute the extra features of intermediate samples and append them to network input.\n\nNext, we demonstrate the importance of extra feature conditioning via additional ablation studies. Specifically, we evaluate the performance of both GraphBFN and DiGress with and without extra feature conditioning on the challenging QM9 with explict Hydrogens dataset. The results are summarized in the table below.\n|Model|Val.(%)↑|Uni.(%)↑|A. Stab.(%)↑|M. Stab.(%)↑|\n|---|---|---|---|---|\n|Train. Set|97.8|100|98.5|87.0|\n|DiGress + no feature|92.3|97.9|97.3|66.8|\n|DiGress| 95.4|97.6|98.1|79.8|\n|GraphBFN + no faeture|96.9|98.1|99.1|90.5|\n|GraphBFN|99.2|94.9|99.4|94.7|\n\nWe observe that extra feature conditioning improves performance across all evaluation metrics for both models, showing its impact on enhancing molecular graph generation.\n\n[1] Vignac, et al., 2022 \"DiGress: Discrete Denoising diffusion for graph generation.\"\n\n> **W1&Q1: Regarding the final discretization of probabilistic matrix and post-processing**\n\nThank you for pointing out the ambiguity in our implementation detail. Yes, that’s correct—at the final step, discrete samples are obtained by directly sampling from the predicted probabilistic matrix (or node probability vectors). We do not employ any specialized discretization technique for all datasets; instead, we sample faithfully from the categorical distribution defined by the output distribution $\\phi(G^{θ_1, 1})$. We also did not filter or curate our samples (e.g. forgo unconnected samples), in order to remain consistent with the evaluation procedures used in prior works.\n\nThe sampling details are depicted in Algorithm 2. Specifically, we sample from output distribution $\\phi(G^{θ_1, 1})$ of the graph, which is split into two components: $V[\\phi(G^{θ_1, 1})]$ for nodes and $E[\\phi(G^{θ_1, 1})]$ for edges. The node tensor $V[\\phi(G^{θ_1, 1})]$ has shape [bs,N,$c_v$], where $c_v$ is the number of node types. For instance, $V[\\phi(G^{θ_1, 1})]$[1,1] is a categorical distribution representing how the first node of the first sample is distributed. Similarly, the edge tensor $E[\\phi(G^{θ_1, 1})]$ has shape [bs,N,N,$c_e$], where $c_e$ denotes the number of edge types. Sampling is performed independently for each node and edge from the corresponding categorical distribution defined by the last dimension.\n\nWe have not explored alternative discretization strategies beyond direct sampling from the categorical distribution. This choice preserves the unbiased nature of our probabilistic modeling and maintains a good balance between sample quality and diversity. However, we believe that exploring alternative sampling strategies, like top-k or top-p, may be useful for tasks with specific demand, such as favoring higher fidelity at the expense of diversity.\n\n> **Towards Additional Comments**\n\nThank you very much for your detailed feedback. We will carefully incorporate your suggestions in future revisions.\n\nNode colors in Figure 1:\n- Apologies for the confusion. The node color reflects a spectral metric used to highlight clusters, originally meant to enhance visualization for structured graphs like SBM samples. We recognize this may be misleading and will either remove the coloring or clarify it in the caption.\n\nMissing curves for DiGress and GruM in Figure 5:\n- Apologies for the confusion. The study in Appendix G.3 replicates GruM [1]’s analysis of topology recovery. The curves for GruM, DiGress, and others can be found in Figure 2 of the GruM paper [1]. We’ll clarify this in the caption in the next version.\n\nTypo in “A few entries…”\n- You’re right—this was a typo. There should be a NOT before \"reported.\" We’ll correct this in the next draft.\n \n\n[1] Jo, et al., 2024 \"Graph Generation with Diffusion Mixture.\"", "claims_and_evidence": "The paper claims that GraphBFN improves graph generation compared to discrete diffusion-based models, demonstrating competitive performance in experimental benchmarks. However, some aspects require further clarification, such as spectral conditioning.", "methods_and_evaluation_criteria": "The experiments are conducted on standard benchmarks such as Planar, SBM, QM9, and ZINC250k, which are standard datasets for evaluating generative graph models.\nThe evaluation metrics are consistent with the existing literature.", "theoretical_claims": "The proof of Proposition 3.2 in Appendix J, about the invariance of the model’s optimization objective and generative density function under node permutations, appears to be correct, although I have not analyzed the entire proof in detail.", "experimental_designs_or_analyses": "The experimental design should be explained more precisely in the appendix rather than simply stating that the setting from another paper was adopted.", "relation_to_broader_scientific_literature": "The paper is well connected to recent works on diffusion-based models for graph generation.", "essential_references_not_discussed": "Huang, H., Sun, L., Du, B., Fu, Y., & Lv, W. (2022, November). Graphgdp: Generative diffusion processes for permutation invariant graph generation. In 2022 IEEE International Conference on Data Mining (ICDM) (pp. 201-210). IEEE.\n\nMinello, G., Bicciato, A., Rossi, L., Torsello, A., & Cosmo, L. Generating Graphs via Spectral Diffusion. In The Thirteenth International Conference on Learning Representations.\n\nYang, L., Huang, Z., Zhang, Z., Liu, Z., Hong, S., Zhang, W., ... & Zhang, L. (2024). Graphusion: Latent diffusion for graph generation. IEEE Transactions on Knowledge and Data Engineering\n\nZhou, C., Wang, X., & Zhang, M. (2024). Unifying generation and prediction on graphs with latent graph diffusion. Advances in Neural Information Processing Systems, 37, 61963-61999.", "other_strengths_and_weaknesses": "The final discretization process of the adjacency matrix requires a more detailed explanation.\n\nSpectral conditioning is mentioned in Conditioned Graph Features on Output Distributions, but it is unclear which features are used and how they improve the model.", "other_comments_or_suggestions": "- In Table 1, I suggest underlining the second-best results to help the reader with comparisons.\n- I recommend adding more detailed descriptions in the captions, at least in the main text.\n- From the Experiment Details section, it is unclear how the experiments were conducted. For instance, when computing MMD, you compare a generated graph set with a reference set. How large are these sets?\n- I suggest moving Related Work after the Introduction.\n- There are several instances where capital letters appear incorrectly after a comma or colon (e.g., “Due to space limit, We defer…”). It would be beneficial to check for these typos.\n- It is unclear where and when the graph spectrum is used. The Abstract states:\n“Though typically represented by the discrete node and edge attributes, the graph topological information can be sufficiently captured by the graph spectrum in a continuous space.” This initial sentence could suggest that the model operates directly on the matrix of eigenvectors, and this impression remains in the reader’s mind, even though the rest of the text does not support it. I recommend clarifying it throughout the text, especially at the beginning, and explicitly distinguishing when the spectrum is used as part of the method and when it is only used for evaluation, as in Figure 1.\n- What do the node colors represent in Figure 1?\n- In Figure 5, “A comparison of the transformation of graph topology between GraphBFN and the diffusion-based models, DiGress and GruM,” are the curves for DiGress and GruM missing?\n- There is a visualization issue: a floating letter “t” appears above Table 5 and Table 6.\n- Is this sentence correct? “A few entries are left as blank because the corresponding experiment results are presented or implemented in the original work.” What does it mean?\n- “To improve conciseness, we use the adjacency matrix E” is an unconventional choice, as “A” is typically used for the adjacency matrix, while “E” is commonly associated with the edge list.\n- The following metrics require better explanation: FCD, SNN, Scaffold Similarity (Scaf), NSPDK, Novelty, and Validity.\n- Figure 1 could be improved.", "questions_for_authors": "The sentence “each entry P_{i,j} could be seen as the parameter of the Bernoulli distribution” suggests that the final discretization of the probabilistic matrix is performed through Bernoulli sampling. However, it is not explicitly stated whether this is the actual step or if other strategies (e.g., thresholding, structural constraints) are applied.\n- Are there additional post-processing steps (e.g., ensuring connectivity, removing isolated nodes)?\n- Have you compared different discretization strategies to assess their effect on the generated graphs?", "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": "oAlaMaeeT1", "reviewer": "Reviewer_Ujzh", "summary": "Graph Bayesian Flow Networks (GraphBFN) introduce a new way to generate graphs using continuous latent variables. Unlike traditional models, GraphBFN smoothly transitions from a starting state to the desired graph by mapping these variables to a probability matrix. This approach efficiently models complex graphs, supports various features, and is faster than previous methods. Experiments show GraphBFN creates realistic and accurate graphs.", "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": "> **W1: Lack of error bar in results**\n\nThank you for the catch. We apologize for not making clear the inconsistent appearance of error terms in the paper. Actually, all reported results are averages of 3 runs. We omitted error terms for readability and because baseline results in prior work did not include them. Detailed results with the error bound for all datasets are summarized in the tables below.\n\n|Dataset|Deg.|Clus.|Orbit|Spec.|V.U.N.|\n|---|:-:|:-:|:-:|:-:|:-:|\n|Planar|$0.0005\\pm0.0002$|$0.0294\\pm 0.0163$|$0.0002\\pm0.0001$|$0.0046\\pm0.0013$|$90.0\\pm3.3$|\n\n|Dataset|Deg.|Clus.|Orbit|Spec.|V.U.N.|\n|---|:-:|:-:|:-:|:-:|:-:|\n|SBM|$0.0005\\pm0.0001$|$0.0560\\pm0.0392$|$0.0370\\pm0.0163$|$0.0053\\pm0.0005$|$87.5\\pm4.0$|\n\n|Dataset|Valid|FCD|NSPDK|Scarf.|\n|---|:-:|:-:|:-:|:-:|\n|QM9 without H|$99.73\\pm0.16$|$0.101\\pm0.017$|$0.0002\\pm0.0000$|$0.9386\\pm0.0980$|\n\n|Dataset|Valid|FCD|NSPDK|Scarf.|\n|---|:-:|:-:|:-:|:-:|\n|ZINC250k|$99.22\\pm0.49$|$2.116\\pm0.327$|$0.0013\\pm0.0006$|$0.5304\\pm0.1980$|\n\n|Dataset|Val|Unique|Novel|Filters|FCD SNN|SNN|Scaf.|\n|---|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|MOSES|$88.5\\pm2.9$|$99.8\\pm0.2$|$89.0\\pm3.3$|$98.3\\pm0.8$|$1.07\\pm0.11$|$0.59\\pm0.11$|$10.0\\pm1.8$|\n\n|Dataset|Val.(%)↑|Uni.(%)↑|A.Stab.(%)↑|M.Stab.(%)↑|\n|---|:-:|:-:|:-:|:-:|\n|QM9 with H|$99.2\\pm0.1$|$94.9\\pm0.5$|$99.4\\pm0.0$|$94.7\\pm0.4$|\n\n\n> **W2: Motivations for Bayesian Flow Networks(BFN)**\n\nThank you for the valuable feedback. We agree that the motivation for choosing BFN can be further clarified. \n\nThe rationale stems from our desire to design a 'smooth' generation/training trajectory is motivated by the recent advancements in the research field of diffusion-based approaches [1,2,3], where the signal noise ratio is widely set as a smooth transformation with respect to timesteps. This implies the information should be gradually decomposed in the forward transformation to provide dense supervision. However, for graphs that lie in discrete state space, the discrete nature makes it challenging to gradually decompose the information using discrete-state diffusion models (like DiGress and DisCo [1,3]), where the noisy graphs are created by operations such as deletion(masking) and replacement and these small perturbations can lead to abrupt structural changes (e.g., loss of connectivity or altered clustering).\n\nBFN offers a compelling alternative by operating in a continuous categorical parameter space, which aligns naturally with the discrete form yet continuous property of graph data.\n\nFurthermore, from the perspective of utilizing the inductive bias of graph data, the most advanced graph generation methods[1,4] have demonstrated the effectiveness and importance of utilizing the graph spectrum as either the auxiliary conditions or learning objectives. The smooth transformation in GraphBFN respects the local geometric and topological properties of the graph, which means that similar nodes remain similar throughout the transformation. Hence, it could provide better spectrum conditioning for neural networks. From the perspective of neural network optimization, smooth transformations avoid abrupt changes and can facilitate more stable training dynamics. Thus, gradients are less likely to explode or vanish, leading to more reliable and efficient learning.\n\n[1] Vignac, et al., 2022 \"DiGress: Discrete Denoising diffusion for graph generation.\"\n\n[2] Jo, et al., 2024 \"Graph Generation with Diffusion Mixture.\"\n\n[3] Xu, et al., 2024 \"Discrete-state Continuous-time Diffusion for Graph Generation.\"\n\n[4] Martinkus, et al., 2022 \"SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators.\"\n\n\n> **Towards additional comments**\n\nThank you for your comments. We will incorporate them in future revisions.\n\nRegarding your second comment, could you please clarify the intended question?\n\nIf you’re referring to the difference between “timesteps” in Figure 5 and “sampling steps” in Table 7, we’re happy to clarify. Figure 5 shows Spec.MMD was evaluated on noisy intermediate samples during generation. “Timestep” refers to a specific point in a sampling trajectory—each curve point corresponds to a sample at a different noise level.\n\nTable 7 shows an ablation study on how reducing the number of sampling steps affects final sample quality. Each row corresponds to a run with a different step count. The first column shows the percentage of default steps used, standardized across datasets. For example, (10, Planar) means using 10% × 1000 = 100 steps.\n\nIf you’re asking about the DiGress and GruM curves in Appendix G.3, we apologize for the confusion. That study replicates GruM [1]’s analysis of graph topology recovery during generation. The corresponding curves for GruM, DiGress, and other baselines appear in Figure 2 of the GruM paper [1]. We’ll clarify this in the figure caption in the next version.\n\n[1] Jo et al., 2024. Graph Generation with Diffusion Mixture.", "claims_and_evidence": "The paper is easy to follow and extensive experiments demonstrate the effectiveness of Bayesian flow method on graph modeling.", "methods_and_evaluation_criteria": "The proposed method follows the widely used evaluation process.", "theoretical_claims": "I have checked the algorithm related to Bayesian flow method in Appendix E.", "experimental_designs_or_analyses": "This paper provides extensive experiments on graph modeling task, as well as detailed ablation study on schedule, crucial hyperparameters 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 for Bayesian flow method in graph modeling and theoretical foundation for this as well.", "essential_references_not_discussed": "Bayesian flow based", "other_strengths_and_weaknesses": "## Strengths\n- The paper proposed Bayesian flow based graph generative framework, a novel graph generative model attempting to capture the discrete data distribution with smooth interpolation.\n- The paper makes huge efforts on adapting Bayesian flow network on graph modeling through careful design of schedule and sampling strategy.\n-  Flowback is interesting.\n- Extensive experiments show the GraphBFN's ability on various graph modeling tasks and the model exhibits good performance across all benchmarks.\n\n## Weaknesses\n- Lack of error bar in general graph generation. \n- The choice of a Bayesian flow network is unclear.", "other_comments_or_suggestions": "- ICLR -> ICML in Ethics Statement\n- In appendix G.3, how the number of steps in Topology Recovery.", "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": "xT2SQdAHbN", "reviewer": "Reviewer_eFTn", "summary": "The paper introduces Graph Bayesian Flow Networks (GraphBFN), a novel framework for discrete graph generation that enables smooth interpolation between graph states. Unlike discrete diffusion models, GraphBFN leverages probabilistic adjacency matrices and Bayesian flow updates to improve stability and efficiency. Several techniques are also proposed to improve the proposed frameworks.\n\n## update after rebuttal\nThe rebuttal of the author brings additional insights to the broader implication of the methodology, but it does not impact the overall assessment of the paper (which was positive in the first place).", "questions": "", "limitations": "", "rating": 3, "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": "> **Q1: Towards the choice of Generative Framework**\n\nThank you for your thoughtful and insightful comments. We first clarified our motivation for choosing the BFN as our model framework. As you mentioned, we use discrete diffusions as a case study to reveal a specific challenge in the discrete graph generative model, i.e., the fluctuation in the training dynamics. Firstly, the challenges are not limited to the scope of discrete diffusion models. For multi-step generative models, such as discrete diffusion/discrete flow matching[1], the fluctuation in the training trajectory originated from discrete space and the properties of discrete graphs.  Moreover, the challenge could actually be generalized as to creating a trajectory from the prior to target distribution of a discrete graph that smoothly decomposes information and provides dense supervision.\n\nThere are several possible solutions, but actually remain an open research problem.  Under the context of the diffusion framework,  encoding the graphs to latent space and hybridizing the latent and discrete diffusion could be a possible solution to keep the discrete nature and build smooth trajectories. However, these approaches generally require training a well-performed encoder/decoder to make it work in practice, which brings a huge computational cost and system complexity. Compared to the diffusion framework, we choose BFN mainly due to its simplicity. BFN achieves smooth interpolation based on the introduced parameter space. Analog to the latent space for diffusion, the parameter space could be seen as a special non-parametric latent space, which is implied by a Bayesian update instead of a trained encoder. Our empirical studies show that parameter space enables the interpretation of natural data properties. We agree that there could be improved space for further exploring and tackling the challenges under various model frameworks, and we will add the discussion to the updated version.  \n\n[1] Lipman et al., 2023 “Flow Matching for Generative Modeling.”\n\n> **Q2: Towards how to characterize a hybrid model**\n\nThanks for your insightful comments! This is a very good question.\nFirstly, we discuss how to characterize a hybrid model. As we mentioned in the response to Q1, this is an open research area, and we believe there are several possible solutions. The key point is that a latent space is generally needed to capture the continuous properties of discrete graphs. The latent space could be represented by learned neural networks or constructed in a non-parametric manner (GraphBFN). Feasible solutions could be either jointly learning the latent distribution and the discrete distribution or designing the latent as an intermediate state between continuous-state and discrete space and only modeling in the latent space as GraphBFN did. \n\nNext, we elaborate on the parameter spaces of GraphBFN. As shown in the previous response to Q1, we could interpret the parameter space as a non-parameterized latent space. However, though the points over the parameter space have a continuous value, the parameter space of $K$-dim one-hot discrete data is actually a $K-1$ simplex space. This is because the parameter space holds the constraint that the samples' dims need to be summed as $1$. The non-free lunch trade-off here is that though the parameter space could be seen as an intermediate between the continuous and discrete, the simplex-contains make it non-trivial to design generative models over such space.\n\nWe will add the discussion to the updated version to illustrate the possible solutions and tradeoffs better.\n\n> **Q3: Towards the trade-off between \"continuous\" and \"discrete\"**\n\n\nThank you for eliciting such an insightful discussion. We discuss the trade-off in the practical setting of graph generation.\nFirst, similar to our response to Reviewer HH53, the benefit of being more \"continuous\" lies in two aspects:\n\n1. continuous transition of latent space\n\n2. latent space itself being continuous-state and interpretable\n\nDue to the space limit, please refer to the last response to Reviewer HH53 for a detailed discussion of these benefits. We apologize!\n\nRegarding the notion of being more “discrete,” we are skeptical about the potential benefits of applying Bit Diffusion [3], given concerns similar to those observed with GruM. While the discrete latent space in Bit Diffusion may appear to align naturally with the inherently discrete structure of graphs, its binary representation lacks interpretability and structure. This limits the model’s ability to capture high-level graph semantics or guide the generation process meaningfully. Nonetheless, we believe Bit Diffusion may still be beneficial in other application domains where simplicity and generic data representation are more important than structured latent semantics.\n\n[1] \"DiGress: Discrete Denoising diffusion for graph generation.\"\n\n[2] \"Graph Generation with Diffusion Mixture.\"\n\n[3] \"Analog bits: Generating discrete ...\"", "claims_and_evidence": "The claims are supported", "methods_and_evaluation_criteria": "The evaluations make sense.", "theoretical_claims": "I did not check the proof in detail but the results make sense.", "experimental_designs_or_analyses": "The experimental design and analysis are sound.", "relation_to_broader_scientific_literature": "The paper proposes a novel flow-based graph generation method.", "essential_references_not_discussed": "The paper identifies the limitations of discrete processes in graph generation and proposes a flow-based smooth alternative. This problem aligns with two existing research directions:\n\nExtending discrete state-space models to continuous representations (e.g., [1]).\n\nEnabling continuous diffusion processes to model discrete features (e.g., [2]).\n\nReferences:\n\n[1] Xu, Zhe, et al. \"Discrete-state Continuous-time Diffusion for Graph Generation.\" arXiv preprint arXiv:2405.11416 (2024).\n\n[2] Chen, Ting, Ruixiang Zhang, and Geoffrey Hinton. \"Analog bits: Generating discrete data using diffusion models with self-conditioning.\" arXiv preprint arXiv:2208.04202 (2022).", "other_strengths_and_weaknesses": "Strength\n\nThe paper is well-written with clear identification motivation/limitation of existing method.\n\nThe proposed method is sound and the empirical results look promising\n\nWeakness\n\nThe proposed method does not perfectly align with the identified motivation (see question below for more details)", "other_comments_or_suggestions": "There seem to be typos in Eq.(2)", "questions_for_authors": "1. The paper clearly articulates the issue of discrete diffusion models for graph generation. However, there seems to be a slight misalignment between the identified issue and the proposed solution. The issue concerns limitations in discrete diffusion, but the proposed method falls under the flow-based family rather than addressing diffusion directly. Could you provide further clarification on this choice? Is there a specific reason for moving away from the diffusion framework rather than improving it?\n\n2. I also have a question regarding the motivation behind the proposed approach in the broader context of graph generation models. Existing methods include continuous diffusion models [1] and discrete diffusion models [2]. Since graph structure generation is inherently discrete, a purely continuous approach may not be suitable. At the same time, the identified limitations of discrete diffusion models suggest that a fully discrete approach is also problematic. If this interpretation is correct, then an intermediate approach—one that balances discrete and continuous modeling—seems necessary. How should we characterize such a hybrid model, and why does the proposed method fit this characterization?\n\n3. There are two existing research directions (see references) that attempt to bridge the gap: (1) making discrete diffusion models more continuous and (2) making continuous diffusion models more discrete. These approaches also seem like potential solutions to the identified problem. How does the proposed method compare to these? What advantages does it offer over existing solutions?\n\nReferences:\n\n[1] Jo, J., Lee, S., and Hwang, S. J. Score-based generative modeling of graphs via the system of stochastic differential equations. arXiv preprint arXiv:2202.02514, 2022.\n\n[2] Vignac, C., Krawczuk, I., Siraudin, A., Wang, B., Cevher, V., and Frossard, P. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.14734, 2022.", "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": "XdEJHHziNw", "reviewer": "Reviewer_HH53", "summary": "This work proposes a new graph generative model called GraphBFN by extends BFN to graph generation. This paper further proposes an advanced sampling strategy and new time-scheduling techniques to boost the performance of BFNs. Empirical evaluation shows that GraphBFN consistently achieves strong performance and higher efficiency.\n\n## Update after rebuttal\n\nThe rebuttal has addressed my concerns, so I have raised my score.", "questions": "", "limitations": "", "rating": 3, "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": "> **W1: Towards the non-trivialness of our work**\n\nThank you for raising this concern. We would like to further clarify the technical contribution of our approach. While our method builds on the BFN framework, *naively applying it fails to perform well*. Our work bridges the gap between the theoretical framework and complex real-world graph generation settings. For instance, in our ablation of the adaptive Flowback sample, disabling it causes a drastic performance drop—valid sample rate on Planar drops from 96.2% to 14.1%. Techniques like this improve the model framework itself and hence are task-agnostic, which may generalize to other complex applications of BFNs.\n\n\n> **W2&3: Regarding GraphBFN's efficiency**\n\nThank you for raising this important point. We would like to clarify that, similar to continuous-time diffusion models, GraphBFN achieves efficiency *not through lower per-step runtime but through its ability to maintain high sample quality with fewer discretization steps*.\n\nTable 5 indicates that GraphBFN is not much slower per step than baselines. Rather, its key advantage lies in Table 7, where GraphBFN can maintain high sample quality with only ~10% of the original sampling steps.\n\nSince GraphBFN and continuous-time models gains efficiency similarly, we compare their performance directly in the next table. GraphBFN consistently maintains the strongest performance at every level of step reduction. This reinforces GraphBFN effiency.\n\nDataset—QM9withoutH\n|Steps|GraphBFN|DisCo-GT|Cometh|\n|---|:-:|:-:|:-:|\n|500|99.7|99.3|99.6|\n|100|99.6|98.75|99.4|\n|10|98.6|95.3|88.7|\n\nWe also provide a runtime comparison for DisCo under identical settings (Cometh's implementation is not available). Its longer runtime stems from its larger default architecture. When reduced to our setup, DisCo’s quality noticeably drops (see last below), suggesting GraphBFN maintains competitive per-step efficiency.\n\n||Time to Sample 10k QM9withH| \n|---|:-:|\n|DisCo-GT|66min|\n|DisCo-MPNN |46min|\n|GraphBFN-GT |44min|\n|GraphBFN-MPNN |35min|\n\nWe also experimented with the faster but less expressive MPNN-based backbone architecture suggested by DisCo. We found GraphBFN can also enjoy this speed up. However, similar to DisCo's finding, we observe that the speed-up architecture results in a decline in sample quality. Even then, GraphBFN-MPNN still outperforms baselines.\n\nDataset—QM9withH\n||Valid| Unique|Atom. Stab.|Mol. Stab.|\n|---|:-:|:-:|:-:|:-:|\n|DisCo(matching size)|96.7|97.9|97.5|68.9|\n|DisCo-GT|98.1|97.8|97.8|70.0|\n|DiGress(GT)|95.4|97.6|98.1|79.8|\n|GraphBFN-GT|99.2|94.9|99.4|94.7|\n|GraphBFN-MPNN|97.3|97.4|98.8|87.8|\n\n\n> **W2&3: Clarifying the Conceptual Difference between Continuous-time Diffusion and \"Smooth Interpolation\"**\n\nThank you for pointing out their relation to \"smoothness\"\n\nWe want to clarify that there are generally two dimensions to consider when discussing smooth interpolation. \n1. continuous transition of latent space\n2. *latent space itself being continuous-state and interpretable (our claim)*\n\nContinuous-time modeling (e.g. GraphBFN, DisCo, and Cometh) addresses the first dimension by allowing the latent distribution to evolve smoothly over continuous time. This allows the model to learn how to make predictions at any point in time, reducing discretization errors. This property explains why these models can sample with far fewer discretization steps than the discrete-time model DiGress[2].\n\nHowever, the “smooth interpolation” we emphasize in our paper primarily refers to the second dimension: the latent space being continuous in state, not just in time. This is a unique property of GraphBFN, thanks to the probabilistic modeling of the BFN framework. Under this continuous and normalized latent space, changes in latent variables between nearby timesteps are significantly more stable compared to discrete latent spaces like those in DiGress. which enables smoother transitions in spectral features. In graph generation tasks, the model heavily relies on the conditioning of these features; hence, having a stable and consistent latent evolution is crucial for generation quality, as illustrated in Appendix G.2.\n\nThough continuous-time dynamics help reduce transition noise in models like DisCo and Cometh, their latent variables still reside in the discrete graph space, which inherently leads to fluctuating latent transitions. To validate this, we conducted the analysis in Appendix G.1 on DisCo. The results show that DisCo’s trajectory behaves similarly to DiGress, with higher fluctuation.\n\n||MASD|MLSTD|MVar|\n|---|---|---|---|\n|Digress|1.14|0.78|0.65|\n|Drum|1.43|0.79|0.77|\n|DisCo|1.05|0.76|0.56|\n|GraphBFN|0.39|0.25|0.26|\n\nWe also distinguish our method from models like GruM. Though GruM also uses a continuous latent space, it is neither normalized nor structured in a way that makes spectral features interpretable. As a result, these models cannot effectively utilize the latent space to aid generation in the way GraphBFN can.", "claims_and_evidence": "The claims are adequately supported by empirical evidence.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria makes sense.", "theoretical_claims": "Strength 1 (theoretical results): This paper theoretically shows the permutation invariance of the loss function and the density function (Proposition 3.2) by proving the permutation equivariance of the Bayesian update rule, and the proof looks sound. \n\nWeakness 1 (marginal contribution): The technical contribution of this paper seems a bit marginal. Most of the method design and theoretical results are just mimicking the original BFN paper (Graves et al., 2023).", "experimental_designs_or_analyses": "Weakness 2 (efficiency): Although this paper claims that GraphBFN is efficient, experimental results do not support this claim as much. In Table 11, GraphBFN is the slowest method in terms of sampling time, slower than DiGress and GruM. Furthermore, later work such as continuous-time graph diffusion has been proposed to further improve the efficiency of DiGress (see Weakness 3 below). It is unclear how does GraphBFN compare with continuous-time graph diffusion models in terms of sampling time.", "relation_to_broader_scientific_literature": "Strength 4 (new direction): This work is the first to extend BFN to graph generation. It opens up a new interesting and promising direction in the area of graph generation.", "essential_references_not_discussed": "Weakness 3 (missing baselines): Continuous-time graph diffusion models [1,2] can also be viewed as \"smooth interpolation.\" They are proposed to improve generation efficiency as well by reducing the number of discretization steps. However, the authors did not discuss or compare GraphBFN with continuous-time graph diffusion models. \n\n- [1] Xu et al. Discrete-state continuous-time diffusion for graph generation. NeurIPS, 2024. \n- [2] Siraudin et al. Cometh: A continuous-time discrete-state graph diffusion model. arXiv:2406.06449.", "other_strengths_and_weaknesses": "There are no other strengths or weaknesses that I want to point out especially.", "other_comments_or_suggestions": "- You mentioned \"ICLR\" in the \"Ethics Statement\" section. It is not relevant to ICML and should be removed. \n- The required \"Impact Statement\" section is missing. Please add it in the revised version of the paper.", "questions_for_authors": "See the weaknesses mentioned 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": {}}]

Author rebuttal:

Meta-review: This paper develops Graph Bayesian Flow Networks (GraphBFN), a generative model for graphs based on Bayesian Flow Networks.  The paper is well-written, the method sound, and an interesting advance in graph generation.  Experiments demonstrate good performance across all benchmarks.  The reviewers unanimously recommend acceptance given the contribution made by the paper.
Decision: Accept (poster)