融合啟發(fā)式和Boosting 的子圖匹配基數(shù)估計(jì)方法

侯文哲，趙 翔

國(guó)防科技大學(xué) 信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)沙410000

隨著網(wǎng)絡(luò)大數(shù)據(jù)的迅速發(fā)展，社交關(guān)系、知識(shí)表示等領(lǐng)域大放異彩。圖數(shù)據(jù)庫(kù)作為一種描述關(guān)系數(shù)據(jù)的天然模型，已成為當(dāng)前海量網(wǎng)絡(luò)數(shù)據(jù)管理的解決范式。因此，圖數(shù)據(jù)管理技術(shù)也成為當(dāng)前的研究熱點(diǎn)。近年，以子圖匹配為代表的圖數(shù)據(jù)上基礎(chǔ)操作的性能得到了巨大提升。但是，一個(gè)完善的高吞吐的圖數(shù)據(jù)庫(kù)系統(tǒng)還應(yīng)具備自適應(yīng)的任務(wù)調(diào)度能力；為了實(shí)現(xiàn)這個(gè)目標(biāo)，圖數(shù)據(jù)庫(kù)系統(tǒng)需要對(duì)系統(tǒng)中的任務(wù)進(jìn)行代價(jià)估計(jì)——特別是對(duì)中間結(jié)果基數(shù)的盡可能準(zhǔn)確估計(jì)，從而優(yōu)化多任務(wù)執(zhí)行的序列與配置。本研究以子圖匹配任務(wù)為例，研究針對(duì)該任務(wù)的基數(shù)估計(jì)的有效方法。

子圖匹配是圖數(shù)據(jù)庫(kù)管理、查詢(xún)等各項(xiàng)工作中的基礎(chǔ)操作。為提高子圖匹配操作的執(zhí)行效率，現(xiàn)有研究對(duì)其執(zhí)行過(guò)程進(jìn)行了有效的剪枝、索引構(gòu)建等優(yōu)化，但精確的子圖匹配問(wèn)題仍然是一個(gè)NP 完全問(wèn)題，隨著待匹配結(jié)點(diǎn)的增多，匹配將難以在有效的時(shí)間內(nèi)完成。若能在匹配執(zhí)行之前就能夠盡可能準(zhǔn)確地估算匹配結(jié)果的基數(shù)，便可幫助實(shí)現(xiàn)對(duì)匹配執(zhí)行過(guò)程和多個(gè)匹配任務(wù)的整體優(yōu)化，對(duì)于提升圖數(shù)據(jù)庫(kù)管理系統(tǒng)的效率和吞吐量意義重大。

當(dāng)前，在關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)領(lǐng)域，學(xué)者已經(jīng)提出一些機(jī)器學(xué)習(xí)的方法和傳統(tǒng)的非機(jī)器學(xué)習(xí)方法來(lái)對(duì)查詢(xún)結(jié)果的數(shù)據(jù)庫(kù)查詢(xún)?nèi)蝿?wù)的基數(shù)進(jìn)行預(yù)測(cè)，而這些方法往往基于數(shù)據(jù)庫(kù)的連接過(guò)程，無(wú)法直接應(yīng)用到以圖為結(jié)構(gòu)的圖數(shù)據(jù)庫(kù)匹配的基數(shù)估計(jì)工作中。另一方面，現(xiàn)有的用于子圖匹配基數(shù)估計(jì)的部分研究依賴(lài)于離線(xiàn)統(tǒng)計(jì)的方法，無(wú)法充分利用圖數(shù)據(jù)中的結(jié)構(gòu)信息，且沒(méi)有一個(gè)適用于多結(jié)點(diǎn)查詢(xún)圖匹配基數(shù)估計(jì)的框架。

鑒于此，本研究旨在設(shè)計(jì)一個(gè)通用方法來(lái)實(shí)現(xiàn)多結(jié)點(diǎn)查詢(xún)圖的預(yù)測(cè)框架，并通過(guò)對(duì)圖數(shù)據(jù)的結(jié)構(gòu)信息建模、編碼，應(yīng)用Boosting 學(xué)習(xí)的思想，實(shí)現(xiàn)魯棒的多結(jié)點(diǎn)子圖在大規(guī)模數(shù)據(jù)圖中匹配基數(shù)的預(yù)測(cè)工作。具體地，提出BoostCard 方法，它首先針對(duì)數(shù)據(jù)圖中結(jié)點(diǎn)的鄰居信息建模，將結(jié)點(diǎn)分類(lèi)并構(gòu)建相應(yīng)索引，然后對(duì)不同類(lèi)型結(jié)點(diǎn)之間能否連成一邊的概率進(jìn)行預(yù)測(cè)，并基于上述信息，對(duì)多結(jié)點(diǎn)子圖的匹配基數(shù)進(jìn)行預(yù)測(cè)，最后運(yùn)用機(jī)器學(xué)習(xí)的方法對(duì)匹配結(jié)果的基數(shù)進(jìn)行補(bǔ)償。

