Graph Embedding & GNN 综述和其它

一、A Comprehensive Survey of Graph Embedding

1. Graph 存在于各种各样的现实场景中，如社交网络social network，引文网络 citation network，知识图谱 knowledge graph 等。大多数现有的图分析方法都遭受很高的计算代价和空间成本，而 graph embedding 提供了一种有效的方法来解决图分析问题。具体而言 graph embedding 将图映射到保留了图信息的低维空间。

   论文 《A Comprehensive Survey of Graph Embedding:Problems, Techniques and Applications》 研究了现有的 graph embedding 方法，对这些 graph embedding 方法技术做了全面的综述。

2. 论文将输入的图分为四类：同质图homogeneous graph、异质图 heterogeneous graph、带辅助信息的图、从非关系数据人工构造的图。

3. 论文将 graph embedding 输出分为四类，包括 node embedding、edge embedding、hybrid embedding、whole-graph embedding。

1.1 定义

1. 给定图 $\mathcal G = (V,E)$ ，其中 $V$ 为顶点集合， $E$ 为边集合， $\mathbf A$ 为图的邻接矩阵。

   • 每个顶点 $v_i$ 关联一个顶点类型$f_v(v_i)$ ，它是一个映射 $f_v:V\rightarrow \mathcal T^v$ ，其中 $\mathcal T^v$ 表示顶点类型集合。
   • 每条边 $e_{i,j}$ 关联一个边类型 $f_e(e_{i,j})$ ，它也是一个映射 $f_e:E\rightarrow \mathcal T^e$ ，其中 $\mathcal T^e$ 表示边类型集合。

   定义同质图 $\mathcal G_{\text{homo}} = (V,E)$ ，其中 $|\mathcal T^v| = |\mathcal T^e| = 1$ 。 $\mathcal G_{\text{homo}}$ 的所有顶点只有一个类型，所有边也只有一个类型。

   定义异质图 $\mathcal G_{\text{hete}} = (V,E)$ ，其中 $| \mathcal T^v| + |\mathcal T^e| \gt 1$ ，即 $\mathcal G_{\text{hete}}$ 的顶点和/或边有多个类型。

   定义知识图谱 knowledge grap $\mathcal G_{\text{know}} = (V,E)$ 为一个有向图，顶点为实体 entity，边为subject-property-object 三元组。每条边由 (head entity, relation, tail entity) 的形式组成，记作 $<h,r,t>$ ，它表示从实体 $h$ 到实体 $h$ 的关系 $r$ ，其中 $h,t\in V$ 为实体， $r\in E$ 为边。我们称 $<h,r,t>$ 为知识图谱三元组。注意，知识图谱中顶点通常具有不同类型，边通常也具有不同类型，因此知识图谱也可以视为一个异质图。

2. 定义顶点 $v_i, v_j$ 之间的一阶邻近度 first-order proximity 为顶点 $v_i$ 和 $v_j$ 的相似性。我们认为：如果两个顶点之间具有较大权重的连接，则它们更为相似。由于边 $e_{i,j}$ 的权重为 $A_{i,j}$ （邻接矩阵的第 $i$ 行第 $j$ 列） ，因此我们将顶点 $v_i$ 和 $v_j$ 之间的一阶邻近度表示为 $s_{i,j}^{(1)} = A_{i,j}$ 。

   定义 $\mathbf{\vec s}_i^{(1)} = \left[s_{i,1}^{(1)},s_{i,2}^{(1)},\cdots, s_{i,|V|}^{(1)} \right]$ 为顶点 $v_i$ 和所有其它顶点的一阶邻近度向量。

3. 定义顶点 $v_i, v_j$ 之间的二阶邻近度 second-order proximity 为顶点 $v_i$ 的邻域和 $v_j$ 的邻域之间的相似性，记作 $s_{i,j}^{(2)}$。二阶邻近度表示顶点邻域结构的相似性，如果两个顶点的邻域越相似，则它们之间的二阶邻近度越大。

   如果我们用 cos 函数作为邻域相似性的度量，则二阶邻近性为：

   $$s_{i,j}^{(2)} = \cos\left(\mathbf{\vec s}_i^{(1)},\mathbf{\vec s}_j^{(1)}\right)$$

   顶点 $v_i,v_j$ 之间的高阶邻近度 higher-order proximity 也可以类似地定义。例如，顶点 $v_i,v_j$ 之间的 $k$ 阶邻近度定义为顶点 $v_i$ 的 $k-1$ 阶邻域和 $v_j$ 的 $k-1$ 阶邻域之间的相似性，即 $\mathbf{\vec s}_i^{(k-1)}$ 和 $\mathbf{\vec s}_j^{(k-1)}$ 之间的相似性。

   注意：也可以使用其它的一些指标来定义高阶邻近度，如 Katz Index, Rooted PageRank, Adamic Adar 等等。

