各种形式的图神经网络的实现和基准测试

2020-07-14

本篇文章是论文的介绍性博客:Benchmarking Graph Neural Networks （https://arxiv.org/abs/2003.00982）的介绍性文章，有兴趣的可以下载原文阅读

图0：在稀疏的2D张量上运行的GCN（顶部）和在密集的2D张量上运行的WL-GNN（底部）的标准实验。

图神经网络（GNN）如今在社会科学，知识图，化学，物理学，神经科学等的各种应用中得到广泛使用，因此，文献中的论文数量激增。

但是，在缺乏标准和被广泛采用的基准的情况下，衡量新模型的有效性和验证可以普遍适用于较大和复杂数据集的新思想变得越来越困难。

为了解决图学习研究中存在的最重要的问题，我们开发了一个开源的，易于使用的且可重现的基准框架（https://github.com/graphdeeplearning/benchmarking-gnns），该框架具有严格的实验协议，该协议代表了GNN的进步。

这篇文章概述了GNN文献中的问题，提出了基准的需求，本文提出的框架，是一种广泛使用的强大GNN基准类别并提出了从广泛的实验中学到的见识。

为什么要进行基准测试？

在深度学习的任何核心研究或应用领域中，基准都有助于识别和量化哪些类型的架构，原理或机制是通用的，并且可以推广到实际任务和大型数据集。 AI领域中的最新革命通常很可能是由大规模基准图像数据集的ImageNet触发的。（显然，其他驱动因素包括研究量的增加，更多数据集，计算，广泛采用等）。

图1：paperswithcode.com的ImageNet分类排行榜

事实证明，在许多科学的领域中，基准测试对于推动进步，确定基本思想以及解决与领域相关的问题都是有益的。这个项目是基于这种动机而构思的。

GNN需要的基准框架

a.数据集

GNN文献中许多被广泛引用的论文都包含在只有几百（或几千）图的小型图数据集上进行评估的实验。

图2：广泛使用的数据集的统计数据。资料来源为Errica2020等

例如，ENZYMES数据集，几乎在用于分类任务的GNN的每项工作中都可以看到。如果使用随机10倍交叉验证（在大多数论文中），则测试集将具有60张图（即600张总图的10％）。这意味着正确的分类（或错误分类）将改变测试准确性得分的1.67％。几个样本可以确定绩效指标的差异为3.33％，这通常是在验证文献中的一个新想法时得出的显着增益得分。这里可以看到，样本数量不可靠，无法具体确认进展情况。¹

我们的实验也表明，此类数据集的性能标准差很大，因此很难对研究思路做出实质性结论。此外，大多数GNN在这些数据集上的统计结果均相同。这些数据集的质量也使人质疑在验证GNN的想法时是否应使用它们。在其中一些数据集中，较简单的模型有时也表现很出色，甚至优于GNN。

因此，区分复杂，简单和不可知的图形架构以进行图形机器学习变得困难。

b.一致的实验方案：

GNN文献中的几篇论文在统一而稳健的实验设置上没有达成共识，这导致实验中讨论的方向的不一致。

此处要突出几个示例：Ying等人在2018年对10倍拆分数据进行了固定次数的训练，并报告了每个epoch的性能，该性能具有"在任何epoch的拆分中具有最高的平均验证准确性" 的特点。 Lee等人，2019年通过监测epoch损失并报告"最后一个epoch的平均测试准确性"超过10倍拆分数据，因此使用了"提前停止标准"。

现在，如果我们将这两篇论文的结果提取到同一张表中，并声称性能得分最高的模型是最有前途的，那么我们是否可以确信这种比较是公平的？

模型的性能还与其他一些问题，超参数选择，可训练参数的不合理预算中的比较，使用不同的训练-验证-测试分割等有关。

这些问题的存在促使我们开发了GNN基准框架，该框架将GNN研究标准化，并帮助研究人员取得更有意义的进展。

建立GNN基准的挑战

缺乏基准一直是GNN文献中的主要问题，因为上述要求尚未得到严格执行。

设计基准非常具有挑战性，因为我们必须为编码框架，实验设置和适当的数据集做出可靠的决策。基准还应该是全面的，以涵盖大多数基本任务，这些基本任务用来指示研究可以应用到的领域。例如，图学习问题包括在节点级，边缘级和图级预测属性。基准应该尝试涵盖其中的大部分（如果不是全部）。

