SNACK: A Sequential Notation Framework for Probabilistic Graph Generation

1 Introduction

• Existing string-based methods typically address only a subset of key capabilities, while multiple strings for one graph complicate probabilistic modeling.The listed capabilities include guaranteed validity, general graph applicability, flexible conditional generation, and goal-directed exploration.Source: §1 · p. 1
• SNACK provides a one-to-one correspondence with adjacency matrices and uses exactly N + 2M tokens for a graph with N nodes and M edges.Unique decoding supports string-based GFlowNet training through a node-ordering policy.Source: §1 · p. 2
• SNACK reliably generates high-quality samples with 100% validity across benchmarks and significantly enhances the scalability of graph GFlowNet training.It is evaluated across graph-related tasks, including distribution learning and property optimization.Source: §1 · p. 2
• SNACK supports string-based GFlowNet training in de novo and conditioned settings, improving scalability.The framework also enables conditioned optimization and direct logit masking by decoding any sequence prefix into a partial graph state.Source: §1 · p. 2
• Bilinear probing shows that SNACK-based models internalize graph structure from sequential data without explicit supervision.Source: §1 · p. 2

2.1 Overview

• SNACK encodes typed undirected graphs row by row, representing each nonzero lower-triangular edge with its node distance and edge type.Each row also records the node type on the diagonal; entries are ordered left to right to prioritize earlier neighbors and reduce decoding context.Source: §2.1 · p. 2

2.2 Bandwidth-restricted encoding

• BFS ordering controls vocabulary size by reducing adjacency-matrix bandwidth, and outperforms Cuthill–McKee in the reported molecular experiments.Bandwidth is the largest distance induced by an ordering; smaller distances reduce the number of distinct distance tokens needed.Source: §2.2 · p. 3

2.3 Invalid logit masking

• Prefix-decodability lets the model inspect a partial graph and mask invalid next tokens for grammar, molecular valence, and BFS-order constraints.BFS masking restricts predictions during generation; choosing BFS ordering for training alone does not guarantee that generations follow BFS.Source: §2.3 · p. 3

2.4 Sequence modeling objective

• The sequence negative log-likelihood conditions each next-token prediction on previous tokens and optimizes a variational lower bound on graph log-likelihood.The loss uses invalid-token masking, and the paper focuses on a fixed random BFS ordering policy.Source: §2.4 · p. 4

2.5 Computing the variational distribution

• SNACK is bijective with ordered adjacency matrices, enabling computation of the sequence distribution by accounting for node orderings that yield the same matrix.Unlike representations where multiple strings can encode the same adjacency matrix, SNACK's bijection supports evaluating q(x|G); the paper notes this enables GFlowNet training and other applications.Source: §2.5 · p. 4

2.6 Training GFlowNets with SNACK

• SNACK-based GFlowNets use token-generation trajectories with deterministic sequence-to-graph decoding and q(x|G) as the backward probability from graph to sequence.The Trajectory Balance objective matches forward and backward trajectory distributions; q(x|G) distributes graph reward across its SNACK representations, and the paper develops a conditioned version for predefined substructures.Source: §2.6 · pp. 4–5

2.7 Overall computation

• Dense-attention computation and memory complexity fall from cubic to quadratic in node count versus graph-based methods.SNACK computes trajectory-level log-probabilities in one full-sequence forward pass, while graph-based methods require N + M intermediate-state passes.Source: §2.7 · p. 5

Graph generative models

• Graph-based methods directly handle discrete structures but can require specialized architectures and incur high computational costs; string-based methods enable efficient standard sequence-model training.GraphRNN predicts every potential edge, whereas SNACK encodes only nonzero entries, improving efficiency for sparse graphs.Source: §3 · p. 5

String representations of graphs

• Unlike SMILES and other graph-string methods, SNACK explicitly formalizes bijectivity with adjacency matrices to support symmetry-aware goal-directed learning.The related-work discussion distinguishes SNACK's design from GEEL's edge-by-edge construction and bandwidth-dependent vocabulary, and from SMILES' syntactic validity issues.Source: §3 · p. 6

GFlowNets

• Prior molecular GFlowNets predominantly use graph representations, while SMILES-based GFlowNets can bias generation toward molecules with multiple valid SMILES strings.SNACK instead uses string representations and accounts for graph symmetries; its state-space DAG allows distinct strings to reach the same terminal graph.Source: §3 · p. 6

4.1 Generic graph generation

