点击上方“小白学视觉”，选择加"星标"或“置顶”
重磅干货，第一时间送达
题目：Hypergraph Isomorphism Computation

超图同构计算

作者：Yifan Feng; Jiashu Han; Shihui Ying; Yue Gao

摘要

同构问题在网络分析中至关重要，涉及分析低阶和高阶结构信息。图同构算法专注于结构等价性，以简化求解空间，帮助蛋白质设计、化学途径和社区检测等应用。然而，它们在捕捉复杂的高阶关系方面表现不佳，这与超图同构方法不同。传统的超图方法面临高内存使用和识别不准确等挑战，导致性能不佳。为了解决这些问题，我们引入了超图 Weisfeiler-Lehman（WL）测试算法，将 WL 测试从图扩展到超图，并开发了两个变体的超图 WL 核框架：超图 WL 子树核和超图 WL 超边核。超图 WL 子树核计算不同类型的根子树，并通过比较不同类型的根子树的数量生成给定超图的最终特征向量。子树核识别不同的根子树，而超边核则关注超边的顶点标签，增强特征向量的生成。为了实现我们的研究目标，我们精心设计了一套全面的实验，包括七个图分类数据集和十二个超图分类数据集。在图分类数据集上的结果表明，超图 WL 子树核可以达到与经典的图 Weisfeiler-Lehman 子树核相同的性能。在超图分类数据集上的结果显示，相比其他典型的基于核的方法有显著改进，这证明了所提出方法的有效性。在我们的评估中，我们提出的方法在运行时间方面优于第二好的方法，处理复杂超图结构时运行速度超过80倍。这显著的速度优势突显了我们方法在实际应用中的巨大潜力。

关键词

高阶相关性
超图
超图计算
超图同构

I. 引言

网络，作为一种典型的非规则建模工具，在许多应用中显示出了它的优势，如社交网络[1]、脑网络[2]、协作网络[3], [4]、知识网络[5]、化学途径[6]和蛋白质结构[7]。然而，现实世界中的非规则数据往往包含大量的高阶相关性，这些相关性无法通过简单的图结构来充分表示。当试图建模高阶相关性时，例如社交媒体中的群体关系[8], [17], [19]，用户-物品网络中的协作关系[9], [10], [36]或学术论文中的合著关系[21], [23]，顶点之间的复杂关系变得模糊，如图1所示。超图中的超边可以连接多个顶点，这使得超图具有超越简单图对关系建模的能力。为了分析和理解超图结构，需要一种工具来衡量不同超图或超图子结构之间的相似性，即“同构测试”。

图同构算法，如 Weisfeiler-Lehman 测试[26]和图核[31], [33], [34]，擅长提取低阶结构信息。然而，当处理超越对对连接的关系时，这些算法面临局限。在标准的 Weisfeiler-Lehman 测试中，每个顶点收集其邻近顶点的标签以创建压缩顶点标签，每个标签对应一个唯一的子树结构。然而，该算法的输出仅限于确定两个图是否相同。此外，基于该算法，提出了图核方法，用于通过连续值来衡量两个图的相似性。图核方法设计了从图结构到特征空间中向量的映射，并利用特征向量的内积来衡量图的相似性。然而，这些基于顶点到顶点标签传播的图相似性测量方法，不适用于处理如前所述的高维结构的复杂性。

随着超图结构的出现，研究人员提出了各种策略[35], [37], [38]来解决高阶结构相似性测量的问题。然而，这些方法中的大多数基本上依赖于将超图转换为传统图结构。这些间接的超图同构算法在某种程度上牺牲了超图固有的复杂结构信息。这导致了标准的不一致和繁琐的计算过程。[35]开发了一种基于采样的方法，从原始超图中提取顶点-超边序列。然而，这种方法可能导致信息丢失，并且在常见场景中（如金字塔状超图，见图5）常常失败。使用间接方法，Bai 等人[37]设计了一种基于转换的方法，通过三步将超图结构转换为低阶图结构。这种方法生成的图规模极大，使其变得不切实际（如表IV所示，当数据集中有超过3000个超图时出现内存不足错误）。

我们将 Weisfeiler-Lehman 测试从图扩展到超图，并提出了用于超图同构测试问题的超图 Weisfeiler-Lehman 测试算法。
我们证明了提出的超图 Weisfeiler-Lehman 子树核在面对图结构时可以退化为图 Weisfeiler-Lehman 子树核，并实现相同的性能。
在19个图/超图分类数据集上的广泛实验验证了所提出方法的有效性。

III. 预备知识

在本节中，我们首先介绍图/超图同构问题的背景。然后，我们简要回顾最相关的图 Weisfeiler-Lehman 核。表 I 中详细描述了符号。

A. 图/超图同构

图同构：给定两个图和，图同构测试的目标（表示为）是找到一个双射映射是否存在。映射称为同构函数，使得

