Google的這篇文章介紹瞭如何給線性注意力機制加上圖結構資訊。

Code

Paper

前置知識：

線性注意力：

線性注意力是self-attention的一個最佳化流派，能將複雜度從

O(N^2)

最佳化到

O(N)

。具體的，注意力機制可以表示為：

Attention(Q,K,V)=softmax(\frac{QK^T}{\sqrt{d}})V\tag{1}

其中

Q

，

K

，

V

是透過輸入線性變換得到的。線性注意力的思想是利用矩陣乘法的結合率，當我們先去掉上式的

softmax

和

\sqrt{d}

，那麼就變成了

(QK^T)V

，然後使用結合率將其變為

Q(K^TV)

，那麼複雜度就從

O(N^2)

到了

O(N)

。問題在於

softmax

是不能輕易拿掉的，只能想辦法從數學形式上去等價。Performer 證明了當為

Q

和

K

加上指數函式時在數學形式上可以近似原始的self-attention，也即

exp(Q)(exp(K^T)V)

。

為self-attention加上圖結構先驗：

因為self-attention的

QK^T

可以當作透過節點特徵相似度計算得到的完全鄰接矩陣。所以當把self-attention利用在圖任務上時可以考慮為其加上圖結構先驗避免只學習語義特徵。Graphormer 就是一個很好的為self-attention加上圖結構資訊的工作，順便推一下自己之前閱讀Graphormer做的筆記

https：//

zhuanlan。zhihu。com/p/38

7624418

。

Method

【Arxiv】 GKAT: Graph Kernel Attention Transformers 為線性注意力加上圖結構先驗

這篇文章巧妙的為線性注意力加上了圖結構先驗。當線性注意力不再計算

QK^T

， 同時也無法得到基於語義的鄰接矩陣，這篇文章的思路是把節點的結構向量的點積作為圖先驗知識。

此文首先給出瞭如下帶結構先驗的原始self-attention：

A_i(k,l)=\frac{K(q_k,k_l)T(k,l)}{\sum\limits_{r\in V}K(q_k,k_r)T(k,r)}\tag{2}

K和T分別對應模型圖中的

A_H

和

A_T

矩陣計算方式，K是基於語義的，T是基於結構的。 其中只要滿足

K:\mathbb{R}^d\times \mathbb{R}^d\to \mathbb{R}

和

T:V\times V\to \mathbb{R}

。翻譯成人話就是滿足對K輸入兩個向量返回一個實數，對T輸入兩個座標返回一個實數即可。一般來說

K=exp(qk^T)

，而T其實可以取圖鄰接矩陣中下標ij的值，也可以取圖拉普拉斯矩陣下標ij的值，或者是兩個節點隨機遊走得到向量的點積都行。

上式中T函式如果為節點的結構向量的點積，那麼其分子部分可以如下式表示，然後就能將其線性化：

K_{prod}(k,l)=\mathbb{E}[(\phi_K(q_K)\otimes \phi_T(k))(\phi_K(k_l)\otimes \phi_T(l))^T]\tag{3}

Random Walks Graph-Nodes Kernels：

另外此文提出了一個Random Walks Graph-Nodes Kernels方法獲得節點的結構向量，並使用節點的結構向量的點積作為式2中的T函式。如下所示：

T_{RWNGK}^{\lambda,\alpha,p}(k,l)=\frac{\mathbb{E}_{\omega_k}[f_k^{\omega_k,\lambda}]}{\Vert\mathbb{E}_{\omega_k}[f_k^{\omega_k,\lambda}]\Vert^\alpha_2}(\frac{\mathbb{E}_{\omega_l}[f_l^{\omega_l,\lambda}]}{\Vert\mathbb{E}_{\omega_l}[f_l^{\omega_l,\lambda}]\Vert^\alpha_2})^T\tag{3}

對於節點

h

，

f_h^{\omega_h,\lambda}\in\mathbb{R}^N

並且

f_h^{\omega_h,\lambda}(i)\mathop{=}\limits^{def}\sum\limits_{l\in L^{\omega(h)}(i)}\lambda^l

。其中

L^{\omega(h)}(i)

表示在給定隨機遊走

\omega(h)

的子序列中以

i

節點為終點的長度集合。同時此文提出了改進版anchor-points，也即在圖中隨機選取

s

個節點作為

h

節點的向量，表示為

f_h^{\omega_h,\lambda}\in\mathbb{R}^s

。下圖展示了選擇不同的方法作為T函式的視覺化結果。

【Arxiv】 GKAT: Graph Kernel Attention Transformers 為線性注意力加上圖結構先驗