图卷积理解及实战

ryluo 2020-06-14 01:29:22
图网络

图卷积的基本定义及改进,以及GCN的代码实现

图卷积定义

任何一个图卷积层都可以写成如下的一个非线性函数:

$H^0=X$为第一层的输入,$X\in R^{N*D}$,$N$为节点个数,$D$为每个节点的特征维度,$A$为邻接矩阵,不同模型的差一点在于函数$f$的实现不同

一种简单的$f$可以定义为:

若是第一层图卷积,则还可以写为:

这种思路是基于节点特征与其所有邻居节点有关的思想。邻接矩阵$A$与特征$H$相乘,等价于,某节点的邻居节点的特征相加,而这样多个隐层的叠加就能利用多层邻居的信息。如下图为四个节点的有向图:

其邻接矩阵可以表示为(注意对角线元素全是0):

若节点特征为:

则:

从上述的公式中,由于邻接矩阵的元素中0代表两个节点之间没有边链接,1代表的是有边连接,而在做矩阵运算的时候只有为1的元素才会进行相加,所以本质上相当于,新节点是由原节点的近邻节点相加得到的。


图卷积改进一(增加自环)

在定义一中存在两个问题:

  1. 没有考虑节点自身对自身的影响
  2. 临界矩阵没有被规范化,度越大的节点聚合后形成的新节点的值越大(影响就越大),反之就越小。这可能导致反向传播的时候梯度消失或爆炸问题

定义二的图卷积公式主要是通过邻接矩阵增加自环,其实就是加了一个单位矩阵,使得节点考虑自身的影响。

对于上述实例表示为:

这样临界矩阵与特征相乘就考虑了自身对自身的影响,所以图卷积公式可以写为:


图卷积改进二(正则化)

先不考虑正则的话,对于每个节点如果链接的节点越多,那么产生的新节点的值就越大,那么我们可以让每个聚合后的新节点的特征值都除以原节点的度,这样就在一定程度上减小了上述2中的问题,即在度矩阵前面乘以一个度矩阵的逆。

先了解一下度矩阵,度矩阵是一个对角矩阵,其对角线上的元素等于节点对应的度数,若邻接矩阵为$A$,则度矩阵可以表示为:

如矩阵$A=\begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0
\end{bmatrix}$的度矩阵为$D=\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 2 & 0 & 0 \\
0 & 0 & 2 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}$

所以图卷积公式又可以写为:

除了上面对度矩阵的处理外还有一种用的比较多,也是论文中提出来的效果更好的一种拉普拉斯正则矩阵(Symmetric normalized Laplacian):

综上所述,最终图卷积的表达式为:

对于Symmetric normalized Laplacian正则的解释:

其中$deg(v_i),deg(v_j)$分别为$i,j$节点的度,也就是度矩阵在节点$i,j$处的值

参考文献:

GRAPH CONVOLUTIONAL NETWORKS

一文读懂图卷积GCN

图卷积网络到底怎么做,这是一份极简的Numpy实现

图卷积实现