超图的指令集与语言

# 超图的指令集与语言
来源：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) 马拉加大学 计算机语言与计算机科学系 Bulevar Louis Pasteur, 35 29071 马拉加, 西班牙 mpascual@uma\.es &[![[Uncaptioned image]](https://arxiv.org/html/2607.10194v1/x2.png)Ezequiel López\-Rubio](https://orcid.org/0000-0001-8231-5687) 马拉加大学 计算机语言与计算机科学系 Bulevar Louis Pasteur, 35 29071 马拉加, 西班牙 ezeqlr@lcc\.uma\.es 通讯作者\. ITIS 软件学院\. 马拉加大学\. C/ Arquitecto Francisco Peñalosa 18, 29010, 马拉加, 西班牙

###### 摘要

我们提出 **IsalHG**，一种将任何有限、连通且超边元数有界的超图的结构表示为紧凑指令字母表 \(\Sigma_{\mathrm{HG}}\) 上的字符串的方法。该编码由一个小的虚拟机执行，该虚拟机包含一个稀疏超图、一个节点引用的循环双链表 (CDLL) 以及 \(k\) 个遍历指针，其中 \(k\) 是超边元数的上界。指令要么将指针在 CDLL 中移动，要么在超图中插入一条超边（可选地包含新节点）。\(\Sigma_{\mathrm{HG}}\) 上的每个字符串都解码成一个有效的超图；该字母表是封闭的。一个贪心的 *HypergraphToString* (\(\mathrm{H2S}\)) 算法能对任何连通超图编码成字符串；一种从字典序最大的结构元组节点开始进行回溯的变体，能产生一个*规范字符串* \(w^*_H\)，我们猜想它是一个完全的同构不变量。那么，规范字符串相等性即可直接在该超图领域内判定超图同构，无需标准的归约到 Levi 关联图再经由图同构引擎的步骤。我们在 150 个连通随机均匀超图和已命名的组合设计上验证了循环性质 \(\mathrm{S2H}(\mathrm{H2S}(H)) \cong H\)，并在一个 \((n, c)\) 网格（每个单元十个种子）上，将规范算法与三种实际可用的精确基线——在二色 Levi 图上运行的 nauty、Traces 和 bliss——进行了基准测试。所有四种方法在 600 个同构判定中的每一个上都达成一致，这与完全性猜想相符。在挂钟时间上，Levi 基线在测试的每个单元上均以三到五个数量级（几何平均比率从 \(311\times\) 到 \(117,672\times\)）的优势胜出，我们如实报告了这一结果。我们贡献了该表示框架、一个关于规范完全性的猜想，以及超图同构的首次原生对比 Levi 基准测试。

*关键词* 超图表示 \(\cdot\) 超图同构 \(\cdot\) 规范形式 \(\cdot\) 指令序列 \(\cdot\) 虚拟机 \(\cdot\) Levi 图

## 1 引言

超图将图推广，它允许一条边连接任意数量的节点而不仅限于两个。它们是群体交互的自然模型：合著团队、化学反应、蛋白质复合物、社交接触事件以及立法联盟都是一组参与者，而非成对出现 (Berge, 1973 (https://arxiv.org/html/2607.10194#bib.bib48); Benson et al., 2018 (https://arxiv.org/html/2607.10194#bib.bib69); Battiston et al., 2020 (https://arxiv.org/html/2607.10194#bib.bib49))。随着高阶网络分析的标准软件的出现 (Landry et al., 2023 (https://arxiv.org/html/2607.10194#bib.bib67); Lotito et al., 2023 (https://arxiv.org/html/2607.10194#bib.bib68))，基本的表示问题在超图层面重新浮现：如何编码超图的结构，使得结构相同的对象可以如此被识别？这便是超图同构问题，它构成了组合设计分类 (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))、超图语料库的去重以及高阶机器学习中结构表达能力评估的基础 (Feng et al., 2024 (https://arxiv.org/html/2607.10194#bib.bib61))。

解决超图同构问题的既定精确路径是归约。超图 \(H\) 被翻译为其 Levi 关联图 \(B(H)\)：一个二部图，其中 \(H\) 的每个节点对应一个顶点，每个超边对应一个顶点，并且当且仅当一个节点属于某个超边时才有一条边 (Berge, 1973 (https://arxiv.org/html/2607.10194#bib.bib48))。对两个顶点类进行染色可使该翻译具有保真性，然后图规范标号引擎——nauty 或 Traces (McKay, 1981 (https://arxiv.org/html/2607.10194#bib.bib50); McKay and Piperno, 2014 (https://arxiv.org/html/2607.10194#bib.bib51))，或 bliss (Junttila and Kaski, 2007 (https://arxiv.org/html/2607.10194#bib.bib52))——在归约后的图上判定同构。这个流程是精确且成熟的；据我们所知，它是目前作为可用软件存在的唯一精确超图同构流程：像 SageMath 和 GAP 这样的设计理论系统在内部通过 nauty 进行它们的关联结构同构测试。然而，这个流程并非*原生*的。归约将顶点集从 \(n\) 膨胀到 \(n+m\)，其中 \(m\) 是超边的数量，并且算法在进行任何同构推理之前就丢弃了超图。迄今提出的原生替代方案属于 Weisfeiler–Leman 族中基于精化的不变量，这些已被证明是不完全的 (Feng et al., 2024 (https://arxiv.org/html/2607.10194#bib.bib61); Zhang et al., 2025 (https://arxiv.org/html/2607.10194#bib.bib62))，以及群论精确算法，这些仍停留在理论层面 (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))。

本文介绍 **IsalHG**（超图的指令集与语言），一种原生的超图顺序表示方法。我们将超图编码为指令字母表 \(\Sigma_{\mathrm{HG}}\) 上的字符串，并使用一个小型虚拟机来执行它，该虚拟机包含一个稀疏超图、一个节点引用的循环双链表 (CDLL) 以及 \(k\) 个遍历指针，其中 \(k\) 是超边元数的上界。\(\Sigma_{\mathrm{HG}}\) 上的每个字符串都解码成一个有效的超图。一个贪心的 HypergraphToString 算法 (\(\mathrm{H2S}\)) 能编码任何连通超图；一种从最大结构元组节点开始进行回溯的变体能产生规范字符串 \(w^*_H\)，我们猜想它是一个完全的同构不变量。根据这个猜想，规范字符串相等性即可在超图领域内判定超图同构。IsalHG 是指令集表示家族的第三个成员，前两个分别是用于有限简单图的 IsalGraph (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)) 和用于符号回归的有标号有向无环图的 IsalSR (Lopez\-Rubio and Pascual\-Gonzalez, 2026a (https://arxiv.org/html/2607.10194#bib.bib72))。

我们做出三项贡献。首先，我们详细规定了字母表、虚拟机以及 \(\mathrm{S2H}\)/\(\mathrm{H2S}\) 算法对，并论证了设计决策。其次，我们作为明确的猜想陈述了循环性质和规范完全性，非正式地讨论了双向推理，并将形式化证明留待一篇专门的理论论文。第三，我们报告了首个针对超图的原生规范字符串方法与 Levi 路径的直接基准测试：在包含 \(n \in \{8, \dots, 25\}\) 个节点的 150 个连通随机均匀超图上，循环性质在每一个实例中都成立，所有四种方法（IsalHG、nauty、Traces、bliss）在所有 600 个同构判定上达成一致，并且 Levi 基线在挂钟时间上以三到五个数量级优于当前的规范算法。我们按实测报告了运行时差距；我们描述了原生编码相对于归约的位置，并且不声称其优于归约。

本文组织如下。第2节 (https://arxiv.org/html/2607.10194#S2) 将 IsalHG 与精确、近似和顺序的先前工作进行了比较。第3节 (https://arxiv.org/html/2607.10194#S3) 定义了字母表、虚拟机、两种转换算法以及所猜想的性质。第4节 (https://arxiv.org/html/2607.10194#S4) 描述了数据队列和实验方案。第5节 (https://arxiv.org/html/2607.10194#S5) 报告了循环性、一致性和运行时的结果，第6节 (https://arxiv.org/html/2607.10194#S6) 对其进行了讨论。第7节 (https://arxiv.org/html/2607.10194#S7) 进行了总结。

## 2 相关工作

与 IsalHG 相关的先前工作分为四个方向：通过 Levi 归约处理超图的实用精确图规范标号工具（§2.1 (https://arxiv.org/html/2607.10194#S2.SS1)）、仅存在于理论中的精确超图同构算法（§2.2 (https://arxiv.org/html/2607.10194#S2.SS2)）、原生但不完全的 Weisfeiler–Leman 风格超图不变量（§2.3 (https://arxiv.org/html/2607.10194#S2.SS3)）以及组合结构的顺序编码（§2.4 (https://arxiv.org/html/2607.10194#S2.SS4)）。第一个方向提供了我们的基线；第二和第三个方向解释了为何没有其他基线可用；第四个方向包含了 IsalHG 所扩展的表示传统。

### 2.1 精确图规范标号与 Levi 归约

实用的图同构主要由构建在个体化-精化 (IR) 范式之上的规范标号工具主导：颜色精化划分顶点，个体化在精化无法分割的单元上进行分支，这些分支上的搜索树产生一个规范标号。nauty 引入了这种架构的现代形式 (McKay, 1981 (https://arxiv.org/html/2607.10194#bib.bib50))；其姊妹算法 Traces 用广度优先策略和不同的单元选择器取代了深度优先遍历，这在高度对称的输入上效果显著；两者一同维护和分发 (McKay and Piperno, 2014 (https://arxiv.org/html/2607.10194#bib.bib51))。bliss 为大规模稀疏图优化了相同的范式 (Junttila and Kaski, 2007 (https://arxiv.org/html/2607.10194#bib.bib52))。这些引擎在实践中能判定拥有数百万顶点的图的同构；所有三种引擎的困难实例现在都有很好的描述 (Neuen and Schweitzer, 2017 (https://arxiv.org/html/2607.10194#bib.bib53))。在理论方面，图同构在拟多项式时间内可判定 (Babai, 2016 (https://arxiv.org/html/2607.10194#bib.bib17))，但 IR 引擎（尽管存在指数级最坏情况）仍然是实际标准。

超图通过一个归约进入这个生态系统。具有 \(n\) 个节点和 \(m\) 条超边的超图 \(H\) 的 Levi 图 \(B(H)\) 是在 \(n+m\) 个顶点上的二部关联图，其中每个超边顶点与其包含的节点的顶点相邻 (Berge, 1973 (https://arxiv.org/html/2607.10194#bib.bib48))。用两种不同的颜色对节点-顶点和超边-顶点进行着色使得归约具有保真性：两个超图同构当且仅当它们的着色 Levi 图同构。据我们所知，每个精确判定超图或关联结构同构的软件系统都遵循这条路线。SageMath 的 `IncidenceStructure.is_isomorphic` 和 GAP 的设计理论包内部调用 nauty，并且设计理论的分类工作——例如对 11,084,874,829 个 19 阶 Steiner 三元组的枚举——结合了基于 nauty 的同构剔除与领域特定的不变量 (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))。因此，对于超图同构，当前可操作精确标准是 Levi 归约加上上述三个引擎之一，任何原生方案都必须与那个流程进行对比测量。

### 2.2 理论上的精确超图同构

超图同构与图同构在多项式时间内等价：Levi 归约将超图映射到着色图，而图是二元超图。然而，理论文献仍然寻求其复杂度尊重超图参数（而非归约膨胀后的规模 \(n+m\)）的算法。Luks (1999 (https://arxiv.org/html/2607.10194#bib.bib54)) 给出了一种算法，其复杂度随节点数指数增长，但随超边数多项式增长。Babai 和 Codenotti (2008 (https://arxiv.org/html/2607.10194#bib.bib55)) 在中等指数时间 \(\exp(\tilde{O}(k^{2}\sqrt{n}))\) 内处理有界秩 \(k\) 的超图。Arvind 等人 (2015 (https://arxiv.org/html/2607.10194#bib.bib56)) 表明，着色超图同构在最大颜色类规模上是固定参数可处理的。Neuen (2022 (https://arxiv.org/html/2607.10194#bib.bib57)) 获得了当前最佳界 \((n+m)^{O((\log d)^{c})}\)，适用于具有受限复合因子的群，同时指出对于超边丰富的输入，对 \(m\) 的依赖性仍远非最优。Schweitzer 和 Wiebking (2019 (https://arxiv.org/html/2607.10194#bib.bib58)) 提出了一个在遗传有限集上的统一规范框架，该框架在与群论算法相同的渐近预算内对超图进行规范化。

这里相关的点是实际的，而非渐近的：这五种算法都没有公开的实现。它们理论上精确并且在精神上是原生的，但无法运行。因此，实用的精确超图同构工具箱中恰好包含由 nauty、Traces 或 bliss 驱动的 Levi 归约；第4节 (https://arxiv.org/html/2607.10194#S4) 将仅与此三种引擎进行基准测试。

### 2.3 Weisfeiler–Leman 不变量与超图学习

另一条独立的工作线通过 Weisfeiler 和 Leman 风格的迭代颜色精化计算同构*不变量* (Weisfeiler and Leman, 1968 (https://arxiv.org/html/2607.10194#bib.bib16))。这种不变量是单向的：不同的值证明非同构，但相等的值不能证明同构，并且对于任何固定的精化维度 \(k\)，都存在一些非同构图对是 \(k\) 维测试无法区分的 (Cai et al., 1992 (https://arxiv.org/html/2607.10194#bib.bib59))。在超图上，颜色精化精确刻画了 Berge-无环模式的同态计数 (Böker, 2019 (https://arxiv.org/html/2607.10194#bib.bib60))，这严格弱于同构。Feng 等人 (2024 (https://arxiv.org/html/2607.10194#bib.bib61)) 引入了一种超图 Weisfeiler–Leman 精化以及 HIC 工具，这是我们所知唯一的生产级原生超图指纹识别工具；他们自己的图 3 展示了一对非同构超图，其精化产生了碰撞，且作者并未描述失效家族。Zhang 等人 (2025 (https://arxiv.org/html/2607.10194#bib.bib62)) 将构造推广到 \(k\) 维层次结构并证明其严格性——每一层都能分离前一层次无法区分的对——代价以 \(O(h \cdot k \cdot n^{k+1})\) 增长，因此在任何可承受的层级上都无法达到完全性。核方法继承了同样的上限：Bai 等人 (2014 (https://arxiv.org/html/2607.10194#bib.bib63)) 基于有向线图的同构测试构建了一个超图核，在任何比较发生之前就将超图转换为图。这些方法驱动了成功的超图学习架构，