基于隨機游走的語義結構查詢算法

朱 玉 游進國* 付子玉

1(昆明理工大學信息工程與自動化學院 云南 昆明 650500)2(大連民族大學計算機科學與工程學院 遼寧 大連 116000)

0 引 言

近年來，圖挖掘(Graph Mining)方向作為數(shù)據(jù)挖掘領域中的重要組成部分引起了社會各界的極大關注。圖在生物信息學(蛋白質(zhì)結構分析、基因組織識別等)、社交網(wǎng)絡(用戶之間的聯(lián)系等)、Web分析(Web內(nèi)容挖掘、Web連接結構分析、Web日志搜索等)、網(wǎng)絡計算等方面有著豐富的應用。圖查詢是圖挖掘的一個重要研究方向。一直以來其中的數(shù)據(jù)查詢問題和方法都受到了人們廣泛的關注和研究。

在圖數(shù)據(jù)挖掘領域中，傳統(tǒng)圖查詢方法大體上可分為關鍵字查詢和頻繁子圖挖掘兩大類。其中關于圖數(shù)據(jù)中的頻繁子圖挖掘可分為如下幾種方法：Apriori-based[1]方法：主要采用Apriori的性質(zhì)，枚舉重復出現(xiàn)的子圖，其中AGM(Apriori-based Graph Mining)[2]是一種基于圖論的思想，挖掘各種不同類型的子圖；AcGM(Apriori-based connected Graph Mining)[3]方法是原有AGM方法拓展到連通圖上；FSG(Frequent Subgraph)[4]采用多種優(yōu)化規(guī)則的方式使其適用于大數(shù)據(jù)集；path-join[5]算法等。由于使用了Apriori性質(zhì)，在擴展邊的過程中，會產(chǎn)生大量的重復候選子圖，從而降低了算法的整體效率。FP-growth[6]方法：是一種執(zhí)行效率較高的方法，其中gSpan(graph-based Substructure pattern mining)[7]是一種典型的基于深度優(yōu)先思想查詢頻繁子圖的算法，但是無法避免子圖同構的問題，從而算法復雜度比較高；CloseGraph(A closed graph pattern mining algorithm)[8]用于查詢相同頻率下最大規(guī)模子圖。也有一些其他的頻繁子圖挖掘算法，例如：Zhu等[9]提出了一種基于用戶約束條件的頻繁子圖挖掘算法gPrune；Wang等[10]提出了一種基于索引的頻繁子圖挖掘算法GraphMiner； Karste等[11]提出了適合于動態(tài)圖挖掘DynamicGREW算法等。Danai等[12]提出了VoG方法，構造一組子圖和一個高頻子圖類型的詞匯表(例如：星形、團和鏈)，根據(jù)詞匯表找出最簡潔的圖描述方式并通過最小描述長度(MDL)原則來衡量描述結果。本文提出一種MDL-based Random-walk Query Algorithm(MRQ)算法，將圖聚集應用到頻繁子圖查詢中，對原圖和特殊子圖進行聚集，解決傳統(tǒng)算法復雜度高的問題。

為了降低百萬節(jié)點大圖所占用的內(nèi)存，加快執(zhí)行時間，本文選取ApxGreedy[17]聚集方法對原圖進行聚集。首先將原圖分為有兩個部分：第一個部分是聚集圖(遠小于輸入圖)，得到輸入圖聚集之后超邊和超點的關系，第二個部分是一組修正圖，用于重建原始輸入圖。選取此聚集方法具有以下好處：(1) 聚集圖占內(nèi)存較小。應用于可視化等圖分析技術是可行的，因為，它提供了對圖的高級結構的洞察，以及各種點簇之間的主要關系。(2) 此方法實現(xiàn)了將大圖高度壓縮。此外，它還支持調(diào)整參數(shù)，可用于實現(xiàn)有損壓縮。

1 問題引入

如圖1所示，給定一個簡單無向圖。

圖1 簡單無向原圖

經(jīng)過ApxGreedy聚集算法預處理之后可以得到一個如圖2所示的隨機游走圖。

圖2 聚集圖

