網(wǎng)絡(luò)表示學(xué)習(xí)方法研究綜述

孫金清，周 慧，趙中英

(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

信息網(wǎng)絡(luò)是最為常見(jiàn)的一種信息載體和形式，隨著互聯(lián)網(wǎng)的不斷發(fā)展，以社交媒體網(wǎng)絡(luò)、移動(dòng)通信網(wǎng)絡(luò)、維基百科等為代表的信息網(wǎng)絡(luò)已成為日常生活中不可或缺的一部分。人類(lèi)的各種交互行為產(chǎn)生了極為豐富的信息網(wǎng)絡(luò)數(shù)據(jù)。與此同時(shí)，面向信息網(wǎng)絡(luò)的數(shù)據(jù)挖掘也逐漸得到學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注。然而隨著數(shù)據(jù)的規(guī)模逐漸增大和網(wǎng)絡(luò)的復(fù)雜性的提升，使用傳統(tǒng)的高維稀疏數(shù)據(jù)的編碼方式難以對(duì)網(wǎng)絡(luò)進(jìn)行處理。因此，如何恰當(dāng)?shù)谋硎揪W(wǎng)絡(luò)中的信息是研究人員首先要面對(duì)的重要問(wèn)題。

網(wǎng)絡(luò)表示學(xué)習(xí)(network representation learning)，又被稱(chēng)之為網(wǎng)絡(luò)嵌入(network embedding)，是銜接網(wǎng)絡(luò)中原始數(shù)據(jù)和網(wǎng)絡(luò)應(yīng)用任務(wù)的橋梁，旨在將網(wǎng)絡(luò)中的組件(節(jié)點(diǎn)、邊或子圖等)表示成向量形式，同時(shí)最大程度地保留組件在原網(wǎng)絡(luò)中的信息和屬性。傳統(tǒng)的網(wǎng)絡(luò)表示一般使用高維的稀疏向量，網(wǎng)絡(luò)表示學(xué)習(xí)旨在將網(wǎng)絡(luò)中的復(fù)雜關(guān)系以更加直觀、更加高效的方式對(duì)原始網(wǎng)絡(luò)空間中的節(jié)點(diǎn)關(guān)系進(jìn)行還原。近年來(lái)，研究者通過(guò)大量研究實(shí)驗(yàn)不斷探索網(wǎng)絡(luò)中組件的高效表示方法，使得學(xué)得的低維表征向量能夠被機(jī)器學(xué)習(xí)算法處理，復(fù)雜的網(wǎng)絡(luò)分析任務(wù)(節(jié)點(diǎn)分類(lèi)[1-2]、鏈接預(yù)測(cè)[3-4]、社區(qū)發(fā)現(xiàn)[5-6]和推薦[7-8]等)得以高效地進(jìn)行。例如，在基于位置的社交網(wǎng)絡(luò)中，Luan等[9]使用張量分解等方法對(duì)網(wǎng)絡(luò)中用戶的行為進(jìn)行建模，根據(jù)用戶偏好進(jìn)行推薦[10]；在電子商務(wù)網(wǎng)絡(luò)中，Liu等[11]提出欠采樣高斯矩陣等方法機(jī)器學(xué)習(xí)方法對(duì)欺詐行為建模，針對(duì)欺詐樣本不均衡[12]、欺詐行為的概念飄逸[13]等進(jìn)行了研究[14]。

為有效地掌握網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域的學(xué)術(shù)思路和動(dòng)態(tài)，本研究對(duì)近年來(lái)面向同構(gòu)網(wǎng)絡(luò)和屬性網(wǎng)絡(luò)的代表性的表示學(xué)習(xí)算法進(jìn)行分類(lèi)介紹和比較。特別地，對(duì)于同構(gòu)網(wǎng)絡(luò)，根據(jù)算法所應(yīng)用的理論基礎(chǔ)進(jìn)行分類(lèi)介紹。對(duì)于屬性網(wǎng)絡(luò)，根據(jù)算法所結(jié)合的屬性信息種類(lèi)進(jìn)行分類(lèi)介紹。此外，對(duì)比分析了各類(lèi)別下的網(wǎng)絡(luò)表示學(xué)習(xí)算法的時(shí)間復(fù)雜度和優(yōu)缺點(diǎn)。

1 問(wèn)題定義

本節(jié)給出網(wǎng)絡(luò)和屬性網(wǎng)絡(luò)形式化定義，并對(duì)同構(gòu)網(wǎng)絡(luò)和屬性網(wǎng)絡(luò)上的表示學(xué)習(xí)進(jìn)行問(wèn)題描述。

