王 藝，王 英

（西南大學(xué) 計(jì)算機(jī)與信息科學(xué)學(xué)院，重慶 400715）

0 概述

知識(shí)圖譜是基于語義技術(shù)的大規(guī)模語義圖知識(shí)庫(kù)［1-2］。截至2019年3月關(guān)聯(lián)開放數(shù)據(jù)云（Linked Open Data Cloud）已有1 239個(gè)數(shù)據(jù)集和16 147條鏈接，均以資源描述框架（Resource Description Framework，RDF）三元組形式對(duì)數(shù)據(jù)進(jìn)行描述［3］。例如，F(xiàn)acebook的開放內(nèi)容協(xié)議［4］、谷歌的知識(shí)圖譜［5］、DBpedia［6］、Wikidata［7］等知識(shí)庫(kù)，其包含的三元組已達(dá)數(shù)百萬條，甚至上億條。語義圖廣泛應(yīng)用在不同領(lǐng)域［2］，如教育領(lǐng)域已相繼啟動(dòng)關(guān)聯(lián)開放數(shù)據(jù)（Linked Open Data，LOD）項(xiàng) 目mEducator［8］、Open University［9］、LAK Dataset［10］等，旨在共享教育數(shù)據(jù)（如課程數(shù)據(jù)、統(tǒng)計(jì)數(shù)據(jù)、教育資源（視頻和文檔等））。

由于語義圖的規(guī)模巨大、結(jié)構(gòu)復(fù)雜且缺乏標(biāo)準(zhǔn)模式，用戶及應(yīng)用程序開發(fā)人員面臨理解、使用等難題。語義圖概要（Semantic Graph Summarization，SGS）是解決該難題的技術(shù)，也是當(dāng)前語義圖領(lǐng)域的研究熱點(diǎn)［11］。SGS 將大規(guī)模語義圖壓縮為一個(gè)縮略圖，保留原有信息的基礎(chǔ)上壓縮其規(guī)模。SGS 依賴于一系列技術(shù)，包括有向圖特征提取、統(tǒng)計(jì)方法、模式挖掘、代數(shù)結(jié)構(gòu)等。例如，基于形式概念分析（Formal Concept Analysis，F(xiàn)CA）［12］的語義圖概要方法［13-15］是一種利用代數(shù)結(jié)構(gòu)構(gòu)建語義圖概要的方法。通過定義語義圖中的相應(yīng)元素為形式概念，并建立概念之間的偏序關(guān)系形成一個(gè)偏序格。

雖然各種SGS 方法提供了針對(duì)大規(guī)模語義圖的概要模型，能夠大幅提升存儲(chǔ)和查詢效率。由于語義圖規(guī)模巨大，使得計(jì)算語義圖概要開銷增大，尤其當(dāng)語義圖數(shù)據(jù)在固定周期更新后，需要重新計(jì)算語義圖概要。

為提高針對(duì)大型語義圖SGS 的計(jì)算效率問題，本文提出一種基于本體分割的SGS 方法。根據(jù)一定標(biāo)準(zhǔn)將語義圖分割生成多個(gè)子圖，以達(dá)到降低原語義圖規(guī)模的目的。同時(shí)利用FCA 方法計(jì)算每個(gè)語義子圖的SGS，使所有語義子圖的SGS 構(gòu)成原圖的概要。

1 相關(guān)工作

語義圖以RDF 三元組形式存儲(chǔ)，由于缺乏標(biāo)準(zhǔn)模式，大規(guī)模語義圖結(jié)構(gòu)復(fù)雜，使得提升查詢、使用效率、理解語義圖成為當(dāng)前亟需解決的難題。SGS 通過對(duì)語義圖進(jìn)行壓縮生成原語義圖的結(jié)構(gòu)和模式，以解決大規(guī)模語義圖的使用問題［11］。當(dāng)前SGS 方法主要分為基于圖結(jié)構(gòu)的方法和基于代數(shù)結(jié)構(gòu)的方法。

1）基于圖結(jié)構(gòu)的方法

根據(jù)RDF 三元組所形成有向圖的結(jié)構(gòu)，對(duì)圖中的節(jié)點(diǎn)進(jìn)行劃分或提取形成概要節(jié)點(diǎn)，所有概要節(jié)點(diǎn)及相應(yīng)的邊構(gòu)成原語義圖概要。文獻(xiàn)［16］提出節(jié)點(diǎn)間的“強(qiáng)”和“弱”等價(jià)關(guān)系，將等價(jià)的節(jié)點(diǎn)歸納為一個(gè)節(jié)點(diǎn)，進(jìn)而形成語義圖的熵圖，即概要圖。文獻(xiàn)［17］提出一種稱為k-概要圖的方法，通過對(duì)語義圖節(jié)點(diǎn)集合進(jìn)行劃分得到k個(gè)子集，每個(gè)子集作為一個(gè)概要節(jié)點(diǎn)。概要節(jié)點(diǎn)間的邊設(shè)置了權(quán)重，描述原語義圖中概要節(jié)點(diǎn)之間邊的數(shù)量。文獻(xiàn)［18］定義類節(jié)點(diǎn)的中心度和頻率，以確定本體模式（類及類之間的層次關(guān)系）中類的重要性。中心度通過計(jì)算類所關(guān)聯(lián)屬性邊的權(quán)重獲取；頻率用于衡量類在各本體中的使用比率。選取k個(gè)最重要的類及其相關(guān)的類作為本體模式概要。文獻(xiàn)［19］提出一種d-概要，描述語義圖不超過d步鄰接節(jié)點(diǎn)的關(guān)聯(lián)模式，語義圖的所有d-概要即是語義圖概要。通過定義d-概要的信息量指標(biāo)，基于頻繁子圖挖掘技術(shù)，提出計(jì)算k個(gè)最大化信息量的d-概要算法。

2）基于代數(shù)結(jié)構(gòu)的方法

利用FCA 構(gòu)建語義圖的代數(shù)結(jié)構(gòu)，生成概念格作為語義圖的概要。概念格本質(zhì)是概念之間的偏序關(guān)系。文獻(xiàn)［13］提出一種基于FCA 的模型——特征集格（Characteristic Set Lattice，CSL）。根據(jù)三元組（s，p，o）的主語和謂語實(shí)體生成特征集概念，進(jìn)而形成特征集格，實(shí)現(xiàn)對(duì)語義圖的概要。文獻(xiàn)［14］中FCA 被用于對(duì)語義圖類節(jié)點(diǎn)和屬性邊進(jìn)行分類，分別形成類節(jié)點(diǎn)集合與屬性邊集合上的偏序集，最后生成模式概念格作為語義圖的概要。文獻(xiàn)［15］提出一種擴(kuò)展的FCA 模型——G-FCA，增加了概念格中對(duì)語義圖三元組賓語實(shí)體的描述功能。

上述兩類SGS 方法均能在壓縮原語義圖規(guī)模的同時(shí)保留某些關(guān)鍵信息，實(shí)現(xiàn)幫助用戶理解及提升查詢效率的目的。目前語義圖規(guī)模巨大，包含的三元組已達(dá)到數(shù)百萬，甚至上億條，使得計(jì)算語義圖概要的開銷巨大。例如，基于FCA 概要生成算法的時(shí)間復(fù)雜度為O（N3）［13］，其中N=max｛|S|，|P|｝，S為圖中RDF 三元組的主語節(jié)點(diǎn)集合，P為屬性集合。文獻(xiàn)［16］提出基于等價(jià)劃分節(jié)點(diǎn)的方法，其時(shí)間復(fù)雜度為O（|VI|?（|VI|+|P|2）），其中：VI為語義圖的實(shí)例節(jié)點(diǎn)集合；P為屬性集合。文獻(xiàn)［19］提出基于模式挖掘的方法，其時(shí)間復(fù)雜度為O（Ns?|V|?|E|），其中：Ns為概要的規(guī)模，即概要中包含的節(jié)點(diǎn)和邊數(shù)；V為語義圖的節(jié)點(diǎn)集合；E為邊集合。因此，對(duì)于大型語義圖中上述兩類SGS 方法的時(shí)間復(fù)雜度較高，當(dāng)語義圖數(shù)據(jù)在固定周期更新后，上述SGS 方法需要重新計(jì)算概要圖。因此，SGS 方法的效率亟需進(jìn)一步提升。

基于本體分割的CSL 概要方法如圖1 所示。首先利用本體分割算法對(duì)語義圖的節(jié)點(diǎn)進(jìn)行劃分，進(jìn)而生成擴(kuò)展子圖。本體分割的目的是將大規(guī)模本體分割為多個(gè)子本體，以解決本體查詢、維護(hù)、重用等問題［20-22］。基于網(wǎng)絡(luò)模型的本體分割方法將本體視為有向圖，依據(jù)其結(jié)構(gòu)進(jìn)行劃分，最終得到多個(gè)子圖，即子本體。例如，文獻(xiàn)［23］將本體模式轉(zhuǎn)化為依賴關(guān)系圖，基于依賴關(guān)系的強(qiáng)弱，將圖的節(jié)點(diǎn)集進(jìn)行自動(dòng)劃分再生成連通的子圖。該方法的優(yōu)勢(shì)在于其劃分過程使用大型網(wǎng)絡(luò)分析工具Pajek［24］的提取線島（Line Island）功能，時(shí)間復(fù)雜度控制在，其中n為圖的節(jié)點(diǎn)數(shù)。語義圖的本質(zhì)就是本體，因此利用本體分割方法對(duì)大型語義圖進(jìn)行分割是可行的。其次針對(duì)每個(gè)由分割生成的擴(kuò)展子圖，基于FCA 構(gòu)造相應(yīng)的格概要。所有子圖的概要組成了原語義圖的概要。

