面向復(fù)雜網(wǎng)絡(luò)的異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)綜述

顏銘江，董一鴻，蘇江軍，陳華輝，錢江波

綜述

面向復(fù)雜網(wǎng)絡(luò)的異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)綜述

顏銘江，董一鴻，蘇江軍，陳華輝，錢江波

（寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江 寧波 315211）

異構(gòu)信息網(wǎng)絡(luò)包含豐富的節(jié)點信息和鏈接信息，具有復(fù)雜異質(zhì)性、高稀疏性、屬性高維性等特性，這些特性給網(wǎng)絡(luò)表示學(xué)習(xí)任務(wù)帶來了巨大的挑戰(zhàn)。異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)通過在嵌入過程中將多樣化的異質(zhì)信息和結(jié)構(gòu)信息進(jìn)行有效融合，學(xué)習(xí)得到更有利于下游機(jī)器學(xué)習(xí)任務(wù)的低維特征向量。從異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)方法的研究粒度出發(fā)，對近年的研究現(xiàn)狀進(jìn)行了比較全面的分析和討論。首先探討網(wǎng)絡(luò)表示學(xué)習(xí)的產(chǎn)生動機(jī)，闡述了近年的異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)的研究歷程；然后對具有代表性的算法模型進(jìn)行分類討論，歸納其主要的研究內(nèi)容和所使用的嵌入技巧。最后給出了未來工作中異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)可能的研究方向和比較有價值的研究內(nèi)容。

網(wǎng)絡(luò)表示學(xué)習(xí)；異構(gòu)信息網(wǎng)絡(luò)；圖嵌入；圖神經(jīng)網(wǎng)絡(luò)；異質(zhì)信息

1 引言

互聯(lián)網(wǎng)基礎(chǔ)建設(shè)的快速發(fā)展使各種線下信息數(shù)字化，導(dǎo)致可利用信息呈爆炸式增長。這些龐大數(shù)據(jù)中多樣化實體和實體間關(guān)聯(lián)構(gòu)成了一系列不同的信息網(wǎng)絡(luò)，如社交網(wǎng)絡(luò)[1-2]、生物分子網(wǎng)絡(luò)[3]等，催生了針對網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘的研究。網(wǎng)絡(luò)表示學(xué)習(xí)[4]（network representation learning/ network embedding，NRL）又稱為圖嵌入，是為了能有效地進(jìn)行信息網(wǎng)絡(luò)數(shù)據(jù)挖掘任務(wù)而產(chǎn)生的研究方法。網(wǎng)絡(luò)表示學(xué)習(xí)依據(jù)相關(guān)優(yōu)化目標(biāo)，將具有高維復(fù)雜信息的網(wǎng)絡(luò)中實體節(jié)點映射到低維向量空間中，并能保留原始網(wǎng)絡(luò)中節(jié)點信息與網(wǎng)絡(luò)結(jié)構(gòu)信息，之后將映射后的低維向量應(yīng)用于各種機(jī)器學(xué)習(xí)任務(wù)，比如節(jié)點分類[5-6]、可視化[7]、推薦系統(tǒng)[8-9]等。最開始對于網(wǎng)絡(luò)的研究是從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)出發(fā)的，忽略網(wǎng)絡(luò)中節(jié)點和關(guān)系的類型信息，即將網(wǎng)絡(luò)視為同構(gòu)網(wǎng)絡(luò)以矩陣分解[10]的方式利用鄰接矩陣實現(xiàn)節(jié)點嵌入。

然而，真實網(wǎng)絡(luò)中包含的節(jié)點類型是多樣化的，節(jié)點之間也存在著不同含義的作用關(guān)系，這種復(fù)雜的內(nèi)容單純依靠傳統(tǒng)網(wǎng)絡(luò)學(xué)習(xí)方法是無法提取的。另外，這種信息多樣化的異構(gòu)信息網(wǎng)絡(luò)中還包含描述節(jié)點自身特征的屬性信息，如文本、圖像等，因此需要有效的方式對這些信息進(jìn)行融合學(xué)習(xí)。異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)通過融合節(jié)點屬性信息和網(wǎng)絡(luò)結(jié)構(gòu)信息，探索各種異質(zhì)信息之間的潛在作用關(guān)系，在網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上捕捉節(jié)點的微觀特性，以獲取保留信息量更多的節(jié)點嵌入，提高任務(wù)性能，其整體學(xué)習(xí)框架如圖1所示。

對真實異構(gòu)網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)主要有3個優(yōu)點：（1）有效緩解現(xiàn)實世界網(wǎng)絡(luò)數(shù)據(jù)的高稀疏性、高維性問題，通過學(xué)習(xí)將異構(gòu)信息網(wǎng)絡(luò)中的節(jié)點和邊都轉(zhuǎn)化為低維稠密向量，降低了存儲空間和節(jié)點間度量復(fù)雜度；（2）有效解決真實網(wǎng)絡(luò)中異質(zhì)信息的融合利用，通過異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)模型能將不同類型節(jié)點映射到統(tǒng)一的低維向量空間中，有效融合節(jié)點屬性信息和節(jié)點間的關(guān)系信息，提高了嵌入有效性；（3）有效控制計算復(fù)雜度，異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)模型在設(shè)計時同時考慮大規(guī)模網(wǎng)絡(luò)問題，保證信息融合的計算復(fù)雜度。這些優(yōu)點更加符合實際應(yīng)用中的工作需求，使異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)成為目前網(wǎng)絡(luò)表示學(xué)習(xí)中的研究熱點。

2 異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)發(fā)展

