網(wǎng)絡(luò)表示學(xué)習(xí)的研究與發(fā)展1

尹贏，吉立新，黃瑞陽，杜立新

?

網(wǎng)絡(luò)表示學(xué)習(xí)的研究與發(fā)展1

尹贏1，吉立新1，黃瑞陽1，杜立新2

（1. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450003； 2. 解放軍63898部隊(duì)，河南 洛陽 471003）

網(wǎng)絡(luò)表示學(xué)習(xí)旨在將網(wǎng)絡(luò)中的節(jié)點(diǎn)表示成低維稠密且具有一定推理能力的向量，以運(yùn)用于節(jié)點(diǎn)分類、社區(qū)發(fā)現(xiàn)和鏈路預(yù)測等社交網(wǎng)絡(luò)應(yīng)用任務(wù)中，是連接網(wǎng)絡(luò)原始數(shù)據(jù)和網(wǎng)絡(luò)應(yīng)用任務(wù)的橋梁。傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)方法都是針對網(wǎng)絡(luò)中節(jié)點(diǎn)和連邊只有一種類型的同質(zhì)信息網(wǎng)絡(luò)的表示學(xué)習(xí)方法，而現(xiàn)實(shí)世界中的網(wǎng)絡(luò)往往是具有多種節(jié)點(diǎn)和連邊類型的異質(zhì)信息網(wǎng)絡(luò)。而且，從時(shí)間維度上來看，網(wǎng)絡(luò)是不斷變化的。因此，網(wǎng)絡(luò)表示學(xué)習(xí)的研究方法隨著網(wǎng)絡(luò)數(shù)據(jù)的復(fù)雜化而不斷變化。對近年來針對不同網(wǎng)絡(luò)的網(wǎng)絡(luò)表示學(xué)習(xí)方法進(jìn)行了分類介紹，并闡述了網(wǎng)絡(luò)表示學(xué)習(xí)的應(yīng)用場景。

大規(guī)模信息網(wǎng)絡(luò)；網(wǎng)絡(luò)表示學(xué)習(xí)；網(wǎng)絡(luò)嵌入；深度學(xué)習(xí)

1 引言

在大數(shù)據(jù)時(shí)代，網(wǎng)絡(luò)數(shù)據(jù)在現(xiàn)實(shí)世界中無處不在。針對網(wǎng)絡(luò)數(shù)據(jù)的研究與分析，已經(jīng)受到社會各界的廣泛關(guān)注。復(fù)雜而龐大的網(wǎng)絡(luò)數(shù)據(jù)往往難以處理，將網(wǎng)絡(luò)數(shù)據(jù)表示成一種高效合理的形式，并將其運(yùn)用于節(jié)點(diǎn)分類、社區(qū)發(fā)現(xiàn)、鏈路預(yù)測和網(wǎng)絡(luò)可視化等應(yīng)用任務(wù)中，對解決現(xiàn)實(shí)網(wǎng)絡(luò)中的實(shí)際應(yīng)用問題具有重要意義。例如，在社交網(wǎng)絡(luò)中，可以通過節(jié)點(diǎn)分類方法對用戶進(jìn)行分類來構(gòu)建用戶推薦系統(tǒng)；在通信網(wǎng)絡(luò)中，可以通過社區(qū)發(fā)現(xiàn)來觀察輿情傳播進(jìn)程；在生物網(wǎng)絡(luò)中，可以通過鏈路預(yù)測推測蛋白質(zhì)之間可能存在的相互作用關(guān)系以推動疾病的治療。這些網(wǎng)絡(luò)分析方法都依賴于網(wǎng)絡(luò)的表示方式，通常利用網(wǎng)絡(luò)鄰接矩陣或者由網(wǎng)絡(luò)中節(jié)點(diǎn)和連邊構(gòu)成的圖來表示網(wǎng)絡(luò)。但是，這樣簡單的表示方式往往存在以下問題。

1) 連邊導(dǎo)致計(jì)算復(fù)雜度高

網(wǎng)絡(luò)通常由節(jié)點(diǎn)集和連邊集組成，節(jié)點(diǎn)代表實(shí)體對象，而連邊則反映出節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系。連邊的存在使大多數(shù)網(wǎng)絡(luò)處理器或網(wǎng)絡(luò)分析算法是迭代的或組合爆炸的。例如，用兩個(gè)節(jié)點(diǎn)之間的最短路徑長度或平均路徑長度表示它們之間的距離。要想使用傳統(tǒng)的網(wǎng)絡(luò)表示方法計(jì)算這樣的距離，必須枚舉出2個(gè)節(jié)點(diǎn)之間的所有可能路徑，從本質(zhì)上看，這是一個(gè)組合問題，計(jì)算復(fù)雜度高。因此，傳統(tǒng)的網(wǎng)絡(luò)表示方法不再適用。

2) 數(shù)據(jù)樣本相互耦合導(dǎo)致低并行性

