C&S：标签传播思想与浅层模型相结合性能即可超过图神经网络

论文标题｜ Combining Label Propagation and Simple Models Out-performs Graph Neural Networks
论文来源｜ ICLR 2021
论文链接｜ https://arxiv.org/abs/2010.13993
源码链接｜ https://github.com/CUAI/CorrectAndSmooth

TL;DR

图神经网络 (GNNs) 在图表示学习领域盛极一时，但是对为什么 GNNs 有效或者其对不同任务性能提升的必然性知之甚少。这篇文章通过大量的直推式实验（节点分类任务）证明，通过浅层模型和两个基于标签传播的后处理步骤即可达到当前 GNNs 模型的性能 🤭，后处理步骤包括两步 (i) 误差修正 (error correlation)：利用训练数据中的残差来纠正测试数据中的误差 (ii) 预测修正 (prediction correlation)：平滑测试数据中的预测结果，作者将其提出的整个框架总称为 C&S（correct and Smooth），并且在实验中证明 C&S 不仅准确性超过当前主流的 GNNs 模型，而且参数量和运行时间远远低于复杂的 GNNs 结构。

Algorithm/Model

针对图中节点分类任务，论文中提出的简单处理框架如下图所示，

主要包含三个部分：

基础预测模型：仅依赖节点特征并且忽略图的结构，例如 MLP 或者线性模型；
修正步骤：将训练数据中的不确定性传播到整个图以此来修正基础预测结果；
平滑步骤：对节点预测结果进行平滑。

其中修正步骤和平滑步骤是基于半监督学习的标签传播思想进行改进的，整个框架没有利用图结构来学习模型参数因此参数量非常少而且不需要大量的时间来训练模型，但实验效果却非常好，所以愈发感觉神经网络是一门玄学了啊！

下面详细介绍下 C&S 模型的细节。

C&S Model

假设给定无向图 $G=(V, E)$ ，其中节点数量 $n=|V|$ ，节点特征 $X\in\mathbb{R}^{n\times p}$ ，邻接矩阵 $A$ ，度矩阵 $D$ ，归一化邻接矩阵 $S = D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ 。对于节点预测任务，节点集 $V$ 划分为不带标签节点集 $U$ 和带标签节点集 $L$ ，将标签表示为独热编码矩阵 $Y \in \mathbb{R}^{n\times c}$ ，带标签的节点划分为训练集 $L_t$ 和验证集 $L_v$ 。直推式的节点分类任务就是在给定的 $G, X, Y$ 下对于集合 $ U$ 中的节点预测标签。

Base Predictor

首先使用一个不依赖于图结构的基础预测模型 $f$ 基于节点特征来预测节点分类，优化目标函数是

$\sum_{i \in L_{t}} \ell\left(f\left(x_{i}\right), y_{i}\right)$

其中 $x_i\in X, y_i\in Y$ , $\ell$ 是损失函数，论文中使用的 $f$ 为线性模型或者浅层 MLP， $\ell$ 是交叉熵损失函数， $L_v$ 中的样本用于调参。通过 $f$ 可以得到每个节点的基础预测结果 $Z\in \mathbb{R}^{n\times c}$ ，每一行表示 softmax 后节点的分布概率。其实这一步也可以使用 GNNs 来作为 base predictor，但是为了更好地比对效果作者只用了浅层模型。

Error Correlation

这一步骤的主要任务是对 base predictor 中的结果提高准确性，主要思想是希望 base predictor 中的误差是通过图中的边进行传播的，即节点 $i$ 和邻居节点有相似的误差。论文中通过通过残差传播来实现这种不确定性。

首先定义一个误差矩阵 $E\in \mathbb{R}^{n\times c}$ ，误差值是训练集中的残差和零：

$E_{L_{t}}=Z_{L_{t}}-Y_{L_{t}}, \quad E_{L_{v}}=0, \quad E_{U}=0$

对于训练集中已知标签的节点只有基础预测结果完全正确才为 0，因此文中通过标签传播技术来平滑误差

$\hat{E}=\underset{W \in \mathbb{R}^{n \times c}}{\arg \min } \operatorname{trace}\left(W^{T}(I-S) W\right)+\mu\|W-E\|_{F}^{2}$

上式中第一项是为了平滑整个图中的误差，等于 $\sum_{j=1}^{c} w_{j}^{T}(I-S) w_{j}$ ，其中 $w_j$ 是 $W$ 的第 $j$ 列。第二项是为了使解接近初始值 $E$ 。上式的解为 $E^{(t+1)}=(1-\alpha) E+\alpha S E^{(t)}$ ，其中 $\alpha = 1/(1+\mu)$ 并且 $E^{(0)}=E$ ，迭代求解上式直至收敛得到 $\hat{E}$ 。