保持聚類結構的異質網絡表示學習

張蝶依，尹立杰

河北地質大學 信息工程學院，石家莊 050031

異質信息網絡（Heterogeneous Information Network，HIN）是具有實際意義且應用較為廣泛的邏輯網絡，具有大規模、異質性等特點[1]。HIN 為數據挖掘提供了新的機遇與挑戰，并且它已廣泛應用于聚類、分類、節點相似性判定、鏈路預測、推薦等任務。異質網絡表示學習旨在將網絡中的節點轉化為低維稠密的實數向量，使得結構相似的節點在低維空間中表示向量相似。

異質網絡表示學習方法可分為4類：基于網絡分解的方法、基于矩陣分解的方法、基于深度神經網絡的方法和基于隨機游走的方法。（1）基于網絡分解的方法，如PTE[2]、LSHM[3]、HERec[4]等，將異質信息網絡按照節點類型分解成多個子網絡，分別對子網絡進行表示學習，得到網絡中不同類型節點的向量表示。（2）基于矩陣分解的方法，如CMF[5]、HeteroMF[6]、DSR[7]，通過構建節點間的關系矩陣，然后對關系矩陣進行矩陣分解得到網絡表示。（3）基于深度神經網絡的方法，如HNE[8]，使用深度架構捕獲異構組件之間的復雜交互，將異構網絡中不同類型的節點映射到相同的低維空間中。（4）基于隨機游走的方法，如Metapath2vec[9]、HIN2Vec[10]、TriDNR[11]，采用隨機游走的方式得到游走序列，并通過預測鄰居節點間的特定關系學習異質網絡中節點的低維表示。盡管這些表示學習方法以不同的策略保持了異質網絡原有的局部或全局拓撲結構，但都沒有考慮異質網絡自身存在的聚類結構。依據網絡分解的思想，異質網絡是由若干同質網絡組合而成。對于既定網絡，同質網絡的個數和網絡規模是已知的。那么，在將節點表達映射成低維空間的向量表示時，保持每一組同質信息網絡固有的聚類結構特征，將獲得更豐富的結構信息和語義信息。保持異質網絡聚類結構的表示學習就是在不改變網絡拓撲結構的前提下，保持異質網絡中每一組同質網絡自身的聚類結構特征，將節點表達映射成低維空間的向量表示。

在低維向量表示方法中，隨機游走表示學習方法比深度學習保留了更多的原始網絡拓撲結構信息。2017年，Dong 等[9]提出基于元路徑進行隨機游走的Metapath2vec模型，利用skip-gram模型學習異質網絡中節點的低維嵌入。Metapath2vec++模型在此基礎上對softmax函數進行改進，針對不同類型的節點分別進行歸一化，使得在神經網絡的輸出層將異質網絡分解成若干同質網絡。但是Metapath2vec 和Metapath2vec++模型都只考慮了節點的近鄰拓撲結構，學習到的表示不能很好地保持網絡中自身的聚類結構，導致在節點聚類任務上效果不佳。Rozemberczki 等提出的GEMSEC[12]模型是以保持同質網絡中拓撲結構和聚類結構為目標，學到的表示能很好地表示同質網絡自身的聚類結構，但是該方法不能直接應用于異質網絡。

針對Metapath2vec、Metapath2vec++及GEMSEC 模型自身存在的缺陷，本文提出兩種既能保持異質網絡中的拓撲結構，又能保持網絡聚類結構的異質網絡表示學習模型：HINSC 及其擴展模型HINSC++。模型按照規定的元路徑獲取節點近鄰序列，依據游走策略選擇目標節點，將其作為前饋神經網絡輸入，經過隱層學習節點的低維表示，在輸出層保持節點的近鄰拓撲結構和聚類結構。在AMiner、DBLP兩個真實異質網絡數據上的實驗結果表明，相比Metapath2vec 和Metapath2vec++，本文提到的兩個模型在聚類任務上NMI 值提高12.46%～26.22%，在分類任務上Macro-F1、Micro-F1 值提高9.32%～17.24%。

1 相關定義

定義1（異質信息網絡[13]）給定一個網絡G=(V,E,T,φ,φ)，其中：V是網絡中的節點集合，E是網絡中邊的集合。T=(TV,TE) ，TV和TE分別代表節點和邊類型的集合。每個節點v∈V和每條邊e∈E的類型由映射函數確定，即φ(v):V→TV,φ(e):E→TE。若|TV|+|TE|＞2，給定的有向網絡G就是異質信息網絡。否則為同質網絡。

定義2（元路徑）給定一個網絡G=(V,E,T,φ,φ)，元路徑Vl，即元路徑是定義在關系R下的節點序列，R=R1°R2…°Rl-1，°代表組合類型操作，Ri∈TE，Vi是第i種類型的節點集合，l為序列長度。

異質信息網絡的元路徑是不同類型的節點通過邊關系建立的組合關系。以包含作者（A）、論文（P）、會議（V）三種節點類型的學術網絡為例，存在論文-作者（P-A）、論文-會議（P-V）兩種類型的邊。如圖1（a）所示的學術網絡模型中，作者a1和a2之間存在多條路徑，路徑a1→p1→a2可以看作元路徑“APA”的一個實例，路徑a1→p1→ACL→p2→a2 可以看作元路徑“APVPA”的一個實例。從實例中可以看出兩條元路徑所表達的是兩種不同的語義關系，其中，“APA”表示兩位作者在同一篇論文上的合著關系，“APVPA”表示兩位作者在同一個會議上發表論文[14]。按照指定的元路徑進行隨機游走可以保持異質網絡語義信息下的結構特征。

圖1 異質學術網絡及其元路徑

定義3（異質網絡表示學習）給定一個異質信息網絡G=(V,E,T,φ,φ)，異質網絡表示學習是將網絡中的節點v∈V投影到一個潛在低維表示空間?d中，學習一個映射函數fG:V→?d，其中d≤|V| ，同時保留網絡原有的結構信息和語義關聯。

2 基于元路徑的隨機游走

大多數基于隨機游走的網絡表示學習方法只考慮同種類型的節點和關系，無法直接應用于異質網絡表示學習，并且鄰居節點間的轉移過程僅考慮了網絡上的局部結構信息，具有一定的盲目性。在異質信息網絡中，按照預定義的元路徑指導隨機游走，能夠根據節點間的語義關系控制游走方向，并捕獲不同類型節點之間的語義和結構相關性。

給定一個異質信息網絡G=(V,E,T,φ,φ) 和元路徑，如果下一類節點和當前節點之間有邊連接，且節點類型符合元路徑模式所規定的下一節點類型，從當前節點的鄰居節點中以一定的概率選擇一個節點進行游走。第i步的節點轉移概率為：

其中，vit∈Vt且vit是第i步類型為t的一個節點(v∈V)；Nt+1(vit)表示節點vti類型為t+1 的鄰居節點，vi+1∈Vt+1。

在當前節點如何進行下一步的游走取決于預先定義好的元路徑，元路徑通常以對稱的方式使用，即它的第一個節點類型V1與最后一個節點類型Vl相同[15]：

基于元路徑的隨機游走策略將不同類型節點整合到skip-gram 模型中，有效捕獲網絡節點間的多種語義關系。圖1（a）中的節點a1分別按元路徑“APA”、“APVPA”隨機游走到達節點a4的游走序列，如圖2所示。

圖2 基于元路徑的隨機游走實例

3 異質網絡的skip-gram模型

在自然語言處理領域中，skip-gram 模型能夠根據單詞上下文之間的關系學習單詞的分布式表示，并且取得了很好的效果，將文本語料庫中的上下文概念映射到網絡中，通過構建skip-gram模型，可以得到網絡中節點的低維表示。

給定同質網絡G=(V,E) ，使用skip-gram模型學習網絡中節點的低維嵌入，其目的是在保持網絡局部結構的基礎上最大化網絡概率：