4. 定义 grap embedding 为：给定一个图 $\mathcal G=(V,E)$ ，以及一个预先指定的embedding 维度 $d$ ， graph embedding 需要将图 $\mathcal G$ 映射到 $d$ 维空间，在映射过程中尽可能保留图的属性。

   图的属性可以通过一阶邻近度和高阶邻近度等指标来衡量。可以将整张图表示为一个 $d$ 维向量；也可以将单张图表示为一组 $d$ 维向量，其中每个向量表示图中部分组件的 embedding （如顶点、边、子结构）。

   如下图所示，单张图以不同粒度嵌入到一个二维空间，其中 $G_{1,2,3}$ 表示包含顶点 $v_1,v_2,v_3$ 的子结构。

   

1.2 问题

1. graph embedding 的输入是图，这里我们将输入图划分为四类：同质图homogeneous graph、异质图 heterogeneous graph、带辅助信息的图、从非关系数据人工构造的图。每种类型的图都会给graph emebdding 带来不同的挑战。

   • 同质图：图的顶点和边分别只有一种类型。同质图可以进一步划分为加权图、无权图，以及有向图，无向图。

     挑战：如何捕获图中观察到的各种各样的连接模式？由于同质图中仅有结构信息可用，因此同质图 graph embedding 的挑战在于如何在 embedding 中保持输入图中观察到的这些连接模式。

   • 异质图：异质图包含三种场景：

     • 基于社区的问答网站 Community-based Question Answering:cQA：cQA 是基于互联网的众包服务，用户可以在网站上发布问题，然后由其它用户回答。直观来看，cQA 图中有不同类型的顶点，如问题 question、答案 answer、用户 user 。
     • 多媒体网络：包含多种类型媒体数据（如图像、文本）的网络。
     • 知识图谱：在知识图谱中，实体（顶点）和关系（边）通常都具有不同的类型。

     除了以上三种类型的异质图之外，还有其它类型的异质图。

     挑战：

     • 如何探索不同类型对象之间的全局一致性？在异质图 embedding 中，不同类型的顶点（或者不同类型的边）被 embedding 到同一个公共空间中。如何确保 embedding 的全局一致性是一个问题。
     • 如何处理不同类型对象之间的不平衡？在异质图中，不同类型的对象数量差异很大，因此学习嵌入时需要考虑数据倾斜问题。

   • 带辅助信息的图：除了包含顶点结构之外，带辅助信息的图还包含顶点/边/全图的辅助信息。有五种类型的辅助信息：

     • label：顶点带标签信息（离散值）。带相同标签的顶点的 embedding 应该彼此靠近、不同标签的顶点的 embedding 应该彼此远离。
     • attribute：顶点带属性信息。和标签不同，属性值可以是连续的也可以是离散的。属性值差异较小的顶点的 embedding 应该彼此靠近、属性值差异较大的顶点的 embedding 应该彼此远离。
     • node feature：顶点带特征信息。和属性值不同，特征可能包含文本、向量、图像等多种类型的内容。顶点特征通过提供丰富的结构化信息来提升 graph emebdding 性能。另外，这也使得 inductive graph embedding 成为可能。
     • information progapation：消息传播。一个典型例子是 Twitter 中的转发。
     • knowledge base：知识库。流行的知识库包括 Wikipedia, Freebase, YAGO, DBPedia 等。以 Wikipedia 为例，concept 是用户提出的实体 entity，文本是该实体相关的文章。

     其它类型的辅助信息包括用户 check-in 数据（用户位置信息）、用户 item 偏好排名信息等等。注意，辅助信息不仅局限于一种类型，也可以考虑多种类型如 label & node feature 。

     挑战：如何融合丰富的非结构化信息，使得学到的 embedding 同时编码了图的拓扑结构和辅助信息？除了图结构信息之外，辅助信息还有助于定义顶点相似性。因此如何融合这两个图拓扑结构和辅助信息这两个信息源，这是一个问题。

   • 人工构造图：此时没有图数据，需要通过不同的方法从非关系数据中人工构建图。大多数情况下，输入为特征矩阵 $\mathbf X\in \mathbb R^{|V|\times d}$ ，其中第 $i$ 行 $\mathbf{\vec x}_i\in \mathbb R^d$ 为第 $i$ 个样本的 $d$ 维特征向量。

     通常使用样本 $i,j$ 的特征向量 $(\mathbf{\vec x}_i, \mathbf{\vec x}_j)$ 来计算相似度 $s_{i,j}$ ，从而构造相似度矩阵 $\mathbf S$ 。然后基于 $\mathbf S$ 有两种人工构造图的方法：

     • 一种直接的计算方法是将 $\mathbf S$ 视为构造图的邻接矩阵。但是这种方法基于欧拉距离，如果 $\mathbf X$ 位于一个弯曲的流形上，那么在这个流形上 $\mathbf{\vec x}_i$ 和 $\mathbf{\vec x}_j$ 的流形距离要远大于它们的欧拉距离。

       为解决该问题，一个方法是从 $\mathbf S$ 构建一个 $k$近邻图 kNN graph，并基于 kNN 图估计一个邻接矩阵 $\mathbf A$ 。如 Isomap 将测地线距离融合到 $\mathbf A$ 中：它首先从 $\mathbf S$ 构造一个 kNN 图，然后找到两个顶点之间的最短距离作为它们的测地线距离。

     • 另一种构造图的方法是基于顶点的共现，从而在顶点之间建立边。如在图像领域，研究人员将像素视为顶点，像素之间的空间关系视为边。

     除了上述基于成对顶点相似性以及顶点共现的方法之外，还针对不同目的设计了其它的图构造方法。

     挑战：

     • 如何构造一个图从而对样本之间的成对关系进行编码？即如何计算非关系数据的样本之间的关系，并构造这样的图。
     • 如何将顶点邻近度矩阵保留在 embedding 空间中？即如何在 embedding 空间中保留构造图的顶点邻近性。

