保持Motif結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)*

許 磊，黃 玲，王昌棟

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

1 引言

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

近年來，網(wǎng)絡(luò)表示學(xué)習(xí)（又稱為網(wǎng)絡(luò)嵌入）成為了一個熱門領(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)容以及其他輔助信息的同時，能夠?qū)W習(xí)出網(wǎng)絡(luò)的潛在、低維度的嵌入向量空間Rd。之前的網(wǎng)絡(luò)分析算法，它們認(rèn)為獲取網(wǎng)絡(luò)結(jié)構(gòu)信息是一個預(yù)處理的步驟，因此更多的是依賴于人工提??；而網(wǎng)絡(luò)表示學(xué)習(xí)則是將這樣一個問題當(dāng)作是網(wǎng)絡(luò)分析任務(wù)的一部分，使用一種“數(shù)據(jù)驅(qū)動”的模式，學(xué)習(xí)出能夠包含網(wǎng)絡(luò)結(jié)構(gòu)信息的嵌入空間[6]。圖1是網(wǎng)絡(luò)表示學(xué)習(xí)的一個流程圖，從圖中可以直觀地看出，網(wǎng)絡(luò)表示學(xué)習(xí)起到的是橋梁的作用[7]。

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

網(wǎng)絡(luò)Motif，又稱網(wǎng)絡(luò)的高階結(jié)構(gòu)，最早是由Milo等人[8]提出的，它指的是由多個節(jié)點(diǎn)組成的一個小型子網(wǎng)絡(luò)結(jié)構(gòu)。在真實(shí)應(yīng)用中，網(wǎng)絡(luò)Motif在復(fù)雜網(wǎng)絡(luò)分析中起到了至關(guān)重要的作用。比如，一個三角型Motif的存在可能說明社交網(wǎng)絡(luò)中這三個節(jié)點(diǎn)的關(guān)系如“鐵三角”般密切；一個多跳環(huán)形結(jié)構(gòu)的存在可能說明金融網(wǎng)絡(luò)中存在著洗錢的行為；星形網(wǎng)絡(luò)結(jié)構(gòu)可能對應(yīng)的是銀行客戶信息網(wǎng)絡(luò)中一個合成的造假個人賬號[9]。因此，如果能夠捕捉出節(jié)點(diǎn)的高階連接模式，那么就能夠更加準(zhǔn)確地刻畫出網(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)，這樣可能會導(dǎo)致一個問題：沒有考慮到節(jié)點(diǎn)的高階連接模式。

Fig.2 Problem in previous algorithm圖2 之前的算法存在的問題

圖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都有三個鄰居，因此如果只考慮節(jié)點(diǎn)的鄰近性，網(wǎng)絡(luò)表示學(xué)習(xí)算法會認(rèn)為節(jié)點(diǎn)A與節(jié)點(diǎn)B具有相同的結(jié)構(gòu)，從而使得學(xué)習(xí)出來的節(jié)點(diǎn)嵌入向量會很接近。然而，對于A節(jié)點(diǎn)，它沒有Motif結(jié)構(gòu)的存在；對于B節(jié)點(diǎn)，它存在一個三角Motif結(jié)構(gòu)。因此，A節(jié)點(diǎn)與B節(jié)點(diǎn)從Motif角度考慮的話是不相同的。然而，目前為止提出的網(wǎng)絡(luò)表示學(xué)習(xí)算法都沒有考慮到節(jié)點(diǎn)的高階連接模式，因此對于擁有網(wǎng)絡(luò)Motif結(jié)構(gòu)的節(jié)點(diǎn)來說，學(xué)習(xí)出來的節(jié)點(diǎn)嵌入向量可能會不夠準(zhǔn)確。

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

給定一個無權(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)的個數(shù)，m=|E|表示網(wǎng)絡(luò)中邊的數(shù)量。假設(shè)已知網(wǎng)絡(luò)Motif結(jié)構(gòu)T，本文提出的算法想要解決的問題就是將每一個節(jié)點(diǎn)v∈V映射到一個低維的向量空間Rd中，即學(xué)習(xí)出一個映射方法fG:V→Rd，其中d?n，使得在向量空間Rd中，原本網(wǎng)絡(luò)中每個節(jié)點(diǎn)的Motif結(jié)構(gòu)T會很好地被保留下來。

3.1 基于Motif的APPR

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

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

