基于路徑適配的大規(guī)模RDF數(shù)據(jù)子圖匹配算法

胡新苗，林 穗，姜文超,，熊 夢，賀忠堂

（1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006；2.中國科學(xué)院 云計(jì)算產(chǎn)業(yè)技術(shù)創(chuàng)新與育成中心，廣東 東莞 523808）

資源描述框架(Resource Description Framework，RDF)[1]是W3C提出的一種標(biāo)準(zhǔn)元數(shù)據(jù)模型，用于以機(jī)器可讀的方式描述Web資源。RDF數(shù)據(jù)通常被定義為三元組〈s，p，o〉的形式，其中，s(subject)表示主題，p(predicate)表示謂詞，o(object)表示賓語，謂詞表示主題與賓語之間的語義關(guān)系。RDF數(shù)據(jù)集通常以圖的形式表示，圖中的頂點(diǎn)表示主題與賓語，而謂詞被映射到連接兩個(gè)頂點(diǎn)的有向邊，它表示頂點(diǎn)之間的語義關(guān)系。SPARQL是為RDF開發(fā)的查詢語言，可實(shí)現(xiàn)在大規(guī)模RDF數(shù)據(jù)圖中迅速地查找符合條件的結(jié)果，其查詢中的核心問題就是子圖模式匹配[2-3]。換言之，針對RDF圖數(shù)據(jù)的模式匹配過程是對大規(guī)模RDF數(shù)據(jù)圖進(jìn)行搜索并找到同構(gòu)于查詢圖的數(shù)據(jù)子圖的遍歷過程。因此，該問題也可以稱為子圖匹配問題。子圖匹配是圖挖掘中一個(gè)重要的分支，它作為實(shí)現(xiàn)圖數(shù)據(jù)上高效查詢的基本操作，也被廣泛應(yīng)用于社會(huì)安全、社交網(wǎng)絡(luò)和生物化學(xué)等各個(gè)領(lǐng)域的實(shí)際問題中[4-5]。隨著大數(shù)據(jù)時(shí)代的到來，RDF數(shù)據(jù)規(guī)模逐漸增大，語義關(guān)系在RDF數(shù)據(jù)模型中的描述也更加復(fù)雜，隨之查詢過程更加復(fù)雜，查詢效率較低。因此，大規(guī)模圖數(shù)據(jù)[6-8]的子圖匹配問題成為學(xué)術(shù)界和工業(yè)界面臨的挑戰(zhàn)。

大規(guī)模圖數(shù)據(jù)上的子圖匹配問題已被證明是一個(gè)NP問題，Ullmann提出Ullmann算法[9]查找同構(gòu)子圖時(shí)采用深度優(yōu)先搜索方法將其依次找出。Cordella等[10]提出VF2算法，在Ullmann算法的基礎(chǔ)上加入了剪枝操作和搜索匹配，提高了算法運(yùn)行效率。GraphQ算法[11]數(shù)據(jù)鄰接狀態(tài)和深度信息進(jìn)行剪枝操作減少時(shí)間開銷。GADDI算法[12]在過濾備選節(jié)點(diǎn)時(shí)采用了構(gòu)建鄰接辨別子結(jié)構(gòu)距離的方法，利用回溯法得到候選子圖并完成子圖匹配。張碩等[13]提出COPESl算法，采用圖集壓縮組織方法將多個(gè)圖結(jié)構(gòu)化地組織起來，同時(shí)給出一個(gè)基于圖挖掘的索引特征生成方法。TurboISO算法[14]為了減小候選節(jié)點(diǎn)范圍，將查詢圖構(gòu)建成NEC-Tree結(jié)構(gòu)形式，并通過深度優(yōu)先搜索方法進(jìn)行匹配。對于小規(guī)模的單圖或圖集來說，這些方法比較適用，但無法滿足大規(guī)模數(shù)據(jù)圖的子圖匹配的精確性和高效率的需求。

