潘嘉琪，鄒俊韜

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

0 引 言

網(wǎng)絡(luò)嵌入[1]因成功應(yīng)用于節(jié)點(diǎn)分類(lèi)[2]、鏈路預(yù)測(cè)[3]、節(jié)點(diǎn)聚類(lèi)[4]和可視化[5]等實(shí)際網(wǎng)絡(luò)分析任務(wù)之中，而在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域得到了廣泛的關(guān)注。它解決了傳統(tǒng)以啟發(fā)式方法構(gòu)建網(wǎng)絡(luò)特征而引發(fā)的高計(jì)算成本和不可追溯性的問(wèn)題。

早期，網(wǎng)絡(luò)嵌入被視為一種特殊的數(shù)據(jù)降維技術(shù)，其流程主要被分解為網(wǎng)絡(luò)特征提取和數(shù)據(jù)降維兩個(gè)獨(dú)立的階段。網(wǎng)絡(luò)特征提取主要負(fù)責(zé)擴(kuò)展和利用網(wǎng)絡(luò)的局部或全局拓?fù)鋵傩詠?lái)構(gòu)建網(wǎng)絡(luò)相關(guān)的表示矩陣，而數(shù)據(jù)降維的本質(zhì)就是使用如SVD[6]、IsoMap[7]和神經(jīng)網(wǎng)絡(luò)[8]等降維技術(shù)將輸入數(shù)據(jù)線性或非線性地投影到低維空間以達(dá)到嵌入的目的。由于這類(lèi)方法在潛在空間中缺乏對(duì)原始網(wǎng)絡(luò)屬性的建模表述以及不能夠定義一個(gè)可解釋的目標(biāo)函數(shù)來(lái)迭代優(yōu)化，所以在大部分網(wǎng)絡(luò)相關(guān)的預(yù)測(cè)任務(wù)中表現(xiàn)出的性能差強(qiáng)人意。為了增強(qiáng)嵌入特征向量對(duì)原網(wǎng)絡(luò)結(jié)構(gòu)屬性的表征能力和解釋嵌入特征向量在潛在空間中的意義，近幾年提出的方法試圖在潛在空間中對(duì)節(jié)點(diǎn)之間的關(guān)系進(jìn)行建模，從而在一定程度上耦合網(wǎng)絡(luò)特征提取和數(shù)據(jù)降維兩個(gè)先前獨(dú)立的過(guò)程。通過(guò)定義一個(gè)迭代優(yōu)化目標(biāo)來(lái)捕獲網(wǎng)絡(luò)在原始結(jié)構(gòu)空間中的性質(zhì)，學(xué)習(xí)到的嵌入特征向量在某些特定的機(jī)器學(xué)習(xí)任務(wù)中具有更優(yōu)良的性能。例如，基于網(wǎng)絡(luò)局部結(jié)構(gòu)信息，用概率的方式對(duì)目標(biāo)節(jié)點(diǎn)及其鄰近的上下文節(jié)點(diǎn)進(jìn)行建模，可以讓節(jié)點(diǎn)在潛在空間中的分布近似于在原始結(jié)構(gòu)空間的分布。此外，網(wǎng)絡(luò)中的節(jié)點(diǎn)通常趨向于某幾個(gè)中心以形成社區(qū)結(jié)構(gòu)，在同一社區(qū)內(nèi)部的連接較為緊密，而在不同社區(qū)之間的連接較為稀疏，網(wǎng)絡(luò)的社區(qū)性被證明可以保存全局的拓?fù)浣Y(jié)構(gòu)屬性[9]。

為了嵌入網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)與節(jié)點(diǎn)局部相似性，文中提出了一種基于高階混合投影估計(jì)的網(wǎng)絡(luò)嵌入方法，簡(jiǎn)稱(chēng)為HPNE。該方法使用混合概率生成模型對(duì)節(jié)點(diǎn)的社區(qū)性進(jìn)行建模，并且融入了節(jié)點(diǎn)一階相似性以防止過(guò)擬合現(xiàn)象，最后采用隨機(jī)梯度下降的優(yōu)化策略，迭代最大化極大似然函數(shù)以求得最佳嵌入結(jié)果。

