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

Simplex Diffusion Models
Sep 28, 2026Justin Deschenaux, Alexandre Galashov, Andrew Campbell +4Diffusion Sampling Diffusion Language Models
Google DeepMind · EPFL · UCL Gatsby
Hierarchical Discrete Flow Matching for Graph Generation
Mar 31, 2026Yoann Boget, Pablo Strasser, Alexandros KalousisGraph Generation Flow-Based Generative Modeling
Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland
Generalized Discrete Diffusion from Snapshots
Mar 22, 2026Oussama Zekri, Théo Uscidda, Nicolas Boullé +1Diffusion Models Diffusion Language Models
CREST, ENSAE, Institut Polytechnique de Paris, Paris, France · Department of Mathematics, Imperial College London, London, SW7 2AZ, UK

Sep 28, 2026J/K move · Enter open · S save

Simplex Diffusion Models

Justin Deschenaux, Alexandre Galashov, Andrew Campbell, Li Kevin Wenliang+3

Google DeepMind · EPFL · UCL Gatsby

Diffusion Sampling Diffusion Language Models Diffusion Models

Open paper AskPDF arXiv

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\%

Abstract

Generative Modeling

Explore similar work

Simplex Diffusion Models

Hierarchical Discrete Flow Matching for Graph Generation

Generalized Discrete Diffusion from Snapshots