以傳統(tǒng)方式表示的網(wǎng)絡(luò)數(shù)據(jù)給并行和分布式算法的設(shè)計(jì)和實(shí)現(xiàn)帶來了很大的困難。研究的難點(diǎn)在于：網(wǎng)絡(luò)中由連邊連接的節(jié)點(diǎn)彼此耦合，若將不同的節(jié)點(diǎn)分布在不同的計(jì)算單元上進(jìn)行處理，往往會造成服務(wù)器之間高昂的通信代價(jià)。雖然通過對大規(guī)模圖形進(jìn)行巧妙分割得到子圖，使并行化性得到一定的提高，但這種方法在很大程度上依賴于網(wǎng)絡(luò)圖形的拓?fù)涮匦浴?/p>

3) 機(jī)器學(xué)習(xí)方法不適用

近年來，機(jī)器學(xué)習(xí)方法（特別是深度學(xué)習(xí)方法）在很多領(lǐng)域都有應(yīng)用，并且取得了不錯(cuò)的效果。這些方法針對各類問題都提供了標(biāo)準(zhǔn)的、通用的、有效的解決途徑。但對于傳統(tǒng)網(wǎng)絡(luò)數(shù)據(jù)的表示，大多數(shù)現(xiàn)有的機(jī)器學(xué)習(xí)方法往往是不適用的。雖然可以簡單地用網(wǎng)絡(luò)鄰接矩陣中節(jié)點(diǎn)對應(yīng)的行向量來表示該節(jié)點(diǎn)。但是這種表示往往具有很高的維度，使后續(xù)的網(wǎng)絡(luò)處理和分析變得十分困難。

為了解決傳統(tǒng)方法的缺陷，研究學(xué)者提出了一種新的網(wǎng)絡(luò)表示方式：將網(wǎng)絡(luò)中的節(jié)點(diǎn)表示成具有一定推理能力的向量映射到低維空間中，旨在以更加直觀高效的方式盡可能地保留節(jié)點(diǎn)間的原始關(guān)系，從而便捷地作為機(jī)器學(xué)習(xí)模型的輸入，運(yùn)用于節(jié)點(diǎn)分類、鏈路預(yù)測和社區(qū)發(fā)現(xiàn)等社交網(wǎng)絡(luò)分析應(yīng)用中。將節(jié)點(diǎn)表示成向量映射到低維空間中，向量間的距離反映出原始網(wǎng)絡(luò)中節(jié)點(diǎn)間的連邊關(guān)系。這就解決了由網(wǎng)絡(luò)中的連邊帶來的一系列網(wǎng)絡(luò)分析問題。同時(shí)，這種網(wǎng)絡(luò)表示方式不需要人工標(biāo)注網(wǎng)絡(luò)特征，而是自動從原始網(wǎng)絡(luò)數(shù)據(jù)中提取出有用的網(wǎng)絡(luò)表征，能夠很好地保留原始網(wǎng)絡(luò)中的信息實(shí)現(xiàn)網(wǎng)絡(luò)重構(gòu)。

2 網(wǎng)絡(luò)表示學(xué)習(xí)的基本定義

3 網(wǎng)絡(luò)表示學(xué)習(xí)方法介紹

隨著網(wǎng)絡(luò)的規(guī)模化和復(fù)雜化，如何分析網(wǎng)絡(luò)中包含的豐富信息是一項(xiàng)非常重要的研究任務(wù)。網(wǎng)絡(luò)表示學(xué)習(xí)將網(wǎng)絡(luò)中的節(jié)點(diǎn)表示成向量映射到低維空間，可以將其作為機(jī)器學(xué)習(xí)算法的輸入來挖掘網(wǎng)絡(luò)數(shù)據(jù)中蘊(yùn)含的豐富信息?，F(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)方法主要針對同質(zhì)信息網(wǎng)絡(luò)和異質(zhì)信息網(wǎng)絡(luò)。接下來分別對基于這兩種網(wǎng)絡(luò)的表示學(xué)習(xí)方法進(jìn)行分析。

3.1 針對同質(zhì)信息網(wǎng)絡(luò)的表示學(xué)習(xí)方法

基于網(wǎng)絡(luò)表示學(xué)習(xí)方法所考慮的網(wǎng)絡(luò)信息內(nèi)容，本節(jié)將同質(zhì)信息網(wǎng)絡(luò)的表示學(xué)習(xí)方法分為兩類：基于網(wǎng)絡(luò)結(jié)構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)和結(jié)合外部信息的網(wǎng)絡(luò)表示學(xué)習(xí)。

圖1 異質(zhì)信息網(wǎng)絡(luò)實(shí)例

3.1.1 基于網(wǎng)絡(luò)結(jié)構(gòu)的同質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)

