谷歌大脑推出新型GKATs图神经网络，超越9种现有技术

图结构数据在社交网络、生物信息学和机器人导航等多个领域广泛存在，这引发了对图神经网络（GNN）研究的浓厚兴趣。

尽管现代GNN在处理图形数据方面取得了显著进展，但依然面临一些挑战，尤其是在处理大规模图时，计算复杂性成为一个主要问题。

相比之下，空间域算法虽然能够避免复杂的频谱计算，但为了模拟长距离的依赖关系，通常需要依赖深度GNN架构，这使得信号从远处节点的传播变得复杂，因为单层仅能模拟局部互动。

为了解决这些问题，谷歌大脑、哥伦比亚大学和牛津大学的研究团队推出了一种新型图神经网络：GRaph KeRnel Attention TRansfoRMeRs（GKATs）。

研究团队证明，GKAT在表达能力上超越了现有的SOTA GNN，同时有效降低了计算负担。

新型GNN，降低计算复杂度

研究者们思考，是否可以设计一款具有密集单层的GNN，明确建模图中节点间更长距离的关系，从而实现更浅的架构并扩展到更大的（不一定是稀疏的）图。

GKAT中的可分解长注意力

GKAT通过将每层内的图注意力建模为节点特征向量的核矩阵与图核矩阵的Hadamard乘积，提升了其表达能力。该方法利用了计算效率更高的隐式注意机制，使得单层内能够建模更远距离的依赖关系，从而超越了传统GNN的表现。

为在图节点上定义高效映射的表达内核，研究人员采用了一种创新的随机游走图节点内核（RWGNKs）方法，通过两个节点的值作为两个频率向量的点积来表示，记录了图节点中的随机游走情况。

完整的GKAT架构由多个模块组成，每个模块包含注意力层和标准MLP层。值得注意的是，注意层与输入图的节点数呈线性关系，而非二次方，从而降低了计算复杂度。

优于9种SOTA GNN

ERdős-Rényi随机图

研究者使用了五个二元分类数据集，正例为与主题相关的随机ER图，负例为与模体具有相同平均度的其他较小ER图。每个数据集构建了S个正例和S个负例，其中S=2048。

他们对GKAT、图卷积网络（GCNs）、谱图卷积网络（SGCs）和图注意网络（GATs）进行了评估。

每个顶点的特征向量长度为l=5，包含其相邻顶序度数l（不足时填充0）。每个模体数据集被随机分为75%的训练集和25%的验证集。

同时，采用学习率η=0.001的AdaM优化器，若验证损失和验证准确率在c=80个连续的epoch中没有改善，则提前停止训练。

研究者选择双层架构，并通过调整使所有模型的规模相当。在GCN和SGC中，隐层包含h=32个节点，而在SGC中，每个隐层与两个多项式局部过滤器结合。在GAT和GKAT中，采用两个注意头，隐层包含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层的GATs和SGCs中胜出。此外，GKAT在趋势上与四层GAT和SGC持平，但在训练及运行推理速度上更快。

生物信息学任务与社交网络数据测试

研究者将GKAT与其他SOTA GNN方法进行比较，包括DCGNN、DiFFPool、ECC、GRaphSAGE和RWNN。对于生物信息学数据集，使用分子指纹（MoleculaR FingeRpRint, MF）作为基线；对于社交网络数据集，采用深度多重集合（DeepMultisets, DM）方法作为基线。

在GKAT配置中，首先应用具有k个头的注意层（待调整的超参数），然后是另一个具有一个头的注意层，以聚合图的拓扑信息。接着应用MF或DM方法以进一步处理聚合的信息。

每个GKAT层中的随机游走长度τ满足：τ≤4，并根据评估数据集进行调整。长随机游走原则上能够捕获更多信息，但会增加与节点无关的信息。

生物信息学数据集

社交网络数据集

其中，平均图径（每对节点最长最短路径的平均值）有助于校准游走长度，并在实验中选择节点数与平均节点数最相似的图。

研究者在9个标准和公开的生物信息学及社交网络数据集上测试了GKAT的图分类任务。表现最佳的方法以粗体显示，第二名以下划线标示。

GKAT在生物信息学数据集的四个任务中有三个结果最佳

GKAT在社交网络数据集的五个任务中有四个位列前两名

值得注意的是，除了一个生物信息学数据集外，GKAT在所有生物信息学数据集上均持续优于基线的GNN方法。

GKAT的空间和时间复杂度增益

研究者比较了加入可分解注意力机制的GKAT（GKAT+）与GAT在速度和内存方面的提升，以及与常规GKAT在准确性上的差距。结果显示，GKAT与GKAT+模型的准确率差距微小。

但是，与GAT相比，GKAT+在每个注意层中持续展现出速度和内存的提升，尤其是在来自CITeseeR和PubMed的大型图形中，这种提升尤为显著。

GKAT+在速度和空间复杂度上的提升

第一行：通过gRaphot对图形进行内存压缩（越低越好）。

第二行和第三行：与GAT相比，每个注意力层的训练和推理速度分别提升。

第四行：与未应用可分解注意力机制的GKAT相比，准确率的下降。

训练不同网络的时间，均为双层结构

此外，在达到特定精度水平所需的时间方面，常规GKAT也比相应模型（GCN、GAT和SGC）更快。

总结

研究者提出了一种全新的基于注意力的图神经网络：GRaph KeRnel Attention TRansfoRMeRs（GKATs），该网络结合了图核方法和可扩展注意力，展现出在处理图数据时更强的表现力，具备低时间复杂度和内存占用，且在多项任务上超越其他SOTA模型。