https://arxiv.org/pdf/2010.14945

https://github.com/CRIPAC-DIG/GCA

Graph Contrastive Learning with Adaptive Augmentation ，2021，WWW

总结：现有的图对比学习方法大多采用统一的数据增强策略，忽略了对数据增强策略方面的研究。作者认为现有的数据增强方式存在两个弊端：一是对于节点属性，简单的数据增强数据增强没什么效果；二是对于拓扑结构数据增强忽略了不同节点在图中影响力不同。因此作者提出了一种新的基于自适应数据增强策略的图对比学习框架GCA。实验结果虽然在大多数设定下都是最优的，但是没提高多少，给人一种调参调出来的感觉。从消融实验的结果来看，模型核心创新点带来的性能提升并不多。

1. 简介

1.1 摘要

Recently, contrastive learning (CL) has emerged as a successful method for unsupervised graph representation learning. Most graph CL methods first perform stochastic augmentation on the input graph to obtain two graph views and maximize the agreement of representations in the two views. Despite the prosperous development of graph CL methods, the design of graph augmentation schemes—a crucial component in CL—remains rarely explored. We argue that the data augmentation schemes should preserve intrin-sic structures and attributes of graphs, which will force the model to learn representations that are insensitive to perturbation on unimportant nodes and edges. However, most existing methods adopt uniform data augmentation schemes, like uniformly dropping edges and uniformly shuffling features, leading to suboptimal performance. In this paper, we propose a novel graph contrastive representation learning method with adaptive augmentation that incorporates various priors for topological and semantic aspects of the graph. Specifically, on the topology level, we design augmentation schemes based on node centrality measures to highlight important connective structures. On the node attribute level, we corrupt node features by adding more noise to unimportant node features, to enforce the model to recognize underlying semantic information. We perform extensive experiments of node classification on a variety of real-world datasets. Experimental results demonstrate that our proposed method consistently outperforms existing state-of-the-art baselines and even surpasses some supervised counterparts, which validates the effectiveness of the proposed contrastive framework with adaptive augmentation.

近年来，对比学习成为了一种成功的用于无监督图表示学习方法。大多数图对比学习方法首先对输入图执行随机增强，得到两个graph views，然后最大化这两个views下图表示的一致性。虽然图表示学习方法发展火热，但是对于作为CL方法中的重要组件图增强模式，很少被探索。我们认为图增强模式应该保留图中固有的结构、属性信息，这样模型学习到的表示能够对抗噪声节点的扰动。但是，大多数现有方法都采用统一的数据增强模式，比如统一去掉部分边或者统一对特征进行shuffle，这导致得到的模型是次优的。本文，我们提出了一种新的图对比表示学习方法，通过结合从图拓扑结构、语义上得到的先验知识，实现自适应数据增强。具体来说，在拓扑结构维度，我们设计的增强策略是基于node centrality来寻找相对更重要的结构信息。在节点属性维度，我们通过向不重要的特征维度加入更多噪声，强制模型识别潜在的意义信息。我们在大量真实数据集上进行了节点分类实验，实验结果表明我们提出的方法优于当前最优方法，甚至超过了部分有监督学习方法，这证明了我们提出的“自适应增强对比框架”的有效性。

1.2 本文工作

背景： 过去几年，图表示学习发展火热，GNN作为最重要的图表示学习方法之一，得到了广泛关注。但是，现有的大多数GNNs都是有监督学习方法，依赖大量有标签数据。对比学习作为一种重要的无监督学习方法，最近被广泛用于图表示学习。

动机： 在CV领域，数据增强模式已经被证明了是CL方法中一个非常重要的组件，但是在图领域对于图数据增强方法探索甚少。

本文工作： 作者认为现有的图对比学习方法中数据增强模式存在两个弊端：

1. 简单的数据增强方法比如DGI中使用的feature shifting，不足以生成diverse邻居，尤其是当节点特征很稀疏时会导致难以优化对比目标函数。
2. 现有方法在数据增强时，忽略了不同节点影响力的差异性。比如通过均匀丢掉一些边来构造graph view，可能会删除一些影响力很大的边，导致得到的嵌入质量降低。

基于上面的分析，作者认为CL方法中的增强策略应该要和输入图动态适应，让增强后的图能够保持其固有结构。本文，作者提出了一种新的对比学习框架用于无监督图表示学习，如下图所示：

首先通过数据增强方法生成两个不同的graph view，利用对比损失训练模型，即最大化同一个节点在两个view下嵌入一致性。

2. 方法

2.1 对比学习框架

如前图1所示，作者提出的GCA框架依旧遵循通用的图对比模式，即生成两个graph view，最大化同一个节点在两个view下节点嵌入的一致性。作者提出的的GCA框架执行步骤如下：

