薛寒生作者

网络表示学习综述:一文理解Network Embedding

本期推荐的论文笔记来自 PaperWeekly 社区用户 @xuehansheng本文是一篇来自 DeepWalk 团队的综述文章,对于近几年网络表示学习(Network Representation Learning/Network Embedding)进行了一个阶段性的总结,并对于未来的发展方向进行了研究。

关于作者:薛寒生,澳大利亚国立大学博士生,研究方向为人工智能与计算生物学。

■ 论文 | A Tutorial on Network Embeddings

■ 链接 | https://www.paperweekly.site/papers/2203

■ 作者 | Haochen Chen / Bryan Perozzi / Rami Al-Rfou / Steven Skiena

论文摘要

网络嵌入方法(Network Embedding)旨在学习网络中节点的低维度潜在表示,所学习到的特征表示可以用作基于图的各种任务的特征,例如分类,聚类,链路预测和可视化。

在本文中,通过分类和总结本研究领域的最新进展来概述网络嵌入学习相关进展。文章首先讨论网络嵌入的属性特征,并简要介绍了网络嵌入学习的历史。然后文章还讨论了在不同场景下的网络嵌入方法,如监督与无监督学习,同质网络学习嵌入与异构网络等。文章进一步论证了网络嵌入学习方法的具体应用,并总结了该领域未来的工作研究。

Network Embedding 介绍

由于信息网络可能包含数十亿个节点和边缘,因此在整个网络上执行复杂的推理过程可能会非常棘手。因此有人提出了用于解决该问题的一种方法是网络嵌入(Network Embedding)。NE 的中心思想就是找到一种映射函数,该函数将网络中的每个节点转换为低维度的潜在表示

总的来说,NE 具有如下几个特征: 

适应性(Adaptability)- 现实的网络在不断发展;新的应用算法不应该要求不断地重复学习过程。 

可扩展性(Scalability)- 真实网络本质上通常很大,因此网络嵌入算法应该能够在短时间内处理大规模网络。 

社区感知(Community aware)- 潜在表示之间的距离应表示用于评估网络的相应成员之间的相似性的度量。这就要求同质网络能够泛化。 

低维(Low dimensional)- 当标记数据稀缺时,低维模型更好地推广并加速收敛和推理。 

持续(Continuous)- 需要潜在的表示来模拟连续空间中的部分社区成员资格。 

一个典型的例子就是 DeepWalk。其学习 Zachary’s Karate network 网络中的拓扑结构信息并转换成一个二维的潜在表示(latent representation)。

Network Embedding 简史 

传统意义上的 Graph Embedding 被看成是一个降维的过程,而主要的方法包括主成分分析(PCA)和多维缩放(MDS)。所有的方法都可以理解成运用一个 n × k 的矩阵来表示原始的 n × m 矩阵,其中 k << n。

在 2000 年代早期,又提出了其他方法,如 IsoMap 和 LLE,以保持非线性流形的整体结构。总的来说,这些方法都在小型网络上提供了良好的性能。 然而这些方法的时间复杂性至少是二次的,这使得它们无法在大规模网络上运行。

另一类流行的降维技术使用可从图中导出的矩阵的光谱特性(例如,特征向量)来嵌入图的节点。拉普拉斯特征映射(Laplacian eigenmaps)通过与其k个最小非平凡特征值相关联的特征向量表示图中的每个节点。 

Deep Learning 

DeepWalk [1] 是第一个被提出来使用表示学习(或深度学习)社区的技术的网络嵌入方法。DeepWalk 通过将节点视为单词并生成短随机游走作为句子来弥补网络嵌入和单词嵌入之间的差距。然后,可以将诸如 Skip-gram 之类的神经语言模型应用于这些随机游走以获得网络嵌入。

DeepWalk 的优点可以概括为:首先其可以按需生成随机游走。由于 Skip-gram 模型也针对每个样本进行了优化,因此随机游走和 Skip-gram 的组合使 DeepWalk 成为在线算法。其次,DeepWalk 是可扩展的,生成随机游走和优化 Skip-gram 模型的过程都是高效且平凡的并行化。最重要的是,DeepWalk 引入了深度学习图形的范例

Unsupervised Network Embeddings

LINE [2] 采用广度优先搜索策略来生成上下文节点:只有距离给定节点最多两跳的节点才被视为其相邻节点。 此外,与 DeepWalk 中使用的分层 softmax 相比,它使用负采样来优化 Skip-gram 模型。 

Node2vec [3] 是 DeepWalk 的扩展,它引入了一个偏向的随机步行程序,结合了 BFS 风格和 DFS 风格的邻域探索。

Walklets [4] 显示 DeepWalk 从 A~1~,A~2~,···,A~k~ 的加权组合中学习网络嵌入。 特别是如果 i<j,DeepWalk 总是偏向于 A~i~ 而不是 A~j~。为了避免上述缺点,Walklets 建议从 A~1~,A~2~,···,A~k~ 中学习多尺度网络嵌入。由于计算 A~i~ 的时间复杂度至少是网络中节点数量的二次方,因此 Walklet 通过在短随机游走中跳过节点来近似 A~i~。它进一步学习来自 A 的不同权力的网络嵌入,以不同的粒度捕获网络的结构信息。 