簡(jiǎn)言之，文章的主要貢獻(xiàn)是將圖數(shù)據(jù)的結(jié)構(gòu)信息建模到子圖匹配結(jié)果的基數(shù)估計(jì)工作中，并根據(jù)Boosting 學(xué)習(xí)思想，提出適用于多結(jié)點(diǎn)子圖的匹配結(jié)果預(yù)測(cè)方法（Boosting cardinality estimator，BoostCard）。

1 相關(guān)工作

在社交、電商、零售、物聯(lián)網(wǎng)等行業(yè)快速發(fā)展的Web 2.0 環(huán)境中，圖數(shù)據(jù)庫(kù)因?yàn)樗膶?duì)聯(lián)系建模等天然優(yōu)勢(shì)，彌補(bǔ)了傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)在復(fù)雜關(guān)系運(yùn)算方面的短板。對(duì)于圖數(shù)據(jù)庫(kù)，找到一種準(zhǔn)確、有效的代價(jià)預(yù)測(cè)方法，將能夠?qū)崿F(xiàn)數(shù)據(jù)管理系統(tǒng)的優(yōu)化，提高執(zhí)行效率。以代價(jià)估計(jì)為依據(jù)尋找最佳執(zhí)行策略的方法已經(jīng)在各大傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)中得到應(yīng)用。在圖數(shù)據(jù)庫(kù)的數(shù)據(jù)管理操作中，子圖同構(gòu)查詢(xún)是重要的基礎(chǔ)查詢(xún)形式，也是數(shù)據(jù)管理的基礎(chǔ)操作，在實(shí)際執(zhí)行查詢(xún)前，若能夠預(yù)先估計(jì)出這些基礎(chǔ)操作的查詢(xún)結(jié)果基數(shù)，也將極大地提升圖數(shù)據(jù)庫(kù)的查詢(xún)性能。然而，目前提出的方法普遍對(duì)圖數(shù)據(jù)庫(kù)的結(jié)構(gòu)要求較為特化，還沒(méi)有一個(gè)泛用、完善的圖數(shù)據(jù)庫(kù)數(shù)據(jù)管理操作代價(jià)估計(jì)的解決方案。

1.1 子圖同構(gòu)算法

子圖同構(gòu)問(wèn)題，簡(jiǎn)單來(lái)說(shuō)就是在給定的數(shù)據(jù)圖中查找與模式圖相同的子結(jié)構(gòu)，一般分為精確匹配和近似匹配。本研究針對(duì)精確匹配展開(kāi)討論，匹配過(guò)程中要求數(shù)據(jù)圖的匹配結(jié)果與模式圖完全一致。

圖）定義三元組(,,)表示一個(gè)圖，其中表示圖中結(jié)點(diǎn)的集合；表示邊的集合，∈×；是該圖的屬性映射函數(shù)，將邊或結(jié)點(diǎn)映射到一個(gè)或一組屬性。

（子圖匹配）已知數(shù)據(jù)圖=(,,)和模式圖=(V,E,L)，精確子圖匹配要求在模式圖和數(shù)據(jù)子圖=(,,)之間建立一個(gè)雙射函數(shù)：

如圖1，模式圖在數(shù)據(jù)圖中存在兩個(gè)匹配的子圖，即=[(,),(,),(,),(,)]和=[(,),(,),(,),(,)]。

圖1 精確匹配示例Fig.1 Sample of exact subisomorphism

從算法的角度，精確匹配分為無(wú)索引的匹配和基于索引的匹配，無(wú)索引的精確匹配利用圖中的語(yǔ)義和結(jié)構(gòu)信息縮小匹配范圍。1976 年提出的Ullmann算法針對(duì)結(jié)點(diǎn)的度、映射規(guī)則、結(jié)點(diǎn)鄰接關(guān)系提出一系列剪枝規(guī)則，在小規(guī)模圖匹配問(wèn)題中簡(jiǎn)單有效。在Ullmann 算法的基礎(chǔ)上，Sansone 等人提出VF2 算法，通過(guò)標(biāo)簽中的語(yǔ)義信息對(duì)匹配的預(yù)選集進(jìn)行過(guò)濾，并通過(guò)預(yù)選結(jié)點(diǎn)在未匹配結(jié)點(diǎn)中的入度和出度進(jìn)行一步預(yù)先判斷，進(jìn)一步縮小了搜索空間。

近年來(lái)的改進(jìn)算法將更復(fù)雜的路徑和子圖結(jié)構(gòu)引入剪枝過(guò)程，進(jìn)一步縮小了搜索空間，以實(shí)現(xiàn)更大規(guī)模的匹配問(wèn)題求解。隨著圖數(shù)據(jù)規(guī)模的繼續(xù)擴(kuò)大，基于索引的匹配技術(shù)應(yīng)運(yùn)而生，這些技術(shù)通過(guò)數(shù)據(jù)圖中的有效特征構(gòu)建索引，能夠快速縮小子圖范圍，再基于備選子圖展開(kāi)精確匹配。這些特征既能實(shí)現(xiàn)圖索引構(gòu)建，又很大程度上表達(dá)了圖的結(jié)構(gòu)信息，對(duì)包含圖數(shù)據(jù)的結(jié)構(gòu)特征構(gòu)建也能起到極大的幫助作用。

