, 岳昆2, 毛钰源1, 刘琰1 1. 云南大学 软件学院, 昆明 650500;
2. 云南大学 信息学院, 昆明 650500
收稿日期：2018-07-19
基金项目：国家自然科学基金资助项目（61562091，61472345）；第二批“云岭****”培养项目（C6153001）；云南省应用基础研究计划面上项目（2016FB110）；云南大学中青年骨干教师培养计划项目；云南大学青年英才培育计划项目（WX173602）；云南大学数据驱动的软件工程科技创新团队项目（2017HC012）
作者简介：罗之皓(1993-), 男, 硕士研究生
通信作者：李劲, 男, 副教授。E-mail:lijin@ynu.edu.cn
摘要：知识图谱数据具有体量大、内容丰富、类型多样、缺乏统一模式描述等特点。提取知识图谱模式信息并形成摘要模式，对于提升知识检索、挖掘质量具有重要研究意义。该文首先给出了摘要模式的判定准则以及摘要模式质量的度量标准，提出了面向知识图谱的Top-k摘要模式挖掘问题，并将该问题建模为一个次模函数优化问题；其次，为高效判定摘要模式及度量模式的覆盖质量，提出了基于Pregel编程模型的并行化摘要模式判定和质量度量算法；然后，给出了高效求解Top-k摘要模式挖掘问题的贪心算法；最后，在真实知识图谱数据上对本文方法进行了验证。实验结果表明：该方法在摘要模式的覆盖度和算法执行效率方面优于已有方法。
关键词：知识图谱摘要模式挖掘次模函数图匹配
Mining Top-k summarization patterns for knowledge graphs
LUO Zhihao1, LI Jin1
, YUE Kun2, MAO Yuyuan1, LIU Yan11.School of Software, Yunnan University, Kunming 650500, China;
2.School of Information, Yunnan University, Kunming 650500, China
Abstract: Knowledge graph data has large volumes, rich content, diverse types, and lacks a unified model description. Pattern information needs to be extracted from knowledge graphs to improve the quality of knowledge graph retrieval and mining. This paper presents a knowledge graph summarization pattern and quality metrics. This method is used in an algorithm for mining Top-k summarization patterns (Top-k SPM) formulated as a submodular function optimization problem. Then, a Pregel based parallel algorithm is used to validate the algorithm and measure the qualities of summarization patterns. Two efficient greedy algorithms are also presented to solve the Top-k SPM. The efficiency and effectiveness of the method is then verified on real knowledge graph datasets. The tests show that the method outperforms the existing methods in terms of coverage and algorithm execution time.
Key words: knowledge graphsummarization pattern miningsubmodular functiongraph matching
近年来，在网络信息技术的支撑下，以维基百科、Yago、Freebase等为代表的包含大量非结构化、异构数据的知识图谱得到了快速发展，并在社交网络，知识检索，生物信息学等领域都有广泛的应用[1-3]。同时，知识图谱数据具有体量庞大、内容丰富、类型多样、动态、无序性强、缺乏统一模式描述等特点[4]。这些特点给用户准确、有效地获取图谱知识带来了巨大的挑战。与传统关系数据相比，知识图谱缺乏统一规范的模式描述。对于用户而言，很难了解、掌握图谱数据包含的模式信息。因此，高效提取知识图谱模式信息，并形成摘要模式(summarization patterns)，以此来展示图谱数据信息、并分析不同类型实体之间的相关关系，对于提升知识图谱的知识检索、挖掘质量具有重要研究意义[5-8]。
广义上讲，知识图谱是一种图数据，因此可基于已有的频繁子图模式挖掘算法获得知识图谱的模式信息。然而，直接基于已有的频繁子图模式挖掘算法得到的图谱模式存在以下问题：1)用户很难控制算法的频繁度值，往往产生大量的频繁子图模式；2)模式的复杂程度不易控制；3)不同模式之间往往相互交叠冗余。针对这些问题，Song等[9]给出了一种新的知识图谱摘要模式挖掘方法。该方法基于已有的图模式挖掘算法得到候选模式集，并将知识图谱模式摘要挖掘建模为一个双目标优化问题，挖掘知识图谱中典型性强且冗余度低的摘要模式。然而，该方法仍然存在一些不足之处，具体地，首先，该方法目标函数的参数需要反复试验验证进行调优；其次，虽然该方法能够有效确保摘要模式集的非冗余性，模式典型性却有待提升。
针对已有方法的不足之处，本文提出了一种知识图谱摘要模式挖掘方法。首先，给出了摘要模式的定义、判定准则以及摘要模式质量的度量标准。提出了基于Pregel编程模型的并行化摘要模式判定和质量度量算法。其次，将知识图谱的Top-k摘要模式挖掘建模为一个优化问题，证明目标函数满足次模性(submodularity)。给出了Top-k摘要模式挖掘贪心算法以及算法加速方法。最后，在真实知识图谱数据上验证了本文提出的模型、算法的优势和有效性。
1 问题定义给出摘要模式的定义以及摘要模式质量度量标准，进一步定义知识图谱的Top-k模式摘要挖掘问题。
G=〈V, E, L〉为知识图(knowledge graph)，表示实体及其关系。其中：V表示节点集，?v∈V表示图谱中的一个实体；E?V×V为边集，表示实体之间的关系；L是标签函数，即L(v)是节点v的标签(或实体类型)；L(e)是边e的标签，表示e连接的2个节点之间的关系类型；P=〈VP, EP〉为模式图(pattern graph)，表示标签及标签之间的关系；VP是标签集，EP是标签关系边集。
与一般图数据不同，知识图谱含有大量实体类型信息，且实体之间的关系多样、复杂。为有效展示知识图谱并提供不同兴趣视角的模式信息，需要对图谱模式的复杂程度进行限制，因此，首先定义受限模式图。
定义1??受限模式图：给定整数参数d和b。图模式P为一个受限模式图，仅当dP≤d，|P|≤b，其中：dP为模式P中节点之间最长路径长度，|P|为P的节点数和边数的总和。
不是任何受限模式图均为有意义的摘要模式。一个摘要模式P是对知识图G中节点及节点关系的概括描述，因此，可基于图模式匹配方法来建立受限模式图是否为合法摘要模式的判定准则。一般地，图模式匹配方法有基于图同构的模式匹配[10-11]以及基于图模拟的模式匹配。图同构方法要求模式图和数据图在节点类型和节点拓扑关系严格一致情况下才能判定为匹配，匹配判定是NP-hard的，对于大规模知识图谱而言，判定求解困难。图模拟要求模式图和数据图节点类型一致，但不要求节点之间拓扑关系严格保持一致，其判定是多项式可解的，因此，本文基于图模拟匹配来定义合法摘要模式的判定准则，具体地，摘要模式由下面的定义2给出。
定义2??摘要模式：给定知识图G=〈V, E, L〉，模式图P=〈VP, EP〉，如果存在二元关系R(P, G)?VP×V，?l∈VP和每一个知识图节点v∈V构成二元关系(l, v)∈R，节点l′和v′分别为l和v的子节点。如果对于P中所有的边(l, l′)，存在图G中对应的边(v, v′)，且(l, l′)的边标签(v, v′)的边标签一致，使得二元关系(l, v)∈R，那么图模式P为图G的一个匹配的摘要。如图 1所示。
 |
