網(wǎng)絡(luò)表示學(xué)習(xí)算法的研究現(xiàn)狀與進(jìn)展

李 敏，汪 晴，于春紅

(淮北師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 淮北 235000)

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，大規(guī)模社交網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)、文獻(xiàn)引文網(wǎng)絡(luò)等網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的挖掘成為數(shù)據(jù)挖掘領(lǐng)域的重點(diǎn)。網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的最大特點(diǎn)是節(jié)點(diǎn)之間并非完全獨(dú)立，因不同關(guān)系產(chǎn)生不同類型的邊，除此之外，節(jié)點(diǎn)因自身特點(diǎn)表現(xiàn)為豐富的內(nèi)容信息。網(wǎng)絡(luò)的復(fù)雜性、大規(guī)模性、不確定性降低了機(jī)器學(xué)習(xí)的效率，網(wǎng)絡(luò)表示學(xué)習(xí)成為關(guān)鍵。

節(jié)點(diǎn)聚類、分類、鏈路預(yù)測等網(wǎng)絡(luò)挖掘應(yīng)用[1]，均以節(jié)點(diǎn)的表示信息為輸入。傳統(tǒng)的網(wǎng)絡(luò)表示主要為矩陣表示，利用網(wǎng)絡(luò)結(jié)構(gòu)信息構(gòu)造網(wǎng)絡(luò)的權(quán)矩陣、鄰接矩陣、關(guān)聯(lián)矩陣等矩陣形式。大規(guī)模網(wǎng)絡(luò)的社團(tuán)現(xiàn)象、冷啟動(dòng)等因素造成網(wǎng)絡(luò)的高維性、稀疏性使矩陣表示陷入困境，同時(shí)矩陣表示無法加入節(jié)點(diǎn)信息。節(jié)點(diǎn)信息具有標(biāo)識(shí)性，有助于提高網(wǎng)絡(luò)挖掘效率，網(wǎng)絡(luò)表示要兼顧網(wǎng)絡(luò)結(jié)構(gòu)信息和節(jié)點(diǎn)信息。向量空間的相似性等定量指標(biāo)可以直接計(jì)算，并且大多機(jī)器學(xué)習(xí)算法以向量為輸入，網(wǎng)絡(luò)表示學(xué)習(xí)將節(jié)點(diǎn)映射到低維向量空間可使用通用的機(jī)器學(xué)習(xí)算法并能夠可視化展示節(jié)點(diǎn)之間的結(jié)構(gòu)關(guān)系。

網(wǎng)絡(luò)表示學(xué)習(xí)可以有效地對(duì)空間中高維度節(jié)點(diǎn)降維，但又不丟失原有網(wǎng)絡(luò)結(jié)構(gòu)信息，應(yīng)用于后續(xù)其他算法中，網(wǎng)絡(luò)表示學(xué)習(xí)流程[1]如圖1所示。

圖1 網(wǎng)絡(luò)表示學(xué)習(xí)流程圖

1 基于結(jié)構(gòu)信息的網(wǎng)絡(luò)表示學(xué)習(xí)

網(wǎng)絡(luò)表示學(xué)習(xí)早期以矩陣表示為主，并基于譜方法對(duì)稀疏、高維節(jié)點(diǎn)進(jìn)行降維。代表方法有主成分分析PCA[2]或者奇異值分解SVD、非線性降維算法LLE[3]、拉普拉斯特征映射[4]等。根據(jù)結(jié)構(gòu)信息的PCA、SVD方法缺乏節(jié)點(diǎn)內(nèi)在信息，LLE、拉普拉斯特征映射只能處理無向網(wǎng)絡(luò)，難以直接對(duì)網(wǎng)絡(luò)進(jìn)行應(yīng)用并且難以擴(kuò)展到大型網(wǎng)絡(luò)。DGE算法[5]基于隨機(jī)游走思想可擴(kuò)展到大型網(wǎng)絡(luò)，有向或無向網(wǎng)絡(luò)均可處理。從社團(tuán)檢測角度設(shè)計(jì)的Social Dimensions等網(wǎng)絡(luò)表示學(xué)習(xí)算法也只考慮網(wǎng)絡(luò)的結(jié)構(gòu)信息[6]。以上算法通常網(wǎng)絡(luò)表示質(zhì)量較差，并且算法復(fù)雜度較高對(duì)應(yīng)用條件要求較為嚴(yán)苛，難以直接應(yīng)用到網(wǎng)絡(luò)挖掘任務(wù)中。

基于自然語言處理技術(shù)的深度學(xué)習(xí)算法DeepWalk[1]和Node2Vec[7]逐漸被應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)中。為克服鄰接矩陣的稀疏性，LINE算法[8]引入二階相似性。基于深度神經(jīng)網(wǎng)絡(luò)的SDNE算法[9]將節(jié)點(diǎn)映射到高度非線性空間獲取網(wǎng)絡(luò)的結(jié)構(gòu)信息。

