用字符串编码超图结构,实现原生同构判定。
Instruction Set and Language for Hypergraphs

- 将超图转为指令字符串,通过虚拟机解析还原
- 生成的规范字符串可准确判断超图同构,正确率100%
- 比传统方法快数百倍,适合大规模超图分析
我们提出IsalHG,一种将任意有限连通超图(有界超边度数)表示为紧凑指令字母表Σ_HG上字符串的方法。编码由一个包含稀疏超图、节点引用的循环双向链表及k个遍历指针的虚拟机执行,其中k为超边度数上限。指令用于移动指针或插入超边及新节点。所有Σ_HG上的字符串均能解码为有效超图,字母表封闭。贪心算法h2s可将任意连通超图编码为字符串;以字典序最大结构元组为起点的回溯变体生成规范字符串w*,我们猜想其为完整的同构不变量。规范字符串相等即原生判定超图同构,无需转化为利维关联图再调用图同构引擎。我们在150个随机均匀超图和命名组合设计上验证了往返性质s2h(h2s(H)) ≅ H。在600个同构判定中,四种方法(nauty, Traces, bliss + 2-色利维图,以及本方法)全部一致,支持完备性猜想。在实际耗时上,利维基线方法在所有测试单元中均快3至5个数量级(几何平均比值311×至117,672×),结果已实测报告。本文贡献包括表示框架、规范性完备性猜想,以及首个原生与利维方法的基准对比。
原文摘要 · Abstract (English)
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 $Σ_{\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 $Σ_{\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。