DeFoG: Defogging Discrete Flow Matching for Graph Generation

We appreciate the detailed comments and pertinent questions. We address the raised concerns below:

Regarding the novelty concerns of our work, we refer to the points Novelty and Graph-specificity of the general comment for a detailed response. Our work introduces new theoretical results and algorithmic innovations specifically designed for graph generation. We provide new theoretical guarantees for both training and sampling stages, including a direct link between the training loss and rate matrix estimation error, along with an upper bound on the sampling error. Furthermore, we address graph-specific challenges by ensuring DeFoG’s permutation equivariance in a fundamentally different context from the original DFM framework. We also explore under-studied aspects of the sampling process for graph generation, such as stochasticity configurations, and propose novel techniques, including target guidance, to enhance DeFoG’s design space, which are critical for achieving state-of-the-art performance. These contributions highlight DeFoG's suitability as a robust framework for graph generative modeling.

W1: Indeed, the DFM framework, which we build upon, allows us to decouple the training and sampling procedures, a key property for efficiently optimizing the sampling process. However, DFM does not work out of the box for graph generation, as it can be observed for the performance of vanilla DeFoG for the different settings analysed (see, for example, Figs. 2, 6 and 7). Our exploration of DeFoG's design space is crucial for the observed state-of-the-art performance. While components like stochasticity during sampling via $R^\text{DB}$ [6] build on prior work, our key innovations, such as target guidance and sample distortion, significantly improve the performance of the vanilla framework. Overall, we believe that our improvements to DeFoG's design space and its extensive exploration are important new contributions to the community, as illustrated by the state-of-the-art results.

W2: Having a decoupled training and sampling procedure allows for a more efficient exploration and optimization of DeFoG's design space. As mentioned in the Introduction (lines 51-53), this decoupling enables optimization at the sampling stage without requiring re-training, a process that is typically the most computationally expensive. Additionally, this also allows for a larger sampling optimization space, since the rate matrices are no longer implicitly defined at training time. This allows us to explore varying stochasticities and target guidance mechanisms at sampling time, which were not possible in continuous-time discrete diffusion. It is due to these procedures that we obtain better performance with fewer steps, as shown in our experiments.

We highlight in Section 4.2, Exploring DeFoG's Design Space, that this efficient optimization is a significant advantage over existing diffusion-based graph generative models:.

"While discrete diffusion models offer a broader design space compared to one-shot models, including noise schedules and diffusion trajectories (Austin et al., 2021), its exploration is costly. In contrast, flow models enable greater flexibility and efficiency due to their decoupled noising and sampling procedures. For instance, the number of sampling steps and their sizes are not fixed as in discrete-time diffusion (Vignac et al., 2022), and the rate matrix design can be adjusted independently, unlike continuous-time diffusion models (Siraudin et al., 2024; Xu et al., 2024). In this section, we exploit this rich design space and propose key algorithmic improvements to optimize both the training and sampling stages of DeFoG."

To further address the reviewer’s concerns, we have added a new section in the appendix (Appendix A.2) contextualizing the benefits of the decoupled stages in DeFoG, relative to existing diffusion-based graph generative models. In particular, we added a new Section(A.2.3) that provides a detailed discussion of how the full decoupling of sampling from training enhances both efficiency and performance.

We support this theoretical motivation with extensive experimental results. First, the decoupled optimization enables DeFoG to achieve state-of-the-art performance across all evaluated tasks (Tables 1, 2, and 3). Second, Figures 2, 6, and 7 demonstrate the critical role of the sampling optimization pipeline in DeFoG’s performance, where we also included curves for DiGress across all datasets to provide a more comprehensive comparison in the revised version of the manuscript. Specifically, these experiments show that vanilla DeFoG's configuration is insufficient to outperform existing diffusion-based graph generative models, and the proposed modifications are pivotal for achieving state-of-the-art results. Importantly, such extensive exploration would be infeasible for other diffusion-based graph generative models.

