图神经网络阅读(二十二)Rethinking Graph Regularization for Graph Neural Networks，AAAI2021

本文的作者系香港中文大学的研究者。
研究表明，在现有GNN架构中使用图拉普拉斯正则化所带来的改进效果甚微甚至并无明显优势；为此我们提出了一种简洁创新的变体方案称为传播正则化(P-reg)，旨在提升现有GNN模型的整体效能。
研究者所提出的模型结构相对简洁明了；然而其涉及的数学公式与理论推导部分较为复杂。
研究领域内的相关背景知识仅限于基础概念。

Propagation-Regularization（P-Reg）

首先，在处理图输入时，模型经过两层GCN（记为f_1）的操作生成输出矩阵 Z∈R^{N×C}。随后对生成的矩阵 Z 进行进一步操作以获得新的矩阵 \hat{A} Z = Z'。即相当于在完成两层GCN后再执行一次无特征矩阵参与的邻域信息传递。由此定义了 P-Reg 的具体形式如下：

ϕ被用来衡量两个特征之间的差异程度。实际上，其本质是通过引入额外的损失函数来增强相同节点在不同传播过程中的相似度。本文着重介绍了三种不同的差异衡量方法：

从而就能通过联合损失函数（基于有监督学习的交叉熵损失带来了影响+P-Reg带来的差异）去训练模型：

其中符号 S_{train} 被定义为训练数据集；
变量 M\text{ }记录着\text{ }训练样本的总数量； 参数 μ\text{ }被设定为\text{ }权重系数；
随后将对这一特定参数进行深入分析。

Grasping the concept of P-reg via Laplacian Regularization in Infinite-depth GCNs

The equivalence of squared-error-based P regularization to squared Laplacian regularization is a critical concept in statistical learning theory.

在原先的论文中描述得令人费解，在此我们进行了适当的重排以提升可读性。首先，在图上定义正则化函数时，则可以采用以下方式：（此处参考文献：Kernels and regularization on graphs）

在GCN模型中通常使用归一化拉普拉斯矩阵\hat Δ；其中其对应的特征值为r(\hat Δ)；而两个矩阵之间的内积运算则定义为其计算公式如下：

其中λi为特征值/ui作为对应的特征向量。初次观察这个公式可能会让人感到困惑不解/first glance this formula might strike you as quite puzzling.因此我们可以采取以下步骤来理解其本质:将等式两边同时乘以对应的特征向量ui/this involves multiplying both sides of the equation by the corresponding eigenvector ui.这样一来就会得到类似于Ax=λx的形式/which will yield a form similar to Ax=λx.真的呢/That's right/这本质上属于广义图正则化算子的特性之一/this is fundamentally tied to one of the key properties of generalized graph regularization operators.然后给出下述定理：

该定理表明，在平方误差框架下定义的P-Reg本质上也属于一种正则化方法。相较于拉普拉斯正则化而言，在这里所讨论的模型中变量R被定义为{\hat Δ}^T\hatax{Δ}（即矩阵Δ转置与自身相乘的结果），而在拉普拉斯正则化中，则是使用r(Δ)来表示。其证明可在附录部分详述。

其中第三个等号后边的\hat{A}Z-Z可以化成(\hat{A}-I)Z，因为外边有着平方所以等价于(I-\hat{A})Z，因此就是\hat ΔZ了。||·||_F表示Frobenius范数（这个定义在原论文中并没有给出），也就是：

此倒数第二步表达式可简化为

1/2\sqrt{\sum_i \sum_j (\widehat{\Delta}Z)_{ij}^2}

因为\widehat{\Delta}是一个对称矩阵，则其按元素相乘\widehat{\Delta}\widehat{\Delta}即等于{\widehat{\Delta}}^\top \widehat{\Delta}, 因此即可得出最终结果。由此可见，在传统的正则化框架下, 平方误差P-reg这一概念同样适用, 从而我们可以充分利用这些优点, 比如构造相应的再生核希尔伯特空间等。（叹）面对这样的证明过程真是让人...

Equivalence of Minimizing P-Reg to Infinite-Depth GCN

第二部分旨在探讨P-Reg与深层网络之间的联系。在去掉了GCN中的激活函数以及参数矩阵W之后，在此前提下得到的深层GCN表达式则可表示为\hat{A}^∞Z。由此可得引理3.1表述为：

这个定理我之前研读了多篇证明，并曾独立推导该定理的证明过程。

带有自环边界的邻接矩阵的最大特征值为1；经过无限次叠加后会逐渐削弱那些具有特征值小于1的部分；这种情况下所有节点都会收敛到相同数值；这也解释了为何深度网络容易出现过平滑的问题。因此通过最小化平方误差项P-reg的方法能够在理论上确保每个节点生成相同的输出向量；这些相同的输出结果与GCN模型在无限深度情况下的表现相吻合，并证明了两者之间的等价性。定理3.2进一步说明了通过最小化Squared Error、Cross Entropy以及KL散度等损失函数的方式能够在理论上实现与多次传播后效果的一致性

Why P-Reg can improve existing GNNs

通过图正则化的视角分析，在理论上而言，在线性代数框架下构建了基于张量分解的概率生成模型，并将其应用于推荐系统中取得了显著的效果；该模型在计算效率和推荐精度方面表现优异。

（a）持续增加训练数据节点的数量会稳步提高模型的分类准确性。这在半监督节点分类任务中表现为一种显著的特性。

（b）P-Reg类似于获取每个节点邻居的投票结果来监督节点。因此，P-reg为节点提供了额外的类别信息，这是无法通过拉普拉斯正则化获得的，因为它只是将边缘连接节点的表示拉近。为了验证这一猜想，提出S_{unmask}，unmasking v_i表示对v_i应用ϕ。这样一来损失就变成了：

当unmask比例上升时,P-reg被应用于更多节点,如图2b所示,整体精度有所提升

（c）Laplacian regularization will not improve the precision of graph models and may even lead to a decline in performance. Furthermore, image-based analysis techniques have validated the model's effectiveness.

Benefits of P-Reg from the Deep GCN Perspective

上文也指出其带来的过平滑现象会显著影响模型性能的表现。因此为了降低这种现象的影响P-reg方法能够有效平衡信息捕获与过平滑的能力，并且通过调节参数μ值大小可以实现对模型复杂度的有效控制。其中调节因子μ值越大则表示模型趋于更深层次的架构。经过可视化实验进一步验证了该方法的有效性

其中w表示类内部的平均距离。

Experimental Results

实验结果就放一些准确率的表格，不再赘述了。