前言

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
自我介绍 ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力????
 

知其然 知其所以然！

 
本文仅记录自己感兴趣的内容

简介

原文链接：https://dl.acm.org/doi/fullHtml/10.1145/3178876.3186120

会议：WWW '18: Proceedings of The Web Conference 2018 （CCF A类）

代码：https://github.com/xgfs/verse

年度：2018

ABSTRACT

将网络规模的信息网络嵌入到低维向量空间中，可以促进链接预测、分类和可视化等任务

过去的研究解决了通过从单词到图表的方法提取这种嵌入的问题，但没有定义一个明确的可理解的图表相关目标

然而，正如我们所展示的，在过去的工作中使用的目标隐式地利用了图节点之间的相似性度量

---

我们提出了顶点相似度嵌入(VERSE)，一个简单、通用和内存高效的方法，它派生出显式校准的图嵌入，以保持选定的顶点到顶点相似度度量的分布

VERSE通过训练单层神经网络来学习这种嵌入

虽然其默认的可伸缩版本是通过采样相似性信息来实现的，但我们也开发了一个使用每个顶点的完整信息的变体

我们在标准基准和真实数据集上的实验研究表明，以不同的相似性度量实例化的VERSE在主要数据挖掘任务中的精确度和召回率方面优于最先进的方法，并在时间和空间效率方面取代了它们，而可伸缩的基于采样的变体与不可伸缩的完全变体取得了同样好的结果

1 INTRODUCTION

图表数据自然出现在许多领域，包括社交网络、蛋白质网络和web

在过去的几年里，许多图挖掘技术被提出来分析和探索这样的真实网络

通常，这类技术应用机器学习来解决诸如节点分类、链路预测、异常检测和节点聚类等任务

---

机器学习算法需要一组富有表现力的判别特征来表征图节点和边

为此，可以使用表示节点[18]之间相似性的特性

然而，特性工程是一项乏味的工作，其结果不能很好地跨任务[15]进行转换

特征设计的另一种选择是学习特征向量，或通过解决无监督的优化问题来嵌入

然而，为学习表示设计和解决一个通用的、可处理的优化问题经受了研究的努力

一项研究[11,42]将经典的降维方法(如SVD)应用于图上的相似性矩阵;
然而，这些方法在构造矩阵方面负担过重
虽然最近的方法[33]克服了这一障碍，但由于其线性特性，导致预测任务的质量较差

另一个研究方向是生成捕捉邻域局部性的特征，通常通过一个可以通过随机梯度下降(SGD)优化的目标[37,41]

这种方法依赖于一个隐含的(尽管是刚性的)节点邻域概念;

然而，这种一刀切的方法无法应对现实世界网络和应用程序的多样性

格罗弗等人，[15]看出了local邻里概念的这种不灵活;为了改进它，他们提出了Node2vec，使用两个超参数对[37]的探索策略进行偏置

然而，这种超参数调优的方法增加了三次最坏情况空间复杂度，并迫使用户遍历多个特性集，并衡量在下游任务中获得最佳性能的特性集

此外，即使通过超参数调优找到一个局部邻域，它仍然只代表一个基于局部的特征类

因此，Node2vec没有充分摆脱它试图修补的刚性

---

我们认为，使用比局部邻域更通用的相似度概念提取特征，可以灵活地解决大量图数据中不同的数据挖掘任务

图1通过在一个图上展示三种不同的相似性，为这种通用的相似性概念提供了一个例子:

• 社区结构指导社区检测任务
• 角色通常用于分类
• 而结构等价定义了知识图中的对等关系

由于现实世界的任务依赖于这些属性的混合

一个多功能的特征学习算法应该能够捕获所有这些相似性

---

在这篇文章中，我们提出了VERSE，这是我们所知的第一种通用的图嵌入方法，它明确地学习节点之间的任何相似性度量

在它的学习核心中，VERSE站在深度学习方法[12,48]和直接分解相似矩阵[11,42]之间

