Cometh: A continuous-time discrete-state graph diffusion model

We thank you for reviewing our work, and provide answers to your concerns below.

The proposed framework mainly combines existing techniques, such as continuous-time Markov chains (CTMC) with marginal transitions and random-walk encoding. While our work builds largely on Campbell et al. (2022), Vignac et al. (2022), and Ma et al. (2023), we emphasize that the extensions were far from straightforward. For example, the marginal transition could not be directly extended from Campbell et al. (2022), requiring us to derive Proposition 1 to enable the use of arbitrary target distributions and to design a new noise schedule. Regarding the random-walk encoding, this is its first application in a generative setting, as well as the first instance of using a graph positional encoding with provable expressivity in graph diffusion models.

There is a lack of comparison with continuous diffusion models on large-scale datasets like MOSES and GuacaMol. There is not a single continuous-state graph diffusion model; GruM is one example of such an approach. To the best of our knowledge, no such models have been evaluated on MOSES and GuacaMol, and performing such computationally expensive evaluations falls outside the scope of our paper. The MOSES and GuacaMol benchmarks include their own set of baselines. Our objective in conducting these experiments was to highlight two key points:

• Performance Comparison: Cometh outperforms its discrete-time counterpart.
• Benchmark Integration: Cometh further bridges the gap between graph diffusion models and the leading baselines on these datasets.

Although Appendix D demonstrates COMETH's performance with fewer steps, the training and sampling times of related works are not compared. We acknowledge that we could add the time requirements of our models and some time comparisons with DiGress. We will add this in a future revised version.

If you are satisfied with our responses, please consider adjusting your score. We are happy to answer any remaining questions. Thank you.

We would like to thank for taking the time to write such a detailed review and for your insightful feebacks. We

Limited technical novelty in adapting the continuous-time framework Although we agree that we build on tools from Campbell et al. 2022, we would like to highlight that the extension of marginal transitions does not trivially derive from their formulation. Indeed, the link between the chosen rate matrix and the prior distribution was not explicitly established. In that regard, the result established in Proposition 1 allow for using any target distribution and open the design space of possible noise schedules. Hence, would like to argue that our contribution is not just a simple extension of Campbell et al. 2022.

Additionally, we believe our experimental results prove the superiority of Cometh over its discrete time counterpart, DiGress, in terms of performance.

Insufficient justification for loss function choice We acknowledge the fact that using direct model supervision with the cross-entropy requires more theoretical justifications. Campbell et al. 2022 provide some insights concerning direct model supervision in the appendix of their paper, by proving that the ideal denoiser of their framework minimizes the cross-entropy loss. They also prove that in discrete time, minimizing the cross-entropy loss amounts to minimizing an upper bound on the ELBO, i.e., a looser bound on the NNL than the ELBO. Though they don’t provide the same result in continuous time, this is another theoretical hint that indicates why CE can be a good candidate for loss function.

Also, in the revised version of the manuscript, we will provide results using the ELBO as a loss function to justify our claim better.

Discussion of the noise schedule is misleading We apologize for this misunderstanding and will rewrite this paragraph to better reflect the true nature of our contribution. Additionally, we will perform an ablation study to compare our cosine schedule against the exponential schedule

Proposition 1 is an adaptation of DiGress[1]'s forward process formulation We are afraid this is a misunderstanding. Proposition 1 is derived from the expression of the forward process formulated in Campbell et al, 2022. It is however true that the resulting expression resembles the forward process of discrete-time models.

Also, the proof is indeed rather simple, but we believe that this result, which was not explicitly derived in Campbell et al. 2022, is fundamental to easily understanding the interplay between the choice of rate matrix, the noise schedule, and the behavior of the forward process. The formulation of the forward process in Campbell et al. 2022 did not allow for an easy derivation of the expression of p(z^T), and the behavior of the forward process was hardly interpretable. Conversely, Proposition 1 provides a clear interpretability of the role of each component in the forward process and allows us to easily design each of them separately.

The properties of the random walk encoding follow directly from Ma et al. (2023) We recognize that the results are a relatively straightforward extension of Ma et al. (2023). However, we find them noteworthy, especially given the newly identified limitation of RRWP. Taken together, these findings illustrate why RRWP can effectively replace most of DiGress’s structural features. Moreover, positional encoding is a well-explored topic in graph learning, and our work serves to align graph diffusion models with discriminative models in this context.