• SNACK generates graph samples whose statistics closely match training distributions across eight datasets, approaching the benchmark performance ceiling without dataset-specific tuning.The evaluation compares degree, clustering, and orbit MMD scores.Source: Table 1 · p. 6, §4.1 · p. 6

4.2 Molecular string generation

• SNACK achieves competitive molecular distribution-learning performance on QM9 and MOSES, and logit masking raises validity to 100%.SMILES, SELFIES, and GEEL remain within one standard deviation across several metrics.Source: Table 2 · p. 7, §4.2 · p. 7
• For substructure-conditioned generation, SNACK (None) succeeds by producing valid, connected molecules containing the target substructure and more heavy atoms.The comparison uses 129 smallest MOSES test molecules and requires an extension beyond the input substructure.Source: Table 3 · p. 7, §4.2 · p. 7

4.3 Goal-directed learning

• SNACK matches graph-based GFlowNet performance on HOMO–LUMO gap optimization and outperforms it on both similarity rewards, with unique fraction 1.0; BFS masking further improves results.On albuterol, the graph-based model's Top 100 reward is 0.171 versus 0.736 for SNACK.Source: Table 4 · p. 8, §4.3 · p. 8
• SNACK (V+B) optimizes target properties while strictly preserving the required fragment under conditioned Trajectory Balance training.The task starts from one of 800 low-penalized-logP molecules.Source: Table 5 · p. 8, §4.3 · p. 8
• SNACK-GFlowNet has higher training throughput than the graph-based baseline as molecular size increases.Figure 2 marks the maximum scale reached within GPU memory constraints.Source: Figure 2 · p. 8, §4.3 · p. 8

4.4 Ablation studies

• BFS node ordering outperforms uniform and CM ordering on both molecular datasets, contrary to prior studies favoring CM ordering.The authors suggest the relative advantage of CM may depend on the dataset and on which generative-quality metrics are used.Source: Table 6 · p. 9, §4.4 · p. 9
• Generating connectivity before the node token performs better consistently than node-first generation across the reported experiments.Figure 3 compares validation loss across block designs.Source: Figure 3 · p. 9, §4.4 · p. 9

• Bilinear probes test whether hidden states at node-type tokens can recover adjacency and shortest-path distance matrices.The method aggregates normalized node representations across layers before training the probe.Source: §5 · p. 9
• SNACK-Transformer hidden representations reconstruct adjacency matrices with AUROC 0.9998, indicating encoded local connectivity, while SPD alignment has MAE 0.9250, suggesting capture of aspects of global graph geometry.Source: §5 · p. 10
• SNACK excels at edge prediction, whereas SMILES is superior at shortest-path-distance prediction, suggesting different structural information is emphasized by the two representations.Table 7 compares model performance on the probing tasks.Source: Table 7 · p. 10, §5 · p. 10

6 Conclusion

• SNACK captures graph structure through a construction process analogous to adjacency-matrix generation, supports structural constraints and GFlowNet training, and performs competitively across benchmarks.The authors identify the fixed, manually designed ordering policy as a limitation and list stereochemistry, jointly learned ordering, and fragment-level generation as future directions.Source: §6 · p. 10

A.1 Definition

• A SNACK string concatenates node blocks, each containing a node token preceded by descending distance tokens paired with edge types to earlier nodes.Each block records that node's connectivity to the previously generated subgraph.Source: §A.1 · p. 16

A.2 Valid masking rule

• Under connected search ordering, each newly generated node must connect to at least one earlier node; BFS masking additionally tracks the node being expanded.Disconnected graphs can instead be represented by concatenating component strings.Source: §A.2 · p. 16

A.3 The number of distance tokens

• SNACK allocates extra distance tokens beyond the largest observed training distance because node reordering can produce longer distances; the required range remains finite.The maximum possible distance is bounded by the total number of nodes.Source: §A.3 · pp. 16–17

A.4 Bijectivity with the adjacency matrix

• The proposition establishes a one-to-one correspondence between SNACK sequences and adjacency matrices.Encoding traverses the lower triangle deterministically; decoding uses node tokens for diagonal entries and distance–edge pairs for off-diagonal entries.Source: §A.4 · p. 17
• Valid distances and descending distance-token order make decoding deterministic, with each sequence component mapping to a unique matrix entry.The proof concludes that distinct sequences reconstruct distinct matrices.Source: §A.4 · p. 17
• Ambiguous tokens can break bijectivity when distinct tokens, such as [O] and [OH2], represent the same molecule.The passage gives H2O as the example.Source: §A.4 · p. 17

