基于频谱的GCN的数学原理

参考链接：
如何理解GCN？知乎回答：从热传导模型到GCN
从CNN到GCN的联系与区别——GCN从入门到精（fang）通（qi）

GCN问题本质

图中的每个结点无时无刻不因为邻居和更远的点的影响，而在改变着自己的状态直到最终的平衡，关系越亲近的邻居影响越大。

GCN的实质

是在一张Graph Network中特征（Feature）和消息（Message）中的流动和传播！

研究GCN的原因

CNN无法处理非欧几里得结构数据，因为此种结构没有平移不变性，卷积核的大小无法固定不变。
拓扑图中包含许多重要的信息，可以通过图谱论进行挖掘。
拓扑连接是一种广义的数据结构，且一般来说任何数据在赋范空间内都可以建立拓扑关系。例如谱聚类（谱聚类原理总结）

进入到应用层面，具体来说。
GCN的目的提取拓扑图的空间特征。

核心理论： Sepectral graph theory 图谱论
图谱论简述

核心思想：

1. 借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质。
2. 借助于图谱的理论来实现拓扑图上的卷积操作。

为什么GCN要用拉普拉斯矩阵？
（1）拉普拉斯是对称矩阵，可以进行特征分解（谱分解），这和GCN的Spectral domain对应。
（2）拉普拉斯矩阵只在中心顶点和一阶相连的顶点上（1-hop neighbor）有非0元素，其余之处均为0.
（3）拉普拉斯算子和拉普拉斯矩阵之间的关系。

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

矩阵的谱分解，特征分解，对角化都是同一概念。特征分解
不是所有矩阵都可以特征分解，充要条件为n阶方阵存在n个线性无关的特征向量。线性无关与线性相关
拉普拉斯矩阵是半正定对称矩阵，有如下三个性质：
（1）对称矩阵一定有n个线性无关的特征向量
（2）半正定矩阵的特征值一定非负
（3）对称矩阵的特征向量相互正交，及所有的特征向量构成的矩阵为正交矩阵。正交矩阵

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

 

 

从传统的傅里叶变换、卷积类比到Graph上的傅里叶变换及卷积

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

Graph上的傅里叶变换
传统的傅里叶变换定义为：
F(ω)=F[f(t)]=∫f(t)e−iwtdt" role="presentation">F(ω)=F[f(t)]=∫f(t)e−iwtdt$F(\omega )=\mathcal{F}[f(t)]={\int }_{}^{}f(t)e^{-iwt}dt$

信号f ( t ) f(t)f(t)与基函数的积分，从数学上看，由于基函数
e−iwt" role="presentation">e−iwt$e^{-iwt}$是拉普拉斯算子的特征函数（满足特征方程），w就和特征值有关，所以使用此式作为基函数。

证明：

同理，在Graph问题中，用到拉普拉斯矩阵（拉普拉斯矩阵就是离散的拉普拉斯算子）时就自然去找拉普拉斯矩阵的特征向量。

 ps:

上述的内积运算是在复数空间中定义的，所以采用了ul∗(i)" role="presentation">u∗l(i)$u_l^{\ast }(i)$,也就是ul" role="presentation">ul$u_l$的共轭。

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

即f在Graph上傅里叶变换的矩阵形式为：

f^=UTf" role="presentation">f^=UTf$\hat{f}=U^{T}f$

(b)Graph上的傅里叶逆变换
类似地，传统的傅里叶逆变换是对频率w求积分：
F−1[F(ω)]=12∏∫F(ω)eiwtdω]" role="presentation">F−1[F(ω)]=12∏∫F(ω)eiwtdω]${\mathcal{F}}^{-1}[F(\omega )]=\frac{1}{2\prod }\int F(\omega )e^{iwt}d\omega ]$

迁移到Graph上变为对特征值λl求和：
f(i)=∑l=1Nf^(λl)ul(i)" role="presentation">f(i)=∑Nl=1f^(λl)ul(i)$f(i)=\sum _{l=1}^N\hat{f}({\lambda }_l)u_l(i)$

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

即f在Graph上傅里叶逆变换为

f^=UTf" role="presentation" style="position: relative;">f^=UTf$\hat{f}=U^{T}f$

推广卷积
在上面的基础上，利用卷积定理类比将卷积运算推广到Graph上。

 

 

参考资料：
傅里叶变换
机器学习中的GCN