然而，完全的图同构测试解决方案已被证明是一个 NP-hard 问题 [25]，因此在实践中不可行。Weisfeiler-Lehman 测试 [26]，也被称为“简单顶点细化”，是图同构测试的一个典型近似解决方案，如算法1所述。它从两个输入图和开始，关联有标签的顶点。每个顶点在每次迭代中收集其邻近顶点的标签以构建子树字符串，该字符串用于重新标记顶点。在每次迭代中，如果两个图的不同类型顶点标签的统计数据不同，算法确定这两个图不是同构的。否则，这两个图可能是同构的。

超图同构：类似地，给定两个超图和，超图同构测试的目标（表示为）是找到一个双射映射是否存在。映射称为同构函数，使得

B. 图 Weisfeiler-Lehman 核

基于图同构的 Weisfeiler-Lehman 测试，分别提出了图 Weisfeiler-Lehman 子树核 [31] 和图 Weisfeiler-Lehman 边核 [33]。这两种核方法的核心动机是将无法比较的图结构映射到特征空间中的特征向量，通过两个特征向量的内积来计算两个图之间的距离，如下所示

图 Weisfeiler-Lehman 子树核：由于每次迭代中的顶点标签对应一个唯一的子树结构，图 Weisfeiler-Lehman 子树核的简单思想是计算图中不同类型标签的数量。因此，特征函数可以定义为

其中是计数函数。是次迭代中第个子树的相应标签，是次迭代中不同子树类型的数量，最大迭代次数为。

图 Weisfeiler-Lehman 边核：此外，图 Weisfeiler-Lehman 边核计算具有相同标签端点的边匹配对，可以表示为

其中。表示一个具有两个标记顶点的边：和。

算法1：图同构的 Weisfeiler-Lehman 测试。

输入：图和，顶点和，顶点标签映射：，哈希函数，运算表示“或”。

多集标签确定。

对于，设置。
对于，为和中的每个顶点分配一个多集标签。

对每个多集进行排序。

对中的元素进行排序并转换为字符串。
将作为前缀添加到。

标签压缩。

对和中所有的字符串进行排序。
将每个字符串映射到一个新的压缩标签。

重新标记。

设置，适用于和中的所有顶点。

IV. 方法

在本节中，我们首先介绍广义的超图 Weisfeiler-Lehman 测试，称为超图 Weisfeiler-Lehman 测试。然后，我们定义基于这些测试的超图 Weisfeiler-Lehman 序列和通用超图核。在接下来的内容中，我们展示了这种核的两个实例：超图 Weisfeiler-Lehman 子树核和超图 Weisfeiler-Lehman 超边核。最后，我们从数学角度将我们的方法与图 Weisfeiler-Lehman 核进行比较。

A. 超图 Weisfeiler-Lehman 测试

基于图同构的 Weisfeiler-Lehman 测试 [26] 的概念，在本小节中，我们将其推广到超图中，如算法2所示。

Weisfeiler-Lehman 测试算法系列的核心思想是通过结合邻近顶点的标签集来增强顶点标签，并随后将这些增强的标签压缩成新表示。这些步骤重复进行，直到两个输入图的顶点标签集不同或迭代次数达到。将“邻居”定义从图扩展到超图的主要挑战在于这两种结构的固有差异。在简单图中，每条边仅连接两个顶点，定义邻居为通过边连接的顶点是直截了当的。然而，在超图中，一个超边可以连接多个顶点，这给在超图中定义邻居关系带来了复杂性。受 [19] 启发，我们采用超边的顶点邻居和顶点的超边邻居来表示超图中的复杂邻居关系。这样，超图中的复杂邻居关系在层次上得以传递，超边在顶点集与另一顶点集之间建立了联系，如图2所示。给定超图，对于每个顶点，其超边邻居和对于每个超边，其顶点邻居可以定义为

其中是超图的关联矩阵。通过定义这两个邻居函数和，我们可以轻松量化超图中超越对对相关性的复杂性。接下来，我们将介绍基于这两个邻居函数的广义超图 Weisfeiler-Lehman 算法，如算法2所示。

假设我们有两个超图和，算法的目标是测试两个输入超图是否同构。假设两个超图中的每个顶点通过顶点标签映射关联有标签。类似地，每个超边的标签由超边标签映射给出。首先，顶点的数量必须相同，否则它们不是同构的。在每次迭代中，顶点的标签通过多集 [28] 进行组织，与集合相比，从数学角度来看，多集允许其每个元素有多个实例。多集和是次迭代中的主要标识符。如果它们都相同，则两个超图是同构的；否则，它们不是。顶点/超边标签多集的初始元素通过原始顶点/超图映射初始化。每次迭代包括两个子过程：顶点标签超边标签和超边标签顶点标签。

在第一个子过程（顶点标签超边标签）中，对于每个超边，我们构建一个多集

算法2：超图同构的超图 Weisfeiler-Lehman 测试算法。

