Instruction set for the representation of graphs

This paper introduces IsalGraph, a novel method that encodes any finite simple graph into a compact, valid nine-character instruction string using a virtual machine, enabling efficient canonical representation and demonstrating strong correlation between string edit distance and graph edit distance for applications in similarity search and language modeling.

The Gist

Imagine you have a complex map of a city, with streets (edges) connecting buildings (nodes). Now, imagine you want to send a text message to a friend describing this entire city so they can rebuild it exactly.

If you tried to describe every possible connection between every building, the message would be huge and messy. If you just listed the buildings in a random order, your friend might build a completely different city because they wouldn't know which building connects to which.

This is the problem the paper "IsalGraph" tries to solve. The authors have invented a new way to turn any network (like a social network, a molecule, or a circuit) into a short, simple string of letters that a computer (or even a human) can read and perfectly reconstruct.

Here is the breakdown of how it works, using some everyday analogies.

1. The Problem: The "Photo Album" vs. The "Instruction Manual"

Most computers currently store graphs like a giant photo album (an adjacency matrix). If you have 1,000 people, you need a 1,000 x 1,000 grid to show who knows whom.

• The Flaw: It's huge (wastes space), it's 2D (hard for AI to read like a story), and if you shuffle the order of the people in the album, the grid looks totally different, even though the friendships haven't changed.

IsalGraph is different. It doesn't take a photo; it writes an instruction manual. It says: "Start here, walk to that building, build a new one, connect them, then walk back."

2. The Machine: The "Circular Train" and the "Two Conductors"

To write this manual, the authors invented a tiny, imaginary machine with three parts:

1. The Graph: The city being built.
2. The Circular Train (CDLL): Imagine the buildings are cars on a circular train track. You can move forward or backward around the loop.
3. Two Conductors (Pointers): Two people standing on the train. Let's call them Primary and Secondary.

The "language" of IsalGraph is a 9-letter alphabet (like N, P, V, C). Each letter tells the conductors what to do:

• N / P (Move): "Primary conductor, move forward/backward one car."
• n / p (Move): "Secondary conductor, move forward/backward one car."
• V / v (Build): "Build a new building right next to where the Primary/Secondary conductor is standing, and connect it to the current building."
• C / c (Connect): "Build a bridge between where the Primary conductor is and where the Secondary conductor is."
• W (Wait): "Do nothing."

The Magic Trick: The most important rule is that every possible string of these letters creates a valid city. You can't type a "garbage" string that breaks the machine. If you type nonsense, the machine just builds a weird but valid city. This makes it perfect for AI, because the AI doesn't have to worry about making mistakes that crash the system.

3. The Translator: Turning a City into a String

How do you turn a real graph into this string?
The authors use a greedy algorithm (a "greedy" strategy). Imagine you are a tour guide trying to describe a maze to a blind person.

1. You start at the entrance.
2. You look around: "Is there a new path I haven't described yet?"
3. If yes, you move your conductors to that spot (using the cheapest moves) and say "Build a new room here!"
4. If no new rooms, but there's a path to a room we already know about, you say "Connect these two!"
5. Repeat until the whole maze is described.

To make the description unique (so that two identical mazes always get the exact same string), the authors suggest trying every possible starting point and every possible order of visiting rooms, then picking the shortest, alphabetically first string. This is the "Canonical" string.

4. Why This Matters: The "Similarity" Test

The paper tests this on real-world data (like chemical molecules and Linux code structures). They found something amazing:

• If two graphs are structurally similar (like two slightly different versions of a molecule), their IsalGraph strings are very similar (only a few letters different).
• If two graphs are very different, their strings are very different.

This is like comparing two sentences. If you change one word in a sentence, the meaning changes slightly. If you change the whole sentence, the meaning is totally different. This allows computers to use Levenshtein distance (a standard way to measure how different two text strings are) to measure how different two complex networks are.

5. The Trade-off: Speed vs. Perfection

• The Fast Way (Greedy): You can generate a string quickly, but if you start at a different building, you might get a slightly different string for the same city. It's fast and good enough for most things.
• The Perfect Way (Canonical): You try every possible start and order to find the "one true string." This guarantees that two identical cities always get the exact same string. However, this is very slow for big cities (it takes a long time to check every possibility).

Summary

IsalGraph is a new way to turn complex networks into simple text strings.

• It's compact: It uses fewer characters than a grid.
• It's safe: Every text string builds a valid graph.
• It's smart: Similar graphs get similar strings, making it easy for AI to learn, compare, and generate new networks.

Think of it as the difference between sending a friend a blurry, giant photo of a city (the old way) versus sending them a precise, step-by-step recipe to build the city from scratch (IsalGraph). The recipe is easier to edit, easier to compare, and easier for a computer to understand.

Technical Summary

Here is a detailed technical summary of the paper "Instruction Set for the Representation of Graphs" by Ezequiel López-Rubio and Mario Pascual-González.

1. Problem Statement

Graphs are fundamental data structures in fields ranging from molecular chemistry to social network analysis. However, representing graphs for modern machine learning, particularly Large Language Models (LLMs) and sequential deep learning architectures, presents significant challenges:

• Adjacency Matrices: The standard representation ($O(N^2)$ space) is sparse-inefficient, inherently 2D (unsuitable for sequential models), and breaks permutation equivariance (the representation changes if node labels are shuffled).
• Existing Sequential Encodings: Many attempts to encode graphs as strings fail to meet four critical criteria simultaneously:
  1. Compactness: Efficient for sparse graphs.
  2. Reversibility: The original graph must be exactly recoverable.
  3. Structure Preservation: Similar graphs should yield similar strings.
  4. Canonicity: Isomorphic graphs must produce a unique, identical string representation.

