转自公众号微软研究院AI头条

编者按：知识图谱作为一种特殊的图数据，不仅人类可以识别且对机器友好。信息检索、问答系统、推荐系统、电子商务、金融风控，这些生活中常见的应用场景都离不开知识图谱的支持。如何构建一个“多快好省”的知识服务系统？微软亚洲研究院机器学习组的研究员们基于自己的经验，给出了他们的建议。

近年来，随着人工智能技术在科研和实践中的广泛发展和应用，知识图谱作为人工智能的重要课题也得到迅速发展。包含上亿条事实的公开知识图谱已经非常常见，并且不同的数据源又互相联结相通，形成了数以百亿计的超大规模知识图谱。与此同时，随着自然语言处理、深度学习等技术的发展，知识图谱的抽取技术也在不断进步，增量的知识图谱数据不断汇入。

一方面，知识的普遍性和关联性等特点决定了知识图谱只有在到达一定的数量级和覆盖率时才能真正发挥其能量；另一方面，常用知识表示方法（比如三元组）的灵活性和碎片化等特点，也让知识图谱数据的管理变得困难。在知识图谱数据已经成为一个不断快速生长的庞然大物的背景下，如何让海量知识变得可用且好用已经成为当前知识型应用的紧迫需求。

同一套知识图谱数据可以在不同应用中通用，同时对于用户而言，构建一套全新的数据系统是一项冗余和繁杂的工作。因此，为知识型应用提供在线可用或下载即可用的数据服务成为一种知识图谱的高效应用方式。本文中，我们将这种在线或离线提供知识图谱数据服务的方式称为“知识图谱即服务”。

本文将从数据、应用及挑战等角度详细阐述如何高效地管理和服务超大规模知识图谱数据，并分享作者所在团队在设计和实现百亿量级知识图谱实时服务中的一些案例经验。

知识图谱：图视角下的知识

英国哲学家弗朗西斯·培根有句名言：“知识就是力量”。Stuart J.Russell 和Peter Norvig 在《人工智能：一种现代方法》一书中指出，人工智能包括自然语言处理、知识表示、自动推理、机器学习、计算机视觉以及机器人技术。知识表示对于人工智能的重要性不言而喻。实际上，机器学习得到的模型也是一种用计算结构和数值表示的知识。

在众多知识表示方式中，知识图谱作为一种语义网络拥有极强的表达能力和建模灵活性：首先，知识图谱是一种语义表示，可以对现实世界中的实体、概念、属性以及它们之间的关系进行建模；其次，知识图谱是其衍生技术的数据交换标准，其本身是一种数据建模的“协议”，相关技术涵盖知识抽取、知识集成、知识管理和知识应用等各个环节。

知识图谱是一种特殊的图数据，它是语义的和可复用的：知识图谱数据一经获取即可被多领域应用重复使用，这也是知识图谱服务的构建动机。那么，知识图谱具体来说是什么呢？

首先，知识图谱是一种特殊的图数据。具体来说，知识图谱是一种带标记的有向属性图。知识图谱中每个结点都有若干个属性和属性值，实体与实体之间的边表示的是结点之间的关系，边的指向方向表示了关系的方向，而边上的标记表示了关系的类型。例如，“汤姆·克鲁斯”和“碟中谍”是两个实体，“出演”则是这两者之间的关系。两个实体分别对应着现实世界中的人和电影，而边则对应了他们所表示的人和电影之间的现实关联。前者是关系的起始结点，后者是关系的目标结点。实体“汤姆·克鲁斯”具有“出生日期”等属性，其属性值为“1962年7月3日”等。

其次，知识图谱是一种人类可识别且对机器友好的知识表示。知识图谱采用了人类容易识别的字符串来标识各元素；同时，图数据表示作为一种通用的数据结构，可以很容易地被计算机识别和处理。

