基于稀疏自編碼器的屬性網(wǎng)絡(luò)嵌入算法

張志敏,柴變芳,李文斌

(河北地質(zhì)大學(xué) 信息工程學(xué)院,石家莊 050031)

0 概述

隨著網(wǎng)絡(luò)信息技術(shù)的發(fā)展以及文獻(xiàn)著作數(shù)量的迅速增加,引文網(wǎng)絡(luò)已經(jīng)形成了一個(gè)超大規(guī)模的復(fù)雜網(wǎng)絡(luò)[1]系統(tǒng),然而此類網(wǎng)絡(luò)數(shù)據(jù)[2]的高維性、稀疏性和異質(zhì)性制約了相關(guān)研究的發(fā)展[3-5]。近年來,很多學(xué)者提出了針對(duì)網(wǎng)絡(luò)分析的網(wǎng)絡(luò)嵌入算法[6-7],其將網(wǎng)絡(luò)信息編碼為低維稠密的實(shí)數(shù)向量,并且得到的低維嵌入向量能夠保持原有網(wǎng)絡(luò)的屬性和結(jié)構(gòu)[8-9]。由于此類向量在使用前必須做進(jìn)一步的任務(wù)分析,如節(jié)點(diǎn)分類、聚類、鏈接預(yù)測(cè)等[10-11],因此如何從原始網(wǎng)絡(luò)中獲取有效的網(wǎng)絡(luò)嵌入向量非常重要。

目前已有多種獲取網(wǎng)絡(luò)嵌入向量的方法,根據(jù)使用信息的不同主要分為兩類:基于網(wǎng)絡(luò)結(jié)構(gòu)的嵌入方法,以及基于網(wǎng)絡(luò)結(jié)構(gòu)和屬性信息的嵌入方法。在基于網(wǎng)絡(luò)結(jié)構(gòu)的嵌入方法中:Deepwalk算法[12]從網(wǎng)絡(luò)結(jié)構(gòu)的隨機(jī)游走序列中得到節(jié)點(diǎn)的嵌入表示,其改進(jìn)算法Node2Vec算法[13]又考慮游走深度與游走廣度,進(jìn)一步提高了網(wǎng)絡(luò)表示學(xué)習(xí)的性能;LINE算法[14]用直接相連的兩個(gè)節(jié)點(diǎn)刻畫第一級(jí)相似度(即利用鄰接矩陣),用不直接連接的兩個(gè)節(jié)點(diǎn)刻畫第二級(jí)相似度(作為鄰接矩陣的補(bǔ)充)進(jìn)行概率建模,并通過最小化概率分布和經(jīng)驗(yàn)分布間的KL散度[15]得到網(wǎng)絡(luò)節(jié)點(diǎn)的嵌入表示。在基于網(wǎng)絡(luò)結(jié)構(gòu)和屬性信息的嵌入方法中:SNE模型[16]融合網(wǎng)絡(luò)結(jié)構(gòu)信息和節(jié)點(diǎn)屬性信息作為神經(jīng)網(wǎng)絡(luò)輸入,在輸出層以最大化節(jié)點(diǎn)鄰居出現(xiàn)概率為優(yōu)化目標(biāo),利用多層感知機(jī)制提取節(jié)點(diǎn)的低維表示;SDNE模型[17]使用深度自編碼器保持兩階鄰居之間的鄰近節(jié)點(diǎn)表示,再通過最小化相鄰節(jié)點(diǎn)間的歐氏距離來保持相鄰節(jié)點(diǎn)之間的鄰近性;DNGR模型[18]采用隨機(jī)沖浪策略捕捉圖形結(jié)構(gòu)信息,再進(jìn)一步將這些結(jié)構(gòu)信息轉(zhuǎn)換為PPMI矩陣,使用去噪自編碼器獲得節(jié)點(diǎn)的嵌入表示;WMCNE模型[19-20]將網(wǎng)絡(luò)拓?fù)浜驼Z義信息統(tǒng)一到圖形表示中,并使用局部空間結(jié)構(gòu)增強(qiáng)圖形表示,在此基礎(chǔ)上使用深層自編碼進(jìn)行網(wǎng)絡(luò)重建。在上述方法中,WMCNE模型性能較好,其對(duì)網(wǎng)絡(luò)拓?fù)浜驼Z義信息進(jìn)行圖形統(tǒng)一化表示,但該模型構(gòu)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)時(shí)利用了由鄰接矩陣轉(zhuǎn)換的模塊度矩陣,未考慮節(jié)點(diǎn)間間接鏈接信息。此外,其在結(jié)合模塊度矩陣和屬性信息時(shí)采用直接拼接方式,自編碼訓(xùn)練時(shí)維度過高并且參數(shù)過多制約了算法性能的提升。

