通用图嵌入方法VERSE：基于相似性度量，实现精确与高效的信息网络分析

5390VERSE：基于相似性度量的通用图嵌入0Anton Tsitsulin HassoPlattner Instituteanton.tsitsulin@hpi.de0Davide Mottin HassoPlattner Institutedavide.mottin@hpi.de0Panagiotis KarrasAarhus Universitypanos@cs.au.dk0Emmanuel Müller HassoPlattner Instituteemmanuel.mueller@hpi.de0摘要0将Web规模的信息网络嵌入到低维向量空间中，可以方便进行链接预测、分类和可视化等任务。过去的研究已经解决了从单词到图形的方法中提取这种嵌入的问题，但没有定义一个明确易懂的与图形相关的目标。然而，正如我们所展示的，过去的研究中使用的目标隐含地利用了图形节点之间的相似性度量。在本文中，我们将之前的相似性导向延伸到其逻辑结论；我们提出了一种名为VERSE（VERtexSimilarity Em-beddings）的简单、通用和内存高效的方法，该方法通过训练单层神经网络来推导出明确校准以保留所选顶点到顶点相似性度量的分布的图形嵌入。VERSE通过对相似性信息进行采样来学习这样的嵌入，默认情况下，它的可扩展版本通过对每个顶点使用完整信息来实现。我们在标准基准和真实数据集上的实验研究表明，VERSE在主要数据挖掘任务的精确度和召回率方面优于最先进的方法，并在时间和空间效率方面超越它们，而可扩展的基于采样的变体与不可扩展的完整变体取得了同样好的结果。0ACM参考格式：Anton Tsitsulin，Davide Mottin，PanagiotisKarras和EmmanuelMüller。2018年。VERSE：基于相似性度量的通用图嵌入。在WWW2018：2018年Web会议上，2018年4月23日至27日，法国里昂。ACM，美国纽约，10页。https://doi.org/10.1145/3178876.318612001 引言0图形数据在许多领域中自然产生，包括社交网络、蛋白质网络和网络。在过去的几年中，已经提出了许多图形挖掘技术来分析和探索这些现实世界的网络。通常，这些技术应用机器学习来解决节点分类、链接预测、异常检测和节点聚类等任务。机器学习算法需要一组具有表征性的区分特征来描述图形节点和边缘。为此，可以使用表示节点之间相似性的特征[18]。0本文发表在知识共享署名4.0国际（CC BY4.0）许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂。© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861200（a）社区结构（b）角色（c）结构等价性0图1：同一图上突出显示了三个节点属性。单个模型能否捕捉到这些属性？0然而，特征工程是一项繁琐的工作，而且结果在不同任务之间无法很好地转化[15]。与特征设计相反，一种替代方法是通过以无监督的方式解决优化问题来学习特征向量或嵌入。然而，设计和解决一个通用且可行的学习表示的优化问题一直是研究的难点[7]。一种研究线路[11,42]是应用经典的降维方法，如SVD，对图上的相似性矩阵进行处理；然而，这些方法的负担在于构建矩阵。虽然最近的一种方法[33]克服了这个障碍，但由于其线性特性，在预测任务中结果质量较差。另一种研究线路旨在生成捕捉邻域局部性的特征，通常通过可以通过随机梯度下降（SGD）进行优化的目标来实现[37,41]。这些方法依赖于一个隐含的、尽管刚性的节点邻域概念；然而，这种一刀切的方法无法应对现实世界网络和应用的多样性。Grover等人[15]发现了局部邻域概念的这种不灵活性；为了改善这种情况，他们提出了Node2vec，它使用两个超参数来偏置[37]的探索策略。然而，这种需要调整超参数的方法导致了立方最坏情况下的空间复杂度，并迫使用户遍历多个特征集并评估在下游任务中表现最好的特征集。此外，即使通过超参数调整找到了局部邻域，它仍然只代表了一类基于局部性的特征；因此，Node2vec并没有充分摆脱它试图修复的刚性。0主题：社交网络分析和Web上的图算法WWW 2018年4月23日至27日，法国里昂5400WWW 2018年4月23日至27日，法国里昂Anton Tsitsulin，Davide Mottin，Panagiotis Karras和Emmanuel Müller0我们认为，通过比局部邻域更多样化的相似性概念提取的特征可以在各种图上解决各种数据挖掘任务。图1展示了图上的三种不同类型的相似性：社区结构指导社区检测任务，角色通常用于分类，而结构等价性定义了知识图中的对等对应关系。由于现实世界的任务依赖于这些属性的混合，一个多功能的特征学习算法应该能够捕捉所有这些相似性。在本文中，我们提出了VERSE，这是第一个我们所知的能够明确学习节点之间的任何相似性度量的多功能图嵌入方法。在其学习核心中，VERSE介于深度学习方法[12, 48]和相似性矩阵的直接分解[11,42]之间。相反，VERSE训练一个简单但表达力强的单层神经网络来重构节点之间的相似性分布。因此，它在各种大型真实网络和任务上的运行时间和质量方面优于先前的方法。由于它能够选择适合当前任务的任何合适的相似性度量，VERSE在不需要改变其核心的情况下适应该任务。因此，它完全改善了[15]中观察到的刚性，并将表示学习与特征工程相结合：任何相似性度量，包括在特征工程中开发的度量，都可以用作VERSE的输入。为了说明，我们使用三种流行的相似性度量来实例化我们的通用方法，即个性化PageRank（PPR）[34]，SimRank[21]和邻接相似性。我们还表明，多功能并不意味着对用户的新负担，只需用相似性度量调整代替超参数调整：使用PPR作为相似性度量的默认选择在我们检查的几乎所有任务和网络中都能获得良好的性能。我们总结我们的贡献如下。0•我们提出了一个多功能的图嵌入框架，明确学习每个图顶点的任何顶点相似性度量的分布。•我们通过我们的相似性框架解释了先前的图嵌入，并使用个性化PageRank，SimRank和邻接相似性实例化了VERSE。•我们设计了一种高效的算法，其时间复杂度与图的大小成线性关系，该算法基于一个单层神经网络，最小化了从真实相似性到重构相似性分布的差异。•在全面的实验评估中，我们展示了VERSE在各种图挖掘任务中的质量优于最先进的方法，同时更加高效。02 相关工作0在没有通用图表示的情况下，图分析任务需要领域专家来设计特征[4,18]或使用专门的特征选择算法[36,40]。最近，引入了专门的方法来学习不同图部分的表示[2,31]以及具有节点注释[20, 55]或边缘注释[19,49]的图。我们专注于学习没有任何先验或额外信息的图中节点的表示。0传统的特征学习通过将表示（如拉普拉斯矩阵或邻接矩阵）压缩到低维空间来学习特征。该领域的早期工作包括谱技术[6]和非线性降维[39,44]。另一方面，边缘费舍尔分析[51]将点数据集的降维视为捕捉其统计和几何属性的图的嵌入。这些方法不能应用于大型图，因为它们操作的是密集矩阵。一些努力已经通过使用增强的线性代数工具来克服这个限制。Ahmed等人[3]采用随机梯度优化进行快速邻接矩阵特征分解；Ou等人[33]利用稀疏广义SVD生成一个图嵌入，HOPE，从一个可分解为两个稀疏接近矩阵的相似性矩阵。HOPE是第一个支持多样性相似性度量的方法；然而，它仍然需要整个图矩阵作为输入，并将问题视为线性降维而不是非线性学习的问题。这样一来，它不仅偏离了当前关于图嵌入的研究，也偏离了早期的工作[51]。0用于表示学习的神经方法。机器学习的进展导致了神经方法在学习表示方面的应用[7]。在图像处理[24]和自然语言处理（NLP）[8, 29,35]等领域的深度学习的成功基础上，word2vec[29]通过训练单层神经网络来猜测给定文本中一个词的上下文词来构建词嵌入。同样，GloVe[35]通过在转换后的共现矩阵中使用SVD的随机版本来学习一个词空间。虽然这些基于文本的方法本质上考虑了邻居关系，但它们需要概念上的适应来建模图形[37]。0神经图嵌入。神经词嵌入的成功启发了学习图表示的自然扩展[11,12, 15, 37, 46, 48]。DeepWalk[37]首次提出了在低维向量空间中学习潜在表示的方法，利用局部节点邻域进行一系列固定长度的随机游走，并使用[29]的SkipGram算法创建一个d维度的顶点表示矩阵。这些表示最大化在随机游走中观察到邻近顶点的后验概率。DeepWalk嵌入可以使用简单的线性分类器（如逻辑回归）来进行分类任务。GraRep[11]建议在不同阶数的DeepWalk转移概率矩阵上使用奇异值分解（SVD），然后连接生成的表示。Struc2vec[38]通过重构图形以反映节点之间的同构性并捕捉结构相似性，然后依赖于DeepWalk核心来推导嵌入。[12,48]等工作研究了用于图嵌入的深度学习方法。他们的结果是复杂的模型，需要精心调整参数和计算昂贵的优化，导致时间和空间复杂度不适用于大型图形。然而，所有基于DeepWalk的方法都使用不适合图形结构的目标函数。一些工作[15, 38,41]尝试将图本地原则融入学习过程。LINE[41]提出了捕捉更多关系的图嵌入0跟踪：社交网络分析和Web上的图算法WWW 2018年4月23日至27日，法国里昂KL (simG(v, ·) || simE(v, ·))(1)L = −�v ∈VsimG(v, ·) log (simE (v, ·))(3)Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France5410VERSE：来自相似度度量的多功能图嵌入WWW 2018年4月23日至27日，法国里昂0算法 相似性0方法 本地可扩展非线性 全局多功能0DeepWalk [37] � � � � � Node2vec [15] LINE [41] � � � � �0GraRep [11] � � � � �0SDNE [48] � � � � �0DNGR [12] � � � � �0HOPE [33] � � � � �0VERSE � � � � �0表1：算法和相似度度量的已满足（�）和未满足（�）属性的相关工作概述。0详细的接近概念。然而，即使是LINE的接近概念也仅限于每个节点的直接邻域；这对于捕捉节点之间的完整关系调色板是不够的[15, 33,38]。此外，Node2vec[15]引入了两个超参数来调节随机游走的生成，从而以半监督的方式将学习过程调整到手头的图形。然而，Node2vec仍然依赖于保留局部邻域的目标，并且对于每个数据集和每个任务都需要费力的调整。0概述。表1概述了图嵌入的五个理想属性，以及先前方法在这些属性上的具备程度。我们区分了算法的属性和方法可能表达的任何隐式或显式的节点相似度度量的属性。0•  local :不需要整个图矩阵作为输入；GraRep、DNGR和HOPE在这一点上失败。 •  scalable :能够在不到一天的时间内处理超过10^6个节点的图；一些方法由于密集矩阵（GraRep）、深度学习计算（SDNE）或两者都失败而无法满足此标准。 •  nonlinear :使用非线性变换；HOPE依赖于线性降维方法SVD；这对于构建图表示来说是有害的，就像线性降维方法一般无法给予非线性对应物的优势一样[26]。 •  global :能够建模任意一对节点之间的关系；LINE和SDNE不具备这个属性，因为它们无法超越节点的直接邻域。 •  versatile :支持多样的相似性函数；HOPE可以做到这一点，但由于其线性特性而受到影响。03多功能图嵌入0VERSE具有我们分类中提到的所有属性；它采用非线性变换，对降维很有帮助[26]；它在每个节点的输入方面是局部的，但在潜在的输入来源方面是全局的；它是可扩展的，因为它基于采样；它是多功能的，因为它的通用性。0(a) 相似性0(b) VERSE0(c) SVD0图2：一个示例相似性矩阵及其由VERSE和SVD重构的结果。Karate俱乐部图[53]，两种方法的维度 d  = 4。03.1 VERSE目标0给定一个图G = ( V ,  E ), 其中 V  = ( v 1 , . . . , v n ),  n  =  | V  | ,是顶点的集合， E  �  ( V  ×  V  ) 是边的集合，我们的目标是学习顶点v  ∈  V  的非线性表示，将其表示为d维的嵌入，其中 d  �  n。这样的表示被编码为一个n  ×  d  的矩阵 W ；一个节点 v的嵌入是矩阵中的一行 W v ,  ∙ ，我们将其简记为 W v。我们的嵌入反映了给定图的相似性分布 sim G  :  V  ×  V  →  R，对于每个节点 v  ∈  V  。因此，我们要求从任何顶点 v到所有其他顶点的相似性 sim G ( v ,  ∙ )都可以被解释为一个分布，其中对于所有的 v  ∈  V ，有 ∑ u  ∈ Vsim G ( v , u )  = 1 。我们的目标是通过一种可扩展的方法设计矩阵W ，该方法既不需要 V  × V的随机相似性矩阵，也不需要显式地生成它。嵌入空间中的相应节点之间的相似性是 sim E  :  V  ×  V  →  R。作为优化目标，我们的目标是最小化给定相似性分布 sim G到嵌入空间中的 sim E 的Kullback-Leibler（KL）散度：0∑0我们通过一个小的相似性矩阵来说明这个目标的有用性。图2显示了（a）PersonalizedPageRank矩阵，（b）VERSE对同一矩阵的重构，以及（c）使用SVD对同一矩阵的重构。可以看出，非线性最小化KL散度可以保留原始矩阵中的大部分信息，而线性的基于SVD的重构则无法区分一些节点。03.2 VERSE嵌入模型0我们定义嵌入空间中两个节点 u , v之间的非归一化距离为它们嵌入的点积  W u  ∙ W � v。然后，嵌入空间中的相似性分布通过softmax进行归一化：0sim E ( v ,  ∙ ) = exp( W v W � ) / ∑ i =1 exp  ( Wv  ∙ W i ) (2)0根据公式1，我们应该最小化从sim G 到 sim E的KL散度；忽略仅依赖于sim G的部分，这个目标等价于最小化交叉熵损失函数[14]：WWW 2018, April 23–27, 2018, Lyon, FranceAnton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Mülleru∼Pv∼simG(u, ·)sElog Pr(D = 0 sim (u,v))(4)simADJG(u,v) =simSRG (u,v) =CI(u) I(v)|I(u)| |I(v)|simSRG (Ii(u), Ij(v))(6)Algorithm 1 VERSE13:д ← D − σ Wu ·Wv∗ λ14:Wu ← д ∗Wv15:Wv ← д ∗Wu5420我们可以通过随机梯度下降来实现这个目标，它允许在每个节点上更新模型。然而，朴素的梯度下降版本需要完全实现sim E和simG。即使在simG易于即时计算的情况下，例如邻接矩阵，方程2中的softmax仍然必须在图中的所有节点上进行归一化。我们使用噪声对比估计（NCE）[16,30]，它允许我们学习一个可证明收敛到目标的模型（参见[17]，定理2）。NCE训练一个二元分类器，区分来自经验相似度分布simG的节点样本和由节点上的噪声分布Q生成的节点样本。考虑一个辅助随机变量D用于节点分类，当节点从经验分布中抽取时D =1，当从噪声分布中抽取样本时D =0。给定从某个分布P中抽取的节点u和从sim G(u,∙)的分布中抽取的节点v，我们从Q(u)中抽取s �n个节点v，并使用逻辑回归来最小化负对数似然：0其中Pr W是从W计算的，是向量W u 和W v的点积的sigmoid函数σ(x) = (1 +  e − x ) − 1，而我们计算sim E(u,∙)时不进行方程2的归一化。随着噪声样本数量s的增加，NCE导数可证明收敛到交叉熵的梯度[30]；因此，凭借NCE的渐近收敛保证，我们实际上是在最小化与simG的KL散度。NCE的理论保证依赖于s，但在实践中小的值效果很好[30]。在我们的实验中，我们使用s =3。NCE的这些收敛保证不受分布P和Q的选择的影响（参见[17]，推论5）；然而，它的性能在实际中依赖于Q [25]。0VERSE的实例化。0虽然VERSE可以与任何相似度函数一起使用，但我们选择将我们的模型实例化为广泛使用的相似度simG，即个性化PageRank（PPR），邻接相似度和SimRank。0个性化PageRank。个性化PageRank[34]是一种常用的节点相似度度量，实际上用于许多图挖掘任务[15,28]。0定义3.1.给定起始节点分布s，阻尼因子α和归一化邻接矩阵A，个性化PageRank向量π s 由递归方程定义：0π s  =  αs  + (1  −  α ) π s A具有概率α的重启随机游走的稳态分布收敛到PPR[34]。因此，从节点v开始的单个随机游走的最后一个节点是从sim G(v,∙)中采样的节点。阻尼因子α控制了探索邻域的平均大小。在第3.6节中，我们将展示α与DeepWalk和Node2vec的窗口大小参数w紧密耦合。0邻接相似度。一种直接的相似度度量是归一化的邻接矩阵；这种相似度对应于0LINE-1模型仅考虑每个节点的直接邻居。更正式地说，给定节点u的出度Out(u)0� 1 / 如果 ( u , v )  ∈  E ，则 Out ( u )为 1，否则为 0 (5)0我们通过实验证明，VERSE模型即使在保持图的邻接矩阵方面也是有效的。0SimRank . SimRank [ 21]是两个节点之间结构相关性的度量，基于这样的假设：如果两个节点连接到其他相似的节点，则它们是相似的；SimRank的递归定义如下：0其中I（v）表示节点v的入邻居集合，C是0到1之间的数，几何上降低了更远节点的重要性。SimRank是一个涉及计算昂贵操作的递归过程：直接方法的复杂度为O（n^4）。通过SimRank-Aware随机游走（SARW）[22]，可以将SimRank值近似到依赖于C的乘法因子。SARW通过两个带有重启的逆向随机游走计算SimRank近似，其中阻尼因子α设置为α = √0C .逆向随机游走以相反方向（v，u）遍历任何边缘（u，v）。由于我们只对每个sim SRG（v，∙）的分布感兴趣，因此可以忽略近似中的乘法因子[22]，对我们的任务影响不大。02: W  ← N � 0 ,  d − 1 � �  其中W ∈ R | V |× d03: 重复04: u  � P �  采样一个节点05: v  �  sim G ( u ) �  采样正例08: 采样负例 � v  � Q ( u )010: 直到收敛011: 返回 W012:  function  Update( u , v ,  D ) �  逻辑梯度更新03.4 VERSE算法0Algorithm 1介绍了VERSE的整体流程。给定一个图形，相似性函数simG和嵌入空间维度d，我们将输出嵌入矩阵W初始化为N（0，10然后，我们使用前一节中讨论的NCE算法通过梯度下降优化我们的目标函数（方程4）。为此，我们重复从正分布P中采样一个节点，采样simG（例如选择一个相邻节点），并绘制s个负例。第13行中的σ表示sigmoid函数σ =（1 +e-x）-1，λ表示学习率。我们选择P和Q均匀分布为U（1，n）。0Track: 用于Web的社交网络分析和图算法 WWW 2018年4月23日至27日，法国里昂204060801000.40.60.81kNDCG@kfull VERSENS,s = 3NCE,s = 3NCE,s = 100GraReptn3tn3n2n2LINEdsndsnmn2Node2vecdsndsnm2nn3HOPEd2md2n2mn2fVERSEdn2dn2n2n2VERSEdsndsnmn2Pr(Xr = j) =2w(w + 1)(w − j + 1)(7)simE(u,v) = Wu ·Wv5430VERSE: 从相似度度量中得到多功能图嵌入 WWW 2018年4月23日至27日，法国里昂0作为处理较小图形的应用的强基准，我们还考虑了VERSE的详细而全面的变体，该变体计算每个节点的完整相似度分布向量，而不是执行基于NCE的采样。我们将此变体命名为fVERSE，并将其包含在我们的实验研究中。图3展示了我们在重建相似性矩阵能力方面的度量结果：（i）使用NCE的VERSE；（ii）使用负采样（NS）的VERSE（也用于Node2vec）；（ii）详细的fVERSE变体。我们观察到，虽然NCE在匹配前100个最相似节点的基本事实方面接近详细方法，但NS无法提供相同的质量。0图3：以NDCG为指标的排名性能，对图中的节点进行平均。03.5 复杂性比较0表2给出了VERSE的平均（Θ）和最坏情况（O）的时间和空间复杂度，以及先前工作中的方法的复杂度；d是嵌入维度，n是节点数，m是边数，s是使用的样本数，t是GraRep中的迭代次数。依赖于快速采样的方法（VERSE和LINE）在最坏情况下需要线性时间和二次空间。DeepWalk由于使用分层softmax而需要O(n logn)的时间。Node2vec存储了邻居的邻居，在稀疏图中产生二次成本，但在稠密图中产生三次成本。因此，与先前的图嵌入方法相比，VERSE的复杂度较低。值得注意的是，即使是计算昂贵的fVERSE也具有与某些先前工作相当的复杂度。0时间 空间0方法 Θ O Θ O0表2：以平均（Θ）和最坏情况（O）的时间和空间复杂度比较神经嵌入方法。03.6 先前方法中的相似性概念0在这里，我们提供了VERSE与LINE [41]、DeepWalk[37]和Node2vec[15]的额外理论考虑，并展示了我们的通用模型在多样性和可扩展性方面如何包含和扩展先前的研究。0与DeepWalk和Node2vec的比较。DeepWalk和Node2vec通过word2vec采样策略从固定窗口大小为 w的随机游走中生成样本[29]。我们推导出该策略的窗口大小 w与Personalized PageRank的阻尼因子 α 之间的关系。0引理3.2.令X_r是用word2vec采样策略以参数w采样的随机游走r的长度表示的随机变量。那么对于任意的0 < j ≤ w0证明. 对于每个节点 v ∈ V，word2vec策略从 v ∈ V 开始采样两个长度为 w的随机游走。这两个随机游走表示了 v 的上下文，其中 v 是长度为 2w+1的游走的中心节点。然后，该模型在不断增加的上下文大小上进行训练，直到w。因此，对于每个随机游走采样的节点数目为 ∑_{i=1}^{w} i = w(w+1)。02. 距离0 < j ≤ w 的节点被采样了 w - j + 1 次；因此，最终的概率是20Personalized PageRank为方程7中的分布提供了最大似然估计，其中 α = w - 10w +1 . 然后，w = 10 对应于 α = 0.82，这接近于标准的 α =0.85，在实践中被证明是有效的[10]。另一方面，例如，α =0.95，在第4.2节的一个任务中实现了最佳性能，对应于 w =39。这样大的 w会极大地增加DeepWalk和Node2vec的计算时间。0与LINE的比较。LINE引入了一阶和二阶接近性的概念来建模复杂的节点关系。正如我们所讨论的，VERSE中的一阶接近性对应于嵌入空间中相似性向量的点积：0另一方面，二阶接近度对应于让VERSE学习另一个矩阵W'，以建模嵌入空间中节点的非对称相似性。我们通过使用W和W'来不对称地定义sim E来实现这一点：0sim E(u, v) = Wu ∙ W'v0二阶接近度背后的直觉与SimRank相同：相似的节点具有相似的邻居。除了LINE-1之外，之前的每种方法都使用了二阶接近度，这是由DeepWalk和Node2vec借用的嵌入的word2vec解释所致。在我们的模型中，可以通过添加一个额外的矩阵来编码二阶接近度；我们在第4节中经验性地评估了它们的有效性。0Track: 社交网络分析和Web图算法 WWW 2018，2018年4月23日至27日，法国里昂1https://github.com/xgfs/verse2https://github.com/xgfs/deepwalk-c3https://github.com/xgfs/node2vec-c4https://github.com/tangjianpku/LINE5440WWW 2018，2018年4月23日至27日，法国里昂 Anton Tsitsulin，Davide Mottin，Panagiotis Karras和Emmanuel Müller04 实验0我们将VERSE与几种最先进的图嵌入算法进行了评估。为了重复性，我们提供了所有数据集和VERSE 1、DeepWalk 2和Node2vec3的C++源代码。我们在Amazon AWSc4.8实例上运行实验，具有60GB的RAM。每种方法都在最佳参数上进行评估，如果在一天内没有返回结果，则提前终止计算。我们提供以下最先进的图嵌入方法进行比较：0•  DeepWalk[37]：该方法通过从每个节点中采样随机游走，对这些游走应用基于word2vec的学习来学习嵌入。我们使用论文中描述的默认参数，即游走长度t = 80，每个节点的游走次数γ = 80，窗口大小w = 10。 •LINE[41]：该方法通过两个步骤在邻接相似性上学习一个d维嵌入。首先，它使用一阶接近度学习d/2维度；然后，它使用二阶接近度学习另外d/2个特征。最后，将这两部分进行归一化和连接。我们使用论文中描述的代码4进行实验，总共采样T = 10^10个样本，每个样本有s= 5个负样本。 •  GraRep[11]：该方法使用奇异值分解对完整的邻接相似性矩阵进行分解，将矩阵与自身相乘，并重复该过程t次。最终的嵌入通过连接分解的向量得到。我们使用t =4和每个SVD分解的32维度；因此，最终的嵌入是d = 128。 •HOPE[33]：该方法是一种修订的奇异值分解方法，仅适用于稀疏相似性矩阵。我们报告了使用默认参数运行HOPE得到的结果，即使用Katz相似性（Katz中心性的扩展[23]）作为相似性度量，β与谱半径成反比。由于Katz相似性在具有汇节点的有向图上不收敛，我们在CoCit数据集上使用了α = 0.85的个性化PageRank。 •  Node2vec[15]：这是一种超参数监督方法，通过添加两个参数p和q来扩展DeepWalk，以控制DeepWalk的随机游走采样。当参数p = 1，q =1时，它对应于DeepWalk；然而，在我们的评估中，有时Node2vec的性能比DeepWalk差，这是因为Node2vec使用了负采样，而DeepWalk使用了分层softmax。我们在每个数据集和任务上对超参数p和q进行了微调。此外，我们使用了大量的训练数据，以便与DeepWalk进行公平比较，即游走长度l = 80，每个节点的游走次数r =80，窗口大小w = 10。0基准。除了图嵌入方法外，我们还实现了以下基准。0•逻辑回归：我们使用著名的逻辑回归方法作为链路预测的基准。我们在一组常见的节点特征上训练模型，包括节点度、共同邻居数量、Adamic-Adar、Jaccard系数、优先连接和资源分配指数[27, 28]。0尺寸统计0数据集 | V | | E | |L | 平均度数 Mod. 密度0BlogCatalog 10k 334k 39 64.8 0.24 6.3 × 10^-30CoCit 44k 195k 15 8.86 0.72 2.0 × 10^-40CoAuthor 52k 178k — 6.94 0.84 1.3 × 10^-40VK 79k 2.7M 2 34.1 0.47 8.7 × 10^-40YouTube 1.1M 3M 47 5.25 0.71 9.2 × 10^-60Orkut 3.1M 234M 50 70 0.68 2.4 × 10^-50表3：数据集特征：顶点数|V|，边数|E|；节点标签数|L|；平均节点度；模块度[32]；密度定义为|E|/|V|^2。0•Louvain社区检测[9]：我们采用标准的分区方法作为图聚类的基准，以模块度[32]为指标报告最佳分区。0参数设置。与之前的研究[15, 37,41]一致，我们将嵌入维度d设置为128。对于VERSE，学习过程（算法1，第3行）运行10^5次，对于fVERSE运行250次；设置的不同是由于VERSE中的模型更新次数为O(n)，而fVERSE中为O(n^2)。我们使用LIBLINEAR[13]进行逻辑回归，使用默认参数设置。与之前的工作[15, 37,41]不同，我们对多标签节点分类采用了更严格的假设：正确类别的数量事先不知道，而是通过标签幂集多标签分类方法[45]找到的。对于链接预测和多标签分类，我们对每个单独的嵌入进行了10次评估，以减少分类器引入的噪声。除非另有说明，否则我们每个实验运行10次，并报告运行中的平均值。在我们的实验研究中，除非另有说明，否则我们使用上述参数作为默认值。0数据集。我们在六个真实数据集上测试了我们的方法；我们在表3中报告了主要的数据特征。• BlogCatalog[54]是BlogCatalog网站上博主之间社交互动的网络。节点标签表示作者提供的主题类别。• Microsoft Academic Graph[1]是来自MicrosoftAcademic网站的学术论文、引用、作者和机构的网络，用于KDD-2016杯赛。它包含了截至2016年2月的1.5亿篇论文，涵盖了从数学到生物学的各个学科。我们从原始网络中提取了两个独立的子图，使用了15个数据挖掘、数据库和机器学习领域的会议。第一个是CoAuthor，是作者之间的合著网络。第二个是CoCit，是引用其他论文的论文网络；标签表示发表论文的会议。•VK是一个俄罗斯综合性社交网络。我们提取了2016年11月和2017年5月的网络快照，以获取关于链接出现的信息。我们使用用户的性别进行分类，使用国家进行聚类。• YouTube[43]是YouTube视频平台用户之间社交互动的网络。标签表示按视频类型分组的观众群体。• Orkut[52]是Orkut社交网络平台用户之间社交互动的网络。标签表示用户的社区。我们提取了50个最大的社区，并将它们用作分类的标签。0主题：社交网络分析和Web上的图算法 WWW 2018，2018年4月23日至27日，法国里昂Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France5450VERSE：来自相似度度量的多功能图嵌入 WWW 2018，2018年4月23日至27日，法国里昂0评估方法。VERSE的默认形式是使用α=0.85的个性化PageRank算法。为了公平起见，我们设计了一个基于超参数的VERSE变体，类似于Node2vec引入的DeepWalk的超参数调整变体[15]。这个变体，hsVERSE，在两个接近顺序（如第3.6节所讨论的）和三个相似度（第3.3节）中通过交叉验证选择最佳相似度，其中α∈{0.45, 0.55, 0.65,0.75, 0.85, 0.95}用于sim PPR G，C∈{0.15, 0.25, 0.35, 0.45, 0.55,0.65}用于sim SR G。0运算符 结果0平均 ( a  +  b ) / 2 连接 [ a 1 , . . . ,  a d ,  b 1 , . . . ,  b d ]Hadamard [ a 1  �  b 1 , . . . ,  a d  �  b d ] 加权 L1 [ | a 1  −  b1 | , . . . ,  | a d  −  b d  | ] 加权 L2 [( a 1  −  b 1 ) 2 , . . . ,  ( ad  −  b d ) 2 ]0表4：用于链接预测任务的向量运算符，对于每个  u , v  ∈  V和相应的嵌入  a ,  b  ∈  R d 。0fVERSE 80.06 79.69 86.71 84.49 84.97 VERSE 79.16 78.7985.69 71.93 72.11 DeepWalk 68.43 68.06 66.54 79.06 78.11GraRep 74.87 74.91 82.24 80.03 80.05 LINE 77.49 77.3977.73 70.55 71.83 HOPE 74.90 74.83 74.81 74.34 74.810hsVERSE 79.52 79.10 86.15 76.45 76.72 Node2vec 77.0776.67 79.42 81.25 80.850特征工程 77.530表5：CoAuthor合著关系图上的链接预测结果。每种方法的最佳结果已用下划线标出。0fVERSE 74.94 74.81 80.77 78.49 79.13 VERSE 73.78 73.6679.71 74.11 74.56 DeepWalk 70.05 69.92 69.79 78.38 77.37LINE 75.17 75.13 72.54 63.77 64.47 HOPE 71.89 71.90 70.2271.22 70.630hsVERSE 74.14 74.02 80.26 73.04 73.53 Node2vec 71.2971.22 72.43 78.38 78.660特征工程 78.840表6：VK社交图上的链接预测结果。每种方法的最佳结果已用下划线标出。04.1 链接预测0链接预测是在网络中预测两个节点之间出现链接的任务。传统的链接预测度量包括Adamic-Adar、优先附加、Katz和Jaccard系数。我们使用表4中显示的方法获取边特征，并在边上训练逻辑回归分类器。例如，对于一对节点  u , v ，Concat运算符返回一个向量，该向量是嵌入  f  ( u ) 和  f  ( v )的顺序连接。在CoAuthor数据上，我们预测2015年和2016年的合著关系的新链接，使用2014年之前的网络进行训练；在VK上，我们预测2016年11月至2017年5月之间是否会出现新的友谊链接，使用50%的新链接进行训练，50%进行测试。我们通过对不存在的边进行采样来训练二元分类器的负例。表5和表6报告了达到的准确性。作为基准，我们使用在相应数据集的特征上训练的逻辑回归分类器。使用向量的Hadamard乘积的VERSE始终是最佳的边表示。我们将这种质量归因于使用噪声对比估计实现的显式重构。VERSE在测试的数据集中始终优于基准。此外，超参数监督的hsVERSE变体在所有数据集上都超过了Node2vec。0方法 1% 3% 5% 7% 9%0fVERSE 27.52 29.83 31.01 31.68 3