层超图网络|向量|层超图|拉普拉斯|新论文|算子

层超图网络 Sheaf Hypergraph Networks

https://arxiv.org/pdf/2309.17116

摘要

高阶关系在自然界中广泛存在，众多现象涉及超越简单成对连接的复杂交互。因此，高阶处理领域的进展能够加速需要结构化数据的各个领域的发展。当前方法通常使用超图来表示这些交互。我们通过为超图引入胞腔层（cellular sheaves）来增强这种表示，这是一种数学构造，它在保持传统超图局部高阶连通性的同时，为其添加了额外结构。受文献中现有拉普拉斯算子的启发，我们开发了两种独特的层超图拉普拉斯算子公式：线性和非线性。我们的理论分析表明，将层（sheaves）融入超图拉普拉斯算子中，比标准超图扩散提供了更具表达力的归纳偏置，从而为有效建模复杂数据结构创造了一个强有力的工具。我们利用这些层超图拉普拉斯算子设计了两类模型：层超图神经网络与层超图卷积网络。这些模型推广了文献中常见的经典超图网络。通过大量实验，我们证明了这种推广显著提升了性能，在多个用于超图节点分类的基准数据集上取得了顶尖结果。

1 引言

关系数据在现实场景中的普遍存在，促使基于图的方法在众多领域得到快速发展并广泛应用[1–4]。然而，图的一个主要局限性在于其无法表示超越成对关系的交互。相比之下，现实世界中的交互往往是复杂且多层面的。有证据表明，高阶关系经常出现在神经科学[5, 6]、化学[7]、环境科学[8, 9]和社交网络[10]中。因此，学习强大且有意义的超图表示已成为深度学习中一个充满前景且快速发展的子领域[11–16]。然而，当前基于超图的模型难以有效捕捉高阶关系。如[17]所述，传统的超图神经网络常常面临过平滑问题。当我们在超图内部传播信息时，节点的表示会在邻域内趋于一致。这种效应阻碍了超图模型捕捉局部高阶细微特征的能力。

需要更强大、更灵活的数学构造来更好地捕捉现实世界交互的复杂性。层（sheaves）为图提供了一种合适的增强方式，能够实现更多样化、更具表达力的表示。胞腔层[18]能够将数据附加到图上，其方法是为节点关联向量空间，并配备一种沿边传递信息的机制。这种方法允许更丰富的数据表示，并增强了建模复杂交互的能力。

出于对更具表达力结构的需求，我们为超图引入了胞腔层，它允许表示更复杂的动态，同时保留超图固有的高阶连通性。我们迎接这一非平凡挑战，将两种常用的超图拉普拉斯算子[19, 11]进行推广，以融入层所提供的更丰富结构。理论上，我们证明了使用我们提出的层超图拉普拉斯算子推导出的扩散过程，比经典超图扩散诱导了更具表达力的归纳偏置。借助这种增强的归纳偏置，我们构建并测试了两个强大的神经网络，它们能够推断和处理超图层结构：层超图神经网络（SheafHyperGNN）和层超图卷积网络（SheafHyperGCN）。

超图胞腔层的引入扩展了表示复杂交互的潜力，并为更先进的技术奠定了基础。通过利用层结构推广超图拉普拉斯算子，我们能够更好地捕捉现实世界数据的细微差别与复杂性。此外，我们的理论分析提供了证据，表明层超图拉普拉斯算子体现了更具表达力的归纳偏置，这对于获得强大的表示至关重要。

我们的主要贡献总结如下：

我们为超图引入了胞腔层，这是一种数学构造，通过为每个节点和超边关联一个向量空间，并配备使它们之间能够进行信息传递的线性投影，从而为超图增强了额外结构。
我们提出了线性和非线性的层超图拉普拉斯算子，推广了文献中常用的标准超图拉普拉斯算子。我们还对这些拉普拉斯算子扩散过程所产生的归纳偏置进行了理论刻画，展示了利用这些新颖工具有效建模复杂现象的优势。
这两种层超图拉普拉斯算子构成了专为超图处理设计的两种新颖架构的基础：层超图神经网络和层超图卷积网络。实验结果表明，这些模型取得了顶尖性能，在众多基准数据集上超越了现有方法。

