嵌入双曲层的神经排序式图表示学习方法

唐素勤,刘笑梅,袁 磊

(广西师范大学 a.教育学部; b.广西多源信息挖掘与安全重点实验室,广西 桂林 541004)

0 概述

网络图包含一组相互连接的节点,其中,每对节点之间具有大量的关系信息[1]。几乎每个领域都需要对图进行分析,例如,在生物网络中,人们可能需要分类蛋白质的角色,或者预测现有药物分子的新应用;在社交网络中,需要有针对性地向用户投放广告或推荐新朋友等。因此,研究人员开发了各种图数据挖掘算法应用于节点分类、标签推荐、异常检测和链接预测等任务。但是,这些已有的图数据挖掘算法通常需要一组图特征信息作为算法的输入。例如,为了从图中提取结构信息,传统的方法通常依靠图的相关统计(如度、聚集系数等)、核函数或手工特征来测量局部近邻结构[2],然而这些手工设计的特征在学习过程中不能自适应,且需要大量的人力成本和专业知识[3]。因此,有学者提出了表示学习方法以避免耗时且成本昂贵的特征设计,该方法同时提高了特征的灵活性。

现有的图表示学习方法主要聚焦于为图数据设计新的神经网络模型或设计更加复杂的随机游走机制来探索网络结构,这些方法往往使图表示学习的复杂性大幅提高。最近,将数据嵌入非欧几里德空间的方法受到越来越多的关注,原因是欧几里德模型不能正确地反映复杂数据模式。受此启发,本文对神经网络表示设置适当的几何结构,特别是层次结构和聚集行为,以捕获图数据的基本属性。图数据的这些基本属性出现在许多遵循幂律分布的现实复杂网络场景中,可作为引入双曲几何的起点。双曲空间能够反映复杂网络的属性主要是由于其潜在的关键属性,即空间量随着距参考点的距离呈指数增长,这与欧几里德空间中较慢的多项式增长相反。因此,本文探索双曲空间是否有助于学习图数据的嵌入,即通过使用神经网络对相互作用或关系进行建模,并利用数据所存在的流形度量结构来学习得到节点的低维紧凑特征向量表示。

通过对图表示学习方法和复杂网络中双曲几何理论进行分析,本文提出一种嵌入双曲层的神经排序式图表示学习方法Neural-HRNE。该方法利用神经网络的无监督端到端方式以及双曲几何的分层自组织能力来自动抽取节点的相似性和层次结构信息。Neural-HRNE方法没有使用过度复杂的节点交互机制,而是提出一种更小更快的神经排序架构来实现同样的性能。其中,利用贝叶斯个性化排序(Bayesian Personalized Ranking,BPR)[4]目标来捕获节点表示向量之间的局部拓扑结构相似性。文献[5]研究表明,在Lorentz模型中学习嵌入比在Poincaré球中更加有效,其不仅更适用于上下层级关系的建模,而且能非常有效地执行黎曼优化并避免由Poincaré距离产生的数值不稳定性问题。因此,在Neural-HRNE方法中,本文将距离度量转换为所嵌入双曲面模型中的度量,图中的节点能利用双曲几何特性自组织为分层结构,从而使得Neural-HRNE方法可以高效地提取节点的潜在特征表示。在学习得到节点的潜在特征向量表示后,本文在多个不同尺度的数据集上分别进行节点推荐和节点分类任务,通过对比几种不同空间中的图表示学习方法来验证所提方法的有效性,并分析其维度敏感性和模型收敛性。

1 相关工作

早期的图表示学习可追溯到2000年,当时的算法主要将图表示学习作为降维技术的一部分,通过特征分解图的关联矩阵来得到节点的特征向量。但是,就节点数量而言,多数算法通常至少具有二次时间复杂度,可扩展性较低限制了它们在大规模图上的应用[6]。与特征工程中需要人工设计特征不同,深度学习会自动从数据中学习特征表示,这使得特征工程向特征学习转变。近期的图表示学习方法主要集中于为图数据设计新的神经网络模型。DeepWalk[7]首先使用随机游走从输入图中采样一组路径,将采样的路径类比于来自语料库的句子,从而利用神经语言模型Skip-Gram学习得到节点的特征向量表示。DeepWalk的成功激发了许多后续的研究,如Node2vec[8]和LINE[9]等。使用递归神经网络模型GRU来嵌入信息的级联路径以及将邻接矩阵输入到自编码器中重构邻域相似的节点也是较典型的方法。作为另一种流行的深度学习模型,卷积神经网络及其变体也被广泛应用于图表示学习。自2008年以来,研究人员聚焦于直接为复杂网络设计有效且可扩展的表示学习技术,且其表现出了良好的性能并能适用于各种应用[6]。

