基于稀疏自編碼器的屬性網絡嵌入算法

張志敏,柴變芳,李文斌

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

0 概述

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

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

本文提出一種深層挖掘網絡拓撲信息并融合節點屬性信息的網絡嵌入算法SAANE。基于網絡鏈接提取二級鄰居和節點的共同鄰居比,并將其整合到同一圖形中,對節點屬性進行相似度計算得到基于屬性相似度的網絡,由此構造屬性模塊度矩陣。在此基礎上,融合網絡拓撲信息和屬性信息進行稀疏自編碼,進而獲得最終的網絡嵌入向量。

1 相關定義

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

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

(1)

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

圖1 Washington數據集的二級鄰居及共同鄰居比

2 SAANE算法

2.1 網絡特征累加對比

為測試網絡拓撲信息深度挖掘的有效性,本文在真實網絡中依次引入鄰接矩陣、二階鄰居、共同鄰居比、節點屬性模塊度,對得到的向量使用K-means方法進行聚類,并選擇NMI作為衡量指標,對比結果如圖2所示。可以看出,針對5個真實網絡依次引入鄰接矩陣、二階鄰居、共同鄰居比和屬性模塊度矩陣,NMI值逐漸增加,說明引入信息的增加有助于進一步挖掘網絡特征。

圖2 真實數據集上的網絡特征聚類結果

2.2 模型框架

SAANE模型框架如圖3所示,其中包含3個模塊:1)網絡特征提取模塊,由網絡拓撲提取二級鄰居及共同鄰居比并進行整合;2)屬性模塊度計算模塊,由節點屬性矩陣獲取屬性模塊度矩陣;3)深度稀疏自編碼器,加權融合處理后的拓撲向量和語義模塊度進行深度稀疏自編碼,同時引入局部增強約束和稀疏損失約束。

圖3 SAANE模型框架

2.2.1 網絡特征提取

M1=sign(A+N)

(2)

為確保由鏈接獲取的信息與共同鄰居比同等重要,采用2-范數對M1做標準化處理,定義如下:

(3)

從而得到:

M2=n(M1)

(4)

對標準化后的特征向量與共同鄰居比求和,即得到由網絡拓撲結構提取出的網絡特征M:

M=M3+R

(5)

2.2.2 語義屬性模塊度

對于節點上的文本屬性,計算兩個節點間的相似性得到相似圖S=[sij]=[cos(wi,wj)],其中wi是節點vi的內容向量。由于模塊度能夠轉好地衡量網絡社區結構強度,因此用模塊度矩陣B代替S作為屬性信息的最終表示,定義如下:

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

(6)

將從拓撲中提取的網絡特征和從屬性信息中提取的網絡特征直接加權求和作為深度自編碼的輸入,計算公式如下:

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

(7)

其中,α表示內容向量在提取的網絡特征中所占權重。

2.2.3 稀疏自編碼器

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

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

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

(8)

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

自編碼器的損失函數為:

(9)

其中,β為權衡參數,H為自編碼訓練過程中獲得的隱層表示,Lreg表示WMCNE模型[19]中局部增強約束部分。

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

由于網絡特征提取過程中多次使用拓撲結構,因此降低了原拓撲結構的稀疏性,使所得特征中非零元素減少,但同時也導致了模型參數訓練時間的增加。針對該問題,本文通過向隱層神經元添加稀疏約束減少編碼層中活動神經元的數量。采用KL散度計算每個神經元稀疏損失,定義如下:

Pij=Kkl(pij‖qij)=

(10)

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

(11)

2.2.4 算法描述

SAANE算法描述如下:

算法1SAANE算法

輸入網絡G=(V,E,C),迭代次數r,表示向量維度d,隨機游走參數p、q,二階鄰居所占權重α,局部增強權重β,稀疏損失權重γ

輸出節點嵌入向量矩陣H,其中每行表示一個節點對應的嵌入向量

//整合輸入向量

1.對于給定網絡,使用Node2Vec算法獲得隨機游走序列;

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

3.計算屬性模塊度矩陣B;

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

//使用自編碼進行迭代訓練

5.初始化權重參數W和偏置b;

6.for i=1 to r

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

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

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

10.根據式(9)的右半部分計算局部增強損失loss_b;

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

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

13.使用RMSprop算法最優化loss值;

14.end

3 實驗

為評估本文算法的有效性,在聚類和分類任務上進行實驗測試。使用5個具有不同大小和特征的公開數據集Washington、Wisconsin、Texas、Cornell和CiteSeer,對比方法為基于拓撲的算法Deepwalk、Node2Vec、LINE、SDNE和基于屬性網絡的嵌入算法TADW[21]、SNE、DNGR、WMCNE。