1 問(wèn)題定義

定義2(網(wǎng)絡(luò)嵌入)：給定一個(gè)網(wǎng)絡(luò)G=(V,E)，網(wǎng)絡(luò)嵌入的目標(biāo)就是學(xué)習(xí)一個(gè)映射函數(shù)f:VRd，將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)投影到一個(gè)d維的潛在空間，與此同時(shí)保留節(jié)點(diǎn)在原始結(jié)構(gòu)空間中的性質(zhì)。用ui表示節(jié)點(diǎn)vi對(duì)應(yīng)的潛在特征向量。

定義3(節(jié)點(diǎn)相似性和相似性矩陣)：節(jié)點(diǎn)相似性反映了成對(duì)節(jié)點(diǎn)在原始結(jié)構(gòu)空間或潛在空間中的相似程度，通常由圖核函數(shù)將其轉(zhuǎn)化成特定的實(shí)值。由節(jié)點(diǎn)相似性構(gòu)成的矩陣稱(chēng)為相似性矩陣。

2 基于高階混合投影估計(jì)的網(wǎng)絡(luò)嵌入方法

2.1 基于skip-gram和負(fù)采樣的網(wǎng)絡(luò)嵌入方法

skip-gram模型是用極大似然估計(jì)去刻畫(huà)目標(biāo)節(jié)點(diǎn)w及其上下文節(jié)點(diǎn)c共同出現(xiàn)的概率，它利用一個(gè)長(zhǎng)度為T(mén)的滑動(dòng)窗口從隨機(jī)游走序列中構(gòu)建目標(biāo)-上下文語(yǔ)料集D={(w,c)|w∈V,c∈{wi-T,…,wi-1,wi+1,…,wi+T}}。文獻(xiàn)[10]通過(guò)公式推導(dǎo)證明基于負(fù)采樣下的skip-gram模型等價(jià)于對(duì)式做因式分解，即

(1)

其中#(w,c)、#(w)、#(c)分別表示目標(biāo)-上下文對(duì)(w,c)、目標(biāo)節(jié)點(diǎn)w和上下文節(jié)點(diǎn)c在D中出現(xiàn)的次數(shù)，b是負(fù)采樣的數(shù)目。

文獻(xiàn)[11]將現(xiàn)有的基于skip-gram和負(fù)采樣的網(wǎng)絡(luò)嵌入模型轉(zhuǎn)化成了譜分解的形式，即

(2)

2.2 模型優(yōu)化目標(biāo)構(gòu)建

基于譜分解的網(wǎng)絡(luò)嵌入是將輸入矩陣X∈RN×N直接線性地投影至低維潛在空間，從而生成網(wǎng)絡(luò)的嵌入特征矩陣U∈Rd×N。從數(shù)據(jù)降維的角度看，譜分解只是減小原始數(shù)據(jù)和重構(gòu)數(shù)據(jù)之間的誤差，而并非是在潛在空間中對(duì)網(wǎng)絡(luò)的特性進(jìn)行建模。為了使得嵌入結(jié)果更好地保存網(wǎng)絡(luò)的性質(zhì)，文中引入一個(gè)可學(xué)習(xí)的線性正交算子W∈Rd×N來(lái)實(shí)現(xiàn)原始結(jié)構(gòu)空間到潛在空間的映射，并在潛在空間中直接構(gòu)建可解釋的迭代優(yōu)化目標(biāo)函數(shù)來(lái)生成節(jié)點(diǎn)的潛在特征向量，其投影過(guò)程可以表述為：

u=Wx

(3)

其中，x∈RN表示節(jié)點(diǎn)在原始結(jié)構(gòu)空間中的特征向量，u∈Rd表示相應(yīng)的潛在特征向量。

然而，網(wǎng)絡(luò)的稀疏性和搜索策略上的局限性會(huì)導(dǎo)致x及其真實(shí)值xtrue之間存在誤差xnoise。為不失一般性，假設(shè)傳播誤差的分布服從各向同性高斯分布p(xnoise)～N(0,σ2I)，其中σ2是模型的超參數(shù)[12]。