2 模型构建

本文的图表示学习方法Neural-HRNE利用BPR来捕获节点之间的局部拓扑结构相似性,并通过双曲几何中的双曲面模型来有效探索图的拓扑结构信息,特别是层级结构。模型的整体架构如图1所示,该模型使用的神经网络结构主要包括输入层、嵌入层、隐藏层、双曲层、输出层和BPR层。具体而言,模型具有共享参数的2个部分,即一个接受正确的节点链接,另一个接受错误的节点链接,并旨在最大化正确链接和错误链接之间的差距。其中,嵌入层根据节点的局部邻居结构学习节点的统一矢量表示,隐藏层应用非线性降维嵌入节点的向量,双曲层使用双曲面模型来探索图的层次结构信息,即通过嵌入空间中的双曲面距离来建模节点对之间的关系,输出层和BPR层通过反向传播开启模型推断。

图1 Neural-HRNE模型整体架构

2.1 输入层和嵌入层

fu=LOOKUP(P,nu)

(1)

在具体实现过程中,本文使用预训练节点嵌入来初始化嵌入层,嵌入矩阵P在学习过程中迭代更新。

2.2 隐藏层

(2)

2.3 双曲层

(3)

(4)

因此,双曲层将节点之间的双曲距离定义为:

(5)

2.4 输出层和BPR层

Neural-HRNE方法通过式(6)的线性变换传递双曲距离:

s(hu,hi)=Wsd(hu,hi)+bs

(6)

(7)

(8)

Neural-HRNE方法的嵌入目标是最大化式(8)。为了便于计算,最小化负对数似然损失函数的和,如下:

(9)

2.5 优化和学习

算法1Riemannian Stochastic Gradient Descent

Inputlearning rateη,number of epochsT

for t=1,2,…,T

土地是财富之母，是我国农村人口的重要财富来源与财富象征；同时，土地是重要的生产和生活资料。贵州省山多地少，可以利用的土地资源稀缺，因此，充分利用好土地资源，通过政策、工程手段、科学技术等发挥其潜在价值，对于贵州省实施精准扶贫，帮助农村地区贫困人口摆脱贫困，走可持续发展的致富之路具有重要的理论意义和现实价值。

grad f(θt)←projθt(ht)

θt+1←expθt(-η grad f(θt))

3 实验结果与分析

将本文方法与现有学习方法进行比较,其中,选取一些常见的具有明确上下级层次结构的概念网络以及未明确编码对象层次结构关系的基准图数据集,以评估各方法的节点推荐和节点分类任务效果,最后分析各方法在不同表示学习空间中的性能,即在欧几里德、Poincaré和双曲面模型中分析各方法对维度的敏感性和模型的收敛性。

3.1 实验设置

本文考虑具有明确上下级层次结构的数据和非树状的有向无环图结构,数据集的相关统计信息如表1所示。其中:

1)WordNet[16]是一个庞大的英文词汇数据库,在WordNet中,名词、动词、形容词和副词各自被组成一个同义词网络,每个同义词集合都代表一种基本的语义概念,本文嵌入WordNet的名词和动词层次结构。

2)ACM计算分类系统CCS[17]是由ACM计算机协会设计的用于分类计算机主题的系统,其可看作一种分层本体,各种ACM期刊使用该系统来按领域组织主题。

3)DBLP是来自DBLP数据集[18]的作者网络,其中包括共同作者、作者引用和文本相似性视图。本文抽取DBLP中的研究人员的共同作者图,其标签表明研究人员发表其研究成果的领域,本文选择其中的“数据库”“数据挖掘”“信息检索”和“机器学习”4个不同的研究领域作为标签。