其中，Nv為網絡G中節點v的鄰居節點集合，p(ct|f(v);θ)是在給定節點v的前提下最大化上下文節點ct的條件概率。

給定異質網絡G=(v,E,T,φ,φ)，并且|TV|＞1 或者|TE|＞1，保持網絡近鄰結構的目標是最大化節點v的異質鄰居，對應的目標函數為：

Nt(v)表示隨機游走序列中節點v的第t種類型的鄰居節點集合，如圖3所示。

圖3 異質skip-gram模型

4 保持聚類結構的異質網絡表示學習

采用元路徑隨機游走策略學得的節點表示可以保持原有的拓撲結構和語義信息。如果能在此基礎上進一步保持網絡自身特有的聚類結構，即保持同一集群下節點間的距離更近這一特性，使得學到的節點表示更準確，提高后續任務的精度。因此，本文提出模型HINSC及其改進模型HINSC++。

4.1 HINSC模型

HINSC模型考慮網絡的拓撲結構，按照規定的元路徑隨機游走，得到的游走序列作為神經網絡的輸入，以保持網絡的拓撲結構和聚類結構為目標，利用隨機梯度下降算法學習異質網絡節點的低維嵌入表示。

前饋神經網絡包含輸入層、隱層和輸出層，模型按照規定的元路徑進行隨機游走，對游走序列選中的節點進行one-hot編碼，將其作為神經網絡的輸入，經過隱層的非線性變換，輸出得到每個節點的低維嵌入向量。輸出層的表示由兩部分構成，一部分利用隱層的輸出最大化當前節點與鄰居節點的鏈接概率，保持網絡中節點的近鄰結構；另一部分利用隱層的輸出最小化當前節點到距離其最近簇中心的距離，保持網絡自身的聚類結構。通過對這兩部分進行聯合優化，即同時保持網絡局部近鄰結構和全局聚類結構，保留節點更多的全局性特征，使得學到的節點表示更準確。

為了保持網絡的拓撲結構和聚類結構，其聯合優化目標函數如式（5）所示：

其中，Lt為保持網絡拓撲結構的目標函數，Lc為保持網絡聚類結構的目標函數，γ為聚類代價權重系數。γ的取值將直接影響節點集群的歸屬，若γ較大將導致節點可能向最近的聚類中心移動，但其中不包含節點v的鄰居節點，使得算法不可能同時產生有效的網絡節點表示和簇中心低維表示[11]。所以一般給定較小的初始值γ(0)∈( 0,1] ，采用指數退火策略控制γ的變化，使得γ隨著迭代次數h的增加逐漸增大到1，如式（6）所示，并通過實驗驗證了γ控制策略的準確性，結果如圖4所示：

圖4 h 對聚類系數γ 的影響

（1）保持網絡的拓撲結構

給定異質網絡G=(v,E,T,φ,φ)，并且|TV|＞1 或者|TE|＞1，采用skip-gram 框架（如圖3 所示）學習網絡中節點的有效表示，其目標是在已知源節點v的條件下最大化異質鄰居節點Nt(v),t∈TV的對數似然：

其中，Nt(v)表示節點v的類型為t的鄰居節點集合，p(ct|f(v);θ)是在給定節點v的前提下最大化上下文節點ct的條件概率，通常用softmax函數表示[16]：

f(v)是節點v的低維嵌入表示。

通過式（7）和（8），可以重寫目標函數：

（2）保持網絡的聚類結構

為了更好地保持網絡自身存在的聚類結構，模型引入k-means損失。同類型節點間具有相似的鄰域，而具有相似鄰域的節點對應的向量表示應該更接近。通過添加一個k-means 聚類函數對網絡中節點的表示進行集群化，進而保持網絡中存在的聚類結構，對應的目標函數如下：

其中，c為簇的個數；μc為簇c的簇中心，在嵌入空間中用d維向量表示。

Mikolov在文獻[17]首次提出負采樣時表示該方法很大程度上降低運算復雜度并提高了節點表示的準確性。因此，采用負采樣[17]的優化策略來降低式（9）的計算復雜度：