Q4: In lines 288-289, we discuss what is a reasonable initial distribution for graphs. This distribution should be permutation invariant, as the order of nodes and edges in a graph is arbitrary. This means that the distribution should have the same probability of yielding any permutation of the same graph. This is a necessary condition to ensure permutation equivariance of the whole model. Therefore, we adopt the proposed formulation:

where $p_\epsilon^\mathcal{X}$ and $p_\epsilon^{\mathcal{E}}$ represent shared distributions across nodes and edges, respectively.

(We changed the notation of $p^n_\epsilon$ to $p_\epsilon^{\mathcal{X}}$ and $p_\epsilon^{ij}$ to $p_\epsilon^{\mathcal{E}}$ to make it clearer that is a shared distribution across nodes and edges, respectively). This formulation is trivially permutation invariant, while sufficiently flexible to allow different prior incorporation strategies, which we explore in the paper. We have updated the main text (lines 290-291) and the proof of Lemma 1 (lines 2372- 2373) to make this connection explicit.

Q5: We are unclear about what is meant by "normalization" here. If it refers to preserving the Kolmogorov equation, we quantify how much deviation is incurred by that component, and there is no need for re-normalization. However, if the question refers to the normalization step $R_t(z_t, z_t) = -\sum_{z_{t+\mathrm{d}t} \neq z_t} R_t(z_t, z_{t+\mathrm{d}t}),$ which ensures $\sum_{z_{t+\mathrm{d}t}} p_{t+\mathrm{d}t|t}(z_{t+\mathrm{d}t} | z_t) = 1$, then note that $R_t(z_t, z_t)$ is computed only at the end. Specifically, it is calculated after summing all the components of $R_t(z_t, z_{t+\mathrm{d}t})$ for $z_{t+\mathrm{d}t} \neq z_t$, including $R^*_t$, $R^\mathrm{DB}_t$, and $R^\omega_t$. So, it is necessarily normalized.

We hope these clarifications address the raised concerns and provide a more comprehensive overview of our work. We have revised our manuscript to better highlight the novelty and contributions of our approach, as well as to clarify notational choices and ensure the accuracy of our framework. We remain at your disposal for any further questions or clarifications.

[1] - Permutation Invariant Graph Generation via Score-Based Generative Modeling, Niu et al., AISTATS 2020

[2] - DiGress: Discrete Denoising Diffusion for Graph Generation, Vignac et al., ICLR 2023

[3] - Variational Flow Matching for Graph Generation, Eijkelboom et al., NeurIPS 2024

[4] - Discrete-state Continuous-time Diffusion for Graph Generation, Xu et al., NeurIPS 2024

[5] - Cometh: A continuous-time discrete-state graph diffusion model, Siraudin et al., ArXiv 2024

[6] - Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design, Campbell et al., ICML 2024

I have read the response and I am not persuaded by the authors regarding Novelty. Specifically,

• The work is essentially the approach first introduced by [1].

  • The authors consider the permutation equivariance and invariance a technical contribution. However, equivariance can be trivially satisfied by the transformer architecture which is well-known and needs no further proof. The authors quote the work of [3] for the proof of invariant property. To conclude, The proof of Lemma 1 can not be regarded as a contribution to this paper.
  • Again, the theoretical guarantees of Theorem 2 in Section 5 do not clearly connect with the main idea of the paper. i.e. what could potentially go wrong with the loss that it need the guarantee of Theorem 2? The authors did not provide a clear explanation. I personally don't like mistifying the paper with unnecessary theoretical guarantees, I didn't go through all the guarantees but at least Lemma 1 seems to be unnecessary, Theorem 2 is mysterious if not completely unnecessary.

• The component RRWP which I believe contributed most of the performance improvement was first adopted to graph generation by [2]. This, in my opinion, can not be considered as an original contribution as well.

The authors have requested for a clarification of the term "logical graph", it indeed is a misused term for "graph". Although I don't think this should be a major source of confusion given this paper is not involved with any other type of data structure, and the response of the authors seems to be in the right context, I apologize for the confusion.

