开放科学（资源服务）标志码（OSID）：

0 概述

知识图谱(Knowledge Graph，KG)是海量数据领域中重要的知识储备库^[1-2]，为知识查询、问答系统和推荐系统^[3]等应用提供知识服务^[4-5]。KG用节点表示实体，用边表示实体间的关系，一个由关系、头实体和尾实体构成的三元组表示一个事实。知识图谱补全(Knowledge Graph Completion，KGC)指通过预测实体之间的新关系来构造三元组^[6]，从而提升KG中知识的丰富程度^[7]。

将实体和关系表示为低维空间中的向量，是一类有效的KGC方法，通过向量间的计算来解决KG内部的关系预测问题。但现实世界中的知识在不断增加变化，这要求KG及时补充现实世界中的知识，而这类KGC方法难以满足从现实世界中学习知识的要求。因此，研究人员将KG内部的补全方法称为封闭世界下的KGC方法，将不包含于KG的数据称为开放世界数据，进一步提出开放世界KGC方法，这类方法的基本思想是从数据中提取KG中不存在的新实体来补全三元组，从而为KG引入新实体。

现有的开放世界KGC方法虽然有效地解决了新实体的来源问题，但每次只能针对缺失头实体或尾实体的一个三元组进行补全，在一定程度上限制了新知识的全面性。KG中关系之间存在相互依赖的性质，可以用来学习新实体的多种关系，但KG不能直接描述这种依赖性。贝叶斯网(Bayesian Network，BN)是表示和推理具有依赖性和不确定性知识的有效工具。本文提出一种基于BN的开放世界KGC方法，给出关系之间依赖性的BN表示模型，设计BN模型构建方法，利用KG来构建BN。在此基础上，提出基于BN概率推理的三元组构造方法，利用现有的命名实体识别技术从开放世界数据中获取包含新实体的三元组，将其作为证据，基于BN概率推理构造更多包含新实体的三元组，从而提升知识的全面性并完善KG。

1 相关工作

基于KG的表示学习进行KGC是一类典型的KGC方法，其补全效果的好坏依赖于表示模型的性能高低。TransE模型^[8]将关系视为实体间的平移向量，其能够有效计算“一对一”关系，但计算“一对多”“多对一”和“多对多”等复杂关系时存在局限性。文献[9]提出TransH模型，利用超平面及该超平面上的向量表示关系，使每个实体在不同关系下拥有不同的向量表示，但TransH仍假设实体和关系处于相同的语义空间，在一定程度上限制了其表示能力^[10]。文献[11]提出TransR模型，为实体向量构造一个公共的空间，并为每个关系向量构造只属于该关系的空间。

上述方法能够将KG中的实体和关系表示为向量空间中的向量，不仅保存了实体和关系的语义，还使得实体和关系变得可计算，进而为KGC、KG查询等任务提供定量的依据，对KG具有重要意义。虽然基于表示学习的封闭世界KGC方法能够在KG内部有效地预测三元组，但是开放世界中的新知识也是补全KG的重要知识来源。封闭世界KGC方法难以满足向KG中引入新实体的要求，因此，有必要研究开放世界KGC方法。

近年来，研究人员用开放世界KGC方法从数据中提取新实体加入KG，从而丰富KG中的知识。文献[12]利用全卷积神经网络从数据中提取新实体，进而利用新实体补全缺失头实体或尾实体的三元组，为KGC提供了一种新思路。文献[13]将文本、图片和数值等多种类型数据作为新实体来构造三元组，丰富了KG中实体的类型，但多种类型的数据导致计算复杂度较高。

开放世界KGC方法能够为KG引入开放世界中的新实体，为KGC方法提供一种新思路。现有的开放世界KGC方法依赖于数据中给出的知识，能够学习到数据中直接描述出的与新实体相关的知识。然而，与一个实体相关的知识往往是多方面的，数据中给出的知识通常只是其中的一部分。现有的开放世界KGC方法虽然能够引入新实体，但无法提升知识的全面性。若利用开放世界数据中给出的知识学习到更多知识，同时对新实体所涉及的多种关系进行补全，将大幅提高新知识的全面性和KGC的效率。

2 基于KGBN的知识图谱补全

KG中同一类型实体涉及的关系之间通常具有相互依赖的性质，给定某个类型实体涉及的一些关系，通过关系之间的依赖性可得到该实体可能涉及的其他关系，从而利用该实体及更多关系来构造三元组。若从开放世界数据中提取的新实体与KG中的实体为相同类型，则新实体涉及的关系往往也符合KG中关系之间的相关性。例如，一部电影的类型为“喜剧”，另一部电影与这部电影具有相同的导演，则其类型很可能也为“喜剧”。在开放世界KGC任务中利用这种依赖性，能基于数据中新实体给定的关系获取其涉及的更多关系，从而提升KG中知识的全面性。因此，如何定量地描述KG中同类实体涉及的关系之间的依赖性，是实现开放世界KGC的重要前提。