網(wǎng)絡(luò)結(jié)構(gòu)可以劃分為以不同粒度呈現(xiàn)的不同組。網(wǎng)絡(luò)表示學(xué)習(xí)中常用的網(wǎng)絡(luò)結(jié)構(gòu)包括鄰域結(jié)構(gòu)、高階節(jié)點(diǎn)鄰近結(jié)構(gòu)和網(wǎng)絡(luò)社團(tuán)。依據(jù)算法基于的不同方法將其分為3類：基于矩陣特征向量和矩陣分解的方法、基于淺層神經(jīng)網(wǎng)絡(luò)的方法和基于深度學(xué)習(xí)的方法。

基于矩陣特征向量和矩陣分解的方法：早期的網(wǎng)絡(luò)表示學(xué)習(xí)算法大多是基于矩陣特征向量和矩陣分解的方法，Saul等[2-3]提出局部線性表示，通過鄰居節(jié)點(diǎn)的線性組合來表示當(dāng)前節(jié)點(diǎn)，算法假設(shè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)位于同一流形區(qū)域。當(dāng)前節(jié)點(diǎn)可表示為

基于淺層神經(jīng)網(wǎng)絡(luò)的方法：受自然語言處理中Word2vec算法[11]的啟發(fā)，Perozzi等[12]提出了DeepWalk算法用于學(xué)習(xí)網(wǎng)絡(luò)中的節(jié)點(diǎn)表示，DeepWalk通過隨機(jī)游走遍歷網(wǎng)絡(luò)中的節(jié)點(diǎn)，從而得到一個(gè)有序的節(jié)點(diǎn)序列，該過程實(shí)際是對網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行采樣的過程，在隨機(jī)游走過程中，節(jié)點(diǎn)越鄰近，共現(xiàn)的概率越大；在通過隨機(jī)游走得到節(jié)點(diǎn)序列以后，該算法利用skip-gram模型由單個(gè)節(jié)點(diǎn)預(yù)測前后序列，學(xué)習(xí)得到該節(jié)點(diǎn)的向量表示。Grover等[13]提出的node2vec改進(jìn)了DeepWalk中的隨機(jī)游走過程。DeepWalk選取隨機(jī)游走序列中下一個(gè)節(jié)點(diǎn)的方式是均勻隨機(jī)分布的，而Node2vec通過引入兩個(gè)參數(shù)和，將寬度優(yōu)先搜索和深度優(yōu)先搜索引入了隨機(jī)游走序列的生成過程。寬度優(yōu)先搜索注重鄰近節(jié)點(diǎn)并刻畫了相對局部的一種網(wǎng)絡(luò)表示，而深度優(yōu)先搜索則反映了更高層面上節(jié)點(diǎn)間的同質(zhì)性。Tang等[14]提出的LINE算法能夠處理任意類型的大規(guī)模網(wǎng)絡(luò)，包括有向和無向、有權(quán)重和無權(quán)重。該算法保留了網(wǎng)絡(luò)中節(jié)點(diǎn)的一階相似性和二階相似性。一階相似性是指有連邊的節(jié)點(diǎn)之間的相似性，主要由連邊權(quán)重決定，沒有連邊的節(jié)點(diǎn)間的相似性則為0。二階相似性是指節(jié)點(diǎn)的鄰近網(wǎng)絡(luò)結(jié)構(gòu)的相似性，若2個(gè)節(jié)點(diǎn)沒有共同的一階鄰居，則二階相似性為0。如圖2所示，節(jié)點(diǎn)5和6的一階相似性為0，但二者具有很強(qiáng)的二階相似性，節(jié)點(diǎn)6和7具有一階相似性但不具備二階相似性。一階相似性和二階相似性互補(bǔ)，使該算法能夠很好地保留網(wǎng)絡(luò)的局部結(jié)構(gòu)和全局結(jié)構(gòu)。

基于深度學(xué)習(xí)的方法：SDNE算法[15]利用深度神經(jīng)網(wǎng)絡(luò)對網(wǎng)絡(luò)的表示學(xué)習(xí)進(jìn)行建模，該半監(jiān)督的深度學(xué)習(xí)模型由多重的非線性映射函數(shù)組成，將輸入的節(jié)點(diǎn)映射到高度非線性空間中以獲取網(wǎng)絡(luò)的結(jié)構(gòu)信息。模型如圖3所示，主要由兩部分組成：一是由拉普拉斯矩陣監(jiān)督的能保留局部信息的一階相似度模塊，二是基于無監(jiān)督深度自編碼器的能保留全局信息的二階相似度模塊。

圖2 一階相似性和二階相似性實(shí)例

模型將一階相似度和二階相似度結(jié)合來同時(shí)保留網(wǎng)絡(luò)結(jié)構(gòu)的局部信息和全局信息，其目標(biāo)函數(shù)可表示為

