基于融合元路径权重的异质网络表征学习①

蒋宗礼,陈浩强,张津丽

(北京工业大学 信息学部,北京 100124)

随着互联网技术的不断发展,现实生活中出现了大量的信息网络,如社交网络、论文引用网络、电商信息网络.信息网络中包含丰富的数据信息,对这些数据进行多角度、多层次的分析具有重要意义.例如,分析电商信息网络中用户购物数据可获知用户的喜好信息,进而可优化电商系统中的商品推荐系统.但是,信息网络中一般包含数百万个数据节点和节点之间的连接(称为“边”),因此在原始信息网络中执行复杂的推理、操作将消耗大量计算资源.目前,一种行之有效的解决方法是对信息网络进行网络表征学习以降低信息网络中数据的表示维度.网络表征学习可将信息网络中节点或者边映射到低维向量空间,即通过降维处理,得到节点或者边的低维、实值、稠密的向量形式,并且在低维空间中具有表示以及推理能力[1].

目前,信息网络表征学习研究中大部分工作聚焦于同质信息网络(信息网络中包含单一类型的节点及单一类型的边)[2].比如,Perozzi B等[3]首次提出以随机游走为基础的网络表征学习模型DeepWalk.该模型将信息网络中数据节点视为单词,节点序列视为句子,然后通过随机游走构建由节点序列组成的语料库,进而结合自然语言处理领域中Skip-gram[4]模型学习信息网络中节点的低维表征.其实验结果表明随机游走技术可有效提取信息网络中结构信息并应用于节点的表征学习.在DeepWalk的基础上Grover A等[5]提出了应用深度优先随机游走和广度优先随机游走提取信息网络中结构信息并结合Skip-gram模型的Node2Vec网络表征学习模型.相比于DeepWalk模型Node2Vec模型在信息网络的低维表征中保留了更多的结构信息,其在分类实验中的准确率同样优于DeepWalk模型.除应用随机游走技术获取信息网络中结构信息进行表征学习外,Tang J[6]提出了应用节点间一介相似性和节点间二阶相似性提取网络结构信息进行表征学习的LINE 模型.此外,Yang C[7]、Cao SS[8]、Tu CC[9]等还提出了基于矩阵分解的网络表征学习方法.

相比于同质信息网络,异质信息网络中包含多种类型的数据节点或者边[10],导致同质信息网络的表征学习方法不适用于异质网络.异质网络表征学习中元路径是一个极其重要的概念,Shi C等[11-13]对此进行了整理、研究.这些研究发现元路径可表示节点类型间的复合关系,不同元路径表示不同的语义信息,基于不同元路径的表征学习方法可造成不同的分析结果和特征表示.此外,Zhang JL等[14]利用不同元路径表示的语义信息对异质信息网络进行表征学习.在元路径的基础上Dong YX等[15]提出了Metapath2Vec异质信息网络表征学习模型.该模型首次应用基于元路径的随机游走获取异质网络中的结构信息并结合Skip-gram模型学习异质网络中节点的低维表征,从而在低维表征中融入元路径所表示的语义信息.但是,该模型仅基于单条元路径对异质网络进行随机游走以获取异质信息网络的结构信息.然而异质信息网络中存在多条元路径,导致Metapath2Vec模型学习的低维表征中缺失原始网络中部分结构信息和其它元路径表示的语义信息.

针对上述问题,本文提出了基于融合元路径权重的异质网络表征.该表征学习方法首先针对异质网络提取元路径集合,然后学习元路径权重并以此为基础对基于不同元路径的低维表征进行加权融合,得到一个低维、实值、稠密且融合不同元路径语义信息的异质网络表征.该低维表征中包含丰富的结构信息以及不同元路径表示的语义信息.本文的主要贡献可概括为以下3点：

(1)在异质网络表征学习中引入元路径权重,通过对基于不同元路径的低维表征进行加权融合,解决了低维表征中缺失原始网络中结构信息以及缺失其它元路径表示的语义信息问题.

(2)基于融合元路径权重的异质网络表征学习在不同数据规模的异质网络中具有良好的表征学习能力,并可有效应用于数据挖掘.

(3)在实际数据集上进行的对比试验验证了基于融合元路径权重的异质网络表征学习方法的正确性、有效性.

1 基本概念

信息网络[12]用于表示由数据节点以及节点之间联系组成的数据网络,可定义为有向图.

