图神经网络学习日记（三）节点嵌入
节点嵌入目的是将节点编码为包含图位置和局部邻域结构信息的低维向量，其几何关系与原始图或网络中的关系相对应。
简单加权图节点嵌入
基于编码-解码框架
编码器将图中每个节点映射为低维向量或低维嵌入，解码器将利用低维节点嵌入重构原始图中每一个节点的邻域信息。
编码器
编码器将节点 \(v \in \mathcal{V}\) 映射为向量嵌入 \(z_v \in \mathbb{R}^d\) ，其中，\(z_v\) 为节点 \(v \in \mathcal{V}\) 对应的嵌入表示，可表示为下式： \[ \mathrm{ENC}: \mathcal{V} \rightarrow \mathbb{R}^d \] 编码器依赖 shallow embedding 方法，即根据节点的 ID 进行简单地嵌入查找，如下式： \[ \mathrm{ENC}(v) = Z[v] \] 其中，\(Z \in \mathbb{R}^{|\mathcal{V}| \times d}\) 为包含所有节点嵌入向量的矩阵，\(Z[v]\) 表示节点 \(v\) 对应 \(Z\) 的某一行向量。
解码器
解码器的任务是根据解码器生成的节点嵌入重构某些确定的图形统计信息。
标准形式为成对的解码器，如下式： \[ \mathrm{DEC}:\mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}^+ \] 成对的解码器可以预测成对出现的节点的关系和相似性。
在一对节点的嵌入表示 \((z_u,z_v)\) 中使用成对解码器，能重构节点 \(u\) 和 \(v\) 之间的关系。重构的目标在于通过最小化重构损失来优化编码器和解码器，如下式： \[ \mathrm{DEC}(\mathrm{ENC}(u),\mathrm{ENC}(v)) = \mathrm{DEC}(z_u,z_v) \approx S[u,v] \] 其中，假定 \(S[u,v]\) 是基于图的节点间相似性的度量。
损失函数
实现重构目标函数的标准操作是在一组训练节点对 \(\mathcal{D}\) 上最小化经验重构损失 \(\mathcal{L}\) ，如下式： \[ \mathcal{L} = \sum_{(u,v)\in \mathcal{D}} \mathcal{l}(\mathrm{DEC}(z_u,z_v),S[u,v]) \] 其中，\(\mathcal{l}: \mathbb{R} \times \mathbb{R}\) 是衡量解码后的近似值 \(\mathrm{DEC}(z_u,z_v)\) 与真值 \(S[u,v]\) 之间差异的函数。在训练集 \(\mathcal{D}\) 上，全过程的目标就是通过训练编码器和解码器，有效地重构成对节点的关系信息。
基于因式分解的方法
节点嵌入表示来解码局部邻居结构与在图的邻接矩阵中重构邻居密切相关，邻接矩阵中重构邻居是使用矩阵分解来学习节点-节点相似性矩阵 \(S\) 的低维表示，其中， \(S\) 概括了邻接矩阵并且能描述用户定义的节点-节点的相似性概念。
拉普拉斯特征映射
使用基于节点嵌入之间的 \(L_2\) 距离定义解码器，如下式： \[ \mathrm{DEC}(z_u,z_v) = ||z_u - z_v||_2^2 \] 根据节点在图中的相似性对节点对进行加权，以得到最终的损失函数，如下式： \[ \mathcal{L} = \sum_{(u,v) \in \mathcal{D}} \mathrm{DEC}(z_u,z_v) \cdot S[u,v] \] 内积法
基于内积的解码器，如下式： \[ \mathrm{DEC}(z_u,z_v) = z_u^Tz_v \] 假设两个节点之间的相似度（如这两个节点局部邻域之间重叠的部分）与节点嵌入表示的点积成正比。
损失函数如下式： \[ \mathcal{L} = \sum_{(u,v) \in \mathcal{D}} ||\mathrm{DEC}(z_u,z_v)-S[u,v]||_2^2 \] 将节点嵌入表示 \(z_u \in \mathbb{R}^d\) 堆叠为矩阵 \(Z \in \mathbb{R}^{|\mathcal{V}| \times d}\) ，则可以将目标函数写成下式： \[ \mathcal{L} = ||{ZZ^T}_2^2|| \]
随机游走嵌入表示
随机游走嵌入表示是内积法应用于邻域重构的随机度量计算的方法。
Deepwalk 和 node2vec
Deepwalk 和 node2vec 使用了 shallow embedding 方法和内积解码器，巧妙的定义相似度和邻域重构的概念，通过优化嵌入表示对随机游走的统计信息进行编码。通过学习节点嵌入使得下式成立： \[ \mathrm{DEC}(z_u,z_v) \overset{d}{=} \frac{e^{z_u^Tz_v}}{\sum_{v_k \in \mathcal{V}}e^{z_u^Tz_k}} \approx p_{\mathcal{g},T}(v|u) \] 其中，\(p_{\mathcal{g},T}(v|u)\) 是指从节点 \(u\) 出发，随机游走 \(T\) 步后访问节点 \(v\) 的概率，\(T \in {2,\cdots}, 10\)。
通过上式的解码器使用下式训练随机游走嵌入： \[ \mathcal{L} = \sum_{(u,v) \in \mathcal{D}} -log(\mathrm{DEC}(z_u,z_v)) \] 通过从每一个节点开始进行随机游走采样，可以生成随机游走的训练集，并用 \(\mathcal{D}\) 表示。
上式损失函数时间复杂度为 \(O(|\mathcal{D}||\mathcal{V}|)\) 。Deepwalk 使用层次的 softmax 函数近似表示解码器，主要通过利用二叉树结构来加速计算，node2vec 使用噪声对比方法近似表示损失函数，使用下式所示的负样本近似表示归一化引子： \[ \mathcal{L} = \sum_{(u,v)\in \mathcal{D}} -log(\sigma(z_u^T,z_v)) - \gamma \mathbb{E}_{v_n \sim P_n(\mathcal{V})}[log(-\sigma(z_u^T,z_{v_n}))] \] 其中，\(\sigma\) 表示 log 激活函数， \(P_n(\mathcal{V})\) 表示节点 \(\mathcal{V}\) 的分布，\(\gamma > 0\) 为超参数。\(P_n(\mathcal{V})\) 往往服从均匀分布，且期望值可采用蒙特卡洛算法近似计算。
Deepwalk 只简单使用均匀的随机游走来定义分布 \(p_{\mathcal{g},T}(v|u)\)，而 node2vec 方法引入了超参数，这些超参数允许随机游走在于图的广度优先搜索或深度优先搜索更相似的游走的概率之间平滑地插值。
随机游走与矩阵分解方法
假设定义下式为节点-节点相似度矩阵的值： \[ S_{DW} = log(\frac{vol(\mathcal{V})}{T}(\sum_{t=1}^TP^t)D^{-1})-log(b) \] 其中 \(b\) 为常值，\(P=D^{-1}A\) 。
还可以将上式内部的部分表示分解成下式所示形式： \[ (\sum_{t=1}^TP^T)D^{-1} = D^{-\frac{1}{2}}(U(\sum_{t=1}^T\Lambda^t)U^T)D^{-\frac{1}{2}} \] 其中，\(U\Lambda U^T=L_{sym}\) 是对称归一化拉普拉斯算子的本征分解。
裘捷中等提出通过 DeepWalk 学习到的嵌入 \(Z\) 需满足下式要求： \[ Z^TZ \approx S_{DW} \] shallow embedding 的局限性
shallow embedding 方法不会在编码器的节点之间共享任何参数，因为编码器会直接为每个节点优化唯一的嵌入向量，不进行参数共享会导致算法在统计和计算过程中效率低下。
shallow embedding 方法没有利用编码器中的节点特征。
shallow embedding 方法是转导性（[[基本概念#Transductive learning|Transductive]] ）的，只能为训练过程中存在的节点生成嵌入，无法为训练之后出现的新节点生成嵌入。
多关系图节点嵌入
设多关系图为 \(\mathcal{G} = (\mathcal{V}, \varepsilon)\)，其中边被定义为元组 \(e=(u,\tau,v)\) 中两个节点间存在的特定关系 \(\tau \in \mathcal{T}\)。
可以将嵌入多关系图视作重构任务，即给定两个节点的嵌入表示 \(z_u\) 和 \(z_v\)，重构这些节点之间的关系。将解码器定义为可同时输入一对节点嵌入及一个关系类型（\(\mathrm{DEC}: \mathbb{R}^d \times \mathcal{R} \times \mathbb{R}^d \rightarrow \mathbb{R}+\)），将解码器的输出（\(\mathrm{DEC}(z_u,\tau,z_v)\)）定义为边 \((u,\tau,v)\) 存在于图谱的可能性。
本节所有方法都是假定从低维向量中直接重构（多关系）邻居。
损失函数
负采样的交叉熵函数 \[ \mathcal{L} = \sum_{(u,\tau,v) \in \varepsilon} -log(\sigma(\mathrm{DEC}(z_u,\tau,z_v))) - \gamma\mathbb{E}_{v_n \sim P_{n,u}(\mathcal{V})}[log(\sigma(-\mathrm{DEC}(z_u,\tau,z_{v_n})))]) \] 其中，\(\sigma\) 为对数函数，\(P_{n,u}(\mathcal{V})\) 为节点集 \(\mathcal{V}\) 的负采样分布，且超参数 \(\gamma > 0\) 。
实际存在于图谱中的、预测为 true 的边的对数似然如下式： \[ log(\sigma(\mathrm{DEC}(z_u,\tau,z_v))) \] 图中不存在的、预测为 false 的边的期望对数似然如下式： \[ \mathbb{E}_{v_n \sim P_{n,u}(\mathcal{V})}[log(\sigma(-\mathrm{DEC}(z_u,\tau,z_{v_n})))] \] 使用蒙特卡洛近似法可以对期望值进行评估，常见损失函数如下式： \[ \mathcal{L} = \sum_{(u,\tau,v)\in \varepsilon} -log(\sigma(\mathrm{DEC}(z_u,\tau,z_v))) - \sum_{v_n \in \mathcal{P}_{n,u}} -[log(\sigma(-\mathrm{DEC}(z_u,\tau,z_{v_n})))] \] 其中，\(\mathcal{P}_{n,u}\) 为从 \(P_{n,u}(\mathcal{V})\) 采样得到的较小节点集。
最大间距损失 \[ \mathcal{L} = \sum_{(u,\tau,v)\in \varepsilon} \sum_{v_n \in \mathcal{P}_{n,u}} max(0, -\mathrm{DEC}(z_u,\tau,z_v) + \mathrm{DEC}(z_u,\tau,z_{v_n}) + \Delta) \] 该损失函数采用对比估计策略，将真实节点解码后的得分与负样本进行对比。其中，\(\Delta\) 项为间隔项，如果所有样本的得分差距都很大，那损失将为 0，该损失函数称为 hinge loss。
多关系解码器
RESCAL 方法
解码器定义为如下式： \[ \mathrm{DEC}(u,\tau,v) = z_u^TR_{\tau}z_v \] 其中，\(R_{\tau} \in \mathbb{E}^{d \times d}\) 是基于特定关系 \(\tau \in \mathcal{R}\) 的可学习矩阵。可借助基本的重构损失函数训练嵌入矩阵 \(Z\) 和关系矩阵 \(R_{\tau}, \forall \tau \in \mathcal{R}\)，如下式： \[ \begin{aligned} \mathcal{L} &= \sum_{u\in \mathcal{V}} \sum_{v\in \mathcal{V}} \sum_{\tau\in \mathcal{R}} || \mathrm{DEC}(u,\tau,v)-\mathcal{A}[u,\tau,v||^2 \\ &= \sum_{u\in \mathcal{V}} \sum_{v\in \mathcal{V}} \sum_{\tau\in \mathcal{R}} ||z_u^T\mathcal{R}_{\tau},z_v - \mathcal{A}[u,\tau,v]|| \end{aligned} \] 其中，\(\mathcal{A} \in \mathbb{R}^{|\mathcal{V}| \times |\mathcal{R}| \times |\mathcal{V}|}\) 为多关系图的邻接张量。
该方法进行关系表示时需要较高的计算量和统计成本，对于每种类型的关系，RESCAL 模型具有 \(O(d^2)\) 的参数量，与节点表示相比，关系表示要求具有更大数量级的参数。
平移解码模型（Translational Decoders）
TransE 模型将关系作为嵌入空间中的平移向量，定义的解码器如下图所示： \[ \mathrm{DEC}(z_u,\tau,z_v) = -|| z_u + r_{\tau} +z_v || \] 其中，使用 \(d\) 维嵌入向量来表示每种关系。在嵌入空间中，根据关系嵌入对头节点进行平移，边存在的可能性与头节点和尾节点嵌入间的距离成比例。
改进模型 1 \[ \mathrm{DEC}(z_u,\tau,z_v) = -|| g_{1,\tau}(z_u) + r_{\tau} - g_{2,\tau}(z_v)|| \] 其中，\(g_{i,\tau}\) 为一种基于关系 \(\tau\) 空间的可训练转换方式。
改进模型 2 TransH \[ \mathrm{DEC}(z_u,\tau,z_v) = -|| (z_u - w_r^Tz_uw_r) + r_{\tau} - (z_u - w_r^Tz_vw_r) || \] TransH 模型可将实体嵌入映射到一个可学习的特定关系超平面上（在执行转换之前，由法线向量 \(w_r\) 定义）。
多段点积（Multi-Linear Dot Products）
多段点积方法通过从简单图中扩展点积解码器来研究多关系解码模型，解码器如下式所示： \[ \mathrm{DEC}(z_u, \tau, z_v) = <z_u,r_{\tau},z_v> = \sum_{i=1}^d z_u[i] \times r_{\tau}[i] \times z_v[i] \] 该方法直接计算解码器中三个向量表示的点积。该解码器只能编码对称的关系，满足下式： \[ \begin{aligned} \mathrm{DEC}(z_u, \tau, z_v) &= <z_u,r_{\tau},z_v> \\ &= \sum_{i=1}^d z_u[i] \times r_{\tau}[i] \times z_v[i] \\ &= <z_v,r_{\tau},z_u> \\ &= DEC(z_v, \tau, z_u) \end{aligned} \] 复解码器
复解码器能够编码有向且不对称的关系。
ComplEx 通过引入复值嵌入表示来扩展 DistMult 解码器，定义为下式： \[ \begin{aligned} \mathrm{DEC}(z_u,\tau,z_v) &= Re<z_u,r_{\tau},\bar{z}_v> \\ &= Re(\sum_{i=1}^d z_u[i] \times r_{\tau}[i] \times z_v[i]) \end{aligned} \] 其中，\(z_u,z_v,r_{\tau} \in \mathbb{C}^d\) 为复值嵌入，Re 表示复值向量的实部。由于采用了尾部嵌入表示的复共轭 \(\bar{z}_v\)，因此这种解码方法适用于非对称关系。
RotateE 方法主要将解码过程定义为嵌入表示在复平面上的旋转，如下式： \[ \mathrm{DEC}(z_u,\tau,z_v) = || Z_u \circ r_{\tau} - z_v || \] 其中，\(\circ\) 为哈达玛乘积。假设上式中所有嵌入表示都是复值，且使 \(|r_{\tau}[i]|=1,\forall i \in {1,\cdots,d}\)，则关系嵌入的每一维向量能表示成 \(r_{\tau}[i]=e^{i\theta_{r,i}}\)，其对应关系向量在复平面内的旋转。
解码器的性能表征
对称性与非对称性
满足下式的关系具有对称性： \[ (u,\tau,v) \in \varepsilon \leftrightarrow (v,\tau,u) \in \varepsilon \] 满足下式的关系具有非对称性： \[ (u,\tau,v) \in \varepsilon \leftrightarrow (v,\tau,u) \notin \varepsilon \] DistMult 仅能建模对称关系。
TransE 解码器仅能建模非对称关系，如下式所示： \[ \begin{aligned} \mathrm{DEC}(Z_u, \tau, z_v) &= \mathrm{DEC}(z_v,\tau,z_u) \\ -|| z_u + r_{\tau} -z_v || &= -|| z_v + r_{\tau} -z_u || \\ \Longrightarrow -r_{\tau} &= r_{\tau} \\ \Longrightarrow r_{\tau} &= 0 \end{aligned} \] 互逆性
互逆性是指一种关系的存在暗含这另一种相反方向关系的存在，如下式： \[ (u,\tau_1,v) \leftrightarrow (v,\tau_2,u) \in \varepsilon \] DisMult 解码器无法对这种关心模式建模，但大多数其它类型解码器都能够表示逆关系。
组合性
满足下式的关系具有组合性： \[ (u,\tau_1,v) \in \varepsilon \wedge (v,\tau_2,u) \in \varepsilon \rightarrow (u,\tau_3,v) \in \varepsilon \] 在 TransE 模型中，当 \(r_{\tau_3} = r_{\tau_1} + r_{\tau_2}\)，满足上述组合性。在 RESCAL 中可以通过定义 \(R_{\tau_3} = R_{\tau_1}R_{\tau_2}\) 满足上述组合性。