Instruction set for the representation of graphs

Ezequiel Lopez-Rubio; Mario Pascual-Gonzalez

cs.CLMar 11, 2026

Instruction set for the representation of graphs

Authors: Ezequiel Lopez-Rubio, Mario Pascual-Gonzalez

Organizations: Department of Computer Languages and Computer Science, University of Málaga, Bulevar Louis Pasteur, 35, 29071 Málaga, Spain · ITIS Software. Universidad de Málaga. C/ Arquitecto Francisco Peñalosa 18, 29010, Málaga, Spain

Abstract

We present IsalGraph, a method for representing the structure of any finite, simple graph as a compact string over a nine-character instruction alphabet. The encoding is executed by a small virtual machine comprising a sparse graph, a circular doubly-linked list (CDLL) of graph-node references, and two traversal pointers. Instructions either move a pointer through the CDLL or insert a node or edge into the graph. A key design property is that every string over the alphabet decodes to a valid graph, with no invalid states reachable. A greedy GraphToString algorithm encodes any connected graph into a string in time polynomial in the number of nodes; an exhaustive-backtracking variant produces a canonical string by selecting the lexicographically smallest shortest string across all starting nodes and all valid traversal orders. We evaluate the representation on five real-world graph benchmark datasets (IAM Letter LOW/MED/HIGH, LINUX, and AIDS) and show that the Levenshtein distance between IsalGraph strings correlates strongly with graph edit distance (GED). Together, these properties make IsalGraph strings a compact, isomorphism-invariant, and language-model-compatible sequential encoding of graph structure, with direct applications in graph similarity search, graph generation, and graph-conditioned language modelling

Figures & tables

Instr.	Type	Effect on state $(G,\mathcal{L},\pi_{1},\pi_{2})$
$N$	Primary move (forward)	$\pi_{1}\leftarrow\mathrm{next}_{\mathcal{L}}(\pi_{1})$
$P$	Primary move (backward)	$\pi_{1}\leftarrow\mathrm{prev}_{\mathcal{L}}(\pi_{1})$
$n$	Secondary move (forward)	$\pi_{2}\leftarrow\mathrm{next}_{\mathcal{L}}(\pi_{2})$
$p$	Secondary move (backward)	$\pi_{2}\leftarrow\mathrm{prev}_{\mathcal{L}}(\pi_{2})$
$V$	Node insertion via primary	Add new node $u$ to $G$ ; add edge $(\mathrm{val}_{\mathcal{L}}(\pi_{1}),\,u)$ to $G$ ; insert $u$ into $\mathcal{L}$ immediately after $\pi_{1}$ .
$v$	Node insertion via secondary	Add new node $u$ to $G$ ; add edge $(\mathrm{val}_{\mathcal{L}}(\pi_{2}),\,u)$ to $G$ ; insert $u$ into $\mathcal{L}$ immediately after $\pi_{2}$ .

Table 1: The IsalGraph instruction set.

\mathrm{val}_{\mathcal{L}}(\ell)

denotes the graph-node index stored as payload of CDLL node

\ell

. The

N/n

(

P/p

) instructions traverse the CDLL in the forward (backward) circular direction. The

V/v

instructions always create edges from the pointer node to the new node; the pointer itself does not move. Instructions

C

and

c

differ only for directed graphs.

Figure 1: Aggregated correlation between graph edit distance (GED) and Levenshtein distance across all five benchmark datasets. Each cell at integer coordinates $(i,j)$ shows the count of graph pairs with $\text{GED}=i$ and $\text{Lev}=j$ (log scale; light = few pairs, dark = many pairs); white cells contain no observed pairs. Dashed grey line: identity ( $\text{Lev}=\text{GED}$ ). Solid red line: ordinary least-squares (OLS) regression. (a) Canonical encoding ( $n=3,424,764$ pairs, $\rho=0.700$ , $\beta=0.79$ ). (b) Greedy-min encoding ( $n=3,424,764$ pairs, $\rho=0.665$ , $\beta=0.78$ ). (c) Greedy-rnd( $v_{0}$ ) encoding ( $n=3,424,764$ pairs, $\rho=0.590$ , $\beta=0.82$ ). Reported statistics: $\rho$ denotes Spearman’s rank correlation coefficient, measuring monotonic association between the two distance measures. $\beta$ denotes the OLS regression slope; $\beta=1$ would indicate that Levenshtein and GED operate on the same scale, while $\beta<1$ indicates that Levenshtein distances grow more slowly than GED.

		IAM LOW	IAM MED	IAM HIGH	LINUX	AIDS
Prop.	$N$	1,180	1,253	2,059	89	769
	Pairs	695,610	784,378	2,118,711	1,685	131,148
	$\bar{m}$	3.07	3.17	4.56	8.35	10.70
Spear. $\rho$	Canonical	0.934 ∗∗∗	0.876 ∗∗∗	0.682 ∗∗∗	0.433 ∗∗∗ (-0.012)	0.349 ∗∗∗
	Greedy-Min	0.908 ∗∗∗ (-0.027)	0.862 ∗∗∗ (-0.014)	0.625 ∗∗∗ (-0.057)	0.445 ∗∗∗	0.304 ∗∗∗ (-0.045)
	Greedy-rnd( $v_{0}$ )	0.706 ∗∗∗ (-0.228)	0.682 ∗∗∗ (-0.195)	0.577 ∗∗∗ (-0.105)	0.301 ∗∗∗ (-0.144)	0.251 ∗∗∗ (-0.098)

