返回介绍

数学基础

统计学习

深度学习

工具

Scala

四、GNN 公平比较 [2019]

发布于 2023-07-17 23:38:24 字数 31037 浏览 0 评论 0 收藏 0

  1. 多年以来研究人员对于学术界的一些缺陷提出了担忧,如机器学习、科学领域的实验的可重复性reproducibility 和可复制性replicability

    最近,图神经网络已经成为图上的机器学习的标准工具,但是这些模型的实验在很多情况下是模棱两可ambiguous 或者不可复现的。一些常见的可复现问题包括: 超参数的选择、数据集的拆分。而且,一些论文的模型评估代码缺失或不完整的。另外,不同论文在节点特征、边的特征选取上也未标准化。

    实际上对模型的评估包括两个不同的阶段:

    • 模型选择:在验证集上通过超参数调优来选择最优超参数,这对应着模型选择。
    • 模型评估:在测试集上对选择出来的模型进行效果评估。

    显然,如果没有把这两个阶段很好地区分,则可能会导致对模型真实性能的过于乐观和有偏的估计。这使得模型评估的结果不置信。这也使得其它竞争者也很难在严格的评估程序下超越这种不置信的结果。

    有鉴于此,论文《A FAIR COMPARISON OF GRAPH NEURAL NETWORKS FOR GRAPH CLASSIFICATION》 提出了使用标准化、且可复现的实验环境来为 GNN 框架提供公平的性能比较。具体而言,作者在严格的模型选择、模型评估框架内进行了大量的实验,其中所有模型均使用相同的特征、相同的数据集拆分来进行比较。

    其次,论文研究了当前 GNN 模型是否、以及何种程度上可以有效地利用图结构。为此,作者添加了两个领域特定的 domain-specific 、结构无感知的 structure-agnostic 基准方法baseline (这些方法没有利用结构信息),其目的是从节点特征中区分出结构信息的贡献。令人惊讶的是,作者发现这些 baseline 甚至在某些数据集上的性能甚至优于 GNN

    最后,作者研究了节点degree 在社交数据集中作为特征的影响。作者证明:提供 degree 可以提高性能,并且对达到良好结果所需要的 GNN 层数也有影响。

    作者表明:这项工作并非旨在确定性能最佳(或最差)的 GNN,也并未否认大家在开发这些模型上的努力。作者只是试图为 GNN 建立标准、统一的评估框架,以便模型之间可以进行公平、客观地比较。

  2. 相关工作:

    • GNNGNN的核心是为图中的每个节点计算一个状态,这个状态根据相邻节点的状态迭代更新。GNN 最近得到了普及,因为它可以有效地从图中自动提取相关的特征。

      在过去,处理复杂图结构的最流行的方法是使用核函数kernel function 来计算与任务相关的特征。然而,这种核函数是非适应性 non-adaptive 的,而且通常计算成本很高,这使得GNN更有吸引力。

      尽管在这项工作中,我们特别关注为图分类而设计的架构,但所有的 GNN 都共享节点邻域上的 "卷积 " 的概念。例如:

      • GraphSAGE 首先对邻域执行sum 池化、均值池化、或最大池化的聚合,然后它在卷积之上应用线性投影更新 node representation 。它还依靠邻域采样方案来保持计算复杂度不变。
      • 相反,Graph Isomorphism Network: GIN 建立在GraphSAGE 的局限性之上,用 multi-set 上的任意聚合函数来扩展GraphSAGEGIN 模型被证明在理论上与 Weisfeiler-Lehman 的图同构测试 graph isomorphism test 一样强大。
      • 最近,《On the limitations of representing functions on sets》给出了在 setmulti-set 上学习排列不变函数permutation-invariant function 所需的隐单元数量的上限。
      • 与上述方法不同,Edge-Conditioned Convolution: ECC 为每个 edge label 学习一个不同的 parameter 。因此,邻域聚合是根据特定的 edge parameter 进行加权的。
      • 最后,Deep Graph Convolutional Neural Network: DGCNN 提出了与 GCN 的表述类似的卷积层。

      一些模型还利用了池化方案,在卷积层之后应用,以减少图的大小。例如:

      • ECC 的池化方案通过一个可以预先计算的可微分的 pooling map 来粗化图形。
      • 同样,DiffPool提出了一种自适应的池化机制,根据监督准则来对节点进行折叠。在实践中,DiffPool 将可微分的图编码器与其池化策略相结合,因此该架构是可以端到端的训练。
      • 最后,DGCNN与其他工作的不同之处在于,节点是通过一种名为 SortPool 的特定算法进行排序和对齐的。
    • 模型评估:

      • 《Pitfalls of graph neural network evaluation》的工作与我们的贡献有类似的目的。具体而言,作者在节点分类任务上比较了不同的 GNN,表明结果高度依赖于所选择的特定 train/validation/test split ,以至于改变 split 会导致巨大的不同性能排名。因此,他们建议在多个 test split 上评估 GNN,以实现公平的比较。

        尽管我们在一个不同的setting 中操作(图分类而不是节点分类),但我们遵循作者的建议,在一个受控和严格的评估框架下评估模型。

      • 最后,《Are we really making much progress? A worrying analysis of recent neural recommendation approaches》的工作批评了大量的神经推荐系统,其中大多数都是不可复制的,表明其中只有一个真正比简单的 baseline 有所提高。

