超图环境下链路预测问题的探究

佘美富， 王逸伟， 张建章， 詹秀秀， 刘闯

1. 杭州师范大学 阿里巴巴复杂科学研究中心，杭州 311121；2. 合肥综合性国家科学中心数据空间研究院，合肥 230088

“关系”普遍存在于现实生活中的各实体之间, 如人们之间的合作或社交、 有机物之间的生化反应等． 数学上, 人们习惯将上述各实体看作节点, 实体间的关系看作节点对的连边, 从而将其表达成统一而简洁的符号形式——图(亦称网络), 并辅之以严密的数学工具来分析和解决现有问题． 然而, 相较于成对实体, 现实中更多存在的是成群实体间的关系, 如合作或社交小组、 多个有机物共同参与的生化反应等． 边所连接节点的数量限制成为图表达能力的桎梏, 使其只能展现成对实体之间的关系． 作为图的自然扩展, 超图将边所连接的节点数量放松至任意, 从而形成了不同于普通边的“超边”． 这种结构上的突破使得超图能呈现任意数量的实体间关系, 进而获得大大强于普通图的表达能力． 超图在表达能力上的优势吸引人们的关注并日益成为研究热点．

在构建图的过程中, 由于观测手段、 数据丢失等问题, 不能保证实体间所有存在的关系都已被描述． 随着图的演化, 节点之间会产生新的关系, 预测缺失或未来即将出现的超边被称之为超图的链路预测, 为了与普通图的链路预测问题进行区分, 将其简称为“超链路预测”． 由于关系的重要性, 超链路预测日益成为人们的研究重点． 然而, 超边大小的任意性导致人们在进行超链路预测时遇到了一些阻碍, 首当其冲的便是候选超边数量的暴增． 具体来说, 超边连接节点数量的放松导致候选超边数量的规模从O(n2)暴增至O(2n), 链路预测方法的输入节点数从固定值2变为任意值． 关于候选超边数量暴增的问题, 对原始的候选超边集进行下采样是一个通用方法． Zhang等[1]对原始的候选超边集按领域知识对各数据集进行采样, 并定义了基于采样后的候选超边集的超链路预测问题． Patil等[2]在完全随机采样和依超边大小分布采样的基础上, 提出了基于motif和clique的抽样方法, 并对这些方法所抽取的样本进行了可预测性研究． 另一种手段是根据启发式方法直接得到待预测超边的大小． Kumar等[3]认为超边的产生应该遵循原始超图的结构规则, 将原始超图的超边大小分布的采样值作为待预测超边的大小． Srinivasan等[4]直接将大小的预测值嵌入生成对抗图中, 利用对抗学习的机制来拟合最佳预测参数． 除候选超边数量暴增的问题外, 超链路预测方法的输入节点数不固定也是一个棘手的问题, 解决该问题的方式依赖于超链路预测方法本身的设计模式, 偏重于机器学习、 矩阵分解模型的方法通常会将待评分的候选超边编码成固定长度的特征向量, 将其作为标准分类器的输入． 例如, Srinivasan等[4]提出了一种新的特征聚合方法, 该方法将节点与超边置于同等地位以进行对称式的卷积运算, 证明了使用所提出方法进行特征学习, 同一等价类的节点或超边之间有相同的特征表示, 所学习到的特征在下游的链路预测任务上有着十分优异的表现． Yuan等[5]提出一种基于张量的联合图嵌入方法, 将成对链接和超链接同时编码到潜在空间上, 该方法捕获并编码了高阶连接的依赖关系, 并据此推断未观察到的超边． 而偏重于复杂图的方法则更加启发式地解决该问题, Benson等[6]认为超边的相似性是所包含节点之间相似性的整体表现, 提出了基于节点对计算候选超边相似性的一般方法． Kumar等[3]则提出了一个迭代式算法, 在每次迭代中进行寻找最优匹配节点并将所预测的超边大小作为迭代次数, 最终输出符合预期的预测超边．