根據(jù)截?cái)嚯S機(jī)游走的思想，DeepWalk構(gòu)建等長節(jié)點(diǎn)序列。首次引入word2vec中的Skip-gram模型創(chuàng)造性地將詞表示學(xué)習(xí)方法引入網(wǎng)絡(luò)表示學(xué)習(xí)中。無向網(wǎng)絡(luò)節(jié)點(diǎn)之間有邊即以等概率游走，有向網(wǎng)絡(luò)中沿“出邊”的方向等概率游走。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)v以Φ:v∈VR|V|×d映射到d維向量空間。Φ產(chǎn)生|V|×d個(gè)自由參數(shù)，根據(jù)上下文的信息和節(jié)點(diǎn)排列獨(dú)立性假設(shè)，優(yōu)化條件概率(1)獲得參數(shù)。

(1)

以vi的截?cái)啻翱赪vi內(nèi)的共現(xiàn)節(jié)點(diǎn)為葉子節(jié)點(diǎn)構(gòu)造哈夫曼樹，獲得截?cái)嘈蛄?b0,b1,…,b|log|V||)=uk∈Wvi，b0=boot，b|log|V||=uk。Skip-gram模型根據(jù)節(jié)點(diǎn)序列uk構(gòu)造，如公式(2)所示。

(2)

其中：

J(Φ(vj))=-logP(uk|Φ(vj))

Skip-gram模型以α=2.5%的隨機(jī)梯度下降率不斷更新公式(2)，加速條件概率(1)收斂，最終獲得vi∈Rd。經(jīng)實(shí)證分析DeepWalk可以用較小的截?cái)嚯S機(jī)游走序列有效表示節(jié)點(diǎn)。

Node2Vec修改DeepWalk隨機(jī)游走跳轉(zhuǎn)機(jī)制，以條件概率P(vi|vi-1)進(jìn)行節(jié)點(diǎn)訪問，不再進(jìn)行均勻采樣。

(3)

其中，α是跳轉(zhuǎn)參數(shù)，W(vi,vi-1)是邊(vi,vi-1)上的權(quán)。游走到節(jié)點(diǎn)vi-1，計(jì)算其鄰居節(jié)點(diǎn)vi與上一節(jié)點(diǎn)vi-2的距離di,i-2，進(jìn)而計(jì)算α，定義如公式(4)所示。

(4)

參數(shù)p和q控制節(jié)點(diǎn)向上和向下跳轉(zhuǎn)的概率，節(jié)點(diǎn)之間以非等概率跳轉(zhuǎn)。參數(shù)p和q其默認(rèn)值均為1，當(dāng)p<1且q>1時(shí)，游走偏廣度優(yōu)先遍歷，著重刻畫局部信息；當(dāng)p>1且q<1時(shí)，著重刻畫全局信息，深度優(yōu)先游走。參數(shù)設(shè)置提高了算法的可擴(kuò)展性，獲取的序列長度不完全相同，更接近真實(shí)情況。Node2Vec隨機(jī)游走跳轉(zhuǎn)機(jī)制如圖2所示。

圖2 Node2Vec跳轉(zhuǎn)機(jī)制

LINE算法采用同時(shí)保持一階相似性和二階相似性的廣度優(yōu)先策略構(gòu)造鄰域表示節(jié)點(diǎn)，克服了網(wǎng)絡(luò)的稀疏性，可擴(kuò)展到包括有向和無向、賦權(quán)和無賦權(quán)等任意類型的大規(guī)模網(wǎng)絡(luò)。

網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)之間的相似度為一階相似性，表示為節(jié)點(diǎn)的聯(lián)合概率P1(vi,vj)。

(5)

二階相似性用于描述網(wǎng)絡(luò)中具有相同鄰接點(diǎn)的節(jié)點(diǎn)之間的相似度，兩個(gè)不直接相連的節(jié)點(diǎn)可以使用自身的表示向量和共同鄰居的表示向量來度量，用條件概率P2(vj|vi)表示。

(6)

圖3 相似性實(shí)例

由圖3可以看出節(jié)點(diǎn)v5,v6不相鄰，不具有一階相似性，但具有二階相似性，因它們有共同鄰居節(jié)點(diǎn)v1,v2,v3,v4。節(jié)點(diǎn)v6,v7相鄰具有一階相似性，但無共同鄰接點(diǎn)沒有二階相似性。LINE遍歷節(jié)點(diǎn)序列時(shí)同時(shí)利用具有互補(bǔ)性的一階相似性和二階相似性，并使用負(fù)采樣優(yōu)化更新節(jié)點(diǎn)表示。對(duì)于稀疏節(jié)點(diǎn)利用鄰居的鄰居構(gòu)造樣本進(jìn)行學(xué)習(xí)，既保留了網(wǎng)絡(luò)的局部結(jié)構(gòu)又保留了全局結(jié)構(gòu)，但并未利用高階相似性信息。

2 基于異質(zhì)網(wǎng)絡(luò)的表示學(xué)習(xí)

