【论文阅读】Self-Supervised Graph Representation Learning via Global Context Prediction
0 摘要
为了充分挖掘快速发展的趋势下的海量无标注网络数据，在本文中我们提出了一种新的自监督学习策略。该策略能够有效提取这些数据所蕴含的信息。
的自然监督来进行图表示学习
我们探究全局上下文能否作为生成有用节点表示的基础监督信号
从图中的若干节点对中随机选取样本数据集，并被用来训练一个深度设计的神经网络以推断各节点间的相对位置关系
1 介绍
应该学习什么 一直是无监督学习的核心问题
不借助人工标注的情况下，如何构建合适的度量标准以指导生成节点的理想表示，构成一个具有挑战性的研究难点。
如何有效地捕捉图的整体结构 仍然是一个具有挑战性的问题
本文：
- 该方法采用了路径步长这一指标来表征全局上下文信息。研究发现，在实际应用中发现路径步长与节点间相似性之间存在显著关联性。
- 在预测图中的一对节点的位置关系分析上展开了深入研究，并在此基础上提出了一种新的自监督式图表示学习框架S ^2GRL。
- 该模型通过学习各节点的特征向量来捕捉网络中的全局拓扑结构特征，并能有效区分不同节点对间的相似度差异
贡献总结：
- 本次研究首次开展对图结构数据中天然存在的监督信号——跳数的探究，并通过该信号实现未标记数据集上节点表示的自监督学习。
- 本研究开发出一种高效自监督学习框架S^2GRL，并运用神经网络预测节点对间的相对上下文位置关系，以实现全局视角下的节点表示学习。
- 本研究展开了系统性的实验评估，在分类、回归和图嵌入等三大典型任务上均进行了深入测试。结果显示，在与当前最先进的无 supervised 方法相比时具有相当竞争力的表现，并在某些领域甚至超越了部分强劲的有 supervision 基准。
3 方法
3.1 问题描述
主要目标在于训练编码器f_\omega，在输入图自身上通过自然监督机制实现每个节点的投影。该过程使得所有节点在全局视角下表示为矩阵形式：即所有节点嵌入构成n\times q维实数矩阵形式：Z = [z_1,z_2,\cdots,z_n]^T\in\mathbb{R}^{n\times q}其中每一列向量代表某个特定节点在整个图中的嵌入表示。其对应的伪标签\hat{Y}则用于指导编码器f_\omega的优化过程
\min_{\omega, \theta} \mathcal{L}(\hat{Y}, h_\theta (f_\omega(X,A)))
- h_\theta：该分类器用于识别伪标签。
- 通过构建特定的伪标签集\hat{Y}以便所需信息得以在节点表示中进行编码。
3.2 一个节点的全局上下文
假设\mathcal{G}中的所有节点共同构成了节点v_i的全局背景；任何其他节点v_j \in \mathcal{G}都可以通过路径p_{ij}与其进行交互；相比基于随机游走算法限定窗口大小所限定的上下文范围而言，这种交互方式更为广泛。
节点v_i的全局上下文定义为\mathcal{C}_i = \mathcal{V} - \{v_i\}
为了实现对整体信息的编码目标，在给定图\mathcal{G}中的任一节点情况下计算该节点与其邻域之间的可能性关系
Pr(\mathcal{C}_i | v_i)
在研究表征的过程中, 我们开发了一个图编码器f_\omega, 该编码器构建了一个基于节点共现的概率模型, 并最终导出了一个最大对数概率的优化问题.
\max_\omega \sum_{v_i \in \mathcal{V}} log Pr (\mathcal{C}_i|f_\omega(v_i))
根据独立性假设，将目标函数分解：
Pr(\mathcal{C}_i | f_\omega(v_i)) = \prod_{v_j \in \mathcal{C}_i}Pr(v_j|f_\omega(v_i))
对于每一对节点v_i和v_j的条件概率而言，一种常见的方法是通过构建一个softmax函数来实现。
条件概率Pr(v_j | f_\omega(v_i))等于分子部分指数函数exp(f_\omega(v_j)与f_\omega(v_i)的点积)，除以分母总和∑_{u∈V}指数函数exp(f_\\omega (u)^Tf_\(\omega) (v_i)))
然后通过选定一个特定分类模型来训练这种后验概率分布P(y|C)。例如，在文本中我们可以利用逻辑回归模型基于上下文信息进行预测。
但是这样的模型会带来大量的类别数量达到|V|的数量级，并耗费巨大的计算资源。此外，在基于我们的假设前提下，在分类器设计过程中难以实现正常工作状态的原因是由于所有目标类被归类为正样本。
因此，在深入分析现有方法的基础上
3.3 一种自然监督信号：跳数
我们为每个节点v_i定义了一个居于hop的全局上下文\mathcal{C}_i
任何一个节点v_i只会被唯一地分配到一个特定的k-step context中\mathcal{C}_i^k内，并非其他任何k’\text{-step} contexts会包含该节点
注意到的是，在本研究中我们关注节点间交互水平时
由于当两个节点间的最短路径非常长时，其间的通信必须经过许多中间节点而导致它们之间的互动水平较低，在这种情况下两者之间距离较近时其相互关系就越密切
考虑每个目标节点v_i，它包含\delta_i个类别，则其伪标签定义为Y_i = \{0,1,\cdots,\delta_i-1\}。其学习目标即为预测任意两个节点间的最短路径长度（也即它们之间的相对位置关系）。
最小化关于ω和θ的值；
对属于类别C_i的所有v_j进行计算；
损失函数L基于Y_i与h_θ(f_ω(v_i)与f_ω(v_j)之间的内积)
- \langle \cdot,\cdot \rangle：是用于测量两个向量之间相互作用的操作
（相对位置如何拓展到具体的下游任务分类中？）
在特定时间段内，上述式子难以实现。这是因为不同目标节点之间的跳数δ有不同的上限，并且对于大规模图而言，精确计算δ并非易事
所以将目标函数修改为：
该优化目标是最小化关于参数ω与θ的损失函数总和；具体而言，在所有样本点vi与它们所属类别中的其他样本vj之间计算预测结果与真实值之间的差异。
最简单的做法是将一跳邻居分为一类。其他的是另一类
编码器f_\omega和分类器h_\theta的参数能够被数学模型所利用以实现协同训练，在经过优化后生成的f_\omega能够提供所需的特征表示
4 实验
4.1 数据集
4.2 Baseline
两类最先进的无监督方法：基于随机游走的算法、GNN
随机游走：DeepWalk、node2vec
GNN：EP-B、DGI、graphite、GMNN、unsupervised GraphSAGE、AGC
监督方法：GCN、GAT、GWNN、GMNN、Adapt
4.3 实验设置
Detailed architecture of S^2GRL
在inductive任务中（PPI、Reddit），该编码器模块采用了两个512神经元Graph Convolutional（GC）层；对于其他类型的任务，则采用了单个512神经元Graph Convolutional（GC）层
内积\langle \cdot, \cdot, \rangle用于评估节点间的相互作用程度，在本研究中采用两个向量之间的距离作为度量依据，并定义为\langle z_i, z_j \rangle = |z_i - z_j|。
确定了一个包含四个子类群的分类体系：其中第一类包括两个独立的子集；第二类由两个并集构成；第三类则由多个子集组成，并列出现以增强描述的完整性
Sampling strategy
因为跳的数量较大，这将引起类内节点数量失衡的问题。为了有效解决这一问题，在分类均匀分布的基础上，我们采用了分批选取的方式。
我们可以先从图G中随机选取一批具有固定数量的目标节点。接着，在每个'major'类别中按照自适应比例抽取相应的节点对进行配对处理。这样做的目的是为了实现类间的均衡分布。
Evaluation metrics
利用学习得到的特征向量作为输入对一个基础的逻辑回归模型进行训练，并通过该模型评估节点级别的分类效果
在聚类任务中，采用K-means算法对学习得到的一系列embedding进行分类处理，并采用NMI作为评估标准。
对于链路预测任务，评价指标：AUC
4.4 实验结果
节点分类
本文提出的算法优于其它无监督算法，尤其是在PPI和Pubmed
据我们所知，在提取高质量表示能力方面 自 监督学习相较于传统 监督方式 拥有更大的潜力 由于通过数据本身构建的 监督机制 能够更加高效地捕获数据的本质特征
聚类
然而我们的简单框架S2GRL也展现出强大的竞争力并在Pubmed上取得了比其他方法更高的NMI值
链路预测
本文提出了一种新的策略，在面对不同程度的边去除率时始终表现出比DGI和node2vec更好的效果。研究表明，通过全局上下文预测学习得到的表示不仅能够从整体拓扑结构出发巧妙地区分节点间的相似性与差异性，并且能够在这一过程中展现出独特的特性。此外，在这一过程中还能够有效地预测缺失的链接关系。
4.5 关于标签类别的进一步讨论
实验结果表明，在对1hop、2hop和3hop进行分类时能够显著增强表示能力
虽然仅采用1-hop可区分类别的数量有限，并且由于high-order context differences are unclear, 因此无法允许类别数目过多
在实验过程中, 我们构建了一个将3跳和4跳归类到同一类别的新方案, 这一方法实现了更高的经验性能。
5 结论
我们开发了一种新设计的自监督框架 S^2GRL, 专为学习节点表示而创建。从我们的了解来看, 这是一项开创性的工作, 首次深入研究了图结构数据中的监督信号。大量实验证明了其有效性, 并展示了显著性能优势。这一成果有望激发更多研究关注自监督图表示学习领域。