Graph Embedding 综述

一、A Comprehensive Survey of Graph Embedding[2017]

1. 图自然存在于现实世界的各种场景中，例如社交媒体网络中的社交图/扩散图、研究领域的引文图、电商领域的用户兴趣图、知识图等。有效的图分析可以使很多应用受益，如节点分类、节点聚类、节点检索/推荐、链接预测等。尽管图分析graph analytics 是实用的和必要的，但大多数现有的图分析方法都存在昂贵的计算成本和空间成本的问题。然而，图嵌入graph embedding提供了一种有效而高效的方法来解决图分析问题。具体来说，graph embedding将图转换为一个低维空间，其中的图信息被保留下来。通过将图表示为一个（或一组）低维向量，然后可以有效地计算图算法。

   graph embedding的问题与两个传统的研究问题有关，即图分析和 representation learning：

   • 一方面，图分析的目的是从图数据中挖掘有用的信息。
   • 另一方面， representation learning 的目的是获得更好的data representation 从而用于构建分类器或其他预测器。

   graph embedding 位于这两个问题的重叠部分，侧重于学习低维representation。这里区分了graph rerpesentation learning和 graph embedding 。注意，graph rerpesentation learning 并不要求学到的 representation 是低维的。

   将图嵌入到低维空间并不是一件简单的事情。graph embedding 的挑战取决于问题的设置，它由嵌embedding input和embedding output组成。论文 《A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications》将 input graph 分为四类，包括同质图 homogeneous graph 、异质图 heterogeneous graph 、带有辅助信息的图、和由非关系型数据non-relational data 构建的图。

   • 不同类型的embedding input 带有不同的信息要在emebdding 空间中保留，因此对图的嵌入问题提出了不同的挑战。例如，当嵌入一个只有结构信息的图时，节点之间的连接是需要保留的目标。然而，对于带有节点标签或属性信息的图来说，辅助信息（即节点标签、属性信息）从其他角度提供了图的属性，因此在嵌入过程中也需要被考虑。

   • 与embedding input 是给定的、固定的不同，embedding output 是任务驱动的。例如，最常见的 embedding output 类型是 node embedding ，它将临近的节点表示为相似的向量。 node embedding 可以有利于节点相关的任务，如节点分类、节点聚类等。

     然而，在某些情况下，目标任务可能与图的更高粒度有关，例如，node pair、子图、整个图。因此，在 embedding output 方面的第一个挑战是为目标任务找到一个合适的 embedding output 类型。论文 《A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications》 将 graph embedding output 分为四种类型，包括 node embedding 、edge embedding 、hybrid embedding 和 whole-graph embedding 。

     不同的输出粒度对 good embedding 有不同的标准，并面临不同的挑战。例如，一个好的 node embedding 保留了与嵌入空间中的邻近节点的相似性。相比之下，一个好的 whole-graph embedding 将整个图表示为一个矢量，这样就可以保留graph-level的相似性。

   根据对不同问题设置中所面临的挑战的观察，作者提出了两个 graph embedding工作的分类法，即根据问题设置和嵌入技术对 graph embedding文献进行分类。具体而言：

   • 作者首先介绍了 graph embedding问题的不同设置，以及在每个设置中面临的挑战。
   • 然后，作者描述现有研究如何在他们的工作中解决这些挑战，包括他们的见解和他们的技术解决方案。

   需要注意的是，尽管已经有一些尝试来综述 graph embedding，但它们有以下两个局限性：

   • 首先，他们通常仅根据 graph embedding技术来进行分类。他们都没有从问题设置的角度分析 graph embedding工作，也没有总结每个问题设置中的挑战。
   • 其次，在现有的 graph embedding 综述中，仅涉及了有限的相关工作。例如，《Graph embedding techniques, applications, and performance: A survey》 主要介绍了12 种有代表性的 graph embedding 算法，《Knowledge graph embedding: A survey of approaches and applications》 只关注知识图的嵌入。此外，没有对每种 graph embedding 技术背后的洞察力进行分析。

   论文贡献：

   • 论文提出了一个基于问题设置的 graph embedding分类法，并总结了每个设置中面临的挑战。作者是第一个根据问题设置对 graph embedding 工作进行分类的人，这为理解现有工作带来了新的视角。
   • 论文对 graph embedding 技术进行了详细的分析。与现有的 graph embedding 综述相比，论文不仅综述了一套更全面的 graph embedding 工作，而且还提出了每个技术背后的见解总结。与简单地罗列过去如何解决 graph embedding 的问题相比，总结的见解回答了问题：为什么能（以某种方式）解决 graph embedding 问题。
   • 论文对 graph embedding 的应用进行了系统的分类，并将这些应用划分为节点相关、边相关、图相关。对于每个类别，论文提出了详细的应用场景作为参考。
   • 在计算效率、问题设置、解决技术和应用方面，论文在 graph embedding 领域提出了四个有希望的未来研究方向。对于每个方向，论文对其在当前工作中的缺点（不足）进行了全面分析，并提出了未来的研究方向。

1.1 定义

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

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

   定义：

   • 同质图 ${\mathcal{G}}_{\text{homo}}=(V,E)$$\mathcal G_{\text{homo}} = (V,E)$ ，其中 $|{\mathcal{T}}^v|=|{\mathcal{T}}^e|=1$$|\mathcal T^v| = |\mathcal T^e| = 1$ 。 ${\mathcal{G}}_{\text{homo}}$$\mathcal G_{\text{homo}}$ 的所有节点只有一个类型，所有边也只有一个类型。
   • 异质图 ${\mathcal{G}}_{\text{hete}}=(V,E)$$\mathcal G_{\text{hete}} = (V,E)$ ，其中 $|{\mathcal{T}}^v|+|{\mathcal{T}}^e|>1$$| \mathcal T^v| + |\mathcal T^e| \gt 1$ ，即 ${\mathcal{G}}_{\text{hete}}$$\mathcal G_{\text{hete}}$ 的节点和/或边有多个类型。
   • 知识图谱 knowledge graph ${\mathcal{G}}_{\text{know}}=(V,E)$$\mathcal G_{\text{know}} = (V,E)$ 为一个有向图，节点为实体 entity，边为subject-property-object 三元组。每条边由 (head entity, relation, tail entity) 的形式组成，记作 $<h,r,t>$$<h,r,t>$ ，它表示从实体 $h$$h$ 到实体 $h$$h$ 的关系 $r$$r$ ，其中 $h,t\in V$$h,t\in V$ 为实体， $r\in E$$r\in E$ 为边。我们称 $<h,r,t>$$<h,r,t>$ 为知识图谱三元组。注意，知识图谱中节点通常具有不同类型，边通常也具有不同类型，因此知识图谱也可以视为一个异质图。

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

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

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

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

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

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

   可以采用递归定义：

   $$\begin{array}{c}{s}_{i,j}^{(k)}=\cos ({\overrightarrow{\mathbf{s}}}_i^{(k-1)},{\overrightarrow{\mathbf{s}}}_j^{(k-1)}),k\ge 2\\ {\overrightarrow{\mathbf{s}}}_i^{(1)}=[s_{i,1}^{(1)},s_{i,2}^{(1)},\cdots ,s_{i,|V|}^{(1)}]\end{array}$$

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

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

   • 可以将整张图表示为一个 $d$$d$ 维向量。
   • 也可以将单张图表示为一组 $d$$d$ 维向量，其中每个向量表示图中部分组件的 embedding （如节点、边、子结构）。

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

   

1.2 问题

1.2.1 Graph Embedding Input

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

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

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

3. 异质图：异质图包含三种场景：

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

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

   挑战：

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

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

   • 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 同时编码了图的拓扑结构和辅助信息？除了图结构信息之外，辅助信息还有助于定义节点相似性。因此如何融合图拓扑结构和辅助信息这两个信息源，这是一个问题。

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

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

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

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

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

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

   挑战：

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

1.2.2 Graph Embedding Output

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

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

2. node embedding ：将每个节点表示为低维空间中的向量，图中临近的节点在 embedding 空间中有相似的向量表示。

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

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

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

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

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

   挑战：

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

4. hybrid embedding：嵌入图的不同类型的组件，如 node + edge （子结构 substructure ）、node + community。

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

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

   挑战：

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

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

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

   挑战：

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

