论文标题：Dual Space Graph Contrastive Learning
论文链接：https://arxiv.org/abs/2201.07409
论文来源：WWW 2022

一、概述

图对比学习的核心思想是构建合适的对比pair以学习输入图的结构语义信息。然而，现有的生成对比pair的方法十分的受限，大多数方法是对图进行干扰，包括node dropping, edge perturbation以及attribute masking等数据增强的方式。这些方法都为生成的视图引入了噪声，因此损害了模型的性能。如果负样本对来自于其他数据集的图或者同一个batch内的其他图，那么则不会引入明显的噪声，然而正样本对通常通过图的干扰方法获得，这样的话噪声的引入就是不可避免的。为了避免引入过多的噪声，一些研究采用sub-graph来生成正样本对。然而，如何生成足够的视图，能够包含独特的和信息丰富的特征，仍然是一个开放的问题。

受双曲空间（hyperbolic space）的图挖掘研究启发，本文采用不同的embedding空间，包括双曲空间和欧式空间（Euclidean space），来生成输入图的多视图。首先，双曲空间需要更小的空间来容纳给定的复杂结构的图，这意味着双曲空间embedding相比于欧几里得空间中的embedding具有独特的表达能力。最明显的特性是欧几里德空间随维度多项式地扩展（expand polynomially），而双曲空间则是指数地扩展（expand exponentially）。这意味着在双曲空间中可以采用更低维的embedding来表示一个图。第二个优点是双曲空间更能捕捉图数据中的层次结构，这意味着双曲空间也适合作为图对比学习范式的一个特殊视图。

尽管双曲空间有着众多优点，但是也不能忽略欧式空间的作用。与双曲空间相比，欧式空间中的向量计算效率更高，因为欧式空间中的距离度量不需要反三角函数。另外，欧式空间的度量可以区分数据之间的相对距离（也就是满足三角不等式），这一优势在许多方法中有被利用，比如k-NN和HDBSCAN。因此，同时引入双曲空间和欧几里得空间来生成不同的视图，可以表达原始图中的层次拓扑结构和节点之间的相对距离，有利于图的对比学习。为了充分利用这些优势，本文建议选择不同的图采样器来采样不同空间的子图。本文认为随机子图采样不能充分利用欧式空间和双曲空间之间对比的优势。如前所述，不同的空间有不同的优势，因此应该采用不同的策略采样子图。对于欧式空间，我们希望采样的子图能够很好地反映节点之间的相对位置。而对于双曲空间，我们希望采样的子图能够包含层次信息和拓扑结构。另外目前的图对比学习方法采用相同的encoder来编码不同的视图，本文认为这样会影响不同视图之间的区分，因此对于不同的视图本文采用不同的encoder。

二、预备知识

1. 双曲空间

目前有多种不同的双曲模型，比如Poincaré ball模型,Klein模型,half-plane模型, hyperboloid模型以及hemisphere模型这五个比较知名的，它们每个都有不同的性质。其中Poincaré ball模型最适合用来进行表示学习，因此它可以使用梯度优化的方法进行调整。Poincaré ball模型的定义域与一个常数负曲率相关：

这是一个上的维开球。欧式空间上的直线对应于Poincaré ball的测地线（geodesics）。给定Poincaré ball上的两个点，这两个点之间的相似性相当于连接这两个点的测地线的测地线长度的倒数：

这里的负曲率为，是欧几里德范数，是反双曲余弦函数。

2. 空间映射

我们不能直接在双曲空间上应用梯度下降，这是因为双曲空间梯度与欧式空间是不同的，为了利用现有的方法，有一个解决办法是将双曲embedding映射成欧式embedding。采用两种映射，分别是指数映射（exponential mapping）和对数映射（logarithmic mapping）。从切线空间（这是一个欧式空间，是原点）到双曲空间（是负曲率）的映射是指数映射，从到的映射是对数映射。以原点为目标点，保证了映射的简单性和对称性。，，则指数映射和对数映射定义为：

