知识蒸馏论文精选——《Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation》

GLNN：无图神经网络

《Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation》 2022 ICLR

作者是Shichang Zhang、Yozen Liu、Yizhou Sun和Neil Shah

代码和论文地址见文末

摘要

图神经网络( Graph Neural Networks，GNNs )是图机器学习的热门，在广泛的节点分类任务上表现出了很好的效果。然而，由于数据依赖性带来的可扩展性挑战，它们在行业中的实际部署中并不受欢迎。也就是说，GNN推理依赖于距离目标节点多跳的邻居节点，而抓取这些邻居节点会给时延受限应用带来负担 。现有的推理加速方法，如剪枝和量化，可以通过减少乘累加( Multiplication-and-ACcumulation，MAC )操作来加速GNNs，但由于没有解决数据依赖问题，这些改进是有限的。相反，多层感知器( MLPs )没有图依赖性，推断速度比GNNs快得多，尽管它们对节点分类的总体精度低于GNNs 。基于这些互补的优势和劣势， 我们通过知识蒸馏( KD )将GNNs和MLPs整合在一起 。我们的工作表明，使用GNN KD可以大幅度地提高MLPs的性能。我们称蒸馏后的MLPs为无图神经网络( Graph-less Neural Networks，GLNNs )，因为它们没有推理图依赖 。我们发现，具有竞争精度的GLNNs比GNNs推理速度快146 × -273 ×，比其他加速方法推理速度快14 × -27 ×。在包含7个数据集的直推式和归纳式预测的生产环境下，GLNN的准确率比独立的MLPs平均提高了12.36 %，并在6 / 7的数据集上与GNN相匹配。综合分析表明，GLNNs何时以及为何能达到与GNNs相当的精度，并建议GLNN作为时延受限应用的简便选择。

1、引言

图神经网络( Graph Neural Networks，GNNs )最近成为图机器学习( Graph Machine Learning，GML )的研究热点，在联合采购图上的产品预测和引文图上的论文类别预测等节点分类任务( Kipf &韦林, 2016 ; Hamilton et al , 2017 ; Veli ckovi ’ c et al , 2017)上取得了很好的效果。然而，对于大规模的工业应用，MLPs仍然是主要的工作，尽管有共同的(隐式)底层图形和GML形式的适用性。造成这种学术-工业差距的原因之一是GNNs (张杰等, 2020 ; Jia et al , 2020)中数据依赖带来的可扩展性和部署方面的挑战，这使得GNNs难以部署到需要快速推理的时延受限应用中。

图依赖导致的邻域获取是GNN延迟的主要来源之一 。对目标节点的推理需要获取多个邻居节点的拓扑和特征，特别是在小世界图(第4节详细讨论)上。常见的推理加速技术如剪枝( Zhou et al , 2021)和量化( Tailor et al . , 2021 ; Zhao et al , 2020)可以通过减少乘累加( MAC )操作在一定程度上加速GNNs。

然而，由于没有解决图依赖问题，它们的改进是有限的。与GNNs不同，MLPs对图数据没有依赖性，并且比GNNs更容易部署 。此外，MLPs还具有规避关系数据( Wei et al . , 2020)在线预测过程中经常发生的冷启动问题的辅助优势，即即使在新相遇节点的邻居信息不能立即获得的情况下，MLPs也可以合理地进行推断 。另一方面，这种图依赖的缺乏通常会损害关系学习任务，限制了MLP在GML任务上的性能与GNNs相比。由此我们提出疑问：我们能否在两个世界之间架起桥梁，同时享受MLPs的低延迟、无依赖特性和GNNs的图上下文感知特性?

目前的工作

我们的关键发现是，在不损失显著性能的情况下，可以从GNNs提取知识到MLPs，但大大减少了节点分类的推理时间 。知识蒸馏( KD )可以离线进行，并与模型训练相耦合。换句话说，我们可以将相当多的工作从时延受限推断步骤(以毫秒为单位的时间减少带来了巨大的差异)转移到不太敏感的训练步骤(以小时或天为单位的时间成本往往是可以容忍的)。我们称这种方法为无图神经网络( Graph-less Neural Network，GLNN ) 。具体来说， GLNN是一个从GNN教师到学生MLP的涉及KD的建模范式；生成的GLNN是通过KD优化的MLP ，因此它在训练中享有图上下文感知的好处，但在推理中没有图依赖。在速度方面，GLNNs具有出色的效率，比GNNs快146 × -273 ×，比其他推理加速方法快14 × -27 ×。在性能方面，在包含7个数据集的直推式和归纳式预测的生产环境下，GLNN的准确率比MLPs平均提高了12.36 %，并在6 / 7的数据集上与GNNs相匹配。我们全面地研究了GLNNs何时以及为何能够像GNNs那样取得具有竞争力的结果。我们的分析表明，实现这种高性能的关键因素是大的MLP尺寸和节点特征与标签之间的高互信息。我们的观察结果与最近在视觉和语言方面的结果一致，这表明足够大的(或稍作修改)MLPs可以取得与CNNs和Transformers ( Liu et al , 2021 ; Tolstikhin et al , 2021 ; Melas-Kyriazi , 2021 ;图夫龙et al , 2021 ; Ding et al , 2021 )相似的结果。

我们的核心贡献如下：

• 我们提出了GLNN，它通过KD到MLP消除了GNN推理中的邻居提取延迟。
• 我们展示了GLNN具有与GNN竞争的性能，同时拥有比香草GNN快146 × -273 ×的推理速度和比其他推理加速方法快14 × -27 ×的推理速度。
• 我们通过考察GLNN在不同设置下的性能，它们作为正则化器的工作方式，它们的归纳偏差，表现力和局限性来全面研究GLNN的性质。

2、相关工作

图神经网络

早期的GNNs将卷积网络泛化为图( Bruna et al . , 2014 ; Defferrard et al , 2017)，后来通过GCN ( Kipf &韦林, 2016)简化为消息传输神经网络( MPNN )。之后的大多数GNNs可以统称为MPNNs。例如，GAT使用注意力( Veli ckovi ’ c等, 2017)，PPNP使用个性化PageRank (克利茨佩拉et al , 2019)，GCNII和DeeperGCN使用残差连接和密集连接( Chen et al . , 2020 ; Li et al . , 2019)。

推理加速

推理加速通过硬件改进和算法改进剪枝、量化提出。对于GNNs，研究了剪枝和量化GNN参数 。这些方法在一定程度上加快了GNN的推理速度，但并没有消除邻居获取延迟。相比之下，我们的交叉模型KD解决了这个问题。同时，Graph - MLP也试图通过训练一个带有邻居对比损失的MLP来绕过GNN的邻居获取( Hu et al . , 2021)，但它只考虑了直推式，而没有考虑更实际的归纳式设置。一些采样工作专注于加速GNN训练(邹薇等, 2019 ; Chen et al . , 2018)，这与我们的推断加速目标是相辅相成的。

