【Graph Embedding】SDNE

关于Graph Embedding系列的论文翻译解读文章：

【Graph Embedding】DeepWalk

【Graph Embedding】line

【Graph Embedding】node2Vec

【Graph Embedding】SDNE

【Graph Embedding】struc2vec

参考资料

paper: https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf

摘要

网络embedding是学习网络中点的低维表示的一种重要方法，目的是捕获和保持网络结构。现有的网络embedding方法几乎都采用了浅层模型。然而，由于底层网络结构复杂，浅层模型无法捕捉到高度非线性的网络结构，导致网络表示不够理想。因此，如何找到一种能够有效捕获高度非线性网络结构并保持全局和局部结构的方法是一个开放而重要的问题。为了解决这一问题，本文提出了一种结构化的深度网络嵌入方法，即SDNE。更具体地说，我们首先提出了一个具有多层非线性函数的半监督深度模型，从而能够捕获高度非线性的网络结构。在此基础上，我们提出了利用一阶近似和二阶近似共同保持网络结构的方法。非监督组件使用二阶接近度来捕获全局网络结构。而一阶邻近度作为监督分量中的监督信息，以保持局部网络结构。该方法通过在半监督深度模型中联合优化，既保留了局部网络结构又保留了全局网络结构，对稀疏网络具有较强的鲁棒性。在实证方面，我们对5个真实世界的网络进行了实验，包括一个语言网络、一个引文网络和3个社交网络。结果表明，与基线相比，该方法能较好地重建原始网络，并在多标签分类、链接预测和可视化三个方面取得了显著的效果。

1. 介绍

如今，网络无处不在，许多真实世界的应用程序需要在这些网络中挖掘信息。例如，Twitter中的推荐系统旨在挖掘社交网络中用户喜欢的tweets。网络广告投放往往需要将用户聚集到社交网络的社区中。因此，在网络中挖掘信息是非常重要的。其中一个基本问题是如何学习有用的网络表示[5]。一种有效的方法是将网络嵌入到一个低维空间中，即学习每个顶点的向量表示，目的是在学习的嵌入空间中重建网络。因此，在网络中挖掘信息，如信息检索[34]，分类[15]和聚类[20]可以直接在低维空间中进行。

学习网络表征面临以下重大挑战: (1)高度非线性:如[19]所述，网络底层结构高度非线性。因此，如何设计一个模型来捕捉高度非线性的结构是相当困难的。(2)保持结构:为了支持分析网络的应用，需要通过网络嵌入来保持网络结构。然而，网络的底层结构非常复杂。顶点的相似性依赖于局部和全局网络结构。因此，如何同时保持局部和全局结构是一个棘手的问题。(3)稀疏性:许多真实世界的网络常常是如此的稀疏，以至于仅利用非常有限的观测链路不足以达到令人满意的性能。

在过去的几十年里，许多网络嵌入方法被提出，它们采用了浅模型，如IsoMAP[29]，Laplacian特征映射(LE)[1]和Line[26]。然而，由于浅层模型[2]的表示法能力有限，难以捕捉到高度非线性的网络结构[30]。虽然有些方法采用了核心技术[32]，但如[36]所述，核心方法也是浅层模型，不能很好地捕捉高度非线性的结构。

为了更好地捕获高度非线性的网络结构，本文提出了一种学习网络顶点表示的深度模型。这是由最近成功的深度学习驱动的，深度学习被证明具有强大的表示能力来学习数据[2]的复杂结构，并在处理图像[15]、文本[25]和音频数据[10]方面取得了实质性的成功。特别地，在我们提出的模型中，我们设计了一个由多个非线性函数组成的多层体系结构。多层非线性函数的组合可以将数据映射到一个高度非线性的潜在空间，从而能够捕捉到高度非线性的网络结构。

