許 磊，黃 玲，王昌棟

中山大學(xué) 數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院，廣州 510000

1 引言

隨著“大數(shù)據(jù)”時(shí)代的到來(lái)，網(wǎng)絡(luò)（又叫作圖）變得無(wú)處不在，人們?nèi)粘Ｉ钪兴a(chǎn)生的各種各樣的數(shù)據(jù)，都能形成網(wǎng)絡(luò)。網(wǎng)絡(luò)不僅是一種數(shù)據(jù)表示形式，同時(shí)也是信息的載體，能夠很好地存儲(chǔ)兩兩物體之間的連接關(guān)系。如何能夠更加有效地對(duì)網(wǎng)絡(luò)進(jìn)行分析，挖掘出有價(jià)值的信息，是如今很多學(xué)者密切關(guān)注且亟待解決的問(wèn)題。網(wǎng)絡(luò)分析的任務(wù)大致可以分為4種：節(jié)點(diǎn)分類(lèi)任務(wù)、鏈路預(yù)測(cè)任務(wù)、社區(qū)發(fā)現(xiàn)任務(wù)以及可視化任務(wù)。過(guò)去的幾十年，為了解決上述所提及到的任務(wù)，許多學(xué)者提出了各種不同的算法。比如，基于模塊度優(yōu)化[1]和譜方法[2]的社區(qū)發(fā)現(xiàn)算法，基于隨機(jī)游走來(lái)傳遞標(biāo)簽[3]的節(jié)點(diǎn)分類(lèi)算法，以及基于節(jié)點(diǎn)相似度[4]和最大似然模型[5]的鏈路預(yù)測(cè)算法等。然而，這些算法大多是在原有的向量空間，即網(wǎng)絡(luò)鄰接矩陣上來(lái)推導(dǎo)求解，從而完成相關(guān)任務(wù)。這樣做法雖然直接、方便且解釋性強(qiáng)，但需要很昂貴的計(jì)算資源。除此之外，鄰接矩陣非常稀疏，對(duì)于一個(gè)大規(guī)模網(wǎng)絡(luò)來(lái)說(shuō)，鄰接矩陣中絕大部分都是0，這也使得一些快速有效的算法無(wú)法很好地應(yīng)用。

近年來(lái)，網(wǎng)絡(luò)表示學(xué)習(xí)（又稱(chēng)為網(wǎng)絡(luò)嵌入）成為了一個(gè)熱門(mén)領(lǐng)域，引起了很多研究學(xué)者的興趣。網(wǎng)絡(luò)表示學(xué)習(xí)可以廣義地理解成網(wǎng)絡(luò)的特征學(xué)習(xí)，旨在保留網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息、頂點(diǎn)內(nèi)容以及其他輔助信息的同時(shí)，能夠?qū)W習(xí)出網(wǎng)絡(luò)的潛在、低維度的嵌入向量空間Rd。之前的網(wǎng)絡(luò)分析算法，它們認(rèn)為獲取網(wǎng)絡(luò)結(jié)構(gòu)信息是一個(gè)預(yù)處理的步驟，因此更多的是依賴(lài)于人工提??；而網(wǎng)絡(luò)表示學(xué)習(xí)則是將這樣一個(gè)問(wèn)題當(dāng)作是網(wǎng)絡(luò)分析任務(wù)的一部分，使用一種“數(shù)據(jù)驅(qū)動(dòng)”的模式，學(xué)習(xí)出能夠包含網(wǎng)絡(luò)結(jié)構(gòu)信息的嵌入空間[6]。圖1是網(wǎng)絡(luò)表示學(xué)習(xí)的一個(gè)流程圖，從圖中可以直觀地看出，網(wǎng)絡(luò)表示學(xué)習(xí)起到的是橋梁的作用[7]。

Fig.1 Flowchart of network representation learning圖1 網(wǎng)絡(luò)表示學(xué)習(xí)的流程圖

網(wǎng)絡(luò)Motif，又稱(chēng)網(wǎng)絡(luò)的高階結(jié)構(gòu)，最早是由Milo等人[8]提出的，它指的是由多個(gè)節(jié)點(diǎn)組成的一個(gè)小型子網(wǎng)絡(luò)結(jié)構(gòu)。在真實(shí)應(yīng)用中，網(wǎng)絡(luò)Motif在復(fù)雜網(wǎng)絡(luò)分析中起到了至關(guān)重要的作用。比如，一個(gè)三角型Motif的存在可能說(shuō)明社交網(wǎng)絡(luò)中這三個(gè)節(jié)點(diǎn)的關(guān)系如“鐵三角”般密切；一個(gè)多跳環(huán)形結(jié)構(gòu)的存在可能說(shuō)明金融網(wǎng)絡(luò)中存在著洗錢(qián)的行為；星形網(wǎng)絡(luò)結(jié)構(gòu)可能對(duì)應(yīng)的是銀行客戶(hù)信息網(wǎng)絡(luò)中一個(gè)合成的造假個(gè)人賬號(hào)[9]。因此，如果能夠捕捉出節(jié)點(diǎn)的高階連接模式，那么就能夠更加準(zhǔn)確地刻畫(huà)出網(wǎng)絡(luò)結(jié)構(gòu)，從而更好地完成網(wǎng)絡(luò)分析任務(wù)。

