全动态超图神经网络

全动态超图神经网络

Totally Dynamic Hypergraph Neural Network

https://www.ijcai.org/proceedings/2023/0275.pdf

摘要 近期的动态超图神经网络（DHGNNs）旨在自适应地优化超图结构，以避免对初始超图结构的依赖，从而在表示学习中捕获更多隐藏信息。然而，大多数现有的 DHGNN 无法调整超边数量，因而难以充分挖掘潜在的超图结构。本文提出一种新方法，即全动态超图神经网络（Totally Dynamic Hypergraph Neural Network, TDHNN），通过调整超边数量来优化超图结构。具体而言，所提方法首先通过对学习到的分布进行采样，捕获超边特征分布以获取动态的超边特征，而非固定特征；随后，基于采样得到的超边与节点的注意力系数构建超图；最后，通过设计一种简洁的超图卷积算法动态更新节点特征。在真实数据集上的实验结果表明，与当前最先进（SOTA）方法相比，所提方法具有有效性。源代码可通过 https://github.com/HHW-zhou/TDHNN 获取。

1 引言 图结构在社交网络 [Berahmand et al., 2021]、网页搜索 [Wang et al., 2021] 和推荐系统 [Wu et al., 2022] 等实际应用中已被广泛使用，因其能够高效地捕获数据之间的关系。然而，常规图的构建基于成对关系，这使得其难以描述复杂关系。超图可以自然地处理这一问题。超图通过将每条超边与任意数量的节点相连，成为解决上述问题的良好替代方案。因此，超图能够捕获节点之间的复杂关系，从而比普通图具有更强的表达能力。

先前的超图方法可分为两类，即静态超图神经网络（SHGNNs）和动态超图神经网络（DHGNNs）。SHGNNs 通过使用初始化的超图结构来捕获节点之间的关系，从而进行表示学习。为此，HGNN [Feng et al., 2019] 采用了卷积方法，而 HGNN+ [Gao et al., 2022] 则引入了一种基于空间的超图卷积。然而，SHGNNs 高度依赖于初始化的超图结构，该结构通常包含冗余信息，且无法发现节点之间隐藏的关系。为解决这些问题，DHGNNs 被提出以从特征中学习潜在连接，并能够挖掘更多有用信息。例如，[Jiang et al., 2019] 提出结合 kNN 和 k-means 方法重构超图；[Bai et al., 2021] 提出使用连续值构建关联矩阵，并利用注意力机制学习连接权重；DeepHGSL [Zhang et al., 2022] 利用多层超图卷积中的隐藏表示来构建超图；HSL [Cai et al., 2022] 则从初始超图结构中采样超边（即去除冗余超边），并利用注意力机制捕获节点与超边之间更多的关系以用于超图构建。

先前的 DHGNNs 忽略了对超边数量（即超边数目）的调整，导致无法正确探索超图结构。也就是说，无论节点如何分配，超边数量始终保持不变。为解决这一问题，t-DHL [Gao et al., 2020] 尝试通过将超边空间投影到二元张量上来自适应地调整超边数量。然而，该方法属于传统机器学习方法，无法以端到端方式使用，因而难以有效探索节点之间的关系。此外，我们观察到，考虑超边特征对于调整超边数量至关重要。实际上，一条超边连接一组节点，因此这些节点之间的共有信息（简称为超边特征）可用于表征该节点集合。相反，如果某条超边无法通过特定度量（例如本文中超边与所属节点之间的注意力系数）来表征一组节点的共有特征，则该超边并非必要。通过这种方式，超边数量可随超边特征进行更新。然而，大多数数据集缺乏可用的超边特征，且很少有研究关注在超图神经网络中考虑超边特征。

为解决上述问题，本文提出一种新方法，即全动态超图神经网络（Totally Dynamic Hypergraph Neural Network, TDHNN），如图 1 所示，用于学习动态超边特征以更新超边数量，包括四个步骤：超边特征采样、超边特征更新、超图构建和超图卷积。前两个步骤生成超边特征，第三步调整超边数量。因此，先前方法中存在的上述问题得到了探索。特别地，超边特征和超边数量均可随更新后的节点特征进行自适应调整。因此，我们的方法避免了初始超图质量较低所带来的影响。

与先前方法不同，我们所提方法的主要贡献总结如下：

• 我们提出了一种新的端到端动态超图框架，能够动态调整超图结构和超边数量。
• 我们提出了一种基于学习到的超边特征的简洁超图卷积算法。
• 我们提出了一种监督约束损失和一种无监督约束损失，以改进所学习的超图。

2 方法论

2.1 超边特征采样

2.2 超边特征更新

随后，我们提出使用注意力系数来表示每条超边与所有节点之间的相关性。然而，只有当超边特征和节点特征属于同一特征空间时，才能计算注意力 [Bai et al., 2021]，因此我们首先使用一个映射函数 f(⋅) 将输入特征 Xv 映射到超边特征的特征空间：

2.3 超图构建