本文提出一種深層挖掘網(wǎng)絡(luò)拓?fù)湫畔⒉⑷诤瞎?jié)點(diǎn)屬性信息的網(wǎng)絡(luò)嵌入算法SAANE。基于網(wǎng)絡(luò)鏈接提取二級(jí)鄰居和節(jié)點(diǎn)的共同鄰居比,并將其整合到同一圖形中,對(duì)節(jié)點(diǎn)屬性進(jìn)行相似度計(jì)算得到基于屬性相似度的網(wǎng)絡(luò),由此構(gòu)造屬性模塊度矩陣。在此基礎(chǔ)上,融合網(wǎng)絡(luò)拓?fù)湫畔⒑蛯傩孕畔⑦M(jìn)行稀疏自編碼,進(jìn)而獲得最終的網(wǎng)絡(luò)嵌入向量。

1 相關(guān)定義

為更好地描述SAANE算法,給出以下定義及其符號(hào)表示。

定義1(屬性網(wǎng)絡(luò)) 給定含有n個(gè)節(jié)點(diǎn)的無向網(wǎng)絡(luò)G=(V,E,C,N,R),其中:V={v1,v2,…,vn}是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合;E={eij}(i,j∈{1,2,…,n})是網(wǎng)絡(luò)中邊的集合;C={c1,c2,…,cn}是節(jié)點(diǎn)屬性集合;N表示前n(n≥2)階鄰居的集合,若vi與vj之間有邊,且vj與vk之間有邊,則vk稱為vi的二階鄰居;R={rij}表示前n(n≥2)階鄰居的共同鄰居比矩陣,節(jié)點(diǎn)vi的前k(k≥2)階鄰居集合為Ni,k,節(jié)點(diǎn)vj的前k(k≥2)階鄰居集合為Nj,k。rij表示為:

(1)

定義2(Node2Vec隨機(jī)序列) 根據(jù)Node2Vec算法設(shè)置參數(shù)p=2,q=0.5,采用深度優(yōu)先搜索策略生成隨機(jī)游走序列。以Washington數(shù)據(jù)集為例進(jìn)行說明。圖1(a)中第1列為當(dāng)前節(jié)點(diǎn)的序號(hào),第2列為當(dāng)前節(jié)點(diǎn)的一階鄰居,第3列為當(dāng)前節(jié)點(diǎn)二階鄰居……,利用該序列提取節(jié)點(diǎn)的二階鄰居集,如圖1(b)所示,然后基于節(jié)點(diǎn)的二階鄰居計(jì)算共同鄰居比,如圖1(c)所示。

圖1 Washington數(shù)據(jù)集的二級(jí)鄰居及共同鄰居比

2 SAANE算法

2.1 網(wǎng)絡(luò)特征累加對(duì)比

為測(cè)試網(wǎng)絡(luò)拓?fù)湫畔⑸疃韧诰虻挠行?本文在真實(shí)網(wǎng)絡(luò)中依次引入鄰接矩陣、二階鄰居、共同鄰居比、節(jié)點(diǎn)屬性模塊度,對(duì)得到的向量使用K-means方法進(jìn)行聚類,并選擇NMI作為衡量指標(biāo),對(duì)比結(jié)果如圖2所示。可以看出,針對(duì)5個(gè)真實(shí)網(wǎng)絡(luò)依次引入鄰接矩陣、二階鄰居、共同鄰居比和屬性模塊度矩陣,NMI值逐漸增加,說明引入信息的增加有助于進(jìn)一步挖掘網(wǎng)絡(luò)特征。

