大規模動態圖中概率游走約束的節點相似Top-k 查詢方法

陳 澤，丁琳琳，宋寶燕，王俊陸

（1.遼寧大學 信息學院，沈陽 110036；2.山東能源新汶礦業集團有限責任公司，山東 泰安 271200；3.東北大學 資源與土木工程學院，沈陽 110004）

0 概述

圖作為一種抽象的數據結構，能夠有效描述現實中各類對象間的復雜關系［1-2］，并廣泛應用于社交網［3］、智能交通網［4］與語義Web 分析［5］等領域。在圖結構中，節點間的相似性度量是各類圖查詢處理的基礎［6］，且可利用得到的查詢結果對節點對間的相似程度進行分析。因此，節點相似性查詢是圖研究領域中的重要問題［7］。

隨著大數據［8］與信息技術［9］的應用，圖中使用的數據規模逐漸增大，圖的節點與邊都隨著時間推移不斷發生動態變化［10-11］。因此，大規模動態圖上的節點相似Top-k 查詢成為圖研究領域中的熱點與難點問題［12］。現有圖節點相似Top-k 查詢方法多數為迭代計算相似度方法［13］，在迭代過程結束前不能得出結果，造成系統資源浪費，且迭代計算可能造成次優相似度累加結果優于最優解，從而導致查詢結果錯誤［14］。此外，迭代查詢方法通常需要遍歷全圖，未考慮到圖結構發生動態變化時如何對查詢過程及結果進行更新維護［15］的問題。上述方法在小規模圖或靜態圖［16］上具有較高的查詢效率與準確度，但不能滿足大規模動態圖對相似查詢效率及準確度的要求。

本文提出一種基于PageRank 的節點相似Top-k查詢方法。該方法通過對PageRank 進行概率游走約束，避免了概率游走反復選取少數邊的情況，并實現將基大圖生成多個小規模單向圖。同時，結合Monte Carlo 模擬法思想，以Top-k 取值為約束條件，有效解決次優相似度疊加問題，提高查詢效率。依據局部自適應原則提出基大圖觸發更新策略和單向圖集聯動更新策略，從而解決查詢效率較低的問題。

1 相關工作

目前，國內外研究人員針對圖節點相似Top-k 查詢方法的研究眾多。文獻［17］提出一種基于節點指紋信息進行相似性查詢的FR 方法，但因為處理節點指紋信息代價較大，所以該方法在大規模圖上的查詢效率較低。文獻［18］提出一種較為精確的迭代計算算法，但該算法在計算相似度的過程中需計算所有節點對的SimRank 相似度，存在計算代價過大的問題。文獻［19］構建一種新的概率計算框架，該框架通過降維的方式能夠有效減少計算量，但在相似度計算中還存在冗余問題，導致查詢結果準確度不高。文獻［20］通過對SimRank 方法進行加權來衡量用戶對具體信息的偏好程度，從而實現相似推薦查詢，但該方法適用于小規模圖查詢，在大規模圖上存在計算權值及查詢對比代價過高的問題。文獻［21］提出一種KM 方法，它通過預計算節點對相似度的邊界來提高查詢效率，但是因為該方法需要進行大量預處理操作，且當圖更新時需要重新計算相似度邊界，所以其在動態圖上的查詢效率較低。文獻［22］提出基于SimRank 的概率游走算法，該算法對節點間相似度的計算表示進行改進，查詢效率較高，但它無法保證在動態圖上的查詢準確度。文獻［23］提出一種在異構信息網絡中的相似性搜索方法，通過x-star 模式來實現相似性搜索，但該模式計算代價較高，且在動態圖上的查詢效率較低。文獻［24］提出基于有向圖的相似性度量方法，依據圖的結構特征綜合性衡量相似性，但其處理過程復雜，不能適用于動態圖查詢。

本文對節點相似Top-k 查詢方法進行深入研究，并提出一種大規模動態圖概率游走約束的節點相似Top-k 查詢方法。該方法綜合考慮大圖的數據規模及圖動態變化時，對節點相似查詢效率及結果集準確度的影響。

2 概率游走約束的相似度累積查詢