2 相关工作

图上的层。 利用现实世界数据中的图结构已推动医疗保健[1]、生物化学[2]、社交网络[20]、推荐系统[3]、交通预测[21]等多个领域的进步，图神经网络（GNN）已成为图表示的标准。然而，在异配设置中，当具有不同标签的节点更有可能相连时，直接处理图结构会导致性能不佳。文献[22]通过以胞腔层[18]的形式为图附加额外的几何结构来解决这一问题。

图上的胞腔层为每个节点和每条边关联一个向量空间，并为每个关联对提供这些空间之间的线性投影。为了考量这种更复杂的几何结构，SheafNN [23] 通过将图拉普拉斯算子替换为层拉普拉斯算子[27]，对经典GNN [24–26] 进行了推广。研究者探索了基于高维层的神经网络，其中的层结构要么从图中学习得到[22]，要么出于效率考虑进行确定性推断[28]。近期的方法集成了注意力机制[29]，或用波动方程替代了传播过程[30]。在最新进展中，层神经网络被发现能显著提升推荐系统的性能，因为它们改进了图神经网络的局限性[31]。

在异构图领域，为不同类型的边学习独特消息传递函数的概念已十分成熟。然而，与RGCN [32]等异构图方法相比，基于层的方法在处理该任务的方式上存在区别。后者为每种关联关系学习独立的参数，而基于层的方法则依赖于与节点和超边相关的特征，动态预测每种关系的投影。因此，层网络中的参数总量不会随着超边数量的增加而急剧膨胀。这一差异凸显了两种方法在底层范式上的根本性转变。

超图网络。 图虽然有用，但有一个显著的局限性：它们只能表示成对关系。许多自然现象涉及复杂的高阶交互[33–35, 9]，需要像超图这样更通用的结构。近年来，针对超图结构已开发出多种深度学习方法。HyperGNN [11] 将超图扩展为加权团，并应用类似于GCN [24] 的消息传递。HNHN [36] 通过引入非线性操作对此进行了改进，而HyperGCN [37] 则使用非线性拉普拉斯算子仅连接差异最显著的节点。与GNN领域的趋势相似，注意力模型在超图领域也日益普及。HCHA [38] 使用一种基于注意力的关联矩阵，该矩阵基于节点与超边的相似度计算得出。类似地，HERALD [39] 利用可学习的距离来推断软关联矩阵。另一方面，HEAT [15] 通过使用Transformer [40] 在每个超边内部传播信息来构建消息。

许多超图神经网络（HNN）方法可被视为两阶段框架：1）将消息从节点发送至超边；2）将消息从超边传回节点。因此，[41] 提出了一种通用框架，其中第一阶段采用平均算子，而第二阶段则可使用任何现有的GNN模块。类似地，[42] 使用DeepSet函数[43]或Transformer[40]来实现这两个阶段，而[44] 在两个阶段均使用类GNN聚合器，并为每个（节点，超边）对分配不同的消息。

相比之下，我们提出了一种新颖的模型，旨在通过将胞腔层附加到超图结构上，并依据该层在模型内部扩散信息，来改进超图处理。我们将首先介绍超图的胞腔层，证明相关拉普拉斯算子的一些性质，随后提出并评估基于层超图拉普拉斯算子的两种架构。

3 超图层拉普拉斯算子

之前的工作侧重于通过依赖定义超图拉普拉斯算子（Laplacian）的各种方法来创建超图表示。在这项工作中，我们将专注于两种定义：如文献 [11] 中使用的超图拉普拉斯算子的线性版本，以及如文献 [37] 中的超图拉普拉斯算子的非线性版本。我们将扩展这两种定义以融入超图层结构，分析由此产生的优势，并基于每一种定义提出两种不同的神经网络架构。关于两种提出的层超图拉普拉斯算子的直观对比，请参见图 1。

3.1 线性层超图拉普拉斯算子