4.1 风险评估&模型选择

  1. 这里对风险评估risk assessment (也称作模型评估model evaluation )和模型选择model selection 过程进行概述,从而明确本文遵循的实验过程。我们首先给出总体评估框架,如下图所示。

    • 使用外层kout-fold$ k_{\text{out}}\text{-fold} $ 交叉验证来估计模型的泛化性能,即模型评估。

    • 使用内层的 hold-out 或者kinn-fold$ k_{\text{inn}}\text{-fold} $ 交叉验证来选择最优的超参数,即模型选择。

      如果采用了kinn-fold$ k_{\text{inn}}\text{-fold} $ 交叉验证,则模型选择成本会放大kinn$ k_\text{inn} $ 倍。

    模型评估期间也需要重新训练模型(利用寻找到的最优超参数在训练集+验证集上)。

  2. 风险评估(也称作模型评估):风险评估的目的是对一类模型的性能进行估计。

    如果未明确给出测试集,则常用的方式是采用 k-fold 交叉验证Cross Validation:CVk-fold CV 使用k$ k $ 个不同的 train/test 拆分来评估模型的泛化性能。

    • 对于每一个拆分,我们进行模型选择过程仅仅使用训练集来选择超参数。此时测试集不会参与模型选择。

      由于模型选择是针对每个 train/test 拆分单独执行的,因此我们就获得了不同的“最优” 超参数配置。这就是为什么我们指的是一类模型的性能。

    • 然后我们将所有拆分中的测试集性能取均值,则得到这一类模型的性能估计。

  3. 模型选择(也称作超参数调优):模型选择的目的是在一组候选超参数配置中选择特定验证集上最优的配置。

    如果未明确提供验证集,则可以使用留出法hold-out 进行 train/validation 拆分,或者一个内层的 k-fold 交叉验证。

    模型选择的一个关键点是:验证集的性能是真实泛化能力的有偏估计。因此,模型选择的评估结果(即验证集性能)往往过于乐观。这个问题已经在论文 《On over-fitting in model selection and subsequent selection bias in performance evaluation》 中进行了详细记录。

    这也是为什么我们的主要贡献是将模型选择、模型评估清晰地分开。这也是很多文献缺少的、或含糊不清的地方。

  4. 模型选择算法Select

    • 输入:

      • 训练集D$ \mathcal D $
      • 超参数选择集合Θ$ \Theta $
    • 输出:最佳超参数θ$ \theta^* $

    • 算法步骤:

      • 将训练集D$ \mathcal D $ 拆分为trainvalid 两个集合Dtrain,Dvalid$ \mathcal D_{\text{train}}, \mathcal D_{\text{valid}} $ 。

      • 初始化验证集评估指标Pθ=ϕ$ \mathbb P_\theta=\phi $ 空集。

      • 对每组超参数θΘ$ \theta\in \Theta $ ,循环执行:

        • 训练模型modelTrain(Dtrain,θ)$ \text{model} \leftarrow \text{Train}(\mathcal D_{\text{train}},\theta) $
        • 评估验证集PθPθEval(model,Dvalid)$ \mathbb P_\theta\leftarrow \mathbb P_\theta\cup \text{Eval}(\text{model},\mathcal D_{\text{valid}}) $
      • 将验证集表现最好的模型挑选出来,并返回对应的超参数:θargmaxθPθ$ \theta^*\leftarrow \arg\max_\theta \mathbb P_{\theta} $ 。

    如果是kinn$ k_\text{inn} $ 折交叉验证,那么需要拆分kinn$ k_\text{inn} $ 次,然后考虑每组超参数在这kinn$ k_\text{inn} $ 个验证集上的性能均值。这需要训练|Θ|×kinn$ |\Theta|\times k_\text{inn} $ 次。

  5. 模型评估算法Assessment

    • 输入:

      • 数据集D$ \mathcal D $
      • 超参数选择集合Θ$ \Theta $
    • 输出:模型的性能

    • 算法步骤:

      • D$ \mathcal D $ 拆分为k$ k $ 个 foldD1,,Dk$ \mathcal D_1,\cdots,\mathcal D_k $ 。

      • 循环执行i=1,,k$ i=1,\cdots,k $ :

        • 选择Di$ \mathcal D_i $ 为测试集Dtest$ \mathcal D_{\text{test}} $ ,选择剩余的jiDi$ \cup_{j\ne i} \mathcal D_i $ 为训练集Dtrain$ \mathcal D_\text{train} $ 。

        • 根据模型选择算法选择最优的超参数:θ=Select(Dtrain,Θ)$ \theta^* = \text{Select}(\mathcal D_\text{train} ,\Theta) $ 。

        • 通过最佳的超参数重复训练R$ R $ 次模型,每次权重使用不同的随机数来初始化。即r=1,R$ r=1\cdots,R $ :

          • modelrTrain(Dtrain,θ)$ \text{model}_r\leftarrow \text{Train}(\mathcal D_\text{train} ,\theta^*) $
          • prEval(modelr,Dtest)$ p_r\leftarrow \text{Eval}(\text{model}_r,\mathcal D_{\text{test}}) $
        • 然后将R$ R $ 次在测试集上的评估结果取均值:perfi=r=1Rpr/R$ \text{perf}_i = \sum_{r=1}^R p_r/R $ 。

      • 最终将k$ k $ fold 的结果取均值:i=1kperfi/k$ \sum_{i=1}^k \text{perf}_i/k $ 。

