保持图上位置/距离/度来提升GNN表示能力

GNN的经典操作是聚合邻居信息来学习节点表示。在这个过程中，GNN很好的保持了图上的邻居结构，如K层GNN保持了图上的K阶邻居信息。另一方面，图上一些性质(节点之间的距离和位置，节点的度等)对于下游任务也是非常重要的。

image-20210622234209893

这里推荐3篇如何在GNN中保持图的位置/距离/度等信息并本质的提升GNN的表示能力。

image-20210623002207189

其中， Do Transformers Really Perform Bad for Graph Representation?拿到了OGB Graph-level 预测任务上的第一名。

19ICML P-GNN Position-aware Graph Neural Networks

image-20210623000116614

本文来自斯坦福Jure组，算是很早将节点位置信息注入到GNN聚合过程和节点表示中去的工作。对于position-aware，文中给出了清晰的定义，简单来说：节点对的向量表示能够反映其之间的距离(最短路径距离SPD)。

Definition 1. A node embedding

is position-aware if there exists a function

such that

, where

is the shortest path distance in

.

那如何具体来描述节点之间的距离呢？这里采取了一种间接的策略：

• 首先选取一些节点集合作为地标，文中叫做anchor-set，其相当于地平线。
• 计算所有节点到地标的距离。

可以看出，这里算的是绝对距离，通过节点到地标的距离来间接反映节点之间的距离。

下图中选取了3个anchor-set

，其中anchor-set

。

这种做法有2个问题：

• anchor-set如何选？选几个？每个里面有几个节点？
• 算的是绝对距离，所以无法Inductive。比如新来一张图，无法直接进行预测。

image-20210622235130513

20NIPS Distance Encoding – Design Provably More Powerful Graph Neural Networks for Structural Representation Learning

image-20210623000052785

本文还是来自斯坦福Jure组，探究了节点之间的距离编码(distance encoding, DE)对于GNN能力的提升作用。

和上一篇P-GNN最大的不同在于，DE是直接计算节点对之间的相对距离，并对其进行编码和注入到GNN中去的。

优点是直接计算计算节点对之间的SPD确保了GNN的Inductive能力，且省去了选取anchor-set的麻烦。问题在于SPD的计算也会增加耗时的。

Do Transformers Really Perform Bad for Graph Representation?

image-20210623000033757

这篇文章拿到了OGB Graph-level 预测任务上的第一名。

image-20210623000237136

本文提出了以下3种编码技术。

• Centrality Encoding，主要是编码节点的度的信息，当做初始节点属性的一部分。直观的想，度越大，节点越重要。

其中，

和

分别代表节点的入度和出度。

• Spatial Encoding，其实就是将节点对之间的SPD

映射了一下。

• Edge Encoding，编码了最短路径上边的信息。本文是针对分子图来设计的，分子之间的不同化学键代表了不同类型/强度的相关性。

代码：https://github.com/Microsoft/Graphormer.