一種融合節點文本屬性信息的網絡表示學習算法

劉正銘,馬 宏,劉樹新,楊奕卓,李 星

(國家數字交換系統工程技術研究中心,鄭州 450002)

0 概述

近年來,隨著以智能終端和社交媒體為代表的各種信息渠道的出現,大數據分析技術越來越受到人們的重視[1]。社交網絡、科學引文網絡等復雜網絡的規模不斷擴大,網絡數據類型復雜多樣。現實網絡數據的高維性、稀疏性和異質性等特點,對現有網絡分析技術帶來嚴重挑戰,這使得對于網絡數據的表示學習研究具有重要意義。

網絡表示學習旨在將每個網絡節點映射為一個低維空間的稠密向量,使得相似的網絡節點在低維空間距離較近。網絡表示學習通過對網絡數據形式進行變換,一方面使其包含的數據信息能夠更加容易提取和分析,即由人為的特征工程轉化為機器的自動特征提取,另一方面有效緩解了網絡數據表示的高維性、稀疏性等問題。

傳統的網絡表示學習模型主要是基于特定網絡關系矩陣降維得到節點的向量表示[2-5],其復雜度通常是網絡節點數量的二次方,同時難以融合網絡節點文本屬性等異質信息進行表示學習。近年來,大量研究者開始研究基于深度學習的網絡表示學習方法[6-7]。文獻[8]提出了DeepWalk算法,通過隨機游走產生節點序列,并將節點序列看作特殊的“句子”作為Word2Vec算法[9]輸入,學習節點的向量表示。文獻[10]提出了LINE算法,對所有網絡節點間的一階相似性和二階相似性進行概率建模,通過最小化該概率分布和經驗分布的KL散度得到節點的向量表示。文獻[11]提出了Node2Vec算法,在DeepWalk算法基礎上,通過設定in、out超參數控制隨機游走策略,挖掘網絡結構的局部特性和全局特性。文獻[12]提出了一個LsNet2Vec模型,針對大規模網絡中的鏈路預測問題進行網絡節點的表示學習。然而,上述方法都只利用了網絡結構信息,忽略了網絡節點屬性信息。

現實的網絡數據還包括豐富的網絡節點屬性信息,如科學引文網絡中文獻題目和摘要等信息。現有融合節點文本屬性信息進行表示學習的算法主要有TADW算法[13],該算法將節點文本屬性信息表示矩陣嵌入矩陣分解過程中實現融合表示學習。然而該算法利用TF-IDF[14]方法編碼表示節點文本屬性信息,忽略了文本中詞的詞序信息,難以有效挖掘深層語義信息。

針對上述方法的不足,本文提出一種融合節點文本屬性信息的網絡表示學習算法。首先,基于DeepWalk思想,將網絡節點結構信息的表示學習問題轉化為詞的表示學習問題。其次,針對節點文本屬性信息的表示學習問題,利用神經網絡語言模型挖掘節點文本屬性的深層語義信息。最后,為實現兩方面信息的融合表示學習,提出基于參數共享機制的共耦神經網絡模型進行聯合訓練。

1 相關概念

為更好地描述所提模型及其具體算法,首先給出相關定義及符號表示。

定義1(文本屬性信息網絡) 用G=(V,E,C)表示文本屬性信息網絡,V={v1,v2,…,vN}表示節點集合,N=|V|表示網絡中的節點數量,E表示V中任意2個節點鏈接構成的集合E={eij|i,j=1,2,…,N},eij表示節點間的鏈接關系緊密程度,即鏈接權重,C={c1,c2,…,cN},ci表示與節點vi相關聯的節點文本屬性信息。

這里考慮網絡節點相似性主要通過網絡結構信息和網絡節點文本屬性信息進行刻畫。也就是說在網絡表示學習過程中,需要同時注意網絡節點結構信息相似性保留和文本屬性信息相似性保留,得到綜合兩方面信息的節點表示向量。