作为链路预测的延伸, 人们会很自然地关注经典链路预测方法应用到超图上的可行性． 传统链路预测的理论已日趋成熟, 诸如Lorrain[7]、 Ou[8]、 Katz[9]、 Liu[10]等的方法足以覆盖大部分场景． 在长时间的探索后, 人们普遍认为一个优秀的链路预测方法应具有这样的特征: 在可解释性强、 计算复杂度相对较低的情况下依然拥有较好的预测效果[11]． 依托成熟的链路预测理论, 将链路预测方法应用到超图环境下是一个很自然的想法． 然而, 图与超图之间巨大的拓扑结构差异使得将此方法移植至超图上时举步维艰． 近年来有极少数的研究基于经典链路预测方法的思想去开发对应的超链路预测版本． Pan等[12]延伸了普通图的环思想, 在超图上定义了节点环路与超边环路, 对不同长度的环路进行加权求和作为逻辑回归的输入, 从而对各候选超边进行概率预测． Srinivasan等[4]受传统链路预测领域内RA算法的影响, 提出了HRA算法以用于超链路预测．

基于上述研究, 在探索的起点上, 本文讨论了一个经典链路预测方法——带重启的随机游走(random walk with restart, 简称RWR)指标, 如何扩展并应用于输入节点数可变的超链路预测场景中, 以该方式为蓝本, 扩展了其他传统链路预测指标, 并以此作为基础方法． 引入了9个不同领域、 不同规模的真实超图, 并对这些超图的节点组进行抽样以生成部分基础方法的分数抽样分布, 通过生成的抽样分布验证了所引入方法在解决超链路预测问题上的有效性, 发现并解释了不同方法的分数分布在不同大小节点组上的差异． 然后, 使用上述方法在所有真实超图上进行了标准的超链路预测实验, 按照Zhang等[1]所提及的方式进行下采样以减少候选超边数量． 结果表明, 带重启的随机游走指标在精确率和召回率上要明显优于其他指标, 虽然没有一个方法在接收者操作特征曲线下面积(AUC)性能上对所有数据集表现一致优越, 但各方法分组AUC的性能变化曲线却与对应的分数分布变化类似, 且均呈现出随节点组大小递增的惊人一致性． 上述所有结果都暗示着大超边内部节点的连接强度要远远大于小超边．

1 问题定义

1.1 超图

给定超图H=〈V,E〉, 其中V={v1, …,vn}, 是n个节点组成的节点集,E={e1, …,em}, 是由m个超边组成的超边集． 每一条超边ej由若干个节点组成, 表示节点之间的相互作用, 用|ej|表示超边ej的大小, 即其所包含的节点数．V的所有节点组合构成了该节点集的幂集2V, 取节点组e∈2V, 则e的大小可取值1, 2, 3, …,n． 因此有超图的超边集E⊂2V． 数学上, 使用关联矩阵B=(bij)n×m表示超图, 其行表示节点, 列表示超边, 当且仅当节点vi属于(亦称关联)超边ej时, 对应元素bij=1, 否则bij=0．

1.2 超链路预测

对于上述超图, 想象因“某种原因”使得部分超边丢失, 导致其仅有部分超边能够被观察到． 则E被分为已观察超边集Eo(亦称正边集)和遗失超边集Euo, 且有Euo=EEo, 这些遗失超边与不能够形成超边的节点组(亦称负边集)混杂在一起组成了候选集D, 记负边集合为En, 且有D=Euo∪En,Φ=Euo∩En． 基于此定义超图上的链路预测任务: 利用正边集Eo, 从候选集D中尽可能多地寻找到属于Euo的边． 该任务等价于一个二分类问题, 在实施过程中, 首先利用链路预测方法对D中所有样本进行评分, 根据评分结果设立一个阈值, 将评分高于阈值的样本判定为正样本, 否则为负样本．

1.3 下采样