這幾年，很多網(wǎng)絡(luò)表示學(xué)習(xí)算法被提出并被很好地應(yīng)用在實(shí)際應(yīng)用中，然而它們大多數(shù)只考慮了節(jié)點(diǎn)的鄰域?qū)傩曰蜞徑?，忽略了?jié)點(diǎn)的Motif結(jié)構(gòu)，這樣可能會(huì)導(dǎo)致一個(gè)問(wèn)題：沒(méi)有考慮到節(jié)點(diǎn)的高階連接模式。

Fig.2 Problem in previous algorithm圖2 之前的算法存在的問(wèn)題

圖2 表示的是節(jié)點(diǎn)A和節(jié)點(diǎn)B的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，可以看到，節(jié)點(diǎn)A和節(jié)點(diǎn)B都有三個(gè)鄰居，因此如果只考慮節(jié)點(diǎn)的鄰近性，網(wǎng)絡(luò)表示學(xué)習(xí)算法會(huì)認(rèn)為節(jié)點(diǎn)A與節(jié)點(diǎn)B具有相同的結(jié)構(gòu)，從而使得學(xué)習(xí)出來(lái)的節(jié)點(diǎn)嵌入向量會(huì)很接近。然而，對(duì)于A節(jié)點(diǎn)，它沒(méi)有Motif結(jié)構(gòu)的存在；對(duì)于B節(jié)點(diǎn)，它存在一個(gè)三角Motif結(jié)構(gòu)。因此，A節(jié)點(diǎn)與B節(jié)點(diǎn)從Motif角度考慮的話(huà)是不相同的。然而，目前為止提出的網(wǎng)絡(luò)表示學(xué)習(xí)算法都沒(méi)有考慮到節(jié)點(diǎn)的高階連接模式，因此對(duì)于擁有網(wǎng)絡(luò)Motif結(jié)構(gòu)的節(jié)點(diǎn)來(lái)說(shuō)，學(xué)習(xí)出來(lái)的節(jié)點(diǎn)嵌入向量可能會(huì)不夠準(zhǔn)確。

為了解決上述問(wèn)題，本文旨在提出一種考慮Motif結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)算法，那么需要考慮兩個(gè)難題：（1）如何根據(jù)指定的Motif結(jié)構(gòu)，捕捉到各個(gè)節(jié)點(diǎn)的高階連接模式；（2）如何將各個(gè)節(jié)點(diǎn)的Motif結(jié)構(gòu)信息應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)上。針對(duì)上述提出的難題，本文提出了MPNE（Motif-preserving network embedding）模型，研究工作主要有：

（1）提出了一種網(wǎng)絡(luò)高階結(jié)構(gòu)表示學(xué)習(xí)算法框架——MPNE，使得在進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)時(shí)能夠考慮節(jié)點(diǎn)的高階結(jié)構(gòu)信息。

（2）MPNE算法首先根據(jù)鄰接矩陣A構(gòu)建出基于Motif的權(quán)重矩陣W，接著通過(guò)APPR（approximate personalized PageRank）算法，計(jì)算出每個(gè)節(jié)點(diǎn)到每個(gè)節(jié)點(diǎn)之間的概率，從而將各個(gè)節(jié)點(diǎn)的高階結(jié)構(gòu)信息包含在內(nèi)。

（3）提出了基于Motif的隨機(jī)游走M(jìn)otifWalk，使得隨機(jī)游走時(shí)更傾向于與當(dāng)前節(jié)點(diǎn)有著緊密Motif結(jié)構(gòu)關(guān)系的節(jié)點(diǎn)。

（4）在三個(gè)真實(shí)世界的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，選取節(jié)點(diǎn)分類(lèi)作為網(wǎng)絡(luò)分析的任務(wù)，實(shí)驗(yàn)結(jié)果證實(shí)了提出的MPNE算法的有效性，特別是在稠密以及Motif結(jié)構(gòu)豐富的網(wǎng)絡(luò)中，Micro-F1以及Macro-F1都比對(duì)比算法提高了不少。

2 相關(guān)工作

網(wǎng)絡(luò)表示學(xué)習(xí)的目的是為了把原本稀疏的鄰接矩陣映射到一個(gè)低維的向量空間，使得節(jié)點(diǎn)能夠用低維稠密的向量表示的同時(shí)，也能保持原來(lái)的網(wǎng)絡(luò)結(jié)構(gòu)信息、節(jié)點(diǎn)內(nèi)容等。本文簡(jiǎn)要地介紹目前網(wǎng)絡(luò)表示學(xué)習(xí)算法的不同分支的一些經(jīng)典算法。