節點的表示向量φ(v)可以看作節點v的特征向量,可直接將其作為機器學習算法的輸入用于后續網絡分析任務,如節點分類、鏈路預測等。由于表示學習過程并不涉及具體網絡分析任務,因此算法所得的表示向量具有廣泛適用性。

2 算法實現

本節首先分別介紹刻畫節點文本屬性信息相似性和網絡結構信息相似性的基礎模型,然后基于這2種基礎模型給出融合訓練模型及其算法的優化求解過程,最后結合算法偽代碼進行算法復雜度分析。

2.1 基礎模型

2.1.1 節點文本屬性信息表示學習

近年來,基于CBOW[9]神經網絡語言模型的詞向量表示學習方法,通過窗口上下文預測中間詞,較好地保留了文本語句中的詞序信息。在此基礎上,文獻[15]提出了用于文本向量表示的Doc2Vec算法,在很多應用中取得了較好的結果。因此,將其作為本文融合算法的基礎模型之一。

如圖1所示,對于任意詞w,給定左右窗口大小為b的上下文詞集合context(w)={w-b:wb},v(w)表示一個從詞w到對應節點的映射函數,矩陣W中的每一行表示一個詞對應的表示向量,矩陣UW中的每一行表示一個節點對應的文本屬性信息的表示向量。

圖1 節點文本屬性信息表示學習模型

算法基本思想是在已知上下文context(w)和v(w)的情況下,預測到詞w的概率最大。其對應最大化目標函數如下:

(1)

其中,D對應于節點文本屬性信息中所有詞的集合。p(w|context(w),v(w))定義為如下Softmax函數:

(2)

其中,v(u)和v′(u)表示u的表示向量及其輔助向量,xw采用累加求和的形式計算如下:

(3)

通過模型訓練后,UW將作為最后所有節點的文本屬性信息表示向量矩陣輸出。

2.1.2 節點網絡結構信息表示學習

對于網絡結構信息表示學習問題,主要分為采樣和訓練2個階段。在采樣階段,使用文獻[8]提出的隨機游走策略捕捉網絡結構信息。從任意節點vi出發,隨機游走固定長度l得到隨機游走序列S={vi,vi+1,vi+2,…,vi+l}作為訓練集。在訓練階段,將隨機游走序列看作特殊的“句子”,作為CBOW模型[10]的輸入,學習節點向量表示。如圖2所示,對于任意節點v,假設給定左右窗口大小為b的上下文節點集合為context(v)={v-b:vb},矩陣US中的每一行表示一個節點對應的網絡結構信息的表示向量。

圖2 網絡結構信息表示學習模型

與第2.1.1節類似,在已知上下文context(v)的情況下,預測到節點v的概率最大,其對應最大化目標函數為:

(4)

其中,V是所有節點的集合。p(v|context(v))定義為如下Softmax函數:

(5)

這里xv采用累加求和的形式計算如下:

(6)

通過模型訓練后,US將作為最后所有節點的網絡結構信息表示向量矩陣輸出。

2.2 融合表示學習模型及其算法優化

為實現節點網絡結構信息和文本屬性信息的融合表示,最簡單的方法就是拼接。如圖3(a)所示,記通過文本屬性信息表示學習模型訓練得到的表示矩陣為UW,通過網絡結構信息表示學習模型訓練得到的表示矩陣為US,直接拼接得到最終的節點表示向量矩陣U+,即U+=UW⊕US,然而這種方法由于UW和US在訓練過程中相互獨立,屬于訓練后結合,缺少了兩方面信息在訓練過程中的相互補充與制約。因此,提出基于參數共享的交叉訓練機制實現融合表示學習,如圖3(b)所示。首先,使用融合表示向量矩陣U替換基礎模型中的UW和US,建立共耦神經網絡模型,如圖4所示。

圖3 2種節點文本屬性的融合方案

圖4 融合節點文本屬性信息的表示學習模型

左右兩部分的表示學習模型交替訓練,U由2個模型共享,即U在訓練過程中相互傳遞。最后,通過反復迭代,得到融合兩方面信息的節點向量表示,其對應的最大化目標函數為:

(7)

其直觀解釋是:一方面融合表示向量和上下文詞向量一起用于預測中間詞w,使得融合表示向量包含節點文本屬性信息;另一方面融合表示向量又參與節點網絡結構信息的表示學習訓練,通過節點網絡結構信息修正融合表示向量。在反復迭代過程中,實現兩方面信息的相互補充與制約。

采用隨機梯度上升方法進行迭代訓練,考慮到計算式(2)和式(5)時需要分別遍歷整個詞集合與節點集合,不適合在大規模網絡的實際應用,文獻[16]提出了基于負采樣(Negative Sampling,NEG)的優化策略用于降低計算復雜度,給出式(5)的近似表示如下:

(8)

其中,Lv(u)為0-1判決函數,當u=v時,Lv(u)=1,否則Lv(u)=0,σ(x)=1/(1+e-x)。NEG(v)表示正樣本(v,context(v))對應的負樣本集。從式(8)不難看出,負采樣的基本思想是最大化正樣本出現概率的同時最小化負樣本出現概率。

下面進一步推導表示向量的更新公式,將式(8)帶入式(4)中可得:

(9)

為求導方便,記式(9)兩次求和項如下:

(10)

首先考慮LS(v,u)關于v′(u)的梯度,推導如下:

(11)

同理,可求出LS(v,u)關于xv的梯度如下:

(12)

(13)

u∈{v}∪NEG(v)

(14)

對于節點文本屬性信息表示學習模型的計算方法類似,在此不再贅述,直接給出最后的更新公式。

(15)

u∈{w}∪NEG(w)

(16)

2.3 融合算法流程及其復雜度分析

融合算法偽代碼如下:

算法1融合節點文本屬性信息的網絡表示學習算法

輸入信息網絡G=(V,E,C),迭代次數r,表示向量維度d,采樣窗口左右大小b,隨機游走長度l,隨機游走次數r′,負采樣樣本數k

輸出節點融合表示向量矩陣U,每一行對應節點表示向量v(u),u∈V

訓練數據集采樣步驟

1.對于節點文本屬性信息,給定參數(b),以采樣窗口大小b采樣文本信息,構成文本屬性信息訓練集{(w,context(w),v(w),NEG(w))}。

2.對于網絡結構信息,給定參數(l,b,r′,k),首先通過隨機游走產生節點序列集合,再以采樣窗口大小b采樣節點序列,構成網絡結構信息訓練集{(v,context(v),NEG(v))}。

迭代訓練步驟如下:

3.for iter=1 to r

4.for w in D

5.random sample(w,context(w),v(w),NEG(w))

6.update=0

8.for u in {w}∪NEG(w)

10.update=update+delta·v′(u)

11.v′(u)=v′(u)+delta·xw//輔助向量更新

end

12.for u in {v(w)}∪context(w)

13.v(u)=v(u)+update//表示向量更新(詞向量及節

//點融合表示向量)

14.end

15.end

16.forvin V

17.random sample (v,context(v),NEG(v))

18.update=0

20.for u in {v}∪NEG(v)

22.update=update+delta·v′(u)

23.v′(u)=v′(u)+delta·xv//輔助向量更新

24.end

25.for u in context(v)

26.v(u)=v(u)+update//表示向量更新(節點融合表

//示向量)

27.end

28.end

29.end

下面結合算法偽代碼(算法1)分析算法流程并討論其復雜度問題。

其次,對于迭代訓練部分,一方面使用隨機梯度上升法(對應求極大值)作為優化更新策略,式(13)～式(16)給出了向量更新公式;另一方面基于參數共享策略進行交叉迭代訓練:步驟4～步驟15實現了節點文本屬性信息的表示學習,步驟16～步驟29實現了網絡結構信息的表示學習,由于節點融合表示向量在兩部分模型中相互傳遞,使得在訓練過程中受到兩方面信息的相互補充與制約。迭代過程中,對于給定的詞w,在負采樣策略下,計算次數從式(3)的|D|(語料庫大小)次減少到1+k次。