語義結構以星形圖為例，星形圖的示例圖和聚集之后的結構如圖3和圖4所示。

圖3 星形圖

圖4 星形圖聚集結構

根據(jù)星形圖聚集后的通用特征進行隨機游走查詢，由于聚集過程中并非能恰好聚集成目的語義結構的隨機游走圖，所以需要放松隨機游走時的查詢條件。本文利用強弱關聯(lián)來取替嚴格的隨機游走查詢跳轉概率，在聚集處理后的隨機游走圖上查詢星形圖的流程如下：

(1) 查找超點間強關聯(lián)的一個超點對；

(2) 一個超點內(nèi)包含一個點，一個超點內(nèi)包含大于等于兩個點；

(3) 多個點簇成的超點內(nèi)為弱關聯(lián)。

在上述整個過程中采用隨機游走查詢算法，減少多余的遍歷，提高了查詢效率。

2 算法描述

隨機游走算法是一個半監(jiān)督的全局最優(yōu)化算法，旨在減少其遍歷路徑中，被極大極小算法評估的路徑數(shù)。在查詢算法中優(yōu)化使用隨機游走思想，用來減少一些不必要的遍歷過程。其中如何通過聚集預處理結果生成隨機游走圖以及在隨機游走查詢中如何設定跳轉概率是應用隨機游走查詢的核心問題，也就是說，需要構建超點之間的相似度并標記超邊，從而降低查詢時間和錯誤率。本文利用隨機游走查詢算法在聚集圖上查詢語義結構，具體算法描述如下：

將目標社交網(wǎng)絡抽象成一個無向無加權簡單圖G=(V,E)，其中V是用戶之間相互關系的集合，E代表每個用戶。對此大圖用聚集算法進行壓縮，根據(jù)超點之間的相似度標記超邊并生成隨機游走圖，在此基礎上進行隨機游走查詢，最后查詢到的語義結構根據(jù)誤差率排序并輸出結果。

2.1 ApxGreedy算法聚集處理

用聚集算法預處理大圖的效果可以直接影響查詢的效果，本文目的在于選取一個高效、快速的聚集算法。針對包含百萬結點的大圖可以快速并低損耗的聚集方法視為可用于查詢預處理的方法。比較BUS(Bottom Up Algorithm)聚集算法 、GGS(Greedy Graph Summary)和貪婪聚集(Greedy)算法等多種聚集算法，實驗結果發(fā)現(xiàn)，目前ApxGreedy聚集算法效果最優(yōu)。

定義1(聚集圖Gs) 給定一個簡單無向無加權圖G=(V,E)，若無向加權圖Gs表示為原圖的聚集圖，則圖Gs的的公式化表示為Gs=(Vs,Es)，其中，聚集圖Gs中的超點集合用Vs=(vs1,vs2,…,vsk)表示，聚集圖Gs中的超邊Es集合的公式為Es=Vs×Es，則聚集圖Gs和原圖G=(V,E)滿足以下關系：

(1)Vi∈Vs,Vi?V,Vi≠Φ；

(3)Es={(Vi,Vj)|?u∈Vi,v∈Vj,(u,v∈E)}。

圖聚集是一個不斷合并頂點及創(chuàng)建超邊的過程。超邊的概率用Pij來表示，其中概率Pij和關聯(lián)強度相關，若原圖中頂點內(nèi)或頂點間實際存在的邊數(shù)越多，即關聯(lián)強度越高，說明在生成聚集圖時，超邊存在的概率越高，反之當關聯(lián)強度越低時，超邊存在的概率越低。

具體的超邊之間存在的概率P的計算方法定義如下：

超點內(nèi)點全連接之后的邊數(shù)為Γij，實際存在的邊數(shù)為Eij，則：

定義2(超點之間的概率)

P=Eij/Γij

(1)

2.2 隨機游走查詢

本文引入隨機游走的方式進行查詢，構建隨機游走模型，包括生成隨機游走圖和在圖上隨機游走查詢兩個部分。

(1) 生成隨機游走圖：