早期的網(wǎng)絡(luò)表示學(xué)習(xí)，絕大多數(shù)都把目光放在矩陣分解的方法上。矩陣分解的算法主要是將網(wǎng)絡(luò)節(jié)點(diǎn)的聯(lián)系通過(guò)一個(gè)矩陣表達(dá)，之后對(duì)這個(gè)矩陣進(jìn)行分解從而得到節(jié)點(diǎn)的向量表達(dá)。最早的一篇基于矩陣分解的網(wǎng)絡(luò)表示學(xué)習(xí)算法是LLE（locally linear embedding）算法[10]。它認(rèn)為在向量空間中，每一個(gè)節(jié)點(diǎn)應(yīng)該是它所有鄰居節(jié)點(diǎn)的線性組合，而線性組合的權(quán)重是由網(wǎng)絡(luò)的節(jié)點(diǎn)鄰接矩陣來(lái)決定的。隨后，LE（Laplacian eigenmaps）算法[11]則認(rèn)為如果兩個(gè)節(jié)點(diǎn)之間的權(quán)重值越高則這兩個(gè)節(jié)點(diǎn)在向量空間中越接近，而且是用拉普拉斯矩陣來(lái)決定這個(gè)權(quán)重值。之后，GF（graph factorization）算法[12]在分解節(jié)點(diǎn)鄰接矩陣的過(guò)程中加入了一個(gè)正則化項(xiàng)來(lái)控制節(jié)點(diǎn)表示向量的秩，同時(shí)運(yùn)用隨機(jī)梯度下降的方法進(jìn)行優(yōu)化，使得算法在大規(guī)模圖中也能高效運(yùn)行。

基于隨機(jī)游走方法的網(wǎng)絡(luò)表示學(xué)習(xí)是近年來(lái)這個(gè)領(lǐng)域比較火的方法。隨機(jī)游走類(lèi)的算法在網(wǎng)絡(luò)分析領(lǐng)域一直被廣泛使用，原因是因?yàn)殡S機(jī)游走能夠很好地反映出網(wǎng)絡(luò)結(jié)構(gòu)的特性，且相比于矩陣分解的方法，基于隨機(jī)游走的方法在性能上要提高很多。DeepWalk算法[12]是第一個(gè)把隨機(jī)游走應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)中的，它主要通過(guò)模擬隨機(jī)游走的過(guò)程，獲取到了每個(gè)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中游走的一條路徑。之后，這條路徑可以看作是一段語(yǔ)句，而路徑中每一個(gè)節(jié)點(diǎn)則是語(yǔ)句中的一個(gè)單詞，然后應(yīng)用到自然語(yǔ)言處理領(lǐng)域中的Word2Vec模型上，從而得到每一個(gè)節(jié)點(diǎn)的嵌入向量。它的核心思想是，如果兩個(gè)節(jié)點(diǎn)很相近，則在游走的路徑上會(huì)更可能地同時(shí)出現(xiàn)。隨后node2vec算法[14]改進(jìn)了DeepWalk算法的隨機(jī)游走過(guò)程，它認(rèn)為游走時(shí)不僅僅要考慮一階相似性，還要考慮二階相似性，因?yàn)槿绻麅蓚€(gè)節(jié)點(diǎn)的共同鄰居越多，說(shuō)明這兩個(gè)節(jié)點(diǎn)越相似。

隨著深度學(xué)習(xí)的高速發(fā)展，基于深度學(xué)習(xí)的表示學(xué)習(xí)算法如SDNE（structural deep network embedding）[15]和DNGR（deep neural network for graph representation）[16]也隨之被提出。相比其他的方法，基于深度學(xué)習(xí)能夠很好地在降維的同時(shí)學(xué)習(xí)到數(shù)據(jù)的非線性特征。

除此之外，有其他一些算法還會(huì)考慮到網(wǎng)絡(luò)節(jié)點(diǎn)的屬性信息[17]。然而目前為止，網(wǎng)絡(luò)表示學(xué)習(xí)大多只考慮了網(wǎng)絡(luò)節(jié)點(diǎn)與節(jié)點(diǎn)之間的相似性，沒(méi)有去考慮網(wǎng)絡(luò)中Motif結(jié)構(gòu)的存在。Motif結(jié)構(gòu)在網(wǎng)絡(luò)中起到了很大的作用，往往組成Motif的節(jié)點(diǎn)關(guān)系更為密切，因此如果能捕捉到每個(gè)節(jié)點(diǎn)的高階連接模式，那么對(duì)于整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的刻畫(huà)會(huì)更為準(zhǔn)確，基于這樣的考慮，本文提出了MPNE算法。目前為止，這是第一篇考慮了網(wǎng)絡(luò)高階結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法。

3 保持高階結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)算法

給定一個(gè)無(wú)權(quán)重網(wǎng)絡(luò)G=(V,E)，以及它的鄰接矩陣A，其中：如果節(jié)點(diǎn)i與節(jié)點(diǎn)j有連接關(guān)系存在，即存在一條邊，則A(i,j)=1；n=|V|表示網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，m=|E|表示網(wǎng)絡(luò)中邊的數(shù)量。假設(shè)已知網(wǎng)絡(luò)Motif結(jié)構(gòu)T，本文提出的算法想要解決的問(wèn)題就是將每一個(gè)節(jié)點(diǎn)v∈V映射到一個(gè)低維的向量空間Rd中，即學(xué)習(xí)出一個(gè)映射方法fG:V→Rd，其中d?n，使得在向量空間Rd中，原本網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的Motif結(jié)構(gòu)T會(huì)很好地被保留下來(lái)。

