基于隨機游走的圖嵌入研究綜述

臘志垚，錢育蓉，冷洪勇，顧天宇，張繼元，李自臣

1.新疆大學(xué) 軟件學(xué)院，烏魯木齊 830046

2.新疆大學(xué) 新疆維吾爾自治區(qū)信號檢測與處理重點實驗室，烏魯木齊 830046

3.北京理工大學(xué) 計算機學(xué)院，北京 100081

4.廣東水利電力職業(yè)技術(shù)學(xué)院 大數(shù)據(jù)與人工智能學(xué)院，廣州 510635

近年來，圖結(jié)構(gòu)信息在眾多系統(tǒng)中都發(fā)揮著重要的支柱功能，圖分析在計算機科學(xué)及相關(guān)應(yīng)用領(lǐng)域中引起廣泛的關(guān)注。圖作為結(jié)構(gòu)化知識庫，不但能夠協(xié)助更高效地保存和訪問交互實體之間的關(guān)系知識，同時在現(xiàn)代機器學(xué)習(xí)任務(wù)中也起著重要的作用，機器學(xué)習(xí)任務(wù)使用圖作為特征信息，來預(yù)測并發(fā)現(xiàn)新的模型。社交網(wǎng)絡(luò)[1]、語言學(xué)[2]、生物學(xué)（蛋白質(zhì)-蛋白質(zhì)網(wǎng)絡(luò)）[3]和推薦系統(tǒng)[4]——這些領(lǐng)域及更多相關(guān)領(lǐng)域的知識都很容易被建模為圖，這些圖可以捕捉單個單元（即節(jié)點）之間的交互（即邊）。圖有很多具體使用價值，例如：蛋白質(zhì)作用分類、協(xié)作網(wǎng)絡(luò)角色劃分、社交網(wǎng)絡(luò)用戶推薦或預(yù)測藥物分子治療方向，圖數(shù)據(jù)的使用會給各行各業(yè)帶來巨大的價值。

從機器學(xué)習(xí)的角度來看，圖數(shù)據(jù)分析面臨的挑戰(zhàn)在于圖結(jié)構(gòu)的高維非歐信息能否直接編碼到低維的特征向量中。因此，基于圖的機器學(xué)習(xí)的核心是找到一種將圖結(jié)構(gòu)的信息結(jié)合到機器學(xué)習(xí)模型中的方法[5]。傳統(tǒng)的提取圖結(jié)構(gòu)信息的方法，主要是圖統(tǒng)計（如：度或聚類系數(shù)）[6]、核函數(shù)[7]或通過精心設(shè)計的特征來提取局部鄰域結(jié)構(gòu)[8]，但設(shè)計這些特性是十分耗時且代價高昂的。由于上面的問題，一種新的學(xué)習(xí)編碼圖結(jié)構(gòu)信息的表示學(xué)習(xí)方法（圖嵌入）引起廣泛的關(guān)注。這種表示學(xué)習(xí)方法很好地解決以前方法面臨的困難，它和以前方法主要不同是如何處理表示圖結(jié)構(gòu)。其主要思想是通過學(xué)習(xí)一種映射關(guān)系，將圖中的節(jié)點或整個（子）圖映射為低維向量空間Rd中的點，通過不斷的優(yōu)化，確保嵌入空間向量最大程度的反應(yīng)原始圖結(jié)構(gòu)。圖嵌入向量直接作為下一步機器學(xué)習(xí)任務(wù)的特征輸入，即圖嵌入跳過圖數(shù)據(jù)預(yù)處理的步驟，直接可以把圖的預(yù)處理作為機器學(xué)習(xí)任務(wù)本身。

隨著圖嵌入技術(shù)的發(fā)展，隨機游走被用來表示圖中的屬性，例如節(jié)點中心性[9]和相似性[10]。當(dāng)只能觀察部分圖或圖太大而無法整體測量時，該類型的方法是特別有用的。該類方法不僅幫助捕獲網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，還可以通過迭代的方式適應(yīng)圖的微小變化。本文重點介紹基于隨機游走的圖嵌入研究方法，通過隨機游走的方式，它把有復(fù)雜結(jié)構(gòu)信息的圖數(shù)據(jù)，提取成類似于語句序列的節(jié)點序列，其后基于語義分析的方法就可以用于圖嵌入向量的生成。雖然基于隨機游走的圖嵌入方法只是圖嵌入中的一類，但卻是最經(jīng)典的方法。

1 符號與基本定義

下面定義幾個相關(guān)概念，類似于Wang等[11]的定義。

圖1 圖嵌入通用框架Fig.1 General framework for graph embedding

定義2（相似度）邊的權(quán)重sij=wij，也稱為節(jié)點vi和節(jié)點vj的一階相似度，它也是節(jié)點之間相似度的首要度量指標(biāo)。若節(jié)點vi和節(jié)點vj擁有相似的一階相似度，就稱節(jié)點vi和節(jié)點vj擁有二階相似度。二階相似度描述的是節(jié)點之間的領(lǐng)域結(jié)構(gòu)的相似度。

定義3（信息網(wǎng)絡(luò)[12]）一個信息網(wǎng)絡(luò)是一個有向圖G=(V,E,Φ,Ψ)，其中V是一個點集，E∈V×V是一個邊集，Φ:V→A和Ψ:E→R分別是節(jié)點和邊的類型映射函數(shù)，當(dāng)|A|>1 或者|R|>1，該網(wǎng)絡(luò)稱為異構(gòu)信息網(wǎng)絡(luò)（heterogeneous information network，HIN）；否則，它是一個同構(gòu)信息網(wǎng)絡(luò)。

定義5（元圖[14]）元圖是在給定的HIN 模式TG=(L,R) 上定義的有向無環(huán)圖（directed acyclic graph，DAG）g=(N,M,ns,nt)，它只有一個源節(jié)點ns（即入度為0）和一個目的節(jié)點nt（即出度為0）。N是節(jié)點類型n∈L的集合，M是邊類型m∈R的集合。

2 隨機游走的圖嵌入模型分類

