最近沉迷游戏,暂不更新文章

MENU

GCN详解

February 27, 2021 • Read: 622 • Deep Learning阅读设置

本文将详细阐述图卷积网络的相关内容。我们首先考虑一个多层图卷积网络(GCN),其层间传播规则如下:

$$ H^{(l+1)}=\sigma(\color{red}{\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}}H^{(l)}W^{(l)}) $$

  • $\tilde{A}=A+I_N$表示图$G$的邻接矩阵$A$加上单位阵$I_N$
  • $\tilde{D}_{ii}=\sum_{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*} $$

为了更好地理解上述公式的含义,例如为什么要引入$\tilde{D}$?为什么要对$\tilde{D}$取$-\frac{1}{2}$次方而不是$\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*} $$

对于$\tilde{A}H^{(l)}$来说,它的实际含义如下图所示

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

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

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

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

总结一下GCN的流程:

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

Reference

Last Modified: March 1, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment