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

（東北大學計算機科學與工程學院，沈陽 110169）

0 引言

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

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

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

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

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

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

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

本文的主要工作如下：

1）提出了一種標簽樹結構。利用二進制數表示圖標簽種類，根據各位上的數值不同，生成不同類型的標簽樹，從而盡可能多地展現出每個節(jié)點的鄰居節(jié)點的結構特征以及鄰居節(jié)點標簽的組合情況。

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

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

1 預備知識

定義1子圖同構。給定一個查詢圖Q={VQ，EQ，LQ}和數據圖G={VG，EG，LG}，其中VQ、VG是頂點的集合，EQ、EG是邊的集合，LQ、LG是將頂點映射到相應標簽的標簽函數。子圖同構即存在一個單射函數f：VQ→VG，對于查詢圖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軸心子圖同構。給定一個查詢圖Q={VQ，EQ，LQ}，軸心up∈VQ以及數據圖G={VG，EG，LG}，軸心vp∈VG，存在一個單射函數f：VQ→VG，軸心子圖同構需要滿足如下三個條件：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)。

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

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

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

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

2 總體結構

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

2.1 編碼過濾

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

本文通過標簽編碼樹的方式將鄰居節(jié)點標簽應用到鄰居結構上，以增強過濾能力。事實上，每個節(jié)點都可以根據其鄰居結構生成一棵無標簽樹。然而鄰居節(jié)點的標簽可能不同，僅生成無標簽樹無法進行有效的比較。因此本文根據標簽類型對樹進行切割，將同一類標簽的節(jié)點放到一棵樹中。

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

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

標簽樹將原本的無標簽樹按照同標簽組合原則進行分割，加強了過濾條件，使其不僅需要滿足結構特征也要滿足標簽特征。由于對于每個節(jié)點的切割規(guī)則是相同的，所以每個節(jié)點所產生樹的數目相同，在比較時通過對應的標簽樹的特征值進行比較，即可過濾掉不滿足的節(jié)點。

2.2 過濾和驗證

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

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

最后，需要驗證得到的子圖是否和查詢圖符合子圖同構的條件?？傮w的過濾和驗證過程將在第4 章詳細介紹。

3 多編碼樹過濾

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

編碼分為兩個部分，首先根據節(jié)點鄰居的結構特征，對節(jié)點周圍的鄰居生成一棵固定層數的樹；其次是結合節(jié)點鄰居的標簽，將節(jié)點的一棵樹分割成多棵樹。3.1 節(jié)和3.2 節(jié)將詳細介紹這兩部分內容?；谶@兩部分的實現，本文方法將數據圖的節(jié)點與查詢圖的節(jié)點進行編碼，得到查詢圖每個節(jié)點的候選節(jié)點。

算法1 生成n層無標簽樹。

3.1 鄰居結構特征

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

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

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

3.2 鄰居標簽特征

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

上述問題帶來以下兩個挑戰(zhàn)：

1）每個節(jié)點的鄰居標簽各不相同，將節(jié)點標簽所有的可能情況排列組合，標簽樹的總量必將過于龐大而難以實用。

2）如果對于每個頂點所生成的樹根據標簽的類型進行分割，將每種標簽的鄰居節(jié)點組合生成一棵樹，這樣生成的標簽樹內容單一且數量不確定。這是因為每個頂點周圍的鄰居標簽有幾類就會生成幾棵樹，并且對于數據圖標簽種類較多的情況生成樹的數量會更多，難以編碼。

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

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

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

表1 30個標簽哈希到標簽桶中生成2棵樹Tab.1 Thirty labels hashing into label buckets to generate 2 trees

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

算法2 生成同類標簽樹。

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

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

圖3 查詢節(jié)點u1和數據節(jié)點v1，v5生成的標簽樹Fig.3 Label trees generated by query node u1 and data nodes v1，v5

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

算法3 編碼過濾。

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

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

4 二次過濾和驗證

4.1 過濾規(guī)則

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

4.2 驗證規(guī)則

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

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

圖5 單個軸心候選節(jié)點的驗證過程Fig.5 Validation process of one pivoted candidate node

5 實驗結果

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

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

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

所有代碼都由C++實現，運行在CUDA Toolkit 10.6、NVIDIA GeForce 940MX GPU 上。

5.1 k的影響

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

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

5.2 和GpSM比較

本文通過實驗來比較軸心子圖同構算法與GpSM 算法的性能，對于不同的查詢圖尺寸和不同的數據圖尺寸（Human 和Hprd 數據集中固定查詢圖尺寸分別為12、16）分別給出了兩個算法的實驗結果。

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

圖7 Human數據集上過濾后的候選節(jié)點Fig.7 Filtered candidate nodes on Human dataset

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

圖8 不同數據集上算法的過濾時間Fig.8 Filtering time of algorithms on different datasets

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

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

6 結語

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