基于隨機游走的圖嵌入算法是借鑒自然語言處理中的詞-向量模型[15]，使用不同的隨機游走策略生成隨機游走的節(jié)點序列，形成語料庫，然后再利用Skip-Gram模型[16]或其變種[17]，生成圖的嵌入向量?；陔S機游走的圖嵌入模型有著不俗的表現(xiàn)，特別是當(dāng)圖規(guī)模十分巨大時，隨機游走方法可以很好地保留圖的結(jié)構(gòu)特性，生成可以近似反應(yīng)節(jié)點屬性的嵌入向量?，F(xiàn)有的基于隨機游走的圖嵌入模型主要分為兩大類：基于經(jīng)典隨機游走的模型和基于屬性游走的模型。

2.1 經(jīng)典隨機游走模型

經(jīng)典的隨機游走采用不同的游走策略在圖上行走，形成節(jié)點序列，最后生成訓(xùn)練需要的語料庫。這種方式生成的語料庫，是同類型或不同類型的節(jié)點構(gòu)成的序列集合，該類模型分為兩類：同構(gòu)網(wǎng)絡(luò)的模型和異構(gòu)網(wǎng)絡(luò)的模型。本節(jié)重點介紹這兩種網(wǎng)絡(luò)中經(jīng)典的基于隨機游走圖嵌入模型，其中前四個模型為同構(gòu)網(wǎng)絡(luò)經(jīng)典模型；后三個模型為異構(gòu)網(wǎng)絡(luò)經(jīng)典模型，最后總結(jié)對比該類方法中不同模型的特點。

2.1.1 DeepWalk模型

DeepWalk模型[18]是基于Word2Vec模型[15]提出的學(xué)習(xí)網(wǎng)絡(luò)頂點潛在表示的方法，借鑒了語言建模算法的思想，利用隨機游走算法生成自己的語料庫，并將圖中的節(jié)點視為自己的詞匯表，再通過Skip-Gram 算法[16]最大化節(jié)點序列中窗口范圍內(nèi)節(jié)點的共現(xiàn)概率，然后將節(jié)點映射到嵌入向量空間。DeepWalk模型的目標(biāo)函數(shù)為：

如圖2 是DeepWalk 模型框架，在實際應(yīng)用中，直接計算Pr(uk|Φ(vj))(uk∈V)的歸一化因子的代價是昂貴的。因此，把頂點集轉(zhuǎn)換為二叉樹，為隨機游走頻繁節(jié)點分配較短的路徑，可以進一步加快訓(xùn)練的過程。該模型在小型圖和大型圖的嵌入表示中都有不錯的性能體現(xiàn)，但是該模型只適用于無權(quán)圖，且只保留了圖的二階相似性，有限的節(jié)點序列長度也影響了獲取圖的全局信息的能力。

圖2 DeepWalk模型結(jié)構(gòu)Fig.2 Model framework of DeepWalk

2.1.2 Node2Vec模型

Node2Vec 模型[19]是在DeepWalk 模型的基礎(chǔ)上，引進了一個有偏的隨機游走的過程，在同質(zhì)性和結(jié)構(gòu)性[20]之間進行權(quán)衡，可以探索不同的鄰域，最終保證生成的嵌入向量質(zhì)量更高。Node2Vec模型的目標(biāo)函數(shù)為：

式中f:V→Rd是從節(jié)點到特征表示的映射函數(shù)。對于大型網(wǎng)絡(luò)，每個節(jié)點劃分函數(shù)Zu的計算成本太高，一般使用負采樣對其進行近似[21]。但使用目標(biāo)函數(shù)（2）還需要滿足兩條假設(shè)：條件獨立性假設(shè)和特征空間對稱性假設(shè)。

Node2Vec模型最大的特點就是設(shè)計有偏的隨機游走策略，通過設(shè)置p和q兩個參數(shù)來平衡廣度優(yōu)先搜索（breadth-first search，BFS）和深度優(yōu)先搜索（depth-first search，DFS），來保證嵌入向量能夠保持圖結(jié)構(gòu)的同質(zhì)性和結(jié)構(gòu)性，如圖3 是Node2Vec 模型的轉(zhuǎn)移策略。其中該算法在二階隨機游走中的轉(zhuǎn)移概率為：

圖3 Node2Vec模型轉(zhuǎn)移策略Fig.3 Transfer strategy of Node2Vec model

此時，αp,q( )t,x的取值由p和q確定。雖然有偏的隨機游走能幫助保存更多的圖的結(jié)構(gòu)信息，但對于圖的全局信息的捕獲能力仍有待提高。

2.1.3 WalkLets模型

DeepWalk 模型和Node2Vec 模型通過隨機游走的方式把不同距離的節(jié)點連接起來，然后生成多個隨機游走序列來隱式的保持節(jié)點之間的高階相似度。Walk-Lets模型[22]將顯式建模的思想與隨機游走相結(jié)合，顯式地編碼多尺度頂點關(guān)系，該模型設(shè)計了多跳的方式來改變隨機游走的策略，游走時跳過圖中的一些節(jié)點，這樣生成的隨機游走序列集可以直接用于DeepWalk的模型上訓(xùn)練。WalkLets模型的目標(biāo)函數(shù)為：

為了解決該模型多跳計算復(fù)雜度的問題，就需要忽略相鄰節(jié)點之間的順序，通過一個節(jié)點預(yù)測其局部結(jié)構(gòu)，而不是使用上下文來預(yù)測缺失的節(jié)點。

該模型采用WalkLets模型使用了DeepWalk模型的嵌入向量處理的方法，但采用了不同于DeepWalk 模型的游走方式，每次跳過k?1 個節(jié)點，可以幫助捕獲更遠距離的圖的信息。相比于DeepWalk 模型，該模型可以捕獲節(jié)點和社區(qū)之間不同尺度的信息，生成更豐富的節(jié)點序列，建模節(jié)點多尺度的信息。

2.1.4 HARP模型

DeepWalk 模型和Node2Vec 模型使用短隨機游動來探索節(jié)點的局部鄰域，而忽略了長距離的全局關(guān)系，且這兩種模型使用隨機梯度下降的方式解決非凸優(yōu)化的問題，該策略可能會陷入局部最優(yōu)解。HARP（hierarchical representation learning for network）模型[23]通過更好的權(quán)重初始化來改進方案并避免局部最優(yōu)解，該模型主要分為三部分：圖粗粒度化、圖嵌入和表示提升。HARP 模型通過圖粗粒度化遞歸地合并原始圖中的節(jié)點和邊，獲得一系列具有相似結(jié)構(gòu)的較小圖；然后，生成粗粒度化的節(jié)點嵌入；再通過層次結(jié)構(gòu)傳播和優(yōu)化嵌入，不斷的優(yōu)化原圖的嵌入。該算法的核心是圖的粗粒度化，目的是降低圖的規(guī)模同時保持圖的基本結(jié)構(gòu)，這一部分主要分為兩個技巧：邊塌陷和星狀塌陷。

（2）星狀塌陷：大部分真實的網(wǎng)絡(luò)是無標(biāo)度網(wǎng)絡(luò)，這時，使用邊塌陷效果不明顯。所以HARP模型采用了星狀塌陷的方式，就把共同以中心點為鄰居的節(jié)點兩兩進行合并，這樣也保證了圖結(jié)構(gòu)的二階相似度。

因此，HARP 可以作為一種通用的元策略，用于改進隨機游走方法的路徑，獲取更好的目標(biāo)函數(shù)解。但是這種粗粒度的方式也會損失一部分圖的結(jié)構(gòu)信息，可能會導(dǎo)致生成的嵌入向量的精確度下降。

2.1.5 metapath2vec和metapath2vec++模型

前面的方法都是對同構(gòu)網(wǎng)絡(luò)的嵌入，沒有考慮到現(xiàn)實中異構(gòu)網(wǎng)絡(luò)，針對異構(gòu)網(wǎng)絡(luò)多類型節(jié)點和鏈接的存在，Dong 等[13]提出一種用于異構(gòu)信息網(wǎng)絡(luò)的頂點嵌入方法，其中包含兩個可伸縮的表示學(xué)習(xí)模型metapath2vec 和metapath2vec++，metapath2vec 模型利用元路徑（meta-path）隨機游走構(gòu)建節(jié)點的異構(gòu)鄰域，然后再利用Skip-Gram模型建模結(jié)構(gòu)和語義相近的節(jié)點，完成節(jié)點嵌入。metapath2vec模型通過在頂點v的領(lǐng)域Nt(v),t∈Tv最大化條件概率來學(xué)習(xí)異構(gòu)網(wǎng)絡(luò)G=(V,E,T)上的頂點特征：

式中，Vt是網(wǎng)絡(luò)中t類型的頂點集合。在此過程中，metapath2vec++模型為Skip-Gram模型輸出層中的每種類型的鄰域指定一組多項式分布，而在metapath2vec，DeepWalk和node2vec中，Skip-Gram模型輸出多項式分布的維度等于整個網(wǎng)絡(luò)中頂點的數(shù)目。然而，對于metapath2vec++的Skip-Gram 模型，其針對特定類型的輸出多項式的維度取決于網(wǎng)絡(luò)中當(dāng)前類型頂點的數(shù)目。最終可得到如下的目標(biāo)函數(shù)：

因此，metapath2vec++模型進一步支持異構(gòu)網(wǎng)絡(luò)中結(jié)構(gòu)和語義關(guān)聯(lián)的同時建模。

2.1.6 HIN2Vec模型

上述模型工作大多落腳于同構(gòu)網(wǎng)絡(luò)，而且往往只關(guān)注節(jié)點之間的整合關(guān)系或者限制類型之間的關(guān)系。針對這種情況，F(xiàn)u 等[14]提出了HIN2Vec 模型，旨在通過利用節(jié)點之間不同類型的關(guān)系來捕獲HINs 中豐富的語義。由于不同的元路徑可能有不同的語義信息，所以作者認(rèn)為對嵌入在元路徑和整個網(wǎng)絡(luò)結(jié)構(gòu)中的豐富信息進行編碼，有助于學(xué)習(xí)更有意義的表示。HIN2Vec模型主要分為兩個部分：基于隨機游走的數(shù)據(jù)生成和表示學(xué)習(xí)。第一部分工作是利用隨機游走與負采樣技術(shù)相結(jié)合，生成用于表示學(xué)習(xí)的數(shù)據(jù)；第二部分表示學(xué)習(xí)的核心是一個神經(jīng)網(wǎng)絡(luò)模型，學(xué)習(xí)表示向量的辦法是最大化預(yù)測節(jié)點之間關(guān)系的可能性。因此，HIN2Vec模型保留了更多的上下文信息，不僅假設(shè)存在關(guān)系的兩個節(jié)點是相關(guān)的，而且還區(qū)分節(jié)點之間的不同關(guān)系，并通過共同學(xué)習(xí)關(guān)系向量區(qū)別對待。HIN2Vec模型的目標(biāo)函數(shù)為：

HIN2Vec 模型通過多任務(wù)學(xué)方法表示節(jié)點和關(guān)系的表示向量，把不同關(guān)系的豐富信息和整體網(wǎng)絡(luò)結(jié)構(gòu)聯(lián)合嵌入到節(jié)點向量中。但是對于一個復(fù)雜網(wǎng)絡(luò)來說，確定兩個節(jié)點之間的所有關(guān)系是非常困難的。因此，為了簡化這個問題，把預(yù)測兩個節(jié)點之間的關(guān)系轉(zhuǎn)換為二分類問題，即給定兩個節(jié)點x、y，預(yù)測它們之間的關(guān)系r是否存在。

2.1.7 MetaGraph2Vec模型

異構(gòu)信息網(wǎng)絡(luò)（HIN）中的網(wǎng)絡(luò)嵌入是一項具有挑戰(zhàn)性的任務(wù)，因為不同節(jié)點類型的復(fù)雜性和節(jié)點之間豐富的關(guān)系。前面提出的方法大多是基于元路徑的來描述HIN中的關(guān)系，但卻不能很好地捕獲節(jié)點之間豐富的上下文語義信息，針對這種情況，提出了一個新的元圖概念，以捕獲更豐富的結(jié)構(gòu)、上下文和語義之間的遠程節(jié)點。然后在此基礎(chǔ)上提出了一種新的嵌入學(xué)習(xí)算法，即MetaGraph2Vec，它使用Metagraph 來指導(dǎo)隨機游走的生成，并學(xué)習(xí)多類型異構(gòu)信息網(wǎng)絡(luò)節(jié)點的潛在嵌入。MetaGraph2Vec模型的嵌入函數(shù)為：