相反，VERSE训练一个简单而富有表现力的单层神经网络来重建节点之间的相似性分布

因此，在各种大型真实网络和任务上，它在运行时和质量方面都优于以前的方法

---

由于能够为手头的任务选择任何适当的相似度量，VERSE可以在不改变核心的情况下适应该任务

因此，它充分改善了[15]中观察到的刚性，并将表示学习与特征工程集成在一起:任何相似度量，包括特征工程中开发的相似度量，都可以作为VERSE的输入

为了说明问题，我们使用三个流行的相似度量来实例化我们的通用方法，分别是个性化PageRank (PPR)[34]、SimRank[21]和邻接相似度

我们还表明，通用性并不意味着给用户带来新的负担，只是用相似度量调优替代超参数调优

使用PPR作为相似度量的默认选择，可以在我们研究的几乎所有任务和网络中获得良好的性能

---

我们总结我们的贡献如下。

• 我们提出了一个通用的图嵌入框架，它明确地学习每个图顶点的任何顶点相似性度量的分布
• 我们通过我们的相似性框架来解释之前的图嵌入，并使用个性化PageRank、SimRank和邻接相似性实例化VERSE
• 我们设计了一个有效的算法，线性图大小，基于单层神经网络最小化从真实的相似性分布到重构的发散
• 在一个彻底的实验评估中，我们表明，versev在各种图挖掘任务中的质量优于最先进的方法，同时更高效

2 RELATED WORK

在缺乏图的通用表示的情况下，图分析任务需要领域专家来制作特征[4,18]或使用专门的特征选择算法[36,40]

最近，人们引入了专门的方法来学习不同图部分[2,31]和在节点[20,55]或边[19,49]上有标注的图的表示

我们专注于学习除了图结构之外没有任何先验或额外信息的图中节点的表示

---

传统的特征学习通过将拉普拉斯矩阵或邻接矩阵等表示压缩到低维空间来学习特征

该领域的早期工作包括光谱技术[6]和非线性降维[39,44]

在另一种思路中，边际费雪分析[51]分析点数据集的维数降维，作为捕获其统计和几何属性的图的嵌入

这种方法不能应用于大型图，因为它们操作的是密集矩阵

为了克服这一限制，已经做出了一些努力，使用增强的线性代数工具

• Ahmed等[3]采用随机梯度优化快速邻接矩阵特征分解
• Ou等人[33]利用稀疏广义SVD从一个易于分解为两个稀疏邻近矩阵的相似矩阵生成一个图嵌入HOPE
  • HOPE是第一个支持不同相似性度量的;但它仍然需要整个图矩阵作为输入，将问题视为线性降维问题，而不是非线性学习问题
  • 这样，它不仅偏离了当前关于图嵌入的研究，而且也偏离了以前的工作[51]

---

表示学习的神经网络方法

机器学习的进步已经导致采用神经方法来学习表示[7]

基于深度学习在图像处理[24]和自然语言处理(Natural Language processing, NLP)等领域的成功[8,29,35]

• word2vec[29]通过训练单层神经网络来猜测文本中给定单词的上下文单词，从而构建单词嵌入
• 同样，GloVe[35]通过变换后的同现矩阵中的随机SVD来学习单词空间。虽然这种基于文本的方法固有地考虑到邻居关系，但它们需要对模型图[37]进行概念上的调整

神经网络图嵌入

神经词嵌入的成功激发了对学习图表示的自然扩展[11,12,15,37,46,48]