3.1 基于Motif的APPR

這節(jié)介紹如何在經(jīng)典的APPR算法上考慮節(jié)點(diǎn)的Motif結(jié)構(gòu)。思路是首先構(gòu)建基于Motif的網(wǎng)絡(luò)矩陣，隨后將APPR算法應(yīng)用到這個(gè)權(quán)重矩陣上，從而得到每個(gè)頂點(diǎn)的PageRank值。

3.1.1 構(gòu)建Motif權(quán)重矩陣

要構(gòu)建基于Motif的矩陣，核心思想是將輸入的鄰接矩陣轉(zhuǎn)換成一個(gè)無(wú)向帶權(quán)重的矩陣，而這個(gè)權(quán)重是由兩兩節(jié)點(diǎn)共同參與形成的Motif數(shù)量決定[18]。假定基于Motif所構(gòu)建的矩陣為W，則W(i,j)的值為節(jié)點(diǎn)i與節(jié)點(diǎn)j所共同參與構(gòu)成的Motif的數(shù)量。如圖3所示，可以看到，節(jié)點(diǎn)1與節(jié)點(diǎn)3共同參與構(gòu)成的三角Motif的數(shù)量為2，分別是（123）和（134），因此對(duì)應(yīng)位置上W(1,3)的權(quán)值為2；而節(jié)點(diǎn)1與節(jié)點(diǎn)2形成的三角Motif數(shù)量只有一個(gè)，因此對(duì)應(yīng)位置上的權(quán)值為1。不同的Motif具有不同的特性，在實(shí)驗(yàn)時(shí)，要根據(jù)具體的任務(wù)選用適合的Motif網(wǎng)絡(luò)結(jié)構(gòu)；如果網(wǎng)絡(luò)中同時(shí)存在不同類(lèi)型的Motif結(jié)構(gòu)，只需針對(duì)特定任務(wù)所選取的Motif結(jié)構(gòu)進(jìn)行研究即可。

Fig.3 Motif weighted matrix圖3 Motif權(quán)重矩陣

這樣一來(lái)，就可以得到一個(gè)基于Motif的無(wú)向帶權(quán)網(wǎng)絡(luò)Gw=(Vw,Ew,W)，其中Vw指的是擁有Motif的節(jié)點(diǎn)。

3.1.2 預(yù)估個(gè)性化PageRank向量

個(gè)性化PageRank向量（PPR）代表的是一個(gè)穩(wěn)定的隨機(jī)游走的分布概率。在隨機(jī)游走的每一步，有一個(gè)轉(zhuǎn)移概率α∈(0,1)，它代表著當(dāng)前隨機(jī)游走到的節(jié)點(diǎn)，有(1-α)的概率會(huì)回到隨機(jī)游走的起始點(diǎn)u，有α的概率會(huì)繼續(xù)隨機(jī)游走到下一個(gè)節(jié)點(diǎn)。之所以稱(chēng)之為“個(gè)性化”，就是保證了隨機(jī)游走時(shí)只能跳轉(zhuǎn)到一些特定的點(diǎn)，從而反映出偏好。在這里，選擇特定的點(diǎn)為隨機(jī)游走的起點(diǎn)，這樣一來(lái)，越接近起始點(diǎn)u的節(jié)點(diǎn)，在從u節(jié)點(diǎn)開(kāi)始的隨機(jī)游走的分布概率值（即PPR向量pu）中的值越大。穩(wěn)定的分布概率可以通過(guò)式（1）來(lái)表達(dá)：

其中，I是單位矩陣，P代表著在整個(gè)網(wǎng)絡(luò)隨機(jī)游走的概率轉(zhuǎn)移矩陣。隨機(jī)游走是一個(gè)馬爾科夫鏈的一個(gè)過(guò)程，即下一步只與當(dāng)前結(jié)果有關(guān)，與更早之前的結(jié)果無(wú)關(guān)。因此，隨機(jī)游走到下一個(gè)點(diǎn)的概率取決于當(dāng)前節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的鄰近程度，因此P=WD-1，其中W是網(wǎng)絡(luò)的Motif權(quán)重矩陣，D=diag(We)代表的是度數(shù)矩陣，度數(shù)矩陣是個(gè)對(duì)角矩陣，對(duì)角元素為每一個(gè)節(jié)點(diǎn)的度數(shù)，e表示的是所有元素為1的矩陣。eu是節(jié)點(diǎn)u的指示向量，如式（2）所示：

如果要想求得這樣一個(gè)穩(wěn)定分布概率，一般是通過(guò)冪迭代的方法得到。然而，這樣做會(huì)帶來(lái)高昂的計(jì)算代價(jià)，因此本文采用文獻(xiàn)[19-20]當(dāng)中的快速估算PageRank值算法。算法通過(guò)一個(gè)誤差容忍值ε來(lái)求得預(yù)估向量pu，使得預(yù)估值p?u滿(mǎn)足式（3）所示條件：

其中，D指的是度數(shù)矩陣。

基于Motif的APPR（MAPPR）偽代碼如算法1所示。

