手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

天天新资讯：图卷积的演变-从谱图卷积到GCN

2023-02-03 06:02:43 来源：博客园

基础

傅里叶级数是对周期为T的确定性信号做展开，而傅里叶变换将周期推广到无穷，能对具有任意长度的信号做展开。

(资料图)

https://www.zhihu.com/question/21665935/answer/2367861632

\[\hat{f}(t)={\int}f(x){\exp}^{-iwt}dx = {\int}f(x) \left(cos(wx) + isin(wx) \right)dx\]

要在图上做图傅里叶变化关键, 是找到图信号的基函数。

拉普拉斯算子(Laplacian operator) 的物理意义是空间二阶导数，其准确定义是：标量梯度场中的散度，可用于描述物理量的流入流出，例如热传播。

图拉普拉斯矩阵L是拉普拉斯算子的在图（离散空间）上的的推广。

广义特征方程：传统傅里叶的基函数可视为拉普拉斯算子（梯度的散度，二阶偏导之和）的特征向量，频率为特征值：

\[∆{e}^{-iwt}=\frac{{\partial}^2}{{\partial}t^2}{e}^{-iwt}={-w^2}{e}^{-iwt}\]

那么，很自然的可++把拉普拉斯L的特征向量作为图傅里叶变换的基函数++。

\[\mathbf{L} = \mathbf{D} - \mathbf{A} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{T}, 拉普拉斯矩阵特征分解\]\[\mathbf{U} = (\mathbf{u}_1, \mathbf{u}_2, {\cdots}, \mathbf{u}_n)， \mathbf{U}^{-1} =\mathbf{U}^T, \mathbf{U} \mathbf{U}^T = \mathbf{I}\]\[ \phi_l = \mathbf{u}_l^{T} \mathbf{f},基向量上的分量\]

图上的任意一个信号(n维)都可表示为拉普拉斯矩阵特征向量（基向量）的线性组合。

\[ 图傅里叶变换， \mathbf{\Phi} = \left[ \begin{matrix} \phi_1 \\ ... \\ \phi_N \end{matrix} \right]=\mathbf{U}^T \mathbf{f}\]\[图傅里叶逆变换， \mathbf{f} ={\sum}_{l} \phi_l \mathbf{u}_l = \mathbf{U} \mathbf{\phi}\]

图傅里叶变换，在这里就是将图信号f投影（内积计算分量）到L的特征向量构成的基向量上。就是将f从原始空间变到新的空间-谱（频）域。

\[ \mathbf{\Phi}=\mathbf{U}^T \mathbf{f}= \mathbf{U}^T (\mathbf{U} \mathbf{\Phi}), \mathbf{f} = \mathbf{U} \mathbf{\Phi} = \mathbf{U} (\mathbf{U}^T \mathbf{f})\]

第一代：Spectral Network

卷积定理：卷积的傅里叶变换等于傅里叶变换的乘积（时域卷积，等于在频域做乘积）

\[ F\{f*g\} = F[f] {\odot} F[g]]\]

通过傅里叶逆变换可以得到:

\[f*g = F^{-1}[F[f]{\odot}F[g]]\]

在图上做，图信号和滤波器g的卷积：

\[输入 \mathbf{x} \in \mathbb{R}^{N}，每一个节点有一个标量\]\[\mathbf{U} \in \mathbb{R}^{N \times N}, 拉普拉斯矩阵特征向量\]\[ 有滤波器向量 \mathbf{g} \in \mathbb{R}^{N}\]

那么，图上的卷积可以定义为：

\[\mathbf{x} \star \mathbf{g} = \mathbf{U} (\mathbf{U}^{T}\mathbf{x}) {\odot} (\mathbf{U}^{T}\mathbf{g}) = \mathbf{U} (\mathbf{U}^{T}\mathbf{x} {\odot} \mathbf{\theta} ) \]\[把 \mathbf{U}^{T}\mathbf{g}统一视为一个，\mathbf{\theta} \in \mathbb{R}^{N} (傅里叶变换后的滤波器 \mathbf{g}) \]

传统滤波器需根据经验设定，在这里可将滤波器视为：可参数化的卷积核

卷积运算中的乘法为element-wise product，即在频域的乘法。在这里，其直观意义就是：

\[(\mathbf{U}^{T}\mathbf{x}) {\odot} \mathbf{\theta}，\mathbf{\theta} {\odot} (\mathbf{U}^{T}\mathbf{x})，交换顺序不影响\]

用卷积核的参数对频域信号的每个分量进行加权操作，从而实现滤波（不同的频率分量有不同的权重系数）

那么将卷积核向量展开为对角矩阵形式（行变换），有：

\[\mathbf{g}_{\theta} = diag{(\mathbf{\theta}) } =\left[ \begin{matrix} {\theta}_1 & ... & 0 \\ ... & ... & ... \\ 0 & ... & {\theta}_N \end{matrix} \right]\]

