原文链接：https://dl.acm.org/doi/abs/10.5555/3015812.3015982

会议：AAAI‘16 （CCF A类）

年度：2016

本文提出了一种新的学习图表示模型

通过捕获模型图结构信息生成每个顶点的低维向量表示

与以往的研究不同，我们使用它随机冲浪模型（ random surfing model）直接获取图结构信息而不是使用Perozzi等人(2014)提出基于抽样的方法生成线性序列

在许多实际问题中，图形是信息管理的常见表达

例如，在蛋白质网络的研究中 从蛋白质-蛋白质相互作用网络中挖掘蛋白质复合物对描述同源蛋白的功能多样性和有价值的进化有重要作用，本质上是一个聚类问题

开发自动算法来从图表中提取有用的深度信息是至关重要的

组织这些与潜在些与潜在大型复杂图相关的信息的有效方法之一

它为图纸的每个顶点分配一个低维密集向量来表示编码图传递的有意义的信息

最近，人们对学习嵌入词汇产生了浓厚的兴趣(Bullinaria和Levy 2007;Mikolov等人2013)

他们的目标是从大量的自然语言文本中学习每个基于上下文的自然语言单词的低维向量

这些作品可以看作是线性序列的学习表征，因为语料库由线性结构组成，线性结构是自然语言单词序列

由此产生的紧凑和低维向量被认为可以捕获丰富的语义信息，并被证明对各种自然语言处理任务有用

虽然已经确定了学习线性结构的有效有效方法(Mikolov et al. 2013;Pennington, Socher和Manning 2014)处理拓扑结构丰富的一般图结构比较复杂

因此，一种自然的方法是确定有效的方法，将学习一般图结构顶点表示的任务转化为线性结构学习表示的任务

Perozzi等人(2014)提出eepWalk通过一种叫做截断随机行走的均匀抽样方法，将未加权图转换为线性序列的集合

• 在他们的方法中，采样顶点序列表示图中顶点之间的连接，可以理解为将一般图结构转换为大量线性结构集合的过程
• 接下来，他们用Mikolov等人(2013)提出的跳跃图模型(skip-gram model)从这种线性结构中学习顶点的低维表示
• 在某些任务中，学任务中被证明是有效的，优于以前的方法，如谱聚类和模块化方法(Tang和Liu 2009a;2009 b;2011;2003年的Macskassy和Provost)。

虽然这种学习非加权图顶点的方法是有效的，但仍有两个重要的问题需要回答

• 1)首先，如何更准确、更直接地获取加权图的图结构信息？
• 2)第二，是否有更好的方法来表示线性结构的顶点？

回答第一个问题

• 我们设计了一个适合加权图的随机冲浪模型，它可以直接产生概率共生矩阵
• 这种矩阵类似于从图形中采样线性序列获得的共并发矩阵(Bullinaria和Levy 2007)，但我们的方法不需要采样过程

回答第二个问题

