SNACK: A Sequential Notation Framework for Probabilistic Graph Generation

Hohyun Kim; Hyesung Kim; Min-hwan Oh; Seunggeun Lee

stat.MLOct 14, 2026

SNACK: A Sequential Notation Framework for Probabilistic Graph Generation

Authors: Hohyun Kim, Hyesung Kim, Min-hwan Oh, Seunggeun Lee

Organizations: Seoul National University

Abstract

We introduce SNACK, a string representation for probabilistic graph generation that enables language models to generate graphs with discrete node and edge features. SNACK linearizes graphs by encoding the nonzero entries of the lower-triangular adjacency matrix, establishing a bijective correspondence between valid sequences and ordered adjacency matrices. This design enables invalid logit masking to enforce structural constraints, such as chemical valence and ordering rules, thereby guaranteeing 100% valid generated sequences while sticking to standard language modeling for effective training. SNACK also enables principled string-based GFlowNet training by explicitly accounting for node-ordering symmetries. Across standard graph-generation tasks and molecular distribution-learning benchmarks, SNACK achieves competitive sample quality, while substantially improving the throughput of GFlowNet training relative to graph-based generation. Probing analyses further show that models trained on SNACK encode meaningful local and global graph structure despite receiving only sequential supervision. These results position SNACK as a practical framework for probabilistic graph generation with deep sequence models.

Figures & tables

Figure 1: Overview of the encoding process. The molecule in the figure is represented as [C]1=[C]2-[C]2-[N]2=1-[C]1-[O] . By reordering the node indices, the same graph can also be represented as [O][C][N]3-2=1-[C]3-[C]3-1=[C] , resulting in a larger bandwidth.

	Planar			Enzymes			SBM			Grid
Method	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.
Training	0.001	0.004	0.000	0.010	0.019	0.009	0.015	0.001	0.037	0.000	0.000	0.000
GraphRNN	0.005	0.278	1.254	0.017	0.062	0.046	0.006	0.058	0.079	0.011	0.000	0.021
GDSS	0.250	0.393	0.587	0.026	0.061	0.009	0.496	0.456	0.717	0.111	0.005	0.070
DiGress	0.000	0.002	0.008	0.011	0.039	0.010	0.006	0.051	0.058	0.016	0.000	0.004
GEEL	0.001	0.010	0.001	0.005	0.018	0.006	0.025	0.003	0.026	0.000	0.000	0.000

Table 1: MMD scores for degree (Deg.), clustering (Clus.), and orbit (Orb.) statistics on selected datasets. Results within one standard deviation of the training graphs are highlighted in bold. The baseline results are obtained from Jang et al. [6] .

	QM9					MOSES
Method	Valid $\uparrow$	FCD $\downarrow$	SNN $\uparrow$	Frag $\uparrow$	Scaf $\uparrow$	Valid $\uparrow$	FCD $\downarrow$	SNN $\uparrow$	Frag $\uparrow$	Scaf $\uparrow$
SMILES	0.995	0.053	0.630	0.995	0.976	0.993	0.100	0.528	1.000	0.898
SELFIES	1.000	0.037	0.625	0.995	0.975	1.000	0.119	0.514	1.000	0.896
SAFE	0.969	0.113	0.611	0.992	0.956	0.989	0.258	0.496	0.999	0.877
STGG	1.000	0.121	0.602	0.994	0.962	1.000	0.114	0.528	1.000	0.891
GEEL	0.995	0.058	0.618	0.993	0.974	0.997	0.104	0.531	1.000	0.894

Table 2: Performance on molecular distribution learning. Results within one standard deviation of the best score are highlighted in bold.

Method	Success
SMILES	0.152
SELFIES	0.181
SAFE	0.057
STGG	0.003
GEEL	0.000
G2PT	0.000

Table 3: Success Rate in conditioned generation.