4)PPI是蛋白质分子之间构建的蛋白质-蛋白质相互作用网络[19]。本文使用PPI网络的智人诱导子图,只有人类基因被保留为节点。Hallmark基因集中提供的基因组被视为节点的类别并代表蛋白质生物状态。

5)Wikipedia[20]是一个维基百科中储存前100万字节中单词的共现网络。在该数据集中,每个节点都是一个单词,每条边是单词之间的共现关系,每个节点都有一个标签,表示单词的POS词性。

表1 数据集的相关统计信息

在对比实验中,所有方法均只使用节点的拓扑结构特征,选取一些基于欧几里德的神经网络嵌入和基于双曲空间的图嵌入方法。本文将Neural-HRNE双曲层中的双曲面度量替换为欧几里德和Poincaré度量并以此来作为其中的对比基线。对比方法具体如下:

1)DNGR[21]采用随机冲浪策略来捕获图结构信息,并进一步将这些结构信息转换为正点互信息矩阵,然后训练堆栈降噪自编码器以学习节点表示。

2)HARP[22]递归地合并原始图中的节点和边以获得具有相似性的一系列较小的连续图结构体,合并的图均具有不同的粒度,从而提供了原始图的全局结构视图。HARP可作为一种通用的元策略来改进图嵌入算法,本文选取文献[22]中表现较好的HARP(N2V)方法,其结合了Node2vec算法用于加强节点嵌入。

3)文献[14]提出了一种双曲空间中图的神经嵌入算法,其采用与DeepWalk类似的方法,不同的是该算法不再使用欧几里德度量,而使用Poincaré度量并在双曲空间中通过反向传播来学习节点的向量表示。

4)文献[13]提出一种基于黎曼流形的“测地线凸锥”模型来学习层次嵌入,其有效解决了Order嵌入[23]和Poincaré嵌入[10]中嵌入空间维度灾难、不能编码不对称关系和Poincaré球边界坍塌问题。

本文嵌入模型中有若干用户定义的超参数。其中,隐藏层中的神经元数量设置为150,嵌入模型中的正则化系数λ设置为0.000 05。在模型学习和优化过程中,设置学习率η为0.5,批量大小定为100。对于其他对比方法,使用网格搜索从集合{0.01,0.001,0.000 1}中选择正则化系数,并从集合{0.01,0.05,0.1,0.5}中选择学习率。对于其余的超参数,本文使用各方法在原文中所建议的默认参数值。设置所有节点的表示维度为50维。

3.2 节点推荐

节点推荐可用于相似性搜索等领域,其任务是根据自身的上下文向用户推荐感兴趣的对象。在现实场景中,推荐的节点有各种类型,如用户兴趣、社交朋友和查询文档等。使用表示学习的低维矢量通常比原始表示密集得多,这减轻了较多数据的稀疏性问题,使得查询任务更加简单和准确。

根据多数图表示学习中的评估方法,本文对于给定的查询节点,计算目标节点与查询节点间的距离并对目标节点进行排序。在实验中,评估本文所提方法在嵌入明确或隐含层级结构数据上的有效性。在评估过程中,本文分别使用上述5个数据集来评估嵌入质量,并将数据视为无向传递闭包,这样的分层结构不能从观察到的边直接得出,而需要被推断出来。为了测量嵌入质量,本文计算每个观察到的边(u,v)在嵌入空间中的相应距离d=(u,v),并按升序排列u的所有未观察到的边的距离,即{d=(u,v′):(u,v′)∉D},得到原始的正确元组排名(越低越好),然后计算所有正确节点的前50平均精度均值MAP@50,结果如表2所示,其中,最优结果加粗表示。

表2 MAP@50结果对比

从表2可以看出,因为双曲几何的分层自组织能力,其所选择的使用双曲空间的表示学习方法比欧几里德空间中的方法更加有效,特别是当学习的特征维度较低时,双曲几何能得到更加紧凑的表示,所以能够更好地在有限空间中表示复杂函数。相比于双曲几何强层次嵌入方法,本文方法也表现出了较好的表达力,显示出其性能优势。

3.3 节点分类

节点分类通过在标记的节点嵌入集上应用分类器来进行训练,即给定未标记节点的特征向量表示,训练的分类器可以预测其类标签。由于WordNet是一个词典且CCS通常作为分类法使用,没有可利用标签,因此本文仅使用DBLP、PPI和Wikipedia数据集来评估嵌入表示的监督学习任务效果,即节点分类的有效性。

