Graph Transformers, emerging as a new architecture for graph representation
learning, suffer from the quadratic complexity on the number of nodes when
handling large graphs. To this end, we propose a Neighborhood Aggregation Graph
Transformer (NAGphormer) that treats each node as a sequence containing a
series of tokens constructed by our proposed Hop2Token module. For each node,
Hop2Token aggregates the neighborhood features from different hops into
different representations, producing a sequence of token vectors as one input.
In this way, NAGphormer could be trained in a mini-batch manner and thus could
scale to large graphs. Moreover, we mathematically show that compared to a
category of advanced Graph Neural Networks (GNNs), called decoupled Graph
Convolutional Networks, NAGphormer could learn more informative node
representations from multi-hop neighborhoods. In addition, we propose a new
data augmentation method called Neighborhood Augmentation (NrAug) based on the
output of Hop2Token that augments simultaneously the features of neighborhoods
from global as well as local views to strengthen the training effect of
NAGphormer. Extensive experiments on benchmark datasets from small to large
demonstrate the superiority of NAGphormer against existing graph Transformers
and mainstream GNNs, and the effectiveness of NrAug for further boosting
NAGphormer.

本研究提出了一种称为邻域聚合图变换器（NAGphormer）的方法，用于处理大规模图数据，它将每个节点视为一个序列，每个序列包含一系列通过 Hop2Token 模块构建的标记。NAGphormer 通过从不同跳的邻域特征进行聚合，生成一系列标记向量作为输入，能够以 mini-batch 的方式进行训练，并能够比图神经网络更好地学习多跳邻域的节点表示。研究同时提出了一种名为 Neighborhood Augmentation 的新型数据增强方法，以同时增强全局邻域和局部邻域的特征，进一步提高 NAGphormer 的训练效果。实验证明，NAGphormer 优于现有的图变换器和主流图神经网络，并且 NrAug 对 NAGphormer 进一步提升作用显著。