Regarding W5, I am satisfied that the authors have made some changes to the paper, however some more clarification from my side is needed.

• $x^n$ can be easily identified as $x$ to the power of $n$. therefore suggest using $x^{(n)}$ instead.
• At #229, I am well-aware that the authors have contextualized $p_{1|t}^\theta$ as a set. However, $p$ is usually used to represent some scalar probability. The presentation should be improved to avoid confusion, a simple change of the notation is not enough.

Regarding Q4, I am not convinced by the authors' response. initial distribution for graphs, This distribution should be permutation invariant, 1. The distribution for graphs should be defined in the space of graphs, i.e. isomorphic graphs A and B are essentially one datapoint. 2. As an initial distribution to sample from, it is not necessary needed to be permutation invariant.

Regarding Q5, I am convinced by the authors' response, but the authors should put this in the paper, specifically the text right before Eq. 7 (with $z_{t+dt} \neq z_t$), to avoid confusion.

[1] Andrew Campbell, Jason Yim, Regina Barzilay, Tom Rainforth, Tommi Jaakkola. "Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design"

[2] Antoine Siraudin, Fragkiskos D. Malliaros, Christopher Morris. "COMETH: A CONTINUOUS-TIME DISCRETE-STATE GRAPH DIFFUSION MODEL"

[3] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. "Digress: Discrete denoising diffusion for graph generation"

We thank the reviewer for their feedback and for acknowledging the improvements made in the revised version of our manuscript. We address the remaining concerns below.

Regarding the novelty concerns:

• "The work is essentially the approach first introduced by [1]."

  While our work builds upon discrete flow matching, we introduce several key innovations that enable its first successful application to graph generation. These include a novel sampling optimization pipeline (including target guidance, sample distortion...), which are crucial for achieving state-of-the-art performance. Extensive experiments (see Figures 2, 6, and 7) demonstrate that a vanilla adaptation of DFM underperforms in this context, underscoring the necessity of our contributions for adapting DFM to the graph domain.

• Regarding Lemma 1:

  We respectfully clarify that the equivariance of the entire generative framework cannot be reduced to the equivariance of the transformer alone. For instance, the applied loss function (node- and edge-wise cross-entropy) achieves permutation invariance only due to its specific formulation, which takes as input a clean graph and its independently noised version, both with the same node ordering. Consequently, full equivariance arises from the combined effects of multiple components: (1) the equivariance of the denoising graph neural network (transformer), (2) the permutation invariance of the loss function, (3) the permutation equivariance of the RRWP encoding, and (4) the permutation invariance of the sampling probabilities.

  While the first three components rely on results that are either straightforward or adapted from prior work, the proof for the fourth component is unique to our framework. This proof directly stems from the application of the discrete flow matching framework to graph generation. We consider this guarantee a key contribution, as it ensures the theoretical soundness of our model. Its importance is further underscored by the presence of similar guarantees in other diffusion-based graph generative models, as noted in our earlier response. Thus, we believe its formalization meaningfully strengthens our work.

• Regarding Theorem 2:

  Improper alignment between loss functions and objectives is a well-documented issue across various domains. In GANs, misaligned objectives often lead to mode collapse [1], where only a subset of the target distribution is captured. In VAEs, poorly designed losses can result in underexploration of the target distribution [2]. In reinforcement learning, inadequate reward shaping frequently produces suboptimal policies [3].

  Theorem 2 establishes a principled foundation for the use of the cross-entropy loss in our framework by demonstrating its direct connection to minimizing errors in the estimated rate matrix. This connection is pivotal for ensuring accurate sampling in the CTMC-based framework, as further reinforced by Theorem 3.

  Importantly, discrete diffusion models were originally proposed with a loss function incorporating a variational upper bound on the negative log-likelihood. However, when adapted to graphs, this loss was simplified to a node- and edge-wise cross-entropy without formal justification (in DiGress [4]). By rigorously linking the cross-entropy loss to rate matrix estimation, we address this gap, thereby enhancing the theoretical robustness and empirical reliability of DeFoG.

• Regarding RRWP:

  We have included an Appendix section (G.3) that provides detailed results comparing DiGress with and without RRWP encodings. These results demonstrate that, while RRWP encodings offer some benefits, their impact is relatively modest. This is particularly evident in the sampling efficiency analysis (Fig. 18), where DiGress with RRWP encodings exhibits a similar trend to DiGress without them. This indicates that the notable sampling efficiency of DeFoG with fewer steps is primarily driven by our optimized discrete flow matching formulation and sampling pipeline.

  Figures 2, 6, and 7 further corroborate this conclusion, showing that our high performance cannot be solely attributed to the use of RRWP encodings. Additionally, while we acknowledge in the paper that we are not the first to incorporate RRWP encodings into a generative framework, our method achieves superior results. Importantly, we are the first to provide a detailed empirical ablation study on the benefits of RRWP within the generative setting. These results justify that the high performance of our method is not merely a consequence of RRWP encodings, but rather the result of the entire framework.

W5 (Notation): We thank the reviewer for your further suggestions over the notation.

• We have modified the notation of $x^n$ to $x^{(n)}$ in the updated version of the manuscript.

• We believe we have addressed the noted notation ambiguities. Specifically, we have explicitly clarified when $p$ represents a non-scalar, as stated, for example, in lines 171-172: "Since we aim to reverse a $z_1$-conditional noising process $p_{t|1}(\cdot | z_1) \in \Delta^{Z-1}$, DFM instead considers a $z_1$-conditional rate matrix, $R_t(\cdot \, , \cdot|z_1) \in \mathbb{R}^{Z \times Z}$ that generates it."

  We also provide a specific definition for nodes and edges in a graph in lines 229-232 to reinforce this notation. "The denoising of DFM requires a noisy graph $G_t$ as input and predicts the clean marginal probability for each node $x^{(n)}$ via $p_{1|t}^{\theta,(n)} (\cdot|G_t)\in \Delta^{X-1}$ and for each edge $e^{(ij)}$ via $p^{\theta,{(ij)}}_{1|t} (\cdot|G_t)\in \Delta^{E-1}$."

  We believe the notation is consistent, since for all cases where we omit a dimension indicator (superscript $(d)$ or $(n)$) after $p_{1|t}$ in a multidimensional setting, we refer to the full joint variable. If the reviewer has specific additional suggestions, we would be happy to incorporate them.

Q4: Thank you for requesting further clarification. The intention of the sentence is to emphasize that, for any two isomorphic graphs, $G_A$ and $G_B$, the probability of generating $G_A$ is identical to that of generating $G_B$ for any distribution within the defined class of distributions. Regarding your specific concerns:

1. We have revised the phrasing in lines 289-291 of the updated manuscript to eliminate any semantic ambiguity.
2. The initial distribution must generate any permutation of the same graph with equal probability to ensure the permutation invariance of the sampling probabilities of the model, thus crucial for Lemma 1 (detailed in lines 2373-2374). Additionally, this formulation allows for likelihood computation of our model, via exchangeability (see Lemma 3.3 of [4]). We do not explore this aspect in the current work, but it leaves the door open for future research.

Q5: We have integrated the suggested modification into the updated version of the manuscript.

As a final remark, we would like to emphasize that our framework achieves state-of-the-art performance and comparable performance with previous diffusion-based models with significantly fewer steps (5%). In our view, these results solidify our framework as a substantial and innovative contribution to the field.

We believe that the constructive feedback provided by the reviewer has guided us toward addressing their concerns more effectively. In light of these improvements, we hope the reviewer might consider revising their score.

[1] - Wasserstein GAN, Arjovsky et al., ICML 2017

[2] - Generating Sentences from a Continuous Space, Bowman et al., CoNLL 2015

[3] - Policy invariance under reward transformations: Theory and application to reward shaping, Ng et al., ICML 1999

[4] - DiGress: Discrete Denoising Diffusion for Graph Generation, Vignac et al., ICLR 2023

