一種融合社區(qū)結構信息的網絡表示學習算法

劉彥北，劉金新，耿 磊，王 雯

（1.天津工業(yè)大學 生命科學學院，天津 300387；2.天津工業(yè)大學 天津市光電檢測技術重點實驗室，天津 300387；3.天津工業(yè)大學 電子與信息工程學院，天津 300387）

網絡與人們的生活息息相關，例如社交網絡、學術引用網絡和蛋白質-蛋白質相互作用網絡。網絡表示學習又稱網絡嵌入，旨在通過捕獲拓撲結構和屬性信息來學習網絡節(jié)點的低維表示，是一種有效的網絡分析手段。它可以克服原始網絡表示在分析任務中遇到的許多困難，例如計算復雜度高、并行性低和機器學習方法不適用[1]。網絡嵌入在各種后續(xù)網絡處理任務如節(jié)點分類[2]、節(jié)點聚類[3]、鏈接預測[4]和可視化[5]等方面表現優(yōu)異，已引起了學者濃厚的興趣。

根據保留網絡的信息類型，可以將已有的網絡嵌入算法分為3類：結構和屬性保留算法、輔助信息保留算法和高級信息保留算法。結構和屬性保留算法[6]旨在保留網絡中節(jié)點之間的結構信息和在嵌入過程中影響網絡發(fā)展的屬性信息。輔助信息保留算法通過融合豐富的輔助信息（例如引文網絡中的節(jié)點內容或標簽，社交網絡中的節(jié)點和邊屬性以及異構網絡中的節(jié)點類型[7]）來獲得更好的節(jié)點表示。高級信息保留算法[8]是指在特定任務中利用監(jiān)督或偽監(jiān)督信息。

根據網絡嵌入中捕獲信息的方式，可以將已有的網絡嵌入算法大致分為3類：基于隨機游走的算法[9-11]、基于矩陣分解的算法[12-15]和基于深度學習的算法[16-19]?；陔S機游走的算法在網絡上執(zhí)行截斷的隨機游走，并生成隨機游走路徑以保持節(jié)點之間的鄰接關系。例如DeepWalk[9]對網絡節(jié)點執(zhí)行隨機游走，發(fā)現隨機游走序列中出現的節(jié)點分布與自然語言單詞的分布相似。因此，該算法擴展了經典的單詞表示模型Skip-Gram[10]以學習節(jié)點表示。Node2vec[11]改進了DeepWalk中隨機游走的生成方法，使生成的隨機游走序列可以反映深度優(yōu)先采樣（DFS）和廣度優(yōu)先采樣（BFS）的特征，從而改善網絡的嵌入效果?；诰仃嚪纸獾乃惴▽⒕W絡中的信息轉換為矩陣形式，并對矩陣進行分解以獲得節(jié)點表示。例如TADW[12]、HOPE[13]和M-NMF[14]等算法試圖通過分解矩陣（捕獲了網絡中各種信息）來學習節(jié)點表示。這些捕獲的信息包括結構關系、文本內容以及各階鄰近度。近年來，許多算法包括LINE[15]、PTE[6]、DeepWalk[9]和Node2vec[11]均被證明等效于矩陣分解。隨著深度學習的迅猛發(fā)展，基于深度學習的網絡表示方法被提出。該方式主要利用非線性函數學習模型以獲得節(jié)點表示。文獻[16]提出的GCN將深度學習中的卷積操作應用到非歐結構的網絡數據上，以此來融合目標節(jié)點周圍鄰居節(jié)點的信息。文獻[17]提出的GAT方法在GCN的基礎上使用注意機制確定節(jié)點鄰域的權重，提高了聚合特征信息的準確性。在GAT的基礎上文獻[18]提出了關聯性圖注意力網絡，整合了圖卷積神經網絡（GCN）+注意力機制+關聯性的優(yōu)點。文獻[19]提出的LC-GNN利用未連接但具有相同標簽的節(jié)點對擴大了GCN和GAT這一類方法中節(jié)點的接受范圍。盡管基于深度學習的算法提供了端到端的學習解決方案，但它們具有較長的訓練時間和復雜的參數。