B Computing random BFS ordering

• The random BFS ordering probability depends on graph structure, not node indexing, so orderings in the same automorphism group receive identical probabilities.The algorithm starts with n possible roots and multiplies by the factorial of each newly discovered neighbor set’s size before returning −log P.Source: B Computing random BFS ordering · p. 17

C Computational complexity of trajectory evaluation

• A causal Transformer evaluates all next-token probabilities for a complete SNACK sequence in one forward pass, whose length is L = N + 2M + O(1).Causal masking lets each prediction use its preceding prefix without separately encoding intermediate prefixes.Source: C Computational complexity of… · p. 18
• Graph-based evaluation separately encodes each intermediate graph, and batching those states does not remove their separate encoding work.The trajectory has T = Θ(N + M) transitions; T counts state-specific evaluations, not necessarily sequential model calls.Source: C Computational complexity of… · p. 18
• Under M = O(N), sequence evaluation has quadratic cost while dense-attention graph-policy evaluation has cubic cost.The cubic bound is tight for node-by-node construction from a fixed-size initial graph.Source: C Computational complexity of… · p. 18

D Applications of graph-to-sequence transition probability

• Computing q(x|G) supports substructure-conditioned optimization, while exact marginal log-likelihood remains intractable because it requires summing over node orderings.The paper describes importance sampling over sequences drawn from q(x|G) as an approximation.Source: D Applications of graph-to-sequence… · pp. 18–19
• The paper uses fixed random BFS ordering, although the optimal ordering can vary by dataset and jointly optimizing q(x|G) and pθ could improve performance.The proposed possibility follows the approach of Chen et al. [7].Source: D Applications of graph-to-sequence… · p. 18

E Training Objectives for Conditioned GFlowNets

• Conditioned generation trains p(G|G0) in proportion to reward while assigning zero reward to graphs unreachable from the scaffold.The trajectory accounts for graph-to-sequence initialization, sequence continuation, and deterministic termination; the TB objective includes the initial-state, ordering, and reward terms.Source: E Training Objectives for Conditioned… · p. 19

F.1 Model architecture

• The shared distribution-learning Transformer has six layers, dimension 384, six attention heads, and approximately 8.9M parameters; goal-directed learning uses four layers.The architecture follows LLaMA with RMSNorm, SwiGLU, and rotary positional embeddings.Source: §F.1 · p. 19

F.2 Generic graph generation

• Generic graph evaluation covers eight synthetic and real datasets, omits edge-type tokens, and uses disconnected BFS masking for multiple components.Training uses random BFS ordering and five seeds, with early stopping typically around 200k iterations.Source: §F.2 · pp. 19–20

F.3 Molecular string generation

• Molecular experiments compare string representations using specified tokenization and bond conventions, with implicit hydrogens added after generation for several methods.SNACK, STGG, GEEL, and G2PT use single, double, and triple bonds; experiments sample 30k molecules and use three seeds.Source: §F.3 · pp. 20–21
• Conditioned-generation evaluation tests continuations of 129 MOSES molecules, requiring valid, connected outputs that retain the conditioning substructure and add heavy atoms.It samples 100 randomized representations per molecule and evaluates pretrained models without additional fine-tuning.Source: §F.3 · p. 21

F.4 Goal-directed learning

• Goal-directed evaluation includes HOMO–LUMO optimization and similarity optimization toward Aripiprazole and Albuterol; the SMILES-based GFlowNet fails to learn from scratch.The SMILES backward distribution is approximated by setting q(x|G) = 1 because multiple SMILES strings can decode to the same molecule.Source: §F.4 · pp. 21–22

F.5 Bilinear probing

• The bilinear probe is trained on hidden representations from a SNACK model to predict adjacency and shortest-path distance.It uses lower-triangular targets and reconstructs full predictions by symmetrization.Source: §F.5 · p. 22

G.1 Full results on generic graphs

• The generic-graph tables report degree, clustering, and orbit-statistic MMD scores, for which lower values indicate better performance.The tables cover Ego-small, Community-small, Planar, Lobster, Enzymes, SBM, Ego, and Grid; the supplied passages do not state specific cell values.Source: §G.1 · p. 22, Table 8 · p. 23, Table 9 · p. 23

G.2.1 Peptide generation

