https://arxiv.org/pdf/2208.06743

Enhancing Graph Contrastive Learning with Node Similarity，2022，arxiv preprint

总结：一篇针对负样本采样的文章。作者认为现有的很多GCL方法是次优的，原因有二：（1）直接将所有不同节点看作负样本不好，因为这些节点里面包含false-negative samples，即那些和query节点具有相同语义（相同标签）的节点；（2）正样本通常只有1个，这不足以让模型拥有push positive sample together的能力。作者设计了一种方案，基于节点间相似度来选取正负样本，并对GCL的对比损失进行改进，提出了一种enhanced objective。文章方法简单，思想和Protopical Graph Contrastive Learning那篇比较像，不过多了一个正样本的选取。

1. 简介

1.1 摘要

Graph Neural Networks (GNNs) have achieved great success in learning graph representations and thus facilitating various graph-related tasks. However, most GNN methods adopt a supervised learning setting, which is not always feasible in real-world applications due to the difficulty to obtain labeled data. Hence, graph self-supervised learning has been attracting increasing attention. Graph contrastive learning (GCL) is a representative framework for self-supervised learning. In general, GCL learns node representations by contrasting semantically similar nodes (positive samples) and dissimilar nodes (negative samples) with anchor nodes. Without access to labels, positive samples are typically generated by data augmentation, and negative samples are uniformly sampled from the entire graph, which leads to a sub-optimal objective. Specifically, data augmentation naturally limits the number of positive samples that involve in the process (typically only one positive sample is adopted). On the other hand, the random sampling process would inevitably select false-negative samples (samples sharing the same semantics with the anchor). These issues limit the learning capability of GCL. In this work, we propose an enhanced objective that addresses the aforementioned issues. We first introduce an unachievable ideal objective that contains all positive samples and no false-negative samples. This ideal objective is then transformed into a probabilistic form based on the distributions for sampling positive and negative samples. We then model these distributions with node similarity and derive the enhanced objective. Comprehensive experiments on various datasets demonstrate the effectiveness of the proposed enhanced objective under different settings.

GNNs在图表示学习领域取得了很大的成功，并因此促进了图相关任务。然而，大多数GNN方法都是有监督方法，在现实世界的很多应用中，往往因为难以获取大量标签导致无法使用GNNs。因此自监督图学习方法引起了越来越多的注意。图对比学习是一种非常具有代表性的自监督学习框架。GCL通过对比锚点和正负样本对来学习节点表示。不需要标签信息，通过数据增强生成正样本对，负样本从整个图中均匀采样会导致sub-optimal目标。具体来说，数据增强天生限制了正样本的数量（通常只有一个正样本）。另一方面，随机选取负样本往往导致选到false-negative样本（和锚点具有相似的语义信息）。这些问题限制了GCL的学习能力。本文，我们提出了一种enhanced objective以解决上述问题。我们首先引入一种理想状态，即包含所有正样本，并且负样本集合中没有错误的。然后将这一理想目标转换成基于正负样本对分布的一种近似形式。然后我们用节点相似度对这些分布建模从而得到enhanced objective。不同数据集上的大量实验证明了我们提出的enhanced objective在不同设置下的有效性。

1.2 本文工作

背景： GNNs在各类图表示学习任务中展现了其强大的能力，但是大多数GNNs是有监督模型，需要有标签数据。在现实世界中，有标签数据往往很难获取到，相反我们可以轻松获取到大量无标签数据。最近，对比学习被引入图学习领域并取得了不错的效果。

动机： 现有GCL模型中正负样本选取比较简单，对于查询节点，通常将该节点在另一个view中相对应的节点看做正样本，其余所有节点看作负样本。作者认为这种方法是次优的，原因有两个：（1）直接将其余所有节点看作负样本的话会导致最终负样本集合中包含一些false-negative samples（和query节点具有相同语义的样本）；（2）只有一个正样本，不足以让模型拥有pull similar nodes together的能力。

本文工作： 作者首先提出了一个idea objective，即将和query节点具有相同标签的节点看作正样本，标签不同的其他节点看作负样本。但是由于无监督设定下，我们没有节点标签信息，因此这种idea objective是不可能实现的。

然后作者通过一堆分析和转换后，提出了一种可行的enhanced objective，可以近似达到idea objective的效果。简单来说就是根据其他节点和query节点的相似度来选取正负样本，选相似度高的作为正样本，相似度低的作为负样本。

2. 方法

本文作者提出了对比学习框架下的一个enhanced objective，具体来说是改进了正负样本的选取。

目前大部分GCL模型正负样本的选取都很简单，通常是生成两个view，将query 节点在另一个视角中的counterpart视为正样本，其余所有节点视为负样本。作者认为这种简单的选取方式会导致GCL模型是sub-optimal。

