图卷积网络入门(GCN) (10)

第一代的图卷积神经网络很巧妙的利用图谱理论来实现拓扑图的卷积操作，但其有很多缺点，比如说：计算复杂度太高，我们需要对拉普拉斯矩阵进行谱分解得到特征向量矩阵

，时间复杂度为

；就算实现完成谱分解，在做矩阵运算时时间复杂度也高达

；此外，GCN-1 的卷积操作是全局的操作，并不是仅来源于节点的邻域。

针对这些问题，学者提出了第二代 GCN：ChbeyNet。

首先我们回顾下图傅立叶变换：

可以看到这是一个和特征值密切相关的函数，我们不妨将

写成拉普拉斯矩阵 L 的特征值函数

：

然后这个卷积核有两个局限性：

不具备局部连接性；

时间复杂度为

。

为了克服这个缺点，我们引入 K 阶多项式：

其中，参数

是多项式系数，这样滤波器就具有了 K 阶局部性了，复杂度也降低到

。

我们将这个公式带入卷积运算中：

此时，我们计算图卷积运算就不需要再乘上特征向量矩阵

，而是直接使用拉普拉斯矩阵 L 的 k 次方，这样就避免了进行特征分解。而我们可以事先计算好

，这样就只需要计算矩阵相乘。同时由于 L 为稀疏矩阵，所以时间复杂度为

，

为节点边数。