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)}$$

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