基于隨機(jī)游走的圖嵌入研究綜述

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

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

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

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

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

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

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

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

1 符號(hào)與基本定義

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

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

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

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

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

2 隨機(jī)游走的圖嵌入模型分類

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

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

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

2.1.1 DeepWalk模型

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

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

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

2.1.2 Node2Vec模型

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

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

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

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

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

2.1.3 WalkLets模型

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

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

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

2.1.4 HARP模型

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

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

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

2.1.5 metapath2vec和metapath2vec++模型

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

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

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

2.1.6 HIN2Vec模型

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

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

2.1.7 MetaGraph2Vec模型

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

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

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

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

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

2.1.8 小結(jié)

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

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

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

2.2 屬性游走模型

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

2.2.1 TriDNR模型

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

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

如圖5所示，DeepWalk方法僅基于網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)網(wǎng)絡(luò)表示，而TriDNR 方法耦合兩個(gè)神經(jīng)網(wǎng)絡(luò)，從三方面（即節(jié)點(diǎn)結(jié)構(gòu)、節(jié)點(diǎn)內(nèi)容和節(jié)點(diǎn)標(biāo)簽）學(xué)習(xí)表示，以捕獲節(jié)點(diǎn)間、節(jié)點(diǎn)詞和標(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é)點(diǎn)間關(guān)系建模：TriDNR的上層可以從隨機(jī)游走序列中學(xué)習(xí)結(jié)構(gòu)關(guān)系。

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

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

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

2.2.2 Role2Vec模型

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

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

2.2.3 GraphRNA模型

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

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

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

2.2.4 FEATHER模型

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

該損失通過梯度下降的方式，搜索β∈R(2?k?d?r)?C（分別有β0和β1）和Θ? 的最優(yōu)值。其中Y=softmax(Z?β)，C是節(jié)點(diǎn)類的數(shù)量，Z是利用評(píng)估點(diǎn)向量Θ? ，歸一化鄰接矩陣和節(jié)點(diǎn)特征作為輸入的圖神經(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)元個(gè)數(shù)。FEATHER 模型的核心是特征函數(shù)的概念，一個(gè)有屬性的無向圖G=(V,E)，G的節(jié)點(diǎn)具有隨機(jī)變量X描述的特征。源節(jié)點(diǎn)u在特征函數(shù)求值點(diǎn)θ∈R處的特征函數(shù)定義如下（其中i表示虛單位）：

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

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

2.2.5 小結(jié)

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

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

2.3 方法小結(jié)

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

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

3 圖嵌入算法實(shí)驗(yàn)對(duì)比分析

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

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

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

表4 實(shí)驗(yàn)數(shù)據(jù)集Table 4 Experimental datasets

3.2 實(shí)驗(yàn)分析

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

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

網(wǎng)絡(luò)重構(gòu)幫助理解圖嵌入的性能，好的網(wǎng)絡(luò)嵌入會(huì)有優(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)對(duì)比。從圖6（d代表嵌入向量空間維度大小）的實(shí)驗(yàn)結(jié)果來看，總體上4 種模型都隨著嵌入向量維度的增加有更好的指標(biāo)體現(xiàn)，前3種數(shù)據(jù)集從規(guī)模來看，相對(duì)規(guī)模比較小，隨著維度的增加，性能指標(biāo)相對(duì)處于平滑狀態(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é)點(diǎn)的鏈接，也就是社區(qū)結(jié)構(gòu)，前3 種模型關(guān)注網(wǎng)絡(luò)的鄰近節(jié)點(diǎn)，即關(guān)注節(jié)點(diǎn)的一階相似性，而Role2Vec模型不只關(guān)注網(wǎng)絡(luò)中節(jié)點(diǎn)的屬性，更關(guān)注網(wǎng)絡(luò)中節(jié)點(diǎn)的結(jié)構(gòu)相似性，因此對(duì)于節(jié)點(diǎn)之間的鄰近鏈接的表征就不夠好。

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

3.2.2 可視化

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

圖7 可視化性能對(duì)比Fig.7 Comparison of visualization performance

4 研究展望

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

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

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

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

（4）可解釋性：表征學(xué)習(xí)之所以有吸引力，是因?yàn)樗鼫p輕了手工設(shè)計(jì)特性的負(fù)擔(dān)，但它也以眾所周知的可解釋性為代價(jià)。基于嵌入的方法提供了最先進(jìn)的性能，但是這些算法的基本限制以及可能的潛在偏差相對(duì)未知。為了向前發(fā)展，必須注意開發(fā)新的技術(shù)來提高所學(xué)表示的可解釋性。

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

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

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

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

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

5 結(jié)語

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