这里, 候选样本集Es的选取也值得讨论． 在超图链路预测的环境下, 超边大小的任意性导致了候选集(所有未形成边的节点组)2VEo的大小呈O(2|V|)上升, 即所谓的“极端类不平稳问题”(extreme class imbalance, 简称ECI)[2]． 从大量的候选边中寻找各个遗失超边无异于大海捞针． 为此, 需要对候选集进行下采样以减小推断空间的大小． 而下采样所采样出的候选样本需要符合“实际情况”, 这里将“实际情况”理解为候选样本的大小分布应该与已观察超边集合的大小分布一致[2]． 为此, 根据已观察超边集Eo的超边大小分布, 对候选样本空间2VEo进行下采样以生成候选样本集Es, 从而保证候选样本集Es的大小分布与Eo一致．

2 方法

超链路预测问题考虑的是超图中一组节点是否能形成超边, 因此首先研究节点对之间的相似性． 本文提出用超图上带重启的随机游走来定义节点对之间的相似性, 还拓展了基于普通图的一些节点对相似性方法来定义超图中节点对的相似性． 基于节点对的相似性再刻画节点组的相似性, 以此作为超链路的预测方法．

2.1 节点对的相似性

2.1.1 带重启的随机游走指标

带重启的随机游走是链路预测里的一个经典方法, 该方法基于图上的带重启随机游走, 并将节点对之间的平稳互达概率作为链路预测分数[11]． 为将上述指标扩展到超图, 需要先定义超图上的随机游走． 假设游走者在时刻t(t=0, 1, …)位于节点vi, 考虑一种无偏的情况, 游走者首先随机游走到包含该节点的任意一条超边上, 并在t+1时刻随机游走到关联该超边的节点vj． 这里定义的超图随机游走可简单表述为上述过程的迭代． 该游走者在t到t+1期间, 从节点vi转移到节点vj的概率为:

(1)

式(1)计算了从vi到vj的单步转移概率, 其前一项和后一项分别描述了“游走到超边”和“游走到节点”的过程． 由于超图中有n个节点, 相应地有n2个单步转移概率, 将这些概率值组织成概率转移矩阵P=(pij)n×n． 依式(1)可将该矩阵进行分解:

(2)

DvE∈Rn×n,DeV∈Rm×m, 均为对角阵, 对角线元素分别为各节点所关联的超边数和各超边所包含的节点数．

(3)

需要注意的是, 并未限制在每一步随机游走的过程中游走者不能跳回上一步节点, 这是为了使状态转移矩阵P能分解为式(2)所示的矩阵运算． 在此基础上添加重启机制, 即在每步游走时, 有一定可能跳回到初始节点vi, 跳回概率为c(0

(4)

(5)

因此, 可以定义节点对vi,vj的平稳解RWR分数:

(6)

式(6)将随机游走者从初始节点vi出发并到达vj的平稳概率作为节点对的相似性分数, 其大小表征了从vi到vj的可达性, 内在编码了超图的拓扑结构． 很明显, 该分数并不具有对称性, 即RWR(vi,vj)≠RWR(vj,vi)．

2.1.2 基础方法扩展

受普通图链路预测方法和已有超图研究的启发, 本文设计了一些超图上刻画节点对相似性的方法, 以下列举这些基础方法基于节点对输入的定义．

1) 共同邻居指标(Common Neighbors, 简称CN)． 共同邻居指标是传统链路预测中最简单也是最经典的指标． 该指标基于“共同邻居越多的节点对越相似”这一思想, 计算公式为[13]:

CN(vi,vj)=|Nvi∩Nvj|

(7)

式中Nvi是节点vi的邻居集合, 在超图中, 它是指与节点vi共存于同一超边内的其他所有节点．

2) 共存超边指标(Coexist Edge, 简称CE)． 不同于普通图, 在超图环境中, 由于边大小的任意性, 两个节点往往会被多个超边同时包含． 统计包含节点对的超边个数便得到共存超边指标, 其计算公式为:

CE(vi,vj)=|Evi∩Evj|

(8)

