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

1.新疆大學 軟件學院，烏魯木齊 830046

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

3.北京理工大學 計算機學院，北京 100081

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

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

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

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

1 符號與基本定義

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

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

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

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

定義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機游走的圖嵌入模型有著不俗的表現，特別是當圖規(guī)模十分巨大時，隨機游走方法可以很好地保留圖的結構特性，生成可以近似反應節(jié)點屬性的嵌入向量?，F有的基于隨機游走的圖嵌入模型主要分為兩大類：基于經典隨機游走的模型和基于屬性游走的模型。

2.1 經典隨機游走模型

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

2.1.1 DeepWalk模型

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

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

圖2 DeepWalk模型結構Fig.2 Model framework of DeepWalk

2.1.2 Node2Vec模型

Node2Vec 模型[19]是在DeepWalk 模型的基礎上，引進了一個有偏的隨機游走的過程，在同質性和結構性[20]之間進行權衡，可以探索不同的鄰域，最終保證生成的嵌入向量質量更高。Node2Vec模型的目標函數為：

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

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

圖3 Node2Vec模型轉移策略Fig.3 Transfer strategy of Node2Vec model

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

2.1.3 WalkLets模型

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

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

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

2.1.4 HARP模型

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

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

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

2.1.5 metapath2vec和metapath2vec++模型

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

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

因此，metapath2vec++模型進一步支持異構網絡中結構和語義關聯的同時建模。

2.1.6 HIN2Vec模型

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

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

2.1.7 MetaGraph2Vec模型

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

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

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

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

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

2.1.8 小結

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

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

表1 經典隨機游走模型對比Table 1 Comparison of classical random walk models

2.2 屬性游走模型

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

2.2.1 TriDNR模型

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

式中，α是平衡網絡結構、內容和標簽信息的權重，b是序列的窗口大小，wj表示上下文窗口的第j個單詞。

如圖5所示，DeepWalk方法僅基于網絡結構學習網絡表示，而TriDNR 方法耦合兩個神經網絡，從三方面（即節(jié)點結構、節(jié)點內容和節(jié)點標簽）學習表示，以捕獲節(jié)點間、節(jié)點詞和標簽詞關系。耦合神經網絡模型架構如圖5右邊框架所示，具有以下特性。

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

（1）節(jié)點間關系建模：TriDNR的上層可以從隨機游走序列中學習結構關系。

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

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

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

2.2.2 Role2Vec模型

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

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

2.2.3 GraphRNA模型

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

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

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

2.2.4 FEATHER模型

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

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

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

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

2.2.5 小結

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

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

2.3 方法小結

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

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

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

基于隨機游走的圖嵌入研究具有多種不同的類型，對于不同類型的圖嵌入應用需要選擇不同的數據集和評價指標。本實驗主要利用同構網絡數據集，進行實驗的對比與分析。

3.1 數據集

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

表4 實驗數據集Table 4 Experimental datasets

3.2 實驗分析

3.2.1 網絡重構

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

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

圖6 網絡重構性能對比Fig.6 Comparison of network reconstruction performance

3.2.2 可視化

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

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

4 研究展望

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

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

（2）可擴展性：現實的世界中存在著復雜的網絡結構，因為網絡的千差萬別，需要尋找一種普適性的辦法，保留網絡的全局屬性。因此，考慮嵌入方法的可擴展性也是一個亟待解決的問題。

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

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

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

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

（2）面向復雜網絡的嵌入模型。復雜網絡不只是同構網絡，它還可能是異構網絡，且網絡中包含有復雜的屬性信息。針對不同類型的復雜網絡，設計不同的策略來反應網絡中復雜的信息和拓撲結構，也是很有前景的一個研究方向。

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

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

5 結語

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