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_cc_2024_Conference
Published: 2024-05-03 03:11:21

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.

Main paper: 
 introduction: 
 Graph generation has been studied for a long time with broad applications, based on either the one-shot (i.e., one-step) [50, 39, 56, 51, 72, 32] or auto-regressive generation paradigm [82, 29, 42, 52] . The former generates all the graph components at once and the latter does that sequentially. A recent trend of applying diffusion generative models [67, 23, 70] to graph generation tasks attracts increasing attentions because of its excellent performance and solid theoretical foundation. In this paper, we follow the one-shot generation paradigm, the same as most graph diffusion generative models. Some earlier attempts at graph diffusion models treat the graph data in a continuous state space by viewing the graph topology and features as 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 [73] is one of the early efforts applying discrete-state diffusion models to graph generation tasks and is the current state-of-the-art 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 is a fixed hyperparameter after the model finishes training. A unique advantage of the continuous-time diffusion models [70, 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., τ -leaping [18, 8, 71] ) and decoupled from the models' training. Thus, a discrete-state continuous-time diffusion model is highly desirable for graph generation tasks.Driven by the recent advance of continuous-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-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-time graph diffusion model is named DISCO. DISCO bears several desirable properties and advantages. First, despite its simplicity, the training objective has a rigorously proved connection to the sampling error. Second, its formulation includes a parametric graph-to-graph mapping, named backbone model, whose input-output 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-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 permutation-equivariant/invariant 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-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 approximation error (Theorem 3.3) and (2) invariant/equivariant properties of DISCO in terms of the permutation of nodes (Theorems 3.8 and 3.9). • Experiment. Extensive experiments validate the empirical performance of DISCO. 
