Question

1. 摘要：GNN是在图上学习的主要技术。然而，人们对 GNN在实践中取得成功的原因、以及它们是否是良好性能所必需的了解相对较少。在这里，论文表明：对于许多标准的 transductive node classification benchmark ，可以结合忽略图结构的浅层模型、以及利用标签结构中相关性的两个简单后处理步骤，从而超过或匹配 SOTA的 GNN的性能。这些后处理步骤利用了标签结构label structure 中的相关性：

   • 误差相关性error correlation ：它将训练数据中的残差residual error 扩散，从而纠正测试数据中的误差。
   • 预测相关性 prediction correlation：平滑了测试数据上的预测结果。

   论文的这个pipeline 称作 “矫正和平滑”Correct and Smooth:C&S。论文的方法在各种transductive 节点分类 benchmark 上都超过或接近了SOTA GNN 的性能，而参数规模小得多，运行速度也快了几个量级，并可以轻松scale 到大型图。例如在 OGB-Products 数据集上，论文的方法相比于著名的 GNN 模型减少了 137 倍参数、提高了 100 倍的训练时间，并且效果还更好。还可以将论文的技术整合到大型 GNN 模型中，从而获得适度的收益。

2. 引言：Graph Neural Network: GNN 目前在图数据领域取得巨大成功，并且经常排在 Open Graph Benchmark 等排行榜的榜首。通常 GNN 的方法论都围绕着创建比基本变体（如 GCN,GraphSAGE）更具有表达力的体系架构，如GAT、GIN 以及其它各种深度模型。然而，随着这些模型变得越来越复杂，理解它们的性能为什么提升是一个重大挑战，而且将它们扩展到大型数据集也很困难。

   相反，论文 《Combining label propagation and simple models out-performs graph neural networks》 研究了结合更简单的模型来获得收益。为此，论文提出了一个简单的 pipeline，它包含三个主要部分（如下图所示）：

   • base prediction：使用忽略图结构（如 MLP 或线性模型）的节点特征进行基础预测base prediction 。
   • correction step：将训练数据中的误差传播到整个图，从而校正基础预测。
   • smoothing：最后，对图上的预测进行平滑。

   这里第二步和第三步只是后处理post-processing，并且使用经典的标签传播 label propagation: LP 技术进行基于图的半监督学习。在该框架中，图结构不是用来学习参数的，而是作为一种后处理机制。这种简单性导致模型的参数数量减少，训练时间也减少了几个数量级，并且可以很容易地扩展到大型图。还可以将论文的思想与SOTA 的 GNN 结合起来，从而得到适度的性能提升。

   论文性能提升的一个主要来源是：直接使用标签进行预测。这个思想并不新鲜，早期的 diffusion-based 的图半监督学习算法（如spectral graph transducer、Gaussian random field model 和 label spreading ）都使用了这个思想。然而，这些方法的动机是对点云数据进行半监督学习，所以特征被用来构建图。然后，这些技术被用于仅从标签（即没有特征）来在关系数据上学习，而这种学习方式在 GNN 中基本上被忽略了。即，作者发现：即使是简单的标签传播（忽略了特征）在一些 benchmark上也有令人惊讶的表现。这启发了作者结合结合两个正交的预测能力：一个预测能力来自节点特征（忽略图形结构），一个预测能力来自在预测中直接使用已知标签。

   最近的研究将GNN与标签传播label propagation 以及马尔科夫随机场Markov Random field 联系起来，一些技术在特征中使用标签信息的临时融合 (如 UniMP )。然而，这些方法的训练成本仍然很高，而论文以两种可以理解的低成本方式使用标签传播：论文从一个无视图结构的模型开始进行廉价的 "基础预测"；之后，论文使用标签传播进行纠错，然后对最终预测进行平滑处理。

   这些后处理步骤是基于 error 和 label 在相连节点上是正相关的这一事实。假设相连节点之间的相似性是许多网络分析的中心，并对应于同质性 homophily 或同源混合assortative mixing。在半监督学习文献中，类似的假设是平滑性 smoothness 或聚类假设 cluster assumption 。论文在各种数据集上看到的标签传播的良好表现表明：这些相关性在普通 benchmark 上是成立的。

   总的来说，论文的方法表明：结合几个简单的思想，可以在模型大小（即参数数量）和训练时间方面，以很小的成本产生出色的transductive 节点分类性能。例如，在 OGB-Product benchmark 上，论文的表现超过了目前最著名的 GNN ，参数数量少了两个数量级，训练时间少了两个数量级。然而，论文的目标并不是说目前的 graph learning 方法很差或不合适。相反，论文的目标是强调提高 graph learning预测性能的更容易的方法，并更好地理解性能提高的来源。论文的主要发现是：将标签更直接地纳入学习算法中是关键。而通过将论文的思想与现有的 GNN 相结合，也可以看到改进，尽管这些改进是微小的。作者希望论文的方法能够激发新的思想，帮助其他的 graph learning 任务，如inductive节点分类、链接预测和图预测。

   下图为C&S 方法的概览。左图表示数据集中有两个类别：橙色和蓝色。

   • 首先使用 MLP 进行基础预测，从而忽略了图结构。这里假设所有节点都给出了相同的预测。
   • 然后从训练数据中传播误差来校正基础预测。
   • 最后校正后的预测通过标签传播得以平滑。

   