圖2 真實(shí)數(shù)據(jù)集上的網(wǎng)絡(luò)特征聚類結(jié)果

2.2 模型框架

SAANE模型框架如圖3所示,其中包含3個(gè)模塊:1)網(wǎng)絡(luò)特征提取模塊,由網(wǎng)絡(luò)拓?fù)涮崛《?jí)鄰居及共同鄰居比并進(jìn)行整合;2)屬性模塊度計(jì)算模塊,由節(jié)點(diǎn)屬性矩陣獲取屬性模塊度矩陣;3)深度稀疏自編碼器,加權(quán)融合處理后的拓?fù)湎蛄亢驼Z義模塊度進(jìn)行深度稀疏自編碼,同時(shí)引入局部增強(qiáng)約束和稀疏損失約束。

圖3 SAANE模型框架

2.2.1 網(wǎng)絡(luò)特征提取

M1=sign(A+N)

(2)

為確保由鏈接獲取的信息與共同鄰居比同等重要,采用2-范數(shù)對(duì)M1做標(biāo)準(zhǔn)化處理,定義如下:

(3)

從而得到:

M2=n(M1)

(4)

對(duì)標(biāo)準(zhǔn)化后的特征向量與共同鄰居比求和,即得到由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)提取出的網(wǎng)絡(luò)特征M:

M=M3+R

(5)

2.2.2 語義屬性模塊度

對(duì)于節(jié)點(diǎn)上的文本屬性,計(jì)算兩個(gè)節(jié)點(diǎn)間的相似性得到相似圖S=[sij]=[cos(wi,wj)],其中wi是節(jié)點(diǎn)vi的內(nèi)容向量。由于模塊度能夠轉(zhuǎn)好地衡量網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)強(qiáng)度,因此用模塊度矩陣B代替S作為屬性信息的最終表示,定義如下:

B=[bij]=[sij-(ξiξj)/2m]

(6)

將從拓?fù)渲刑崛〉木W(wǎng)絡(luò)特征和從屬性信息中提取的網(wǎng)絡(luò)特征直接加權(quán)求和作為深度自編碼的輸入,計(jì)算公式如下:

X=[xij]=[mij+αbij]

(7)

其中,α表示內(nèi)容向量在提取的網(wǎng)絡(luò)特征中所占權(quán)重。

2.2.3 稀疏自編碼器

自編碼器由編碼器和解碼器組成,其中,編碼器將輸入空間中的數(shù)據(jù)映射到潛在空間,解碼器將潛在空間的數(shù)據(jù)映射到重構(gòu)空間。形式上,編碼器將輸入數(shù)據(jù)zi映射到潛在空間的hi,解碼器將表示空間的對(duì)象hi映射到重建空間中的yi,公式如下:

hi=f(W(H)xi+b(H))

yi=f(W(Y)hi+b(Y))

(8)

其中,W(H)和b(H)是編碼參數(shù),f(·)是編碼/解碼激活函數(shù),如tanhx=(ex-e-x)/(ex+e-x),W(Y)和b(Y)是學(xué)習(xí)的解碼參數(shù)。

自編碼器的損失函數(shù)為:

(9)

其中,β為權(quán)衡參數(shù),H為自編碼訓(xùn)練過程中獲得的隱層表示,Lreg表示W(wǎng)MCNE模型[19]中局部增強(qiáng)約束部分。

當(dāng)自編碼器收斂時(shí),最中間的隱層即為網(wǎng)絡(luò)的最終嵌入。為獲得更好的表示,堆疊多個(gè)自編碼器,構(gòu)建一個(gè)完整的深度自編碼器學(xué)習(xí)網(wǎng)絡(luò)嵌入向量。首先訓(xùn)練第一個(gè)自編碼器來重建輸入矩陣X,并且獲得第一個(gè)隱層H(1)以及第一個(gè)重建層Y(1)。然后使用H(1)訓(xùn)練第2個(gè)自編碼器的隱層,……,以此逐層構(gòu)造模型,然后獲得最終的隱層表示作為最終嵌入。

