• 问答
  • 技术
  • 实践
  • 资源
【Arxiv】 GKAT: Graph Kernel Attention Transformers 为线性注意力加上图结构先验
技术讨论
来源 | LMissher


image.png

线性注意力:

线性注意力是self-attention的一个优化流派,能将复杂度从 [公式] 优化到 [公式]。具体的,注意力机制可以表示为:

[公式]

其中 [公式][公式][公式] 是通过输入线性变换得到的。线性注意力的思想是利用矩阵乘法的结合率,当我们先去掉上式的 [公式][公式],那么就变成了 [公式],然后使用结合率将其变为 [公式],那么复杂度就从 [公式] 到了 [公式]。问题在于 [公式] 是不能轻易拿掉的,只能想办法从数学形式上去等价。Performer 证明了当为 [公式][公式] 加上指数函数时在数学形式上可以近似原始的self-attention,也即 [公式]

为self-attention加上图结构先验:

因为self-attention的 [公式] 可以当作通过节点特征相似度计算得到的完全邻接矩阵。所以当把self-attention利用在图任务上时可以考虑为其加上图结构先验避免只学习语义特征。Graphormer 就是一个很好的为self-attention加上图结构信息的工作,顺便推一下自己之前阅读Graphormer做的笔记https://zhuanlan.zhihu.com/p/387624418

Method

这篇文章巧妙的为线性注意力加上了图结构先验。当线性注意力不再计算 [公式], 同时也无法得到基于语义的邻接矩阵,这篇文章的思路是把节点的结构向量的点积作为图先验知识。

此文首先给出了如下带结构先验的原始self-attention:

[公式]

K和T分别对应模型图中的 [公式][公式]矩阵计算方式,K是基于语义的,T是基于结构的。 其中只要满足 [公式][公式]。翻译成人话就是满足对K输入两个向量返回一个实数,对T输入两个坐标返回一个实数即可。一般来说 [公式],而T其实可以取图邻接矩阵中下标ij的值,也可以取图拉普拉斯矩阵下标ij的值,或者是两个节点随机游走得到向量的点积都行。

上式中T函数如果为节点的结构向量的点积,那么其分子部分可以如下式表示,然后就能将其线性化:

[公式]

Random Walks Graph-Nodes Kernels:

另外此文提出了一个Random Walks Graph-Nodes Kernels方法获得节点的结构向量,并使用节点的结构向量的点积作为式2中的T函数。如下所示:

[公式]

对于节点 [公式][公式] 并且 [公式]。其中 [公式] 表示在给定随机游走 [公式] 的子序列中以 [公式] 节点为终点的长度集合。同时此文提出了改进版anchor-points,也即在图中随机选取 [公式] 个节点作为 [公式] 节点的向量,表示为 [公式]。下图展示了选择不同的方法作为T函数的可视化结果。


相关推荐:

线性 Attention 的探索:Attention 必须有个 Softmax 吗?
图解 Transformer — Attention Is All You Need

  • 0
  • 0
  • 1569
收藏
暂无评论