以上算法不區(qū)分節(jié)點(diǎn)和邊的類型，真實(shí)世界中的網(wǎng)絡(luò)是節(jié)點(diǎn)具有差異性、節(jié)點(diǎn)之間的鏈接關(guān)系各異的異質(zhì)網(wǎng)絡(luò)。例如物聯(lián)網(wǎng)主要包含用戶、商品兩類節(jié)點(diǎn)，主要應(yīng)用有推薦系統(tǒng)預(yù)測。文獻(xiàn)引文網(wǎng)絡(luò)有4類節(jié)點(diǎn)：作者(A)、論文(P)、刊物(V)、主題(O)，論文與其他3個(gè)節(jié)點(diǎn)之間都存在鏈接關(guān)系，廣泛應(yīng)用在作者影響力排序中，如圖4所示。

圖4 文獻(xiàn)引文網(wǎng)絡(luò)

同質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)難以利用異質(zhì)網(wǎng)絡(luò)中豐富的語義信息。異質(zhì)網(wǎng)絡(luò)因節(jié)點(diǎn)間的關(guān)聯(lián)邊類型不同所蘊(yùn)含的語義也不同，節(jié)點(diǎn)之間的相似性不能直接量化度量。HINE算法[10]應(yīng)用Meta math概念區(qū)分異質(zhì)網(wǎng)絡(luò)中不同類型的邊序列構(gòu)造元路徑，引文文獻(xiàn)網(wǎng)絡(luò)中常用的元路徑類型有“APA”“APVPA”“OAPVPAO”3種類型。從圖4中可以找到一條表示具有相同研究領(lǐng)域的“APVPA”元路徑“a1→p1→ACL→p2→a3”?；谠窂搅炕?jié)點(diǎn)的相似性，使異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)成為可能。異質(zhì)網(wǎng)絡(luò)是表示現(xiàn)實(shí)世界中對(duì)象交互的更加通用的建模方式，異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)主要有以下3種方式。

(1)基于隨機(jī)游走的方法

(7)

Nt(v),t∈Tv為異質(zhì)共現(xiàn)節(jié)點(diǎn)，通過極大化目標(biāo)節(jié)點(diǎn)出現(xiàn)的概率，使用Softmax函數(shù)加速其收斂速度構(gòu)造異構(gòu)Skip-gram模型。

(8)

(9)

～P(ut)[logσ(-Xutm·Xv]

(10)

Metapath2vec++受PTE[12]啟發(fā)，根據(jù)節(jié)點(diǎn)類型構(gòu)造異構(gòu)負(fù)采樣，加速函數(shù)歸一化時(shí)也充分考慮了節(jié)點(diǎn)類型。經(jīng)實(shí)證分析Metapath2vec++在多標(biāo)簽分類、節(jié)點(diǎn)聚類、相似性搜索等任務(wù)中具有更高的精度和可靠性。

(2)分解網(wǎng)絡(luò)的方法

根據(jù)節(jié)點(diǎn)類型將大規(guī)模異質(zhì)網(wǎng)絡(luò)分解成若干個(gè)子網(wǎng)絡(luò)，進(jìn)行同質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)，有效融合不同類型的節(jié)點(diǎn)是關(guān)鍵。代表算法有PTE[12]和HERec[13]等，需要更少的調(diào)整參數(shù)。PTE算法結(jié)合有限的標(biāo)簽實(shí)例和大量未標(biāo)簽實(shí)例，解決了無監(jiān)督表示學(xué)習(xí)算法不能適應(yīng)特定目標(biāo)的機(jī)器學(xué)習(xí)任務(wù)。PTE首次根據(jù)共現(xiàn)詞的不同層次將文本網(wǎng)絡(luò)分解成“詞-詞”網(wǎng)絡(luò)、“詞-文件”網(wǎng)絡(luò)和“詞-標(biāo)簽”網(wǎng)絡(luò)，向低維向量空間映射時(shí)保持詞的二階相似性。HERec基于不同元路徑提取同類型節(jié)點(diǎn)序列構(gòu)造同質(zhì)網(wǎng)絡(luò)，進(jìn)行Node2vec同質(zhì)表示學(xué)習(xí)，并融合不同類型節(jié)點(diǎn)的向量表示，基于矩陣分解構(gòu)造評(píng)分預(yù)測模型，聯(lián)合融合函數(shù)進(jìn)行模型優(yōu)化。

PTE定義3個(gè)二部網(wǎng)絡(luò)，分別為上下文詞共現(xiàn)“詞-詞”網(wǎng)絡(luò)Gww=(V,Eww)，詞與文件共現(xiàn)的“詞-文件”網(wǎng)絡(luò)Gwl=(V∪L,Ewl)，詞與某類文件共現(xiàn)的“詞-標(biāo)簽”網(wǎng)絡(luò)Gwl=(V∪L,Ewl)。利用節(jié)點(diǎn)的二階相似性修改LINE模型適應(yīng)二部網(wǎng)絡(luò)嵌入。

首先定義二部網(wǎng)絡(luò)G=(VA∪VB,E)，VA∩VB=φ，vi∈VA,vj∈VB。極小化二階相似性P(vi|vj)。

(11)

直接利用公式(12)加總極小化3個(gè)子網(wǎng)絡(luò)的詞節(jié)點(diǎn)相似性。

