Graph Convolutional Network（GCN）

这里先回顾一下之前讲解的朴素图神经网络，如下图：

图中左上角方框部分可以看作图神经网络的初始状态。以 1 号节点为例, 在图神经网络中, 信息的传递是先汇聚一号节点的邻居节点信息, 得到汇聚后的新向量, 这个向量可以看作图神经网络第一层的输入信息 \(H^{(l)}\) 。然后 \(H^{(l)}\) 经过一个 MLP 的映射, 得到一个新的输出向量 \(H^{(l+1)}\), 这个向量则作为第二层图神经网络的输入信息, 依次类推, 可以定义出一个多层的图神经网络。层与层之间的信息传递公式可以写作:
$$
\boldsymbol{H}^{(l+1)}=\sigma\left(\boldsymbol{H}^{(l)} \boldsymbol{W}^{(l)}\right)
$$

而图卷积神经网络的计算公式则为:
$$
\boldsymbol{H}^{l+1}=\sigma\left(\tilde{\boldsymbol{D}}^{-\frac{1}{2}} \tilde{\boldsymbol{A}} \tilde{\boldsymbol{D}}^{-\frac{1}{2}} \boldsymbol{H}(l) \boldsymbol{W}(l)\right)
$$

两者最主要的区别就是图卷积神经网络比图神经网络多了一个 \(\tilde{\boldsymbol{D}}^{-\frac{1}{2}} \tilde{\boldsymbol{A}}^{-\frac{1}{2}}\) 。其中, \(\tilde{\boldsymbol{A}}=\boldsymbol{A}+\boldsymbol{I}_N, \boldsymbol{A}\) 就是图的邻接矩阵, \(\boldsymbol{I}_N\) 是一个全一的对角矩阵, 即:

$$
\begin{aligned}
& \boldsymbol{A}=\left(\begin{array}{cccc}
0 . & 1 . & 1 . & 0 . \\
1 . & 0 . & 1 . & 0 . \\
1 . & 1 . & 0 . & 1 . \\
0 . & 0 . & 1 . & 0 .
\end{array}\right) \quad \boldsymbol{I}_N=\left(\begin{array}{cccc}
1 . & 0 . & 0 . & 0 . \\
0 . & 1 . & 0 . & 0 . \\
0 . & 0 . & 1 . & 0 . \\
0 . & 0 . & 0 . & 1 .
\end{array}\right) \\
& \tilde{\boldsymbol{A}}=\boldsymbol{A}+\boldsymbol{I}_N=\left(\begin{array}{llll}
1 . & 1 . & 1 . & 0 . \\
1 . & 1 . & 1 . & 0 . \\
1 . & 1 . & 1 . & 1 . \\
0 . & 0 . & 1 . & 1 .
\end{array}\right) \\
&
\end{aligned}
$$

邻接矩阵 \(\boldsymbol{A}\) 表示的是节点与节点之间的关系，全一的对角矩阵 \(\boldsymbol{I}_N\) 表示的是节点自身,所以 \(\tilde{\boldsymbol{A}}=\boldsymbol{A}+\boldsymbol{I}_N\) 表示考虑了节点自身信息的邻接矩阵。

先将 \(\boldsymbol{A}\) 矩阵加入图卷积神经网络的计算公式中, 得到:
$$
\boldsymbol{H}^{(l+1)}=\sigma\left(\tilde{\boldsymbol{A}} \boldsymbol{H}^{(l)} \boldsymbol{W}^{(l)}\right)
$$

其中:
$$
\tilde{\boldsymbol{A}} \boldsymbol{H}^{(l)}=\left(\begin{array}{cccc}
1 . & 1 . & 1 . & 0 . \\
1 . & 1 . & 1 . & 0 . \\
1 . & 1 . & 1 . & 1 . \\
0 . & 0 . & 1 . & 1 .
\end{array}\right) *\left(\begin{array}{ccc}
1 . & 0 . & 0 . \\
0 . & 1 . & 0 . \\
0 . & 0 . & 1 . \\
0 . & 1 . & 1 .
\end{array}\right)=\left(\begin{array}{ccc}
1 . & 1+1 . & 1 . \\
1 . & 1 . & 1 . \\
1 . & 1+1 . & 1+1 . \\
0 . & 1 . & 1+1 .
\end{array}\right)
$$

