论文标题：NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs.
论文链接：https://openreview.net/pdf?id=8KYeilT3Ow
图1 作者信息
此文发表于ICLR2023，是一篇将Transformer推广到大图上的工作。此前绝大多数的Graph Transformer将整个图作为输入，由于注意力机制平方计算复杂度的影响， 无法扩展到大图上的图数据挖掘的任务上。为了解决这个问题，作者提出了一种名为Hop2Token的策略，将输入数据由整图变为由邻域信息所构成的节点序列，从而引入批训练的策略来控制模型的训练开销。
核心模块
这篇文章提出了一种名为NAGphormer的Graph Transformer模型，该模型包含了两个核心模块，一个是Hop2Token模块，用于构建基于多跳邻域信息的节点序列；另一个是Attention-based readout function模块，用于生成最终的节点表征。该模型的整体框架如图2所示。
图2 NAGphormer的框架图
Hop2Token
顾名思义，该模块是将多跳邻域（Multi-hop neighborhood）转化为Token的形式，用于为每个节点构造输入序列。具体而言，为了刻画每个节点的邻域信息，作者利用了图扩散的方式，通过邻接矩阵在图上传播节点的属性特征来计算节点的邻域特征。
图3 邻域信息的获取
在获得邻域信息后，作者将节点的邻域信息按照跳数从低到高进行排列，用于构建基于多跳邻域的节点序列。通过这种方式，NAGphormer便可将整个图转化为节点序列的形式。Hop2Token的伪代码如图4所示。
图4 Hop2Token的伪
Hop2Token的优势有两点：一是在模型训练前为每个节点构建独立的输入序列，这种模式使得NAGphormer可以利用批训练的方式来控制训练代价，从而达到在大图上训练模型的目的；二是每个节点的多跳邻域序列可用于捕捉邻域之间的语义关联，这种关联信息是被之前的GNN模型所忽略的。在实践中，由于Transformer模块无法捕捉位置信息，作者为每个节点添加了基于拉普拉斯特征向量所构成的位置编码，用于提升模型的效果。
图5 加入位置编码
Attention-based readout function
在将节点序列输入到标准的Transformer训练后，会得到每个节点不同跳邻域的表征。为了计算最终的节点表征，作者提出了一种基于注意力的读出函数，其核心想法是基于注意力机制来自适应地聚合多跳邻域的信息，以形成最终的节点表征。
图6 Attention-based readout function
实验部分
作者在各种规模的图数据集上测试了模型在节点分类任务上的性能。
图7 数据集统计信息
图8 小图上的节点分类性能
图9 大图上的节点分类性能
从实验结果上看，该方法在保证模型性能的同时，还能提升模型的可扩展性。其消融实验也表明，基于注意力的读出函数也能有效地提升模型的表现。
图10 不同读出函数的表现
总结
NAGphormer 是一种用于大图节点分类任务的Graph Transformer模型，它利用Hop2Token模块构建节点的输入序列，并通过attention-based readout function得到最终的节点表示。然而仅仅依靠邻域传播的方式构建的token list可能无法很好地代表图上的信息，如全局依赖，异质性等等。后面可以考虑如何结合图上复杂的信息来更好地构建节点的token list。