不同于傳統(tǒng)的直推式網(wǎng)絡(luò)表示學(xué)習(xí)算法，Hamilton等[16]提出一種適用于大規(guī)模網(wǎng)絡(luò)的歸納式學(xué)習(xí)方法GraphSAGE。該算法通過聚集采樣到的鄰居節(jié)點(diǎn)表示來更新當(dāng)前節(jié)點(diǎn)的特征表示，而不是像直推式方法將每個(gè)節(jié)點(diǎn)單獨(dú)進(jìn)行訓(xùn)練。在聚類過程中，網(wǎng)絡(luò)第層聚集到的鄰居即為寬度優(yōu)先搜索（BFS）過程中第層的鄰居。同時(shí)，作者在算法中利用了3種聚類策略：Mean、LSTM和MaxPooling。

圖3 SDNE算法模型框架

表1 算法適用網(wǎng)絡(luò)及實(shí)驗(yàn)數(shù)據(jù)集

總之，判別器和生成器的訓(xùn)練過程是一個(gè)最大最小相互制約的過程，算法的目標(biāo)函數(shù)可表示為

常見的基于網(wǎng)絡(luò)結(jié)構(gòu)的同質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)方法如表1所示。

3.1.2 結(jié)合外部信息的同質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)

傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)方法都是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法，但除了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)還包括標(biāo)簽和文本等重要的外部信息，這些外部信息也是網(wǎng)絡(luò)表示學(xué)習(xí)的一個(gè)重要研究內(nèi)容。

為了適應(yīng)節(jié)點(diǎn)分類等機(jī)器學(xué)習(xí)任務(wù)，Tu等[18]提出了針對帶標(biāo)簽網(wǎng)絡(luò)的半監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)模型MMDW。該模型基于矩陣分解，利用SVM 分類器和節(jié)點(diǎn)的標(biāo)簽信息來尋找優(yōu)化的分類邊界。通過優(yōu)化SVM最大間隔分類器和轉(zhuǎn)換為矩陣因子分解形式的DeepWalk模型，MMDW模型能學(xué)習(xí)到包含網(wǎng)絡(luò)結(jié)構(gòu)信息和標(biāo)簽信息的節(jié)點(diǎn)表示。

在網(wǎng)絡(luò)數(shù)據(jù)中，節(jié)點(diǎn)除了包含標(biāo)簽信息，還包含一些文本信息。這些文本信息也可以作為網(wǎng)絡(luò)信息的補(bǔ)充，有助于進(jìn)行更加合理適用的網(wǎng)絡(luò)表示學(xué)習(xí)。TADW[19]基于矩陣分解將節(jié)點(diǎn)的文本信息引入網(wǎng)絡(luò)表示學(xué)習(xí)中，TADW模型框架如圖4所示。

圖4 TADW模型框架

模型將關(guān)系矩陣分解為、、這3個(gè)矩陣的乘積。其中，表示文本特征矩陣，和表示參數(shù)矩陣，算法通過梯度下降法來迭代更新參數(shù)矩陣。模型的目標(biāo)函數(shù)可表示為

但是TADW算法的計(jì)算代價(jià)很高，而且算法只是將節(jié)點(diǎn)屬性進(jìn)行簡單結(jié)合，這就造成了網(wǎng)絡(luò)中語義信息的大量丟失。Sun等[20]提出一種新的CENE算法，將節(jié)點(diǎn)內(nèi)容視為一種特殊的節(jié)點(diǎn)來擴(kuò)展網(wǎng)絡(luò)，如圖5所示。擴(kuò)展的網(wǎng)絡(luò)中包含兩種節(jié)點(diǎn)：原始網(wǎng)絡(luò)節(jié)點(diǎn)和構(gòu)造的“節(jié)點(diǎn)內(nèi)容”節(jié)點(diǎn)?；诓煌?jié)點(diǎn)，擴(kuò)展的網(wǎng)絡(luò)也包括兩種邊：原始節(jié)點(diǎn)之間的連邊和原始節(jié)點(diǎn)與“節(jié)點(diǎn)內(nèi)容”之間的連邊。算法使用邏輯回歸函數(shù)學(xué)習(xí)擴(kuò)展的網(wǎng)絡(luò)，并通過負(fù)采樣的方法優(yōu)化目標(biāo)函數(shù)。通過該算法得到的網(wǎng)絡(luò)表示不僅可以保留網(wǎng)絡(luò)結(jié)構(gòu)特征，還可以保留節(jié)點(diǎn)和內(nèi)容之間的語義信息。

Pan等提出一個(gè)能結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)內(nèi)容和節(jié)點(diǎn)標(biāo)簽這3種網(wǎng)絡(luò)信息的深度學(xué)習(xí)模型TriDNR[21]，模型結(jié)構(gòu)如圖6所示，其目標(biāo)函數(shù)可表示為