圖1 基于本體分割的CSL 概要Fig.1 CSL summary based on ontology partition

SGS 方法是直接生成語義圖的概要（如圖1虛線箭頭所示），而本文是利用本體分割算法先劃分語義圖，再構(gòu)造各語義子圖的概要。SGS 方法的復(fù)雜度主要由計(jì)算等價(jià)、相似節(jié)點(diǎn)、計(jì)算元素間的偏序產(chǎn)生，而本文方法經(jīng)過分割步驟，針對(duì)語義子圖進(jìn)行計(jì)算概要圖，大幅度降低了計(jì)算SGS 的時(shí)間消耗。雖然本體分割步驟有一定的計(jì)算開銷，但其復(fù)雜度可控制在，使得計(jì)算SGS 的總體效率高于一般SGS 方法。

2 基于本體分割的SGS

2.1 語義圖的CSL 概要

設(shè)G=（V，E，P，λ）是一個(gè)語義圖，其中：V=I∪L∪B，I為URI的集合；L為字面量集合；B為空白節(jié)點(diǎn)集合。E=｛（u，v）|u，v∈V｝是屬性邊的集合。λ是標(biāo)號(hào)函數(shù)，，其中：（P）為屬性集合的冪集。GI=（VI，EI，PI，λI）是語義圖G的實(shí)例圖，其中VI?V是所有實(shí)例、字面量和空白節(jié)點(diǎn)構(gòu)成的集合，EI?E是VI之間的關(guān)系。

定義1（形式上下文）表示為X=（S，PI，R），其中S是所有GI中三元組主語構(gòu)成的集合，稱為實(shí)體集合，PI是GI中所有三元組屬性構(gòu)成的集合，R是S和PI中元素的關(guān)系，即R=｛（s，p）|?o，（s，p，o）∈GI｝。

定義2（特征集合）給定形式上下文，對(duì)任意s∈S，CS（s）=｛p|?o，（s，p，o）∈GI｝，CS（s）是實(shí)體s的特征集合。

定義3（特征集概念）給定形式上下文，c=（S?，T）被稱為一個(gè)特征集概念，需滿足以下條件：1）S??S；2）T?PI；3）對(duì)任意的s∈S?，CS（s）=T。

令C表示X中所有的特征集概念集合，則|C|是X中特征集概念的個(gè)數(shù)，其取值范圍為：1≤|C|≤min｛|VI|，。若|C|=1，表 明?vi，vj∈VI，且vi≠vj，均 有CS（vi）=CS（vj），即GI中所有實(shí)例有相同的特征集合。若，表明?vi，vj∈VI，且vi≠vj。當(dāng)時(shí)，CS（vi）≠CS（vj），即不同的實(shí)例有不同的特征集合；當(dāng)時(shí)，不同實(shí)例的不同特征集合達(dá)到最大值。因此，|C|的數(shù)值描述了語義圖數(shù)據(jù)的規(guī)范性，數(shù)值越小，則語義圖數(shù)據(jù)越規(guī)范；反之，語義圖數(shù)據(jù)越不規(guī)范。

例1語義圖的形式上下文及特征集格如圖2 所示。由英國(guó)學(xué)術(shù)公開數(shù)據(jù)服務(wù)［8］提供的LOD 數(shù)據(jù)如圖2（a）。X=（S，PI，R），其中S=｛BU，RVC，UR，HC，PA｝，PI=｛pu，gi，gr，fn，bn，lo，sn｝，從圖2（a）可以看出，矩陣顯示了關(guān)系R，“×”表示實(shí)體和屬性之間有關(guān)系。例如，與RVC實(shí)例有關(guān)的關(guān)系為：（RVC，pn），（RVC，gi），（RVC，sn）。實(shí)體RVC 的特征集合CS（RVC）=｛pn，gi，sn｝。圖2（a）包含的特征集概念集合C=｛c1，c2，c3，c4，c5｝，其中c1=（｛BU｝，｛pn，gi，gr，fn，bn，sn｝），c2=（｛RVC｝，｛pn，gi，gr｝），c3=（｛UR｝，｛pn，gi，gr，bn，lo｝），c4=（｛HC｝，｛pn，gr，bn，sn｝），c5=（｛PA｝，｛pn，gi，gr，fn｝）。本例中，特征集合數(shù)|C|=|VI|=5，即不同的實(shí)例有不同的特征集合，表明該語義圖數(shù)據(jù)不規(guī)范。

設(shè)?為特征集概念元素T之間的包含關(guān)系，則（C，?）是一個(gè)偏序集。一般情況下，由于缺乏最大元和最小元，該偏序集不是格。為了使（C，?）成為一個(gè)格，需要增加兩個(gè)元素到C中，分別是：（?，PI）和（?，?），其中（?，PI）為格的最大元，（?，?）為格的最小元。該偏序格被稱為特征集格CSL。