1. 每一轮随机采用两个增强函数$t\sim\mathcal T$，$t'\sim\mathcal T$，其中$\mathcal T$表示所有可能的增强函数集合。

2. 生成两个不同的graph views，$\widetilde{G}_{1}=t(\widetilde{G})$，$\widetilde{G}_{2}=t^{\prime}(\widetilde{G})$。两个视图下的节点嵌入分别表示为$U=f\left(\widetilde{X}_{1}, \widetilde{A}_{1}\right)$，$V=f\left(\widetilde{X}_{2}, \widetilde{A}_{2}\right)$，其中$\widetilde{X}_{*}$和$\widetilde{A}_{*}$分别表示特征矩阵和邻接矩阵。

3. 对于视图$\widetilde G_1$下的任意一节点$v_i$，将其嵌入表示$\mathbb u_i$视作锚点，将该节点在另一个视图下的嵌入表示$\mathbb v_i$看作正例，两个视图下的所有其他节点嵌入看作负例。最后，对于每个正例对$(\mathbb{u_i,v_i})$定义如下pairwise objective：

   $\begin{array}{l} \ell\left(u_{i}, v_{i}\right)= \\ \log \underbrace{e \underbrace{\theta\left(u_{i}, v_{i}\right) / \tau}_{\text {positive pair }}+\underbrace{\sum_{k \neq i} e^{\theta\left(u_{i}, v_{k}\right) / \tau}}_{\text {inter-view negative pairs }}+\underbrace{\sum_{k \neq i} e^{\theta\left(u_{i}, v_{i}\right) / \tau}}_{\text {intra-view negative pairs }}}, \end{array}$

   其中$\tau$为温度参数。定义$\theta(\mathbb{u,v})=s(g(\mathbb u),g(\mathbb v))$，其中$s(·,·)$表示余弦距离，$g(·)$表示非线性转换。

4. 基于paire wise损失，整个模型的木变函数可以定义为：

   $\mathcal{J}=\frac{1}{2 N} \sum_{i=1}^{N}\left[\ell\left(u_{i}, v_{i}\right)+\ell\left(v_{i}, u_{i}\right)\right]$

2.2 自适应增强策略

和常规图对比学习中的数据增强策略不同，作者提出了一种自适应数据增强策略，尝试保留重要的结构、属性信息不变，丢掉或改变那些不重要的边和属性。

2.2.1 Topology-level增强

对于拓扑结构数据增强，一种直接的方法就是从原始边集合$\mathcal E$中采用调整后的子集$\widetilde {\mathcal E}$：

$P\{(u, v) \in \widetilde{\mathcal{E}}\}=1-p_{u v}^{e}$

其中$(u,v)\in\mathcal E$，$p_{uv}^e$表示丢掉边$(u,v)$的概率。作者认为$p_{uv}^e$应该和边重要性挂钩，即越重要的边，被丢掉的概率越小。

在图学习领域，衡量节点重要性的一种通用方法就是node centrality。这里，作者定义edge centrality $w_{uv}^e$来衡量边重要性。

具体来说，给定node centrality度量方法$\varphi_{c}(\cdot): \mathcal{V} \rightarrow \mathbb{R}^{+}$，有$w_{u v}^{e}=\left(\varphi_{c}(u)+\varphi_{c}(v)\right) / 2$。对于有向图，则直接使用尾结点centrality作为边centrality $w_{u v}^{e}=\varphi_{c}(v)$。

得到edge centrality后，令$s_{uv}^e=log\ w_{uv}^e$前文中概率$p_{uv}^e$计算方式如下：

$p_{u v}^{e}=\min \left(\frac{s_{\max }^{e}-s_{u v}^{e}}{s_{\max }^{e}-\mu_{s}^{e}} \cdot p_{e}, p_{\tau}\right)\tag 4$

其中$p_e$为超参数，表示整体丢边概率，$s_{max}^e$和$\mu_s^e$分别表示$s_{uv}^e$的最大值和平均值，$p_\tau<1$表示cut-off概率，防止丢边概率过大，导致图结构过度损失。

对于node centrality计算方法，作者使用下面三种：

• Degree centrality

  即将节点度作为centrality，在有向图中将入度作为centrality。

• Eigenvector centrality

  将节点邻接矩阵最大特征值对应的特征向量作为centrality。和degree centrality不同，eigenvector centrality还考虑了相邻节点的重要性。在有向图中使用右特征向量作为centrality。

• PageRank centrality

  将pagerank算法计算得到的权重作为centrality，具体定义如下：

  $\sigma=\alpha A D^{-1} \sigma+1$

