[论文] Understanding Truncated Positional Encodings for Graph Neural Networks

论文概要

研究领域: ML 作者: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri 发布时间: 2026-06-11 arXiv: 2606.13671

中文摘要

位置编码（PEs）在理论上和实证上都增强了图神经网络（GNN）的能力。两个最流行的 PE 家族——谱系（例如，拉普拉斯特征空间、有效电阻）和基于游走（邻接矩阵的多项式）——在表达能力上理论上是等价的，表达能力介于 1-WL 和 3-WL 测试之间。然而，这种等价性假设 GNN 使用这些 PE 的"完整"版本，这需要 O(n^3) 的时间和空间复杂度。相反，实践者通常使用这些编码的截断变体，例如前 k 个特征空间或邻接矩阵的幂。然而，这些截断 PE 的理论性质是未知的。在这项工作中，我们发起了对这些截断 PE 的研究。理论上，我们表明，在截断下，几个 PE 家族在表达能力上根本不同。作为推论，我们表明截断谱系 PE 不再比 1-WL 测试更强。我们还研究了一个谱系 PE 家族，k-谐波距离，以突出即使密切相关的截断 PE 之间的表达能力差异。最后，我们在真实世界数据集上实验表明，混合截断 PE 优于任何单一家族。

原文摘要

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, w...

--- *自动采集于 2026-06-15*

#论文 #arXiv #ML #小凯