4.2 可重复性

  1. 我们首先简要回顾了五种不同的最新 GNN 模型,重点介绍了原始论文中的实验配置问题以及实验结果的可重复性。我们的观察仅基于原始论文的内容和可用的代码。

    我们挑选 GNN 模型的原则:论文的实验使用 10-fold CV 评估性能、同行评审过、很强的架构差异、热门的模型。具体而言我们选择了 GGCNN, DiffPool, ECC, GIN, GraphSAGE 等五个模型。每个模型的详细说明请参考各自的论文。

  2. 我们考察evaluation 质量和可重复性的标准是:

    • 是否提供了数据预处理、模型选择、模型评估的代码。
    • 是否提供了数据集拆分。
    • 是否进行了分层stratification 拆分,即拆分前后每个集合中的类别比例保持不变。
    • 是否报告了 10-fold CV 的均值和标准差,且是否在测试集上进行(即模型评估)、而不是在验证集上进行(相当于模型选择)。

    我们总结了这五个模型的可重复性,如下表所示。其中:(Y) 表示满足条件;(N) 表示不满足条件;(A) 表示模棱两可ambiguity ,即不清楚是否满足条件; (-) 表示信息不足,即没有关于该条件的任何信息。

    注意,这里不包括 GraphSAGE,因为原始论文没有直接将其应用于图分类任务。

    • DGCNN:作者使用 10-fold CV 来评估模型。所有数据集的模型结构都是固定的(比如网络层数、隐层维度),然后仅使用一个随机的 CV fold 来调优 learning rateepoch 数量,然后将这两个超参数应用到其它 fold 。尽管这种做法仍然可以接受,但是可能会导致性能欠佳。而且,作者没有提供模型选择的复现代码。

      此外,作者对10fold 进行评估,并报告了10 个最终得分的均值,这使得标准差偏小。此外,其它对比模型并没有使用相同的过程。

      最后,CV 数据集拆分可以正确地分层拆分并可以公开获得,使得可以评估过程可以复现。

    • DiffPool:尚不清楚是否在测试集而不是验证集上获得了报告的结果。尽管作者声称使用了 10-fold CV,但是未报告 DiffPool 及其竞争对手的标准差。

      此外,作者确认对验证集应用了早停来防止过拟合。不幸的是,模型选择代码和验证集拆分都不可用。

      此外,根据代码,数据被随机拆分(未分层拆分)并且没有设置随机种子,因此每次执行代码时,拆分都是不同的(因此无法复现)。

    • ECC:论文报告说 ECC10-fold 评估的,但结果不包含标准差。和 DGCNN 相似,超参数是预先固定的,因此尚不清楚是否以及如何进行模型选择。重要的是,在代码中没有对数据预处理、数据分层拆分stratification 、数据拆分、模型选择的任何参考。

    • GIN:作者正确地列出了所有已调优的超参数。但是,正如论文和公开的评论里明确指出的,他们报告了 10-fold CV 的验证准确率。换句话讲,报告的结果涉及模型选择,而不是模型评估。模型选择的代码并未提供。

    • GraphSAGE:原始论文没有在图分类数据集上测试该模型,但是 GraphSAGE 在其它论文中经常作为 Baseline。因此,图分类的 GraphSAGE 结果应该附有代码以复现实验。尽管如此,报告 GraphSAGE 结果的两个工作(DiffPool, GIN) 都没有这样做。

    结论:我们的分析表明,就评估质量和结果可复现而言,GNN 的工作很少遵循良好的机器学习规范。

