GCN

CNN和GCN的联系与区别

1. 什么是离散卷积？CNN中卷积发挥什么作用？

CNN中的卷积本质上就是利用一个共享参数的过滤器（kernel），通过计算中心像素点以及相邻像素点的加权和来构成feature map实现空间特征的提取，当然加权系数就是卷积核的权重系数。

那么卷积核的系数如何确定的呢？是随机化初值，然后根据误差函数通过反向传播梯度下降进行迭代优化。这是一个关键点，卷积核的参数通过优化求出才能实现特征提取的作用，GCN的理论很大一部分工作就是为了引入可以优化的卷积参数。

2. GCN中的Graph指什么？为什么要研究GCN？

GCN中的Graph

CNN可以有效的提取空间特征。但是有一点需要注意：CNN处理的图像或者视频中像素点是排列成很整齐的（也就是很多论文中所提到的Euclidean Structure）

与之相对应，科学研究中还有很多 Non Euclidean Structure的数据，例如社交网络、信息网络中有很多类似的结构。

实际上，这样的网络结构就是图论中抽象意义上的拓扑图

所以，Graph Convolution Network中的Graph是指数学（图论）中的用顶点和边建立相应关系的拓扑图

那么为什么要研究GCN？

• CNN无法处理Non Euclidean Structure的数据，学术上的表达就是传统的离散卷积，在Non Euclidean Structure的数据上无法保持平移不变性。通俗理解就是在拓扑图中每个定点的相邻顶点数目都可能不同，那么当然无法用一个同样尺寸的卷积核来进行卷积运算
• 由于CNN无法处理Non Euclidean Structure的数据，又希望在这样的数据结构（拓扑图）上有效地提取特征空间来进行机器学习，所以GCN成为了研究的重点
• 广义上来讲，任何数据在赋范空间内都可以建立拓扑关联，谱聚类就是应用了这样的思想。所以说拓扑连接是一种广义的数据结构，GCN有很大的应用空间。

3. 提取拓扑图空间特征的两种方式

GCN的本质目的就是用来提取拓扑图的空间特征，目前实现这个目标的最主要的两种方式是：vertex domain(spatial domain)和spectral domain

vertex domain(spatial domain)

这是一种非常直观的方式，顾名思义：提取拓扑图上的空间特征，那么就把每个顶点相邻的neighbors找出来。这里面蕴含的科学问题有二：

• 按照什么条件去找中心vertex的neighbors，也就是如何确定receptive field？
• 确定receptive field，按照什么方式处理包含不同neighbors的特征？

根据这两个问题设计算法，就可以实现目标了。

这种方法主要的缺点如下：

• 每个定点提取出来的neighbors不同，使得计算处理必须针对每个顶点
• 提取特征的效果可能没有卷积好

spectral domain

就是GCN的理论寄出了。这种思路就是希望接组合图谱的理论来实现拓扑图上的卷积操作。从整个研究的时间进程来看：首先研究GSP（Graph signal processing）的学者定义了graph上的Fourier Transformation，进而定义了graph上的convolution，最后与深度学习结合提出了Graph Convolution Network

Q1：什么是Spectral graph theory？

简单的概括就是借助图的拉普拉斯矩阵的特征值和特征向量来研究图的性质

Q2：GCN为什么要利用Spectral graph theory？

4. 什么是拉普拉斯矩阵？为什么GCN要用拉普拉斯矩阵？

什么是拉普拉斯矩阵？

Graph Fourier Transformation及Graph Convolution的定义都用到了拉普拉斯矩阵，那么首先介绍一下拉普拉斯矩阵

对于图$G = (V, E)$，其$Laplacian$矩阵的定义为$L = D - A$，其中$L$是$Laplacian$矩阵，$D$是定点的度矩阵（对角矩阵），对角线上元素依次为各个顶点的度，$A$是图的邻接矩阵。看下图，很快就能知道$Laplacian$矩阵的计算方法

这里要说明的是：常用的拉普拉斯矩阵实际有三种:

• $L = D - A$定义的$Laplacian$矩阵更专业的名称叫Combinatorial Laplacian

• $L^{sys} = D^{-1/2}LD^{-1/2}$定义的叫Symmetric normalized Laplacian

• $L^{rw} = D^{-1}L$定义的叫Random walk normalized Laplacian

为什么GCN要用拉普拉斯矩阵？

• 拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解），这就和GCN的spectral domain对应上了
• 拉普拉斯矩阵只在中心定点和一阶相连的顶点上（1-hop neighbor）有非0元素，其余之处全为0
• 通过拉普拉斯算子与拉普拉斯矩阵进行类比

拉普拉斯矩阵的谱分解（特征分解）

GCN的核心基于拉普拉斯矩阵的谱分解。

首先，矩阵的谱分解，特征分解，对角化都是一个概念

不是所有的矩阵都可以特征分解，其充要条件为n阶方阵存在n个线性无关的特征向量。

但是拉普拉斯矩阵是半正定对称矩阵（半正定矩阵本身就是对称矩阵），有如下三个性质：

• 对称矩阵一定有n个线性无关的特征向量
• 半正定矩阵的特征值一定非负
• 对称矩阵的特征向量相互正交，即所有特征向量构成的矩阵为正交矩阵

由上可以知道拉普拉斯矩阵一定可以谱分解，且分解后有特殊的形式。

对于拉普拉斯矩阵其谱分解为：

$L=U\left(\begin{array}{ccc}{\lambda_{1}} & {} \\ {} & {\ddots} & {} \\ {} & {} & {\lambda_{n}}\end{array}\right) U^{-1}$

其中$U=(\overrightarrow{u_{1}}, \overrightarrow{u_{2}}, \cdots, \overrightarrow{u_{n}})$，是列向量为单位特征向量的矩阵，也就是$\overrightarrow{u_{l}}$是列向量。

$\left(\begin{array}{cccc}{\lambda_{1}} \\ {} & {} & {\ddots} \\ {} & {} & {} & {\lambda_{n}}\end{array}\right)$是n个特征值构成的对角矩阵

由于$U$是正交矩阵，即$UU^{T} = E$

所以特征分解又可以写成：

$L=U\left(\begin{array}{ccc}{\lambda_{1}} & {} & {} \\ {} & {\ddots} & {} \\ {} & {} & {\lambda_{n}}\end{array}\right) U^{T}$

6. 如何从传统的傅里叶变换、卷积类比到Graph上的傅里叶变换及卷积？

把传统的傅里叶变换以及卷积迁移到Graph上来，核心工作其实就是把拉普拉斯算子的特征函数$e^{-iwt}$变为Graph对应的拉普拉斯矩阵的特征向量

• Graph上的傅里叶变换

  传统的傅里叶变换定义为：

  $F(\omega)=\mathcal{F}[f(t)]=\int f(t) e^{-i \omega t} d t$

信号$f(t)$与基函数$e^{-iwt}$的积分，那么为什么要找