Discrete Bayesian Sample Inference for Graph Generation

## Abstract

Abstract Generating graph-structured data is crucial in applications such as molecular generation, knowledge graphs, and network analysis. However, their discrete, unordered nature makes them difficult for traditional generative models, leading to the rise of discrete diffusion and flow matching models. In this work, we introduce GraphBSI , a novel one-shot graph generative model based on Bayesian Sample Inference (BSI). Instead of evolving samples directly, GraphBSI iteratively refines a belief over graphs in the continuous space of distribution parameters, naturally handling discrete structures. Further, we state BSI as a stochastic differential equation (SDE) and derive a noise-controlled family of SDEs that preserves the marginal distributions via an approximation of the score function. Our theoretical analysis further reveals the connection to Bayesian Flow Networks and Diffusion models. Finally, in our empirical evaluation, we demonstrate state-of-the-art performance on molecular and synthetic graph generation, outperforming existing one-shot graph generative models on the standard benchmarks Moses and GuacaMol.

## 1 Introduction

Graph structures appear in various domains ranging from molecular chemistry to transportation and social networks. Generating realistic graphs enables simulation of real-world scenarios, augmenting incomplete datasets, and discovering new materials and drugs (Guo & Zhao, 2022; Zhu et al., 2022). However, their unique and complex structure poses challenges to traditional generative models that are designed for continuous data such as images. This has resulted in a diverse landscape of graph generative models, featuring autoregressive models (You et al., 2018) and one-shot models (Kipf & Welling, 2016), including a range of diffusion-based models (Ho et al., 2020).

Recently, Bayesian Flow Networks (BFNs) (Graves et al., 2025) have emerged as a novel class of models that operate on the parameters of a distribution over samples rather than on the samples themselves. This approach is particularly appealing for discrete data, as the parameters of a probability distribution evolve smoothly even when the underlying samples remain discrete. Graph generative models based on BFNs have shown competitive performance in molecule generation (Song et al., 2025). However, operating in parameter space and being motivated through information theory adds a layer of complexity to the BFN framework that hinders its accessibility.

*Bayesian Sample Inference* (BSI) (Lienen et al., 2025) offers a simplified interpretation and generalizes continuous BFNs by viewing generation as a sequence of Bayesian updates that iteratively refine a belief over the unknown sample. The model is trained by optimizing its corresponding ELBO.

This work introduces GraphBSI, extending BSI to discrete graphs. Instead of operating on discrete states, GraphBSI evolves on the probability simplex of node and edge categories. We derive BSI for categorical data and show how to generate variably-sized graphs with it. Next, we formulate categorical BSI as an SDE and, via the Fokker–Planck equation, derive a noise-controlled family of SDEs that preserves marginals while interpolating between a deterministic probability-flow ODE and a highly stochastic sampler. Empirically, we demonstrate that GraphBSI achieves state-of-the-art results on the GuacaMol (Brown et al., 2019) and Moses (Polykovskiy et al., 2020) benchmarks for molecule generation. In extensive ablation studies, we show that noise control is a crucial factor for optimizing performance. An overview of our method is shown in [Fig. 1](https://arxiv.org/html/2511.03015v1#S2.F1).

Our main contributions can be summarized as follows:

- •
We derive BSI for categorical data, including graphs. The result generalizes the Bayesian Flow Network (BFN) framework with a simplified interpretation while avoiding limit approximations in the Bayesian update.
- •
We formulate categorical BSI as an SDE. Through the Fokker-Planck equation, we derive a generalized SDE with a noise-controlling parameter and identical marginals, allowing us to interpolate between a deterministic probability flow ODE and a sampling scheme that overrides all previous predictions with the most recent one.
- •
We demonstrate that GraphBSI achieves SOTA results across most metrics in the Moses and GuacaMol molecule generation benchmarks with as few as 50 function evaluations, and further gains substantial improvements with 500 function evaluations.

## 2 The Bayesian Sample Inference Framework for Graphs

Figure: Figure 1: Illustration of GraphBSI’s generative process. Nodes and edges are modeled as independent categorical variables. One edge-type is used to represent the non-existence of an edge. The latent variable $\mathbf{z}_{t}$ represents a distribution over graphs rather than a graph itself. The neural network $f_{\theta}$ smoothly steers this distribution from a random initial distribution $\mathbf{z}_{0}$ to a distribution concentrated on valid graphs $\mathbf{z}_{1}$, which is modeled as a Stochastic Differential Equation (SDE).
Refer to caption: x1.png

Bayesian Sample Inference (BSI) (Lienen et al., 2025) is a novel generative modeling framework simplifying and generalizing Bayesian Flow Networks (BFNs) (Graves et al., 2025). While BSI was originally presented for continuous data, we develop a theoretical framework extending BSI to categorical data analogously. We start by introducing the required background knowledge. All proofs are shown in [App. C](https://arxiv.org/html/2511.03015v1#A3).

#### Background.

Bayesian Sample Inference (BSI) (Lienen et al., 2025) generates samples by iteratively refining an initial belief $p(\mathbf{x})$ about the sample $\mathbf{x}$ to be generated through noisy measurements $\mathbf{y}$ of $\mathbf{x}$. The initial belief $p(\mathbf{x}\mid\mathbf{z}_{0})$ follows a broad isotropic Gaussian with parameters $\mathbf{z}_{0}=(\bm{\mu}_{0},\sigma_{0})$. The belief is then refined by a sequence of noisy measurements $\mathbf{y}_{0},\dots,\mathbf{y}_{k-1}$ that follow Gaussians centered around $\mathbf{x}$. After receiving the measurement $\mathbf{y}_{i}$, the information contained in it is integrated into our next belief $\mathbf{z}_{i+1}$ through a Bayesian update. Once the belief of $\mathbf{x}$ is sufficiently sharp, we return a sample from it.
We train a neural network $f_{\theta}$ to predict the train sample $\mathbf{x}$ from the information collected about it in the belief $\mathbf{z}_{i}$ for each timestep $i\in{0,\dots,k-1}$. The trained neural network allows us to generate new samples during inference by creating the noisy measurements through an approximation $\hat{\mathbf{x}}_{i}=f_{\theta}(\mathbf{z}_{i},i)$ of the sample $\mathbf{x}$ in each timestep $i$.

#### Extension to categorical data.

Now, we will focus on the case that our data lies on the simplex, i.e., we have a categorical belief for $\mathbf{x}$ over $c$ possible categories, i.e., $x\in\Delta_{c-1}^{n}\subset[0,1]^{n\times c}$. If we have access to noisy measurements $\mathbf{y}_{i}\sim\mathcal{N}(\mathbf{x},\Sigma^{2}=\alpha_{i}^{-1}I)$ of the sample $\mathbf{x}$, we can infer $\mathbf{x}$ from the measurements using Bayes’ theorem in a similar fashion to the continuous case. We start with an initial belief $p(\mathbf{x}\mid\mathbf{z}_{0})\sim\mathrm{Cat}(\mathrm{softmax}(\mathbf{z}_{0}))$, where $\mathbf{z}_{0}\in\mathbb{R}^{n\times c}$ are the logits of a categorical distribution with $n$ independent components. Then, we can update the belief parameters $\mathbf{z}$ after observing $\mathbf{y}_{i}$ using Bayes’ theorem.

###### Theorem 1 .

Given a prior belief $p(\mathbf{x}\mid\mathbf{z})=\mathrm{Cat}(\mathbf{x}\mid\mathrm{softmax}(\mathbf{z}))$, after observing $\mathbf{y}\sim\mathcal{N}(\mathbf{y}\mid\mu=\mathbf{x},\Sigma^{2}=\alpha^{-1}\mathbf{I})$ at precision $\alpha$, the posterior belief is $p(\mathbf{x}\mid\mathbf{z},\mathbf{y},\alpha)=\mathrm{Cat}(\mathbf{x}\mid\mathrm{softmax}(\mathbf{z}_{\mathrm{post}}))$ with

$$ $\mathbf{z}_{\mathrm{post}}=\mathbf{z}+\alpha\mathbf{y}.$ (1) $$

Now, we can iterate over multiple noisy measurements and update our belief until $p(\mathbf{x}\mid\mathbf{y}_{1},\dots,\mathbf{y}_{k})$ identifies $\mathbf{x}$ with high probability.
Through [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1), we encode the information contained in all these measurements in our updated belief parameters $\mathbf{z}_{k}$ as $p(\mathbf{x}\mid\mathbf{y}_{1},\dots,\mathbf{y}_{k})=p(\mathbf{x}\mid\mathbf{z}_{k})\sim\mathrm{Cat}(\mathrm{softmax}(\mathbf{z}_{k}))$ with $\mathbf{z}_{k}=\mathbf{z}_{0}+\sum_{i}\alpha_{i}\mathbf{y}_{i}$.

We process each observation $\mathbf{y}_{i}$ sequentially, inducing a notion of time. We measure $\mathbf{y}_{i}$ at time $t_{i}=\Delta t\cdot i\in[0,1]$ with $\Delta t=1/(k+1)$, and the subsequent Bayesian update takes us to $t_{i+1}$. To control the total amount of information added to the belief $p(\mathbf{x}\mid\mathbf{z}_{t})$ up to time $t$, we define a monotonically increasing precision schedule $\beta\colon[0,1]\to\mathbb{R}^{+}$. The measurement $\mathbf{y}_{i}$ contains the information added in the time interval $[t_{i},t_{i+1}]$, and therefore we choose $\alpha_{i}=\beta(t_{i+1})-\beta(t_{i})$.

Generative model construction. We build a generative model for categorical data given the above procedure, similarly as done for BSI with continuous data (Lienen et al., 2025). We begin with a logit $\mathbf{z}_{0}$ defining the initial belief of the sample $\mathbf{x}$ that we will generate in the end, with $\mathbf{z}_{0}\sim\mathcal{N}(\bm{\mu}_{0},\beta_{0})$ sampled from a simple prior distribution. As $\mathbf{x}$ is unknown a priori, we cannot measure it, so instead we estimate it from the information we have gathered so far encoded in our latest belief. Let $f_{\theta}:\mathbb{R}^{n\times c}\times[0,1]\mapsto\Delta^{n}_{c-1}$ be a neural network with parameters $\theta$ estimating the unknown sample $\mathbf{x}$ behind our observations given our current belief $\mathbf{z}_{t}$ and time $t$. We estimate $\mathbf{x}$ as $\hat{\mathbf{x}}_{i}=f_{\theta}(\mathbf{z}_{i},t)$, followed by a noisy measurement $\mathbf{y}_{i}\sim\mathcal{N}(\hat{\mathbf{x}}_{i},\Sigma^{2}=\alpha^{-1}_{i})$ centered around $\hat{\mathbf{x}}_{i}$ with precision $\alpha_{i}$. Then, we update our belief with $\mathbf{y}_{i}$ via [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1). Now, we repeatedly predict $\hat{\mathbf{x}}_{i}$, measure $\mathbf{y}_{i}$, and update the belief parameters $\mathbf{z}_{i+1}\leftarrow\mathbf{z}_{i}+\alpha_{i}\mathbf{y}_{i}$ until our belief is sufficiently sharp at $t=1$. Finally, we return a sample from $\mathrm{Cat}(\mathbf{x}\mid\mathrm{softmax}(\mathbf{z}_{1}))$. See [Alg. 1](https://arxiv.org/html/2511.03015v1#alg1) for a formal description.

Evidence Lower Bound. To train our neural network, we interpret CatBSI as a hierarchical latent variable model to derive an evidence lower bound (ELBO) of the sample likelihood (Kingma & Welling, 2013), providing a natural training target. As latent variables, we choose the beliefs $\mathbf{z}_{0},\dots,\mathbf{z}_{k}$. Their distribution in [Alg. 1](https://arxiv.org/html/2511.03015v1#alg1) factorizes, allowing us to write

$$ $p(\mathbf{x})=\operatorname*{\mathbb{E}}\limits_{p(\mathbf{z}_{0})\prod_{i=1}^{k}p(\mathbf{z}_{i}|\mathbf{z}_{i-1},\theta)}\left[p(\mathbf{x}\mid\mathbf{z}_{k})\right].$ (2) $$

As encoding distribution $q(\mathbf{z}_{0},\mathbf{z}_{1},\dots,\mathbf{z}_{k}\mid\mathbf{x})$, we choose the distribution induced under [Alg. 1](https://arxiv.org/html/2511.03015v1#alg1) with a fixed reconstruction $f_{\theta}(\mathbf{z},t)=\mathbf{x}$. Thanks to the simple form of [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1), it is straightforward to compute the marginal $q(\mathbf{z}_{i}\mid\mathbf{x})$:

$$ $\mathbf{z}_{i}=\mathbf{z}_{0}+\sum_{j=0}^{i-1}\alpha_{j}\mathbf{y}_{j}\sim\mathcal{N}(\bm{\mu}_{0}+\beta(t_{i})\mathbf{x},\Sigma^{2}=\beta_{0}+\beta(t_{i}))$ (3) $$

Equipped with this, we can derive the following ELBO:

###### Theorem 2 .

For categorical BSI, the log-likelihood of $\mathbf{x}$ under [Alg. 1](https://arxiv.org/html/2511.03015v1#alg1) is lower bounded by

$$ $\log p(\mathbf{x})\geq\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}\mathbf{z}_{k}\sim q(\mathbf{z}|\mathbf{x},t_{k})\end{subarray}}[\log p(\mathbf{x}\mid\mathbf{z}_{k})]-\frac{k}{2}\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}i\sim\mathcal{U}(0,k-1)\\ \mathbf{z}_{i}\sim q(\mathbf{z}|\mathbf{x},t_{i})\end{subarray}}[(\beta(t_{i+1})-\beta(t_{i}))||f_{\theta}(\mathbf{z}_{i},t_{i})-\mathbf{x}||_{2}^{2}],$ (4) $$

where $q(\mathbf{z}\mid\mathbf{x},t)=\mathcal{N}(\mathbf{z}\mid\bm{\mu}_{0}+\beta(t)\mathbf{x},\beta_{0}+\beta(t)I)$ and $p(\mathbf{x}\mid\mathbf{z}_{k})=\mathrm{Cat}(\mathbf{x}\mid\mathrm{softmax}(\mathbf{z}_{k}))$.

The first term does not depend on $\theta$ and therefore cannot be optimized; we only need to minimize the second term. For $k\to\infty$, we have that $k(\beta(t_{i+1})-\beta(t_{i}))\to\beta^{\prime}(t_{i})$ since $\Delta t=t_{i+1}-t_{i}=1/(k+1)\approx 1/k$, and $t_{i}\sim\mathcal{U}(0,1)$. Maximizing the ELBO for $k\to\infty$ over the dataset above is therefore equivalent to minimizing

$$ $\mathcal{L}\equiv\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}\mathbf{x}\sim p(\mathbf{x})\\ t\sim\mathcal{U}(0,1)\\ \mathbf{z}\sim q(\mathbf{z}|\mathbf{x},t)\end{subarray}}[\beta^{\prime}(t)/2\cdot||f_{\theta}(\mathbf{z},t)-\mathbf{x}||_{2}^{2}]$ (5) $$

