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

0 概述

知识图谱是基于语义技术的大规模语义图知识库^[1-2]。截至2019年3月关联开放数据云（Linked Open Data Cloud）已有1 239个数据集和16 147条链接，均以资源描述框架（Resource Description Framework，RDF）三元组形式对数据进行描述^[3]。例如，Facebook的开放内容协议^[4]、谷歌的知识图谱^[5]、DBpedia^[6]、Wikidata^[7]等知识库，其包含的三元组已达数百万条，甚至上亿条。语义图广泛应用在不同领域^[2]，如教育领域已相继启动关联开放数据（Linked Open Data，LOD）项目mEducator^[8]、Open University^[9]、LAK Dataset^[10]等，旨在共享教育数据（如课程数据、统计数据、教育资源（视频和文档等））。

由于语义图的规模巨大、结构复杂且缺乏标准模式，用户及应用程序开发人员面临理解、使用等难题。语义图概要（Semantic Graph Summarization，SGS）是解决该难题的技术，也是当前语义图领域的研究热点^[11]。SGS将大规模语义图压缩为一个缩略图，保留原有信息的基础上压缩其规模。SGS依赖于一系列技术，包括有向图特征提取、统计方法、模式挖掘、代数结构等。例如，基于形式概念分析（Formal Concept Analysis，FCA）^[12]的语义图概要方法^[13-15]是一种利用代数结构构建语义图概要的方法。通过定义语义图中的相应元素为形式概念，并建立概念之间的偏序关系形成一个偏序格。

虽然各种SGS方法提供了针对大规模语义图的概要模型，能够大幅提升存储和查询效率。由于语义图规模巨大，使得计算语义图概要开销增大，尤其当语义图数据在固定周期更新后，需要重新计算语义图概要。

为提高针对大型语义图SGS的计算效率问题，本文提出一种基于本体分割的SGS方法。根据一定标准将语义图分割生成多个子图，以达到降低原语义图规模的目的。同时利用FCA方法计算每个语义子图的SGS，使所有语义子图的SGS构成原图的概要。

1 相关工作

语义图以RDF三元组形式存储，由于缺乏标准模式，大规模语义图结构复杂，使得提升查询、使用效率、理解语义图成为当前亟需解决的难题。SGS通过对语义图进行压缩生成原语义图的结构和模式，以解决大规模语义图的使用问题^[11]。当前SGS方法主要分为基于图结构的方法和基于代数结构的方法。

1）基于图结构的方法

根据RDF三元组所形成有向图的结构，对图中的节点进行划分或提取形成概要节点，所有概要节点及相应的边构成原语义图概要。文献[16]提出节点间的“强”和“弱”等价关系，将等价的节点归纳为一个节点，进而形成语义图的熵图，即概要图。文献[17]提出一种称为k-概要图的方法，通过对语义图节点集合进行划分得到k个子集，每个子集作为一个概要节点。概要节点间的边设置了权重，描述原语义图中概要节点之间边的数量。文献[18]定义类节点的中心度和频率，以确定本体模式（类及类之间的层次关系）中类的重要性。中心度通过计算类所关联属性边的权重获取；频率用于衡量类在各本体中的使用比率。选取k个最重要的类及其相关的类作为本体模式概要。文献[19]提出一种d-概要，描述语义图不超过d步邻接节点的关联模式，语义图的所有d-概要即是语义图概要。通过定义d-概要的信息量指标，基于频繁子图挖掘技术，提出计算k个最大化信息量的d-概要算法。

2）基于代数结构的方法

利用FCA构建语义图的代数结构，生成概念格作为语义图的概要。概念格本质是概念之间的偏序关系。文献[13]提出一种基于FCA的模型——特征集格（Characteristic Set Lattice，CSL）。根据三元组（s，p，o）的主语和谓语实体生成特征集概念，进而形成特征集格，实现对语义图的概要。文献[14]中FCA被用于对语义图类节点和属性边进行分类，分别形成类节点集合与属性边集合上的偏序集，最后生成模式概念格作为语义图的概要。文献[15]提出一种扩展的FCA模型——G-FCA，增加了概念格中对语义图三元组宾语实体的描述功能。

