基于矩陣分解的屬性網(wǎng)絡(luò)表示學(xué)習(xí)

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

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

0 概述

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

機器學(xué)習(xí)是人工智能的重要研究方向,近年來已有越來越多的機器學(xué)習(xí)算法被提出,其性能遠(yuǎn)超傳統(tǒng)算法,但由于網(wǎng)絡(luò)是一種特殊的數(shù)據(jù)結(jié)構(gòu),其不能直接作為機器學(xué)習(xí)算法的輸入進(jìn)而實現(xiàn)網(wǎng)絡(luò)分析任務(wù),因此網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)應(yīng)運而生[3]。網(wǎng)絡(luò)表示學(xué)習(xí)旨在將網(wǎng)絡(luò)中的節(jié)點表示為低維實值向量,在一定程度上保留了原始網(wǎng)絡(luò)信息。在學(xué)習(xí)并得到節(jié)點表示向量后,可使用機器學(xué)習(xí)算法進(jìn)行節(jié)點分類[4]和鏈路預(yù)測[5]等網(wǎng)絡(luò)分析任務(wù)?；诰植烤€性嵌入(Locally Linear Embedding,LLE)[6]和拉普拉斯特征映射(Laplacian Eigenmaps,LE)[7]的傳統(tǒng)網(wǎng)絡(luò)表示學(xué)習(xí)算法通常依賴于求解親和度矩陣的主導(dǎo)特征向量,且時間復(fù)雜度較高,因此很難將其應(yīng)用于大規(guī)模網(wǎng)絡(luò)。

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

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

本文提出一種基于矩陣分解的屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法(ANEMF)。該算法定義二階結(jié)構(gòu)相似度矩陣和屬性相似度矩陣,通過對網(wǎng)絡(luò)結(jié)構(gòu)相似度和屬性相似度損失函數(shù)進(jìn)行聯(lián)合優(yōu)化,實現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)信息和節(jié)點屬性信息的融合,從而得到節(jié)點的向量表示。

1 屬性網(wǎng)絡(luò)表示學(xué)習(xí)

為更好地描述本文提出的屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法,表1列出了主要參數(shù)及其定義。

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

1.1 相關(guān)概念

本節(jié)主要介紹與本文工作相關(guān)的一些定義和模型。

1.2 結(jié)構(gòu)相似性

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

本文將網(wǎng)絡(luò)鄰接矩陣A作為節(jié)點間的一階相似度矩陣,為保留一階結(jié)構(gòu)相似性,定義以下?lián)p失函數(shù)來最小化連接節(jié)點之間的表示差異:

(1)

其中,‖·‖F(xiàn)表示矩陣的F范數(shù)。

(2)

其中,ai為鄰接矩陣A的第i行,為保留二階結(jié)構(gòu)相似性,最小化以下?lián)p失函數(shù):

(3)

基于以上分析,為同時保留網(wǎng)絡(luò)結(jié)構(gòu)的一階相似性和二階相似性,本文將最終網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的損失函數(shù)定義為:

(4)

其中,參數(shù)α>0為二階結(jié)構(gòu)相似性的權(quán)重系數(shù),通過調(diào)節(jié)α的大小以適應(yīng)不同網(wǎng)絡(luò)。

1.3 屬性相似性

(5)

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

(6)

1.4 網(wǎng)絡(luò)表示聯(lián)合學(xué)習(xí)

上文通過定義JS和JA兩個損失函數(shù)完成對網(wǎng)絡(luò)結(jié)構(gòu)信息和節(jié)點屬性信息的建模。為使得到的表示向量能夠同時保留網(wǎng)絡(luò)結(jié)構(gòu)信息和節(jié)點屬性信息,對上述兩種信息進(jìn)行聯(lián)合建模,其聯(lián)合損失函數(shù)如式(7)所示:

J=JS+βJA=

(7)