discrete-state continuous-time diffusion models: 
 A D-dimensional discrete state space is represented as X = {1, . . . , C} D . A continuous-time Markov Chain (CTMC){x t = [x 1 t , • • • x D t ]} t∈[0,T ] is characterized by its (time-dependent) rate matrix R t ∈ R |X |×|X | . Here x t is the state at the time step t. The transition probability q t|s between from time s to t satisfies the Kolmogorov forward equation, for s < t,EQUATIONThe marginal distribution can be represented as q t (x t ) = x0∈X q t|0 (x t |x 0 )π data (x 0 ) where π data (x 0 ) is the data distribution. If the CTMC is defined in time interval [0, T ] and if the rate matrix R t is well-designed, the final distribution q T (x T ) can be close to a tractable reference distribution π ref (x T ), e.g., uniform distribution. We notate the reverse stochastic process as xt = x T -t ; a well-known fact (e.g., Section 5.9 in [63] ) is that the reverse process {x t } t∈[0,T ] is also a CTMC, characterized by the reverse rate matrix: Rt (x, y) = q(y) q(x) R t (y, x). The goal of the CTMC-based diffusion models is an accurate estimation of the reverse rate matrix Rt so that new data can be generated by sampling the reference distribution π ref and then simulating the reverse CTMC [16, 17, 18, 1] . However, the complexity of the rate matrix is prohibitively high because there are C D possible states. A reasonable simplification is to factorize the process over dimensions [8, 71, 73, 2] . Specifically, the forward process is factorized as q t|s (x t |x s ) = D d=1 q t|s (x [71] propose another singleton conditional distribution-based objective p θ (y d |x \d ,t) p θ (x d |x \d ,t) ≈ q(y d |x \d ) q(x d |x \d ) whose rationale is Brook's Lemma [5, 49] .t (x d , y d ) = x d 0 R d t (y d , x d ) q t|0 (y d |x d 0 ) q t|0 (x d |x d 0 ) q 0|t (x d 0 |x). Campbell et al. [8] estimate q 0|t (x d 0 |x) via a neural network p θ such that p θ (x d 0 |x, t) ≈ q 0|t (x d 0 |x); Sun et al.We study the graphs with categorical node and edge attributes. A graph with n nodes is represented by its edge type matrix and node type vector: G = (E, F), where E = (e (i,j) ) i,j∈N + ≤n ∈ {1, . . . , a + 1} n×n , F = (f i ) i∈N + ≤n ∈ {1, . . . , 
method: 
 This section presents the proposed discrete-state continuous-time graph diffusion model, DISCO whose overview is Figure 2 . Section 3.1 introduces 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 in Sections 3.3 and 3.4, respectively. Last but not least, a specific neural architecture of the graph-to-graph backbone model and its properties regarding the permutation of node ordering are introduced in Sections 3.5 and 3.6, respectively. All proofs are in Appendix.The number of possible states of an n-node graph is (a + 1) n 2 × b n which is intractably large. Thus, we follow existing discrete models [2, 8, 71, 73] and formulate the forward processes on every node/edge to be independent. Mathematically, the forward diffusion process for s < t is factorized asq t|s (G t |G s ) = n i,j=1q t|s (eEQUATIONwhere the edge type transition probabilities {q t|s (e , respectively. The forward processes, i.e., the forward rate matrices in our context, are predefined, which will be introduced in Section 3.2. Given the factorization of forward transition probability in Eq. ( 2), a question is raised: what is the corresponding factorization of the forward rate matrix (R t ) and the reverse rate matrix ( Rt )? Remark 3.1 shows such a factorization.1: A training graph G 0 = ({f i 0 }, {e (i,j) 0 }) is given. 2: Sample t ∼ U (0,T ) ; sample G t based on transition probabilities q t|0 (f t = v|f 0 = u) = (e t 0 β(s)R f ds ) uv and q t|0 (e t = v|e 0 = u) = (e t 0 β(s)Reds ) uv , given G 0 = ({f i 0 }, {e (i,j) 0 }). 3: Predict the clean graph Ĝ0 = ({ f i 0 }, {ê (i,j) 0 }) ← {p θ 0|t (f i |G t )}, {p θ0|t (e (i,j) |G t )} , given G t . 4: Compute cross-entropy loss between G 0 and Ĝ0 based on Eq. ( 6) and update θ.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 asR t ( Ḡ, G) = i A i t + i,j B (i,j) t (3) Rt (G, Ḡ) = i A i t f i 0 q t|0 ( f i |f i 0 ) q t|0 (f i |f i 0 ) q 0|t (f i 0 |G) + i,j B (i,j) t e (i,j) 0 q t|0 (ē (i,j) |e (i,j) 0 ) q t|0 (e (i,j) |e (i,j) 0 ) q 0|t (e (i,j) 0 |G) (4)whereA i t = R i t ( f i , f i )δ Ḡ\ f i ,G\f i , B (i,j) t = R (i,j) t (ē (i,j) , e (i,j) )δ Ḡ\ē (i,j) ,G\e (i,j) , the operator δ Ḡ\ f i ,G\f i (or δ Ḡ\ē (i,j) ,G\e (i,j) ) checks whether two graphs Ḡ and G are exactly the same except for node i (or the edge between nodes i and j).Note that this factorization itself is not our contribution but a necessary part of our framework, so we mention it here for completeness. Its full derivation is in Appendix -Section A. Next, we detail the design of forward rate matrices.A proper choice of the forward rate matrices {R (i,j) t } i,j∈N , should converge to their reference distributions within [0, T ] and (2) the reference distributions should be easy to sample (e.g., uniform distribution). We follow [8] to formulate R(i,j) t = β(t)R (i,j) e , ∀i, j and R i t = β(t)R i f , ∀i, where β(t) is a corruption schedule, {R (i,j) e} and {R i f } are the base rate matrices. For brevity, we set all the nodes/edges to share a common node/edge rate matrix, i.e., R (i,j) e = R e and R i f = R f , ∀i, j. Then, the forward transition probability for all the nodes and edges are q t|0 (f t = v|f 0 = u) = (e t 0 β(s)R f ds ) uv and q t|0 (e t = v|e 0 = u) = (e t 0 β(s)Reds ) uv , 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 B.For categorical data, a reasonable reference distribution is a uniform distribution, i.e., π f = 1 b for nodes and π e = 1 a+1 for edges. In addition, inspired by [73] , we find that node and edge marginal distributions m f and m e are good choices as the reference distributions. Concretely, an empirical estimation of m f and m e 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 to uniform and marginal distributions. if R f = 1m ⊤ f -I and R e = 1m ⊤ e -I.1 is an all-one vector and I is an identity matrix.Regarding the selection of β(t), we follow [23, 70, 8] and set β(t) = αγ t log(γ) for a smooth change of the rate matrix. α and γ are hyperparameters. Detailed settings are in Appendix F.3.Next, we introduce the estimation of the reverse process from its motivation. The reverse process is essentially determined by the reverse rate matrix Rt in Eq. ( 4), whose computation needs q 0|t (f i 0 |G) and q 0|t (e (i,j) 0 |G), ∀i, j; their exact estimation is expensive because according to Bayes' rule, p t (G) is needed, whose computation needs to enumerate all the given graphs:p t (G) = G0 q t|0 (G|G 0 )π data (G 0 ).Thus, we propose parameterizing the reverse transition probabilities via a neural network θ whose specific architecture is introduced in Section 3. 5 = i Ri θ,t (f i , f i ) + i,j R(i,j) θ,t (e (i,j) , ē(i,j) ) where Ri θ,t (f i , f i ) = A i t f i 0 q t|0 ( f i |f i 0 ) q t|0 (f i |f i 0 ) p θ 0|t (f i 0 |G), R(i,j) θ,t (e (i,j) , ē(i,j) ) = B (i,j) t e(i,j) 0 q t|0 (ē (i,j) |e (i,j) 0) q t|0 (e (i,j) |e(i,j) 0 ) p θ 0|t (e (i,j) 0|G), and the remaining notations are the same as Eq. ( 4). Note that all the terms {p θ 0|t (f i |G)} i∈N + ≤n and {p θ 0|t (e (i,j) |G)} i,j∈N + ≤n can be viewed together as a graph-to-graph mapping θ : G → G, whose input is the noisy graph G t 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 Rt (from Eq. ( 4)) and the parametric Rθ,t 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 asf i 0 = [p θ 0|t (f i = 1|G t ), . . . , p θ 0|t (f i = b|G t )] ⊤ ∈ [0, 1] b and ê(i,j) 0 = [p θ 0|t (e (i,j) = 1|G t ), . . . , p θ 0|t (e (i,j) = a + 1|G t )] ⊤ ∈ [0, 1] a+1 . Theorem 3.3 (Approximation error). for G ̸ = Ḡ Rt (G, Ḡ) -Rθ,t (G, Ḡ) 2 ≤ C t + C node t E G0 q t|0 (G|G 0 ) i L CE One-Hot(f i 0 ), f i 0 + C edge t E G0 q t|0 (G|G 0 ) i,jL CE One-Hot(e (i,j) 0), ê(i,j)EQUATION)where C t , C node t , and C edge t are constants independent on θ but dependent on t, G, and Ḡ; One-Hot transforms f i 0 and e (i,j) 0 into one-hot vectors.The bound in Theorem 3.3 is tight, i.e., the right-hand side of Eq. ( 5) is 0, whenever f i 0 = q 0|t (f i 0 |G t ), ∀i and ê(i,j) 0 = q 0|t (e (i,j) 0|G t ), ∀i, j. Guided by Theorem 3.3, we (1) take expectation of t by sampling t from a uniform distribution t ∼ U (0,T ) and (2) simplify the right-hand side of Eq. ( 5) by using the unweighted CE loss as our training objective:min θ T E t E G0 E q t|0 (Gt|G0) i L CE (One-Hot(f i 0 ), f i 0 ) + i,jL CE (One-Hot(eEQUATIONA step-by-step training algorithm is in Algorithm 1. Note that the above CE loss has been used in some diffusion models (e.g., [2, 8] ) but lacks a good motivation, especially in the continuous-time setting. We motivate it based on the rate matrix discrepancy, as a unique contribution of this paper.Given the parametric reverse rate matrix Rθ,t (G, Ḡ), the graph generation process can be implemented by two steps: (1) sampling the reference distribution π ref (i.e., π f for nodes and π e for edges) and(2) numerically simulating the CTMC from time T to 0. The exact simulation of a CTMC has been studied for a long time, e.g., [16, 17, 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θ,t requires recomputation. A practical approximation is to assume Rθ,t is fixed during a time interval [t -τ, t], i.e., delaying the happening of transitions in [t -τ, t] and triggering them all together at the time t -τ ; this strategy is also known as τ -leaping [18, 8, 71] , and DISCO adopts it.We elaborate on τ -leaping for transitions of node types; the transitions of edge types are similar. The rate matrix of the i-th node is fixed as Riθ,t (f i , f i ) = R i t ( f i , f i ) f i 0 q t|0 ( f i |f i 0 ) q t|0 (f i |f i 0 ) p θ 0|t (f i |G t ), during [t -τ, t].According to the definition of rate matrix, in [t -τ, t], the number of transitions fromf i to f i , namely J f i , f i , follows the Poisson distribution, i.e., J f i , f i ∼ Poisson(τ Ri θ,t (f i , f i )). For categorical data (e.g., node type), multiple transitions in [t -τ, t] are invalid and meaningless. In other words, for the i-th node, if the total number of transitionsf i J f i , f i > 1, f i keeps unchanged in [t -τ, t]; otherwise, if f i J f i , f i = 1 and J f i ,s = 1, i.e., there is exact 1 transition, f i jumps to s. A step-by-step sampling algorithm (Algorithm 2) is in Appendix. Remark 3.4. The sampling error of τ -leaping is linear to C err [8] , the approximation error of the reverse rates: G̸ = Ḡ Rt (G, Ḡ) -Rθ,t (G, Ḡ) ≤ C err . Interested readers are referred to Theorem 1 from [8] . Our Theorem 3.3 shows the connection between our training loss and C err , which further verifies the correctness of our training loss.As mentioned in Section 3.3, the parametric backbone p θ 0|t (G 0 |G t ) is a graph-to-graph mapping whose input is the noisy graph G t and its output is the predicted denoised graph G 0 . There exists a broad range of neural network architectures. Notably, DiGress [73] uses a graph Transformer (GT) as p θ 0|t , a decent reference for our continuous-time framework. We name our model with the GT backbone as DISCO-GT and its detailed configuration is in Appendix F.3. The main advantage of the GT is its long-range interaction thanks to 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, we posit that a regular message-passing neural network (MPNN) [19] should be a promising choice for p θ 0|t (G 0 |G t ). It is recognized that the MPNNs' expressiveness might not be as good as GTs' [33, 7] , e.g., in terms of long-range interactions. However, in our setting, the absence of an edge is viewed as a special type of edge and the whole graph is complete; therefore, 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 ∈ {1, . . . , a, a + 1} n×n , F ∈ {1, . . . , b} n , we first transform both the matrix E and F into one-hot embeddings E OH ∈ {0, 1} n×n×(a+1) and F OH ∈ {0, 1} n×b . Then, some auxiliary features (e.g., the # of specific motifs) are extracted: F aux , y aux = Aux(E OH ) to overcome the expressiveness limitation of MPNNs [11] .Here F aux and y aux are the node and global auxiliary features, respectively. Note that a similar auxiliary feature engineering 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 F OH ⊕ F aux , edge features E OH , and global features y aux into a common hidden space asF hidden = MLP(F OH ⊕ F aux ), E hidden = MLP(E OH ), y hidden = MLP(y aux ), where ⊕ is a concatenation operator.The following formulas present the update of node embeddings (e.g., r i = F(i, :)), edge embedding (e.g., r (i,j) = E(i, j, :)), and global embedding y in an MPNN layer, where we omit the subscript hidden if it does not cause ambiguity:EQUATIONThe edge embeddings are aggregated by mean pooling (i.e., n j=1 r (j,i) /n); the node pair embeddings are passed to edges by Hadamard product (i.e., r i ⊙ r j ); 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 E. 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 input dimensions, MLP(F) ∈ R n×b and MLP(E) ∈ R n×n×(a+1) , which are output after wrapped with softmax.Both the proposed MPNN and the GT from DiGress [73] use the PNA and FiLM to merge embeddings, but MPNN does not have multi-head self-attention layers so that the computation overhead is lower.Reordering the nodes keeps the property of a given graph, which is known as permutation invariance. In addition, for a given function if its input is permuted and its output is permuted accordingly, such a behavior is known as permutation equivariance. In this subsection, we analyze permutationequivariance/invariance of the (1) diffusion framework (Lemmas 3.5, 3.6, and 3.7), (2) sampling density (Theorem 3.8), and (3) training loss (Theorem 3.9). Lemma 3.5 (Permutation-equivariant layer). The proposed MPNN layer (Eqs. ( 7) and ( 8)) is permutation-equivariant.The auxiliary features from the Aux are also permutation-equivariant (see Appendix E). Thus, the whole MPNN-based backbone p θ 0|t is permutation-equivariant. Note that the GT-based backbone from DiGress [73] is also permutation-equivariant whose proof is omitted as it is not our contribution. Next, we show the permutation invariance of the rate matrices. Lemma 3.6 (Permutation-invariant rate matrices). The forward rate matrix of DISCO is permutationinvariant if it is factorized as Eq. (3). The parametric reverse rate matrix of DISCO ( Rθ,t ) is permutation-invariant whenever the graph-to-graph backbone p θ 0|t is permutation-equivariant. Lemma 3.7 (Permutation-invariant transition probability). For CTMC satisfying the Kolmogorov forward equation (Eq. ( 1)), if the rate matrix is permutation-invariant (i.e., R t (x i , x j ) = R t (P(x i ), P(x j )), the transition probability is permutation-invariant (i.e., q t|s (x t |x s ) = q t|s (P(x t )|P(x s )), where P is a permutation.Based on Lemmas 3.6 and 3.7, DISCO's parametric reverse transition probability is permutationinvariant. The next theorem shows the permutation-invariance of the sampling probability. Theorem 3.8 (Permutation-invariant sampling probability). If both the reference distribution π ref and the reverse transition probability are permutation-invariant, the parametric sampling distribution p θ 0 (G 0 ) is permutation-invariant.In addition, the next theorem shows the permutation invariance of the training loss. Theorem 3.9 (Permutation-invariant training loss). The proposed training loss Eq. ( 6) is invariant to any permutation of the input graph G 0 if p θ 0|t is permutation-equivariant. 
experiments: 
 This section includes: an effectiveness evaluation on plain graphs (Section 4.1) and molecule graphs (Section 4.2), an efficiency study (Section 4.3), and an ablation study (Section 4.4). Detailed settings (Sections F.1-F.3), additional effectiveness evaluation (Sections F.4, additional ablation study (Section F.5), convergence study (Section F.6), and visualization (Section F.7) are in Appendix. Our code is released3 .Datasets and metrics. Datasets SBM, Planar [51] , 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 number of occurrences of substructures with 4 nodes), Uniqueness(%), Novelty(%), and Validity(%) are chosen as metrics. Details about the datasets, metrics, baselines (Section F.2.2), and results on Community (Table 8 ) are in Appendix.Results. Table 1 shows the effectiveness evaluation on SBD and Planar from which we observe: • 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 performance in terms of Validity is not the statistics reported in the paper but from their latest model checkpoint 4 .In fact, we found it very hard for DiGress and DISCO-GT to 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: our models can still trade-off between the sampling efficiency and quality even after the model is trained and frozen. • In general, DISCO-MPNN has competitive performance against DISCO-GT in terms of Deg., Clus., and Orb. However, its performance is worse compared to DISCO-GT in terms of Validity, which might be related to the different model expressiveness. Studying the graph-to-graph model expressiveness would be an interesting future direction, e.g., generating valid Planar graphs. Table 2 shows the performance on QM9 dataset. Our observation is consistent with the performance comparison on plain datasets: (1) DISCO-GT obtains slightly better or at least competitive performance against DiGress due to the shared graph-to-graph backbone, but our framework offers extra flexibility in the sampling process; (2) DISCO-MPNN obtains decent performance in terms of Validity, Uniqueness, and Novelty comparing with DISCO-GT.Tables 3 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. A major computation bottleneck is the graph-to-graph backbone p θ 0|t , which is GT or MPNN. We compare the number of parameters, the forward and backpropagation time of GT and MPNN in Table 5 . For a fair comparison, we set all the hidden dimensions of GT and MPNN as 256 and the number of layers as 5. We use the Community [82] dataset and set the batch size as 64. Table 5 shows that GT has a larger capacity and more parameters at the expense of more expensive training. An ablation study on DISCO-GT for reference distributions (marginal vs. uniform), and sampling steps (1 to 500) is presented in Table 6 .The number of sampling steps is round( 1 τ ) if T = 1. QM9 dataset is chosen. A similar ablation study on DISCO-MPNN is in Table 9 in Appendix. We observe that first, generally, 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), the performance degradation is still very slight, implying our method's high robustness in sampling steps. Second, the marginal reference distribution is better than the uniform distribution, consistent with the observation from DiGress [73] . 
related work: 
 Diffusion models [80] can be interpreted from both the score-matching [69, 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 is 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; τ -LDR [8] generalizes D3PM by formulating a continuous-time Markov chain; [71] proposes a 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 [44, 13, 85, 86, 84, 15, 83, 14, 61, 74, 47, 79, 78, 59, 3] such as molecule design [65, 25, 27, 43] . Pioneering works such as EDP-GNN [56] and GDSS [32] diffuse graph data in a continuous state space [26] . DiscDDPM [22] is an early effort to modify the DDPM architecture into a discrete state. In addition, DiGress [73] is also a 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 an interesting process: diffusing graphs into empty graphs. Besides, GRAPHARM [36] proposes an autoregressive graph diffusion model, and [45] applies the diffusion models for molecule property prediction tasks. In addition to the above-mentioned general graph diffusion models, there are many other task-tailored graph diffusion generative models [48, 30, 41, 60, 77, 76, 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 a solid theoretical foundation. We also propose a simplified message-passing architecture to serve as the graph-to-graph 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. Proposition B.1 (Analytical forward process for commutable rate matrices, Proposition 10 from [8] ). if R t and R t ′ commute ∀t, t ′ , q t|0 (x t = j|x 0 = i) = (e t 0 Rsds ) ij Proof. If q t|0 = exp t 0 R s ds is the forward transition probability matrix, it should satisfy the Kolmogorov forward equation d dt q t|0 = q t|0 R s . The transition probability matrixEQUATIONand, based on the fact that R t and R ′ t commute ∀t, t ′ , its derivative isEQUATIONThus, q t|0 = exp t 0 R s ds is the solution of Kolmogorov forward equation.For the node i, if its forward rate matrix is set as R i t = β(t)R f , we have R i t and R i t ′ commute, ∀t, t ′ . Thus, the transition probability for node i is q t|0 (f i t = v|f i 0 = u) = (e t 0 β(s)R f ds ) uv . Based on similar derivation, we have the transition probability for the edge (i, j) as q t|0 (e Proof. If we formulate the rate matrices for nodes and edges as R (i,j) t = β(t)R e , ∀i, j and R i t = β(t)R f , ∀i, every rate matrix is commutable for any time steps t and t ′ . In the following content, we show the proof for the node rate matrix R i t = β(t)R f ; the converged distribution of edge can be proved similarly. Based on Proposition B.1, the transition probability matrix between time steps t and t + ∆t is(i,j) t = v|e (i,j) 0 = u) = (e t 0 β(s)Reds ) uv . 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 to 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 a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the 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 a dataset. 
 
 Appendix: EQUATIONEQUATIONwhere (*) is based on the Mean Value Theorem. If the high-order term O((∆t) 2 ) is omitted and we short β ∆t = ∆tβ(ξ), for R f = 11 ⊤ -bI, we haveEQUATIONwhich is the transition matrix of the uniform diffusion in the discrete-time diffusion models [67, 2] . Thus, with T → ∞ and q t+∆t|t to the power of infinite, the converged distribution is a uniform distribution. Similarly, for R f = 1m ⊤ f -I the transition matrix isEQUATIONwhich is a generalized transition matrix of the 'absorbing state' diffusion [2] . The difference lies at for the 'absorbing state' diffusion [2] , m f is set as a one-hot vector for the absorbing state, and here we set it as the marginal distribution. Thus, with T → ∞ and q t+∆t|t to the power of infinite, the converged distribution is a marginal distribution m f .C.2 Proof of Theorem 3.3Theorem 3.3 says for G ̸ = Ḡ, Rt (G, Ḡ) -Rθ,t (G, Ḡ) 2 ≤ C t + C node t E G0 q t|0 (G|G 0 ) i L CE (One-Hot(f i 0 ), f i 0 ) + C edge t E G0 q t|0 (G|G 0 ) i,jL CE (One-Hot(e (i,j) 0), ê(i,j)EQUATIONwhere the node and edge estimated probability vector (sum is 1) is notated asEQUATIONEQUATION≤ i A i t f i 0 q t|0 ( f i |f i 0 ) q t|0 (f i |f i 0 ) (q 0|t (f i 0 |G) -p θ 0|t (f i 0 |G)) + i,j B (i,j) t e (i,j) 0 q t|0 (ē (i,j) |e (i,j) 0) q t|0 (e (i,j) |e (i,j) 0) (q 0|t (eEQUATIONWe check the first term of Eq. ( 20):EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhereEQUATION*) is based on the Pinsker's inequality, (**) is based on Cauchy-Schwarz inequality:EQUATIONwhere G0(f i 0 ) marginalizing all the graphs at time 0 whose i-th node is f i 0 ; p 0,t (f i 0 , G) is the joint probability of a graph whose i-th node is f i 0 at time 0 and it is G at time t; p 0,t (G 0 , G) is the joint probability of a graph which is G 0 at time 0 and it is G at time t. Plugging Eq. ( 33) into Eq. ( 26):EQUATIONwhere C 5 = 1 pt(G) . A similar analysis can be conducted about the second term of Eq. ( 20) and we directly present it here: i,j B (i,j) t e (i,j) 0 q t|0 (ē (i,j) |e (i,j) 0 ) q t|0 (e (i,j) |e (i,j) 0) (q 0|t (e (i,j) 0 |G) -p θ 0|t (e (i,j) 0 |G)) ≤C 3 C 4 + C 5 E G0 q t|0 (G|G 0 ) i,jL CE (One-Hot(eEQUATIONwhereC 3 = √ 2n sup i,j {C i,j }, C 4 = i,j e (i,j) 0 C e (i,j) 0 , C i,j = B (i,j) t sup e (i,j) 0 q t|0 (ē (i,j) |e (i,j) 0 ) q t|0 (e (i,j) |e (i,j) 0 ), C e (i,j) 0 = q 0|t (e(i,j) 0 |G) log q 0|t (e (i,j) 0 |G).Plugging Eqs. ( 34) and ( 35) into Eq. ( 20), being aware that C 1 , C 2 , C 3 , C 4 , C 5 are all t-related:Rt (G, Ḡ) -Rθ,t (G, Ḡ) ≤ C 1 C 2 + C 5 E G0 q t|0 (G|G 0 ) i L CE (One-Hot(f i 0 ), f i 0 ) + C 3 C 4 + C 5 E G0 q t|0 (G|G 0 ) i,jL CE (One-Hot(eEQUATION( * )≤ C t + C node t E G0 q t|0 (G|G 0 ) i L CE (One-Hot(f i 0 ), f i 0 ) + C edge t E G0 q t|0 (G|G 0 ) i,jL CE (One-Hot(e (i,j) 0), ê(i,j)EQUATIONwhere (*) is based on Cauchy-Schwarz inequality,C t = 2C 2 1 C 2 + 2C 2 3 C 4 , C node t = 2C 2 1 C 5 , C edge t = 2C 2 3 C 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 isF = {r i } n i=1 ∈ R n×d , E = {r i,j } n i,j=1 ∈ R n×n×d , y ∈ R d, where d is the hidden dimension. The updating formulas of an MPNN layer can be presented asEQUATIONEQUATIONEQUATIONThe permutation P of the input of an MPNN layer can be presented asP F = {r i } n i=1 , E = {r i,j } n i,j=1 , y = {r σ(i) } n i=1 , {r σ(i),σ(j) } n i,j=1, y where σ : {1, . . . , n} → {1, . . . , n} is a bijection.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,EQUATIONBecause j) , and the FiLM module (Eq. ( 71)) is not related to the node ordering, r (σ(i),σ(j)) ← FiLM FiLM(r (σ(i),σ(j)) , r σ(i) ⊙ r σ(j) ), y = FiLM FiLM(r (i,j) , r i ⊙ r j ), y (42)n j=1 r (j,i) = n j=1 r (σ(j),σ(i)) , r i ⊙ r j = r σ(i) ⊙ r σ(EQUATIONEQUATIONThus, we proved thatEQUATIONC.4 Proof of Lemma 3.6Proof. The forward rate matrix (Eq. ( 3)) is the sum of component-specific forward rate matrices ({R(i,j) t } i,j∈N + ≤n and {R i t } i∈N + ≤n). It is permutation-invariant because the summation is permutationinvariant.The parametric reverse rate matrix isEQUATIONwhereRi θ,t (f i , f i ) = A i t f i 0 q t|0 ( f i |f i 0 ) q t|0 (f i |f i 0 ) p θ 0|t (f i 0 |G t ), R(i,j) θ,t (e (i,j) , ē(i,j) ) = B (i,j) t e(i,j) 0 q t|0 (ē (i,j) |e (i,j) 0) q t|0 (e (i,j) |e(i,j) 0 ) p θ 0|t (e (i,j) 0 |G t ).If we present the permutation P on every node Thus, the sampling probability of permuted graph P(G 0 )EQUATIONEQUATIONEQUATIONwhere (*) is based on Lemma 3.6 and Lemma 3.7, the transition probability of DISCO is permutationinvariant and (**) is from the assumption that the reference distribution π ref (G T ) is permutationinvariant. Thus, we proved that for the simple case, Rθ,t fixed ∀t, the sampling probability is permutation-invariant.For the practical sampling, as we mentioned in Section 3.4, the τ -leaping algorithm assumes that the time interval [0, T ] is divided into various length-τ intervals [0, τ ), [τ, 2τ ), . . . , [T -τ, T ] (here both close sets or open sets work) and assume the reverse rate matrix is fixed as Rθ,t within every length-τ interval, such as (t -τ, t]. Thus, the sampling probability can be computed asEQUATION)The conclusion from the simple case can be generalized to this τ -leaping-based case because all the transition probability q t-τ |t (G t-τ |G t ) and the reference distribution are permutation-invariant.Note that Xu et al. [77] have a similar analysis in their Proposition 1 on a DDPM-based model.C.7 Proof of Theorem 3.9Recall our training objective ismin θ T E t∼U (0,T ) E G0 E q t|0 (Gt|G0) i L CE (One-Hot(f i 0 ), f i 0 ) + i,jL CE (One-Hot(e (i,j) 0), ê(i,j)EQUATIONwheref i 0 = [p θ 0|t (f i = 1|G t ), . . . , p θ 0|t (f i = b|G t )] ⊤ ∈ [0, 1] b and ê(i,j) 0 = [p θ 0|t (e (i,j) = 1|G t ), . . . , p θ 0|t (e (i,j) = a + 1|G t )] ⊤ ∈ [0, 1] a+1Proof. We follow the notation and present the permutation P on every node as a bijection σ : {1, . . . , n} → {1, . . . , n}. We first analyze the cross-entropy loss on the nodes for a single training graph G 0 and taking expectation E G0 keeps the permutation invariance:EQUATION= T E t∼U (0,T )EQUATION( * )= T E t∼U (0,T )GtEQUATIONEQUATIONEQUATIONwhere (*) is from the permutation invariance of the forward process and (**) is from the permutation equivariance of the graph-to-graph backbone and the permutation invariance of the cross-entropy loss. A similar result can be analyzed on the cross-entropy loss on the edgesL edge (G 0 ) = T E t∼U (0,T ) E q t|0 (Gt|G0) i,jL CE (One-Hot(e (i,j) 0), ê(i,j)EQUATIONand we omit the proof here for brevity.A Step-by-step procedure about the τ -leaping graph generation is presented in Algorithm 2.Algorithm 2 τ -Leaping Graph Generation 1: t ← T 2: G t = ({e (i,j) } i,j∈N + ≤n , {f i } i∈N + ≤n ) ← π ref (G)3: while t > 0 do 4:for i = 1, . . . , n do 5: for i, j = 1, . . . , n do 11:for s = 1, . . . , b do 6: Ri θ,t (f i , s) = R i t (s, f i ) f i 0 q t|0 (s|f i 0 ) q t|0 (f i |f i 0 ) p θ (f i |G t , t) 7: J f i ,s ← Poisson(τ R i t (s, f i )) ▷ # offor s = 1, . . . , a do▷ # of transition for every edge f i ← s * ▷ update node 22:end ifend forfor i, j = 1, . . . , n doif a s=1 J e (i,j) ,s > 1 or a s=1 J e (i,j) ,s = 0 then 26:e (i,j) ← e (i,j) ▷ stay the same 27: end for 32:t ← t -τ 33: end whileFor learning a better graph-to-graph mapping p θ 0|t (G 0 |G t ), artificially augmenting the node-level features and graph-level features is proved effective to enhance the expressiveness of graph learning models [81, 73] . For this setting, we keep consistent with the state-of-the-art model, DiGress [73] , and extract the following three sets of auxiliary features. Note that the following features are extracted on the noised graph G t .We binarize the edge tensor E into an adjacency matrix A ∈ {0, 1} n×n whose 1 entries denote the corresponding node pair is connected by any type of edge.Motif features. The number of length-3/4/5 cycles every node is included in is counted as the topological node-level features; also, the total number of length-3/4/5/6 cycles is the topological graph-level features.Spectral features. The graph Laplacian is decomposed. The number of connected components and the first 5 non-zero eigenvalues are selected as the spectral graph-level features. An estimated indicator of whether a node is included in the largest connected component and the first 2 eigenvectors of the non-zero eigenvalues are selected as the spectral node-level features.Molecule features. On molecule datasets, the valency of each atom is selected as 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 nodelevel features F aux and graph-level features y. An important property is that the above node-level features are permutation-equivariant and the above graph-level features are permutation-invariant, whose proof is straightforward so we omit it 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,EQUATION)where ⊕ is the concatenation operator, x i ∈ R d ; min, max, mean, and std are coordinate-wise, e.g.,EQUATIONwhere Linear is a single fully-connected layer without activation function and ⊙ is the Hadamard product.F.1 Hardware and SoftwareWe implement DISCO in PyTorch5 and PyTorch-geometric 6 . All the efficiency study results are 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 can be finished in 2 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.The statistics about all the datasets used in this paper are presented in Table 7 , where a is the number of edge types, b is the number of node types, |E| is the number of edges and |F| is the number of nodes.Dataset Split.We follow the settings of SPECTRE [51] and DiGress [73] to split the SBM, Planar [51] , and Community [82] datasets into 64/16/20% for training/validation/test set. Metrics. The Maximum Mean Discrepancy (MMD) [82] measures the discrepancy between two sets of distributions. The relative squared MMD [73] is defined as followsEQUATIONwhere ({G} gen , ({G} train , and ({G} 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 4 nodes). In addition, the Uniqueness, Novelty, and Validity are chosen. Uniqueness reports the fraction of the generated nonisomorphic graphs; Novelty reports the fraction of the generated graphs not isomorphic with any graph from the training set; Validity checks the fraction of the generated graphs following some specific rules. For the SBM dataset, we 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, we only report the Uniqueness, Novelty, and Validity results on the SBM and Planar datasets.We report mean±std in 5 runs.Baseline methods. GraphRNN [82] , GRAN [42] , GG-GAN [37] , MolGAN [9] , SPECTRE [51] , EDP-GNN [56] , GraphGDP [26] , DiscDDPM [22] , EDGE [10] , ConGress [73] , DiGress [73] are chosen.Dataset Split. We follow the split of QM9 from DiGress [73] and follow the split of MOSES [58] and GuacaMol [6] according to their benchmark settings. Their statistics are presented in Table 7 .Metrics. For QM9, Uniqueness, Novelty, and Validity are chosen as metrics. The first two are the same as introduced in Section F.2.2. The Validity is computed by building a molecule with RdKit7 and checking if we can obtain a 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 code8 is used to report the performance.For GuacaMol, the chosen metrics include Uniqueness, Novelty, Validity, KL Divergence, and Frećhet ChemNet Distance (FCD), which is consistent with DiGress [73] . The official evaluation code 9 is used to report the performance.We report mean±std in 5 runs except MOSES and GuacaMol, whose computations are too expensive to repeat multiple times.Baseline methods. CharacterVAE [20] , GrammarVAE [38] , GraphVAE [66] , GT-VAE [55] , Set2GraphVAE [72] , GG-GAN [37] , MolGAN [9] , SPECTRE [51] , GraphNVP [50] , GDSS [32] , [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 [10] 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.5 0.9±0.2 0.9±0.3 DISCO-GT 0.9±0.2 0.9±0.3 1.1±0.4EDGE [10] , ConGress [73] , DiGress [73] , GRAPHARM [36] ,VAE [21] , JT-VAE [29] , GraphIN-VENT [53] , LSTM [64] , NAGVAE [40] , and MCTS [28] are chosen.Forward Diffusion Settings. As we introduced in Proposition 3.2, we tried two sets of rate matrices for the node and edge forward diffusion, so that the converged distribution is either uniform or marginal distribution. We found the marginal distribution leads to better results than the uniform distribution. Thus, the reference distribution is the marginal distribution for all the main results, except Tables 6 and 9 . The performance comparison between the marginal diffusion and uniform diffusion is presented in the ablation study in Sections 4.4 andF.5. The β(t) controls how fast the forward process converges to the reference distribution, which is set as β(t) = αγ t log(γ), which is consistent with many existing works [23, 70, 8] . In our implementation, we assume the converged time T = 1 and for the forward diffusion hyperparameters (α, γ) we tried two sets: (1.0, 5.0) and (0.8, 2.0) where the former one can ensure at 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 p θ 0|t is easier to train.Reverse Sampling Settings. The number of sampling steps is determined by τ , which is round( 1 τ ) if we set the converged time T = 1. We select the number of sampling steps from {50, 100, 500}, which is much smaller the number of sampling steps of DiGress [73] from {500, 1000}. For the number of nodes n in every generated graph, we compute a graph size distribution of the training set by counting the number of graphs for different sizes (and normalize the counting to sum it up to 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 p θ 0|t is graph transformer (GT). We use the exactly same GT architecture as DiGress [73] and adopt their recommended configurations 10 . The reason is that this architecture is not our contribution, and setting the graph-to-graph model p θ 0|t same can ensure a fair comparison between the discrete-time graph diffusion framework (from DiGress) and the continuous-time 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 -4 , and the weight decay is set as 0.Additional Community plain graph dataset results are in Table 8 . Our observation is consistent with the main content: both variants of DISCO are on par with, or even better than the SOTA general graph diffusion generative model, DiGress. Table 9 shows the ablation study of DISCO-MPNN on QM9 dataset. Our observations are 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 is better than the uniform distribution, consistent with the observation from DiGress [73] . The generated graphs on the SBM and Planar datasets are presented in Figure 4 . We clarify that the generated planar graphs are selected to be valid because, as Table 1 shows, not all the generated graphs are valid planar graphs, but the planar layout can only visualize valid planar graphs in our setting 11 . The generated SBM graphs are not selected; even if a part of them cannot pass the strict SBM statistic test (introduced in Section F.2.2 -Metrics), most, if not all, of them still form 2 -5 densely connected clusters.The generation trajectory of SBM graphs is presented in Figure 5 which demonstrates the reverse denoising process visually. In this paper, we study the generation of graphs with categorical node and edge types. The current model DISCO cannot be applied to generate graphs with multiple node/edge features (e.g., multiplex networks) and this is an important future work to study. Also, we view the absence of edge as a special type of edge, which forms a complete graph and promotes the expressiveness of our MPNN backbone model. However, it will lead to quadratic complexity concerning the number of nodes. For our 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. This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.• The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).https://github.com/pricexu/DisCohttps://github.com/cvignac/DiGress/blob/main/README.mdhttps://pytorch.orghttps://pytorch-geometric.readthedocs.io/en/latesthttps://www.rdkit.org/https://github.com/molecularsets/moseshttps://github.com/BenevolentAI/guacamolhttps://github.com/cvignac/DiGress/tree/main/configs/experimenthttps://networkx.org/documentation/stable/reference/generated/networkx.drawing. layout.planar_layout.html 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: questions: **Questions**
- 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?
- Can the proposed architecture be applicable to generate weighted and directed networks?
- The related work section is very brief, possibly due to page limitations but an extended version can be added in the appendix.

**Typos and Errors**
- In Lines 94-95, the set membership symbol should be the subset symbol.
- 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: limitations: The authors addressed the limitations of the model in the appendix.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1.	Some symbols in the formulas of this paper are not clear in the context, which reduces readability
2.	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.
questions: 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: limitations: Yes, the authors addressed limitations, potential negative societal impact, and mitigation.
paper_summary: paper_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.
strength_weakness: strength_weakness: > w1: the proposed seems to be a rather straightforward derivation from the existing tools (replacing discrete markov chain with continuous time)

> w2: no implementation available

> w3:  there is a disconnection between the proposed motivation (sampling motivation) and the (theoretical) discussion of the proposed method (see questions below)

> w4: most theoretical results seem to be a standard derivation from existing literature
questions: 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: limitations: N.A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

[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.

[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.
questions: 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: limitations: I recommend the authors supplement more relevant baselines to enrich the experiments.

Comments: title: Further Discussion
Response to the rebuttal
Thanks for your response
comment: We sincerely thank the reviewer for insightful questions, suggestions, and discussion. We appreciate your recognition of our work and will revise the paper according to the valuable feedback provided!
I thank the authors for their diligent responses. Most of my concerns and questions are addressed and I have raised my score accordingly. 
I will suggest the authors to make further emphasis on the sampling aspect in both the technical and experiment section for revised version, as that is the main the motivation of the paper.
We sincerely appreciate your thoughtful review and are glad to have the opportunity to clarify your questions. Thank you for your recognition of our work!
We sincerely appreciate your thoughtful review and are glad to have the opportunity to clarify your questions. Thank you for your recognition of our work!
Dear Reviewer XoYX,

We appreciate your insightful response and are glad to clarify your concerns. We sincerely invite the reviewer to have further discussions.

> **Q1.** Why can't $\tau$-leaping be used in the discrete model? Can it be applied in other continuous graph generation such as GDSS?

**A1.** We clarify this as follows.

1. **$\tau$-leaping [1-3] is designed for continuous-time discrete-state** stochastic processes (CTMC). It **cannot** be applied to discrete-time models (e.g., Digress [4]) because $\tau$-leaping needs the rate matrices as input, but **discrete-time models do not have rate matrices**.

2. It **cannot** be applied to GDSS because GDSS is a **continuous-state** model, which is not characterized by the rate matrices.

> **Q2.** The result in Table 9 shows that the proposed method is robust to the sampling step and as mentioned in the paper, DIGRESS also has this property. This does not show there is an improvement in sampling efficiency.

**A2.** We would like to answer the reviewer' question from the following perspectives: 

1. Theoretically, Digress cannot have such sampling flexibility. For example, **if the model is trained with 500 forward steps, technically, its reverse process has to include 500 steps**. In other words, for a Digress model trained with 500 forward steps, doing the reverse process in 100 steps is hard to ensure that the generated samples are from the desired generation distribution.

2. Empirically, we have conducted the following experiments to answer the reviewer's question better. We train a Digress model in **500 forward steps** and use it to **do reverse sampling in 500 steps**. We artificially freeze the reverse transition probability in every $\mathrm{round}(500/k)$ steps, where $k$ is the number of inferences. In this way, we have a fair comparison to show the sampling robustness regarding the number of model inferences in Table 1. The metric is validity, and the results of DisCo are shown in Table 4 of our submitted paper. Both DisCo and Digress use the graph Transformer as the backbone and the marginal distribution as the reference distribution. **DisCo is consistently more robust regarding the decrease in the number of inferences. In other words, DisCo has a better quality-efficiency tradeoff.**

| \# of inferences | DisCo | Digress |
|---|---|---|
| 500 | 99.3$\pm$0.6 | 98.9$\pm$0.4 |
| 100 | 98.7$\pm$0.5 | 95.0$\pm$1.1 |
| 30 | 97.9$\pm$1.2 | 92.1$\pm$0.7 |
| 10 | 95.3$\pm$1.9 | 87.9$\pm$0.8 |
| 5 | 93.0$\pm$1.7 | 80.1$\pm$1.4 |
| 1 | 76.1$\pm$2.3 | 67.1$\pm$2.9 |
Table 1. Quality-efficiency tradeoff comparison on QM9

3. In addition, we did not find results from the Digress paper [4] showing that Digress is robust to the step size. If the reviewer could kindly give us a point on related results/statements, we will be happy to check them out.

> **Q3.** As the main motivation for using a continuous Markov model instead of a discrete one is to improve the sampling efficiency, one should expect to see more evaluation and evidence to support and validate that this has been achieved.

**A3.** As we mentioned in the submitted paper, Tables 4 and 9 show that the model's performance is robust when the sampling steps are decreased, achieving a decent generation quality-efficiency tradeoff. Lines 844-846 in the appendix detail the sampling steps used to search for the best results, much smaller than Digress's number of sampling steps. In addition, the results from Table 1 in this response should be supplementary to show the generation efficiency of DisCo, which will be included in the revised paper.

```
Reference:

[1] Campbell, Andrew, et al. "A continuous time framework for discrete denoising models." NeurIPS 2022.

[2] Gillespie, Daniel T. "Approximate accelerated stochastic simulation of chemically reacting systems." The Journal of chemical physics 115.4 (2001): 1716-1733.

[3] Wilkinson, Darren J. Stochastic modelling for systems biology. Chapman and Hall/CRC, 2018

[4] Vignac, Clement, et al. "DiGress: Discrete Denoising diffusion for graph generation." ICLR 2023.
```
Thank the authors for more experiments, and further explanation. I choose to keep my positive score.
Thank you for the diligent response. However, I still found my main concerns not fully addressed.

As the main motivation for using a continuous Markov model instead of a discrete one is to improve the sampling efficiency, one should expect to see more evaluation and evidence to support and validate that this has been achieved. 

In addition, the result in Table 9 shows that the proposed method is robust to the sampling step and as mentioned in the paper, DIGRESS also has this property. This does not show there is an improvement in sampling efficiency.

Q: Why can't $\tau$-leaping be used in the discrete model? Can it be applied in other continuous graph generation such as GDSS?
I appreciate the authors' efforts in addressing the points I’ve indicated, and I increased my score.