NAGphormer: Neighborhood Aggregation Graph Transformer for Node Classification in Large Graphs
Graph Transformers have demonstrated superiority on various graph learning
tasks in recent years. However, the complexity of existing Graph Transformers
scales quadratically with the number of nodes, making it hard to scale to
graphs with thousands of nodes. To this end, we propose a Neighborhood
Aggregation Graph Transformer (NAGphormer) that is scalable to large graphs
with millions of nodes. Before feeding the node features into the Transformer
model, NAGphormer constructs tokens for each node by a neighborhood aggregation
module called Hop2Token. For each node, Hop2Token aggregates neighborhood
features from each hop into a representation, and thereby produces a sequence
of token vectors. Subsequently, the resulting sequence of different hop
information serves as input to the Transformer model. By considering each node
as a sequence, NAGphormer could be trained in a mini-batch manner and thus
could scale to large graphs. NAGphormer further develops an attention-based
readout function so as to learn the importance of each hop adaptively. We
conduct extensive experiments on various popular benchmarks, including six
small datasets and three large datasets. The results demonstrate that
NAGphormer consistently outperforms existing Graph Transformers and mainstream
Graph Neural Networks.