式中Evi是包含节点vi的超边集合．

3) Jaccard指标(简称JC)． Jaccard指标[14]最初用来计算两集合之间的相似性． 在超图中, 用该指标计算节点对之间的相似性定义如下:

(9)

4) Adamic-Adar指标(简称AA)． Adamic-Adar指标[15]在CN的基础上考虑了共同邻居的权重, 权重是共同邻居的邻居数对数的倒数． 在超图中, 对于节点, 可以将共存于同一超边的其他节点看作“点邻居”, 将节点所关联的超边看作“边邻居”． 对于超边, 可以将所包含的节点看作点邻居, 将具有共同关联节点(即相交)的超边看作边邻居． 由于邻居可分为点邻居和边邻居, 点邻居、 边邻居的不同组合对应4种不同的AA指标, 分别为VVAA、VEAA、EVAA、EEAA． 计算公式如下:

(10)

指标名称的第一个和第二个字母分别代表共同邻居和共同邻居的邻居的性质． 例如,VEAA表示节点对的共同邻居为“点邻居”, 而共同邻居的邻居为“边邻居”, 也即计算与节点对均为邻居的节点权重, 权重由该邻居所关联的超边数量计算所得．kvV(z)、kvE(z)统计了节点z的邻居节点个数和关联超边个数, 而keV(z)、keE(z)则统计了超边z所包含的节点个数及超边z所相交的超边个数, 一般将kvE和keV看作节点和超边的度[16]．

5)α阶局部游走指标．α阶局部游走指标定义在游走的基础之上, 将节点对之间α阶游走的数量作为分数． 在普通图中, 形如vi0,vi1, …,viα-1这样, 节点个数为α且相邻节点在图中互为邻居的节点序列被称之为一次α阶游走． 扩展到超图上[17], 超图上的一次α阶游走可定义为一个节点、 超边交替出现的序列:

vi0,ei0,vi1,ei1, …,eiα-1,viα

(11)

其长度等于α, 即超边出现的次数． 同样, 序列中的相邻元素在对应超图中相互关联． 节点对之间的α阶游走数量, 即α阶局部游走指标可表示为:

(12)

2.2 节点组的相似性

(13)

(14)

在社交领域, 式(14)所蕴含的思想直观且有效: 若一组成员之间两两关系亲密, 那么他们更有可能组成一个团体．

3 实验

3.1 数据集

本文引入了9个真实超图, 其领域覆盖了食谱、 生物、 合作、 社交等方面． 各数据集的详细统计信息见表1． 表1 由真实数据构建的超图拓扑结构性质, 其中n,m, 〈kvE〉, 〈kvV〉, 〈|e|〉,d(H), |E2|, |E3|, |E4|, |E5|, 分别表示超图的节点数, 超边数, 节点超度的平均值, 节点一阶邻居数的平均值, 超边大小的平均值, 密度[18], 超边大小分别为2,3,4,5的超边数量．

表1 各数据集的详细统计信息和超图拓扑结构性质

1)chuancai[1]: 菜谱数据集, 节点由食材构成, 一道川菜所需的一组食材构成一条超边．

2)iAB_RBC_283,iJO1366[1]: 人类、 大肠杆菌代谢反应数据集． 超边表示生物体内的代谢反应, 边内的节点表示参与该反应的反应物．

3)CoreComplex: 本文构建了人类蛋白质相互作用数据集． 超边代表人体内的蛋白质相互作用, 其包含的节点表示参与相互作用的蛋白质．

4)Cora-Co-citation,Cora-Co-reference[19]: 这两个是引文数据集, 两者的节点均表示机器学习论文． 在Cora-Co-citation超图中, 超边连接了被同一篇论文所引用的所有论文． 而在Cora-Co-reference中, 引用了同一篇论文的论文组成一条超边．

5)DBLP-Co-authorship[20]: 这是一个计算机领域的论文合作数据集． 节点表示论文作者, 超边连接了同一篇文章的所有作者．

