基于元路径与节点属性的合著关系预测

张雪婷，程 华，房一泉

华东理工大学 信息科学与工程学院，上海200237

链接预测[1]作为社会网络分析的核心任务之一，通过网络节点及网络拓扑等信息预测网络中尚未连接的两个节点间存在链接的可能性。传统的链接预测面向同构社会网络，即只包含一种类型的节点和连接。大多数现实网络，如学术网络[2]、患者网络[3]和生物信息网络[4]都是异构社会网络，包含多种类型的对象和关系。异构社会网络的数据挖掘已成为新的问题和挑战，是近几年的研究热点。

Ströele 等[5]提出了基于节点度、共同邻居以及Katz系数三个指标的异构社会网络链接预测算法，用于合作网络中隐含关系的预测。Dong 等[6]提出Metapath2vec算法，基于元路径随机游走确定节点表示，完成节点分类、链接预测等任务。Lu等[7]提出Rhine算法，在文献[6]基础上引入隶属关系（ARS）和交互关系（IRS），捕捉异构网络的隐含信息，提高链接预测的准确度。

本文在用Metapath2vec 算法获得基于元路径节点表示的基础上，用TF-IDF算法赋予论文节点语义属性，提出异构节点的复合表示方法。在路径表示上，提出将元路径上的异构节点按类别重构多条单类型节点路径的方法，构建基于节点类型的元路径表示，并将路径信息融合得到路径的网络表示。卷积神经网络有利于挖掘链接序列节点间的隐含拓扑关系[8]，通过多次卷积实现异构社会网络节点间的链接预测。实验表明，本文方法比其他方法在预测合著关系上有更高的准确率，预测模型也有更强的稳定性。

1 问题描述

定义1（异构社会网络（Heterogeneous Social Network））表示为G=(V,E)，其中V 表示网络中所有的节点集合，E 表示节点关系的连接集合。有α:V →O 表示节点类型的映射函数，β:E →R 表示连接类型的映射函数。任意节点v ∈V 属于某一节点类型α(v)∈O，任意连接β(v)∈R 属于某一关系类型e ∈E。

在异构学术网络中，包含3 种类型节点：论文节点(P)、作者节点(A)、会议节点(C)，如图1。常预测的关系有合著关系(A-A)、投录关系(P-C)、论文引用关系(P-P)等，其中合著关系、论文引用关系为隐性关系。研究合著关系可以帮助学者更好地了解潜在的科研合作关系；也可以帮助追踪分析其他科研人员的研究方向，更高效地分享学术资源、交流科研观点。

图1 异构学术网络

定义2（网络模式（Network Schema））是异构社会网络G 的元模型，表示为TG=(O,R)，其中O 表示节点集合，R 表示关系集合。

异构学术网络的网络模式如图2，O={P,A,C},R={P-A,P-C}。

图2 异构学术网络的网络模式

定义3（元路径（meta-path）[9]）定义在网络模式TG上，表示连接两个节点且包含节点边缘类型关系的序列。元路径可形式化表示LR：

其中，N1表示元路径的起始节点，Np表示元路径的终点节点，Ri表示相邻节点Ni与Ni+1间的关系。节点N1和节点Np之间的组合关系记为：R=R1∘R2∘…∘Rp-1，其中∘是关系的组合运算。

元路径作为异构社会网络中重要且独有的概念，可以表示节点间关系和路径的语义信息。本文预测元路径下作者间的合著关系，A-A 间的元路径可以表示为：

其中n1,n2∈[0,1]，n∗∈N。

图3（a）为“作者-论文-作者-论文-作者”(APAPA)元路径，表示从给定作者开始，通过其论文的合著作者，找到该合著作者的其他合著论文作者；图3（b）为“作者-论文-会议-论文-作者”(APCPA)元路径，表示从给定作者开始，通过该作者投稿过论文的会议，找到该会议的其他论文作者。两个待预测节点间不同的元路径反应了不同的路径结构及语义信息，得到的预测结果也应不同。

图3 元路径示例

2 异构节点的向量化表示学习