| 图 1 知识图谱示例 |
| 图选项 |
给定一个摘要模式P，用R(P, G)在知识图G上决定的子图大小来度量GP的质量，为此，定义摘要模式P的覆盖度。
定义3??摘要模式的覆盖度：给定知识图G和模式摘要P。所有满足二元关系R的元组(l, v)∈R(P, G)中的实体节点v及其连接边构成的G的子图记为GP，则模式摘要P的覆盖度记为cov(GP, G)并定义如下：
| ${\rm{cov}}\left( {{G_P}, G} \right) = \frac{{\left| {{G_P}} \right|}}{G}.$ | (1) |
例1??给定参数d=2, b=5，图 1中的3个图模式满足受限模式条件。其中只有P1、P2满足摘要的定义，P3中标签为A的节点，其子节点的标签为B，而图G中，不存在这样的关系，所以P3不满足摘要的定义。摘要P1根据定义3，由P1与G的二元关系R(P1, G)={(C, c1)，(C, c2)，(C, c3)，(D, d1)，(D, d2)，(D, d3)，(F, f1)，(F, f2)，(F, f3)}，得到对应图G中节点：c1、c2、c3、d1、d2、d3、f1、f2、f3，并根据这些节点之间的关系构成子图GP1，|GP1|=18, |G|=31。同理，|GP2|=12，cov(GP1, G)=
由定义3可知，模式P的覆盖度越高，P对知识图谱数据的概括能力就越强。同时，2个摘要模式P1和P2的覆盖子图GP1和GP2的节点集、边集也可能存在交集，即摘要模式可能存在覆盖交叠。于是，如何获得概括能力强，相互不冗余的摘要模式集成为需要解决的问题，并将其描述为Top-k摘要模式挖掘问题。
定义4??Top-k摘要模式挖掘问题(Top-k SPM)：给定常数k，知识图的Top-k摘要模式挖掘问题定义如下：
| $\begin{array}{*{20}{c}}{{S^*} = {\rm{arg}}\;{\rm{ma}}{{\rm{x}}_{\left| S \right|}}{{_ = }_k}F\left( S \right) = }\\{{\rm{arg}}\;{\rm{ma}}{{\rm{x}}_{\left| S \right|}}{{_ = }_k}\frac{{\left| {\bigcup\limits_{i = 1}^k {{G_{{P_i}}}} } \right|}}{G}.}\end{array}$ | (2) |
定义5??次模函数[12]：给定集合U，函数F: 2U→?+是U上的次模函数，仅当对于任意两个集合S?T?U, 任意元素j∈U\T, 有F(S∪{j})-F(S)≥F(T∪{j})-F(T)。
定理1??Top-k SPM的目标函数满足次模性。
证明：设U为全集，设任意两个集合S和T，有S?T?U，元素Pj∈E/T。|S|=n, |T|=m, m≥n。
记
| $\begin{array}{l}\sigma (S|{P_j}) = F\left( {S \cup \{ j\} } \right) - F\left( S \right), \\\sigma (T|{P_j}) = F\left( {T \cup \{ j\} } \right) - F\left( T \right), \end{array}$ |
| $\begin{array}{*{20}{c}}{\sigma (S|{P_j}) = \frac{{\left| {\left( {\bigcup\limits_{i = 1}^n {{G_{{P_i}}}} } \right) \cup {G_{{P_j}}}} \right|}}{{\left| G \right|}} - \frac{{\left| {\bigcup\limits_{i = 1}^n {{G_{{P_i}}}} } \right|}}{{\left| G \right|}} = }\\{\frac{{\left| {{G_{{P_j}}} - \left( {\bigcup\limits_{i = 1}^n {{G_{{P_i}}}} } \right)} \right|}}{{\left| G \right|}} \ge 0。}\end{array}$ |
需要说明的是：与文[9]中将摘要模式挖掘问题定义为一个双目标函数优化问题不同，本文将Top-k SPM定义为一个次模函数最大化问题。由此，挖掘过程中无需人为指定折中因子。次模函数优化过程中寻求边际效用最大化(marginal utility maximization)的数学性质也决定了结果集由高覆盖度且相互之间非冗余的模式组成，保证了求解质量。虽然Top-k SPM是NP-hard的，但由文[13]结论可知，贪心算法求解Top-k SPM可得到保证近似下界
2 Top-k摘要模式挖掘算法首先介绍给定知识图G的一个受限模式图P，基于Pregel编程模型的判定P为合法摘要模式的判定方法，以及求P在G上的覆盖子图GP的方法。基于此，进一步介绍基于贪心算法挖掘Top-k摘要模式集，并讨论基于lazy update的挖掘算法加速方法。
2.1 摘要模式判定及其覆盖子图求解给定受限模式P和知识图G，判定P为G上的合法摘要模式的关键是：确定二元关系R(P，G)是否存在，进一步地，如果P为G上的合法摘要模式，那么，P在G上的覆盖子图GP依赖于求解R(P，G)中的所有二元元组。由定义2可知，求解R(P，G)的过程是一个基于图模拟判定P是否匹配G的过程。由文[14]可知，判定算法是多项式计算复杂度的，即O((|VP|+|V|)(|EP|+|E|))。
首先介绍判定知识图G中任意节点u∈V匹配的方法。由定义2可知，判定节点u∈V是否匹配取决于：如果u的标签是l∈Vp，且l是p中的叶子节点，则u是匹配的；如果v的标签为l，且在p中l有子结点l1′，l2′，…，lc′，那么，v在G中具有l1′，l2′，…，lc′标签的子节点，且v与其li′(i=1, 2，…, c)标签子节点之间的边与边(l, li′)的标签一致，则v匹配。
基于节点匹配判定，进一步可判定P是否为合法摘要模式，具体地，将P中节点进行拓扑排序，并生成一个由P决定的标签拓扑序列，记为l1，l2，…，lt。对知识图G中的节点，按照P中标签拓扑序列的逆序判定相应标签的节点是否匹配，最终，如果G中存在l1，l2，…，lt标签的匹配节点，那么，P被判定为一个合法的摘要模式。在对P进行判定过程中，被判定为匹配的节点及与这些节点相邻的具有相应标签的边即构成覆盖子图GP。
由于实际应用中的知识图谱含有大量节点和边，判定P和求解GP是耗时的。为高效地判定、求解，本文提出了一种基于Pregel编程模型[15]的并行化的摘要模式判定及覆盖子图的求解方法。
Pregel编程模型是一种以节点为中心的并行迭代式图计算模型。基本思想是：整个计算分为多个超步(super step)迭代执行。在每一个超步，图中节点并行地接收、合并其邻居节点发来的消息，根据消息更新节点自身的状态，然后向其邻居节点发送新消息。当图中没有消息传递时，整个Pregel过程结束。基于Pregel编程模型的摘要模式判定及覆盖子图的求解算法分为2个步骤：
步骤1??初始化：首先，为记录G中节点的匹配状态，以及记录覆盖子图信息，对于G中每个节点v设置2个变量，分别为：匹配状态mv，覆盖节点集Cv。mv是个Bool变量(T为true，F为false)，mv=true，判定节点v匹配。Cv是集合，用来存储与节点v相关的已匹配的节点集。由定义2可知，G中标签为P中叶子标签的所有节点均为已匹配节点，例如图 2中，对于给定的P来说，G中的f1、f2、f3均为匹配节点，于是有mf1=T，mf2=T，mf3=T，以及Cf1={f1}，Cf2={f2}等等。其他v是否匹配取决于其是否具有已匹配的相应标签的子节点，例如图 2中，c1是否匹配取决于d1或者d2是否匹配。于是，给定P，可初始化mv，例如，mc1=md1∨md2 (即节点c1匹配，仅当其任意一个D标签子节点匹配)，md1=mf1等.由于c1、d1等非叶子标签节点在Pregel消息传递前无法判定是否匹配，因此Cc1=?，Cd1=?等。
 |
