深入理解图卷积网络（4）

1.图卷积与拉普拉斯平滑：图卷积网络的过平滑问题

我们可以从不同的角度理解图卷积网络的作用机制，其中一个是：通过与不利用图信息的全连接网络进行比较。让我们考虑一层简单的图卷积网络：

它可以被拆解为两步。我们先对H¹  用图卷积，得到一个新的特征矩阵：。然后在这个新的特征矩阵上加上一个全连接层：

实际上，图卷积网络的每一层就是一种特别的拉普拉斯平滑。拉 普拉斯平滑就是让一个点和它周围的点尽可能相似，每个节点的新特征是其周围节点特征的均值。让我们考虑这样一个图，在原来图的基础上，给它加上自环，也就是每个节点可以有连接到自己的边，这样图的邻接矩阵就变味了，即 =A+I。   在这个图上，节点特征的任意维度都可以看成一个图信号，那么在这个维度上的拉普拉斯平滑就可以被定义为：

 如果加上节点本身的影响，则可以扩展为：

 其中 0<γ≤1是控制信息传播中当前节点信息和邻接点信息比例的参数。写成矩阵形式就是：

 在γ=1的标准情况下，有：

        虽然拉普拉斯平滑的特性给图卷积网络带来了很多好处，使得每个节点能够更好地利用周围节点的信息，但是它也带来了对图卷积网络模型的限制。研究者发现，叠加越来越多的图卷积网络层后，训练结果不仅没有变得更好，反 而变差了。这又是为什么呢?

        假设一个图是联通的，并且不是一个二分图，我们对它上面的一个图信号 w 做 m 次拉普拉斯平滑(相当于叠加m 层图卷积网络)后，这个图信号将最终收敛到同一个值，节点本身的信息则全部丢失既：

 其中c是一个常数项。

        如果图不是联通的，则我们可以把图分割成不同的联通块，并得出相似的结论，只不过叠加无限多层之后的状态就是多个u0向量的线性组合。

        这就是图卷积网络的过平滑问题。之后，又有研究者对图卷积网络的过平滑问题做出了更详细的理论分析:当图卷积网络的参数满足一定条件时，随着图卷积网络层数的增加，它的表达力呈指数下降。

        叠加多层图卷积网络会过平滑，而只用浅层(如两层)图卷积网络又不能获得有用的远程信息，怎么解决这个问题呢?Li等人想了一个办法，他们除了使用图卷积网络模型，还使用了一个随机游走模型，将两个模型通过协同训练的方式结合，得到一个类似于标签传播的最终态，这就意味着信息已经从任意节点传到无限远了。然后，图卷积网络和随机游走模型可以用协同训练的方式结合，进行半监督学习，这样就同时拥有了两个模型的好处。 实验证明，这个方法在训练标签更少的时候可以显著提升图卷积网络的效果。除了这种方法，解决深层图卷积网络过平滑问题的方法还有残差连接、跳跃知识网络。后面将会介绍。

2.图卷积网络与个性化PageRank

        同样是为了解决图卷积网络的过平滑问题，一个新的观点被提出将图卷积网络与个性化PageRank联系在一起。对一个k层的图卷积网络，假设输入节点属性为X, 邻接矩阵为A, 输出节点嵌入为 Z,   那么一个节点x 对另一个节点y 的影响分数可以被计算为

,它与从根节点x 出发的k 步随机游走的概率密切相关： P(x→y,k)。当随机游走到无限远时(即k→0),  并且如果这个图是不可约且非周期性的，那么这个随机游走的概率分布会收缩到一个极限π= Aπ 。由于这个极限状态的解只依赖于图结构本身，与出发点无关，就导致节点本身信息的损失(等同于过平滑)。在PageRank 中，我们可以得到一个随机游走的收敛状态 πpr=Arwπpr,不同的只是状态转移矩阵用的是Arw=AD-1（上标）。

        为了解决节点信息丢失的问题，在PageRank中，我们可以通过在随机游走中保留部分根节点信息来改进模型，也就是得到个性化PageRank模型。我们只需要对随机游走模型做些许改动，加上根节点的信息，使它变成：

求解它的极限状态，得到：

        这个极限状态也就是个性化PageRank的解。可以看出，即使在极限状态下，通过对根节点的设置，原节点的信息ix 依然被保留，在最终状态中，不同节点也就拥有了不同的表示。

        然后，我们可以将这种传播方式移植到图神经网络中。我们先对节点的属性X进行变换，得到一个初始的节点状态H, 然后利用个性化PageRank更新这个状态直到收敛，这样一个可以把节点信息传到“无限远”的新模型就诞生了：

其中H=f(X) 可以是一个多层感知机。这个全新的图神经网络被称为PPNP（神经网络预测的个性化传播模型）。求解矩阵的逆(I-(1-a)A)-1并不是一件容易的事情，复杂度非常高， 尤其在图很大的情况下是很难直接计算的。因此，我们做了一个近似 计算，相比于直接求矩阵的逆计算出最终状态，我们可以把它拆解成随机游走 的形式进行 K 步迭代计算：

         因为是对PPNP的一种近似，所以称这个模型为APPNP（神经网络预测的近似个性化传播模型)。观察APPNP的每个步骤，我们会发现只有在最开始Z⁰  的计算中有参数，接下来的更新步骤都是无参数的，这使得增加层数不会对整个图神经网络的参数量造成影响，因此只需要很少的参数就 可以传播到更多的层，而且不太容易造成过平滑的问题。

