文献地址：https://arxiv.org/abs/2008.11416

摘要

图神经网络 (Graph Neural Network, GNN)：一种流行的节点表示方法
目前的专注点：
- 保持图的 平滑性
- 保持节点表示的 可识别性
健壮的图节点表示：既能够抵抗轻微的输入扰动，还可以保持节点良好的区分度
对比图神经网络 (contractive graph neural network, CGNN)：以 无监督 的方式学习健壮的节点表示，即通过一个对比学习目标保持 稳定性 和 平滑性，同时还保留了现有GNN模型的 平滑性
特点：该方法得到的框架可以与其他现有的GNN模型配套使用
过程：
- 首先通过大量理论推导对CGNN的方法进行描述和公式推导
- 然后在实验方面从四个不同的角度进行广泛的验证，在转导和归纳学习设置下的基准测试证明，CGNN与最近的有监督和无监督方法相比能够在保持图的平滑度和节点表示的可识别性上取得更好的结果。

介绍

图节点表示的 平滑性 、可识别性 、稳定性

一个说明节点表示的图例
- $v_0$ 是锚节点
- $v_1$ 是与锚节点 $v_0$ 相关的点【邻居】
- $v_6$ 是与锚节点 $v_0$ 不相关的点【非邻居】
- 使用子邻居表示锚节点 $v_0$ 轻微变动的邻居
- 平滑性：节点 $v_0$ 和节点 $v_1$ 在嵌入空间中的距离尽可能近
- 可识别性：节点 $v_0$ 和节点 $v_6$ 在嵌入空间中的距离尽可能近
- 稳定性：对于轻微变动的邻居，节点 $v_0$ 的表示是稳定的
实现方式：
- 平滑性 通过一个GNN模型进行维护，该GNN模型工作类似于特征提取器
- 可识别性 和 稳定性 由对比学习目标维护
对比学习目标
- 作用：在具有不同扰动的情况下，估计相同节点表示的高相似性，以及不同节点表示的低相似性
贡献：
- 研究了基于图上节点邻居抽样的鲁棒节点表示方法的局限性
- 提出了对照图神经网络CGNN，为众多图论算法的鲁棒性设计提供了一个新的视角
- CGNN的模型框架可以为GNN缓解过拟合问题的相关研究提供参考

对比图神经网络

节点表示问题
- 定义：给定无向图 $G = (V, E)$ ，其中 $V = \{v_i|1\leq i \leq N\}$ 表示图中的节点， $E = \{ e_{ij}| 1\leq i, j \leq N\}$ 表示节点之间的连接
  $e_{ij}= \begin{cases} 1& \text{节点i与节点j存在连接}\\ 0& \text{节点i与节点j不存在连接} \end{cases}$
- 邻接矩阵 $A \in R^{N \times N}$ ，该矩阵及其稀疏，并且由0,1组成
- 目的：将节点表示为具有代表性的嵌入，其可以应用于其余的任务【节点分类】

抽样邻居的稳定性

实现稳定性的直观方法：从具有轻微变化的输入中强制得到节点表示，使得该节点表示与真是节点表示相似
我们的方法：在节点扰动不同时，在同一节点表示之间得到 稳定性
换句话说：任意给定一个锚点 $v_0$ , 将该节点的原始邻居表示为 $N_0$ ，为了在邻居 $N_0$ 上制造扰动，我们以 $\rho$ 的几率随机丢弃 $N_0$ 的边，令 $p(N_0, \rho)$ 是带有 $\rho$ 的 $N_0$ 的分布，在每一step中，得到 $p(N_0, \rho)$ 的多样本的稳定性是计算效率低下的，我们的方法是采用等效的方法，在不同的steps中，在 $p(N_0, \rho)$ 中的每两个随机样本之间得到稳定性，然后，如果我们将 $N_0^1$ 和 $N_0^2$ 考虑为 $N_0$ 的子邻居的话，即有 $N_0^1, N_0^2 \sim p(N_0, \rho)$ ，其中 $N_0^1$ 和 $N_0^2$ 是两个不同的子邻居，因为它们是在两个独立的步骤中随机drop得到的结果。令 $f_\theta$ 是具有平滑特性的GNN 框架，我们可以得到 $z_0^1 = f_\theta (N_0^1)$ , $z_0^2 = f_\theta (N_0^2)$ ，其中 $z_0^1$ 和 $z_0^2$ 分别是来自于 $N_0^1$ 和 $N_0^2$ 的锚节点表示。

