图神经网络（GNNs）已成为处理图结构学习任务的基石，尤其是在消息传递神经网络（MPNNs）的框架下，因其能够利用局部邻居信息进行高效计算而广受欢迎。然而，一个长期存在的理论瓶颈限制了其进一步发展：标准的MPNNs的表达能力被证明不会超过经典的图同构测试——一维Weisfeiler-Lehman（1-WL）算法。这意味着，对于那些在1-WL测试下无法区分的非同构图，传统的GNNs也无法为它们学习出不同的表示。为了突破这一限制，研究者们探索了多种途径，例如注入预计算的结构特征、利用高阶子结构、扩展消息传递的感受野，或者基于子图进行处理。尽管如此，目前的研究对于图中不同类型结构成分（例如，捕获不同图性质的子图）之间如何相互作用，以及这些相互作用如何影响图表示的学习能力，仍然缺乏深入的理解。现有的工作大多局限于学习顶点与其邻居之间的简单交互，缺乏揭示不同特性结构成分之间复杂交互的能力。
为了应对上述挑战，来自澳大利亚国立大学计算学院图形研究实验室的Asela Hevapathige和Qing Wang在《Neural Networks》上发表了一项研究。他们的核心洞见在于：以一种置换不变的方式对图进行分割，能够保留图的内在结构属性，从而为探索图中不同结构成分之间的交互提供一种强大而有效的方法。现实世界中的图通常由具有不同拓扑特性的结构成分组成，探索这些成分及其相互作用不仅能带来对图结构的新见解，也能为图表示学习注入新的能力。基于此，他们提出了图分割神经网络（GPNN），这是一个旨在通过置换不变的图分割来整合结构交互，从而增强图表示学习的新架构。
研究人员开展此项研究主要运用了几个关键技术方法。首先是理论框架构建，他们引入了“分割同构”和“交互同构”的新概念，建立了图分割与图同构之间的理论联系，为分析结构交互提供了严格的数学基础。其次是GPNN架构设计，该架构核心是“分割着色”方案，根据预定的置换不变分割方案（如基于节点度或k-核的分割）为顶点和边分配颜色，以区分分区内交互、分区间交互和无交互三种类型，并设计了相应的消息传递机制来聚合来自不同颜色分区的邻居信息。最后是表达能力与复杂度分析，他们从理论上证明了GPNN变体在表达能力上超越1-WL并高效逼近3-WL，同时分析了不同分割方案和交互类型下的计算复杂度，在表达力与效率之间取得了平衡。
研究结果
- •
3. 图分割与图同构：本研究首先形式化地定义了置换不变的图分割方案。在此基础上，引入了两个新的同构概念——“分割同构”和“交互同构”。研究证明，如果两个图是同构的，那么它们一定是交互同构的，但反之则不然；同样，如果两个图是交互同构的，那么它们一定是分割同构的，但反之也不然。这建立了一个严格的理论层次，将图分割与经典的图同构问题联系起来，为后续的模型表达能力分析奠定了基础。
- •
4. 提出的GNN架构：基于上述理论，研究者提出了GPNN。其核心创新在于“分割着色”：根据一个置换不变的分割方案（例如，按节点度或k-核值分割），为每个顶点分配一个分区颜色，并为每对顶点根据它们是否相连以及是否属于同一分区，分配一个边交互颜色（区分分区内边、分区间边和无边）。GPNN的消息传递机制同时更新顶点嵌入和顶点对之间的交互嵌入，并最终将来自不同颜色分区（即不同结构成分）的邻居信息进行区分和组合，从而显式地建模了结构成分内部及之间的交互。
- •
5. 模型实现：论文提供了GPNN的具体实现方案。顶点嵌入和交互嵌入的更新分别通过多层感知机（MLP）实现，并聚合来自邻居的信息。最终顶点的组合嵌入由来自各颜色分区的聚合信息组合而成。重要的是，GPNN可以作为一个插件模块集成到现有的GNN模型（如GIN、GCN）中，与这些模型学到的顶点表示相结合，进一步增强其表达能力。
- •
表达力分析：研究对GPNN的表达能力进行了深入的理论分析。结果表明，GPNN的表达能力超越了1-WL。具体而言，在仅考虑分区内边的交互类型（E⋆）下，GPNN的表达能力严格高于1-WL；当同时考虑分区内和分区间边的交互类型（E⋄）时，其表达能力进一步提升；若考虑所有顶点对（包括无边连接）的交互类型（E†），GPNN的表达能力可以高效地逼近3-WL。这从理论上证实了通过置换不变分割来建模结构交互能够显著增强GNN的表达能力。
- •
复杂性分析：研究还分析了GPNN不同变体的计算复杂度。通过选择不同的分割方案（如λ⊥、λ≤1-WL、λ≥3-WL）和交互类型，GPNN能够在表达能力和计算效率之间进行灵活的权衡，使其适用于不同规模和图结构的任务，具备了实际应用的可行性。
研究结论与意义
本研究的核心结论是，通过置换不变的图分割来显式地建模图中结构成分之间的交互，是一种有效且高效地增强图神经网络表达能力的新途径。研究者提出的GPNN架构不仅在理论上被证明能够超越传统GNN的1-WL上限，并高效逼近更强大的3-WL，而且在实验中于多种图基准任务上展现出了优于现有先进模型的性能。
这项研究的重要意义体现在多个层面。在理论层面，它建立了图分割与图同构之间的新颖理论联系，引入了“分割同构”和“交互同构”的概念，为理解和分析图的结构交互提供了新的理论框架。在方法层面，GPNN为解决GNN表达能力受限这一根本问题提供了一种新的、与现有高阶GNN、结构增强GNN和子图GNN等方案有本质区别的架构思路。它避免了高阶GNN的高计算成本、结构增强GNN对专家知识的依赖以及子图GNN的重叠计算问题，提供了一种全局、一次分割、显式建模交叉交互的高效方案。在应用层面，GPNN的良好可扩展性以及其作为插件模块的灵活性，使其有潜力广泛应用于社交网络分析、生物信息学、推荐系统等需要深刻理解复杂图结构关系的现实任务中，推动图表示学习技术在更复杂场景下的应用。
