圖嵌入模型綜述

袁立寧，李 欣，王曉冬，劉 釗

1.中國人民公安大學 信息網絡安全學院，北京100038

2.天津市公安局河西分局 科技信息化支隊，天津300202

3.天津市公安局河東分局 科技信息化支隊，天津300171

4.中國人民公安大學 新型犯罪研究中心，北京100038

圖是復雜系統中常用的信息載體，可以表示現實中許多復雜關系，如社交網絡、犯罪網絡、交通網絡等。圖結構作為一種非歐幾里德數據，很難直接應用卷積神經網絡（convolutional neural network，CNN）和循環神經網絡（recurrent neural network，RNN）等深度學習方法。為了構造用于圖數據挖掘的特征表示，圖嵌入將節點映射到低維空間，生成保留原始圖中某些重要信息的低維向量。目前，圖嵌入不僅在節點分類、鏈接預測、節點聚類、可視化等復雜網絡上的機器學習任務中獲得成功，還廣泛用于社交影響力建模、內容推薦等現實任務。

早期的圖嵌入算法主要用于數據降維，通過鄰域關系構建相似度圖，將節點嵌入低維向量空間，并保持相連節點向量的相似性。這類方法通常時間復雜度高，很難擴展到大型圖上。近年來，圖嵌入算法轉向擴展性強的方法。例如，矩陣分解方法使用鄰接矩陣的近似分解作為嵌入；隨機游走法將游走序列輸入到Skip-Gram生成嵌入。這些方法利用圖的稀疏性降低了時間復雜度。當前，很多綜述對圖嵌入方法進行了歸納與總結，但存在兩大局限：一是部分綜述僅涉及傳統方法介紹，許多新模型沒有納入研究；二是這些綜述只關注靜態圖嵌入或動態圖嵌入，忽略了二者之間的關聯性。

本文對圖嵌入方法進行全面系統性綜述，有以下三方面的貢獻：（1）提出一種新的圖嵌入分類法，同時對靜態圖和動態圖方法進行分類；（2）對現有模型進行系統性分析，為理解現有方法提供新視角；（3）提出了四個圖嵌入的潛在研究方向。

1 圖嵌入相關定義及符號表示

1.1 問題定義

圖）圖通常表示為=(,)，其中表示節點集，表示邊集。

（靜態圖）給定圖=(,)，如果節點和邊的狀態不隨時間變化，圖為靜態圖。

