图卷积神经网络研讨会笔记

地址：https://www.bilibili.com/video/BV1zp4y117bB/?p=1

图卷积神经网络—中科院沈华伟老师

The power of CNN lies in : 优势是平移不变性（translation- or shift-invariant）：识别目标独有的特征，尽管其特征的空间位置发生变化。

卷积是什么：卷积（convolution）是在两个函数上的数学操作，$f$与$g$，生成第三个函数$h$。卷积更为本质的是对原始信号的处理，使得信号更平滑。

连续空间里卷积定义为积分：比如时间$t$上的函数，此处原始信号$f$，卷积核为$g$（局部的方波），生成新的函数$h$比原有信号更加平滑。

$$h(t) = (f * g)(t) =\int f(t)g(t -\tau)d\tau$$

离散空间里卷积定义为求和如下：

$$h(x,y) = (f * g) (x, y) =\sum_{m,n}f(x-m, y -n)g(m,n)$$

两类卷积方法：Spectral methods谱方法（空间方法的一类）和Spatial methods空间方法。

• 谱方法：卷积定义在谱域（spectral domain）；通过图傅立叶变换和卷积理论。最大的挑战是：convolution filter defined in sepcrtal domain is not localized in vertex domain.
  • 直接定义图上的卷积不满足平移不变性，因此谱方法是将图上的信号变换到谱域，通过谱域进行卷积，然后再变换到空间域上。
• 空间方法：卷积定义在点域（vertex domain）；卷积此时作为目标节点在局部的一个带权聚合函数(weighted average function)。最大的挑战是：the size of neighborhood varies remarkably across nodes, e.g.,幂律分布。（难点：参数共享问题）

先给出预先的定义：

这里值得看的是特征矩阵$\mathbf{X}$的每一列可以看作是定义在图上的一个信号。

拉普拉斯矩阵刻画了信号在图上的平滑程度。

• 图的傅里叶基（Fourier basis of graph） $\mathbf{G}$：设图拉普拉斯矩阵的正交基向量为${ul}{l=1}^n$，对应的非负特征值为${\lambdal }{l=1}^n$ 。图拉普拉斯矩阵可以对角化为:

$$L=𝑈\Lambda𝑈^T$$

​ 这里$U = [u_1, u_2, …, u_n ]$，$\Lambda = diag([\lambda_1,\dots,\lambda_n])$

• 图傅立叶变化（Graph Fourier transform）：信号$\mathbf{x}\in R^n$的图傅立叶变化定义如下：

  $$\mathbf{\hat x} = U^T\mathbf{x}$$

  图傅立叶逆变化（Graph Fourier inverse transform）：

  $$\mathbf{x} = U \mathbf{\hat x}$$

• 卷积理论（Convolution theorem）：The Fourier transform of a convolution of two signals is the point-wise product of their Fourier transforms：

$$\mathcal{F}(f * g) = \mathcal{F}(f) * \mathcal{F}(g)$$

根据卷积理论，给定一个信号$\mathbf{x}$作为输入，$\mathbf{y}$作为滤波（filter），图卷积$*_G$ 定义为：

$$\mathbf{x} *_G \mathbf{y} = U((U^T\mathbf{x})\bigodot(U^T\mathbf{y}))$$

此时谱域上的卷积滤波（convolution filter）为$U^Ty$。定义：

$$U^T \mathbf{y} = [\theta_1，\theta_2，\dots，\theta_n]$$ $$g_{\theta} = diag( [\theta_1，\theta_2，\dots，\theta_n])$$

我们有：

$$\mathbf{x} *_G \mathbf{y} = Ug_{\theta} U^T\mathbf{x}$$