基于网络表示学习[10]，可将网络中的节点表示为低维稠密的空间向量，利用深度学习等方法可实现节点分类、链接预测以及网络重构等任务。常见的网络表示算法包括基于随机游走的Metapath2vec 算法[6]、Line 算法[11]及Node2vec 算法[12]；基于深度学习的GCN 算法[13]、SDNE算法[14]；基于矩阵分解的GF算法[15]。面向异构社会网络，本文综合考虑元路径和节点属性两个因素，实现节点的向量化表示。

2.1 基于元路径的向量化表示

Metapath2vec 算法解决了异构社会网络中基于元路径的向量化表示。基于给定元路径指导随机游走的节点跳转，保存元路径邻居节点信息，通过计算节点与邻居节点在给定元路径上的条件概率来学习节点的唯一嵌入表示。在给定元路径LR中，第i 步的转换概率为：

利用异构的skip-gram模型生成能够捕捉语义信息和不同节点类型的表示，模拟路径中节点之间的结构相关性。即在同构skip-gram 模型的基础上，添加了对不同节点类型的叠加。对于给定节点v，最大化其异构上下文邻居节点的概率：

Nt(v)表示节点类型为t 的邻居节点ct所构成的集合，P(ct|v;ϑ)通常被定义为softmax函数，有：

其中，Xv表示节点v 的特征表示。

2.2 基于节点语义的向量化表示

对于学术网络中的论文节点，其论文名可以表征论文内容，论文节点包含语义特征。本文引入TF-IDF 算法[16]，计算论文节点的语义信息。TF-IDF算法描述了词在文本中的重要性，根据字词在文本中出现的次数和在整个语料中出现的频率来计算词在整个语料中的重要程度。词频TF 统计文本中词的出现频率，是一个特定条件下词项概率分布的交叉熵。逆文本频率IDF 反映了词在所有文本中出现的频率：

N 代表语料库中文本的总数，N(x)代表语料库中包含词x 的文本总数，有：

在论文节点中，TF-IDF 算法用出现词语的频次来突出论文主题，用出现词语的逆文档频率来突出论文标题的独特性，可以有效地提取论文标题文本的语义信息。通过TfidfVectorizer把原始的论文标题集合转化为TF-IDF 的特征矩阵，通过计算每个论文节点的TF-IDF值以完成语义表示。

2.3 节点的复合向量化表示

异构社会网络中的节点，均可以采用2.1节和2.2节中的两种方法分别进行向量化表示，包含元路径信息的向量表示为Mx，包含节点语义属性的向量表示为TFx。

对于论文节点，其语义信息明显，可以综合元路径信息和语义属性，构建复合的向量表示为TMx。本文通过全连接层对TFx向量降维处理，降低了预测模型的时间及空间复杂度，还避免了向量维数较大带来的信息不对等：

将处理后的语义向量和结构向量拼接，即可实现节点的复合向量化表示。

3 合著关系的链接预测

卷积神经网络在图像、文本分类等方面都取得了很好的效果，Li 等[17]提出了一种级联的卷积神经网络，利用多次CNN 挖掘复杂网络的深度信息，提高预测准确度。在网络表示中可用CNN提取多个同类型节点的联合特征，而在关系预测中可用CNN 构建分类模型以完成链接预测。本文分别基于元路径序列和节点类型的网络表示，构建对应的链接预测模型。

3.1 基于元路径序列的链接预测模型

异构社会网络可以表示为不同元路径序列的组合，且元路径的长度可能不同。元路径长度增长，网络基于元路径游走的时间呈指数倍增加，而链接预测的准确率却随路径长度的增长而降低[18]。考虑到学术网络为密集网络，路径越长得到的路径越多，影响计算效率及准确率，本文选用合著关系(A-A)间步长不大于4的元路径，包括APA、APAPA、APCPA。元路径APA 被视为本研究的真值路径，故本文仅研究两类元路径APAPA 和APCPA，其序列提取过程如图4。

图4 从异构社会网络中提取元路径