GraRep [5] 类似地通过将图形邻接矩阵提升到不同的幂来利用不同尺度的节点共现信息。将奇异值分解(SVD)应用于邻接矩阵的幂以获得节点的低维表示。

Walklet 和 GraRep之间存在两个主要差异。首先,GraRep 计算 A~i~ 的确切内容,而 Walklets 接近它。其次,GraRep 采用 SVD 来获得具有精确分解的节点嵌入,而 Walklet 使用 Skip-gram 模型。

有趣的是,Levy 和 Goldberg 证明带负抽样的跳过法(SGNS)隐含地将节点和各个上下文节点之间的 PMI 矩阵分解。总而言之,GraRep 使用噪声较小的过程生成网络嵌入,但 Walklet 证明更具可扩展性。 

GraphAttention [6] 提出了一种 attention 模型,它可以学习多尺度表示,最好地预测原始图中的链接。GraphAttention 不是预先确定参数来控制上下文节点分布,而是自动学习对图转换矩阵的幂集的 attention。 

SDNE [7] 学习节点表示,通过深度自动编码器保持 2 跳邻居之间的接近度。它通过最小化它们的表示之间的欧几里德距离来进一步保持相邻节点之间的接近度。 

DNGR [8] 是另一种基于深度神经网络的学习网络嵌入的方法。他们采用随机冲浪策略来捕获图形结构信息。他们进一步将这些结构信息转换为 PPMI 矩阵,并训练堆叠去噪自动编码器(SDAE)以嵌入节点。

Attributed Network Embeddings

上述无监督网络嵌入方法仅利用网络结构信息来获得低维度的网络特征。但是现实世界网络中的节点和边缘通常与附加特征相关联,这些特征称为属性(attribute)。例如在诸如 Twitter 的社交网络站点中,用户(节点)发布的文本内容是可用的。因此期望网络嵌入方法还从节点属性和边缘属性中的丰富内容中学习。 

TADW [9] 研究节点与文本特征相关联的情况。TADW 的作者首先证明了 DeepWalk 实质上是将转移概率矩阵 M 分解为两个低维矩阵。受此结果的启发,TADW 包含文本特征矩阵 T 通过将 M 分解为 W,H 和 T 的乘积,进入矩阵分解过程。最后,将 W 和 H×T 连接起来作为节点的潜在表示。 

CENE [10] 是一种网络嵌入方法,它共同模拟节点中的网络结构和文本内容。CENE 将文本内容视为特殊类型的节点,并利用节点-节点链接和节点内容链接进行节点嵌入。 优化目标是共同最小化两种类型链路的损失。 

HSCA [11] 是一种归因图的网络嵌入方法,它同时模拟同音,网络拓扑结构和节点特征。 

Maxmargin DeepWalk(MMDW)[12] 是一种半监督方法,它学习部分标记网络中的节点表示。MMDW 由两部分组成:第一部分是基于矩阵分解的节点嵌入模型,第二部分是将学习的表示作为特征来训练标记节点上的最大边缘 SVM 分类器。通过引入偏置梯度,可以联合更新两个部分中的参数

Heterogeneous Network Embeddings

异构网络具有多类节点或边缘。为了模拟不同类型的节点和边缘,大多数异构网络嵌入方法通过联合最小化每种模态的损失来学习节点嵌入。这些方法要么直接在相同的潜在空间中学习所有节点嵌入,要么事先为每个模态构建嵌入,然后将它们映射到相同的潜在空间。 

Chang [13] 提出了异构网络的深度嵌入框架。他们的模型首先为每种模态(如图像,文本)构建一个特征表示,然后将不同模态的嵌入映射到同一个嵌入空间。优化目标是最大化链接节点的嵌入之间的相似性,同时最小化未链接节点的嵌入。注意,边可以在相同模态内的两个节点之间以及来自不同模态的节点之间。 

Zhao [14] 是另一种用于在异构网络中构造节点表示的框架。具体来说,他们认为维基百科网络有三种类型的节点:实体,单词和类别。建立相同和不同类型节点之间的共现矩阵,并且使用坐标矩阵分解从所有矩阵联合学习实体,词和类别的表示。 

Li [15] 提出了一种神经网络模型,用于学习异构社交网络中的用户表示。他们的方法联合模拟用户生成的文本,用户网络和用户与用户属性之间的多方面关系。 

HEBE [16] 是一种嵌入大规模异构事件网络的算法,其中事件被定义为网络中一组节点(可能是不同类型)之间的交互。虽然先前的工作将事件分解为事件中涉及的每对节点之间的成对交互,但 HEBE 将整个事件视为超边界并同时保留所有参与节点之间的接近度。

具体而言,对于超边缘中的每个节点,HEBE 将其视为目标节点,并将超边界中的其余节点视为上下文节点。因此,基础优化目标是在给定所有上下文节点的情况下预测目标节点。 

