朱 磊,姚燕妮，高 勇，王一川，姬文江，黑新宏，劉 征

(1.西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710048；2.西安理工大學(xué) 自動(dòng)化與信息工程學(xué)院，陜西 西安 710048)

圖被大規(guī)模用于構(gòu)造半結(jié)構(gòu)或非結(jié)構(gòu)化的數(shù)據(jù)和語義。例如，化學(xué)[1]、社交網(wǎng)絡(luò)[2]、知識(shí)圖譜[3]、XML文件[4]等。在這些應(yīng)用中，實(shí)體和關(guān)系被建模為圖模型，并構(gòu)建更加高效的半結(jié)構(gòu)或非結(jié)構(gòu)化的圖數(shù)據(jù)庫，然后應(yīng)用圖挖據(jù)相關(guān)技術(shù)去高效智能地檢索事物間的關(guān)聯(lián)關(guān)系[5]。

圖數(shù)據(jù)庫相關(guān)領(lǐng)域中，子圖查詢過程包含子圖同構(gòu)的判定，而該問題已經(jīng)證明是NP完全問題[6]，所以現(xiàn)存的方法均采用過濾-驗(yàn)證框架，而且提取高效的圖特征進(jìn)行過濾已成為子圖查詢的重要研究方向。一些現(xiàn)存的方法主要采用數(shù)據(jù)挖掘的理論去提取頻繁子結(jié)構(gòu)作為特征，并使用倒排序的索引進(jìn)行過濾[7,8]。但是這類方法在圖數(shù)據(jù)頻繁更新時(shí)，必須重新挖掘頻繁子結(jié)構(gòu)和建立索引，導(dǎo)致代價(jià)過大[9]。

針對(duì)無向加權(quán)圖，本文提出了一種子圖查詢方法PSQuery，提取的主要特征包括：節(jié)點(diǎn)標(biāo)記、邊、最短權(quán)值路徑和拉普拉斯圖譜信息。將這些信息特征分別按照不同方法進(jìn)行編碼，形成節(jié)點(diǎn)和圖編碼，基于圖編碼構(gòu)建索引樹進(jìn)行過濾。在遍歷索引樹后生成候選圖集合，再采用經(jīng)典VF2算法進(jìn)行子圖同構(gòu)驗(yàn)證，得到最終的結(jié)果集。通過在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比，驗(yàn)證了本文所提方法提高了子圖查詢的效率。同時(shí)，由于PSQuery方法不以頻繁子結(jié)構(gòu)作為圖的特征，因此提出的方法可以很好地處理圖庫頻繁更新的情況。

1 相關(guān)工作

定義：(無向加權(quán)圖)給定無向加權(quán)圖G=〈VS,ES〉，其中VS和ES分別為節(jié)點(diǎn)集合和邊集合。圖中每個(gè)節(jié)點(diǎn)v可以建模為二元組〈vid，vlable〉，表示節(jié)點(diǎn)的ID和標(biāo)記。每條邊e建模為三元組〈vi，ew，vj〉，用于表示節(jié)點(diǎn)vi和vj間的無向邊，其邊權(quán)值為ew。

定義：(子圖查詢)給定一個(gè)圖數(shù)據(jù)庫D和一個(gè)查詢圖Q，其中數(shù)據(jù)集包含n個(gè)數(shù)據(jù)圖,D={G1,G2, …,Gn}。子圖查詢的目標(biāo)是在D中找到Q的所有超圖集合。

在具體查詢過程中，涉及的難點(diǎn)是查詢中包含了子圖同構(gòu)的判定，而該問題已經(jīng)被證明是NP完全問題。所以，現(xiàn)存的方法通常采用過濾-驗(yàn)證框架去加速子圖查詢過程，目的是減少子圖同構(gòu)判定的次數(shù)。

在子圖查詢的相關(guān)工作中，Closure-Tree方法將相同子結(jié)構(gòu)聚簇為閉包，并且對(duì)閉包建立索引樹[10]。在遍歷索引樹時(shí)進(jìn)行過濾，將不符合條件的閉包刪除，生成候選圖；在過濾時(shí)，采用子圖同構(gòu)的判定方法進(jìn)行驗(yàn)證，得到結(jié)果集。但是，該方法在過濾時(shí)采用類似子圖同構(gòu)的判定方法進(jìn)行檢測(cè)，導(dǎo)致該方法在過濾階段花費(fèi)較高的代價(jià)[9]。