而在最終的匹配過(guò)程中，子圖匹配問(wèn)題仍然是NP 完全問(wèn)題（non-deterministic polynomial complete problem），在多項(xiàng)式的時(shí)間開(kāi)銷(xiāo)內(nèi)對(duì)匹配結(jié)果的基數(shù)進(jìn)行粗略估計(jì)將為查詢(xún)操作的優(yōu)化提供重要依據(jù)。

1.2 啟發(fā)式預(yù)測(cè)方法

圖數(shù)據(jù)庫(kù)系統(tǒng)進(jìn)行查詢(xún)時(shí)使用連接運(yùn)算擴(kuò)大對(duì)圖中各邊的搜索和匹配。一些圖數(shù)據(jù)庫(kù)系統(tǒng)將預(yù)先加入索引的圖數(shù)據(jù)子模式作為基本單位進(jìn)行連接。Maduko 等人針對(duì)上述過(guò)程，提出了一種圖數(shù)據(jù)摘要技術(shù)，并通過(guò)建立的圖數(shù)據(jù)摘要，使用有索引的頻繁子結(jié)構(gòu)描述查詢(xún)子圖數(shù)據(jù)的特征，進(jìn)行啟發(fā)式的查詢(xún)子圖基數(shù)估計(jì)。

對(duì)子圖匹配問(wèn)題的代價(jià)預(yù)估技術(shù)，在資源描述框架中也已經(jīng)提出了一系列可行的實(shí)現(xiàn)模型，但這些方法對(duì)圖數(shù)據(jù)的構(gòu)成結(jié)構(gòu)有較高的要求，解決問(wèn)題較為特化，在所有結(jié)點(diǎn)均表示一個(gè)實(shí)體的非資源描述框架的圖數(shù)據(jù)中難以達(dá)到預(yù)期,不能實(shí)現(xiàn)普通圖數(shù)據(jù)庫(kù)的匹配代價(jià)預(yù)測(cè)。

針對(duì)上述問(wèn)題，Paradies 等人為非資源描述框架下的圖數(shù)據(jù)提出一種專(zhuān)門(mén)的子圖匹配基數(shù)估計(jì)的方法，該方法基于統(tǒng)計(jì)學(xué)理論，運(yùn)用數(shù)據(jù)圖中的基礎(chǔ)統(tǒng)計(jì)數(shù)據(jù)預(yù)測(cè)兩結(jié)點(diǎn)及其相連的邊在單張大規(guī)模數(shù)據(jù)圖中的匹配結(jié)果的基數(shù)，并通過(guò)關(guān)系依賴(lài)使算法在多屬性圖的環(huán)境中更加穩(wěn)定有效。但是方法只對(duì)兩個(gè)結(jié)點(diǎn)及其相連的邊有效，無(wú)法直接應(yīng)用于存在多結(jié)點(diǎn)的完整模式圖匹配中。

1.3 關(guān)系型數(shù)據(jù)的智能化估計(jì)

近幾年來(lái)，很多學(xué)者為提升數(shù)據(jù)庫(kù)查詢(xún)性能預(yù)測(cè)的普適性，尤其是為解決存在復(fù)雜謂詞和連接時(shí)傳統(tǒng)方法誤差較大的問(wèn)題，提出了一些基于深度學(xué)習(xí)的解決方案。Kipf 等人提出Learned Cardinalities方法，對(duì)數(shù)據(jù)庫(kù)表、連接操作、謂詞邏輯分別進(jìn)行編碼，以實(shí)現(xiàn)數(shù)據(jù)庫(kù)查詢(xún)輸入的向量化轉(zhuǎn)化表示。

最新的結(jié)構(gòu)化查詢(xún)語(yǔ)言（structured query language，SQL）查詢(xún)性能預(yù)測(cè)研究通過(guò)SQL 查詢(xún)執(zhí)行計(jì)劃實(shí)現(xiàn)了更為靈活的端到端預(yù)測(cè)來(lái)適應(yīng)各種不同結(jié)構(gòu)的查詢(xún)。SQL 查詢(xún)語(yǔ)句可以通過(guò)執(zhí)行優(yōu)化器表示為查詢(xún)執(zhí)行計(jì)劃的形式，它們將SQL 查詢(xún)細(xì)化成對(duì)數(shù)據(jù)庫(kù)系統(tǒng)中的原子性操作，并構(gòu)建成樹(shù)狀結(jié)構(gòu)來(lái)表示具體執(zhí)行過(guò)程。