其中,β是調(diào)節(jié)節(jié)點屬性信息貢獻(xiàn)程度的一個非負(fù)參數(shù),以適應(yīng)不同網(wǎng)絡(luò)和特定任務(wù)。具體而言,β越大,意味著節(jié)點屬性對表示學(xué)習(xí)的影響越大。從式(7)可以看出,該模型的基本思想旨在使節(jié)點表示向量的內(nèi)積接近結(jié)構(gòu)相似度的同時也盡可能地接近屬性相似度。

1.5 模型優(yōu)化

本節(jié)先介紹損失函數(shù)的優(yōu)化,即最小化式(7),再給出基于矩陣分解的屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法的偽代碼。由矩陣的F范數(shù)和跡之間的關(guān)系得到:

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

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

(1+α+β)tr(YYTYYT)

(8)

對Y求偏導(dǎo)得到:

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

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

(9)

因此,Y具有以下更新規(guī)則:

(10)

由文獻(xiàn)[18]可得Y的乘法更新規(guī)則為:

(11)

根據(jù)以上分析可得基于矩陣分解的屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法(ANEMF)的偽代碼,如算法1所示:

算法1ANEMF算法

輸入屬性網(wǎng)絡(luò)G=(V,E,T),迭代次數(shù)i,二階結(jié)構(gòu)相似性權(quán)重系數(shù)α,屬性相似性權(quán)重系數(shù)β,表示向量維度d

輸出網(wǎng)絡(luò)節(jié)點表示矩陣Y,每一行對應(yīng)節(jié)點的表示向量rv,v∈V

1.計算鄰接矩陣A

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

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

4.初始化節(jié)點表示矩陣Y

5.J=0

6.for iter=1 to i

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

8.if相鄰兩次損失函數(shù)J的差值小于閾值,跳出循環(huán)

9.根據(jù)式(11)更新Y

10.end

1.6 算法復(fù)雜度分析

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

2 實驗結(jié)果與分析

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

本文選取3個公開的真實網(wǎng)絡(luò)作為實驗數(shù)據(jù)集進(jìn)行實驗仿真,其統(tǒng)計數(shù)據(jù)如表2所示。

表2 實驗數(shù)據(jù)集統(tǒng)計Table 2 Experimental datasets statistics

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

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

GPlus數(shù)據(jù)集[19]包含4 586個節(jié)點和309 864條邊,其來自一個Google Plus用戶的匿名ego-network,節(jié)點表示ego用戶的朋友,邊表示朋友之間的友誼關(guān)系。每個節(jié)點包含“性別”“機構(gòu)”“職業(yè)”“姓氏”“地區(qū)”“大學(xué)”6個屬性信息,使用一個3 293維的向量進(jìn)行表示,并將性別作為類別標(biāo)簽。

2.2 對比算法及參數(shù)設(shè)置

DeepWalk算法:基于Random Walk采樣和SkipGram模型訓(xùn)練學(xué)習(xí)得到的節(jié)點表示向量,僅利用網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)。實驗中DeepWalk算法的參數(shù)設(shè)置具體為:節(jié)點序列長度為40,每個節(jié)點采樣的序列數(shù)量為40,滑動窗口大小為10。

TADW算法:基于矩陣分解模型將結(jié)構(gòu)信息矩陣分解為兩個參數(shù)矩陣和一個屬性信息矩陣,并將網(wǎng)絡(luò)結(jié)構(gòu)信息和節(jié)點屬性信息相融合得到節(jié)點表示向量。實驗中TADW算法的參數(shù)設(shè)置參考文獻(xiàn)[12],其中λ=0.2。

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

2.3 節(jié)點分類性能分析

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

(12)

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

(13)

(14)

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

(15)

(16)

(17)

(18)

(19)

(20)

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

表3 Citeseer數(shù)據(jù)集上的節(jié)點分類F1值Table 3 Node classification F1 value on Citeseer dataset %

表4 Facebook數(shù)據(jù)集上的節(jié)點分類F1值Table 4 Node classification F1 value on Facebook dataset %

表5 GPlus數(shù)據(jù)集上的節(jié)點分類F1值Table 5 Node classification F1 value on GPlus dataset %

