https://arxiv.org/pdf/2204.13846

https://github.com/zhuyun97/rosa

RoSA: A Robust Self-Aligned Framework for Node-Node Graph Contrastive Learning，2022，IJCAI

1. 简介

1.1 摘要

Graph contrastive learning has gained significant progress recently. However, existing works have rarely explored non-aligned node-node contrasting. In this paper, we propose a novel graph contrastive learning method named RoSA that focuses on utilizing non-aligned augmented views for node-level representation learning. First, we leverage the earth mover’s distance to model the minimum effort to transform the distribution of one view to the other as our contrastive objective, which does not require alignment between views. Then we introduce adversarial training as an auxiliary method to increase sampling diversity and enhance the robustness of our model. Experimental results show that RoSA outperforms a series of graph contrastive learning frameworks on homophilous, non-homophilous and dynamic graphs, which validates the effectiveness of our work. To the best of our awareness, RoSA is the first work focuses on the non-aligned node-node graph contrastive learning problem.

1.2 本文工作

背景： 有研究指出对于node-level任务，使用node-node对比，获得的收益最大。

动机：

1. 现有node-node GCL方法基本都是对比aligned views

   • 一方面，这限制了模型的灵活性和视角的多样性；
   • 另一方面，某些场景下视角必须是non-aligned的，比如随机游走采样和时空网络中。

   什么是aligned view和non-aligned view，下图展示了几个例子：

   

• aligned view：两个视角中包含的节点集合是一样的，可能在结构和节点属性上有所差异；
  • 对应于丢边或者mask feature等增强策略
  • non-aligned view：两个视角中包含的节点集合不同
    • 对应丢节点等增强策略

2. 为什么现有GCL中没有考虑non-aligned view？存在2个难点：

   • 对于N-N类型GCL，如果对比non-aligned view，现有GCL框架就会存在一些问题

     • 对于某个节点i，可能在视角1中存在，但是视角2中不存在。这导致完全没法对比这两个视角，因为节点i不存在正样本。
     • 正负样本间距离的计算也不能采用传统的余弦相似度。

   • 使用什么样的增强策略来生成non-aligned views？

     • 需要最大化视角差异的同时，不破坏原有语义信息

本文工作： 作者提出了RoSA框架，解决了前文提到的non-aligned下GCL存在的两个挑战。

2. 方法

整个框架比较核心的点有3个：生成对比视角、视角对比和对抗训练，下面详细介绍下这3块内容。

生成图视角

一个好的对比视角具有这样的特性：存在差异的同时，保留原始语义信息。

本文作者利用随机游走来生成对比视角。具体来说，对于每个central节点$v$，给定step size $s$，restart概率$\alpha$,利用随机游走生成一个subgraph。每个节点游走2次，这样就能生成2个view。

这种策略下，不仅可以保留原始语义，正负样本也能很好确定：

• 对于节点v，利用随机游走生成了两个子图$\mathcal G_1^v,\mathcal G_2^v$，这两个子图以$v$为中心节点的子图就是一个正样本对。
• 以v节点为中心的子图和以其他所有节点为中心的子图，构成所有的负样本对。

对比损失

得到unaligned view和正负样本后，最后一个核心问题就是对比损失的定义。因为两个视角是unaligned，传统的基于余弦相似度的对比损失就没办法用了。本文作者提出了一种基于EMD算法的对比目标g-EMD，这也是本文最核心的创新点。

EMD是一种度量两个分布之间相似度的算法，用于图像相似度度量，早期时候多用于图像检索。

EMD，earth mover‘s distance，从字面理解就是，把一个分布搬运到另一个分布的代价。对应到本文，可以理解成把一个子图搬运到另一个子图的代价。g-EMD的公式定义如下：

$\begin{gathered} \min _{\Gamma} \sum_{i}^{M} \sum_{j}^{N} \mathbf{D}_{i j} \boldsymbol{\Gamma}_{i j} \\ \text { s.t. } \boldsymbol{\Gamma}_{i j} \geq 0, i=1,2, \ldots, M, j=1,2, \ldots, N \\ \sum_{i}^{M} \boldsymbol{\Gamma}_{i j}=r_{j}, j=1,2, \ldots, N \\ \sum_{j}^{N} \boldsymbol{\Gamma}_{i j}=t_{i}, i=1,2, \ldots, M \end{gathered}$

其中$\mathbf D$和$\Gamma$分别是搬运代价矩阵和权重矩阵。下面详细介绍下这两个矩阵：

• 假设$\mathbf X\in\mathbb R^{M\times d}$和$\mathbf Y \in \mathbb R^{N\times d}$表示两个增强视角，其实就是两个随机游走生成的子图，两个子图分别包含M个节点和N个节点

  • $x_i\in \mathbb R^d$和$y_i\in \mathbb R^d$表示连个子图中的节点嵌入。

