Instruction Set and Language for Hypergraphs

# Instruction Set and Language for Hypergraphs
Source: [https://arxiv.org/html/2607.10194](https://arxiv.org/html/2607.10194)
[![[Uncaptioned image]](https://arxiv.org/html/2607.10194v1/x1.png)Mario Pascual\-González](https://orcid.org/0009-0001-2178-4647) Department of Computer Languages and Computer Science University of Málaga Bulevar Louis Pasteur, 35 29071 Málaga, Spain mpascual@uma\.es &[![[Uncaptioned image]](https://arxiv.org/html/2607.10194v1/x2.png)Ezequiel López\-Rubio](https://orcid.org/0000-0001-8231-5687) Department of Computer Languages and Computer Science University of Málaga Bulevar Louis Pasteur, 35 29071 Málaga, Spain ezeqlr@lcc\.uma\.es Corresponding author\. ITIS Software\. Universidad de Málaga\. C/ Arquitecto Francisco Peñalosa 18, 29010, Málaga, Spain

###### Abstract

We presentIsalHG, a method for representing the structure of any finite, connected hypergraph of bounded hyperedge arity as a string over a compact instruction alphabetΣHG\\Sigma\_\{\\mathrm\{HG\}\}\. The encoding is executed by a small virtual machine comprising a sparse hypergraph, a circular doubly\-linked list \(CDLL\) of node references, andkktraversal pointers, wherekkbounds 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ΣHG\\Sigma\_\{\\mathrm\{HG\}\}decodes to a valid hypergraph; the alphabet is closed\. A greedy*HypergraphToString*\(H2S\\mathrm\{H2S\}\) algorithm encodes any connected hypergraph into a string; a backtracking variant seeded at nodes of lexicographically maximal structural tuple produces a*canonical string*wH∗w^\{\*\}\_\{H\}, 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 propertyS2H​\(H2S​\(H\)\)≅H\\mathrm\{S2H\}\(\\mathrm\{H2S\}\(H\)\)\\cong Hon 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\)\(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 ratio311×311\\timesto117,672×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\.

*Keywords*hypergraph representation⋅\\cdothypergraph isomorphism⋅\\cdotcanonical form⋅\\cdotinstruction sequences⋅\\cdotvirtual machine⋅\\cdotLevi graph

## 1Introduction

Hypergraphs generalise graphs by allowing an edge to connect any number of nodes rather than exactly two\. They are the natural model for group interactions: co\-authorship teams, chemical reactions, protein complexes, social contact events, and legislative coalitions are all sets of participants, not pairs\(Berge,[1973](https://arxiv.org/html/2607.10194#bib.bib48); Bensonet al\.,[2018](https://arxiv.org/html/2607.10194#bib.bib69); Battistonet al\.,[2020](https://arxiv.org/html/2607.10194#bib.bib49)\)\. As standard software for higher\-order network analysis has emerged\(Landryet al\.,[2023](https://arxiv.org/html/2607.10194#bib.bib67); Lotitoet al\.,[2023](https://arxiv.org/html/2607.10194#bib.bib68)\), the fundamental representation question resurfaces at the hypergraph level: how should the structure of a hypergraph be encoded so that structurally identical objects can be recognised as such? This is the hypergraph isomorphism problem, and it underlies the classification of combinatorial designs\(Kaski and Östergård,[2004](https://arxiv.org/html/2607.10194#bib.bib64); Colbourn and Dinitz,[2007](https://arxiv.org/html/2607.10194#bib.bib65)\), the deduplication of hypergraph corpora, and the assessment of structural expressivity in higher\-order machine learning\(Fenget al\.,[2024](https://arxiv.org/html/2607.10194#bib.bib61)\)\.

The established exact route to hypergraph isomorphism is a reduction\. The hypergraphHHis translated into its Levi incidence graphB​\(H\)B\(H\): a bipartite graph with one vertex per node ofHH, one vertex per hyperedge, and an edge whenever a node belongs to a hyperedge\(Berge,[1973](https://arxiv.org/html/2607.10194#bib.bib48)\)\. Colouring the two vertex classes makes the translation faithful, and a graph canonical\-labelling engine — nauty or Traces\(McKay,[1981](https://arxiv.org/html/2607.10194#bib.bib50); McKay and Piperno,[2014](https://arxiv.org/html/2607.10194#bib.bib51)\), or bliss\(Junttila and Kaski,[2007](https://arxiv.org/html/2607.10194#bib.bib52)\)— decides isomorphism on the reduced graph\. This pipeline is exact and mature; to our knowledge, it is the only exact hypergraph isomorphism procedure available as working software: design\-theory systems such as SageMath and GAP route their incidence\-structure isomorphism tests through nauty internally\. The pipeline is not*native*\. The reduction inflates the vertex set fromnnton\+mn\+m, wheremmis the number of hyperedges, and the algorithm discards the hypergraph before any isomorphism reasoning begins\. Native alternatives proposed so far are refinement\-based invariants in the Weisfeiler–Leman family, which are provably incomplete\(Fenget al\.,[2024](https://arxiv.org/html/2607.10194#bib.bib61); Zhanget al\.,[2025](https://arxiv.org/html/2607.10194#bib.bib62)\), and group\-theoretic exact algorithms, which remain theoretical\(Babai and Codenotti,[2008](https://arxiv.org/html/2607.10194#bib.bib55); Neuen,[2022](https://arxiv.org/html/2607.10194#bib.bib57); Schweitzer and Wiebking,[2019](https://arxiv.org/html/2607.10194#bib.bib58)\)\.

This paper introducesIsalHG\(Instruction Set and Language for Hypergraphs\), a native sequential representation of hypergraphs\. We encode a hypergraph as a string over the instruction alphabetΣHG\\Sigma\_\{\\mathrm\{HG\}\}and execute it with a small virtual machine comprising a sparse hypergraph, a circular doubly\-linked list of node references, andkktraversal pointers, wherekkbounds the hyperedge arity\. Every string overΣHG\\Sigma\_\{\\mathrm\{HG\}\}decodes to a valid hypergraph\. A greedy HypergraphToString algorithm \(H2S\\mathrm\{H2S\}\) encodes any connected hypergraph; a backtracking variant seeded at nodes of maximal structural tuple computes a canonical stringwH∗w^\{\*\}\_\{H\}, which we conjecture to be a complete isomorphism invariant\. Under this conjecture, canonical\-string equality decides hypergraph isomorphism within the hypergraph domain\.IsalHGis the third member of an instruction\-set representation family, afterIsalGraphfor finite simple graphs\(López\-Rubio,[2025](https://arxiv.org/html/2607.10194#bib.bib36); Lopez\-Rubio and Pascual\-Gonzalez,[2026b](https://arxiv.org/html/2607.10194#bib.bib71)\)andIsalSRfor the labelled directed acyclic graphs of symbolic regression\(Lopez\-Rubio and Pascual\-Gonzalez,[2026a](https://arxiv.org/html/2607.10194#bib.bib72)\)\.

We make three contributions\. First, we specify the alphabet, the virtual machine, and theS2H\\mathrm\{S2H\}/H2S\\mathrm\{H2S\}algorithm pair, and motivate the design decisions\. Second, we state the round\-trip and canonical\-completeness properties as explicit conjectures, argue both directions informally, and defer the formal proofs to a dedicated theoretical paper\. Third, we report the first direct benchmark of a native canonical\-string method against the Levi route on hypergraphs: on 150 connected random uniform hypergraphs spanningn∈\{8,…,25\}n\\in\\\{8,\\dots,25\\\}nodes, the round\-trip property holds in every instance, all four methods \(IsalHG, nauty, Traces, bliss\) agree on all 600 isomorphism verdicts, and the Levi baselines outperform the current canonical algorithm by three to five orders of magnitude in wall\-clock time\. We report the runtime gap as measured; we characterise where the native encoding stands relative to the reduction and make no claim of superiority over it\.

The paper is organised as follows\. Section[2](https://arxiv.org/html/2607.10194#S2)positionsIsalHGagainst exact, approximate, and sequential prior work\. Section[3](https://arxiv.org/html/2607.10194#S3)defines the alphabet, the virtual machine, both conversion algorithms, and the conjectured properties\. Section[4](https://arxiv.org/html/2607.10194#S4)describes the data cohort and the experimental protocol\. Section[5](https://arxiv.org/html/2607.10194#S5)reports the round\-trip, agreement, and runtime results, which Section[6](https://arxiv.org/html/2607.10194#S6)discusses\. Section[7](https://arxiv.org/html/2607.10194#S7)concludes\.

## 2Related work

Prior work relevant toIsalHGfalls into four strands: the practical exact graph canonical\-labelling tools that reach hypergraphs through the Levi reduction \(§[2\.1](https://arxiv.org/html/2607.10194#S2.SS1)\), exact hypergraph isomorphism algorithms that exist only in theory \(§[2\.2](https://arxiv.org/html/2607.10194#S2.SS2)\), Weisfeiler–Leman\-style hypergraph invariants that are native but incomplete \(§[2\.3](https://arxiv.org/html/2607.10194#S2.SS3)\), and sequential encodings of combinatorial structures \(§[2\.4](https://arxiv.org/html/2607.10194#S2.SS4)\)\. The first strand supplies our baselines; the second and third explain why no other baseline is available; the fourth contains the representation traditionIsalHGextends\.

### 2\.1Exact graph canonical labelling and the Levi reduction

Practical graph isomorphism is dominated by canonical\-labelling tools built on the individualisation–refinement \(IR\) paradigm: colour refinement partitions the vertices, individualisation branches on the cells the refinement cannot split, and a search tree over these branches yields a canonical labelling\. nauty introduced the modern form of this architecture\(McKay,[1981](https://arxiv.org/html/2607.10194#bib.bib50)\); its sibling Traces replaced the depth\-first traversal with a breadth\-first strategy and a different cell selector, which pays off on highly symmetric inputs; both are maintained and distributed together\(McKay and Piperno,[2014](https://arxiv.org/html/2607.10194#bib.bib51)\)\. bliss refined the same paradigm for large and sparse graphs\(Junttila and Kaski,[2007](https://arxiv.org/html/2607.10194#bib.bib52)\)\. These engines decide isomorphism for graphs with millions of vertices in practice; hard instances for all three are now well characterised\(Neuen and Schweitzer,[2017](https://arxiv.org/html/2607.10194#bib.bib53)\)\. On the theory side, graph isomorphism is decidable in quasipolynomial time\(Babai,[2016](https://arxiv.org/html/2607.10194#bib.bib17)\), but the IR engines, with exponential worst cases, remain the practical standard\.

Hypergraphs enter this ecosystem through a reduction\. The Levi graphB​\(H\)B\(H\)of a hypergraphHHwithnnnodes andmmhyperedges is the bipartite incidence graph onn\+mn\+mvertices in which each hyperedge vertex is adjacent to the vertices of the nodes it contains\(Berge,[1973](https://arxiv.org/html/2607.10194#bib.bib48)\)\. Colouring node\-vertices and hyperedge\-vertices with two distinct colours makes the reduction faithful: two hypergraphs are isomorphic exactly when their coloured Levi graphs are\. Every software system we are aware of that decides hypergraph or incidence\-structure isomorphism exactly follows this route\. SageMath’sIncidenceStructure\.is\_isomorphicand GAP’s design\-theory packages invoke nauty internally, and the classification campaigns of design theory — for example the enumeration of the 11,084,874,829 Steiner triple systems of order 19 — combine nauty\-based isomorph rejection with domain\-specific invariants\(Kaski and Östergård,[2004](https://arxiv.org/html/2607.10194#bib.bib64); Colbourn and Dinitz,[2007](https://arxiv.org/html/2607.10194#bib.bib65)\)\. For hypergraph isomorphism, therefore, the operational exact standard is the Levi reduction plus one of the three engines above, and any native proposal must measure itself against that pipeline\.

### 2\.2Exact hypergraph isomorphism in theory

Hypergraph isomorphism is polynomial\-time equivalent to graph isomorphism: the Levi reduction maps hypergraphs to coloured graphs, and graphs are hypergraphs of arity two\. The theoretical literature has nevertheless sought algorithms whose complexity respects hypergraph parameters instead of the inflated sizen\+mn\+mof the reduction\.Luks \([1999](https://arxiv.org/html/2607.10194#bib.bib54)\)gave an algorithm exponential in the number of nodes but polynomial in the number of hyperedges\.Babai and Codenotti \([2008](https://arxiv.org/html/2607.10194#bib.bib55)\)handle hypergraphs of bounded rankkkin moderately exponential timeexp⁡\(O~​\(k2​n\)\)\\exp\(\\tilde\{O\}\(k^\{2\}\\sqrt\{n\}\)\)\.Arvindet al\.\([2015](https://arxiv.org/html/2607.10194#bib.bib56)\)showed that colored hypergraph isomorphism is fixed\-parameter tractable in the maximum colour\-class size\.Neuen \([2022](https://arxiv.org/html/2607.10194#bib.bib57)\)obtained the currently best bound,\(n\+m\)O​\(\(log⁡d\)c\)\(n\+m\)^\{O\(\(\\log d\)^\{c\}\)\}for groups with restricted composition factors, while noting that the dependence onmmremains far from optimal for hyperedge\-rich inputs\.Schweitzer and Wiebking \([2019](https://arxiv.org/html/2607.10194#bib.bib58)\)proposed a unifying canonisation framework over hereditarily finite sets that canonises hypergraphs within the same asymptotic budget as the group\-theoretic algorithms\.

The relevant point here is practical, not asymptotic: none of these five algorithms has a public implementation\. They are exact and, in spirit, native, but they cannot be run\. The practical exact toolbox for hypergraph isomorphism thus contains precisely the Levi reduction driven by nauty, Traces, or bliss; Section[4](https://arxiv.org/html/2607.10194#S4)benchmarks against those three engines and no others\.

### 2\.3Weisfeiler–Leman invariants and hypergraph learning

A separate line of work computes isomorphism*invariants*by iterated colour refinement in the style of Weisfeiler and Leman\(Weisfeiler and Leman,[1968](https://arxiv.org/html/2607.10194#bib.bib16)\)\. Such invariants are one\-sided: different values certify non\-isomorphism, but equal values certify nothing, and for every fixed refinement dimensionkkthere exist non\-isomorphic graph pairs thekk\-dimensional test cannot separate\(Caiet al\.,[1992](https://arxiv.org/html/2607.10194#bib.bib59)\)\. On hypergraphs, colour refinement characterises exactly the homomorphism counts of Berge\-acyclic patterns\(Böker,[2019](https://arxiv.org/html/2607.10194#bib.bib60)\), which is strictly weaker than isomorphism\.Fenget al\.\([2024](https://arxiv.org/html/2607.10194#bib.bib61)\)introduced a hypergraph Weisfeiler–Leman refinement together with the HIC tool, the only production\-quality native hypergraph fingerprint we are aware of; their own Figure 3 exhibits a pair of non\-isomorphic hypergraphs the refinement collides, and the authors do not characterise the failure family\.Zhanget al\.\([2025](https://arxiv.org/html/2607.10194#bib.bib62)\)generalise the construction to akk\-dimensional hierarchy and prove it strict — each level separates pairs the previous level collapses — at a cost that grows asO​\(h⋅k⋅nk\+1\)O\(h\\cdot k\\cdot n^\{k\+1\}\), so completeness is unreachable at any affordable level\. Kernel methods inherit the same ceiling:Baiet al\.\([2014](https://arxiv.org/html/2607.10194#bib.bib63)\)build a hypergraph kernel from isomorphism tests on the directed line graph, converting the hypergraph into a graph before any comparison takes place\. These methods drive successful hypergraph learning architectures, just as the one\-dimensional test bounds message\-passing graph networks\(Xuet al\.,[2019](https://arxiv.org/html/2607.10194#bib.bib15)\), but they answer a different question than ours: they trade completeness for tractability, whereasIsalHGaims at a complete invariant and accepts, for now, a large runtime cost\. We therefore cite them as predecessors and do not benchmark against them \(Section[4\.2](https://arxiv.org/html/2607.10194#S4.SS2)returns to this point\)\.

### 2\.4Sequential encodings of combinatorial structures

Encoding structured objects as strings is an old and productive idea\. SMILES represents molecules as character strings and obtains canonical forms through Morgan\-style canonical atom ranking\(Weininger,[1988](https://arxiv.org/html/2607.10194#bib.bib28)\); SELFIES redesigned the alphabet so that every string decodes to a valid molecule\(Krennet al\.,[2020](https://arxiv.org/html/2607.10194#bib.bib30)\), the same closure propertyIsalHGadopts as a design requirement\. Sequential graph generation models such as GraphRNN linearise graphs into edge\-event sequences for learning purposes, without canonicality guarantees\(Youet al\.,[2018](https://arxiv.org/html/2607.10194#bib.bib18)\)\. Closest to our goal,Grzelak and Aßmann \([2021](https://arxiv.org/html/2607.10194#bib.bib70)\)define a canonical string encoding for pure bigraphs, a different class of objects \(process topologies with linked interfaces\) but the same logical aim of replacing structure comparison by string comparison\.

IsalHGdescends directly from two systems\.IsalGraphrepresents finite simple graphs as strings over a nine\-character alphabet executed by a virtual machine with a circular doubly\-linked list and two traversal pointers, and conjectures its exhaustive\-backtracking canonical string to be a complete graph invariant\(López\-Rubio,[2025](https://arxiv.org/html/2607.10194#bib.bib36); Lopez\-Rubio and Pascual\-Gonzalez,[2026b](https://arxiv.org/html/2607.10194#bib.bib71)\)\.IsalSRtransfers the machine to the labelled expression DAGs of symbolic regression, adds a two\-tier labelled alphabet, and uses the canonical string to collapse theΘ​\(k\!\)\\Theta\(k\!\)node\-numbering redundancy of the search space\(Lopez\-Rubio and Pascual\-Gonzalez,[2026a](https://arxiv.org/html/2607.10194#bib.bib72)\)\.IsalHGgeneralises the machine along a third axis: from edges over exactly two nodes with two pointers to hyperedges over up tokknodes withkkpointers\. We are not aware of any prior work that represents hypergraphs as executable instruction sequences serving as a canonical isomorphism invariant; the structurally closest proposals are the bigraph encoding ofGrzelak and Aßmann \([2021](https://arxiv.org/html/2607.10194#bib.bib70)\)and the two sibling systems above\.

## 3Methodology

This section defines theIsalHGrepresentation\. We fix notation and scope \(§[3\.1](https://arxiv.org/html/2607.10194#S3.SS1)\), define the instruction alphabet and the virtual machine that executes it \(§[3\.2](https://arxiv.org/html/2607.10194#S3.SS2)\), present the string\-to\-hypergraph interpreter \(§[3\.3](https://arxiv.org/html/2607.10194#S3.SS3)\) and the greedy hypergraph\-to\-string encoder \(§[3\.4](https://arxiv.org/html/2607.10194#S3.SS4)\), and construct the canonical string together with the two properties we conjecture and validate empirically \(§[3\.5](https://arxiv.org/html/2607.10194#S3.SS5)\)\.

### 3\.1Preliminaries and scope

A*hypergraph*is a pairH=\(V,E\)H=\(V,E\)whereVVis a finite set of nodes andEEis a set of hyperedges, each hyperedgee∈Ee\\in Ebeing a subset ofVVwith\|e\|≥2\|e\|\\geq 2\. The*arity*of a hyperedge is its cardinality\. The*primal graph*ofHHis the simple graph onVVthat joins two nodes whenever some hyperedge contains both;HHis*connected*when its primal graph is connected, and the distancedH​\(u,v\)d\_\{H\}\(u,v\)between two nodes is their distance in the primal graph\. Two hypergraphsH1=\(V1,E1\)H\_\{1\}=\(V\_\{1\},E\_\{1\}\)andH2=\(V2,E2\)H\_\{2\}=\(V\_\{2\},E\_\{2\}\)are*isomorphic*, writtenH1≅H2H\_\{1\}\\cong H\_\{2\}, when a bijectionϕ:V1→V2\\phi:V\_\{1\}\\to V\_\{2\}exists withE2=\{ϕ​\(e\):e∈E1\}E\_\{2\}=\\\{\\phi\(e\):e\\in E\_\{1\}\\\}\.

Throughout the paper, input hypergraphs are finite, undirected, connected, free of duplicate hyperedges, and of arity at most a fixed parameterk≥2k\\geq 2\. Directed hypergraphs, edge weights, and disconnected inputs are outside the scope of this preprint; node and hyperedge labels are supported by the alphabet but not exercised here \(Remark[3\.2](https://arxiv.org/html/2607.10194#S3.Thmtheorem2)\)\.

### 3\.2Instruction set and virtual machine

AnIsalHGstring is executed by a virtual machine whose state is a tuple

𝒮=\(H,ℒ,p1,…,pk\),\\mathcal\{S\}\\;=\\;\(H,\\mathcal\{L\},p\_\{1\},\\dots,p\_\{k\}\),whereHHis the hypergraph under construction,ℒ\\mathcal\{L\}is a circular doubly\-linked list \(CDLL\) holding one reference per node ofHH, andp1,…,pkp\_\{1\},\\dots,p\_\{k\}arekktraversal pointers intoℒ\\mathcal\{L\}\. The pointer count equals the arity boundkk: an instruction that creates a hyperedge designates each pre\-existing member through one of the leading pointers, sokkpointers suffice for hyperedges of arity up tokk\. The initial state consists of a single node, a CDLL containing only that node, and allkkpointers resting on it\.

The instruction alphabetΣHG\\Sigma\_\{\\mathrm\{HG\}\}contains five token families, summarised in Table[1](https://arxiv.org/html/2607.10194#S3.T1)\. Movement tokensPiP\_\{i\}andNiN\_\{i\}advance and retreat pointerpip\_\{i\}by one CDLL position\. Insertion tokensVi,jV\_\{i,j\}andCiC\_\{i\}create hyperedges:Vi,jV\_\{i,j\}connects theiinodes underp1,…,pip\_\{1\},\\dots,p\_\{i\}tojjfreshly created nodes, which are spliced intoℒ\\mathcal\{L\}immediately afterp1p\_\{1\}, whileCiC\_\{i\}connects theiinodes underp1,…,pip\_\{1\},\\dots,p\_\{i\}and creates no node\. Neither insertion token moves a pointer\.WWdoes nothing\. Counting the admissible parameter combinations gives

\|ΣHG\|=k​\(k−1\)2⏟Vi,j\+k⏟Ci\+k⏟Pi\+k⏟Ni\+1⏟W=k​\(k−1\)2\+3​k\+1,\|\\Sigma\_\{\\mathrm\{HG\}\}\|\\;=\\;\\underbrace\{\\tfrac\{k\(k\-1\)\}\{2\}\}\_\{V\_\{i,j\}\}\\;\+\\;\\underbrace\{k\}\_\{C\_\{i\}\}\\;\+\\;\\underbrace\{k\}\_\{P\_\{i\}\}\\;\+\\;\\underbrace\{k\}\_\{N\_\{i\}\}\\;\+\\;\\underbrace\{1\}\_\{W\}\\;=\\;\\tfrac\{k\(k\-1\)\}\{2\}\+3k\+1,which is1313for the arity\-3 hypergraphs of Section[4](https://arxiv.org/html/2607.10194#S4)and7676at the default capk=10k=10\.

Table 1:TheIsalHGinstruction setΣHG\\Sigma\_\{\\mathrm\{HG\}\}\. The machine state is\(H,ℒ,p1,…,pk\)\(H,\\mathcal\{L\},p\_\{1\},\\dots,p\_\{k\}\);val​\(pi\)\\mathrm\{val\}\(p\_\{i\}\)denotes the node referenced by pointerpip\_\{i\}\. No instruction can fail: pointer aliasing shrinks the support of the created hyperedge, and a duplicate hyperedge turnsCiC\_\{i\}into a no\-op\.###### Proposition 3\.1\(Closure\)\.

Every stringw∈ΣHG∗w\\in\\Sigma\_\{\\mathrm\{HG\}\}^\{\*\}decodes to a valid hypergraph\.

###### Proof\.

Every token is executable in every reachable state\.ℒ\\mathcal\{L\}is circular and never empty, soPiP\_\{i\}andNiN\_\{i\}are always defined\. The pointers always reference nodes ofHH, so the member sets built byVi,jV\_\{i,j\}andCiC\_\{i\}are well defined; if several pointers alias the same node the created hyperedge simply has smaller support, andVi,jV\_\{i,j\}always contains at least one fresh node, so it never duplicates an existing hyperedge\.CiC\_\{i\}skips duplicates by definition, andWWchanges nothing\. Hence execution is total and the final state contains a valid hypergraph\. ∎

Four decisions shape this alphabet\. First, hyperedge insertion is atomic: oneVi,jV\_\{i,j\}orCiC\_\{i\}token per hyperedge, so the string length decomposes into a structural part fixed byHHand a traversal part \(Remark[3\.4](https://arxiv.org/html/2607.10194#S3.Thmtheorem4)\)\. Second, the language is closed \(Proposition[3\.1](https://arxiv.org/html/2607.10194#S3.Thmtheorem1)\): there are no syntactically or semantically invalid strings, the property that makes molecular alphabets such as SELFIES robust for generative use\(Krennet al\.,[2020](https://arxiv.org/html/2607.10194#bib.bib30)\)and thatIsalGraphadopted for graphs\(Lopez\-Rubio and Pascual\-Gonzalez,[2026b](https://arxiv.org/html/2607.10194#bib.bib71)\)\. Third, movements are unit steps on a circular list, so the traversal cost of inserting a hyperedge equals the CDLL distance between the pointers and the intended members; encoders that keep this distance small produce short strings; cascade rule C1 of §[3\.4](https://arxiv.org/html/2607.10194#S3.SS4)minimises exactly this cost\. Fourth, new nodes enterℒ\\mathcal\{L\}next top1p\_\{1\}, keeping recently created nodes close to the active region of the list and therefore cheap to reach while the encoding of their neighbourhood completes\. The no\-opWWis retained for padding and for closure of the language under single\-token edits, followingIsalGraph\.

### 3\.3String\-to\-hypergraph conversion

The interpreterS2H\\mathrm\{S2H\}executes the tokens of a string sequentially from the initial state and returns the final hypergraph\. Algorithm[1](https://arxiv.org/html/2607.10194#alg1)lists the dispatch; Figure[1](https://arxiv.org/html/2607.10194#S3.F1)traces it on the canonical string of the Fano plane\. By Proposition[3\.1](https://arxiv.org/html/2607.10194#S3.Thmtheorem1)the interpreter is total: it never rejects its input, which distinguishesΣHG\\Sigma\_\{\\mathrm\{HG\}\}from encodings whose decoder must validate\.

Algorithm 1S2H​\(w,k\)\\mathrm\{S2H\}\(w,k\): string\-to\-hypergraph interpreter\.1:string

w∈ΣHG∗w\\in\\Sigma\_\{\\mathrm\{HG\}\}^\{\*\}, pointer count

kk
2:hypergraph

HH
3:

H←H\\leftarrowsingle node

u0u\_\{0\};

ℒ←\[u0\]\\mathcal\{L\}\\leftarrow\[u\_\{0\}\];

p1,…,pk←u0p\_\{1\},\\dots,p\_\{k\}\\leftarrow u\_\{0\}
4:foreach token

ttof

ww, in orderdo

5:if

t=Pit=P\_\{i\}thenadvance

pip\_\{i\}one position forward in

ℒ\\mathcal\{L\}
6:elseif

t=Nit=N\_\{i\}thenretreat

pip\_\{i\}one position backward in

ℒ\\mathcal\{L\}
7:elseif

t=Vi,jt=V\_\{i,j\}then

8:create nodes

u1,…,uju\_\{1\},\\dots,u\_\{j\}; insert them into

ℒ\\mathcal\{L\}after

p1p\_\{1\}
9:add hyperedge

\{val​\(p1\),…,val​\(pi\)\}∪\{u1,…,uj\}\\\{\\mathrm\{val\}\(p\_\{1\}\),\\dots,\\mathrm\{val\}\(p\_\{i\}\)\\\}\\cup\\\{u\_\{1\},\\dots,u\_\{j\}\\\}to

HH
10:elseif

t=Cit=C\_\{i\}then

11:

e←\{val​\(p1\),…,val​\(pi\)\}e\\leftarrow\\\{\\mathrm\{val\}\(p\_\{1\}\),\\dots,\\mathrm\{val\}\(p\_\{i\}\)\\\}
12:if

e∉E​\(H\)e\\notin E\(H\)thenadd hyperedge

eeto

HH
13:endif

14:elseif

t=Wt=Wthendo nothing

15:endif

16:endfor

17:return

HH

###### Example 3\.3\.

Letk=3k=3andw=V1,2​P2​C2w=V\_\{1,2\}\\,P\_\{2\}\\,C\_\{2\}\. Execution starts with the single node0and all pointers on it\.V1,2V\_\{1,2\}creates nodes11and22, splices them afterp1p\_\{1\}so thatℒ=\[0,1,2\]\\mathcal\{L\}=\[0,1,2\], and adds the arity\-3 hyperedge\{0,1,2\}\\\{0,1,2\\\}\.P2P\_\{2\}advancesp2p\_\{2\}to node11\.C2C\_\{2\}adds the arity\-2 hyperedge\{val​\(p1\),val​\(p2\)\}=\{0,1\}\\\{\\mathrm\{val\}\(p\_\{1\}\),\\mathrm\{val\}\(p\_\{2\}\)\\\}=\\\{0,1\\\}\. The result is a hypergraph on three nodes with one triple and one pair\.

![Refer to caption](https://arxiv.org/html/2607.10194v1/x3.png)Figure 1:S2H\\mathrm\{S2H\}execution on the canonical string of the Fano plane STS\(7\) \(1818tokens,k=3k=3\), sampled every three instructions\. Top: the CDLL with the pointersp1p\_\{1\},p2p\_\{2\},p3p\_\{3\}\. Middle: the token tape; pending instructions are highlighted and fade once executed\. Bottom: the output hypergraph, whose seven hyperedges materialise as theVV/CCtokens execute\. Tokens are rendered in the serialised labelled syntaxV​\[ℓe;i;j;ℓ1,…,ℓj\]V\[\\ell\_\{e\};i;j;\\ell\_\{1\},\\dots,\\ell\_\{j\}\]of Remark[3\.2](https://arxiv.org/html/2607.10194#S3.Thmtheorem2), with all labels equal to the trivial0\.
### 3\.4Hypergraph\-to\-string conversion

The greedy encoderH2S\\mathrm\{H2S\}inverts the interpreter\. Given a connected hypergraphHHand a start nodev0v\_\{0\}, it simulates the virtual machine while maintaining a correspondence between the machine’s nodes and the nodes ofHH: the initial machine node corresponds tov0v\_\{0\}, and every hyperedge ofHHis marked*waiting*until a token inserts its image\. At each step, a waiting hyperedge is*insertable*when at least one of its members already has a machine counterpart; its materialised members must be brought under the leading pointers, and its remaining members will be created fresh by theVVtoken itself\.

The cost of a candidate is measured in pointer movements\. A*displacement tuple*δ=\(δ1,…,δk\)∈ℤk\\delta=\(\\delta\_\{1\},\\dots,\\delta\_\{k\}\)\\in\\mathbb\{Z\}^\{k\}moves each pointerplp\_\{l\}by\|δl\|\|\\delta\_\{l\}\|CDLL positions, forward whenδl\>0\\delta\_\{l\}\>0and backward whenδl<0\\delta\_\{l\}<0, at total cost∑l\|δl\|\\sum\_\{l\}\|\\delta\_\{l\}\|\. For each insertable hyperedge the encoder computes the cost\-minimal displacement tuple that parksp1,…,pip\_\{1\},\\dots,p\_\{i\}on itsiimaterialised members — candidate\-driven search over the waiting hyperedges, which are far fewer than the\(2​\|ℒ\|\+1\)k\(2\|\\mathcal\{L\}\|\+1\)^\{k\}displacement tuples\. The winning candidate is selected by a fixed cascade:

1. C1\.*Cost\.*Minimise the total displacement∑l\|δl\|\\sum\_\{l\}\|\\delta\_\{l\}\|; among equal totals, take the lexicographically smallest\(\|δ1\|,…,\|δk\|,δ1,…,δk\)\\bigl\(\|\\delta\_\{1\}\|,\\dots,\|\\delta\_\{k\}\|,\\delta\_\{1\},\\dots,\\delta\_\{k\}\\bigr\)\.
2. C2\.*Kind\.*PreferVVoverCC\.
3. C3\.*Token\.*Take the lexicographically smallest\(i,j\)\(i,j\)amongVVcandidates, or the smallestiiamongCCcandidates\.
4. C4\.*Structure\.*Take the candidate hyperedge with the lexicographically smallest structural tupleη​\(e\)\\eta\(e\)\(§[3\.5](https://arxiv.org/html/2607.10194#S3.SS5)\)\.
5. C5\.*Backtracking\.*Any tie that survives C1–C4 spawns one branch per remaining candidate\. In addition, when aVi,jV\_\{i,j\}token is emitted, the assignment of thejjnew members ofeeto thejjinsertion positions afterp1p\_\{1\}is not determined by C1–C4; the encoder branches over these assignments as well\. All branches are explored to completion and the lexicographically smallest completed string is kept\.

The selected displacement is emitted as a block of movement tokens — retreats before advances, pointer index ascending, so that equal displacements always serialise identically — followed by theVi,jV\_\{i,j\}orCiC\_\{i\}token\. Algorithm[2](https://arxiv.org/html/2607.10194#alg2)summarises the loop, and Figure[2](https://arxiv.org/html/2607.10194#S3.F2)traces it on the Fano plane\. Connectivity guarantees progress: while waiting hyperedges remain, at least one of them touches the materialised region, so the loop terminates after exactly\|E​\(H\)\|\|E\(H\)\|insertion tokens\.

Algorithm 2GreedyH2S​\(H,v0\)\\mathrm\{H2S\}\(H,v\_\{0\}\): hypergraph\-to\-string encoder\.1:connected hypergraph

HHof arity at most

kk; start node

v0v\_\{0\}
2:string

wwwith

S2H​\(w,k\)≅H\\mathrm\{S2H\}\(w,k\)\\cong H\(Conjecture[3\.7](https://arxiv.org/html/2607.10194#S3.Thmtheorem7)\)

3:initialise the machine on a single node corresponding to

v0v\_\{0\}; mark every hyperedge of

HHwaiting

4:whilewaiting hyperedges remaindo

5:foreach insertable waiting hyperedge

eedo

6:compute the cost\-minimal displacement

δ​\(e\)\\delta\(e\)parking

p1,…,pip\_\{1\},\\dots,p\_\{i\}on the materialised members of

ee
7:endfor

8:select

\(e,δ​\(e\)\)\(e,\\delta\(e\)\)by the cascade C1–C5

9:emit the movement block of

δ​\(e\)\\delta\(e\); move the pointers

10:emit

Vi,jV\_\{i,j\}if

eehas

j≥1j\\geq 1unmaterialised members, else

CiC\_\{i\}; execute it; extend the node correspondence; unmark

ee
11:endwhile

12:returnthe emitted token sequence

![Refer to caption](https://arxiv.org/html/2607.10194v1/x4.png)Figure 2:GreedyH2S\\mathrm\{H2S\}encoding of the Fano plane STS\(7\), sampled every three instructions\. Top: the CDLL of the simulated machine with the pointersp1p\_\{1\},p2p\_\{2\},p3p\_\{3\}\. Middle: the output tape, filling left to right as tokens are emitted\. Bottom: the input hypergraph; each of the seven hyperedges fades once an emittedVV/CCtoken consumes it\. The final string has1818tokens:77insertion tokens \(33VV,44CC\) and1111movements\.
### 3\.5Structural tuples and the canonical string

The greedy encoder is deterministic once the start node is fixed and the C5 branches are resolved, but its output still depends onv0v\_\{0\}\. The canonical algorithm removes this dependence with a structural seed selector\. For a nodevvand depthh≥1h\\geq 1, let

ξh​\(v\)=\|\{u∈V:dH​\(u,v\)=h\}\|,ξ​\(v\)=\(ξ1​\(v\),ξ2​\(v\),ξ3​\(v\)\),\\xi\_\{h\}\(v\)\\;=\\;\\bigl\|\\\{\\,u\\in V:d\_\{H\}\(u,v\)=h\\,\\\}\\bigr\|,\\qquad\\xi\(v\)=\\bigl\(\\xi\_\{1\}\(v\),\\xi\_\{2\}\(v\),\\xi\_\{3\}\(v\)\\bigr\),the number of nodes at primal distance exactlyhhfromvv, collected up to depth33; for a hyperedgeee, letη​\(e\)=∑v∈eξ​\(v\)\\eta\(e\)=\\sum\_\{v\\in e\}\\xi\(v\)componentwise\. Both tuples are isomorphism\-invariant becauseϕ\\phipreserves primal distances\. The depth33is inherited fromIsalGraph; whether it must grow for specific hypergraph families is an open question\.

###### Definition 3\.5\(Canonical string\)\.

Tokens are ordered by their kind rankW<N<P<V<CW<N<P<V<Cand then by their numeric parameters, and token sequences are compared lexicographically under this order\. The*canonical string*of a connected hypergraphHHis

wH∗=lexmin⁡\{H2S​\(H,v0\):v0∈arg⁡maxlex⁡ξ​\(v\)\},w^\{\*\}\_\{H\}\\;=\\;\\operatorname\{lexmin\}\\bigl\\\{\\,\\mathrm\{H2S\}\(H,v\_\{0\}\)\\;:\\;v\_\{0\}\\in\\arg\\max\\nolimits\_\{\\mathrm\{lex\}\}\\xi\(v\)\\,\\bigr\\\},where eachH2S\\mathrm\{H2S\}run resolves its C5 ties by exploring all branches and returning its lexicographically smallest completed string\.

Restricting the start nodes to thearg⁡max\\arg\\maxofξ\\xiis sound because an isomorphism maps maximal\-ξ\\xinodes to maximal\-ξ\\xinodes, and it narrows the seed set on irregular inputs; on vertex\-transitive hypergraphs, where every node attains the maximum, the canonical algorithm degenerates to running the greedy from allnnnodes\.

###### Example 3\.6\.

For the Fano plane STS\(7\) withk=3k=3the canonical algorithm returns the1818\-token string

w∗=𝚅𝟷,𝟸​𝚅𝟷,𝟸​𝚅𝟷,𝟸​𝙽𝟷​𝙽𝟷​𝙽𝟷​𝙽𝟸​𝙿𝟹​𝙲𝟹​𝙽𝟷​𝙽𝟸​𝙲𝟹​𝙿𝟷​𝙿𝟹​𝙲𝟹​𝙽𝟷​𝙿𝟸​𝙲𝟹\.w^\{\*\}=\\mathtt\{V\_\{1,2\}\\,V\_\{1,2\}\\,V\_\{1,2\}\\,N\_\{1\}\\,N\_\{1\}\\,N\_\{1\}\\,N\_\{2\}\\,P\_\{3\}\\,C\_\{3\}\\,N\_\{1\}\\,N\_\{2\}\\,C\_\{3\}\\,P\_\{1\}\\,P\_\{3\}\\,C\_\{3\}\\,N\_\{1\}\\,P\_\{2\}\\,C\_\{3\}\}\.The threeV1,2V\_\{1,2\}tokens materialise the six non\-seed nodes and the three lines through the seed node; the fourC3C\_\{3\}tokens complete the remaining lines after repositioning the pointers\. Figures[2](https://arxiv.org/html/2607.10194#S3.F2)and[1](https://arxiv.org/html/2607.10194#S3.F1)trace the encoding and the decoding of this string\.

We now state the two properties on which the isomorphism application rests\. Both are conjectures: we argue them informally, validate them empirically in Section[5](https://arxiv.org/html/2607.10194#S5), and defer the formal proofs to a dedicated theoretical paper, exactly asIsalGraphandIsalSRdid for their canonical claims\(Lopez\-Rubio and Pascual\-Gonzalez,[2026b](https://arxiv.org/html/2607.10194#bib.bib71),[a](https://arxiv.org/html/2607.10194#bib.bib72)\)\.

###### Conjecture 3\.7\(Round\-trip fidelity\)\.

For every connected hypergraphHHof arity at mostkkand every start nodev0∈V​\(H\)v\_\{0\}\\in V\(H\),S2H​\(H2S​\(H,v0\),k\)≅H\.\\mathrm\{S2H\}\\bigl\(\\mathrm\{H2S\}\(H,v\_\{0\}\),k\\bigr\)\\cong H\.

The encoder maintains, by construction, a bijection between the machine’s nodes and the visited nodes ofHH, and every emitted insertion token adds the image of exactly one waiting hyperedge under that bijection\. If the loop invariant — the machine state always equals the state thatS2H\\mathrm\{S2H\}reaches on the partial string — holds through every branch, the final correspondence is an isomorphism\. Establishing the invariant rigorously is the missing step\.

###### Conjecture 3\.8\(Canonical completeness\)\.

For all connected hypergraphsH1,H2H\_\{1\},H\_\{2\}of arity at mostkk,H1≅H2⇔wH1∗=wH2∗\.H\_\{1\}\\cong H\_\{2\}\\iff w^\{\*\}\_\{H\_\{1\}\}=w^\{\*\}\_\{H\_\{2\}\}\.

The forward direction would follow from the label\-blindness of the canonical search: an isomorphismϕ\\phimaps the maximal\-ξ\\xiseeds ofH1H\_\{1\}onto those ofH2H\_\{2\}, preserves every quantity the cascade C1–C4 inspects \(displacement costs depend only on the evolving CDLL geometry, which is identical on both sides, andη\\etais isomorphism\-invariant\), and maps the C5 branch sets onto each other; the two hypergraphs then generate the same set of candidate strings and hence the same lexicographic minimum\. The backward direction would follow from Conjecture[3\.7](https://arxiv.org/html/2607.10194#S3.Thmtheorem7)by transitivity:H1≅S2H​\(wH1∗\)=S2H​\(wH2∗\)≅H2H\_\{1\}\\cong\\mathrm\{S2H\}\(w^\{\*\}\_\{H\_\{1\}\}\)=\\mathrm\{S2H\}\(w^\{\*\}\_\{H\_\{2\}\}\)\\cong H\_\{2\}\. What a proof must establish rigorously is that the greedy\-plus\-backtracking search depends only on the abstract incidence structure of the input, never on node identifiers\. We leave this verification as future work; Section[5](https://arxiv.org/html/2607.10194#S5)reports the supporting evidence, with no counterexample found\.

## 4Computational experiments

The experiments answer two questions: does the round\-trip property of Conjecture[3\.7](https://arxiv.org/html/2607.10194#S3.Thmtheorem7)hold in practice, and where does the native canonical algorithm of Definition[3\.5](https://arxiv.org/html/2607.10194#S3.Thmtheorem5)stand, in correctness and in cost, against the Levi\-reduction baselines on identical inputs\. §[4\.1](https://arxiv.org/html/2607.10194#S4.SS1)specifies the data cohort and §[4\.2](https://arxiv.org/html/2607.10194#S4.SS2)the measurement protocol\.

### 4\.1Data: connected uniform random hypergraphs

All instances are drawn from therr\-uniform Erdős–Rényi model: givennnnodes and an inclusion probabilitypp, each of the\(nr\)\\binom\{n\}\{r\}candidate hyperedges of arityrrenters the hypergraph independently with probabilitypp\(Chodrow,[2020](https://arxiv.org/html/2607.10194#bib.bib66)\), as implemented in the XGI library\(Landryet al\.,[2023](https://arxiv.org/html/2607.10194#bib.bib67)\)\. We parameterise density by the expected number of hyperedges per node,cc, settingp=c​n/\(nr\)p=c\\,n/\\binom\{n\}\{r\}so that𝔼​\[m\]=c​n\\mathbb\{E\}\[m\]=c\\,n, and we reportccas the density axis\.

Because the encoder requires connected input \(Remark[3\.10](https://arxiv.org/html/2607.10194#S3.Thmtheorem10)\) while the Levi baselines accept any input, a raw Erdős–Rényi sample would hand the two families different effective workloads\. We therefore condition the generator on connectivity: samples whose primal graph is disconnected are rejected and redrawn under a deterministic seed walk \(seed,seed\+1,000,003,seed\+2⋅1,000,003,…\\mathrm\{seed\},\\ \\mathrm\{seed\}\+1\{,\}000\{,\}003,\\ \\mathrm\{seed\}\+2\\cdot 1\{,\}000\{,\}003,\\dots\), so every method fingerprints exactly the same connected hypergraph and the cohort remains reproducible from the seed list alone\. On the grid below, acceptance typically requires one to three draws\. We call the resulting distribution*uniform Erdős–Rényi conditional on connectivity*\.

The cohort sweeps three axes: node countn∈\{8,12,16,20,25\}n\\in\\\{8,12,16,20,25\\\}, arityr=3r=3, and densityc∈\{1\.0,1\.5,2\.0\}c\\in\\\{1\.0,1\.5,2\.0\\\}, with ten seeds \(seed∈\{0,…,9\}\\mathrm\{seed\}\\in\\\{0,\\dots,9\\\}\) per\(n,c\)\(n,c\)cell —150150instances in total\. Figure[3](https://arxiv.org/html/2607.10194#S4.F3)shows how each axis deforms the instances\. Arity33is the regime of the classical design\-theory literature \(Steiner triple systems are33\-uniform\), and thennandccranges were fixed in preliminary runs as the largest grid on which every method, includingIsalHG, terminates within the600600s per\-fingerprint budget on every instance; the ceiling is set byIsalHG, not by the baselines, a point Section[6](https://arxiv.org/html/2607.10194#S6)returns to\. For the correctness protocol, each instanceHHis paired withσ​\(H\)\\sigma\(H\)for a vertex permutationσ\\sigmadrawn uniformly from the cell’s pinned generator, giving150150isomorphic pairs with a known certificate\.

![Refer to caption](https://arxiv.org/html/2607.10194v1/x5.png)Figure 3:The cohort axes at seed0\. Centre\-left: the baseline cell \(n=16n=16,r=3r=3,c=1\.5c=1\.5\)\. Moving left and right varies the node count \(n=8n=8andn=25n=25at the same density\); the two right\-hand panels vary the density atn=16n=16\(c=1c=1andc=2c=2\)\. Hyperedges are drawn as shaded regions over the numbered nodes\. All five instances are connected by construction under the reject\-resample policy of §[4\.1](https://arxiv.org/html/2607.10194#S4.SS1)\.
### 4\.2Experimental setup

#### Methods under test\.

Four methods compute one fingerprint per hypergraph and decide isomorphism by fingerprint equality\.IsalHGcomputes the canonical string of Definition[3\.5](https://arxiv.org/html/2607.10194#S3.Thmtheorem5); the search is implemented in C\+\+17 behind a Python interface\. The three baselines translateHHinto its Levi graphB​\(H\)B\(H\)with the standard22\-colouring \(node\-vertices versus hyperedge\-vertices\) and canonically label it with, respectively, nauty 2\.8\.8 through thepynautybinding, bliss 0\.77 throughpython\-igraph, and Traces through thedreadnautinterface of the nauty 2\.9\.1 distribution, whose canonical graph line serves as the fingerprint\.

The comparison is exact\-versus\-exact: a baseline must solve the same problemIsalHGsolves: an isomorphism decision with zero false positives and zero false negatives on every pair, while existing as runnable software\. These two requirements pin the baseline set exactly\. The Levi reduction driven by nauty, Traces, or bliss is, as discussed in §[2\.1](https://arxiv.org/html/2607.10194#S2.SS1), the only exact hypergraph isomorphism procedure with public implementations, and design\-theory systems \(SageMath, GAP\) delegate to nauty internally, so benchmarking the three engines directly also covers the tools built on them\. The theoretical exact algorithms of §[2\.2](https://arxiv.org/html/2607.10194#S2.SS2)have no implementations to run\. The Weisfeiler–Leman family of §[2\.3](https://arxiv.org/html/2607.10194#S2.SS3)is excluded on principle rather than availability: those methods compute incomplete invariants, so a runtime comparison against them would compare answers to different questions; their own published counterexamples already locate the correctness difference\.

#### Measurements\.

For each of the600600\(method, instance\) pairs we record the fingerprint wall\-clock time as the median of1010repeated calls \(time\.perf\_counter\), its interquartile range, the peak resident\-set increment of the call \(getrusage\(RUSAGE\_SELF\)\), and the fingerprint length in bytes\. A600600s watchdog per fingerprint converts non\-termination into an explicit DNF record\. Because Traces runs as a subprocess, its memory column measures the parent process only; its wall\-clock includes the subprocess start\-up\. Both caveats are flagged where they matter\.

#### Correctness protocol\.

Three checks run on top of the measurements\. \(i\)*Positive pairs*: every method must returntrueon\(H,σ​\(H\)\)\(H,\\sigma\(H\)\)for each of the150150instances —600600checks in total\. \(ii\)*Cross\-method agreement*: within every\(n,c\)\(n,c\)cell, the iso\-equivalence partition that each method’s fingerprints induce on the cell’s ten instances must coincide across the four methods\. \(iii\)*Round\-trip*: for every cohort instance and for five named designs \(the Fano plane STS\(7\), STS\(9\), the two non\-isomorphic cyclic STS\(13\) with starter blocks\{0,1,4\}\\\{0,1,4\\\}and\{0,1,6\}\\\{0,1,6\\\}, and the generalized quadrangle GQ\(2,2\)\), the canonical string is decoded withS2H\\mathrm\{S2H\}and the result is compared against the original hypergraph with nauty as the independent oracle\.

#### Execution\.

The timing sweep ran on the CPU partition of the Picasso supercomputer \(SCBI, University of Málaga\) as one single\-core SLURM array task per \(method, instance\) pair,600600tasks in total, with1616GB of memory per task; every task completed\. The C\+\+ engine was compiled with GCC at\-O3\. The round\-trip checks, which assert a boolean rather than a timing, ran on a development workstation\. All seeds are pinned, and the cohort, the configuration, and the per\-cell result records are archived with the project\.

## 5Results

We report the round\-trip verification \(§[5\.1](https://arxiv.org/html/2607.10194#S5.SS1)\), the correctness agreement across the four methods \(§[5\.2](https://arxiv.org/html/2607.10194#S5.SS2)\), the wall\-clock and memory characterisation \(§[5\.3](https://arxiv.org/html/2607.10194#S5.SS3)\), and the fingerprint lengths \(§[5\.4](https://arxiv.org/html/2607.10194#S5.SS4)\)\.

### 5\.1Round\-trip verification

The round\-trip check passes on every tested input: all150150cohort instances and all five named designs satisfyS2H​\(wH∗,k\)≅H\\mathrm\{S2H\}\(w^\{\*\}\_\{H\},k\)\\cong H, with the isomorphism confirmed by nauty on the Levi graphs \(Table[2](https://arxiv.org/html/2607.10194#S5.T2)\)\. Canonical strings range from9898to1,5561\{,\}556serialised bytes over the cohort \(median174174bytes atn=8n=8,982982bytes atn=25n=25\)\. Figures[2](https://arxiv.org/html/2607.10194#S3.F2)and[1](https://arxiv.org/html/2607.10194#S3.F1)display one such round trip on the Fano plane: the encoder produces the1818\-token canonical string of Example[3\.6](https://arxiv.org/html/2607.10194#S3.Thmtheorem6), andS2H\\mathrm\{S2H\}decodes it back into a hypergraph isomorphic to the input\. These results support Conjecture[3\.7](https://arxiv.org/html/2607.10194#S3.Thmtheorem7)on155155structurally diverse inputs; they do not prove it\.

Table 2:Round\-trip verification\. Each input is encoded to its canonical stringwH∗w^\{\*\}\_\{H\}, decoded withS2H\\mathrm\{S2H\}, and compared against the original with nauty as the independent oracle\. The two cyclic STS\(13\) are not isomorphic to each other and receive distinct canonical strings\.
### 5\.2Correctness agreement

All600600positive\-pair checks pass: on every one of the150150\(H,σ​\(H\)\)\(H,\\sigma\(H\)\)pairs, all four methods —IsalHG, nauty, Traces, and bliss — confirm isomorphism on every pair, with zero failures\. Within every\(n,c\)\(n,c\)cell, the four methods also induce identical iso\-equivalence partitions over the cell’s ten instances, so no pair exists anywhere in the cohort on whichIsalHGand a Levi baseline disagree, in either direction\. The named designs add a discrimination check at the other pole of the symmetry spectrum: the two non\-isomorphic cyclic STS\(13\), which agree on the trivial invariants \(nn,mm, degree and arity sequences\), receive distinct canonical strings \(Table[2](https://arxiv.org/html/2607.10194#S5.T2)\)\. Across everything we tested, no counterexample to Conjecture[3\.8](https://arxiv.org/html/2607.10194#S3.Thmtheorem8)appeared\. We note the limits of this evidence: the cohort is small \(n≤25n\\leq 25,r=3r=3\), and random hypergraphs are rigid with high probability, so the hard cases for canonical algorithms — large\-automorphism designs at scale — are only touched by the five fixtures of Table[2](https://arxiv.org/html/2607.10194#S5.T2)\.

### 5\.3Runtime and memory

Table[3](https://arxiv.org/html/2607.10194#S5.T3)and Figure[4](https://arxiv.org/html/2607.10194#S5.F4)report wall\-clock time; every cell of the grid completed for every method\. The Levi baselines dominate the entire grid\. nauty is the fastest method on every cell, between0\.0480\.048and0\.2010\.201ms per fingerprint; bliss runs within a factor of22–44of nauty; Traces stays at a flat≈3\\approx 3ms, which its fitted exponent \(n−0\.02n^\{\-0\.02\}\) identifies as thedreadnautsubprocess start\-up floor rather than algorithmic cost\.IsalHGspans16\.916\.9ms to22\.822\.8s over the same grid\. The fitted growth exponents separate the regimes:n5\.79n^\{5\.79\}forIsalHG\(pooled overcc;n6\.2n^\{6\.2\}atc=2c=2alone\) againstn0\.93n^\{0\.93\}for nauty andn0\.80n^\{0\.80\}for bliss\. The per\-cell geometric\-mean ratio ofIsalHGto the best Levi engine grows from311×311\\timesat the smallest, densest cell to117,672×117\{,\}672\\timesat\(n,c\)=\(25,1\.5\)\(n,c\)=\(25,1\.5\), roughly tripling with each step innn\. No crossover regime appears anywhere in the tested grid, and the exponent gap implies none will appear at largernnunder the current canonical search\.

Table 3:Median wall\-clock per fingerprint \(ms; median over ten seeds, ten repeats per seed\) for the fifteen\(n,c\)\(n,c\)cells of ther=3r=3grid, and the geometric\-mean ratio ofIsalHGover the best Levi engine per instance\. No method timed out on any instance \(600600s budget\)\.![Refer to caption](https://arxiv.org/html/2607.10194v1/x6.png)Figure 4:Median wall\-clock per fingerprint \(log scale\) across the fifteen\(n,c\)\(n,c\)cells, grouped bynnwithc∈\{1,1\.5,2\}c\\in\\\{1,1\.5,2\\\}inside each group\. Markers are medians over ten seeds with interquartile ranges; dashed lines are per\-method power\-law fitsT≈a⋅nβT\\approx a\\cdot n^\{\\beta\}with the fitted exponents in the legend\. The flat Traces line is the subprocess start\-up floor, not the algorithm\.Memory does not separate the methods at this scale \(Figure[5](https://arxiv.org/html/2607.10194#S5.F5)\): the peak resident\-set increment per fingerprint stays below22MiB for every method on every cell, with quantisation at the page\-size granularity dominating the visible variation\. The Traces column measures the parent process only \(§[4\.2](https://arxiv.org/html/2607.10194#S4.SS2)\), so its flat0\.40\.4MiB line excludes the subprocess\.

![Refer to caption](https://arxiv.org/html/2607.10194v1/x7.png)Figure 5:Peak resident\-set increment per fingerprint \(log scale\) over the same grid as Figure[4](https://arxiv.org/html/2607.10194#S5.F4)\. All methods stay below22MiB; page\-granularity quantisation dominates the visible variation\. The Traces series measures the parent process only\.
### 5\.4Fingerprint length

Figure[6](https://arxiv.org/html/2607.10194#S5.F6)compares the fingerprint sizes\. The canonical string is comparable in length to the serialised canonical labellings of the Levi engines: its median is460460bytes over the grid, between nauty \(320320bytes\) and bliss \(784784bytes\), while Traces’ compact graph\-line format is the smallest at8888bytes\. The fitted growth isn1\.49n^\{1\.49\}forIsalHGagainstn1\.11n^\{1\.11\}ton1\.27n^\{1\.27\}for the baselines — consistent with Remark[3\.4](https://arxiv.org/html/2607.10194#S3.Thmtheorem4): the string pays one token per hyperedge \(m=c​nm=c\\,nhere\) plus the pointer travel, which grows with the CDLL length\. Fingerprint length is the one axis on whichIsalHGdoes not trail the Levi baselines by orders of magnitude\.

![Refer to caption](https://arxiv.org/html/2607.10194v1/x8.png)Figure 6:Median fingerprint length in bytes \(log scale\) over the same grid as Figure[4](https://arxiv.org/html/2607.10194#S5.F4), with per\-method power\-law fits in the legend\.IsalHG’s canonical string lies between the serialised canonical labellings of nauty and bliss; Traces’ graph line is the most compact\.

## 6Discussion

#### What the agreement establishes, and what it does not\.

The correctness outcome is uniform:600600positive\-pair verdicts with zero failures, identical partitions in every cell, a perfect round\-trip record, and distinct canonical strings for the two non\-isomorphic STS\(13\)\. Everything we measured is consistent with Conjectures[3\.7](https://arxiv.org/html/2607.10194#S3.Thmtheorem7)and[3\.8](https://arxiv.org/html/2607.10194#S3.Thmtheorem8), and the experiments were designed so that a single disagreement with any of the three Levi engines would have surfaced as an explicit counterexample\. None did\. The evidence remains bounded: the cohort is small and, being random, rigid with high probability, so the regime where canonical algorithms historically fail — large automorphism groups at scale — is represented only by the five designs of Table[2](https://arxiv.org/html/2607.10194#S5.T2)\. We leave the extension of the correctness campaign to the published design catalogues for a separate empirical paper; formal proofs belong to a theoretical one\.

#### Reading the runtime gap\.

The gap is large and it grows:311×311\\timesat\(n,c\)=\(8,1\)\(n,c\)=\(8,1\),117,672×117\{,\}672\\timesat\(25,1\.5\)\(25,1\.5\), with fitted exponentsn5\.79n^\{5\.79\}againstn0\.93n^\{0\.93\}\(Figure[4](https://arxiv.org/html/2607.10194#S5.F4)\)\. Two properties of the canonical search of Definition[3\.5](https://arxiv.org/html/2607.10194#S3.Thmtheorem5)account for the shape\. First, the seed rule runs the greedy once per maximal\-ξ\\xinode, and on near\-regular random hypergraphs the maximal\-ξ\\xiclass is large, so the multiplier approachesnn\. Second, everyVVemission branches over the assignments of its new nodes \(cascade rule C5\), and the branch count compounds along the string, bounded by the product ofj\!j\!over theVVemissions \(Remark[3\.9](https://arxiv.org/html/2607.10194#S3.Thmtheorem9)\)\. Both costs are intrinsic to the search discipline, not to its implementation: the measured engine is compiled C\+\+, and the exponent gap means no constant factor will close it\. During development we also evaluated several encoder variants — a single\-seed greedy, colour\-refinement pruning of the branch sets, and an exhaustive search — and none of them changed the competitive picture on this cohort\.

#### Fairness in both directions\.

The comparison flatters neither side\. nauty, Traces, and bliss embody four decades of individualisation–refinement engineering\(McKay,[1981](https://arxiv.org/html/2607.10194#bib.bib50); McKay and Piperno,[2014](https://arxiv.org/html/2607.10194#bib.bib51); Junttila and Kaski,[2007](https://arxiv.org/html/2607.10194#bib.bib52)\), whereas the canonical algorithm measured here is the first implementation of a new representation; we did not expect it to match mature engines\. In the other direction, two measurement artefacts favour neither side but bear noting: the flat33ms Traces line is subprocess start\-up rather than solver time, so Traces would track the other engines if invoked in\-process, and the memory columns are uninformative at this scale \(all methods below22MiB\), with the Traces value measuring the parent process only\.

#### Paths forward\.

The measurements identify the two components that dominate the cost\. The seed multiplier requires stronger isomorphism\-invariant seed selectors than depth\-3ξ\\xi— the design\-theory practice of pre\-partitioning by configuration counts\(Kaski and Östergård,[2004](https://arxiv.org/html/2607.10194#bib.bib64)\)is the natural template\. The branch compounding requires a search discipline that prunes equivalent branches instead of enumerating them, in the spirit of the individualisation–refinement tree\(McKay and Piperno,[2014](https://arxiv.org/html/2607.10194#bib.bib51)\)and of the canonisation framework ofSchweitzer and Wiebking \([2019](https://arxiv.org/html/2607.10194#bib.bib58)\), while keeping the canonical string as the output object\. Both directions preserve the contribution of this paper — the representation and its conjectured completeness — and replace only the search that computeswH∗w^\{\*\}\_\{H\}\.

#### Scope limits\.

Four threats to validity delimit the claims\. The grid fixesr=3r=3andn≤25n\\leq 25, so nothing here speaks to higher arities or larger inputs except the fitted exponents\. The cohort is conditioned on connectivity, a distribution choice made so that all methods receive identical inputs; raw Erdős–Rényi sampling would instead route disconnected instances away fromIsalHG\(Remark[3\.10](https://arxiv.org/html/2607.10194#S3.Thmtheorem10)\)\. The timing hardware is a single CPU\-partition node class, and the600600s budget, although never reached, caps what the grid could have explored\. Finally, fingerprint length \(Figure[6](https://arxiv.org/html/2607.10194#S5.F6)\) is the only axis where the native encoding is presently competitive; we report it as an observation, not as a claim of advantage\.

## 7Conclusion

#### Summary of contributions\.

This paper has introducedIsalHG, a sequential instruction\-based representation of finite connected hypergraphs of bounded arity\. A virtual machine defines the encoding: it manipulates a circular doubly\-linked list of node references throughkktraversal pointers, inserting hyperedges — and, through theVi,jV\_\{i,j\}tokens, new nodes — as instructions execute\. We establish four points:

1. \(i\)*A native representation with a closed language\.*Every string overΣHG\\Sigma\_\{\\mathrm\{HG\}\}decodes to a valid hypergraph \(Proposition[3\.1](https://arxiv.org/html/2607.10194#S3.Thmtheorem1)\), and the alphabet size grows only quadratically in the arity bound,\|ΣHG\|=k​\(k−1\)/2\+3​k\+1\|\\Sigma\_\{\\mathrm\{HG\}\}\|=k\(k\-1\)/2\+3k\+1\. This is, to our knowledge, the first executable\-string representation of hypergraphs intended as a canonical isomorphism invariant\.
2. \(ii\)*Round\-trip fidelity, verified\.*The greedyH2S\\mathrm\{H2S\}encoder and theS2H\\mathrm\{S2H\}interpreter invert each other up to isomorphism on every tested input:150150connected random uniform hypergraphs and five named designs, confirmed independently by nauty \(Conjecture[3\.7](https://arxiv.org/html/2607.10194#S3.Thmtheorem7); Table[2](https://arxiv.org/html/2607.10194#S5.T2)\)\.
3. \(iii\)*Canonical completeness, conjectured and unrefuted\.*The canonical stringwH∗w^\{\*\}\_\{H\}agreed with nauty, Traces, and bliss on all600600isomorphism verdicts of the cohort and separated the two non\-isomorphic STS\(13\) \(Conjecture[3\.8](https://arxiv.org/html/2607.10194#S3.Thmtheorem8)\); no counterexample was found anywhere in the campaign\.
4. \(iv\)*An honest cost characterisation\.*On the tested grid the Levi baselines dominate wall\-clock by three to five orders of magnitude \(geometric\-mean ratio311×311\\timesto117,672×117\{,\}672\\times\), with fitted growthn5\.79n^\{5\.79\}for the current canonical search againstn0\.93n^\{0\.93\}for nauty\. Fingerprint length is the one axis where the native encoding is already comparable \(460460versus320320–784784median bytes\)\.

#### Limitations\.

The two central conjectures — round\-trip fidelity \(Conjecture[3\.7](https://arxiv.org/html/2607.10194#S3.Thmtheorem7)\) and canonical completeness \(Conjecture[3\.8](https://arxiv.org/html/2607.10194#S3.Thmtheorem8)\) — remain unproven; we defer their proofs to a dedicated theoretical paper\. The canonical search is not competitive in runtime with the Levi pipeline anywhere in the tested regime, and its fitted exponent implies the gap widens withnn\. The encoder requires connected input, hyperedge arities are capped by the pointer countkk, and the empirical evidence covers33\-uniform hypergraphs withn≤25n\\leq 25plus five design fixtures\.

#### Future directions\.

Our immediate priorities are the formal proofs of both conjectures and a redesigned canonical search — stronger structural seed invariants and pruning of equivalent branches — that keeps the string as the output object\. Our planned empirical campaign extends the correctness evidence to the exhaustive Steiner\-system catalogues, hard symmetric families, and real\-world hypergraph corpora, where the deduplication workload also exercises the representation at scale\. On the representation side, the labelled alphabet of Remark[3\.2](https://arxiv.org/html/2607.10194#S3.Thmtheorem2)and the treatment of disconnected inputs complete the object class, and the string form itself — compact, closed, and sequential — suits the similarity\-search and generative uses thatIsalGraphandIsalSRexplore for their domains\(Lopez\-Rubio and Pascual\-Gonzalez,[2026b](https://arxiv.org/html/2607.10194#bib.bib71),[a](https://arxiv.org/html/2607.10194#bib.bib72)\)\.

## 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

- Colored hypergraph isomorphism is fixed parameter tractable\.Algorithmica71\(1\),pp\. 120–138\.External Links:[Document](https://dx.doi.org/10.1007/s00453-013-9787-y)Cited by:[§2\.2](https://arxiv.org/html/2607.10194#S2.SS2.p1.5)\.
- L\. Babai and P\. Codenotti \(2008\)Isomorphism of hypergraphs of low rank in moderately exponential time\.In49th Annual IEEE Symposium on Foundations of Computer Science \(FOCS\),pp\. 667–676\.External Links:[Document](https://dx.doi.org/10.1109/FOCS.2008.80)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.2](https://arxiv.org/html/2607.10194#S2.SS2.p1.5)\.
- L\. Babai \(2016\)Graph isomorphism in quasipolynomial time\.arXiv preprint\.Note:arXiv:1512\.03547Cited by:[§2\.1](https://arxiv.org/html/2607.10194#S2.SS1.p1.1)\.
- L\. Bai, P\. Ren, and E\. R\. Hancock \(2014\)A hypergraph kernel from isomorphism tests\.In22nd International Conference on Pattern Recognition \(ICPR\),pp\. 3880–3885\.External Links:[Document](https://dx.doi.org/10.1109/ICPR.2014.667)Cited by:[§2\.3](https://arxiv.org/html/2607.10194#S2.SS3.p1.4)\.
- F\. Battiston, G\. Cencetti, I\. Iacopini, V\. Latora, M\. Lucas, A\. Patania, J\. Young, and G\. Petri \(2020\)Networks beyond pairwise interactions: Structure and dynamics\.Physics Reports874,pp\. 1–92\.External Links:[Document](https://dx.doi.org/10.1016/j.physrep.2020.05.004)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p1.1)\.
- A\. R\. Benson, R\. Abebe, M\. T\. Schaub, A\. Jadbabaie, and J\. Kleinberg \(2018\)Simplicial closure and higher\-order link prediction\.Proceedings of the National Academy of Sciences115\(48\),pp\. E11221–E11230\.External Links:[Document](https://dx.doi.org/10.1073/pnas.1800683115)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p1.1)\.
- C\. Berge \(1973\)Graphs and hypergraphs\.North\-Holland,Amsterdam\.Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p1.1),[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.1](https://arxiv.org/html/2607.10194#S2.SS1.p2.5)\.
- J\. Böker \(2019\)Color refinement, homomorphisms, and hypergraphs\.InGraph\-Theoretic Concepts in Computer Science \(WG 2019\),Lecture Notes in Computer Science, Vol\.11789,pp\. 338–350\.External Links:[Document](https://dx.doi.org/10.1007/978-3-030-30786-8%5F26)Cited by:[§2\.3](https://arxiv.org/html/2607.10194#S2.SS3.p1.4)\.
- J\. Cai, M\. Fürer, and N\. Immerman \(1992\)An optimal lower bound on the number of variables for graph identification\.Combinatorica12\(4\),pp\. 389–410\.External Links:[Document](https://dx.doi.org/10.1007/BF01305232)Cited by:[§2\.3](https://arxiv.org/html/2607.10194#S2.SS3.p1.4)\.
- P\. S\. Chodrow \(2020\)Configuration models of random hypergraphs\.Journal of Complex Networks8\(3\),pp\. cnaa018\.External Links:[Document](https://dx.doi.org/10.1093/comnet/cnaa018)Cited by:[§4\.1](https://arxiv.org/html/2607.10194#S4.SS1.p1.10)\.
- C\. J\. Colbourn and J\. H\. Dinitz \(Eds\.\) \(2007\)Handbook of combinatorial designs\.2nd edition,CRC Press,Boca Raton\.Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.10194#S2.SS1.p2.5)\.
- Y\. Feng, J\. Han, S\. Ying, and Y\. Gao \(2024\)Hypergraph isomorphism computation\.IEEE Transactions on Pattern Analysis and Machine Intelligence46\(5\),pp\. 3880–3893\.External Links:[Document](https://dx.doi.org/10.1109/TPAMI.2024.3353199)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p1.1),[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.3](https://arxiv.org/html/2607.10194#S2.SS3.p1.4)\.
- D\. Grzelak and U\. Aßmann \(2021\)A canonical string encoding for pure bigraphs\.SN Computer Science2\(4\),pp\. 246\.External Links:[Document](https://dx.doi.org/10.1007/s42979-021-00552-5)Cited by:[§2\.4](https://arxiv.org/html/2607.10194#S2.SS4.p1.1),[§2\.4](https://arxiv.org/html/2607.10194#S2.SS4.p2.3)\.
- T\. Junttila and P\. Kaski \(2007\)Engineering an efficient canonical labeling tool for large and sparse graphs\.InProceedings of the Ninth Workshop on Algorithm Engineering and Experiments \(ALENEX\),pp\. 135–149\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611972870.13)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.1](https://arxiv.org/html/2607.10194#S2.SS1.p1.1),[§6](https://arxiv.org/html/2607.10194#S6.SS0.SSS0.Px3.p1.2)\.
- P\. Kaski and P\. R\. J\. Östergård \(2004\)The Steiner triple systems of order 19\.Mathematics of Computation73\(248\),pp\. 2075–2092\.External Links:[Document](https://dx.doi.org/10.1090/S0025-5718-04-01626-6)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p1.1),[§2\.1](https://arxiv.org/html/2607.10194#S2.SS1.p2.5),[§6](https://arxiv.org/html/2607.10194#S6.SS0.SSS0.Px4.p1.2)\.
- M\. Krenn, F\. Häse, A\. Nigam, P\. Friederich, and A\. Aspuru\-Guzik \(2020\)Self\-referencing embedded strings \(SELFIES\): A 100% robust molecular string representation\.Machine Learning: Science and Technology1\(4\),pp\. 045024\.External Links:[Document](https://dx.doi.org/10.1088/2632-2153/aba947)Cited by:[§2\.4](https://arxiv.org/html/2607.10194#S2.SS4.p1.1),[§3\.2](https://arxiv.org/html/2607.10194#S3.SS2.p3.6)\.
- N\. W\. Landry, M\. Lucas, I\. Iacopini, G\. Petri, A\. Schwarze, A\. Patania, and L\. Torres \(2023\)XGI: A Python package for higher\-order interaction networks\.Journal of Open Source Software8\(85\),pp\. 5162\.External Links:[Document](https://dx.doi.org/10.21105/joss.05162)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p1.1),[§4\.1](https://arxiv.org/html/2607.10194#S4.SS1.p1.10)\.
- E\. Lopez\-Rubio and M\. Pascual\-Gonzalez \(2026a\)Instruction set and language for symbolic regression\.Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p3.6),[§2\.4](https://arxiv.org/html/2607.10194#S2.SS4.p2.3),[§3\.5](https://arxiv.org/html/2607.10194#S3.SS5.p3.1),[Remark 3\.2](https://arxiv.org/html/2607.10194#S3.Thmtheorem2.p1.4),[§7](https://arxiv.org/html/2607.10194#S7.SS0.SSS0.Px3.p1.1)\.
- E\. Lopez\-Rubio and M\. Pascual\-Gonzalez \(2026b\)Instruction set for the representation of graphs\.Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p3.6),[§2\.4](https://arxiv.org/html/2607.10194#S2.SS4.p2.3),[§3\.2](https://arxiv.org/html/2607.10194#S3.SS2.p3.6),[§3\.5](https://arxiv.org/html/2607.10194#S3.SS5.p3.1),[§7](https://arxiv.org/html/2607.10194#S7.SS0.SSS0.Px3.p1.1)\.
- E\. López\-Rubio \(2025\)Representation of the structure of graphs by sequences of instructions\.arXiv preprint\.Note:arXiv:2512\.10429v2Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p3.6),[§2\.4](https://arxiv.org/html/2607.10194#S2.SS4.p2.3)\.
- Q\. F\. Lotito, M\. Contisciani, C\. De Bacco, L\. D\. Gaetano, L\. Gallo, A\. Montresor, F\. Musciotto, N\. Ruggeri, and F\. Battiston \(2023\)Hypergraphx: a library for higher\-order network analysis\.Journal of Complex Networks11\(3\),pp\. cnad019\.External Links:[Document](https://dx.doi.org/10.1093/comnet/cnad019)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p1.1)\.
- E\. M\. Luks \(1999\)Hypergraph isomorphism and structural equivalence of Boolean functions\.InProceedings of the Thirty\-First Annual ACM Symposium on Theory of Computing \(STOC\),pp\. 652–658\.External Links:[Document](https://dx.doi.org/10.1145/301250.301427)Cited by:[§2\.2](https://arxiv.org/html/2607.10194#S2.SS2.p1.5)\.
- B\. D\. McKay and A\. Piperno \(2014\)Practical graph isomorphism, II\.Journal of Symbolic Computation60,pp\. 94–112\.External Links:[Document](https://dx.doi.org/10.1016/j.jsc.2013.09.003)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.1](https://arxiv.org/html/2607.10194#S2.SS1.p1.1),[§6](https://arxiv.org/html/2607.10194#S6.SS0.SSS0.Px3.p1.2),[§6](https://arxiv.org/html/2607.10194#S6.SS0.SSS0.Px4.p1.2)\.
- B\. D\. McKay \(1981\)Practical graph isomorphism\.Congressus Numerantium30,pp\. 45–87\.Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.1](https://arxiv.org/html/2607.10194#S2.SS1.p1.1),[§6](https://arxiv.org/html/2607.10194#S6.SS0.SSS0.Px3.p1.2)\.
- D\. Neuen and P\. Schweitzer \(2017\)Benchmark graphs for practical graph isomorphism\.In25th Annual European Symposium on Algorithms \(ESA\),LIPIcs, Vol\.87,pp\. 60:1–60:14\.External Links:[Document](https://dx.doi.org/10.4230/LIPIcs.ESA.2017.60)Cited by:[§2\.1](https://arxiv.org/html/2607.10194#S2.SS1.p1.1)\.
- D\. Neuen \(2022\)Hypergraph isomorphism for groups with restricted composition factors\.ACM Transactions on Algorithms18\(3\)\.External Links:[Document](https://dx.doi.org/10.1145/3527667)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.2](https://arxiv.org/html/2607.10194#S2.SS2.p1.5)\.
- P\. Schweitzer and D\. Wiebking \(2019\)A unifying method for the design of algorithms canonizing combinatorial objects\.InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing \(STOC\),pp\. 1247–1258\.External Links:[Document](https://dx.doi.org/10.1145/3313276.3316338)Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.2](https://arxiv.org/html/2607.10194#S2.SS2.p1.5),[§6](https://arxiv.org/html/2607.10194#S6.SS0.SSS0.Px4.p1.2)\.
- D\. Weininger \(1988\)SMILES, a chemical language and information system\. 1\. Introduction to methodology and encoding rules\.Journal of Chemical Information and Computer Sciences28\(1\),pp\. 31–36\.External Links:[Document](https://dx.doi.org/10.1021/ci00057a005)Cited by:[§2\.4](https://arxiv.org/html/2607.10194#S2.SS4.p1.1)\.
- B\. Weisfeiler and A\. Leman \(1968\)The reduction of a graph to canonical form and the algebra which appears therein\.Nauchno\-Technicheskaya Informatsiya2\(9\),pp\. 12–16\.Cited by:[§2\.3](https://arxiv.org/html/2607.10194#S2.SS3.p1.4)\.
- K\. Xu, W\. Hu, J\. Leskovec, and S\. Jegelka \(2019\)How powerful are graph neural networks?\.InInternational Conference on Learning Representations,Note:arXiv:1810\.00826Cited by:[§2\.3](https://arxiv.org/html/2607.10194#S2.SS3.p1.4)\.
- J\. You, R\. Ying, X\. Ren, W\. L\. Hamilton, and J\. Leskovec \(2018\)GraphRNN: generating realistic graphs with an auto\-regressive model\.InProceedings of the 35th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.80,pp\. 5708–5717\.Cited by:[§2\.4](https://arxiv.org/html/2607.10194#S2.SS4.p1.1)\.
- D\. Zhang, C\. Zhang, Y\. Rao, Q\. Li, and C\. Zhu \(2025\)Improved expressivity of hypergraph neural networks through high\-dimensional generalized Weisfeiler\-Leman algorithms\.InProceedings of the 42nd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.267\.Cited by:[§1](https://arxiv.org/html/2607.10194#S1.p2.6),[§2\.3](https://arxiv.org/html/2607.10194#S2.SS3.p1.4)\.