定義1網(wǎng)絡(luò)[15]。網(wǎng)絡(luò)是對(duì)關(guān)系型數(shù)據(jù)的刻畫(huà)，主要由節(jié)點(diǎn)和和連接這些節(jié)點(diǎn)的邊構(gòu)成，表示諸多對(duì)象及其相互聯(lián)系，符號(hào)表示為G(V,E)，其中V表示網(wǎng)絡(luò)G中的節(jié)點(diǎn)集，E表示邊集。

問(wèn)題1同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)[17]。給定同構(gòu)網(wǎng)絡(luò)G(V,E)，目標(biāo)是為網(wǎng)絡(luò)中的節(jié)點(diǎn)v∈V(或邊、子圖等)學(xué)習(xí)映射關(guān)系f:v→rv∈Rd，其中rv為節(jié)點(diǎn)v學(xué)得的低維稠密向量，d是表征向量的維度，d?|V|，轉(zhuǎn)換函數(shù)f用于捕獲原網(wǎng)絡(luò)中節(jié)點(diǎn)之間的拓?fù)潢P(guān)聯(lián)關(guān)系。

問(wèn)題2屬性網(wǎng)絡(luò)表示學(xué)習(xí)[16-17]。給定屬性網(wǎng)絡(luò)G(V,E,A)，目標(biāo)是為屬性網(wǎng)絡(luò)中的節(jié)點(diǎn)v∈V(或邊、子圖等)學(xué)習(xí)映射關(guān)系f:v→rv∈Rd，其中rv是為節(jié)點(diǎn)v學(xué)得的低維稠密向量，d是表征向量的維度，d?|V|，轉(zhuǎn)換函數(shù)f用于捕獲原網(wǎng)絡(luò)中復(fù)雜的拓?fù)浜蛯傩躁P(guān)聯(lián)關(guān)系。

在介紹算法分類(lèi)之前，首先列出論文中用到的主要符號(hào)以及其含義如表1所示。

表1 論文中的常用符號(hào)

2 同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)

本節(jié)介紹基于網(wǎng)絡(luò)拓?fù)湫畔⒌耐瑯?gòu)表示學(xué)習(xí)算法。根據(jù)理論基礎(chǔ)，將代表性算法分為基于非線性流形學(xué)習(xí)、基于自定義損失函數(shù)、基于簡(jiǎn)單神經(jīng)網(wǎng)絡(luò)、基于矩陣分解以及基于深層神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)表示學(xué)習(xí)算法等5類(lèi)。

2.1 基于非線性流形學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)算法

非線性流形學(xué)習(xí)常用于對(duì)高維的流形數(shù)據(jù)進(jìn)行非線性降維，代表性算法有Isomap(isometric feature mapping)[18]、LLE(locally linear embedding)[19]和LE(laplacian eigenmaps)[20]等。這些算法通過(guò)構(gòu)建鄰域圖來(lái)發(fā)現(xiàn)高維空間中的數(shù)據(jù)的低維結(jié)構(gòu)，并得到對(duì)應(yīng)的低維向量表示，屬于網(wǎng)絡(luò)表示學(xué)習(xí)的早期成果。下面對(duì)這些代表性算法分別進(jìn)行介紹。

在Isomap算法[19]中，設(shè)計(jì)了能夠衡量高維流形數(shù)據(jù)之間的測(cè)地距離的有效方法。相比歐氏距離，測(cè)地距離更接近非線性數(shù)據(jù)之間的實(shí)際距離。如圖1所示，該算法首先通過(guò)計(jì)算原數(shù)據(jù)節(jié)點(diǎn)間的歐式距離來(lái)建立鄰域連接圖，然后通過(guò)尋找鄰域圖上的兩點(diǎn)間的最短路徑(紅線)近似逼近測(cè)地距離(藍(lán)線)；接下來(lái)，基于數(shù)據(jù)點(diǎn)之間的測(cè)地距離構(gòu)建距離矩陣；最后通過(guò)多維標(biāo)度(multidimensional scaling,MDS)方法根據(jù)距離矩陣對(duì)數(shù)據(jù)進(jìn)行降維。

圖1 Isomap算法節(jié)點(diǎn)距離計(jì)算示例[19]

LLE算法[19]首先假設(shè)非線性數(shù)據(jù)在局部范圍內(nèi)存在線性關(guān)系，那么每個(gè)數(shù)據(jù)節(jié)點(diǎn)可表示成其鄰居節(jié)點(diǎn)的加權(quán)組合。同時(shí)，該算法又假設(shè)這些高維數(shù)據(jù)映射到低維空間后仍能夠保持原數(shù)據(jù)空間上的局部線性關(guān)系。利用這些假設(shè)，數(shù)據(jù)在高維和低維空間上的聯(lián)系能夠被建立起來(lái)。最后，通過(guò)對(duì)關(guān)系矩陣求解特征向量來(lái)獲取數(shù)據(jù)的低維表示。隨后，科研人員針對(duì)局部線性關(guān)系的構(gòu)建方法提出了對(duì)LLE算法的改進(jìn)，相關(guān)算法有LE[20],Hessian LLE[21]等。