BN^[14]是描述变量间相互依赖关系和不确定性知识的有效工具^[15]。基于证据变量的取值，利用BN的概率推理，可计算得到查询变量不同取值的条件概率。鉴于BN对不确定性知识表示与推理的优势，本文将BN作为KG中关系之间依赖性表示和推理的框架，构建一个基于KG的BN(KG-based Bayesian Network，KGBN)，其中包含有向无环图(Directed Acyclic Graph，DAG)和条件概率表(Conditional Probability Table，CPT)，将KG中的关系表示为KGBN中的变量，并将KG中关系连接的不同尾实体表示为KGBN中变量的不同取值。如图 1所示，将KG中的关系“导演” “演员”和“类型”表示为KGBN中的变量x₁、x₂和x₃，“演员1”出演的某部电影为“喜剧”的可能性可利用条件概率P(x₃=“喜剧”|x₂=“演员1”)=0.95进行定量描述。

KGBN的构建包括DAG构建和CPT计算。对于同一类型的实体而言，它们共同涉及的关系描述了该类实体的特性，在KGC任务中考虑这些关系对实体的描述作用，能够更准确地获取新实体的特性，从而为构造三元组提供可靠的依据。因此，本文将关系在实体描述中的重要程度作为构建DAG的依据，在DAG中使得重要关系的优先级高于次要关系，进而获取关系之间的依赖性。具体而言，关系的出现频率越低，则越能准确描述实体的特点^[16]。若将关系看作一种“资源”，关系连接的尾实体看作“传播介质”^[17]，那么“传递资源多”的关系在实体描述中发挥着更重要的作用，如“语言”关系的尾实体“普通话”一般不具备其他信息，而“导演”关系的尾实体“导演1”具有国籍、作品等信息，根据“导演1”容易推出电影的“语言”为“普通话”，反之则很难推出一部“普通话”电影的“导演”是“导演1”。

本文提出基于KG中关系出现频率和传递资源数的DAG构建方法，给出关系在实体描述中重要程度的定量计算方法，将一个关系重要于另一个关系的状态表示为DAG中一个变量指向另一个变量的有向边，构造出DAG，进而提出基于KG的三元组数据集抽取方法，从KG中抽取关系与尾实体的不同组合情况，并获取每种组合的出现次数，从而得到包含KGBN中不同变量取值组合及其个数的数据集。在此基础上，给出基于最大似然估计法的CPT计算方法，利用DAG和数据集为每个变量计算CPT，最终构建出KGBN。

为了实现开放世界KGC，本文将从开放世界数据中提取的包含新实体的三元组作为KGBN推理的证据，通过概率推理来获取新实体涉及的更多关系，从而构造出新的三元组。BN推理分为精确推理和近似推理，精确推理通过给定证据变量取值来计算查询变量的后验概率分布，近似推理降低了精确推理的复杂度和对精度的要求，以在较短时间内得到一个近似解^[18]。

三元组的正确与否决定了KG所表达知识的可靠性，考虑到KGC任务对结果的精度要求较高，本文在KGBN推理中采用精确推理，提出基于KGBN推理的三元组构造方法，从数据中提取包含新实体的三元组，将其中的关系及尾实体作为KGBN推理中的证据变量及其取值，并将KGBN中其他未知取值的变量作为查询变量，进而基于KGBN推理得到查询变量不同取值的条件概率，将条件概率作为构造新三元组的依据，从而构造出包含新实体及更多关系的三元组。

本文方法也可用于封闭世界KGC任务，即针对KG中已有的实体进行补全。针对KG中已有的某个实体，在包含该实体的三元组中存在已知的关系和尾实体，可以作为KGBN推理的证据变量及其取值，基于KGBN推理即可获取其他变量的取值条件概率，进而构造出更多三元组。

本文使用DBpedia数据集^[19]和Freebase数据集^[20]，分别在开放世界和封闭世界下进行链路预测和三元组类型预测实验，以测试本文方法的结构构建效率。

3 KGBN构建 3.1 相关定义

定义1^[10] 将KG表示为$ {G}_{K}=\left(E, R, T\right) $，其中，$ E=\left\{{e}_{1}, {e}_{2}, \cdots , {e}_{\varepsilon }\right\} $表示实体集合，$ \varepsilon $为实体个数，$ R=\left\{{r}_{1}, {r}_{2}, \cdots , {r}_{\gamma }\right\} $表示关系集合，$ \gamma $为关系的个数，$ T=\left\{\left(h, r, t\right)\right\}(h, t\in E, h\ne t, r\in R) $表示三元组集合，h为头实体，t为尾实体。

BN通过DAG和CPT来表示和推理变量间的相互依赖关系和不确定性知识，其中，DAG的节点表示变量，有向边表示变量间的依赖关系，每个节点具有一个CPT，描述了父节点对该节点的影响程度。KGBN由DAG和CPT构成，其中，变量表示KG中的关系，变量的取值表示关系连接的尾实体。为方便后续讨论，将KGBN中的变量个数设为$ n(n <\gamma ) $。

定义2 将KGBN表示为$ \varphi =\left({G}_{B}, \theta \right) $，其中：

1) $ {G}_{B}=\left(X, Y\right) $表示DAG结构，$ X=\left\{{x}_{1}, {x}_{2}, \cdots , {x}_{n}\right\} $表示变量集，$ {x}_{i} $表示$ {G}_{K} $中同类实体所涉及的任意一个关系，Y表示有向边集，$ 〈{x}_{i}, {x}_{j}〉 $表示由$ {x}_{i} $到$ {x}_{j} $的有向边，此时，$ {x}_{i} $称为$ {x}_{j} $的父变量，变量$ {x}_{j} $的父变量集合记为$ {P}_{\mathrm{p}\mathrm{a}}\left({x}_{j}\right) $。

2) $ \theta $表示所有变量的CPT集合，其由$ P\left({x}_{i}\right) $和$ P\left({x}_{i}|{P}_{\mathrm{p}\mathrm{a}}\left({x}_{i}\right)\right) $构成。

3.2 DAG构建

为了构建KGBN，本文提出基于关系出现次数和传递资源数的DAG构建方法，通过定量计算关系在实体描述中的重要程度来获取关系之间的优先级别，并将其表示为DAG中变量之间的有向边，从而获取KG中同一类型实体所涉及的关系之间的依赖性。

KG中出现频率低的关系能更准确地描述实体的特点，例如，某部电影具有2位“主演”和10位“工作人员”，“主演”往往比“工作人员”更能说明电影的特点。本文提出逆频(Inverse Frequency，IF)指标来度量关系在实体描述中的重要程度。对于$ {G}_{K} $中的任意关系r，IF计算公式如下：

$ {I}_{\mathrm{I}\mathrm{F}}\left(r\right)=\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\frac{\gamma }{{N}_{T}\left(r\right)} $

(1)

其中，$ {N}_{T}\left(r\right) $为三元组集合T中包含关系r的三元组个数。

KG中“传递资源越多”的关系对实体描述的作用越大，本文提出关系传递(Relation Transfer，RT)指标，在某些关系具有相同IF值时，利用RT值度量这些关系对实体描述的重要程度。对于r，RT计算公式如下：

$ {R}_{\mathrm{R}\mathrm{T}}\left(r\right)=\left\{\begin{array}{l}\mathrm{l}\mathrm{o}{\mathrm{g}}_{a}\frac{{N}_{T}\left(h\in {E}_{r}\right)}{\sum\limits_{i=1}^{n}{N}_{T}\left(h\in {E}_{i}\right)}, {N}_{T}\left(h\in {E}_{r}\right)\ne 0\\ 0, {N}_{T}\left(h\in {E}_{r}\right)=0\end{array}\right. $

(2)

其中，$ {E}_{r} $表示在集合T中关系r连接的尾实体集合，$ {N}_{T}\left(h\in {E}_{r}\right) $表示集合T中以$ {E}_{r} $中各实体为头实体的三元组个数，即关系r连接的尾实体的出度之和，$ \sum\limits_{i=1}^{n}{N}_{T}\left(h\in {E}_{i}\right) $为$ \varphi $中n个变量所表示的关系的$ {N}_{T}\left(h\in {E}_{r}\right) $之和。

在构建$ {G}_{B} $时，首先利用式(1)计算各变量所表示关系的IF值，并根据IF值对变量进行降序排列，得到$ {G}_{B} $的变量集X和关系的IF值数组；然后统计关系在$ {G}_{K} $中传递的资源数，利用式(2)计算X中各变量所表示关系的RT值，得到关系的RT值数组。

在进行DAG构建时，依次从变量集X中取出变量$ {x}_{i}(1\le i\le n-1) $，放入SameX集合中，并将这个变量所表示关系的IF值与X中下一个变量$ {x}_{i+1}(1\le i\le n-1) $所表示关系的IF值进行比较，比较结果分为以下4种情况：

1) 若两个关系的IF值不相等，则在有向边集Y中添加SameX集中每个变量指向下一个变量$ {x}_{i+1} $的有向边。

2) 若两个关系的IF值相等，进而比较它们的RT值，并在Y中添加所表示关系的RT值大的变量指向所表示关系的RT值小的变量的有向边。

3) 若两个关系的IF值和RT值均相等，则判断这个变量是否为X中的倒数第二个变量，若不是，则将这个变量保留在SameX集中，并开始下一次循环，因此，SameX集中的变量所表示的关系的IF值和RT值总是相等的。

4) 若两个关系的IF值和RT值均相等，且这个变量$ {x}_{i} $是X中的倒数第二个变量，则将X中的最后一个变量$ {x}_{n} $放入SameX集，并获取SameX集中的变量个数s，找到X中第n-s个变量$ {x}_{n-s} $，$ {x}_{n-s} $即为所表示关系的RT值大于SameX集中变量所表示关系的RT值的最接近的变量，接着在Y中分别添加$ {x}_{n-s} $指向SameX集中除第一个变量之外的每个变量的有向边，并清空SameX集，结束循环。

DAG的构建过程如算法1所示：

