从社交网络到生物信息学再到机器人技术中的导航和规划问题，图在各种现实世界数据集中无处不在。因此，人们对专门设计用于处理图结构数据的图神经网络(GNN)产生了极大的兴趣。尽管现代GNN在理解图数据方面取得了巨大成功，但在有效处理图数据方面仍然存在一些挑战。例如，当所考虑的图很大时，计算复杂性就会成为一个问题。相比之下，在空间域中工作的算法避免了昂贵的频谱计算，但要对更长距离的依赖性进行建模，则必须依赖深度GNN架构来从远处节点传播信号，因为各个层仅对局部交互进行建模。为了解决这些问题，来自谷歌大脑、哥伦比亚大学和牛津大学的研究团队提出了一类新的图神经网络：GraphKernelAttentionTransformers(GKATs)。它结合了图形内核、基于注意力的网络和结构先验，以及最近的Transformer架构，该架构通过低秩分解技术应用小内存占用隐式注意力方法。该团队证明了GKAT比SOTAGNN具有更强的表达能力，同时还减轻了计算负担。新的GNN，降低计算复杂性“是否有可能设计一个具有密集单个层的GNN，明确地模拟图中更长范围的节点到节点关系，从而在扩展更大（不一定是稀疏）图的同时启用更浅的架构？”GKATs中的可分解长注意力GKAT将每一层内的图注意力建模为节点特征向量的核矩阵与图核矩阵的Hadamard乘积。单层，从而提高其表达能力超越传统的GNN。为了在图形节点上定义表达内核以实现高效映射，研究人员采用了一种新方法随机游走图节点内核(RWGNKs)，其中两个节点的值是作为两个频率向量的点积给出，这些向量记录图节点中的随机游走。完整的GKAT架构由几个块组成，每个块由注意力层和标准MLP层构建。值得注意的是，注意力层线性缩放而不是二次方缩放输入图的节点数，因此与其常规图相比降低了计算复杂度注意对口。优于9个SOTAGNNErd?s-Rényi随机图作者使用了五个二元分类数据集，这些数据集由连接到主题的随机ER图（正例）或与主题具有相同平均度数的其他较小的ER图（负例）组成。对于每个数据集，构建S个正例和S个负例，其中S=2048。作者测试了GKAT、图卷积网络(GCN)、谱图卷积网络(SGC)和图注意力网络(GAT)。每个顶点的特征向量长度为??l=5，并包含其相邻的顶阶度l（如果小于l，则用0填充）。每个主题的数据集随机分为75%的训练集和25%的验证集。同时，使用学习率为η=0.001的Adam优化器，如果在c=80个连续的epoch中验证损失和验证精度都没有提高，则提前停止训练。对于模型，作者选择使用两层架构并进行调整以使所有模型在尺寸上具有可比性。在GCN和SGC中，隐藏层有h=32个节点。在SGC中，每个隐藏层都与2个多项式局部滤波器组合。GAT和GKAT中使用了2个attentionheads，隐藏层有h=9个节点。在GKAT中，使用长度为τ=3的随机游走。可以看出，GKAT在所有主题上都优于其他方法。检测长诱导环和深度和密度注意力测试算法需要确定，给定常数T，图形是否包含长度大于T的诱导环。因此，主题本身成为一个全局属性，不能通过探索节点的邻居。在这个实验中，我们还要注意“深度和密度”的权衡。具有密集注意力的浅层神经网络能够对依赖于稀疏层的深层网络进行建模，但是以每层额外的计算成本为代价。实验中需要控制GCN、GAT和SGC的隐藏层节点数，以及GAT每个注意力头的个数，使其可训练参数总量与双层相当GKAT。对于GKAT，第一层应用8个头，第二层应用1个头，每个头的大小为d=4。最后一层是全连接层，输出维度为o=2，用于二进制分类和随机游走长度τ=6。不同长度GKAT的随机游走结果双层GKAT与具有不同隐藏层数(2-6)的GCN、GAT和SGC的比较表明，较浅的GKAT击败几乎所有GCN变体且少于4层。GAT和SGC。此外，GKAT与四层GAT和SGC趋势相等，但在训练和运行推理方面更快。生物信息学任务和社交网络数据的测试作者将GKAT与其他SOTAGNN方法进行了比较，包括：DCGNN、DiffPool、ECC、GraphSAGE和RWNN。对于生物信息学数据集，分子指纹(MF)方法用作基线。对于社交网络数据集，使用DeepMultisets(DM)方法作为基线。在GKAT配置方面，首先应用具有k个头（要调整的超参数）的注意层。然后是另一个注意力层，一个头，聚合图上的拓扑信息。接下来，应用MF方法或DM方法对聚合信息进行进一步处理。每个GKAT层中的随机游走长度τ满足：τ≤4并且取决于评估的数据集。长距离随机游走原则上可以捕获更多信息，但代价是增加了不相关的节点。生物信息学数据集社交网络数据集，其中平均图直径（每对节点的最长和最短路径的平均值）有助于校准步行长度并选择节点数与节点平均数最相似的图实验。作者在九个标准和公开可用的生物信息学和社交网络数据集上测试了GKAT的图形分类任务。对于每个数据集，性能最好的方法以粗体显示，第二好的方法带有下划线。GKAT在生物信息学数据集的四个任务中的三个任务中成绩最好GKAT在社交网络数据集的五个任务中的四个任务中排名前两名值得注意的是，除了一个生物信息学数据集外，GKAT是唯一的GNN方法在所有生物信息学数据集上始终优于基线。GKAT的空间和时间复杂度增益作者比较了GKAT（GKAT+）加入可分解注意力机制和GAT在速度和内存上的提升，以及与常规GKAT在精度上的损失。可以看出对应的GKAT和GKAT+模型的准确率差距很小。但与GAT相比，GKAT+在每个注意力层都产生了一致的速度和内存增益，尤其是对于来自Citeseer和Pubmed的那些非常大的图，增益非常可观。GKAT+在速度和空间复杂度方面的改进第一行：通过graphot对图形进行内存压缩（越低越好）。第二行和第三行：与GAT相比，各注意力层的训练和推理速度分别有所提高。第四行：与未应用可分解注意力的GKAT相比，精度下降。是时候训练不同的网络了，它们都具有两层结构。此外，就达到一定准确度所需的时间而言，常规GKAT也比相应模型（GCN、GAT和SGC）更快。总结作者提出了一种新的基于注意力的图神经网络：GraphKernelAttentionTransformers(GKATs)：利用图核方法和可扩展的注意力在处理图数据时更具表现力，时间复杂度和内存占用率低在广泛的范围内优于其他SOTA模型任务范围
