[论文] 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...

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

#论文 #arXiv #ML #小凯