调整超边数量 由于我们学习的是超边特征的分布而不是固定的超边特征，我们可以通过调整样本数量 mm 来改变超边的数量。挑战在于样本数量是不可微的，我们无法通过反向传播来调整它。从图论的角度来看，如果我们知道什么样的超边和节点关系构成了一个最优超图，我们就能解决这个挑战。然而，这也是一个非常有挑战性的课题，目前尚无相关的理论研究。为了让模型能够自适应地找到更好的采样数量，我们设计了一个简单但有效的评估标准，以判断学习到的超边数量是否合适。我们定义超图的饱和度分数（saturation score）：

2.4 超图卷积简单超图卷积层

随后，我们使用学习到的超边特征和构建的超图来更新节点的特征。[Feng et al., 2019] 提出了首个超图卷积公式：

其中 ww 是一个可训练参数。也就是说，我们在公式 (12) 的基础上加入了节点自身的特征。事实上，公式 (14) 与公式 (13) 同样有效，且计算效率更高。

无监督约束 我们使用带标签的节点来获取监督约束，并希望具有相同标签的节点被划分到同一条超边中；类似地，对于无监督约束，我们希望被划分到同一条超边中的节点更加相似。在监督阶段，我们的约束损失直接应用于 HH，而在无监督阶段，我们在卷积层之后的节点特征上添加了约束：

2.5 与 k-means 的联系与区别

我们构建超图的方式与 k-means 相似。k-means 的主要过程是 (1) 随机选择聚类中心，(2) 聚类，(3) 更新聚类中心，然后重复 (2) 和 (3) 直到收敛。所提出的 TDHNN 的流程是 (1) 采样超边，(2) 将节点分配给每条超边，(3) 更新超边的特征分布，然后重复 (2) 和 (3) 直到收敛。我们的方法与 k-means 的主要区别如下：

• k-means 学习聚类中心的特征，而 TDHNN 学习超边的特征分布；
• k-means 选择固定的 k 个聚类中心，而 TDHNN 根据学习到的超图的饱和度分数动态调整样本数量；
• k-means 中的每个簇是互不相交的，而 TDHNN 的超边之间存在交集。

3 实验

3.1 实验设置数据集

遵循首个超图卷积神经网络的研究工作 [Feng et al., 2019]，我们使用了两个视觉物体分类数据集（即普林斯顿 ModelNet40 [Wu et al., 2015] 和台湾大学 3D 模型（简称 NTU））。其中，ModelNet40 包含 12,311 个物体，共 40 类；NTU 包含 2,012 个物体，总计 67 类 3D 形状。与 [Feng et al., 2019] 类似，我们使用群组视图卷积神经网络（GVCNN）[Feng et al., 2018] 和多视图卷积神经网络（MVCNN）[Su et al., 2015] 进行特征提取，并分别考虑仅使用一组特征以及同时使用两组特征的情况。我们对 ModelNet40 和 NTU 采用了相同的划分标准，即 80% 作为训练集，20% 作为测试集。由于数据集的标准划分使用固定的训练样本，一种方法可能会受到固定数据分布的影响。为了更好地进行比较，我们采用与 [Jiang et al., 2019] 相同的方法，在 Cora [Veličković et al., 2017] 数据集上随机采样不同比例的数据作为训练集。具体而言，除了标准划分外，我们分别选取 2%、5.2%、10%、20%、30% 和 44% 的数据进行训练。

对比方法 我们的对比方法包括两种经典图模型，即 GCN [Kipf and Welling, 2016] 和 GAT [Veličković et al., 2017]；三种超图卷积神经网络，即 HGNN、HGNN+ 和 HNHN [Dong et al., 2020]；以及两种动态超图网络，即 DHGNN、HyperGCN [Yadati et al., 2019]、DeepHGSL [Zhang et al., 2022] 和 HSL [Cai et al., 2022]。我们通过开源工具 PyTorch Geometric [Fey and Lenssen, 2019] 实现 GCN 和 GAT，并通过开源工具 DHG（DeepHypergraph）[Gao et al., 2022] 实现 HGNN、HGNN+、HNHN、HyperGCN 和 DeepHGSL。对于 DHGNN 和 HSL，我们使用其源代码进行实验。

3.2 结果与讨论视觉物体分类

视觉物体分类的实验结果如表 1 所示。无论是在 ModelNet40 还是 NTU 数据集上，无论使用哪一组特征，所提出的 TDHNN 在所有对比方法中均取得了最佳结果。与图算法 GCN 和 GAT 相比，TDHNN 分别平均提升了 2.82% 和 2.88%。与静态超图算法 HGNN、HGNN+ 和 HNHN 相比，TDHNN 分别平均提升了 1.33%、1.6% 和 2.12%。与动态超图算法 DHGNN、HyperGCN、DeepHGSL 和 HSL 相比，我们的分类准确率分别平均提升了 2.22%、2.77%、6.25% 和 1.95%。总体而言，超图算法在 ModelNet40 和 NTU 上的表现优于图算法。然而，某些算法在实验结果中表现出不稳定性。例如，当 HNHN 在 ModelNet40 上分别使用 GVCNN 和 MVCNN 的特征时，显示出较高的准确率（分别为 92.10% 和 91.10%）。然而，当同时融合这两组特征时，准确率的提升并不明显（93.80%）。与其他方法相比，其表现甚至更低，类似的情况也出现在 NTU 上。当 DHGNN 单独使用 MVCNN 的特征时，无论是在 ModelNet40 还是 NTU 上，准确率都相对较低，但在融合这两组特征时却取得了较好的成绩。与这两种方法形成鲜明对比的是，TDHNN 取得了更好的结果，无论是单独使用特定特征还是同时融合两组特征，都表现出更好的稳定性和兼容性。

