Understanding Truncated Positional Encodings for Graph Neural Networks
English summary
This paper studies the theoretical expressiveness of truncated positional encodings (PEs) for graph neural networks, which are commonly used in practice for computational efficiency. It shows that under truncation, previously equivalent PE families (spectral and walk-based) become fundamentally different in expressive power, with truncated spectral PEs losing their advantage and becoming no stronger than the 1-WL test. The authors introduce k-harmonic distances to further compare closely related truncated spectral PEs. Experiments on real-world datasets demonstrate that mixing different truncated PE families yields better performance than using any single family.
Chinese summary
本文研究了图神经网络中截断位置编码的理论表达能力，这些编码因计算效率而在实践中普遍使用。研究表明，在截断条件下，原本表达能力等价的谱编码和游走编码系列产生了根本性差异，其中截断谱编码不再强于1-WL测试。作者引入了k-调和距离来进一步对比相近的截断谱编码。在真实数据集上的实验表明，混合不同截断编码系列的表现优于使用任何单一编码系列。
Key points
The paper provides the first theoretical analysis of truncated positional encodings (PEs) for GNNs, filling a gap between common practice and theoretical understanding.
首次对图神经网络中常用的截断位置编码进行理论分析，填补了实践与理论之间的空白。
It proves that truncation breaks the expressive equivalence among different PE families; specifically, truncated spectral PEs are no longer more powerful than the 1-WL test.
证明截断打破了不同位置编码系列之间的表达能力等价性；具体而言，截断的谱编码不再比1-WL测试更强。
The study introduces k-harmonic distances as a tool to examine fine-grained expressive differences among truncated spectral PEs.
引入k-调和距离作为工具，考察截断谱编码之间更细微的表达能力差异。
Experiments show that combining multiple truncated PE types (a mix) outperforms using any single family on real-world graph datasets.
实验表明，在真实图数据集上，混合使用多种截断位置编码类型的效果优于单独使用任何单一系列。