定义1.信息网络G=(V,E),其中V表示信息网络中数据节点的集合,E表示节点之间边的集合.定义映射函数 Φ :V→A表示节点与节点类型之间的映射关系,即对任意节点v∈V都有唯一的节点类型 Φ(v)∈A与之对应.定义映射函数 Ψ :E→R表示边与边类型之间的映射关系,即对任意一条边e∈E都有唯一的边类型Ψ(e)∈R与之对应.当节点类型数|A|＞1或者边类型数|R|＞1时,该信息网络为异质信息网络.

如图1(a)所示,作者合著网络为同质信息网络,其中只包含作者类型的数据节点以及表示节点之间合著关系的边.图1(b)所示的学术文献网络为异质信息网络,其中包含3种节点类型,分别为作者、文章、会议.同时,包含两种边类型,分别用于表示作者与文章之间的撰写与被撰写关系以及文章与会议之间的发表与被发表关系.

网络模式[10]是信息网络G=(V,E)的元级描述.

定义2.网络模式TG=(A,R).其中A为信息网络G中节点类型集合,R为信息网络G中边类型集合.

例如,在图1(b)的基础上可定义学术文献网络的网络模式.如图1(c)所示,该网络模式为由3种节点类型和两种边类型构成的有向图.

在网络模式的基础上可定义元路径[16],用于表示节点类型间的复合关系.

定义3.给定异质信息网络的网络模式TG=(A,R),其元路径定义为即在节点类型A1与Al+1之间定义长度为l的复合关系Rc=R1°R2°···°Rl,其中 ° 表示关系间的复合算子.

元路径不仅刻画了对象之间的语义关系,而且能够提取对象之间的特征信息[16].例如,根据定义,可基于图1(c)中的网络模式定义学术文献网络的元路径,如APA、APCPA、APAPA等.不同元路径表示不同的语义信息,比如,APA表示两个作者合著完成了一篇文章,而APCPA则表示两个作者在同一个会议中发表了文章,前者语义中侧重于文章,后者则侧重于会议.

异质信息网络中存在多条元路径,基于不同元路径的表征学习方法可造成不同的分析结果和特征表示.为表示不同元路径对异质网络表征学习的重要程度,本文对元路径赋予相应的权重值.

