Research map / Graph learning / Graph self-supervised learning
VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections
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 VCR-Graphormer, a mini-batch graph transformer that tokenizes each node with PPR-ranked token lists enriched by structure- and content-based virtual super-node connections, achieving scalable node classification.
Problem
Graph transformers need dense global attention, which is quadratic and unaffordable on large graphs; mini-batch training with few samples per batch cannot capture enough global topological and feature information.
Approach
Assign each node a PPR-sampled token list and apply self-attention only on it, then rewire the graph with structure-aware (METIS cluster) and content-aware (label/cluster) virtual super nodes so that PPR token lists capture global, long-range and heterophilous information at O(m + k log k) tokenization cost.
Key results
- VCR-Graphormer achieves 89.77% on PubMed, 71.67% on CoraFull and 91.75% on Computer, competitive with or best among the listed baselines on small-scale datasets.
- On Reddit VCR-Graphormer reports 93.69 ± 0.08, the best among listed methods; on Amazon2M it reports 76.09 vs NAGphormer's 77.43.
- On arXiv-year (heterophilous, large-scale) VCR-Graphormer reports 54.15 ± 0.09, above GCNII and GPR-GNN but below GloGNN++ (54.79).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use VCR-Graphormer instead of NAGphormer | node classification · PubMed | accuracy: 89.70 ± 0.19 -> 89.77 ± 0.15 | Helped |
| use VCR-Graphormer instead of NAGphormer | node classification · CoraFull | accuracy: 71.51 ± 0.13 -> 71.67 ± 0.10 | Helped |
| use VCR-Graphormer instead of Exphormer | node classification · Computer | accuracy: 91.59 ± 0.31 -> 91.75 ± 0.15 | Helped |
| use VCR-Graphormer instead of NAGphormer | node classification · Photo | accuracy: 95.49 ± 0.11 -> 95.53 ± 0.14 | Helped |
| use VCR-Graphormer instead of Exphormer | node classification · CS | accuracy: 95.77 ± 0.15 -> 95.37 ± 0.04 | Hurt |
| use VCR-Graphormer instead of NAGphormer | node classification · Physics | accuracy: 97.34 ± 0.03 -> 97.34 ± 0.04 | No clear effect |
| use VCR-Graphormer instead of NAGphormer | node classification · Reddit | accuracy: 93.58 ± 0.05 -> 93.69 ± 0.08 | Helped |
| use VCR-Graphormer instead of GRAND+ | node classification · Aminer | accuracy: 54.67 ± 0.25 -> 53.59 ± 0.10 | Hurt |
| use VCR-Graphormer instead of NAGphormer | node classification · Amazon2M | accuracy: 77.43 ± 0.11 -> 76.09 ± 0.16 | Hurt |
| use VCR-Graphormer instead of GloGNN++ | node classification without minibatching · arXiv-year | accuracy: 54.79 ± 0.25 -> 54.15 ± 0.09 | Hurt |
| decrease the number of hops (ablation) | VCR-Graphormer · Reddit | accuracy: 93.36 -> 93.02 | Hurt |
| increase the number of structure-aware super nodes and sample more neighbors (ablation) | VCR-Graphormer with reduced hop count · Reddit | accuracy: 93.02 -> 93.16 | Helped |
Limitations
- Only slightly faster than eigendecomposition on Amazon2M, and VCR-Graphormer does not beat NAGphormer on Amazon2M or Aminer.
- Virtual super node count and neighbor limits (under 20 tokens) are hyperparameters that trade off accuracy and efficiency.
- Content-aware super nodes use only training-set labels, limiting use when labels are scarce.
Experimental setup
Datasets: PubMed CoraFull Computer Photo CS Physics Reddit Aminer Amazon2M Squirrel Actor Texas
Benchmarks: PubMed CoraFull Computer Photo CS Physics Reddit Aminer Amazon2M Squirrel Actor Texas
Metrics: node classification accuracy
Baselines: GCN GAT APPNP GPR-GNN GraphSAINT PPRGo GRAND+ GT Graphormer SAN GraphGPS NAGphormer
Builds on: NAGphormer personalized PageRank GPR-GNN Jumping Knowledge METIS
Closest papers by meaning
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.88)
- Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification (AAAI 2025 · similarity 0.87)
- GraphGPT: Generative Pre-trained Graph Eulerian Transformer (ICML 2025 · similarity 0.87)
- Polynormer: Polynomial-Expressive Graph Transformer in Linear Time (ICLR 2024 · similarity 0.87)
- Even Sparser Graph Transformers (NeurIPS 2024 · similarity 0.87)
- Subgraph Invariant Learning Towards Large-Scale Graph Node Classification (AAAI 2025 · similarity 0.87)
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.