为了解决深度模型的结构保持和稀疏性问题，我们进一步提出将一阶和二阶近似[26]联合应用到学习过程中。一阶近似是仅在由边连接的顶点之间的局部两两相似，这是局部网络结构的特征。然而，由于网络的稀疏性，许多有效的链接都丢失了。因此，一阶邻近度不足以表示网络结构。因此，我们进一步提出二阶邻近度来表示顶点邻域结构的相似性，以捕捉全局网络结构。利用一阶和二阶邻近性，我们可以分别很好地刻画局部和全局网络结构。为了在深度模型中保护局部和全局网络结构,我们提出半监督架构,非监督的组件可以利用二阶距离保护全局网络结构而监督组件利用一阶距离作为监督信息保存局部的网络结构。因此，所学习的表示法可以很好地保持局部和全局网络结构。此外，如图1所示，具有二阶接近度的顶点对的数量要比具有一阶接近度的顶点对的数量大得多。因此，二阶邻近度的引入能够在描述网络结构方面提供更多的信息。结果表明，该方法对稀疏网络具有较强的鲁棒性。

根据经验，我们在五个真实的网络数据集和四个真实的应用程序上进行了实验。结果表明，与基线相比，我们的方法生成的表示能更好地重构原始网络，并在各种任务和各种网络(包括非常稀疏网络)上获得可观的收益。结果表明，我们在高度非线性空间中学习的表示方法能够很好地保持网络结构，并且对稀疏网络具有较强的鲁棒性。

综上所述，本文的贡献如下:

• 提出了一种结构化的深度网络embedding方法，即SDNE。该方法能够将数据映射到一个高度非线性的潜在空间中，从而保持网络结构，对稀疏网络具有较强的鲁棒性。
• 提出了一种新的半监督结构的深度模型，该模型同时优化了一阶近似和二阶近似。结果表明，该算法保持了局部和全局网络结构，对稀疏网络具有较强的鲁棒性。
• 该方法在5个实际数据集和4个应用场景中得到了广泛的评价。结果表明，该方法在多标签分类、重建、链接预测和可视化等方面具有较好的实用性。具体来说，我们的方法可以在标记数据缺乏的情况下实现比基线更显著的改进(20%)。在某些情况下，我们减少60%的训练样本，但仍然可以获得更好的性能。

2. 相关工作

2.1 深度神经网络

表示学习长期以来一直是机器学习的一个重要问题，许多研究工作都是针对样本的表示学习[3,35]。深度神经网络的最新进展表明，它们具有强大的表示能力[12]，可以为许多类型的数据生成非常有用的表示。例如，[15]提出了一个七层卷积神经网络来生成图像表示进行分类。[33]提出了一个多模态深度模型来学习图像-文本的统一表示来实现跨模态检索任务。

然而，就我们所知，深度学习用来处理网络的工作很少，尤其是学习网络表示的工作。在[9]中，采用限制玻尔兹曼机进行协同过滤。[30]采用深度自动编码器进行图形聚类。[5]提出了一种异构深度模型来进行异构数据嵌入。我们与这些作品有两个不同之处。首先，目标不同。我们的工作重点是学习低维结构保留的网络表示，这些表示可以用于任务之间。其次，我们考虑顶点之间的一阶和二阶邻近性，以保持局部和全局网络结构。但它们只关注一阶信息。

2.2 网络Embedding

我们的工作解决了网络嵌入的问题，即学习网络的表示。一些早期的作品像Local Linear Embedding(LLE)[22]、IsoMAP[29]首先基于特征向量构造亲和图，然后求解主导特征向量作为网络表示。最近,[26]设计了两个试图分别捕获局部和全局网络结构的损失函数。此外，[4]扩展了工作以利用高阶信息。尽管这些网络embedding方法取得了成功，但它们都采用了浅层模型。如前所述，浅层模型很难有效地捕获底层网络中高度非线性的结构。此外，尽管他们中的一些人试图使用一阶和高阶邻近性来保存局部和全局网络结构，但他们分别学习这些表示并简单地连接这些表示。显然，在一个统一的架构中同时对它们进行建模来捕获局部和全局网络结构是次优的。

DeepWalk[21]结合随机漫步和跳跃图来学习网络表示。虽然在经验上是有效的，但它缺乏一个明确的目标函数来阐明如何保持网络结构。它倾向于只保留二级邻近性。然而，我们的方法设计了一个明确的目标函数，它通过保留一阶和二阶邻近性来同时保留局部和全局结构。

3. SDNE(Structural Deep Network Embedding)

首先定义问题。然后介绍了SDNE的半监督深度模型。最后对模型进行了讨论和分析。

3.1 问题定义

首先给出图的定义。

定义1. 图

