多編碼樹GPU并行軸心子圖匹配

汪 洋，江世杰，曹宇聰，李傳文

（東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110169）

0 引言

近年來(lái)，隨著對(duì)圖的重要性的認(rèn)識(shí)逐漸增加，如何有效地對(duì)圖數(shù)據(jù)進(jìn)行管理成為了人們的研究重點(diǎn)。由于目前圖搜索［1-3］、子圖匹配等常見的圖操作仍存在可擴(kuò)展性和效率等方面的問(wèn)題，對(duì)這些操作的研究正在受到越來(lái)越多的關(guān)注。軸心子圖同構(gòu)作為一種特殊的子圖同構(gòu)問(wèn)題，也日益引起廣大研究者的興趣。對(duì)于一個(gè)給定的查詢圖，以查詢圖中的一個(gè)節(jié)點(diǎn)為軸心，軸心子圖同構(gòu)需要找到數(shù)據(jù)圖中與軸心匹配的節(jié)點(diǎn)。所謂與軸心匹配的節(jié)點(diǎn)是指數(shù)據(jù)圖中至少存在一個(gè)與查詢圖匹配的子圖，子圖中包含該節(jié)點(diǎn)。例如圖1（a）為軸心子圖同構(gòu)的查詢圖Q，其軸心為u1；在圖1（b）的數(shù)據(jù)圖G中，v1是軸心u1的有效匹配，因?yàn)樗嬖谟谝粋€(gè)查詢結(jié)果圖中，并且位置與u1對(duì)應(yīng)。

軸心子圖同構(gòu)的應(yīng)用非常廣泛，如蛋白質(zhì)交互網(wǎng)絡(luò)功能預(yù)測(cè)、頻繁子圖挖掘、鄰居子圖挖掘等［4-6］。Abdelhamid 等［7］提出了軸心子圖同構(gòu)算法——智能軸心子圖同構(gòu)（Smart Pivoted Sugraph Isomorphism，Smart PSI），利用機(jī)器學(xué)習(xí)預(yù)測(cè)候選節(jié)點(diǎn)是不是有效節(jié)點(diǎn)，從而分別利用樂(lè)觀和悲觀方法對(duì)該節(jié)點(diǎn)進(jìn)行驗(yàn)證。在預(yù)測(cè)正確的情況下，可以根據(jù)相應(yīng)算法快速求解，但是在預(yù)測(cè)錯(cuò)誤的情況下，利用相反算法進(jìn)行驗(yàn)證會(huì)浪費(fèi)大量的計(jì)算資源和內(nèi)存消耗，從而降低算法的執(zhí)行效率。其他軸心子圖同構(gòu)算法大多先進(jìn)行子圖同構(gòu)搜索，然后從子圖同構(gòu)結(jié)果中找到軸心節(jié)點(diǎn)。

根據(jù)算法的主要執(zhí)行環(huán)境，子圖同構(gòu)算法可分為基于CPU 和基于GPU 兩類。

基于CPU 的子圖同構(gòu)算法 Shang 等［8］提出了快速子圖同構(gòu)（Quick Subgraph Isomorphism，QuickSI），首先用快速子圖同構(gòu)序列（Quick subgraph Isomorphism Sequence，QISequence）來(lái)限制搜索空間，以及通過(guò)在數(shù)據(jù)庫(kù)中出現(xiàn)的特征頻數(shù)來(lái)確定序列順序，然后用Swift index 減少過(guò)濾階段的開 銷。Han 等［9］提出渦 輪增壓同構(gòu)（Turbo-charged Isomorphism，TurboISO），利用查詢圖的查詢順序來(lái)提高子圖同構(gòu)算法的執(zhí)行效率，同時(shí)提出鄰居等價(jià)類以減少候選節(jié)點(diǎn)的數(shù)量，減少無(wú)用的開銷。Zhang 等［10］提出了基于索引的圖匹配方 法（Distance Index based subGraph mAtching，GADDI），通過(guò)在單個(gè)大圖中引入頻繁子結(jié)構(gòu)進(jìn)而提出一種距離度量方法，通過(guò)相鄰判別子結(jié)構(gòu)（Neighboring Discriminating Substructure，NDS）距離將一對(duì)鄰居節(jié)點(diǎn)的局部圖結(jié)構(gòu)捕獲，產(chǎn)生強(qiáng)大的剪枝能力。算法的執(zhí)行方式［11-12］各有不同，而這些都是通過(guò)將候選節(jié)點(diǎn)進(jìn)行過(guò)濾［13］來(lái)提高算法的執(zhí)行效率。

基于GPU 的子圖同構(gòu)算法 隨著GPU 的高速發(fā)展，研究者開始嘗試將CPU 上的串行計(jì)算轉(zhuǎn)化為GPU 上的并行計(jì)算。利用GPU 的多核并行處理能力，可以顯著加快子圖同構(gòu)算法，因此許多研究人員提出了多種在GPU 上執(zhí)行的子圖同構(gòu)算法［14-15］。例如，Bonnici 等［16］提出GRASS，通過(guò)GPU并行過(guò)濾掉當(dāng)前查詢節(jié)點(diǎn)不滿足的候選節(jié)點(diǎn)，從而減小生成的搜索空間樹的尺寸。Tran 等［17］提出的GPU 友好子圖匹配（GPU-friendly Subgraph Matching，GpSM），通過(guò)生成樹和訪問(wèn)順序并行過(guò)濾查詢節(jié)點(diǎn)的候選集，然后基于非樹結(jié)構(gòu)和約簡(jiǎn)低連接點(diǎn)進(jìn)一步精煉候選節(jié)點(diǎn)，從而提高算法執(zhí)行效率。GPU 友好子 圖同構(gòu)（GPU-friendly Subgraph Isomorphism，GSI）［18］基于與GpSM 相似的 過(guò)濾和 連接框 架，但不同 于GpSM 基于邊的連接方式，GSI 采用了一種基于頂點(diǎn)的連接方式。