結(jié)合執(zhí)行計(jì)劃的樹(shù)狀結(jié)構(gòu)特點(diǎn)，一些學(xué)者通過(guò)構(gòu)建相應(yīng)的表示模型來(lái)執(zhí)行逐級(jí)預(yù)測(cè)。Sun、Li 為執(zhí)行計(jì)劃樹(shù)的結(jié)點(diǎn)構(gòu)建一個(gè)結(jié)點(diǎn)表示網(wǎng)絡(luò)來(lái)預(yù)測(cè)到每個(gè)結(jié)點(diǎn)為止的開(kāi)銷(xiāo)及基數(shù)，并作為高一級(jí)運(yùn)算的輸入向上傳遞；對(duì)于有謂詞限定數(shù)據(jù)，該方法采取簡(jiǎn)單的數(shù)理計(jì)算獲取預(yù)測(cè)值。Marcus 等人針對(duì)執(zhí)行計(jì)劃中不同的操作構(gòu)建不同輸入結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)作為神經(jīng)單元，并將這些神經(jīng)單元依據(jù)查詢(xún)計(jì)劃的結(jié)構(gòu)連接成樹(shù)，僅通過(guò)查詢(xún)計(jì)劃中的參數(shù)和低一級(jí)的預(yù)測(cè)結(jié)果作為輸入實(shí)現(xiàn)預(yù)測(cè)。

2 問(wèn)題定義

定義2 引用了關(guān)于子圖匹配問(wèn)題的定義，擬解決的問(wèn)題是盡可能準(zhǔn)確預(yù)測(cè)子圖匹配的基數(shù)。

（子圖匹配基數(shù)）對(duì)于給定的數(shù)據(jù)圖=(,,)以及模式圖=(V,E,L)，模式圖可能與的任意子圖=(,,)建立雙射函數(shù)滿(mǎn)足子圖匹配的要求，將所有滿(mǎn)足要求的函數(shù)集合記作F，該集合中元素的個(gè)數(shù)|F|即為數(shù)據(jù)圖與模式圖的子圖匹配基數(shù)。

在大規(guī)模的數(shù)據(jù)圖中，執(zhí)行子圖匹配任務(wù)往往會(huì)面臨時(shí)空開(kāi)銷(xiāo)大，無(wú)法在足夠短的時(shí)間內(nèi)給出結(jié)果。本文研究子圖匹配基數(shù)的預(yù)測(cè)方法，輸入擬執(zhí)行子圖匹配的模式圖與數(shù)據(jù)圖。在不進(jìn)行實(shí)際的子圖匹配操作的前提下，輸出一個(gè)該組圖數(shù)據(jù)的子圖匹配基數(shù)的預(yù)測(cè)值。

3 BoostCard 方法

BoostCard 是一種在整張模式圖上游走，依經(jīng)過(guò)的每一邊估計(jì)匹配結(jié)果基數(shù)的方法，這個(gè)過(guò)程中會(huì)利用對(duì)各個(gè)結(jié)點(diǎn)的局部結(jié)構(gòu)信息生成對(duì)應(yīng)的結(jié)點(diǎn)表示，并以此提高每一跳預(yù)測(cè)的準(zhǔn)確度。在這一預(yù)測(cè)框架下，為了能夠?qū)崿F(xiàn)對(duì)模式圖全局信息的掌握，預(yù)測(cè)補(bǔ)償機(jī)制以提升學(xué)習(xí)的形式加入到方法中，對(duì)結(jié)點(diǎn)的表示向量進(jìn)行學(xué)習(xí)，獲得針對(duì)不同模式圖的補(bǔ)償強(qiáng)度來(lái)優(yōu)化預(yù)測(cè)結(jié)果。

3.1 基本思路

模式圖對(duì)于數(shù)據(jù)圖的匹配過(guò)程被視為一個(gè)連接操作的執(zhí)行過(guò)程。模式圖中的結(jié)點(diǎn)的匹配順序由深度優(yōu)先遍歷產(chǎn)生：(,,,)，首先將中的結(jié)點(diǎn)分為兩個(gè)集合，即已匹配集V和待匹配集V。初始條件下，所有結(jié)點(diǎn)均于待匹配集V中，隨著未匹配的結(jié)點(diǎn)加入匹配，模式圖中的結(jié)點(diǎn)依匹配順序由待匹配集轉(zhuǎn)移到已匹配集中。如圖2 所示的子圖匹配過(guò)程中，在前三個(gè)結(jié)點(diǎn)已經(jīng)完成匹配的情況下，V={,,}，V={}。匹配的過(guò)程可以看作模式圖的子圖在數(shù)據(jù)圖的約束下添加一個(gè)滿(mǎn)足條件的結(jié)點(diǎn)及其與中一點(diǎn)之間相連的邊，匹配完成后V={,,,}，V=?。

圖2 結(jié)構(gòu)信息獲取Fig.2 Structural information acquirement

BoostCard的基本預(yù)測(cè)過(guò)程在算法1中給出描述。

預(yù)測(cè)框架

BoostCard 預(yù)測(cè)主要由四部分組成：結(jié)構(gòu)索引、結(jié)點(diǎn)連接預(yù)測(cè)、多結(jié)點(diǎn)預(yù)測(cè)框架、預(yù)測(cè)補(bǔ)償器。