The loss above immediately yields the training procedure [Alg. 2](https://arxiv.org/html/2511.03015v1#alg2). This matches the continuous-time categorical BFN loss up to a constant when $\beta_{0}\to 0$, i.e., the prior is a Dirac delta at $t=0$.

###### Theorem 1 .

###### Theorem 2 .

#### Adaptation for graphs.

We represent graphs with $N$ nodes as tuples $(X,A)$, where $X\in\Delta_{c_{X}-1}^{N}\subset[0,1]^{N\times c_{X}}$ are the one-hot encoded categories of each node and $A\in\Delta_{c_{A}-1}^{N\times N}\subset[0,1]^{N\times N\times c_{A}}$ the one-hot encoded categories of each edge, with the first category denoting the absence of an edge. We treat each node and edge as an independent component of the categorical belief, allowing us to apply the categorical BSI framework to graphs. Note that dependence between edges is introduced via our network $f$. We choose a permutation invariant reconstruction network $f_{\theta}$, resulting in a permutation invariant generative model when the noise is isotropic.

To enable a varying number of nodes in the graph, we first sample a number of nodes $N$ from the marginal node count distribution, and subsequently generate the node and edge values. In practice, this is achieved by masking out inactive nodes and edges for train graphs with fewer nodes.

Figure: Algorithm 1 Sampling with Categorical BSI

Figure: Algorithm 2 Training Categorical BSI

## 3 Categorical BSI as a Stochastic Differential Equation

Figure: Figure 2: Trajectories of the SDE [Theorem 4](https://arxiv.org/html/2511.03015v1#Thmtheorem4) for different values of $\gamma$ with three classes and fixed reconstruction $f_{\theta}(\mathbf{z}_{t},t)=\hat{e}_{2}$. At $\gamma=0$, the sampler resembles a probability flow ODE as in flow matching. Increasing $\gamma$ leads to noisier trajectories. At $\gamma=1$, the original SDE in [Theorem 3](https://arxiv.org/html/2511.03015v1#Thmtheorem3) is recovered, and increasing the noise further makes the trajectories even more volatile. The density function of the marginal distribution $p(\mathbf{x}\mid\mathbf{z}_{t})$ (shown in the background) is identical for all $\gamma$.
Refer to caption: x2.png

In this section, we analyze the update equation in [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1) and take the infinite-step limit, obtaining an SDE. We then introduce a parameter that controls the stochasticity and yields a family of SDEs with identical marginals.

#### SDE Dynamics.

First, we notice that as the number of steps $k$ increases, i.e., $\Delta t:=1/(k+1)\to 0$, the updates in [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1) converge to the following SDE.

###### Theorem 3 .

As $\Delta t\to 0$, the update equation in [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1) converges to the following SDE:

$$ $\displaystyle d\mathbf{z}_{t}$ $\displaystyle=\beta^{\prime}(t)f_{\theta}(\mathbf{z}_{t},t)dt+\sqrt{\beta^{\prime}(t)}dW_{t}$ (6) $$

where $dW_{t}$ is a Wiener process and $\mathbf{z}_{0}\sim\mathcal{N}(\bm{\mu}_{0},\beta_{0}\cdot I)$.

Note that while the distribution of $\mathbf{z}_{0}$ is not required to be normal for [Theorem 3](https://arxiv.org/html/2511.03015v1#Thmtheorem3) itself, it is necessary for the following steps. Phrasing the evolution of the latent variable $\mathbf{z}_{t}$ as an SDE enables the use of more advanced sampling schemes and allows us to derive a generalized SDE family. The original discrete update in [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1) is recovered by applying an Euler-Maruyama discretization of [Eq. 6](https://arxiv.org/html/2511.03015v1#S3.E6).

###### Theorem 3 .

#### Generalized SDE.

We now generalize [Eq. 6](https://arxiv.org/html/2511.03015v1#S3.E6) to a family that preserves the marginal probability paths $p_{t}(\mathbf{z}_{t})$ while controlling stochasticity via the parameter $\gamma$, similar to Karras et al. (2022):

###### Theorem 4 .

The SDE in [Theorem 3](https://arxiv.org/html/2511.03015v1#Thmtheorem3) is generalized by the following family of SDEs with equal marginal densities $p_{t}(\mathbf{z}_{t})$:

$$ $\displaystyle d\mathbf{z}_{t}$ $\displaystyle=\beta^{\prime}(t)f_{\theta}(\mathbf{z}_{t},t)dt+\frac{\gamma-1}{2}\beta^{\prime}(t)\nabla_{\mathbf{z}_{t}}\log p_{t}(\mathbf{z}_{t})dt+\sqrt{\gamma\beta^{\prime}(t)}dW_{t}$ (7) $$

where $dW_{t}$ is a Wiener process and $\mathbf{z}_{0}\sim\mathcal{N}(\bm{\mu}_{0},\beta_{0}\cdot I)$.

Setting $\gamma=0$ yields a deterministic probability flow ODE, equivalent to Xue et al. (2024). Unlike BFNs, however, CatBSI samples the prior belief $p(\mathbf{z}\mid t=0)$ rather than choosing a fixed prior, naturally avoiding the discontinuity around $t=0$. Further, choosing $\gamma=1$ recovers the original SDE in [Theorem 3](https://arxiv.org/html/2511.03015v1#Thmtheorem3), and larger $\gamma$ produces more stochastic trajectories. We visualize in [Fig. 2](https://arxiv.org/html/2511.03015v1#S3.F2) how varying $\gamma$ affects the dynamics for three classes. Although the marginal distributions are equal for all $\gamma$ in theory, the empirical performance varies as $\nabla_{\mathbf{z}_{t}}\log p_{t}(\mathbf{z}_{t})$ is not available in closed form. Higher stochasticity allows the model to correct errors made in previous sampling steps but requires a finer discretization (see [Sec. 4.3](https://arxiv.org/html/2511.03015v1#S4.SS3)). In the limit $\gamma\to\infty$, the sampler effectively overwrites the current state completely in every step (see [Sec. B.3](https://arxiv.org/html/2511.03015v1#A2.SS3)).
To turn [Eq. 7](https://arxiv.org/html/2511.03015v1#S3.E7) into a practical sampling algorithm, we approximate the score function $\nabla_{\mathbf{z}_{t}}\log p_{t}(\mathbf{z}_{t})$, as described in the following.

###### Theorem 5 .

The BSI loss [Eq. 5](https://arxiv.org/html/2511.03015v1#S2.E5) also is a score matching loss with the score model $s_{\theta}(\mathbf{z},t)$ parameterized as

$$ $s_{\theta}(\mathbf{z},t)\equiv\frac{\bm{\mu}_{0}+\beta(t)f_{\theta}(\mathbf{z},t)-\mathbf{z}}{\beta(t)+\beta_{0}}\overset{!}{\approx}\nabla_{\mathbf{z}}\log p_{t}(\mathbf{z})$ (8) $$

###### Theorem 4 .

###### Theorem 5 .

#### Discretization and integration.

As the SDE is not solvable in closed form, we resort to numerical sampling. While a simple Euler-Maruyama (EM) approach performs well on sufficiently fine time grids, we find that integrating a locally linearized SDE within each step can improve sample quality for low numbers of neural function evaluations (see [Sec. 4.3](https://arxiv.org/html/2511.03015v1#S4.SS3)). More specifically, we freeze the reconstructor $\hat{\mathbf{x}}=f_{\theta}(\mathbf{z}_{t},t)$ over the time interval $[t,t+\Delta t]$, representing an Ornstein-Uhlenbeck process. This allows us to solve the SDE analytically within this interval.

###### Theorem 6 .

Fixing the prediction $\hat{\mathbf{x}}=f_{\theta}(\mathbf{z}_{t},t)$ and the values $\beta=\beta(t+\Delta t/2)$, $\beta^{\prime}=\beta^{\prime}(t+\Delta t/2)$ in [Eq. 7](https://arxiv.org/html/2511.03015v1#S3.E7) in a time interval $[t,t+\Delta t]$ yields an Ornstein-Uhlenbeck (OU) process with the exact marginal

$$ $\mathbf{z}_{t+\Delta t}\sim m+(\mathbf{z}_{t}-m)e^{-\kappa\Delta t}+\sqrt{\frac{\gamma\beta^{\prime}}{2\kappa}(1-e^{-2\kappa\Delta t})}\cdot\mathcal{N}(0,I),$ (9) $$

where $\kappa=\frac{(\gamma-1)\beta^{\prime}}{2(\beta_{0}+\beta)}$, $m=\bm{\mu}_{0}+(\beta+\beta^{\prime}/\kappa)\hat{\mathbf{x}}$.

Note that the OU discretization converges towards the EM scheme for $\Delta t\to 0$ (see [Sec. B.1](https://arxiv.org/html/2511.03015v1#A2.SS1)). Employing the discretization schemes yields [Algs. 3](https://arxiv.org/html/2511.03015v1#alg3) and [4](https://arxiv.org/html/2511.03015v1#alg4).

Figure: Algorithm 3 Euler-Maruyama Sampling

Figure: Algorithm 4 Ornstein-Uhlenbeck Sampling

We also allow a nonuniform time grid. Following Karras et al. (2022), we introduce a parameter $\rho$ that controls the distribution of function evaluations over the time grid:

$$ $t_{i}=\left(\frac{i}{k}\right)^{\rho},\qquad i=0,1,\dots,k.$ (10) $$

Here, $\rho=1$ recovers a uniform grid; larger $\rho$ concentrates steps near the beginning ($t\approx 0$), whereas smaller $\rho$ concentrates them near the end ($t\approx 1$).

###### Theorem 6 .

## 4 Experiments

In this section, we present our empirical results. We benchmark our model against state-of-the-art baselines from the diffusion and flow-matching literature on unconditional molecular and synthetic graph generation. The GuacaMol and Moses benchmarks for molecular generation (Brown et al., 2019; Polykovskiy et al., 2020) serve as our primary evaluation datasets. Additionally, we conduct ablation studies to analyze the impact of various components and hyperparameters on the model’s performance. Further, we report results on the synthetic planar, tree, and stochastic block model graph generation tasks (Bergmeister et al., 2024; Martinkus et al., 2022).

### 4.1 Experimental Setup

#### Datasets.

To test performance on real-world graphs, we train GraphBSI on the Moses (Polykovskiy et al., 2020) and GuacaMol (Brown et al., 2019) datasets for molecular generation. Further, we include results for the planar, tree, and stochastic block model (Martinkus et al., 2022; Bergmeister et al., 2024) synthetic graph generation datasets. Find a summary in [Tab. 6](https://arxiv.org/html/2511.03015v1#A4.T6).

#### Evaluation metrics.

We follow the standard evaluation practices as established by Polykovskiy et al. (2020); Brown et al. (2019); Preuer et al. (2018) for molecule generation and Martinkus et al. (2022); Bergmeister et al. (2024) for synthetic graph generation. Find a detailed description in [Tabs. 7](https://arxiv.org/html/2511.03015v1#A4.T7) and [8](https://arxiv.org/html/2511.03015v1#A4.T8).

#### Practical considerations.

The reconstruction network $f_{\theta}$ is parameterized using the same graph transformer architecture as Qin et al. (2025); Vignac et al. (2023), with the node- and edge logits and class probabilities, entropy, random walk features, and sinusoidal embeddings (Vaswani et al., 2017) of the timestep $t$ with frequencies proposed by Lienen et al. (2024) as features. Empirically, we find that an exponential precision schedule with a final precision that allows for a near-perfect reconstruction maximizes performance (see [Tab. 5](https://arxiv.org/html/2511.03015v1#A4.T5)). For both latent node- and edge classes, we choose a normal prior with the marginal distribution over the dataset and a small variance of $1.0$. Finally, we apply a preconditioning scheme where the neural network predicts the difference between the belief and the true sample, setting $f_{\theta}(z,t)=\mathrm{softmax}(z+\tilde{f}_{\theta}(z,t))$.

Evaluation After training to convergence, we evaluate the benchmark metrics for both discretization schemes [Algs. 3](https://arxiv.org/html/2511.03015v1#alg3) and [4](https://arxiv.org/html/2511.03015v1#alg4). For both molecule generation benchmarks, we report results with a compute budget of 50 and 500 discretization steps. In each of the four configurations (2 discretization schemes, 2 numbers of steps), we optimize the noise level $\gamma$ and report the best result. Find the final configurations in [Tab. 5](https://arxiv.org/html/2511.03015v1#A4.T5).
For the synthetic graph generation benchmarks, we report results with the best-performing noise level and the Ornstein-Uhlenbeck discretization with 1000 function evaluations.

### 4.2 Results

#### Molecule Generation.

As illustrated in [Tab. 1](https://arxiv.org/html/2511.03015v1#S4.T1), GraphBSI is competitive with 50 steps with both discretization schemes for both molecule benchmarks, achieving state-of-the-art results on the majority of the metrics. Notably, GraphBSI outperforms DeFoG with both discretization schemes on all metrics except novelty on Moses. On most metrics, the OU discretization performs better than the EM scheme.
At the full 500 steps, GraphBSI with the OU discretization outperforms all existing models on all metrics except novelty with Moses, saturating validity and consistently exceeding the state-of-the-art. The EM scheme performs slightly worse than OU on most metrics, but remarkably pushes the state-of-the art on the FCD metric from $1.07$ to $0.26$ on Moses.

Table: Table 1: Results on the GuacaMol and Moses benchmarks for molecular generation with 50 and 500 sampling steps and the Euler-Maruyama (EM) and Ornstein-Uhlenbeck (OU) discretization.

#### Synthetic Benchmarks.

As shown in [Tab. 2](https://arxiv.org/html/2511.03015v1#S4.T2), GraphBSI achieves competitive results on the synthetic graph generation benchmarks. Our model saturates validity on the planar- and tree graph generation tasks, and achieves adequate validity on the stochastic block model graphs. The mean ratio as a measure of distribution similarity is competitive on all three datasets, even though the metric should be taken with a grain of salt due to the small dataset size of only $128$ graphs, resulting in high uncertainty in the evaluation.

Table: Table 2: Results on the synthetic graph generation benchmarks. Like DeFoG, we generate 40 graphs five times and report the mean and standard deviation over the runs.

### 4.3 Ablation Studies

Figure: Figure 3: Normalized metrics (zero mean, unit variance) vs. noise level $\gamma$ for different numbers of function evaluations (FE) and discretization schemes. Our custom Ornstein-Uhlenbeck discretization scheme is denoted as OU, while the standard Euler-Maruyama scheme is written as Euler. Some values for the Euler scheme are missing since the sampler becomes unstable if $\gamma\cdot\Delta t$ becomes too large (see [Sec. B.2](https://arxiv.org/html/2511.03015v1#A2.SS2)).
Refer to caption: x5.png

Noise level. To test the effect of the compute budget, noise level, and discretization scheme on performance, we conduct a grid search over the number of function evaluations (NFEs) in $\{25,50,100,200,500\}$, noise levels $\gamma$ in $\{0.0,5.0,20.0,100.0,250.0,1000.0\}$, and both discretization schemes on the Moses dataset. As shown in [Fig. 3](https://arxiv.org/html/2511.03015v1#S4.F3), performance in both discretization schemes is closely related at low noise levels, which is to be expected since both discretize the same SDE. Higher compute budgets lead to better performance on all metrics except novelty. However, the Euler-Maruyama scheme becomes unstable at higher noise levels, leading to a significant drop in performance (see [Sec. B.2](https://arxiv.org/html/2511.03015v1#A2.SS2)). In contrast, the Ornstein-Uhlenbeck scheme remains stable, and both the SNN score and scaffold similarity benefit from higher noise levels. The FCD metric, however, is optimal at a medium noise level between $20$ and $100$. With a few exceptions, the Ornstein-Uhlenbeck scheme matches or outperforms the Euler-Maruyama scheme at all compute budgets and noise levels. Novelty suffers from increased noise levels and compute budgets, which is consistent with the model generating samples closer to the training data distribution. Notably, all metrics perform poorly at a noise level of $0.0$, which corresponds to the probability flow ODE (equivalent to Xue et al. (2024)).

Non-uniform timesteps. To test whether a fine discretization is more important at some timesteps compared to others, we analyze the effect of non-uniform timestepping, putting a finer discretization at either earlier or later timesteps. As shown in [Fig. 4](https://arxiv.org/html/2511.03015v1#S4.F4), SNN and Scaffold similarity remain mostly unaffected by the choice of $\rho$; only the FCD varies significantly. A finer discretization at later timesteps ($\rho<1$) improves the FCD at $50$ function evaluations in both discretization schemes and at $500$ evaluations in the Ornstein-Uhlenbeck scheme.

Figure: Figure 4: Performance change for changes in the non-uniform timestepping parameter $\rho$ in $t_{i}=(i/k)^{\rho}$ for $i=0,1,\dots,k$ compared to the uniform case $\rho=1$. $\rho<1$ results in a finer discretization at later timesteps, while $\rho>1$ corresponds to finer discretization at earlier steps.
Refer to caption: x6.png

## 5 Related Work

Graph generation presents three main challenges compared to image and text generation:
(1) graphs are discrete structures, unlike images, which are continuous;
(2) graphs have a variable shape, with both the number and arrangement of nodes and edges changing across samples, unlike the fixed dimensions of images; and
(3) nodes in graphs lack a natural order, in contrast to text, where tokens follow a well-defined sequence. Various approaches have been proposed to tackle these challenges.

Autoregressive models have proven successful in text generation by sequentially predicting the next token based on previous ones Brown et al. (2020). Applied to graphs, these models generate nodes and edges one by one, maintaining the graph structure as they proceed. This approach has been used for tasks such as molecule and social-network generation You et al. (2018); Liao et al. (2020). However, autoregressive models violate permutation invariance by relying on a specific node ordering.

One-shot models address the ordering challenge by generating the entire graph in a single step, without relying on a specific node ordering. Examples include Variational Autoencoders Kingma & Welling (2013), GANs Cao & Kipf (2022), normalizing flows Liu et al. (2019), and discrete flow matching Gat et al. (2024); Qin et al. (2025).

Diffusion models have emerged as a powerful class of one-shot generative models for continuous data such as images Sohl-Dickstein et al. (2015); Ho et al. (2020). Their core idea is to learn a generative process that gradually transforms noise into clean data by reversing a diffusion process with a neural network. Noise is typically applied independently to each pixel in images or to each node in graphs, naturally resulting in a permutation-invariant model when combined with a Graph Neural Network (GNN) Niu et al. (2020). A variable number of nodes can be handled by conditioning the diffusion process on the node count, e.g., by first sampling a node mask and then applying diffusion to the masked graph Niu et al. (2020); Qin et al. (2025). To improve scalability, hybrid methods that reverse a coarsening process and generate local structures with a diffusion model have also been proposed Bergmeister et al. (2024).

Discrete diffusion addresses the discreteness of graphs. The most straightforward approach relaxes discrete data to a continuous space, applies diffusion, and quantizes the generated outputs back to the discrete space in a final step Niu et al. (2020); Jo et al. (2022; 2024). Alternatively, one can use discrete diffusion in which the state is perturbed via a Markovian transition matrix in discrete time steps (often including an absorbing state) Austin et al. (2023); this has been applied to graphs Vignac et al. (2023); Haefeli et al. (2023). A related recent approach uses a continuous-time Markov chain for the discrete diffusion process (see Campbell et al. (2022)), which allows more flexible sampling on graphs Siraudin et al. (2024); Xu et al. (2024).

Bayesian Flow Networks (Graves et al., 2025) propose a conceptually distinct approach to discrete generative models: diffusion is applied to the parameters of a distribution over samples rather than to the samples themselves. BFNs can be interpreted as an SDE, enabling more efficient sampling algorithms Xue et al. (2024). This provides a solid theoretical foundation for diffusion on discrete data while retaining the benefits of smooth parameter changes, and it achieves competitive performance on protein and graph generation Atkinson et al. (2025); Song et al. (2025); Tao & Abe (2025). The flexible design of BFNs also permits joint generation of continuous and discrete quantities, for example the 3D positions, atom types, and charges in molecular generation Song et al. (2024).
Bayesian Sample Inference Lienen et al. (2025) extends BFNs by adding a prior over the distribution parameters and offers a simplified interpretation for the continuous-data case.

## 6 Conclusion

In this work, we introduce GraphBSI, a novel generative model for graphs based on Bayesian Sample Inference with state-of-the-art performance in large molecule generation benchmarks. Similar to Bayesian Flow Networks, GraphBSI iteratively refines a belief over the graph structure, modeled as a categorical distribution over adjacency matrices, through Bayesian updates. We show that in the limit of infinitesimal time steps, GraphBSI converges to a Stochastic Differential Equation (SDE). Further, we employ the Fokker-Planck equation to derive a generalized SDE with a tunable noise parameter, allowing us to interpolate between a deterministic probability flow ODE, the original SDE, and a substantially more volatile sampler. We demonstrate that GraphBSI achieves state-of-the-art performance on the GuacaMol and Moses benchmarks for large molecule generation, outperforming existing models on nearly all metrics. Finally, in our ablations we empirically show that noise control critically influences performance.

#### Limitations and Future Work.

GraphBSI, in its current implementation, suffers from the quadratic scaling of compute and memory requirements in the number of nodes that comes with the application of a graph transformer. Exploring a more memory-efficient graph neural network architecture to generate larger graphs would be a promising avenue for future research. Further, while GraphBSI allows for variable-sized graphs, the number of nodes is sampled beforehand instead of jointly generated with the graph features. Allowing for nodes to appear or disappear while generating the graph, similar to jump diffusion (Campbell et al., 2023), might result in a more flexible generative process.

## References

- Atkinson et al. (2025)
Timothy Atkinson, Thomas D. Barrett, Scott Cameron, Bora Guloglu, Matthew
Greenig, Charlie B. Tan, Louis Robinson, Alex Graves, Liviu Copoiu, and
Alexandre Laterre.
Protein sequence modelling with bayesian flow networks.
*Nature Communications*, 16(1):3197, 2025.
ISSN 2041-1723.
doi: 10.1038/s41467-025-58250-2.
URL [https://doi.org/10.1038/s41467-025-58250-2](https://doi.org/10.1038/s41467-025-58250-2).
- Austin et al. (2023)
Jacob Austin, Daniel D. Johnson, Jonathan Ho, Daniel Tarlow, and Rianne van den
Berg.
Structured denoising diffusion models in discrete state-spaces, 2023.
URL [https://arxiv.org/abs/2107.03006](https://arxiv.org/abs/2107.03006).
- Bergmeister et al. (2024)
Andreas Bergmeister, Karolis Martinkus, Nathanaël Perraudin, and Roger
Wattenhofer.
Efficient and scalable graph generation through iterative local
expansion, 2024.
URL [https://arxiv.org/abs/2312.11529](https://arxiv.org/abs/2312.11529).
- Brown et al. (2019)
Nathan Brown, Marco Fiscato, Marwin H.S. Segler, and Alain C. Vaucher.
Guacamol: Benchmarking models for de novo molecular design.
*Journal of Chemical Information and Modeling*, 59(3):1096–1108, March 2019.
ISSN 1549-960X.
doi: 10.1021/acs.jcim.8b00839.
URL [http://dx.doi.org/10.1021/acs.jcim.8b00839](http://dx.doi.org/10.1021/acs.jcim.8b00839).
- Brown et al. (2020)
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, … Ilya Sutskever,
et al.
Language models are few‐shot learners.
In *NeurIPS*, 2020.
- Campbell et al. (2022)
Andrew Campbell, Joe Benton, Valentin De Bortoli, Tom Rainforth, George
Deligiannidis, and Arnaud Doucet.
A continuous time framework for discrete denoising models, 2022.
URL [https://arxiv.org/abs/2205.14987](https://arxiv.org/abs/2205.14987).
- Campbell et al. (2023)
Andrew Campbell, William Harvey, Christian Weilbach, Valentin De Bortoli, Tom
Rainforth, and Arnaud Doucet.
Trans-dimensional generative modeling via jump diffusion models,
2023.
URL [https://arxiv.org/abs/2305.16261](https://arxiv.org/abs/2305.16261).
- Cao & Kipf (2022)
Nicola De Cao and Thomas Kipf.
Molgan: An implicit generative model for small molecular graphs,
2022.
URL [https://arxiv.org/abs/1805.11973](https://arxiv.org/abs/1805.11973).
- Gat et al. (2024)
Itai Gat, Tal Remez, Neta Shaul, Felix Kreuk, Ricky T. Q. Chen, Gabriel
Synnaeve, Yossi Adi, and Yaron Lipman.
Discrete flow matching, 2024.
URL [https://arxiv.org/abs/2407.15595](https://arxiv.org/abs/2407.15595).
- Graves et al. (2025)
Alex Graves, Rupesh Kumar Srivastava, Timothy Atkinson, and Faustino Gomez.
Bayesian flow networks, 2025.
URL [https://arxiv.org/abs/2308.07037](https://arxiv.org/abs/2308.07037).
- Guo & Zhao (2022)
Xiaojie Guo and Liang Zhao.
A systematic survey on deep generative models for graph generation,
2022.
URL [https://arxiv.org/abs/2007.06686](https://arxiv.org/abs/2007.06686).
- Haefeli et al. (2023)
Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger
Wattenhofer.
Diffusion models for graphs benefit from discrete state spaces, 2023.
URL [https://arxiv.org/abs/2210.01549](https://arxiv.org/abs/2210.01549).
- Ho et al. (2020)
Jonathan Ho, Ajay Jain, and Pieter Abbeel.
Denoising diffusion probabilistic models, 2020.
URL [https://arxiv.org/abs/2006.11239](https://arxiv.org/abs/2006.11239).
- Jo et al. (2022)
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang.
Score-based generative modeling of graphs via the system of
stochastic differential equations, 2022.
URL [https://arxiv.org/abs/2202.02514](https://arxiv.org/abs/2202.02514).
- Jo et al. (2024)
Jaehyeong Jo, Dongki Kim, and Sung Ju Hwang.
Graph generation with diffusion mixture, 2024.
URL [https://arxiv.org/abs/2302.03596](https://arxiv.org/abs/2302.03596).
- Karras et al. (2022)
Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine.
Elucidating the design space of diffusion-based generative models,
2022.
URL [https://arxiv.org/abs/2206.00364](https://arxiv.org/abs/2206.00364).
- Kingma & Welling (2013)
Diederik P Kingma and Max Welling.
Auto-encoding variational bayes, 2013.
URL [https://arxiv.org/abs/1312.6114](https://arxiv.org/abs/1312.6114).
- Kipf & Welling (2016)
Thomas N. Kipf and Max Welling.
Variational graph auto-encoders, 2016.
URL [https://arxiv.org/abs/1611.07308](https://arxiv.org/abs/1611.07308).
- Liao et al. (2020)
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L.
Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel.
Efficient graph generation with graph recurrent attention networks,
2020.
URL [https://arxiv.org/abs/1910.00760](https://arxiv.org/abs/1910.00760).
- Lienen et al. (2024)
Marten Lienen, David Lüdke, Jan Hansen-Palmus, and Stephan Günnemann.
From zero to turbulence: Generative modeling for 3d flow simulation.
In *ICLR*, 2024.
- Lienen et al. (2025)
Marten Lienen, Marcel Kollovieh, and Stephan Günnemann.
Generative modeling with bayesian sample inference, 2025.
URL [https://arxiv.org/abs/2502.07580](https://arxiv.org/abs/2502.07580).
- Liu et al. (2019)
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky.
Graph normalizing flows, 2019.
URL [https://arxiv.org/abs/1905.13177](https://arxiv.org/abs/1905.13177).
- Martinkus et al. (2022)
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer.
Spectre: Spectral conditioning helps to overcome the expressivity
limits of one-shot graph generators, 2022.
URL [https://arxiv.org/abs/2204.01613](https://arxiv.org/abs/2204.01613).
- Niu et al. (2020)
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano
Ermon.
Permutation invariant graph generation via score-based generative
modeling, 2020.
URL [https://arxiv.org/abs/2003.00638](https://arxiv.org/abs/2003.00638).
- Polykovskiy et al. (2020)
Daniil Polykovskiy, Alexander Zhebrak, Benjamin Sanchez-Lengeling, Sergey
Golovanov, Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey
Artamonov, Vladimir Aladinskiy, Mark Veselov, Artur Kadurin, Simon Johansson,
Hongming Chen, Sergey Nikolenko, Alan Aspuru-Guzik, and Alex Zhavoronkov.
Molecular Sets (MOSES): A Benchmarking Platform for
Molecular Generation Models.
*Frontiers in Pharmacology*, 2020.
- Preuer et al. (2018)
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and
Günter Klambauer.
Fréchet chemnet distance: A metric for generative models for
molecules in drug discovery.
*Journal of Chemical Information and Modeling*, 58(9):1736–1741, 2018.
doi: 10.1021/acs.jcim.8b00234.
URL [https://doi.org/10.1021/acs.jcim.8b00234](https://doi.org/10.1021/acs.jcim.8b00234).
PMID: 30118593.
- Qin et al. (2025)
Yiming Qin, Manuel Madeira, Dorina Thanou, and Pascal Frossard.
Defog: Discrete flow matching for graph generation, 2025.
URL [https://arxiv.org/abs/2410.04263](https://arxiv.org/abs/2410.04263).
- Siraudin et al. (2024)
Antoine Siraudin, Fragkiskos D. Malliaros, and Christopher Morris.
Cometh: A continuous-time discrete-state graph diffusion model, 2024.
URL [https://arxiv.org/abs/2406.06449](https://arxiv.org/abs/2406.06449).
- Sohl-Dickstein et al. (2015)
Jascha Sohl-Dickstein, Eric A. Weiss, Niru Maheswaranathan, and Surya Ganguli.
Deep unsupervised learning using nonequilibrium thermodynamics, 2015.
URL [https://arxiv.org/abs/1503.03585](https://arxiv.org/abs/1503.03585).
- Song et al. (2021)
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano
Ermon, and Ben Poole.
Score-based generative modeling through stochastic differential
equations, 2021.
URL [https://arxiv.org/abs/2011.13456](https://arxiv.org/abs/2011.13456).
- Song et al. (2024)
Yuxuan Song, Jingjing Gong, Hao Zhou, Mingyue Zheng, Jingjing Liu, and Wei-Ying
Ma.
Unified generative modeling of 3d molecules with bayesian flow
networks.
In *The Twelfth International Conference on Learning
Representations*, 2024.
URL [https://openreview.net/forum?id=NSVtmmzeRB](https://openreview.net/forum?id=NSVtmmzeRB).
- Song et al. (2025)
Yuxuan Song, Juntong Shi, Jingjing Gong, Minkai Xu, Stefano Ermon, Hao Zhou,
and Wei-Ying Ma.
Smooth interpolation for improved discrete graph generative models.
In *Forty-second International Conference on Machine Learning*,
2025.
URL [https://openreview.net/forum?id=OYUG5SCg6k](https://openreview.net/forum?id=OYUG5SCg6k).
- Tao & Abe (2025)
Nianze Tao and Minori Abe.
Bayesian flow network framework for chemistry tasks.
*Journal of Chemical Information and Modeling*, 65(3):1178–1187, 2025.
doi: 10.1021/acs.jcim.4c01792.
- Uhlenbeck & Ornstein (1930)
George Eugene Uhlenbeck and Leonard Salomon Ornstein.
On the theory of the brownian motion.
*Physical Review*, 36(5):823–841, 1930.
- Vaswani et al. (2017)
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones,
Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.
Attention is all you need.
*Advances in neural information processing systems*, 30, 2017.
- Vignac et al. (2023)
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and
Pascal Frossard.
Digress: Discrete denoising diffusion for graph generation, 2023.
URL [https://arxiv.org/abs/2209.14734](https://arxiv.org/abs/2209.14734).
- Xu et al. (2024)
Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan,
Zhichen Zeng, Mahashweta Das, and Hanghang Tong.
Discrete-state continuous-time diffusion for graph generation, 2024.
URL [https://arxiv.org/abs/2405.11416](https://arxiv.org/abs/2405.11416).
- Xue et al. (2024)
Kaiwen Xue, Yuhao Zhou, Shen Nie, Xu Min, Xiaolu Zhang, Jun Zhou, and Chongxuan
Li.
Unifying bayesian flow networks and diffusion models through
stochastic differential equations, 2024.
URL [https://arxiv.org/abs/2404.15766](https://arxiv.org/abs/2404.15766).
- You et al. (2018)
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec.
Graphrnn: Generating realistic graphs with deep auto-regressive
models, 2018.
URL [https://arxiv.org/abs/1802.08773](https://arxiv.org/abs/1802.08773).
- Zhu et al. (2022)
Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu
Wu.
A survey on deep graph generation: Methods and applications, 2022.
URL [https://arxiv.org/abs/2203.06714](https://arxiv.org/abs/2203.06714).

## Appendix A Relationship between Categorical BSI and Categorical BFNs

There is a close equivalence between Categorical Bayesian Sample Inference (BSI) and Categorical Bayesian Flow Networks (BFNs). In fact, Categorical BFNs can be seen as a special case of Categorical BSI with a specific choice of prior distribution and noise schedule. To illustrate this, we will show the relationship between the components of both frameworks.

Input Distribution Both BFNs and categorical BSI parameterize the distribution over the data $\mathbf{x}$ using a categorical distribution. The logits are denoted as $\mathbf{z}$ in BSI and as $\theta$ in BFNs. In BSI, the parameters $\mathbf{z}$ are the logits of a categorical distribution, i.e., $p(\mathbf{x}\mid\mathbf{z})\sim\mathrm{Cat}(\mathrm{softmax}(\mathbf{z}))$. In BFNs, the parameters $\theta$ are the probabilities of each category, i.e., $p(\mathbf{x}\mid\theta)\sim\mathrm{Cat}(\theta)$. The two parameterizations are equivalent since $\theta=\mathrm{softmax}(\mathbf{z})$ and $\mathbf{z}=\log(\theta)$ (up to an additive constant).

Output Distribution The output distribution in BFNs is an intermediate distribution that is not needed in BSI.

Prior Distribution While Categorical BSI includes a normal prior distribution over the logits of the categorical distribution $(p(\mathbf{z}\mid t=0)\sim\mathcal{N}(\bm{\mu}_{0},\beta_{0}I))$, Categorical BFNs fix the parameters to $\theta_{0}=1/K$. Therefore, categorical BFNs can be seen as a special case of categorical BSI with $\bm{\mu}_{0}=0$ and $\beta_{0}=0$.

Sender Distribution The sender distribution in categorical BFNs is an intermediate distribution that is not required in categorical BSI.

Receiver Distribution The sender distribution in categorical BFNs is given as

$$ $p_{R}(\mathbf{y}\mid\mathbf{x},\alpha)\sim\sum_{k}\mathrm{softmax}(\Psi(\theta))_{k}\mathcal{N}(\alpha(K\hat{e}_{k}-1),\alpha KI)$ $$

It corresponds to the noisy measurement distribution in categorical BSI, $p(\mathbf{y}\mid\mathbf{x},\alpha)\sim\mathcal{N}(\hat{\mathbf{x}},1/\alpha I)$. Note that for $\alpha\to 0$, it holds that:

$$ $p_{R}(\mathbf{y}\mid\mathbf{x},\alpha)\sim\mathcal{N}(\alpha(K\mathrm{softmax}(\Psi(\theta))-1),\alpha KI)$ $$

The sender distribution for $\alpha\to 0$ is an affine transformation of the noisy observation function for BSI: If we set $\mathbf{y}\sim p(\mathbf{y}\mid\mathbf{x},\alpha)=\mathcal{N}(\hat{\mathbf{x}},1/\alpha I)$ and compute $y^{\prime}=\alpha(K\mathbf{y}-1)$, then $y^{\prime}\sim p_{s}(y^{\prime}\mid\mathbf{x},\alpha)$, where $\mathrm{softmax}(\Psi(\theta))$ corresponds to the sample reconstruction $\hat{\mathbf{x}}$. Thus, the two distributions are equivalent up to an affine transformation of the variable and therefore contain the same information. However, in the formulation of categorical BSI, we can directly see that $\mathbf{y}$ is a noisy observation of $\mathbf{x}$ and we do not require computing the distribution as a limit of a multinomial distribution as in BFNs.

Bayesian Update Function The Bayesian update function in categorical BFNs (Graves et al., 2025, Eq. 171) is the equivalent of [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1) in categorical BSI. The update is simplified for BSI since the belief parameters are in logit space instead of probability space. Furthermore, the scaling of the receiver distribution leads to an extra factor of $\alpha$ in categorical BSI.

Bayesian Update Distribution This is an intermediate that is not required in categorical BSI.

Accuracy Schedule The accuracy schedule can be chosen freely in categorical BSI. In categorical BFNs, the accuracy schedule is fixed to $\beta(t)=t^{2}\beta(1)$.

Bayesian Flow Distribution The Bayesian flow distribution in categorical BFNs corresponds to [Eq. 3](https://arxiv.org/html/2511.03015v1#S2.E3) in categorical BSI. The two distributions are equivalent up to an affine transformation of the variable, as explained above.

Continuous Time Loss The continuous time loss in categorical BFNs (Graves et al., 2025, Eq. 205) corresponds to [Eq. 5](https://arxiv.org/html/2511.03015v1#S2.E5) in categorical BSI. Both are the L2 loss between the reconstruction and the one-hot encoded data.

SDE formulation Both BSI and BFN sampling can be formulated as SDEs. Here, [Theorem 3](https://arxiv.org/html/2511.03015v1#Thmtheorem3) corresponds to (Xue et al., 2024, Eq. 24). To do so, the authors also operate on the logits of the categorical distribution instead of the probabilities.

Score function approximation The score function approximation for categorical BFNs (Xue et al., 2024, Eq. 28) corresponds to [Theorem 5](https://arxiv.org/html/2511.03015v1#Thmtheorem5) for $\beta_{0}=0$ up to a constant. Note that a value of $\beta_{0}>0$ avoids the division by zero in the score function approximation at $t=0$.

## Appendix B Analysis of SDE-based Sampling Algorithms

In this section, we analyze the behavior of the SDE-based sampling methods [Algs. 3](https://arxiv.org/html/2511.03015v1#alg3) and [4](https://arxiv.org/html/2511.03015v1#alg4).

### B.1 Equivalence of the two Sampling Algorithms for Infinite Steps

It is worth noting that for $\Delta t\to 0$, the Ornstein-Uhlenbeck discretization and the Euler-Maruyama discretization of [Eq. 7](https://arxiv.org/html/2511.03015v1#S3.E7) converge to the same update step:

$$ $\displaystyle\mathbf{z}_{t+\Delta t}$ $\displaystyle\sim m+(\mathbf{z}_{t}-m)e^{-\kappa\Delta t}+\sqrt{\frac{\gamma\beta^{\prime}}{2\kappa}(1-e^{-2\kappa\Delta t})}\cdot\mathcal{N}(0,1)$ (11) $\displaystyle\to m+(\mathbf{z}_{t}-m)(1-\kappa\Delta t)+\sqrt{\frac{\gamma\beta^{\prime}}{2\kappa}(1-(1-2\kappa\Delta t))}\cdot\mathcal{N}(0,1)$ (12) $\displaystyle=\mathbf{z}_{t}+\kappa(m-\mathbf{z}_{t})\Delta t+\sqrt{\gamma\beta^{\prime}\Delta t}\cdot\mathcal{N}(0,1)$ (13) $\displaystyle=\mathbf{z}_{t}+\kappa(\bm{\mu}_{0}+(\beta+\beta^{\prime}/\kappa)\hat{\mathbf{x}}-\mathbf{z}_{t})\Delta t+\sqrt{\gamma\beta^{\prime}\Delta t}\cdot\mathcal{N}(0,1)$ (14) $\displaystyle=\mathbf{z}_{t}+\beta^{\prime}\hat{\mathbf{x}}\Delta t+\frac{\gamma-1}{2}\beta^{\prime}\frac{\bm{\mu}_{0}+\beta\hat{\mathbf{x}}-\mathbf{z}_{t}}{\beta+\beta_{0}}\Delta t+\sqrt{\gamma\beta^{\prime}\Delta t}\cdot\mathcal{N}(0,1)$ (15) $\displaystyle=\mathbf{z}_{t}+\beta^{\prime}f_{\theta}(\mathbf{z}_{t},t)\Delta t+\frac{\gamma-1}{2}\beta^{\prime}\nabla_{\mathbf{z}_{t}}\log p_{t}(\mathbf{z}_{t})\Delta t+\sqrt{\gamma\beta^{\prime}\Delta t}\cdot\mathcal{N}(0,1)$ (16) $$

### B.2 Stability of Euler-Maruyama Sampling

Let us explicitly write out the update step of the Euler-Maruyama discretization of [Eq. 7](https://arxiv.org/html/2511.03015v1#S3.E7):

$$ $\displaystyle\mathbf{z}_{t+\Delta t}$ $\displaystyle\sim\mathbf{z}_{t}+\beta^{\prime}\hat{\mathbf{x}}\Delta t+\frac{\gamma-1}{2}\beta^{\prime}\frac{\bm{\mu}_{0}+\beta\hat{\mathbf{x}}-\mathbf{z}_{t}}{\beta+\beta_{0}}\Delta t+\sqrt{\gamma\beta^{\prime}\Delta t}\cdot\mathcal{N}(0,1)$ (17) $\displaystyle=\left(1-\frac{(\gamma-1)\beta^{\prime}}{2(\beta+\beta_{0})}\Delta t\right)\mathbf{z}_{t}+\beta^{\prime}\hat{\mathbf{x}}\Delta t+\frac{(\gamma-1)\beta^{\prime}(\bm{\mu}_{0}+\beta\hat{\mathbf{x}})}{2(\beta+\beta_{0})}\Delta t+\sqrt{\gamma\beta^{\prime}\Delta t}\cdot\mathcal{N}(0,1)$ (18) $$

As a rule of thumb, the coefficient in front of $\mathbf{z}_{t}$ should not be negative, i.e., the previous step should not be over-corrected. This yields the condition

$$ $\displaystyle 1-\frac{(\gamma-1)\beta^{\prime}}{2(\beta+\beta_{0})}\Delta t$ $\displaystyle\geq 0$ (19) $\displaystyle\iff\Delta t\cdot(\gamma-1)$ $\displaystyle\leq\frac{2(\beta+\beta_{0})}{\beta^{\prime}}$ (20) $$

For our precision schedule on moses ($\beta_{\mathtt{start}}=3.0,\beta_{\mathtt{end}}=12.0,\beta_{0}=1.0$), we find that

$$ $\min_{t\in[0,1]}\frac{2(\beta(t)+\beta_{0})}{\beta^{\prime}(t)}\approx 0.48$ (21) $$

The resulting maximum stable noise level $\gamma$ for different numbers of sampling steps in [Tab. 3](https://arxiv.org/html/2511.03015v1#A2.T3) predicts the observed behavior in [Fig. 3](https://arxiv.org/html/2511.03015v1#S4.F3) surprisingly well.

**Table 3: Maximum stable $\gamma$ for different numbers of sampling steps with the Euler-Maruyama discretization, following [Eq. 21](https://arxiv.org/html/2511.03015v1#A2.E21).**
| Number of Timesteps | $\Delta t$ | Maximum Stable $\gamma$ |
| --- | --- | --- |
| 25 | 0.040000 | 12.938480 |
| 50 | 0.020000 | 24.876960 |
| 100 | 0.010000 | 48.753920 |
| 200 | 0.005000 | 96.507840 |
| 500 | 0.002000 | 239.769601 |

### B.3 Behavior of Ornstein-Uhlenbeck Sampling with Infinite Noise

Taking the limit $\gamma\to\infty$ in [Alg. 4](https://arxiv.org/html/2511.03015v1#alg4) yields an interesting sampling algorithm (see [Alg. 5](https://arxiv.org/html/2511.03015v1#alg5)). In this limit, the update step becomes independent of the previous step $\mathbf{z}_{t}$, replacing all previous information with the current prediction $\hat{\mathbf{x}}$. Empirically, we find that fixing the prior value after the initial sampling step, as shown in [Alg. 6](https://arxiv.org/html/2511.03015v1#alg6), works better in practice (see [Tab. 4](https://arxiv.org/html/2511.03015v1#A2.T4)). This algorithm matches the Flowback algorithm from Song et al. (2025). We find that with a budget of 50 sampling steps, this algorithm performs surprisingly well on molecule generation. However, a higher compute budget drastically reduces performance. We hypothesize that this is because an excessive amount of stochasticity is introduced.
Song et al. (2025) address this by adaptively alternating between vanilla BFN steps and Flowback steps, effectively mixing [Alg. 1](https://arxiv.org/html/2511.03015v1#alg1) with [Alg. 5](https://arxiv.org/html/2511.03015v1#alg5).

Figure: Algorithm 5 Sampling with $\gamma\to\infty$

Figure: Algorithm 6 Fixed-prior sampling with $\gamma\to\infty$

Table: Table 4: Results on the GuacaMol and Moses benchmarks for molecular generation with 50 and 500 sampling steps and the Euler- (EM) and Ornstein-Uhlenbeck (OU) discretization, and with [Alg. 5](https://arxiv.org/html/2511.03015v1#alg5) ($\gamma\to\infty$) and [Alg. 6](https://arxiv.org/html/2511.03015v1#alg6) ($\gamma\to\infty$, FP)

## Appendix C Proofs

###### Theorem 1 .

Given a prior belief $p(\mathbf{x}\mid\mathbf{z})=\mathrm{Cat}(\mathbf{x}\mid\mathrm{softmax}(\mathbf{z}))$, after observing $\mathbf{y}\sim\mathcal{N}(\mathbf{y}\mid\mu=\mathbf{x},\Sigma^{2}=1/\alpha I)$ at precision $\alpha$, the posterior belief is $p(\mathbf{x}\mid\mathbf{z},\mathbf{y},\alpha)=\mathrm{Cat}(\mathbf{x}\mid\mathrm{softmax}(\mathbf{z}_{\mathrm{post}}))$ with

$$ $\mathbf{z}_{\mathrm{post}}=\mathbf{z}+\alpha\cdot\mathbf{y}$ (22) $$

###### Proof.

We need to compute the Bayesian update of the belief parameters. Each dimension can be considered independently since the noise is isotropic. Let us start with a single-variable prior belief $\mathrm{Cat}(\mathrm{softmax}(\mathbf{z}))$ with $\mathbf{z}\in\mathbb{R}^{c}$, and a noisy observation $\mathbf{y}\mid\mathbf{x},\alpha\sim\mathcal{N}(\mu=\mathbf{x},\Sigma^{2}=1/\alpha\cdot I)$ of the true sample $\mathbf{x}\in\Delta^{c-1}$ at precision $\alpha$. Let us now consider any class $l\in{1,\dots,c}$. We write $\hat{e}_{l}$ for the one-hot encoding of class $l$. Since we are only interested in the ratio of the posterior probabilities, we can ignore any factors that do not depend on $l$ and normalize at the end. We have:

$$ $\displaystyle p(\mathbf{x}=\hat{e}_{l}\mid\mathbf{z})$ $\displaystyle=\mathrm{softmax}(\mathbf{z})_{l}\propto\exp(\mathbf{z}_{l})$ (23) $\displaystyle p(\mathbf{y}\mid\mathbf{x}=\hat{e}_{l},\alpha)$ $\displaystyle=\mathcal{N}(\mathbf{y}|\mu=\hat{e}_{l},\Sigma^{2}=1/\alpha\cdot I)$ (24) $\displaystyle p(\mathbf{x}=\hat{e}_{l}\mid\mathbf{z},\mathbf{y},\alpha)$ $\displaystyle=\propto p(\mathbf{y}\mid\mathbf{x}=\hat{e}_{l},\alpha)\cdot p(\mathbf{x}=\hat{e}_{l}\mid\mathbf{z})$ (25) $\displaystyle=\mathcal{N}(\mathbf{y}\mid\mu=\hat{e}_{l},\Sigma^{2}=1/\alpha\cdot I)\cdot\mathrm{softmax}(\mathbf{z})_{l}$ (26) $\displaystyle\propto\exp\left(-\frac{||\mathbf{y}-\hat{e}_{l}||^{2}}{2\cdot 1/\alpha}\right)\cdot\exp(\mathbf{z}_{l})$ (27) $\displaystyle=\exp\left(-\frac{||\mathbf{y}||^{2}-2\cdot\langle\mathbf{y},\hat{e}_{l}\rangle+||\hat{e}_{l}||^{2}}{2\cdot 1/\alpha}+\mathbf{z}_{l}\right)$ (28) $\displaystyle\propto\exp\left(\alpha\cdot\mathbf{y}_{l}+\mathbf{z}_{l}\right)$ (29) $$

Let us now normalize the results to obtain the posterior probabilities:

$$ $\displaystyle p(\mathbf{x}=\hat{e}_{l}\mid\mathbf{z},\mathbf{y},\alpha)$ $\displaystyle=\frac{\exp\left(\alpha\cdot\mathbf{y}_{l}+\mathbf{z}_{l}\right)}{\sum_{l^{\prime}=1}^{c}\exp\left(\alpha\cdot\mathbf{y}_{l^{\prime}}+\mathbf{z}_{l^{\prime}}\right)}=\mathrm{softmax}(\mathbf{z}+\alpha\cdot\mathbf{y})_{l}$ (30) $$

Putting everything together, we find that the posterior belief is $p(\mathbf{x}\mid\mathbf{z},\mathbf{y},\alpha)=\mathrm{Cat}(\mathbf{x}\mid\mathrm{softmax}(\mathbf{z}_{\mathrm{post}}))$ with

$$ $\mathbf{z}_{\mathrm{post}}=\mathbf{z}+\alpha\cdot\mathbf{y}$ (31) $$

∎

###### Theorem 2 .

For categorical BSI, the log-likelihood of $\mathbf{x}$ under [Alg. 1](https://arxiv.org/html/2511.03015v1#alg1) is lower-bounded by

$$ $\log p(\mathbf{x})\geq\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}\mathbf{z}_{k}\sim q(\mathbf{z}|\mathbf{x},t_{k})\end{subarray}}[\log p(\mathbf{x}\mid\mathbf{z}_{k})]-\frac{k}{2}\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}i\sim\mathcal{U}(0,k-1)\\ \mathbf{z}_{i}\sim q(\mathbf{z}|\mathbf{x},t_{i})\end{subarray}}[(\beta(t_{i+1})-\beta(t_{i}))||f_{\theta}(\mathbf{z}_{i},t_{i})-\mathbf{x}||_{2}^{2}],$ (32) $$

where $q(\mathbf{z}\mid\mathbf{x},t)=\mathcal{N}(\mathbf{z}\mid\bm{\mu}_{0}+\beta(t)\mathbf{x},\beta_{0}+\beta(t)I)$.

###### Proof.

For any distribution $p(\mathbf{x})$ and any latent variable $\mathbf{z}$, i.e. any choice of prior $p(\mathbf{z})$, encoding distribution $p(\mathbf{z}\mid\mathbf{x})$, and likelihood $p(\mathbf{x}\mid\mathbf{z})$, we have the variational lower bound

$$ $\log p(\mathbf{x})\geq\operatorname*{\mathbb{E}}_{\mathbf{z}\sim p(\mathbf{z}\mid\mathbf{x})}[\log p(\mathbf{x}\mid\mathbf{z})]-\mathrm{KL}(p(\mathbf{z}\mid\mathbf{x})\|p(\mathbf{z}))$ (33) $$

on $\log p(\mathbf{x})$ Kingma & Welling (2013). We choose the beliefs $\mathbf{z}_{0},\dots,\mathbf{z}_{k}$ as latent variables at the discretized time steps $t_{0},\dots,t_{k}$. We choose the encoding distribution to be the distribution of the beliefs under [Alg. 1](https://arxiv.org/html/2511.03015v1#alg1) with the reconstruction network $f_{\theta}$ replaced by the true sample $\mathbf{x}$:

$$ $p(\mathbf{z}_{0},\dots,\mathbf{z}_{k}\mid\mathbf{x})=\mathcal{N}(\mathbf{z}_{0}\mid\bm{\mu}_{0},\beta_{0}I)\prod_{i=0}^{k-1}p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},\mathbf{x},t_{i})$ (34) $$

The transition distribution $p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},\mathbf{x},t_{i})$ can be computed from [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1):

$$ $\mathbf{z}_{i+1}=\mathbf{z}_{i}+\alpha_{i}\cdot\mathbf{y}_{i}\sim\mathbf{z}_{i}+\alpha_{i}\cdot\mathcal{N}(\mathbf{y}\mid\mu=\mathbf{x},1/\alpha_{i}I)=\mathcal{N}(\mathbf{z}_{i+1}\mid\mathbf{z}_{i}+\alpha_{i}\cdot\mathbf{x},\alpha_{i}I)$ (35) $$

The distribution of $p(\mathbf{z})$ following [Alg. 1](https://arxiv.org/html/2511.03015v1#alg1) factorizes similarly:

$$ $p(\mathbf{z}_{0},\dots,\mathbf{z}_{k})=\mathcal{N}(\mathbf{z}_{0}\mid\bm{\mu}_{0},\beta_{0}I)\prod_{i=0}^{k-1}p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},t_{i},\theta)$ (36) $$

with the transition distribution

$$ $p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},t_{i},\theta)=\mathcal{N}(\mathbf{z}_{i+1}\mid\mathbf{z}_{i}+\alpha_{i}\cdot f_{\theta}(\mathbf{z}_{i},t_{i}),\alpha_{i}I)$ (37) $$

Let us now compute the KL divergence:

$$ $\displaystyle\mathrm{KL}(p(\mathbf{z}_{0},\dots,\mathbf{z}_{k}\mid\mathbf{x})\|p(\mathbf{z}_{0},\dots,\mathbf{z}_{k}))$ (38) $\displaystyle=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{z}_{0},\dots,\mathbf{z}_{k}\sim\\ p(\mathbf{z}_{0},\dots,\mathbf{z}_{k}\mid\mathbf{x})\end{subarray}}\left[\log\frac{p(\mathbf{z}_{0},\dots,\mathbf{z}_{k}\mid\mathbf{x})}{p(\mathbf{z}_{0},\dots,\mathbf{z}_{k})}\right]$ (39) $\displaystyle=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{z}_{0},\dots,\mathbf{z}_{k}\sim\\ p(\mathbf{z}_{0},\dots,\mathbf{z}_{k}\mid\mathbf{x})\end{subarray}}\left[\log\frac{\mathcal{N}(\mathbf{z}_{0}\mid\bm{\mu}_{0},\beta_{0}I)\prod_{i=0}^{k-1}p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},\mathbf{x},t_{i})}{\mathcal{N}(\mathbf{z}_{0}\mid\bm{\mu}_{0},\beta_{0}I)\prod_{i=0}^{k-1}p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},t_{i},\theta)}\right]$ (40) $\displaystyle=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{z}_{0},\dots,\mathbf{z}_{k}\sim\\ p(\mathbf{z}_{0},\dots,\mathbf{z}_{k}\mid\mathbf{x})\end{subarray}}\left[\sum_{i=0}^{k-1}\log\frac{p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},\mathbf{x},t_{i})}{p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},t_{i},\theta)}\right]$ (41) $\displaystyle=\sum_{i=0}^{k-1}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{z}_{i}\sim p(\mathbf{z}_{i}\mid\mathbf{x})\end{subarray}}\left[\mathrm{KL}(p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},\mathbf{x},t_{i})\|p(\mathbf{z}_{i+1}\mid\mathbf{z}_{i},t_{i},\theta))\right]$ (42) $\displaystyle=\sum_{i=0}^{k-1}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{z}_{i}\sim p(\mathbf{z}_{i}\mid\mathbf{x})\end{subarray}}\left[\mathrm{KL}(\mathcal{N}(\mathbf{z}_{i+1}\mid\mathbf{z}_{i}+\alpha_{i}\cdot\mathbf{x},\alpha_{i}I)\|\mathcal{N}(\mathbf{z}_{i+1}\mid\mathbf{z}_{i}+\alpha_{i}\cdot f_{\theta}(\mathbf{z}_{i},t_{i}),\alpha_{i}I))\right]$ (43) $\displaystyle=\sum_{i=0}^{k-1}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{z}_{i}\sim p(\mathbf{z}_{i}\mid\mathbf{x})\end{subarray}}\left[\frac{1}{2\alpha_{i}}||\mathbf{z}_{i}+\alpha_{i}\cdot\mathbf{x}-(\mathbf{z}_{i}+\alpha_{i}\cdot f_{\theta}(\mathbf{z}_{i},t_{i}))||_{2}^{2}\right]$ (44) $\displaystyle=\sum_{i=0}^{k-1}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{z}_{i}\sim p(\mathbf{z}_{i}\mid\mathbf{x})\end{subarray}}\left[\frac{\alpha_{i}}{2}||\mathbf{x}-f_{\theta}(\mathbf{z}_{i},t_{i})||_{2}^{2}\right]$ (45) $\displaystyle=\sum_{i=0}^{k-1}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}\mathbf{z}_{i}\sim p(\mathbf{z}_{i}\mid\mathbf{x})\end{subarray}}\left[(\beta(t_{i+1})-\beta(t_{i}))/2||\mathbf{x}-f_{\theta}(\mathbf{z}_{i},t_{i})||_{2}^{2}\right]$ (46) $\displaystyle=\operatorname*{\mathbb{E}}_{\begin{subarray}{c}i\sim\mathcal{U}(0,k-1)\\ \mathbf{z}_{i}\sim p(\mathbf{z}_{i}\mid\mathbf{x})\end{subarray}}\left[\frac{k}{2}(\beta(t_{i+1})-\beta(t_{i}))||\mathbf{x}-f_{\theta}(\mathbf{z}_{i},t_{i})||_{2}^{2}\right]$ (47) $$

Since $p(\mathbf{x}\mid\mathbf{z}_{0},\dots,\mathbf{z}_{k})=p(\mathbf{x}\mid\mathbf{z}_{k})=\mathrm{Cat}(\mathbf{x}\mid\mathrm{softmax}(\mathbf{z}_{k}))$, we can plug in [Eq. 3](https://arxiv.org/html/2511.03015v1#S2.E3) to obtain the final result:

$$ $\log p(\mathbf{x})\geq\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}\mathbf{z}_{k}\sim q(\mathbf{z}|\mathbf{x},t_{k})\end{subarray}}[\log p(\mathbf{x}\mid\mathbf{z}_{k})]-\frac{k}{2}\operatorname*{\mathbb{E}}\limits_{\begin{subarray}{c}i\sim\mathcal{U}(0,k-1)\\ \mathbf{z}_{i}\sim q(\mathbf{z}|\mathbf{x},t_{i})\end{subarray}}[(\beta(t_{i+1})-\beta(t_{i}))||f_{\theta}(\mathbf{z}_{i},t_{i})-\mathbf{x}||_{2}^{2}],$ (48) $$

where $q(\mathbf{z}\mid\mathbf{x},t)=\mathcal{N}(\mathbf{z}\mid\bm{\mu}_{0}+\beta(t)\mathbf{x},\beta_{0}+\beta(t)I)$.
∎

###### Theorem 3 .

As $\Delta t\to 0$, the update equation in [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1) converges to the following SDE:

$$ $\displaystyle d\mathbf{z}_{t}$ $\displaystyle=\beta^{\prime}(t)f_{\theta}(\mathbf{z}_{t},t)dt+\sqrt{\beta^{\prime}(t)}dW_{t}$ (49) $$

where $dW_{t}$ is a Wiener process and $\mathbf{z}_{0}\sim\mathcal{N}(\bm{\mu}_{0},\beta_{0}\cdot I)$.

###### Proof.

Take the update equation [Theorem 1](https://arxiv.org/html/2511.03015v1#Thmtheorem1) with an infinitesimal time step $\Delta t\to 0$, it holds that

$$ $\alpha=(\beta(t+\Delta t)-\beta(t))\to\beta^{\prime}(t)\Delta t$ (50) $$

Therefore, we have:

$$ $\displaystyle\mathbf{z}_{t+\Delta t}$ $\displaystyle=\mathbf{z}_{t}+\alpha\mathbf{y}$ (51) $\displaystyle\sim\mathbf{z}_{t}+\alpha\mathcal{N}(\hat{\mathbf{x}},\Sigma^{2}=1/\alpha I)$ (52) $\displaystyle=\mathbf{z}_{t}+\mathcal{N}(\alpha\hat{\mathbf{x}},\Sigma^{2}=\alpha I)$ (53) $\displaystyle\to\mathbf{z}_{t}+\beta^{\prime}(t)\hat{\mathbf{x}}\Delta t+\sqrt{\beta^{\prime}(t)}\sqrt{\Delta t}\cdot\mathcal{N}(0,\mathbf{I})$ (54) $$

We identify this as the Euler-Maruyama discretization of the SDE above.
∎

###### Theorem 4 .

The SDE in [Theorem 3](https://arxiv.org/html/2511.03015v1#Thmtheorem3) is generalized by the following family of SDEs with equal marginal densities $p_{t}(\mathbf{z}_{t})$:

$$ $\displaystyle d\mathbf{z}_{t}$ $\displaystyle=\beta^{\prime}(t)f_{\theta}(\mathbf{z}_{t},t)dt+\frac{\gamma-1}{2}\beta^{\prime}(t)\nabla_{\mathbf{z}_{t}}\log p_{t}(\mathbf{z}_{t})dt+\sqrt{\gamma\beta^{\prime}(t)}dW_{t}$ (55) $$

where $dW_{t}$ is a Wiener process and $\mathbf{z}_{0}\sim p(\mathbf{z}\mid t=0)$.

###### Proof.

We need to show that the evolution of the probability density $p_{t}(\mathbf{z}_{t})$ of [Eq. 6](https://arxiv.org/html/2511.03015v1#S3.E6) matches that of [Eq. 7](https://arxiv.org/html/2511.03015v1#S3.E7). The evolution is characterized by the Fokker-Planck equation:

$$ $\displaystyle\frac{\partial p_{t}(\mathbf{z}_{t})}{\partial t}=\sum_{j}-\nabla_{\mathbf{z}_{j}}\left(\beta^{\prime}(t)f_{\theta}(\mathbf{z}_{t},t)+\frac{\gamma-1}{2}\beta^{\prime}(t)\nabla_{\mathbf{z}_{t}}\log p_{t}(\mathbf{z}_{t})\right)p_{t}(\mathbf{z}_{t})+\frac{1}{2}\gamma\beta^{\prime}(t)\nabla_{\mathbf{z}_{j}}^{2}p_{t}(\mathbf{z}_{t})$ $\displaystyle=\sum_{j}-\nabla_{\mathbf{z}_{j}}\left(\beta^{\prime}(t)f_{\theta}(\mathbf{z}_{t},t)p_{t}(\mathbf{z}_{t})\right)-\frac{\gamma-1}{2}\beta^{\prime}(t)\nabla_{\mathbf{z}_{j}}\left(p_{t}(\mathbf{z}_{t})\nabla_{\mathbf{z}_{j}}\log p_{t}(\mathbf{z}_{t})\right)+\frac{1}{2}\gamma\beta^{\prime}(t)\nabla_{\mathbf{z}_{j}}^{2}p_{t}(\mathbf{z}_{t})$ $\displaystyle=\sum_{j}-\nabla_{\mathbf{z}_{j}}\left(\beta^{\prime}(t)f_{\theta}(\mathbf{z}_{t},t)p_{t}(\mathbf{z}_{t})\right)-\frac{\gamma-1}{2}\beta^{\prime}(t)\nabla_{\mathbf{z}_{j}}^{2}p_{t}(\mathbf{z}_{t})+\frac{1}{2}\gamma\beta^{\prime}(t)\nabla_{\mathbf{z}_{j}}^{2}p_{t}(\mathbf{z}_{t})$ $\displaystyle=\sum_{j}-\nabla_{\mathbf{z}_{j}}\left(\beta^{\prime}(t)f_{\theta}(\mathbf{z}_{t},t)p_{t}(\mathbf{z}_{t})\right)+\frac{1}{2}\beta^{\prime}(t)\nabla_{\mathbf{z}_{j}}^{2}p_{t}(\mathbf{z}_{t})$ $$

Which equals the Fokker-Planck equation of the SDE in [Eq. 6](https://arxiv.org/html/2511.03015v1#S3.E6).
∎

###### Theorem 5 .

The BSI loss [Eq. 5](https://arxiv.org/html/2511.03015v1#S2.E5) also is a score matching loss with the score model $s_{\theta}(\mathbf{z},t)$ parameterized as

$$ $s_{\theta}(\mathbf{z},t)\equiv\frac{\bm{\mu}_{0}+\beta(t)f_{\theta}(\mathbf{z},t)-\mathbf{z}}{\beta(t)+\beta_{0}}\overset{!}{\approx}\nabla_{\mathbf{z}}\log p_{t}(\mathbf{z})$ (56) $$

###### Proof.

Score matching Song et al. (2021) is a generative model that learns to approximate the score function $\nabla_{\mathbf{z}}\log p_{t}(\mathbf{z})$ of a distribution $p_{t}(\mathbf{z})$ by minimizing the score matching loss:

$$ $\mathcal{L}_{\mathtt{score}}\equiv\mathbb{E}_{t\sim\mathcal{U}(0,1)}[\lambda(t)\mathbb{E}_{p(\mathbf{x})}\mathbb{E}_{p_{t}(\mathbf{z}\mid\mathbf{x})}\left[\|s_{\theta}(\mathbf{z},t)-\nabla_{\mathbf{z}}\log p_{t}(\mathbf{z}\mid\mathbf{x})\|_{2}^{2}\right]]$ (57) $$

where $\lambda:[0,1]\mapsto\mathbb{R}^{+}$ is a positive weighting function. The distribution $p_{t}(\mathbf{z}\mid\mathbf{x})$ is the distribution of the latent variable at time $t$ given the true sample $\mathbf{x}$.
For categorical BSI, we have from [Eq. 3](https://arxiv.org/html/2511.03015v1#S2.E3):

$$ $p_{t}(\mathbf{z}\mid\mathbf{x})=\mathcal{N}(\mathbf{z}\mid\bm{\mu}_{0}+\beta(t)\mathbf{x},(\beta_{0}+\beta(t))I)$ (58) $$

The score function of an isotropic Gaussian can be computed in closed form:

$$ $\displaystyle\nabla_{\mathbf{z}}\log\mathcal{N}(\mathbf{z}\mid\mu,\sigma^{2}I)$ $\displaystyle=\nabla_{\mathbf{z}}\left(-\frac{||\mathbf{z}-\mu||^{2}}{2\sigma^{2}}\right)=-\frac{\mathbf{z}-\mu}{\sigma^{2}}$ (59) $$

Plugging in the parameters of $p_{t}(\mathbf{z}\mid\mathbf{x})$, we find:

$$ $\displaystyle\nabla_{\mathbf{z}}\log p_{t}(\mathbf{z}\mid\mathbf{x})$ $\displaystyle=-\frac{\mathbf{z}-(\bm{\mu}_{0}+\beta(t)\mathbf{x})}{\beta_{0}+\beta(t)}=\frac{\bm{\mu}_{0}+\beta(t)\mathbf{x}-\mathbf{z}}{\beta_{0}+\beta(t)}$ (61) $$

With the proposed score model parameterization $s_{\theta}(\mathbf{z},t)$, we find:

$$ $\displaystyle\mathcal{L}_{\mathtt{score}}=\mathbb{E}_{t\sim\mathcal{U}(0,1)}[\lambda(t)\mathbb{E}_{p(\mathbf{x})}\mathbb{E}_{p_{t}(\mathbf{z}\mid\mathbf{x})}\left[\|s_{\theta}(\mathbf{z},t)-\nabla_{\mathbf{z}}\log p_{t}(\mathbf{z}\mid\mathbf{x})\|_{2}^{2}\right]]$ (62) $\displaystyle=\mathbb{E}_{t\sim\mathcal{U}(0,1)}[\lambda(t)\mathbb{E}_{p(\mathbf{x})}\mathbb{E}_{p_{t}(\mathbf{z}\mid\mathbf{x})}\left[\left\|\frac{\bm{\mu}_{0}+\beta(t)f_{\theta}(\mathbf{z},t)-\mathbf{z}}{\beta(t)+\beta_{0}}-\frac{\bm{\mu}_{0}+\beta(t)\mathbf{x}-\mathbf{z}}{\beta_{0}+\beta(t)}\right\|_{2}^{2}\right]]$ (63) $\displaystyle=\mathbb{E}_{t\sim\mathcal{U}(0,1)}[\lambda(t)\mathbb{E}_{p(\mathbf{x})}\mathbb{E}_{p_{t}(\mathbf{z}\mid\mathbf{x})}\left[\left\|\frac{\beta(t)(f_{\theta}(\mathbf{z},t)-\mathbf{x})}{\beta(t)+\beta_{0}}\right\|_{2}^{2}\right]]$ (64) $\displaystyle=\mathbb{E}_{t\sim\mathcal{U}(0,1)}[\lambda(t)\frac{\beta(t)^{2}}{(\beta(t)+\beta_{0})^{2}}\mathbb{E}_{p(\mathbf{x})}\mathbb{E}_{p_{t}(\mathbf{z}\mid\mathbf{x})}\left[\left\|(f_{\theta}(\mathbf{z},t)-\mathbf{x})\right\|_{2}^{2}\right]]$ (65) $$

Choosing the weighting $\lambda(t)=\beta^{\prime}(t)\frac{(\beta(t)+\beta_{0})^{2}}{\beta(t)^{2}}$, we find that the score matching loss equals the BSI loss in [Eq. 5](https://arxiv.org/html/2511.03015v1#S2.E5).
∎

###### Theorem 6 .

Fixing the prediction $\hat{\mathbf{x}}=f_{\theta}(\mathbf{z}_{t},t)$ and the values $\beta=\beta(t+\Delta t/2)$, $\beta^{\prime}=\beta^{\prime}(t+\Delta t/2)$ in [Eq. 7](https://arxiv.org/html/2511.03015v1#S3.E7) in a time interval $[t,t+\Delta t]$ yields an Ornstein-Uhlenbeck process with the exact marginal

$$ $\mathbf{z}_{t+\Delta t}\sim m+(\mathbf{z}_{t}-m)e^{-\kappa\Delta t}+\sqrt{\frac{\gamma\beta^{\prime}}{2\kappa}(1-e^{-2\kappa\Delta t})}\cdot\mathcal{N}(0,I),$ (67) $$

where $\kappa=\frac{(\gamma-1)\beta^{\prime}}{2(\beta_{0}+\beta)}$, $m=\bm{\mu}_{0}+(\beta+\beta^{\prime}/\kappa)\hat{\mathbf{x}}$.

###### Proof.

The SDE in [Eq. 7](https://arxiv.org/html/2511.03015v1#S3.E7) with fixed parameters $\beta,\beta^{\prime},\hat{\mathbf{x}}$ is given as

$$ $\displaystyle d\mathbf{z}_{t}$ $\displaystyle=\beta^{\prime}\hat{\mathbf{x}}dt+\frac{\gamma-1}{2}\beta^{\prime}\nabla_{\mathbf{z}_{t}}\log p_{t}(\mathbf{z}_{t})dt+\sqrt{\gamma\beta^{\prime}}dW_{t}$ (68) $$

where $dW_{t}$ is a Wiener process and $\mathbf{z}_{t}\sim p(\mathbf{z}\mid t)$. Let us insert [Theorem 5](https://arxiv.org/html/2511.03015v1#Thmtheorem5) to obtain

$$ $\displaystyle d\mathbf{z}_{t}$ $\displaystyle=\beta^{\prime}\hat{\mathbf{x}}dt+\frac{\gamma-1}{2}\beta^{\prime}\frac{\bm{\mu}_{0}+\beta f_{\theta}(\mathbf{z}_{t},t)-\mathbf{z}_{t}}{\beta+\beta_{0}}dt+\sqrt{\gamma\beta^{\prime}}dW_{t}$ (69) $\displaystyle=\frac{(\gamma-1)\beta^{\prime}}{2(\beta_{0}+\beta)}\left(\bm{\mu}_{0}+\left(\beta+\frac{2(\beta_{0}+\beta)}{\gamma-1}\right)\hat{\mathbf{x}}-\mathbf{z}_{t}\right)dt+\sqrt{\gamma\beta^{\prime}}dW_{t}$ (70) $$

Setting $\kappa=\frac{(\gamma-1)\beta^{\prime}}{2(\beta_{0}+\beta)}$ and $m=\bm{\mu}_{0}+(\beta+\beta^{\prime}/\kappa)\hat{\mathbf{x}}$, we find

$$ $d\mathbf{z}_{t}=\kappa(m-\mathbf{z}_{t})dt+\sqrt{\gamma\beta^{\prime}}dW_{t}$ (71) $$

which is an Ornstein-Uhlenbeck process. The exact marginal distribution of an Ornstein-Uhlenbeck process is given as Uhlenbeck & Ornstein (1930):

$$ $\mathbf{z}_{t+\Delta t}\sim m+(\mathbf{z}_{t}-m)e^{-\kappa\Delta t}+\sqrt{\frac{\gamma\beta^{\prime}}{2\kappa}(1-e^{-2\kappa\Delta t})}\cdot\mathcal{N}(0,I)$ (72) $$

∎

###### Theorem 1 .

###### Proof.

###### Theorem 2 .

###### Proof.

###### Theorem 3 .

###### Proof.

###### Theorem 4 .

###### Proof.

###### Theorem 5 .

###### Proof.

###### Theorem 6 .

###### Proof.

## Appendix D Additional Results

Figure: Figure 5: Results on the QM9 dataset.
Refer to caption: x8.png

[Fig. 5](https://arxiv.org/html/2511.03015v1#A4.F5) shows our method is competitive on the QM9 dataset with removed hydrogen atoms, achieving state-of-the-art results on validity and FCD. We explicitly model charges on the nodes, enabling high validity scores.

Table: Table 5: Hyperparameters used for the results in [Tabs. 1](https://arxiv.org/html/2511.03015v1#S4.T1) and [2](https://arxiv.org/html/2511.03015v1#S4.T2). The precision schedule is parameterized as $\beta(t)=\beta_{\mathtt{start}}\cdot(\exp(t\cdot\log(\beta_{\mathtt{end}}/\beta_{\mathtt{start}}))-1)$.

**Table 6: Datasets with training samples and maximum number of nodes.**
| Dataset | Train samples | Max. Nodes |
| --- | --- | --- |
| GuacaMol (Brown et al., 2019) | 1.3M | 88 |
| Moses (Polykovskiy et al., 2020) | 1.6M | 30 |
| Planar (Martinkus et al., 2022) | 128 | 64 |
| SBM (Martinkus et al., 2022) | 128 | 187 |
| Tree (Bergmeister et al., 2024) | 128 | 64 |

Table: Table 7: Molecular metrics

Table: Table 8: Synthetic graph metrics metrics

## Peer Reviews

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: 1) Could you add a minimal appendix probe comparing means/covariances of $z_t$ across a few $t$ and $\gamma$ values as an intuitive check for the “same marginal” claim? This can be very lightweight.  
2) For Theorem 5, do you plan to include the missing $\tfrac{1}{2}$ factor in a revision/erratum and explicitly state the condition under which it is strictly aligned with Eq.(5)?  
3) For the final decoding, which default path do you recommend—**categorical sampling** or **argmax quantization**—and why (stability, diversity, alignment with prior work)?  
4) If adding figures is difficult, would you consider providing a reference configuration in the repo for a “**same wall-clock budget**” comparison (fixed batch/GPU/time) so others can verify fairness?  
5) For the “affine equivalence” phrasing, would you consider noting in the appendix that “same-order approximation” is more accurate when covariance scalings differ, to avoid readers inferring strict equivalence?
soundness: 3
strengths: - **Originality**: Systematically ports BSI to **discrete/categorical graphs** and unifies deterministic ODE and stochastic sampling paths via **SDE + controllable noise**. This “bridging” removes some practical limitations of prior BFN-style derivations and constitutes originality via domain adaptation and simplification.  
- **Quality**: A clear training objective (ELBO) and a family of samplers (controlled by $\gamma$) are provided, with strong **inference efficiency** (competitive at low NFE). Ablations on $\gamma$ and time grids are helpful; engineering appears solid.  
- **Clarity**: Key intuitions (“belief contraction,” “same marginal family”) are conveyed through diagrams and concise algorithms; the separation of main text and appendix reads well.  
- **Significance**: For **discrete structure generation** (notably molecular graphs), the **low-step, efficient** generation is practically relevant. Methodologically, it offers a clean, implementable link between BFN/BSI and diffusion-SDE paradigms, with potential impact on broader discrete domains.
summary: The paper extends Bayesian Sample Inference (BSI) to categorical/graph generation, introduces an SDE view with a controllable noise family ($\gamma$), and studies two discretizations (EM/OU). On molecular benchmarks, the method achieves competitive performance with relatively few function evaluations (e.g., 50/500 NFE). The contribution is integration-oriented: it adapts BFN/BSI ideas to discrete graphs with a clearer Bayesian update and an SDE formulation, offering a tunable trade-off between speed and quality. The writing is generally clear, but several theoretical statements and implementation details would benefit from refinement.
weaknesses: 1) **ELBO Reconstruction Term** In the main theorem, the reconstruction term is written as $\mathbb{E}[p(x|z)]$ instead of the standard $\mathbb{E}[\log p(x|z)]$. While the conclusion that this term is independent of $\theta$ still holds, the ELBO should use the expected log-likelihood. Please unify the notation in the main text and appendix.

2) **Weighting in Theorem 5** To be strictly consistent with the loss in the main text, a factor $\tfrac{1}{2}$ is needed, i.e.,  
$$
\lambda(t) = \frac{\beta'(t)}{2} \cdot \frac{(\beta(t) + \beta_0)^2}{\beta(t)^2}.
$$  
The current statement may double the scaling. A short clarification aligning Theorem 5 with Eq. (5) would help.

3) **Over-Strong “Affine Equivalence” Wording** The appendix claims an affine equivalence between the receiver distribution and BSI observations, but the covariance scaling does not match exactly. A safer phrasing is “same-order approximation in the small- $\alpha$ limit,” avoiding over-commitment.

4) **Final Decoding Inconsistency** The text mentions sampling from $\mathrm{Cat}(\mathrm{softmax}(z))$ while algorithms return `Quantize(f_\theta(\cdot,1))`. Since sampling vs. quantization affects diversity and faithfulness differently, please unify the terminology and state the default choice with a brief rationale.

5) **Empirical Support for “Same Marginal” is Indirect** The claim that different $\gamma$ share the same marginal is mainly supported through downstream metrics. A lightweight check in $z$ -space (e.g., comparing first and second moments at a few $t$, $\gamma$) would make the claim more tangible—no large-scale new experiments needed.

6) **Comparative/Robustness Details Could Be Lightly Strengthened** If space permits, adding small variance bands over a few seeds on key plots or clarifying a “same wall-clock budget” comparison protocol would improve perceived fairness and reproducibility.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: See Weaknesses.
soundness: 3
strengths: Extends the Bayesian Sample Inference framework to discrete graphs.

Introduces both Euler–Maruyama and Ornstein–Uhlenbeck discretization schemes.

Outperforms baselines on key metrics with fewer sample steps.
summary: This paper presents GraphBSI, a new one-shot generative model for discrete graphs based on Bayesian Sample Inference (BSI).
Unlike conventional diffusion or Bayesian Flow Network (BFN) models, GraphBSI performs generation by refining a belief distribution in parameter space rather than evolving discrete samples directly. The authors derive a categorical BSI formulation and show that in the continuous-time limit, it becomes a stochastic differential equation (SDE). They further generalize this to a family of SDEs with a noise control parameter γ, allowing smooth interpolation between deterministic probability-flow ODEs and stochastic samplers. On standard molecule generation benchmarks (GuacaMol and MOSES), GraphBSI achieves  superior results across most metrics.
weaknesses: How sensitive is GraphBSI to the choice of the precision schedule β(t)? The paper only mentioned a monotonically increasing schedule.

Since GraphBSI is similar to BFN, a direct comparison with GraphBFN regarding training time would better highlight its practical advantages.

In addition, GraphBFN is not included in Table 2. Including GraphBFN results would allow for a clearer assessment of GraphBSI’s improvements over prior BFN-based approaches. The sampling_step=50 for GraphBSI is also missed in Table 2.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: 1. Which preprocessing procedure (which version of the implementation) the authors apply for the MOSES dataset?
2. Do you have results with 5 or 10 steps, since the method already reaches very high performance with only 50 steps?
3. How do the authors evaluate the robustness of the framework, separately in terms of hyperparameters during training, and sampling?
soundness: 2
strengths: The paper clearly presents the method being used. It is easy to follow.

It has a thorough structure, including theoretical guarantees and experimental analysis.

The experimental results are impressive, especially with only 50 steps.
summary: The paper proposed a method based on BSI for graph generation, achieving outstanding performance.
weaknesses: Regarding the soundness of the paper, it is not clear how this work relates to graphs, and it seems mainly adapted for discrete data, and the transformers and graph features mainly follow the previous work. I would like to ask the authors to clarify whether they are the first to adapt BSI to discrete data modalities. If yes, is the main approach is adding softmax operations on the original feature z used in common BSI?

Beyond that, I kindly ask the authors to clarify better the relationship between BSI and BFN. The paper states that BFN is a more generalizable version of BSI, but a more thorough discussion would help the reader understand the connection better. In terms of application, how does this help in your implementation or analysis, and what can BFN not achieve?

Additionally, mathematically, what is the difference between this method and a continuous diffusion on the simplex space, or a continuous diffusion on the logits space with softmax applied? If different, what makes BFN more advantageous than these normal diffusion formulations?

Clarifying these points would help me better understand the contribution of the paper.

---

confidence: 4
contribution: 2
initial_rating: 4
presentation: 3
questions: - Q1: Though the title states that the model is designated for graph generation, my main question is whether the model is specifically working for graph generation, or it can bring similar improvements to other discrete generation tasks. If this is designed for graph generation, I would like to see more on how can BSI improve the graph generation? If not and BSI can generally improve the discrete generation, it might be ideal to conduct generative tasks to modalities other than graphs, such as text modeling, protein co-design, etc[1][2]. 

- Q2: I look into the appendix and understand that the loss in eq. 5 is derived through the lower bound of log-likelihood. Honestly this is a bit surprised as from the assumption, the x is sampled from a softmax version of z, it seems cross-entropy loss to be more reasonable. Could the authors elaborate more on advantage of choosing the loss to be squared distance ? I am convinced with the derivation but It just seems a bit unnatural. 

- Q3: In the abstract, the authors claim that the advantage of BSI comes from introducing a continuous belief z that can better capture the evolution of dynamics. Would the authors provide more evidence/justification/intuition on why this works? 


[1] A. Campbell et al. A Continuous Time Framework for Discrete Denoising Models. NeurIPS 2023

[2] A. Campbell et al. Generative Flows on Discrete State-Spaces: Enabling Multimodal Flows with Applications to Protein Co-Design. ICML 2024
soundness: 2
strengths: - The proposed Discrete BSI presents a compelling and theoretically interesting mechanism for discrete data generation. The idea of operating on a continuous belief state to model the evolution of discrete variables addresses a key challenge in generative modeling.

- The application of BSI to graph generation yields significant performance improvements over state-of-the-art methods on established benchmarks like Moses and GuacaMol. This highlights the practical efficacy of the approach.

- The theoretical foundations are presented rigorously, with (mostly) well-stated theorems and proofs that are easy to follow.
summary: This paper introduces Discrete Bayesian Sampling Inference (BSI), a novel framework for graph generation. The core idea is to model the generative process not through discrete state transitions, but by evolving a continuous belief state, which is argued to better capture the dynamics of discrete variable evolution. The authors provide a theoretically grounded framework to derive the training and sampling methodologies. GraphBSI is evaluated on molecular graph generation benchmarks, where it demonstrates significant performance improvements over current state-of-the-art models.
weaknesses: - My primary concern is the precise positioning of the paper's contribution. It is somewhat ambiguous whether the main novelty lies in the general framework for discrete generation (placing it alongside with discrete diffusion, flow models, etc.) or specifically in its application to graph generation. Clarifying this would significantly strengthen the paper's impact by helping the reader understand its broader context and significance. Honestly I would be happy to improve the score if this question is properly addressed. 

- Insufficient Ablation of Performance Gains: While the empirical gains are impressive, the source of these improvements is not fully elucidated. The provided ablation studies on noise levels and time distortion are helpful, but a deeper analysis is needed to isolate which specific components of the GraphBSI model are most critical to its success.

- The theoretical framework is solid but I would appreciate if the authors can provide some easy-to-follow explanations alongside. Some of the results are slightly against intuition (e.g. Theorem 2 where the lower bound is a squared error for categorical variables) and can be difficult to understand at the first glimpse. Also, I would appreciate if the authors can compare their methods with a few existing continuous state discrete diffusion/flow models, both theoretical and empirical. Such as [1, 2, 3]. 

[1] H. Stark. et al. "Dirichlet Flow Matching with Applications to DNA Sequence Design". ICML 2024

[2] O. Davis. et al. "Fisher flow matching for generative modeling over discrete data". NeurIPS 2024

[3] H. Zheng. et al. "Continuously augmented discrete diffusion model for categorical generative modeling". Arxiv.


Decision: Accept (Poster)