LE算法[20]同樣根據(jù)數(shù)據(jù)節(jié)點(diǎn)在高維空間上的鄰近關(guān)系來(lái)進(jìn)行低維映射，核心思想是保持相鄰節(jié)點(diǎn)在低維表示空間中的鄰近關(guān)系。數(shù)據(jù)的低維表示是對(duì)應(yīng)的拉普拉斯矩陣的前d個(gè)最小特征值所對(duì)應(yīng)的特征向量。由于以上介紹的算法都只能處理無(wú)向網(wǎng)絡(luò)，DGE(directed graph embedding)算法[22]基于LE算法進(jìn)行了改進(jìn)，采用基于隨機(jī)游走的方法為不同點(diǎn)加入不同的權(quán)重信息，使之能夠處理有向和無(wú)向兩種類(lèi)型的網(wǎng)絡(luò)。

本節(jié)中所介紹的算法僅保留了節(jié)點(diǎn)的一階相似度，無(wú)法衡量全局性的數(shù)據(jù)特征，而且計(jì)算時(shí)間復(fù)雜度較高，不能擴(kuò)展到大規(guī)模網(wǎng)絡(luò)上。

2.2 基于自定義損失函數(shù)的網(wǎng)絡(luò)表示學(xué)習(xí)算法

LINE算法[23]通過(guò)設(shè)計(jì)自定義的損失函數(shù)來(lái)建模網(wǎng)絡(luò)中節(jié)點(diǎn)的一階和二階相似度。其中一階相似性指的是相連節(jié)點(diǎn)間的相似度，對(duì)應(yīng)的目標(biāo)函數(shù)如式(1)所示；二階相似性指的是共享多個(gè)相同鄰居的節(jié)點(diǎn)之間的相似度，對(duì)應(yīng)的目標(biāo)函數(shù)如式(2)所示。該算法使用隨機(jī)梯度下降法優(yōu)化目標(biāo)函數(shù)并更新節(jié)點(diǎn)的向量表示。

(1)

(2)

2.3 基于簡(jiǎn)單神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)表示學(xué)習(xí)算法

簡(jiǎn)單神經(jīng)網(wǎng)絡(luò)在網(wǎng)絡(luò)表示學(xué)習(xí)中的應(yīng)用主要受到Word2vec[24]詞向量訓(xùn)練模型的啟發(fā)。DeepWalk算法[25]首次將詞向量訓(xùn)練模型引入到網(wǎng)絡(luò)中，用于學(xué)習(xí)網(wǎng)絡(luò)中節(jié)點(diǎn)的向量表示；該算法采用截?cái)嚯S機(jī)游走的方式為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)構(gòu)建鄰域節(jié)點(diǎn)，然后使用詞向量訓(xùn)練模型Skip-Gram[24]進(jìn)行訓(xùn)練，最大化鄰域節(jié)點(diǎn)在目標(biāo)節(jié)點(diǎn)周?chē)霈F(xiàn)的概率，由此得到每個(gè)節(jié)點(diǎn)的低維向量表示。

Grover等[26]進(jìn)一步對(duì)DeepWalk算法的隨機(jī)游走方式進(jìn)行了改進(jìn)，設(shè)計(jì)了node2vec算法，通過(guò)引入兩個(gè)參數(shù)p和q來(lái)控制隨機(jī)游走的方向，進(jìn)而能夠捕獲更加豐富的網(wǎng)絡(luò)結(jié)構(gòu)信息。值得注意的是，當(dāng)p=q=1時(shí)，node2vec等同于DeepWalk算法。此外，在struc2vec算法[27]中，為了捕獲節(jié)點(diǎn)間的全局結(jié)構(gòu)相似性，作者設(shè)計(jì)了多層加權(quán)圖來(lái)選取更具代表性的臨域節(jié)點(diǎn)。

NBNE(neighbor based node embeddings)算法[28]和ProxEmbed算法[29]也運(yùn)用了隨機(jī)游走與神經(jīng)網(wǎng)絡(luò)相結(jié)合的思想對(duì)網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)?？偟膩?lái)說(shuō)，基于簡(jiǎn)單神經(jīng)網(wǎng)絡(luò)方法的優(yōu)點(diǎn)是時(shí)間復(fù)雜度低，但此類(lèi)算法缺少明確的目標(biāo)函數(shù)，同時(shí)通過(guò)特定步長(zhǎng)的隨機(jī)游走并不能夠充分捕獲復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)信息[23]。

