# Instruction Set and Language for Hypergraphs

arXiv: https://arxiv.org/abs/2607.10194 · HTML: https://mlsanity.com/paper/2607.10194/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 33 references that are in the map.
- First posted on arXiv 11 Jul 2026.

## Builds on (most cited first, 12 of 12)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Hypergraph Isomorphism Computation](https://mlsanity.com/paper/2307.14394/) (2023)
- [Hypergraphx: a library for higher-order network analysis](https://mlsanity.com/paper/2303.15356/) (2023)
- [Benchmark Graphs for Practical Graph Isomorphism](https://mlsanity.com/paper/1705.03686/) (2017)
- [Representation of the structure of graphs by sequences of instructions](https://mlsanity.com/paper/2512.10429/) (2025)
- [A unifying method for the design of algorithms canonizing combinatorial objects](https://mlsanity.com/paper/1806.07466/) (2018)
- [Hypergraph Isomorphism for Groups with Restricted Composition Factors](https://mlsanity.com/paper/2002.06997/) (2020)
- [Instruction set for the representation of graphs](https://mlsanity.com/paper/2603.11039/) (2026)
- [Instruction Set and Language for Symbolic Regression](https://mlsanity.com/paper/2603.21836/) (2026)

## Abstract (arXiv)

We present IsalHG, a method for representing the structure of any finite, connected hypergraph of bounded hyperedge arity as a string over a compact instruction alphabet SigmaHG. 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 SigmaHG decodes to a valid hypergraph; the alphabet is closed. A greedy HypergraphToString (h2s) algorithm encodes any connected hypergraph into a string; a backtracking variant seeded at nodes of lexicographically maximal structural tuple produces a canonical string w*, which we conjecture to be a complete isomorphism invariant. Canonical-string equality then decides hypergraph isomorphism natively, without the standard reduction to the Levi incidence graph followed by a graph-isomorphism engine. We verify the round-trip property s2h(h2s(H)) cong H on 150 connected random uniform hypergraphs and on named combinatorial designs, and we benchmark the canonical algorithm against the three practically available exact baselines -- nauty, Traces, and bliss operating on the 2-coloured Levi graph -- across a (n, c) grid with ten seeds per cell. All four methods agree on every one of 600 isomorphism verdicts, consistent with the completeness conjecture. On wall-clock time the Levi baselines dominate every tested cell by three to five orders of magnitude (geometric-mean ratio 311× to 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.