本文从数据集中随机抽取不同比例的标记节点,并将它们用作训练数据,其余的作为测试数据。对于欧几里德模型,本文使用LibLinear库中的one-vs-rest SVM分类器预测每个节点最可能的标签,而对于双曲模型,本文使用基于双曲距离的内核训练SVM分类模型。重复上述过程10次,表3和表4所示为DBLP、PPI和Wikipedia数据集中的各方法平均性能表现,最优结果加粗表示。

表3 DBLP数据集上的准确率对比

表4 PPI和Wikipedia数据集上的节点多标签分类Macro-F1结果

从表3、表4可以看出,相比于经典的基于欧几里德空间的方法,双曲几何对于数据的层次结构特征抽取更加有效,这有助于轻松高效地处理各种下游图数据分析任务。随着分类训练数据的增加,各分类器的性能均在不断提高,而对比于同等情况下使用欧几里德嵌入的EuclideanEmb,本文提出的图表示学习方法在Poincaré和双曲面模型中性能均有所提高。在同是使用了双曲几何自组织能力的方法中,Neural-HRNE的结果基本持平或略微降低,这可能是由于Neural-HRNE中的节点采样策略过于简单,未探索到节点之间诸如同质性或结构等价性的关系,或者所设计的神经网络较为浅层并直接使用了One-hot来初始化该神经网络,导致方法学习性能有所降低。因此,下一步考虑探索结合复杂网络和机器学习的更加高效的采样策略和更加强健的神经网络,以提高Neural-HRNE方法的性能。

3.4 模型性能分析

为了进一步说明双曲面模型对图表示学习性能的影响,本文选取仅改变双曲层设置的表示学习方法进行比较。具体地,分别在EuclideanEmb、PoincaréEmb和Neural-HRNE方法中测试模型对表示学习维度的敏感性和模型的收敛性。图2所示为不同空间学习方法在WordNet名词层的维度敏感性和收敛性。图2(a)为仅改变表示学习的维度后对WordNet名词层的节点推荐结果MAP@50的影响,从中可以看出,相比于欧几里德几何,双曲几何对空间的使用效率更高,欧几里德嵌入在维度较低时对特征的表达能力较弱,而双曲几何能在较低的维度时依然具有较好的表现性能,双曲几何大约在50维时就趋于稳定,其比欧几里德更能提供紧凑的特征向量表示。图2(b)为EuclideanEmb、PoincaréEmb和Neural-HRNE模型在50维时对WordNet名词层中节点特征表示学习的收敛情况。从中可以看出,本文提出的神经排序网络大约在10个时期内收敛,与欧几里德嵌入相比,双曲几何的嵌入方法收敛更快,损失误差更低。

图2 3种方法在WordNet名词中的维度敏感性和 模型收敛性结果对比

对不同空间中图表示学习方法的维度敏感性和模型收敛性进行分析,结果表明,相比于欧几里德嵌入,双曲几何能提供更高质量的嵌入,特别是在学习维度较低的情况下。本文提出的双曲面模型表现出与Poincaré模型相当的性能,且其神经网络模型具有高效的学习能力。

4 结束语

如何对图中的节点进行有效的特征表示一直是图挖掘领域的研究热点。本文提出一种嵌入双曲层的神经排序式图表示学习方法,以提取节点的相似性和层次结构特性。该方法利用贝叶斯个性化排序作为其目标函数,并在其中加入一层双曲层来度量节点对之间的局部拓扑结构相似性,利用黎曼梯度下降来学习更高效的节点特征向量表示。对比使用欧几里德、Poincaré和双曲面模型的不同表示学习方法的性能,结果表明,本文所提方法能够更高效地学习节点特征,而且可以获得更加紧凑、更具表达力的特征向量表示。嵌入双曲空间中的层次结构能很好地获取数据的基础语义,下一步将探索双曲空间的优化方法以提高嵌入质量并获得更快的收敛速度。此外,将双曲嵌入有效地整合到下游的任务和应用中,以及在多关系数据或图像等更复杂的数据嵌入中应用双曲几何理论,也是今后的研究重点。