上述方法主要集中在保持結構關系（基于隨機游走的算法）或最小化重構誤差（基于矩陣分解的算法和基于深度學習的算法）兩方面。但是，現存的這些算法中仍然存在一個巨大的挑戰(zhàn)，那就是作為網絡結構重要特征的社區(qū)結構信息[20]通常被忽略了。社區(qū)結構在網絡中占有極其重要的位置，因為它從更高的層次揭示了網絡的組織結構和功能組件[21]，因此，捕獲原始網絡中的社區(qū)結構是嵌入學習中的關鍵步驟。

本文設計了一種融合社區(qū)結構信息的網絡嵌入（CINE）模型，具體來說，將可以揭示網絡組織結構的模塊度[21]思想納入基于矩陣分解的模型中，以提取社區(qū)結構信息。與同樣研究社區(qū)結構信息的Wang等[21]提出的算法相比，本文所提算法的主要創(chuàng)新點在于不僅僅捕獲了社區(qū)結構信息，還將低階網絡結構信息和節(jié)點屬性信息同時融合到了節(jié)點表示中，設計了一個整體的目標函數，并使用共軛梯度算法進行優(yōu)化。最后在3個基準數據集上用獲得的嵌入結果進行節(jié)點分類，通過鏈路預測實驗來評估所學節(jié)點低維表示的有效性。

1 CINE模型

1.1 CINE模型構建

CINE的模型框架如圖1所示。首先將捕獲了節(jié)點之間的一階和二階鄰近性的相似度矩陣分解為不同的組成部分；然后使用模塊化約束以挖掘網絡中的社區(qū)結構；最后聯合優(yōu)化，獲得低維的節(jié)點向量表示。

圖1 CINE模型框圖Fig.1 Diagram of CINE mode

（1）建模結構和屬性信息。借鑒TADW的建模思想，在矩陣分解的基礎上利用歸納完成矩陣的思想將文本特征合并到節(jié)點表示中。計算公式為：

式中：S為捕獲節(jié)點之間一階和二階鄰近性的相似度矩陣；W為節(jié)點的低維表示矩陣；Y為輔助矩陣；X為節(jié)點文本特征矩陣；λ為控制參數。TADW是一種基于矩陣分解的模型，通過合并屬性特征來獲得更好的網絡表示。

（2）建模社區(qū)結構信息。首先引入社區(qū)結構這個概念，在參考基于模塊度最大化[22]的社區(qū)檢測方法后對社區(qū)結構進行建模。模塊度的定義為：

式中：ki為節(jié)點i的度；如果節(jié)點i屬于第1個社區(qū)則hi＝1，否則hi＝－1；如果邊是隨機放置的，則kikj/2e為節(jié)點i和j之間的期望邊數。因此，直觀地說，模塊度本質是度量落在社區(qū)內的邊數與隨機放置邊的等價網絡中的期望邊數之間的差。模塊度矩陣定義為B∈Rn×n，其中Bij=Aij-（kikj/2e），使得Q=hTBh/4e，h=[hi]∈Rn表示社區(qū)指示向量，如果大于兩個社區(qū)則為社區(qū)表示矩陣H，式（2）化簡為：

式中：tr（X）為矩陣X的跡；A為鄰接矩陣；B∈Rn×n為模塊度矩陣；H∈Rn×k為社區(qū)指示矩陣。H的約束是確保只有一個元素在每一行中為1，其余為0。因此，每個節(jié)點僅屬于一個社區(qū)。

結合式（1）、式（3）將社區(qū)結構引入屬性網絡的表示中，得到：

式中：α和β為用于調整相應項貢獻的參數；C∈Rk×d為社區(qū)表示矩陣。矩陣C的第r行（Cr）為社區(qū)r的表示。假設節(jié)點i屬于社區(qū)r，則節(jié)點i的表示類似于社區(qū)r的表示。相反，如果節(jié)點i不屬于社區(qū)r，則該節(jié)點的表示向量與社區(qū)r的表示向量正交。根據此假設，本文所提模型期望WTCT的結果可以近似社區(qū)指標矩陣H，這樣保證了同一社區(qū)的節(jié)點更相似，從而在節(jié)點表示學習中獲取了社區(qū)結構。

式（4）中，第1項捕獲網絡中節(jié)點級別鄰近度；第2項通過矩陣分解將社區(qū)結構信息吸收到低維矩陣W中；模塊度項約束社區(qū)指標矩陣H來更好地捕獲網絡中的社區(qū)分布；最后1項通過調整參數λ1來防止過擬合。