Absence of code/implementation We will provide the code and a checkpoint so that you reviewers can reproduce our results.

Can you expand on your noise schedule choice related to graph diffusion in continuous time in particular? Our choice of noise schedule was simply made to match older heuristics of discrete time diffusion models. We also demonstrate with Proposition 1 how any noise schedule converging towards 1 when t is close to 1 can be used. We therefore open the design space of noise schedules for discrete diffusion models and showcasts this using the cosine schedule.

Could you elaborate on why the random walk encoding is a better choice than other encodings (e.g. Laplacian)? The main advantage of RRWP is that it allows it to encompass most auxiliary features used in DiGress – namely the cycles and connected components features – but using only one, easily computed encoding.

Some Laplacian features are also used in DiGress.Although RRWP does not directly encompass those features, the RWSE component within RRWP, as explained in line 311, serves as an effective alternative to them. In fact, RWSE is a commonly used node-level encoding, which has performed on par with Laplacian encodings in various graph learning settings (​e.g. Rampasek et al., 2022).

Thank you for taking the time to write a detailed rebuttal. I am afraid I cannot change my score before the changes and results requested are provided.

In the meantime, I have some follow-ups to the authors' response:

• Proposition 1 being derived from Campbell et al. (2022): Thank you for clarifying this point. While the derivation proposed in the proposition allows for interpretability, I believe the proposition itself still constitutes a minor technical contribution within the framework of continuous time diffusion.

• RRWP and replacing DiGress's features: the ability to obtain multiple features from a single encoding is indeed interesting to note, but as pointed out in my initial review, reaching this observation does not require novel technical contributions on top of the work of Ma et al. 2023. The limitations of RRWP similarly build on established results in the literature. Therefore, I maintain that this is not a substantial contribution of COMETH.

We thank you for you constructive feedback. Below, we address your concern and answer your questions about our work.

the contribution of the proposed extension for marginal transition seems minor, and its impact on improving graph generation remains unclear. Using marginal transitions with a marginal prior distribution is standard in graph diffusion models (Vignac et al. 2022, Qin et al. 2023), as we elaborate in l.202. The marginal prior is optimal within our chosen distribution space, being the closest product-form distribution to the data distribution. This avoids issues like the uniform prior, which would result in overly dense graphs (e.g., a density of 0.5 for Planar compared to its actual 0.9). While we rely on tools from Campbell et al. 2022, the extension of marginal transitions is non-trivial, as the link between the rate matrix and the prior was not explicitly established, making our contribution more than a straightforward extension.

To better highlight the importance of extending marginal transitions to continuous time, we will provide an ablation study to demonstrate how the marginal transitions improve over uniform transitions.

the lack of an ablation study makes it difficult to determine the extent to which each component contributes We acknowledge that assessing the respective contributions of the continuous-time framework and the RRWP encoding requires an ablation study. We will add the ablation in a revised version.

why is the discrete-time sampling scheme referred to as ancestral sampling The term ancestral sampling refers to how discrete-time diffusion models are sampled from and was introduced by Song et al. 2021. The important point here is that discrete-time models use a discrete time scale, which is fixed during training, and that allows for only one sampling scheme. Continuous-time models, however, leave the discretization of the time axis to the sampling stage, and offer the possibility to choose any CTMC simulation tool to simulate the reverse process

How does the continuous-time Markov chain (CTMC) version of discrete-state marginal transition diffusion aid in graph generation? The first motivation for lifting discrete graph diffusion models to continuous time is that this has proven to be beneficial in terms of performance in several fields, e.g., images (Song et al, 2021) and text (Lou, 2024). Empirically, we also found that using a continuous-time approach is beneficial for graph generation. Another motivation for lifting graph diffusion models to continuous time is the flexibility it provides in terms of sampling methods. Several of them have been used to sample from continuous-time discrete diffusion models (e.g. Euler, tau-leaping). The design space for such methods is still open, and we believe that our work will open the way to creating innovative sampling schemes for graph diffusion models.