在早期同構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)的研究過程中，基于矩陣分解的算法由于計算復(fù)雜度過高不適用于大規(guī)模網(wǎng)絡(luò)表示學(xué)習(xí)。后來受自然語言處理的啟發(fā)，DeepWalk[11]開始利用游走和Skip-gram結(jié)合的方式從序列中節(jié)點共現(xiàn)的角度學(xué)習(xí)節(jié)點嵌入；Node2vec[12]進(jìn)一步改進(jìn)游走方式，同時捕捉局部和全局結(jié)構(gòu)信息；LINE[13]則是從節(jié)點對間一階相似性和二階相似性出發(fā)學(xué)習(xí)節(jié)點嵌入；GraphWave[14]通過小波擴(kuò)散的方式學(xué)習(xí)節(jié)點結(jié)構(gòu)特征，將小波視為圖上概率分布。以上這些方式都是從網(wǎng)絡(luò)結(jié)構(gòu)的相似性出發(fā)，不同的是：Node2vec和GraphWave分別通過偏向游走和小波擴(kuò)散的方式捕捉網(wǎng)絡(luò)結(jié)構(gòu)，而LINE則是非常直接地保留目標(biāo)節(jié)點對之間的結(jié)構(gòu)相似度。但是，隨著同構(gòu)網(wǎng)絡(luò)研究的不斷發(fā)展，研究者們發(fā)現(xiàn)單純拓?fù)浣Y(jié)構(gòu)已經(jīng)很難再對網(wǎng)絡(luò)嵌入性能有更高的提升，而真實網(wǎng)絡(luò)中隨處可見的異質(zhì)信息（如實體附帶的屬性、文本信息）以及實體間的語義信息在嵌入過程中并沒有得到有效的利用。

圖1 異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)框架

異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)便是從網(wǎng)絡(luò)中這些復(fù)雜的異質(zhì)信息出發(fā)，將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息與多種異質(zhì)信息進(jìn)行有效的融合嵌入，并且能有效解決異構(gòu)信息網(wǎng)絡(luò)高稀疏性、高異質(zhì)性等特點。由于異構(gòu)信息網(wǎng)絡(luò)中節(jié)點類型和關(guān)系類型是最基本的異質(zhì)信息，受DeepWalk在同構(gòu)網(wǎng)絡(luò)中隨機(jī)游走策略的啟發(fā)，研究者們利用節(jié)點類型和關(guān)系類型設(shè)計元路徑來指導(dǎo)隨機(jī)游走方式，保留節(jié)點間具有人工經(jīng)驗的語義信息，Metapath2vec[15]、HINE[16]等便是利用此種方式實現(xiàn)對節(jié)點間特定關(guān)系的保留。DDRW[17]等則將截斷的隨機(jī)游走與層級Softmax進(jìn)行結(jié)合，配合分類目標(biāo)函數(shù)捕獲節(jié)點的相似性。ProxEmbed[18]等利用LSTM具有時間記憶性的特點，意圖將隨機(jī)游走序列模擬為節(jié)點間的“時間”演化過程匹配LSTM輸入，同時在嵌入過程中考慮節(jié)點異質(zhì)性。HNE[19]、PTE[20]等方法從簡化嵌入的角度出發(fā)，將原始異構(gòu)信息網(wǎng)絡(luò)根據(jù)不同內(nèi)容拆分為多個子圖進(jìn)行獨立嵌入。由于神經(jīng)網(wǎng)絡(luò)在計算機(jī)視覺領(lǐng)域迅速發(fā)展，并取得了非常不錯的成果，研究者們開始嘗試將相關(guān)方法應(yīng)用到網(wǎng)絡(luò)表示學(xué)習(xí)過程中，實現(xiàn)端到端學(xué)習(xí)。比如PinSage[21]借鑒卷積方式探索節(jié)點間的消息傳遞；DKN[22]受遷移學(xué)習(xí)的啟發(fā)，利用現(xiàn)有知識圖譜模型和CNN實現(xiàn)新聞推薦；HeGAN[23]等利用GAN提高網(wǎng)絡(luò)嵌入的魯棒性。

3 相關(guān)概念

為了學(xué)習(xí)異構(gòu)網(wǎng)絡(luò)中具有異質(zhì)性的拓?fù)浣Y(jié)構(gòu)，設(shè)計符合異構(gòu)網(wǎng)絡(luò)的隨機(jī)游走策略是十分必要的，因此許多工作中引入了人工經(jīng)驗，提出了元路徑的概念。

4 異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)方法

本節(jié)從異構(gòu)信息網(wǎng)絡(luò)的研究內(nèi)容出發(fā)，根據(jù)不同的研究內(nèi)容和方式將現(xiàn)有異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)方法分為4種：基于邊采樣的方法、基于隨機(jī)游走的方法、基于子圖的方法和基于圖神經(jīng)網(wǎng)絡(luò)的方法。

4.1 基于邊采樣的方法

網(wǎng)絡(luò)中的邊代表了兩個節(jié)點之間存在著某種關(guān)系，在網(wǎng)絡(luò)表示學(xué)習(xí)的過程中，研究者們常將邊作為衡量兩個節(jié)點是否相似的直接體現(xiàn)。在同構(gòu)網(wǎng)絡(luò)中，類似LINE[13]的方法在通過邊采樣學(xué)習(xí)節(jié)點嵌入時只需要考慮節(jié)點間拓?fù)浣Y(jié)構(gòu)關(guān)系即可。但是在異構(gòu)網(wǎng)絡(luò)中，需要考慮多樣化的邊類型信息，比如社交網(wǎng)絡(luò)中用戶之間有朋友和敵對關(guān)系。如果只考慮節(jié)點間有邊而不考慮邊的類型，則無法區(qū)分社交網(wǎng)絡(luò)中兩個實體間具體關(guān)系，可能導(dǎo)致最終給目標(biāo)推薦的用戶是目標(biāo)極為討厭的對象，造成推薦失敗。因此在從邊采樣角度出發(fā)進(jìn)行節(jié)點嵌入時必須考慮不同語義關(guān)系帶來的差異性，這樣才能準(zhǔn)確描述和保留節(jié)點間語義特性。