| 图 2 基于Pregel的摘要模型判定及其覆盖子图求解 |
| 图选项 |
步骤2??Pregel消息传递：Pregel过程的消息从已判定为匹配的叶子标签节点开始。在图 2中，从f1、f2、f3开始。每个已匹配的节点根据P中规定的边标签向其父节点发消息，消息内容为：节点ID，节点标签，例如，f1向d1发送消息msg(f1, F)。需要注意的是，f2不会向d3发送消息，因为边(f2, d3)与P中F到D的边标签不同。接收到消息的节点将消息进行合并，例如d2同时接收到msg(f2, F)，msg(f3, F)，将它们按标签合并为msg({f2, f3}, F)，进而调用节点消息处理函数vprog处理合并后的消息，具体地，根据消息更新匹配判定逻辑表达式，例如，对于d2节点，其逻辑表达式为：md2=mf2∨mf3，由接收到的消息可知f2、f3已匹配，因此，更新逻辑表达式为：md2=T∨T，于是，d2判定为匹配。图 2中的Pregel过程经历2个超步(在图中用不同有向线段表示)完成消息传递。最终，c1、c2都是被判定为匹配C的标签点，因此模式P为一个合法的摘要模式，同时，其覆盖子图由所有灰色节点及相应边组成。
2.2 挖掘算法Top-k摘要模式挖掘算法的基本思想是：首先，基于频繁子图模式挖掘算法，例如GRAMI[16]，得到模式子图，并选择满足dP≤d, |P|≤bP条件的子图作为受限模式图；其次，对每个受限模式图P，采用节2.1描述的Pregel过程判定P，且如果P为合法模式，则同时求解其覆盖子图GP；再次，根据式(2)中目标函数F(S)，每次选取F(S)最大边际效用的P加入S，直到|S|=k；最后，算法输出S作为Top-k摘要模式挖掘结果。图 3中算法1给出了Top-k摘要模式挖掘算法的完整描述。
 |