2. graph emebdding 的输出是图（或者图的一部分）的一个（或者一组）低维向量。根据输出粒度，可以将 graph embedding 输出分为 node embedding 顶点 embedding、edge embedding 边 embedding 、hybrid embedding 混合 embedding、whole-graph embedding 全图 embedding。

   与固定的且给定的输入不同，graph embedding 的输出是任务驱动的。例如，顶点 embedding 可用于各种与顶点相关的图分析任务，而某些任务（如化合物分类）可能需要全图 embedding 。因此，embedding 输出的第一个挑战是如何找到满足特定任务需求的、合适的 graph embedding 。

   • 顶点 embedding ：将每个顶点表示为低维空间中的向量，图中相近 close 的顶点在 embedding 空间中有相似的向量表示。

     各种 graph embedding 方法之间的差异在于如何定义两个顶点之间的相近程度 closeness，其中一阶邻近度和二阶邻近度是计算两个顶点相近程度的常用度量，某些工作中也使用高阶邻近度。

     挑战：如何在各种类型的输入图中定义成对顶点的相近成对，以及如何在 embedding 中对这种相近程度进行编码？

   • 边 embedding ：将每条边表示为低维空间中的向量。边 embedding 在以下两种情况下很有用：

     • 知识图谱 embedding 需要学习顶点 embedding 和边 embedding。每条边都是三元组 $<h,r,t>$ ，边 embedding 需要在embedding 空间中保留 $h$ 和 $t$ 之间的关系 $r$ ，这样可以在给定三元中的两个元素时正确地预测缺失的实体或者关系。
     • 一些工作将顶点 pair 对嵌入为一个向量，从而预测这对顶点之间是否存在链接。

     总之，边 embedding 有利于与边相关的图分析，如链接预测、知识图谱的实体/关系预测。

     挑战：

     • 如何定义 edge-level 相似度？边的相似度不同于顶点相似度，因为边通常包含一对顶点。
     • 对于有向边，如何建模边的非对称属性？和顶点不同，边可以是有向的。因此边 embedding 需要编码这种不对称属性。

   • 混合 embedding：嵌入图的不同类型的组件，如 顶点 + 边 （子结构 substructure ）、顶点 + 社区 community。

     已有大量工作研究了子结构嵌入substructure embedding，而社区嵌入 community embedding 目前关注较少。

     子结构embedding 或者社区embedding 也可以通过聚合结构中的顶点embedding 和边 embedding 来得到，但是这种间接的方式并未针对结构的表示进行优化。而且，顶点 embedding 和社区 embedding 可以彼此强化：通过融合社区感知 community-aware 的高阶邻近度，可以学到更好的顶点 embedding；而当学到更高的顶点 embedding 时，就可以检测到更好的社区。

     挑战：

     • 如何生成目标子结构？和其它类型的 embedding 输出相反，混合 embedding 并未提供需要嵌入的目标（如子图，社区）。因此第一个挑战是如何生成这种目标结构。
     • 如何在一个公共空间中嵌入不同类型的图组件？不同类型的目标（如社区、顶点）可以同时嵌入到一个公共空间中。如何解决 embedding 目标类型的异质性是一个问题。

   • 全图 embedding ：将整个图输出为一个 embedding 向量，这通常用于蛋白质、分子等较小的图。这种情况下，一个图表示为一个向量，相似的图被嵌入到相近的 embedding 空间。

     全图 embedding 提供了图的相似度计算的一种简单有效解决方案，使得图分类任务受益。

     挑战：

     • 如何捕获整个图的属性？全图 embedding 需要捕获真个图的属性，而不是单个顶点或者边的属性。
     • 如何在表达性 expressiveness 和效率 efficiency 之间平衡？ 由于需要捕获全图属性，因此和其它类型的 embedding 相比，全图 embedding 耗时更多。全图 embedding 的关键挑战是如何在学到的 embedding 的表达能力和 embedding 算法的效率之间平衡。

1.3 技术

1. 通常graph embedding 目标是在低维 embedding 空间中表达一个图，其中该 embedding 空间保留尽可能多的图属性信息。不同 graph embedding 算法之间的差异主要在于如何定义需要保留的图属性。不同的算法对于顶点相似性、边相似性、子结构相似性、全图相似性有不同的定义，以及对于如何将这种相似性保留在 embedding 空间有各自不同的见解 insight。

a. 矩阵分解

1. 基于矩阵分解 Matrix Factorization 的graph emebdding 方法以矩阵形式表示图属性，如顶点成对相似性 node pairwise similarity，然后分解该矩阵从而得到顶点 embedding。

   基于矩阵分解的 graph embedding 方法也是 graph embedding 的早期研究方式。大多数情况下，输入是非关系型的 non-relational、高维的数据通过人工构造而来的图，输出是一组顶点 embedding 。因此可以将 graph embedding 视为保留结构信息的降维问题，该问题假设输入数据位于低维流形中。

   有两种类型的基于矩阵分解的 graph embedding 方法：分解图拉普拉斯特征图 Laplacian Eigenmaps 、分解顶点邻近度矩阵proximity matrix。