再次，知识图谱自带语义，蕴涵逻辑含义和规则。知识图谱中的结点对应现实世界中的实体或者概念，每条边或属性也对应现实中的一条知识。在此之上，我们可以根据人类定义的规则，推导出知识图谱数据中没有明确给出的知识。比如，已知“张三是个人”，我们就可以根据“人都有父母，都有大脑，需要呼吸”等规则得到很多新知识，而无需在知识图谱中逐条给出。再比如，“外公”的“儿子”是“舅舅”，据此可以推导出很多实体之间的亲属等关系。

下面介绍一下广泛使用的知识图谱表示框架和查询语言：资源描述框架(Resource Description Framework, RDF) 和SPARQL 查询语言(SPARQL Protocol and Query Language, SPARQL) 。

资源描述框架中的基本元素格式为：<主, 谓, 宾> 或<s, p, o>。它采用主语、谓词和宾语的方式来表示和陈述一条知识，这种表示方式简单且灵活。由于资源描述框架的英文缩写为RDF，知识图谱数据集也经常被称为RDF数据集，而其管理工具通常被称为RDF Store或Triple Store。在RDF中，我们可以用<Tom_Cruise, Acting, Mission:Impossible>和<Tom_Cruise, Date_Of_Birth, ”July 3, 1962”>等来表示实体“汤姆·克鲁斯”的关系和属性。一个RDF 数据可以分为两个部分：

一：显式三元组。这部分由数据集直接给定。例如：

     <Sky, Color, blue>

     <Alice, Friend, Bob>

二：隐含三元组。这部分由推理规则隐含表示。规则可作用于显式三元组，其推导出的三元组数量可能巨大，甚至超过原始数据数倍。例如：

如果?x 是一种?y, 而?y是?z的子类型，那么?x 也是一种?z: (?x, IsA, ?y) & (?y, SubclassOf, ?z) => (?x, IsA, ?z) 

如果?y是?x的朋友，那么?x 是?y的朋友: (?x, Friend, ?y) => (?y, Friend, ?x)

代表性的RDF 数据集包括Freebase、DBpedia、WikiData、Yago2、Cyc、PubChemRDF以及UniProt等。已有知识图谱数据中的数据量已达到空前规模，例如Freebase 包含大约19亿的三元组，DBpedia 包含大约30亿三元组，而Bio2RDF 拥有约100亿三元组。这些数据集因为链接开放数据倡议(Linked Open Data initiative, LOD) 而互相连通，形成了一个超过1490 亿三元组的超大知识图谱。如果算上它们遵循标准规则集(如ρdf, RDFSPlus, RDFSFull, OWL DL 等) 可得的隐含三元组，实际的数据量将更为庞大。

SPARQL是一种广泛使用的知识图谱查询语言。它的主要功能是做声明式的子图匹配，即只描述最终需要的结果模式，而具体执行的过程由底层数据管理系统决定。一个SPARQL 查询的主要组成部分是基本图模式，比如(?s, p, ?o)，三个元素分别对应主、谓、宾，其中需要匹配的元素用带问号的变量表示。通过集合交、并、差等操作符号实现组合逻辑。此外，其它的图查询语言比如GraphQL 和Cypher 也可以用于查询知识图谱。

知识图谱应用

国内外各大公司、高校以及研究机构都对知识图谱进行了探索和构建，比如谷歌的Google Knowledge Graph、微软的Bing Knowledge Graph、搜狗的知立方、 百度知心、阿里巴巴的商品知识图谱、复旦大学的CN-DBpedia、东南大学的Zhishi.me、清华大学的Xlore 以及开放中文知识图谱社区OpenKG 的cnSchema.org 等。知识图谱的发展同时也得到了政府的关注和支持，例如中国国务院在《新一代人工智能发展规划》(国发〔2017〕35号) 一文中就明确提出了知识图谱相关的发展规划。

作为一种应用型技术，知识图谱支撑了很多行业中的具体应用。例如：

- 信息检索：搜索引擎中对实体信息的精准聚合和匹配、对关键词的理解以及对搜索意图的语义分析等；