Opte=Oww+Owd+Owl

(12)

其中：

PTE算法對(duì)于具有豐富類標(biāo)號(hào)實(shí)例的長文本數(shù)據(jù)的預(yù)測是有效的，但詞節(jié)點(diǎn)表示學(xué)習(xí)只是簡單融合3個(gè)子網(wǎng)絡(luò)，還有改善的空間。

HERec算法首先基于元路徑提取多個(gè)同質(zhì)網(wǎng)絡(luò)并獨(dú)立表示學(xué)習(xí)。給定元路徑ρ，基于Node2vec思想，目標(biāo)函數(shù)(13)經(jīng)隨機(jī)梯度下降優(yōu)化得到節(jié)點(diǎn)的低維向量表示e。

(13)

(14)

α,β為調(diào)整參數(shù)，節(jié)點(diǎn)的不同向量表示使用線性公式(15)和非線性公式(16)所示的融合函數(shù)表示。

(15)

(16)

(3)基于深度神經(jīng)網(wǎng)絡(luò)的方法

深度神經(jīng)網(wǎng)絡(luò)模型容易對(duì)非線性關(guān)系建模，一些學(xué)者嘗試?yán)蒙疃壬窠?jīng)網(wǎng)絡(luò)模型對(duì)異質(zhì)網(wǎng)絡(luò)中不同類型的節(jié)點(diǎn)分別進(jìn)行建模，并抽取節(jié)點(diǎn)語義信息。

BL-MNE[14]采用無監(jiān)督神經(jīng)網(wǎng)絡(luò)模型自動(dòng)編碼器在不同元路徑下對(duì)節(jié)點(diǎn)進(jìn)行低維編碼，再對(duì)這些信息通過meta鄰近性度量進(jìn)行聯(lián)合編碼學(xué)習(xí)得到異質(zhì)網(wǎng)絡(luò)的低維空間表示。共用已編碼的成熟異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)構(gòu)造一致屬性增廣網(wǎng)絡(luò)，不同網(wǎng)絡(luò)之間通過轉(zhuǎn)移矩陣進(jìn)行融合，對(duì)于網(wǎng)絡(luò)稀疏性有很好的效果。SHINE[15]針對(duì)情感網(wǎng)絡(luò)構(gòu)造3個(gè)不同的網(wǎng)絡(luò)，對(duì)3個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)分別進(jìn)行多重深度自動(dòng)編碼并壓縮編碼得到低維向量表示，構(gòu)造聚合函數(shù)融合子網(wǎng)的節(jié)點(diǎn)表示用于情感鏈路預(yù)測。針對(duì)文本和圖像并存的異質(zhì)網(wǎng)絡(luò)，HNE[16]訓(xùn)練卷積神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)文本，同時(shí)訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)圖像，構(gòu)建轉(zhuǎn)移矩陣投影文本和圖像的向量表示到同一空間，使跨模態(tài)數(shù)據(jù)之間的相似性可以度量。

學(xué)習(xí)異質(zhì)網(wǎng)絡(luò)的嵌入表示能夠較好地刻畫網(wǎng)絡(luò)中不同類型節(jié)點(diǎn)之間的復(fù)雜關(guān)聯(lián)，便于和其他模態(tài)信息的融合，廣泛應(yīng)用于各類任務(wù)場景，一些結(jié)合任務(wù)的方法也被提出。例如PTE、Metapath2vec、GERI[17]等用于異質(zhì)網(wǎng)絡(luò)節(jié)點(diǎn)分類，SHINE、HIN2vec[18]等用于異質(zhì)網(wǎng)絡(luò)鏈路預(yù)測，JRL[19]、HERec等用于異質(zhì)網(wǎng)絡(luò)推薦系統(tǒng)，APE[20]是一個(gè)學(xué)術(shù)合作異質(zhì)網(wǎng)絡(luò)雙盲評(píng)審的作者識(shí)別問題。除此之外，RANCH[21]利用圖注意網(wǎng)絡(luò)和卷積神經(jīng)網(wǎng)絡(luò)構(gòu)建半監(jiān)督學(xué)習(xí)模型，采用邊緣約束截?cái)嚯S機(jī)游走產(chǎn)生節(jié)點(diǎn)序列，并融合節(jié)點(diǎn)標(biāo)簽信息，在節(jié)點(diǎn)分類中效果顯著。MHGan[22]受生成對(duì)抗網(wǎng)絡(luò)和元路徑的啟發(fā)，充分考慮節(jié)點(diǎn)和邊的異質(zhì)性提高關(guān)系感知能力，實(shí)現(xiàn)對(duì)異質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)，在鏈路預(yù)測和節(jié)點(diǎn)分類中性能表現(xiàn)較好。

3 節(jié)點(diǎn)信息融合的網(wǎng)絡(luò)表示方法

