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 机制，可以为不同的邻居节点分配不同的权重。