趙宇紅，張凱

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

相似性度量是信息網絡挖掘與分析的重要且基礎的任務.異構信息網絡[1]可以表達更豐富且更深層次的語義，基于異構信息網絡下的相似性度量能夠更加全面地發(fā)現(xiàn)節(jié)點之間的關聯(lián)以及網絡中隱藏的知識.因此，如何尋找一種準確且高效的異構信息網絡相似性度量算法是一個非常有意義的課題.

現(xiàn)有的異構信息網絡相似性度量[2]大多是基于節(jié)點之間的鏈接關系，如PathSim，AvgSim等經典算法[3，4].PathSim算法是最早提出的根據(jù)元路徑來進行相似性度量的算法，是一種基于對稱元路徑的相似性度量算法，在相同類型的節(jié)點關聯(lián)度量中具有較好的代表性.而在實際的異構信息網絡中度量不同類型對象之間的相似性也具有重要的現(xiàn)實意義.AvgSim算法是基于單條元路徑下通過正反向2次游走取平均值的方式來度量相似性，但是，算法需要預設元路徑，而不同的元路徑擁有不同的語義信息，根據(jù)不同元路徑進行相似性度量會得到不同的度量結果，因此，選用單條元路徑進行度量在一定程度上會影響相似性度量算法的準確性.

鑒于現(xiàn)有異構信息網絡相似性度量算法在度量類型以及準確率等方面的問題，本課題打算針對異構信息網絡下社區(qū)節(jié)點特征多樣性的問題，通過結合注意力機制尋找一種全新的節(jié)點相似性度量算法，主要從節(jié)點與元路徑之間的關系進行改進，通過結合注意力機制，同時考慮節(jié)點屬性與元路徑的重要性，提出一種全新的衡量節(jié)點相似性的評價指標.

1 背景

1.1 相關概念