根據(jù)RDF數(shù)據(jù)圖的子圖匹配定義，有2種方法來解決匹配問題[15-16]。一種是利用子圖同構(gòu)的精確RDF圖匹配算法，其思想是將圖G及其標(biāo)簽綁定中所有可能的子圖與模式圖Q進(jìn)行比較并獲取所有候選子圖，然后檢查支配關(guān)系并返回最佳匹配結(jié)果。但是該方法在響應(yīng)時(shí)間上效率不高，可能會(huì)產(chǎn)生大量不必要的中間結(jié)果，需要對Q與G進(jìn)行大量子圖同構(gòu)檢驗(yàn)，其算法復(fù)雜度很高。另一種方法采用近似匹配策略，以減少耗時(shí)的窮舉搜索，該方法適當(dāng)降低子圖同構(gòu)和其他傳統(tǒng)圖相似度量的剛性結(jié)構(gòu)和標(biāo)簽匹配約束。然而，現(xiàn)有的圖匹配算法忽略了RDF圖的許多特性。例如，這些算法在RDF圖中只考慮頂點(diǎn)和邊的相似性，而不考慮頂點(diǎn)和邊之間的結(jié)構(gòu)。更重要的是，這些算法忽略了資源之間的語義關(guān)系，而這些語義關(guān)系對于實(shí)際應(yīng)用中的子圖匹配問題來說至關(guān)重要。

針對以上問題，本文提出基于路徑適配的大規(guī)模RDF數(shù)據(jù)子圖匹配算法。該算法選擇的路徑不是以匹配頂點(diǎn)為基本單元，而是基于路徑索引搜索子圖。首先將模式圖分解為一組從根頂點(diǎn)開始到目的頂點(diǎn)結(jié)束的路徑集；然后將這些路徑與數(shù)據(jù)圖進(jìn)行匹配；并重建與查詢路徑最匹配的候選路徑以生成最終匹配結(jié)果。實(shí)驗(yàn)測試了在不同數(shù)據(jù)集上的路徑索引構(gòu)建時(shí)間以及F-measure值，與Spath算法、Sapper算法和SQM算法相比，算法查詢準(zhǔn)確率更高，且具有更高的查詢效率。

1 基本概念

定義1RDF數(shù)據(jù)圖[1-3]。

RDF數(shù)據(jù)圖G=(VG,EG,LG)，其中，VG是一組有限的頂點(diǎn)，EG?V×V是一組有向邊，LG是一組頂點(diǎn)對應(yīng)的標(biāo)簽集合。

定義2RDF查詢圖[1-3]。

查詢圖Q=(VQ,EQ,LQ)，其中，VQ是查詢圖中頂點(diǎn)的集合，EQ是查詢圖中邊的集合，LQ是查詢圖中頂點(diǎn)對應(yīng)的標(biāo)簽集合。

定義3RDF圖路徑[16]。

在RDF圖的上下文中，不同的路徑表示頂點(diǎn)之間不同的語義關(guān)系。對于一個(gè)RDF圖，它的根頂點(diǎn)是一個(gè)入度為零的頂點(diǎn)，而目標(biāo)頂點(diǎn)是一個(gè)出度為零的頂點(diǎn)。假設(shè)G=(V,E,L)是一個(gè)RDF圖。G中的路徑p被定義為不同頂點(diǎn)的有限序列p=v1,v2,···,vn，其中，vi∈V和(vi,vi+1)∈E且i∈[1,n?1]。因?yàn)镽DF圖的結(jié)構(gòu)中不但有頂點(diǎn)，而且邊也有標(biāo)簽，所以RDF圖的路徑表達(dá)式可以描述為“頂點(diǎn)?邊”交替的序列。

定義4子圖匹配。

給定一個(gè)RDF數(shù)據(jù)圖G和查詢圖Q，子圖匹配查詢由元素(頂點(diǎn)和邊)匹配、結(jié)構(gòu)匹配等部分組成，其答案是一組子圖M，這樣子圖m∈M類似于查詢圖。如圖1所示，圖1(a)表示數(shù)據(jù)圖G，圖1(b)表示查詢圖Q，對于查詢圖Q，數(shù)據(jù)圖G的子圖匹配結(jié)果為(m1,m4,m3,m2)。