在聚集預處理的步驟里根據(jù)兩點之間的關聯(lián)強度即概率Pij決定是否用邊將兩點相連。為方便求解，將聚集之后的兩點之間的關聯(lián)強度即概率Pij作為邊的權重。當兩點之間的概率Pij很小或者為0時，節(jié)點之間的權重視為零。

定義3(隨機游走圖中超點之間的距離) 假設圖G=(V,E)，其中超點個數(shù)為n。邊權重使用高斯核函數(shù)計算，公式為：

(2)

(3)

(2) 隨機游走查詢:

超圖中的一條超邊包含可能超過兩個以上的超點，所以對超圖使用隨機游走查詢方法。隨機游走的過程為：選定初始定點u，根據(jù)超邊的權重W(e)大小的概率成正比的選擇一條包含當前定點u的特定超邊e；在已經(jīng)選中的超邊中，根據(jù)頂點權重大小概率成正比的選擇轉移頂點v。設P為隨機游走的轉移矩陣，其計算式表示為:

(4)

根據(jù)聚集圖的權重矩陣P計算圖G的概率轉移矩陣，其計算式表示為：

(5)

隨機游走查詢過程使用以下函數(shù)表示：

(6)

2.3 語義結構相關定義

在社交網(wǎng)絡中，我們關注用戶之間的關系，比如名人與粉絲之間的關系，互相都關注的親友團體，存在共同粉絲的明星等，由此可以根據(jù)這些重要的關系來形成值得討論的語義結構。

本文著重討論四種語義結構：星形圖、鏈、團、二部圖。

經(jīng)過聚集算法得到聚集圖結構后，可總結出以下四種語義結構的通用特征的重新的定義：

(1) 星形圖：超點和超點之間是強關聯(lián)，中心點經(jīng)過聚集之后的超點中只有一個點，各個結點聚合后的超點有至少超過兩個點，且超點內(nèi)部為弱關聯(lián)。

(2) 二部圖：聚合在兩個超點內(nèi)，且每個超點內(nèi)的點個數(shù)大于等于2個，超點內(nèi)部概率為0，超點之間概率為1 。

以上兩個結果在聚集之后的通用特征統(tǒng)一，而對于鏈和團針對點個數(shù)的增多，聚集效果并不相同，所以利用實際聚集之后的效果對鏈和團結構的通用特征進行總結。

(3) 鏈：鏈聚集之后還是鏈，但其每個超點內(nèi)包含的點數(shù)小于等于2個，且聚集圖對應的鄰接矩陣對角線的值都為0。

(4) 團：本文實驗發(fā)現(xiàn)，點數(shù)n<9時，團會聚集成一個新的團結構，且聚集圖所對應的鄰接矩陣對角線不為0；當951時會聚集在一個超點內(nèi)，且聚集圖所對應的鄰接矩陣對角線不為0。

2.4 成本誤差排序

除此之外，本文引入了成本來計算誤差，并根據(jù)誤差的大小，來對查詢到的語義結構進行排序。

在隨機聚集(ApxGreedy)算法中，一般而言，用c′v近似表示點v的成本，其中c′v是點v鏈接的邊中所有點的近似最小總成本。之后，將兩個點u和v合并成一個新的超點w，其中超點w的成本降低了s′(u,v)，用公式(c′u+c′v-c′w)/(c′u+c′v)表示點u和v合并為超點w后的損失，因此s′(u,v)是點u和v合并后的成本誤差。

在聚集基礎上繼續(xù)討論成本誤差，并根據(jù)此項標準對查找到的語義結構進行排序，相關定義如下：

引入交叉熵的概念，通常交叉熵可在神經(jīng)網(wǎng)絡(機器學習)中作為損失函數(shù)，真實標記的分布表示為p，訓練后的模型的預測標記分布表示為q，p與q的相似性可以用交叉熵損失函數(shù)來衡量。

標準的交叉熵公式為：

C(p,q)=-qlog(p/q)

式中：由于強關聯(lián)概率q=1，所以C(p)=-log(p)。

此后，將總的誤差轉化為了聚集部分的誤差與查詢部分誤差的和，如下所示：