社交網(wǎng)絡(luò)、文獻(xiàn)引文網(wǎng)絡(luò)等現(xiàn)實(shí)世界網(wǎng)絡(luò)中的節(jié)點(diǎn)并不完全相同，節(jié)點(diǎn)含有豐富的信息，節(jié)點(diǎn)的類標(biāo)簽、屬性、語義描述等文本信息有助于網(wǎng)絡(luò)挖掘任務(wù)。主要依賴結(jié)構(gòu)信息忽略節(jié)點(diǎn)特征信息的傳統(tǒng)網(wǎng)絡(luò)表示學(xué)習(xí)，網(wǎng)絡(luò)挖掘效果不佳。有效融合結(jié)構(gòu)和文本信息提高節(jié)點(diǎn)表示的質(zhì)量并增強(qiáng)機(jī)器學(xué)習(xí)輸入的效果是網(wǎng)絡(luò)表示學(xué)習(xí)的關(guān)鍵。網(wǎng)絡(luò)結(jié)構(gòu)融合節(jié)點(diǎn)信息的表示方法主要有以下3種方式。

(1)結(jié)合文本信息的方法

關(guān)系矩陣M的內(nèi)在結(jié)構(gòu)近似等價(jià)于一個(gè)低秩矩陣，基于這一假設(shè)，M是可分解的，但這是NP困難的。TADW在前人工作的基礎(chǔ)上通過DeepWalk構(gòu)建矩陣M=(A+A2)/2，將文本特征矩陣T融入到DeepWalk矩陣分解M=WT×HT，通過共軛梯度下降法優(yōu)化公式(17)所示的目標(biāo)函數(shù)獲得W，H，拼接W和HT。

(17)

HOPE算法[27]也基于矩陣分解框架，這類算法的最大缺點(diǎn)就是存儲(chǔ)、計(jì)算成本高，伸縮性不好，不適合大規(guī)模網(wǎng)絡(luò)表示學(xué)習(xí)。

(2)半監(jiān)督學(xué)習(xí)

網(wǎng)絡(luò)節(jié)點(diǎn)分類任務(wù)需提取節(jié)點(diǎn)的分類信息，無監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)在節(jié)點(diǎn)分類中往往效果不佳。利用節(jié)點(diǎn)類標(biāo)簽信息的半監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)有針對(duì)性地提升節(jié)點(diǎn)的區(qū)分性，在分類任務(wù)中效果較好。MMDW[28]是和TADW類似的半監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)方法，該方法先學(xué)習(xí)基于DeepWalk的矩陣分解形式的網(wǎng)絡(luò)表示模型M=XTY，同時(shí)基于SVM學(xué)習(xí)一個(gè)X的最大間距分類器。MMDW通過目標(biāo)函數(shù)(18)優(yōu)化分類器。

(18)

(19)

MMDW通過固定X，將Y轉(zhuǎn)化為對(duì)偶問題，W和ζ的優(yōu)化借助隨機(jī)梯度下降方法。固定W和ζ，計(jì)算分類器邊界，并設(shè)置傾向于正確類別的偏置向量，達(dá)到提高表示向量區(qū)分能力的目的。在SVM的影響下，MMDW既獲得了網(wǎng)絡(luò)結(jié)構(gòu)信息，也獲得了類標(biāo)簽信息，提高了節(jié)點(diǎn)的區(qū)分性。受最大間距分類器影響，DDRW[29]也采用了類似的方法，DeepWalk矩陣分解模型和最大間距分類器同時(shí)訓(xùn)練，提高網(wǎng)絡(luò)節(jié)點(diǎn)的分類效果。

網(wǎng)絡(luò)中的節(jié)點(diǎn)往往只有部分含有類標(biāo)簽信息，為了更好地利用節(jié)點(diǎn)信息和節(jié)點(diǎn)標(biāo)簽信息，Pan等[30]提出了耦合深度神經(jīng)網(wǎng)絡(luò)的TriDNR模型，該模型耦合兩個(gè)神經(jīng)網(wǎng)絡(luò)融合節(jié)點(diǎn)的結(jié)構(gòu)、文本和標(biāo)簽信息獲得節(jié)點(diǎn)的向量表示。模型上層生成的節(jié)點(diǎn)序列S與DeepWalk的隨機(jī)游走相似；節(jié)點(diǎn)的文本信息詞向量{Wi}作為模型的底層；中間層基于文本信息利用深度神經(jīng)網(wǎng)絡(luò)融合S和{Wi}獲得節(jié)點(diǎn)的向量表示。另一個(gè)神經(jīng)網(wǎng)絡(luò)融合標(biāo)簽向量{Ci}和詞向量{Wi}。最大化目標(biāo)函數(shù)公式(20)耦合兩個(gè)神經(jīng)網(wǎng)絡(luò)。

(20)

其中，α是平衡結(jié)構(gòu)信息、文本信息、標(biāo)簽信息的權(quán)，b是隨機(jī)游走窗口大小，Wj是窗口內(nèi)第j個(gè)詞。