| 图 3 算法1 |
| 图选项 |
算法1的时间复杂度分析如下：基于Pregel模型判定P，求解其覆盖子图GP，时间复杂度为O((|V|+|VP|)(|E|+|EP|))[14]。贪心算法求解摘要模式集S，时间复杂度为O(|P|)。所以算法1的时间复杂度为
| $O(\left| {P\left| ( \right|V} \right| + |{V_P}\left| {)(} \right|E\left| + \right|{E_P}\left| {) + } \right|P|).$ |
基于lazy update策略的Top-k摘要模式挖掘算法的基本思想是：给定摘要提取的数目k、图G和基于图G的频繁模式子图挖掘结果集P，首先对P中的所有模式子图做筛选，满足约束性图模式条件的图模式进行模式匹配，不满足约束性图模式条件的则舍去。并分别计算剩余模式子图对应的次模函数边际效益值，按照函数值做非递增排序，函数值最大对应的摘要模式图P添加到摘要集S中；在选第二元素及其以后的过程中，首先更新F值最大的模式子图的函数值，若更新之后该子图对应的函数F仍然最大，那么该元素即为当前最优值，直接添加到集合S中，如果F不是最大值，那么就按照贪心算法重复此部分的计算并排序；按照该步骤进行计算，直至S的元素个数达到k个。算法如图 4所示。
 |