大規模圖中游走步數的增大將會直接影響查詢效率，為降低基大圖節點相似度計算次數，避免Top-k 查詢中多個“遠關系”的疊加結果優于“近關系”的問題，本文引入PageRank 概率游走機制，并提出利用單邊弱化因子對概率進行約束，將基大圖轉化為多個小規模單向圖，以k取值為約束條件來遞增游走步數，實現單向圖集上的節點相似Top-k 快速累積查詢。

2.1 PageRank 概率約束

定義1基大圖：假設Gr表示基大圖，即大規模動態圖，節點u為基大圖Gr中的節點，（u，v）表示基大圖Gr中的邊。

定義2單向圖：假設Gs表示基大圖中的單向圖，則且v至多取一個節點。其中，節點u為基大圖Gr中的節點，在單向圖Gs中，（u，v）表示節點u的唯一出邊。

當單向圖進行選取時，需要從基大圖中的查詢節點開始，從圖中查詢節點及其相關節點中隨機選出一條路徑進行迭代計算，滿足每個節點有且僅有一條出邊，但可以存在多條入邊的情況。為確保隨機選取的效率，本文引入PageRank 概率游走機制進行路徑選取，具體如式（1）所示：

其中，P（u）為節點u被訪問到的概率，d表示算法繼續訪問執行的概率，N為基大圖中所有的節點數量，in（u）表示所有指向節點u的節點集合，out（v）表示節點v指向其他節點的集合。單向圖的大小可根據具體的Top-k 查詢條件及游走步數i來確定。圖1 為基大圖轉化為單向圖的示意圖。

圖1 單向圖轉化示意圖Fig.1 Schematic diagram of unidirectional graph conversion

從圖1 可知，通過概率游走得到的單向圖可有效降低圖規模。由于單向圖是在基大圖中通過概率游走機制選取的，若某個或某些節點的出邊數較少或只有一條出邊，則會導致對PageRank 概率游走進行選取時，每個單向圖中出現出邊的概率較大，進而在相似度計算時會反復疊加這些邊，直接影響查詢結果的準確度。

為避免上述問題，本文對單向圖的各條邊引入單邊弱化因子參量，并進行PageRank 的概率約束。其中，n為選取次數。將因子參量賦予給單向圖中的每條邊，若某條邊被選中的次數越多，則其對相似度計算的影響力下降越多，重復選中該邊的概率將會形成弱化趨勢。圖2 為單向圖集構建示意圖。

圖2 單向圖集構建示意圖Fig.2 Schematic diagram of unidirectional graphs construction

如圖2 所示，單向圖1 與單向圖2 均是由圖1 中基大圖通過弱化重復路徑約束生成的單向圖。以節點h為例，因為h只有一條出邊，所以生成的所有單向圖均含有邊（h，c）。在單向圖1 中，邊（h，c）的影響力為1，而在單向圖2 中，在單邊弱化因子的作用下，其影響力降至為1/2，這說明通過減少某一條邊的反復疊加，可有效降低對相似計算結果的影響。

2.2 節點相似Top-k 累積查詢

如果要找到查詢節點u的相似節點v，則需要找到節點u和節點v在j步概率游走內的可能相遇節點。由于查詢游走步數較多，在基大圖上的遍歷查詢效率很低，因此本文基于Monte Carlo 模擬法思想，在整個單向圖集中選取若干個查詢節點u的j步隨機相遇節點，使用節點的累積相似度代替節點真實相似度。

假設弱單向圖集為Gs={Gs1，Gs2，…，Gsn}中的單向圖，且是相互獨立的隨機樣本，給基大圖G中的邊隨機分配權重值，則由大數定理可得：

由式（2）可知，當n→∞時，基大圖中個體和總體的均值差值正向趨近于0。因為弱單向圖集中的各個單向圖具有極小的相關性，且只與查詢節點u的j步游走鄰居節點相關，所以由Monte Carlo 模擬法可得，當弱單向圖集Gs中的各個單向圖樣本滿足路徑覆蓋時，其計算結果可滿足基大圖G的誤差需求，且具有更快的收斂性。累積相似度計算方法如式（3）所示：