為了減少過濾階段的判定開銷，一些方法使用數(shù)據(jù)挖掘的算法，提取頻繁子結(jié)構(gòu)建立倒序索引。在遍歷索引時(shí)，對(duì)查詢圖不包含的頻繁子結(jié)構(gòu)進(jìn)行過濾，通過子圖同構(gòu)算法進(jìn)行驗(yàn)證得到結(jié)果集。例如，Graphgrep[11]采用路徑建立索引。而gIndex[7]、Swiftindex[8]、FG-gindex[12]、Treepi[13]等方法挖掘頻繁子圖或者子樹作為索引特征。這類方法在構(gòu)建索引的過程中花費(fèi)的代價(jià)較大，所以在圖數(shù)據(jù)頻繁更新時(shí)，這類算法由于必須重新挖掘頻繁子結(jié)構(gòu)和建立索引，導(dǎo)致代價(jià)過大[9]。

為了避免上述問題，第三類方法是將圖的結(jié)構(gòu)信息映射到數(shù)字空間，使用表示學(xué)習(xí)的方法生成編碼，并且在編碼的基礎(chǔ)上建立索引。這類方法包括了GCoding[9]和LsGCoding[14]方法。但是，這些方法提取的結(jié)構(gòu)特征或者缺失環(huán)路信息(例如GCoding提取的樹形結(jié)構(gòu))，或者提取的邊不包含權(quán)值信息(例如LsGCoding只能提取無權(quán)邊的圖譜)，這些都會(huì)在處理無向加權(quán)邊的圖數(shù)據(jù)庫時(shí)，導(dǎo)致查詢的性能降低[14]。

針對(duì)無向加權(quán)圖數(shù)據(jù)庫，G-CORE方法使用路徑信息特征，提高了無向加權(quán)圖的推理和計(jì)算的效率[15]。受此啟發(fā)，本文將加權(quán)路徑信息和拉普拉斯圖譜信息提取出來，按照表示學(xué)習(xí)方法的思路，提出了無向加權(quán)圖的子圖查詢方法PSQuery，來提高無向加權(quán)邊圖集的查詢效率。

2 PSQuery編碼和索引方法

本文提出的PSQuery方法的處理流程如圖1所示。

圖1 過濾-驗(yàn)證框架

不同于GCoding和LsGCoding方法，本文將最短權(quán)值路徑和圖譜作為新特征去加速無向加權(quán)圖的處理過程。首先，對(duì)圖數(shù)據(jù)庫中每個(gè)圖的節(jié)點(diǎn)、邊、最短權(quán)值路徑和拉普拉斯圖譜進(jìn)行提取，并且將其編碼生成數(shù)據(jù)圖碼，同時(shí)建立索引樹和數(shù)據(jù)圖庫。接著，對(duì)查詢圖進(jìn)行編碼，生成對(duì)應(yīng)的查詢數(shù)據(jù)圖碼。然后，按照過濾-驗(yàn)證框架進(jìn)行查詢處理。需要注意的是，PSQuery方法不僅在過濾過程中使用了新的特征編碼比較，并且在驗(yàn)證過程中將最短路徑信息也作為判定規(guī)則，目的是提高方法的整體查詢效率。

2.1 圖譜及路徑的相關(guān)性質(zhì)

定義：(鄰接矩陣和Laplacian矩陣)給出一個(gè)無向加權(quán)圖G，其鄰接權(quán)值矩陣和Laplacian矩陣表示為WG和LG。具體的構(gòu)成為：

其中，ew為相連節(jié)點(diǎn)之間的路徑權(quán)值。根據(jù)上述矩陣的定義，可以計(jì)算出圖G中的最短權(quán)值路徑矩陣和對(duì)應(yīng)的圖譜信息。

定義：(圖譜和Laplacian圖譜)給出一個(gè)無向加權(quán)圖G，對(duì)應(yīng)的Laplacian矩陣LG的特征值序列稱為G的Laplacian圖譜。

對(duì)于無向加權(quán)圖，應(yīng)用權(quán)值路徑信息和Laplacian圖譜的性質(zhì)，即路徑權(quán)值和圖譜的嵌套定理可以進(jìn)行過濾操作[16,17]。

定理：(路徑權(quán)值的嵌套定理)給出兩個(gè)無向加權(quán)圖G1和G2，G1是G2的子圖，并且G1中任意兩個(gè)節(jié)點(diǎn)vi和vj，G2中與之對(duì)應(yīng)的節(jié)點(diǎn)為v’i和v’j。如果vi和vj之間的最短權(quán)值路徑為αk，v’i和v’j之間的最短權(quán)值路徑為α’k，那么它們的路徑的權(quán)值應(yīng)滿足αk≥α’k。