当每个超边恰好包含两个节点时（因此 H H 是一个图），内部求和将只包含一项，我们便恢复了如文献 [22] 中公式化的图的层拉普拉斯算子（sheaf Laplacian）。

在接下来的章节中，我们将展示使用这种层超图扩散代替通常的超图扩散的优势。

直观地说，这意味着使用线性超图拉普拉斯算子应用扩散会导致相邻节点的表示变得相似。虽然这在某些场景中是可取的，但在其他场景中可能会导致性能不佳，这种现象被称为过平滑（over-smoothing）[17]。在下文中，我们展示了使用线性层超图拉普拉斯算子应用扩散，通过隐式最小化一个更具表达力的能量函数来解决这些局限性。这使我们能够建模使用通常的拉普拉斯算子无法触及的现象。

该量度量了超边茎（stalk）域中相邻节点之间的差异，而不同于通常的超图狄利克雷能量，后者是在节点特征域中度量这种距离。在下文中，我们将证明，使用线性层拉普拉斯算子应用超图扩散会隐式地降低该能量。

3.2 非线性层超图拉普拉斯算子

尽管线性超图拉普拉斯算子通常用于处理超图，但它在完全保留超图结构方面存在不足[47]。为了解决这些缺点，文献[48]引入了非线性拉普拉斯算子，并证明其谱性质与线性拉普拉斯算子相比更适用于高阶处理。例如，与线性版本相比，非线性拉普拉斯算子在最小割问题中会产生更均衡的划分，而该任务已知与半监督节点分类密切相关。此外，虽然线性拉普拉斯算子为每个超边关联一个团（clique），但非线性版本具有依赖更稀疏连通性的优势。我们将采用类似的方法来推导层超图拉普拉斯算子的非线性版本，并分析使用该算子应用扩散的好处。

定义 4. 我们如下引入超图 H 关于信号 x 的非线性层超图拉普拉斯算子：

尽管被最小化的势函数发生了变化，但总体目标仍然与线性情况类似：力求在超边茎空间内的表示之间达成连贯的一致性，而不是在输入空间中为每个超边生成均匀的特征。与线性场景形成对比的是，在线性场景中每个超边需要二次方数量的边，而非线性层超图拉普拉斯算子将单个边与每个超边相关联，从而提高了计算效率。

3.3 层超图网络

流行的超图神经网络 [45, 11, 37, 50] 从多种超图扩散算子 [47, 48, 51] 中汲取灵感，从而产生了多样化的消息传递技术。这些技术都涉及信息从节点传播到超边，反之亦然。我们将采用类似的策略，并基于本文中讨论的层扩散机制所启发的两种消息传递方案，引入层超图神经网络（Sheaf Hypergraph Neural Network）和层超图卷积网络（Sheaf Hypergraph Convolutional Network）。

总之，本文介绍的模型，即 SheafHyperGNN 和 SheafHyperGCN，充当了经典 HyperGNN [11] 和 HyperGCN [37] 的推广。与其传统对应物相比，这些新模型具有更具表达力的隐式正则化。

4 实验分析

我们在八个领域、规模和异配水平（heterophily level）各异且常用于超图基准测试的真实世界数据集上评估我们的模型。这些数据集包括 Cora, Citeseer, Pubmed, Cora-CA, DBLP-CA [37], House [52], Senate 和 Congress [53]。为了确保与基线方法的公平比较，我们遵循 [50] 中使用的相同训练流程，将数据随机划分为 50% 的训练样本、25% 的验证样本和 25% 的测试样本，并使用不同的随机划分将每个模型运行 10 次。我们报告平均准确率以及标准差。

此外，我们受 [50] 引入的数据集启发，在一组合成异配数据集上进行了实验。遵循他们的方法，我们使用上下文超图随机块模型（contextual hypergraph stochastic block model）[54–56] 生成一个包含 5000 个节点的超图：其中一半属于类别 0，另一半属于类别 1。随后，我们随机采样 1000 个基数（cardinality）为 15 的超边，每个超边恰好包含 β 个来自类别 0 的节点。异配水平计算为 α = min ⁡ ( β , 15 − β ) 。节点特征是从标准差为 1 的标签依赖高斯分布中采样的。由于原始数据集未公开，我们通过改变异配水平 α ∈ { 1 … 7 } 生成我们自己的数据集，并重新运行他们的实验以进行公平比较。