• DeepWalk[37]首先提出利用局部节点邻域学习低维向量空间中的潜在表示。它从每个顶点运行一系列固定长度的随机游走，并使用[29]的SkipGram算法创建一个d维顶点表示矩阵。这些表示最大化了在随机游走中观察到相邻顶点的后验概率。DeepWalk嵌入可以使用简单的线性分类器(如逻辑回归)来通知分类任务。
• GraRep[11]建议对对数变换的不同阶DeepWalk转移概率矩阵进行奇异值分解(Singular Value Decomposition, SVD)，然后将得到的表示形式串联起来
• Struc2vec[38]重新连接图，以反映节点之间的同构性，并捕获结构相似性，然后依靠DeepWalk核心获得嵌入
• 像[12,48]这样的作品研究了图嵌入的深度学习方法。他们的结果相当于复杂的模型，需要精细的参数调优和计算昂贵的优化，导致时间和空间的复杂性不适合大型图。

然而，所有基于deepwalk的方法都使用了不适合图结构的目标函数

一些作品[15,38,41]试图将图形原生原则注入到学习过程中

• LINE[41]提出了捕获更精细的接近概念的图嵌入。然而，即使是LINE的邻近性概念也局限于每个节点的邻近区域;这不足以捕获节点关系的完整面板[15,33,38]
• 此外，Node2vec[15]引入了两个超参数来调节随机游走的生成，从而以半监督的方式将学习过程定制到身边的图上。然而，Node2vec仍然以保存本地邻域为目标，需要对每个数据集和每个任务进行费力的调优

表1概述了图嵌入的五个理想属性，以及以前的方法拥有这些属性的程度

我们区分了算法的性质

一方面，那些节点之间的任何隐式或显式相似度量的方法可能表示

另一方面

• 局部:不需要整个图矩阵作为输入;GraRep,DNGR和HOPE在这方面失败了
• 可扩展:能够在一天内处理超过106个节点的图;有些方法由于密集矩阵(GraRep)、深度学习计算(SDNE)或两者兼有(DNGR)而不能满足这一标准
• 非线性:采用非线性变换;HOPE依赖于线性降维方法SVD;这不利于它在构建图表示上的性能，就像线性降维方法在一般的[26]中不能赋予其非线性对应方法的优势一样
• 全局:能够建模任何一对节点之间的关系;LINE和SDNE不共享这个属性，因为它们不能看到节点的近邻以外的地方
• 通用性:支持多种相似功能;HOPE做到了这一点，但它的线性特性让它妥协了

3 VERSATILE GRAPH EMBEDDING

VERSE拥有我们的分类法中提到的所有属性

• 它采用非线性变换，适合降维[26]
• 就每个节点所需的输入而言，它是局部的，但就输入的潜在来源而言，它是全局的
• 它是可扩展的，因为它是基于抽样，并由于其通用性而多才多艺（Versatile）

3.1 VERSE Objective

给定一个图$G=(V,E)$，

• $V=(v_1，\dots ，v_n)，n=|V|$，是顶点集合
• $E\subseteq (V\times V)$是边集合

我们的目的是学习顶点$v\in V$到$d$维嵌入的非线性表示，其中$d\ll n$

• 这样的表示被编码到$n\times d$矩阵W中
• 节点$v$的嵌入为行$W_v$

---

我们的嵌入反映了给定图相似性的分布$si{m}_G:V\times V\to R$对于每个节点$v\in V$的分布

因此，我们要求任意顶点$v$与所有其他顶点$si{m}_G(v，\cdot )$的相似性可以被解释为${\sum }_{u\in V}si{m}_G(v,u)=1$的分布

我们的目标是通过一种可扩展的方法来设计$W$，该方法既不需要$V\times V$随机相似矩阵，也不需要它的显式具体化

嵌入空间中对应的节点间相似度为$si{m}_E:V\times V\to R$

作为优化目标，我们的目标是最小化给定相似度分布$si{m}_G$到嵌入空间中$si{m}_E$的Kullback-Leibler (KL)的发散:

个人理解：
$si{m}_G$是输入的相似性分布
$si{m}_E$是嵌入后的相似性分布

---

我们使用一个小的相似矩阵来说明这个目标的有用性

图2显示了

• $(a)$个性化PageRank矩阵
• $(b)$用VERSE重建相同矩阵
• $(c)$用SVD重建相同矩阵

