近年来，在网络信息技术的支撑下，以维基百科、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=〈V_P, E_P〉为模式图(pattern graph)，表示标签及标签之间的关系；V_P是标签集，E_P是标签关系边集。

与一般图数据不同，知识图谱含有大量实体类型信息，且实体之间的关系多样、复杂。为有效展示知识图谱并提供不同兴趣视角的模式信息，需要对图谱模式的复杂程度进行限制，因此，首先定义受限模式图。

定义1  受限模式图：给定整数参数d和b。图模式P为一个受限模式图，仅当d_P≤d，|P|≤b，其中：d_P为模式P中节点之间最长路径长度，|P|为P的节点数和边数的总和。

不是任何受限模式图均为有意义的摘要模式。一个摘要模式P是对知识图G中节点及节点关系的概括描述，因此，可基于图模式匹配方法来建立受限模式图是否为合法摘要模式的判定准则。一般地，图模式匹配方法有基于图同构的模式匹配^[10-11]以及基于图模拟的模式匹配。图同构方法要求模式图和数据图在节点类型和节点拓扑关系严格一致情况下才能判定为匹配，匹配判定是NP-hard的，对于大规模知识图谱而言，判定求解困难。图模拟要求模式图和数据图节点类型一致，但不要求节点之间拓扑关系严格保持一致，其判定是多项式可解的，因此，本文基于图模拟匹配来定义合法摘要模式的判定准则，具体地，摘要模式由下面的定义2给出。

定义2  摘要模式：给定知识图G=〈V, E, L〉，模式图P=〈V_P, E_P〉，如果存在二元关系R(P, G)⊆V_P×V，∀l∈V_P和每一个知识图节点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所示。

给定一个摘要模式P，用R(P, G)在知识图G上决定的子图大小来度量G_P的质量，为此，定义摘要模式P的覆盖度。

定义3  摘要模式的覆盖度：给定知识图G和模式摘要P。所有满足二元关系R的元组(l, v)∈R(P, G)中的实体节点v及其连接边构成的G的子图记为G_P，则模式摘要P的覆盖度记为cov(G_P, G)并定义如下：

$ {\rm{cov}}\left( {{G_P}, G} \right) = \frac{{\left| {{G_P}} \right|}}{G}. $

(1)

其中：|G_P|表示子图G_P边和节点的总数目，|G|表示图G的边和节点数的总和。

例1  给定参数d=2, b=5，图 1中的3个图模式满足受限模式条件。其中只有P₁、P₂满足摘要的定义，P₃中标签为A的节点，其子节点的标签为B，而图G中，不存在这样的关系，所以P₃不满足摘要的定义。摘要P₁根据定义3，由P₁与G的二元关系R(P₁, G)={(C, c₁)，(C, c₂)，(C, c₃)，(D, d₁)，(D, d₂)，(D, d₃)，(F, f₁)，(F, f₂)，(F, f₃)}，得到对应图G中节点：c₁、c₂、c₃、d₁、d₂、d₃、f₁、f₂、f₃，并根据这些节点之间的关系构成子图G_P1，|G_P1|=18, |G|=31。同理，|G_P2|=12，cov(G_P1, G)=$\frac{{18}}{{31}} > {\mathop{\rm cov}} \left( {{G_{{P_2}}}, G} \right) = \frac{{12}}{{31}}$，所以，P₁的覆盖度高于P₂。

由定义3可知，模式P的覆盖度越高，P对知识图谱数据的概括能力就越强。同时，2个摘要模式P₁和P₂的覆盖子图G_P1和G_P2的节点集、边集也可能存在交集，即摘要模式可能存在覆盖交叠。于是，如何获得概括能力强，相互不冗余的摘要模式集成为需要解决的问题，并将其描述为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)

其中：S={P₁, P₂, …, P_k}为含k个受限摘要模式组成的集合，G_Pi为摘要模式P_i在知识图G上的覆盖子图，|G_Pi|为图G_Pi的节点数和边数的总和。不难看出，Top-k SPM等价于一个最大k覆盖问题，因此是NP-hard的。然而，Top-k SPM问题的目标函数是满足次模性，这为高效近似求解该问题提供了理论基础。

