arXiv:2412.08835cs.LG2024-12被引 1

用代数拓扑重构图神经网络基础,突破传统邻域限制。

Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs

  • 以覆盖代替邻域作为消息传递基础,基于范畴论构建新框架。
  • 在多个图同构基准上零失败,显著提升拓扑感知能力。
  • 适合研究图神经网络理论、拓扑建模与高阶结构学习的学者。

图神经网络(GNN)几乎都依赖单一原始结构:邻域。无论架构如何变化,消息传递最终都基于邻域聚合,这从根本上限制了表达能力,通常仅达到Weisfeiler-Lehman(WL)测试的强度。本文挑战这一范式,提出Grothendieck图神经网络(GkGNN)框架,严格将邻域扩展为覆盖,并以此取代邻域作为消息传递的基本对象。邻域与邻接矩阵可视为特例,而覆盖则提供了一种原则性强且灵活的拓扑感知传播机制。GkGNN形式化了覆盖,并系统性地将其转化为矩阵,类似于邻接矩阵编码邻域,从而支持理论分析与实际实现。在此框架下,我们引入源自范畴论的筛覆盖(cover of sieves),捕捉丰富的拓扑结构。基于此,设计了筛神经网络(SNN),一种固定覆盖的典型实例,可推广邻接矩阵。实验表明,SNN在挑战性图同构基准(SRG、CSL、BREC)上实现零失败,并通过受控标签传播探测显著提升拓扑感知性能。结果确立了GkGNN作为替代邻域的奠基性框架。

原文摘要 · Abstract (English)

Graph Neural Networks (GNNs) are almost universally built on a single primitive: the neighborhood. Regardless of architectural variations, message passing ultimately aggregates over neighborhoods, which intrinsically limits expressivity and often yields power no stronger than the Weisfeiler-Lehman (WL) test. In this work, we challenge this primitive. We introduce the Grothendieck Graph Neural Networks (GkGNN) framework, which provides a strict algebraic extension of neighborhoods to covers, and in doing so replaces neighborhoods as the fundamental objects of message passing. Neighborhoods and adjacency matrices are recovered as special cases, while covers enable a principled and flexible foundation for defining topology-aware propagation schemes. GkGNN formalizes covers and systematically translates them into matrices, analogously to how adjacency matrices encode neighborhoods, enabling both theoretical analysis and practical implementation. Within this framework, we introduce the cover of sieves, inspired by category theory, which captures rich topological structure. Based on this cover, we design Sieve Neural Networks (SNN), a canonical fixed-cover instantiation that generalizes the adjacency matrix. Experiments show that SNN achieves zero observed failures on challenging graph isomorphism benchmarks (SRG, CSL, BREC) and substantially improves topology-aware evaluation via a controlled label-propagation probe. These results establish GkGNN as a principled foundational framework for replacing neighborhoods in GNNs.

图神经网络拓扑感知代数框架范畴论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。