由于網(wǎng)絡(luò)特征提取過程中多次使用拓?fù)浣Y(jié)構(gòu),因此降低了原拓?fù)浣Y(jié)構(gòu)的稀疏性,使所得特征中非零元素減少,但同時(shí)也導(dǎo)致了模型參數(shù)訓(xùn)練時(shí)間的增加。針對(duì)該問題,本文通過向隱層神經(jīng)元添加稀疏約束減少編碼層中活動(dòng)神經(jīng)元的數(shù)量。采用KL散度計(jì)算每個(gè)神經(jīng)元稀疏損失,定義如下:

Pij=Kkl(pij‖qij)=

(10)

最后,將神經(jīng)元的稀疏損失添加到目標(biāo)函數(shù)中,得到新的目標(biāo)損失函數(shù),如式(11)所示,并且迭代計(jì)算其最小值。

(11)

2.2.4 算法描述

SAANE算法描述如下:

算法1SAANE算法

輸入網(wǎng)絡(luò)G=(V,E,C),迭代次數(shù)r,表示向量維度d,隨機(jī)游走參數(shù)p、q,二階鄰居所占權(quán)重α,局部增強(qiáng)權(quán)重β,稀疏損失權(quán)重γ

輸出節(jié)點(diǎn)嵌入向量矩陣H,其中每行表示一個(gè)節(jié)點(diǎn)對(duì)應(yīng)的嵌入向量

//整合輸入向量

1.對(duì)于給定網(wǎng)絡(luò),使用Node2Vec算法獲得隨機(jī)游走序列;

2.根據(jù)隨機(jī)游走序列,獲得二階鄰居矩陣N和共同鄰居比矩陣R;

3.計(jì)算屬性模塊度矩陣B;

4.根據(jù)式(7)整合輸入向量;

//使用自編碼進(jìn)行迭代訓(xùn)練

5.初始化權(quán)重參數(shù)W和偏置b;

6.for i=1 to r

7.根據(jù)式(8)獲得隱藏層嵌入向量H;

8.根據(jù)Y=f(WTH+b2)獲得輸出層嵌入向量;

9.根據(jù)式(9)的左半部分計(jì)算重建損失loss_a;

10.根據(jù)式(9)的右半部分計(jì)算局部增強(qiáng)損失loss_b;

11.根據(jù)式(10)計(jì)算稀疏損失loss_c;

12.loss=loss_a+loss_b+loss_c;//總的損失函數(shù)

13.使用RMSprop算法最優(yōu)化loss值;

14.end

3 實(shí)驗(yàn)

為評(píng)估本文算法的有效性,在聚類和分類任務(wù)上進(jìn)行實(shí)驗(yàn)測(cè)試。使用5個(gè)具有不同大小和特征的公開數(shù)據(jù)集Washington、Wisconsin、Texas、Cornell和CiteSeer,對(duì)比方法為基于拓?fù)涞乃惴―eepwalk、Node2Vec、LINE、SDNE和基于屬性網(wǎng)絡(luò)的嵌入算法TADW[21]、SNE、DNGR、WMCNE。

為確保對(duì)比的公平性,將所有算法的最終維度設(shè)置為64,參數(shù)采用默認(rèn)值。對(duì)于本文算法,文本屬性權(quán)重占比根據(jù)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)平均邊數(shù)的不同進(jìn)行設(shè)置,以便更大程度提取不同網(wǎng)絡(luò)的內(nèi)在特征。自編碼器中激活函數(shù)選擇tanh(·)。實(shí)驗(yàn)取10次運(yùn)行結(jié)果的平均值進(jìn)行比較。

3.1 數(shù)據(jù)集比較

CiteSeer數(shù)據(jù)集是一個(gè)由3 312個(gè)科學(xué)出版物組成的引文網(wǎng)絡(luò),其中包含6個(gè)類別;WebKB數(shù)據(jù)集包含4個(gè)子數(shù)據(jù)集Washington、Wisconsin、Texas、Cornell,分別收集了4個(gè)不同大學(xué)的網(wǎng)頁數(shù)據(jù)。各數(shù)據(jù)集詳情如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 實(shí)驗(yàn)環(huán)境

