揭示图神经网络中截断位置编码的表达能力差异，指导实际应用选择。
Understanding Truncated Positional Encodings for Graph Neural Networks
- 分析截断谱编码与行走编码的表达力差异
- 证明截断后谱编码不再强于1-WL测试
- 实验证明混合使用更优，适合真实图数据
位置编码（PEs）能提升图神经网络（GNN）的表达能力，理论上和实践中均有效。谱系（如拉普拉斯特征空间、有效电阻）与行走基（邻接矩阵多项式）两类编码在完整形式下具有相同表达力，介于1-WL与3-WL测试之间。但完整形式需O(n³)时间与空间复杂度，实践中常使用截断版本（如前k个特征空间或邻接矩阵前k次幂）。本文首次研究此类截断编码的理论性质。理论表明：截断后不同编码家族表达力本质不同；作为推论，截断谱编码不再超越1-WL测试。通过研究一种谱系编码——k-调和距离，进一步凸显相近编码在截断下的表达力差异。实验显示，在真实数据集上，混合使用截断编码优于单一编码家族。
原文摘要 · Abstract (English)
Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.g., Laplacian eigenspaces, effective resistance) and walk-based (polynomials of the adjacency matrix) - are theoretically equivalent in expressive power, with expressivity between the 1-WL and 3-WL tests. However, this equivalence assumes the GNN uses the "complete" version of these PEs, which requires $O(n^3)$ time and space complexity. Instead, practitioners commonly use truncated variants of these encodings, such as the first $k$ eigenspaces or powers of the adjacency matrix. However, the theoretical properties of these truncated PEs are unknown. In this work, we initiate the study of these truncated PEs. Theoretically, we show that, under truncation, several families of PEs are fundamentally different in expressive power. As a corollary, we show that truncated spectral PEs are no longer stronger than the 1-WL test. We also study a family of spectral PEs, the $k$-harmonic distances, to highlight the differences in expressive power of even closely related truncated PEs. Finally, we experimentally show that a mix of truncated PEs is preferable to any single family on real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。