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).

用个性化 PageRank（PPR）对每个节点进行令牌化，并在此令牌列表上应用标准的多头自注意力机制，以计算其节点表示。借助 PPR 令牌化方法，使得以分批加载节点的令牌列表进行图转换器的小批量训练成为可能。此外，通过在结构和内容的基础上创建多种类型的虚拟连接，能够将本地和全局上下文、长距离交互以及异源信息编码到每个节点的令牌列表中，从而形成我们的虚拟连接排序图转换器（VCR-Graphormer）模型。