基于矩陣分解的屬性網絡表示學習

張 潘,盧光躍,呂少卿,趙雪莉

(1.西安郵電大學 通信與信息工程學院,西安 710121; 2.陜西省信息通信網絡及安全重點實驗室,西安 710121)

0 概述

隨著互聯網絡科技的快速發展,網絡已成為人們獲取信息、互動交流的重要途徑。在現實世界中,很多復雜系統都可以表示為社交網絡、引文網絡、生物網絡和信息網絡[1-3]等網絡形式,而以Facebook、Twitter、微信和微博為代表的社交網絡給人們的生活帶來了巨大變化,人們在社交網絡中的活動產生了大量數據,而這些數據通常蘊涵著豐富的可用信息。此外,引文網絡、移動互聯網絡和生物網絡由于結構復雜,并且隱含其中的深層信息通常具有重要的研究意義,因此也受到了學術界的廣泛關注。

機器學習是人工智能的重要研究方向,近年來已有越來越多的機器學習算法被提出,其性能遠超傳統算法,但由于網絡是一種特殊的數據結構,其不能直接作為機器學習算法的輸入進而實現網絡分析任務,因此網絡表示學習技術應運而生[3]。網絡表示學習旨在將網絡中的節點表示為低維實值向量,在一定程度上保留了原始網絡信息。在學習并得到節點表示向量后,可使用機器學習算法進行節點分類[4]和鏈路預測[5]等網絡分析任務。基于局部線性嵌入(Locally Linear Embedding,LLE)[6]和拉普拉斯特征映射(Laplacian Eigenmaps,LE)[7]的傳統網絡表示學習算法通常依賴于求解親和度矩陣的主導特征向量,且時間復雜度較高,因此很難將其應用于大規模網絡。

Word2vec是Google于2013年推出的一個用于獲取詞向量的開源工具[8],在詞向量表示方面取得了良好的性能。受到Word2vec的啟發,PEROZZI于2014年提出DeepWalk算法[9],創造性地將深度學習技術引入網絡表示學習領域,通過隨機游走生成一系列節點序列,然后將這些序列作為Word2vec算法的輸入得到節點的表示向量,在節點分類、鏈路預測等網絡分析任務中取得了較好的效果。文獻[10]提出LINE算法且定義網絡節點間的一階相似性和二階相似性并對其進行概率建模,通過最小化概率分布和經驗分布的KL散度,得到最終的節點表示向量。文獻[11]提出Node2vec算法,其在DeepWalk算法的基礎上設計廣度優先游走和深度優先游走兩種采樣策略,并挖掘出網絡局部特性和全局特性,最終得到節點的表示向量。

然而,上述算法僅考慮了網絡拓撲結構信息,并未有效利用網絡節點的屬性信息,而現實世界中的網絡包含性別、愛好、職業和文本信息等節點屬性信息。因此,如何將這些屬性信息有效融合到網絡表示學習算法中是近年來急需解決的問題。為此,研究人員提出TADW[12]、AANE[13]等算法。文獻[12]證明了DeepWalk算法與矩陣分解的等價性,并對網絡文本信息加以利用,使得TADW算法能得到質量更高的節點表示。AANE算法融合了網絡結構信息和節點屬性信息,并將建模和優化過程分解為多個子問題,通過分布式方式進行聯合學習,大幅提升了訓練速度。但TADW算法針對的節點屬性信息為文本信息,忽略了文本中詞的詞序信息及網絡結構的一階相似性,難以有效挖掘出深層語義信息[14]且解釋性不強,而AANE算法雖然保留了網絡結構的一階相似性,卻忽略了網絡結構的二階相似性。

本文提出一種基于矩陣分解的屬性網絡表示學習算法(ANEMF)。該算法定義二階結構相似度矩陣和屬性相似度矩陣,通過對網絡結構相似度和屬性相似度損失函數進行聯合優化,實現網絡結構信息和節點屬性信息的融合,從而得到節點的向量表示。