上述两类SGS方法均能在压缩原语义图规模的同时保留某些关键信息，实现帮助用户理解及提升查询效率的目的。目前语义图规模巨大，包含的三元组已达到数百万，甚至上亿条，使得计算语义图概要的开销巨大。例如，基于FCA概要生成算法的时间复杂度为O（N³）^[13]，其中N=max{|S|，|P|}，S为图中RDF三元组的主语节点集合，P为属性集合。文献[16]提出基于等价划分节点的方法，其时间复杂度为O（|V_I|∙（|V_I|+|P|²）），其中：V_I为语义图的实例节点集合；P为属性集合。文献[19]提出基于模式挖掘的方法，其时间复杂度为O（N_s∙|V|∙|E|），其中：N_s为概要的规模，即概要中包含的节点和边数；V为语义图的节点集合；E为边集合。因此，对于大型语义图中上述两类SGS方法的时间复杂度较高，当语义图数据在固定周期更新后，上述SGS方法需要重新计算概要图。因此，SGS方法的效率亟需进一步提升。

基于本体分割的CSL概要方法如图 1所示。首先利用本体分割算法对语义图的节点进行划分，进而生成扩展子图。本体分割的目的是将大规模本体分割为多个子本体，以解决本体查询、维护、重用等问题^[20-22]。基于网络模型的本体分割方法将本体视为有向图，依据其结构进行划分，最终得到多个子图，即子本体。例如，文献[23]将本体模式转化为依赖关系图，基于依赖关系的强弱，将图的节点集进行自动划分再生成连通的子图。该方法的优势在于其划分过程使用大型网络分析工具Pajek^[24]的提取线岛（Line Island）功能，时间复杂度控制在$ O\left(n\sqrt{n}\right) $，其中n为图的节点数。语义图的本质就是本体，因此利用本体分割方法对大型语义图进行分割是可行的。其次针对每个由分割生成的扩展子图，基于FCA构造相应的格概要。所有子图的概要组成了原语义图的概要。

SGS方法是直接生成语义图的概要（如图 1虚线箭头所示），而本文是利用本体分割算法先划分语义图，再构造各语义子图的概要。SGS方法的复杂度主要由计算等价、相似节点、计算元素间的偏序产生，而本文方法经过分割步骤，针对语义子图进行计算概要图，大幅度降低了计算SGS的时间消耗。虽然本体分割步骤有一定的计算开销，但其复杂度可控制在$ O\left(n\sqrt{n}\right) $，使得计算SGS的总体效率高于一般SGS方法。

2 基于本体分割的SGS 2.1 语义图的CSL概要

设G=（V，E，P，λ）是一个语义图，其中：V=I ∪ L ∪ B，I为URI的集合；L为字面量集合；B为空白节点集合。E={（u，v）|u，v∈V}是属性边的集合。λ是标号函数，λ∶E→℘（P），其中：℘（P）为属性集合的幂集。G_I=（V_I，E_I，P_I，λ_I）是语义图G的实例图，其中V_I⊆V是所有实例、字面量和空白节点构成的集合，E_I⊆E是V_I之间的关系。

定义1（形式上下文）  表示为X=（S，P_I，R），其中S是所有G_I中三元组主语构成的集合，称为实体集合，P_I是G_I中所有三元组属性构成的集合，R是S和P_I中元素的关系，即R={（s，p）|∃o，（s，p，o）∈G_I}。

定义2（特征集合）  给定形式上下文，对任意s∈S，CS（s）={p|∃o，（s，p，o）∈G_I }，CS（s）是实体s的特征集合。

定义3（特征集概念）  给定形式上下文，c=（S'，T）被称为一个特征集概念，需满足以下条件：1）S'⊆S；2）T⊆P_I；3）对任意的s∈ S'，CS（s）=T。

令C表示X中所有的特征集概念集合，则|C|是X中特征集概念的个数，其取值范围为：1≤|C|≤ min{|V_I|，|℘（P_I）|}。若|C|=1，表明∀v_i，v_j∈V_I，且v_i≠v_j，均有CS（v_i）=CS（v_j），即G_I中所有实例有相同的特征集合。若|C|=min{|V_I|，|℘（P_I）|}，表明∀v_i，v_j∈V_I，且v_i≠v_j。当|V_I|≤|℘（P_I）|时，CS（v_i）≠CS（v_j），即不同的实例有不同的特征集合；当|V_I| > |℘（P_I）|时，不同实例的不同特征集合达到最大值|℘（P_I）|。因此，|C|的数值描述了语义图数据的规范性，数值越小，则语义图数据越规范；反之，语义图数据越不规范。

