2017-GCN-Semi-Supervised Classif

2021-03-16 本文已影响0人不太聪明的亚子

原文链接：https://arxiv.org/abs/1609.02907

代码链接： https://github.com/tkipf/gcn.

出处： ICLR

关键词：semi-supervised, graph convolutional networks

一、motivation

通过在图上做卷积学习节点特征，做分类任务。

二、核心思想

1. 图卷积

首先，我们先明确所谓的卷积是什么意思，是计算中心节点和邻居节点的加权求和，本质上就是在汇聚邻居信息。在如图像这种的结构化数据中，卷积核具有平移不变性，而在图这种非结构化数据，CNN卷积核的平移不变形不再适用，我们需要在图拓扑中寻找邻居，然后定义图上的“卷积”操作来汇聚邻居节点的信息

传统的卷积有两种，一种是CNN那种，直接在数据空域中进行计算；还有一种是将数据通过傅里叶变换变到频域中进行计算。在图上，如果使用空域卷积，由于每个节点的邻居都不同，那么没有办法使用共享卷积核进行卷积操作；如果使用频域卷积，就需要先把图上的数据变换到频域，再计算。

作者选择了第二种，在图上使用频域卷积。

传统的频域卷积是这样的：函数 $f(t)$ 和 $f(h)$ 二者的卷积是其函数傅里叶变换乘积的逆变换，即：

$f*h = F^{-1}[\hat{f} (\omega )\hat{h(\omega)}]=\frac{1}{2\Pi } \int_{}^{} \hat{f} (\omega )\hat{h(\omega)}e^{i\omega t} d\omega$

其中， $\hat{f}(\omega )$ 和 $\hat{h}(\omega )$ 是傅里叶变换后的值， $e^{i\omega t}$ 是傅里叶变换的基函数。

那么仿照传统频域卷积，图卷积可以定义为： $（f*h)_{G} = U((U^T h)\odot (U^Tf))$ ，也是把 $f$ 和 $h$ 分别进行图傅里叶变换到频域相乘再逆变换回来。

对比可以发现，作者把图上的傅里叶变换定义为： $\hat{f} = U^Tf$ ， $\hat{h}=U^Th$ ，其中， $U$ 是图拉普拉斯矩阵的特征向量矩阵。所以，定义图卷积的关键在于定义图傅里叶变换，作者是怎么得到图上傅里叶变换公式的呢？

2. 图傅里叶变换

传统傅里叶变换： $X(f) = \int_{}^{}x(t)e^{-iwt}dt$ ，

其中， $x(t)$ 是空域表示， $X(f)$ 是频域表示， $e^{-iwt}$ 是基函数。

作者发现以 $e^{-iwt}$ 为基的拉普拉斯算子是：

对照 $AV=\lambda V$ ，可以发现，傅里叶变换中的基其实对照过来是矩阵的特征向量，那么将矩阵替换成图拉普拉斯矩阵，就是：

$LU=\lambda U$ ，那么这个 $U$ 应该也可以做为图傅里叶变换的基。

于是，作者定义图拉普拉斯矩阵的特征向量可以做图傅里叶变换的基，得到：

$F(\lambda)=\sum_{i=1}^N f(i)U^{i}$ ， $f(i)$ 是第 $i$ 个点的信号， $\lambda$ 是特征值。

3. 图卷积核

前面定义图卷积的计算是 $（f*h)_{G} = U((U^T h)\odot (U^Tf))$ ，把 $U^Th$ 表示成对角矩阵形式，则有

表示成函数形式为 $y_{output}=\sigma (Ug_\theta (\Lambda )U^Tx)$ ，输入是 $x$ ，输出是 $y_{output}$ ， $g_\theta (\Lambda )$ 是要学习的卷积核。

作者使用切比雪夫多项式近似做卷积核： $g_\theta (\Lambda )\approx \sum_{k=0}^{K-1}\beta _kT_k(\Lambda )$ ，其中， $T_k(x)=\cos (k\cdot arc\cos (x))$ ，则图卷积表示成：

$y_{output}=\sigma (U\sum_{k=0}^{K-1}\beta _kT_k(\tilde{\Lambda })U^Tx)=\sigma (\sum_{k=0}^{K-1}\beta _kT_k(U\tilde{\Lambda }U^T )x)=\sigma (\sum_{k=0}^{K-1}\beta _kT_k(\tilde{L} )x)$ ，化简完就不用计算拉普拉斯矩阵的特征向量了。