定義1(異構信息網絡)異構信息網絡[5]是指包含各種節(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(網絡模式)網絡模式S類似于數(shù)據(jù)庫中的E-R圖，圖中頂點為網絡G中的節(jié)點類型集合T，邊為鏈接關系集合R，記為S=(T，R).圖1為幾種經典異構信息網絡中的網絡模式圖.

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

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

1.2 異構信息網絡研究現(xiàn)狀

不同于以往用于理論研究的簡單信息網絡，許多實際應用的真實信息網絡通常都涵蓋了多種關系的復雜交互，例如社交網絡，計算機系統(tǒng)，生物網絡等等.這種具有異構特征的信息網絡由Sun Y及Han J[7]等人于2009年提出明確的概念，隨后元路徑理論于2011年被提出.自此，異構信息網絡的分析和研究迅速成為數(shù)據(jù)挖掘、數(shù)據(jù)庫、信息檢索等領域的熱點，并在這些領域的各類期刊、會議中嶄露頭角.除此以外，關于異構信息網絡的專題研討會也在逐年增加.

異構信息網絡為數(shù)據(jù)挖掘領域帶來了新的挑戰(zhàn)，在此領域近十年已發(fā)表的論文中，涉及的分支主要包括分類、聚類、鏈路預測、推薦、相似性度量、信息融合、排名等，其所占的比例如圖3所示.

圖3 異構信息網絡研究比例圖

2 融合節(jié)點與元路徑的相似性度量

注意力機制[8]最近幾年在各大研究領域被廣泛使用，如圖像處理、語音識別和自然語言處理等.注意力機制和人類的視覺注意力很相似，通過快速掃描全局圖像，獲得需要重點關注的目標區(qū)域，得到注意力焦點，而后對這一區(qū)域投入更多注意力，以獲取更多需要關注目標的細節(jié)信息，從而抑制其他無用信息.

深度學習中的注意力機制從本質上講和人類的選擇性視覺注意力機制類似，目的也是從眾多信息中選擇出對當前任務目標最關鍵的信息.

通過將注意力機制應用于相似性度量，可以更好地發(fā)現(xiàn)節(jié)點間的關聯(lián)以及網絡中隱藏的知識，從而更好地應用于聚類、推薦系統(tǒng)等研究領域.課題具體研究步驟如下：

首先，進行節(jié)點級別的相似性度量，通過得到節(jié)點之間的距離分布并結合信息散度，從而得到相鄰2節(jié)點之間的相似性；然后，進行元路徑級別的相似性度量，通過結合注意力機制，得到對應節(jié)點下元路徑的重要性；最后，通過對節(jié)點與元路徑所獲得的相似性進行融合計算，提出一種全新的節(jié)點相似性度量算法.通過在DBLP，ACM和IMDB 3個真實網絡數(shù)據(jù)集上選取多條元路徑進行實驗，并且與傳統(tǒng)的PathSim，AvgSim等算法進行對比，以此來證明所提出的相似性度量算法的準確性.

本文算法框架圖如圖4所示.

圖4 本文算法框架圖

2.1 節(jié)點級別的相似性度量

復雜網絡中節(jié)點的距離分布[9]包含了詳細的拓撲信息，比如平均度、直徑和路徑長度等，刻畫了網絡中的局部結構差異.因此，通過考慮節(jié)點之間的距離分布信息，可以更準確地度量節(jié)點之間的相似性.

復雜網絡中每個節(jié)點之間的距離分布為Wi={wi(k)}，wi(k)的計算公式如式(2)所示.

(2)

式中：Ni(k)為距離初始節(jié)點的最短路徑長度為k的節(jié)點個數(shù)；n為實例網絡中節(jié)點的總個數(shù).以圖5為例，當中心節(jié)點為12，距離節(jié)點12的路徑長度k=0時，只有12本身1個節(jié)點，故Ni(k)=1；當路徑長度k=1時，距離節(jié)點12的路徑長度為1的節(jié)點有13和192個節(jié)點，故Ni(k)=2.T(G)代表了實例網絡中的最大路徑長度，以圖5為例，距離節(jié)點12的最大路徑長度T(G)=3.

圖5 節(jié)點距離分布拓撲圖

圖5展示了節(jié)點12與其他節(jié)點最短路徑的距離分布情況.上述實例網絡的直徑T(G)=3，根據(jù)實例網絡中的節(jié)點路徑距離長度，節(jié)點12依次可到達的節(jié)點個數(shù)為：N(i)={Ni(k)|0≤k≤T(G)},即：

N(12)={1,2,3,3} .

由此可以得到節(jié)點12的距離分布為：

即：

W12={0.11，0.22，0.33，0.33} .

復雜網絡中節(jié)點之間的距離分布包含了詳細地拓撲信息.所以，通過考慮節(jié)點之間的距離分布可以詳細地刻畫節(jié)點之間的結構性差異，從而更準確地度量節(jié)點之間的相似性.

信息論中，信息散度[10]又稱為KL-散度，通常是用來度量2個概率分布在統(tǒng)計上存在的差異.本文算法通過使用信息散度來計算2個節(jié)點之間距離分布的差異，2個節(jié)點之間的信息散度越小，則這2個節(jié)點之間的距離分布越相似，反之亦然.

信息散度的定義如式(3)所示.

(3)

因為信息散度之間是非對稱的，因此需要對任意兩個節(jié)點之間的信息散度進行轉化.

kij=SKL(Wi‖Wj)+SKL(Wj‖Wi) .

(4)

通過得到相鄰2節(jié)點之間的信息散度，從而定義出來同一網絡拓撲下不同節(jié)點之間的相似性矩陣M.

(5)

其中任意2個節(jié)點i，j之間的相似性可由式(6)得出：

(6)

式中：Kij為相鄰兩節(jié)點i，j之間的信息散度；Kmax為同一網絡拓補下相鄰2節(jié)點間最大的信息散度.由公式(6)即可求得在節(jié)點級別下，相鄰2節(jié)點i，j之間的相似性.

2.2 元路徑級別的相似性度量

異構信息網絡中的節(jié)點序列構成了許多條元路徑，每一條元路徑既蘊含了不同的語義信息，也在語義表達中占據(jù)了不同的重要程度.因此，為了提高相似性度量算法的準確率跟計算效率，既要綜合考慮多樣化的節(jié)點屬性信息，又要考慮多條元路徑[11]的重要程度.

因為節(jié)點之間包含不同的屬性信息，所以不同類型的節(jié)點具有不同的特征空間.對于每種類型的節(jié)點，通過設計1種特定類型的轉換矩陣SΦi將不同類型節(jié)點的特征進行投影，從而可以投影到同一個特征空間.

(7)

式中：Pi和Pi'分別為節(jié)點i的初始特征與投影特征，Φi為節(jié)點i所在的元路徑.

然后，給定通過元路徑Φ所連接的節(jié)點對(i，j)，通過attnode執(zhí)行節(jié)點級注意力的深層神經網絡，可以得到節(jié)點j相對于節(jié)點i的重要性.

(8)

圖6 基于注意力機制的深層神經網絡

(9)

(10)

給定元路徑集合，將節(jié)點特征作為輸入，執(zhí)行節(jié)點級注意，便可得到一組語義特定的節(jié)點嵌入.接下來通過attsem執(zhí)行元路徑級別注意力的深層神經網絡，把從節(jié)點級注意力中學習到的節(jié)點特征作為輸入，得到每條元路徑(ZΦ0，ZΦ1…ZΦn)的重要性.

(ZΦ0，ZΦ1…ZΦn)=attsem(MΦ0，MΦ1…MΦn) .

(11)

在得到每條元路徑的重要性后，通過Softmax函數(shù)對其進行規(guī)范化得到相應元路徑Φi下的權重，表示為γΦi.使用Softmax函數(shù)對所有元路徑的上述重要性進行歸一化處理，具體過程如式(12)所示.

(12)

通過結合節(jié)點屬性，將節(jié)點級別的語義作為嵌入，最終得到元路徑級別的重要性.γΦi越高，元路徑Φi越重要，元路徑級別的相似性度量結束.

2.3 相似性度量

將得到的節(jié)點級別的相似性與對應節(jié)點下元路徑的權重進行加權融合，得到一種全新的相似度Kij來衡量節(jié)點之間的相似性，既考慮了節(jié)點之間的相似度，又考慮了對應節(jié)點下元路徑的重要性，加權融合過程如式(13)所示.

(13)

(14)

式中：n為通過節(jié)點i，j為下元路徑的數(shù)量；S為節(jié)點中實例占類型的比重，通過S可以將節(jié)點實例跟元路徑的權重進行結合.

3 仿真實驗與分析

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

本文所選取的數(shù)據(jù)集包括3個數(shù)據(jù)集：分別為ACM數(shù)據(jù)集，DBLP數(shù)據(jù)集以及IMDB數(shù)據(jù)集.以上數(shù)據(jù)集均為異構信息網絡中的經典數(shù)據(jù)集.

ACM期刊主要覆蓋計算機科學與軟件工程、計算機科學與信息系統(tǒng)等學科，涵蓋內容十分廣泛.通過提取發(fā)表在KDD，SIGMOD，SIGCOMM，MobiCOMM和VLDB上面的論文，然后將其分為3類：無線通信，數(shù)據(jù)挖掘和數(shù)據(jù)庫.所提取的ACM數(shù)據(jù)集包含3025篇論文(paper)、5835位作者(author)與56門學科(subject)，使用元路徑PAP，PSP進行實驗.

DBLP數(shù)據(jù)集包含了計算機中的4大研究領域，分別是數(shù)據(jù)庫、數(shù)據(jù)挖掘、機器學習和信息檢索，本文通過提取DBLP中的20個會議，14328篇論文，4057個作者和8789個關鍵字來進行仿真實驗.實驗中所選取的元路徑分為3條，分別是APA，APCPA和APTPA 3條元路徑.

IMDB(互聯(lián)網電影資料庫Internet Movie Database)是一個關于電影演員、電影、電視節(jié)目、電視明星和電影制作的在線數(shù)據(jù)庫.

通過提取IMDB的1個子集，它包含了4780部電影(movie)，5841個演員(actor)和2269個導演(director).電影按類型分為3種(動作類、喜劇類和戲劇類).電影的特點對應于一一包含的元素，這些詞代表了各種情節(jié).通過使用元路徑集合MAM，MDM來進行實驗.

為評價算法的有效性、準確性，仿真實驗分別采用標準相似性算法衡量指標AUC， Precision和F1指標來驗證算法的準確性.

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

(15)

式中：n為總共比較的次數(shù)；n′為隨機從測試集中取出的邊的分數(shù)值大于不存在的邊的分數(shù)的次數(shù)；n″為2分數(shù)值相等的次數(shù).

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

(16)

F1指標，是統(tǒng)計學中用來衡量二分類模型精確度的一種指標.它同時兼顧了分類模型的精確率和召回率.F1指標可以看作是模型精確率和召回率的一種調和平均值，它的最大值是1，最小值是0，定義如下所示：

(17)

AUC與F1指標綜合考慮了所提出模型的準確率，從整體上衡量了算法的準確性；Precision從局部命中率方面，衡量了算法的準確性；在AUC跟F1指標相近的情況下，Precision值越大表明結果越準確.

3.2 仿真實驗與結果分析

3.2.1數(shù)據(jù)集預處理

選擇與2種經典的相似性度量算法來進行對比.分別是PathSim算法和AvgSim算法.PathSim算法在單條元路徑上通過矩陣相乘度量相同類型間節(jié)點的相似性，采用對稱元路徑來展開對比；AvgSim算法通過雙向隨機游走，度量不同類型節(jié)點之間的相似性.

通過對比以上2個經典算法，采用DBLP，ACM和IMDB 3種經典異構信息網絡數(shù)據(jù)集進行實驗，使用AUC，Precision和F13種相似性指標進行對比，充分證明了本文算法的有效性，可以應用于大規(guī)模異構信息網絡下節(jié)點之間的相似性度量，且效果明顯優(yōu)于傳統(tǒng)算法.

通過對3個經典異構信息網絡數(shù)據(jù)集進行預處理跟模型訓練，數(shù)據(jù)集如表1所示.

表1 不同數(shù)據(jù)集下元路徑選取

3.2.2算法準確性驗證

通過與傳統(tǒng)的PathSim和AvgSim算法進行對比，采用AUC，precision和F1指標進行衡量，實驗數(shù)據(jù)如表2所示.

表2 ACM數(shù)據(jù)集下不同相似性度量算法的比較

在相似性度量結果上，通過對比PathSim算法和AvgSim算法，在ACM數(shù)據(jù)集下，所選取的元路徑為PAP，實驗結果顯示.AUC指標較傳統(tǒng)算法分別提升了4.39%和5.37%，F(xiàn)1指標分別提升了4.23%和4.84%，precision指標較AvgSim算法降低了1.32%，但是對比PathSim算法提升了3.27%.

表3 DBLP數(shù)據(jù)集下不同相似性度量算法的比較

在DBLP數(shù)據(jù)集下，通過對比PathSim算法和AvgSim算法，3種指標均有明顯提升.通過實驗對比發(fā)現(xiàn)，AUC指標分別提升了6.09%和2.72%，F(xiàn)1指標分別提升了4.23%和3.57%，Precision指標分別提升了0.17%和2.76%.

通過對比多條元路徑進行實驗，發(fā)現(xiàn)本文算法適用于任意類型節(jié)點之間的相似性度量，并且綜合考慮了節(jié)點屬性與元路徑下的重要性，有效地融合了注意力機制.通過多次對比實驗結果，發(fā)現(xiàn)所提算法普適性好，準確率相比較于其他傳統(tǒng)的相似性度量算法都有穩(wěn)定的提升，因此，所提算法對異構信息網絡中節(jié)點之間的相似性度量是可行的、有效的，且準確性較好.

4 總結

異構信息網絡能夠更加全面地反映真實網絡中節(jié)點之間的類型與關聯(lián)，本文通過綜合考慮節(jié)點屬性與元路徑權重，并將二者進行加權融合，提出一種綜合考慮節(jié)點與元路徑重要性的節(jié)點相似性度量算法，通過在3個真實網絡數(shù)據(jù)集上進行驗證，證明了所提算法的有效性.所提算法充分考慮了元路徑以及節(jié)點類型，擴展了算法的普適性，提高了節(jié)點相似性度量算法的準確性.實驗結果表明，算法可以有效提高算法的準確率且普適性更廣.后期可以結合多種聚類算法，如K-means聚類算法，標簽傳播算法等進行聚類，使該算法更好地應用于推薦系統(tǒng)或者社區(qū)發(fā)現(xiàn)等研究領域.