6)cat-edge-music-blues-reviews[21]: 这是一个共评论数据集． 节点是亚马逊购物网上的用户, 在一个月内评论过相同布鲁斯音乐产品的用户组成一条超边．

7)email-Eu[6, 22-23]: 线上社交数据集． 节点表示欧洲科研机构的电子邮箱, 超边是一次邮件发送, 由邮件发送者和所有接收者所组成． 原始数据集中,email-Eu图的超边带有时间戳, 这里将多个带时间戳的超边合并成一个超边以静态化原始数据集．

3.2 方法有效性验证与超图结构探索

算法1: 指标分数抽样算法输入: 超图: H=, 指标: f, 节点组大小: b输出: 任意节点组分数样本集: Sarb, 超边节点组分数样本集: Sedge1. Sarb, Sedge←[], [];2. //获得指定大小的超边子集3. Eb←E.get_subset(b);4. for e in Eb do5. //从节点集中不放回抽取 |e| 个节点6. e =V.random_choice(|e|);7. Sarb.append(fH(e ));8. H' ← ;9. Sedge.append(fH'(e));10. end do Result: Sarb, Sedge

如何验证第2章所列举的链路预测方法在超图环境下的有效性, 即指标f是否有能力将有潜力形成超边的节点组和普通节点组区分开来． 一个自然的想法是: 随机选取一条超边, 同时从超图节点集中随机选取一个相同大小且无重复元素的节点组, 前者的f指标分数大于后者的概率越大, 指标f就有效．

3.2.1 分数分布分析

红色为超边节点组, 蓝色为任意节点组．

图2 各数据集CE分数分布的误差棒图

各数据集任意节点组的分数分布都极其类似, 其分数严重集中在低分值, 且均值方差几乎没有变化, 本文将其作为对照组来观察同尺寸的超边节点组分数分布． 在生物代谢图上, 超边节点组所有分数抽样分布的变化都十分统一: 开始时节点组的分数基本集中于低分值上, 随着节点数的增加, 其样本分数的取值范围逐渐增大且更加均匀地分布于各个区间． 观察iAB_RBC_283的CE分数分布(图1a), 该数据集的节点组CE分数表示节点组内各反应物平均共同参与的反应数． 可以看到, 2,3-超边节点组的分数并未显著大于同尺寸任意节点组(p>0.05), 而4-超边节点组相当一部分超边节点组的分数落在了10左右, 当节点组大小为5时, 超边节点组的分数更均匀地落在了大分数上, 这表明多反应物的代谢反应显著依赖于反应物两两之间的可反应程度, 且依赖程度随代谢反应规模的增加而增加． 蛋白质代谢图CoreComplex的各分数分布也有类似变化, 但并未表现得像前两者显著．

cat-edge-music-blues-reviews和DBLP-Co-authorship图的超边分别以“兴趣”和“合作”关系将代表各用户的相关节点相连． 这两个图的构成具有一定的相似性, 即由代表人的节点因为共同事件所联系到一起,CE、CN分别表征了人们之间共同参与事件及共同参与者的数量． 而两者超边节点组分数分布也比较类似． 以cat-edge-music-blues-reviews图为例, 超边节点组在CN与CE上的分数分布表明: 节点组增大时, 虽然人们之间共同购买的产品并未显著变化, 但用CN所统计的用户的共同兴趣者却大大增加． 对于邮件收发图email-Eu, 除2-超边节点组外,email-Eu图各方法分数分布在其余大小的节点组上几乎没有差别, 即均表现为均值类似的正态分布(图1b)． 且各方法分数分布的均值总体先上升后保持平稳(略有上升或下降), 造成这种现象的一个解释是“朋友在工作中产生”, 工作环境下的多次群发促成了日后代表亲密关系的“一对一沟通”．

3.2.2 结构分析