其中，M為負采樣的個數

4.2 HINSC++模型

HINSC模型在神經網絡的輸出層進行softmax歸一化時沒有考慮節點的類型，因此HINSC++模型在softmax函數上對不同類型的節點分別進行歸一化：

其中，Vt是網絡中第t種類型節點的集合。

考慮到式（12）的復雜度為O(|V|2)，不適合大規模網絡，因此采用負采樣優化策略來降低計算復雜度：

采用隨機梯度下降算法進行迭代訓練，假設μc是距離f(v)最近的簇中心，則f(v)的梯度為：

假設所有的簇中心都是不同的，屬于簇中心c的節點集合為Vc，則簇中心μc的梯度為：

根據節點嵌入表示f(v)和簇中心嵌入表示μc的梯度，給出HINSC++模型的算法描述，如算法1所示。

算法1HINSC++

輸入：異質信息網絡G=(v,E,T,φ,φ)，元路徑Θ，節點游走次數k，游走長度g，向量維度d，窗口大小ω，聚類目標權重系數γ，學習率η，迭代次數h，負采樣個數M。

輸出：節點嵌入向量f(v),v∈V

簇中心嵌入向量μc,c∈C

1. 初始化所有模型參數

2. 按照給定的元路徑生成隨機游走序列

3. 從隨機游走序列中生成訓練樣本{(vi,vj)}

4. foriter=1 tohdo

5. for (vi,vj)∈訓練樣本do

6. 根據式（5）、（10）和（13）來計算L

7. 根據式（6）增大γ

8. 根據式（14）更新f(v)

9. 根據式（15）更新μc

5 實驗與結果分析

5.1 數據集

AMiner Computer Science[18]是一個學術社交網絡，包括論文（P）、作者（A）、會議（V）共3種類型的節點，實驗選取了來自8個研究領域共131個會議上發表的論文來構建異質網絡。

DBLP[19]是一個關于計算機類英文文獻的書目信息網絡。本文從中選取了來自4 個研究領域共20 個會議上發表的論文[10]。DBLP書目信息網絡包含論文（P）、作者（A）、會議（V）共3種類型的節點，論文-作者（P-A）、論文-會議（P-V）兩種類型的邊，使用研究領域作為網絡中節點對應的標簽。為了學得異質網絡中3 種類型節點的低維表示，實驗選擇APVPA元路徑進行隨機游走。

5.2 比較方法

為了驗證本文提出的HINSC和HINSC++模型的有效性，在AMiner 和DBLP 數據集上和幾個具有代表性的網絡表示學習方法進行對比。

DeepWalk[20]/Node2vec[21]：DeepWalk 方法首先通過隨機游走得到一個序列，然后利用skip-gram 模型預測每個節點的鄰居節點，最終得到每個節點的低維表示。Node2vec 方法在此基礎上進行改進，通過設置參數p和q，將BFS和DFS隨機游走相結合來獲取節點的近鄰序列，既保證了網絡結構的等價性，又保證了網絡中節點間的同質性。對于相同的隨機路徑輸入（在node2vec中p=1 和q=1），發現在層次softmax（DeepWalk）和負采樣（Node2vec）之間進行選擇不會產生顯著差異[9]。

LINE[22]：把網絡中的節點根據關系的疏密程度映射到向量空間中去，該算法同時考慮了網絡中節點的一階（1st-）和二階（2nd-）相似性，很好地保留了網絡的局部結構和全局結構。

GEMSEC：以保持網絡聚類結構為目標，學到的表示能很好地保持同質網絡的聚類結構。

Metapath2vec：基于元路徑進行隨機游走，通過skip-gram 模型學習異質網絡中節點的嵌入表示，但是學到的表示只考慮了網絡的拓撲結構。

Metapath2vec++：在Metapath2vec 的基礎上考慮節點的類型，使得不同類型的節點得以區分開來。