x=xtrue+xnoise

(4)

xnoise=x-WTu=(I-WTW)x

(5)

(6)

其中，M∈R(N-d)×N也是線性正交算子，有MMT=I。假設(shè)ε服從各項(xiàng)同性高斯分布p(ε)～N(0,σ2I)，它具有和xnoise相同的噪聲方差。由于u和ε相互獨(dú)立，則輸入數(shù)據(jù)x的極大似然概率為：

(7)

(8)

事實(shí)上，節(jié)點(diǎn)之間的關(guān)聯(lián)可能會(huì)隨著W的迭代優(yōu)化而被破壞，即出現(xiàn)過(guò)擬合現(xiàn)象。這一方面是由于W的正交約束在每次迭代中不能總是被滿足或只能近似滿足，另一方面是由于網(wǎng)絡(luò)的社區(qū)性會(huì)過(guò)分地弱化屬于不同社區(qū)的兩個(gè)節(jié)點(diǎn)之間的關(guān)聯(lián)或過(guò)分地增強(qiáng)同一社區(qū)內(nèi)的兩個(gè)節(jié)點(diǎn)之間的關(guān)聯(lián)。因此，為了防止上述過(guò)擬合現(xiàn)象，需要在每次迭代過(guò)程中重構(gòu)節(jié)點(diǎn)的相似性來(lái)維持網(wǎng)絡(luò)的局部結(jié)構(gòu)。文中通過(guò)最小化先驗(yàn)概率和似然概率之間的KL距離來(lái)重構(gòu)節(jié)點(diǎn)的一階相似性，即

(9)

其中，σ(x)=1/(1+exp(-x))是激活函數(shù)。

綜上所述，在聯(lián)合嵌入社區(qū)結(jié)構(gòu)和節(jié)點(diǎn)局部相似性后，最終的目標(biāo)函數(shù)變成了最大化式(10)，即

L=L1-αL2-βLreg

(10)

其中，Lreg是正則項(xiàng)，用于對(duì)投影算子W施加正交約束，α,β>0是權(quán)衡系數(shù)，Lreg是一個(gè)可微分的函數(shù)[13]，定義如下：

(11)

其中，wi表示投影算子W的第i個(gè)行向量，且有‖wi‖=1，i=1,2,…,d。

2.3 模型迭代優(yōu)化

文中采用隨機(jī)梯度下降方法來(lái)優(yōu)化式(10)中的目標(biāo)函數(shù)。在每次迭代過(guò)程中，關(guān)鍵步驟就是計(jì)算正交投影算子W、混合高斯分類(lèi)參數(shù){θk,πk}和噪聲方差σ2的偏導(dǎo)數(shù)。詳細(xì)的優(yōu)化流程如算法1所示。

算法1：基于隨機(jī)梯度下降的優(yōu)化流程算法。

輸入：網(wǎng)絡(luò)G=(V,E)，嵌入維度d,混合高斯組件個(gè)數(shù)K,最大訓(xùn)練迭代次數(shù)T，學(xué)習(xí)速率η，權(quán)衡系數(shù)α,β

輸出：網(wǎng)絡(luò)嵌入特征矩陣U

2.隨機(jī)初始化模型參數(shù)W，σ2，μk，Σk，πk(k=1,2,…,K)

3.fori=1 toTdo

4.計(jì)算嵌入特征矩陣U=WX

7.fork=1 toKdo //更新每個(gè)高斯混合組件的參數(shù)

8.根據(jù)式(16)～式(18)計(jì)算μk,Σk,πk的梯度，并做更新，即

12.end for

14.end for

(1)L關(guān)于正交投影算子W的偏導(dǎo)數(shù)為：

(12)

其中，L1，L2，Lreg關(guān)于W的偏導(dǎo)數(shù)分別為：

(13)

(14)

(15)

(2)L關(guān)于混合高斯分量參數(shù){θk,πk}的偏導(dǎo)數(shù)為：