| 图 4 算法2 |
| 图选项 |
算法2是算法1的加速算法，最坏的情况和算法2的时间复杂度一样，为O(|P|(|V|+|VP|)(|E|+|EP|)+|P|); 而最好的情况是，每次选取元素的时候只用计算一次，所以最优情况下的时间复杂度为O(|P|(|V|+|VP|)(|E|+|EP|)+k)。
3 实验方法与结果3.1 实验环境设置1) 实验数据集。
利用3个真实的图数据集上测试了本文的算法，其中Caida是自治系统商业关系网络，Yago是开源的知识图库，Stanford是斯坦福大学提供的网页关系网络。Caida：节点数为26 475，边数为106 762，节点标签有40类，边标签有4类。Yago：采用Yago源数据集的一个子集作为实验数据，节点集文本为1.32 MB(100 000个节点)，边表文本为5.34 MB(348 089条边)，节点标签为6 753类，边标签为37类。Stanford：节点集文本为3.08 MB(281 903个节点)，边表文本为35.7 MB(2 312 498条边)，节点标签为11 478类，边标签为120类。
2) 度量标准。
本文提出的方法旨在利用较少的数据表达更多原数据的内容，故使用覆盖度作为覆盖性的度量标准，由于图数据量比较庞大时，图模式挖掘需要消耗大量计算机内存和挖掘时间，为实验便携性，采用挖掘部分图模式进行摘要选取，定义如下：
| ${\rm{cov}}\left( {{G_S}, {G_{{P_{{\rm{sum}}}}}}} \right) = \frac{{\left| {{G_S}} \right|}}{{\left| {{G_{{P_{{\rm{sum}}}}}}} \right|}}.$ | (3) |
3) 实验环境
本文提出的算法均采用scala语言实现，所有实验在一台16 GB内存、8核(8个Intel 3.4 GHz CPU)的实验室PC机上完成。Apache Spark采用2.0版本。
3.2 实验内容如表 1所示，频繁度为图模式的挖掘标准，使用GRAMI挖掘工具根据该图模式挖掘得到相应的数目的图模式。模式图最大值和最小值(是单个图模式边数和节点数总和的最大值或最小值)用于衡量一个图模式的大小，挖掘得到的所有图模式对图G做图模式匹配得到的所有子图，存在一个对原图数据的最大覆盖，即式(3)中的GPsum，最大覆盖数为|GPsum|。
表 1 图模式挖掘的参数
| 数据集 | 频繁度 | 模式图 数目 | 模式图 最大值 | 模式图 最小值 | 最大覆盖 |
| Caida | 100 | 692 | 15 | 3 | 4 698 |
| Yago | 38 | 872 | 11 | 3 | 10 468 |
| Stanford | 400 | 542 | 7 | 3 | 17 952 |
表选项
使用GRAMI进行频繁模式子图挖掘，整个过程耗时，挖掘结果也需要消耗计算机的大量内存，通过多次调整频繁度，保证了避免内存溢出的情况下使得挖掘数目一定。数据集Caida频繁度取100，受限模式参数d=2，b=15，满足首先模式条件的图模式共692个。数据集Yago中的频繁度取38，受限模式参数d=2，b=11，满足受限模式条件的图模式共872个。Stanford频繁度取400，受限模式参数d=2，b=7，满足受限模式条件的图模式共542个。
图 5给出了3个数据集摘要选取的运行时间。运行时间包含了所有图模式的匹配以及算法进行摘要选取2部分。随着摘要模式数目的增多，时间消耗越大。在整个算法运行中，图模式匹配消耗了大量的时间，例如数据集Stanford中，进行图模式匹配的时间开销约为120 min。随着摘要选取数目的增加，图模式匹配消耗的时间不变，只增加了图模式选取所消耗的时间，故而时间增幅比较小。由此可以看出，传统的频繁模式子图挖掘得到的结果存在大量冗余图模式，通过本文算法筛选，能够挖掘到覆盖能力更强的摘要模式。
 |