在元路径表示中，分别对作者节点、论文节点、会议节点取向量化表示MA、TMP、MC，按元路径序列顺序拼接成元路径表示矩阵，如图5（a）。图5为基于元路径APCPA 下的链接预测模型，向量化后的矩阵表示记为：RAPCPA+TMP。通过CNN的多次卷积运算提取元路径序列相邻节点间的隐含结构特征，实现链接预测。

该模型的链接预测部分（图5（b））构建多层卷积神经网络。每经过一次卷积层都会经过一次最大池化层，卷积神经网络输出的特征值在长和宽方向上都会减小为原来的二分之一，感受野扩大为原来的二倍。最后经过全连接层和softmax 分类器层，实现合著关系的链接预测。模型选择ReLu 函数作为神经元的激励函数，减轻卷积神经网络在训练过程中的过拟合现象。

该模型也适用于基于元路径APAPA 及其他元路径的合著关系预测问题，只需对图5（a）部分不同类型的节点个数和序列顺序做调整。此模型在两条元路径上的表示分别记为RAPAPA、RAPCPA。

3.2 基于节点类型的链接预测模型

图5 基于元路径序列的链接预测模型

学术网络的元路径包含多种类型节点，且同一条路径中每种类型的节点可能有多个。因此可采用同类型节点重构元路径方法，即按元路径顺序提取同类型节点，将其重构为多条同构路径，如图6。

图7表示为基于元路径APAPA 的情况，对于作者节点和作者节点分别取向量化表示MA、TMP。提取同类型节点并重构同构路径：仅含作者节点的路径记为LA、仅含论文节点的路径记为LP。用卷积神经网络分别提取每条同构路径相邻节点间的隐含结构信息，挖掘潜在语义属性，再将提取到的信息赋予节点本身。将同一条元路径衍生的多条同构路径信息融合，构建基于节点类型的元路径新表示：RA3P2+TMp。

链接预测部分和图5（b）部分一致，采用卷积神经网络挖掘异构学术网络的深层次信息，以提高链接预测的准确性。本模型同样也适用于基于元路径APCPA 及其他元路径的合著关系预测，只需对网络表示部分节点个数和节点类型做调整。基于节点类型的链接预测模型不仅考虑了元路径的序列信息，而且重构了元路径的表示，挖掘了相邻同构节点间的隐含信息。此模型在两条元路径上的表示分别记为RA3P2、RA2P2C。

4 实验

4.1 数据集

本文选取典型的学术网络：数据库与信息系统（DBIS）数据集[19]进行实验，包含60 694 名作者，72 902篇论文和4 580 个会议；还包括192 421 个论文作者关系，72 902个论文会议关系，属于密集网络。

图6 基于节点类型的网络序列化表示

图7 基于节点类型的链接预测模型

4.2 评价指标

本文基于真正例（TP）、真负例（TN）、假正例（FP）、假负例（FN）等，获得链接预测的准确率和召回率，并用AUC值和MAE值综合评价模型优劣。

（2）召回率（Recall），表示实际正样本中预测为正样本的比例：

（3）AUC 值（Area Under the Curve），ROC 曲线下方的面积，可以直观评价分类器的好坏：

其中，n 为随机实验的次数，n′为正样本比负样本得分高的次数，n″为正样本和负样本得分一样高的次数。若AUC值小于0.5，则表明算法比随机选择的准确率还低。

（4）MAE 值（Mean Absolute Error），表示观测值与真实值绝对误差的平均值，能更好地反映预测值误差的实际情况：

4.3 实验及结果分析

针对论文节点三种向量化方法：MP、TFP、TMP，路径长度为4 的两条元路径：APAPA、APCPA，链接预测的两种网络构建模型：RAPAPA或RAPCPA方法，或方法分别进行实验。研究向量化表示、元路径选取、预测模型构建对预测结果的影响。

4.3.1 节点向量化表示对预测结果的影响

采用RAPAPA方法对论文节点的不同向量化表示方法进行实验，实验结果见表1。

表1 论文节点的不同向量化表示在RAPAPA 下的预测结果

实验3 的AUC、Acc 和Recall 值均高于实验2 和实验1的各项指标。说明对比其元路径信息MP，语义属性TFP有更重要的作用，结合了元路径信息和节点属性的复合节点表示TMP更有助于社会网络的挖掘，这是同构社会网络不具备的特点。实验3的MAE值低于实验2 和实验1，说明了采用复合向量化表示的模型稳定性更好。