為確保對比的公平性,將所有算法的最終維度設置為64,參數采用默認值。對于本文算法,文本屬性權重占比根據網絡中每個節點平均邊數的不同進行設置,以便更大程度提取不同網絡的內在特征。自編碼器中激活函數選擇tanh(·)。實驗取10次運行結果的平均值進行比較。

3.1 數據集比較

CiteSeer數據集是一個由3 312個科學出版物組成的引文網絡,其中包含6個類別;WebKB數據集包含4個子數據集Washington、Wisconsin、Texas、Cornell,分別收集了4個不同大學的網頁數據。各數據集詳情如表1所示。

表1 實驗數據集

3.2 實驗環境

本文采用Python3.6實現各算法,在Intel Core i7-3770 CPU?3.40 GHz,8.00 GB內存的Windows10(64位)計算機上運行程序。

3.3 聚類實驗

得到網絡嵌入向量后,本文使用K-means算法進行聚類,評估指標選用NMI值,表2所示的結果表明,使用SAANE算法獲得的嵌入向量進行聚類任務時,NMI值在最佳基線上平均提高了5.83%。

表2 9種算法的NMI值對比

3.4 分類實驗

得到網絡嵌入向量后,使用Logistic、支持向量機SVC、線性判別分析LDA、K-近鄰算法4種方法對這些節點進行正確標注分類,并采用精度平均值作為度量指標評估所有方法的性能,如表3所示。可以看出,使用SAANE算法進行分類可使準確率平均提高4.53%。

表3 9種算法的分類準確率對比

3.5 實驗結果分析

表2和表3的實驗結果顯示,本文算法性能優于其他算法。具體分析如下:

1)基于隨機游走的Node2Vec算法和DeepWalk算法較依賴局部信息,而TADW、SNE、DNGR、WMCNE算法既考慮了拓撲結構,又考慮了語義信息,其中性能較好的是WMCNE算法,但該算法將處理過的拓撲信息和語義信息進行拼接,導致訓練前維度過高,訓練過程緩慢。本文算法對拓撲結構、二階鄰居、共同鄰居比進行整合,并將這些特征標準化,使其能直接進行運算,再與語義信息加權整合,既提高了訓練速度,又避免了網絡中拓撲信息和屬性信息的權重占比對目標嵌入向量造成影響。表4顯示了2個模型在不同數據集上迭代1 000次并運行10次的平均時間,可以看出,相較于其他8種算法中性能最好的WMCNE算法,本文算法運行時間較短。

表4 WMCNE和SAANE算法的運行時間對比

2)獲取嵌入向量時,需要根據情況設置網絡拓撲信息和節點屬性的權重,SAANE從邊/節點比值入手,對網絡中每個節點平均邊數多的網絡減少節點屬性權重(Washington、Wisconsin、Texas數據集節點屬性權重為2時性能較好),而對網絡中每個節點平均邊數少的網絡則增加節點屬性的權重(Cornell和Citeseer數據集節點權重設置為4時性能較好)。

4 算法參數敏感度分析

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

4.1 鄰居階數影響分析

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

圖4 n階鄰居實驗結果(n=2,3,4,5)

4.2 屬性特征所占權重影響分析

圖5顯示了融合拓撲特征和語義特征時語義特征所占權重的影響,α取值0.0～6.0,間隔0.5進行一次實驗。可以看出,α取值的最佳效果與網中每個節點擁有的平均邊數有關,如Washington、Wisconsin、Texas數據集的平均邊數大于1.5,則語義權重值為2.0時NMI值較穩定且效果較好,而對于Cornell和Cite數據集則平均邊數小于1.5,語義權重設置為4.0性能更好,說明使用網絡拓撲結構和節點屬性捕獲網絡特征時,兩者各自所占權重與網絡中各節點的平均邊數有關,節點平均邊數越大,屬性所占權重值應越小。

圖5 語義特征權重實驗結果

4.3 稀疏損失參數影響分析

圖6顯示了設置權重參數相同情況下稀疏損失參數取值對實驗結果的影響,γ取值0.0～1.0,間隔0.1進行一次實驗。可以看出,γ取值的最佳效果與網絡中每個節點擁有的平均邊數有關,如Washington、Wisconsin、Texas數據集的平均邊數大于1.5,則稀疏損失設置為0.1時NMI值較穩定且效果較好,而對于Cornell和Cite數據集則稀疏損失權重設置為0.3性能更好,說明使用網絡拓撲結構和節點屬性捕獲網絡特征時,稀疏損失約束與網絡中各節點的平均邊數有關,節點平均邊數越多,稀疏損失約束設置的值應越小。

圖6 稀疏損失實驗結果

5 結束語

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