1维GNN即使简单也难泛化，因VC维无限
A note on the VC dimension of 1-dimensional GNNs
- 用VC维分析1维GNN泛化能力，发现参数少时仍无限
- 无论是否用多项式激活函数，结果均显示无限VC维
- 适合研究GNN理论局限的学者关注
图神经网络（GNN）已成为分析图结构数据的关键工具，能捕捉复杂关系信息。尽管其表达能力（如等价于1-WL同构测试）已有充分研究，但泛化能力仍需深入理解。本文通过考察Vapnik-Chervonenkis（VC）维，研究GNN的泛化性能。我们扩展了先前结果，证明单参数的1维GNN在无界图上具有无限VC维。此外，该结论对使用解析非多项式激活函数的GNN同样成立，包括最近被证明与1-WL测试等价的1维GNN。这些结果表明，从VC维视角看，即使是结构最简单的GNN也存在固有的泛化局限。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) have become an essential tool for analyzing graph-structured data, leveraging their ability to capture complex relational information. While the expressivity of GNNs, particularly their equivalence to the Weisfeiler-Leman (1-WL) isomorphism test, has been well-documented, understanding their generalization capabilities remains critical. This paper focuses on the generalization of GNNs by investigating their Vapnik-Chervonenkis (VC) dimension. We extend previous results to demonstrate that 1-dimensional GNNs with a single parameter have an infinite VC dimension for unbounded graphs. Furthermore, we show that this also holds for GNNs using analytic non-polynomial activation functions, including the 1-dimensional GNNs that were recently shown to be as expressive as the 1-WL test. These results suggest inherent limitations in the generalization ability of even the most simple GNNs, when viewed from the VC dimension perspective.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。