在Φ(vi)已知的條件下，最大化vi的上下文節(jié)點在w窗口大小內(nèi)出現(xiàn)的概率，在模型實際的運算時，使用了負采樣來近似目標(biāo)函數(shù)，減少計算復(fù)雜度。

MetaGraph2Vec 模型的特點是在元圖的隨機游走，元圖包含節(jié)點之間的多條路徑，每條路徑描述一種類型的關(guān)系，隨機游走后便于捕獲網(wǎng)絡(luò)的上下文和語義信息。圖4（a）顯示了HIN的模式，該模式由3種節(jié)點類型組成：作者（A）、論文（P）和地點（V），以及3 種邊緣類型：作者撰寫論文、引用和發(fā)表。元路徑P1:A →P →V →P →A 描述了兩位作者在同一期刊發(fā)表論文的關(guān)系，而路徑P2:A →P →A →P →A 描述兩位作者有相同的合著者。而圖4（b）構(gòu)建了元圖，它描述了兩位作者在同一地點發(fā)表論文或共享同一合著者時的相關(guān)性，元圖g可以被視為元路徑P1和P2的并集，在生成隨機游動序列時，它可以提供由P1和P2生成的隨機游走的超集。

圖4 模式、元路徑和元圖Fig.4 Schema，metapath and metagraph

該模型使用元圖的方式，生成節(jié)點之間的多條路徑，每條路徑描述一種類型的關(guān)系，因此多條元路徑的擴充提供有效的方法來捕獲節(jié)點之間豐富的上下文和語義關(guān)系。這大大增強了基于元路徑的嵌入技術(shù)處理非常稀疏異構(gòu)信息網(wǎng)絡(luò)的能力。

2.1.8 小結(jié)

同構(gòu)網(wǎng)絡(luò)中隨機游走模型通過采用不同的隨機游走策略，生成多樣化的節(jié)點序列，可以反應(yīng)更豐富的圖結(jié)構(gòu)信息。依此思路，2019 年，Schloetterer 等[27]提出了一種基于隨機游走圖嵌入的新擴展HALK（hierarchical random walk），從不同層次游動中移除一定百分比的最不頻繁節(jié)點，實現(xiàn)更遠節(jié)點之間的鏈接，反應(yīng)更多的圖結(jié)構(gòu)信息。2021 年，Zhou 等[28]引入帶重啟的有偏隨機游走的方法，提出了GEBRWR 模型來獲得高精度的鏈路預(yù)測；Wu等[29]提出了ProbWalk算法，利用邊緣權(quán)重確定轉(zhuǎn)移概率，并根據(jù)轉(zhuǎn)移概率生成用于圖嵌入的隨機游走序列。這一系列的方法，均取得了不錯的實驗效果。

而異構(gòu)網(wǎng)絡(luò)中隨機游走模型更關(guān)注游走路徑的選擇，通過構(gòu)建元路徑或元圖的方式來描述不同類型節(jié)點的特征和節(jié)點之間的關(guān)系，生成的節(jié)點序列可以更好的捕獲結(jié)構(gòu)、上下文和語義信息。從元路徑的角度考慮，Shao 等[30]提出H2Rec（homogeneous and heterogeneous network embedding fusion for social recommendation）模型融合同質(zhì)和異質(zhì)信息，在同質(zhì)信息網(wǎng)絡(luò)使用隨機游走策略中生成節(jié)點序列，在異質(zhì)信息網(wǎng)絡(luò)中利用元路徑來引導(dǎo)隨機游走方法生成節(jié)點序列。從構(gòu)建元圖的角度出發(fā)，文獻[31]提出MIFHNE 模型，基于多源信息融合的異構(gòu)網(wǎng)絡(luò)，使用基于元圖的隨機游走策略捕獲語義信息；文獻[32]提出了復(fù)合元圖（composite meta-graph，CMG），根據(jù)CMG 可以準(zhǔn)確地闡述不同類型和不同距離的節(jié)點之間豐富的語義關(guān)系和豐富的結(jié)構(gòu)上下文，然后提出了CMG2Vec（composite meta-graph based heterogeneous information network embedding approach）模型。這兩種角度的考慮，均在異構(gòu)網(wǎng)絡(luò)的圖嵌入中表現(xiàn)出了優(yōu)良的性能。依據(jù)上面的模型介紹，如表1從類別、模型、年份、模型策略、優(yōu)缺點和應(yīng)用場景多個方面進行了總結(jié)。

表1 經(jīng)典隨機游走模型對比Table 1 Comparison of classical random walk models

2.2 屬性游走模型

經(jīng)典的隨機游走模型被廣泛的應(yīng)用在圖分析的各種任務(wù)中，利用這些經(jīng)典的模型生成節(jié)點的結(jié)構(gòu)化序列，不僅可以捕獲圖的拓撲結(jié)構(gòu)，且緩解了知識表示面臨的稀疏性和維度災(zāi)難問題[33]。大量的事實表明，現(xiàn)實世界的網(wǎng)絡(luò)中包含著豐富的信息，而不只是包含純節(jié)點?；趯傩杂巫叩哪Ｐ蛧L試把這些復(fù)雜信息抽象成屬性，但是屬性網(wǎng)絡(luò)大多是異構(gòu)的，且考慮屬性會使節(jié)點交互變得更加復(fù)雜，增加模型建立的難度。為了解決這一問題，許多學(xué)者嘗試在屬性網(wǎng)絡(luò)上執(zhí)行隨機游走，并利用它們進行網(wǎng)絡(luò)節(jié)點的表示學(xué)習(xí)。

2.2.1 TriDNR模型