圖1 子圖匹配示例Fig.1 Example of subgraph matching

子圖查詢用于識別查詢子圖在RDF數(shù)據(jù)圖中的出現(xiàn)次數(shù)。查詢圖Q=(VQ,EQ,LQ)是一個(gè)RDF圖，其中每個(gè)頂點(diǎn)v∈VQ用標(biāo)簽LQ標(biāo)記。查詢圖指定了數(shù)據(jù)圖G的子圖必須滿足的結(jié)構(gòu)和語義要求，即：子圖查詢以查詢圖Q作為輸入，檢索包含或類似于查詢圖的數(shù)據(jù)圖G，并返回檢索到的圖或由檢索到的圖組成的新圖。

2 基于路徑適配的子圖匹配算法

2.1 路徑適配

雖然樹和圖可以保存更多的結(jié)構(gòu)信息，但它們潛在的龐大規(guī)模和昂貴的剪枝成本，甚至超過了搜索空間剪枝的優(yōu)勢，因此路徑作為合適的索引模式比樹和圖更有優(yōu)勢。為了將數(shù)據(jù)路徑與輸入查詢路徑進(jìn)行比較，并確定哪個(gè)數(shù)據(jù)路徑與查詢路徑最相似，需為路徑定義一個(gè)距離度量，類似于使用編輯操作定義字符串，通過定義路徑編輯距離，即通過編輯操作更改路徑，直到存在與查詢路徑相等的路徑。

定義5編輯操作。

給定一個(gè)RDF路徑，基本的路徑編輯操作包括：替換RDF實(shí)體或文字、替換RDF屬性、刪除一個(gè)RDF實(shí)例或文字、刪除一個(gè)RDF屬性、插入一個(gè)RDF實(shí)例或文字、插入一個(gè)RDF屬性。

定義6編輯路徑。

給定一個(gè)RDF路徑p和一個(gè)編輯序列T=(ω1,ω2,ω3,···,ωn)的編輯操作，編輯路徑T(p)=ωn(···ω2(ω1(p))···)。每個(gè)基本路徑編輯操作ωi被分配一個(gè)特定的代價(jià)c(ωi)。代價(jià)c(ωi)根據(jù)編輯操作的類型和所涉及的RDF元素性質(zhì)而變化。例如，修改頂點(diǎn)標(biāo)簽與頂點(diǎn)插入關(guān)系不大，因?yàn)楹笳咴黾恿寺窂街g的語義距離。顯然，如何確定路徑中元素組件的相似性和定義編輯操作的代價(jià)是關(guān)鍵問題。

將p轉(zhuǎn)化為T(p)的總代價(jià)為c(T)=。換句話說，編輯路徑的代價(jià)是序列T中所有編輯操作代價(jià)的總和?？梢钥闯觯ǔＳ卸鄠€(gè)編輯操作序列將路徑p轉(zhuǎn)換為路徑T(p)，對于路徑編輯距離度量，更傾向于花費(fèi)代價(jià)越小的序列。

定義7路徑編輯距離。