定义4.元路径集合P={p1,p2,···,pn},对于任意一条元路径pi∈P都有权重wpi与之对{应,各条元路径的权重值构成元路径的权重集合其中wp1+wp1+···+wpn=1.

网络表征学习[17]用于降低信息网络中数据节点的表示维度.

定义5.对于给定的信息网络G=(V,E),网络表征学习的目标是通过对目标函数fG=V→Ld的学习将信息网络中的节点在低维空间Ld中进行向量表示,从而得到信息网络的低维表征M∈ R|V|×d,其中d≪|V|.低维空间Ld中的低维表征需尽可能保留原始信息网络中的结构信息,以便低维表征在低维空间中具有良好的表示、推理能力.

图1 信息网络及网络模式

2 基于融合元路径权重的异质网络表征学习

异质网络表征学习中元路径具有刻画对象之间语义关系以及能够抽取对象之间特征信息的特点,经常用于指导获取异质信息网络的结构信息.异质信息网络中不同元路径表示不同的语义信息,因此基于不同元路径的表征学习方法可造成不同的分析结果和特征表示.但是,现有的异质网络表征学习方法往往采用单条元路径提取节点间结构信息,进而学习节点的低维表征.导致学习到的低维表征中缺失原始信息网络中部分结构信息及其它元路径表示的语义信息,影响低维表征在低维空间中的表示、推理能力,进而影响其在数据挖掘任务中的有效性.基于融合元路径权重的异质网络表征学习方法学习到的低维表征融合了不同元路径表示的语义信息,在低维空间中具有良好的表示、推理能力,提高了低维表征在数据挖掘任务中的有效性.如图2所示,基于融合元路径权重的异质网络表征学习方法包含4个处理阶段：阶段1用于构建元路径集合.阶段2对元路径集合进行权重学习.阶段3根据元路径集合学习各个元路径所对应的异质信息网络的低维表征.阶段4将基于元路径权重对各个低维表征进行融合.

2.1 阶段 1：构建元路径集合

此阶段首先根据实际生活中的异质信息网络定义其网络模式.对异质信息网络G=(V,E),其节点类型数|A|＞1或者边类型数|R|＞1,定义其网络模式为TG=(A,R).然后,基于网络模式定义不同的元路径pi,从而构建异质信息网络的元路径集合P={p1,p2,···,pn}.

2.2 阶段 2：元路径权重学习

目前,多个研究发现不同元路径对异质网络表征学习的重要程度不同[14,16,18].因此,阶段2中应用HeteClass[18]框架中的元路径权重学习思想对阶段1中

应用上述元路径权重学习思想实现了元路径权重学习程序并对元路径集合P={p1,p2,···,pn}进行权重学习,以此计算元路径的权重并构建元路径的权重集合

图2 基于融合元路径权重的异质网络表征学习

2.3 阶段3：异质信息网络的表征学习

阶段3将根据元路径集合对异质信息网络进行表征学习.本文采用基于元路径的随机游走技术[15]获取异质信息网络中节点序列集,结合Skip-gram[4]模型学习异质信息网络的低维表征.

基于元路径的随机游走技术是Dong YX[15]等人提构建的元路径集合进行权重学习,为元路径赋予权重值,以此表明不同元路径对异质信息网络表征学习的重要程度.

HeteClass框架是Gupta M等[18]提出的一种基于元路径的直推式分类框架.该框架提出了一种基于目标类型对象之间关联程度的元路径权重学习方法.该方法以最大化相同标签对象之间的相关性,同时最小化不同标签对象之间的相关性为思想提出了式(1)所示的损失函数.其中 θk表示第k个元路径的重要程度,vi,vj表示带标签的目标类型对象.Sign为符号函数,用于表示目标类型对象是否具有相同标签信息,若相同值为1,否则值为-1.Simpk为目标对象的相关性矩阵[19].λ为正则化系数,‖·‖为 ℓ2范数.该学习方法通过最小化目标函数计算元路径权重.出的一种基于元路径的图随机遍历技术.对于给定的异质信息网络G=(V,E)和元路径随机游走的起始节点为A1类型节点,第i+ 1个游走节点的选择概率如式(2)所示.其中表示At类型的节点,表示节点的邻域中At+1类型的节点数量.第i+ 1个游走节点应从节点的所有At+1类型的邻居节点中随机选择.基于节点选择概率,随机游走将在元路径的指导下游走出包含元路径语义信息以及异质信息网络中结构信息的节点序列.

Skip-gram模型是Mikolov T等[4]提出的用于自然语言处理中学习大型数据集中单词的连续向量表征的神经网络模型.Skip-gram模型具有三层网络结构,分别为输入层、隐藏层和输出层,并提出了式(3)所示的损失函数[20].其中,C为上下文中单词数量,V为语料库中单词数量,wI表示输入的单词,wO,i表示第i个输出的上下文单词,j*c为输出层输出的第c个上下文单词在语料库中的真实索引,u表示单词从隐藏层到输出层过程中的计算分数.该模型输入为由文本中句子构成的语料库,通过最小化损失函数,学习语料库中单词的低维表征.

目前,DeepWalk[3]、Node2Vec[5]、Metapath2Vec[15]等研究发现将信息网络中节点信息映射为自然语言可应用Skip-gram模型学习信息网络中节点的低维表征.基于元路径的随机游走技术可提取包含元路径语义信息、网络结构信息的节点序列,从而将异质信息网络中的节点信息映射为自然语言,进而可结合Skip-gram模型学习异质信息网络中节点的低维表征.

如图2中阶段3所示,首先应用基于元路径的随机游走技术获取异质信息网络中的节点序列.对任意元路径pi∈P获取其相应的节点序列集cpi并构建语料库集合C={cp1,cp2,···,cpn}.

对语料库集合中任意一个节点序列集cpi应用Skip-gram模型学习异质信息网络的低维表征Mpi.此时,任意元路径pi都有唯一的低维表征Mpi与之对应.各个低维表征构成了基于不同元路径的低维表征集合M={Mp1,Mp2,···,Mpn}.

2.4 阶段4：基于元路径权重对低维表征进行融合

此阶段基于元路径权重集合W={wp1,wp2,···,wpn}对低维表征集合M={Mp1,Mp2,···,Mpn}进行加权融合.对于任意的低维表征Mpi均基于相应的元路径pi,所以低维表征Mpi中仅包含元路径pi所表示的语义信息,导致基于单一元路径的低维表征中缺失其它元路径表示的语义信息.而元路径因语义信息的不同对表征学习的重要程度不同,从而具有不同的权重.所以对基于不同元路径的低维表征进行加权融合可得到融合不同元路径语义信息的低维表征,从而提高低维表征质量.因此,本文提出了式(4)所示的低维表征融合公式,并基于该公式实现了基于元路径权重的低维表征融合算法.

如算法1所示,该算法的输入为元路径权重集合、低维表征集合以及低维表征维度,然后依次对低维表征中d个特征分量进行加权融合,得到融合不同元路径语义信息的低维表征MW.低维表征MW不仅包含不同元路径的语义信息,而且还包含丰富的网络结构信息.以上特点使得基于融合元路径权重的低维表征在低维空间中具有良好的表示、推理能力,并且可有效应用于数据挖掘任务.

算法1.基于元路径权重的低维表征融合算法images/BZ_36_1632_2616_1903_2653.pngimages/BZ_36_2137_2616_2262_2653.pngimages/BZ_36_1290_2667_1457_2705.png输入：元路径权重集合,低维表征集合,维度d images/BZ_36_1775_2723_1825_2752.png输出：融合元路径权重的低维表征images/BZ_36_1375_2769_1554_2798.png1.for doimages/BZ_36_1324_2824_1953_2857.png2.3.end for

3 实验结果与分析

为证明本文提出的基于融合元路径权重的异质网络表征学习方法的正确性以及在数据挖掘任务中的有效性,本文对实际数据集进行了节点分类对比试验.

3.1 实验数据集

实验所用数据集为AMIner[15,21]数据集,该数据集为典型的异质学术文献信息网络.如表1所示,该数据集中包含作者、文章、会议3种节点类型,共计4891 819个数据节点,其中246 678个带标签的作者节点被分为8个类别,分别为Computing Systems,Theoretical Computer Science,Computer Networks & Wireless Communication,Computer Graphics,Human Computer Interaction,Computational Linguistics,Computer Vision &Pattern Recognition,Databases & Information Systems.

表1 AMIner数据集中的节点

如表2所示,AMiner数据集中共包含12 518 144个边,其中表示文章与作者之间撰写与被撰写关系的边共9323 739个,表示文章与会议之间发表与被发表关系的边共3194 405个.

表2 AMIner数据集中的边

此外,本文在AMIner数据集的基础上构建数据规模较小的子数据集AMIner-Small,用于验证本文提出的基于融合元路径权重的异质网络表征学习方法对不同数据规模的异质信息网络的表征学习能力.如表3所示,AMIner-Small数据集中数据规模远远小于AMiner数据集.

表3 AMIner-Small数据集中的节点

3.2 评价指标

在分类实验中,数据的低维表征质量对实验结果具有重要影响,因此本文通过实验结果评价低维表征质量,进而分析异质网络表征学习方法的正确性、有效性.

本文采用分类精确率(Precision)、召回率(Recall)、Micro-F1分数、Macro-F1分数评价分类实验结果,从而评价不同异质网络表征学习方法的正确性、在数据挖掘任务中的有效性.

分类精确率为预测为正类的样本中实际为正类的样本比例.召回率表示预测为正类的样本数占全部正类样本数的比例.F1分数(Micro-F1分数、Macro-F1分数)表示精确度和召回率的加权平均值.以上4个评价指标值越高表示分类实验越精确,相应的低维表征质量越高、异质网络表征学习方法越正确、有效.

3.3 节点分类实验

3.3.1 AMIner-Small数据集的节点分类实验

采用HIN2Vec[17]异质网络表征框架作为对比实验方法.不同于之前基于Skip-gram模型的表征方法,HIN2Vec核心是一个神经网路模型,并且将元路径视为节点间的不同类型关系,然后通过捕获节点间不同类型关系学习节点的低维表征.

首先在AMIner-Small数据集的基础上构建元路径集合并学习各个元路径的权重.权重学习实验重复十次,结果如表4所示,其中APA的权重均值为0.01,APAPA的权重均值为0.02,APCPA的权重均值为0.97.根据元路径权重学习结果发现在AMIner-Small数据集中元路径APCPA表示的语义信息对异质网络表征学习的重要程度远高于APA、APAPA表示的语义信息,而APA、APAPA表示的语义信息对异质网络表征学习的重要程度则十分接近.

表4 元路径及其权重

在元路径集合及权重的基础上分别应用本文提出的基于融合元路径权重的异质网络表征学习方法以及HIN2Vec框架学习AMIner-Small数据集中节点的低维表征.然后将带标签的675个作者节点的低维表征作为特征向量训练和测试SVM分类器.分类实验中将675个低维表征按70%/30%比例随机分为训练数据集与测试数据集,分类结果是取10次实验结果的均值.具体实验结果如表5所示,其中FMPW表示本文提出的基于融合元路径权重的异质网络表征学习方法.

表5 AMIner-Small数据集中作者节点分类结果

根据实验结果发现本文提出的基于融合元路径权重的异质网络表征学习方法在分类精确率、召回率、Micro-F1分数、Macro-F1分数上均明显高于HIN2Vec方法.该结果表明基于融合元路径权重的异质网络表征学习方法对小规模异质网络具有良好的表征学习能力,证明了该方法的正确性、有效性.

3.3.2 AMIner数据集的节点分类实验

由于AMIner数据集中数据规模远大于AMiner-Small数据集,导致HIN2Vec不能处理AMiner数据集,所以本文采用Metapath2Vec[15]异质网络表征方法作为对比实验方法.Metapath2Vec应用基于单条元路径的随机游走获取异质网络中的结构信息并结合Skip-gram模型需学习异质网络的低维表征.

此部分实验中,实验步骤与AMIner-Small数据集中分类的实验步骤一致,首先提取元路径APA、APAPA、APCPA构成元路径集合并学习其权重,然后分别采用本文提出的基于融合元路径权重的异质网络表征学习方法和Metapath2Vec方法学习AMIner数据集中节点的低维表征.

元路径权重学习的实验结果与AMIner-Small数据集中的元路径权重学习结果一致,即APA的权重均值为0.01,APAPA的权重均值为0.02,APCPA的权重均值为0.97.该结果表示在AMIner数据集中APCPA表示的语义信息对异质网络表征学习的影响程度最大.

本文在全部节点的低维表征中随机挑选47 108个带标签的作者的低维表征作为SVM分类器的特征向量,其中训练集比例为10%～90%,其余节点为测试集.实验重复十次并取平均值,结果如图3所示,其中FMPW表示本文提出的基于融合元路径权重的异质网络表征学习方法.

根据实验结果可知,随着训练集比例的提高,分类结果越加精确.而且本文提出的基于融合元路径权重的异质网络表征学习方法的分类精确率、召回率、Micro-F1分数、Macro-F1分数中均明显高于基于元路径APA和基于元路径APAPA的Metapath2Vec方法,但是仅率高于基于APCPA的Metapath2Vec方法.造成以上结果的原因在于,元路径APCPA的 权重为0.97,导致融合不同元路径的低维表征中APCPA对应的低维表征占主要比例.该结果从侧面验证了元路径权重学习结果的正确性.此外,基于图3所示的实验结果发现基于不同元路径的Metapath2Vec方法学习的低维表征质量差别大,导致应用Metapath2Vec方法学习异质网络的低维表征时结果具有不确定性.而本文提出的基于融合元路径权重的异质网络表征学习方法可得出最优结果,从而有效解决上述问题.

3.4 实验分析

综合以上实验结果可知,基于融合元路径权重的异质网络表征学习方法可应用于不同数据规模的异质网络,并且在不同数据规模的异质网络中分类实验结果优于基准方法HIN2Vec和Metapath2Vec.因此本文提出的基于融合元路径权重的异质网络表征学习方法对不同数据规模的异质网络具有良好的表征学习能力,可学习得到高质量的低维表征,可有效应用于数据挖掘任务,并且优于基于单条元路径的异质网络表征学习方法.

4 结论

本文提出基于融合元路径权重的异质网络表征学习方法,通过元路径权重学习表明元路对异质网络表征学习的重要程度,并以此为基础对基于不同元路径的低维表征进行加权融合,得到融合不同元路径语义信息的异质网络表征.该方法解决了基于单条元路径的异质网络表征学习方法不能包含其它元路径语义信息而导致的低维表征中缺失结构信息、语义信息的问题.同时通过对比试验证明本文提出的基于融合元路径权重的异质网络表征学习方法在不同数据规模的异质网络中具有良好的表征学习能力,并且可有效应用于数据挖掘任务.在未来的工作中,将对如何提高大规模异质网络的表征学习效率进行深入研究.