GNN蒸馏

现有的GNN KD工作试图将大的GNN提取到更小的GNN中。LSP ( Yang et al , 2021b)和TinyGNN ( Yan et al , 2020)在保留局部信息的同时进行KD。他们的学生是参数较少但不一定层数较少的GNN。因此，这两种设计仍然需要延迟诱导抓取。GFKD ( Deng & Zhang , 2021)通过图生成进行图级KD。在GFKD中，数据实例是独立的图，而我们关注的是图中的依赖节点。Graph SAIL ( Xu et al , 2020)使用KD学习学生在新数据上工作良好，同时保留在旧数据上的性能。CPF ( Yang et al , 2021a)结合了KD和标签传播( LP )。CPF中的学生不是一个GNN，但由于使用了LP，它仍然严重依赖于图。

3、预备知识

注意

对于 GML (图机器学习) 任务，输入通常是一个图及其节点特征，我们记为 G = ( V、E)，其中 V 代表所有节点， E 代表所有边。令 N 表示节点总数.我们用 X∈RN×D 表示节点特征，行 xv 表示节点 v∈V 的 D 维特征。我们用邻接矩阵 A 表示边，用 Au 表示边，如果边 ( u , v) ∈ E，则 v = 1，否则为 0。对于 GML 最重要的应用之一的节点分类，其预测目标为 Y∈RN×K，其中行 yv 为节点 v 的 K 维的 one-hot 向量。对于给定的 G，通常会标记一小部分节点，我们用上标 L 来标记 。VL，XL 和 YL。大多数节点将是未标记的，我们使用上标 U ，即。VU，XU 和 YU 。

图神经网络

大多数 GNN 适用于消息传递框架，其中每个节点 v 的表示 hv 在每层通过收集其邻居的消息来迭代更新，记为 N ( v )。对于第 l 层，h(l)v 由上一层表示 h(l-1)u ( h(0)u = xu ) 通过聚集操作 AGGR 和 UPDATE 操作得到

4、 动机

由于图依赖的存在，GNNs具有相当大的推理延迟。多一个GNN层就意味着多获取一跳的邻居节点 。在平均度为 R 的图上推断一个具有 L 层 GNN 的节点需要 O(RL) 个抓取。对于真实世界的图，R 可以很大，例如 Twitter ( Ching et al . , 2015)中的 208。此外，由于取层必须顺序进行，总延迟随着L的增加而迅速爆炸 。

图1 ：GNNs的取指次数和推理时间都比MLPs多一个数量级，并且随着层数的增加呈指数增长。

左：需要为两个GNN层提取邻居。

中：用于推理的取指总数。

右：总推断时间。( OGB产品上10个随机节点的归纳推理( Hu et al , 2020) )。

图 1 显示了每个 GNN 层添加的依赖关系和推理时间的指数爆炸 。相比之下，MLP 推理时间要小得多，且呈线性增长 。这一显著的差距极大地促进了 MLPs 相对于 GNNs在工业应用中的实用性。

节点获取延迟的加剧有两个因素：首先，更新的GNN架构越来越深 ，从64层( Chen et al , 2020)到甚至1001层( Li et al , 2021)。其次，工业规模的图往往过于庞大 ，不适合存入单机( Jin et al , 2022)的内存中，需要将图分片出主存。例如，截至2015年3月，Twitter每月有288M活跃用户(节点)和60B追随者(边)。截至2014年12月00日，Facebook有1.39 B活跃用户，超过400B条边。即使以稀疏矩阵友好的格式(通常为COO或CSR)存储时，这些图也是TB级的，并且还在不断增长。远离内存存储会导致更慢的邻居获取。

另一方面，MLPs 缺乏利用图拓扑的手段，这损害了它们对节点分类的性能 。例如，Graph SAGE在Products上的测试精度为78.61，而同等大小的MLP的测试精度为62.47。尽管如此，最近在视觉和语言方面的结果表明，大型的(或稍作修改) MLPs可以达到与CNNs和Transformers ( Liu et al . , 2021)类似的结果。因此，我们也提出了一个问题：能否将 GNNs 和 MLPs 的优势结合起来，以获得高精度和低延迟的模型 ? 这促使我们从GNNs到MLPs进行跨模型KD。

5、无图神经网络

我们引入GLNN，并回答其性质的探索问题 ：

1 ) GLNN如何与MLP和GNN进行比较?

2 ) GLNNs在直推式和感应式环境下都能正常工作?

3 ) GLNNs与其他推理加速方法的比较?

4 ) GLNNs如何从KD中获益?

5 ) GLNNs是否具有足够的模型表达能力?

6 ) GLNNs何时失效?

5.1 GLNN框架

GLNN的思想是直接的，但正如我们将看到的那样，是非常有效的。简而言之，我们通过教师GNN 的 KD训练了一个"增强"的 MLP 。KD 在 Hinton等人( 2015 )中被介绍，其中知识从一个繁琐的教师转移到一个简单的学生。在我们的例子中，我们用一个教师 GNN 为每个节点 v 生成软目标 zv。然后我们训练一个同时带有真实标签 yv 和 zv 的学生 MLP。目标函数为方程1，λ为权重参数，Llabel 为 yv 和学生预测之间的交叉熵( yv，L Teacher为KL散度)。

KD 之后的模型，即。GLNN 本质上是一种 MLP 。因此，GLNNs 在推理过程中没有图依赖，并且与 MLPs 一样快速。另一方面，通过离线 KD ，优化 GLNN 参数，与 GNN 一样进行预测和泛化，具有推理速度快、部署方便等优点。

图2 ：GLNN框架：在离线训练中，针对软目标，在图上应用一个经过训练的GNN教师。然后，在软目标引导的节点特征上训练一个学生MLP。蒸馏的MLP，现在是GLNN，被部署用于在线预测。由于消除了图依赖进行推理，GLNNs比GNNs推理速度快得多，因此被命名为"无图神经网络" 。

在图2中，我们展示了 GLNNs 的离线 KD 和在线推理步骤。

5.2 实验设置

数据集

我们考虑了CPF论文( Yang et al , 2021a)中使用的所有五个数据集 ，即。Cora、Citeseer、Pubmed、A - Computer、A - Photo。为了充分评估我们的方法，我们还包括两个更大的OGB数据集( Hu et al , 2020)。Arxiv和产品。

模型架构

为了得到一致的结果，我们使用GCN聚合的Graph SAGE ( Hamilton等, 2017)作为教师 。我们在第6节对GCN ( Kipf &韦林, 2016)、GAT ( Veli ckovi ’ c等, 2017)和APPNP (克利茨佩拉等, 2019)等其他GNN教师进行消融研究。

