# VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 67 references that are in the map.
- First posted on arXiv 24 Mar 2024.

## Builds on (most cited first, 30 of 49)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Transformers in Vision: A Survey](https://mlsanity.com/paper/2101.01169/) (2021)
- [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)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [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)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)

## Built on by (most cited first, 30 of 34)

- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Learning Graph Quantized Tokenizers](https://mlsanity.com/paper/2410.13798/) (2024)
- [Video Anomaly Detection in 10 Years: A Survey and Outlook](https://mlsanity.com/paper/2405.19387/) (2024)
- [BACKTIME: Backdoor Attacks on Multivariate Time Series Forecasting](https://mlsanity.com/paper/2410.02195/) (2024)
- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [Graph4MM: Weaving Multimodal Learning with Structural Information](https://mlsanity.com/paper/2510.16990/) (2025)
- [PyG-SSL: A Graph Self-Supervised Learning Toolkit](https://mlsanity.com/paper/2412.21151/) (2024)
- [A Survey of Graph Transformers: Architectures, Theories and Applications](https://mlsanity.com/paper/2502.16533/) (2025)
- [Can Graph Neural Networks Learn Language with Extremely Weak Text Supervision?](https://mlsanity.com/paper/2412.08174/) (2024)
- [Breaking Silos: Adaptive Model Fusion Unlocks Better Time Series Forecasting](https://mlsanity.com/paper/2505.18442/) (2025)
- [Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers](https://mlsanity.com/paper/2406.19258/) (2024)
- [Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models](https://mlsanity.com/paper/2510.17457/) (2025)
- [NTFormer: A Composite Node Tokenized Graph Transformer for Node Classification](https://mlsanity.com/paper/2406.19249/) (2024)
- [Rethinking Tokenized Graph Transformers for Node Classification](https://mlsanity.com/paper/2502.08101/) (2025)
- [Invariant Link Selector for Spatial-Temporal Out-of-Distribution Problem](https://mlsanity.com/paper/2505.24178/) (2025)
- [A Scalable and Effective Alternative to Graph Transformers](https://mlsanity.com/paper/2406.12059/) (2024)
- [How to Make LMs Strong Node Classifiers?](https://mlsanity.com/paper/2410.02296/) (2024)
- [Learnable Spatial-Temporal Positional Encoding for Link Prediction](https://mlsanity.com/paper/2506.08309/) (2025)
- [HeroFilter: Adaptive Spectral Graph Filter for Varying Heterophilic Relations](https://mlsanity.com/paper/2510.10864/) (2025)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework](https://mlsanity.com/paper/2510.18825/) (2025)
- [OWLEYE: Zero-Shot Learner for Cross-Domain Graph Data Anomaly Detection](https://mlsanity.com/paper/2601.19102/) (2026)
- [Node4All: Learning Node Representation Beyond Datasets](https://mlsanity.com/paper/2607.17272/) (2026)
- [SPARC: Spectral Architectures Tackling the Cold-Start Problem in Graph Learning](https://mlsanity.com/paper/2411.01532/) (2024)
- [Dual Mamba for Node-Specific Representation Learning: Tackling Over-Smoothing with Selective State Space Modeling](https://mlsanity.com/paper/2511.06756/) (2025)
- [VecFormer: Towards Efficient and Generalizable Graph Transformer with Graph Token Attention](https://mlsanity.com/paper/2602.19622/) (2026)
- [Learning a Mini-batch Graph Transformer via Two-stage Interaction Augmentation](https://mlsanity.com/paper/2407.09904/) (2024)
- [ReHub: Linear Complexity Graph Transformers with Adaptive Hub-Spoke Reassignment](https://mlsanity.com/paper/2412.01519/) (2024)
- [Adaptive Tokenization: On the Hop-Overpriority Problem in Tokenized Graph Learning Models](https://mlsanity.com/paper/2505.15845/) (2025)
- [DAM-GT: Dual Positional Encoding-Based Attention Masking Graph Transformer for Node Classification](https://mlsanity.com/paper/2505.17660/) (2025)

## Abstract (arXiv)

Graph transformer has been proven as an effective graph learning method for its adoption of attention mechanism that is capable of capturing expressive representations from complex topological and feature information of graphs. Graph transformer conventionally performs dense attention (or global attention) for every pair of nodes to learn node representation vectors, resulting in quadratic computational costs that are unaffordable for large-scale graph data. Therefore, mini-batch training for graph transformers is a promising direction, but limited samples in each mini-batch can not support effective dense attention to encode informative representations. Facing this bottleneck, (1) we start by assigning each node a token list that is sampled by personalized PageRank (PPR) and then apply standard multi-head self-attention only on this list to compute its node representations. This PPR tokenization method decouples model training from complex graph topological information and makes heavy feature engineering offline and independent, such that mini-batch training of graph transformers is possible by loading each node's token list in batches. We further prove this PPR tokenization is viable as a graph convolution network with a fixed polynomial filter and jumping knowledge. However, only using personalized PageRank may limit information carried by a token list, which could not support different graph inductive biases for model training. To this end, (2) we rewire graphs by introducing multiple types of virtual connections through structure- and content-based super nodes that enable PPR tokenization to encode local and global contexts, long-range interaction, and heterophilous information into each node's token list, and then formalize our Virtual Connection Ranking based Graph Transformer (VCR-Graphormer).