1.3 技术

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

1.3.1 矩阵分解

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

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

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

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

a. Graph Laplacian Eigenmaps

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

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

   $${\overrightarrow{\mathbf{y}}}^{\ast }=\arg min\sum _{i\ne j}(y_i-y_j{)}^2{W}_{i,j}=\arg min{\overrightarrow{\mathbf{y}}}^{\mathrm{\top }}\mathbf{L}\overrightarrow{\mathbf{y}}$$

   假设 embedding 维度为 $d$$d$ 维，则可以分别针对每一维来计算最优的 embedding。

   其中：

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

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

   $${\overrightarrow{\mathbf{y}}}^{\ast }=\arg \underset{{\overrightarrow{\mathbf{y}}}^{\mathrm{\top }}\mathbf{D}\overrightarrow{\mathbf{y}}=1}{min}{\overrightarrow{\mathbf{y}}}^{\mathrm{\top }}\mathbf{L}\overrightarrow{\mathbf{y}}=\arg min\frac{{\overrightarrow{\mathbf{y}}}^{\mathrm{\top }}\mathbf{L}\overrightarrow{\mathbf{y}}}{{\overrightarrow{\mathbf{y}}}^{\mathrm{\top }}\mathbf{D}\overrightarrow{\mathbf{y}}}=\arg max\frac{{\overrightarrow{\mathbf{y}}}^{\mathrm{\top }}\mathbf{W}\overrightarrow{\mathbf{y}}}{{\overrightarrow{\mathbf{y}}}^{\mathrm{\top }}\mathbf{D}\overrightarrow{\mathbf{y}}}$$

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

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

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

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

   $${\overrightarrow{\mathbf{a}}}^{\ast }=\arg min\sum _{i\ne j}({\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_i-{\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_j{)}^2{W}_{i,j}=\arg min{\mathbf{a}}^{\mathrm{\top }}\mathbf{X}\mathbf{L}{\mathbf{X}}^{\mathrm{\top }}\overrightarrow{\mathbf{a}}$$

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

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

   $${\overrightarrow{\mathbf{a}}}^{\ast }=\arg min\frac{{\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}\mathbf{X}\mathbf{L}{\mathbf{X}}^{\mathrm{\top }}\overrightarrow{\mathbf{a}}}{{\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}\mathbf{X}\mathbf{D}{\mathbf{X}}^{\mathrm{\top }}\overrightarrow{\mathbf{a}}}=\arg max\frac{{\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}\mathbf{X}\mathbf{W}{\mathbf{X}}^{\mathrm{\top }}\overrightarrow{\mathbf{a}}}{{\overrightarrow{\mathbf{a}}}^{\mathrm{\top }}\mathbf{X}\mathbf{D}{\mathbf{X}}^{\mathrm{\top }}\overrightarrow{\mathbf{a}}}$$

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

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

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

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

   • 最初的研究 MDS 直接采用两个特征向量 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 和 ${\overrightarrow{\mathbf{x}}}_j$$\mathbf{\vec x}_j$ 之间的欧氏距离作为 $W_{i,j}$$W_{i,j}$。MDS 不考虑节点的相邻关系，也就是说，任何一对训练样本都被认为是相连的。

   • 后续研究（如Isomap、LE、LPP、LLE ）通过首先从数据特征中构建一个 k nearest neighbour graph 来克服这个问题。每个节点只与它的 top-k 相似邻居相连。之后，利用不同的方法来计算相似性度矩阵 $\mathbf{W}$$\mathbf W$ 从而尽可能多地保留所需的图属性。

   • 最近设计了一些更先进的模型。例如：

     • AgLPP 入了一个 anchor graph ，以显著提高 LPP 的效率。
     • LGRM 学习了一个 local regression model 来掌握图的结构，以及一个全局回归global regression 项来进行 out-of-sample 的数据推断。
     • 最后，与之前保留 local geometry 的工作不同，LSE 使用 local spline regression 来保留 global geometry。

   • 当辅助信息（如label、属性）可用时，目标函数被调整以保留更丰富的信息：

     • 例如，SR构建了一个邻接图adjacent graph $\mathbf{W}$$\mathbf W$ 和一个标记图 labelled graph ${\mathbf{W}}^{\text{SR}}$$\mathbf W^\text{SR}$。目标函数由两部分组成：一部分侧重于保留 LPP 数据集的局部几何结构 local geometric structure ，另一部分试图在标记的训练数据上获得最佳类别可分的embedding 。
     • 同样，ARE 也构建了两个图：一个是编码局部几何结构的邻接图 $\mathbf{W}$$\mathbf W$，一个是编码用户相关性反馈中 pairwise relation 的 feedback relational graph ${\mathbf{W}}^{\text{ARE}}$$\mathbf W^\text{ARE}$。
     • RF-Semi-NMF-PCA 的目标函数由三个部分组成，从而同时考虑聚类、降维和 graph embedding：PCA、k-means 和 graph Laplacian regularization 。

   • 其他一些工作认为，不能通过简单地枚举成对的节点关系来构建 $\mathbf{W}$$\mathbf W$，相反它们采用 semidefinite programming: SDP 来学习 $\mathbf{W}$$\mathbf W$ 。具体而言：

     • SDP 旨在找到一个内积矩阵，使图中不相连的任何两个输入之间的成对距离最大化，同时保留最近的邻居距离。
     • MVU 构建了这样的矩阵，然后将MDS 应用于学到的内积矩阵。《Unsupervised large graph embedding》证明：如果 $\mathbf{W}$$\mathbf W$ 是对称的、双随机的、PSD 的、以及秩为 $p$$p$ 的，则正则化的LPP 等价于正则化的 SR。

   

b. Node Proximity Matrix

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

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

   $$min\Vert \mathbf{W}-\mathbf{Y}{\left({\mathbf{Y}}^c\right)}^{\mathrm{\top }}\Vert$$

   其中：

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

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

   $$\mathbf{W}=\sum _{i=1}^{|V|}{\sigma }_i{\overrightarrow{\mathbf{u}}}_i{\left({\overrightarrow{\mathbf{u}}}_i^c\right)}^{\mathrm{\top }}\simeq \sum _{i=1}^d{\sigma }_i{\overrightarrow{\mathbf{u}}}_i{\left({\overrightarrow{\mathbf{u}}}_i^c\right)}^{\mathrm{\top }}$$

   其中：

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

   则我们得到最优 embedding 为：

   $$\begin{array}{c}\mathbf{Y}=[{\sqrt{\sigma }}_1{\overrightarrow{\mathbf{u}}}_1,\cdots ,{\sqrt{\sigma }}_d{\overrightarrow{\mathbf{u}}}_d]\\ {\mathbf{Y}}^c=[{\sqrt{\sigma }}_1{\overrightarrow{\mathbf{u}}}_1^c,\cdots ,{\sqrt{\sigma }}_d{\overrightarrow{\mathbf{u}}}_d^c]\end{array}$$

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

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

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

   

1.3.2 深度学习

1. 基于深度学习的 graph embedding 在图上应用深度学习模型，这些模型的输入可以是从图采样得到的路径，也可以是整个图本身。因此基于是否采用随机游走从图中采样路径，我们将基于深度学习的 graph embedding 分为两类：带随机游走的 deep learning、不带随机游走的 deep learning。
2. 总结：由于深度学习的鲁棒性和有效性，深度学习已被广泛应用于 graph emebdding 中。除了人工构造的图之外，所有类型的图输入以及所有类型的 embedding 输出都可以应用基于深度学习的 graph embedding 方法。

a. Deep Learning based Graph Embedding with Random Walk

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

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

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

   DeepWalk 的目标函数为：

   $$\underset{\mathbf{Y}}{min}\sum _i-\log P(\{v_{i-w},\cdots ,v_{i-1},v_{i+1},\cdots ,v_{i+w}\}\mid {\overrightarrow{\mathbf{y}}}_i)$$

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

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

   $$\log P(\{v_{i-w},\cdots ,v_{i-1},v_{i+1},\cdots ,v_{i+w}\}\mid {\overrightarrow{\mathbf{y}}}_i)=\sum _{-w\le j\le w,j\ne 0}\log P(v_{i+j}\mid {\overrightarrow{\mathbf{y}}}_i)$$

   这里假设给定节点 $v_i$$v_i$ 的条件下，上下文窗口内的各节点之间相互独立。

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

   $$P(v_{i+j}\mid {\overrightarrow{\mathbf{y}}}_i)=\frac{\exp \left({\overrightarrow{\mathbf{y}}}_{i+j}^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i\right)}{\sum _{k=1}^{|V|}\exp \left({\overrightarrow{\mathbf{y}}}_k^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i\right)}$$

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

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

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

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

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

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

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

     $$P(v_{i+j}\mid {\overrightarrow{\mathbf{y}}}_i)=\log \sigma \left({\overrightarrow{\mathbf{y}}}_{i+j}^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i\right)+\sum _{t=1}^K{\mathbb{E}}_{v_t\sim P_n}[\log \sigma (-{\overrightarrow{\mathbf{y}}}_{v_t}^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i)]$$

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

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

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

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

   • Eq.11 表示 $P(v_{i+j}\mid {\overrightarrow{\mathbf{y}}}_i)=\prod _{t=1}^{\log (|V|)}P(b_t\mid {\overrightarrow{\mathbf{y}}}_i)$$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 {\overrightarrow{\mathbf{y}}}_i)=\log \sigma \left({\overrightarrow{\mathbf{y}}}_{i+j}^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i\right)+\sum _{t=1}^K{\mathbb{E}}_{v_t\sim P_n}[\log \sigma (-{\overrightarrow{\mathbf{y}}}_{v_t}^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i)]$$P(v_{i+j}\mid \mathbf{\vec y}_i) = \log \sigma\left(\mathbf{\vec y}_{i+j}^\top \mathbf{\vec y}_i\right) + \sum_{t=1}^K \mathbb E_{v_t\sim P_n}\left[\log \sigma\left(-\mathbf{\vec y}_{v_t}^\top\mathbf{\vec y}_i\right)\right]$ 。

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

   

b. Deep Learning based Graph Embedding without Random Walk

1. 不基于带随机游走的 deep learning的 graph embedding 的思想是：深度神经网络体系结构是将图编码到低维空间的强大、有效的解决方案。

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

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

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

   • Deep Neural Network：卷积神经网络及其变种已被广泛用于graph embedding。

     • 一些工作直接使用原始 CNN 模型，并对 input graph 进行重构从而适应 CNN 。
     • 另一些工作尝试将深度神经网络推广到非欧几何邻域（如，图结构）。这些方法之间的差异在于它们在图上采取了不同的、类似于卷积的运算方式。例如，模仿卷积定理来定义谱域中的卷积、以及将卷积视为空间域中的邻域匹配。

   • 还有一些其他类型的基于深度学习的 graph embedding 方法，如：

     • DUIF 使用 hierarchical softmax 作为前向传播来最大化modularity 。
     • HNE 利用深度学习技术来捕捉异质组件之间的交互，如 CNN 组件用于图片、FC 层用于文本。

我们在下表中总结了所有不带随机游走的基于深度学习的 graph embedding 方法，并比较了它们使用的模型以及每个模型的输入。

1.3.3 边重构

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

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

2. 总结：基于边重构的方法适用于大多数 grap embedding 场景。根据我们的观察发现，只有非关系数据中构建的人工图embedding 、 whole-graph embedding 还未应用这种方式。原因是：

   • 人工构造的图中，所谓的 “边” 是我们人工构造的，并没有真实的物理含义。而且不同的构造方式得到的 “边” 不同。

• 边仅代表两个节点之间的关系，因此基于边重建的方法聚焦于局部的连接性，因此它不适合whole-graph embedding 。

a. 最大化边的重建概率

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

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

   $$p^{(1)}(v_i,v_j)=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{y}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_j)}$$

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

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

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

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

   $$p^{(2)}(v_j\mid v_i)=\frac{\exp \left({\overrightarrow{\mathbf{y}}}_j^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i\right)}{\sum _{k=1}^{|V|}\exp \left({\overrightarrow{\mathbf{y}}}_k^{\mathrm{\top }}{\overrightarrow{\mathbf{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}$$\mathcal P$ 为图中随机游走序列中随机选择的 {start_node, end_node} 组成的集合，即从每条随机游走序列上随机截取的两个点。这使得节点之间的二阶邻近度转换为从起点到终点的随机游走概率。

b. 最小化基于距离的重建损失

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

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

   $$p^{(1)}(v_i,v_j)=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{y}}}_i^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_j)}$$

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

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

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

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

   $${\mathcal{O}}_{min}^{(1)}=min-(\sum _{e_{i,j}\in E}{W}_{i,j}\log p^{(1)}(v_i,v_j))$$

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

   $$p^{(2)}(v_j\mid v_i)=\frac{\exp \left({\overrightarrow{\mathbf{y}}}_j^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_i\right)}{\sum _{k=1}^{|V|}\exp \left({\overrightarrow{\mathbf{y}}}_k^{\mathrm{\top }}{\overrightarrow{\mathbf{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}$$d_i = \sum_{e_{i,k}\in E} W_{i,k}$ 为节点的 out-degree（或者在无向图中就是节点的 degree）。同样地，由于计算 $p^{(2)}(v_j\mid v_i)$$p^{(2)}(v_j\mid v_i)$ 的代价较大，这里我们也采用负采样技术来提高效率。

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

   $${\mathcal{O}}_{min}^{(2)}=min-(\sum _{e_{i,j}\in E}{W}_{i,j}\log p^{(2)}(v_j\mid v_i))$$

c. 最小化 Margin-based 排序损失

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

2. 定义 $s(v_i,v_j)$$s(v_i,v_j)$ 为节点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间的相似性， $V_i^{+}$$V_i^+$ 表示和节点 $v_i$$v_i$ 相关的节点集合， $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$$\gamma$ 为 margin 超参数。

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

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

   

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

   具体而言，在知识图谱 embedding 中，我们设计了能量函数 $f_r(h,t)$$f_r(h,t)$ ，它类似于 ${\mathcal{O}}_{\text{rank}}$$\mathcal O_{\text{rank}}$ 中的 $s(v_i,v_i^{+})$$s(v_i,v_i^+)$ 。但是这两个函数略有不同：

   • $s(v_i,v_i^{+})$$s(v_i,v_i^+)$ 表示节点 $v_i$$v_i$ 和 $v_i^{+}$$v_i^+$ 的 embedding 之间的相似性得分。
   • $f_r(h,t)$$f_r(h,t)$ 表示 $h$$h$ 和 $t$$t$ 在关系 $r$$r$ 上的 embedding 的距离得分。

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

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

   $${\mathcal{O}}_{\text{rank}}^{\text{kg}}=min\sum _{<h,r,t>\in \mathcal{S},<h^{\prime },r,t^{\prime }>\notin \mathcal{S}}max\{0,\gamma +f_r(h,t)-f_r(h^{\prime },t^{\prime })\}$$

   其中 $\mathcal{S}$$\mathcal S$ 为知识图谱中的三元组。

   现有知识图谱 embedding 方法主要优化上述 ${\mathcal{O}}_{\text{rank}}^{\text{kg}}$$\mathcal O_{\text{rank}}^{\text{kg}}$ ，它们之间的主要区别在于如何定义 $f_r(h,t)$$f_r(h,t)$ 。

   

1.3.4 Graph Kernel

1. Graph Kernel 的原理是：整个图结构可以表示为一个向量，其中向量每个分量表示被分解的基本子结构的计数。

2. Graph Kernel 是 R 卷积的一个实例，它是一种在离散的复合对象 discrete compound object 上定义 kernel 的一种通用方法。这种方法通过将结构化对象递归地分解为 “原子” 的子结构，并两两进行比较。Graph Kernel 将每个图表示为一个向量，并使用两个向量的内积来比较两个图的相似性。在Graph Kernel 中通常定义三种类型的 “原子” 子结构：Graphlet、Subtree Pattern、Random Walk 。

3. Graphlet：一个 Graphlet 是一个 size-k的、诱导的 induced、非同构的 non-isomorphic 子图。

   假设将图 $\mathcal{G}$$\mathcal G$ 分解为一组 graphlet $\{G_1,G_2,\cdots ,G_d\}$$\{G_1,G_2,\cdots,G_d\}$ ，则 $\mathcal{G}$$\mathcal G$ 可以嵌入为一个 $d$$d$ 维的归一化向量 ${\overrightarrow{\mathbf{y}}}_{\mathcal{G}}$$\mathbf{\vec y}_{\mathcal G}$ ，其中第 $i$$i$ 项表示 graphlet $G_i$$G_i$ 出现在 $\mathcal{G}$$\mathcal G$ 中的归一化频次。

4. Subtree Pattern：在这种 kernel 中，图被分解为 subtree pattern 。

   一个例子是 Weisfeiler-Lehman 子树。对于带标记的图（即具有离散型的节点标签）执行 relabeling 迭代过程。每次迭代过程中如下图所示：

   • 根据节点的标签及其邻居标签为节点得到 multiset label，multiset label 中对邻居标签进行升序排列。
   • 将 multiset label 映射称为新的label。这里使用字符串到 ID 的映射，也可以采用其它映射函数如哈希函数。
   • 使用新 label 执行 relabel 过程。

   假设在图 $\mathcal{G}$$\mathcal G$ 上执行 $h$$h$ 轮 relabelling 过程，则 embedding ${\overrightarrow{\mathbf{y}}}_{\mathcal{G}}$$\mathbf{\vec y}_\mathcal G$ 包含 $h$$h$ 个 block，第 $j$$j$ 个 block 的第 $i$$i$ 个元素表示第 $i$$i$ 个标签在第 $j$$j$ 轮迭代分配节点的频次。

   

5. Random Walk：在这种 kernel 中，图被分解为随机游走序列或路径（注意，这里的路径是固定的不是随机的），而 kernel 表示随机游走序列或路径出现的频次。

   以路径为例，假设图 $\mathcal{G}$$\mathcal G$ 分解为 $d$$d$ 条最短路径，其中第 $i$$i$ 条路径表示为三元组 $<l_i^s,l_i^e,n_i>$$<l_i^s,l_i^e, n_i>$ ， $l_i^s$$l_i^s$ 和 $l_i^e$$l_i^e$ 表示路径的开始节点的标签和结束节点的标签， $n_i$$n_i$ 为路径的长度。则 $\mathcal{G}$$\mathcal G$ 表示为一个 $d$$d$ 维向量 ${\overrightarrow{\mathbf{y}}}_{\mathcal{G}}$$\mathbf{\vec y}_\mathcal G$ ，其中第 $i$$i$ 个元素表示第 $i$$i$ 个三元组在 $\mathcal{G}$$\mathcal G$ 中出现的频次。

6. 总结：Graph Kernel 用于捕获整个图的全局属性，因此仅用于 whole-graph emebdding。输入图的类型通常是同质图，或者带有辅助信息的图。

1.3.5 生成式模型

1. 可以指定输入特征和类别标签的联合分布来定义生成式模型 generative model 。一个典型的例子是潜在迪利克雷分配 Latent Dirichlet Allocation: LDA，其中文档被解释为主题的分布，主题是单词的分布。

   有两种生成式模型用于 graph embedding ：

   • Embed Graph Into The Latent Semantic Space ：原理是节点被嵌入到潜在语义空间中，其中节点之间的距离解释了观察到的图结构。

     该方法直接将图嵌入到潜在空间，每个节点都表示为潜在空间中的一个向量。换句话讲，它将观察到的图视为从生成模型生成而来。例如在 LDA 中，文档被嵌入到 topic 空间中，单词相似的文档具有相似的 topic 向量。

   • Incorporate Latent Semantics for Graph Embedding：原理是图中距离较近、且具有相似语义的节点应该紧密嵌在一起。其中节点语义可以通过生成式模型从节点描述信息中获取。

     该方法使用潜在语义作为节点辅助信息从而进行 graph embedding。最终 embedding 不仅取决于图结构信息，还取决于节点的潜在语义信息。

   这两种方法的不同之处在于：第一种方法中 emebdding 空间就是潜在空间 latent space；第二种方法中，潜在空间用于融合节点的不同来源的信息，并帮助将一个图嵌入到另一个空间。

2. 总结：生成式模型可以用于node embedding、 edge embedding。由于该方法考虑了节点语义，因此输入图通常是异质图，或者带有辅助信息的图。

1.3.6 混合技术和其它

1. 有时在一项工作中结合了多种技术：

   • 《Cross view link predictionby learning noise-resilient representation consensus》 通过最小化 margin-based ranking loss 学习 edge-based embedding ，并通过矩阵分解学习 attribute-based embedding 。
   • 《Semantically smooth knowledge graph embedding》 优化了 margin-based ranking loss ，并将基于矩阵分解的损失作为正则化项。
   • 《Community-based question answering via asymmetric multifaceted ranking network learning》 使用 LSTM 来学习嵌入 cQA 中的句子，并使用 margin-based ranking loss 来融合好友关系。
   • 《Context-dependent knowledge graph embedding 》 采用 CBOW/SkipGram进行知识图谱实体嵌入，然后通过最小化 margin-based ranking loss 对 embedding 进行微调。
   • 《Text-enhanced representation learning for knowledge graph》 使用 word2vec 来嵌入文本上下文，使用 TransH 来嵌入实体/关系，从而在知识图谱嵌入中利用了丰富的上下文信息。
   • 《Collaborative knowledge base embedding for recommender systems》 利用知识库中的异质性信息来提高推荐性能。它使用 TransR 进行 network embedding ，并使用自编码器进行 textual embedding和 visual embedding 。
   • 最后，人们提出了生成式模型，从而将协同过滤与 items semantic representation 相结合。

2. 除了所介绍的五类技术外，还有其他方法：

   • 《Hierarchical graph embedding in vector space by graph pyramid》 提出了通过图与prototype graph 的距离来嵌入图的方法。
   • 《On the embeddability of random walk distances 》 首先使用 pairwise 最短路径距离来嵌入一些 landmark 节点。然后嵌入其他节点，使其与 landmark 节点的距离尽可能地接近真实的最短路径。
   • 《Cross view link predictionby learning noise-resilient representation consensus》 联合优化了基于边的损失（最大化观察一个节点的邻居的可能性）和基于属性的损失（学习 link-based representation 的线性投影）。
   • KR-EAR (《Knowledge representation learning with entities, attributes and relations》) 将知识图谱中的关系区分为 attribute-based 和 relation-based 。它构建了一个 relational triple encoder （TransE、TransR）来嵌入实体和关系之间的关联，以及一个 attributional triple encoder 来嵌入实体和属性之间的关联。
   • Struct2vec 通过 hierarchical metric 考虑了节点的结构身份 structral identify ，从而用于node embedding。
   • 《Fast network embedding enhancement via high order proximity approximation》 通过近似高阶邻近性矩阵提供了一种快速嵌入方法。

1.3.7 总结

1. 我们在下表给出所有五种 graph embedding 的优缺点。

   • 基于矩阵分解的 graph embedding 使用 global pairwise 相似度的统计信息来学习 embedding。

     由于某些任务依赖于独立的局部上下文窗口，因此它可以超越基于深度学习的 graph embedding 方法。但是，无论是邻接矩阵的构造还是矩阵的特征值分解，其时间代价、空间代价都很高。这使得矩阵分解的效率较低，并且无法扩展到大规模的图。

   • 基于深度学习的 grap emebdding 效果突出。我们认为深度学习适用于 graph embedding，因为它具有从复杂图结构中自动识别出有用representation的能力。例如：

     • 带随机游走的深度学习方法可以通过图上的采样路径自动探索邻域结构。
     • 不带随机游走的深度学习方法可在同质图中建模可变大小的子图结构，或者在异质图中建模各种类型节点之间丰富的交互。

     另一方面，基于深度学习的方法也有局限性：

     • 对于带随机游走的深度学习方法，它仅考虑路径内的局部邻域，因此忽略了全局结构信息。

       另外，由于无法在统一的框架中同时优化embedding 和路径采样，因此很难找到最佳的采样策略。

     • 对于不带随机游走的深度学习方法，计算代价通常很高。

     最后，传统的深度学习架构假设输入数据是 grid 结构从而充分利用 GPU ，但是图数据不具备 grid 结构，因此需要不同的解决方案来提高计算效率。

   • 基于边重建的graph embedding 方法可以基于观察到的边或者有序三元组从而优化目标函数。和前两类 graph embedding 相比，它的训练效率更高。

     但是这一系列方法是使用直接观测到的局部信息进行训练的，因此获得的 embedding 缺乏对全局图结构的了解。

   • 基于 graph kernel 的 graph embedding 将整个图转换为一个向量，从而促进 graph-level 的图分析任务，例如图分类。它比其它类型的技术更加高效，因此它只需要枚举图中出现的“原子”的子结构。

     但是，这种类似于 bag-of-word 的方法有两个局限：

     • 首先，子结构之间不是相互独立的。例如 size 为 k+1 的 graphlet 可以通过size 为 k 的 graphlet 通过添加一些新的节点和一些新的边得到。这意味着通过 graphlet 的 graph representation 存在冗余信息。
     • 其次，随着子结构 size 的增加，graph embedding 维度通常呈指数型增长，从而导致 embedding 的稀疏性问题。

   • 基于生成式模型的 graph embedding 可以自然地利用统一模型中不同来源的信息（如，图结构、节点属性）。直接将图嵌入到潜在的语义空间中，得到的 emebdding 可以用语义来解释。

     但是，假设观测数据满足某种分布通常很难证明。并且生成式方法需要大量的训练数据来估计模型。因此对于较小的图或者少量的图，它无法很好地工作。

   

1.4 应用

1. 节点相关应用：

   • 节点分类：通常先将每个节点嵌入为一个低维向量，然后通过在标记节点的 embedding 向量上应用分类器进行训练。

     另外，和上面的两阶段节点分类相比，一些工作设计了一个统一的框架来共同优化node embedding 和节点分类，从而学到每个节点的 classification-specific representation 。

   • 节点聚类：通常先将每个节点嵌入为一个低维向量，然后将传统的聚类算法应用于node embedding 。作为无监督算法，当节点标签不可用时可以使用聚类算法。

     现有大多数方法都使用 k-means 作为聚类算法。也有一些方法在一个目标中共同优化了聚类和node embedding，从而学到每个节点的 clustering-specific representation 。

   • 节点推荐/检索/排序：节点推荐任务是基于某些标准（如相似性），将 top-K 相似节点推荐给目标节点。

     在 knowledge graph embedding 中被广泛讨论的一个具体应用是entity ranking ：在三元组 $<h,r,t>$$<h,r,t>$ 中，给定 $r$$r$ 和 $t$$t$ 的情况下返回真实的 $h$$h$ 、或者给定 $r$$r$ 和 $h$$h$ 的情况下返回真实的 $t$$t$ 。

2. 边相关的应用：

   • 链接预测：graph embedding 旨在用低维的向量来表示图，但有趣的是，得到的 embedding 向量也可以反过来帮助推断图结构。

     实际上输入的图通常是残缺的。例如，在社交网络中实际上彼此认识的两个用户可能因为种种原因并没有添加为好友。在graph embedding 中，低维 embedding 向量预期会保留不同阶次、不同尺度的邻近度，因此这些embedding 向量编码了有关网络结构的丰富信息，并可以用于预测图中的缺失链接。

     基于 graph embedding的链接预测大多数应用于同质图，也有少量工作涉及异质图的链接预测。

   • 三元组分类 Triple Classification：三元组分类是知识图谱的特定应用，其目标是对未见过的三元组 $<h,r,t>$$<h,r,t>$ 进而判别：$h$$h$ 和 $t$$t$ 之间的关系是否是 $r$$r$ ？

3. 图相关应用：

   • 图分类：图分类是将类别标签分配给整个图。这不同于节点分类，节点分类是将类别标签分配给每个节点。当图作为基本的单元时，这一点很重要。如，在化合物分类任务中，每个图都是一个化合物。
   • 可视化：图可视化是在低维空间中生成图的可视化。通常，出于可视化的目的，所有节点都使用二维向量 embedding，然后在二维空间中使用不同的颜色绘制从而表示节点类别。图可视化生动地展示了属于同一个类别节点的 embedding 是否彼此靠近。

4. 其它应用：上面讨论的是一些通用的应用，这里是一些具体的应用：

   • 知识图谱相关：包括从大规模纯文本中提取 relational fact、从文本中提取医学实体、将自然语言文本与知识图谱中的实体联系起来，等等。
   • 多媒体网络相关：包括嵌入了 geo-tagged 的社交媒体的记录 <time, location, message> 从而在给定其中两个元素的情况下恢复缺失的第三个元素；使用 graph embedding来数据维度从而用于人脸识别；将图像映射到一个语义流形中从而促进 content-based 的图像检索。
   • 信息传播相关：包括通过嵌入 social interaction graph 来预测 propagation user 并识别领域专家。
   • 社交网络对齐：包括预测两个不同社交网络中的两个用户账户是否为同一用户所有。
   • 图像相关：一些工作嵌入了由图像构建的graph，然后将 emebdding 用于图像分类、图像聚类、图像分割、模式识别，等等。

1.5 未来方向

1. 这里我们总结了graph embedding 四个未来方向，包括计算效率、问题设置、技术、应用场景。

   • 计算效率computation efficiency：传统的深度学习模型（专为欧式结构的数据来设计）利用现代 GPU 来优化计算效率，通常假设输入数据为一维或二维网格形状。但是图不具备这种网格结构，因此需要针对 graph embedding 设计深度架构来提高模型效率。

   • 问题设置 problem setting：动态图是 graph embedding 的一种有前景的方向。图并不总是静态的，可以是动态演进的。一方面，图的结构可能随时间发生变化，如出现一些新节点、新的边，而有一些旧节点、旧的边消失；另一方面，图中节点的属性可能随时间发生变化。

     与静态图的嵌入不同，动态图的技术需要可扩展的（最好是增量的），以便有效地处理动态变化。这使得大多数现有的 graph embedding 方法都存在效率低的问题，不再适用。如何针对动态图设计有效的 graph embedding 方法，仍然是悬而未决的问题。

   • 技术 techniques：结构感知 structure-aware 对基于边重建的 graph embedding 非常重要。目前基于边重建的 graph embedding 方法仅依赖于一阶邻域，图的全局结构（如路径、树、子图模式）被忽略。

     从直觉上讲，一个子结构包含的信息要比单条边更丰富。因此，需要有一种有效的结构感知 graph embedding 优化框架以及子结构采样策略。

   • 应用：graph embedding 已应用于许多不同的应用中。它可以将不同数据源、不同平台、不同视角的数据映射到公共的空间，从而便于直接比较。如 content-based 图像检索、keyword-based 图像/视频检索等。

     使用 graph embedding 进行表示学习的优势在于：训练数据的graph 的流形被保留在 embedding 中，并可以进一步使得后续的应用受益。因此， graph embedding 可以使那些假定输入数据实例与某些关系（即通过某些link 来连接）相关的任务受益。探索从 graph embedding 中受益的应用场景是非常重要的，因为它从不同的角度为传统问题提供了有效的解决方案。

二、Graph Embedding Techniques, Applications, and Performance[2017]

1. 近年来，由于网络在现实世界中无处不在，图分析 graph analysis 已经引起了越来越多的关注。图分析任务可以大致抽象为以下四类：节点分类、链接预测、节点聚类、以及可视化：

   • 节点分类的目的是根据其他标记的节点和网络的拓扑结构来确定节点的标签。
   • 链接预测指的是预测缺失的链接或未来可能出现的链接。
   • 节点聚类是用来寻找类似节点的子集，并将它们分组。
   • 可视化有助于提供对网络结构的洞察力。

   在过去的几十年里，人们为上述任务提出了许多方法：

   • 对于节点分类，大致有两类方法：使用随机游走来传播标签的方，以及从节点中提取特征并对其应用分类器的方法。
   • 链接预测的方法包括：基于相似性的方法、最大似然模型、以及概率模型。
   • 聚类方法包括：基于属性的模型、以及直接最大化（或最小化）簇间（或簇内）距离的方法。

   论文 《Graph Embedding Techniques, Applications, and Performance: A Survey》 提供了一种分类方法，来分析现有的方法以及应用领域。

   通常图任务的模型要么在原始图的邻接矩阵上执行，要么在一个派生的向量空间上执行。近年来，基于向量空间的 graph representation方法能够保持图的属性，因此被广泛应用。获得这样的 embedding 对于图分析任务非常有用。可以将node embedding 作为模型的特征输入，这可以避免使用一个非常复杂的模型直接应用到图数据上。

   获得每个节点的 embedding 向量非常困难，并存在一些挑战：

   • 属性选择：节点的良好的 embedding 向量应该保持图结构信息。第一个挑战是：embedding 应该保留图的哪个属性？

     由于在图上存在多种距离度量和属性（如一阶邻近度、二阶邻近度），因此这种选择可能很困难，并且依赖于具体的任务。

   • 可扩展性：大多数真实网络都很大，并且包含数百万节点和边。embedding 算法应该是可扩展的，并能够处理大图。

   • embedding 维度：选择最佳的 embedding 维度可能很困难。例如，更高的维度可以提高边重建的准确性，但是具有更高的时间复杂度和空间复杂度。根据方法的不同，具体的最佳 embedding 维度也是 task-specific 的。如，在链接预测任务中，如果使用的模型仅捕获节点之间的局部连接，则较小的 embedding 维度可能导致更好的链接预测准确性。

   论文贡献：

   • 论文提出了一个 graph embedding 方法的分类法，并解释了它们的差异。作者定义了四个不同的任务，也就是 graph embedding技术的应用领域。作者说明了 graph embedding 的演变、所面临的挑战、以及未来可能的研究方向。
   • 论文对各种 graph embedding 模型进行了详细而系统的分析，并讨论了它们在各种任务上的表现。对于每一种方法，作者通过对一些常见的数据集和应用场景的综合比较评估，分析其保留的属性及其准确性。此外，作者对所评估的方法进行了超参数敏感性分析以测试它们的鲁棒性，并提供对最佳超参数的理解。
   • 为了促进 graph embedding 的进一步研究，论文最后介绍了GEM，这是作者开发的开源 Python 库，在一个统一的接口下提供了本综述中讨论的所有 graph embedding 方法的实现。就作者所知，这是第一篇综述 graph embedding 技术及其应用的论文。

2.1 算法

1. 给定图 $G=(V,E)$$G=(V,E)$ ，其中 $V=\{v_1,v_2,\cdots ,v_n\}$$V=\{v_1,v_2,\cdots,v_n\}$ 为节点集合， $E=\{e_{i,j}\}$$E=\{e_{i,j}\}$ 为边集合。

   邻接矩阵 $\mathbf{W}=\{W_{i,j}\}$$\mathbf W =\{W_{i,j}\}$ 包含每条边的非负权重，即 $W_{i,j}\ge 0$$W_{i,j}\ge 0$ 。如果 $v_i,v_j$$v_i,v_j$ 之间不存在边，则 $W_{i,j}=0$$W_{i,j} = 0$ 。对于无向图 $W_{i,j}=W_{j,i}$$W_{i,j} = W_{j,i}$ ，对于有向图则不一定成立。

2. 定义节点 $v_i,v_j$$v_i, v_j$ 之间的一阶邻近度 first-order proximity 为节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的相似性。

   我们认为：如果两个节点之间具有较大权重的连接，则它们更为相似。由于边 $e_{i,j}$$e_{i,j}$ 的权重为 $W_{i,j}$$W_{i,j}$ ，因此我们将节点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间的一阶邻近度为 $s_{i,j}=W_{i,j}$$s_{i,j}=W_{i,j}$ 。

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

3. 定义节点 $v_i,v_j$$v_i, v_j$ 之间的二阶邻近度 second-order proximity 为节点 $v_i$$v_i$ 的邻域和 $v_j$$v_j$ 的邻域之间的相似性。二阶邻近度表示节点邻域结构的相似性，如果两个节点的邻域越相似，则它们之间的二阶邻近度越大。如果我们用 cos 函数作为邻域相似性的度量，则二阶邻近性为：$\cos ({\overrightarrow{\mathbf{s}}}_i,{\overrightarrow{\mathbf{s}}}_j)$$\cos\left(\mathbf{\vec s}_i ,\mathbf{\vec s}_j \right)$ 。

   节点 $v_i,v_j$$v_i,v_j$ 之间的高阶邻近度 higher-order proximity 也可以类似地定义。例如，节点 $v_i,v_j$$v_i,v_j$ 之间的 $k$$k$ 阶邻近度定义为节点 $v_i$$v_i$ 的 $k-1$$k-1$ 阶邻域和 $v_j$$v_j$ 的 $k-1$$k-1$ 阶邻域之间的相似性。

   和 《A Comprehensive Survey of Graph Embedding[2017]》 类似，也可以采用递归定义：

   $$\begin{array}{c}{s}_{i,j}^{(k)}=\cos ({\overrightarrow{\mathbf{s}}}_i^{(k-1)},{\overrightarrow{\mathbf{s}}}_j^{(k-1)}),k\ge 2\\ {\overrightarrow{\mathbf{s}}}_i^{(1)}=[s_{i,1}^{(1)},s_{i,2}^{(1)},\cdots ,s_{i,|V|}^{(1)}]\end{array}$$

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

4. 给定一个图 $G=(V,E)$$G=(V,E)$ ，graph embedding 是一个映射 $f:v_i\to {\overrightarrow{\mathbf{y}}}_i\in {\mathbb{R}}^d$$f: v_i \rightarrow \mathbf{\vec y}_i\in \mathbb R^d$ ，其中 $d\ll |V|$$d\ll |V|$ 。在映射过程中， $f$$f$ 保留了 $G$$G$ 的某些属性（如一阶邻近度）。

   因此，embedding 将每个节点映射到低维特征向量，并尝试保留节点之间的连接信息。

5. graph embedding 技术的历史演进：

   • 在21世纪初，研究人员开发了 graph embedding 算法，作为降维技术的一部分。他们会根据邻居关系为 $n$$n$ 个 $D$$D$ 维的数据点构建一个相似性图similarity graph ，然后将图的节点嵌入到一个 $d$$d$ 维的向量空间中，其中 $d\le D$$d\le D$。embedding 的思想是：让相连的节点在向量空间中相互靠近。Laplacian Eigenmaps 和 Locally Linear Embedding: LLE 是基于这个原理的算法的例子。然而，可扩展性是这种方法的一个主要问题，其时间复杂度为 $O(|V{|}^2)$$O(|V|^2)$ 。

   • 自 2010 年以来，关于 graph embedding 的研究已经转向获得可扩展的 graph embedding 技术，这些技术利用了现实世界网络的稀疏性。例如：

     • Graph Factorization 使用邻接矩阵的近似分解化作为 embedding 。
     • LINE扩展了这种方法，并试图保留一阶邻近性和二阶邻近性。
     • HOPE 扩展了 LINE，试图通过使用广义的奇异值分解Singular Value Decomposition: SVD来分解相似性矩阵而不是邻接矩阵，从而保留高阶接近性。
     • SDNE 使用自编码器来嵌入图的节点并捕获高度非线性的依赖关系。

     新的可扩展方法的时间复杂度为 $O(|E|)$$O(|E|)$ 。

6. 我们将近年来提出的 graph embedding 技术分为三类：

   • 基于矩阵分解的方法 factorization-based 。
   • 基于随机游走的方法 random walk-based 。
   • 基于深度学习的方法 deep learning-based。

   这些类别代表性的方法以及简要介绍如下表所示。

   

2.1.1 基于分解的方法

1. 基于分解的方法以矩阵形式表示节点之间的连接，然后将该矩阵分解从而获得node embedding。用于表示连接的矩阵可以为节点邻接矩阵、图拉普拉斯矩阵、节点转移概率矩阵、Katz 相似度矩阵。

   Katz Index:KI 用于区分不同邻居节点的不同影响力，它给邻居节点赋予不同的权重：对于短路径赋予较大权重、对于长路径赋予较小的权重。

   给定节点 $v_i,v_j$$v_i,v_j$ 以及邻接矩阵 $\mathbf{W}$$\mathbf W$ ，则节点 $v_i,v_j$$v_i,v_j$ 之间长度为 $l$$l$ 的路径权重为 ${\left({\mathbf{W}}^l\right)}_{i,j}$$\left(\mathbf W^l\right)_{i,j}$ 。则有：

   $$\text{KI}(v_i,v_j)=\sum _{l=1}^{\mathrm{\infty }}{\beta }^l\times {\left({\mathbf{W}}^l\right)}_{i,j}$$

   其中 $1>\beta >0$$1\gt \beta\gt 0$ 为权重衰减因子。为保证数列的收敛性， $\beta$$\beta$ 必须小于邻接矩阵 $\mathbf{W}$$\mathbf W$ 最大特征值的倒数。

   令 KI 矩阵为 $\mathbf{K}$$\mathbf K$ ，则有：

   $$\mathbf{K}=\beta \mathbf{W}+{\beta }^2{\mathbf{W}}^2+\cdots ={(\mathbf{I}-\beta \mathbf{W})}^{-1}-\mathbf{I}$$

   由于存在矩阵求逆运算，因此总的算法复杂度为 $O(|V{|}^3)$$O(|V|^3)$ 。

   矩阵分解的方法因矩阵属性而异。如果获得的矩阵是半正定的（例如，图拉普拉斯矩阵），则可以使用特征值分解 eigenvalue decomposition。对于非结构化矩阵 unstructured matrices，可以使用梯度下降法在线性时间内获得 embedding 。

2. LLE：局部线性嵌入 Locally Linear Embedding:LLE 假设每个节点的 embedding 都是其邻居节点的 embedding 的线性组合。

   假设图 $G$$G$ 的邻接矩阵为 $\mathbf{W}$$\mathbf W$ ，第 $i$$i$ 行第 $j$$j$ 列为 $W_{i,j}$$W_{i,j}$ ，则节点 $v_i$$v_i$ 的 embedding ${\overrightarrow{\mathbf{y}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec y}_i\in \mathbb R^d$ 通过邻居node embedding 的线性组合近似为：

   $${\overrightarrow{\mathbf{y}}}_i\simeq \sum _j{W}_{i,j}{\overrightarrow{\mathbf{y}}}_j$$

   我们通过最小化近似误差来得到目标函数：

   $$\mathcal{L}(\mathbf{Y})=\sum _i{\Vert {\overrightarrow{\mathbf{y}}}_i-\sum _j{W}_{i,j}{\overrightarrow{\mathbf{y}}}_j\Vert }_2^2$$

   其中 $\mathbf{Y}\in {\mathbb{R}}^{n\times d}$$\mathbf Y\in \mathbb R^{n\times d}$ 为节点的 embedding 矩阵。

   可以看到当 $\mathbf{Y}=\mathbf{0}$$\mathbf Y = \mathbf 0$ 即全零矩阵时，上述目标函数最小。因此，为了消除这种平凡解我们增加约束条件：

   $$\frac{1}{n}{\mathbf{Y}}^{\mathrm{\top }}\mathbf{Y}=\mathbf{I}$$

   进一步地，为消除平移不变性，因为如果 ${\overrightarrow{\mathbf{y}}}_i$$\mathbf {\vec y}_i$ 为解，则 ${\overrightarrow{\mathbf{y}}}_i+a$$\mathbf{\vec y}_i + a$ 也是解，$a$$a$ 为任意常数。我们令 embedding 以零点为中心：

   $$\sum _i{\overrightarrow{\mathbf{y}}}_i=\overrightarrow{\mathbf{0}}$$

   因此得到最优化方程：

   $$\begin{array}{c}min\mathcal{L}(\mathbf{Y})=min\sum _i{\Vert {\overrightarrow{\mathbf{y}}}_i-\sum _j{W}_{i,j}{\overrightarrow{\mathbf{y}}}_j|\Vert }_2^2\\ s.t.\frac{1}{n}{\mathbf{Y}}^{\mathrm{\top }}\mathbf{Y}=\mathbf{I},\sum _i{\overrightarrow{\mathbf{y}}}_i=\overrightarrow{\mathbf{0}}\end{array}$$

   可以将上述最优化问题简化为一个特征值问题 eigenvalue problem ，最终的解为稀疏矩阵 $(\mathbf{I}-\mathbf{W}{)}^{\mathrm{\top }}(\mathbf{I}-\mathbf{W})$$(\mathbf I - \mathbf W)^\top(\mathbf I- \mathbf W)$ 的最小 $d+1$$d+1$ 个特征值 eigenvalue 对应的特征向量eigenvector，并剔除最小特征值对应的特征向量。

3. Laplacian Eigenmaps ：拉普拉斯特征图Laplacian Eigenmaps 旨在当 $W_{i,j}$$W_{i,j}$ 较高时两个节点的 embedding 距离较近。具体而言，其目标函数为：

   $$\mathcal{L}(\mathbf{Y})=\frac{1}{2}\sum _i\sum _j{W}_{i,j}{\Vert {\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j\Vert }_2^2=\text{tr}\left({\mathbf{Y}}^{\mathrm{\top }}\mathbf{L}\mathbf{Y}\right)$$

   其中 tr(.) 为矩阵的迹trace， $\mathbf{L}=\mathbf{D}-\mathbf{W}$$\mathbf L = \mathbf D - \mathbf W$ 为图拉普拉斯矩阵，$\mathbf{D}=\text{diag}(d_1,\cdots ,d_n),d_i=\sum _j{W}_{i,j}$$\mathbf D = \text{diag}(d_1,\cdots,d_n), d_i = \sum_{j}W_{i,j}$ 为图的度矩阵。

   可以看到当 $\mathbf{Y}=\mathbf{0}$$\mathbf Y = \mathbf 0$ 即全零矩阵时，上述目标函数最小。因此为了消除这种平凡解，我们增加约束条件 ${\mathbf{Y}}^{\mathrm{\top }}\mathbf{D}\mathbf{Y}=\mathbf{I}$$\mathbf Y^\top\mathbf D\mathbf Y = \mathbf I$ ，以及 $\sum _i{\overrightarrow{\mathbf{y}}}_i=\overrightarrow{\mathbf{0}}$$\sum_i\mathbf{\vec y}_i = \mathbf{\vec 0}$ 。即：

   $$\begin{array}{c}min\mathcal{L}(\mathbf{Y})=min\frac{1}{2}\sum _i\sum _j{W}_{i,j}{\Vert {\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j\Vert }_2^2=min\text{tr}\left({\mathbf{Y}}^{\mathrm{\top }}\mathbf{L}\mathbf{Y}\right)\\ s.t.{\mathbf{Y}}^{\mathrm{\top }}\mathbf{D}\mathbf{Y}=\mathbf{I},\sum _i{\overrightarrow{\mathbf{y}}}_i=\overrightarrow{\mathbf{0}}\end{array}$$

   上述最优化问题的解为归一化的图拉普拉斯矩阵 ${\mathbf{L}}_{\text{norm}}={\mathbf{D}}^{-1/2}\mathbf{L}{\mathbf{D}}^{-1/2}$$\mathbf L_{\text{norm}} = \mathbf D^{-1/2}\mathbf L\mathbf D^{-1/2}$ 的 $d$$d$ 个最小的特征值 eigenvalue对应的特征向量 eigenvector 。

4. Cauchy Graph Embedding：对于任意节点 $v_i,v_j,v_p,v_q$$v_i,v_j, v_p,v_q$ ，当 $W_{i,j}\ge W_{p,q}$$W_{i,j}\ge W_{p,q}$ 时有：

   $${\Vert {\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j\Vert }_2^2\le {\Vert {\overrightarrow{\mathbf{y}}}_p-{\overrightarrow{\mathbf{y}}}_q\Vert }_2^2$$

   则我们称该 embedding 保留了局部拓扑结构local topology 。即：对于任意一对节点 $(v_i,v_j)$$(v_i,v_j)$ ，它们的相似度越高（由连接权重 $W_{i,j}$$W_{i,j}$ 衡量），则它们嵌入得越紧密。

   在拉普拉斯特征图中，由于embedding 距离使用二次函数，因此：对于embedding 距离较大的不相似的节点，其距离的平方较大；对于 embedding 距离较小的相似节点，其距离平方较小。因此该目标函数更侧重于找到 ”不相似性性“，而不是”相似性“ 。即：

   • 如果将不相似节点映射到相似的 embedding，则惩罚较小。
   • 如果将相似节点映射到不相似的 embedding，则惩罚较大。

   因此拉普拉斯特征图倾向于将节点都映射到相似的 embedding ，这使得emebdding 无法保留图的局部拓扑结构。

   Cauchy Graph Embedding 通过将 $||{\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j|{|}_2^2$$||\mathbf{\vec y}_i - \mathbf{\vec y}_j||_2^2$ 替换为 $\frac{1}{||{\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j|{|}_2^2+{\sigma }^2}$$\frac{1}{||\mathbf{\vec y}_i - \mathbf{\vec y}_j||_2^2+\sigma^2}$ 来解决该问题，其目标函数为：

   $$\begin{array}{c}max\mathcal{L}(\mathbf{Y})=max\sum _i\sum _j\frac{W_{i,j}}{||{\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j|{|}_2^2+{\sigma }^2}\\ s.t.{\mathbf{Y}}^{\mathrm{\top }}\mathbf{D}\mathbf{Y}=\mathbf{I},\sum _i{\overrightarrow{\mathbf{y}}}_i=\overrightarrow{\mathbf{0}}\end{array}$$

   注意这里为 max 而不是 min 。

   这一变化得核心在于：对于较大的 $W_{i,j}$$W_{i,j}$ ，模型鼓励较小的距离 $||{\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j|{|}_2^2$$||\mathbf{\vec y}_i - \mathbf{\vec y}_j||_2^2$ 。因此新的目标函数将重点放在相似的节点上，而不是不相似的节点上。

   但是对于较小的 $W_{i,j}$$W_{i,j}$，模型也鼓励较小的距离 $||{\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j|{|}_2^2$$||\mathbf{\vec y}_i - \mathbf{\vec y}_j||_2^2$ 。所以无论如何，模型都鼓励 $||{\overrightarrow{\mathbf{y}}}_i-{\overrightarrow{\mathbf{y}}}_j|{|}_2^2\to 0$$||\mathbf{\vec y}_i - \mathbf{\vec y}_j||_2^2\rightarrow 0$ 。

5. SPE：结构保持嵌入 Structure Preserving Embedding:SPE 是扩展拉普拉斯特征图的另一种方式。SPE 目标是准确地重建输入图。embedding 存储为一个半正定的核矩阵 $\mathbf{K}$$\mathbf K$ ，然后定义一个连通算法 connectivity algorithm $\mathcal{G}$$\mathcal G$ 来从 $\mathbf{K}$$\mathbf K$ 中重建图。

   我们求解最优化方程：

   $$\underset{\mathbf{K}}{max}\text{tr}(\mathbf{K}\mathbf{W})$$

   从而试图重建 rank-1 的谱嵌入 spectral embedding 。

   连通算法 $\mathcal{G}$$\mathcal G$ 的选择产生了对目标函数的约束。如，如果连通方案是将节点和它半径 $ϵ$$\epsilon$ 内的邻居相连，则约束条件为：

   $$(K_{i,i}+K_{j,j}-2K_{i,j})(W_{i.j}-1/2)\le ϵ(W_{i,j}-1/2)$$

   此时求解的kernel $\mathbf{K}$$\mathbf K$ 可以完美重建原始图。

   为了处理图中的噪音，可以添加一个松弛变量 $\xi$$\xi$ ，此时优化目标为：

   $$\begin{array}{c}\underset{\mathbf{K}}{max}\text{tr}(\mathbf{K}\mathbf{W})-C\xi \\ s.t.(K_{i,i}+K_{j,j}-2K_{i,j})(W_{i.j}-1/2)\le ϵ(W_{i,j}-1/2)-\xi \end{array}$$

   其中 $C$$C$ 控制松弛度 slackness 。

6. Graph Factorization：图分解Graph Factorization:GF 算法是第一个可以在 $O(|E|)$$O(|E|)$ 时间复杂度内获得graph embedding 的算法。为了获得 embedding，GF 通过最小化以下目标函数来分解邻接矩阵：

   $$\mathcal{L}(\mathbf{Y},\lambda )=\frac{1}{2}\sum _{(i,j)\in E}{(W_{i,j}-{\overrightarrow{\mathbf{y}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)}^2+\frac{\lambda }{2}\sum _i||{\overrightarrow{\mathbf{y}}}_i|{|}_2^2$$

   其中 $\lambda$$\lambda$ 为正则化系数。

   注意：求和是在所有观测到的边上，而不是所有的节点pair 对上。

   GF 是一种可扩展的、近似的求解方案。由于邻接矩阵通常不是半正定的，因此即使 embedding 的维度选择为 $|V|$$|V|$ ，损失函数的最小值也大于零。

7. GraRep：GrapRep 定义节点的转移概率矩阵为 $\mathbf{T}={\mathbf{D}}^{-1}\mathbf{W}$$\mathbf T = \mathbf D^{-1} \mathbf W$ ，其中 $k$$k$ 阶转移概率矩阵为 ${\mathbf{T}}^k$$\mathbf T^k$ 。然后定义矩阵 ${\mathbf{X}}^k$$\mathbf X^k$ 为：

   $$X_{i,j}^k=max(\log \left(\frac{T_{i,j}^k}{\sum _{i^{\prime }}{T}_{i^{\prime },j}^k}\right)-\log \left(\frac{\lambda }{|V|}\right),0)$$

   其中 $\lambda$$\lambda$ 为负采样的负样本数量。

   最终执行矩阵分解：

   $${\mathbf{Y}}^k{\mathbf{C}}^k={\mathbf{X}}^k$$

   其中 ${\mathbf{Y}}^k$$\mathbf Y^k$ 为节点的 $k$$k$ 阶 embedding， ${\mathbf{C}}^k$$\mathbf C^k$ 为节点的 $k$$k$ 阶上下文 embedding 。

   最终拼接节点所有阶的 embedding 得到node embedding 。

   GrapRep 的缺陷在于其可扩展性，因为 ${\mathbf{T}}^k$$\mathbf T^k$ 有 $O(|V{|}^2)$$O(|V|^2)$ 非个零项。

8. HOPE ：HOPE 通过最小化 $||\mathbf{S}-\mathbf{Y}\mathbf{C}|{|}_F^2$$||\mathbf S - \mathbf Y\mathbf C||_F^2$ 来保留高阶邻近度，其中 $\mathbf{Y}$$\mathbf Y$ 为node embedding 矩阵，$\mathbf{C}$$\mathbf C$ 为coordinate 矩阵，$\mathbf{S}$$\mathbf S$ 为高阶邻近度矩阵。

   如果将 $\mathbf{Y}$$\mathbf Y$ 视为embedding 空间中的一组基向量，则 $\mathbf{C}$$\mathbf C$ 为 embedding 空间的坐标，$\mathbf{Y}\mathbf{C}$$\mathbf Y\mathbf C$ 来近似高阶邻近度。

   作者尝试了不同的相似性度量，包括 Katz Index, Rooted Page Rank, Common Neighbors, Adamic-Adar 。例如当选择 Katz Index 时，高阶邻近度矩阵为：

   $$\begin{array}{c}\mathbf{S}={\mathbf{M}}_a^{-1}{\mathbf{M}}_b\\ {\mathbf{M}}_a=(\mathbf{I}-\beta \mathbf{W}),{\mathbf{M}}_b=\beta \mathbf{W}\end{array}$$

   其中 $\beta$$\beta$ 为衰减系数。因此 ${\mathbf{M}}_a,{\mathbf{M}}_b$$\mathbf M_a, \mathbf M_b$ 都是稀疏的，这使得 HOPE 可以使用广义奇异值分解可以有效获得node embedding 。

9. 其它方法：为了对高维数据降维，这里其它一些方法能够执行 graph embedding，包括：主成分分析Principal Component Analysis:PCA、线性判别分析 Linear Discrimant Analysis:LDA、IsoMap、多尺度缩放Multidimesional Scaling:MDS、局部特性保持Locality Preserving Properties:LPP、核特征图Kernel Eigenmaps。《Non-negative graph embedding》 提出了一个通用框架用于为这些算法产生非负的 graph embedding。

   最近的一些技术聚焦在联合学习网络结构和节点属性信息上：

   • Augmented Relation Embedding: ARE 用基于内容的图像特征来增强网络，并修改graph-Laplacian 矩阵来捕获这些信息。
   • Text-associated DeepWalk: TADW 对节点的相似度矩阵执行分解，同时用到了文本特征矩阵。
   • Heterogeneous Network Embedding: HNE 学习网络每个模态的表示，然后使用线性变换将它们映射到同一个公共空间中。