用逻辑框架揭示图Transformer的表达能力边界
Expressive Power of Graph Transformers via Logic
- 通过一阶逻辑和模态逻辑分析图Transformer的表达能力
- 浮点数下GPS网络等价于带计数全局模态的模态逻辑
- 为图神经网络提供可证明的表达能力理论依据
Transformers是现代大语言模型的基础，但其在图结构上的表达能力尚不明确。本文研究了Dwivedi与Bresson（2020）提出的图Transformer（GTs）以及Rampásek等（2022）提出的GPS网络在软注意力和平均硬注意力下的表达能力。研究涵盖实数理论设定与更实际的浮点数情形。在实数设定下，当仅考虑一阶逻辑（FO）可定义的顶点属性时，GPS网络具有与带全局模态的分级模态逻辑（GML）相同表达能力；在浮点数设定下，其表达能力等价于带计数全局模态的GML。该结果为全局属性表达提供了绝对性刻画，不限于背景逻辑中的性质。类似地，对于图Transformer，其在实数下等价于带全局模态的命题逻辑，在浮点数下等价于带计数全局模态的命题逻辑。
原文摘要 · Abstract (English)
Transformers are the basis of modern large language models, but relatively little is known about their precise expressive power on graphs. We study the expressive power of graph transformers (GTs) by Dwivedi and Bresson (2020) and GPS-networks by Rampásek et al. (2022), both under soft-attention and average hard-attention. Our study covers two scenarios: the theoretical setting with real numbers and the more practical case with floats. With reals, we show that in restriction to vertex properties definable in first-order logic (FO), GPS-networks have the same expressive power as graded modal logic (GML) with the global modality. With floats, GPS-networks turn out to be equally expressive as GML with the counting global modality. The latter result is absolute, not restricting to properties definable in a background logic. We also obtain similar characterizations for GTs in terms of propositional logic with the global modality (for reals) and the counting global modality (for floats).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。