输入：超图和，顶点和，超边和，顶点标签映射：，超边标签映射，迭代次数，多集排序函数，连接多集中的元素并字符串化函数：，字符串压缩函数，连接函数将新字符串化函数与旧字符串化函数连接：，运算表示“或”。

初始化顶点标签。
初始化顶点标签。
初始化超边标签。
初始化超边标签。
while 且 do
// 每个超边收集其顶点邻居标签。
对 do
// 1. 将超边的顶点邻居标签收集到多集中。
// 2. 排序多集并字符串化。
// 3. 超边标签压缩和重新标记。
end for
// 每个顶点收集其超边邻居标签。
对 do
// 1. 将顶点的超边邻居标签收集到多集中。
// 2. 排序多集。
// 3. 顶点标签压缩和重新标记。
end for
end while
比较和输出：和是否是同构的。

B. 超图 Weisfeiler-Lehman 序列

在本小节中，我们定义了超图 Weisfeiler-Lehman 序列，并基于提出的超图 Weisfeiler-Lehman 测试算法，给出了通用超图 Weisfeiler-Lehman 核的定义。

超图 Weisfeiler-Lehman 序列：在超图 Weisfeiler-Lehman 算法的第次迭代中，我们生成两个标记函数，用于顶点，用于超边。注意，这些标记函数对于输入超图和是一致的。如果两个顶点在超图或中共享相同的标签，这表明它们具有相同的根子树。在这里，我们将每次迭代（包括其两个子过程）视为一个函数，它以相同的方式转换输入超图。经过次迭代后，我们得到一个包含个超图（包括原始超图）的序列。该序列称为超图 Weisfeiler-Lehman 序列，可以定义如下。

定义 1：给定一个超图和重标记函数

，表示第次迭代后的重标记超图。那么，超图 Weisfeiler-Lehman 序列可以定义为

其中且，这是超图的高度为的 Weisfeiler-Lehman 序列。

在定义 1 中，和从原始超图初始化。重标记函数生成上一次迭代后的重标记超图。在序列中，顶点集和超边集是相同的，而顶点和超边的标签在每次迭代中都会变化。

通用超图 Weisfeiler-Lehman 核：给定超图，我们可以通过算法 2 获得超图 Weisfeiler-Lehman 序列。为了从这些序列中生成超图嵌入以进行计算，我们定义了通用超图 Weisfeiler-Lehman 核。

定义 2：令为我们称之为基础核的任何超图核，给定两个超图和，具有次迭代的超图 Weisfeiler-Lehman 核可以定义为

其中和分别是超图和的 Weisfeiler-Lehman 序列。

定义 2 提供了基于核的超图嵌入的综合框架，能够将具有不同高度的离散根子树纳入考虑范围。当给定基础核的显式策略（例如标签类型计数）时，超图 Weisfeiler-Lehman 核将原始超图结构转换为希尔伯特空间中的向量嵌入。此嵌入表示允许完成各种任务，包括超图分类、检索和相似性测量。

定理 1：令基础核为超图上的任何正半定核。那么，相应的超图 Weisfeiler-Lehman 核是正半定的。

证明：令为与核对应的特征映射，

我们有

因此，我们有

我们可以构建一个和的组合函数。然后，我们有

由于正半定核的和是正半定核，并且是和的正半定核，因此是正半定的。

基于超图 Weisfeiler-Lehman 测试算法，我们提出了通用超图 Weisfeiler-Lehman 核，从数学角度来看，这是一个进步。通用核是一个灵活而强大的框架。它的输入是超图 Weisfeiler-Lehman 测试算法生成的标记超图序列，输出是原始超图的嵌入特征向量，可以用于许多下游任务。通用核的核心组件是核函数，它可以由任何映射函数实现，例如计算不同顶点子树、超边子树的数量，或使用加权计数策略。不同的核实现将从超图结构中捕捉不同的信息，并在不同的下游任务中取得令人满意的性能。在接下来的部分中，我们将基于通用超图 Weisfeiler-Lehman 核框架实现两个基础核实例：子树核和超边核。

C. 超图 Weisfeiler-Lehman 子树核

基于算法2和定义2，本小节介绍一个自然实例，称为超图 Weisfeiler-Lehman 子树核。由于迭代中的顶点标签压缩了一个高度为的唯一根子树，用离散标签的频率描述原始超图结构是一种直观策略。通过将 Weisfeiler-Lehman 子树核 [31] 从图推广到超图，第一个实例可以定义如下：

定义3：设和为超图。定义为在超图 Weisfeiler-Lehman 算法的第次迭代中出现的顶点标签集。设和为超图和的超图 Weisfeiler-Lehman 序列。设为超图和的原始标签集。假设所有两两不相交。没有损失一般性，假设每个是有序的。定义映射，，使得是标签在超图中出现的次数。那么，具有次迭代的两个超图和的 Weisfeiler-Lehman 子树核定义为

其中

和

D. 超图 Weisfeiler-Lehman 超边核