C=C(u,v)+C(p)

2.5 算法復雜度

本算法包含三個步驟：(1) 對輸入的簡單無向大圖進行隨機聚集處理。(2) 利用各個語義結構聚集之后的特點進行查詢。(3) 根據(jù)MDL誤差排序并輸入。其中，對輸入的簡單無向大圖進行隨機聚集處理時間復雜度為： 在每個合并步驟中，計算包含v的所有2Hop(v)對的成本降低；這總共需要O(3Hop(v))時間。再次，假設平均查詢邊數(shù)為dav，這變成O(dav3)。利用隨機游走進行查詢的時間復雜度為O(|E|)。

本文是基于隨機游走的語義結構剪枝查詢算法，先使用聚集預處理之后再利用隨機游走的思想進行查詢，且查詢部分只與邊有關系。所以本算法的時間復雜度最壞為O(dav3)+O(|E|)。其中|E|為給定社交網(wǎng)絡的邊數(shù)。

綜上，本算法的時間復雜度為O(dav3)+O(|E|)。

2.6 算法流程圖

本算法的流程圖如圖5所示。

圖5 算法流程圖

2.7 算法偽代碼

對于輸入的簡單無向大圖，本文中先利用隨機聚集算法進行聚集處理，根據(jù)定義生成隨機游走圖，再利用隨機游走查詢算法對語義結構進行查詢，最后根據(jù)MDL誤差來進行優(yōu)良排序，并輸出查到的最優(yōu)結構所處的超點位置。

算法: MDL-based Random-walk Query Algorithm(MRQ)輸入: 圖G=(V,E)輸出: 輸出查詢到的語義結構1: /?初始化階段?/2: 對圖G=(V,E)用ApxGreedy算法進行聚集處理,存儲聚集圖Gs=(Vs,Es)的超點和超邊3: 通過儲存的超點Es與超邊Vs計算強弱關聯(lián)pij4: 通過遍歷聚集之后邊上的強弱關聯(lián)pij 來隨機游走查找4種語義結構5: 通過已查詢到的結構計算其成本損失誤差C6: 根據(jù)成本誤差C對語義結構進行排序并輸出前n個結構

3 實驗結果及分析

3.1 實驗環(huán)境

本文所有實驗都是在一臺PC機上運行的，PC機的配置如下：Intel(R) Xeon(R) CPU E51630 v4 ,3.70 GHz，內(nèi)存8 GB，Windows10 操作系統(tǒng)。本文的算法是基于Java語言編程實現(xiàn)的，其中開發(fā)工具是IntelliJ IDEA。

3.2 實驗環(huán)境

第一組數(shù)據(jù)集是使用來自歐洲大型研究機構的電子郵件數(shù)據(jù)生成的(email-Eu-core network)。如果發(fā)送了至少一封電子郵件，那么網(wǎng)絡中存在邊緣(u,v)。 電子郵件僅代表機構成員(核心)之間的通信，數(shù)據(jù)集不包含來自世界其他地方的傳入消息或傳出消息。數(shù)據(jù)是以 TXT 格式進行加載和使用的。圖中的頂點數(shù)是1 005個，邊數(shù)是25 571條。

第二組數(shù)據(jù)集是使用來自歐洲大型研究機構的電子郵件數(shù)據(jù)生成的(email-Eu-core network)。如果發(fā)送了至少一封電子郵件，那么網(wǎng)絡中存在邊(u,v)。 電子郵件僅代表機構成員(核心)之間的通信，數(shù)據(jù)集不包含來自世界其他地方的傳入消息或傳出消息。數(shù)據(jù)是以 TXT 格式進行加載和使用的。圖中的頂點數(shù)為1 005個，邊數(shù)為25 571條。

第三組數(shù)據(jù)集是DBLP計算機科學書目提供了計算機科學研究論文的綜合列表(DBLP collaboration network and ground-truth communities)。如果至少發(fā)表一篇論文，構建一個共同作者網(wǎng)絡，兩個作者之間相互關聯(lián)。作者發(fā)布到某個期刊或會議形成一個社區(qū)。圖中的頂點代表論文，邊代表作者之間存在的合著關系。數(shù)據(jù)是以 TXT 格式進行加載和使用的。圖中的頂點數(shù)為317 080個，邊數(shù)為 1 049 866 條。