• SNACK shows a clear validity advantage and outperforms baselines on FCD for Peptides-func, while remaining competitive on SNN.Compared with SELFIES, the other method reported to guarantee 100% validity, SNACK performs better across all metrics.Source: Table 10 · p. 24, §G.2.1 · p. 24

G.2.2 MOSES benchmark

• SNACK-Transformer matches or exceeds reported MOSES baselines, although diverse architectures make strict head-to-head comparison difficult.The results are reported in Tables 11 and 12.Source: Table 11 · p. 24, §G.2.2 · p. 25, Table 12 · p. 25

G.2.3 Explicit hydrogen modeling

• FCD was 0.037 ± 0.003 on QM9 and 0.103 ± 0.002 on MOSES for implicit hydrogen modeling, versus 0.040 ± 0.002 and 0.144 ± 0.031 for explicit modeling.The authors report that implicit hydrogen modeling does not compromise, and may enhance, generative performance.Source: §G.2.3 · p. 25

G.3 Scalability of GFlowNet training

• Across training and inference, SNACK is faster and more memory-efficient than graph-based GFlowNet, with the gap increasing as atom count grows.Measurements use batch sizes 8 for training and 100 for inference; curves are truncated after CUDA out-of-memory failures. Figure 5 shows the scalability measurements.Source: §G.3 · p. 25, Figure 5 · p. 26

G.4 Substructure conditioned generation

• SNACK permits functional groups to attach to any previously generated atom within its bandwidth, and its example yields three valid prefixes rather than SMILES’ two.This flexibility is presented for substructure-conditioned generation from a partial fragment.Source: §G.4 · p. 26

G.5 Model internals

• A bilinear probe finds that SNACK predicts adjacency edges more accurately than the trained SMILES model, while trained SMILES also reconstructs adjacency structure.The probe’s MOSES reconstruction results are presented in Table 13.Source: Table 13 · p. 26, §G.5 · p. 27
• Layer-wise probing finds structural details most recoverable in intermediate SNACK-Transformer layers.Figure 7 visualizes adjacency-matrix reconstructions across layers.Source: §G.5 · p. 27, Figure 7 · p. 27

H.1 Rationale for CM ordering

• SNACK’s bandwidth determines vocabulary size, so CM ordering can reduce the output space from O(N^2) to O(φ̂ · N).Unlike GraphRNN, bandwidth only marginally increases SNACK’s transformer output-projection overhead.Source: §H.1 · p. 27

H.2 Optimal ordering policy depends on dataset

• CM ordering performs better on Community-small and Lobster, while the authors find no universally superior ordering policy across datasets.The authors connect CM’s advantage on these datasets to their low-degree peripheral structure and report differing maximum bandwidth across policies in Table 14.Source: §H.2 · pp. 27–28, Table 14 · p. 28
• Sequence learnability is a more critical determinant of generative quality than output-space reduction alone.The authors note that jointly training the ordering policy with the graph generative model can yield significant gains [7].Source: §H.2 · p. 28

H.3 Analysis of evaluation metrics

• Raw sequence-level losses are misleading across orderings because they differ by the entropy of q(x|G), even under perfect convergence.The paper points to the BFS–CM training-loss gap in Figure 9; per-token normalization may mask ordering-complexity effects.Source: §H.3 · pp. 28–29
• Action-level precision and recall favor CM because BFS allows more valid trajectories, so the authors recommend ordering-invariant graph statistics such as FCD or MMD.They note that BFS performs competitively with CM under MMD in results reported by Diamant et al. [10].Source: §H.3 · p. 29

Discussion

• Existing string-based methods vary in structural validity, graph-domain generality, conditioned-generation support, and evaluation beyond distribution learning.The paper notes that invalid-sample rejection can hinder exploration and training stability in goal-directed settings with sparse rewards.Source: I Discussion · p. 29
• SNACK is presented as a general-purpose string representation guaranteeing 100% structural validity and supporting distribution learning, conditioned generation, and string-based GFlowNets.The paper situates these capabilities among prior string-based graph-generation developments [4] [6] [16] [30] [38].Source: I Discussion · p. 29
• The current framework uses a fixed node ordering policy and atom-level generation; learned ordering and fragment-level generation were not empirically explored.The evaluation also relies on a TB objective in one GFlowNet implementation and lacks extensive hyperparameter search.Source: I Discussion · p. 29
• The authors identify molecular design, including drug discovery and materials science, as potential applications, while noting misuse risks from generating harmful or toxic compounds.They point to responsible deployment and screening protocols as necessary considerations.Source: I Discussion · p. 30