定义5  次模函数^[12]：给定集合U，函数F: 2^U→ℝ⁺是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，元素P_j∈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} $

同理，$\sigma (T|{P_j}) = \frac{{\left| {{G_{{P_j}}} - \left( {\bigcup\limits_{i = 1}^m {{G_{{P_i}}}} } \right)} \right|}}{{\left| G \right|}} \ge 0$。由此可得：σ(S|P_j)≥σ(T|P_j)≥0。综上，F(S∪{P_j})-F(S)≥F(T∪{P_j})-F(T)，因此，F(S)满足次模性。

需要说明的是：与文[9]中将摘要模式挖掘问题定义为一个双目标函数优化问题不同，本文将Top-k SPM定义为一个次模函数最大化问题。由此，挖掘过程中无需人为指定折中因子。次模函数优化过程中寻求边际效用最大化(marginal utility maximization)的数学性质也决定了结果集由高覆盖度且相互之间非冗余的模式组成，保证了求解质量。虽然Top-k SPM是NP-hard的，但由文[13]结论可知，贪心算法求解Top-k SPM可得到保证近似下界$1 - \frac{1}{e}$的近似解。

2 Top-k摘要模式挖掘算法

首先介绍给定知识图G的一个受限模式图P，基于Pregel编程模型的判定P为合法摘要模式的判定方法，以及求P在G上的覆盖子图G_P的方法。基于此，进一步介绍基于贪心算法挖掘Top-k摘要模式集，并讨论基于lazy update的挖掘算法加速方法。

2.1 摘要模式判定及其覆盖子图求解

给定受限模式P和知识图G，判定P为G上的合法摘要模式的关键是：确定二元关系R(P，G)是否存在，进一步地，如果P为G上的合法摘要模式，那么，P在G上的覆盖子图G_P依赖于求解R(P，G)中的所有二元元组。由定义2可知，求解R(P，G)的过程是一个基于图模拟判定P是否匹配G的过程。由文[14]可知，判定算法是多项式计算复杂度的，即O((|V_P|+|V|)(|E_P|+|E|))。

首先介绍判定知识图G中任意节点u∈V匹配的方法。由定义2可知，判定节点u∈V是否匹配取决于：如果u的标签是l∈V_p，且l是p中的叶子节点，则u是匹配的；如果v的标签为l，且在p中l有子结点l₁^′，l₂^′，…，l_c^′，那么，v在G中具有l₁^′，l₂^′，…，l_c^′标签的子节点，且v与其l_i^′(i=1, 2，…, c)标签子节点之间的边与边(l, l_i^′)的标签一致，则v匹配。

基于节点匹配判定，进一步可判定P是否为合法摘要模式，具体地，将P中节点进行拓扑排序，并生成一个由P决定的标签拓扑序列，记为l₁，l₂，…，l_t。对知识图G中的节点，按照P中标签拓扑序列的逆序判定相应标签的节点是否匹配，最终，如果G中存在l₁，l₂，…，l_t标签的匹配节点，那么，P被判定为一个合法的摘要模式。在对P进行判定过程中，被判定为匹配的节点及与这些节点相邻的具有相应标签的边即构成覆盖子图G_P。

由于实际应用中的知识图谱含有大量节点和边，判定P和求解G_P是耗时的。为高效地判定、求解，本文提出了一种基于Pregel编程模型^[15]的并行化的摘要模式判定及覆盖子图的求解方法。

Pregel编程模型是一种以节点为中心的并行迭代式图计算模型。基本思想是：整个计算分为多个超步(super step)迭代执行。在每一个超步，图中节点并行地接收、合并其邻居节点发来的消息，根据消息更新节点自身的状态，然后向其邻居节点发送新消息。当图中没有消息传递时，整个Pregel过程结束。基于Pregel编程模型的摘要模式判定及覆盖子图的求解算法分为2个步骤：

