Instruction Set and Language for Hypergraphs
Quick Answer
This paper shows that The IsalHG method encodes finite connected hypergraphs into strings using a compact instruction set, achieving hypergraph isomorphism natively.
Quick Take
It outperforms traditional Levi graph methods by 311x to 117,672x in benchmark tests across 600 isomorphism verdicts, contributing a new representation framework and a conjecture of canonical completeness.
Key Points
- IsalHG encodes hypergraphs as strings over a compact alphabet Σ_HG.
- The method includes a virtual machine with a sparse hypergraph and CDLL.
- Canonical string equality determines hypergraph isomorphism without Levi graph reduction.
- Benchmarks show IsalHG outperforms nauty, Traces, and bliss by significant margins.
- The study verifies round-trip property on 150 random hypergraphs.
Paper Resources
📖 Reader Mode
~2 min readAbstract: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.
| Subjects: | Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Programming Languages (cs.PL) |
| MSC classes: | 68T10 |
| ACM classes: | I.2 |
| Cite as: | arXiv:2607.10194 [cs.CL] |
| (or arXiv:2607.10194v1 [cs.CL] for this version) | |
| https://doi.org/10.48550/arXiv.2607.10194 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Mario Pascual-González [view email]
[v1]
Sat, 11 Jul 2026 08:15:52 UTC (21,926 KB)
— Originally published at arxiv.org
Want this in your inbox every morning?
Daily brief at your local 8am — bilingual EN/中文, free.
More from arXiv cs.CL
See more →TriAgent: Divergence-Aware Committees for Cost-Efficient Financial Sentiment Analysis
TriAgent introduces a cost-efficient multi-agent system for financial sentiment analysis, combining VADER, FinBERT, and Qwen2.5. It achieves an F1 score of ~0.87 with significant savings of $9.3M/year at a 10M-user scale compared to GPT-4o-mini, while also detecting hallucinations with an AUC of 0.90.