定理：(圖譜的嵌套定理)給出兩個(gè)無向加權(quán)圖G1和G2，其Laplacian矩陣分別表示為L(zhǎng)Am×m和LBn×n(m≤n)。其中LAm×m的特征值為λm-1≤λm-2≤…≤λ1≤λ0，LBn×n的特征值表示為βn-1≤βn-2≤…≤β1≤β0。如果G1是G2的子圖，那么它們的特征值滿足λk≤βk，k=0,1,…,m-1。

基于統(tǒng)計(jì)學(xué)規(guī)律，無向加權(quán)圖中節(jié)點(diǎn)標(biāo)記和邊的個(gè)數(shù)也具有相似的性質(zhì)，即通過數(shù)值比較進(jìn)行過濾操作。在GCoding和LsGCoding方法中，這兩種基本特征已被提取為圖的特征編碼[9,14]。根據(jù)特征進(jìn)行編碼的操作效率高，所以PSQuery提取這4個(gè)圖屬性作為索引特征。

2.2 數(shù)據(jù)圖的編碼

本文提取的4個(gè)特征包含：節(jié)點(diǎn)標(biāo)記、邊、最短權(quán)值路徑和拉普拉斯圖譜。這4個(gè)特征編碼的組合信息較全面地描述了無向加權(quán)圖的基本信息、加權(quán)路徑信息和拓?fù)湫畔ⅰ?/p>

圖的編碼過程是對(duì)每個(gè)原始的圖數(shù)據(jù)的節(jié)點(diǎn)進(jìn)行特征提取，生成對(duì)應(yīng)編碼；再將每個(gè)節(jié)點(diǎn)的編碼組合生成圖的編碼。

在編碼過程中，提取的第一個(gè)特征是節(jié)點(diǎn)的標(biāo)記信息。提取到節(jié)點(diǎn)標(biāo)記信息后，按照哈希映射函數(shù)將節(jié)點(diǎn)的標(biāo)記映射到數(shù)字空間，生成節(jié)點(diǎn)標(biāo)記編碼；然后將所有節(jié)點(diǎn)標(biāo)記編碼合并生成圖的節(jié)點(diǎn)標(biāo)記編碼。

在圖2中，Q包含標(biāo)記為A、C、D的節(jié)點(diǎn)各一個(gè)，兩個(gè)標(biāo)記為B的節(jié)點(diǎn)。查找節(jié)點(diǎn)哈希函數(shù)，v4的節(jié)點(diǎn)標(biāo)記編碼為“0001”。對(duì)其他節(jié)點(diǎn)進(jìn)行相同的操作，可以得到圖中其他節(jié)點(diǎn)的標(biāo)記編碼,并且，按位相加即可得到圖Q的節(jié)點(diǎn)標(biāo)記編碼為“1121”。

圖2 節(jié)點(diǎn)的哈希映射函數(shù)

提取的第二個(gè)特征為邊信息。通過遍歷節(jié)點(diǎn)相鄰邊的哈希映射函數(shù)，可以得到鄰接邊的編碼。按位相加可得到圖Q的邊編碼。圖3給出圖Q中邊的哈希映射函數(shù)，其中“*”表示經(jīng)過的任意邊權(quán)值。

圖3 邊的哈希函數(shù)

對(duì)于加權(quán)圖Q中節(jié)點(diǎn)v4的鄰接邊，通過查找哈希映射函數(shù)得到邊編碼“0100”。最后，將5個(gè)節(jié)點(diǎn)對(duì)應(yīng)的5個(gè)計(jì)數(shù)串按對(duì)應(yīng)位相加，得到無向加權(quán)圖Q的邊編碼為“1331”。

區(qū)別于現(xiàn)存的基于表示學(xué)習(xí)的方法，本文提取路徑權(quán)值信息和拉普拉斯圖譜作為特征進(jìn)行映射編碼。根據(jù)路徑權(quán)值的嵌套定理，可以將兩個(gè)節(jié)點(diǎn)之間的路徑權(quán)值數(shù)進(jìn)行比較和過濾。本文將最短權(quán)值路徑作為第三個(gè)特征，進(jìn)行加速過濾操作。在提取最短權(quán)值路徑時(shí)，首先生成鄰接權(quán)值矩陣，接著針對(duì)無向加權(quán)圖，使用優(yōu)化的Floyd算法求解各個(gè)節(jié)點(diǎn)之間的最短權(quán)值路徑矩陣[18]，如表1所示，其中Ivaule為初始權(quán)值。

表1 最短權(quán)值路徑矩陣的算法(算法1)