2. 总结：矩阵分解主要用于两种场景：嵌入由非关系数据构成的图的顶点 embedding（这是拉普拉斯特征图的典型应用场景）；嵌入同质图。

1> Graph Laplacian Eigenmaps

1. 图拉普拉斯特征图分解的思想是：图拉普拉斯特征图分解保留的图属性为成对顶点相似性，因此如果两个相距较远的顶点（通过 embedding 距离衡量）的相似度较大，则给予较大的惩罚。

   为方便讨论，假设 embedding 的维度为一维，即将每个顶点 $v_i$ 映射为一个整数 $y_i$ 。基于上述洞察 insight，则最优化 embedding 为：

   $$\mathbf {\vec y}^* = \arg\min\sum_{i\ne j} (y_i - y_j)^2 W_{i,j} = \arg\min \mathbf{\vec y}^T\mathbf L \mathbf{\vec y}$$

   其中：

   • $y_i$ 为顶点 $v_i$ 的一维 embedding ，$\mathbf{\vec y}$ 为所有顶点一维embedding 组成的 embedding 向量。
   • $W_{i,j}$ 为顶点 $v_i,v_j$ 之间的成对相似性， $\mathbf W$ 为图中顶点之间的相似度矩阵。通常选择 $\mathbf W$ 为图的邻接矩阵（无权图）或者带权重的邻接矩阵（带权图）。
   • $\mathbf L = \mathbf D- \mathbf W$ 为图拉普拉斯矩阵，其中 $\mathbf D=\text{diag}(D_i)$ 为对角矩阵， $D_i = \sum_{j\ne i}W_{i,j}$ 为其对角线元素。

   但是，上述最优化方程没有唯一解。假设 $\mathbf {\vec y}^*$ 为最终解，则 $\frac{\mathbf {\vec y}^*}{2}$ 使得目标函数更小，矛盾。因此为了移除缩放因子的影响，我们通常增加约束条件 $\mathbf{\vec y}^T \mathbf D \mathbf {\vec y} = 1$ 。因此问题变为：

   $$\mathbf {\vec y}^* = \arg\min_{\mathbf{\vec y}^T \mathbf D \mathbf {\vec y} = 1} \mathbf{\vec y}^T\mathbf L \mathbf{\vec y} = \arg\min \frac{\mathbf{\vec y}^T\mathbf L \mathbf{\vec y} }{\mathbf{\vec y}^T\mathbf D \mathbf{\vec y} } = \arg\max \frac{\mathbf{\vec y}^T\mathbf W \mathbf{\vec y} }{\mathbf{\vec y}^T\mathbf D \mathbf{\vec y} }$$

   则最优解 $\mathbf {\vec y}^*$ 为特征值分解问题eigenproblem $\mathbf W{\mathbf {\vec y}} = \lambda \mathbf D \mathbf{\vec y}$ 的最大特征值eigenvalue 对应的特征向量 eigenvector 。

2. 上述 graph embedding 的问题是该方法是 transductive 的，它仅能嵌入已有的顶点。实际应用中还需要嵌入未见过的、新的顶点。

   一种解决方案是设计线性函数 $y_i = \mathbf{\vec x}_i^T \mathbf{\vec a}$ ，其中 $\mathbf{\vec x}_i\in \mathbb R^{d_f}$ 为顶点 $v_i$ 的特征向量 feature vector 。这样只要提供顶点的特征向量，我们就可以求得其 embedding 。因此 inductive graph embedding 问题的核心在于求解合适的 $\mathbf{\vec a}$ 。

   同样地我们认为如果相距较远的两个顶点（通过 embedding 距离衡量）的相似度较大，则给与较大的惩罚。则最优化 embedding 为：

   $$\mathbf{\vec a}^* = \arg\min \sum_{i\ne j}(\mathbf{\vec a}^T\mathbf{\vec x}_i - \mathbf{\vec a}^T \mathbf{\vec x}_j)^2 W_{i,j} = \arg\min \mathbf a^T \mathbf X \mathbf L \mathbf X^T\mathbf{\vec a}$$

   其中 $\mathbf X\in \mathbb R^{d_f\times |V|}$ 为顶点特征向量组成的特征矩阵。

   类似地，为了移除缩放因子的效果，我们通常增加约束条件 $\mathbf{\vec a}^T\mathbf X \mathbf D \mathbf X^T\mathbf {\vec a} = 1$ 。因此问题变为：

   $$\mathbf{\vec a}^* = \arg\min \frac{\mathbf{\vec a}^T\mathbf X \mathbf L \mathbf X^T\mathbf {\vec a}}{\mathbf{\vec a}^T\mathbf X \mathbf D \mathbf X^T\mathbf {\vec a} }= \arg\max \frac{\mathbf{\vec a}^T\mathbf X \mathbf W \mathbf X^T\mathbf {\vec a}}{\mathbf{\vec a}^T\mathbf X \mathbf D \mathbf X^T\mathbf {\vec a} }$$

   则最优解 $\mathbf {\vec a}^*$ 为特征值分解问题eigenproblem $\mathbf X\mathbf W\mathbf X^T{\mathbf {\vec a}} = \lambda \mathbf X\mathbf D \mathbf X^T\mathbf{\vec a}$ 的最大特征值 eigenvalue 对应的特征向量 eigenvector 。