实验在单块具有 48GB 显存的 NVIDIA Quadro RTX 8000 GPU 上执行。除非另有说明，我们的结果代表了每个架构通过使用随机搜索进行超参数优化所获得的最佳性能。关于所有模型选择和超参数的详细信息可以在补充材料中找到。

与近期方法的比较。 我们还将文献中的几种近期模型进行了比较，例如 HCHA [38], HNHN [36], AllDeepSets [42], AllSetTransformer [42], UniGCNII [57], HyperND [58], 和 ED-HNN [50]。我们的模型在所有真实世界数据集上取得了具有竞争力的结果，并在其中五个数据集上达到了最先进的（state-of-the-art）性能（表 1）。这些结果证实了使用层拉普拉斯算子处理超图的优势。我们还在合成异配数据集上将我们的模型与一系列基线进行了比较。结果如表 3 所示。我们要表现最好的模型 SheafHyperGNN，在所有异配水平上始终优于其他模型。请注意，我们要利用层结构增强经典超图处理的框架并不局限于本文测试的两种传统模型（HyperGNN 和 HyperGCN）。大多数近期的最先进方法，例如 ED-HNN，可以很容易地被调整以学习和处理我们要新颖的胞腔层超图，而不是标准超图，从而推动超图领域的进一步发展。

在接下来的章节中，我们进行了一系列消融研究，以更深入地了解我们的模型。我们将探索各种类型的限制映射，分析网络深度变化时性能如何变化，并研究茎维度对最终精度的重要性。

深度的影响。 众所周知，在超图网络中堆叠多层会导致模型性能下降，特别是在异配设置中。这种现象被称为过平滑，在图 [59] 和超图文献 [17] 中都有深入研究。为了分析我们的模型受此限制的程度，我们在合成数据集的最异配版本（ α = 7 ）上训练了一系列模型。对于 SheafHyperGNN 及其 HyperGNN 等效模型，我们将层数在 1 到 8 之间变化。在图 2 中，我们观察到虽然 HyperGNN 在超过 3 层时表现出性能下降，但 SheafHyperGNN 的性能保持基本恒定。在比较 SheafHyperGCN 与 HyperGCN 时，非线性版本也观察到了类似结果（结果在补充材料中）。这些结果表明我们的模型在异配设置中具有潜在优势，允许构建更深的架构。

调查特征多样性。 我们的理论分析表明，虽然传统超图网络倾向于为相邻节点产生相似特征，但我们的层超图网络减少了更复杂的超边茎空间中相邻节点之间的距离。结果是，节点的特征不会变得统一，保留了它们的个体身份。我们通过计算 HyperGNN 和 SheafHyperGNN 的狄利克雷能量（图 2 中的阴影区域）作为相邻节点之间相似度的度量来经验性地评估这一点。结果与理论分析一致：虽然增加 HyperGNN 的深度会创建均匀的特征，但 SheafHyperGNN 不受此限制的影响，鼓励节点之间的多样性。

5 结论

在本文中，我们引入了超图的胞腔层，这是一种建立在经典超图结构之上、用于建模高阶关系的富有表达力的工具。此外，我们提出了两个模型，分别基于线性和非线性层超图拉普拉斯算子，能够推断并处理层超图结构。我们证明了与这些模型相关的扩散过程诱导了一种更具表达力的隐式正则化，扩展了与标准超图扩散相关的能量。这种新颖的架构推广了经典超图网络，且我们通过实验表明，它在多个数据集上优于现有方法。我们在 HyperGNN 和 HyperGCN 中用层超图拉普拉斯算子替换超图拉普拉斯算子的技术，建立了一个通用的框架，可用于“层化”（sheafify）其他超图架构。我们相信，层超图能够为快速发展的超图领域的进一步进步做出贡献，其影响将远远超出本文所呈现的结果。

原文链接： https://arxiv.org/pdf/2309.17116