表示每个节点向量要同时考虑自身节点和它相邻节点的信息。 \(\tilde{D}_{i i}=\Sigma_j \tilde{\boldsymbol{A}}_{i j}\) 是度矩阵, 表示的是每个节点的度数。例如, 图 9-44 中的一号节点, 考虑其自连接, 则度数等于 3 。
$$
\tilde{\boldsymbol{D}}=\left(\begin{array}{llll}
3 . & 0 . & 0 . & 0 . \\
0 . & 3 . & 0 . & 0 . \\
0 . & 0 . & 4 . & 0 . \\
0 . & 0 . & 0 . & 2 .
\end{array}\right)
$$
\(\tilde{\boldsymbol{D}}^{-1}\) 表示将度矩阵中的元素取倒数, \(\tilde{\boldsymbol{D}}^{-\frac{1}{2}}\) 则再取其平方根, 得到:

$$
\tilde{\boldsymbol{D}}^{-1}=\left(\begin{array}{cccc}
1 / 3 . & 0 . & 0 . & 0 . \\
0 . & 1 / 3 . & 0 . & 0 . \\
0 . & 0 . & 1 / 4 . & 0 . \\
0 . & 0 . & 0 . & 1 / 2 .
\end{array}\right) \tilde{\boldsymbol{D}}^{-\frac{1}{2}}=\left(\begin{array}{cccc}
0.57735027 & 0 . & 0 . & 0 . \\
0 . & 0.57735027 & 0 . & 0 . \\
0 . & 0 . & 0.5 & 0 . \\
0 . & 0 . & 0 . & 0.70710678
\end{array}\right)
$$

所以 \(\tilde{\boldsymbol{D}}^{-1}\left(\tilde{\boldsymbol{A}} \boldsymbol{H}^{(l)}\right)\) 相当于对 \(\tilde{\boldsymbol{A}} \boldsymbol{H}^{(l)}\) 结果的行做归一化, 即:

$$
\tilde{\boldsymbol{D}}^{-1}\left(\tilde{\boldsymbol{A}} \boldsymbol{H}^{(l)}\right)=\left(\begin{array}{cccc}
1 / 3 . & 0 . & 0 . & 0 . \\
0 . & 1 / 3 . & 0 . & 0 . \\
0 . & 0 . & 1 / 4 . & 0 . \\
0 . & 0 . & 0 . & 1 / 2 .
\end{array}\right) *\left(\begin{array}{ccc}
1 . & 1+1 . & 1 . \\
1 . & 1 . & 1 . \\
1 . & 1+1 . & 1+1 . \\
0 . & 1 . & 1+1 .
\end{array}\right) \\ =  \left(\begin{array}{ccc}
1 / 3 * 1 . & 1 / 3 *(1+1) . & 1 / 3 * 1 . \\
1 / 3 * 1 . & 1 / 3 * 1 . & 1 / 3 * 1 . \\
1 / 4 * 1 . & 1 / 4 *(1+1) . & 1 / 4 *(1+1) \\
1 / 2 * 0 . & 1 / 2 * 1 . & 1 / 4 *(1+1) .
\end{array}\right)
$$

同理, \(\left(\tilde{\boldsymbol{A}} \boldsymbol{H}^{(l)}\right) \tilde{\boldsymbol{D}}^{-1}\) 相当于对 \(\tilde{\boldsymbol{A}} \boldsymbol{H}^{(l)}\) 结果的列做归一化。最后, 公式(9-14)中左乘和右乘的矩阵使用的是 \(\tilde{\boldsymbol{D}}^{-\frac{1}{2}}\) 而不是 \(\tilde{\boldsymbol{D}}^{-1}\) 的原因是：当对行列元素各做一次归一化后, 相当于对节点向量的每个元素都做了两次归一化, 也就是多做了一次, 因此这里使用做归一化的矩阵的是 \(\tilde{\boldsymbol{D}}^{-\frac{1}{2}}\) 。最终, 图卷积神经网络的计算公式则为:
$$
\boldsymbol{H}^{l+1}=\sigma\left(\tilde{\boldsymbol{D}}^{-\frac{1}{2}} \tilde{\boldsymbol{A}} \tilde{\boldsymbol{D}}^{-\frac{1}{2}} \boldsymbol{H}(l) \boldsymbol{W}(l)\right)
$$

小结一下，图卷积神经网络GCN其实和卷积神经网络CNN没有什么关系。相比于朴素的图神经网络，GCN在做节点信息聚合时，增加了自身节点信息的考虑，并根据节点的度进行了节点向量的归一化处理。