The authors propose IsalGraph, a novel method that encodes graph structure as a compact string over a small instruction alphabet, satisfying all four criteria.

2. Methodology: IsalGraph

IsalGraph defines a graph representation via a 9-instruction virtual machine (VM). The encoding process involves two algorithms: StringToGraph (S2G) for decoding and GraphToString (G2S) for encoding.

2.1 The Interpreter State

The VM maintains a state $S = (G, L, \pi)$ consisting of:

• $G$: A finite, simple graph built incrementally.
• $L$: A Circular Doubly-Linked List (CDLL) containing references to the graph nodes.
• $\pi = (\pi_1, \pi_2)$: Two traversal pointers (primary and secondary) pointing to nodes within the CDLL.

2.2 The Instruction Alphabet ($\Sigma$)

The encoding uses a 9-character alphabet: $\{N, n, P, p, V, v, C, c, W\}$.

• Pointer Movement: N/P move the primary pointer forward/backward; n/p move the secondary pointer.
• Node Insertion: V inserts a new node connected to the primary pointer's target; v connects to the secondary pointer's target. Crucially, the pointer does not move after insertion.
• Edge Insertion: C creates an edge between the primary and secondary targets; c creates the reverse edge (relevant for directed graphs).
• No-op: W leaves the state unchanged.

Key Property: Every possible string over $\Sigma$ decodes to a valid graph. There are no "invalid" states, making the representation robust for generative models.

2.3 Encoding Algorithms

• StringToGraph (S2G): A deterministic algorithm that executes instructions sequentially to reconstruct the graph.
• GraphToString (G2S): A greedy algorithm that traverses the input graph to generate the instruction string. It minimizes pointer movement costs by selecting the cheapest displacement $(a, b)$ that allows a structural operation (adding a node or edge).
• Canonical String ($w^*_G$): To ensure isomorphism invariance (ignoring node labeling), the paper proposes an exhaustive backtracking variant. It explores all starting nodes and all valid neighbor traversal orders, selecting the lexicographically smallest shortest string as the canonical representation.

3. Key Contributions

1. Universal Validity: Unlike other encodings, every string in the IsalGraph language decodes to a valid graph, eliminating the need for validity-checking decoders.
2. Reversibility: The G2S and S2G algorithms form a perfect round-trip for connected graphs.
3. Conjectured Canonicity: The authors conjecture that the canonical string $w^*_G$ is a complete graph invariant (i.e., $G \cong H \iff w^*_G = w^*_H$). Empirical tests on 71 graph pairs showed 100% accuracy in distinguishing isomorphic vs. non-isomorphic graphs.
4. Metric Locality: The Levenshtein distance between IsalGraph strings correlates strongly with the Graph Edit Distance (GED), a standard metric for structural dissimilarity.

4. Experimental Results

The authors evaluated IsalGraph on five real-world datasets (IAM Letter, LINUX, AIDS) and synthetic random graphs.

4.1 Correlation with Graph Edit Distance (GED)

• Strong Correlation: The Levenshtein distance between IsalGraph strings showed a high Spearman rank correlation ($\rho$) with GED.
  • IAM Letter (Sparse): $\rho \approx 0.93$ (Canonical encoding).
  • LINUX/AIDS (Denser): $\rho$ decreased to $\approx 0.35–0.45$ as graph density increased, but remained statistically significant.
• Compression: Levenshtein distances grew slower than GED ($\beta < 1$ in regression), indicating that structurally distant graphs often share long common subsequences in their instruction strings.

4.2 Time Complexity

• Greedy Variants: The greedy encoding methods scale polynomially ($T \sim n^{3.1}$ to $n^{4.5}$), handling graphs up to 50 nodes efficiently.
• Canonical Variant: The exhaustive backtracking approach scales super-polynomially ($T \sim n^{9.0}$), becoming computationally infeasible for graphs larger than $\approx 12$ nodes.

4.3 Neighborhood Analysis

• Asymmetry: Small structural changes (GED=1) can result in large string changes (Levenshtein > 1) because the optimal traversal order may shift entirely.
• Robustness: Conversely, small string changes (Levenshtein=1) always result in small structural changes (GED $\le$ 2). This makes the representation conservative: it is more likely to overestimate dissimilarity than to miss a similar graph, which is advantageous for retrieval tasks prioritizing recall.

5. Significance and Applications

IsalGraph offers a bridge between structural graph data and sequential language models:

• Graph Similarity Search: The Levenshtein distance on IsalGraph strings serves as a computationally efficient proxy for the NP-hard GED, enabling fast $k$-nearest-neighbor retrieval.
• Graph Generation: Because every string is valid, IsalGraph strings can be used as direct inputs for LLMs or diffusion models to generate new, valid graph structures without post-hoc correction.
• Graph-Conditioned Modeling: The representation allows for "graph-conditioned language modeling," where the structure of a graph is treated as a sequence of tokens, enabling reasoning over graph topology using standard transformer architectures.

Limitations

• The canonical completeness (isomorphism invariance) remains a conjecture, though empirically supported.
• The canonical encoding is too slow for large graphs ($N > 12$), limiting its use to small-scale exact matching.
• The current implementation requires connected graphs; disconnected components or directed graphs with unreachable nodes require preprocessing.