1 屬性網絡表示學習

為更好地描述本文提出的屬性網絡表示學習算法,表1列出了主要參數及其定義。

表1 主要參數及其定義Table 1 Main parameters and their definitions

1.1 相關概念

本節主要介紹與本文工作相關的一些定義和模型。

1.2 結構相似性

網絡中直接相連的兩個節點更可能具有相似的向量表示(具有較高權重的節點對在表示空間中的距離更近),即一階相似性[10]。如果兩個節點之間存在一條邊,那么它們在低維向量空間中的表示應該相似。可以看出,一階相似性是網絡結構最為直接的表達形式,因此有必要將其保留。

本文將網絡鄰接矩陣A作為節點間的一階相似度矩陣,為保留一階結構相似性,定義以下損失函數來最小化連接節點之間的表示差異:

(1)

其中,‖·‖F表示矩陣的F范數。

(2)

其中,ai為鄰接矩陣A的第i行,為保留二階結構相似性,最小化以下損失函數:

(3)

基于以上分析,為同時保留網絡結構的一階相似性和二階相似性,本文將最終網絡拓撲結構信息的損失函數定義為:

(4)

其中,參數α>0為二階結構相似性的權重系數,通過調節α的大小以適應不同網絡。

1.3 屬性相似性

(5)

其中,ti為屬性矩陣T的第i行。為保留屬性相似性,本文將屬性信息的損失函數定義為:

(6)

1.4 網絡表示聯合學習

上文通過定義JS和JA兩個損失函數完成對網絡結構信息和節點屬性信息的建模。為使得到的表示向量能夠同時保留網絡結構信息和節點屬性信息,對上述兩種信息進行聯合建模,其聯合損失函數如式(7)所示:

J=JS+βJA=

(7)

其中,β是調節節點屬性信息貢獻程度的一個非負參數,以適應不同網絡和特定任務。具體而言,β越大,意味著節點屬性對表示學習的影響越大。從式(7)可以看出,該模型的基本思想旨在使節點表示向量的內積接近結構相似度的同時也盡可能地接近屬性相似度。

1.5 模型優化

本節先介紹損失函數的優化,即最小化式(7),再給出基于矩陣分解的屬性網絡表示學習算法的偽代碼。由矩陣的F范數和跡之間的關系得到:

J=tr(ATA+αSTS+βMTM)-

2tr(AT+αST+βMT)YYT+

(1+α+β)tr(YYTYYT)

(8)

對Y求偏導得到:

2α(S+ST)Y-2β(M+MT)Y]ij=

[4(1+α+β)YYTY-4(A+αS+βM)Y]ij

(9)

因此,Y具有以下更新規則:

(10)

由文獻[18]可得Y的乘法更新規則為:

(11)

根據以上分析可得基于矩陣分解的屬性網絡表示學習算法(ANEMF)的偽代碼,如算法1所示:

算法1ANEMF算法

輸入屬性網絡G=(V,E,T),迭代次數i,二階結構相似性權重系數α,屬性相似性權重系數β,表示向量維度d

輸出網絡節點表示矩陣Y,每一行對應節點的表示向量rv,v∈V

1.計算鄰接矩陣A

2.根據式(2)計算二階相似度矩陣S

3.根據式(5)計算屬性相似度矩陣M

4.初始化節點表示矩陣Y

5.J=0

6.for iter=1 to i

7.根據式(7)計算損失函數J

8.if相鄰兩次損失函數J的差值小于閾值,跳出循環

9.根據式(11)更新Y

10.end

1.6 算法復雜度分析

由上文分析可以看出,算法時間復雜度主要取決于矩陣的乘法運算,每更新一次節點表示矩陣Y需要的時間復雜度為O(n2d),其中,n表示節點數量,d表示節點表示維數。由于實際應用中d遠小于宏準確率(Macro-P),因此本文ANEMF算法的時間復雜度為宏召回率(Macro-R)。

2 實驗結果與分析

