GCN系列1-gcn入门

又双叒叕挖一个坑,GCN两年前刚入门dl的时候就听说过了,甚至在知乎上为其专门建了一个收藏文件夹,然而从来没有去深入了解过。原因是之前自学数据结构后一直以来对图结构有莫名的恐惧,毕竟确实没花时间好好学。但是该来的还是逃不掉的,无论是做nlp还是图像/视频处理,gcn都是要学的~

Why GCN?

图像视频或文本语音都是 Euclidean Structure. 而对于 Non Euclidean Structure的数据,比如社交网络、信息网络中有很多类似的结构无法使用CNN/RNN来进行处理, GCN就是来处理这类结构的数据的。

事实上,广义上讲,任何数据在赋范空间内都可以建立拓扑关联.
社交网络拓扑示意(Non Euclidean Structure)

其实任何结构都可以看作是图,图像也好,自然语言也罢,都是特殊的图结构。语言实际上其内部也是复杂的树形结构,也是一种图结构;而像图片,在做目标识别的时候,我们关注的实际上只是二维图片上的部分关键点,这些点组成的也是一个图的结构。

Basis of graph theory

GCN 和 谱聚类都是基于图论的,先温习下图的相关概念。

无向图

谱聚类基础之无向权重图

  • 图 G(V,E). V 是顶点的集合,E是边。
  • 度矩阵:对于有边连接的两个点 \(v_i\)\(v_j\)\(w_{ij}>0\),对于没有边连接的两个点 \(v_i\)\(v_j\)\(w_{ij}=0\)。对于图中的任意一个点 \(v_i\),它的度 \(d_i\) 定义为和它相连的所有边的权重之和,即 \(d_i=\sum_{j=1}^nw_{ij}\). 利用每个点度的定义,我们可以得到一个 nxn 的度矩阵D,它是一个对角矩阵,只有主对角线有值,对应第i行的第i个点的度数 \[ \begin{pmatrix} d_1 & ... & ... \\ ... & d_2 & ... \\ ... & ... & ... \\ ... & ... & d_n \\ \end{pmatrix} \]

利用所有点之间的权重值,我们可以得到图的邻接矩阵W,它也是一个nxn的矩阵,第i行的第j个值对应我们的权重wij. 如果是无权重值的图,则用0、1来表示这两个节点之间是否有边。

这是一个无向无权图。

邻接矩阵

谱聚类基础之相似矩阵 这里的相似矩阵就是邻接矩阵,邻接矩阵的值代表着顶点之间的相似度,而相似度如何定量,就是这篇文章中第三节提到的三种构建方法。 - \(\epsilon\)邻近法
- k近邻法,这里涉及到一个问题,就是两个顶点不一定互为k近邻。为了保证邻接矩阵是对称的,有两种解决方案
- 全连接法,所有权重都大于1,具体的权重计算可以选择不同的核函数

拉普拉斯矩阵

拉普拉斯矩阵: \(L=D-W\)
拉普拉斯矩阵有一些很好的性质如下:
- 拉普拉斯矩阵是对称矩阵,这可以由D和W都是对称矩阵而得。
- 由于拉普拉斯矩阵是对称矩阵,则它的所有的特征值都是实数。
- 对于任意的向量f,我们有
\[f^TLf = \frac{1}{2}\sum\limits_{i,j=1}^{n}w_{ij}(f_i-f_j)^2\]

\[f^TLf = f^TDf - f^TWf = \sum\limits_{i=1}^{n}d_if_i^2 - \sum\limits_{i,j=1}^{n}w_{ij}f_if_j\] \[=\frac{1}{2}( \sum\limits_{i=1}^{n}d_if_i^2 - 2 \sum\limits_{i,j=1}^{n}w_{ij}f_if_j + \sum\limits_{j=1}^{n}d_jf_j^2) = \frac{1}{2}\sum\limits_{i,j=1}^{n}w_{ij}(f_i-f_j)^2\] - 拉普拉斯矩阵是半正定的,且对应的n个实数特征值都大于等于0,即 \(0=λ_1≤λ_2 ≤...≤ λ_n\), 且最小的特征值为0,这个由性质3很容易得出。

初识 GCN

开山之作:Semi-supervised classification with graph convolutional networks