We sincerely appreciate the reviewer’s constructive feedback and requests for clarification. We have addressed the raised questions below:

W1: We believe that our work offers substantial advances beyond existing frameworks in both theoretical insights and performance. Furthermore, our experiments emphasize that while DFM is not directly tailored for graph generation, it holds significant potential due to its flexible exploration space. Our comprehensive investigation into DeFoG's design space has been instrumental in realizing the observed state-of-the-art performance. For additional details, please refer to the "Novelty" section in the general comments. In summary, we present the first method to enable systematic, effective, and extensively studied sampling optimization, which our experiments demonstrate as crucial for achieving state-of-the-art performance.

W2: We thank the reviewer for the suggestion. Unfortunately, due to the author guidelines for the rebuttal, we are constrained by space limitations in the main text. Nevertheless, to address the reviewer's concern we have added a new section in the appendix (Appendix A) that provides a more comprehensive and detailed overview of the related research methods. There, we introduce the several compared methods and provide a detailed and compact contextualization of DeFoG within the diffusion-based graph generative models landscape. We hope this provides a more detailed context for our work, but we remain open to further suggestions in case we missed any relevant work.

Q1: Again, we thank the reviewer for the suggestion and we included a more comprehensive study about RRWP in Appendix G.3 in response. Please refer to the point Isolate Effect of RRWP of the general comment for the results of the ablation study comparing DiGress with the RRWP encoding.

Q2: DiGress was initially excluded from Figures 6b, 6c, 7b, and 7c because Figures 6a and 7a were intended as illustrative examples for synthetic and molecular datasets, rather than exhaustive coverage. Additionally, the original code repository did not provide checkpoints for these datasets. However, we have now run the code and obtained the required checkpoints ourselves. The updated results, included in the revised version of our PDF, confirm that DeFoG outperforms DiGress in both efficiency and performance, while maintaining consistent trends across datasets.

We hope these clarifications address the raised concerns and provide a more comprehensive overview of our work. We remain at your disposal for any further questions or clarifications.

We appreciate the reviewer's feedback and the acknowledgement of our extensive exploration of DeFoG's design space. We address the raised concerns below:

W1: To address concerns regarding innovation, we kindly refer the reviewer to our general comments on Novelty, where we provide a detailed explanation of how DeFoG addresses critical gaps in the graph generation research community.

Regarding the comparison with previous diffusion-based graph models, we believe this has been addressed in multiple sections of the paper. Below, we highlight key points from our work. Nevertheless, to make this comparison more compact and detailed, we added a new section to the appendix highlighting the advantages of DeFoG vs previous continuous diffusion models (see Appendix A.2).

We first remark in the Introduction:

"However, the sampling processes of these methods [referring to previous graph diffusion models] remain highly constrained due to a strong interdependence with training: design choices made during training mostly determine the options available during sampling. Therefore, optimizing parameters such as noise schedules requires re-training, which incurs significant computational costs." and "Specifically, its [referring to DFM formulation] noising process involves a linear interpolation in the probability space between noisy and clean data, displaying well-established advantages for continuous state spaces in terms of performance (Esser et al., 2024; Lipman et al.) and theoretical properties (Liu et al., 2023). Most notably, the denoising process in DFM uses an adaptable sampling step scheme (both in size and number) and CTMC rate matrices that are independent of the training setup. Such a decoupling allows for the design of sampling algorithms that are disentangled from training, enabling efficient performance optimization at the sampling stage without extensive retraining. However, despite its promising results, the applicability of DFM to graph generation remains unclear, and the proper exploitation of its additional training-sampling flexibility is still an open question in graph settings". 

In the following paragraphs of the Introduction, we ellaborate on how to successfully apply DFM to graph generation, yielding DeFoG. Then, in the "Graph Diffusion" paragraph of the Related Work section:

"One of the initial research directions in graph diffusion sought to adapt continuous diffusion frameworks for graph-structured data (Niu et al., 2020; Jo et al., 2022; 2024), which introduced challenges in preserving the inherent discreteness of graphs. In response, discrete diffusion models (Austin et al., 2021) were effectively extended to the graph domain (Vignac et al., 2022; Haefeli et al.), utilizing Discrete-Time Markov Chains to model the stochastic diffusion process. However, this method restricts sampling to the discrete time points used during training. To address this limitation, continuous-time discrete diffusion models incorporating CTMCs have emerged (Campbell et al., 2022), and have been recently applied to graph generation (Siraudin et al., 2024; Xu et al., 2024). Despite employing a continuous-time framework, their sampling optimization space remains limited by training dependent design choices, such as fixed rate matrices, which hinders further performance gains."

In the next paragraph of the same section, "Discrete flow Matching", we provide more details in the comparison to continuous-time diffusion models:

"This DFM approach theoretically streamlines its diffusion counterpart by employing linear interpolation for the mapping from data to the prior distribution. Moreover, its CTMC-based denoising process accommodates a broader range of rate matrices, which need not be fixed during training. In practice, DFM consistently outperforms traditional discrete diffusion models. In this paper, we build on the foundations of DFM with the aim of further advancing graph generative models."

Later, in section "Exploring DeFoG's Design Space" (4.2), we reiterate:

"While discrete diffusion models offer a broader design space compared to one-shot models, including noise schedules and diffusion trajectories (Austin et al., 2021), its exploration is costly. In contrast, flow models enable greater flexibility and efficiency due to their decoupled noising and sampling procedures. For instance, the number of sampling steps and their sizes are not fixed as in discrete-time diffusion (Vignac et al., 2022), and the rate matrix design can be adjusted independently, unlike continuous-time diffusion models (Siraudin et al., 2024; Xu et al., 2024). In this section, we exploit this rich design space and propose key algorithmic improvements to optimize both the training and sampling stages of DeFoG."

Q1: The exact computation of the expectation requires evaluating a weighted sum over possible rate matrices:

$E_{p_{{1|t}}^{\theta,d} (z_1^d | z_t^{1:D})} [ R_t^d(z_t^d, z_{t + \Delta t}^d | z_1^d)] = \sum_{z_1^d} p_{1|t}^{\theta,d} (z_1^d | z_t^{1:D}) R^d_t(z_t^d, z_{t + \Delta t}^d | z_1^d)$

This involves a sweep over the possible states of $z_1^d$. For graphs, this corresponds to a full sweep over possible node and edge states per each denoising step. However, since one forward pass of the denoising neural network computes $p_{1|t}^{\theta,d}$ for all $z^d_1$, the exact expectation does not require additional network calls.

In our experiments, the cardinalities of the node ($X$) and edge ($E$) state spaces are relatively small:

• Synthetic datasets: $X=1$, $E=2$;
• Molecular datasets: $X=4$, $E=5$;
• Digital Pathology datasets: $X=2$, $E=9$.

The table below summarizes the runtimes (mean ± std over 5 runs) for representative datasets:

These results show that the computational overhead of the exact expectation in our setting is minimal. Importantly, as anticipated, the overhead increases with the cardinalities of the state spaces.

We hope these clarifications address the raised concerns and provide a more comprehensive overview of our work. We remain at your disposal for any further questions or clarifications.

[1] - DiGress: Discrete Denoising Diffusion for Graph Generation, Vignac et al., ICLR 2023

We thank the reviewer for their insightful feedback. We address each point below:

W1: Please refer to the points "Graph-specificity" and "Novelty" of the general comment.

W2: We thank the reviewer for the suggestion regarding the RRWP encodings. We included a more comprehensive study about RRWP in Appendix G.3. Please refer to the point Isolate Effect of RRWP of the general comment.

W3: We thank the reviewer for the pointers. We have evaluated both CatFlow and GruM with our evaluation pipeline and have added them to our related work discussion (see section Related Work and Appendix A).

