ChebNetII

ChebNet1以及GCN的区别

谱相关详见:https://blog.csdn.net/chairuilin/article/details/140108216?spm=1001.2014.3001.5501
将图变到谱域
$$\hat{X}=U^{T}X$$
将谱域转换为原区域:
$$X=U\hat{X}$$
由
$$x\ast y=U((U^{T}x)\odot (U^{T}y))$$
可得:
$$g\ast x=U((U^{T}g)\odot (U^{T}x))$$
由于$$L=U\Lambda U^T$$
我们得到:
$$U^{T}L=\Lambda U^T$$
也就是卷积核对$U^T$进行图域到谱域的转换,g是一个可以学习的参数.我们就可以得到:
$$U^{T}g=g_{\theta }(\Lambda )$$
假如用切比雪夫多项式提供一个多项式逼近
$$g_{\theta }(\Lambda )=\sum _{k=0}^K{\theta }_k\cdot T_k(\Lambda )$$
$$\begin{array}{rl}& g\ast x=U((U^{T}g)\ast (U^{T}x))\\ 3& =U(g_{\theta }(\Lambda )\ast (U^{T}x))\\ & =U(\sum _{k=0}^K{\theta }_k\cdot T_k(\Lambda )\ast U^{T}x)\\ & =\sum _{k=0}^K{\theta }_k\cdot T_k(U\Lambda U^T)x\end{array}$$
$$g\ast x=\sum _{k=0}^K{\theta }_k\cdot T_k(L)x$$
由于切比雪夫多项式为:
$${\bar{x}}_0=x,{\bar{x}}_1=Lx,{\bar{x}}_k=2L{\bar{x}}_{k-1}-{\bar{x}}_{k-2}$$
我们令:k=1,那么,有:
$$g\ast x={\theta }_{0}x+{\theta }_{1}Lx$$
再令:${\theta }_0=1,{\theta }_1=-1$,那么,就有:
$g\ast x=I-L=D^{-1/2}A{D}^{-1/2}$
$$\text{令 }{I}_N+D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}\to {\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}},\tilde{A}=A+I_N$$
最终,就可以得到GCN的推到:
$$Z={\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}X\Theta$$

我们可以定义多项式滤波器为:
$$\mathbf{y}=\mathbf{U}diag\left[h({\lambda }_1),...,h({\lambda }_n)\right]{\mathbf{U}}^T\mathbf{x}=\mathbf{U}h\left(\mathbf{\Lambda }\right){\mathbf{U}}^T\mathbf{x}\approx \sum _{k=0}^K{w}_k{\mathbf{L}}^k\mathbf{x},$$
其中,h对应光谱滤波器,$$h(\lambda )=\sum _{k=0}^K{w}_k{\lambda }^k,\lambda \in [0,2]$$
ChebNet使用切比雪夫多项式去近似过滤器操作:
$$\mathbf{y}\approx \sum _{k=0}^K{w}_k{T}_k(\hat{\mathbf{L}})\mathbf{x}$$

在这里,$$\hat{\mathbf{L}}=2\mathbf{L}/{\lambda }_{max}-\mathbf{I}$$
表示拉普拉斯矩阵${\lambda }_{max}$是L的最大特征值,$w_k$表示切比雪夫系数.切比雪夫多项式可以被定义为:
$$T_k(x)=2x{T}_{k-1}(x)-{\dot{T}}_{k-2}(x)$$
$$T_0(x)=1$$
$$T_1(\bar{x})=x.$$

审视ChebNet的动机