類似于DeepWalk模型，該模型通過隨機(jī)游走生成節(jié)點(diǎn)的表示向量來保留節(jié)點(diǎn)在結(jié)構(gòu)上的相似性；然后用另一個(gè)神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)節(jié)點(diǎn)上下文的相關(guān)性；同時(shí)，將節(jié)點(diǎn)標(biāo)簽作為輸入，直接在標(biāo)簽和上下文之間建模來學(xué)習(xí)標(biāo)簽向量和單詞向量。

常見的結(jié)合外部信息的同質(zhì)信息網(wǎng)絡(luò)表示學(xué)習(xí)算法如表2所示。

表2 算法適用網(wǎng)絡(luò)及實(shí)驗(yàn)數(shù)據(jù)集

3.2 針對異質(zhì)信息網(wǎng)絡(luò)的表示學(xué)習(xí)方法

早期的網(wǎng)絡(luò)表示學(xué)習(xí)算法是針對節(jié)點(diǎn)和邊類型只有一種的同質(zhì)信息網(wǎng)絡(luò)，而將所有節(jié)點(diǎn)和連邊視為同一類的同質(zhì)網(wǎng)絡(luò)忽略了網(wǎng)絡(luò)中豐富的語義信息，并不能有效地反映現(xiàn)實(shí)世界中的網(wǎng)絡(luò)。類型化、半結(jié)構(gòu)化的異質(zhì)信息網(wǎng)絡(luò)建?？梢圆东@真實(shí)世界中最根本的語義信息[22]。目前，針對異質(zhì)信息網(wǎng)絡(luò)的表示學(xué)習(xí)方法研究相對較少，主要分為3類：基于隨機(jī)游走的方法、基于分解的方法和結(jié)合應(yīng)用任務(wù)的方法。

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

Yu等[23]受同質(zhì)網(wǎng)絡(luò)中Node2vec算法的啟發(fā)，提出了Metapath2vec算法，該方法通過在異質(zhì)信息網(wǎng)絡(luò)中進(jìn)行隨機(jī)游走來獲取節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合。不同于同質(zhì)信息網(wǎng)絡(luò)中的隨機(jī)游走，Metapath2vec算法中的隨機(jī)游走是在元路徑[24]的指導(dǎo)下進(jìn)行的，其跳轉(zhuǎn)概率為

基于元路徑進(jìn)行隨機(jī)游走得到的節(jié)點(diǎn)序列，不僅包含網(wǎng)絡(luò)的結(jié)構(gòu)信息，還包含網(wǎng)絡(luò)中的語義信息。在得到節(jié)點(diǎn)序列之后，算法利用skip-gram模型得到節(jié)點(diǎn)的向量表示，并采用負(fù)采樣的方法更新式(12)的目標(biāo)函數(shù)。

Metapath2vec算法在利用softmax函數(shù)進(jìn)行歸一化時(shí)，并沒有考慮節(jié)點(diǎn)的類型，而是和同質(zhì)網(wǎng)絡(luò)表示學(xué)習(xí)算法DeepWalk、Node2vec的處理方式一樣，是將所有節(jié)點(diǎn)的特征表示之和作為softmax函數(shù)的分母。作者在提出Metapath2vec的同時(shí)，提出了Metapath2vec++[23]，該算法在Metapath2vec的基礎(chǔ)上改進(jìn)了softmax函數(shù)，如式(13)所示。Metapath2vec++對不同類型的節(jié)點(diǎn)分別進(jìn)行歸一化，相當(dāng)于在淺層神經(jīng)網(wǎng)絡(luò)的輸出層根據(jù)節(jié)點(diǎn)類型將整個(gè)異質(zhì)信息網(wǎng)絡(luò)分解成不同的同質(zhì)信息網(wǎng)絡(luò)。通過Metapath2vec++得到的節(jié)點(diǎn)表示在運(yùn)用節(jié)點(diǎn)分類、聚類和相似性搜索等應(yīng)用任務(wù)時(shí)，具有更高的精度和可靠性。

2) 基于分解的方法

從網(wǎng)絡(luò)分解的角度對異質(zhì)信息網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)，往往有化繁為簡的效果。Tang等提出的PTE算法[25]，將包含詞、文件、標(biāo)簽這3種節(jié)點(diǎn)類型的文本信息網(wǎng)絡(luò)分解成3個(gè)不同的子網(wǎng)絡(luò)：詞?詞網(wǎng)絡(luò)、詞?文件網(wǎng)絡(luò)、詞?標(biāo)簽網(wǎng)絡(luò)。然后對這3個(gè)不同的網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)，得到不同類型節(jié)點(diǎn)的向量表示。Shi等提出的HERec[26]模型基于元路徑從異質(zhì)信息網(wǎng)絡(luò)中抽取出同類節(jié)點(diǎn)序列，相當(dāng)于從異質(zhì)信息網(wǎng)絡(luò)中抽取出多個(gè)同質(zhì)信息網(wǎng)絡(luò)?；诓煌窂?，該模型抽取出的同類節(jié)點(diǎn)序列有所不同。算法將基于不同元路徑抽取出的同類節(jié)點(diǎn)分別進(jìn)行表示學(xué)習(xí)，然后利用融合函數(shù)對節(jié)點(diǎn)的不同表示進(jìn)行融合，并將向量整合到矩陣分解模型中，通過矩陣分解模型和融合函數(shù)一起對預(yù)測任務(wù)進(jìn)行聯(lián)合優(yōu)化。該方法與基于卷積神經(jīng)網(wǎng)絡(luò)的監(jiān)督方法相比調(diào)整參數(shù)更少。

