Research map / Graph learning / Graph self-supervised learning
Rethinking Tokenized Graph Transformers for Node Classification
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 SwapGT, a tokenized graph Transformer for node classification that generates diverse node-token sequences via a token swapping operation over a kNN graph and adds a center alignment loss.
Problem
Existing tokenized graph Transformers build token sequences only from first-order neighbors in a similarity (kNN) graph, which limits token diversity and hurts node classification, especially with sparse training labels.
Approach
Token swapping replaces each node token with a randomly sampled token from that token's own token set, so sampling reaches (t+1)-hop neighbors on the kNN graph and yields multiple diverse token sequences; a center alignment loss pulls together the representations from the same node's multiple sequences.
Key results
- Under dense splitting, SwapGT achieves the best accuracy on all eight datasets, e.g., 95.92% on Photo and 87.56% on Flickr.
- Under sparse splitting (2.5% training), SwapGT improves over the best baseline on BlogCatalog (88.11% vs 84.57% for GPRGNN) and Citeseer (69.91% vs 66.70% for APPNP).
- Ablation shows removing the center alignment loss (SwapGT-O) lowers performance, with larger gains under sparse splitting; token swapping beats simply doubling k (SwapGT-L) and random sampling from 2k tokens (SwapGT-R).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SwapGT instead of the strongest reported baseline | Node classification models · All eight datasets, dense splitting | accuracy | Helped |
| Use SwapGT instead of the strongest reported baseline | Node classification models · All eight datasets, sparse splitting | accuracy | Helped |
| Add center alignment loss (ablation) | SwapGT · Node classification, dense splitting | accuracy | Helped |
| Add center alignment loss (ablation) | SwapGT · Node classification, sparse splitting | accuracy | Helped |
| Replace token swapping with sampling 2k tokens in one sequence (ablation) | SwapGT · Node classification | accuracy | Hurt |
| Replace token swapping with random sampling of k tokens from the enlarged 2k token set (ablation) | SwapGT · Node classification | accuracy | Hurt |
| Use multiple randomly sampled sequences rather than one longer sequence (ablation) | SwapGT-L versus SwapGT-R · Node classification, most cases | accuracy | Helped |
| Vary swapping times t; use t no less than 2 (ablation) | SwapGT · Node classification, all datasets | accuracy | Helped |
| Increase augmentation times s (ablation) | SwapGT · Node classification, sparse versus dense splitting | accuracy | Mixed |
Surprising findings
- Graph transformers outperform GNNs on over half the datasets under dense splitting, but GNNs generally beat them under sparse splitting.
Limitations
- Swapping uses a uniform random strategy for token selection, so gains vary across graphs.
- Hyperparameters (t, s, k, alpha) must be tuned per dataset via grid search.
Experimental setup
Datasets: Photo ACM Computer Citeseer WikiCS BlogCatalog UAI2010 Flickr
Benchmarks: Photo ACM Computer Citeseer WikiCS BlogCatalog UAI2010 Flickr
Metrics: accuracy
Baselines: SGC APPNP GPRGNN FAGCN BM-GCN ACM-GCN NAGphormer SGFormer Specformer VCR-Graphormer PolyFormer
Builds on: NAGphormer personalized PageRank propagation
Closest papers by meaning
- Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers (NeurIPS 2024 · similarity 0.89)
- Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification (AAAI 2025 · similarity 0.88)
- Equivalence is All: A Unified View for Self-supervised Graph Learning (ICML 2025 · similarity 0.86)
- GraphGPT: Generative Pre-trained Graph Eulerian Transformer (ICML 2025 · similarity 0.86)
- Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning (ICLR 2025 · similarity 0.85)
- NLGT: Neighborhood-based and Label-enhanced Graph Transformer Framework for Node Classification (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.