GCN over smoothing问题最早应该是《Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning》2018 提出的。在这篇以及后续几篇研究GCN理论的文献都有类似的over smoothing的推导，我整理出来如下：
over smoothing的推导
首先给出GCN的信息传递矩阵的
次幂收敛性的推导。Kipf版GCN形式是：
设对称拉普拉斯矩阵，其中特征值
- 先证明
的最小特征值是0。不难看出
所以
，其中
是元素全为1的向量。
- 再证
，另
，那么有
当图是二分图的时候，不等式的等号成立。由于现实中只要不是太小的图，都几乎不可能是二分图，所以不讨论
和
- 第三步是对
进行矩阵分解。Kipf版GCN，忽略激活函数时有
，而
，所以
再根据上文讨论的特征值取值范围，可以得到的收敛状态：
。
，M是edge数量，N是node数量。因此：
其中常数项
。所以层数很大的时候，输入图信号已经完全被平滑掉了，剩下的只有度的信息，图信号也就很难在欧氏空间线性可分了。这就是over smoothing的根本原因。
我这个是简化版的证明，没考虑激活函数的情况。最完整的证明见ICLR 2020的《Graph Neural Networks Exponentially Lose Expressive Power for Node Classific》。此文证明了在权重矩阵最大元素乘以Laplacian的最小非零特征值小于1的条件下，GCN随着卷积层增加，图信号会收敛到Laplacian矩阵的零特征值对应特征向量张成的子空间内，这个子空间里图信号是完全损失了的。并且信息的损失速度是层数的指数倍。
over smoothing solution文献综述
- 《Representation Learning on Graphs with Jumping Knowledge Networks》2018这篇文献的贡献在于证明了以下几点：a.不同类型的节点的over smoothing速度不一样，越边缘的节点过平滑的速度越慢；b.以
作为信息传递矩阵时，图卷积和随机游走的等价性。其实这个在Chung的图谱理论书里也有讨论了。这篇论文的理论分析很值得一看，不过提出来的Jumping Knowledge Networks模型比较平凡。
- 《Predict then Propagate: Graph Neural Networks meet Personalized PageRank》 2018此文从personalized pageRank得到启发，提出了PPNP模型和APPNP模型。如果把图卷积的过程看作一个随机游走过程，
是平稳状态，那么有
。Personalize PageRank算法希望随机游走的过程有一定概率跳转回到原始状态，则有
，其中
表示初始状态，也可以理解为输入图信号。因此得到了
。PPNP模型的形式是：
是输入的图信号。如果求矩阵逆的过程复杂度太高，那么将上式的矩阵逆进行泰勒展开，就有了近似PPNP模型，APPNP模型：
理论和文中的实验都显示K趋于无穷大时，APPNP模型会收敛到PPNP模型。这个研究挺有创新型的，在citation数据集的分数也超出了GCN不少。 - 《simple and deep graph convolutional networks》2020在APPNP的基础上加上了参数矩阵的identity mapping，提出的GCNII模型形式是
在理论上作者证明了该模型能拟合任意系数的自环拉普拉斯矩阵多项式滤波器，实验表现很亮眼，刷新了3个citation数据集的SOTA分数。我认为APPNP和GCNII都是彻底解决over smoothing的很好的方案。 - 除此之外，还有一些研究，我认为是缓解但没有彻底解决over smoothing的，包括：ICLR 2020的文章：DropEdge和PairNorm；Nips 2020的GRAND和GroupNorm，这些我觉得都比较水；KDD 2020有一篇研究提出了DAGNN，大概是一个对每层图卷积的输出进行AttentionPooling，模型没啥创新型，建模思路值得一学，在citation数据集的表现也不错。