整個CINE模型具有2個優(yōu)點：首先CINE能夠捕獲社區(qū)結構信息，以使所學的嵌入表示更好地表達原始網絡的組織結構和功能組件；其次是將社區(qū)結構信息、節(jié)點級別的鄰近度和屬性信息融合到一個目標函數中進行聯合優(yōu)化，這樣學習的節(jié)點表示更加完善。

1.2 CINE模型優(yōu)化

首先將目標函數方程（4）簡化為：

雖然f（W，H，Y，C）相對于W、H、Y和C同時來看是非凸函數，但在采用交替迭代方法后，即W、H、Y和C中的3個變量固定，相對于僅剩的一個變量而言轉化成為該變量的凸函數。此時，整體目標函數的非凸問題就可以轉化為關于4個變量的4個凸函數的求解問題，正確初始化W、H、Y和C后再采用共軛梯度下降法尋找出最優(yōu)解即可。

（1）H步：給定W、C、Y，求解目標中H的子問題。目標函數可以寫成：

式中：H為社區(qū)指標矩陣，由于約束項，使等式（6）的優(yōu)化成為一個非確定性多項式（NP）難題。參照MNMF[14]，放松對HTH的約束為HTH=I后可解決上述問題。最后加入正則化系數λ2將式（6）轉換為：

式中：λ2>0應該足夠大以確保滿足正交性，本文在實驗中將λ2設置為103。

（2）Y步：給定W、H、C，求解式（5）中Y的子問題。目標函數可以寫成：

（3）C步：給定W、H、Y，求解式（5）中C的子問題。目標函數可以寫成：

（4）W步：給定H、Y、C，求解式（5）中W的子問題。目標函數可以寫成：

（5）然后，使用共軛梯度算法分別進行迭代優(yōu)化。算法流程如下。

輸入：網絡G={V，E，X}，維度d，社區(qū)的數量k，參數α，β，λ。

隨機初始化W、Y、H、C并且計算S和B。

H-步：給定W、Y、C使用共軛梯度下降法針對式（7）優(yōu)化H。

Y-步：給定W、H、C使用共軛梯度下降法針對式（8）優(yōu)化Y。

C-步：給定W、H、Y使用共軛梯度下降法針對式（9)優(yōu)化C。

W-步：給定Y、H、C使用共軛梯度下降法針對式（10）優(yōu)化W。

輸出：直到目標函數收斂，輸出節(jié)點表示矩陣W。

1.3 復雜度分析

本節(jié)主要分析CINE算法的時間復雜度。根據式（6）—式（9）中的更新規(guī)則計算時間復雜度，分別需要O（n2k+ndk），O（nnz（S）+ndf+nf2），O（nd2+ndk）和O（nd）。其中，nnz（·）表示非零條目的數量。由于d，k，f<

2 實驗驗證

本文采用Cora、Citeseer和Wiki等3個公開網絡數據集驗證CINE在節(jié)點分類、鏈接預測和可視化任務中的表現。Cora和Citeseer是2個引文網絡，網絡中不同主題的文檔作為節(jié)點，文檔之間的引用作為邊緣。Wiki是一種語言網絡，其中文檔之間的超鏈接充當邊緣。對于所有數據集，文檔的內容對應于節(jié)點特征，這些節(jié)點特征由相應文檔的詞袋表示。表1給出了3個數據集的詳細信息。

表1 數據集詳細信息Tab.1 Details of dataset

為了證明本文所提出CINE算法的有效性，將其與DeepWalk[9]、Node2vec[11]、GraRep[23]、LINE[15]、HOPE[13]、TADW[12]等6種經典的網絡嵌入方法進行比較。其中，DeepWalk[9]為基于隨機游走的網絡嵌入方法，使用截斷的隨機游走保留節(jié)點上下文的結構信息；Node2vec[11]為基于偏向隨機游走的網絡嵌入方法，使用深度優(yōu)先采樣（DFS）和廣度優(yōu)先采樣（BFS）圖搜索來獲得比DeepWalk更高的質量和更多的信息表示；GraRep[23]為基于矩陣分解的網絡嵌入方法，使用奇異值（SVD）分解來保留全局結構信息；LINE[15]為適用于大規(guī)模網絡數據的網絡嵌入方法，使用負采樣來優(yōu)化目標函數，保留了節(jié)點之間的一階和二階接近度；HOPE[13]為基于矩陣分解的網絡嵌入方法，使用SVD分解相似矩陣而不是鄰接矩陣來保留高階接近度；TADW[12]為基于矩陣分解的網絡嵌入方法，使用歸納完成矩陣保留節(jié)點的文本特征。

