SelfGNN: Self-supervised Graph Neural Networks without explicit negative sampling

2021-10-02

字数统计: 2.7k | 阅读时长≈ 11 分钟

https://github.com/zekarias-tilahun/SelfGNN

SelfGNN: Self-supervised Graph Neural Networks without explicit negative sampling，2021，WWW

总结：作者提出了隐式负采样GCL模型SelfGNN。创新意义不强，纯粹把CV中一种最新的、非常牛的对比学习技术BYOL弄到图对比学习里面来了。主要创新点有两个：一是借鉴CV中隐式CL方法，将其拓展到GCL方法中；二是借鉴CV中数据增强技术，提出4种用于图数据的特征增强（FA）方法，取得了和常用的拓扑增强（TA）方法相当的性能，但是不需要额外的计算代价（TA计算复杂度通常为 $O(N^3)$ ）。文章实验比较丰富，实验结果也挺好的。

1. 简介

1.1 摘要

Real world data is mostly unlabeled or only few instances are labeled. Manually labeling data is a very expensive and daunting task. This calls for unsupervised learning techniques that are powerful enough to achieve comparable results as semi-supervised/supervised techniques. Contrastive self-supervised learning has emerged as a powerful direction, in some cases outperforming supervised techniques.

In this study, we propose, SelfGNN, a novel contrastive self-supervised graph neural network (GNN) without relying on explicit contrastive terms. We leverage Batch Normalization, which introduces implicit contrastive terms, without sacrificing performance. Furthermore, as data augmentation is key in contrastive learning, we introduce four feature augmentation (FA) techniques for graphs. Though graph topological augmentation (TA) is commonly used, our empirical findings show that FA perform as good as TA. Moreover, FA incurs no computational overhead, unlike TA, which often has 𝑂(𝑁3)time complexity, 𝑁 – number of nodes.

Our empirical evaluation on seven publicly available real-world data shows that, SelfGNN is powerful and leads to a performance comparable with SOTA supervised GNNs and always better than SOTA semi-supervised and unsupervised GNNs. The source code is available at https://github.com/zekarias-tilahun/SelfGNN.

现实世界的数据大多数都是无标签或只有少量有标签，而人工标记数据往往代价昂贵，这要求我们开发出和半监督/有监督想能相媲美的强大无监督算法。对比自监督学习是一个非常好的研究方向，在某些场景下其性能已经超过有监督技术。

本文我们提出了一种新的对比自监督图神经网络SelfGNN，它不需要依赖明确的对比项。我们利用Batch Normalization技术，可以在不牺牲性能的情况下引入隐含对比项。另外，由于数据增强是对比学习中十分关键的一个步骤，我们提出了四种用于图数据的特征增强技术（FA）。经过图拓扑结构增强技术（TA）经常被使用，我们在研究过程中发现FA的性能和TA一样好。不像TA，FA不会带来额外的计算开销。

我们在多个公共数据集上的实验表明，SelfGNN和SOTA有监督方法性能相当，并且在大部分情况下其性能要优于SOTA半监督/无监督GNNs。模型源码获取链接为https://github.com/zekarias-tilahun/SelfGNN。

1.2 本文工作

背景： 近几年，自监督学习方法发展火热，在无监督学习和有监督学习之间架起了桥梁。在CV和NLP邻域自监督学习取得了很大成功，在某些场景下其性能甚至超过了有监督方法。这些自监督方法是由所谓的对比学习（CL）驱动的，通过最大化同一样本在不同视角下的一致性来学习特征表示。大概从2020年开始，研究人员将CL方法引入图学习领域，陆续进行了很多研究。

动机： CV中最近一些研究提出了不需要明确对比项的CL模型（借助孪生网络的一些东西实现的），但是性能比需要明确对比项的模型更好。因此在CV中，我们已经明确了无论使用explicit负样本还是implicit负样本，CL方法都能取得不弱于有监督方法的性能。但是对于图对比学习，我们还不知道负样本究竟需不需要是显示的。