要構(gòu)建基于Motif的矩陣，核心思想是將輸入的鄰接矩陣轉(zhuǎn)換成一個無向帶權(quán)重的矩陣，而這個權(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），因此對應(yīng)位置上W(1,3)的權(quán)值為2；而節(jié)點(diǎn)1與節(jié)點(diǎn)2形成的三角Motif數(shù)量只有一個，因此對應(yīng)位置上的權(quán)值為1。不同的Motif具有不同的特性，在實(shí)驗(yàn)時，要根據(jù)具體的任務(wù)選用適合的Motif網(wǎng)絡(luò)結(jié)構(gòu)；如果網(wǎng)絡(luò)中同時存在不同類型的Motif結(jié)構(gòu)，只需針對特定任務(wù)所選取的Motif結(jié)構(gòu)進(jìn)行研究即可。

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

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

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

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

其中，I是單位矩陣，P代表著在整個網(wǎng)絡(luò)隨機(jī)游走的概率轉(zhuǎn)移矩陣。隨機(jī)游走是一個馬爾科夫鏈的一個過程，即下一步只與當(dāng)前結(jié)果有關(guān)，與更早之前的結(jié)果無關(guān)。因此，隨機(jī)游走到下一個點(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ù)矩陣是個對角矩陣，對角元素為每一個節(jié)點(diǎn)的度數(shù)，e表示的是所有元素為1的矩陣。eu是節(jié)點(diǎn)u的指示向量，如式（2）所示：

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

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

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

算法1 Motif-Approximate-PPR

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

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

3.2 MPNE算法框架

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

3.2.1 DeepWalk模型

Word2Vec算法是Mikolov等人提出用來學(xué)習(xí)語料庫中單詞的分布式表達(dá)[21]。隨后，DeepWalk算法受此啟發(fā)，將語料庫中的單詞這樣一個概念換成網(wǎng)絡(luò)中的節(jié)點(diǎn)，從而將經(jīng)典的Word2Vec算法應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域上。DeepWalk通過隨機(jī)游走得到一條路徑，這個路徑可以被看作是句子，而單詞的上下文可以看作這條路徑中選定節(jié)點(diǎn)的鄰居。假如給定一個網(wǎng)絡(luò)G=(V,E)，則整個模型的目標(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采用了二叉霍夫曼樹和隨機(jī)梯度下降優(yōu)化了目標(biāo)函數(shù)的求導(dǎo)。最后通過反向傳播算法，不斷優(yōu)化更新從而得到最終的節(jié)點(diǎn)向量表示。

3.2.2 MotifWalk

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

算法2 MotifWalk

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

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

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

3.2.3 MPNE算法偽代碼

最后，整個算法偽代碼如算法3所示。

算法3Motif-preserving network embedding

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

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

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

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

本章首先介紹實(shí)驗(yàn)的設(shè)置，包括實(shí)驗(yàn)所采用的數(shù)據(jù)集、評估標(biāo)準(zhǔn)以及對比算法。之后，對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個，它們分別是：

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

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

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

4.1.2 對比算法

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

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

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

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

4.1.3 評估準(zhǔn)則

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

本文提出了保持Motif結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)算法——MPNE算法，從而在學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的向量表示時，更加側(cè)重地考慮節(jié)點(diǎn)的高階連接模式。算法首先根據(jù)需要的網(wǎng)絡(luò)Motif結(jié)構(gòu)得到基于Motif的網(wǎng)絡(luò)權(quán)重矩陣；接著根據(jù)算法MAPPR來快速求得基于Motif的個性化PageRank預(yù)估值；最后，根據(jù)這個預(yù)估值進(jìn)行MotifWalk，得到每一個節(jié)點(diǎn)的隨機(jī)游走路徑，從而能夠運(yùn)用Word2Vec模型來得到網(wǎng)絡(luò)的向量表示。為了驗(yàn)證提出的算法性能，本文將算法應(yīng)用到三個真實(shí)數(shù)據(jù)集上，以及與三個經(jīng)典的網(wǎng)絡(luò)表示算法進(jìn)行比較。從實(shí)驗(yàn)結(jié)果上來看，在稠密以及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ā)展的一個領(lǐng)域，很多學(xué)者提出了許多創(chuàng)新、有啟發(fā)性的算法來更好地揭示網(wǎng)絡(luò)的本質(zhì)，挖掘了很多隱藏的信息。然而，隨著數(shù)據(jù)的形式越來越多元化，網(wǎng)絡(luò)也會變得越來越復(fù)雜，而現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)算法還有很多空白區(qū)域沒有涉及，比如本文提出的網(wǎng)絡(luò)高階結(jié)構(gòu)。而在本文的基礎(chǔ)上，在下一步的研究中，可以更加關(guān)注動態(tài)網(wǎng)絡(luò)的表示學(xué)習(xí)，比如以網(wǎng)絡(luò)高階結(jié)構(gòu)為載體來揭示動態(tài)網(wǎng)絡(luò)結(jié)構(gòu)變化的趨勢，從而來預(yù)測網(wǎng)絡(luò)的發(fā)展變化。除此之外，如今異構(gòu)信息網(wǎng)絡(luò)越來越熱門，因?yàn)樗怯刹煌愋偷墓?jié)點(diǎn)以及不同類型的邊構(gòu)成的，所以異構(gòu)信息網(wǎng)絡(luò)的表示學(xué)習(xí)也是會被不斷關(guān)注、探究的方向。