算法1 KGBN的DAG构建

输入

X：DAG的变量集

Y：DAG的有向边集，初始为空

IF：变量所表示关系的IF值数组

RT：变量所表示关系的RT值数组

输出

$ {G}_{B} $：KGBN的DAG结构

1.SameX$ \leftarrow \mathrm{\varnothing } $

2.for i=1 to n-1

3.SameX$ \leftarrow $SameX$ \bigcup ${x_i}

4.if (IF[i]$ \ne $IF[i+1])

5.for each $ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $ in SameX

6.Y$ \leftarrow $Y $ \bigcup $ < $ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $，x_i+1 > ，SameX$ \leftarrow $SameX-{$ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $} //加边

7.end for

8.else if (RT[i] > RT[i+1])

9.for each $ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $ in SameX

10.Y$ \leftarrow $Y $ \bigcup $ < $ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $，x_i+1 > ，SameX$ \leftarrow $SameX-{$ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $}

11.end for

12.else if (RT[i] < RT[i+1])

13.for each $ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $ in SameX

14.Y$ \leftarrow $Y$ \bigcup $ < x_i+1，$ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $ > ，SameX$ \leftarrow $SameX-{$ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $}

15.end for

16.else if (i=n-1) //RT值相等

17.SameX$ \leftarrow $SameX$ \bigcup ${x_i+1}，s$ \leftarrow $|SameX|

18.if (s≠n) //找出RT值大于x_i的最接近的变量

19.for each $ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $ in SameX

20.if (j≠1)

21.Y$ \leftarrow $Y $ \bigcup $ < x_n-s，$ {\mathrm{x}}_{\mathrm{j}}^{\text{'}} $ >

22.end if

23.end for

24.SameX$ \leftarrow \mathrm{\varnothing } $

25.end if

26.end if

27.end for

28.return $ {\mathrm{G}}_{\mathrm{B}} $=(X，Y)

算法1的执行代价主要取决于KGBN中变量的个数，若变量集X中有n个变量，则算法1的时间复杂度为O(n)。

如表 1所示，算法1在第一次、第二次执行中分别添加有向边 < x₁，x₂ > 和 < x₂，x₃ > ，在第三次执行时，将x₃与x₄比较，得到$ {I}_{\mathrm{I}\mathrm{F}}\left({r}_{3}\right)={I}_{\mathrm{I}\mathrm{F}}\left({r}_{4}\right) $，且$ {R}_{\mathrm{R}\mathrm{T}}\left({r}_{3}\right)={R}_{\mathrm{R}\mathrm{T}}\left({r}_{4}\right) $，将x₃保留在SameX集中，继续循环。接着，将x₄放入SameX集中，并与下一个变量x₅进行比较，得到$ {I}_{\mathrm{I}\mathrm{F}}\left({r}_{4}\right)={I}_{\mathrm{I}\mathrm{F}}\left({r}_{5}\right) $和$ {R}_{\mathrm{R}\mathrm{T}}\left({r}_{4}\right)={R}_{\mathrm{R}\mathrm{T}}\left({r}_{5}\right) $，且x₄为倒数第二个变量，将x₅放入SameX集。此时，SameX集中有3个变量，由此找到变量x₂，根据表 1可以看出，x₂所表示关系的RT值大于SameX集中变量所表示关系的RT值，且x₂是最接近SameX集中变量的变量，因此，分别对SameX集中除第一个变量之外的每个变量添加x₂指向该变量的有向边，即 < x₂，x₄ > 和 < x₂，x₅ > 。

3.3 数据集抽取和CPT计算

本节基于KG三元组抽取数据集，利用三元组中的关系和尾实体来生成KGBN中包含n个变量取值的组合，并统计变量取值组合的个数，从而利用DAG和数据集计算得到KGBN的CPT。

基于KG三元组抽取数据集的过程为：

1) 从$ {G}_{K} $的三元组集合T中抽取满足以下2个条件的三元组：

(1) 三元组的头实体和构建$ \varphi $的实体为同一类型。

(2) 三元组的关系为$ \varphi $中变量所表示的关系。

2) 对于这些三元组中的每一个关系，将其作为$ \varphi $中的变量$ {x}_{i} $，同时将这个关系连接的不同尾实体作为变量$ {x}_{i} $的不同取值，得到变量的取值集合，记为$ {x}_{i}=\left\{{k}_{1}, {k}_{2}, \cdots , {k}_{{m}_{i}}\right\} $，其中，$ {m}_{i} $为$ {x}_{i} $的取值个数。

3) 利用$ \varphi $中的变量及其取值得到所有可能的取值组合$ \left\{{d}_{1}, {d}_{2}, \cdots , {d}_{\delta }\right\} $，其中，$ \delta =\prod \limits_{i=1}^{n}{m}_{i} $，$ {d}_{l}\left(1\le l\le \delta \right) $表示第l种变量取值组合。

接着，统计每种取值组合的个数，过程为：

1) 基于前文抽取出的满足2个条件的三元组，将其中头实体为同一个实体的多个三元组归为一条数据。