设$G = (V, E)$是一个给定的网络。其中$V = \{v_1, …, v_n\}$代表顶点的集合，$E = \{e_{i, j}\}_{i,j=1}^n$代表边的集合，每条边$e_{i,j}$有一个权重$s_{i,j} \geq 0$。如果$v_i$和$v_j$没有连接，则$s_{i,j} = 0$。此外，对于未加权的图$s_{i,j} = 1$，对于加权图$s_{i,j} > 0$。

定义2. 一阶相似度

一阶近似描述一对顶点之间的两两相似性。对于任意一对顶点，如果$s_{i,j} > 0$，则$v_i$与$v_j$之间存在正一阶近似。否则，$v_i$和$v_j$之间的一阶相似度为0

定义3. 二阶相似度

一对顶点之间的二阶相似度描述了相邻结构的邻近性。设$\cal N_u = \{s_{u,1}, …, s_{u, |V|}\}$表示$v_u$和其他顶点之间的一阶相似度。然后，二阶相似度由$\cal N_u$和$\cal N_v$的相似度决定。

直观地说，二阶相似性假设如果两个顶点有许多共同的邻居，它们就趋向于相似。这种假设在很多领域都被证明是合理的[6,14]。例如，在语言学中，如果单词总是被相似的上下文[6]包围，它们就会是相似的。如果人们有很多共同的朋友，他们会成为朋友。二阶相似度已被证明是定义一对顶点相似度的良好度量，即使它们没有被一条边[17]连接，因此可以极大地丰富顶点之间的关系。因此，通过引入二阶相似性，能够表征全局网络结构，缓解稀疏性问题。

利用一阶近似和二阶近似，研究了在进行网络嵌入时如何同时集成它们以保持局部结构和全局结构的问题。这个问题的定义如下:

定义4. 网络Embedding

给定一个图$G = (V, E)$，网络embedding旨在学习一个映射函数$f: v_i \to y_1 \in \Bbb R^d$，其中$d \ll |V|$。该函数的目的是使$y_i$和$y_j$之间的相似度明确地保持$v_i$和$v_j$的一阶和二阶邻近性。

3.2 模型

3.2.1 框架

本文提出了一种半监督深度模型来进行网络embedding，其框架如图2所示。为了捕获高度非线性的网络结构，我们提出了一种深度结构，它由多个非线性映射函数组成，将输入数据映射到一个高度非线性的潜在空间来捕获网络结构。此外，为了解决结构保持和稀疏性问题，我们提出了一种利用二阶和一阶近似的半监督模型。对于每个顶点，我们都可以得到它的邻域。因此，我们通过重构每个顶点的邻域结构来设计无监督分量来保持二阶邻近性。同时，对于一小部分节点对，我们可以得到它们的配对相似性，即一阶近似。因此，我们设计了监督分量来利用一阶近似作为监督信息来细化潜在空间中的表示。通过联合优化半监督深度模型，SDNE能较好地保持高度非线性的局部全局网络结构，对稀疏网络具有较强的鲁棒性。在下一节中，我们将详细介绍如何实现半监督深度模型。

3.2.2 损失函数

在介绍损失函数之前，我们定义表1中的一些术语和符号，这些术语和符号将在后面使用。注意，上面的参数^表示解码器的参数。

现在我们介绍半监督模型的损失函数。我们首先描述无监督组件如何利用二阶邻近性来保持全局网络结构。

二阶邻近度是指一对顶点的邻域结构的相似程度。因此，为了对二阶近似进行建模，需要对每个顶点的邻域进行建模。给定一个网络$G = (V, E)$，我们可以得到它的邻接矩阵$S$，其中包含n个实例$s_1, …, s_n$。对于每个实例，$s_i = \{s_{i,j}\}_{j=1}^n, s_{i,j} > 0$当且仅当$v_i$和$v_j$之间存在联系时。因此，$s_i$描述了顶点$v_i$的邻域结构，$S$提供了每个顶点的邻域结构信息。使用$S$，我们扩展了传统的深度自动编码器[23]，以保持二阶接近。

考虑到是自包含的，我们简要回顾了深层自动编码器的关键思想。它是一个由编码器和解码器两部分组成的无监督模型。编码器由多个将输入数据映射到表示空间的非线性函数组成。解码器由多个非线性函数组成，将表示空间中的表示映射到重构空间。然后给定输入$x_i$，各层的隐藏表示如下2所示:

$$y_i^{(1)} = \sigma(W^{(1)}x_i + b^{(1)}) \\ y_i^{(k)} = \sigma(W^{(k)}y_i^{(k-1)} + b^{k}), k=2,...,K \tag{1}$$

在得到$y_i^{(k)}$之后，我们可以通过逆转编码器的计算过程得到输出$\hat{x_i}$。自动编码器的目标是最小化输出和输入的重构误差。损失函数如下:

$$\cal L = \sum_{i=1}^n\parallel \hat{x_i} - x_i \parallel_{2}^2 \tag{2}$$

[23]证明，虽然最小化重构损失并不能显式地保持样本间的相似性，但是重构准则可以平滑地捕获数据流形，从而保持样本间的相似性。然后考虑我们的例子中,如果我们使用邻接矩阵$S$作为自动编码器作为输入,即$x_i = s_i$，因为每个实例$s_i$表示顶点$v_i$的邻域结构，重构过程将使具有相似邻域结构的顶点具有相似的潜在表示。

然而，由于网络的某些特定特性，这种重建过程不能直接应用于我们的问题。在网络中，我们可以观察到一些链接，但同时也观察不到许多合法的链接，这意味着顶点之间的链接确实表示它们之间的相似性，但没有链接不一定表示它们之间的差异性。此外，由于网络的稀疏性，$S$中非零元素的数量远远小于零元素的数量。然后如果我们直接使用$S$作为传统的自动编码器的输入，它更容易在$S$中重建零元素，然而，这不是我们想要的。为了解决这一问题，我们对非零元素的重构误差比零元素的重构误差施加了更多的惩罚。修正后的目标函数如下:

$$\cal L_{2nd} = \mit \sum_{i=1}^n\parallel \hat{x_i} - x_i \odot b_i \parallel_{2}^2 \\ =\parallel(\hat{X} - X) \odot B \parallel_F^2 \tag{3}$$

其中$\odot$为Hadamard乘积，$bi = \{b_{i,j}\}_{j=1}^n$。如果$s_{i,j} =0$，则$b_{i,j} = 1$，否则$b_{i,j} = \beta > 1$。利用修正后的深度自编码器，以邻接矩阵S作为输入，将具有相似邻域结构的顶点映射到表示空间附近，由重构准则保证。换句话说，我们的模型的无监督组件可以通过重建顶点之间的二阶接近度来保持全局网络结构。

既要保留全局网络结构，又要捕捉局部结构。我们用一阶近似来表示局部网络结构。一阶近似可视为约束一对顶点潜在表示的相似性的监督信息。因此，我们设计监督组件来利用一阶邻近性。该目标的损失函数定义如下:

$$\cal L_{1st} = \mit \sum_{i,j=1}^n s_{i,j} \parallel y_i^{(K)} - y_j^{(K)} \parallel_2^2 \\ = \sum_{i,j=1}^n s_{i,j} \parallel y_i - y_j \parallel_2^2 \tag{4}$$

等式4的目标函数借用了拉普拉斯变换的思想[1]，当相似的顶点被映射到离嵌入空间很远的地方时，就会受到惩罚。一些关于社交网络[13]的工作也使用了类似的想法。我们区分它们的方面是，我们在深层模型中加入了这个想法，使由一条边连接的顶点被映射到嵌入空间附近。因此，该模型保持了一阶近似性。

为了同时保持一阶和二阶邻近性，我们提出了一个结合等式3和等式4的半监督模型，使下列目标函数最小化：

$$\cal L_{mix} = L_{2nd} + \alpha L_{1st} + vL_{reg} \\ = \mit \parallel(\hat{X} - X) \odot B\parallel_F^2 + \alpha\sum_{i,j=1}^n s_{i,j} \parallel y_i - y_j \parallel_2^2 + v \cal L_{reg} \tag{5}$$

其中，$\cal L_{reg}$是一个$\cal L2$正则项：

$$\cal L_{reg} = \mit \frac{1}{2}\sum_{k=1}^K(\parallel W^{(k)} \parallel_F^2 + \parallel \hat{W}^{(k)} \parallel_F^2)$$

3.2.3 优化