與以上單純預(yù)測節(jié)點語義關(guān)系的方法不同，Qu等[27]認(rèn)為不同類型的邊在邊采樣過程中的先后順序可能會對最終的嵌入效果產(chǎn)生不同的影響。因此模型在采樣過程中引入強(qiáng)化學(xué)習(xí)機(jī)制，劃分計劃模塊和學(xué)習(xí)模塊，前者根據(jù)LINE的評價結(jié)果計算類型采樣價值Q，后者利用查表和神經(jīng)網(wǎng)絡(luò)確定價值Q，兩者結(jié)合獲取最優(yōu)邊采樣類型序列。HEER[28]則認(rèn)為不同語義關(guān)系可能會存在不兼容的問題，導(dǎo)致原本比較相近的節(jié)點在投影到低維向量空間后變得較為疏遠(yuǎn)。因此HEER將節(jié)點根據(jù)語義關(guān)系進(jìn)行分組，然后進(jìn)行獨立嵌入，利用邊向量定義節(jié)點對的類型接近度，用來度量邊與類型的耦合程度：

基于邊采樣的方法將關(guān)注點放在網(wǎng)絡(luò)的局部結(jié)構(gòu)特征，每次只涉及部分節(jié)點，計算復(fù)雜度低。另外，異構(gòu)網(wǎng)絡(luò)中的邊采樣以邊的類型為主導(dǎo)，考慮節(jié)點間語義關(guān)系，更有利于完成類似社區(qū)內(nèi)用戶推薦等任務(wù)。但是邊采樣涉及的關(guān)系類型較為簡單，難以推測復(fù)雜語義關(guān)系。

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

雖然這種方法在構(gòu)造鄰居節(jié)點時考慮了節(jié)點類型，但是在利用Softmax計算共現(xiàn)概率時并沒有考慮節(jié)點類型信息帶來的影響。因此在原始模型的基礎(chǔ)之上進(jìn)一步改進(jìn)異構(gòu)Skip-gram模型概率計算，設(shè)計考慮節(jié)點類型的負(fù)采樣，使Softmax計算時只考慮特定類型節(jié)點，降低計算復(fù)雜度：

基于隨機(jī)游走的方法能有效捕獲遠(yuǎn)距離節(jié)點的相似度信息，同時也能將節(jié)點屬性信息和局部結(jié)構(gòu)特征融入嵌入過程中，提高信息保留量。由于隨機(jī)游走帶來的感受野非常大，并且能非常靈活地融入各種輔助信息，因此是當(dāng)前的研究熱點。

4.3 基于子圖的方法

圖2 SPE子圖模式mi

除了以上通過游走路徑聚合方式組成新的子圖，還有些方法直接根據(jù)實體類型將網(wǎng)絡(luò)拆分成不同的子圖。比如，HNE[19]根據(jù)圖片和文本類型將原始網(wǎng)絡(luò)拆分成兩個只包含圖片或文本的子網(wǎng)絡(luò)，并使用現(xiàn)有方式分別對其進(jìn)行嵌入，最終實現(xiàn)跨模態(tài)的相似度度量。PTE[20]根據(jù)文本中僅有的部分標(biāo)簽數(shù)據(jù)，將原異構(gòu)文本網(wǎng)絡(luò)拆分成3個子網(wǎng)絡(luò)——word-word網(wǎng)絡(luò)、word-document網(wǎng)絡(luò)和word-label網(wǎng)絡(luò)，并對上述網(wǎng)絡(luò)分別利用LINE進(jìn)行學(xué)習(xí)得到不同類型對象的向量表示，之后利用詞向量的平均求和獲得任意文本的嵌入表示。SHINE[37]根據(jù)情感得分和用戶信息將原始網(wǎng)絡(luò)拆分為社交網(wǎng)絡(luò)、情感網(wǎng)絡(luò)和簡介網(wǎng)絡(luò)，通過3個網(wǎng)絡(luò)的獨立嵌入分別獲得名人和普通人的3種向量表示，隨后進(jìn)行簡單聚合獲得最終嵌入，最后利用兩種向量的情感符號預(yù)測進(jìn)行模型優(yōu)化。

另外，還有一些任務(wù)驅(qū)動型拆分方法，根據(jù)不同任務(wù)將原始異構(gòu)網(wǎng)絡(luò)拆分成有利于任務(wù)目標(biāo)的子網(wǎng)絡(luò)，比如PGCN[38]為實現(xiàn)推薦任務(wù)，將網(wǎng)絡(luò)拆分成3個子網(wǎng)絡(luò)——user-item、item-item和user-subseq，分別對應(yīng)用戶的商品偏好、商品依賴和用戶相似度信息。同時，模型根據(jù)節(jié)點類型和距離篩選鄰居節(jié)點并進(jìn)行加權(quán)聚合產(chǎn)生虛擬節(jié)點解決節(jié)點鄰居數(shù)目多變問題，然后利用卷積操作對虛擬節(jié)點特征進(jìn)行聚合學(xué)習(xí)，保留網(wǎng)絡(luò)局部特征。HGAT[39]與之類似，為實現(xiàn)用戶屬性標(biāo)簽的推理，同樣將原始網(wǎng)絡(luò)拆分成3個子網(wǎng)絡(luò)——attribute-item、item-user和user-user，以層級推進(jìn)的方式依次實現(xiàn)item和user的嵌入，同時給出了3種聚合方法有效性的討論。

