Graph neural networks (GNNs) are the primary tool for processing graph-structured data. Unfortunately, the most commonly used GNNs, called Message Passing Neural Networks (MPNNs) suffer from several fundamental limitations. To overcome these limitations, recent works have adapted the idea of positional encodings to graph data. This paper draws inspiration from the recent success of Laplacian-based positional encoding and defines a novel family of positional encoding schemes for graphs. We accomplish this by generalizing the optimization problem that defines the Laplace embedding to more general dissimilarity functions rather than the 2-norm used in the original formulation. This family of positional encodings is then instantiated by considering p-norms. We discuss a method for calculating these positional encoding schemes, implement it in PyTorch and demonstrate how the resulting positional encoding captures different properties of the graph. Furthermore, we demonstrate that this novel family of positional encodings can improve the expressive power of MPNNs. Lastly, we present preliminary experimental results.
翻译:图形神经网络 (GNNs) 是处理图形结构数据的主要工具。 不幸的是,最常用的GNNs, 称为信息传递神经网络(MPNNs), 受到一些基本限制。 为了克服这些限制, 最近的工作将定位编码的概念改成了图形数据。 本文从基于 Laplacian 的定位编码最近的成功中汲取了灵感, 并定义了图表定位编码方案的新式组合。 我们通过概括优化问题来完成这一点, 优化问题定义了 Laplace 嵌入更一般的差异函数, 而不是原始配方中使用的 2- 诺姆 。 定位编码的这一组随后通过考虑 p- norms 进行即时化。 我们讨论计算这些定位编码计划的方法, 在 PyTorrch 中实施, 并演示由此产生的定位编码如何捕捉取图形的不同属性 。 此外, 我们证明定位编码的新组可以改善 MPNes 的表达力。 最后, 我们提出初步实验结果 。