网络表示学习综述学习笔记

自然语言处理 本文总阅读量次

网络表示学习综述

将网络信息转化为低维稠密的实数向量，并用于已有的机器学习算法的输入

G=(V,E) –> Representation Learning –>Network embeddings

在网络中拓扑结构相似的节点也应该具有相近的向量表示。

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

方法 简介 优缺点
谱聚类算法 计算关系矩阵的前K个特征向量或奇异向量来得到k纬的节点表示 依赖于关系矩阵的构建，时间复杂度与空间复杂度较高
局部线性表示 一个节点与它邻居的表示都位于该流形的一个局部线性的区域. 也就是说, 一个节点的表示可以通过它的邻居节点的表示的线性组合来近似得到. 使用邻居节点表示的加权和与中心节点表示的距离作为损失函数.
最小化损失函数的优化问题最终转化成某个关系矩阵特征向

量计算问题求解. |
| Laplace 特征表 | 假设两个相连的节点的表示应该相近 | 转化为 Laplace 矩阵的特征向量计算问题. |
| 有向图表示 | 扩展了 Laplace 特征表方法, 给不同点的损失函数以不同的权重 | |
| | 模块性意味着在同一模块内节点连接紧密, 而不同模块间节点连接稀疏. | 最终该优化问题转化为了归一化的 Laplace 矩阵的特征向量计算. |

这一类方法最主要的缺点在于复杂度: 大规模矩阵的特征向量计算是非常消耗计算时间和空间。

基于简单神经网络的算法

DeepWalk算法充分利用网络结构中的随机游走序列的信息。首先在网络上采样生成大量的随机游走序列, 然后用 Skip-gram 和 Hierarchical Softmax 模东型对随机游走序列中每个局部窗口内的节点对进行概率建模, 最大化随机游走序列的似然概率, 并最终使用随机梯度下降学习参数.

  • 只依赖于局部信息，适用于分布式和在线系统
  • 1对比0-1二值邻接矩阵，方差与不确定性降低

Word2vec应用于随机游走序列

一种可以适用于大规模的有向带权图的网络表示学习算法. 为了对节点间的关系进行建模, LINE算法用观察到的节点间连接刻画了第一级相似度关系, 用不直接相连的两个节点的共同邻居刻画了这两个点之间的第二级相似度关系. 直觉上说, 对直接相连的两个节点间关系的刻画等价于对原始网络的邻接矩阵的建模. 但是一个网络中的边关系往往是非常稀疏的, 所以有必要进一步刻画第二级相似度关系来考虑

基于矩阵分解的方法

给定关系矩阵, 对关系矩阵进行矩阵分解达到降维的效果, 从而得到节点的网络表示。（DeepWalk 算法实际上等价于某个特定关系矩阵的矩阵分解）

GraRep算法

GraRep 通过 SVD 分解对该关系矩阵进行降维从而得到 k 步网络表示。对邻接矩阵 A 进行行归一化处理, 使得矩阵 A 中每行的加和等于 1. 则 GraRep 算法在计算 k 步网络表示时分解了矩阵 Ak, 该关系矩阵中的每个单元对应着两
个节点间通过 k 步的随机游走抵达的概率。

算法框架:

  1. 第一步构建节点间的关系矩阵,
  2. 第二步对该矩阵进行矩阵分解操作得到网络表示

基于社区发现的算法

让节点表示的每一维对应该节点从属于一个社区的强度, 然后设计最优化目标进行求解.

BIGCLAM 算法对网络中每条边的生成概率进行建模: 两个点的向量表示内积越大, 那么这两个点之间形成边的概率也就越高. 算法的最大化目标是整个网络结构的最大似然概率. 最优化求解参数的过程由随机梯度下降算法实现.

保存特殊性质的网络表示

大多数网络表示学习方法使用向量表示间的内积或者余弦距离刻画节点相似度. 但内积或者余弦距离都是无向的, 会丢失网络中的非对称性. 另一方面, 一些依赖于网络结构定义的性质, 如社区 (community)等信息, 也会在网络表示学习的过程中丢失。

HOPE 算法 [21] 为每个节点刻画了两种不同的表示, 并着眼于保存原始网络中的非对称性信息.构建了不同的非对称的关系矩阵, 然后使用 JDGSVD 算法进行矩阵降维得到节点的网络表示.

CNRL 算法 [22] 考虑了在节点表示中嵌入网络隐藏的社区信息. 假设每个节点属于多个社区, 也就是每个节点在所有的社区上有一个概率分布。CNRL 将网络中的社区看作文本中的主题, 也就是说, 网络中相关的节点倾向于行程社区, 而文本中相关的词则会构成主题. 因此, CNRL 算法在生成的随机游走序列上, 将每个节点序列看成一篇文档, 通过基于 Gibbs 采样的 LDA [23] 来学习每个节点的社区分布, 并通过随机采样的方式, 来给序列中的节点分配其对应的社区标签.

结合外部信息

  • 文本信息、标签分类
  • 半监督节点分类任务：一种半监督的网络表示学习方法 MMDW，会针对分类边界上的支持向量计算其偏置向量, 使其在学习过程中向正确的类别方向进行偏置, 从而增大表示向量的区分能力.
  • 结合边上的标签信息：TransNet 假设头结点表示向量加上关系表示向量等于尾节点表示向量. 其中, 通过关键词抽取、命名实体识别等方式, 对交互文本抽取出标签集合来表示关系. 随后, 通过深层自动编码器对标签集合进行压缩, 来得到关系的表示向量. 该模型能够有效地预测未标注的边上的标签集合, 在社会关系抽取任务上取得了显著的提升.
自然语言处理