Tokenized Graph Transformer with Neighborhood Augmentation for Node
  Classification in Large Graphs
Jinsong Chen Chang Liu Kaiyuan Gao Gaichao Li Kun He
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.