本小节介绍了另一个通用超图 Weisfeiler-Lehman 超边核的实例：超图 Weisfeiler-Lehman 超边核。与子树核不同，此实例计算不同类型超边的频率。由于每个超边可以连接多个顶点，我们将其视为有序集合进行比较。与之前的子树核相比，超边核可以在每次迭代中直接表示高阶连接信息。其定义如下。

定义4：设和为超图。定义为在超图 Weisfeiler-Lehman 算法的第次迭代中出现的顶点标签集。设和为超图和的超图 Weisfeiler-Lehman 序列。设为超图和的原始标签集。假设所有两两不相交。定义映射

作为在 -次迭代中的超边编码来表示超边。假设每个超边编码是一个有序顶点标签元组。定义为在 -次迭代中出现的超边编码集。没有损失一般性，假设每个和是有序的。定义映射，，使得是超图中超边编码的出现次数。那么，具有次迭代的两个超图和的 Weisfeiler-Lehman 超边核定义为

其中

和

类似地，超图 Weisfeiler-Lehman 超边核可以进一步写为

其中是 Dirac 核函数。超图 Weisfeiler-Lehman 超边核利用超边作为子树的根，并计算不同超边子树的数量以捕捉原始超图的高阶信息。显然，这种类型的核函数可以表示具有不同度数的超边，并嵌入比超图 Weisfeiler-Lehman 子树核更复杂的超图结构。

复杂性：所提出的超图 Weisfeiler-Lehman 超边核在具有次迭代的个超图上的运行时间复杂度为。是最终特征的维度，等于的总和。根据 IV-C 节，构建超图 Weisfeiler-Lehman 序列的运行时间为。对于每个超图，构建超边编码的次迭代运行时间为，等于。因此，对于个超图，构建超边编码的运行时间为。至于超边编码计数阶段，成对个超图的复杂度如（4）所示，为。因此，所有这些步骤的总运行时间为。

E. 实际计算

由于超图 Weisfeiler-Lehman 核生成的特征维度大且不确定，我们采用常用的归一化技巧 [32] 来减少训练和测试超图的特征维度。给定特定超图 Weisfeiler-Lehman 核提取的特征矩阵和，和分别表示训练超图和测试超图的数量。我们基于训练超图压缩它们，使用函数。压缩特征可以通过

和

计算出来。压缩特征和的每个条目可以计算为

其中在或范围内，分别用于训练和测试。函数可以定义为

其中表示点积和外积。是全1向量。注意，在测试超图的嵌入过程中，那些未见过的结构如根子树和超边会被丢弃。通过这种方式，训练超图和测试超图的最终特征是可比的。

F. 分析和讨论

在本小节中，我们讨论了超图 Weisfeiler-Lehman 子树核与图 Weisfeiler-Lehman 子树核、图神经网络、超图神经网络和二部图核的关系。

与图 WL 子树核的关系：在这里，我们证明了在面对简单图结构时，超图 Weisfeiler-Lehman 子树核可以退化为图 Weisfeiler-Lehman 子树核。

定理2：给定一个图，设和分别为图/超图 Weisfeiler-Lehman 子树核的压缩函数，将根字符串压缩为唯一标签。存在一个双射函数将图 Weisfeiler-Lehman 子树核的根字符串映射到超图 Weisfeiler-Lehman 核的根字符串。

证明：满射证明：在次迭代中，给定顶点，图 Weisfeiler-Lehman 子树核的压缩根字符串 [31] 为

，其中是顶点的邻居顶点集。是多集排序函数。是字符串连接操作。最后，在次迭代中，图 Weisfeiler-Lehman 子树核的顶点的根字符串可以表示为

通过组成标签函数，我们可以构建一个将有序顶点集映射到根字符串的单射函数。然后，顶点的根字符串可以写为。

类似地，给定顶点，在次迭代中，超图 Weisfeiler-Lehman 子树核的压缩根字符串为

，其中是给定顶点的超边邻居集。然后，每个超边标签可以通过

计算，其中是给定超边的顶点邻居集。最后，在次迭代中，超图 Weisfeiler-Lehman 子树核的顶点的根字符串可以表示为

其中表示由超边连接的顶点集。考虑到给定图中的每条边只连接两个顶点，并且其中一个连接的顶点必须是顶点，（8）可以写为

由于简单图中的超边度数恒定为2，超边标签全部相同：

。

当时，这两种算法都计算不同类型标签的数量，因此产生相同数量的根字符串。

当时，通过组成标签函数和初始超边标签，我们可以构建一个将顶点集映射到字符串的单射函数。然后，从超图 Weisfeiler-Lehman 提取的顶点的根字符串可以写为，这可以映射到从图 Weisfeiler-Lehman 提取的根字符串。由于输入图相同，高度为1的根子树数量也相同，这两个算法在第一次迭代中的唯一标签数量相同。

当时，是关于

的函数，其中和分别是指定的根顶点和由边连接的另一个顶点。对于指定的顶点，相关顶点集