• 对于代价矩阵$\mathbf D$，作者定义了连个方面的代价

  • 维度1：节点的相似度，将$\mathbf {x_i}$搬运到$\mathbf {y_j}$的代价，定义为：

  $\mathbf{D}_{i j}=1-\frac{\boldsymbol{x}_{i}^{T} \boldsymbol{y}_{j}}{\left\|\boldsymbol{x}_{i}\right\|\left\|\boldsymbol{y}_{j}\right\|}$

  ​ 其实就是1减去节点相似度，两个节点越相似，搬运代价越低。

  • 维度2：拓扑距离，即两个节点之间的跳数，表示为$\Psi \in \mathbb{R}^{M \times N}$。其思想在于，两个节点在空间上距离越近，越相似，搬运代价越低。

    $\mathbf{S}_{i, j}=S\left(\Psi_{i, j}\right)=\frac{1}{1+e^{-\Psi_{i, j} / \tau}}$

    这样最终拓扑距离的范围控制在$\mathbf{S} \in[0.5,1]^{M \times N}$。

  • 这样，最终的距离矩阵定义为

    $\mathbf{D}=\mathrm{D} \circ \mathrm{S}$

• 对于$\mathbf \Gamma$矩阵，需要依赖于两个向量$\mathbf t\in\mathbb R^M$和$\mathbf r\in\mathbb R^N$，计算方式如下：

$\Pi(\mathbf{t}, \mathbf{r})=\left\{\boldsymbol{\Gamma} \in \mathbb{R}^{M \times N} \mid \boldsymbol{\Gamma} \mathbf{1}_{M}=\mathbf{t}, \boldsymbol{\Gamma}^{T} \mathbf{1}_{N}=\mathbf{r}\right\}$

​ 这里的向量t和r可以分别理解成视角1中每个节点的搬运概率和视角2中每个节点的接收概率，它们的计算法如下：

$\begin{aligned} \boldsymbol{t}_{i} &=\max \left\{\boldsymbol{x}_{i}^{T} \cdot \frac{\sum_{j=1}^{N} \boldsymbol{y}_{j}}{N}, 0\right\} \\ \boldsymbol{r}_{j} &=\max \left\{\boldsymbol{y}_{j}^{T} \cdot \frac{\sum_{i=1}^{M} \boldsymbol{x}_{i}}{M}, 0\right\} \end{aligned}$

​ 其实就是两个节点越相似，权重越大。这里还有一点内容没介绍，就是$\Gamma$的具体计算方法，上面那个公式其实是给了一个方程 组，需要求解$\Gamma$矩阵，感兴趣可以自己去看原文。

得到g-EMD的具体定义后，对比损失定义如下：

$\begin{gathered} \quad \ell\left(\mathbf{Z}_{1}^{(i)}, \mathbf{Z}_{2}^{(i)}\right)= \\ -\log \left(\frac{e^{\left.\mathrm{s}\left(\mathbf{Z}_{1}^{(i)}, \mathbf{Z}_{2}^{(i)}\right)\right) / \tau}}{\sum_{k=1}^{N} e^{\left.\mathrm{s}\left(\mathbf{Z}_{1}^{(i)}, \mathbf{Z}_{2}^{(k)}\right)\right) / \tau}+\sum_{k=1}^{N} \mathbf{1}_{[k \neq i]} e^{\left.\mathrm{s}\left(\mathbf{Z}_{1}^{(i)}, \mathbf{Z}_{1}^{(k)}\right)\right) / \tau}}\right) \end{gathered}$

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

整体格式和传统GCL方法没什么区别，唯一一点区别就是函数$s(\cdot)$，以前的方法都是采用余弦相似度函数，这里改成了g-EMD函数。

对抗训练

这个没什么好说的，感觉是作者拉过来凑数的，让工作显得更丰富一些：

$\min _{\theta, \omega} \mathbb{E}_{\left(\mathbf{X}_{1}^{(i)}, \mathbf{X}_{2}^{(i)}\right) \sim \mathbb{D}}\left[\frac{1}{M} \sum_{t=0}^{M-1} \max _{\delta_{t} \in \mathcal{I}_{t}} \mathcal{J}\left(\mathbf{X}_{1}^{(i)}+\delta_{t}, \mathbf{X}_{2}^{(i)}\right)\right]$

这个也不是本文的重点，这里就不细说了。

3. 实验

1. 同构图

   

2. 异构图

   

3. 大规模图

   

4. 动态图

   

5. 消融实验

   

6. 可视化1

   

7. 可视化2