基于元路徑加權融合的異構網絡相似性度量

趙宇紅，薛維佳

(內蒙古科技大學 信息工程學院，內蒙古 包頭 014010)

0 引 言

相似性度量是信息網絡挖掘與分析的重要且基礎的任務[1]。異構信息網絡[2]可以表達更豐富且深層次的語義，基于異構信息網絡的相似性度量能夠更全面地發(fā)現(xiàn)節(jié)點間的關聯(lián)及網絡中隱藏的知識。因此，如何構建一種準確且高效的異構信息網絡相似性度量算法是一個非常有意義的課題。現(xiàn)有的異構網絡相似性度量大多是基于節(jié)點間的鏈接關系，如PathSim[3]、AvgSim[4]、HeteSim[5]算法等。PathSim是最早提出的根據(jù)元路徑來進行相似性度量的算法，是一種基于對稱元路徑的相似性算法，在相同類型節(jié)點關聯(lián)度量中具有較好的代表性。而實際的異構網絡中度量不同類型對象之間的相似性也具有現(xiàn)實意義[6]。HeteSim算法通過雙向隨機游走到元路徑的中心來度量不同類型節(jié)點相似性，但是，算法復雜度較高，不適用于大規(guī)模的異構網絡。AvgSim算法是基于單條元路徑下通過正反向兩次游走取平均的方式來度量相似性，但是算法需要預設元路徑，而不同的元路徑擁有不同的語義信息，根據(jù)不同元路徑進行相似性度量會得到不同的度量結果，因此選用單條元路徑進行度量在一定程度上會影響相似性度量算法的準確性。鑒于現(xiàn)有異構信息網絡相似性度量在度量類型及準確性等方面的問題，本文在考慮元路徑對語義表達貢獻程度的基礎上，融合多條關鍵元路徑，提出了一種可度量任意類型節(jié)點間的相似性度量的Multi-WPathSim算法。

1 Multi-WPathSim算法

1.1 相關概念

定義1 異構信息網絡: 異構信息網絡是包含多種節(jié)點與關系的信息網絡，可以由式(1)表示。其中在網絡G中，節(jié)點集合為V，鏈接關系為E，節(jié)點類型集合為T，鏈接關系所屬類型集合為R

G={V,E,T,R,φ,φ,ψ}

(1)

其中，φ、φ、ψ分別代表節(jié)點間關系映射、節(jié)點類型映射、鏈接關系類型映射，并且當且僅當|T|>1或者|R|>1時，網絡G為異構信息網絡，若|T|=1和|R|=1則G為同構。

定義2 網絡模式(Network Schema)[7]:網絡模式S類似于數(shù)據(jù)庫中的ER圖，圖中頂點為網絡G中的節(jié)點類型集合T，邊為鏈接關系集合R，記為S=(T,R)。圖1為幾種經典異構信息網絡中的網絡模式圖。

圖1 經典異構信息網絡模式實例

圖2 DBLP網絡模式及元路徑實例

1.2 任意類型節(jié)點相似性度量

PathSim算法是通過矩陣相乘的方式來計算相同類型節(jié)點間的相似度。相似度用s(x,y)表示，其中x,y表示同類型節(jié)點。其計算公式如下

(2)

P是已事先確定的元路徑，px→y代表了在當前元路徑下，從節(jié)點x到y(tǒng)的所有路徑實例；px→x代表了從節(jié)點x到x的所有路徑實例；py→y代表了從節(jié)點y到y(tǒng)的所有路徑實例。這里x、y節(jié)點代表同種類型的節(jié)點，它們之間的相似性由路徑數(shù)目決定。

PathSim算法僅針對相同類型節(jié)點即局限于對稱元路徑，且元路徑是預設的單條路徑，異構信息網絡中包含了多類型節(jié)點及多條元路徑，為更準確地進行相似性度量，本文在PathSim算法的基礎上進行了改進，提出了可以度量任意類型節(jié)點間相似性的相似性度量方法

(3)

其中，Tx=Ty代表節(jié)點類型相同。當Tx≠Ty時，px→x、py→y的計算公式為

px→x=r(x)r(x)px→x∈P′

(4)

py→y=r(y)r(y)py→y∈P′

(5)

其中，元路徑P′=PP-1，以DBLP數(shù)據(jù)集為例，當元路徑P為APC，則元路徑P′代表了APCPA。r是M的主特征向量，MP′為元路徑P′的關系矩陣。

1.3 Multi-WPathSim算法

異構信息網絡中節(jié)點序列構成了許多元路徑，每一條元路徑既蘊含了不同的語義，也在語義表達中占據(jù)著不同的重要程度。任何獨立的元路徑或對稱元路徑集合都不能全面覆蓋異構信息網絡中豐富的語義信息，為提高相似性度量的準確性和計算效率，既要包括多樣化的元路徑又要考慮不同元路徑對語義表達的影響力，同時設計高效的計算模式也是非常必要的。基于上述目標，本文提出的Multi-WPathSim算法，利用加權融合元路徑的方法來進行相似性度量。本文的算法框架如圖3所示。

