如何构建大图上的线性复杂度Transformer？本文将要介绍的发表于NeurIPS22的工作对这一开放问题给出了探索性的思路，这项工作也入选了会议的Spotlight Presentation（比例约5%）。

论文题目：NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification

作者信息：吴齐天，赵文滔，李泽楠，David Wipf，严骏驰

论文地址：https://openreview.net/pdf?id=sMezXGG5So

项目地址：https://github.com/qitianwu/NodeFormer

简介

尽管图神经网络（以下简称GNN）目前已成为对图结构数据建模和表征的主流范式，其“沿着固定输入图结构进行信息传递”的设计思想也暴露出了诸多不足。由于每层聚合只考虑相邻节点间的信息传递，这种有限的感受野（receptive field）设计使得GNN无法有效利用来自其他节点的全局信息。此外，在很多下游任务中，输入数据可能并不包含图结构（如图片分类中，每张图片样本是独立的），此时GNN对输入图结构的依赖性导致其无法正常工作。

本文提出了一种新型的图表征模型架构，称为NodeFormer，它实现了每层任意两两节点间的信息传递，即在每层的信息聚合中会考虑图中所有其他节点对当前节点的影响。NodeFormer设计思想的直观理解就是把GNN定义在了一个两两节点潜在相连且每层的图拓扑可学习的计算图上。 然而，这种简单直接的设计思想却带来了令人望而却步的计算复杂度（节点数目的平方级复杂度），使其无法扩展到大规模节点分类图上。为此本文提出了一种具有线性复杂度的可变图结构信息传递方法，使得上述思路首次成功扩展到了百万级规模的节点分类图上，这一方法还能被用于处理没有输入图的问题。

研究背景

虽然GNN在众多图数据建模的任务上都取得了优异的表现，但其在很多场景下暴露出的不足目前也备受关注。例如，GNN对于图中“遥远”的节点会过度挤压（over-squashing），在聚合过程中稀释掉这部分信息；GNN有限的感受野使其难以捕捉长距离依赖（long-range dependence）；GNN聚合邻居信息的设计不能很好兼容包含异配关系（heterophily）或连边残缺的图；以及在极端的没有输入图的情况下，GNN就无法正常工作了。

图片
GNN的核心设计思想与在常见情况下的局限性

这一系列的问题和局限性都源自GNN的核心设计思想“沿着固定输入图结构进行信息传递”，这也启发了我们是否能构建一个不依赖于固定输入图的模型，可以在一个更灵活的隐式图上实现两两节点的信息传递。

内容中包含的图片若涉及版权问题，请及时与我们联系删除