Advancing Graph Generation through Beta Diffusion
Authors: Xinyang Liu
Yilin He
Bo Chen
Mingyuan Zhou
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Machine Learning
Generative Models
Denoising Diffusion Probabilistic Models
Primary area: generative models
TL;DR: This paper introduces a graph generative model developed upon beta diffusion process, and along with a modulation technique to prioritize the stability of generating important substructure, whose effectiveness is validated by experimental results.

Abstract: Diffusion models have excelled in generating natural images and are now being adapted to a variety of data types, including graphs. However, conventional models often rely on Gaussian or categorical diffusion processes, which can struggle to accommodate the mixed discrete and continuous components characteristic of graph data. Graphs typically feature discrete structures and continuous node attributes that often exhibit rich statistical patterns, including sparsity, 
bounded ranges, skewed distributions, and long-tailed behavior. To address these challenges, we introduce Graph Beta Diffusion (GBD), a generative model specifically designed to handle the diverse nature of graph data. GBD leverages a beta diffusion process, effectively modeling both continuous and discrete elements. Additionally, we propose a modulation technique that enhances the realism of generated graphs by stabilizing critical graph topology while maintaining flexibility for other components. GBD competes strongly with existing models across multiple general and biochemical graph benchmarks, showcasing its ability to capture the intricate balance between discrete and continuous features inherent in real-world graph data. Our PyTorch code is available at https://github.com/xinyangATK/GraphBetaDiffusion.

Published as a conference paper at ICLR 2025
ADVANCING GRAPH GENERATION THROUGH BETA DIFFUSION
Xinyang Liu'.*, Yilin He Bo Chen', Mingyuan Zhou'
The University of Texas at Austin, "Xidian University
xinyangatxegmaill com, yilin. www.ccembs.............ooo...... behen@mail wtt.:/aai..iiiiiiiiaammmmmamimim addinnnndu... en, mingyuan. zhou@mecombs, utexas edu
https/coomssuuteeeseeee wtw.ua.eeeee.eo edu
ABSTRACT
Diffusion models have excelled in generating natural images and adapted to variety of data types, including graphs. However, conventional models often rely on Gaussian or categorical diffusion processes, which can struggle ac- commodate the mixed discrete and continuous components characteristic of graph data. Graphs typically feature discrete structures and continuous node attributes that often exhibit rich statistical patterns, including sparsity, bounded ranges, skewed distributions, and long-tailed behavior. address these challenges, we introduce Graph Beta Diffusion (GBD), generative model specifically designed to handle the diverse nature of graph data. GBD leverages beta diffusion process, effec- tively modeling both continuous and discrete elements. Additionally, we propose modulation technique that enhances the realism of generated graphs by stabilizing critical graph topology while maintaining flexibility for other components. GBD competes strongly with existing models across multiple general and biochemical graph benchmarks, showcasing ability to capture the intricate balance between discrete and continuous features inherent in real-world graph data. Our Py code is available at httpp::/ggihub..om//iing http://gihlo..oooooauuuaaaa/aaat
being
G. G O Q2
GT
Gt
G G. P.
Go
Ge
forward process
reverse process
Q Pr.
Beta variables
minimize heampling and feorrection
Figure 1: Overview of the forward and reverse diffusion processes of GBD. The multiplicative factors Q: and Pt are sampled from beta distributions parameterized the initial graphs Go and "clean graphs" predicted by Go. The neural network Go is learned through minimizing Equation 8 constituted by Lsampling and Leorrection
0.TrT
0.11
0.15T
0.2TT
0.5
Figure 2: Edge generation process of the GBD model in graph topology (top) and adjacency matrix (bottom) views. Nodes sorted by descending degree centrality and color-coded by degree, from yellow (high) purple (low). modulation technique in Section 2.3 enables early emergence key positions such as community hubs, enhancing reverse chain stability.
Equul contribution.

---

Published as a conference paper at ICLR 2025
INTRODUCTION
In recent years, there has been significant surge in interest and activity in the field of graph generation, particularly with the development of advanced generative models tailored for graphs. This growing attention is driven by the recognition of graph data's 's pervasive presence and utility across
diverse real-world applications, ranging from social network study (Newman et al. 2002 Conti et al.
2011 Abbe 2018; Shirzadian al. (023) to biochemical molecular research (Jin et al. 2018 Liu
et al. 2018 Bongini et al. [021] Guo et al. 2024 Li & Yamanishi] 2024). Additionally, the rapid
evolution of machine learning tools has introduced powerful techniques for data generation, among
2020 Song et al. 2021 Austin et al. 2021] Avdeyev et al. 2023 Chen & Zhou 2023: Zhou et al. 2023) stand out as a notable example. As these advanced lools
which diffusion models (Ho et al.
intersect with the task of graph generation, we witness the emergence of numerous diffusion- baasdd
graph generative models (Niu et al. 2020a Jo et al. [022; Haefeli et al.) 2022] Huang al. 2022
Vignac et al. 2023 Jo et al. 2023 Cho et al. 2023 Chen et al. 2023 Kong et al. (023).
While cnlffusion-based graph generative models often demonstrate superior performance compared to
their predecessors (You et al. [2018] De Cao & Kipi 2018 Li et al. [201]] Simonovsky & Komodakis 2018| [iu et al.] [019 | (Shi et |020 [uo et al. Martinku et al. (022). there is still potential for further enhancement in the quality of generated graphs. Among the latest advancements in these methods, it is widely recognized that incorporating inductive bias from the graph data is generally beneficial for model design (Jo et al. 2023). One promising direction of incorporating this bias involves considering the statistical characteristics of the distribution of graph data. For instance, both Graph D3PM (Haefeli al.] 2022) and DiGress (Vignac al. 2023) have demonstrated that when considering the binary or categorical nature of the graph adjacency matrix and modeling it in the discrete space, it provides benefits for generating more realistic graphs.
Accounting for the discreteness of the graph adjacency matrix has shown enhancement to performance. However, it crucial to recognize that the complexity and flexibility of the distribution characteristics of graph data extend beyond mere discreteness. Real-world graphs usually display sparse edge distributions and exhibit diverse statistical patterns in node attributes, which may include skewed,
multi-modal, or long-tailed distributions (Barabási et al. 22000] Ciotti et al. 2015 Liang et al.) 2023 Wang et al., 2023). While the values within node feature matrices may not inherently bounded by range, they are often be empirically represented or processed into quantities that are bound by specific limits. Considering the unique characteristics inherent to graph data, it is clear that Gaussian and categorical distributions, often default choices for constructing diffusion processes, may not adequately align with these graph traits. This misalignment could introduce noticeable limitations in accurately modeling the distribution of graphs.
Given the unique statistical characteristics of graph data, the beta distribution emerges as a particularly suitable modeling choice. With great flexibility model continuous data with various statistical characteristics and approximate discrete distributions at all sparsity levels, the beta distribution aligns well with the inherent traits of graphs, hence making itself promising candidate to surpass the potential limitations imposed by utilizing Gaussian or categorical distributions. In this paper, we introduce Graph Beta Diffusion (GBD) as novel addition diffusion- based graph generative models. GBD models the joint distribution of node attributes and edge connections within graph through beta diffusion (Zhou al.) 2023), generative diffusion process that is built upon the thinning of beta random variables in its multiplicative forward diffusion process and the thickening in its multiplicative reverse process.
We underscore two major contributions arising from the development of GBD. First, our experiments generating data on various synthetic and real-world graphs confirm the effectiveness of beta diffusion as a strategic choice within the design framework of the backbone diffusion model, especially for graph generation tasks. Second, our exploration of the model's design space has yielded a set of recommended practices, notably novel modulation technique that bolsters the stability of generating essential graph structures. We demonstrate that these practices, when implemented together, lead to consistent enhancements in model performance.
2
THE METHODOLOGY
In this study, our primary focus lies in generating two types of graphs: generic graphs and molecular graphs. A graph with N nodes is represented by the tuple G (A,X), X), where X NDD
2

---

Published as a conference paper at ICLR 2025
denotes the node features with feature dimension D, and A E RNXN is the symmetric binary adjacency matrix that defines the connections between nodes. The selection of node features offers high flexibility, ranging from raw-data raw-data-provided node categories to hand-crafted features such as node-level statisties (Jo et al. 2022) or spectral graph signals (Jo et al. 2023). The features within X exhibit great diversity in their nature, including numerical, categorical, and ordinal types. Through preprocessing methods including dummy-encoding we standardize them as continuous variables bounded by [0, 1]. For molecular graphs, we use A (I:K) to represent the structure of graph with K' types of edges and G is defined as (A X). In the sequel, we by default employ the generie graph scenario to illustrate the methodology.
empirical CDF transformation or normalization,
2.1 FORWARD AND REVERSE BETA DIFFUSION PROCESSES
Forward multiplicative beta diffusion process. Such a process can be characterized by the transition probability q( (Gr G Go). with Go denoting the combination of the original adjacency matrix and node feature matrix. Following recent diffusion- based graph generative models (Jo et al.,
2022, Vignac al. 2023 Jo al., 2023 Cho et al.
2023), we assume qG, G,-1, Go) ) to be
factorizable such that g(G G Go (A, A Ao
q(x, X,-1, Xo). Constructing the
forward multiplicative beta diffusion process (hou et al.
2023 for graph modeling, we have:
A A QA, QA,1 Beta (n 7A 1
(I)
X X,-I Qx,e, Qx Beta (o, 7x (a:-1 ( ao) tE [1,]].
(2)
Here 7A. 77x positive scalars adjusting the concentration of beta distributions, with higher values leading to enhanced concentration and reduced variability. The diffusion noise schedule is defined with {az [1,T]} T],, which represent sequence of values descending from towards 0 as t increases. Elements in the fractional multiplier Q or QA are independently sampled from their respective beta distributions. With the forward diffusion process defined in Equations] | and 2 characterize the stochastic transitions of an element within G as:
1 Beta
Gr.
g 9c-
ma490. 170.://a11111 a4)go
gt-1
9t-1
where depending on whether g is an element in A or X, we have either 7A 17 7x. Derived from Equation the joint distribution q(G Go) has analytical format the marginal distribution at each time stamp I, specifically,
(G, Go) = Beta(na, Go, 771 Go)
Reverse multiplicative beta diffusion process. It important to note that the joint distribution (G Go) can be equivalently constructed in reverse order, which directs samples from the terminus states GT towards the initial states Go by incrementally applying the changes SG, each reversed time stamp. With the changes at a given time t parameterized as 5G, := P. @ (1 Gt). where P, are beta-distributed fractional multipliers, the time-reversal multiplicative sampling process can be mathematically defined as: for = T,T 1,,,,,
G, G. + o (1) P, Beta (n(a, az) Go, 7/1 - Go)).
Similar to the forward sampling process, we can derive the transition distribution corresponding to the reverse sampling process described in Equation 5 as following:
q( G Gr. Go) 1 G.
Beta
G
G
m ar) (1a -at-1Go)
G
Following previous work (Austin et al. 2021 Haefeli al. 2022 Vignac et al. 2023 Zhou et al.. 2023), we construct the reverse diffusion process through the definition of ancestral sampling distribution as following:
Pe G G.) = gG,-1 G.. (G.,).
where (G,
(, t) is a neural network that predicts the conditional expectation of G given G,- Following Vignac et al. (2023), we instantiate Gg (G,, t) as graph transformer network Dwivedi & Bresson 2020). We present the complete sampling process Appendix [J.1]
3

