面向異質信息網絡的表示學習方法研究綜述*

周 慧，趙中英，李 超

山東科技大學 計算機科學與工程學院，山東 青島 266590

1 引言

網絡是表達事物之間關聯關系的有效載體，由節點和鏈接關系（邊）組成，在日常生活中無處不在。異質信息網絡是一種特殊類型的網絡，由多種類型的節點、鏈接關系以及屬性信息組成，具有大規模、異質性等特點。隨著信息時代的發展，所面臨的信息網絡越來越復雜，各行各業對數據處理的速度和有效性也提出了更高的需求。采用鄰接矩陣這種高維稀疏的編碼方式來表示網絡中的節點，很難被機器學習算法處理。網絡表示學習（或網絡嵌入）采用低維向量的形式表示網絡中的組件，打破了網絡固有的節點和邊的形態，同時最大程度地保留原網絡中的結構信息和特性。由于低維的向量很容易被機器學習算法處理，因而越來越受到學術界和產業界的廣泛關注，也有效地運用到了節點分類[1-2]、鏈接預測[3-4]、社區發現[5-6]和推薦[7-8]等任務中。最初的網絡表示學習算法注重對原網絡的復現，即最大程度保留原網絡中的信息。相關研究工作包括DeepWalk[9]、LINE（large-scale information network embedding）[10]、node2vec[11]和 GraRep（graph representations）[12]等。雖然這些算法越來越精確地保留了節點在原網絡中的相對位置關系，但它們只是單純地借助于拓撲結構信息，學得的表征向量缺乏對后續實驗任務的區別力和推理能力。現實世界的網絡中普遍存在著除拓撲信息之外的異質信息，包括節點或邊上的標簽信息、社區信息和屬性信息等。充分利用這些異質信息有助于學得更具推理能力和區別力的表征向量。

融合異質信息的網絡表示學習工作相繼被提出，在很大程度上推動了該領域的發展。對這些算法進行分類梳理有助于了解和掌握該領域的學術思路和動態。在本文中，首先創建了一個統一的分類框架，并在每個類別下列舉了一些代表性算法。進一步地，從橫向上對各類別下的代表性算法進行了介紹，包括其主要的理論方法和思想。之后，又縱向對比了這些算法的時間復雜度、優缺點和評估實驗等。此外，整理了實驗中一些常用的數據集，并給出了簡單的屬性介紹和相關鏈接。在文章最后，進一步指出了該領域的挑戰和未來可能的研究方向。

1.1 相關定義

1.1.1 異質信息網絡

根據石川等人在文獻[13]中提出的異質信息網絡的定義，進一步對本文所涉及的異質信息網絡給出以下形式化的定義。

1.1.2 網絡表示學習

定義2（網絡表示學習[14]（network representation learning，NRL））給定一網絡G(V,E)，其中V表示網絡G中的節點集，E表示網絡G中的邊集。目標是為網絡中的節點v∈V（或邊、子圖等）學習一映射關系f:v→rv∈Rd，其中rv是為節點v學得的低維稠密向量，d＜＜|V|，轉換函數f用于捕獲定義在原網絡中的相似度信息。

結合定義1，進一步給出異質信息網絡上的表示學習的形式化定義，如下所示。

定義3（異質信息網絡表示學習）給定一異質信息網絡G(V,E,T,φ,ψ,H)，目標是為網絡中的節點v∈V（或邊、子圖等）學習一映射關系f:v→rv∈Rd，d＜＜|V|，rv是為節點v學得的低維稠密向量，其中包含了節點在原網絡中的異質信息。

1.2 符號和解釋

進一步總結了本文中用到的主要符號及其解釋，如表1所示。

Table 1 Notations used in this paper表1 本文中的常用符號

2 算法分類介紹

Fig.1 Classification framework for algorithms(color of algorithm is corresponding to methodology)圖1 算法分類框架（算法的顏色與理論相對應）