为了优化上述模型，目标是最小化$\theta$的函数$\cal L_{mix}$。其中的关键步骤是计算的偏导数$\cal \partial L_{mix} / \partial \hat{W}^{(k)}$和$\cal \partial L_{mix} / \partial W^{(k)}$。偏导数的详细数学形式如下:

$$\frac {\cal \partial L_{mix}}{\partial \hat{W}^{(k)}} = \frac{\partial \cal L_{2nd}}{\partial \hat{W}^{(k)}} + v \frac{\partial \cal L_{reg}}{\partial \hat{W}^{(k)}} \\ \frac {\cal \partial L_{mix}}{\partial W^{(k)}} = \frac{\partial \cal L_{2nd}}{\partial W^{(k)}} + \alpha \frac{\partial \cal L_{1st}}{\partial W^{(k)}} + v \frac{\partial \cal L_{reg}}{\partial W^{(k)}} \tag{6}$$

我们首先看$\frac{\partial \cal L_{2nd}}{\partial \hat{W}^{(K)}}$，可以改写为：

$$\frac{\partial \cal L_{2nd}}{\partial \hat{W}^{(K)}} = \frac{\partial \cal L_{2nd}}{\partial \hat{X}}.\frac{\partial \hat{X}}{\partial \hat{W}^{(K)}} \tag{7}$$

对于第一项，根据等式3，我们有:

$$\frac{\partial \cal L_{2nd}}{\partial \hat{X}} = 2(\hat{X} - X) \odot B \tag{8}$$

第二项的计算$\frac{\partial \hat{X}}{\partial \hat{W}}$很容易根据$\hat{X} = \sigma(\hat{Y}^{(K-1)}\hat{W}^{(K)} + \hat{b}^{(K)})$计算。那么$\frac{\partial \cal L_{2nd}}{\partial \hat{W}^{(K)}}$也是可得的。基于反向传播，我们可以迭代得到$\frac{\partial \cal L_{2nd}}{\partial \hat{W}^{(K)}}, k=1,…,K-1$和$\frac{\partial \cal L_{2nd}}{\partial W^{(k)}}, k=1,…,K$。现在$\cal L_{2nd}$的偏导数的计算已经完成了。

然后我们继续计算$\frac{\partial \cal L_{1st}}{\partial W^{(k)}}$的偏导数。$\cal L_{1st}$的损失函数可以重新表述为:

$$\cal L_{1st} = \mit \sum_{i,j=1}^n s_{i,j} \parallel y_i - y_j \parallel_2^2 = 2tr(Y^TLY) \tag{9}$$

其中$L = D - S$，$D \in \Bbb R^{n \times n}$是对角矩阵，$D_{i,j} = \sum_j s_{i,j}$。

然后我们首先重点计算$\frac{\partial \cal L_{1st}}{\partial W^{(k)}}$:

$$\frac{\partial \cal L_{1st}}{\partial W^{(k)}} = \frac{\partial \cal L_{1st}}{\partial Y}.\frac{\partial Y}{\partial W^{(K)}} \tag{10}$$

因为$Y = \sigma(Y^{(K-1)}W^{(K)} + b^{(K)})$，第二项的计算$\frac{\partial Y}{\partial W^{(K)}}$也是比较容易的。对于第一项$\frac{\partial \cal L_{1st}}{\partial Y}$的计算，有：

$$\frac{\partial \cal L_{1st}}{\partial Y} = 2(L + L^T).Y \tag{11}$$

同样地，利用反向传播我们可以完成$\cal L_{1st}$的偏导计算。

现在我们得到了参数的偏导数。在参数初始化的情况下，利用随机梯度下降法对模型进行优化。注意，由于模型高度非线性，在参数空间中存在许多局部最优。因此，为了找到一个好的参数空间区域，我们首先使用深度信念网络对参数进行预训练，这在文献中已经被证明是深度学习中参数初始化的必要步骤[7]。完整的算法参见Alg. 1。

3.3 分析和讨论

在这一节中，我们对所提出的SDNE半监督深度模型进行了一些分析和讨论。

新顶点: 网络embedding的一个实际问题是如何学习新顶点的表示。对于一个新的顶点$v_k$，如果其与已有顶点的连接已知，则可以得到其邻接向量$x = \{s_{1,k}, …, s_{n,k}\}$，其中$s_{i, k}$表示现有$v_i$与新顶点$v_k$的相似性。然后我们可以简单地将$x$输入到我们的深度模型中，并使用经过训练的参数$\theta$来得到$v_k$的表示。这样一个过程的复杂度是$O(1)$。如果$v_i$和网络中现有的顶点之间没有连接，我们的方法和最先进的网络embedding方法都无法处理。为了处理这种情况，我们可以求助于其他方面的信息，比如新顶点的内容特性，我们将其留作以后的工作。

训练复杂度: 不难看出，我们的模型训练复杂度为$O(ncdI)$，其中$n$为顶点数，$d$为隐含层的最大维数，$c$为网络的平均度，$I$为迭代次数。参数$d$通常与嵌入向量的维数有关，而与顶点数无关。$I$和$n$是独立的。对于$c$来说，在实际应用中它通常可以看作一个常量。例如，在社交网络中，一个人的最大朋友数总是有限的[30]。在top-k相似图中，$c = k$，因此$cdI$与$n$无关，因此整体训练复杂度与网络中顶点的数量成线性关系。

4. 试验

在本节中，我们将在几个真实世界数据集和应用程序上评估我们提出的方法。实验结果表明在基线上有显著的改进。

4.1 数据集

为了全面评估这些表达的有效性，我们使用了5个数据集，包括3个社交网络、1个引用网络和1个语言网络，用于3个现实世界的应用，即多标签分类、链接预测和可视化。考虑到这些数据集的特点，我们为每个应用程序使用一个或多个数据集来评估性能。具体描述如下。

• BLOGCATALOG[27]、FLICKR[27]和YOUTUBE[28]:它们是在线用户的社交网络。每个用户至少有一个类别的标签。总的来说，BLOGCATALOG有39个不同的类别，FLICKR有195个类别，类别有47个类别。这些类别可以用作每个顶点的基本事实。因此，它们可以通过多标签分类任务进行评价。
• RXIV GR-QC[16]:是一个来自arXiv的论文协作网络，涵盖了广义相对论和量子宇宙学的论文。在这个网络中，顶点表示作者，而边缘表示作者在arXiv中合作发表过一篇科学论文。数据集用于链接预测任务，因为我们没有每个顶点的类别信息。
• 20-NEWSGROUP4:这个数据集是一个20000个新闻组文档的近似值集合，每个文档由20个不同组中的一个标记。我们使用每个单词的tfidf向量表示文档，余弦相似度表示两个文档之间的相似度。我们可以根据这样的相似性来构建网络。我们选择标记为comp.graphics, rec.sport.baseball和talk.politics.gums来执行可视化任务。

综上所述，我们进行了加权和非加权、稀疏和稠密、小网络和大网络的实验。因此，数据集可以全面反映网络embedding方法的特点。数据集的详细统计信息可在表2中汇总。

4.2 Baseline 算法

我们使用以下五种方法作为基线。前四种是网络embedding方法。共同近邻直接预测网络上的链路，是实现链路预测[17]的有效方法。

• DeepWalk[21]:采用随机游走和跳跃图模型生成网络表示。
• LINE[26]:它定义了损失函数来分别保留一阶或二阶邻近性。在优化损失函数之后，它连接这些表示。
• GraRep[4]:它扩展到高阶邻近，并使用SVD来训练模型。它还可以直接连接一阶和高阶的表示方法。
• Laplacian特征映射(LE)[1]:它通过分解邻接矩阵的Laplacian矩阵来生成网络表示。它只利用一阶近似来保持网络结构。
• 共同邻居(Common Neighbor)[17]:它只使用共同邻居的数量来衡量顶点之间的相似性。它仅用于链路预测任务的基线。

4.3 评估指标

在我们的实验中，我们完成了重建、链接预测、多标签分类和可视化的任务。对于重建和链路预测，我们使用precision@k和Mean Average Precision(MAP)来评估性能。它们的定义如下:

• precision@k是一个给返回实例同等权重的度量。定义如下:

  $$precision@k = \frac{|\{j|i,j \in V,inder(j) \leq k, \Delta_i(j)=1\}|}{k}$$

  其中V为顶点集，$index(j)$为第$j$个顶点的排序索引，$\Delta_i(j) = 1$表示$v_i$与$v_j$有关联。

• Mean Average Precision(MAP)：

  $$AP(i) = \frac{\sum_j precision@j(i).\Delta_i(j)}{|\{\Delta_i(j) = 1\}|} \\ MAP = \frac{\sum_{i \in Q}AP(i)}{|Q|}$$

对于多标签分类任务，我们采用了micro-F1和macro-F1。

• Macro-F1是一个给每个类同等权重的度量。定义如下:

$$Macro-F1 = \frac{\sum_{A \in C}F1(A)}{|C|}$$

其中$F1(A)$为标签A的F1度量。

• Micro-F1是一个给每个实例同等权重的度量。定义如下:

$$Pr = \frac{\sum_{A \in C}TP(A)}{\sum_{A \in C}(TA(A) + FP(A))}, R = \frac{\sum_{A \in C}TP(A)}{\sum_{A \in C}(TA(A) + FN(A))} \\ Micro-F1 = \frac{2\*Pr\*R}{Pr + R}$$

4.4 参数设置

在本文中，我们提出了一个多层的深层结构，层的数量随着不同的数据集而变化。表3列出了每个层的维数。神经网络有三层影藏层用于BLOGCATALOG, ARXIV GR-QC和20-NEWSGROUP，四层影藏层用于FLICKR和YOUTUBE。如果我们使用更深层次的模型，性能几乎保持不变，甚至变得更差。

对于我们的方法，通过在验证集上使用网格搜索来调整超参数$\alpha$,$\beta$和$v$，将基线的参数调整为最优。对于LINE，随机梯度下降的小批量大小设置为1。初始值的学习率为0.025。设负采样数为5，样本总数为100亿个。此外，根据[26]，连接1阶和2阶表示形成最终的embedding向量并通过L2归一化到最终的embedding向量，LINE产生更好的结果。我们按照他们的方式来得到结果。对于DeepWalk，我们设置窗口大小为10，步长为40，每个顶点的步长为40。对于GraRep，我们设置最大矩阵转移步长为5。

4.5 试验结果

在本节中，我们首先评估重构性能。然后，我们报告了在三种经典的数据挖掘和机器学习应用，即多标签分类、链接预测和可视化中，不同embedding方法生成的网络表示的泛化结果。

4.5.1 网络重构

在评估该方法在实际应用中的泛化性之前，我们首先对不同网络embedding方法的网络重构能力进行了基本评估。这个实验的原因是一个好的网络embedding方法应该保证所学习的嵌入能够保持原来的网络结构。我们使用语言网络ARXIV GR-QC和社交网络BLOGCATALOG代表。对于给定的网络，我们使用不同的网络embedding方法来学习网络表示，然后预测原始网络的链接。由于原网络中存在的链路已知，可以作为ground-truth，我们可以评估不同方法的重构性能，即训练集误差。使用precision@k和MAP作为评估指标。precision@k的结果如图3所示。MAP的结果见表4。

从结果来看，我们有以下观察和分析:

• 表4显示了我们的方法在两个数据集的基线之上实现了显著的改进。图3显示，当k增加时，我们方法的precision@k始终是最高的。结果表明，该方法能较好地保持网络结构。
• 具体来说，对于ARXIV GR-QC网络，我们的方法的precision@k可以达到100%左右,直到k增加到10000时保持在100%。这说明我们的方法几乎可以完美地重构出这个数据集中的原始网络，特别是考虑到这个数据集中的链接总数是28980条。
• 虽然SDNE和LINE都利用了一阶和二阶邻近性来保持网络结构，但SDNE的性能更好。原因可能是两方面。首先，LINE采用浅层结构，难以捕捉底层网络中高度非线性的结构。其次，LINE将一阶近似和二阶近似的表示法直接串联起来，这在SDNE中是次优的。
• SDNE和LINE的性能都优于LE, LE只利用一阶近似来保持网络结构，说明引入二阶近似可以更好地保持网络结构。

4.5.2 多分类

在众多的应用中，分类是一项非常重要的工作，因此许多相关的算法和理论已经被[18]研究过。因此，我们在本实验中通过一个多标签分类任务来评估不同网络表示的有效性。顶点的表示由网络embedding方法生成，并作为特征将每个顶点分类为一组标签。具体来说，我们采用LIBLINEAR[8]来训练分类器。在训练分类器时，我们随机抽取标记节点的一部分作为训练数据，其余部分作为测试。对于BLOGCATALOG，我们随机抽取10%到90%的顶点作为训练样本，并使用剩余的顶点来测试性能。对于FLICKR和YOUTUBE，我们随机抽取1%到10%的顶点作为训练样本，并使用剩余顶点来测试性能。另外，我们删除了在YOUTUBE上没有任何类别标记的顶点。我们重复这个过程5次，并报告平均的Micro-F1和Macro-F1。结果分别如图4和图5所示。

从结果来看，我们有以下观察和分析:

• 在图4和图5中，我们的方法的曲线始终高于基线的曲线。结果表明，与基线相比，该方法的学习网络表示能更好地推广到分类任务。
• 在图4 (BLOGCATALOG)中，当训练百分比从60%下降到10%时，我们的方法在基线上的改进幅度更加明显。结果表明，在标记数据有限的情况下，该方法比基线方法有更大的改进。这种优势对于实际应用尤其重要，因为标记的数据通常是稀缺的。
• 在大多数情况下，DeepWalk的性能是网络embedding方法中最差的。原因有两个。首先，DeepWalk没有明确的目标函数来捕获网络结构。其次,DeepWalk采用随机漫步的方式来丰富顶点的邻居，这种随机的方式引入了大量的噪声，特别是对于那些高阶顶点。

4.5.3 链路预测

在本节中，我们主要针对链路预测任务进行了两个实验。第一个评估总体性能，第二个评估网络的不同稀疏性如何影响不同方法的性能。

在本节中，我们将使用数据集ARXIV GR-QC。为了在网络中进行链路预测任务，我们随机隐藏一部分现有链路，利用剩余网络训练网络embedding模型。训练结束后，我们可以得到预测未观测链路的表征。与重构任务不同，此任务预测未来链接，而不是重构现有链接。因此，该任务可以表现出不同网络embedding方法的可预测性。另外，我们添加共同近邻是一种有效的链路预测方法。

在第一个实验中，我们随机隐藏了15%的的已有链接(约4000个链接)，并使用precision@k作为预测隐藏链接的评价指标。我们逐步将k从2增加到10000，结果如表5所示。最佳性能以粗体突出显示。表5的一些观察和分析结果如下:

• 结果表明，当k增加时，我们的方法的性能始终优于其他网络嵌入方法。结果表明，用该方法学习的表征对新链接的形成具有更好的预测能力。
• 当k = 1000时，我们的方法的精度仍然高于0.9，但是其他方法的精度很快下降到0.8以下。结果表明，该方法能够保持较高的排名精度。这种优势对于推荐和信息检索等实际应用程序非常重要，因为用户更关心在这些应用程序中排名靠前的结果。

在第二个实验中，我们通过随机删除原网络中的一部分链接来改变网络的稀疏性，然后按照上述步骤报告不同网络embedding方法的结果。结果显示在图6。

结果表明，当网络越稀疏，LE与SDNE之间或LE与LINE之间存在的差距越大。结果表明，二阶近似的引入使得学习表示对稀疏网络具有更强的鲁棒性。此外，当我们删除80%的链接时，我们的方法仍然比基线执行得好得多。它还演示了SDNE在处理稀疏网络中的强大功能。

4.5.4 可视化

网络embedding的另一个重要应用是在二维空间中生成网络的可视化。因此，我们将20个新闻组网络的学习表示可视化。我们使用不同网络embedding方法获得的低维网络表示作为可视化工具t-SNE[31]的输入。因此，每个新闻组文档都被映射为一个二维向量。然后我们可以把每个向量想象成二维空间中的一个点。对于标记为不同类别的文件，我们在对应的点上使用不同的颜色。因此，一个良好的可视化结果是，相同颜色的点彼此接近。可视化图如图7所示。除了可视化图形外，我们还使用与[4]相似的Kullback-Leibler散度作为定量评价指标。KL散度越小，性能越好。结果如表6所示。

从图7可以看出，LE和DeepWalk的结果并不令人满意，因为属于不同类别的点是混合在一起的。对于LINE，形成了不同类别的集群。但是在中间部分，不同类别的文档仍然混杂在一起。对于GraRep，结果看起来更好，因为相同颜色的点形成分段组。然而，每个群体的界限不是很清楚。显然，SDNE的可视化在组分离和边界方面表现得最好。表6中的结果也定量地证明了我们的方法在可视化任务中的优越性。