DeFoG: Discrete Flow Matching for Graph Generation

We thank the reviewer for their thoughtful feedback. Below, we address the raised concerns in detail.

Essential Reference: We thank the reviewer for proposing this interesting reference. We will expand our related work section to include a discussion over methods that support both continuous and discrete data. Specifically, we propose to integrate the following in the revised manuscript:

Integrating continuous and categorical data within graph generative models is an important challenge, as many real-world applications involve heterogeneous data types (e.g., molecular graphs containing atomic coordinates alongside categorical atom and bond types). A recent example addressing this challenge is GBD [1], which incorporates beta diffusion to jointly model both continuous and discrete variables. Similarly, DeFoG is amenable to formulations involving mixed data types by leveraging an approach akin to MiDi [2], independently factorizing continuous and discrete variables. However, explicitly exploring this integration is beyond the scope of this work.

Results on ZINC250 dataset: To further support our empirical findings on real-world datasets, we provide results on the ZINC250k. We evaluate DeFoG’s performance on this dataset after 14 hours of training under the same setting of previous works [3] and compare it, to the best of our knowledge, against the strongest-performing methods currently reported in the literature [1,3,4].

DeFoG accomplishes state-of-the-art performance for this dataset. Notably, it also attains superior FCD performance using only 50 sampling steps, outperforming existing methods. We thank the reviewer for suggesting the ZINC250k benchmark. These results further demonstrate DeFoG’s generalization capabilities in molecular graph modeling, strengthening our contribution, and, thus, have been included into the updated manuscript.

Standard Deviation for Synthetic Graphs In the Experiments section, we report VUN and the average ratio of MMDs for all the synthetic datasets, with both mean and standard deviation (std). We can observe DeFoG’s stable performance, in particular for a large number of steps. Additionally, we provide the full results for all the original graph-specific metrics, including Degree, Orbit, Wavelet, Spectral, and Cluster MMDs, with mean and std, in Table 7.

Sampling Distortion The original DFM paper [6] considers evenly spaced sampling timesteps without any distortion. In contrast, we investigate how breaking this uniformity can yield more refined generative trajectories, especially at timesteps crucial for capturing specific graph properties. Our results (Sec. 5.3 – Sampling Distortion) demonstrate that, for graphs with strict structural constraints (e.g., planarity), it is beneficial to emphasize refinement at later steps, as categorical variables may abruptly transition as $t \rightarrow 1$, potentially violating the required structure. Refining these late steps thus helps detect and correct such errors. Conversely, for datasets without strict constraints (e.g., SBM), this refinement is not necessary. Moreover, we provide insights into the interplay between training and sampling distortions, observing that aligning these distortions typically yields the best generative performance, although this is not universally true. We also propose a simple heuristic to determine the optimal sampling distortion (see App C.2.). Finally, similar beneficial effects of distorted scheduling have been reported for other data modalities, such as image generation and language modeling [6].

Overall, sampling distortion allows us to exploit DeFoG's training-sampling decoupling to further enhance generative performance by adapting the generative process to different graph characteristics, refining the corresponding crucial timesteps.

[1] - Advancing Graph Generation through Beta Diffusion, Liu et al., ICLR 2025

[2] - Midi: Mixed graph and 3d denoising diffusion for molecule generation, Vignac et al., ECML-PKDD 2023

[3] - Graph Generation with Diffusion Mixture, Jo et al., ICML 2024

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

[5] - Digress: Discrete denoising diffusion for graph generation, Vignac et al., ICLR 2023

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

[7] - Discrete Flow Matching, Gat et al., NeurIPS 2024

We thank the reviewer for positively assessing our framework’s novelty, theoretical grounding, and empirical results. Below, we address the raised concerns:

I - Methods And Evaluation Criteria:

1. Hyperparameters sensitivity: In the paper, we perform extensive hyperparameter sensitivity analyses covering $R^\omega$, $R^\text{DB}$, target guidance, stochasticity level, initial distributions, and training-sampling distortion (Sec. 5.3, App. B.1–B.4, C.1–C.2, Figs. 9, 10, 13, 14), as acknowledged by Reviewers 8xvx and 2q2N. These analyses sufficiently cover the key factors affecting generation and we provide supporting intuitions (Sec. 3.2, 5.3).
2. Computational trade-offs: We report training/sampling runtimes for DeFoG across datasets (App. F.3) and compare them with SOTA methods in Sec. 5.2. Note that step count scales linearly with runtime. Regarding memory usage, we propose to clarify in App. F.3:

"DeFoG’s memory usage matches existing diffusion models, with quadratic complexity in node number due to complete-graph modeling. Rate matrix overhead is negligible, and RRWP features are more efficient to compute than previous alternatives [3,4]."

II - Theoretical Claims:

1. Whether "noise schedules" refers to the choice of initial distribution or distortion functions, our theoretical results explicitly link training loss to sampling accuracy. Strong empirical results validate the practical relevance of these results, and the observed performance deterioration with fewer sampling steps confirms the theoretical predictions (Tables 1,2; Figs. 7,8,11,12).

III - Experimental Designs Or Analyses:

1. Scalability: We believe our efficiency claims are well-supported: DeFoG reduces sampling steps to 5–10% of the original total (Tables 1,2) and uses more efficient additional features (Table 12). Moreover, DeFoG's memory usage matches existing diffusion models (see I.2), enabling similar graph scales as competing methods. Scaling these methods to larger graphs is an interesting and challenging problem by itself (e.g., [5] leverages sparsity to scale existing graph diffusion models, an approach also applicable to DeFoG), thus beyond this work's scope.
2. Ablations: See I.1.
3. OOD Generalization: Unlike conventional OOD tasks, graph generation typically aims to maintain distributional similarity [3,4] rather than handle distributional shifts. Thus, while an interesting direction, it is beyond our scope. For standard generalization, see VII-2.

IV - Supplementary Material:

1. We ensure reproducibility via the provided code and detailed hyperparameters (App. B.4, F.4).

V - Broader Literature:

1. Graph flows/autoregressive models: We extensively discuss key autoregressive models (GraphRNN, GRAN, BiGG, GraphGen) (Sec.4, App.A.1, Table 1). Regarding normalizing flows, we acknowledge their relevance (Sec. 4) but are unaware of recent graph-specific advances directly relevant to our work; any suggestions are welcome.

VI - Essential References:

1. We included [1] in our related work, where we already discuss similar (autoregressive) models.
2. [2] is only a tutorial description on generative models for molecular graphs. Arguably, it is not an “essential reference'' on graph generative models. In case this was not a mistake, we kindly invite the reviewer to motivate this request.

VII - Other Strengths And Weaknesses:

1. Scalability: See III.1.
2. Generalization: DeFoG generalizes across diverse domains (synthetic, molecular, digital pathology), going beyond typical benchmarks in graph generation studies [4,5]. The additional ZINC250k results requested by Reviewer 2q2N further support this, making our generalization analysis comprehensive.
3. Hyperparameter studies: See I.1

VIII - Other Comments or Suggestions:

1. Efficiency: DeFoG incurs no additional overhead per sampling step (Alg. 2), and RRWP features are computed more efficiently than in prior work [3,4] (App. G.4).
2. Scalability: See III.1.
3. Flow/autoregressive comparison: See V.

IX - Questions For Authors:

1. Imbalanced graph structures: DeFoG implicitly captures distributional heterogeneity, confirmed by superior performance on very diverse structural graph statistics (degree, clustering, orbits, spectral, wavelet distributions; e.g., Table 7) and datasets.
2. Computational decoupling trade-offs: Per-step sampling efficiency matches/exceeds existing models (See VIII.1). Additionally, training-sampling decoupling enables optional independent tuning, potentially further improving performance at minimal extra cost via an optimized hyperparameter selection pipeline (App.B.4).
3. Hyperparameter sensitivity: See I.1.

[3] - Digress: Discrete denoising diffusion for graph generation, Vignac et al., ICLR 2023

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

[5] - Sparse Training of Discrete Diffusion Models for Graph Generation, Qin et al., ArXiv 2023

We thank the reviewer for their constructive feedback, as well as for recognizing the importance of our algorithmic improvements, the thoroughness of our experimental validation, and the practical value of our contributions to the graph generation community. Aligned with the reviewer's perspective, we are committed to releasing a clean, well-documented, and easy-to-use codebase upon publication to facilitate adoption and further developments by the community.