3. 图卷积网络与低通滤波

        回顾第3章介绍的谱域图神经网络，图卷积网络可以看成图信号在谱域上的滤波器：

        其中一个图信号x先通过图论傅里叶变换变为谱域中的信号x=UTx, 通过一个滤波器 g(A),  再用图论逆傅里叶变换回到原来的空域。在图傅里叶变换中,U中的每个特征向量代表一个基底，对应的中的特征值代表一个图信号的频率 。

        为了了解图神经网络的滤波性质，我们先来想一个问题：在图信号中，究竟是什么频率的信号起了更大的作用?我们来看一个简单的实验。为了验证滤波效果，我们给图信号(节点的属性)加上高斯噪声N(0,o² ),然后只取U 中前 k 个基底(对应频率最小的k个分量)进行图论傅里叶变换和逆傅里叶变换  U[:kU][:k]T。 注意，这里没有滤波器，所以这个过程只是对图信号的重构。 只不过我们去掉了高频的信号，只保留了前k个低频部分。在得到重构的图信号之后，我们以它为输入，训练一个两层的多层感知机，在图数据上做节点分类任务。

        图信号中的低频成分或许保留了大部分有用的信息， 而高频成分则类似于噪声，需要过滤。从这个角度考虑，一个图卷积网络应该尽量设计成一个低通滤波器，尽量保留图信号中的低频成分。那么,我们熟悉的图卷积网络是否符合这个猜想呢?

        每一层图卷积网络可以拆解为两步，左乘A 的卷积操作和右乘 W 的全连接层。我们可以把卷积这一步看作对图信号的滤波。这样谱域上的图卷积可以被重新写成

Y=Ug()UT(转置)xw,g()变成了一个没有参数的滤波器，而可学习的参数都被挪到了右边的W  中。

        为了简化分析，假设图论傅里叶变换所用的是正则化后的拉普拉斯矩阵 L=I-D-1/2AD-1/2,那么D-1/2AD-1/2x=(I-L)X=U(I-)UTx 对应的滤波器就是g()=I- 。在大部分图上(特征值接近2属于比较少见 的情况)这都是一个低通滤波器。D -1/2AD-1/2 xW实际上是一个没有加自环的图卷积网络，在加了自环并做相应的正则化后，D-1/2(A+I)D-1/2xW 造成所有的特征值进一步收缩，变得更接近0,也就造成了图卷积网络的低通效果。

4.图滤波神经网络

        我们可以先对图信号(节点属性矩阵)进行滤波，再将其输入一个可学习的多层感知机中。低通滤波器的选择可以不必拘泥于图卷积网络，图上的任意低通滤波函数都可以被采用。这样，我们就得到了一 个基于图滤波的推广模型，叫作图滤波神经网络:f=fmlp(fA(X))其中，fA代表一个图上的低通滤波器，而fmlp是一个多层感知机。下面来看一个简单的例子。之前讨论了图卷积网络与拉普拉斯平滑的关系，其实拉普拉斯平滑也经常被用于半监督机器学习，它本质上也对应了图信号分析中常用的一种低通滤波。采用拉普拉斯正则化的半监督学习可以被写为：

它的最优解是y=(I+L)-¹x。    如果把x看成图信号而非标签，则它就对应了一个g()=(I+γ)- ¹   的滤波器。如果 =1,    则对它做一阶泰勒近似，就回到了不加自环的图神经网络的滤波器形式

g()≈I-。最后，不得不提的是，并非所有图神经网络都是低通滤波的。

5.简化图卷积网络

        将图神经网络拆解成一个滤波器和一个多层感知机的好处是可以创造出更加简化的模型，比多层感知机更早提出的简化图卷积网络就是这种思想下的产物：在多层图卷积网络中，若省略每一 层的非线性函数，多层图卷积网络叠加之后的简化模型仍然可以看成由两部分组成，左边是多层图卷积，右边是多个全连接线性层：

叠加多层之后的图卷积(A^mX)，仍然起到了低通滤波的作用，而多个全连接线性层可以合并在一起。这个模型的好处是在我们想得到多层图卷积网络时预先计算出A^m, 而不需要进行中间层的多次迭代，节省了不必要的内存空间并且降低了计算复杂度。实验结果也证明，简化图卷积网络可以得到几乎和图卷积网络一样的效果，丢失中间的非线性层并没有损失模型的精度，而它带来的复杂度的降低则对工业应用特别友好。

        值得注意的是，简化图卷积网络是在所有线性层叠加完之后，加上非线性层来预测Y=Softmax(Z)=Softmax(A^mxθ),这一点和图滤波神经网络有区别。图滤波神经网络右边的线性层并没有合并，以图卷积网络作为滤波器的两层图滤波神经网络为例，f=σ(σ(A^²xW₁)W₂),     因此，图滤波神经网络在具有简化图卷积网络优势的同时，又增加了一定的模型表达性，效果也稍好。

小结

        本章简单地介绍了图神经网络与其他领域的联系，道出了图卷积网络本质上可以被认为是拉普拉斯平滑，从图信号分析的角度看，它是一个低通滤波器。 由此，我们分析了图卷积网络，以及其他图神经网络的最大问题之一：当叠加多层之后信息丢失，也就是过平滑。我们也看到了将滤波与可学习的参数分离， 可以设计出新的、更简单的或者更有表达力的图神经网络模型。