張雪婷，程 華，房一泉

華東理工大學 信息科學與工程學院，上海200237

鏈接預測[1]作為社會網(wǎng)絡(luò)分析的核心任務(wù)之一，通過網(wǎng)絡(luò)節(jié)點及網(wǎng)絡(luò)拓撲等信息預測網(wǎng)絡(luò)中尚未連接的兩個節(jié)點間存在鏈接的可能性。傳統(tǒng)的鏈接預測面向同構(gòu)社會網(wǎng)絡(luò)，即只包含一種類型的節(jié)點和連接。大多數(shù)現(xiàn)實網(wǎng)絡(luò)，如學術(shù)網(wǎng)絡(luò)[2]、患者網(wǎng)絡(luò)[3]和生物信息網(wǎng)絡(luò)[4]都是異構(gòu)社會網(wǎng)絡(luò)，包含多種類型的對象和關(guān)系。異構(gòu)社會網(wǎng)絡(luò)的數(shù)據(jù)挖掘已成為新的問題和挑戰(zhàn)，是近幾年的研究熱點。

Str?ele 等[5]提出了基于節(jié)點度、共同鄰居以及Katz系數(shù)三個指標的異構(gòu)社會網(wǎng)絡(luò)鏈接預測算法，用于合作網(wǎng)絡(luò)中隱含關(guān)系的預測。Dong 等[6]提出Metapath2vec算法，基于元路徑隨機游走確定節(jié)點表示，完成節(jié)點分類、鏈接預測等任務(wù)。Lu等[7]提出Rhine算法，在文獻[6]基礎(chǔ)上引入隸屬關(guān)系（ARS）和交互關(guān)系（IRS），捕捉異構(gòu)網(wǎng)絡(luò)的隱含信息，提高鏈接預測的準確度。

本文在用Metapath2vec 算法獲得基于元路徑節(jié)點表示的基礎(chǔ)上，用TF-IDF算法賦予論文節(jié)點語義屬性，提出異構(gòu)節(jié)點的復合表示方法。在路徑表示上，提出將元路徑上的異構(gòu)節(jié)點按類別重構(gòu)多條單類型節(jié)點路徑的方法，構(gòu)建基于節(jié)點類型的元路徑表示，并將路徑信息融合得到路徑的網(wǎng)絡(luò)表示。卷積神經(jīng)網(wǎng)絡(luò)有利于挖掘鏈接序列節(jié)點間的隱含拓撲關(guān)系[8]，通過多次卷積實現(xiàn)異構(gòu)社會網(wǎng)絡(luò)節(jié)點間的鏈接預測。實驗表明，本文方法比其他方法在預測合著關(guān)系上有更高的準確率，預測模型也有更強的穩(wěn)定性。

1 問題描述

定義1（異構(gòu)社會網(wǎng)絡(luò)（Heterogeneous Social Network））表示為G=(V,E)，其中V 表示網(wǎng)絡(luò)中所有的節(jié)點集合，E 表示節(jié)點關(guān)系的連接集合。有α:V →O 表示節(jié)點類型的映射函數(shù)，β:E →R 表示連接類型的映射函數(shù)。任意節(jié)點v ∈V 屬于某一節(jié)點類型α(v)∈O，任意連接β(v)∈R 屬于某一關(guān)系類型e ∈E。

在異構(gòu)學術(shù)網(wǎng)絡(luò)中，包含3 種類型節(jié)點：論文節(jié)點(P)、作者節(jié)點(A)、會議節(jié)點(C)，如圖1。常預測的關(guān)系有合著關(guān)系(A-A)、投錄關(guān)系(P-C)、論文引用關(guān)系(P-P)等，其中合著關(guān)系、論文引用關(guān)系為隱性關(guān)系。研究合著關(guān)系可以幫助學者更好地了解潛在的科研合作關(guān)系；也可以幫助追蹤分析其他科研人員的研究方向，更高效地分享學術(shù)資源、交流科研觀點。

圖1 異構(gòu)學術(shù)網(wǎng)絡(luò)

定義2（網(wǎng)絡(luò)模式（Network Schema））是異構(gòu)社會網(wǎng)絡(luò)G 的元模型，表示為TG=(O,R)，其中O 表示節(jié)點集合，R 表示關(guān)系集合。

異構(gòu)學術(shù)網(wǎng)絡(luò)的網(wǎng)絡(luò)模式如圖2，O={P,A,C},R={P-A,P-C}。

圖2 異構(gòu)學術(shù)網(wǎng)絡(luò)的網(wǎng)絡(luò)模式

定義3（元路徑（meta-path）[9]）定義在網(wǎng)絡(luò)模式TG上，表示連接兩個節(jié)點且包含節(jié)點邊緣類型關(guān)系的序列。元路徑可形式化表示LR：

其中，N1表示元路徑的起始節(jié)點，Np表示元路徑的終點節(jié)點，Ri表示相鄰節(jié)點Ni與Ni+1間的關(guān)系。節(jié)點N1和節(jié)點Np之間的組合關(guān)系記為：R=R1°R2°…°Rp-1，其中°是關(guān)系的組合運算。

元路徑作為異構(gòu)社會網(wǎng)絡(luò)中重要且獨有的概念，可以表示節(jié)點間關(guān)系和路徑的語義信息。本文預測元路徑下作者間的合著關(guān)系，A-A 間的元路徑可以表示為：

其中n1,n2∈[0,1]，n?∈N。

圖3（a）為“作者-論文-作者-論文-作者”(APAPA)元路徑，表示從給定作者開始，通過其論文的合著作者，找到該合著作者的其他合著論文作者；圖3（b）為“作者-論文-會議-論文-作者”(APCPA)元路徑，表示從給定作者開始，通過該作者投稿過論文的會議，找到該會議的其他論文作者。兩個待預測節(jié)點間不同的元路徑反應(yīng)了不同的路徑結(jié)構(gòu)及語義信息，得到的預測結(jié)果也應(yīng)不同。

圖3 元路徑示例

2 異構(gòu)節(jié)點的向量化表示學習

基于網(wǎng)絡(luò)表示學習[10]，可將網(wǎng)絡(luò)中的節(jié)點表示為低維稠密的空間向量，利用深度學習等方法可實現(xiàn)節(jié)點分類、鏈接預測以及網(wǎng)絡(luò)重構(gòu)等任務(wù)。常見的網(wǎng)絡(luò)表示算法包括基于隨機游走的Metapath2vec 算法[6]、Line 算法[11]及Node2vec 算法[12]；基于深度學習的GCN 算法[13]、SDNE算法[14]；基于矩陣分解的GF算法[15]。面向異構(gòu)社會網(wǎng)絡(luò)，本文綜合考慮元路徑和節(jié)點屬性兩個因素，實現(xiàn)節(jié)點的向量化表示。

2.1 基于元路徑的向量化表示

Metapath2vec 算法解決了異構(gòu)社會網(wǎng)絡(luò)中基于元路徑的向量化表示?；诮o定元路徑指導隨機游走的節(jié)點跳轉(zhuǎn)，保存元路徑鄰居節(jié)點信息，通過計算節(jié)點與鄰居節(jié)點在給定元路徑上的條件概率來學習節(jié)點的唯一嵌入表示。在給定元路徑LR中，第i 步的轉(zhuǎn)換概率為：

利用異構(gòu)的skip-gram模型生成能夠捕捉語義信息和不同節(jié)點類型的表示，模擬路徑中節(jié)點之間的結(jié)構(gòu)相關(guān)性。即在同構(gòu)skip-gram 模型的基礎(chǔ)上，添加了對不同節(jié)點類型的疊加。對于給定節(jié)點v，最大化其異構(gòu)上下文鄰居節(jié)點的概率：

Nt(v)表示節(jié)點類型為t 的鄰居節(jié)點ct所構(gòu)成的集合，P(ct|v;?)通常被定義為softmax函數(shù)，有：

其中，Xv表示節(jié)點v 的特征表示。

2.2 基于節(jié)點語義的向量化表示

對于學術(shù)網(wǎng)絡(luò)中的論文節(jié)點，其論文名可以表征論文內(nèi)容，論文節(jié)點包含語義特征。本文引入TF-IDF 算法[16]，計算論文節(jié)點的語義信息。TF-IDF算法描述了詞在文本中的重要性，根據(jù)字詞在文本中出現(xiàn)的次數(shù)和在整個語料中出現(xiàn)的頻率來計算詞在整個語料中的重要程度。詞頻TF 統(tǒng)計文本中詞的出現(xiàn)頻率，是一個特定條件下詞項概率分布的交叉熵。逆文本頻率IDF 反映了詞在所有文本中出現(xiàn)的頻率：

N 代表語料庫中文本的總數(shù)，N(x)代表語料庫中包含詞x 的文本總數(shù)，有：

在論文節(jié)點中，TF-IDF 算法用出現(xiàn)詞語的頻次來突出論文主題，用出現(xiàn)詞語的逆文檔頻率來突出論文標題的獨特性，可以有效地提取論文標題文本的語義信息。通過TfidfVectorizer把原始的論文標題集合轉(zhuǎn)化為TF-IDF 的特征矩陣，通過計算每個論文節(jié)點的TF-IDF值以完成語義表示。

2.3 節(jié)點的復合向量化表示

異構(gòu)社會網(wǎng)絡(luò)中的節(jié)點，均可以采用2.1節(jié)和2.2節(jié)中的兩種方法分別進行向量化表示，包含元路徑信息的向量表示為Mx，包含節(jié)點語義屬性的向量表示為TFx。

對于論文節(jié)點，其語義信息明顯，可以綜合元路徑信息和語義屬性，構(gòu)建復合的向量表示為TMx。本文通過全連接層對TFx向量降維處理，降低了預測模型的時間及空間復雜度，還避免了向量維數(shù)較大帶來的信息不對等：

將處理后的語義向量和結(jié)構(gòu)向量拼接，即可實現(xiàn)節(jié)點的復合向量化表示。

3 合著關(guān)系的鏈接預測

卷積神經(jīng)網(wǎng)絡(luò)在圖像、文本分類等方面都取得了很好的效果，Li 等[17]提出了一種級聯(lián)的卷積神經(jīng)網(wǎng)絡(luò)，利用多次CNN 挖掘復雜網(wǎng)絡(luò)的深度信息，提高預測準確度。在網(wǎng)絡(luò)表示中可用CNN提取多個同類型節(jié)點的聯(lián)合特征，而在關(guān)系預測中可用CNN 構(gòu)建分類模型以完成鏈接預測。本文分別基于元路徑序列和節(jié)點類型的網(wǎng)絡(luò)表示，構(gòu)建對應(yīng)的鏈接預測模型。

3.1 基于元路徑序列的鏈接預測模型

異構(gòu)社會網(wǎng)絡(luò)可以表示為不同元路徑序列的組合，且元路徑的長度可能不同。元路徑長度增長，網(wǎng)絡(luò)基于元路徑游走的時間呈指數(shù)倍增加，而鏈接預測的準確率卻隨路徑長度的增長而降低[18]?？紤]到學術(shù)網(wǎng)絡(luò)為密集網(wǎng)絡(luò)，路徑越長得到的路徑越多，影響計算效率及準確率，本文選用合著關(guān)系(A-A)間步長不大于4的元路徑，包括APA、APAPA、APCPA。元路徑APA 被視為本研究的真值路徑，故本文僅研究兩類元路徑APAPA 和APCPA，其序列提取過程如圖4。