总体而言，所提出的 TDHNN 具有三个优势：首先，通过应用超图结构，我们可以更好地挖掘数据中的多重关系；其次，我们动态学习超图结构，能够充分挖掘数据中的潜在关系；第三，我们可以动态调整超边数量，以帮助学习更合理的超图结构。

引文网络分类 在 Cora 数据集上使用不同比例样本的实验结果如表 2 所示。如图所示，除了在 2% 的划分比例下（此时准确率为 76.11%，仅次于 DHGNN 的 76.90%，差距为 0.8%）外，TDHNN 在所有其他划分比例下均取得了最佳结果。与图算法 GCN 和 GAT 相比，TDHNN 分别平均提升了 4.11% 和 1.57%。与静态超图算法 HGNN、HGNN+ 和 HNHN 相比，TDHNN 分别平均提升了 3.14%、4.37% 和 6.18%。与动态超图算法 DHGNN、HyperGCN、DeepHGSL 和 HSL 相比，我们的分类准确率分别平均提升了 1.07%、17.38%、2.86% 和 3.09%。具体而言，在 2% 和 5.2% 的划分比例下，HGNN、HGNN+ 和我们的 TDHNN 取得了相对相似的性能。然而，随着训练比例的增加，TDHNN 的优势得以显现，这可能归功于监督约束损失 Ls。

3.3消融研究

所提出的TDHNN包含三个主要组成部分：超边更新器（简称HU）、有监督约束（简称C1）和无监督约束（简称C2）。为了验证各部分的有效性，我们测试了这些组件的不同组合。如表3所示，首先，与仅使用单一组件相比，TDHNN在ModelNet40、NTU和Cora数据集上平均分别提升了1.22%、3.75%和3.13%。在仅使用HU的情况下，模型在各数据集上的表现均可接受，尤其在ModelNet40上达到97.28%，接近使用全部组件时的性能。在仅使用C1的情况下，模型在ModelNet40（94.24%）和NTU（77.74%）上的整体性能大幅下降，但在Cora上略优于仅使用HU的情况（提升0.3%）。当仅使用C2时，ModelNet40上的表现同样非常出色（97.36%），且在Cora上也优于仅使用HU或C1的情况。当任意两个组件组合使用时，与使用单一组件相比，整体性能并未显著提升。具体而言，当组合使用C1和C2时，模型在ModelNet40和NTU上甚至无法收敛（分类准确率分别为7.86%和6.43%）。然而，当同时使用全部三个组件时，模型性能达到最优，且不再出现无法收敛的情况。

3.4 可视化

为了更好地展示TDHNN的能力，我们使用t-SNE算法[Van der Maaten and Hinton, 2008]对模型的嵌入表示进行降维并可视化。我们还计算了嵌入表示的轮廓系数（Silhouette score）[Rousseeuw, 1987]以对其进行评估。为了进行比较，我们在HGNN+和HNHN上进行了相同的实验。实验结果如图2所示。如图所示，在TDHNN的实验结果中，类别之间的边界更加清晰。轮廓系数也证明了这一点：HGNN+和HNHN的轮廓系数分别为0.3531和0.3344，而TDHNN为0.5081，比前两种方法分别高出15.50%和17.34%。

3.5 运行时间

为了验证TDHNN的计算效率，我们将每次迭代所需的时间与最新的动态超图方法进行了比较。如表4所示，在三个数据集上，与DHGNN、HyperGCN和DeepHGSL相比，TDHNN每个epoch平均分别提升了9.44秒、3.01秒和2.31秒。与HSL相比，TDHNN平均慢0.04秒，这是因为HSL是从现有的超图结构中采样并获取新结构，而非使用特征进行重构。此外，我们未将TDHNN与静态方法进行比较，因为这些方法不涉及超图重构。

3.6 灵敏度分析

超图饱和阈值的影响

4 结论

在本文中，我们提出了一种新颖的动态超图学习框架，该框架能够动态调整超图的结构以及超边的数量。据我们所知，这可能是首个以超边特征为中心构建超图的工作，它为超图神经网络的研究与学习开辟了一条新途径。所提出的TDHNN通过学习超边的特征分布，并根据所学超图的饱和度评分来调整样本数量，从而动态调整超图结构。为了使构建的超图更加合理，我们在卷积后的图和特征上提出了两种约束。实验验证了我们方法的有效性。然而，该方法仍有许多方面可以改进。例如，超图饱和度的度量方式以及调整超边数量的策略可能过于简单；超边数量与样本数量之间的关系仍有待进一步探索和理论证明。这些也是我们未来需要继续深入研究和探索的方向。

原文链接：https://www.ijcai.org/proceedings/2023/0275.pdf