3. 相关工作：

   • Approximate Personalized Propagation of Neural Predictions:APPNP 框架是和我们工作最相关的，因为它们也是平滑了基础预测。但是，他们专注于将这个平滑处理集成到训练过程中，以便可以端到端地训练他们的模型。这种方式不仅显著增加计算成本，而且还使 APPNP 无法在推断时纳入标签信息。

     和 APPNP 相比，我们的框架可以产生更准确的预测、训练速度更快，并且更容易scale 到大规模图数据。

   • 我们的框架还补充了 Simplified Graph Convolution ，以及旨在提高可扩展性的算法。然而，我们的方法的主要重点是直接使用标签，而可扩展性是一个副产品。

   • 之前也有将 GCN和标签传播联系起来的工作：

     • 《Unifying graph convolutional neural networks and label propagation》 将标签传播作为预处理步骤从而用于 GNN的edge 加权，而我们将标签传播作为后处理步骤并避免使用 GNN 。
     • 《Residual correlation in graph neural network regression》 将具备标签传播的GNN 用于回归任务，我们的 error correction 步骤将他们的一些思想适配为分类的情况。

   • 最后，最近有几种方法将非线性纳入标签传播从而与 GNN 竞争并实现可扩展性，但这些方法专注于 low label rate setting ，并且没有纳入 feature learning 。

30.1 模型