給定兩條路徑p和p'，定義p和p'之間的路徑編輯距離為：dist(p,p')=，Ti是將p轉(zhuǎn)換為p'的路徑編輯操作序列。

2.2 計(jì)算匹配相似度

RDF圖中的每個(gè)元素都依賴于圖的結(jié)構(gòu)。相應(yīng)地，由圖中的一些基本元素組成的子結(jié)構(gòu)(如路徑或子圖)存在的匹配度必須依賴于元素的相對匹配度。例如，路徑存在的匹配度與路徑中每個(gè)元素(頂點(diǎn)和邊)的相對匹配度相關(guān)。

定義8假設(shè)G=(V,E,L)是一個(gè)RDF圖，G′∈G是一個(gè)連通的子圖，它由一組路徑集合P=(p1，p2，···，pn)組成。RDF子圖的匹配度聚合函數(shù)是一個(gè)函數(shù)tm，它給每個(gè)RDF圖G'分配一個(gè)聚合的匹配值 ?G′，這代表了G'的相似度，它被定義為

?G′=tm(?p1,?p2，···，?pn)

其中，tm是一個(gè)特定于應(yīng)用的聚合函數(shù)，選擇最小值作為目標(biāo)函數(shù)，即總體匹配度值 ?G′為路徑產(chǎn)生的匹配度的最小值。

RDF圖的不同路徑表示RDF圖中頂點(diǎn)之間的不同關(guān)系。RDF圖的路徑可以由更多RDF三元組組成，作為“頂點(diǎn)?邊”交替序列。因此，可以通過聚合組成匹配路徑的三元組集合的匹配度來計(jì)算匹配路徑的絕對匹配度。

2.3 子圖匹配算法

根據(jù)上述定義，數(shù)據(jù)路徑與輸入查詢路徑之間的路徑編輯距離越小，兩者越相似，可以通過計(jì)算路徑上對齊來計(jì)算圖的相似度。查詢圖Q在數(shù)據(jù)圖G上的匹配結(jié)果就是構(gòu)成G的連通分量的Q的所有路徑的匹配集。為了提高在大規(guī)模RDF數(shù)據(jù)圖中的子圖匹配準(zhǔn)確性和效率，提出基于路徑適配的子圖匹配算法，算法主要分為3個(gè)階段：

(1)數(shù)據(jù)預(yù)處理：建立圖索引結(jié)構(gòu)。采用上下文感知的路徑索引，以獲取關(guān)于圖路徑的詳細(xì)信息，實(shí)現(xiàn)對候選匹配項(xiàng)的高效檢索。為了提取到達(dá)給定頂點(diǎn)V的所有路徑的集合，使用廣度優(yōu)先搜索從根開始探索G。為了提高基于路徑的查詢處理效率，使用反向路徑(目標(biāo)頂點(diǎn)到根頂點(diǎn))表達(dá)式以跳過代價(jià)昂貴的圖遍歷，并將存儲的所有根到當(dāng)前頂點(diǎn)的對應(yīng)路徑表達(dá)式構(gòu)建B+樹索引。路徑索引包含了RDF圖中從當(dāng)前頂點(diǎn)到所有根的路徑表達(dá)式，此外，通過相應(yīng)聚合函數(shù)，預(yù)先計(jì)算并存儲每個(gè)路徑的匹配度。

(2)查詢處理：查詢處理由路徑分解、尋找候選路徑和拼接候選路徑3個(gè)子階段組成，圖2給出了在RDF數(shù)據(jù)圖G上查詢圖Q的基本過程。具體步驟如下：①路徑分解。將查詢圖劃分為一組路徑Q={q1,q2,···,qk}，為便于重構(gòu)答案子圖，采用k-partition交集圖保存圖查詢的結(jié)構(gòu)信息。在k-partition交集圖中，一個(gè)頂點(diǎn)對應(yīng)于一個(gè)查詢路徑，而一條邊(qi,qj)表示路徑qi和qj路徑至少共享一個(gè)公共頂點(diǎn)，即路徑qi可以和qj連接，且它們之間至少有一個(gè)交點(diǎn)。②尋找候選路徑。對于每個(gè)查詢路徑q∈Q，使用路徑之間的編輯距離dist(q,p)查詢路徑和候選路徑過濾后的匹配集。③拼接候選路徑。使用圖探索算法重構(gòu)候選路徑以獲得完整的結(jié)果匹配，通過在k-partition交集圖中執(zhí)行消息傳遞，得到的是包含在G中的一組近似子圖。然后，根據(jù)路徑編輯距離對實(shí)際匹配的答案進(jìn)行排序。

圖2 查詢處理階段圖Fig.2 Query processing phase diagram

(3)圖匹配處理：通過選擇最相關(guān)的路徑并將之與每個(gè)集合的路徑編輯距離最低的路徑連接起來，生成完整的查詢匹配。連接條件是路徑p和p'之間的連接謂詞的數(shù)量等于路徑q和q'之間的謂詞的數(shù)量，其中q和q'分別是對應(yīng)于包含p和p'的集合的路徑。

通過以上描述，可以得到基于路徑適配的子圖匹配算法過程如下：

在匹配過程中，從一條路徑的匹配開始，逐步增加連接路徑的匹配。一旦獲得了候選集，圖搜索算法將通過連接候選集中最相近的路徑的方法來執(zhí)行。首先將結(jié)果集ApproximateAnswersSet初始化為一個(gè)空集，如果連接過程中沒有結(jié)果加入，則答案集ans輸出空集。如果不能生成k個(gè)答案，并且集合候選集CandidateSet不為空，通過選擇并組合每個(gè)集合候選集的編輯距離按遞增順序排列的路徑，得到前k個(gè)答案。然后將答案集進(jìn)行初始化，并選擇k-partition交集圖中與現(xiàn)有路徑重疊頂點(diǎn)(連接謂詞)最多的路徑q。選擇路徑q對應(yīng)的集合cn，并從cn中取出頂層路徑p。將路徑q添加到訪問的匹配路徑集合V中，在答案集ans中加入p。通過廣度優(yōu)先搜索遍歷獲得完整的答案，如函數(shù)BFS-visit中所示。最后，將完整答案包含在近似答案集中。通過使用該策略，如果不能找到查詢圖Q的k個(gè)近似答案，則該過程停止。

2.4 算法復(fù)雜性

在數(shù)據(jù)預(yù)處理中，需要通過遍歷RDF圖G來構(gòu)建路徑索引結(jié)構(gòu)。對于每個(gè)頂點(diǎn)V，采用一種優(yōu)化的方法實(shí)現(xiàn)，即從根頂點(diǎn)進(jìn)行廣度優(yōu)先搜索遍歷來收集路徑信息。假設(shè)根頂點(diǎn)在G中的平均次數(shù)為d，可以直觀地說明數(shù)據(jù)預(yù)處理階段的時(shí)間復(fù)雜度為O(|V|×d)，|V|為RDF圖G中的頂點(diǎn)數(shù)，d為最大頂點(diǎn)度。

路徑分解的核心過程本質(zhì)上是廣度優(yōu)先搜索處理。廣度優(yōu)先搜索中每個(gè)頂點(diǎn)最多只排隊(duì)一次，復(fù)雜度是O(|VQ|)。每條邊最多被檢查一次，復(fù)雜度是O(|EQ|)。因此，子步驟的總運(yùn)行時(shí)間為O(|VQ|+|EQ|)，|VQ|和|EQ|分別為查詢圖Q的頂點(diǎn)數(shù)和邊數(shù)。

尋找候選路徑步驟的復(fù)雜度為|P|×O(D)，其中|P|為集合P中查詢路徑的數(shù)量，D為索引檢索到的路徑數(shù)量，在最壞情況下，與數(shù)據(jù)的大小成正比。也就是說，必須執(zhí)行D個(gè)插入到候選集，最多執(zhí)行|P|次。

在查詢匹配步驟中，它最多迭代k次，k是返回答案的數(shù)量。在每次迭代中，都有一次調(diào)用函數(shù)BFSvisit，該函數(shù)探索k-partition交集圖。在最壞的情況下，它的代價(jià)是O(h×D)，因?yàn)樗鼨z查h乘以G中的每條數(shù)據(jù)路徑，其中h是k-partition交集圖的深度。因此該子步驟的復(fù)雜度為O(k×h×D)，通過k次調(diào)用函數(shù)BFS-visit來探索k-partition交集圖，即O(h×D)。

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

