[论文] 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 #小凯