信息網(wǎng)絡(luò)挖掘通常需要檢查節(jié)點之間的鏈接關(guān)系以進行分析，基于傳統(tǒng)隨機游走的方法只關(guān)注節(jié)點本身，而忽略了節(jié)點的信息，但是大多數(shù)現(xiàn)實的網(wǎng)絡(luò)蘊含著大量的信息。面對這種問題，2016年，Pan等[34]提出了一種三方深度網(wǎng)絡(luò)表示模型：TriDNR模型，它使用來自三方的信息：節(jié)點結(jié)構(gòu)、節(jié)點內(nèi)容和節(jié)點標(biāo)簽，來共同學(xué)習(xí)最佳的節(jié)點表示。TriDNR 模型主要包含兩個步驟：（1）隨機游走序列生成，使用網(wǎng)絡(luò)結(jié)構(gòu)作為輸入，并在節(jié)點上隨機生成一組游動；（2）耦合神經(jīng)網(wǎng)絡(luò)模型學(xué)習(xí)，通過考慮以下信息將每個節(jié)點嵌入到連續(xù)空間中：隨機游走語料庫、節(jié)點內(nèi)容相關(guān)性和標(biāo)簽信息。此時TriDNR模型的目標(biāo)函數(shù)：

式中，α是平衡網(wǎng)絡(luò)結(jié)構(gòu)、內(nèi)容和標(biāo)簽信息的權(quán)重，b是序列的窗口大小，wj表示上下文窗口的第j個單詞。

如圖5所示，DeepWalk方法僅基于網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)網(wǎng)絡(luò)表示，而TriDNR 方法耦合兩個神經(jīng)網(wǎng)絡(luò)，從三方面（即節(jié)點結(jié)構(gòu)、節(jié)點內(nèi)容和節(jié)點標(biāo)簽）學(xué)習(xí)表示，以捕獲節(jié)點間、節(jié)點詞和標(biāo)簽詞關(guān)系。耦合神經(jīng)網(wǎng)絡(luò)模型架構(gòu)如圖5右邊框架所示，具有以下特性。

圖5 DeepWalk模型和TriDNR模型的框架Fig.5 Architecture of DeepWalk model and TriDNR model

（1）節(jié)點間關(guān)系建模：TriDNR的上層可以從隨機游走序列中學(xué)習(xí)結(jié)構(gòu)關(guān)系。

（2）節(jié)點內(nèi)容相關(guān)性評估：TriDNR的下層對文檔中單詞的上下文信息（節(jié)點內(nèi)容關(guān)聯(lián)）進行建模。

（3）連接：通過模型中的節(jié)點v1耦合這兩層，表明v1同時受隨機游走序列和節(jié)點內(nèi)容信息的影響。

（4）標(biāo)簽內(nèi)容對應(yīng)建模：為了利用每個節(jié)點有價值的類標(biāo)簽信息，同時學(xué)習(xí)輸入標(biāo)簽向量和輸出單詞向量，用于節(jié)點標(biāo)簽和節(jié)點內(nèi)容之間的直接建模。

2.2.2 Role2Vec模型

圖嵌入中，使用傳統(tǒng)的隨機游走主要捕獲頂點之間的接近度[35]，從而使圖中彼此接近的頂點嵌入在一起，也就是說隨機游走可能首先訪問附近的頂點，這使得它們適合于尋找社區(qū)，而不是角色（結(jié)構(gòu)相似性）。2019年，Ahmed 等[36]提出了Role2Vec 模型，利用屬性隨機游走的靈活概念來解決此問題，并作為推廣現(xiàn)有方法的基礎(chǔ)，如DeepWalk、Node2Vec和許多其他利用隨機游走的方法，該框架使這些方法能夠更廣泛地適用于轉(zhuǎn)換學(xué)習(xí)和歸納學(xué)習(xí)，且可用于屬性圖。Role2Vec模型認(rèn)為兩個頂點在屬性或結(jié)構(gòu)特征方面相似，則它們屬于同一集合，而頂點屬性和結(jié)構(gòu)特征可以通過根據(jù)其端點的類型區(qū)分來表示，這引出了屬性隨機游走的概念，因此屬性游走是相鄰頂點類型的序列，該定義誘導(dǎo)頂點類型序列稱為屬性隨機游動，也是一個馬爾可夫鏈。因此，Role2Vec模型的目標(biāo)函數(shù)：

Role2vec 框架使用頂點映射和屬性隨機游走來學(xué)習(xí)嵌入。因此，本模型的目標(biāo)是對每個頂點類型與其上下文類型相關(guān)的條件概率進行建模，嵌入結(jié)構(gòu)（即嵌入和上下文向量）在具有相同頂點類型的頂點之間共享。要注意：Role2vec 模型學(xué)習(xí)聚合網(wǎng)絡(luò)的嵌入，是把單個頂點之間的詳細關(guān)系聚合為頂點類型之間的總關(guān)系。

2.2.3 GraphRNA模型

在現(xiàn)實系統(tǒng)中，節(jié)點不會是純頂點，還具有不同的特征，這些特征由豐富數(shù)據(jù)集來描述。這些節(jié)點屬性包含豐富的信息，這些信息通常補充了網(wǎng)絡(luò)，并為基于隨機游走的分析帶來了機會。然而，目前尚不清楚如何為屬性網(wǎng)絡(luò)開發(fā)隨機游動，以實現(xiàn)有效的聯(lián)合信息提取，并且節(jié)點的屬性信息使網(wǎng)絡(luò)的結(jié)構(gòu)變得更加復(fù)雜。為了彌補這一差距，2019 年，Huang 等[33]提出了GraphRNA 模型，該框架是一種新的基于屬性的網(wǎng)絡(luò)嵌入框架，將協(xié)作游走機制AttriWalk 與圖遞歸網(wǎng)絡(luò)GRN 結(jié)合，在屬性網(wǎng)絡(luò)上更有效地學(xué)習(xí)節(jié)點的表示。GraphRNA可以在無監(jiān)督、有監(jiān)督或半監(jiān)督的環(huán)境下進行訓(xùn)練，這個屬性是從GCN[38-39]繼承的。GraphRNA 模型可大致分成三部分：（1）統(tǒng)一的游走機制，為了實現(xiàn)對復(fù)雜的屬性節(jié)點采樣的目的，構(gòu)建基于節(jié)點屬性的二部圖，幫助生成多樣化的節(jié)點序列；（2）圖遞歸網(wǎng)絡(luò)（GRN），一種有效幫助節(jié)點表示的深層結(jié)構(gòu)，生成的隱藏狀態(tài)序列符合采樣節(jié)點之間的交互關(guān)系；（3）生成節(jié)點嵌入，選取部分以某節(jié)點為起始節(jié)點的序列，構(gòu)建集合，然后利用池化方法來生成節(jié)點的嵌入向量。該文以有監(jiān)督的環(huán)境為例，基于交叉熵誤差，目標(biāo)函數(shù)可定義如下：