Reward	Method	Avg. Reward	Diversity	Top 100 reward	Top 100 div.	Div. Top 100	Uniq. Frac.
Gap	Graph	$0.984_{\pm 0.010}$	$0.958_{\pm 0.003}$	$\textbf{1.118}_{\pm 0.006}$	$\textbf{0.948}_{\pm 0.006}$	$\textbf{1.118}_{\pm 0.006}$	$0.982_{\pm 0.016}$
	SNACK (V)	$0.988_{\pm 0.001}$	$0.957_{\pm 0.001}$	$\textbf{1.117}_{\pm 0.005}$	$0.940_{\pm 0.006}$	$\textbf{1.117}_{\pm 0.005}$	$\textbf{1.000}_{\pm 0.000}$
	SNACK (V+B)	$\textbf{0.997}_{\pm 0.001}$	$\textbf{0.959}_{\pm 0.000}$	$\textbf{1.118}_{\pm 0.002}$	$\textbf{0.947}_{\pm 0.002}$	$\textbf{1.118}_{\pm 0.002}$	$\textbf{1.000}_{\pm 0.000}$
Ari	Graph	$0.159_{\pm 0.002}$	$\textbf{0.956}_{\pm 0.002}$	$0.204_{\pm 0.006}$	$\textbf{0.960}_{\pm 0.000}$	$0.204_{\pm 0.006}$	$0.997_{\pm 0.002}$
	SNACK (V)	$0.187_{\pm 0.000}$	$0.942_{\pm 0.000}$	$0.259_{\pm 0.003}$	$0.939_{\pm 0.001}$	$0.259_{\pm 0.003}$	$\textbf{1.000}_{\pm 0.000}$
	SNACK (V+B)	$\textbf{0.292}_{\pm 0.022}$	$0.945_{\pm 0.002}$	$\textbf{0.469}_{\pm 0.009}$	$0.916_{\pm 0.001}$	$\textbf{0.469}_{\pm 0.009}$	$\textbf{1.000}_{\pm 0.000}$

Table 4: Results for HOMO–LUMO gap (Gap), Aripiprazole similarity (Ari), and Albuterol similarity (Alb) optimization tasks. Bold indicates results within one standard deviation of the best.

Method	Improvement	Similarity	Success
JT-VAE	$1.91_{\pm 2.0}$	$0.28_{\pm.1}$	97.5%
GCPN	$4.20_{\pm 1.3}$	$0.32_{\pm.1}$	100%
GraphDF	$5.93_{\pm 0.8}$	$0.30_{\pm.1}$	100%
SNACK	$\mathbf{6.45}_{\pm 1.6}$	$\mathbf{0.46}_{\pm.15}$	100%

Table 5: Conditioned optimization

Figure 2: GFlowNet training time comparison. The ‘×’ indicates the maximum scale within GPU memory constraints.

	QM9	MOSES
Unif.	$0.203_{\pm 0.013}$	$6.513_{\pm 0.710}$
CM	$0.044_{\pm 0.004}$	$0.113_{\pm 0.010}$
BFS	$\mathbf{0.037}_{\pm 0.003}$	$\mathbf{0.103}_{\pm 0.002}$

Table 6: Comparison of FCD scores across different node ordering strategies.

Figure 3: Validation loss of SNACK (None) on QM9 dataset for each block design.

Figure 4: Adjacency and SPD matrices recovered from the model’s hidden representations.

	Adjacency		SPD
Model	Accuracy $\uparrow$	AUROC $\uparrow$	MSE $\downarrow$	MAE $\downarrow$
Random	0.9191	0.9362	3.0564	1.2897
SMILES	0.9894	0.9970	1.2722	0.8148
SNACK	0.9976	0.9998	1.6659	0.9250

Table 7: Model comparison on probing. “Random” denotes a randomly initialized SNACK model.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

	Ego-small			Community-small			Planar			Lobster
	$4\leq\|V\|\leq 18$			$12\leq\|V\|\leq 20$			$\|V\|=64$			$10\leq\|V\|\leq 100$