1.3.1 獲取元路徑

為更準確地度量相似性，應該確定關鍵的元路徑集合，并按照元路徑在語義表達的貢獻程度進行路徑融合。

圖3 Multi-WPathSim算法框架

首先，基于相似度度量的目標實體確定元路徑的出節(jié)點與入節(jié)點。譬如，在DBLP數(shù)據(jù)集中，如果要衡量作者與出版社之間的相似度，那么元路徑的出節(jié)點與入節(jié)點就是作者與出版社。

其次，設定元路徑的路徑長度l，隨機游走遍歷所有的元路徑，得到所有的元路徑的路徑集合。Sun等[3]通過大量實驗證實，元路徑長度相對短時就可以很好地度量相似性，并且隨著路徑長度的增大，路徑實例數(shù)也呈現(xiàn)指數(shù)級的增長。借鑒這樣的研究結論，本文將元路徑長度l設為2～5。

最后，根據(jù)元路徑遍歷得到所有的路徑實例。輸入到已構建的CBOW(continuous bag of words)模型，其模型結構如圖4所示。通過學習訓練，得到中心節(jié)點與其它節(jié)點同時出現(xiàn)的概率，使用節(jié)點出現(xiàn)概率確定元路徑的存在概率，它表達了該路徑對語義表達的貢獻程度，該概率將作為路徑的權重。

圖4 CBOW模型結構

1.3.2 基于CBOW的元路徑權重計算

CBOW模型也稱為連續(xù)詞袋模型，該模型根據(jù)中心詞的上下文來預測句子的概率[9]，即已知當前詞wt的上下文為wt-n,wt-n+1,……,wt+n-1,wt+n，預測當前詞wt，該模型通過詞向量間的空間相似度來衡量文本語義上的相似度，本文將詞向量空間關聯(lián)引用至節(jié)點序列關聯(lián)。

利用CBOW模型學習元路徑權重的具體步驟如下：

(1)獲取路徑實例，在路徑長度的約束下，循環(huán)遍歷得到所有的路徑實例。例如，在DBLP數(shù)據(jù)集中要計算元路徑為APTP下的路徑實例數(shù)，則需要對DBLP數(shù)據(jù)集鏈接關系集進行分解，得到關于AP，PT，TP的鄰接矩陣，然后隨機以一節(jié)點Ai開始，根據(jù)鄰接矩陣確定下一跳節(jié)點，利用循環(huán)遍歷得到基于元路徑APTP的所有路徑實例；

(2)將路徑實例作為語料庫輸入到CBOW模型中，通過隱藏層將輸入層輸入的節(jié)點初始化向量做求和累加運算，在輸出層得到哈夫曼樹。在哈夫曼樹中每一個非葉子節(jié)點代表一次二分類問題，葉子節(jié)點代表網絡中出現(xiàn)的每一個節(jié)點，利用每個葉子節(jié)點對應的哈夫曼編碼以及二分類處理計算任意兩節(jié)點同時出現(xiàn)的概率。

(3)通過兩兩節(jié)點出現(xiàn)概率確定元路徑實例的存在概率，最終，確定當前元路徑的存在概率。具體計算方法如式(6)-式(11)：

計算隱藏層的輸出h

(6)

其中，C代表窗口大小，xi代表第i個節(jié)點，W為權重矩陣。該輸出h代表對輸入層輸入的節(jié)點向量加權求平均。

計算在輸出層每個節(jié)點的輸入

(7)

計算輸出層的輸出

(8)

其中，V代表網絡中包含的節(jié)點數(shù)，c代表窗口內的任意節(jié)點數(shù)，yc,j代表輸出層中節(jié)點j與窗口中的任意節(jié)點數(shù)的概率值。

計算單條路徑實例的存在概率

(9)

其中，yk代表當前路徑實例的存在概率，l代表元路徑長度。

根據(jù)式(9)得到的結果，來計算當前元路徑的存在概率。計算公式如下

(10)

其中，n代表路徑實例個數(shù)。Pm代表在當前元路徑的存在概率。

在確定好所有元路徑的存在概率后，利用存在概率極限值δ來確定有效元路徑集合。通過元路徑存在概率，計算不同有效元路徑所占的權重，然后，加權融合進行最終的相似性度量計算。其中，概率極限值δ需要通過實驗來確定。

元路徑的權重計算公式為

(11)

其中，m代表了當前的元路徑，k代表了符合條件的元路徑的條數(shù)。

1.3.3 元路徑融合

本文采用線性融合的方式對元路徑進行加權融合。在此基礎上得到最終的相似性度量算法計算方式。其具體公式為