本文實(shí)驗(yàn)配置采用Windows10 64位系統(tǒng)，Intel Core(TM)i7-10710U CPU，16 GB內(nèi)存，實(shí)驗(yàn)采用的RDF數(shù)據(jù)集是來自IMDB的真實(shí)子集[16]，利用RDF數(shù)據(jù)構(gòu)造數(shù)據(jù)圖，其中每個(gè)三元組都對應(yīng)一條連接2個(gè)頂點(diǎn)的邊，將每個(gè)頂點(diǎn)增加一個(gè)頂點(diǎn)標(biāo)簽。通過從數(shù)據(jù)圖中隨機(jī)選擇子圖，實(shí)驗(yàn)中使用的查詢圖模式有4種，如圖3所示。圖3(a)為2條路徑的鏈?zhǔn)讲樵兡Ｊ?。圖3(b)是一個(gè)簡單的、高選擇性的星形查詢模式，從中心頂點(diǎn)開始，可以分解為6條路徑。圖3(c)是一個(gè)樹形查詢模式，從根頂點(diǎn)到葉子頂點(diǎn)可以分解為6條路徑。圖3(d)是組成從根頂點(diǎn)到目標(biāo)頂點(diǎn)的查詢路徑的復(fù)合式查詢模式。

圖3 數(shù)據(jù)集模式圖Fig.3 Data set model diagram