圖4 從異構(gòu)社會網(wǎng)絡(luò)中提取元路徑

在元路徑表示中，分別對作者節(jié)點、論文節(jié)點、會議節(jié)點取向量化表示MA、TMP、MC，按元路徑序列順序拼接成元路徑表示矩陣，如圖5（a）。圖5為基于元路徑APCPA 下的鏈接預測模型，向量化后的矩陣表示記為：RAPCPA+TMP。通過CNN的多次卷積運算提取元路徑序列相鄰節(jié)點間的隱含結(jié)構(gòu)特征，實現(xiàn)鏈接預測。

該模型的鏈接預測部分（圖5（b））構(gòu)建多層卷積神經(jīng)網(wǎng)絡(luò)。每經(jīng)過一次卷積層都會經(jīng)過一次最大池化層，卷積神經(jīng)網(wǎng)絡(luò)輸出的特征值在長和寬方向上都會減小為原來的二分之一，感受野擴大為原來的二倍。最后經(jīng)過全連接層和softmax 分類器層，實現(xiàn)合著關(guān)系的鏈接預測。模型選擇ReLu 函數(shù)作為神經(jīng)元的激勵函數(shù)，減輕卷積神經(jīng)網(wǎng)絡(luò)在訓練過程中的過擬合現(xiàn)象。

該模型也適用于基于元路徑APAPA 及其他元路徑的合著關(guān)系預測問題，只需對圖5（a）部分不同類型的節(jié)點個數(shù)和序列順序做調(diào)整。此模型在兩條元路徑上的表示分別記為RAPAPA、RAPCPA。

3.2 基于節(jié)點類型的鏈接預測模型

圖5 基于元路徑序列的鏈接預測模型

學術(shù)網(wǎng)絡(luò)的元路徑包含多種類型節(jié)點，且同一條路徑中每種類型的節(jié)點可能有多個。因此可采用同類型節(jié)點重構(gòu)元路徑方法，即按元路徑順序提取同類型節(jié)點，將其重構(gòu)為多條同構(gòu)路徑，如圖6。

圖7表示為基于元路徑APAPA 的情況，對于作者節(jié)點和作者節(jié)點分別取向量化表示MA、TMP。提取同類型節(jié)點并重構(gòu)同構(gòu)路徑：僅含作者節(jié)點的路徑記為LA、僅含論文節(jié)點的路徑記為LP。用卷積神經(jīng)網(wǎng)絡(luò)分別提取每條同構(gòu)路徑相鄰節(jié)點間的隱含結(jié)構(gòu)信息，挖掘潛在語義屬性，再將提取到的信息賦予節(jié)點本身。將同一條元路徑衍生的多條同構(gòu)路徑信息融合，構(gòu)建基于節(jié)點類型的元路徑新表示：RA3P2+TMp。

鏈接預測部分和圖5（b）部分一致，采用卷積神經(jīng)網(wǎng)絡(luò)挖掘異構(gòu)學術(shù)網(wǎng)絡(luò)的深層次信息，以提高鏈接預測的準確性。本模型同樣也適用于基于元路徑APCPA 及其他元路徑的合著關(guān)系預測，只需對網(wǎng)絡(luò)表示部分節(jié)點個數(shù)和節(jié)點類型做調(diào)整?；诠?jié)點類型的鏈接預測模型不僅考慮了元路徑的序列信息，而且重構(gòu)了元路徑的表示，挖掘了相鄰同構(gòu)節(jié)點間的隱含信息。此模型在兩條元路徑上的表示分別記為RA3P2、RA2P2C。

4 實驗

4.1 數(shù)據(jù)集

本文選取典型的學術(shù)網(wǎng)絡(luò)：數(shù)據(jù)庫與信息系統(tǒng)（DBIS）數(shù)據(jù)集[19]進行實驗，包含60 694 名作者，72 902篇論文和4 580 個會議；還包括192 421 個論文作者關(guān)系，72 902個論文會議關(guān)系，屬于密集網(wǎng)絡(luò)。

