Question

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 学习网络每个模态的表示，然后使用线性变换将它们映射到同一个公共空间中。

2.1.2 基于随机游走的方法

1. 随机游走已被用于近似求解图中的很多属性，包括节点中心性 centrality、节点相似性 similarity 。

   当只能观察到图的一部分，或者图太大而无法整体计算时，随机游走的方法特别有用。人们已经提出一些使用随机游走的方法来获得 node representation 。

2. DeepWalk：DeepWalk 通过最大化随机游走过程中节点$v_i$$ v_i $ 为中心的窗口为$k$$ k $ 内节点的概率，从而保持节点之间的高阶邻近度。即：$max\log P(v_{i-k},\cdots ,v_{i-1},v_{i+1},\cdots ,v_{i+k}\mid {\overrightarrow{\mathbf{y}}}_i)$$ \max \log P(v_{i-k},\cdots,v_{i-1},v_{i+1},\cdots,v_{i+k}\mid \mathbf{\vec y}_i) $ ，其中$k$$ k $ 为上下文窗口大小。

   此外，可以通过基于内积的解码器来从 node embedding 中重建边。

3. node2vec：类似于 Deepwalk，node2vec 通过最大化给定节点在随机游走序列中后续节点出现的概率，从而保留节点之间的高阶邻近度。

   和 Deepwalk 区别在于：node2vec 采用了有偏的随机游走，可以在广度优先搜索BFS 和深度优先搜索 DFS 之间平衡。因此， node2vec 可以产生比 DeepWalk 更高质量的 embedding 。选择正确的 balance 能够保留社区结构community structure 、或者保留节点的结构等价性 structural equivalence 。

4. Hierarchical Representation Learning for Network: HARP：Deepwalk 和 node2vec 随机初始化node embedding 来训练模型，由于它们的目标函数是非凸的，因此这种随机初始化可能卡在局部最优点。Hierarchical Representation Learning for Networks:HARP 引入了一种策略，可以通过更好的权重初始化策略来改进方法并避免局部最优。

   为此，HARP 构建了一种层次结构 hierarchy，每一层都是通过将前一层的节点聚合从而对图进行粗化 coarsening。然后，HARP 生成最粗粒度的图的 embedding，并将该 embedding 初始化更细粒度的图的 embedding。

   就这样一层一层地训练和初始化来传播这些不同层的 embedding，直到获得初始图的 embedding。因此，HARP 可以和基于随机游走的方法结合使用，从而获得更好的 embedding 。

5. Walklets：DeepWalk 和 node2vec 通过随机游走来隐式地保留节点之间的高阶邻近度。由于随机性，节点之间的距离在不同随机游走序列中可能不同。而基于分解的方法通过目标函数从而显式保留节点之间的距离。

   Walklets 将显式建模的思想和随机游走思想相结合，该模型通过跳过随机游走序列的$k$$ k $ 个节点来修改 DeepWalk 中的随机游走策略。

6. 其它方法：也有上述方法的几种变体。GenVector, Discriminative Deep Random Walk:DDRW, Tri-party Deep Network Representation:TriDNR 通过联合学习网络结构和节点属性来扩展了随机游走方法。

2.1.3 基于深度学习的方法

1. 越来越多的深度学习方法应用于图分析。由于深度自编码器能够对数据中的非线性结构进行建模，因此被广泛应用于降维。最近 SDNE, DNGR 利用深度自编码器这种能力来生成 embedding 从而捕获图的非线性。

2. Structural Deep Network Embedding: SDNE：SDNE 提出使用深度自编码器来保留网络的一阶邻近度和二阶邻近度，它通过共同优化两个邻近度来实现这一目标。

   SDNE 使用高度非线性的函数来获取 embedding，模型分为两个部分：

   • 无监督部分：该部分由一个自编码器组成，目标是为节点找到重构误差最小的 embedding。
   • 监督部分：该部分基于拉普拉斯特征图，利用一阶邻近度（即链接信息）作为监督信息来约束节点的 embedding，使得相似的节点在 embedding 空间中更紧密。