最后,分析算法的整體復雜度問題。在單次迭代過程中,對于給定詞w,在負采樣策略下,計算次數從式(3)的|D|(語料庫大小)次減少到1+k次。遍歷詞集合,計算次數為|D|·(1+k)次。同理,對于給定節點v,遍歷節點集,計算次數為|V|·(1+k)次。因此,迭代r次后,整體計算復雜度為ο(r·(|D|+|V|)·(1+k))。在實際應用場景中,由于r,k<<|D|,|V|,因此算法計算時間復雜度和網絡規模成線性比例關系,算法可擴展到大規模場景的實際應用。

3 實驗驗證與分析

為驗證本文提出算法的有效性,在2個公開數據集上與具有代表性的表示學習算法進行對比。

3.1 實驗數據集

DBLP數據集來源于AMiner網站公開數據集。本文抽取其中4個知名國際會議論文數據(CIKM,KDD,IJCAI,CVPR),將論文作為網絡節點,標題信息作為節點文本屬性信息,利用引用關系構建引文網絡,包含節點18 223個,連邊15 867條,4類節點標簽對應不同的會議論文集。

CiteSeer-M10數據集來源于CiteSeerX網站中抽取的數據集。本文將文獻[17]從該網站中抽取的包含10個方向論文引用關系的數據集作為實驗數據集。將論文作為網絡節點,標題信息作為節點文本屬性信息,利用引用關系構建引文網絡,包含節點10 310個,連邊77 218條,10類節點標簽對應不同方向的論文集。

3.2 對比算法

將對比算法分為3類:1)僅利用節點文本屬性信息;2)僅利用網絡結構信息;3)同時利用兩方面信息的融合算法。

下面簡要介紹對比算法:

1)Doc2Vec算法:僅利用節點文本屬性信息進行表示學習。

2)DeepWalk算法:僅利用網絡結構信息進行表示學習。

3)DW+D2V算法:將Doc2Vec算法和DeepWalk算法學習的表示向量進行拼接,使得到的節點表示向量既包含文本屬性信息又包含網絡結構信息。

4)TADW算法:通過矩陣分解的形式,直接利用節點文本屬性信息和網絡結構信息得到節點表示向量。

本文算法的主要參數設定為表示向量維度d=200,迭代次數r=10,其余參數設定為對應子結構的原始文獻給出的建議值:文獻[15]中的Doc2Vec算法設定文本屬性信息表示學習窗口大小為10;文獻[8]根據DeepWalk算法對隨機游走的討論,設定游走長度l=40,窗口大小為10,游走次數r′=80。為保持一致,各對比算法維度都設置為d=200。

3.3 評測任務及其指標

評測方法與文獻[11,13]類似,首先進行無監督的表示學習,然后將其用在多標簽分類任務中,比較不同算法的性能。基本思想是具有較好標簽預測能力的表示學習算法能夠更加準確地從原始網絡數據中提取節點特征向量表示。由于評測數據集是多分類問題,因此在評價指標選擇問題上,先在各混淆矩陣上分別計算準確率和召回率,記為(P1,R1),(P2,R2),…,(Pn,Rn),再計算平均值,得到宏準確率(Macro_P)、宏召回率(Macro_R)及相應的宏F值(Macro_F):

(17)

(18)

(19)

為方便進行算法比較,與文獻[11,13]一致,統一采用SVM線性分類器進行節點分類任務,排除不同分類器對節點分類性能造成影響的情況。為考察算法在不同監督信息量情況下的標簽預測性能,隨機取訓練集大小從10%～90%,剩余部分作為測試集,重復10次取結果平均值。實驗流程如圖5所示。

圖5 實驗流程

3.4 實驗結果分析

圖6和圖7分別記錄了在DBLP和CiteSeer-M10數據集上的不同訓練率下(10%～90%,間隔20%進行測試)的3種節點分類性能指標結果,即宏準確率、宏召回率和宏F值。實驗結果顯示,本文所提算法的節點分類性能高于比較算法。