通過算法1，由PSQuery方法可以得到最短權(quán)值路徑矩陣。該矩陣中的元素為節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的最短權(quán)值路徑。圖2中Q的最短權(quán)值路徑矩陣為：

根據(jù)上述權(quán)值矩陣，PSQuery方法通過將矩陣中的元素進(jìn)行編碼，并且進(jìn)行計(jì)算，得到每個(gè)節(jié)點(diǎn)到標(biāo)記為L(zhǎng)′節(jié)點(diǎn)的最短權(quán)值路徑；再取每個(gè)節(jié)點(diǎn)的權(quán)值中的最小值作為圖Q的權(quán)值路徑編碼。圖4給出了權(quán)值路徑編碼的生成過程。

圖4 圖Q的權(quán)值路徑編碼

PSQuery方法提取的最后一個(gè)特征為L(zhǎng)aplacian圖譜。具體生成過程中，對(duì)每個(gè)節(jié)點(diǎn)生成L(為一整數(shù))層生成圖，并且計(jì)算對(duì)應(yīng)圖譜來表示各個(gè)節(jié)點(diǎn)的局部拓?fù)湫畔?；再將?jié)點(diǎn)的圖譜進(jìn)行組合，得到整個(gè)無向加權(quán)圖的拓?fù)湫畔?，即Laplacian圖譜。其中，L層生成圖的算法如表2所示。

表2 L層生成圖的生成算法(算法2)

按照算法2，PSQuery可以生成節(jié)點(diǎn)L層生成圖；接著，按照雅克比算法求解出對(duì)應(yīng)的特征值，并取最大的兩個(gè)特征值作為節(jié)點(diǎn)的圖譜；最后，將所有節(jié)點(diǎn)的圖譜組合，生成圖的Laplacian圖譜。

根據(jù)上述提取特征和對(duì)特征進(jìn)行編碼的過程，可以得到節(jié)點(diǎn)編碼和圖編碼，具體如圖5所示。

圖5 節(jié)點(diǎn)編碼和圖編碼

2.3 索引的建立

索引樹的構(gòu)建參照GCoding方法中索引樹的構(gòu)造過程[9]。使用圖編碼中節(jié)點(diǎn)標(biāo)記編碼和邊編碼作為索引樹的一個(gè)節(jié)點(diǎn)。下面給出4個(gè)數(shù)據(jù)圖的索引樹實(shí)例。

在圖6(a)中，列出的圖數(shù)據(jù)庫包含了圖G1、G2、G3和G4。圖6(b)為該圖庫的索引樹。PSQuery方法提取每張數(shù)據(jù)圖編碼中的前兩部分作為索引的特征，構(gòu)建索引樹。

圖6 索引樹

在構(gòu)建索引樹的過程中，對(duì)于具有相同節(jié)點(diǎn)標(biāo)記編碼V和邊編碼E的無向加權(quán)圖，將其作為同一個(gè)葉子節(jié)點(diǎn)進(jìn)行處理。其中，每個(gè)中間節(jié)點(diǎn)有l(wèi)(l為整數(shù))個(gè)孩子節(jié)點(diǎn)，且中間節(jié)點(diǎn)C0、C1、C2、…、Cl的編碼為l個(gè)孩子節(jié)點(diǎn)的編碼值中對(duì)應(yīng)位上的最大值。同時(shí)，按照平衡樹的生成方法，將每個(gè)圖的編碼插入索引中，最終得到一個(gè)完整的平衡索引樹[19]。

3 PSQuery的查詢處理

3.1 過濾過程

本文所提方法中過濾規(guī)則分為兩部分：節(jié)點(diǎn)過濾規(guī)則和圖過濾規(guī)則。具體地，先根據(jù)圖過濾規(guī)則，篩選出初步符合條件的無向加權(quán)數(shù)據(jù)圖集，再對(duì)這些數(shù)據(jù)圖集使用節(jié)點(diǎn)過濾規(guī)則進(jìn)行二次過濾，找出真正符合條件的候選圖集。下面具體給出兩個(gè)過濾規(guī)則。

圖過濾規(guī)則：給定兩個(gè)無向加權(quán)圖G1和G2，G1包含m個(gè)節(jié)點(diǎn)，G2包含n個(gè)節(jié)點(diǎn)。其中n≥m。假定它們的圖編碼分別為gCode(G1)=〈V(G1),E(G1),P(G1),L(G1)〉和gCode(G2)=〈V(G2),E(G2),P(G2),L(G2)〉(其中P為最短權(quán)值路徑編碼，L為拉普拉斯圖譜)。若G1和G2的圖編碼不滿足下列條件：