3. Deep Neural Networks for Learning Graph Representations:DNGR：DNGR 结合了随机游走和深度自编码器。该模型由三部分组成：随机游走、positive pointwise mutual information :PPMI 矩阵、堆叠式的降噪自编码器。

   • 输入图通过随机游走模型生成概率共现矩阵，类似于 HOPE 中的相似矩阵。
   • 然后将概率共现矩阵转换为 PPMI 矩阵。
   • 最后将 PPMI 矩阵输入到堆叠的降噪自编码器中获得 embedding 。

   输入的 PPMI 矩阵可以确保自编码器模型可以捕获更高阶的邻近度。此外，使用堆叠式的降噪自编码器有助于在图中存在噪声的情况下增强模型的鲁棒性，并有助于捕获具体任务所需的底层结构，这些任务包括链接预测、节点分类等。

4. Graph Convolutional Networks:GCN：上述讨论的基于深度神经网络的方法（SDNE,DNGR 等）将每个节点的全局邻域（DNGR 中 PPMI 的一行、SDNE 中邻接矩阵的一行）作为输入。对于大型稀疏图，这可能计算代价太大。图卷积神经网络GCN 通过在图上定义卷积算子来解决该问题。

   GCN 迭代式地聚合节点邻域 embedding，并使用邻域聚合后的 emebdding 和节点前一轮 embedding 来更新节点这一轮的 embedding。由于 GCN 仅聚合节点的局部邻域，因此可扩展性更强。经过多次迭代之后，节点学到的 embedding 能够刻画全局邻域。

   可以将卷积滤波器大致分为空间滤波器 spatial filter、谱域滤波器 spectral filter。空间滤波器直接作用于原始图和邻接矩阵，谱域滤波器作用于图的拉普拉斯矩阵的谱域。

5. Variational Graph Auto-Encoders:VGAE：图的变分自编码器使用 GCN 作为编码器、使用向量内积作为解码器。输入为图的邻接矩阵，并依赖 GCN 来学习节点之间的高阶邻近度。实验表明，和非概率non-probabilistic 的自编码器相比，使用变分自编码器可以提升性能。

2.1.4 其它方法

