Unrestrained Simplex Denoising for Discrete Data. A Non-Markovian Approach Applied to Graph Generation

Yoann Boget; Alexandros Kalousis

cs.LGMar 30, 2026

Unrestrained Simplex Denoising for Discrete Data. A Non-Markovian Approach Applied to Graph Generation

Authors: Yoann Boget, Alexandros Kalousis

Organizations: Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland

Abstract

Denoising models such as Diffusion or Flow Matching have recently advanced generative modeling for discrete structures, yet most approaches operate directly in the discrete state space, leading to abrupt state changes. We introduce simplex denoising, a simple yet effective generative framework that operates on the probability simplex. The key idea is a non-Markovian noising scheme in which, for a given clean data point, noisy representations at different times are conditionally independent. While preserving the theoretical guarantees of denoising-based generative models, our method removes unnecessary constraints, thereby improving performance and simplifying the formulation. Empirically, unrestrained simplex denoising surpasses strong discrete diffusion and flow-matching baselines across synthetic and real-world graph benchmarks. These results highlight the probability simplex as an effective framework for discrete generative modeling.

Figures & tables

Panel of Figure 1 — Figure 1: Upper row: Noising with a linear interpolant creates discontinuities and, for $t>0.5$ , all points remain in the Voronoi region of their original vertex. Lower row: Noising with an explicit parametric probability path avoids discontinuities.

	Planar					SBM
	Valid $\uparrow$	Deg. $\downarrow$	Clust. $\downarrow$	Orbit $\downarrow$	Spect. $\downarrow$	Valid $\uparrow$	Deg. $\downarrow$	Clust. $\downarrow$	Orbit $\downarrow$	Spect. $\downarrow$	Novel $\uparrow$
Train.	$100.0\phantom{0}$	$\phantom{0}0.25$	$36.6$	$0.8$	$6.6$	$93.5$	$\phantom{0}1.57$	$50.1$	$37.0$	$4.6$	100
DiGress	$45.5$	$\phantom{0}0.71$	$45.4$	$\phantom{0}1.31$	$8.4$	$51.0$	$\phantom{0}\bm{1.28}$	$51.5$	$\bm{39.6}$	$\bm{5.0}$	100
GruM	$91.0$	$\phantom{0}\bm{0.38}$	$40.7$	$\phantom{0}6.42$	$\bm{7.9}$	$67.5$	$\phantom{0}2.20$	$\bm{49.9}$	$\bm{40.4}$	$\bm{5.1}$	100
SID	$91.3$	$5.9$	$163.4\phantom{0}$	$19.1\phantom{0}$	$\bm{7.6}$	$63.5$	$11.5\phantom{0}$	$\bm{51.4}$	$123.1\phantom{0}$	$5.9$	100
DeFoG	$99.5$	$0.5$	$50.1$	$0.6$	$\bm{7.2}$	$\bm{90.0}$	* $0.6$ *	$51.7$	$\phantom{0}55.6$	$\bm{5.4}$	0 $90$

Table 2: Results on Planar and SBM .

	Deg. $\downarrow$	Clust. $\downarrow$	Orbit $\downarrow$	Spect. $\downarrow$	Ratio $\downarrow$
Train.	$0.003$	$0.019$	$0.001$	$0.0189$	$1$
GraphVAE	$1.369$	$0.629$	$0.191$	-	-
GraphRNN	$0.017$	$0.062$	$0.046$	-	-
GDSS	$0.026$	$0.061$	$0.009$	-	-
DiscDiff	$0.212$	$0.631$	$0.515$	$0.0196$	$155.0$
NM-CD	$0.084$	$0.308$	$0.125$	$0.0202$	$42.6$

Table 3: Results on Enzymes .

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Voronoi probabilities over time for ${\mathbf{x}}_{t}\sim\mathrm{Dir}({\bm{1}}+\alpha_{t}{\mathbf{x}}_{1})$ on ${\mathbb{S}}_{3}$ , with $\alpha_{t}=-a\log(1-t)$ , for various values of $a$ . For $a=1$ , $P_{v_{k}}$ remains low for most of the trajectory and only increases sharply as $t\to 1$ ; for $a=10$ , $P_{v_{k}}$ is already close to $1$ by $t=0.6$ . Suitable choices of $a$ therefore likely lie between $1$ and $10$ .

	Planar	SBM	QM9H	ZINC250K
GNN layers	8	8	8	8
Hidden layers in MLPs	2	2	2	2
Node representation size	256	256	256	256
Edge representation size	64	128	128	128
Denoising steps	128	512	1024	1024
Learning rate	0.0002	0.0005	0.0005	0.0005

Appendix

