等变超图神经网络

Equivariant Hypergraph Neural Networks

等变超图神经网络

https://www.ecva.net/papers/eccv_2022/papers_ECCV/papers/136810086.pdf

摘要

计算机视觉和机器学习中的许多问题可以归结为在表示高阶关系的超图上进行学习。最近的超图学习方法扩展了基于消息传递的图神经网络，这种方法虽然简单，但在建模长程依赖性和表达能力方面存在根本性的局限。另一方面，基于张量的等变神经网络具有最大的表达能力，但由于计算量大以及对固定阶超边的严格假设，其在超图中的应用受到限制。我们解决了这些问题，并提出了等变超图神经网络（Equivariant Hypergraph Neural Network, EHNN），这是首次尝试为通用超图学习实现具有最大表达能力的等变层。我们还提出了基于超网络（EHNN-MLP）和自注意力机制（EHNN-Transformer）的两种实用框架实现，它们易于实现，且在理论上比大多数消息传递方法更具表达能力。我们在一系列超图学习问题中展示了其能力，包括合成 k-边识别、半监督分类和视觉关键点匹配，并报告了优于强消息传递基线的性能。我们的实现代码可在 https://github.com/jw9730/ehnn 获取。

关键词：超图神经网络，图神经网络，置换等变性，半监督分类，关键点匹配

1 引言

对涉及一组实体及其关系的系统进行推理需要关系型数据结构。图通过节点和边来表示关系型数据，其中节点对应于实体，边表示一对节点之间的关系。然而，成对的边往往不足以表示更复杂的关系。例如，许多实体的几何构型（如角度和面积）只有通过考虑三个或更多节点之间的高阶关系才能捕捉到。超图是一种通用的数据结构，它通过超边（即同时关联两个以上节点的边）来表示这种高阶关系 [6]。因此，它被广泛用于表示各种视觉数据，如场景 [19, 30]、特征对应 [4, 41, 49, 55] 和多边形网格 [8, 46, 58]，以及一般的关系型数据，如社交网络 [10, 37, 52]、生物网络 [22, 33]、语言结构 [15] 和组合优化问题 [28]。

2 预备知识与相关工作

让我们介绍来自置换等变学习的预备概念 [32, 43, 51]。我们首先描述高阶张量，然后描述构成等变 GNN 的最大表达能力置换等变线性层 [43]。

3 等变超图神经网络

3.1 超图作为高阶张量序列

3.2 超图的等变线性层

3.3 等变超图神经网络 (EHNN)

3.4 EHNN 的实际实现

我们通过将 EHNN-MLP 消融简化为 AllDeepSets 来展示以下内容：

定理 3.AllDeepSets 层（公式 (12)）是 EHNN-MLP 层（公式 (7)）的一个特例，反之则不成立。

最后，定理 3 导出了以下推论：

推论 1.EHNN-MLP 层比 AllDeepSets 层以及 AllDeepSets 所包含的所有超图神经网络都具有更强的表达能力。

我们在附录 A.2 中提供了深入的讨论，包括 EHNN-Transformer 和 AllSetTransformer [13] 之间的比较。

4 实验

我们在一系列超图学习问题上测试了 EHNN，包括合成节点分类问题、真实世界半监督分类和视觉关键点匹配。对于真实世界任务，我们使用了 Chien 等人 [13] 中的 10 个半监督分类数据集以及 Wang 等人 [55] 中的两个视觉关键点匹配数据集。包括数据集和超参数在内的详细信息见附录 A.3。额外的实验，包括对比和消融研究，以及运行时间和内存成本分析，见附录 A.4。

4.1 合成 k-边识别

测试性能如表 1 所示。EHNN 相比消息传递网络取得了显著提升，产生了近乎完美的预测。该结果表明，即使是对于简单的任务，也存在网络的高表达能力至关重要的情况。此外，我们观察到证据表明模型可以对未见的超边阶数进行插值甚至外推。这支持了使用超网络来推断潜在未见阶数参数的做法。

4.2 半监督分类

为了在真实世界超图学习中测试 EHNN，我们使用了 10 个直推式半监督节点分类数据集 [13]。数据被随机划分为 50% 训练集、25% 验证集和 25% 测试集。我们使用随机划分和初始化运行实验 20 次，并报告聚合的分类准确率。

测试性能如表 2 所示。我们的方法通常在强基线（例如 AllDeepSets 和 AllSetTransformer）上取得有利的分数——我们的模型在 Walmart (1) 上将最先进水平提高了 3.27%，在 House (0.6) 上提高了 1.82%，在 Walmart (0.6) 上提高了 1.54%。值得注意的是，EHNN-Transformer 在大多数情况下给出了最先进的性能。这支持了注意力机制能增强等变网络的观点 [32, 36]，同时也暗示了 EHNN 的高表达能力使其在不仅涉及社交网络，还涉及视觉和图形学（NTU2012 和 ModelNet40）的通用超图学习设置中表现强劲。

4.3 视觉关键点匹配

为了在表示为超图学习的计算机视觉问题中测试 EHNN，我们解决了视觉关键点匹配问题。由于两张图像在视角、尺度和光照方面存在差异，该任务被认为具有挑战性。遵循先前的工作 [55]，我们将该问题视为超图匹配，其中每张图像的关键点形成一个超图。这被认为是有帮助的，因为超边特征可以捕捉旋转和尺度不变的几何特征（如角度）。然后，我们按照先前的工作 [55]，将超图匹配转化为单个关联超图上的二分类节点分类问题。

我们使用了两个标准数据集 [55]：Willow ObjectClass [14] 和 PASCAL-VOC [9, 17]。Willow 数据集包含 256 张图像，涵盖 5 个物体类别。PASCAL-VOC 数据集包含 11,530 张图像，涵盖 20 个物体类别，由于光照和姿态的巨大差异而被认为具有挑战性。我们遵循 NHGM-v2 [55] 的训练设置，仅将超图神经网络模块替换为 EHNN-MLP/-Transformer。NHGM-v2 与我们模型的主要区别在于，NHGM-v2 利用了两个独立的消息传递网络，一个用于 2-边，另一个用于 3-边，并将节点特征聚合作为加权和。相比之下，EHNN 通过共享的 MLP 超网络和全局交互广泛地混合了来自 2-边和 3-边的信息。

结果如表 3 和表 4 所示。在 Willow 数据集上，EHNN-Transformer 给出了最佳性能，比 NHGM-v2 提高了 4.87%。在 PASCAL-VOC 数据集上，EHNNs 比 NHGM-v2 提高了约 1%，并且与依赖复杂组合求解器的最佳模型（BBGM；差距 0.19%）[50] 具有竞争力。我们推测，2-边（距离）和 3-边（角度）特征的内在及全局混合改善了超图学习，从而也改善了关键点匹配。

5 结论

我们提出了一种被称为等变超图神经网络（EHNN）的超图神经网络。EHNN 通过将超图表示为张量序列并在其上组合等变线性层，将等变 GNN 的理论基础扩展到了通用无向超图。我们进一步提出了 EHNN-MLP/-Transformer，这是基于 MLP 超网络的 EHNN 的实际实现。我们证明了 EHNN 在理论上比大多数消息传递网络具有更强的表达能力，并提供了实证证据。

原文链接：https://www.ecva.net/papers/eccv_2022/papers_ECCV/papers/136810086.pdf