---

Published as a conference paper at ICLR 2025
2.2 TRAINING GBD
The overall training procedure of GBD is described in Section D.1 of the Appendix. We employ the objective function proposed by beta diffusion (Zhou al. 2023), specifically,
C = Σ (1 - Ceampligg (t, Go) + w Leorrectoon (t, Gr), E [0, 1=2
(8)
In Equation 8 the loss terms associated with sampling and correction are defined as
Ceampling (t, Go) Go) KL (L (oepppoGGaaa (G.-1 Gt) 9(G G., Go)),
(9)
Leorrection (t, Go) - Go) KL (g, Go (G, || ( Go)).
(10)
In Equation 10 the KL divergence is evaluated between the following distributions: ((G, Go(G, , ()) is Beta(njo, Go Gr. (),n)))nll11))) a (G,, ()), and g(G, Go) is the same as g(G; Go) in distribution. The subscript is introduced to represent generic graph sample other than G. that is also obtained at time t from the forward diffusion process. The core principle behind the loss function terms can be described as follows: Csampling drives the empirical ancestral sampling distribution towards the bias on marginal distribution at each time stamp accumulated through the ancestral sampling. These two types of loss terms collectively reduce the divergence between the empirical joint distribution on two graphs sampled from adjacent time stamps in the reverse process, and their joint distribution derived from the forward diffusion process. A positive weight is introduced to balance the effects of these two types of loss terms. We set it to 0.01, following Zhou et al. (2023), and found that this configuration is sufficient to produce graphs that closely resemble the reference graphs without further tuning. To better elucidate the optimization objective, we list out the analytical expressions of the KL divergence term in Appendix
posterior distribution, while Leorrection corrects the
B
is demonstrated in Zhou et al. (202)) that the KL divergence between two beta distributions can be expressed in the format of a Bregman divergence. Namely, considering convex function
r(a))(3) is the beta function, the loss term Leampling p(a, 33) e In Beta(a, 3), where Beta(a, 9) r(a+3)
can be expressed
Csampling (f, Go)
(lasampling: Dsampling] [a [sampling by Dimmpling)) asampling 17(1==111 Go, Dsampling 17(1 at-- Go), Sampling = -
(11)
- ar) Dsampling = n71 a: Go).
Likewise, express the correction loss term Lcorrection
Loorrection (t, Go) By(G)) (lacoreectonns Deorrection] coorrcction b Deorrection)).
Acorrection = nja, Go, bearrection = 17(1 ag Go);
(12)
correction na Go. bearraction = 17(11 aq Go).
Here we reference the de notation of [anerjee et al. (2005) to represent the Bregman divergence. As established in Lemmas 3-5 of Zhou et al. (2023). since both Leampling and Learrection can be formulated as Bregman divergences, Proposition I of Banerjee et al. (2005) applics, demonstrating that they yield the same unbiased optimal solution. This justifies the use of Go in the reverse diffusion process, as detailed below.
Property Both Cyampling and Leorrection are uniquely minimized at
Go Go Go
E
2.3 EXPLORING THE DESIGN SPACE OF GBD
Many diffusion-based graph generative models offer great flexibility with technical adjustment to enhance their practical performances. Here we list four impactful dimensions among the design space of GBD. Namely, data transformation, concentration modulation, logit-domain computation, and neural-netword network precondition. We elaborate each design dimension below and discuss our choices in these aspects in the Appendix.
4

---

Published as a conference paper at ICLR 2025
Data transformation. We convert the raw data X) to Go through linear transformations, i.e.,
Go = (Ao: Xo), where Ao w A + ba, Xo wx X + bx:
(13)
with the constraints that min (wr, ba: wxx wx,bx) > 0 and max(wa + bA, wx + bx) S 1. This operation not only ensure that all data values fall within the positive support of beta distributions, avoiding gradient explosion when optimizing the loss function, but also provide an effective means to adjust the rate at which diffusion trajectories mix. A forward diffusion trajectory reaches state of "mix" when it becomes indistinguishable to discern the initial value from its counterfactual given the current value. A suitable mixing rate ensures that the signal-to-noise ratio (SNR) of the final state in the forward diffusion process approaches zero, meeting the prerequisite for learning reverse diffusion while preserving the learnability of graph structural patterns. The scaling parameter provides a macro control for the mixing rate, with a smaller value contracting the data range and promoting the arrival of the mixing state.
Concentration modulation. Another hyperparameter that offers a more refined adjustment to the mixing rate is the concentration parameter rj. Higher values of 7) reduce the variance of the fractional multipliers P. sampled from their corresponding beta distributions, thus delaying the arrival of the mixing state. Leveraging this property, we have devised a simple yet effective modulation strategy to differentiate the mixing times across various graph substructures.
Specifically, we assign higher 1) values to "important positions" within a graph, such as edges connecting high-centrality nodes or edges deemed significant based on domain knowledge, such as the carbon-carbon bond in chemical molecules. For instance, when modulating 1j from degree centrality, the exact operation executed upon the 7) values for edge (u, v) and for the features of node u can be mathematically expressed as
Nu. 9. 9.4.maaaa (max deg(v))) Ta = 9x (deg(u)))
(14)
Here we first prepare several levels of values, then utilize two assignment functions, namely ga(.) and (-), to map the node degrees (or their percentile in the degree population within one graph) to one of the choices of the 7 values. We have observed that this operation indeed prolongs the presence of these substructures during the forward diffusion process, which in turn leads to their earlier emergence compared to the rest of the graph during the reverse process. Additionally, provide an alternate definition of "importance positions" using betweenness centrality (Freeman 1977), detailed in Appendix D.2, and also ablate its effects in Section 4.3
We visualize the reverse process from two perspectives in Figure 2 We first obtain the The by degrees retrieved from the training set before sampling and then generate graph through reverse beta diffusion. From the top row, we observe that edges linked to nodes with higher degrees (indicated by brighter colors) appear first, followed by other edges. From the bottom row, is evident that edges connected to the first five nodes, which have higher degrees, are identified first and then progressively in descending order of degree. Notably, the nodes of the adjacency matrices the bottom row are reordered by decreasing node degree of the final graph. Additionally, we can also find the predicted graph of GBD converges in an early stage to the correct topology. We attribute the enhanced quality of generated graphs to the early emergence of these "important substructures," which likely improves the reliability of generating realistic graph structures. Furthermore, this approach is particularly appealing it allows for the flexible integration of graph inductive biases within the diffusion model framework.
Logit domain computation. Another noteworthy designing direction lies in the computation domain. Although the reverse sampling process directly implemented from Equation 5 already effective generate realistic graph data, we observe that migrating the computation to the logit space further enhances model performance and accelerates training convergence. One potential explanation that the logit transformation amplifies the structural patterns of the graph when all edge weights are very close to zero at the beginning of the ancestral sampling process. Equivalent to Equation 5 the logit-domain computation can be expressed as
logit (G.-1) = In (oggit( + e logic((P)) + (lggit(G))))ggg((..)))
(15)
Neural-network precondition. Finally, we employ the neural-network precondition technique (Karras al. 2022) and customize it for training GBD, which involves standardizing G, before
5

---

Published as a conference paper at ICLR 2025
passing them to the prediction network Go(+). In other words, we modify Equation 7
po Ge) :- g(Gt-1 G., (G.(G.))) ()), G. G. - Blgd
or logit(G.) - B[logit(g.]]
(16)
/arlg
v /Va[llggi((s.)
To illustrate the application of neural- preconditioning, we present an example of training GBD to generate graphs G = AA X). For simplicity, we assume the predictor operates in the original domain, with corresponding results for cases involving logit domain computations provided in Appendix C We make following statistical assumptions regarding the marginal distribution of ag and To, the elements within the graph adjacency matrices and node feature matrices after the data transformation step: ag follows a Bernoulli distribution with two possible outcomes amin, Omax where the probability of ag = Qmax is p, and 2o follows uniform distribution over the support [Emin mmax] Given that 9: 1.90 ~ (Beta(njogg0 n(1 - (r. and by applying the law of total expectation and the law of total variance, one can derive that
Elo+] = Oie (p- Omax + (1 pp) Omin),
Var
1
(B[as) - -lar)") + n4
(at - p)) amiia)
(17)
vIA +
B[xr] 2
av (Frin + Xmaxx)
Var[ar] nx
[B(ze)] B(xe)))
+ 12( +1)
7xx
(a (X Tmia]
(18)
Using these computed quantities, we complete the neural-network preconditioning by standardizing G; into G. = (A,, Xt), where the adjacency matrix is transformed as A, = -A.-E//a))/ / /Varjau
and the node feature matrix as X, (x,-) / /arrizzl The standardized graph G, is then used as input to the predictor network. The derivation Equations and i8]s Appendix C While neural-network preconditioning is generally effective for stabilizing model training, we empirically find to be particularly beneficial when training the GBD with the predictor defined in the logit space, where increased variability is introduced.
RELATED WORK
Graph generative models. Early attempts at modeling graph distributions trace back to the Erdōs- Rényi graph model (ERDaS & R&wi, 1959 Erdós et al.] 1960). from which a plethora of graph generative models have emerged. These models employ diverse approaches establish the data generative process and devise optimization objectives, which in turn have significantly expanded the flexibility in modeling the distribution of graph data. Stochastic blockmodels (Holland al.
1983 Lee & Wilkinson| 2019). latent variable models (Airoldi et al. 2009 Zhou 2015 Caron &
|
Fox 2017 and their caaatiionallatttnooooooo baased based successors (Kipf & Welling, 2016 Hasanzadeh
et al. 2019 Mehta et al. 2019 He et al., (022) assume that edges are formed through independent pairwise node interactions, and thus factorize the probability of the graph adjacency matrix into the dot product of factor representations of nodes. Sequential models (You et al. 2018 Wang et al. 2018) Jin et al., 2018. Han et al. 2023) adopt a similar concept of node interactions but correlate these interactions by organizing them into series of connection events. Additionally, some models treat the graph adjacency matrix as a parameterized random matrix and generate it by mapping a random vector through a forwafd neural network (Simonovsky & Komodakis 2018 De Cao & Kipf 2018). In terms of optimization targets, many utilize www.-iikkoodbaaaseeeeeeeee objectives such as negative log-likelihood (Liu et al., 2019) evidence lower bound objectives (Kipf & Welling 2016), while others employ generative adversarial losses (Wang et al.) 2018) or reinforcement learning losses (De Cao & Kipf. 2018). Diffusion-based graph generative models (Jo al., 2022] Haefeli al.
2022] et al. [0033] Niu et al. 20200b a Chen et al. 2023 Cho et al.) 2023 Kong et al. 2023). including this work, feature unique data generation process compared to previous models. They map the observed graph structures and node features to a latent space through a stochastic diffusion process, whose reverse process can be learned by optimizing a variational lower bound (Vignac et al..
2023) or numerically solving reverse stochastic differential equation (Jo et al. 2022).
Diffusion models. The stochastic diffusion process is introduced by Sohl- Dickstein et al. 2015 for deep unsupervised learning, and its foundational connection with deep generative models laid