2.4 基于矩陣分解的網(wǎng)絡(luò)表示學(xué)習(xí)算法

矩陣分解指的是將一個(gè)矩陣分解成多個(gè)矩陣，分解后的矩陣能夠以低于原矩陣的維度來(lái)近似地保留原矩陣的特征，這種理論被廣泛用于網(wǎng)絡(luò)表示學(xué)習(xí)任務(wù)中。

劉知遠(yuǎn)等[30]首先證明了DeepWalk算法[25]等同于對(duì)網(wǎng)絡(luò)轉(zhuǎn)移概率矩陣進(jìn)行矩陣分解。由于以往的算法局限于捕獲節(jié)點(diǎn)間的低階相似度信息或直接建模高階相似性，忽略了從低階到高階的過(guò)程中所蘊(yùn)藏的拓?fù)湫畔?。為解決以上問(wèn)題，GraRep算法[31]被提出，分別對(duì)不同k步范圍內(nèi)的網(wǎng)絡(luò)拓?fù)湫畔⑦M(jìn)行奇異值分解，并將每一步得到的向量表示相連，由此得到的節(jié)點(diǎn)表示能夠更加精確地反映真實(shí)的網(wǎng)絡(luò)結(jié)構(gòu)信息，但是該算法的時(shí)間復(fù)雜度較大，僅適用于規(guī)模較小的網(wǎng)絡(luò)。

Yang等[32]指出在網(wǎng)絡(luò)表示學(xué)習(xí)的過(guò)程中考慮節(jié)點(diǎn)的高階相似度信息是非常重要的，但同時(shí)也會(huì)增加模型的復(fù)雜度，無(wú)法適用于大規(guī)模網(wǎng)絡(luò)；為解決上述的問(wèn)題，作者提出了NEU(network embedding update)算法，在不增加算法復(fù)雜度的同時(shí)，通過(guò)在原有表示學(xué)習(xí)算法基礎(chǔ)上添加附加項(xiàng)，來(lái)快速生成能夠捕獲高階信息的向量近似值。

2.5 基于深層神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)表示學(xué)習(xí)算法

深層神經(jīng)網(wǎng)絡(luò)在不同的領(lǐng)域都有著廣泛的應(yīng)用，而且在學(xué)習(xí)不同層次的數(shù)據(jù)特征方面已經(jīng)取得了較好的研究成果[33]。在網(wǎng)絡(luò)表示學(xué)習(xí)方向上，學(xué)者運(yùn)用深層神經(jīng)網(wǎng)絡(luò)來(lái)捕獲網(wǎng)絡(luò)中復(fù)雜的非線性信息。

Jacobs等[34]提出一種基于深層神經(jīng)網(wǎng)絡(luò)的半監(jiān)督模型SEANO，為具有局部標(biāo)簽和屬性信息的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行向量表示。該模型通過(guò)深度學(xué)習(xí)框架將節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)信息、屬性信息相關(guān)聯(lián)。

Cao等[35]指出基于奇異值分解的網(wǎng)絡(luò)表示學(xué)習(xí)算法局限于從線性關(guān)系中推出節(jié)點(diǎn)的向量表示，無(wú)法捕獲到網(wǎng)絡(luò)中存在的復(fù)雜非線性關(guān)系，為解決此問(wèn)題提出DNGR模型(如圖2所示)，該模型首先采用帶權(quán)隨機(jī)游走方法來(lái)捕獲網(wǎng)絡(luò)結(jié)構(gòu)信息，并生成概率共現(xiàn)矩陣；然后在此基礎(chǔ)上計(jì)算得到點(diǎn)互信息矩陣；最后采用SDAE(dtacked denosing autoencoders)算法[36]對(duì)向量進(jìn)行分層學(xué)習(xí)并降維，最終得到網(wǎng)絡(luò)中節(jié)點(diǎn)的向量表示。

圖2 DNGR模型框架[36]

SDNE(dtructural deep network embedding)模型[37]同樣基于深層神經(jīng)網(wǎng)絡(luò)模型，并采用半監(jiān)督方法進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)(如圖3所示)，該模型由兩部分組成：第一部分為無(wú)監(jiān)督的深層自編碼器，用于捕獲節(jié)點(diǎn)的鄰域結(jié)構(gòu)相似性，即節(jié)點(diǎn)的二階相似度；另一個(gè)部分建立在自編碼器的中間層，用于有監(jiān)督地建模節(jié)點(diǎn)的一階相似度。