Smart PSI 雖然針對(duì)軸心子圖同構(gòu)進(jìn)行了優(yōu)化，但該方法是一種傳統(tǒng)的基于CPU 的方法，難以有效利用GPU 等新硬件的大規(guī)模并行處理能力。為了利用GPU 的高并發(fā)能力，本文設(shè)計(jì)了一種適用于GPU 的編碼過(guò)濾方式，可以并行地對(duì)候選節(jié)點(diǎn)進(jìn)行過(guò)濾。根據(jù)查詢圖節(jié)點(diǎn)的訪問(wèn)順序，該方法將下一個(gè)查詢圖節(jié)點(diǎn)的候選節(jié)點(diǎn)鎖定在與上一個(gè)查詢圖節(jié)點(diǎn)匹配的數(shù)據(jù)圖節(jié)點(diǎn)的鄰居范圍內(nèi)，達(dá)到二次過(guò)濾的效果。

在過(guò)濾過(guò)程中考慮節(jié)點(diǎn)的特征越多，過(guò)濾的效果越好；然而選用過(guò)多的節(jié)點(diǎn)特征會(huì)增加過(guò)濾過(guò)程的計(jì)算量，影響總體執(zhí)行效率。因此不同的過(guò)濾算法會(huì)在選用節(jié)點(diǎn)特征時(shí)進(jìn)行一定的權(quán)衡。為了在不占用過(guò)多計(jì)算資源的同時(shí)包含更多的特征，本文提出了一種基于多編碼樹的過(guò)濾方法，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行壓縮編碼。首先將節(jié)點(diǎn)的標(biāo)簽、度和鄰居結(jié)構(gòu)融入多棵不同的編碼樹中；然后計(jì)算每個(gè)編碼樹的特征向量并保存。在查詢圖中僅需要比較查詢圖節(jié)點(diǎn)與數(shù)據(jù)圖節(jié)點(diǎn)的特征向量編碼，即可將數(shù)據(jù)圖中的無(wú)效節(jié)點(diǎn)進(jìn)行大規(guī)模的過(guò)濾，極大縮小了候選節(jié)點(diǎn)生成的搜索空間樹的尺寸，提高了算法的執(zhí)行效率。本文提出的編碼方式還充分考慮了GPU的特點(diǎn)，從而使GPU 在利用編碼進(jìn)行過(guò)濾時(shí)可以充分地進(jìn)行并行操作。實(shí)驗(yàn)結(jié)果表明，本文方法的執(zhí)行時(shí)間明顯少于目前最先進(jìn)的基于GPU 的子圖同構(gòu)算法。

本文的主要工作如下：

1）提出了一種標(biāo)簽樹結(jié)構(gòu)。利用二進(jìn)制數(shù)表示圖標(biāo)簽種類，根據(jù)各位上的數(shù)值不同，生成不同類型的標(biāo)簽樹，從而盡可能多地展現(xiàn)出每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的結(jié)構(gòu)特征以及鄰居節(jié)點(diǎn)標(biāo)簽的組合情況。

2）提出了一種新穎的節(jié)點(diǎn)編碼方式。將節(jié)點(diǎn)盡可能多的特征組合起來(lái)，利用節(jié)點(diǎn)的鄰接矩陣的特征值來(lái)表示其鄰居節(jié)點(diǎn)的結(jié)構(gòu)和標(biāo)簽特征，然后將節(jié)點(diǎn)的標(biāo)簽、度以及特征值組合起來(lái)生成編碼，將復(fù)雜的結(jié)構(gòu)比較轉(zhuǎn)化為簡(jiǎn)單的數(shù)值比較。

3）提出了一種新的軸心子圖同構(gòu)搜索算法。利用GPU并行過(guò)濾當(dāng)前的查詢圖節(jié)點(diǎn)的候選節(jié)點(diǎn)，同時(shí)驗(yàn)證當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)在已匹配序列中的位置是否是其所匹配的節(jié)點(diǎn)的鄰居在已匹配序列中的位置的子集，將過(guò)濾與驗(yàn)證相結(jié)合。

1 預(yù)備知識(shí)

定義1子圖同構(gòu)。給定一個(gè)查詢圖Q={VQ，EQ，LQ}和數(shù)據(jù)圖G={VG，EG，LG}，其中VQ、VG是頂點(diǎn)的集合，EQ、EG是邊的集合，LQ、LG是將頂點(diǎn)映射到相應(yīng)標(biāo)簽的標(biāo)簽函數(shù)。子圖同構(gòu)即存在一個(gè)單射函數(shù)f：VQ→VG，對(duì)于查詢圖Q中?u，v∈VQ且(u，v)∈EQ，有f(u)，f(v)∈VG，(f(u)，f(v))∈EG，LQ(u)=LG(f(u))且LQ(v)=LG(f(v))。

定義2軸心子圖同構(gòu)。給定一個(gè)查詢圖Q={VQ，EQ，LQ}，軸心up∈VQ以及數(shù)據(jù)圖G={VG，EG，LG}，軸心vp∈VG，存在一個(gè)單射函數(shù)f：VQ→VG，軸心子圖同構(gòu)需要滿足如下三個(gè)條件：1）?u，v∈VQ有f(u)，f(v)∈VG，LQ(u)=LG(f(u)) 且LQ(v)=LG(f(v))；2）?(u，v)∈EQ，有(f(u)，f(v))∈EG；3）vp=f(up)。

軸心子圖同構(gòu)問(wèn)題類似于子圖同構(gòu)問(wèn)題，但是軸心子圖同構(gòu)問(wèn)題不需要在數(shù)據(jù)圖中找到所有與查詢圖匹配的子圖，而只需要在數(shù)據(jù)圖中找到所有與查詢圖軸心匹配的節(jié)點(diǎn)，每一節(jié)點(diǎn)至少存在于一個(gè)與查詢圖子圖同構(gòu)的子圖中。與子圖同構(gòu)相比，軸心子圖同構(gòu)只需要少量的計(jì)算和內(nèi)存。如圖1 所示，軸心子圖同構(gòu)的結(jié)果為{v1}，不包括v5，這是因?yàn)関1存在子圖(v1，v2，v3，v4)與查詢圖匹配，而v5不存在與查詢圖匹配的子圖。

定義3誘導(dǎo)子圖。一個(gè)誘導(dǎo)子圖g是圖G的節(jié)點(diǎn)的子集以及這些節(jié)點(diǎn)子集在G中形成的邊。