式中，yi是定義了節(jié)點i標(biāo)簽的one-hot 向量，wh是一個權(quán)重網(wǎng)絡(luò)，其每一行wj對應(yīng)于節(jié)點屬性類別的潛在表示，hi是利用屬性隨機游走生成的節(jié)點序列再經(jīng)過GRN后生成的節(jié)點i的表示向量。

該模型解決向高度節(jié)點收斂的方式是構(gòu)建節(jié)點屬性的二部網(wǎng)絡(luò)，增加隨機游走多樣性，設(shè)置一個概率參數(shù)來決定隨機游走的采樣策略：在二部圖網(wǎng)絡(luò)上走兩步，或在局部拓撲網(wǎng)絡(luò)上走一步，最后生成節(jié)點序列來反應(yīng)節(jié)點之間的復(fù)雜的屬性交互。在二部圖g(υ,μ,ε)的游走增加了屬性游走的多樣性和靈活性。

2.2.4 FEATHER模型

現(xiàn)實網(wǎng)絡(luò)中鄰域特征的解釋可能很復(fù)雜，網(wǎng)絡(luò)中包含多個屬性，具有影響節(jié)點和網(wǎng)絡(luò)特性的各種分布。因此，簡單線性聚合，如平均值，并不代表這種多樣性信息。針對這種情況，2020 年，Rozemberczki 等[40]提出了FEATHER 模型，使用了一個靈活定義在圖頂點上的特征函數(shù)的概念來描述頂點特征在多尺度上的分布，這是一種計算效率很高的算法，其中特征函數(shù)的概率權(quán)重定義為隨機游動的轉(zhuǎn)移概率。FEATHER 模型的損失函數(shù)為：

該損失通過梯度下降的方式，搜索β∈R(2?k?d?r)?C（分別有β0和β1）和Θ? 的最優(yōu)值。其中Y=softmax(Z?β)，C是節(jié)點類的數(shù)量，Z是利用評估點向量Θ? ，歸一化鄰接矩陣和節(jié)點特征作為輸入的圖神經(jīng)網(wǎng)絡(luò)的前向傳遞；Y?=softmax(σ(Z?β0)?β1)，這里β0∈R(2?k?d?r)?h是訓(xùn)練的輸入權(quán)重矩陣，β1∈Rh?C輸出權(quán)重矩陣，h是隱藏層神經(jīng)元個數(shù)。FEATHER 模型的核心是特征函數(shù)的概念，一個有屬性的無向圖G=(V,E)，G的節(jié)點具有隨機變量X描述的特征。源節(jié)點u在特征函數(shù)求值點θ∈R處的特征函數(shù)定義如下（其中i表示虛單位）：

其中，從屬概率p(w|u)描述源節(jié)點u和目標(biāo)節(jié)點w∈V之間關(guān)系的強度，源節(jié)點u和目標(biāo)節(jié)點w不必直接連接。

FEATHER模型可以在線性時間內(nèi)高效地計算大型屬性圖上的特征函數(shù)，創(chuàng)建節(jié)點的歐氏向量空間表示。FEATHER 模型對數(shù)據(jù)損壞具有魯棒性，并且同構(gòu)圖具有相同的向量空間表示，能高效、穩(wěn)健地將知識從一個圖轉(zhuǎn)移到另一個圖。

2.2.5 小結(jié)

基于屬性游走的模型不僅關(guān)注網(wǎng)絡(luò)中的節(jié)點和拓撲結(jié)構(gòu)，還關(guān)注節(jié)點本身多樣化的信息。隨機游走的過程中，把網(wǎng)絡(luò)中的信息抽象成屬性，生成帶有屬性的節(jié)點序列；圖嵌入向量生成的過程中，使用屬性節(jié)點序列更有利于網(wǎng)絡(luò)的表示。大量事實表明捕獲多尺度上的屬性鄰域關(guān)系對于一系列應(yīng)用非常有用，MUSAE 模型[41]從節(jié)點周圍的節(jié)點屬性的局部分布中捕獲節(jié)點的信息，融合了屬性化和鄰近保持算法的優(yōu)點?，F(xiàn)有的屬性網(wǎng)絡(luò)嵌入模型利用淺層網(wǎng)絡(luò)來獲取網(wǎng)絡(luò)的特征信息，但卻無法捕獲屬性網(wǎng)絡(luò)中非線性的深層特征，這樣必然會導(dǎo)致結(jié)果陷入局部最優(yōu)解。針對這種情況，Hong等[42]提出一種深度屬性網(wǎng)絡(luò)嵌入框架，采用個性化隨機游走的模型來捕獲網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點屬性之間的相互作用，來捕獲網(wǎng)絡(luò)中的復(fù)雜結(jié)構(gòu)和屬性信息。研究人同的工作，均證明基于屬性游走的圖嵌入模型有著旺盛的生命力。依據(jù)上面的介紹，表2 從模型、年份、模型策略、優(yōu)缺點和應(yīng)用場景多個方面進行總結(jié)。

表2 屬性游走模型對比Table 2 Comparison of attribute walk models

2.3 方法小結(jié)