最后，可得到：

\[\mathbf{x} \star \mathbf{g} = \mathbf{U} (\mathbf{U}^{T}\mathbf{x} {\odot} \mathbf{\theta} ) \\= \mathbf{U} (\mathbf{\theta} {\odot} \mathbf{U}^{T}\mathbf{x} ) \\ = \mathbf{U} \mathbf{g}_{\theta} \mathbf{U}^{T} \mathbf{x} \]

假设每个节点有d维的特征，即通道数为d（d个图信号）:

\[\mathbf{X} = \left[ \begin{matrix} {x_{11}} & {x_{12}} & ... & {x_{1d}} \\ ... & ... & ... \\ {x_{n1}} & {x_{n2}} & ... & {x_{nd}} \end{matrix} \right] = \left[ \begin{matrix} {\mathbf{x}_1} & {\mathbf{x}_2} & ... & {\mathbf{x}_d} \end{matrix} \right] \]

注意，\(\mathbf{X} \in \mathbb{R}^{N \times d}\), 每一个通道可使用多个卷积核（类似CNN，拓展通道数）。

对于第l层谱图卷积，通道数为d_l：

\[假设第 {l} 和{l+1}层的节点状态为： \mathbf{X}^{(l)} \in \mathbb{R}^{N \times d_l}， \mathbf{X}^{(l+1)} \in \mathbb{R}^{N \times d_{l+1}}\]\[\mathbf{X}^{(l)}_{:i} =\mathbf{x}^{(l)}_{i} \in \mathbb{R}^{N}\]

使用d_l * d_(l+1)个卷积核，每次在全部通道分别用d_l个卷积核并将结果求和，重复d_(l+1)次，得到输出特征通道：

\[\mathbf{x}^{l+1}_j={\sigma}(\mathbf{U} {\sum}_{i=1}^{d_l} \mathbf{\Theta}^l_{i,j} \mathbf{U}^T \mathbf{x}^l_i), (j = 1, \dots, d_{(l+1)})\]\[\mathbf{\Theta}^l_{i,j}直接视为模型参数， \mathbf{U} \mathbf{\Theta}^l_{i,j} \mathbf{U}^T对应CNN中的卷积核(复杂度 O(n^2))\]

Spectral Graph Convolution操作定义为：

计算图拉普拉斯(graph Laplacian)的特征值分解，得到特征向量
将图信号进行图傅里叶变换，然后使用卷积核进行滤波，然后再进行图傅里叶逆变换

缺点：

图拉普拉斯特征分解O(n^3)复杂度，前向传播O(n^2)。
卷积核参数量大： n * d_l * d_(l+1), 易过拟合(n 为节点数量)
在空域上没有明确定义，不能局部化到节点上

第二代：ChebNet

切比雪夫网络实现了：快速局部化和低复杂度

\[\mathbf{g} \star \mathbf{x} = \mathbf{x} \star \mathbf{g} = \mathbf{U} \mathbf{g}_{\theta} \mathbf{U}^{T} \mathbf{x}，谱图卷积\]

从图信号分析的角度考虑，希望这个过滤函数g能有较好的局部化（只影响节点的局部邻居点）。

\[故可把\mathbf{g}定义成\mathbf{L}的函数\mathbf{g}_{\theta}(\mathbf{L})，例如\mathbf{L}的多项式\]

因为作用一次拉普拉斯矩阵, 相当于在图上把信息扩散到1阶邻居。

图信号被这个滤波器过滤后 (++拉普拉斯矩阵乘法仅与特征值相关++)，得到：

\[\mathbf{y} = \mathbf{g}_{\theta} (\mathbf{L})\mathbf{x} = \mathbf{g}_{\theta} (\mathbf{U} \mathbf{\Lambda} \mathbf{U}^{T}) \mathbf{x} =\mathbf{U} \mathbf{g}_{\theta} (\mathbf{\Lambda}) \mathbf{U}^{T} \mathbf{x} \]\[\mathbf{\Lambda}，特征值构成的对角矩阵\]

也就是说，可把谱域图卷积中的卷积核, 看作拉普拉斯矩阵特征值的函数。通常，可选择使用一个多项式卷积核:

\[\mathbf{g}_{\theta}(\mathbf{\Lambda}) = \sum_{k=0}^{K} \mathbf{\theta_{k}} \mathbf{\Lambda}^{k}\]

其中，参数ek是多项式的系数。通过这个定义，我们现在只需要K+1个参数（K《n）这大大降低了参数学习过程的复杂度。就相当于:

\[\mathbf{g}_{\theta}(\mathbf{L}) = \sum_{k=0}^{K} \mathbf{\theta_{k}} \mathbf{L}^{k}\]

因此信息最多在每个节点传播K步，即即卷积的局部化。

ChebNet进一步提出了加速方案：