这里的 $k$ 表示考虑到几阶邻居。

当 $k=0$ 时， $T_0(\tilde{L} )=I$ ；

当 $k=1$ 时， $T_1(\tilde{L} )=\tilde{L}$ ;

当 $k>1$ 时， $T_k(\tilde{L} )=2\tilde{L}T_{k-1}(\tilde{L} )-T_{k-2}(\tilde{L} )$ .

其中， $\tilde{L}=2L/\lambda _{max}-I$ ， $I$ 是单位矩阵。

将拉普拉斯矩阵 $L$ 变换成 $\tilde{L}$ 是因为 $T_k(x)$ 中， $x$ 的取值范围是[-1,1]，而 $L$ 的范围是[0,1]，需要变换到[-1,1]的范围。

在GCN文章中，作者只考虑了一阶邻居，即 $k=0和k=1$ 的情况，且 $\lambda _{max}\approx 2$ ，则 $\tilde{L}=2L/\lambda _{max}-1=L-I _N$ ， $L=I_N-D^{-\frac{1}{2} }AD^{-\frac{1}{2} }$ 那么：

$g_\theta *x\approx \sum_{k=0}^{1}\beta _kT_k(\tilde{L} )x=\theta _0x+\theta _1(L-L_N)x =\theta _0x+\theta _1(I_N-D^{-\frac{1}{2} }AD^{-\frac{1}{2} }-I_N)x=\theta _0x-\theta _1D^{-\frac{1}{2} }AD^{-\frac{1}{2} }x$

因为 $\theta _0和\theta _1$ 之间没有约束，那么参数计算量会上升，所以作者把两个参数合并：

$g_\theta *x\approx\theta (I_N+D^{-\frac{1}{2} }AD^{-\frac{1}{2} })x$

其中， $\theta =\theta _0=-\theta_1$ .

又因为 $I_N+D^{-\frac{1}{2} }AD^{-\frac{1}{2} }$ 这个矩阵的特征值 $\in [0,2]$ ，在神经网络的训练中会导致梯度消失或爆炸，所以：

$I_N+D^{-\frac{1}{2} }AD^{-\frac{1}{2} }\rightarrow \tilde{D} ^{-\frac{1}{2} }\tilde{A}\tilde{D}^{-\frac{1}{2} }$

其中， $\tilde{A}= A+I_N$ ， $\tilde{D}_{ij}=\sum\nolimits_{j}\tilde{A}_{ij}$ .

所以，最后输入信号 $X\in R^{N\times C}$ ，

$Z=\tilde{D} ^{-\frac{1}{2} }\tilde{A}\tilde{D}^{-\frac{1}{2} }X\theta$

其中， $\theta \in R^{C\times F}$ ， $Z\in R^{N\times F}$

作者使用了两层GCN，表达式为： $Z=f(X,A)=softmax(\hat{A}ReLU(\hat{A}XW^{(0)} )W^{(1)} )$

其中， $\hat{A}=\tilde{D} ^{-\frac{1}{2} }\tilde{A}\tilde{D}^{-\frac{1}{2} }$

三、直观理解GCN计算公式

隐含层之间的传递

$h^l$ 是节点在第 $l$ 层的隐含表示，左边部分 $\tilde{D} ^{-\frac{1}{2} }\tilde{A}\tilde{D}^{-\frac{1}{2} }$ 是图的拉普拉斯矩阵， $\tilde{A} =A+I_N$ 是考虑了自连接的邻接矩阵， $\tilde{D}$ 是由 $\tilde{A}$ 计算得到的度矩阵，右边 $W^l$ 表示 $l$ 层神经网络要学习的参数。

直观理解这个公式就是先汇聚自身及邻居节点的信息，然后放入神经网络中学习。

我觉得最重要的就是这些了，剩下的是一些实验相关的内容，不难理解。另外就是作者使用的是半监督学习，只用很少的标签。

四、小结

1. GCN的突出贡献是将空域和频域的卷积操作联系起来，使得图卷积有了理论支撑；

2. 相比早期的图神经网络如node2vec只使用了拓扑结构，GCN使用了图的拓扑结构和节点特征；

3. GCN只考虑了一阶邻居，线性计算比较高效；

4. GCN虽然是学习节点embedding并分类，但它启发了后来很多研究，包括异构图，边分类等等。

2017-GCN-Semi-Supervised Classif

猜你喜欢

热点阅读