同样，收集真实且具有代表性的大规模数据集也具有挑战性。缺乏可以定义数据集质量或验证给定任务的统计代表性的理论工具，因此很难决定数据集。此外，由于大多数流行的图学习框架都不能"非常有效地"迎合大型图，因此图的节点和边的特征以及图大小的比例需要任意选择。

最近，开放图基准测试（OGB）进行了有效的努力，以收集有意义的中大型数据集，以指导图学习研究。该计划是对该项目目标的补充。

拟议的基准框架：

我们为图神经网络提出了一个具有以下关键特征的基准框架：

1. 我们开发了模块化的编码基础架构，可用于加快新思想的开发

1. 我们的框架采用了严格而公正的实验协议

1. 我们提出了合适的中等规模的数据集，可以将其作为插件用于以后的研究。²

1. 涵盖了图机器学习中的四个基本任务，即图分类，图回归，节点分类和边缘分类。

a.编码基础架构

我们的基准代码基础架构基于Pytorch / DGL。

从总体来看，我们的框架为以下各项统一了独立的组件：i）数据通道，ii）GNN层和模型，iii）训练和测试功能，iv）网络和超参数配置以及v）单一执行脚本以实现可重复性。

图3：我们在GitHub上开源的模块化编码框架的快照

b.数据集：

我们包括来自化学，数学建模，计算机视觉，组合优化和社交网络等不同领域的8个数据集。

图4：基准中包含的数据集的摘要统计

本节介绍了数据集准备步骤及其与基准图神经网络的相关性。

值得一提的是，我们包括OGB的OGBL-COLLAB，这表明我们可以灵活地合并OGB计划中的任何当前和将来的数据集。

c.实验协议：

我们为基准图神经网络模型定义了严格而公平的实验协议。

数据集拆分：鉴于文献中存在针对不同模型使用不同的训练验证测试拆分的问题，我们确保我们的数据管道为每个待比较的GNN模型提供相同的训练，验证和测试拆分。对于一般的数据集，我们遵循标准拆分。对于没有标准拆分的合成数据集，我们确保在拆分之间的类分布或合成属性相同。请参阅论文以了解更多详细信息。

训练：我们对所有实验使用相同的训练设置和报告格式。我们使用Adam优化器以基于验证损失的学习速率衰减策略训练GNN。我们针对每个未指定时期的实验进行训练，其中以最小学习率进行训练会导致模型没有明显的学习。

重要的是，这种策略使用户可以轻松地选择要训练模型的时期。

每个实验都在4种不同的种子上进行，最多需要12个小时的训练时间，并报告了4个实验的最后epoch得分的摘要统计信息。

参数预算：我们决定使用两个可训练的参数预算：（i）每个任务的每个GNN的100k参数，以及（ii）我们研究将模型放大到更大的参数和更深层的GNN的500k参数。相应选择隐藏层的数量和隐藏尺寸以匹配这些预算。

我们选择具有相似参数的预算以进行公平比较，否则很难严格评估不同的模型。在GNN文献中，经常看到将新模型与现有文献进行比较，而没有参数数量的任何细节，也没有试图使模型具有相同的大小。话虽如此，我们的目标不是为每个模型都找到最佳的超参数集，这是一项计算量大的任务。

d.图神经网络：

我们对GNN的两大类进行了基准测试，它们代表了最新文献中见证的图神经网络体系结构的绝对进步。我们将这两个类别命名为GCN（图卷积网络）和WL-GNN（魏斯菲勒-雷曼GNN）。

GCN指的是利用稀疏张量计算的流行的基于消息传递的GNN，而WL-GNN是基于WL测试的理论表达GNN，用以区分需要在哪一层进行密集张量计算的非同构图。

因此，我们的实验管线如图5所示为GCN，图6所示为WL-GNN。

图5：我们的GCN的标准实验管线，它们在稀疏的rank-2张量上运行。

图6：我们的用于WL-GNN的标准实验管线，它们在密集的rank-2张量上运行。

我们将读者引向我们的论文和相应的作品，以获取有关GNN的数学公式的更多详细信息。对于感兴趣的读者，我们还将在论文上包括每个基准的GNN的层更新的框图。