①V(G1)[i]=V(G2)[i],i=0,1,…,lV-1;

②E(G1)[i]≤E(G2)[i],i=0,1,…,lE-1;

③P(G1)[i]≥P(G2)[i],i=0,1,…,lV-1;

④L(G1)k[i]≤L(G2)k[i],i=0,1，k=0,1,…,m-1。

那么G1不是G2的子圖。

節(jié)點(diǎn)過濾規(guī)則：給定兩個(gè)無向加權(quán)圖G1和G2，對(duì)于G1中的任一節(jié)點(diǎn)v，其編碼為〈V(v),E(v),P(v),L(v)〉。如果無向加權(quán)圖G2中找不到這樣的節(jié)點(diǎn)v′，其編碼對(duì)應(yīng)表示為〈V(v′),E(v′),P(v′),L(v′)〉，且滿足以下條件：

那么G1不是G2的子圖。

由于圖過濾規(guī)則的效率高于節(jié)點(diǎn)過濾規(guī)則，PSQuery方法首先使用圖過濾規(guī)則遍歷索引樹，接著使用節(jié)點(diǎn)過濾規(guī)則進(jìn)行判定，生成規(guī)模較小的候選集。

以圖2中的查詢圖Q為例，使用圖過濾規(guī)則遍歷圖6中的索引樹。首先將Q的圖編碼與根節(jié)點(diǎn)進(jìn)行比較，發(fā)現(xiàn)不滿足圖過濾條件，繼續(xù)遍歷其孩子節(jié)點(diǎn)；當(dāng)遍歷到中間節(jié)點(diǎn)C2，對(duì)比編碼E時(shí)，滿足圖過濾規(guī)則，則C2及其孩子節(jié)點(diǎn)全部刪除。同理，遍歷到G1時(shí)也滿足圖過濾規(guī)則，也被刪除，最后產(chǎn)生候選集為{G2}。按照同樣的判定方法，經(jīng)過節(jié)點(diǎn)判定規(guī)則后，就可以生成最終的候選集合。

完成過濾后，接著對(duì)每個(gè)候選圖進(jìn)行驗(yàn)證處理，得到最終的查詢結(jié)果集。

3.2 驗(yàn)證過程

在驗(yàn)證階段，采用經(jīng)典的VF2算法進(jìn)行子圖同構(gòu)的判定[20]。在VF2方法中，對(duì)匹配對(duì)進(jìn)行判定的可行性規(guī)則由兩部分組成：語法規(guī)則和語義規(guī)則。語法規(guī)則按照VF2算法中列舉的相關(guān)規(guī)則進(jìn)行判定。對(duì)于語義規(guī)則，VF2算法根據(jù)子圖中節(jié)點(diǎn)和鄰接邊與超圖中對(duì)應(yīng)節(jié)點(diǎn)和對(duì)應(yīng)鄰接邊的相似匹配關(guān)系進(jìn)行判定。為了實(shí)現(xiàn)無向加權(quán)圖中加權(quán)邊的信息判定，在驗(yàn)證過程中，將節(jié)點(diǎn)過濾規(guī)則也作為語義規(guī)則的一部分進(jìn)行判定，從而加速了無向加權(quán)圖的同構(gòu)判定效率。

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

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

為了進(jìn)一步驗(yàn)證所提方法的可行性和有效性，本文選取第三類基于表示學(xué)習(xí)的GCoding和LsGCoding方法進(jìn)行比較和驗(yàn)證。在具體的實(shí)驗(yàn)中，對(duì)比的兩種方法均基于iGraph框架進(jìn)行編程實(shí)現(xiàn)[21]。

這三種方法都提取了節(jié)點(diǎn)和邊的信息，而實(shí)驗(yàn)性能差異主要是由于GCoding方法將生成子樹的圖譜作為該方法的主要特征，LsGCoding方法將生成子圖的圖譜作為主要特征，而PSQuery方法將生成子圖的拉普拉斯圖譜和最短路徑長(zhǎng)度作為主要特征所導(dǎo)致的。由于主要特征的不同，這三個(gè)方法在過濾和驗(yàn)證過程中的過濾和判定效率不同，本節(jié)內(nèi)容是對(duì)這三種方法的性能測(cè)試。

實(shí)驗(yàn)中的輸入數(shù)據(jù)分為兩類數(shù)據(jù)：真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集。