圖3 SDNE模型框架[37]

2.6 同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)算法對(duì)比

本節(jié)中，對(duì)同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)算法進(jìn)行對(duì)比，包括算法的時(shí)間復(fù)雜度和優(yōu)缺點(diǎn)，總結(jié)如表2所示。

表2 同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)算法對(duì)比

3 屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法

第2節(jié)中介紹的網(wǎng)絡(luò)表示學(xué)習(xí)算法只是對(duì)節(jié)點(diǎn)在網(wǎng)絡(luò)中的拓?fù)潢P(guān)系和結(jié)構(gòu)相似性進(jìn)行編碼與計(jì)算?，F(xiàn)實(shí)生活中的網(wǎng)絡(luò)蘊(yùn)含著豐富的異構(gòu)信息，例如網(wǎng)絡(luò)中節(jié)點(diǎn)和邊上的標(biāo)簽信息以及文本特征信息等，若這些信息得到合理的運(yùn)用，會(huì)對(duì)網(wǎng)絡(luò)表示學(xué)習(xí)起到很好的輔助作用。本節(jié)中以異構(gòu)信息的種類(lèi)作為分類(lèi)依據(jù)，對(duì)現(xiàn)有的屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法進(jìn)行具體的描述，并分析這些算法的異同之處。

3.1 嵌入社區(qū)信息

現(xiàn)實(shí)網(wǎng)絡(luò)中蘊(yùn)藏著豐富的社區(qū)信息，尤其在社交網(wǎng)絡(luò)中最為常見(jiàn)，反映了網(wǎng)絡(luò)中的個(gè)體與其他個(gè)體之間的關(guān)聯(lián)關(guān)系，是對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行分析和研究的重要屬性，也是對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)交互關(guān)系預(yù)測(cè)的重要依據(jù)。

M-NMF(modularized nonegative matrix factorization)算法[38]分別從微觀和宏觀的角度學(xué)習(xí)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行向量表示，模型同時(shí)考慮了節(jié)點(diǎn)之間的相似度以及節(jié)點(diǎn)所屬的社區(qū)信息。微觀層面上，算法計(jì)算節(jié)點(diǎn)的一階和二階相似度；宏觀層面上，算法運(yùn)用基于模塊性最大化社區(qū)發(fā)現(xiàn)方法[39]來(lái)建模網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。M-NMF算法將這兩個(gè)方面進(jìn)行了融合，其目標(biāo)函數(shù)如式(3)所示，將目標(biāo)函數(shù)最小化即得到節(jié)點(diǎn)的向量表示。

(3)

除了利用社區(qū)信息對(duì)網(wǎng)絡(luò)中的單個(gè)節(jié)點(diǎn)進(jìn)行表示學(xué)習(xí)之外，還有算法可以直接對(duì)網(wǎng)絡(luò)中的整個(gè)社區(qū)進(jìn)行表示學(xué)習(xí)。ComE算法[40]首先運(yùn)用一些經(jīng)典的社區(qū)發(fā)現(xiàn)算法(如譜聚類(lèi))對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)，根據(jù)社區(qū)發(fā)現(xiàn)結(jié)果為每個(gè)節(jié)點(diǎn)進(jìn)行社區(qū)標(biāo)注；然后運(yùn)用經(jīng)典的表示學(xué)習(xí)算法(LINE、DeepWalk等)對(duì)節(jié)點(diǎn)進(jìn)行嵌入；最后把所屬相同社區(qū)的節(jié)點(diǎn)表示進(jìn)行聚合。模型中節(jié)點(diǎn)嵌入、社區(qū)發(fā)現(xiàn)以及社區(qū)嵌入之間相互促進(jìn)，節(jié)點(diǎn)的嵌入增強(qiáng)了社區(qū)發(fā)現(xiàn)并擬合出更好的社區(qū)嵌入。

3.2 嵌入標(biāo)簽信息

3.2.1 嵌入節(jié)點(diǎn)的標(biāo)簽信息

傳統(tǒng)的無(wú)監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)算法，雖然能夠?qū)W(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)涮匦赃M(jìn)行學(xué)習(xí)，但是對(duì)后續(xù)的一些機(jī)器學(xué)習(xí)任務(wù)缺乏區(qū)別性和針對(duì)性，進(jìn)而有學(xué)者提出了有監(jiān)督的表示學(xué)習(xí)方法，訓(xùn)練出具有針對(duì)性的表示向量。