定義4（CSL 概要）給定語義圖G，設(shè)（C，?）為特征集概念集合上定義的偏序集。令C?=C∪（?，PI）∪（?，PI），則（C?，?）為一個(gè)偏序格，該偏序格稱為語義圖G的CSL 概要。

當(dāng)|C|=1時(shí)，語義圖數(shù)據(jù)是規(guī)范的，CSL概要只有|C|+2=3 個(gè)元素：（?，PI），（VI，CS（VI））和（?，?）。當(dāng)，CSL 概要包含了|C|+2 個(gè)元素。因此，數(shù)據(jù)的規(guī)范性可由CSL 概要包含的元素反映，數(shù)據(jù)越規(guī)范，CSL 概要包含的元素越少，反之則越多。

例2例1 中的（C，?）是一個(gè)偏序集，其誘導(dǎo)的格如圖2（b）所示。該格是圖2（a）所示LOD 數(shù)據(jù)的CSL 概要，包含|C|+2=7 個(gè)元素。

圖2 語義圖的形式上下文及特征集格Fig.2 Formal context and characteristic set lattice of semantic graph

2.2 語義圖分割

語義圖分割是通過劃分大型語義圖為規(guī)模合適的子圖，從而達(dá)到提高語義圖概要計(jì)算效率的目的。

定義5（語義圖分割）設(shè)GI=（VI，EI，PI，λI）是實(shí)例圖，π=｛V1，V2，…，Vs｝為GI的一個(gè)分割，需滿足3 個(gè)條件：1）?≠Vi?VI；2）Vi∩Vj=?；3）

定義6（語義圖的擴(kuò)展子圖）設(shè)GI=（VI，EI，PI，λI）是G=（V，E，P，λ）的實(shí)例圖，π=｛V1，V2，…，Vs｝為GI的分割，稱Gi=（Wi，Ei，Pi，λ）（i=1，2，…，s）為Vi所誘導(dǎo)的擴(kuò)展子圖，需滿足3 個(gè)條件：1）Wi=Vi∪VBi，其中VBi=｛v|?u∈Vi，（u，v）∈E｝為邊界節(jié)點(diǎn)集合；2）Ei=｛（u，v）|（u，v）∈E且u，v∈Vi｝；3）Pi=｛p|λ（u，v）=p且u，v∈Vi｝。

上述定義是關(guān)于語義圖的分割，其本質(zhì)是對(duì)語義圖節(jié)點(diǎn)集合進(jìn)行劃分。集合的劃分方案數(shù)較多，選取合適的劃分標(biāo)準(zhǔn)是對(duì)語義圖進(jìn)行合理分割的首要問題。文獻(xiàn)［23］提出一種劃分本體模式的方法，通過將類之間的層次關(guān)系轉(zhuǎn)換為賦權(quán)圖（又稱依賴圖），再進(jìn)行圖的線島劃分。該劃分算法的本質(zhì)是將依賴緊密的節(jié)點(diǎn)劃分在一個(gè)塊中。由于本文考慮的是大型語義圖的實(shí)例圖劃分，無法直接使用文獻(xiàn)［23］所提出的算法，因此改進(jìn)了該本體模式劃分算法。

首先將語義實(shí)例圖轉(zhuǎn)換為依賴圖；其次根據(jù)依賴圖將節(jié)點(diǎn)集合劃分為線島，作為節(jié)點(diǎn)的分割；最后計(jì)算擴(kuò)展子圖。

定義7（語義圖的依賴圖）給定GI=（VI，EI，PI，λI）是 實(shí)例 圖，有向圖=（VI，ED，we）是 依賴圖，其中：ED為依賴圖的邊集合；we為邊上的權(quán)重集合。若（vi，vj）∈EI，則（vi，vj）∈ED且（vj，vi）∈ED。每條邊（vi，vj）有預(yù)設(shè)權(quán)重，它的值由其關(guān)聯(lián)的屬性確定（默認(rèn)值為1）。對(duì)于任意的（vi，vj）∈ED，其依賴圖的權(quán)重w（vi，vj）如式（1）所示：

定義7 中每條邊的預(yù)設(shè)權(quán)重用來描述不同屬性的重要性，可由用戶定義，其默認(rèn)值為1。若所有預(yù)設(shè)權(quán)重為1，并注意到依賴圖的所有邊都是對(duì)稱出現(xiàn)的，則式（1）可簡(jiǎn)化為式（2），其中d+（vi）表示vi的出度，如式（2）所示：

式（1）和式（2）計(jì)算了節(jié)點(diǎn)vi到vj的依賴強(qiáng)度，其原理是基于社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)洞理論中比例強(qiáng)度關(guān)系網(wǎng)絡(luò)的相關(guān)結(jié)論［25］。以式（2）為例，若節(jié)點(diǎn)vi只與vj鄰接，則vi完全依賴于vj，這時(shí)w（vi，vj）=1；若節(jié)點(diǎn)vi與包括vj的k個(gè)節(jié)點(diǎn)鄰接，則vi依賴于vj的程度與其出度成反比，即w（vi，vj）=1/k。因此，式（1）及式（2）體現(xiàn)了節(jié)點(diǎn)之間的依賴強(qiáng)弱程度。在后面的本體分割步驟中，這樣的權(quán)重設(shè)置可以將依賴緊密的節(jié)點(diǎn)劃分在一個(gè)分塊中。

