第４４ 卷 第１ 期２０２１ 年１ 月计 算机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ ．４４Ｎｏ．１Ｊａｎ． ２０２１知识图谱划分算法研究综述王 鑫 陈蔚雪 杨雅君 张小旺 冯志勇（天津大学智能与计算学部 天津 ３００３５４）（天津市认知计算与应用重点实验室 天津 ３００ ３５ ４）摘 要 知识图谱是人工智能的重要基石， 因其包含丰富的图结构和属性信息而受到广泛关注．知识图谱可以精确语义描述现实世界中的各种实体及其联系， 其中顶点表示实体， 边表示实体间的联系．知识图谱划分是大规模知识图谱分布式处理的首要工作， 对知识图谱分布式存储、 查询、推理和挖掘起基础支撑作用．随着知识图谱数据规模及分布式处理需求的不断增长， 如何对其进行划分已成为目前知识图谱研究的热点问题．从知识图谱和图划分的定义出发， 系统性地介绍当前知识图谱数据划分的各类算法， 包括基本、多级、流式、分布式和其他类型图划分算法． 首先， 介绍４ 种基本图划分算法： 谱划分算法、 几何划分算法、分支定界算法、ＫＬ及其衍生算法， 这类算法通常用于小规模图数据或作为其他划分算法的一部分； 然后， 介绍多级图划分算法， 这类算法对图粗糙化后进行划分再投射回原始图， 根据粗糙化过程分为基于匹配的算法和基于聚合的算法； 其次， 描述３ 种流式图划分算法， 这类算法将顶点或边加载为序列后进行划分， 包括Ｈａｓｈ算法、贪心算法、 Ｆｅｎｎｅｌ 算法， 以及这３ 种算法的衍生算法； 再次，介绍以ＫａＰＰａＪ八ＢＥＪＡ和轻量级重划分为代表的分布式图划分算法及它们的衍生算法； 同时， 在其他类型图划分算法中， 介绍近年来新兴的２ 种图划分算法： 标签传播算法和基于查询负载的算法． 通过在合成与真实知识图谱数据集上的丰富实验， 比较了５ 类知识图谱代表性划分算法在划分效果、查询处理与图数据挖掘方面的性能差异，分析实验结果并推广到推理层面， 获得了基于实验的知识图谱划分算法性能评价结论． 最后， 在对已有方法分析和比较的基础上， 总结目前知识图谱数据划分面临的主要挑战， 提出相应的研究问题， 并展望未来的研究方向．关键词 知识图谱； 图划分； 多级划分； 流划分； 分布式中图法分类号ＴＰ３ １１ＤＯＩ号１ ０． １ １８９ ７／ＳＰ．Ｊ． １０１ ６． ２０２１ ． ００２３５ＲｅｓｅａｒｃｈｏｎＫｎｏｗｌｅｄｇｅＧｒａｐｈＰａｒｔｉｔｉｏｎｉｎｇＡｌｇｏｒｉｔｈｍｓ：ＡＳｕｒｖｅｙＷＡＮＧＸｉ ｎＣＨＥＮＷｅｉ ＸｕｅＹＡＮＧＹａＪｕｎＺＨＡＮＧＸｉ ａｏ ＷａｎｇＦＥＮＧＺｈｉ Ｙｏｎｇ（． Ｃｏｌ ｌｅｇｅｏｆＩｎｔｅｌｌ ｉｇｅｎｃｅａｎｄＣｏｍｐｕｔ ｉｎｇ？Ｔｉａｎｊｉ ｎＵｎｉ ｖｅｒｓｉｔｙ？Ｔｉａｎｊｉｎ３００３５４）（ ＴｉａｎｊｉｎＫｅｙＬａｂｏｒａｔ ｏｒｙｏｆＣｏｇｎｉ ｔｉｖｅＣｏｍｐｕｔ ｉｎｇａｎｄＡｐｐｌ ｉｃａｉｉ ｏｎＴｉａｎｊｉｎ３００３５４）ＡｂｓｔｒａｃｔＫｎｏｗｌ ｅｄｇｅｇｒａｐｈｓａｒｅｉｍｐｏｒｔａｎｔｃｏｒｎｅｒｓｔｏｎｅｓｏｆａｒｔｉ ｆｉｃｉａｌｉ ｎｔ ｅｌ ｌｉｇｅｎｃｅ，ｗｈｉｃｈｎｏｔｏｎｌ ｙｈａｖｅｔｈｅｇｒａｐｈｓｔｒｕｃｔｕｒｅｏｆｔｈｅｇｅｎｅｒａｌｇｒａｐｈｍｏｄｅｌｂｕｔａｌ ｓｏｃｏｎｔａｉ ｎｒｉｃｈａｔｔｒｉ ｂｕｔｅｉ ｎｆｏｒｍａｔｉ ｏｎｏｆｖｅｒｔｉｃｅｓａｎｄｅｄｇｅｓ．Ｔｈｅｒｅｆｏｒｅ，ｋｎｏｗｌｅｄｇｅｇｒａｐｈｓｈａｖｅｒｅｃｅｉ ｖｅｄｗｉ ｄｅｓｐｒｅａｄａｔｔｅｎｔｉ ｏｎｉ ｎｐｒａｃｔｉｃａｌｔａｓｋｓ． Ｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｓｃａｎｕｓｅａｃｃｕｒａｔｅｓｅｍａｎｔｉｃｓｔｏｄｅｓｃｒｉ ｂｅｔｈｅｖａｒｉ ｏｕｓｅｎｔｉｔｉｅｓａｎｄｔｈｅｉｒｃｏｎｎｅｃｔｉ ｏｎｓｉ ｎｔｈｅｒｅａｌ ｗｏｒｌ ｄ，ｗｈｅｒｅｔｈｅｖｅｒｔｉｃｅｓｒｅｐｒｅｓｅｎｔｅｎｔｉｔｉｅｓ，ａｎｄｔｈｅｅｄｇｅｓｒｅｐｒｅｓｅｎｔｃｏｎｎｅｃｔｉ ｏｎｓａｍｏｎｇｔｈｅｓｅｅｎｔｉ ｔｉｅｓ．Ｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｐａｒｔｉ ｔｉｏｎｉｎｇｉ ｓａｆｕｎｄａｍｅｎｔａｌ ｔａｓｋｆｏｒｄｉ ｓｔｒｉ ｂｕｔｅｄｐｒｏｃｅｓｓｉ ｎｇｏｆｌ ａｒｇｅ ｓｃａｌ ｅｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｓ，ａｎｄｉ ｔｉ ｓｔｈｅｅｓｓｅｎｔｉ ａｌ ｓｕｐｐｏｒｔｆｏｒａｓｅｒｉ ｅｓｏｆｇｒａｐｈｐｒｏｃｅｓｓｉｎｇｏｐｅｒａｔｉ ｏｎｓｉ ｎｃｌｕｄｉｎｇｄｉ ｓｔｒｉｂｕｔｅｄｓｔｏｒａｇｅ，ｑｕｅｒｙｐｒｏｃｅｓｓｉ ｎｇ，ｒｅａｓｏｎｉｎｇ，ａｎｄｄａｔａｍｉ ｎｉ ｎｇ．Ｗｉｔｈｔｈｅｉ ｎｃｒｅａｓｉ ｎｇｓｃａｌ ｅｏｆｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｓａｎｄｍｏｒｅｒｅｑｕｉｒｅｍｅｎｔｓｏｆｄｉｓｔｒｉ ｂｕｔｅｄｐｒｏｃｅｓｓｉｎｇ，ｉｔｉｓｄｉ ｆｆｉｃｕｌ ｔｔｏｐａｒｔｉｔｉ ｏｎｌ ａｒｇｅ ｓｃａｌ ｅｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｓ，ｗｈｉｃｈｈａｓｂｅｃｏｍｅａｈｏｔｉｓｓｕｅｉ ｎｔｈｅｃｕｒｒｅｎｔ收稿日期：２０１９ ０９ ０５； 在线发布日期：２０２０ ０２ ０５．本课题得到国家重点研发计划项目（２０１９ＹＦＥ０１９８６００） 、 国家自然科学基金（６１９７２２７５） 资助． 王 鑫， 博士， 教授， 中国计算机学会（ ＣＣＦ） 杰出会员， 主要研究领域为知识图谱数据管理、 图数据库、 大规模知识处理． Ｅｍａｉｌ：ｗａｎｇｘ＠ｔｊｕ． ｅｄｕ．ｃｎ． 陈蔚雪， 硕士研究生， 主要研究方向为知识图谱数据管理、 图数据库、 大规模知识处理． 杨雅君， 博士， 副教授， 中国计算机学会（ ＣＣＦ） 会员， 主要研究方向为图数据库、 图数据挖掘． 张小旺， 博士， 副教授， 中国计算机学会（ ＣＣＦ） 会员， 主要研究方向为数据库、人工智能、 知识图谱． 冯志勇， 博士， 教授， 中国计算机学会（ ＣＣＦ） 杰出会员， 主要研究领域为知识工程、 服务计算．２３６ 计 算机 学 报 ２０２１年ｒｅｓｅａｒｃｈｏｎｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｓ．Ｓｔａｒｔｉ ｎｇｆｒｏｍｔｈｅｄｅｆｉ ｎｉｔｉ ｏｎｓｏｆｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｓａｎｄｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉ ｎｇ，ｗｅｓｙｓｔｅｍａｔｉｃａｌ ｌ ｙｉ ｎｔｒｏｄｕｃｅｖａｒｉｏｕｓａｌｇｏｒｉｔｈｍｓｃｕｒｒｅｎｔｌ ｙａｖａｉｌ ａｂｌ ｅｆｏｒｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉｎｇ，ｉ ｎｃｌ ｕｄｉ ｎｇｂａｓｉｃｇｒａｐｈｐａｒｔｉｔｉｏｎｉ ｎｇａｌｇｏｒｉｔｈｍｓ，ｍｕｌ ｔｉｌ ｅｖｅｌｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉ ｎｇａｌ ｇｏｒｉｔｈｍｓ，ｓｔｒｅａｍｉｎｇｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉ ｎｇａｌ ｇｏｒｉｔｈｍｓ，ｄｉｓｔｒｉ ｂｕｔｅｄｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉ ｎｇａｌ ｇｏｒｉｔｈｍｓ，ａｎｄｏｔｈｅｒｔｙｐｅｓｏｆｇｒａｐｈｐａｒｔｉ ｔｉ ｏｎｉｎｇａｌｇｏｒｉｔｈｍｓ．Ｆｉｒｓｔ，ｆｏｕｒｂａｓｉｃｇｒａｐｈｐａｒｔｉ ｔｉ ｏｎｉｎｇａｌｇｏｒｉ ｔｈｍｓａｒｅｒｅｖｉ ｅｗｅｄ，ｉ ｎｃｌ ｕｄｉ ｎｇｓｐｅｃｔｒａｌｐａｒｔｉｔｉ ｏｎｉ ｎｇａｌｇｏｒｉ ｔｈｍｓ，ｇｅｏｍｅｔｒｉ ｃｐａｒｔｉ ｔｉ ｏｎｉ ｎｇａｌｇｏｒｉ ｔｈｍｓ，ｂｒａｎｃｈａｎｄｂｏｕｎｄａｌｇｏｒｉ ｔｈｍｓ，ＫＬａｎｄｉ ｔｓｄｅｒｉ ｖａｔｉｖｅａｌｇｏｒｉ ｔｈｍｓ． Ｔｈｉ ｓｔｙｐｅｏｆａｌｇｏｒｉ ｔｈｍｓｕｓｕａｌ ｌ ｙｗｏｒｋｓｏｎｓｍａｌ ｌ ｓｃａｌ ｅｇｒａｐｈｓｏｒａｓｓｕｂｒｏｕｔｉ ｎｅｓｆｏｒｍｏｒｅｓｏｐｈｉ ｓｔｉ ｃａｔｅｄａｌｇｏｒｉ ｔｈｍｓ．Ｓｅｃｏｎｄ， ｔｗｏｍｕｌ ｔｉｌ ｅｖｅｌｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉｎｇａｌｇｏｒｉｔｈｍｓａｒｅｉ ｎｔｒｏｄｕｃｅｄ，ｏｎｅｏｆｗｈｉｃｈｕｓｅｓｔｈｅｍａｔｃｈｉ ｎｇｂａｓｅｄａｌｇｏｒｉｔｈｍｄｕｒｉ ｎｇｔｈｅｃｏａｒｓｅｎｉ ｎｇｐｈａｓｅ， ａｎｄｔｈｅｏｔｈｅｒｕｓｅｓｔｈｅａｇｇｒｅｇａｔｉ ｏｎ ｂａｓｅｄａｌｇｏｒｉ ｔｈｍ．Ａｆｔｅｒｃｏａｒｓｅｎｉ ｎｇ，ｔｈｅｙｐａｒｔｉ ｔｉ ｏｎｔｈｅｍｕｃｈｓｍａｌ ｌｅｒｇｒａｐｈａｎｄｔｈｅｎｐｒｏｊｅｃｔｔｈｅｒｅｓｕｌ ｔｂａｃｋｔｏｔｈｅｏｒｉｇｉ ｎａｌｇｒａｐｈ．Ｔｈｉ ｒｄ，ｓｔｒｅａｍｉ ｎｇｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉ ｎｇａｌｇｏｒｉ ｔｈｍｓａｒｅｄｅｓｃｒｉ ｂｅｄ，ｗｈｉ ｃｈｌ ｏａｄａｇｒａｐｈａｓａｓｅｑｕｅｎｃｅｏｆｖｅｒｔｉ ｃｅｓｏｒｅｄｇｅｓａｎｄａｓｓｉｇｎｅａｃｈｅｌ ｅｍｅｎｔｔｏｔｈｅｃｏｒｒｅｓｐｏｎｄｉ ｎｇｐａｒｔｉ ｔｉ ｏｎｓ． Ｔｈｅｓｔｒｅａｍｉ ｎｇｇｒａｐｈｐａｒｔｉ ｔｉｏｎｉ ｎｇａｌｇｏｒｉ ｔｈｍｓｃａｎｂｅｆｕｒｔｈｅｒｄｉ ｖｉ ｄｅｄｉ ｎｔｏｔｈｒｅｅｓｕｂｃａｔｅｇｏｒｉ ｅｓ：ｔｈｅｈａｓｈａｌｇｏｒｉｔｈｍ， ｔｈｅｇｒｅｅｄｙａｌｇｏｒｉｔｈｍ， ｔｈｅＦｅｎｎｅｌ ａｌｇｏｒｉｔｈｍ， ａｎｄｔｈｅｉｒｄｅｒｉ ｖａｔｉｖｅａｌｇｏｒｉｔｈｍｓ．Ｆｏｕｒｔｈ，ｗｅｉ ｎｔｒｏｄｕｃｅｄｉｓｔｒｉ ｂｕｔｅｄｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉ ｎｇａｌｇｏｒｉｔｈｍｓｆｏｒｐａｒｔｉｔｉ ｏｎｉ ｎｇｌ ａｒｇｅ ｓｃａｌ ｅｇｒａｐｈｓｉ ｎｄｉｓｔｒｉｂｕｔｅｄｅｎｖｉｒｏｎｍｅｎｔｓ．Ｗｅｃｈｏｏｓｅｔｈｒｅｅｒｅｐｒｅｓｅｎｔａｔｉ ｖｅａｌｇｏｒｉｔｈｍｓ，ｎａｍｅｌ ｙｔｈｅＫａＰＰａａｌｇｏｒｉｔｈｍ，ｔｈｅＪＡＢＥＪＡａｌｇｏｒｉ ｔｈｍ，ｔｈｅｌｉｇｈｔｗｅｉｇｈｔｒｅｐａｒｔｉ ｔｉ ｏｎｉｎｇａｌｇｏｒｉｔｈｍ，ａｎｄｔｈｅｎｄｅｓｃｒｉ ｂｅｄｅｒｉ ｖａｔｉ ｖｅａｌｇｏｒｉｔｈｍｓｏｆｔｈｅｓｅｄｉ ｓｔｒｉ ｂｕｔ ｅｄａｌｇｏｒｉ ｔｈｍｓ． Ｍｅａｎｗｈｉ ｌ ｅ，ａｓｔｈｅｏｔｈｅｒｔｙｐｅｓｏｆｇｒａｐｈｐａｒｔｉ ｔｉ ｏｎｉ ｎｇａｌｇｏｒｉｔｈｍｓ，ｗｅｐｒｅｓｅｎｔｔｗｏｒｅｃｅｎｔｇｒａｐｈｐａｒｔｉ ｔｉ ｏｎｉ ｎｇａｌｇｏｒｉ ｔｈｍｓ，ｏｎｅｉ ｓｔｈｅｌ ａｂｅｌｐｒｏｐａｇａｔｉ ｏｎａｌｇｏｒｉｔｈｍ，ａｎｄｔｈｅｏｔｈｅｒｉ ｓｔｈｅｑｕｅｒｙｗｏｒｋｌ ｏａｄ ｂａｓｅｄａｌｇｏｒｉ ｔｈｍ． Ｂｙｃｏｎｄｕｃｔｉｎｇｅｘｔｅｎｓｉ ｖｅｅｘｐｅｒｉｍｅｎｔｓｏｎｂｏｔｈｓｙｎｔｈｅｔｉｃａｎｄｒｅａｌｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｄａｔａｓｅｔｓ，ｗｅｃｏｍｐａｒｅｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｆｉ ｖｅｒｅｐｒｅｓｅｎｔａｔｉ ｖｅｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｐａｒｔｉ ｔｉｏｎｉ ｎｇａｌｇｏｒｉ ｔｈｍｓｉ ｎｐａｒｔｉ ｔｉ ｏｎｉ ｎｇｅｆｆｅｃｔｓ，ｑｕｅｒｙｐｒｏｃｅｓｓｉ ｎｇ，ａｎｄｇｒａｐｈｄａｔａｍｉ ｎｉ ｎｇ．Ｗｅａｎａｌ ｙｚｅｔｈｅｅｘｐｅｒｉ ｍｅｎｔａｌｒｅｓｕｌｔｓｉ ｎｄｅｔａｉｌ ａｎｄｄｒａｗｇｅｎｅｒａｌ ｃｏｎｃｌ ｕｓｉ ｏｎｓ，ａｎｄｅｘｔｅｎｄｔｈｅｍｔｏｔｈｅｒｅａｓｏｎｉ ｎｇｔａｓｋｓ． Ｔｈｅｐｅｒｆｏｒｍａｎｃｅｅｖａｌ ｕａｔｉｏｎｃｏｎｃｌ ｕｓｉ ｏｎｓｏｆｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｐａｒｔｉ ｔｉ ｏｎｉ ｎｇａｌｇｏｒｉ ｔｈｍｓａｒｅｏｂｔａｉ ｎｅｄｂａｓｅｄｏｎｔｈｅｓｅｅｘｐｅｒｉｍｅｎｔｓａｎｄａｎａｌ ｙｓｅｓ． Ｆｉ ｎａｌ ｌ ｙ，ｂａｓｅｄｏｎｔｈｅａｎａｌ ｙｓｉ ｓａｎｄｃｏｍｐａｒｉ ｓｏｎｏｆｅｘｉ ｓｔｉ ｎｇｍｅｔｈｏｄｓ，ｗｅｓｕｍｍａｒｉｚｅｔｈｅｍａｉ ｎｃｈａｌ ｌ ｅｎｇｅｓｉ ｎｔｈｅｃｕｒｒｅｎｔｒｅｓｅａｒｃｈｏｎｋｎｏｗｌ ｅｄｇｅｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉ ｎｇ，ｐｒｏｐｏｓｅｔｈｅｃｏｒｒｅｓｐｏｎｄｉ ｎｇｉｓｓｕｅｓｔｈａｔｃａｎｂｅｉ ｎｖｅｓｔｉｇａｔ ｅｄ，ａｎｄｌ ｏｏｋｆｏｒｗａｒｄｔｏｔｈｅｆｕｔｕｒｅｒｅｓｅａｒｃｈｄｉｒｅｃｔｉ ｏｎｓｏｎｔｈｉｓｔｏｐｉｃ．Ｋｅｙｗｏｒｄｓｋｎｏｗｌｅｄｇｅｇｒａｐｈ；ｇｒａｐｈｐａｒｔｉｔｉ ｏｎｉ ｎｇ；ｍｕｌ ｔｉ ｌｅｖｅｌｐａｒｔｉｔｉｏｎｉｎｇ；ｓｔｒｅａｍｉ ｎｇｐａｒｔｉ ｔｉ ｏｎｉ ｎｇ；ｄｉ ｓｔｒｉｂｕｔｉ ｏｎｉ 引 言近年来， 知识图谱得到了越来越多的关注和发展．知识图谱［１］最早由Ｇｏｏｇｌ ｅ 在２０１２ 年提出， 现如今规模已经达到百万顶点（ １〇６） 和上亿条边（ １〇８）， 常用的知识图谱有ＤＢｐｅｄｉａ？、ＹＡＧＯ［ ３］、Ｗｉ ｋｉ ｄａｔａ［ ４］、Ｆｒｅｅｂａｓｅ［５］以及中文百科知识图谱ＣＮＤＢｐｅｄｉａ［６］、Ｚｈｉ ｓｈｕ ｍｅ［ ７ ］等． 知识图谱数据模型基于图结构， 用顶点表示实体， 用边表示实体间的联系．由于同时包含了图的结构信息和属性信息， 知识图谱能够更好地表示现实生活中的复杂关系．知识图谱不仅需要根据实际情况随时更新数据， 还要进行存储、 查询、 推理、 挖掘等一系列操作．如今知识图谱的数据规模正在不断增大， 链接开放数据（ Ｌｉ ｎｋｅｄＯｐｅｎＤａｔａ）２０１９年３月发布的ＬＯＤ云图中有很多知识图谱数据集规模超过１０ 亿条三元组［ ８ ］． 以维基百科知识图谱ＤＢｐｅｄｍ为例， 它所包含的三元组数据已经超过了３０ 亿条． 由于知识图谱数据的急剧增长， 传统的集中式数据处理已经不能满足当前需求， 必须通过分布式集群来存储和处理大规模知识图谱数据． 知识图谱数据的分布式存储面临的第一个问题即是知识图谱划分． 这就使得如何划分大规模知识图谱， 同时满足跨分区边数目最小化且有效提高知识图谱查询处理性能成为迫切需要深人研究的课题．Ｉ 期 王義等； 知班真鬚刻分＿＊＿寒難 ２３ ７知识图瞥划分作为大规模知识圈谱分布式处理的首要工柞， 随着知识画谱数据规模及分布式处理需求的増长面險着新的挑战．一方面， 现有的知识图谱划分方法在大图上的划分效果并不理想， 时间复杂度较高， 特别是对于。包含数据量大且关系复杂的知识图ｍ产业界对于知识旣谱划分通常使用分布式处理框架， 需ｓ在集群上我到量佳的数据分布，》 然而高质量的划分必须同时满足负载平衡（ 在机器之间均匀地分配数据）和最小化切割边或顶点的数量（其顶点或边癘于不同的分区）， 这增加了机器之间的通信成本． 另一方面，＿前主要利用现有的图 分算法对知识？谱进＃划分， 然而这些算法忽略了＇知识＿谱的属性信息， 如何充分利用知识图谱数摒进行划分、如何制定统一的划分标准以及如何將划分与后续的查询处理相结合是当前研究的难点问題．知识图谱划分有着十分靈要的现实意义， 例如复杂网络《、 围像分割＿、 趙大规模集成电路设计 等． 在复杂网络方面＊最典型的就是社交网络分析ｍ＊每一个用户都是一个顶点＊ 可以稂据用户个人倩息以及用户之间的联系对其进行分类？ 更好地对易有相＿属性的甩户进行分析． 这同祥适用于道路交通网络？和生物网络Ｄ４］，道路交通网络讀裏构建＿来分析车辆轨迹和人的行动路线，．生物网络则通过图来表示蛋白质间的相互作甩以及基因序列． 图僳分割［１ ５ １梟图僳处理的重寒内容，它儒粟将像素分靡到相应对象中． 在图划分中， 每个顶蟲代个像素 象分割即对图中顶点．进行划分． 超大规樓集成电路（ＶＬＳＩ）设计是另一种常见的图划分皮用‘技米， 划分的目的是为了降低ＶＬＳＩ 设计的复杂性？Ｓ划分犛一个经典的ＮＰ难问题，？ｉｔ嘗恒定因子的近似算痛 ． 目前Ｅ有许多关于图划分＃法的研究， 但是现有的＇图划分算法综述都只養ｆ图论中的画Ｇ＝＜ｙ． Ｅ）， 并不包括知识图谱的相关内容， 知识＿谱划分算法的综述尚未发现？ 鉴于此， 本文主要对现有知识縛谱划分算法研究进行较为全面地综述， 襲体据架如茵１ 所示．分算法划分算法定界算法互ｌ算法及其衍生ｎ知识图划分算法Ｈ多级图划分基于匹配的算法基于聚合的算法ｊ 哈希算法及其衍生ｊ贪心算法及其衍生ＭＦｅｒｍｅｌ算法及其衍生＾其他类型图划芬＿标签传播算法基于查询负载的算法图１知识图谱划分算法框架图２ 按照时间顺序列出了本文所综述的主要算法． 从图中可以看出，ＫＬ算法是最早出现的图划分１． 基本图划分算法。谱二分银純］？ ｋｌ［４８］２．＿多级图划分算＾． 流式图划分算法． 分布式图划分算法ＳＲＣＢ＾３惯觀＃３２］Ｄ Ｍｉｌｌｅｒ ｅｔ ａｌ．［３４］ ？ 半定规划［ ４Ｓ］１妒３６］〇〇二賴划㈣Ｃｈａｎｅｔ ａｌ．［ ３０］ｏ〇线性规划［ 則ｍｒｓｂ［２９］〇〇ｍｅｌｏ［３１］ｌｉｎｇｅｔａｌ．［４６－４７］３ＳｃａｌａＰａｒｔ［３７］５． 其他类型图划分算法？ｍｒｓｂ［２９］□ ＭｅｔｉｓＰ＾□ ＰａｒＭｅｔｉｓ［ ７ＺｌＫａＳＰａｒ１ ５１１ □ＫａＰＰａ［５３］□ＫａＦＦＰａ［ ６２］□■ ＤＩＢＡＰｆ？１■Ｓａｆｒｏ ｅｔ ａｌ．ｌＺ｛■ ＰＤＩＢＡＰ１７１３□ＷＡＲＰ１６０３□ＥＡＧＲＥ［６１］？ＰａｒＭｅｔｉｓ［ ｒａ］ｒ ，ＡＧｒｉｄ［７Ｓ］哈希算法［７３］厶ａＨＤＲＦ［７７］贪心算银７６１ ａ▲Ｆｅｎｎｅｌ［７８］厶 ＬＤＧ＾ ７３】Ｇｉｎｇｅｒ？０］ ｉ３ｔｃｈ［８２］ ？｜？Ａｙｄｉｎｅｔ ａｌ．１１０１１ＪＡ－ＢＥ－ＪＡ－ＶＣ［ ８９］〇ＴＴ＾Ｐ１＾［９３１ｊａ－ｂｅ－ｊａ［８８］？〇ＫａＦＦＰａＥ［６３］ 〇？Ｉ〇ＧＰ［ＫａＰＰａ關〇Ｍｅｙｅｒｈｅｎｋｅ ｅｔ  ａｌ ．［８７］ 〇Ｕｇａｎｄｅｒ ｅｔａＬ［ １１３禁忌搜索［１ＣＰｅｎｇｅｔ ａｌ．［１１７］Ｘｕｅｔａｌ．［１０５］？ＷＡＲＰ嗍？今今ｘｄｇｐｃ１ １２］今Ｍｅｙｅｒｈｅｎｋｅ ｅｔ  ａｌ ．［ ８７］＾） 谱划分算法） 几何划分算法＆分支定界算法？ＫＬ算法及其衍生］ 基于匹配的算法■基于聚合的算法＼ 哈希算法及其衍生、贪心算法及其衍生‘Ｆｅｎｎｅｌ算法及其衍生＞ ＫａＰＰａ＃法及其衍生＞ＪＡ－ＢＥ－ＪＡ算法及其衍生丨－轻量级重划分算法，签传播算法—基于负载的算法ａ 其他算法１９７０１９８０１９９０ ２０００ ２０１０ ２０２０时间图２知识图谱划分算法时间轴２３８ 计 算机 学 报 ２０２１年算法， 随后出现的是谱划分算法， 之后很长一段时间内都是这两类算法， 直到２０ 世纪９０ 年代图划分算法的种类才逐渐增多， 有了几何划分算法和分支定界算法． 早期算法主要在单机环境下运行， 随着图数据规模的增大， 多级图划分算法逐渐兴起， 其将原始图粗糙化为较小图进行划分， 再将结果投射回原始图． 之后随着大规模知识图谱的出现， 多级算法也不能处理现有的大图， 人们开始思考如何将现有算法置于分布式环境下运行， 于是有了分布式图划分算法． 并且将动态图作为划分的输人图， 以适应现实中不断更新的数据． 近几年提出的流式图划分算法将顶点或边转化成流输人， 是另一种划分大规模图的思路．当前知识图谱得到广泛关注，一些专门针对ＲＤＦ图的划分算法开始出现， 例如基于查询负载的算法．相关工作． 文献［１７］对近年来出现的图划分算法进行了综述， 但是侧重于文献列举， 算法介绍较为简单， 本文不仅详细描述了各种算法， 还比文献［１７］多了流式图划分算法、标签传播算法和基于查询负载的算法等内容． 文献［１８］综述了以顶点为中心的分布式图计算框架， 关于图划分一节的介绍较为简单， 包含的算法类型并不全面． 文献［１９］着重分析了分布式框架下的图划分算法， 更侧重于不同框架的性能比较． 文献［２０］对已有多级图划分算法进行了综述． 文献［２１ ２２］从顶点划分和边划分两个方面综述了流式图划分算法． 文献［２３］综述了云计算环境下进行大规模图数据处理的关键问题， 从单指标和多指标两个方面分析了部分图划分算法． 本文详细介绍５ 种类型的知识图谱划分算法， 比上述文献更加综合全面．２ 预备知识知识图谱目前并没有一个统一的严格定义． 知识图谱是图Ｇ＝ｃｙ， Ｅ） 的某种扩展形式， 其中ｖ是顶点集合， 表示实体， Ｅ是边集合， 表示实体间的联系． 实际上， 知识图谱是图数据模型的继承和发展，其在一般图模型的顶点和边上附加更多的属性信息， 用于描述现实世界中事物的广泛联系． 知识图谱主要有以下４ 种类型， 分别是ＲＤＦ图、属性图、 异构信息网络和有向标签图． 有关知识图谱数据管理的详细内容可参见文献［２４］．ＲＤＦ图定义为ＲＤＦ三元组的有限集合． ＲＤＦ是万维网联盟制定的一种表示网络信息的标准， 通过资源、属性和值来描述特定信息． ＲＤＦ采用三元组０４，〇） 的形式， 其中ｓ４，〇 分别代表语义数据中的主语、谓语和宾语． ＲＤＦ 图的顶点集合是三元组中主语和宾语的集合， 边集合是谓语的集合． ＲＤＦ图的形式化定义如下．定义１．ＲＤＦ图． 设Ｕ、Ｂ和Ｌ为互不相交的无限集合， 分别代表ＵＲＩ、 空顶点（ ｂｌ ａｎｋｎｏｄｅ） 和字面量（ ｌｉｔ ｅｒａｌ ）．—个三元组〇，ｆ，〇）ｅ（ＵＵＢ）ＸＵＸ（ＵＵＢＵＬ） 称为ＲＤＦ三元组， 其中ｓ 是主语 是谓语，〇 是宾语． ＲＤＦ图Ｇ是二兀组（５，／＞，〇） 的有限集合．属性图是另一种常用的知识图谱数据模型． 与ＲＤＦ图相比， 属性图多了一个键值对来表示顶点或边的信息． 属性图的形式化定义如下．定义２． 属性图． 属性图Ｇ是四元组（Ｖ， Ｅ，Ａ ４）． 其中：（１） Ｖ是顶点的集合；（２） ＥＧＶＸＶ是有向边的集合， 如ｅ＝（ 巧， 巧）表亦ｅ 是从ｗ！ 到 的有向边；（ ３） 设 是标签集合， 函数Ａ ：（ＹＵＥ）—为顶点或边赋予标签， 如 Ａ（ ｗ）＝／ 表示顶点ｗ的标签是Ｚ；（ ４） 设 是属性集合， ＶａＺ 是值集合， 函数５：（ｙＵＥ）ＸＰｒｏｆ—ＶａＺ 为顶点或边关联属性， 如ｐ（ｚＰｒｏｐ，ａ（ｚＶａｌ，Ｓ（ｖ， ｐ）＝ａｖＰ的值是ａ．异构信息网络源自信息网络． 信息网络是指带有对象或链接类型映射的有向图， 如果信息网络中对象或链接的类型总数大于１， 则称为异构信息网络． 其形式化定义如下．定义３． 异构信息网络． 异构信息网络Ｇ由三元组（Ｖ， Ｅ，Ａ） 构成． 其中（ １） Ｖ是顶点的集合；（ ２） ＥＧＶＸＶ是有向边的集合；（３） 设Ｔ＿ｙ＃是类型集合， 函数Ａ ： （ＶＵＥ）—为顶点或边赋予类型， 如／ｅＴ＿ｙ＃， Ａ（ ＾）＝Ｚ表示顶点ｎ 的所属类型是有向标签图是在有向图Ｇ＝（ｙ， Ｅ） 的基础上为每个顶点添加了标签． 其形式化定义如下．定义４． 有向标签图． 有向标签图Ｇ由三元组（ｙ， Ｅ， Ｌ） 构成． 其中（ １） Ｖ是顶点的集合；（ ２） ＥＧＶＸＶ是有向边的集合；王義等； 知班真鬚刻分＿＊＿寒難 ２３ ９１ 期ＧＴ） Ｌ是顶点和边上标签的集．合．知识图键泛化、统一了各种图模猶镇枸， 知识图谱与各种图模型的关系如图３ 所示．．可以看出； 知识图谱扩麗了一般图模型， 通常意义上的图ａ包含顶点和边； 而知识圈谱增加了顶点和边的属性信息，不钽能够划分和存储， 还能进行查询、推理和挖掘等操作． 有向标签图是最简单的知识图谱模型＃ 真在一般图模型的基础上增加了标签集＃； 图中的任意顶点或边至■少关联一个标签，ＲＤＦ图可以看作是特殊的有向标签图， 其特殊之处在于一＋三元组中的谓语也可作为另一 ？个三元组的生语或宾语反映在有向标聲Ｈ中， 即边亦可作为顶点， 顶点与边交集非空．属＇性Ｈ在一般＿模型的基础上进衧扩展， 其增加了顶点癘性和边１ 属性的内置支持１ 目前被图数据库业羿广泛采用． 异构信息网络和有向标签图相似， 不同的是将标．签换成了所属类型， 且每个顶点或边可以有不止一个所貭类型？知识图谱＋顶点＋边＋划分（）＋存储（）＋查询〇ＲＤＦ图 属性图 异构信息网络 有向标签图＋主语十谓语＋宾语＋标签集合＋属性集合＋类型集合 ＋标签集合图３ 翱班． ＿遽翁务种＿虐知识图瞥与一般图模型相比含有更加丰竄的信息＞通常布一般图模型上的各种图划分算法也适用＇于知识厨谱． 为简便起见， 如无特别说明， 本文介绍＇的面划分算抜、均普遍适用于各类知识图谱的划分．限于篇幅． 这里以ＲＤＦＭ作为代表， 给 十知识图儀示倒， 如图■！ 所：示。定义５． 图划分． 给定＿Ｇ＝（Ｖ， ￡），图划分是将虜Ｇ划分成Ａ 部分， 每一部分用朽表示：？ 其中ｆｅ［１，々ｉ对于任意 ，有ｐ，ｎ巧＝０且ｕｈ只＝Ｇ．图划分需要满足式（ １） 或式（： 幻以实现负栽平衡，肩錄＿４、化跨趑分 Ｋ前諷倉或逾， 这两坝也是判断划分质量好坏的标准．？（１ ＆）／． ｉｓｉ［Ｖｉ｜＾，ｊｉ（＼－＼－〇）ｉｋｃｉ）姐（＇１— ｜ ｜ 拉丨 Ｓ ｎｌＸｌ＋ ＃ ）ｆｋ（２）其中４ＳＵ，１ ］是释动诨子，加和《分别代表虜的顶点数和边数，Ｉ Ｖ，｜ 和｜ ｜ 分鄉是：第１ 个分区的顶点数和边数？顧划分问道． 已難被证明是ＫＰ难间题１ ６］．＿翁人Ｍ陣时间＇突化时（例如增加或删＿一些顶点）， 划分可能会失． 去平衡， 因此对于动态图， 需要在划分前设定一个阈值，一旦失衡超过该阈值， 则会重新■进＇行： 划分．在图划分算法中：ｒ有两种切分方法＞一种是对顶点迸行划分， 另一神是对边进行划分， 圈ｓ 給岀了两种划分方法的示例？猶＇？ 两种划分方ｌｉ猶示例（？５璁虚划＃雜Ｉｔ点；｜ｒｊ分慧ｙ同分 ． 造腐通诞割＇； （ｂ＞进爾分将边刻分鑾幕同分区， 栽屬ＭＵ翁割＞２１０ 计導机攀报： ＿１苹在顶点划分中》可能存．在跨越分区的边（ 姐圈５（ａ） 中的边（ｓ％儀） 的两个顶点分别麇于不闻分＇区 ，更多的跨越边意味羞真大的通債开销， 因此顶点划分的主要优化目标是减少边切割？ 词样地， 边划分的主要优化目标是减少顶点切割．由于Ｂ有的图划分算法大部分是对图的顶点进行划分， 在本文中如无特别说明匣划分算法均采用顶点划分．表１ 给出了图划分算法中的一些常用符号．表１ 常用符号符号 描述Ｇ／Ｇ， 输入图／Ｇ的第ｉ 个子集Ｖ／Ｖ， Ｇ中顶点的集合／Ｖ的第ｉ 个子集Ｅ／Ｅ， Ｇ中边的集合／Ｅ的第ｉ 个子集Ｖ Ｇ的一个顶点？＾和％之间的边ｎ Ｇ的顶点数量ｍ Ｇ的边数量ｋ Ｇ的分区数Ｐ／尺 ？的 漏杳／（？ＳＩ擊个參ＫＰ（ｖ）＾所在的分区ＮＣｖ） 翁播邻顶点鑛合ｄｅｇ（ｖ） ＾的度数ｃｉｖ）＾的权重３ 基本图划分算法本节主：要包括苹期出现的较．为，经典的斑划分箅法 乎条件琅制， 这些算法通常作甩于小规模厨＊或者作为子程序应用ｆｉｉ复杂的虜划分方法． 这些算法大部分仅用于图的二分， 但胃以推广到＆个分Ｋ（例如通过递归： 过程夂３． １ 谱划分算法镩二分法是一种常用的图划分算法，－： 最．攀由Ｄｏｎａｔｈ等人［２ ５］和Ｆｉｅｄｌｅｒ［２ ６ ２ ７］提出， 它通过计箅图对龜的Ｌａｐｌ ａｅｅ 氣阵Ｌ的＿二小特貧餘＃征食量ｙ，即Ｆｉｅｄｌ ｅｒＪｔ［ 量来瑜定划费标准． 其：中Ｌ＝Ｄ Ａ，是图的度矩阵， Ａ是图的邻接矩阵． Ｌ二（／ｑ？ 的定义如下：１，如： 第＜ｉ罐（ｔ，，）ｉ 如果 ）胃１］通过确處．Ｖ的中隹＿£ 并且将小ｆ或： 等ｆ＇兩的顶点分配铪朽＊其余顶点分配给巧完成菌划分． 当分区数大于２ 时， 可递归地便用谱二分法（ＲＳＢ】ｔ２ Ｓ ］，直至达到划分目标．然而， ＲＳＢ的运行时间较长． 造成较高的成本．文献［２§］使滅多隹方裏乘快遽＿轉Ｆｉ ｅｄｌ ｅｒｌｔ＿黧法结构类似于第４节中介绍时多级图划分算法， 它先构造一系列较小的爾， 在粗糙化图上计算Ｆｉｅｄｌ ｅｒ阿董，再将向董逐步插值到吏裔级别的■中， 其间使用Ｒａｙｌ ｅｉｇｈ 商迭代进行局部改进？ 文献［ＳＯ－３１：！通过使用ＬｄｐＷｅ： 矩阵的多个特征＿羹將图轟接划分成多个部分， 进一步提高了效率．３． ２ 几何划分算法几何划分算法利用谏点的坐标債息对樹进行划分？ 坐标二分法ＤＳ２是其中最简单的算法？ 它基于以下假设： 除了顶点集： 合 （ 巧，％，…） 之外， 还審在可用于顶点的二维或兰潍坐 对于任意奶£Ｖ，， 存在； ＝． 雜雜： 标见． ＝（■ｓ之； 或三维坐标Ｉ？ ，＝，ｙ， ，氣夂然Ｓ＇逸择任意． 龜标方甸（： 例如ｙ＇方向）作为基准， 根据孩．点的ｙ坐标对所有顶ｉｔ进行排序＿ 将＿ｖＭ标较小的一半顶点分配给Ｐｉ， 其他顶点分配给朽＊再使用递归坐标二分法（ＲＣＢ） 即可对图迸行多路划分．坐：标二分藤的一个缺逼暴太依赖坐＝顧， 导款同一图在不同的坐标系中有眷完全不同的划分结巣．惯性划分［ ３ ２ ３ ３］的出现解决了这个问题， 它曹以看作是坐标二分法的改进， 但它投有利用： 坐标轴， 而＇是通过选择划分的基准线（或平冒．） Ｌ， 使得所■有顶点到Ｌ的乎方職最小化， 如画Ｓ 所示．（工６ ， ３〇Ａｐ，．文献［３４４５］提出 重叠图的概念， 其特殊类型包括平面图 近邻面和有限元相关？， 划分时需将Ｊ维顶． 点随机投巖至Ｊ＋１ 维球体，由逋过中心点的平茴进行二等分＊此外，述有将ｄ维顶点降低至一维空间进行划分的空间填充曲线法［３ ６ ３ ７ ］， 以及使用画嵌人将坐标赋營图进行划分的方法ｐｓ］．３． ３ 分支定界算法Ｎｆ难间题， 通常使用分支定界［３ ９］算： 法解决， 这对图划分同祥适用． 分支定界通过将赓始问题分成王義等； 知班真鬚刻分＿＊＿寒難 ２４１１ 期两个或多个子问題， 递归地进行求解， 从而找到最佳舊决＇方氣分支靈界树的＿个节處３＃座不同：的乎问题， 算法在原始问题的解决方案基础上保持上界ｔ；ｓＵ可以在算法改迸时更新． 要处理树中的节点， 需要在枏瘦子问题的解决．方案上计算下界Ｌ．？ 如果财剪掉节点， 否则继续分支． 创建两个或更多的子问題． 護个过程如獨７ 所： 本．在图划分问题中， 获得上赛和下界的方式有很多， 例如利用线性规划［ ４° ４２ ］ｖ丰定规戈１Ｐ１ ４３］、 二次规划ｄ叫等． 文就［４６—４７］采用组合的方法， 可似划分Ｓ大规辏的菌，首先假设Ａ和Ｂ是Ｖ的两个不相交．子集＊其他不： 在Ａ或Ｂ中的顶点属于未分配状态，对于Ａ可以扩展成的任意Ａ＋， 计算Ｂ和Ａ＋之间的最小边切割， 从而进行划体读方法可以划分具有上百万个顶点的图， 但其在大规模图上的运行时间较长．３． ４ＫＬ算法及其衍生上述算法都是宣接作用于． 原． 始圈进行划分． 除此之外述有 已划＃图的改进＿＿ｉ（ Ｋｅｒｎｉｇｂａｎ和Ｌｍ提出的ＫＬ算法［４Ｓ］通常被认为是第一个此娄图划分算法． ＫＬ算法从任意两个分区开始ｓ 通过交换顶点或顶点集来创建新的划分方案． 从菌改进初始划分方案？ 对新的划分方案重复该过程， 直到不能改进为止．假设Ａ和Ｂ是ｙ的两个初始分区， 顶点ｗ的增益办是将 从原有分区移至新分区后所减少的切割边数， 这里的＆可以是负数． 交縣Ｍ点《ｅＡ和＆ｅＢ的增益ｇ为私＋ｇ》一其中汛心用来判断顶虑《与６ 之间县否存在边＊定义如下ｓ极ｓ，＆）：（４）ｆ １？ 如果： （ａ，＆）否则谁择使备最大化的联處对ｔｅ，６ ？），一旦遽择ａ：和６， 之后交换不再考虑《或 依次选择现点对，Ｃ ｆｌ．２ ， ＳＧ？卜 ／２  ！，６卜 ／２ ！），找出能使ｆＣ＆，匕〉 逢： 太化的／ ， 交换■■處藥ｉａ． ｉ，ａ． ２，？ ？ｎｌ＇ｉ－１和汍么 ＫＬ算法童复以上过程，直到没有政進为止．爾Ｓ暴琪点交狹的一个例著，＿８ 顶歲丨 交雜示ＭｄＳＡ：ｔ＞２ 和顶轟％交换：后，摩音ＪＳ隹徽由ｉ感少筹３》ＫＬ： ＿法＇的—ｔ戴： 太ｌｉｔ迸蠢ＦＭｕｃ６ｉａ－Ｍａｔｔｉｉ６ｙｓ６ｓ（ＦＭ）彝法》９］？ＫＬ和ＦＭ之间的主要区， 别在于顶点移动的单位＿ ＫＬ一次交换一对顶点， 而ＦＭ—犹只移动一个顶点＊ 这使得ＦＭ比ＫＬ、效傘：更：禽且役有划分质量的损失．ＫＬ算法通常用于其他图划分着法的细化， 特别是在多鈒Ｍ划分莫法的反粗糙化阶段． 文献［５０］在ＫＬ萁法的基础上提出ＫＬ（ｌｉ算法和边界ＫＬ算：法ｆＢＫＬ），ＫＬ（ｌｉ算： 法只运行一次ＫＬ算：法， 不再进行迭代过裎；ＢＫＬＸ＃跨越分区的边所连接的Ｉ点集使用ＫＬ算法？ 在保证质量的同时减少了划分时间．ＫａＳＰａｒＭ考虑了高度Ｍ部化的ＦＭ算法， 仅从处于边界的未进行粗糙化的顶点开始搜索＿进一步痗高了划分效率．是对基本？划分算法的一个小结． 磨划分算法和分支定界算法虽然时间复杂度较高？但是有着良好的划分處義＊多适用于在单机上划分规模较小的‘相． 反：？ 几何划分＃法耗时较少． ． 划分质＃要差一些， 但可以贫展到分布式坏癘下， 从而划分大规ＩＩ图数据． ＫＬ算法及其改进算法通常与其他算法尤其：是第４ 节将介结的多级？划分算法相结合使用， 作为反粗糙化阶段的细化算法．２４２ 计 算 机 学报 ２０２１年表２ 基本图划分算法小结类型 优点 缺点 算法 描述谱划分算法引入Ｌａｐｌａｃｅ 矩阵的特征向量，在小规模图上划分质量较高时间复杂度较高， 不适用于大规模图的划分谱二分法［＿？７］ＲＳＢ［２ ８］ＭＲＳＢ［２ ９］ＭＥＬＯ［３１］利用Ｌａｐｌａｃｅ 矩阵的第二小特征值的特征向量（即Ｆｉｅｄｌｅｒ 向量）将图划分为两部分递归使用谱二分法， 直至达成目标在粗糙化图上计算Ｆｉｅｄｌｅｒ 向量， 再将其逐步插值回原始图使用Ｌａｐｌａｃｅ 矩阵的多个特征向量直接将图划分成多个部分几何划分算法能够充分利用顶点的坐标信息， 计算简单，可用于大规模图只考虑坐标而不是顶点间的联系， 导致跨越分区的边数较多ＲＣＢ［２ ８］惯性划分［３ ２＿３ ３］Ｍｉｌｌ ｅｒ等人［３４＿３５］ＩＳｐ［３ ６］ＳｃａｌａＰａｒｔ［ ３７ ］递归地根据顶点某一方向的坐标将顶点平均分成两部分使所有顶点到基准线（或平面） 的平方和最小化将＾维顶点投影至＾＋１ 维球体， 由通过中心点的平面进行划分将＾维顶点降低至一维空间， 利用Ｈｉｌｂｅｒｔ 曲线进行划分使用图嵌入将坐标赋予图， 再进行划分分支定界算法利用已有算法计算划分的上界和下界， 在小规模图上取得较好的划分质量计算较为复杂， 不适用于大规模图的划分线性规划［＾２］半定规划［４１＿４３］二次规划［４４＿４５］Ｄｅｌｌｉｎｇ等人［４“７ ］利用线性规划算法确定划分边界利用半定规划算法确定划分边界利用二次规划算法确定划分边界利用组合算法确定划分边界ＫＬ算法及其衍生算法计算较为简单， 可以只对图的局部顶点做交换而不用搜索整个图划分时间随迭代次数成正比ＫＬ［４８］ＦＭ［４９］ＢＫＬ［５ ０］在已有划分方案基础上交换不同分区的顶点或顶点集在已有划分方案基础上移动顶点到其他分区只对划分边界的顶点进行交换对于知识图谱而言， 使用義本图划分算法时＊蕾繫忽略厲暴和边的属性偉息， 将知识？谱当作无向图进行划分？由于基本图划分算法是在单机环墉下迸行的． 通常只猶划分具有上万个顶点和边的知识暖輿．． 不符合现实戀裏ｆ一般情況下不单独使用． 但是这些：算法的基本思想可以被利用并加以改进， 例如在多级图＇划分算法中将图粗槌化后的划分阶段，此时图的规模已足够小， 可直狻使用＇基本图划分馨法； 另一种情况是将这些箕法扩展到分布式坏境： 下从而进行大规模． 知识图鸯的划分■４ 多级图划分算法随着图数据规模的增长＊基本图划分算法？已经不能满足实际需要，于是产生了多级图划分算法ｔ５２］． 这类算法首先将图Ｇ粗糙化为只包含几百个顶点的摘荽Ｈ， 在这个小得多的＿上进行划分１然后将划分结臬投影回原始图？聱个过輕分为三个阶段： 粗糙化、初始划分和反粗糙化， 如图９ 所示．Ｗ８ 多象廣划；§＃＿： 示意粗糙化的主要目的． 是生成具有较少自由度的输人图， 这是逋过构造一系列具有萬小Ｍ寸的祖糙化图来实现的． 这一＃段逋常舊要收缩顶． 点集， 这意味着用粗糙化图中的单个顶点《代替原始图中的部分顶点， 假设Ｌ是ｖ中部分顶点的集合ｔ那么ｃ＜？．）＝乏＞（ｔｄ？收缩时苜能会产生平行边， 类似地， 甩单个边代眷这些边興輟重臀于乎仔边的杈重之和． 这禅使得粗糙化图中的划分 果能够反映原始图申的划分结藥？轉商已裘租槌化至足够小时【即可以使用基本图划分算法进行处埋时 停止粗糙化． 本文中提到的任何基本图划分算法ｉ只要可以处理顶点和边的权重． ． 皆胃甩于初始划分．一些代价较高的划分方法在粗糙化图上拥有较好的划分效果， 隹是不意味着在原始图上拥有同样的效果． 有些多级划分算法采用多种筒单方法的组合进行划分， 也可以获得很好？的划分效， 果［１ ７］＿皮粗槌化即将粗糙化图的划分逐步映射至原始图的划分． 由于原始图比粗糙化图具有更， 多的自由度， 粗糙化图的最隹划分不一定是原始图的最隹划分？ｐ此， 在反租槌化阶段请要利用一些．算法迸行细化（如ＫＬ算法夂反粗糙化和细化同时进行， 直至划分结果没有太太变化？多绞图划分算法的难点在于构濟租糙化图》划分和细化算法可＃见本文其他小节ｓ 本管：重点介缉粗糙化的两种类型以及对应的划分算法， 分别是基王義等； 知班真鬚刻分＿＊＿寒難Ｉ 期于匹配的算法和基于聚合的算法．４．１ 基于匹配的算法最常见的粗糙化方法是通过最大匹Ｅ得到的．给定图Ｇ， 匹？ＭＧＥ是一组边集集脅中任意厕条边不存在公共顶点＊量大Ｉ 匹配是指包含最：多数量的边的匹配． 在粗糙化阶段， 匹配中弯条边连接的顶点都用单个顶点代替？ 图１０是ＥＳ配的一个例子， 其中Ｍ＝？４ｔｅｃｓＭ）－Ｃ＾＇３■ｍＪ ｝■Ｓｆｉｌ 祖糙化价段的匹？示例一－个紆的Ｋ酿獻徽包费＃可能多前核寘霄的边， 但同时也希望顶点权重保持平衡［５ ３］． 针对这个问题：？ 文献［〇］使用评级函数ｆ 对边的权重和均匀性之间的迸行权衡，假设＿（：？０代毫斑》 的＇杈３８署代表顶点《的权重， 文献［５３］经实骏验证， 最优评级： 函數为ｆ｛ｔｉ？£）Ｗｉｔｌ ＇ Ｖ）ｃｉｕ＾ｃＣｖ）（５）使用深度优先算法或随机算法可以快速获得最大匹節， 文献［５〇］进一步提出Ｔ重边ｔｅＥ、轻边匹Ｅ和重面匹． 配等启发式算法． 其中重边匹配在文献［５０］中被怔明划分效果最好， 它以随机顺、 序访问■顶点， 优先选择连接顶点的权重最离的未匹配边添加到匹首己．有一些接近钱性时间的算法寄要较大开销， 但是可以．获得吏好的虜量保证，例如贪心算法［ ５ ４］、 路径增长：算法（ＰＧＡ）［５ ５］以及结含贪心算法和ＰＯＡ的全局路径算法（ ＧＰ Ａ）［ ５ ６ ］．贪心算法的思想非常简？藤重賛： ．地将＿曹麗？中索匹祗的权童優高的边添加到？配中，直到没有可＇选择的边． ＰＧＡ需要构建一组顶点不枏交路径， 每条路径从任意顶点开始，将与当前顶点《梱邻的未租糙化顶点〃的权麓最大的边ｅ＝（ｖ． ？）添加到路径中》 并删除与ｗ相邻的所有边？ 如果灣前路径无法扩展， ＰＧＡ将开始构建新的路径、罝萬没有剩佘边＾在增长路径的同財， 选择成为路径的边将交替地添加到匹配Ｍｌ 和Ｍｚ 中；最终返回二者中的较大僮．． ＧＰＡ在上述两种算法的基础上， 按照权重降低的顺序扫描边， 构建路径的集合ＥＶ然后使用动态规划算法为这些路径计算最大权重匹配？在第一轮ＧＰＡ完成启３賞在剩余边上运行第二轮ＧＰＡ， 多数情况下在第二轮过后己經． 没有剩佘边，］？Ｍ ＥＴＩ Ｓ＾７ ５ Ｓ ］是最常见的多缘图划分箕法， 它在：粗糖化阶段选择重边匹配， 在划分和细化时使用ＫＬ算法， 文献［ＳＣｆｒ次将ＭＥＴＩＳ作用于ＲＤＦ图．．ＷＡＲＰ［６ °］进一步扩麗了这种方法， 它将图划分与跨分区的三元簞查询负载感知复制相绪合，， 并通过匹前查询模式扩璩片段＊实规高效的查询处理．ＥＡＧＲＥ［ ６ １３通过在ＲＤＦ数据中使用实体概念来粗糙化ＲＤＦ图？ 通过对同一类时实体进行分组， 可以＿少ＲＤＦ的查询时间．ＫａＰＰａＭ罩一神基于ＧＰＡ匹配的分布式多级图划分算法》＾ 其分Ｋ数量露麥等于所便用的处理器的数量＿ＫａＰＰａ 以及其改进算法ＫａＦＦＰａ［＠？ＫａＦＦＰ：ａＥ［ ６ ３：ｒ雜寒１令轉细介绍？ 此外， ＫａＳＦ：ａｒ［ ５ １ ］是一个塞于极限思想的图划分算法ｓ 它仅收缩两个级别之间的单条边， 使得不同级别的图只有少量；变化，从而保证划分质量．４． ２ 基于聚合的算法除了基于匹袍的算法， 另一种常见的粗糙化方法是基于权重聚合的方法＆４６ ６ ］． 这种方法源自代数多重网格法（ａｍｇｊ￡６ ７１在扠露聚合中， 每个顶点窗以分屬木同的聚合． 祖糙化阶段包食三个步骤： 首先选择？的部？分顶点作为聚合的种子； 然后确： 定计算规则， 可得到属于每个聚合的非种子顶点的权重后计算租糙化顶虑之间的连接强度．权重聚食首先选择一组顶点Ｃ匚Ｖ， 使得Ｆ二Ｖ／Ｃ中的所有其他顶点强耦合到Ｃ． 从 ０和Ｆ＝Ｖ开始， 将顶点从Ｆ转移到Ｃ直至剩佘＊？£Ｆ＿足２Ｍｉ｝＜ｓ＆ｒｓ）ｊｅｃ，６Ｖ－＃是■脅参歡（逋攀＠知〇－５１对于ｉｅｆ， 定义ｔ： 中？ 的粗槌化邻域 ． 设是图中的神子＿／ 的相邻顶点在ｉｆｅ糙化图中的聚合序号， 绖典的ＡＭＧ矩阵Ｋ大小为｜Ｖ｜ ／｜Ｃ｜ ） 的定义如下：Ｗｉｉ ／＾Ｐｊ Ｗ，ｋｅＮ｛如果如果？＇ｅｃ＾＝ｉ否则Ｐ叫， 代表Ｉ屬于第Ｋ：／） 聚合的可能性． 第ｐ个聚合的大小 ｆ 蓬接两个聚合Ｐ和 的边、的权｝重为ｋｐ＾ｋｌＰ ｌｑ－ｋ參ｌ加权聚合可能导致更密集的粗糙化图， 所以養要谨慎选择ＡＭＧ方法，同时保证负载均衡？ 文献［２０］使用代数距离［ ６ Ｓ］作为顶点之间连通性的度量，以２１４ 计導机攀报： ＿１苹获得高质量且负载均衡的划分鍺果． 文敝ｎｓ？］提出了一个祖糙化框架＊， 真目标是保留图的谱特征，使用随机游走推导祖糙化的待征向量， 但痊代价非常高． Ｄ１ＢＡＰＷ和ＰＤＩＢＡＰ［ ｎ］在细化阶段使用棊于扩散的算法＊ 能够提升划分质量并且更努地弁行化＿表Ｓ给出了多级？划分算法的小结？ 基千ＥＥ的算法因其时间复杂度较小更：为常见ｓ 其中ＭＥＴＩＳ以提出时间早、 速度快、质量高等原因通常？作为其他算法的比较标准？然而， ＭＥＴＩＳ无法倉接应用到， 大规隹厨数据上， 后续算法主荽围绕如何实现更大规模图数据的划分以及如何在分布式条件下进行划分这两个方询发展．目前产业界常用时知识图谱（如ＤＢｐｅｄｉａ）在划分时都采用ＭＥＴＩＳ算法的主寒思想，常见做法是将ＭＥＴＩＳ算法集成至分布式系统中以便在不同机器上存储大规模数据．表３ 多级图划分算法小结类型 优点 缺点 算法 描述ＭＥＴＩＳ［ ５７－５８ ］粗糙化阶段使用匹配算法收缩边， 细化阶段使用ＫＬ改进算法基于匹配的算法每一级别的顶点只能粗糙化到下一级别的一个顶点上， 计算较为简单时间复杂度与粗糙化的级别有关和图的规模有关， 单机情况下只能划分小规模图ＷＡＲＰ［６ ０ ］ＫａＰＰａ［５ ３］将ＭＥＴＩＳ算法应用于ＲＤＦ图， 并通过匹配查询模式进行扩展粗糙化阶段使用ＧＰＡ算法计算匹配， 并且使用ＦＭ算法进行细化ＫａＦＦＰａ［６ ２］ＫａＳＰａｒ［ ５１ ］在ＫａＰＰａ 的基础上，在粗糙化和反粗糙化阶段进行迭代粗糙化阶段每级仅收缩单条边，细化阶段使用ＦＭ算法基于聚合的算法引入ＡＭＧ算法计算顶点分数， 划分质量较高计算较为复杂， 单个顶点可粗糙化至下一级的多个顶点， 易导致更密集的粗糙化图Ｓａｆｒｏ等人［２ ０］ＤＩＢＡＰ［７ ０］粗糙化阶段使用ＡＭＧ算法， 并以代数距离作为顶点连通性的度量粗糙化阶段使用ＡＭＧ算法， 细化阶段使用基于扩散的算法进行改进同基本酉划分算法相似， 多级厨刘分． 算法不考虑知＇识图濟的属性倩息》 将知识图谱当作无向图粗糙化后进行划分． 不同之处在于多辍Ｍ划分算法对划分包含数十万个顶点和上百方条边的知识掲谱，适用范围要比基本？划分算法更广？ 但它仍属于单机环境下的划分算法， ＿要与第６ 节的分布式图划分寘法结合才能划分大规擦知识＿谱．》 其中的典型雾禱梟ＭＥＴＩＳ的并行版本ｐａｒＭＯＳｆ７ ２１．５ 流式图划分算法流式圈划分算法１：７ ３ １舞近年来提出的一种圃划分方法， 流式图划分的目的是为了对太规模流式Ｗ数据进行高效率划分． 流式图划分箕祛将图加载为包含顶点或边的序列， 再将每个元素分配． 到对应的分区， 整个过程如图１１ 所；ｇｔ．（＇顶点流 ？ｐ１〇ｎ〇巧〇巧〇＆４〇 ％〇吒＂ ＂，图ｉｉ 德式勝划： ｆｌ＃？酱德雜素：： 意麗５． １Ｈａｓｈ 算法及其衍生．流式图划分算法中，最筒单的是Ｈａｓｈ箕法，它通过构逢棊于散列的映射函数紅； 科一柯进行划分， 菌数Ａ的输人可以是顶点或边的编号．以边为例， 边 Ｃ坊，ｖｌｆｊ）： 的分区为Ｐ（ｅ）＝ｍｏｔＫｆｅ：） ． 这种皂发式算法通ｆ会造成大量ｆｔ顶点切割， 虽然时间开销较少但往往木能获得较禽的图划分质量－是对Ｈａｓｈ算法的一种改进， 它是一种边划分算法， 主要思想是优先切割更裔度数的顶点． 在ＤＢＨ算法中， ４（ｅ）的歲义如下：（， 如果》ｈ｛ｅｊＩＢ）ｕ（〇， 否则ＧｉｒｅＰ５ ］同样是边划分箕法， 在Ｈａｓｈ算法的塞础上，ｉ＃加了对分区的约東：（： 幻Ｐ （％） 且ｐ （，） ｇｔｒｓ）＼ｐ（ｖ，）＼ ＝Ｉｐｃ－Ｐｉ）！．Ｇｒｉｄ通过构造矩阵ＸＸＹ使＃ＸＹ＝ｈ： 真中是是分区数． 每一个元素代表？一个分私＇再将顶点＾通过雇数／！ 映射至矩阵中对应的分ｇ编号， 计算与＊所属分区同在一行或一列的分区编号集合ｓ 这种方式保怔了每对顶点计算启的交寒都有两个分Ｋ， 之后再选择负载较小的分区作为该对顶点对应边的最终分区 Ｇｉｒｄ蕾粟随时维护分区分配以计隹负载最小的Ｈ王 鑫等： 知识图谱划分算法研究综述 ２４５１ 期５． ２ 贪心算法及其衍生贪心算法［ ７ ６ ］是一种基于规则的流式图划分算法， 属于边划分算法， 对于给定边 ｅ 的顶点它遵循的规则如下：ａ） 如果ｐｕ）ｎｐ（巧） 乒０， 则将ｅ 划分至ｐｏ，）ｎｆ＊（巧） 的最小负载分区中；（２） 如果尸（功川尸（巧）＝０且 （巧） 乒０， 则将ｅ 划分至Ｐ（Ａ）Ｕ） 的最小负载分区中；（３） 如果Ｐｆｅ） 乒０且Ｐ（％）＝０， 则将ｅ 划分至Ｐ（ Ａ） 的最小负载分区中；（４） 如果Ｐ（Ｗ！）＝０且Ｐ（巧）＝０， 则将ｅ 划分至现有的最小负载分区中．ＬＤＧ［７ ３］在贪心算法的基础上， 增加了分区的负载限制． ＨＤＲＦ［ ７ ７ ］是对贪心算法的一种改进， 类似于ＤＢＨ， 将度数纳人考虑范围， 优先对度数较高的顶点进行划分．对于给定边 巧） ， ＨＤＲＦ定义分区巧为ＣＩＩＤＲＦＵ，巧， Ｚ） 的最大值：ｄ（． ｖｔ ）ｇ（ｖ， 〇ｄｅｇ（ Ｖｊ ）ｌｄ（ｖ｝）（９）ｄｅｇ（ ｖｔ ）＋ｄｅｇ（ Ｖｊ）ｐ＋（ｉ沢？） ） ， 如果ｚ ｅｐ（？）ｉ〇 ，否厕Ｊｃｉ ｉｄｒｆｕ，， ｚ）＝ａ ｘｍａｘｓｔｚｅ ＾１（ １０）＋ｅ＼ ｍａｘｓｔｚｅ ｍｔｎｓｔｚｅｇ（ ｖｔ＾ｙ ＋ｇｉ ｖ，， ／＞（ ｉｄ其中， ＴＯａｍｉｚｅ 和ＴＯｉｗＷｚｅ 分别是具有最大负载和最小负载的分区的大小．当Ａ ＜１ 时， 该方法与贪心算法相似， 可能会造成分区不平衡． 为了解决这个问题， 通常设置Ａ＞１． 如果Ａ—００， 该方法将趋近于随机划分．Ｈ ＤＲＦ可以在处理输人流的同时维护度信息并对其进行更新， 而不是在分区之前预先计算度， 适用于动态图的划分．５． ３Ｆｅｎｎｅｌ 算法及其衍生Ｆｅｎｎｅｌ［ ７ ８ ］是另一种常见的流式图划分算法， 它的核心思想是最大化相邻顶点和最小化不相邻顶点． Ｆｅｎｎｅｌ 与ＬＤＧ相似， 都需要计算相邻顶点数，不同的是Ｆｅｎｎｅｌ 需要根据每个分区的负载限制设置最大分配顶点数的阈值． 对于负载低于阈值并且输人顶点被分配给具有最大分数的分区， 计算分数８ｇ（ ｖ， Ｐｔ ）．ｄｇ（ｖ， Ｐｔ ）＝＼Ｐｔｆ］ Ｎ（ｖ）｜ ？ｙ｜Ｐ，Ｉ７１（ １２）其中， 参数《 和ｙ 是可调的， 顶点所在的分区为ａｒｇｍａｘＯｇ〇，） ｝． 此外， 文献［７９］ 提出了基于Ｆｅｎｎｅｌ 的再划分方法ｒｅ Ｆｅｎｎｅｌ， 这是一种迭代算法， 通过利用先前的划分结果来提高图的划分质量，实验表明其效果可与ＭＥＴＩＳ算法相当．受到Ｆｅｎｎｅｌ 算法的启发， 文献［８０］提出了一种名为Ｇｍｇｅｒ 的算法． 它对较低度数的顶点使用类Ｆｅｎｎｅｌ 算法对顶点及其人边进行划分， 与Ｆｅｎｎｅｌ 不同的是， Ｇｉ ｎｇｅｒ 的目标函数同时考虑了顶点和边．而对度数较高的顶点， Ｇｉ ｎｇｅｒ 使用Ｈａｓｈ 算法对顶点的人边进行划分．然而， Ｆｅｎｎｅｌ 算法在计算时要提前获知顶点数？和边数ｍ， 这使得其在执行划分时需要保持输人图不变， 不适用于动态图的划分．表４ 给出了流式图划分算法的小结， 其他相关细节以及实验结果比较可参见文献［２１ ２２］． 其中文献［２２］是流式图划分算法的最新实验性分析结果，通过大量比较实验得出以下结论： Ｈａｓｈ 算法是简单但有效的一种方法， 尤其是在降低延迟方面；Ｆｅｎｎｅｌ 算法更适用于对度数较低的图进行划分， 例如道路交通网络； Ｇｍｇｅｒ算法在像社交网络这样具有长尾分布的图上更加有效； 对于幂率图而言，ＨＤＲＦ则是最佳算法， 因为其较低的顶点切割和均衡的负载可以使图划分获得最佳性能．表４ 流式图划分算法小结类型 优点 缺点 算法 描述Ｈａｓｈ算法及其衍生计算简单， 时间复杂度低， 可以在划分过程中随时对图进行更新初始随机划分， 导致跨越分区的顶点数较多，划分质量较差Ｈａｓｈ算法［７３］ＤＢＩ Ｉ［７４ ］Ｇｒｉｄ［７５］对顶点或边随机选择分区在Ｈａｓｈ算法的基础上， 优先对有更髙度数的顶点进行切割通过构造矩阵得到两个候选分区， 再选择负载较小的分区贪心算法及其衍生适用于动态图的划分， 对幂率图的划分效果明显贪心算法划分质量较差； 改进后的Ｉ ＩＤＲＦ时间复杂度较髙贪心算法［７６ ］Ｉ ＩＤＲＦ［７７］基于特定规则选择负载较小的分区在贪心算法的基础上， 优先对有更髙度数的顶点进行切割Ｆｅｎｎｅｌ 算法及其衍生同时考虑相邻顶点数和非相邻顶点数， 划分质量较髙计算较为复杂； 需要提前获知顶点数和边数，不适用于动态图的划分Ｆｅｎｎｅｌ［７８ ］Ｇｉｎｇｅｒ［８０］在最大化相邻顶点和最小化不相邻顶点之间进行插值低度数顶点使用类Ｆｅｎｎｅｌ 算法， 髙度数顶点使用Ｈａｓｈ算法ｍａ 计導机攀报： ＿１苹与之前的图划分算法不苘， 流式圈划分算法在划分时需荽将知识慰谱加载为包含顶点或边的序列， 在整个过程中只需一次图遍历， 而不最将菌载入后进行多次迭代计算， 所以能够作用Ｔ隹含上亿个顶彘和边的知识图谱，符合大规模知识图谱的划分寒求？６ 分布式图划分算法随着？数据规模的不断增大， 如何在分布式环攙下实现图划分算法已成为必餘謙求． 梟常见的方法是开发＆有Ｍ划分算法的并行版本， 例如， ＭＥＴＩＳ算法的并行版本Ｐ紅ＭＥＴＩＳ域、Ｓｃｏｔｃｈ算法Ｍ的并行版本ＰＴＳｃｏｔｃｈＥＳ ２ ］． 这两种都是墨于递归二分法的算法， 它们比直接６ 分区算法更难乎并行化》 ＠为在最初的两个分区中，可用的‘并行性较少？ 这两种算法属于早期分布式图划分算法：， 本节将去費介绍最近？＿ 出的几种典型分布式图划分算法．６． １ＫａＰＰａ算法及其衍生Ｈｏｌ ｔｇｒｅ观等人Ｍ提出了一种分布式多级图划分寘法ＫａＰＰａ． 该寘法在粗糙化阶段使用文献［Ｓ３］提供的分布式匹配算法， 并且便用ＦＭ算法进行细化， 使用邻接矩阵存储顶点＿边的权重， 使用Ｈａｓｈ表存储迁移的顶点和对应的边． 隹迸行局部改进算法之前； 誓粟在每个分区的边界执行广度优先搜索生成顶． 点盡细化操作将在这些顶． 点盡之间进行．ＫａＦＦＰａ［ ６ ２３＃ＫａＰＰａ齒基撤Ｌｂ不考．虑并行化，而是专洼于大规模酉的划分， 扩雇了． 文敵［射－８５］引入的多级送代算法＊真主鼕思想是在祖糙化和反粗糙化阶段进行迭代，一旦围被划分， 两个分区之． 间的边就不会收缩， 这样可以确保分区赓量＊ 传统的多缴划分算法Ｈ执行一次粗槌化和反粗糙化， 也被称作Ｖ循环《２］？ＫａＦＦＰａ提出了两种新的全鳥搜索方法，分别是Ｗ搪坏和Ｆ循环． Ｗ掮环的工作谭理如下：在每个级别上使用不苘的随机种子进行两次独立的粗槌化和反粗糙化， 从而得到更好的划分鍺果． Ｆ循环类似于Ｗ循环， 区别在于？每一级上最多执行两次递归调用． 不同循环的例子见菌１２．＿Ｉｔ 从左到右依歡： ■參談： 划： 量攀緣＿Ｖ癖珲 蕭环翁Ｆ攝砰ＫａＦＦＰａＥ１６ ３］是ＫａＦＦＰａ的进化：算翁：Ｃ：ＥＡ．！（版．本， 从图的初始划分开始， 以边切割数作为划分标准， 爵过多轮选择后ｒ每出綦优划分结果．为了避免陷人， 局部最优， 引人变异算子以减缓算法收敛．ＫａＦＦＰａＥ定义了两个变异算子风和恥， 它们随机作用Ｔ不同顶点， 均执行尸游坏．ＫａＦＦＰａＥ的弁行化过程如下： 首先需要估计＿的分ｇ数Ｓ， 每个处理单元执行划分步骤并测量划分时间／， 再选择Ｓ使得创建Ｓ个分区的时间约为ｋｌａｌ／／， 其中／，暴调整参数． 而＾， 是图划分的总运行时间？＿？个处理傘元多次调用：ＫａＦＦＰａ创：建Ｓ个分Ｋ， 并以一定概率插人变异算子＊＾ 只蘩有时间剩？， 算法就錢猶坏进行．文乘［８６］改进了ＫａＦＦＰａＥ， 能够实现完全平衡的划分？ 文献［８７：！将ＫａＦＦＰａＥ与第７ 节的标签传播算法结含， 得到Ｔ更高质黧；的图划分效果４６． ２ＪＡ－ＢＥ－ＪＡ算法及其衍生Ｒａｈｉ ｍｉａｎ等人ｔｓ ｓ］提出了名为ＪＡ－ＢＥＪＡ的分布式图划分算法， 该算： 法使用局部搜索和模拟退火技术进行Ｓ划分． ＪＡ－ＢＥ－ＪＡ算法首先随机均匀地为每个厲点分配一种颜色 指顶点Ｐ 的颜色， 具有相同顏色的顶点屬于Ｍ—分区．？将ＪＶ？（ｃ＞定义为具有颜色。的ｐ的银居集合． 顶点ｆｔ的邻居敷用Ａ表示， ４（ｃ）＝｜ ＮＪｃ）｜ 是具有颜色ｃ 的ｐ的邻居数． 图的賺量定义为具有不同颜色的顶点■ 之间的边数， 因此， 顶总的能羹是其具有不同颜色的邻居的数羞， 并且图的能． 量是顶点的龍量的总和：Ｅ（ｍ＾＼＾］（Ａ－ｄｖ（ｎ〇＇）Ｃ１Ｓ１然后将相邻顶点和随机顶点集作．为候选萬点进行搜索， 如果交换顶点颜色后图的能量降低， 则进行交换， 当搜索不到可交换颜色的顶点时． 算法终止？图１３ｆ和《？ 交换前， 与ｆ颜色相同的邻居数为１， 与《？ 颜色相同的邻居数为０４和《？ 交换后， 与ｆ颜色相同的邻居数为３ ， 与《？ 颜色相同的邻居数为１， ３＋１＞１＋０，交换后图的能量更高交换过程如图１３ 所示．王義等； 知班真鬚刻分＿＊＿寒難 ２４７１ 期（兩°４（）°＋ ＜＾（％）°（１４）其中， 《？是能鼋函数的参数． 利用模拟退火技术防止陷入局部最优， 引入温度：Ｔ并让它随时间减少， 类似于冷却过程ｆＴ降为１ 时不再下降．ＪＡ－ＢＥＪＡＶＧｔｓ］是ＪＡ－ＢＥＪＡ的一个变体真棊于边划分而不是顼点划分． 该算法首先将一组边随机划．分遵不同的分鼠同时允许顶点被复制到多个分Ｅ中． 然斿定义每个边和匐个分区的能量函数，根摒系统能量判断是香交换边， 诙算法通过应甩鳥部搜索：算法迭代地改进初始划分．６． ３ 轻量级重划分算法为了适应动态图的计算， 需＊根据输人图的更新倩息在已有划分基础上再次划分， 这个过程称为ａ；划分［９ °］ ｍ菜重划分箅法仅依赖于薺重新划分的图中的少量信息， 则称其为轻量级重划分算法． 当新顶点加人眉或图的权．重发生变化时， 较董级重划分将被触发．同时通过迭代过程减少边切割， 适用： 于动态靡的划分， 该算法利用奉合顶京权重倉息作为其辅助数据４目比ｆ图的结构倩息》 该数据要小得多．假设＠是分區叉中的顶点， 增益 是将 从＆移至＆所减少的边切割数＊ 增益可以是负值． 在每次迭代中定义两个阶段＊ 第一阶段仅允许从具嘗较低编号到较离编号的分区移动顶＊ｓ 而第二：阶段仅允许在相友方向上慈动顶点． 如果孩点对以移动至多个分区， 则选择增益最大的分Ｋ，当某分區权重超过负载时， 不＊向该分区迁移顶点＞当投有孩点需蘩移动时， 算法緒東■ ？ 整个过程如图１４Ｐ３：ｗ＝３，ｅｃ＝３Ｐ３：Ｚ￡ｆ＝４ｆｅｃ＝３Ｐ３：ｅｃ＝２图ｗ左图食韧龄划 国， 灼，， Ａ代表分区 代表衩歡—代看遠：傷割数， 灰色■默＃羞忝请霱要移动至编号更高的分区中（即队＾到．ｆｔ虐 中＿图ｉｔ： 灰色麗虚＿＃＿奮細餘分区中（即孤朽到ｆｔ＞ｒｌｆ倒焉舊義鐵家財的划分圏文就［ ａｉ］提出一种将轻量级重划分集成到Ｈｅｒｍｅｓ 寒＿中的方法！ｓ：雜轉霄嵌人至Ｎｅｏ４ｊｇｆ数擦库［ ９ ２ ］， 以支持在分布式环境下进行图划分． 文献［９３］将划分分为两个阶段， 逻辑顶点迁移和物理顶点迁移， 在降低通信成本的同时能够更好地豳甩于现实中的大规模西数据．表５ 给出了上述几种分布式图划分算法的小结．划分日寸通常会使用分布式Ｈ处理框架Ｍａｐ＇Ｒｅｄｗｒｆ９４］，通过引入编程樓望来促进高效分布式算法执行， 同时抽象出底屠细节－除此之外， 常用的分布式图处理権架遂有Ｐｒｅｇｅｌ［ ９ ５ ］、ＧｒａｐｌｉＸｒｓ ６ ］、 ＰｃｒｗｅｒＬｙｘａ＾。］等，其划分质量与所使用的划分算法有关， 具体细节及相关比较可参见文就Ｄ９］． 近年来出现的质量鉸高翁分■布式菌划分算法还： 有ｆｔ： Ｈａ４〇ｅｐＳｐａｒｋ馨梦ｆ式猶樂上Ｍ行的ＤＦＥＰ７１和Ｄｙｎａｍｉ ｃＤＦＥＰ１９＇增纛在栽菌划分箅法Ｉ〇ＧＰ［ ９ ９ ］、 将图转化成树的表５ 分布式图划分算法小结类型 优点 缺点 算法 描述ＫａＰＰａ算法及其衍生引入分布式匹配算法， 使得多级算法能够划分大规模图需要提前存储顶点和边， 不适用于动态图的划分ＫａＰＰａ［５ ３］ＫａＦＦＰａＥ［６ ３］Ｍｅｙｅｒｈｅｎｋｅ等人［Ｓ ７］粗糙化阶段使用ＧＰＡ算法计算匹配， 并且使用ＦＭ算法进行细化在ＫａＰＰａ 的基础上， 在粗糙化和反粗糙化阶段进行Ｆ循环将标签传播算法与ＫａＦＦＰａＥ相结合ＪＡ－ＢＥ－ＪＡ算法及其衍生计算简单， 局部性强， 且能避免陷入局部最优运行时间与迭代次数呈正相关， 不适用于动态图的划分ＪＡ－ＢＥ－ＪＡ［８８］ＪＡ－ＢＥ－ＪＡ－ＶＣ［８ ９］为每个顶点随机分配颜色， 定义顶点能量， 通过交换顶点减少图的总能量为每个顶点随机分配颜色， 定义边的能量， 通过交换边减少图的总能量轻量级重划分 搜專较小， 可纏 运行时间与迭代次Ｉ Ｉｅｒｍｅｓ［９ １］按照指定顺序迁移顶点， 并将其集成到Ｉ ｌｅｍｉ ｅｓ系统中算法 时更新顶点 数呈正相关Ｐｌａｎａｒ［９ ３ ］将轻量级重划分分为逻辑顶点迁移和物理顶点迁移两个阶段２１８ 计導机攀报： ＿１苹Ｓｌｉｅｄｐ算法［１°°］、基于线形嵌人的划分算法［ ―以及基于定？边交换的分布， 式在线太图划分算铉［１°２ ］．可以看出； 分布式图划分算法从原来的研发已有算：法的并行版本遂渐演变为直接在分布式环境下提出新算法． 输入图也不局限于＇静态图， 而增加了结合实际需要随时可更新数据的动态图．分布式图划分箅法可用于具有上亿个顶点和边－的大规模图数据的划分， 是目前进行大规模真拿知识图谱划分的主锍算法＊ 但现有太部分分布式图划分算法不能充分利用知识鮮磨的丰富属性信息．７ 其他类型图划分算法除了上述４ 种类．型的图划分算法外， 还有一些其他类塑的算法有参较野的图划分敏果， 例如， 基乎遗传／进化算法进行图划分 基于截忌搜索的顶点交换方法［１°４］、■于痦义的ＲＤＦ图划分箅法？５］、ＢＳＰ模型的大图划分算法 以及动态平衡图划分算法［ １ °ｓ ］． 限于篇幅， 本节对其中两种當用的算法类虚进行介＿－７．１ 标签传播算法标签传播算法（ＬＰ Ａ：） ［１ °９］首先为每斗顶点随机均匀分配一个标签， 然后迭代地更新顶启： 标签． 在每次迭代中， 顶点将其相邻顶点， 中数量最多的标签作为自己的标甚 签不再軍攻时＊ 读过程终止； 具有相同标签的顶点属于同一分区？ 标签传＃算法中顶点更新的过程如图１５ 所示．隱：１５ 标雜＿卿臟Ｓ麗澈自身健但ＸＰＡ无法保证分区大小平衡， 文献［１１０］通过提供箱确约束， 即给定分区顶点数羞的上限和下Ｐ良以解决该问题？ 文献［１Ｘ１］提电与ＭＥＴＩＳ结合的算法ＭＬＰ， 在粗糙化过程中使用ＬＰＡ， 可划分具有１０亿以上顶点的獨．以上两种方法Ｍ适用于静态图 ｘＤＧＩ＾１ １２！＾—个基于ＬＰＡ和顶点迁移的自适斑分布式图划分系统？Ｓｐｉｎｎｅｒ［１ １ ３］是基于ＬＰＡ以顶点为中心在Ｐｍｇｅｌ下实现的图划分算法， 其根据权麗和分区太小为每个顶点赋予对应的分数， 并以此判定顶点■ 是齊迂移至其他分区． 文献［１１４］将ＫａＦＦＰａ 与ＬＰＡ结合，并在文献［８７］中实现了其分布式算法， 可划分上ｆ乙顶点的國？ 旦遞量聲窗于ＰｓｒＭＥＸＩＳ和ＰＴｉ＆ｏｔｄｉ，但是该方法．在划分知识图谱时需要将其转化为无向图， 未利用知识樹谱的貭性橋息．７． ２ 基于查询负载的算法近年乘由于知识函谱的广泛礙用， 出现了一些提升ＲＤＦ知识請谱查询性能时國划， 分算法， 文献［１１５］中使用对ＲＤＦ谓语迸行随机划分的箕法ＰＢ， 可在一■定糧度上廉裔査爾效率＜还有一些方法则是直接基于查询负载对ＲＤＦ图进行划分［ ６ °＇１ １ ６ １ １ ７ ］， 其中文献［１１７］增加了查询负载 彳 Ｑｉ， Ｑ＇２ ，…， （３」． 豫算法的目的暴根据边屬性出现的频繁程度对边进行划分， 从而提齊查询性能． 为了＾找羼貧髙访间频率的模式（ Ｆ ＡＰ）瞥要定义ＦＡＰ使用值謂ＣＱ． ｐ以记录ＦＡＰ的访问频率， 其中Ｑ是一个ＳＰＡＲＱＬ查询，户是一种频繁钫何糢式．丨１， 如果ｆ是Ｑ的子围ｕｓｅ｛Ｑ， ｐ）＝Ｃｌ： ？ｌ〇． 否则馨變镇：式 多命中ｉ询Ｑ的增盤： 为ｉｆｅｗ／Ｍ＃，Ｑ）＝｜Ｅ（岁） ｜其：中玖束） 是＃中滕“＇组边． 对于一组频繁模式Ｐ＝彳九． 九，上的增益是其所有ＦＡＰ的增益和．ＢｅｍｆｉｔＣＰｆｉ＾Ｓ—ｔａａ％｛Ｂｅｈ：ｅｆｉｔ（ｐ＾ Ｑｉ） ｝（１６）算法的优化目标是最太化受存储约束限制的增益？＃于这个问题是ＮＰ难的， 文献〇１１７］＇莱用贪心算法选择频繁访问模式． Ｍ１６ 是鲠繁访问模式的一个示侧？文職［１１〇提出了两种分片策略： 藥直分片和水平分片．垂直分片蕭要将匹配到相同频繁访问模式的图放人＿一个分片？ 直为单个ＲＤＦ图包含的频繁访问＊式有限， 过滤棹不相关的元素可以提高查询性能．对于圈４的ＲＤＦ图， 采用图１Ｓ 的频繁访向隹式ｆ， —直發片如图１？所亦王 鑫等： 知识图谱划分算法研究综述 ２４９ １ 期２０１６Ｉ“ＣｈａｄｗｉｃｋＢｏｓｅｍａｎ”一ｉｎ－Ｃ＾＾ｈａｄｗｉｃｋ＿Ｂｏｓ＾ｍｎ＾＞２０１５ ２０１８ Ｃ＾ｒｋ＿Ｒｕｆ＾Ｉ＞ｒｏｌｅＢｒｕｃｅＢａｎｎｅｒ”｜图１ ７ 基于查询负载的垂直分片对于水平分片， 需要将相同频繁访问模式的匹配放入不同的分片中． 首先定义结构简单谓语＃为单个频繁访问模式对应的等式或不等式． 假设频繁访问模式ｆ含有变量集合Ｖａｒ＝｛ｔ；ａｎ，ｔ；ａｒ２ ，…，ｔ；ａｒ？｝， ＃的定义如下：ｓｐｉｐｉｖａｒｉ）６Ｖａｌｕｅ（１７）其中 ， ＶａＺｗｅ 是常量约束．以图１６ 的频繁访问模式为例， 可以生成结构简单谓语如下：（ １）ｓｐｉ：ｐ（？ｘｌ）＝＾ＣｈａｄｗｉｃｋＢｏｓｅｍａｎ＾；（２）ｓｐ２：＾（ ？ｘｌ）＾ＣｈａｄｗｉｃｋＢｏｓｅｍａｎ＾；（３）ｓｐｚ ：ｐｉ ｌｘ２）—Ａｖｅｎｇｅｒｓ：Ｉｎｆｉ ｎｉｔｙ＿Ｗａｒ；（４）ｓｐＡ：Ａｖｅｎｇｅｒｓ：Ｉｎｆｉ ｎｉ ｔｙ＿Ｗａｒ．再将结构最小谓语定义为相同频繁访问模式的＃的合取？ 给定一组 ｛ 咖， 咖，…，｝， 结构最小谓语 ｛ｍ九，／？＾２ ，…， 的定义如下：Ｍ—｛ｍｐｉ＼Ａｓｐｋ（１８）ｓｐｋｅＳＰ其中，＝或＾＾＝然后根据结构最小谓语对图进行划分．依然以图１６ 的频繁访问模式为例， 对应的结构最小谓语如下：（１）／７Ｚ户丄： 户（ ？ｘｌ）＝“ＣｈａｄｗｉｃｋＢｏｓｅｍａｎ”八ｐｉＰ． ｘＺ）＝Ａｖｅｎｇｅｒｓ：Ｉｎｆｉ ｎｉｔｙ＿Ｗａｒ；（２）ｍ户２ ： 户（ ？ｘｌ）＝“ＣｈａｄｗｉｃｋＢｏｓｅｍａｎ”八ｐＣ＂！ｘ２）７＾Ａｖｅｎｇｅｒｓ：Ｉｎｆｉｎｉ ｔｙ＿Ｗａｒ；（３）／ｔｚ户３ ： 户（ ？ｘｌ）＃“ＣｈａｄｗｉｃｋＢｏｓｅｍａｎ”八＾？（？ｘ２）＝Ａｖｅｎｇｅｒｓ：Ｉｎｆｉ ｎｉｔｙ＿Ｗａｒ；（４）７７ｚ户４ ： 户（ ？ｘｌ）＃“ＣｈａｄｗｉｃｋＢｏｓｅｍａｎ”八＾？（？ｘ２）７＾Ａｖｅｎｇｅｒｓ：Ｉｎｆｉ ｎｉ ｔｙ＿Ｗａｒ．图１８ 显示了从上述结构最小谓语生成的所有水平分片．Ｃ＾＾＾ｇｅｒｓ：Ｉｎｆｉｎｉｔｙ．十２０１８ 饥Ｐｉ＾Ｃｈａｄｗｉｃｋｎａｍｅ＾ｒｐｌｅ＜ＣＩ＾ａｄｗｉｃｋ＿Ｂｏｓｅｍ＾＞ａｃｔｓｊｎａｃｔｓ＾ｎ２０１８ｙ＾Ｔ２０１６｜ ｍｐ２“Ｍａｒｋ Ｒｕｆｆａｌｏ’’｜ ｜ “Ｂｒｕｃｅ Ｂａｎｎｅｒ”ｃｒｋ＿Ｒｕｆｆ？一Ｉａｃｔｓｊｎｘｐ＼＾Ｃ＾＾ｇｉｇｅｒｓ：Ｉｎｆｉｎｉｔｙ＿＾＾＾＞２０１８“ＰａｕｌＲｕｄｄ”ｎａｍｅｄ＾ｕｌ＿Ｒｕ＜＾Ｈ＞ａｃｔｓｊｎ８“Ａｎｔ－ｍａｎ”ｒｏｌｅ’ｙｅａｒ２０１５（／ｕａｐｔａｉｎ＿Ａｍｅｒｉｃａ＾、Ｊ：ｉｖｉＬＷｋ＾２０１６｜ ｍｐ４图１ ８ 基于查询负载的ＲＤＦ图划分中结构最小谓语ｍ办、 和ｍ九对应的水平分片Ｍ分片和水平分片的侧重点不同， 前者利用查询的局部性来提高吞吐儀， 后者旨在通过并行化子查询来縮短查询响应时间， 文献Ｄ１７］最后在权衡这两种分片策略优勢的塞础上， 提出掘， 合分片策略？表Ｓ绐出了以上两种划分奪．法的一个小鍺．表７ 汇总了本文介绍的所有类型的知识图谱划分算法， 包括＇每种箅法的文献和主要特桌描述？从表中可以看出， 流式图划分算法、分布式图划分算法以及基于查询负载的算法有很大的发，展空间， 应该． 成为未来知识图谱划分的重启研究；ｒｉｉｇ ■表６ 其他类型图划分算法小结焉製： 儒Ａ计肆翁单、 直楼， 划＿鍫 爾塗切ｉｆ象缺蟲ＵｇａｒＫｆｅＫ馨人本身不保证负载平衡，需要加限制条件或与ｘＤＧＰＥ１ １？其他算法结合． ｒｎＳｐｉｎｎｅｒ［１ １３ ］描述顶点根据约束条件更新自身标签在粗糙化阶段使用标签传播算法在用标签传播算法进行划分后进行顶点迁移根据权重和分区大小为每个顶点赋予分数， 以此判定顶点是否迁移基于查询负载的算法充分考虑了图的结只针对ＲＤＦ图， 计算构信息和属性信息较为复杂ＷＡＲＰ［６０］Ｐｅｎｇ 等人［１ １７ ］将ＭＥＴＩＳ算法应用于ＲＤＦ图， 并通过匹配查询模式进行扩展根据频繁访问模式对ＲＤＦ图进行划分２５０ 计 算 机 学报２０２１ 年表７ 知识图谱划分算法总结类型 名称 文献 描述基本图划分算法谱划分算法几何划分算法分支定界算法ＫＬ算法及其衍生［２５］？［３１］［２８］［３２］？［３７］［４０］？［４７］［４８］［４９］［５０］［５１］利用Ｌａｐｌａｃｅ 矩阵的特征向量对图进行划分根据顶点坐标进行图划分将图划分分成多个子问题递归求解， 从而找到最优解在已有图划分基础上交换顶点多极图划分算法基于匹配的算法基于聚合的算法［５０］？［６３］［６４］？［７１］将图粗糙化为小图进行划分， 再将划分结果投影回原始图基于ＧＰＡ匹配的多级划分流式图划分算法Ｈａｓｈ算法及其衍生贪心算法及其衍生Ｆｅｎｎｅｌ 算法及其衍生［７３］［７４］［７５］［７６］［７７］［７８］［７９］ ［８０］构建散列函数， 实现随机划分基于特定规则选择负载较小的分区在最大化相邻顶点和最小化不相邻顶点之间进行插值分布式图划分算法ＫａＦＦＰａＥ算法及其衍生ＪＡＢＥＪＡ算法及其衍生轻量级重划分算法［５３］［６３］［８７］［８８］ ［８９］［９０］［９１］［９３］在每个级别上执行多次粗糙化／反粗糙化过程使用顶点交换和模拟退火技术进行图划分根据图的更新信息进行划分， 顶点按照指定顺序迁移其他类型图划分算法标签传播算法基于查询负载的算法［８７］［１０９］？［１１４］［６０］［１１６］［１１７］更新顶点标签为最多邻居顶点标签， 多次迭代后得到结果从ＲＤＦ图中选出常用的查询负载模式， 并以此作为划分依据８ 实验分析前文中提到， 知识图谱划分是为知识图谱的分布式存储、查询、 推理和挖掘提供了基础支撑． 本节选取查询和挖掘， 将划分后的数据集上传至集群进行分布式存储， 通过实验比较不同划分算法对查询和挖掘的响应时间， 分析划分效果与二者的内在联系， 并延伸至推理层面．８． １实验环境实验分析前简要介绍本次实验使用的硬件和软件配置． 硬件配置： 实验集群由５ 台腾讯云标准型Ｓ５ 服务器构成， 每台机器都有４ 个ＣＰＵ和１６ ＧＢ内存， 系统盘大小５０ＧＢ， 网络连接为以太网．软件配置： 操作系统为ＣｅｎｔＯＳ７．６， 每台机器安装分布式ＲＤＦ知识图谱数据库管理系统ｇＳｔｏｒｅＤ？来进行查询， 并使用ＭＰＩＣＨ３．３．２ 来进行集群中多个机器节点间的通信． 实验在合成数据集ＬＵＢＭ和真实数据集ＤＢｐｅｄｉａ２０１９ ０８３０？的实体间链接图文件ｍａｐｐｉ ｎｇｂａｓｅｄ＿ｏｂｊｅｃｔｓ＿ｅｎ上完成， 对数据集中的ＲＤＦ图进行划分， 数据集的具体内容如表８ 所示， 其中平均度的定义如下：平均度＝边数（ １９）表８ 最大负载率算法 ＬＵＢＭ１００ ＤＢｐｅｄｉａＨａｓｈ １． ００ １． ００ＭＥＴＩＳ１．０３１．０３Ｉ ＩＤＲＦ １． ００ １． ００ＪＡＢＥＪＡ １． ００ １． ００ＰＢ １． ６１ １． ２４实验从前文提到的图划分算法中选取５ 种典型算法， 对其图划分效果进行实验验证． 算法包括： 基于随机划分思想的Ｈａｓｈ算法、多级图划分算法ＭＥＴＩＳ（见４．１ 小节） 、流式图划分算法ＨＤＲＦ？（见５．２ 小节） 、分布式图划分算法ＪＡＢＥＪＡ？（ 见６．２ 小节） 以及基于ＲＤＦ谓语的划分算法ＰＢ？（见７．２ 小节）．８． ２ 划分效果分析由于ＲＤＦ图是三兀组的集合， 故对于顶点划分算法， 需要将宾语复制到主语所在分区， 以保证三元组的完整性． 第２ 节给出了图划分的两个目标， 分别是最小化跨越分区的顶点数或边数以及负载平衡．本小节针对这两个指标展开实验， 选择ＬＵＢＭ１００作为ＬＵＢＭ数据集的代表， 在其和ＤＢｐｅｄｍ数据集上使用５ 种具有代表性的图划分算法， 分别在２ 到１ 〇 个分区进行实验． 为了统一划分标准， 通过统计复制顶点数来比较划分效果， 复制顶点数越少说明该算法的划分效果越好， 其结果如图１９ 所示． 并统计了最大分区顶点数与理想状态下各分区顶点数的比值作为最大负载率， 在表９ 给出， 其定义如下：最大分区顶点数最大负载率：（２０）负载平衡时各分区的顶点数从图表中可以得出以下结论：（１）Ｈａｓｈ 算法的复制顶点数最多， 这是由于Ｈａｓｈ算法是一种随机划分的算法， 不能保证划分质量， 同时， Ｈａｓｈ算法严格按照平衡分区进行计算． 由前文分析可知， 各类图划分算法的目的均在于减少（ＤＵｓｉｎｇｇＳｔｏｒｅＤｌｉｎｋ， ｈｔ ｔｐｓ：／／ｇｉｔｈｕｂ．ｃｏｍ／ｂｎｕ０５ｐｐ／ｇＳｔｏｒｅＤ．ｈｔ ｍｌ２０１９，２，１６②ＤＢｐｅｄｉａｄａｔ ａｓｅｔｓ， ｈｔ ｔｐｓ： ／／ｗｉｋｉ， ｄｂｐｅｄｉａ． ｏｒｇ／ｄｅｖｅｌｏｐ／ｄａｔ ａｓｅｔｓ， ｈｔｍｌ２０１９ ， ８ ， ３０③ＵｓｉｎｇＩ ＩＤＲＦｌｉ ｎｋ， ｈｔｔｐｓ： ／／ｇｉｔ ｈｕｂ．ｃｏｍ／ｆａｂｉｏｐｅｔ ｒｏｎｉ／ＶＧＰ．ｈｔ ｍｌ２０１５，７，６④ＵｓｉｎｇＪＡＢＥＪＡｌｉｎｋ， ｈｔ ｔｐｓ：／／ｇｉｔｈｕｂ． ｃｏｍ／ｆａｔ ｅｍｅｈｒ／ｊａｂｅｊａ．ｈｔ ｍｌ２０ １６，６，７⑤ＵｓｉｎｇＰＢｌｉ ｎｋ， ｈｔｔｐｓ： ／／ｇｉ ｔｈｕｂ． ｃｏｍ／ｄｉｃｅｇｒｏｕｐ／ｒｄｆ ｐａｒｔ ｉｔｉｏｎｉｎｇ． ｈｔｍｌ２０１８，７ ，１２王義等； 知班真鬚刻分＿＊＿寒難 ２５ １１ 期（ａ） ＬＵＢＭｌＯＯ不同机器间时通信开销， 而Ｈａｓｈ算法的目的只是为了快速划分， 并不考虚划分质量■， 故其他ｉ 种算法的复制 点数均小于 吨算法．．（ ２）ＭｆｉｔＥ算法在这两个数据集上的纖合划分效果最好， 特到是在ＤＢｐｅｄｉａ■ 数据集下， 其平均复制顶点数仅为Ｈａｓｈ算法的仏２％，并且明显少于另外３种算法， 这也是目前在较小规模團上最常用ＭＥＴＩＳ舊法敵麋卸此外， ＭＥＴＩＳ算法在粗糙化图上进行平衡划分， 但是在投射回縻始图时会造成一定的備差， 导致最终负载稍有不平衡？（幻ＨＤＲＦ算法在ＬＵＢＭ数据集下的划分效１０图１９Ｎｕｍｂｅｒｏｆｐａｒｔｉｔｉｏｎｓ（ｂ ）ＤＢｐｅｄｉａ不＿１身饕蠢■复制琪虞戆果更好， 主要原因在于ＨＤ． ＲＦ箕法适甩于蓁率图，而ＬＵＢＭ数据集的平均度更高， 说明其包含的高次顶点数要多于ＤＢｐｅｄｉｓ 数据集４更有利于： ＨＤＲＦ算法的运行．（４）ＪＡ－ＢＥ－ＪＡ箅法的划分效果在这５ 种算法中处于中等水平 其适用范围较广， 更适含在大规模数提集上进行划分？ 由于该算酱是祖已绫划分好的平衡分区上进行顶点交换， 所以可以保持負载突全平衡．切ＰＢ算法的复制顸点数较多， 仅次于ｍｉ ｓｈ算法， 这是Ｈ为它在划分时主要基于的是一种随机方法７ 同时， 诶算法役有考虑负载平衡， 在一定程度Ｊ：降低了复制顶点数．表９实验所用数据集数据集 大小 顶点数 边数 平均度＝边数／顶点数ＬＵＢＭ２０３４１ Ｍ ６６３６４７ ２ ６８７ ５９６ ４． ０５ＬＵＢＭ４０６７６ Ｍ １ ３０８２７４ ５４９５７４２ ４．２０ＬＵＢＭ ＬＵＢＭ６０ ０． ９ ９Ｇ １９７１ ８７１ ８００２４７２ ４． ０６ＬＵＢＭ８０１．３３Ｇ ２ ６４２ ８１０１０７２６ ４１５ ４． ０６ＬＵＢＭ１００１．６ ６Ｇ ３ ３０１ ７１８ １３ ４０３ １３４ ４． ０６ＤＢｐｅｄｉａ ｍａｐｐｉ ｎｇｂａｓｅｄ＿ｏｂｊｅｃｔｓ＿ｅｎ １．５２Ｇ ４２５ ６８９２ １１ ０１８ ２４９ ２．５９８． ３ 查询时间分析本组实验对比了不同划分算法在分区数为４ 时的查询时间鼻体实现方法是在ＬＵＢＭ数据集和ＤＢｐｅｄ＇ｉ ａ 数据集上进行划分疴，对ＬＵＢＭ数据菜使用查询Ｑ１、 Ｑ２ 和Ｑ３， 对ＤＢｐｅｄｉ ａ数据集使用查询ＤＱ１、ＤＱ２：和ＤＱ３， 同时记議查询的响： 愈： 时间ｓ 其中Ｑｒ和ＤＱＩ 讓于星麵慮询， Ｑ２、 Ｑ３、ＤＱ２ 和０＜３￥麗乎复． 杂查询， 娘和ＤＱ＆匹配的查询数要远超过Ｑ２和ＤＱ．２， 査询难度依歡增加， ＆询暴旬可在附录中查墙，图２０ 和阌２１ 分别展示了这爾组数摒集上的实验结巣．在ＬＵＢ．Ｍ数摒梟上， 显縣Ｈａｓｈ算法的查询时间在５种算． 法中是最长的，：ＰＢ箕法的查询时间＇量短， 而其他３ 种划分算法并无屋著差别．从图２０ （ａ．）可以着出， 各类算法在简单查询上的查询时间差别不太、， 尤其， 是在较小数据集ＬＵＢＭ２〇 和ＬＵＢＭ＾上， 二牽？的查询时间几乎相两． ． 随着查询难度的增加，图２ＣＫＷ开始有较明显的＿距；》 宣到■在图２０心）中， Ｈａｓｈ算法在． ＬＵＢＭ１０．０数据集上的查询时间与ＰＢ算法相差１２．９ｓ，达到最大．在ＤＢｐｅｄｋ数裾集上的锗果与ＬＵＢＭ数据集相似， 不同的是差距要小一些， 在图２１（ｃｊｒＪｌ： 方能看到较为清楚的结果． 这与两个数据集的平均度有关系，ＤＢｐｅｄｉ ａ数据集的乎均度小， 导致可四配时查询数少， 对应的查询时间降低？ 相比较而言＊在ＤＢｐｅｄｉａ数据集ＪｌＭＥＴＴＳ： 算法的查询效果聲比ＬＵＢＭ数据集上更奸一通过对比划分效果图可知， 查询时间与复制顶２５ ２ 计 算机 学 报 ２０２１年ＬＵＢＭ２０ＬＵＢＭ４０ＬＵＢＭ６０ＬＵＢＭ８０ＬＵＢＭ１００Ｄａｔａｓｅｔｓ（ａ） 查询Ｑ１的运行时间ＬＵＢＭ２０ＬＵＢＭ４０ＬＵＢＭ６０ＬＵＢＭ８０ＬＵＢＭ１００ＤａｔａｓｅｔｓＬＵＢＭ２０ＬＵＢＭ４０ＬＵＢＭ６０ＬＯＢＭ８０ＬＵＢＭ１００Ｄａｔａｓｅｔｓ（ｃ） 查询Ｑ３的运行时间图２０不同划分算法在ＬＵＢＭ数据集上的查询时间０．５１°ａ〇Ｇｒａｐｈｐａｒｔｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｓ（ａ） ＤＱｌＧｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｓ（ｂ） ＤＱ２Ｇｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｓ（ｃ） ＤＱ３，釘 本獨划分霉徵在ＤＢｐｓｊｉａ黎載集上的查询时间点数总体ＪＬ呈正相关？Ｈａｓｈ箅法的划分效果最差，所以查■询耗时最长，ＭＥＴＩＳ算法在ＤＢｐｅｄｋ数据集１： 的划分效果敏好，：对座簡查＿用－时植少：， 这是：由于随机分配导致围处理財跨机器的计算较多， 逋偾时间太大增加， 查询时间随之增长． ＰＢ算法的情况诗殊．興其增加了根据谓语进行划分这一环节，提；高了査询效率． 所以它的查询时间要少于其他划分算法？由此可得出结论， 对于大部分知识图谱划分算法， 跨越分Ｋ的顶点数或边数越多， 基于此种知识窗谱划分算法的查询处理时间就越长．８，４ 挖掘时间分析由于数据挖掘是从大量数据中搜索隐藏信：息， 这里来用复齋查询方式达到这一目的＊ 在ＬＵＢＭ１００数据集和ＤＢｐｅｄｋ数据集上分别使用挖掘谱句ＤＭ１和ＤＭ２， 挖掘语句可參见附录，图２２展示了不同划分算法在两个数据集上分区数为４ 时的挖掘时间．与查询结某相似，Ｈａｄｉ 算法的挖掘时间明屬超过其他４ 种算法， ＰＢ算法的时间最魔， ＭＥＴＩＳ算王 鑫等： 知识图谱划分算法研究综述 ２５３１ 期Ｇｒａｐｈｐａｒｔｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｓ（ａ）ＬＵＢＭ１００Ｇｒａｐｈ ｐａｒｔｉｔｉｏｎｉｎｇａｌｇｏｒｉｔｈｍｓ图 不同划分！壽糖猶挖掘法次之． 不同的是， 因为挖掘耗时较长， 各个箅法闻的差距比查询时吏大． 所以对于挖掘来说， 奠运行时间主要与算法的划分效果有关， 跨越分区的顶点数或边数越多？执行数据挖掘时的通債开铕就越大， 相应的运行时间也越长．我们相信，读结论同样适；ｆｌ予知识图谱的推理，因为任何在知 图请上进行的分布式计箅都需要考虑通倩开锴的问题＊而＇图划分的目标是减少跨越分Ｋ的顶点或边， 从而减少通信时间， 根抿上述实验－分析可知， 知识图谱划分效果越好，划分后进行査询、推理和挖掘等操作的时向就越少．８． ５ 实验总结表１０给出了率节实验效果的一个总结． 显然，Ｈａｓｈ＇算法的划分敏臬、 聋＿效果和挖掘效果较差，祖是它的时间复杂度低， 容易实现， 适合在大规模图上霧要＇快速划分的倩况； ＭＥＴＩＳ算法的整体效畢较好， 在ＤＢｐｅｃＵａ 数据集上＿现最为明显， 但也有其简限性， 只适用于本地环境下规模较小的数据集；ＨＤＲＦ算法和ＪＡ－ＢＥＪＡ算法处乎中间水平， 不同的蕞ＨＤＲＦ算法更：适甩于幂率Ｋ＿， 所以在ＬＵＢ． Ｍ数据集上的划分、查：询、挖掘效果要比ＪＡ－ＢＥ－ＪＡ算法更好； ＰＢ算法的划分效果较差，但是查询和挖掘效果最好兩行时间少， 适合騫栗快速进＃ＲＤＦ圈＂计算的情况． 综上所述， 没有哪一种算法在所宥情况Ｔ都是最好的， 爵赛根据实际情况选择合适的算法，从而高效地实现知识图儀分布式存储、 蜜询、推埋、挖掘等一系列操作＊表１０ 实验效果总结算法 划分效果 查询效果 挖掘效果Ｈａｓｈ 负载平衡， 复制顶点数最多 查询时间最长 挖掘时间最长ＭＥＴＩＳ 负载稍不平衡， 但复制顶点数最少， 特别是在ＤＢｐｅｄｉａ数据集上 查询时间较短 挖掘时间较短Ｉ ＩＤＲＦ 负载平衡， 复制顶点数较少， 在ＬＵＢＭ数据集上效果更好 查询时间较长 挖掘时间较长ＪＡ－ＢＥ－ＪＡ 负载平衡， 复制顶点数较少 查询时间较长 挖掘时间较长ＰＢ 负载不平衡， 复制顶点数较多 查询时间最短 挖掘时间最短９ 未来研究方向逋过上述分析与比较， 可以＃出知识圈瓚划分已轻取得了一定的成臬ａ提出了不少成熟的理论和算法？偉是， 现存的钿识菌谱刘分算法的理论、方法与技术尚有许多灣限性？仍面临翁许多问蘧和挑战，进一步．研ｆｔ建處包：猶（１） 知识圈１１划分标准与算法效率如何权衡本文介绍的知识图谱的划分算法大部分是顧一般图划分寡法的基础ｉｉ迸行的， 由予知识图谱包含燈息要比一般的图獏３１丰富和复杂， 划分通當和后期的１存储查询枏结合， 增加了划分难度． 传统的图划分方法以降低顶点或边的切割数为划分員标， 以负载是否平衡、 是否具有较小的时间复杂度等作为衡量划分好坏的标准． 但是对于知识ｆｉ谱而言， 除了这些以外， 还应以知识图贵的图结构和属牲翁息作为划分标准， ＿分是为了更好地执行后续的存储、 查询、推理和挖掘操作？ 此外， 知识图谱数据镆型尚未有统一定义， 也没有确定的标淮． 所以讀耍深入研充针对知识围谱的划分算法＜做到既要有利于支持知识時谱查询的快速执行， 又繫避免划分算法复杂度过窗＾（ ２） 面询知识野谱窗层语义如何划分知识图谱的一个重要”特点是对本体的表示． 以２５４ 计 算机 学 报 ２０２１年ＲＤＦ图为例， 其源于语义Ｗｅｂ的发展， 其在标准制定之初即面向Ｗｅｂ 上全局资源的表示、发布和集成，在ＲＤＦ图之上定义了ＲＤＦ模式语言（ＲＤＦＳｃｈｅｍａ）和Ｗｅｂ本体语言（ＯＷＬ） ， 可用于表示丰富的高级语义知识． 虽然目前已经有了针对ＲＤＦ图语义划分的算法， 但是还没有考虑利用本体语言作为启发信息进行划分． 如何利用知识图谱高层语义指导划分是非常重要的研究方向．（３） 面向知识图谱应用需求如何划分知识图谱的应用领域非常广泛， 在社交网络、道路交通、 电子商务等方面都有着重要作用． 以电子商务为例， 企业可以构建用户的知识图谱， 对用户的商品查询情况、 购买记录进行分析， 将用户划分至对应的消费人群． 知识图谱的领域应用研究正处于起步阶段， 目前各个领域特定的知识图谱划分结果还没有相应的质量评价指标， 如何针对应用需求进行知识图谱划分还需要进行深人研究．（４） 超大规模知识图谱如何划分目前， 大规模知识图谱划分普遍使用分布式算法， 例如， 基于ＭａｐＲｅｄｕｃｅ、Ｐｒｅｇｅｌ、ＭＰＩ 等已有分布式处理框架进行划分．但是随着具有数十亿三元组规模的知识图谱不断涌现， 现有分布式方法已不足以应对超大规模知识图谱的划分， 通常会导致算法运行时间增长， 不同机器间跨越边数或顶点数增多， 通信成本增加等． 这就需要进一步研究超大规模知识图谱的高效划分方法， 使得知识图谱在负载尽量均衡的情况下减少不同机器间的通信开销， 在满足划分目标的同时降低划分算法的复杂度．（５） 基于知识图谱表示学习如何划分近年来， 知识图谱表示学习开始兴起， 其主要思想是将知识图谱的实体和关系嵌人到低维向量空间中， 在保留结构信息的同时有效支持下游任务． 基于知识图谱表示学习的划分方法是一个值得研究的新方向， 目前已有的方法是在图嵌人后利用坐标信息，使用几何划分方法进行划分． 但这些算法只限于单机环境， 还没有扩展到分布式框架上． 如何更好地将表示学习与其他常用的划分方法特别是分布式图划分算法结合， 从而提高划分的效率和质量是非常有意义的研究课题．（６） 知识图谱划分如何支持存储查询知识图谱划分是分布式存储的必要手段， 划分的目的是为了更好地执行后续的存储查询． 所以划分阶段需要考虑存储查询， 同样地， 执行存储查询时也需要考虑划分．当前已经有基于查询负载的知识图谱划分算法， 但都是基于静态图的划分． 在现实应用中， 知识图谱数据会随时间而动态变化， 需要及时更新划分的输人图． 如何使其与动态图划分算法更好地结合， 以及如何对划分算法与存储查询方案融合进行优化设计仍需进一步研究．１０总 结知识图谱以精确的语义描述了现实世界中的实体以及实体间的关系， 有着广泛的应用． 知识图谱划分作为大规模知识图谱分布式处理的首要工作， 具有十分重要的意义． 本文对现有知识图谱划分算法进行了研究综述， 介绍了４ 种基本图划分算法， 比较了多级图划分算法的２ 种类型， 给出了流式图划分算法的主要思想， 描述了３ 种分布式图划分算法， 介绍了最近提出的２ 种新型图划分算法， 在合成与真实知识图谱数据集上探究了５ 种知识图谱代表性划分算法在划分效果、查询处理与图数据挖掘方面的性能差异， 最后展望了知识图谱划分算法的未来研究方向．致 谢 感谢湖南大学信息科学与工程学院彭鹏博士在实验环境配置中提供的帮助， 同时感谢编辑部和审稿人给予本文的宝贵意见！