步骤1  初始化：首先，为记录G中节点的匹配状态，以及记录覆盖子图信息，对于G中每个节点v设置2个变量，分别为：匹配状态m_v，覆盖节点集C_v。m_v是个Bool变量(T为true，F为false)，m_v=true，判定节点v匹配。C_v是集合，用来存储与节点v相关的已匹配的节点集。由定义2可知，G中标签为P中叶子标签的所有节点均为已匹配节点，例如图 2中，对于给定的P来说，G中的f₁、f₂、f₃均为匹配节点，于是有m_f1=T，m_f2=T，m_f3=T，以及C_f1={f₁}，C_f2={f₂}等等。其他v是否匹配取决于其是否具有已匹配的相应标签的子节点，例如图 2中，c₁是否匹配取决于d₁或者d₂是否匹配。于是，给定P，可初始化m_v，例如，m_c1=m_d1∨m_d2 (即节点c₁匹配，仅当其任意一个D标签子节点匹配)，m_d1=m_f1等.由于c₁、d₁等非叶子标签节点在Pregel消息传递前无法判定是否匹配，因此C_c1=Ø，C_d1=Ø等。

步骤2  Pregel消息传递：Pregel过程的消息从已判定为匹配的叶子标签节点开始。在图 2中，从f₁、f₂、f₃开始。每个已匹配的节点根据P中规定的边标签向其父节点发消息，消息内容为：节点ID，节点标签，例如，f₁向d₁发送消息msg(f₁, F)。需要注意的是，f₂不会向d₃发送消息，因为边(f₂, d₃)与P中F到D的边标签不同。接收到消息的节点将消息进行合并，例如d₂同时接收到msg(f₂, F)，msg(f₃, F)，将它们按标签合并为msg({f₂, f₃}, F)，进而调用节点消息处理函数vprog处理合并后的消息，具体地，根据消息更新匹配判定逻辑表达式，例如，对于d₂节点，其逻辑表达式为：m_d2=m_f2∨m_f3，由接收到的消息可知f₂、f₃已匹配，因此，更新逻辑表达式为：m_d2=T∨T，于是，d₂判定为匹配。图 2中的Pregel过程经历2个超步(在图中用不同有向线段表示)完成消息传递。最终，c₁、c₂都是被判定为匹配C的标签点，因此模式P为一个合法的摘要模式，同时，其覆盖子图由所有灰色节点及相应边组成。

2.2 挖掘算法

Top-k摘要模式挖掘算法的基本思想是：首先，基于频繁子图模式挖掘算法，例如GRAMI^[16]，得到模式子图，并选择满足d_P≤d, |P|≤b_P条件的子图作为受限模式图；其次，对每个受限模式图P，采用节2.1描述的Pregel过程判定P，且如果P为合法模式，则同时求解其覆盖子图G_P；再次，根据式(2)中目标函数F(S)，每次选取F(S)最大边际效用的P加入S，直到|S|=k；最后，算法输出S作为Top-k摘要模式挖掘结果。图 3中算法1给出了Top-k摘要模式挖掘算法的完整描述。

