許 磊，黃 玲，王昌棟

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

1 引言

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

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

Fig.1 Flowchart of network representation learning圖1 網(wǎng)絡表示學習的流程圖

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

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

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

圖2 表示的是節(jié)點A和節(jié)點B的網(wǎng)絡拓撲結(jié)構(gòu)，可以看到，節(jié)點A和節(jié)點B都有三個鄰居，因此如果只考慮節(jié)點的鄰近性，網(wǎng)絡表示學習算法會認為節(jié)點A與節(jié)點B具有相同的結(jié)構(gòu)，從而使得學習出來的節(jié)點嵌入向量會很接近。然而，對于A節(jié)點，它沒有Motif結(jié)構(gòu)的存在；對于B節(jié)點，它存在一個三角Motif結(jié)構(gòu)。因此，A節(jié)點與B節(jié)點從Motif角度考慮的話是不相同的。然而，目前為止提出的網(wǎng)絡表示學習算法都沒有考慮到節(jié)點的高階連接模式，因此對于擁有網(wǎng)絡Motif結(jié)構(gòu)的節(jié)點來說，學習出來的節(jié)點嵌入向量可能會不夠準確。

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

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

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

（3）提出了基于Motif的隨機游走MotifWalk，使得隨機游走時更傾向于與當前節(jié)點有著緊密Motif結(jié)構(gòu)關系的節(jié)點。

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

2 相關工作

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

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

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

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

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

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

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

3.1 基于Motif的APPR

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

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

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

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

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

3.1.2 預估個性化PageRank向量

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

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

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

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

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

算法1 Motif-Approximate-PPR

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

輸出：個性化PageRank向量的預估值。

3.2 MPNE算法框架

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

3.2.1 DeepWalk模型

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

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

3.2.2 MotifWalk

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

算法2 MotifWalk

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

輸出：基于Motif的隨機游走路徑walk。

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

3.2.3 MPNE算法偽代碼

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

算法3Motif-preserving network embedding

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

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

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

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

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

4.1 實驗設置

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

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

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

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

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

4.1.2 對比算法

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

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

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

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

4.1.3 評估準則

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

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

4.1.4 實驗參數(shù)設置

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

4.2 實驗結(jié)果分析

網(wǎng)絡表示學習算法的重點是更好地將網(wǎng)絡節(jié)點通過嵌入向量表示，因此為了體現(xiàn)這一點，所采用的機器學習算法也應該越簡單越好。本文最終選用KNN算法來完成多分類任務，訓練集是從數(shù)據(jù)集中隨機選取，它的個數(shù)占數(shù)據(jù)集個數(shù)的比例從10%依次增加至90%。KNN采用的是歐式距離，經(jīng)實驗發(fā)現(xiàn)，K值的選擇在8～15之間比較合適。實驗過程重復20次，最后計算Micro-F1以及Macro-F1的平均值作為最終結(jié)果。由于本文提出的算法是針對節(jié)點的Motif結(jié)構(gòu)，因此最后進行實驗的節(jié)點是數(shù)據(jù)集中具有Motif結(jié)構(gòu)的節(jié)點。最終實驗結(jié)果如表1～表3所示。這說明，今后如果遇到網(wǎng)絡已知的真實類標比較少的情況下，本文提出的算法能夠更好地完成網(wǎng)絡分析任務。表2顯示的是在Citeseer數(shù)據(jù)集上運行的結(jié)果，然而這個數(shù)據(jù)集上表現(xiàn)得最好的是DeepWalk算法。經(jīng)過分析，Cora數(shù)據(jù)集共有2 708個節(jié)點，5 429條邊，其中具有三角Motif結(jié)構(gòu)的節(jié)點有1 470個；而Citeseer數(shù)據(jù)集共有3 312個節(jié)點，卻只有4 732條邊，此外，具有三角Motif結(jié)構(gòu)的節(jié)點只有1 189個。也就是說，相比于Citeseer數(shù)據(jù)集，Cora數(shù)據(jù)集更加得稠密，含有的Motif結(jié)構(gòu)信息更加豐富，因此本文算法MPNE能夠表現(xiàn)得更好；而Citeseer數(shù)據(jù)集比較稀疏，含有的高階連接模式信息較少，因此DeepWalk算法能夠表現(xiàn)得更好。這說明，本文提出的MPNE算法更適用于稠密網(wǎng)絡，有助于更好地分析網(wǎng)絡中的Motif結(jié)構(gòu)信息。最后，表3顯示的是在TerroristAttack數(shù)據(jù)集上運行的結(jié)果。Terrorist Attack數(shù)據(jù)集共有1 293個節(jié)點以及3 172條邊，然而實際上大多數(shù)節(jié)點都是單獨一個節(jié)點存在，經(jīng)過統(tǒng)計，最終只有645個節(jié)點參與了邊的構(gòu)建，且只有354個節(jié)點具有三角Motif結(jié)構(gòu)，因此整個網(wǎng)絡比較稠密，Motif結(jié)構(gòu)信息比較豐富。從結(jié)果來看，當訓練集比例大于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é)進行參數(shù)敏感性實驗，從而檢測出所用參數(shù)對算法結(jié)果的影響。這里選用Cora數(shù)據(jù)集做測試，選取Micro-F1作為測試指標來觀察，以及訓練集的比例設為90%。當以某一參數(shù)作為變量進行實驗時，其他參數(shù)選用缺省值。本文驗證了嵌入空間向量維度參數(shù)d，如何選擇上下文鄰居節(jié)點到Word2Vec模型的參數(shù)（隨機游走次數(shù)、游走的路徑長度以及上下文窗口大?。┖陀嬎銈€性化PageRank向量預估值的參數(shù)（轉(zhuǎn)移概率和誤差容忍值），最后結(jié)果如圖4所示。

可以看到，有些參數(shù)的選擇對結(jié)果影響不大，如向量維度、隨機游走次數(shù)以及上下文窗口大小。從結(jié)果中得出，向量維度d的建議取值是32，隨機游走次數(shù)γ的建議取值是10以及上下文窗口大小w的建議取值是8，因為此時算法效果比較好，且如果取了更大的值會帶來更高的一個計算代價，但卻不能使算法表現(xiàn)提高，得不償失。有些參數(shù)的選擇對結(jié)果會稍微影響，比如當路徑長度大于50和轉(zhuǎn)移概率大于0.9時，算法的表現(xiàn)會下降；而有些參數(shù)的選擇則會對結(jié)果造成比較大的影響，比如當誤差容忍值ε的取值太大時，會使算法表現(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)絡表示學習算法——MPNE算法，從而在學習網(wǎng)絡節(jié)點的向量表示時，更加側(cè)重地考慮節(jié)點的高階連接模式。算法首先根據(jù)需要的網(wǎng)絡Motif結(jié)構(gòu)得到基于Motif的網(wǎng)絡權(quán)重矩陣；接著根據(jù)算法MAPPR來快速求得基于Motif的個性化PageRank預估值；最后，根據(jù)這個預估值進行MotifWalk，得到每一個節(jié)點的隨機游走路徑，從而能夠運用Word2Vec模型來得到網(wǎng)絡的向量表示。為了驗證提出的算法性能，本文將算法應用到三個真實數(shù)據(jù)集上，以及與三個經(jīng)典的網(wǎng)絡表示算法進行比較。從實驗結(jié)果上來看，在稠密以及Motif結(jié)構(gòu)豐富的網(wǎng)絡中，本文的算法表現(xiàn)得更好，能夠更好地捕捉到網(wǎng)絡結(jié)構(gòu)信息。除此之外，本文還做了與算法相關參數(shù)敏感性分析的實驗。

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