| 图 5 subTopk算法在3个数据集上的运行时间 |
| 图选项 |
3.3 算法实验对比1) 双目标函数与subTop-k的实验对比。
采用文[9]中的双目标优化函数(Biopt)做实验对比，从覆盖度和时间消耗两方面进行对比。Biopt中，α的值需要用户自定义，α的值取值依次为0.3、0.5、0.7，经过实验对比，α取值为0.7的时候效果最好。
图 6中给出了3个数据集使用subTop-k算法进行摘要选取的覆盖结果。图 6a、6b、6c分别是数据集Caida、Yago和Stanford的实验结果。由表 1可知，挖掘得到的摘要模式集对应一个最大覆盖数目，采用这个最大数目来进行覆盖度的衡量。例如图 6b是在Yago数据上运行的结果，最大覆盖数目为10 468，也就是说挖掘出的872个图模式经过摘要判定后得到一系列子图，将这些子图做并，得到一个最大子图，对应节点数和边数的总和为10 468，根据这个最大覆盖数，来进行摘要覆盖度的计算。当k=5时，top-5的摘要模式集的覆盖数目为8 714，覆盖度为0.832 4，当k=40时，top-40的摘要模式集覆盖数目达到最大覆盖，所以覆盖度为1。覆盖度计算如式(3)所示。Biopt折中系数α取0.7进行实验对比。从实验结果中可以得到，使用subTop-k选取的摘要模式图在覆盖范围方面均优于Biopt；而在在选取摘要数目较少的时候，覆盖范围的优势比较明显。
 |