本文采用Python3.6實(shí)現(xiàn)各算法,在Intel Core i7-3770 CPU?3.40 GHz,8.00 GB內(nèi)存的Windows10(64位)計(jì)算機(jī)上運(yùn)行程序。

3.3 聚類實(shí)驗(yàn)

得到網(wǎng)絡(luò)嵌入向量后,本文使用K-means算法進(jìn)行聚類,評(píng)估指標(biāo)選用NMI值,表2所示的結(jié)果表明,使用SAANE算法獲得的嵌入向量進(jìn)行聚類任務(wù)時(shí),NMI值在最佳基線上平均提高了5.83%。

表2 9種算法的NMI值對(duì)比

3.4 分類實(shí)驗(yàn)

得到網(wǎng)絡(luò)嵌入向量后,使用Logistic、支持向量機(jī)SVC、線性判別分析LDA、K-近鄰算法4種方法對(duì)這些節(jié)點(diǎn)進(jìn)行正確標(biāo)注分類,并采用精度平均值作為度量指標(biāo)評(píng)估所有方法的性能,如表3所示。可以看出,使用SAANE算法進(jìn)行分類可使準(zhǔn)確率平均提高4.53%。

表3 9種算法的分類準(zhǔn)確率對(duì)比

3.5 實(shí)驗(yàn)結(jié)果分析

表2和表3的實(shí)驗(yàn)結(jié)果顯示,本文算法性能優(yōu)于其他算法。具體分析如下:

1)基于隨機(jī)游走的Node2Vec算法和DeepWalk算法較依賴局部信息,而TADW、SNE、DNGR、WMCNE算法既考慮了拓?fù)浣Y(jié)構(gòu),又考慮了語義信息,其中性能較好的是WMCNE算法,但該算法將處理過的拓?fù)湫畔⒑驼Z義信息進(jìn)行拼接,導(dǎo)致訓(xùn)練前維度過高,訓(xùn)練過程緩慢。本文算法對(duì)拓?fù)浣Y(jié)構(gòu)、二階鄰居、共同鄰居比進(jìn)行整合,并將這些特征標(biāo)準(zhǔn)化,使其能直接進(jìn)行運(yùn)算,再與語義信息加權(quán)整合,既提高了訓(xùn)練速度,又避免了網(wǎng)絡(luò)中拓?fù)湫畔⒑蛯傩孕畔⒌臋?quán)重占比對(duì)目標(biāo)嵌入向量造成影響。表4顯示了2個(gè)模型在不同數(shù)據(jù)集上迭代1 000次并運(yùn)行10次的平均時(shí)間,可以看出,相較于其他8種算法中性能最好的WMCNE算法,本文算法運(yùn)行時(shí)間較短。

表4 WMCNE和SAANE算法的運(yùn)行時(shí)間對(duì)比

2)獲取嵌入向量時(shí),需要根據(jù)情況設(shè)置網(wǎng)絡(luò)拓?fù)湫畔⒑凸?jié)點(diǎn)屬性的權(quán)重,SAANE從邊/節(jié)點(diǎn)比值入手,對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)平均邊數(shù)多的網(wǎng)絡(luò)減少節(jié)點(diǎn)屬性權(quán)重(Washington、Wisconsin、Texas數(shù)據(jù)集節(jié)點(diǎn)屬性權(quán)重為2時(shí)性能較好),而對(duì)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)平均邊數(shù)少的網(wǎng)絡(luò)則增加節(jié)點(diǎn)屬性的權(quán)重(Cornell和Citeseer數(shù)據(jù)集節(jié)點(diǎn)權(quán)重設(shè)置為4時(shí)性能較好)。

4 算法參數(shù)敏感度分析

SAANE算法包含3個(gè)超參數(shù),即前n階鄰居、節(jié)點(diǎn)屬性所占權(quán)重比值α和稀疏損失參數(shù)γ,本文通過改變參數(shù)取值得到不同的節(jié)點(diǎn)嵌入,并用K-means方法對(duì)得到的表示進(jìn)行聚類操作,再使用NMI評(píng)估方法進(jìn)行結(jié)果評(píng)估。