例1  语义图的形式上下文及特征集格如图 2所示。由英国学术公开数据服务^[8]提供的LOD数据如图 2（a）。X=（S，P_I，R），其中S={BU，RVC，UR，HC，PA}，P_I={pu，gi，gr，fn，bn，lo，sn}，从图 2（a）可以看出，矩阵显示了关系R，“×”表示实体和属性之间有关系。例如，与RVC实例有关的关系为：（RVC，pn），（RVC，gi），（RVC，sn）。实体RVC的特征集合CS（RVC）={pn，gi，sn}。图 2（a）包含的特征集概念集合C={c₁，c₂，c₃，c₄，c₅}，其中c₁=（{BU}，{pn，gi，gr，fn，bn，sn}），c₂=（{RVC}，{pn，gi，gr}），c₃=（{UR}，{pn，gi，gr，bn，lo}），c₄=（{HC}，{pn，gr，bn，sn}），c₅=（{PA}，{pn，gi，gr，fn}）。本例中，特征集合数|C|=|V_I|=5，即不同的实例有不同的特征集合，表明该语义图数据不规范。

设⊆为特征集概念元素T之间的包含关系，则（C，⊆）是一个偏序集。一般情况下，由于缺乏最大元和最小元，该偏序集不是格。为了使（C，⊆）成为一个格，需要增加两个元素到C中，分别是：（Ø，P_I）和（Ø，Ø），其中（Ø，P_I）为格的最大元，（Ø，Ø）为格的最小元。该偏序格被称为特征集格CSL。

定义4（CSL概要）  给定语义图G，设（C，⊆）为特征集概念集合上定义的偏序集。令C'=C $ \bigcup $（Ø，P_I）$ \bigcup $（Ø，P_I），则（C'，⊆）为一个偏序格，该偏序格称为语义图G的CSL概要。

当|C|=1时，语义图数据是规范的，CSL概要只有|C|+2=3个元素：（Ø，P_I），（V_I，CS（V_I））和（Ø，Ø）。当|C|=min{|V_I|，|℘（P_I）|}，CSL概要包含了|C|+2个元素。因此，数据的规范性可由CSL概要包含的元素反映，数据越规范，CSL概要包含的元素越少，反之则越多。

例2  例1中的（C，⊆）是一个偏序集，其诱导的格如图 2（b）所示。该格是图 2（a）所示LOD数据的CSL概要，包含|C|+2=7个元素。

2.2 语义图分割

语义图分割是通过划分大型语义图为规模合适的子图，从而达到提高语义图概要计算效率的目的。

定义5（语义图分割）  设G_I=（V_I，E_I，P_I，λ_I）是实例图，π={V₁，V₂，…，V_s}为G_I的一个分割，需满足3个条件：1）Ø≠V_i⊆V_I；2）V_i $ \bigcap $ V_j=Ø；3）$ \underset{i\in \{{\rm{1, 2}}, \cdots , s\}}{\cup }{V}_{i}={V}_{I} $。

定义6（语义图的扩展子图）  设G_I=（V_I，E_I，P_I，λ_I）是G=（V，E，P，λ）的实例图，π={V₁，V₂，…，V_s}为G_I的分割，称G_i=（W_i，E_i，P_i，λ）（i=1，2，…，s）为V_i所诱导的扩展子图，需满足3个条件：1）W_i=V_i∪VB_i，其中VB_i={v|∃u∈V_i，（u，v）∈E}为边界节点集合；2）E_i={（u，v）|（u，v）∈E且u，v∈V_i}；3）P_i={p|λ（u，v）=p且u，v∈V_i}。

上述定义是关于语义图的分割，其本质是对语义图节点集合进行划分。集合的划分方案数较多，选取合适的划分标准是对语义图进行合理分割的首要问题。文献[23]提出一种划分本体模式的方法，通过将类之间的层次关系转换为赋权图（又称依赖图），再进行图的线岛划分。该划分算法的本质是将依赖紧密的节点划分在一个块中。由于本文考虑的是大型语义图的实例图划分，无法直接使用文献[23]所提出的算法，因此改进了该本体模式划分算法。