有了上面两个映射函数，我们就能够将双曲embedding映射到欧式空间以做进一步的处理。神经网络模型中三个主要的embedding处理为矩阵相乘、加偏置以及激活函数：

权重矩阵和偏置通常定义在欧式空间，这意味着它们不能直接和双曲embedding进行操作，为了完成这个过程，我们必须利用上面的映射。对于双曲矩阵相乘，有：

对于双曲偏置相加，有：

对于激活函数，则采用：

利用上述变换，我们可以利用现有的欧氏空间图学习方法来处理双曲空间的图学习问题。

三、方法

1. 框架

本节介绍Dual Space Graph Contrastive learning（DSGC）的主要细节。DSGC的框架如下图所示：

框架

整个框架包含两个部分，一个部分对应标注数据，另一个对应未标注数据。在每个部分中都有欧式空间和双曲空间两个视图。

2. 图采样

在DSGC中首先采用子图采样生成初始的不同视图。一些方法可以进行子图采样，比如深度优先、广度优先以及随机游走等等。给定一个图，代表节点集合，代表边集合，代表节点特征，另外有一个图采样器，然后其子图就表示为：

在欧式空间上采用DiffusionSampler作为子图采样的方法，这种方法相较于基于随机游走的方法更适合保留节点之间的相对距离关系。在双曲空间上我们利用CommunityStructureExpansionSampler作为子图采样的方法来提取输入图的层次信息和树拓扑结构。

3. 图encoder

本文采用多种不同的GNN encoder来进行实验，包括卷积GNN模型如GCN，基于消息传递的GNN模型如GraphSAGE，基于注意力机制的GNN模型如GAT以及结构信息感知的GNN模型如GIN。注意，对于双曲GNN模型，它们实际上具有与欧式GNN模型相同的结构，不同的点在于双曲GNN encoder的输出embedding将被映射到双曲空间上，并且双曲embedding将在双曲空间上计算损失函数。双曲损失函数训练双曲GNN模型，使其输出合适的双曲embedding。

给定图，以及encoder，对于图，我们可以得到它在欧式空间和双曲空间的embedding：

对于图级别的学习任务，还有一个额外的readout函数来由节点的表示获得图表示。

4. 空间转换

为了能够充分利用两个空间的优点，我们采用对比不同空间的图embedding的方法来构建图对比学习的正负样本对，然而两个空间的embedding不能直接进行比较，因此需要进行映射。为了将欧式embedding与双曲embedding进行比较，我们应该将欧式embedding映射到双曲空间：

5. 分类器

获得图的欧式空间embedding以后将其通过一个MLP进行分类：

是类的个数，为激活函数。

6. 损失函数

对比学习的损失函数来自图的双曲embedding和转换过的欧式embedding之间，正样本就是一个图的这两个embedding。在一个mini-batch中假设存在个无标注图和1个标注图，则负样本为这个标注图与个无标注图的组合。具体的：

这里的是一个温度超参数。

采用交叉熵损失函数作为分类任务的监督损失：

这里的为交叉熵损失，为真实标签。

DSGC最终的损失函数为：

是一个控制对比损失的超参数。

四、实验

1. 数据集

采用MUTAG, REDDIT-BINARY和COLLAB三个数据集进行实验。数据集统计如下：

数据集

2. 实验结果

对比了多个GNN baseline和其他图对比学习方法的结果：

实验

3. 消融实验

探究了不同的encoder组合的影响，下图x轴代表双曲空间的encoder，y轴代表欧式空间的encoder：

消融实验

实验结果表明当label ratio越高时实验效果越好，但当label ratio较低时，两个空间采用相同类型的encoder效果就比较差，因此在面对标注数据较少时可以选择采用不同种类的encoder。

下面的实验探究了隐层维度对实验结果的影响：

消融实验

实验表明维度较小时（比如8和16）结果比较稳定。当维度较大时（比如32和64），结果并没有显示出明显的优越性。而且在COLLAB数据集上结果不太稳定，维度较大时尤甚。因此在使用DSGC时建议采用较小的维度。