為保證公平，所有的算法都采用相同的參數，原始模型metapath2vec、metapath2vec++采用的是隨機梯度下降算法，為了在同等條件下分析改進模型和原始模型的對比效果，HINSC 及其擴展模型HINSC++采用隨機梯度下降算法更新參數，參數設置如下：每個節點隨機游走次數k=100 ，隨機游走長度g=50 ，向量維度d=32，負采樣個數M=5，窗口大小ω=7。

5.3 聚類任務實驗結果分析

采用k-means算法進行聚類，并根據標準化互信息（NMI）對聚類結果進行評估，進行獨立重復實驗10次，取10 次實驗的平均值作為最終結果。如表1 為各算法在AMiner、DBLP數據集上的聚類結果。

表1 AMiner和DBLP各數據集上的聚類結果

從表1 可以看出，本文提出的HINSC、HINSC++模型在2個數據集中的聚類效果均優于對比方法。與聚類效果較好的對比模型Metapath2vec 和Metapath2vec++比較，在AMiner 數據集上，HINSC、HINSC++模型在author 聚類任務上的NMI 值仍提高12.46%～26.66%，在venue 聚類任務上的NMI 值提高7.91%～14.72%，在DBLP數據集上，HINSC、HINSC++模型在author聚類任務上的NMI 值仍提高14.88%～26.8%，在venue 聚類任務上的NMI 值提高8.17%～12.49%，這說明考慮網絡聚類結構能夠保持同類節點間的相似性，對學習異質網絡節點表示有很重要的意義。

5.4 分類任務實驗結果分析

分類算法采用SVM，評價指標采用Macro-F1 和Micro-F1，采用10 折交叉驗證，取所有節點的嵌入表示的90%作為訓練集，剩下的10%作為測試集，重復實驗10 次，取平均值作為最終分類結果，如表2 是各算法在AMiner和DBLP數據集上的分類結果。

從表2可以看出，在venue分類任務中，HINSC++模型在兩個數據集中的分類效果均略高于對比方法。對于author分類任務，以Macro-F1指標為例，HINSC++模型比對比算法中最優的Metapath2vec++分別高17.24%、12.08%，在Micro-F1 指標上，HINSC++模型比對比算法中的最優值分別高9.32%、9.41%。這在一定程度上表明考慮網絡中的聚類結構能夠學到更好的節點表示，加入聚類結構目標學到的表示進一步保持了異質網絡的結構相似性。

表2 AMiner和DBLP各數據集上的分類結果

5.5 參數敏感性分析

HINSC++模型在優化目標中有一個超參數聚類目標權重系數γ，通過實驗分析超參數γ對聚類結果造成的影響，本文分別在AMiner和DBLP兩個數據集上對參數進行測試（如圖5），除了需要測試的參數外，其他參數均保持默認值。

圖5 γ 對聚類NMI值的影響

這里的γ均為初始值，隨著迭代次數h的增加逐漸增大到1，在AMiner 和DBLP 數據集上，隨著γ取值的減小，NMI值先增加后減少，AMiner數據集在0.01處取得最優值，DBLP數據集在0.1處取得最優值。從圖5中可以看出，保持網絡聚類結構對異質網絡表示學習有很大的幫助，當聚類權重系數γ設置較大或者較小都會降低表示學習的效果。因此，本文實驗超參數γ在AMiner 數據集上設置為0.01，在DBLP 數據集上設置為0.1。

6 結束語

本文提出保持聚類結構的異質網絡表示學習模型HINSC 和HINSC++，兩種模型均以網絡拓撲結構信息作為輸入，在輸出層保持節點的近鄰結構和聚類結構，從而更好地學到網絡的聚類信息。聚類和分類任務在兩個真實網絡數據上測試均取得較好的效果，實驗結果表明，HINSC 和HINSC++模型學到的表示確實有效地提高了網絡嵌入的質量。

現實世界網絡具有動態性，節點、鏈接關系會不斷發生變化，如何設計出保持聚類結構的在線異質網絡表示學習算法，將成為下一步的主要研究方向。