3.将传统投入产出表中所涉及的42个细化部门合并为六大部门：农业、工业、建筑业、商业餐饮业、货运邮电业、非物质生产部门；

4.3.2 重构元路径对预测结果的影响

表2 论文节点的不同向量化表示在下的预测结果

表2 论文节点的不同向量化表示在下的预测结果

实验序号456实验方法RA3P2+Mp RA3P2+TFp RA3P2+TMp AUC 0.987 0.989 0.995 Acc 0.952 0.958 0.974 Recall 0.948 0.949 0.966 MAE 0.048 0.042 0.026

对比实验1、4，实验2、5，实验3、6，可以得到在论文节点向量化表示方法一致的情况下，方法均比RAPAPA方法有更好的实验结果。说明基于元路径序列顺序提取同类型节点重构路径的方法，可以更好地提取元路径上的隐藏信息，是因为挖掘相邻的同类型节点具有一定的物理意义。方法可以认为得到了待预测节点间具有不同语义的两条路径，且用CNN 也能更好地提取路径上的相关性。故元路径上同类型节点的隐含邻居信息可以帮助网络重构，有效地提高异构社会网络中链接预测的精度。

4.3.3 不同元路径对预测结果的影响

两个节点之间不同的元路径具有不同的结构和语义信息，APAPA 元路径侧重强调存在间接合著关系的两作者之间的合著关系，而APCPA 元路径则强调在同一会议上发表过论文的两作者之间的合著关系。针对元路径APCPA，实验见表3、表4。

表3 论文节点的不同向量化表示在RAPCPA 下的预测结果

表4 论文节点的不同向量化表示在 下的预测结果

表4 论文节点的不同向量化表示在 下的预测结果

实验序号10 11 12实验方法RA2P2C+Mp RA2P2C+TMp RA2P2C+TFp AUC 0.991 0.993 0.996 Acc 0.970 0.971 0.975 Recall 0.966 0.967 0.976 MAE 0.030 0.029 0.025

实验7～12依次和实验1～6对比，均有略优的预测结果，说明了不同元路径下的预测结果会略有不同。其间包含的节点类型越多，可以更多维地描述待预测节点，提高最终的预测结果。

4.3.4 与其他算法对比

文献[6]Metapath2vec 算法为仅考虑异构网络中元路径的情况，即本文的实验1；文献[7]Rhine 算法是在Metapath2vec算法的基础上引入两种不同的关系：ARS和IRS，ARS 表示元路径的端点类型不同，意味着两端节点的从属关系。IRS表示元路径的端点类型相同，描述对等结构，即两端节点的交互关系，基于元路径APAPA 的实验结果见表5。

表5 与其他算法的预测结果比较

本文方法在四个指标上均获得了更好的效果，与实验1 相比，本文方法增加语义属性，说明语义属性可以辅助节点的向量化表示；实验13 考虑的从属关系及交互关系只分析元路径端点类型，本文方法综合考虑整条元路径的节点类型，提取同类型节点的隐含信息、拼接不同类型的节点表示；将捕捉网络的局部信息丰富至全局网络拓扑，显然会有更好的预测效果。实验14 为仅选用一层卷积的情况，其Acc值和MAE值略高于实验6，而Recall 值值略低于实验6，故本文暂不讨论卷积层数对实验结果的影响。

5 结语

本文在DBIS数据集上对异构学术网络中的合著关系进行研究，预测现有研究者未来产生合著关系的可能。在异构网络节点的向量化表示中，不仅考虑元路径信息还充分挖掘部分节点的语义属性，实验表明增加语义属性的复合向量化表示可以更好地描述异构节点；在其路径结构表示上，提取元路径包含的同类型节点，挖掘相邻同类型节点间的隐含信息，可以更好地表征网络结构，提高最终的预测结果。

在未来工作中，试图将本文提出的模型应用到更多类型的异构社会网络中，探索本模型的普适性。此外，还将研究更多高效的链接预测模型。