針對融合異質信息的網絡表示學習算法，首先設計了一個統一的分類框架，并在每個類別下列舉了一些代表性算法。如圖1所示，該框架首先以信息類型作為分類依據將算法分成了四大類，即：標簽/社區信息、屬性信息、多種類型信息以及異構網絡。其中前三類面向的是帶有輔助信息的網絡，第四類面向的是異構網絡。接下來，在每個類別下進一步劃分成有監督和無監督這兩個子類，并列舉了相應的代表性算法。此外，框圖的最下方是這些算法用到的基礎理論方法，包括矩陣分解、神經網絡、自定義損失函數以及其他的綜合框架。采用不同的顏色進行標注，并與相應算法的顏色相對應。在下文中，將對一些代表性算法進行分類介紹。

2.1 標簽信息輔助的網絡表示學習

2.1.1 基于矩陣分解的方法

MMDW（max-margin DeepWalk）[15]是基于矩陣分解的有監督的表示學習模型。該模型首先從理論上證明了DeepWalk相當于矩陣分解；然后將矩陣分解得到的表征向量輸入到支持向量機[16]（support vector machine，SVM）中進行訓練，并根據分類邊界產生有偏置的梯度方向；之后根據該方向進行向量更新，以增大表示向量在分類器中的分類間隔。總的來說，該模型共同優化最大間隔分類器和目標矩陣分解模型，使得學得的表征向量具有對后續機器學習任務的區別力。

與之類似的算法還包括DDRW（discriminative deep random walk）[17]、TLINE[18]以 及 SemNE（semisupervised network embedding）[19]等。這些算法共同的優點是能夠直接優化分類損失，使學得的表征向量具有區別力，但這些算法容易產生過擬合。

2.1.2 基于神經網絡的方法

Kipf等人提出了GCN（graph convolution networks）[20]算法，運用卷積神經網絡來處理圖結構數據。該算法首先將圖的拉普拉斯矩陣的特征向量矩陣通過傅里葉變換轉化到譜空間上，然后進行卷積操作。然后通過部分帶標簽的節點對模型進行訓練，從而實現半監督學習。此外，作者還設計了一種簡單有效的層級傳播規則，通過這種方式可快速有效地處理圖數據上的半監督分類問題。特別地，在不借助任何外部信息的情況下，該模型所學得的圖節點向量表示和DeepWalk算法結果是極為相似的，這也表明了圖卷積神經網絡應用在網絡表示學習任務中的有效性。更多關于圖神經網絡的內容可參閱文獻[21]。

TransNet（translation-based network representation）[22]將自編碼器模型與轉換機制[23-24]相結合，對網絡中邊上的標簽信息進行建模。主要方法是對邊上的標簽信息進行自編碼，并對自編碼器中間層上的邊向量進行轉換操作，將節點的向量表示和對應的邊向量訓練成平移關系。由此，可根據節點向量直接推出邊向量，通過解碼操作即可獲得邊上的標簽信息。該模型被成功運用在社會關系提取任務中。

2.1.3 綜合框架方法

在現實網絡中，節點之間存在著不同類型的相似性，使得網絡呈現出多種視圖（multi-view）。傳統網絡表示學習模型大都是學習網絡中的單一視圖信息，唐建等人提出了一種可整合網絡中多視圖信息的魯棒性表示學習模型MVE（multi-view network embedding）[25]。該模型基于注意力機制學習各視圖的權重并進行信息整合，最終學得具有高魯棒性的表征向量。

進一步將本小節中介紹的算法進行綜合比較，包括時間復雜度、理論基礎、有無監督以及評估方法等，對比結果如表2所示。

Table 2 Comprehensive comparison of algorithms assisted by label information表2 標簽信息輔助的算法綜合比較

2.2 社區信息輔助的網絡表示學習

2.2.1 基于矩陣分解的方法

M-NMF（modularized nonnegative matrix factorization）[26]算法對網絡中節點分別從微觀和中觀的角度學習向量表示，同時考慮節點之間的相似度和節點所屬的社區信息。微觀層面上，該算法主要編碼節點間的一階和二階拓撲相似度；中觀層面上，該模型運用基于模塊性最大化的社區發現方法來建模網絡中的社區結構。最終學得的表征向量同時包含了節點在原網絡中的拓撲信息以及所屬的社區信息，在后續的節點聚類和分類任務中表現優越。