預(yù)測(cè)執(zhí)行過(guò)程如下：（1）通過(guò)結(jié)構(gòu)索引將數(shù)據(jù)圖中所有結(jié)點(diǎn)分類(lèi)分組，并構(gòu)建簡(jiǎn)單索引實(shí)現(xiàn)快速訪(fǎng)問(wèn)。（2）在構(gòu)建的結(jié)構(gòu)索引的基礎(chǔ)上，通過(guò)結(jié)點(diǎn)連接預(yù)測(cè)過(guò)程，對(duì)數(shù)據(jù)圖中任意兩類(lèi)結(jié)點(diǎn)之間連成一邊的概率進(jìn)行預(yù)測(cè)。（3）多結(jié)點(diǎn)預(yù)測(cè)器依照匹配過(guò)程，預(yù)測(cè)模式圖在數(shù)據(jù)圖中出現(xiàn)的次數(shù)，即匹配結(jié)果的基數(shù)。預(yù)測(cè)器對(duì)模式圖的子圖的匹配基數(shù)進(jìn)行預(yù)測(cè)，并依照匹配順序添加新的待匹配結(jié)點(diǎn)以更新，直到所有中結(jié)點(diǎn)全部添加到中，此時(shí)所得到的預(yù)測(cè)結(jié)果即為模式圖的匹配基數(shù)估計(jì)值。（4）根據(jù)建立的結(jié)構(gòu)索引，可以通過(guò)預(yù)測(cè)補(bǔ)償器獲取模式圖的統(tǒng)計(jì)向量表示作為依據(jù)，結(jié)合提升學(xué)習(xí)的思想對(duì)預(yù)測(cè)結(jié)果進(jìn)行補(bǔ)償。

接下來(lái)，分別對(duì)模型的每個(gè)部分進(jìn)行討論。

3.2 結(jié)構(gòu)索引

結(jié)構(gòu)索引的目的在于對(duì)數(shù)據(jù)圖中出現(xiàn)的結(jié)點(diǎn)的結(jié)構(gòu)信息建模。這些結(jié)構(gòu)信息主要基于每個(gè)結(jié)點(diǎn)及其相鄰的結(jié)點(diǎn)的屬性信息構(gòu)建而成。

屬性映射函數(shù)將各結(jié)點(diǎn)的屬性映射到自然數(shù)集中：

:→

其中，為數(shù)據(jù)圖中屬性集，??，為自然數(shù)集的子集；∈，可作為結(jié)點(diǎn)屬性的唯一表示。

結(jié)構(gòu)索引的構(gòu)成由圖2（d）所示，對(duì)于數(shù)據(jù)圖中的結(jié)點(diǎn)v，其中，l∈，為結(jié)點(diǎn)v的整數(shù)映射，為表示v的鄰居結(jié)點(diǎn)信息的二值向量：

對(duì)于數(shù)據(jù)圖的結(jié)點(diǎn)v，若其存在屬性映射到整數(shù)集后取值為的鄰居，則取值為1，不存在上述鄰居結(jié)點(diǎn)則取值為0，在圖2（a）所示的數(shù)據(jù)圖中，結(jié)點(diǎn)的結(jié)構(gòu)索引向量如圖2（e）所示。圖中結(jié)點(diǎn)和邊的屬性映射到整數(shù)域中，圖2（b）展示了經(jīng)屬性映射的數(shù)據(jù)圖。結(jié)點(diǎn)自身的屬性映射為2，其鄰居結(jié)點(diǎn)含有被映射為0、1 的屬性；在圖示的數(shù)據(jù)圖中，結(jié)點(diǎn)屬性只有4 種取值，的長(zhǎng)度為4。綜上，的結(jié)構(gòu)索引向量中取值為2，為(1,1,0,0)。結(jié)構(gòu)索引將數(shù)據(jù)圖中的各個(gè)結(jié)點(diǎn)的結(jié)構(gòu)信息表示成一個(gè)標(biāo)量與一個(gè)向量組成的元組作為結(jié)點(diǎn)v的結(jié)構(gòu)標(biāo)識(shí)d∈×{0,1}。擁有同樣結(jié)構(gòu)標(biāo)識(shí)的結(jié)點(diǎn)即被視為同種類(lèi)型的結(jié)點(diǎn)。 D={∈|d=}表示有同一類(lèi)結(jié)構(gòu)標(biāo)識(shí)的結(jié)點(diǎn)。

3.3 結(jié)點(diǎn)連接預(yù)測(cè)

結(jié)點(diǎn)連接預(yù)測(cè)的作用是針對(duì)數(shù)據(jù)圖，統(tǒng)計(jì)不同類(lèi)型的結(jié)點(diǎn)之間能夠連成擁有某屬性的一邊的概率。

結(jié)點(diǎn)連接預(yù)測(cè)同樣將數(shù)據(jù)圖中的邊的屬性映射到整數(shù)集：

:→S

其中，分母表示數(shù)據(jù)圖中d類(lèi)型的結(jié)點(diǎn)到d類(lèi)型的結(jié)點(diǎn)可能的組合的個(gè)數(shù)；分子表示這些組合中兩點(diǎn)之間存在一條屬性映射到的邊的組合數(shù)。

至此，對(duì)于一個(gè)匹配查詢(xún)的模式圖，首先以?xún)山Y(jié)點(diǎn)及其間一邊構(gòu)成的圖為例，將兩結(jié)點(diǎn)分別分類(lèi)到對(duì)應(yīng)的結(jié)點(diǎn)類(lèi)型中，即可通過(guò)數(shù)據(jù)圖中這兩種結(jié)點(diǎn)的數(shù)目以及其間可連成一邊的概率預(yù)測(cè)匹配結(jié)果的基數(shù)。

