一種面向無向加權(quán)圖的子圖查詢方法

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

(1.西安理工大學 計算機科學與工程學院，陜西 西安 710048；2.西安理工大學 自動化與信息工程學院，陜西 西安 710048)

圖被大規(guī)模用于構(gòu)造半結(jié)構(gòu)或非結(jié)構(gòu)化的數(shù)據(jù)和語義。例如，化學[1]、社交網(wǎng)絡(luò)[2]、知識圖譜[3]、XML文件[4]等。在這些應用中，實體和關(guān)系被建模為圖模型，并構(gòu)建更加高效的半結(jié)構(gòu)或非結(jié)構(gòu)化的圖數(shù)據(jù)庫，然后應用圖挖據(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)存的方法均采用過濾-驗證框架，而且提取高效的圖特征進行過濾已成為子圖查詢的重要研究方向。一些現(xiàn)存的方法主要采用數(shù)據(jù)挖掘的理論去提取頻繁子結(jié)構(gòu)作為特征，并使用倒排序的索引進行過濾[7,8]。但是這類方法在圖數(shù)據(jù)頻繁更新時，必須重新挖掘頻繁子結(jié)構(gòu)和建立索引，導致代價過大[9]。

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

1 相關(guān)工作

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

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

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

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

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

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

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

2 PSQuery編碼和索引方法

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

圖1 過濾-驗證框架

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

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

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

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

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

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

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

定理：(圖譜的嵌套定理)給出兩個無向加權(quán)圖G1和G2，其Laplacian矩陣分別表示為LAm×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)計學規(guī)律，無向加權(quán)圖中節(jié)點標記和邊的個數(shù)也具有相似的性質(zhì)，即通過數(shù)值比較進行過濾操作。在GCoding和LsGCoding方法中，這兩種基本特征已被提取為圖的特征編碼[9,14]。根據(jù)特征進行編碼的操作效率高，所以PSQuery提取這4個圖屬性作為索引特征。

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

本文提取的4個特征包含：節(jié)點標記、邊、最短權(quán)值路徑和拉普拉斯圖譜。這4個特征編碼的組合信息較全面地描述了無向加權(quán)圖的基本信息、加權(quán)路徑信息和拓撲信息。

圖的編碼過程是對每個原始的圖數(shù)據(jù)的節(jié)點進行特征提取，生成對應編碼；再將每個節(jié)點的編碼組合生成圖的編碼。

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

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

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

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

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

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

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

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

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

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

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

PSQuery方法提取的最后一個特征為Laplacian圖譜。具體生成過程中，對每個節(jié)點生成L(為一整數(shù))層生成圖，并且計算對應圖譜來表示各個節(jié)點的局部拓撲信息；再將節(jié)點的圖譜進行組合，得到整個無向加權(quán)圖的拓撲信息，即Laplacian圖譜。其中，L層生成圖的算法如表2所示。

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

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

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

圖5 節(jié)點編碼和圖編碼

2.3 索引的建立

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

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

圖6 索引樹

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

3 PSQuery的查詢處理

3.1 過濾過程

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

圖過濾規(guī)則：給定兩個無向加權(quán)圖G1和G2，G1包含m個節(jié)點，G2包含n個節(jié)點。其中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é)點過濾規(guī)則：給定兩個無向加權(quán)圖G1和G2，對于G1中的任一節(jié)點v，其編碼為〈V(v),E(v),P(v),L(v)〉。如果無向加權(quán)圖G2中找不到這樣的節(jié)點v′，其編碼對應表示為〈V(v′),E(v′),P(v′),L(v′)〉，且滿足以下條件：

那么G1不是G2的子圖。

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

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

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

3.2 驗證過程

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

4 實驗結(jié)果和分析

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

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

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

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

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

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

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

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

實驗的運行環(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é)果評測標準

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

4.4 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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