2) 利用这条数据中的关系及尾实体生成$ \varphi $的变量及变量取值，每条数据可生成一个包含n个变量取值的组合，若这个组合与变量取值组合$ {d}_{l} $相同，则将这个组合作为$ {d}_{l} $的一个实例。

3) 根据前文所得的变量取值组合，利用KG统计每种变量取值组合的个数，构成数据集$ D=\left\{({d}_{1}, {N}_{D}({d}_{1}\left)\right)\mathrm{ }, ({d}_{2}, {N}_{D}({d}_{2}\left)\right)\mathrm{ }, \cdots \mathrm{ }, ({d}_{\delta }, {N}_{D}({d}_{\delta }\left)\right)\right\} $，其中，$ {N}_{D}\left({d}_{l}\right) $表示$ {d}_{l} $的实例数。

假设KG的片段如图 2所示，其中每个关系分别连接2种尾实体。在图 1所示的KGBN中，共有2个变量，每个变量有2个取值，计算可得数据集中共有2×2×2=8种变量取值组合，如图 2中数据集D的片段所示。利用实体“电影1”构成的多个三元组生成变量取值组合，记为d₁的1个实例，根据KG片段统计得到d₁共有2个实例。

在计算CPT时，若$ {x}_{i} $无父变量，其CPT值为$ {x}_{i} $的边缘概率分布$ P\left({x}_{i}\right) $；若$ {x}_{i} $有父变量，则其CPT值为条件概率分布$ P\left({x}_{i}\right|{P}_{\mathrm{p}\mathrm{a}}\left({x}_{i}\right)) $。基于最大似然估计法^[14]，利用$ {G}_{B} $和数据集D计算$ {x}_{i} $的CPT值$ {\theta }_{ijk} $，如式(3)所示：

