孫金清，周 慧，趙中英

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

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

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

為有效地掌握網絡表示學習領域的學術思路和動態(tài)，本研究對近年來面向同構網絡和屬性網絡的代表性的表示學習算法進行分類介紹和比較。特別地，對于同構網絡，根據算法所應用的理論基礎進行分類介紹。對于屬性網絡，根據算法所結合的屬性信息種類進行分類介紹。此外，對比分析了各類別下的網絡表示學習算法的時間復雜度和優(yōu)缺點。

1 問題定義

本節(jié)給出網絡和屬性網絡形式化定義，并對同構網絡和屬性網絡上的表示學習進行問題描述。

定義1網絡[15]。網絡是對關系型數據的刻畫，主要由節(jié)點和和連接這些節(jié)點的邊構成，表示諸多對象及其相互聯(lián)系，符號表示為G(V,E)，其中V表示網絡G中的節(jié)點集，E表示邊集。

問題1同構網絡表示學習[17]。給定同構網絡G(V,E)，目標是為網絡中的節(jié)點v∈V(或邊、子圖等)學習映射關系f:v→rv∈Rd，其中rv為節(jié)點v學得的低維稠密向量，d是表征向量的維度，d?|V|，轉換函數f用于捕獲原網絡中節(jié)點之間的拓撲關聯(lián)關系。

問題2屬性網絡表示學習[16-17]。給定屬性網絡G(V,E,A)，目標是為屬性網絡中的節(jié)點v∈V(或邊、子圖等)學習映射關系f:v→rv∈Rd，其中rv是為節(jié)點v學得的低維稠密向量，d是表征向量的維度，d?|V|，轉換函數f用于捕獲原網絡中復雜的拓撲和屬性關聯(lián)關系。

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

表1 論文中的常用符號

2 同構網絡表示學習

本節(jié)介紹基于網絡拓撲信息的同構表示學習算法。根據理論基礎，將代表性算法分為基于非線性流形學習、基于自定義損失函數、基于簡單神經網絡、基于矩陣分解以及基于深層神經網絡的網絡表示學習算法等5類。

2.1 基于非線性流形學習的網絡表示學習算法

非線性流形學習常用于對高維的流形數據進行非線性降維，代表性算法有Isomap(isometric feature mapping)[18]、LLE(locally linear embedding)[19]和LE(laplacian eigenmaps)[20]等。這些算法通過構建鄰域圖來發(fā)現高維空間中的數據的低維結構，并得到對應的低維向量表示，屬于網絡表示學習的早期成果。下面對這些代表性算法分別進行介紹。

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

圖1 Isomap算法節(jié)點距離計算示例[19]

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

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

本節(jié)中所介紹的算法僅保留了節(jié)點的一階相似度，無法衡量全局性的數據特征，而且計算時間復雜度較高，不能擴展到大規(guī)模網絡上。

2.2 基于自定義損失函數的網絡表示學習算法

LINE算法[23]通過設計自定義的損失函數來建模網絡中節(jié)點的一階和二階相似度。其中一階相似性指的是相連節(jié)點間的相似度，對應的目標函數如式(1)所示；二階相似性指的是共享多個相同鄰居的節(jié)點之間的相似度，對應的目標函數如式(2)所示。該算法使用隨機梯度下降法優(yōu)化目標函數并更新節(jié)點的向量表示。

(1)

(2)

2.3 基于簡單神經網絡的網絡表示學習算法

簡單神經網絡在網絡表示學習中的應用主要受到Word2vec[24]詞向量訓練模型的啟發(fā)。DeepWalk算法[25]首次將詞向量訓練模型引入到網絡中，用于學習網絡中節(jié)點的向量表示；該算法采用截斷隨機游走的方式為網絡中的每個節(jié)點構建鄰域節(jié)點，然后使用詞向量訓練模型Skip-Gram[24]進行訓練，最大化鄰域節(jié)點在目標節(jié)點周圍出現的概率，由此得到每個節(jié)點的低維向量表示。

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

NBNE(neighbor based node embeddings)算法[28]和ProxEmbed算法[29]也運用了隨機游走與神經網絡相結合的思想對網絡進行表示學習。總的來說，基于簡單神經網絡方法的優(yōu)點是時間復雜度低，但此類算法缺少明確的目標函數，同時通過特定步長的隨機游走并不能夠充分捕獲復雜的網絡結構信息[23]。

2.4 基于矩陣分解的網絡表示學習算法

矩陣分解指的是將一個矩陣分解成多個矩陣，分解后的矩陣能夠以低于原矩陣的維度來近似地保留原矩陣的特征，這種理論被廣泛用于網絡表示學習任務中。

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

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

