Discrete-state Continuous-time Diffusion for Graph Generation

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.

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.

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.

Meanwhile, following reviewer's suggestion, we have included more baseline methods' reported performance as follows:

1. We include results of Digress and our method DisCo from our submitted paper for comparison.

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

3. We report more results on the Community dataset in Table 1 below, whose metrics are MMD ratios $\textrm{MMD}^2(\{\mathcal{G}\}\_{`gen`}||\{\mathcal{G}\}\_{`test`})/\textrm{MMD}^2(\{\mathcal{G}\}\_{`train`}||\{\mathcal{G}\}\_{`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.

4. We report more results on the QM9 dataset in Table 2 below, which also shows that DisCo performs comparably against SOTA models.

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?

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.

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

Reference:

[1] Vignac, Clement, et al. "DiGress: Discrete Denoising diffusion for graph generation." ICLR 2023.

[2] Liu, Jenny, et al. "Graph normalizing flows." NeurIPS 2019.

[3] Niu, Chenhao, et al. "Permutation invariant graph generation via score-based generative modeling." AISTATS 2020.

[4] Huang, Han, et al. "Graphgdp: Generative diffusion processes for permutation invariant graph generation." ICDM 2022.

[5] Jo, Jaehyeong, Seul Lee, and Sung Ju Hwang. "Score-based generative modeling of graphs via the system of stochastic differential equations." ICML 2022.

[6] Haefeli, Kilian Konstantin, et al. "Diffusion Models for Graphs Benefit From Discrete State Spaces." NeurIPS 2022 GLFrontiers Workshop.

[7] Chen, Xiaohui, et al. "Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling." ICML 2023.

[8] Fu, Xingcheng, et al. "Hyperbolic Geometric Latent Diffusion Model for Graph Generation." ICML 2024.

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.

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.

A1. Although there have been prior works (e.g., [1]) on CTMC-based diffusion models, we make the following new contributions:

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

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

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

We will revise this paper's introduction to highlight our unique contributions better.

Q2. no implementation available

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.

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?

A3. Thanks for raising this question to improve the presentation of this paper. We clarify your concerns from the following three perspectives:

1. 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).

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

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

We will highlight the connection between the motivation and the proposed method in revised versions.

Reference:

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

[2] Vignac, Clement, et al. "DiGress: Discrete Denoising diffusion for graph generation." ICLR 2023.

[3] Austin, Jacob, et al. "Structured denoising diffusion models in discrete state-spaces." NeurIPS 2021.

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.

Q1. Some symbols in the formulas of this paper are not clear in the context, which reduces readability

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.

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.

A2. Although there have been prior works (e.g., [1]) on CTMC-based diffusion models, we make the following new contributions:

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

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

We will revise this paper's introduction to highlight our unique contributions better.

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?

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.

Reference:

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

[2] Vignac, Clement, et al. "DiGress: Discrete Denoising diffusion for graph generation." ICLR 2023.

[3] Austin, Jacob, et al. "Structured denoising diffusion models in discrete state-spaces." NeurIPS 2021.

[4] Zhang, Qinsheng, and Yongxin Chen. "Fast Sampling of Diffusion Models with Exponential Integrator." ICLR 2023.

[5] Song, Yang, et al. "Score-Based Generative Modeling through Stochastic Differential Equations." ICLR 2021.

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.

Q1. Baseline methods, e.g., GraphINVENT and DiGress, show comparable or better performance in some metrics and datasets.

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.

Q2. The paper adapts a previous CTMC-based diffusion model for the graph domain. It doesn’t present substantial novel material.

A2. Although there have been prior works (e.g., [1]) on CTMC-based diffusion models, we make the following new contributions:

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

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

We will revise this paper's introduction to highlight our unique contributions better.

Q3. Metrics are different in Tables 2 and 6-8, and some tables lack error terms.

A3. We appreciate this suggestion and are eager to enhance this paper's clarity. We clarify your concern regarding metrics and error terms:

1. To make a fair comparison, we keep the metrics consistent with Digress [2], a published SOTA solution.

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

3. Error terms for MOSES and GuacaMol are not included because their computations are too expensive for multiple runs (lines 825-826 in the Appendix).

Q4. Can the proposed architecture be applicable to weighted and directed networks?

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.

Q5. An extended related work section can be added.

A5. We appreciate this great suggestion and will provide a more comprehensive related work section in the revised version.

Q6. In Lines 94-95, the set membership symbol should be the subset symbol.

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.

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?

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$, ..."

Reference:

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

[2] Vignac, Clement, et al. "DiGress: Discrete Denoising diffusion for graph generation." ICLR 2023.

[3] Austin, Jacob, et al. "Structured denoising diffusion models in discrete state-spaces." NeurIPS 2021.

[4] Polykovskiy, Daniil, et al. "Molecular sets (MOSES): a benchmarking platform for molecular generation models." Frontiers in pharmacology 2020.

[5] Brown, Nathan, et al. "GuacaMol: benchmarking models for de novo molecular design." Journal of chemical information and modeling 2019.

[6] Razavi, Ali, et al. "Generating diverse high-fidelity images with vq-vae-2." NeurIPS 2019.

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!