(16)

(17)

(18)

(3)對(duì)于噪聲方差σ2，存在閉合解，即

(19)

3 實(shí)驗(yàn)仿真與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

3.1.1 數(shù)據(jù)集

為驗(yàn)證提出算法的有效性，采用4個(gè)真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集，其相關(guān)的統(tǒng)計(jì)信息如表1所示。

表1 實(shí)驗(yàn)網(wǎng)絡(luò)數(shù)據(jù)的統(tǒng)計(jì)信息

Wiki包含2 405個(gè)頁(yè)面，15 985個(gè)頁(yè)面之間的超鏈接，一共有19種標(biāo)簽。

Cora是一個(gè)學(xué)術(shù)引用網(wǎng)絡(luò)，其中每個(gè)節(jié)點(diǎn)代表一篇論文，連邊代表論文之間的引用關(guān)系，每篇論文只含有1個(gè)標(biāo)簽。Cora總共含有2 708個(gè)節(jié)點(diǎn)，5 278條連邊(移除了自連接的引用關(guān)聯(lián)，原先有5 429個(gè)引用關(guān)聯(lián))。

Terrorist是一個(gè)恐怖襲擊網(wǎng)絡(luò)，其中每個(gè)節(jié)點(diǎn)表示一個(gè)恐怖襲擊個(gè)體，且分配一個(gè)標(biāo)簽用于顯示攻擊類(lèi)型。該網(wǎng)絡(luò)一共含有645個(gè)節(jié)點(diǎn)(移除了孤立點(diǎn)，原先有1 293個(gè)節(jié)點(diǎn))，3 172條連邊，6種標(biāo)簽。

Karate是一個(gè)小型網(wǎng)絡(luò)，包含34個(gè)節(jié)點(diǎn)和78條邊。

3.1.2 基準(zhǔn)算法

DeepWalk[14]是典型的基于隨機(jī)游走的網(wǎng)絡(luò)嵌入方法，它在網(wǎng)絡(luò)上執(zhí)行均勻隨機(jī)游走來(lái)構(gòu)建語(yǔ)料集，并通過(guò)skip-gram模型訓(xùn)練得到網(wǎng)絡(luò)的潛在特征。

Node2vec[15]在DeepWalk的基礎(chǔ)上引入了兩個(gè)參數(shù)p和q來(lái)控制二階隨機(jī)游走過(guò)程，以此來(lái)平衡深度搜索和廣度搜索。

LINE[16]定義了節(jié)點(diǎn)的一階、二階相似度，并使用負(fù)采樣的優(yōu)化策略來(lái)最小化相似度先驗(yàn)概率和后驗(yàn)概率的KL距離。

GraRep[17]使用截?cái)郤VD方法來(lái)分解不同步長(zhǎng)的高階PPMI矩陣，并將各步長(zhǎng)分解后的特征級(jí)聯(lián)在一起形成網(wǎng)絡(luò)的潛在特征矩陣。

3.1.3 實(shí)驗(yàn)參數(shù)設(shè)置

在和現(xiàn)有模型的對(duì)比實(shí)驗(yàn)中，除非特殊說(shuō)明，否則對(duì)所有的網(wǎng)絡(luò)而言，嵌入維度都默認(rèn)設(shè)置為d=128。對(duì)于DeepWalk和Node2vec方法，窗口大小設(shè)置為10，采樣步長(zhǎng)為80，隨機(jī)游走算子數(shù)為10。此外，Node2vec方法執(zhí)行網(wǎng)格搜索p,q∈{0.25,0.5,0.75,1,4}來(lái)尋找性能最佳的控制參數(shù)。對(duì)于LINE方法，文中采用一階相似度和二階相似度相組合的形式，在基于隨機(jī)梯度下降優(yōu)化過(guò)程中，負(fù)采樣數(shù)為3，學(xué)習(xí)率為0.01。對(duì)于GraRep方法，最高移動(dòng)步長(zhǎng)設(shè)置為6。對(duì)于HPNE方法，高斯混合組件數(shù)K的大小設(shè)置為標(biāo)簽的類(lèi)別種數(shù)；在Karate網(wǎng)絡(luò)中，權(quán)衡系數(shù)α=1,β=5，在Cora和Wiki網(wǎng)絡(luò)中，α=0.01,β=0.02；在Terrorist網(wǎng)絡(luò)中α=0.01,β=0.004；學(xué)習(xí)速率設(shè)置為0.01，最大迭代次數(shù)為100。

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