其中，節點u、v表示概率游走的節點，ω表示相遇節點，pt(u，ω) 及pt(v，ω) 為節點u、v在概率游走過程中出度倒數的乘積，j表示游走步數，∏w為單邊弱化因子的疊乘值。

2.3 節點相似Top-k 算法

針對基大圖游走步數遞增會降低圖查詢效率的問題，本文通過多次引入PageRank 概率游走機制，并提出單邊弱化因子對其進行概率約束，實現基大圖轉化為多個單向圖集合。由于查詢游走步數較多導致基大圖上的遍歷查詢效率較低，因此通過多次隨機選取查詢節點，利用大數定理進行驗證，并計算出節點的累計相似度作為節點的真實相似度，以Top-k 取值為基準逐步增大游走步數，實現節點相似Top-k 的快速累積查詢。

節點相似Top-k 算法描述如算法1 所示。其中，通過PageRank 概率游走機制得到N個單向圖的圖集，且在每個單向圖中，根據概率游走路徑找到節點ur的t步相遇節點集，再將節點的游走概率以及單邊弱化因子疊乘值代入相似度計算公式中進行計算，以k值作為約束條件，從相遇節點集中選出節點ur的相似節點集，并對節點進行相似度排序得出最終結果。

采用概率游走約束的節點進行相似Top-k 累積計算，且當計算結果滿足Top-k 結果集需求時，則立即停止迭代并輸出結果集，避免多個“遠關系”的疊加結果優于“近關系”的問題，并提高查詢效率。算法1 中對n個單項圖均選取查詢節點ur進行概率游走，共找到其j步相遇節點，通過相似度計算公式計算其與查詢節點ur的相似度，排序得出查詢結果。因此，算法1 的時間復雜度為O（n·j）≈O（n）。

3 自適應動態更新

節點相似Top-k 查詢方法在大規模圖中可以快速反饋滿足條件的查詢結果，但當圖發生動態變化時，為確保查詢結果的準確度，需要對圖結構及結果集進行更新維護。本文綜合更新效率及準確度2 個方面的因素，實現基大圖及單向圖集的自適應動態更新。

3.1 基大圖觸發更新

對基大圖更新時，若每次都進行實時更新，則會導致更新代價過大，且許多變化與查詢無關，造成資源浪費；若進行累計更新，則可能導致查詢結果錯誤，降低查詢準確度。因此，本文以Top-k 查詢條件作為更新操作觸發點進行自適應觸發更新，且觸發規則為：判斷查詢節點u以及u的出邊集合｛（u，v）|u∈Gr，v∈No(u)，(u，v)∈Gs｝是否發生變化，若節點u及（u，v）均發生變化，則采取即時更新策略更新查詢；若查詢節點u或其出邊（u，v）沒有發生變化，則繼續判斷在游走路徑過程中的相遇節點是否為起點，并查看起點的邊集合｛（v，r）|r∈Gr，v∈No(u)，是否變化，若發生變化，此時需采用即時更新策略；若上述2 種情形均未發生，則采用累計更新策略對圖集進行更新。

3.1.1 即時更新策略

對基大圖進行更新時，當圖中的節點及邊變化較大時通常會對圖的查詢結果產生較大影響，此時需采用即時更新策略。即時更新策略主要是針對查詢節點u及其i步鄰居節點的變化而言，采用即時更新策略的具體情況可表述為當圖發生動態變化時，首先查看節點及其出邊是否存在變化，若出現變化，則說明其相似節點等均發生變化，若不對其改變會增加查詢結果的錯誤率；若節點及其出邊未發生變化時，則需查看其鄰居節點集中各個節點的查詢節點i步鄰居節點集合是否發生變化，若發生變化，則采用即時更新策略。