评估协议

对于本节的所有实验，我们报告了不同随机种子下10次试验的平均值和标准差 。模型性能以准确性来衡量，并在测试数据上报告结果，使用验证数据选择最佳模型。

直推式与归纳式

给定G，X 和 Y L，我们考虑两种情况下的节点分类：直推式( trans )和归纳式( ind ) 。对于ind，我们只给出了一些用于归纳评价的试验数据。我们首先选取归纳节点，它将VU划分为不相交的归纳子集和观察子集，即.。然后保留和与相连的所有边，得到两个不相交的图，没有共享的节点和边。节点特征和标签被划分成三个互不相交的集合，即。和。具体来说，这两个设置的输入/输出都变成了：

tran ：在G、X、YL上训练；对( XU , YU)评价；KD对 v∈V 使用zv。

在直推式设置中，模型的训练和评估都是在同一个图上进行的。 具体来说，训练时使用图中的一部分节点（通常是带有标签的节点）来训练模型，而评估时则在图的剩余未标记节点上进行。在这种设置中，整个图的结构和所有节点的特征在训练阶段都是可见的，包括验证和测试节点。

ind ：在Gobs，XL，XUobs 和 YL上进行训练；( XUind , YUind)评价；对于 ，KD使用 zv。

与直推式不同，归纳式设置更关注模型对全新、未见过节点的泛化能力。在这种设置中，模型在训练时只能访问一部分图（观察到的子图），而在评估时则需要对另一部分未见过的节点（归纳子图）做出预测 。这些未见过的节点及其连接的边在训练期间被保留，并仅用于最终的归纳评估。

总结：tran是训练阶段所有的图都能看见。ind是训练阶段只能看到一部分图，另一部分图看不见，评估阶段才能看见 。

注意，对于 tran，图中的所有节点包括验证和测试节点都用来生成 z。关于这一选择以及其他实验细节的讨论见附录A 。

5.3 Glnns与 Mlps和Gnns 的比较?

我们首先将GLNNs与具有相同层数和隐藏维数的MLPs和GNNs进行比较 。我们首先考虑标准的直推设定，因此我们在表 1 中的结果与Yang et al ( 2021a )和Hu et al ( 2020 )等文献中的结果直接可比。

表1 ：在直推式设置下，GLNNs 在7个数据集中的5个数据集上的表现优于 MLPs，并与GNNs相匹配。∆MLP ( ∆GNN )表示GLNN和训练好的MLP ( GNN )之间的差异。结果显示了(越高越好)的准确性；∆GNN≥0 表示 GLNN 优于 GNN。

如表1所示，所有 GLNNs 的性能都比 MLPs 有较大的提升。在较小的数据集(前5行)上，GLNNs 甚至可以超过教师 GNNs。也就是说，对于每个任务，在相同的参数预算下，存在一组具有 GNN 竞争性能(详细讨论见第5.6和5.7节)的 MLP 参数。对于较大的 OGB 数据集(最后2行)，GLNN的性能在 MLPs 上有所提升，但仍差于教师 GNN。

表2 ：扩展的 GLNNs 与 GNNs 在 OGB 数据集上的性能相匹配。对于 Arxiv，我们使用 MLPw4 ( GLNNw4 )。对于我们的项目，我们使用 MLPw8 ( GLNNw8 ) 。

然而，正如我们在表2中所示，这种差距可以通过将MLP 尺寸增加到 MLP wi 来缓解。

图3 ：扩展的 MLPs ( GLNNs ) 可以匹配GNN的精度，但推断速度显著加快。表格设置与图1相同。左：MLPs的推理时间 vs 针对不同模型大小的 GNN ( SAGE ) 。右：模型精度 vs 推断时间 。注：时间轴是对数刻度的。

在图3 (右)中，我们可视化了不同模型规模下预测精度和模型推断时间之间的权衡关系 。我们发现，随着 GLNN 规模的逐渐增大，其性能逐渐接近于 SAGE。另一方面，当我们减少 SAGE 的层数时，准确率迅速下降到比 GLNNs 更差。关于增加 MLP 尺寸的原理的详细讨论见附录B。

5.4 Glnns在直推式与归纳式两种设定下都能正常工作?

虽然直推式是节点分类的常用研究设置，但它不包含对未见节点的预测。因此，这可能不是评估已部署模型的最佳方法，它必须经常生成新数据点的预测，并可靠地保持对旧数据点的性能。因此，为了更好地理解 GLNN 的有效性，我们还考虑了它们在包含直推式和归纳式预测的现实生产环境下的表现。

为了对一个模型进行归纳评估，我们从训练中取出一些测试节点组成一个归纳集，即。在生产中，一个模型可能会被周期性地重新训练，例如每周一次。VUind中的抵制节点表示两次训练之间进入图中的新节点。与VUobs相比，VUind通常较小。如Graham ( 2012 )中对增长最快的科技创业企业的估计一样，为5 - 7 %。

在我们的案例中，为了减少随机性和更好地评估可推广性，我们使用包含 20 % 测试数据的 V Uind。我们还对包含其他 80 % 测试数据的 V Uobs 进行了评估，这代表了对观察到的未标记节点的标准直推预测，因为在实际情况中，推断通常是在现有节点上重新进行的。我们在表 3 中报告了这两个结果和一个插值的生产( prod )结果 。实验结果更加清晰地展示了模型的泛化能力以及在生产中的准确性。除 20 ~ 80 外不同感应分裂率的消融研究见第6节 。

在表 3 中，我们看到 GLNNs 对于归纳预测仍然可以比 MLP 提高很大的边际。在6 / 7数据集上，GLNN prod 性能与 GNN 相当，支持将 GLNN 部署为速度更快的模型，而没有或仅有轻微的性能损失。在 Arxiv 数据集上，GLNN 的性能显著低于 GNN - -我们假设这是由于 Arxiv 具有特别具有挑战性的数据分割，导致测试节点和训练节点之间的分布偏移，这对于 GLNNs 来说是很难捕获的，而不像 GNNs 那样利用邻居信息 。然而，我们注意到 GLNN 的性能比 MLP 有了显著的提高。

5.5 Glnns与其他推理加速方法的比较?

常用的推理加速技术包括剪枝和量化 。这些方法可以减少模型参数和乘法累加( Multiplication-and-ACcumulation，MAC )操作。尽管如此，它们并没有消除邻居获取延迟 。因此，它们在GNNs上的速度增益不如在NNs上显著。对于GNNs，邻居采样也被用来减少抓取延迟。

表4 ：虽然其他推理加速方法加速了SAGE，但它们比GLNNs慢得多 。数字( ms )是在随机选择的10个节点上的归纳推理时间。