1)真實(shí)數(shù)據(jù)集。該數(shù)據(jù)集包含10 000個(gè)簡(jiǎn)單數(shù)據(jù)圖作為測(cè)試數(shù)據(jù)圖集，是從Developmental Therapeutics Program主頁上已知分類的化學(xué)分子式中提取出來的，并且大部分子圖查詢方法均采用該數(shù)據(jù)集進(jìn)行測(cè)試。其中每個(gè)圖的平均節(jié)點(diǎn)個(gè)數(shù)為25.4，邊的個(gè)數(shù)為27.3。輸入的查詢圖集也來源于這個(gè)真實(shí)數(shù)據(jù)集，包括了6個(gè)查詢集合：Q4、Q8、Q12、Q16、Q20、Q24，其中每個(gè)查詢集Qi包含了1 000個(gè)隨機(jī)抽取的查詢圖，并且邊的個(gè)數(shù)為i。

2)合成數(shù)據(jù)集。合成數(shù)據(jù)集由iGraph提供，使用圖生成器GraphGen生成。此數(shù)據(jù)集包含10 000個(gè)稠密數(shù)據(jù)圖，數(shù)據(jù)集中圖的平均節(jié)點(diǎn)個(gè)數(shù)為30，邊的平均密度為0.5。查詢圖集則按照真實(shí)數(shù)據(jù)集的抽取方式進(jìn)行抽取，同樣得到Q4、Q8、Q12、Q16、Q20、Q24，一共6組數(shù)據(jù)集。

4.2 參數(shù)設(shè)置和實(shí)驗(yàn)環(huán)境

在實(shí)驗(yàn)中，測(cè)試3種方法，其中每種方法的參數(shù)設(shè)置主要涉及提取圖譜時(shí)構(gòu)造的節(jié)點(diǎn)對(duì)應(yīng)的N層生成圖或者樹的層數(shù)，以及最終生成圖譜時(shí)選取的特征值的個(gè)數(shù)。這兩個(gè)參數(shù)選用與GCoding相同的兩個(gè)參數(shù)值，即N=2，特征值個(gè)數(shù)等于2。這是因?yàn)樵趇Graph框架中，通過實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)N大于2或特征值個(gè)數(shù)大于2時(shí)，候選集的大小不會(huì)發(fā)生太大變化。

實(shí)驗(yàn)的運(yùn)行環(huán)境為Windows XP SP3系統(tǒng)，CPU為Intel Core CPUI7-8550U，內(nèi)存大小為3.5G，開發(fā)環(huán)境為Visual Studio 2010。

4.3 結(jié)果評(píng)測(cè)標(biāo)準(zhǔn)

實(shí)驗(yàn)包含兩大部分：生成編碼，構(gòu)建索引樹的過程和查詢處理過程，所以評(píng)判標(biāo)準(zhǔn)也分為兩個(gè)部分。評(píng)判標(biāo)準(zhǔn)1為索引的構(gòu)建時(shí)間和索引的大??；評(píng)判標(biāo)準(zhǔn)2為候選集的大小和查詢時(shí)間。對(duì)應(yīng)的評(píng)判結(jié)論為：構(gòu)建索引和編碼的時(shí)間越少，并且索引樹越小，說明方法性能越好；候選集越小，查詢時(shí)間越短，說明方法的查詢性能越好。

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

實(shí)驗(yàn)中，從10 000張真實(shí)或合成數(shù)據(jù)圖中隨機(jī)抽取4次，對(duì)應(yīng)圖數(shù)量分別為2 000、4 000、6 000、8 000張，加上10 000張數(shù)據(jù)圖，形成5種規(guī)模的數(shù)據(jù)集。針對(duì)這5個(gè)不同規(guī)模的數(shù)據(jù)集，分別進(jìn)行編碼，構(gòu)建索引和查詢處理的操作，得到圖7～圖10所示的真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比結(jié)果，以及圖11～圖14的合成數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比結(jié)果。

1)真實(shí)數(shù)據(jù)集上的結(jié)果分析。

圖7 真實(shí)數(shù)據(jù)集上編碼和索引時(shí)間

圖7展示了真實(shí)數(shù)據(jù)圖庫規(guī)模從2 000張到10 000張圖時(shí)，3種方法的編碼和索引時(shí)間。PSQuery方法提取節(jié)點(diǎn)和邊信息、權(quán)值路徑和Laplacian圖譜，而GCoding和LsGCoding方法只有節(jié)點(diǎn)、邊和圖譜(或者拉普拉斯圖譜)信息，所以PSQuery方法編碼和索引構(gòu)建的時(shí)間大于GCoding方法和LsGCoding方法。

圖8 真實(shí)數(shù)據(jù)集上索引的大小

