IsalGraph: Encoding Graphs as Strings a Language Model Can Actually Read

Paper: 2603.11039 Authors: Ezequiel Lopez-Rubio, Mario Pascual-Gonzalez Categories: cs.CL, cs.AI, cs.DS

The Gap

Graphs are everywhere in ML — molecules, social networks, program ASTs, knowledge graphs. But the dominant tools for working with them (GNNs, graph kernels, GED solvers) all share a structural problem: they don’t produce a flat string. That matters because the most powerful sequence models (transformers, LLMs) eat strings for breakfast. If you want to use a language model to generate or compare graphs, you need a serialization.

Prior serializations exist but each has a catch. Adjacency matrices are quadratic in size and not canonical. SMILES (for molecules) is domain-specific and breaks on non-molecular graphs. Graph6 and Sparse6 are compact but not designed for edit-distance alignment — Levenshtein distance on them doesn’t correlate with graph edit distance. And most serializations have invalid states: a random string doesn’t decode to a valid graph, which makes generative modeling painful (you need constrained decoding or heavy post-processing).

The specific gap: no general-purpose, compact, always-valid, isomorphism-invariant graph serialization whose string edit distance tracks graph edit distance.

Problem: Graphs can't be fed to sequence models without serialization
    |
    v
Prior art: Adjacency matrix (too big), SMILES (domain-locked),
           Graph6 (no GED alignment), ad-hoc (invalid states)
    |
    v
Assumption: A small virtual machine with constrained ops
            can guarantee validity by construction
    |
    v
Method: IsalGraph -- 9-instruction VM over CDLL + sparse graph
        GraphToString (greedy) + canonical variant (backtracking)
    |
    v
Evidence: Levenshtein(IsalGraph strings) ~ GED on 5 benchmark datasets
    |
    v
Conclusion: Compact, valid, canonical, LM-compatible graph encoding

The Increment

One sentence: Before this paper, feeding a graph to a language model or using string edit distance as a graph similarity proxy required ugly hacks; after it, you have a clean, always-valid encoding where Levenshtein distance is a meaningful graph metric.

Core Mechanism

IsalGraph is a tiny virtual machine with three pieces of state: a sparse graph (nodes and edges accumulate here), a circular doubly-linked list (CDLL) of references to graph nodes, and two traversal pointers (call them P and Q) that walk around the CDLL. The nine instructions either move P or Q forward/backward around the ring, insert a new node into the graph (and add it to the CDLL), or insert an edge between the nodes currently pointed to by P and Q.

The key design insight is that every instruction is always applicable — there are no preconditions that can fail. Moving a pointer around a ring never fails. Inserting a node always succeeds (just add it). Inserting an edge between two valid pointer targets always succeeds (it’s a simple graph, so duplicates are silently ignored). This means any string over the nine-character alphabet decodes to some valid graph. No invalid states. No error handling. The VM is total.

Encoding goes the other direction. The greedy GraphToString picks a starting node, initializes the CDLL with it, then repeatedly finds the cheapest instruction sequence to bring the next unvisited node or edge into scope and emits those instructions. The canonical variant runs this over all possible starting nodes and all valid traversal orders, keeping the lexicographically smallest shortest string — giving you an isomorphism-invariant fingerprint.

  Input graph G
       |
       v
  Pick start node  <----+
       |                |
       v                | (backtracking variant:
  Init CDLL + ptrs      |  try all start nodes,
       |                |  keep lex-min result)
       v                |
  Greedy emit loop -----+
  [move P? move Q? insert node? insert edge?]
       |
       v
  String s over {a,b,c,d,e,f,g,h,i}
       |
       v
  Decode: VM replays s -> reconstructs G

Think of it like giving someone directions to draw a graph on a whiteboard using only nine spoken commands. The listener holds a marker (two markers, actually — P and Q), a whiteboard (the graph), and a lazy-susan of node labels (the CDLL). You can say “spin your left marker one step clockwise,” “spin your right marker one step back,” “add a new node to the lazy-susan,” or “draw a line between whatever your two markers are pointing at right now.” Because every command is always physically doable, your listener can never get confused or stuck — any sequence of commands produces some drawing. The encoding problem is just: what’s the shortest sequence of commands that produces this specific drawing?

Key Concepts