在DeepWalk算法基礎(chǔ)上，MMDW(max-margin deepwalk)算法[30]添加了一個(gè)有監(jiān)督的最大間隔分類(lèi)器，利用節(jié)點(diǎn)的標(biāo)簽信息進(jìn)行有監(jiān)督學(xué)習(xí)。算法得到的節(jié)點(diǎn)向量中包含了網(wǎng)絡(luò)的拓?fù)湫畔⒑途哂袇^(qū)別性的標(biāo)簽信息，分類(lèi)效果優(yōu)于其他無(wú)監(jiān)督的算法。Li等[41]將截?cái)嚯S機(jī)游走的DeepWalk算法與分類(lèi)器相結(jié)合，提出了與MMDW算法相類(lèi)似的DDRW(discriminative deep random walk)算法。

另一方面，MVE(multi-view network embedding)算法[42]為節(jié)點(diǎn)收集并整合了網(wǎng)絡(luò)中多視角的相似度信息，將其用于表示學(xué)習(xí)。模型訓(xùn)練的過(guò)程如圖4所示，算法為節(jié)點(diǎn)在每個(gè)視角下都學(xué)得向量表示，并將學(xué)得的向量進(jìn)行整合。MCGE(multi-view clusting framework with grapg embedding)算法[33]同樣運(yùn)用了多視角的方式將表示學(xué)習(xí)運(yùn)用在聚類(lèi)任務(wù)中。

圖4 MVE模型框架[43]

3.2.2 嵌入邊的標(biāo)簽信息

TransNet模型[43]將轉(zhuǎn)換機(jī)制[44]和深度神經(jīng)網(wǎng)絡(luò)運(yùn)用到屬性網(wǎng)絡(luò)表示學(xué)習(xí)。該模型分為兩個(gè)模塊，如圖5所示，第一個(gè)模塊對(duì)邊的標(biāo)簽信息進(jìn)行自編碼；第二部分算法將邊的首尾節(jié)點(diǎn)和邊上的標(biāo)簽向量嵌入到相同的空間中，并使得U+1≈V′，運(yùn)用轉(zhuǎn)換機(jī)制并最小化鉸鏈損失函數(shù)。TransNet算法在社會(huì)關(guān)系提取的任務(wù)中表現(xiàn)出較好的結(jié)果。

圖5 TransNet模型框架[43]

3.3 嵌入文本信息

文本信息在網(wǎng)絡(luò)中普遍存在，例如：社交網(wǎng)絡(luò)中用戶寫(xiě)的動(dòng)態(tài)和發(fā)表的評(píng)論；合著網(wǎng)絡(luò)中作者的論文等文本信息。這些文本信息對(duì)于學(xué)習(xí)網(wǎng)絡(luò)豐富的向量特征具有重大意義。CANE模型[45]引入一種相互注意機(jī)制(mutual attention)，對(duì)節(jié)點(diǎn)的結(jié)構(gòu)信息和文本信息進(jìn)行了融合，從而考慮節(jié)點(diǎn)的上下文信息，在和不同的節(jié)點(diǎn)交互時(shí)具有不同的表示。

Yang等[46]證明DeepWalk算法計(jì)算過(guò)程實(shí)際上相當(dāng)于矩陣分解過(guò)程，同時(shí)注意到現(xiàn)實(shí)網(wǎng)絡(luò)中的節(jié)點(diǎn)蘊(yùn)含著豐富的文本信息，提出了TADW(text-associated deep walk)算法。算法利用矩陣分解的方法把節(jié)點(diǎn)的附加文本信息加入到矩陣分解的過(guò)程中。如圖6所示，矩陣M被分解成三個(gè)矩陣，其中T矩陣中包含了節(jié)點(diǎn)的文本特征。通過(guò)最小化損失函數(shù)(4)來(lái)更新W和H矩陣，最終使用W、H和T三個(gè)矩陣作為節(jié)點(diǎn)的低維向量表示。

圖6 TADW算法[46]

(4)

Huang等[16]提出AANE算法。根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，算法對(duì)節(jié)點(diǎn)間的一階相似度進(jìn)行建模，同時(shí)根據(jù)屬性信息生成節(jié)點(diǎn)的屬性關(guān)聯(lián)矩陣，使得節(jié)點(diǎn)向量與節(jié)點(diǎn)的屬性信息盡可能的匹配。算法將網(wǎng)絡(luò)中的屬性信息和拓?fù)湫畔⑦M(jìn)行高效匯聚，使用矩陣分解方法生成向量表示。

