超图神经网络的强大力度如何？

《IEEE Transactions on Pattern Analysis and Machine Intelligence》：How Powerful are Hypergraph Neural Networks?

　　

摘要：

同构识别对于分析复杂网络结构至关重要。传统方法如Weisfeiler-Lehman（WL）核和各种图神经网络（GNN）往往忽视了实际应用所需的高阶交互。此外，超图WL核方法难以区分均匀正则超图，因为它们仅关注邻域连通性，而无法有效捕捉独特的高阶结构。为克服这些问题，我们提出了超图身份感知子树核（IA Subtree Kernel），通过同时考虑邻域连通性和连接密度来区分均匀正则超图。该核方法通过不同长度的闭合路径的变化来检测超图结构中的细微差异。此外，我们开发了两种超图神经网络：超图同构网络（HGIN）和身份感知超图同构网络（IA-HGIN）。这些模型结合了超图WL子树核的优势和先进的神经网络架构，通过整合闭合路径分布的特征来提高分类性能。我们还首次提供了基于核的方法与神经网络在表达能力方面的全面理论比较，确认了IA-HGIN的优越性能。在八个合成数据集和八个真实超图数据集上的实验结果验证了我们的方法相对于现有最先进方法的有效性。

I. 引言

同构识别对于分析复杂网络至关重要，其中结构特征决定了功能，例如与蛋白质折叠结构相关的蛋白质功能[1]以及受神经元连接影响的脑功能[2]、[3]。相同的同构子结构是系统功能分析的关键范式[4]。许多研究使用图结构对复杂网络的结构进行建模，从而产生了大量关注同构识别和子结构分析的研究工作。然而，复杂网络本身包含许多高阶结构（涉及三个或更多元素的交互），这些结构无法用图来建模。因此，基于图的同构识别方法，如Weisfeiler-Lehman（WL）核[5]、[6]和GNN/GIN方法[7]、[8]、[9]，本身就存在局限性：基于图的建模和分析方法受到图表示能力的限制，丢失了高阶结构信息，从而限制了其实际应用性能。相比之下，超图能够全面覆盖低阶和高阶关联建模。因此，超图的同构分析方法[10]、[11]逐渐引起了研究人员的关注。