作者首先提出了一种idea objective，即将所有和query节点类别相同的节点视作正样本，类别不同的所有节点视作负样本。

但是由于没有标签信息，这种理想目标显然不可能实现。然后作者一步步对idea objective进行近似，提出了一个可以实现的近似理想目标。关于作者如何进行近似的本文不作介绍（感觉没什么意义），下面直接看作者提出的Enhanced Objective：

$\mathcal{L}_{E N}(v)=-\log \frac{\sum_{v_j \in \mathcal{V}_M}\left[w_v^{+}\left(v_j\right) e^{f(v)^{\top} f\left(v_j\right) / \tau}\right]}{e^{f(v)^{\top} f\left(v^{\prime}\right) / \tau}+\sum_{v_j \in \mathcal{V}_N}\left[w_v^{-}\left(v_j\right) e^{f(v)^{\top} f\left(v_j\right) / \tau}\right]}$

其中$w_v^+(v_j)$和$w_v^-(v_j)$定义如下：

$\begin{aligned} &w_v^{+}\left(v_j\right)=\frac{\mathcal{T}\left(\operatorname{sim}\left(v, v^j\right)\right)}{\frac{1}{M} \sum_{v_j \in \mathcal{V}_M} \mathcal{T}\left(\operatorname{sim}\left(v, v_k\right)\right)} \\ &w_v^{-}\left(v_j\right)=\frac{\mathcal{D}\left(\operatorname{sim}\left(v, v_j\right)\right)}{\frac{1}{N} \sum_{v_j \in \mathcal{V}_N} \mathcal{D}\left(\operatorname{sim}\left(v, v_k\right)\right)} . \end{aligned}$

其中$\mathcal T(\cdot)$是一个单调递增函数，$\mathcal D(\cdot)$是单调递减函数，$sim(\cdot,\cdot)$是相似度函数，$V_M=\left\{v_j\right\}_{j=1}^M \sim p$和$V_N=\left\{v_j\right\}_{j=1}^N \sim p$，$p$是均匀分布。本文$\mathcal T(\cdot)$和$\mathcal D(\cdot)$的定义如下：

$\begin{aligned} &\mathcal{T}\left(\operatorname{sim}\left(v_i, v_j\right)\right)=\exp \left(\operatorname{sim}\left(v_i, v_j\right) / \tau_p\right)-1 \\ &\mathcal{D}\left(\operatorname{sim}\left(v_i, v_j\right)\right)=\exp \left(-\operatorname{sim}\left(v_i, v_j\right) / \tau_n\right) \end{aligned}$

上述enhanced objective通俗点解释就是：“根据节点和锚点之间的相似度选取正负样本，将相似度高的作为正样本，相似度低的作为负样本”。不过在具体实现时，节点$v_j$并不是说非0即1，即并不是限定死它就必须是负样本或者正样本，而是根据$v_i$和$v_j$之间的相似度计算一个权重（绝对值越大权重越大）加到对比损失中。

现在还剩下最后一个问题，即相似度函数的选择。本文作者提出了3种方案：

1. 结构相似度

   使用PPR（Personalized Page Rank）计算节点相似度：

   $\operatorname{sim}_G\left(v_i, v_j\right)=\hat{P}[i, j] \text { or } \operatorname{sim}_G\left(v_i, v_j\right)=\cos (\hat{P}[i,:], \hat{P}[j,:])$

   以上两种实现方式具体用哪种，作者在实验中通过超参进行调节。

2. 特征相似度

   特征相似度就是计算两个节点之间的余弦相似度：

   $\operatorname{sim}_F\left(v_i, v_j\right)=\cos \left(\mathbf{x}_i, \mathbf{x}_j\right)$

3. 结构+特征混合

   混合方式就是把前两种通过平衡因子连接到一起：

   $\operatorname{sim}\left(v_i, v_j\right)=\beta \cdot \operatorname{sim}_F\left(v_i, v_j\right) \cdot \gamma+(1-\beta)\cdot\operatorname{sim}_G\left(v_i, v_j\right)$

   其中$\sum \operatorname{sim}_G\left(v_i, v_j\right) / \sum \operatorname{sim}_F\left(v_i, v_j\right)$让两个相似度的scale相同。

3. 实验

3.1 基础对比

1. GCA vs GCA+

   GCA+即使用作者提出的enchanced objective替换GCA中的objective。

   

2. GRACE vs GRACE+

   

3. Graph-MLP vs Graph-MLP+

   Graph-MLP是借鉴对比学习思想的一种半监督方法。作者用自己提出的enhanced objective对其进行改进。

   

3.2 消融实验

GRACE+§表示只使用$w^+_v(v_j)$，GRACE+(N)表示只使用$w_v^-(v_j)$，GRACE+(G)表示只使用结构相似度，GRACE+(F)表示只使用特征相似度。