本章主要介紹兩大類基于隨機游走的圖嵌入模型?；诮?jīng)典隨機游走的模型又分為兩小類：同構(gòu)網(wǎng)絡(luò)模型和異構(gòu)網(wǎng)絡(luò)模型，同構(gòu)網(wǎng)絡(luò)節(jié)點或邊的類型只有一種，而異構(gòu)網(wǎng)絡(luò)會有多種類型的節(jié)點和邊，因此異構(gòu)網(wǎng)絡(luò)的模型更加復(fù)雜一點；后面介紹基于屬性游走的圖嵌入模型更加復(fù)雜，因為網(wǎng)絡(luò)屬性包含多個維度的屬性信息?？傮w來看，同構(gòu)網(wǎng)絡(luò)模型更關(guān)注隨機游走的策略，異構(gòu)網(wǎng)絡(luò)模型更關(guān)注游走路徑的構(gòu)建，而最后的屬性游走模型在前面工作的基礎(chǔ)上，還關(guān)注節(jié)點本身多樣化的信息。依據(jù)已有的成果對各種方法進行分析，表3從類別、機制、解決問題、優(yōu)勢、局限性和適用場景多個方面，對基于隨機游走的圖嵌入模型進行總的特征分析。

表3 基于隨機游走的圖嵌入模型對比Table 3 Comparison of graph embedding models based on random walk

3 圖嵌入算法實驗對比分析

基于隨機游走的圖嵌入研究具有多種不同的類型，對于不同類型的圖嵌入應(yīng)用需要選擇不同的數(shù)據(jù)集和評價指標(biāo)。本實驗主要利用同構(gòu)網(wǎng)絡(luò)數(shù)據(jù)集，進行實驗的對比與分析。

3.1 數(shù)據(jù)集

本實驗使用的數(shù)據(jù)集有：Karate[43]、Football[44]、Dolphins[45]、Hep-th[46]、Astro-ph[47]、Cond-mat-2005[48]，表4對這些數(shù)據(jù)集的特點和特征，進行相關(guān)的總結(jié)。

表4 實驗數(shù)據(jù)集Table 4 Experimental datasets

3.2 實驗分析

3.2.1 網(wǎng)絡(luò)重構(gòu)

網(wǎng)絡(luò)重構(gòu)任務(wù)是利用學(xué)習(xí)到的低維嵌入來重構(gòu)圖的邊和拓撲結(jié)構(gòu)，用于評估嵌入向量的質(zhì)量。嵌入作為圖的低維表示，可以幫助重建圖。對于每種方法生成的圖嵌入向量，重建節(jié)點之間的鏈接，然后使用前k對頂點的預(yù)測鏈接所占原始圖中鏈接的比例來評估模型的重構(gòu)表現(xiàn)。網(wǎng)絡(luò)重構(gòu)任務(wù)通常采用MAP（mean average precision）[49]作為評價指標(biāo)：

網(wǎng)絡(luò)重構(gòu)幫助理解圖嵌入的性能，好的網(wǎng)絡(luò)嵌入會有優(yōu)良的性能指標(biāo)的體現(xiàn)。在Karate、Football、Dolphins、Hep-th、Astro-ph和Cond-mat-2005數(shù)據(jù)集上，做了Deep-Walk、Node2Vec、WalkLets 和Role2Vec 這4 種模型的不同維度嵌入向量指標(biāo)對比。從圖6（d代表嵌入向量空間維度大小）的實驗結(jié)果來看，總體上4 種模型都隨著嵌入向量維度的增加有更好的指標(biāo)體現(xiàn)，前3種數(shù)據(jù)集從規(guī)模來看，相對規(guī)模比較小，隨著維度的增加，性能指標(biāo)相對處于平滑狀態(tài)，而另外3 種數(shù)據(jù)集的規(guī)模比較大，隨著維度的增加，性能指標(biāo)也相應(yīng)遞增，可見更高的維度有助于保存更多的網(wǎng)絡(luò)信息；從圖中也可以看出DeepWalk、Node2Vec 和WalkLets 這3 種模型的性能體現(xiàn)優(yōu)于Role2Vec模型，而Role2Vec模型在這6種數(shù)據(jù)集上表現(xiàn)性能比較差且不穩(wěn)定，原因是網(wǎng)絡(luò)重構(gòu)更關(guān)注的是網(wǎng)絡(luò)鄰近節(jié)點的鏈接，也就是社區(qū)結(jié)構(gòu)，前3 種模型關(guān)注網(wǎng)絡(luò)的鄰近節(jié)點，即關(guān)注節(jié)點的一階相似性，而Role2Vec模型不只關(guān)注網(wǎng)絡(luò)中節(jié)點的屬性，更關(guān)注網(wǎng)絡(luò)中節(jié)點的結(jié)構(gòu)相似性，因此對于節(jié)點之間的鄰近鏈接的表征就不夠好。

圖6 網(wǎng)絡(luò)重構(gòu)性能對比Fig.6 Comparison of network reconstruction performance

3.2.2 可視化

可視化任務(wù)是對生成的嵌入向量在二維空間展示，便于直觀地觀察原始圖的特點和拓撲結(jié)構(gòu)。如果可視化的數(shù)據(jù)集是有標(biāo)簽的，一個好的嵌入可以使標(biāo)簽相同的節(jié)點彼此接近，不同的標(biāo)簽節(jié)點彼此遠離。在Karate 數(shù)據(jù)集上做DeepWalk、Node2Vec、WalkLets和Role2Vec 模型的可視化對比，如圖7 所示，學(xué)習(xí)4 種模型的128 維的嵌入向量，并將其輸入到t-SNE[50]以將維度減少到2，然后在二維空間中可視化節(jié)點。利用網(wǎng)絡(luò)中節(jié)點的標(biāo)簽和社區(qū)結(jié)構(gòu)，可以直觀地看出4 種模型都能較好地保留原始圖的結(jié)構(gòu)，相對來說，前3 種模型可以有效地捕捉節(jié)點的社區(qū)結(jié)構(gòu)，使同類型的節(jié)點更近；而Role2Vec 模型未能充分地利用節(jié)點的特征和標(biāo)簽信息，導(dǎo)致模型的性能較差，同類型的節(jié)點分布零散。

圖7 可視化性能對比Fig.7 Comparison of visualization performance

4 研究展望

