人工智能咨询培训老师叶梓 转载标明出处
尽管图变换器在理论上具有强大的表达能力，但是它们在扩展到大型图时面临着巨大的挑战。这一挑战主要源于其全局注意力机制的二次方时间复杂度，这不仅限制了其在大型图数据集上的应用，也使得其在内存和计算资源上的需求变得难以承受。
为了解决这一问题，一种名为EXPHORMER的框架应运而生。旨在构建强大且可扩展的图变换器。该框架的核心是一种基于虚拟全局节点和扩展器图的稀疏注意力机制，这些机制的数学特性，如谱扩张、伪随机性和稀疏性，使得图变换器的复杂度仅与图的大小成线性关系，同时保持了理论上的优越性质。
方法
稀疏注意力机制通过一个有向图H来建模，包含n个节点。如果存在一个从节点i到节点j的有向边，则表示这两个节点之间有直接的交互，即注意力机制将计算它们之间的内积。具体为一个变换器块可以被视为一个函数，它处理每个节点的d维嵌入，将R^d×n映射到R^d×n。注意力机制的输出由下式给出：
其中，X_{NH(i)}表示只包含节点i的邻居的子矩阵。这种注意力机制的计算量由图H的边数决定。标准的变换器块由注意力机制和前馈层组成。
图1 展示了EXPHORMER的各个组成部分。EXPHORMER架构是基于扩展器图的稀疏注意力机制，构建了一个交互图H，包括局部邻域注意力（即输入图的边）、度数为3的扩展器图、单个虚拟节点的全局注意力，以及将所有组件合并成一个交互图来决定注意力模式。
-
扩展器图注意力：使用随机扩展器图的边作为注意力模式。这些图具有小直径、谱近似完全图、良好的混合属性等理论特性，使得它们能够在不连接所有节点对的情况下，传播输入图中距离较远的节点对之间的信息。
-
全局注意力：在交互图中添加少量虚拟节点，每个节点都连接到所有非虚拟节点。这些节点充当全局“存储池”，具有全变换器的通用近似功能。
-
局部邻域注意力：通过允许每个节点v只关注其在G中的直接邻居，来模拟局部交互，即H包含输入图的边E及其反向，引入O(|E|)交互边。
扩展器图是完全图的稀疏近似。例如，一个d-regular的ϵ-expander图在n个顶点上的谱近似了完全图Kn。谱近似能够保持图的切割结构，因此基于扩展器边的稀疏注意力机制保留了全注意力机制的谱特性。
扩展器图的另一个属性是随机游走混合良好。这意味着从任意初始分布在顶点上的随机游走，在经过对数级步骤后，将接近于在所有节点上均匀分布。
尽管稀疏变压器模型的通用近似属性并不像密集变压器模型那样直接，但任何连续函数f : [0, 1]^d×|V| → R^d×|V|都可以被EXPHORMER网络使用全局注意力或适当版本的扩展器注意力近似到任意期望的精度。
想要掌握如何将大模型的力量发挥到极致吗？叶老师带您深入了解 Llama Factory —— 一款革命性的大模型微调工具。实战专家1小时讲解让您轻松上手，学习如何使用 Llama Factory 微调模型。
评论留言“参加”或扫描微信备注“参加”，即可参加线上直播分享，叶老师亲自指导，互动沟通，全面掌握Llama Factory。关注享粉丝福利，限时免费录播讲解。
LLaMA Factory 支持多种预训练模型和微调算法。它提供灵活的运算精度和优化算法选择，以及丰富的实验监控工具。开源特性和社区支持使其易于使用，适合各类用户快速提升模型性能。
实验
实验涉及多种图数据集，包括图像基础的图数据集（CIFAR10、MNIST、PascalVOC-SP、COCO-SP）、合成的SBM数据集（PATTERN、CLUSTER）、代码图数据集（MalNet-Tiny）和分子数据集（Peptides-Func、Peptides-Struct、PCQM-Contact）。还展示了EXPHORMER在处理超过5000个节点的更大图上的能力，包括引文网络（CS、Physics、ogbn-arxiv）和共同购买网络（Computer、Photo）。
实验中，EXPHORMER与MPNNs一起在GraphGPS框架下进行组合，构建图变换器模型。通过将注意力机制与消息传递方案相结合，并与适当的位置和结构编码一起使用。
表2 比较了在不同数据集上的注意力机制，包括EXPHORMER与其他稀疏变换器架构（BigBird和Performer）的性能，并与完整的变换器GPS模型进行了对比。结果显示，在四个数据集中，EXPHORMER模型优于GPS-BigBird和GPS-Performer模型，并在三个数据集上超越了GPS-Transformer模型，同时在第四个数据集上表现具有竞争力。
表1 展示了在五个数据集上的实验结果，包括四个来自Benchmarking GNNs集合的数据集和代码图数据集MalNet-Tiny。EXPHORMER在这些数据集上实现了最先进的性能，并在其余数据集上与最佳单一模型精度保持竞争力。所有数据集中，EXPHORMER模型的准确性都优于基于完全（密集）变换器的GraphGPS模型，并且也优于基于SAN模型和多种MPNN基线的模型。
表3 展示了在Long-Range Graph Benchmark（LRGB）中的实验结果，该基准由五个挑战性数据集组成，测试模型学习输入图中长期依赖关系的能力。结果显示，EXPHORMER在五个数据集中的三个上超越了GraphGPS，并在剩余两个数据集中与最佳单一模型结果保持竞争力。
表4 展示了在不同注意力机制下模型在归纳图数据集上的准确性。在大型数据集上，如ogbn-arxiv，EXPHORMER模型能够处理包含超过160,000个节点和超过一百万条边的单个大图。EXPHORMER可以用于更大的图，具有数十万个节点。
表5 展示了完整模型与移除每个组件后的模型的比较结果。这些实验表明，局部邻域一直是EXPHORMER的一个有效补充，但在虚拟节点和扩展器图之间，有时其中一个会导致性能下降。这一问题在附录D中有进一步讨论。
综合这些实验结果，可以得出以下结论：(a) EXPHORMER在多种数据集上实现了最先进的性能；(b) EXPHORMER在参数更少的情况下，一致性地优于其他稀疏注意力机制，并经常超越密集变换器；(c) EXPHORMER成功地允许GraphGPS克服内存瓶颈，扩展到更大的图（超过10,000个节点），同时仍然提供有竞争力的性能。
https://arxiv.org/pdf/2303.06147v2
GitHub - hamed1375/Exphormer: Exphormer: Sparse Transformer for Graphs