定義8（依賴圖的線島）設(shè)是依賴圖，Ls?VI是一個(gè)線島當(dāng)且僅當(dāng)Ls能誘導(dǎo)一個(gè)的連通子圖，存在一個(gè)的生成樹，滿足：

例3語義圖分割過程及擴(kuò)展子圖如圖3 所示。從圖3 可以看出，一個(gè)語義實(shí)例圖GI，包含9 個(gè)三元組，9 個(gè)實(shí)體。首先將GI轉(zhuǎn)換為依賴關(guān)系圖。設(shè)所有邊的預(yù)設(shè)權(quán)重為1，根據(jù)式（2）可得依賴圖各邊的權(quán)重。節(jié)點(diǎn)間的依賴關(guān)系和權(quán)重。例如，以節(jié)點(diǎn)v4為起點(diǎn)的4 條邊的權(quán)重為w（v4，v1）、w（v4，v2）、w（v4，v3）、w（v4，v5），根據(jù)式（2）其權(quán)重均為0.25，表示v4依賴于v1、v2、v3、v5每個(gè)節(jié)點(diǎn)的程度是0.25。依據(jù)依賴圖權(quán)重所體現(xiàn)的節(jié)點(diǎn)連接強(qiáng)弱，由定義8 可將語義圖的節(jié)點(diǎn)劃分為兩個(gè)節(jié)點(diǎn)集：V1=｛v1，v2，v3，v4｝和V2=｛v5，v6，v7，v8，v9｝。由該節(jié)點(diǎn)的劃分可按定義6 得到相應(yīng)的擴(kuò)展子圖G1和G2（注意到G2包含一個(gè)邊界節(jié)點(diǎn)v5）。

圖3 語義圖分割過程及擴(kuò)展子圖Fig.3 Semantic graph segmentation process and extended sub-graphs

2.3 基于本體分割的CSL 概要

基于本體分割的CSL 概要包括如下定義：

定義9（基于本體分割的CSL 概要）設(shè)GI=（VI，EI，PI，λI）是語義圖G的實(shí)例圖，π=｛V1，V2，…，Vs｝為GI的分塊，Gi（i=1，2，…，s）為Vi對(duì)應(yīng)的擴(kuò)展子圖。由Gi定義的FC 為Xi=（Si，Pi，Ri），則針對(duì)每個(gè)Xi可構(gòu)造相應(yīng)的CSL：Li（i=1，2，…，s）。由各子圖的CSL 構(gòu)成的集合L=｛L1，L2，…，Ls｝為語義圖G的概要。

例4語義圖經(jīng)分割為兩個(gè)擴(kuò)展子圖G1和G2，根據(jù)2.2 節(jié)的方法，可分別產(chǎn)生L1和L2為G的CSL 概要。G1的特征集概念為c1=（｛v3｝，｛p3，p4｝）和c2=（｛v4｝，｛p1，p2，p3｝），相應(yīng)CSL 為L(zhǎng)1=｛（（?，?），c1），（（?，?），c2），（c1，（?，P1）），（c2，（?，P1））｝；G2的特征集概念為c3=（｛v5｝，｛p5，p6｝）和c4=（｛v9｝，｛p1，p2｝），相應(yīng)的CSL 為L(zhǎng)2=｛（（?，?），c3），（（?，?），c4），（c3，（?，P2）），（c4，（?，P2））｝，其中P1=｛p1，p2，p3p4｝，P2=｛p1，p2，p5p6｝。

設(shè)X=（S，PI，R）為由GI定義的FC，則該語義圖的CSL 概要大小為|S|+2，其中2 是添加的最大元和最小元。當(dāng)|S|較大時(shí)，構(gòu)造CSL 所花時(shí)間和空間復(fù)雜度較高。因此，針對(duì)整個(gè)語義圖，構(gòu)造CSL 時(shí)間復(fù)雜度相當(dāng)高。本體分割后使得|Si|遠(yuǎn)小于|S|，從而大幅度提升了CSL 的構(gòu)造效率。

3 算法分析

3.1 算法步驟

算法1 描述了基于本體分割方法計(jì)算語義圖G的CSL 概要的主要步驟。

