过平滑

首先来看过平滑。GNN 本质上是逐层推送彼此相邻节点混合的表征，因此极端地看，如果层数无限多，那么所有节点的表征都将收敛到一个驻点，这也就与输入特征完全无关了，并会导致梯度消失问题。因此，过平滑的一个现象是模型的训练损失和验证损失都难以下降。那么，为什么会出现过平滑呢？

我们以线性 GCN 来进行说明。首先，GCN 与平滑有何关联？一般来说，GCN 可被视为拉普拉斯平滑（Laplacian smoothing）的一种特殊形式，如下所示：

这个过程意味着一个节点的新特征是根据其本身和相邻节点的加权平均而构建的。

要知道这个过平滑过程发生的位置，我们先讨论一下 GCN 何时会因过平滑而失效？我们将讨论三种过平滑的情况。第一种是使用线性激活时，隐变量 H_L 会收敛到一个特定的点。第二种是使用 ReLU 激活时，H_L 会收敛到一个特定的平面 M。第三种是使用 ReLU 加偏差时，H_L 会收敛到一个特定的子立方体 O(M, r) 的表面。

在使用线性激活的情况下，H_L 为什么会收敛到一个特定的点呢？实际上，这与 L步随机游走有关。一个游走器从一个节点游走到其一个相邻节点的概率为「1/该节点的度」。经过 L步游走后，游走的路径会形成一个已访问节点的序列。用数学公式表示，随机游走的过程实际上就是一个归一化的矩阵的 L次幂乘以初始概率。

然后，如果我们用一组在节点特征上的可学习参数替换这个初始概率，它就能转换成一个线性的 L层 GCN。

可以看出，基于随机游走的一些结论也适用于线性 GCN，其中一项便是随机游走在经过无限多步之后会收敛到一个驻点。

详细地说，我们首先需要进行特征值分解，即将归一化的邻接矩阵分解为 n 个特征值 λ 及其对应的特征向量 u。

将这个求和展开，可得到下式：

这个图谱中的特征值有一个性质。即，假设一个图 g 包含 m 个互相连接的分量，则归一化邻接矩阵的特征值便由 m 个为 1 的最大特征值构成，其余的 λ 则在 (-1,1) 的开区间中。

因此，当 lL趋近无穷大时，最大的 m 项依然存在，因为其 λ 等于 1。但是，其余的项都将被忽略，因为这些 λ 的 l 次幂将趋近于零。这会使得隐变量 H_L 随网络深度增长而趋近于一个特定的点。

另一方面，对于非线性的情况，H_L 将收敛到一个具有非线性激活 ReLU 的特定子空间 M。首先我们给出 M 子空间的定义：

则随着层的深度增加，隐变量将越来越接近子空间 M。H_L+1 离该子空间的距离至少为：

要注意，λ_m+1 是邻接矩阵中最大的非 1 特征值，s_l 则是模型参数 W_l 中最大的奇异值。

接下来我们开始解析这个收敛公式。这个归一化邻接矩阵的收敛满足这一不等式。

如果我们假设这个子空间的维度为 m，则 m 个最大的 λ 将位于该子空间，其余的则在 λ_m+1 的范围内。

然后，模型参数 W_l 和 ReLU 的收敛分别满足下列两个不等式：

有关这些不等式的更详细证明，请参阅 ICLR 2020 论文《Graph Neural Networks Exponentially Loss Expressive Power for Node Classification》。

综合这些不等式，可得到隐变量的子空间距离沿层数变化的收敛性。可以看到，随着层数趋近于无穷大，子空间距离将趋近于 0，因此隐变量将会收敛到子空间 M。

接下来是更一般的情况，使用 ReLU 加偏差的 GCN 又如何呢？H_L 将收敛到一个特定子立方体 O(M,r) 的表面上。首先，我们写出带偏差的 GCN 的公式：

很显然，由于 b_l 到子空间的距离是一个常量，因此其收敛性就满足：

可以看到，当 l 趋近无穷大时，不等式右侧部分就是一个无穷等比序列的和：

因此，可以看到 H_L 将趋近于一个子立方体的表面，其与子空间 M 的距离为 r，而 r 就等于上式。

总结一下，通过分析上面三种来自不同场景的情况，可以发现这三种情况之下存在一种普适的公式。我们可用以下不等式统一过平滑的情况：

然后通过不同的 v 和 r 取值，我们可以得到不同的具体情况：

详见论文：

《Tackling Over-Smoothing for General Graph Convolutional Networks》（https://arxiv.org/pdf/2008.09864.pdf）。

专栏文章内容及配图由作者撰写发布，仅供工程师学习之用，如有侵权或者其他违规问题，请联系本站处理。 联系我们