一種面向無向加權圖的子圖查詢方法

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

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

圖被大規模用于構造半結構或非結構化的數據和語義。例如，化學[1]、社交網絡[2]、知識圖譜[3]、XML文件[4]等。在這些應用中，實體和關系被建模為圖模型，并構建更加高效的半結構或非結構化的圖數據庫，然后應用圖挖據相關技術去高效智能地檢索事物間的關聯關系[5]。

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

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

1 相關工作

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

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

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

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

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

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

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

2 PSQuery編碼和索引方法

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

圖1 過濾-驗證框架

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

2.1 圖譜及路徑的相關性質

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

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

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

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

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

定理：(圖譜的嵌套定理)給出兩個無向加權圖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。

基于統計學規律，無向加權圖中節點標記和邊的個數也具有相似的性質，即通過數值比較進行過濾操作。在GCoding和LsGCoding方法中，這兩種基本特征已被提取為圖的特征編碼[9,14]。根據特征進行編碼的操作效率高，所以PSQuery提取這4個圖屬性作為索引特征。

2.2 數據圖的編碼

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

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

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

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

圖2 節點的哈希映射函數

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

圖3 邊的哈希函數

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

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

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

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

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

圖4 圖Q的權值路徑編碼

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

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

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

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

圖5 節點編碼和圖編碼

2.3 索引的建立

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

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

圖6 索引樹

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

3 PSQuery的查詢處理

3.1 過濾過程

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

圖過濾規則：給定兩個無向加權圖G1和G2，G1包含m個節點，G2包含n個節點。其中n≥m。假定它們的圖編碼分別為gCode(G1)=〈V(G1),E(G1),P(G1),L(G1)〉和gCode(G2)=〈V(G2),E(G2),P(G2),L(G2)〉(其中P為最短權值路徑編碼，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的子圖。

節點過濾規則：給定兩個無向加權圖G1和G2，對于G1中的任一節點v，其編碼為〈V(v),E(v),P(v),L(v)〉。如果無向加權圖G2中找不到這樣的節點v′，其編碼對應表示為〈V(v′),E(v′),P(v′),L(v′)〉，且滿足以下條件：

那么G1不是G2的子圖。

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

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

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

3.2 驗證過程

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

4 實驗結果和分析

4.1 數據源

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

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

實驗中的輸入數據分為兩類數據：真實數據集和合成數據集。

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

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

4.2 參數設置和實驗環境

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

實驗的運行環境為Windows XP SP3系統，CPU為Intel Core CPUI7-8550U，內存大小為3.5G，開發環境為Visual Studio 2010。

4.3 結果評測標準

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

4.4 實驗結果與分析

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

1)真實數據集上的結果分析。

圖7 真實數據集上編碼和索引時間

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

圖8 真實數據集上索引的大小

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

圖9 真實數據集候選圖集合的大小

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

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

圖10 真實數據集上的查詢時間

2)合成數據集上的結果分析。

圖11 合成數據集上編碼和索引時間

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

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

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

圖12 合成數據集上索引的大小

圖13 合成數據集候選圖集合的大小

圖14 合成數據集上的查詢時間

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

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

3)數據集更新時的性能分析。

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

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

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

圖15 數據集更新時的裁剪效率

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

圖16 數據集更新時索引構建時間

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

5 結 語

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