圖6 DBLP數據集上的分類結果

圖7 CiteSeer-M10數據集上的分類結果

下面從兩方面分析實驗結果:

1)融合算法優勢明顯。Doc2Vec算法和DeepWalk算法分別挖掘了節點文本屬性信息和結構信息,但效果都較為普通。基于簡單拼接的DW+D2V算法性能進一步提升,但是相比于融合模型仍然有提升空間。在30%的訓練率情況下,在DBLP網絡中,本文算法的分類宏F值比DW+D2V算法提高了4.3%,比融合算法TADW提高了2.2%;在CiteSeer-M10網絡中,本文算法的分類宏F值比DW+D2V算法提高了11%,比融合算法TADW提高了3.8%。

2)神經網絡特征挖掘優勢明顯。和通過矩陣分解方式進行融合表示的TADW算法相比,基于共耦神經網絡的本文算法平均節點分類準確率在DBLP和CiteSeer-M10網絡中分別達到68%和71%,比TADW算法分別提高了3%和3.6%。作為本文算法子結構的Doc2Vec文本表示學習算法僅依賴節點文本屬性信息的情況下就達到較好的節點分類效果。如圖6(a)和圖7(a)所示,在30%訓練率下,在DBLP和CiteSeer-M10網絡上的節點分類準確率分別達到61.9%和47.9%。這一方面說明結合文本屬性信息的重要性,另一方面也說明了神經語言模型在挖掘文本語義信息方面的巨大優勢,這也是結合神經語言模型改進網絡表示學習算法的初衷。

3.5 算法參數敏感性分析

本文算法包含了表示向量維度d和融合算法迭代次數r這2個主要超參數,本節將通過實驗分析超參數的選擇對算法用于多標簽節點分類問題性能好壞的影響。通過改變參數取值,得到不同的節點表示向量。按照圖5的實驗流程,在30%訓練率的情況下,測試不同的節點表示向量對多標簽節點分類問題性能指標宏F值的影響,實驗結果如圖8所示。圖8(a)表示了改變表示向量維度d對算法分類預測性能的影響,d取值從50～300,每間隔50進行一次實驗。隨著表示向量維度的增加,分類預測宏F值逐漸增加,說明了較高維度能夠捕獲更多的網絡信息,形成更具區分性的網絡表示。然而同時也注意到,表示維度增加到200維以后,分類預測宏F值有所下降。這說明采用過多的表示向量維度衡量網絡節點相似性,減少了具有重要區分度特征的權重影響,反而導致性能損失。因此,200維的表示向量維度較為合適。圖8(b)是改變算法迭代次數r對算法分類預測性能的影響,將迭代次數變化范圍設置為2～12,間隔2次進行一次實驗。隨著迭代次數的增加,分類預測宏F值明顯提升,體現了交叉訓練過程中兩方面信息的相互補充。迭代次數超過10次以后,分類預測性能趨于穩定,說明融合模型能夠挖掘的網絡信息趨于穩定。因此,迭代次數超過10次后停止迭代更新。

圖8 超參數對算法分類性能指標宏F值的影響結果

4 結束語

本文基于神經語言模型提出了一個結合節點文本屬性信息的網絡表示學習算法,實現了節點文本屬性信息和網絡結構信息的融合表示學習。針對文本屬性信息和網絡結構信息等異質信息難以有效融合表示的問題,給出基于參數共享的共耦神經網絡模型用于融合訓練。在2個真實世界網絡數據集上的實驗結果表明,該算法有效實現了融合表示學習,在面向節點分類的評測任務中,算法性能有一定提升。算法復雜度與網絡規模大小成線性比例關系,能夠適用于大數據時代背景下的大規模復雜信息網絡的表示學習問題。然而,該算法僅考慮了節點文本屬性信息,下一步將針對實際網絡中存在的圖像信息、語音信息等其他異質信息對算法進行優化。