总体上看, 由于超边形成机理相同, 同一领域数据集的超边节点组分数分布相似． 而不同数据集超边节点组的各方法分数抽样分布与均值方差变化呈现两种趋势, 要么没有明显变化, 要么初始时显著上升． 这说明两点: 第一, 各方法以多视角衡量了节点组之间节点对的亲密程度． 第二, 超图的“派系闭合假说”认为, 大关系在形成前, 其内部节点之间的联系已经非常紧密． 基于此, 演化良好的超图, 大尺度超边节点组内部节点对的亲密程度必然大于2-超边节点组． 如若不然, 超边节点组内的各个亲密节点对更倾向于生成各种细密的2-超边而没有继续扩张的趋势． 甚至于在大部分数据集中, 2-超边节点组和2-任意节点组之间分数分布几乎没有差异． 一般认为, 方法对超边节点组和任意节点组的评分差异越大, 该方法预测能力越强． 上述情况会使得各方法很难将大小为2的超边节点组和其他节点组区分开来从而导致误判． 例如, 两个引文图Cora-Co-citation和Cora-Co-reference的所有方法的超边节点组分数抽样分布几乎不受节点组大小的影响, 由于没有明显的演化规律和超边节点组与任意节点组之间的分数差异不明显, 所提出的方法对这两个图的链路预测效果将不会太理想． 总的来说, 通过抽样及之后的分析, 在验证了已抽样方法的有效性——即它们的确能区分正负样本的同时, 还发现在大多数情况下, 这种区分能力和节点组的大小有关, 即对大尺寸节点组的区分能力要远远强于小尺寸节点组． 由于真实超图的超边大小分布往往展现为幂律, 即小尺寸超边占绝大多数, 因此, 对小尺寸、 甚至于2-节点组的无力是制约超链路预测方法性能的主要桎梏．

3.3 超链路预测

本文使用经典的二分类全局指标——接收者操作特征曲线下面积(AUC), 与局部指标——精确率(precision@k)和召回率(recall@k), 来评估第2节所列举方法在各真实图上的表现． 对单个数据集及特定指标的每次实验, 采用五折交叉验证的方式进行并重复若干次, 记录每次实验的交叉验证平均值． 参数设置上,RWR的游走重启概率c固定为0.15．

3.3.1 预测结果分析

预测结果的AUC评价展示在表2, 可以看到, 并未有任何一种方法在所有数据集上表现得最好, 这便是超链路预测环境下的“天下没有午餐定律”[24]． 令人惊喜的莫过于CE, 该方法定义十分简单, 却在iAB_RBC_283、iJO1366、CoreComplex、Cora-Co-reference、DBLP-Co-authorship上表现优异． 将CE应用于这些数据集还能得到更加直观的物理解释, 例如, 对于合作图DBLP-Co-authorship, 以CE方法的视角来看, 当一群作者相互之间合作过很多次时, 他们更有可能组团进行合作． 在数据集chuancai和email-Eu上,CN方法有着不错的性能表现． 以email-Eu为例,CE方法计算了节点组内节点对之间的平均邮件收发事件数, 而CN方法计算了各自参与的邮件收发事件的其他共同参与者数量, 这表明, 有着更多工作伙伴关系的成员组之间更有可能产生邮件收发事件． 在普通图的链路预测中, 奇数步局部游走指标在代谢图上效果良好[25], 如果将CE看作“WK1”, 其效果在生物数据集上表现最优也就不足为奇了．JC作为CE的加权, 整体上前者的表现不如后者, 这也说明了链路预测方法的准确度并非与其计算复杂度呈正比． 对于在超图环境中所扩展的4类AA方法, 若分别将VVAA、VEAA看作CN的改进,EVAA、EEAA看作CE的改进, 则这两组方法内部之间的性能表现都十分接近． 且将点邻居个数看作共同邻居或共存超边的权重时(VVAA之于CN、 EVAA之于CE), 整体有着更为明显的性能提升, 这可能是由于点邻居的数量相对于边邻居更多, 致使其权重的粒度更加细致从而有着很好的区分度．RWR在各数据集上的AUC表现似乎与邻域方法、 特别是CE的表现正相反, 如前者在chuancai、cat-edge-music-blues-reviews、email-Eu上具有较优秀的预测效果, 而后者在除这些以外的其他数据集上有着较好的表现, 这表明在超链路预测任务中, 节点间的全局特征与局部特征都能提供有效信息． 同时本文对某一方法作用于所有数据集上的链路预测性能(AUC分数)与所有数据集的某一特定统计特征进行了相关性计算, 热力图见图3． 总体上看, 超图的“规模”越大, 其可预测性越好, 注意到〈kvE〉, 即所谓超图的平均超度[26]与方法的预测性能之间呈显著正相关, 这意味着该指标的大小直接展示了数据集可利用信息的多少．