如圖2（c）所示的模式圖中，結(jié)點(diǎn)對(duì)應(yīng)數(shù)據(jù)圖的結(jié)構(gòu)標(biāo)識(shí)為(2,(0,1,0,0))，這與中結(jié)點(diǎn)的結(jié)構(gòu)標(biāo)識(shí)(2,(1,1,0,0))是不同的，然而模式圖顯然可以在數(shù)據(jù)圖中成功匹配。

預(yù)測(cè)乘子multiplier

匹配概率match_prob

輸入：數(shù)據(jù)圖中目標(biāo)結(jié)點(diǎn)，模式圖中待匹配結(jié)點(diǎn)。

輸出：匹配到的概率。

3.4 多結(jié)點(diǎn)預(yù)測(cè)器

BoostCard 預(yù)測(cè)器根據(jù)匹配順序添加結(jié)點(diǎn)實(shí)現(xiàn)預(yù)測(cè)：

新加入的結(jié)點(diǎn)對(duì)于其所在模式圖的結(jié)構(gòu)信息未必與數(shù)據(jù)圖中的對(duì)應(yīng)結(jié)點(diǎn)完全相同，但是其結(jié)構(gòu)信息卻可以以不同的概率對(duì)應(yīng)到中不同種類(lèi)的結(jié)點(diǎn)中。

其中，⊕為按位異或操作，兩個(gè)序列中對(duì)應(yīng)位置的元素相同則取值為1，否則取值為0。

至此已實(shí)現(xiàn)了多結(jié)點(diǎn)模式圖的匹配基數(shù)估計(jì)。

3.5 預(yù)測(cè)補(bǔ)償

由于上述預(yù)測(cè)過(guò)程是一個(gè)使用預(yù)測(cè)值生成新的預(yù)測(cè)值的過(guò)程，未免會(huì)有誤差累積的問(wèn)題。為了補(bǔ)償這種累計(jì)誤差，引入預(yù)測(cè)補(bǔ)償器實(shí)現(xiàn)模式圖的嵌入表示和累計(jì)誤差的補(bǔ)償，得到最終預(yù)測(cè)結(jié)果。

將定義為模式圖中所有結(jié)構(gòu)標(biāo)識(shí)的集合。對(duì)預(yù)測(cè)結(jié)果補(bǔ)償時(shí)，首先將模式圖嵌入表示為長(zhǎng)度為||的向量：

由公式向量的每一個(gè)元素分別對(duì)應(yīng)一個(gè)結(jié)構(gòu)標(biāo)識(shí)。

式中，∈[0,1]，為補(bǔ)償閾值，用以控制發(fā)生錯(cuò)誤補(bǔ)償?shù)那闆r，該值為超參數(shù)，取值越大，對(duì)錯(cuò)誤補(bǔ)償?shù)囊种圃綇?qiáng)。和為模型參數(shù)，下面通過(guò)訓(xùn)練獲取對(duì)于特定數(shù)據(jù)圖的上述參數(shù)。

根據(jù)上述預(yù)測(cè)過(guò)程，能夠得到任意一組模式圖在給定數(shù)據(jù)圖中的匹配基數(shù)估計(jì)值。同時(shí)，也可以通過(guò)實(shí)際執(zhí)行精確匹配來(lái)確定其真實(shí)的匹配基數(shù)。對(duì)于實(shí)際值大于預(yù)測(cè)值的模式圖，將其標(biāo)簽標(biāo)記為1，即M=1，對(duì)于實(shí)際值小于預(yù)測(cè)值的模式圖，將其標(biāo)簽標(biāo)記為-1，即M=-1。

其圖像如圖3 所示。

圖3 損失函數(shù)Fig.3 Loss function

4 實(shí)驗(yàn)

BoostCard 方法主要應(yīng)用于模式圖在單張大規(guī)模數(shù)據(jù)圖中的匹配結(jié)果基數(shù)的預(yù)測(cè)。本章展開(kāi)實(shí)驗(yàn)來(lái)評(píng)估BoostCard 方法對(duì)匹配基數(shù)的預(yù)測(cè)能力。

4.1 實(shí)驗(yàn)內(nèi)容

實(shí)驗(yàn)采用經(jīng)典的大規(guī)模圖數(shù)據(jù)Yeast 數(shù)據(jù)集、Human 數(shù)據(jù)集和Facebook 數(shù)據(jù)集以及使用graphGen工具人工生成的數(shù)據(jù)圖作為測(cè)試數(shù)據(jù)。在上述數(shù)據(jù)集中隨機(jī)生成結(jié)點(diǎn)數(shù)分別為2、3、4、5 以及10 的子圖作為匹配的查詢(xún)集。在本實(shí)驗(yàn)中，所有生成的模式圖均為無(wú)環(huán)的樹(shù)狀圖。

