欢迎访问一起赢论文辅导网
博士论文
当前位置:首页 > 博士论文
知识图谱划分算法研究综述_王鑫
来源:一起赢论文网     日期:2021-04-25     浏览数:2693     【 字体:

 第44 卷 第1 期2021 年1 月计 算机 学 报CHINESEJOURNALOFCOMPUTERSVol .44No.1Jan. 2021知识图谱划分算法研究综述王 鑫 陈蔚雪 杨雅君 张小旺 冯志勇(天津大学智能与计算学部 天津 300354)(天津市认知计算与应用重点实验室 天津 300 35 4)摘 要 知识图谱是人工智能的重要基石, 因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述现实世界中的各种实体及其联系, 其中顶点表示实体, 边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的首要工作, 对知识图谱分布式存储、 查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增长, 如何对其进行划分已成为目前知识图谱研究的热点问题.从知识图谱和图划分的定义出发, 系统性地介绍当前知识图谱数据划分的各类算法, 包括基本、多级、流式、分布式和其他类型图划分算法. 首先, 介绍4 种基本图划分算法: 谱划分算法、 几何划分算法、分支定界算法、KL及其衍生算法, 这类算法通常用于小规模图数据或作为其他划分算法的一部分; 然后, 介绍多级图划分算法, 这类算法对图粗糙化后进行划分再投射回原始图, 根据粗糙化过程分为基于匹配的算法和基于聚合的算法; 其次, 描述3 种流式图划分算法, 这类算法将顶点或边加载为序列后进行划分, 包括Hash算法、贪心算法、 Fennel 算法, 以及这3 种算法的衍生算法; 再次,介绍以KaPPaJ八BEJA和轻量级重划分为代表的分布式图划分算法及它们的衍生算法; 同时, 在其他类型图划分算法中, 介绍近年来新兴的2 种图划分算法: 标签传播算法和基于查询负载的算法. 通过在合成与真实知识图谱数据集上的丰富实验, 比较了5 类知识图谱代表性划分算法在划分效果、查询处理与图数据挖掘方面的性能差异,分析实验结果并推广到推理层面, 获得了基于实验的知识图谱划分算法性能评价结论. 最后, 在对已有方法分析和比较的基础上, 总结目前知识图谱数据划分面临的主要挑战, 提出相应的研究问题, 并展望未来的研究方向.关键词 知识图谱; 图划分; 多级划分; 流划分; 分布式中图法分类号TP3 11DOI号1 0. 1 189 7/SP.J. 101 6. 2021 . 00235ResearchonKnowledgeGraphPartitioningAlgorithms:ASurveyWANGXi nCHENWei XueYANGYaJunZHANGXi ao WangFENGZhi Yong(. Col legeofIntell igenceandComput ing?Tianji nUni versity?Tianjin300354)( TianjinKeyLaborat oryofCogni tiveComput ingandAppl icaii onTianjin300354)AbstractKnowl edgegraphsareimportantcornerstonesofarti ficiali nt el ligence,whichnotonl yhavethegraphstructureofthegeneralgraphmodelbutal socontai nrichattri butei nformati onofverticesandedges.Therefore,knowledgegraphshaverecei vedwi despreadattenti oni npracticaltasks. Knowl edgegraphscanuseaccuratesemanticstodescri bethevari ousentitiesandtheirconnecti onsi nthereal worl d,wheretheverticesrepresententities,andtheedgesrepresentconnecti onsamongtheseenti ties.Knowl edgegraphparti tioningi safundamental taskfordi stri butedprocessi ngofl arge scal eknowl edgegraphs,andi ti stheessenti al supportforaseri esofgraphprocessingoperati onsi ncludingdi stributedstorage,queryprocessi ng,reasoning,anddatami ni ng.Withthei ncreasi ngscal eofknowl edgegraphsandmorerequirementsofdistri butedprocessing,itisdi fficul ttopartiti onl arge scal eknowl edgegraphs,whichhasbecomeahotissuei nthecurrent收稿日期:2019 09 05; 在线发布日期:2020 02 05.本课题得到国家重点研发计划项目(2019YFE0198600) 、 国家自然科学基金(61972275) 资助. 王 鑫, 博士, 教授, 中国计算机学会( CCF) 杰出会员, 主要研究领域为知识图谱数据管理、 图数据库、 大规模知识处理. Email:wangx@tju. edu.cn. 陈蔚雪, 硕士研究生, 主要研究方向为知识图谱数据管理、 图数据库、 大规模知识处理. 杨雅君, 博士, 副教授, 中国计算机学会( CCF) 会员, 主要研究方向为图数据库、 图数据挖掘. 张小旺, 博士, 副教授, 中国计算机学会( CCF) 会员, 主要研究方向为数据库、人工智能、 知识图谱. 冯志勇, 博士, 教授, 中国计算机学会( CCF) 杰出会员, 主要研究领域为知识工程、 服务计算.236 计 算机 学 报 2021年researchonknowl edgegraphs.Starti ngfromthedefi niti onsofknowl edgegraphsandgraphpartiti oni ng,wesystematical l yi ntroducevariousalgorithmscurrentl yavail abl eforknowl edgegraphpartiti oning,i ncl udi ngbasicgraphpartitioni ngalgorithms,mul til evelgraphpartiti oni ngal gorithms,streaminggraphpartiti oni ngal gorithms,distri butedgraphpartiti oni ngal gorithms,andothertypesofgraphparti ti oningalgorithms.First,fourbasicgraphparti ti oningalgori thmsarerevi ewed,i ncl udi ngspectralpartiti oni ngalgori thms,geometri cparti ti oni ngalgori thms,branchandboundalgori thms,KLandi tsderi vativealgori thms. Thi stypeofalgori thmsusual l yworksonsmal l scal egraphsorassubrouti nesformoresophi sti catedalgori thms.Second, twomul til evelgraphpartiti oningalgorithmsarei ntroduced,oneofwhichusesthematchi ngbasedalgorithmduri ngthecoarseni ngphase, andtheotherusestheaggregati on basedalgori thm.Aftercoarseni ng,theyparti ti onthemuchsmal lergraphandthenprojecttheresul tbacktotheorigi nalgraph.Thi rd,streami nggraphpartiti oni ngalgori thmsaredescri bed,whi chl oadagraphasasequenceofverti cesoredgesandassigneachel ementtothecorrespondi ngparti ti ons. Thestreami nggraphparti tioni ngalgori thmscanbefurtherdi vi dedi ntothreesubcategori es:thehashalgorithm, thegreedyalgorithm, theFennel algorithm, andtheirderi vativealgorithms.Fourth,wei ntroducedistri butedgraphpartiti oni ngalgorithmsforpartiti oni ngl arge scal egraphsi ndistributedenvironments.Wechoosethreerepresentati vealgorithms,namel ytheKaPPaalgorithm,theJABEJAalgori thm,thelightweightreparti ti oningalgorithm,andthendescri bederi vati vealgorithmsofthesedi stri but edalgori thms. Meanwhi l e,astheothertypesofgraphparti ti oni ngalgorithms,wepresenttworecentgraphparti ti oni ngalgori thms,onei sthel abelpropagati onalgorithm,andtheotheri sthequeryworkl oad basedalgori thm. Byconductingextensi veexperimentsonbothsyntheticandrealknowl edgegraphdatasets,wecomparetheperformanceoffi verepresentati veknowl edgegraphparti tioni ngalgori thmsi nparti ti oni ngeffects,queryprocessi ng,andgraphdatami ni ng.Weanal yzetheexperi mentalresultsi ndetail anddrawgeneral concl usi ons,andextendthemtothereasoni ngtasks. Theperformanceeval uationconcl usi onsofknowl edgegraphparti ti oni ngalgori thmsareobtai nedbasedontheseexperimentsandanal yses. Fi nal l y,basedontheanal ysi sandcompari sonofexi sti ngmethods,wesummarizethemai nchal l engesi nthecurrentresearchonknowl edgegraphpartiti oni ng,proposethecorrespondi ngissuesthatcanbei nvestigat ed,andl ookforwardtothefutureresearchdirecti onsonthistopic.Keywordsknowledgegraph;graphpartiti oni ng;mul ti levelpartitioning;streami ngparti ti oni ng;di stributi oni 引 言近年来, 知识图谱得到了越来越多的关注和发展.知识图谱[1]最早由Googl e 在2012 年提出, 现如今规模已经达到百万顶点( 1〇6) 和上亿条边( 1〇8), 常用的知识图谱有DBpedia?、YAGO[ 3]、Wi ki data[ 4]、Freebase[5]以及中文百科知识图谱CNDBpedia[6]、Zhi shu me[ 7 ]等. 知识图谱数据模型基于图结构, 用顶点表示实体, 用边表示实体间的联系.由于同时包含了图的结构信息和属性信息, 知识图谱能够更好地表示现实生活中的复杂关系.知识图谱不仅需要根据实际情况随时更新数据, 还要进行存储、 查询、 推理、 挖掘等一系列操作.如今知识图谱的数据规模正在不断增大, 链接开放数据( Li nkedOpenData)2019年3月发布的LOD云图中有很多知识图谱数据集规模超过10 亿条三元组[ 8 ]. 以维基百科知识图谱DBpedm为例, 它所包含的三元组数据已经超过了30 亿条. 由于知识图谱数据的急剧增长, 传统的集中式数据处理已经不能满足当前需求, 必须通过分布式集群来存储和处理大规模知识图谱数据. 知识图谱数据的分布式存储面临的第一个问题即是知识图谱划分. 这就使得如何划分大规模知识图谱, 同时满足跨分区边数目最小化且有效提高知识图谱查询处理性能成为迫切需要深人研究的课题.I 期 王義等; 知班真鬚刻分_*_寒難 23 7知识图瞥划分作为大规模知识圈谱分布式处理的首要工柞, 随着知识画谱数据规模及分布式处理需求的増长面險着新的挑战.一方面, 现有的知识图谱划分方法在大图上的划分效果并不理想, 时间复杂度较高, 特别是对于。包含数据量大且关系复杂的知识图m产业界对于知识旣谱划分通常使用分布式处理框架, 需s在集群上我到量佳的数据分布,》 然而高质量的划分必须同时满足负载平衡( 在机器之间均匀地分配数据)和最小化切割边或顶点的数量(其顶点或边癘于不同的分区), 这增加了机器之间的通信成本. 另一方面,_前主要利用现有的图 分算法对知识?谱进#划分, 然而这些算法忽略了'知识_谱的属性信息, 如何充分利用知识图谱数摒进行划分、如何制定统一的划分标准以及如何將划分与后续的查询处理相结合是当前研究的难点问題.知识图谱划分有着十分靈要的现实意义, 例如复杂网络《、 围像分割_、 趙大规模集成电路设计 等. 在复杂网络方面*最典型的就是社交网络分析m*每一个用户都是一个顶点* 可以稂据用户个人倩息以及用户之间的联系对其进行分类? 更好地对易有相_属性的甩户进行分析. 这同祥适用于道路交通网络?和生物网络D4],道路交通网络讀裏构建_来分析车辆轨迹和人的行动路线,.生物网络则通过图来表示蛋白质间的相互作甩以及基因序列. 图僳分割[1 5 1梟图僳处理的重寒内容,它儒粟将像素分靡到相应对象中. 在图划分中, 每个顶蟲代个像素 象分割即对图中顶点.进行划分. 超大规樓集成电路(VLSI)设计是另一种常见的图划分皮用‘技米, 划分的目的是为了降低VLSI 设计的复杂性?S划分犛一个经典的NP难问题,?it嘗恒定因子的近似算痛 . 目前E有许多关于图划分#法的研究, 但是现有的'图划分算法综述都只養f图论中的画G=<y. E), 并不包括知识图谱的相关内容, 知识_谱划分算法的综述尚未发现? 鉴于此, 本文主要对现有知识縛谱划分算法研究进行较为全面地综述, 襲体据架如茵1 所示.分算法划分算法定界算法互l算法及其衍生n知识图划分算法H多级图划分基于匹配的算法基于聚合的算法j 哈希算法及其衍生j贪心算法及其衍生MFermel算法及其衍生^其他类型图划芬_标签传播算法基于查询负载的算法图1知识图谱划分算法框架图2 按照时间顺序列出了本文所综述的主要算法. 从图中可以看出,KL算法是最早出现的图划分1. 基本图划分算法。谱二分银純]? kl[48]2._多级图划分算^. 流式图划分算法. 分布式图划分算法SRCB^3惯觀#32]D Miller et al.[34] ? 半定规划[ 4S]1妒36]〇〇二賴划㈣Chanet al.[ 30]o〇线性规划[ 則mrsb[29]〇〇melo[31]lingetal.[46-47]3ScalaPart[37]5. 其他类型图划分算法?mrsb[29]□ MetisP^□ ParMetis[ 7ZlKaSPar1 511 □KaPPa[53]□KaFFPa[ 62]□■ DIBAPf?1■Safro et al.lZ{■ PDIBAP1713□WARP1603□EAGRE[61]?ParMetis[ ra]r ,AGrid[7S]哈希算法[73]厶aHDRF[77]贪心算银761 a▲Fennel[78]厶 LDG^ 73】Ginger?0] i3tch[82] ?|?Aydinet al.11011JA-BE-JA-VC[ 89]〇TT^P1^[931ja-be-ja[88]?〇KaFFPaE[63] 〇?I〇GP[KaPPa關〇Meyerhenke et  al .[87] 〇Ugander etaL[ 113禁忌搜索[1CPenget al.[117]Xuetal.[105]?WARP嗍?今今xdgpc1 12]今Meyerhenke et  al .[ 87]^) 谱划分算法) 几何划分算法&分支定界算法?KL算法及其衍生] 基于匹配的算法■基于聚合的算法\ 哈希算法及其衍生、贪心算法及其衍生‘Fennel算法及其衍生> KaPPa#法及其衍生>JA-BE-JA算法及其衍生丨-轻量级重划分算法,签传播算法—基于负载的算法a 其他算法197019801990 2000 2010 2020时间图2知识图谱划分算法时间轴238 计 算机 学 报 2021年算法, 随后出现的是谱划分算法, 之后很长一段时间内都是这两类算法, 直到20 世纪90 年代图划分算法的种类才逐渐增多, 有了几何划分算法和分支定界算法. 早期算法主要在单机环境下运行, 随着图数据规模的增大, 多级图划分算法逐渐兴起, 其将原始图粗糙化为较小图进行划分, 再将结果投射回原始图. 之后随着大规模知识图谱的出现, 多级算法也不能处理现有的大图, 人们开始思考如何将现有算法置于分布式环境下运行, 于是有了分布式图划分算法. 并且将动态图作为划分的输人图, 以适应现实中不断更新的数据. 近几年提出的流式图划分算法将顶点或边转化成流输人, 是另一种划分大规模图的思路.当前知识图谱得到广泛关注,一些专门针对RDF图的划分算法开始出现, 例如基于查询负载的算法.相关工作. 文献[17]对近年来出现的图划分算法进行了综述, 但是侧重于文献列举, 算法介绍较为简单, 本文不仅详细描述了各种算法, 还比文献[17]多了流式图划分算法、标签传播算法和基于查询负载的算法等内容. 文献[18]综述了以顶点为中心的分布式图计算框架, 关于图划分一节的介绍较为简单, 包含的算法类型并不全面. 文献[19]着重分析了分布式框架下的图划分算法, 更侧重于不同框架的性能比较. 文献[20]对已有多级图划分算法进行了综述. 文献[21 22]从顶点划分和边划分两个方面综述了流式图划分算法. 文献[23]综述了云计算环境下进行大规模图数据处理的关键问题, 从单指标和多指标两个方面分析了部分图划分算法. 本文详细介绍5 种类型的知识图谱划分算法, 比上述文献更加综合全面.2 预备知识知识图谱目前并没有一个统一的严格定义. 知识图谱是图G=cy, E) 的某种扩展形式, 其中v是顶点集合, 表示实体, E是边集合, 表示实体间的联系. 实际上, 知识图谱是图数据模型的继承和发展,其在一般图模型的顶点和边上附加更多的属性信息, 用于描述现实世界中事物的广泛联系. 知识图谱主要有以下4 种类型, 分别是RDF图、属性图、 异构信息网络和有向标签图. 有关知识图谱数据管理的详细内容可参见文献[24].RDF图定义为RDF三元组的有限集合. RDF是万维网联盟制定的一种表示网络信息的标准, 通过资源、属性和值来描述特定信息. RDF采用三元组04,〇) 的形式, 其中s4,〇 分别代表语义数据中的主语、谓语和宾语. RDF 图的顶点集合是三元组中主语和宾语的集合, 边集合是谓语的集合. RDF图的形式化定义如下.定义1.RDF图. 设U、B和L为互不相交的无限集合, 分别代表URI、 空顶点( bl anknode) 和字面量( lit eral ).—个三元组〇,f,〇)e(UUB)XUX(UUBUL) 称为RDF三元组, 其中s 是主语 是谓语,〇 是宾语. RDF图G是二兀组(5,/>,〇) 的有限集合.属性图是另一种常用的知识图谱数据模型. 与RDF图相比, 属性图多了一个键值对来表示顶点或边的信息. 属性图的形式化定义如下.定义2. 属性图. 属性图G是四元组(V, E,A 4). 其中:(1) V是顶点的集合;(2) EGVXV是有向边的集合, 如e=( 巧, 巧)表亦e 是从w! 到 的有向边;( 3) 设 是标签集合, 函数A :(YUE)—为顶点或边赋予标签, 如 A( w)=/ 表示顶点w的标签是Z;( 4) 设 是属性集合, VaZ 是值集合, 函数5:(yUE)XProf—VaZ 为顶点或边关联属性, 如p(zProp,a(zVal,S(v, p)=avP的值是a.异构信息网络源自信息网络. 信息网络是指带有对象或链接类型映射的有向图, 如果信息网络中对象或链接的类型总数大于1, 则称为异构信息网络. 其形式化定义如下.定义3. 异构信息网络. 异构信息网络G由三元组(V, E,A) 构成. 其中( 1) V是顶点的集合;( 2) EGVXV是有向边的集合;(3) 设T_y#是类型集合, 函数A : (VUE)—为顶点或边赋予类型, 如/eT_y#, A( ^)=Z表示顶点n 的所属类型是有向标签图是在有向图G=(y, E) 的基础上为每个顶点添加了标签. 其形式化定义如下.定义4. 有向标签图. 有向标签图G由三元组(y, E, L) 构成. 其中( 1) V是顶点的集合;( 2) EGVXV是有向边的集合;王義等; 知班真鬚刻分_*_寒難 23 91 期GT) L是顶点和边上标签的集.合.知识图键泛化、统一了各种图模猶镇枸, 知识图谱与各种图模型的关系如图3 所示..可以看出; 知识图谱扩麗了一般图模型, 通常意义上的图a包含顶点和边; 而知识圈谱增加了顶点和边的属性信息,不钽能够划分和存储, 还能进行查询、推理和挖掘等操作. 有向标签图是最简单的知识图谱模型# 真在一般图模型的基础上增加了标签集#; 图中的任意顶点或边至■少关联一个标签,RDF图可以看作是特殊的有向标签图, 其特殊之处在于一+三元组中的谓语也可作为另一 ?个三元组的生语或宾语反映在有向标聲H中, 即边亦可作为顶点, 顶点与边交集非空.属'性H在一般_模型的基础上进衧扩展, 其增加了顶点癘性和边1 属性的内置支持1 目前被图数据库业羿广泛采用. 异构信息网络和有向标签图相似, 不同的是将标.签换成了所属类型, 且每个顶点或边可以有不止一个所貭类型?知识图谱+顶点+边+划分()+存储()+查询〇RDF图 属性图 异构信息网络 有向标签图+主语十谓语+宾语+标签集合+属性集合+类型集合 +标签集合图3 翱班. _遽翁务种_虐知识图瞥与一般图模型相比含有更加丰竄的信息>通常布一般图模型上的各种图划分算法也适用'于知识厨谱. 为简便起见, 如无特别说明, 本文介绍'的面划分算抜、均普遍适用于各类知识图谱的划分.限于篇幅. 这里以RDFM作为代表, 给 十知识图儀示倒, 如图■! 所:示。定义5. 图划分. 给定_G=(V, £),图划分是将虜G划分成A 部分, 每一部分用朽表示:? 其中fe[1,々i对于任意 ,有p,n巧=0且uh只=G.图划分需要满足式( 1) 或式(: 幻以实现负栽平衡,肩錄_4、化跨趑分 K前諷倉或逾, 这两坝也是判断划分质量好坏的标准.?(1 &)/. isi[Vi|^,ji(\-\-〇)ikci)姐('1— | | 拉丨 S nlXl+ # )fk(2)其中4SU,1 ]是释动诨子,加和《分别代表虜的顶点数和边数,I V,| 和| | 分鄉是:第1 个分区的顶点数和边数?顧划分问道. 已難被证明是KP难间题1 6]._翁人M陣时间'突化时(例如增加或删_一些顶点), 划分可能会失. 去平衡, 因此对于动态图, 需要在划分前设定一个阈值,一旦失衡超过该阈值, 则会重新■进'行: 划分.在图划分算法中:r有两种切分方法>一种是对顶点迸行划分, 另一神是对边进行划分, 圈s 給岀了两种划分方法的示例?猶'? 两种划分方li猶示例(?5璁虚划#雜It点;|rj分慧y同分 . 造腐通诞割'; (b>进爾分将边刻分鑾幕同分区, 栽屬MU翁割>210 计導机攀报: _1苹在顶点划分中》可能存.在跨越分区的边( 姐圈5(a) 中的边(s%儀) 的两个顶点分别麇于不闻分'区 ,更多的跨越边意味羞真大的通債开销, 因此顶点划分的主要优化目标是减少边切割? 词样地, 边划分的主要优化目标是减少顶点切割.由于B有的图划分算法大部分是对图的顶点进行划分, 在本文中如无特别说明匣划分算法均采用顶点划分.表1 给出了图划分算法中的一些常用符号.表1 常用符号符号 描述G/G, 输入图/G的第i 个子集V/V, G中顶点的集合/V的第i 个子集E/E, G中边的集合/E的第i 个子集V G的一个顶点?^和%之间的边n G的顶点数量m G的边数量k G的分区数P/尺 ?的 漏杳/(?SI擊个參KP(v)^所在的分区NCv) 翁播邻顶点鑛合deg(v) ^的度数civ)^的权重3 基本图划分算法本节主:要包括苹期出现的较.为,经典的斑划分箅法 乎条件琅制, 这些算法通常作甩于小规模厨*或者作为子程序应用fii复杂的虜划分方法. 这些算法大部分仅用于图的二分, 但胃以推广到&个分K(例如通过递归: 过程夂3. 1 谱划分算法镩二分法是一种常用的图划分算法,-: 最.攀由Donath等人[2 5]和Fiedler[2 6 2 7]提出, 它通过计箅图对龜的Lapl aee 氣阵L的_二小特貧餘#征食量y,即Fiedl erJt[ 量来瑜定划费标准. 其:中L=D A,是图的度矩阵, A是图的邻接矩阵. L二(/q? 的定义如下:1,如: 第<i罐(t,,)i 如果 )胃1]通过确處.V的中隹_£ 并且将小f或: 等f'兩的顶点分配铪朽*其余顶点分配给巧完成菌划分. 当分区数大于2 时, 可递归地便用谱二分法(RSB】t2 S ],直至达到划分目标.然而, RSB的运行时间较长. 造成较高的成本.文献[2§]使滅多隹方裏乘快遽_轉Fi edl erlt_黧法结构类似于第4节中介绍时多级图划分算法, 它先构造一系列较小的爾, 在粗糙化图上计算Fiedl er阿董,再将向董逐步插值到吏裔级别的■中, 其间使用Rayl eigh 商迭代进行局部改进? 文献[SO-31:!通过使用LdpWe: 矩阵的多个特征_羹將图轟接划分成多个部分, 进一步提高了效率.3. 2 几何划分算法几何划分算法利用谏点的坐标債息对樹进行划分? 坐标二分法DS2是其中最简单的算法? 它基于以下假设: 除了顶点集: 合 ( 巧,%,…) 之外, 还審在可用于顶点的二维或兰潍坐 对于任意奶£V,, 存在; =. 雜雜: 标见. =(■s之; 或三维坐标I? ,=,y, ,氣夂然S'逸择任意. 龜标方甸(: 例如y'方向)作为基准, 根据孩.点的y坐标对所有顶it进行排序_ 将_vM标较小的一半顶点分配给Pi, 其他顶点分配给朽*再使用递归坐标二分法(RCB) 即可对图迸行多路划分.坐:标二分藤的一个缺逼暴太依赖坐=顧, 导款同一图在不同的坐标系中有眷完全不同的划分结巣.惯性划分[ 3 2 3 3]的出现解决了这个问题, 它曹以看作是坐标二分法的改进, 但它投有利用: 坐标轴, 而'是通过选择划分的基准线(或平冒.) L, 使得所■有顶点到L的乎方職最小化, 如画S 所示.(工6 , 3〇Ap,.文献[3445]提出 重叠图的概念, 其特殊类型包括平面图 近邻面和有限元相关?, 划分时需将J维顶. 点随机投巖至J+1 维球体,由逋过中心点的平茴进行二等分*此外,述有将d维顶点降低至一维空间进行划分的空间填充曲线法[3 6 3 7 ], 以及使用画嵌人将坐标赋營图进行划分的方法ps].3. 3 分支定界算法Nf难间题, 通常使用分支定界[3 9]算: 法解决, 这对图划分同祥适用. 分支定界通过将赓始问题分成王義等; 知班真鬚刻分_*_寒難 2411 期两个或多个子问題, 递归地进行求解, 从而找到最佳舊决'方氣分支靈界树的_个节處3#座不同:的乎问题, 算法在原始问题的解决方案基础上保持上界t;sU可以在算法改迸时更新. 要处理树中的节点, 需要在枏瘦子问题的解决.方案上计算下界L.? 如果财剪掉节点, 否则继续分支. 创建两个或更多的子问題. 護个过程如獨7 所: 本.在图划分问题中, 获得上赛和下界的方式有很多, 例如利用线性规划[ 4° 42 ]v丰定规戈1P1 43]、 二次规划d叫等. 文就[46—47]采用组合的方法, 可似划分S大规辏的菌,首先假设A和B是V的两个不相交.子集*其他不: 在A或B中的顶点属于未分配状态,对于A可以扩展成的任意A+, 计算B和A+之间的最小边切割, 从而进行划体读方法可以划分具有上百万个顶点的图, 但其在大规模图上的运行时间较长.3. 4KL算法及其衍生上述算法都是宣接作用于. 原. 始圈进行划分. 除此之外述有 已划#图的改进__i( Kernigban和Lm提出的KL算法[4S]通常被认为是第一个此娄图划分算法. KL算法从任意两个分区开始s 通过交换顶点或顶点集来创建新的划分方案. 从菌改进初始划分方案? 对新的划分方案重复该过程, 直到不能改进为止.假设A和B是y的两个初始分区, 顶点w的增益办是将 从原有分区移至新分区后所减少的切割边数, 这里的&可以是负数. 交縣M点《eA和&eB的增益g为私+g》一其中汛心用来判断顶虑《与6 之间县否存在边*定义如下s极s,&):(4)f 1? 如果: (a,&)否则谁择使备最大化的联處对te,6 ?),一旦遽择a:和6, 之后交换不再考虑《或 依次选择现点对,C fl.2 , SG?卜 /2  !,6卜 /2 !),找出能使fC&,匕〉 逢: 太化的/ , 交换■■處藥ia. i,a. 2,? ?nl'i-1和汍么 KL算法童复以上过程,直到没有政進为止.爾S暴琪点交狹的一个例著,_8 顶歲丨 交雜示MdSA:t>2 和顶轟%交换:后,摩音JS隹徽由i感少筹3》KL: _法'的—t戴: 太lit迸蠢FMuc6ia-Mattii6ys6s(FM)彝法》9]?KL和FM之间的主要区, 别在于顶点移动的单位_ KL一次交换一对顶点, 而FM—犹只移动一个顶点* 这使得FM比KL、效傘:更:禽且役有划分质量的损失.KL算法通常用于其他图划分着法的细化, 特别是在多鈒M划分莫法的反粗糙化阶段. 文献[50]在KL萁法的基础上提出KL(li算法和边界KL算:法fBKL),KL(li算: 法只运行一次KL算:法, 不再进行迭代过裎;BKLX#跨越分区的边所连接的I点集使用KL算法? 在保证质量的同时减少了划分时间.KaSParM考虑了高度M部化的FM算法, 仅从处于边界的未进行粗糙化的顶点开始搜索_进一步痗高了划分效率.是对基本?划分算法的一个小结. 磨划分算法和分支定界算法虽然时间复杂度较高?但是有着良好的划分處義*多适用于在单机上划分规模较小的‘相. 反:? 几何划分#法耗时较少. . 划分质#要差一些, 但可以贫展到分布式坏癘下, 从而划分大规II图数据. KL算法及其改进算法通常与其他算法尤其:是第4 节将介结的多级?划分算法相结合使用, 作为反粗糙化阶段的细化算法.242 计 算 机 学报 2021年表2 基本图划分算法小结类型 优点 缺点 算法 描述谱划分算法引入Laplace 矩阵的特征向量,在小规模图上划分质量较高时间复杂度较高, 不适用于大规模图的划分谱二分法[_?7]RSB[2 8]MRSB[2 9]MELO[31]利用Laplace 矩阵的第二小特征值的特征向量(即Fiedler 向量)将图划分为两部分递归使用谱二分法, 直至达成目标在粗糙化图上计算Fiedler 向量, 再将其逐步插值回原始图使用Laplace 矩阵的多个特征向量直接将图划分成多个部分几何划分算法能够充分利用顶点的坐标信息, 计算简单,可用于大规模图只考虑坐标而不是顶点间的联系, 导致跨越分区的边数较多RCB[2 8]惯性划分[3 2_3 3]Mill er等人[34_35]ISp[3 6]ScalaPart[ 37 ]递归地根据顶点某一方向的坐标将顶点平均分成两部分使所有顶点到基准线(或平面) 的平方和最小化将^维顶点投影至^+1 维球体, 由通过中心点的平面进行划分将^维顶点降低至一维空间, 利用Hilbert 曲线进行划分使用图嵌入将坐标赋予图, 再进行划分分支定界算法利用已有算法计算划分的上界和下界, 在小规模图上取得较好的划分质量计算较为复杂, 不适用于大规模图的划分线性规划[^2]半定规划[41_43]二次规划[44_45]Delling等人[4“7 ]利用线性规划算法确定划分边界利用半定规划算法确定划分边界利用二次规划算法确定划分边界利用组合算法确定划分边界KL算法及其衍生算法计算较为简单, 可以只对图的局部顶点做交换而不用搜索整个图划分时间随迭代次数成正比KL[48]FM[49]BKL[5 0]在已有划分方案基础上交换不同分区的顶点或顶点集在已有划分方案基础上移动顶点到其他分区只对划分边界的顶点进行交换对于知识图谱而言, 使用義本图划分算法时*蕾繫忽略厲暴和边的属性偉息, 将知识?谱当作无向图进行划分?由于基本图划分算法是在单机环墉下迸行的. 通常只猶划分具有上万个顶点和边的知识暖輿.. 不符合现实戀裏f一般情況下不单独使用. 但是这些:算法的基本思想可以被利用并加以改进, 例如在多级图'划分算法中将图粗槌化后的划分阶段,此时图的规模已足够小, 可直狻使用'基本图划分馨法; 另一种情况是将这些箕法扩展到分布式坏境: 下从而进行大规模. 知识图鸯的划分■4 多级图划分算法随着图数据规模的增长*基本图划分算法?已经不能满足实际需要,于是产生了多级图划分算法t52]. 这类算法首先将图G粗糙化为只包含几百个顶点的摘荽H, 在这个小得多的_上进行划分1然后将划分结臬投影回原始图?聱个过輕分为三个阶段: 粗糙化、初始划分和反粗糙化, 如图9 所示.W8 多象廣划;§#_: 示意粗糙化的主要目的. 是生成具有较少自由度的输人图, 这是逋过构造一系列具有萬小M寸的祖糙化图来实现的. 这一#段逋常舊要收缩顶. 点集, 这意味着用粗糙化图中的单个顶点《代替原始图中的部分顶点, 假设L是v中部分顶点的集合t那么c<?.)=乏>(td?收缩时苜能会产生平行边, 类似地, 甩单个边代眷这些边興輟重臀于乎仔边的杈重之和. 这禅使得粗糙化图中的划分 果能够反映原始图申的划分结藥?轉商已裘租槌化至足够小时【即可以使用基本图划分算法进行处埋时 停止粗糙化. 本文中提到的任何基本图划分算法i只要可以处理顶点和边的权重. . 皆胃甩于初始划分.一些代价较高的划分方法在粗糙化图上拥有较好的划分效果, 隹是不意味着在原始图上拥有同样的效果. 有些多级划分算法采用多种筒单方法的组合进行划分, 也可以获得很好?的划分效, 果[1 7]_皮粗槌化即将粗糙化图的划分逐步映射至原始图的划分. 由于原始图比粗糙化图具有更, 多的自由度, 粗糙化图的最隹划分不一定是原始图的最隹划分?p此, 在反租槌化阶段请要利用一些.算法迸行细化(如KL算法夂反粗糙化和细化同时进行, 直至划分结果没有太太变化?多绞图划分算法的难点在于构濟租糙化图》划分和细化算法可#见本文其他小节s 本管:重点介缉粗糙化的两种类型以及对应的划分算法, 分别是基王義等; 知班真鬚刻分_*_寒難I 期于匹配的算法和基于聚合的算法.4.1 基于匹配的算法最常见的粗糙化方法是通过最大匹E得到的.给定图G, 匹?MGE是一组边集集脅中任意厕条边不存在公共顶点*量大I 匹配是指包含最:多数量的边的匹配. 在粗糙化阶段, 匹配中弯条边连接的顶点都用单个顶点代替? 图10是ES配的一个例子, 其中M=?4tecsM)-C^'3■mJ }■Sfil 祖糙化价段的匹?示例一-个紆的K酿獻徽包费#可能多前核寘霄的边, 但同时也希望顶点权重保持平衡[5 3]. 针对这个问题:? 文献[〇]使用评级函数f 对边的权重和均匀性之间的迸行权衡,假设_(:?0代毫斑》 的'杈38署代表顶点《的权重, 文献[53]经实骏验证, 最优评级: 函數为f{ti?£)Witl ' V)ciu^cCv)(5)使用深度优先算法或随机算法可以快速获得最大匹節, 文献[5〇]进一步提出T重边teE、轻边匹E和重面匹. 配等启发式算法. 其中重边匹配在文献[50]中被怔明划分效果最好, 它以随机顺、 序访问■顶点, 优先选择连接顶点的权重最离的未匹配边添加到匹首己.有一些接近钱性时间的算法寄要较大开销, 但是可以.获得吏好的虜量保证,例如贪心算法[ 5 4]、 路径增长:算法(PGA)[5 5]以及结含贪心算法和POA的全局路径算法( GP A)[ 5 6 ].贪心算法的思想非常简?藤重賛: .地将_曹麗?中索匹祗的权童優高的边添加到?配中,直到没有可'选择的边. PGA需要构建一组顶点不枏交路径, 每条路径从任意顶点开始,将与当前顶点《梱邻的未租糙化顶点〃的权麓最大的边e=(v. ?)添加到路径中》 并删除与w相邻的所有边? 如果灣前路径无法扩展, PGA将开始构建新的路径、罝萬没有剩佘边^在增长路径的同財, 选择成为路径的边将交替地添加到匹配Ml 和Mz 中;最终返回二者中的较大僮.. GPA在上述两种算法的基础上, 按照权重降低的顺序扫描边, 构建路径的集合EV然后使用动态规划算法为这些路径计算最大权重匹配?在第一轮GPA完成启3賞在剩余边上运行第二轮GPA, 多数情况下在第二轮过后己經. 没有剩佘边,]?M ETI S^7 5 S ]是最常见的多缘图划分箕法, 它在:粗糖化阶段选择重边匹配, 在划分和细化时使用KL算法, 文献[SCfr次将METIS作用于RDF图..WARP[6 °]进一步扩麗了这种方法, 它将图划分与跨分区的三元簞查询负载感知复制相绪合,, 并通过匹前查询模式扩璩片段*实规高效的查询处理.EAGRE[ 6 13通过在RDF数据中使用实体概念来粗糙化RDF图? 通过对同一类时实体进行分组, 可以_少RDF的查询时间.KaPPaM罩一神基于GPA匹配的分布式多级图划分算法》^ 其分K数量露麥等于所便用的处理器的数量_KaPPa 以及其改进算法KaFFPa[@?KaFFP:aE[ 6 3:r雜寒1令轉细介绍? 此外, KaSF:ar[ 5 1 ]是一个塞于极限思想的图划分算法s 它仅收缩两个级别之间的单条边, 使得不同级别的图只有少量;变化,从而保证划分质量.4. 2 基于聚合的算法除了基于匹袍的算法, 另一种常见的粗糙化方法是基于权重聚合的方法&46 6 ]. 这种方法源自代数多重网格法(amgj£6 71在扠露聚合中, 每个顶点窗以分屬木同的聚合. 祖糙化阶段包食三个步骤: 首先选择?的部?分顶点作为聚合的种子; 然后确: 定计算规则, 可得到属于每个聚合的非种子顶点的权重后计算租糙化顶虑之间的连接强度.权重聚食首先选择一组顶点C匚V, 使得F二V/C中的所有其他顶点强耦合到C. 从 0和F=V开始, 将顶点从F转移到C直至剩佘*?£F_足2Mi}<s&rs)jec,6V-#是■脅参歡(逋攀@知〇-51对于ief, 定义t: 中? 的粗槌化邻域 . 设是图中的神子_/ 的相邻顶点在ife糙化图中的聚合序号, 绖典的AMG矩阵K大小为|V| /|C| ) 的定义如下:Wii /^Pj W,keN{如果如果?'ec^=i否则P叫, 代表I屬于第K:/) 聚合的可能性. 第p个聚合的大小 f 蓬接两个聚合P和 的边、的权}重为kp^klP lq-k參l加权聚合可能导致更密集的粗糙化图, 所以養要谨慎选择AMG方法,同时保证负载均衡? 文献[20]使用代数距离[ 6 S]作为顶点之间连通性的度量,以214 计導机攀报: _1苹获得高质量且负载均衡的划分鍺果. 文敝ns?]提出了一个祖糙化框架*, 真目标是保留图的谱特征,使用随机游走推导祖糙化的待征向量, 但痊代价非常高. D1BAPW和PDIBAP[ n]在细化阶段使用棊于扩散的算法* 能够提升划分质量并且更努地弁行化_表S给出了多级?划分算法的小结? 基千EE的算法因其时间复杂度较小更:为常见s 其中METIS以提出时间早、 速度快、质量高等原因通常?作为其他算法的比较标准?然而, METIS无法倉接应用到, 大规隹厨数据上, 后续算法主荽围绕如何实现更大规模图数据的划分以及如何在分布式条件下进行划分这两个方询发展.目前产业界常用时知识图谱(如DBpedia)在划分时都采用METIS算法的主寒思想,常见做法是将METIS算法集成至分布式系统中以便在不同机器上存储大规模数据.表3 多级图划分算法小结类型 优点 缺点 算法 描述METIS[ 57-58 ]粗糙化阶段使用匹配算法收缩边, 细化阶段使用KL改进算法基于匹配的算法每一级别的顶点只能粗糙化到下一级别的一个顶点上, 计算较为简单时间复杂度与粗糙化的级别有关和图的规模有关, 单机情况下只能划分小规模图WARP[6 0 ]KaPPa[5 3]将METIS算法应用于RDF图, 并通过匹配查询模式进行扩展粗糙化阶段使用GPA算法计算匹配, 并且使用FM算法进行细化KaFFPa[6 2]KaSPar[ 51 ]在KaPPa 的基础上,在粗糙化和反粗糙化阶段进行迭代粗糙化阶段每级仅收缩单条边,细化阶段使用FM算法基于聚合的算法引入AMG算法计算顶点分数, 划分质量较高计算较为复杂, 单个顶点可粗糙化至下一级的多个顶点, 易导致更密集的粗糙化图Safro等人[2 0]DIBAP[7 0]粗糙化阶段使用AMG算法, 并以代数距离作为顶点连通性的度量粗糙化阶段使用AMG算法, 细化阶段使用基于扩散的算法进行改进同基本酉划分算法相似, 多级厨刘分. 算法不考虑知'识图濟的属性倩息》 将知识图谱当作无向图粗糙化后进行划分. 不同之处在于多辍M划分算法对划分包含数十万个顶点和上百方条边的知识掲谱,适用范围要比基本?划分算法更广? 但它仍属于单机环境下的划分算法, _要与第6 节的分布式图划分寘法结合才能划分大规擦知识_谱.》 其中的典型雾禱梟METIS的并行版本parMOSf7 21.5 流式图划分算法流式圈划分算法1:7 3 1舞近年来提出的一种圃划分方法, 流式图划分的目的是为了对太规模流式W数据进行高效率划分. 流式图划分箕祛将图加载为包含顶点或边的序列, 再将每个元素分配. 到对应的分区, 整个过程如图11 所;gt.('顶点流 ?p1〇n〇巧〇巧〇&4〇 %〇吒" ",图ii 德式勝划: fl#?酱德雜素:: 意麗5. 1Hash 算法及其衍生.流式图划分算法中,最筒单的是Hash箕法,它通过构逢棊于散列的映射函数紅; 科一柯进行划分, 菌数A的输人可以是顶点或边的编号.以边为例, 边 C坊,vlfj): 的分区为P(e)=motKfe:) . 这种皂发式算法通f会造成大量ft顶点切割, 虽然时间开销较少但往往木能获得较禽的图划分质量-是对Hash算法的一种改进, 它是一种边划分算法, 主要思想是优先切割更裔度数的顶点. 在DBH算法中, 4(e)的歲义如下:(, 如果》h{ejIB)u(〇, 否则GireP5 ]同样是边划分箕法, 在Hash算法的塞础上,i#加了对分区的约東:(: 幻P (%) 且p (,) gtrs)\p(v,)\ =Ipc-Pi)!.Grid通过构造矩阵XXY使#XY=h: 真中是是分区数. 每一个元素代表?一个分私'再将顶点^通过雇数/! 映射至矩阵中对应的分g编号, 计算与*所属分区同在一行或一列的分区编号集合s 这种方式保怔了每对顶点计算启的交寒都有两个分K, 之后再选择负载较小的分区作为该对顶点对应边的最终分区 Gird蕾粟随时维护分区分配以计隹负载最小的H王 鑫等: 知识图谱划分算法研究综述 2451 期5. 2 贪心算法及其衍生贪心算法[ 7 6 ]是一种基于规则的流式图划分算法, 属于边划分算法, 对于给定边 e 的顶点它遵循的规则如下:a) 如果pu)np(巧) 乒0, 则将e 划分至po,)nf*(巧) 的最小负载分区中;(2) 如果尸(功川尸(巧)=0且 (巧) 乒0, 则将e 划分至P(A)U) 的最小负载分区中;(3) 如果Pfe) 乒0且P(%)=0, 则将e 划分至P( A) 的最小负载分区中;(4) 如果P(W!)=0且P(巧)=0, 则将e 划分至现有的最小负载分区中.LDG[7 3]在贪心算法的基础上, 增加了分区的负载限制. HDRF[ 7 7 ]是对贪心算法的一种改进, 类似于DBH, 将度数纳人考虑范围, 优先对度数较高的顶点进行划分.对于给定边 巧) , HDRF定义分区巧为CIIDRFU,巧, Z) 的最大值:d(. vt )g(v, 〇deg( Vj )ld(v})(9)deg( vt )+deg( Vj)p+(i沢?) ) , 如果z ep(?)i〇 ,否厕Jci idrfu,, z)=a xmaxstze ^1( 10)+e\ maxstze mtnstzeg( vt^y +gi v,, />( id其中, TOamize 和TOiwWze 分别是具有最大负载和最小负载的分区的大小.当A <1 时, 该方法与贪心算法相似, 可能会造成分区不平衡. 为了解决这个问题, 通常设置A>1. 如果A—00, 该方法将趋近于随机划分.H DRF可以在处理输人流的同时维护度信息并对其进行更新, 而不是在分区之前预先计算度, 适用于动态图的划分.5. 3Fennel 算法及其衍生Fennel[ 7 8 ]是另一种常见的流式图划分算法, 它的核心思想是最大化相邻顶点和最小化不相邻顶点. Fennel 与LDG相似, 都需要计算相邻顶点数,不同的是Fennel 需要根据每个分区的负载限制设置最大分配顶点数的阈值. 对于负载低于阈值并且输人顶点被分配给具有最大分数的分区, 计算分数8g( v, Pt ).dg(v, Pt )=\Ptf] N(v)| ?y|P,I71( 12)其中, 参数《 和y 是可调的, 顶点所在的分区为argmaxOg〇,) }. 此外, 文献[79] 提出了基于Fennel 的再划分方法re Fennel, 这是一种迭代算法, 通过利用先前的划分结果来提高图的划分质量,实验表明其效果可与METIS算法相当.受到Fennel 算法的启发, 文献[80]提出了一种名为Gmger 的算法. 它对较低度数的顶点使用类Fennel 算法对顶点及其人边进行划分, 与Fennel 不同的是, Gi nger 的目标函数同时考虑了顶点和边.而对度数较高的顶点, Gi nger 使用Hash 算法对顶点的人边进行划分.然而, Fennel 算法在计算时要提前获知顶点数?和边数m, 这使得其在执行划分时需要保持输人图不变, 不适用于动态图的划分.表4 给出了流式图划分算法的小结, 其他相关细节以及实验结果比较可参见文献[21 22]. 其中文献[22]是流式图划分算法的最新实验性分析结果,通过大量比较实验得出以下结论: Hash 算法是简单但有效的一种方法, 尤其是在降低延迟方面;Fennel 算法更适用于对度数较低的图进行划分, 例如道路交通网络; Gmger算法在像社交网络这样具有长尾分布的图上更加有效; 对于幂率图而言,HDRF则是最佳算法, 因为其较低的顶点切割和均衡的负载可以使图划分获得最佳性能.表4 流式图划分算法小结类型 优点 缺点 算法 描述Hash算法及其衍生计算简单, 时间复杂度低, 可以在划分过程中随时对图进行更新初始随机划分, 导致跨越分区的顶点数较多,划分质量较差Hash算法[73]DBI I[74 ]Grid[75]对顶点或边随机选择分区在Hash算法的基础上, 优先对有更髙度数的顶点进行切割通过构造矩阵得到两个候选分区, 再选择负载较小的分区贪心算法及其衍生适用于动态图的划分, 对幂率图的划分效果明显贪心算法划分质量较差; 改进后的I IDRF时间复杂度较髙贪心算法[76 ]I IDRF[77]基于特定规则选择负载较小的分区在贪心算法的基础上, 优先对有更髙度数的顶点进行切割Fennel 算法及其衍生同时考虑相邻顶点数和非相邻顶点数, 划分质量较髙计算较为复杂; 需要提前获知顶点数和边数,不适用于动态图的划分Fennel[78 ]Ginger[80]在最大化相邻顶点和最小化不相邻顶点之间进行插值低度数顶点使用类Fennel 算法, 髙度数顶点使用Hash算法ma 计導机攀报: _1苹与之前的图划分算法不苘, 流式圈划分算法在划分时需荽将知识慰谱加载为包含顶点或边的序列, 在整个过程中只需一次图遍历, 而不最将菌载入后进行多次迭代计算, 所以能够作用T隹含上亿个顶彘和边的知识图谱,符合大规模知识图谱的划分寒求?6 分布式图划分算法随着?数据规模的不断增大, 如何在分布式环攙下实现图划分算法已成为必餘謙求. 梟常见的方法是开发&有M划分算法的并行版本, 例如, METIS算法的并行版本P紅METIS域、Scotch算法M的并行版本PTScotchES 2 ]. 这两种都是墨于递归二分法的算法, 它们比直接6 分区算法更难乎并行化》 @为在最初的两个分区中,可用的‘并行性较少? 这两种算法属于早期分布式图划分算法:, 本节将去費介绍最近?_ 出的几种典型分布式图划分算法.6. 1KaPPa算法及其衍生Hol tgre观等人M提出了一种分布式多级图划分寘法KaPPa. 该寘法在粗糙化阶段使用文献[S3]提供的分布式匹配算法, 并且便用FM算法进行细化, 使用邻接矩阵存储顶点_边的权重, 使用Hash表存储迁移的顶点和对应的边. 隹迸行局部改进算法之前; 誓粟在每个分区的边界执行广度优先搜索生成顶. 点盡细化操作将在这些顶. 点盡之间进行.KaFFPa[ 6 23#KaPPa齒基撤Lb不考.虑并行化,而是专洼于大规模酉的划分, 扩雇了. 文敵[射-85]引入的多级送代算法*真主鼕思想是在祖糙化和反粗糙化阶段进行迭代,一旦围被划分, 两个分区之. 间的边就不会收缩, 这样可以确保分区赓量* 传统的多缴划分算法H执行一次粗槌化和反粗糙化, 也被称作V循环《2]?KaFFPa提出了两种新的全鳥搜索方法,分别是W搪坏和F循环. W掮环的工作谭理如下:在每个级别上使用不苘的随机种子进行两次独立的粗槌化和反粗糙化, 从而得到更好的划分鍺果. F循环类似于W循环, 区别在于?每一级上最多执行两次递归调用. 不同循环的例子见菌12._It 从左到右依歡: ■參談: 划: 量攀緣_V癖珲 蕭环翁F攝砰KaFFPaE16 3]是KaFFPa的进化:算翁:C:EA.!(版.本, 从图的初始划分开始, 以边切割数作为划分标准, 爵过多轮选择后r每出綦优划分结果.为了避免陷人, 局部最优, 引人变异算子以减缓算法收敛.KaFFPaE定义了两个变异算子风和恥, 它们随机作用T不同顶点, 均执行尸游坏.KaFFPaE的弁行化过程如下: 首先需要估计_的分g数S, 每个处理单元执行划分步骤并测量划分时间/, 再选择S使得创建S个分区的时间约为klal//, 其中/,暴调整参数. 而^, 是图划分的总运行时间?_?个处理傘元多次调用:KaFFPa创:建S个分K, 并以一定概率插人变异算子*^ 只蘩有时间剩?, 算法就錢猶坏进行.文乘[86]改进了KaFFPaE, 能够实现完全平衡的划分? 文献[87:!将KaFFPaE与第7 节的标签传播算法结含, 得到T更高质黧;的图划分效果46. 2JA-BE-JA算法及其衍生Rahi mian等人ts s]提出了名为JA-BEJA的分布式图划分算法, 该算: 法使用局部搜索和模拟退火技术进行S划分. JA-BE-JA算法首先随机均匀地为每个厲点分配一种颜色 指顶点P 的颜色, 具有相同顏色的顶点屬于M—分区.?将JV?(c>定义为具有颜色。的p的银居集合. 顶点ft的邻居敷用A表示, 4(c)=| NJc)| 是具有颜色c 的p的邻居数. 图的賺量定义为具有不同颜色的顶点■ 之间的边数, 因此, 顶总的能羹是其具有不同颜色的邻居的数羞, 并且图的能. 量是顶点的龍量的总和:E(m^\^](A-dv(n〇')C1S1然后将相邻顶点和随机顶点集作.为候选萬点进行搜索, 如果交换顶点颜色后图的能量降低, 则进行交换, 当搜索不到可交换颜色的顶点时. 算法终止?图13f和《? 交换前, 与f颜色相同的邻居数为1, 与《? 颜色相同的邻居数为04和《? 交换后, 与f颜色相同的邻居数为3 , 与《? 颜色相同的邻居数为1, 3+1>1+0,交换后图的能量更高交换过程如图13 所示.王義等; 知班真鬚刻分_*_寒難 2471 期(兩°4()°+ <^(%)°(14)其中, 《?是能鼋函数的参数. 利用模拟退火技术防止陷入局部最优, 引入温度:T并让它随时间减少, 类似于冷却过程fT降为1 时不再下降.JA-BEJAVGts]是JA-BEJA的一个变体真棊于边划分而不是顼点划分. 该算法首先将一组边随机划.分遵不同的分鼠同时允许顶点被复制到多个分E中. 然斿定义每个边和匐个分区的能量函数,根摒系统能量判断是香交换边, 诙算法通过应甩鳥部搜索:算法迭代地改进初始划分.6. 3 轻量级重划分算法为了适应动态图的计算, 需*根据输人图的更新倩息在已有划分基础上再次划分, 这个过程称为a;划分[9 °] m菜重划分箅法仅依赖于薺重新划分的图中的少量信息, 则称其为轻量级重划分算法. 当新顶点加人眉或图的权.重发生变化时, 较董级重划分将被触发.同时通过迭代过程减少边切割, 适用: 于动态靡的划分, 该算法利用奉合顶京权重倉息作为其辅助数据4目比f图的结构倩息》 该数据要小得多.假设@是分區叉中的顶点, 增益 是将 从&移至&所减少的边切割数* 增益可以是负值. 在每次迭代中定义两个阶段* 第一阶段仅允许从具嘗较低编号到较离编号的分区移动顶*s 而第二:阶段仅允许在相友方向上慈动顶点. 如果孩点对以移动至多个分区, 则选择增益最大的分K,当某分區权重超过负载时, 不*向该分区迁移顶点>当投有孩点需蘩移动时, 算法緒東■ ? 整个过程如图14P3:w=3,ec=3P3:Z£f=4fec=3P3:ec=2图w左图食韧龄划 国, 灼,, A代表分区 代表衩歡—代看遠:傷割数, 灰色■默#羞忝请霱要移动至编号更高的分区中(即队^到.ft虐 中_图it: 灰色麗虚_#_奮細餘分区中(即孤朽到ft>rlf倒焉舊義鐵家財的划分圏文就[ ai]提出一种将轻量级重划分集成到Hermes 寒_中的方法!s:雜轉霄嵌人至Neo4jgf数擦库[ 9 2 ], 以支持在分布式环境下进行图划分. 文献[93]将划分分为两个阶段, 逻辑顶点迁移和物理顶点迁移, 在降低通信成本的同时能够更好地豳甩于现实中的大规模西数据.表5 给出了上述几种分布式图划分算法的小结.划分日寸通常会使用分布式H处理框架Map'Redwrf94],通过引入编程樓望来促进高效分布式算法执行, 同时抽象出底屠细节-除此之外, 常用的分布式图处理権架遂有Pregel[ 9 5 ]、GrapliXrs 6 ]、 PcrwerLyxa^。]等,其划分质量与所使用的划分算法有关, 具体细节及相关比较可参见文就D9]. 近年来出现的质量鉸高翁分■布式菌划分算法还: 有ft: Ha4〇epSpark馨梦f式猶樂上M行的DFEP71和Dynami cDFEP19'增纛在栽菌划分箅法I〇GP[ 9 9 ]、 将图转化成树的表5 分布式图划分算法小结类型 优点 缺点 算法 描述KaPPa算法及其衍生引入分布式匹配算法, 使得多级算法能够划分大规模图需要提前存储顶点和边, 不适用于动态图的划分KaPPa[5 3]KaFFPaE[6 3]Meyerhenke等人[S 7]粗糙化阶段使用GPA算法计算匹配, 并且使用FM算法进行细化在KaPPa 的基础上, 在粗糙化和反粗糙化阶段进行F循环将标签传播算法与KaFFPaE相结合JA-BE-JA算法及其衍生计算简单, 局部性强, 且能避免陷入局部最优运行时间与迭代次数呈正相关, 不适用于动态图的划分JA-BE-JA[88]JA-BE-JA-VC[8 9]为每个顶点随机分配颜色, 定义顶点能量, 通过交换顶点减少图的总能量为每个顶点随机分配颜色, 定义边的能量, 通过交换边减少图的总能量轻量级重划分 搜專较小, 可纏 运行时间与迭代次I Iermes[9 1]按照指定顺序迁移顶点, 并将其集成到I lemi es系统中算法 时更新顶点 数呈正相关Planar[9 3 ]将轻量级重划分分为逻辑顶点迁移和物理顶点迁移两个阶段218 计導机攀报: _1苹Sliedp算法[1°°]、基于线形嵌人的划分算法[ ―以及基于定?边交换的分布, 式在线太图划分算铉[1°2 ].可以看出; 分布式图划分算法从原来的研发已有算:法的并行版本遂渐演变为直接在分布式环境下提出新算法. 输入图也不局限于'静态图, 而增加了结合实际需要随时可更新数据的动态图.分布式图划分箅法可用于具有上亿个顶点和边-的大规模图数据的划分, 是目前进行大规模真拿知识图谱划分的主锍算法* 但现有太部分分布式图划分算法不能充分利用知识鮮磨的丰富属性信息.7 其他类型图划分算法除了上述4 种类.型的图划分算法外, 还有一些其他类塑的算法有参较野的图划分敏果, 例如, 基乎遗传/进化算法进行图划分 基于截忌搜索的顶点交换方法[1°4]、■于痦义的RDF图划分箅法?5]、BSP模型的大图划分算法 以及动态平衡图划分算法[ 1 °s ]. 限于篇幅, 本节对其中两种當用的算法类虚进行介_-7.1 标签传播算法标签传播算法(LP A:) [1 °9]首先为每斗顶点随机均匀分配一个标签, 然后迭代地更新顶启: 标签. 在每次迭代中, 顶点将其相邻顶点, 中数量最多的标签作为自己的标甚 签不再軍攻时* 读过程终止; 具有相同标签的顶点属于同一分区? 标签传#算法中顶点更新的过程如图15 所示.隱:15 标雜_卿臟S麗澈自身健但XPA无法保证分区大小平衡, 文献[110]通过提供箱确约束, 即给定分区顶点数羞的上限和下P良以解决该问题? 文献[1X1]提电与METIS结合的算法MLP, 在粗糙化过程中使用LPA, 可划分具有10亿以上顶点的獨.以上两种方法M适用于静态图 xDGI^1 12!^—个基于LPA和顶点迁移的自适斑分布式图划分系统?Spinner[1 1 3]是基于LPA以顶点为中心在Pmgel下实现的图划分算法, 其根据权麗和分区太小为每个顶点赋予对应的分数, 并以此判定顶点■ 是齊迂移至其他分区. 文献[114]将KaFFPa 与LPA结合,并在文献[87]中实现了其分布式算法, 可划分上f乙顶点的國? 旦遞量聲窗于PsrMEXIS和PTi&otdi,但是该方法.在划分知识图谱时需要将其转化为无向图, 未利用知识樹谱的貭性橋息.7. 2 基于查询负载的算法近年乘由于知识函谱的广泛礙用, 出现了一些提升RDF知识請谱查询性能时國划, 分算法, 文献[115]中使用对RDF谓语迸行随机划分的箕法PB, 可在一■定糧度上廉裔査爾效率<还有一些方法则是直接基于查询负载对RDF图进行划分[ 6 °'1 1 6 1 1 7 ], 其中文献[117]增加了查询负载 彳 Qi, Q'2 ,…, (3」. 豫算法的目的暴根据边屬性出现的频繁程度对边进行划分, 从而提齊查询性能. 为了^找羼貧髙访间频率的模式( F AP)瞥要定义FAP使用值謂CQ. p以记录FAP的访问频率, 其中Q是一个SPARQL查询,户是一种频繁钫何糢式.丨1, 如果f是Q的子围use{Q, p)=Cl: ?l〇. 否则馨變镇:式 多命中i询Q的增盤: 为ifew/M#,Q)=|E(岁) |其:中玖束) 是#中滕“'组边. 对于一组频繁模式P=彳九. 九,上的增益是其所有FAP的增益和.BemfitCPfi^S—taa%{Beh:efit(p^ Qi) }(16)算法的优化目标是最太化受存储约束限制的增益?#于这个问题是NP难的, 文献〇117]'莱用贪心算法选择频繁访问模式. M16 是鲠繁访问模式的一个示侧?文職[11〇提出了两种分片策略: 藥直分片和水平分片.垂直分片蕭要将匹配到相同频繁访问模式的图放人_一个分片? 直为单个RDF图包含的频繁访问*式有限, 过滤棹不相关的元素可以提高查询性能.对于圈4的RDF图, 采用图1S 的频繁访向隹式f, —直發片如图1?所亦王 鑫等: 知识图谱划分算法研究综述 249 1 期2016I“ChadwickBoseman”一in-C^^hadwick_Bos^mn^>2015 2018 C^rk_Ruf^I>roleBruceBanner”|图1 7 基于查询负载的垂直分片对于水平分片, 需要将相同频繁访问模式的匹配放入不同的分片中. 首先定义结构简单谓语#为单个频繁访问模式对应的等式或不等式. 假设频繁访问模式f含有变量集合Var={t;an,t;ar2 ,…,t;ar?}, #的定义如下:spipivari)6Value(17)其中 , VaZwe 是常量约束.以图16 的频繁访问模式为例, 可以生成结构简单谓语如下:( 1)spi:p(?xl)=^ChadwickBoseman^;(2)sp2:^( ?xl)^ChadwickBoseman^;(3)spz :pi lx2)—Avengers:Infi nity_War;(4)spA:Avengers:Infi ni ty_War.再将结构最小谓语定义为相同频繁访问模式的#的合取? 给定一组 { 咖, 咖,…,}, 结构最小谓语 {m九,/?^2 ,…, 的定义如下:M—{mpi\Aspk(18)spkeSP其中,=或^^=然后根据结构最小谓语对图进行划分.依然以图16 的频繁访问模式为例, 对应的结构最小谓语如下:(1)/7Z户丄: 户( ?xl)=“ChadwickBoseman”八piP. xZ)=Avengers:Infi nity_War;(2)m户2 : 户( ?xl)=“ChadwickBoseman”八pC"!x2)7^Avengers:Infini ty_War;(3)/tz户3 : 户( ?xl)#“ChadwickBoseman”八^?(?x2)=Avengers:Infi nity_War;(4)77z户4 : 户( ?xl)#“ChadwickBoseman”八^?(?x2)7^Avengers:Infi ni ty_War.图18 显示了从上述结构最小谓语生成的所有水平分片.C^^^gers:Infinity.十2018 饥Pi^Chadwickname^rple<CI^adwick_Bosem^>actsjnacts^n2018y^T2016| mp2“Mark Ruffalo’’| | “Bruce Banner”crk_Ruff?一Iactsjnxp\^C^^gigers:Infinity_^^^>2018“PaulRudd”named^ul_Ru<^H>actsjn8“Ant-man”role’year2015(/uaptain_America^、J:iviLWk^2016| mp4图1 8 基于查询负载的RDF图划分中结构最小谓语m办、 和m九对应的水平分片M分片和水平分片的侧重点不同, 前者利用查询的局部性来提高吞吐儀, 后者旨在通过并行化子查询来縮短查询响应时间, 文献D17]最后在权衡这两种分片策略优勢的塞础上, 提出掘, 合分片策略?表S绐出了以上两种划分奪.法的一个小鍺.表7 汇总了本文介绍的所有类型的知识图谱划分算法, 包括'每种箅法的文献和主要特桌描述?从表中可以看出, 流式图划分算法、分布式图划分算法以及基于查询负载的算法有很大的发,展空间, 应该. 成为未来知识图谱划分的重启研究;riig ■表6 其他类型图划分算法小结焉製: 儒A计肆翁单、 直楼, 划_鍫 爾塗切if象缺蟲UgarKfeK馨人本身不保证负载平衡,需要加限制条件或与xDGPE1 1?其他算法结合. rnSpinner[1 13 ]描述顶点根据约束条件更新自身标签在粗糙化阶段使用标签传播算法在用标签传播算法进行划分后进行顶点迁移根据权重和分区大小为每个顶点赋予分数, 以此判定顶点是否迁移基于查询负载的算法充分考虑了图的结只针对RDF图, 计算构信息和属性信息较为复杂WARP[60]Peng 等人[1 17 ]将METIS算法应用于RDF图, 并通过匹配查询模式进行扩展根据频繁访问模式对RDF图进行划分250 计 算 机 学报2021 年表7 知识图谱划分算法总结类型 名称 文献 描述基本图划分算法谱划分算法几何划分算法分支定界算法KL算法及其衍生[25]?[31][28][32]?[37][40]?[47][48][49][50][51]利用Laplace 矩阵的特征向量对图进行划分根据顶点坐标进行图划分将图划分分成多个子问题递归求解, 从而找到最优解在已有图划分基础上交换顶点多极图划分算法基于匹配的算法基于聚合的算法[50]?[63][64]?[71]将图粗糙化为小图进行划分, 再将划分结果投影回原始图基于GPA匹配的多级划分流式图划分算法Hash算法及其衍生贪心算法及其衍生Fennel 算法及其衍生[73][74][75][76][77][78][79] [80]构建散列函数, 实现随机划分基于特定规则选择负载较小的分区在最大化相邻顶点和最小化不相邻顶点之间进行插值分布式图划分算法KaFFPaE算法及其衍生JABEJA算法及其衍生轻量级重划分算法[53][63][87][88] [89][90][91][93]在每个级别上执行多次粗糙化/反粗糙化过程使用顶点交换和模拟退火技术进行图划分根据图的更新信息进行划分, 顶点按照指定顺序迁移其他类型图划分算法标签传播算法基于查询负载的算法[87][109]?[114][60][116][117]更新顶点标签为最多邻居顶点标签, 多次迭代后得到结果从RDF图中选出常用的查询负载模式, 并以此作为划分依据8 实验分析前文中提到, 知识图谱划分是为知识图谱的分布式存储、查询、 推理和挖掘提供了基础支撑. 本节选取查询和挖掘, 将划分后的数据集上传至集群进行分布式存储, 通过实验比较不同划分算法对查询和挖掘的响应时间, 分析划分效果与二者的内在联系, 并延伸至推理层面.8. 1实验环境实验分析前简要介绍本次实验使用的硬件和软件配置. 硬件配置: 实验集群由5 台腾讯云标准型S5 服务器构成, 每台机器都有4 个CPU和16 GB内存, 系统盘大小50GB, 网络连接为以太网.软件配置: 操作系统为CentOS7.6, 每台机器安装分布式RDF知识图谱数据库管理系统gStoreD?来进行查询, 并使用MPICH3.3.2 来进行集群中多个机器节点间的通信. 实验在合成数据集LUBM和真实数据集DBpedia2019 0830?的实体间链接图文件mappi ngbased_objects_en上完成, 对数据集中的RDF图进行划分, 数据集的具体内容如表8 所示, 其中平均度的定义如下:平均度=边数( 19)表8 最大负载率算法 LUBM100 DBpediaHash 1. 00 1. 00METIS1.031.03I IDRF 1. 00 1. 00JABEJA 1. 00 1. 00PB 1. 61 1. 24实验从前文提到的图划分算法中选取5 种典型算法, 对其图划分效果进行实验验证. 算法包括: 基于随机划分思想的Hash算法、多级图划分算法METIS(见4.1 小节) 、流式图划分算法HDRF?(见5.2 小节) 、分布式图划分算法JABEJA?( 见6.2 小节) 以及基于RDF谓语的划分算法PB?(见7.2 小节).8. 2 划分效果分析由于RDF图是三兀组的集合, 故对于顶点划分算法, 需要将宾语复制到主语所在分区, 以保证三元组的完整性. 第2 节给出了图划分的两个目标, 分别是最小化跨越分区的顶点数或边数以及负载平衡.本小节针对这两个指标展开实验, 选择LUBM100作为LUBM数据集的代表, 在其和DBpedm数据集上使用5 种具有代表性的图划分算法, 分别在2 到1 〇 个分区进行实验. 为了统一划分标准, 通过统计复制顶点数来比较划分效果, 复制顶点数越少说明该算法的划分效果越好, 其结果如图19 所示. 并统计了最大分区顶点数与理想状态下各分区顶点数的比值作为最大负载率, 在表9 给出, 其定义如下:最大分区顶点数最大负载率:(20)负载平衡时各分区的顶点数从图表中可以得出以下结论:(1)Hash 算法的复制顶点数最多, 这是由于Hash算法是一种随机划分的算法, 不能保证划分质量, 同时, Hash算法严格按照平衡分区进行计算. 由前文分析可知, 各类图划分算法的目的均在于减少(DUsinggStoreDlink, ht tps://github.com/bnu05pp/gStoreD.ht ml2019,2,16②DBpediadat asets, ht tps: //wiki, dbpedia. org/develop/dat asets, html2019 , 8 , 30③UsingI IDRFli nk, https: //git hub.com/fabiopet roni/VGP.ht ml2015,7,6④UsingJABEJAlink, ht tps://github. com/fat emehr/jabeja.ht ml20 16,6,7⑤UsingPBli nk, https: //gi thub. com/dicegroup/rdf part itioning. html2018,7 ,12王義等; 知班真鬚刻分_*_寒難 25 11 期(a) LUBMlOO不同机器间时通信开销, 而Hash算法的目的只是为了快速划分, 并不考虚划分质量■, 故其他i 种算法的复制 点数均小于 吨算法..( 2)MfitE算法在这两个数据集上的纖合划分效果最好, 特到是在DBpedia■ 数据集下, 其平均复制顶点数仅为Hash算法的仏2%,并且明显少于另外3种算法, 这也是目前在较小规模團上最常用METIS舊法敵麋卸此外, METIS算法在粗糙化图上进行平衡划分, 但是在投射回縻始图时会造成一定的備差, 导致最终负载稍有不平衡?(幻HDRF算法在LUBM数据集下的划分效10图19Numberofpartitions(b )DBpedia不_1身饕蠢■复制琪虞戆果更好, 主要原因在于HD. RF箕法适甩于蓁率图,而LUBM数据集的平均度更高, 说明其包含的高次顶点数要多于DBpedis 数据集4更有利于: HDRF算法的运行.(4)JA-BE-JA箅法的划分效果在这5 种算法中处于中等水平 其适用范围较广, 更适含在大规模数提集上进行划分? 由于该算酱是祖已绫划分好的平衡分区上进行顶点交换, 所以可以保持負载突全平衡.切PB算法的复制顸点数较多, 仅次于mi sh算法, 这是H为它在划分时主要基于的是一种随机方法7 同时, 诶算法役有考虑负载平衡, 在一定程度J:降低了复制顶点数.表9实验所用数据集数据集 大小 顶点数 边数 平均度=边数/顶点数LUBM20341 M 663647 2 687 596 4. 05LUBM40676 M 1 308274 5495742 4.20LUBM LUBM60 0. 9 9G 1971 871 8002472 4. 06LUBM801.33G 2 642 81010726 415 4. 06LUBM1001.6 6G 3 301 718 13 403 134 4. 06DBpedia mappi ngbased_objects_en 1.52G 425 6892 11 018 249 2.598. 3 查询时间分析本组实验对比了不同划分算法在分区数为4 时的查询时间鼻体实现方法是在LUBM数据集和DBped'i a 数据集上进行划分疴,对LUBM数据菜使用查询Q1、 Q2 和Q3, 对DBpedi a数据集使用查询DQ1、DQ2:和DQ3, 同时记議查询的响: 愈: 时间s 其中Qr和DQI 讓于星麵慮询, Q2、 Q3、DQ2 和0<3¥麗乎复. 杂查询, 娘和DQ&匹配的查询数要远超过Q2和DQ.2, 査询难度依歡增加, &询暴旬可在附录中查墙,图20 和阌21 分别展示了这爾组数摒集上的实验结巣.在LUB.M数摒梟上, 显縣Hash算法的查询时间在5种算. 法中是最长的,:PB箕法的查询时间'量短, 而其他3 种划分算法并无屋著差别.从图20 (a.)可以着出, 各类算法在简单查询上的查询时间差别不太、, 尤其, 是在较小数据集LUBM2〇 和LUBM^上, 二牽?的查询时间几乎相两. . 随着查询难度的增加,图2CKW开始有较明显的_距;》 宣到■在图20心)中, Hash算法在. LUBM10.0数据集上的查询时间与PB算法相差12.9s,达到最大.在DBpedk数裾集上的锗果与LUBM数据集相似, 不同的是差距要小一些, 在图21(cjrJl: 方能看到较为清楚的结果. 这与两个数据集的平均度有关系,DBpedi a数据集的乎均度小, 导致可四配时查询数少, 对应的查询时间降低? 相比较而言*在DBpedia数据集JlMETTS: 算法的查询效果聲比LUBM数据集上更奸一通过对比划分效果图可知, 查询时间与复制顶25 2 计 算机 学 报 2021年LUBM20LUBM40LUBM60LUBM80LUBM100Datasets(a) 查询Q1的运行时间LUBM20LUBM40LUBM60LUBM80LUBM100DatasetsLUBM20LUBM40LUBM60LOBM80LUBM100Datasets(c) 查询Q3的运行时间图20不同划分算法在LUBM数据集上的查询时间0.51°a〇Graphpartitioningalgorithms(a) DQlGraph partitioningalgorithms(b) DQ2Graph partitioningalgorithms(c) DQ3,釘 本獨划分霉徵在DBpsjia黎載集上的查询时间点数总体JL呈正相关?Hash箅法的划分效果最差,所以查■询耗时最长,METIS算法在DBpedk数据集1: 的划分效果敏好,:对座簡查_用-时植少:, 这是:由于随机分配导致围处理財跨机器的计算较多, 逋偾时间太大增加, 查询时间随之增长. PB算法的情况诗殊.興其增加了根据谓语进行划分这一环节,提;高了査询效率. 所以它的查询时间要少于其他划分算法?由此可得出结论, 对于大部分知识图谱划分算法, 跨越分K的顶点数或边数越多, 基于此种知识窗谱划分算法的查询处理时间就越长.8,4 挖掘时间分析由于数据挖掘是从大量数据中搜索隐藏信:息, 这里来用复齋查询方式达到这一目的* 在LUBM100数据集和DBpedk数据集上分别使用挖掘谱句DM1和DM2, 挖掘语句可參见附录,图22展示了不同划分算法在两个数据集上分区数为4 时的挖掘时间.与查询结某相似,Hadi 算法的挖掘时间明屬超过其他4 种算法, PB算法的时间最魔, METIS算王 鑫等: 知识图谱划分算法研究综述 2531 期Graphpartitioningalgorithms(a)LUBM100Graph partitioningalgorithms图 不同划分!壽糖猶挖掘法次之. 不同的是, 因为挖掘耗时较长, 各个箅法闻的差距比查询时吏大. 所以对于挖掘来说, 奠运行时间主要与算法的划分效果有关, 跨越分区的顶点数或边数越多?执行数据挖掘时的通債开铕就越大, 相应的运行时间也越长.我们相信,读结论同样适;fl予知识图谱的推理,因为任何在知 图请上进行的分布式计箅都需要考虑通倩开锴的问题*而'图划分的目标是减少跨越分K的顶点或边, 从而减少通信时间, 根抿上述实验-分析可知, 知识图谱划分效果越好,划分后进行査询、推理和挖掘等操作的时向就越少.8. 5 实验总结表10给出了率节实验效果的一个总结. 显然,Hash'算法的划分敏臬、 聋_效果和挖掘效果较差,祖是它的时间复杂度低, 容易实现, 适合在大规模图上霧要'快速划分的倩况; METIS算法的整体效畢较好, 在DBpecUa 数据集上_现最为明显, 但也有其简限性, 只适用于本地环境下规模较小的数据集;HDRF算法和JA-BEJA算法处乎中间水平, 不同的蕞HDRF算法更:适甩于幂率K_, 所以在LUB. M数据集上的划分、查:询、挖掘效果要比JA-BE-JA算法更好; PB算法的划分效果较差,但是查询和挖掘效果最好兩行时间少, 适合騫栗快速进#RDF圈"计算的情况. 综上所述, 没有哪一种算法在所宥情况T都是最好的, 爵赛根据实际情况选择合适的算法,从而高效地实现知识图儀分布式存储、 蜜询、推埋、挖掘等一系列操作*表10 实验效果总结算法 划分效果 查询效果 挖掘效果Hash 负载平衡, 复制顶点数最多 查询时间最长 挖掘时间最长METIS 负载稍不平衡, 但复制顶点数最少, 特别是在DBpedia数据集上 查询时间较短 挖掘时间较短I IDRF 负载平衡, 复制顶点数较少, 在LUBM数据集上效果更好 查询时间较长 挖掘时间较长JA-BE-JA 负载平衡, 复制顶点数较少 查询时间较长 挖掘时间较长PB 负载不平衡, 复制顶点数较多 查询时间最短 挖掘时间最短9 未来研究方向逋过上述分析与比较, 可以#出知识圈瓚划分已轻取得了一定的成臬a提出了不少成熟的理论和算法?偉是, 现存的钿识菌谱刘分算法的理论、方法与技术尚有许多灣限性?仍面临翁许多问蘧和挑战,进一步.研ft建處包:猶(1) 知识圈11划分标准与算法效率如何权衡本文介绍的知识图谱的划分算法大部分是顧一般图划分寡法的基础ii迸行的, 由予知识图谱包含燈息要比一般的图獏31丰富和复杂, 划分通當和后期的1存储查询枏结合, 增加了划分难度. 传统的图划分方法以降低顶点或边的切割数为划分員标, 以负载是否平衡、 是否具有较小的时间复杂度等作为衡量划分好坏的标准. 但是对于知识fi谱而言, 除了这些以外, 还应以知识图贵的图结构和属牲翁息作为划分标准, _分是为了更好地执行后续的存储、 查询、推理和挖掘操作? 此外, 知识图谱数据镆型尚未有统一定义, 也没有确定的标淮. 所以讀耍深入研充针对知识围谱的划分算法<做到既要有利于支持知识時谱查询的快速执行, 又繫避免划分算法复杂度过窗^( 2) 面询知识野谱窗层语义如何划分知识图谱的一个重要”特点是对本体的表示. 以254 计 算机 学 报 2021年RDF图为例, 其源于语义Web的发展, 其在标准制定之初即面向Web 上全局资源的表示、发布和集成,在RDF图之上定义了RDF模式语言(RDFSchema)和Web本体语言(OWL) , 可用于表示丰富的高级语义知识. 虽然目前已经有了针对RDF图语义划分的算法, 但是还没有考虑利用本体语言作为启发信息进行划分. 如何利用知识图谱高层语义指导划分是非常重要的研究方向.(3) 面向知识图谱应用需求如何划分知识图谱的应用领域非常广泛, 在社交网络、道路交通、 电子商务等方面都有着重要作用. 以电子商务为例, 企业可以构建用户的知识图谱, 对用户的商品查询情况、 购买记录进行分析, 将用户划分至对应的消费人群. 知识图谱的领域应用研究正处于起步阶段, 目前各个领域特定的知识图谱划分结果还没有相应的质量评价指标, 如何针对应用需求进行知识图谱划分还需要进行深人研究.(4) 超大规模知识图谱如何划分目前, 大规模知识图谱划分普遍使用分布式算法, 例如, 基于MapReduce、Pregel、MPI 等已有分布式处理框架进行划分.但是随着具有数十亿三元组规模的知识图谱不断涌现, 现有分布式方法已不足以应对超大规模知识图谱的划分, 通常会导致算法运行时间增长, 不同机器间跨越边数或顶点数增多, 通信成本增加等. 这就需要进一步研究超大规模知识图谱的高效划分方法, 使得知识图谱在负载尽量均衡的情况下减少不同机器间的通信开销, 在满足划分目标的同时降低划分算法的复杂度.(5) 基于知识图谱表示学习如何划分近年来, 知识图谱表示学习开始兴起, 其主要思想是将知识图谱的实体和关系嵌人到低维向量空间中, 在保留结构信息的同时有效支持下游任务. 基于知识图谱表示学习的划分方法是一个值得研究的新方向, 目前已有的方法是在图嵌人后利用坐标信息,使用几何划分方法进行划分. 但这些算法只限于单机环境, 还没有扩展到分布式框架上. 如何更好地将表示学习与其他常用的划分方法特别是分布式图划分算法结合, 从而提高划分的效率和质量是非常有意义的研究课题.(6) 知识图谱划分如何支持存储查询知识图谱划分是分布式存储的必要手段, 划分的目的是为了更好地执行后续的存储查询. 所以划分阶段需要考虑存储查询, 同样地, 执行存储查询时也需要考虑划分.当前已经有基于查询负载的知识图谱划分算法, 但都是基于静态图的划分. 在现实应用中, 知识图谱数据会随时间而动态变化, 需要及时更新划分的输人图. 如何使其与动态图划分算法更好地结合, 以及如何对划分算法与存储查询方案融合进行优化设计仍需进一步研究.10总 结知识图谱以精确的语义描述了现实世界中的实体以及实体间的关系, 有着广泛的应用. 知识图谱划分作为大规模知识图谱分布式处理的首要工作, 具有十分重要的意义. 本文对现有知识图谱划分算法进行了研究综述, 介绍了4 种基本图划分算法, 比较了多级图划分算法的2 种类型, 给出了流式图划分算法的主要思想, 描述了3 种分布式图划分算法, 介绍了最近提出的2 种新型图划分算法, 在合成与真实知识图谱数据集上探究了5 种知识图谱代表性划分算法在划分效果、查询处理与图数据挖掘方面的性能差异, 最后展望了知识图谱划分算法的未来研究方向.致 谢 感谢湖南大学信息科学与工程学院彭鹏博士在实验环境配置中提供的帮助, 同时感谢编辑部和审稿人给予本文的宝贵意见!

[返回]
上一篇:大数据_小数据_问题_以小见大的洞察_陈国青
下一篇:新一轮收储制度改革导致玉米减产了吗_基于DID模型的分析_阮荣平