4.1 鄰居階數(shù)影響分析

在實(shí)驗(yàn)過程中,分別測(cè)試選擇二階鄰居、三階鄰居、四階鄰居和五階鄰居在最終實(shí)驗(yàn)結(jié)果NMI值上的影響,如圖4所示,可以看出,本文算法在選擇二階鄰居時(shí)效果較好。

圖4 n階鄰居實(shí)驗(yàn)結(jié)果(n=2,3,4,5)

4.2 屬性特征所占權(quán)重影響分析

圖5顯示了融合拓?fù)涮卣骱驼Z義特征時(shí)語義特征所占權(quán)重的影響,α取值0.0～6.0,間隔0.5進(jìn)行一次實(shí)驗(yàn)。可以看出,α取值的最佳效果與網(wǎng)中每個(gè)節(jié)點(diǎn)擁有的平均邊數(shù)有關(guān),如Washington、Wisconsin、Texas數(shù)據(jù)集的平均邊數(shù)大于1.5,則語義權(quán)重值為2.0時(shí)NMI值較穩(wěn)定且效果較好,而對(duì)于Cornell和Cite數(shù)據(jù)集則平均邊數(shù)小于1.5,語義權(quán)重設(shè)置為4.0性能更好,說明使用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性捕獲網(wǎng)絡(luò)特征時(shí),兩者各自所占權(quán)重與網(wǎng)絡(luò)中各節(jié)點(diǎn)的平均邊數(shù)有關(guān),節(jié)點(diǎn)平均邊數(shù)越大,屬性所占權(quán)重值應(yīng)越小。

圖5 語義特征權(quán)重實(shí)驗(yàn)結(jié)果

4.3 稀疏損失參數(shù)影響分析

圖6顯示了設(shè)置權(quán)重參數(shù)相同情況下稀疏損失參數(shù)取值對(duì)實(shí)驗(yàn)結(jié)果的影響,γ取值0.0～1.0,間隔0.1進(jìn)行一次實(shí)驗(yàn)。可以看出,γ取值的最佳效果與網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)擁有的平均邊數(shù)有關(guān),如Washington、Wisconsin、Texas數(shù)據(jù)集的平均邊數(shù)大于1.5,則稀疏損失設(shè)置為0.1時(shí)NMI值較穩(wěn)定且效果較好,而對(duì)于Cornell和Cite數(shù)據(jù)集則稀疏損失權(quán)重設(shè)置為0.3性能更好,說明使用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性捕獲網(wǎng)絡(luò)特征時(shí),稀疏損失約束與網(wǎng)絡(luò)中各節(jié)點(diǎn)的平均邊數(shù)有關(guān),節(jié)點(diǎn)平均邊數(shù)越多,稀疏損失約束設(shè)置的值應(yīng)越小。

圖6 稀疏損失實(shí)驗(yàn)結(jié)果

5 結(jié)束語

本文提出基于稀疏自編碼器的SAANE算法。根據(jù)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)獲得隨機(jī)游走序列,利用此序列分別得到二階鄰居和共同鄰居比,并將鄰接矩陣、二階鄰居、共同鄰居比相互整合融入語義信息,在此基礎(chǔ)上進(jìn)行深度稀疏自編碼訓(xùn)練,得到最終嵌入向量。該算法在5個(gè)真實(shí)數(shù)據(jù)集上執(zhí)行聚類和分類任務(wù)時(shí)均獲得了較好的效果。然而,本文假設(shè)只要節(jié)點(diǎn)間有鏈接(直接鏈接或間接鏈接)就表示兩個(gè)節(jié)點(diǎn)有一定關(guān)系,但在真實(shí)網(wǎng)絡(luò)中不同類別的兩個(gè)節(jié)點(diǎn)間也可能存在鏈接關(guān)系。如何在網(wǎng)絡(luò)結(jié)構(gòu)中保留正向鏈接并消除多余的鏈接,獲得更貼合真實(shí)網(wǎng)絡(luò)的嵌入向量,將是下一步的研究方向。