Paper deep dive
Instruction Set and Language for Hypergraphs
Mario Pascual-Gonzalez, Ezequiel Lopez-Rubio
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/14/2026, 5:57:31 AM
Summary
The paper introduces IsalHG, a native sequential representation framework for hypergraphs that encodes them as strings over a compact instruction alphabet executed by a virtual machine. It proposes a greedy encoding algorithm (H2S) and a backtracking variant to generate a canonical string, conjectured to be a complete isomorphism invariant. The authors benchmark IsalHG against established graph isomorphism tools (nauty, Traces, bliss) that operate on the Levi incidence graph reduction. Results show perfect agreement on isomorphism verdicts across 600 test cases, though the Levi-based baselines are significantly faster (3-5 orders of magnitude). The work contributes a novel hypergraph representation, a canonical completeness conjecture, and the first direct native-versus-reduction benchmark for hypergraph isomorphism.
Entities (10)
Relation Signals (12)
IsalHG → benchmarkedagainst → nauty
confidence 95% · benchmark the canonical algorithm against the three practically available exact baselines -- nauty, Traces, and bliss
IsalHG → benchmarkedagainst → bliss
confidence 95% · benchmark the canonical algorithm against the three practically available exact baselines -- nauty, Traces, and bliss
IsalHG → benchmarkedagainst → Traces
confidence 95% · benchmark the canonical algorithm against the three practically available exact baselines -- nauty, Traces, and bliss
Traces → operateson → Levi graph
confidence 95% · nauty, Traces, and bliss operating on the 2-coloured Levi graph
nauty → operateson → Levi graph
confidence 95% · nauty, Traces, and bliss operating on the 2-coloured Levi graph
bliss → operateson → Levi graph
confidence 95% · nauty, Traces, and bliss operating on the 2-coloured Levi graph
Levi graph → reduces → Hypergraph isomorphism
confidence 95% · The established exact route to hypergraph isomorphism is a reduction. The hypergraph H is translated into its Levi incidence graph
Canonical string → decides → Hypergraph isomorphism
confidence 90% · Canonical-string equality then decides hypergraph isomorphism natively
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We present IsalHG, a method for representing the structure of any finite, connected hypergraph of bounded hyperedge arity as a string over a compact instruction alphabet $\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, and $k$ traversal pointers, where $k$ bounds the hyperedge arity. Instructions either move a pointer through the CDLL or insert a hyperedge, optionally together with new nodes, into the hypergraph. Every string over $\Sigma_{\mathrm{HG}}$ decodes to a valid hypergraph; the alphabet is closed. A greedy \emph{HypergraphToString} (h2s) algorithm encodes any connected hypergraph into a string; a backtracking variant seeded at nodes of lexicographically maximal structural tuple produces a \emph{canonical string} $w^{*}$, which we conjecture to be a complete isomorphism invariant. Canonical-string equality then decides hypergraph isomorphism natively, without the standard reduction to the Levi incidence graph followed by a graph-isomorphism engine. We verify the round-trip property $s2h(h2s(H)) \cong H$ on 150 connected random uniform hypergraphs and on named combinatorial designs, and we benchmark the canonical algorithm against the three practically available exact baselines -- nauty, Traces, and bliss operating on the 2-coloured Levi graph -- across a $(n, c)$ grid with ten seeds per cell. All four methods agree on every one of 600 isomorphism verdicts, consistent with the completeness conjecture. On wall-clock time the Levi baselines dominate every tested cell by three to five orders of magnitude (geometric-mean ratio $311\times$ to $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.
Tags
Links
- Source: https://arxiv.org/abs/2607.10194v1
- Canonical: https://arxiv.org/abs/2607.10194v1
Trouble viewing inline? Open PDF directly →
Full Text
62,151 characters extracted from source content.
Expand or collapse full text
Instruction Set and Language for Hypergraphs 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 & 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 Corresponding author. ITIS Software. Universidad de Málaga. C/ Arquitecto Francisco Peñalosa 18, 29010, Málaga, Spain Abstract We present IsalHG, a method for representing the structure of any finite, connected hypergraph of bounded hyperedge arity as a string over a compact instruction alphabet ΣHG _HG. The encoding is executed by a small virtual machine comprising a sparse hypergraph, a circular doubly-linked list (CDLL) of node references, and k traversal pointers, where k bounds the hyperedge arity. Instructions either move a pointer through the CDLL or insert a hyperedge, optionally together with new nodes, into the hypergraph. Every string over ΣHG _HG decodes to a valid hypergraph; the alphabet is closed. A greedy HypergraphToString (H2SH2S) 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 property S2H(H2S(H))≅HS2H(H2S(H)) H on 150 connected random uniform hypergraphs and on named combinatorial designs, and we benchmark the canonical algorithm against the three practically available exact baselines — nauty, Traces, and bliss operating on the 2-coloured Levi graph — across a (n,c)(n,c) grid with ten seeds per cell. All four methods agree on every one of 600 isomorphism verdicts, consistent with the completeness conjecture. On wall-clock time the Levi baselines dominate every tested cell by three to five orders of magnitude (geometric-mean ratio 311×311× to 117,672×117,672×), 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 ⋅· hypergraph isomorphism ⋅· canonical form ⋅· instruction sequences ⋅· virtual machine ⋅· Levi graph 1 Introduction 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; Benson et al., 2018; Battiston et al., 2020). As standard software for higher-order network analysis has emerged (Landry et al., 2023; Lotito et al., 2023), 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; Colbourn and Dinitz, 2007), the deduplication of hypergraph corpora, and the assessment of structural expressivity in higher-order machine learning (Feng et al., 2024). The established exact route to hypergraph isomorphism is a reduction. The hypergraph H is translated into its Levi incidence graph B(H)B(H): a bipartite graph with one vertex per node of H, one vertex per hyperedge, and an edge whenever a node belongs to a hyperedge (Berge, 1973). Colouring the two vertex classes makes the translation faithful, and a graph canonical-labelling engine — nauty or Traces (McKay, 1981; McKay and Piperno, 2014), or bliss (Junttila and Kaski, 2007) — 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 from n to n+mn+m, where m is 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 (Feng et al., 2024; Zhang et al., 2025), and group-theoretic exact algorithms, which remain theoretical (Babai and Codenotti, 2008; Neuen, 2022; Schweitzer and Wiebking, 2019). This paper introduces IsalHG (Instruction Set and Language for Hypergraphs), a native sequential representation of hypergraphs. We encode a hypergraph as a string over the instruction alphabet ΣHG _HG and execute it with a small virtual machine comprising a sparse hypergraph, a circular doubly-linked list of node references, and k traversal pointers, where k bounds the hyperedge arity. Every string over ΣHG _HG decodes to a valid hypergraph. A greedy HypergraphToString algorithm (H2SH2S) encodes any connected hypergraph; a backtracking variant seeded at nodes of maximal structural tuple computes a canonical string wH∗w^*_H, which we conjecture to be a complete isomorphism invariant. Under this conjecture, canonical-string equality decides hypergraph isomorphism within the hypergraph domain. IsalHG is the third member of an instruction-set representation family, after IsalGraph for finite simple graphs (López-Rubio, 2025; Lopez-Rubio and Pascual-Gonzalez, 2026b) and IsalSR for the labelled directed acyclic graphs of symbolic regression (Lopez-Rubio and Pascual-Gonzalez, 2026a). We make three contributions. First, we specify the alphabet, the virtual machine, and the S2HS2H/H2SH2S 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 spanning n∈8,…,25n∈\8,…,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 positions IsalHG against exact, approximate, and sequential prior work. Section 3 defines the alphabet, the virtual machine, both conversion algorithms, and the conjectured properties. Section 4 describes the data cohort and the experimental protocol. Section 5 reports the round-trip, agreement, and runtime results, which Section 6 discusses. Section 7 concludes. 2 Related work Prior work relevant to IsalHG falls into four strands: the practical exact graph canonical-labelling tools that reach hypergraphs through the Levi reduction (§2.1), exact hypergraph isomorphism algorithms that exist only in theory (§2.2), Weisfeiler–Leman-style hypergraph invariants that are native but incomplete (§2.3), and sequential encodings of combinatorial structures (§2.4). The first strand supplies our baselines; the second and third explain why no other baseline is available; the fourth contains the representation tradition IsalHG extends. 2.1 Exact 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); 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). bliss refined the same paradigm for large and sparse graphs (Junttila and Kaski, 2007). 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). On the theory side, graph isomorphism is decidable in quasipolynomial time (Babai, 2016), but the IR engines, with exponential worst cases, remain the practical standard. Hypergraphs enter this ecosystem through a reduction. The Levi graph B(H)B(H) of a hypergraph H with n nodes and m hyperedges is the bipartite incidence graph on n+mn+m vertices in which each hyperedge vertex is adjacent to the vertices of the nodes it contains (Berge, 1973). 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’s IncidenceStructure.is_isomorphic and 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; Colbourn and Dinitz, 2007). 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.2 Exact 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 size n+mn+m of the reduction. Luks (1999) gave an algorithm exponential in the number of nodes but polynomial in the number of hyperedges. Babai and Codenotti (2008) handle hypergraphs of bounded rank k in moderately exponential time exp(O~(k2n)) ( O(k^2 n)). Arvind et al. (2015) showed that colored hypergraph isomorphism is fixed-parameter tractable in the maximum colour-class size. Neuen (2022) obtained the currently best bound, (n+m)O((logd)c)(n+m)^O(( d)^c) for groups with restricted composition factors, while noting that the dependence on m remains far from optimal for hyperedge-rich inputs. Schweitzer and Wiebking (2019) 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 benchmarks against those three engines and no others. 2.3 Weisfeiler–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). Such invariants are one-sided: different values certify non-isomorphism, but equal values certify nothing, and for every fixed refinement dimension k there exist non-isomorphic graph pairs the k-dimensional test cannot separate (Cai et al., 1992). On hypergraphs, colour refinement characterises exactly the homomorphism counts of Berge-acyclic patterns (Böker, 2019), which is strictly weaker than isomorphism. Feng et al. (2024) 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. Zhang et al. (2025) generalise the construction to a k-dimensional hierarchy and prove it strict — each level separates pairs the previous level collapses — at a cost that grows as O(h⋅k⋅nk+1)O(h· k· n^k+1), so completeness is unreachable at any affordable level. Kernel methods inherit the same ceiling: Bai et al. (2014) 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 (Xu et al., 2019), but they answer a different question than ours: they trade completeness for tractability, whereas IsalHG aims 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 returns to this point). 2.4 Sequential 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); SELFIES redesigned the alphabet so that every string decodes to a valid molecule (Krenn et al., 2020), the same closure property IsalHG adopts as a design requirement. Sequential graph generation models such as GraphRNN linearise graphs into edge-event sequences for learning purposes, without canonicality guarantees (You et al., 2018). Closest to our goal, Grzelak and Aßmann (2021) 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. IsalHG descends directly from two systems. IsalGraph represents 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; Lopez-Rubio and Pascual-Gonzalez, 2026b). IsalSR transfers 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!) (k!) node-numbering redundancy of the search space (Lopez-Rubio and Pascual-Gonzalez, 2026a). IsalHG generalises the machine along a third axis: from edges over exactly two nodes with two pointers to hyperedges over up to k nodes with k pointers. 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 of Grzelak and Aßmann (2021) and the two sibling systems above. 3 Methodology This section defines the IsalHG representation. We fix notation and scope (§3.1), define the instruction alphabet and the virtual machine that executes it (§3.2), present the string-to-hypergraph interpreter (§3.3) and the greedy hypergraph-to-string encoder (§3.4), and construct the canonical string together with the two properties we conjecture and validate empirically (§3.5). 3.1 Preliminaries and scope A hypergraph is a pair H=(V,E)H=(V,E) where V is a finite set of nodes and E is a set of hyperedges, each hyperedge e∈Ee∈ E being a subset of V with |e|≥2|e|≥ 2. The arity of a hyperedge is its cardinality. The primal graph of H is the simple graph on V that joins two nodes whenever some hyperedge contains both; H is connected when its primal graph is connected, and the distance dH(u,v)d_H(u,v) between two nodes is their distance in the primal graph. Two hypergraphs H1=(V1,E1)H_1=(V_1,E_1) and H2=(V2,E2)H_2=(V_2,E_2) are isomorphic, written H1≅H2H_1 H_2, when a bijection ϕ:V1→V2φ:V_1→ V_2 exists with E2=ϕ(e):e∈E1E_2=\φ(e):e∈ E_1\. Throughout the paper, input hypergraphs are finite, undirected, connected, free of duplicate hyperedges, and of arity at most a fixed parameter k≥2k≥ 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). 3.2 Instruction set and virtual machine An IsalHG string is executed by a virtual machine whose state is a tuple =(H,ℒ,p1,…,pk),S\;=\;(H,L,p_1,…,p_k), where H is the hypergraph under construction, ℒL is a circular doubly-linked list (CDLL) holding one reference per node of H, and p1,…,pkp_1,…,p_k are k traversal pointers into ℒL. The pointer count equals the arity bound k: an instruction that creates a hyperedge designates each pre-existing member through one of the leading pointers, so k pointers suffice for hyperedges of arity up to k. The initial state consists of a single node, a CDLL containing only that node, and all k pointers resting on it. The instruction alphabet ΣHG _HG contains five token families, summarised in Table 1. Movement tokens PiP_i and NiN_i advance and retreat pointer pip_i by one CDLL position. Insertion tokens Vi,jV_i,j and CiC_i create hyperedges: Vi,jV_i,j connects the i nodes under p1,…,pip_1,…,p_i to j freshly created nodes, which are spliced into ℒL immediately after p1p_1, while CiC_i connects the i nodes under p1,…,pip_1,…,p_i and creates no node. Neither insertion token moves a pointer. W does 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+3k+1,| _HG|\;=\; k(k-1)2_V_i,j\;+\; k_C_i\;+\; k_P_i\;+\; k_N_i\;+\; 1_W\;=\; k(k-1)2+3k+1, which is 1313 for the arity-3 hypergraphs of Section 4 and 7676 at the default cap k=10k=10. Table 1: The IsalHG instruction set ΣHG _HG. The machine state is (H,ℒ,p1,…,pk)(H,L,p_1,…,p_k); val(pi)val(p_i) denotes the node referenced by pointer pip_i. No instruction can fail: pointer aliasing shrinks the support of the created hyperedge, and a duplicate hyperedge turns CiC_i into a no-op. Token Constraints Effect on the state Vi,jV_i,j 1≤i,j≤k−11≤ i,j≤ k-1; i+j≤ki+j≤ k Create j new nodes u1,…,uju_1,…,u_j; insert them into ℒL immediately after p1p_1; add the hyperedge val(p1),…,val(pi)∪u1,…,uj\val(p_1),…,val(p_i)\∪\u_1,…,u_j\ to H. Pointers do not move. CiC_i 1≤i≤k1≤ i≤ k Add the hyperedge val(p1),…,val(pi)\val(p_1),…,val(p_i)\ to H; skip if that hyperedge already exists. Pointers do not move. PiP_i 1≤i≤k1≤ i≤ k Advance pip_i one position forward in ℒL. NiN_i 1≤i≤k1≤ i≤ k Retreat pip_i one position backward in ℒL. W — No operation. Proposition 3.1 (Closure). Every string w∈ΣHG∗w∈ _HG^* decodes to a valid hypergraph. Proof. Every token is executable in every reachable state. ℒL is circular and never empty, so PiP_i and NiN_i are always defined. The pointers always reference nodes of H, so the member sets built by Vi,jV_i,j and CiC_i are well defined; if several pointers alias the same node the created hyperedge simply has smaller support, and Vi,jV_i,j always contains at least one fresh node, so it never duplicates an existing hyperedge. CiC_i skips duplicates by definition, and W changes nothing. Hence execution is total and the final state contains a valid hypergraph. ∎ Four decisions shape this alphabet. First, hyperedge insertion is atomic: one Vi,jV_i,j or CiC_i token per hyperedge, so the string length decomposes into a structural part fixed by H and a traversal part (Remark 3.4). Second, the language is closed (Proposition 3.1): there are no syntactically or semantically invalid strings, the property that makes molecular alphabets such as SELFIES robust for generative use (Krenn et al., 2020) and that IsalGraph adopted for graphs (Lopez-Rubio and Pascual-Gonzalez, 2026b). 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 minimises exactly this cost. Fourth, new nodes enter ℒL next to p1p_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-op W is retained for padding and for closure of the language under single-token edits, following IsalGraph. Remark 3.2 (Labelled extension). ΣHG _HG extends to node- and hyperedge-labelled hypergraphs by parameterising the insertion tokens with label identifiers, V[ℓe;i;j;ℓ1,…,ℓj]V[ _e;i;j; _1,…, _j] and C[ℓe;i]C[ _e;i], in the two-tier style introduced by IsalSR (Lopez-Rubio and Pascual-Gonzalez, 2026a). The figures in this paper render tokens in that serialised syntax with the single trivial label 0; the mathematical treatment of labelled hypergraphs is deferred. 3.3 String-to-hypergraph conversion The interpreter S2HS2H executes the tokens of a string sequentially from the initial state and returns the final hypergraph. Algorithm 1 lists the dispatch; Figure 1 traces it on the canonical string of the Fano plane. By Proposition 3.1 the interpreter is total: it never rejects its input, which distinguishes ΣHG _HG from encodings whose decoder must validate. Algorithm 1 S2H(w,k)S2H(w,k): string-to-hypergraph interpreter. 1:string w∈ΣHG∗w∈ _HG^*, pointer count k 2:hypergraph H 3:H←H← single node u0u_0; ℒ←[u0]L←[u_0]; p1,…,pk←u0p_1,…,p_k← u_0 4:for each token t of w, in order do 5: if t=Pit=P_i then advance pip_i one position forward in ℒL 6: else if t=Nit=N_i then retreat pip_i one position backward in ℒL 7: else if t=Vi,jt=V_i,j then 8: create nodes u1,…,uju_1,…,u_j; insert them into ℒL after p1p_1 9: add hyperedge val(p1),…,val(pi)∪u1,…,uj\val(p_1),…,val(p_i)\∪\u_1,…,u_j\ to H 10: else if t=Cit=C_i then 11: e←val(p1),…,val(pi)e←\val(p_1),…,val(p_i)\ 12: if e∉E(H)e∉ E(H) then add hyperedge e to H 13: end if 14: else if t=Wt=W then do nothing 15: end if 16:end for 17:return H Example 3.3. Let k=3k=3 and w=V1,2P2C2w=V_1,2\,P_2\,C_2. Execution starts with the single node 0 and all pointers on it. V1,2V_1,2 creates nodes 11 and 22, splices them after p1p_1 so that ℒ=[0,1,2]L=[0,1,2], and adds the arity-3 hyperedge 0,1,2\0,1,2\. P2P_2 advances p2p_2 to node 11. C2C_2 adds the arity-2 hyperedge val(p1),val(p2)=0,1\val(p_1),val(p_2)\=\0,1\. The result is a hypergraph on three nodes with one triple and one pair. Figure 1: S2HS2H execution on the canonical string of the Fano plane STS(7) (1818 tokens, k=3k=3), sampled every three instructions. Top: the CDLL with the pointers p1p_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 the V/C tokens execute. Tokens are rendered in the serialised labelled syntax V[ℓe;i;j;ℓ1,…,ℓj]V[ _e;i;j; _1,…, _j] of Remark 3.2, with all labels equal to the trivial 0. 3.4 Hypergraph-to-string conversion The greedy encoder H2SH2S inverts the interpreter. Given a connected hypergraph H and a start node v0v_0, it simulates the virtual machine while maintaining a correspondence between the machine’s nodes and the nodes of H: the initial machine node corresponds to v0v_0, and every hyperedge of H is 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 the V token itself. The cost of a candidate is measured in pointer movements. A displacement tuple δ=(δ1,…,δk)∈ℤkδ=( _1,…, _k) ^k moves each pointer plp_l by |δl|| _l| CDLL positions, forward when δl>0 _l>0 and backward when δl<0 _l<0, at total cost ∑l|δl| _l| _l|. For each insertable hyperedge the encoder computes the cost-minimal displacement tuple that parks p1,…,pip_1,…,p_i on its i materialised members — candidate-driven search over the waiting hyperedges, which are far fewer than the (2|ℒ|+1)k(2|L|+1)^k displacement tuples. The winning candidate is selected by a fixed cascade: C1. Cost. Minimise the total displacement ∑l|δl| _l| _l|; among equal totals, take the lexicographically smallest (|δ1|,…,|δk|,δ1,…,δk) (| _1|,…,| _k|, _1,…, _k ). C2. Kind. Prefer V over C. C3. Token. Take the lexicographically smallest (i,j)(i,j) among V candidates, or the smallest i among C candidates. C4. Structure. Take the candidate hyperedge with the lexicographically smallest structural tuple η(e)η(e) (§3.5). C5. Backtracking. Any tie that survives C1–C4 spawns one branch per remaining candidate. In addition, when a Vi,jV_i,j token is emitted, the assignment of the j new members of e to the j insertion positions after p1p_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 the Vi,jV_i,j or CiC_i token. Algorithm 2 summarises the loop, and Figure 2 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 2 Greedy H2S(H,v0)H2S(H,v_0): hypergraph-to-string encoder. 1:connected hypergraph H of arity at most k; start node v0v_0 2:string w with S2H(w,k)≅HS2H(w,k) H (Conjecture 3.7) 3:initialise the machine on a single node corresponding to v0v_0; mark every hyperedge of H waiting 4:while waiting hyperedges remain do 5: for each insertable waiting hyperedge e do 6: compute the cost-minimal displacement δ(e)δ(e) parking p1,…,pip_1,…,p_i on the materialised members of e 7: end for 8: select (e,δ(e))(e,δ(e)) by the cascade C1–C5 9: emit the movement block of δ(e)δ(e); move the pointers 10: emit Vi,jV_i,j if e has j≥1j≥ 1 unmaterialised members, else CiC_i; execute it; extend the node correspondence; unmark e 11:end while 12:return the emitted token sequence Figure 2: Greedy H2SH2S encoding of the Fano plane STS(7), sampled every three instructions. Top: the CDLL of the simulated machine with the pointers p1p_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 emitted V/C token consumes it. The final string has 1818 tokens: 77 insertion tokens (33 V, 44 C) and 1111 movements. Remark 3.4 (String-length decomposition). The greedy encoder emits exactly one insertion token per hyperedge and no W, so for a hypergraph with m hyperedges |w|=m+∑tcost(δt),|w|\;=\;m\;+\; _tcost( _t), where the sum runs over the emission steps. Only the traversal term depends on the encoding order; minimising string length therefore reduces to minimising total pointer travel, which is what cascade rule C1 pursues locally. The node count is recovered as |V|=1+∑V-tokensj|V|=1+ _V-tokensj. For the Fano plane, |w|=7+11=18|w|=7+11=18. 3.5 Structural 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 on v0v_0. The canonical algorithm removes this dependence with a structural seed selector. For a node v and depth h≥1h≥ 1, let ξh(v)=|u∈V:dH(u,v)=h|,ξ(v)=(ξ1(v),ξ2(v),ξ3(v)), _h(v)\;=\; |\\,u∈ V:d_H(u,v)=h\,\ |, ξ(v)= ( _1(v), _2(v), _3(v) ), the number of nodes at primal distance exactly h from v, collected up to depth 33; for a hyperedge e, let η(e)=∑v∈eξ(v)η(e)= _v∈ eξ(v) componentwise. Both tuples are isomorphism-invariant because ϕφ preserves primal distances. The depth 33 is inherited from IsalGraph; whether it must grow for specific hypergraph families is an open question. Definition 3.5 (Canonical string). Tokens are ordered by their kind rank W<N<P<V<CW<N<P<V<C and then by their numeric parameters, and token sequences are compared lexicographically under this order. The canonical string of a connected hypergraph H is wH∗=lexminH2S(H,v0):v0∈argmaxlexξ(v),w^*_H\;=\;lexmin \\,H2S(H,v_0)\;:\;v_0∈ _lexξ(v)\, \, where each H2SH2S run resolves its C5 ties by exploring all branches and returning its lexicographically smallest completed string. Restricting the start nodes to the argmax of ξ is sound because an isomorphism maps maximal-ξ nodes to maximal-ξ nodes, 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 all n nodes. Example 3.6. For the Fano plane STS(7) with k=3k=3 the canonical algorithm returns the 1818-token string w∗=,,,.w^*= 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 three V1,2V_1,2 tokens materialise the six non-seed nodes and the three lines through the seed node; the four C3C_3 tokens complete the remaining lines after repositioning the pointers. Figures 2 and 1 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, and defer the formal proofs to a dedicated theoretical paper, exactly as IsalGraph and IsalSR did for their canonical claims (Lopez-Rubio and Pascual-Gonzalez, 2026b, a). Conjecture 3.7 (Round-trip fidelity). For every connected hypergraph H of arity at most k and every start node v0∈V(H)v_0∈ V(H), S2H(H2S(H,v0),k)≅H.S2H (H2S(H,v_0),k ) H. The encoder maintains, by construction, a bijection between the machine’s nodes and the visited nodes of H, 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 that S2HS2H 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 hypergraphs H1,H2H_1,H_2 of arity at most k, H1≅H2⇔wH1∗=wH2∗.H_1 H_2 w^*_H_1=w^*_H_2. The forward direction would follow from the label-blindness of the canonical search: an isomorphism ϕφ maps the maximal-ξ seeds of H1H_1 onto those of H2H_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 η is 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 by transitivity: H1≅S2H(wH1∗)=S2H(wH2∗)≅H2H_1 2H(w^*_H_1)=S2H(w^*_H_2) 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 reports the supporting evidence, with no counterexample found. Remark 3.9 (Hardness and cost). Hypergraph isomorphism is polynomial-time equivalent to graph isomorphism, so under Conjecture 3.8 computing wH∗w^*_H is at least as hard as graph isomorphism, and no polynomial-time algorithm should be expected. The concrete search of Definition 3.5 multiplies up to n seed runs by the C5 branches, whose count is bounded by the product of j!j! over the V emissions of a run; we make no worst-case claim beyond this bound and measure the cost empirically in Section 5. Remark 3.10 (Parameters). Two canonical strings are comparable only when computed with the same pointer count k; we use the maximal arity of the compared hypergraphs. Disconnected inputs are rejected — a per-component encoding with a lexicographic merge is the natural extension but is not developed here. 4 Computational experiments The experiments answer two questions: does the round-trip property of Conjecture 3.7 hold in practice, and where does the native canonical algorithm of Definition 3.5 stand, in correctness and in cost, against the Levi-reduction baselines on identical inputs. §4.1 specifies the data cohort and §4.2 the measurement protocol. 4.1 Data: connected uniform random hypergraphs All instances are drawn from the r-uniform Erdős–Rényi model: given n nodes and an inclusion probability p, each of the (nr) nr candidate hyperedges of arity r enters the hypergraph independently with probability p (Chodrow, 2020), as implemented in the XGI library (Landry et al., 2023). We parameterise density by the expected number of hyperedges per node, c, setting p=cn/(nr)p=c\,n/ nr so that [m]=cnE[m]=c\,n, and we report c as the density axis. Because the encoder requires connected input (Remark 3.10) 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,…seed,\ seed+1,000,003,\ seed+2· 1,000,003,…), 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 count n∈8,12,16,20,25n∈\8,12,16,20,25\, arity r=3r=3, and density c∈1.0,1.5,2.0c∈\1.0,1.5,2.0\, with ten seeds (seed∈0,…,9seed∈\0,…,9\) per (n,c)(n,c) cell — 150150 instances in total. Figure 3 shows how each axis deforms the instances. Arity 33 is the regime of the classical design-theory literature (Steiner triple systems are 33-uniform), and the n and c ranges were fixed in preliminary runs as the largest grid on which every method, including IsalHG, terminates within the 600600 s per-fingerprint budget on every instance; the ceiling is set by IsalHG, not by the baselines, a point Section 6 returns to. For the correctness protocol, each instance H is paired with σ(H)σ(H) for a vertex permutation σ drawn uniformly from the cell’s pinned generator, giving 150150 isomorphic pairs with a known certificate. Figure 3: The cohort axes at seed 0. 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=8 and n=25n=25 at the same density); the two right-hand panels vary the density at n=16n=16 (c=1c=1 and c=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. 4.2 Experimental setup Methods under test. Four methods compute one fingerprint per hypergraph and decide isomorphism by fingerprint equality. IsalHG computes the canonical string of Definition 3.5; the search is implemented in C++17 behind a Python interface. The three baselines translate H into its Levi graph B(H)B(H) with the standard 22-colouring (node-vertices versus hyperedge-vertices) and canonically label it with, respectively, nauty 2.8.8 through the pynauty binding, bliss 0.77 through python-igraph, and Traces through the dreadnaut interface 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 problem IsalHG solves: 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, 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 have no implementations to run. The Weisfeiler–Leman family of §2.3 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 the 600600 (method, instance) pairs we record the fingerprint wall-clock time as the median of 1010 repeated calls (time.perf_counter), its interquartile range, the peak resident-set increment of the call (getrusage(RUSAGE_SELF)), and the fingerprint length in bytes. A 600600 s 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 return true on (H,σ(H))(H,σ(H)) for each of the 150150 instances — 600600 checks in total. (i) 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. (i) 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 with S2HS2H 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, 600600 tasks in total, with 1616 GB 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. 5 Results We report the round-trip verification (§5.1), the correctness agreement across the four methods (§5.2), the wall-clock and memory characterisation (§5.3), and the fingerprint lengths (§5.4). 5.1 Round-trip verification The round-trip check passes on every tested input: all 150150 cohort instances and all five named designs satisfy S2H(wH∗,k)≅HS2H(w^*_H,k) H, with the isomorphism confirmed by nauty on the Levi graphs (Table 2). Canonical strings range from 9898 to 1,5561,556 serialised bytes over the cohort (median 174174 bytes at n=8n=8, 982982 bytes at n=25n=25). Figures 2 and 1 display one such round trip on the Fano plane: the encoder produces the 1818-token canonical string of Example 3.6, and S2HS2H decodes it back into a hypergraph isomorphic to the input. These results support Conjecture 3.7 on 155155 structurally diverse inputs; they do not prove it. Table 2: Round-trip verification. Each input is encoded to its canonical string wH∗w^*_H, decoded with S2HS2H, 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. Input n m S2H(wH∗)≅HS2H(w^*_H) H |wH∗||w^*_H| (bytes) Connected uniform ER cohort 88–2525 66–6767 150/150150/150 9898–1,5561,556 Fano plane STS(7) 77 77 yes 121121 STS(9) 99 1212 yes 227227 Cyclic STS(13), starter 0,1,4\0,1,4\ 1313 1313 yes 258258 Cyclic STS(13), starter 0,1,6\0,1,6\ 1313 1313 yes 263263 GQ(2,2) 1515 1515 yes 278278 5.2 Correctness agreement All 600600 positive-pair checks pass: on every one of the 150150 (H,σ(H))(H,σ(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 which IsalHG and 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 (n, m, degree and arity sequences), receive distinct canonical strings (Table 2). Across everything we tested, no counterexample to Conjecture 3.8 appeared. We note the limits of this evidence: the cohort is small (n≤25n≤ 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. 5.3 Runtime and memory Table 3 and Figure 4 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, between 0.0480.048 and 0.2010.201 ms per fingerprint; bliss runs within a factor of 22–44 of nauty; Traces stays at a flat ≈3≈ 3 ms, which its fitted exponent (n−0.02n^-0.02) identifies as the dreadnaut subprocess start-up floor rather than algorithmic cost. IsalHG spans 16.916.9 ms to 22.822.8 s over the same grid. The fitted growth exponents separate the regimes: n5.79n^5.79 for IsalHG (pooled over c; n6.2n^6.2 at c=2c=2 alone) against n0.93n^0.93 for nauty and n0.80n^0.80 for bliss. The per-cell geometric-mean ratio of IsalHG to the best Levi engine grows from 311×311× at the smallest, densest cell to 117,672×117,672× at (n,c)=(25,1.5)(n,c)=(25,1.5), roughly tripling with each step in n. No crossover regime appears anywhere in the tested grid, and the exponent gap implies none will appear at larger n under 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 the r=3r=3 grid, and the geometric-mean ratio of IsalHG over the best Levi engine per instance. No method timed out on any instance (600600 s budget). n c IsalHG Levi (nauty) Levi (bliss) Levi (Traces) ratio 88 1.01.0 16.916.9 0.0480.048 0.120.12 3.223.22 315×315× 88 1.51.5 21.221.2 0.0590.059 0.140.14 3.273.27 345×345× 88 2.02.0 22.322.3 0.0730.073 0.160.16 2.912.91 311×311× 1212 1.01.0 42.742.7 0.0710.071 0.170.17 3.313.31 548×548× 1212 1.51.5 44.944.9 0.0780.078 0.180.18 3.083.08 541×541× 1212 2.02.0 55.955.9 0.1000.100 0.240.24 3.303.30 592×592× 1616 1.01.0 176.7176.7 0.0880.088 0.200.20 3.203.20 1,985×1,985× 1616 1.51.5 241.5241.5 0.1110.111 0.230.23 3.063.06 2,141×2,141× 1616 2.02.0 492.3492.3 0.1290.129 0.290.29 3.463.46 4,319×4,319× 2020 1.01.0 822.0822.0 0.0990.099 0.200.20 2.722.72 7,824×7,824× 2020 1.51.5 2,039.72,039.7 0.1380.138 0.320.32 3.373.37 13,128×13,128× 2020 2.02.0 3,037.33,037.3 0.1620.162 0.350.35 3.173.17 15,934×15,934× 2525 1.01.0 6,863.56,863.5 0.1450.145 0.300.30 3.213.21 57,223×57,223× 2525 1.51.5 19,170.619,170.6 0.1760.176 0.340.34 2.922.92 117,672×117,672× 2525 2.02.0 22,786.122,786.1 0.2010.201 0.440.44 3.173.17 110,719×110,719× Figure 4: Median wall-clock per fingerprint (log scale) across the fifteen (n,c)(n,c) cells, grouped by n with c∈1,1.5,2c∈\1,1.5,2\ inside each group. Markers are medians over ten seeds with interquartile ranges; dashed lines are per-method power-law fits T≈a⋅nβT≈ a· n^β 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): the peak resident-set increment per fingerprint stays below 22 MiB 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), so its flat 0.40.4 MiB line excludes the subprocess. Figure 5: Peak resident-set increment per fingerprint (log scale) over the same grid as Figure 4. All methods stay below 22 MiB; page-granularity quantisation dominates the visible variation. The Traces series measures the parent process only. 5.4 Fingerprint length Figure 6 compares the fingerprint sizes. The canonical string is comparable in length to the serialised canonical labellings of the Levi engines: its median is 460460 bytes over the grid, between nauty (320320 bytes) and bliss (784784 bytes), while Traces’ compact graph-line format is the smallest at 8888 bytes. The fitted growth is n1.49n^1.49 for IsalHG against n1.11n^1.11 to n1.27n^1.27 for the baselines — consistent with Remark 3.4: the string pays one token per hyperedge (m=cnm=c\,n here) plus the pointer travel, which grows with the CDLL length. Fingerprint length is the one axis on which IsalHG does not trail the Levi baselines by orders of magnitude. Figure 6: Median fingerprint length in bytes (log scale) over the same grid as Figure 4, 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. 6 Discussion What the agreement establishes, and what it does not. The correctness outcome is uniform: 600600 positive-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 and 3.8, 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. 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× at (n,c)=(8,1)(n,c)=(8,1), 117,672×117,672× at (25,1.5)(25,1.5), with fitted exponents n5.79n^5.79 against n0.93n^0.93 (Figure 4). Two properties of the canonical search of Definition 3.5 account for the shape. First, the seed rule runs the greedy once per maximal-ξ node, and on near-regular random hypergraphs the maximal-ξ class is large, so the multiplier approaches n. Second, every V emission branches over the assignments of its new nodes (cascade rule C5), and the branch count compounds along the string, bounded by the product of j!j! over the V emissions (Remark 3.9). 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; McKay and Piperno, 2014; Junttila and Kaski, 2007), 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 flat 33 ms 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 below 22 MiB), 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 ξ — the design-theory practice of pre-partitioning by configuration counts (Kaski and Östergård, 2004) 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) and of the canonisation framework of Schweitzer and Wiebking (2019), 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 computes wH∗w^*_H. Scope limits. Four threats to validity delimit the claims. The grid fixes r=3r=3 and n≤25n≤ 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 from IsalHG (Remark 3.10). The timing hardware is a single CPU-partition node class, and the 600600 s budget, although never reached, caps what the grid could have explored. Finally, fingerprint length (Figure 6) is the only axis where the native encoding is presently competitive; we report it as an observation, not as a claim of advantage. 7 Conclusion Summary of contributions. This paper has introduced IsalHG, 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 through k traversal pointers, inserting hyperedges — and, through the Vi,jV_i,j tokens, new nodes — as instructions execute. We establish four points: (i) A native representation with a closed language. Every string over ΣHG _HG decodes to a valid hypergraph (Proposition 3.1), and the alphabet size grows only quadratically in the arity bound, |ΣHG|=k(k−1)/2+3k+1| _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. (i) Round-trip fidelity, verified. The greedy H2SH2S encoder and the S2HS2H interpreter invert each other up to isomorphism on every tested input: 150150 connected random uniform hypergraphs and five named designs, confirmed independently by nauty (Conjecture 3.7; Table 2). (i) Canonical completeness, conjectured and unrefuted. The canonical string wH∗w^*_H agreed with nauty, Traces, and bliss on all 600600 isomorphism verdicts of the cohort and separated the two non-isomorphic STS(13) (Conjecture 3.8); no counterexample was found anywhere in the campaign. (iv) An honest cost characterisation. On the tested grid the Levi baselines dominate wall-clock by three to five orders of magnitude (geometric-mean ratio 311×311× to 117,672×117,672×), with fitted growth n5.79n^5.79 for the current canonical search against n0.93n^0.93 for nauty. Fingerprint length is the one axis where the native encoding is already comparable (460460 versus 320320–784784 median bytes). Limitations. The two central conjectures — round-trip fidelity (Conjecture 3.7) and canonical completeness (Conjecture 3.8) — 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 with n. The encoder requires connected input, hyperedge arities are capped by the pointer count k, and the empirical evidence covers 33-uniform hypergraphs with n≤25n≤ 25 plus 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 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 that IsalGraph and IsalSR explore for their domains (Lopez-Rubio and Pascual-Gonzalez, 2026b, a). 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 V. Arvind, B. Das, J. Köbler, and S. Toda (2015) Colored hypergraph isomorphism is fixed parameter tractable. Algorithmica 71 (1), p. 120–138. External Links: Document Cited by: §2.2. L. Babai and P. Codenotti (2008) Isomorphism of hypergraphs of low rank in moderately exponential time. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), p. 667–676. External Links: Document Cited by: §1, §2.2. L. Babai (2016) Graph isomorphism in quasipolynomial time. arXiv preprint. Note: arXiv:1512.03547 Cited by: §2.1. L. Bai, P. Ren, and E. R. Hancock (2014) A hypergraph kernel from isomorphism tests. In 22nd International Conference on Pattern Recognition (ICPR), p. 3880–3885. External Links: Document Cited by: §2.3. 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 Reports 874, p. 1–92. External Links: Document Cited by: §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 Sciences 115 (48), p. E11221–E11230. External Links: Document Cited by: §1. C. Berge (1973) Graphs and hypergraphs. North-Holland, Amsterdam. Cited by: §1, §1, §2.1. J. Böker (2019) Color refinement, homomorphisms, and hypergraphs. In Graph-Theoretic Concepts in Computer Science (WG 2019), Lecture Notes in Computer Science, Vol. 11789, p. 338–350. External Links: Document Cited by: §2.3. J. Cai, M. Fürer, and N. Immerman (1992) An optimal lower bound on the number of variables for graph identification. Combinatorica 12 (4), p. 389–410. External Links: Document Cited by: §2.3. P. S. Chodrow (2020) Configuration models of random hypergraphs. Journal of Complex Networks 8 (3), p. cnaa018. External Links: Document Cited by: §4.1. C. J. Colbourn and J. H. Dinitz (Eds.) (2007) Handbook of combinatorial designs. 2nd edition, CRC Press, Boca Raton. Cited by: §1, §2.1. Y. Feng, J. Han, S. Ying, and Y. Gao (2024) Hypergraph isomorphism computation. IEEE Transactions on Pattern Analysis and Machine Intelligence 46 (5), p. 3880–3893. External Links: Document Cited by: §1, §1, §2.3. D. Grzelak and U. Aßmann (2021) A canonical string encoding for pure bigraphs. SN Computer Science 2 (4), p. 246. External Links: Document Cited by: §2.4, §2.4. T. Junttila and P. Kaski (2007) Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), p. 135–149. External Links: Document Cited by: §1, §2.1, §6. P. Kaski and P. R. J. Östergård (2004) The Steiner triple systems of order 19. Mathematics of Computation 73 (248), p. 2075–2092. External Links: Document Cited by: §1, §2.1, §6. 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 Technology 1 (4), p. 045024. External Links: Document Cited by: §2.4, §3.2. 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 Software 8 (85), p. 5162. External Links: Document Cited by: §1, §4.1. E. Lopez-Rubio and M. Pascual-Gonzalez (2026a) Instruction set and language for symbolic regression. Cited by: §1, §2.4, §3.5, Remark 3.2, §7. E. Lopez-Rubio and M. Pascual-Gonzalez (2026b) Instruction set for the representation of graphs. Cited by: §1, §2.4, §3.2, §3.5, §7. E. López-Rubio (2025) Representation of the structure of graphs by sequences of instructions. arXiv preprint. Note: arXiv:2512.10429v2 Cited by: §1, §2.4. 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 Networks 11 (3), p. cnad019. External Links: Document Cited by: §1. E. M. Luks (1999) Hypergraph isomorphism and structural equivalence of Boolean functions. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC), p. 652–658. External Links: Document Cited by: §2.2. B. D. McKay and A. Piperno (2014) Practical graph isomorphism, I. Journal of Symbolic Computation 60, p. 94–112. External Links: Document Cited by: §1, §2.1, §6, §6. B. D. McKay (1981) Practical graph isomorphism. Congressus Numerantium 30, p. 45–87. Cited by: §1, §2.1, §6. D. Neuen and P. Schweitzer (2017) Benchmark graphs for practical graph isomorphism. In 25th Annual European Symposium on Algorithms (ESA), LIPIcs, Vol. 87, p. 60:1–60:14. External Links: Document Cited by: §2.1. D. Neuen (2022) Hypergraph isomorphism for groups with restricted composition factors. ACM Transactions on Algorithms 18 (3). External Links: Document Cited by: §1, §2.2. P. Schweitzer and D. Wiebking (2019) A unifying method for the design of algorithms canonizing combinatorial objects. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), p. 1247–1258. External Links: Document Cited by: §1, §2.2, §6. D. Weininger (1988) SMILES, a chemical language and information system. 1. Introduction to methodology and encoding rules. Journal of Chemical Information and Computer Sciences 28 (1), p. 31–36. External Links: Document Cited by: §2.4. B. Weisfeiler and A. Leman (1968) The reduction of a graph to canonical form and the algebra which appears therein. Nauchno-Technicheskaya Informatsiya 2 (9), p. 12–16. Cited by: §2.3. K. Xu, W. Hu, J. Leskovec, and S. Jegelka (2019) How powerful are graph neural networks?. In International Conference on Learning Representations, Note: arXiv:1810.00826 Cited by: §2.3. J. You, R. Ying, X. Ren, W. L. Hamilton, and J. Leskovec (2018) GraphRNN: generating realistic graphs with an auto-regressive model. In Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 80, p. 5708–5717. Cited by: §2.4. 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. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267. Cited by: §1, §2.3.