EOE [17] 是用于耦合异构网络的网络嵌入方法,其中两个同构网络与网络间边缘连接。EOE 学习两个网络的潜在节点表示,并利用和谐嵌入矩阵将不同网络的表示转换为相同的空间。 

Metapath2vec [18] 是 DeepWalk 的扩展,适用于异构网络。为了构建随机漫游,Metapath2vec 使用基于元路径的漫游来捕获不同类型节点之间的关系。对于来自随机游走序列的学习表示,他们提出异构 Skip-gram,其在模型优化期间考虑节点类型信息。

总结

该 Network Embedding 综述文章较为系统地阐述了目前 NE 的发展现状,并从 Unsupervised Network Embeddings, Attributed Network Embeddings 和 Heterogeneous Network Embeddings 等几个部分进行了介绍。本笔记主要着重于介绍现有的一系列方法,对于其在不同场景的应用不做详细阐述。

PaperWeekly
PaperWeekly

推荐、解读、讨论和报道人工智能前沿论文成果的学术平台。

入门网络表示学习
141
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

自动编码器技术

自动编码器是用于无监督学习高效编码的人工神经网络。 自动编码器的目的是学习一组数据的表示(编码),通常用于降维。 最近,自动编码器已经越来越广泛地用于生成模型的训练。

广度优先搜索技术

广度优先搜索算法(英语:Breadth-First-Search,缩写为BFS),又译作宽度优先搜索,或横向优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。广度优先搜索的实现一般采用open-closed表。

感知技术

知觉或感知是外界刺激作用于感官时,脑对外界的整体的看法和理解,为我们对外界的感官信息进行组织和解释。在认知科学中,也可看作一组程序,包括获取信息、理解信息、筛选信息、组织信息。与感觉不同,知觉反映的是由对象的各样属性及关系构成的整体。

词嵌入技术

词嵌入是自然语言处理(NLP)中语言模型与表征学习技术的统称。概念上而言,它是指把一个维数为所有词的数量的高维空间嵌入到一个维数低得多的连续向量空间中,每个单词或词组被映射为实数域上的向量。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

时间复杂度技术

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

奇异值分解技术

类似于特征分解将矩阵分解成特征向量和特征值,奇异值分解(singular value decomposition, SVD)将矩阵分解为奇异向量(singular vector)和奇异值(singular value)。通过分解矩阵,我们可以发现矩阵表示成数组元素时不明显的函数性质。而相比较特征分解,奇异值分解有着更为广泛的应用,这是因为每个实数矩阵都有一个奇异值分解,但未必都有特征分解。例如,非方阵型矩阵没有特征分解,这时只能使用奇异值分解。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

监督学习技术

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

降维技术

降维算法是将 p+1 个系数的问题简化为 M+1 个系数的问题,其中 M<p。算法执行包括计算变量的 M 个不同线性组合或投射(projection)。然后这 M 个投射作为预测器通过最小二乘法拟合一个线性回归模型。两个主要的方法是主成分回归(principal component regression)和偏最小二乘法(partial least squares)。

主成分分析技术

在多元统计分析中,主成分分析(Principal components analysis,PCA)是一种分析、简化数据集的技术。主成分分析经常用于减少数据集的维数,同时保持数据集中的对方差贡献最大的特征。这是通过保留低阶主成分,忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面。但是,这也不是一定的,要视具体应用而定。由于主成分分析依赖所给数据,所以数据的准确性对分析结果影响很大。

神经语言模型技术

语言模型是估计单词序列的联合概率函数,比如给一个长度为m的单词序列,通过使用语言模型,可以获得这m个单词分布的概率P(W1,...,Wm)。对于许多的自然语言处理的应用,可以估计不同短语的概率是极具应用价值的。语言模型可以应用于语音识别,机器翻译,语音标记,解析,手写识别,信息检索等领域。

堆叠技术

堆叠泛化是一种用于最小化一个或多个泛化器的泛化误差率的方法。它通过推导泛化器相对于所提供的学习集的偏差来发挥其作用。这个推导的过程包括:在第二层中将第一层的原始泛化器对部分学习集的猜测进行泛化,以及尝试对学习集的剩余部分进行猜测,并且输出正确的结果。当与多个泛化器一起使用时,堆叠泛化可以被看作是一个交叉验证的复杂版本,利用比交叉验证更为复杂的策略来组合各个泛化器。当与单个泛化器一起使用时,堆叠泛化是一种用于估计(然后纠正)泛化器的错误的方法,该泛化器已经在特定学习集上进行了训练并被询问了特定问题。

推荐文章
2018年ACM CSUR综述文章“Spatio-Temporal Data Mining: A Survey of Problems and Methods”中提到三篇Network-based representations文章,可关注 1. Cross-species analysis of biological networks by Bayesian alignment. PNAS 2006, 103, 29, 10967–10972. 2. Comparing networks from a data analysis perspective. In CCS. Springer, 2009, 1907–1916. 3.S. Soundarajan et al. 2013. Which network similarity measure should you choose: an empirical study. In Workshop on Information in Networks, New York, USA.