1. LINE：LINE 显式地定义了两个目标函数，分别用于保持一阶邻近度和二阶邻近度。

   • 一阶邻近度目标函数类似于因子分解 Graph Factorization:GF ，因为它们都旨在保持邻接矩阵和成对embedding 内积产生的矩阵的之间差异足够小。区别在于 GF 通过直接最小化二者之间的差异来实现，而 LINE 通过最小化理论联合概率分布和经验联合概率分布的KL 距离来实现。

     LINE 为每对节点定义了两个联合概率分布，其中理论联合概率分布采用 embedding 定义为：

     $$p_1(v_1,v_j)=\frac{1}{1+\exp (-{\overrightarrow{\mathbf{y}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j)}$$

     经验联合概率分布使用邻接矩阵定义为：

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

     因此一阶邻近度目标函数为：

     $${\mathcal{L}}_1=-\sum _{(i,j)\in E}{W}_{i,j}\log p_1(v_i,v_j)$$

   • 类似地，LINE 定义了二阶邻近度目标函数：

     $$\begin{array}{c}{p}_2(v_j\mid v_i)=\frac{\exp ({\overrightarrow{\mathbf{y}}}_j\cdot {\overrightarrow{\mathbf{y}}}_i)}{\sum _{j^{\prime }}\exp ({\overrightarrow{\mathbf{y}}}_{j^{\prime }}\cdot {\overrightarrow{\mathbf{y}}}_i)}\\ {\hat{p}}_2(v_j\mid v_i)=\frac{W_{i,j}}{d_i}\\ {\mathcal{L}}_2=-\sum _{(i,j)\in E}{W}_{i,j}\log p_2(v_j\mid v_i)\end{array}$$

   .

2.1.5 讨论

1. 我们可以将 embeddign 解释为描述图数据的 representation，因此它可以深入了解图的属性。

   我们以下图为例，考虑一个全连接的二部图$G_1$$ G_1 $ ：

   • 试图保持相连节点的 embedding 距离紧凑的 embedding 算法（ Community Preserving Embedding:CPE ）无法捕获图结构，如下图 (b) 所示。
   • 试图嵌入结构相等的 structurally-equivalent 节点的 embedding 距离紧凑的 embedding 算法（Structural-equivalence Preserving Embedding:SPE）效果很好，如下图 (c) 所示。

   类似地，考虑将两个星形结构通过一个 hub 节点相连的图$G_2$$ G_2 $ ，节点 1,3 是结构等价的，因此在下图 (f) 中它们的 embedding 相距很近、在下图 (e) 中它们相距很远。

   因此，可以根据 embedding 算法解释图属性的能力将这些算法分类：

   • 基于因子分解的方法无法学到任何可解释性，如解释网络的连接性connectivity。另外，除非显式地在目标函数中包含结构对等性structural equivalence，否则基于因子分解的方法也无法学习结构对等性。
   • 基于随机游走的方法中，可以通过修改随机游走参数在一定程度上控制 embedding 方法学到的连接性和结构性的 mixture 。
   • 在基于深度学习的方法中，提供足够的参数则它们可以学到连接性和结构性的 mixture 。例如，下图 (c) 中给出了 SDNE 学到的针对完全二部图 complete bipartite graph 的 node embedding 。

   

2.2 应用

1. 作为图的 representation，embedding 可以应用于各种下游任务，包括：网络压缩 network compression、可视化 visualization、聚类 clustering、链接预测 link prediction、节点分类 node classification。

2. 网络压缩：给定图$G$$ G $ ，网络压缩的目标是得到更少边的压缩图$G^{\ast }$$ G^* $ ，从而使得图的存储更有效、图的分析更快。多年来，许多研究人员使用 aggregation based 的方法来压缩图。这方面工作的主要思路是利用图的链接结构link structure来分组节点和边。《Graph summarization with bounded error》 利用信息论中的 Minimum Description Length: MDL 将图 summarize 为一个 graph summary 和 edge correction 。

   类似于这些 representation，graph embedding 也可以解释为图的 summarization 。《Structural deep network embedding》 和 《Asymmetric transitivity preserving graph embedding》通过从 embedding 中重建原始图并评估重建误差来明确地测试这一假设。他们表明，每个节点的低维 representation （在100 的数量级）有助于图的重建。

3. 可视化：由于 embedding 是图在向量空间的表示，因此可以使用降维技术，如主成分分析 PCA、t-SNE 等技术来对图进行可视化。如 DeepWalk, LINE, SDNE 的原始论文中都展示了 node embedding 的可视化。

4. 聚类：聚类分为两类，即基于结构的聚类、基于属性的聚类。

   • 基于结构的聚类：它又分为两类，即基于社区community-based的聚类、基于结构等效structurally equivalent based的聚类。

     • 基于社区的聚类旨在找到稠密的子图，其中子图内部具有大量的簇内边 intra-cluster edge 、子图之间具有少量的簇间边 inter-cluster edge 。
     • 基于结构等效的聚类相反，其目标是识别具有相似角色的节点（如 hub 节点、异常点）。

   • 基于属性的聚类：基于属性的聚类除了观测到的链接之外，还利用节点属性来聚类。

   《A spectral clustering approach to finding communities in graphs》 在 embedding 上使用 k-means 对节点进行聚类，并将在 Wordnet 和 NCAA 数据集上获得的聚类可视化，验证了所获得的聚类有直观的解释。

5. 链接预测：网络是根据观测到的实体之间的交互而构建的，这些交互可能是不完整 incomplete 的或者不准确 inaccurate 的。链接预测的目标是识别虚假的交互并预测缺失的交互。人们综述了链接预测领域的最新进展，并将算法分为：基于相似性（局部相似性和全局相似性）的方法、基于最大似然的方法、概率性的方法。

   embedding 可以显式或隐式地捕获网络的固有动态 inherent dynamics，从而可以执行链接预测。实验表明：通过使用 embedding 执行链接预测要比基于传统相似度的链接预测方法更准确。

6. 节点分类：通常由于各种原因，在网络中只有部分节点被标记，大部分节点的标记都是未知的。节点分类任务是通过网络结构和已标记节点来预测这些缺失的标记。

   节点分类方法大概分为两类，即基于特征提取的方法和基于随机游走的方法：

   • 基于特征提取的方法根据节点邻域和局部网络统计信息生成节点的特征，然后使用逻辑回归或朴素贝叶斯等分类器来预测标签。
   • 基于随机游走的方法通过随机游走来传播标签。

   embedding 可以解释为基于网络结构自动抽取的特征，因此属于第一类。实验表明：通过使用 embedding 的节点分类可以更准确地预测缺失的标签。

2.3 实验

1. 实验配置：32 core 2.6 GHz 的 CPU、128 GB RAM、Nvidia Tesla K40C 的单机，Ubuntu 14.04.4 LTS 操作系统。

2. 数据集：我们使用一个人工合成的数据集SYN-SBM 以及 6 个真实数据集，这些数据集的统计信息见下表（No. of labels 表示标签类别数） 。

   • SYB-SNM ：使用 Stochastic Block Model 方法人工创建的图，其中包括 1024 个节点、3 个社区。我们设置 in-block 概率为 0.1 以及 cross-block 概率为 0.01 。由于我们知道这个图中的社区结构 community structure ，我们用它来可视化通过各种方法学到的 emebdding 。
   • KARATE：Zachary 的 karate network 是一个著名的大学空手道俱乐部的社交网络。它在社交网络分析中被广泛研究。
   • BLOGCATALOG：这是一个由BlogCatalog 网站上博主的社交关系组成的网络。标签代表了博主的兴趣，这是通过博主提供的 meta data 推断出的。
   • YOUTUBE：这是一个 Youtube 用户的社交网络。标签代表了喜欢的视频类型。
   • HEP-TH：原始数据集包含 1993 年1月至2003年4 月期间的High Energy Physics Theory 的论文摘要。我们为这一时期发表的论文建立了一个合作网络 collaboration network 。
   • ASTRO-PH：这是一个由 1993 年1月至2003年4月期间提交到arXiv 的论文的作者组成的合作网络。
   • PPI：这是一个人类蛋白质之间的生物交互网络 biological interaction network 。

   

3. 评估指标：

   • 对于图重构和链接预测任务，我们使用 Precision at K:Pr@K 、Mean Average Precision:MAP 为评估指标。

     • Pr@K 表示对于节点$v_i$$ v_i $ ，结果的 top K 节点中和节点$v_i$$ v_i $ 真正存在连接的节点的比例，即：$\frac{\text{num of ground-truth in top-K}}{K}$$ \frac{\text{num of ground-truth in top-K}}{K} $ 。
     • AP@K 给出节点$v_i$$ v_i $ 在所有$k=1,2,3,\cdots ,K$$ k=1,2,3,\cdots,K $ 上的 Pr@k 均值，即：$\frac{1}{K}\sum _{k=1}^K\text{Pr@k}$$ \frac{1}{K}\sum_{k=1}^K\text{Pr@k} $ 。
     • MAP@K 进一步评估了所有节点的 Pr@k 值。

   • 对于节点分类任务，我们使用 micro-F1 和 macro-F1 指标。

2.3.1 Graph Reconstruction

1. 我们使用 graph embedding 重建节点的邻近度，然后根据节点邻近度对节点进行排序，并计算 top K 个预测中实际链接的占比作为重构精度 reconstruction precision 。由于对所有节点 pair 对计算的代价很大 （复杂度为$O(|V{|}^2)$$ O(|V|^2) $ ），因此我们随机采样 1024 个节点进行评估。为缓解采样随机性对评估结果的影响，我们随机采样并评估五次，并上报评估结果的均值和方差。

   为获得每种 embedding 方法的最佳超参数，我们进行超参数搜索并评估每种超参数的平均 MAP （评估时采样五次）。最后我们使用最佳超参数来重新训练模型并报告5 次采样的平均结果。

   下图给出了不同方法 128 维 embedding 获得的重构精度。结论：

   • 虽然embedding 性能与数据集有关，但是总体而言保留高阶邻近度的 embedding 方法要更好。

   • 拉普拉斯特征图LE 在 SBM 上的出色表现归因于数据集中缺乏高阶结构。

   • SDNE 在所有数据集上均表现良好，这归因于它从网络中学习复杂结构的能力。

     虽然 SDNE 效果好，但是其计算复杂度为$O(|V|\times |E|)$$ O(|V|\times |E|) $ ，这对于大型图是不现实的。

   • node2vec 学到的 embedding 具有较低的重构精度，这可能是由于高度非线性的降维导致了非线性的流形。

     理论上 node2vec 的高度非线性会导致更好的表达能力，这里 node2vec 结果交叉表明出现了严重的过拟合。

   • HOPE 学习线性的 embedding 但是保留了高阶邻近度，它可以很好地重建图，无需任何额外参数。

   

2. 进一步地，我们考察 embedding 维度对于重建误差的影响。结论：

   • 除了少数几个例外，随着embedding 维度的增加，MAP 值也增加。这是很直观地，因为更高的 embedding 维度能存储更多信息。
   • SDNE 可以将图以很高的精度嵌入到 16 维向量空间中，尽管需要解码器及其参数来获得这种精度。

   

2.3.2 Visualization

1. 由于 embedding 是图中节点的低维向量表示，因此我们可以利用 embedding 来可视化节点从而了解网络拓扑结构。由于不同 embedding 方法保留了网络中的不同结构，因此它们的能力以及对节点可视化的解释也有所不同。

   例如，设置广度优先BFS 超参数的 node2vec 学到的 embedding 倾向于将结构等效的节点聚集在一起；直接保留节点之间 k-hop 距离的方法（GF,LE,LLE 的$k=1$$ k=1 $ ， HOPE,SDNE 的$k>1$$ k\gt 1 $ ）将相邻节点聚集在一起。

   我们对 SBM, Karate 数据集使用不同方法生成 128 维的节点embedding，并通过t-SNE 将这些 embedding 可视化到 2D 空间。

   • SBM 数据集的可视化结果如下图所示。由于我们已知底层社区结构，因此我们使用社区标签为节点着色，不同颜色代表不同社区。

     结论：尽管数据集结构良好，所有 embedding 都一定程度上捕获了社区结构，但是由于 HOPE,SDNE 保留了高阶邻近性，因此相比于 LE,GF,LLE ，HOPE,SDNE 可视化的不同社区的间隔更清晰。

     

   • Karate 可视化结果如下图所示。结论：

     • LLE,LE 试图保留图的社区结构，并将较高 intra-cluster 边的节点聚类在一起。

     • GF 将社区结构紧密地嵌在一起，并使社区内节点远离其它节点。

     • 在 HOPE 中，我们观察到编号为 16,21 的节点，它们在原始图的 Katz 相似度非常低（0.0006），并在 embedding 空间中相距最远。

     • node2vec,SDNE 同时保留了节点社区结构和节点结构角色。

       • 节点 32,33 是 degree 很高的 hub 节点，并且是它们各自社区的中心节点。它们被嵌入在一起，并远离其它低 degree 的节点，并且更靠近各自社区的节点。
       • 节点 0 充当社区之间的 bridge ，因此SDNE 将节点 0 嵌入到远离其它节点。注意，与其它方法不同，这并不意味着节点 0 和其它节点断开连接，而是 SDNE 将节点 0 标识为独有的节点类型。

       虽然尚未研究过深度自编码器识别网络中重要节点的能力，但是鉴于这一发现我们认为这一方向是有希望的。

     

2.3.3 Link Prediction

1. graph embedding 另一个重要应用是预测图中未观测的连接。一个好的 network representation 应该能够很好地捕获图的固有结构，从而预测可能的、但是未观测的链接。

   为测试链接预测任务中不同 embedding 方法的性能，对于每个数据集我们随机隐藏 20% 的边，并利用剩余 80% 边来学习 embedding。然后根据学到的 embedding 来预测训练数据中未观测到的、最有可能的边。

   和图重构任务一样，我们随机采样 1024 个节点的随机子图，并针对子图中的隐藏边来预测边是否存在。为缓解采样随机性对评估结果的影响，我们随机采样并评估五次，并上报评估结果的均值和方差。

   直接在原始的图上进行评估需要评估$O(|V|\times |V|)$$ O(|V|\times |V|) $ 的 node pair，这对于大一点的图而言计算量太大。

   我们对每个emebdding 方法执行超参数搜索，并使用最佳超参数重新在 80%:20% 拆分得到的训练集上重新训练模型。

   下图给出了不同方法的 128 维embedding 的效果。结论：

   • 不同方法的性能和数据集高度相关。
   • node2vec 在 BlogCatalog 数据集上表现良好，但是在其它数据集上表现不佳（垫底）。
   • HOPE 在所有数据集上均表现良好，这意味着保留高阶邻近性有利于预测未观测到的链接。
   • SDNE 优于所有其它方法，但是在 PPI 数据集上除外。在 PPI 数据集上，随着 embedding 尺寸增加到 8 以上，SDNE 性能急剧下降。

   

2. 进一步地，我们考察 embedding 维度对于链接预测性能的影响。结论：

   • 在 PPI 数据集上，随着 embedding 尺寸增加到 8 以上，SDNE 性能急剧下降。

   • 在 PPI, BlogCatalog 数据集中，与图重构任务不同，随着 embedding 维度的增加链接预测性能不会得到改善。这可能是因为具有更多参数的模型在观测到的链接上过拟合，并且无法预测到未观测的链接。

   • 即使在相同数据集上，方法性能也取决于 embedding 维度。例如：

     • 在 PPI 数据集上，HOPE 在高维度 embedding 上的效果超越了其它方法。
     • 在所有数据集上，SNDE 在低维度 embedding 上的效果超越了其它方法。

     我们最终要评估的是在各模型的最佳 embedding 上，每个模型的效果。

   

2.3.4 Node Classification

1. 良好的 graph embedding 可以捕获网络结构，这对于节点分类很有用。通过使用生成的 embedding 作为特征对节点进行分类，我们比较了不同 embedding 方法的有效性。其中分类算法为 LIBLINEAR 库提供的 one-vs-one 逻辑回归模型。

   对于每个数据集，在分类期间我们随机抽取 10% ~ 90% 的标记节点作为训练集，剩余标记节点作为测试集。我们随机执行5 次拆分并报告测试集上评估结果的均值。

   下图给出了节点分类实验的结果。结论：

   • node2vec 在大多数节点分类任务上超越了其它方法。如前所述，node2vec 保留了节点之间的同质性 homophily，以及结构对等性structural equivalence 。这表明这在节点分类中可能很有用。

     例如在 BlogCatalog 中，用户之间可能具有相似的兴趣，但是网络是通过社交关系而不是兴趣关系而建立的。

   • 在 SBM 数据集中，其它方法性能超越了 node2vec。这是因为SBM 数据集的标签反映了社区，而节点之间没有结构上的对等性。

   

2. 进一步地，我们考察 embedding 维度对于节点分类性能的影响。其中训练集、测试集拆分比例为 50%:50% 。结论：

   • 和链接预测任务一样，节点分类任务性能在某些大小的维度之后达到饱和或者下降。这可能是模型对于训练数据过拟合。
   • 由于 SBM 是非常结构化的社区，因此即使是 8 维的 embedding 也可以达到很好的效果。
   • 在 PPI,BlogCatalog 数据集，node2vec 需要 128 维的 embedding 才能达到最佳性能。

   

2.3.5 参数敏感性

1. 这里我们要解决三个问题：

   • embedding 方法对于超参数鲁棒性如何？
   • 最佳超参数是否取决于 embedding 被使用的下游任务？
   • 超参数的性能差异对数据集提供了什么洞察？

   我们通过分析每个 embedding 方法上不同超参数的性能来回答这些问题。我们评估了 SBM, PPI, Hep-th 数据集。由于图拉普拉斯没有超参数，因此不在我们分析范围之内。

2. Graph Factorization:GF：GF 模型的目标函数包含了权重正则化项，该项带有一个超参数：正则化系数。正则化系数可以控制 embedding 的泛化能力：

   • 较低的正则化系数有助于更好地重建图，但是可能会对观察到的图过拟合，从而导致较差的预测性能。
   • 较高的正则化系数可能对数据欠拟合，因此在所有任务上效果都较差。

   我们在下图的实验结果中观察到这种效果。可以看到：

   • 随着正则化系数的提高，预测任务（链接预测、节点分类）的性能先达到峰值，然后开始恶化。
   • 随着正则化系数的提高，图重建任务的性能恶化。
   • 不同数据集上性能变化很大，因此需要为不同数据集仔细调整正则化系数。

   

3. HOPE： HOPE 将节点相似度矩阵分解从而得到node embedding，因此超参数取决于获得相似度矩阵的方法。由于我们在实验中使用 Katz 指数来计算相似度，因此我们评估了衰减因子$\beta$$ \beta $ 的效果。$\beta$$ \beta $ 因子可以解释为高阶邻近度的系数，并且最佳取值受到图结构的影响。

   • 对于具有紧密联系的、社区结构良好的图，较高的$\beta$$ \beta $ 值会错误地将不相似的节点嵌入到 embedding 空间中相近的位置。
   • 对于弱社区结构weak community 的图，重要的是捕获高阶距离，因此较高的$\beta$$ \beta $ 值可能会产生更好的 embedding 。

   下图的实验结果验证了我们的假设。结论：

   • 由于人工合成数据集 SBM 由紧密的社区组成，因此增加$\beta$$ \beta $ 并不会改善任何任务的性能。
   • 在 PPI, HEP-th 数据集中，随着$\beta$$ \beta $ 的增加任务性能也在提升。这是可以预期的，因为 PPI, Hep-th 数据集包含高阶的链接。
   • 在所有数据集中，最佳最佳$\beta$$ \beta $ 值对于图重构任务最低（为$2^{-6}$$ 2^{-6} $ ），对于节点分类预测任务最高（为$2^{-4}$$ 2^{-4} $ ）。这也符合直觉，因为高阶信息对于重建未观测的边不是必须的，但是对于预测任务很有用。彼此之间相距较远的节点比其相连的节点更有可能具有相同的标签。

   

4. SDNE：SDNE 使用耦合的深度自编码器来嵌入图，它利用超参数$\beta$$ \beta $ 来控制目标函数中监督损失和无监督损失的权重。较高的$\beta$$ \beta $ 值将关注于监督损失（对应于已观测链接），而忽视无监督损失（对应于未观测链接）。

   下图给出了不同参数值的实验结果。结论：

   • 链接预测性能随$\beta$$ \beta $ 值得不同而有很大差异。对于Hep-th 数据集，最佳$\beta$$ \beta $ 值使得链接预测的 MAP 提升超过 3 倍；对于 PPI 数据集，最佳$\beta$$ \beta $ 值使得链接预测的 MAP 提升大约 2 倍。
   • 节点分类性能受$\beta$$ \beta $ 值影响较小。
   • 总体而言，最佳性能在$\beta$$ \beta $ 不大不小时取得，超过最佳$\beta$$ \beta $ 则性能下降。

   

5. node2vec 在图上执行有偏得随机游走，并将共现的节点嵌入到 embedding 空间中靠近得位置。在该方法得各个超参数中，我们分析超参数$p$$ p $ 和$q$$ q $ 得影响，对于其它超参数保持固定（如，上下文窗口大小为 10，随机游走序列长度为 80）。

   超参数$p$$ p $ 和$q$$ q $ 控制了随机游走的方向和速度，它们允许我们的搜索过程在 BFS 和 DFS 之间插值，从而反应结点的不同类型的相似性。

   • 返回参数 Return Parameter$p$$ p $ ：参数$p$$ p $ 控制了重新访问上一步已访问节点的概率。

     • 一个较大的值$p>max(q,1)$$ p\gt \max(q,1) $ 将使得接下来访问的节点$x$$ x $ 不大可能是上一步已访问的节点$t$$ t $ （除非节点$v$$ v $ 除了$t$$ t $ 之外再也没有其它邻居）。

       这种策略鼓励适当的进行探索新结点，并避免采样过程中的冗余2-hop （即：经过两步转移又回到了结点本身）。

     • 一个较小的值$p<max(q,1)$$ p\lt \max(q,1) $ 将使得接下来访问的节点$x$$ x $ 很可能是上一步已访问的节点$t$$ t $ 。

       这种策略使得随机游走序列尽可能地留在源点$u$$ u $ 的局部区域。

   • 内外参数 In-out parameter$q$$ q $ ：参数$q$$ q $ 控制了探索的方向是向内搜索还是向外搜索。

     • 如果$q>1$$ q\gt1 $ 则$x$$ x $ 倾向于向$t$$ t $ 靠拢。这种策略将采样局限在一个很小的范围，从而获得网络的一个局部视图，类似于 BFS 的行为。
     • 如果$q<1$$ q\lt 1 $ 则$x$$ x $ 倾向于远离$t$$ t $ 。这种策略将鼓励采样向外拓展，从而获得网络的一个宏观视图，类似于 DFS 的行为。

     但是这种策略和BFS、DFS 本质上是不同的：我们的策略采样的结点与源点的距离并不是严格相等的（BFS）、也不是严格递增的 （DFS ）。另外我们的策略易于预处理，且采样效率很高。

   

   我们实验不同$p$$ p $ 和$q$$ q $ 值在 PPI, Hep-th 数据集得效果如下图所示。结论：

   • 较低值$q$$ q $ 值有助于实现更高的分类准确性，这表明捕捉结构等价性是准确嵌入图的结构所需要的。
   • 较高的$q$$ q $ 值有助于提升链接预测准确率，这表明捕获社区结构对于链接预测任务至关重要。

   

   我们实验不同$q$$ q $ 值对链接预测任务的SBM 的效果。结论：

   • 随着$q$$ q $ 的增加，链接预测 MAP 性能得到提升，直到最佳性能。
   • 由于 SBM 具有紧密联系的、结构良好的社区，因此最优$q$$ q $ 值要高得多。

   

2.4 GEM

1. 我们发布了一个开源的 Python 库：Graph Embedding Methods: GEM （https://github.com/palash1992/GEM ），它为这里介绍的所有方法的实现及其评估指标提供了一个统一的接口。该库同时支持加权图和无权图。GEM 的 hierarchical design 和模块化实现有助于用户在新的数据集上测试所实现的方法，并作为一个 platform 来轻松开发新的方法。

   GEM 提供了 Locally Linear Embedding 、Laplacian Eigenmaps、Graph Factorization、HOPE、SDNE 、以及 node2vec的实现。对于node2vec，我们使用作者提供的C++实现并提供一个 Python 接口。

   此外，GEM提供了一个接口来在上述四个任务上评估学到的 embedding 。该接口很灵活，支持多种边重建指标，包括余弦相似度、欧氏距离、以及 decoder based 指标。对于多标签的节点分类，该库使用 one-vs-rest 逻辑回归分类器，并支持使用其他临时 ad hoc 的分类器。

2.5 未来方向

1. 我们认为在图嵌入领域有三个有前途的研究方向：

   • 探索非线性模型：如综述所示，通用的非线性模型（如，基于深度学习的模型）在捕获图的固有动态inherent dynamics 方面显示出巨大的前景。这些非线性模型有能力近似任意函数，但是缺点是可解释性有限。

     进一步研究这些模型所学到的 embedding 的可解释性，可能是非常有用的。

   • 研究网络的演变 evolution：利用 embedding 来研究图的演变是一个新的研究领域，需要进一步探索。

   • 生成具有真实世界特征的人工合成网络：生成人工合成网络一直是一个流行的研究领域，主要是为了便于模拟。真实graph 的低维向量 representation 可以帮助理解图结构，因此对生成具有真实世界特征的人工合成图很有帮助。