3. 现有方法的差异主要在于如何计算顶点 $v_i, v_j$ 之间的成对相似度 $W_{i,j}$ ，以及是否使用线性函数 $y_i = \mathbf{\vec x}_i^T\mathbf{\vec a}$ 。在下表中我们总结了现有的 eigenmaps-based graph embedding 方法，并给出了它们如何计算顶点相似度矩阵 $\mathbf W$ 以及采用什么目标函数。

   其中：

   • Eq.2 表示目标函数 $\mathbf {\vec y}^* = \arg\max \frac{\mathbf{\vec y}^T\mathbf W \mathbf{\vec y} }{\mathbf{\vec y}^T\mathbf D \mathbf{\vec y} }$ ； Eq.4 表示目标函数 $\mathbf{\vec a}^* = \arg\max \frac{\mathbf{\vec a}^T\mathbf X \mathbf W \mathbf X^T\mathbf {\vec a}}{\mathbf{\vec a}^T\mathbf X \mathbf D \mathbf X^T\mathbf {\vec a} }$。
   • $\mathcal O(\cdot)$ 表示某些算法的目标函数，如 $\mathcal O(\text{SVM classifier})$ 表示 SVM 分类器的目标函数。

   

4. 上述讨论都是假设 embedding 为一维的。事实上如果希望 embedding 是多维的，如 $d$ 维，则选择的不是最大特征值对应的特征向量，而是 top d 特征值对应的特征向量。

2> Node Proximity Matrix

1. 除了上述求解广义特征值方法之外，另一个方向是试图直接分解顶点邻近度矩阵。可以基于矩阵分解技术在低维空间中逼近approximate 顶点邻近度，使得顶点邻近度的逼近损失最小化。

   给定顶点邻近度矩阵 $\mathbf W$ ，则这种方法的目标函数为：

   $$\min||\mathbf W - \mathbf Y \left(\mathbf Y^c\right)^T||$$

   其中：

   • $\mathbf Y\in \mathbb R^{|V|\times d}$ 为顶点的 embedding 矩阵
   • $\mathbf Y^c\in \mathbb R^{|V|\times d}$ 为顶点的content embedding 矩阵

   该目标函数是寻找邻近度矩阵 $\mathbf W$ 的一个最优低秩近似。一种流行的求解方法是对 $\mathbf W$ 进行 SVD 分解：

   $$\mathbf W = \sum_{i=1}^{|V|} \sigma_i \mathbf{\vec u}_i \left(\mathbf{\vec u}_i^c\right)^T \simeq \sum_{i=1}^{d} \sigma_i \mathbf{\vec u}_i \left(\mathbf{\vec u}_i^c\right)^T$$

   其中：

   • $\{\sigma_1,\sigma_2,\cdots,\sigma_{|V|}\}$ 为邻近度矩阵 $\mathbf W$ 的从大到小排序的奇异值
   • $\mathbf{\vec u}_i,\mathbf{\vec u}_i^c$ 为奇异值 $\sigma_i$ 对应的奇异向量

   则我们得到最优 embedding 为：

   $$\mathbf Y = [\sqrt\sigma_1\;\mathbf{\vec u}_1,\cdots,\sqrt\sigma_d\;\mathbf{\vec u}_d ]\\ \mathbf Y^c = [\sqrt\sigma_1\;\mathbf{\vec u}_1^c,\cdots,\sqrt\sigma_d\;\mathbf{\vec u}_d ^c]$$

   根据是否保留不对称性，顶点 $v_i$ 的 embedding 可以为 $\mathbf{\vec y}_i$ ，其中 $\mathbf{\vec y}_i$ 为 $\mathbf Y$ 的第 $i$ 行 ；也可以为 $\mathbf{\vec y}_i$ 和 $\mathbf{\vec y}_i^c$ 的拼接，即 $[\mathbf{\vec y}_i,\mathbf{\vec y}_i^c]$ ，其中 $\mathbf{\vec y}_i^c$ 为 $\mathbf Y^c$ 的第 $i$ 行。

2. 我们在下表中总结了更多的矩阵分解方案，例如正则化的高斯矩阵分解、正则化的低秩矩阵分解、带更多正则化约束的矩阵分解等。

   其中：Eq.5 表示目标函数 $\min||\mathbf W - \mathbf Y \left(\mathbf Y^c\right)^T||$ 。

   

b. 深度学习

1. 基于深度学习的 graph embedding 在图上应用深度学习模型，这些模型的输入可以是从图采样得到的路径，也可以是整个图本身。因此基于是否采用随机游走从图中采样路径，我们将基于深度学习的 graph embedding 分为两类：带随机游走的 deep learning、不带随机游走的 deep learning。