算法1 的第1 步對(duì)輸入的語義圖文件進(jìn)行解析，可使用RDFLib 庫(kù)的parse 函數(shù)完成解析，其結(jié)果G為三元組構(gòu)成的有向圖。第2～5 步是從G中提取實(shí)例圖GI。其中，第2 步初始化GI為有向圖，第3～5 步中，對(duì)每個(gè)三元組（s，p，o），若屬性p不是rdf：type，則表明該三元組是實(shí)例之間的關(guān)系，故加入到GI中。第6～10 步生成GI的依賴圖。第6 步初始化為有向圖。第7～10 步是對(duì)于GI中的每個(gè)節(jié)點(diǎn)u，對(duì)其所有鄰接的節(jié)點(diǎn)v，增加邊（u，v）到依賴圖中，且相應(yīng)邊的權(quán)重we=1/w，其中w為u的出度。第11 步根據(jù)依賴圖對(duì)節(jié)點(diǎn)進(jìn)行劃分，得到劃分π，由s個(gè)分塊｛V1，V2，…，Vs｝構(gòu)成。Partition 函數(shù)使用了Pajek的“劃分”功能，其中劃分選擇方法為線島。第12～19步，根據(jù)節(jié)點(diǎn)劃分結(jié)果生成每個(gè)劃分塊Vi的擴(kuò)展子圖ExGi。對(duì)于Vi中的每個(gè)節(jié)點(diǎn)u，若u的出度為0，則將u加入ExGi中；若u的出度不為0，則對(duì)u的所有鄰接節(jié)點(diǎn)v，將邊（u，v）加入ExGi中。第20～21 步，計(jì)算每個(gè)擴(kuò)展子圖的CSL 概要Li，ComputeLattice 函數(shù)的任務(wù)是生成特征集概念形成的偏序格。本文采用文獻(xiàn)［13］的算法實(shí)現(xiàn)該偏序格的計(jì)算。

3.2 算法時(shí)間復(fù)雜度分析及比較

3.2.1 算法1 時(shí)間復(fù)雜度

算法1 主要分為5 個(gè)任務(wù)：1）提取語義圖的實(shí)例圖GI；2）生 成GI的依賴圖；3）生成節(jié)點(diǎn)劃分π；4）計(jì)算所有劃分塊的擴(kuò)展子圖ExGi；5）計(jì)算每個(gè)ExGi的CSL 概要Li。

任務(wù)1 的時(shí)間復(fù)雜度為O（|P|），其中|P|為語義圖屬性集合的基數(shù)。任務(wù)2 的時(shí)間復(fù)雜度為O（|VI|?Δ），其中|VI|是實(shí)例圖GI的節(jié)點(diǎn)集合基數(shù)，Δ為GI的節(jié)點(diǎn)最大度。任務(wù)3 使用Pajek 工具完成劃分功能，其所有算法的時(shí)間復(fù)雜度最高為，其中n為圖的節(jié)點(diǎn)數(shù)。因此，利用Pajek 生成實(shí)例圖GI的節(jié)點(diǎn)集合劃分π=｛V1，V2，…，Vs｝，時(shí)間復(fù)雜度最高為。任務(wù)4 的時(shí)間復(fù)雜度為O（|VI|?Δ+），其中Δ+是GI節(jié)點(diǎn)的最大出度。任務(wù)5 的時(shí)間復(fù)雜度為O（|P|?|Cm|2），其中|Cm|=max｛|C|，|C2|，…，|Cs|｝是所有擴(kuò)展子圖的特征集概念數(shù)最大值。在一般情況下，|P|和Δ 均遠(yuǎn)小于|VI|，且|Ci|≤|Vi|。綜上所述，算法1 的時(shí)間復(fù)雜度為O（|P|?|Cm|2）。

3.2.2 算法時(shí)間復(fù)雜度對(duì)比分析

為了與語義圖概要類似方法和標(biāo)準(zhǔn)方法進(jìn)行對(duì)比，本文基于FCA 的概要［13］和基于語義圖節(jié)點(diǎn)等價(jià)劃分的概要方法［16］（基于熵圖的概要）作為算法時(shí)間復(fù)雜度比較對(duì)象。

基于FCA 的概要方法時(shí)間復(fù)雜度為O（N3），其中：N=max｛|S|，|P|｝；S為語義圖中RDF 三元組主語節(jié)點(diǎn)集合；P為屬性集合?；陟貓D的概要方法通過確定節(jié)點(diǎn)間等價(jià)關(guān)系，進(jìn)而對(duì)節(jié)點(diǎn)集合進(jìn)行劃分形成概要節(jié)點(diǎn)，并計(jì)算概要節(jié)點(diǎn)間的屬性邊，從而生成概要圖。該方法時(shí)間復(fù)雜度為O（|VI|?（|VI|+|P|2））。

從3.2.1 節(jié)可知，本文所提算法的復(fù)雜度為O（|P|?|Cm|2）。經(jīng)過本體分割后，|Cm|的數(shù)值控制在較小的范圍，對(duì)于大型語義圖，|Cm|的值遠(yuǎn)小于|VI|、|V|和|P|，因此相比上述兩種概要方法，算法1 具有較高的效率和可擴(kuò)展性。