2.1 實驗數據集

本文選取3個公開的真實網絡作為實驗數據集進行實驗仿真,其統計數據如表2所示。

表2 實驗數據集統計Table 2 Experimental datasets statistics

Citeseer數據集包含3 312個節點和4 732條邊,以及6個類別標簽,其中每個節點表示一篇論文,每條邊代表兩篇論文間的引用關系,每篇論文都由一個3 703維的二進制0/1向量進行描述。在本文中,將每個二值向量視為對應節點的屬性信息。

Facebook數據集[19]包含1 034個節點和26 749條邊,其來自一個Facebook用戶的匿名ego-network,節點表示ego用戶的朋友,邊表示朋友之間的友誼關系。每個節點包含“生日”“工作”“性別”“教育”“語言”“地區”等10個匿名屬性信息,使用一個576維的向量進行表示,并將性別作為類別標簽。

GPlus數據集[19]包含4 586個節點和309 864條邊,其來自一個Google Plus用戶的匿名ego-network,節點表示ego用戶的朋友,邊表示朋友之間的友誼關系。每個節點包含“性別”“機構”“職業”“姓氏”“地區”“大學”6個屬性信息,使用一個3 293維的向量進行表示,并將性別作為類別標簽。

2.2 對比算法及參數設置

DeepWalk算法:基于Random Walk采樣和SkipGram模型訓練學習得到的節點表示向量,僅利用網絡結構信息進行網絡表示學習。實驗中DeepWalk算法的參數設置具體為:節點序列長度為40,每個節點采樣的序列數量為40,滑動窗口大小為10。

TADW算法:基于矩陣分解模型將結構信息矩陣分解為兩個參數矩陣和一個屬性信息矩陣,并將網絡結構信息和節點屬性信息相融合得到節點表示向量。實驗中TADW算法的參數設置參考文獻[12],其中λ=0.2。

為保證對比的公平性,實驗中將節點的表示向量維度設置為d=100。另外,本文ANEMF算法的參數設置為α=3、β=1。

2.3 節點分類性能分析

本文將節點表示向量用于多分類任務以評價算法性能。由文獻[20]可知,分類結果使用F1值作為算法評價指標,F1值是分類問題常用的衡量指標。對于有k個類別標簽的數據集而言,假設將第i類數據預測為第i類的個數(真正例)表示為TP(i)、將第i類數據預測為非第i類的個數(假反例)表示為FN(i),將非第i類數據預測為第i類的個數(假正例)表示為FP(i),則F1值定義為:

(12)

其中,P為準確率,R為召回率,具體計算公式如下:

(13)

(14)

在通常情況下需要進行多次訓練和測試同一數據集以客觀評價模型優劣,因此會產生多個不同的TP(i)、FP(i)、FN(i)和TN(i),不妨假設得到n組不同值并對每組值分別計算P與R,從而得到n組P和R,再對其進行求平均得到宏準確率(Macro-P)、宏召回率(Macro-R)和宏F1值(Macro-F1)以及微準確率(Micro-P)、微召回率(Micro-R)和微F1值(Micro-F1)。

(15)

(16)

(17)

(18)

(19)

(20)

本文對每個數據集進行10次獨立重復實驗,取10次實驗的Micro-F1值和Macro-F1值作為最終實驗結果,其中訓練率設置為2%、4%、6%、8%、10%、15%、20%、30%、40%。表3～表5分別記錄了3個數據集在不同訓練率下的節點分類實驗結果,表中加粗數據表示對應訓練率下的最大值。

表3 Citeseer數據集上的節點分類F1值Table 3 Node classification F1 value on Citeseer dataset %

表4 Facebook數據集上的節點分類F1值Table 4 Node classification F1 value on Facebook dataset %

表5 GPlus數據集上的節點分類F1值Table 5 Node classification F1 value on GPlus dataset %