| 图 6 subTop-k与BiOpt覆盖度对比 |
| 图选项 |
2) luTop-k算法与subTop-k和Biopt算法的对比。
采用luTop-k的方式优化传统的贪心算法，图 7给出了luTop-k与subTop-k、Biopt选取的覆盖性对比。图 7a、7b、7c分别是数据集Caida、Yago和Stanford的实验结果。同样的，采用最大覆盖数目来进行覆盖度的计算。取α=0.7的Biopt作为实验对比。luTop-k的覆盖性比subTop-k的覆盖性弱一些，但优于Biopt。同样的，随着摘要数目的增多，覆盖性逐渐接近于最大覆盖。
 |
| 图 7 luTop-k与subTop-k和Biopt的覆盖度对比 |
| 图选项 |
时间方面如图 8所示。luTop-k的时间开销最少，并且随着摘要选取数目的增多，luTop-k的运算时间小幅增加，可以看到，luTop-k在摘要选取数目较多的时候，加速效果明显。
 |
| 图 8 luTop-k与subTop-k和Bioopt的运行时间对比 |
| 图选项 |
总的来说，subTop-k SPM覆盖性和时间开销2个方面都明显优于Biopt；在牺牲一定覆盖性的情况下，luTop-k能够获得更少的时间开销。
3.4 Top-k SPM实际案例以Yago数据集为例，分别采用subTop-k、Biopt算法挖掘top-2的摘要模式集，结果如图 9所示。使用subTop-k挖掘的摘要模式集如{P1, P2}所示，其的覆盖度为0.696 3；使用Biopt挖掘的摘要模式集如{P3, P4}所示，其覆盖度为0.379 7。圈节点中的数字表示节点ID，旁边的数字是该节点的标签ID。
 |
