Discrete-state Continuous-time Diffusion for Graph Generation
Authors: Zhe Xu
Ruizhong Qiu
Yuzhong Chen
Huiyuan Chen
Xiran Fan
Menghai Pan
Zhichen Zeng
Mahashweta Das
Hanghang Tong
Venue: NeurIPS 2024 poster (2024)
Keywords: graph generation
diffusion generative model
Primary area: diffusion_based_models

Abstract: Graph is a prevalent discrete data structure, whose generation has wide applications such as drug discovery and circuit design. Diffusion generative models, as an emerging research focus, have been applied to graph generation tasks. Overall, according to the space of states and time steps, diffusion generative models can be categorized into discrete-/continuous-state discrete-/continuous-time fashions. In this paper, we formulate the graph diffusion generation in a discrete-state continuous-time setting, which has never been studied in previous graph diffusion models. The rationale of such a formulation is to preserve the discrete nature of graph-structured data and meanwhile provide flexible sampling trade-offs between sample quality and efficiency. Analysis shows that our training objective is closely related to the generation quality and our proposed generation framework enjoys ideal invariant/equivariant properties concerning the permutation of node ordering. Our proposed model shows competitive empirical performance against other state-of-the-art graph generation solutions on various benchmarks while at the same time can flexibly trade off the generation quality and efficiency in the sampling phase.

Discrete-state Continuous-time Diffusion for Graph Generation
Zhe Xu"
Ruizhong Qiu'
Yuzhong Chen'
Huiyuan Chen
Xiran Fan
Menghai Pan'
Zhichen Zeng"
Mahashweta Das
Hanghang Tong"
Abstract
Graph a prevalent discrete data structure, whose generation has wide applications such drug discovery and circuit design. Diffusion generative models, as an emerging research focus, have been applied to graph generation tasks. Overall, according to the space of states and time steps, diffusion generative models discrete-/contiiuuus-iii fashions. In this paper, formulate the graph diffusion generation in discrete- state continuous-timg setting, which has never been studied in previous graph diffusion models. The rationale of such formulation is to preserve the discrete nature of graph-structured data and meanwhile provide flexible sampling trade-offs between sample quality and efficiency. Analysis shows that our training objective is closely related to the generation quality and our proposed generation framework enjoys ideal invariant/equivariant properties concerning the permutation of node ordering. Our proposed model shows competitive empirical performance against statc-of- the-art graph generation solutions on various benchmarks and at the same time can flexibly trade off the generation quality and efficiency in the sampling phase.
be categorized into discrete-/contimuuus-tii
Introduction
Graph generation has been studied for a long time with broad applications, based on
Time space
either the one-shot (i.e., one-step) [50] 39
GeoDiff ContGF GraphGIP
56 51 72 32
rugo-regressive genera- The former generates all the graph components at once and the latter does that sequentially. re- cent trend of applying diffusion generative to graph generation tasks attracts increasing attentions because of its excellent performance and solid theo- retical foundation. In this paper, we follow the one-shot generation paradigm, the same as most graph diffusion generative models.
Discrete
DHIBP
DiGress
tion paradigm
29
42 52
GDSS NeuraiPLexor
Continuous
DisCo (This work)
models 667 23 70
Continuous
space
Figure 1: A taxonomy of graph diffusion models.
Some earlier attempts at graph diffusion models treat the graph data in a continuous state space by viewing the graph topology and features continuous variables (56). Such a formulation departs from the discrete nature of graph-structured data; e.g. topological sparsity is lost and the discretization in the generation process requires extra hyper-parameters, DiGress 773 one of the early efforts
University Illinois Urbana- Sabana-Champaign [zhexu3, rq5, zhichenz, htong] illinois.edu Visa Research. (yuzchen, hchen, xirafan, menpan, mahdas) @visa.com
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