算法1 Motif-Approximate-PPR

輸入：網(wǎng)絡(luò)Gw=(Vw,Ew,W)，起始節(jié)點(diǎn)u，轉(zhuǎn)移概率α，誤差容忍值ε。

輸出：個(gè)性化PageRank向量的預(yù)估值。

3.2 MPNE算法框架

在解決了第一個(gè)難點(diǎn)后，開(kāi)始解決第二個(gè)難點(diǎn)：如何將包含了節(jié)點(diǎn)高階連接模式信息的個(gè)性化PageRank預(yù)估值應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)上。本文采用的是基于DeepWalk算法的想法，通過(guò)特定的隨機(jī)游走得到路徑，將路徑運(yùn)用到自然語(yǔ)言處理領(lǐng)域上的Word2Vec模型上。

3.2.1 DeepWalk模型

Word2Vec算法是Mikolov等人提出用來(lái)學(xué)習(xí)語(yǔ)料庫(kù)中單詞的分布式表達(dá)[21]。隨后，DeepWalk算法受此啟發(fā)，將語(yǔ)料庫(kù)中的單詞這樣一個(gè)概念換成網(wǎng)絡(luò)中的節(jié)點(diǎn)，從而將經(jīng)典的Word2Vec算法應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域上。DeepWalk通過(guò)隨機(jī)游走得到一條路徑，這個(gè)路徑可以被看作是句子，而單詞的上下文可以看作這條路徑中選定節(jié)點(diǎn)的鄰居。假如給定一個(gè)網(wǎng)絡(luò)G=(V,E)，則整個(gè)模型的目標(biāo)函數(shù)如式（4）所示：

其中，N(v)是節(jié)點(diǎn)v在路徑上的上下文鄰居，p(c|v;θ)表示的是基于給定節(jié)點(diǎn)v和當(dāng)前的參數(shù)θ下出現(xiàn)節(jié)點(diǎn)c的條件概率。之后，DeepWalk采用了二叉霍夫曼樹(shù)和隨機(jī)梯度下降優(yōu)化了目標(biāo)函數(shù)的求導(dǎo)。最后通過(guò)反向傳播算法，不斷優(yōu)化更新從而得到最終的節(jié)點(diǎn)向量表示。

3.2.2 MotifWalk

然而，DeepWalk算法中的隨機(jī)游走只考慮了一階相似性，即在隨機(jī)游走的過(guò)程，下一步只會(huì)跳到當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，因此DeepWalk算法只適用于不帶權(quán)重的無(wú)向圖。而需要的隨機(jī)游走過(guò)程是基于求解得到的個(gè)性化PageRank預(yù)估值進(jìn)行的，因此在這里，本文提出了基于Motif的隨機(jī)游走M(jìn)otifWalk，偽代碼如算法2所示。

算法2 MotifWalk

輸入：網(wǎng)絡(luò)Gw=(Vw,Ew,W)，起始節(jié)點(diǎn)u，路徑長(zhǎng)度L，轉(zhuǎn)移概率α，誤差容忍值ε。

輸出：基于Motif的隨機(jī)游走路徑walk。

算法2中的第4行概括了MotifWalk是如何進(jìn)行隨機(jī)游走的，即下一步節(jié)點(diǎn)的選擇是通過(guò)帶權(quán)重的非均勻采樣實(shí)現(xiàn)，而權(quán)重則是當(dāng)前節(jié)點(diǎn)的個(gè)性化PageRank預(yù)估值。這樣一來(lái)，路徑會(huì)更可能地添加PageRank值高的節(jié)點(diǎn)，也就是與當(dāng)前節(jié)點(diǎn)有很強(qiáng)Motif結(jié)構(gòu)聯(lián)系的節(jié)點(diǎn)。

3.2.3 MPNE算法偽代碼

最后，整個(gè)算法偽代碼如算法3所示。

算法3Motif-preserving network embedding

輸入：網(wǎng)絡(luò)Gw=(Vw,Ew,W)，向量空間維度d，轉(zhuǎn)移概率α，誤差容忍值ε，每個(gè)節(jié)點(diǎn)的隨機(jī)游走次數(shù)γ，上下文窗口大小w，隨機(jī)游走的路徑長(zhǎng)度L。

輸出：節(jié)點(diǎn)的向量表示矩陣Φ∈R|Vw|×d。

基于之前的預(yù)備知識(shí)，首先從原網(wǎng)絡(luò)中得到Motif權(quán)重網(wǎng)絡(luò)Gw，之后對(duì)這個(gè)網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)進(jìn)行MotifWalk，這樣就能得到以網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)為起始節(jié)點(diǎn)的游走路徑。這個(gè)過(guò)程重復(fù)γ次，最終能夠得到路徑集合Ψ。將路徑集合放到Word2Vec模型中，設(shè)置好上下文的窗口大小w，就能得到所需的網(wǎng)絡(luò)節(jié)點(diǎn)向量表示矩陣Φ。

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

