GNN 2021(十二) On the Equivalence of Decoupled Graph Convolution Network and Label Propagation，WWW

解耦GCN的工作原理尚不为人们所完全理解，尽管其表现出色。在本研究中，我们从一个全新视角探讨了半监督节点分类中的解耦GCN模型。通过深入理论研究发现：解耦后的GCN本质上等同于两步标签传播机制：首先，在图上扩散已知标签以生成伪标签；其次，在包含伪标签的数据上训练常规神经网络分类器。我们的研究表明：解耦后的GCN具有优于传统标签传播的优势在于其能自动分配权重给伪标签数据中的结构信息与模型感知特征参数。这一发现解释了为何解耦后的GCN在面对结构噪声与过度平滑时更具稳定性：因为其能够有效避免传统方法在这些情况下的局限性；但同时也容易受到标签噪声干扰以及模型初始化选择的影响。基于上述发现基础之上，在现有技术框架下提出了创新性方法：动态自适应传播与训练（Propagation and Adaptive Training, PTA）。该方法采用动态自适应加权策略以克服现有解耦方案的技术缺陷

PRELIMINARIES

Decoupled GCN

解耦GCN的公式如下：

其中f_\theta(·)是特征变换函数，可以是一个神经网络；\bar{A}=\sum{\beta_k\hat{A}^k}，由图结构和传播策略决定，其元素反映了图中两个节点的邻近性。解耦GCN有两个通用的代表：APPNP以及DAGNN：
APPNP ：

DAGNN 类似于 APPNP ，但其主要区别在于 传递机制 。具体而言，在每一步操作中都会对特征进行加权计算后再进行传递：\bar{A}=\sum_{k=0}^{K}{s_k\hat{A}^k} ，其中 s_k 表示各层对应的权重系数。值得注意的是，在 SGC 模型中，默认采用了一种通过分离作用来实现信息传递的方式。

这里的\bar{A}被定义为S^K（即\bar{A} = S^K），而函数f_\theta(·)则等于X\Theta（即f_\theta(·) = X\Theta ）。这些模型本质上属于基础类型，并且APPNP与DAGNN在之前的博客中也有详细的介绍

Label Propagation

标签传播算法是一种成熟的半监督学习方法，在图结构中传播已标注数据到未标注节点。它的工作原理可借助数学模型进行形式化表达。

其中符号 Y^{(k)} 代表在第 k 次迭代过程中使用的软标签矩阵。\n变量 y_{ij} ^{(k)} 度量了节点 i 在第 k 次迭代中被预测为类别 c \n的概率。\n对于 LP 算法而言\n其传播机制 \hat{A} 通常采用多种不同的策略。\n例如\n在借鉴于 APPNP 框架时\n

UNDERSTANDING DECOUPLED GCN FROM LABEL PROROGATION

Propagation then Training

在研究解耦GCN的过程中, 我们希望在此过程中设计一种简单的基于标签传播的节点分类模型. 具体来说, 则包含两个阶段: 第一阶段是通过LP算法沿图传播已知节点的真实标签; 第二阶段则是利用这些传播得到的伪label（称为softlabel）. 对于未标记的数据点, 我们会生成这些pseudo labels. 在这一系列处理之后, 我们会利用增强后的pseudo labels数据集来训练一个神经网络预测器. 这种训练模式简单直观, 通过引入人工生成的信息来提升数据质量, 从而有助于提高模型的表现能力. 从形式上来看, 模型优化的目标函数如下:

\min_{\theta} \sum_{v=1}^V \mathcal{L}(y_v, f_\theta(x_v'))

其中, x_v' 表示经过人工增强后的输入特征向量; \mathcal{L} 是损失函数; f_\theta 是我们的神经网络预测器; V 是图中所有节点的数量.

\iota()定义为损失函数。如果我们选择交叉熵作为损失函数，则上述公式可转换为：

如果与邻接矩阵有关，则公式（9）中的\bar{a}_{ij}就是经过归一化处理后的权重参数。按照公式（9）所描述的方法被称作Propagation then Training Statically (PTS)。然而，在不依赖于邻接矩阵的情况下，则对于那些不依赖于邻接矩阵的LP算法，则可以采用一种学习权重来替代：

其中交叉熵为 CE 。可学习的广义权值 w （而不单纯仅依赖于拓扑结构进行加权），受模型预测结果及传播方案调控，并被称为Propagation then Training方法（简称 PT ）。其具体形式为函数 g:

Connection between Decoupled GCN and PT

本文从数学角度深入探讨了解耦GCN的梯度特性，并通过深入研究发现，在训练阶段解耦GCN的行为与PT模型之间存在显著的一致性。

证明：通过对解耦GCN与PT梯度进行分析研究, 可以得出该引理成立的理论依据. 首先指出, 在结构GCN传播机制中存在以下损失函数:

对参数\theta求导，具体过程稍微在纸上推导：

并且因为y_j属于one-hot向量，在这种情况下仅当第j个元素等于1时才成立，并且从而使得方程（12）得以进一步简化。

\nabla_\theta之前的项可以看成是一个动态的参数w，那么可得：

这个就是PT的梯度。因此LEMMA成立。

Analyzing Decoupled GCN from PT

通过上述证明过程, 我们能够深入理解解耦GCN的工作原理。这等价于通过标签传播机制生成伪标签, 并利用加权损失函数对这些伪标签数据进行神经预测器的优化训练。从式(13)可知, 解耦GCN的核心在于利用标签传播构建额外的学习样本。具体而言, 该方法将节点j的真实标签扩散至其他节点（例如节点i）, 并通过强化处理后的伪标签数据来训练一个性能更为卓越的分类器。因此, 解耦GCN之所以能够提升原始GCN性能的原因在于: 首先, 通过将真实信息与推断出的信息相结合, 可以显著提高模型的学习能力; 其次, 强化后的伪标签能够更有效地引导模型捕捉复杂的特征关系; 最后, 这种机制使得模型在面对复杂图结构时表现出更强的泛化能力。

1. 在半监督学习场景中存在一个关键挑战即节点标记数据量有限难以有效提升模型性能。
2. 解耦图卷积网络通过动态调整权重克服了传统方法依赖固定权重带来的局限性。
3. 推断阶段预测节点标签依赖于其K-hop邻居的特征信息而非仅基于自身属性。

但是，这也暴露出解耦后的GCN存在的一些缺陷：

基于模型预测结果实时更新权重的数据被称为伪标记数据，在这种情况下，模型初始状态对整个训练过程的影响显得尤为重要。（这是因为邻接矩阵进行了归一化处理）这暗示着我们假定每个来源标签对标签样本具有同等的重要性。然而这种方法忽视了标签质量及重要性差异的影响，在真实应用场景中可能存在较明显的缺陷与不稳定性。

PROPOSED METHOD: PROPAGATION THEN TRAINING ADAPATIVELY（PTA）

旨在使模型对标记噪声更加抗干扰，并通过取消解耦GCN层的规范化处理，使得具有不同标记的数据在模型训练中产生独特的影响效果。未经过规范化处理的权重参数表达式为：

旨在使模型对标记噪声更加抗干扰，并通过取消解耦GCN层的规范化处理，使得具有不同标记的数据在模型训练中产生独特的影响效果。未经过规范化处理的权重参数表达式为：

由特定的标记源节点生成的伪标记数据的累计权值可记为：

基于变量f进行动态调整的是该算法的核心特点。然而这种设计可能会影响到模型对初始参数的敏感性 从而影响了标记数据的影响范围 我们将在后续的设计中采取措施来解决这一问题 在后续的设计中将采取措施来解决这一问题

基于上述分析 我们开发了一个自适应加权机制 为此我们提出了一个自适应加权机制 详细描述如下

其中 权值w_{i,k(j)}的变化可能会对网络的整体性能产生影响 为此我们提出了一个自适应加权机制 详细描述如下

其中 权值f_{i,k(j)}的变化可能会对网络的整体性能产生影响 我们开发了一个自适应加权策略如下

\gamma用于控制f_{i,h{(j)}}对于伪标签权重的影响，并随着训练的过程而优化。𝑒表示当前的培训时代，𝜖是一个控制灵敏度的温度超参数。在epoch较小时，不成熟的神经网络产生的预测相对不可靠，PTA减少了模型预测对加权伪标记数据的影响。这种设置使模型产生稳定的结果。随着训练的进行，随着神经预测器逐渐给出更准确的结果，PTA扩大了其影响，使模型对标签噪声和结构噪声都具有鲁棒性。我们消除了解耦GCN的局限性，同时充分利用了它的优势。总的来说，PTA优化了以下目标函数：

FRAMEWORK OF PTA

PTA的框架由数据预处理、训练和推理三部分组成。

• Data preprocessing. By leveraging label propagation algorithms, we expand the soft label set Y_{soft}. Specifically, this paper employs a personalized PageRank approach to propagate labels.

• Operation。在训练过程中仅仅涉及简单的神经网络f_\theta(·)的训练工作，其损失函数形式如式（18）所示；同样也可以表示为

在该方法中（其中该方法是指 PTS），其参数\gamma设为0（主要应用于静态传播过程）。而 PTD则设为1（其核心流程是先进行传播再进行动态优化）。

• Inference。在预测的时候还是使用APPNP：

这里只有f_\theta(·)是学习到的。用算法伪代码描述：

EXPERIMENTS

数据集：

实验主要回答四个问题：

Q1

通过消融实验来验证模型性能。我们将解耦图卷积网络（GCN）的有效性主要归因于三个方面：第一部分是基于标签传播的数据增强措施包括标签传播；第二部分是引入了动态权重机制；第三部分是采用了基于图结构信息的信息融合预测器（即依照图结构进行信息聚合）。为了系统地分析各组件的作用影响程度，在实验中我们设计并执行了消融研究，并与baseline对比：第一组对比方案采用多层感知机（MLP），这等价于去除了伪标记学习和基于图结构的信息聚合；第二组对比方案去除了伪标签的学习过程（即权重参数w_{ij}被移除）；第三组对比方案不再采用动态调整权重的方法；第四组对比方案去除了集成过程（即去除了式（31）中第二个子模型）。

从表4，可以有结论：

1. 在性能上显著优于MLP的所有带有标签传播的方法进一步验证了伪标签的有效性；
2. 通过对比PTS与APPNP-noa-nof, 得出了结论：使用带权的伪标签在性能上具有显著优势；同时发现，在实际应用中发现APPNP相较于PTS表现出色。
3. 我们还观察到APPNP始终优于APPNP-noe, 得出结论：集成在提升解耦GCN性能方面发挥了关键作用。

Q2

也可以看到模型的抗噪结构噪声的能力：

而对于标签的噪声，本文提出的PTA要比APPNP更加优异。

Q3

与基线模型比起来，效果更好。

Q4

比起APPNP，耗时更少。