稳定性和可识别性的对比损失

得到稳定性和可识别性：我们在CGNN中使用对比损失
- 稳定性：相同的节点在不同的扰动下可以得到高度相似的节点表示
- 可识别性：不同的节点在不同的扰动下得到不同的节点表示
CGNN的整体架构图：

CGNN架构图
- $(z_0^1, z_0^2)$ 是相似的表示【同一节点】， $(z_0^1, z_j^2)$ 是不同表示【不同节点】。
- $(z_0^1, z_0^2)$ 和 $(z_0^1, z_j^2)$ 之间的标准闭信号表示为 $L_1 = -E_{\{ z_0^1, z_0^2, z_j^2\} |_{j=1}^K} [\log \frac {h_\phi(z_0^1, z_0^2)}{\sum_{j=0}^K h_\phi (z_0^1, z_j^2)}]$
- 其中 $h_\phi$ 表示分数函数——成对的样本分数较高，不成对的样本分数较低
- $K$ 表示为配对样本的数目
- 分数函数的实现 $h_\phi (z_0^1, z_0^2) = e^{z_0^{1^T}\frac {z_0^2}{\tau}}$
- 其中 $\tau$ 表示控制分数函数的随机性
- 使用 $z_0^2$ 替换公式 $L_1 = -E_{\{ z_0^1, z_0^2, z_j^2\} |_{j=1}^K} [\log \frac {h_\phi(z_0^1, z_0^2)}{\sum_{j=0}^K h_\phi (z_0^1, z_j^2)}]$ 中的 $z_0^1$ ，此时得到公式： $L_1 = -E_{\{ z_0^2, z_0^`, z_j^`\} |_{j=1}^K} [\log \frac {h_\phi(z_0^2, z_0^1)}{\sum_{j=0}^K h_\phi (z_0^2, z_j^1)}]$
- 最终的对比损失表示 $\min_\theta L = L_1 + L_2$ ，其中 $\theta$ 是GNN框架模型的唯一的参数
- 最终得到的 $L$ 本质上是一个估计器，用来最大化 $z_0^1$ 和 $z_0^2$ 之间的互信息，即 $I(z_0^1, z_0^2) \geq \log(K) - L$
- $L$ 是 $I(z_0^1, z_0^2)$ 的下边界， $K$ 越大，下边界越小
- 最小化 $L$ 实际上就是在某个特定方向上最大化 $z_0^1$ 和 $z_0^2$ 之间的互信息
- 在那一个方向上，成对的节点表示比未成对的节点表示更相似或相关

近似噪声对比估计

上述公式中存在的问题：在 $K$ 值较大的情况下， $L_1$ 和 $L_2$ 公式中的 $softmax$ 操作计算效率低下
解决方案：使用 噪声对比估计 (Noise contrastive estimation, NCE)
NCE 是用来估计非标准化统计模型的收敛估计
NCE 的基本思想：使用非线性逻辑回归去判别观察到的数据和人工加入噪音后的数据
公式说明：
对于 $z_0^1$
$z_x^2$ 是一个变量 $z_x^2= \begin{cases} z_0^2& \text{配对}\\ z_j^2& \text{不配对} \end{cases}$
二进制潜变量 $c$ $c= \begin{cases} 1& \text{配对}\\ 0& \text{不配对} \end{cases}$
$c = 1$ 的概率表示： $p(c=1|z_0^1, z_x^2) = \frac {p_d(z_x^2|z_0^1)}{p_d(z_x^2|z_0^1) + Kp_n(z_x^2|z_0^1)}$
- $p( \cdot, \cdot)$ 表示数据分布
- $p_n(\cdot, \cdot)$ 表示噪声分布，并且 $p_n ( \cdot | z_1^0) = \frac 1N$
我们使用非归一化模型 $h_\phi (z_0^1, z_x^2)$ 代替 $p_d(z_x^2|z_0^1)$ ，并且 $c$ 满足伯努利分布，即可以得到 $L_1$ 的 NCE表达： $L_{1-NCE} = -E_{\{z_0^1, z_0^2, z_j^2|_{j=1}^K\}} \log(p(c=1|z_0^1, z_0^2)) + K\log (p(c=0|z_0^1, z_j^2))]$
同样，可以分别得到 $L_{NCE}$ 和 $L_{2-NCE}$ ： $L_{2-NCE} = -E_{\{z_0^2, z_0^1, z_j^1|_{j=1}^K\}} \log(p(c=1|z_0^2, z_0^1)) + K\log (p(c=0|z_0^2, z_j^1))]$
$L_{NCE} = L_{1-NCE} + L_{2-NCE}$
最终目标函数 $L_{NCE}$
方式：具有多个邻居的同一节点的表示为正样本，不同节点的表示为负样本。通过分区正负样本，NCE目标学习同一节点不同变体的共同因素，同时识别出不相关因素

