SNACK: A Sequential Notation Framework for Probabilistic Graph Generation
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.
Related
- Variational Probabilistic Quantization for Secret Key Generation
- Schrödinger Bridges on Lie Group Manifolds for Probabilistic Intrinsic Generation
- Limitations on Autoregressive Token Generation via Sequential Sampling
- Nonparametric framework for the definition, adaptive detection and probabilistic interpretation of outliers
- ML-CLAPPS: A Probabilistic Framework for Imbalanced Multilabel Learning under Class Prioritization
BibTeX
@misc{kim2026snack,
title = {{SNACK: A Sequential Notation Framework for Probabilistic Graph Generation}},
author = {Hohyun Kim and Hyesung Kim and Min-hwan Oh and Seunggeun Lee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19781},
eprint = {2610.19781},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19781},
}
RIS
TY - UNPB
TI - SNACK: A Sequential Notation Framework for Probabilistic Graph Generation
AU - Hohyun Kim
AU - Hyesung Kim
AU - Min-hwan Oh
AU - Seunggeun Lee
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.19781
UR - https://arxiv.org/abs/2610.19781
AB - 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.
ER -