定理1［19］給定樹T有n個(gè)頂點(diǎn)和樹T′有m個(gè)頂點(diǎn)(n≥m)，它們的鄰接矩陣分別記為A和B。對(duì)于矩陣A，其特征值為λ1≥λ2≥…λn。對(duì)于矩 陣B，其特征值為α1≥α2≥…αm。如果T′是T的一個(gè)誘導(dǎo)子樹，則λn-m+i≤αi≤λi(i=1，2，…，m)。

定理1 是樹與其誘導(dǎo)子樹的鄰接矩陣特征值之間的關(guān)系。本文中，將圖轉(zhuǎn)化為樹，利用定理1 驗(yàn)證子圖。但是需要注意的是，定理1 只是一個(gè)必要條件而不是一個(gè)充分必要條件，對(duì)于滿足上述特征值條件的圖S和圖G，無(wú)法得到圖G是圖S的一個(gè)誘導(dǎo)子圖或者是子圖，但是可以得到滿足上述條件的圖一定包含了圖S的所有子圖。因此可以利用此條件進(jìn)行過(guò)濾，依據(jù)查詢圖節(jié)點(diǎn)鄰居結(jié)構(gòu)，對(duì)數(shù)據(jù)圖中每個(gè)節(jié)點(diǎn)鄰居結(jié)構(gòu)不滿足上述條件的節(jié)點(diǎn)進(jìn)行剪枝。

2 總體結(jié)構(gòu)

本文提出了一種基于GPU 的軸心子圖同構(gòu)算法，由編碼過(guò)濾、二次過(guò)濾和驗(yàn)證兩階段構(gòu)成。

2.1 編碼過(guò)濾

過(guò)濾階段著重研究如何將節(jié)點(diǎn)的鄰居結(jié)構(gòu)以及節(jié)點(diǎn)的鄰居標(biāo)簽應(yīng)用到編碼中，從而過(guò)濾掉更多候選節(jié)點(diǎn)。對(duì)于查詢圖節(jié)點(diǎn)的候選節(jié)點(diǎn)來(lái)說(shuō)，除了其本身的特征滿足查詢節(jié)點(diǎn)特征外，其鄰居節(jié)點(diǎn)的特征也要滿足查詢節(jié)點(diǎn)的鄰居特征。鄰居結(jié)構(gòu)是鄰居特征的重要因素，本文利用鄰接矩陣來(lái)表示。由于定理1 只適用于樹結(jié)構(gòu)，因此本文將圖節(jié)點(diǎn)的鄰居結(jié)構(gòu)轉(zhuǎn)化為樹結(jié)構(gòu)。如果查詢圖節(jié)點(diǎn)的鄰居結(jié)構(gòu)不是其候選節(jié)點(diǎn)鄰居結(jié)構(gòu)的子結(jié)構(gòu)，那么通過(guò)定理1 可以過(guò)濾掉該候選節(jié)點(diǎn)。

本文通過(guò)標(biāo)簽編碼樹的方式將鄰居節(jié)點(diǎn)標(biāo)簽應(yīng)用到鄰居結(jié)構(gòu)上，以增強(qiáng)過(guò)濾能力。事實(shí)上，每個(gè)節(jié)點(diǎn)都可以根據(jù)其鄰居結(jié)構(gòu)生成一棵無(wú)標(biāo)簽樹。然而鄰居節(jié)點(diǎn)的標(biāo)簽可能不同，僅生成無(wú)標(biāo)簽樹無(wú)法進(jìn)行有效的比較。因此本文根據(jù)標(biāo)簽類型對(duì)樹進(jìn)行切割，將同一類標(biāo)簽的節(jié)點(diǎn)放到一棵樹中。

定理2對(duì)于樹T′和T，按照將相同標(biāo)簽的節(jié)點(diǎn)放入同種標(biāo)簽樹中的規(guī)則將其切割成n個(gè)子樹，得到子樹序列和ST={t1，t2，…，ti，…，tn}，如 果序列中的所有ti′都是ti的誘導(dǎo)子樹，那么T′一定是T的一個(gè)誘導(dǎo)子樹。

證明 由于標(biāo)簽加入，若序列中的所有都是ti的誘導(dǎo)子樹，那么去掉標(biāo)簽后所有依舊是ti的誘導(dǎo)子樹，則T′必然是T的誘導(dǎo)子樹。

標(biāo)簽樹將原本的無(wú)標(biāo)簽樹按照同標(biāo)簽組合原則進(jìn)行分割，加強(qiáng)了過(guò)濾條件，使其不僅需要滿足結(jié)構(gòu)特征也要滿足標(biāo)簽特征。由于對(duì)于每個(gè)節(jié)點(diǎn)的切割規(guī)則是相同的，所以每個(gè)節(jié)點(diǎn)所產(chǎn)生樹的數(shù)目相同，在比較時(shí)通過(guò)對(duì)應(yīng)的標(biāo)簽樹的特征值進(jìn)行比較，即可過(guò)濾掉不滿足的節(jié)點(diǎn)。

2.2 過(guò)濾和驗(yàn)證

二次過(guò)濾和驗(yàn)證是利用過(guò)濾與驗(yàn)證框架，將編碼過(guò)濾后得到的每個(gè)查詢圖節(jié)點(diǎn)的候選集再次過(guò)濾。這次過(guò)濾是依據(jù)軸心子圖同構(gòu)的第二個(gè)條件，即如果兩個(gè)查詢圖節(jié)點(diǎn)之間存在邊，那么它們?cè)跀?shù)據(jù)圖中的候選節(jié)點(diǎn)之間也必定存在邊，否則該節(jié)點(diǎn)即可被過(guò)濾掉。

對(duì)于兩個(gè)候選節(jié)點(diǎn)之間是否存在邊這一條件，可以利用訪問(wèn)順序解決，而不需要驗(yàn)證邊的存在：給定查詢圖，從查詢圖的軸心節(jié)點(diǎn)開始，依次訪問(wèn)軸心節(jié)點(diǎn)的鄰居，那么在數(shù)據(jù)圖中就會(huì)依次訪問(wèn)軸心候選節(jié)點(diǎn)的鄰居，無(wú)需訪問(wèn)非鄰居節(jié)點(diǎn)。