表4给出了从 FP32 到 INT8 ( QSAGE ) 的 vanilla SAGE, quantized SAGE 、剪枝50 %权重的SAGE ( PSAGE )、fan-out 15的推断近邻采样和 GLNN 的显式速度比较。与图1相同的设置下，我们看到 GLNN 的速度要快得多。

另外两种被认为是推理加速的方法是GNN - to - GNN KD，如 TinyGNN ( Yan et al , 2020) 和 Graph Augmented-MLPs ( GA-MLPs )，如 SGC ( Wu et al . , 2019) 或 SIGN ( Frasca et al , 2020)。GNN-to-GNN KD 的推理速度可能比与学生具有相同 i 的 GNN - Li 慢，因为通常会有一些额外的开销，如 TinyGNN 中的 Peer - Aware Module ( PAM )。GA-MLPs 的预算扩展了节点特征，并将 MLPs 应用到其中。在预计算的情况下，它们的推理时间与保维增广( SGC )的 MLPs 相同，与增广涉及级联( SIGN )的增广 MLPwi 相同。因此，对于这两种方法，将 GLNN 与 GNN - Li 和 MLPwi 进行比较是足够的，如图3 (左)所示。我们看到 GNN - Lis 比 MLPs 慢得多。对于 GA - MLPs，由于无法对归纳节点进行完全的预计算，GA - MLPs 仍然需要获取邻居节点。这使得它们在归纳场景下的速度远低于 MLPwi，甚至低于Zhou等( 2021 )提出的剪枝 GNN 和 TinyGNN。

5.6 Glnn如何从蒸馏中获益?

我们发现 GNNs 在节点分类任务上明显优于 MLPs 。但是，有了KD，GLNNs 往往可以与 GNNs竞争。这说明存在合适的 MLP 参数，能够很好地逼近从节点特征到标签的理想预测函数 。然而，这些参数很难通过标准的随机梯度下降来学习。我们假设 KD 通过正则化和转移诱导偏差来帮助发现它们。

首先，我们说明KD可以帮助规则化学生模型 。

图4 ：在 CPF 数据集上的损失曲线表明 GLNN 蒸馏有助于规则化训练 。这里 GLNN 的训练损失是在硬标签上的，只对应于方程1中的第一项。

从图4中直接训练的MLP和GLNN的损失曲线可以看出，MLP的训练和验证损失之间的差距明显大于GLNN，并且MLP表现出明显的 过拟合趋势。其次，我们分析了使GNNs具有强大节点分类能力的归纳偏差，这表明节点推断应该受到图拓扑结构的影响。而MLPs具有较小的诱导偏倚。Transformers ( Vaswani et al , 2017) 和 MLPs 之间也存在类似的差异。Liu et al . ( 2021 )的研究表明，变压器中的电感偏置可以通过在大型MLP上的简单栅极来缓解。对于节点分类，我们假设KD有助于缓解归纳偏差，因此GLNNs可以有竞争力地执行。由于归纳偏差，GNN教师的软标签受到图拓扑结构的严重影响。它们在类上保持非零概率，而不是标签提供的基本真值，这有助于学生学习补充 MLPs 中缺失的归纳偏差。为了定量地评估这个假设，我们在方程2中定义了割损失 Lcut∈[ 0、1 ] 来衡量模型预测和图拓扑(详见附录C)之间的一致性：

其中 \hat{Y}∈[ 0、1 ]N×K是模型输出的软分类概率，A和D是邻接矩阵和度矩阵。当 Lcut接近于 1 时，表示预测结果与图的拓扑结构非常一致。在我们的实验中，我们观察到 SAGE 在5个 CPF 数据集上的平均 Lcut 为0.9221，具有较高的一致性。同样对 Mlps 的 Lcut 仅为0.7644，而对 Glnns 的 Lcut 为0.8986。这说明GLNN的预测结果确实得益于教师输出 ( 附录C中的 Lcut 值全表 ) 中包含的图拓扑知识。

5.7 Glnns具有足够的模型表达能力?

直觉上，邻居信息的加入使得 GNNs 在对节点进行分类时比 MLPs 更加强大。因此，关于 KD 从 GNNs 到 MLPs 的一个自然问题是，MLPs 是否具有足够的表达能力来表示图数据以及 GNNs。最近的许多工作研究了 GNN 模型的表达能力( Xu et al . , 2018 ; Chen et al . , 2021)。后者分析了用于节点分类的 GNNs 和 GA - MLPs，并将表达能力表征为模型(附录D中的形式化定义)诱导的根图的等价类数。结论是 GNNs 比 GA - MLPs 更强大，但在大多数真实世界情况下，它们的表达能力是不可区分的。

我们采用Chen et al ( 2021 )的分析框架，在附录D中展示了由 GNNs 和 MLPs 诱导的等价类个数分别为和| X |。 其中，m 表示最大节点度，L 表示GNN层数，X 表示所有可能的节点特征集合。前者显然更大，这表明 GNNs 具有更强的表达能力 。然而，在经验上，当| X |很大时，差距几乎没有影响。在实际应用中，节点特征可能是高维的，如词袋，甚至是词嵌入，从而使得| X |非常大。与词袋一样，| X |的大小为 O( pD )，其中 D 为词汇量，p 为最大词频。L 层GNN 的表达能力以为下界，但根据经验，MLP 和 GNN都应该具有足够的表达能力，因为 D 通常是数百或更大的(见表5)。

表5 ：数据集统计。

5.8 Glnns何时失效?

正如第5.7节和附录 D 所讨论的那样，GML 节点分类的目标是在有根图 G[i] 和标签 yi 上拟合一个函数 f。从信息论的角度来看，通过最小化常用的交叉熵损失来拟合 f 等价于最大化互信息( MI )，I( G[i] ; yi)，如Qin et al . ( 2020 )所示。如果我们把 G[i] 看成是两个随机变量 X[i] 和 E[i] 的联合分布，分别表示 G[i] 中的节点特征和边，则我们有

仅依赖于边和标签，因此MLPs只能最大化 。在极端情况下，给定E[i]，当 y[i] 条件独立于X[i]时，可以为零。例如，当每个节点都被它的度或是否形成三角形标记时。那么MLPs将无法拟合有意义的函数，GLNNs也将无法拟合有意义的函数。然而，这种情况通常是罕见的，在实际环境中我们的工作主要关注的是意想不到的。对于真实的GML任务，节点特征和结构角色往往是高度相关的(勒里克等, 2020)，因此即使仅基于节点特征，MLPs也可以取得合理的结果，因此GLNNs可以潜在地取得更好的结果。我们在第6节中通过创建低MI场景来研究GLNNs的失效情况。

6、消融研究