2.2.2 綜合框架方法

除了利用社區信息對網絡中的單個節點進行表示學習之外，Cavallari等人設計了ComE（community embedding）[27]模型，可直接對整個社區進行表示學習。模型中節點嵌入、社區發現以及社區嵌入這三部分之間循環進行，并且相互促進。節點嵌入有助于增強社區發現，用于輸出更好的社區，由此能夠進一步擬合出更好的社區嵌入。實驗證明這對社區層面上的任務有很大的幫助，包括社區發現、社區可視化和社區推薦等。結合社區信息進行表示學習的算法還包括COSINE（community-preserving social network embeddings）[28]、CARE（community aware random walk for network embedding)[29]和 GNE（galaxy network embedding）30]等無監督學習算法。

進一步將本小節中介紹的算法進行綜合比較，總結如表3所示。

2.3 屬性信息輔助的網絡表示學習

2.3.1 基于矩陣分解的方法

Liu等人在DeepWalk算法基礎之上進行改進，提出了TADW（text-associated DeepWalk）[31]算法。該算法將節點的屬性信息加入到矩陣分解的過程中，主要思想如圖2所示。其目標是對矩陣M(M=(A+A2)/2)進行矩陣分解，使得M≈WTHT，其中T矩陣中包含了節點的屬性信息。對應的目標函數如式（1）所示，最小化目標函數并更新矩陣W和H。節點最終的向量表示由矩陣W和HT對應的列向量拼接得到。DMF（discriminative matrix factorization）[32]對 TADW算法進一步作了改進，通過增加一線性分類器進行有監督學習，從而使學得的表征向量更具區別力。

Fig.2 Framework of TADW model(from Ref.[31])圖2 TADW模型框架（來源于文獻[31]）

AANE（accelerated attributed network embedding）[33]模型同樣基于矩陣分解將網絡中的拓撲信息以及屬性信息整合到一起。特別地，該模型將優化過程分解成了多個子問題進行并行工作，通過這種方法大大提升了模型的工作效率。Li等人引入矩陣攝動理論，進一步設計了能夠適應網絡動態變化的表示學習模型 DANE（dynamic attributed network embedding）[34]，在網絡拓撲結構和屬性信息產生變化后，該模型能夠在較短時間內對網絡中的節點生成新的向量表示。

2.3.2 基于神經網絡的方法

Li等人提出了一深度學習模型VAE（variational AutoEncoder）[35]來學習網絡中節點的嵌入。該模型整合了doc2vec[36]和深度自編碼器，將屬性信息和拓撲信息進行整合并映射到同一語義空間中。其中doc2vec用于將屬性信息向量化，深度自編碼器用于整合向量化的屬性信息和拓撲信息（鄰接矩陣）。特別地，在編碼區的最后一層會產生兩種信息新的分布，以提取兩者的主要特征。最終，模型將自編碼器的中間層作為節點的向量表示。學得的表征向量同時捕獲了節點在原網絡中的屬性信息以及高度非線性的拓撲信息。

Table 3 Comprehensive comparison of algorithms assisted by community information表3 社區信息輔助的算法綜合比較

GraphSAGE（graph sample and aggregate）[37]在傳統圖卷積神經網絡上進行了延伸，通過匯聚多階鄰居節點的信息來生成向量表示。特別地，該模型對于不同階層的鄰居節點訓練不同的聚合器，并可通過后續的任務進行有監督的學習。最終學得的節點的向量表示一方面匯聚了多階鄰居節點的屬性信息，另一方面也捕獲了原網絡中的拓撲信息。EP（embedding propagation）[38]算法同樣是通過匯聚鄰居信息來進行表示學習。不同之處在于，EP算法屬于無監督學習，且獨立學習每種不同類型標簽的嵌入。

