Augmentation-Free Self-Supervised Learning on Graphs

2022-10-03

字数统计: 2.3k | 阅读时长≈ 10 分钟

https://ojs.aaai.org/index.php/AAAI/article/view/20700/20459

Augmentation-Free Self-Supervised Learning on Graphs ，2022，AAAI

总结：挺好的一篇文章，故事讲得很完整，方法也挺新颖的。作者提出了一种无须增强的GCL方法，利用基于节点表示的kNN获取正样本集合的。在此基础上，考虑到节点的局部机构信息和全局语义信息，使用基于结构的kNN算法和聚类算法，对第一步获取到的正样本集合进行过滤，达到降噪的目的。总的来说，方法比较新，思路很清晰，故事也很完整。至于实验结果，基础对比实验效果一般，不过消融实验、可视化和参数敏感性实验都挺好的，内容比较完整。

1. 简介

1.1 摘要

Inspired by the recent success of self-supervised methods applied on images, self-supervised learning on graph structured data has seen rapid growth especially centered on augmentation-based contrastive methods. However, we argue that without carefully designed augmentation techniques, augmentations on graphs may behave arbitrarily in that the underlying semantics of graphs can drastically change. As a consequence, the performance of existing augmentation-based methods is highly dependent on the choice of augmentation scheme, i.e., hyperparameters associated with augmentations. In this paper, we propose a novel augmentation-free self-supervised learning framework for graphs, named AF-GRL. Specifically, we generate an alternative view of a graph by discovering nodes that share the local structural information and the global semantics with the graph. Extensive experiments towards various node-level tasks, i.e., node classification, clustering, and similarity search on various realworld datasets demonstrate the superiority of AFGRL. The source code for AFGRL is available at https://github.com/Namkyeong/AFGRL .

受自监督方法最近在图像领域成功应用的启发，图结构数据上的自监督方法发展迅速，尤其是基于增强的对比方法。然而，我们认为如果不进行设计增强技术，图上的增强会很糟糕，因为这可能导致图的潜在语义信息发生巨大改变。因此现有的基于增强的方法都高度依赖于增强策略的选择，即与增强相关的一些超参数。本文我们提出了一种新的augmentation-free图自监督框架，称之为AF-GRL。具体来说，我们通过寻找那些和图共享局部结构信息和全局语义信息的节点来生成alternative view。在node-level任务上的大量实验证明了AFGRL的优越性能。

1.2 本文工作

背景： 最近自监督学习在计算机视觉、信号处理、自然语言处理等众多领域都得到了广泛应用。受对比学习在视觉领域成功应用的启发，研究人员将其引入了图学习领域。visual和graph中的对比学习具有inherent distinction： while augmentation is well defined on images, it may behave arbitrarily on graphs。对于image，裁剪、旋转或者改变颜色后，人类依旧可以分辨这张图片。但是对于graph，增减节点或者边后，可能图的语义发生巨大的变化。

动机： 现有的GCL方法大多都依赖增强策略的选取，作者希望设计一种不需要增强的对比学习方法。

本文工作： 作者提出了一种自监督图表示学习框架AFGRL，既不需要增强也不需要负采样。

不需要增强？ 将原始图作为一个视角，通过discovering生成其他视角，进行对比。discovering是啥？后文我们再介绍。
不需要负采样？ 采用现有的BYOL框架，无需显示负采样。

2. 方法

2.1 回顾BYOL

BYOL是2020年提出来的，用于解决CV中对比学习的负采样问题。

BYOL训练两个对立的编码器 $f_\theta$ 和 $f_\xi$ ，分别用于计算两个增强视角 $\mathrm{x}_1 \sim t(\mathrm{x})$ 和 $\mathrm{x}_2 \sim t^{\prime}(\mathrm{x})$ 的嵌入，记作 $\mathbf{h}_1=f_\theta\left(\mathbf{x}_1\right)$ 和 $\mathbf{h}_2=f_\xi\left(\mathbf{x}_2\right)$ 。

然后将两者映射到对比空间，即 $\mathbf{z}_1=g_\theta\left(\mathbf{h}_1\right)$ 和 $\mathbf{z}_2=g_\xi\left(\mathbf{h}_2\right)$ 。

目标函数定义为 $\mathcal{L}_{\theta, \xi}=\left\|\bar{q}_\theta\left(\mathbf{z}_1\right)-\overline{\mathbf{z}}_2\right\|^2$ ，其中 $\bar{q}_\theta\left(\mathbf{z}_1\right)$ 和 $\bar{\mathbf z}_2$ 表示 $q_\theta\left(\mathbf{z}_1\right)$ 和 $\mathbf z_2$ 的 $l_2$ 范式。

上面是将 $\mathrm{x}_1$ 喂给online编码器 $f_\theta$ ， $\mathrm{x}_2$ 喂给target编码器 $g_\xi$ 。将两者反过来，我们就能得到对称的编码损失，记作 $\widetilde{\mathcal{L}}_{\theta, \xi}$ 。

