戴琼海院士团队 | 面向大规模数据的高效超图神经网络

研究意义

高阶关联广泛存在于现实世界中，如社交网络、生物网络、交通网络等，建模及优化高阶关联对于网络属性研究和演化趋势预测具有重要意义。超图是一种灵活的数据结构，能够自然地建模高阶关联。近年来，随着深度学习的发展，基于超图建模的超图神经网络被广泛应用于面向高阶关联的表示学习。然而，现有的超图神经网络均基于直推学习范式，时间、空间复杂度较高，虽然在小规模超图数据集上取得了不错的效果，但难以应用到大规模数据上，限制了其应用范围。

本文工作

本文首先分析了现有超图神经网络方法在大规模数据上应用的挑战，然后针对该问题提出了面向大规模数据的高效超图神经网络方法EHGNN。针对现有方法空间、时间复杂度过高的问题，EHGNN分别设计了超图采样模块和基于单阶段超图卷积的计算加速模块，同时降低了超图神经网络的空间开销和时间开销，使得超图神经网络适用于大规模超图数据，显著增强了可扩展性。

具体而言，针对现有方法空间复杂度过高从而不适用于大规模数据的问题，超图采样模块将从原始大规模数据中构造出的大超图分解为多个规模可控的子超图，从而实现在可控空间复杂度下进行计算。本文进一步提出了两种超图采样方法：分层采样和子超图预采样算法。分层采样基于分层扩散的思想，在超图神经网络的每层卷积层分别对当前超图进行采样，得到多个子超图后再进行分批次的超图卷积。子超图预采样基于中心扩散的思想，预先多层采样获得多个子超图，再进行超图神经网络卷积计算。

针对当前超图神经网络方法基于两阶段消息传递范式从而时间复杂度较高的问题，本文提出了基于 “节点-节点”单阶段超图卷积模块，避免了超边特征的额外计算，提高了超图神经网络的运算效率。具体而言，进行超图神经网络的分批计算时，在当前批次节点集内获取节点间的局部邻接关系，并进行从源节点特征到目标节点特征的特征聚合。

图1 EHGNN的框架图

实验结果

为验证所提出的EHGNN 模型的有效性，本文在 4 个真实世界的超图数据集上进行了实验，包含 2 个大规模超图数据集（Amazon-reviews 和 CIKM19-ECOMM）以及 2 个小规模超图数据集（Walmart-trips 和 House-bills），评估任务为节点分类任务。

实验中选择了五类方法进行对比，包含传统图学习方法、图表示学习方法、图神经网络方法、传统超图学习方法以及超图神经网络方法。下表展示了在4个数据集上的实验结果。

表1 Amazon-reviews数据集实验结果

表2 CIKM19-ECOMM 数据集实验结果

表3 Walmart-trips 数据集实验结果

表4 House-bills 数据集实验结果

从以上实验结果中, 我们可以观察到，在两个大规模超图数据集上，大部分方法均受限于内存无法运行；而在可运行的方法中，所提出的 EHGNN模型在所有指标上均大幅超过对比方法. 例如，在 Amazon-reviews 数据集中的 Accuracy 指标上，EHGNN 超过 DeepWalk 方法约 32 个百分点；在 Precision 指标上，EHGNN 相对于 Deepwalk 性能提高了 45.82%。 在两个小规模超图数据集上，我们可以发现，基于超图的方法性能普遍优于基于图的方法，且EHGNN 在两个数据集的所有指标上均取得了最优结果。例如，对于 House-bills 数据集，HGNN+ 相对于 GraphSAGE 方法在 Recall 指标上取得了 25.79% 的性能提升。特别地，所提出的模型 EHGNN 相对于 GraphSAGE 在 Recall 指标上取得了 31.65% 的性能提升。这主要是因为图结构由于其固有限制，难以建模超图数据中节点间的高阶关联，基于超图团扩展获得的简单图相对于原超图存在信息损失。而 EHGNN 能够更好地建模数据间的高阶关联，从而获得更优的性能。

本文还对比了 EHGNN 模型和基准方法的时空运行效率。图 6 进一步展示了 EHGNN 与对比方法在 4 个数据集上的空间开销-准确率分布。从图中可以发现，在两个大规模数据集 Amazon-reviews 和 CIKM19-ECOMM 上，EHGNN 模型在分类精度和空间开销两方面均取得了优势——分类精度最高，内存占用最小。而在两个小规模数据集 Walmart-trips 和 House-bills 上，EHGNN 仍在所有方法中取得了最好的预测性能。在空间开销方面，虽然EHGNN 模型的内存占用要稍高于部分对比方法，但所占用空间均属于同一数量级，且为主流商用服务器能够支持的性能范围，并不会制约方法应用。以上实验结果表明，在空间开销成为关键制约因素的大规模数据集上，EHGNN 在分类精度和空间开销两方面均能取得显著优势；而在小规模数据集上，EHGNN 也能够拥有最优分类性能。

图2  4 个数据集上各方法的空间开销-准确率分布