3) 結(jié)合應(yīng)用任務(wù)的方法

異質(zhì)信息網(wǎng)絡(luò)表示學(xué)習(xí)算法常和具體的數(shù)據(jù)挖掘任務(wù)相結(jié)合，Sun等[27]首先提出基于元路徑評估異質(zhì)信息網(wǎng)絡(luò)中節(jié)點(diǎn)間相似性的算法PathSim，該算法基于對稱元路徑，可測量異質(zhì)信息網(wǎng)絡(luò)中同類型對象間的相似程度。Sun等[28]提出的Pathselclus算法利用用戶提供的種子作為聚類的先驗(yàn)知識，提出一個(gè)基于聚類的生成模型來模擬節(jié)點(diǎn)間關(guān)系的生成，并通過評估元路徑關(guān)系矩陣與基于先驗(yàn)知識的聚類結(jié)果的一致性來優(yōu)化元路徑權(quán)重和聚類效果。也有算法用于異質(zhì)信息網(wǎng)絡(luò)的節(jié)點(diǎn)分類，Luo等[29]提出的HetPathMine算法通過構(gòu)建元路徑選擇模型來將異質(zhì)信息網(wǎng)絡(luò)中帶標(biāo)簽的數(shù)據(jù)進(jìn)行分類。Kong等[30]提出了一種適用于大規(guī)模網(wǎng)絡(luò)的基于元路徑的分類算法，該算法考慮了不同元路徑所蘊(yùn)含的不同語義，以捕獲不同連接類型對實(shí)體對象間關(guān)聯(lián)程度的影響，從而有效地對異質(zhì)網(wǎng)絡(luò)進(jìn)行大規(guī)模集體分類。Fu等[31]提出的HIN2vec利用神經(jīng)網(wǎng)絡(luò)模型來實(shí)現(xiàn)異質(zhì)信息網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的表示。學(xué)習(xí)到的向量可以直接用于鏈路預(yù)測任務(wù)，并具有很好的效果。

4 應(yīng)用場景

常見的網(wǎng)絡(luò)表示學(xué)習(xí)應(yīng)用場景主要有節(jié)點(diǎn)分類、鏈路預(yù)測、社區(qū)發(fā)現(xiàn)和可視化等。

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

在進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)處理時(shí)，往往需要將網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行合理分類。例如，在社交網(wǎng)絡(luò)中，可以根據(jù)用戶的興趣愛好對用戶分類以進(jìn)行相關(guān)推薦。用戶的興趣愛好是將用戶進(jìn)行分類的類別標(biāo)注信息，是對用戶進(jìn)行分類的依據(jù)。然而實(shí)際數(shù)據(jù)中的類別標(biāo)注信息十分稀疏，可以利用網(wǎng)絡(luò)表示學(xué)習(xí)算法來對節(jié)點(diǎn)進(jìn)行編碼，使在標(biāo)注信息很少的情況下也能得到很好的分類效果。

2) 鏈路預(yù)測

鏈路預(yù)測是指對網(wǎng)絡(luò)中丟失的邊或者潛在的邊進(jìn)行預(yù)測，可以幫助分析數(shù)據(jù)缺失的網(wǎng)絡(luò)以及網(wǎng)絡(luò)的演化，其在現(xiàn)實(shí)生活中具有廣泛的運(yùn)用。例如，可以利用鏈路預(yù)測方法基于當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測可能成為朋友的用戶，從而對用戶進(jìn)行好友推薦。鏈路預(yù)測的常見評價(jià)指標(biāo)為AUC值，當(dāng)在樣本集中隨機(jī)挑選一個(gè)正樣本以及一個(gè)負(fù)樣本，分類算法根據(jù)計(jì)算得到的正樣本分?jǐn)?shù)值高于負(fù)樣本分?jǐn)?shù)值的概率就是AUC值。

3) 社區(qū)發(fā)現(xiàn)

社區(qū)發(fā)現(xiàn)是指將網(wǎng)絡(luò)中相似的節(jié)點(diǎn)劃分到同一社區(qū)，與節(jié)點(diǎn)分類的不同之處在于，社區(qū)發(fā)現(xiàn)不依靠任何標(biāo)記的數(shù)據(jù)，而是直接對網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行無監(jiān)督的聚類。社區(qū)發(fā)現(xiàn)是一個(gè)自由度較高的網(wǎng)絡(luò)應(yīng)用任務(wù)，可以結(jié)合網(wǎng)絡(luò)表示學(xué)習(xí)利用社區(qū)發(fā)現(xiàn)算法對網(wǎng)絡(luò)中的用戶進(jìn)行自動分組。

