SNACK: A Sequential Notation Framework for Probabilistic Graph Generation

We introduce SNACK, a string representation for probabilistic graph generation that enables sequence models to generate and model graph-structured data. 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 supports invalid logit masking for enforcing structural constraints, including chemical valence and ordering constraints, and 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 or state-of-the-art 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.