保持Motif結構的網絡表示學習*

許 磊，黃 玲，王昌棟

中山大學 數據科學與計算機學院，廣州 510000

1 引言

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

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

Fig.1 Flowchart of network representation learning圖1 網絡表示學習的流程圖

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

這幾年，很多網絡表示學習算法被提出并被很好地應用在實際應用中，然而它們大多數只考慮了節點的鄰域屬性或鄰近性，忽略了節點的Motif結構，這樣可能會導致一個問題：沒有考慮到節點的高階連接模式。

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

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

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

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

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

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

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

2 相關工作

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

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

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

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

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

3 保持高階結構的網絡表示學習算法

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

3.1 基于Motif的APPR

這節介紹如何在經典的APPR算法上考慮節點的Motif結構。思路是首先構建基于Motif的網絡矩陣，隨后將APPR算法應用到這個權重矩陣上，從而得到每個頂點的PageRank值。

3.1.1 構建Motif權重矩陣

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

Fig.3 Motif weighted matrix圖3 Motif權重矩陣

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

3.1.2 預估個性化PageRank向量

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

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

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

其中，D指的是度數矩陣。

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

算法1 Motif-Approximate-PPR

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

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

3.2 MPNE算法框架

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

3.2.1 DeepWalk模型

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

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

3.2.2 MotifWalk

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

算法2 MotifWalk

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

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

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

3.2.3 MPNE算法偽代碼

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

算法3Motif-preserving network embedding

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

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

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

4 實驗結果與分析

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

4.1 實驗設置

4.1.1 數據集

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

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

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

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

4.1.2 對比算法

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

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

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

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

4.1.3 評估準則

本次實驗選擇完成的網絡分析任務為節點分類，由于節點的類標種類有多個，因此是多分類任務。由于是多分類任務，因此采用的評測指標為Micro-F1和Macro-F1，如式（5）、式（6）所示。其中TPi指的是類標i被預測正確的數量，FPi指的是實際上不屬于類標i但被預測為類標i的數量，FNi指的是實際上屬于類標i但沒被正確預測的數量，M指的是類標個數。

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

4.1.4 實驗參數設置

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

4.2 實驗結果分析

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

Table 1 Multi-classification results on Cora表1 在Cora數據集上的多分類結果

Table 2 Multi-classification results on Citeseer表2 在Citeseer數據集上的多分類結果

Table 3 Multi-classification results on TerroristAttack表3 在TerroristAttack數據集上的多分類結果

4.3 參數敏感性分析

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

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

Fig.4 Parameter sensitivity analysis圖4 參數敏感性分析

5 結束語

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

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