本文配套PPT，在微信公众号「DataFunSummit」，回复「20220312」领取
导读：今天分享的主题是有关知识图谱多步推理的最新研究成果。这系列研究重点关注如何使用embedding在大规模的、有噪音的知识图谱上进行多步推理，回答复杂的逻辑query。
今天的介绍会围绕下面四点展开：
01
知识图谱背景介绍
首先和大家分享下知识图谱的背景。
知识图谱是由一系列三元组（h,r,t）组成的，每一个三元组对应了常识信息，如“蒙娜丽莎是达芬奇创作的”、“巴黎是一个城市”等。在现实生活中，WIKIDATA和Freebase是典型的大规模知识图谱，同时它们包含的噪音信息也较多。
由于噪音信息的存在，知识图谱领域很重要的一个任务是补充图谱中缺失的边，也就是边预测或者知识图谱补全任务。
我们今天的分享主要着重于在单步推理的基础上，在含有噪音的大规模知识图谱上完成需要多步逻辑运算的推理任务。比如我们的输入可以是：“加拿大图灵奖获得者是哪个大学毕业的？”、“谁是从未举办过足球世界杯的欧洲国家的现任总统？”、“预测哪些药物可以靶向与新冠病毒相关联的蛋白质？”等问题。这些问题都需要在知识图谱上进行多步推理才能得到答案。
在推荐系统中也可以进行类似的建模。比如我们想要找到一个用户群体，使得这个群体中的用户都更倾向于赞同某一给定的帖子。这一类型的问题需要在知识图谱中进行至少两步的推理才能找到对应的答案。其可视化子图如上图所示。
下面简要定义一下多步推理任务：给定一个任意复杂的逻辑问题，我们需要直接预测答案对应的实体。如上图所示，输入问题是“找到一个药物C，使得它可能可以靶向与疾病A和疾病B都相关联的蛋白质P”，那么这个问题就可以转化为一个逻辑表达式。逻辑表达式是一个具有图结构的query plan，它也对应着人类去回答一个复杂逻辑问题的思路。比如对于图中的例子，在知识图谱中，我们从蓝色节点A与B开始，分别基于“关联”关系在图中进行游走，找到满足关系的实体（也就是和疾病A相关联的蛋白质集合，以及和疾病B相关联的蛋白质集合）；接着我们对两个候选集合取交集，找到共有的元素；最后我们根据“target”关系找到图中满足要求的药物C。
在大规模知识图谱上进行多步推理存在如下挑战：
基于上述问题，我们希望避免对图谱中隐式的边关系进行建模，同时能在大规模知识图谱中高效地找到复杂逻辑问题的答案。
--
02
Query2Box：
使用Box Embedding在知识图谱中回答复杂query
我们提出的方法属于在embedding空间进行图谱推理的模型。具体地，对于图谱中每一个实体节点和关系边我们都会学习一个embedding，同时对于给定query，我们也将其映射至相同的embedding空间中。通过这一操作，推理任务均可以在embedding空间内完成。由于embedding空间相较于高维离散输入是低维的，那么它很自然地具有更强的鲁棒性，对噪音信息更加不敏感。通过将query映射至embedding空间，多步推理寻找答案的算法就可以转化为在空间内找到与query的k近邻。
我们提出了Query2Box模型，其基本想法是将query表示为空间中的长方体，那么空间中的逻辑推理就可以很方便地被定义。例如，“与”运算对应着长方体的交集。这一做法的优点在于它解决了空间中两个点无法定义逻辑“与”运算。
具体地，我们的方法在学习节点embedding和关系边embedding的基础上增加了学习query embedding，它在空间中对应于一个高维的长方形。它由两组可学习的参数组成：中心点center以及边长offset。我们的目标问题就为：如何将一个query plan通过空间映射得到它们在向量空间中的位置。
在我们给出的解决方案中，需要定义两组算子：projection和intersection。
Projection算子将空间内一组节点集合映射至空间内另一组节点集合。例如，我们将一组蛋白质集合通过“target by”关系映射至一组疾病集合。具体地，我们使用类似于TransE的方法，将给定输入box embedding使用关系embedding平移至输出集合的box embedding。
Intersection算子是多个box embedding，输出是这些集合的交集对应的box embedding。该算子需要满足：
这是因为交集操作会使得输入集合的元素数量变小，那么它在空间中的向量表达也要同时变“小”。
以之前提到的寻找药物的query为例，其推理可视化的流程如上图所示。我们首先在向量空间中确定疾病A和疾病B的点，得到它们的embedding；接下来我们使用projection算子将A和B分别映射至两个box，它们分别表示与疾病A和疾病B相关联的蛋白质；随后我们使用intersection算子找到一个box，它们代表既和A相关联又和B相关联的蛋白质集合；之后，我们调用projection算子将集合映射至另一个box，它代表靶向候选蛋白质的药物集合；最后，我们在box中使用k近邻搜索选择候选节点。
Query2Box有如下优势：
为了去训练Query2Box，我们不仅需要得到含有答案的正样本，同时需要使用负采样得到每个query的负样本。一般来说，对于每个query，我们会选取约200个负样本，它们代表着不是正确答案的节点。我们的优化目标借鉴了对比学习，即最小化正样本embedding与query embedding之间的距离，同时最大化负样本embedding与query embedding之间的距离。
--
03
大规模知识图谱多跳推理框架SMORE
我们希望能将如Query2Box等使用embedding进行知识图谱多跳推理的模型运用在超大规模的图谱上，如拥有约9千万个节点的Freebase。但是，我们面临着两方面挑战。首先，在算法层面，由于我们需要训练多步的逻辑query，那么首先需要构建多步的逻辑query，同时我们需要为每一步query找到对应的答案以及一些负样本。这些操作的计算成本都很高，一般为指数级复杂度。其次，在系统层面，我们的模型同时含有稀疏的embedding矩阵和稠密的逻辑算子，并且系统需要高效地去生成训练数据。这些特性都对设计提出了很高的要求。
首先，给定一个知识图谱和一个query plan，我们需要构建一个具有图结构的query。我们的做法是设计一些抽象的query模板，我们的任务就是将query plan具化为一个具有模板结构的query。
Query生成的流程如上图所示。具体地，我们将模板中的抽象节点转化为知识图谱的一个节点，抽象边转化为知识图谱的一个关系。
如果我们采用随机采样的方法从query起点anchor（query template中蓝色的点）开始进行填充，那么我们无法保证最终生成的query是有答案的。所以我们的想法是从答案节点（query template中绿色的点）出发，使用知识图谱中随机采样得到的一个实体进行填充。如果把答案节点看成一颗树的根节点的话，我们的方法想到与从树的根节点开始自顶向下进行搜索与填充，直至所有的anchor节点都被映射为知识图谱上的实体。
例如图中的例子，我们首先从根节点出发，在图谱中随机选取一个实体Fulvestrant；随后由于模板进行了intersection算子操作，这意味着我们需要有多个实体集合同时包含Fulvestrant；之后，对于上半部分，我们通过随机在知识图谱上选取一个和Fulvestrant节点相关联的关系来实例化projection算子，得到“TreatedBy”关系，找到图谱中对于关系的头实体“Breast Cancer”，然后进一步选取关系“Assoc”与对应头实体“ESR2”进行实例化；对于下半部分，我们进行与上半部分类似的操作，得到“CauseBy”关系与“Short of Breath”实体；最终，我们的两个anchor node被确定，query样本生成也就完成了。
整个query实例化的过程非常高效。这是因为我们在每一步递归进行实例化时都仅仅做了随机采样一个图谱节点的操作，这对于一个最大度数为d、query模板的跳数为m的实例化操作来说时间复杂度为O(md)。
接下来我们需要解决对于一个query如何高效地生成多个负样本的问题。一个直观的做法是在知识图谱中以anchor node开始答案节点为结束，遍历所有答案，随后将不属于正样本的节点作为负样本，但是这一做法的时间复杂度是，对于大规模知识图谱来说运算过于昂贵。
所以，基于上述问题，我们提出了双向搜索的思想，即由于我们并不需要query路径中间所有的答案，所以我们可以在负采样时从anchor node开始进行m/2步游走找到一系列中间节点对应的实体，同时从答案节点开始向后遍历m/2步，来找到一些可能可以作为负样本的实体节点。最后，我们仅需要验证两个集合的节点是否含有交集即可。如果节点属于交集，那么它就不是一个负样本，反之则可以作为一个负样本进行使用。通过这一算法，负采样的时间复杂度可以降为。
在系统层面，我们也构建了一个高效的框架，从而实现同时进行query生成、query embedding运算以及梯度计算等。我们还通过异步计算和优化计算流水线的方法来加速推理过程。
除此之外，我们还提出了几个用于多跳推理的超大规模知识图谱数据集，将原来的benchmark提高了1365倍。
在小型知识图谱的多跳推理中，SMORE相较于baseline算法提升了2.2倍，GPU内存开销减少了30.6%。
对于在大型的知识图谱中进行多跳推理任务，之前很多已知的算法模型很多都因为过大的GPU内存开销和高昂的时间复杂度而无法进行训练。相对地，SMORE是第一个使这些模型能在超大规模图谱上进行训练的框架。它最大的优点在于其GPU内存开销和训练速度几乎与图的规模无关。
SMORE支持多GPU训练，并且保证模型得到线性的训练速度提升。SMORE的源代码在google research的github代码库中进行了开源，它不仅支持多跳推理的训练，还支持传统的单跳推理（如TransE等）的模型。需要指出的是，SMORE在所有知识图谱推理任务中训练效率均高于同类框架。
--
04
总结
本次分享首先阐述了embedding空间进行复杂query推理的问题。随后介绍了Query2Box模型，它使用了box embedding的思想来解决多步query的推理。为了将如Query2Box这类基于embedding空间进行多步推理的方法应用于大规模知识图谱中，我们提出了SMORE。它是第一个可以在超大规模图中进行多跳推理训练的框架，同时它已经在github上进行了开源。
--
05
Q&A
Q：Query2Box的建模灵感是什么？
A：Query2Box是针对一个集合进行建模。Box的好处是解决了空间中两个点的交集无法被定义的问题，而相对地两个box的交集很容易被计算。
Q：Box的大小如何定义的？
A：Box由中心点center和边长offset来定义。这两组参数是通过优化对比损失函数来训练来学习出来的。具体地，对比损失函数是希望正样本能被映射至答案box中，同时增加负样本与答案box的距离。直观上来理解，模型会学习更改box大小来完成上述目标。
Q：除了projection和intersection算子，有没有考虑过并集或者差集算子？
A：在我们的文章中，我们额外考虑了并集算子。具体地，我们证明了：若需要完成并集算子，对应的box embedding的维度需要足够高。那么，并集对应的操作并不能仅仅映射为一个box embedding，而是需要使用两个box embedding进行表示。那么在计算一个节点与并集的距离时，我们选取的是点与两个box之间的最小值。这一定义来源于并集的定义，即若一个点在一个集合中，那么它就在一组集合的并集中。差集算子在后续β-embedding的工作中被提出，大概做法是将集合映射为一个β分布而非一个box，而β分布可以更加灵活地实现包括差集之内的逻辑运算。
今天的分享就到这里，谢谢大家。
阅读更多技术干货文章、下载讲师PPT，请关注微信公众号“DataFunSummit”。
分享嘉宾：任泓宇 斯坦福 博士研究生
编辑整理：吴祺尧 加州大学圣地亚哥分校
出品平台：DataFunTalk
01/分享嘉宾
任泓宇
斯坦福 博士研究生
Hongyu Ren is a fourth year CS Ph.D. student at Stanford advised by Prof. Jure Leskovec. His research interests lie in the intersection of graph representation learning and neural symbolic reasoning on structured data. His recent work includes learning knowledge representations and advancing multi-hop reasoning on large-scale knowledge graphs. His research is supported by the Masason Foundation Fellowship, Apple PhD Fellowship and Baidu Scholarship.
02/报名看直播 免费领PPT
03/关于我们
DataFun：专注于大数据、人工智能技术应用的分享与交流。发起于2017年，在北京、上海、深圳、杭州等城市举办超过100+线下和100+线上沙龙、论坛及峰会，已邀请超过2000位专家和学者参与分享。其公众号 DataFunTalk 累计生产原创文章700+，百万+阅读，14万+精准粉丝。
欢迎转载分享，转载请私信留言。
| 留言与评论（共有 0 条评论） “” |
