TPAMI 2024 | 超图同构计算
小白学视觉
共 91680字，需浏览 184分钟
·
2024-06-24 10:04
点击上方“小白学视觉”，选择加"星标"或“置顶”
重磅干货，第一时间送达
题目：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. 图/超图同构
B. 图 Weisfeiler-Lehman 核
-
图 Weisfeiler-Lehman 子树核：由于每次迭代中的顶点标签对应一个唯一的子树结构，图 Weisfeiler-Lehman 子树核的简单思想是计算图中不同类型标签的数量。因此，特征函数 可以定义为
-
图 Weisfeiler-Lehman 边核：此外，图 Weisfeiler-Lehman 边核计算具有相同标签端点的边匹配对，可以表示为
-
多集标签确定。 -
对于 ，设置 。 -
对于 ，为 和 中的每个顶点 分配一个多集标签 。 -
对每个多集进行排序。 -
对 中的元素进行排序并转换为字符串 。 -
将 作为前缀添加到 。 -
标签压缩。 -
对 和 中所有 的字符串 进行排序。 -
将每个字符串 映射到一个新的压缩标签。 -
重新标记。 -
设置 ，适用于 和 中的所有顶点。
IV. 方法
A. 超图 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 核：给定超图，我们可以通过算法 2 获得超图 Weisfeiler-Lehman 序列。为了从这些序列中生成超图嵌入以进行计算，我们定义了通用超图 Weisfeiler-Lehman 核。
C. 超图 Weisfeiler-Lehman 子树核
D. 超图 Weisfeiler-Lehman 超边核
E. 实际计算
F. 分析和讨论
-
与图 WL 子树核的关系：在这里，我们证明了在面对简单图结构时，超图 Weisfeiler-Lehman 子树核可以退化为图 Weisfeiler-Lehman 子树核。
-
与图神经网络的关系：在这里，我们讨论了典型图神经网络（包括 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. 实验
A. 通用设置
-
训练细节：为了公平比较，我们将随机种子设置在 [2021, 2025] 范围内，并采用5折交叉验证进行每个实验。我们报告五折五种子的方法的平均结果。由于这些核方法只能生成图/超图特征，我们利用标准的 SVM [39], [40] 作为分类器来比较这些方法。注意，所有方法的 SVM 都初始化为相同的超参数。
-
其他细节：为了评估捕获不同相关结构的效果，我们排除所有数据集的原始顶点特征。每个顶点标签基于顶点度初始化，边/超边标签根据边/超边度初始化。注意，图中的边标签始终保持不变，为二。
B. 超图数据集上的实验
-
数据集：合成超图数据集：为了评估同构算法在捕获结构信息方面的性能，我们创建了四组随机生成的超图数据集：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 对随机采样的高度依赖，这会损害预测的稳定性。
-
真实超图上的结果和讨论：表 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. 图数据集上的实验
-
数据集：合成图数据集：我们设计并生成了两个合成图数据集，RG-Macro 和 RG-Sub，以测试不同算法在各种低阶结构上的能力。我们采用两步法创建这些图。首先，我们手工挑选了六种广泛使用的图结构作为“子图”因子，包括完全图、二部图、环图、立方体图、星形图和轮图。随机选择构造参数生成每个图。作为示例，具有参数 的环图由一组五个相互连接的节点组成，每个节点通过一条边连接到其相邻节点。其次，我们设计了六种方式将“子图”因子图组合成更大的图，如链链接、星链接、环链接等。这些链接策略被记录为“宏观”图结构。这两个数据集包含相同的图，但目标标签不同。RG-Macro 数据集使用“宏观”图结构作为标签，而 RG-Sub 数据集测试区分“子图”结构的能力。
-
实验结果和讨论：表 VII 和表 VIII 提供了七个图数据集上的实验结果。我们有以下三个观察。首先，结果表明超图 WL 子树方法与图 WL 子树方法在相同的随机种子和折分割下表现相似。这可以通过 IV-F1 节中的分析来解释，该分析表明超图 WL 核在面对低阶图结构时等于图 WL 核。其次，对比的两种超图核方法比图核方法表现更差。这是因为这两种超图核方法只关注高阶相关性，对常见的低阶相关性无效。例如，超图有向线核通过两步结构转换嵌入图/超图，这将产生许多冗余的低阶结构。面对低阶结构任务（如图分类），这些冗余结构包含许多噪音，可能会降低最终图/超图特征的质量。第三，与超图/图 WL 子树核相比，超图 WL 超边核在这些图数据集中表现尚可。主要原因是图中的边仅连接两个顶点，这限制了超边核的建模能力。在接下来的超图实验中，我们将展示提出的两种超图核方法相比现有图和超图核方法的显著性能提升。
D. 运行时间比较
VI. 结论
声明
下载1：OpenCV-Contrib扩展模块中文版教程
在「小白学视觉」公众号后台回复：扩展模块中文教程，即可下载全网第一份OpenCV扩展模块教程中文版，涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。
下载2：Python视觉实战项目52讲 在「小白学视觉」公众号后台回复：Python视觉实战项目，即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目，助力快速学校计算机视觉。
下载3：OpenCV实战项目20讲 在「小白学视觉」公众号后台回复：OpenCV实战项目20讲，即可下载含有20个基于OpenCV实现20个实战项目，实现OpenCV学习进阶。
交流群
欢迎加入公众号读者群一起和同行交流，目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群（以后会逐渐细分），请扫描下面微信号加群，备注：”昵称+学校/公司+研究方向“，例如：”张三 + 上海交大 + 视觉SLAM“。请按照格式备注，否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告，否则会请出群，谢谢理解~
评论