加速训练的策略

DropEdge 采样策略：
- 训练 epochs 为 $T$
- 构造 $N$ 个节点的各个子邻居的复杂度为 $O(NT)$
- DropEdge：在每个epoch中随机在邻接矩阵A上丢弃一些边
- 然后将具有轻微扰动的邻接矩阵 $A^1$ 和 $A^2$ 用于训练模型【而不是使用原来的 $N_0^1$ 和 $N_0^2$ 】
Memory Bank 策略：
- 为了有效地为 $L_{NCE}$ 采得 K 个噪声样本
- 所有节点的潜特征都存储在内存中，在损失反向传播中进行同步更新
- 使用这种方式可以动态地优化目标函数 $L_{NCE}$

基于小图的取样

NCE 估计是一个低方差高偏差的估计量，即需要采样大小K足够大才能得到紧密的下界【为了收敛】
对于图上任意一个节点 $v_0$
较大的采样大小 K 会导致得到 $v_0$ 的相似表示的风险，因而造成错误的对比信号
给定一个具有 N 个节点的图 G
K 表示为采样的未配对节点的集合
M 表示在嵌入空间中具有相似表示的节点的集合
命题：
- 对于图 G 中的一个任意节点 $v_0$
- 在 K 上取得相似的节点的风险为
  - 当 N 大 M 小时，可以得到低风险
  - 其中 $|\cdot|$ 表示集合的长度
  - 当数据集太小或者节点 $v_0$ 的相似节点数太大时，将会在错误方向优化公式 $L_{NCE}$

与其他方法的比较

以前的GNN模型能够保留平滑性特点
对于有监督的GNN方法
- 可识别性可以通过足够的标签来保留【需要耗费大量的人力来标注】
我们的方法在保留稳定性的同时，还以无监督的方式学习了健壮的节点表示
DGI 是一种基于最大化互信息的无监督学习方法
- 最大化节点表示形式和相应的高级图表示形式之间的互信息
- 在保留节点高阶信息的同时还得到了更好的平滑性
CGNN 最大化具有不同扰动的相同节点表示的互信息，通过对比目标，保持稳定性和可识别性

实验和分析

数据集描述

四个基准数据集

四个基准数据集
数据集说明
- Pubmed：广泛使用的引文网络
- Facebook：一个网页数据集
  - 节点：网页首页
  - 边：站点之间的连接
- Coauthor-CS / Coauthor-Phy：合著者数据集
设置：
- 对于 Pubmed， Facebook， Coauthor-CS，我们进行转导学习，在训练过程中，可以访问所有节点机器原始特征
- 对于 Coauthor-Phy，我们进行归纳学习，即在训练期间没有使用测试节点
数据划分
- 对于Pubmed，使用半监督学习的常见数据划分
- 对于Faceboook和Coauthor-CS，我们使用每个类别的20个节点是训练集，每个列表的30个节点是验证集，其余的是测试集
- 对于Coauthor-Phy，随机抽取20000个节点作为训练集，并抽取5000个节点作为验证集，其余的作为测试集

实验设置

基准
- 有监督方法：
  - GCN
  - JKNet
  - GraphSage
  - GAT
  - ResGCN
  - DropEdge
- 无监督方法：
  - DGI
参数设置
- 维度设置：128
- 迭代：学习率为0.001迭代5000次
- drop 比率： $\rho = 0.3$
- temperature: $\tau = 0.1$
- 采样大小： $K = 1024$