針對不同RDF子集進(jìn)行實(shí)驗(yàn)測試，得到整個(gè)數(shù)據(jù)預(yù)處理階段基于路徑的圖索引構(gòu)建時(shí)間和索引路徑的數(shù)量如表1所示。由表1可知，構(gòu)建索引的時(shí)間和路徑數(shù)將會(huì)隨著改變RDF數(shù)據(jù)圖大小而變化，索引時(shí)間的增加幅度小于圖大小的增加幅度。例如，系統(tǒng)用1 563 ms從60 K的3倍數(shù)量創(chuàng)建的數(shù)據(jù)圖構(gòu)建147 265條索引路徑，盡管60 K圖比10 K圖大6倍，但索引時(shí)間平均增加了2倍。

表1 索引構(gòu)建對比Table 1 Index building comparison

為了驗(yàn)證該子圖匹配算法的有效性與合理性。對于每個(gè)查詢，對有效性的評價(jià)基準(zhǔn)分別進(jìn)行測試：(1)查準(zhǔn)率(P)表示返回的相關(guān)解與系統(tǒng)找到的所有解的比值；(2)查全率(R)表示返回的相關(guān)解決方案(以RS為單位)占所有解決方案的比值；(3)F-measure(F-M)結(jié)合了Precision和Recall的結(jié)果，反映了算法的實(shí)際效果，即F-M=(2PR)/(R+P)。

通過將RDF圖路徑適配算法與Spath算法、Sapper算法和SQM算法在數(shù)據(jù)集上的有效性進(jìn)行對比，且對比3種算法的R值、P值和F-M值，結(jié)果如表2所示。

表2 路徑適配算法與其他算法比較Table 2 The path adaptation algorithm compared with other algorithms

通過表2測試數(shù)據(jù)可知，本文算法在查準(zhǔn)率R值、查全率P值和F-measure值這3個(gè)數(shù)據(jù)方面都優(yōu)于其他3種算法，且能夠更好地利用結(jié)構(gòu)信息的F-measure值。同時(shí)，所有算法的查全率R都會(huì)降低結(jié)果的質(zhì)量，因?yàn)?，隨著路徑長度的增加，尋找候選路徑的搜索空間也會(huì)增加，這會(huì)導(dǎo)致返回更多的中間匹配項(xiàng)。

4 結(jié)語

為了提高在大規(guī)模圖數(shù)據(jù)上查詢圖的查詢效率，本文提出了一種基于路徑適配的大規(guī)模RDF數(shù)據(jù)圖上的子圖匹配算法，即基于路徑的解決方案。該方案將查詢圖分解為一組可能重疊的路徑，找到單個(gè)路徑的匹配項(xiàng)，并根據(jù)特定的上下文條件選取具有良好選擇性的可能匹配項(xiàng)子集作為候選項(xiàng)。候選路徑進(jìn)一步連接在一起，以幫助恢復(fù)查詢圖，以最終完成圖查詢處理。最后將該方法與3種代表性圖匹配算法在數(shù)據(jù)集上進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，該方法在路徑索引構(gòu)建、有效性方面優(yōu)于其他方法。