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

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

0 概述

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

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

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

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

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

1 相關(guān)概念

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

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

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

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

2 算法實現(xiàn)

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

2.1 基礎模型

2.1.1 節(jié)點文本屬性信息表示學習

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

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

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

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

(1)

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

(2)

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

(3)

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

2.1.2 節(jié)點網(wǎng)絡結(jié)構(gòu)信息表示學習

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

圖2 網(wǎng)絡結(jié)構(gòu)信息表示學習模型

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

(4)

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

(5)

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

(6)

通過模型訓練后,US將作為最后所有節(jié)點的網(wǎng)絡結(jié)構(gòu)信息表示向量矩陣輸出。

2.2 融合表示學習模型及其算法優(yōu)化

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

圖3 2種節(jié)點文本屬性的融合方案

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

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

(7)

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

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

(8)

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

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

(9)

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

(10)

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

(11)

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

(12)

(13)

u∈{v}∪NEG(v)

(14)

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

(15)

u∈{w}∪NEG(w)

(16)

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

融合算法偽代碼如下:

算法1融合節(jié)點文本屬性信息的網(wǎng)絡表示學習算法

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

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

訓練數(shù)據(jù)集采樣步驟

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

2.對于網(wǎng)絡結(jié)構(gòu)信息,給定參數(shù)(l,b,r′,k),首先通過隨機游走產(chǎn)生節(jié)點序列集合,再以采樣窗口大小b采樣節(jié)點序列,構(gòu)成網(wǎng)絡結(jié)構(gòu)信息訓練集{(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//表示向量更新(詞向量及節(jié)

//點融合表示向量)

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//表示向量更新(節(jié)點融合表

//示向量)

27.end

28.end

29.end

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

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

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

3 實驗驗證與分析

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

3.1 實驗數(shù)據(jù)集

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

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

3.2 對比算法

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

下面簡要介紹對比算法:

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

2)DeepWalk算法:僅利用網(wǎng)絡結(jié)構(gòu)信息進行表示學習。

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

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

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

3.3 評測任務及其指標

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

(17)

(18)

(19)

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

圖5 實驗流程

3.4 實驗結(jié)果分析

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

圖6 DBLP數(shù)據(jù)集上的分類結(jié)果

圖7 CiteSeer-M10數(shù)據(jù)集上的分類結(jié)果

下面從兩方面分析實驗結(jié)果:

1)融合算法優(yōu)勢明顯。Doc2Vec算法和DeepWalk算法分別挖掘了節(jié)點文本屬性信息和結(jié)構(gòu)信息,但效果都較為普通?；诤唵纹唇拥腄W+D2V算法性能進一步提升,但是相比于融合模型仍然有提升空間。在30%的訓練率情況下,在DBLP網(wǎng)絡中,本文算法的分類宏F值比DW+D2V算法提高了4.3%,比融合算法TADW提高了2.2%;在CiteSeer-M10網(wǎng)絡中,本文算法的分類宏F值比DW+D2V算法提高了11%,比融合算法TADW提高了3.8%。

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

3.5 算法參數(shù)敏感性分析

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

圖8 超參數(shù)對算法分類性能指標宏F值的影響結(jié)果

4 結(jié)束語

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