在本节中，我们对节点特征噪声、感应分裂率和教师 GNN 架构进行了 GLNNs 的消融研究。报告的结果是 CPF 中五个数据集上的平均测试精度。更多的实验可以在附录中找到，包括高级 GNN 教师(附录F )、GA - MLP 学生(附录G )和非同质数据(附录I )。

噪声节点特征

在第5.8节中，我们通过在节点特征中添加不同水平的高斯噪声来降低它们与标签的互信息来研究 GLNN 的失败案例。具体地，我们将 X 替换为，是独立于 X 的各向同性高斯，α∈[ 0、1 ]表示噪声水平。我们在图5 (左)中展示了 MLP，GNN 和 GLNN在不同噪声水平下的归纳性能。我们看到，随着 α 的增加，MLPs 和 GLNNs的精度下降比GNNs快，而对于小αs，GLNNs 和 GNNs的性能仍然相当。当α达到1时，\hat{X} 和 Y 将变得相互独立，对应于第5.8节所讨论的极端情况。更详细的讨论见附录 J。

感应分裂率

在第5.4节中，我们使用20 - 80分位的测试数据进行归纳评估。在图5 (中间)中，我们展示了不同分裂率(附录H中更详细的地块)下的结果。我们看到，随着诱导部分的增加，GNN和MLP的性能保持大致相同，而GLNN的诱导性能略有下降。我们只考虑高达50 - 50的速率，因为在实际中具有50 %甚至更多的感应节点是高度不典型的。当遇到大量的新数据时，从业者可以选择在部署之前在所有数据上重新训练模型。

教师GNN架构

到目前为止，我们使用 SAGE 来表示 GNNs。在图5 (右)中，我们展示了其他各种GNN教师的结果，例如：Gcn、Gat、Appnp。我们看到，GLNNs 可以向不同的教师学习，并比 MLPs 有所改进。四位教师的表现相似，但从 APPNP 中提取的 GLNN 比其他教师稍差。事实上，在Yang等人( 2021a )中也观察到了类似的现象，即 : APPNP使学生获益最少 。一个可能的原因是，APPNP 的第一步是利用节点自身的特征来预测(在图上传播之前)，这与学生MLP正在做的事情非常相似，因此比其他教师提供给MLP的额外信息更少 。

7、结论与未来工作

在本文中，我们探索了是否可以桥接 GNNs 和 MLPs 的优点，以实现准确和快速的 GML 模型部署。我们发现，从 GNNs 到 MLPs 的 KD 有助于消除推理图依赖 ，这导致 GLNNs 在享受竞争性能的同时比 GNNs 快146 × -273 ×。我们对 GLNN 的性质进行了全面的研究。在7个不同领域的数据集上的实验结果表明，GLNNs 可以作为部署延迟约束模型的一个简便选择。在我们的实验中，当前版本的 GLNNs 在 Arxiv 数据集 上并没有表现出有竞争力的归纳性能。更先进的蒸馏技术可以潜在地提高 GLNN 的性能，我们将这项研究作为未来的工作。

A、附录

A.1 数据集

在这里，我们提供了我们用来支持我们论点的数据集的详细描述。在这些数据集中，有4个是引文图。Cora，Citeseer，Pubmed，ogbn-arxiv，节点特征为论文的描述，或者是词袋向量，或者是 TF - IDF 向量，或者是词嵌入向量。

表5 ：数据集统计。

在表5中，我们提供了这些数据集的基本统计数据。

对于所有的数据集，我们遵循原始论文中的设置对数据进行拆分。具体来说，对于 CPF 论文中的五个较小的数据集，我们使用 CPF 分裂策略，每个随机种子对应一个不同的分裂。对于 OGB 数据集，我们遵循 OGB 官方对 Arxiv 和 Products 分别基于时间和流行度的拆分。

A.2 模型超参数

每个数据集上 GNN 模型的超参数取自 CPF 论文和 OGB 官方示例提供的最佳超参数 。对于学生 MLPs 和 GLNNs，除非与- wi 或- Li 另有规定，我们将其层数和每层隐含维数设置为与教师 GNN 相同，因此它们的总参数量与教师 GNN 相同。

对于GLNNs，我们从 [ 0.01、0.005、0.001] 进行学习率的超参数搜索，从 [ 0、0.001、0.002、0.005、0.01] 进行权重衰减，从 [ 0、0.1、0.2、0.3、0.4、0.5、0.6] 进行dropout 。

A.3 知识蒸馏

我们使用 Hinton 等人( 2015 )中提出的蒸馏方法，如方程1，发现硬标签是有用的，因此建议非零 λs。在我们的例子中，我们对 λ 做了一些微调，但并没有发现非零的 λ s有很大帮助 。因此，我们报告了 λ = 0 时的所有结果，即 只有包含软标签的第二项是有效的 。更仔细地调整 λ，由于搜索空间严格更大，应该会进一步改善结果。我们在我们的代码中实现了一个加权版本，我们将λ的选择作为未来的工作。

A.4 直推式设定和归纳式设定

给定 G，X 和 YL，节点分类的目标可以分为两种不同的设置，即直推式和归纳式。在实际应用中，前者可以对应于基于用户画像和其他已有用户来预测某个用户的缺失属性，后者可以对应于预测一些新节点的标签，而这些新节点只在推断时才会出现。为了在给定的数据集上创建归纳设置，我们在训练过程中保留一些节点以及与这些节点相连的边，并将它们仅用于归纳评估。这些节点和边是从测试数据中挑选出来的。利用上面定义的记号，我们挑选出了VU中的归纳结点VU，它将VU划分为不相交的归纳子集和观察子集，即。。然后我们可以取 VUind 中所有与节点相连的边来进一步划分整个图，从而得到 .我们使用下面的符号来显示两种设置的输入和输出。

我们在图6中可视化了归纳设置和转导设置之间的差异。

图6 ：2层GNN所示的直推式设置和归纳式设置。中间显示了用于训练的原始图。左边显示了直推式设置，其中测试节点是红色的并且在图中。右边表示归纳设置，其中测试节点为未见的新节点 。

A.5 在直推式设置下选择软目标

对于5.3节的直推式设置，图中的所有节点，包括验证和测试节点，都用于软目标生成 。与归纳式案例相比，它似乎不太实用，但却是发展我们的论点的必要步骤。我们现在讨论这一选择背后的理由。

