自监督-Self-Supervised Graph Representation Learning via Global Context Prediction
标签：自监督学习、图神经网络
动机
- 在没有手工标注的情况下, 如何设计合适的目标函数学习理想的节点表示是个具有挑战的任务, 如何有效捕获图的整体结构仍然是一个具有挑战的问题
- 更加充分的利用数据本身的问题
贡献
- 首次尝试研究隐藏在图结构数据中的自然监督信号, 即条数, 并利用该信号以自监督方式来学习未标记数据集上的节点表示
- 我们提出一个有效的自监督学习框架 \(S^2GRL\) 训练一个神经网络预测节点对之间的相对上下文位置, 学习全局上下文感知的节点表示
- 进行广泛的实验来评估三个常见学习任务的 \(S^2GRL\) 结果表明, 与最先进的无监督方法相比, 该方法表现较好的性能
思想
定义
符号定义
一个无向图 \(\mathcal{G} = \{\mathcal{V}, \mathcal{E}, \mathcal{F}\}\), 顶点集合 \(|\mathcal{V}| = n\), 边集合 \(\mathcal{E} = m\), \(v_i \in \mathcal{V}\) 并且附属一个 \(d\) 维的属性(特征) \(\mathcal{F} = {f_1, f_2, ..., f_d}\). \(X = [X_1, X_2, ···,x_n]^T \in \mathbb{R}^{n \times d}\) 是 \(n\) 个节点的属性, 是\(A \in \{0, 1\}^{n \times n}\) 是一个邻接矩阵
框架
算法
Problem Formulation
目的是训练一个编码器 \(f_w\) , 从输入图本身自动获得自监督指导将每一个节点投影到 \(q\) 维空间中 \(\mathbb{R}^q\), 而不是通过外部注释标签, 这样节点将在全局上下文表示为 \(Z = [z_1,z_2,...,z_n]^T \in \mathbb{R}^{n \times q}\) , 这个自由监督信号作为为标签 \(\hat{Y}\) 去训练编码器 \(f_w\) :
\[min_{w, \theta} \mathcal{L}(\hat{Y}, h_{\theta}(f_{w}(X,A))) \]其中 \(h_{\theta}\) 是预测伪标签的分类器.构建特定的伪标签 \(\hat{Y}\) 使得所需的信息可以再借点表示编码
Global Context of A Node
假设 $\mathcal{G} $ 中所有节点都能成为节点 \(v_i\) 的全局上下文信息, \(v_j \in \mathcal{G}\) 和 \(v_i\) 之间存在一条路径 \(p_{i,j}\) 使其进行交互, 这样的的全局上下文所包含的比基于随机游走固定窗口所包含的信息更综合. 形式上, \(v_i\) 的全局信息被表示为 \(\mathcal{C} = \mathcal{V} - \{v_i\}\), 为了对全局信息进行编码, 在 \(\mathcal{G}\) 中给定节点情况下, 估计预测上下文信息的似然:
\[Pr(\mathcal{C}_i | v_i) \]为了学习表示, 我们将图编码器 \(f_w\) 引入上式, 它表示节点共现的概率分布,然后产生一个最大化对数概率的优化问题:
\[max_{w} \sum_{v_i \in \mathcal{V}} \log \Pr (\mathcal{C}|f_w{(v_i)}) \]然后基于独立假设对优化问题的目标函数进行因子分解:
\[\Pr(\mathcal{C}|f_w{(v_i)}) = \prod_{v_i \in \mathcal{C}_i} \Pr(v_j | f_w(v_i)) \]对于节点对 \(v_i\) 和 \(v_j\) 的条件似然, 一个经典的解决方法使定义 softmax 函数
然后使用特定的分类器来学习这种后验分布, 例如使用逻辑回归来预测上下文. 但这样的模型将导致大量的类别等于 \(|V|\), 消耗大量的计算资源. 此外, 在我们的全局上下文假设下, 分类器不能被训练正常工作, 因为所有的目标类都是正的. 因此, 我们提出了另一种预测 \(\Pr (v_j| f_ω(v_i))\) 的策略, 利用跳数作为监督, 以细粒度的方式指导全局上下文预测
A Natural Supervisory Signal: Hop Count
定义: 基于跳的上下文 \(\mathcal{C}_i\) 包含一组可以到达节点 \(v_i\) 通过不同跳数的最短路径, 即由多个特定 \(k-hop\) 上下文 \(\mathcal{C}_i^k\) 组成的 \(\mathcal{C}_i\) 只包含 \(k\) 跳的节点:
\[\mathcal{C}_i = \mathcal{C}_i^{1} \cup \mathcal{C}_i^{2} \cup ...\mathcal{C}_i^{\delta_i},\\ and~~~~~ \mathcal{C}_i^k = \{v_j | d_{i,j} = k\}, k = 1, 2, ..., \delta_i \]\(\delta_i\) 的上界是 \(v_i\) 到其他节点的跳数, \(d_{i,j}\) 是路径 \(p_{i,j}\) 的长度.
这样, 对于每一个目标节点 \(v_i\) 的, 按照 \(\mathcal{C_i}\) 用着 \(\delta_i\) 分类和伪标签 \(Y_i = \{0, 1, ... , \delta_i - 1\}\), 通过解决以下优化问题预测 \(v_i\) 和 \(v_j\) 之间的跳数:
\[min_{w, \theta} \sum _{v_j \in \mathcal{C}_i} \mathcal{L}(Y_i, h_{\theta}(\langle f_w(v_i), f_w(v_j)\rangle)) \]其中 \(\langle \cdot, \cdot\rangle\) 这是一种用来测量两个向量之间相互作用的运算, 需要注意的是, 上式在实际中很难求解, 因为不同目标节点的跳数 \(δ\) 的上界是不同的, 对于大图来说, 要精确确定 \(δ\) 并不容易. 因此, 修改它以适应现实情况是必要的. 灵感来自于小世界现象表明, 两个实体在网络六个或更少的连接彼此远离, 假设节点之间的跳数是在一定的范围内, 无法控制. 因此, 对于每个节点 \(v_i\) 上的 \(δ\) 类, 我们通过合并多个类, 将它们划分为 \(α\) 主要类, 并相应地更新伪标签为\(\hat{Y} =\{0,1，···，α?1\}\). 然后, 我们得到了所提出的 \(S^2GRL\) 的目标函数:
\[min_{\theta, w} \sum_{v_i \in \mathcal{V}} \sum_{v_j \in \mathcal{C}_i} \mathcal{L}(\hat{Y}, h_{\theta}(\langle f_w{(v_i)}, f_w(v_j)\rangle)) \]“主要”类别的设计遵循明确区分差异和部分容忍的原则相似之处. 例如, 一个节点和它的 \(1\) 跳上下文之间的交互程度与它的 \(2\) 跳上下文明显不同, 因为你可能不知道你朋友的朋友. 因此, 将他们视为两个“主要”类别是恰当的. 相比之下, 高跳上下文之间的区别相对模糊, 将它们合并为一个“主要”类似乎更合理. \(α\) 表示此类预定义类的数量. 一个简单的解决方案是将 \(1\) 跳上下文视为一个类, 其余的视为另一个类, 这类似于重建邻接矩阵 \(A\) 的思想. 现在, 编码器 \(f_ω\) 和分类器 \(h_θ\) 的参数可以通过优化上式共同学习, 优化后的 \(f_ω\) 的输出就是我们想要的表示
实验
节点分类任务.
总结
提出了一种用于学习节点表示的新型自监督框架 \(S^2GRL\), 这是探索用于表示学习的图结构数据中的监督信号的第一次尝试. 大量实验证明了我们框架的有效性