本章首先介紹實(shí)驗(yàn)的設(shè)置，包括實(shí)驗(yàn)所采用的數(shù)據(jù)集、評(píng)估標(biāo)準(zhǔn)以及對(duì)比算法。之后，對(duì)MPNE算法的實(shí)驗(yàn)結(jié)果以及參數(shù)敏感性進(jìn)行分析。本文實(shí)驗(yàn)采用的Motif結(jié)構(gòu)為三角Motif。

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

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

本文實(shí)驗(yàn)所采用的數(shù)據(jù)集有3個(gè)，它們分別是：

（1）Cora[22]數(shù)據(jù)集是基于鏈接的數(shù)據(jù)集，是一個(gè)引用網(wǎng)絡(luò)。整個(gè)數(shù)據(jù)集是由7個(gè)不同領(lǐng)域的2 708篇科學(xué)出版物，以及5 429條鏈接組成。如果兩篇科學(xué)出版物存在著引用/被引用關(guān)系，則這兩篇科學(xué)出版物存在鏈接關(guān)系。節(jié)點(diǎn)的類(lèi)標(biāo)表示這篇科學(xué)出版物屬于哪個(gè)領(lǐng)域。經(jīng)過(guò)統(tǒng)計(jì)，該數(shù)據(jù)集擁有三角Motif結(jié)構(gòu)的節(jié)點(diǎn)有1 470個(gè)。

（2）Citeseer[22]數(shù)據(jù)集和Cora數(shù)據(jù)集相似，同樣是基于鏈接的數(shù)據(jù)集，是一個(gè)引用網(wǎng)絡(luò)。整個(gè)數(shù)據(jù)集是由6個(gè)不同領(lǐng)域的3 312篇科學(xué)出版物，以及4 732條鏈接組成。經(jīng)過(guò)統(tǒng)計(jì)，該數(shù)據(jù)集擁有三角Motif結(jié)構(gòu)的節(jié)點(diǎn)有1 189個(gè)。

（3）TerroristAttack數(shù)據(jù)集是國(guó)外PIT（profile in terror）項(xiàng)目中的一個(gè)聯(lián)系網(wǎng)絡(luò)數(shù)據(jù)集。整個(gè)數(shù)據(jù)集由1 293個(gè)節(jié)點(diǎn)以及3 172條邊組成，每一個(gè)節(jié)點(diǎn)表示一場(chǎng)恐怖襲擊，如果兩場(chǎng)恐怖襲擊的參與者是屬于同一恐怖組織的，則這兩個(gè)節(jié)點(diǎn)存在連接關(guān)系。每個(gè)節(jié)點(diǎn)有一個(gè)類(lèi)標(biāo)，表示這場(chǎng)恐怖襲擊通過(guò)什么手段實(shí)施犯罪，共有6類(lèi)，分別是：縱火、轟炸、綁架、放射性物質(zhì)、槍械武器和其他。經(jīng)過(guò)統(tǒng)計(jì)，該數(shù)據(jù)集擁有三角Motif結(jié)構(gòu)的節(jié)點(diǎn)有354個(gè)。

4.1.2 對(duì)比算法

為了驗(yàn)證本文算法的表現(xiàn)，本文和以下算法進(jìn)行了對(duì)比：

SpectralClustering[23]：譜聚類(lèi)算法首先通過(guò)網(wǎng)絡(luò)G的鄰接矩陣求得網(wǎng)絡(luò)的歸一化拉普拉斯矩陣L?。之后，選取矩陣L?的前d個(gè)最小特征值所對(duì)應(yīng)的特征向量作為節(jié)點(diǎn)的表示向量，從而將網(wǎng)絡(luò)嵌入到向量空間Rd中。

LINE（large-scale information network embedding）[24]：LINE算法不僅考慮了一階相似性，同時(shí)也考慮了二階相似性，從而使得最終學(xué)習(xí)到的向量空間中能夠既保留網(wǎng)絡(luò)局部結(jié)構(gòu)信息，也能保留網(wǎng)絡(luò)全局結(jié)構(gòu)信息。

DeepWalk：DeepWalk算法是通過(guò)隨機(jī)游走生成路徑，之后沿用Word2Vec算法的Skip-Gram模型從而將網(wǎng)絡(luò)嵌入到向量空間Rd中。

4.1.3 評(píng)估準(zhǔn)則

本次實(shí)驗(yàn)選擇完成的網(wǎng)絡(luò)分析任務(wù)為節(jié)點(diǎn)分類(lèi)，由于節(jié)點(diǎn)的類(lèi)標(biāo)種類(lèi)有多個(gè)，因此是多分類(lèi)任務(wù)。由于是多分類(lèi)任務(wù)，因此采用的評(píng)測(cè)指標(biāo)為Micro-F1和Macro-F1，如式（5）、式（6）所示。其中TPi指的是類(lèi)標(biāo)i被預(yù)測(cè)正確的數(shù)量，F(xiàn)Pi指的是實(shí)際上不屬于類(lèi)標(biāo)i但被預(yù)測(cè)為類(lèi)標(biāo)i的數(shù)量，F(xiàn)Ni指的是實(shí)際上屬于類(lèi)標(biāo)i但沒(méi)被正確預(yù)測(cè)的數(shù)量，M指的是類(lèi)標(biāo)個(gè)數(shù)。