首先，直推式设置是图数据最常见的设置，它被用于大多数GNN架构工作和我们在相关工作中提到的GNN加速工作中。因此，为了避免任何混乱和与以前文献中的数字进行公平的比较，我们开始了与标准直推式设置完全相同的输入和输出的实验。在这种设置下，GNN的输入包括所有的节点特征和图结构，因此GLNN被设置为能够访问相同的输入。由于GLNN包含教师训练步骤和蒸馏步骤，所有节点的软标签都是教师训练步骤产生的中间输出，因此用于第二个蒸馏步骤以获得最佳的GLNN性能。这种直推式的设置可以归结为当学生足够大时的理智检查 。因此，我们将设置分离为GLNN和GLNN +，并将结果分别报告在表1和表2中。在表1中，我们正在检查在等参数约束下，与GNN相比，GLNN的性能如何。其结果可以解释为给定一个固定的参数预算，是否存在一组参数( MLP的一个实例化)可以达到与GNN一样的竞争结果。只有在这一点成立的情况下，我们才应该像第5.4节那样，进一步考察更具趣味性和挑战性的归纳案例。

其次，我们关注的任务是节点分类，它在许多情况下被认为是** 标签非常稀缺的半监督学习**。例如，Pubmed仅使用20K个节点中的60个已标注节点(每班20人)进行训练。我们的目标不是设计一个能够进行小样本学习的先进模型，而是利用尽可能多的数据来简化模型，以便进行更有效的推理 。因此，我们在所有未标记节点上使用软伪标注，以获得最佳的GLNN性能。在现实中，当存在大量单独的无标签数据时，这些无标签数据可以用于GLNN蒸馏训练，也可以使用不同的有标签数据集进行评估 。在我们的案例中，我们在第5.4节的归纳场景中模拟了这一场景。

A.6 实施和硬件细节

在基线和我们的方法上的实验都是使用PyTorch，用于GNN算法的DGL ( Wang et al . , 2019)库和用于优化的 Adam ( Kingma & Ba , 2015)实现的。我们的实验在一台80个 Intel ( R ) Xeon ( R ) E5-2698 v4 @ 2.20 GHz 处理器和一个 16GB 内存的NVIDIA V100 GPU上进行。

B、Gnns vs B Gnns的空间和时间复杂度

与 MLP 和 GNN 相比，GLNN 为用户提供了一个在模型精度和时间复杂度之间权衡的便捷工具，而不直接关注空间复杂度 。考虑到空间复杂度和时间复杂度是相关的，我们现在在实验中对这两个复杂度进行更详细的讨论。

在表1中，模型比较了等大小的 MLPs ( GLNNs ) 和 GNNs。虽然固定参数预算来控制空间复杂度是比较模型时的标准方法，但对于跨模型比较，特别是 MLPs vs GNNs 。使用 GNNs 进行推理时，需要将图全部或批量地加载到内存中，并且可能使用比模型参数大得多的空间。因此，GNNs 的实际空间复杂度远高于等尺寸的 MLPs。从时间复杂度的角度来看，GNNs 的主要推理延迟来自于数据依赖，如第4节所示。在与图1相同的设置下，我们在图3左边显示，即使具有8倍宽隐藏层的5层 MLP 仍然比单层 SAGE 运行速度快得多。跨模型比较的另一个例子是 Transformers vs RNNs。大型 Transformer 由于注意力机制可以拥有比 RNNs 更多的参数，但总体上也比 RNNs 更快，这是推理时间最小化背景下的重要考虑。

在表1中，我们看到，对于同等大小的比较，GLNNs 在 OGB 数据集上的精度不如 GNNs。根据上面的讨论，考虑到表1中使用的 GLNNs 在 OGB 数据集中数百万个节点上的(3层, 256个隐藏维度)相对较小，我们询问是否可以通过增加 MLP 从而增加 GLNN 大小来缓解这一差距。答案是肯定的，见表2。

C、基于 Min - cut 的模型预测与图拓扑的一致性度量

基于5.6节中的最小切割问题，我们引入了一个度量来衡量模型预测与图拓扑之间的一致性。K - way 归一化最小切割问题，简称最小切割问题，通过去除最小体积的边，将 V 中的 N 个节点划分为 K 个不相交的子集。根据迪隆等( 2004 )，最小切割问题可以表示为

用 C 表示划分 V 的节点分配矩阵 。如果节点 i 被分配到第 j 类中，则C i，j = 1。A 为邻接矩阵，D 为度矩阵。这里我们试图最大化的这个量告诉我们赋值是否与图的拓扑结构一致。它越大则需要去掉的边越少，赋值与图中已有的连接越一致。在 Bianchi 等( 2019 )中，作者表明，当用软分类概率替换硬分配时，式( 2 )中的一个截断损失 Lcut 可以成为式( 4 )的一个很好的近似，并作为度量指标 。

D、Gnns的表现力 vs Mlps为根图的等价类

在Chen et al ( 2021 )中，GNNs和GA - MLPs的表达能力通过根图的诱导等价类进行了理论上的量化。我们采用了他们的框架，并对 GNNs vs MLPs。我们首先定义了有根图。

定义1 (有根图)

一个有根图，记为 G[i] ，是指 G[i] 中的一个节点 i 称为根的图。GNNs、GA - MLPs 和 MLPs 都可以看作是根图上的函数。在标号为 yi 的节点 i 上进行节点级任务的目标是拟合一个关于输入-输出对( G[i] , yi )的函数。

我们将有根图的空间记为 E 。根据 Chen et al ( 2021 ) ，一个模型在图数据上的表达能力是通过它在E上逼近函数的能力来评估的。这进一步被刻画为E上有根图的诱导等价类的个数，等价关系定义如下。给定E上的一族函数F，在所有有根图中定义一个等价关系，使得当且仅当。我们现在给出一个命题来刻画 GNN 的表达能力(在附录 E 中证明)。

命题1

用X表示所有可能的节点特征集合，并假设| X | ≥ 2，用 m 表示最大节点度，并假设 m ≥ 3，则 L 层 GNN 诱导的有根图的等价类总数为的下界 。

如命题1所示，GNNs 的表达能力随层数L呈双指数增长，即取 log ( log ( · ) ) 后，表达能力随层数L呈线性增长 。如Chen et al . ( 2021 )所示，GA - MLPs 的表达能力仅在 L 中呈指数增长。在此框架下，MLP 的表达能力为| X |，相当于 0 层 GA - MLP。由于前者比后者大得多，结论将是 GNNs 比 MLPs 表达能力强得多。这两个数字之间的差距确实存在，但经验上这种差距只有在| X |较小时才会产生影响。正如在 Chen et al ( 2021 ) 中，下界证明和构造的例子都表明 GNNs 比假设 | X | = 2 的 GA - MLPs 更有效。在实际应用和本文考虑的数据集中，节点特征可以是类似词袋的高维向量，这使得 | X | 非常巨大。因此，这种差距在经验上没有多大意义。

E、命题1的证明

为了证明命题1，我们首先定义有根聚集树 ，它与有根图类似但不同。

定义2(根聚集树)

有根图 G[i] 的深度K根聚集树是一棵深度 K 根树，它有一个(可能是多对一的)从树中的每个节点到 G[i] 中的某个节点的映射，其中( i )树的根映射到节点 i，( ii )树中每个节点 j 的孩子映射到 G[i] 中节点 j 的邻居。