---

Published as a conference paper at ICLR 2025
Planar
SBM
QM9
ZINC250K
giKO S
Figure 3: Examples of graphs generated by the GBD model on Planar, SBM, CM9, and 2 2INC250K datasets.
down by Song & Ermon (2019) and denoising diffusion probabilistic model (DDPM) (Ho et al. 2020). DDPM maps a data sample to the latent space via a Markov process that gradually applies noise to the original sample, and learns reverse process reproduce the sample in finite steps. The optimization and sampling processes in DDPM can be interpreted through the lens of variational inference (Sohl-Dickstein et al.] 2015 Ho et al.) 2020) can be formulated score matching with Langevin dynamics (Song et al. 2021 Song & Ermon 2019). Both approaches are focused on diffusion processes that define the transition between normally distributed variables, which proven effective for generating natural images. As the scope of generative tasks expands to discrete domains like text, diffuuion models transitioning between discrete states emerge (Austin et al. 2202]) which demonstrates that the choice of probabilistic distribution for modeling each noise state could significantly impact the learning task. This conclusion is also validated in the application of graph generation (Haefeli et al.) 2022] Vignac et al.) (023). Further studies (Chen & Zhou, 2023 Zhou et al. 2023) are conducted to improve diffusion models by introducing novel diffusion processes based on probabilistic distributions that better capture the intrinsic characteristics of the generation target. Among these, the beta diffusion of Zhou et al. (2023) is chosen as the foundation our method, due to the beta distribution's ' proficiency in capturing sparsity and modeling runge-bounder data across mixed types. These traits are commonly observed in real-world graphs (Barabási et al. 2000 Ciotti
al. 2015 Liang et al. 2023
Wang al. 2023).
EXPERIMENTS
4.1
GENERIC GRAPH GENERATION
Datasets and metrics. We use five graph datasets with varying sizes, connectivity, and topology. commonly employed as benchmarks. Ego-small 11 includes 200 sub-graphs from the Citeseer network with S N < 18 nodes. Community-smal 20. Grid contains 100 2D grid graphs with 100 N < 400. Planar includes 200 synthetic planar graphs with = 64. SBM comprises 200 stochastic block model graphs with 2-5 communities, where 44 N 187 and each community has 20 nodes.
has 100 synthetic graphs with 12 < <
For a fair comparison, we follow the experimental setup Jo et al. (2022 2023), using the same train/test split. We evaluate using maximum mean discrepancy (MMD) (rrettnn et al. 2012) to compare the distributions of key graph properties between test graphs and generated graphs: degree (Deg.), clustering coefficient (Clus.), and 4-node orbit counts (Orbit). For more complex structures like P Planar and SBM, we also report the eigenvalues of the graph Laplacian (Spec.) and the percentage of valid, unique, and novel graphs (V.U.N.) assess how well the model captures both intrinsic features and global graph properties. A lower score indicates better performance for all metries except V.U.N. More details on these metrics can be found in Appendix H.
Baselines. We compare GBD against various graph generation methods, including autoregressive
models: DeepGMG (Li et al. 2018), GraphRNN (You et al., 2018), and GraphAF (Shi et al.) 2020); one-shot model: Graph VAE (Simonovsky & Komodakis 2018); and flow-based models: GNF (Liu et al. 2019) and GraphDF (Luo et al. 2021). Additionally, we compare against state- of-the-art (SOTA) Liffusion-based graph generative models, including score score-based or continuous:
EDP-GNN (Niu al. 2020a), GDSS, GDSS + Transofrmer (TF) (Jo et al., 2022 GruM [Jo et al.,
2023). and ConGress (Vignac et al. 2023);; discrete: DiGress (Vignac et al. 2023 ; autoregressive:
GraphARM ARM (Kong al. 2023); and model with wavelet features: Wave-GiD (Cho al. 2023
7

---

Published as a conference paper at ICLR 2025
Table 1: MMD results for simple generic graph generation.
Ego-small
Community-smm small
Grid
Method
Deg.
Clus.
Orbit.
Deg.
Clus.
Orbit.
Deg.
Clus.
Orbit.
DeepGMG
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.064
0.043
0.021
GruphAF
0.030
0.110
0.001
0.180
0.200
0.020
GraphDF
0.040
0.130
0.010
0.060
0.120
0.030
VAE
0.130
0.170
0.050
0,350
0.980
0.540
1.619
0.0
0.919
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.455
0.238
0.328
GDSS
0.021
0.024
0.007
0.045
0.086
0.007
0.111
0.005
0.070
ConGress"
0.037
0.064
0.017
0.020
0.076
0.006
DiGress
0.017
0.021
0.010
0.028
0.115
0.009
GruphARM
0.019
0.017
0.010
0.034
0.082
0.004
Wave-GD
0.012
0.010
0.005
0.007
0.058
0.002
0.144
0.004
0.021
0.011
0.014
0.002
0.002
0.060
0,002
0.045
0.011
0.040
GBD
(=0.008)
(++00013)
(+0.004)
(+000003
(+:0.004)
(+:0.003)
(+000044
(+000002)
(+0.014)
Table 2: MMD results for complex generic graph generation.
Planar
SBM
Method
Deg.
Clus.
Orbit.
Spec.
V.U.N.
Deg.
Clus.
Orbit.
Spec.
V.U.N.
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.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
GDSS+TF
0.0036
0.1206
0.0525
0.0137
5.0
0.0411
0.0565
0.0706
0.0074
27.5
ConGress
0.0048
0.2728
1.2950
0.0418
0.0273
0.1029
0.1148
0.0
DiGress
0.0003
0.0372
0.0009
0.0106
0.0013
0.0498
0.0434
0.0400
74.0
GruM
0.0005
0.0353
0.0009
0.0062
90.0
0,0007
0.0492
0.0448
0.0050
85.0
GBD
0.0003
0.0353
0.0135
0.0059
92.5
0.0013
0.0493
0.0446
0.0047
75.0
Generating graphs with simple topology Using the GBD theoretical model and the implementa- tion detailed in Appendix I we show that GBD excels at generating graphs with moderate size and simple topological patterns, as evidenced by the MMD metrics Table [ GBD outperforms the baselines in five out of nine experiments and remains statistically par with the SOTA model in the other two. Even with larger graphs (e.g., the Gris benchmark), GBD achieved a degree MMD of 0.045, significantly surpassing all baselines, well maintaining competitive performance other metrics. Moreover, previous works (Cho et al. 2023 Jo et al.) 2022 Liu et al.) 2019) suggested that the MMDs metric suffers from large standard deviations due the insufficient size of the sampled graphs. Thus, to gain comprehensive study, we repeated the evaluation using an enlarged generated sample of 1024 graphs. As shown in Appendix [22, the results demonstrate that GBD consistently generates graphs that resembles true data, with improved statistical significance in experimental conclusions.
Generating graphs with complex topology GBD also maintains a leading position in generating large graphs with complex topologies, shown by the results in Table 2 In the experiments the Planar and SBM datasets, GBD achieved superior or comparable MMD scores on most graph statisties, along with high V.U.N. scores, consistently ranking first or second among all baselines. These results provide stronger evidence of GBD's capability and suitability as candidate model for generating graph data, particularly for applications where real-world instances typically more complex in nature.
Rapid convergence in the reverse process. We conducted a convergence experiment measuring the V.U.N. metric for graphs G2 generated at every 100 steps on the reverse chain, with the results shown in Figure 4 The figure highlights that GBD achieves high V.U.N. score at early timestamps the reverse diffusion process, reflecting rapid convergence. Notably, both GBD and the second- second-place model, GruM (Jo et al. 2023), share key property of predicting E, Go G.). While GruM achieves
8

---

Published as a conference paper at ICLR 2025
DiGress GO5S-TF
DiGress GD5S-TF
(surs]
(surs)
V0
02-
02
01-
00
Timesteps
Timesteps
Figure 4: V.U.N. results for intermediate graph samples in the reverse chain on P Planar (left) and SBM (right)
datasets, with GBD demonstrating clear advantage in convergence rate.
Table 3: 2D molecule generation results
QM9 UN) s 9
ZINC250K (NN s 38)
Method
Valid (%)
FCD 4
NSPDK
Scaf.
Valid(%)
FCD
NSPDK |
Scuf. 1
MoFlow
91.36
4.467
0.0169
0.1447
63.11
20.931
0.0455
0.0133
GraphAF
74.43
5.625
0.0207
0.3046
68.47
16.023
0.0442
0.0672
GraphDF
93.88
10.928
0.0636
0.0978
90.61
33.546
0.1770
0.0000
EDP-GNN
47.52
2.680
0.0046
0.3270
82.97
16.737
0.0485
0.0000
GDSS
95.72
2.900
0.0033
0.6983
97.01
14.656
0.0195
0.0467
GDSS+TF
99.68
0.737
0.0024
0,9129
96.04
5.556
0.0326
0.3205
DiGress
98.19
0.095
0.0003
0,9353
3.482
0.0021
0.4163
SwinGNN
99.71
0.125
0.0003
81.72
5.920
0.006
GraphARM
90.25
1.22
0.0020
88.23
16.26
0.055
EDGE
99.10
0.458
0.763
GruM
99.69
0.108
0.0002
0,9449
98.65
2.257
0.0015
0.5299
GBD
99.88
0.093
0.0002
0.9510
97.87
2.248
0.0018
0.5042
it through designing the model upon an OU bridge mixture (Jo et al. 2023), our model attain the same property due to the inherent nature of beta diffusion.
4.2 MOLECULE GENERATION
Datasets and Metrics We consider two widely-used molecule datasets benchmarks in Jo et al. (2022): QM9 (Ramakrishnan al. 2014), which consists of 133,885 molecules with N < 9 nodes from 4 different node types, and Z INC250K (Irwin et al. 20122). which consists of 249,455 molecules with < 38 nodes from different node types. Molecules both datasets have 3 edge types, namely single bond, double bond, and triple bond.
Following the evaluation setting Jo et al. (2022), we generated 10,000 molecules for each dataset and evaluated them with four metries: the ratio of valid molecules without correction (Val.), Fréchet ChemNet Distance (FCD), Neighborhood subgraph pairwise distance kernel NSPDK, and Scaffold similarity (Scaf.). We provide the results of uniqueness and novelty in Appendix E.2
Baselines We compare GBD against the following autoregressive and one-shot graph generation methods: MoFlow (Zang & Wang 2020), GraphAF (Shi et al. 2020), GraphDF (Luo et al. 2021 and several state-of-the-art diffusion baasuddon-baeedd graph generative models discussed previously: EDP.
GNN (Niu et al.] 2020a), GDSS (Jo al. (022). ConGress (Vignac et al. 2023). DiGress (Vignac
al. 2023). SwinGNN (Nuu et al. 2020b). GraphARM (Kong et al. (023). EDGE (Chen et al.
2023
and GruM (Jo al. 2023). We describe the details of the implementation in Appendix E.2
Results As shown in Table we observe that our GBD outperforms most previous diffusion-based models and is competitive with the current mate-off-the-rt Gaussian-based diffusion model, GruM. In particular, compared to the basic continuous diffusion model, GBD significantly outperforms it (GDSS+TF) under the same Transforrrr architecture. Additionally, observe that our proposed beta- based graph diffusion model is superior to the discrete diffusion model on both 2D molecule datasets, demonstrating that method is also capable of modeling complex structures of attributed graphs. We attribute this to the excellent modeling ability of the beta-based graph diffusion model for sparse data distributions.

---

Published as a conference paper at ICLR 2025
4.3 ADDITIONAL EXPERIMENTAL RESULTS
Ablation study on precondition and computation domain. We vary the options regarding the computation domain and the application of preconditioning. and summarize the results in Table The combination of adopting logit domain computation without using preconditioning can sometimes increase the challenge in model convergence, and therefore, it is not recommended. The listed results on Ego-smas beneficial for achieving better model performance, and the effect of preconditioning is more evident when the computation is perfomed in the logit domain.
and Community- y- demonstrate that both techniques are in general
Table 4: The effect of logit domain computation and preconditioning
Ego-small
Community small
Logit Domain
Preconditioning
Deg.
Clus.
Orbit.
Deg.
Clus.
Orbit.
0.015
0.018
0.004
0.011)
0.076
0.004
0.013
0.017
0.002
0.004
0.044
0.007
0.011
0.014
0.002
0.002
0.060
0.002
Ablation study on concentration modulation. To verify that effect of concentration modulation, we compared the results of GBD under different concentration modulation strategies on both the general graph and the molecule graph. As shown Table assigning the appropriate yj through optional concentration modulation strategies helps GBD model various types of graphs, and this technique has the potential for further modification according to varying scenarios.
Table 5: The effect of concentration modulation on generic graph and molecule graph.
Planar
SBM
Modulation Strutegy
Deg.
Clus.
Orbit.
Spec.
V.U.N.
Deg.
Clus.
Orbit.
Spec.
V.U.N.
w/o modulation
0.0005
0.0357
0.0294
0.0069
87.5
0.0015
0.0493
0.0452
0.0051
72.5
Betweenness Centrality
0.0003
0.0354
0.0154
0.0057
90.0
0.0015
0.0492
0.0450
0.0053
70.0
Degree Centrality
0.0003
0.0353
0.0135
0.0059
92.5
0.0013
0.0493
0.0446
0.0047
75.0
QM9
ZINC250K
Modulution Strategy
Valid(
FCD
NSPDK |
Spec. J
Valid((F)
J
NSPDK
Spec. J
wfo modulation
99.73
0.126
0.0003
0.9475
2.412
0.0020
0.5033
Carbon Bonds
99.88
0.093
0.0002
0.9510
97.87
2.248
0,0018
0,5042
Comparison on various node feature initialization. To demonstrate that GBD has the potential to model graphs with various types node features, we explored the impact different initialization of node features on modeling the joint distribution G = (A, X). Specifically, the node representation can be featured by Degree, Centrailities, and Eigenvectors and we vary the node feature initialization and summarize the results of model performance, as detailed in Appendix
4.4 VISUALIZATION
We present samples from GBD trained on planar, SBM, QM9 and 2INC250K in Figure 3 Addi- tionally, we provide visualization of the generative process and more generated graphs of GBD, along with comprehensive description Appendix G
CONCLUSION
We introduce graph beta diffusion (GBD), novel graph generation framework developed upon beta diffusion. We demonstrate that the utilization of beta distribution define the diffusion process is beneficial for modeling the distribution of graph data, and outline four crucial designing elements-data transformation, concentration modulation, logit-domain computation, and neural- network precondition-thar consistently enhance model performance. Through extensive experiments, GBD demonstrated superior performance across various graph benchmarks, showcasing its ability to model diverse patterns within graph data. Moreover, proposed model shows promise in modeling various types of data with discrete structures and offers valuable insights into further exploring the properties of beta diffusion.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
Our Py code is available at https://gthubb.cm/ http::/wwww.....aaaaaaaaaaaaaaaa The im- plementation follows the training and sampling algorithms described in Appendix D.1 and other technical details outlined in Appendix D
ACKNOWLEDGMENT
M. Zhou acknowledges the support of a gift fund from Apple.
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1-88) 2018
Edo Airoldi, David Blei, Stephen Fienberg, and Eric Xing. Mixed membership stochastic blockmodels. In Advances in Neural Information Processing Systems (NeurIPS), volume 21, 2009.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 34: 1 19911-17993, 2021.
Pavel Avdeyev, Chenlai Shi, Yuhao Tan, Kseniia Dudnyk, and Jian Zhou. Dirichlet diffusion score model for biological sequence generation. In Proceedings of the Fortieth International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2023.
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, Joydeep Ghosh, and John Lafferty. Clustering with Bregman divergences. Journal of machine learning research, 6(10), 2005.
Albert-László Barabási, Réka Albert, and Hawoong Jeong. Scale-free characteristics of random net- works: the topology of the world-wide web. Physica A: statistical mechanics and its applications, 281(1-4):69-77 0700669-777,20 2000.
Guy W Bemis and Mark A Murcko. The properties of known drugs. 1. molecular frameworks. Journal of medicinal chemistry, (1115))2887-2893 1996.
Pietro Bongini, Monica Bianchini, and Franco Scarselli. Molecular generative graph neural networks for drug discovery. Neurocomputinng 150:242-2573 2021.
François Caron and Emily Fox. Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Society Series B: Statistical Methodology, 19955 1366, 2017.
Tianqi Chen and Mingyuan Zhou. Learning to jump: Thinning and thickening latent counts for generative modeling. In International Conference on Machine Learning, pp. 5367-5382. PMLR, 2023.
Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. In International Conference on Machine Learning. PMLR, 2023.
Hyuna Cho, Minjae Jeong, Sooyeon Jeon, Sungsoo Ahn, and Won Hwa Kim. Multi-resolution spectral coherence for graph generation with score-based diffusion. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Valerio Ciotti, Ginestra Bianconi, Andrea Capocci, Francesca Colaiori, and Pietro Panzarasa. Degree correlations in signed social networks. Physica A: Statistical Mechanics and its Applications, 422:
25-39, 2015.
Marco Conti, Andrea Passarella, and Fabio Pezzoni. A model for the generation of social network graphs. In 2011 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, pp. 1-6. IEEF, 2011.
11

---

Published as a conference paper at ICLR 2025
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint 17X.::8005.1173, 2018.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprini arXiv:2012.09699 2020.
ERDdS and R&wi. On random graphs Publ, math. debrecen, 6(290-297):18, 1959.
Paul Erdös, Alfréd Rényi, et al. On the evolution random graphs. Publ. math. inst. hung. acad. sci, 5(1):17-60, 1960.
LC Freeman. of measures of centrality based betweenness. Sociometry, 1977.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. The Journal of Machine Learning Research, (3(1):733-773, 2012.
Zhiye Guo, Jian Liu, Yanli Wang, Mengrui Chen, Duolin Wang, Dong Xu, and Jianlin Cheng. Diffusion models in bioinformatics and computational biology. Nature reviews bioengineering, (2):136-154, 2024.
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer, Diffusion models for graphs benefit from discrete state spaces. In The First Learning on Graphs Conference, 2022.
Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab,(LANL) Los Alamos, NM (United States), 2008.
Xu Han, Xiaohui Chen, Francisco JR Ruiz, and Li-Ping Liu. Fitting autoregressive graph generative models through maximum likelihood estimation. Journal of Machine Learning Research, 24(97): 1-30, 2023.
Arman Hasanzadeh, Ehsan Hajiramezanali, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Semi-implicit graph variational auto-encoders. Advances Neural Information Processing Systems (NeurIPS), volume 32, pp. 10711-10722 2019.
Yilin He, Chaojie Wang, Hao Zhang, Bo Chen, and Mingyuan Zhou. variational edge partition model for supervised graph representation learning. Advances in Neural Information Processing Systems, 35:12339-12351 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 109-137, 1983.
Han Huang, Leilei Sun, Bowen Du, and Weifeng Lv. Conditional diffusson based on discrete graph structures for molecular graph generation. NeurIPS 2022 Workshop on -core-Based Methods, 2022.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International conference on machine learning, pp. 2323-2332. PMLR, 2018.
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning, pp. 10362-10383. PMLR, 2022.
Jachyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with diffusion mixture. arXiv preprint 2002::2302.0599 2023.
12

---

Published as a conference paper at ICLR 2025
Weonyoung Joo, Wonsung Lee, Sungrae Park, and Il-Chul Moon. Dirichlet variational autoencoder. Pattem Recognition, 107:107514, 2020.
Tero Karras, Miia Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion- based generative models. Advances Neural Information Processing Systems, 35:26565-26577,, 2022.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv: 2016.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation. International Conference on Machine Learning, pp. 17391-17408. PMLR, 2023.
Greg Landrum et al. Rdkit: Open-source cheminformatics, 2006.
Clement Lee and Darren J Wilkinson. A review of stochastic block models and extensions for graph clustering. Applied Network Science, 4(1):1-50, 2019.
Chen Li and Yoshihiro Yamanishi. Tengan: Pure transformer encoders make an efficient discrete gan for de novo molecular generation. In International Conference Artificial Intellignnce and Statistics, pp. 361-369. PMLR, 2024.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. In International conference on machine learning. PMLR, 2018.
Langzhang Liang. Zenglin Xu, Zixing Song, Irwin King, Yuan Qi, and Jieping Ye. Tackling toig-tailed distribution issue in graph neural networks via normalization. IEEE Transactions on Knowledge and Data Engineering, 2023.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. Advances in Neural Information Processing Systems, 32, 2019.
Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander Gaunt. Constrained graph variational autoencoders for molecule design. Advances in neural information processing systems, 31, 2018.
Youzhi Luo, Keqiang Yan, and Shuiwang Ji. Graphdf: A discrete flow model for molecular graph generation. International conference on machine learning, pp. 7192-7203. PMLR, 2021.
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spec- tral conditioning helps overcome the expressivity limits of one-shot graph generators. In International Conference on Machine Learning, pp. 15159-15179. PMLR, 2022.
Nikhil Mehta, Lawrence Carin, and Piyush Rai. Stochastic blockmodels meet graph neural networks. In International Conference on Machine Learning (ICML). pp. 4466 4474, 2019.
Mark EJ Newman, Duncan J Watts, and Steven H Strogatz. Random graph models of social networks. Proceedings of the national academy of sciences, (9(suppl1)):266622572 2002.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Per- mutation invariant graph generation via score-based generative modeling. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artifi- cial Intelligence and Statisties, volume 108 of Proceedings of Machine Learning Research, pp. 4474 4484. PMLR, 26-28 Aug 2020a.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permu- tation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics, pp. 4474-4484 PMLR, 2020b.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, highhpeeforrance deep learning library. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2025
Ethan Perez, Florian Strub, Harm De Vries, Vincent Dumoulin, and Aaron Courville. Film: Visual reasoning with a general conditioning layer. In Proceedings of the AAAl conference on artificial intelligence, volume 32, 2018.
Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3):93 93, 2008
Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang, and Jian Tang, Graphaf: a flow-based autoregressive model for molecular graph generation. In International Conference Learning Representations, 2020.
Pouyan Shirzadian, Blessy Antony, Akshaykumar G Gattani, Nure Tasnina, and Lenwood S Heath, A time evolving online social network generation algorithm. Scientific Reports, 13(1):2395, 2023.
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning-ICAN 2018 8: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pp. 412-422. Springer, 2018.
Jascha Sohl- Diak--ickstein. Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pp. 2256-2265. PMLR, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. International Conference Learning Representations, 2021.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Confer- ence on Learning Representations, 2023.
Haohui Wang. Baoyu Jing, Kaize Ding, Yada Zhu, Liqing Zhang, and Dawei Zhou. Characterizing long-tail categories on graphs. arXiv preprint arXiv:2305.09%) 2023.
Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo. Graphgan: Graph representation learning with generative adversarial nets. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep augo-regressive models. In International conference on machine learning. pp. 5708-5717. PMLR, 2018
Chengxi Zang and Fei Wang. 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.
Mingyuan Zhou Infinite edge partition models for overlapping community detection and link predic- tion. In International Conference Artificial Intelligence and Statistics (AISTATS), volume 38 of Proceedings of Machine Learning Research, pp. 1135-1143, 2015.
Mingyuan Zhou, Tianqi Chen, Zhendong Wang, and Huangjie Zheng. Beta diffusion. In NewrIPS 2023: Neural Information Processing Systems, 2023.
14

---

Published as a conference paper at ICLR 2025
A BACKGROUND OF BETA DIFFUSION MODEL
In this section, we employ x to denote the original data that already normalized to the range [o, 1]. The variables 21 through 2T denote the latent states sampled via forward beta diffusion process. with larger subscripts indicating states closer to complete noise. The beta diffusion model (Zhou al. 2023) is designed so that each latent state follows a beta distribution as its conditional marginal distribution:
( 20) Beta(z; m0, r7(1 2x)=
(19)
In this setup, y/ serves as the concentration parameter, where larger values of 1) result in a stronger concentration effect, shaping the beta distribution more sharply around its mean. The parameter oa is scheduling factor that gradually decreases from 1 to 0 as the forward diffusion process advances, controlling the degree of noise introduced at each step.
To achieve this, the transition between two consecutive states in the forward diffusion process is formulated as multiplication by an attenuating factor, i.e.,
24 2 qt q: Beta(naazz - t [1.
(20)
To demonstrate that the forward process defined via Equation 20 results in the conditional marginal distribution given in Equation 19 one can utilize the property that
(2t, 2t-1 - 24, 1 Dir(na 17(x-11 - a.) n(1 - av-1z))). E [1,2]
(21)
and then apply mathematical induction establish the desired conclusion.
It is worth noting that a generic triplet (Ti, 22, T3) from the Dirichlet distribution in Equation 21 can be generated using the stick-breakin construction. Specifically, лi is first sampled from Beta(noaz20, 77(1 20)). Next, is created by multiplying (1 - TT) by a factor sampled from 20)) Finally, Ty can be obtained by subtracting (π + TT2) from one. This aligns with the reverse transition process: once is obtained, 2 1 can be reconstructed by adding an increment, generated in the same manner as π2, to 2t, i.e.,
Beta(n)(a,-1 at) 2n)
セ 24 (1 (1-zz) 21) Pt, Pt Beta(n(ar-1 =,) v1(1 at- / [1,7].
(22)
With the reverse transition process formalized in Equation 22 one can derive the reverse transition distribution as
( Ze, 20) = 1 Beta
2t-1 - 24
17(01-1 - -1 a04-120) E [1,7]. (23)
21-1
In practice, to implement the reverse diffusion process, Zhou et al. (2023) defines the ancestral sampling distribution as following:
(a | 2x) == ((=1-1 Rt, fo( ())
(24)
with fo denoting a neural network with parameters 0, that predicts 2g with latent state 2, and time stamp t.
B ANALYTICAL EXPRESSIONS OF OPTIMIZATION OBJECTIVE
Recall that the optimization function is expressed as
C (1 w) Ceampling (4, Go) + w Leorrection (1, G.), E [0,
(25)
1=2
with the components defined as follows:
Leampling (t. Go) G.)G...) (poooGGe G.) || ( Gt, Go)),
(26)
Leorrection (t, Go) A Go) KL ( Go (G,,t) || ( Go)).
(27)
To derive the analytical form Leampling and Crorrections we employ the following property of beta distribution (Joo al. 2020 Zhou et al. 2023)
15

---

Published as a conference paper at ICLR 2025
Property 2 The KL divergence between Beta distributions Beta(O1. 31) and Beta 32) is given by:
KL (Belafan, B1) || Bela((u2, (2))
=11 B( B2) + (ax oz) (v((r)) - ( + B:)1 + (31 (2) - ((a1 + 8:31. (28)
B(ai, B1)
where B(a, Na)r(a) is the Beta function, v5()) demotes the digamma T(++3)
With probability distributions gG Gr,, Go) and po po G.) defined in Equations 6 and
the parameters (Ap: Pp. agg Bg) are instantiated as follows:
0 7 - ar) Go, 31 =n(11 0t Go);
17(0=111 - Go, B2 n7(1 - aa-1
Substituting these into Equation 28 we can express the KL term within Csampling as
KL (po G.) (G G. Go))
= In[(n[at-1- Gb) + In n0--1 - In In - no)
- In[(n(aa---)) - [n na1-1 Go) + In [( nay Go)
+ n -a) Go) v - or ),)
(29)
+ n - Go) (1 na-1
+ (Gn Go) d1 na, Go),
where Go = Go(G,, t).
Similarly, the KL term within Lcorrection can be derived
KL (g(G,, Co (G, Go)
= InTaa) + In (1) - nay In (nnaa Go) In [() - -1a-
(30)
+ Gay - Go) (v(na, - vinn - ma,,G))
C MATHEMATICAL EXPRESSIONS FOR ELEMENTS IN NEURAL-NETWORK PRECONDITIONING
In this section, we present the full derivation of the expressions for the mean and variance of o, and I, shown in Equations 17 and 18 and extend these conclusions to logit(a.) and logit(x.).. To establish these results, we begin by introducing the following property of the beta distribution:
Property 3 Given that St go Beta( s7(1 a,go)), one can derive that Elgt go] 0::90
and Var(g, 9u] (1 Let μ == E[go] and x² = Var By applying the law of total expectation and the law of total variance, we obtain the following results:
q+1
Blg oup, Varígı] o4f o1² + + t0702
(31)
n+1
Their counterparts in the logit domain expressed as Ellogit (gt)] = E[v(nang))) - Elp(y - rj.,o)))
(32)
Var(logit(go)) = Ely (mangu)) + Elo (n a:go))
+ Varlgg(no + Var[v(n(1 - axgo))]
(33)
with vh()) and (-) denoting digamma and Cangummaannntiinn
In the example presented in Section 2.3
we assume that ag follows a categorical distribution with outcomes Omin and Omax where the probability of P(ag amax) p. This leads to the expected
16