横坐标为方法, 纵坐标为统计特征, 该图表征了真实数据集的统计特征与方法预测性能的相关性．

表2 各方法在不同数据集上的AUC对比

预测结果的精确率及召回率曲线分别展示在图4、 图5, 两者的阈值上限取各数据集测试集样本数量的一半． 不同于在AUC表现上的“百家争鸣”, 精确率及召回率曲线上扩展的RWR方法在所有数据集上均取得了不错的效果, 说明所引入超图随机游走方式的有效性, 即该过程确实能够捕捉到超图的拓扑结构． 局部游走指标(WK2、 WK3)效果普遍较差, 两者的效果随着阈值k的增加而快速下降, 这可能是因为在扩展局部游走时并未考虑“游走宽度”[17], 从而丢失了超边的“高阶特性”． 总的来说, 各方法虽然在性能上有所差异, 但正如本章第2节所言, 所扩展的方法在应用于超链路环境中时, 都能够对正负样本有效地进行预测．

图4 精确率曲线

3.3.2 分组评估

延续抽样时的方式, 在链路预测完成后, 对各方法应用于各数据集的表现分节点组大小进行评估, 评估结果见图6． 与抽样类似的是, 各方法2-节点组上的链路预测效果明显低于其他节点组． 例如, 对于iAB_RBC_283, 2-超边节点组的CE、 CN分数分布并未显著大于任意节点组, 相对应, 很多方法对该数据集2-节点组进行链路预测的AUC效果甚至低于0.5． 对于大尺寸节点组, 各方法在整体上表现一致． 这一现象不仅与抽样结果相吻合, 还从链路预测角度体现了大超边内部节点的强链接程度． 与抽样不同的是, AUC的效果评估曲线在绝大部分数据集上呈现绝对递增的趋势, 即随着节点组节点数的增加, 各方法在数据集上的链路预测效果越来越好．

4 总结与展望

本文给出了将链路预测方法扩展到超图环境的一般方式, 并基于此方式扩展了11种方法． 对所扩展的方法在真实超图上进行分数抽样并生成了对应的分数抽样分布, 验证了扩展方法的有效性, 发现了不同数据集的超边演化规律, 认为演化良好的超图其超边内部的联系强度随节点数增加而增加, 由此推论超链接预测的主要难点在于对小尺寸超边的预测． 然后, 将所扩展方法直接应用于真实超图的超链路预测, 链路预测结果表明, 不同方法适用于不同的超图环境, 但在局部精确率和召回率上, RWR有着更好的性能． 还根据节点组大小对预测效果分别进行评估, 结果表明在同一数据集内, 扩展方法的性能随着节点组节点数的增加而增加．

在未来的研究中, 希望引入除式(13)外更多的扩展方式以达到性能的进一步提升． 对于具体的链路预测方法, 在普通链路预测指标的基础上, 希望加入更多超图独有的高阶性质, 如“宽度”[17]、 “高阶随机游走”[27]等, 另外, 更希望所设计的方法能有效地应对当前方法在预测小尺寸超边上的无力． 最后, 关于超边下采样算法的讨论正如火如荼[2, 28-29], 期待在未来, 使用最新的下采样算法所得到更加“仿真”的负样本能更好地评估方法的性能．