Paper deep dive
Instruction set for the representation of graphs
Ezequiel Lopez-Rubio, Mario Pascual-Gonzalez
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 3/22/2026, 6:20:05 AM
Summary
The paper introduces IsalGraph, a novel method for representing finite, simple graphs as compact strings using a nine-character instruction alphabet. The encoding utilizes a virtual machine with a sparse graph, a circular doubly-linked list (CDLL), and two traversal pointers. The method includes a greedy 'GraphToString' algorithm and an exhaustive-backtracking variant to produce canonical strings, which are shown to be isomorphism-invariant and correlate with graph edit distance, making them suitable for graph similarity search and language modeling.
Entities (5)
Relation Signals (3)
StringToGraph → decodes → IsalGraph
confidence 95% · The S2G algorithm (Algorithm 1) executes an IsalGraph string instruction by instruction
GraphToString → encodes → IsalGraph
confidence 95% · The G2S algorithm is the inverse of S2G: given a graph G and a starting node v0, it produces an IsalGraph string
IsalGraph → uses → Circular Doubly-Linked List
confidence 95% · The encoding is executed by a small virtual machine comprising a sparse graph, a circular doubly-linked list (CDLL)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 \emph{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
Tags
Links
- Source: https://arxiv.org/abs/2603.11039v1
- Canonical: https://arxiv.org/abs/2603.11039v1
Trouble viewing inline? Open PDF directly →
Full Text
54,861 characters extracted from source content.
Expand or collapse full text
Instruction set for the representation of graphs Ezequiel López-Rubio Department of Computer Languages and Computer Science University of Málaga Bulevar Louis Pasteur, 35 29071 Málaga, Spain ezeqlr@lcc.uma.es & Mario Pascual-González Department of Computer Languages and Computer Science University of Málaga Bulevar Louis Pasteur, 35 29071 Málaga, Spain mpascual@uma.es Corresponding author. 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 Σ 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 wG∗w^*_G 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. Keywords graph representation ⋅· adjacency matrix ⋅· instruction sequences ⋅· deep learning ⋅· language models ⋅· structural patterns 1 Introduction Graphs are among the most expressive data structures available to scientists and engineers. Molecular compounds, social networks, knowledge bases, protein interaction networks, and circuit topologies can all be modelled as collections of nodes connected by edges (Zhou et al., 2020; Khoshraftar and An, 2024; Ju and others, 2024). A central challenge in contemporary computational graph processing is representation: how should the structure of a graph be encoded in a form that supports efficient computation, generalisation, and downstream learning? The dominant answer is the adjacency matrix. Given a graph G=(V,E)G=(V,E) on N=|V|N=|V| nodes, its adjacency matrix MG∈0,1N×NM_G∈\0,1\^N× N records which pairs of nodes are connected. The adjacency matrix is the foundation of spectral graph theory, algebraic graph algorithms, and virtually all existing deep learning approaches to graphs (Kipf and Welling, 2017; Hamilton et al., 2017; Veličković et al., 2018). Its limitations, however, are substantial: it occupies O(N2)O(N^2) space regardless of graph sparsity. Furthermore, it is inherently two-dimensional and therefore not directly consumable by sequential models such as recurrent networks or transformers. Last but not least, it breaks permutation equivariance because its meaning depends on the arbitrary ordering assigned to the nodes. A possible alternative line of research seeks to encode graphs as sequences that can be fed to sequence models. This is particularly appealing in the current era of large language models, which have demonstrated remarkable capacity to process, generate, and reason over sequential data (Vaswani et al., 2017; Devlin et al., 2019). The challenge is to design a sequential encoding that is: (i) compact, using much less than O(N2)O(N^2) symbols for sparse graphs; (i) reversible, so that the original graph structure can be recovered exactly from the string; (i) structure-preserving, so that similar graphs yield similar strings; and (iv) canonicalisable, admitting a unique representative string per isomorphism class. This paper presents IsalGraph, a novel methodology for sequential graph representation satisfying all four desiderata. The encoding is defined by a small virtual machine comprising a sparse graph, a circular doubly linked list (CDLL) of graph nodes, and two traversal pointers. Nine instructions move the pointers through the CDLL or insert nodes and edges into the graph. Executing any string in the instruction language decodes it into a graph; conversely, a greedy algorithm encodes any connected graph into a string. It must be highlighted that all strings over the defined alphabet are valid, i.e. they decode to a graph. A canonical string is obtained by minimising string length over all starting nodes and all valid traversal orders, producing a complete graph invariant with formal correctness guarantees. Our previous work (López-Rubio, 2025) is substantially different from IsalGraph because the older approach requires a fixed ordering of the nodes and does not employ a circular doubly linked list of nodes. The structure of this paper is as follows. Section 2 presents the graph representation methodology. After that, Section 3 reports the results of an exploratory computational experiment. Finally, Section 5 deals with the conclusions. 2 Methodology This section presents the formal machinery of IsalGraph. Subsection 2.1 defines the interpreter state and instruction set. Subsection 2.1.3 describes the StringToGraph (S2GS2G) algorithm. Subsection 2.2 presents the GraphToString (G2SG2S) algorithm. Subsection 2.3 states the canonical-string invariance conjecture. Subsection 2.4 establishes the topological relationship between the IsalGraph string metric and graph edit distance. 2.1 Instruction Set and String Execution 2.1.1 Interpreter State The IsalGraph interpreter maintains three components simultaneously during the execution of an instruction string. Definition 2.1 (Interpreter state). An IsalGraph interpreter state is a triple =(G,ℒ,π)S=(G,\,L,\,π) where: • G=(VG,EG)G=(V_G,E_G) is a finite, simple graph built incrementally, with nodes identified by contiguous non-negative integers 0,1,…,|VG|−1\0,1,…,|V_G|-1\. • ℒL is an array-backed circular doubly-linked list (CDLL) whose nodes carry graph-node indices as integer payloads. We write valℒ(ℓ)val_L( ) for the payload of CDLL node ℓ , and next(ℓ)next( ), prev(ℓ)prev( ) for its successor and predecessor in the circular order. The CDLL index space and the graph node index space are distinct: a CDLL node ℓ is not the same object as graph node valℒ(ℓ)val_L( ). • π=(π1,π2)π=( _1, _2) is a pair of pointers, where each pointer is a CDLL node index. π1 _1 is called the primary pointer and π2 _2 the secondary pointer. Initial state. Before any instruction is executed, the interpreter is placed in the following initial state: (i) G contains exactly one node (node 0) and no edges. (i) ℒL contains exactly one node whose payload is graph node 0. (i) Both pointers π1 _1 and π2 _2 point to this single CDLL node. 2.1.2 The Instruction Alphabet IsalGraph strings are drawn from the nine-character alphabet Σ=N,n,P,p,V,v,C,c,W. \;=\;\N,\,n,\,P,\,p,\,V,\,v,\,C,\,c,\,W\. The semantics of each instruction are defined in Table 1 and expanded below. Table 1: The IsalGraph instruction set. valℒ(ℓ)val_L( ) denotes the graph-node index stored as payload of CDLL node ℓ . The N/nN/n (P/pP/p) instructions traverse the CDLL in the forward (backward) circular direction. The V/vV/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. Instr. Type Effect on state (G,ℒ,π1,π2)(G,L, _1, _2) N Primary move (forward) π1←nextℒ(π1) _1 _L( _1) P Primary move (backward) π1←prevℒ(π1) _1 _L( _1) n Secondary move (forward) π2←nextℒ(π2) _2 _L( _2) p Secondary move (backward) π2←prevℒ(π2) _2 _L( _2) V Node insertion via primary Add new node u to G; add edge (valℒ(π1),u)(val_L( _1),\,u) to G; insert u into ℒL immediately after π1 _1. v Node insertion via secondary Add new node u to G; add edge (valℒ(π2),u)(val_L( _2),\,u) to G; insert u into ℒL immediately after π2 _2. C Edge insertion (primary → secondary) Add edge (valℒ(π1),valℒ(π2))(val_L( _1),\,val_L( _2)) to G. For undirected graphs, the reverse edge is also added. c Edge insertion (secondary → primary) Add edge (valℒ(π2),valℒ(π1))(val_L( _2),\,val_L( _1)) to G. Equivalent to C for undirected graphs. W No-op State is unchanged. Critical semantic note. In the V and v instructions, the new CDLL node for u is inserted after the pointer’s current CDLL node, but the pointer itself does not advance to the new node. This means that after a V instruction, π1 _1 still references the same CDLL node as before the instruction was executed. Every string is valid. A key design property of the IsalGraph alphabet is that every string w∈Σ∗w∈ ^* decodes to a valid finite simple graph. No instruction can produce an undefined or inconsistent state: pointer movements wrap around the circular CDLL, and node- and edge-insertion instructions always have a well-defined, deterministic effect. 2.1.3 The StringToGraph Algorithm The S2GS2G algorithm (Algorithm 1) executes an IsalGraph string instruction by instruction, starting from the initial state and returning the resulting graph. Algorithm 1 S2G(w,)S2G(w,\,directed): StringToGraph 1:String w∈Σ∗w∈ ^*; Boolean directed 2:Graph G such that S2G(w)=GS2G(w)=G 3:⊳ Initialise interpreter state 4:G←G← new graph with one node u0=0u_0=0, directed ==directed 5:ℒ←L← new CDLL; ℓ0←ℒ.insert_after(∅,u0) _0 .insert\_after( ,\;u_0) 6:π1←ℓ0 _1← _0; π2←ℓ0 _2← _0 7:⊳ Execute each instruction in turn 8:for each character σ in w do 9: if σ=Nσ=N then 10: π1←ℒ.next(π1) _1 .next( _1) 11: else if σ=Pσ=P then 12: π1←ℒ.prev(π1) _1 .prev( _1) 13: else if σ=nσ=n then 14: π2←ℒ.next(π2) _2 .next( _2) 15: else if σ=pσ=p then 16: π2←ℒ.prev(π2) _2 .prev( _2) 17: else if σ=Vσ=V then 18: u←G.add_node()u← G.add\_node() 19: G.add_edge(valℒ(π1),u)G.add\_edge\! (val_L( _1),\;u ) 20: ℒ.insert_after(π1,u)L.insert\_after( _1,\;u) ⊳ pointer π1 _1 does not move 21: else if σ=vσ=v then 22: u←G.add_node()u← G.add\_node() 23: G.add_edge(valℒ(π2),u)G.add\_edge\! (val_L( _2),\;u ) 24: ℒ.insert_after(π2,u)L.insert\_after( _2,\;u) ⊳ pointer π2 _2 does not move 25: else if σ=Cσ=C then 26: G.add_edge(valℒ(π1),valℒ(π2))G.add\_edge\! (val_L( _1),\;val_L( _2) ) 27: else if σ=cσ=c then 28: G.add_edge(valℒ(π2),valℒ(π1))G.add\_edge\! (val_L( _2),\;val_L( _1) ) 29: else if σ=Wσ=W then 30: skip ⊳ no-op 31: end if 32:end for 33:return G Remark 2.2. For undirected graphs, add_edge(u,v)(u,v) inserts both (u,v)(u,v) and (v,u)(v,u) into the adjacency structure, so instructions C and c have identical effect. For directed graphs they differ by edge direction. Example 2.3 (Decoding VvNV). We trace S2G(VvNV,=)S2G( VvNV,\;directed=false): (1) Init: G=(0,∅)G=(\0\,\, ); CDLL =[0]=[0]; π1=π2=ℓ0 _1= _2= _0 (payload 0). (2) V: add node 11; add edge (0,1)(0,1); CDLL =[0,1]=[0,1]; π1 _1 still on ℓ0 _0. (3) v: add node 22; add edge (0,2)(0,2); CDLL =[0,1,2]=[0,1,2] (inserted after π2=ℓ0 _2= _0, so after 0 but before 11 in circular order — actually [0,2,1][0,2,1]); π2 _2 still on ℓ0 _0. (4) N: π1←next(ℓ0) _1 ( _0) (node 22 in current circular order [0,2,1][0,2,1]). (5) V: add node 33; add edge (2,3)(2,3); CDLL =[0,2,3,1]=[0,2,3,1]. 2.2 Graph-to-String Conversion The G2SG2S algorithm is the inverse of S2GS2G: given a graph G and a starting node v0∈V(G)v_0∈ V(G), it produces an IsalGraph string w such that S2G(w)≅GS2G(w) G. The algorithm is a greedy search that at each step finds the cheapest pointer displacement (in terms of number of pointer-move instructions emitted) that enables a useful structural operation. 2.2.1 Pair Generation and Cost Ordering The search space at each step is the set of integer displacement pairs (a,b)∈−M,…,M2(a,b)∈\-M,…,M\^2, where M is the current node count and a, b are the number of steps to move the primary and secondary pointers respectively (positive = forward, negative = backward). The cost of a pair is its total pointer-movement count |a|+|b||a|+|b|, which equals the number of N/P/n/p instructions that will be emitted. Definition 2.4 (Sorted displacement pairs). For a positive integer M, let (M)=(a,b)|a,b∈[−M,M]P(M)\;=\; \(a,b)\; |\;a,b∈[-M,M] \ sorted in increasing order of (|a|+|b|,|a|,a,b)(|a|+|b|,\;|a|,\;a,\;b) lexicographically. The primary sort key |a|+|b||a|+|b| minimises total pointer movement; secondary keys break ties deterministically. 2.2.2 Algorithm Description The algorithm (Algorithm 2) maintains an output graph GoutG_out and two node-index mappings: ι (input-to-output) and ι−1 ^-1 (output-to-input). These mappings are necessary because GoutG_out is built incrementally with its own node numbering, which may differ from the input graph’s numbering. At each iteration, the algorithm enumerates pairs (a,b)∈(M)(a,b) (M) in order and attempts four operations in priority order: V (node via primary) The tentative primary position π~1 π_1 corresponds to a node in the input graph that has an unmapped neighbour. A new node is inserted. v (node via secondary) Same, but using the tentative secondary position π~2 π_2. C (edge, primary → secondary) The tentative positions correspond to two nodes in the input graph that are adjacent but whose corresponding output-graph nodes are not yet connected. c (edge, secondary → primary) Same as C but reversed; meaningful only for directed graphs. The first pair (a,b)(a,b) for which any of these operations is applicable is committed: the pointer-move instructions are emitted (|a||a| copies of N or P; |b||b| copies of n or p), the structural instruction (V, v, C, or c) is appended, the actual pointers are updated, and the loop continues. The algorithm terminates when all nodes and all edges of G have been inserted. Algorithm 2 G2S(G,v0)G2S(G,\,v_0): GraphToString (greedy) 1:Connected graph G=(V,E)G=(V,E); starting node v0∈Vv_0∈ V 2:String w∈Σ∗w∈ ^* with S2G(w)≅GS2G(w) G 3:⊳ Initialise state 4:Verify all nodes are reachable from v0v_0 5:Gout←G_out← empty graph; u0←Gout.add_node()u_0← G_out.add\_node() 6:ℒ←L← new CDLL; ℓ0←ℒ.insert_after(∅,u0) _0 .insert\_after( ,\;u_0) 7:π1←ℓ0 _1← _0; π2←ℓ0 _2← _0 8:ι←v0↦u0 ←\v_0 u_0\; ι−1←u0↦v0 ^-1←\u_0 v_0\ 9:nleft←|V|−1n_left←|V|-1; eleft←|E|e_left←|E|; w←εw← 10:⊳ Main loop: continue until all nodes and edges are inserted 11:while nleft>0n_left>0 or eleft>0e_left>0 do 12: M←|V(Gout)|M←|V(G_out)| 13: for (a,b)(a,b) in (M)P(M) do 14: ℓ~1←walk(ℒ,π1,a) _1 (L,\, _1,\,a); v~1←ι−1[valℒ(ℓ~1)] v_1← ^-1[val_L( _1)] 15: ℓ~2←walk(ℒ,π2,b) _2 (L,\, _2,\,b); v~2←ι−1[valℒ(ℓ~2)] v_2← ^-1[val_L( _2)] 16: if nleft>0n_left>0 and ∃c∈NG(v~1)∃\,c∈ N_G( v_1) with c∉dom(ι)c ( ) then ⊳ V: node via primary 17: u←Gout.add_node()u← G_out.add\_node(); ι[c]←u [c]← u; ι−1[u]←c ^-1[u]← c 18: Gout.add_edge(valℒ(ℓ~1),u)G_out.add\_edge(val_L( _1),\;u); ℒ.insert_after(ℓ~1,u)L.insert\_after( _1,\;u) 19: w+=moves(a,primary)+Vw +=moves(a,primary)+ V; π1←ℓ~1 _1← _1 20: nleft-=1n_left -=1; eleft-=1e_left -=1; break 21: else if nleft>0n_left>0 and ∃c∈NG(v~2)∃\,c∈ N_G( v_2) with c∉dom(ι)c ( ) then ⊳ v: node via secondary 22: u←Gout.add_node()u← G_out.add\_node(); ι[c]←u [c]← u; ι−1[u]←c ^-1[u]← c 23: Gout.add_edge(valℒ(ℓ~2),u)G_out.add\_edge(val_L( _2),\;u); ℒ.insert_after(ℓ~2,u)L.insert\_after( _2,\;u) 24: w+=moves(b,secondary)+vw +=moves(b,secondary)+ v; π2←ℓ~2 _2← _2 25: nleft-=1n_left -=1; eleft-=1e_left -=1; break 26: else if (v~2,v~1)∈E( v_2, v_1)∈ E and (valℒ(ℓ~2),valℒ(ℓ~1))∉E(Gout)(val_L( _2),val_L( _1))∉ E(G_out) then ⊳ C 27: Gout.add_edge(valℒ(ℓ~1),valℒ(ℓ~2))G_out.add\_edge(val_L( _1),\;val_L( _2)) 28: w+=moves(a,pri)+moves(b,sec)+Cw +=moves(a,pri)+moves(b,sec)+ C 29: π1←ℓ~1 _1← _1; π2←ℓ~2 _2← _2; eleft-=1e_left -=1; break 30: else if G directed and (v~1,v~2)∈E( v_1, v_2)∈ E and (valℒ(ℓ~1),valℒ(ℓ~2))∉E(Gout)(val_L( _1),val_L( _2))∉ E(G_out) then ⊳ c 31: Gout.add_edge(valℒ(ℓ~2),valℒ(ℓ~1))G_out.add\_edge(val_L( _2),\;val_L( _1)) 32: w+=moves(a,pri)+moves(b,sec)+cw +=moves(a,pri)+moves(b,sec)+ c 33: π1←ℓ~1 _1← _1; π2←ℓ~2 _2← _2; eleft-=1e_left -=1; break 34: end if 35: end for 36:end while 37:return w Here walk(ℒ,ℓ,a)walk(L, ,a) returns the CDLL node reached by taking |a||a| steps forward (if a>0a>0) or backward (if a<0a<0) from ℓ . The helper moves(a,primary)moves(a,primary) emits a copies of N (if a≥0a≥ 0) or |a||a| copies of P (if a<0a<0), and analogously for the secondary pointer with n/pn/p. Remark 2.5 (Reachability precondition). For directed graphs, the V and v instructions always create edges of the form (existing_node→new_node)(existing\_node \_node). Consequently, G2SG2S can only encode nodes that are reachable from v0v_0 via directed outgoing edges. The algorithm raises an error if any node is unreachable from the chosen starting node. Remark 2.6 (String length decomposition). For a graph G with N nodes and M edges, the length of any IsalGraph string encoding G satisfies: |w|=(N−1)⏟one V/v per non-root node+M−(N−1)⏟one C/c/V/v per extra edge+∑k(|ak|+|bk|)⏟pointer moves.|w|\;=\; (N-1)_one V/v per non-root node\;+\; M-(N-1)_one C/c/V/v per extra edge\;+\; _k(|a_k|+|b_k|)_pointer moves. The first two terms are fixed by G; only the total pointer-movement cost depends on the traversal order. Minimising |w||w| therefore reduces to minimising total pointer travel. 2.3 Conjectured Properties The greedy G2SG2S algorithm is not label-blind in its base form: its neighbour iteration order (over sets) depends on the order that the nodes are extracted from the set, so two isomorphic graphs with different node numberings may yield different strings from the greedy algorithm. To recover a labelling-independent encoding, we define the canonical string via exhaustive backtracking. Definition 2.7 (Canonical string). Let (G)W(G) denote the set of all IsalGraph strings producible by the exhaustive-backtracking variant of G2SG2S (which explores all valid neighbour choices at every V/vV/v branch point) over all starting nodes v∈V(G)v∈ V(G). The canonical string of G is wG∗=lexminw∈(G)||w|=minw′∈(G)|w′|.w^*_G\;=\;lexmin \\,w (G)\; |\;|w|= _w (G)|w | \. That is, among all shortest strings in (G)W(G), select the lexicographically smallest under the total order C<N<P<V<W<c<n<p<vC<N<P<V<W<c<n<p<v on Σ . This construction motivates the following conjecture, which we state here as our primary theoretical claim and support empirically in Section 3. Conjecture 2.8 (Canonical string as complete graph invariant). Let G and H be finite, simple graphs. Then G≅H⇔wG∗=wH∗.G H\; \;w^*_G=w^*_H. The forward direction (G≅H⇒wG∗=wH∗G H w^*_G=w^*_H) would follow from the label-blindness of the exhaustive canonical search: an isomorphism ϕ:V(G)→V(H)φ:V(G)→ V(H) bijects the set of valid traversals of G from v onto the valid traversals of H from ϕ(v)φ(v), so the two graphs generate identical sets of strings and hence the same canonical minimum. The backward direction (wG∗=wH∗⇒G≅Hw^*_G=w^*_H G H) would follow from round-trip correctness: if both G and H produce the same canonical string w, then G≅S2G(w)≅HG 2G(w) H by transitivity. A complete proof requires establishing, rigorously, that the exhaustive-backtracking algorithm is indeed label-blind, i.e. that its output depends only on the abstract adjacency structure of the input and not on the integer identifiers assigned to nodes. We leave this verification as future work and instead provide empirical support: 100% invariance and discrimination rates on 71 isomorphic and non-isomorphic graph pairs across nine graph families (see Section 3). Remark 2.9 (Relation to graph isomorphism). If Conjecture 2.8 holds, then computing wG∗w^*_G is at least as hard as graph isomorphism, since wG∗=wH∗w^*_G=w^*_H if and only if G≅HG H. Graph isomorphism is known to lie in NP and is not known to be NP-complete; it has quasi-polynomial-time algorithms. The exhaustive canonical search used to compute wG∗w^*_G has complexity that grows super-polynomially with |V(G)||V(G)| in the worst case. 2.4 Topological Structure A key property of a useful graph representation is metric locality: small structural changes to a graph should produce small changes in its representation. Conversely, structurally dissimilar graphs should have representations that are far apart. We formalise this via a comparison between the Levenshtein distance on IsalGraph strings and the standard Graph Edit Distance (GED). 2.4.1 The String Distance Definition 2.10 (Levenshtein distance on IsalGraph strings). For two IsalGraph strings w1,w2∈Σ∗w_1,w_2∈ ^*, their Levenshtein distance is dLev(w1,w2)=mink|w1→k editsw2,d_Lev(w_1,w_2)\;=\; \k\; |\;w_1 $k$ editsw_2 \, where a single edit is a character insertion, deletion, or substitution. This is computed in O(|w1|⋅|w2|)O(|w_1|·|w_2|) time via standard dynamic programming. Applied to canonical strings, we define the IsalGraph graph distance: dIsalGraph(G,H)=dLev(wG∗,wH∗).d_ IsalGraph(G,H)\;=\;d_Lev(w^*_G,\,w^*_H). 2.4.2 Graph Edit Distance Definition 2.11 (Graph Edit Distance (Sanfeliu and Fu, 2012)). The Graph Edit Distance GED(G,H)GED(G,H) is the minimum number of elementary edit operations (node insertion, node deletion, edge insertion, edge deletion) needed to transform G into a graph isomorphic to H, under uniform unit costs. GED is a complete metric on the space of finite graphs up to isomorphism (i.e. GED(G,H)=0⇔G≅HGED(G,H)=0 G H), but it is NP-hard to compute even for simple unit-cost functions. 2.4.3 The Locality Property We state the locality relationship between dIsalGraphd_ IsalGraph and GED as a claim. Let G and H be finite, simple, connected graphs. Denote by k=GED(G,H)k=GED(G,H) their graph edit distance. Then, empirically: (i) Monotonicity. dIsalGraph(G,H)d_ IsalGraph(G,H) is a non-decreasing function of k: adding more edit operations to G produces a canonical string further from wG∗w^*_G. (i) Strong correlation. Over a broad sample of graph families, the Pearson correlation and the Spearman rank correlation between dIsalGraphd_ IsalGraph and GED are high. (i) Sensitivity. The mapping k↦dIsalGraphk d_ IsalGraph is monotonically increasing on average. The locality property distinguishes IsalGraph from many other graph representations. For comparison, the Hamming distance between (permuted) adjacency matrices does not satisfy locality because a single node insertion changes O(N)O(N) entries in the matrix. The IsalGraph encoding instead reflects the instruction-level cost of re-encoding the modified graph, which is naturally bounded by the number of changed edges plus the additional pointer moves required to reach the new positions. For the N×N× N binary adjacency matrix, a single edge insertion changes exactly one entry (two for undirected graphs), giving a Hamming distance of 11 or 22 per edge edit—asymptotically smaller than the IsalGraph bound. However, the adjacency matrix does not admit a meaningful string metric without first fixing a canonical node ordering, which reintroduces the isomorphism problem. The IsalGraph distance dIsalGraphd_ IsalGraph is isomorphism-invariant by construction, whereas the Hamming distance on adjacency matrices is not. 2.4.4 Implications for Graph Similarity Search The locality property has practical consequences. First, it suggests that dIsalGraphd_ IsalGraph can serve as a computationally efficient proxy for GED in similarity search: computing dLevd_Lev takes O(|w1|⋅|w2|)O(|w_1|·|w_2|) time, whereas exact GED requires exponential time. Second, the correlation is strong enough that rankings produced by dIsalGraphd_ IsalGraph closely mirror GED rankings, which is the property required for k-nearest-neighbour retrieval. Third, because every IsalGraph string decodes to a valid graph, interpolation in the string space (e.g. via random or guided edit paths) produces valid intermediate graphs, enabling gradient-free graph optimisation via string-space random walks. 3 Computational experiments This section describes the datasets, evaluation protocol, and computational infrastructure underlying the experiments. Three objectives guide the experimental design: (i) quantifying the agreement between Levenshtein distance on IsalGraph strings and graph edit distance across real-world graph benchmarks; (i) characterising the empirical time complexity of the encoding algorithms on synthetic random graphs; and (i) measuring the trade-off between encoding quality and computational cost across three encoding strategies of increasing expense. 3.1 Benchmark Datasets The experiments require two kinds of benchmark data: real-world graph collections with exact GED ground truth, for evaluating how faithfully the Levenshtein distance approximates structural dissimilarity; and synthetic random graphs of controlled size, for measuring how encoding time scales with the number of nodes. 3.1.1 Real-World Graph Collections Five datasets from three application domains are used for the correlation analysis and the speedup measurement. In all cases, node and edge attributes are discarded; the IsalGraph encoding operates solely on graph topology. Only connected graphs are retained, since the G2SG2S algorithm (Algorithm 2) requires a connected input. IAM Letter (LOW, MED, HIGH). The IAM Letter dataset (Riesen and Bunke, 2008) contains prototype graphs of 15 capital letters of the Roman alphabet that consist exclusively of straight lines. Nodes represent characteristic points of the letter strokes (endpoints, corners, intersections), and edges connect consecutive points along a stroke. Three subsets correspond to increasing levels of positional noise applied to node coordinates: Low, Med, and High. After connectivity filtering, the subsets contain 1,180, 1,253, and 2,059 graphs, with mean edge counts of 3.07, 3.17, and 4.56, respectively. For these three subsets, exact GED is computed via the A∗ algorithm of NetworkX (Hagberg et al., 2008) with uniform unit costs: node insertion and deletion cost 1, edge insertion and deletion cost 1, and node substitution cost 0 (all nodes are structurally identical after stripping coordinates). LINUX. The LINUX dataset contains program flow graphs extracted from subroutines of the Linux kernel, originally collected by Bai et al. (2019) and redistributed with isomorphism deduplication by Jain et al. (2024). After filtering for connectivity and restricting to graphs with at most 12 nodes, 89 graphs remain (mean edge count: 8.35). Precomputed exact GED matrices from the GraphEdX repository are used directly; these were obtained via A∗ search with topology-only costs (zero cost for all node operations; unit cost for edge insertion and deletion). AIDS. The AIDS dataset contains molecular graphs from the Developmental Therapeutics Program of the U.S. National Cancer Institute, where nodes represent atoms and edges represent covalent bonds. The topology-only variant distributed by Jain et al. (2024) is used, in which all node labels (atom types) have been stripped and GED is computed with the same topology-only cost function as LINUX. After filtering, 769 connected graphs remain (mean edge count: 10.70). The five datasets cover structural densities ranging from sparse (mean edges 3.07) to moderately dense (10.70), and sample sizes from 89 to 2,059 graphs. Table 2 summarises the number of graphs, the number of valid pairwise comparisons, and the mean edge count for each dataset. 3.1.2 Synthetic Graph Families The complexity characterisation requires graphs of controlled size, independent of any particular application domain. Random connected graphs are generated from two standard families: • Barabási–Albert (BA) preferential-attachment graphs (Barabási and Albert, 1999) with attachment parameters m∈1,2m∈\1,2\. • Erdős–Rényi (ER) random graphs (Erdős and Rényi, 1959) with edge probabilities p∈0.3,0.5p∈\0.3,0.5\. When an ER graph is disconnected, only its largest connected component is retained. For each family, graphs are generated at node counts n∈3,4,…,50n∈\3,4,…,50\ for the greedy methods and n∈3,4,…,20n∈\3,4,…,20\ for the canonical method, with a per-instance timeout of 600 seconds. Five independent instances are generated per (n,family)(n,family) combination. These synthetic graphs are used exclusively for the time-complexity analysis reported in Figure 2; they do not participate in the correlation experiments. 3.2 Evaluation Protocol The evaluation is organised into four components: a comparison of three encoding methods (Section 3.2.1), a correlation analysis between Levenshtein and GED distances on the real-world datasets (Section 3.2.3), a complexity and speedup measurement on the synthetic and real-world datasets, respectively (Section 3.2.4), and a qualitative neighbourhood analysis on a small illustrative graph (Section 3.2.5). 3.2.1 Encoding Methods Under Comparison Three variants of the G2SG2S encoding (Section 2.2) are evaluated, ordered by decreasing computational cost: Canonical. The exhaustive-backtracking procedure of Definition 2.7, returning the lexicographically minimal shortest string wG∗w^*_G. Greedy-min. The greedy G2SG2S algorithm executed from every starting node v0∈V(G)v_0∈ V(G); the shortest string across all runs is selected. Greedy-rnd(v0v_0). A single greedy G2SG2S run from a uniformly random starting node. 3.2.2 Distance Computation Exact graph edit distance (GED; Definition 2.11) serves as the ground-truth structural dissimilarity measure. The GED computation procedure for each dataset is described in Section 3.1. For each encoding method, all-pairs Levenshtein distance matrices (Definition 2.10) are computed from the resulting IsalGraph strings. 3.2.3 Correlation Analysis The agreement between the Levenshtein and GED distance matrices is quantified over all valid upper-triangular pairs (i,j)(i,j) with i<ji<j, GED(Gi,Gj)>0GED(G_i,G_j)>0, and dLev(wi,wj)>0d_Lev(w_i,w_j)>0. Two statistics are reported per dataset and encoding method: • Spearman’s rank correlation coefficient ρ, measuring monotonic association between the two distance measures. • The ordinary least-squares (OLS) regression slope β of Levenshtein distance on GED, where β=1β=1 indicates equal scaling and β<1β<1 indicates that Levenshtein distances grow more slowly than GED. The p-values reported in Table 2 are obtained from SciPy’s implementation of the Spearman test, which uses the asymptotic t-distribution approximation t=ρ(n−2)/(1−ρ2)t=ρ (n-2)/(1-ρ^2) with n−2n-2 degrees of freedom, where n is the number of valid pairs. Given that all five datasets yield n>1,600n>1,600 pairs, the asymptotic approximation is well justified. Statistical significance is assessed at α=0.001α=0.001. 3.2.4 Complexity and Speedup Measurement Encoding time is measured on the synthetic graph families described in Section 3.1. Each encoding is repeated 25 times per graph instance, and the median CPU time is retained to reduce the effect of system scheduling variance. The aggregate time at each node count n is the median across instances and families, with the interquartile range as a dispersion measure. Scaling exponents α are estimated by fitting T(n)=c⋅nαT(n)=c· n^α via OLS on log-transformed data (logT T vs. logn n), and goodness of fit is reported as R2R^2. The computational speedup of the IsalGraph pipeline (encoding plus pairwise Levenshtein distance) over exact GED is measured on the five real-world datasets. Speedup ratios are computed per graph pair and aggregated as the geometric mean, stratified by graph size (n=3n=3 to 1111 nodes). 3.2.5 Neighbourhood Topology As a qualitative illustration of the locality property (Section 2.4), the neighbourhood structure of a representative small graph is examined under both GED and Levenshtein distance. The base graph is the house graph on 5 nodes and 6 edges. All graphs at GED=1GED=1 from the base graph (single edge edits) are enumerated, and their Levenshtein distances to the base encoding are computed. Conversely, all strings at Levenshtein distance 11 from the base encoding are generated (single character substitutions, insertions, and deletions), decoded via S2GS2G, and their GED to the base graph is computed. 3.3 Implementation The IsalGraph core is implemented in Python with no external dependencies. Adapters for NetworkX (Hagberg et al., 2008), igraph (Csárdi and Nepusz, 2006), and PyTorch Geometric (Fey and Lenssen, 2019) provide interoperability with standard graph libraries. Timing measurements use time.process_time() to record CPU time exclusive of I/O and system scheduling. All experiments were executed on the Picasso supercomputer at the Supercomputing and Bioinformatics Centre (SCBI) of the University of Málaga. A fixed random seed of 4242 is used throughout for reproducibility. 4 Results We evaluate IsalGraph along three axes: agreement between Levenshtein distance and GED (Section 4.1), and empirical time complexity of the encoding algorithms (Section 4.2). A qualitative neighbourhood analysis completes the evaluation (Section 4.3). 4.1 Correlation with Graph Edit Distance Table 2 reports the Spearman rank correlation coefficient ρ between GED and Levenshtein distance for each dataset and encoding method. All fifteen ρ values are statistically significant at α=0.001α=0.001. On the three IAM Letter subsets, which contain sparse graphs (m¯≤4.56 m≤ 4.56), the canonical encoding attains strong monotonic agreement with GED: ρ=0.934ρ=0.934 on Low, 0.8760.876 on Med, and 0.6820.682 on High. Greedy-min trails canonical by modest margins (Δρ=0.027 ρ=0.027, 0.0140.014, and 0.0570.057, respectively), while Greedy-rnd(v0v_0) incurs larger losses, reaching Δρ=0.228 ρ=0.228 below canonical on Low. On the denser LINUX and AIDS datasets (m¯=8.35 m=8.35 and 10.7010.70), correlation drops markedly. The best method on LINUX is Greedy-min (ρ=0.445ρ=0.445), the only dataset where it surpasses canonical (ρ=0.433ρ=0.433), by a margin of 0.0120.012. On AIDS, canonical leads with ρ=0.349ρ=0.349. The small difference on LINUX may reflect the limited number of valid pairs (n=1,685n=1,685) relative to the other datasets (n≥131,148n≥ 131,148), which amplifies the effect of individual outlier pairs on the rank correlation statistic. Figure 1: Aggregated correlation between graph edit distance (GED) and Levenshtein distance across all five benchmark datasets. Each cell at integer coordinates (i,j)(i,j) shows the count of graph pairs with GED=iGED=i and Lev=jLev=j (log scale; light = few pairs, dark = many pairs); white cells contain no observed pairs. Dashed grey line: identity (Lev=GEDLev=GED). Solid red line: ordinary least-squares (OLS) regression. (a) Canonical encoding (n=3,424,764n=3,424,764 pairs, ρ=0.700ρ=0.700, β=0.79β=0.79). (b) Greedy-min encoding (n=3,424,764n=3,424,764 pairs, ρ=0.665ρ=0.665, β=0.78β=0.78). (c) Greedy-rnd(v0v_0) encoding (n=3,424,764n=3,424,764 pairs, ρ=0.590ρ=0.590, β=0.82β=0.82). Reported statistics: ρ denotes Spearman’s rank correlation coefficient, measuring monotonic association between the two distance measures. β denotes the OLS regression slope; β=1β=1 would indicate that Levenshtein and GED operate on the same scale, while β<1β<1 indicates that Levenshtein distances grow more slowly than GED. Table 2: Dataset properties and Spearman ρ correlation between GED and IsalGraph Levenshtein distance across encoding methods. m¯ m: mean edges per graph (complexity proxy). Spearman-ρ difference between best method per dataset is showcased. Best ρ per dataset in bold. 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 m¯ m 3.07 3.17 4.56 8.35 10.70 Spear. ρ 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(v0v_0) 0.706∗ (-0.228) 0.682∗ (-0.195) 0.577∗ (-0.105) 0.301∗ (-0.144) 0.251∗ (-0.098) p∗∗<0.001^***p<0.001, p∗<0.01^**p<0.01, p∗<0.05^*p<0.05. m¯ m increases monotonically as ρ degrades across datasets. Figure 1 displays the aggregated joint distribution of GED and Levenshtein distance over all 3,424,7643,424,764 valid pairs from the five datasets. The concentration of mass near the identity line confirms that the two measures are broadly co-monotonic, though the spread increases at higher GED values. The OLS regression slopes β=0.79β=0.79 (Canonical), 0.780.78 (Greedy-min), and 0.820.82 (Greedy-rnd) lie consistently below unity, indicating that Levenshtein distances grow more slowly than GED. This compression stems from the bounded instruction alphabet (|Σ|=9| |=9): structurally distant graphs can still share long common subsequences in their encoding strings, attenuating the measured string dissimilarity. A monotonic relationship between graph density and correlation strength is apparent across all five datasets. As the mean edge count m¯ m increases from 3.073.07 (IAM Low) to 10.7010.70 (AIDS), ρ decreases for every encoding method (Table 2). The steepest drop occurs between IAM High (m¯=4.56 m=4.56, canonical ρ=0.682ρ=0.682) and LINUX (m¯=8.35 m=8.35, canonical ρ=0.433ρ=0.433), where a near-doubling of mean edge count coincides with a 37% relative decline in ρ. This degradation is consistent with the sequential nature of the G2SG2S traversal: as edge density grows, a single depth-first pass captures a diminishing fraction of the graph’s pairwise connectivity, and the resulting string becomes a coarser proxy for the full topology. 4.2 Empirical Time Complexity Figure 2 shows the median encoding time as a function of graph size n for the three methods on synthetic random graphs (Barabási–Albert and Erdős–Rényi families). Power-law fits T(n)=c⋅nαT(n)=c· n^α on log-transformed data yield exponents α=3.1α=3.1 for Greedy-rnd(v0v_0), α=4.5α=4.5 for Greedy-min, and α=9.0α=9.0 for Canonical, all with R2≥0.979R^2≥ 0.979. Figure 2: Empirical time complexity of IsalGraph encoding methods on random graphs (Barabási–Albert m∈1,2m∈\1,2\ and Erdős–Rényi p∈0.3,0.5p∈\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⋅nαT=c· n^α via OLS on log–log data. Greedy-rnd(v0v_0): α=3.1α=3.1, R2=0.989R^2=0.989. Greedy-Min: α=4.5α=4.5, R2=0.989R^2=0.989. Canonical: α=9.0α=9.0, R2=0.979R^2=0.979. Greedy methods exhibit polynomial scaling (α≈3α≈ 3–55), while the canonical method scales super-polynomially (α≈9α≈ 9) on random graphs and becomes infeasible beyond n≈12n≈ 12. The Greedy-rnd exponent α≈3α≈ 3 is consistent with the cost of a single G2SG2S traversal, whose dominant operation is the neighbour-selection step repeated at each of the O(n)O(n) visited nodes. Greedy-min iterates the greedy procedure over all n starting nodes, raising the empirical exponent to α≈4.5α≈ 4.5; the half-unit above n4n^4 reflects the variable string length across starting nodes and the associated comparison cost. Both greedy variants scale to graphs with 50 nodes within the 600-second timeout. The canonical method exhibits α=9.0α=9.0, a direct consequence of its exhaustive backtracking over all starting nodes and all valid neighbour orderings. At n=12n=12, the canonical encoding already approaches the timeout threshold; beyond this size, it is impractical without further algorithmic refinement. The high R2R^2 values confirm that the power-law model captures the observed scaling within the tested range, although the canonical method’s true asymptotic complexity is super-polynomial due to the combinatorial explosion of traversal orderings. 4.3 Neighbourhood Structure Figure 3 illustrates the relationship between graph-space and string-space proximity on a concrete example, complementing the aggregate correlation analysis above. The base graph G0G_0 is the house graph (5 nodes, 6 edges), and its canonical IsalGraph encoding serves as the reference string. The 1-GED neighbourhood of G0G_0 comprises 10 non-isomorphic graphs obtained by a single edge insertion or deletion that preserves connectivity (6 deletions and 4 insertions). Their Levenshtein distances to the encoding of G0G_0 range from 1 to 5: a single structural edit can require up to five character changes in the instruction string. This spread arises because the canonical encoding selects the globally optimal traversal order; modifying one edge may shift this optimum entirely, producing a substantially different string even though the underlying graph changed minimally. Figure 3: Neighbourhood topology of the house graph G0G_0 (5 nodes, 6 edges) under two distance metrics. Centre column: base graph G0G_0 with its canonical IsalGraph encoding (colour-coded by instruction type). Top rows: 4 representative 1-GED neighbours (single edge edit), with Levenshtein distances Lev∈[1, 5]Lev∈[1,\,5] to the encoding of G0G_0. Bottom rows: 4 representative 1-Levenshtein neighbours (single character substitution, insertion, or deletion in the instruction string), with GED values GED∈[1, 2]GED∈[1,\,2]. Dashed red edges indicate structural differences from G0G_0. Horizontal heatmaps below each graph render the IsalGraph instruction string with per-character colouring (alphabet Σ=N,n,P,p,V,v,C,c,W =\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. In the reverse direction, the 1-Levenshtein neighbourhood—strings differing from the base encoding by a single substitution, insertion, or deletion—yields graphs with GED∈1,2GED∈\1,2\ to G0G_0. String-space proximity thus implies graph-space proximity: small perturbations to the instruction string produce small structural changes. This directional tightness follows from the instruction semantics, where each character corresponds to at most one structural operation (node creation, edge insertion, or pointer movement), bounding the topological effect of any single character change. The asymmetry between the two neighbourhoods—tight from string-space to graph-space, loose from graph-space to string-space—is inherent to any encoding in which multiple traversal orders can represent the same graph. It has a practical implication: Levenshtein distance on IsalGraph strings is more likely to overestimate GED (when a small structural change requires a large string rearrangement) than to underestimate it (since each character change has bounded structural impact). This conservative bias favours recall over precision: Levenshtein-based retrieval is more likely to return a slightly dissimilar graph than to miss a genuinely similar one, a property that is advantageous in retrieval settings where recall is prioritised. 5 Conclusion Summary of contributions. This paper has introduced IsalGraph, a sequential instruction-based representation of finite simple graphs. The encoding is defined by a nine-instruction virtual machine that manipulates a circular doubly-linked list (CDLL) of graph-node references via two traversal pointers, inserting nodes and edges into a sparse graph as instructions are executed. The resulting representation has four properties that distinguish it from existing graph encodings: (i) Universal validity. Every string over the alphabet Σ=N,n,P,p,V,v,C,c,W =\N,n,P,p,V,v,C,c,W\ decodes to a valid finite simple graph. There are no syntactically or semantically invalid strings, which eliminates the need for validity-checking decoders and simplifies the design of generative models. (i) Reversibility. The greedy GraphToString (G2SG2S) algorithm encodes any connected graph G into a string w such that S2G(w)≅GS2G(w) G. Round-trip correctness was confirmed at a 100% pass rate over 945 test instances spanning twelve graph families, with independent cross-validation via the VF2 isomorphism algorithm. (i) Canonical completeness (conjectured). The canonical string wG∗w^*_G, computed by exhaustive backtracking over all starting nodes and all valid neighbour orderings, is conjectured to be a complete graph invariant: G≅H⇔wG∗=wH∗G H w^*_G=w^*_H. This conjecture is supported by 100% invariance and discrimination accuracy on 71 graph pairs across nine structural families including trees, cycles, complete graphs, stars, wheels, Barabási–Albert graphs, and the Petersen graph. (iv) Metric locality. The Levenshtein distance between IsalGraph strings correlates strongly with graph edit distance on real-world graph benchmarks, reaching Spearman ρ=0.934ρ=0.934 on the sparse IAM Letter (LOW) dataset (n=695,610n=695,610 pairs, p<0.001p<0.001) and remaining significant across all five datasets tested, covering a range of structural densities from m¯=3.07 m=3.07 to m¯=10.70 m=10.70 mean edges per graph. Limitations. Three limitations warrant explicit acknowledgement. First, the canonical completeness conjecture remains unproven. A formal proof would require establishing rigorously that the exhaustive-backtracking algorithm is label-blind, i.e. that its output depends solely on abstract adjacency structure and not on the integer identifiers assigned to nodes. Second, the canonical encoding scales super-polynomially (T∼n9.0T n^9.0) and is computationally infeasible for graphs with more than approximately 12 nodes on current hardware within a 600-second timeout. Third, the G2SG2S algorithm requires the input graph to be connected; for directed graphs, it additionally requires all nodes to be reachable from the chosen starting node via directed outgoing edges. Graphs that do not satisfy these conditions cannot be encoded without preprocessing. Acknowledgment The authors thankfully acknowledge the computer resources (Picasso Supercomputer), technical expertise, and assistance provided by the SCBI (Supercomputing and Bioinformatics) center of the University of Málaga. References Y. Bai, H. Ding, S. Bian, T. Chen, Y. Sun, and W. Wang (2019) SimGNN: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, p. 384–392. External Links: Document Cited by: §3.1.1. A. Barabási and R. Albert (1999) Emergence of scaling in random networks. Science 286 (5439), p. 509–512. External Links: Document Cited by: 1st item. G. Csárdi and T. Nepusz (2006) The igraph software package for complex network research. InterJournal Complex Systems 1695, p. 1–9. Cited by: §3.3. J. Devlin, M. Chang, K. Lee, and K. Toutanova (2019) BERT: pre-training of deep bidirectional transformers for language understanding. arXiv preprint. Note: arXiv:1810.04805 Cited by: §1. P. Erdős and A. Rényi (1959) On random graphs I. Publicationes Mathematicae Debrecen 6, p. 290–297. Cited by: 2nd item. M. Fey and J. E. Lenssen (2019) Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, Note: arXiv:1903.02428 Cited by: §3.3. A. A. Hagberg, D. A. Schult, and P. J. Swart (2008) Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (SciPy 2008), p. 11–15. Cited by: §3.1.1, §3.3. W. L. Hamilton, R. Ying, and J. Leskovec (2017) Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, Vol. 30, p. 1024–1034. Cited by: §1. E. Jain, I. Roy, S. Meher, S. Chakrabarti, and A. De (2024) Graph edit distance with general costs using neural set divergence. In Advances in Neural Information Processing Systems, Vol. 37. Note: arXiv:2409.17687 Cited by: §3.1.1, §3.1.1. W. Ju et al. (2024) A comprehensive survey on deep graph representation learning. Neural Networks 171, p. 1063–1095. External Links: Document Cited by: §1. S. Khoshraftar and A. An (2024) A survey on graph representation learning methods. ACM Transactions on Intelligent Systems and Technology 15 (2), p. 1–45. External Links: Document Cited by: §1. T. N. Kipf and M. Welling (2017) Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, Note: arXiv:1609.02907 Cited by: §1. E. López-Rubio (2025) Representation of the structure of graphs by sequences of instructions. arXiv preprint. Note: arXiv:2512.10429v2 Cited by: §1. K. Riesen and H. Bunke (2008) IAM graph database repository for graph based pattern recognition and machine learning. In Structural, Syntactic, and Statistical Pattern Recognition, Lecture Notes in Computer Science, Vol. 5342, p. 287–297. External Links: Document Cited by: §3.1.1. A. Sanfeliu and K. Fu (2012) A distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics (3), p. 353–362. Cited by: Definition 2.11. A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin (2017) Attention is all you need. In Advances in Neural Information Processing Systems, Vol. 30. Cited by: §1. P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio (2018) Graph attention networks. In International Conference on Learning Representations, Note: arXiv:1710.10903 Cited by: §1. J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun (2020) Graph neural networks: A review of methods and applications. AI Open 1, p. 57–81. External Links: Document Cited by: §1.