可以看出,僅利用網絡結構信息的DeepWalk算法性能較差,而同時考慮網絡結構信息和節點屬性信息的TADW算法和本文ANEMF算法的性能相對較好,證明了節點屬性信息對于網絡表示學習質量的提升具有重要作用。在Facebook數據集和GPlus數據集上,本文ANEMF算法在節點分類實驗中的優勢較為明顯,以Micro-F1為評價標準,在Facebook和GPlus數據集上,相比TADW算法的節點分類性能提高3.15%～5.11%和2.1%～5.37%;以Macro-F1為評價標準,在Facebook和GPlus數據集上,相比TADW算法的節點分類性能提高了0.17%～4.51%和1.73%～3.28%。在Citeseer數據集上,本文ANEMF算法的性能表現在訓練率較低時有較大優勢,隨著訓練率的提高,TADW算法的性能表現優于本文ANEMF算法,但優勢并不明顯(Micro-F1值的差值在0.5%以內),其原因為Citeseer數據集的節點屬性信息為文本信息,而TADW算法的設計初衷就是融合節點的文本信息。總體而言,本文ANEMF算法在節點分類任務中的性能表現優于對比算法。

2.4 算法穩定性分析

本文ANEMF算法主要包括二階結構相似性權重系數α、屬性相似性權重系數β和節點表示向量的維數d3個參數。為研究這3個參數對本文ANEMF算法的影響,通過在Citeseer、Facebook和GPlus 3個數據集上的實驗對這3個參數進行分析,其中訓練率固定為10%。圖1～圖3分別為本文ANEMF算法在3個數據集上選擇不同α和β時的節點分類F1值的變化情況,其中α和β的取值均為0.1、0.5、1.0、3.0、5.0。可以看出,對于節點表示維數d=100,性能指標Micro-F1值在Citeseer、Facebook和GPlus 3個數據集上的變化范圍分別為3.0%、1.5%和1.6%。因此,整體上看ANEMF算法的性能更穩定。

圖1 ANEMF算法在Citeseer數據集上選擇不同α和β時的Micro-F1值變化情況Fig.1 The change of Micro-F1 value when the ANEMF algorithm selects different α and β on Citeseer dataset

圖3 ANEMF算法在GPlus數據集上選擇不同α和β時的Micro-F1值變化情況Fig.3 The change of Micro-F1 value when the ANEMF algorithm selects different α and β on GPlus dataset

圖4給出了本文ANEMF算法在3個數據集上的Micro-F1值隨著表示維數d的變化情況,其中d的取值分別為25、50、100、150、200。可以看出,對于Citeseer數據集而言,隨著d的增加,性能指標Micro-F1值也增大,當d=50時,實驗結果更優,當d>100后,性能指標Micro-F1值開始下降,并慢慢趨于穩定;對于Facebook和Gplus數據集而言,隨著表示維數d的增加,Micro-F1值穩步提升,最后趨于穩定。因此,本文實驗中選用d的默認值為100維,在保證分類性能的同時具有較低的節點表示向量維數。綜上所述,當參數α、β和d在合理的取值范圍內變化時,本文ANEMF算法具有穩定的性能表現。

圖4 ANEMF算法在3個數據集上Micro-F1值隨d的變化情況Fig.4 The change of Micro-F1 value with d on three datasets of ANEMF algorithm

3 結束語

本文提出一種基于矩陣分解的屬性網絡表示學習算法(ANEMF),聯合網絡拓撲結構和節點屬性信息進行網絡表示學習,使得到的節點表示向量能夠同時保留網絡拓撲結構信息與節點屬性信息。在3個真實公開數據集上進行節點分類和算法穩定性實驗,結果表明本文ANEMF算法在3個數據集上的表現均優于DeepWalk和TADW算法,能夠有效提升節點表示向量在節點分類任務中的性能。但由于現實中的網絡存在明顯的社區結構特性,因此后續可將網絡社區結構信息融入網絡表示學習算法中,進一步提升網絡表示學習質量,使得到的節點表示能更精確地刻畫原始網絡特性。