可见

• 分布间KL散度的非线性最小化保留了原始矩阵中的大部分信息
• 而基于svd的线性重构无法区分某些节点

图2:一个相似矩阵的例子及其用VERSE和SVD重建。空手道俱乐部图[53]，两种方法维数d = 4

3.2 VERSE Embedding Model

$si{m}_E$:我们将嵌入空间中两个节点$u,v$之间的非归一化距离定义为它们嵌入的点积$Wu\cdot W^{T}v$

然后用softmax对嵌入空间的相似度分布进行归一化:

通过方程1，我们要使$si{m}_G$到$si{m}_E$的$KL$散度最小

忽略只依赖于$si{m}_G$的部分，这个目标等价于最小化交叉熵损失函数[14]:

我们可以通过随机梯度下降来适应这一目标，它允许在每个节点上奇异地更新模型

然而，naïve版本的梯度下降将需要$si{m}_E$和$si{m}_G$的完全具体化

• 即使$si{m}_G$很容易在动态中计算，比如邻接矩阵
• 但等式2中的softmax仍然需要对图中的所有节点进行归一化

---

我们使用噪声对比估计(NCE)[16,30]

它允许我们学习一个可证明收敛于其目标的模型(参见[17]，定理2)

NCE训练一个二分类器来区分来自经验相似性分布$si{m}_G$的节点样本和那些由节点上的噪声分布$Q$产生的节点样本

考虑一个辅助随机变量$D$用于节点分类

• 对于经验分布得出的节点D = 1
• 对于噪声分布得出的样本D = 0

给定一个从$P$分布中抽取的节点$u$和一个从$si{m}_G(u，\cdot )$分布中抽取的节点$v$

我们从$Q(u)$中抽取$s\ll n$个节点$\tilde{v}$，并使用逻辑回归最小化负对数似然:

其中

• $P{r}_W$是由$W$作为向量$W_u$与$W_v$的点积的sigmoid $\sigma (x)=(1+e^{-x}{)}^{-1}$来计算的

而我们计算$si{m}_E(u，\cdot )$时没有采用式2的归一化

随着噪声样本数量$s$的增加，NCE导数收敛于交叉熵梯度[30]

因此，由于NCE的渐近收敛保证，我们实际上最小化了$si{m}_G$的kl散度

NCE的理论保证依赖于$s$，而小的值在实践中可以很好地工作[30]

在我们的实验中，我们使用$s=3$

NCE的这些收敛保证不受分布P和Q的选择的影响(见[17]，推论5)
然而，根据经验，它的性能取决于Q[25]。

3.3 Instantiations of VERSE

虽然VERSE可以用于任何相似度函数，但我们选择将模型实例化为广泛使用的相似度$si{m}_G$，即

• 个性化PageRank (PPR)
• 邻接相似性(Adjacency similarity)
• SimRank

---

Personalized PageRank

个性化PageRank[34]是节点间常见的相似性度量，实际应用于许多图挖掘任务[15,28]。

定义：给定起始节点分布$s$、阻尼因子$\alpha$和归一化邻接矩阵$A$，个性化PageRank向量${\pi }_s$由递归方程定义:

具有α重启概率的随机游走的平稳分布收敛于PPR[34]

因此，来自$si{m}_G(v，\cdot )$的样本是来自节点$v$的单次随机游走中的最后一个节点

阻尼因子α控制所探索的邻域的平均大小

---

Adjacency similarity

一个简单的相似性度量是归一化邻接矩阵

这种相似性对应于LINE-1模型，只考虑每个节点的近邻

更正式地说，给定节点$u$的出度$Out(u)$

实验证明，VERSE模型在保持图的邻接矩阵方面也是有效的

---

SimRank

SimRank[21]是两个节点之间结构关系的度量，其基础是假设两个节点连接到其他类似节点时是相似的

SimRank递归地定义如下

其中