Method	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.
Training	0.021	0.031	0.012	0.016	0.032	0.003	0.001	0.004	0.000	0.007	0.000	0.005
GraphVAE	0.130	0.170	0.050	0.350	0.980	0.540	–	–	–	–	–	–
GraphRNN	0.090	0.220	0.003	0.080	0.120	0.040	0.005	0.278	1.254	0.000	0.000	0.000
GRAN	0.009	0.038	0.009	0.005	0.142	0.090	0.001	0.043	0.001	0.038	0.000	0.001

Appendix

Table 8: Results for Ego-small, Community-small, Planar, and Lobster datasets.

	Enzymes			SBM			Ego			Grid
	$10\leq\|V\|\leq 125$			$31\leq\|V\|\leq 187$			$50\leq\|V\|\leq 399$			$100\leq\|V\|\leq 400$
Method	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.	Deg.	Clus.	Orb.
Training	0.010	0.019	0.009	0.015	0.001	0.037	0.010	0.003	0.017	0.000	0.000	0.000
GraphVAE	1.369	0.629	0.191	–	–	–	–	–	–	1.619	0.000	0.919
GraphRNN	0.017	0.062	0.046	0.006	0.058	0.079	0.117	0.615	0.043	0.011	0.000	0.021
GRAN	0.023	0.031	0.169	0.011	0.055	0.054	0.026	0.342	0.254	0.001	0.004	0.002

Appendix

Table 9: Results for Enzymes, SBM, Ego, and Grid datasets.

Method	Valid $\uparrow$	FCD $\downarrow$	SNN $\uparrow$	Frag $\uparrow$	Scaf $\uparrow$
SMILES	$0.820{\scriptstyle\,\pm\,0.027}$	$0.755{\scriptstyle\,\pm\,0.071}$	$\mathbf{0.762{\scriptstyle\,\pm\,0.003}}$	$0.999{\scriptstyle\,\pm\,0.000}$	$0.887{\scriptstyle\,\pm\,0.006}$
SELFIES	$\mathbf{1.000{\scriptstyle\,\pm\,0.000}}$	$0.444{\scriptstyle\,\pm\,0.042}$	$0.715{\scriptstyle\,\pm\,0.002}$	$\mathbf{1.000{\scriptstyle\,\pm\,0.000}}$	$0.887{\scriptstyle\,\pm\,0.003}$
GEEL	$0.781{\scriptstyle\,\pm\,0.028}$	$1.701{\scriptstyle\,\pm\,0.331}$	$0.689{\scriptstyle\,\pm\,0.010}$	$0.998{\scriptstyle\,\pm\,0.000}$	$\mathbf{0.896{\scriptstyle\,\pm\,0.004}}$
SNACK (None)	$0.938{\scriptstyle\,\pm\,0.013}$	$\mathbf{0.422{\scriptstyle\,\pm\,0.064}}$	$0.755{\scriptstyle\,\pm\,0.002}$	$0.999{\scriptstyle\,\pm\,0.000}$	$0.889{\scriptstyle\,\pm\,0.001}$
SNACK (V+B)	$\mathbf{1.000{\scriptstyle\,\pm\,0.000}}$	$\mathbf{0.376{\scriptstyle\,\pm\,0.070}}$	$0.755{\scriptstyle\,\pm\,0.005}$	$\mathbf{1.000{\scriptstyle\,\pm\,0.000}}$	$0.891{\scriptstyle\,\pm\,0.003}$

Appendix

Table 10: Performance on Peptides-func dataset.

Method	Valid	Unique1	Unique2	IntDiv	IntDiv2	Filters	Novel
Training Dataset	1.0000	1.0000	1.0000	0.8567	0.8508	1.0000	0.0000
HMM [ 37 ]	0.0760	0.6230	0.5671	0.8466	0.8104	0.9024	0.9994
NGRAM [ 37 ]	0.2376	0.9740	0.9217	0.8738	0.8644	0.9582	0.9694
Combinatorial [ 67 ]	1.0000	0.9983	0.9909	0.8732	0.8666	0.9557	0.9878
CharRNN [ 68 ]	0.9748	1.0000	0.9994	0.8562	0.8503	0.9943	0.8419
AAE [ 37 ]	0.9368	1.0000	0.9994	0.8557	0.8499	0.9960	0.7931