首先将语义实例图转换为依赖图；其次根据依赖图将节点集合划分为线岛，作为节点的分割；最后计算扩展子图。

定义7（语义图的依赖图）  给定G_I=（V_I，E_I，P_I，λ_I）是实例图，有向图$ {G}_{I}^{{\rm{D}}} $=（V_I，E_D，w^e）是依赖图，其中：E_D为依赖图的边集合；w^e为边上的权重集合。若（v_i，v_j）∈ E_I，则（v_i，v_j）∈E_D且（v_j，v_i）∈ E_D。每条边（v_i，v_j）有预设权重$ {w}_{ij}^{p} $，它的值由其关联的属性确定（默认值为1）。对于任意的（v_i，v_j）∈E_D，其依赖图的权重w（v_i，v_j）如式（1）所示：

$ w({v}_{i}, {v}_{j})=\frac{{w}_{ij}^{{\rm{p}}}+{w}_{ji}^{{\rm{p}}}}{\sum\limits _{k}\left({w}_{ik}^{{\rm{p}}}+{w}_{ki}^{{\rm{p}}}\right)} $

(1)

定义7中每条边的预设权重用来描述不同属性的重要性，可由用户定义，其默认值为1。若所有预设权重为1，并注意到依赖图的所有边都是对称出现的，则式（1）可简化为式（2），其中d⁺（v_i）表示v_i的出度，如式（2）所示：

$ w({v}_{i}, {v}_{j})=\frac{1}{{d}^{+}\left({v}_{i}\right)} $

(2)

式（1）和式（2）计算了节点v_i到v_j的依赖强度，其原理是基于社会网络结构洞理论中比例强度关系网络的相关结论^[25]。以式（2）为例，若节点v_i只与v_j邻接，则v_i完全依赖于v_j，这时w（v_i，v_j）=1；若节点v_i与包括v_j的k个节点邻接，则v_i依赖于v_j的程度与其出度成反比，即w（v_i，v_j）=1/k。因此，式（1）及式（2）体现了节点之间的依赖强弱程度。在后面的本体分割步骤中，这样的权重设置可以将依赖紧密的节点划分在一个分块中。

定义8（依赖图的线岛）  设$ {G}_{I}^{{\rm{D}}} $=（V_I，E_D，w^e）是依赖图，L_s⊆V_I是一个线岛当且仅当L_s能诱导一个$ {G}_{I}^{{\rm{D}}} $的连通子图，存在一个$ {G}_{I}^{{\rm{D}}} $的生成树T=（V_T，E_T，w^e_T），满足：

