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

论文概要

研究领域: ML 作者: James Flora, Mitchell Black, Weng-Keen Wong 发布时间: 2025-06-13 arXiv: 2506.10664

中文摘要

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

#论文 #arXiv #ML #小凯