---

Published as a conference paper at ICLR 2025
value p dmax p) Omin and variance x² p(1 () amin)²
Taking these
quantities into Equation 31 we obtain
E[a.] 04. (p amax (1 p) +mminn;
Var[ar]
[E(as] -(aa))))))))) +
MA
(a) (00-pp))(aa p)) - amiu)))
7A +
7A +1
For node features, the assumption states that zi uniformly distributed over the interval [Emin Tmax This gives mean of (Fmin and variance of o² (Tmaa =min)"/12 and the correspond- ing mean and variance ae can then be expressed as
1
E(x:]] = Ort (Tmin + Fmax),
2 + (E[ar) - B[x,1)) + 12(πx + 1] (of( Xminn
Var[ax]
fxx
Under the same probabilistic assumptions for og and no. can derive the expressions for the terms
in Equations 32 and presented in the following remarks:
Remark Given that dg has two potential outcomes {omin amax} with P(an = -mnax) = p, the computation of B[logit(gr)] and Var involves several key components, including:
([)(n)aa))) p (1(()10mxx)) + (1 1 p) (Ijanammn))
B[v(n ))raa) p- vnn 10x00max
p) (0 n10:ammin)
Var p(1 (v (1(p)(amaxx)) 25 ()(j)tt
Varlv(n - p(1 p) (vin 7)rraaaxx) (1 m)aaamn)))
(mp ) p () (nax))aux)
(1 p) ( (nan
(1 p- 3 (n 7)rama)))
p) 0 g)camin)
(34)
Remark 2 Let xo be uniformly distributed Unif Unif(Imiin [iin Imax) We denote K the number of sub-intervals used for numerical integration via the Trapezoidal rule. Similar Remark] we present the expressions for the components in the logit domain as follows:
1
[[(()))))))] Vjck (2mmx Xmin)
(In (mjcettaax) In ((rrexs(Fmin)
E( ((m mac(Fmax Tmin)
(In I'1 maxtmmi - In 1'1 m)assmax)))
K
? (may (amin + (Fmax mmin))) [[(()ee)0)) 20(==0)=((=X)
Var[U(nau=20)] max
i=
1aa (Imin & (amax #min)) B[v(1 manco))? .0. (((==0++(i=k))
Var(u(1) - m)) max
El (1)C0e0)))))
(#((0remmxx) (n)eesmin))
n) (Xmax Xmin)
(l (n n)o))))) m Fmin)
1
(vin 704 16(1 7)xx)))xx)
(35)
D DETAILS OF GBD
D.I TRAINING AND SAMPLING
We provide the pseudo-code of the training and sampling of our generative framework within original domain and logit domain, respectively. Specifically, AlgorithmBaam and Algorithm [ show the procedure of training and sampling in original domain, respectively. practice, we migrate our proposed GBD to logit domain shown in Algorithm 4 and Algorithm in most cases.
17

---

Published as a conference paper at ICLR 2025
Algorithm 1 Sampling, in original domain.
Algorithm 2 Sampling, in logit domain
Require: Number of time steps T = 1000, de- fault concentration parameter ? 30, predie-
1: Sample logil(Gr)) ~ p(logit (Ar), logil(X+))
2: for l 1 to do Gin logit Gll-
tor Ce.
Varllogit(GG.]]
1: (Optional) Assign value to via Equation 38
2: Sample Gr (Ar; Xx) p(r, XT)
4:
(A xx) + Ga(Gin,
3: for tr
do
5:
Ao f wA A DA
4: Gin V.
[[,
X. wx Xx + bx
7:
Go (Ao. Xo)
5:
(Ag, X6) Go GGGii)
8:
U, ~ Gaumma(7)ar
- as Go. 1)
6:
Ao t WA A + ba
9:
Ve- Gamma(7(1 - a -
X. - wx X0 bx
10:
logit((P,) + In U V.
8:
Gu + (Au, Xu)
11: Obtain logit (G--) from Equation I5
9:
P. Bela(v((ac-1 Go)
12: end for
Go))
13: Go sigmood (logit(Go)
10: G t G. + P. G.)
14: return (Au ba)/ Wa and (Xu - bx //xx
11: end for
12: return (Aa ba)/wa wA and (Xo bx)/wxx
Algorithm 3 Training, original domain.
Algorithm Training, in logit domain.
Require:
Number of timesteps
1000, de-
Require:
Number of timesteps T', concentration pa- rameter 7) predictor Ge. node inffuence factor input graph batch B, learning rate A, optimization steps M. Same default values with Algorithm
fault concentration parameter r 30, pre-
dictor Co, default node influence factor 7
0.5, input graph batch B = (G)
(A (())) default learning rate 0.002, optimization steps M.
1: for step = to M do
2: Initialize Lx and LA with 0
1: (Optional) Assign value to via Equation 38
3: for 1 K do
2: for step 1 M do Initialize Lx and LA with 0
Un.,(L....,. Or, 0,,0 & schedule(t), schedullet
4: for k 1 K do
1)
5: t~ Uniff(1,,... T))
Ao f- wA (k) + ba
6:
0r,01-1 (ieeduuu(t,,,cheduuae
7:
Xo + ux x(4) + bx
1)
8:
Go <- (Aa,
7:
Ao
A (k) ba
9:
U. Gammaa (Taa Ija, Go.
8:
Xo wx (k) + bx
10:
V. Gaumma au Go). )
Go < (Ao, Xo)
11:
logit(G; + U, V
10:
G. ~ (eta(nja Go, 17(1 a: Go))
12:
Gin + loxit(Ga))33loxt(GG...
VarlBooio(GG.)
11:
G.n + / [
13:
(Å6 X6) Go(Gin,
12:
(Ág, X6) Ga GG
14:
Ao
A
13:
An wA Ab+ +b
15:
Xo wx -6b + bx
Xo = wx X/6 + bx
16:
LA +- LA + L(Ao, 7,,77 a--1)
15:
LA LA L(Au, An, m7 an a1-1)
17:
Lx + Lx + L(Xo, Xo, T, at, a1-1)
16:
Lx <- Lx + L(Xo, Xo, Cee, 11-
18:
end for
17:
end for
19:
B 4--
인/ VolCa xxxx)
18:
8 & VolCa +(x))
20:
end for
19:
end for
D.2 DETAILS OF CONCENTRATION MODULATION
Here we elaborate the concentration modulation strategies mentioned in Section 2.3
Concentration Modulation for general graph generation For general graph generation, we pro- vide two strategies depending on node-level centralities, which degree centrality and betweenness centrality, respectively. For the degree centrality of the node u in an undirected graph, it can be formulated
Ca(u) Cin (u) Cout (u) Deg(u)
(36)
18

---

Published as a conference paper at ICLR 2025
where Cin(u) (u), Cout (u) and Deg(u) are denoted as the in-degree, out-degree, and total degree of the node u. For the betweenness centrality of the node u in an undirected graph, it can formulated as practice, we utilize the library of NetworkX Hagberg al. (2008) to implement this.
Ca(u) = E spttp
(
(37)
9st
where 9st is the total number of shortest paths from node s to node i, (u) is the number of those paths that pass through v. For large graphs, exact calculation of betweenness centrality can be time-consuming, thus approximation algorithms using random sampling are often employed. In
With these two metrics to measure the centrality of the nodes, which are denoted as C(u) in general, the modulated 17 can be mathematically expressed
Mu 9A 9 (C(u), C(v))), Tu = gx (C(u)).
(38)
where (-) and gx gx(+) are two assignment functions that map the node centrality to one of the predefined 17 values.
Concentration Modulation for molecule graph generation For molecule graph generation, we provide straightforward strategy that regards the carbon atom as the most important node, well as the bonds connected to the carbon atoms as the important edge in molecule graph. Specifically, for various types of carbon-atom bond, we first rank the importance of bonds in the following order: carbon-carbon bonds, carbon-nitrogen bonds, carbon-oxygen bonds, carbon-sulfur bonds, and so on. Then we can assign predefined on different nodes and edges depending on their "importance" in molecule graph.
D.3 MODEL ARCHITECHTURE
We leverage the graph transformer network introduced in Dwivedi & Bresson 2020) and Vignac et al. (2023) cross all graph generation tasks. Each graph transformer layer consists of a graph attention module, as well as fully-connected layers and layer normalization. It employs self-attention module to update node features, then uses FiLM layers (Perez et al., 2018) to incorporate edge features and global features. Since the data we transformed falls within the range of [0, 1], we apply the sigmoid function to the output of node features and adjacency matrices to model the one-hot encoded representation of node and edge.
D.4 SCHEDULE OF DIFFUSION PROCESS IN GBD
Following Zhou et al. 2022)) we employ a sigmoid diffusion schedule defined as as 1/(1 co -c- =o)") throughout all experiments, where cp = 10 and c₁ = -13.
E EXPERIMENTAL DETAILS
E. GENERAL GRAPH GENERATION
Datasets We evaluated our model using three synthetic and real datasets of varying size and connectivity, previously used benchmarks in the literature (Cho al.) 2023 Jo et al. 2022): Ego-smal 11 (Sen et al. 2008) consists of 200 small real sub-graphs from the Citeseer network dataset with
consists of 100 randomly generated synthetic graphs with 12 < N < 20, where the graphs are constructed by two equal-sized communitics, each of which generated by the Erdös Rényí model (Erdōs et al. 1960), with p = 0.7 and 0.05NN inter- community edges are added with uniform probability as in previous works (Jo et al., 2022; Niu et al.) 2020b). Grid consists of randomly generated 100 standard 2D grid graphs with 100 < N 400 and the maximum number of edges per node is 4 since all nodes are arranged in regular lattice. Planar comprises 200 synthetic planar graphs, each containing N = 64. nodes. SBM includes 200 synthetic stochastic block model graphs, where the number of communities is randomly sampled from to 5, and the number of nodes in each community is randomly sampled from 20 to 40. The probability of edges between communities is 0.3 and that of edges within communities is 0.05.
18. Community-smal
19

---

Published as a conference paper at ICLR 2025
Evaluation metries For fair comparison, we follow the experimental and evaluation settings of et al. (2022) (023). using the same train/test split, where 80% of the data is used as the training set and the remaining 20% as the test set. We adopt maximum mean discrepancy (MMD) evaluation metric to compare three graph property distributions between test graphs and the same number of generated graphs: degree (Deg.), clustering coefficient (Clus.) and count of orbits with 4 nodes (Orbit). Note that we use the Gaussian Earth Mover's s Distance (EMD) kernel to compute the MMDs following the method used in previous work (Jo et al.) 2022] Cho et al. 2023). Additionally, for graphs with more complex structures like P Planar and SBM, we report the eigenvalues of the graph Laplacian (Spec.) and the percentage of valid, unique, and novel graphs (V.U.N.) measure whether the model has learned the intrinsic feature distribution and global properties of the graph. lower value is better for all of these metrics except V.U.N. Specifically, graph is defined as a valid planar graph if it is connected and planar. Following the statistical test introduced in Martinkus ct al. (022). we determine that a graph is a valid SBM graph if and only if it has a community count between 2 and 5, and node count inside each community between 20 and 40.
our
Implementation details We follow the evaluation setting of Jo et al. 2022 Cho al. 2023 to generate graphs of the same size as the test data in each run and we report the mean and standard deviation obtained from 3 independent runs for each dataset. We report the baseline results taken from Cho et al. (2023), except for the results of ConGress in Tables [and which we obtained by running its corresponding open-source code. For fair comparison, we adopt the Graph Transformer (Dwivedi & Bresson 2020 Vignac et al.) (2023) as the neural network used in GDSS+Transformer (Jo et al. 2022). DiGress (Vignac et al. 2023). ) and DruM (Jo et al. 2023). We set the diffusion steps to 1000 for all the diffusion models. For important hyperparameters mentioned in Sec 2.33 we usually set [10000, 100, 30, 10) for the normalized degrees corresponding
Scale = 0.9, Shaft = 0.09. and
to the intervals falling in the interval split by [1.0, 0.8, 0.4, 0.1]. respectively. In practice, we set threshold as 0.5 to quantize generated continue adjacency matrix.
E.2 2D MOLECULE GENERATION
Datasets We utilize two widely- -used molecular datasets as benchmarks, as described in Jo et al. (0023): QM9 (Ramakrishnan et al. 2014), consisting of 133,885 molecules with N S 9 nodes from 4 different node types and ZINC250k (Irwin et al., 2012), consisting of 249, molecules with
N < 38 nodes from node types. Molecules in both datasets have edge types, namely single bond, double bond, and triple bond. Following the standard procedure in the literature (Shi et al. (2020)
[uo et al. 2021 Jo et al. 2022 2023), we kekulize the molecules using the RDKit library (Landrum al. 2006) and remove the hydrogen atoms from the molecules in the QM9 and ZINC250k datasets.
Evaluation metrics Following the evaluation setting of Jo et al. 2022), we generate 10,000 molecules for each dataset and evaluate them with four metrics: the ratio of valid molecules with- out correction (Val.). Frechet ChemNet Distance (FCD) evaluates the chemical properties of the molecules by measuring the distance between the feature vectors of generated molecules and those in the test set using ChemNet. Neighborhood Subgraph Pairwise Distance Kernel (NSPDK) assesses the quality of the graph structure by measuring the MMD between the generated molecular graphs and the molecular graphs from the test set. Scaffold Similarity (Scaf.) evaluates the ability to generate similar substructures by measuring the cosine similarity of the frequencies of Murcko scaffolds (Bemis & Murcko 1996).
Implementation details We follow the evaluation setting of Jo et al. 2022 2023) to generate
10,000 molecules and evaluate graphs with test data for each dataset. We quote the baselines results from Jo et al. (2023). For a fair comparison, we adopt the Graph Transformer (Dwivedi & Bresson 2020 Vignac et al. 2023) as the neural network used in GDSS+Transformer (TF) (Jo et al.]22022, DiGress (Vignac et al. 2023), and DruM (Jo et al.] 2023). We apply the exponential moving average (EMA) to the parameters while sampling and set the diffuusion steps to 1000 for all the diffusion models. For both QM9 and ZINC250K, we encode nodes and edges to one-hot and set Scate = 0.9, Shift = 0.09. For n modulated in molecule generation, with the help of chemical knowledge, we apply 17 [10000, 100, 100, 100, 30) to curbon-carbon bonds, carbon- nitrogen, carbon-oxygen, apply 7 10000, 100, 100, 100,30 on carbon atom, nitrogen atom, oxygen atom and other possible
and other possible bonds, respectively. For 17 of nodes,
20

---

Published as a conference paper at ICLR 2025
Table 6: Additional 2D molecule generation results on CM9 dataset.
QM9 (IN) s
Method
Valid (%) f
FCD L
NSPDK
Scaf. f
Uniq (%) f
Novelty (96 1
MoFlow
91.36
4,467
0.0169
0.1447
98.65
94.72
GraphAF
74,43
5.625
0.0207
0.3046
88.64
86.59
GraphDF
93.88
10.928
0.0636
0.0978
98.58
98.54
EDP-GNN
47.52
2.680
0.0046
0.3270
99.25
86.58
GDSS
95.72
2,900
0.0033
0.6983
98.46
86.27
GDSS+TF
99.68
0.737
0.0024
0,9129
DiGress
98.19
0,095
0.0003
0,9353
96.67
25.58
SwinGNN
99.71
0.125
0.0003
96.25
17.34
GraphARM
90.25
1.22
0.0020
95.62
70.39
EDGE
99.10
0,458
0.763
100.0
GruM
99.69
0.108
0.0002
0.9449
96.90
24.15
GBD
99.88
0.093
0.0002
0.9510
97.12
26.32
Table 7: Additional molecule generation results on 2INC250% dataset.
ZINC250K (N)
Method
Valid (%)
FCD L
NSPDK
Scaf.
Uniq (%)
Novelty (%) f
MoFlow
63.11
20.931
0.0455
0.0133
99.99
100.0
GraphAF
68.47
16.023
0.0442
0.0672
98.64
99.99
GraphDF
90.61
33.546
0.1770
0.0000
99.63
100.0
EDP-GNN
82.97
16.737
0.0485
0.0000
99.79
100.0
GDSS
97.01
14.656
0.0195
0.0467
99.64
100.0
GDSS+TF
96.04
5,556
0.0326
0.3205
DiGress
94.99
3,482
0.0021
0.4163
99.97
99.99
SwinGNN
81.72
5,920
0.006
99.98
99.91
GraphARM
88.23
16.26
0.055
99.46
100.0
GruM
98.65
2.257
0.0015
0,5299
99.97
99.98
GBD
97.87
2,248
0.0018
0,5042
99.97
99.99
applying the appropriate for different node types and edge types can prolong the presence of related substructures during the diffusion process. In practice, we set threshold as 0.5 to quantize generated continue adjacency matrix, and the value in discrete adjacency matrix is 0 after quantizing and only if all values in each dimension are all O.
atoms, respectively. As described in Section 2.3
Complete results on 2D molecule generation We provided additional results including Unique and Novelty on 2D molecule generation in T Table
E.3 COMPUTING RESOURCES
For all experiments, we utilized the PyTorch (Paszke et al. 2019) framework to implement GBD and trained the model with NVIDIA GeForce RTX 4090 and RTX A5000 GPUs.
F ADDITIONAL EXPERIMENTAL RESULTS
F.1 EVALUATION WITH LARGER SAMPLE SIZE
As described in Section small number of nodes and the insufficient size of the sampled graphs can lead to large standard deviations when evaluating with the reference graph on smaller dataset. Therefore, we attempted evaluate the large number generated graphs and report the results in Table We observe that our proposed GBD outperforms previous continuous and discrete diffusion models on both smaller datasets. Furthermore, GBD significantly surpasses the wavelet- based diffusion model (Wave-GD) by wide margin the Community small dataset, evidenced by both means and standard deviations, Specifically, GBD achieves 85 5000% 90.5%, and 40.0% improvements over Wave-GD in the MMDs means of Degree, Cluster, and Orbit, respectively, indicating that our
21

---

Published as a conference paper at ICLR 2025
proposed model is capable of generating smaller graphs that closer to the data distribution with better stability.
Table 8: Generic graph generation results with enlarged sample (1024 graphs).
Ego-small
Community small
Method
Deg. +
Clus.
Orbit.
Avg. 4
Deg. +
Clus. +
Orbit.
Avg. 4
GraphRNN
0.040
0,050
0.060
0.050
0.030
0.010
0.010
0.017
GNF
0.010
0.030
0.001
0.014
0.120
0.150
0.020
0.097
EDP-GNN
0.010
0.025
0.003
0.013
0.006
0.127
0.018
0.050
GDSS
0.023
0.020
0.005
0.016
0,029
0.068
0.004
0.034
0.030
0.050
0.008
0.030
0.004
0.047
0.001
0.017
ConGress
0.001)
0.003)
0.001)
0.000)
0.000)
0.000)
0.009
0.031
0.003
0.014
0.003
0.009
0.001
0.004
DiGress
0.000)
0.002)
0.000)
0.000)
0.001)
0.000)
0.010
0.018
0.005
0.011
0.016
0.077
0.001
0.031
Wave-GD
0.001)
0.003)
0.002)
0.000)
0.006)
0.002)
0.007
0.011
0.003
0.010
0.002
0.007
0.001
0.003
GBD
(#: 0.000)
(# 0.001)
( 0.000)
( 0.000)
(# 0.001)
(# 0.000)
F.2
COMPARISON ON VARIOUS NODE FEATURE INITIALIZATTON.
Node feature initialization features, respectively:
We initialize node representations using the following node-level
Degree (one-hot): Degree with one-hot format is a categorical representation of a node's degree. It encodes the degree information as a binary vector where each position corresponds to a possible degree value. The position corresponding to the node's 's actual degree is set to 1, while all other positions are O.
Degree (normalized): The normalized degree is continuous representation of node's degree, scaled to a value between and 1.
Centrality: Here we adopt the normalized betweenness centrality as initial node features and is a measure of node's importance based on its role in connecting other nodes. quantifies the fraction of shortest paths between all pairs of nodes that pass through the given node. The normalized version scales this value to be between and 1.
Eigenvectors: Following Jo et al. (0022), we adopt the two first eigenvectors associated to eigenvalues as initial node features.
Results As shown in Table GBD outperforms GDSS TF and ConGress by a large margin in all MMDs when the node representation exhibits sparsity and long-tailedness. Additionally, GBD achieves competitive performance compared with other Gaussian-based diffusion models while the node feature is initializing with Eigenvectors. This demonstrates that our proposed GBD has the ability to model graphs with flexible node features, indicating its potential for modeling graphs with more informative features.
G VISUALIZATION
We follow the implementation described in Section 2.3 and the nodes in all adjacency matrices are reordered by decreasing the degree of nodes. Apparently, we can find that edges associated with nodes with large degree will be the first to be identified and then spread in decreasing order of degree on both datasets in Appendix G.I] It is worth noting that the reverse beta diffusion can converge rapidly, leading to generated graphs with correct topology at an early stage. This shows that our proposed GBD can further explore the potential benefits beta diffusion, resulting in valid graphs with stability and high quality. For generated molecule graphs shown in Appendix G.I] we observe that GBD can successfully generate valid and high-quality 2D molccules, verifying its ability to model attributed graphs. More generated graphs presented following.
22

---

Published as a conference paper at ICLR 2025
Table The effect of Feature Initialization on Community-small and Ego-small.
Community-
Node Feature
Degree (one-hol)
Degree (normalized)
Centralities
Eigenvectors
Method
Deg.
Clus.
Orhit.
Deg.
Clus.
Orbit.
Deg.
Clus.
Orbit.
Deg.
Clus.
Orbit.
GDSS-TF
0.008
0.080
0.005
0.009
0.077
0.005
0.010
0.075
0.004
0.005
0.061
0.003
ConGress
0.024
0.072
0.006
0,020
0.076
0.006
0.013
0.079
0.005
0.004
0.067
0.003
GBD
0.002
0.060
0.002
0.004
0.059
0.003
0.003
0.059
0.003
0.004
0.064
0.002
Ego-samll
Node Feature
Degree (onc-hot)
Degree (normlized)
Centralities
Bigenvoctors
Method
Deg.
Clus.
Orbit.
Deg.
Clus.
Orbit.
Deg.
Clus.
Orbit.
Deg.
Clus.
Orbit.
GDSS+TF
0.016
0.020
0.004
0.018
0.023
0.005
0.017
0.026
0.006
0.013
0.015
0.002
ConGress
0.045
0.059
0.015
0.037
0.064
0.017
0.032
0.057
0.014
0.020
0.029
0.011
GBD
0.011
0.014
0.002
0.013
0.017
0.002
0.015
0.012
0.003
0.017
0,016
0.002
G.1
GENERATIVE PROCESS GBD ON GENERAL DATASETS
We visualize the generative process of GBD the Communi -tn small 11 and the Ego small
dataset in Figures and respectively.
0.17
0.2T
0.3T
0.4T
0.5T
0.67
0.77
0.8
0.9
Figure 5: Visualization of the generative process of GBD on the Commun i ty-amal dataset.
G.2 GENERATIVE PROCESS GBD ON COMPLEX GRAPH
We provide the visualization of the complex graph generated by GBD on the Planar and the SBM datasets in Figure 7 and in Figure & respectively.
G.3 GENERATED GRAPHS OF GBD ON 2D MOLECULE DATASETS
We provide the visualization the 2D molecules generated by GBD on the QM9 and the 2INC250K datasets in Figure 9 and in Figure 10 respectively.
23

---

Published as a conference paper at ICLR 2025
0.1T
0.2T
0.3T
0.4T
0.5T
0.60
0.77
0.8T
0.97
Figure 6: Visualization of the generative process of GBD on the kgo-sma smal datasct.
Figure Visualization the generated graphs of GBD on the Planar dataset.
G.4 GENERATED GRAPHS GBD ON BA-NETWORKS
We provide the visualization of the BA-networks (n 20, = 2) generated by GBD in Figure []
24

---

Published as a conference paper at ICLR 2025
Figure 8: Visualization of the generated graphs of GBD the SBM dataset.
NH
0H
HNN
Figure 9: Visualization of the generated graphs of GBD on the QM9 datasct.
25

---

Published as a conference paper at ICLR 2025
tor
Figure 10: Visualization of the generative graphs of GBD on the X I NC250k dataset.
Figure 11: Visualization of the generative graphs of GBD on the BA-network (n = 20, m = 2).
26


Reviews:
[{"review_id": "RCBJW1SeOA", "reviewer": "Reviewer_gBaw", "summary": "The paper proposes graph beta diffusion for the task of generating small graphs such as molecules. The core concept is approaching this task by adapting beta diffusion (Zhou et al., 2023), which is meant for generating data within bounded ranges (e.g., 0 to 1 for non-edge and edge) and is based on the beta diffusion rather than the Gaussian distribution. In addition to this core idea, the paper also explores several design ideas to strengthen the proposed method, including \"concentration modulation,\" which modify the diffusion distribution for important positions in the graph. The paper concludes with experiments on real and synthetic datasets, showing that the proposed method is at least competitive with other recently proposed methods in terms of matching certain graph statistics. There are also ablation experiments supporting the lift from the design ideas.", "questions": "Some questions are given above. Additionally:\n\n- As stated on line 458, this method predicts $\\mathbb{E}[\\mathbf{G}_0 | \\mathbf{G}_t$], which is not the standard diffusion setup, and as stated on line 160, this requires a neural network that predicts the conditional expectation of $\\mathbf{G}_0$ given $\\mathbf{G}_t$. Could the authors please expand on this design decision and its possible consequences? In particular, is it possible this reduces the diversity of samples?\n- Perhaps relatedly, regarding concentration modulation: How is $\\eta$, which corresponds to important positions in the sample, set at sampling time? Is the graph distribution generated by this method equivariant to permutations of the nodes?\n\n### Typos\n- Line 376 \"Transofrmer\"\n- Line 522 \"Centrailities\"", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The core idea of applying a diffusion method based on the beta distribution to graph generation seems logical.\n- The graph generation task that this paper tackles is enjoying a lot of attention recently.\n- The writing is generally clear.\n- The evaluation is fairly extensive, showing that the method is at least competitive with other recent approaches, and also includes ablations for the proposed design components.", "weaknesses": "- Since the main thrust of this paper is approaching graph generation with a diffusion method that is suited for bounded data, like the probability of each edge, there could be more discussion of alternatives to beta diffusion. What makes beta diffusion (Zhou et al., 2023) more suited for this task as opposed to, e.g., Dirichlet Diffusion Score Model (Avdeyev et al., 2023) or Dirichlet Flow Matching (Stark et al., 2024)?\n- Relatedly, given that the main thrust is application of beta diffusion, there could be more intuition given for beta diffusion itself, given that it was proposed in a recent paper.\n- With the exception of concentration modulation, little of the design seems specific to graphs, making this largely an application of a prior work to a specific domain. There could be more elucidation of what is gained from using beta diffusion vs standard diffusion in a graph context, e.g., some empirical or theoretical work showing that the beta distribution is more suited to capturing certain graph motifs.\n- $\\omega$ seems to be a key hyperparameter controlling the weight of two losses in beta diffusion. It seems unexplored here beyond reusing the value in the beta diffusion paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dlnTNfklky", "reviewer": "Reviewer_ioTm", "summary": "This paper presents a novel graph generation model by adapting the recent diffusion process work (Zhou et al., 2023) to handle graph-structured data. The authors assess the performance of the proposed model against state-of-the-art methods on both synthetic and real-world datasets, including molecular datasets commonly used in graph generation tasks.", "questions": "**Questions:**\n\n- The methodology mainly adapts the work of Zhou et al. (2023) for graph-structured data and raises concerns about the originality of the paper. Could the authors emphasize their unique contributions beyond this adaptation?\n- The reported improvements over baseline methods appear minimal. Could the authors clarify the practical impact of these results?\n- Tables 1 and 2 use different baseline models, omitting certain comparisons (e.g., Wave-GD, GraphARM, GNF, GraphVAE in Table 1; GruM, GDSS+TF, SPECTRE in Table 2). Tables are missing standard deviation values (Tables 2 and 3) and certain metrics (e.g., Spec. and V.U.N in Table 1), with no explanation for missing entries. Could the authors clarify their choices?\n- Does the proposed model offer any guarantees regarding the connectivity of the generated graphs?\n\n\n**Additional comments:**\n- The provided equations in the paper are a bit challenging to follow, especially for readers unfamiliar with the work of Zhou et al. (2023). The authors might provide additional background or a summary of this prior work to improve readability. \n- The graph images in the first row of Figure 2 are unclear, and it is difficult to see the nodes and edges. The authors might consider improving the quality or resolution of these visuals.\n- Similarly, the SBM graph in Figure 3 is hard to interpret due to its size. Providing an adjacency matrix or alternative visualization might enhance readability.\n\nGiven the concerns outlined above regarding the experimental evaluations and originality of the paper, I recommend a rating of 5 for the paper.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Adapting the recent beta diffusion process to graph-structured data.\n- The model is evaluated on both synthetic and real-world data, including widely used molecule datasets.\n- The structure of the paper is generally well-organized.", "weaknesses": "- While the model adapts the diffusion process for graph data, there is limited discussion on unique contributions beyond this adaptation. Emphasizing the model’s distinct aspects and theoretical advancements would strengthen the paper's impact.\n- Similarly, the paper heavily references Zhou et al. (2023), making it challenging for readers who are not familiar with this work to fully understand the technical content. \n- The reported results raise questions about the practical significance of the proposed architecture, with inconsistent comparisons across tables (missing baselines and metrics like Spec. and V.U.N.), lack of standard deviation reporting in Tables 2 and 3, and missing entries, all of which reduce confidence in the experimental evaluation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xUiM31AaXn", "reviewer": "Reviewer_9sdC", "summary": "This paper introduces Graph Beta Diffusion to address the inherent conflict between graph structure and diffusion models. It also proposes a modulation technique aimed at stabilizing the topology of the key graph.", "questions": "1.For a graphset data, a concentration modulation is calculated for each graph and then concat them into a matrix. Will this cause a large consumption of time? And how should Concentration modulation be defined during generation? Because we don't know some of the properties of the graph in advance when sampling from the beta distribution?\n2.What is the sampling rate of this method? And how does the sampling rate affect the quality of the generated graphs?\n3.Can this approach be extended to conditional diffusion generation? Other methods like GDSS or Digress can easily combine with conditional generation in theory.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.The paper is well-articulated and easy to comprehend.\n2.The rationale behind this paper is quite sound, as diffusion models and graph structures do not align well.", "weaknesses": "1.Could the author offer a comparison of complexity? For instance, the calculation of concentration appears to be time-consuming. Authors should provide a comparison of complexity with other methods, preferably including both theoretical analysis as well as experimental data. (e.g. complexity comparison between GDSS and Digress)\n2.Lack of detection for networks with other topological properties. BA networks, for example, follow a power-law distribution.\n3.The sample rate analysis and scalability of this method are not discussed in detail. For example, in an SDE-based diffusion framework, we can use many different accelerated sampling methods, as well as perform conditional generation. But is this approach effective?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hBYNshcslg", "reviewer": "Reviewer_PnYi", "summary": "This paper presents a Graph Beta Diffusion for the natural conflict between graph structure and diffusion model. A modulation technique is proposed to stabilize the topology of the key graph.", "questions": "1. How to explain the beta distribution is better suited to the graph than other discrete distributions.\n2. Can concentration modulation be used with other diffusion methods?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The motivation of this paper is very reasonable. Diffusion model and graph structure are incompatible.\n2. The paper is well written and is easy to understand.\n3. The Concentration modulation method is very cleverly designed. It seems to make good use of the topological properties of the graph structure.", "weaknesses": "1. The authors give no clear evidence as to why beta diffusion is effective at modeling the graph structure. The discrete distribution can take many forms. Or why not use BFN to model the distribution of a graph.\n2. In terms of experimental results, if concentration modulation is not included, the effect of beta diffusion is not better than Digress and Grum. This does not effectively explain the effectiveness of beta diffusion. Another point of view is, can the ordinary diffusion model also use this idea to control the noise process?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)