網(wǎng)絡(luò)中節(jié)點(diǎn)的標(biāo)簽信息可能不完整、包含噪聲，很難學(xué)習(xí)一個(gè)統(tǒng)一的表示形式將標(biāo)簽信息融合到結(jié)構(gòu)信息中。針對(duì)以上問題，Huang等[31]提出了LANE模型。該模型由兩部分組成，第一部分基于譜聚類將節(jié)點(diǎn)相似性映射為結(jié)構(gòu)表示矩陣U(G)和節(jié)點(diǎn)屬性表示矩陣U(A)，并將U(A)融合進(jìn)U(G)稱為屬性網(wǎng)絡(luò)嵌入；第二部分基于同質(zhì)性假設(shè)融合標(biāo)簽信息光滑U(G)為矩陣U(Y)，同時(shí)融合U(G)和U(Y)獲得節(jié)點(diǎn)的表示矩陣H稱為標(biāo)簽嵌入。U(G)和U(A)的獲得方式相同，U(G)根據(jù)模型(21)獲得。

(21)

(22)

根據(jù)局部特征分解方程不斷更新4個(gè)變量矩陣，直到目標(biāo)函數(shù)收斂，完成網(wǎng)絡(luò)到向量空間的映射。

(3)擴(kuò)展網(wǎng)絡(luò)

隨著對(duì)網(wǎng)絡(luò)認(rèn)識(shí)的不斷深入，網(wǎng)絡(luò)表示學(xué)習(xí)方法又出現(xiàn)了擴(kuò)展網(wǎng)絡(luò)的方法。CENE[32]將網(wǎng)絡(luò)擴(kuò)展為包含兩類節(jié)點(diǎn)和兩類邊的網(wǎng)絡(luò)Gavg(Vn,Vc,Enn,Enc)，其中，Vn為原始網(wǎng)絡(luò)的節(jié)點(diǎn)，Vc為擴(kuò)展節(jié)點(diǎn)信息的特殊節(jié)點(diǎn)，Enn為連接原始節(jié)點(diǎn)的邊，連接Vn與Vc的邊為Enc。分別使用邏輯回歸函數(shù)學(xué)習(xí)Vn和Vc的向量表示，使用負(fù)采樣的方法優(yōu)化目標(biāo)函數(shù)：

(23)

其中，SP是隨機(jī)游走序列，SN是負(fù)采樣節(jié)點(diǎn)。使用拼接函數(shù)公式(24)拼接兩類節(jié)點(diǎn)。

L=α×Lnn+(1-α)×Lnc

(24)

其中，Lnn為通過由Enn形成的序列Vn，Lnc為通過由Enc形成的序列Vc，參數(shù)α∈[0,1]平衡結(jié)構(gòu)信息和文本信息之間的重要性，隨機(jī)梯度下降優(yōu)化拼接函數(shù)。

TENR[33]和CENE相似，將節(jié)點(diǎn)信息視為節(jié)點(diǎn)并根據(jù)節(jié)點(diǎn)信息的相似性構(gòu)建文本網(wǎng)絡(luò)，融合原網(wǎng)絡(luò)擴(kuò)展成異質(zhì)網(wǎng)絡(luò)，如圖5所示，圓圈外是文本節(jié)點(diǎn)保留了文本相似性，內(nèi)是原始節(jié)點(diǎn)保持了結(jié)構(gòu)相似性。

圖5 文本異質(zhì)網(wǎng)絡(luò)

受CBOW[34]啟發(fā)，TENR基于負(fù)采樣構(gòu)建拓?fù)浣Y(jié)構(gòu)模型學(xué)習(xí)原始節(jié)點(diǎn)的結(jié)構(gòu)向量表示，同時(shí)構(gòu)建文本模型學(xué)習(xí)受文本信息影響的節(jié)點(diǎn)向量表示，最終節(jié)點(diǎn)的向量表示共享兩個(gè)模型的學(xué)習(xí)。

4 基于動(dòng)態(tài)網(wǎng)絡(luò)的表示學(xué)習(xí)方法

真實(shí)世界中的很多網(wǎng)絡(luò)是動(dòng)態(tài)的，隨時(shí)間的推移會(huì)出現(xiàn)節(jié)點(diǎn)和邊的添加或刪除，靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法不能滿足動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)的需求。更新現(xiàn)有靜態(tài)網(wǎng)絡(luò)表示方法[35]以適應(yīng)動(dòng)態(tài)網(wǎng)絡(luò)挖掘任務(wù)是最簡單的方法，現(xiàn)有大多方法將動(dòng)態(tài)網(wǎng)絡(luò)按時(shí)間片應(yīng)用靜態(tài)網(wǎng)絡(luò)表示方法并增加動(dòng)態(tài)變化識(shí)別機(jī)制。網(wǎng)絡(luò)分解方法[35]試圖通過對(duì)連續(xù)時(shí)間片上的網(wǎng)絡(luò)表示進(jìn)行光滑來學(xué)習(xí)動(dòng)態(tài)網(wǎng)絡(luò)表示[36]。動(dòng)態(tài)屬性網(wǎng)絡(luò)表示框架DANE[37]首先提出離線表示方法，然后根據(jù)屬性演化網(wǎng)絡(luò)的變化更新表示結(jié)果。Know-Evolve[38]提出基于多元事件檢測的實(shí)體嵌入知識(shí)圖譜的演化網(wǎng)絡(luò)表示法。CTDN[39]是基于隨機(jī)游走的連續(xù)時(shí)間動(dòng)態(tài)網(wǎng)絡(luò)表示方法，隨機(jī)游走非在線，網(wǎng)絡(luò)表示前需要知道所有隨機(jī)游走的信息。HTNE[40]嘗試建模動(dòng)態(tài)網(wǎng)絡(luò)為自激勵(lì)系統(tǒng)并利用Hawkes過程模型對(duì)網(wǎng)絡(luò)中的鄰域形成進(jìn)行建模，基于時(shí)間點(diǎn)過程優(yōu)化網(wǎng)絡(luò)表示。HTNE是在線動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)框架，優(yōu)化過程中使用歷史數(shù)據(jù)，在每個(gè)步驟中都要針對(duì)歷史數(shù)據(jù)進(jìn)行調(diào)整?；谏鐖F(tuán)嵌入的Netwalk[41]，利用內(nèi)存中的存儲(chǔ)數(shù)據(jù)更新隨機(jī)游走序列。Du等[42]提出動(dòng)態(tài)skip-gram框架，Rudolph等[43]提出基于高斯隨機(jī)游走的動(dòng)態(tài)詞嵌入算法，在時(shí)間序列上定義基于向量表示的隨機(jī)游走。