$ \begin{array}{l}{\rm{m}}{\rm{a}}{\rm{x}}\left\{w\right(v, {v}^{\text{'}})\left|(v, {v}^{\text{'}})\in {E}_{D}\wedge \left(\right(v\in {L}_{s}\wedge {v}^{\text{'}}\right.\notin {L}_{s})\vee \\ (v\notin {L}_{s}\wedge v\in {L}_{s})\left)\right\}<{\rm{m}}{\rm{i}}{\rm{n}}\left\{w\right(u, {u}^{\text{'}}\left)\right|(u, {u}^{\text{'}})\in {E}_{T}\}\end{array} $

(3)

例3  语义图分割过程及扩展子图如图 3所示。从图 3可以看出，一个语义实例图G_I，包含9个三元组，9个实体。首先将G_I转换为依赖关系图。设所有边的预设权重为1，根据式（2）可得依赖图各边的权重。节点间的依赖关系和权重。例如，以节点v₄为起点的4条边的权重为w（v₄，v₁）、w（v₄，v₂）、w（v₄，v₃）、w（v₄，v₅），根据式（2）其权重均为0.25，表示v₄依赖于v₁、v₂、v₃、v₅每个节点的程度是0.25。依据依赖图权重所体现的节点连接强弱，由定义8可将语义图的节点划分为两个节点集：V₁={v₁，v₂，v₃，v₄}和V₂={v₅，v₆，v₇，v₈，v₉}。由该节点的划分可按定义6得到相应的扩展子图G₁和G₂（注意到G₂包含一个边界节点v₅）。

2.3 基于本体分割的CSL概要

基于本体分割的CSL概要包括如下定义：

定义9（基于本体分割的CSL概要）  设G_I=（V_I，E_I，P_I，λ_I）是语义图G的实例图，π={V₁，V₂，…，V_s}为G_I的分块，G_i（i=1，2，…，s）为V_i对应的扩展子图。由G_i定义的FC为X_i=（S_i，P_i，R_i），则针对每个X_i可构造相应的CSL：L_i（i=1，2，…，s）。由各子图的CSL构成的集合L={L₁，L_2，…，L_s}为语义图G的概要。

例4  语义图经分割为两个扩展子图G₁和G₂，根据2.2节的方法，可分别产生L₁和L₂为G的CSL概要。G₁的特征集概念为c₁=（{v₃}，{p₃，p₄}）和c₂=（{v₄}，{p₁，p₂，p₃}），相应CSL为L₁={（（Ø，Ø），c₁），（（Ø，Ø），c₂），（c₁，（Ø，P₁）），（c₂，（Ø，P₁））}；G₂的特征集概念为c₃=（{v₅}，{p₅，p₆}）和c₄=（{v₉}，{p₁，p₂}），相应的CSL为L₂={（（Ø，Ø），c₃），（（Ø，Ø），c₄），（c₃，（Ø，P₂）），（c₄，（Ø，P₂））}，其中P₁={p₁，p₂，p₃ p₄}，P₂={p₁，p₂，p₅ p₆}。

设X=（S，P_I，R）为由G_I定义的FC，则该语义图的CSL概要大小为|S|+2，其中2是添加的最大元和最小元。当|S|较大时，构造CSL所花时间和空间复杂度较高。因此，针对整个语义图，构造CSL时间复杂度相当高。本体分割后使得|S_i|远小于|S|，从而大幅度提升了CSL的构造效率。

3 算法分析 3.1 算法步骤

算法1描述了基于本体分割方法计算语义图G的CSL概要的主要步骤。

算法1  计算语义图的CSL概要

输入  SG //语义图文件，格式可为rdf，ttl，或者nt

输出  L_i（i=1，2，…，s）//L_i是第i个扩展子图的CSL概要

1. G=parse（SG）

//G是三元组构成的有向图

2. G_I=DiGraph（）

//G_I是实例图，初始化其为有向图

3. for（s，p，o）in G：

4. if p！=RDF.type：

5.G_I.add_edge（s，o，label=p）//生成实例图G_I

6. DepG_I=Di.Graph（）

//DepG_I是依赖图

7. for u in G_I.nodes：

8. w=G_I.degree（u）

//w是节点u的总度数

9. for v in G_I.neighbors（u）

//v是u的邻接节点

10.DepG_I.add_edge（u，v，weight=1/w）//生成依赖图的

//边及权重

11. π={V₁，V₂，…，V_s}← Partition（DepG_I，LineIsland）

//利用Pajek的划分功能，分割DepG_I

12. for V_i in π：

13.ExG_i=DiGraph（）//ExG_i是V_i的扩展子图

14. for u in V_i：

15. if G_I.out_degree（u）==0：

16. ExG_i.add_node（u）

17. else：

18. for v in G_I.neighbors（u）：

19. ExG_i.add_edge（u，v）

20. for i=1 to s：

21.L_i← ComputeLattice（ExG_i）//计算扩展子图的CS概要

22. Return L_i（i=1，2，…，s）

算法1的第1步对输入的语义图文件进行解析，可使用RDFLib库的parse函数完成解析，其结果G为三元组构成的有向图。第2~5步是从G中提取实例图G_I。其中，第2步初始化G_I为有向图，第3~5步中，对每个三元组（s，p，o），若属性p不是rdf：type，则表明该三元组是实例之间的关系，故加入到G_I中。第6~10步生成G_I的依赖图$ {G}_{I}^{{\rm{D}}} $。第6步初始化$ {G}_{I}^{{\rm{D}}} $为有向图。第7~10步是对于G_I中的每个节点u，对其所有邻接的节点v，增加边（u，v）到依赖图$ {G}_{I}^{{\rm{D}}} $中，且相应边的权重w_e=1/w，其中w为u的出度。第11步根据依赖图$ {G}_{I}^{{\rm{D}}} $对节点进行划分，得到划分π，由s个分块{V₁，V₂，…，V_s}构成。Partition函数使用了Pajek的“划分”功能，其中划分选择方法为线岛。第12~19步，根据节点划分结果生成每个划分块V_i的扩展子图ExG_i。对于V_i中的每个节点u，若u的出度为0，则将u加入ExG_i中；若u的出度不为0，则对u的所有邻接节点v，将边（u，v）加入ExG_i中。第20~21步，计算每个扩展子图的CSL概要L_i，ComputeLattice函数的任务是生成特征集概念形成的偏序格。本文采用文献[13]的算法实现该偏序格的计算。

3.2 算法时间复杂度分析及比较 3.2.1 算法1时间复杂度

算法1主要分为5个任务：1）提取语义图的实例图G_I；2）生成G_I的依赖图$ {G}_{I}^{{\rm{D}}} $；3）生成节点划分π；4）计算所有划分块的扩展子图ExG_i；5）计算每个ExG_i的CSL概要L_i。

任务1的时间复杂度为O（|P|），其中|P|为语义图属性集合的基数。任务2的时间复杂度为O（|V_I|∙Δ），其中|V_I|是实例图G_I的节点集合基数，Δ为G_I的节点最大度。任务3使用Pajek工具完成划分功能，其所有算法的时间复杂度最高为$ O\left(n\sqrt{n}\right) $，其中n为图的节点数。因此，利用Pajek生成实例图G_I的节点集合划分π={V₁，V₂，…，V_s}，时间复杂度最高为$ O\left(\left|{V}_{I}\right|\sqrt{\left|{V}_{I}\right|}\right) $。任务4的时间复杂度为O（|V_I|∙Δ⁺），其中Δ⁺是G_I节点的最大出度。任务5的时间复杂度为O（|P|∙|C_m|²），其中|C_m|=max{|C|，|C₂|，…，|C_s|}是所有扩展子图$ {G}_{I}^{{\rm{E}}} $的特征集概念数最大值。在一般情况下，|P|和Δ均远小于|V_I|，且|C_i|≤|V_i|。综上所述，算法1的时间复杂度为O（|P|∙|C_m|²）。

3.2.2 算法时间复杂度对比分析

为了与语义图概要类似方法和标准方法进行对比，本文基于FCA的概要^[13]和基于语义图节点等价划分的概要方法^[16]（基于熵图的概要）作为算法时间复杂度比较对象。

基于FCA的概要方法时间复杂度为O（N³），其中：N=max{|S|，|P|}；S为语义图中RDF三元组主语节点集合；P为属性集合。基于熵图的概要方法通过确定节点间等价关系，进而对节点集合进行划分形成概要节点，并计算概要节点间的属性边，从而生成概要图。该方法时间复杂度为O（|V_I|∙（|V_I|+|P|²））。

从3.2.1节可知，本文所提算法的复杂度为O（|P|∙|C_m|²）。经过本体分割后，|C_m|的数值控制在较小的范围，对于大型语义图，|C_m|的值远小于|V_I|、|V|和|P|，因此相比上述两种概要方法，算法1具有较高的效率和可扩展性。

3.2.3 语义图数据结构敏感性分析

基于FCA的概要方法和基于熵图的概要方法对语义图数据规范性敏感，而算法1对语义图数据规范性不敏感。

基于FCA的概要方法对数据规范性敏感，当数据规范时，即|C|=1，其概要图只包含一个概要节点，时间复杂度为O（|V|）；当数据完全不规范时，即|C|=min{|V_I|，|℘（P_I）|}，概要图包含|C|个概要节点，时间复杂度为O（N³）（ N=max{|V|，|P|}）。

基于熵图的概要方法对数据规范性敏感，当数据规范时，即|C|=1，则所有实例节点都是等价的，概要图只有一个概要节点，时间复杂度是O（|E|），其中E为语义图属性边的集合；当数据完全不规范时，即|C|=min{|V_I|，|℘（P_I）|}，则每个实例为独立的概要节点，时间复杂度达到最大，即O（|V_I|∙（|V_I|+|P|²））。

算法1的时间复杂度取决于|P|和|C_m|，经过本体分割步骤，|C_m|控制在合理范围，因此算法1对数据的规范程度不敏感。

4 实验与结果分析 4.1 数据集

本文使用的数据集如表 1所示，包括南安普顿大学提供的LOD^[26]数据集（数据集I）和Berlin SPARQL Benchmark（BSBM）^[27-28]数据集（数据集II）。数据集I包含南安普顿大学相关数据，例如校历、教学楼信息、校内餐饮、停车场、公开课视频、在线培训课程等与该校相关信息。数据以RDF/XML、Turtle、JSON格式发布。数据集II是电商产品数据，包含商家、产品、用品评价等信息，是Turtle格式。该数据集由BSBM提供的程序自动生成，可根据需要生成不同规模的数据集。本文所用BSBM数据集分别为BSBMData 4M（4 017 700个三元组）和BSBMData 10M（10 044 250个三元组）。

4.2 实验1

实验1的目的是验证在计算CSL概要时，基于分割再计算与不分割直接计算的效率。实验1使用数据集I，采用Python语言，单机环境Windows10 64位专业版，CPU Intel酷睿i7-3740QM 2.7 GHz，内存32 GB。

4.2.1 基于本体分割的CSL概要

本文使用本体分割算法，并调用Pajek对语义图分割为30个分块，预处理及分割过程耗时0.49 s。在数据集I语义图的分割结果如图 4所示。从图 4可以看出，最小的分块包含107个节点，最大的分块包含3 365个节点。在数据集I上语义子图的CSL概要如图 5所示，其包含的特征集概念数（6~87），以及特征集之间的关系，即CSL中哈斯图的边（简称特征边）为（1~178）。

4.2.2 直接生成的CSL概要

在数据集I直接生成语义图的CSL概要，其概要结果包含特征集概念371个，特征边共有620条，程序耗时17.05 s。

两种方法的结果对比如图 6所示。基于本体分割的CSL方法总耗时为10.36 s，是分割耗时（0.49 s）与分块计算CSL耗时（9.87 s）之和。直接生成CSL方法的耗时17.05 s。从时间复杂度分析，基于本体分割的CSL方法明显优于直接生成的CSL方法，时间效率提升了39%。由于本体分割可以离线进行，如果不包括本体分割耗时，本文算法的耗时节省了42%。从生成的特征集概念和特征边分析，基于本体分割的CSL概要生成了更多的特征集概念和特征边。因此，基于本体分割的CSL方法明显提升了CSL概要的效率。

4.3 实验2

将本文方法与其他代表性的语义图概要方法进行比较，以验证本文方法的有效性。本文选取基于熵图的概要^[16]作为比较对象，其原因是利用节点等价关系进行概要生成熵图，且该方法提供了相应的工具，验证数据集为公开的BSBM数据集。实验2的环境与实验1相同。在不同数据集，两种方法的耗时情况如图 7所示。两种概要情况对比如表 2所示。在BSBMData 4M数据集，基于本体的分割方法和基于熵图的方法分别耗时15 s和21 s，前者效率提升了29%；对于BSBMData10M数据集，基于本体的分割方法和基于熵图的方法分别耗时42.5 s和53 s，前者效率提升了20%。在时间耗时方法，基于本体分割的方法要优于基于熵图的概要方法，两组数据效率平均提升25%。说明先对大规模数据集进行划分后再运算能有效提高概要方法的效率。

从表 2可以看出，在两个不同规模的数据集，基于熵图的概要方法能大幅缩减语义图节点数量。在总体概要结果上，基于熵图的概要方法得到了更小的概要图；在每个划分的子图概要情况上，两种方法得到了数量接近的概要节点。由于BSBM数据集由程序自动生成电商产品数据规范性高^[28]，每个产品（实例）基本都包含商家、产品、用品评价等信息（不同的属性仅有39个），两个数据集规模不同，但结构相同。由3.2.3节算法对语义数据规范性敏感分析可知，语义图中大量的节点是等价的，且BSBMData4M和BSBMData10M规模相差虽大，由于数据集的规范性导致概要节点数量差距不大。而本文方法对于数据是否结构规范不敏感，且经过分割步骤后，概要图规模能够控制在合理范围。

5 结束语

本文提出一种基于本体分割的SGS方法，将大型的语义图划分为多个子图，每个子图生成特征集格CSL概要。实验结果表明，从算法时间复杂度分析，相比基于FCA的概要和基于熵图的概要方法，本文方法对语义数据的规范程度不敏感，具有较好的可扩展性。在LOD数据集和BSBM数据集上，本文方法能有效提高概要方法的效率。下一步将对并行计算各语义子图CSL概要的算法进行研究，以进一步提升算法效率。