具体流程:ChebBase->发现ChebBase/k效果更好(比chebbase等更好),因此分析,得到理论2.1(即要对系数$w_k$限制->利用切比雪夫差值限制$w_k$,并提出了$w_k=\frac{2}{K+1}{\sum }_{j=0}^K{\gamma }_j{T}_k(x_j)$,其中,${\lambda }_j$可以被定义Chebyshev node $x_j$

切比雪夫基与其他基的区别:
$$h(\hat{\lambda })\approx \sum _{k=0}^K{w}_k{T}_k(\hat{\lambda }),\hat{\lambda }\in [-1,1],$$
其中,$\hat{\lambda }$是拉普拉斯矩阵$\hat{L}$的特征值.
最近的工作有利用多项式和Bearbstein base去逼近过滤器
为了去逼近切比雪夫基的近似能力,我们用切比雪夫基简单替代了GPRGNN和BERNNET.
切比雪夫的表达为:
$$\mathbf{Y}=\sum _{k=0}^K{w}_k{T}_k(\hat{\mathbf{L}})f_{\theta }\left(\mathbf{X}\right)$$
其中,$f_{\theta }$表示为MLP
很显然,chebnet获得了最差的性能.
我们认为是切比雪夫基学习到了非法系数导致的.
定义一个在$[-1,1]$之间的连续函数f,切比雪夫扩展被定义为:$$\begin{array}{r}f(x)=\sum _{k=0}^{\infty }{w}_k{T}_k(x)\end{array}$$
其中,$w_k$被定义为切比雪夫系数.由于如上的经验,因此切比雪夫系数必须被限制
定理2.1:
如果f(x)在边界弱奇异且在$(-1,1)$内可解析,切比雪夫系数将会逐渐减少($k\to \infty$)至$\frac{1}{k^q}$,q是正常数.弱奇异指的是f的求导可能在边界处消失.
逼近解析函数的能力对于逼近光谱过滤器的任务至关重要,因为非解析过滤器器很难多项式逼近,并有可能导致过度逼近.而chebnet和chebbase的系数$w_k$没有任何限制,只是通过梯度下井求得,这不满足如上定理2.1,会导致弱的性能.利用定理2.1,我们创造了ChebBase/k
$$\mathbf{Y}=\sum _{k=0}^K\frac{w_k}{k}{T}_k(\hat{\mathbf{L}})f_{\theta }(\mathbf{X})\text{\hspace{1em}(6)}$$
经过实验,我们发现ChebBase/k效果最好.受此驱动,我们提出了ChebNetII

Chebnet II

尽管$Chebnet/k$似乎得到了应有的性能,它仍然有很多的缺点:
1.对系数施加惩罚在数学上并不美观
2.很难对学到的光谱过滤器进行进一步的限制.例如,目前我们不知道如何去修改公式6来去获得一个非负的过滤器
为此,我们引入了切比雪夫差值:

切比雪夫差值:

考虑到一个现实中的过滤函数$h(\hat{\lambda })$在$[-1,1]$内连续,当这个过滤器在有限个点${\lambda }_k$上已知,我们可以用如下多项式近似:
$$h({\hat{\lambda }}_k)=P_K({\hat{\lambda }}_k)$$
我们生成K+1个采样点${\hat{\lambda }}_0<{\hat{\lambda }}_1<...<{\hat{\lambda }}_K$在$[-1,1]$中,取构造$P_K(\hat{\lambda })$.直观来说,提升K可以提高逼近的质量.然而,由于龙格现象,前者不经常成立.解决之的一个方法就是切比雪夫差值,它有优越的近似能力和更快的收敛速度.切比雪夫差值用切比雪夫节点作为差值点,这些点的本质是第k+1个切比雪夫方程的零点.

定义3.1切比雪夫点

切比雪夫多项式$T_k(x)$满足近似表达:$T_k(x)=\cos \left(k\arccos (x)\right).$切比雪夫点$T_k(x)$被定义为:$x_j=\cos \left(\frac{2j+1}{k}\pi \right),j=0,1,\dots ,k-1$他们位于区间(-1,1)内,是$T_k(x)$的零点.
定理3.1表明切比雪夫多项式有k个零点.

定理3.2切比雪夫差值

给定一个连续的过滤函数$h(\hat{\lambda })$,$x_j=\cos \left(\frac{2j+1}{k}\pi \right),j=0,1,\dots ,k$表示切比雪夫点,$h(x_j)$表示节点$x_j$,切比雪夫差值$h(\hat{\lambda })$可以被定义为:
$$P_K(\hat{\lambda })=\sum _{k=0}^K{c}_k^{\prime }{T}_k(\hat{\lambda }),c_k=\frac{2}{K+1}\sum _{j=0}^{K}h(x_j)T_k(x_j),$$
其中,$c_0^{\prime }=c_0/2,c_1^{\prime }=c_1,\dots ,c_K^{\prime }=c_K.$.

受到切比雪夫差值激励,它以最佳的收敛率逼近任意频谱的滤波器$h(\hat{\lambda })$,ChebNetII重新参数过滤器$h(x_j)$,具体的是,ChebNetII 模型可以被定义为:
$$\mathbf{Y}=\frac{2}{K+1}\sum _{k=0}^K\sum _{j=0}^K{\gamma }_j{T}_k(x_j)T_k(\hat{\mathbf{L}})f_{\theta }(\mathbf{X}),$$
在这里,$\begin{array}{r}{x}_j=cos\left(\left(j+1/2\right)\pi /(K+1)\right)\end{array}$是$T_{K+1}$切比雪夫节点.$f_{\theta }$表示在节点x上的MLP,${\gamma }_j\text{ for }j=0,1,...,K$是可学习的参数.

ChebNetII --基于切比雪夫差值

具体的是,ChebNetII
$$\mathbf{y}\approx \frac{2}{K+1}\sum _{k=0}^K\sum _{j=0}^K{\gamma }_j{T}_k(x_j)T_k(\hat{\mathbf{L}})\mathbf{x}.$$
很容易看到,与原始的ChebNet相比,我们仅仅参数化系数$w_k$通过
$$w_k=\frac{2}{K+1}\sum _{j=0}^K{\gamma }_j{T}_k({\underline{x}}_j)$$
然而,这个小小的修改允许我们对最终过滤器的形状进行更多的控制,因为切比雪夫差值表明${\gamma }_j$直接对应过滤器值$h(x_i)$对于切比雪夫节点.相关系数$w_k=\frac{2}{K+1}{\sum }_{j=0}^{K}h(x_j)T_k(x_j)$从根本上满足定义2.1因为我们直接逼近过滤器$h$.此外,切比雪夫多项式也提供了几个好的数学性质.

杂乱

ChebNet的结构是:
$$\mathbf{Y}=\sum _{k=0}^K{T}_k(\hat{\mathbf{L}})\mathbf{X}{\mathbf{W}}_k$$
ChebnNet作者指出了原始的频谱图卷积有两大缺点:
1.图卷积核是全局的且参数量大 (卷积核大小与输入信号相同，参数量与图节点数相同)
2. 图卷积运算的复杂度高 (运算过程涉及高计算复杂度的特征分解)
为了克服卷积核过大的缺点,ChebNet指出可以使用多项式展开近似计算图卷积，即对参数化的频率响应函数进行多项式近似：
$$g_{\theta }(\Lambda )\approx \sum ^{k-1}{\theta }_k{\Lambda }^k$$
$$y=U{g}_{\theta }(\Lambda )U^{T}x=U(\sum _{k=0}^K{\theta }_k{\Lambda }^k)U^{T}x$$
但是,整个图卷积的复杂度还是ON2,为了降低复杂度,作者使用迭代定义的切比雪夫多项式做近似.
$$\begin{array}{rl}& \text{1.切比雪夫的递归定义}[\begin{array}{c}{T}_0(x)=1\\ T_1(x)=x\\ T_{n+1}(x)=2x{T}_n(x)-T_{n-1}(x)\end{array}\\ & \text{2.切比雪夫卷积核}\left[\begin{array}{c}{g}_{{\theta }^{\prime }}(\Lambda )\approx {\sum }_{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{\Lambda })\\ \tilde{\Lambda }=\frac{2}{{\lambda }_{\max }}\Lambda -I_N\end{array}\right]\\ & \text{3.切比雪夫图卷积}\left[\begin{array}{c}{g}_{{\theta }^{\prime }}\star x\approx {\sum }_{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{L})x\\ \\ \tilde{L}=\frac{2}{{\lambda }_{\max }}L-I_N\end{array}\right]\end{array}$$
$$\begin{array}{rl}y=g_{{\theta }^{\prime }}(L)x& =\sum _{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{L})x\\ & ={\theta }_0^{\prime }{T}_0(\tilde{L})x+{\theta }_1^{\prime }{T}_1(\tilde{L})x+{\theta }_2^{\prime }{T}_2(\tilde{L})x+\cdots +{\theta }_K^{\prime }{T}_K(\tilde{L})x\\ & ={\theta }_0^{\prime }{\bar{x}}_0+{\theta }_1^{\prime }{\bar{x}}_1+{\theta }_2^{\prime }{\bar{x}}_2+\cdots +{\theta }_K^{\prime }{\bar{x}}_K\\ & =[{\bar{x}}_0{\bar{x}}_1...{\bar{x}}_K][{\theta }_0^{\prime }{\theta }_1^{\prime }...{\theta }_K^{\prime }]\end{array}$$
$\begin{array}{l}\text{Calculating }{\bar{x}}_k=2\tilde{L}{\bar{x}}_{k-1}-{\bar{x}}_{k-2}\cot O(E)\\ \text{Total complexity: }O(KE)\end{array}$
ChebNet结论:
要学一个filter,filter需要学一族参数$\theta$,做filter的方式就是把信号用迭代的方式算到k次方,相乘得到filter完整的信号
受切比雪夫图卷积的启发，Thomas等人(GCN的作者)提出了一种更加简单的图卷积变种GCN。GCN相当于对一阶切比雪夫图卷积的再近似。在切比雪夫卷积核定义的基础上，我们令多项式的阶数K=1，再令矩阵L的大特征值为2(带来的缩放效应可以通过网络学习自动适应)，则图卷积运算过程可以按如下过程进一步简化：
$$\begin{array}{rl}& 令K=1,{\lambda }_{\max }\approx 2\\ & g_{{\theta }^{\prime }}\star x\approx {\theta }_0^{\prime }x+{\theta }_1^{\prime }\left(L-I_N\right)x\\ & ={\theta }_0^{\prime }x-{\theta }_1^{\prime }{D}^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}x\\ & \text{令}\theta ={\theta }_0^{\prime }=-{\theta }_1^{\prime }\\ & g_{\theta }\star x\approx \theta \left(I_N+D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}\right)x\\ & \text{令}{I}_N+D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}\to {\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}},\tilde{A}=A+I_N\\ & \text{并将图信号}x{\text{推广到多维数据R}}^{n\times c},\text{ 可得}\\ & Z={\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}X\Theta \end{array}$$ GCN的卷积核更小，参数量也更少，计算复杂度也随之减小，可以说是将简化进行到了极致，它等价于最简的一阶切比雪夫卷积