- 自然语言理解：知识图谱中的知识作为理解自然语言中实体和关系的背景信息；

- 问答系统：匹配问答模式和知识图谱中知识子图之间的映射；

- 推荐系统：将知识图谱作为一种辅助信息集成到推荐系统中以提供更加精准的推荐选项；

- 电子商务：构建商品知识图谱来精准地匹配用户的购买意愿和商品候选集合；

- 金融风控：利用实体之间的关系来分析金融活动的风险以提供在风险触发后的补救措施（如联系人等）；

- 公安刑侦：分析实体和实体之间的关系以获得线索等；

- 司法辅助：法律条文的结构化表示和查询来辅助案件的判决等；

- 教育医疗：提供可视化的知识表示，用于药物分析、疾病诊断等；

……

那么知识图谱在这些应用中是如何被访问的呢？知识图谱的服务场景按照其对响应时间的要求可以大体分为在线查询和离线分析两类。

在线查询任务包括：1) 针对实体的查询，如“作者为苏轼的诗”；2) 针对属性的查询，如“辛弃疾的生卒年”；3) 针对关系的查询，通过多跳关系搜索实现知识图谱中的关系发现，如“汤姆·克鲁斯和布拉德·皮特一起演的电影所获奖项”；4) 针对子图结构的查询，用于查询具有某种特定关系的一系列实体，如“参与演出过同一部电影并且具有夫妻关系的演员”；5) 针对查询的聚合，如“世界十大最高峰所在的国家列表”。这类查询的特点是：响应延迟敏感，但数据吞吐量低。

离线分析任务包括：1) 基于图结构的计算，如：知识图谱向量化表示、知识图谱数据补全和实体排序等；2) 基于规则的推理；3) 基于整体信息的统计分析等。这类任务对响应时间要求低，但要求高数据吞吐量。

知识图谱服务的挑战

那么，构建知识图谱服务有什么难点呢？主要包括以下三点：

一：并行图处理。作为一类特殊的图数据，知识图谱的存储、查询以及计算都需要处理和图结构相关的如下三方面挑战：

图数据的复杂性。从数据访问的角度看，无论图数据如何表示，对一个图结点邻居结点的访问都会涉及到在连续存储空间中的“跳转”，即大量的随机数据访问。大量程序优化技术依赖于数据的局部性和重用。大量随机数据访问会导致中央处理器的缓存在大部分时间里失效，进而导致系统性能急剧下降。从程序结构的角度看，图的非结构化特性使得并行处理十分困难。值得一提的是，切分图数据本身是一个NP 难问题，这让分而治之方案的系统设计变得困难。

图结构和计算的多样性。图数据类型很多，图算法的性能会因为图特征不同而大相径庭。图计算的类型也有很多种，有针对性的系统优化适用面比较受限。

图数据规模越来越大。大规模的图数据让很多经典图算法因为低效而不可用。

二：隐含语义信息处理。例如，处理(?x, Parent, ?y) => (?x, Father, ?y) UNION (?x, Mother, ?y) 和(?x, Niece, ?y) => (?x, Niece, ?y) UNION (?x, Spouse, ?z) AND (?z, Niece, ?y) 这类基于规则的推理将放大存储、查询代价。处理方法一般分为两类：一类是在查询之前就将所有隐含的三元组推导出来并作为正常三元组存储，这类方法会大量增加存储代价；另一类是在查询时，按照推理规则将一个查询重写成多个查询，最后汇总查询结果，这类方法会大大增加查询代价。而将两种方法融合的折中方法则会同时放大存储和查询代价。

三：复杂的数据模式。知识图谱的数据模式(Schema)很复杂，如‘A dog can be also an actor’ (DEFINE ‘Actor SubClass Person’?)；实体可以多角色，如‘A director who is also an actor, a singer, and a writer’；属性可以有多值或缺省，如‘An actor with many awards’ 和‘A person entity without birthday data’ 等。数据模式的复杂使得知识的物理存储和优化变得十分困难。

