万字长文带你入门 GCN( 八 )

可以看到这是一个和特征值密切相关的函数，我们不妨将写成拉普拉斯矩阵 L 的特征值函数：

本文插图
然后这个卷积核有两个局限性：

不具备局部连接性；
时间复杂度为。

为了克服这个缺点，我们引入 K 阶多项式：
其中，参数是多项式系数，这样滤波器就具有了 K 阶局部性了，复杂度也降低到。
我们将这个公式带入卷积运算中：

本文插图
此时，我们计算图卷积运算就不需要再乘上特征向量矩阵，而是直接使用拉普拉斯矩阵 L 的 k 次方，这样就避免了进行特征分解。而我们可以事先计算好，这样就只需要计算矩阵相乘。同时由于 L 为稀疏矩阵，所以时间复杂度为，为节点边数。
此外，作者还引入了切比雪夫展开式来近似。
设为切比雪夫多项式的第 k 阶式子，切比雪夫多项式的递归式为：。所以我们有：

本文插图
其中，；是指拉普拉斯矩阵 L 的最大值。
这是因为切比雪夫多项式的输入要在之间，由于拉普拉斯矩阵的半正定性，所以所有的特征值都是大于等于 0 的，将其除以最大特征值可以将特征压缩到区间内，现在需要将其压缩到，所以我们有：
我们将切比雪夫多项式引入到我们的卷积变换中：

本文插图
其中，。这个表达式为拉普拉斯多项式中的一个 k 阶近似函数，依赖于节点的「k 阶邻域」（走 k 步能到的邻居），时间复杂度与边呈线形相关。
3.5 GCN-3
第二代 GCN 解决了图卷机要求特征分解的问题，但是在计算图卷积操作时，依然每次都要进行矩阵乘法，时间复杂度为，于是学者继续优化。
我们把上式拿下来：

本文插图
GCN 通过上式的多层卷积层进行叠加，而每层都会逐点进行非线性叠加，考虑到时间复杂度问题，学者直接取 K=2 ，也就是说得到了一个拉普拉斯算子的二阶近似函数。这样我们既可以对网络进行卷积操作，又不会引入太多的切比雪夫系数。而且这样的线形运算允许我们构建更深的网路，提高模型的建模能力。
我们知道归一化的拉普拉斯矩阵的特征值区间为 [0, 2] ，进一步近似，所以我们有新的表达式：