这样BYOL最终的损失函数定义为： $\mathcal{L}_{\theta, \xi}^{\mathrm{BYOL}}=\mathcal{L}_{\theta, \xi}+\widetilde{\mathcal{L}}_{\theta, \xi}$ 。

在每一轮梯度下降过程中，只优化 $\theta$ ，通过 $\theta$ 更新 $\xi$ ，即 $\theta \leftarrow \operatorname{optimizer}\left(\theta, \nabla_\theta \mathcal{L}_{\theta, \xi}^{\mathrm{BYOL}}, \eta\right), \xi \leftarrow \tau \xi+(1-\tau) \theta$ 。

2.2 AFGRL

AFGRL框架图如上，这里的核心就是它如何实现Augmentation-Free的。

我们知道增强的目的在于生成不同的视角，而生成不同视角的目的在于获取正负样本对。AFGRL采用BYOL框架，因此不需要负采样，因此我们这里重点要关注的时AFGRL如何选取正样本的。下面看看作者是如何实现的。

对于输入图 $\mathcal G$ 中的任意节点 $v_i\in \mathcal V$ ，使用两个编码器来学习节点表示，online编码器 $f_\theta(\cdot)$ 和目标编码器 $f_\xi$ 。输入 $\mathcal G$ 的邻接矩阵 $A$ 和节点特征 $X$ 后，我们可以得到两组节点表示， $\mathbf{H}^\theta=f_\theta(\mathbf{X}, \mathbf{A})$ 和 $\mathbf{H}^{\xi}=f_{\xi}(\mathbf{X}, \mathbf{A})$ 。

对于query node $v_i \in \mathcal V$ ，我们按如下公式计算它和其余所有节点之间的相似度：

\operatorname{sim}\left(v_i, v_j\right)=\frac{\mathbf{h}_i^\theta \cdot \mathbf{h}_j^{\xi}}{\left\|\mathbf{h}_i^\theta\right\|\left\|\mathbf{h}_j^{\xi}\right\|}, \forall v_j \in \mathcal{V}

得到相似度矩阵后，我们使用KNN算法，找到和query节点 $v_i$ 最相关的节点集合，记作 $\mathbf{B}_i$ ，将其看作 $v_i$ 的正样本集合。

这种做法看起来很合理，但是存在一些问题：

由于没有使用任何标签信息，得到的正样本集合噪声太大，即包含很多和query节点语义不相似的正样本；
graph天生具有结构信息，这种方法没考虑到；
没考虑图的全局语义信息。

针对这3个问题，作者进行了一下改进，过滤掉正样本集合中那些不合适的节点。

2.2.1 Capturing Local Structural Information

先重申下作者的目标：让前文计算出来的 $\mathbf B_i$ 中的节点标签尽可能和query节点标签一致。

上图纵轴是使用k-NN算法得到的节点集合中，和query节点标签相同的节点比例，横轴是k大小。

Rand.GCN表示使用2层GCN学习到节点嵌入后，使用k-NN算法（即前文计算 $\mathbf B_i$ 的方法）
Adj表示单纯使用邻接矩阵，此时的k-NN即k跳邻居
Rand.GCN + Adj表示前两者的结合体，即取两者的交集
Features表示使用节点特征计算k-NN

从上图可以看出，使用Rand.GCN + Adj时，无论k取多大，correct ratio都最大。这正是作者想要的。

对于query节点 $v_i$ ，假设使用Adj计算k近邻后得到的集合为 $\mathbf N_i$ ，那么此时过滤后的正样本集合应该是 $\mathbf{B}_i \cap \mathbf{N}_i$ 。

2.2.2 Capturing Global Semantics

作者这里使用聚类技术来捕捉全局语义信息。对于目标节点表示 $\mathbf H^\xi$ ，将其划分成 $K$ 个cluster，表示为 $\mathbf{G}=\left\{G_1, G_2, \ldots, G_K\right\}$ 。 $c\left(\mathbf{h}_i^{\xi}\right) \in\{1, \ldots, K\}$ 表示节点 $v_i$ 属于哪个cluster。那作者是如何利用聚类信息对正样本集合进行过滤的呢？如下图所示：

这个图看起来有点复杂，其实算起来很简单。对于query节点$v_i$，其最终的正样本集合为： $$ \mathbf{P}_i=\left(\mathbf{B}_i \cap \mathbf{N}_i\right) \cup\left(\mathbf{B}_i \cap \mathbf{C}_i\right) $$ 其中$\mathbf C_i$表示和$v_i$在同一个cluster的所有节点组成的集合。得到正样本集合后，AFGRL的目标函数定义为： $$ \mathcal{L}_{\theta, \xi}=-\frac{1}{N} \sum_{i=1}^N \sum_{v_j \in \mathbf{P}_i} \frac{\mathbf{z}_i^\theta \mathbf{h}_j^{\xi \top}}{\left\|\mathbf{z}_i^\theta\right\|\left\|\mathbf{h}_j^{\xi}\right\|} $$ 即最小化查询节点$v_i$和正样本节点之间的余弦距离。