本文主要介紹基于隨機游走的圖嵌入方法和應(yīng)用，比較了各種模型之間的差異，對基于隨機游走圖嵌入的方法進行了比較全面的闡述。圖上機器學(xué)習(xí)的表示學(xué)習(xí)方法為傳統(tǒng)特征工程提供了一種強有力的替代方法，基于隨機游走的圖嵌入用于圖數(shù)據(jù)的表示，可以用于不同的任務(wù)，這些任務(wù)可以大致分為：網(wǎng)絡(luò)重構(gòu)[51-52]、節(jié)點分類[53-54]、圖聚類[55-56]、異常點檢測[57]、鏈接預(yù)測[58]和可視化[59]。雖然基于隨機游走的圖嵌入實現(xiàn)了數(shù)據(jù)的降維和表示，在解決圖數(shù)據(jù)稀疏問題、計算效率低和圖數(shù)據(jù)理解等方面表現(xiàn)優(yōu)異，但是基于隨機游走的圖嵌入也面臨著一些亟待解決的問題。

（1）屬性選擇：實際應(yīng)用場景下圖數(shù)據(jù)不僅僅包含單純的節(jié)點，還含有復(fù)雜的屬性和拓撲結(jié)構(gòu)。圖嵌入向量不僅需要保留圖的節(jié)點，還要能夠保留圖的屬性。因此，需要考慮選擇合適的距離度量和屬性，保證嵌入向量的性能。

（2）可擴展性：現(xiàn)實的世界中存在著復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，因為網(wǎng)絡(luò)的千差萬別，需要尋找一種普適性的辦法，保留網(wǎng)絡(luò)的全局屬性。因此，考慮嵌入方法的可擴展性也是一個亟待解決的問題。

（3）嵌入維數(shù)：真實的場景下節(jié)點數(shù)量和鏈接千差萬別，因此針對不同的數(shù)據(jù)集選取不同的嵌入維度反應(yīng)網(wǎng)絡(luò)的特征，是一件很有技巧的事情。若是一味地使用高的維度，會導(dǎo)致較高的時間和空間復(fù)雜度。

（4）可解釋性：表征學(xué)習(xí)之所以有吸引力，是因為它減輕了手工設(shè)計特性的負擔(dān)，但它也以眾所周知的可解釋性為代價?；谇度氲姆椒ㄌ峁┝俗钕冗M的性能，但是這些算法的基本限制以及可能的潛在偏差相對未知。為了向前發(fā)展，必須注意開發(fā)新的技術(shù)來提高所學(xué)表示的可解釋性。

隨著大數(shù)據(jù)技術(shù)的發(fā)展，呈現(xiàn)出海量、高維、稀疏、動態(tài)和異構(gòu)等復(fù)雜特征的圖數(shù)據(jù)或圖結(jié)構(gòu)，給圖數(shù)據(jù)的分析和挖掘帶來了巨大的挑戰(zhàn)。基于隨機游走的圖嵌入模型雖然在各種任務(wù)中表現(xiàn)出不錯的性能，但是它也面臨著一些挑戰(zhàn)，如：節(jié)點海量性、屬性信息融合、圖的異構(gòu)性、節(jié)點的動態(tài)變化性和模型的非線性。圖上機器學(xué)習(xí)的表示學(xué)習(xí)方法為傳統(tǒng)特征工程提供了一種強有力的替代方法，然而，在改進這些方法的性能方面，更重要的是建立一致的理論框架，為后面的研究提供可參考的標(biāo)準(zhǔn)?？傮w來說，接下來的研究方向分為以下幾類：

（1）面向超大規(guī)模網(wǎng)絡(luò)的嵌入模型。雖然基于隨機游走的模型可以較好地反應(yīng)大型圖的網(wǎng)絡(luò)信息，但生成嵌入向量的代價較高。隨著社交媒體和電商的發(fā)展，網(wǎng)絡(luò)中節(jié)點和邊的數(shù)量級一定會越來越大，在這種背景下，提高嵌入模型的性能和降低網(wǎng)絡(luò)生成的代價是生成超大規(guī)模圖嵌入向量亟待解決的問題。

（2）面向復(fù)雜網(wǎng)絡(luò)的嵌入模型。復(fù)雜網(wǎng)絡(luò)不只是同構(gòu)網(wǎng)絡(luò)，它還可能是異構(gòu)網(wǎng)絡(luò)，且網(wǎng)絡(luò)中包含有復(fù)雜的屬性信息。針對不同類型的復(fù)雜網(wǎng)絡(luò)，設(shè)計不同的策略來反應(yīng)網(wǎng)絡(luò)中復(fù)雜的信息和拓撲結(jié)構(gòu)，也是很有前景的一個研究方向。

（3）面向動態(tài)網(wǎng)絡(luò)的嵌入模型。大部分場景下圖是動態(tài)演化的，這個演化過程包含著復(fù)雜的信息。隨機游走的方法不斷迭代的過程可以反應(yīng)圖動態(tài)演化過程中的微小變化，設(shè)計合適的游走策略在降低時間復(fù)雜度的同時，還保留動態(tài)圖的演化信息，是動態(tài)圖嵌入必須要考慮的內(nèi)容。

（4）面向特定場景的嵌入模型。許多嵌入模型用于可視化、節(jié)點分類、鏈接預(yù)測和異常點檢測等任務(wù)中都取得了不錯的實驗效果。但是真實的場景（推薦、反作弊等）提供了豐富的大規(guī)模的多樣化的數(shù)據(jù)，不再只是對單一任務(wù)的要求，需要考慮不同類型的任務(wù)的結(jié)合，因此，研究特定場景下的圖表征學(xué)習(xí)也是一個熱門的研究方向。

5 結(jié)語

圖表示學(xué)習(xí)（圖嵌入）是人工智能研究的熱點之一，隨著圖嵌入方法的不斷發(fā)展，該研究吸引到了大量研究人員的關(guān)注。本文在介紹完背景知識后，重點介紹了基于隨機游走的圖嵌入方法，將該類型方法分為基于經(jīng)典隨機游走的模型和基于屬性游走的模型，進行了深入的對比分析，并做了展望。