NLP（一）学习《网络表示学习综述》

作者: shijiatongxue | 来源:发表于2018-10-17 17:39 被阅读0次

0 摘要

网络是表达物体和物体间联系的一种重要形式，针对网络的分析研究的一个关键问题就是研究如何合理地表示网络中的特征信息。

1 引言

在学术价值方面，能否对复杂信息网络做出有效合理的数据分析是今后学术研究上的热门话题。
在应用价值方面，信息网络中拥有着非常广泛的应用前景，如节点分类、链接预测、社区发现、推荐系统等任务。

1.1 挑战

一个重要的问题就是如何合适地表示网络信息。传统的网络表示一般使用高维的稀疏向量。但是高维稀疏的表示也成为了人们使用统计学习方法时的局限所在，因为高维的向量将会花费更多的运行时间和计算空间。随着表示学习技术的发展，研究者转而探索将网络中的节点表示为低维稠密的向量表示方法。有效融合网络结构与节点外部信息，形成更具区分性的网络表示成为挑战。

2 网络表示学习的定义

网络表示是衔接网络原始数据和网络应用任务的桥梁。
网络表示学习算法负责从网络数据中学习得到网络中每个节点的向量表示，之后这些节点表示就可以作为节点的特征应用于后续的网络应用任务。

网络表示学习流程图.png

3 基于网络结构的网络表示学习

3.1 基于矩阵特征向量计算

较早的用于网络表示学习的算法主要归于此类。谱聚类算法通过计算关系矩阵的前k个特征向量或奇异向量来得到k维的节点表示。关系矩阵一般就是网络的邻接矩阵或者Laplace矩阵。这类方法强烈依赖于关系矩阵的构建，不同的关系矩阵的测评结果差异很大。一般来讲，基于谱聚类方法的时间复杂度较高，因为特征向量和奇异向量的计算时间是非线性的。另一方面，谱聚类方法需要将关系矩阵整体存在内存中，所以空间复杂度也是不能忽略的。现在将展示几种谱聚类算法的实例。
局部线性表示（locally linear embedding）假设节点的表示是从同一个流形中采样得到的。一个节点的表示可以通过它的邻居节点的表示的线性组合来近似得到。局部线性表示使用邻居节点表示的加权和与中心节点表示的距离作为损失函数。最小化损失函数的优化问题最终转化为某个关系矩阵特征向量计算问题求解。
Laplace特征表（Laplace eigenmap）简单的假设两个相连的节点的表示应该相近。特别地，这里表示相近是由向量表示的欧式距离的平方来定义。该优化问题可以类似地转化为Laplace矩阵的特征向量计算问题。
有向图表示（directed graph embedding）进一步扩展了Laplace特征表方法，给不同点的损失函数以不同的权重。其中点的权重是由基于随机游走的排序方法来决定，如PageRank。
不同于前面的方法，Tang和Liu假设节点表示的每一维对应着该节点从属于一个社区的强度，进而将模块性引入了损失函数。模块性事衡量网络分离程度的指标，高的模块值意味着在同一模块内节点连接紧密，而不同模块间节点连接稀疏。最终该优化问题转化为归一化的Laplace矩阵的特征向量计算。
此类方法一般先定义一个关于节点表示的线性或二次函数损失函数。然后将最优化问题转化为某个关系矩阵的特征向量计算问题。这一类方法最主要的缺点在于复杂度：大规模矩阵的特征向量计算是非常消耗计算时间和空间的。
模型的适用性比较如下：

模型	无向图	有权图	有向图
局部线性表示	√	-	-
Laplace特征表	√	√	-
有向图表示	√	√	√

3.2 基于简单神经网络的算法

对最优化问题求最优解的过程，如特征向量的计算，对于大规模网络数据来说是非常耗时的。另一方面，基于神经网络的方法已经在自然语言和图像领域取得了非常突出的成果。虽然梯度下降的参数更新方法无法保证总是得到最优化问题的最优解，但是神经网络的方法一般更加快速而且也能得到相当不错的结果。
DeepWalk算法第一次将深度学习中的技术引入到网络表示学习领域。DeepWalk算法充分利用了网络结构中的随机游走序列的信息。使用随机游走序列而不是邻接矩阵的优势有两点：首先，随机游走序列只依赖于局部信息，所以可以使用于分布式和在线系统，而使用邻接矩阵就必须把所有的信息存储于内存中处理。第二，对随机游走序列进行建模可以降低建模0-1二值邻接矩阵的方差和不确定性。
LINE算法用观察到的节点间连接刻画了第一级相似度关系，用不直接连接的两个节点的共同邻居刻画了这两个点之间的第二级相似度关系。直觉上说，对直接项链的两个节点间关系的刻画等价于对原始网络的临界矩阵的建模。但是一个网络中的边关系往往是非常稀疏的，所以有必要进一步刻画第二级相似度来考虑并不直接相连，但是共同邻居较多的节点对，从而对第一级相似度的信息给予补充。
node2vec模型是DeepWalk的扩展方法。通过改善DeepWalk模型的随机游走策略，node2vec能够生成质量更高的节点序列。具体来说，node2vec引入两个超参数p和q，来控制随机游走算法的广度和深度。通过结合BFS和DFS搜索算法，node2vec模型能够更好地对网络结构进行探索，使得网络节点表示既能够包含局部的网络结构信息，也能够包含更深层的全局的网络结构信息，从而节点表示质量更高，在节点分类任务上获得了显著的提升。
小结：基于神经网络的方法一般需要设计合适的损失函数，通过随机梯度下降算法对模型中的参数进行优化。这一类方法与基于矩阵特征向量的方法相比，往往速度更快，效率更高，在后续的网络分析中表现更好。

3.3 基于矩阵分解的方法

给定关系矩阵，对关系矩阵进行矩阵分解达到降维的效果，从而得到节点的网络表示。
GraRep算法考虑了一种特别的关系矩阵。GraRep通过SVD分解对该关系矩阵进行降维从而得到k步网络表示。形式化地，假设首先对邻接矩阵A进行归一化处理，使得矩阵A中每行的加和等于1。则GraRep算法在计算k步网络表示时分解了矩阵 $A^k$ ，该关系矩阵中的每个单元对应着两个节点间通过k步随机游走抵达的概率。但GraRep的主要缺点在于其在计算关系矩阵 $A^k$ 的时候计算效率很低。
Yang等在其后续工作中将基于矩阵分解或者可以转化为矩阵分解的方法总结成同一个算法框架：第一步构建节点间的关系矩阵，第二步对该矩阵进行矩阵分解操作得到网络表示。该工作将谱聚类方法，DeepWalk和GraRep方法第一步构建关系矩阵的过程进行了分析对比，并总结在如下表中，其中L是Laplace矩阵。

方法	矩阵	正确率	速度	效果
谱聚类	L	准确	快	低
DeepWalk	$\sum_{k=1}^{K} {\frac{A^k}{K}}$	大约	快	中
GraRep	$A^k,k=1,...,K$	准确	慢	高

通过对上表的观察，可以得出两个结论。一是对更高阶的关系矩阵 $A^k$ 的构建可以提升网络表示的效果，二是精确的计算高阶的关系矩阵 $A^k$ 计算效率很低。这两个结论促使我们寻找一种可以间接近似高阶的关系矩阵且不增加计算复杂度的方法。
Yang等提出了一种简单的网络表示更新策略NEU，如下表示：
$R_{new}=R+\lambda_1A \cdot R + \lambda_2A \cdot (A \cdot R)$
其中 $\lambda_1$ ， $\lambda_2$ 是超参数，一般设置为 $0.5$ 和 $0.25$ 。该工作证明了上式可以让更新后的网络表示近似地等价于从更高阶的关系矩阵中分解而来，而不增加计算复杂度。实际上，当该算法作用于DeepWalk算法的输出结果时，只占用DeepWalk算法1%的时间，就可以有非常显著的提升效果。

3.4 基于深层神经网络的方法

SDNE使用深层网络对节点表示间的非线性进行建模。整个模型可以被分为两个部分：一个是由Laplace矩阵监督的建模第一级相似度的模块，另一个是由无监督的深层自编码器对第二级相似度关系进行建模。最终SDNE算法将深层自编码器中间层作为节点的网络表示。

SDNE算法

3.5 基于社区发现的算法

如谱聚类算法中展示的，研究者已经考虑从社区发现角度学习网络表示。具体来说，就是让节点表示的每一维对应该节点从属于一个社区的强度，然后设计最优化目标进行求解。这类算法会学习的到上述的社区强度关系表示，然后转化为社区发现的结果。而学习社区强度关系表示的过程可以看作是无监督的非负节点表示学习的过程。
BIGCLAM作为一个可覆盖社区发现算法，为每个网络中的节点学习了一个上述的k维非负向量表示。BIGCLAM算法对网络中的每条边的生成概率进行建模：每个点的向量表示内积越大，那么这两个点之间形成边的概率就越高。算法的最大目标是整个网络结构的最大似然概率。最优化求解参数的过程由随机梯度下降算法实现。

3.6 保存特殊性质的网络表示

使用向量表示代替原始网络的策略在带来便利的同时，也会丢失很多原始网络中的信息。比如大多数网络表示学习方法使用向量表示间的内积或者余弦距离刻画节点相似度。但内积或者余弦距离都是无向的，会丢失网络中的非对称性。另一方面，一些依赖于网络结构定义的性质，如社区等信息，也会在网络表示学习的过程中丢失。
HOPE算法为每个节点刻画了两种不同的表示，并着眼于保存原始网络中的非对称性信息。HOPE构建了不同的非对称性的关系矩阵，然后使用JDGSVD算法进行矩阵降维得到节点的网络表示。
CNRL算法考虑了在节点表示中嵌入网络隐藏的社区信息。

4 结合外部信息的网络表示学习

真实世界中的网络节点往往会伴随着丰富的外部信息，例如文本信息、标签类别信息等。而传统网络表示学习主要依赖网络拓扑结构信息，而忽略了这些异质的外部信息。因此，如何能够在网络表示学习过程中，考虑这些外部信息，提高网络表示质量和增强表示向量在网络分析任务上的效果是网络表示学习领域的重要挑战。

4.1 结合文本信息的方法

在社交网络中，除去用户间的好友关系，也会有丰富的用户状态或者博客内容等文本信息。我们可以利用这些文本信息作为网络结构信息的补充，进一步增强网络节点表示的强度和效果。
TADW在矩阵分解框架下，将文本特征引入网络表示学习。TADW算法基于矩阵分解形式的DeepWalk算法进一步加强得到：将关系矩阵M分解成3个效地矩阵乘积，器中黄色矩阵T是固定的文本特征向量，两外两个矩阵是参数矩阵。TADW算法使用共轭梯度下降法迭代更新W矩阵和H矩阵求解参数。

TADW算法
真实世界中的网络节点在与其他节点进行交互时，往往会展现出不同方面的特点。然而，已有的网络表示方法会给每个网络节点学习一个固定的表示向量，不能展现处同一节点对于不同邻居节点角色变化。此外，这些方法不能对节点之间的关系进行有效的建模和解释。因此，CANE利用网络节点的文本信息对节点之间的关系进行解释，来为网络节点根据不同的邻居学习上下文相关的网络表示。
CANE假设每个节点的表示向量由文本表示向量及结构表示向量组成，其中，文本表示向量的生成过程与边上的邻居相关，所以生成的节点表示也是上下文相关的。

4.2 半监督的网络表示学习

无监督的网络表示学习中，其后续任务很多是以节点表示作为特征的节点分类任务。半监督的网络表示的想法就是把已经标注的节点的节点类别或者标签利用起来，加入到网络表示学习的过程中，从而针对性地提升节点网络表示在后续分类任务中的效果。

4.3 结合边上标签信息的网络表示学习

除了节点本身附加的文本、标签等信息外，节点与节点之间也存在着丰富的交互信息。例如，社交媒体上用户之间会存在交谈、转发等文本信息；论文合作网络中，研究者之间存在合作的论文的具体信息。然而，已有的网络表示学习模型更侧重于节点本身的信息，而把边简单地看作0，1值或者连续的实值，而忽略边上丰富的语义信息。同时，已有的网络表示学习一般采用节点分类、链接预测等网络分析任务来衡量网络表示学习的质量，而忽略了对节点之间具体关系的建模和预测能力。
为了解决关系的建模和预测问题，Tu等提出了TransNet模型，利用平移机制来解决社会关系抽取问题。

5 评测任务和应用场景

5.1 节点分类

在进行网络数据的分析时，一个最常见的场景就是对网络中的节点进行合理的划分。如，在社交网络，不同的用户可以根据他们的兴趣爱好不同分为不同的类别。类似的任务场景还有对互联网上的各个网页进行内容上的分类。

5.2 链接预测

链接预测旨在预测网络中丢失的边，或者未来可能会出现的边。在进行链接预测时，需要对所有不在训练数据中的点对打分。在表示学习中，一般使用一对节点表示的内积或者余弦相似度来计算得分。我们一般用AUC值来评价链接预测任务的结果。AUC值代表了一条未观测到的点对得分比一条不存在的点对得分高的概率。（？）

5.3 社区发现

社区发现问题旨在对网络中的节点进行无监督的聚类，从而将网络中相似的节点归为同一个社区。与节点分类任务相比，社区发现任务最主要的不同就是社区发现任务是无监督的。社区发现算法可以用来未社交网络中的用户自动划分好友的分组，为蛋白质网络中的各类蛋白质依照它们之间的联系自动分类。

6 总结与展望

现有网络表示学习方法主要依赖于静态的网络拓扑信息，而忽略了网络结构的动态性、网络中节点的异质性、节点拥有大量外部信息等。

参考文献：
涂存超, 杨成, 刘知远,等. 网络表示学习综述[J]. 中国科学:信息科学, 2017(8).