Self-supervised Graph-level Representation Learning with Local and Global Structure

• Minghao Xu, Hang Wang, Bingbing Ni, et al. Self-supervised Graph-level Representation Learning with Local and Global Structure[C]. In ICML 2021.
• 上海交通大学

  摘要(Abstract)

  本文研究了无监督/自监督的全图表示学习，它在药物和材料发现中的分子性质预测等许多任务中都是至关重要的。现有的方法主要集中在保持不同图实例之间的局部相似结构，而不能发现整个数据集的全局语义结构。本文提出了一种用于自监督全图表示学习的统一框架，称为局部实例和全局语义学习(GraphLoG)。
  具体地说，GraphLoG除了保留局部相似性外，还引入了层次原型来捕捉全局语义簇。提出了一种有效的在线期望最大化(EM)算法来学习该模型。我们通过在大量的无标记图上预先训练GraphLoG，然后在下游任务上进行精调来评估GraphLoG。在化学和生物基准数据集上的大量实验证明了该方法的有效性。

  关键词(Keywords)

  自监督学习、图表示学习、局部实例、全局语义

  1 引言(Introduction)

  2 问题定义和预备知识(Problem Definition and Preliminaries)

  2.1 问题定义(Problem Definition)

  2.2 预备知识(Preliminaries)

  3 GraphLoG：具有局部和全局结构的自监督图级表示学习

   在这一部分中，我们介绍了我们的方法，称为局部实例和全局语义学习(GraphLoG)，用于自监督图表示学习。GraphLoG的主要目的是发现和提炼潜在空间中图嵌入的局部和全局结构，以便我们可以为下游任务(如图分类)学习有用的图表示。具体地说，GraphLoG通过对齐相关图/子图的嵌入来构造局部光滑的潜在空间。在此基础上，利用分层原型对图嵌入的全局结构进行建模，并通过在线EM算法最大化数据似然。接下来，我们详细阐述了GraphLoG框架。

  3.1 学习图表示的局部实例结构(Learning Local-instance Structure of Graph Representations)

  遵循现有的降维方法(Tenenbaum等人，2000；Roweis&Saul，2000；Belkin&Niyogi，2002)，局部结构学习的目标是保持数据在映射到低维潜在空间之前和之后的局部相似性。具体地说，期望相似的图或子图彼此嵌入得很近，而不相似的图或子图映射到相距很远的地方。利用定义在潜在空间中的相似性度量，我们将该问题描述为最大化相关图/子图对的相似性，而最小化负图对的相似性。
  具体地说，给定从数据分布PG采样的图G=(V，E，XV，XE)，我们通过随机掩蔽图中的一部分节点/边属性来获得其相关对应图G0=(V0，E0，XV0，XE0)(Hu等，2019)(详细方案见附录)。此外，对于由图G中的结点v及其L-跳邻域构成的子图Gv，我们将图G0中对应的子图G0v视为其相关对偶。通过在图G和G0上应用L层GNN模型GNNθ(θ代表GNN的参数)，得到图和子图的嵌入如下：
  其中hv={hgv|v∈V}和hv0={hg0v|v∈V0}分别表示图G和G0中嵌入的子图的集合。
  在这个阶段，学习的目标是提高相关图/子图对的相似度，而减小负图对的相似度。使用特定的相似性度量(例如。
  余弦相似度s(x，y)=x>y/||x|y||在我们的实践中，我们寻求分别优化图和子图的以下两个目标函数：
  其中pn(G，G0)和pn(Gv，G0v)表示从中采样负对的噪声分布。在实践中，对于相关图对(G，G0)或相关子图对(Gv，G0v)，我们用数据集中的另一个图(以同一图中的另一个节点为中心的子图)随机替换G(Gv)来构造负图对。
  为了学习图表示的局部实例结构，我们的目标是最小化两个目标函数(等式。6和7)关于GNN的参数：

  3.2 学习图表示的全局语义结构(Learning Global-semantic Structure of Graph Representations)

  值得注意的是，数据集中的图可能具有分层语义信息。例如，药品(即。分子图)在解剖治疗化学药物(A TC)分类系统中由五级层次表示(Chen等人，2012b)。在映射到潜在空间后，所有图在数据集中的嵌入也期望形成与原始数据的层次语义结构相对应的全局结构。
  然而，由于自监督图表示学习中缺乏明确的语义标签，这种全局结构不能通过标签诱导的监督来获得。为了克服这一局限性，我们引入了一组额外的模型参数，层次原型，以层次的方式表示潜在空间中的特征簇。它们被形式化地定义为C={cli}mri=1(l=1，2，···，Lp)，其中cli∈Rδ表示第l层的第i个原型，Lp是分层原型的深度，m1表示第l层的原型的数量。这些原型被构造为一组树(图1(B))，其中每个节点对应于一个原型，并且，除了叶节点外，每个原型都具有一组子节点，表示为C(Cli)(1 6 i 6ml，l=1，2，···，Lp−1)。
  全局语义学习的目标是鼓励图形紧凑地嵌入相应的原型周围，同时改进层次原型以更好地表示数据。我们将这个问题形式化地描述为优化一个潜变量模型。具体地说，对于观测数据集G={G1，G2，···，GM}，我们考虑一个潜在变量集，即所有图Z={ZG1，zG2，···，zGM}的原型赋值(zGm是在潜在空间中最能代表GM的原型的集合)。该问题中的模型参数是GNN参数θ和层次原型C，由于没有给出每个图对应的潜在变量，因此很难直接最大化完全数据似然函数p(G，Z|θ，C)。因此，我们试图通过EM算法来最大化完全数据似然的期望。
  Vanilla EM算法(Dempster等人，1977；Krishnan等人，1997)要求在每次参数更新之前完全遍历数据集，当数据集的大小像我们的情况一样大时，这在计算上效率低下。因此，我们考虑一种在线EM变体(Sato&Ishii，2000；Capp‘e&Mouline，2009；Leung&Klein，2009)，它对小批量数据进行操作。这种方法是基于I.I.D.的。数据集的假设，其中潜变量的完整数据似然和后验概率都可以在每个观测-潜变量对上进行因式分解：
  首先，介绍了模型参数的初始化方案。
  模型参数的初始化Initialization of model parameters。在触发全局结构探索之前，我们首先通过最小化lLocal来预先训练GNN，并使用所得到的GNN模型作为初始化，从而建立局部光滑的潜在空间。然后，我们利用这个预先训练的GNN模型来提取数据集中所有图的嵌入，并对这些图嵌入应用K-均值聚类来初始化具有输出聚类中心的底层原型(即{CLP i}MLP i=1)。通过迭代地将K-均值聚类应用于下层的原型来初始化上层的原型。对于每次聚类，我们丢弃分配了少于两个样本的输出聚类中心，以避免琐碎的解(Bach&Harchaoui，2007；Caron等人，2018)。
  接下来，我们描述了我们方法中应用的E-步骤和M-步骤的细节。
  E-step。在这一步中，我们首先从数据集G中随机抽样一个小批次图Eg={G1，G2，···，GN}(N表示批次大小)，而Ez={ZGN}NN=1表示对应于这些抽样图的潜在变量。每个潜在变量zGn={z1Gn，z2Gn，···，zLp Gn}是一个从顶层到底层的原型链，最能表示潜在空间中的图Gn，它认为zl+1Gn是zlGn在相应树结构中的子节点，即。Zl+1Gn∈C(ZlGn)(l=1，2，···，Lp−1)。由于有I.I.D.，所以可以用因式分解的方法来估计Ez的后验分布。假设：
  其中，θt−1和Ct−1是上一个EM周期的模型参数。直接求每个后验分布p(Zgn|Gn，θt−1，Ct−1)是非平凡的，这需要遍历分层原型中所有可能的链。取而代之的是，我们采用了随机EM算法的思想(Celeux&Govert，1992；Nielsen et al.，2000)，并绘制了一个样本ˆZGN∼p(ZGN|Gn，θt−1，Ct−1)用于蒙特卡罗估计。
  具体地说，我们以自上而下的方式从每一层依次采样一个原型，所有采样的原型在分层原型中形成一个从顶层到底层的连接链。形式上，我们首先根据所有顶层原型的范畴分布从顶层抽样一个原型，即ˆz1Gn∼Cat(z1Gn|{αi}M1i=1)(αi=Softmax(s(c1i，hgn))，其中s表示余弦相似性度量；对于l层(l>2)的采样，我们基于从上一层采样的Prototypeˆzl−1Gn的子节点上的范畴分布从该层提取原型，即ˆzlGn∼Cat(zlGn|{αc})(αc=Softmax(s(c，hgn))，∀c∈C(ˆzl−1Gn))，使得我们采样潜在变量ˆzGn={ˆz1Gn，ˆz2Gn，···，ˆzLp Gn}，它是分层原型中的连通链。利用上面推导出的潜在变量，我们寻求在M步中最大化完全数据对数似然的期望。
  M-step。在这一步中，我们的目标是最大化关于潜在变量的后验分布的预期完全数据对数似然，其定义如下：
  这一期望需要对所有数据点进行计算，而这在在线设置中是无法实现的。作为替代，我们建议最大化小批量例如的预期对数似然，其可以使用在E步骤中采样的潜在变量eZest={ˆzgn}nn=1来估计：
  我们想指出的是，EQ(θ，C)是Q(θ，C)的一个像样的代理，其中它们之间近似存在比例关系(参见附录以获得证明)：
  我们进一步将EQ(θ，C)与批次大小进行缩放，以得出在计算方面更稳定的对数似然函数L(θ，C)：
  为了估计L(θ，C)，我们需要定义图G和潜在变量zg的联合似然，在我们的方法中它用基于能量的公式来表示：
  其中Z(θ，C)表示配分函数。我们通过测量嵌入HG的图与ZG中的原型之间的相似性以及测量来自连续层的ZG中的原型之间的相似性来形式化负能量函数f：
  F直观地评估了潜在变量zg在潜在空间中表示图G的能力，也衡量了分层原型中沿着链条从顶层到底层的连续原型之间的亲和力。
  由于配分函数的难解性，用p(G，zg|θ，C)进行优化是不容易的。受噪声对比估计(NCE)(Gutmann&Hyv？arinen，2010；2012)的启发，我们寻求用非归一化似然进行优化，即。˜p(G，zg|θ，C)=exp(f(hg，zg))，通过将正观测-潜变量对与从某种噪声分布中采样的负对进行对比，其定义了很好地逼近L(θ，C)的目标函数：
  其中Pn(G，Zg)是噪声分布。在实践中，我们计算了小批次中所有正对的外期望，即(Gn，ˆZGN)(1 6 N 6 N)，而为了计算内期望，我们通过固定图Gn并每次用同一层上的另一个原型随机替换ˆZGN中的一个Lp原型来构造正对(Gn，ˆZGN)的Lp负对。对于全局语义学习，我们的目标是关于GNN参数θ和分层原型C两者最小化全局目标函数lglobal：
  一般而言，所提出的在线EM算法寻求最大化由模型参数θ和C控制的联合似然p(G，Z|θ，C)。进一步，我们提出如下命题：该算法确实能够最大化边际似然函数p(G|θ，C)。

  3.3 模型优化与下游应用(Model Optimization and Downstream Application)

  4 相关工作(Related Work)

  图神经网络Graph Neural Networks (GNNs)。最近，在通过优化随机行走(Perozzi等人，2014；Tang等人，2015；Grover&Leskovec，2016；Narayanan等人，2017)或矩阵因式分解(曹等人，2015；Wang等人，2016)目标学习图表示之后，GNN以邻域聚合的方式显式地推导出邻近保留的特征向量。正如Gilmer等人所建议的那样。(2017)，大多数GNN的前向传递可以描述为两个阶段，消息传递和读出阶段，各种工作(Duvenaud等人，2015；Kipf&Well，2017；Hamilton等人，2017；V elickovic等人，2018；Ying等人，2018；Zhang等人，2018；Xu等人，2019)试图提高这两个阶段的有效性。与这些主要以监督方式训练的方法不同，我们的方法旨在针对GNN的自我监督学习。
  基于自监督学习的图神经网络Self-supervised Learning for GNNs。最近有一些工作探索了基于GNN的自监督图表示学习。Garc‘ıa-Dur’an&Niepert(2017)通过嵌入传播和V elickovic等人学习了图的表示。(2019)，Sun等人。(2019)通过互信息最大化实现了这一目标。此外，一些自我监督任务，例如边预测(Kipf&Well，2016)、上下文预测(Hu等人，2019；Rong等人，2020)、图划分(You等人，2020b)、边/属性生成(Hu等人，2020)和对比学习(Hassani&Ahmadi，2020；Qiu等人，2020；You等人，2020a)被设计为从未标记的图中获取知识。然而，这些方法都只能对不同图实例之间的局部关系进行建模。该框架试图发现一组图的局部实例结构和全局语义结构。
  自监督的语义学习Self-supervised Semantic Learning。基于聚类的方法(谢等人，2016；杨等人，2016；2017；Caron等人，2018；纪万昌等人，2019；Li等人，2020)通常用于以自监督方式学习数据的语义信息。其中，DeepCluster(Caron et al.，2018)证明了通过聚类预测学习到的视觉表征对各种下游视觉任务具有很强的迁移能力。原型对比学习(Li et al.，2020)证明了它优于实例层面的对比学习方法。这些方法主要是针对图像开发的，而不是针对图形结构的数据。此外，在以往的工作中，对数据的层次语义结构的探索较少。

  5 实验(Experiments)

  在本节中，我们使用预训练然后微调的程序来评估GraphLoG在化学和生物领域的性能。此外，还进行了分析性研究，以验证局部和全球结构学习的有效性。

  5.1 实验设置(Experimental Setup)

  预训练细节Pre-training details。跟随胡等人的研究。(2019)，我们采用了一个五层图同构网络(GIN)(Xu等人，2019)，该网络具有300维的隐藏单元和用于性能比较的平均池读出函数(秒。5.2和5.3)。我们使用ADAM优化器(Kingma&Ba2015)(学习率：1×10−3)来预先训练带有lLocal的GNN一个纪元，然后用lLocal和lglobal训练整个模型10个纪元。对于层次原型初始化中的每一次K-均值聚类，我们采用50个初始聚类中心。除非另有说明，批次大小N设置为512，层级原型深度Lp设置为3。这些超参数是在四个下游分子数据集(即BBBP、Sider、ClinTox和BACE)的验证集上通过网格搜索选择的，并以SEC为单位进行灵敏度分析。5.4.
  微调细节Fine-tuning details。为了对下游任务进行微调，在预先训练的广义神经网络上附加一个线性分类器，并使用ADAM优化器(学习率：1×10−3，微调批大小：32)来训练模型100个历元。我们使用了固定步长的学习速率调度器，它每30个历元将学习速率乘以0.3。所有报告的结果都是在五次独立运行中平均得出的。源代码可在https://github.上找到。Com/DeepGraphLearning/GraphLoG.
  性能比较Performance comparison。对于化学和生物领域的实验，我们将该方法与现有的自监督图表示学习算法(即EdgePred(Kipf&Well，2016)、Infoggraph(Sun等人，2019)、AttrMating(Hu等人，2019)、ConextPred(Hu等人，2019)、GraphPartition(You等人，2020b)和GraphCL(You等人，2020a)进行比较，以验证其有效性。我们报道了来自Hu等人的EdgePred、AttrMasking和ConextPred的结果。(2019)，并基于发布的源代码考察了Infoggraph、GraphPartition和GraphCL的性能。

  5.2 化学领域的实验(Experiments on Chemistry Domain)

  5.3 生物领域的实验(Experiments on Biology Domain)

  5.4 分析(Analysis)

  不同目标函数的效果Effect of different objective functions。在选项卡中。4、分析了三种目标函数对生物领域的影响，并继续使用SEC中描述的GIN。在本实验中为5.1。当每个目标函数单独应用时(第一、第二和第三行)，全局语义学习的目标函数表现最好，这可能得益于它对数据语义结构的探索。通过同时应用不同的目标函数，完全模型(最后一行)的性能最佳，说明局部结构和全局结构的学习是相辅相成的。
  层次化原型深度Lp的灵敏度Sensitivity of hierarchical prototypes’ depth Lp。在这一部分中，我们讨论了参数LP的选择，该参数控制发现的语义层次的数量。在图3(A)中，我们绘制了模型在不同Lp值下的性能曲线。可以观察到，与浅层次原型(即Lp 6 2)相比，层次较深的原型(即Lp>3)具有稳定的性能增益。
  批次大小N的敏感性Sensitivity of batch size N。在这个实验中，我们评估了批次大小N对我们方法的影响。图3(B)显示了使用不同批次大小的下游任务的测试ROC-AUC。从折线图中我们可以观察到，大批量(即N>256)可以促进GraphLoG的性能。在这种情况下，抽样的小批次能够更好地代表整个数据集，从而得到更精确的Eq似然期望。14.
  可视化Visualization。在图2中，我们利用t-SNE(Maten&Hinton，2008)来可视化ZINC15数据集上的图嵌入和层次原型。与仅使用局部约束LSub和Lgraph(配置(A)和(B))相比，应用全局约束lglobal(配置(C))后获得了更明显的特征分离，说明了其在发现数据潜在的全局语义结构方面的有效性。

  6 结论和未来工作(Conclusions and Future Work)

  我们设计了一种用于自监督图表示学习的统一框架，称为局部实例和全局语义学习(GraphLoG)，它对一组未标记图的结构进行局部和全局建模。在这个框架中，我们新颖地提出了在图嵌入的基础上学习层次原型来推断图中的全局语义结构。使用来自化学和生物领域的基准数据集，我们经验地验证了我们的方法在不同GNN架构上的优越性能。
  我们未来的工作将包括进一步改进全局结构学习技术，将预训练和精调统一起来，并将我们的框架扩展到社会学、物理学和材料科学等其他领域。