Smooth Interpolation for Improved Discrete Graph Generative Models

W1: Towards the non-trivialness of our work

Thank you for raising this concern. We would like to further clarify the technical contribution of our approach. While our method builds on the BFN framework, naively applying it fails to perform well. Our work bridges the gap between the theoretical framework and complex real-world graph generation settings. For instance, in our ablation of the adaptive Flowback sample, disabling it causes a drastic performance drop—valid sample rate on Planar drops from 96.2% to 14.1%. Techniques like this improve the model framework itself and hence are task-agnostic, which may generalize to other complex applications of BFNs.

W2&3: Regarding GraphBFN's efficiency

Thank you for raising this important point. We would like to clarify that, similar to continuous-time diffusion models, GraphBFN achieves efficiency not through lower per-step runtime but through its ability to maintain high sample quality with fewer discretization steps.

Table 5 indicates that GraphBFN is not much slower per step than baselines. Rather, its key advantage lies in Table 7, where GraphBFN can maintain high sample quality with only ~10% of the original sampling steps.

Since GraphBFN and continuous-time models gains efficiency similarly, we compare their performance directly in the next table. GraphBFN consistently maintains the strongest performance at every level of step reduction. This reinforces GraphBFN effiency.

Dataset—QM9withoutH

We also provide a runtime comparison for DisCo under identical settings (Cometh's implementation is not available). Its longer runtime stems from its larger default architecture. When reduced to our setup, DisCo’s quality noticeably drops (see last below), suggesting GraphBFN maintains competitive per-step efficiency.

We also experimented with the faster but less expressive MPNN-based backbone architecture suggested by DisCo. We found GraphBFN can also enjoy this speed up. However, similar to DisCo's finding, we observe that the speed-up architecture results in a decline in sample quality. Even then, GraphBFN-MPNN still outperforms baselines.

Dataset—QM9withH

W2&3: Clarifying the Conceptual Difference between Continuous-time Diffusion and "Smooth Interpolation"

Thank you for pointing out their relation to "smoothness"

We want to clarify that there are generally two dimensions to consider when discussing smooth interpolation.

1. continuous transition of latent space
2. latent space itself being continuous-state and interpretable (our claim)

Continuous-time modeling (e.g. GraphBFN, DisCo, and Cometh) addresses the first dimension by allowing the latent distribution to evolve smoothly over continuous time. This allows the model to learn how to make predictions at any point in time, reducing discretization errors. This property explains why these models can sample with far fewer discretization steps than the discrete-time model DiGress[2].

However, the “smooth interpolation” we emphasize in our paper primarily refers to the second dimension: the latent space being continuous in state, not just in time. This is a unique property of GraphBFN, thanks to the probabilistic modeling of the BFN framework. Under this continuous and normalized latent space, changes in latent variables between nearby timesteps are significantly more stable compared to discrete latent spaces like those in DiGress. which enables smoother transitions in spectral features. In graph generation tasks, the model heavily relies on the conditioning of these features; hence, having a stable and consistent latent evolution is crucial for generation quality, as illustrated in Appendix G.2.

Though continuous-time dynamics help reduce transition noise in models like DisCo and Cometh, their latent variables still reside in the discrete graph space, which inherently leads to fluctuating latent transitions. To validate this, we conducted the analysis in Appendix G.1 on DisCo. The results show that DisCo’s trajectory behaves similarly to DiGress, with higher fluctuation.

We also distinguish our method from models like GruM. Though GruM also uses a continuous latent space, it is neither normalized nor structured in a way that makes spectral features interpretable. As a result, these models cannot effectively utilize the latent space to aid generation in the way GraphBFN can.

Q1: Towards the choice of Generative Framework

Thank you for your thoughtful and insightful comments. We first clarified our motivation for choosing the BFN as our model framework. As you mentioned, we use discrete diffusions as a case study to reveal a specific challenge in the discrete graph generative model, i.e., the fluctuation in the training dynamics. Firstly, the challenges are not limited to the scope of discrete diffusion models. For multi-step generative models, such as discrete diffusion/discrete flow matching[1], the fluctuation in the training trajectory originated from discrete space and the properties of discrete graphs. Moreover, the challenge could actually be generalized as to creating a trajectory from the prior to target distribution of a discrete graph that smoothly decomposes information and provides dense supervision.

There are several possible solutions, but actually remain an open research problem. Under the context of the diffusion framework, encoding the graphs to latent space and hybridizing the latent and discrete diffusion could be a possible solution to keep the discrete nature and build smooth trajectories. However, these approaches generally require training a well-performed encoder/decoder to make it work in practice, which brings a huge computational cost and system complexity. Compared to the diffusion framework, we choose BFN mainly due to its simplicity. BFN achieves smooth interpolation based on the introduced parameter space. Analog to the latent space for diffusion, the parameter space could be seen as a special non-parametric latent space, which is implied by a Bayesian update instead of a trained encoder. Our empirical studies show that parameter space enables the interpretation of natural data properties. We agree that there could be improved space for further exploring and tackling the challenges under various model frameworks, and we will add the discussion to the updated version.

[1] Lipman et al., 2023 “Flow Matching for Generative Modeling.”

Q2: Towards how to characterize a hybrid model

Thanks for your insightful comments! This is a very good question. Firstly, we discuss how to characterize a hybrid model. As we mentioned in the response to Q1, this is an open research area, and we believe there are several possible solutions. The key point is that a latent space is generally needed to capture the continuous properties of discrete graphs. The latent space could be represented by learned neural networks or constructed in a non-parametric manner (GraphBFN). Feasible solutions could be either jointly learning the latent distribution and the discrete distribution or designing the latent as an intermediate state between continuous-state and discrete space and only modeling in the latent space as GraphBFN did.

Next, we elaborate on the parameter spaces of GraphBFN. As shown in the previous response to Q1, we could interpret the parameter space as a non-parameterized latent space. However, though the points over the parameter space have a continuous value, the parameter space of $K$-dim one-hot discrete data is actually a $K-1$ simplex space. This is because the parameter space holds the constraint that the samples' dims need to be summed as $1$. The non-free lunch trade-off here is that though the parameter space could be seen as an intermediate between the continuous and discrete, the simplex-contains make it non-trivial to design generative models over such space.

We will add the discussion to the updated version to illustrate the possible solutions and tradeoffs better.

Q3: Towards the trade-off between "continuous" and "discrete"

Thank you for eliciting such an insightful discussion. We discuss the trade-off in the practical setting of graph generation. First, similar to our response to Reviewer HH53, the benefit of being more "continuous" lies in two aspects:

1. continuous transition of latent space

2. latent space itself being continuous-state and interpretable

Due to the space limit, please refer to the last response to Reviewer HH53 for a detailed discussion of these benefits. We apologize!

Regarding the notion of being more “discrete,” we are skeptical about the potential benefits of applying Bit Diffusion [3], given concerns similar to those observed with GruM. While the discrete latent space in Bit Diffusion may appear to align naturally with the inherently discrete structure of graphs, its binary representation lacks interpretability and structure. This limits the model’s ability to capture high-level graph semantics or guide the generation process meaningfully. Nonetheless, we believe Bit Diffusion may still be beneficial in other application domains where simplicity and generic data representation are more important than structured latent semantics.

[1] "DiGress: Discrete Denoising diffusion for graph generation."

[2] "Graph Generation with Diffusion Mixture."

[3] "Analog bits: Generating discrete ..."

W1: Lack of error bar in results

Thank you for the catch. We apologize for not making clear the inconsistent appearance of error terms in the paper. Actually, all reported results are averages of 3 runs. We omitted error terms for readability and because baseline results in prior work did not include them. Detailed results with the error bound for all datasets are summarized in the tables below.

W2: Motivations for Bayesian Flow Networks(BFN)

Thank you for the valuable feedback. We agree that the motivation for choosing BFN can be further clarified.

The rationale stems from our desire to design a 'smooth' generation/training trajectory is motivated by the recent advancements in the research field of diffusion-based approaches [1,2,3], where the signal noise ratio is widely set as a smooth transformation with respect to timesteps. This implies the information should be gradually decomposed in the forward transformation to provide dense supervision. However, for graphs that lie in discrete state space, the discrete nature makes it challenging to gradually decompose the information using discrete-state diffusion models (like DiGress and DisCo [1,3]), where the noisy graphs are created by operations such as deletion(masking) and replacement and these small perturbations can lead to abrupt structural changes (e.g., loss of connectivity or altered clustering).

BFN offers a compelling alternative by operating in a continuous categorical parameter space, which aligns naturally with the discrete form yet continuous property of graph data.

Furthermore, from the perspective of utilizing the inductive bias of graph data, the most advanced graph generation methods[1,4] have demonstrated the effectiveness and importance of utilizing the graph spectrum as either the auxiliary conditions or learning objectives. The smooth transformation in GraphBFN respects the local geometric and topological properties of the graph, which means that similar nodes remain similar throughout the transformation. Hence, it could provide better spectrum conditioning for neural networks. From the perspective of neural network optimization, smooth transformations avoid abrupt changes and can facilitate more stable training dynamics. Thus, gradients are less likely to explode or vanish, leading to more reliable and efficient learning.

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

[2] Jo, et al., 2024 "Graph Generation with Diffusion Mixture."

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

[4] Martinkus, et al., 2022 "SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators."

Towards additional comments

Thank you for your comments. We will incorporate them in future revisions.

Regarding your second comment, could you please clarify the intended question?

If you’re referring to the difference between “timesteps” in Figure 5 and “sampling steps” in Table 7, we’re happy to clarify. Figure 5 shows Spec.MMD was evaluated on noisy intermediate samples during generation. “Timestep” refers to a specific point in a sampling trajectory—each curve point corresponds to a sample at a different noise level.

Table 7 shows an ablation study on how reducing the number of sampling steps affects final sample quality. Each row corresponds to a run with a different step count. The first column shows the percentage of default steps used, standardized across datasets. For example, (10, Planar) means using 10% × 1000 = 100 steps.

If you’re asking about the DiGress and GruM curves in Appendix G.3, we apologize for the confusion. That study replicates GruM [1]’s analysis of graph topology recovery during generation. The corresponding curves for GruM, DiGress, and other baselines appear in Figure 2 of the GruM paper [1]. We’ll clarify this in the figure caption in the next version.

[1] Jo et al., 2024. Graph Generation with Diffusion Mixture.

W2: Towards how spectral features are used and how they improve the model

We apologize for the confusion. Our use of extra features—including both spectral and structural—follows the setup in prior work [1]. The key difference is that GraphBFN computes these features over the output distribution $\phi(G^{θ_t, t})$, a probabilistic matrix, instead of noisy intermediate samples.

We first clarify how extra features are used and implemented in the model. Each feature is categorized into node-level features and graph-level features. For graph-level features, we use

1. graph level counts of cycles,
2. the multiplicity of the eigenvalue 0, and
3. the first 5 nonzero eigenvalues of the graph Laplacian.

For node-level features, we use

1. node level counts of cycles.
2. the eigenvectors corresponding to eigenvalue 0 and
3. the first two eigenvectors associated with nonzero eigenvalues.

For molecular graphs, we include an additional graph-level feature — the molecular weight — and a node-level feature — the valency of each atom.

These choices follow DiGress [1]; more details are in their Appendix B.

How the extra features are used is included in Appendix.L.1, "Experiment Details". In short, we compute the extra features of intermediate samples and append them to network input.

Next, we demonstrate the importance of extra feature conditioning via additional ablation studies. Specifically, we evaluate the performance of both GraphBFN and DiGress with and without extra feature conditioning on the challenging QM9 with explict Hydrogens dataset. The results are summarized in the table below.

We observe that extra feature conditioning improves performance across all evaluation metrics for both models, showing its impact on enhancing molecular graph generation.

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

W1&Q1: Regarding the final discretization of probabilistic matrix and post-processing

Thank you for pointing out the ambiguity in our implementation detail. Yes, that’s correct—at the final step, discrete samples are obtained by directly sampling from the predicted probabilistic matrix (or node probability vectors). We do not employ any specialized discretization technique for all datasets; instead, we sample faithfully from the categorical distribution defined by the output distribution $\phi(G^{θ_1, 1})$. We also did not filter or curate our samples (e.g. forgo unconnected samples), in order to remain consistent with the evaluation procedures used in prior works.

The sampling details are depicted in Algorithm 2. Specifically, we sample from output distribution $\phi(G^{θ_1, 1})$ of the graph, which is split into two components: $V[\phi(G^{θ_1, 1})]$ for nodes and $E[\phi(G^{θ_1, 1})]$ for edges. The node tensor $V[\phi(G^{θ_1, 1})]$ has shape [bs,N,$c_v$], where $c_v$ is the number of node types. For instance, $V[\phi(G^{θ_1, 1})]$[1,1] is a categorical distribution representing how the first node of the first sample is distributed. Similarly, the edge tensor $E[\phi(G^{θ_1, 1})]$ has shape [bs,N,N,$c_e$], where $c_e$ denotes the number of edge types. Sampling is performed independently for each node and edge from the corresponding categorical distribution defined by the last dimension.

We have not explored alternative discretization strategies beyond direct sampling from the categorical distribution. This choice preserves the unbiased nature of our probabilistic modeling and maintains a good balance between sample quality and diversity. However, we believe that exploring alternative sampling strategies, like top-k or top-p, may be useful for tasks with specific demand, such as favoring higher fidelity at the expense of diversity.

Towards Additional Comments

Thank you very much for your detailed feedback. We will carefully incorporate your suggestions in future revisions.

Node colors in Figure 1:

• Apologies for the confusion. The node color reflects a spectral metric used to highlight clusters, originally meant to enhance visualization for structured graphs like SBM samples. We recognize this may be misleading and will either remove the coloring or clarify it in the caption.

Missing curves for DiGress and GruM in Figure 5:

• Apologies for the confusion. The study in Appendix G.3 replicates GruM [1]’s analysis of topology recovery. The curves for GruM, DiGress, and others can be found in Figure 2 of the GruM paper [1]. We’ll clarify this in the caption in the next version.

Typo in “A few entries…”

• You’re right—this was a typo. There should be a NOT before "reported." We’ll correct this in the next draft.

[1] Jo, et al., 2024 "Graph Generation with Diffusion Mixture."