GraphSAGE模型[47]是對(duì)傳統(tǒng)圖卷積神經(jīng)網(wǎng)絡(luò)的延伸，模型中目標(biāo)節(jié)點(diǎn)的向量表示由其鄰居節(jié)點(diǎn)的信息(拓?fù)湫畔⒑蛯傩孕畔?所決定。模型訓(xùn)練的過(guò)程如圖7所示，首先從源節(jié)點(diǎn)的k階鄰居中選擇一定數(shù)量的節(jié)點(diǎn)；接下來(lái)對(duì)不同的k階鄰居節(jié)點(diǎn)訓(xùn)練出相應(yīng)的聚合函數(shù)(例如Mean aggregator、LSTM aggregator等)。最終得到的節(jié)點(diǎn)向量表示匯聚了其各自鄰居的信息，不僅可對(duì)訓(xùn)練過(guò)程中不可見(jiàn)的節(jié)點(diǎn)信息進(jìn)行預(yù)測(cè)，而且能夠結(jié)合后續(xù)的任務(wù)進(jìn)行有監(jiān)督學(xué)習(xí)。

圖7 GraphSAGE模型[48]

3.4 嵌入多類(lèi)型屬性信息

另外還有一些網(wǎng)絡(luò)表示學(xué)習(xí)算法，綜合學(xué)習(xí)了不同類(lèi)型的屬性信息。

LANE(label informed attributed network embedding)算法[48]同時(shí)學(xué)習(xí)屬性網(wǎng)絡(luò)中的節(jié)點(diǎn)相似度信息和標(biāo)簽信息，綜合兩者生成節(jié)點(diǎn)的向量表示。圖8展示了算法的計(jì)算流程。算法主要分為兩個(gè)模塊，在第一個(gè)模塊中算法對(duì)網(wǎng)絡(luò)的屬性信息和拓?fù)湫畔⑦M(jìn)行嵌入，第二個(gè)模塊將節(jié)點(diǎn)的標(biāo)簽信息進(jìn)行嵌入。LANE算法通過(guò)相關(guān)投影模式將學(xué)得的這三類(lèi)信息映射到新的維度空間中，最大化三者在新空間上的關(guān)聯(lián)性，進(jìn)而得出最終的向量表示。

圖8 LANE模型框架[49]

SNE(docial network embedding)算法[49]運(yùn)用深層神經(jīng)網(wǎng)絡(luò)對(duì)不同類(lèi)型的節(jié)點(diǎn)信息進(jìn)行綜合學(xué)習(xí)，如圖9所示。該算法將節(jié)點(diǎn)的屬性作為神經(jīng)網(wǎng)絡(luò)的輸入，由兩個(gè)全連接層組成的嵌入層對(duì)屬性向量進(jìn)行降維，進(jìn)而通過(guò)隱含層對(duì)向量進(jìn)行非線性映射，最后經(jīng)過(guò)一個(gè)隱含層后得到的向量轉(zhuǎn)化成目標(biāo)節(jié)點(diǎn)與其它節(jié)點(diǎn)連接的概率向量。最終節(jié)點(diǎn)的向量表示由最后一個(gè)隱含層的向量和連接到輸出層的權(quán)重向量相加得到。

圖9 SNE模型框架[50]

3.5 屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法對(duì)比

從算法的時(shí)間復(fù)雜度和其優(yōu)缺點(diǎn)等方面對(duì)上述屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法進(jìn)行比較，如表3所示。

表3 屬性網(wǎng)絡(luò)表示學(xué)習(xí)算法對(duì)比

4 應(yīng)用場(chǎng)景

網(wǎng)絡(luò)表示學(xué)習(xí)具有多種任務(wù)應(yīng)用場(chǎng)景，典型的有節(jié)點(diǎn)分類(lèi)、鏈接預(yù)測(cè)、聚類(lèi)和推薦等。本節(jié)選取不同類(lèi)別下的代表性算法，并將這些算法在節(jié)點(diǎn)分類(lèi)這一應(yīng)用場(chǎng)景下進(jìn)行測(cè)試，比較不同算法在相同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。選取了8個(gè)代表性的網(wǎng)絡(luò)表示學(xué)習(xí)算法進(jìn)行實(shí)驗(yàn)對(duì)比，分別為同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)類(lèi)別下的DeepWalk[25]、Node2vec[26]、LINE[23]和GraRep[31]等算法，和屬性網(wǎng)絡(luò)表示學(xué)習(xí)類(lèi)別下的CANE[45]、TADW[46]、SEANO[34]和GraphSAGE[47]等算法。

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

選用以下三種常用的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

①Cora引文數(shù)據(jù)集的子集，包括2 708個(gè)節(jié)點(diǎn)和5 429條邊，其中每個(gè)節(jié)點(diǎn)代表一篇論文，每條邊代表論文之間的引用關(guān)系。所有論文根據(jù)學(xué)科領(lǐng)域被劃分為7個(gè)類(lèi)別，且每篇論文具有一個(gè)1 433維度的屬性向量，屬性向量提取自論文中的關(guān)鍵詞。