圖6 基于節(jié)點類型的網(wǎng)絡(luò)序列化表示

圖7 基于節(jié)點類型的鏈接預測模型

4.2 評價指標

本文基于真正例（TP）、真負例（TN）、假正例（FP）、假負例（FN）等，獲得鏈接預測的準確率和召回率，并用AUC值和MAE值綜合評價模型優(yōu)劣。

（2）召回率（Recall），表示實際正樣本中預測為正樣本的比例：

（3）AUC 值（Area Under the Curve），ROC 曲線下方的面積，可以直觀評價分類器的好壞：

其中，n 為隨機實驗的次數(shù)，n′為正樣本比負樣本得分高的次數(shù)，n″為正樣本和負樣本得分一樣高的次數(shù)。若AUC值小于0.5，則表明算法比隨機選擇的準確率還低。

（4）MAE 值（Mean Absolute Error），表示觀測值與真實值絕對誤差的平均值，能更好地反映預測值誤差的實際情況：

4.3 實驗及結(jié)果分析

針對論文節(jié)點三種向量化方法：MP、TFP、TMP，路徑長度為4 的兩條元路徑：APAPA、APCPA，鏈接預測的兩種網(wǎng)絡(luò)構(gòu)建模型：RAPAPA或RAPCPA方法，或方法分別進行實驗。研究向量化表示、元路徑選取、預測模型構(gòu)建對預測結(jié)果的影響。

4.3.1 節(jié)點向量化表示對預測結(jié)果的影響

采用RAPAPA方法對論文節(jié)點的不同向量化表示方法進行實驗，實驗結(jié)果見表1。

表1 論文節(jié)點的不同向量化表示在RAPAPA 下的預測結(jié)果

實驗3 的AUC、Acc 和Recall 值均高于實驗2 和實驗1的各項指標。說明對比其元路徑信息MP，語義屬性TFP有更重要的作用，結(jié)合了元路徑信息和節(jié)點屬性的復合節(jié)點表示TMP更有助于社會網(wǎng)絡(luò)的挖掘，這是同構(gòu)社會網(wǎng)絡(luò)不具備的特點。實驗3的MAE值低于實驗2 和實驗1，說明了采用復合向量化表示的模型穩(wěn)定性更好。

3.將傳統(tǒng)投入產(chǎn)出表中所涉及的42個細化部門合并為六大部門：農(nóng)業(yè)、工業(yè)、建筑業(yè)、商業(yè)餐飲業(yè)、貨運郵電業(yè)、非物質(zhì)生產(chǎn)部門；

4.3.2 重構(gòu)元路徑對預測結(jié)果的影響

表2 論文節(jié)點的不同向量化表示在下的預測結(jié)果

表2 論文節(jié)點的不同向量化表示在下的預測結(jié)果

實驗序號456實驗方法RA3P2+Mp RA3P2+TFp RA3P2+TMp AUC 0.987 0.989 0.995 Acc 0.952 0.958 0.974 Recall 0.948 0.949 0.966 MAE 0.048 0.042 0.026

對比實驗1、4，實驗2、5，實驗3、6，可以得到在論文節(jié)點向量化表示方法一致的情況下，方法均比RAPAPA方法有更好的實驗結(jié)果。說明基于元路徑序列順序提取同類型節(jié)點重構(gòu)路徑的方法，可以更好地提取元路徑上的隱藏信息，是因為挖掘相鄰的同類型節(jié)點具有一定的物理意義。方法可以認為得到了待預測節(jié)點間具有不同語義的兩條路徑，且用CNN 也能更好地提取路徑上的相關(guān)性。故元路徑上同類型節(jié)點的隱含鄰居信息可以幫助網(wǎng)絡(luò)重構(gòu)，有效地提高異構(gòu)社會網(wǎng)絡(luò)中鏈接預測的精度。

