过度平滑被认为是深度图卷积网络（GCN）中性能下降的主要原因。 在本文中，我们提出了一种新的观点，即深层GCN可以在训练过程中真正学会抗过度平滑。 这项工作将标准GCN体系结构解释为多层感知器（MLP）的分层集成和图正则化。 我们分析并得出结论，在训练之前，深层GCN的最终表示确实会过度平滑，但是，它会在训练过程中学习到反过度平滑的功能。 根据结论，本文进一步设计了一种便宜而有效的技巧来改善GCN训练。 我们验证我们的结论并评估三个引文网络上的技巧，并进一步提供有关GCN中邻域聚集的见解。
本文指出：深度GCN在训练之前确实会出现过度平滑，这也是GCN的特性，但在训练过程中它会学习抗过度平滑。通过两步来重构基于MLP的图正则化模型。每一步最小化一个损失函数，其中 ι r e g \iota _{reg} ιreg是图正则化损失，表示的是相连节点对之间的平滑性。 ι 0 \iota _{0} ι0是经验损失。步骤一隐式地将正则化损失编码为MLP的层级传播，得到GCN结构；步骤二在GCN结构上执行标准的反向传播算法来最小化 ι 0 \iota _{0} ι0 所以GCN能被表示为两步最小化： 在前向传播的过程中编码 ι r e g \iota _{reg} ιreg，并在 ι 0 \iota _{0} ι0的监督下训练参数。 该图很明显的说明了在前向传播过程中（训练之前），GCN确实会遇到过平滑，因为特征之间的平滑性得分和节点之间的平滑性得分越来越高，说明特征和节点之间趋于一致，由于深层GCN体系结构的影响自然会使 ι r e g \iota _{reg} ιreg最小，因此逐渐使所有节点表示与拉普拉斯算子的最大特征向量成比例。但是在step2训练过程中GCN会学习阻止过平滑。因为：（1）过平滑的情况取决于 { W l } \left \{ W_{l} \right \} {Wl} （2）step2的目标是找到最优的 { W l } \left \{ W_{l} \right \} {Wl}，也就是最小化经验损失 ι 0 \iota _{0} ι0 （3）只要过平滑存在，节点间的表达就会变得难以区分，所以最小化 ι 0 \iota _{0} ι0，模型必须学习使特征变得可分，也就意味着抗过平滑。
图正则化是一种相当通用的图嵌入算法，它被描述为：找到一个映射 f ( ⋅ ) f\left ( \cdot \right ) f(⋅),来最小化下面的损失函数： 第一项是标签集的经验风险，第二项是相连节点对的图正则化项。 其中： Δ = I − D − 1 / 2 A D − 1 / 2 \Delta =I-D^{-1/2}AD^{-1/2} Δ=I−D−1/2AD−1/2是正则化后的拉普拉斯算子， ι r e g \iota _{reg} ιreg是对相邻节点间引起的变化进行惩罚。
给定拉普拉斯算子 Δ ∈ R n × n \Delta\in \mathbb{R}^{n\times n} Δ∈Rn×n ，特征矩阵 Δ ∈ X n × d \Delta\in \mathbb{X}^{n\times d} Δ∈Xn×d ，为了防止出现平凡解 X = 0 ∈ R n × d X=0\in \mathbb{R}^{n\times d} X=0∈Rn×d，加入一个限制条件， ∣ ∣ X ∣ ∣ F 2 = c 1 ∈ R ∔ \left | \left | X \right | \right |_{F}^{2}=c_{1}\in \mathbb{R}^{\dotplus } ∣∣X∣∣F2=c1∈R∔，即 X X X的F范数必须为正数，F范数是矩阵各项绝对值平方之和。那么这个最优化问题就变为了： 我们把这个最优化问题转化成瑞利熵： 瑞利熵： 一个向量 x ∈ R m x\in \mathbb{R}^{m} x∈Rm的瑞利熵是一个标量： 它对 x x x具有尺度不变性，即对于任意 c 1 ≠ 0 ∈ R c_{1}\neq 0\in \mathbb{R} c1=0∈R,有 R ( x ) = R ( c 1 ⋅ x ) R\left ( x \right )=R\left ( c_{1}\cdot x \right ) R(x)=R(c1⋅x)，我们将 R ( x ) R\left ( x \right ) R(x)看成 x x x的函数，当 x i x_{i} xi是 △ \bigtriangleup △的特征向量时， x i x_{i} xi是稳定点。假设 Δ x i = λ i x i \Delta x_{i}=\lambda _{i}x_{i} Δxi=λixi ，则 x i x_{i} xi的瑞利熵恰为其对应的特征值 λ i \lambda _{i} λi 当 x x x不是 Δ \Delta Δ的特征向量时， R ( x ) R\left ( x \right ) R(x)关于分量 x j x_{j} xj的偏导为： 因此 R ( x ) R\left ( x \right ) R(x)关于 x x x的偏导为： 回到上面的最优化问题上面来：
一步提升： 给定初始值 X X X，一步优化的目标是找到一个更好的值 X b e t t e r X_{better} Xbetter，满足 R ( X b e t t e r ) ≤ R ( X ) R\left ( X_{better} \right )\leq R\left ( X \right ) R(Xbetter)≤R(X)，并且 ∥ X b e t t e r ∥ F 2 = c 1 \left \| X_{better} \right \|_{F}^{2}= c_{1} ∥Xbetter∥F2=c1。我们的策略是首先将这个问题看成是 R ( x ) R\left ( x \right ) R(x)的无约束优化，然后通过梯度下降将 X X X更新为中间值 X m i d X_{mid} Xmid，使得 R ( X m i d ) ≤ R ( X ) R\left ( X_{mid} \right )\leq R\left ( X \right ) R(Xmid)≤R(X)。最后将 X m i d X_{mid} Xmid进行缩放，得到更好的值 X b e t t e r X_{better} Xbetter，满足标准约束。 给定初始值 X X X，运用梯度下降，学习率为： 在无约束空间里得到中间值 X m i d X_{mid} Xmid： 经过证明可知 R ( X m i d ) ≤ R ( X ) R\left ( X_{mid} \right )\leq R\left ( X \right ) R(Xmid)≤R(X)，令 X b e t t e r = c 3 ⋅ X m i d X_{better}= c_{3}\cdot X_{mid} Xbetter=c3⋅Xmid，从而满足规范约束 ∥ X b e t t e r ∥ F 2 = c 1 \left \| X_{better} \right \|_{F}^{2}= c_{1} ∥Xbetter∥F2=c1。
公式讨论： 通过上述讨论可知 R ( X b e t t e r ) = R ( X m i d ) ≤ R ( X ) R\left ( X_{better} \right )= R\left ( X_{mid} \right )\leq R\left ( X \right ) R(Xbetter)=R(Xmid)≤R(X)，并且
考虑简单的多层感知机（MLP），它的前向传播规则为： step1：在前向传播中最小化 ι r e g \iota _{reg} ιreg 为了保证MLP的输出能获得更小的 ι r e g \iota _{reg} ιreg，一种经验的方法是在层级传播中使用梯度下降，那么平滑效应也会随着层逐渐积累。考虑（l+1)的输出： 因此，GCN正向传播实质上是在MLP的正向传播中逐级应用STEP1，是映射 f = f ( L ) ∘ . . . ∘ f ( 1 ) f=f^{\left ( L \right )}\circ ...\circ f^{\left ( 1 \right )} f=f(L)∘...∘f(1)在初始特征 X ( 0 ) X^{\left ( 0 \right )} X(0) 上的组合。本质上，GCN结构隐含了最小化图正则化器的目标。
step2:在反向传播中最小化 ι 0 \iota _{0} ι0 我们已经将图正则化 ι r e g \iota _{reg} ιreg转化成了层级卷积算子，那么经验损失 ι 0 \iota _{0} ι0就是唯一的监督损失了，在训练过程中，通常使用反向传播算法来执行。
综上所述：GCN模型可以从图正则化的角度来解释，step1隐式地将图正则化编码为了MLP的前向传播，这也解释了我们通常看到的GCN结构是为什么是这样的。step2在反向传播后，会学习最优的 { W ( l ) } \left \{ W^{\left ( l \right )} \right \} {W(l)}和低维的 f ( X ) f\left ( X \right ) f(X) 。因此GCN能被表示为两步最优化：
GCN在很多应用上都被限制在较浅的层（2-4层），当增加更多的中间层后模型的性能就会降低。可能有三种原因导致： （1）增加参数导致的过拟合 （2）梯度消失或爆炸 （3）由于拉普拉斯平滑造成的过平滑 前两个原因是所有深度结构里面都共有的，因此过平滑问题是本文关注的重点。通过分析深度GCN在训练过程中的表现可以得出，GCN的训练过程是起始于过平滑环境的，并且深度GCN能学习抗过平滑，通过实验，表明过拟合可能是性能下降的主要因素。
过度平滑意味着节点的表达变得越来越相似，多层图卷积后最终变得难以区分。主要的原因由下面的定理给出： Theorem1. 给定任意的信号 x ∈ R n x\in \mathbb{R}^{n} x∈Rn，和一个对称阵 A ∈ R n × n A\in \mathbb{R}^{n\times n} A∈Rn×n，性质 lim k → ∞ A k x ∝ u 1 \lim_{k\rightarrow \infty }A^{k}x\propto u_{1} limk→∞Akx∝u1 对 x x x几乎处处成立。这里 A A A具有非负的特征值并且 u 1 u_{1} u1是 A A A最大的特征值。 证明： 将 A A A进行特征分解，得到 在一个 k k k层的SGC（GCN的线性模型）中，图卷积的效果和应用拉普拉斯平滑 k k k次的效果一样。 假设 λ 1 \lambda _{1} λ1是最大的特征值，堆叠无穷次的层之后， lim k → ∞ A k x ∝ u 1 \lim_{k\rightarrow\infty }A^{k}x\propto u_{1} limk→∞Akx∝u1, 即输出和输入特征 x x x无关。 特别的，对于两个被广泛使用的卷积算子 A s y m = D ˇ − 1 / 2 ( I + A ) D ~ − 1 / 2 A_{sym}=\check{D}^{-1/2}\left ( I+A \right )\tilde{D}^{-1/2} Asym=Dˇ−1/2(I+A)D~−1/2，和 A r w = D ~ − 1 ( I + A ) A_{rw}=\tilde{D}^{-1}\left ( I+A \right ) Arw=D~−1(I+A) ，他们有共同的主特征值 λ 1 = 1 \lambda _{1}=1 λ1=1，对应的特征向量为 D ˉ 1 / 2 I \bar{D}^{1/2}I Dˉ1/2I和 I I I.在训练之前，如果深度无穷大，那么GCN的输出将会和 D ˉ 1 / 2 I \bar{D}^{1/2}I Dˉ1/2I和 I I I成比例。幸运的是这种情形取决于参数矩阵， 在训练过程中 ，学习的参数会通过非线性函数变换来充分反抗平滑效应。通过对SGN分析后，可以证明没有非线性激活后，SGN的平滑性会独立于参数，因此不会抗过平滑。所以GCN在训练过程中会逐渐处理过平滑问题。
分析： 两个损失函数其实是一个相互对抗的过程，在训练GCN之前，从定理一可知每个特征通道的输出特征会和卷积算子最大的特征向量成比例。这种情形下，特征表达是难以区分的，正则化损失 ι r e g \iota _{reg} ιreg变小，但是有一个大的经验损失 ι 0 \iota _{0} ι0 ，GCN的训练过程就是从初始平滑环境下平衡 ι r e g \iota _{reg} ιreg和 ι 0 \iota _{0} ι0。 ι r e g \iota _{reg} ιreg是编码相连节点对的平滑性，它是支持平滑环境的，即相连节点共享相似的特征表达。 ι 0 \iota _{0} ι0是根据标签结果计算误差，现实世界中，标签总是包含其他的语义信息，所以两个函数的目标不是一致的。 ι r e g \iota _{reg} ιreg是趋向节点表达一致，而 ι 0 \iota _{0} ι0是逐步地从平滑域（节点的表达与度的平方根成比例）向最优域（节点表达部分相似，可分离，和标签的语义信息一致）转化，这就是一个抗平滑的过程。
从上文可知，深度GCN的学习是从平滑环境开始的，这会使训练过程变慢。因此我们提出一种技巧来保证一个更好的训练开始点，以加速训练。
动机： 本文提出均值减法，即从每个隐藏层的每个特征通道都减去其均值。我们的动机主要来源于定理一，即卷积算子的幂迭代会逼近最大的特征向量，这会导致过平滑的开始。在运用均值减法之后，修正的幂迭代会得到Fiedler向量（特征向量里面第二小的向量），它提供了一个粗糙图分区的结果，使训练更快。
均值减法：假设卷积算子为 A r w A_{rw} Arw，它最大的特征向量 u 1 = I ∈ R n u_{1}=I\in \mathbb{R}^{n} u1=I∈Rn，对于 l l l层通道 k k k的输出特征 X k ( l ) ∈ R n X_{k}^{\left ( l \right )}\in \mathbb{R}^{n} Xk(l)∈Rn，均值减法为： u 1 ˉ = u 1 ∥ u 1 ∥ \bar{u_{1}}=\frac{u_{1}}{\left \| u_{1} \right \|} u1ˉ=∥u1∥u1，上式实际上减小了与 { u 1 } \left \{ u_{1} \right \} {u1}空间相合的分量。逼近了Fiedler向量，该向量被广泛应用与图谱理论里面的图分区，它最初是用来分离节点的。运用均值技巧后，修正的GCN将会在一个粗糙的图分区上进行训练，使训练加快。
本文在三个引文数据集 Cora, Citeseer, Pubmed上进行实验，回答了下面三个问题： （1）使深层GCN性能下降的主要原因是什么？为什么？ （2）怎样加速通用深层GCN模型的训练？ （3）学习率 η \eta η 重要吗？怎样选择邻居节点的聚合权重？
1.过拟合还是过平滑 该图比较了深层GCN和深层SGC在cora和pubmed两个数据集上的训练精度和测试精度。SGC是GCN没有激活函数的线性模型，可以看出SGC的性能在训练集和测试集上随着深度加深会急剧下降，这是过平滑的强烈表现。GCN在测试集上两层之后的性能就不如SGC了，这可能是由于过拟合，但是即使模型深度增加，它的精度始终稳定在一个高的精度，这显示了一个非过平滑的状态。 该图显示了GCN模型在cora数据集上的训练和测试损失随着深度的变化。注意到在浅层（2-3层），随着轮数增加，训练和测试曲线逐渐下降。但是在深层，训练曲线几乎降为0，测试曲线先降低然后升高，因此可以推断过拟合可能是导致深层GCN性能下降的主要原因。还注意到在第3层，测试损失总是水平的，所以3（或4）层可能是过拟合的一个分隔层，这也和我们通常所说的2或3层GCN比深层GCN效果更好的情形相一致。
2.均值减法的效果 该图比较了四种GCN模型的效果，四种模型的实验设置，超参数选择都一样，他们的不同就是怎样转换层级特征矩阵。均值减法是在每个卷积层之前减去平均特征值。PairNorm将在顶部添加一个重新缩放步骤。这两种技巧都没有增加额外的参数。 BatchNorm学习了特征表达的均值和方差，增加了额外的参数。 实验结果表明，mean-subtraction, PairNorm and BatchNorm三个模型都会帮助提高训练过程，因为（1）能很好的拟合训练数据；（2）能很快的收敛；和BatchNorm相比，mean-subtraction得到了更加稳定的训练曲线，并且花费更少的时间。和PairNorm 相比，mean-subtraction在测试数据上有更高的精度，我们认为是在PairNorm里增加的重新缩放可能导致了严重的过拟合问题。总之，mean-subtraction不仅能加速模型的收敛，也能保留相同的表达力，它不失为一个训练深层GCN的理想方法。
3.聚合邻居节点的权重 本文选择的学习率为 η = T r ( X T X ) 2 − T r ( X T △ X ) T r ( X T X ) \eta =\frac{Tr\left ( X^{T}X \right )}{2-\frac{Tr\left ( X^{T}\bigtriangleup X \right )}{Tr\left ( X^{T}X \right )}} η=2−Tr(XTX)Tr(XT△X)Tr(XTX),然而不同的学习率会导致不同的邻域信息聚合权重。下图评估了不同的权重对GCN训练和测试精度的影响。 可以看出，训练和测试精度随着 w ( η ) w\left ( \eta \right ) w(η)的增加先上升后下降，对于通用的浅层GCN，选择权重 w ( η ) w\left ( \eta \right ) w(η)=1，即学习率为 η = T r ( X T X ) 2 − T r ( X T △ X ) T r ( X T X ) \eta =\frac{Tr\left ( X^{T}X \right )}{2-\frac{Tr\left ( X^{T}\bigtriangleup X \right )}{Tr\left ( X^{T}X \right )}} η=2−Tr(XTX)Tr(XT△X)Tr(XTX)，此时效果最好。对于深层GCN模型，更大的权重更可取。
本文从基于MLP的图正则化算法出发重构了图卷积网络（GCN），基于此，分析了深层GCN的训练过程，提出了新的理解：深层GCN有抗过平滑的自然特性，并且过拟合可能是导致深层GCN性能下降的主要原因。更进一步提出了高校的 mean-subtractio技巧来加速深层GCN的训练。
