图卷积神经网络入门基础

#卷积

#定义

卷积是一种数学运算,称$(f*g)(n)$为$f,g$的卷积,

其连续的定义为:

$$(f*g)(n) = \int_{-\infty}^{+\infty} f(\tau)g(n-\tau)d\tau$$

离散的定义为:

$$(f*g)(n) = \sum\limits_{\tau = -\infty}^\infty f(\tau)g(n-\tau)$$

若令$x = \tau,y = n-\tau$,则$x+y = n$表示的是平行的直线。

对于图像来说,图像上的滑动窗口很好的解释了卷积的定义:

gnn1

可以发现,我们对$f,g$进行卷积操作,保证$x,y$坐标的和都为1:

gnn2

写成卷积公式为:

$$(f*g)(1,1) = \sum\limits_{k=0}^{2}\sum\limits_{h=0}^{2}f(h,k)g(1-h,1-k)$$

这样就实现了使用$g$这个算子在图像上的滑动。但注意,在数学中的卷积运算中,卷积核与原始的矩阵乘积,是围绕着中心元素进行180度旋转后,才是对应的元素

而在实际的图像空间滤波中,我们是将设计的特定卷积核,然后将其与像素矩阵的对应元素(不进行上述的旋转)相乘得到。例如,在CV中常见的平滑滤波,高斯滤波。这些滤波被设计出来,以提取不同的特征。

对于神经网络来讲,最大的不同是,这些滤波不需要我们自己去定义(也就是提取特征的过程),而是通过网络自身训练每一个卷积层的滤波器。让这些滤波器组对特定的模式有高的激活,以达到CNN网络的分类/检测等目的。因此,在CNN中,由于这些卷积核都是未知参数,需要根据数据训练学习,那么翻不翻转已经没有关系了。

#理解

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

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

#Laplacian matrix

我们上离散数学都学过,图拉普拉斯矩阵的定义为:

$$L = D -W$$

其中,$D$ 是顶点的度矩阵(对角矩阵),$W$是图的邻接矩阵(带边权重)。其normalized形式为:

$$L^{nor} = D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$$

但为什么是这样定义呢?我们先从拉普拉斯算子说起。

#Laplacian

其数学定义为:

$$\Delta = \sum\limits_i \frac{\delta^2}{\delta x_i^2}$$

即为非混合二阶偏导数的和

#图像中的拉普拉斯算子

图像是一种离散数据,那么其拉普拉斯算子必然要进行离散化。

从导数定义:

$$f'(x) = \frac{\delta f(x)}{\delta x} \approx f(x+1) - f(x)$$

因此可以得到二阶导为:

$$f''(x) = \frac{\delta^2 f(x)}{\delta x^2} \approx f'(x) - f'(x-1) \approx f(x+1) + f(x-1) - 2f(x)$$

因此我们可以得到结论:

  • 二阶导数近似等于其二阶差分。
  • 二阶导数等于其在所有自由度上微扰之后获得的增益。一维函数其自由度可以理解为2,分别是+1和-1两个方向。

对于二维的图像来说,其有两个方向(4个自由度)可以变化,即如果对(x,y)处的像素进行扰动,其可以变为四种状态:

$$(x+1,y),(x-1,y),(x,y+1),(x,y-1)$$

当然了,如果将对角线方向也认为是一个自由度的话,会再增加几种状态:

$$(x+1,y+1),(x+1,y-1),(x-1,y+1),(x-1,y-1)$$

事实上图像处理上正是这种。

为了简便起见,这里只讨论第一种:

$$\Delta = \frac{\delta^2f(x,y)}{\delta x} + \frac{\delta^2f(x,y)}{\delta y} \approx f(x+1,y) + f(x-1,y) + f(x,y+1) + f(x,y-1) - 4f(x,y)$$

这不就是我们常见的拉普拉斯滤波吗。

这给我们一种形象的结论:拉普拉斯算子就是在所有自由度上进行微小变化后获得的增益。

#Graph

对于有N个节点的Graph,就设节点为$1...N$,且其邻接矩阵为$W$。

若这个Graph是一个完全图,即任意两个节点之间都有一条边,那么对一个节点进行微扰,它可能变成任意一个节点。因此,该Graph的自由度最多为$N$。

那么对应的函数是一个$N$维向量,即$f= (f_1,...,f_N)$,这里,$f_i$表示函数$f$在节点$i$的值。

对于任意节点$i$进行微扰,它可能变为任意一个与他相邻的节点 $j \in\mathcal{N_i}$,其中 $\mathcal{N_i}$ 表示节点i的一阶邻域节点。

我们上面结论说了,拉普拉斯算子就是在所有自由度上进行微小变化后获得的增益。但是对于Graph,从节点$i$变化到节点$j$增益是多少呢?即 $f_j - f_i$ 是多少呢?最容易想到就是和他们之间的边权相关,设为 $W_{ij}$。

所以,对于Graph来说,其拉普拉斯算子如下:

$$(\Delta f)i = \sum\limits_i \frac{\delta^2 f}{\delta i^2} \approx \sum\limits{j \in \mathcal{N_i}}W_{ij}(f_j - f_i) = \sum\limits_jW_{ij}(f_j - f_i)$$

继续可以简化为

$$\sum\limits_jW_{ij}(f_j - f_i) = \sum\limits_j W_{ij}f_j - \sum\limits_j W_{ij}f_i = (Wf)_i - (Df)_i = [(W-D)f]_i$$

其中,若$W_{ij}$都为1(simple graph),$\sum\limits_j W_{ij}f_i$可以看作在$i$节点的度($D_i$)。即:$(\Delta f_i) = [(W-D)f]_i$