确定根字符串，然后可以简化为。我们还可以构建一个用于映射的单射函数。然后，根字符串可以写为。因此，在的迭代中，这两个算法的压缩标签数量也相同。

由于这两种算法在每次迭代中产生相同数量的唯一压缩标签，两个算法在次迭代中提取的根字符串数量相同。这些根字符串也可以从相同的排序顶点集中确定。因此，满射成立。

注入证明：首先，我们构建一个从图 Weisfeiler-Lehman 根字符串到超图 Weisfeiler-Lehman 根字符串的映射。给定一个如（7）所示的根字符串，我们首先用单射函数提取茎顶点集。注意，茎顶点集的第一个元素是根顶点，其余的是顶点的邻居顶点集。然后，我们将茎顶点集转换为扩展集

。在超图 Weisfeiler-Lehman 子树核的根字符串（如（9）所示）中，更新的超边标签

是的函数，初始超边标签全相同。因此，根字符串也可以从茎顶点集计算出来，可以用单射函数表示。然后，映射可以实现为组合函数。

接下来，我们证明

。表示图 Weisfeiler-Lehman 子树核提取的最终根字符串集。从算法 [31] 的定义中，我们知道中的任何两个元素都是不同的，并且表示不同的根子树结构。假设我们有两个根字符串和满足，则和的根顶点相同，称为顶点。显然，单射函数的操作是可逆的。然后，两个相同的根字符串和可以转换为茎顶点集

。删除每个元素的根顶点并应用的逆函数后，和将生成相同的根字符串和。由于假设错误导致矛盾，因此得出注入成立的结论。

最后，由于满射和注入成立，根据双射的定义，引理2成立。

定理3：给定一组图，核矩阵和分别由图 Weisfeiler-Lehman 子树核和超图 Weisfeiler-Lehman 子树核生成。然后，和是相同的。

证明：给定图，特征向量和分别是从图/超图 Weisfeiler-Lehman 子树核提取的图嵌入。由于特征向量中的每个元素对应一个唯一的根字符串，并且根据引理2，存在一个置换矩阵，使得。核矩阵和的条目可以计算为

其中表示两个向量的内积运算。根据置换矩阵，我们有

因此，核矩阵和在位置的每个元素都是相同的。定理成立。

与图神经网络的关系：在这里，我们讨论了典型图神经网络（包括 GCN [11]，GIN [15] 和 k-GNN [16]）的关系。GCN [11] 通过光谱拉普拉斯矩阵进行邻域平滑。与提出的超图 Weisfeiler-Lehman 子树核相比，GCN 的局限性有两个方面。首先，其固有的成对消息传递限制了对高阶结构（如超图）的应用。其次，基于平均值的邻域聚合不是一个单射函数；因此，它无法区分某些相似的子结构。为了更好地识别子结构，GIN [15] 采用基于求和的邻域聚合函数（如 [15] 所证明的单射函数）来实现与图 Weisfeiler-Lehman 测试 [26] 中的哈希映射函数相当的能力。然而，GIN 也受到成对消息聚合的限制，这不适用于超图结构。相比之下，提出的超图 WL 测试将邻域定义从图推广到超图，这可以视为 GIN 框架在超图结构上的高阶形式。另一种高阶图神经网络是 k-GNN，源自 k-WL 测试。k-GNN 将图中的任意个顶点绑定在一起生成超级顶点，并在这些超级顶点共享相同顶点时连接它们。换句话说，k-GNN 在原始图上构建高阶相关性，并通过连接一些成对边将其转换为新的低阶结构。显然，k-GNN 的表达能力增加，使其能够在理论上区分 1-WL 和 GIN 失败的情况。不幸的是，随着和图的大小增加，k-GNN 的复杂性呈指数增长，并且也无法处理高阶超图结构。相比之下，提出的超图 Weisfeiler-Lehman 核可以直接区分低阶图结构和高阶超图结构中的子结构。
与超图神经网络的关系：我们进一步讨论了典型超图神经网络（包括 HGNN [17] 和 HGNN+ [19]）的关系。HGNN [17] 利用超图拉普拉斯平滑高阶相关性的顶点特征，这也在超图级别分类任务中存在非单射聚合函数的问题。HGNN 本质上对原始超图应用团扩展，并通过基于平均值的聚合从顶点到顶点传递消息，这无法区分相似的子结构。因为团扩展是一种多对一映射，如 Feng 等 [20] 所述，这可能会将不同的超图结构投影到相同的图结构上，而基于平均值的聚合是结构识别的弱判别器 [15]。相比之下，HGNN+ 执行两阶段消息传递：顶点到超边和超边到顶点，这类似于星形扩展。通过添加更多的虚拟顶点作为顶点之间的桥梁来替换这些高阶连接，HGNN+ 可以克服基于团的 HGNN 在子结构区分中的固有缺陷。也就是说，HGNN+ 在大多数场景中可以实现更高的表达能力上限。然而，HGNN+ 也存在基于平均值的聚合可能无法区分相似子结构的问题。因此，定义一个用于超图中消息聚合的单射函数（如我们超图 Weisfeiler-Lehman 测试中的哈希函数）将是一个潜在的工作。对 HGNN+ 的扩展将具有神经网络的强大学习能力和 WL 测试的准确判别能力，这可以在未来的工作中完成。
与二部图核的关系：在本节中，我们讨论了两种典型的应用于二部图 [24] 和超图 [37] 的二部图核的关系。Li 等 [24] 利用二部图对用户-物品交互数据进行建模，从而构建一个具有两种类型顶点的异构图。他们开发了一种随机游走核，将相关结构嵌入顶点表示中，以进行下游任务。然而，这种类型的二部图核只能处理成对相关性，无法扩展到超图。相比之下，提出的超图 Weisfeiler-Lehman 子树核可以通过放松高阶相关性的邻居定义来处理超图。尽管星形扩展可以将超图转换为二部图，但生成的二部图相关性本质上是低阶的，可能需要额外的内存。在处理包含二部图和高阶相关性的更复杂超图时，将超图建模为二部图的方法可能会失败。另一种典型的二部图核是超图有向线核 [37]，它设计了一种映射，将超图结构转换为用于结构识别的有向线图。显然，这种映射不是双射的，会生成许多冗余结构。这将导致许多中等规模超图数据集中的内存不足问题，如表 IV 所示，并且随着超图的增长，运行时间会极大地增加，如图 6 所示。此外，超图有向线核 [37] 采用两个对称有向图核进行特征提取。相比之下，提出的超图 Weisfeiler-Lehman 子树核直接对超图进行操作，只需一次核方法即可生成超图表示。因此，我们的核方法在有效性和效率方面实现了更大的改进。

