Graph Attention Networks

1 Graph Attention Networks

[Velickovic P, 2017, 1] 提出了图的注意力网络，利用注意力机制聚合信息，相当于空间法的卷积。

用$\vec{h}_{i}^{(l)}$hi(l)​表示第$l$l层的第$i$i个顶点的特征向量。

• attention coefficient :

$e_{ij} = a \left( W \vec{h}_{i}^{(l)}, W \vec{h}_{j}^{(l)} \right). \tag{1.1}$eij​=a(Whi(l)​,Whj(l)​).(1.1)

其中$a(\cdot)$a(⋅)是非线性**函数，原文给的是$\text{LeakReLU}_{\alpha=0.2} \left( \vec{a} \left[ W \vec{h}_{i}^{(l)} \| W \vec{h}_{j}^{(l)} \right] \right)$LeakReLUα=0.2​(a[Whi(l)​∥Whj(l)​])，$\|$∥是拼接操作。

• attention mechanism：

$\alpha_{ij} = \text{softmax}_j(e_{ij}) = \frac{ \exp(e_{ij}) }{\sum_{k \in \mathcal{N}(i)} \exp (e_{ik}) }. \tag{1.2}$αij​=softmaxj​(eij​)=∑k∈N(i)​exp(eik​)exp(eij​)​.(1.2)

用注意力作信息聚合。单头注意力：
$\vec{h}_{i}^{(l+1)} = \sigma \left( \sum_{j \in \mathcal{N}(i)} \alpha_{ij} W \vec{h}_{j}^{(l)} \right). \tag{1.3}$hi(l+1)​=σ⎝⎛​j∈N(i)∑​αij​Whj(l)​⎠⎞​.(1.3)

多头注意力为：
$\vec{h}_{i}^{(l+1)} = {\Large \|}_{k=1}^{K} \sigma \left( \sum_{j \in \mathcal{N}(i)} \alpha_{ij}^k W^k \vec{h}_{j}^{(l)} \right). \tag{1.4}$hi(l+1)​=∥k=1K​σ⎝⎛​j∈N(i)∑​αijk​Wkhj(l)​⎠⎞​.(1.4)

平均注意力：
$\vec{h}_{i}^{(l+1)} = \sigma \left( \frac{1}{K} \sum_{k=1}^{K} \sum_{j \in \mathcal{N}(i)} \alpha_{ij}^k W^k \vec{h}_{j}^{(l)} \right). \tag{1.5}$hi(l+1)​=σ⎝⎛​K1​k=1∑K​j∈N(i)∑​αijk​Wkhj(l)​⎠⎞​.(1.5)

2 Watch Your Step: Learning Node Embeddings via Graph Attention

[Abuelhaija S, 2018, 2] 在利用转移矩阵$\mathcal{T}=\text{diag}(A \times \vec{1}_N)^{-1} \times A$T=diag(A×1N​)−1×A作随机游走计算共现矩阵$D$D（co-occurrence matrix）时，使用注意力作概率对每次转移加权。
$\mathbb{E}\left[D;Q_1,Q_2,\cdots,Q_C \right] = \tilde{P}^{(0)} \sum_{k=1}^{C} Q_k \left( \mathcal{T} \right)^k = \tilde{P}^{(0)} \mathbb{E}_Q[\left( \mathcal{T} \right)^k]. \tag{2.1}$E[D;Q1​,Q2​,⋯,QC​]=P~(0)k=1∑C​Qk​(T)k=P~(0)EQ​[(T)k].(2.1)

其中$C$C是总的随机游走步数，$\tilde{P}^{(0)}$P~(0)是初始的位置对角阵，$\sum_k Q_k = 1$∑k​Qk​=1。

使用注意力机制：
$(Q_1,Q_2,Q_3,\cdots) = \text{softmax}((q_1,q_2,q_3,\cdots)). \tag{2.2}$(Q1​,Q2​,Q3​,⋯)=softmax((q1​,q2​,q3​,⋯)).(2.2)

3 GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs

[Zhang J, 2018, 3] 使用了Gate门控注意力，就是在[Velickovic P, 2017, 1]提出的注意力中的$\sum_{j \in \mathcal{N}(i)} \alpha_{ij} W \vec{h}_{j}^{(l)}$∑j∈N(i)​αij​Whj(l)​的部分再加入一个权重门控：
$\vec{h}_{i}^{(l+1)} = {\Large \|}_{k=1}^{K} \sigma \left( \sum_{j \in \mathcal{N}(i)} g_{i}^{k} \alpha_{ij}^k W^k \vec{h}_{j}^{(l)} \right). \tag{3.1}$hi(l+1)​=∥k=1K​σ⎝⎛​j∈N(i)∑​gik​αijk​Wkhj(l)​⎠⎞​.(3.1)
门控$\vec{g}_i$g​i​:
$\vec{g}_i = (g_{i}^{1},\cdots,g_{i}^{K}) = \sigma \left( \vec{h}_i^{(l)} \| \max_{j \in \mathcal{N}(i)} \left(\{ W_1 \vec{h}_j^{(l)} + \vec{b}_1 \} \right) \| \frac{ \sum_{j \in \mathcal{N}(i)} \vec{h}_j^{(l)} }{|\mathcal{N}(i)|} \right) W_2 + \vec{b}_2. \tag{3.2}$g​i​=(gi1​,⋯,giK​)=σ(hi(l)​∥j∈N(i)max​({W1​hj(l)​+b1​})∥∣N(i)∣∑j∈N(i)​hj(l)​​)W2​+b2​.(3.2)

4 Graph Classification using Structural Attention

[Lee J B, 2018, 4] 提出了结构注意力，就是对邻居信息聚合时使用了注意力机制。

上图中$f_s(\cdot:\theta_s)$fs​(⋅:θs​)对邻居顶点信息聚合，$f_h(\cdot:\theta_h)$fh​(⋅:θh​)对隐藏层表达更新，$f_c(\cdot:\theta_c)$fc​(⋅:θc​)使用新的隐藏层表达预测标签，$f_r(\cdot:\theta_r)$fr​(⋅:θr​)则生成新的排序向量（反映顶点的类型重要性排序）$\vec{r}_t$rt​。

$f_s(\cdot:\theta_s)$fs​(⋅:θs​)也称作Step Module，工作原理见下图。$A,D$A,D别是邻接矩阵和顶点特征向量矩阵，$c_{t-1}$ct−1​是当前顶点。而$\vec{r}_{t-1}$rt−1​是排序向量，$\tau: \reals^{N \times D} \rightarrow \reals^{N \times R}$τ:RN×D→RN×R，$R$R是顶点类型，也可以看成是将原理的特征变换后的新特征表达。其中$(T \vec{r}_{t-1})^T$(Trt−1​)T就是注意力权重。

参考文献

• 1 Velickovic P, Cucurull G, Casanova A, et al. Graph Attention Networks[J]. arXiv: Machine Learning, 2017.

• 2 Abuelhaija S, Perozzi B, Alrfou R, et al. Watch Your Step: Learning Node Embeddings via Graph Attention[C]. neural information processing systems, 2018: 9180-9190.

• 3 Zhang J, Shi X, Xie J, et al. GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs[J]. arXiv: Learning, 2018.

• 4 Lee J B, Rossi R A, Kong X, et al. Graph Classification using Structural Attention[C]. knowledge discovery and data mining, 2018: 1666-1674.