3.2.1 鏈路預(yù)測(cè)任務(wù)

鏈路預(yù)測(cè)作為一項(xiàng)監(jiān)督式學(xué)習(xí)任務(wù)，它根據(jù)節(jié)點(diǎn)之間的結(jié)構(gòu)信息來(lái)推斷其中存在連邊的可能性。如果節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間存在連邊，則連邊eij的標(biāo)簽為1，否則為0。為了構(gòu)建訓(xùn)練集Etrain，文中隨機(jī)從邊集E中抽取80%的邊作為訓(xùn)練集中的正例樣本，記為Etrain+，并且從不存在的邊集Enon=V×V-E中隨機(jī)抽取同等數(shù)量的邊作為訓(xùn)練集中的負(fù)例樣本，記為Etrain-，以此解決類(lèi)不平衡問(wèn)題。E中剩余20%的邊將作為測(cè)試集中的正例樣本，記為Etest+，而測(cè)試集中的負(fù)例樣本則是從Enon中隨機(jī)抽取和Etest+同等數(shù)量的邊構(gòu)成，記為Etest-。實(shí)驗(yàn)先在網(wǎng)絡(luò)G=(V,Etrain)上執(zhí)行網(wǎng)絡(luò)嵌入算法來(lái)獲得節(jié)點(diǎn)的潛在特征向量，然后借鑒文獻(xiàn)[15]中定義的二元操作算子g(u,v)生成每條邊的特征，最后使用scikit-learn庫(kù)中的線性分類(lèi)器SVM來(lái)訓(xùn)練和預(yù)測(cè)。

二元操作算子g(u,v)定義如下

Average:

(20)

Hadamard:

gi(u,v)=f(u)i·f(v)i

(21)

Weighted-L1:

gi(u,v)=|f(u)i-f(v)i|

(22)

Weighted-L2:

gi(u,v)=|f(u)i-f(v)i|2

(23)

其中，f(u)和f(v)分別表示節(jié)點(diǎn)u和節(jié)點(diǎn)v的潛在特征向量，f(u)i表示f(u)中的第i個(gè)元素。

文中使用AUC(area under the roc curve)指標(biāo)評(píng)估鏈路預(yù)測(cè)的性能。實(shí)驗(yàn)結(jié)果如圖1所示，對(duì)于Karate網(wǎng)絡(luò)，HPNE在Average、Hadamard、Weighted-L2算子上將最佳基準(zhǔn)線分別提高了17.64%、15.0%、8.7%，并在Weightd-L2算子上獲得了最高AUC得分；對(duì)于Cora網(wǎng)絡(luò)，HPNE在Weighted-L1、Weighted-L2算子上將最佳基準(zhǔn)線分別提高了7.6%、10.5%，并在Weightd-L2算子上獲得了最高AUC得分；對(duì)Wiki網(wǎng)絡(luò)，HPNE在Hadamard算子上將最佳基準(zhǔn)線提高了5.1%并且獲得了最高的AUC得分；對(duì)于Terrorist網(wǎng)絡(luò)，HPNE在Hadamard、Weighted-L1算子上分別將最佳基準(zhǔn)線提高了0.4%、3.4%?？傮w而言，提出的模型在鏈路預(yù)測(cè)任務(wù)中和現(xiàn)有的網(wǎng)絡(luò)嵌入算法相比，具有一定的優(yōu)越性。

圖1 鏈路預(yù)測(cè)結(jié)果

3.2.2 節(jié)點(diǎn)分類(lèi)任務(wù)