對(duì)于獲取的數(shù)據(jù)集，采用VF2 算法執(zhí)行匹配過(guò)程，記錄每組查詢(xún)圖在相應(yīng)的數(shù)據(jù)圖中的匹配結(jié)果數(shù)作為匹配數(shù)據(jù)的真實(shí)值。在實(shí)際匹配的過(guò)程中，認(rèn)為模式圖中結(jié)點(diǎn)的屬性應(yīng)與數(shù)據(jù)圖中被匹配結(jié)點(diǎn)的屬性完全相同。

通過(guò)獲得的上述數(shù)據(jù)訓(xùn)練BoostCard 預(yù)測(cè)模型。分別使用傳統(tǒng)的統(tǒng)計(jì)方法以及BoostCard 預(yù)測(cè)方法對(duì)數(shù)據(jù)的匹配結(jié)果進(jìn)行預(yù)測(cè)，比較執(zhí)行結(jié)果。

傳統(tǒng)統(tǒng)計(jì)方法通過(guò)式（10）計(jì)算結(jié)點(diǎn)的選擇度：

并通過(guò)式（9）計(jì)算一條邊在數(shù)據(jù)圖中的預(yù)測(cè)基數(shù)。

在多結(jié)點(diǎn)的預(yù)測(cè)過(guò)程中，預(yù)測(cè)按照結(jié)點(diǎn)游走的順序進(jìn)行，每加入一個(gè)結(jié)點(diǎn)，將已經(jīng)預(yù)測(cè)的部分看作一個(gè)新的結(jié)點(diǎn)，與下一個(gè)待匹配結(jié)點(diǎn)形成一個(gè)新的短路徑，直到所有結(jié)點(diǎn)完成匹配。該方法將作為本文的基準(zhǔn)方法。

將每組模式圖隨機(jī)分為5 組，進(jìn)行五折交叉驗(yàn)證，并取平均值作為一次實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)重復(fù)5 次，得到5 組結(jié)果，最終輸出5 次實(shí)驗(yàn)結(jié)果的平均值。為了在訓(xùn)練及預(yù)測(cè)中，使輸出值更加均勻，對(duì)匹配基數(shù)做對(duì)數(shù)處理，這樣也更能表現(xiàn)匹配基數(shù)的數(shù)量級(jí)。接下來(lái)，將每個(gè)查詢(xún)結(jié)果對(duì)應(yīng)的數(shù)據(jù)圖與模式圖作為預(yù)測(cè)模型的輸入，執(zhí)行匹配基數(shù)估計(jì)。

為了評(píng)估預(yù)測(cè)的準(zhǔn)確度，實(shí)驗(yàn)采用兩個(gè)評(píng)價(jià)指標(biāo)：平均平方誤差()、決定系數(shù)()。決定系數(shù)通常用來(lái)衡量回歸任務(wù)的擬合程度。其計(jì)算方式如式（12）所示，越大，表示模型的擬合程度越強(qiáng)。當(dāng)值為負(fù)時(shí)，表示模型無(wú)法解釋擬合中的變異，即模型不適用于相應(yīng)數(shù)據(jù)的擬合，實(shí)驗(yàn)中以“—”表示。

4.2 實(shí)驗(yàn)結(jié)果

通過(guò)預(yù)測(cè)結(jié)果與匹配實(shí)際值的對(duì)數(shù)均方誤差評(píng)估預(yù)測(cè)的準(zhǔn)確率。預(yù)測(cè)值如表1 所示，由圖4給出。在結(jié)點(diǎn)較多的情況下，由于匹配基數(shù)的增大，匹配結(jié)果真值的方差隨之增大，通過(guò)進(jìn)行評(píng)估反映得預(yù)測(cè)準(zhǔn)確度的精度會(huì)有所下降，但由于同一組實(shí)驗(yàn)中的不同方法采用的是相同的數(shù)據(jù)集，值的大小仍可用以比較兩種方法的準(zhǔn)確度。在給定的數(shù)據(jù)集中，傳統(tǒng)預(yù)測(cè)方法在僅有兩個(gè)結(jié)點(diǎn)的模式圖中優(yōu)于BoostCard 方法，其主要原因是BoostCard 方法中的結(jié)構(gòu)索引等結(jié)構(gòu)信息對(duì)單邊的預(yù)測(cè)會(huì)造成一定的影響，對(duì)統(tǒng)計(jì)信息直接應(yīng)用的傳統(tǒng)方法在單邊預(yù)測(cè)的情況下反而更加準(zhǔn)確。但是，在傳統(tǒng)的方法中，隨著結(jié)點(diǎn)數(shù)的增加，預(yù)測(cè)結(jié)果的分布很快變得不可控，在超過(guò)3 個(gè)結(jié)點(diǎn)的查詢(xún)集中甚至出現(xiàn)值為負(fù)的情況，預(yù)測(cè)結(jié)果與實(shí)際值難以成正線(xiàn)性關(guān)系，難以滿(mǎn)足實(shí)際需求，而在一定的范圍內(nèi)，BoostCard 方法在多結(jié)點(diǎn)數(shù)據(jù)中仍能提供較穩(wěn)定的估計(jì)值。

表1 預(yù)測(cè)r2 值Table 1 Estimated r2 values

圖4 估計(jì)均方誤差Fig.4 Estimation of mean-square error

4.3 預(yù)測(cè)補(bǔ)償準(zhǔn)確率