V. 实验

在本节中，我们对七个图和12个超图数据集进行了实验，包括合成数据集和真实数据集。此外，我们还进行了消融研究，以比较提出的两种超图 Weisfeiler-Lehman 核。此外，我们还比较了这些方法在数据噪声挑战下的计算运行时间和鲁棒性。

A. 通用设置

本小节概述了所有实验中应用的标准实验设置，这些设置可能会在每个指定实验中被覆盖。在接下来的小节中，缩写 WL 用于表示 Weisfeiler-Lehman。

对比方法：由于我们专注于纯核方法处理相关数据，为了公平比较，我们选择了四种典型的基于图/超图核的方法。GraphLet 核 [34]。这是一种典型的基于采样的图核方法，从给定的图中绘制并计算小因子图。图 WL 子树核 [31]。这种方法自然地从图 Weisfeiler-Lehman 算法推广，计算给定图的根子树。超图根核 [35]。这是一种典型的基于采样的超图核方法，从给定的超图中绘制并计算超路径。超图有向线核 [37]。超图有向线核是一种基于转换的方法，将超图转换为有向图。然后，应用有向 Weisfeiler-Lehman 算法提取给定超图的特征向量。

训练细节：为了公平比较，我们将随机种子设置在 [2021, 2025] 范围内，并采用5折交叉验证进行每个实验。我们报告五折五种子的方法的平均结果。由于这些核方法只能生成图/超图特征，我们利用标准的 SVM [39], [40] 作为分类器来比较这些方法。注意，所有方法的 SVM 都初始化为相同的超参数。

其他细节：为了评估捕获不同相关结构的效果，我们排除所有数据集的原始顶点特征。每个顶点标签基于顶点度初始化，边/超边标签根据边/超边度初始化。注意，图中的边标签始终保持不变，为二。

由于传统的图核方法不能直接应用于超图，我们采用常见的技巧团扩展 [19] 将超图转换为图。至于在图数据集上面对超图核，我们将这些图直接视为2-均匀超图。

我们评估单标签分类任务的准确性（Acc）和宏观 F1 分数（F1_ ma）作为性能指标。我们将精确匹配比率（EMR）和基于示例的准确性（EB-Acc）作为多标签分类任务的评估标准。

B. 超图数据集上的实验

本小节展示了在几个超图数据集上的实验结果，包括四个合成数据集和八个真实超图数据集。表 II 总结了数据集的统计数据。

数据集：合成超图数据集：为了评估同构算法在捕获结构信息方面的性能，我们创建了四组随机生成的超图数据集：RHG-10、RHG-3、RHG-Table 和 RHG-Pyramid。通过随机选择构造参数，我们创建了范围广泛的多样化超图进行实验。RHG-10 数据集包含所有十种不同的超图结构因子。图 4 展示了所有十种典型超图结构的示例。在十种手动选择的结构中，有三对（六种类型）超图结构容易混淆，其余四种类型从常见和经典的超图结构中选择。为了评估算法识别重要高阶结构的能力，我们为三种明显不同的超图结构随机生成了1000个超图：超金字塔、超检查表和超轮，从而构建了 RHG-3 数据集。此外，为了验证我们的超图同构算法的细粒度分类能力，我们为每对容易混淆的超图结构创建了两个独立的数据集：RHG-Pyramid 包含由超金字塔和超固金字塔结构组成的一千个超图；RHG-Table 由超检查表和超反检查表结构的数据组成。