本文工作： 作者将CV中那些隐式负样本CL模型拓展到图对比学习方法中，提出了隐式负采样GCL方法SelfGNN。虽然借鉴了CV中的隐式CL方法，但是和他们有所不同，SelfGNN中隐式负样本技术借鉴的时BYOL中的一些思想。另外，受CV中增强技术的启发，本文作者提出了4中用于图数据的FA增强技术。和其他GCL方法中常用TA增强技术相比，FA性能和TA相当，但是不需要额外的计算代价。（TA增强通常计算复杂度为 $O(N^3)$ ）

2. 方法

2.1 增强策略

数据增强是对比学习中非常重要的一个步骤，图数据增强策略大体可以分两类：topology和feature，本文作者分别为这两类设计了若干种增强策略。

2.1.1 拓扑增强

作者提出了三种拓扑增强策略：基于随机游走的PageRank、基于heat-kernel的PageRank和另外一种基于Katz-index的高阶网络重构技术。三种方法公式如下：

\begin{array}{c} H^{P P R}=\alpha(I-(1-\alpha) \tilde{A})^{-1} \\ H^{H K}=\exp \left(t A D^{-1}-t\right) \\ H^{k a t z}=(I-\beta \tilde{A})^{-1} \beta \tilde{A} \end{array}

2.1.2 特征增强

前人研究中特征增强主要采用mask或者增加噪声策略。本文作者提出了下面四种特征增强策略：

Split： 受CV中图片剪切的启发，将节点特征向量划分成两部分 $X=X[:,: F / 2]$ 和 $X'=X[:,: F / 2]$ ，分别构成原始数据的两个view。
Standardize： 受CV中缩放的启发，对原始特征施加z-score标准化 $X^{\prime}=\left(\frac{X^{T}-\bar{x}}{s}\right)^{T}$ ，其中 $\bar x\in\mathbb R^{F\times 1}$ ， $s\in\mathbb R^{F\times 1}$ 。虽然特征向量具体数值法神改变，但是 $X'$ 中蕴含的信息和 $X$ 是一致的。
Local Degree Profile： 有些数据集没有节点特征信息，有研究提出利用节点的度信息来构建起特征向量 $X'\in\mathbb R^{N\times 5}$ 。将这种LDP机制作为增强策略，然后用0对LDP生成的特征矩阵进行填充使得X和 $X’$ 维度相匹配，即 $X'\in\mathbb R^{N\times F}$ 。
Paste： 这种策略把LDP和X结合到一起，即 $X'\in\mathbb R^{N\times(F+5)}$ 。此时需要将原始特征X用0填充，得到 $X\in\mathbb R^{N\times(F+5)}$ 。

2.2 模型架构

如上图1所示，作者提出的架构模仿了在对比学习中经常被用到的孪生网络。SelfGNN包含两个并行的网络，左边称之为学生网络，右边称之为老师网络。

两条网络第一个组件都是GNN编码器，左边参数为 $\theta$ ，右边参数为 $\phi$ 。编码器详细结构如下图2A所示：

需要注意的是，左边和右边网络有两点不同：

左边比右边多一个prediction block，其结构如上图2B所示。这个预测块视图让学生网络生成的向量尽可能和老师网络生成的向量一致，即 $g_\theta(X_1)\approx X_2$ 。
执行梯度下降时只更新左边网络图编码器参数 $\theta$ ，右边网络的图编码器采用动量更新机制，即：
$\phi \leftarrow \tau \phi+(1-\tau) \theta$

在这种架构下，模型最终的损失函数定义为均方误差：

\mathcal{L}_{\theta}=2-2 \cdot \frac{\left\langle g_{\theta}\left(X_{1}\right), X_{2}\right\rangle}{\left\|g_{\theta}\left(X_{1}\right)\right\|_{F} \cdot\left\|X_{2}\right\|_{F}}

注：损失函数里为啥乘个2，我也不知道。。。

最后还有个问题需要解决，就是前文提到的TA增强策略在SelfGNN中使用存在两个问题：

TA涉及到矩阵变换，时间复杂度为 $O(N^3)$
TA会导致变数量大幅增加，由于显存有限，这是模型就不支持full-batch GNNs。

为了解决这个问题，作者采用ClusterGCN中的子图采样方法。首先使用METIS创建原始的cluster，然后随机merge一些clusters构成batchs。然后不是针对整个图，而是将TAs单独用于每个子图，再用这些子图batchs训练SelfGNN。作者称这种SelfGNN变体为ClusterSelfGNN。