鏈路預(yù)測是最廣泛的動(dòng)態(tài)網(wǎng)絡(luò)分析應(yīng)用，而現(xiàn)有時(shí)間模式大多簡化網(wǎng)絡(luò)的動(dòng)態(tài)變化，只根據(jù)上一時(shí)間步長網(wǎng)絡(luò)預(yù)測新鏈接，有的還假設(shè)網(wǎng)絡(luò)動(dòng)態(tài)變化是光滑的，并使用規(guī)則化降低快速變化的影響。在每個(gè)時(shí)間片上dyngraph2vec[44]進(jìn)行多重非線性學(xué)習(xí)結(jié)構(gòu)信息，采用循環(huán)神經(jīng)網(wǎng)絡(luò)更新表示，循環(huán)層設(shè)置回顧參數(shù)控制周期變動(dòng)長度。t'=t+1時(shí)刻的網(wǎng)絡(luò)表示以t時(shí)刻一系列節(jié)點(diǎn)表示為基礎(chǔ)，極小化公式(25)表示的損失函數(shù)。

(25)

靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)的方法具有不穩(wěn)定性[45]，又由于網(wǎng)絡(luò)結(jié)構(gòu)的變動(dòng)通常是局部的，隨機(jī)游走序列只有少部分受到影響，Heidari[45]提出基于隨機(jī)游走的增量網(wǎng)絡(luò)表示學(xué)習(xí)算法EvoNRL。增量地更新備用隨機(jī)游走集，并提出支持隨機(jī)游走集合的有效存儲(chǔ)和更新的索引機(jī)制用于網(wǎng)絡(luò)的動(dòng)態(tài)表示。采用靜態(tài)隨機(jī)游走方法獲得t時(shí)刻Gt的每個(gè)節(jié)點(diǎn)的有效隨機(jī)游走集RWt并存儲(chǔ)為二維numpy矩陣。時(shí)刻t'=t+i(i=1,2,…)，因節(jié)點(diǎn)的增刪或邊的增刪導(dǎo)致網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化，采用不同的方法單獨(dú)更新G't的RW't使在t'時(shí)刻仍有效，并將節(jié)點(diǎn)的增刪看作特殊的邊的增刪。增量更新隨機(jī)游走需要大量的存儲(chǔ)和計(jì)算開銷，為克服這一缺點(diǎn)，提出基于流行的開源索引和搜索技術(shù)的索引機(jī)制能夠有效地索引和檢索大量文檔，每個(gè)隨機(jī)游走看作由詞節(jié)點(diǎn)組成的文檔，將所有隨機(jī)游走建立反向隨機(jī)游走索引IRW表示節(jié)點(diǎn)到RWt的映射，RWt的增量更新依賴IRW。EvoNRL討論的是連通、無權(quán)、無向網(wǎng)絡(luò)，網(wǎng)絡(luò)結(jié)構(gòu)中發(fā)生的任何變化按重要性進(jìn)行量化，在最佳時(shí)間或真正需要時(shí)獲得新的網(wǎng)絡(luò)表示，消除隨機(jī)過程的影響，盡可能保存原始隨機(jī)游走序列，通過使用上一次運(yùn)行的數(shù)據(jù)來初始化模型。