圖8展示了真實(shí)數(shù)據(jù)圖庫從2 000張到10 000張圖時(shí)，編碼和索引大小的實(shí)驗(yàn)性能。因?yàn)镻SQuery方法比GCoding和LsGCoding方法提取的特征多了權(quán)值路徑信息，所以PSQuery方法中數(shù)據(jù)圖庫和索引所占空間更大。而GCoding方法的主要特征只有子樹的特征值，所以GCoding方法的索引空間最小。

圖9 真實(shí)數(shù)據(jù)集候選圖集合的大小

圖9為真實(shí)數(shù)據(jù)庫中不同查詢圖集合下，3種方法過濾后的候選集的大小。隨著查詢圖集合從Q24變化到Q4，3種方法的結(jié)果集在增大，候選圖集也在增大。與GCoding和LsGCoding兩個(gè)方法相比，由于PSQuery方法提取更多的權(quán)值路徑信息，其裁剪過濾性能最好，所以在真實(shí)數(shù)據(jù)集上，PSQuery方法生成的候選集最小。由于候選集規(guī)模直接影響查詢效率，所以這也說明PSQuery方法在一定程度上提升了過濾的性能。

從圖10中可以看出，隨著真實(shí)數(shù)據(jù)集上查詢圖從Q24變化到Q4，3種方法的查詢時(shí)間都在增大。這是因?yàn)楹蜻x集一直在增大，必須花費(fèi)更多的時(shí)間去進(jìn)行子圖的驗(yàn)證操作才能得到最終結(jié)果集。并且除了Q4，PSQuery方法的查詢時(shí)間均小于GCoding方法和LsGCoding方法。由于提取了更好的圖特征，PSQuery方法候選集最小，驗(yàn)證時(shí)間最少，相應(yīng)的查詢時(shí)間最少，這說明PSQuery方法提高了真實(shí)數(shù)據(jù)集上的加權(quán)無向圖的子圖查詢效率。

圖10 真實(shí)數(shù)據(jù)集上的查詢時(shí)間

2)合成數(shù)據(jù)集上的結(jié)果分析。

圖11 合成數(shù)據(jù)集上編碼和索引時(shí)間

圖11給出了3種方法在合成數(shù)據(jù)集上的編碼和索引時(shí)間。相較于LsGCoding和PSQuery方法，GCoding方法的編碼和索引時(shí)間最大。這是因?yàn)楹铣蓤D大部分為稠密圖，針對(duì)稠密圖，GCoding方法在生成N層生成樹時(shí)會(huì)增加多個(gè)重復(fù)的節(jié)點(diǎn)，因此對(duì)應(yīng)的鄰接矩陣在計(jì)算特征值時(shí)會(huì)十分復(fù)雜[14]。由于PSQuery方法相較于LsGCoding方法，增加了路徑的權(quán)值信息，所以花費(fèi)的時(shí)間多于LsGCoding方法。

圖12給出了3種方法在不同合成數(shù)據(jù)集規(guī)模上的索引大小。因?yàn)镻SQuery方法提取的特征多于GCoding和LsGCoding方法，所以PSQuery方法的索引所占空間最大。

圖13給出了合成數(shù)據(jù)集上3種方法在不同規(guī)模查詢集上的候選集大小。隨著查詢集的邊個(gè)數(shù)遞減，3種方法在合成數(shù)據(jù)集上的候選集在增大。并且稠密圖中，節(jié)點(diǎn)和邊的基本信息可以覆蓋部分權(quán)值路徑信息，所以在不同查詢集上，3種方法的候選集規(guī)模很接近，裁剪后的過濾性能近似相同。

圖12 合成數(shù)據(jù)集上索引的大小

圖13 合成數(shù)據(jù)集候選圖集合的大小

圖14 合成數(shù)據(jù)集上的查詢時(shí)間

圖14給出了合成數(shù)據(jù)集上不同查詢集的查詢性能。當(dāng)查詢集從Q24變化到Q4時(shí)，LsGCoding方法的查詢時(shí)間少于GCoding方法。而PSQuery方法提取了權(quán)值路徑信息，其產(chǎn)生的候選圖集最小，所以其查詢時(shí)間均小于GCoding和LsGCoding方法。