\[把 \mathbf{g}_{\theta}(\mathbf{\Lambda})近似为切比雪夫多项式的K阶阶段\]\[\mathbf{g}_{\theta}(\mathbf{\Lambda}) = \sum_{k=0}^{K} \theta_{k} T_{k}(\tilde{\mathbf{\Lambda}}) \]

其中，Tk是k阶切比雪夫多项式。

\[\tilde{\mathbf{\Lambda}} = 2 \mathbf{\Lambda}_n / \lambda_{max} - \mathbf{I}_n是一个对角阵 \\主要将特征值对角阵映射到[-1，1]区间\\\lambda_{max}是\mathbf{L} 最大的特征值，\theta_{k} \in \mathbb{R}^{K}为切比雪夫系数向量\]

之所以采用切比雪夫多项式，是因为考虑到它具有很好的性质，可以循环递归求解:

\[T_{k}(\mathbf{x})=2 \mathbf{x} T_{k-1}(\mathbf{x})-T_{k-2}(\mathbf{x})\]\[从初始值 T_{0}(\mathbf{x})=1, T_{1}(\mathbf{x})=\mathbf{x}开始,采用递归公式，可求得k阶T_k的值\]

为了避免特征值分解，将式（3.8）写回为L的函数:

\[\begin{aligned} \mathbf{y} =\boldsymbol{g} * \mathbf{x} & = \mathbf{U} \mathbf{g}_{\theta} (\mathbf{\Lambda}) \mathbf{U}^{T} \mathbf{x} \\ & = \mathbf{U} \left( \sum_{k=0}^{K} \theta_{k} T_{k}(\tilde{\mathbf{\Lambda}}) \right) \mathbf{U}^{T} \mathbf{x} \\ & = \sum_{k=0}^{K} \theta_{k} \left(\mathbf{U} T_{k}(\tilde{\mathbf{\Lambda}}) \mathbf{U}^{T}\right) x \\&=\sum_{k=0}^{K} \theta_{k} T_{k}(\tilde{\mathbf{L}}) \mathbf{x} \end{aligned}\]\[其中, \tilde{\mathbf{L}}=\frac{2}{\lambda_{\max }} \mathbf{L}-\mathbf{I}_{N}。这个式子是拉普拉斯矩阵的K次多项式。\]

因此，它仍然保几K-局部化(节点仅被其周围的K 阶邻居节点所影响）。

第三代：GCN

GCN限制了逐层的卷积操作，并将切比雪夫多项式的项数设为K=1来减缓过拟合的问题，

\[它还近似了\lambda_{\max } \approx 2，最后简化的方程如下\]\[ \mathbf{g}_{\theta^{\prime}} \star \mathbf{x} \approx \theta_{0}^{\prime} \mathbf{x}+\theta_{1}^{\prime}\left(\mathbf{L}-\mathbf{I}_{N}\right) \mathbf{x}=\theta_{0}^{\prime} \mathbf{x}-\theta_{1}^{\prime} \mathbf{D}^{-\frac{1}{2}} \mathbf{A} \mathbf{D}^{-\frac{1}{2}} \mathbf{x}\]

使用两个无限制的参数\(\theta"_0\)和\(\theta"_1\)。

在通过设置\(\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime}\)来限制参数的数量之后，我们可以得到一下的表达式

\[ \mathbf{y} =\boldsymbol{g} * \mathbf{x} = \mathbf{g}_{\theta} \star \mathbf{x} \approx \theta\left(\mathbf{I}_{N}+\mathbf{D}^{-\frac{1}{2}} \mathbf{A} \mathbf{D}^{-\frac{1}{2}}\right) \mathbf{x}\]

值得一提的是，叠加使用这个操作会导致数值不稳定性以及梯度爆炸或消失(因为不断地乘以同一个矩阵)，因此，该论文里面使用了重规整化操作(renormalization)：

\[ \mathbf{I}_{N}+\mathbf{D}^{-\frac{1}{2}} \mathbf{A} \mathbf{D}^{-\frac{1}{2}}\rightarrow{}\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}}\]

其中，

\[\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}_{N}，\tilde{\mathbf{D}}_{i i}=\sum_{j} \tilde{\mathbf{A}}_{i j}\]\[最后，论文将模型扩展为含有C个输入通道的信号，\mathbf{X} \in \mathbb{R}^{N \times C}以及F个滤波器来用于提取特征\]\[ \mathbf{Z}=\tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{X} \boldsymbol{\Theta}\]\[ 其中，\Theta \in \mathbb{R}^{C \times F}是滤波器参数矩阵，\mathbf{Z} \in\mathbb{R}^{N \times F}是卷积信号矩阵。\]

在所有这些频域方法中，学习得到的滤波器都是基于拉普拉斯特征分解，也就是取决于图的结构，这也就意味着，在一个特定结构上训练得到的模型，并不能直接应用到另外一个结构不同的图上。

关键词：拉普拉斯傅里叶变换特征向量