最后，需要驗(yàn)證得到的子圖是否和查詢圖符合子圖同構(gòu)的條件。總體的過(guò)濾和驗(yàn)證過(guò)程將在第4 章詳細(xì)介紹。

3 多編碼樹過(guò)濾

盡可能多地過(guò)濾掉查詢圖節(jié)點(diǎn)的候選節(jié)點(diǎn)是提高算法的執(zhí)行效率的有效途徑。對(duì)于無(wú)向圖而言，節(jié)點(diǎn)的標(biāo)簽和度是現(xiàn)有的許多編碼方式［20］都會(huì)利用的特征。但是對(duì)于大圖而言，這種編碼方式的過(guò)濾能力并不顯著。因此將節(jié)點(diǎn)的鄰居結(jié)構(gòu)組合到編碼中引起了很多人的研究興趣，然而如何在編碼鄰居結(jié)構(gòu)的同時(shí)保持編碼結(jié)果的簡(jiǎn)潔高效始終是一個(gè)難點(diǎn)問(wèn)題。本文利用節(jié)點(diǎn)的鄰居結(jié)構(gòu)特征，將鄰居節(jié)點(diǎn)的標(biāo)簽融入多編碼樹的特征值中，將復(fù)雜的結(jié)構(gòu)特征比較轉(zhuǎn)化為數(shù)值之間的比較，從而簡(jiǎn)化了鄰居結(jié)構(gòu)編碼，縮短了過(guò)濾過(guò)程的執(zhí)行時(shí)間。

編碼分為兩個(gè)部分，首先根據(jù)節(jié)點(diǎn)鄰居的結(jié)構(gòu)特征，對(duì)節(jié)點(diǎn)周圍的鄰居生成一棵固定層數(shù)的樹；其次是結(jié)合節(jié)點(diǎn)鄰居的標(biāo)簽，將節(jié)點(diǎn)的一棵樹分割成多棵樹。3.1 節(jié)和3.2 節(jié)將詳細(xì)介紹這兩部分內(nèi)容?；谶@兩部分的實(shí)現(xiàn)，本文方法將數(shù)據(jù)圖的節(jié)點(diǎn)與查詢圖的節(jié)點(diǎn)進(jìn)行編碼，得到查詢圖每個(gè)節(jié)點(diǎn)的候選節(jié)點(diǎn)。

算法1 生成n層無(wú)標(biāo)簽樹。

3.1 鄰居結(jié)構(gòu)特征

對(duì)于圖的每個(gè)節(jié)點(diǎn)，可根據(jù)其鄰居節(jié)點(diǎn)的結(jié)構(gòu)生成一棵固定層數(shù)的樹，節(jié)點(diǎn)本身作為根節(jié)點(diǎn)。算法1 展示了圖G中頂點(diǎn)v構(gòu)造成n層樹的步驟，以當(dāng)前節(jié)點(diǎn)為根，采用廣度優(yōu)先遍歷將其鄰居節(jié)點(diǎn)插入到樹中，生成n層樹。首先需要將當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)插入到樹中作為根的孩子，并標(biāo)記為已訪問(wèn)（4）行～5）行）。之后對(duì)當(dāng)前節(jié)點(diǎn)的每個(gè)鄰居節(jié)點(diǎn)各自執(zhí)行search 函數(shù)（6）行）生成多棵當(dāng)前節(jié)點(diǎn)的子樹，search 函數(shù)是一個(gè)遞歸函數(shù)，作用是將當(dāng)前節(jié)點(diǎn)的未被訪問(wèn)過(guò)的鄰居節(jié)點(diǎn)作為孩子插入樹中（9）行～19）行），直到樹的層數(shù)達(dá)到設(shè)定值（10）行）。

以圖2 為例，圖中對(duì)于圖1 中給定查詢圖Q和數(shù)據(jù)圖G，分別以u(píng)1和v1、v5為根節(jié)點(diǎn)生成一個(gè)2層的樹結(jié)構(gòu)。通過(guò)驗(yàn)證查詢圖節(jié)點(diǎn)生成的n層樹是否是數(shù)據(jù)圖節(jié)點(diǎn)生成的n層樹的子樹，來(lái)過(guò)濾掉不滿足的節(jié)點(diǎn)。因此本文可以利用鄰接矩陣表示n層樹結(jié)構(gòu)，對(duì)于n階矩陣存在n個(gè)特征值，GCoding（Graph Coding）［19］中對(duì)前2、3個(gè)，n個(gè)最大特征值進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明選擇前2 個(gè)最大特征值性能更優(yōu)。因此本文也選取鄰接矩陣的前2個(gè)最大特征值，即利用2個(gè)簡(jiǎn)單的數(shù)值來(lái)表示復(fù)雜的鄰居結(jié)構(gòu)。

圖2 查詢節(jié)點(diǎn)u1和數(shù)據(jù)節(jié)點(diǎn)v1、v5生成的2層樹結(jié)構(gòu)Fig.2 Two-level tree structures generated by query node u1 and data nodes v1，v5

3.2 鄰居標(biāo)簽特征

如果將給定圖中的每個(gè)頂點(diǎn)都根據(jù)算法1 生成一棵樹，將過(guò)濾掉數(shù)據(jù)圖中與查詢圖節(jié)點(diǎn)鄰居結(jié)構(gòu)不一致的節(jié)點(diǎn)。然而這種做法只考慮了鄰居結(jié)構(gòu)問(wèn)題，而沒(méi)有充分利用鄰居的標(biāo)簽信息。想要高效地過(guò)濾節(jié)點(diǎn)必須盡可能多地考慮節(jié)點(diǎn)以及節(jié)點(diǎn)鄰居的標(biāo)簽特征。

上述問(wèn)題帶來(lái)以下兩個(gè)挑戰(zhàn)：

1）每個(gè)節(jié)點(diǎn)的鄰居標(biāo)簽各不相同，將節(jié)點(diǎn)標(biāo)簽所有的可能情況排列組合，標(biāo)簽樹的總量必將過(guò)于龐大而難以實(shí)用。