We remain open to any further suggestions or questions that may arise.

We thank the reviewer for their time and comments. We address the raised concerns below:

Claims And Evidence.

We agree with the reviewer that the training-sampling disentanglement is a contribution of DFM. In this regard, our contribution lies in making this decoupling effective for graph generation, where it had not been previously formulated, implemented, or empirically validated (as acknowledged in lines 145–150). Crucially, notice that applying existing DFM methods to graphs does not lead to improved performance (see Fig. 2 ablations). DeFoG addresses this by providing a graph tailored formulation that effectively leverages the decoupling between training and sampling, resulting in significant improvements in both sampling flexibility and efficiency.

We understand that the original phrasing could be misleading and so we propose the revised formulation:

We introduce DeFoG, a novel graph generative model that effectively exploits the training-sampling decoupling inherited from its flow-based formulation, significantly enhancing sampling flexibility and efficiency.

We hope this effectively addresses the reviewer’s concerns and remain available for further discussion.

Theoretical claims:

• Our Corollary 1 does not relate to the CTMC sampling error. Instead, it establishes that minimizing the CE loss directly corresponds to minimizing an upper bound on the rate matrix estimation error, directly promoting accurate sampling. This justifies the use of the CE loss without requiring ELBO-derived approximations (more on this below).

• Corollary 2 is not solely about the discretization error resulting from the CTMC sampling - which, as correctly noted by the reviewer is $O(\Delta t)$ (same as $O(h)$). Instead, it combines this term with the estimation error that results from Corollary 1 to bound the deviation of the generated graph distribution. Notice that this type of result is commonly sought in generative modeling to guarantee generation accuracy. For instance, Theorem 1 in [5] presents an analogous bound in the context of discrete diffusion, though with significant differences (e.g., they assume a bounded rate matrix estimation error, while we explicitly prove it).

Regarding the connection between DeFoG’s loss (CE) and ELBO, [1] derives an ELBO loss suitable to our chosen rate matrices (decomposed into three terms weighted CE, KL divergence, rate matrix regularizer). However, they motivate using only the CE loss based on approximations upon the derived ELBO by dropping the rate matrix-dependent terms (see App. C.2 from [1]). In contrast, our bounds do not require such simplifications and are agnostic to rate matrix design choices (e.g., stochasticity level), reinforcing our training-sampling decoupling claim. Additionally, [2], which is a contemporaneous submission under ICML guidelines (alongside [3]), also establishes an ELBO loss; however, on our understanding, it applies to a different family of conditional rate matrices.

We have included the discussion above, as well as the mentioned references, into the revised manuscript. We hope this clarifies the raised concern; if not, we remain open to further feedback.

Questions For Authors:

We use $x^{(n)}$ for the $n$-th node ($1 \leq n \leq N$) and $e^{(ij)}$ for the edge between nodes $x^{i}$ and $x^{j}$ ($1 \leq i < j \leq N$). Nodes are gathered as $x^{1:n:N}$, edges as $e^{1:i<j:N}$. Node and edge state spaces are denoted by $\mathcal{X}$ and $\mathcal{E}$ (cardinalities $X$, $E$, respectively), meaning nodes take values in $\\{ 1,\dots,X \\}$ and edges in $\\{ 1,\dots,E \\}$. Following standard practice in the field [6,7,8], we keep the number of nodes fixed throughout trajectories and explicitly model a complete graph, connecting all node pairs by edges. During diffusion trajectories, only node and edge classes change, not their structural existence. Crucially, one of the edge classes represents the absence of an edge ("non-existing” edge), but there is no “non-existing” class for nodes. Hence, each edge is always associated with its two vertices (there can be “floating” nodes, but no “floating edges”). We thank the reviewer for raising this important remark; we have made this more explicit in the updated manuscript.

Overall, we appreciate the reviewer’s constructive feedback, and we think their questions improved our work. We remain open to any further suggestions.

[5] - A Continuous Time Framework for Discrete Denoising Models, Campbell et al., NeurIPS 2022

[6] - Digress: Discrete denoising diffusion for graph generation, Vignac et al., ICLR 2023

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

[8] - Cometh: a Continuous-time Discrete-state Graph Diffusion Model, Siraudin et al., ArXiv 2024