GAT 图注意力网络 Graph Attention Network

图神经网络 GNN 把深度学习应用到图结构 (Graph) 中,其中的图卷积网络 GCN 可以在 Graph 上进行卷积操作。但是 GCN 存在一些缺陷:依赖拉普拉斯矩阵,不能直接用于有向图;模型训练依赖于整个图结构,不能用于动态图;卷积的时候没办法为邻居节点分配不同的权重。因此 2018 年图注意力网络 GAT (Graph Attention Network) 被提出,解决 GCN 存在的问题。

1.GCN 缺点

在之前的文章38.图神经网络 GNN 之图卷积网络 (GCN)介绍了图卷积神经网络 GCN,不熟悉的童鞋可以参考一下。GNN 模型可以分为频谱域 (spectral domain) 和空间域 (spatial domain) 两大类:spectral 的方法通常利用了拉普拉斯矩阵,借助图谱的方式进行卷积操作;spatial 的方法通常使用更直接的方式聚合邻居节点的信息。

之前介绍的该 GCN 模型是基于频谱域 (spectral domain) 的,利用了拉普拉斯矩阵,总的来说 GCN 存在下面的缺点:

GCN 假设图是无向的,因为利用了对称的拉普拉斯矩阵 (只有邻接矩阵 A 是对称的,拉普拉斯矩阵才可以正交分解),不能直接用于有向图。GCN 的作者为了处理有向图,需要对 Graph 结构进行调整,要把有向边划分成两个节点放入 Graph 中。例如 e1、e2 为两个节点,r 为 e1,e2 的有向关系,则需要把 r 划分为两个关系节点 r1 和 r2 放入图中。连接 (e1, r1)、(e2, r2)。

GCN 不能处理动态图,GCN 在训练时依赖于具体的图结构,测试的时候也要在相同的图上进行。因此只能处理 transductive 任务,不能处理 inductive 任务。transductive 指训练和测试的时候基于相同的图结构,例如在一个社交网络上,知道一部分人的类别,预测另一部分人的类别。inductive 指训练和测试使用不同的图结构,例如在一个社交网络上训练,在另一个社交网络上预测。

GCN 不能为每个邻居分配不同的权重,GCN 在卷积时对所有邻居节点均一视同仁,不能根据节点重要性分配不同的权重。

2018 年图注意力网络 GAT 被提出,用于解决 GCN 的上述问题,论文是《GRAPH ATTENTION NETWORKS》。GAT 采用了 Attention 机制,可以为不同节点分配不同权重,训练时依赖于成对的相邻节点,而不依赖具体的网络结构,可以用于 inductive 任务。

2.GAT

假设 Graph 包含 N 个节点,每个节点的特征向量为 hi,维度是 F,如下所示:

GAT 图注意力网络 Graph Attention Network节点特征向量 h

对节点特征向量 h 进行线性变换,可以得到新的特征向量 h’i,维度是 F’,如下所示,W 为线性变换的矩阵:

GAT 图注意力网络 Graph Attention Network节点特征向量线性变换 h'

节点 j 是节点 i 的邻居,则可以使用 Attention 机制计算节点 j 对于节点 i 的重要性,即 Attention Score:

GAT 图注意力网络 Graph Attention NetworkAttention Score

GAT 具体的 Attention 做法如下,把节点 i、j 的特征向量 h’i、h’j 拼接在一起,然后和一个 2F’ 维的向量 a 计算内积。激活函数采用 LeakyReLU,公式如下:

GAT 图注意力网络 Graph Attention NetworkGAT Attention 计算方式

Attention 如下图所示:

GAT 图注意力网络 Graph Attention NetworkGAT Attention 示意图

经过 Attention 之后节点 i 的特征向量如下:

GAT 图注意力网络 Graph Attention NetworkAttention 后的特征向量

GAT 也可以采用 Multi-Head Attention,即多个 Attention,如下图所示:

GAT 图注意力网络 Graph Attention NetworkGAT Multi-Head Attention

如果有 K 个 Attention,则需要把 K 个 Attention 生成的向量拼接在一起,如下:

GAT 图注意力网络 Graph Attention NetworkK 个 Attention 输出结果拼接

但是如果是最后一层,则 K 个 Attention 的输出不进行拼接,而是求平均。

GAT 图注意力网络 Graph Attention Network最后一层 Attention 输出结果

取出节点在 GAT 第一层隐藏层向量,用 T-SNE 算法进行降维可视化,得到的结果如下,可以看到不同类别的节点可以比较好的区分。

GAT 图注意力网络 Graph Attention NetworkGAT 节点向量降维可视化

3.GAT 总结

GAT 的时间复杂度为 O(|V|FF’+|E|F’),其中 |V|FF’ 是计算所有节点特征向量变换的时间复杂度 (即 Wh),|E|F’ 是计算 Attention 的时间复杂度。GAT 不依赖于完整的图结构,只依赖于边,因此可以用于 inductive 任务。GAT 可用于有向图。采用 Attention 机制,可以为不同的邻居节点分配不同的权重。4.参考文献

GRAPH ATTENTION NETWORKS

SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS