GCN详解

155****7220

本文将详细阐述图卷积网络的相关内容。我们首先考虑一个多层图卷积网络（GCN），其层间传播规则如下：
$$
H^{(l+1)}=\sigma(\color{red}{\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}}H^{(l)}W^{(l)})
$$

$A~=A+IN\tilde{A}=A+I_N$ 表示图 $G$ 的邻接矩阵 $A$ 加上单位阵 $I_N$
$D~<em>ii=∑</em>jA~ij\tilde{D}<em>{ii}=\sum</em>{j}\tilde{A}_{ij}$

以一个具体的图 $G$ 为例

$$
\begin{align*}
\tilde{A}&=\begin{bmatrix}\color{red}{1}&\color{red}{1}&\color{red}{1}&0&0&0&0\\color{red}{1}&\color{red}{1}&\color{red}{1}&0&0&0&0\\color{red}{1}&\color{red}{1}&\color{red}{1}&\color{red}{1}&0&0&0\0&0&\color{red}{1}&\color{red}{1}&\color{red}{1}&\color{red}{1}&\color{red}{1}\0&0&0&\color{red}{1}&\color{red}{1}&\color{red}{1}&\color{red}{1}\0&0&0&\color{red}{1}&\color{red}{1}&\color{red}{1}&0\0&0&0&\color{red}{1}&\color{red}{1}&0&\color{red}{1}\end{bmatrix}\
\tilde{D}&=\begin{bmatrix}\color{red}{3}&0&0&0&0&0&0\0&\color{red}{3}&0&0&0&0&0\0&0&\color{red}{4}&0&0&0&0\0&0&0&\color{red}{5}&0&0&0\0&0&0&0&\color{red}{4}&0&0\0&0&0&0&0&\color{red}{3}&0\0&0&0&0&0&0&\color{red}{3}\end{bmatrix}\
\tilde{D}^{-\frac{1}{2}}&=\begin{bmatrix}\color{red}{\frac{1}{\sqrt{3}}}&0&0&0&0&0&0\0&\color{red}{\frac{1}{\sqrt{3}}}&0&0&0&0&0\0&0&\color{red}{\frac{1}{\sqrt{4}}}&0&0&0&0\0&0&0&\color{red}{\frac{1}{\sqrt{5}}}&0&0&0\0&0&0&0&\color{red}{\frac{1}{\sqrt{4}}}&0&0\0&0&0&0&0&\color{red}{\frac{1}{\sqrt{3}}}&0\0&0&0&0&0&0&\color{red}{\frac{1}{\sqrt{3}}}\end{bmatrix}
\end{align*}
$$
为了更好地理解上述公式的含义，例如为什么要引入 $D~\tilde{D}$ ？为什么要对 $D~\tilde{D}$ 取 $−12-\frac{1}{2}$ 次方而不是 $12\frac{1}{2}$ 次方，下面我将对上述公式进行详细解释

首先我们可以考虑将公式进行简化，即
$$
\begin{align*}
&H^{(l+1)}=\sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)}) \\Rightarrow &H^{(l+1)}=\sigma(\tilde{A}H^{(l)}W^{(l)})
\end{align*}
$$
对于 $A~H(l)\tilde{A}H^{(l)}$ 来说，它的实际含义如下图所示

$H^{(l)}$ 每一行代表的是图 $G$ 中每一个节点，根据矩阵乘法法则，从上图我们可以看出，第0号节点的表示即为0号节点+1号节点+2号节点

到这里我们就理解了， $A~H(l)\tilde{A}H^{(l)}$ 的含义是聚合周围节点的信息，来更新自己

但是简单的聚合似乎不太合理，因为不同的节点重要性不一样，因此我们应该引入一种类似于「注意力机制」的东西。具体来说，如果一个节点的「度」非常大，即与他相邻的节点非常多，那么它传递的消息，权重就应该小一点

举一个具体的例子，假设新垣结衣与你的室友都有直接的边与你相连，那么在她们两个人对你进行评价的时候，谁的评价更重要一点？很明显是你室友，因为新垣结衣的好友非常多，即新垣结衣的「度」非常大，那么他对你的了解可能就不太多。反之，你室友的「度」相比新垣结衣小很多，因此你室友对你的评价就会比较准确

总结一下GCN的流程：

$D~−12A~D~−12H(l)\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}$ 节点间进行特征传递
$σ(D~−12A~D~−12H(l)W(l))\sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})$ 对每一个节点做一次线性变换并且激活
重复 $L$ 次步骤1和步骤2，实现多层图卷积
获取最终的 $H^{(L)}$ 作为最终的节点表示，然后送入到下游任务中，例如节点分类

Reference

https://baidu-pgl.gz.bcebos.com/pgl-course/lesson_3.pdf