• 首先，让我们回顾一种流行的学习线性结构顶点的方法
• Levy和Goldberg(2014)最近的一项研究表明，与跳跃图相关的目标函数图相关的目标函数(Mikolov2013年等人上下文的移位点互信息(PPMI)矩阵有内在联系
• 具体来说，他们展示了分解标准奇异值(SV)方法对PPMI矩阵分解可以从分解后的矩阵中总结出顶点/单词表示

最新方法：GraRep (Cao, Lu, and Xu 2015年)，已被证明在学习图所示的任务中取得了良好的经验

然而，该方法采用奇异值分解(SV)没有探索出更好的非线性降维技术

在这篇文章中，我们给了它Levy和Goldberg(2014)工作提供了新的视角

我们认为原始PPMI矩阵本身就是图的显式表示矩阵，SV步骤本质上起着降维工具箱的作用

虽然SV步骤诱导最终的单词表征被证明是有效的，Levy等人(2015)也证明了使用PPMI矩阵本身作为单词表征的有效性

有趣的是，正如作者所示，从SV学习方法的表达不能完全超过PPMI表示矩阵本身(Levy, Goldberg, and agan 2015)

因为我们的最终目标是学习好的顶点，有效地捕捉图片的信息

研究从PPMI最好在矩阵中恢复顶点法是至关重要的，在这里可以捕获不同顶点之间潜在的复杂、非线性关系

深度学习照亮了非线性复杂现象建模的道路，在不同的领域有许多成功的应用，如语音识别(ahl et al. 2012)和计算机视觉

深度神经网络(NN)，例如自编码器是一种从低级特征学习高级抽象的有效方法

这个过程本质上执行降维，将数据从高维空间映射到低维空间

与基于(截断)svd的降维方法(通过线性投影从原始表示空间映射到一个低秩的新空间)不同，深度神经网络(如堆叠自编码器)可以学习高度非线性的投影

事实上，Tian et al.(2014)最近的一项工作在聚类任务中使用稀疏自编码器代替光谱聚类的特征值分解步骤，取得了显著的改进

在他们工作的激励下，我们还研究了使用基于深度学习的替代方法从原始数据表示学习低维表示的有效性

与他们的工作不同，我们的目标是学习一般图的顶点表示，而不是专门关注聚类任务。

我们将深度学习方法应用于PPMI矩阵，而不是他们模型中使用的拉普拉斯矩阵

前者已被证明具有产生比后者更好的表现的潜力

为了增强我们模型的鲁棒性，我们还使用了堆叠去噪自编码器来学习多层表示

我们将我们提出的模型称为NGR(用于图表示的深度神经网络)

学习到的表示可以被视为输入特征，可以输入到其他任务中，如无监督聚类和监督分类任务

为了验证我们模型的有效性，我们进行了实验，将学习到的表示用于一系列不同的任务，其中考虑了现实世界中不同类型和拓扑的网络

为了进一步证明我们的模型在考虑更简单、更大规模的实际图结构时的有效性，我们将我们的算法应用于一个非常大的语言数据集，并在单词相似任务上进行了实验

在所有这些任务中，我们的模型在学习图表示方面优于其他方法，而且我们的模型也可以并行化

我们的主要贡献有两方面:

• 从理论上讲，我们认为深度神经网络的优势在于能够捕获图所传达的非线性信息，而传统的线性降维方法不能很容易地捕获这些信息。此外，我们认为我们的随机冲浪模型可以用来取代广泛使用的传统的基于抽样的方法来收集图表信息。
• 经验上，我们证明了我们的新模型能够更好地学习加权图的低维顶点表示，其中有意义的语义，关系和结构信息的图可以被捕获。我们展示了结果表示可以有效地用作不同下游任务的特征。

在本节中，我们

• 首先展示了一个在eepWalk中提出的无权重图的随机抽样，以说明将顶点表示转换为线性表示的可行性
• 接下来，我们考虑两种词表示方法:带负采样的跳跃图和基于PPMI矩阵的矩阵分解。这些方法可以被视为从线性结构数据学习词汇表征的线性方法。

Notation

G = ( V , E ) G = (V, E) G=(V,E)

• V V V:顶点集合

• E E E: 边集合

• 在一个未加权的图中，边权表示两个顶点之间是否存在关系，因此是二值关系

• 相反，加权图中的边权是表示两个顶点之间关联程度的实数。虽然加权图中的边权可以是负的，但本文只考虑非负权

为了便于标记，我们在本文中还使用 w w w和 c c c来表示顶点

我们试图通过捕获深度结构信息来获得一个表示图 G G G顶点的矩阵 R R R（R即是我们需要求到嵌入）

eepWalk提供了一种截断随机漫步的有效方法，将未加权的图结构信息转化为表示图顶点之间关系的线性序列

所提出的随机游走是一种均匀抽样方法，适用于非加权图

• 他们首先从图中随机选择一个顶点 v 1 v_1 v1​，并将其标记为当前顶点
• 然后从当前顶点 v 1 v_1 v1​的所有邻居中随机选择下一个顶点 v 2 v_2 v2​
• 现在，他们将这个新选择的顶点 v 2 v_2 v2​标记为当前顶点，并重复这样的顶点采样过程
• 当一个序列内的顶点数达到一个预先设定的值，即步行长度 η η η时，算法终止
• 重复上述过程 γ γ γ次(称为总行走)后，收集线性序列块

截断随机游动是利用线性序列表达非加权图结构信息的一种有效方法，但其采样过程较慢，且超参数 η η η和 γ γ γ不易确定

我们注意到，eepWalk生成了一个基于采样线性序列的共现矩阵。

简要介绍了一下eepWalk

在第三节中，我们描述了我们的随机冲浪模型，该模型直接从一个加权图构造一个概率共现矩阵，从而避免了昂贵的抽样过程

自然语言语料库由线性序列的词流组成

近年来，神经嵌入方法和基于矩阵分解的方法在词汇表征学习中得到了广泛的应用。

在(Mikolov et al. 2013)中提出的跳跃图模型已经被证明是学习单词表征的一种有效和高效的方法

两种值得注意的改进跳跃图模型的方法是

• 负采样(SGNS)
• 分层softmax

在本文中，我们选择使用前一种方法：负采样(SGNS)

在SGNS中，噪声对比估计(NCE)方法的简化变体(Gutmann和Hyv̈arinen 2012;采用Mnih和Teh 2012)来增强跳跃图模型的稳健性

SGNS从经验的单字母单词分布中随机创建负对 ( w , c N ) (w, c_N) (w,cN​)，并尝试使用低维向量表示每个单词 w ∈ V w∈V w∈V和上下文单词 c ∈ V c∈V c∈V对

SGNS的目标函数是使正对 ( w , c ) (w, c) (w,c)最大，负对 ( w , c N ) (w, c_N) (w,cN​)最小

式中

• σ ( ⋅ ) σ(·) σ(⋅)为 σ ( x ) = ( 1 + e − x ) − 1 σ(x) = (1 +e^{−x})^{−1} σ(x)=(1+e−x)−1的sigmoid函数
• λ λ λ为负样本数。 E c N ∼ p [ ⋅ ] E_{c_N \sim p_}[·] EcN​∼p​​[⋅]是负采样 c N c_N cN​得到的实例符合分布 p = # ( c ) ∣ ∣ p = \frac{\#(c)}{||} p=∣∣#(c)​ (单数c在数据集中的分布)时的期望

介绍Skip-gram模型（采用负采样）

学习图形表示(尤其是单词表示)的另一种方法是基于矩阵因式分解技术

这些方法基于全局共现计数的统计来学习表示，并且在某些预测任务中可以优于基于单独局部上下文窗口的神经网络方法

矩阵因式分解方法的一个例子是超空间类比分析(Lund And Burgess 1996)，

• 它因式分解词-词共现矩阵以产生词表示
• 这种方法和相关方法的主要缺点是：具有相对较少语义值的频繁词(例如，停用词)对所生成的词表示具有不成比例的影响

丘奇和汉克斯的逐点互信息(PMI)矩阵就是为了解决这个问题而提出的，此后被证明提供了更好的单词表示

改进性能的一种常见方法是将每个负值赋给0，这在(Levy和Goldberg 2014)中有详细说明，以形成PPMI矩阵

PMI矩阵 → \rightarrow → PPMI矩阵

虽然PPMI矩阵是高维矩阵，但使用截断奇异值分解方法进行降维会产生关于 L 2 L_2 L2​损失的最优秩因式分解

我们假设矩阵 X X X可以分解成三个矩阵 U Σ V T UΣV^T UΣVT

• U U U和 V V V是正交阵
• Σ Σ Σ是对角阵

换句话说：

这里

• U d U_d Ud​和 V d V_d Vd​是对应于前 d d d个奇异值(在 Σ d Σ_d Σd​中)的 U U U和 V V V的左侧 d d d列

根据Levy等人的说法。(2015)，字表示矩阵 R R R可以是：

PPMI矩阵 X X X是单词表示矩阵和上下文矩阵的乘积

奇异值分解（SV）过程提供了一种从矩阵 X X X中寻找矩阵 R R R的方法，其中

• R R R的行向量是词/顶点的低维表示，可以通过 X X X给出的高维表示的线性投影来获得

我们认为这样的投影不一定是线性投影

在这项工作中，我们研究了通过使用深度神经网络来使用非线性投影方法来代替线性奇异值分解方法

深度神经网络可以用来学习多层次的特征表示，已经在不同的领域取得了成功的结果

训练这样的网络被证明是困难的，一个有效的解决方案，在(Hinton和Salakhutdinov，2006；Bengio et al.2007)，是采用贪婪的分层无监督预训练

这一策略旨在一次学习每一层的有用表示法，旨在一次学习每一层的有用表示法

然后，将学习到的低级表示作为输入馈送到下一层，用于随后的表示学习

神经网络通常使用诸如Sigmoid或tanh之类的非线性激活函数来捕捉从输入到输出的复杂的、非线性的投影

为了训练涉及多层特征表示的深层体系结构，自动编码器已成为常用的构建块之一自动编码器执行两个动作–编码步骤，然后是解码步骤。

略（AE的内容暂略）

堆叠式自动编码器是由多层这样的自动编码器组成的多层深度神经网络

堆叠式自动编码器使用逐层训练方法来提取基本规则，这些规则逐层地从数据中捕获不同级别的抽象，其中较高层传达来自数据的较高级别的抽象

如图1所示，该模型由三个主要步骤组成

• 首先，引入随机冲浪模型来捕获图结构信息，并生成一个概率共现矩阵
• 接下来，我们根据概率共现矩阵计算PPMI矩阵(见第2.3节)
• 之后，一个堆叠的去噪自编码器(第3.2节)用来学习低维顶点表示

将图结构转换为线性序列的抽样方法虽然有效，但也存在一些缺点:

• 首先，采样序列具有有限的长度。这使得在采样序列边界处出现的顶点很难获得正确的上下文信息
• 其次，确定某些超参数如步长 η η η和总步长 γ γ γ并不简单，特别是对于大型图

为了解决这些问题，我们考虑使用一个随机冲浪模型

该模型是由用于任务排名的PageRank模型激发的

我们首先在一个图中随机排列顶点

假设当前的顶点是第 i i i个顶点，有一个转换矩阵 A A A来捕捉不同顶点之间的转换概率

我们引入了一个行向量 p k p_k pk​

• 它的第 j j j个元素表示经过 k k k步跃迁后到达第 j j j个顶点的概率
• p 0 p_0 p0​是第 i i i个元素的值为1，其他元素都为0的初始1-hot向量

我们考虑一个有重新开始的随机冲浪模型:

• 在每一个时间点，有一个随机冲浪过程继续的概率 α α α
• 有一个随机冲浪过程返回到原始顶点并重新开始的概率 1 − α 1−α 1−α

这就得到了如下的递归关系:

如果我们假设在这个过程中没有随机重启，那么经过恰好 k k k步的转换后到达不同顶点的概率如下所示:

相当于此时 α = 1 \alpha = 1 α=1

直观地说，两个顶点之间的距离越近，它们之间的关系就应该越亲密

因此，根据上下文节点与当前节点的相对距离来衡量其重要性是合理的

这种加权策略在word2vec和GloVe 中都得到了实施，并被发现对于实现良好的实证结果很重要

基于这一事实，我们可以看到，理想情况下，第 i i i个顶点的表示应该按照以下方式构建:

• W ( ⋅ ) W(·) W(⋅)为递减函数，即 W ( t + 1 ) < W ( t ) W (t + 1) < W (t) W(t+1)<W(t)

理想状态时

我们认为，以下基于上述随机冲浪过程的顶点表示构造方法实际上满足上述条件:

实际的情况

其实可以证明我们有以下几点:

其中 p 0 ∗ = p 0 p^∗_0 = p_0 p0∗​=p0​， p t ∗ p^*_t pt∗​在 r r r中的系数是

• w ( t ) w(t) w(t)是 α < 1 α < 1 α<1的递减函数

而跳跃图中的权重函数可以描述为

GloVe中的权重函数为:

从图2可以看出，所有的权函数都是单调递减函数 与word2vec和GloVe类似，我们的模型还允许根据上下文信息到目标的距离来进行不同的加权

这在之前被证明对于构建良好的单词表示是重要的

我们旨在研究从PPMI矩阵中构建高质量的低维向量表示，以传达图的基本结构信息

SV（奇异值分解）过程虽然有效，但本质上只产生从PPMI矩阵所包含的向量表示到最终的低维顶点向量表示的线性变换

我们认为在这两个向量空间之间可以建立潜在的非线性映射

因此，我们使用堆栈去噪自编码器(深度学习中常用的一种模型)，从原始的高维顶点向量生成压缩的低维向量

如表1所示，我们首先初始化神经网络的参数，然后使用贪婪分层训练策略学习每一层的高层抽象

为了增强NN的鲁棒性，我们使用了堆叠去噪自编码器(SAE)

与传统的自动编码器不同，在进行训练步骤之前，去噪自动编码器会部分破坏输入数据

• 具体地说，我们随机破坏每个输入样本 x x x(一个向量)，以一定的概率将向量中的一些条目赋值为0

这种想法类似于矩阵完成任务中的缺失条目建模，其目标是利用数据矩阵中的规律性，在特定的假设下有效地恢复完整的矩阵

在如图1所示的SAE结构中