2）如果對(duì)于每個(gè)頂點(diǎn)所生成的樹根據(jù)標(biāo)簽的類型進(jìn)行分割，將每種標(biāo)簽的鄰居節(jié)點(diǎn)組合生成一棵樹，這樣生成的標(biāo)簽樹內(nèi)容單一且數(shù)量不確定。這是因?yàn)槊總€(gè)頂點(diǎn)周圍的鄰居標(biāo)簽有幾類就會(huì)生成幾棵樹，并且對(duì)于數(shù)據(jù)圖標(biāo)簽種類較多的情況生成樹的數(shù)量會(huì)更多，難以編碼。

面對(duì)以上挑戰(zhàn)，本文提出了一種多標(biāo)簽的編碼樹方式：用二進(jìn)制數(shù)來(lái)表示標(biāo)簽，如果圖中共有n種標(biāo)簽，則可以設(shè)置不超過(guò)n個(gè)標(biāo)簽桶，將每種標(biāo)簽按一定形式（哈希、等分等）歸入一個(gè)標(biāo)簽桶中，每個(gè)標(biāo)簽桶按順序從1 開始編號(hào)。然后將標(biāo)簽桶序號(hào)二進(jìn)制形式第i位為1 的所有標(biāo)簽桶歸為第i組，共有組。同一個(gè)標(biāo)簽桶組的所有標(biāo)簽類型的鄰居節(jié)點(diǎn)將被用來(lái)生成同一棵樹。

例如，在一個(gè)包含30 種標(biāo)簽的圖中，最多可以生成30 個(gè)標(biāo)簽桶，進(jìn)而產(chǎn)生=5 個(gè)標(biāo)簽桶組，每個(gè)標(biāo)簽桶組生成一棵樹，最終每個(gè)節(jié)點(diǎn)可生成5 棵樹。除此之外，本文還生成1 棵由算法1 所生成的不考慮鄰居節(jié)點(diǎn)標(biāo)簽的樹。

然而，對(duì)于給定的n種標(biāo)簽，也可以生成少于n個(gè)標(biāo)簽桶。具體生成多少標(biāo)簽桶將參照實(shí)驗(yàn)結(jié)果進(jìn)行討論。表1給出了30 個(gè)標(biāo)簽哈希到3 個(gè)標(biāo)簽桶中生成2 棵樹的情況，其中桶ID 由1～3 表示，每個(gè)桶ID 由兩位二進(jìn)制數(shù)表示，根據(jù)每個(gè)節(jié)點(diǎn)標(biāo)簽所在的桶ID 的各個(gè)位置上是否為1 分成相應(yīng)的標(biāo)簽桶組，兩位二進(jìn)制數(shù)可以分成兩個(gè)標(biāo)簽桶組（只考慮各個(gè)位置為1 的情況），因此可以生成2 棵樹。

表1 30個(gè)標(biāo)簽哈希到標(biāo)簽桶中生成2棵樹Tab.1 Thirty labels hashing into label buckets to generate 2 trees

雖然編碼節(jié)點(diǎn)本身在生成樹的時(shí)候不考慮節(jié)點(diǎn)標(biāo)簽，但由于節(jié)點(diǎn)本身的標(biāo)簽和度會(huì)單獨(dú)進(jìn)行編碼，因此這樣做并不會(huì)影響過(guò)濾效果。在進(jìn)行比較操作時(shí)，只需對(duì)同類型的樹得到的特征值相互比較，因此可以實(shí)現(xiàn)較高的過(guò)濾效率。采用這種方式對(duì)樹進(jìn)行切割，包含了所有標(biāo)簽的可能情況，并且每一棵樹都能覆蓋到圖中一半的標(biāo)簽，增強(qiáng)了過(guò)濾效果。

算法2 生成同類標(biāo)簽樹。

算法2 描述了標(biāo)簽樹的生成過(guò)程：以當(dāng)前節(jié)點(diǎn)為根，采用深度優(yōu)先遍歷的方式將其鄰居節(jié)點(diǎn)插入到滿足條件的多棵標(biāo)簽樹中，從而生成多個(gè)n層標(biāo)簽樹。依據(jù)算法1 生成一棵無(wú)標(biāo)簽樹，然后保持根節(jié)點(diǎn)不變生成多棵標(biāo)簽樹（1）行～3）行），之后遞歸遍歷無(wú)標(biāo)簽樹（4）行），根據(jù)flag確定節(jié)點(diǎn)屬于哪棵標(biāo)簽樹（11）行～14）行）。通過(guò)findAncestors 函數(shù)找到與目前節(jié)點(diǎn)相連的父節(jié)點(diǎn)，如果父節(jié)點(diǎn)不存在，則繼續(xù)向上查找直到根節(jié)點(diǎn)。

圖3 給出了本文方法的一個(gè)示例。根據(jù)圖1 中標(biāo)簽類型，將各種標(biāo)簽哈希到相應(yīng)的桶中，并根據(jù)相應(yīng)的桶ID 來(lái)確定標(biāo)簽樹。由圖3 可見，軸心u1和候選節(jié)點(diǎn)v1具有相近的鄰居結(jié)構(gòu)，而與v5的鄰居結(jié)構(gòu)差異則較大。圖節(jié)點(diǎn)的每棵樹都要轉(zhuǎn)化為鄰接矩陣并求其特征值，選擇前兩個(gè)最大的特征值作為特征進(jìn)行編碼。本文方法將頂點(diǎn)的標(biāo)簽、度以及頂點(diǎn)鄰居生成的標(biāo)簽樹的特征值組合起來(lái)表示為Tcoding={label，degree，seq={a1，a2，b1，b2，…}}。編碼可 以采用脫機(jī)處理的方式進(jìn)行預(yù)計(jì)算。

圖3 查詢節(jié)點(diǎn)u1和數(shù)據(jù)節(jié)點(diǎn)v1，v5生成的標(biāo)簽樹Fig.3 Label trees generated by query node u1 and data nodes v1，v5