2. 基于带随机游走的 deep learning的 graph embedding 的思想是：对于给定的顶点，通过最大化给定该顶点 embedding 时，最大化该顶点邻域的条件概率则可以在 embedding 空间中保留图的二阶邻近度。

   在基于带速记有着的deep learning 的 grap emebdding 中，图表示为从图中采样的一组随机游走序列。然后深度学习模型被应用于这些随机游走序列从而执行 grap embedding 。在嵌入过程中，embedding 保留了这些随机游走序列携带的图属性。

   基于以上的洞察，DeepWalk 采用神经语言模型（SkipGram） 执行 grap embedding，其中 SkipGram 旨在最大化窗口内单词之间的共现概率。DeepWalk 首先应用截断的随机游走从输入图采样一组随机序列，然后将 SkipGram 应用于采样到的随机序列，从而最大化给定顶点条件下顶点邻域出现的概率。通过这种方式，相似邻域（具有较大的二阶邻近度）的顶点共享相似的 embedding 。

   DeepWalk 的目标函数为：

   $$\min_{\mathbf Y}\sum_i -\log P\left(\{v_{i-w},\cdots, v_{i-1},v_{i+1},\cdots,v_{i+w}\}\mid \mathbf{\vec y}_i\right)$$

   其中： $\mathbf{\vec y}_i\in \mathbb R^d$ 为顶点 $v_i$ 的 embedding ； $w$ 为上下文窗口的大小。

   SkipGram 不考虑窗口内顶点的属性，因此有：

   $$\log P\left(\{v_{i-w},\cdots, v_{i-1},v_{i+1},\cdots,v_{i+w}\}\mid \mathbf{\vec y}_i\right) = \sum_{-w\le j\le w, j\ne 0} \log P(v_{i+j}\mid \mathbf{\vec y}_i)$$

   其中 $P(v_{i+j}\mid \mathbf{\vec y}_i)$ 表示给定顶点 $v_i$ 的 embedding 时，顶点 $v_{i+j}$ 位于 $v_i$ 上下文窗口 $w$ 内的概率。这个条件概率定义为 softmax 函数：

   $$P(v_{i+j}\mid \mathbf{\vec y}_i) = \frac{\exp \left(\mathbf{\vec y}_{i+j}^T \mathbf{\vec y}_{i} \right)}{\sum_{k=1}^{|V|}\exp \left(\mathbf{\vec y}_{k}^T \mathbf{\vec y}_{i} \right)}$$

   上述概率难以计算，因为分母需要计算 $\mathbf{\vec y}_i$ 和图中所有顶点的 embedding 的内积，算法复杂度为 $O(|V|)$ 。为降低算法复杂度，有两种解决方案：

   • Hierarchical Softmax：我们构造二叉树来高效计算 $P(v_{i+j}\mid \mathbf{\vec y}_i)$ ，其中将每个顶点分配给二叉树的叶节点。现在我们仅需要评估从二叉树根节点到相应叶子节点的路径的概率。

     假设根节点到叶节点 $v_j$ 的节点路径为 $(b_0,b_1,\cdots,b_{\log (|V|)})$ ，其中 $b_0 = \text{root}$ ， $b_{\log(|V|)} = v_j$ ，则有：

     $$P(v_{i+j}\mid \mathbf{\vec y}_i) = \prod_{t=1}^{\log (|V|)}P(b_t\mid \mathbf{\vec y}_i)$$

     $P(b_t\mid \mathbf{\vec y}_i)$ 为一个二元分类器 $P(b_t\mid \mathbf{\vec y}_i) = \sigma(\mathbf{\vec y}^T_{b_t}\mathbf{\vec y}_i)$ ，其中： $\sigma(\cdot)$ 为 sigmoid 函数； $\mathbf{\vec y}^T_{b_t}$ 为 $b_t$ 的父节点的 embedding。

     现在 Hierarchical Softmax 函数将 SkipGram 的时间复杂度从 $O(|V|^2)$ 降低到 $O(|V|\times \log (|V|))$ 。

   • 负采样：负采样的核心思想是将目标顶点和噪声区分开来。即对于顶点 $v_i$ ，我们希望将其邻居 $v_{i+j}$ 和其它顶点区分开。我们使用一个噪音分布 $P_n(v_i)$ 为顶点 $v_i$ 采样一组噪音顶点，称为负样本。因此 $P(v_{i+j}\mid \mathbf{\vec y}_i)$ 计算为：

     $$P(v_{i+j}\mid \mathbf{\vec y}_i) = \log \sigma(\mathbf{\vec y}_{i+j}^T \mathbf{\vec y}_i) + \sum_{t=1}^K \mathbb E_{v_t\sim P_n}[\log \sigma(-\mathbf{\vec y}_{v_t}^T\mathbf{\vec y}_i)]$$

     其中： $K$ 为负样本数量； $v_t$ 为采样到的负样本。

     通常 $P_n(v_i)$ 选择一个均匀分布 $P_n(v_i)\sim \frac{1}{|V|}$ ，也可以选择其它分布。

     最终负采样将 SkipGram 的时间复杂度从 $O(|V|^2)$ 降低到 $O(K |V|)$ 。

   DeepWalk 的成功引起了很多后续的研究，这些研究在graph embedding 的采样路径上应用了各种深度学习模型（如 SkipGram 或 LSTM），我们在下表中总结了这些方法。其中：

   • Eq.11 表示 $P(v_{i+j}\mid \mathbf{\vec y}_i) = \prod_{t=1}^{\log (|V|)}P(b_t\mid \mathbf{\vec y}_i)$
   • Eq.12 表示 $P(v_{i+j}\mid \mathbf{\vec y}_i) = \log \sigma(\mathbf{\vec y}_{i+j}^T \mathbf{\vec y}_i) + \sum_{t=1}^K \mathbb E_{v_t\sim P_n}[\log \sigma(-\mathbf{\vec y}_{v_t}^T\mathbf{\vec y}_i)]$

   如下表所示，大多数研究都遵循了 DeepWalk 思想，但是改变了随机游走采样方法或者要保留的邻近度。注意：SkipGram 仅能嵌入单个顶点，如果需要嵌入一个顶点序列到固定维度的向量（如将一个句子嵌入为一个向量），则需要使用 LSTM 。

   