• $I(v)$表示节点$v$的内邻居集合
• $C$是一个介于0到1之间的数字，它在几何上折扣了更远节点的重要性

SimRank是一个递归过程，涉及到计算成本很高的操作:直接的方法的复杂性为$O(n^4)$

通过SimRank感知随机漫步(SARW)[22]，可以将SimRank值近似为依赖于C的乘性因子

SARW通过两次反向随机漫步(其中阻尼因子$\alpha$被设为$\alpha =\sqrt{C}$)来计算SimRank近似

反向随机漫步以相反的方向$(v,u)$遍历任何边$(u,v)$

由于我们只对每个$si{m}_G^{SR}(v，\cdot )$的分布感兴趣，我们可以忽略在近似[22]中对我们的任务影响很小的乘法因子

3.4 VERSE Algorithm

算法1给出了VERSE的整体流程

步骤：

1. 给定一个图、一个相似函数$si{m}_G$和嵌入空间维数$d$，我们将输出嵌入矩阵$W$初始化为$N(0,\frac{1}{d})$
2. 然后，我们使用前一节讨论的NCE算法，通过梯度下降来优化我们的目标(公式4)
3. 为此，我们反复从正分布P中采样一个节点，从$si{m}_G$中采样(例如，选择一个相邻节点)，并抽取$s$个负分布的例子

注释：

• 第13行中的$\sigma$表示sigmoid函数$\sigma =(1+e^{-x}{)}^{-1}$
• $\lambda$表示学习率
• 我们选择$P$和$Q$被$U(1,n)$均匀分布

作为处理较小图的应用程序的强大基线，我们还考虑了一种详尽的、详尽的VERSE变体

它计算每个节点的完全相似度分布向量，而不是执行基于NCE的抽样

我们将这种变体命名为$fVERSE$，并将其纳入我们的实验研究

---

图3展示了我们利用NCE重建

• (i) VERSE相似矩阵的能力
• (ii) VERSE使用负采样(NS)(也用于Node2vec)
• (iii)精疲力竭的变体

我们观察到

• 虽然NCE在匹配地面真实值前100个最相似的节点方面采用了穷举方法
• 但NS无法提供相同的质量

3.5 Complexity Comparison

3.6 Similarity Notions in Previous Approaches

在这里，我们提供了与LINE[41]、DeepWalk[37]和Node2vec[15]相比的额外理论考虑，并演示了我们的通用模型如何包含和扩展了以前在多功能性和可伸缩性方面的研究。

Comparison with DeepWalk and Node2vec

DeepWalk和node2vec通过word2vec采样策略[29]从窗口大小为w的随机漫步中生成样本

我们导出了该策略的窗口大小$w$与个性化页面排名的阻尼因子$\alpha$之间的关系

个性化PageRank提供了$\alpha =\frac{w-1}{w+1}$时方程7中分布的最大似然估计

• $w=10$对应$\alpha =0.82$，接近$\alpha =0.85$的标准，在实践中证明了[10]的有效性
• 另一方面，$\alpha =0.95$，即在4.2节中实现任务的最佳性能，对应$w=39$。如此大的$w$会大大增加DeepWalk和Node2vec的计算时间

Comparison with LINE

LINE引入了一阶和二阶近似的概念来模拟复杂的节点关系

如我们所讨论的，在VERSE中，一阶接近度对应于嵌入空间中相似性向量之间的点积:

另一方面，二阶接近对应于让VERSE多学习一个矩阵$W^{\prime }$，从而对嵌入空间中节点的不对称相似性进行建模

我们通过不对称地定义$si{m}_E$，同时使用$W$和$W^{\prime }$

二阶接近背后的直觉与SimRank相同:相似的节点具有相似的邻域

由于deepwalk和Node2vec借用了嵌入的word2vec解释，除了LINE-1，之前的每一种方法都使用了二阶接近

在我们的模型中，二阶邻近性可以通过添加一个额外的矩阵进行编码;我们将在第4节对其有效性进行实证评估