第四組數(shù)據(jù)是利用python代碼生成的已知圖，每個圖都含有固定數(shù)量的語義結構，其中共構造了七個圖，這七個圖中包含四種語義結構，鏈(ch)、星形圖(st)、二部圖(bc)和團(fc)各20、40、60、80、100、1 000，10 000個。

3.3 實驗結果分析

本文從不同方面分析算法在不同大小的數(shù)據(jù)上的效率表現(xiàn)。

根據(jù)VoG中使用的數(shù)據(jù)集Notre Damesi，使用MRQ算法在不同數(shù)量的邊上與VoG結果進行比較，并根據(jù)VoG實驗給出的數(shù)據(jù)得出結果，如圖6所示。

圖6 MRQ和VoG在數(shù)據(jù)集Notre Damesi上的執(zhí)行時間

在第二個數(shù)據(jù)集上使用本文MRQ算法和VoG算法，由表1可知，隨著邊的數(shù)量逐漸增加，本文算法和VoG算法的運行時間也越來越長，當邊的數(shù)量增加到一定程度時，算法的運行成本也會大幅增加。

表1 MRQ、VoG在數(shù)據(jù)集email-Eu-corenetwork的響應時間

通過表1可以清晰地對比出，在同樣的數(shù)據(jù)集上本文的算法MRQ與VoG在時間上有了本質(zhì)上的縮減。隨著邊數(shù)的增加，VoG迭代的次數(shù)會越來越大導致時間的增長速度的比較大，而本文的MRQ比VoG快了兩個數(shù)量級。

在第二個數(shù)據(jù)集上運行了本文MRQ算法，檢驗其在大數(shù)據(jù)集上的響應時間，結果如表2所示，充分驗證了本文算法在大數(shù)據(jù)集上也有很大的提升，百萬邊的大數(shù)據(jù)集運行時間都控制在1 min以內(nèi)。

表2 MRQ在數(shù)據(jù)集DBLP上的響應時間

在確認本文MRQ算法與VoG算法在時間上有了很大優(yōu)化之后，對第三組數(shù)據(jù)集上查找的準確率進行對比實驗，如圖7所示。

圖7 MRQ和VoG在構造圖上的準確率

通過第三組實驗，可以清晰地看出，MRQ算法和VoG算法都可以保持比較高效的準確性，MRQ算法的平均準確率可以達到98%左右，而VoG算法在小數(shù)據(jù)集上的準確率沒有MRP算法的準確率高，最大相差5%左右，并且MRQ算法的平均準確率比VoG高3%左右。

綜上所述，與VoG算法相比，MRQ算法在時間上快了10倍，并且在大數(shù)據(jù)集上的子圖查詢的準確率表現(xiàn)的更加優(yōu)異，無論在大數(shù)據(jù)集還是小數(shù)據(jù)集MRQ都有很好的表現(xiàn)，不僅比VoG節(jié)省更多的查詢時間，而且準確率也有很好的表現(xiàn)。

4 結 語

當前關于語義結構的查詢大多是基于大圖上直接查詢的，本文對簡單無向大圖使用ApxGreedy算法進行聚集處理，再根據(jù)聚集后的語義結構的特征，即超點之間和超點內(nèi)的強弱關系確定跳轉概率來對每種語義結構進行隨機游走查詢。最后定義成本誤差來對查找到的結構進行排序并輸出結果。用本文的算法與VoG算法進行了對比實驗，在相同的真實數(shù)據(jù)集下，本文算法明顯在時間和準確性上優(yōu)于VoG，說明本文的算法能提高查詢語義結構的效果和效率。

本文使用的簡單無向無加權的大圖都是同構圖，即圖中頂點的屬性是一致的?，F(xiàn)實生活中還存在異構圖，即頂點的屬性是不一致的。所以，下一步將研究帶異構圖中的基于聚集圖的語義結構剪枝查詢算法。