图卷积

2020-08-12  本文已影响0人  学术界末流打工人

图卷积简介

经典的卷积网络的局限：无法处理图结构数据

经典卷积网络与图卷积网络处理不同数据图

经典卷积处理图结构数据的局限性

  1. 只能处理固定输入维度的数据
  2. 局部输入数据必须有序

  3. 语音，图像，视频（规则结构）满足以上两点要求。但并不适用于图结构数据(非欧几里得空间数据)


    欧几里得与非欧几里得数据图

部分较为经典模型

经典模型时间图

图卷积的背景知识

什么是卷积？

根据卷积定理，两信号在空域(或者时域)的频域中的傅里叶变换的乘积，即：
F[f_1(t)*F_2(t)] = F_1(w) · F_2(w)
其中f(t)为空域上的信号,F_1(w)为频域上的信号。F_1(w)为频域上的信号。F为傅里叶变换，*表示卷积，·为乘积。

关于卷积更详细的讲解：
如何通俗易懂地解释卷积？

也可以写成：f_1(t)*f_2(t)=F^{-1}[F_1(w)·F_2(w)]
其中：

傅里叶变换

傅里叶变换公式: F(w)=F[f(t)]=\int^{\infty}_{-\infty}{f(t)e^{-iwt}dt}

拉普拉斯矩阵(Laplacian Matrix)

符号设置：

拉普拉斯矩阵的定义：度矩阵减邻接矩阵


上图中：

拉普拉斯矩阵是对称半正定矩阵：
证明如下：对于任意向量f=[f_1,f_2,...,f_n]^T有
f^tLf=f^TDf-f^TWf \\=\sum^n_{i=1}d_if^2_i-\sum^n_{i,j=1}f_if_jW_{ij} \\ =\frac 1 2(\sum^n_{i=1}d_if^2_i-2\sum^n_{i,j=1)}f_if_jW_{ij}+\sum^n_{j=1}d_jf^2_j) \\ =\frac 1 2(\sum^n_{i,j=1})W_{ij}(f_i-f_j)^2)\geq 0

拉普拉斯矩阵特点：

正定矩阵(positive definite matrix)

定义：给定一个大小为n\times n的实对称矩阵A,若对于任意长度为n的非零向量x,有x^T Ax >0恒成立，则矩阵A是一个正定矩阵。

半正定矩阵(positive semi-definite matrix)

定义：给定一个大小为n\times n的实对称矩阵A,若对于任意长度为n的向量x,有x^TAx \geq 0恒成立，则矩阵A是一个半正定矩阵。

拉普拉斯矩阵的谱分解

特征分解（Eigen decomposition），又称谱分解（Spectral decomposition） 是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。
L = U\Lambda U^{-1} = U \left[ \begin{matrix} \lambda_1 \qquad \qquad \\ \ddots \\ \qquad \qquad \lambda_n \end{matrix} \right] \\ U=(\vec{u}_1,\vec{u}_2,...,\vec{u}_n) \\ \vec{u}_i \in \mathbb{R},i=1,2,...,n

特征值特征向量详细讲解

附录

其他资源

图论方向每年论文总结

References

  1. 图卷积神经网络
  2. 浅谈「正定矩阵」和「半正定矩阵」
上一篇 下一篇

猜你喜欢

热点阅读