# Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification

arXiv: https://arxiv.org/abs/2412.15302 · HTML: https://mlsanity.com/paper/2412.15302/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 43 references that are in the map.
- First posted on arXiv 19 Dec 2024.

## Builds on (most cited first, 26 of 26)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Multi-Scale Context Aggregation by Dilated Convolutions](https://mlsanity.com/paper/1511.07122/) (2015)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Graph Neural Network-Based Anomaly Detection in Multivariate Time Series](https://mlsanity.com/paper/2106.06947/) (2021)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Graph-Bert: Only Attention is Needed for Learning Graph Representations](https://mlsanity.com/paper/2001.05140/) (2020)
- [NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs](https://mlsanity.com/paper/2206.04910/) (2022)
- [Position Information in Transformers: An Overview](https://mlsanity.com/paper/2102.11090/) (2021)
- [Hierarchical Graph Transformer with Adaptive Node Sampling](https://mlsanity.com/paper/2210.03930/) (2022)
- [Tackling Over-Smoothing for General Graph Convolutional Networks](https://mlsanity.com/paper/2008.09864/) (2020)
- [Gophormer: Ego-Graph Transformer for Node Classification](https://mlsanity.com/paper/2110.13094/) (2021)
- [GRAND+: Scalable Graph Random Neural Networks](https://mlsanity.com/paper/2203.06389/) (2022)

## Built on by (most cited first, 3 of 3)

- [FairGE: Fairness-Aware Graph Encoding in Incomplete Social Networks](https://mlsanity.com/paper/2601.09394/) (2026)
- [Graph Cascades: Contagion-Based Mesoscopic Rewiring for Structure-Aware Graph Machine Learning](https://mlsanity.com/paper/2606.05046/) (2026)
- [GraphVQ: Structure-Aware Autoregressive Decoding over Context-Quantized Graph Tokens](https://mlsanity.com/paper/2609.37604/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are widely used in graph data mining tasks. Traditional GNNs follow a message passing scheme that can effectively utilize local and structural information. However, the phenomena of over-smoothing and over-squashing limit the receptive field in message passing processes. Graph Transformers were introduced to address these issues, achieving a global receptive field but suffering from the noise of irrelevant nodes and loss of structural information. Therefore, drawing inspiration from fine-grained token-based representation learning in Natural Language Processing (NLP), we propose the Structure-aware Multi-token Graph Transformer (Tokenphormer), which generates multiple tokens to effectively capture local and structural information and explore global information at different levels of granularity. Specifically, we first introduce the walk-token generated by mixed walks consisting of four walk types to explore the graph and capture structure and contextual information flexibly. To ensure local and global information coverage, we also introduce the SGPM-token (obtained through the Self-supervised Graph Pre-train Model, SGPM) and the hop-token, extending the length and density limit of the walk-token, respectively. Finally, these expressive tokens are fed into the Transformer model to learn node representations collaboratively. Experimental results demonstrate that the capability of the proposed Tokenphormer can achieve state-of-the-art performance on node classification tasks.