【斯坦福】 距离编码-为结构表示学习设计更强大的GNN.

从图结构数据中学习节点集的结构表示对于从节点角色发现到链接预测和分子分类的各种应用至关重要。图神经网络（GNNs）在结构表示学习方面取得了巨大的成功。然而：

大多数 GNN 受到 1-Weisfeiler-Lehman（WL）test 的限制，因此有可能为实际上不同的结构和图形生成相同的表示。 最近通过模仿高阶 WL tests 提出的更强大的 GNN 只关注全图表示，不能利用图结构的稀疏性来提高计算效率。 这篇文章提出了一类与结构相关的特征，称为距离编码(Distance Encoding，DE)，以帮助 GNN 以比 1-WL test 更严格的表达能力来表示任意大小的节点集。DE 本质上捕获了要学习表示的节点集与图中每个节点之间的距离，其中包括与图相关的重要度量，如最短路径距离和广义 PageRank 得分。

此外，此文还提出了两个通用的 GNNs 框架来使用 DEs：

作为额外的节点属性 进一步作为 GNNs 中消息聚合的控制器 这两个框架仍然可以利用稀疏结构来保持处理大型图的可扩展性。

理论上，作者证明了这两个框架可以区分传统 GNN 经常失效的几乎所有规则图中嵌入的节点集。还严格分析了它们的局限性。 实验上，作者在6个真实网络上分别从节点结构角色预测、链路预测和三角形预测三个方面对这两个框架进行了实证评估。 结果表明，DE-assisted GNNs 的平均准确率比没有 DEs 的 GNNs 提高了15%，DE-assisted GNNs 的性能也明显优于专门为这些相应任务设计的其他最先进的基线。