這里需要一提的是，在實(shí)驗(yàn)中計(jì)算Macro-F1時(shí)，有一些數(shù)據(jù)集可能存在某個(gè)類(lèi)標(biāo)使得Fi為NaN，從而使得Macro-F1顯示為NaN的結(jié)果。因此，在求解Macro-F1中的Precisioni、Recalli以及Fi時(shí)，會(huì)在分母上加1，避免出現(xiàn)NaN的情況。

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

實(shí)驗(yàn)時(shí)，對(duì)比算法所選用的參數(shù)都為對(duì)比算法論文中提供的缺省參數(shù)，其中SpectralClustering以及DeepWalk算法的d設(shè)置為64，LINE算法的d設(shè)置為500。為了使得實(shí)驗(yàn)結(jié)果更有說(shuō)服性，這里MPNE算法的實(shí)驗(yàn)參數(shù)設(shè)為與DeepWalk算法相同。

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

網(wǎng)絡(luò)表示學(xué)習(xí)算法的重點(diǎn)是更好地將網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)嵌入向量表示，因此為了體現(xiàn)這一點(diǎn)，所采用的機(jī)器學(xué)習(xí)算法也應(yīng)該越簡(jiǎn)單越好。本文最終選用KNN算法來(lái)完成多分類(lèi)任務(wù)，訓(xùn)練集是從數(shù)據(jù)集中隨機(jī)選取，它的個(gè)數(shù)占數(shù)據(jù)集個(gè)數(shù)的比例從10%依次增加至90%。KNN采用的是歐式距離，經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)，K值的選擇在8～15之間比較合適。實(shí)驗(yàn)過(guò)程重復(fù)20次，最后計(jì)算Micro-F1以及Macro-F1的平均值作為最終結(jié)果。由于本文提出的算法是針對(duì)節(jié)點(diǎn)的Motif結(jié)構(gòu)，因此最后進(jìn)行實(shí)驗(yàn)的節(jié)點(diǎn)是數(shù)據(jù)集中具有Motif結(jié)構(gòu)的節(jié)點(diǎn)。最終實(shí)驗(yàn)結(jié)果如表1～表3所示。這說(shuō)明，今后如果遇到網(wǎng)絡(luò)已知的真實(shí)類(lèi)標(biāo)比較少的情況下，本文提出的算法能夠更好地完成網(wǎng)絡(luò)分析任務(wù)。表2顯示的是在Citeseer數(shù)據(jù)集上運(yùn)行的結(jié)果，然而這個(gè)數(shù)據(jù)集上表現(xiàn)得最好的是DeepWalk算法。經(jīng)過(guò)分析，Cora數(shù)據(jù)集共有2 708個(gè)節(jié)點(diǎn)，5 429條邊，其中具有三角Motif結(jié)構(gòu)的節(jié)點(diǎn)有1 470個(gè)；而Citeseer數(shù)據(jù)集共有3 312個(gè)節(jié)點(diǎn)，卻只有4 732條邊，此外，具有三角Motif結(jié)構(gòu)的節(jié)點(diǎn)只有1 189個(gè)。也就是說(shuō)，相比于Citeseer數(shù)據(jù)集，Cora數(shù)據(jù)集更加得稠密，含有的Motif結(jié)構(gòu)信息更加豐富，因此本文算法MPNE能夠表現(xiàn)得更好；而Citeseer數(shù)據(jù)集比較稀疏，含有的高階連接模式信息較少，因此DeepWalk算法能夠表現(xiàn)得更好。這說(shuō)明，本文提出的MPNE算法更適用于稠密網(wǎng)絡(luò)，有助于更好地分析網(wǎng)絡(luò)中的Motif結(jié)構(gòu)信息。最后，表3顯示的是在TerroristAttack數(shù)據(jù)集上運(yùn)行的結(jié)果。Terrorist Attack數(shù)據(jù)集共有1 293個(gè)節(jié)點(diǎn)以及3 172條邊，然而實(shí)際上大多數(shù)節(jié)點(diǎn)都是單獨(dú)一個(gè)節(jié)點(diǎn)存在，經(jīng)過(guò)統(tǒng)計(jì)，最終只有645個(gè)節(jié)點(diǎn)參與了邊的構(gòu)建，且只有354個(gè)節(jié)點(diǎn)具有三角Motif結(jié)構(gòu)，因此整個(gè)網(wǎng)絡(luò)比較稠密，Motif結(jié)構(gòu)信息比較豐富。從結(jié)果來(lái)看，當(dāng)訓(xùn)練集比例大于20%時(shí)，MPNE算法表現(xiàn)得最好。

Table 1 Multi-classification results on Cora表1 在Cora數(shù)據(jù)集上的多分類(lèi)結(jié)果

Table 2 Multi-classification results on Citeseer表2 在Citeseer數(shù)據(jù)集上的多分類(lèi)結(jié)果

Table 3 Multi-classification results on TerroristAttack表3 在TerroristAttack數(shù)據(jù)集上的多分類(lèi)結(jié)果

4.3 參數(shù)敏感性分析