從真實(shí)數(shù)據(jù)和合成數(shù)據(jù)的實(shí)驗(yàn)結(jié)果可知，在編碼和索引階段，PSQuery方法的索引時(shí)間和所占空間均大于GCoding和LsGCoding方法。但是在加權(quán)無向圖的多次子圖查詢處理過程中，索引只需建立一次，所以索引相關(guān)操作并不能作為主要的性能評(píng)定指標(biāo)。而每次查詢都會(huì)產(chǎn)生的查詢時(shí)間是其主要的性能評(píng)定指標(biāo)。從真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集的查詢性能上分析，PSQuery方法產(chǎn)生的候選集規(guī)模最小或者相似，并且驗(yàn)證過程中增加了權(quán)值的判定條件，所以PSQuery方法的查詢時(shí)間都優(yōu)于同類其他方法，從而在一定程度上提高了加權(quán)圖的子圖查詢效率。

3)數(shù)據(jù)集更新時(shí)的性能分析。

數(shù)據(jù)集更新的操作主要是對(duì)圖數(shù)據(jù)集合進(jìn)行添加操作。針對(duì)數(shù)據(jù)圖集合的添加，使用GCoding方法提到的數(shù)據(jù)更新性能分析方法，對(duì)真實(shí)數(shù)據(jù)集，在數(shù)據(jù)集規(guī)模為2 000的基礎(chǔ)上，每次增加2 000個(gè)數(shù)據(jù)圖進(jìn)行更新性能分析[9]。同樣，選擇經(jīng)典的基于頻繁子結(jié)構(gòu)方法gIndex與PSQuery方法進(jìn)行比較[9]。

基于表示學(xué)習(xí)的方法，在計(jì)算新插入數(shù)據(jù)圖的特征編碼的基礎(chǔ)上，將其編碼插入到索引樹中，這樣便完成了更新操作。但是，對(duì)于基于頻繁子結(jié)構(gòu)的方法的圖更新處理，現(xiàn)存的處理方法有兩種機(jī)制：①直接將新加入的數(shù)據(jù)圖進(jìn)行處理，只是在倒排索引中增加新圖的ID；②將新加入的圖和原數(shù)據(jù)集重新開始進(jìn)行頻繁子結(jié)構(gòu)挖據(jù)，新建整個(gè)倒排索引[13]。所以，在該部分實(shí)驗(yàn)中，將PSQuery方法的更新操作和gIndex方法的兩種操作進(jìn)行比較。

還有一個(gè)數(shù)據(jù)集更新時(shí)的評(píng)價(jià)指標(biāo)：索引構(gòu)建時(shí)間，用于描述編碼的索引更新的時(shí)間。索引構(gòu)建時(shí)間越少，說明更新的代價(jià)越小，適應(yīng)數(shù)據(jù)集更新的性能就越好。圖15～16為過濾效率的實(shí)驗(yàn)結(jié)果。

圖15 數(shù)據(jù)集更新時(shí)的裁剪效率

在圖15中，PSQuery方法在數(shù)據(jù)集每次增加2 000個(gè)圖集的情況下，裁剪的效率性能比較穩(wěn)定。gIndex方法的新建索引的裁剪效率也比較穩(wěn)定，但是該方法在增量構(gòu)建索引的情況下，其裁剪效率明顯在下降。

圖16 數(shù)據(jù)集更新時(shí)索引構(gòu)建時(shí)間

在圖16中，隨著更新數(shù)據(jù)集的增大，PSQuery方法和gIndex方法構(gòu)建索引的時(shí)間都在增大。對(duì)于gIndex方法，其增量形式構(gòu)建索引方法的花費(fèi)時(shí)間雖然較小，但是圖16中該機(jī)制下索引的裁剪效率在降低，進(jìn)而降低該方法的查詢效率。而gIndex如果每次新建索引，其索引構(gòu)建時(shí)間會(huì)大幅增大，而其裁剪效率變化不是很大，略低于PSQuery方法。PSQuery方法在數(shù)據(jù)集更新的情況下，索引構(gòu)建時(shí)間和裁剪效率相較于gIndex方法的兩種不同機(jī)制都比較穩(wěn)定。所以PSQuery方法可以很好地處理數(shù)據(jù)集更新的情況。

5 結(jié) 語

本文針對(duì)無向加權(quán)圖的子圖查詢問題，提出了基于最短權(quán)值路徑和Laplacian圖譜的新編碼方法，并且在編碼的基礎(chǔ)上生成了新的索引樹。同時(shí)，按照過濾-驗(yàn)證框架進(jìn)行子圖查詢，通過大量的實(shí)驗(yàn)證實(shí)了該方法具有一定的可行性和有效性，特別是PSQuery方法可以很好地處理數(shù)據(jù)集更新的情況。后期計(jì)劃將這些新編碼應(yīng)用到超圖查詢和知識(shí)圖譜的查詢問題中，并且尋找更優(yōu)的圖特征去處理有向圖的查詢問題。