基于子圖的方法通常是將原始網(wǎng)絡(luò)根據(jù)研究內(nèi)容或研究任務(wù)拆分成不同的子網(wǎng)絡(luò)，對每個子網(wǎng)絡(luò)采用不同的方式進(jìn)行獨立嵌入，降低了多種信息融合嵌入的難度，同時也降低了嵌入計算復(fù)雜度。另外，由于拆分后的子網(wǎng)絡(luò)具有某種特定含義，且包含的節(jié)點類型比較一致，因此更有利于針對特定任務(wù)進(jìn)行網(wǎng)絡(luò)嵌入。

4.4 基于圖神經(jīng)網(wǎng)絡(luò)的方法

人工智能和機(jī)器學(xué)習(xí)在圖像和自然語言處理等方面取得的顯著成果，鼓勵了更多的研究者將深度神經(jīng)網(wǎng)絡(luò)應(yīng)用于網(wǎng)絡(luò)表示學(xué)習(xí)中，期望能通過無監(jiān)督或半監(jiān)督的方式自主學(xué)習(xí)網(wǎng)絡(luò)中的非線性特征，比如SHINE[37]等利用無監(jiān)督自編碼器實現(xiàn)自適應(yīng)的關(guān)鍵信息提取等。受益于CNN[40]在計算機(jī)視覺上取得的顯著效果，GCN[41]和GraphSage[42]將CNN的卷積操作適配于在非矩陣結(jié)構(gòu)的不規(guī)則網(wǎng)絡(luò)中，利用圖的Laplacian矩陣作為規(guī)則化輸入，進(jìn)行圖卷積操作。但是這種同構(gòu)方法并不適用于類型稀疏的大規(guī)模異構(gòu)信息網(wǎng)絡(luò)。隨著GNN[43]（圖神經(jīng)網(wǎng)絡(luò)）可解釋性的提出，如何有效利用圖神經(jīng)網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)嵌入進(jìn)入了研究高潮期。GNN的核心思想很簡單，即通過迭代的方式將目標(biāo)節(jié)點的鄰居信息不斷聚合到的嵌入中，從而達(dá)到節(jié)點間信息傳遞的效果。具體第次迭代運算如下所示：

隨著GNN迭代次數(shù)的增加，能捕獲的局部特征信息就越接近于全局特征信息。HetGNN[44]根據(jù)節(jié)點類型對鄰居節(jié)點進(jìn)行聚合，并利用兩個RNN實現(xiàn)網(wǎng)絡(luò)嵌入：第一個RNN用于編碼每個節(jié)點的特征交互以獲得節(jié)點的上下文嵌入；另一個RNN將鄰居分組上下文嵌入進(jìn)行聚合，進(jìn)一步引入注意力機(jī)制度量不同類型節(jié)點的影響程度。受到局部信息迭代聚合的啟發(fā)，PinSage[21]提出局部圖卷積模型，將圖卷積中的矩陣運算替代為消息傳遞的聚合運算，根據(jù)當(dāng)前節(jié)點子節(jié)點訪問次數(shù)確定鄰居節(jié)點的重要程度，并不斷將鄰居特征進(jìn)行加權(quán)聚合到中心節(jié)點。IntentGC[45]在此基礎(chǔ)之上設(shè)計快速圖卷積模型，在鄰居聚合過程中采用多尺度過濾器，從多個角度對不同類型的鄰居節(jié)點進(jìn)行加權(quán)聚合，如式（7）所示，以此降低圖卷積計算復(fù)雜度，使其能有效部署在十億級別網(wǎng)絡(luò)中運行。

DKN[22]利用遷移學(xué)習(xí)的思想，結(jié)合現(xiàn)有的知識圖譜模型設(shè)計了KCNN，將文本和實體利用卷積的方式保持對齊關(guān)系，并利用知識圖譜模型實現(xiàn)新聞內(nèi)容的預(yù)訓(xùn)練，然后將實體、上下文和詞嵌入共同匹配卷積輸入，同時引入候選新聞與用戶的注意力權(quán)重，實現(xiàn)最終用戶與新聞的推薦任務(wù)。NeRank[46]則利用不同嵌入方式對問答社區(qū)內(nèi)的用戶和問題文本進(jìn)行獨立嵌入，然后利用CNN實現(xiàn)排名成績的計算。

GraphGAN[47]在假設(shè)節(jié)點之間的鏈接具有潛在分布的前提下，通過對抗性訓(xùn)練讓生成器生成的節(jié)點鏈接分布不斷逼近真實潛在分布。它的出現(xiàn)使GAN開始在網(wǎng)絡(luò)表示方面綻放光芒，以對抗學(xué)習(xí)的方式探索網(wǎng)絡(luò)中潛在的隱藏信息。NetRA[48]利用LSTM完成正則化自動編碼器功能實現(xiàn)對游走路徑信息的自主學(xué)習(xí)，將輸出的路徑嵌入作為真實樣本，利用GAN進(jìn)行對抗性訓(xùn)練學(xué)習(xí)網(wǎng)絡(luò)異質(zhì)結(jié)構(gòu)分布，使嵌入具有更強(qiáng)的魯棒性，提高抗干擾能力。

