基于元路徑與節點屬性的合著關系預測

張雪婷，程 華，房一泉

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

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

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

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

1 問題描述

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

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

圖1 異構學術網絡

定義2（網絡模式（Network Schema））是異構社會網絡G 的元模型，表示為TG=(O,R)，其中O 表示節點集合，R 表示關系集合。

異構學術網絡的網絡模式如圖2，O={P,A,C},R={P-A,P-C}。

圖2 異構學術網絡的網絡模式

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

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

元路徑作為異構社會網絡中重要且獨有的概念，可以表示節點間關系和路徑的語義信息。本文預測元路徑下作者間的合著關系，A-A 間的元路徑可以表示為：

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

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

圖3 元路徑示例

2 異構節點的向量化表示學習

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

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

Metapath2vec 算法解決了異構社會網絡中基于元路徑的向量化表示。基于給定元路徑指導隨機游走的節點跳轉，保存元路徑鄰居節點信息，通過計算節點與鄰居節點在給定元路徑上的條件概率來學習節點的唯一嵌入表示。在給定元路徑LR中，第i 步的轉換概率為：

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

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

其中，Xv表示節點v 的特征表示。

2.2 基于節點語義的向量化表示

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

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

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

2.3 節點的復合向量化表示

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

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

將處理后的語義向量和結構向量拼接，即可實現節點的復合向量化表示。

3 合著關系的鏈接預測

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

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

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

圖4 從異構社會網絡中提取元路徑

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

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

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

3.2 基于節點類型的鏈接預測模型

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

學術網絡的元路徑包含多種類型節點，且同一條路徑中每種類型的節點可能有多個。因此可采用同類型節點重構元路徑方法，即按元路徑順序提取同類型節點，將其重構為多條同構路徑，如圖6。

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

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

4 實驗

4.1 數據集

本文選取典型的學術網絡：數據庫與信息系統（DBIS）數據集[19]進行實驗，包含60 694 名作者，72 902篇論文和4 580 個會議；還包括192 421 個論文作者關系，72 902個論文會議關系，屬于密集網絡。

圖6 基于節點類型的網絡序列化表示

圖7 基于節點類型的鏈接預測模型

4.2 評價指標

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

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

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

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

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

4.3 實驗及結果分析

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

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

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

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

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

3.將傳統投入產出表中所涉及的42個細化部門合并為六大部門：農業、工業、建筑業、商業餐飲業、貨運郵電業、非物質生產部門；

4.3.2 重構元路徑對預測結果的影響

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

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

實驗序號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，可以得到在論文節點向量化表示方法一致的情況下，方法均比RAPAPA方法有更好的實驗結果。說明基于元路徑序列順序提取同類型節點重構路徑的方法，可以更好地提取元路徑上的隱藏信息，是因為挖掘相鄰的同類型節點具有一定的物理意義。方法可以認為得到了待預測節點間具有不同語義的兩條路徑，且用CNN 也能更好地提取路徑上的相關性。故元路徑上同類型節點的隱含鄰居信息可以幫助網絡重構，有效地提高異構社會網絡中鏈接預測的精度。

4.3.3 不同元路徑對預測結果的影響

兩個節點之間不同的元路徑具有不同的結構和語義信息，APAPA 元路徑側重強調存在間接合著關系的兩作者之間的合著關系，而APCPA 元路徑則強調在同一會議上發表過論文的兩作者之間的合著關系。針對元路徑APCPA，實驗見表3、表4。

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

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

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

實驗序號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對比，均有略優的預測結果，說明了不同元路徑下的預測結果會略有不同。其間包含的節點類型越多，可以更多維地描述待預測節點，提高最終的預測結果。

4.3.4 與其他算法對比

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

表5 與其他算法的預測結果比較

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

5 結語

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

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