Table 4: Hyperparameters.

	Planar		SBM		QM9H	ZINC250K
	Time $\downarrow$	Params	Time $\downarrow$	Params	Params	Params
DiGress	$16.9\pm 0.0$	$8.9$ M	$96.9\pm 0.1$	$7.1$ M	$3.6$ M	$8.2$ M
GruM	$29.3\pm 0.0$	$7.1$ M	$84.2\pm 0.0$	$7.1$ M	-	$8.2$ M
NM-DD	$\phantom{0}9.9\pm 0.4$	$5.4$ M	$84.1\pm 0.3$	$6.2$ M	$6.2$ M	$6.2$ M
DiriFM	$\phantom{0}9.4\pm 0.1$	$5.4$ M	$89.0\pm 0.3$	$6.2$ M	$6.2$ M	$6.2$ M
UNSID	$\phantom{0}6.3\pm 0.0$	$5.4$ M	$72.6\pm 0.5$	$6.2$ M	$6.2$ M	$6.2$ M

Appendix

Table 5: Model sizes and sampling times (in seconds).

	Valid (%) $\uparrow$	FCD $\downarrow$	NSPDK $\downarrow$	Unique (%) $\uparrow$
Train.	$98.90\pm 0.05$	$0.062\pm 0.002$	$0.121\pm 0.016$	$99.81\pm 0.04$
DiGress	$95.4\phantom{0}\pm 1.1\phantom{0}$	-	-	$97.6\phantom{0}\pm 0.4\phantom{0}$
DiscDiff	$22.29\pm 0.62$	$4.246\pm 0.454$	$41.932\pm 0.741\phantom{0}$	$73.72\pm 0.56$
NM-DD	$97.97\pm 0.07$	$0.366\pm 0.021$	$1.149\pm 0.047$	$95.23\pm 0.17$
NM-CD	$31.29\pm 0.15$	$1.688\pm 0.031$	$22.675\pm 0.099\phantom{0}$	$91.45\pm 0.27$
DiriFM	$92.20\pm 0.19$	$0.356\pm 0.029$	$0.495\pm 0.010$	$97.53\pm 0.13$

Appendix

Table 6: Results on QM9H . NSPDK is reported

\times 10^{3}

NFE	Invalid (%) $\downarrow$	FCD $\downarrow$	NSPDK $\downarrow$
$16$	$5.71$	$6.54$	$7.97$
$32$	$1.05$	$4.32$	$4.00$
$64$	$0.36$	$3.26$	$2.79$
$128$	$0.08$	$2.63$	$2.08$
$256$	$0.09$	$2.17$	$1.59$
$512$	$0.01$	$1.92$	$1.34$

Appendix

Table 7: Effect of the NFE on ZINC250K . NSPDK is reported

\times 10^{3}

Panel of Figure 4 — Figure 4: Voronoi probabilities for various values of $a$ in the schedule $\alpha_{t}=-a\log(1-t)$ , for $K=9$ (left) and $K=2$ (right).

$a$	Valid (%) $\uparrow$	FCD $\downarrow$	NSPDK $\downarrow$	Unique (%) $\uparrow$	Novel (%) $\uparrow$
$1$	$98.87\pm 0.16$	$4.13\pm 0.08$	$2.61\pm 0.11$	$99.86\pm 0.01$	$99.99\pm 0.01$
$2$	$99.89\pm 0.03$	$1.89\pm 0.01$	$0.98\pm 0.06$	$99.98\pm 0.00$	$99.96\pm 0.01$
$3$	$99.98\pm 0.01$	$1.79\pm 0.03$	$1.00\pm 0.06$	$100.00\pm 0.00\phantom{0}$	$99.97\pm 0.01$
$4$	$99.94\pm 0.02$	$1.82\pm 0.05$	$1.05\pm 0.04$	$99.99\pm 0.00$	$99.98\pm 0.01$
$6$	$99.92\pm 0.02$	$1.66\pm 0.03$	$0.82\pm 0.03$	$99.99\pm 0.01$	$99.97\pm 0.02$
$10$	$99.91\pm 0.00$	$1.95\pm 0.03$	$1.25\pm 0.07$	$99.99\pm 0.01$	$99.99\pm 0.00$

Appendix

Table 8: Results on ZINC250K for various values of the schedule hyperparameter

a

. NSPDK is reported

\times 10^{3}

Figure 5: Comparison between the uniform prior $\mathrm{Dir}({\bm{1}})$ and the marginal-weighted mixture of Dirichlet distributions $q_{0}^{\mathrm{marg}}$ ( $\kappa=2$ ) on ZINC250K .

	Valid (%) $\uparrow$	MAE $\downarrow$