$ {\theta }_{ijk}=\left\{\begin{array}{l}P({x}_{i}=k)=\frac{{N}_{D}({x}_{i}=k)}{\sum\limits_{l=1}^{\delta }{N}_{D}\left({d}_{l}\right)}, {P}_{\mathrm{p}\mathrm{a}}\left({x}_{i}\right)=\mathrm{\varnothing }\\ P\left({x}_{i}\right|{P}_{\mathrm{p}\mathrm{a}}\left({x}_{i}\right))=\frac{{N}_{D}({x}_{i}=k, {P}_{\mathrm{p}\mathrm{a}}({x}_{i})=j)}{{N}_{D}\left({P}_{\mathrm{p}\mathrm{a}}\right({x}_{i})=j)}, {P}_{\mathrm{p}\mathrm{a}}({x}_{i})\ne \mathrm{\varnothing }\end{array}\right. $

(3)

其中，$ {N}_{D}({x}_{i}=k) $为D中满足$ {x}_{i} $取值为k的实例数，$ \sum\limits_{l=1}^{\delta }{N}_{D}\left({d}_{l}\right) $为D中的实例数之和，$ {N}_{D}\left({P}_{\mathrm{p}\mathrm{a}}\right({x}_{i})=j) $为D中满足$ {x}_{i} $的父变量$ {P}_{\mathrm{p}\mathrm{a}}\left({x}_{i}\right) $取值组合为第j种的实例数，$ {N}_{D}({x}_{i}=k, {P}_{\mathrm{p}\mathrm{a}}({x}_{i})=j) $为D中满足$ {x}_{i} $取值为k且其父变量$ {P}_{\mathrm{p}\mathrm{a}}\left({x}_{i}\right) $取值组合为第j种的实例数。

4 基于KGBN推理的三元组构造

本节以开放世界数据中提取的包含新实体的三元组为基础，利用其中的关系及尾实体获取KGBN推理中的证据变量及其取值，进而将新实体涉及的其他关系作为查询变量，并将推理得到的查询变量取值作为关系连接的尾实体，从而构造出新的三元组。开放世界数据中的三元组可以用经典的LSTM-CRF^[21-22]技术获取。BN精确推理的计算复杂度相对于变量个数成指数增长，变量消元(Variable Elimination，VE)方法^[23]利用变量间的条件独立关系减少推理过程中的变量个数，降低计算复杂度，使得整体计算复杂度未必相对于变量个数成指数增长^[18]，因此，本文采用VE作为KGBN推理算法。

将从数据中提取的三元组集合记为$ W=\left\{\left({h}^{\text{'}}, \right.\right.{r}_{1}^{\text{'}}, $ $ \left.{t}_{1}^{\text{'}}\right), $ $ \left.\left({h}^{\text{'}}, {r}_{2}^{\text{'}}, {t}_{2}^{\text{'}}\right), \cdots , \left({h}^{\text{'}}, {r}_{\omega }^{\text{'}}, {t}_{\omega }^{\text{'}}\right)\right\}$$\left({r}_{1}^{\text{'}}, {r}_{2}^{\text{'}}, \cdots , {r}_{\omega }^{\text{'}}\in X\right) $ ，其中，$ {h}^{\text{'}} $为从数据中提取的新实体。将集合W中的关系作为$ \varphi $中的证据变量，记为证据变量集合X_z，并将关系连接的尾实体作为各证据变量的取值。将集合X中存在而X_z中不存在的变量作为查询变量，记为查询变量集合X_q，最大条件概率的阈值记为$ \alpha $。

基于KGBN推理构造三元组的基本思想如下：首先，针对集合X_q中任意一个查询变量x，计算得到包含$ \varphi $中所有概率分布的集合，并将X_z中各个变量的取值代入其中；其次，对除x外所有属于X但不属于X_z的变量设置消元顺序，对其中每个变量进行求和消元，得到一个新的概率分布集合；然后，将概率分布集合中的所有函数相乘得到关于x的函数，进而利用函数计算得到x各个取值的条件概率，并找到最大条件概率P(x=k|X_z)；随后，判断最大条件概率是否大于等于阈值$ \alpha $，若是，则利用满足大条件概率的k值构造三元组($ {h}^{\text{'}}, x, k) $；最后，将三元组和集合W加入$ {G}_{K} $的三元组集合T中。重复上述过程，直到循环结束。基于KGBN推理的三元组构造过程如算法2所示。

算法2    基于KGBN推理的三元组构造

输入

$ \varphi $：KGBN

W：包含新实体$ h\text{'} $的三元组集合

X_z：证据变量集合

X_q：查询变量集合

T：KG的三元组集合

E：KG的实体集合

输出

$ {T}^{\text{'}} $：补全后的KG三元组集合

$ {E}^{\text{'}} $：补全后的KG实体集合

1.for each x in X_q

2.F$ \leftarrow \rm{ \mathsf{ φ} } $中所有的概率分布

3.在F中代入证据变量的取值

4.$ \rm{ \mathsf{ ρ} }\leftarrow $X-X_z-{x} //设置变量消元的顺序

5.while ($ \rm{ \mathsf{ ρ} }\ne \mathrm{\varnothing } $) //求和消元

6.设I为$ \rm{ \mathsf{ ρ} } $中首位变量，将I从$ \rm{ \mathsf{ ρ} } $中删除

7.从F中删除涉及I的函数，设为$ \left\{{\mathrm{f}}_{1}, {\mathrm{f}}_{2}, \cdots , {\mathrm{f}}_{\mathrm{k}}\right\} $

8.g$ \leftarrow \prod \limits_{\mathrm{i}=1}^{\mathrm{k}}{\mathrm{f}}_{\mathrm{i}} $ //计算得到新的概率分布

9.u$ \leftarrow \sum\limits_{\mathrm{I}}\mathrm{g} $

10.将u放回F

11.end while

12.将F中所有函数相乘，得到x的函数u(x)

13.P(x=k|X_z)$ \leftarrow \underset{\mathrm{k}\in \mathrm{x}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}\left(\mathrm{u}\left(\mathrm{x}\right)/\sum\limits_{\mathrm{x}}\mathrm{u}\left(\mathrm{x}\right)\right) $//计算x不同//取值的条件概率，并得到最大条件概率

14.if (P(x=k|X_z)$ \ge \mathrm{\alpha } $)

15.$ {\mathrm{T}}^{\text{'}}\leftarrow ${(h$ {}^{\text{'}} $，x，k)}$ \bigcup $ T $ \bigcup {\mathrm{T}}^{\text{'}} $ //构造三元组

16.end if

17.end for

18.$ {\mathrm{T}}^{\text{'}}\leftarrow $W$ \bigcup $T，$ {\mathrm{E}}^{\text{'}}\leftarrow ${h$ \mathrm{\text{'}} $} $ \bigcup $ E

19.return $ {\mathrm{T}}^{\text{'}}, {\mathrm{E}}^{\text{'}} $

算法2的执行代价主要取决于集合X_q中的查询变量个数和每次推理中消元的变量个数，算法2的总执行代价为查询变量的个数和每次推理中消元执行代价之和的乘积。

在封闭世界下执行KGC任务时，首先，将KG中包含同一个头实体的多个三元组作为一个集合；其次，利用其中的关系及尾实体作为证据变量及证据变量的取值；然后，将集合X中其他变量作为查询变量；最后，针对查询变量进行KGBN推理，利用算法2得到新的三元组。

以图 1中的KGBN为例，假设从数据中提取到三元组集合W={(“电影”，“导演”，“导演1”)，(“电影”，“演员”，“演员1”)}，证据变量及其取值为{x₁=“导演1”，x₂=“演员1”}，查询变量为x₃。利用算法2计算P(x₃)，首先得到KGBN中的概率分布集合{P(x₁)，P(x₂|x₁)，P(x₃|x₂)}，设置变量消元顺序为{x₁，x₂}。从概率分布集合中删去包含x₁的函数，并生成新函数g(x₂)=$ \sum\limits_{{x}_{1}}P\left({x}_{1}\right)P\left({x}_{2}\right|{x}_{1}) $，得到{g(x₂)，P(x₃|x₂)}。类似地，消去x₂，得到P(x₃=“剧情”|x₂=“演员1”)=0.05，P(x₃=“喜剧”|x₂=“演员1”)=0.95，构造三元组(“电影”，“类型”，“喜剧”)。

5 实验验证

将本文知识图谱补全方法记为BN-KGC，使用DBpedia50k、DBpedia500k^[19]和FB15k^[20]数据集在开放世界下测试BN-KGC的效率和有效性。BN-KGC也可用于封闭世界KGC任务，本文基于OpenKE平台^[24]实现TransE^[8]、TransH^[9]和TransR^[11]方法，在封闭世界下测试BN-KGC的有效性。

FB15k数据集包含14 951个实体和1 345个关系，DBpedia50k和DBpedia500k数据集分别包含49 900个实体、654个关系和517 475个实体、654个关系。3种数据集的三元组个数划分情况如表 2所示。

本文定义了最大条件概率的阈值$ \alpha $，利用$ \alpha $来决定KGBN推理所得的取值是否能够作为构造三元组的实体。若$ \alpha $值过小，则会导致结果的准确率降低；若$ \alpha $值过大，则会导致所得结果的数量减少。本文利用验证集进行阈值设置，首先对验证集中的三元组进行KGBN推理，得到构成这些三元组的正确结果的条件概率(正确结果的条件概率不一定为最大条件概率)，进而利用这些条件概率计算平均值并作为阈值$ \alpha $，本文通过测试将阈值$ \alpha $设置为0.95。

5.1 结构构建效率测试

为了验证本文KGBN构建方法的有效性，对KGBN构建方法的执行时间进行测试。首先，针对KGBN中不同的变量个数，测试在不同数据集下计算IF值和RT值的执行时间。计算IF值、RT值的执行时间结果分别如图 3和图 4所示，从中可以看出，执行时间均随变量个数的增多而增加。其中，在FB15k数据集下执行时间最长，在DBpedia500k数据集下执行时间次之。对从KG中抽取数据集的执行时间进行测试，结果如图 5所示。从图 5可以看出，抽取数据集的执行时间随KGBN中变量个数的增多而增加，其中，在DBpedia500k数据集下执行时间最长，在FB15k数据集下执行时间次之。

将同个数据集下的IF值、RT值计算和数据集抽取的执行时间进行对比，在FB15k、DBpedia50k和DBpedia500k数据集下的执行时间情况分别如图 6~图 8所示。从中可以看出，在同等条件下RT值计算的执行时间总体大于IF值计算的执行时间，且数据集抽取的执行时间略高于IF值计算的执行时间，但远低于RT值计算的执行时间。

测试含不同变量个数时KGBN结构构建的执行时间，结果如图 9所示。从图 9可以看出，构建KGBN的执行时间随变量个数的增多而增加，在DBpedia500k数据集下的执行时间最长，在FB15k数据集下的执行时间次之。这表明在KGBN构建的执行时间中IF值和RT值计算的执行时间占比很小，同时测试中针对3个~11个IF值的降序排列以及针对3个~11个变量的DAG构建花费的时间远小于IF值计算的时间，这说明本文KGBN构建方法的执行时间主要取决于CPT的计算时间。

5.2 开放世界KGC方法有效性测试 5.2.1 三元组类型预测

在三元组类型预测任务中，测试集中的三元组被称为正确三元组，将测试集中的三元组随机替换实体，得到错误三元组。其中，正确三元组被预测为正记作TP，错误三元组被预测为正记作FP，正确三元组被预测为负记作FN。三元组类型预测的评估指标分别为准确率(Precision)、召回率(Recall)及F1值。

首先，利用训练集和验证集分别构建包含5个、8个和11个变量的KGBN，并将阈值$ \alpha $设置为0.95；然后，利用测试集中的三元组进行KGBN推理，得到三元组中关系连接尾实体的条件概率，将条件概率不小于阈值的三元组记为正，否则记为负，进而得到三元组类型预测结果。

当KGBN中包含5个变量时，三元组类型预测结果的各项指标如图 10所示。从图 10可以看出，随着查询变量个数的增多，预测结果的准确率略有下降，而召回率呈上升趋势，在FB15k数据集下预测结果的F1值保持相对稳定的趋势，在DBpedia数据集下预测结果的F1值呈先上升后下降的趋势。当KGBN中包含8个变量时，三元组类型预测的结果如图 11所示。从图 11可以看出，预测结果的准确率、召回率和F1值均有明显的提升。其中，在FB15k数据集下预测结果的准确率和F1值较好，在DBpedia数据集下预测结果的召回率较好。当KGBN中包含11个变量时，三元组类型预测的结果如图 12所示。从图 12可以看出，预测结果的准确率随着查询变量个数的增多而略有下降，但召回率和F1值随着查询变量个数的增多而明显提升。

在实际中，准确率和召回率难以同时兼顾，一个较高时另一个总会较低，因此测试中通常采用F1值来综合度量方法的有效性。结合图 10~图 12的结果可以看出，随着查询变量个数的增多，针对同一个头实体构造的三元组个数增加，因此，预测结果的召回率有所提升。虽然证据变量的减少可能会导致预测结果的准确率下降，但是预测结果的F1值会有一定提升或能保持相对稳定的趋势。

5.2.2 链路预测

本文分别在3个数据集上执行链路预测任务，进一步测试BN-KGC实现开放世界KGC的有效性。链路预测能够预测三元组缺失的头实体或尾实体，可用于KGC任务。将测试集中的三元组称为正确三元组，对于任意一个正确三元组，本文利用实体集中所有实体替换其尾实体构造参考集，打分排序后根据正确三元组在参考集中的排名计算MR和Hits@10指标。MR用于度量正确三元组排名的平均值，Hits@10用于衡量排名在前10的正确三元组个数占三元组总个数的比例。利用前文构建得到的KGBN，将基于KGBN推理得到三元组中关系连接尾实体的条件概率作为评分函数，进而计算BN-KGC的MR和Hits@10。链路预测结果如表 3所示，从表 3可以看出，在FB15k数据集下，当KGBN中变量和查询变量个数分别为8和3时预测的MR结果最小，当KGBN中变量和查询变量个数分别为8和5时预测的Hits@10结果最大。在DBpedia50k数据集下，当KGBN中变量和查询变量个数分别为8和5时取得的MR和Hits@10均为最好。在DBpedia500k数据集下，当KGBN中变量和查询变量个数分别为11和6时预测的MR结果最小，当KGBN中变量和查询变量个数分别为11和4时预测的Hits@10结果最大。从总体来看，当KGBN中变量和查询变量个数分别为8和5时预测结果最好，因此，本文采用该组结果与现有的开放世界KGC方法进行比较。

如表 4所示，在DBpedia数据集下将ConMask^[12]方法与BN-KGC方法执行的链路预测结果进行比较。在DBpedia50k数据集中，ConMask的MR和Hits@10最佳，这是由于KGBN的预测效果受初始KG影响，当初始KG规模较小时难以全面地获取关系之间的相关性，从而导致BN-KGC的预测效果略差于ConMask。在DBpedia500k数据集下将BN-KGC方法和ConMask方法的链路预测结果进行比较，此时BN-KGC方法预测结果的MR优于ConMask方法。实验结果表明，当初始KG规模较大时BN-KGC方法可以较全面地获取关系之间的相关性，从而有效完成开放世界KGC任务。

5.3 封闭世界KGC方法有效性测试

BN-KGC方法也可用于封闭世界KGC任务，为了测试基于BN-KGC方法实现封闭世界KGC的有效性，分别在3个数据集下基于OpenKE平台得到TransE、TransH及TransR的三元组类型预测结果和链路预测结果，并将其与BN-KGC进行比较。

封闭世界下的链路预测结果如表 5所示，从表 5可以看出，在FB15k数据集下，基于BN-KGC方法预测的MR结果达到77，仅排在TransR之后。在DBpeida50k数据集下，基于BN-KGC方法预测的MR结果最佳。在DBpedia500k数据集下，基于BN-KGC方法预测的MR结果和Hits@10均为最佳。三元组类型预测结果的准确率、召回率和F1值如图 13所示。从图 13可以看出，在FB15k和DBpedia500k数据集下，基于BN-KGC方法预测结果的准确率和F1值最佳，在DBpedia50k数据集下，基于BN-KGC方法预测结果的准确率、召回率和F1值均为最佳。实验结果表明，本文方法同样适用于封闭世界KGC任务，即BN-KGC方法具有有效性。

本节基于FB15k和DBpedia数据集，首先，测试KGBN构建方法的时间效率，实验结果表明，KGBN的结构构建执行时间主要取决于变量个数，且其中用于计算CPT的执行时间最多；其次，在开放世界下进行三元组类型预测实验，对比不同变量个数、不同查询变量个数下的KGBN预测结果，结果表明，本文方法能够有效提升预测结果的召回率，并且在最好情况下预测结果的准确率高达0.88；然后，在开放世界下进行链路预测实验，并将本文方法的实验结果与现有的开放世界方法进行比较，结果表明，当初始KG达到一定规模时，基于本文方法预测的结果在MR指标上有所提升，达到159；最后，在封闭世界下分别进行三元组类型预测和链路预测任务，结果表明，基于本文方法预测三元组类型时的准确率和F1值明显高于基于表示学习的其他方法，并且在DBpedia500k数据集下进行链路预测时，本文方法的MR和Hits@10分别达到107和0.66。

6 结束语

本文使用BN描述KG中同类实体涉及的关系之间的依赖性，提出KGBN模型构建方法和基于KGBN推理的三元组构造方法。实验结果表明，该三元组构造方法针对新实体能够同时构造多个三元组，有效提升KGC任务中新知识的全面性。随着KG中知识的增加以及变化，关系间的依赖性也会发生相应变化，导致KGBN推理的准确率降低。因此，如何将KG中的新知识用于KGBN构建，实时反映关系间的依赖性，进而提升KGC方法的时效性，将是下一步的研究方向。