3.2.3 語義圖數(shù)據(jù)結(jié)構(gòu)敏感性分析

基于FCA 的概要方法和基于熵圖的概要方法對(duì)語義圖數(shù)據(jù)規(guī)范性敏感，而算法1 對(duì)語義圖數(shù)據(jù)規(guī)范性不敏感。

基于FCA 的概要方法對(duì)數(shù)據(jù)規(guī)范性敏感，當(dāng)數(shù)據(jù)規(guī)范時(shí)，即|C|=1，其概要圖只包含一個(gè)概要節(jié)點(diǎn)，時(shí)間復(fù)雜度為O（|V|）；當(dāng)數(shù)據(jù)完全不規(guī)范時(shí)，即|C|=min，概要圖包含|C|個(gè)概要節(jié)點(diǎn)，時(shí)間復(fù)雜度為O（N3）（N=max｛|V|，|P|｝）。

基于熵圖的概要方法對(duì)數(shù)據(jù)規(guī)范性敏感，當(dāng)數(shù)據(jù)規(guī)范時(shí)，即|C|=1，則所有實(shí)例節(jié)點(diǎn)都是等價(jià)的，概要圖只有一個(gè)概要節(jié)點(diǎn)，時(shí)間復(fù)雜度是O（|E|），其中E為語義圖屬性邊的集合；當(dāng)數(shù)據(jù)完全不規(guī)范時(shí)，即|C|=min，則每個(gè)實(shí)例為獨(dú)立的概要節(jié)點(diǎn)，時(shí)間復(fù)雜度達(dá)到最大，即O（|VI|?（|VI|+|P|2））。

算法1 的時(shí)間復(fù)雜度取決于|P|和|Cm|，經(jīng)過本體分割步驟，|Cm|控制在合理范圍，因此算法1 對(duì)數(shù)據(jù)的規(guī)范程度不敏感。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 數(shù)據(jù)集

本文使用的數(shù)據(jù)集如表1 所示，包括南安普頓大學(xué)提供的LOD［26］數(shù)據(jù)集（數(shù)據(jù)集I）和Berlin SPARQL Benchmark（BSBM）［27-28］數(shù)據(jù)集（數(shù)據(jù)集II）。數(shù)據(jù)集I 包含南安普頓大學(xué)相關(guān)數(shù)據(jù)，例如校歷、教學(xué)樓信息、校內(nèi)餐飲、停車場(chǎng)、公開課視頻、在線培訓(xùn)課程等與該校相關(guān)信息。數(shù)據(jù)以RDF/XML、Turtle、JSON 格式發(fā)布。數(shù)據(jù)集II 是電商產(chǎn)品數(shù)據(jù)，包含商家、產(chǎn)品、用品評(píng)價(jià)等信息，是Turtle 格式。該數(shù)據(jù)集由BSBM 提供的程序自動(dòng)生成，可根據(jù)需要生成不同規(guī)模的數(shù)據(jù)集。本文所用BSBM 數(shù)據(jù)集分別為BSBMData 4M（4 017 700個(gè)三元組）和BSBMData 10M（10 044 250 個(gè)三元組）。

表1 數(shù)據(jù)集參數(shù)信息Table 1 Datasets parameters information

4.2 實(shí)驗(yàn)1

實(shí)驗(yàn)1 的目的是驗(yàn)證在計(jì)算CSL 概要時(shí)，基于分割再計(jì)算與不分割直接計(jì)算的效率。實(shí)驗(yàn)1 使用數(shù)據(jù)集I，采用Python語言，單機(jī)環(huán)境Windows10 64位專業(yè)版，CPU Intel 酷睿i7-3740QM 2.7 GHz，內(nèi)存32 GB。

4.2.1 基于本體分割的CSL 概要

本文使用本體分割算法，并調(diào)用Pajek 對(duì)語義圖分割為30 個(gè)分塊，預(yù)處理及分割過程耗時(shí)0.49 s。在數(shù)據(jù)集I 語義圖的分割結(jié)果如圖4 所示。從圖4 可以看出，最小的分塊包含107 個(gè)節(jié)點(diǎn)，最大的分塊包含3 365 個(gè)節(jié)點(diǎn)。在數(shù)據(jù)集I 上語義子圖的CSL 概要如圖5 所示，其包含的特征集概念數(shù)（6～87），以及特征集之間的關(guān)系，即CSL 中哈斯圖的邊（簡(jiǎn)稱特征邊）為（1～178）。

圖4 在數(shù)據(jù)集I 語義圖的分割結(jié)果Fig.4 Segmentation results of semantic graph on the dataset I

圖5 在數(shù)據(jù)集I 語義子圖的CSL 概要Fig.5 CSL summaries of semantic sub-graphs on the dataset I

4.2.2 直接生成的CSL 概要

在數(shù)據(jù)集I 直接生成語義圖的CSL 概要，其概要結(jié)果包含特征集概念371 個(gè)，特征邊共有620 條，程序耗時(shí)17.05 s。

