GAT学习笔记
发布于2020-11 浏览:2034 回复:0
0
收藏
快速回复

Graph Attention Networks(ICLR 2018)

论文链接:https://arxiv.org/pdf/1710.10903.pdf

1.GCN缺点

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

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

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

2.GAT

GAT 采用了 Attention 机制,可以为不同节点分配不同权重,训练时依赖于成对的相邻节点,而不依赖具体的网络结构,可以用于 inductive 任务。

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

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

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


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


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

GAT 也可以采用 Multi-Head Attention,如果有 K 个 Attention,则需要把 K 个 Attention 生成的向量拼接在一起,如下:

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

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

3.总结

(1)GAT 的时间复杂度为 O(|V|FF'+|E|F'),其中 |V|FF' 是计算所有节点特征向量变换的时间复杂度 (即 Wh),|E|F' 是计算 Attention 的时间复杂度。

(2)GAT 不依赖于完整的图结构,只依赖于边,因此可以用于 inductive 任务。

(3)GAT 可用于有向图。采用 Attention 机制,可以为不同的邻居节点分配不同的权重。

 

收藏
点赞
0
个赞
TOP
切换版块