Tokenized Graph Transformer with Neighborhood Augmentation for Node Classification in Large Graphs

Understand

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.