结合以上对数据特点、查询特点以及数据模式的分析，我们把一个知识服务系统所面临的挑战总结为以下四点：

- 系统架构：实现数据可扩展；

- 存储设计：处理随机数据访问；

- 数据访问：友好的访问接口；

- 高效查询：低延迟和/或高吞吐数据查询。

这四点汇集起来就是：多、快、好、省。

知识图谱服务的实现

我们先分析底层数据存储介质。常见的内存(RAM) 和硬盘(HDD)的响应速度级别分别为10的负7次方秒和10的负2次方秒，而数据吞吐量分别为3GB/s左右和100MB/s 左右。传统硬盘由于其机械寻道机制的限制，数据的随机化和并行化读写性能差。为了满足高并行和随机化数据访问的需求，对延迟敏感的知识图谱应用一般都选择内存作为主要的存储介质。另一方面，由于单机内存容量的限制，向上扩展代价昂贵，我们更倾向于可扩展的内存云架构。

从存储架构角度看，单机存储系统主要为两类：一类是基于传统关系数据库构建的系统，如SW-Store、Triple Tables 等；另一类是针对知识图谱数据定制的专用存储查询系统，如RDF-3X、TripleBit等。分布式系统大致可以分为分布式文件系统、键值存储系统、中心化的存储以及混合存储这四种。

对于上层应用，系统需要提供细粒度的访问接口。原因如下：首先这些接口可以作为在线查询的轻量级工具，同时可以作为离线分析的并行化组件，真正实现将N 转换为1 + 1 + … + 1，其中N 表示批量的操作，而1表示细粒度的操作。这样我们将这些1并行执行，就可以获得与批量处理相当的高吞吐量效果。反之，如果我们只支持批量处理，当系统响应多个细粒度操作时就会变成N + N + … + N，从而导致资源的浪费和响应速度的下降。

数据存储和处理模块作为中间层，向下它基于底层存储架构（比如内存云），需要考虑存储代价敏感和随机访问友好两个特点；同时向上它需要提供细粒度且高效的访问接口。

数据存储和处理模块最核心的部分是知识图谱数据的物理表示。它负责实现存储、查询和更新在内的数据管理，需要解决的核心问题是管理一个可更新的超大规模稀疏三阶张量：如果将知识图谱数据的主语、谓词和宾语三个部分分别看作三个维度，每一个维度上的取值范围即知识图谱中对应位置出现的所有值，那么整个数据集就可以被一个稀疏的三阶张量表示，而知识图谱的存储问题也可以转换为对这个三阶张量的压缩和索引。这个三阶张量非常稀疏且分布不均匀，其中主语和宾语这两维的数量大，可以达到十亿量级，而谓词通常在几千到上万的量级。我们需要在存储和查询两个方面同时做到高效，并且支持对各个维度的自由更新。

具体的优化目标包括：首先是能够尽量缩小数据存储文件的大小；其次是能够快速地处理各类数据访问请求；最后是支持增量更新。鉴于物理存储模型的复杂性和灵活性，常见的一类方法是直接将这个三阶张量中的元素（即三元组）作为最小存储单元进行压缩表示并建立索引。这种方法对三个元素按位置进行排列组合进行多次存储，已达到空间换时间的目的。这种方法我们不妨称为零阶展平。另一类方法则将三阶张量按某一阶展平，如主语（图数据结构）或谓词（垂直划分、比特矩阵等）。最后一类同时按两阶来展平，如主语和谓词，这一类我们称为强类型的存储方案。前面提到的常见数据存储方案大多属于弱类型系统，如三元表（简单直接）或“谓词-宾语”键值列表等。相比于弱类型系统，强类型系统具有更小的数据存储和访问代价和更少的联结操作(JOIN) 代价。

后记

设计一个高效的大规模知识服务系统包含大量琐碎的细节。除了通用的系统优化技巧，如果需要把我们的经验总结为一条，那将是：强类型数据建模（软件）+ 分布式内存存储（硬件）。