2.5 基于深層神經網絡的網絡表示學習算法

深層神經網絡在不同的領域都有著廣泛的應用，而且在學習不同層次的數據特征方面已經取得了較好的研究成果[33]。在網絡表示學習方向上，學者運用深層神經網絡來捕獲網絡中復雜的非線性信息。

Jacobs等[34]提出一種基于深層神經網絡的半監(jiān)督模型SEANO，為具有局部標簽和屬性信息的網絡節(jié)點進行向量表示。該模型通過深度學習框架將節(jié)點的拓撲結構信息、屬性信息相關聯(lián)。

Cao等[35]指出基于奇異值分解的網絡表示學習算法局限于從線性關系中推出節(jié)點的向量表示，無法捕獲到網絡中存在的復雜非線性關系，為解決此問題提出DNGR模型(如圖2所示)，該模型首先采用帶權隨機游走方法來捕獲網絡結構信息，并生成概率共現矩陣；然后在此基礎上計算得到點互信息矩陣；最后采用SDAE(dtacked denosing autoencoders)算法[36]對向量進行分層學習并降維，最終得到網絡中節(jié)點的向量表示。

圖2 DNGR模型框架[36]

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

圖3 SDNE模型框架[37]

2.6 同構網絡表示學習算法對比

本節(jié)中，對同構網絡表示學習算法進行對比，包括算法的時間復雜度和優(yōu)缺點，總結如表2所示。

表2 同構網絡表示學習算法對比

3 屬性網絡表示學習算法

第2節(jié)中介紹的網絡表示學習算法只是對節(jié)點在網絡中的拓撲關系和結構相似性進行編碼與計算。現實生活中的網絡蘊含著豐富的異構信息，例如網絡中節(jié)點和邊上的標簽信息以及文本特征信息等，若這些信息得到合理的運用，會對網絡表示學習起到很好的輔助作用。本節(jié)中以異構信息的種類作為分類依據，對現有的屬性網絡表示學習算法進行具體的描述，并分析這些算法的異同之處。

3.1 嵌入社區(qū)信息

現實網絡中蘊藏著豐富的社區(qū)信息，尤其在社交網絡中最為常見，反映了網絡中的個體與其他個體之間的關聯(lián)關系，是對網絡中節(jié)點進行分析和研究的重要屬性，也是對網絡中節(jié)點交互關系預測的重要依據。

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

(3)

除了利用社區(qū)信息對網絡中的單個節(jié)點進行表示學習之外，還有算法可以直接對網絡中的整個社區(qū)進行表示學習。ComE算法[40]首先運用一些經典的社區(qū)發(fā)現算法(如譜聚類)對網絡進行社區(qū)發(fā)現，根據社區(qū)發(fā)現結果為每個節(jié)點進行社區(qū)標注；然后運用經典的表示學習算法(LINE、DeepWalk等)對節(jié)點進行嵌入；最后把所屬相同社區(qū)的節(jié)點表示進行聚合。模型中節(jié)點嵌入、社區(qū)發(fā)現以及社區(qū)嵌入之間相互促進，節(jié)點的嵌入增強了社區(qū)發(fā)現并擬合出更好的社區(qū)嵌入。

3.2 嵌入標簽信息

3.2.1 嵌入節(jié)點的標簽信息

傳統(tǒng)的無監(jiān)督網絡表示學習算法，雖然能夠對網絡節(jié)點的拓撲特性進行學習，但是對后續(xù)的一些機器學習任務缺乏區(qū)別性和針對性，進而有學者提出了有監(jiān)督的表示學習方法，訓練出具有針對性的表示向量。

在DeepWalk算法基礎上，MMDW(max-margin deepwalk)算法[30]添加了一個有監(jiān)督的最大間隔分類器，利用節(jié)點的標簽信息進行有監(jiān)督學習。算法得到的節(jié)點向量中包含了網絡的拓撲信息和具有區(qū)別性的標簽信息，分類效果優(yōu)于其他無監(jiān)督的算法。Li等[41]將截斷隨機游走的DeepWalk算法與分類器相結合，提出了與MMDW算法相類似的DDRW(discriminative deep random walk)算法。

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

圖4 MVE模型框架[43]

3.2.2 嵌入邊的標簽信息

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

圖5 TransNet模型框架[43]

3.3 嵌入文本信息

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

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

圖6 TADW算法[46]

(4)

Huang等[16]提出AANE算法。根據網絡拓撲結構，算法對節(jié)點間的一階相似度進行建模，同時根據屬性信息生成節(jié)點的屬性關聯(lián)矩陣，使得節(jié)點向量與節(jié)點的屬性信息盡可能的匹配。算法將網絡中的屬性信息和拓撲信息進行高效匯聚，使用矩陣分解方法生成向量表示。