4) 可視化

可視化是指利用一定的計(jì)算機(jī)技術(shù)將數(shù)據(jù)轉(zhuǎn)換成圖形或者圖像直觀地呈現(xiàn)出來，從而清晰有效地表達(dá)出信息。通過網(wǎng)絡(luò)表示學(xué)習(xí)，可以在低維向量空間得到網(wǎng)絡(luò)節(jié)點(diǎn)的表示向量，而這些向量可以直接用于網(wǎng)絡(luò)的可視化，使網(wǎng)絡(luò)可視化變得高效便捷。

5 結(jié)束語

網(wǎng)絡(luò)表示學(xué)習(xí)的研究方法隨著網(wǎng)絡(luò)數(shù)據(jù)的復(fù)雜化而不斷變化，保留網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)屬性是網(wǎng)絡(luò)表示學(xué)習(xí)的基礎(chǔ)。如果網(wǎng)絡(luò)表示學(xué)習(xí)方法沒有很好地保留網(wǎng)絡(luò)結(jié)構(gòu)和屬性，那么當(dāng)節(jié)點(diǎn)映射到低維向量空間中時(shí)，會造成嚴(yán)重的信息丟失。此外，也可以考慮將某些領(lǐng)域知識作為高級信息來輔助網(wǎng)絡(luò)表示學(xué)習(xí)。從現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)工作來看，該領(lǐng)域是一個(gè)新興的且非常具有前景的研究方向。近年來，網(wǎng)絡(luò)表示學(xué)習(xí)取得了豐碩的研究成果，但仍存在以下挑戰(zhàn)。

1) 現(xiàn)實(shí)網(wǎng)絡(luò)是蘊(yùn)含龐大數(shù)據(jù)量的大規(guī)模復(fù)雜網(wǎng)絡(luò)，如何高效處理這些龐大的數(shù)據(jù)，是網(wǎng)絡(luò)表示學(xué)習(xí)亟待解決的一個(gè)難點(diǎn)。

2) 動態(tài)網(wǎng)絡(luò)的研究相對較少，如何從時(shí)間維度上綜合考慮網(wǎng)絡(luò)的重構(gòu)是網(wǎng)絡(luò)表示學(xué)習(xí)一個(gè)研究難點(diǎn)。

3) 現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)算法只能適用于一般的網(wǎng)絡(luò)應(yīng)用任務(wù)，如節(jié)點(diǎn)分類和鏈路預(yù)測等，這些方法主要針對一般的網(wǎng)絡(luò)結(jié)構(gòu)，對一些具體的網(wǎng)絡(luò)應(yīng)用任務(wù)可能并不適用。

[1] SUN Y, HAN J. Mining heterogeneous information networks: a structural analysis approach[J]. ACM Sigkdd Explorations Newsletter, 2013, 14(2): 20-28.

[2] ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323-2326.

[3] SAUL L K, ROWEIS S T. An introduction to locally linear embedding[J]. Journal of Machine Learning Research, 2008.

[4] BELKIN M, NIYOGI P. Laplacian eigenmaps and spectral techniques for embedding and clustering[J]. Advances in Neural Information Processing Systems, 2002, 14(6): 585-591.

[5] HE X, NIYOGI P. Locality preserving projections[C]//Advances in Neural Information Processing Systems. 2004: 153-160.

[6] AHMED A, SHERVASHIDZE N, NARAYANAMURTHY S, et al. Distributed large-scale natural graph factorization[C]// International Conference on World Wide Web. ACM, 2013: 37-48.

[7] CAO S, LU W, XU Q. GraRep: learning graph representations with global structural information[C]//ACM International on Conference on Information and Knowledge Management. 2015: 891-900.

[8] CHENG W, GREAVES C, WARREN M. From-gram to skipgram to concgram[J]. International Journal of Corpus Linguistics, 2006, 11(4):411-433.

[9] OU M, CUI P, PEI J, et al. Asymmetric transitivity preserving graph embedding[C]//The 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016: 1105-1114.

[10] KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43.

[11] MIKOLOV T, CHEN K, CORRADO G, et al. Efficient estimation of word representations in vector space[J]. Computer Science, 2013.

[12] PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk:online learning of social representations[C]//ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2014: 701-710.

[13] GROVER A, LESKOVEC J. node2vec: scalable feature learning for networks[C]//The 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2016: 855-864.

[14] TANG J, QU M, WANG M, et al. LINE: large-scale information network embedding[C]//International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2015: 1067-1077.

