【天津大学】知识图谱划分算法研究综述

知识图谱是人工智能的重要基石，因其包含丰富的图结构和属性信息而受到广泛关注.知识图谱可以精确语义描述 现实世界中的各种实体及其联系，其中顶点表示实体，边表示实体间的联系.知识图谱划分是大规模知识图谱分布式处理的 首要工作，对知识图谱分布式存储、查询、推理和挖掘起基础支撑作用.随着知识图谱数据规模及分布式处理需求的不断增 长，如何对其进行划分已成为目前知识图谱研究热点问题.从知识图谱和图划分的定义出发，系统性地介绍当前知识图谱数 据划分的各类算法，包括基本、多级、流式、分布式和其他类型图划分算法.首先，介绍 4 种基本图划分算法：谱划分算法、 几何划分算法、分支定界算法、KL 及其衍生算法，这类算法通常用于小规模图数据或作为其他划分算法的一部分；然后， 介绍多级图划分算法，这类算法对图粗糙化后进行划分再投射回原始图，根据粗糙化过程分为基于匹配的算法和基于聚合的 算法；其次，描述 3 种流式图划分算法，这类算法将顶点或边加载为序列后进行划分，包括哈希算法、贪心算法、Fennel 算法，以及这 3 种算法的衍生算法；再次，介绍以 KaPPa、JA-BE-JA 和轻量级重划分为代表的分布式图划分算法及它们的 衍生算法；同时，在其他类型图划分算法中，介绍近年来新兴的 2 种图划分算法：标签传播算法和基于查询负载的算法。通 过在合成与真实知识图谱数据集上的丰富实验，比较了 5 类知识图谱代表性划分算法在划分效果、查询处理与图数据挖掘方 面的性能差异，分析实验结果并推广到推理层面，获得了基于实验的知识图谱划分算法性能评价结论。最后，在对已有方法 分析和比较的基础上，总结目前知识图谱数据划分面临的主要挑战，提出相应的研究问题，并展望未来的研究方向.