②Citeseer引文數(shù)據(jù)集的子集，包含3 312個(gè)節(jié)點(diǎn)(論文)和4 732條邊(引用關(guān)系)。論文來(lái)自計(jì)算機(jī)科學(xué)和信息科學(xué)等相關(guān)領(lǐng)域，共分為6個(gè)類(lèi)別。每篇論文具有一個(gè)3 703維的屬性向量，屬性向量提取自論文的題目和摘要。

③Wiki數(shù)據(jù)集來(lái)自Wikipedia，共包含2 405個(gè)節(jié)點(diǎn)和17 981條邊，其中每個(gè)節(jié)點(diǎn)表示一篇文章，邊表示文章之間的鏈接關(guān)系。所有節(jié)點(diǎn)被劃分為17個(gè)類(lèi)別，且每篇文章具有一個(gè)4 973維度的屬性向量。

將這三種數(shù)據(jù)集的信息整理如表4所示。

表4 三種數(shù)據(jù)集的信息

4.2 節(jié)點(diǎn)分類(lèi)實(shí)驗(yàn)結(jié)果

將代表性算法在不同數(shù)據(jù)集上學(xué)得的表征向量輸入到one-vs-all分類(lèi)器中，并選取一定比例的節(jié)點(diǎn)進(jìn)行有監(jiān)督訓(xùn)練，目標(biāo)是預(yù)測(cè)剩余節(jié)點(diǎn)的標(biāo)簽。在節(jié)點(diǎn)分類(lèi)任務(wù)中選用Micro-F1和Macro-F1這兩種常用的評(píng)價(jià)指標(biāo)對(duì)分類(lèi)結(jié)果進(jìn)行評(píng)價(jià)。圖10、圖11和圖12分別為代表性算法在Cora、Citeseer和Wiki數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，其中各個(gè)子圖的橫軸代表數(shù)據(jù)訓(xùn)練的比例，縱軸表示兩種指標(biāo)(Micro-F1和Macro-F1)的評(píng)價(jià)結(jié)果。從圖中可以清晰地對(duì)不同算法的實(shí)驗(yàn)結(jié)果進(jìn)行觀察和對(duì)比?？偟膩?lái)說(shuō)，結(jié)合屬性信息的表示學(xué)習(xí)算法在節(jié)點(diǎn)分類(lèi)任務(wù)中的表現(xiàn)更加優(yōu)越。

圖10 Cora數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

圖11 Citeseer數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

圖12 Wiki數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

5 總結(jié)

本研究面向同構(gòu)網(wǎng)絡(luò)和屬性網(wǎng)絡(luò)，對(duì)相關(guān)代表性的網(wǎng)絡(luò)表示學(xué)習(xí)算法進(jìn)行了分類(lèi)介紹和比較。與基于拓?fù)湫畔⑾啾?，結(jié)合網(wǎng)絡(luò)中蘊(yùn)含的屬性信息進(jìn)行表示學(xué)習(xí)更易捕獲到真實(shí)網(wǎng)絡(luò)中的復(fù)雜關(guān)系，也能獲得更具區(qū)別力的表征向量。網(wǎng)絡(luò)表示學(xué)習(xí)研究雖然已經(jīng)取得了豐碩的成果，但仍然面臨著巨大的挑戰(zhàn)：

1)大規(guī)模網(wǎng)絡(luò)表示學(xué)習(xí)。在實(shí)際場(chǎng)景中的社交網(wǎng)絡(luò)規(guī)模可達(dá)到上億節(jié)點(diǎn)，然而已有的網(wǎng)絡(luò)表示學(xué)習(xí)模型無(wú)法應(yīng)對(duì)此類(lèi)規(guī)模的網(wǎng)絡(luò)。同時(shí)網(wǎng)絡(luò)中包含的噪音甚至誤導(dǎo)性數(shù)據(jù)也逐漸增多，面對(duì)噪音數(shù)據(jù)應(yīng)該如何有效處理、過(guò)濾，也是網(wǎng)絡(luò)表示學(xué)習(xí)需要考慮的問(wèn)題之一。

2)網(wǎng)絡(luò)動(dòng)態(tài)變化的適應(yīng)性。隨著5G時(shí)代的來(lái)臨，網(wǎng)絡(luò)結(jié)構(gòu)及其包含的信息瞬息萬(wàn)變。如何將網(wǎng)絡(luò)表示學(xué)習(xí)方法與時(shí)代的發(fā)展步伐相匹配，對(duì)動(dòng)態(tài)變化的網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)，值得進(jìn)一步研究。