合成超图上的结果和讨论：表 III 提供了四个合成超图数据集上的实验结果。基于获得的结果，我们对每个数据集进行了不同的观察。首先，从 RHG-10 数据集中获得的结果显示了我们的同构算法相比其他算法的显著改进。具体而言，超图 WL 子树的准确性提高了25.1%，超图 WL 超边的准确性提高了20.3%。其次，Graphlet 提供的同构结果比其他算法明显更低。这种差异可以归因于 Graphlet 对随机采样的高度依赖，这会损害预测的稳定性。

超图同构和图同构之间的性能差异在 RHG-Table 数据集中显而易见。使用图同构算法时需要通过团扩展将超图结构转换为图结构，这揭示了图结构在表示复杂结构方面不如超图。同样，对于包含两种复杂超图结构的 RHG-Table 和 RHG-Pyramid 数据集，超图根算法的识别能力显著低于其他超图同构算法。与两种图同构算法的表现相似，超图根算法约50%的准确性表明它无法解决超稳固检查表和超检查表结构。超图根算法表现较差的原因在于其本质上是一种随机游走采样方法，在遇到重叠部分的超边时会导致随机遍历。因此，该算法缺乏对常见于超稳固金字塔结构中重叠节点组的可靠判断，如图 5 所示。然而，HG 有向线算法不受此限制。通过将其转换为二部图，重叠的边得到适当增强，从而克服了上述问题。我们的两种算法超越了传统方法。它们通过消除超图到图转换步骤显著减少了从特殊结构中提取结构特征所需的时间，并在涉及常见重叠超边的情况下表现出强大的识别能力。

真实超图上的结果和讨论：表 IV 和表 V 展示了八个真实超图数据集的实验结果。基于这些结果，我们有三个观察。首先，我们提出的两种超图 WL 核在所有真实超图数据集中都优于其他对比方法。这种优势源于我们的方法能够通过两阶段超图 WL 算法有效捕获和识别各种高阶结构。其次，我们观察到提出的“HG WL 超边”方法在三个 IMDB-Wri 数据集中优于提出的“HG WL 子树”方法：IMDB-Wri-Form、IMDB-Wri-Genre 和 IMDB-Wri-Genre-M。通过进一步分析，在表 II 中，我们发现这三个超图数据集的超边平均数量较低（<= 5.0），超边平均度较高（>= 5.0）。结果表明，与“HG WL 子树”方法相比，“HG WL 超边”方法能够识别由较多顶点连接的更复杂的超边。因此，“HG WL 超边”在这三个超图数据集中表现更好。第三，对于对比方法，我们观察到在大多数数据集中，HG 有向线方法优于图 WL 子树方法，而 HG 根方法优于 Graphlet 方法。需要注意的是，为了确保公平比较，Graphlet 和 HG 根方法是基于采样的方法，而其他两种方法不是。显然，由于采样固有的信息丢失，基于采样的方法的性能低于其他两种方法。在每种方法类型中，超图核方法能够直接捕获和处理超图中存在的高阶相关性，从而表现出优越的性能。

C. 图数据集上的实验

本小节展示了图数据集上的实验，包括两个合成数据集和五个真实图数据集。表 VI 总结了这些数据集的统计数据。

数据集：合成图数据集：我们设计并生成了两个合成图数据集，RG-Macro 和 RG-Sub，以测试不同算法在各种低阶结构上的能力。我们采用两步法创建这些图。首先，我们手工挑选了六种广泛使用的图结构作为“子图”因子，包括完全图、二部图、环图、立方体图、星形图和轮图。随机选择构造参数生成每个图。作为示例，具有参数的环图由一组五个相互连接的节点组成，每个节点通过一条边连接到其相邻节点。其次，我们设计了六种方式将“子图”因子图组合成更大的图，如链链接、星链接、环链接等。这些链接策略被记录为“宏观”图结构。这两个数据集包含相同的图，但目标标签不同。RG-Macro 数据集使用“宏观”图结构作为标签，而 RG-Sub 数据集测试区分“子图”结构的能力。

真实世界图数据集：IMDB-BINARY [41] 和 IMDB-MULTI [41] 是电影合作数据集。两个数据集中的每个顶点都是一个演员。每部电影对应一个图，并将一个分类目标与之关联。如果两个演员同时出现在另一部电影中，将创建一条边连接它们。IMDB-BINARY 包含来自两个类型的电影：动作片和浪漫片。IMDB-MULTI 是 IMDB-BINARY 的多类版本，包含喜剧片、浪漫片和科幻片。NCI1 [43]、MUTAG [42] 和 PROTEINS [44] 是生物信息学数据集。NCI1 是从国家癌症研究所（NCI）数据集中收集的。它是一个均衡的化合物子集，用于筛选或抑制人类肿瘤细胞系生长，具有37个离散标签。MUTAG 是一个变异芳香和杂芳香硝基化合物数据集，具有七个离散标签。PROTEINS 是一个数据集，其中节点是二级结构元素（SSEs），如果它们在氨基酸序列或三维空间中是邻居，则在两个节点之间有一条边。它有三个离散标签，分别代表螺旋、片或转弯。

