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

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

现有的神经网络（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 微调模型。

评论留言“参加”或扫描微信备注“参加”，即可参加线上直播分享，叶老师亲自指导，互动沟通，全面掌握Llama Factory。关注享粉丝福利，限时免费录播讲解。

实验

实验采用了多种数据集，包括小型到中型的图数据集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图的依赖性较低，并且能够从数据中学习到有用的潜在图结构。