| 图 9 Yago数据集上的Top-k SPM实际案例 |
| 图选项 |
4 结论高效提取知识图谱模式信息，并形成摘要模式，对于提升知识图谱的知识检索、挖掘质量具有重要研究意义。本文提出了一种新的知识图谱摘要模式挖掘方法。该方法将知识图谱的摘要模式挖掘问题建模为一个次模函数优化问题，并基于Pregel编程模型进行摘要模式判定和质量度量，进而基于贪心算法进行Top-k摘要模式挖掘。在真实的知识图谱数据上将本文的方法与已有方法进行了实验对比，从模式摘要集质量、算法运行时间两方面验证了本文方法的优势和有效性。
基于本文工作，将来拟在以下2个方面继续开展研究工作：带标签层次信息的摘要模式挖掘和针对动态知识图谱的摘要模式挖掘均是需要研究的课题。
参考文献
| [1] | QIAN J W, LI X Y, ZHANG C H, et al. Social network de-anonymization and privacy inference with knowledge graph model[J]. IEEE Transactions on Dependable and Secure Computing, 2017. DOI:10.1109/TDSC.2017.2697854 |
| [2] | SHI B X, WENINGER T. Discriminative predicate path mining for fact checking in knowledge graphs[J]. Knowledge-Based Systems, 2016, 104: 123-133. DOI:10.1016/j.knosys.2016.04.015 |
| [3] | SHI L X, LI S J, YANG X R, et al. Semantic health knowledge graph:Semantic integration of heterogeneous medical knowledge and services[J]. BioMed Research International, 2017, 2858423. |
| [4] | 王萍.网络环境下的领域知识挖掘[D].上海: 华东师范大学, 2010. WANG P. Domain knowledge mining in network environments[D]. Shanghai: East China Normal University, 2010. (in Chinese) http://cdmd.cnki.com.cn/Article/CDMD-10269-2010197471.htm |
| [5] | 陈池, 王宇鹏, 李超, 等. 面向在线教育领域的大数据研究及应用[J]. 计算机研究与发展, 2014, 51(S1): 67-74. CHEN C, WANG Y P, LI C, et al. The research and application of big data in the field of online education[J]. Journal of Computer Research and Development, 2014, 51(S1): 67-74. (in Chinese) |
| [6] | SANG S T, YANG Z Z, WANG L, et al. SemaTyP:A knowledge graph based literature mining method for drug discovery[J]. BMC Bioinformatics, 2018, 19(1): 193-193. |
| [7] | KEMMAR A, LEBBAH Y, LOUDNI S. Interval graph mining[J]. International Journal of Data Mining, Modelling and Management, 2018, 10(1): 1-22. DOI:10.1504/IJDMMM.2018.089629 |
| [8] | 高俊平, 张晖, 赵旭剑, 等. 面向维基百科的领域知识演化关系抽取[J]. 计算机学报, 2016, 39(10): 2088-2101. GAO J P, ZHANG H, ZHAO X J, et al. Evolutionary relation extraction for domain knowledge in Wikipedia[J]. Chinese Journal of Computers, 2016, 39(10): 2088-2101. DOI:10.11897/SP.J.1016.2016.02088 (in Chinese) |
| [9] | SONG Q, WU Y H, DONG X L. Mining summaries for knowledge graph search[C]//Proceedings of 2016 IEEE International Conference on Data Mining. Barcelona, Spain: IEEE, 2016: 1215-1220. |
| [10] | BABAI L. Graph isomorphism in quasipolynomial time[extended abstract] [C]//Proceedings of the 48th Annual ACM Symposium on Theory of Computing. Cambridge, USA: ACM, 2016: 684-697. |
| [11] | SAMSI S, GADEPALLY V, HURLEY M, et al. Static graph challenge: Subgraph isomorphism[C]//Proceedings of 2017 IEEE High Performance Extreme Computing Conference. Waltham, USA: IEEE, 2017: 1-6. |
| [12] | KRAUSE A, GOLOVIN D. Submodular function maximization[M]//BORDEAUX L, HAMADI Y, KOHLI P. Tractability. Cambridge: Cambridge University Press, 2014: 71-104. |
| [13] | DVO?áK W, HENZINGER M, WILLIAMSON D P. Maximizing a Submodular function with viability constraints[J]. Algorithmica, 2017, 77(1): 152-172. |
| [14] | MA S, CAO Y, FAN W F, et al. Capturing topology in graph pattern matching[J]. Proceedings of the VLDB Endowment, 2011, 5(4): 310-321. DOI:10.14778/2095686 |
| [15] | MALEWICZ G, AUSTERN M H, BIK A J C, et al. Pregel: A system for large-scale graph processing[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. Indianapolis, USA: ACM, 2010: 135-146. |
| [16] | ELSEIDY M E, ABDELHAMID P, SKIADOPOULOS S, et al. GraMi:Frequent subgraph and pattern mining in a single large graph[J]. Proceedings of the VLDB Endowment, 2014, 7(7): 517-528. DOI:10.14778/2732286 |
