论文标题：Graph Self-supervised Learning with Accurate Discrepancy Learning
论文链接：https://arxiv.org/abs/2202.02989
论文来源：arXiv 2022

一、概述

近来的一些图自监督学习方法大致可分为两类：预测学习（predictive learning）和对比学习（contrastive learning）。预测学习通过预测mask掉的属性、连接或者图的上下文来学习表示。然而，预测学习是受限的，这是因为它只考虑子图语义。对比学习最早起源于图像领域，通过不同的干扰方法来构建图的不同视图，然后构建正负样本对来学习图片的全局表示。图对比学习也类似，通常采用的数据增强方法有edge perturbation, attribute masking以及subgraph sampling，然后通过最大化两个原图的干扰视图的相似性来学习图的表示。

然而，数据增强以后的视图保留了原图的语义这样的假设总是正确的吗？在图像领域的数据增强并不会改变人类对图片的认知，但是在图领域这一点并不成立。图像存在于一个连续的空间，而图是一种天然离散的数据结构，因此对图来说微小的扰动可能会导致被干扰的图与原图完全不同。举例来说，下面的两个化合物虽然结构相似，但是性质完全不同，在这种情况下，现有的带有扰动的对比学习可能会导致模型学习两个语义上不同的图的相同表示：

举例

为了解决这个问题，本文提出了一个学习图之间精确差异的模型，叫做Discrepancy-based Self-supervised LeArning（D-SLA）。D-SLA首先按照不同的图编辑距离（graph edit distance）来干扰图，接着不同于对比学习训练扰动图尽可能的相似，D-SLA通过区分原图和扰动图来学习它们之间的差异。同时利用图编辑距离来精确学习扰动图之间的差异，也就是说embedding之间的差异要与图编辑距离成正比。另外利用同一个batch内的其他图（负样本图），来使得原图和负样本图之间的距离比原图和其扰动图之间的距离更大。这样的设计使得D-SLA能够捕捉细微的和巨大的拓扑结构差异，而通常的对比学习是忽视了图的轻微差异的。因此，D-SLA能够享受到预测学习和对比学习两种图自监督学习的好处。下图展示了预测学习、对比学习和D-SLA的大致区别：

对比

二、方法

1. 框架

D-SLA是一个预训练的方法。下图展示了D-SLA的大体框架：

D-SLA

2. 区分原图和扰动图

与对比学习训练两个扰动图表示尽可能地相似不同，本文的目标是预测区分原图和扰动图，称为original graph discrimination任务。为原图，为扰动图，那么目标函数为：

是图的得分，从一个可学习的得分网络中得到，是从一个GNN encoder中学习到的表示。通过区分原图和扰动图的训练，模型将学习捕捉图的正确分布，因为扰动图可能与原图相反，在语义上是不正确的，以及学习区分原图和其扰动图之间的细微差别。

3. 干扰方法

D-SLA使用增删边的子集的方法来获得原图的扰动图，这样获得扰动图与原图有细微的差别但也可能在语义上是不正确的。具体的，D-SLA的干扰模式包括以下两个阶段：
①增删小数量的边；
②mask节点的属性。

给定原图，D-SLA会干扰原图次，以获得。干扰时首先增删中的边，也要调整。接着还要随机mask掉中的一些属性（其实是丢弃一些节点），以便使得模型更难区分它们。特别说明的是仅使用节点属性mask，实际上在上面的预测任务中所谓的原图指的是而非。总结来说和获取的过程如下：

和是节点mask和边干扰函数。原图和扰动图的得分由得到：

4. 按照图编辑距离学习差异

将所有的看做等同，因此不能学习扰动图之间精确的差异。在这一小节，我们首先引入精确度量扰动图差异的度量方法——图编辑距离（graph edit distance）。图编辑距离定义为将一个图转换为另一个图的操作（包括边和节点的插入、删除以及替换）的数量，用于度量两个图之间的差异性。不过值得注意的是，计算图编辑距离的操作数量的问题是NP-hard问题，但是我们可以在原图和扰动图之间计算它，而不需要任何代价，因为我们手动设置扰动期间的增删等操作的数量，以此来作为原图和扰动图之间的图编辑距离。也就是说，本文采用增删边的数量来作为和之间的图编辑距离，这也是为什么选用增删边作为扰动方法的原因。

图的embedding之间的距离应该与他们的图编辑距离成正比，这是接下来的损失函数的基本思想。具体的，我们将作为锚点，其扰动图与之间的embedding距离和图编辑距离分别记作和，为了实现精确学习图之间差异的目标，所以采用以下损失函数：

这里采用L2范数来度量embedding距离。注意，模型可能会学习到一个很简单的解决方案，就是将所有的设置为，但是这是不可能出现的情况，因为是和其他目标函数一起训练的，因此不必担心这个问题。我们可以根据图编辑距离采用不同水平的干扰程度，比如弱扰动和强扰动图。

5. 与其他图的相对差异学习

和的使用不会使得模型学习到两个完全不同的图的差异。如果想要同样的使用图编辑距离来学习原图和其他负样本图（指的是同一个batch内的其他图）之间的差异，这是不可能的，因为他们之间的图编辑距离是不可度量的（NP-hard问题）。因此，我们采用一种学习相对距离的方法，基于这样的假设：原图和同一个batch内的负样本图之间的距离应该要比原图和其扰动图之间的距离要大的多，至少要大到一个比较明显的程度，也就是说要大于一个margin（在实际操作中这个margin就是接下来的超参数）。因此D-SLA还采用了一个margin loss，具体如下：

这里的是原图和其扰动图之间的距离：。是原图和其负样本图之间的距离：，是同一个batch内的其他图，是margin超参数。通过这种方式，我们可以让模型学习到，对于原图，负样本图比扰动图更不相似，同时扰动图依照图编辑距离的不同也略有不同。

6. 总结

有了上面三个损失函数，那么D-SLA最终的损失函数为：

D-SLA学习图级表示，通过区分原图和扰动图，可以捕捉到不同图的角落区域的细微差异。此外，与对比学习不同，D-SLA可以区别具有不同属性的不同扰动图，而对比学习认为它们处于同等地位。

三、实验

本文为了证明D-SLA能够学习图的全局和局部表示，进行了图分类（graph classification）和连接预测（link prediction）任务的实验。

1. 图分类

实验在化学领域和生物学领域的数据集上进行，实验结果如下：

图分类

2. 连接预测

实验在社交网络等数据集上进行，实验结果如下：

连接预测

3. 其他实验

下图证明了模型捕捉到了图之间的精确差异：

实验

接着进行了三种损失的消融实验：

实验

最后进行了embedding的可视化：

实验