本節(jié)通過(guò)調(diào)整閾值對(duì)預(yù)測(cè)補(bǔ)償器的執(zhí)行效果進(jìn)行評(píng)估。在BoostCard 預(yù)測(cè)方法中，在進(jìn)行初步的基于概率的技術(shù)預(yù)測(cè)后，模型會(huì)通過(guò)機(jī)器學(xué)習(xí)方法對(duì)結(jié)果進(jìn)行補(bǔ)償性預(yù)測(cè)，如3.5 節(jié)所述，這個(gè)過(guò)程可以看作一個(gè)分類(lèi)問(wèn)題。當(dāng)實(shí)際值大于初步預(yù)測(cè)值時(shí)，預(yù)測(cè)補(bǔ)償因子＞0，反之，＜0。為了避免錯(cuò)誤方向的補(bǔ)償，采用閾值來(lái)限制補(bǔ)償?shù)膱?zhí)行。當(dāng)且僅當(dāng)預(yù)測(cè)補(bǔ)償因子的絕對(duì)值||＞時(shí)，執(zhí)行預(yù)測(cè)補(bǔ)償。

實(shí)驗(yàn)針對(duì)Human 及Facebook 數(shù)據(jù)集展開(kāi)，研究的不同取值對(duì)正確執(zhí)行補(bǔ)償?shù)挠绊?，通過(guò)設(shè)置不同的值研究補(bǔ)償結(jié)果。在實(shí)驗(yàn)中，如下定義準(zhǔn)確率（）并以此為評(píng)估依據(jù)：

評(píng)估結(jié)果如表2 所示。

表2 預(yù)測(cè)補(bǔ)償器準(zhǔn)確率Table 2 Accuracy of estimation compensation

圖5 展示了Human 數(shù)據(jù)集中，對(duì)含有5 個(gè)結(jié)點(diǎn)的模式圖集進(jìn)行預(yù)測(cè)時(shí)，準(zhǔn)確率與執(zhí)行率隨閾值取值變化的影響。圖像顯示，隨著增大補(bǔ)償預(yù)測(cè)的準(zhǔn)確率有所升高，但是可執(zhí)行的補(bǔ)償越來(lái)越少。閾值減小，將允許更多的預(yù)測(cè)結(jié)果執(zhí)行預(yù)測(cè)補(bǔ)償，但有可能導(dǎo)致最終預(yù)測(cè)更加偏離真實(shí)值。

圖5 預(yù)測(cè)補(bǔ)償準(zhǔn)確率與正確執(zhí)行數(shù)Fig.5 Accuracy and recall of estimation compensation

5 結(jié)束語(yǔ)

子圖匹配的基數(shù)估計(jì)任務(wù)在圖數(shù)據(jù)相關(guān)領(lǐng)域的研究工作，尤其是圖數(shù)據(jù)庫(kù)執(zhí)行效率優(yōu)化方面發(fā)揮著重要作用。本文從統(tǒng)計(jì)學(xué)的角度結(jié)合集成學(xué)習(xí)的思想對(duì)圖數(shù)據(jù)中的結(jié)構(gòu)鄰域信息進(jìn)行建模并實(shí)現(xiàn)子圖匹配基數(shù)的預(yù)測(cè)。文章提出的BoostCard 方法能夠運(yùn)用圖數(shù)據(jù)中結(jié)點(diǎn)鄰域的結(jié)構(gòu)信息來(lái)提升預(yù)測(cè)過(guò)程的拓?fù)湫畔⒌睦寐?，在結(jié)點(diǎn)數(shù)目有限的模式圖中給出較高的預(yù)測(cè)準(zhǔn)確度，實(shí)現(xiàn)了一種通用的匹配基數(shù)估計(jì)架構(gòu)。為了提高預(yù)測(cè)模型對(duì)全局信息的應(yīng)用，BoostCard 方法通過(guò)全局的結(jié)構(gòu)索引信息對(duì)預(yù)測(cè)結(jié)果進(jìn)行進(jìn)一步補(bǔ)償，并提供一個(gè)可調(diào)節(jié)的閾值控制補(bǔ)償力度，以應(yīng)對(duì)不同特征的數(shù)據(jù)集。相對(duì)于傳統(tǒng)的預(yù)測(cè)方法，BoostCard 方法能夠在結(jié)點(diǎn)較多的模式圖的匹配任務(wù)中實(shí)現(xiàn)更加穩(wěn)定的表現(xiàn)。

BoostCard 方法同樣可以應(yīng)用到各種索引編碼中，以表示模式圖中更加豐富、細(xì)化的結(jié)構(gòu)特征。文章采取的結(jié)構(gòu)索引實(shí)質(zhì)上相當(dāng)于一個(gè)星形特征的索引，現(xiàn)有的子圖匹配索引技術(shù)提供了鏈狀、樹(shù)狀、環(huán)狀等多種結(jié)構(gòu)特征。這些結(jié)構(gòu)特征將為提升學(xué)習(xí)提供更全面的學(xué)習(xí)依據(jù)，這也是未來(lái)工作中有待進(jìn)一步考慮的問(wèn)題。