4.3.3 不同元路徑對預測結(jié)果的影響

兩個節(jié)點之間不同的元路徑具有不同的結(jié)構(gòu)和語義信息，APAPA 元路徑側(cè)重強調(diào)存在間接合著關(guān)系的兩作者之間的合著關(guān)系，而APCPA 元路徑則強調(diào)在同一會議上發(fā)表過論文的兩作者之間的合著關(guān)系。針對元路徑APCPA，實驗見表3、表4。

表3 論文節(jié)點的不同向量化表示在RAPCPA 下的預測結(jié)果

表4 論文節(jié)點的不同向量化表示在 下的預測結(jié)果

表4 論文節(jié)點的不同向量化表示在 下的預測結(jié)果

實驗序號10 11 12實驗方法RA2P2C+Mp RA2P2C+TMp RA2P2C+TFp AUC 0.991 0.993 0.996 Acc 0.970 0.971 0.975 Recall 0.966 0.967 0.976 MAE 0.030 0.029 0.025

實驗7～12依次和實驗1～6對比，均有略優(yōu)的預測結(jié)果，說明了不同元路徑下的預測結(jié)果會略有不同。其間包含的節(jié)點類型越多，可以更多維地描述待預測節(jié)點，提高最終的預測結(jié)果。

4.3.4 與其他算法對比

文獻[6]Metapath2vec 算法為僅考慮異構(gòu)網(wǎng)絡(luò)中元路徑的情況，即本文的實驗1；文獻[7]Rhine 算法是在Metapath2vec算法的基礎(chǔ)上引入兩種不同的關(guān)系：ARS和IRS，ARS 表示元路徑的端點類型不同，意味著兩端節(jié)點的從屬關(guān)系。IRS表示元路徑的端點類型相同，描述對等結(jié)構(gòu)，即兩端節(jié)點的交互關(guān)系，基于元路徑APAPA 的實驗結(jié)果見表5。

表5 與其他算法的預測結(jié)果比較

本文方法在四個指標上均獲得了更好的效果，與實驗1 相比，本文方法增加語義屬性，說明語義屬性可以輔助節(jié)點的向量化表示；實驗13 考慮的從屬關(guān)系及交互關(guān)系只分析元路徑端點類型，本文方法綜合考慮整條元路徑的節(jié)點類型，提取同類型節(jié)點的隱含信息、拼接不同類型的節(jié)點表示；將捕捉網(wǎng)絡(luò)的局部信息豐富至全局網(wǎng)絡(luò)拓撲，顯然會有更好的預測效果。實驗14 為僅選用一層卷積的情況，其Acc值和MAE值略高于實驗6，而Recall 值值略低于實驗6，故本文暫不討論卷積層數(shù)對實驗結(jié)果的影響。

5 結(jié)語

本文在DBIS數(shù)據(jù)集上對異構(gòu)學術(shù)網(wǎng)絡(luò)中的合著關(guān)系進行研究，預測現(xiàn)有研究者未來產(chǎn)生合著關(guān)系的可能。在異構(gòu)網(wǎng)絡(luò)節(jié)點的向量化表示中，不僅考慮元路徑信息還充分挖掘部分節(jié)點的語義屬性，實驗表明增加語義屬性的復合向量化表示可以更好地描述異構(gòu)節(jié)點；在其路徑結(jié)構(gòu)表示上，提取元路徑包含的同類型節(jié)點，挖掘相鄰同類型節(jié)點間的隱含信息，可以更好地表征網(wǎng)絡(luò)結(jié)構(gòu)，提高最終的預測結(jié)果。

在未來工作中，試圖將本文提出的模型應(yīng)用到更多類型的異構(gòu)社會網(wǎng)絡(luò)中，探索本模型的普適性。此外，還將研究更多高效的鏈接預測模型。