(12)

其中，sm(x,y)是基于式(3)計算在元路徑m中的相似性度量結果。

2 實驗與分析

2.1 數(shù)據(jù)集與評價標準

本文選取的數(shù)據(jù)集為ACM數(shù)據(jù)集以及DBLP數(shù)據(jù)集。ACM數(shù)據(jù)集和DBLP數(shù)據(jù)集均為異構信息網絡中的經典數(shù)據(jù)集，其網絡模式圖如圖1(a)和圖1(b)所示。

DBLP數(shù)據(jù)集中選取計算機四大研究領域的20個會議，2277篇論文，5000個作者，13 576個關鍵字，以及與論文之間存在鏈接的會議、作者、關鍵字這3類節(jié)點的關系數(shù)23 757條。

ACM數(shù)據(jù)集包含14個科學會議，以及在這些會議上發(fā)表的論文1.2萬篇，1.7萬作者，1800個作者從屬機構，73個論文主題以及1500個關鍵字。

為評價算法的有效性、準確性，仿真實驗分別采用標準相似性算法衡量指標AUC(area under the receiver ope-rating characteristic curve)[10]、Precision[10]來驗證度量的準確性以及在相同聚類算法的基礎上，用歸一互化信息NMI[11]指標來驗證聚類的效果。

AUC指標從全局來衡量算法的精確度，其定義為

(13)

其中，n代表總共比較的次數(shù)，n′代表隨機從測試集中取出的邊的分數(shù)值大于不存在的邊的分數(shù)次數(shù)，n″代表兩分數(shù)值相等次數(shù)[11]。

Precision值是度量排在前L個預測結果中被度量準確的比例。如果有m個結果準確，則Precision定義為

(14)

顯然，AUC與Precision分別從整體性及局部命中率方面，衡量了算法的準確性，在相近的AUC的情況下，Precision值越大表明結果越準確。

歸一化互信息NMI(normalized mutual information)值是度量聚類結果與給定標準劃分間的相似程度[11]。NMI值越高，說明所提出的相似度算法的聚類效果更有效和準確。

2.2 仿真方案設計

本文中我們選擇與3種經典的相似性度量算法來進行對比。這3種算法分別是：PathSim算法，HeteSim算法和AvgSim算法。PathSim算法在單條元路徑上通過矩陣相乘度量相同類型節(jié)點相似性；HeteSim算法與AvgSim算法都是通過雙向隨機游走度量不同類型節(jié)點間相似性[6]。所以在對比過程中，HeteSim算法與AvgSim算法可以直接用非對稱元路徑來進行對比，PathSim算法采用對稱元路徑來展開對比。

元路徑的概率極限值δ是指判斷元路徑存在的概率為多大時可以影響整個相似性度量算法的準確度。取值過大，會導致有效的元路徑過少，丟失一些異構信息網絡的語義信息；取值過小，可能會使得一些對相似性度量算法影響較小的元路徑存在，導致算法的復雜度過高，影響算法的效率。實驗所選用的路徑關系為DBLP中“撰寫關系”，路徑長度l為2-5，用AUC值進行參數(shù)估計，圖5為不同概率極限值下的相似性度量結果準確率比較。由仿真結果圖可知，算法的準確率在概率極限值為0.3時達到最高，并隨著極限值的增大而減小，因此本文所選定的概率極限值δ為0.3。

圖5 不同概率極限值下的AUC值比較

2.3 結果與分析

2.3.1 元路徑的選擇與存在概率的確定

在進行元路徑的確定時，首先需要確定計算的目標實體，也就是元路徑的出節(jié)點與入節(jié)點。以往解決方案中，對稱路徑的考慮較多，在本文中，度量的重點在于非對稱元路徑，所以選擇的元路徑的出節(jié)點與入節(jié)點是不同類型的節(jié)點。本文選用的度量對象是作者與論文。表1為元路徑長度為2-5時，遍歷的元路徑、元路徑實例個數(shù)以及當前元路徑的存在概率。

2.3.2 元路徑的權重確定

通過參數(shù)討論中的概率極限值比較，最終確定的概率極限值為0.3，選擇概率大于0.3的元路徑來進行融合加權。因此，確定了最終的元路徑條數(shù)以及根據(jù)上述的權重計算式(11)得到最終的元路徑權重。表2為最終得到的元路徑集合以及相應的權重。

2.3.3 算法準確性驗證

表3給出了在ACM數(shù)據(jù)集中，元路徑為APVCVPA下，根據(jù)不同的相似性度量算法，檢索與作者Christos Faloutsos最相近的前5位作者以及他們之間的相似性度量分數(shù)。元路徑APVCVPA表示兩個作者在同一個會議中發(fā)表論文。如表3所示，在相似性度量結果中，找出的作者集合有部分是重合的，表明本文提出的算法是有效的。而根據(jù)元路徑可知，如果作者的研究領域相同，那么他們發(fā)表的論文屬于同一個會議的可能性就更大，因此可知與Christos Faloutsos最相似的作者是Philip Yu、Jian Pei、Jiawei Han等。