4.3 实验

  1. 我们采用严格实践来使用模型选择和模型评估框架,从而对 9 个数据集(4 个化学数据集,5 个社交数据集)来重新评估上述 5 个模型。此外,我们还是实现了两个 baseline,其目的是了解GNN 是否能够利用结构信息。

    • 所有模型均已通过 Pytorch Geometrics 库来实现,这个库提供了图的预处理程序,并使得图卷积的定义更容易实现。有时我们发现论文和相关代码之间存在差异,此时我们遵从论文中的规范。
    • 由于 GraphSAGE 在原始工作中并未应用于图分类,因此我们选择了最大池化全局聚合函数对图进行分类。此外,我们未使用 GraphSAGE 等人定义的采样邻域聚合方案,而是直接使用整个邻域。
  2. 数据集:所有图数据集都是公开可用的,代表了文献中最常用于比较 GNN 的那些数据集。

    • D&D, PROTEINS, NCI1, ENZYMES为化合物数据集, IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY, REDDIT-5K, COLLAB 为社交网络数据集。数据集的统计信息如下所示。
    • 当节点特征(即 node label 列)不可用时,我们要么为所有节点赋予特征1 ,要么为所有节点赋予节点的 degree。另外,遵从文献的做法,对于 ENZYMES 数据集使用 18 个附加的节点属性。

  3. 特征:在 GNN 文献中,常见的做法是将节点结构属性作为节点特征。如:

    • DiffPooldegree 和聚类系数coefficient 作为节点的特征。
    • GIN 使用节点 degreeone-hot 向量作为节点的特征向量。GIN 之所以如此选择是平衡了性能的提升(sum 函数的单射性质) 和模型的泛化能力(无法将模型推广到任意 degree 的图)。

    一般而言,良好的实验做法建议所有模型应该使用相同的输入形式来进行一致性consistently 的比较。这就是为什么我们使用相同的节点特征重新评估所有模型的原因。具体而言,对于化学领域,我们使用一种通用配置;对于社交领域,我们使用两种可选配置。

    • 对于化学领域,节点特征为原子类型的 one-hot 编码。但是在 ENZYMES 上,我们遵循文献并使用了18 种附加特征。

    • 在社交领域,节点没有特征。我们对所有节点使用无差别的特征(即所有节点特征均为 1 )、或者使用节点 degree 作为特征。因此,我们能够了解模型所施加的结构归纳偏置structural inductive bias 是否有效。即,模型是否能够隐式地学到图的结构特征。

      已经有论文(《Leveraging label-independent features for classification in sparsely labeled networks: An empirical study》)研究了向图的通用机器学习模型种添加结构特征的效果,因此这里我们重点关注节点 degree 特征。

  4. baseline 方法:我们对化学数据集、社交数据集使用两种截然不同的 baseline

    • 对于除ENZYMES 以外的所有化学数据集,我们采用分子指纹技术Molecular Fingerprint technique

      • 首先应用全局sum 池化,即通过将图中所有节点的特征加在一起来统计图中每个类型原子出现的次数。
      • 然后应用带 ReLU 激活函数的单层 MLP
    • 在社交数据集和 ENZYMES(由于存在附加特征):

      • 我们首先在节点特征上应用单层 MLP
      • 然后是全局sum 池化。
      • 最后是一个用于分类的单层 MLP

    注意:这两个baseline 都没有使用图的拓扑结构,即结构无感知的。因此这两个baseline 作为一个参考标准,可以评估特定数据集上 GNN 的有效性。

    实际上,如果 GNN 的性能接近结构无感知的baseline,则可以得出两个结论:

    • 该任务不需要拓扑结构信息就可以有效地解决。这个结论可以通过 domain-specific 的专家的专业知识进行验证。
    • GNN 没有充分利用图结构信息。这个结论很难验证,因为多种因素会起作用,如:训练数据集的规模、体系结构所施加的结构归纳偏置、用于模型选择的超参数等。

    但是,GNN 性能相对于这些结构无感知baseline 的显著提升,是图拓扑结构有效利用的证据。因此,结构无感知baseline 对于了解是否、以及如何改进模型至关重要。

  5. 实验配置:我们使用 10-fold CV 进行模型评估,并使用内层 holdout 技术(90%:10%training/validation 拆分)来进行模型选择。

    每次选择模型之后,我们在整个训练 fold 上训练三次模型,并随机保留数据的 10% 来进行早停。我们需要采用这三个独立的训练来平滑不利的随机权重初始化的影响。

    最终的测试 fold 得分是这三个训练模型的测试得分均值。

    • 我们采用 patience 参数为n$ n $ 的早停策略。如果经过了 nepoch 而验证集的性能没有任何改善,则训练将停止。

      高的 n 值对于验证集得分的波动不敏感从而更有利于模型选择,但是也会有更多的计算量作为代价。

    • 数据集拆分是预先计算好的,所以模型选择、模型评估都是在相同的数据集拆分上进行的。

    • 所有数据都是分层拆分的,这使得每个集合中各类别的比例和原始数据集是保持不变的。

  6. 超参数:我们通过网格搜索来执行超参数调优。我们总是包含其它论文中用到的超参数。其中包括:

    • 对所有模型都通用的超参数:卷积层数、embedding 空间维度、学习率、早停标准(基于验证集准确率或者验证集损失)。
    • model-specific 的超参数:正则化项、dropout、以及模型特有的其它超参数。

    所有超参数搜索空间如下表所示。

  7. 我们的实验涉及大量训练。对所有模型,超参数搜索规模从 3272 种可能的配置(具体取决于超参数数量)。完成一次模型评估过程需要超过 47000 次(以单次训练次数为单位)。如此大量的工作需要同时利用 CPUGPU 的并行性,从而在合理的时间内完成实验。

    我们重点强调某些情况下(如社交网络数据集中的 ECC),当单个超参数配置的训练需要超过 72 个小时,这使得对单个网格的搜索需要持续一个月。因此,由于需要大量的实验和大量的计算资源,我们将完成一次训练的时间限制为 72 个小时。

  8. 下表给出了我们的实验结果,包括平均准确率和标准差。上表为化学数据集的结果、下表为社交网络数据集的结果,最佳结果以粗体突出显示。OOR 表示超出资源限制(Out of Resources) ,要么是时间超出(单次训练时间超过 72 小时)、要么是 GPU 内存超出。

    总体而言:

    • GIN 似乎在社交网络数据集上非常有效。

    • D&D, PROTEINS, ENZYMES 数据集上,没有一个 GNN 能够超越 baseline 方法。

      相反,在 NCI1 上,GNN 明显超越了baseline 。这表明:GNN 确实利用到了NCI1 的图的拓扑结构信息。

    • NCI1 上,即使是非常多参数的 baseline 也无法完全拟合训练集。我们考虑具有 10000 个隐单元、没有正则化的 baseline,它仅达到 67% 的训练准确率。

      相反, GNN 很容易地对训练集过拟合(训练准确率接近 100%)。这表明结构信息极大地影响了拟合训练集的能力。

    • 在社交网络数据集上,将节点 degree 作为特征是有利的。

  9. baseline 的重要性:我们的研究结果还表明:结构无感知的baseline 是了解 GNN 有效性、并提取有用的洞察insight 的重要工具。

    例如,在 D&D, PROTEINS, ENZYMES 数据集上,没有一个 GNN 能够超越 baseline。我们认为:这些 SOTAGNN 模型还不能完全利用这些数据集上的结构。

    实际上在化学领域,众所周知:结构特征和分子特性是存在相关性的。而这些GNN 模型并没有成功地利用到拓扑结构信息。

    因此,我们推荐 GNN 的从业者在未来工作中包括 baseline 比较,从而更好地刻画他们的贡献程度。

    结论:结构无感知的 baselien 很重要,它可以评估 GNN 模型是否捕获了图结构信息。

  10. 节点 degree 效果:我们的研究结果还表明:使用节点 degree 作为输入特征几乎总是有益于社交网络数据集上的模型性能,某些时候甚至提高得非常多。

    • degree 信息平均使得 baseline 模型的效果提升大约 15%,因此在很多数据集上都有竞争力。具体而言,baselineIMDB-BINARY 上达到了最佳性能。

    • 相反,添加 degree 特征对于大多数 GNN 而言并不重要,因为它们可以从结构中自动推断出这类信息。

      DGCNN 是一个值得注意的例外,它明确地需要节点 degree 信息从而在所有数据集上表现良好。

    此外,我们观察到:在添加节点 degree 作为特征之后,模型的排名发生翻天覆地的变化。这就带来一个问题:对节点采用结构特征(如节点degree、聚类系数 clustering coefficient)之后,对模型性能的影响。这留待以后的工作。

    最后,我们还想知道:采用节点 degree 特征之后,是否会影响解决任务所需的模型层数。因此,我们通过计算 10 个不同 fold 中超参数调优得到的最优层数的中位数来研究这个问题。我们观察到一个总体趋势(其中 GraphSAGE 是唯一的例外):degree 的使用使得所需的网络层数减小了大约1层,如下表所示(1 表示所有节点的特征都是相同的,即无信息的特征)。这可能是由于大多数架构在第一层就发现计算 degree 很有用的事实。

    结论:节点特征很重要,像 degree 之类的节点统计特征的引入可以改变 GNN 模型、 baseline 模型的效果和排名。

  11. 最后我们将测试结果的均值和文献报告的结果相比较。此外,我们还汇总了 10 个不同模型选择中(因为是 10-fold CV ),验证集的均值,即平均验证准确率。

    • 我们的测试准确率在大多数情况下和文献中报告的有所不同,并且这两个结果之间的差距通常都是一致的(文献报告的普遍高估)。
    • 平均验证准确率始终高于或等于测试准确率。这是预料之中的。

    最后,我们再次强调我们的结果是:在严格的模型选择和评估协议的框架内获得的;公平地为所有模型使用相同的数据集拆分、数据特征;可复现。

    结论:必须评估测试集,验证集的指标往往会高估模型的能力。

    但是从下图中发现:验证集的排名与测试集的排名相一致。这个现象没有理论上保证,仅仅是从实验数据中观察到。

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文