因此,图上的拉普拉斯算子应该定义为$D-W$!

#拉普拉斯的谱分解

由于拉普拉斯矩阵是半正定对称矩阵,有如下三个性质:

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

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

$$L = U \begin{pmatrix}\lambda_1 & & \ & ...& \ & & \lambda_n\end{pmatrix} U^{-1}$$

由于$U$是列向量为单位特征的矩阵,因此:$UU^T = E$

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

$$L = U \begin{pmatrix}\lambda_1 & & \ & ...& \ & & \lambda_n\end{pmatrix} U^{T}$$

#Fourier transform on Graph

#图上的傅立叶变换

传统的傅立叶变换(参考这里):

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

Fourier transform is the expansion of $f$ in terms of the eigenfunctions of the Laplace operator, i.e, the second derivative

其实就是信号 $f(t)$与基函数 $e^{-i\omega t}$的积分,那么为什么要找$e^{-i\omega t}$作为基函数呢?

  • 广义的特征方程定义为:$AV = \lambda V$,其中$A$是一种变换
  • 可以证明:$\Delta e^{-iwt} = \frac{\partial ^2}{\partial t^2} = -w^2 e^{-iwt}$
  • $e^{-i\omega t}$ 是拉普拉斯算子的特征函数(满足特征方程), $\omega$ 和特征值密切相关。

仿照以上定义Graph上的傅立叶变换:

$$F(\lambda_l) = \hat{f} (\lambda_l)= \sum\limits_{i=1}^N f(i) u^T_l(i)$$

$f$ 是Graph上的 $N$ 维向量, $f(i)$ 与Graph的顶点一一对应, $u_l(i)$表示第 $l$ 个特征向量的第 $i$ 个分量。那么特征值(频率) $\lambda_l$ 下的, $f$ 的Graph 傅里叶变换就是与 $\lambda_l$ 对应的特征向量 $u_l$ 进行内积运算。

利用矩阵乘法将Graph上的傅里叶变换推广到矩阵形式:

$$\left(\begin{matrix} \hat{f}(\lambda_1)\ \hat{f}(\lambda_2) \ \vdots \ \hat{f}(\lambda_N) \end{matrix}\right)=\left(\begin{matrix}\ u_1(1) &u_1(2)& \dots &u_1(N) \ u_2(1) &u_2(2)& \dots &u_2(N)\ \vdots &\vdots &\ddots & \vdots\ u_N(1) &u_N(2)& \dots &u_N(N) \end{matrix}\right)\left(\begin{matrix}f(1)\ f(2) \ \vdots \f(N) \end{matrix}\right)$$

即 $f$ 在Graph上傅里叶变换的矩阵形式为: $\hat{f}=U^Tf $

#图上的傅立叶逆变换

类似地,传统的傅里叶变换是对频率 $\omega$ 求积分:

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

迁移到Graph上变为对特征值 $\lambda_l$ 求和:

$$f(i)=\sum_{l=1}^{N}{\hat{f}(\lambda_l) u_l(i)}$$

利用矩阵乘法将Graph上的傅里叶逆变换推广到矩阵形式:

$$ \left(\begin{matrix}f(1)\ f(2) \ \vdots \ f(N) \end{matrix}\right)= \left(\begin{matrix}\ u_1(1) &u_2(1)& \dots &u_N(1) \ u_1(2) &u_2(2)& \dots &u_N(2)\ \vdots &\vdots &\ddots & \vdots\ u_1(N) &u_2(N)& \dots &u_N(N) \end{matrix}\right) \left(\begin{matrix} \hat{f}(\lambda_1)\ \hat{f}(\lambda_2) \ \vdots \ \hat{f}(\lambda_N) \end{matrix}\right)$$

即 $f$ 在Graph上傅里叶逆变换的矩阵形式为: $f=U\hat{f}$

#推广卷积

#卷积定理

  • 函数卷积的傅里叶变换是函数傅立叶变换的乘积,即对于函数 $f(t)$ 与 $h(t)$ 两者的卷积是其函数傅立叶变换乘积的逆变换:

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

  • 其中$\mathcal{F}$是傅立叶变换。那么,我们如何在图上定义卷积呢?答案是用图上拉普拉斯算子的特征方程的形式定义图上的傅立叶变换。

#图上的卷积

  • $f$ 的傅里叶变换为 $\hat{f}=U^Tf$

  • 卷积核 $h$ 的傅里叶变换写成对角矩阵的形式即为:

$$ \left(\begin{matrix}\hat h(\lambda_1) & \&\ddots \ &&\hat h(\lambda_n) \end{matrix}\right)$$

  • $\hat{h}(\lambda_l)=\sum_{i=1}^{N}{h(i) u_l^T(i)}$ 是**根据需要设计的卷积核** $h$ 在Graph上的傅里叶变换

  • 两者的傅立叶变换乘积即为:

$$\left(\begin{matrix}\hat h(\lambda_1) & \&\ddots \ &&\hat h(\lambda_n) \end{matrix}\right) U^Tf $$

  • 再乘以 $U$ 求两者傅立叶变换乘积的逆变换,则求出卷积:

$$(f*h)_G= U\left(\begin{matrix}\hat h(\lambda_1) & \&\ddots \ &&\hat h(\lambda_n) \end{matrix}\right) U^Tf $$

  • 很多论文中卷积公式表示为:$(f*h)_G=U((U^Th)\odot(U^Tf))$,其实是完全相同的

#Reference

  1. 如何理解卷积
  2. 图拉普拉斯算子为何定义为D-W
  3. 深入理解傅里叶变换
  4. 图卷积网络(GCN)新手村完全指南
  5. 如何理解 Graph Convolutional Network(GCN)
Load Comments?