Table 2: Dataset properties and Spearman

\rho

correlation between GED and IsalGraph Levenshtein distance across encoding methods.

\bar{m}

: mean edges per graph (complexity proxy). Spearman-

\rho

difference between best method per dataset is showcased. Best

\rho

per dataset in bold .

Figure 2: Empirical time complexity of IsalGraph encoding methods on random graphs (Barabási–Albert

m\in\{1,2\}

and Erdős–Rényi

p\in\{0.3,0.5\}

). Horizontal axis: number of nodes

n

; vertical axis: encoding time in seconds (log scale). Markers show the median across graph instances; error bars denote the interquartile range. Dashed lines are polynomial fits

T=c\cdot n^{\alpha}

via OLS on log–log data. Greedy-rnd(

v_{0}

\alpha=3.1

R^{2}=0.989

. Greedy-Min:

\alpha=4.5

R^{2}=0.989

. Canonical:

\alpha=9.0

R^{2}=0.979

. Greedy methods exhibit polynomial scaling (

\alpha\approx 3

–

5

), while the canonical method scales super-polynomially (

\alpha\approx 9

) on random graphs and becomes infeasible beyond

n\approx 12

Figure 3: Neighbourhood topology of the house graph

G_{0}

(5 nodes, 6 edges) under two distance metrics. Centre column: base graph

G_{0}

with its canonical IsalGraph encoding (colour-coded by instruction type). Top rows: 4 representative 1-GED neighbours (single edge edit), with Levenshtein distances

\mathrm{Lev}\in[1,\,5]

to the encoding of

G_{0}

. Bottom rows: 4 representative 1-Levenshtein neighbours (single character substitution, insertion, or deletion in the instruction string), with GED values

\mathrm{GED}\in[1,\,2]

. Dashed red edges indicate structural differences from

G_{0}

. Horizontal heatmaps below each graph render the IsalGraph instruction string with per-character colouring (alphabet

\Sigma=\{N,n,P,p,V,v,C,c,W\}

). The asymmetry between 1-GED and 1-Levenshtein neighbourhoods illustrates that graph-space proximity does not imply string-space proximity, and vice versa.

Instruction Set and Language for Hypergraphs
Jul 11, 2026Mario Pascual-Gonzalez, Ezequiel Lopez-RubioGraph Matching
Department of Computer Languages and Computer Science University of Málaga Bulevar Louis Pasteur, 35 29071 Málaga, Spain · ITIS Software. Universidad de Málaga. C/ Arquitecto Francisco Peñalosa 18, 29010, Málaga, Spain
DRESS: A Continuous Framework for Structural Graph Refinement
Feb 24, 2026Eduar Castrillo VelillaGraph Representation Learning
Breaking Hard Isomorphism Benchmarks with DRESS
Mar 19, 2026Eduar Castrillo VelillaGraph Matching

Jul 11, 2026J/K move · Enter open · S save

Instruction Set and Language for Hypergraphs

Mario Pascual-Gonzalez, Ezequiel Lopez-Rubio

Department of Computer Languages and Computer Science University of Málaga Bulevar Louis Pasteur, 35 29071 Málaga, Spain · ITIS Software. Universidad de Málaga. C/ Arquitecto Francisco Peñalosa 18, 29010, Málaga, Spain

Graph Matching

Open paper AskPDF arXiv

We present IsalHG, a method for representing the structure of any finite, connected hypergraph of bounded hyperedge arity as a string over a compact instruction alphabet

Σ_{\mathrm{HG}}

. The encoding is executed by a small virtual machine comprising a sparse hypergraph, a circular doubly-linked list (CDLL) of node references, and

k

traversal pointers, where

k

bounds the hyperedge arity. Instructions either move a pointer through the CDLL or insert a hyperedge, optionally together with new nodes, into the hypergraph. Every string over

Σ_{\mathrm{HG}}

decodes to a valid hypergraph; the alphabet is closed. A greedy HypergraphToString (h2s) algorithm encodes any connected hypergraph into a string; a backtracking variant seeded at nodes of lexicographically maximal structural tuple produces a canonical string

w^{*}

, which we conjecture to be a complete isomorphism invariant. Canonical-string equality then decides hypergraph isomorphism natively, without the standard reduction to the Levi incidence graph followed by a graph-isomorphism engine. We verify the round-trip property

s2h(h2s(H)) \cong H

on 150 connected random uniform hypergraphs and on named combinatorial designs, and we benchmark the canonical algorithm against the three practically available exact baselines -- nauty, Traces, and bliss operating on the 2-coloured Levi graph -- across a

(n, c)

grid with ten seeds per cell. All four methods agree on every one of 600 isomorphism verdicts, consistent with the completeness conjecture. On wall-clock time the Levi baselines dominate every tested cell by three to five orders of magnitude (geometric-mean ratio

311\times

117{,}672\times

), which we report as measured. We contribute the representation framework, a conjecture of canonical completeness, and the first native-versus-Levi benchmark for hypergraph isomorphism.

Abstract

Explore similar work

Instruction Set and Language for Hypergraphs

DRESS: A Continuous Framework for Structural Graph Refinement

Breaking Hard Isomorphism Benchmarks with DRESS