對(duì)于查詢圖中的每一個(gè)節(jié)點(diǎn)的多標(biāo)簽樹，在過(guò)濾過(guò)程中將其前兩個(gè)最大特征值與數(shù)據(jù)圖中節(jié)點(diǎn)的多標(biāo)簽樹特征值進(jìn)行比較。當(dāng)數(shù)據(jù)圖中的節(jié)點(diǎn)的頂點(diǎn)編碼與查詢圖的節(jié)點(diǎn)的頂點(diǎn)編碼符合如下條件才可以被存入查詢圖節(jié)點(diǎn)的候選集：1）節(jié)點(diǎn)標(biāo)簽必須相同；2）查詢圖節(jié)點(diǎn)的度必須小于等于數(shù)據(jù)圖節(jié)點(diǎn)的度；3）查詢圖節(jié)點(diǎn)生成的每棵標(biāo)簽樹對(duì)應(yīng)的特征值必須小于等于數(shù)據(jù)圖節(jié)點(diǎn)生成的每棵標(biāo)簽樹對(duì)應(yīng)的特征值。

算法3 編碼過(guò)濾。

算法3 給出了編碼過(guò)濾的過(guò)程。首先初始化查詢圖節(jié)點(diǎn)的候選集（1）行～3）行）；其次按照查詢圖節(jié)點(diǎn)訪問(wèn)順序依次訪問(wèn)，每個(gè)查詢圖節(jié)點(diǎn)與數(shù)據(jù)圖節(jié)點(diǎn)并行比較編碼，將符合條件的數(shù)據(jù)圖節(jié)點(diǎn)存入候選集（4）行～10）行）。GPU 中的并行處理方式是以線程束為單位，每個(gè)線程束包含的32 個(gè)線程內(nèi)部以并行方式同時(shí)處理一個(gè)查詢圖節(jié)點(diǎn)與32 個(gè)數(shù)據(jù)圖節(jié)點(diǎn)之間的比較操作，過(guò)濾掉不滿足的數(shù)據(jù)圖節(jié)點(diǎn)，并將過(guò)濾結(jié)果合并存儲(chǔ)。這種高效的編碼過(guò)濾過(guò)程很大程度上減少了過(guò)濾所需的時(shí)間。圖4 給出了查詢圖Q和數(shù)據(jù)圖G每個(gè)節(jié)點(diǎn)的編碼，依據(jù)上述條件進(jìn)行比較可以得到過(guò)濾后的每個(gè)查詢圖節(jié)點(diǎn)的候選集分別為u1={v1}，u2={v2}，u3={v3}，u4={v2，v4}。

圖4 查詢圖Q與數(shù)據(jù)圖G的節(jié)點(diǎn)編碼Fig.4 Node coding of query graph Q and data graph G

4 二次過(guò)濾和驗(yàn)證

4.1 過(guò)濾規(guī)則

給定查詢圖Q和數(shù)據(jù)圖G以及查詢圖節(jié)點(diǎn)的訪問(wèn)順序，以查詢圖軸心為起始節(jié)點(diǎn)，依次訪問(wèn)軸心的鄰居，數(shù)據(jù)圖中同樣以軸心候選節(jié)點(diǎn)為起始節(jié)點(diǎn)，依次訪問(wèn)鄰居節(jié)點(diǎn)，這樣就可以直接過(guò)濾掉與軸心候選節(jié)點(diǎn)之間不存在邊的候選節(jié)點(diǎn)，同樣地，隨后每一層的節(jié)點(diǎn)都必須是上一層已匹配節(jié)點(diǎn)的鄰居。

4.2 驗(yàn)證規(guī)則

給定查詢圖Q和數(shù)據(jù)圖G，將已匹配的查詢圖節(jié)點(diǎn)ui以及其在數(shù)據(jù)圖中的匹配節(jié)點(diǎn)vi存入匹配序列seq={(u1，v1)，(u2，v2)，…，(ui，vi)，…}。將當(dāng)前查詢圖節(jié)點(diǎn)的鄰居在匹配序列中的位置存入集合SQ中，并將其匹配的數(shù)據(jù)圖的節(jié)點(diǎn)的鄰居在匹配序列中的位置存入集合SG中，匹配過(guò)程中必須滿足SQ是SG的子集。

每個(gè)查詢圖節(jié)點(diǎn)得到的候選集都可以生成一棵搜索空間樹，每一層都是查詢圖節(jié)點(diǎn)的候選集。遍歷搜索空間樹的過(guò)程中，本文方法將剪枝和驗(yàn)證過(guò)程相結(jié)合，分別從查詢圖軸心和其在數(shù)據(jù)圖中的候選節(jié)點(diǎn)開始，按照鄰居節(jié)點(diǎn)順序依次訪問(wèn)。對(duì)于每個(gè)查詢圖節(jié)點(diǎn)的候選集，根據(jù)過(guò)濾規(guī)則必須是當(dāng)前查詢圖節(jié)點(diǎn)的被訪問(wèn)過(guò)的父節(jié)點(diǎn)的鄰居。本文利用GPU 并行剪枝掉不滿足的節(jié)點(diǎn)，同時(shí)根據(jù)驗(yàn)證規(guī)則對(duì)已匹配序列中當(dāng)前查詢節(jié)點(diǎn)鄰居的位置進(jìn)行驗(yàn)證。驗(yàn)證采用深度優(yōu)先遍歷的方式，直到所有查詢圖節(jié)點(diǎn)均被訪問(wèn)過(guò)，如果得到一個(gè)查詢圖的有效匹配，則軸心的這個(gè)候選節(jié)點(diǎn)就是軸心子圖同構(gòu)的解之一。將軸心的候選節(jié)點(diǎn)依次驗(yàn)證，最終得到軸心的所有匹配。圖5 給出了單個(gè)軸心候選節(jié)點(diǎn)的驗(yàn)證過(guò)程。對(duì)于單個(gè)軸心候選節(jié)點(diǎn)，依據(jù)過(guò)濾規(guī)則將下一層中所有不是其鄰居的候選節(jié)點(diǎn)過(guò)濾掉，再在這一層中選擇剩余候選節(jié)點(diǎn)中的一個(gè)節(jié)點(diǎn)繼續(xù)往下一層進(jìn)行過(guò)濾，其中每一層都進(jìn)行了并行剪枝，并對(duì)剪枝后的候選節(jié)點(diǎn)進(jìn)行驗(yàn)證。如果某一層的一個(gè)節(jié)點(diǎn)不滿足驗(yàn)證規(guī)則，轉(zhuǎn)而尋找該層的下一個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行驗(yàn)證，直至最后一層，仍然有滿足驗(yàn)證規(guī)則的節(jié)點(diǎn)，則得到了一個(gè)有效的子圖匹配。如果某一層的所有節(jié)點(diǎn)都無(wú)法滿足驗(yàn)證規(guī)則，那么無(wú)法得到查詢圖的有效匹配，則此軸心候選節(jié)點(diǎn)為無(wú)效節(jié)點(diǎn)。