为了直观的展示作者提出的自适应数据增强方法，作者对Karate club数据集上部分数据进行了可视化实验：

上图中展示的是由两个教练分别领导的两个不同学生小组，可以看到三种数据增强策略都更加强调教练和本组学员之间的边。

2.2.2 Node-attribute-level增强

和图像领域数据增强类似，作者通过用0随机mask特征向量部分维度，实现增加节点属性噪声的效果。

具体来说，首先采样一个随机向量$\tilde{\boldsymbol{m}} \in\{0,1\}^{F}$，其满足分布$\tilde{m}_{i} \sim \operatorname{Bern}\left(1-p_{i}^{f}\right), \forall i$。强化后的节点特征表示为：

$\widetilde{X}=\left[x_{1} \circ \tilde{m} ; x_{2} \circ \tilde{m} ; \cdots ; x_{N} \circ \tilde{m}\right]^{\top}$

和topology-level强化类似，概率值$p_i^f$应该反映节点特征$i-th$维度的重要性。

作者假设对于频繁出现的特征维度，其重要程度更高。

• 对于one-hot节点特征$x_{ui}\in\{0,1\}$，每个维度重要程度计算方法如下：

  $w_{i}^{f}=\sum_{u \in \mathcal{V}} x_{u i} \cdot \varphi_{c}(u)$

  其中$\varphi_c(·)$表示node centrality度量方法。

• 对于连续节点特征$x_u$，$x_{ui}$表示第i维度的数值，作者这里直接使用该值的绝对值计算维度重要性：

  $w_{i}^{f}=\sum_{u \in \mathcal{V}}\left|x_{u i}\right| \cdot \varphi_{c}(u)$

和topology-level一样，最终的概率值计算方法如下：

$p_{i}^{f}=\min \left(\frac{s_{\max }^{f}-s_{i}^{f}}{s_{\max }^{f}-\mu_{s}^{f}} \cdot p_{f}, p_{\tau}\right)$

其中$s_i^f=log\ w_i^f$，$s_{max}^f$和$\mu_s^f$分别表示最大值和平均值，$p_\tau$为超参数。

2.3 理论证明

这一部分作者从MI maximization和triplet loss两方面证明了模型的有效性。

一、MI maximization

MI即Mutual Information互信息（概率论和信息论中的概念），表示一个随机变量中包含另一个随机变量的信息量，也可以理解成两个随机变量之间的相关程度。

这块具体证明看的不是很懂，感兴趣的可以看原文。最后证明了作者前文中提出的目标函数$\mathcal J$是输入特征X和学习到的特征表示之间MI值的下界：

$\mathcal{J} \leq I(X ; U, V)$

大概的证明过程为：首先证明$\mathcal J$是InfoNCE（一种图对比学习方法）的下界，而InfoNCE目标函数是MI的下界，即$I(U ; V) \leq I(X ; U, V)$。本文提出的数据增强策略，在对比两个view 时，可以强制模型将重要的信息编码到节点嵌入中。

二、Triplet loss

本文定义的目标函数$\mathcal J$也可以看做深度度量学习中常用的三元损失。详细证明和分析过程可以看原文。

最后作者得出两个结论，一是本文提出的数据增强策略是有效的，二是GCA中的对比目标优化代价低。

3. 实验

作者通过实验回答下列三个问题：

• 在节点分类任务上，作者提出的GCA模型是否优于baseline方法？
• 作者提出的数据增强策略是否有用？不同增强策略性能如何？
• GCA模型对超参是否敏感？关键超参对模型性能有何影响？

3.1 实验设置

一、数据集

二、Baselines

• 传统方法：DeepWalk，node2vec
• 深度学习方法：GAE，VGAE，DGI，GMI，MVGL
• 有监督学习方法：GCN，GAT

三、实现细节

所有模型都采用两层GCN作为编码器：

$\begin{aligned} \mathrm{GC}_{i}(\boldsymbol{X}, \boldsymbol{A}) &=\sigma\left(\hat{D}^{-\frac{1}{2}} \hat{A} \hat{D}^{-\frac{1}{2}} X W_{i}\right) \\ f(X, A) &=\mathrm{GC}_{2}\left(\mathrm{GC}_{1}(X, A), A\right) \end{aligned}$

3.2 实验结果

一、RQ1：在节点分类任务上，作者提出的GCA模型是否优于baseline方法？

二、RQ2：作者提出的数据增强策略是否有用？不同增强策略性能如何？

三、RQ3：GCA模型对超参是否敏感？关键超参对模型性能有何影响？

为了简化问题，作者这里设置$p_e=p_{e,1}=p_{e,2}$，$p_f=p_{f,1}=p_{f_2}$。