这篇文章将分类问题转化为图上的标签传播，并借助localized spectral filter 以及其一阶近似来简化计算。

Model

图上的spectral convolutions 被定义为输入$x\in \mathbb{R}^N$与filter $g_\theta = diag(\theta)$在Fourier domain的乘积

$g_\theta \star x = Ug_\theta U^\top x$

其中$U$为图的normalized 拉普拉斯矩阵$L$的特征向量，$L=I_N - D^{-\frac12}AD^{-\frac12} = U\Lambda U^\top$. $U^\top x$即为$x$在图上的傅里叶变换。$g_\theta$可以取为$\Lambda$的函数，$g_\theta(\Lambda)$. 由于计算矩阵特征分解复杂度非常高，作者借助切比雪夫多项式进行近似。

$g_{\theta'}(\Lambda)\approx \sum_{k=0}^K\theta_k'T_k(\tilde{\Lambda})$

其中$\tilde{\Lambda} = \frac{2}{\lambda_{max}}\Lambda - I_N$，$\theta_k’\in \mathbb{R}^K$，为切比雪夫多项式的系数。切比雪夫多项式定义为$T_k(x) = 2xT_{k-1}(x)-T_{k-2}(x), T_0(x) = 1, T_1(x)= x$.

考虑到$(U\Lambda U^\top)^k = U\Lambda^kU^\top$, 有

$g_{\theta'}\star x \approx\sum_{k=0}^K\theta_k'T_k(\tilde{L})x$

其中$\tilde{L} = \frac2{\lambda_{max}}L - I_N$.

这就是原式的K阶近似，只考虑到了每个结点的K阶邻点。本文令$K=1$.

同时，作者将$\lambda_{max}\approx 2$，这个近似是因为作者认为网络可以通过学到的scale适应这个变化。这样就得到了下面的式子

$g_{\theta'}\star x \approx\theta_0'x+\theta_1'(L-I_N)x = \theta_0'x-\theta_1'D^{-\frac12}AD^{-\frac12}x$

更进一步令$\theta = \theta_0’ = -\theta_1’$，有

$g_{\theta'}\star x \approx\theta(I_N+D^{-\frac12}AD^{-\frac12})x$

注意到$I_N+D^{-\frac12}AD^{-\frac12}$的特征值在$[0,2]$内，对于深度网络来说可能会发生梯度消失/爆炸的情况。作者介绍了一个trick，来避免这种情况的发生

$I_N+D^{-\frac12}AD^{-\frac12}\rightarrow \tilde{D}^{-\frac12}\tilde{A}\tilde{D}^{-\frac12}$

其中$\tilde{A}=A+I_N, \tilde{D}_{ii} = \sum_j\tilde{A}_{ij}$.

因此通过下式就可以将C个通道的输入$X\in\mathbb{R}^{N\times C}$转化为F维的输出

$Z=\tilde{D}^{-\frac12}\tilde{A}\tilde{D}^{-\frac12}X\Theta$

其中$\Theta\in\mathbb{R}^{C\times F}, Z\in\mathbb{R}^{N\times F}$.