• Circular Doubly-Linked List (CDLL) as traversal context: The CDLL isn’t storing the graph — it’s storing a *cursor context for traversal. Think of it as a ring of bookmarks. As you encode a graph, you add new nodes to this ring and move your two pointers around it to “aim” at the nodes you want to connect next. The ring structure means pointer movement wraps around naturally, which is why it’s always valid. Without the CDLL, you’d need explicit node-addressing instructions, which would either blow up the alphabet size or introduce invalid states (what if you address a node that doesn’t exist yet?).

• Isomorphism invariance via canonical form: Two graphs are isomorphic if one is just a relabeling of the other — same structure, different node names. A canonical encoding assigns the same string to all isomorphic graphs. IsalGraph achieves this by exhaustive search: try every starting node and every valid traversal order, take the lexicographically smallest shortest string. It’s brute-force canonicalization, not a clever polynomial-time algorithm, which is fine for small graphs but worth noting for scale.

• Levenshtein distance as a GED proxy: Graph Edit Distance (GED) counts the minimum node/edge insertions and deletions to transform one graph into another. Computing it exactly is NP-hard. The paper’s bet is that if two graphs have similar structure, their IsalGraph strings will also be similar, so Levenshtein distance (cheap to compute) approximates GED (expensive). This is an empirical claim, not a theoretical guarantee — and the paper validates it on five datasets.

Framework Shift

Before (mainstream approach):        After (this paper):

  Graph G                              Graph G
     |                                    |
     v                                    v
  GNN / kernel / GED solver           IsalGraph VM encoder
     |                                    |
     v                                    v
  Embedding vector                     String "aabcdiefg..."
  or distance matrix                      |
     |                              +-----+-----+
     v                              v           v
  Downstream task               LM directly  Levenshtein
  (needs special arch)          ingests it   ~ GED

From task-specific graph architectures to a universal string serialization, the core shift is: treat graph structure as a language, not a topology.

Expert Assessment

Problem choice: This is a real gap, not a manufactured one. The friction between graph-structured data and sequence models is genuinely felt by anyone who’s tried to do graph generation with LLMs. The paper sits at a productive intersection of graph theory and NLP infrastructure. It’s not a flashy problem, but it’s a useful one.

Method maturity: The VM design is clever — the “always-valid by construction” property is the paper’s best idea, and it’s clean. The canonical encoding via exhaustive backtracking is less impressive; it’s exponential in the worst case and the paper doesn’t deeply analyze when it’s tractable. The greedy encoder is polynomial but not canonical, so you’re choosing between speed and uniqueness. A smarter canonicalization algorithm (e.g., based on graph automorphism groups) would strengthen the contribution significantly.

Experimental integrity: The correlation between Levenshtein distance and GED is the central empirical claim, and the five datasets (IAM Letter LOW/MED/HIGH, LINUX, AIDS) are standard benchmarks — that’s good. But the paper doesn’t compare against other serializations (Graph6, SMILES where applicable, adjacency list) on the same correlation metric. Without that baseline, you can’t tell if IsalGraph is *better or just also works. That’s a meaningful gap in the evaluation.

Writing quality: The VM specification section is precise and well-done. The weakest part is the discussion of computational complexity for the canonical encoder — it’s hand-wavy where it should be rigorous. Tightening that section (with a proper complexity analysis and a discussion of graph classes where backtracking is tractable) would elevate the paper from “interesting system paper” to “solid theoretical contribution.”

Verdict: weak accept — the core idea is sound and practically useful, but the evaluation doesn’t fully justify the claims and the canonical encoder’s complexity is underanalyzed.

Takeaways

• The “always-valid by construction” VM design is directly stealable for any domain where you want to do generative modeling over structured objects. If you can define a small instruction set where every instruction is always applicable, you get free validity guarantees for any sequence model you train on it. This pattern applies to trees, DAGs, chemical reactions, even simple programs.

• Using a CDLL as a traversal cursor (rather than explicit addressing) is a nice trick for keeping the instruction alphabet small while maintaining enough expressiveness to reach any node. Worth thinking about in other serialization contexts.

• The Levenshtein-as-GED-proxy idea is practically useful even if theoretically loose. If you’re doing graph similarity search and GED is too slow, this gives you a cheap approximate metric that’s easy to implement and doesn’t require a GNN.