表1 DBLP數(shù)據(jù)集中不同元路徑實例個數(shù)及其存在概率

表2 元路徑集合以及權重分配

表4是在元路徑為APVC下，根據(jù)不同的相似性度量算法，檢索與作者Christos Faloutsos最相近的前5個會議以及他們之間的相似性度量分數(shù)。因為PathSim算法是度量對稱元路徑間的相似性，所以本部分實驗選用其它幾種相似形式度量算法進行比較。已知Christos Faloutsos是KDD的一位非常有影響力的研究員，根據(jù)表4得出的結果，那么與Christos Faloutsos相似度較高的幾位作者所在的影響力比較大的幾家期刊也應該與Christos Faloutsos相似度比較高。而VLDB，SIGMOD，SIGIR中Philip Yu，Jian Pei，Jiawei Han等的影響力比較高，社區(qū)排名分數(shù)比較靠前。所以，本文的度量結果是準確的。

表3 ACM數(shù)據(jù)集中對稱元路徑下與作者“Christos Faloutsos”相關Top-5

表4 ACM數(shù)據(jù)集中非對稱元路徑下與作者“Christos Faloutsos”相關的期刊Top-5

為了驗證本文的算法可適用于任意類型節(jié)點的相似性度量，分別在對稱元路徑與非對稱元路徑下進行準確率的仿真實驗。

表5為在對稱元路徑下，通過不同的路徑關系分別驗證算法的準確率。其中，PathSim算法、HeteSim算法、AvgSim算法中作者關系的元路徑為APCPA，會議關系的元路徑為CPAPC，論文關系的元路徑為PAPCPAP。實驗結果表明：在聚類結果上，本文算法相比PathSim、Hete-Sim、AvgSim算法NMI值分別提高了10.27%、5.73%和0.56%，說明本文算法相比其它相似性度量算法在聚類任務中的表現(xiàn)更好；在全局相似度度量結果上，本文算法的AUC值相比其它算法平均提升了4.65%、3.93%和2.97%；從局部準確率結果來看，本文Precision值相比其它算法分別提升了6.33%、2.33%和2%，說明本文算法的相似性度量準確率更高，度量效果更好。

表5 在對稱元路徑下不同相似性度量算法的準確度比較

表6為在非對稱元路徑下的相似性度量算法準確率比較，因為PathSim算法只能度量同類節(jié)點間的相似性，因此本次實驗選用HeteSim算法、AvgSim算法與本文算法進行比較。其中，HeteSim算法與AvgSim算法的撰寫關系的元路徑為APCPTP，發(fā)表關系的元路徑為APTPC。對比實驗結果可知，在相似性度量結果上，本文的算法相比HeteSim算法和AvgSim算法，AUC準確率分別提升了3.52%和3.01%；對比Precision值，較HeteSim算法提升了2%，較AvgSim算法降低了1%，但是Precision僅從局部考慮算法準確率，AUC是從整體上衡量算法的準確性，因此說明本文算法在非對稱元路徑上的整體度量效果更好。

表6 在非對稱元路徑下不同相似性度量算法的準確度比較

綜上所述，本文算法不僅僅局限于對稱路徑，在非對稱路徑上表現(xiàn)同樣優(yōu)秀，算法適用于任意類型節(jié)點的度量，普適性好，而且本文的算法準確率相較其它傳統(tǒng)的相似性度量算法都有較大的提升，因此，Multi-WPathSim對異構信息網絡相似性度量是可行的、有效的且準確性較好。

3 結束語

異構信息網絡能夠更全面地反映真實網絡中節(jié)點的類型與關聯(lián)，本文在研究了現(xiàn)有異構信息網絡的相似性度量算法的基礎上，重點針對PathSim算法在計算異構信息網絡節(jié)點間相似性時，只能在預設的元路徑中度量同種類型節(jié)點而不能更準確地度量異構信息網絡中任意節(jié)點的相似性問題，提出一種加權融合多條元路徑的相似性度量算法。算法充分考慮了多元路徑在異構信息的語義表達，細化了不同元路徑對相似性度量的影響，解決了PathSim算法在元路徑及節(jié)點類型的局限性，擴展了算法的普適性，提高了節(jié)點相似性度量的準確性。實驗結果表明，本算法可以有效提高算法的準確率且普適性更廣。但同時算法還有較大的提升空間，例如權重的融合方式除了線性融合，還有非線性融合方式，以及如何將該算法更好地應用于推薦系統(tǒng)或者社區(qū)發(fā)現(xiàn)等研究領域。