用行走路径矩阵替代消息传递，提升图神经网络效率与泛化性
Caterpillar GNN: Replacing Message Passing with Efficient Aggregation
- 基于行走路径的结构化聚合，降低计算复杂度
- 在挑战性基准上表现优于传统消息传递模型
- 适合追求高效、可解释图学习的开发者使用
消息传递图神经网络（MPGNN）主导现代图学习。现有方法通过丰富邻接关系聚合来增强表达能力。本文提出一种基于行走路径关联矩阵的高效聚合机制，主动牺牲部分表达力以获得更强且更结构化的归纳偏置。该方法可在经典消息传递与基于行走的简化方法间无缝缩放。我们通过广义毛毛虫图的同态计数，严格刻画了各中间步骤的表达能力。基于此，提出Caterpillar GNN，其鲁棒的图级聚合在专为挑战MPGNN设计的基准上表现优异。此外，在真实数据集上，Caterpillar GNN实现相当预测性能的同时，显著减少隐藏层中的节点数量。
原文摘要 · Abstract (English)
Message-passing graph neural networks (MPGNNs) dominate modern graph learning. Typical efforts enhance MPGNN's expressive power by enriching the adjacency-based aggregation. In contrast, we introduce an efficient aggregation over walk incidence-based matrices that are constructed to deliberately trade off some expressivity for stronger and more structured inductive bias. Our approach allows for seamless scaling between classical message-passing and simpler methods based on walks. We rigorously characterize the expressive power at each intermediate step using homomorphism counts over a hierarchy of generalized caterpillar graphs. Based on this foundation, we propose Caterpillar GNNs, whose robust graph-level aggregation successfully tackles a benchmark specifically designed to challenge MPGNNs. Moreover, we demonstrate that, on real-world datasets, Caterpillar GNNs achieve comparable predictive performance while significantly reducing the number of nodes in the hidden layers of the computational graph.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。