本節(jié)進(jìn)行參數(shù)敏感性實(shí)驗(yàn)，從而檢測(cè)出所用參數(shù)對(duì)算法結(jié)果的影響。這里選用Cora數(shù)據(jù)集做測(cè)試，選取Micro-F1作為測(cè)試指標(biāo)來(lái)觀察，以及訓(xùn)練集的比例設(shè)為90%。當(dāng)以某一參數(shù)作為變量進(jìn)行實(shí)驗(yàn)時(shí)，其他參數(shù)選用缺省值。本文驗(yàn)證了嵌入空間向量維度參數(shù)d，如何選擇上下文鄰居節(jié)點(diǎn)到Word2Vec模型的參數(shù)（隨機(jī)游走次數(shù)、游走的路徑長(zhǎng)度以及上下文窗口大?。┖陀?jì)算個(gè)性化PageRank向量預(yù)估值的參數(shù)（轉(zhuǎn)移概率和誤差容忍值），最后結(jié)果如圖4所示。

可以看到，有些參數(shù)的選擇對(duì)結(jié)果影響不大，如向量維度、隨機(jī)游走次數(shù)以及上下文窗口大小。從結(jié)果中得出，向量維度d的建議取值是32，隨機(jī)游走次數(shù)γ的建議取值是10以及上下文窗口大小w的建議取值是8，因?yàn)榇藭r(shí)算法效果比較好，且如果取了更大的值會(huì)帶來(lái)更高的一個(gè)計(jì)算代價(jià)，但卻不能使算法表現(xiàn)提高，得不償失。有些參數(shù)的選擇對(duì)結(jié)果會(huì)稍微影響，比如當(dāng)路徑長(zhǎng)度大于50和轉(zhuǎn)移概率大于0.9時(shí)，算法的表現(xiàn)會(huì)下降；而有些參數(shù)的選擇則會(huì)對(duì)結(jié)果造成比較大的影響，比如當(dāng)誤差容忍值ε的取值太大時(shí)，會(huì)使算法表現(xiàn)得比較糟糕，因此結(jié)合計(jì)算性能和算法表現(xiàn)考慮，誤差容忍值ε的建議取值為0.01×|V|/2|E|。

Fig.4 Parameter sensitivity analysis圖4 參數(shù)敏感性分析

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

本文提出了保持Motif結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)算法——MPNE算法，從而在學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的向量表示時(shí)，更加側(cè)重地考慮節(jié)點(diǎn)的高階連接模式。算法首先根據(jù)需要的網(wǎng)絡(luò)Motif結(jié)構(gòu)得到基于Motif的網(wǎng)絡(luò)權(quán)重矩陣；接著根據(jù)算法MAPPR來(lái)快速求得基于Motif的個(gè)性化PageRank預(yù)估值；最后，根據(jù)這個(gè)預(yù)估值進(jìn)行MotifWalk，得到每一個(gè)節(jié)點(diǎn)的隨機(jī)游走路徑，從而能夠運(yùn)用Word2Vec模型來(lái)得到網(wǎng)絡(luò)的向量表示。為了驗(yàn)證提出的算法性能，本文將算法應(yīng)用到三個(gè)真實(shí)數(shù)據(jù)集上，以及與三個(gè)經(jīng)典的網(wǎng)絡(luò)表示算法進(jìn)行比較。從實(shí)驗(yàn)結(jié)果上來(lái)看，在稠密以及Motif結(jié)構(gòu)豐富的網(wǎng)絡(luò)中，本文的算法表現(xiàn)得更好，能夠更好地捕捉到網(wǎng)絡(luò)結(jié)構(gòu)信息。除此之外，本文還做了與算法相關(guān)參數(shù)敏感性分析的實(shí)驗(yàn)。

網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域是最近蓬勃發(fā)展的一個(gè)領(lǐng)域，很多學(xué)者提出了許多創(chuàng)新、有啟發(fā)性的算法來(lái)更好地揭示網(wǎng)絡(luò)的本質(zhì)，挖掘了很多隱藏的信息。然而，隨著數(shù)據(jù)的形式越來(lái)越多元化，網(wǎng)絡(luò)也會(huì)變得越來(lái)越復(fù)雜，而現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)算法還有很多空白區(qū)域沒(méi)有涉及，比如本文提出的網(wǎng)絡(luò)高階結(jié)構(gòu)。而在本文的基礎(chǔ)上，在下一步的研究中，可以更加關(guān)注動(dòng)態(tài)網(wǎng)絡(luò)的表示學(xué)習(xí)，比如以網(wǎng)絡(luò)高階結(jié)構(gòu)為載體來(lái)揭示動(dòng)態(tài)網(wǎng)絡(luò)結(jié)構(gòu)變化的趨勢(shì)，從而來(lái)預(yù)測(cè)網(wǎng)絡(luò)的發(fā)展變化。除此之外，如今異構(gòu)信息網(wǎng)絡(luò)越來(lái)越熱門(mén)，因?yàn)樗怯刹煌?lèi)型的節(jié)點(diǎn)以及不同類(lèi)型的邊構(gòu)成的，所以異構(gòu)信息網(wǎng)絡(luò)的表示學(xué)習(xí)也是會(huì)被不斷關(guān)注、探究的方向。