即時更新策略的優勢在于當發現基大圖的變化對查詢關聯影響較大時，通過該方法可有效保證查詢結果的準確度。即時更新算法如算法2 所示。其中，判斷查詢節點u以及u的出邊集合｛（u，v）|u∈Gr，v∈No(u)，(u，v)∈Gs｝是否發生變化，若節點u及邊（u，v）發生變化，則即刻進行更新操作；若未發生變化，則繼續判斷u的鄰居節點集中各個節點的查詢節點i步鄰居節點集合是否發生變化。若查詢節點i步鄰節點集合與原數據集相比沒有發生變化，則停止遍歷，查詢結果集不變，若發生變化，則分別找出該集合中各個節點的出邊及i步鄰居節點集合，并重新計算相似查詢結果。

在算法2 中，假設共有n個節點u，對每個節點u開始遍歷，若節點u或者其出邊發生變化，則立即更新圖，因此最少時間復雜度為O（n）；若未發生變化，則需查看其i步鄰居節點集合是否發生變化，假設其鄰居節點集合數量為k，則最大時間復雜度為O（n·k）≈O（n）。由于算法2 中無需額外輔助存儲空間，因此空間復雜度為S（1）。

3.1.2 累積更新策略

即時更新策略在針對查詢節點及其鄰居節點發生變化時，能夠有效減少查詢圖時的錯誤率，但當基大圖發生的變化與查詢關聯較小時，采用即時更新策略會降低效率以及浪費空間。針對這種情況，為提高效率和節省存儲空間，本文提出一種累積更新策略，其主要步驟為：先為圖查詢創建一個輔助存儲空間Ω，該空間主要用來記錄在一段時間內圖的節點與邊的變化情況，并以一定的周期對圖進行定時更新。為避免某個節點或某條邊存在多次刪除、增添等情況，在輔助存儲空間Ω中，需要先對記錄變化進行合并操作，從而進一步提高更新效率。在輔助存儲空間Ω中為每條記錄添加一個數據變化用到的標簽，并令標簽的初始值為0。由于節點的增刪最終可以轉化為邊的增刪，因此表中只需記錄邊的增刪，并以設定的?t為周期累加輔助表標簽值，進而更新圖。

累計更新策略的優勢在于能夠避免某條邊的重復刪減情況，通過這種標簽的設定不僅可以簡化更新操作，而且可有效提高更新效率。累計更新算法如算法3 所示。其中，為更新圖中每條邊的增減情況記錄均設定一個標簽（u，v，i），若刪除邊（u，v）則將其標記為（u，v，-1）；若增加邊（u，v）則將其標記為（u，v，1）；接下來對更新圖中的所有邊進行遍歷，若標簽值為0，則說明不需增加刪除邊；若標簽值為1，則說明需要增加邊；若標簽值為-1，則說明需要刪除邊。在統計完所有邊的標簽后，再對圖進行更新操作。

在算法3 中，假設圖中共有n條邊（u，v），并對每條邊的記錄進行統計，共需統計n次，因此其時間復雜度為O（n）。由于統計一次邊需額外開辟輔助空間對記錄進行存儲，因此空間復雜度為S（n）。

3.2 單向圖集聯動更新

如3.1 節所述，當基大圖發生變化時，為保證查詢的準確度，需要對單向圖集進行對應的更新操作。為避免重新選取單向圖，本文基于局部更新原則分別對單向圖集中所有單向圖中邊和節點的變化進行局部更新處理，更新策略可表述為：

1）增加邊：當基大圖中增加某條邊（a，b）時，判斷邊（a，b）中頭節點a的出邊數Num（a），若節點a出邊數Num（a）=0，則需要在每個單向圖中均增加邊（a，b）；若節點a出邊數Num（a）≠0，則需要在所有單向圖中為該節點重新選取一條出邊。

2）刪除邊：當基大圖中刪除了某條邊（a，b）時，判斷邊（a，b）中頭節點a的出邊數Num（a），若節點a出邊數Num（a）=1，則在所有單向圖中刪除這條邊；若節點a出邊數Num（a）>1，則為所有包含被刪除邊的單向圖中的節點a重新選取一條出邊。

3）增加節點：當基大圖中增加節點u時，主要看其是否有邊（u，v）的增加，若沒有邊的增加，則不需處理單向圖集，否則按上述邊的增加方法來更新圖集。