可以看出,僅利用網(wǎng)絡(luò)結(jié)構(gòu)信息的DeepWalk算法性能較差,而同時考慮網(wǎng)絡(luò)結(jié)構(gòu)信息和節(jié)點屬性信息的TADW算法和本文ANEMF算法的性能相對較好,證明了節(jié)點屬性信息對于網(wǎng)絡(luò)表示學(xué)習(xí)質(zhì)量的提升具有重要作用。在Facebook數(shù)據(jù)集和GPlus數(shù)據(jù)集上,本文ANEMF算法在節(jié)點分類實驗中的優(yōu)勢較為明顯,以Micro-F1為評價標(biāo)準(zhǔn),在Facebook和GPlus數(shù)據(jù)集上,相比TADW算法的節(jié)點分類性能提高3.15%～5.11%和2.1%～5.37%;以Macro-F1為評價標(biāo)準(zhǔn),在Facebook和GPlus數(shù)據(jù)集上,相比TADW算法的節(jié)點分類性能提高了0.17%～4.51%和1.73%～3.28%。在Citeseer數(shù)據(jù)集上,本文ANEMF算法的性能表現(xiàn)在訓(xùn)練率較低時有較大優(yōu)勢,隨著訓(xùn)練率的提高,TADW算法的性能表現(xiàn)優(yōu)于本文ANEMF算法,但優(yōu)勢并不明顯(Micro-F1值的差值在0.5%以內(nèi)),其原因為Citeseer數(shù)據(jù)集的節(jié)點屬性信息為文本信息,而TADW算法的設(shè)計初衷就是融合節(jié)點的文本信息?？傮w而言,本文ANEMF算法在節(jié)點分類任務(wù)中的性能表現(xiàn)優(yōu)于對比算法。

2.4 算法穩(wěn)定性分析

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

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

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

圖4給出了本文ANEMF算法在3個數(shù)據(jù)集上的Micro-F1值隨著表示維數(shù)d的變化情況,其中d的取值分別為25、50、100、150、200?？梢钥闯?對于Citeseer數(shù)據(jù)集而言,隨著d的增加,性能指標(biāo)Micro-F1值也增大,當(dāng)d=50時,實驗結(jié)果更優(yōu),當(dāng)d>100后,性能指標(biāo)Micro-F1值開始下降,并慢慢趨于穩(wěn)定;對于Facebook和Gplus數(shù)據(jù)集而言,隨著表示維數(shù)d的增加,Micro-F1值穩(wěn)步提升,最后趨于穩(wěn)定。因此,本文實驗中選用d的默認(rèn)值為100維,在保證分類性能的同時具有較低的節(jié)點表示向量維數(shù)。綜上所述,當(dāng)參數(shù)α、β和d在合理的取值范圍內(nèi)變化時,本文ANEMF算法具有穩(wěn)定的性能表現(xiàn)。

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

3 結(jié)束語

本文提出一種基于矩陣分解的屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法(ANEMF),聯(lián)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點屬性信息進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí),使得到的節(jié)點表示向量能夠同時保留網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息與節(jié)點屬性信息。在3個真實公開數(shù)據(jù)集上進(jìn)行節(jié)點分類和算法穩(wěn)定性實驗,結(jié)果表明本文ANEMF算法在3個數(shù)據(jù)集上的表現(xiàn)均優(yōu)于DeepWalk和TADW算法,能夠有效提升節(jié)點表示向量在節(jié)點分類任務(wù)中的性能。但由于現(xiàn)實中的網(wǎng)絡(luò)存在明顯的社區(qū)結(jié)構(gòu)特性,因此后續(xù)可將網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)信息融入網(wǎng)絡(luò)表示學(xué)習(xí)算法中,進(jìn)一步提升網(wǎng)絡(luò)表示學(xué)習(xí)質(zhì)量,使得到的節(jié)點表示能更精確地刻畫原始網(wǎng)絡(luò)特性。