[15] WANG D, CUI P, ZHU W. structural deep network embedding[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016: 1225-1234.

[16] HAMILTON W, YING Z, LESKOVEC J. Inductive representation learning on large graphs[C]//Advances in Neural Information Processing Systems. 2017: 1024-1034.

[17] WANG H, WANG J, WANG J, et al. GraphGAN: graph representation learning with generative adversarial nets[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018.

[18] TU C, ZHANG W, LIU Z, et al. Max-margin DeepWalk: discriminative learning of network representation[C]//International Joint Conference on Artificial Intelligence. AAAI Press, 2016. 3889: 3895.

[19] YANG C, ZHAO D, ZHAO D, et al. Network representation learning with rich text information[C]// International Conference on Artificial Intelligence. AAAI Press, 2015: 2111-2117.

[20] SUN X, GUO J, DING X, et al. A general framework for content-enhanced network representation learning[J]. arXiv preprint arXiv:1610.02906,2016.

[21] PAN S, WU J, ZHU X, et al. Tri-party deep network representation[C]//International Joint Conference on Artificial Intelligence. AAAI Press, 2016:1895-1901.

[22] 孫藝洲, 韓家煒. 異構(gòu)信息網(wǎng)絡(luò)挖掘原理與方法[M]. 北京: 機(jī)械工業(yè)出版社, 2016,2. SUN Y Z, HAN J W. Principles and methods of heterogeneous information network mining[M]. Beijing: Machinery Industry Press, 2016.

[23] DONG Y, CHAWLA N V , SWAMI A, et al. metapath2vec: scalable representation learning for heterogeneous networks[C]// ACM Sigkdd International Conference on Knowledge Discovery & Data Mining. 2017:135-144.

[24] SUN G, ZHANG X. Graph embedding with rich information through heterogeneous network[J]. arXiv preprint arXiv: 1710.06879, 2017.

[25] TANG J, QU M, MEI Q. Pte: Predictive text embedding through large-scale heterogeneous text networks[C]//The 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2015: 1165-1174.

[26] SHI C, HU B, ZHAO X, et al. Heterogeneous information network embedding for recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2019, 31(2): 357-370.

[27] SUN Y, HAN J, YAN X, et al. Pathsim: meta path-based top-similarity search in heterogeneous information networks[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 992-1003.

[28] SUN Y, NORICK B, HAN J, et al. PathSelClus: integrating meta-path selection with user-guided object clustering in heterogeneous information networks[J]. ACM Transactions on Knowledge Discovery from Data, 2013, 7(3): 1-23.

[29] LUO C, GUAN R, WANG Z, et al. Hetpathmine: a novel transductive classification algorithm on heterogeneous information networks[C]//European Conference on Information Retrieval. 2014: 210-221.

[30] KONG X, YU P S, DING Y, et al. Meta path-based collective classification in heterogeneous information networks[J]. 2012: 1567-1571.

[31] FU T Y, LEE W C, LEI Z. HIN2Vec: explore meta-paths in heterogeneous information networks for representation learning[C]//ACM, 2017: 1797-1806.

Research and development of network representation learning

YIN Ying1, JI Lixin1, HUANG Ruiyang1, DU Lixin2

1. China National Digital Switching System Engineering & Technological Center, Zhengzhou 450003, China 2. The 63898 Troop of PLA, Luoyang 471003, China

Network representation learning is a bridge between network raw data and network application tasks which aims to map nodes in the network to vectors in the low-dimensional space. These vectors can be used as input to the machine learning model for social network application tasks such as node classification, community discovery, and link prediction. The traditional network representation learning methods are based on homogeneous information network. In the real world, the network is often heterogeneous with multiple types of nodes and edges. Moreover, from the perspective of time, the network is constantly changing. Therefore, the research method of network representation learning is continuously optimized with the complexity of network data. Different kinds of network representation learning methods based on different networks were introduced and the application scenarios of network representation learning were expounded.

large-scale information network, network representation learning, network embedding, deep learning

The National Natural Science Foundation for Creative Research Groups of China(No.61521003)

TP391.4

A

10.11959/j.issn.2096-109x.2019019

尹贏（1994? ），女，四川綿竹人，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心碩士生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)、網(wǎng)絡(luò)表示學(xué)習(xí)。

吉立新（1969? ），男，江蘇淮安人，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心研究員，主要研究方向?yàn)橥ㄐ啪W(wǎng)信息安全。

黃瑞陽（1986? ），男，福建漳州人，國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心助理研究員，主要研究方向?yàn)槲谋就诰?、圖挖掘。

杜立新（1996? ），男，甘肅武威人，主要研究方向?yàn)榇髷?shù)據(jù)分析。

2018?10?25；

2018?12?20

尹贏，15883880517@163.com

國家自然科學(xué)基金創(chuàng)新群體資助項(xiàng)目（No.61521003）

尹贏, 吉立新, 黃瑞陽, 等. 網(wǎng)絡(luò)表示學(xué)習(xí)的研究與發(fā)展[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 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.