4 EXPERIMENTS

4.1 Link Prediction

4.2 Node Classification

4.3 Node Clustering

4.4 Graph Reconstruction

4.5 Parameter Sensitivity

4.6 Scalability

4.7 Visualization

5 CONCLUSIONS

我们引入了一个关于图嵌入的新视角:为了具有表现力，图嵌入应该捕获节点之间的某种相似性度量

有了这个视角，我们开发了一个可扩展的嵌入算法VERSE

与之前在该领域的研究不同

• VERSE的目的是重建每个图节点的任意选择的相似性度量的分布
• 因此，versee在其范围内引入了图表的全局视图，同时大大减少了训练所需的参数数
• verse具有线性的时间复杂度，因此它可以扩展到大型的真实图，而它只需要存储图的空间
• 此外，我们已经阐明了一些关于图嵌入的前期工作，通过顶点相似性的棱镜来观察和解释它们

我们全面的实验研究表明，即使将PPR作为默认的相似性概念实例化，VERSE在大量图任务中始终优于最先进的图嵌入方法，而超参数监督变体的表现甚至更好

因此，我们提供了强有力的证据，表明真正基于顶点相似性的嵌入地址图挖掘比其他方法更具挑战性

读后总结

这篇文章开始读的有点云里雾里 （天气炎热????）

后面多读了几遍，发现还是有一点收获的

作者最开始的思路主要是利用$si{m}_G$和$si{m}_E$来构造损失函数

• $si{m}_G$主要就是利用原图得到两个节点之间的相似性，这里有三种相似性计算方式
  • PPR
  • Adjacency similarity
  • SimRank
• $si{m}_E$主要就是对嵌入表示中两个节点进行的相似性计算，这里也就使用的是内积的方式

然后构建的损失函数为：

但是这样的话会有个问题：计算复杂度太高了，不易于计算

然后作者提出改进，使用NCE算法，大概意思就是

1. 对于节点$u$，先从$si{m}_G(u,\cdot )$构建的顶点分布中选择一个顶点$v$，计算$si{n}_E(u,v)$
2. 然后选择$s$个噪声点（从一个自己定义的分布中选择，噪声点为$\tilde{v}$），计算$si{m}_E(u,\tilde{v})$
3. 依照上面两个步骤，得到损失

因为NCE得到的损失当S为一定的值时，是等效于最开始的交叉熵的，而且就计算复杂度要低很多

所以使用$NCE$算法

总体算法步骤为

个人理解步骤为：

1. 先随机初始化嵌入矩阵$W$
2. 然后随机选一个顶点$u$（从自己定义的分布中选择）
3. 再从以$si{m}_G$构造的分布中随机选择一个顶点$v$
4. 计算$L_{NCE}$，得到梯度$g$，然后更新$w_u$和$w_v$（这里只使用一层神经网络）
5. 然后再随机选取$S$个噪声点（也是从自定义的分布中选择，为$\tilde{v}$）
6. 利用循环 对每一个噪声点$\tilde{v}$计算$L_{NCE}$，得到梯度，更新$W_u$和$W_{\tilde{v}}$
7. 直到算法收敛为止

读完之后，醍醐灌顶，作者思路不是那么复杂，很简洁

感慨思考的角度很独特，佩服！

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正

最后

以上就是昏睡世界为你收集整理的【论文阅读｜深读】VERSE: Versatile Graph Embeddings from Similarity Measures前言简介ABSTRACT1 INTRODUCTION2 RELATED WORK3 VERSATILE GRAPH EMBEDDING4 EXPERIMENTS5 CONCLUSIONS读后总结结语的全部内容，希望文章能够帮你解决【论文阅读｜深读】VERSE: Versatile Graph Embeddings from Similarity Measures前言简介ABSTRACT1 INTRODUCTION2 RELATED WORK3 VERSATILE GRAPH EMBEDDING4 EXPERIMENTS5 CONCLUSIONS读后总结结语所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。