实验结果和讨论：表 VII 和表 VIII 提供了七个图数据集上的实验结果。我们有以下三个观察。首先，结果表明超图 WL 子树方法与图 WL 子树方法在相同的随机种子和折分割下表现相似。这可以通过 IV-F1 节中的分析来解释，该分析表明超图 WL 核在面对低阶图结构时等于图 WL 核。其次，对比的两种超图核方法比图核方法表现更差。这是因为这两种超图核方法只关注高阶相关性，对常见的低阶相关性无效。例如，超图有向线核通过两步结构转换嵌入图/超图，这将产生许多冗余的低阶结构。面对低阶结构任务（如图分类），这些冗余结构包含许多噪音，可能会降低最终图/超图特征的质量。第三，与超图/图 WL 子树核相比，超图 WL 超边核在这些图数据集中表现尚可。主要原因是图中的边仅连接两个顶点，这限制了超边核的建模能力。在接下来的超图实验中，我们将展示提出的两种超图核方法相比现有图和超图核方法的显著性能提升。

D. 运行时间比较

在本小节中，我们进行实验以评估不同方法的运行时间性能，如图 6 所示。为了公平比较，我们选择了超图有向线方法作为基准，因为它是一种不采用采样策略的超图核方法。DeepHyperGraph4 库用于生成合成超图。这些方法在相同的机器上计算，配备 Intel i7-10700 @ 2.90 GHz×16 CPU 和 16G 内存。默认情况下，随机生成具有“低阶优先”配置的500个超图，每个超图包含50个顶点和250个超边。为了进行完整的运行时间比较，我们设计了四种类型的合成超图设置。第一种合成超图设置用于测试随着每个超图顶点数量的增长方法的运行时间。在此设置中，超图数量固定为500。在每个超图中，超边数量是顶点数量的五倍。该设置的实验结果如图 6(a) 所示。第二种合成超图设置用于测试随着每个超图超边数量的增长方法的运行时间。在此设置中，顶点数量固定为50。超边数量在 [50, 100, 150, 200] 范围内变化。该设置的实验结果如图 6(b) 所示。第三种合成超图设置用于评估随着超图数量的增加方法的运行时间性能。在此设置中，顶点和超边数量分别固定为50和250。超图数量在 [50, 100, 200, 500, 1000, 2000] 范围内变化。该设置的实验结果如图 6(c) 所示。最后一种合成超图设置用于测试随着超图复杂性的增加方法的运行时间。与简单图中的边相比，超边可以连接多个顶点。超图的复杂性会随着超边度数的增加而上升。在此设置中，顶点和超边数量分别固定为50和250。然而，超边的度数是可变的。换句话说，我们随机生成500个2-均匀超图、3-均匀超图、4-均匀超图和5-均匀超图进行运行时间比较。该设置的实验结果如图 6(d) 所示。从四组实验结果中，我们观察到提出的两种方法运行速度显著快于（86×）对比的超图有向线方法。尤其是面对更复杂的超图数据集（超边度数增加），提出的方法在图 6(d) 所示的情况下仍显示出强大的运行时间。这是因为超图有向线方法不能直接处理超图，通过团扩展将超图转换为无向图，并进一步生成有向线图以进行核特征提取。相比之下，我们的超图 Weisfeiler-Lehman 核直接处理超图，避免了不必要的转换，保持了计算效率。

VI. 结论

在本文中，我们将 Weisfeiler-Lehman 测试从图扩展到超图，并提出了超图 Weisfeiler-Lehman 测试算法用于超图同构测试问题。我们证明了提出的超图 Weisfeiler-Lehman 子树核可以退化为图 Weisfeiler-Lehman 子树核，在面对图结构时实现相同的性能。对19个图/超图分类数据集的广泛实验证明了所提出方法的有效性。我们的未来工作将集中于进一步增强核函数并探索其在各个领域的应用。

声明

本文内容为论文学习收获分享，受限于知识能力，本文对原文的理解可能存在偏差，最终内容以原论文为准。本文信息旨在传播和学术交流，其内容由作者负责，不代表本号观点。文中作品文字、图片等如涉及内容、版权和其他问题，请及时与我们联系，我们将在第一时间回复并处理。

下载1：OpenCV-Contrib扩展模块中文版教程

在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。

下载2：Python视觉实战项目52讲

在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。

下载3：OpenCV实战项目20讲

在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。

交流群

欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~

TPAMI 2024 | 超图同构计算

点击上方“小白学视觉”，选择加"星标"或“置顶”重磅干货，第一时间送达题目：Hypergraph Isomorphism Computation