圖5 單個(gè)軸心候選節(jié)點(diǎn)的驗(yàn)證過(guò)程Fig.5 Validation process of one pivoted candidate node

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

本章通過(guò)實(shí)驗(yàn)對(duì)本文提出的算法進(jìn)行性能分析。由于目前唯一的針對(duì)軸心子圖同構(gòu)進(jìn)行了優(yōu)化的Smart PSI 是一種傳統(tǒng)的基于CPU 的方法，難以有效利用GPU 等新硬件的大規(guī)模并行處理能力。實(shí)驗(yàn)中將目前最先進(jìn)的基于GPU 的子圖同構(gòu)算法GpSM 與本文算法進(jìn)行比較。

本文選用了兩個(gè)有著不同的結(jié)構(gòu)和尺寸的真實(shí)數(shù)據(jù)集，其中Human 數(shù)據(jù)集［21］包含4 674 個(gè)節(jié)點(diǎn)、86 282 個(gè)邊以及44種節(jié)點(diǎn)標(biāo)簽，Hprd 數(shù)據(jù)集［21］包含9 460 個(gè)節(jié)點(diǎn)、34 998 個(gè)邊以及307 種節(jié)點(diǎn)標(biāo)簽。顯然Human 數(shù)據(jù)集是一個(gè)稠密數(shù)據(jù)集，每個(gè)節(jié)點(diǎn)連接約19 條邊；而Hprd 數(shù)據(jù)集是一個(gè)稀疏數(shù)據(jù)集，每個(gè)節(jié)點(diǎn)連接約4 條邊。在實(shí)驗(yàn)測(cè)試中使用的都是無(wú)向圖，且這兩個(gè)數(shù)據(jù)集均沒(méi)有邊標(biāo)簽。

本文在數(shù)據(jù)圖中隨機(jī)選擇一系列連通子圖作為查詢圖，并且隨機(jī)選擇其中的一個(gè)節(jié)點(diǎn)為軸心。由于Human 數(shù)據(jù)集是稠密數(shù)據(jù)集，本文將查詢圖的尺寸指定為4、8、12、16、20個(gè)節(jié)點(diǎn)，對(duì)于Hprd 數(shù)據(jù)集，指定查詢圖的尺寸為8、16、24、32個(gè)節(jié)點(diǎn)。

所有代碼都由C++實(shí)現(xiàn)，運(yùn)行在CUDA Toolkit 10.6、NVIDIA GeForce 940MX GPU 上。

5.1 k的影響

圖6 給出了在Human 數(shù)據(jù)集中不同棵樹的過(guò)濾能力的實(shí)驗(yàn)結(jié)果。Human 有44 種標(biāo)簽，最多能夠生成6 棵標(biāo)簽樹，每棵標(biāo)簽樹都是在生成2 層樹的前提下執(zhí)行的。無(wú)論查詢圖的尺寸大小，在6 棵樹的情況下所能過(guò)濾的候選節(jié)點(diǎn)更多。這是因?yàn)? 棵標(biāo)簽樹可以包含數(shù)據(jù)圖中的所有標(biāo)簽種類，產(chǎn)生更多的過(guò)濾條件。而只有1 棵樹則過(guò)于單調(diào)，只考慮節(jié)點(diǎn)鄰居結(jié)構(gòu)沒(méi)有考慮節(jié)點(diǎn)鄰居標(biāo)簽信息。其他的樹均沒(méi)有充分利用節(jié)點(diǎn)鄰居標(biāo)簽和結(jié)構(gòu)，因此得到的過(guò)濾效果比6 棵樹較差。

圖6 不同棵樹在Human數(shù)據(jù)集上對(duì)于候選節(jié)點(diǎn)的過(guò)濾能力Fig.6 Filtering ability to candidate nodes with different tree numbers on Human dataset

5.2 和GpSM比較

本文通過(guò)實(shí)驗(yàn)來(lái)比較軸心子圖同構(gòu)算法與GpSM 算法的性能，對(duì)于不同的查詢圖尺寸和不同的數(shù)據(jù)圖尺寸（Human 和Hprd 數(shù)據(jù)集中固定查詢圖尺寸分別為12、16）分別給出了兩個(gè)算法的實(shí)驗(yàn)結(jié)果。

本文將性能比較分為三個(gè)方面，分別為過(guò)濾能力、過(guò)濾時(shí)間以及整個(gè)算法執(zhí)行時(shí)間。圖7（a）給出了在查詢圖尺寸為4、8、12、16、20 的情況下在Human 數(shù)據(jù)集中的候選節(jié)點(diǎn)的個(gè)數(shù)。軸心子圖同構(gòu)算法的過(guò)濾效果隨著查詢圖尺寸增加趨于穩(wěn)定，與GpSM 保持著較小的差距。其中12-tree 是前文中提到的在6-tree 上所做的擴(kuò)展，其性能有較小的提升。圖7（b）給出了在數(shù)據(jù)圖尺寸為1 000、2 000、3 000、4 000、5 000的情況下在Human 數(shù)據(jù)集中的候選節(jié)點(diǎn)的個(gè)數(shù)。隨著數(shù)據(jù)集尺寸的增大，軸心子圖同構(gòu)算法的過(guò)濾效果依然趨于穩(wěn)定，沒(méi)有增大與GpSM 算法過(guò)濾效果的差距。

圖7 Human數(shù)據(jù)集上過(guò)濾后的候選節(jié)點(diǎn)Fig.7 Filtered candidate nodes on Human dataset