（動態圖）動態圖可以按時間分成一系列演化圖G=(,,…,G，表示演化圖的數量。每個演化圖G=(V,E表示節點和邊在時刻的狀態。動態圖包含快照型和連續時間型（見圖1）?？煺招蛣討B圖按時間序列將動態圖分解為等間隔的靜態圖；連續時間型用多個時間戳標記每條邊來保留節點間的連接變化。

圖1 快照型和連續時間型動態圖Fig.1 Snapshot and continuous-time dynamic graphs

（一階相似度）一階相似度描述節點之間的成對鄰近度。如果節點v和v之間存在一條邊，v和v的一階相似度為邊權重w；如果在v和v之間沒有邊，一階相似度為0。

（二階相似度）二階相似度描述節點鄰域結構的相似度。假設w=[w,w,…,w]表示節點v與其他節點的一階相似度，那么v和v的二階相似度由w和w的相似程度決定。

（圖嵌入）圖嵌入將每個節點映射成低維向量表示（見圖2），同時保留了原始圖中某些關鍵信息。映射函數通常定義為:v→Y∈R，其中為嵌入向量的維度。

圖2 圖嵌入的一般過程Fig.2 General framework for graph embedding

1.2 符號表示

本文常用符號及其定義見表1。

表1 符號及定義Table 1 Symbols and definitions

2 圖嵌入分類

本章提出一種新的分類方法，用于現有圖嵌入模型的分類。按照模型所使用的算法原理將靜態圖和動態圖模型同時分為五大類：基于矩陣分解的圖嵌入、基于隨機游走的圖嵌入、基于自編碼器的圖嵌入、基于圖神經網絡（graph neural networks，GNN）的圖嵌入和基于其他方法的圖嵌入。圖3 為分類思路及內容體系構建，圖4 為圖嵌入模型的分類匯總。

圖3 圖嵌入內容體系Fig.3 Content system of graph embedding

圖4 圖嵌入模型分類匯總Fig.4 Categorization and summary of graph embedding models

2.1 基于矩陣分解的圖嵌入

基于矩陣分解的圖嵌入通過分解節點關系矩陣獲得低維嵌入。不同的關系矩陣采用的分解方法不同，例如鄰接矩陣通常使用奇異值分解（singular value decomposition，SVD）的方法生成節點嵌入，而屬性矩陣通常使用特征值分解的方法。

基于矩陣分解的靜態圖嵌入模型對節點關聯信息矩陣和屬性信息矩陣進行特征分解，然后將分解得到的屬性嵌入和結構嵌入進行融合，生成節點的低維嵌入表示。圖5 說明了矩陣分解和靜態圖嵌入生成的一般過程。

圖5 基于矩陣分解的靜態圖嵌入模型框架Fig.5 Framework of eigenvalue factorization in static graph embedding

局部線性映射（locally linear embedding，LLE）將每個節點表示為相鄰節點的線性組合，構造鄰域保持映射（見圖6）。具體實現分為三步：（1）以某種度量方式（如歐氏距離）選擇個鄰近節點；（2）由個近鄰線性加權重構節點，并最小化節點重建誤差獲得最優權重；（3）最小化最優權重構建的目標函數生成。目標函數的表達式為：

圖6 LLE 步驟Fig.6 Steps of LLE

式中，W為節點與節點的權重系數。作為一種重要的降維算法，LLE 在降維時能夠保持樣本的局部特征，并通過稀疏矩陣特征分解的方式適當降低了計算復雜度。但是，該模型對值的選擇十分敏感，對最終的降維結果有極大影響。

由上式特性可知，在節點數量較多、嵌入維度較大時，模型計算會產生極大的內存占用。為此，GF 設計了一種最小化簇外一階鄰居數量的圖分割算法，保證圖結構信息無損，提升模型計算效率。

GraRep分別構建1 到步的對數轉移概率矩陣{,,…,T}，將T中所有負值元素替換為0，使T為正步對數轉移概率矩陣，以減少噪聲。最后，使用SVD 分解T得到節點表示Y，并將{,,…,Y}進行合并，得到最終嵌入。GraRep 能夠在嵌入中整合全局結構信息，但訓練過程中涉及矩陣運算和SVD，計算復雜度極高，難以擴展到大規模圖數據。

非對稱傳遞性可以刻畫有向邊之間的關聯，有助于捕捉圖的結構。為了保留有向圖中的非對稱傳遞性，HOPE采用了一種保持高階相似度的嵌入方法，在保留非對稱傳遞性的向量空間中生成圖嵌入（見圖7），訓練中使用L2 范數進行優化：

圖7 HOPE 模型框架Fig.7 Framework of HOPE

式中，為源嵌入，為目標嵌入。許多相似性度量可以反映非對稱傳遞性，如Katz指標、Adamic-Adar分數等，用于構建相似度矩陣。此外，HOPE 使用廣義SVD（generalized singular value decomposition，GSVD）分解，適當降低了計算復雜度，但是低階GSVD 逼近能力有限，限制了模型表達能力。

在原始圖上，本征圖用于保留節點間有利關聯，懲罰圖用于保留節點間的不利關聯。為了綜合本征圖和懲罰圖的特點，NGE（non-negative graph embedding）引入非負矩陣分解（non-negative matrix factorization，NMF）生成嵌入表示。NMF 將數據矩陣分解成低階非負基矩陣和非負系數矩陣，并使用L1 損失作為目標函數。在此基礎上，NGE 將和分成兩部分：=[,]；=[,]。由于(,)和(,)是互補空間，可以通過疊加的方式重構原始數據，的目標函數可以由懲罰圖目標函數進行轉換。將NMF 的L1 損失和和目標函數相結合，可得NGE 的目標函數為：

拉普拉斯特征映射（Laplacian eigenmaps，LE）與LLE 相似，也是從局部近似的角度構建數據之間的關系。具體而言，LE 使用鄰接矩陣建立包含局部結構信息的嵌入表示，并要求相連節點在嵌入空間中盡可能地靠近。因此，LE 的目標函數為：

由上式可知，LE 的目標函數強調權值大的節點對，弱化權值小的節點對，導致原始圖中的局部拓撲結構被破壞。為了增強圖嵌入的局部拓撲保持性，柯西圖嵌入（Cauchy graph embedding，CGE）引入距離的反函數來保持節點在嵌入空間中的相似關系。因此，CGE 將LE 的目標函數改寫為：

相比LE，CGE 的目標函數更加強調短距離，即確保局部越鄰近的節點在嵌入空間的距離越接近。

從矩陣分解的角度看，圖的動態演化實質上是原始矩陣的不斷變化?；诰仃嚪纸獾膭討B圖方法利用特征分解構造圖的高階相似度矩陣，然后利用矩陣攝動理論更新圖的動態信息。矩陣攝動理論可以高效更新圖的高級特征對，同時避免了每個時刻的重新計算嵌入矩陣。圖8 是基于矩陣分解的動態圖嵌入的一般過程。

圖8 基于矩陣分解的動態圖嵌入模型框架Fig.8 Framework of matrix factorization in dynamic graph embedding

圖9 DANE 模型結構Fig.9 Framework of DANE

DHPE同樣采用分布式框架：靜態部分，DHPE與HOPE 相似，將GSVD 分解Katz相似度矩陣轉換為廣義特征值問題，使每個時刻生成的低維嵌入保留節點的高階相似度；動態部分，DHPE 使用矩陣攝動理論更新GSVD 的結果。此外，模型假設圖中節點數恒定（添加或刪除的節點為孤立節點），使每個時刻圖的變化轉化為邊的變化。DHPE 能夠在保持高階相似性的同時更新節點嵌入，其增量計算方案有效提升了動態模型的計算效率。

Chen 等人提出了TRIP 和TRIP-BASIC 兩種在線算法跟蹤動態圖的特征對，其核心思路是利用矩陣攝動理論對圖的特征對進行更新。TRIP 和TRIPBASIC 引入圖中三角形個數作為屬性信息構建特征函數，然后將特征對映射成屬性向量。上述模型能夠有效追蹤特征對、三角形個數和魯棒性分數隨時間的動態變化，但是模型的誤差會隨著時間推移不斷積累。

由于增量矩陣的更新采用近似值的方式，導致生成嵌入的過程中誤差不斷積累。為解決上述問題，TIMERS采用SVD 最大誤差界重啟算法，設置SVD 重新啟動時間，減少時間上的誤差積累。該模型的核心包含兩部分：（1）增量更新，通過函數近似地更新前一時刻的結果；（2）SVD 重啟，通過設置誤差閾值，確定執行SVD 重啟時刻，重新計算最優SVD結果，并最小化重啟次數。

MF通過構造攜帶重要特征的矩陣因子，使潛在的NMF 特征有效地表達動態信息。為了充分利用不同時刻的拓撲信息，MF 對嵌入空間的鄰接關系矩陣進行整合，找到在各個時刻一致的嵌入矩陣和系數矩陣，并通過最小化Frobenius 范數使各時刻Y和、W和差異最小。基于NMF 加權表示相似性指數的MF 比基于靜態表示相似性指數的方法具有更好的性能。

DWSF采用使用Semi-NMF和弱監督分解（weakly supervised factorization，WSF），將數據矩陣分解為標簽矩陣和嵌入矩陣（=，其中是非負的，和沒有約束），然后使用標簽傳播（label propagation）算法初始化標簽矩陣因子，將類標簽從有標簽的數據實例傳播到無標簽的數據實例，最后將控制信息量的平滑度項與Semi-NMF 相結合，優化模型參數生成嵌入。DWSF 將有限的監督信息合并為類別標簽，在每次迭代中動態更新，大幅提升了模型在分類任務上的表現。

2.2 基于隨機游走的圖嵌入

受word2vec的啟發，基于隨機游走的圖嵌入方法將節點轉化為詞，將隨機游走序列作為句子，利用Skip-Gram 生成節點的嵌入向量。隨機游走法可以保留圖的結構特性，并且在無法完整觀察的大型圖上仍有不錯的表現。

基于隨機游走的靜態圖嵌入模型通過隨機游走獲得訓練語料庫，然后將語料庫集成到Skip-Gram 獲得節點的低維嵌入表示。

Deepwalk使用隨機游走對節點進行采樣，生成節點序列，再通過Skip-Gram 最大化節點序列中窗口范圍內節點之間的共現概率，將節點v映射為嵌入向量Y（見圖10）：

圖10 Deepwalk 模型結構Fig.10 Framework of Deepwalk

生成的嵌入將節點之間的關系編碼在低維向量空間，用于捕捉鄰域相似性和社區結構，學習節點的潛在特征。Deepwalk 不僅在數據量較少時有較好的表現，還可以擴展到大型圖的表示學習。由于優化過程中未使用明確的目標函數，使得模型保持網絡結構的能力受到限制。

node2vec在Deepwalk 的基礎上，引入有偏的隨機游走（見圖11），增加鄰域搜索的靈活性，生成質量更高、信息更多的嵌入表示。通過設置和兩個參數，平衡廣度優先搜索（breadth-first sampling，BFS）和深度優先搜索（depth-first sampling，DFS）策略，使生成的嵌入能夠保持社區結構等價性或鄰域結構等價性。雖然node2vec 能夠保持更多的一階相似度和二階相似度信息，但仍然缺少明確的目標函數來保持全局網絡結構。

圖11 node2vec中的隨機游走過程Fig.11 Random walk procedure in node2vec

Deepwalk 和node2vec 采用隨機游走探索節點局部鄰域，使得學習到的低維表示無法保留圖的全局結構，同時使用隨機梯度下降求解非凸的目標函數，使生成的嵌入可能陷入局部最優解。為了解決上述問題，HARP將原始圖中的節點和邊遞歸地合并在一起，得到一系列結構相似的壓縮圖。這些壓縮圖有不同的粒度，提供了原始圖全局結構的視圖。從最粗略的形式開始，每個壓縮圖學習一組嵌入表示，并用于初始化下一個更細化的壓縮圖的嵌入。HARP能夠與Deepwalk 和node2vec結合使用，提升原始模型性能，生成信息更豐富的嵌入表示。

利用分層Softmax，Deepwalk 目標函數可以改寫為矩陣分解的形式：

式中，M是以節點為起點為終點的長度為的路徑期望值；e是one-hot 向量，其第個元素為1 其余元素為0，A的不同冪次代表了不同的尺度?？梢奃eepwalk 已經隱式地建模了從1 到階的多尺度依賴關系，但無法單獨訪問不同尺度。為了顯式地構建階關系，Walklets修改了Deepwalk 的采樣過程，在隨機游走序列上跳過-1 個頂點。除此之外，模型的優化和嵌入生成方式均與Deepwalk 相同。相較于Deepwalk，Walklets 能夠捕獲節點與社區之間不同尺度的層次結構，進而顯式建模多尺度關系，保留更豐富的節點從屬關系信息。

TriDNR是首個利用標簽信息進行表示學習的深層神經網絡模型，能夠同時利用網絡結構、節點特征和節點標簽學習節點嵌入表示（見圖12）。具體而言，TriDNR 使用兩個神經網絡來捕獲節點-節點、節點-單詞、標簽-單詞之間的關系。對于網絡結構，通過隨機游走序列最大化共現概率來保持圖中節點間的鄰近關系；對于節點特征，通過最大化給定節點的單詞序列的共現概率捕獲節點與單詞的相關性；對于節點標簽，通過最大化給定類別標簽的單詞序列的概率建模標簽與單詞的對應關系。最后，使用耦合神經網絡的算法將三部分信息合并為節點嵌入。

圖12 TriDNR 模型結構Fig.12 Architecture of TriDNR model

基于隨機游走的動態圖嵌入模型將每條邊與對應時刻相關聯，使隨機游走序列由一系列包含遞增時刻的邊所連接的節點構成，最后利用Skip-Gram 模型將每個節點映射成維向量。

Sajjad 等人將圖嵌入的生成過程分為兩步：首先，更新動態圖上的隨機游走序列。與直接在靜態快照上從頭開始隨機游走相比，更新算法保持了隨機游走的統計特性。然后，在給定前一時刻的嵌入表示以及更新后的隨機游走序列的條件下，利用Skip-Gram 模型對嵌入表示進行更新。CTDNE則利用時間隨機游走從連續型動態圖中學習包含時間信息的嵌入表示。實際上，CTDNE 采用的時間隨機游走與靜態圖方法相似，但約束每個隨機游走符合邊出現的時間順序，即邊的遍歷必須按照時間遞增的順序，由于每條邊包含多個時間戳，使得同一節點可能在游走中出現多次。時間信息的引入減少了嵌入的不確定性，使CTDNE 在眾多任務上的表現優于Deepwalk 和node2vec等靜態模型。

在動態圖中應用靜態方法存在兩大問題：（1）對每個快照都進行隨機游走非常耗時；（2）不同快照的嵌入空間并不一致。為解決上述問題，Mahdavi 等人在node2vec 的基礎上，提出了動態圖嵌入模型dynnode2vec。該模型在快照上運行node2vec 獲得嵌入向量以及訓練后的Skip-Gram 模型。對于后續快照，在兩個連續快照之間執行以下步驟：（1）為演化節點生成隨機游走序列；（2）使用動態Skip-Gram將前一時刻學習到的嵌入作為初始權值，結合演化節點的隨機游走生成當前時刻嵌入。由于動態圖是逐漸演化的，即大多數節點的鄰域保持不變，dynnode2vec 僅對演化節點進行隨機游走大幅提升了模型效率。

STWalk是一種無監督節點軌跡學習算法，通過捕捉給定時間窗口內節點變化生成嵌入表示。該模型將當前時刻快照上的隨機游走定義為空間游走，過去時刻快照上的隨機游走定義為時間游走，從而捕捉節點的時空行為，然后利用Skip-Gram 生成節點軌跡的嵌入表示。STWalk 有兩種不同的變體：STWalk1 同時考慮空間游走和時間游走來學習嵌入表示；STWalk2 將空間游走和時間游走建模為兩個子問題并分別求解，然后組合兩個結果獲得最終的嵌入表示。上述模型僅使用圖的結構信息學習捕獲節點軌跡時空特性的低維嵌入，未考慮節點特征和標簽信息。

Deepwalk 和node2vec 模仿單詞嵌入作為節點嵌入表示，而tNodeEmbed模仿句子嵌入作為節點嵌入表示。句子中每個單詞不僅代表節點隨時間變化的向量，還捕捉了節點角色和連接關系的動態變化。為此，tNodeEmbed 使用聯合損失函數優化兩個目標：（1）三維特征空間中節點的靜態鄰域；（2）圖的動態特性。tNodeEmbed 使用node2vec對節點嵌入進行初始化，將不同時刻的節點表示進行對齊，然后根據給定的圖分析任務和過去時刻的節點嵌入聯合學習，使生成的嵌入既保留圖的結構和動態信息，又適用于特定任務。

2.3 基于自編碼器的圖嵌入

自編碼器（autoencoder，AE）是一種人工神經網絡，包含編碼器和解碼器兩部分，用于無監督地構造輸入數據的向量表示。通過對數據中的非線性結構進行建模，自編碼器使隱藏層學習到的表示維度小于輸入數據，即對原始數據進行降維?；谧跃幋a器的圖嵌入方法使用自編碼器對圖的非線性結構建模，生成圖的低維嵌入表示。

基于自編碼器的圖嵌入方法起源于使用稀疏自編碼器的GraphEncoder。其基本思想是將歸一化的圖相似度矩陣作為節點原始特征輸入到稀疏自編碼器中進行分層預訓練，使生成的低維非線性嵌入可以近似地重建輸入矩陣并保留稀疏特性：

SDNE利用深度自編碼器以及圖的一階、二階相似度，捕獲高度非線性的網絡結構。SDNE 包含有監督組件和無監督組件（見圖13），用于保持節點的一階和二階相似度。有監督組件引入拉普拉斯特征映射作為一階相似度的目標函數，使生成的嵌入捕獲局部結構信息。無監督組件修改L2 重建損失函數作為二階相似度的目標函數，使生成的嵌入捕獲全局結構信息。對一階和二階相似度聯合優化，增強了模型在稀疏圖上的魯棒性，使生成的嵌入同時保留全局和局部結構信息。

圖13 SDNE 模型結構Fig.13 Framework of SDNE

DNGR生成低維嵌入的過程主要分為三步：（1）利用隨機沖浪模型捕捉圖的結構信息，并生成共現概率矩陣；（2）利用共現概率矩陣計算正逐點互信息（positive pointwise mutual information，PPMI）矩陣；（3）將PPMI 矩陣輸入堆疊去噪自編碼器（stacked denoising autoencoder，SDAE）生成低維嵌入表示。相較于隨機游走，隨機沖浪直接獲取圖的結構信息，克服了原有采樣過程的限制；PPMI 矩陣能夠保留圖的高階相似度信息；堆疊結構使隱層維度平滑遞減，提升深層架構學習復雜特征的能力，同時去噪策略增強了模型的魯棒性。

DNE-APP利用半監督堆疊式自編碼器（stacked autoencoder，SAE）生成保留階信息的低維嵌入主要分為兩步：（1）使用PPMI 度量和步轉移概率矩陣，生成包含階信息的相似度聚合矩陣。（2）使用SAE重構相似度聚合矩陣，學習低維非線性嵌入表示。與僅保持一階和二階相似度的SDNE 相比，DNEAPP 模型可以保持不同的階相似度；與僅重建高階相似度的DNGR 相比，DNE-APP 在重建過程中引入了成對約束，使相似節點在嵌入空間更加接近。

變分自編碼器（variational autoencoder，VAE）是用于降維的生成式模型，其優勢為容忍噪聲和學習平滑的表示。VGAE首先引入VAE 學習可解釋的無向圖嵌入表示。模型的編碼器部分使用圖卷積網絡（graph convolutional network，GCN）：

式中，=GCN(,) 是均值向量μ的矩陣，同樣ln=GCN(,)為方差向量。模型的解碼器部分使用嵌入的內積：

式中，(·)是sigmoid 函數。最后，VGAE 通過最小化重構損失和變分下界對模型進行優化：

式中，[(·)||(·)]為(·)和(·)的KL散度，()為高斯先驗。

Salha 等人提出的Linear-VGAE 模型使用基于歸一化鄰接矩陣的簡單線性模型替換VGAE 中的GCN 編碼器：

與一般的非對稱模型不同，GALA采用完全對稱的圖卷積自編碼器模型生成圖的低維嵌入表示。在對輸入矩陣重構的過程中，編碼器執行的拉普拉斯平滑與解碼器的拉普拉斯銳化相對稱。與現有的VGAE 方法不同，為了使解碼器可以直接重構節點的特征矩陣，GALA 使用譜半徑為1 的拉普拉斯銳化表示。相較于僅使用GCN 編碼器的模型，GALA 的對稱結構，能夠在編碼和解碼過程中同時使用結構信息和節點特征。

ANE使用對抗性自編碼器生成捕獲高度非線性結構信息的低維嵌入。具體而言，ANE 利用一階和二階相似度捕捉圖的局部和全局結構，使生成的嵌入可以保持高度的非線性，同時訓練過程對抗性自編碼器的兩個準則：一是基于重建誤差的自編碼器訓練準則；二是將嵌入表示的聚合后驗分布與任意先驗分布匹配的對抗性訓練準則。通過施加對抗性正則化，ANE 改善了嵌入生成過程中的流形斷裂問題，提升了低維嵌入的表示能力。

基于自編碼器的動態圖方法將每個時刻訓練的參數作為下一時刻自編碼器的初始值，從而在一定程度上保持生成嵌入的穩定性，節省模型的訓練時間，提高模型的計算效率。

受SDNE 的啟發，Goyal 等人提出了快照型動態圖嵌入模型DynGEM（見圖14）。該模型使用深度自編碼器將輸入數據映射到高度非線性的低維嵌入空間，以捕捉任一時刻快照中節點的連接趨勢，同時下一個時刻的嵌入模型直接繼承前一個時刻的訓練參數，使時刻的快照嵌入可以利用-1 時刻快照嵌入進行增量的學習。由于動態圖中節點的數量不斷變化，DynGEM 設計了一種可動態調節神經網絡中神經元個數、隱層層數的方法PropSize。在訓練過程中，DynGEM 結合一階相似度和二階相似度保留局部結構信息和全局結構信息，同時引入L1 和L2 正則化進一步提升模型性能。需要注意的是DynGEM 不強加保持相鄰時刻嵌入接近的顯式正則化，即相鄰時刻的快照如果明顯不同，則相應的編碼函數f和f也有所不同。

圖14 DynGEM 模型結構Fig.14 Framework of DynGEM

DynGEM 生成當前時刻嵌入時只捕獲了前一時刻的信息，致使大量歷史信息被忽略，為此Goyal 等人提出了另一個基于自編碼器的動態圖嵌入模型dyngraph2vec。該模型將之前個時刻的圖結構信息作為輸入，將當前時刻生成圖嵌入作為輸出，從而捕獲當前時刻與之前多個時刻節點之間的非線性交互信息。該模型有三種變體（見圖15）：dyngraph-2vecAE 以一種簡單的方式對自編碼器進行擴展；dyngraph2vecRNN 和dyngraph2vecAERNN 使 用 長 短期記憶網絡（long short-term memory，LSTM）對歷史信息編碼。在動態圖的演化過程中，dyngraph2vec僅使用相鄰節點，未考慮圖的高階相似度信息。

圖15 dyngraph2vec變體結構Fig.15 Variations of dyngraph2vec

隨著動態圖的演化，NetWalk可以增量地學習網絡表示（見圖16）。具體而言，NetWalk 利用初始的動態圖上提取的多個游走序列以及深度自編碼器的隱藏層生成節點嵌入表示。在訓練過程中，NetWalk聯合最小化游走序列中成對節點的表示距離和自編碼器的重構誤差，使學習到的嵌入表示既可以實現局部擬合，又可以實現全局正則化。NetWalk 對生成到的嵌入表示使用動態聚類模型，能夠標記圖中異常的節點或邊。

圖16 NetWalk 異常檢測的流程Fig.16 Workflow of NetWalk for anomaly detection

BurstGraph將動態圖的演化分為一般演化和突發演化，并使用兩個基于RNN 的VAE 分別對每個時刻的演化信息進行建模。在編碼器部分，兩個自編碼器共同使用GraphSAGE學習到的節點特征和拓撲結構信息。對于突發演化，BurstGraph 在VAE 中引入了spike &slab 分布作為近似后驗分布；對于一般演化，BurstGraph 使用原始的VAE 模型。為了充分利用圖的動態信息，BurstGraph 使用RNN 捕捉每個時刻的圖結構，將一般演化和突發演化信息保留在RNN狀態單元中，并隨時間的推移不斷更新狀態單元。由于生成的嵌入中保留了突發信息，BurstGraph常用于關于圖的異常檢測中的突發檢測任務。

動態圖嵌入通常存在三方面的局限性：（1）嵌入表示空間，歐式空間表示可能導致圖的潛在層次結構失真；（2）動態信息，忽視圖的動態演化通常會導致模型錯誤地利用未來信息來預測過去的交互；（3）不確定性，圖的固有特性，生成的確定性表示不能對不確定性建模。為了解決上述問題，HVGNN采用雙曲變分GNN 對雙曲空間中的動態圖進行建模，使生成的嵌入同時包含圖的動態信息和不確定性。具體而言，HVGNN 使用雙曲空間代替歐式空間，同時引入新的時間GNN（temporal GNN，TGNN）來建模動態特性。為了建模圖的不確定性，HVGNN設計了一個基于TGNN 的雙曲VGAE，使模型可以對不確定性和動態進行聯合建模。最后，引入的重參數化采樣算法，實現模型的梯度學習。相較于歐式空間計算量的指數增長，雙曲空間降低了模型的計算復雜度；對于不確定性的建模，增強了傳遞較少信息且具有較多動態特性節點的表示性能。

2.4 基于圖神經網絡的圖嵌入

圖神經網絡（GNN）是專門處理圖數據的深度模型，其利用節點間的消息傳遞來捕捉某種依賴關系，使生成的嵌入可以保留任意深度的鄰域信息。由于GNN 模型強大的表示能力，嵌入模型的性能得到了顯著提升。

基于GNN 的靜態圖模型聚合節點鄰域的嵌入并不斷迭代更新，利用當前的嵌入及上一次迭代的嵌入生成新的嵌入表示。通過多次迭代，GNN 模型學習到的嵌入可用于表征全局結構。

GCN 使用節點特征矩陣與鄰接矩陣生成包含節點的特征信息的嵌入表示（見圖17）。對于多層GCN，層間傳播公式為：

圖17 多層GCN 結構Fig.17 Framework of multi-layer GCN

GCN 通常應用于固定圖的直推式表示學習，GraphSAGE 將其擴展到歸納式無監督學習的任務中，利用節點特征（例如文本屬性、節點度）學習不可見節點的嵌入表示。GraphSAGE 不是為每個節點訓練單獨的嵌入，而是通過采樣和聚合節點的局部鄰域特征訓練聚合器函數，同時學習每個節點鄰域的拓撲結構及特征分布，生成嵌入表示（見圖18）。相比GCN，GraphSAGE 使用無監督損失函數強制鄰近節點具有相似表示，遠距離節點具有不同的表示。在給定下游任務的情況下，GraphSAGE 能夠替換或增加相應的目標函數，進行有監督或半監督學習，提升模型的靈活性；訓練過程執行分批次訓練，提升模型的收斂速度。

圖18 圖解GraphSAGE 采樣和聚合方式Fig.18 Visual illustration of GraphSAGE sampling and aggregation approach

圖注意力網絡（graph attention network，GAT）在GCN 的基礎上引入注意力機制，對鄰近節點特征加權求和，分配不同的權值。針對單個節點，GAT使用self-attention獲得注意力系數：

式中，e表示的是節點對節點的重要性。GAT 使用masked-attention將注意力分配到節點的鄰域：

式中，是層間的權重矩陣，||表示拼接運算。最后，使用multi-head attention生成節點嵌入：

式中，表示激活函數，表示multi-head attention的頭數，α為第個self-attention。注意力參數全圖共享，大幅減少了參數占用的存儲空間，同時GAT 對所有鄰居節點進行采樣，較GraphSAGE 得到的嵌入更具表征性。GAT 的缺點在于使用二階以上鄰居時，容易導致過度平滑。

用于圖嵌入的GNN 模型大多遵循鄰域聚合架構，通過遞歸地聚合和變換鄰域節點的特征向量生成節點嵌入，因此不能有效區分某些簡單的圖結構。為了提高GNN 模型對圖結構的辨識能力，圖同構網絡（graph isomorphism network，GIN）利用GNN 和WL（Weisfeiler-Lehman）圖同構測試之間的密切聯系，使生成的嵌入保留圖結構辨識信息。WL 測試通過聚合給定節點鄰居的特征向量對該節點進行迭代更新，同時使用內射聚合更新將不同的節點鄰域映射為不同的特征向量。GIN 采用與WL 內射聚合相似的方式進行建模：首先，將節點鄰居的特征向量抽象為一個多集；然后，將鄰居聚合運算抽象為多集上的函數（多集函數的區分性越強，底層的表征能力就越強）；最后，將生成的嵌入用于圖分類任務，其性能可以匹配WL 測試的結果。

MF-GCN是一種多濾波GCN 模型（見圖19），在每個傳播層使用多個局部GCN 濾波器進行特征提取，使模型捕捉到節點特征的不同方面。對于第一層，MF-GCN 對節點屬性進行如下操作：

圖19 MF-GCN 模型結構Fig.19 Framework of MF-GCN

多數GCN 模型中鄰域相互作用項的系數相對較小，導致性能與采用線性策略的簡化圖卷積網絡（simplified graph convolutional networks，SGC）相當。為了有效捕捉圖的復雜非線性，GraphAIR同時對鄰域聚合和鄰域交互進行建模。GraphAIR 由兩部分組成：鄰域聚合模塊通過組合鄰域特征來構建節點表示；鄰域交互模塊通過乘法運算顯式建模鄰域交互?，F有的大多數GCN 模型與GraphAIR 兼容，可以提供即插即用的鄰域聚合模塊和鄰域交互模塊。此外，GraphAIR 利用殘差學習策略，將鄰域交互與鄰域聚合分離，使模型更容易優化。

SDGNN是用于處理符號有向圖的嵌入模型，其在傳統GNN 的基礎上考慮了平衡理論和地位理論，重新設計聚合器和損失函數。SDGNN聚合來自不同鄰域的信息，并使用MLP（multilayer perceptron）將這些消息編碼為節點嵌入。SDGNN 的聚合器可分為兩類：一是平均聚合器，二是注意力聚合器。為了優化生成的嵌入，SDGNN 使用組合損失函數來重構網絡中的符號、方向和三角形三個關鍵特征。平衡理論和地位理論的引入，使SDGNN 在考慮邊緣符號的同時兼顧方向信息，提升了模型在符號圖分析任務中的表現。

基于GNN 的動態圖模型通常在靜態圖模型的基礎上，引入一種循環機制更新網絡參數，實現動態過程的建模，使生成低維嵌入可以有效保留圖的動態演化信息。

DyRep將動態圖嵌入假設為圖的動態（拓撲演化）和圖上的動態交織演化（節點間的活動）的中介過程。DyRep 采用關聯和通信事件的形式接收動態信息，并基于以下原則捕獲觀察到的事件的影響，更新有關節點的表示：（1）自我傳播。自我傳播是支配單個節點演化的動力中最小的組成部分。節點相對于其先前位置在嵌入空間中演化，而不是以隨機方式進化。（2）外源驅動。一些外力可以在某時間間隔平滑地更新該節點的當前特征。（3）局部嵌入傳播。事件中涉及的兩個節點形成臨時（通信）或永久（關聯）路徑，用于信息從一個節點的鄰域傳播到另一個節點。DyRep 采用雙時間尺度來捕捉圖級和節點級的動態過程，計算節點表示并參數化。最后，使用時間注意機制耦合模型的結構和時間信息，使生成的節點嵌入可以捕獲非線性的動態信息。DyRep 作為一種歸納式學習模型，強調學習節點的表示方法而不是節點的固定表示，因此更利于新的節點表示的生成。

DySAT通過鄰域結構和時間兩個維度的聯合自注意力來計算節點嵌入，主體為三個模塊（見圖20）：（1）結構注意力塊通過自注意聚集和堆疊從每個節點局部鄰域中提取特征，以計算每個快照的中間表示并輸入到時間模塊；（2）時間自注意力塊通過嵌入每個快照的絕對時間位置來捕獲排序信息，并將位置嵌入與結構注意力塊的輸出組合，輸入到前饋層；（3）圖上下文預測模塊通過跨多個時間步長的目標函數保留節點的鄰域信息，使生成的嵌入能夠捕捉結構演化。DySAT 的優點在于使用多頭注意力能夠捕獲動態性的多個方面，缺點在于該模型僅適用于節點數恒定的動態圖，并且節點共現率作為損失函數導致模型捕捉節點的動態變化的能力有限。

圖20 DySAT 模型結構Fig.20 Framework of DySAT

動態圖中節點可能頻繁出現和消失，使得RNN在學習這種不規則的行為時非常具有挑戰性。為了解決這個問題，EvolveGCN在每個時間步使用RNN 來調整GCN（即網絡參數），即關注GCN 參數在每個時刻的演化而不關注該時刻的節點表示，這不僅提高了模型的自適應性和靈活性，還可以保持圖的動態信息。此外，EvolveGCN 只對RNN 參數進行訓練，不再訓練GCN 參數，這種方式使得參數的數量不會隨著時刻的增加而增長，使該模型像常用的RNN 一樣易于管理。

在新的邊出現時，DGNN不僅更新節點表示，同時將交互信息傳播到其他受影響的節點，使嵌入信息在更新和傳播過程中可以合并交互之間的時間間隔。當新的邊出現時，兩端節點及其一階鄰域都有明顯的概率變化。此外，鄰域受到的影響與時刻有關，最近時刻與端點交互的鄰居節點對出現的新變化很敏感，而較遠的過去時刻的鄰居受影響較小。端點和一階鄰域均使用時態信息增強LSTM 作為更新模塊的基本框架，使模型能夠處理不同時間間隔的信息。

TemporalGAT通過集成GAT 和時間卷積網絡（temporal convolutional network，TCN）來學習動態圖上的嵌入表示（見圖21）。該模型將self-attention應用于節點鄰域，并通過TCN 保留圖的動態信息。最后，采用二元交叉熵損失函數學習節點表示，并預測節點之間是否存在邊。TemporalGAT 不僅能夠建模節點數目不固定的動態圖，還能同時捕獲動態圖的結構信息與時間信息。

圖21 TemporalGAT 模型結構Fig.21 Framework of TemporalGAT

2.5 基于其他方法的圖嵌入

LINE同樣定義了一階相似度和二階相似度函數，并對其進行優化。一階相似度用于保持鄰接矩陣和嵌入表示的點積接近，二階相似度用于保持上下文節點的相似性。為了結合一階和二階相似度，LINE 分別優化一階和二階相似度的目標函數，然后將生成的嵌入向量進行拼接。LINE 的邊采樣策略克服了隨機梯度下降的局限性，使其能夠應用到大規模圖嵌入中；但是一階和二階表示單獨優化以及簡單的拼接操作，限制了模型表示能力。

DRNE沒有重建鄰接矩陣，而是直接使用LSTM 聚合鄰域信息重建節點嵌入（見圖22）。DRNE的目標函數如下：由于LSTM 要求其輸入是一個序列，DRNE 根據節點的度數進行排序，同時對度數較大的節點采用鄰域抽樣技術，以防止過長的記憶。這種方法可以保持節點的正則等價性和多種中心性度量（如PageRank）。

圖22 DRNE 模型結構Fig.22 Framework of DRNE

Transformer架構已經成為許多領域的主流選擇，但在圖級預測任務中，通常表現不佳。為此，Ying等人在標準Transformer 的基礎上利用圖的結構信息構建Graphormer（見圖23）。對于結構信息的編碼主要分為三部分：（1）中心性編碼（centrality encoding）用于捕捉圖中節點的重要性，根據每個節點的度為每個節點分配一個可學習向量，并將其添加到輸入層的節點特征中。（2）空間編碼（spatial encoding）用于捕捉節點之間的結構關系，根據每個節點對的空間關系為其分配了一個可學習的嵌入。（3）邊編碼（edge encoding）用于捕捉邊緣特征中額外的空間信息，然后將其輸入到Transformer 層。Graphormer 同時使用上述結構信息編碼，提升模型性能，進而生成更優的嵌入表示。

圖23 Graphormer模型結構Fig.23 Framework of Graphormer

HTNE使用Hawkes 過程捕捉歷史鄰域對當前鄰域的影響，建模動態圖中節點的鄰域序列。然后，將節點分別映射為基向量和歷史向量，并輸入到Hawkes 過程以生成嵌入表示。由于歷史鄰域對當前鄰域形成的影響因節點而不同，引入注意力機制調節影響的大小。HTNE 的核心在于使用鄰域的形成過程描述節點的動態演化，Hawkes 過程及注意力的引入使生成的嵌入有效集成到上述信息。

DynamicTriad通過施加三元組（一組三個頂點的集合）模擬圖的動態變化。一般來說，三元組分為兩種類型：閉合三元組和開放三元組。由開放三元組演化為封閉三元組的三元組閉合過程是動態圖形成和演化的基本機制。DynamicTriad 采用統一的框架來量化上述閉合過程，使模型能夠有效捕捉圖的動態信息。

動態圖通常是在微觀和宏觀兩方面隨時間演化，微觀動態可以描述拓撲結構的形成過程，宏觀動態描述了圖規模的演化模式。MDNE是首個將微觀動態和宏觀動態同時融入到動態圖嵌入過程的模型。對于微觀動態，MDNE 把邊的建立當作時間事件，并提出時間注意點流程來捕獲用于嵌入生成的時間屬性。對于宏觀動態，MDNE 通過定義使用嵌入參數化的動態方程來捕獲內在演化模式，再利用內在演化模式在更高層次上約束圖的拓撲結構。最后，MDNE 利用微觀動態和宏觀動態的演化和交互，生成節點嵌入。微觀動態描述的是網絡結構的形成過程，宏觀動態描述的是網絡規模的演化模式。大多數動態圖方法只考慮了微觀動態，忽略了宏觀動態在保持網絡結構和演化模式方面的重要價值，MDNE 同時使用宏觀動態和微觀動態，進而增強了模型的泛化能力。

因果匿名游走（causal anonymous walks，CAW）與匿名游走（anonymous walks，AW）相比有兩個不同性質：（1）因果關系提取。CAW 從感興趣的鏈接開始，隨著時間的推移回溯多個相鄰鏈接，以編碼動態圖的基本因果關系。（2）基于集合的匿名化。CAW 刪除遍歷集合中的節點標識以保證歸納學習，同時根據特定位置出現的計數對相應節點標識進行編碼。CAW-N 是專門用于鏈接預測的變體，該模型對兩個感興趣的節點進行CAW 采樣，然后通過RNN 和集合池化對采樣結果進行編碼和聚合，生成最終嵌入。CAW-N 不僅保留了游走過程中所有細粒度的時間信息，還可以通過motif計數將其移除。

2.6 圖嵌入模型關系分析

圖嵌入可以解釋為生成圖數據的向量表示，用于洞察圖的某種特性。表2 和表3 歸納了主要靜態圖嵌入和動態圖嵌入的模型策略?；诰仃嚪纸獾姆椒ㄖ挥邪囟ǖ哪繕撕瘮?，才能學習相應的圖結構和信息?；陔S機游走的方法可以通過改變參數來控制游走方式，還可以與其他模型疊加提升性能?；贏E 和GNN 的方法利用近似定理廣泛建模，使模型能夠同時學習節點屬性、拓撲結構和節點標簽等信息。

表2 靜態圖嵌入模型策略歸納Table 2 Strategies of static graph embedding

表3 動態圖嵌入模型策略歸納Table 3 Strategies of dynamic graph embedding

圖嵌入模型之間不是相互割裂的，而是存在理論依托關系：CGE 修改LE 的目標函數，進一步增強鄰近節點相似性；DANE 離線模型采用類似LE 的方式保持各時刻快照的一階相似度；DHPE 以HOPE 為基礎，引入矩陣攝動理論更新動態信息；NGE、MF 和DWSF 以NMF 為基礎；node2vec 在Deepwalk 的 基礎上引入有偏的隨機游走；HARP 通常與Deepwalk 或node2vec 結合使用；dynnode2vec 在node2vec 的基礎上，使用Skip-Gram 更新動態信息；DNE-APP 在DNGR 基礎上引入成對約束；VGAE 使用GCN 作為編碼器；BurstGraph 使用GraphSAGE 進行采樣；GAT在GCN 的基礎上引入注意力機制；MF-GCN 以GraphSAGE為基礎構建；GraphAIR 將GCN 和GAT作為組件；EvolveGCN使用RNN調整GCN參數；TemporalGAT 對GAT 和TCN 進行集成。

3 數據集與應用

本章將詳細介紹常見圖嵌入數據集和機器學習任務。表4 和表5 分別為常用靜態圖和動態圖嵌入數據集的統計信息。

表4 靜態圖數據集統計信息Table 4 Statistics of static graph datasets

表5 動態圖數據集統計信息Table 5 Statistics of dynamic graph datasets

3.1 數據集

20-Newsgroup：由大約20 000 個新聞組文檔構成的數據集。這些文檔根據主題劃分成20 個組，每個文檔表示為每個詞的TF-IDF 分數向量，構建余弦相似圖。為了證明聚類算法的穩健性，分別從3、6 和9 個不同的新聞組構建了3 個圖，使用的縮寫NG 是Newsgroup 的縮寫。

Flickr：由照片分享網站Flickr 上的用戶組成的網絡。網絡中的邊指示用戶之間的聯系關系。標簽指示用戶的興趣組（例如黑白色攝影）。

DBLP：引文網絡數據集，每個頂點表示一個作者，從一個作者到另一個作者的參考文獻數量由這兩個作者之間的邊權重來記錄。標簽上標明了研究人員發表研究成果的4 個領域。

YouTube：YouTube 視頻分享網站用戶之間的社交網絡。標簽代表了喜歡視頻類型（例如動漫視頻）的觀眾群體。

Wikipedia：網頁共現網絡，節點表示網頁，邊表示網頁之間的超鏈接。Wikipedia數據集的TF-IDF矩陣是描述節點特征的文本信息，節點標簽是網頁的類別。

Cora、CiteSeer、Pubmed：標準的引文網絡基準數據集，節點表示論文，邊表示一篇論文對另一篇論文的引用。節點特征是論文的詞袋表示，節點標簽是論文的學術主題。

Yelp：本地商業評論和社交網站，用戶可以提交對商家的評論，并與其他人交流。由于缺乏標簽信息，該數據集常用于鏈接預測。

Epinions：產品評論網站數據集，基于評論的詞袋模型生成節點屬性，以用戶評論的主要類別作為類別標簽。該數據集有16 個時間戳。

Hep-th：高能物理理論會議研究人員的合作網絡，原始數據集包含1993 年1 月至2003 年4 月期間高能物理理論會議的論文摘要。

AS(autonomous systems)：由邊界網關協議日志構建的用戶通信網絡。該數據集包含從1997 年11月8 日到2000 年1 月2 日的733 條通信記錄，通常按照年份將這些記錄劃分為不同快照。

Enron：Enron 公司員工之間的電子郵件通信網絡。該數據集包含1999 年1 月至2002 年7 月期間公司員工之間的電子郵件。

UCI：加州大學在線學生社區用戶之間的通信網絡。節點表示用戶，用戶之間的消息通信表示邊緣。每條邊攜帶的時間指示用戶何時通信。

3.2 網絡重構

網絡重構任務是利用學習到節點低維向量表示重新構建原始圖的拓撲結構，評估生成的嵌入保持圖結構信息的能力。通過計算基于節點嵌入的內積或者相似性來預測節點間是否存在鏈接，使用前對頂點真實鏈接所占原始圖中鏈接的比例來評估模型的重構表現。

網絡重構任務通常分為3 個步驟：（1）使用圖嵌入模型生成嵌入表示。（2）計算節點對應的重構鄰近度并進行排序。（3）計算前對節點的真實鏈接的比例。

網絡重構任務通常采用MAP（mean average precision）作為評價指標：

式中，@()是節點v的精度，Δ()=1 表示節點和之間存在連接。

好的網絡嵌入方法能夠捕捉到具有網絡結構信息的嵌入表示，從而能夠很好地重構網絡。在Yelp數據集上，ANE 和LINE 的結果要好于僅利用一階相似度的LE 和使用隨機游走的Deepwalk。可見，表示局部結構的一階相似性和表示全局結構的二階相似性在保持網絡結構方面都起著重要的作用。由于ANE 采用了對抗性訓練，其表現略優于LINE。各模型網絡重構性能見圖24。

圖24 網絡重構性能對比Fig.24 Performance comparison of graph reconstruction

3.3 節點分類

節點分類任務是利用圖的拓撲結構和節點特征確定每個節點所屬類別?，F實世界的圖數據，可能不是完全標簽化的，由于各種因素大部分節點的標簽可能是未知的，節點分類任務可以利用已有標簽節點和連接關系來推斷丟失的標簽。此外，節點分類任務可分為兩類：多標簽分類和多類分類。前者使用的數據集中每個節點僅由一個類別標簽標記，后者則由多個類別標簽標記。

節點分類任務通常分為3 個步驟：（1）使用圖嵌入模型生成嵌入表示。（2）將包含標簽信息的數據集劃分為訓練集和測試集。（3）在訓練集上訓練分類器，在測試集驗證模型性能。常用的分類器包括邏輯回歸分類器、最近鄰分類器、支持向量機和樸素貝葉斯分類器等。

節點分類任務通常采用-1 和-1作為評價指標：

式中，1()是標簽的1 分數，表示準確率，表示召回率。對于多分類任務準確度（Accuracy）與-1 的值相同。

利用網絡結構和節點特征預測節點標簽在網絡分析中有著廣泛的應用。通過將生成的嵌入作為節點特征對節點進行分類，可以比較各種嵌入方法在該任務中的有效性。

在CiteSeer 數據集上的靜態圖節點分類實驗中，同時使用節點特征和網絡拓撲結構的GNN 模型均取得了較好的結果，僅使用網絡結構進行無監督學習的Deepwalk、node2vec 和LINE 模型性能較差。相較原始的GraphSAGE 模型，MF-GCN 使用多個局部GCN 濾波器進行特征提取，使模型捕捉到節點特征的不同方面，從而進一步提升了模型性能。同樣突出的GraphAIR 模型分別對鄰域聚合和鄰域交互進行建模，與原始的GCN 和GAT 模型結合使用，提升基礎模型的性能。各模型靜態圖節點分類性能見圖25。

圖25 靜態圖節點分類性能對比Fig.25 Performance comparison of static graph node classification

在引入時間信息的DBLP 數據集上的動態圖節點分類實驗中，與靜態圖嵌入模型（DeepWalk、node2vec、LINE 和SDNE）相比，DANE 保留的動態信息使生成的嵌入具有更強的表示能力；與動態圖嵌入模型（tNodeEmbed、CTDNE、HTNE、DynamicTriad和MDNE）相比，DANE 捕捉了拓撲結構和節點屬性特征的相關性，并保留圖的動態信息，生成抗噪聲的嵌入，從而提高結構嵌入的準確性。此外，由于DANE抗噪聲的特性，使其有較好的魯棒性。各模型動態圖節點分類性能見表6。

表6 動態圖節點分類性能對比Table 6 Performance comparison of dynamic graph node classification %

3.4 鏈接預測

鏈接預測任務用于預測兩個節點之間是否存在邊或者預測圖中未觀察到的鏈接，評估生成嵌入在保持拓撲結構方面的性能。

鏈接預測任務通常分為3 個步驟：（1）使用圖嵌入模型生成嵌入表示。（2）對數據集中任意兩個節點間的邊信息進行標記，然后將數據集分為訓練集和測試集。（3）在訓練集上訓練分類器，在測試集上進行鏈接預測實驗。

鏈接預測任務通常采用AUC（area under the curve）和AP（average precision）作為評價指標：

AUC：把閾值設置在緊靠每個正例之下，計算負類的查全率，再取平均值。

AP：把閾值設置在緊靠每個正例之下，計算正類的查準率，再取平均值。

圖嵌入可以顯式或隱式地捕獲網絡的固有結構，以預測可能存在但未被觀察到的連接關系。在CiteSeer 數據集上，GraphAIR（AIR-GAE）的性能優于其他基于GNN 和AE 的方法，Deepwalk 的表現最差。主要原因可能是鏈路預測任務通常使用成對解碼器來計算兩個節點之間鏈路的概率。例如，GAE和VGAE 假設兩個節點之間存在邊的概率與這兩個節點的嵌入的點積成正比。AIR-GAE 通過兩個節點嵌入相乘來顯式地對鄰域交互進行建模，這與鏈接預測任務有著內在的聯系，進而提升了模型性能。各模型鏈接預測性能見表7。

表7 鏈接預測性能對比Table 7 Performance comparison of link prediction %

3.5 聚類

聚類任務采用無監督的方式將圖劃分為若干個社區，使屬于同一社區的節點具有更多相似特性。在利用模型生成嵌入后，一般采用頻譜聚類（非歸一化譜聚類和歸一化譜聚類）和-means等經典方法將節點嵌入聚類。

聚類任務通常采用歸一化互信息（normalized mutual information，NMI）評估聚類性能：

式中，用于度量和聚類結果之間的相似性，(·)表示信息熵。

將生成的嵌入表示進行聚類，使具有相似特性的節點盡可能在同一社區。在20-NewsGroup 數據集上，GraRep、LINE 和DNGR 模型在3NG、6NG 和9NG實驗中性能明顯優于其他基線算法。對于GraRep 和LINE，兩種方法可以有效捕捉豐富的局部關系信息，從而提高了聚類結果。對于DNGR，使用的深度神經網絡能夠有效捕捉圖的非線性，同時使用隨機沖浪代替廣泛使用的抽樣方法加強了原始圖中信息的提取。各模型聚類性能見圖26。

圖26 節點聚類性能對比Fig.26 Performance comparison of node clustering

3.6 異常檢測

異常檢測任務用于識別圖中的“非正?！苯Y構，通常包括異常節點檢測、異常邊緣檢測和異常變化檢測。常見的異常檢測方法有兩種：一是將原始圖進行壓縮，通過聚類和離群點檢測識別壓縮圖中的異常；二是利用模型生成節點嵌入并分組為個社群，檢測不屬于已有社群的新節點或邊。

異常檢測任務通常采用AUC 作為評價指標。

圖數據的異常檢測主要是找出與正常數據集差異較大的離群點（異常點）。好的嵌入表示能夠利用決策邊界，有效界定正常點與異常點。在DBLP 和Hep-th 數據集上，Deepwalk、node2vec 和SDNE 的實驗結果相近，而NetWalk明顯優于上述方法。NetWalk模型的高性能得益于以下優點：（1）網絡嵌入可以動態更新；（2）流式節點和邊可以在存儲空間恒定的情況下進行高效編碼；（3）可以靈活地擴展到不同類型的網絡；（4）可實時檢測網絡異常。各模型異常檢測性能見圖27。

圖27 異常檢測性能對比Fig.27 Performance comparison of anomaly detection

3.7 可視化

可視化任務是對嵌入進行降維和可視化，從而直觀地觀察原始圖中某些特征。可視化任務通常是在有標簽數據集上進行的，不同標簽的節點在二維空間中使用不同的顏色進行標記。由于嵌入中保留了原始圖的某種信息，可視化結果直接反映了二維空間中同一社群節點具有更加相似的特征。

對于可視化任務，好的嵌入表示在二維圖像中相同或相近的節點彼此接近，不同的節點彼此分離。在Cora 數據集上，將模型生成的低維嵌入輸入到-SNE，使嵌入維數降至2，同一類別的節點使用相同的顏色表示。Yuan 等人比較了不同模型的可視化性能，部分可視化結果見圖28。GCN 和GAT學習的節點向量能夠有效捕捉到社區的結構，使同類型節點更為接近。Deepwalk 和SDNE 只使用鄰接矩陣作為輸入，沒有充分利用節點特征和標簽信息，導致模型性能較差，尤其是SDNE 模型，不同類型的點在二維空間中幾乎是無序的。

圖28 不同模型的可視化結果Fig.28 Visualization of different models

4 未來研究方向

通過對傳統和新型圖嵌入方法的研究和分析，現階段的主要任務依然是提升模型對大規模和復雜圖數據的擴展性、創新模型方法和提高下游任務性能。據此，本章提出了未來工作的四個研究方向。

（1）面向大規模圖數據的嵌入模型

對于大規模靜態圖嵌入，通常采用分布式計算或無監督學習的方式提高計算效率。開放圖基準（open graph benchmark，OGB）是新興圖學習領域可擴展、可重復的基準，通過驗證node2vec、LINE 和GraphSAGE 等實驗表現，證明了模型的有效性。對于大規模動態圖嵌入，現有模型無法采用類似靜態圖的方式實現圖表示學習任務，因為動態圖的規模不僅涉及圖的大小，還涉及快照或時間戳的數量。因此，降低網絡演化復雜度和提升模型性能是解決大規模動態圖嵌入問題的兩個重要方面。

（2）面向復雜圖數據的嵌入模型

現階段，大部分研究仍集中在簡單的同質圖上，如經典的GCN 模型只需鄰接矩陣、節點特征矩陣和系數矩陣即可實現。然而，現實世界的網絡往往更加復雜，如異質圖、有向圖和超圖等?，F有模型中，HGSL實現了異質圖表示學習，SDGNN 實現了符號有向圖表示學習，DANE 實現了屬性圖的表示學習。隨著圖表示學習研究的深入，探索更為復雜圖數據的表示將仍舊是有前景的研究方向。

（3）改進模型訓練策略

復雜的模型可以提升效果，但往往超參數較多且難以訓練。相較于設計新的模型架構，一些研究者開始探索如何利用訓練策略（如數據擴增）來提升現有模型的性能。GraphMix利用數據擴增技術，將簡單的GCN 架構提升到先進基線模型的水平，并且無需額外的內存和計算消耗?，F階段，除了開發新的圖嵌入模型外，充分挖掘已有模型潛力仍然是一項充滿挑戰的工作。

（4）面向特定任務的嵌入模型

大部分圖嵌入模型生成的結果將用于節點分類、鏈接預測、可視化等多個任務。與上述建模思路不同，面向任務的嵌入模型只關注一個任務，并充分利用與該任務相關信息來訓練模型。多數情況下，面向任務的嵌入模型在目標任務上比通用嵌入模型更有效，如Semi-AttentionAE采用集成學習的方法，聯合訓練GAT 與LE，提升節點分類任務性能。針對特定任務設計高性能模型同樣是今后研究的熱點方向。

5 結束語

本文對圖嵌入文獻進行了全面回顧，給出了圖嵌入有關定義，提出了靜態圖和動態圖模型通用的分類方法，對現有模型的核心策略以及靜態圖和動態圖模型理論相關性進行了系統性分析。在應用部分，介紹了圖嵌入常用數據集以及節點分類、鏈接預測等常見的機器學習任務，比較了不同模型的表現。最后，從圖數據、模型策略和應用場景三方面提出了圖嵌入領域四個未來有希望的研究方向。