ViT/MLP-Mixer 在图结构上的泛化

图神经网络（Graph Neural Networks, GNNs）在图表示学习领域展现出巨大潜力。标准GNN通过堆叠多层实现局部消息传递机制，在整个图域中传播信息。然而，这一范式存在两大主要局限：信息过压缩（over-squashing）问题以及对长程依赖关系建模能力不足。尽管引入全局注意力机制可缓解上述问题，但会显著增加计算开销，导致复杂度上升至二次方级别。本文提出一种替代性方法，通过借鉴计算机视觉领域提出的ViT（Vision Transformer）与MLP-Mixer架构，以克服上述结构瓶颈。我们引入一类新型GNN，称为Graph ViT/MLP-Mixer，具备三大核心特性：其一，能够有效捕捉长程依赖关系，并缓解信息过压缩问题，该能力在Long Range Graph Benchmark和TreeNeighbourMatch数据集上得到验证；其二，具备更高的计算效率与内存效率，其时间与空间复杂度均与节点数和边数呈线性关系，优于现有的图Transformer及高表达力GNN模型；其三，在图同构性判别方面表现出强表达能力，能够区分至少3-WL（Weisfeiler-Lehman）非同构图。我们在4个模拟数据集和7个真实世界基准数据集上对所提架构进行了测试，结果均展现出极具竞争力的性能。相关源代码已公开，便于复现，地址为：\url{https://github.com/XiaoxinHe/Graph-ViT-MLPMixer}。