Research map / Graph learning / GNN architectures

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

AAAI 2025 · Graph learning › GNN architectures · approach: Graph structure learning · 6 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Tokenphormer, a graph Transformer that feeds each node a multi-token sequence (mixed-walk tokens, a self-supervised graph pre-trained SGPM token, and hop tokens) and reports state-of-the-art node classification on six homogeneous and three heterogeneous benchmarks.

Problem

Graph Transformers treating nodes as tokens are computationally costly and noisy, and existing token-based graph Transformers (e.g., NAGphormer's hop tokens) are too coarse to capture diverse graph structures for node classification.

Approach

Generate multiple fine-grained tokens per node: walk-tokens from four mixed walk types (uniform, non-backtracking, neighborhood jump, non-backtracking neighborhood jump), an SGPM-token from a BERT-style MLM pre-trained on serialized walks ("graph document"), and hop-tokens from decoupled message passing, then fuse them with an attention readout in a Transformer.

Key results

• Tokenphormer reaches 91.20% on Cora and 96.14% on Amazon Photo, the best reported among compared methods, with mean±std over 10 seeds.
• On heterogeneous datasets, Tokenphormer without SGPM-tokens achieves 86.17% on Wisconsin and 37.01% on Actor, best on those two, while Gapformer is best on Cornell at 77.57% vs 76.22% for Tokenphormer.
• Ablation shows removing walk-tokens causes the largest drop (e.g., Cora 91.20 to 88.37), and mixed walks outperform each single walk type.

Measured effects reported in the paper

Surprising findings

• On Flickr, APPNP (93.25%) outperforms Tokenphormer (92.44%), and Gapformer is best on Cornell, so Tokenphormer is not best on every dataset.
• Hop-token removal changes accuracy only slightly on most datasets, since many walk tokens already cover k-hop neighborhoods.

Limitations

• Several baseline numbers for NAGphormer were re-run by the authors because standard deviations were missing, and some baseline entries are unknown ('-' or 'x').
• The SGPM-token pre-training uses 4 H800 GPUs and the approach adds multiple token generators, increasing pipeline complexity.
• Heterogeneous experiments omit the SGPM-token, so the full model is not evaluated on those datasets.

Experimental setup

Datasets: Cora Citeseer Flickr Photo DBLP Pubmed Cornell Wisconsin Actor

Benchmarks: Cora Citeseer Flickr Photo DBLP Pubmed Cornell Wisconsin Actor

Metrics: accuracy

Baselines: GCN GAT GraphSAGE APPNP JKNet GPR-GNN GRAND+ GATv2 GT Graphormer SAN Gophormer

Builds on: NAGphormer Gophormer BERT Graphormer

Closest papers by meaning

• Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers (NeurIPS 2024 · similarity 0.89)
• Rethinking Tokenized Graph Transformers for Node Classification (NeurIPS 2025 · similarity 0.88)
• VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections (ICLR 2024 · similarity 0.87)
• NLGT: Neighborhood-based and Label-enhanced Graph Transformer Framework for Node Classification (AAAI 2025 · similarity 0.87)
• GraphGPT: Generative Pre-trained Graph Eulerian Transformer (ICML 2025 · similarity 0.86)
• Label-free Node Classification on Graphs with Large Language Models (LLMs) (ICLR 2024 · similarity 0.86)