Unconditional	$99.6$	$1.06$
Classifier guidance	$99.5$	$0.42$

Appendix

Table 9: Effect of classifier guidance on QM9H . The MAE between target and generated QED values is computed in standardized units.

	Valid (%) $\uparrow$	Deg. $\downarrow$	Clust. $\downarrow$	Orbit $\downarrow$	Spect. $\downarrow$
Train.	$100.0\pm 0.0$	$0.25\pm 0.18$	$36.6\pm 3.5$	$0.78\pm 0.37$	$6.62\pm 1.34$
DiGress	$45.5\pm 7.0$	$0.71\pm 0.40$	$\phantom{0}45.4\pm 13.6$	$1.31\pm 0.78$	$8.40\pm 1.16$
GruM	$91.0\pm 2.6$	$0.38\pm 0.15$	$40.7\pm 4.8$	$6.42\pm 1.96$	$7.87\pm 1.17$
SID	$91.3\pm 4.1$	$5.93\pm 1.26$	$163.4\pm 31.9$	$19.1\phantom{0}\pm 4.14\phantom{0}$	$7.62\pm 1.34$
DeFoG	$99.5\pm 1.0$	$0.5\phantom{0}\pm 0.2\phantom{0}$	$\phantom{0}50.1\pm 14.9$	$0.6\phantom{0}\pm 0.4\phantom{0}$	$7.2\phantom{0}\pm 1.1\phantom{0}$
DiscDiff	$\phantom{0}0.0\pm 0.0$	$56.1\phantom{0}\pm 3.70\phantom{0}$	$294.0\pm 3.4\phantom{0}$	$1410.0\phantom{0}\pm 44.5\phantom{000}$	$85.1\phantom{0}\pm 1.6\phantom{00}$

Appendix

Table 10: Results on Planar . MMDs are reported

\times 10^{3}

	Valid (%) $\uparrow$	Deg. $\downarrow$	Clust. $\downarrow$	Orbit $\downarrow$	Spect. $\downarrow$	Novel (%) $\uparrow$
Train.	$93.50\pm 2.00$	$1.57\pm 0.55$	$50.11\pm 0.51$	$37.0\pm 10.7$	$4.58\pm 0.49$	$100$
DiGress	$51.00\pm 9.62$	$1.28\pm 0.48$	$51.49\pm 1.31$	$39.6\pm 7.7$	$5.04\pm 0.63$	$100.0\pm 0.0$
GruM	$67.54\pm 2.98$	$2.20\pm 0.76$	$49.88\pm 0.62$	$40.4\pm 5.6$	$5.06\pm 0.72$	$100.0\pm 0.0$
SID	$63.5\phantom{0}\pm 3.7\phantom{0}$	$11.5\phantom{0}\pm 2.7\phantom{0}$	$51.4\pm 1.5$	$123.1\pm 5.4\phantom{0}$	$5.93\pm 1.18$	$100.0\pm 0.0$
DeFoG	$90.0\phantom{0}\pm 5.2\phantom{0}$	$0.6\phantom{0}\pm 2.3\phantom{0}$	$51.7\pm 1.2$	$\phantom{0}55.6\pm 73.9$	$5.40\pm 1.20$	$90.0\pm 5.1$
DiscDiff	$\phantom{0}0.00\pm 0.00$	$1.82\pm 0.88$	$86.38\pm 6.37$	$125.7\pm 3.3\phantom{0}$	$11.28\pm 1.06\phantom{0}$	$100.0\pm 0.0$

Appendix

Table 11: Results on SBM . MMDs are reported

\times 10^{3}

	Valid (%) $\uparrow$	FCD $\downarrow$	NSPDK $\downarrow$	Unique (%) $\uparrow$	Novel (%) $\uparrow$
Train.	$100.00\pm 0.00$	$1.13\pm 0.01$	$0.10\pm 0.00$	$99.97\pm 0.02$	-
DiGress	$94.99$	$3.48$	$2.1$	-	-
GruM	$98.65$	$2.26$	$1.5$	-	-
GraBFN	$99.22$	$2.12$	$1.3$	-	-
SID	$99.50\pm 0.06$	$2.06\pm 0.05$	$2.01\pm 0.01$	$99.84\pm 0.02$	$99.97\pm 0.00$
DiscDiff	$74.17\pm 0.65$	$4.78\pm 0.14$	$4.08\pm 0.13$	$100.00\pm 0.00\phantom{0}$	$100.00\pm 0.00\phantom{0}$

Appendix

Table 12: Results on ZINC250K . NSPDK is reported

\times 10^{3}

	Deg. $\downarrow$	Clust. $\downarrow$	Orbit $\downarrow$	Spect. $\downarrow$