為了有效利用邊類型生成具有特定語義關(guān)系的目標(biāo)節(jié)點，HeGAN[23]提出泛化生成器，在Metapath2vec初始化節(jié)點向量的基礎(chǔ)上，意圖從連續(xù)分布中直接采樣“潛在”節(jié)點，同時在生成器和判別器中引入關(guān)系類型感知以捕獲更加豐富的語義關(guān)系，實現(xiàn)對訓(xùn)練集中不可見節(jié)點的正確嵌入。

基于圖神經(jīng)網(wǎng)絡(luò)的方法利用神經(jīng)網(wǎng)絡(luò)強(qiáng)大的自主學(xué)習(xí)能力對異構(gòu)網(wǎng)絡(luò)中的異質(zhì)信息進(jìn)行自主嵌入，簡化嵌入過程，在實現(xiàn)端到端學(xué)習(xí)的同時降低模型構(gòu)造難度。目前神經(jīng)網(wǎng)絡(luò)對于各種屬性信息（如圖片、文本等）都具有良好的學(xué)習(xí)能力，能有效處理異構(gòu)信息網(wǎng)絡(luò)中節(jié)點和邊的額外屬性信息，減少信息損失。圖神經(jīng)網(wǎng)絡(luò)能根據(jù)不同的任務(wù)靈活搭建，因此更受研究者們的喜愛。

5 模型歸納

本節(jié)從主要研究內(nèi)容、嵌入方法、具體應(yīng)用等方面對近幾年的異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)的代表性研究算法進(jìn)行了相關(guān)內(nèi)容的整理，結(jié)果見表1。異構(gòu)信息網(wǎng)絡(luò)中節(jié)點和邊的類型信息是最容易獲取的異質(zhì)信息，因此大多數(shù)算法從類型信息出發(fā)對節(jié)點進(jìn)行低維嵌入，這與表1中大部分學(xué)習(xí)模型的主要研究內(nèi)容保持一致。此類算法大多關(guān)注節(jié)點語義關(guān)系，由此產(chǎn)生的節(jié)點嵌入多用于節(jié)點分類、鏈路預(yù)測等任務(wù)，基于邊采樣和隨機(jī)游走的方法便是如此。此外，單純利用類型信息的方法算法復(fù)雜度較低，在大規(guī)模網(wǎng)絡(luò)中也能達(dá)到不錯的運行效率?；谧訄D嵌入的方法從簡化網(wǎng)絡(luò)嵌入角度出發(fā)，依據(jù)類型信息和任務(wù)內(nèi)容拆分重組原始網(wǎng)絡(luò)形成不同的子網(wǎng)絡(luò)，利用已有網(wǎng)絡(luò)表示學(xué)習(xí)方法獨立嵌入，最后將子圖嵌入結(jié)果進(jìn)行組合或直接利用。這種類似分治的算法將復(fù)雜問題簡單化，降低了整個算法的計算復(fù)雜度，且在不同子網(wǎng)絡(luò)中能進(jìn)行針對性信息融合。此外，拆分后的子圖將具有相似內(nèi)容或相同偏好的節(jié)點聚集在一起，更有利于實現(xiàn)社區(qū)發(fā)現(xiàn)、近似查詢等任務(wù)。但是根據(jù)某種特定信息對原始圖進(jìn)行拆分會造成一些信息的截斷，導(dǎo)致信息丟失，在一定程度上降低嵌入有效性?；趫D神經(jīng)網(wǎng)絡(luò)的方法實現(xiàn)端到端的學(xué)習(xí)方式，將整個網(wǎng)絡(luò)作為輸入，考慮不同異質(zhì)信息之間的潛在聯(lián)系，在整個嵌入過程中利用不同的嵌入模塊有效融合更多的異質(zhì)信息，保證整個模型具有足夠的魯棒性和有效性。此類方法在設(shè)計時更加側(cè)重于實際應(yīng)用，大部分是任務(wù)驅(qū)動型算法，多用于推薦系統(tǒng)中。雖然這類算法在模型設(shè)計時靈活性更高，難度更低，能利用各種類型的內(nèi)容信息，但是在有效融合不同嵌入模塊時控制計算復(fù)雜度仍是比較困難的點。

表1 主要模型歸納與概括

6 結(jié)束語

異構(gòu)信息網(wǎng)絡(luò)中具有很多能描述個體特征的異質(zhì)性信息，更加逼近于真實世界中實體及實體間的關(guān)系，因此異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)在近幾年成為網(wǎng)絡(luò)表示學(xué)習(xí)的熱點內(nèi)容。雖然目前的算法都對異構(gòu)信息網(wǎng)絡(luò)中異質(zhì)性信息的保留進(jìn)行了較為有效的嘗試，但是大部分算法只利用了單一的異質(zhì)信息，比如常用的文本信息，而視頻信息、音頻信息等還未得到有效利用，而且大部分算法都無法達(dá)到工業(yè)級應(yīng)用，距離實際應(yīng)用還有很長一段距離。因此異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)的研究還具有很大的發(fā)展空間，在未來工作中可以從以下幾個方面著手研究。

（1）異構(gòu)信息網(wǎng)絡(luò)中異質(zhì)信息的融合

