1,168 次浏览

基于谱图的GCN

Graph

现在就来说说这个字母G,我们知道CNN对于图像处理是十分得心应手的,堪称是法宝,而CNN处理的图像是十分规则的,人们认为处理图像问题是在欧式空间上进行的,如果我们把图片的像素看做一个个独立的点相互连接,就可以看做是一个特殊的图结构。而GCN中的graph是指的抽象的图,就像离散数学中学的图结构以及数据结构中学的图结构。

graph是由点集合\(\)\(V\)\(\),边集合\(\)\(E\)\(\),以及两点相连边的权重集合\(\)\(W\)\(\)构成的集合,即\(\)\(G=(V, E, W)\)\(\)。对于图片而言,将像素点当做点集合,相邻像素连线形成边集合,边之间的权重都是平均分布,这样也可以将其看做一个图结构。

卷积

然后我们来抓住这个字母C(convolution)。

简而言之,先从傅里叶变换先开始,傅里叶变换是将一个周期函数表示成有一组正交函数基的线性组合,也即我们将原函数投影到的以得到的正交函数基构成的空间中。这组函数基由正弦函数与余弦函数来表示,写成负指数形式:
F.T: \(\)\(\hat{f}(s) = \lmoustache ^{\infty}_{-\infty} g(t)e^{-2\pi i s t} dt\)\(\)
I.F.T: \(\)\(g(t)=\lmoustache ^{\infty}_{-\infty} \hat{f}(s)e^{2\pi i s t} ds\)\(\)

对于两个傅里叶变换之后相加,由积分相加的性质很快可以得到:
\(\)\(\mathcal{F}f(s)+\mathcal{F}g(s)=(\mathcal{F}(f+g))(s)\)\(\)
即:\(\)\(\mathcal{F}f + \mathcal{F}g = \mathcal{F}(f+g)\)\(\)

那么对于两个傅里叶变换之后的乘法呢?
\(\)\((\mathcal{F}f)(\mathcal{F}g)=\lmoustache ^{\infty}_{-\infty}e^{-2\pi i s t_1}f(t_1)dt_1 \lmoustache ^{\infty}_{-\infty}e^{-2\pi i s t_2}g(t_2)dt_2\)\(\)
\(\)\(=\lmoustache ^{\infty}_{-\infty}(\lmoustache ^{\infty}_{-\infty}e^{-2\pi i s (t_1+t_2)}f(t_1)dt_1)g(t_2)dt_2\)\(\)
令\(\)\(u=t_1+t_2\)\(\)
\(\)\((\mathcal{F}f)(\mathcal{F}g)=\lmoustache ^{\infty}_{-\infty}(\lmoustache ^{\infty}_{-\infty}e^{-2\pi i s u}f(t_1)dt_1)g(u-t_1)d(u-t_1)\)\(\)
\(\)\(=\lmoustache ^{\infty}_{-\infty}(\lmoustache ^{\infty}_{-\infty}g(u-t_1)f(t_1)dt_1)e^{-2\pi i s u}du\)\(\)
令\(\)\(h(u)=\lmoustache ^{\infty}_{-\infty}g(u-t_1)f(t_1)dt_1\)\(\),得到下式:
\(\)\((\mathcal{F}f)(\mathcal{F}g)=\lmoustache ^{\infty}_{-\infty} h(u)e^{-2\pi i s u}du=(\mathcal{F}h)(s)\)\(\)
所以我们得到了卷积
\(\)\((g\ast f)(t)=\lmoustache ^{\infty}_{-\infty}g(\tau-t)f(t)dt\)\(\)
由上述推导可得到:
\(\)\((\mathcal{F}f)(\mathcal{F}g)=\mathcal{F}(g \ast f)\)\(\)

Graph Convolution

前面分别了解字母G与字母C,那么GC如何成为整体呢?

首先我们从字母C可以看到,这个连接的桥梁是Fourier transform。但是我们无法在Graph上直接使用FT的。傅里叶变换的本质就是将原函数分解成由正交基函数(这组函数基就是负指数函数)组成的线性组合,按线代理解则是将函数投影到新的由这一组正交基函数的空间中。对应于这个概念,我们就要提到operator与eigenfunction(特征函数)这两个概念了。