Train.	$3.3\pm 0.3$	$19.2\pm 4.2$	$0.9\pm 0.3$	$18.9\pm 0.1$
GraphVAE	$1369\pm 20$	$629\pm 5$	$191\pm 20$	-
GraphRNN	$17\pm 7$	$62\pm 20$	$46\pm 31$	-
GDSS	$26\pm 8$	$61\pm 10$	$9\pm 5$	-
DiscDiff	$212.7\pm 11.8$	$631.1\pm 45.7$	$515.5\pm 54.1$	$19.6\pm 0.2$
NM-DD	$13.6\pm 4.1$	$39.9\pm 5.2$	$10.4\pm 0.9$	$17.4\pm 0.0$

Appendix

Table 13: Results on Enzymes . MMDs are reported

\times 10^{3}

Panel of Figure 9 — Figure 9: Stochstic Block Model

Generative Modeling

Generative modeling learns data distributions to create new samples, from images and text to molecules, simulations, and structured records.

See all 493 papers

Sep 28, 2026

Simplex Diffusion Models

Diffusion models have revolutionized generative modeling for continuous data through the gradual refinement of a belief state. This iterative refinement has not yet carried over to discrete diffusion models, which discard uncertainty at intermediate steps through categorical sampling (information collapse). We propose Simplex Diffusion Models (SDMs), a framework that lifts the diffusion process to the probability simplex to represent beliefs over categories. SDMs admit probability paths with closed-form reverse transitions and can be trained with a simple cross-entropy loss. Contrary to earlier proposals such as Dirichlet Flow Matching which requires integrating an ordinary differential equation, we introduce a DDIM-like sampler with a tunable level of stochasticity. Because SDMs operate on samples on the simplex, they can carry uncertainty across denoising steps, which mitigates information collapse. On OpenWebText, SDMs are competitive with strong Discrete Diffusion baselines, achieving

17.0

GenPPL at

5.46

unigram entropy in 64 sampling steps, close to real validation data. Even without Self-Conditioning (SC), SDMs outperform masked and uniform diffusion (with SC or predictor-corrector sampling) on code generation (TinyGSM,

T=0.1

;

49.0\%

vs.

45.8\%

). Distilled down to 8 steps, SDMs solve

32.1\%

of GSM8K problems, more than distilled Discrete Diffusion models with 128 steps (

21.4\%

Justin Deschenaux, Alexandre Galashov, Andrew Campbell +4

Google DeepMind · EPFL · UCL Gatsby

Diffusion Sampling Diffusion Language Models Diffusion Models

Ask PDF

Mar 31, 2026

Hierarchical Discrete Flow Matching for Graph Generation

Denoising-based models, including diffusion and flow matching, have led to substantial advances in graph generation. Despite this progress, such models remain constrained by two fundamental limitations: a computational cost that scales quadratically with the number of nodes and a large number of function evaluations required during generation. In this work, we introduce a novel hierarchical generative framework that reduces the number of node pairs that must be evaluated and adopts discrete flow matching to significantly decrease the number of denoising iterations. We empirically demonstrate that our approach more effectively captures graph distributions while substantially reducing generation time.

Yoann Boget, Pablo Strasser, Alexandros Kalousis

Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland

Graph Generation Flow-Based Generative Modeling Discrete Flow Matching

Ask PDF

Mar 22, 2026

Generalized Discrete Diffusion from Snapshots

We introduce Generalized Discrete Diffusion from Snapshots (GDDS), a unified framework for discrete diffusion modeling that supports arbitrary noising processes over large discrete state spaces. Our formulation encompasses all existing discrete diffusion approaches, while allowing significantly greater flexibility in the choice of corruption dynamics. The forward noising process relies on uniformization and enables fast arbitrary corruption. For the reverse process, we derive a simple evidence lower bound (ELBO) based on snapshot latents, instead of the entire noising path, that allows efficient training of standard generative modeling architectures with clear probabilistic interpretation. Our experiments on large-vocabulary discrete generation tasks suggest that the proposed framework outperforms existing discrete diffusion methods in terms of training efficiency and generation quality, and beats autoregressive models for the first time at this scale. We provide the code along with a blog post on the project page : https://oussamazekri.fr/gdds.

Oussama Zekri, Théo Uscidda, Nicolas Boullé +1

CREST, ENSAE, Institut Polytechnique de Paris, Paris, France · Department of Mathematics, Imperial College London, London, SW7 2AZ, UK

Diffusion Models Diffusion Language Models

Ask PDF

Abstract

Generative Modeling

Explore similar work

Simplex Diffusion Models

Hierarchical Discrete Flow Matching for Graph Generation

Generalized Discrete Diffusion from Snapshots