圖8（a）給出了在查詢圖尺寸為4、8、12、16、20 的情況下在Human 數(shù)據(jù)集上的過(guò)濾時(shí)間。圖8（b）給出了在查詢圖尺寸為8、16、24、32 的情況下在Hprd 數(shù)據(jù)集上的過(guò)濾時(shí)間。隨著查詢圖尺寸的增大，軸心子圖同構(gòu)算法的過(guò)濾時(shí)間幾乎沒(méi)有增長(zhǎng)，而GpSM 算法的過(guò)濾時(shí)間大幅增加。這是因?yàn)檩S心子圖同構(gòu)算法中的過(guò)濾階段是通過(guò)GPU 并行處理每一個(gè)查詢節(jié)點(diǎn)，并且過(guò)濾使用的編碼是簡(jiǎn)單的數(shù)值比較，所以過(guò)濾的時(shí)間消耗相對(duì)較少，并且不會(huì)有太大的變化。而GpSM 算法是通過(guò)構(gòu)建查詢圖的最小生成樹，隨著查詢圖尺寸的增加，構(gòu)建的最小生成樹便隨著增大，且時(shí)間消耗也會(huì)隨之增加。同樣的，12-tree 是6-tree 的擴(kuò)展，其過(guò)濾時(shí)間和6-tree 的過(guò)濾時(shí)間相差無(wú)幾。圖8（c）展現(xiàn)了數(shù)據(jù)圖尺寸為1 000、2 000、3 000、4 000、5 000 的情況下在Human 數(shù)據(jù)集上軸心子圖同構(gòu)算法的過(guò)濾時(shí)間。圖8（d）展現(xiàn)了數(shù)據(jù)圖尺寸為2 000、4 000、6 000、8 000、10 000 的情況下在Hprd 數(shù)據(jù)集上軸心子圖同構(gòu)算法的過(guò)濾時(shí)間。隨著數(shù)據(jù)集尺寸的增大，軸心子圖同構(gòu)算法的過(guò)濾時(shí)間只有小幅的增長(zhǎng)，而GpSM 算法的過(guò)濾時(shí)間有著相對(duì)大幅的增加。數(shù)據(jù)集的尺寸大小會(huì)影響查詢圖中每個(gè)節(jié)點(diǎn)過(guò)濾所需的時(shí)間，并且當(dāng)數(shù)據(jù)集的尺寸逐漸增大時(shí)，GpSM 通過(guò)最小生成樹的訪問(wèn)順序過(guò)濾后得到的候選集尺寸增大，從而影響過(guò)濾時(shí)間。

圖8 不同數(shù)據(jù)集上算法的過(guò)濾時(shí)間Fig.8 Filtering time of algorithms on different datasets

圖9（a）給出了在查詢圖尺寸為4、8、12、16、20 的情況下在Human 數(shù)據(jù)集上的整個(gè)算法執(zhí)行時(shí)間。圖9（b）給出了在查詢圖尺寸為8、16、24、32 的情況下，在Hprd 數(shù)據(jù)集上的整個(gè)算法執(zhí)行時(shí)間。隨著查詢圖尺寸的增加，GpSM 算法執(zhí)行時(shí)間呈線性增長(zhǎng)，而軸心子圖同構(gòu)算法的執(zhí)行時(shí)間是先相對(duì)平穩(wěn)再趨于線性增長(zhǎng)，但總體時(shí)間要少于GpSM 算法。這是因?yàn)榕c軸心子圖同構(gòu)算法相比，GpSM 算法的過(guò)濾和連接都要低效，連接過(guò)程需要將邊的候選節(jié)點(diǎn)選出并存入哈希表中，而這是非常耗時(shí)的。圖9（c）給出了數(shù)據(jù)圖尺寸為1 000、2 000、3 000、4 000、5 000 的情況下在Human 數(shù)據(jù)集上軸心子圖同構(gòu)算法執(zhí)行的總時(shí)間。圖9（d）給出了數(shù)據(jù)圖尺寸為2 000、4 000、6 000、8 000、10 000 的情況下在Hprd 數(shù)據(jù)集上軸心子圖同構(gòu)算法執(zhí)行的總時(shí)間。隨著數(shù)據(jù)集尺寸的增加，算法耗時(shí)都趨于線性增長(zhǎng)。這是因?yàn)閿?shù)據(jù)集尺寸的增加會(huì)增大GpSM 算法過(guò)濾后得到的候選集尺寸，間接增大了連接階段的邊的候選集的尺寸，使得邊的候選集存入哈希表的時(shí)間也會(huì)相應(yīng)增加，影響了算法的執(zhí)行時(shí)間。

圖9 不同數(shù)據(jù)集上的算法執(zhí)行總時(shí)間Fig.9 Total execution time of algorithms on different datasets

6 結(jié)語(yǔ)

本文提出了一種新穎的多編碼樹過(guò)濾方式，將鄰居結(jié)構(gòu)和鄰居節(jié)點(diǎn)標(biāo)簽轉(zhuǎn)化為多個(gè)包含標(biāo)簽信息的編碼樹，用特征值表示標(biāo)簽樹的結(jié)構(gòu)，結(jié)合節(jié)點(diǎn)特征以及不同標(biāo)簽樹的特征值得到每個(gè)節(jié)點(diǎn)的編碼；通過(guò)GPU 并行比較每個(gè)查詢節(jié)點(diǎn)與數(shù)據(jù)節(jié)點(diǎn)的編碼進(jìn)行過(guò)濾，減小了軸心子圖同構(gòu)算法生成的搜索空間樹的規(guī)模。在此基礎(chǔ)上，本文提出了軸心子圖同構(gòu)算法，結(jié)合過(guò)濾和驗(yàn)證方式，并行處理每個(gè)查詢節(jié)點(diǎn)由多編碼樹過(guò)濾后的候選節(jié)點(diǎn)，驗(yàn)證子圖是否是查詢圖的有效匹配，最終得到軸心的所有有效匹配節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明本文算法在過(guò)濾效果上相對(duì)穩(wěn)定且與GpSM 有著較小的差距，在過(guò)濾時(shí)間和算法總體時(shí)間上要優(yōu)于當(dāng)前最先進(jìn)的基于GPU的GpSM 算法。