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

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

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

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

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

上述方法主要集中在保持結(jié)構(gòu)關(guān)系（基于隨機(jī)游走的算法）或最小化重構(gòu)誤差（基于矩陣分解的算法和基于深度學(xué)習(xí)的算法）兩方面。但是，現(xiàn)存的這些算法中仍然存在一個(gè)巨大的挑戰(zhàn)，那就是作為網(wǎng)絡(luò)結(jié)構(gòu)重要特征的社區(qū)結(jié)構(gòu)信息[20]通常被忽略了。社區(qū)結(jié)構(gòu)在網(wǎng)絡(luò)中占有極其重要的位置，因?yàn)樗鼜母叩膶哟谓沂玖司W(wǎng)絡(luò)的組織結(jié)構(gòu)和功能組件[21]，因此，捕獲原始網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)是嵌入學(xué)習(xí)中的關(guān)鍵步驟。

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

1 CINE模型

1.1 CINE模型構(gòu)建

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

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

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

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

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

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

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

結(jié)合式（1）、式（3）將社區(qū)結(jié)構(gòu)引入屬性網(wǎng)絡(luò)的表示中，得到：

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

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

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

1.2 CINE模型優(yōu)化

首先將目標(biāo)函數(shù)方程（4）簡化為：

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

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

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

式中：λ2>0應(yīng)該足夠大以確保滿足正交性，本文在實(shí)驗(yàn)中將λ2設(shè)置為103。

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

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

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

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

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

隨機(jī)初始化W、Y、H、C并且計(jì)算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。

輸出：直到目標(biāo)函數(shù)收斂，輸出節(jié)點(diǎn)表示矩陣W。

1.3 復(fù)雜度分析

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

2 實(shí)驗(yàn)驗(yàn)證

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

表1 數(shù)據(jù)集詳細(xì)信息Tab.1 Details of dataset

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

實(shí)驗(yàn)過程中比較方法的參數(shù)默認(rèn)使用原作者的設(shè)置，本文實(shí)驗(yàn)所用數(shù)據(jù)集及對比方法復(fù)現(xiàn)調(diào)用OpenNE開源庫，鏈接如下：https：//github.com/thunlp/OpenNE。對于CINE，設(shè)置α，β∈{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}。與此同時(shí)，本文使用SVD對屬性信息X進(jìn)行預(yù)處理，將其簡化為一個(gè)200維矩陣。為了公平起見，所有嵌入方法的表示維度統(tǒng)一設(shè)置為128。

2.1 節(jié)點(diǎn)分類

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

表2 Cora數(shù)據(jù)集上的分類結(jié)果Tab.2 Classification results on Cora dataset

表3 Wiki數(shù)據(jù)集上的分類結(jié)果Tab.3 Classification results on Wiki dataset

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

表4 Citeseer數(shù)據(jù)集上的分類結(jié)果Tab.4 Classification results on Citeseer dataset

2.2 鏈路預(yù)測

采用網(wǎng)絡(luò)10%的邊緣作為測試集，剩下90%的邊緣作為訓(xùn)練集。重復(fù)實(shí)驗(yàn)10次以獲得平均結(jié)果，并采用ROC曲線下面積（AUROC）為評價(jià)指標(biāo)，如圖2所示。

由圖2可知，CINE在3個(gè)數(shù)據(jù)集上均達(dá)到了最好的效果。從Cora數(shù)據(jù)集的AUROC得分來看，與Node2vec、DeepWalk和TADW相比，CINE分別得到了1.165、1.144和1.059倍的相對提高。這些結(jié)果驗(yàn)證了學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)表示時(shí)捕獲社區(qū)結(jié)構(gòu)的必要性。

圖2 鏈路預(yù)測實(shí)驗(yàn)結(jié)果Fig.2 Experiment results of link prediction

2.3 可視化

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

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

圖3 可視化實(shí)驗(yàn)結(jié)果Fig.3 Visualized experimental results

3 結(jié)論

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

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

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

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