applying discrete-state diffusion models to graph generation tasks and is the current state-of-the-ar graph diffusion generative model. However, DiGress is defined in the discrete time space whose generation is inflexible. This is because, its number of sampling steps must match the number of forward diffusion steps, which a fixed hyperparameter after the model finishes training. A unique advantage of the continuous-time diffusion models 770 32) lies in their flexible sampling process, and its simulation complexity is proportional to the number of sampling steps, determined by the step size of various numerical approaches (e.g., r-leaping [8] g 7T) and decoupled from the models' training. Thus, a discrete-state continuous- diffusion model is highly desirable for graph generation tasks.
Driven by the recent advance of continuous-ting time Markov Chain (CTMC)- based diffusion generative model [8]. we incorporate the ideas of CTMC into the corruption and denoising of graph data and propose the first discrete-state continuous- mattinuous-time graph diffusion generative model. It shares the same advantages as DiGress by preserving the discrete nature of graph data and meanwhile overcomes the drawback of the nonadjustable sampling process in DiGress. This Discrete state Continuous-tine graph diffusion model is named DisCo.
DISCO bears several desirable properties and advantages. First, despite its simplicity, the training objective has rigorously proved connection to the sampling error. Second, its formulation includes a parametric graph-to-graph mapping, named backbone model, whose input-outpur architecture is shared between DisCo and DiGress. Therefore, the graph transformer (GT)-based backbone model [54] from DiGress can be seamlessly plugged into DisCo. Third, a concise message- message-passing neural network backbone model is explored with DisCo, which is simpler than the GT backbone and has decent empirical performance. Last but not least, our analyses show that the forward and reverse diffusion process in DIsCo can retain the permutaioon-qqivvraannnwee
properties for its training loss and sampling distribution, both of which are critical and practical inductive biases on graph data.
Comprehensive experiments on plain and molecule graphs show that DisCo can obtain competitive or superior performance against state-of-the-art graph generative models and provide additional sampling flexibility. Our main contributions are summarized:
Model. We propose the first discrete-state continuous- time graph diffusion model, DISCO. We utilize the successful graph-to suph-to-graph neural network architecture from DiGress and further explore a new lightweight backbone model with decent efficacy.
Analysis. Our analysis reveals (1) the key connection between the training loss and the approx- imation error (Theorem (3.3) and (2) invariant/equivariant properties of DisCo in terms of the
permutation of nodes (Theorems 3.8 and (.9)..
Experiment. Extensive experiments validate the empirical performance of DIsCO.
2 Preliminaries
2.1 Discrete-State Continuous-time Diffusson Models
A D-dimensional discrete state space is represented as X' = CjP A continuous-time Markov Chain (CTMC) {x, [x] .......--0 x: Hejorr is characterized by its (time-dependent) rate matrix R2 E x| Here x, is the state at the time step t. The transition probability 4: between from time 1 satisfies the Kolmogorov forward equation, for 1,
d dt (x, (x.) = Σ
SEX
The marginal distribution can be represented as q: (xx) = ExSex Otjo(x; (aa) (Xo) where Taata (Xx)) is the data distribution. If the CTMC is defined in time interval []. and if the rate matrix R, is well-designed, the final distribution (x(x)) can be close to a tractable reference distri- bution Trat (xar(X)). ), e.g., uniform distribution. We notate the reverse stochastic process as xx well-known fact (e.g., Section 5.9 in (63) is that the reverse process {x+ (x:)eejo.r) is also a CTMC,
characterized by the reverse rate matrix: yx
(y x). The goal of the CTMC-based q(x)
g(y)
diffusion models an accurate estimation of the reverse rate matrix Rł so that new data can be gener- ated by sampling the reference distribution Trat and then simulating the reverse CTMC [16 17 18
However, the complexity of the rate matrix prohibitively high because there are D possible states. Specifically,
A reasonable simplification is to factorize the process over dimensions
S 7 73

---

Predefined forward diffusion with R,
== 0
t= T
Reverse generation process with Rg,-
Figure 2: An overview of DISCo. A transition can happen at any time in [0, T.
the forward process is factorized 4:/ x2) I 2tla (2]])= for < t. Then, the forward diffusion of each dimension is independent and is governed by fimension-speciiee forward rate matrices {R;) d==1 With such factorization, the goal is to estimate the dimension-specife reverse
rate matrices (R dd=
The dimension-specinf
reverse
rate
is
represented as
(x
(1j0(zz wgg) 9ojo (=//xx)) Campbell al. estimate (,/(=////x via neural network py such that pe (zg (x, t) = 9oje ( bx: Sun et al. 71 propose another singleton conditional po(u"
Σng (y Ird) 9uio =n)
biv"lx whose rationale is Brook's 's Lemma S 49 distribution-based objective Pe ((v())))
2.2 Graph Generation and Notations
We study the graphs with categorical node and edge attributes. A graph with nodes is represented by its edge type matrix and node type vector: g = (E, F), where = (clt.)) ) ji.jent E f1.....a
b)". 1|ax", F = (f') seNt, f1.....b)""
and are the numbers of node and edge types, respectively.
Notably, the absence of an edge is viewed as special edge type, so there are (a + 1) edge types in total. The problem study is graph generation where N graphs ] from an inaccessible
graph data distribution are given and we aim to generate M graphs {9* "0'heet from 6.
3 Method
This section presents the proposed discrete-state continuous-time graph diffusion model, DisCo whose overview is Figure Section Scction introoduees the necessity to factorize the diffusion process and Section 3.2 details the forward process. Our training objective and its connection to sampling are introduced Sections 3.3 and 3.4 respectively. Last but not least, specific neural architecture of the graph-to-ge to-gaph backbone model and its properties regarding the permutation of node ordering are respectively. All proofs in Appendix.
introduced in Sections
3.5 and 3.6
3.1 Factorized Discrete Graph Diffusion Process
The number of possible states of an n-node graph is (a + 1)n² x 6" which is intractably large. Thus, we follow existing discrete models 22 8 71 73 and formulate the forward processes on every node/edge to be independent. Mathematically, the forward diffusion process for & is factorized as
4o (G. G.) = II
dej (e
(1.) ((55)) (
I Te (filst)
d==1
where the edge type transition probabilities (e (t.f) (e Disent. and node type transition probabilities (fll are characterized by their forward rate matrices {R. (id)
Jijent
and (R) (RIient. respectively. The forward processes, i.c., the forward rate matrices in our context, are predefined, which will be introduced in Section 3.2 Given the factorization forward transition probability in Eq. (2) question is raised: what is the corresponding factorization of the forward rate matrix (R₂) and the reverse rate matrix (R,)? Remark 3.1 shows such factorization.

---

Algorithm Training of DISCO
1: A training graph Go (Uo), feo ()))))) is given.
2: Sample t ~ U(,rr); sample G. based on transition probabilities qejoff = vi.o = u) =
(eli Rys)) uuo and q: (e = vieo = u) = (elā ((s)R Juu. given Go (1f0), fo) ().
3: Predict the clean graph Go = (ff(), 3) + (f9%) ( (e(30))))) given Gr.
4: Compute cross-entropy loss between Go and Go based Eq. 6 and update 0.
Remark 3.1. (Factorization of rate matrices, extended from Proposition 3 of 8 Given the factorized forward process Eq. (2. the overall rate matrices are factorized
(G, = Σ A Σ
B (b.)
(3)
Σ (e (1-5)
L (J (0)
R,(9 Σ A
qol (fill)
qe (ea(e( Qo (c) (1:))
( (4)
qe a (f 56)
fo
where A8 = RI 1' Blda) = R, R (E(L.)) ( ) jo (ra gretts) the operator f (or dgr pre()))))))))))) checks whether two graphs G and G are exactly the same except for node (or the edge between nodes and j).
Note that this factorization itself is not our contribution but necessary part of our framework, we mention it here for completeness. Its full derivation is in Appendix Section A Next, we detail the design of forward matrices.
3.2 Forward Process
(a.5) (R((d)) Jijeng. and {Rilien,. important because (1) the probability distributions of node and edge types, {q (a(fi)) and ( BiJeN should converge their reference distributions within [0, and (2) the reference distributions should be easy to sample (e.g., uniform distribution). We follow g to formulate R
proper choice of the forward rate matrices (R,
(6d) Vi, and R; B(t) R/, Vi, where B(t) is corruption schedule, (R! (1d)) and {R}} are the base rate matrices. For brevity,
(i.i) 3())
set all the nodes/edges to share common node/edge rate matrix, i... R! R. and R = Ry, Vi.j. Then, the forward transition probability for all the nodes and edges are q: = vl.o u) (e.i dds) ww and (ej vlea u) (el' (ss) )ue respectively. We omit the superscript i (or (i.j) because the transition probability is shared by all the nodes (or edges). The detailed derivation of the above analytic forward transition probability is provided in Appendix- Section
For categorical data, a reasonable reference distribution a uniform distribution, i.c., F. = for 1
nodes and म. = a+1 for edges. addition, inspired by 73,, we find that node and edge marginal distributions my and m. are good choices as the reference distributions. Concretely, an empirical estimation of my and m. is to count the number of node/edge types and normalize them. The following proposition shows how to design the rate matrices to guide the forward process to converge uniform and marginal distributions.
The forward processes for nodes and edges converge to uniform distributions if R 11T bl and R. 11 (a I)I: they converge to marginal distributions my and m. if an all-one vector and is an identity matrix.
Proposition 3.2.
R, 1m. I R. 1m
Regarding the selection of (t), we follow
23 70 8 and set B()) = ary" (og()) for a smooth change
of the rate matrix. and y are hyperparameters. Detailed settings are in Appendix F3

---

3.3 Parameterization and Optimization Objective
Next, we introduce the estimation of the reverse process from its motivation. The reverse pro- cess is essentially determined by the reverse rate matrix R in Eq. ( whose computation needs (ofe(S and 90je(e6 ji their exact estimation is expensive because according to Bayes' rule, Pr(G) is needed, whose computation needs to enumerate all the given graphs: P(())= = Eg. 9: (
Thus, we propose parameterizing the reverse transition probabilities via a neural network i whose specific architecture is introduced in Section 3.5 The terms (1op=(f(l9) kent. and (9))(())))))))) and (p (e.0
in Eq. (4) are replaced with the parameterized (f leNt.
Thus, a parameterized reverse rate matrix (9. is repre- sented as (9,) E. + E,, Rig (id) (elts), ((l))) where (f F)
( (9)lennt.
(1:) (g), and the remaining notations are the same as Eq. Note that all the terms (r (1 (111)) ient. and
A Es l (5)) 91 o( Pojo (f61)). Ro, (e(h)) e(..)) (.)))) Eg (i5) 900 . (o)((e)
(roje (e(x)))))))))) i.jent. be viewed together graph-to toch-tt----ee to-graph mapping 0 6 6, whose input is the noisy graph G. and its output is the predicted clean graph probabilities, concretely, the node/edge type probabilities of all the nodes and edges.
Intuitively, the discrepancy between the groundtruth R. (from Eq. 44) and the parametric Rø, should be small. Theorem 3.3 establishes a cross-entropy (CE)-based upper bound of such a discrepancy, where the estimated probability vectors (sum is 1) are notated as Sö = 18
1[(.)..... - 1[ E [0, 1]
bl E [0, 1 and a(t3) (e(tt)) 1(9,), .........ppp (elt..) +
Theorem 3.3 (Approximation error). for g + E
(9,9) - (9, < C. + CRosE Eoo 9n) Σ Lee (One-Hot(Ja))
+ C₂ Cedge Reo (9 Go)
Σ
(oneHoooot)( (1.11) 2f1111)
(5)
where Ct Crobe, and Cedge are constants independent on O but dependent I, 9, and G: One-Hot transforms S/ and eg
(6.5) into one-hot vectors.
The bound in Theorem 3.3 is tight, i.e., the right-hand side of Eq. (5 is O, whenever fg
% (fil))) , Vi and efi (e (1:5) (.),, Vi.j. Guided by Theorem 3.3 we (1) take expecta-
tion of by sampling from uniform distribution L ~~ 1~~2p U( T) and (2) simplity the right-hand side of Eq. (5) by using the unweighted CE loss as our training objective:
Σ Lce (One-Hot(fo)) fo) + Σ Lex (ote e c(1
min EE, B.. (S,16))
(6)
A step-by-step training algorithm is in Algorithm 1 Note that the above CE loss has been used in some diffusion models (e.g.. 22 () but lacks good motivation, especially in the continuous-tin ttime
setting. We motivate it based on the rate matrix discrepancy, as unique contribution of this paper.
3.4 Sampling Reverse Process
Given the parametric reverse rate matrix Rg. 9), the graph generation process can be implemented by two steps: (1) sampling the reference distribution Tref (i.e., y for nodes and π. for edges) and (2) numerically simulating the CTMC from time T to O. The exact simulation of CTMC has been studied for long time, e.g., [6 1 However, their simulation strategies only allow one transition (e.g., one edge/node type change) per step, which is highly inefficient for graphs as the number of nodes and edges is typically large; once a(n) node/edge is updated, Rø, requires recomputation. A
5

---

practical approximation is to assume Rø,; is fixed during time interval [t - T, t), i.e. delaying the happening of transitions in it T. and triggering them all together at the time 7; this strategy is also known as r-leaping [8 8 71 and DISCO adopts it.
We elaborate on r-leaping for transitions of node types; the transitions of edge types similar. The (f)))) during [t t.. According to the definition of rate matrix, in [t 7, 1), the number of transitions from f Poisson(rRR, (f", f*)) For
rate matrix of the i-th node is fixed as ( F) RJ( , E gnols" (á)
( Poje (f
to f", namely fr. follows the Poisson distribution, i.e., J y categorical data (e.g., node type), multiple transitions in [t J. t) are invalid and meaningless. In other words, for the i-th node, if the total number of transitions Σ J/s.F > 1, f keeps unchanged in [L - T, I]: otherwise, if yz y = 1 and Jr. 1, i.e., there is exact 1 transition, I² jumps to A step-by-step sampling algorithm (Algorithm 2 is in Appendix.
Remark 3.4. The sampling error of r-leaping is linear to Carr [ the approximation error of the < Cerr- Interested readers are referred to Theorem 1 from 8 Our Theorem 3.3 shows the connection between our training loss and Ceer, which further
reverse rates: Σoya (R, R., (G, g)
verifies the correctness of our training loss.
3.5 Model Instantiation
As mentioned in Section 3.3 the parametric backbone (9o(9) is graph-to-gran to-graphh mapping whose input is the noisy graph It and its output is the predicted denoised graph Go. There exists a broad range of neural network architectures. Notably, DiGress (73 uses graph Transformer (GT) as p decent reference for our vontinuous-time framework. We name model with the GT backbone as DISCO-GT and its detailed configuration is in Appendix FF3 The main advantage of the GT is its long-range interaction thanks the complete self-attention graph; however, the architecture is very complex and includes multi-head self-attention modules, leading to expensive computation.
Beyond GTs, in this paper, posit that regular should be a promising choice for p (So (G)) It is recognized that the MPNNs' expressiveness might not be as good as GTs' B3 7. e.g.. in terms of long-range interactions. However, in our setting, the special type of edge and the whole graph is complete; therefore,
passing neural network (MPNN) [19
absence of edge is viewed such a limitation of MPNN is naturally mitigated, which is verified by our empirical evaluations.
Concretely, an MPNN-based graph-to-graph mapping is presented as follows, and DiSCO with MPNN backbone is named DISCO-MPNN, Given a graph G = (E, F), where E E (l...., a, a + 1 F (I.....b) 6)"" we first transform both the matrix E and F into one-hot embeddings Eωs E {0, 11)xxxx(+tt) and Fos (0, 1 jaxb, Then, some auxiliary features (e.g., the # of specific motifs) are extracted: F Faux: Ysux = Aux (oR)) to overcome the expressiveness limitation of MPNNs (.]. Here Fauz and Yauz are the node and global auxiliary features, respectively. Note that similar auxiliary feature engincering is also applied in DiGress [73]. More details about the Aux can be found in Appendix E Then, three multi-layer perceptrons (MLPs) are used to map node features Fax t F Fauz. edge features Egn. and global features Yaux into a common hidden space as Fhidden = MLP MLP on + F J. Exidden M (Eα)). Vhidden ayx(). where @ is a concatenation operator. The following formulas present the update of node embeddings (e.g.. r' = Fii,:)), edge embedding (e.g., p(())) = E().j:))), and global embedding y in an MPNN layer, where we omit the subscript hidden if it does not cause ambiguity:
Σ /0.0//))))) m.)x)
r' FiLM FILM
T',MLL MLP
(666 + (iLM(PiLM x Or))))
(7)
y y + +NA ((r')) + PNA (( (1)0)))))))
(8)
The edge embeddings are aggregated by mean pooling (i.c., Σラ= ((+.) /n); the node pair embeddings
are passed to edges by Hadamard product (i.e., r' @ r'); edge/node embeddings are merged to the global embedding y via the PNA module [12] Some FiLM modules (57) are used for the
interaction between node/edge/global embeddings. More details about the PNA and FiLM are in
Appendix F. In this paper, we name Eqs. (7) and (8) on all nodes/edges together as an MPNN
layer, F, E, y + MPNN(F, E, y). Stacking multiple MPNN layers leads to larger model capacity.

---

Finally, two readout MLPs are used to project the node/edge embeddings into imput dimensions, MLP(F) Raxb and (E) E [xxxxxa+1), which are output after wrapped with sof tmat.
Both the proposed MPNN and the GT from DiGress 773 use the PNA and FiLM merge embeddings,
but MPNN does not have multi-head self-attention layers so that the computation overhead is lower.
3.6 Permutation Equivariance and Invariance
Reordering the nodes keeps the property of given graph, which is known as permutation invariance. In addition, for given function if its input is permuted and its output is permuted accordingly,
such a behavior known as permutation equivariance. In this subsection, we analyze permutation-
equivariance//nvariacce of the (I) diffusion framework (Lemmas 3.5 3.6, and 3.7) (2) sampling
density (Theorem 3.8). and (3) training loss (Theorem (.99)
Lemma 3.5 reemutation-equivaraa layer). The proposed MPNN layer (Eqs. and permutation-eequivvriiia
The auxiliary features from the Aux are also permutation eeuivviriiniiiiiiantn (see Appendix Thus, the Note that the GT- backbone from DiGress 7 also sermutation-qquiaarian whose proof is omitted is not our contribution. Next, we show the permutation invariance of the rate matrices.
whole MPNN-based backbone poj is permutation-equivanee
Lemma 3.6 (Permutation-invariin rate matrices). The forward rate matrix of DISCO is permutation- invariant if is factorized as Eq. 3 The parametric reverse rate matrix of DiSCo (Ro,z) is iitiuttatioonivviiiann whenever the graph-to-graph backbone Pole is permutation-equivarii
Lemma 3.7 Permmutatonninvvariaatt transition probability). For CTMC satisfying the Kolmogorov forward equation (Eq. (T), if the rate matrix is permutation-inaarimn (i.e., R (x;xx))) R, (Pxs),, P(x;)), the transition probability is permutation-invaaiin (i.e., 4uja (x1 Xx)
(P(x.) (P())))))))))))))))))))))))))))) (x.),, where P a permulation.
Based on Lemmas 3.6 and 3.7 DisCo's parametric reverse transition probability is permutation
invariant. The next theorem shows the -nniaaatiioo--nvaiananeeee the sampling probability.
Theorem 3.8 cormutationninvartti
sampling probability). If both the reference distribution ørej and the reverse transition probability are ionnuutationinvariinn the parametric sampling distribution ph (Go) is permutation inntutttatioiiiariann..
In addition, the next theorem shows the permutation invariance of the training loss.
Theorem 3.9 (Permutation- innnutaaiooniivaiiantt training loss). The proposed training loss Eq. (6) is invariant to any permutation of the input graph Go if poj is permutation-equivvriann.
4 Experiments
This section includes: an effectiveness evaluation on plain graphs (Section 4.1 and molecule graphs
(Section 4.2). efficiency study (Section 4.3 and ablation study (Section (.4). Detailed
settings (Sections F.3.3) additional effectiveness evaluation (Sections F4 additional ablation ablatioon study
(Section F.5), convergence study (Section F.6). and visualization (Section F.7 are in Appendix. Our
code is released!
4.1 Plain Graph Generation
Datasets and metrics. Datasets SBM, Planar [1 and Community [82 are used. The relative squared Maximum Mean Discrepancy (MMD) for degree distributions (Deg.), clustering coefficient distributions (Clus.), and orbit counts (Orb.) distributions (the numher of occurrences of substructures with nodes), Uniqueness($e). Novelty(%), ) and Validity(%) are chosen metrics. Details about the datasets, metrics, baselines (Section F.2.2.. and results on Community (Table X are in Appendix.
Results. Table the effectiveness evaluation on SBD and Planar from which we observe:
7

---

Table 1: Performance (mean-tstd)) on SBM and Planar datasets.
Dataset
Model
Deg-L
Clus
Orb.4
Unique f
Novel f
Valid f
GraphRNN
82
6.9
1.7
3.1
100.0
100.0
5.0
GRAN 42
14.1
1.7
2.1
100.0
100.0
25.0
GG-GAN 37
4.4
2.1
2.3
100.0
100.0
0.0
MolGAN
9
29.4
3.5
2.8
95.0
100.0
10.0
SBM
SPECTRE 51
1.9
1.6
1.6
100.0
100.0
52.5
ConGress 73
34.1
3.1
4.5
0.0
0.0
0.0
DiGress 73
1.6
1.5
1.7
100.0
100.0
67.5
DISCO-MPNN
1.8402
0.8
2.7+0.4
100.0
100.0
41.9+22
DISCO-GT
0.8++02
0.8
2.0+0.5
100.0=
100.0=
66.2
GraphRNN 82
24.5
9.0
2508.0
100.0
100.0
0.0
GRAN 42
3.5
1.4
85.0
2.5
97.5
GG-GAN 37
315.0
8.3
2062.6
100.0
100.0
0.0
MolGAN
9
4.5
10.2
2346.0
25.0
100.0
0.0
Planar
SPECTRE [1
2.5
2.5
2.4
100.0
100.0
25.0
ConGress 73
23.8
8.8
2590.0
0.0
0.0
0.0
DiGress 77
1,4
1.2
1.7
100.0
100.0
85.0
DIsCo-MPNN
1.4+0033
1.4=0.4
6.441.6
100.0
100.0::0.0
33.8+2.7
DIsCO-GT
1.2+
1.3=0.5
1.7+
100.0
100.0:
83.6#2.1
Table 2: Performance (td% on QM9 dataset. V., U., and N. mean Valid, Unique, and Novel.
Model
Valid f
V.U. t
V.U.N.
CharacterVAE
20
10.3
7.0
6.3
Grammar VAE 38
60.2
5.6
4.5
Graph VAE
66
55.7
42.0
26.1
GT-VAE 55
74.6
16.8
15.8
Se12GraphVAE
722
59.9
56.2
GG-GAN 37
51.2
24.4
24.4
MolGAN
98.1
10.2
9.6
SPECTRE [51
87.3
31.2
29.1
GraphNVP (50
83.1
82.4
GDSS 32
95.7
94.3
EDGE 110
99.1
99.1
ConGress 73
98.9
95.7
38.3
DiGress 73
99.0
95.2
31.8
GRAPHARM [36
90.3
86.3
DISCO-MPNN
98.9=0.7
98.7+05
68.7.00.
DISCO-GT
99.3
98.9
56.2.0.
DISCO-GT can obtain competitive performance against the SOTA, DiGress, which is reasonable because both models share the graph Transformer backbone. Note that DiGress's 's performance in terms of Validity is not the statistics reported in the paper but from their latest model checkpoint fact, we found it very hard for DiGress and DisCo-GT learn to generate valid SBM/Planar graphs. These two datasets have only 200 graphs, but sometimes only after > 10, 000 epochs training, the Validity percentage can be > 50%. Additionally, DISCo-GT provides extra flexibility during sampling by adjusting the т. This is important: sampling efficiency and quality even after the model trained and frozen.
models can still trade-off between the
In general, DISCO-MPNN has competitive performance against DISCO-GT in terms of Deg., Clus., and Orb. However, its performance worse compared to DISCO-GT in terms of Validity, which might be related to the different model expressiveness. Studying the graph-to-get tot-too--ppphh model expressiveness would be an interesting future direction, e.g., generating valid Planar graphs.

---

Table 3: Performance on MOSES. VAE, JT-VAE, and GraphINVENT have hard-coded rules to ensure high validity.
Model
Valid
Unique t
Novel f
Filters
FCD
SNN 1
Scaf 1
VAE 121
97.7
98.8
69.5
99.7
0.57
0.58
5.9
JT-VAE 29
100.0
100.0
99.9
97.8
1.00
0.53
10.0
GraphINVENT 53
96.4
99.8
N/A
95.0
1.22
0.54
12.7
ConGress 73
83.4
99.9
96.4
94.8
1.48
0.50
16.4
DiGress 73
85.7
100.0
95.0
97.1
1.19
0.52
14.8
DISCO-MPNN
83.9
100.0
98.8
87.3
1.63
0.48
13.5
DISCO-GT
88.3
100.0
97.7
95.6
1.44
0.50
15.1
Table 4: Performance on GuacaMol. LSTM, NAGVAE, and MCTS are tailored for molecule datasets; ConGress, DiGress, and DISCO are general graph generation models.
Model
Valid f
Unique f
Novel f
KL div t
FCD t
LSTM
64
95.9
100.0
91.2
99.1
91.3
NAGVAE 40
92.9
95.5
100.0
38.4
0.9
MCTS 28
100.0
100.0
95.4
82.2
1.5
ConGress 73
0.1
100.0
100.0
36.1
0.0
DiGress 7
85.2
100.0
99.9
92.9
68.0
DiSCO-MPNN
68.7
100.0
96.4
77.0
36.4
DISCO-GT
86.6
100.0
99.9
92.6
59.7
4.2 Molecule Graph Generation
Dataset and metrics. The datasets QM9 662. MOSES [58], and GuacaMol [6 are chosen. For MOSES, metrics including Uniquess, Novelty, Validity, Filter, FCD, SNN, and Scaf reported in Table For QM9, metrics include Uniqueness, Novelty, and Validity. For GuacaMol, metrics include Valid, Unique, Novel, KL div, and FCD. Details about the datasets, metrics, and baseline methods are in Appendix F.2.3
Results. Table shows the performance on QM9 dataset. Our observation is consistent with the per- formance comparison on plain datasets: (1) DisCo-GT obtains slightly better or at least competitive performance against DiGress due to the shared traph-to-graph backbone, but our framework offers extra ficxibility in the sampling process; (2) DIsCO-MPNN obtains decent performance terms of Validity, Uniqueness, and Novelty comparing with DISCO-GT.
Tables and 4 show the performance on MOSES and GuacaMol which further verifies that (1) performance of DISCO-GT is on par with the SOTA general graph generative models, DiGress and (2) DISCO-MPNN has decent performance, but worse than DisCo-GT and DiGress.
4.3
Efficiency Study
A major computation bottleneck the graph-to-graph backbone p which is GT MPNN. We compare the number of parameters, the forward and back- propagation time of GT and MPNN in Table 5 For a fair comparison, we all the hidden dimensions of GT and MPNN as 256 and the number of layers as 5. use the Community batch size 64. Table shows that GT has larger capacity and more parameters at the expense of more expensive training.
Table 5: Efficiency comparison in terms of
number of parameters, forward and backprop- agation time (second/iteration)
GT
MPNN
Parameters x 106
106
S2 dataset and set the
Forward
0.065
0.022
Backprop. 0.034
0.018

---

4.4 Ablation Study
An ablation study on DisCo-GT for reference distributions (marginal vs. uniform), and sampling steps (1 to 500) is presented in Table [ The number of sampling steps is round( if T = 1. QM9 dataset chosen. similar ablation study on DISCO-MPNN is in Table p in Appendix. We observe that first, gen- erally, the fewer sampling steps, the lower the generation quality. In some cases (e.g., the marginal distribution) with the sampling steps decreasing significantly (e.g., from 500 to 30),
Table 6: Ablation study (dda with GT backbone. V., U., and N. mean Valid, Unique, and Novel.
Ref. Dist.
Steps
Valid f
V.U. 1
V.U.N. f
500
99.3
98.9106
56.2.10.4
100
98.7100
98.5+04
58.810.4
30
97.91112
97.611.1
59.2
Marginal
10
95.3+119
9..8+1.6
62.1
5
93.0
1.
64.9
1
76.142.
1.
62.9
500
94.1109
92.910.5
56.610.4
100
91.5111
90.3109
54.411.
30
88.7+116
86.9+1.0
58.6+2.1
Uniform
10
84.5+2.
80.4
59.8+18
the performance degradation is still very slight, implying our method's high robustness in sampling steps. Second, the marginal reference dis- tribution is better than the uniform distribution, consistent with the observation from DiGress 73
5
77.0
69.9
13.5
1
44.9
35.1+34
29.6:2255
Related Work
Diffusion models 80 can be interpreted from both the score- motthina 66 70 or the variational
autoencoder perspective 23
35
34 Pioneering efforts on diffusion generative modeling study the
process in continuous-state 67 23 68 whose typical reference distribution Gaussian. Beyond that,
some efforts propose discrete- state models [24] to E.g., D3PM (2) designs the discrete diffusion
process by multiplication of transition matrices; T-LDR (8] generalizes D3PM by formulating continuous-time Markov chain; (71) proposes singleton conditional distribution-based objective
for the continuous- time Markov chain-based model whose rationale is Brook's Lemma [5] 49].
Diffusion models are widely used in graph generation tasks
86
15
83 14
61
74
79 78 59 such as molecule design 65
Pioneering works such as EDP-GNN [66]
and GDSS B2 diffuse graph data in continuous state space [26]. DiscDDPM [22 is an early
effort to modify the DDPM architecture into discrete state. In addition, DiGress 73 also
one-shot discrete-state diffusion model, followed by a very recent work MCD 46 both in the
discrete-time setting. Beyond the above-mentioned efforts, DruM (31 proposes to mix the diffusion
process. EDGE [10] proposes interesting process: diffusing graphs into empty graphs. Besides, GRAPHARM (36] proposes an autoregressive graph diffusion model, and [45) applics the diffusion models for molecule property prediction tasks. In addition to the above-mentionel general graph diffusion models, there are many other task-tailored graph diffusion generative models [48, (0] 41 60
77 4 75), which incorporate more in-depth domain expertise into the model design. Interested
readers are referred to this survey [44
Conclusion
This paper introduces the first discrete-state continuous-time graph diffusion generative model, DISCO. Our model effectively marries continuous-time Markov Chain formulation with the discrete nature of graph data, addressing the fundamental sampling limitation of prior models. DisCO's training objective is concise with solid theoretical foundation. We also propose simplified message-passing architecture serve as the graph-to-gen torphph-grrph-oo backbone, which theoretically has desirable properties against permutation of node ordering and empirically demonstrates decent performance against existing graph generative models in tests on various datasets.
10

---

Acknowledgments and Disclosure of Funding
ZX, RQ. 77., and HT are partially supported by NSF (2324770). The content of the information in this document does not necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.
References
[1] David F Anderson. modified next reaction method for simulating chemical systems with time dependent propensities and delays. The Journal of chemical physics, 127(21), 2007.
[2] Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den Berg. Structured denoising diffusion models in discrete spate-spaces. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Perey Liang. and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 2021, virtual, pages 17981-17993, 2021.
[3] Yikun Ban, Yunzhe Qi. and Jingrui He. Neural contextual bandits for personalized recommen- dation. In Tat-Seng Chua, Chong- Wah Ngo, Roy Ka-Wei Lee, Ravi Kumar, and Hady W. Lauw, editors, Companion Proceedings of the ACM on Web Conference 2024, WWW 2024, Singapore, Singapore, May 13-17, 2024, pages 1246-1249. ACM, 2024.
[4] Fan Bao, Min Zhao, Zhongkai Hao, Peiyao Li, Chongxuan Li, and Jun Zhu. Equivariant energy-guided sde for inverse molecular design. In The eleventh international conference on learning representations, 2023.
[5] D Brook. On the distinction between the conditional probability and the joint probability approaches in the specification of nearest-neighbour systems. Biometrika, 51(3/4):481-455 1964.
[6] Nathan Brown, Marco Fiscato, Marwin H. S. Segler, and Alain C. Vaucher. Guacamol: Bench- marking models for de novo molecular design. J. Chem. Inf. Model., 196)):096--11088,, 2019.
[7] Chen Cai, Truong Son Hy. Rose Yu, and Yusu Wang. On the connection between MPNN and graph transformer. Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 3408 3430. PMLR, 2023.
[8] Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. continuous time framework for discrete denoising models. In NeurIPS, 2022.
[9] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. CoRR, 11V/8805.1197 2018.
[10] Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. In Proceedings of the 40th International Conference on Machine Learning, pages 4585-4611 2023.
[11] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[12] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Lio, and Petar Velickovic. Principal neighbourhood aggregation for graph nets. Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrlPS 2020, December 6- 12, 2020, virtual, 2020.

---

[13] Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey, SIGKDD Explor. 24(2):61-77, 2022.
[14] Dongqi Fu and Jingrui He. Natural and artificial dynamics in graphs: Concept, progress, and future. Frontiers Big Data, 5, 2022.
[15] Dongqi Fu, Zhe Xu, Hanghang Tong, and Jingrui He. Natural and artificial dynamics in gnns: A tutorial. In Tat-Seng Chua, Hady W. Lauw, Luo Si, Evimaria Terzi, and Panayiotis Tsaparas, editors, Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, WSDM 2023, Singapore, 27 February 2023 3 March 2023, pages 1252-1255. ACM, 2023.
[16] Daniel T Gillespie. A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. Journal of computational physics, 22(4))403 434, 1976.
[17] Daniel T Gillespie. Exact stochastic simulation of coupled chemical reactions. The journal of physical chemistry, (25):23340 2361, 1977.
[18] Daniel T Gillespie. Approximate accelerated stochastic simulation of chemically reacting systems. The Journal of chemical physics, 115(4):116-1133, 2001.
[19] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 1 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272. PMLR, 2017.
[20] Rafael Gómez-Boue Bombareeli, David Duvenaud, José Miguel Hernández-Lobato. Jorge Aguilera- Iparraguire, Timothy D. Hirzel, Ryan P. Adams, and Alán Sapuru-Guzia Automatic chemical design using a data-driven continuous representation of molecules. CoRR, abs/1610.02415, 2016.
[21] Rafael Gómez-Bombarelli Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato Benjamín Sánchez-Longeling, Dennis Sheberla, Jorge aguilera-Iparragune Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven continuous representation of molccules. ACS central science, 4(2):268-22 276, 2018.
[22] Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. CoRR, abs/2210.01549 2022.
[23] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tiee Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[24] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. In Marc' Aurelio Ran- zato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-1 2021, virtual, pages 12465, 2021.
[25] Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3d. In Kamalika Chaudhuri. Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 8867-8887. PMLR, 2022.
[26] Han Huang, Leilei Sun, Bowen Du, Yanjie Fu, and Weifeng Lv. Graphgdp: Generative diffusion processes for permutation invariant graph generation. In Xingquan Zhu, Sanjay Ranka, My Thai, Takashi Washio, and Xindong Wu, editors, IEEE International Conference on Data Mining, ICDM 2022, Orlando, FL, USA, November 28 Dec. 1, 2022, pages 201-210. IEEE, 2022.
12

---

[27] Lei Huang, Hengtong Zhang, Tingyang Xu, and Ka-Chun Wong. MDM: molecular diffusion model for 3d molecule generation. In Brian Williams, Yiling Chen. and Jennifer Neville, editors, Thirty-Seventi AAAI Conference on Artificial Intelligece, AAAI 2023, Thirty-Fijil Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 5105-5112, AAAI Press, 2023.
[28] Jan H Jensen. A graph-based genetic algorithm and generative model/monte carlo tree search for the exploration of chemical space. Chemical science, 10(12):356733522 2019.
[29] Wengong Jin, Regina Barzilay, and Tommi S. Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 2328 2337. PMLR, 2018.
[30] Bowen Jing, Gabriele Corso, Jeffrey Chang, Regina Barzilay, and Tommi S. Jaakkola. Torsional diffusion for molecular conformer generation. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
[31] Jaehyeong Jo, Dongki Kim, and Sung Ju Hwang. Graph generation with destination-predictin diffusion mixture. OpenReview, 2023.
[32] Jachyeong Jo. Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning. ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 10362-10388 10383. PMLR, 2022.
[33] Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
[34] Diederik P. Kingma and Ruiqi Gao. Understanding diffusion objectives the ELBO with simple data augmentation. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information P Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10- 16, 2023, 2023.
[35] Diederik P. Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. CORR, 02s/22177.06300 2021.
[36] Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang, Autoregressive diffusion model for graph generation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning. ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, PMLR, 2023.
volume 202 of Proceedings of Machine Learning Research, pages
[37] Igor Krawczuk, Pedro Abranches, Andreas Loukas, and Volkan Cevher. Gg-gan: A geometric graph generative adversarial network, 2021. In URL hups://openreview: net/forum, 2020.
[38] Matt J. Kusner and José Miguel Hermández-Lobato. GANS for sequences of discrete elements with the gunbel-softmax distribution. CoRR, abs/1611.0000 2016.
[39] Youngchun Kwon, Dongseon Lee, Youn-Suk Choi, Kyoham Shin, and Seokho Kang. Com- pressed graph representation for scalable molecular graph generation. J. Cheminformatics, 12(1):58, 2020.
13

---

[40] Youngchun Kwon, Dongseon Lee, Youn-Sute Soun-Suk Choi, Kyoham Shin, and Seokho Kang, Com- pressed graph representation for scalable molecular graph generation. Journal of Cheminfor maticy, 12:1-8, 2020.
[41] Seul Lee, Jachyeong Jo, and Sung Ju Hwang. Exploring chemical space with score-based out-of-distribttion generation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 18872-18892, PMLR, 2023.
[42] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 4257-4267, 2019.
[43] Haitao Lin, Yufei Huang, Meng Liu, Xuanjing Li, Shuiwang Ji, and Stan Z. Li. Diffbp: Generative diffusion of 3d molecules for target protein binding. CoRR, abs/2211.11211 2022.
[44] Chengyi Liu, Wenqi Fan, Yunqing Liu, Jiatong Li, Hang Li, Hui Liu, Jiliang Tang, and Qing Li. Generative diffusion models on graphs: Methods and applications. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 6702-6711. ijcai.org, 2023.
[45] Gang Liu, Eric Inae, Tong Zhao, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Data-centric learning from unlabeled graphs with diffusion model. Advances in neural information processing systems, 36, 2023.
[46] Gang Liu, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Inverse molecular design with multi- conditional diffusion guidance. arXiv preprint arXiv:2401.33856 2024.
[47] Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. Class-imbalanced graph learning without class rebalancing. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
[48] Shitong Luo, Chence Shi, Minkai Xu, and Jian Tang. Predicting molecular conformation via dynamic graph score matching. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 19784-19795, 2021.
[49] Siwei Lyu, Interpretation and generalization of score matching. In Jeff A. Bilmes and Andrew Ng, editors, UAI 2009, Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, Montreal, QC, Canada, June 18-21, 2009, pages 359-366. AUAI Press, 2009.
[50] Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnvp: An invertible flow model for generating molecular graphs. CoRR, abss/1905.1 16000, 2019.
[51] Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. SPECTRE: spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 15159-15179. PMLR, 2022.
[52] Rocío Mercado, Tobias Rastemo, Edvard Lindelöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Esben Jannik Bjerrum. Graph networks for molecular design. Mach. Learn. Sci. Technol., 2(2):25023, 2021.
[53] Rocío Mercado, Tobias Rastemo, Edvard Lindelöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Eshen Jannik Bjerrum. Graph networks for molecular design. Machine Learning: Science and Technology, 2(2)3025023, 2021.
14

---

[54] Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective. CoRR, abs/2202.08455. 2022.
[55] Joshua Mitton, Hans M. Senn, Klaas Wynne, and Roderick Murray-Smith. A graph VAE and graph transformer approach to generating molecular graphs. CoRR, 0als/2104.04345, 2021.
[56] Chenhao Niu, Yang Song, Jiaming Song. Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 Augusi 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 4474 4484. PMLR, 2020.
[57] Ethan Perez, Florian Strub, Harm de Vries, Vincent Dumoulin, and Aaron C. Courville. Film: Visual reasoning with general conditioning layer. In Sheila A. Mcllraith and Kilian Q. Wein- berger, editors, Proceedings of the Thirty-Secona AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3942-3951. AAAI Press, 2018
[58]
Daniil Polykovskiy, Alexander Zhebrak, Benjamín Sánchez-Lengeling Sergey Golovanov, Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, Artur Kadurin, Sergey I. Nikolenko, Alán Aspuru- and Alex Zhavoronkov. Molecular sets (MOSES): A benchmarking platform for molecular generation models. CoRR, abs/1811. 2018.
[59] Yunzhe Qi, Yikun Ban, and Jingrui He. Graph neural bandits. In Ambuj K. Singh, Yizhou Sun, Leman Akoglu, Dimitrios Gunopulos. Xifeng Yan, Ravi Kumar, Fatma Ozcan, and Jieping Ye, editors, Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pages 1920-1931. ACM, 2023.
[60] Zhuoran Qiao, Weili Nie, Arash Vahdat, Thomas F. Miller III, and Anima Anandkumar. Dynamic-backbone protein-ligand structure prediction with multiscale generative diffusion models. CoRR, abs/2209. 15171, 2022.
[61] Ruizhong Qiu, Dingsu Wang, Lei Ying. H. Vincent Poor, Yifang Zhang, and Hanghang Tong. Reconstructing graph diffusion history from a single snapshot. In Ambuj K. Singh, Yizhou Sun, Leman Akoglu, Dimitrios Gunopulos, Xifeng Yan, Ravi Kumar, Fatma Ozcan, and Jieping Ye, editors, Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach. CA. USA, August 6-10, 2023, pages 1978-1988. ACM, 2023.
[62] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):177 2014.
[63] Sidney I Resnick. Adventures in stochastic processes. Springer Science & Business Media, 1992.
[64] Marwin HS Segler, Thierry Kogej. Christian Tyrchan, and Mark P Waller. Generating focused molecule libraries for drug discovery with recurrent neural networks. ACS central science, 10031120-33,, 2018
[65] Chence Shi, Shitong Luo, Minkai Xu, and Jian Tang. Learning gradient fields for molecular conformation generation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9558-95588888 00188955...8 PMLR, 2021.
[66] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Vera Kurková, Yannis Manolopoulos, Barbara Hammer, Lazaros S. Iliadis, and Ilias Maglogiannis, editors, Artificial Neural Networks and Machine Learning- ICANN 2018 27th International Conference Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I, volume 11 139 of Lecture Notes Computer Science, pages 412-422. Springer, 2018.
15

---

[67] Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference Machine Learning, ICML. 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 2265. JMLR.org.. 2015.
[68] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[69] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1895-11907, 2019.
[70] Yang Song, Jascha bih--Dickttein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May
3-7, 2021. OpenReview.net, 2021.
[71] Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous-time discrete diffusion models. In The Eleventh International Conference on Learning Representa- lions, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[72] Clément Vignac and Pascal Frossard. Top-n: Equivariant set and graph generation without exchangeability. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[73] Clément Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh Interna- rional Conference Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[74] Dingsu Wang, Yuchen Yan, Ruizhong Qiu, Yada Zhu, Kaiyu Guan, Andrew Margenot, and Hanghang Tong. Networked time series imputation via position-aware graph enhanced varia- tional autoencoders. In Ambuj K. Singh, Yizhou Sun, Leman Akoglu, Dimitrios Gunopulos, Xifeng Yan, Ravi Kumar, Fatma Ozcan, and Jieping Ye, editors, Proceedings the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10, 2023, pages
ACM, 2023.
[75] Tomer Weiss, Eduardo Mayo Yanes, Sabyasachi Chakraborty, Luca Cosmo, Alex M Bron- stein, and Renana Computational Science, 3(10):873 882, 2023.
Guided diffusion for inverse molecular design. Nature
[76] Minkai Xu, Alexander S Powers, Ron O Dror, Stefano Ermon, and Jure Leskovec. Geometric latent diffusion models for 3d molecule generation. In International Conference on Machine Learning, pages 38592-38610 PMLR, 2023.
[77] Minkai Xu, Lantao Yu, Yang Song, Chence Shi, Stefano Ermon, and Jian Tang. Geodiff: geometric diffusion model for molecular conformation generation. In The Tenth Interna- tional Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[78] Zhe Xu, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, Hao Yang, and Hanghang Tong. Kernel ridge regression-based graph dataset distillation. In Ambuj K. Singh, Yizhou Sun, Leman Akoglu, Dimitrios Gunopulos, Xifeng Yan, Ravi Kumar, Fatma Ozcan, and Jieping Ye, editors, Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023, Long Beach, CA, USA, August 6-10 10, 2023, pages ACM, 2023.
16

---

[79] Zhe Xu, Boxin Du, and Hanghang Tong. Graph sanitation with application to node classification. In Frédérique Laforest, Raphaël Troncy, Elena Simperl, Deepak Agarwal, Aristides Gionis. Ivan Herman, and Lionel Médini, editors, WWW '2: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pages 136-1147. ACM, 2022.
[80] Ling Yang, Zhilong Zhang, Yang Song, Shenda Hong, Runsheng Xu, Yue Zhao, Yingxia Shao, Wentao Zhang, Ming-Hsure Hsuan Yang, and Bin Cui. Diffusion models: A comprehensive survey of methods and applications. CoRR, hbss/209.00796. 2022.
[81]
Jiaxuan You, Jonathan Michael Gomes Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Thirty-Fifih AAAI Conference Artificial Intelligence, AAAI 2021, Thirly-Third Conference on Innovative Applications of Artificial Intelligence, TAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 202 I, Virtual Event, February 2-9, 2021, pages 10737-10745, AAAI Press, 2021.
[82] Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrmn: Generating realistic graphs with deep auto-regressive models. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Machine Learning, ICML 2018, Stockholmsmüssaan Stockholm, Sweden, July 10, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5694-57033 PMLR, 2018.
[83] Zhichen Zeng, Ruizhong Qiu, Zhe Xu, Zhining Liu, Yuchen Yan, Tianxin Wei, Lei Ying, Jingrui He, and Hanghang Tong. Graph mixup on approximate Forty-first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 21 21-27, 2024. OpenReview.net, 2024.
geodesics. In
[84] Lecheng Zheng, Dawei Zhou, Hanghang Tong, Jiejun Xu, Yada Zhu, and Jingrui He. Fairgen: Towards fair graph generation. In 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands, May 13-16. 2024, pages 2285-2297. IEEE, 2024.
[85] Dawei Zhou, Lecheng Zheng, Jiawei Han, and Jingrui He. A data-driven graph generative model for temporal interaction networks. Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash, editors, KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pages 401-411. ACM, 2020.
[86] Dawei Zhou, Lecheng Zheng. Jiejun Xu, and Jingrui He. Misc-gan: A multi-scan generative model for graphs Frontiers Big Data, 2:3, 2019.
17

---

Appendix
The organization of this appendix as follows
Section
A
the derivation of the factorized rate matrices.
Section
the forward transition probability matrix given a rate matrix.
Section
C
all the proofs.
Section
C.1
proof of Proposition 3.2
Section
proof of Theorem
Section
proof of Lemma 3.5
Section
proof of Lemma 3.6
Section
proof Lemma 3.7
Section
C.6
proof of Theorem 3.8
Section
proof Theorem 3.9
Section
D
step-by-step sampling algorithm.
Section
the auxiliary features and neural modules used by DisCo.
Section
detailed experimental settings and additional experimental results.
Section FI
hardware and software
Section dataset setup
Section hyperparameter settings
Section
additional effectiveness evaluation on Community Dataset
Section
additional ablation study with the MPNN backbone
Section convergence study
Section visualization
Section this paper's limitations and future work.
Section H the broad impact of this paper.
A Details of the Factorization of Rate Matrices
In this section, we detail the derivation of Remark 3.1 which is extended from the following Proposition 3 of [8) Proposition A.1 (Factorization of the rate matrix, Proposition from 8 If the forward process
factorizes qr, (x:(x.) I[ 9 ( (xf then the forward and reverse rates are of the
form
Rx Σ R (xd (8)88 ax
(9)
d=1
at o o=
Rx(x, = Σ R (zd
)0 xe Σ Cope (2g)x)
(10)
(x (20)
zd
where xx) 1 when all dimensions except for d are equal.
As all the nodes and edges are categorical, applying the above proposition of the nodes and edges leads to our Remark 3.1
B Details of Forward Transition Probability
In this section, we present derivation of forward transition probability for nodes; the forward process for edges can be derived similarly. Note that this derivation has been mentioned in [8] for generic discrete cases; we graft the graph settings and include it here for completeness. The core derivation of the forward transition probability is to prove the following proposition.
18

---

Proposition B.1 (Analytical forward process for commutable rate matrices, Proposition 10 from ( ) if RR, and Ry commute Vt, t', (2 2|æ (eló R,,s)),,
Proof. If 9rjo = exp
R,ds is the forward transition probability matrix, should satisfy the Kolmogorov forward equation de Z0jo
Ocjo
R.s.
The transition probability matrix
00
48jo
Redo)
(11)
Ar!
k=0
and, based on the fact that R2 and R2 commute Vt, t',, its derivative
00
(k - 1)1 (% R,ds) (R.ddds)
1
(k-1)
9:jo
Σ
(12)
Thus, 4:jo = exp (Jo R,,s is the solution of Kolmogorov forward equation.
For the node i, if its forward rate matrix is set as R; = R,, we have R2 and RS commute, vI, l' Thus, the transition probability for node is q olʃ u) (edo d()) Jun. Based
on similar derivation, have the transition probability for the edge (i.j) as qujlec (a.) olcp u) (elo R, Jn.
(15)
C Proofs
C.1 Proof of Proposition 3.2
Proposition 3.2 claims the forward process converges to uniform distributions if R, 11 bI and R. = 11 (a + I)I and converges to marginal distributions my and m. if R, 1m/ - and
R. 1m - I.
Proof. If we formulate the rate matrices for nodes and edges as R, (t.)
R.((.)
R(t) Vi.j and R
Rt Vi, every rate matrix is commutable for any time steps and t'. In the following content,
show the proof for the node rate matrix R R( y; the converged distribution of edge can be
proved similarly. Based on Proposition B.
the transition probability matrix between time steps t
and + At is
r+A
1+AH I+
((s) O((A)))
(13)
I+ AOS(E)R +
(14)
where (*) based on the Mean Value Theorem. If the high-order term O((At))) omitted and we short BA.- At, for R, 11T bI, we have
l+ = 11 II,
(15)
which is the transition matrix of the uniform diffusion in the discrete-time diffusion models [67 Thus, with T + do and dt to the power of infinite, the converged distribution is a uniform distribution. Similarly, for R, 1m; the transition matrix is
2
C+aa s 3a:1m, + (1-11a0 3Ar)
(16)
which is a generalized transition matrix of the 'absorbing state' diffusion 2 The difference lies at for the "absorbing state' diffusion 22 my is set as one-hot vector for the absorbing state, and here we set the marginal distribution. Thus, with T - oo and (ttA to the power of infinite, the converged distribution is marginal distribution m,..
D
19

---

C.2 Proof of Theorem 3.3
Theorem 3.3 says for + g,
C. + Czode TeodeEE 9e (9 (0) R, 9) - (9, 9)
Σ Ces (One- fo)
Eg. (91 Σ Les Hone-Hoot (1:1),, c!i
(17)
where the node and edge estimated probability vector (sum is 1) is notated as fo (P
Il..).... pb (f = Tl e [0, 1] and af"h²) = (e(is) = 1|9,), pb (elis) = a +
[[.))] E [0, 1jatt.
Proof.
RG 9) Rs (9,
(18)
21 ((f)))
Σ A
(f0l) - ((ll))
2loo (f*)
fg
B
(
@ejo(e(10)100 (11)) (10))(e) (0) - (e)((e0=))))))
(19)
1,
Σ
4
2njo
(F)))))
(90 (fll)) - poje (f
B
(
o: (e (1.))) [20
(8.5) (50 (0
(1.5) (9)
(20)
We check the first term of Eq.
20
( f8)
Σ
A
(fole( - -(
(21)
o0 (((
fb
A sup
goje (5ll) Crlls)
(22)
q: (f
fb
Σ C Σ
Uoje (Gdl)) -g..
(23)
Σ
C.
Σ
(Cra Z () log P6 (f619)
(24)
f8
(w0)
Σ Σ
(Crs a log (f
(25)
f8
=0
C2
Σ
Goje log log
(26)
fb
(15)) (11)( f Cj ( log 90 (f(l))) (*) is based on the Pinsker's
where C A sup
inequality, (**) is based on Cauchy-Schware inequality: Σ Voi S Ei. C =
V2nsup, (C.). C2 E.E, C3.- Next, the term - E.E, Zo (56lg) (681) is equiva-
20

---

lent to:
ΣE
(o log log (oll))
(27)
f0
Σ
Po Po.c log (111
(28)
Pr(G)
fö
1
ΣΣ
Σ
(29)
Pt(
fà Soll))
1
ΣΣ
E
Tatta (0)) 74
(30)
(((
f8 Gollg)
ΣE
Σ
Tanra
(31)
(c())
fo So(
Σ
datta (90)9))(919.)) Σ
Cas
(32)
(9)
Go
4Ho Σ (ot
(33)
Po (g)
where Eee(h)) marginalizing all the graphs time whose i-th node is fo: po.c the joint
probability of a graph whose i-th node is fg at time 0 and it is G time I; Po.: 9) is the joint probability of graph which is Go at time and is G at time Plugging Eq. (33) into Eq. (26):
(f
Σ
A
(20) (5(l)) (()1((
2: (f*
fa
Co + CrLE,. (9
Σ Lox (Dne-Hoo(((f)
(34)
where Cs
p:( A similar analysis can be conducted about the second term of Eq. 20 and
directly present it here:
(00(66)01e)))) (1.1))
Σ
B
(1())))))))))) p((((((2))1)))
<Cs
C. + CgE (
Σ
Laz (one- (t))) e(
(35)
where C3
/2n (rihh
C4
Ens Eggo Caan
Oij
B(hr))
(1:5) (1)) log e g).
sup (..))
(a))
Plugging Eqs.
34 and
35
into Eq.
20 being aware that C1. C2, Cz. C4. Os are all l-related:
(9, (G,
< C
C2 +
Σ
Lae (o=(One-Hot
+ Ca
ca, + ColEo.
Σ
(a( (i.) elt:))
(36)
(G Coode (9009999
Σ
Len (on
(one e(1.))) 1/2
+ C C
C
Σ
(37)
i
21

---

where (*) is based on Cauchy-Schwarrd Schwarz inequality, C. = 20902 + 20 C, 2090s. Cr C-
L
C.3 Proof of Lemma 3.5
We clarify that the term "permutation" in this paper refers to the reordering of the node indices, i.e., the first dimension of F and the first two dimensions of E.
Proof. The input of an MPNN layer is F {ri)i= E Rand E (rag) E Ruxund, y E Rd, where d the hidden dimension. The updating formulas an MPNN layer can be presented as
(
- r
)
r' + FiLM
FiLM
r', MLP
..
(38)
n
(bd) + FiLM FiLM(FiLM(( (53), Or)) y)),
(39)
y PNA (E=) + PNA (NA((r( (1(t)) ((
(40)
The permutation p of the input of an MPNN layer can be presented as P(F [r;]]=1 E
(re. (.g.) = (00 R)= where o {l....... n + (1....,m is bijec- tion.
For PNA (Eq. (70).. it includes operations max, min, mean, and std which are all permutation-invariant and thus, the PNA module is permutation-invariant Then,
y + PNA (I') )i=1) + PNA (fr (1-)
((x())) (1)(()))),))))) y PNA ((r (1)a }:=1) + PNA (10) ([ (41)
Because Σラ=
(0,) = (((()))())) Or (()) 3 (J), and the FiLM module (Eq.
is not related to the node ordering,
((((0))(1))) ( r c r FiLM (FLM(())(( or)),)
(42)
Ej ((o7 y
(1) <- FiLM
FiLM
(1) MLP
(43)
Σj= ((1)))
) .y
FiLM
FILM
F',
(44)
Thus, we proved that
MPNN (P(F.E.v))
-PM.)))))MMMM(((() E.y)
(45)
C.4 Proof of Lemma 3.6
Proof. The forward rate matrix (Eq. (3) is the sum of component-specific forward rate matrices ([R( (15)) J.jen and [Ri)ent ). is permutation invariant because the summation is permutation -initttiiiiinnnniaan
Zn
invariant.
The parametric reverse rate matrix
Ro = Σ R. + Σ
R (c(0)) (0-1))
(46)
where
R (F
A Σ f woll Pop ( 9t).
(f
R (eli)) a(:J))
B(b-)) E.g.o. (1)) wolelss21 Pole (0)
(1-5) G.).
If we present the permutation P on every node
22

---

as a bijection σ {1, (m....,,. + {l..... n). the term
q (f' (8o)
R2 (f)))))))))))) A Σ
o ( (1)) Poje (fale.)
(47)
fb
= = of yoor Σ Aoo(f f()
( Poje (f61g.
(48)
4 o (f (5
R₁ ( (Fo(tt) f
5o a a (fo(0) Poje (Jlls.)
(49)
A fo
(*x) ((((()))))) (
0
(1 (P(G))
5 2 20 (000000)))))) Pale
(50)
( R2g
(51)
where (+) is based on the permutation invariant of the forward process and its rate matrix; (**) is based on the permutation equivariance of the graph-to-graphi backbone pprr-
C.5 Proof of Lemma 3.7
Recall the Kolmogorov forward equation, for < t.
d
(x1)((xx/xx) (x,)
Σ (1, SEN
(52)
dt
Proof. We aim to show that 2t/s (P(xx))((xx.) is solution of Eq. 52 Because the permutation P bijection, have
(53)
di
= Σ 2/ (PP)
(54)
EEX
4tj= (P))
(55)
EEX
where (*) is because R₁ is cormutation-invarinn As Eq. 55 and Eq. 52 share the same rate matrix, and the rate matrix completely determines the CTMC (and its Kolmogorov forward equation) (63
thus, their solutions are the same: 4/ (x, (x,)x,) 2qja (P.,))) i.e., the transition probability is permutation- innaaiiant.....
C.6 Proof of Theorem 3.8
Proof. We start from simple where the parametric rate matrix is fixed all the time,
Pg(Go) = Σ
20pz (e (Gr),
(56)
Gr
where the transition probability is by solving the Kolmogorov forward equation
d
dt (9.99.)
Σ
(R..)))))
(57)
23

---

Thus, the sampling probability of permuted graph P(Go)
(P(C))) = Σ (PPo (P(GT))
(58)
Gr
(
(9 (
(59)
Gr
(*+)
(9)
(60)
9r
(Go)
(61)
where (*) is based on Lemma and Lemma 3.7 the transition probability of DisCo is permutation- invariant and (**) is from the assumption that the reference distribution (Tr) is permutation- invariant. Thus, we proved that for the simple case, Rg, fixed Vt, the sampling probability is intuutatiioninvariann
For the practical sampling, as we mentioned in Section 3.4 the r-leaping algorithm assumes that the time interval [0, T) is divided into various length-7 intervals [0, r): (T.:.).... -, (here both close sets open sets work) and assume the reverse rate matrix is fixed as Rø,; within every length-r interval, such as (t - T, t.. Thus, the sampling probability can be computed as
(9))
Σ
40 ... (9-
(62)
Gr.GT -..
The conclusion from the simple case can be generalized to this r-leaping based case because all the transition probability (t-r)((9--199) and the reference distribution are permutation-invariann O
Note that Xu et al. 77 have similar analysis in their Proposition on DDPM-basee model.
C.7 Proof of Theorem 3.9
Recall our training objective is
min't TE Eg. E
+ Σ Lae (O))
Σ 1
Les (ote (1.1)) c(620))
9
(63)
where fi = P = 1(9)) ..j. ( = b[g.)) E [0, 1 and a(hd) = (elis)
1 (l.)...... pb (clti)) aa+ 1[9))) E [0,
Proof. We follow the notation and present the permutation P every node bijection [I....,n] + {I....,,7) n). We first analyze the cross-entropy loss on the nodes for a single training graph Go and taking expectation Eg, keeps the permutation invariance:
Laode (Go) = TEiuu4,, Eayo(GG (Go) Σ (o
(64)
TE
(G Σ Hot (ot(f))e---o..f)
(65)
G1
TEm-Ha
(P(()) Σ (One
(66)
Gr
(xx)
TE
(P(()))))))G) Σ (One- fo()))
(67)
Laode (P(Go))
(68)
where (*) from the permutation invariance of the forward process and (*+) from the permutation cquivariance of the graph-to-graph backbone and the permutation invariance of the cross-entropy
24

---

loss. A similar result can be analyzed on the cross-entropy loss on the edges
Ledgo = (o. B ge Go)
Σ
Loz(One-Hot(( (1.1)) (O e0 c(1))) Ledgo (P(Go))
(69)
and we omit the proof here for brevity.
D Sampling Algorithm
A Step-by-step procedure about the r-leaping graph generation is presented in Algorithm 2
Algorithm 2 r-LLppinng Graph Generation
1: / T
2: G. = (ffe M.jeNt I.JENt. {f (f')seent,) t- Tret (9)
3: while t do
4:
for i 1,..., do
5:
for s = 1, 1......b do (f Rs f') Es ((olols5)
6:
(a((")) Po (f,))
7:
J + Poisson(T RR (*))
P of transition for every node
8:
end for end for
9:
10:
for j. 1, .,.... do
11:
for s = L,....a a do
12:
R (1.1) (e(ls) R, (i.ii()s clis)) En
oooletia) (0 featy po po(elt)))Ge.
13:
Jann Poisson(TR.) (15)
# of transition for every edge
14:
end for
15:
end for
16:
for
1 n do -==1 Jp or Em=1 Jr = then
17:
18:
b stay the same
else
20:
8* = arg max, (J
21:
f³ f s*
& update node
end end for
23:
for
i.j
1, do
25:
De a Jol 1 or Ea Jannn = 0 then ((5) (1.5)
26:
stay the same
27:
else
s* arg maxs (Je.,,
29:
c(h)) + s*
b update edge
30:
end if
31:
end for
32:
1-
33:
end while
E Auxiliary Features, PNA and FiLM Modules
For learning better graph-to-graph mapping p (GolGr), artificially augmenting the node-level features and graph-level features is proved effective to enhance the expressiveness of graph learning models [1 73). For this setting, we keep consistent with the state-of-the-ar model, DiGress [7] and extract the following three sets of auxiliary features. Note that the following features are extracted on the noised graph G.
25

---

We binarize the edge tensor E into an adjacency matrix A E 10,1)ax whose 1 entries denote the corresponding node pair connected by any type edge.
Motif features. The number of length-3/4 ///5 cycles every node included in is counted as the topological node-level features; also, the total number of length-3/4] 3//55/6/666/// cycles is the topological graph-level features.
Spectral features. The graph Laplacian is decomposed. The number of connected components and the first non-zero eigenvalues are selected as the spectral graph-level features, An estimated indicator of whether node is included in the largest connected component and the first 2 eigenvectors of the nen-zero eigenvalues are selected as the spectral node-level features.
Molecule features. On molecule datasets, the valency of each atom is selected the node-level feature, and the total weight of the whole molecule is selected as the graph-level feature.
The above node-level features and graph-level features are concatenated together as the auxiliary node- level features F aux and graph-level features y. An important property that the above node-level features are permutation-cquivariin
and the above graph-level features are permutation-invarian whose proof is straightforward so we omit here.
Next, two important modules used in the MPNN backbone: PNA and FiLM are detailed.
PNA module. The PNA module 12 is implemented as follows,
PNA((x) = MLP(min [x @ max {xi )==1) @ mean( [x:]]=1 @ stdd (x:((()) (70)
where @ is the concatenation operator, X; E Rdd min, max, mean, and std coordinate- e.g.,
min( }=)) R
FiLM module. FiLM 57 is implemented as follows,
FiLM( Xy) = Linear(x;) + Linear(x;) O x, Xx
(71)
where Linear is single fully-comnected layer without activation function and @ is the Hadamard product.
F Supplementary Details about Experiments
F1 Hardware and Software
We implement DIsCo in PyTorcf and PyTorch-geometrigg All the efficiency study results from one NVIDIA Tesla V100 SXM2-32GB GPU on a server with 96 Intel(R) Xeon(R) Gold 6240R CPU @ 2.40GHz processors and 1.5T RAM. The training on QM9 and Community hours. For the training on SBM, Planar, it can be finished within 48 hours to get decent validity. The training on MOSES and GuacaMol can be finished within 96 hours.
be finished in 2
F.2
Dataset Setup
F.2.1
Dataset Statistics
The statistics about all the datasets used in this paper are presented in Table where is the number of edge types, is the number of node types, EE| is the number of edges and |F] is the number of nodes.
F.2.2 Detailed Settings on Plain Graph Datasets
Dataset Split. We follow the settings of SPECTRE [5T] and DiGress 73 to split the SBM,
Planar 51 and Community 82 datasets into 64/ 16/2% for training/validatiionness set.
hatpe://pytorcch.or
26

---

Table 7: Dataset statistics.
Name
# Graphs
Split
b
Avg.
E
Max E
Avg. [F]
Max
|F
SBM
128/32/40
1000.8
2258
104.0
187
Planar
200
128/32/40
355.7
362
64.0
64
Community
100
64/16/20
1
1
74.0
122
15.7
20
QM9
130831
97734/20042/13005
4
4
18.9
28
8.8
9.
MOSES
1733214
1419512//556176/155522
4
8
46.3
62
21.6
27
GuacaMol
1398213
11186333699266206554
4
12
60.4
176
27.8
88
Metrics. The Maximum Mean Discrepancy (MMD) 82 measures the discrepancy between two
sets of distributions. The relative squared MMD 73 defined as follows
MMD (19) gen (9)tesr)
score MMD2 (rr)trainl [ea))
(72)
where (19) gan- (19) train: and (19) test are the sets of generated graphs, training graphs, and test graphs, respectively. We report the above relative squared MMD for degree distributions (Deg.), clustering coefficient distributions (Clus.), and average orbit counts (Orb.) statistics (the number of occurrences of all substructures with nodes). In addition, the Uniqueness, Novelty, and Validity are chosen. Uniqueness reports the fraction of the generated nonisomorphic graphs; Novelty reports the fraction the generated graphs not isomorphic with any graph from the training set; Validity checks the fraction of the generated graphs following some specifie rules. For the SBM dataset, follow the validity check from [51] whose core idea is to check whether real SBM graphs are statistically indistinguishable from the generated graphs; for the Planar dataset, we check whether the generated graphs are connected and are indeed planar graphs. Because the Community dataset does not have the Validity metric, only report the Uniqueness, Novelty, and Validity results the SBM and Planar datasets.
We report std in 5 runs.
Baseline methods. GraphRNN 82
GRAN
42
GG-GAN 37
MoIGAN 91
SPECTRE (1].
EDP-GNN (56), GraphGDP 26 DiscDDPM chosen.
22
EDGE TO
ConGress 73 DiGress 73
F.2.3 Detailed Settings on Molecule Graph Datasets
Dataset Split.
We follow the split of QM9 from DiGress 73 and follow the split MOSES (8
and GuacaMol [6] according their benchmark settings. Their statistics presented in Table
Metrics. For QM9, Uniqueness, Novelty, and Validity are chosen as metrics. The first two are the same as introduced in Section F2.2 The Validity is computed by building a molecule with RdKit and checking if we can obtain valid SMILES string from it.
For MOSES, the chosen metrics include Uniqueness, Novelty, Validity, Filters, Fréchet ChemNet Distance (FCD), Similarity to a nearest neighbor (SNN), and Scaffold similarity (Scaf), which is consistent with DiGress 73]. The official evaluation code used to report the performance.
For GuacaMol, the chosen metrics include Uniqueness, Novelty, Validity, KI. Divergence, and Frechet ChemNet Distance (FCD), which is consistent with DiGress 73 The official evaluation code is used report the performance.
We report tssd in 5 runs except MOSES and GuacaMol, whose computations are too expensive repeat multiple times.
Baseline methods. CharacterVAF 20 Vr 38
Graph 66
GT-VAE
55
Se12GraphVAE 72), GG-GAN 37 MolGAN ( SPECTRE 511. GraphNVP [50), GDSS 32
ftttps:/www.rdkit.ot
27

---

Table 8: Generation performance (mean on the Community dataset.
Model
Deg.v
Clus.
Orb.
GraphRNN
82
4.0
1.7
4.0
GRAN 42
3.0
1.6
1.0
EDP-GNN [56
2.5
2.0
3.0
GraphGDP
[26
2.0
1.1
DiscDDPM
22
1.2
0.9
1.5
EDGE [00
1.0
1.0
2.0
GG-GAN 37
4.0
3.1
8.0
MolGAN 9
3.0
1.9
1.0
SPECTRE [51
0.5
2.7
2.0
DiGress 73
1.0
0.9
1.0
DISCO-MPNN
1.4
0.9
0.9
DISCO-GT
0.9+0.2
0.9+00.
1.1
EDGE 10
ConGress 731, DiGress [73), GRAPHARM 36 VAE 21]. JT.VAE 29 GraphIN-
VENT
53
LSTM 64), NAGVAE 40 and MCTS 28 are chosen.
E3
Hyperparameter Settings
Forward Diffusion Settings. As we introduced in Proposition 3.2 we tried two sets of rate matrices for the node and edge forward diffusion, that the converged distribution is either uniform or marginal distribution. We found the marginal distribution leads better results than the uniform distribution. Thus, the reference distribution is the marginal distribution for all the main results, except Tables and | | The performance comparison between the marginal diffusion and uniform diffusion is presented in the ablation study in Sections 4.4 a.c The ((t) controls how fast the forward process converges to the reference distribution, which set as (1) = ary (o))))))), which is g In our implementation, we assume the converged time T = and for the forward diffusion hyperparameters (at,) we tried two sets: (1.0, 5.0) and (0.8, 2.0) where the former one ensure T = 1 the distribution is very close to the reference distribution, and the latter one does not fully corrupt the raw data distribution so the graph-to-graph model Pole is easier train.
consistent with many existing works 23 70
Reverse Sampling Settings. The number of sampling steps is determined by which is round we set the converged time 7= We select the number of sampling steps from (50, 100, 500]. which is much smaller the number of sampling steps of DiGress 773 from (500, 1000). For the number of nodes n in every generated graph, we compute a graph size distribution the training set by counting the number of graphs for different sizes (and normalize the counting to sum it up 1). Then, we will sample the number of nodes from this graph size distribution for graph generation.
Neural Network Settings. For DIsCO-GT, the parametric graph-to-graph model Poje is graph transformer (GT). We use the exactly same GT architecture DiGress [3 and adopt their recom- mended configurations 10 The reason is that this architecture is not our contribution, and setting the graph-to- to- to-graph model P same can ensure fair comparison between the discrete-time graph diffusion framework (from DiGress) and the continuous-tima graph diffusion framework (from this work). For DISCO-MPNN, we search the number of MPNN layers from (3, 5, 8}, set all the hidden dimensions the same, and search it from (256, 512]. For both variants, the dropout is set as 0.1, the learning rate is set as 2e 2 and the weight decay set as O.
E.4 Additional Results Community
Additional Community plain graph dataset results are in Table 8 Our observation is consistent with the main content: both variants of DISCO are par with, even better than the SOTA general graph diffusion generative model, DiGress.
28

---

Table 9: Ablation study (mean=sstd%) with MPNN backbone. V., U., and N. mean Valid, Unique, and Novel.
Ref. Dist.
Steps
Valid
V.U. f
V.U.N. f
500
98.9=0.7
98.7=0.5
68.7+002
100
98.4
98.0_1.0
69.11006
30
97.711.2
97.5.08
70.4111
Marginal
10
92.311.9
91.9122
66.411.7
5
88.8
87.1
67.3129
1
64.4
63.2=199
55.8+14
500
93.5
93.2=111
64.9
100
93.1
92.6-1.7
66.2+11
30
87.1
86.8-1.1
64.041.
Uniform
10
83.7
81.9=2.1
61.3+20
5
81.5#229
75.4=3.4
64.6+23
1
71.3+2.3
42.2=4.0
36.9+32
E,5 Additional Ablation Study
Table shows the ablation study of DISCO-MPNN QM9 dataset. Our observations consistent with the main content: (1) generally, the fewer sampling steps, the lower the generation quality but method's performance is robust in terms of the decreasing of sampling steps; (2) the marginal reference distribution better than the uniform distribution, consistent with the observation from DiGress 773.
F.6 Convergence Study
Figure 3 shows the training loss of DIsCO-GT and DISCO-MPNN on four datasets, whose X-axis is the number of iterations (i.e., the number of epochs the number of training samples batch size). We found that overall the training losses converge smoothly on 4 datasets.
0.30
GT
GT
MPNN
0.3
MPNN
0.25
Logs
Loss
0.20
0.15
0.10
200
400
600
800
1000
0
200
400
600
800
1000
Iter.
Iter.
(a) SBM
(b) Planar
GT
GT
0.40
MPNN
2.0
MPNN
Loss
0.35
Loss
0.30
0.25
1.0
200
600
800
1000
400
600
800
Iter.
Iter.
(c) Community
(d) QM9
Figure 3: Training loss of DISCO on different datasets and backbone models.
29

---

E.7
Visualization
The generated graphs on the SBM and Planar datasets are presented in Figure 4 generated planar graphs are selected to be valid because, Table [ shows, not all the generated graphs are valid planar graphs, but the planar layout can only visualize valid planar graphs in our setting ! The generated SBM graphs not selected; even if a part of them cannot pass the striet SBM statistic test (introduced in Section F.2.2 Metrics), most, not all, of them still form 2 densely connected clusters.
We clarify that the
The generation trajectory of SBM graphs is presented in Figure 5 which demonstrates the reverse denoising process visually.
(a) SBM
(b) Planar
Figure 4: Generated graphs.
G Limitation and Future Work
In this paper, we study the generation graphs with categorical node and edge types. The current model DISCO cannot be applied to generate graphs with multiple node/edge features (c.g., multiplex networks) and this is an important future work to study. Also, we view the absence of edge as special type of edge, which forms complete graph and promotes the expressiveness of our MPNN backbone model. However, it will lead to quadratic complexity concerning the number of nodes. For current dataset (e.g. graphs with < 1000 nodes) the complexity is still acceptable but for future studies on generating large graphs, we aim to design more efficient diffusion generative models.
https://networkx. http::///etoooooooooooooootttttt wttp://www....aaaaaaa.aaa//a///a layout. planar_ glanar_layout.at lww.utyyttttt.... html
30

---

Figure 5: Generation trajectory of SBM graphs with different sizes. Every row is the generation trajectory of one graph from time T (left) & (right) with equal time intervals.
H Broader Impact
This paper presents work whose goal is to advance the field of Machine Learning. There many potential socictal consequences of our work, none of which we feel must be specifically highlighted here.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarize all the theoretical and experimental contributions of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitation mentioned in Section G
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
32

---

Justification:
Detailed assumptions and proofs are included in the Section
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibiliyy
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Detailed experimental settings are included in Section Also, the code of this paper is released in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
33

---

reproducible, they Answer: [Yes]
Justification: All the datasets are publicly available and their links are included in Section F The code released in the supplementary materials; will formally release the code after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.co
public/guidess Sabliic//uddes//oeeebbbsssssss
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 7/nips. //nips.cc/publ httppss.ccpublli/guudeeee sttp://////oooeeeessiiiissssssee
ssioiiooiiiiioioccicc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All the training details are included in Section F and the released codes.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report average results with standard deviation on all the datasets, except MOSES and GuacaMol, whose computations are too expensive to repeat multiple times.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
34

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The compute resources are detailed in Section F.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We checked the code of Ethics and the paper conforms with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: mentioned in Section Our work general graph generative modeling, which shares potential societal consequences with many established graph generative models.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
35

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We did not scrape any dataset from Internet and our released model is of low risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All the datasets and codes of baseline methods are publicly available and for the academic purpose.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
36

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We did not release any new dataset and the code released will be well docu- mented after the acceptance.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
37


Reviews:
[{"review_id": "zYNf4d9t5H", "reviewer": "Reviewer_Tpg4", "summary": "The paper introduces a novel graph generation method based on the continuous-time Monte Carlo Markov Chain by adapting the previous work [7]. The proposed architecture comes in two variants: one utilizing a graph Transformer and another using a regular message-passing neural network. The performance of the model is evaluated on artificial planar and SBM networks, as well as on real datasets for the molecule graph generation task.", "questions": "**Questions**\n- The same metrics are not used across various tables (Tables 2 and 6-8), and some tables lack error terms. This inconsistency makes it difficult to compare results comprehensively. Can the authors update the results to enhance the clarity and reliability of the results?\n- Can the proposed architecture be applicable to generate weighted and directed networks?\n- The related work section is very brief, possibly due to page limitations but an extended version can be added in the appendix.\n\n**Typos and Errors**\n- In Lines 94-95, the set membership symbol should be the subset symbol.\n- In Lines 193-197, it is assumed that J_{f_i, f^bar_i} follows Poisson distribution so how can the conditions \\sum_{ f^bar_i} J_{f_i, f^bar_i} = 1 and J_{f_i, s} > 1 hold for some s because all entries are non-negative?", "limitations": "The authors addressed the limitations of the model in the appendix.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a novel graph generation method relying on a continuous-time Markov Chain-based diffusion generative model.\n- The proposed architecture is supported by theoretical analysis.\n- The model is evaluated on both artificial and real datasets and shows comparable performance with respect to the state-of-the-art methods.", "weaknesses": "- In the real datasets, for the molecule graph generation task, baseline methods such as GraphINVENT and DiGress show comparable or better performance in some metrics.\n- The paper relies on adapting a previous continuous-time Markov Chain-based diffusion generative model for the graph domain. Thus, it doesn’t present substantial new material in terms of novelty.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer Tpg4, we appreciate your tremendous time and effort in reviewing our paper and are glad that you recognize our proposed model, theoretical contribution, and experiments. For your questions, our point-to-point responses are as follows.\n\n---\n\n> **Q1.** Baseline methods, e.g., GraphINVENT and DiGress, show comparable or better performance in some metrics and datasets.\n\n**A1.** Theoretically, **our CTMC-based model with sufficiently expressive GNNs should perform comparably to other one-shot diffusion models (e.g., Digress)**. The expressiveness comparison between autoregressive models (e.g., GraphINVENT) and one-shot diffusion models is difficult. We would like to emphasize that the main advantage and focus of our method is a **flexible sample quality vs. generation efficiency trade-off**. E.g., Table 9 in the Appendix shows our method's good generation quality even after decreasing the sampling steps from 500 to 100.\n\n---\n\n> **Q2.** The paper adapts a previous CTMC-based diffusion model for the graph domain. It doesn’t present substantial novel material.\n\n\n**A2.** Although there have been prior works (e.g., [1]) on CTMC-based diffusion models, we make the following new contributions:\n\n1. We derive a CE-based loss that differs from the existing ELBO-based loss [1]. The CE-based loss has been widely used in discrete diffusion [2-3] but still lacks a theoretical foundation. To bridge this gap, our Theorem 3.3 shows that **the CE-based loss is an upper bound of the estimation error of reverse rate matrices**.\n   \n2. Existing CTMC-based models are not permutation-equivariant, thus unsuitable for graph generation. We propose **a permutation-equivariant CTMC formulation** to address this issue. Remark that it is a highly nontrivial modification of existing discrete-time graph diffusion models. This is because discrete-time diffusion has a simpler reverse process, but the reverse process of CTMC is much more complicated.\n\nWe will revise this paper's introduction to highlight our unique contributions better.\n\n---\n\n> **Q3.** Metrics are different in Tables 2 and 6-8, and some tables lack error terms.\n\n**A3.** We appreciate this suggestion and are eager to enhance this paper's clarity. We clarify your concern regarding metrics and error terms:\n\n1. To make a fair comparison, we **keep the metrics consistent with Digress [2]**, a published SOTA solution.\n   \n2. Some of the metrics are **specific to datasets** (e.g., MOSES [4] and GuacaMol [5]). It is hard to ensure all the datasets have the same metrics. We invite the reviewer to check Sections F.2.2 and F.2.3 in the Appendix, which detail these metrics.\n\n3. Error terms for MOSES and GuacaMol are not included because their computations are too expensive for multiple runs (lines 825-826 in the Appendix).\n\n---\n\n> **Q4.** Can the proposed architecture be applicable to weighted and directed networks?\n\n**A4. Yes, our method applies to both weighted and directed graphs. For weighted graphs, the edge weights need to be discretized**. E.g., for edge weights in $[0,2]$, it could be discretized in $\\\\{0.0,0.1,\\dots,1.9,2.0\\\\}$ and viewed as discrete edge states. Then this paper's model can be used. Note that discretization has been widely used to generate images [6]. **Our model can also be applied to directed graphs**. In our implementation, for undirected graphs, only the upper-triangle of the edge type matrix $\\mathbf E$ will be sampled and the matrix will be symmetrized. **If the dataset is directed, every entry of the matrix $\\mathbf E$ will be sampled.** \n\n---\n\n> **Q5.** An extended related work section can be added.\n\n**A5.** We appreciate this great suggestion and will provide a more comprehensive related work section in the revised version.\n\n---\n\n> **Q6.** In Lines 94-95, the set membership symbol should be the subset symbol.\n\n**A6.** Sorry for the confusion; we clarify it as follows. For $\\mathbf{E} = \\\\{e^{(i,j)}\\\\}\\_{i,j\\in\\mathbb{N}^{+}\\_{\\leq n}}\\in\\\\{1,\\dots, a+1\\\\}^{n\\times n}$, $\\\\{1,\\dots, a+1\\\\}^{n\\times n}$ denotes **the set of $n\\times n$ matries** and each matrix's entries are in $\\\\{1,\\dots, a+1\\\\}$ (by the definition of Cartesian product); $\\mathbf E$ should be an $n\\times n$ matrix so the $\\in$ symbol is correct. However, we acknowledge that **the notation $\\mathbf E = \\\\{e^{(i,j)}\\\\}\\_{i,j\\in\\mathbb{N}^{+}\\_{\\leq n}}$ is not standard. We will change to a more standard $(\\cdot)$-based notation** (e.g. from https://en.wikipedia.org/wiki/Matrix_(mathematics)) in the revised version and our final notation is $\\mathbf{E} = (e^{(i,j)})\\_{i,j\\in\\mathbb{N}^{+}\\_{\\leq n}}\\in\\\\{1,\\dots, a+1\\\\}^{n\\times n}$. The notation of the vector $\\mathbf F$ will be changed similarly.\n\n---\n\n> **Q7.** How can the conditions  $\\sum\\_{\\bar{f^i}}J\\_{f^i,\\bar{f^i}} = 1$ and $J\\_{f^i,s}>1$ hold for some $s$ because all entries are non-negative?\n\n**A7.** We thank the reviewer for catching this important typo. The reviewer is right. Every $J\\_{f^i,\\bar{f^i}}$ follows Poisson distribution (line 193 in our paper) whose possible values are non-negative. **Line 196 should be \"if $\\sum\\_{\\bar{f^i}}J\\_{f^i,\\bar{f^i}} = 1$ and $J\\_{f^i,s}=1$, ...\"**\n\n\n```\nReference:\n\n[1] Campbell, Andrew, et al. \"A continuous time framework for discrete denoising models.\" NeurIPS 2022.\n\n[2] Vignac, Clement, et al. \"DiGress: Discrete Denoising diffusion for graph generation.\" ICLR 2023.\n\n[3] Austin, Jacob, et al. \"Structured denoising diffusion models in discrete state-spaces.\" NeurIPS 2021.\n\n[4] Polykovskiy, Daniil, et al. \"Molecular sets (MOSES): a benchmarking platform for molecular generation models.\" Frontiers in pharmacology 2020.\n\n[5] Brown, Nathan, et al. \"GuacaMol: benchmarking models for de novo molecular design.\" Journal of chemical information and modeling 2019.\n\n[6] Razavi, Ali, et al. \"Generating diverse high-fidelity images with vq-vae-2.\" NeurIPS 2019.\n```", "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": "gzrTnfLuf0", "reviewer": "Reviewer_ohXc", "summary": "This paper categorizes existing graph diffusion models into 4 types according to whether the space of states and time steps are discrete or continuous.  The authors design DISCO, the first discrete-state continuous-time graph diffusion generative model. By incorporating continuous-time Markov chains while preserving the discrete nature of graph data, DISCO enables more flexible sampling and decouples it from model’s training. Furthermore, this paper explores a novel and concise message-passing neural network as a replacement for complex graph transformer, while maintaining competitive performance.", "questions": "Besides more flexible sampling,  do graph diffusion models based on continuous time have any other advantages compared to discrete-time models? Does the flexibility of sampling provide any particular benefits to generating new data?", "limitations": "Yes, the authors addressed limitations, potential negative societal impact, and mitigation.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThe motivation of this work is clear and easy to understand.\n2.\tThis paper provides comprehensive mathematical proofs to help to clearly understand how to apply continuous-time Markov chains to graph diffusion generative models", "weaknesses": "1.\tSome symbols in the formulas of this paper are not clear in the context, which reduces readability\n2.\tThis paper seems to merely combine continuous-time Markov chains with discrete graph data, essentially integrating two previous works, and the innovation is slightly insufficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer ohXc, we thank you for your tremendous time and effort in reviewing our paper, and we are glad that you recognize this paper's clear motivation and theoretical contribution. For your questions, our point-to-point responses are as follows.\n\n> **Q1.** Some symbols in the formulas of this paper are not clear in the context, which reduces readability\n\n**A1.** We are sorry that this paper's readability is not satisfactory, and we will try our best to improve its clarity. If the reviewer could kindly point out  specific notations that are not well-explained in the context, it will help us **fix them in the revised versions**.\n\n---\n\n> **Q2.** This paper seems to merely combine continuous-time Markov chains with discrete graph data, essentially integrating two previous works, and the innovation is slightly insufficient.\n\n**A2.** Although there have been prior works (e.g., [1]) on CTMC-based diffusion models, we make the following new contributions:\n\n1. We derive a CE-based loss function that differs from the ELBO-based loss in existing CTMC-based diffusion [1]. The CE-based loss has been widely used in discrete diffusion [2-3] but still lacks a theoretical foundation. To bridge this gap, we prove our Theorem 3.3, showing that **the CE-based loss is an upper bound of the estimation error of reverse rate matrices**.\n   \n2. Existing CTMC-based diffusion models are not permutation-equivariant, thus unsuitable for graph generation. We propose **a permutation-equivariant version of the CTMC formulation** to address this issue. We remark that it is a highly nontrivial modification of existing discrete-time graph diffusion models. This is because discrete-time diffusion has a simpler reverse process, but the reverse process of CTMC is different and much more complicated.\n\nWe will revise this paper's introduction to highlight our unique contributions better.\n\n---\n\n> **Q3.** Besides more flexible sampling, do graph diffusion models based on continuous time have any other advantages compared to discrete-time models? Does the flexibility of sampling provide any particular benefits to generating new data?\n\n**A3.** Theoretically, CTMC-based graph diffusion generative modeling should achieve comparable performance with other one-shot diffusion frameworks (e.g., Digress [2]) if the GNN has sufficient expressiveness. The main advantage of our method, and also the focus of this paper, is to provide a flexible trade-off between sample quality and generation efficiency. For example, Table 9 in the Appendix shows that **even after decreasing the sampling steps from 500 to 100 (only with 1/5 sampling time), our method can still achieve good generation quality**. In addition, continuous-time models (including our proposed model) have greater potential, compared to the discrete-time models, to **inspire future efficient sampling methods**, e.g., [4] is inspired from [5], a continuous-time model.\n\n\n```\nReference:\n\n[1] Campbell, Andrew, et al. \"A continuous time framework for discrete denoising models.\" NeurIPS 2022.\n\n[2] Vignac, Clement, et al. \"DiGress: Discrete Denoising diffusion for graph generation.\" ICLR 2023.\n\n[3] Austin, Jacob, et al. \"Structured denoising diffusion models in discrete state-spaces.\" NeurIPS 2021.\n\n[4] Zhang, Qinsheng, and Yongxin Chen. \"Fast Sampling of Diffusion Models with Exponential Integrator.\" ICLR 2023.\n\n[5] Song, Yang, et al. \"Score-Based Generative Modeling through Stochastic Differential Equations.\" ICLR 2021.\n\n```", "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": "eBmLS57RaQ", "reviewer": "Reviewer_XoYX", "summary": "The paper presents DISCO (Discrete-State Continuous-Time Diffusion), a novel framework for graph generation. DISCO formulates the graph diffusion process in a discrete-state continuous-time setting, preserving the discrete nature of graph data while allowing for flexible sampling trade-offs between quality and efficiency. The model integrates concepts from continuous-time Markov Chains (CTMC) and employs a graph-to-graph neural network backbone for efficient graph generation.", "questions": "> Q1: the motivation for making the original discrete transition process continuous is to improve the sampling efficiency. Has this been achieved in the proposed method? If so, what is the improvement and where exactly does this improvement come from?", "limitations": "N.A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- the paper is well written. most sections are easy to follow\n\n- the proposed research question is important (efficiency is indeed a limitation of current discrete graph generation model) \n\n- the proposed method is technically sound", "weaknesses": "> w1: the proposed seems to be a rather straightforward derivation from the existing tools (replacing discrete markov chain with continuous time)\n\n> w2: no implementation available\n\n> w3:  there is a disconnection between the proposed motivation (sampling motivation) and the (theoretical) discussion of the proposed method (see questions below)\n\n> w4: most theoretical results seem to be a standard derivation from existing literature", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer XoYX, we appreciate your tremendous time and effort in reviewing our paper and are glad that you recognize its presentation, technical soundness, and importance to this research problem. Our point-to-point responses to your questions are as follows.\n\n> **Q1.** The proposed method seems to be a rather straightforward derivation from the existing tools (replacing discrete markov chain with continuous time). Most theoretical results seem to be a standard derivation from existing literature.\n\n**A1.**  Although there have been prior works (e.g., [1]) on CTMC-based diffusion models, we make the following new contributions:\n\n1. Existing CTMC-based diffusion models (e.g., [1]) are not permutation-equivariant, thus not suitable for graph generation. We propose a permutation-equivariant version of the CTMC formulation to address this issue. We remark that it is **a highly nontrivial modification of existing discrete-time graph diffusion models**. This is because discrete-time diffusion has a simpler reverse process, but the reverse process of CTMC is different and much more complicated.\n   \n2. We derive a CE-based loss function different from the existing ELBO-based loss for CTMC-based diffusion [1]. The CE-based loss has been widely used in discrete diffusion [2-3] but still lacks a theoretical foundation. To bridge this gap, we prove our Theorem 3.3, showing that the CE-based loss is an upper bound of the estimation error of reverse rate matrices. To our best knowledge, **such analysis does not exist in existing literature.**\n\n3. The theoretical analysis in Section 3.6 shows the proposed graph generative model's permutation equivariance and invariance. Our analysis is **not derived from existing literature** because it has to be **tailored for the specific model/framework**. In other words, we propose a new graph generative model and theoretically prove it also enjoys nice permutation equivariant/invariant properties.\n\nWe will revise this paper's introduction to highlight our unique contributions better.\n\n---\n\n> **Q2.** no implementation available\n\n**A2.** We have provided our code as a ZIP file in the **supplementary material on OpenReivew**. We are sorry that we forgot to mention this in the paper. We will also open-source our code once this paper is accepted.\n\n---\n\n> **Q3.** there is a disconnection between the proposed motivation (sampling motivation) and the (theoretical) discussion of the proposed method. The motivation for making the original discrete transition process continuous is to improve the sampling efficiency. Has this been achieved in the proposed method? If so, what is the improvement and where exactly does this improvement come from?\n\n**A3.** Thanks for raising this question to improve the presentation of this paper. We clarify your concerns from the following three perspectives: \n\n1. Yes, **our proposed method successfully improves the generation efficiency**. The detailed comparison is in Table 9, which shows that the generation quality is still very good even after decreasing the sampling steps from 500 to 100 (i.e., only with 1/5 wall-clock sampling time).\n   \n2. The reason why the proposed model can achieve such a quality-efficiency tradeoff is that **the step size of approximate simulating methods (e.g., $\\tau$-leaping [1]) for CTMC determines the accuracy vs. efficiency trade-off**: smaller step sizes generally lead to more accurate simulations but require more computational time and larger step sizes can be faster but with lower simulating accuracy.\n\n3. To achieve such sampling flexibility, this paper presents a CTMC-based graph diffusion generative framework. We agree with the reviewer that our theoretic analysis is not related to the generation efficiency; however, **analysis in Section 3.6 illustrates that our CTMC-based framework is suitable for graph generation** (i.e., with important permutation equivariant/invariant properties) and **Theorem 3.3 motivates the loss function**, which is critical for the model training.\n\nWe will highlight the connection between the motivation and the proposed method in revised versions.\n\n```\nReference:\n\n[1] Campbell, Andrew, et al. \"A continuous time framework for discrete denoising models.\" NeurIPS 2022.\n\n[2] Vignac, Clement, et al. \"DiGress: Discrete Denoising diffusion for graph generation.\" ICLR 2023.\n\n[3] Austin, Jacob, et al. \"Structured denoising diffusion models in discrete state-spaces.\" NeurIPS 2021.\n\n```", "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": "BKHfEXzYab", "reviewer": "Reviewer_9BTR", "summary": "This paper is an extension of current graph diffusion generation to discrete-state and continuous-time version, and proposes DisCo model. The authors also prove permutation-equivariance/invariance of the proposed diffusion framework, sampling and training loss.", "questions": "As shown in table 3, DisCo-MPNN is much more efficient than DisCo-GT. But from eq. (7) and (8), DisCo-MPNN also conducts aggregation over the whole graph, so its complexity is the same as graph transformer. How to explain this point?", "limitations": "I recommend the authors supplement more relevant baselines to enrich the experiments.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Continuous-time diffusion is a generlization of different strategies, e.g. DDPM and NCSN, so it is more powerful and flexible. Discrete state is also suitable for graph data becaused of discrete edge connection and node classes. This paper integrates these two advantages into a framework, and its good performance is expected.\n\n2. The wrting quality and organization is good and easy to follow.", "weaknesses": "The selected baselines are not enough. Only DiGress is compared as graph diffusion generation, but other generation methods based on diffusion have been developed. I only list two relevant baselines  [1-2], but I convince that there are more relevent baselines.\n\n[1] Chen, X., He, J., Han, X., & Liu, L. P. (2023). Efficient and degree-guided graph generation via discrete diffusion modeling. arXiv preprint arXiv:2305.04111.\n\n[2] Fu, X., Gao, Y., Wei, Y., Sun, Q., Peng, H., Li, J., & Li, X. (2024). Hyperbolic Geometric Latent Diffusion Model for Graph Generation. arXiv preprint arXiv:2405.03188.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 9BTR, we appreciate your tremendous time and effort in reviewing our paper and are glad that you recognize the proposed method's reasonability and writing quality. Our point-to-point responses to your questions are as follows.\n\n> **Q1.** The selected baselines are not enough. Only DiGress is compared as graph diffusion generation, but other generation methods based on diffusion have been developed. I only list two relevant baselines, but I convince that there are more relevent baselines.\n\n**A1.** Thanks for this suggestion.  First, we would like to explain that in our submitted version, we basically select the same baseline methods as Digress (a SOTA discrete graph diffusion generative model) because our goal is to show the proposed method can have **competitive performance against Digress [1]** but with **much better efficiency**; in other words, our goal is **not to pursue a higher generation quality, but a better accuracy-efficiency trade-off**. \n\nMeanwhile, following reviewer's suggestion, we have included more baseline methods' reported performance as follows: \n\n1. We include results of Digress and our method DisCo from our submitted paper for comparison.\n  \n2. Newly added baselines are commonly tested on different datasets or metrics, so we only **report their performance on the shared datasets and metrics** in our paper during the rebuttal phase. We will include more baselines, datasets, and metrics in the revised version.\n\n3. We report more results on the Community dataset in Table 1 below, whose metrics are MMD ratios $\\textrm{MMD}^2(\\{\\mathcal{G}\\}\\_{\\texttt{gen}}||\\{\\mathcal{G}\\}\\_{\\texttt{test}})/\\textrm{MMD}^2(\\{\\mathcal{G}\\}\\_{\\texttt{train}}||\\{\\mathcal{G}\\}\\_{\\texttt{test}})$ (more details about this metric are in Appendix Section F.2.2) which shows that **DisCo has comparable performance against many SOTA models**. Also, we would like to note that intuitively, **the MMD ratios should not be much lower than 1**, because the distribution of the training set is the optimization objective of our generative models. Interestingly, HypDiff reports performance as low as 0.1, which appears to be significantly lower than other models. We will investigate this further by examining their evaluation and attempting to reproduce their results after this rebuttal phase.\n\n4. We report more results on the QM9 dataset in Table 2 below, which **also shows that DisCo performs comparably** against SOTA models.\n\n| Model | Deg.$\\downarrow$ | Clus.$\\downarrow$ | Orb.$\\downarrow$ |\n|---|---|---|---|\n|     GNF [2]    | 1.0 | 2.9 | 17.0 |\n| EDP-GNN [3] | 2.5 | 2.0 | 3.0 |\n| GraphGDP [4] | 2.0 | 1.1 | - |\n| GDSS [5] | 2.3 | 1.2 | 0.7 |\n|     DiscDDPM [6]   | 1.2 | 0.9 | 1.5 |\n| EDGE [7] | 1.0 | 1.0 | 2.0 |\n| HypDiff [8] | 0.1 | 0.1 | - |\n| DiGress [1]  | 1.0 | 0.9 | 1.0 |\n| DisCo-GT (Ours) | 0.9$\\pm$0.2 | 0.9$\\pm$0.3 | 1.1$\\pm$0.4 |\n| DisCo-MPNN (Ours) | 1.4$\\pm$0.5 | 0.9$\\pm$0.2 | 0.9$\\pm$0.3 |\nTable 1. More results from baselines on the **Community** Dataset\n\n\n| Model | Valid $\\uparrow$ | V.U. $\\uparrow$ | V.U.N. $\\uparrow$ |\n|---|---|---|---|\n| GDSS [5] | 95.7 | 94.3 | - |\n| EDGE [7] | 99.1 | 99.1 | - |\n| ConGress [1] | 98.9 | 95.7 | 38.3 |\n| DiGress [1] | 99.0 | 95.2 | 31.8 |\n| DisCo-GT (Ours) | 98.0$\\pm$0.7 | 97.6$\\pm$0.5 | 68.6$\\pm$0.8 |\n| DisCo-MPNN (Ours) | 92.8$\\pm$2.1 | 91.2$\\pm$1.5 | 78.0$\\pm$1.1 |\nTable 2. More results from baselines on the **QM9** Dataset\n\n---\n\n> **Q2.** As shown in table 3, DisCo-MPNN is much more efficient than DisCo-GT. But from eq. (7) and (8), DisCo-MPNN also conducts aggregation over the whole graph, so its complexity is the same as graph transformer. How to explain this point?\n\n**A2.** This is a good question. You are right that the MPNN's aggregation is over the whole graph, as we mentioned between lines 210 and 214 and that is the reason why we believe MPNN can also achieve nice effectiveness. The key architecture difference between GT (from Digress [1]) and our MPNN is that we remove the **multi-head outer product-based self-attention layers** (lines 236-237), as we empirically found their contribution to the generation quality is minor, but are computationally very expensive. In other words, our model can be viewed with **only 1 head without computing the attention**, which leads to the speedup and the decrease of \\# of parameters. \n\nP.S., the multi-head outer product-based self-attention layers from Digress can be found in Figure 6 in [1], and their implementation is between lines 182-184 in https://github.com/cvignac/DiGress/blob/main/src/models/transformer_model.py.\n\n\n```\nReference:\n\n[1] Vignac, Clement, et al. \"DiGress: Discrete Denoising diffusion for graph generation.\" ICLR 2023.\n\n[2] Liu, Jenny, et al. \"Graph normalizing flows.\" NeurIPS 2019.\n\n[3] Niu, Chenhao, et al. \"Permutation invariant graph generation via score-based generative modeling.\" AISTATS 2020.\n\n[4] Huang, Han, et al. \"Graphgdp: Generative diffusion processes for permutation invariant graph generation.\" ICDM 2022.\n\n[5] Jo, Jaehyeong, Seul Lee, and Sung Ju Hwang. \"Score-based generative modeling of graphs via the system of stochastic differential equations.\" ICML 2022.\n\n[6] Haefeli, Kilian Konstantin, et al. \"Diffusion Models for Graphs Benefit From Discrete State Spaces.\" NeurIPS 2022 GLFrontiers Workshop.\n\n[7] Chen, Xiaohui, et al. \"Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling.\" ICML 2023.\n\n[8] Fu, Xingcheng, et al. \"Hyperbolic Geometric Latent Diffusion Model for Graph Generation.\" ICML 2024.\n```", "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:
Dear reviewers, we thank you for your time and effort in providing valuable reviews for our paper. We appreciate the reviewers' recognition that our theoretic results support the proposed method (Tpg4 and ohXc), that our experiments are comprehensive (Tpg4), that our paper is clear and easy to understand (XoYX and 9BTR), that the method is technically sound (XoYX). We also thank the reviewers for their constructive comments to improve this paper further. Our responses to your questions are provided below. We sincerely invite reviewers for further discussion.

Meta-review: The paper proposes a discrete-state continuous-time diffusion model for graph generation. The main novelty of the model stems from its ability to directly deal with the discrete nature of graphs in the generation process while simultaneously being flexible by relying on a continuous-time sampling mechanism. These aspects have been highlighted by the reviewers -- making a solid contribution to the field. The response of the authors to the different questions raised further clarified several aspects of the paper. Therefore, I recommend accepting the paper.
Decision: Accept (poster)