ICLR 2024 || 图学习领域，注意力IS OFTEN NOT ALL YOU NEED!!!

NewBeeNLP

发布于 2024-04-26 20:20:21

1210

发布于 2024-04-26 20:20:21

文章被收录于专栏：NewBeeNLPNewBeeNLP

后台留言『交流』，加入NewBee讨论组

今天给大家介绍一篇论文，这篇论文探讨了图神经网络中自注意力机制与虚拟节点的异同。作者从理论和实验两个角度对比了图Transformer和带虚拟节点的消息传递图神经网络在一致性表达能力上的差异。这篇论文对理解不同全局信息交换范式具有重要意义。

1. 基本信息

论文题目：Distinguished in Uniform: Self-Attention vs. Virtual Nodes

作者：Eran Rosenbluth, Jan Tönshoff, Martin Ritzert, Berke Kisin, Martin Grohe

作者研究单位：

RWTH Aachen University
Georg-August-Universität Göttingen

2. 介绍

图Transformer（如SAN和GPS）通过将消息传递图神经网络（MPGNN）与全局自注意力相结合来处理图数据。之前的研究表明，它们是通用函数逼近器（universal function approximator），但有两个保留（reservations）：

初始节点特征必须增加某些位置编码。
这种逼近approximators是非一致的：不同大小的图可能需要不同的逼近网络。

本文首先澄清，这种形式的普适性并非图Transformer所独有：使用相同的位置编码，纯MPGNN甚至2层MLP也是非一致通用逼近器。然后，本文考虑一致性表达能力：目标函数将由一个网络对所有大小的图进行逼近。作者将图Transformer与更高效的MPGNN+虚拟节点架构进行了比较。两种模型定义的本质区别在于它们的全局计算方法——自注意力机制与虚拟节点。

本文的主要贡献是证明了在一致性表达能力上，MPGNN+VN和图Transformer都不能相互取代对方。作者用合成数据实验证明了相关理论。此外，本文在真实数据集上进行了实验，观察到混合结果，表明在实验中也没有明显的优劣之分。

本文提到的几种模型。

MPGNN+VN 带虚拟节点的消息传递图神经网络(MPGNN+VN)是在标准的消息传递框架下加入一个全局虚拟节点来实现长程特征交互。形式上,一个维度为

的带虚拟节点的消息传递层(MP+V)由一个维度为

的消息传递层MP和一个同样维度为

的读出函数R组成。虚拟节点会在每一轮消息传递后进行中间特征聚合,并将结果加到所有节点上:

\mathrm{MPV}(G)_v := \mathrm{R}\big(\mathrm{MP}(G)\big) + \mathrm{MP}(G)_v

一个

层的MPGNN+VN

\mathcal{N} = (P, L_1, \dots, L_L, R)

由一个将输入特征映射到

维的映射

、

个MP+V层

L_1,\dots,L_L

和一个最终读出函数

组成。

Transformer Layer：Transformer层由自注意力模块(SA)和前馈网络(FF)组成。对于一个输入矩阵

\mathbf{X} \in \mathbb{R}^{n \times d}

(如图的节点特征矩阵),Transformer层计算:

\begin{aligned} \mathbf{Y} &:= \mathrm{norm}_1\big(\mathbf{X} + \mathrm{SA}(\mathbf{X})\big)\\ \mathbf{Z} &:= \mathrm{norm}_2\big(\mathbf{Y} + \mathrm{FF}(\mathbf{Y})\big) \end{aligned}

其中

\mathbf{Z} \in \mathbb{R}^{n \times d}

是该层的输出矩阵,

\mathrm{norm}_1

和

\mathrm{norm}_2

是可选的归一化操作如LayerNorm或BatchNorm。

自注意力(SA)模块由多个注意力头组成。每个头

\mathcal{H}

由三个矩阵

\mathbf{W}_Q, \mathbf{W}_K, \mathbf{W}_V \in \mathbb{R}^{d \times d_h}

参数化,计算:

\mathcal{H}(\mathbf{X}) := \mathrm{softmax}\left(\frac{(\mathbf{X}\mathbf{W}_Q)(\mathbf{X}\mathbf{W}_K)^\top}{\sqrt{d_h}}\right)\mathbf{X}\mathbf{W}_V

其中softmax函数在每一行进行归一化。

Graph Transformer：图transformer通过迭代细化节点的embedding来处理图数据,其中每次迭代都使用一个Transformer层。形式上,一个维度为

p,d,q

的图transformer

\mathcal{N} = (P, L_1, \dots, L_L, R)

由一个映射

、

个维度为

的Transformer层

L_1,\dots,L_L

和一个维度为

d;q

的读出函数

组成。

GPS GPS是Rampášek等人提出的一种图transformer变体。它在标准的Transformer层中额外加入了一个消息传递(MP)模块,并与自注意力模块并行。形式上,一个维度为

的GPS层

\mathcal{L} = (\mathrm{SA}, \mathrm{MP}, \mathrm{FF})

包含一个自注意力模块SA、一个消息传递层MP和一个前馈网络FF,计算:

\begin{aligned} \mathbf{Y} &:= \mathrm{norm}_1\big(\mathbf{X} + \mathrm{SA}(\mathbf{X})\big) + \mathrm{norm}_2\big(\mathbf{X} + \mathrm{MP}(\mathbf{X})\big)\\ \mathbf{Z} &:= \mathrm{norm}_3\big(\mathbf{Y} + \mathrm{FF}(\mathbf{Y})\big) \end{aligned}

类似于图transformer,一个

层GPS网络

\mathcal{N} = (P, L_1, \dots, L_L, R)

由映射

、

个GPS层和读出函数

组成。

总的来说,MPGNN+VN通过加入一个全局虚拟节点来增强消息传递GNN的表达能力,而图transformer使用自注意力机制来建模长程交互。GPS进一步将两种范式相结合,在标准的Transformer层中额外加入了消息传递模块。本文从理论和实践的角度分析了它们之间的异同。

3. 方法

本文主要研究了图Transformer（GT）和带虚拟节点的消息传递图神经网络（MPGNN+VN）在一致性逼近能力上的差异。

首先，假设位置编码是图同构的，作者证明了2层MLP和1层MPGNN是通用函数逼近器：

\forall\varepsilon >0 \exists f \in F : \forall G \in \mathcal{G}_{S}^{p} \forall v \in V(G) |f(G)(v) - h(G)(v)| \leq \varepsilon

其中

是2层MLP或1层MPGNN的集合，

是目标函数。这说明位置编码的注入使得非常简单的模型也能在有限图上逼近任意函数。

接下来，作者证明了GT和MPGNN+VN都不是一致通用逼近器。如果令

为图上NP-hard问题的特征函数，如判断图是否3-可着色，并假设

P \neq NP

，则有：

GPS \not\approx h, MPGNN+VNs \not\approx h

进一步地，作者构造了一个目标函数

f(G_n) = n^2

，证明了对于任意的GPS

，存在一个

使得：

|f(G_n) - B(G_n)| >\delta

这说明GPS无法一致地逼近

。相反地，带求和读出函数的MPGNN+VN能够准确计算

。

另一方面，作者构造了另一个目标函数

h(G_{l,r})

：

h(G_{l,r}) := l(\frac{3+2re^9}{1+re^9} + r\frac{3+2re^{12}}{1+re^{12}})

并证明了对于任意的MPGNN+VN，存在

r_0

使得当

r > r_0

时：

\lim_{l\to\infty} |h(G_{l,r}) - B(G_{l,r})| = \infty

然而，存在一个GPS能够准确计算

。综上，作者得出结论，MPGNN+VN和GPS在一致性表达能力上是不可比的。

4. 实验发现

为了验证理论发现，作者在合成数据集上进行了实验。第一个实验基于定理4.3，测试MPGNN+VN和GPS学习目标函数

f(G_n) = n^2

的能力。

结果表明，MPGNN+VN能够完美预测训练分布外更大图的目标函数值。相比之下，GPS虽然在训练分布内表现良好，但在更大的图上性能迅速下降。这与推论4.4一致。

第二个实验基于定理4.7，比较两种模型学习目标函数

h(G_{l,r})

的能力。

可以看到，MPGNN+VN的误差随

和

的增加大约以两倍速率增长，而GPS的泛化能力更好。这与推论4.9相符合。

在真实数据集上，作者观察到混合的结果，MPGNN+VN和图Transformer都没有明显的优势。具体而言：

在LRGB的peptides数据集上，所有模型表现接近，与简单的MPGNN相比，MPGNN+VN和图Transformer都没有明显的优势。
在PascalVOC-SP上，GatedGCN+VN与GPS不相上下，表明虚拟节点在该任务上与自注意力机制效果相当。
在ogbg-molpcba上，GatedGCN+VN实现了最佳性能，比其他方法高出1%的平均精度。

总的来说，实验结果表明，在真实数据集任务中，带虚拟节点的MPGNN整体上是可以与图Transformer相媲美的。

5. 结论

本文比较了图Transformer与带虚拟节点的消息传递图神经网络的一致性表达能力。理论上，作者证明了两类模型都不是一致通用逼近器，并构造了它们各自能够表示而对方不能一致逼近的函数。这表明在一致性表达能力上，图Transformer与MPGNN+VN是不可比的。

合成实验验证了理论发现：当目标函数可被某一模型族一致表示而另一模型族不能时，前者确实展现出了更好的泛化能力。

在真实数据集上的实验显示出混合的结果，两类模型整体表现相近，都没有明显的优势。这与理论分析给出的"不可比"结论是一致的。此外，带虚拟节点的MPGNN在某些任务上能够实现最佳性能，表明简单高效的虚拟节点在实验中是足以和自注意力机制相媲美的。

用一句话来概括，在图学习领域，注意力并不总是你所需要的全部：in graphlearning, attention is often not all you need

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2024-04-25，如有侵权请联系 cloudcommunity@tencent.com 删除

神经网络

本文分享自 NewBeeNLP 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度