VCR-Graphormer is a mini-batch graph transformer that uses virtual connections to efficiently learn graph representations. The method addresses the computational inefficiency of traditional graph transformers, which require dense attention mechanisms leading to quadratic complexity. VCR-Graphormer employs personalized PageRank (PPR) to generate token lists for each node, enabling efficient mini-batch training. By incorporating virtual connections through structure- and content-based super nodes, the method captures local and global contexts, long-range interactions, and heterophilous information in the token lists. This approach reduces the computational complexity from O(n³) to O(m + k log k), where m is the number of edges and k is the number of selected neighbors per node. The method is validated on various graph datasets, demonstrating competitive performance in node classification tasks, particularly on heterophilous graphs. VCR-Graphormer effectively combines the strengths of graph convolutional networks with the flexibility of transformers, achieving efficient and scalable graph learning.VCR-Graphormer is a mini-batch graph transformer that uses virtual connections to efficiently learn graph representations. The method addresses the computational inefficiency of traditional graph transformers, which require dense attention mechanisms leading to quadratic complexity. VCR-Graphormer employs personalized PageRank (PPR) to generate token lists for each node, enabling efficient mini-batch training. By incorporating virtual connections through structure- and content-based super nodes, the method captures local and global contexts, long-range interactions, and heterophilous information in the token lists. This approach reduces the computational complexity from O(n³) to O(m + k log k), where m is the number of edges and k is the number of selected neighbors per node. The method is validated on various graph datasets, demonstrating competitive performance in node classification tasks, particularly on heterophilous graphs. VCR-Graphormer effectively combines the strengths of graph convolutional networks with the flexibility of transformers, achieving efficient and scalable graph learning.