VCR-Graphormer: A Mini-Batch Graph Transformer via Virtual Connections This paper introduces VCR-Graphormer, a novel mini-batch graph transformer that addresses the computational inefficiency of dense attention mechanisms in graph learning. Traditional graph transformers use dense attention to capture expressive representations from complex topological and feature information, resulting in quadratic computational costs that are unaffordable for large-scale data. To overcome this, VCR-Graphormer employs personalized PageRank (PPR) to generate token lists for each node, which are then processed by standard self-attention mechanisms to produce node representations. This approach decouples model training from complex graph topological information, enabling efficient mini-batch training. The paper proposes a method to enhance the token lists by introducing virtual connections through structure- and content-based super nodes. These virtual connections allow PPR tokenization to encode local and global contexts, long-range interactions, and heterophilous information into each node's token list. This results in a more comprehensive representation that supports different graph inductive biases for model training. The proposed method achieves a complexity of O(m + k log k), significantly lower than the O(n^3) complexity of previous works. The paper also discusses the principles of a "good" tokenization, emphasizing the need for token lists to reflect local and global topological information, preserve long-range interactions, contain heterophilous information, and be efficiently obtained. VCR-Graphormer satisfies these criteria by incorporating virtual connections and structure-aware and content-aware super nodes. Experiments on various graph datasets demonstrate that VCR-Graphormer achieves competitive performance with limited token length, showing that sampled global neighbors can be effective without the need for eigendecomposition. The method is also effective on heterophilous datasets, where traditional methods struggle due to the lack of homophily. Ablation studies and parameter analysis further validate the effectiveness of the proposed approach, showing that structure-aware and content-aware neighbors contribute to performance and that the number of structure-aware super nodes, hops, and neighbors are interrelated. The paper concludes that VCR-Graphormer provides an efficient and effective solution for mini-batch training of graph transformers, demonstrating the potential of token-based approaches in graph learning. The method is theoretically grounded in graph convolutional networks and leverages the concept of jumping knowledge to enhance performance. The proposed approach offers a promising direction for scalable graph learning and has the potential to be applied to a wide range of graph-related tasks.VCR-Graphormer: A Mini-Batch Graph Transformer via Virtual Connections This paper introduces VCR-Graphormer, a novel mini-batch graph transformer that addresses the computational inefficiency of dense attention mechanisms in graph learning. Traditional graph transformers use dense attention to capture expressive representations from complex topological and feature information, resulting in quadratic computational costs that are unaffordable for large-scale data. To overcome this, VCR-Graphormer employs personalized PageRank (PPR) to generate token lists for each node, which are then processed by standard self-attention mechanisms to produce node representations. This approach decouples model training from complex graph topological information, enabling efficient mini-batch training. The paper proposes a method to enhance the token lists by introducing virtual connections through structure- and content-based super nodes. These virtual connections allow PPR tokenization to encode local and global contexts, long-range interactions, and heterophilous information into each node's token list. This results in a more comprehensive representation that supports different graph inductive biases for model training. The proposed method achieves a complexity of O(m + k log k), significantly lower than the O(n^3) complexity of previous works. The paper also discusses the principles of a "good" tokenization, emphasizing the need for token lists to reflect local and global topological information, preserve long-range interactions, contain heterophilous information, and be efficiently obtained. VCR-Graphormer satisfies these criteria by incorporating virtual connections and structure-aware and content-aware super nodes. Experiments on various graph datasets demonstrate that VCR-Graphormer achieves competitive performance with limited token length, showing that sampled global neighbors can be effective without the need for eigendecomposition. The method is also effective on heterophilous datasets, where traditional methods struggle due to the lack of homophily. Ablation studies and parameter analysis further validate the effectiveness of the proposed approach, showing that structure-aware and content-aware neighbors contribute to performance and that the number of structure-aware super nodes, hops, and neighbors are interrelated. The paper concludes that VCR-Graphormer provides an efficient and effective solution for mini-batch training of graph transformers, demonstrating the potential of token-based approaches in graph learning. The method is theoretically grounded in graph convolutional networks and leverages the concept of jumping knowledge to enhance performance. The proposed approach offers a promising direction for scalable graph learning and has the potential to be applied to a wide range of graph-related tasks.