深蓝学院-GNN课程笔记03-图嵌入
这个系列是深蓝学院图深度学习理论与实践的同步课程笔记。课程内容涉及图深度学习的基础理论与应用，本节主要介绍图嵌入的相关内容。
图嵌入的通用框架
图嵌入(graph embedding)的目的是将图上的每个节点映射为一个向量，这个向量也称为节点嵌入(node embedding)。最简单的嵌入方法是使用邻接矩阵的对应列作为嵌入，但由于邻接矩阵往往是非常稀疏的这样的嵌入方式在计算和存储上效率都很低。因此我们希望能够在图上找到一个低维的节点嵌入，使得嵌入后的节点向量能够保留原始图上的一些信息。
第一代图嵌入方法是基于图拉普拉斯矩阵的谱分解来实现嵌入。它的核心思想是对拉普拉斯矩阵进行矩阵分解，从而实现对数据进行降维。这种嵌入方法的主要缺陷在于它具有非常高的计算复杂度，因此难以应用到大规模的图上。
第二代图嵌入方法则是来源于自然语言处理中的词向量(word2vec)技术。词向量是利用语料中词的共现信息来对词进行嵌入，它的基本思想是同时出现的词会具有相似的语义。把词向量的思想应用到节点嵌入中就得到了第二代图嵌入技术，和第一代嵌入技术相比第二代图嵌入技术通常比较高效而且具有更好的拓展性。
从宏观上来看，图嵌入需要解决两个基本问题：需要保留图上的哪些信息以及如何取保留这些信息。常用的信息包括共现信息、结构角色、社区信息以及节点状态等，而在对信息进行重构时则需要保证嵌入后的结果与嵌入前尽可能一致。因此图嵌入的通用框架需要4个关键组件：
- 映射函数\(f\)将图域节点映射到嵌入域\(\mathbb{R}^d\)；
- 提取图上关键信息\(I\)的信息提取器；
- 利用嵌入域\(\mathbb{R}^d\)重新构造所提取到的信息，构造的信息记为\(I'\)；
- 对提取到的信息\(I\)和重构信息\(I'\)进行优化，学习映射函数\(f\)的参数。
简单图嵌入
保留邻域信息
DeepWalk是基于节点共现信息来实现图嵌入的方法。对于没有方向且只包含节点连接信息的简单图，我们可以利用图上的随机游走(random walk)来模拟共现语料的效果。定义当前节点\(v^{(t)}\)转移到与它相邻的其它节点的概率为：
\[P(v^{(t+1)} \vert v^{(t)}) = \left\{ \begin{aligned} & \frac{1}{d(v^{(t)})} & & v^{(t+1)} \in N(v^{(t)}) \\ & 0 & & \text{otherwise} \end{aligned} \right.\]也就是说在\(v^{(t)}\)处会以均匀概率转移到和它相邻的其它节点上。以这样的方式在图上进行采样就得到了一系列节点构成的序列作为训练数据。对于训练数据中的中心节点和与它相邻的上下文节点，我们构造2个映射函数：
\[f_{cen} (v_i) = W_{cen} e_i\] \[f_{con} (v_i) = W_{con} e_i\]其中\(W_{cen}\)和\(W_{con}\)为中心节点和上下文节点的嵌入矩阵，每一列表示一个节点嵌入向量；\(e_i\)为仅在\(v_i\)处取1的one-hot向量。对于共现信息\(I_W = \{ (v_{cen}, v_{con}) \}\)，中心节点和上下文节点的共现概率可以利用softmax函数进行计算：
\[P(v_{con} \vert v_{cen}) = \frac{\exp \{ f_{con} (v_{con})^T f_{cen} (v_{cen}) \}}{\sum_v \exp \{ f_{con} (v)^T f_{cen} (v_{cen}) \}}\]将序列中的共现概率累乘起来可以得到似然函数：
\[L(W_{cen}, W_{con}) = \prod_{I_W} \frac{\exp \{ f_{con} (v_{con})^T f_{cen} (v_{cen}) \}}{\sum_v \exp \{ f_{con} (v)^T f_{cen} (v_{cen}) \}}\]我们可以通过最大化似然函数来重构嵌入后的共现信息。在实际应用中更常见的形式是最小化对数损失来实现训练过程：
\[l = -\sum_{I_W} \log \frac{\exp \{ f_{con} (v_{con})^T f_{cen} (v_{cen}) \}}{\sum_v \exp \{ f_{con} (v)^T f_{cen} (v_{cen}) \}}\]DeepWalk训练时的主要难点在于分母项\(\sum_v \exp \{ f_{con} (v)^T f_{cen} (v_{cen}) \}\)，当图上的节点很多时分母项需要计算中心节点和每个节点嵌入向量的内积并求和。为了解决这个问题实践中往往通过分层softmax或者负样本采样的方式来对计算过程进行加速。
分层softmax的思想是将图上的每个顶点表示为一颗二叉树的叶节点，这样顶点的转移概率可以转换为二叉树上一系列路径的乘积：
\[P(v_{con} \vert v_{cen}) = \prod p_{\text{path}}(p^{(h)} \vert v_{cen})\]当路径选择向左前进时，对应的概率为：
\[p_{\text{path}}(p^{(h)} \vert v_{cen}) = p(\text{left} \vert b_i, v_{cen}) = \sigma(f_b(b_i)^T f(v_{cen}))\]类似地，选择向右的概率为：
\[p_{\text{path}}(p^{(h)} \vert v_{cen}) = p(\text{right} \vert b_i, v_{cen}) = 1- \sigma(f_b(b_i)^T f(v_{cen})) = \sigma(-f_b(b_i)^T f(v_{cen}))\]此时我们不再学习顶点的两个映射函数\(f_{cen}\)和\(f_{con}\)，但是学习叶节点和中间节点的映射函数\(f\)和\(f_{b}\)。
另一种加速方法是负样本采样，它的核心思想是将多分类转换为二分类问题来求解。随机游走的目的是提高共现顶点出现的概率，因此我们可以把共现的顶点视为正样本并且把没有直接相连的样本视为负样本，这样得到二分问题的目标函数：
\[\log \sigma \big( f_{con} (v_{con})^T f_{cen} (v_{cen}) \big) + \sum_{i=1}^k E_{v_n \sim P_n(v)} [\log \sigma \big( -f_{con} (v_{n})^T f_{cen} (v_{cen}) \big)]\]其中\(P_n(v)\)表示负样本的分布，对于每个正样本我们会抽样出\(k\)个负样本来进行训练。
除了DeepWalk算法之外还有一些其它的基于顶点共现信息的图嵌入方法。如LINE算法使用边的集合来提取共现信息，而node2vec算法则采用二阶随机游走来提取共现信息，在进行游走时允许回溯到之前的顶点：
\[\alpha(v^{(t+1)} \vert v^{(t)}, v^{(t-1)}) = \left\{ \begin{aligned} & \frac{1}{p} & & \text{dist}(v^{(t-1)}, v^{(t+1)}) = 0 \\ & 1 & & \text{dist}(v^{(t-1)}, v^{(t+1)}) = 1 \\ & \frac{1}{q} & & \text{dist}(v^{(t-1)}, v^{(t+1)}) = 2 \end{aligned} \right.\]上式意为从当前顶点回溯到之前顶点的倾向性为\(\frac{1}{p}\)，探索\(v^{(t-1)}\)附近顶点的倾向为\(1\)，而向外探索的倾向性为\(\frac{1}{q}\)。LINE算法和node2vec算法对随机游走的方式进行了改进，除此之外算法的其它步骤则与DeepWalk一致。
保留结构角色
在很多应用中我们希望具有相似结构特征的顶点在嵌入后仍然是相似的，而struc2vec就是这样的一种基于结构特征的图嵌入算法。首先我们需要去衡量不同顶点在图上的结构相似度，直观上看相似的顶点需要具有相近的度，而且它们邻居的度也应该相似。
在这种观察的基础上，struc2vec提出了一种层次化的结构相似度度量方法：
\[g_k(u, v) = g_{k-1}(u, v) + \text{dist} (S_u^k, S_v^k)\]上式中\(g_k(u, v)\)为\(u\)和\(v\)两个顶点的第\(k\)阶结构相似度，我们定义\(k=-1\)时\(g_{-1}(u, v) = 0\)；\(S_u^k\)和\(S_v^k\)分别表示\(u\)和\(v\)两个顶点\(k\)阶邻居的度排序后的序列；\(\text{dist}\)为度量两个序列距离的函数。\(g_k(u, v)\)越大说明\(u\)和\(v\)两个顶点的结构差异越大。
在此基础上我们可以定义一个包含\(k\)层的全连接图，其中第\(i\)层任意两个顶点之间边的权重为：
\[w_i(u, v) = \exp \{ -g_i(u, v) \}\]同时每个顶点还与它上下两层的同一顶点相连，对应边的权重为：
\[w(u^{(i)}, u^{(i-1)}) = 1\] \[w(u^{(i)}, u^{(i+1)}) = \log (\Gamma_i (u) + e)\] \[\Gamma_i (u) = \sum_{v_j \in V} \mathbf{1}\{ w_i(v, v_j) \gt \bar{w}_i \}\]其中\(\bar{w}_i = \frac{\sum_{(u, v) \in E_i} w_i(u, v)}{\frac{1}{2} \vert V \vert (\vert V \vert-1)}\)表示第\(i\)层全连接图边的平均权重。
构造出新的图后我们就可以在新图上进行随机游走，然后类似于DeepWalk的步骤提取共现信息并进行训练即可获得保留图结构信息的嵌入。
保留节点状态
在很多应用中我们希望能够在嵌入后保留节点的全局状态，比如说中心性等。此时我们可以按照顶点状态进行排序，得到顶点序列：
\[v_{(1)}, v_{(2)}, ..., v_{(N)}\]此时顶点\(v_{(i)}\)排在\(v_{(j)}\)前面的概率可以建模为：
\[p(v_{(i)}, v_{(j)}) = \sigma \big(w^T (u_{(i)} - u_{(j)}) \big)\] \[u_{(i)} = f(v_{(i)})\]为了保留顶点的排序信息，我们需要最大化全局排名概率：
\[p_{\text{global}} = \prod_{1 \leq i \lt j \leq N} p(v_{(i)}, v_{(j)})\]当然实际中更常见的形式是将\(p_{\text{global}}\)的负对数作为损失函数并进行最小化：
\[L_{\text{global}} = - \log p_{\text{global}}\]保留社区结构
社区结构是图最重要的特征之一，它的特点是同一个社区内的顶点联系紧密但社区之间只有稀疏的连接。
显然我们希望能够将顶点的社区信息保留到嵌入中。对于拥有两个社区的图，假设我们知道它的社区分配则可以定义模块度如下：
\[Q = \frac{1}{2 \text{vol}(G)} h^T B h\] \[B_{ij} = A_{ij} - \frac{d(v_i) d(v_j)}{\text{vol}(G)}\]式中，\(\text{vol}(G) = \sum_{v_i \in V} d(v_i)\)为图上所有节点的度的和；\(h\)为顶点社区的指示向量；\(A\)为图的邻接矩阵；\(d(v_i)\)为顶点的度。当图上有不止2个社区时，我们可以将模块度进行推广：
\[Q = \text{tr} (H^T B H)\]其中\(H\)为社区成员的分配矩阵，它的每一列表示一个社区，每一行为一个one-hot向量表示当前顶点对应的社区。显然分配矩阵\(H\)满足约束条件：
\[\text{tr} (H^T H) = N\]我们可以通过最大化模块度来进行进行社区发现，此时相当于求解约束优化问题：
\[\begin{aligned} \max_H \ \ & Q = \text{tr} (H^T B H) \\ \text{s.t.} \ \ & \text{tr} (H^T H) = N \end{aligned}\]除了社区结构之外我们还希望保持顶点度的连接信息。对于任意两个顶点\(v_i\)和\(v_j\)，它们的邻域相似度可以定义为：
\[s_{ij} = \frac{A_i A_j^T}{\Vert A_i \Vert \Vert A_j \Vert}\]其中\(A_i\)为邻接矩阵的第\(i\)行。当\(v_i\)和\(v_j\)共享的邻居越多时，它们的邻域相似度相似度越大；当\(v_i\)和\(v_j\)不共享任何邻居时，邻域相似度为0。然后我们将邻接矩阵和邻域相似度矩阵组合到一起，得到优化目标矩阵：
\[P = A + \eta \cdot S\]式中，\(\eta \lt 0\)控制邻域相似度的重要程度。接着假设\(P\)在嵌入域的重构为\(W_{con} W_{cen}^T\)，从而得到顶点相关信息重构的误差函数：
\[\Vert P - W_{con} W_{cen}^T \Vert_F^2\]最后把顶点相关信息和社区结构信息组合到一起，得到最终的优化目标函数：
\[\min_{W_{con}, W_{cen}, H, C} \Vert P - W_{con} W_{cen}^T \Vert_F^2 + \alpha \Vert H - W_{cen} C^T \Vert_F^2 - \beta \cdot \text{tr} (H^T B H)\]其中矩阵\(C\)是额外的参数矩阵，用来重建指示矩阵\(H\)；超参数\(\alpha\)和\(\beta\)用来控制三个优化项之间的平衡。
复杂图嵌入
前面我们介绍了不类型的简单图嵌入方法，在简单图的基础上我们可以结合不同复杂图自身的特点将图嵌入推广到复杂图上。
异质图嵌入
对于包含不同边信息的异质图，我们需要结合专业知识来定义meta-path并按照meta-path定义的模式来进行随机游走。
二分图嵌入
对于二分图，我们可以把它划分为两个子图；同时两个子图内部的顶点没有直接连接，只能通过另一个子图上的顶点相连。在这种情况下我们可以在两个子图上分别进行随机游走来实现图嵌入，对于同一个子图上的两个顶点，如果它们具有共享的邻居则认为它们在新的子图上存在共现关系。
同时我们还希望原始二分图上相连的顶点在分别嵌入后具有相似性，因此额外引入边的优化函数：
\[L_e = - \sum_{(v_1, v_2) \in E} \log \sigma(v_1^T v_2)\]最后将二分图边的优化函数与两个子图上的随机游走结合起来，得到最终的目标函数：
\[L = L_e + \eta_1 L_{V_1} + \eta_2 L_{V_2}\]其中超参数\(\eta_1\)和\(\eta_2\)用来平衡不同类型信息的重要性。
多维图嵌入
对于多维度，我们则需要在每个维度上独立进行随机游走。同时每个顶点的嵌入包含通用信息和维度特有信息两部分：
\[u_{d, i} = u_i + r_{d, i}\]其中\(u_i\)为顶点的通用表示，仅与顶点相关；\(r_{d, i}\)为顶点\(v_i\)在\(d\)维中的信息，与其它维度无关。
符号图嵌入
对于包含同时正负信息的符号图，在随机游走时需要对顶点\(v_i\)同时采样它的正负邻居形成三元组\((v_i, v_j, v_k)\)。同时在进行优化时要保证正向邻居\((v_i, v_j)\)的距离大于负向邻居\((v_i, v_k)\)的距离，对应的优化函数为：
\[s(f(v_i), f(v_j)) - \big( s(f(v_i), f(v_k)) + \delta \big)\]其中参数\(\delta\)控制正负向邻居相似度的阈值。
超图嵌入
对于包含超边的超图需要考虑超边所描述的顶点相似性以及超边内部顶点之间的相似性。对于超边所定义的相似性，假设超边都包含\(k\)个顶点，顶点集合\(V^i = \{ v_{(1)}^i, v_{(2)}^i, ... , v_{(k)}^i \}\) 存在超边连接的概率可通过一个前馈神经网络描述：
\[p(1 \vert V^i) = \sigma(g(v_{(1)}^i, v_{(2)}^i, ... , v_{(k)}^i))\]因此，我们可以在顶点集合上进行采样得到超边集合\(\mathcal{E}\)对应的目标函数：
\[L_1 = - \bigg( \sum_{V^i \in \mathcal{E}} \log p (1 \vert V^i) + \sum_{V^i \in \mathcal{E'}} \log (1 - p (1 \vert V^i)) \bigg)\]而对于每个超边内部的相似性，我们首先定义超图内的共现信息矩阵为：
\[A = H H^T - D\]其中\(H^{\vert V \vert \times \vert E \vert}\)为超图的关联矩阵，它的每一列对应一条超边，\(H_{i,j}=1\)表示顶点\(v_i\)位于超边\(e_j\)内；\(D\)则是顶点的度矩阵。\(A\)矩阵的第\(i\)行描述了顶点\(v_i\)与图上其它顶点的共现信息，我们可以利用一个前馈神经网络来近似它：
\[\tilde{A}_i = f(u_i)\]然后利用最小二乘法来定义重构共现信息的目标函数：
\[L_2 = \sum_{V^i \in \mathcal{E}} \Vert A_i - \tilde{A}_i \Vert^2\]最后将两部分目标函数相加就得到了超图上进行图嵌入的目标函数：
\[L = L_1 + \eta L_2\]动态图嵌入
对于包含时间信息的动态图在随机游走时必须按照边的时间顺序进行采样，同时下一条边的发生时间要在上一条边的发生时间之后。