GraphSAGE模型[47]是對傳統(tǒng)圖卷積神經網絡的延伸，模型中目標節(jié)點的向量表示由其鄰居節(jié)點的信息(拓撲信息和屬性信息)所決定。模型訓練的過程如圖7所示，首先從源節(jié)點的k階鄰居中選擇一定數量的節(jié)點；接下來對不同的k階鄰居節(jié)點訓練出相應的聚合函數(例如Mean aggregator、LSTM aggregator等)。最終得到的節(jié)點向量表示匯聚了其各自鄰居的信息，不僅可對訓練過程中不可見的節(jié)點信息進行預測，而且能夠結合后續(xù)的任務進行有監(jiān)督學習。

圖7 GraphSAGE模型[48]

3.4 嵌入多類型屬性信息

另外還有一些網絡表示學習算法，綜合學習了不同類型的屬性信息。

LANE(label informed attributed network embedding)算法[48]同時學習屬性網絡中的節(jié)點相似度信息和標簽信息，綜合兩者生成節(jié)點的向量表示。圖8展示了算法的計算流程。算法主要分為兩個模塊，在第一個模塊中算法對網絡的屬性信息和拓撲信息進行嵌入，第二個模塊將節(jié)點的標簽信息進行嵌入。LANE算法通過相關投影模式將學得的這三類信息映射到新的維度空間中，最大化三者在新空間上的關聯(lián)性，進而得出最終的向量表示。

圖8 LANE模型框架[49]

SNE(docial network embedding)算法[49]運用深層神經網絡對不同類型的節(jié)點信息進行綜合學習，如圖9所示。該算法將節(jié)點的屬性作為神經網絡的輸入，由兩個全連接層組成的嵌入層對屬性向量進行降維，進而通過隱含層對向量進行非線性映射，最后經過一個隱含層后得到的向量轉化成目標節(jié)點與其它節(jié)點連接的概率向量。最終節(jié)點的向量表示由最后一個隱含層的向量和連接到輸出層的權重向量相加得到。

圖9 SNE模型框架[50]

3.5 屬性網絡表示學習算法對比

從算法的時間復雜度和其優(yōu)缺點等方面對上述屬性網絡表示學習算法進行比較，如表3所示。

表3 屬性網絡表示學習算法對比

4 應用場景

網絡表示學習具有多種任務應用場景，典型的有節(jié)點分類、鏈接預測、聚類和推薦等。本節(jié)選取不同類別下的代表性算法，并將這些算法在節(jié)點分類這一應用場景下進行測試，比較不同算法在相同數據集上的實驗結果。選取了8個代表性的網絡表示學習算法進行實驗對比，分別為同構網絡表示學習類別下的DeepWalk[25]、Node2vec[26]、LINE[23]和GraRep[31]等算法，和屬性網絡表示學習類別下的CANE[45]、TADW[46]、SEANO[34]和GraphSAGE[47]等算法。

4.1 數據集

選用以下三種常用的數據集進行實驗。

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

②Citeseer引文數據集的子集，包含3 312個節(jié)點(論文)和4 732條邊(引用關系)。論文來自計算機科學和信息科學等相關領域，共分為6個類別。每篇論文具有一個3 703維的屬性向量，屬性向量提取自論文的題目和摘要。

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

將這三種數據集的信息整理如表4所示。

表4 三種數據集的信息

4.2 節(jié)點分類實驗結果

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

圖10 Cora數據集上的實驗結果

圖11 Citeseer數據集上的實驗結果

圖12 Wiki數據集上的實驗結果

5 總結

本研究面向同構網絡和屬性網絡，對相關代表性的網絡表示學習算法進行了分類介紹和比較。與基于拓撲信息相比，結合網絡中蘊含的屬性信息進行表示學習更易捕獲到真實網絡中的復雜關系，也能獲得更具區(qū)別力的表征向量。網絡表示學習研究雖然已經取得了豐碩的成果，但仍然面臨著巨大的挑戰(zhàn)：

1)大規(guī)模網絡表示學習。在實際場景中的社交網絡規(guī)?？蛇_到上億節(jié)點，然而已有的網絡表示學習模型無法應對此類規(guī)模的網絡。同時網絡中包含的噪音甚至誤導性數據也逐漸增多，面對噪音數據應該如何有效處理、過濾，也是網絡表示學習需要考慮的問題之一。

2)網絡動態(tài)變化的適應性。隨著5G時代的來臨，網絡結構及其包含的信息瞬息萬變。如何將網絡表示學習方法與時代的發(fā)展步伐相匹配，對動態(tài)變化的網絡進行表示學習，值得進一步研究。