實驗過程中比較方法的參數默認使用原作者的設置，本文實驗所用數據集及對比方法復現調用OpenNE開源庫，鏈接如下：https：//github.com/thunlp/OpenNE。對于CINE，設置α，β∈{0.01，0.05，0.1，0.5，1}和λ1∈{0.1，0.2，0.3，0.5，0.6，0.7，0.8，0.9，1}。與此同時，本文使用SVD對屬性信息X進行預處理，將其簡化為一個200維矩陣。為了公平起見，所有嵌入方法的表示維度統(tǒng)一設置為128。

2.1 節(jié)點分類

隨機抽取一定百分比的標記節(jié)點作為訓練集，其余作為測試集，樣本訓練集的比例占數據集的10%至90%；采用LIBLINEAR軟件包[24]訓練分類器，進行了10次實驗，所有算法都采用微平均（Micro-F1）和宏平均（Macro-F1）評估指標，具體結果如表2—表4所示。

表2 Cora數據集上的分類結果Tab.2 Classification results on Cora dataset

表3 Wiki數據集上的分類結果Tab.3 Classification results on Wiki dataset

由表2—表4可以看出，CINE的分類性能始終高于其他基線方法。CINE和TADW這2種方法優(yōu)于僅捕獲網絡結構信息的其他傳統(tǒng)嵌入方法，這表明在網絡中融合屬性信息可以更好地學習節(jié)點表示。與此同時，在3個數據集上CINE的性能都顯著高于TADW，充分證明捕獲社區(qū)結構可以更好地表達網絡的結構信息，并有助于分類任務。

表4 Citeseer數據集上的分類結果Tab.4 Classification results on Citeseer dataset

2.2 鏈路預測

采用網絡10%的邊緣作為測試集，剩下90%的邊緣作為訓練集。重復實驗10次以獲得平均結果，并采用ROC曲線下面積（AUROC）為評價指標，如圖2所示。

由圖2可知，CINE在3個數據集上均達到了最好的效果。從Cora數據集的AUROC得分來看，與Node2vec、DeepWalk和TADW相比，CINE分別得到了1.165、1.144和1.059倍的相對提高。這些結果驗證了學習網絡節(jié)點表示時捕獲社區(qū)結構的必要性。

圖2 鏈路預測實驗結果Fig.2 Experiment results of link prediction

2.3 可視化

采用t-SNE[25]包對CINE和典型基線方法執(zhí)行可視化任務，利用結果進行更直觀地比較分析。由于3個數據集效果類似，本文只展示了Cora數據集上的可視化結果，如圖3所示。圖3中，不同的顏色代表不同的類別。

由圖3可以看出，與DeepWalk相比，TADW和CINE可以更好地分離不同類別的數據點，這表明融合屬性特征使得節(jié)點學習到的網絡信息更加豐富。與TADW相比，CINE中相同類別的數據點彼此靠近，不同類別的邊界線更加明顯，這證明捕獲社區(qū)結構后節(jié)點表示可以更好地表達網絡的組織結構信息。

圖3 可視化實驗結果Fig.3 Visualized experimental results

3 結論

本文提出了一種新穎的融合社區(qū)結構信息的網絡嵌入模型（CINE）。在嵌入過程中，CINE使用矩陣分解來融合節(jié)點的1階、2階節(jié)點鄰近度信息以及屬性信息，在模塊度的指導下捕獲社區(qū)結構，設計一個統(tǒng)一的目標函數，采用共軛梯度算法對其進行優(yōu)化，并在Cora、Wiki、Citeseer3個真實數據集上驗證了所提出模型的有效性。結果表明：

（1）在分類任務中，CINE采用90%訓練集在3個數據集上的Micro-F1分數分別達到0.900 2、0.840 2、0.761 9，優(yōu)于所有對比算法；

（2）在Cora數據集的鏈路預測任務中，CINE的AUROC得分比Node2vec、DeepWalk和TADW分別提高了1.165、1.144和1.059倍；

（3）CINE算法在保留了從更高層次揭示網絡組織結構和功能組件的社區(qū)結構信息后，所學習的節(jié)點表示可以更好地完成后續(xù)各種網絡分析任務。