Research map / Graph learning / Graph self-supervised learning

SNACK: A Sequential Notation Framework for Probabilistic Graph Generation

NeurIPS 2026 · Graph learning › Graph self-supervised learning · approach: Diffusion-based graph generation

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SNACK, a bijective string representation of graphs that encodes nonzero lower-triangular adjacency entries, enabling mask-based validity, exact GFlowNet training with automorphism correction, and competitive graph/molecule generation.

Problem

String-based graph generators lack a bijection between strings and graphs, so one graph maps to many strings, hurting probabilistic modeling (likelihood, GFlowNet training) and goal-directed/conditioned generation.

Approach

Linearize the graph row-by-row by encoding only nonzero lower-triangular adjacency entries as distance and edge-type tokens before node tokens, giving a bijection with ordered adjacency matrices; combined with BFS ordering, logit masking (grammar, valence, BFS) and automorphism-corrected trajectory balance enable exact string-based GFlowNets.

Key results

• On MOSES, SNACK (V+B) reaches 1.000 validity with FCD 0.103 and scaffold similarity 0.895, competitive with SMILES and SELFIES.
• On albuterol similarity GFlowNet optimization, SNACK (V+B) reaches top-100 reward 0.736 vs 0.171 for the graph-based GFlowNet.
• Per training step, SNACK-GFlowNet throughput scales better than graph GFlowNet with molecule size (cubic vs quadratic complexity claim); bilinear probe on MOSES achieves adjacency AUROC 0.9998.

Surprising findings

• Node-first block ordering, common in graph-based and GEEL methods, consistently hurt performance versus the edge-first SNACK design.
• Connected-molecule CM ordering underperformed BFS ordering, contrary to prior work favoring CM for bandwidth reduction.
• SMILES-based GFlowNets failed to learn from scratch on the goal-directed tasks.

Limitations

• Ordering policy is fixed and manually designed (BFS), not learned.
• Does not yet handle stereochemistry or chirality.
• Node-level representation only; fragment-level generation not addressed.

Experimental setup

Datasets: QM9 MOSES Planar Lobster Enzymes SBM Ego Grid community-small Ego-small ZINC250k Peptides-func

Benchmarks: QM9 MOSES Planar Enzymes SBM Grid HOMO-LUMO gap optimization albuterol/aripiprazole similarity

Metrics: MMD Validity FCD SNN Fragment similarity Scaffold similarity success rate average reward diversity top-100 reward

Baselines: GraphRNN GDSS DiGress GEEL SMILES SELFIES SAFE STGG G2PT JT-VAE GCPN GraphDF

Builds on: GFlowNet trajectory balance GEEL SELFIES SMILES BFS ordering

Closest papers by meaning

• Graph Generation with $K^2$-trees (ICLR 2024 · similarity 0.87)
• A Simple and Scalable Representation for Graph Generation (ICLR 2024 · similarity 0.86)
• Graph Generative Pre-trained Transformer (ICML 2025 · similarity 0.86)
• GraphGPT: Generative Pre-trained Graph Eulerian Transformer (ICML 2025 · similarity 0.86)
• Flatten Graphs as Sequences: Transformers are Scalable Graph Generators (NeurIPS 2025 · similarity 0.85)
• Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.85)