異構(gòu)信息網(wǎng)絡(luò)中除了類型信息，還有多種模態(tài)的屬性信息，比如數(shù)值、圖像、文本、音頻等。這些信息都是異構(gòu)網(wǎng)絡(luò)中可以利用的有效信息，若能有效保留這些具有明顯特異性的個體信息，對于網(wǎng)絡(luò)嵌入性能而言能有很好的提升。目前大多數(shù)異構(gòu)表示學(xué)習(xí)算法主要有3種方式保留異質(zhì)性信息：第一種是制定游走策略利用類型信息，在嵌入過程中融入屬性特征；第二種是將異構(gòu)信息網(wǎng)絡(luò)拆分成不同含義的子圖，利用現(xiàn)有嵌入模型簡化嵌入難度，最終對嵌入結(jié)果進(jìn)行聚合；第三種是利用目前發(fā)展火熱的圖神經(jīng)網(wǎng)絡(luò)實現(xiàn)端到端的學(xué)習(xí)方式，以原始網(wǎng)絡(luò)作為輸入，在嵌入過程中利用不同模塊學(xué)習(xí)不同異質(zhì)信息，但是不同模塊的有效融合是最大的難題。這3種方法的使用也不一定完全獨立，比如NetRA[48]便是第一種和第三種方式的組合。因此，設(shè)計一種對異質(zhì)信息具有高容納性的靈活嵌入工具是異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)未來的研究方向之一。

（2）大規(guī)模網(wǎng)絡(luò)算法有效性

而今各種網(wǎng)絡(luò)規(guī)模在不斷擴(kuò)大，大部分算法模型都是基于小規(guī)模網(wǎng)絡(luò)設(shè)計的，無法直接應(yīng)用于工業(yè)級的大規(guī)模網(wǎng)絡(luò)分析任務(wù)中，并沒有太高的實際應(yīng)用價值。為了提高大規(guī)模網(wǎng)絡(luò)上的算法有效性，設(shè)計符合實際工作的工業(yè)級算法，許多大企業(yè)和科研團(tuán)隊開始進(jìn)行合作研究，并取得了一些不錯的成果，比如PinSage[21]被設(shè)計部署于有30億節(jié)點規(guī)模的Pinterest網(wǎng)站，IntentGC[45]被設(shè)計部署于有30億節(jié)點規(guī)模的淘寶網(wǎng)站。這些工作都是根據(jù)實際工作而設(shè)計的工業(yè)級算法，能在有效時間內(nèi)完成對大規(guī)模網(wǎng)絡(luò)學(xué)習(xí)的任務(wù)。因此從算法的運行效率出發(fā)，設(shè)計能實際落地的工業(yè)級圖嵌入算法也是目前網(wǎng)絡(luò)表示學(xué)習(xí)發(fā)展的主要趨勢。

（3）模型泛化能力

異構(gòu)信息網(wǎng)絡(luò)對應(yīng)現(xiàn)實世界中的真實群體，因此網(wǎng)絡(luò)的規(guī)模和內(nèi)容并不是恒久不變的，會隨著網(wǎng)絡(luò)新節(jié)點的加入以及節(jié)點間交互的產(chǎn)生而變化。如網(wǎng)絡(luò)中會出現(xiàn)新的節(jié)點，甚至是孤立點，而這些新節(jié)點對于已有模型的執(zhí)行而言并不友好。因為現(xiàn)有模型在訓(xùn)練過程中使用的訓(xùn)練集基本都是利用網(wǎng)絡(luò)歷史數(shù)據(jù)構(gòu)造的，因此模型在訓(xùn)練過程中只能獲取已有節(jié)點的內(nèi)在特性，對于訓(xùn)練過程中并未出現(xiàn)的新節(jié)點可能無法進(jìn)行有效的嵌入。比如在商品推薦系統(tǒng)中，新加入的用戶并沒有購買任何物品，能利用的信息僅有注冊時的一些個人信息，此時推薦模型便無法根據(jù)用戶歷史記錄對用戶進(jìn)行有效的商品推薦。隨著GAN在計算機(jī)視覺上的有效發(fā)展，網(wǎng)絡(luò)表示學(xué)習(xí)的工作者們開始利用GAN提高模型泛化能力[23,48]，以解決實際應(yīng)用中經(jīng)常出現(xiàn)的“冷啟動”問題。此外，良好地運用節(jié)點屬性信息也可以提升模型泛化能力。

（4）結(jié)合具體應(yīng)用

通過網(wǎng)絡(luò)表示學(xué)習(xí)得到的低維向量表示本質(zhì)是為后續(xù)的應(yīng)用場景服務(wù)的，比如推薦系統(tǒng)等。隨著圖神經(jīng)網(wǎng)絡(luò)的發(fā)展，研究者們開始根據(jù)具體任務(wù)設(shè)計端到端的學(xué)習(xí)模型。這種針對具體任務(wù)設(shè)計具體算法的方式，更加符合現(xiàn)在工業(yè)生產(chǎn)中的需要，且能根據(jù)具體任務(wù)中的一些特殊信息進(jìn)行模型微調(diào)，學(xué)得具有針對性的嵌入向量。如何有效根據(jù)任務(wù)目標(biāo)設(shè)計具有實際應(yīng)用價值的算法模型，也是未來異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)有價值的研究方向之一。

[1] TYLENDA T, ANGELOVA R, BEDATHUR S. Towards time-aware link prediction in evolving social networks[C]//Proceedings of the 3rd Workshop on Social Network Mining and Analysis. [S.l.:s.n.], 2009.

[2] 顧秋陽, 琚春華, 吳功興. 融入用戶合作與領(lǐng)導(dǎo)激勵的社交網(wǎng)絡(luò)知識傳播模型[J]. 電信科學(xué), 2020, 36(10): 172-182.

GU Q Y, JU C H, WU G X. Knowledge communication model of social network with user cooperation and leadership encouragement[J]. Telecommunications Science, 2020, 36(10): 172-182.

[3] THEOCHARIDIS A, VAN DONGEN S, ENRIGHT A J, et al. Network visualization and analysis of gene expression data using BioLayout Express 3D[J]. Nature Protocols, 2009, 4 (10): 1535.