通过展开GNNs中的邻域聚合步骤，可以得到一个有根的聚合树。根图和根聚集树的示意图见Chen et al . ( 2021 )图4。我们用 T L 表示深度为L的所有有根聚集树的集合。然后我们用 TL ，X，m表示 TL 的一个子集，其中节点的特征属于 X，并且所有的节点恰有 m 个度( m个子节点)，并且在这m 个节点中至少有两个节点具有不同的特征。换句话说，一个节点不可能有所有相同的子节点。在定义了有根聚集树的情况下，我们准备证明命题1。该证明改编自Chen等人( 2021 )中引理3的证明 。

证明

由于所有 depth-L GNNs 的家族诱导的 E 上等价类的个数由所有共享同一深度 L ( Chen et al , 2021)的根聚集树的根图构成，因此命题1中的下界问题可以归结为下界| TL |，进而可以归结为子集| TL，X，m |的下界问题。现归纳出。

当L = 1时，树的根可以有| X |个不同的选择。对于子节点，我们从| X |中提取m个特征，并且允许重复。这导致例。因此，。

假设该语句对 L 成立，通过从 T，T′∈TL，X，m 中构造 TL+1，X，m 中的树，说明该语句对 L + 1 成立。我们通过将 X 中的节点特征分配给 T 和 T′ 中每个叶子节点的 m 个子节点来实现。首先注意，当 T 和 T′ 是两棵非同构树时，无论节点特征如何赋值，由 T 和 T′ 构造的两棵深度为 depth-L+1 的树都会不同。现在我们考虑所有的树都可以从 T 出发，通过将子树的节点特征分配给叶子节点来构造。

我们首先考虑 T 中从根到叶的所有路径。每条路径由一系列节点组成，其中节点特征形成一对一映射到一个 L 元组 τ∈{ ( x1 , … , xL)：xi∈X } 。叶子节点称为 τ 下的节点，如果从根到它的路径对应于 τ 。不同 τs 下节点的子节点总是可区分的，因此任何赋值都会导致不同的深度为 L + 1 的根聚集树。另一方面，在相同的 τ 下，节点的子节点的分配可以被过数。因此，对于下界T L+1，X，m，我们只考虑一种特殊的分配方式来避免过度计算，即所有节点的子节点在相同的 τ 下分配相同的特征集合。

由于我们假设 T 中至少有两个节点具有不同的特征，因此从根到叶的路径至少存在 2L 个不同的 τs。对于一个固定 τ 下的叶子节点 j，它的一个子节点需要具有与 j 的父节点相同的特征。这种限制是由于有根聚集树的定义。因此，我们只挑选其他 m - 1 个节点的特征，每个 j 的特征都是的。那么通过这样的构造，T 中 depth-L+1 的树的总数可以被下界。最后，我们有这个下界对所有的 T∈TL，X，m 都成立，因此我们得到 和

F、作为教师提出了GNN架构

在我们的实验中，SAGE教师始终被使用，以避免模型架构的影响。其他一些GNN如GCN也被考虑在消融研究中，但它们并不是针对特定数据集的最有名的架构。为了说明GLNN在有更强的教师的情况下具有更强的性能，我们考虑在产品上可以访问的最佳教师。我们以OGB排行榜的MLP + C & S Huang et al ( 2021 )为新教师，该教师报告了84.18 %的准确率，截至2021年11月在排行榜上排名第8。我们选择MLP + C & S而不是其他的前7个，因为其他的要么依赖于原始文本(给定节点特征的附加信息)，要么需要一个大的GPU，内存> 16GB，这是我们无法访问的。此外，与MLP + C & S相比，它们的改进并不十分显著，即84 %到86 %。MLP + C & S教师的结果如表9所示。

表9 ：GLNN + with MLP + C & S教师对产品的评价

我们发现，在新教师的作用下，GLNN +的性能提高到甚至优于SAGE ( 78.61 % )，这表明GLNN可以在更强的教师作用下变得更强。

G、Glnn的单跳邻居的特征增强

在我们的主要实验中，GLNN在Arxiv数据集上的归纳性能不如其他方法。因此，我们考虑用它们的一跳邻居来增加节点特征，以包含更多的图信息。这可以看作是介于纯GLNNs和GNNs之间的中间地带。对于这个新的实验，我们遵循表3中的设置，但采用了两种新的方法。我们在下面解释这两种方法的设置。

1、1-hop GA-MLP ：首先，对于每个节点 v，我们收集它的 1 - hop 邻居 u 的特征来增强 v 的原始特征，即 xv → \widetilde{x}v ，类似于 SGC。然后我们在 \widetilde{x}v 图上训练一个 MLP。注意到如果 v 在观察图中，而 u 在归纳的(在训练过程中未观察到)部分，那么 v 不会从 u 中收集特征。

2、1-hop GA-GLNN ：经过与 1 - hop GA - MLP 相同的特征增强步骤。然后用教师 GNN 的蒸馏训练一个 MLP。

3、综上所述，我们在下面的表格中比较了5种不同的模型

( a ) SAGE ： xv 上的单模型

( b ) MLP ： xv 上的单模型

( c ) GLNN ： xv 上的 SAGE 教师和 MLP 学生

( d ) 1-hop GA-MLP ：\widetilde{x}v 上的单模型

( e ) 1-hop GA-GLNN ： xv 上的SAGE教师，\widetilde{x}v 上的 MLP 学生

我们在下表中显示，使用1跳邻居特征后，GLNN的性能有了很大的提高。我们也观察到从 MLP 到 1 - hop GA - MLP 的显著改善。然而，我们确实看到 1 - hop GA-GLNN ( 68.83 ) 可以从 1 - hop GA-MLP ( 66.62 ) 进一步改进，并与教师( 70.64 )几乎匹配。

表10 ：在 Arxiv 上使用单跳邻居进行特征增强的 GLNN

如图3所示，本文案例中的 1 层 GNN 比 GLNN ( 29.31 ms vs . 7.56 ms) 慢了约 4 倍，这应该是1 跳 GA - MLP / GA - GLNN 与 GLNN 速度对比的一个很好的近似。这一结果在实践上是有益的，因为它给了实践者更多的灵活性，他们希望用更少的推理时间来交易多少准确性。

H、模型在不同感应分裂率下的性能

本节是对第 6 节中感应分裂率烧蚀研究的延续。它将图 5 推广到更多的拆分率( 10 : 90 ~ 90 : 10)，并显式地显示了在每个数据集上的归纳和转导性能。为了更好地可视化，下面的图中训练数据标签率也从 20 个/类降低到 5 个/类。

图7 ：MLP、GNN ( SAGE ) 和 GLNN 在生产环境中不同感应拆分率下的模型感应性能比较。