3. 不基于带随机游走的 deep learning的 graph embedding 的思想是：多层神经网络体系结构是将图编码到低维空间的强大、有效的solution 。

   这一类deep learning 方法直接将深度神经网络应用于整个图（或者图的邻接矩阵）。以下是一些用于 graph embedding 的流行深度学习模型：

   • 自编码器 autoencoder：自编码器旨在通过其编码器encoder 和解码器 decoder，使得自编码器的输出和输入的重构误差最小。编码器和解码器都包含多个非线性函数，其中编码器将输入数据映射到表示空间、解码器将表示空间映射到重构空间。

     就邻域保持而言，采用自编码器的 grap embedding 思想类似于顶点邻近度矩阵分解。具体而言，由于邻接矩阵包含了顶点的邻域信息，因此如果将邻接矩阵作为自编码器的输入，则重构过程将使得具有相似邻域的顶点具有相似的 embedding 。

   • Deep Neural Network：一些工作尝试将深度神经网络推广到非欧几何邻域（如，图结构）。这些方法之间的差异在于它们在图上采取了不同的、类似于卷积的运算方式。

   还有一些其它的基于深度学习的 graph embedding 方法。我们在下表中总结了所有基于深度学习的 graph embedding 方法，并比较了它们使用的模型以及每个模型的输入。

   

4. 总结：由于深度学习的鲁棒性和有效性，深度学习已被广泛应用于 graph emebdding 中。除了人工构造的图之外，所有类型的图输入以及所有类型的 embedding 输出都可以应用基于深度学习的 graph embedding 方法。

c. 边重构

1. 基于边重建edge reconstruction 的 node embedding 基本思想是：通过 node embedding 重建的边应该和输入图中的边尽可能一致。

   因此，基于边重建的node embedding 方法通过最大化边的重建概率或最小化边的重建损失，从而优化边重建的目标函数。其中重建损失又分为 distance-based 损失和 margin-based ranking 损失。

2. 最大化边的重建概率的基本思想是：好的顶点 embedding 应该能够最大程度地重建图中的边。

   因此，该方法最大化所有观察到的边的生成概率。给定顶点 $v_i,v_j$ 的 embedding $\mathbf{\vec y}_i,\mathbf{\vec y}_j$，我们计算边的生成的概率为联合概率：

   $$p^{(1)}(v_i,v_j) = \frac{1}{1+\exp\left(-\mathbf{\vec y}_i^T\mathbf{\vec y}_j\right)}$$

   它表示顶点 $v_i,v_j$ 之间存在边的概率，即一阶邻近度。

   为学习node embedding，我们最大化图中所有边的生成概率，因此目标函数为：

   $$\mathcal O_{\max}^{(1)} = \max\sum_{e_{i,j}\in E} \log p^{(1)}(v_i,v_j)$$

   类似地，顶点 $v_i,v_j$ 之间的二阶邻近性为给定 $v_i$ 的条件下生成顶点 $v_j$ 的条件概率。它可以解释为图中从顶点 $v_i$ 开始、以 $v_j$ 结束的随机游走的概率。这个概率为：

   $$p^{(2)}(v_j\mid v_i) = \frac{\exp\left(\mathbf{\vec y}_j^T\mathbf{\vec y}_i\right)}{\sum_{k=1}^{|V|}\exp\left( \mathbf{\vec y}_k^T\mathbf{\vec y}_i\right)}$$

   则最大化二阶邻近性的目标函数为：

   $$\mathcal O_{\max}^{(2)} = \max\sum_{\{v_i,v_j\}\in \mathcal P} \log p^{(1)}(v_j\mid v_i)$$

   其中 $\mathcal P$ 为图中随机游走序列中随机选择的 {开始顶点， 结束顶点} 组成的集合，即从每条随机游走序列上随机截取的两个点。这使得顶点之间的二阶邻近度转换为从起点到终点的随机游走概率。