Appendix

Table 11: First set of experimental results for the MOSES benchmark.

	FCD ( $\downarrow$ )		SNN ( $\uparrow$ )		Frag ( $\uparrow$ )		Scaf ( $\uparrow$ )
Method	Test	TestSF	Test	TestSF	Test	TestSF	Test	TestSF
Training Dataset	0.0080	0.4755	0.6419	0.5859	1.0000	0.9986	0.9907	0.0000
HMM [ 37 ]	24.466	25.431	0.3876	0.3795	0.5754	0.5681	0.2065	0.0490
NGRAM [ 37 ]	5.5069	6.2306	0.5209	0.4997	0.9846	0.9815	0.5302	0.0977
Combinatorial [ 67 ]	4.2375	4.5113	0.4514	0.4388	0.9912	0.9904	0.4445	0.0865
CharRNN [ 68 ]	0.0732	0.5204	0.6015	0.5649	0.9998	0.9983	0.9242	0.1101

Appendix

Table 12: Second set of experimental results for the MOSES benchmark.

Panel of Figure 5 — Figure 5: Scalability of SNACK and the graph GFlowNet versus the number of atoms $N$ .

Figure 6: Generated samples conditioned on Maribavir core.

Target	Metric	SNACK	SMILES	Random
Adjacency	Accuracy $\uparrow$	0.9976	0.9894	0.9191
Adjacency	AUROC $\uparrow$	0.9998	0.9970	0.9362
SPD	MSE $\downarrow$	1.6659	1.2722	3.0564
SPD	MAE $\downarrow$	0.9250	0.8148	1.2897

Appendix

Table 13: Reconstruction performance of the bilinear probe.

Figure 7: Layer-wise adjacency matrices reconstructed from the hidden representations of the SNACK-Transformer.

Figure 8: Sample graphs of generic datasets.

Graph Generation

Graph generation builds models and algorithms that create graphs with desired structures, properties, or distributions.

See all 67 papers

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models
Jun 2, 2026Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha +1Graph Generation Generative Modeling
Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA
Latent Flow Matching for Molecular Graph Generation
Oct 5, 2026Mathis Goupillon, Roman Bresson, Konstantinos Divriotis +1Flow Matching Molecular Graph Generation
Mohamed bin Zayed University of Artificial Intelligence
FLAGG: Flexible Autoregressive Graph Generation
Jun 3, 2026Samuel Cognolato, Alessandro Sperduti, Luciano SerafiniGraph Generation Autoregressive Generation
Department of Mathematics, University of Padova, Padova, VE, 35121 Italy · Fondazione Bruno Kessler (FBK), Trento, TN, 38123 Italy · Department of Information Engineering and Computer Science, University of Trento, Trento, TN, 38123 Italy

Jun 2, 2026J/K move · Enter open · S save

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha, Edoardo Serra

Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA

Graph Generation Generative Modeling Autoregressive Generation

Open paper AskPDF arXiv

Generating realistic and diverse graphs is a key problem in machine learning, with applications in molecular discovery, circuit design, cybersecurity, and beyond. However, current graph generative models remain limited by scalability and novelty. Diffusion-based methods often require costly full-adjacency operations and long denoising chains, while many autoregressive and hybrid models have at least quadratic complexity. In addition, these models often imitate training graphs rather than generalize beyond them. We propose a lightweight autoregressive framework to address these issues. It uses a structure-guided topological ordering to serialize graphs into regular edge sequences, enabling near log-linear generation, and a two-phase training strategy that combines exploration-oriented augmentation with iterative refinement to reduce overfitting and promote controlled novelty. Experiments on molecular and non-molecular benchmarks show that our approach improves novelty while preserving high validity and uniqueness. The framework also supports both LSTM and Mamba-style causal sequence backbones, with large-memory accelerators enabling longer graph-sequence experiments beyond typical GPU limits.

Abstract

Graph Generation

Explore similar work

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

Latent Flow Matching for Molecular Graph Generation

FLAGG: Flexible Autoregressive Graph Generation