1. 给定无向图$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ \mathcal G=(\mathcal V, \mathcal E) $ ，其中$\mathcal{V}=\{v_1,\cdots ,v_n\}$$ \mathcal V=\{v_1,\cdots,v_n\} $ 为节点集合，$\mathcal{E}=\{e_{i,j}\}$$ \mathcal E=\{e_{i,j}\} $ 为边集合。

   • 每个节点$v_i$$ v_i $ 关联一个特征向量${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^{d_f}$$ \mathbf{\vec x}_i\in \mathbb R^{d_f} $ ，所有节点的特征向量组成特征矩阵$\mathbf{X}\in {\mathbb{R}}^{n\times d_f}$$ \mathbf X\in \mathbb R^{n\times d_f} $ 。

   • 令$\mathbf{A}$$ \mathbf A $ 为邻接矩阵，$\mathbf{D}$$ \mathbf D $ 为degree度矩阵，$\mathbf{S}={\mathbf{D}}^{-1/2}\mathbf{A}{\mathbf{D}}^{-1/2}$$ \mathbf S=\mathbf D^{-1/2}\mathbf A\mathbf D^{-1/2} $ 为归一化的邻接矩阵。

   • 节点集合$\mathcal{V}$$ \mathcal V $ 划分为标记节点集合${\mathcal{V}}_L$$ \mathcal V_{L} $ 和未标记节点集合${\mathcal{V}}_U$$ \mathcal V_U $ ：

     $$\mathcal{V}={\mathcal{V}}_L\cup {\mathcal{V}}_U,\varphi ={\mathcal{V}}_L\cap {\mathcal{V}}_U$$
     • ${\mathcal{V}}_L$$ \mathcal V_L $ 中每个节点$v_i$$ v_i $ 都有一个标签$y_i\in \{1,2,\cdots ,c\}$$ y_i\in \{1,2,\cdots,c\} $ 。我们将标签$y_i$$ y_i $ 写作 one-hot 向量${\overrightarrow{\mathbf{y}}}_i\in {\mathbb{R}}^c$$ \mathbf{\vec y}_i\in \mathbb R^c $ 。
     • ${\mathcal{V}}_U$$ \mathcal V_U $ 中每个未标记节点$v_i$$ v_i $ ，我们将其one-hot 向量记作全零${\overrightarrow{\mathbf{y}}}_i=\overrightarrow{\mathbf{0}}$$ \mathbf{\vec y}_i = \mathbf{\vec 0} $ 。

     所有节点标签的 one-hot 向量组成标签矩阵$\mathbf{Y}\in {\mathbb{R}}^{n\times c}$$ \mathbf Y\in \mathbb R^{n \times c} $ 。

   • 进一步地，我们将标记节点集合${\mathcal{V}}_L$$ \mathcal V_{L} $ 划分为训练集${\mathcal{V}}_{L_t}$$ \mathcal V_{L_t} $ 和验证集${\mathcal{V}}_{L_v}$$ \mathcal V_{L_v} $ ：

     $${\mathcal{V}}_L={\mathcal{V}}_{L_t}\cup {\mathcal{V}}_{L_v},\varphi ={\mathcal{V}}_{L_t}\cap {\mathcal{V}}_{L_v}$$

   我们任务的目标是：给定$\mathcal{G},\mathbf{X},\mathbf{Y}$$ \mathcal G,\mathbf X, \mathbf Y $ 的条件下，预测${\mathcal{V}}_U$$ \mathcal V_U $ 中节点的标签。

2. C&S 方法从基于节点特征的、简单的 base predictor 开始，这个 predictor 不依赖于对图的任何学习。然后执行两种类型的标签传播：

   • 一种是通过对误差相关性进行建模来校正 base prediction，即误差平滑性。
   • 另一种是平滑最终预测，即标签平滑性。

   标签传播只是后处理步骤post-processing step ，因此我们的 pipeline 没有端到端的训练。

3. 在 C&S 方法中，图数据仅在这些后处理步骤和预处理步骤 pre-processing step 中使用（比如构建节点特征），和标准的 GNN 模型相比，这使得训练更快且可扩展性更好。

   图数据在预处理步骤中用于生成节点 embedding，从而增强特征$\mathbf{X}$$ \mathbf X $ 。

   此外， C&S 方法同时使用了标签传播和节点特征，这些互补的信号会产生更出色的预测结果。

   标签传播本身往往在没有特征的情况下也表现得很出色。

30.1.1 Base Predictor

1. 首先我们使用不依赖于图结构的、简单的base predictor 。具体而言，我们首先训练模型$\mathcal{F}(\cdot )$$ \mathcal F(\cdot) $ ，使得训练损失最小化：

   $$\underset{\mathrm{\Theta }}{min}\sum _{v_i\in {\mathcal{V}}_{L_t}}l(\mathcal{F}({\overrightarrow{\mathbf{x}}}_i;\mathrm{\Theta }),{\overrightarrow{\mathbf{y}}}_i)$$

   其中：

   • ${\overrightarrow{\mathbf{x}}}_i$$ \mathbf{\vec x}_i $ 为节点$v_i$$ v_i $ 的特征向量，${\overrightarrow{\mathbf{y}}}_i$$ \mathbf{\vec y}_i $ 为节点$v_i$$ v_i $ 标签的 one-hot 向量。
   • $l(\cdot ,\cdot )$$ l(\cdot,\cdot) $ 为损失函数（这里为交叉熵损失函数），$\mathcal{F}(\cdot )$$ \mathcal F(\cdot) $ 为模型，$\mathrm{\Theta }$$ \Theta $ 为模型参数。

   所有损失在标记的训练集${\mathcal{L}}_{L_t}$$ \mathcal L_{L_t} $ 上进行。

2. 本文选择$\mathcal{F}(\cdot )$$ \mathcal F(\cdot) $ 为线性模型，或者浅层的 multilayer perceptron: MLP 后接一个softmax 输出层。这种 base predictor 忽略图结构，因此可以避免 GNN 的可扩展问题。不过我们可以使用任何 base predictor，甚至包括 GNN 的 base predictor。

   但是，为了使得我们的 pipeline 简单且可扩展，我们仅使用线性模型或者 MLP 作为 base predictor 。

30.1.2 误差校正

1. 接下来我们通过融合标签信息来提高 base prediction 的准确率。核心思想是：我们预期基础预测的误差在图上正相关。换句话讲：节点$v_i$$ v_i $ 处的误差和相邻节点的误差相似。

   我们在图上传播spread 这种误差相似性。我们的方法在某种程度上受到残差传播的启发。在残差传播中，类似的概念用于节点回归任务。

   为此，我们定义一个误差矩阵$\mathbf{E}\in {\mathbb{R}}^{n\times c}$$ \mathbf E\in \mathbb R^{n\times c} $ 。令节点$v_i$$ v_i $ 的基础预测为向量${\overrightarrow{\mathbf{z}}}_i=\mathcal{F}({\overrightarrow{\mathbf{x}}}_i;\mathrm{\Theta })\in {\mathbb{R}}^c$$ \mathbf{\vec z}_i = \mathcal F(\mathbf{\vec x}_i;\Theta)\in \mathbb R^{ c} $ 。所有节点的基础预测向量组成基础预测矩阵$\mathbf{Z}\in {\mathbb{R}}^{n\times c}$$ \mathbf Z\in \mathbb R^{n\times c} $ 。则误差矩阵是训练数据集上的残差：

   $$\begin{array}{c}{\mathbf{E}}_{L_t}={\mathbf{Z}}_{L_t}-{\mathbf{Y}}_{L_t}\\ {\mathbf{E}}_{L_v}=\mathbf{0},{\mathbf{E}}_U=\mathbf{0}\end{array}$$

   其中：

   • ${\mathbf{E}}_{L_t}$$ \mathbf E_{L_t} $ 是在训练集${\mathcal{V}}_{L_t}$$ \mathcal V_{L_t} $ 上的误差矩阵，${\mathbf{E}}_{L_v}$$ \mathbf E_{L_v} $ 是在验证集${\mathcal{V}}_{L_v}$$ \mathcal V_{L_v} $ 上的误差矩阵，${\mathbf{E}}_U$$ \mathbf E_U $ 是在测试集${\mathcal{V}}_U$$ \mathcal V_U $ （也就是未标记节点）上的误差矩阵。
   • ${\mathbf{Z}}_{L_t}$$ \mathbf Z_{L_t} $ 是在训练集${\mathcal{V}}_{L_t}$$ \mathcal V_{L_t} $ 上的基础预测矩阵，${\mathbf{Y}}_{L_t}$$ \mathbf Y_{L_t} $ 是在训练集${\mathcal{V}}_{L_t}$$ \mathcal V_{L_t} $ 上的标签矩阵。仅当base predictor 做出完美预测时，误差矩阵才为零。

2. 现在我们已知误差矩阵$\mathbf{E}$$ \mathbf E $ （称作真实误差），现在我们希望学习一个平滑的误差$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ （称作平滑误差），这个平滑的误差满足两个条件：

   • $\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 和已知的真实误差$\mathbf{E}$$ \mathbf E $ 比较接近。

     应该是在训练集上和误差矩阵${\mathbf{E}}_{L_t}$$ \mathbf E_{L_t} $ 比较接近。

   • $\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 在图上应该是平滑的。即相连的节点具有相似的平滑误差。

   因此我们使用标签扩散技术来平滑误差，优化目标：

   $$\hat{\mathbf{E}}=\arg \underset{\mathbf{W}\in {\mathbb{R}}^{n\times c}}{min}\text{trace}({\mathbf{W}}^{\mathrm{\top }}(\mathbf{I}-\mathbf{S})\mathbf{W})+\mu ||\mathbf{W}-\mathbf{E}|{|}_F^2$$

   其中：

   • 第一项鼓励误差估计在图上的平滑性。这等价于：

     $$\sum _{j=1}^c{\overrightarrow{\mathbf{w}}}_j^{\mathrm{\top }}(\mathbf{I}-\mathbf{S}){\overrightarrow{\mathbf{w}}}_j$$

     ${\overrightarrow{\mathbf{w}}}_j\in \mathbb{R}$$ \mathbf{\vec w}_j\in \mathbb R $ 为$\mathbf{W}$$ \mathbf W $ 的第$j$$ j $ 列，代表每个节点在类别$c$$ c $ 上的平滑误差。

     $\mathbf{W}$$ \mathbf W $ 的解就是$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 。

   • 第二项使得最终的解接近已知的真实误差$\mathbf{E}$$ \mathbf E $ 。

   • $\mu$$ \mu $ 为超参数，用于平衡两个目标的重要性。

   这个目标函数可以通过迭代来求解：

   $${\mathbf{E}}^{(t+1)}=(1-\alpha )\mathbf{E}+\alpha \mathbf{S}{\mathbf{E}}^{(t)}$$

   其中：$\alpha =1/(1+\mu )$$ \alpha = 1/(1+\mu) $ ，以及${\mathbf{E}}^{(0)}=\mathbf{E}$$ \mathbf E^{(0)} = \mathbf E $ 。

   该迭代方程快速收敛到$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 。

   一旦得到平滑误差$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ ，我们将其添加到基础预测中，从而得到校正的预测：

   $${\mathbf{Z}}^{(r)}=\mathbf{Z}+\hat{\mathbf{E}}$$

   我们强调这是一种后处理技术，没有和base predictor 相结合的训练过程。

3. 在回归问题中，基于高斯假设，这种方式的误差传播被证明是正确的方法。但是对于分类问题，平滑误差$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 可能不在正确的范围内。

   考虑到：

   $${\Vert {\mathbf{E}}^{(t+1)}\Vert }_2\le (1-\alpha ){\Vert \mathbf{E}\Vert }_2+\alpha {\Vert \mathbf{S}\Vert }_2{\Vert {\mathbf{E}}^{(t)}\Vert }_2=(1-\alpha ){\Vert \mathbf{E}\Vert }_2+\alpha {\Vert {\mathbf{E}}^{(t)}\Vert }_2$$

   其中${\mathbf{E}}^{(0)}=\mathbf{E}$$ \mathbf E^{(0)} = \mathbf E $ 。则有：

   $${\Vert {\mathbf{E}}^{(t)}\Vert }_2\le {\Vert \mathbf{E}\Vert }_2$$

   因此，传播没有足够多的总质量total mass，所以传播无法完全纠正图中所有节点上的误差。并且，实验发现调整残差的比例实际上可以提供帮助。

   有鉴于此，我们提出了两种缩放残差的方法：

   • autoscale：直观地，我们希望将$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 中的误差大小缩放到和$\mathbf{E}$$ \mathbf E $ 中的误差大小差不多。

     由于我们仅知道训练节点上的真实误差，所以我们用训练节点上的平均误差来计算这个缩放比例。

     形式上，令${\overrightarrow{\mathbf{e}}}_j\in {\mathbb{R}}^c$$ \mathbf{\vec e}_j\in \mathbb R^c $ 为节点$v_j$$ v_j $ 的真实误差（它就是$\mathbf{E}$$ \mathbf E $ 的第$j$$ j $ 行）。定义：

     $$\sigma =\frac{1}{|{\mathcal{V}}_{L_t}|}\sum _{j\in {\mathcal{V}}_{L_t}}{\Vert {\overrightarrow{\mathbf{e}}}_j\Vert }_1$$

     其中$\sigma$$ \sigma $ 描述了真实误差$\mathbf{E}$$ \mathbf E $ 的平均大小。

     然后我们将未标记节点$v_i$$ v_i $ 的预测调整为：

     $${\overrightarrow{\mathbf{z}}}_i^{(r)}={\overrightarrow{\mathbf{z}}}_i+\sigma \times \frac{{\widehat{\overrightarrow{\mathbf{e}}}}_i}{{\Vert {\widehat{\overrightarrow{\mathbf{e}}}}_i\Vert }_1},v_i\in {\mathcal{V}}_U$$

     其中${\widehat{\overrightarrow{\mathbf{e}}}}_i\in {\mathbb{R}}^c$$ \hat{\mathbf{\vec e}}_i\in \mathbb R^c $ 为节点$v_i$$ v_i $ 的平滑误差（它就是$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 的第$i$$ i $ 行）。

   • FDiff-scale：另一种方法，我们可以选择一种扩散方法，该方法在标记节点上（包括训练集和验证集）保持真实误差${\mathbf{E}}_L$$ \mathbf E_L $ 。

     具体而言，我们在未标记节点上迭代平滑误差为：

     $${\mathbf{E}}_U^{(t+1)}={\left[{\mathbf{D}}^{-1}\mathbf{A}{\mathbf{E}}^{(t)}\right]}_U$$

     迭代过程中固定${\mathbf{E}}_L^{(t)}={\mathbf{E}}_L$$ \mathbf E_L^{(t)} = \mathbf E_L $ ，直到收敛到$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 。其中${\mathbf{E}}^{(0)}=\mathbf{E}$$ \mathbf E^{(0)} = \mathbf E $ 。

     直观地看，这将在标记节点${\mathcal{V}}_L$$ \mathcal V_L $ 上固定已知真实误差，而在未标记节点${\mathcal{V}}_U$$ \mathcal V_U $ 上对邻域的误差取平均，直到收敛。通过这种误差传播方式，${\mathbf{E}}^{(t)}$$ \mathbf E^{(t)} $ 中元素的最大值和最小值都不会超过${\mathbf{E}}_L$$ \mathbf E_L $ 中的值。

     另外，我们仍然发现学习缩放的超参数$s$$ s $ ，从而产生${\mathbf{Z}}^{(r)}=\mathbf{Z}+s\hat{\mathbf{E}}$$ \mathbf Z^{(r)} = \mathbf Z + s\hat{\mathbf E} $ 是有效的。

30.1.3 平滑预测

1. 现在我们得到每个节点$v_i$$ v_i $ 的得分向量 score vector${\overrightarrow{\mathbf{z}}}_i^{(r)}$$ \mathbf{\vec z}_i^{(r)} $ ，它就是${\mathbf{Z}}^{(r)}$$ \mathbf Z^{(r)} $ 的第$i$$ i $ 行。它是通过使用平滑误差$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ 对base predictor$\mathbf{Z}$$ \mathbf Z $ 进行校正而获得。

   为了做出最终预测，我们进一步对校正后的预测进行平滑处理。这样做的动机是：图中相邻的节点可能具有相似的标签，这在网络同质性homophily 或者分类混合assortative mixing 的属性下是可以预期的。

   因此，我们通过另一个标签传播来鼓励图上标签分布的平滑性。

   • 首先我们定义标签矩阵的最优猜测$\mathbf{G}\in {\mathbb{R}}^{n\times c}$$ \mathbf G\in \mathbb R^{n\times c} $ ，它将训练节点的猜测结果设置为真实标签，将验证节点和测试节点的猜测结果设置为校正后的预测：

     $${\mathbf{G}}_{L_t}={\mathbf{Y}}_{L_t},{\mathbf{G}}_{L_v,U}={\mathbf{Z}}_{L_v,U}^{(r)}$$

     我们也可以在验证节点上使用真实标签，这将在后面的实验中讨论。

   • 然后我们使用迭代公式：

     $${\mathbf{G}}^{(t+1)}=(1-\alpha )\mathbf{G}+\alpha \mathbf{S}{\mathbf{G}}^{(t)}$$

     其中${\mathbf{G}}^{(0)}=\mathbf{G}$$ \mathbf G^{(0)} = \mathbf G $ 。

     我们迭代上式直到收敛，从而得到最终预测$\hat{\mathbf{Y}}$$ \hat{\mathbf Y} $ 。

   • 最终测试节点$v_i\in {\mathcal{V}}_U$$ v_i\in \mathcal V_U $ 的分类预测为：

     $${\hat{y}}_i=\arg \underset{j\in \{1,2,\cdots ,c\}}{max}{\hat{Y}}_{i,j}$$

2. 和误差校正一样，这里的预测平滑是一个后处理步骤。这里的预测平滑在本质上类似于 APPNP，我们稍后将其进行比较。但是，APPNP 是端到端训练的，在最后一层 representation 上进行传播而不是 softmax，不使用标签，并且动机不同。

30.1.4 总结

1. 回顾我们的 pipeline：

   • 首先，我们从低成本的基础预测$\mathbf{Z}$$ \mathbf Z $ 开始，仅使用节点特征而不使用图结构。

   • 然后，我们通过在训练数据上传播已知真实误差来估计平滑误差$\hat{\mathbf{E}}$$ \hat{\mathbf E} $ ，从而得到误差校正的预测${\mathbf{Z}}^{(r)}=\mathbf{Z}+\hat{\mathbf{E}}$$ \mathbf Z^{(r)} = \mathbf Z+\hat{\mathbf E} $ 。

     将训练节点的真实误差传播到所有节点。注意，我们仅关心测试节点的误差，因为测试误差需要用于纠正测试节点的预测标签。而训练节点的标签是已知的，直接使用 ground-truth 。

   • 最后，我们通过另外一个标记传播步骤将校正预测与已知标签相结合，从而生成平滑的最终预测。

     标签传播时，训练节点传播的是真实标签，测试节点传播的是预测标签。

   我们将这个通用的 pipeline 称作 Correct and Smooth:C&S 。

   其核心就是两个平滑：误差平滑、输出平滑。

2. 在显示该 pipeline 在 transductive 节点分类上实现 SOTA 性能之前，我们简要介绍了另一种提高性能的简单方法：特征增强。

   深度学习的标志是：我们可以自动学习特征而不是手动的特征工程，但是GNN 仍然依靠输入的特征来执行预测。

   有很多方法可以从图拓扑中获取有用的特征来扩展原始节点的特征。在我们的 pipeline 中，我们使用来自矩阵${\mathbf{D}}_{\tau }^{-1/2}(\mathbf{A}+\frac{\tau }{n}\mathbf{I}){\mathbf{D}}_{\tau }^{-1/2}$$ \mathbf D_{\tau}^{-1/2}(\mathbf A + \frac{\tau}{n}\mathbf I)\mathbf D_{\tau}^{-1/2} $ 的前$k$$ k $ 个特征向量eigenvector 作为规范化的谱域嵌入regularized spectral embedding ，从而增强特征。这里：

   • $\tau$$ \tau $ 是规范化参数，设置为图的平均 degree 。
   • ${\mathbf{D}}_{\tau }$$ \mathbf D_\tau $ 为对角矩阵，其第$i$$ i $ 个对角线元素为$D_{i,i}+\tau$$ D_{i,i} + \tau $ ，$D_{i,i}$$ D_{i,i} $ 为节点$v_i$$ v_i $ 的 degree 。

   虽然底层的矩阵是稠密的，但是我们可以应用矩阵向量乘法，并使用迭代的特征向量求解器eigensolver 来在$O(|\mathcal{E}|)$$ O(|\mathcal E|) $ 时间内快速计算 embedding 。

   在论文的实验部分，作者在进行训练速度的比较时没有考虑计算 spectral embedding 的预处理时间，因此是不公平的比较。此外，计算 spectral embedding 对于大图而言是不可行的。

30.2 实验

1. 数据集：为证明我们方法的效果，我们使用了九个数据集，其中包括：

   • Open Graph Benchmark:OGB 中的 Arxiv 数据集和 Products 数据集：标签为论文类别或商品类别，特征从文本内容派生而来。
   • 三个经典引文网络 benchmark 数据集 Cora,Citeseer,Pubmed ：标签为论文类别，特征从文本内容派生而来。
   • 一个web graph 数据集 wikiCS：：标签为网页类别，特征从文本内容派生而来。
   • Rice University 的Facebook 社交网络数据集：类别为宿舍 dorm residence，特征为画像诸如性别、专业、班级等属性。
   • US County 数据：类别为 2016 年选举结果，特征为人口统计特征。
   • 欧洲研究所的 email 数据集：类别为成员的部门，没有特征。

   数据集的统计信息如下所示。另外我们还给出了我们方法相比较于 SOTA GNN：参数数量降低的比例、准确率的提升（绝对值）、以及我们方法的训练时间（秒）。结果表明：通过避免使用昂贵的 GNN，我们的方法需要较少的参数、更快的训练速度，并且通常得到更准确的结果。

   

2. 数据集拆分：

   • 在 Arxiv 数据集和 Products 数据集中，训练集、验证集、测试集的拆分由benchmark 本身来提供。
   • 对于 wikiCS 数据集的拆分，我们和 《A wikipedia-based benchmark for graph neural networks》 的拆分一致。
   • 对于 Rice, US County, Email 数据集，我们随机拆分为 40%/10%/50%。
   • 对于更小的引文网络数据集，我们使用 60%/20%/20% 的随机拆分。

   我们并没有采用很低的 label rate，这是为了改善数据集对于超参数的敏感性。

   在我们的所有实验中，不同拆分的预估准确率标准差在 1% 以内，并且通常不会改变我们的定性比较。

3. base predictor 和 baseline：

   • base predictor：

     • 我们使用线性模型Linear和 MLP 模型作为简单的 base predictor，其中输入特征是原始节点特征和 spectral embedding。
     • 我们还使用了仅使用原始特征的普通线性模型Plain Linear 作为base predictor 进行比较。

   • 变种：我们对比了仅使用 base predictor 的方法、使用 autoscale 和 FDiff-scale 的方法。

   • baseline：

     • 我们对标签传播 Label Propagation 模型进行比较。

     • 我们选择 GCN, SGC, APPNP 作为对比的 GNN 模型。对于 GCN 模型，我们将输入到每一层、以及从每一层到输出层都添加了额外的残差链接 residual connection，从而产生了更好的效果。GCN 的层数、隐层维度和 MLP 相同。

       注意：这里的 GCN 一种 GCN 风格的模型，而不是原始的、Kipf&Welling 提出的模型。

   • 最后，我们还包含了几个 state-of-the-art 的 baseline：

     • 对于 Arxiv 和 Product 数据集，我们使用 UniMP 模型。该模型在 2020-10-01 位于 OGB 排行榜的榜首。
     • 对于 Cora,Citeseer,Pubmed 数据集，我们复用《 Simple and deep graph convolutional networks》 论文给出的最好的结果。
     • 对于 Email 和 US County 数据集，我们使用 GCNII 模型。
     • 对于 Rice31，我们使用带spectral embedding 的 GCN、以及带 node2vec embedding 的 GCN 。这是我们发现的、效果最好的 GNN-based 模型。
     • 对于 WikiCS，我们使用 APPNP 。

   对于所有模型，我们通过验证集来选择一组固定的超参数。

30.2.1 仅训练标签

1. 在平滑预测阶段，我们仅在训练节点上使用真实标签，即：

   $${\mathbf{G}}_{L_t}={\mathbf{Y}}_{L_t},{\mathbf{G}}_{L_v,U}={\mathbf{Z}}_{L_v,U}^{(r)}$$

   下表给出了实验结果，其中 Base Prediction 表示仅使用基础预测而没有任何后处理；Autoscale 和 FDiff-scale 表示使用不同的平滑预测缩放方式。

   我们重点介绍一些重要发现：

   • 首先，在我们模型中C&S 后处理带来可观的收益。例如在 Product 数据集上，应用了后处理之后 MLP base prediction 的测试准确率从 63% 提升到 84%。

   • 其次，在很多case 中：

     • 具有 C&S 的 Plain Linear 模型也足以战胜常规的 GCN 模型。
     • 标签传播LP（一种没有可训练参数的方法）通常与 GCN 具有相当的竞争力。

     鉴于 GCN 的主要动机是解决连接的节点可能没有相似的标签的事实，这一点令人惊讶。我们的结果表明：通过简单地使用特征从而将相关性融合到图中，这通常是一个更好的主意。

   • 第三，我们模型的变体在 Product,Cora,Email,Rice31, US County 上的表现优于 SOTA。在其它数据集上，我们表现最好的模型和 SOTA 之间没有太大差异。

   

2. 为了了解直接使用 ground truth 标签有多大帮助，我们还尝试了没有标签的 C&S 版本，其中不执行C&S步骤，而是使用《Learning with local and global consistency》 中的方法来平滑 base predictor 的输出，我们称这个版本为 Basic Model。即：

   • 标签信息仅用于base predictor 的训练。
   • 图结构信息仅用于 base predictor 预测结果的平滑。

   这里面缺少了误差的平滑，仅保留预测结果的平滑。

   结果如下表所示。我们看到：

   • Linear 和 MLP 的 base predictor 通常可以超过 GCN 的性能。这些结果再次表明输出平滑非常重要，而 GCN 的原始动机具有误导性。相反，我们假设 GCN 可以通过平滑图上的输出来获得性能提升。这与 《Simplifying graph convolutional networks》 的观察类似。
   • 另外，我们也看到下图中这个 Basic Model 和上图中使用 C&S 的方法之间仍然存在性能差异。

   Plain Linear 缺少了节点的 spectral embedding 特征。

   

3. 下表给出了仅使用误差校正，但是未使用平滑预测的实验结果。

   实验结果表明：误差校正、平滑预测这两个标签传播步骤对于最终效果提升都是至关重要的。

   

30.2.2 更多标签

1. 可以使用验证标签是我们方法的优势，这甚至可以进一步提升我们框架的性能。

   在平滑预测阶段，我们在训练节点和验证节点上使用真实标签，即：

   $${\mathbf{G}}_L={\mathbf{Y}}_L,{\mathbf{G}}_U={\mathbf{Z}}_U^{(r)}$$

   注意：我们不使用验证标签来训练 base predictor 模型，而是用于选择 base predictor 的超参数。

   通过引入验证集标签，更多的节点被指定了 ground-truth，因此网络中传播的信息量更大。

   下表给出了实验结果（另外，数据集统计信息表给出了相对于 SOTA 的收益）。应用了验证标签之后，我们的最佳模型在 9 个数据集中的 7 个中超越了 SOTA，并且具有可观的收益。

   可以看到：

   • 融合验证标签的能力是我们方法的优势。而 GNN 并没有这种优势，因为它们通常依靠早停来防止过拟合，可能并不总是从更多数据中受益（比如，在标签分布偏移 shift 的情况下），并且不直接使用标签。
   • 对于很多数据集上的 transductive 节点分类，要获得良好的性能，实际上并不需要大型的而且昂贵的GNN 模型。
   • 将经典的标签传播思想和简单的 base predictor 相结合，在这些任务上的性能超越了 GNN 模型。

   

30.2.3 改善 GNN

1. 和 GNN 以及其它 SOTA 解决方案相比，我们的 C&S 框架通常需要更少的参数。例如我们在下图绘制了 Product 数据中，不同模型的参数和性能的关系。

   

   我们的方法不仅使用更少的参数，但真正的收益在于训练时间更快。和具有可比准确率的模型相比，我们的模型的训练时间要快几个量级。因为我们的 base prediction 不需要使用图结构。例如：

   • 在 Arxiv 数据集上，我们的 MLP+C&S 模型和 GCN + label 的模型具有相似的参数数量。但是我们的模型训练中，每个 epoch 的训练速度要快 7倍，并且收敛速度更快。
   • 在 Products 数据集上，和 SOTA 相比，我们的 linear base predictor +C&S 模型具有更高的准确率，训练速度提高了 100倍、参数数量减少了 137 倍。
   • 我们还在更大的数据集 papers 100M 上评估了我们的方法。这里我们以 Linear + C&S 模型，可以达到 65.33% 的准确率，比 SOTA 的 63.29% 更高。

   这种比较是不公平的比较，因此 C&S 方法需要节点的 spectral embedding 作为输入，这通常是非常昂贵的且通常无法扩展到大型图。一种解决办法是用 DeepWalk 来得到 node emebdding，但是这种预处理也非常耗时。

   如果没有 spectral embedding （即，Plain Linear），则 C&S 的效果出现巨大的下降。而且这种依赖于人工特征工程（虽然是通过 graph embedding 自动计算得到）的方式不太鼓励，因为强烈依赖于经验。

2. 一般而言，我们的 pipeline 还可以用于改善 GNN 的性能。我们将误差校正、平滑预测应用到了更复杂的 base predictor 上，诸如 GCNII 和 GAT。

   实验结果如下表所示。这提升了我们在某些数据集上的结果，包括在 Arxiv 上击败了 SOTA。但是，有时性能提升只是很小的，这表明大型模型可能正在捕获与我们简单的 C&S 框架相同的信号。

   

30.2.4 可视化

1. 为了帮助理解 C&S 框架的性能，我们在 US County 数据集上的预测可视化。

   • (a)：US County 可视化，其中 embedding 由 GraphViz 提供，颜色对应于类别标签。总体而言是经纬度坐标的压缩旋转版本。
   • (b)：和 (a) 部分对应的pannel，显示 C&S 在哪个阶段做出了正确的预测。
   • (c)：显示了相同 pannel 上 GNN 做出的预测。

   如预期的那样，残差相关性倾向于校正节点，其中临县为这些节点提供了相关信息。例如：

   • 我们看到 base prediction 中的很多误差已被残差相关性校正（图 3b 的左图和右图）。在这些情况下，对应于德克萨斯州和夏威夷州的部分地区，县的人口统计特征和全国其它地区相比是异常的，这误导了 Linear 模型和 GCN 模型。而来自相邻县的残差相关性能够校正预测。
   • 我们还看到最终的预测相关性使得预测变得平滑，如图 3b 的中间部分所示，这使得可以基于邻居的正确分类来校正误差。