Tu等人指出現實網絡中節點與不同鄰居節點交互時所展現的主題會有所不同，進而設計了CANE（context-aware network embedding）[39]算法。該算法通過一深度架構將節點的屬性信息和拓撲信息映射到同一語義空間中，并引入注意力機制來捕獲節點與不同鄰居交互時所側重的主題。

2.3.3 基于自定義損失函數的方法

Xu等人認為現實世界網絡中的鏈接信息和屬性信息大都是部分可見的，由此提出了NRCL（noiseresilient representation consensus learning）[40]算法為具有部分鏈接和屬性信息的網絡學習向量表示，并應用到鏈接預測任務中。該模型將網絡中的節點分為三類，分別為具有連邊的節點集、具有屬性信息的節點集以及同時具有這兩種信息的節點集，網絡中的節點屬于這三類中的一類或多類。對前兩類節點集分別進行建模，然后通過第三類節點集相聯系，由此使得鏈接信息與屬性信息相互補充，學得的向量表示具有高魯棒性。

進一步將本小節中介紹的算法進行綜合比較，總結如表4所示。

2.4 多類別信息輔助的網絡表示學習

以上介紹的表示學習模型都只結合了一種異質信息，并不適用于多種異質信息的有效融合。而如何有效地融合和平衡多種異質信息是一個極具挑戰的任務。已有一些研究者針對此問題各自提出了不同的解決方法。在下文中，將對這些研究成果分別進行詳細介紹。

2.4.1 基于神經網絡的方法

Fig.3 Framework ofASNE model(from Ref.[41])圖3 ASNE模型框架（來源于文獻[41]）

Table 4 Comprehensive comparison on algorithms assisted by attribute information表4 屬性信息輔助的算法綜合比較

ASNE（attributed social network embedding）[41]運用深層神經網絡對不同類型的節點信息（離散+連續）進行綜合的學習，模型的整體架構如圖3所示。首先，該模型對節點的離散屬性（例如id）進行onehot編碼，對于連續屬性（例如文本）進行TF-IDF（term frequency-inverse document frequency）編碼；然后，將編碼生成的向量輸入到嵌入層（由兩個全連接層組成）進行降維，Wid和Watt分別對應id和屬性信息的全連接層中的權重矩陣；之后將降維后的向量進行拼接，并輸入到隱含層中進行非線性映射；最后，在輸出層上計算出目標節點與其他節點連接的概率，由此將拓撲信息與多種類別的屬性信息聯系起來。總的來說，該模型通過深層神經網絡建模不同類型信息之間的復雜的關聯關系，在后續的節點分類和鏈接預測的任務中表現優越。

Jacobs等人提出了一種半監督模型SEANO（semisupervised embedding in attributed networks with outliers）[42]為具有部分標簽和屬性信息的網絡學習節點的向量表示。該模型通過深度學習架構將節點的拓撲結構信息、屬性信息和標簽信息關聯起來。模型的整體框架如圖4所示，它包含了兩個輸入層和兩個輸出層，中間通過非線性映射層將異構信息相連。其中，輸入層中包含了目標節點和其鄰居節點的屬性信息向量；左側的輸出層作為該模型的有監督學習部分，通過帶有標簽信息的節點進行訓練；右側的輸出層作為模型的無監督學習部分，用于捕獲節點在原網絡中的拓撲信息。最后，將模型嵌入層中的向量作為節點最終的向量表示。

Fig.4 Framework of SEANO model(from Ref.[42])圖4 SEANO模型框架(來源于文獻[42])

2.4.2 綜合框架方法

Huang等人提出了一種半監督的綜合框架LANE（label informed attributed network embedding）[43]來匯聚多種異構信息。該模型通過將標簽信息、屬性信息和拓撲信息映射到相同的語義空間中，并尋找三者之間的關聯關系來獲得節點的向量表示。其中，對于拓撲信息和屬性信息的嵌入主要運用了譜方法；對于標簽信息的嵌入，主要根據同質性原則，使具有相同標簽的節點在向量空間中距離相近。最后通過相關投影將學得的這三類向量嵌入到一個新的維度空間中，最大化三者在新空間上的關聯性，進而得出最終的向量表示。