在節(jié)點(diǎn)分類(lèi)任務(wù)中，每個(gè)節(jié)點(diǎn)都分配有一個(gè)或多個(gè)標(biāo)簽。文中將節(jié)點(diǎn)的潛在特征向量隨其標(biāo)簽一同作為輸入，使用scikit-learn庫(kù)中帶有L2正則項(xiàng)的一對(duì)多Logistic Regression分類(lèi)器進(jìn)行分類(lèi)。隨機(jī)抽取10%到90%的樣本作為訓(xùn)練集，其余作為測(cè)試集。在該任務(wù)中使用Micro-F1和Macro-F1指標(biāo)對(duì)模型的性能進(jìn)行評(píng)估，并且每個(gè)網(wǎng)絡(luò)重復(fù)實(shí)驗(yàn)10次取平均結(jié)果，以避免偶然性。

圖2 Wiki數(shù)據(jù)集的Micro-F1和Macro-F1指標(biāo)得分

如圖2～圖4所示，文中提出的HPNE算法在Micro-F1和Macro-F1指標(biāo)下較其他算法都有一定的性能提升。對(duì)于Wiki網(wǎng)絡(luò)，HPNE將Micro-F1和Macro-F1的最佳基準(zhǔn)線分別提高了2.7%和2.2%，在訓(xùn)練樣本的抽取比率小于20%時(shí)，DeepWalk和GraRep的性能優(yōu)于HPNE，這是由于訓(xùn)練樣本的規(guī)模太小而無(wú)法在網(wǎng)絡(luò)中凸顯社區(qū)結(jié)構(gòu)導(dǎo)致；隨著訓(xùn)練樣本抽取率的提升，社區(qū)結(jié)構(gòu)越來(lái)越凸顯，HPNE的性能也逐漸提升。對(duì)于Cora網(wǎng)絡(luò)，HPNE在Micro-F1和Macro-F1指標(biāo)上比DeepWalk分別提高了1.3%-2.9%和0.74%-3.0%，比Node2vec分別提高了1.9%-2.2%和0.2%-2.0%，比GraRep分別提高了5.2%-11.0%和4.0%-9.2%，比LINE分別提高了21.6%-43.%和22.9%-40.0%。對(duì)于Terrorist網(wǎng)絡(luò)，在訓(xùn)練樣本抽取率為90%的時(shí)候，HPNE在Micro-F1和Macro-F1上擁有最大的性能提升，分別為6.95%和2.54%。綜上所述，HPNE可以將網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)和局部節(jié)點(diǎn)之間的關(guān)聯(lián)嵌入至潛在特征向量中，從而提高節(jié)點(diǎn)分類(lèi)任務(wù)的預(yù)測(cè)性能。

圖3 Cora數(shù)據(jù)集的Micro-F1和Macro-F1指標(biāo)得分

圖4 Terrorist數(shù)據(jù)集的Micro-F1和Macro-F1指標(biāo)得分

4 結(jié)束語(yǔ)

提出了一種基于高階混合投影估計(jì)的網(wǎng)絡(luò)嵌入方法，該方法借鑒譜分解的思想，利用線性算子將網(wǎng)絡(luò)從高維結(jié)構(gòu)空間投影至低維潛在特征空間，然后利用混合概率模型對(duì)節(jié)點(diǎn)的分布進(jìn)行建模以刻畫(huà)網(wǎng)絡(luò)的社區(qū)性質(zhì)。此外，在每次迭代的過(guò)程中還融入了節(jié)點(diǎn)的一階相似性來(lái)防止過(guò)擬合現(xiàn)象。在實(shí)際的優(yōu)化過(guò)程中，該模型的時(shí)間復(fù)雜度與網(wǎng)絡(luò)的規(guī)模呈正相關(guān)，且采用隨機(jī)梯度下降優(yōu)化高斯混合模型參數(shù)時(shí)，需要對(duì)協(xié)方差做近似取舍。因此，如何有效地加速迭代優(yōu)化過(guò)程和使用更合適的混合概率模型來(lái)對(duì)節(jié)點(diǎn)的分布建模是后期主要研究的問(wèn)題。