-
开放科学(资源服务)标志码(OSID):
-
“关系”普遍存在于现实生活中的各实体之间,如人们之间的合作或社交、有机物之间的生化反应等. 数学上,人们习惯将上述各实体看作节点,实体间的关系看作节点对的连边,从而将其表达成统一而简洁的符号形式——图(亦称网络),并辅之以严密的数学工具来分析和解决现有问题. 然而,相较于成对实体,现实中更多存在的是成群实体间的关系,如合作或社交小组、多个有机物共同参与的生化反应等. 边所连接节点的数量限制成为图表达能力的桎梏,使其只能展现成对实体之间的关系. 作为图的自然扩展,超图将边所连接的节点数量放松至任意,从而形成了不同于普通边的“超边”. 这种结构上的突破使得超图能呈现任意数量的实体间关系,进而获得大大强于普通图的表达能力. 超图在表达能力上的优势吸引人们的关注并日益成为研究热点.
在构建图的过程中,由于观测手段、数据丢失等问题,不能保证实体间所有存在的关系都已被描述. 随着图的演化,节点之间会产生新的关系,预测缺失或未来即将出现的超边被称之为超图的链路预测,为了与普通图的链路预测问题进行区分,将其简称为“超链路预测”. 由于关系的重要性,超链路预测日益成为人们的研究重点. 然而,超边大小的任意性导致人们在进行超链路预测时遇到了一些阻碍,首当其冲的便是候选超边数量的暴增. 具体来说,超边连接节点数量的放松导致候选超边数量的规模从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的性能变化曲线却与对应的分数分布变化类似,且均呈现出随节点组大小递增的惊人一致性. 上述所有结果都暗示着大超边内部节点的连接强度要远远大于小超边.
HTML
-
本文引入了9个真实超图,其领域覆盖了食谱、生物、合作、社交等方面. 各数据集的详细统计信息见表 1. 表 1由真实数据构建的超图拓扑结构性质,其中n,m,〈kvE〉,〈kvV〉,〈|e|〉,d(H),|E2|,|E3|,|E4|,|E5|,分别表示超图的节点数,超边数,节点超度的平均值,节点一阶邻居数的平均值,超边大小的平均值,密度[18],超边大小分别为2,3,4,5的超边数量.
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图的超边带有时间戳,这里将多个带时间戳的超边合并成一个超边以静态化原始数据集.
-
算法1:指标分数抽样算法 输入:超图:H=〈V,E〉,指标:f,节点组大小:b 输出:任意节点组分数样本集:Sarb,超边节点组分数样本集:Sedge 1. Sarb,Sedge←[],[]; 2. //获得指定大小的超边子集 3. Eb←E.get_subset(b); 4. for e in Eb do 5. //从节点集中不放回抽取|e|个节点 6. ẽ=V.random_choice(|e|); 7. Sarb.append(fH(ẽ)); 8. H′ ← 〈V,E\e〉; 9. Sedge.append(fH′(e)); 10. end do Result:Sarb,Sedge 如何验证第2章所列举的链路预测方法在超图环境下的有效性,即指标f是否有能力将有潜力形成超边的节点组和普通节点组区分开来. 一个自然的想法是:随机选取一条超边,同时从超图节点集中随机选取一个相同大小且无重复元素的节点组,前者的f指标分数大于后者的概率越大,指标f就有效.
基于上述想法,分别对所扩展的CN、CE和WK2方法进行抽样分析. 具体来说,对于任意一个真实图H=〈V,E〉,首先将2V\V内(不考虑大小为1的超边)所有节点组分为两大类:超边节点组和任意节点组. 顾名思义,一个超边节点组e∈E,其本身构成了一条超边. 而任意节点组ẽ∈2V\V取自超图所有可能的超边集合. 利用抽样算法分别得到超图的超边节点组和任意节点组的分数样本集合,并利用这些样本生成超边节点组和任意节点组在超图上的指标分数分布,最后比较两组分布和统计特征的差异性. 考虑到超图上的高阶特性,进一步细化抽样工作:抽样算法1以节点组大小为区分分开进行抽样,从而可生成不同大小节点组的分数分布. 注意到在对超边节点组进行抽样时,算法1首先将该节点组形成的超边所移除以模拟该超边形成前的环境.
-
由于空间有限,图 1仅展示部分数据集的部分方法分数分布,还展示了分布的样本均值X、样本标准差S以及两节点组分布t检验的p值. 由于各数据集中超边数量总体呈“小超边多、大超边少”的幂律分布趋势,在生成分数分布时,对小尺寸的节点组单独进行统计,而对大尺寸节点组进行联合统计. 同时绘制了各分数分布的误差棒图,图 2进行了部分展示. 实验结果表明CN及其衍生方法(VVAA、VEAA)、CE及其衍生方法(EVAA,EEAA,JC)、WK2和WK3的分布形状较为类似,其差别在于取值范围及精度,以下着重分析可解释性较强的CN、CE和WK方法的分数分布.
各数据集任意节点组的分数分布都极其类似,其分数严重集中在低分值,且均值方差几乎没有变化,本文将其作为对照组来观察同尺寸的超边节点组分数分布. 在生物代谢图上,超边节点组所有分数抽样分布的变化都十分统一:开始时节点组的分数基本集中于低分值上,随着节点数的增加,其样本分数的取值范围逐渐增大且更加均匀地分布于各个区间. 观察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). 且各方法分数分布的均值总体先上升后保持平稳(略有上升或下降),造成这种现象的一个解释是“朋友在工作中产生”,工作环境下的多次群发促成了日后代表亲密关系的“一对一沟通”.
-
总体上看,由于超边形成机理相同,同一领域数据集的超边节点组分数分布相似. 而不同数据集超边节点组的各方法分数抽样分布与均值方差变化呈现两种趋势,要么没有明显变化,要么初始时显著上升. 这说明两点:第一,各方法以多视角衡量了节点组之间节点对的亲密程度. 第二,超图的“派系闭合假说”认为,大关系在形成前,其内部节点之间的联系已经非常紧密. 基于此,演化良好的超图,大尺度超边节点组内部节点对的亲密程度必然大于2-超边节点组. 如若不然,超边节点组内的各个亲密节点对更倾向于生成各种细密的2-超边而没有继续扩张的趋势. 甚至于在大部分数据集中,2-超边节点组和2-任意节点组之间分数分布几乎没有差异. 一般认为,方法对超边节点组和任意节点组的评分差异越大,该方法预测能力越强. 上述情况会使得各方法很难将大小为2的超边节点组和其他节点组区分开来从而导致误判. 例如,两个引文图Cora-Co-citation和Cora-Co-reference的所有方法的超边节点组分数抽样分布几乎不受节点组大小的影响,由于没有明显的演化规律和超边节点组与任意节点组之间的分数差异不明显,所提出的方法对这两个图的链路预测效果将不会太理想. 总的来说,通过抽样及之后的分析,在验证了已抽样方法的有效性——即它们的确能区分正负样本的同时,还发现在大多数情况下,这种区分能力和节点组的大小有关,即对大尺寸节点组的区分能力要远远强于小尺寸节点组. 由于真实超图的超边大小分布往往展现为幂律,即小尺寸超边占绝大多数,因此,对小尺寸、甚至于2-节点组的无力是制约超链路预测方法性能的主要桎梏.
-
本文使用经典的二分类全局指标——接收者操作特征曲线下面积(AUC),与局部指标——精确率(precision@k)和召回率(recall@k),来评估第2节所列举方法在各真实图上的表现. 对单个数据集及特定指标的每次实验,采用五折交叉验证的方式进行并重复若干次,记录每次实验的交叉验证平均值. 参数设置上,RWR的游走重启概率c固定为0.15.
-
预测结果的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]与方法的预测性能之间呈显著正相关,这意味着该指标的大小直接展示了数据集可利用信息的多少.
预测结果的精确率及召回率曲线分别展示在图 4、图 5,两者的阈值上限取各数据集测试集样本数量的一半. 不同于在AUC表现上的“百家争鸣”,精确率及召回率曲线上扩展的RWR方法在所有数据集上均取得了不错的效果,说明所引入超图随机游走方式的有效性,即该过程确实能够捕捉到超图的拓扑结构. 局部游走指标(WK2、WK3)效果普遍较差,两者的效果随着阈值k的增加而快速下降,这可能是因为在扩展局部游走时并未考虑“游走宽度”[17],从而丢失了超边的“高阶特性”. 总的来说,各方法虽然在性能上有所差异,但正如本章第2节所言,所扩展的方法在应用于超链路环境中时,都能够对正负样本有效地进行预测.
-
延续抽样时的方式,在链路预测完成后,对各方法应用于各数据集的表现分节点组大小进行评估,评估结果见图 6. 与抽样类似的是,各方法2-节点组上的链路预测效果明显低于其他节点组. 例如,对于iAB_RBC_283,2-超边节点组的CE、CN分数分布并未显著大于任意节点组,相对应,很多方法对该数据集2-节点组进行链路预测的AUC效果甚至低于0.5. 对于大尺寸节点组,各方法在整体上表现一致. 这一现象不仅与抽样结果相吻合,还从链路预测角度体现了大超边内部节点的强链接程度. 与抽样不同的是,AUC的效果评估曲线在绝大部分数据集上呈现绝对递增的趋势,即随着节点组节点数的增加,各方法在数据集上的链路预测效果越来越好.