兩種方法的結(jié)果對(duì)比如圖6 所示?；诒倔w分割的CSL 方法總耗時(shí)為10.36 s，是分割耗時(shí)（0.49 s）與分塊計(jì)算CSL 耗時(shí)（9.87 s）之和。直接生成CSL 方法的耗時(shí)17.05 s。從時(shí)間復(fù)雜度分析，基于本體分割的CSL方法明顯優(yōu)于直接生成的CSL 方法，時(shí)間效率提升了39%。由于本體分割可以離線進(jìn)行，如果不包括本體分割耗時(shí)，本文算法的耗時(shí)節(jié)省了42%。從生成的特征集概念和特征邊分析，基于本體分割的CSL 概要生成了更多的特征集概念和特征邊。因此，基于本體分割的CSL 方法明顯提升了CSL 概要的效率。

圖6 兩種概要方法的結(jié)果對(duì)比Fig.6 Results comparison between two summarization methods

4.3 實(shí)驗(yàn)2

將本文方法與其他代表性的語義圖概要方法進(jìn)行比較，以驗(yàn)證本文方法的有效性。本文選取基于熵圖的概要［16］作為比較對(duì)象，其原因是利用節(jié)點(diǎn)等價(jià)關(guān)系進(jìn)行概要生成熵圖，且該方法提供了相應(yīng)的工具，驗(yàn)證數(shù)據(jù)集為公開的BSBM 數(shù)據(jù)集。實(shí)驗(yàn)2 的環(huán)境與實(shí)驗(yàn)1 相同。在不同數(shù)據(jù)集，兩種方法的耗時(shí)情況如圖7 所示。兩種概要情況對(duì)比如表2 所示。在BSBMData 4M 數(shù)據(jù)集，基于本體的分割方法和基于熵圖的方法分別耗時(shí)15 s和21 s，前者效率提升了29%；對(duì)于BSBMData10M數(shù)據(jù)集，基于本體的分割方法和基于熵圖的方法分別耗時(shí)42.5 s 和53 s，前者效率提升了20%。在時(shí)間耗時(shí)方法，基于本體分割的方法要優(yōu)于基于熵圖的概要方法，兩組數(shù)據(jù)效率平均提升25%。說明先對(duì)大規(guī)模數(shù)據(jù)集進(jìn)行劃分后再運(yùn)算能有效提高概要方法的效率。

圖7 在兩種數(shù)據(jù)集上兩種概要方法的耗時(shí)對(duì)比Fig.7 Consumption results comparison between two summarization methods on two kinds of data sets

表2 兩種概要方法參數(shù)對(duì)比Table 2 Parameters comparison of two kinds of summarization methods

從表2 可以看出，在兩個(gè)不同規(guī)模的數(shù)據(jù)集，基于熵圖的概要方法能大幅縮減語義圖節(jié)點(diǎn)數(shù)量。在總體概要結(jié)果上，基于熵圖的概要方法得到了更小的概要圖；在每個(gè)劃分的子圖概要情況上，兩種方法得到了數(shù)量接近的概要節(jié)點(diǎn)。由于BSBM 數(shù)據(jù)集由程序自動(dòng)生成電商產(chǎn)品數(shù)據(jù)規(guī)范性高［28］，每個(gè)產(chǎn)品（實(shí)例）基本都包含商家、產(chǎn)品、用品評(píng)價(jià)等信息（不同的屬性僅有39 個(gè)），兩個(gè)數(shù)據(jù)集規(guī)模不同，但結(jié)構(gòu)相同。由3.2.3 節(jié)算法對(duì)語義數(shù)據(jù)規(guī)范性敏感分析可知，語義圖中大量的節(jié)點(diǎn)是等價(jià)的，且BSBMData 4M 和BSBMData10M 規(guī)模相差雖大，由于數(shù)據(jù)集的規(guī)范性導(dǎo)致概要節(jié)點(diǎn)數(shù)量差距不大。而本文方法對(duì)于數(shù)據(jù)是否結(jié)構(gòu)規(guī)范不敏感，且經(jīng)過分割步驟后，概要圖規(guī)模能夠控制在合理范圍。

5 結(jié)束語

本文提出一種基于本體分割的SGS 方法，將大型的語義圖劃分為多個(gè)子圖，每個(gè)子圖生成特征集格CSL 概要。實(shí)驗(yàn)結(jié)果表明，從算法時(shí)間復(fù)雜度分析，相比基于FCA 的概要和基于熵圖的概要方法，本文方法對(duì)語義數(shù)據(jù)的規(guī)范程度不敏感，具有較好的可擴(kuò)展性。在LOD 數(shù)據(jù)集和BSBM 數(shù)據(jù)集上，本文方法能有效提高概要方法的效率。下一步將對(duì)并行計(jì)算各語義子圖CSL 概要的算法進(jìn)行研究，以進(jìn)一步提升算法效率。