• GruM: for synthetic datasets, we used directly the generated graphs by GruM (readily available in the official repository) and evaluated them with our pipeline. For the molecular dataset (QM9), the generated smiles provided result from a posteriori correction, which would lead to an unfair comparison. Therefore, we re-sampled the graphs using the provided GruM sampling codes and checkpoints, and, again, passed these graphs through our molecular evaluation pipeline. In particular, unlike the original paper, we report strict validity rather than the relaxed version to maintain consistency across our results on the QM9 dataset.
  Discussion: DeFoG demonstrates improved performance over GruM on the Planar and SBM datasets, with the exception of the average ratio metric on SBM. On the QM9 dataset, both methods have comparable performance. However, while not in our original tables, we remark that the novelty score of DeFoG is 33.2% compared to GruM's 25.2%. This suggests that GruM is more prone to overfitting to the training dataset, while DeFoG generates more diverse molecular structures. (Note: these low values of novelty for highly performant graph generative models in QM9 are not unusual, since this dataset consists of an exhaustive enumeration of the small molecules complying with a given set of constraints [1]).

• CatFlow: However, we are not able to compute the average ratio metric, nor to run our molecular evaluation with the information available. Unfortunately, we were unable to find any official implementation of the proposed method. The code submitted as supplementary material in OpenReview seems to be a preliminary version (has no README, we could not reproduce the environment, ...), which does not allow us to provide a fair comparison. We tried to reach out to the authors, but we did not receive any response. If this status changes during the rebuttal period, we will update our results accordingly.
  Discussion: For synthetic datasets, we use the V.U.N. values reported in their paper: 80.0 and 85.0 for Planar and SBM, respectively. DeFoG outperforms CatFlow on both datasets.

Dear Reviewer,

As we approach the end of the rebuttal period, we wanted to check if our responses have addressed your concerns or if there are any remaining points we could clarify.

Best regards,

The authors

Graph-specificity: DeFoG is specifically tailored to the graph generation domain. First, we address key challenges in graph-specific modeling, ensuring that the full framework achieves permutation equivariance — a scenario radically different from the one originally considered in DFM [5]. We manage to overcome GNN architectural expressivity limitations by incorporating graph transformers and RRWP encodings. In particular, we provide new results evaluating the time complexity and efficacy of these encodings in graph generation performance and sampling efficiency (see Isolate Effect of RRWP). Additionally, we adopt a differentially weighted loss function for nodes and edges, which enforces a differential bias during training justified by their distinct roles in the graph structure.

Furthermore, we explore a class of initial distributions of the noising process, $p_\epsilon$, that maintain DeFoG's permutation equivariance. Our aim is to identify which distributions provide better inductive biases for graph generation tasks, connecting our findings to existing results in the graph generation literature. We also offer insights specific to graph generation, such as identifying the types of time distortions that enhance generation quality for different datasets. These findings reveal significant differences from other data modalities, e.g.:

"In contrast to prior findings in image generation, which suggest that focusing on intermediate time regions is preferable (Esser et al., 2024), we observe that for most graph generation tasks, the best-performing distortion functions particularly emphasize $t$ approaching 1. Our key insight is that, as $t$ approaches 1, discrete structures undergo abrupt transitions between states — from 0 to 1 in a one-hot encoding — rather than the smooth, continuous refinements seen in continuous domains. Therefore, later time steps are critical for detecting errors, such as edges breaking planarity or atoms violating molecular valency rules."

Finally, DeFoG's decoupling of training and sampling enables flexible sampling procedures that previous diffusion-based graph generative models did not offer. This flexibility allows us, for the first time to the best of our knowledge, to explore varying stochasticity configurations ($R^\mathrm{DB}$) at sampling time specifically for graph settings. Additionally, we propose a target guidance mechanism ($R^\omega$), which is crucial to DeFoG's success in graph generation tasks. While some building blocks (e.g., target guidance) may not be exclusively applicable to graphs, their adaptability to other domains highlights the distinct strength of our method. Nevertheless, all our contributions are designed for, developed, and validated on graph data.