更强大的图神经网络反而可能泛化更差，关键看训练数据够不够
Graph Representational Learning: When Does More Expressivity Hurt Generalization?
- 用预度量衡量图结构相似性，分析表达能力与泛化的关系
- 发现模型越强需更多数据或更接近的测试图才能保持性能
- 理论结合实验，适合研究图学习泛化性的读者
图神经网络（GNN）是处理结构化数据的强大工具，但其表达能力与预测性能之间的关系仍不明确。本文提出一类预度量，用于捕捉图之间不同程度的结构相似性，并将其与泛化能力关联，进而影响高表达力GNN的性能。在图标签与结构特征相关的情况下，推导出依赖于训练与测试图间距离、模型复杂度和训练集大小的泛化界。结果表明，若缺乏足够大的训练集或训练/测试图距离过远，更表达力的GNN反而会泛化更差。研究揭示了表达力与泛化之间的权衡关系，理论分析得到实证支持。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) are powerful tools for learning on structured data, yet the relationship between their expressivity and predictive performance remains unclear. We introduce a family of premetrics that capture different degrees of structural similarity between graphs and relate these similarities to generalization, and consequently, the performance of expressive GNNs. By considering a setting where graph labels are correlated with structural features, we derive generalization bounds that depend on the distance between training and test graphs, model complexity, and training set size. These bounds reveal that more expressive GNNs may generalize worse unless their increased complexity is balanced by a sufficiently large training set or reduced distance between training and test graphs. Our findings relate expressivity and generalization, offering theoretical insights supported by empirical results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。