3. 最小化边的重建distance-based 损失的基本思想：通过 node embedding 计算的顶点邻近度，应该尽可能和图中通过边计算的顶点邻近度一致，从而最小化邻近度之间的差异，最终保留图的邻近度属性。

   通过 node embedding 计算的一阶邻近度为：

   $$p^{(1)}(v_i,v_j) = \frac{1}{1+\exp\left(-\mathbf{\vec y}_i^T\mathbf{\vec y}_j\right)}$$

   而通过图中边计算的经验一阶邻近度为：

   $$\hat p^{(1)}(v_i,v_j) = \frac{W_{i,j}}{\sum_{e_{i,j}\in E} W_{i,j}}$$

   其中 $W_{i,j}$ 为边 $e_{i,j}$ 的权重。

   $p^{(1)}$ 和 $\hat p^{(1)}$ 之间的距离越小，则一阶邻近度保留得越完整。我们以 KL 散度为距离函数来计算 $p^{(1)}$ 和 $\hat p^{(1)}$ 之间的距离，并忽略掉一些常数项，则保留一阶邻近度的目标函数为：

   $$\mathcal O_{\min}^{(1)} = \min -\left(\sum_{e_{i,j}\in E} W_{i,j} \log p^{(1)}(v_i,v_j)\right)$$

   类似地，通过 node embedding 计算的二阶邻近度为：

   $$p^{(2)}(v_j\mid v_i) = \frac{\exp\left(\mathbf{\vec y}_j^T\mathbf{\vec y}_i\right)}{\sum_{k=1}^{|V|}\exp\left( \mathbf{\vec y}_k^T\mathbf{\vec y}_i\right)}$$

   而通过图中边计算的经验二阶邻近度为：

   $$\hat p^{(2)} (v_j\mid v_i) = \frac{W_{i,j}}{d_i}$$

   其中 $d_i = \sum_{e_{i,k}\in E} W_{i,k}$ 为顶点的 out-degree（或者在无向图中就是顶点的 degree）。

   同样地，由于计算 $p^{(2)}(v_j\mid v_i)$ 的代价较大，这里我们也采用负采样技术来提高效率。

   $p^{(2)}$ 和 $\hat p^{(2)}$ 之间的距离越小，则二阶邻近度保留得越完整。我们以 KL 散度为距离函数来计算 $p^{(2)}$ 和 $\hat p^{(2)}$ 之间的距离，并忽略掉一些常数项，则保留二阶邻近度的目标函数为：

   $$\mathcal O_{\min }^{(2)} = \min -\left(\sum_{e_{i,j}\in E} W_{i,j} \log p^{(2)}(v_j\mid v_i)\right)$$

4. 最小化边的重建margin-based 损失的基本思想：边暗示了一对顶点之间的相关性relevance。因此，对于一个顶点 A，假设它和顶点 B 存在边、和顶点 C 不存在边，则在顶点 B 和 C 之间，顶点 A 的 embedding 和顶点 B 的embedding 更相似。

   定义 $s(v_i,v_j)$ 为顶点 $v_i$ 和 $v_j$ 之间的相似性， $V_i^+$ 表示和顶点 $v_i$ 相关的顶点集合， $V_i^-$ 表示和顶点 $v_i$ 之间无关的顶点集合。则 margin-based ranking loss 为：

   $$\mathcal O_{\text{rank}} = \min \sum_{v_i^+\in V_i^+}\sum_{v_i^-\in V_i^-} \max\{0, \gamma -(s(v_i,v_i^+) - s(v_i,v_i^-))\}$$

   其中 $\gamma$ 为 margin 参数。

   最小化该损失函数鼓励 $s(v_i,v_i^+)$ 和 $s(v_i,v_i^-)$ 之间较大的 margin，励因此鼓励 $v_i$ 嵌入到相关顶点附近、并远离非相关顶点。

5. 下表中我们总结了现有的利用 graph embedding 的边重建技术，给出了它们的目标函数和保留的顶点邻近度。通常大多数方法使用上述目标函数之一。注意：当在 graph embedding 期间同时优化另一个任务时，该 task-specific 目标函数将融合到总的目标函数中。

   

6. 大多数现有的知识图谱embedding 方法都选择优化margin-based ranking 损失函数。知识图谱 $\mathcal G$ 由大量的三元组 $<h,r,t>$ 组成，表明 head entity $h$ 通过关系 $r$ 连接到 tail entity $t$ 。对 $\mathcal G$ 的 embedding 可以解释为保留图的排名ranking属性，使得真实的三元组 $<h,r,t>$ 的排名高于虚拟的三元组 $<h^\prime, r,t^\prime>$ （后者在 $\mathcal G$ 中不存在）。

   特别是在知识图谱 embedding 中，我们设计了能量函数 $f_r(h,t)$ ，它类似于 $\mathcal O_{\text{rank}}$ 中的 $s(v_i,v_i^+)$ 。但是这两个函数略有不同：$s(v_i,v_i^+)$ 表示顶点 $v_i$ 和 $v_i^+$ 的 embedding 之间的相似性得分，而 $f_r(h,t)$ 表示 $h$ 和 $t$ 在关系 $r$ 上的 embedding 的距离得分。

   $f_r(h,t)$ 的一个选择是 $||h +r-t||_{l_1}$ ，其中关系视为 embedding 空间的转换。可选的 $f_r(h,t)$ 在下表中所示。

   最终，知识图谱的 graph embedding 目标函数为：