SNACK Framework: A Unified New Paradigm for Generating Graph Structures with Sequence Models

Graph generation has always been a hard problem in deep learning — graph data has no natural sequential order, and the discrete features of nodes and edges make it difficult to directly apply traditional sequence models. The recently proposed SNACK (Sequential Notation for Adjacency and Connectivity Knowledge) framework uses a clever string representation method to transform the graph generation problem into a sequence modeling problem, while simultaneously addressing the two major pain points of validity and efficiency.

Core Idea: "Flattening" the Adjacency Matrix into a String

SNACK's basic operation is intuitive: it encodes only the non-zero elements in the lower triangular adjacency matrix, linearizing them into a sequence. This design establishes a bijection — legal SNACK sequences correspond one-to-one with ordered adjacency matrices.

What does this mean? Any sequence that conforms to the grammar necessarily corresponds to a legal graph, and vice versa. This bidirectional mapping is the cornerstone of the entire framework, allowing sequence models (such as Transformers and RNNs) to seamlessly transfer to graph generation tasks. Compared to previous methods that required complex graph neural network encoders, SNACK can directly process graph-structured data using language model architectures.

Lower triangular adjacency matrix refers to keeping only the triangular region of the adjacency matrix at and below the diagonal (excluding the diagonal itself). For an undirected graph with n nodes, its adjacency matrix is symmetric, and the upper triangular and lower triangular information is completely redundant. Therefore, retaining only the non-zero elements of the lower triangle can losslessly reconstruct the entire graph structure. At the same time, the natural row-major traversal order of elements in the lower triangle implicitly assigns a certain permutation to the nodes, thereby converting the unordered graph structure into a deterministic sequence. This choice avoids the duplicate encoding problem caused by graph symmetry, ensuring that the same graph corresponds to only one canonical lower triangular sequence, which is the key to SNACK's ability to establish a bijection.

Bijection refers to a one-to-one correspondence between two sets: each legal SNACK sequence uniquely determines an ordered adjacency matrix, and conversely, each ordered adjacency matrix uniquely determines a legal SNACK sequence. This property guarantees that the sequence space and the graph space are structurally equivalent, so when using sequence models to model graph generation problems, no loss of expressive power is introduced, nor is any representational ambiguity produced. Without a bijection, a sequence model might generate sequences that cannot be mapped back to graphs, or multiple different sequences might represent the same graph, leading to confused training objectives.

Invalid Logit Masking: Ensuring 100% Legal Output

A common problem with sequence generation models is that they may produce outputs that violate constraints. In molecular generation scenarios, this manifests as generating atomic connections that violate chemical valence rules; in general graph generation, it may produce adjacency structures that do not conform to ordering rules.

SNACK solves this problem through an invalid logit masking mechanism. At each decoding step, the model dynamically computes which tokens are structurally legal based on the partially generated sequence, setting the logits of illegal tokens to negative infinity. This constraint is exact — the paper claims it can guarantee that 100% of generated sequences are legal.

The practical value of this feature is significant. Traditional methods typically require post-processing steps to correct illegal outputs, or rely on penalty terms in reinforcement learning to indirectly guide the model, whereas SNACK encodes structural constraints directly into the generation process itself.

Logit refers to the unnormalized raw scores produced by a neural network at the output layer (especially in classification tasks), which are typically then converted to probabilities via the Softmax function. In sequence generation models, at each step, logits need to be computed for each of the vocabulary-sized tokens. If sampling is done directly based on probabilities, the model might select structurally illegal tokens, for example, allowing an atom to exceed its maximum valence in molecular generation.

Invalid Logit Masking is a technique that enforces constraints during the decoding phase: for all possible tokens at the current step, it determines based on the generated prefix whether each token would lead to an illegal structure, and sets the logit corresponding to illegal tokens to negative infinity (-∞). This way, after Softmax, the probabilities of these tokens become 0, and the model will never sample them. This method embeds the syntactic constraints of graph structure directly into the generation process, without the need for post-hoc checking or correction of outputs, which is why the paper can claim a 100% legality guarantee. Compared to penalty terms in reinforcement learning, masking is a hard constraint that does not depend on model learning, making it more reliable and interpretable.

GFlowNet Training: Explicitly Handling Node Ordering Symmetry