算法1的时间复杂度分析如下：基于Pregel模型判定P，求解其覆盖子图G_P，时间复杂度为O((|V|+|V_P|)(|E|+|E_P|))^[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^[12]策略对贪心算法进行优化。本文节3实验结果表明:该策略可有效提升算法执行效率。

基于lazy update策略的Top-k摘要模式挖掘算法的基本思想是：给定摘要提取的数目k、图G和基于图G的频繁模式子图挖掘结果集P，首先对P中的所有模式子图做筛选，满足约束性图模式条件的图模式进行模式匹配，不满足约束性图模式条件的则舍去。并分别计算剩余模式子图对应的次模函数边际效益值，按照函数值做非递增排序，函数值最大对应的摘要模式图P添加到摘要集S中；在选第二元素及其以后的过程中，首先更新F值最大的模式子图的函数值，若更新之后该子图对应的函数F仍然最大，那么该元素即为当前最优值，直接添加到集合S中，如果F不是最大值，那么就按照贪心算法重复此部分的计算并排序；按照该步骤进行计算，直至S的元素个数达到k个。算法如图 4所示。

算法2是算法1的加速算法，最坏的情况和算法2的时间复杂度一样，为O(|P|(|V|+|V_P|)(|E|+|E_P|)+|P|); 而最好的情况是，每次选取元素的时候只用计算一次，所以最优情况下的时间复杂度为O(|P|(|V|+|V_P|)(|E|+|E_P|)+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)

其中：S表示算法得到的解集，是模式图的一个集合；${G_S} = \bigcup\limits_{{s_i} \in S}^k {{G_{{s_i}}}} $表示S中包含的所有摘要模式的覆盖范围，是所有模式图匹配到的子图总和。挖掘得到的所有图模式，对图G具有一个最大覆盖数${G_{{P_{{\rm{sum}}}}}} = \bigcup\limits_{{p_i} \in P}^m {{G_{{P_i}}}} $，G_Psum表示整个挖掘的图模式集P中所有图模式匹配到的子图的并集。由此可以看出，cov越大，解集的覆盖性就越好，cov最大值为1。

3) 实验环境

本文提出的算法均采用scala语言实现，所有实验在一台16 GB内存、8核(8个Intel 3.4 GHz CPU)的实验室PC机上完成。Apache Spark采用2.0版本。

3.2 实验内容

如表 1所示，频繁度为图模式的挖掘标准，使用GRAMI挖掘工具根据该图模式挖掘得到相应的数目的图模式。模式图最大值和最小值(是单个图模式边数和节点数总和的最大值或最小值)用于衡量一个图模式的大小，挖掘得到的所有图模式对图G做图模式匹配得到的所有子图，存在一个对原图数据的最大覆盖，即式(3)中的G_Psum，最大覆盖数为|G_Psum|。

使用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。随着摘要选取数目的增加，图模式匹配消耗的时间不变，只增加了图模式选取所消耗的时间，故而时间增幅比较小。由此可以看出，传统的频繁模式子图挖掘得到的结果存在大量冗余图模式，通过本文算法筛选，能够挖掘到覆盖能力更强的摘要模式。

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；而在在选取摘要数目较少的时候，覆盖范围的优势比较明显。

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。同样的，随着摘要数目的增多，覆盖性逐渐接近于最大覆盖。

时间方面如图 8所示。luTop-k的时间开销最少，并且随着摘要选取数目的增多，luTop-k的运算时间小幅增加，可以看到，luTop-k在摘要选取数目较多的时候，加速效果明显。

总的来说，subTop-k SPM覆盖性和时间开销2个方面都明显优于Biopt；在牺牲一定覆盖性的情况下，luTop-k能够获得更少的时间开销。

3.4 Top-k SPM实际案例

以Yago数据集为例，分别采用subTop-k、Biopt算法挖掘top-2的摘要模式集，结果如图 9所示。使用subTop-k挖掘的摘要模式集如{P₁, P₂}所示，其的覆盖度为0.696 3；使用Biopt挖掘的摘要模式集如{P₃, P₄}所示，其覆盖度为0.379 7。圈节点中的数字表示节点ID，旁边的数字是该节点的标签ID。

4 结论

高效提取知识图谱模式信息，并形成摘要模式，对于提升知识图谱的知识检索、挖掘质量具有重要研究意义。本文提出了一种新的知识图谱摘要模式挖掘方法。该方法将知识图谱的摘要模式挖掘问题建模为一个次模函数优化问题，并基于Pregel编程模型进行摘要模式判定和质量度量，进而基于贪心算法进行Top-k摘要模式挖掘。在真实的知识图谱数据上将本文的方法与已有方法进行了实验对比，从模式摘要集质量、算法运行时间两方面验证了本文方法的优势和有效性。

基于本文工作，将来拟在以下2个方面继续开展研究工作：带标签层次信息的摘要模式挖掘和针对动态知识图谱的摘要模式挖掘均是需要研究的课题。