將本小節介紹的算法及帶有輔助信息的網絡表示學習方法進行綜合對比，從算法的理論基礎、有無監督、時間復雜性、評測任務等方面進行比較，分別如表5和表6所示。

2.5 面向異構網絡的表示學習

2.5.1 基于自定義損失函數的方法

Jacob等人在文獻[44]中提出了一種半監督表示學習算法LSHM（latent space heterogeneous model），用于對異構網絡中的不同類型的節點學習向量表示。該算法同時對相同類型和不同類型的節點進行平滑性約束，并將所有類型的節點映射到同一潛在空間中。此外，對于每類節點，都會進一步學習一分類函數，并對帶標簽的節點進行預測。最終學得的向量表示同時包含了節點在原網絡中的拓撲信息和標簽信息。

Table 5 Comprehensive comparison on algorithms assisted by polytype information表5 多類型信息輔助的算法綜合比較

Table 6 Comparison of NRL algorithms in terms of theoretical foundation表6 網絡表示學習算法的理論基礎比較

PTE（predictive text embedding）[45]算法在 LINE算法的基礎上進行了改進，用于在異構文本網絡中學習文本的嵌入。異構文本網絡中包含了單詞、文檔和標簽這三種類型的節點。在建模過程中，首先將異構文本網絡劃分成了三個子網絡，分別為“單詞-單詞”“單詞-文本”和“單詞-標簽”子網絡。然后采用改進后的LINE算法分別對這些子網絡建模，捕獲不同類型信息之間的相似性。最終文本的向量表示由相應單詞的向量表示取平均得到。

以上介紹的算法都是將異構數據拆分成兩兩交互的類型分別進行建模，這種方法的缺點就是無法捕獲一些強類型對象（strongly-typed objects）產生的共同作用效果。Gui等人提出了HEBE（hyperedgebased embedding）[46]算法用于解決這個問題。該算法將一類事件產生的交互集合（即強類型對象）看作一個超邊，并將每個超邊作為一個整體進行建模。在建模過程中，將超邊中的一特定類型的節點設定為預測目標，并用該超邊中剩余節點對該目標節點進行預測，從而捕獲了基于事件的相似性關系。

2.5.2 基于矩陣分解的方法

CMF（coordinate matrix factorization）[47]是一種基于矩陣分解的異構網絡表示學習算法，用于同時學習維基百科中實體、類別和詞的向量表示。該算法通過矩陣分解的方式分別建立實體之間、實體與類別之間、實體與詞之間的聯系，總的損失函數如式（2）所示。通過這種方式，一方面可以克服網絡稀疏問題，另一方面也方便增加更多的關系矩陣，具有可擴展性。

2.5.3 基于神經網絡的方法

metapath2vec[48]算法基于隨機游走和skip-gram模型來學習異構網絡中節點的向量表示。該算法設計了基于元路徑的隨機游走方法，通過定義的對稱的meta-path來控制隨機游走過程。產生的節點序列可以直接輸入到skip-gram模型中進行訓練，不區分節點的類別。作者將skip-gram進一步作了改進，改進后的模型metapath2vec++使得不同類型的節點能夠在輸出層上被區別開來。Zhang等人在文獻[49]中指出了基于mata-path的方法只能嚴格按照設定的路徑類型選取節點建立聯系，并不能捕獲那些距離較遠的節點間的相似性，而且只有一少部分節點符合設定的元路徑，從而導致在訓練過程中數據的稀疏。由此，作者設計一種基于元圖（metagraph）的方法來引導隨機游走的過程。由于每個元圖中包含了多種元路徑，因而在隨機游走過程中能夠實現更加靈活的匹配，從而捕獲更加復雜的節點關系。

在文獻[50]中，作者提出了一種無監督的異構網絡表示學習框架AspEm（embedding learning by aspects），為異構節點學習匯聚多方面信息的向量表示。如圖5所示，（a）圖例可以分解成（b）中兩個方面的子圖。文中設計了一種不兼容信息度量方法來提取這種多方面子圖。該模型進一步將不同子圖通過skip-gram分別進行訓練，最后將同一節點的來自不同子圖的向量表示整合在一起。