Another important contribution of SNACK is enabling GFlowNet to be trained directly in string space. GFlowNet is a class of generative models for learning probability distributions, with the goal of making generation probabilities proportional to target rewards.

Graph data has an inherent difficulty: the same graph can have multiple node orderings, but they are essentially equivalent. SNACK explicitly accounts for this node ordering symmetry, enabling GFlowNet's training objective to correctly handle this equivalence relationship. Experiments show that compared to methods that operate directly on graphs, SNACK achieves significant improvements in GFlowNet training throughput.

GFlowNet (Generative Flow Network) is a class of generative models based on flow matching, whose learning objective is to make the probability of generating a certain object x proportional to a given reward function R(x), i.e., P(x) ∝ R(x). During training, a forward policy (generating objects from an initial state) and a backward policy (tracing back from objects to the initial state) are typically constructed, and the two are made consistent under flow conservation constraints. In graph generation tasks, the reward can be defined as molecular properties, graph validity, etc.

Node ordering symmetry refers to the fact that the same graph exhibits different matrix forms under different node permutations of the adjacency matrix, but they are semantically the same graph. If a generative model does not account for this symmetry, it will treat different orderings of the same graph as different samples, leading to incorrect probability assignment. SNACK implicitly eliminates this symmetry by fixing the graph to the canonical ordering of the lower triangular adjacency matrix (e.g., in node index order). Therefore, when GFlowNet is trained in string space, no additional symmetry handling is needed, and each graph corresponds to only one sequence. This both simplifies the training objective and avoids learning redundant multiple representations, significantly improving training efficiency.

Experimental Performance: Both Quality and Efficiency

On standard graph generation tasks and molecular distribution learning benchmarks, SNACK achieves competitive sample quality. More critically, there is an efficiency improvement — since sequence generation can leverage mature sequence model infrastructure (such as KV caching, parallel decoding, etc.), its throughput far exceeds graph-based generation methods.

Probing analysis reveals an interesting phenomenon: models trained only under sequence supervision still encode meaningful local and global graph structure information in their internal representations. This indicates that serialization does not lose the structural information of graphs, and the model can "learn" the intrinsic patterns of graphs from string sequences.

Probing Analysis is a common technique for understanding the internal representations of neural networks: training simple classifiers (such as linear classifiers) on the hidden layer representations of a model to predict certain predefined structural properties (e.g., node degree, shortest path length, local subgraph types, etc.). If a simple classifier can predict these properties with high accuracy, it indicates that the model has spontaneously encoded this information internally. In SNACK experiments, probing analysis revealed that models trained purely with sequence supervision still contain meaningful local and global graph structure information in their internal representations, proving that serialization does not lose key structural features of graphs and that the model learns graph patterns from string sequences. This finding strengthens confidence in the ability of sequence models to handle graph data.

Why It's Worth Paying Attention To

The significance of SNACK lies in the fact that it provides a pragmatic technical route: rather than designing complex graph-specific architectures, it converts graphs into sequences and reuses the engineering optimizations and architectural innovations accumulated over years in the sequence model field.

Of course, SNACK also has its scope of applicability — it currently mainly targets graphs with discrete node and edge features. Whether it is applicable to scenarios such as continuous-feature graphs and dynamic graphs still requires further exploration. But as a general framework for probabilistic graph generation, SNACK builds a simple yet effective bridge between sequence models and graph structures.

One-line Summary

SNACK Framework structures graphs into string sequences, guaranteeing 100% legal generation through bijections and masking, and supporting efficient GFlowNet training.

Paragraph Summary

SNACK framework proposes a new method for converting graph generation into sequence modeling: encoding only the non-zero elements of the lower triangular adjacency matrix, linearizing them into a string sequence, establishing a bijection between legal sequences and ordered adjacency matrices, enabling sequence models to directly process graph data. Through an invalid logit masking mechanism, it ensures 100% legality during decoding, avoiding post-processing or reinforcement learning penalties. It also explicitly handles node ordering symmetry, allowing GFlowNet to be trained directly in string space, significantly improving throughput. On standard graph generation and molecular distribution learning tasks, SNACK is competitive in both sample quality and efficiency. Probing analysis shows that under pure sequence supervision, the model's internal representations still encode local and global structural information, providing a pragmatic technical path for graph generation.