在线代中对于一个向量在矩阵的作用下,依旧等于这个向量或向量的缩放,我们称这个向量是特征向量,前人们发现有些函数在一些计算下依旧会保持不变或者缩放,这种函数就叫做eigenfunction,例如,\(\)\(e^x\)\(\)这个钉子户函数,在一阶求导算子的计算下,\(\)\(\frac{d}{dx}e^x = e^x\)\(\),\(\)\(e^x\)\(\)就是一阶求导算子的特征函数,在进行二阶求导,你就会发现这个函数还是钉在原地。你再看看它在傅里叶变换中的表现,\(\)\(e^{-2\pi i s t}\)\(\)具有正交性,而且和\(\)\(e^x\)\(\)一样是可以成为特征函数的,只是比\(\)\(e^x\)\(\)多了缩放因子。

对于\(\)\(e^{-2\pi i s t}\)\(\)来说,他是一维拉普拉斯算子\(\)\(\frac{d^2}{dx^2}\)\(\)的特征函数,拉普拉斯算子的定义是函数梯度的散度,也即:\(\)\(\bigtriangleup = \sum _i \frac{\partial^2}{\partial x_i ^2}\)\(\)

离散化拉普拉斯算子:
\(\)\(\frac{\partial^2 f(x)}{\partial x ^2}=f^{\prime \prime}(x) \approx f^\prime (x) – f ^\prime(x-1) \\\approx f(x+1)-f(x)-f(x)+f(x-1) \\= f(x+1) +f(x-1) -2f(x)\)\(\)

二维情况下:
\(\)\(\bigtriangleup=\frac{\partial^2 f(x, y)}{\partial x ^2}+ \frac{\partial^2 f(x, y)}{\partial y ^2} \\ \approx f(x+1, y) +f(x-1, y)+f(x, y+1)+f(x, y-1)-4f(x, y)\)\(\)

可以从上式看到,拉普拉斯算子表示的是当前点与周围相连点之间的差值,导数的分母为\(\)\(\Delta x = (x+1) – x\)\(\)。但是对于图来说,我们不能单纯的使用\(\)\(\Delta x = (x+1) – x\)\(\),我们需要考虑到两个相连接点之间的距离,即,\(\)\((f_i -f_j)/\delta_{ij}=>w_{ij}(f_i-f_j)\)\(\),所以得到下式:
\(\)\(\bigtriangleup = \sum_i \frac{\partial^2f}{\partial i^2} \approx \sum_{j \in N_i}w_{ij}(f_i -f_j)\)\(\)
\(\)\(\sum_{j \in N_i}w_{ij}(f_i -f_j) = \sum_j w_{ij}f_i -\sum_j w_{ij}f_j=[(D-W)f]_i\)\(\)
\(\)\(\bigtriangleup f = (D-W)f = Lf\)\(\),这便是我们的拉普拉斯矩阵。

由上述我们知道拉普拉斯矩阵就是图上的拉普拉斯算子。拉普拉斯矩阵,是一个半正定矩阵,有完整的正交向量基。所以仿照傅里叶变换,就可以使用拉普拉斯矩阵来得到图傅里叶变换,原来的负指数则有拉普拉斯矩阵的的特征向量替代,得到变换后的图域为关于特征值的函数:
\(\)\(\hat{f}(\lambda _l)= <f, u_l>=\sum^N _{l}f(i)u^*_l(i) \)\(\)
图傅里叶逆变换:
\(\)\(f(i) = \sum^N _{l}\hat{f}(\lambda _l)u_{l}(i)\)\(\)
矩阵形式:
\(\)\(\hat{f} =U^Tf\)\(\)
\(\)\(f = U\hat{f}\)\(\)

有了图傅里叶变换,那么图卷积呢?

根据前文讲的卷积,进行推广:
\(\)\((f \ast g)_G = U((U^T g)\odot (U^Tf))\)\(\)
\(\)\(\odot\)\(\)为哈达玛积。

至此GCN的G与C的理论就结束了。

reference
1. Shuman D I, Narang S K, Frossard P, et al. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE signal processing magazine, 2013, 30(3): 83-98.
2. Hammond D K, Vandergheynst P, Gribonval R. Wavelets on graphs via spectral graph theory[J]. Applied and Computational Harmonic Analysis, 2011, 30(2): 129-150.