图8 ：MLP，GNN ( SAGE ) 和 GLNN 在生产环境中不同感应分割率下的模型转导性能比较。

I、Glnn在节点特征异质性和非同质性下

除了主要实验中使用的 7 个数据集外，我们还考虑了来自 Ivanov & Prokhorenkova ( 2021 ) 和Lim et al ( 2021 ) 的另外 4 个数据集来进一步评估 GLNN。

House _ class 和 VK _ class 数据集来自 Ivanov & Prokhorenkova ( 2021 ) 。这两个图的节点特征都是基于表格数据，与 Cora 等的词袋节点特征相反，具有不同的类型、尺度和含义。数据集的一些基本统计量如下表所示。

表11 ：具有异构节点特征的数据集统计

我们使用 Ivanov & Prokhorenkova ( 2021 ) 的最佳 BGNN 模型作为教师，将 GLNN 应用在House _ class 和 VK _ class 上。比较如下表所示。Ivanov & Prokhorenkova ( 2021 ) 也将 GAT、GCN、AGNN 和 APPNP 作为基线，它们在这两个数据集上的表现与(差异< 0.025)相当。我们通过将 4 个 GNN 模型中的最佳结果与这些基线进行比较，并将其称为下表中的 GNN，即。Gnn = Max ( GAT、GCN、AGNN、APPNP)。从表中，我们可以看到 GLNN 可以从 MLP 中改进，优于 GNN 和LightGBM，并且与教师 BGNN 相比具有竞争力。

表12 ：异构节点特征数据集上的 GLNN。GLNN 以外的数字取自 Ivanov & Prokhorenkova ( 2021 )。

我们进一步从Lim et al . ( 2021 )中挑选出非同质的 Penn94 和 Pokec 数据集。数据集的一些基本统计量如下表所示。

表13 ：非同源数据集的统计

使用 GCN 教师，我们看到 GLNN 的性能比 MLP 有所提高，并在 Penn94 上与教师 GCN 形成竞争。然而，在 Pokec 上，简单的 LINK 模型可以达到非常好的性能，并且优于 Lim 等人( 2021 )中报道的大多数 GNN。LINK 是一个完全不使用节点特征的纯结构化模型。这说明 Pokec 数据集对应于我们在第5.8节( GLNN 的局限性)中讨论的设定- -如果节点标签在很大程度上仅由图结构决定，那么 GLNN 将举步维艰。我们观察到，由于这一限制，GLNN 不如 LINK。然而，我们仍然可以看到，对于大多数的非同源数据集，MLPs 已经在它们上工作得相当好，并且我们可以将 GLNN 用于其他数据集，如 Penn94。

表14 ：非同质数据集的 Glnn。GLNN 以外的数字取自 Lim et al ( 2021 )。

J、模型与含噪Node特征的比较

在第 6 节中，我们进行了消融研究，以比较带有噪声节点特征的模型性能，结果如图5中的左图所示。这个情节有两个微妙之处。( 1 )对于高噪声特征，即使在 α = 1 且特征完全随机的情况下，GNN 的性能仍然较高。( 2 )对于完全随机的特征，GLNN 的性能仍然高于 MLP。我们现在对它们进行更详细的讨论和解释。

Gnn在随机特征上的表现

GNN 仍然表现良好，因为具有相同标签的节点很可能是连接的，并且 GNN 可以对训练数据进行过拟合。我们通过一个玩具的例子来说明细节。假设图中存在一个包含节点 A，B，C，D 的 4 团，且只有一条边 D - E 将这个团连接到其他的图节点上.假设 A，B，C，D 都有 iid 个随机高斯原始特征和相同的类标 c。令 A 为归纳测试节点，假设 E 和 B、C、D 构成的三角形在训练图中。我们考虑一个简单的 1 层 GCN 的例子，将消息传递分解为特征聚合和非线性变换。在训练过程中，GNN 通过学习一个非线性变换，将 B，C，D 的聚合特征映射到 c 类，从而实现对数据的过拟合。B和C的聚合特征只会是 B、C、D 原始特征的平均值，虽然 E 也参与了 D 的特征聚合步骤，但是 D 的聚合特征也会非常接近这个平均值。然后在对 A 进行测试时，由于A的聚合特征是 A、B、C、D 原始节点特征的平均值，所以通过过拟合的非线性变换很可能将 A 的聚合特征分类到同一类 c 中。在这种情况下，由于过拟合，GNN 实际上可以正确分类 A。对于层数较多的 GNN 和邻居节点较多的图，该结论可能具有普适性。这大致是一个"多数投票"的过程。对于一个测试节点 A，如果 A 收集的特征中有许多节点具有相同的类标号，并且出现在训练图中，那么A将被一个过拟合的分类器分类为这个类。

Glnn和MLP在随机特征上的表现

MLP 和 GLNN 之间的差距是由于数据不平衡造成的。GLNN 可以从软标签中学习不平衡，而 MLPs 只能访问均匀选择的训练节点。我们使用 A - computer 数据集作为例子来解释更多的细节，其中 MLP 和 GLNN 之间的差距是显而易见的。任务为 10 类分类。在随机节点特征下 ( α = 1 )， MLP 的归纳精度为 0.0652，GLNN 的归纳精度为 0.2538。如果数据标签是一致的，那么两个模型都应该给出 0.1 左右的精度。然而，归纳数据集上的标签实际上是不平衡的。我们在图 9 中展示了结果。左边的 hist 是归纳测试集的标签分布。尤其是 4 班，约占 40 %。然而，考虑到这种不平衡性，标准的训练-测试分割在标签之间均匀地选择训练节点。在这种情况下，每类 20 个节点。因此，MLP 对随机特征的预测预期是相对均匀的，因为我们在其上训练的 200 个节点是均匀的。这就给出了中间所示的 hist，其中最大的一类约占17.5 %。最后，对于 GLNN ，我们在所有 200 个带有硬标签的训练节点上进行训练，加上观测图 Gobs (见5.2节)中其他节点的软标签。由于这些额外的节点是随机选择的，其标签分布实际上与整个数据上的标签分布和归纳测试集上的分布相似。因此，我们得到右边的 GLNN 预测结果 hist。虽然对于每个节点，我们不能指定与其特征相关的预测，但平均而言，该分布在归纳测试集上非常接近真实的标签分布，并且具有更高的期望。事实上，如果预测分布恰好是归纳测试集上的真实分布，则期望为 0.2169。GLNN 实际上做得更好，因为它将赌注更多地放在最大的类上。

图9 ：在A - computer数据集上归纳(预测)的标签分布。左：真标签。Middle：MLP预测标签。右边：通过GLNN预测标签 。

论文地址：http://arxiv.org/abs/2110.08727

代码：代码点此处