why is the difference between nodes and edges considered a challenge when the treatment appears to be the same throughout the paper? The difference in treatment lies in the rate matrices and their associated prior distributions. Since edges and nodes do not have the same set of attributes or support, their corresponding rate matrices have different dimensionality, and so do the probability vectors of their corresponding prior distribution. This differs from, e.g., text data, for which the same rate matrix can be used for every token.

The model performs well on QM9 but not as well on the other two molecular datasets. We believe this is a misinterpretation of the results on MOSES and GuacaMol. If QM9 is now more a sanity check than a real benchmark, MOSES and GuacaMol are still challenging datasets for general purpose graph generation models. If you compare Cometh's results to those obtained by DiGress, you’ll see a neat improvement in performance, especially on GuacaMol. Consequently, Cometh outperforms its discrete-time counterpart and performs very well as a graph generation model. We believe your question comes from the comparison to other baselines. Excluding DiGress, all other baselines are trained using domain-specific knowledge (e.g., process SMILES strings), which gives them a clear advantage over general-purpose graph diffusion models. We’d like to highlight the fact that Cometh is the first general-purpose graph diffusion model that obtains near-SOTA performance on GuacaMol, being only outperformed in terms of FCD by the LSTM model.

If you are satisfied with our responses, please consider adjusting your score. Thank you.

We thank the reviewer for the questions and the valuable suggestions to improve the clarity of our work.

there is a concurrent work, [R1] (Xu et al., 2024) We acknowledge that concurrent work was released at approximately the same time as ours. We will mention them in a revised version of the manuscript and add them to the baselines. Here, we offer a concise comparison with their work :

• On MOSES, Cometh performs on par with Disco, our competitor’s model. Disco slightly outperforms Cometh regarding VUN, but Cometh obtains better results on all the other metrics.
• On GuacaMol, Cometh outperforms Disco by a large margin on all the metrics.
• The results are more contrasted on the synthetic datasets. Disco obtains better results on the distribution metrics (Degree, Clustering, Orbit, and Spectrum), but Cometh obtains much better results regarding Valid, Unique, and Novel samples. Note that the distribution metrics are calculated on all the generated graphs, not only the Valid, Unique, and Novel ones. Therefore, it seems that our superior performance on the VUN metric comes at the cost of a slightly worse ability to retrieve the graph statistics and vice versa.

Generally speaking, we believe that our work provides more significant contributions than Xu et al, 2024 in the sense that their work consists mostly of an extension of DiGress to continuous time. That is, their major contribution is to propose to use of an MPNN rather than a GT as backbone, but that approach yields quite poor experimental results. On the other hand, we successfully leverage the RRWP encoding and the predictor-corrector mechanism and propose a conditional generation experiment.

The writing and organization of this paper need improvement. We acknowledge the fact that we refer several times to Vignac et al. (2022) and Campbell et al. (2022) because Cometh relies a lot on the concepts introduced in those two articles. In the final version, we will highlight our contributions better. We also provided a complete description of Campbell et al. 2022 in the Appendix. Note that an overview of our model is provided in Figure 1.

Some experimental results lack sufficient interpretation. As these are quite complicated architectures, like any deep learning architecture, it is hard to interpret the results for each metric individually. As you can see, DiGress performs better on Degree and Orbit but much worse on Cluster. Overall, we believe that Cometh obtains a much stronger performance than DiGress since we obtain a much better performance on the VUN metric and a competitive performance on most distribution metrics.

What is the reason for choosing the marginal distribution? Using marginal transitions along with a marginal prior distribution is a well-established standard in the graph diffusion model literature (Vignac et al. 2022, Qin et al. 2023). We elaborate on this in l 202. To provide further clarification on that matter, the marginal prior distribution is optimal within the space of distributions we are seeking to use, i.e. a distribution that is the product of the same distribution for the n nodes and the n(n-1)/2 edges. This is the closest distribution of that form from the data distribution. A major flaw of the uniform distribution in the case of graphs is that G^{T} would be much denser than the graphs of the data distribution, e.g., for Planar, it would yield graphs of density 0.5 while the average density of this distribution is close to 0.9. Therefore, the model would first need to retrieve this sparsity before fine-tuning the graph structure.

The computational resources and time requirements are not reported in the submission. Computation resources are listed in Appendix C5. We will add the time requirements in a revised version.

If you are satisfied with our responses, please consider adjusting your score. Thank you.