Fig.5 Schema and 2 aspects of HIN(from Ref.[50])圖5 異構網絡的圖例和兩個方面（來源于文獻[50]）

Wang等人提出了SHINE（signed heterogeneous information network embedding）[51]模型用于預測異構情感網絡中用戶的潛在情感傾向。文中通過建立情感網絡、社會網絡和資料網絡這三大網絡來匯聚異構信息，并通過三個深度自編碼器分別對三個網絡進行信息嵌入，之后將節點在不同網絡下得到的向量表示進行匯聚，產生節點最終的向量表示。最后可通過計算用戶表征向量之間的相似性來進行情感預測。該模型充分借助異構信息，有效地解決了冷啟動問題，進而可有效應用到鏈接預測和推薦任務中。

2.5.4 綜合框架方法

為了整合異構網絡中不同類型的信息，Chang等人設計了一深度架構HNE（heterogeneous network embedding）[52]，將不同類型的信息映射到相同的語義空間中。以包含文本和圖片信息的異構網絡為例，該模型對不同類型的節點采用不同的處理方法（圖片-卷積神經網絡，文本-全連接神經網絡），并將它們映射到同一潛在空間中。進一步地，該模型根據原網絡中的拓撲信息對不同類型的節點對（“圖片-圖片”“圖片-文本”和“文本-文本”）進行相似性建模。由此也證明了不同模態的數據類型能夠通過這種深層架構在同一潛在空間中建立聯系。

Fu等人提出了HIN2Vec（heterogeneous information network to vector）[53]模型，基于神經網絡同時學習異構網絡中的節點和元路徑的向量表示。與上文介紹的基于metapath的算法不同，HIN2Vec是以完全隨機游走的方式選取訓練集，并通過預測相鄰節點間的特定關系來建模異構網絡中節點的關聯關系。這種多任務學習方法使得表示學習過程得以高效進行。

3 常用數據集

本章主要介紹上述論文實驗中常用的數據集，包括數據集的來源（Link）、節點數（|V|）、邊數（|E|）、標簽類別數(|y|)、是否有屬性信息（attributes，Att.）等。同時對這些數據集進行分類，類別包括：社交網絡（social network）、引文網絡（citation network）、合著網絡（collaboration network）、網頁鏈接網絡（Webpage network）和生物學網絡（biological network）等。將數據集的信息總結如表7所示。

4 總結與展望

本文為融合異質信息的網絡表示學習算法設計了一個統一的分類框架，并對一些代表性算法進行了概括介紹和分類對比。總的來說，復雜網絡中豐富的信息越來越充分地得到挖掘和運用，這也使模型學得的表征向量更能反映網絡的真實形態。隨著社會發展，現實世界網絡會變得更加復雜，如何有效地匯聚不同類型的信息來輔助表征向量的學習，使其更具推理能力和區別力，同時降低整個模型的復雜度是今后仍需研究的開放性問題。對此領域未來可能的研究方向做了如下總結：

（1）適應大規模復雜網絡。現有的融合異質信息的網絡表示學習算法僅適用于小規模數據網絡，難以適用到現實應用場景中。因此，設計具有可擴展性的算法值得未來進行深入研究。

（2）適應網絡的動態變化。現實網絡具有動態性，節點、鏈接關系以及復雜的異質信息都會不斷發生變化，而現有的網絡表示學習算法大都不適用于在線更新。設計能夠有效融合異質信息的在線網絡表示算法具有很高的實用價值。

Table 7 Data sets and descriptions表7 數據集及其介紹

（3）尋找更多的應用場景。目前網絡表示學習的應用場景相對局限，主要包括節點分類、聚類、社區發現、鏈接預測等。挖掘出更多復雜網絡中的應用場景，并設計針對特定任務的網絡表示學習算法是未來值得探索的方向。