[4] 尹贏, 吉立新, 黃瑞陽, 等. 網(wǎng)絡(luò)表示學(xué)習(xí)的研究與發(fā)展[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 2019, 5(2): 77-87.

YIN Y, JI L X, HUANG R Y, et al. Research and development of network representation learning[J]. Chinese Journal of Network and Information Security, 2019, 5(2): 77-87.

[5] TANG J, AGGARWAL C, LIU H. Node classification in signed social networks[C]//Proceedings of the 2016 SIAM International Conference on Data Mining. [S.l.:s.n.], 2016: 54-62.

[6] THEOCHARIDIS A, VAN DONGEN S, ENRIGHT A J, et al. Network visualization and analysis of gene expression data using BioLayout Express 3D[J]. Nature Protocols, 2009, 4(10): 1535.

[7] 鄔少清, 董一鴻, 王雄, 等. 基于高階相似性的屬性網(wǎng)絡(luò)表示學(xué)習(xí)[J]. 電信科學(xué), 2020, 36(12): 20-32.

WU S Q, DONG Y H, WANG X, et al. Learning attribute network algorithm based on high-order similarity[J]. Telecommunications Science, 2020, 36(12): 20-32.

[8] ZHOU C, LIU Y, LIU X, et al. Scalable graph embedding for asymmetric proximity[C]//Proceedings of Thirty-First AAAI Conference on Artificial Intelligence. [S.l.:s.n.], 2017.

[9] 周晶, 孫喜民, 于曉昆, 等. 知識圖譜與數(shù)據(jù)應(yīng)用——智能推薦[J]. 電信科學(xué), 2019, 35(8): 165-172.

ZHOU J, SUN X M, YU X K, et al. Knowledge graph and data application: intelligent recommendation[J]. Telecommunications Science, 2019, 35(8): 165-172.

[10] BALASUBRAMANIAN M, SCHWARTZ E L J S. The isomap algorithm and topological stability[J]. Science, 2002, 295 (5552): 7.

[11] PEROZZI B, AL-RFOU R, SKIENA S. Deepwalk: online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2014: 701-710.

[12] GROVER A, LESKOVEC J. Node2vec: scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2016: 855-864.

[13] TANG J, QU M, WANG M, et al. LINE: large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. New York: ACM Press, 2015: 1067-1077.

[14] DONNAT C, ZITNIK M, HALLAC D, et al. Learning structural node embeddings via diffusion wavelets[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2018: 1320-1329.

[15] DONG Y, CHAWLA N V, SWAMI A. Metapath2vec: scalable representation learning for heterogeneous networks[C]// Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2017: 135-144.

[16] HUANG Z, MAMOULIS N J A P A. Heterogeneous information network embedding for meta path based proximity[J]. arXiv: 1701. 05291v1, 2017.

[17] LI J, ZHU J, ZHANG B. Discriminative deep random walk for network classification[C]//Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). [S.l.:s.n.], 2016: 1004-1013.

[18] LIU Z, ZHENG V W, ZHAO Z, et al. Semantic proximity search on heterogeneous graph by proximity embedding[C]//Proceedings of Thirty-First AAAI Conference on Artificial Intelligence. [S.l.:s.n.], 2017.

[19] CHANG S, HAN W, TANG J, et al. Heterogeneous network embedding via deep architectures[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2015: 119-128.

[20] TANG J, QU M, MEI Q. PTE: predictive text embedding through large-scale heterogeneous text networks[C]// Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2015: 1165-1174.

[21] YING R, HE R, CHEN K, et al. Graph convolutional neural networks for Web-scale recommender systems[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2018: 974-983.

[22] WANG H, ZHANG F, XIE X, et al. DKN: deep knowledge-aware network for news recommendation[C]// Proceedings of the 2018 World Wide Web Conference. [S.l.:s.n.], 2018: 1835-1844.

[23] HU B, FANG Y, SHI C. Adversarial learning on heterogeneous information networks[C]//Proceedings of KDD 2019. [S.l.:s.n.], 2019.

[24] SHI C, LI Y, ZHANG J, et al. A survey of heterogeneous information network analysis[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 29 (1): 17-37.

[25] FU TY, LEE WC, LEI Z. Hin2vec: Explore meta-paths in heterogeneous information networks for representation learning[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. New York: ACM Press, 2017: 1797-1806.

[26] YANG L, ZHANG Z, CAI X, et al. Citation recommendation as edge prediction in heterogeneous bibliographic network: a network representation approach[J]. IEEE Access, 2019(7): 23232-23239.

[27] QU M, TANG J, HAN J. Curriculum learning for heterogeneous star network embedding via deep reinforcement learning[C]//Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. New York: ACM Press, 2018: 468-476.

[28] SHI Y, ZHU Q, GUO F, et al. Easing embedding learning by comprehensive transcription of heterogeneous information networks[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2018: 2190-2199.

[29] YIN Y, JI L, HUANG R, et al. Heterogeneous network representation learning method based on meta-path[C]//Proceedings of 2019 IEEE 4th International Conference on Cloud Computing and Big Data Analysis (ICCCBDA). Piscataway: IEEE Press, 2019: 664-670.

[30] WANG X, JI H, SHI C, et al. Heterogeneous graph attention network[C]//Proceedings of the World Wide Web Conference. [S.l.:s.n.], 2019: 2022-2032.

[31] VELI?KOVI? P, CUCURULL G, CASANOVA A, et al. Graph attention networks[J]. arXiv preprint arXiv: 1710. 10903, 2017.

[32] ZHUO W, ZHAN Q, LIU Y, et al. Context attention heterogeneous network embedding[J]. Computational Intelligence and Neuroscience, 2019.

[33] LU M, WEI X, YE D, et al. A unified link prediction framework for predicting arbitrary relations in heterogeneous academic networks[J]. IEEE Access, 2019(7): 124967-124987.

[34] LIU Z, ZHENG V W, ZHAO Z, et al. Distance-aware dag embedding for proximity search on heterogeneous graphs[C]//Proceedings of Thirty-Second AAAI Conference on Artificial Intelligence. [S.l.:s.n.], 2018.

[35] LIU Z, ZHENG V W, ZHAO Z, et al. Interactive paths embedding for semantic proximity search on heterogeneous graphs[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2018: 1860-1869.

[36] LIU Z, ZHENG V W, ZHAO Z, et al. Subgraph-augmented path embedding for semantic user search on heterogeneous social network[C]//Proceedings of the 2018 World Wide Web Conference. [S.l.:s.n.], 2018: 1613-1622.

[37] WANG H, ZHANG F, HOU M, et al. SHINE: signed heterogeneous information network embedding for sentiment link prediction[C]//Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining. New York: ACM Press, 2018: 592-600.

[38] XU Y, ZHU Y, SHEN Y, et al. Learning shared vertex representation in heterogeneous graphs with convolutional networks for recommendation[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. [S.l.:s.n.], 2019: 4620-4626.

[39] CHEN W, GU Y, REN Z, et al. Semi-supervised user profiling with heterogeneous graph attention networks[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence. [S.l.:s.n.], 2019: 2116-2122.

[40] KRIZHEVSKY A, SUTSKEVER I, HINTON G E. Imagenet classification with deep convolutional neural networks[C]//Proceedings of Advances in Neural Information Processing Systems. [S.l.:s.n.], 2012: 1097-1105.

[41] KIPF T N, WELLING M J A P A. Semi-supervised classification with graph convolutional networks[C]//Proceedings of the 5th International Conference on Learning Representations(ICLR). [S.l.:s.n.], 2017.

[42] HAMILTON W, YING Z, LESKOVEC J. Inductive representation learning on large graphs[C]//Proceedings of Advances in Neural Information Processing Systems. [S.l.:s.n.], 2017: 1024-1034.

[43] XU K, HU W, LESKOVEC J, et al. How powerful are graph neural networks?[J]. arXiv: 1810.00826v3, 2018.

[44] ZHANG C, SONG D, HUANG C, et al. Heterogeneous graph neural network[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2019: 793-803.

[45] ZHAO J, ZHOU Z, GUAN Z, et al. IntentGC: a scalable graph convolution framework fusing heterogeneous information for recommendation[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2019: 2347-2357.

[46] LI Z, JIANG JY, SUN Y, et al. Personalized question routing via heterogeneous network embedding[C]//Proceedings of Proceedings of the AAAI Conference on Artificial Intelligence. [S.l.:s.n.], 2019: 192-199.

[47] WANG H, WANG J, WANG J, et al. Graphgan: graph representation learning with generative adversarial nets[C]//Proceedings of Thirty-Second AAAI Conference on Artificial Intelligence. [S.l.:s.n.], 2018.

[48] YU W, ZHENG C, CHENG W, et al. Learning deep network representations with adversarially regularized autoencoders[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM Press, 2018: 2663-2671.

A survey of heterogeneous network representation learning for complex networks

YAN Mingjiang, DONG Yihong, SU Jiangjun, CHEN Huahui, QIAN Jiangbo

Faculty of Electrical Engineering and Computer Science, Ningbo University, Ningbo 315211, China

Heterogeneous information networks contain rich information about node and link, and have some characteristics, such as complex heterogeneity, high sparsity, high-dimensionality of attributes, etc, which brings huge challenges to network representation learning tasks. The heterogeneous network representation learning learns low-dimensional feature vectors that are more conducive to downstream machine learning tasks by effectively integrating diverse heterogeneous information and structural information in the embedding process. It conducts a relatively comprehensive analysis and discussion of the research status in recent years, starting from the research granularity of the heterogeneous network representation learning method. Firstly, the motivation of network representation learning and the research history of heterogeneous information network representation learning in recent years was discussed. Then some representative algorithm models were classified, followed by the summary of their main research contents and embedding skills. Finally, some possible directions and valuable contents of heterogeneous information network representation learning research in future work were listed.

network representation learning, heterogeneous information network, graph embedding, graph neural network, heterogeneous information

TP391

A

10.11959/j.issn.1000?0801.2021013

2020?04?26；

2020?12?10

董一鴻，dongyihong@nbu.edu.cn

浙江省自然科學(xué)基金資助項目（No.LY20F020009，No.LZ20F020001）；國家自然科學(xué)基金資助項目（No.61572266）；寧波市自然科學(xué)基金資助項目（No.202003N4086）

The Natural Science Foundation of Zhejiang Province (No.LY20F020009, No.LZ20F020001), The National Natural Science Foundation of China (No.61572266), Ningbo Natural Science Foundation (No.202003N4086)

顏銘江（1996? ），男，寧波大學(xué)碩士生，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘。

董一鴻（1969? ），男，博士，寧波大學(xué)教授、碩士生導(dǎo)師，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘、人工智能。

蘇江軍（1994? ），男，寧波大學(xué)碩士生，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘。

陳華輝（1964? ），男，博士，寧波大學(xué)教授，主要研究方向為數(shù)據(jù)處理與挖掘、云計算。

錢江波（1974? ），男，博士，寧波大學(xué)教授，主要研究方向為數(shù)據(jù)處理與挖掘、邏輯電路設(shè)計、多維索引與查詢優(yōu)化。