DCTNE[46]是基于隨機(jī)游走的動(dòng)態(tài)連續(xù)時(shí)間網(wǎng)絡(luò)表示學(xué)習(xí)算法，根據(jù)歷史數(shù)據(jù)對(duì)當(dāng)前節(jié)點(diǎn)的影響不同建立有偏隨機(jī)游走過程獲得節(jié)點(diǎn)時(shí)序鄰居節(jié)點(diǎn)序列，學(xué)習(xí)網(wǎng)絡(luò)表示，在節(jié)點(diǎn)分類任務(wù)上效果顯著。DynGraphGAN[47]構(gòu)建對(duì)抗網(wǎng)絡(luò)，獲取節(jié)點(diǎn)、邊變動(dòng)引起的網(wǎng)絡(luò)局部結(jié)構(gòu)信息變化信息，嵌入結(jié)構(gòu)特征和動(dòng)態(tài)演化趨勢?；陔S機(jī)游走的動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)還有Sajjad等[48]提出的增量隨機(jī)游走算法和半監(jiān)督學(xué)習(xí)算法tNodeEmbed[49]。TensorGCN[50]、OCAN[51]和AddGraph[52]都是基于深度學(xué)習(xí)的動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)算法，目前也有學(xué)者提出利用霍克斯點(diǎn)過程的動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法[53]，也取得了一定的成果。HIN_DRL[54]利用網(wǎng)絡(luò)異質(zhì)信息學(xué)習(xí)動(dòng)態(tài)網(wǎng)絡(luò)，基于元路徑和時(shí)間戳信息動(dòng)態(tài)隨機(jī)游走生成節(jié)點(diǎn)序列。

5 結(jié)語

網(wǎng)絡(luò)表示學(xué)習(xí)旨在將網(wǎng)絡(luò)節(jié)點(diǎn)映射到便于機(jī)器學(xué)習(xí)處理的低維向量空間，消除網(wǎng)絡(luò)的高維性和稀疏性。靜態(tài)網(wǎng)絡(luò)的表示方法主要分為矩陣分解法和隨機(jī)游走法，矩陣分解法存儲(chǔ)、計(jì)算成本高，伸縮性不好，只適用于小型網(wǎng)絡(luò)；利用網(wǎng)絡(luò)的局部信息構(gòu)造節(jié)點(diǎn)序列的隨機(jī)游走方法，能擴(kuò)展到大型網(wǎng)絡(luò)。網(wǎng)絡(luò)表示學(xué)習(xí)不僅要表征網(wǎng)絡(luò)結(jié)構(gòu)信息還要結(jié)合節(jié)點(diǎn)文本信息以及節(jié)點(diǎn)之間的不同關(guān)聯(lián)關(guān)系，還要注意節(jié)點(diǎn)的差異性?，F(xiàn)實(shí)世界中，大規(guī)模網(wǎng)絡(luò)往往隨時(shí)間的推移會(huì)出現(xiàn)節(jié)點(diǎn)及邊的變動(dòng)，具有不確定性，靜態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)方法很難適應(yīng)網(wǎng)絡(luò)的動(dòng)態(tài)變化。網(wǎng)絡(luò)的演變特征學(xué)習(xí)是現(xiàn)有大多動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)的核心，但對(duì)網(wǎng)絡(luò)的高度動(dòng)態(tài)性建模不夠，適應(yīng)性不高。網(wǎng)絡(luò)表示學(xué)習(xí)在未來還有巨大發(fā)展空間，尤其是具體應(yīng)用場景下融合多模態(tài)信息動(dòng)態(tài)大規(guī)模網(wǎng)絡(luò)表示學(xué)習(xí)。

(1)融合多模態(tài)信息的網(wǎng)絡(luò)表示學(xué)習(xí)?，F(xiàn)階段只保存網(wǎng)絡(luò)自身的信息網(wǎng)絡(luò)表示學(xué)習(xí)，忽略了知識(shí)圖譜等外部知識(shí)信息，異質(zhì)網(wǎng)絡(luò)因節(jié)點(diǎn)信息不同形成多樣化的鏈接關(guān)系，從而包含豐富的多模態(tài)信息，如何將這些信息融合進(jìn)網(wǎng)絡(luò)表示學(xué)習(xí)是亟待解決的難點(diǎn)。

(2)融合節(jié)點(diǎn)信息的大規(guī)模動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)?，F(xiàn)有動(dòng)態(tài)網(wǎng)絡(luò)表示學(xué)習(xí)僅學(xué)習(xí)網(wǎng)絡(luò)的結(jié)構(gòu)信息，試圖捕捉動(dòng)態(tài)變化信息。融合節(jié)點(diǎn)信息快速獲取新增節(jié)點(diǎn)信息，并高效地表示節(jié)點(diǎn)，以增量或在線計(jì)算的方式表示網(wǎng)絡(luò)仍是一個(gè)難點(diǎn)。

(3)基于具體應(yīng)用任務(wù)特點(diǎn)的網(wǎng)絡(luò)表示學(xué)習(xí)。目前網(wǎng)絡(luò)表示學(xué)習(xí)算法主要集中在通用的表示學(xué)習(xí)以適用所有網(wǎng)絡(luò)分析任務(wù)，很少分析具體應(yīng)用任務(wù)特點(diǎn)。通用表示學(xué)習(xí)在異常檢測、社區(qū)發(fā)現(xiàn)等具體應(yīng)用中效果往往不佳。如何將網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)根據(jù)不同應(yīng)用場景設(shè)計(jì)更加合理的節(jié)點(diǎn)表示模型提高應(yīng)用效果是值得關(guān)注的問題。