为了在此阶段快速回顾，我们讨论了基准的需求，建立这样的框架所面临的挑战以及我们提议的基准框架的细节。现在，我们深入研究实验。

我们对基于消息传递的GCN和WL-GNN进行调查，以揭示重要的见解并强调在构建强大的GNN模型时面临的潜在的基本挑战。

在建议的数据集上对GNN进行基准测试。

我们使用基准测试框架中当前包含的每个GNN模型对所有数据集进行全面的实验。实验帮助我们得出许多见解，此处仅讨论其中一些。我们建议阅读论文以获取有关实验结果的详细信息。

我们基准测试的GNN是：

· 图卷积网络（GCN）https://arxiv.org/abs/1609.02907

· GraphSagehttps://cs.stanford.edu/people/jure/pubs/graphsage-nips17.pdf

· 图注意力网络（GAT）https://arxiv.org/abs/1710.10903

· 高斯混合模型（MoNet）https://arxiv.org/abs/1611.08402

· GatedGCNhttps://arxiv.org/abs/1711.07553

· 图同构网络（GIN）https://arxiv.org/abs/1810.00826

· RingGNN https://papers.nips.cc/paper/9718-on-the-equivalence-between-graph-isomorphism-testing-and-function-Approximation-with-gnns

· 3WL-GNN https://arxiv.org/abs/1905.11136

1.与图无关的NN在建议的数据集上表现不佳：我们将所有GNN与一个简单的MLP进行比较，该MLP彼此独立地更新了每个节点的特征，即忽略了图结构。

layer层的MLP节点更新公式为：

MLP对每个数据集的评分始终保持较低，这表明有必要考虑这些任务的图形结构。这一结果还表明，这些数据集在统计学上将模型的性能分开了，因此它们对于GNN研究是多么合适。

2.在所建议的数据集上，GCN的性能优于WL-GNN：尽管WL-GNN在图的同构性和表达能力方面具有可证明的强大功能，但我们认为的WL-GNN模型无法胜过GCN。与使用稀疏张量的GCN相比，这些模型的时空复杂度低，因此可以扩展到较大的数据集。

GCN可以方便地扩展到16层并在所有数据集上提供最佳结果，而WL-GNN在尝试构建更深的网络时会面临损失不收敛和/或内存不足的错误。

3.各向异性机制改善了消息传递GCN的体系结构：在消息传递GCN的模型中，我们可以将它们分为各向同性和各向异性。

节点更新方程对每个边缘方向均平等对待的GCN模型被认为是各向同性的；节点更新方程对每个边缘方向的处理方式不同的GCN模型被认为是各向异性的。

各向同性层更新公式：

各向异性层更新公式：

根据以上等式，GCN，GraphSage和GIN是各向同性的GCN，而GAT，MoNet和GatedGCN是各向同性的GCN。

我们的基准实验表明，各向异性机制是GCN的体系结构改进，可提供始终如一的出色结果。请注意，稀疏和密集注意力机制（分别在GAT和GatedGCN中）是GNN中各向异性的示例。

4.训练理论上强大的WL-GNN面临着潜在的挑战：我们观察到WL-GNN的性能得分存在很高的标准差。（回想一下，我们报告了4次运行的不同种子的每次性能）。这揭示了训练这些模型的问题。

像批量训练和批量归一化这样的通用训练程序没有在EL-GNS中使用，因为它们在密集的2D张量上运行。

为了清楚地描述这一点，在处理稀疏秩2D张量的领先图机器学习库中，对GCN进行批处理的方法包括为一批图准备一个稀疏块对角线邻接矩阵。

图7：用一个稀疏块对角矩阵表示的小批量图。

在密集秩2D张量上运行的WL-GNN具有在密集张量中的每个位置处/从该位置处计算信息的组件。因此，同一方法（图7）不适用，因为它将使整个块对角矩阵密集，并会破坏稀疏性。

GCN利用分批训练并使用批归一化来进行稳定和快速的训练。此外，采用当前设计的WL-GNN不适用于单个大型图形，例如。 OGBL-COLLAB。我们无法在GPU和CPU内存上都安装这么大的密集张量。

因此，我们的基准测试建议需要重新考虑WL-GNN的更好的设计方法，这些方法可以利用稀疏性，批处理，归一化等方案，这些已成为深度学习的通用要素。