4）刪除節點：當基大圖中需要刪除某節點時，先要查看是否存在以該節點為頭節點或者為尾節點的邊，若存在以該節點為頭節點的邊，則需要在每個單向圖中刪除這樣的節點以及以它們為頭節點的邊；若存在以該節點為尾節點的邊時，則需刪除并找到它們的頭節點；若不存在上述兩種情況，則不需處理。其中，若節點不存在出邊則不進行處理，并在每個單向圖中為其余節點重新選取一條出邊。

圖3 為基大圖中刪除節點f、增加邊（g，h）時，單向圖集中的單向圖更新示意圖。

圖3 基大圖與單向圖更新示意圖Fig.3 Schematic diagram of base large graph and unidirectional graph updating

如圖3 所示，通過對各單向圖節點和邊的局部操作，可以最大程度地降低單向圖集的更新代價，進而提高大規模動態圖Top-k 查詢效率。單向圖更新算法如算法4 所示，其過程為在單向圖集中判斷邊（u，v）以及節點u是否出現上述某一種情況，并針對上述中某一種情況進行相應操作。

4 實驗結果與分析

實驗從查詢效率、結果可靠性及更新效率等方面驗證本文所提方法的有效性。實驗的硬件配置為Windows10 系統主機、16 GB 內存、CPU 型號為Intel i5-9300H 以及64 位操作系統、2 TB 硬盤。為驗證本文方法的有效性，本文選取5 組節點與邊數量均不等的數據集，具體如表1 所示。

表1 實驗數據集Table 1 Experimental datasets

4.1 節點相似Top-k 查詢效率分析

圖4為在5 組數據集下，FR、KM、SimRank、P-SimRank 方法與本文方法的查詢效率對比結果。其中，實驗以平均查詢時間作為查詢效率評價準則。從圖4 可以看出，相比其他方法，本文方法具有較高的查詢效率。這是由于FR 與KM 采用的是在結果集中過濾掉不合格節點的方法，造成查詢效率較低，SimRank 與P-SimRank 在計算過程中容易造成相似度疊加問題，因此其適用于小規模的圖查詢問題，在大圖上權值的計算及查詢效率較低，本文方法僅需篩選出查詢節點的相似節點，因此需要處理的數據量很小，查詢效率較高。

圖4 4 種方法的查詢效率對比Fig.4 Comparison of query efficiency of four methods

4.2 節點相似Top-k 查詢結果可靠性分析

圖5 為4 種方法查詢結果的可靠性對比。從圖5可以看出，本文方法的準確度與FR、KM 方法的原圖查詢準確度近似，但FR、KM 方法存在穩定性較差以及準確度差異較大的問題。本文方法具有較高的可靠性，這是由于SimRank、P-SimRank 方法中的節點間相似度計算僅考慮了游走過程中節點相遇總時間的數學期望，無法保證較高的查詢準確度。因此，本文方法查詢結果的準確度相對較高。

圖5 4 種方法的查詢結果可靠性對比Fig.5 Reliability comparison of query results of four methods

4.3 自適應動態更新策略分析

實驗通過分析邊的更新效率來驗證更新策略的有效性，每個圖隨機選擇約80%的插入邊和20%的刪除邊進行更新。表2 為在4 個數據集上更新1 000 條邊的原圖與單向圖的時間。從表2 可知，本文提出的更新策略在各個數據集上均可達到較高的更新效率。

表2 本文更新策略在4 個數據集上的更新效率Table 2 Update efficiency of the proposed strategy on four datasets

5 結束語

本文利用大規模動態圖概率游走約束條件，提出一種節點相似Top-k 查詢方法。該方法通過引入PageRank 概率游走機制，實現將基大圖轉化為多個單向圖集，并依據Monte Carlo 模擬法思想實現Top-k節點相似查詢。實驗結果表明，與FR、KM、SimRank及P-SimRank 方法相比，本文方法的查詢準確度與查詢效率均有大幅提升，且在查詢準確度上表現出良好的穩定性?？紤]到圖中邊的權值對節點相似度的影響以及對圖查詢與更新的重要性，后續將采用SimRank 及其優化方法對加權圖的相似節點Top-k查詢進行改進，進一步提高查詢效率與準確度。