NodeFormer:一种用于节点分类的可扩展图结构学习 Transformer

发布于:2024-11-29 ⋅ 阅读:(33) ⋅ 点赞:(0)

 人工智能咨询培训老师叶梓 转载标明出处

现有的神经网络(GNNs)在处理大规模图数据时面临着一些挑战,如过度平滑、异质性、长距离依赖处理、边缘不完整性等问题,尤其是当输入图完全缺失时。为了解决这些问题,上海交通大学的研究者们人提出了一种名为NodeFormer的新型图结构学习Transformer。

NodeFormer提出了一种全新的全对消息传递方案,通过一种核化的Gumbel-Softmax操作符来减少算法复杂度,使其与节点数量呈线性关系。这种方法不仅能够高效地在大规模、潜在的全连接图中学习潜在图结构,而且能够以可微分的方式进行端到端的优化。

NodeFormer还引入了关系偏差和边缘级别的正则化损失,以更好地适应输入图(如果存在的话),并指导适当地学习自适应结构。

方法

NodeFormer通过一种新颖的方法来更新节点嵌入,采用核化的Gumbel-Softmax操作符,实现了每一层节点嵌入的O(N)复杂度更新。NodeFormer引入了关系偏差和边缘正则化损失机制,两者均在输入图可用时发挥作用,且计算复杂度为O(E)。在训练过程中,模型的目标是最小化监督分类损失和边缘正则化损失的加权和。

算法 1描述了NodeFormer的前馈计算过程。该算法从输入节点特征Z(0)=X和可选的图邻接矩阵A开始,通过迭代的方式,每一层都使用核化的Gumbel-Softmax操作符来更新节点嵌入。这个过程包括了关系偏差的引入,以及通过邻接矩阵A强化观察到的边的传播权重。

为了证明新的消息传递函数的正确性,提出了两个关键的理论问题。定理1(Softmax-Kernel的近似误差)指出,当特征映射的维度足够大且温度参数τ接近零时,正则化特征映射的分布将趋于原始的分类分布。定理2(核化Gumbel-Softmax随机变量的性质)进一步确认了这一点。

NodeFormer通过引入温度参数τ和随机特征映射的维度m,平衡了RF近似和Gumbel-Softmax近似之间的权衡。较大的τ有助于减少核维度m的负担,而较小的τ则需要较大的m来保证足够的RF近似精度。如果τ过大,每条边的权重将趋于1/N,即模型几乎退化为平均池化;而较小的τ则会使核化Gumbel-Softmax更好地近似分类分布。

图1阐释了NodeFormer的数据流向,突出了模型的三个主要组成部分:全对消息传递(MP)模块、关系偏差和边缘正则化损失。MP模块负责以O(N)的复杂度更新节点嵌入,而关系偏差和边缘正则化损失则根据输入图的可用性进行计算,两者的计算复杂度均为O(E)。这种设计使得NodeFormer在保持高效计算的同时,能够充分利用输入图的结构信息。

想要掌握如何将大模型的力量发挥到极致吗?叶老师带您深入了解 Llama Factory —— 一款革命性的大模型微调工具(限时免费)。

1小时实战课程,您将学习到如何轻松上手并有效利用 Llama Factory 来微调您的模型,以发挥其最大潜力。

CSDN教学平台录播地址:https://edu.csdn.net/course/detail/39987 

实验

实验采用了多种数据集,包括小型到中型的图数据集Cora、Citeseer、Deezer和Actor,以及更大规模的图数据集OGB-Proteins和Amazon2M。此外,还考虑了无输入图的半监督图像和文本分类任务,使用的是Mini-ImageNet和20News-Groups数据集。

在实验中,NodeFormer的输出预测层是一个单层的MLP(多层感知机),对于所有数据集,激活函数σ设置为sigmoid,温度参数τ设置为0.25。所有实验都在配备16GB内存的NVIDIA V100上进行。实验与多个基线模型进行比较,包括GCN、GAT、JKNet、MixHop、DropEdge、LDS-GNN、IDGL、SGC和GraphSAINT。

在Cora、Citeseer、Deezer和Actor数据集上进行了传导式节点分类实验。这些数据集的规模从2K到20K个节点不等。对于评估指标,Deezer数据集使用ROC-AUC,其他数据集使用准确率。图2展示了NodeFormer在这些数据集上的表现,无论是在同质性还是非同质性图上,NodeFormer都取得了最佳的准确率/ROC-AUC,特别是在两个非同质性图上,NodeFormer的性能大大超过了其他模型。

进一步测试了NodeFormer在大规模网络上的可扩展性,使用了OGB-Proteins和Amazon2M数据集,节点数分别超过10万个和200万个。OGB-Proteins是一个包含112个输出维度的多任务数据集,而Amazon2M是从亚马逊共购网络中提取的,包含长距离依赖。表2和表3展示了NodeFormer在这些数据集上的测试结果,无论是在ROC-AUC还是准确率上,NodeFormer都显著优于基线模型,并且内存消耗也更低。

在没有输入图的情况下,NodeFormer被应用于Mini-ImageNet和20News-Groups数据集上的半监督图像和文本分类任务。使用k-NN方法基于输入节点特征构建图,以启用GNN的消息传递和NodeFormer的基于图的组件。表4展示了在不同k值下的结果,NodeFormer在8个案例中的7个中都取得了最佳性能,表明NodeFormer对于k-NN图的依赖性较低,并且能够从数据中学习到有用的潜在图结构。

图3展示了NodeFormer与两种最先进的结构学习模型在训练/推理时间和GPU内存消耗方面的比较。NodeFormer在训练时间、推理时间和内存消耗方面都有显著降低。还探讨了随机组成部分的影响、边缘损失和关系偏差的影响,以及温度参数和特征映射维度的影响。

图6展示了温度和随机特征映射维度对模型性能的影响,结果与理论分析一致。图4和通过可视化,展示了NodeFormer学习到的节点嵌入和边连接,以及与原始图结构的比较,说明了NodeFormer如何通过学习潜在结构来改进下游节点级预测任务的性能。

NodeFormer在各种实验中都显示出了优异的性能,无论是在处理同质性还是非同质性图、大规模图数据集,还是在没有输入图的情况下进行图增强应用的任务。这些结果证明了NodeFormer在实际应用中的有效性和可扩展性。

https://arxiv.org/pdf/2306.08385v1

https://github.com/qitianwu/nodeformer