提出消息传递复杂度，更真实地评估图神经网络性能。
What Expressivity Theory Misses: Message Passing Complexity for GNNs
- 用连续指标衡量图神经网络的消息传递难度。
- 实验证明该指标与模型实际表现高度相关。
- 适合关注模型实际效果而非理论表达能力的研究者。
表达能力理论是分析图神经网络（GNN）的主流框架，旨在判断模型能区分哪些图结构。然而，我们指出这一焦点存在偏差：一方面，多数现实任务并不要求超过基础WL测试的表达能力；另一方面，表达能力理论采用二元判定和理想化假设，难以反映实际性能。为此，本文提出消息传递复杂度（MPC），一个连续量化的指标，用于衡量特定任务中GNN架构进行消息传递的难度。MPC不仅捕捉了如过挤现象等实践限制，还保留了表达能力理论中的不可行性结论，有效弥合理论与实践之间的差距。在多个基础GNN任务上的广泛验证表明，MPC的理论预测与实际性能高度一致，成功解释了不同架构的成功与失败。因此，MPC超越了传统表达能力理论，为理解与改进GNN架构提供了更强大、更细致的分析框架。
原文摘要 · Abstract (English)
Expressivity theory, characterizing which graphs a GNN can distinguish, has become the predominant framework for analyzing GNNs, with new models striving for higher expressivity. However, we argue that this focus is misguided: First, higher expressivity is not necessary for most real-world tasks as these tasks rarely require expressivity beyond the basic WL test. Second, expressivity theory's binary characterization and idealized assumptions fail to reflect GNNs' practical capabilities. To overcome these limitations, we propose Message Passing Complexity (MPC): a continuous measure that quantifies the difficulty for a GNN architecture to solve a given task through message passing. MPC captures practical limitations like over-squashing while preserving the theoretical impossibility results from expressivity theory, effectively narrowing the gap between theory and practice. Through extensive validation on fundamental GNN tasks, we show that MPC's theoretical predictions correlate with empirical performance, successfully explaining architectural successes and failures. Thereby, MPC advances beyond expressivity theory to provide a more powerful and nuanced framework for understanding and improving GNN architectures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。