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

1.中國人民公安大學(xué) 信息網(wǎng)絡(luò)安全學(xué)院，北京100038

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

3.天津市公安局河?xùn)|分局 科技信息化支隊，天津300171

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

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

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

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

1 圖嵌入相關(guān)定義及符號表示

1.1 問題定義

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

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

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

圖1 快照型和連續(xù)時間型動態(tài)圖Fig.1 Snapshot and continuous-time dynamic graphs

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

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

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

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

1.2 符號表示

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

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

2 圖嵌入分類

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

圖3 圖嵌入內(nèi)容體系Fig.3 Content system of graph embedding

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

2.1 基于矩陣分解的圖嵌入

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

基于矩陣分解的靜態(tài)圖嵌入模型對節(jié)點關(guān)聯(lián)信息矩陣和屬性信息矩陣進(jìn)行特征分解，然后將分解得到的屬性嵌入和結(jié)構(gòu)嵌入進(jìn)行融合，生成節(jié)點的低維嵌入表示。圖5 說明了矩陣分解和靜態(tài)圖嵌入生成的一般過程。

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

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

圖6 LLE 步驟Fig.6 Steps of LLE

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

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

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

非對稱傳遞性可以刻畫有向邊之間的關(guān)聯(lián)，有助于捕捉圖的結(jié)構(gòu)。為了保留有向圖中的非對稱傳遞性，HOPE采用了一種保持高階相似度的嵌入方法，在保留非對稱傳遞性的向量空間中生成圖嵌入（見圖7），訓(xùn)練中使用L2 范數(shù)進(jìn)行優(yōu)化：

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

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

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

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

由上式可知，LE 的目標(biāo)函數(shù)強調(diào)權(quán)值大的節(jié)點對，弱化權(quán)值小的節(jié)點對，導(dǎo)致原始圖中的局部拓?fù)浣Y(jié)構(gòu)被破壞。為了增強圖嵌入的局部拓?fù)浔３中?，柯西圖嵌入（Cauchy graph embedding，CGE）引入距離的反函數(shù)來保持節(jié)點在嵌入空間中的相似關(guān)系。因此，CGE 將LE 的目標(biāo)函數(shù)改寫為：

相比LE，CGE 的目標(biāo)函數(shù)更加強調(diào)短距離，即確保局部越鄰近的節(jié)點在嵌入空間的距離越接近。

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

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

圖9 DANE 模型結(jié)構(gòu)Fig.9 Framework of DANE

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

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

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

MF通過構(gòu)造攜帶重要特征的矩陣因子，使?jié)撛诘腘MF 特征有效地表達(dá)動態(tài)信息。為了充分利用不同時刻的拓?fù)湫畔?，MF 對嵌入空間的鄰接關(guān)系矩陣進(jìn)行整合，找到在各個時刻一致的嵌入矩陣和系數(shù)矩陣，并通過最小化Frobenius 范數(shù)使各時刻Y和、W和差異最小。基于NMF 加權(quán)表示相似性指數(shù)的MF 比基于靜態(tài)表示相似性指數(shù)的方法具有更好的性能。

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

2.2 基于隨機游走的圖嵌入

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

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

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

圖10 Deepwalk 模型結(jié)構(gòu)Fig.10 Framework of Deepwalk

生成的嵌入將節(jié)點之間的關(guān)系編碼在低維向量空間，用于捕捉鄰域相似性和社區(qū)結(jié)構(gòu)，學(xué)習(xí)節(jié)點的潛在特征。Deepwalk 不僅在數(shù)據(jù)量較少時有較好的表現(xiàn)，還可以擴展到大型圖的表示學(xué)習(xí)。由于優(yōu)化過程中未使用明確的目標(biāo)函數(shù)，使得模型保持網(wǎng)絡(luò)結(jié)構(gòu)的能力受到限制。

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

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

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

利用分層Softmax，Deepwalk 目標(biāo)函數(shù)可以改寫為矩陣分解的形式：

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

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

圖12 TriDNR 模型結(jié)構(gòu)Fig.12 Architecture of TriDNR model

基于隨機游走的動態(tài)圖嵌入模型將每條邊與對應(yīng)時刻相關(guān)聯(lián)，使隨機游走序列由一系列包含遞增時刻的邊所連接的節(jié)點構(gòu)成，最后利用Skip-Gram 模型將每個節(jié)點映射成維向量。

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

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

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

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

2.3 基于自編碼器的圖嵌入

自編碼器（autoencoder，AE）是一種人工神經(jīng)網(wǎng)絡(luò)，包含編碼器和解碼器兩部分，用于無監(jiān)督地構(gòu)造輸入數(shù)據(jù)的向量表示。通過對數(shù)據(jù)中的非線性結(jié)構(gòu)進(jìn)行建模，自編碼器使隱藏層學(xué)習(xí)到的表示維度小于輸入數(shù)據(jù)，即對原始數(shù)據(jù)進(jìn)行降維。基于自編碼器的圖嵌入方法使用自編碼器對圖的非線性結(jié)構(gòu)建模，生成圖的低維嵌入表示。

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

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

圖13 SDNE 模型結(jié)構(gòu)Fig.13 Framework of SDNE

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

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

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

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

式中，(·)是sigmoid 函數(shù)。最后，VGAE 通過最小化重構(gòu)損失和變分下界對模型進(jìn)行優(yōu)化：

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

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

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

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

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

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

圖14 DynGEM 模型結(jié)構(gòu)Fig.14 Framework of DynGEM

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

圖15 dyngraph2vec變體結(jié)構(gòu)Fig.15 Variations of dyngraph2vec

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

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

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

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

2.4 基于圖神經(jīng)網(wǎng)絡(luò)的圖嵌入

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

基于GNN 的靜態(tài)圖模型聚合節(jié)點鄰域的嵌入并不斷迭代更新，利用當(dāng)前的嵌入及上一次迭代的嵌入生成新的嵌入表示。通過多次迭代，GNN 模型學(xué)習(xí)到的嵌入可用于表征全局結(jié)構(gòu)。

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

圖17 多層GCN 結(jié)構(gòu)Fig.17 Framework of multi-layer GCN

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

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

圖注意力網(wǎng)絡(luò)（graph attention network，GAT）在GCN 的基礎(chǔ)上引入注意力機制，對鄰近節(jié)點特征加權(quán)求和，分配不同的權(quán)值。針對單個節(jié)點，GAT使用self-attention獲得注意力系數(shù)：

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

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

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

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

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

圖19 MF-GCN 模型結(jié)構(gòu)Fig.19 Framework of MF-GCN

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

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

基于GNN 的動態(tài)圖模型通常在靜態(tài)圖模型的基礎(chǔ)上，引入一種循環(huán)機制更新網(wǎng)絡(luò)參數(shù)，實現(xiàn)動態(tài)過程的建模，使生成低維嵌入可以有效保留圖的動態(tài)演化信息。

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

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

圖20 DySAT 模型結(jié)構(gòu)Fig.20 Framework of DySAT

動態(tài)圖中節(jié)點可能頻繁出現(xiàn)和消失，使得RNN在學(xué)習(xí)這種不規(guī)則的行為時非常具有挑戰(zhàn)性。為了解決這個問題，EvolveGCN在每個時間步使用RNN 來調(diào)整GCN（即網(wǎng)絡(luò)參數(shù)），即關(guān)注GCN 參數(shù)在每個時刻的演化而不關(guān)注該時刻的節(jié)點表示，這不僅提高了模型的自適應(yīng)性和靈活性，還可以保持圖的動態(tài)信息。此外，EvolveGCN 只對RNN 參數(shù)進(jìn)行訓(xùn)練，不再訓(xùn)練GCN 參數(shù)，這種方式使得參數(shù)的數(shù)量不會隨著時刻的增加而增長，使該模型像常用的RNN 一樣易于管理。

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

TemporalGAT通過集成GAT 和時間卷積網(wǎng)絡(luò)（temporal convolutional network，TCN）來學(xué)習(xí)動態(tài)圖上的嵌入表示（見圖21）。該模型將self-attention應(yīng)用于節(jié)點鄰域，并通過TCN 保留圖的動態(tài)信息。最后，采用二元交叉熵?fù)p失函數(shù)學(xué)習(xí)節(jié)點表示，并預(yù)測節(jié)點之間是否存在邊。TemporalGAT 不僅能夠建模節(jié)點數(shù)目不固定的動態(tài)圖，還能同時捕獲動態(tài)圖的結(jié)構(gòu)信息與時間信息。

圖21 TemporalGAT 模型結(jié)構(gòu)Fig.21 Framework of TemporalGAT

2.5 基于其他方法的圖嵌入

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

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

圖22 DRNE 模型結(jié)構(gòu)Fig.22 Framework of DRNE

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

圖23 Graphormer模型結(jié)構(gòu)Fig.23 Framework of Graphormer

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

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

動態(tài)圖通常是在微觀和宏觀兩方面隨時間演化，微觀動態(tài)可以描述拓?fù)浣Y(jié)構(gòu)的形成過程，宏觀動態(tài)描述了圖規(guī)模的演化模式。MDNE是首個將微觀動態(tài)和宏觀動態(tài)同時融入到動態(tài)圖嵌入過程的模型。對于微觀動態(tài)，MDNE 把邊的建立當(dāng)作時間事件，并提出時間注意點流程來捕獲用于嵌入生成的時間屬性。對于宏觀動態(tài)，MDNE 通過定義使用嵌入?yún)?shù)化的動態(tài)方程來捕獲內(nèi)在演化模式，再利用內(nèi)在演化模式在更高層次上約束圖的拓?fù)浣Y(jié)構(gòu)。最后，MDNE 利用微觀動態(tài)和宏觀動態(tài)的演化和交互，生成節(jié)點嵌入。微觀動態(tài)描述的是網(wǎng)絡(luò)結(jié)構(gòu)的形成過程，宏觀動態(tài)描述的是網(wǎng)絡(luò)規(guī)模的演化模式。大多數(shù)動態(tài)圖方法只考慮了微觀動態(tài)，忽略了宏觀動態(tài)在保持網(wǎng)絡(luò)結(jié)構(gòu)和演化模式方面的重要價值，MDNE 同時使用宏觀動態(tài)和微觀動態(tài)，進(jìn)而增強了模型的泛化能力。

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

2.6 圖嵌入模型關(guān)系分析

圖嵌入可以解釋為生成圖數(shù)據(jù)的向量表示，用于洞察圖的某種特性。表2 和表3 歸納了主要靜態(tài)圖嵌入和動態(tài)圖嵌入的模型策略?；诰仃嚪纸獾姆椒ㄖ挥邪囟ǖ哪繕?biāo)函數(shù)，才能學(xué)習(xí)相應(yīng)的圖結(jié)構(gòu)和信息。基于隨機游走的方法可以通過改變參數(shù)來控制游走方式，還可以與其他模型疊加提升性能。基于AE 和GNN 的方法利用近似定理廣泛建模，使模型能夠同時學(xué)習(xí)節(jié)點屬性、拓?fù)浣Y(jié)構(gòu)和節(jié)點標(biāo)簽等信息。

表2 靜態(tài)圖嵌入模型策略歸納Table 2 Strategies of static graph embedding

表3 動態(tài)圖嵌入模型策略歸納Table 3 Strategies of dynamic graph embedding

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

3 數(shù)據(jù)集與應(yīng)用

本章將詳細(xì)介紹常見圖嵌入數(shù)據(jù)集和機器學(xué)習(xí)任務(wù)。表4 和表5 分別為常用靜態(tài)圖和動態(tài)圖嵌入數(shù)據(jù)集的統(tǒng)計信息。

表4 靜態(tài)圖數(shù)據(jù)集統(tǒng)計信息Table 4 Statistics of static graph datasets

表5 動態(tài)圖數(shù)據(jù)集統(tǒng)計信息Table 5 Statistics of dynamic graph datasets

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

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

Flickr：由照片分享網(wǎng)站Flickr 上的用戶組成的網(wǎng)絡(luò)。網(wǎng)絡(luò)中的邊指示用戶之間的聯(lián)系關(guān)系。標(biāo)簽指示用戶的興趣組（例如黑白色攝影）。

DBLP：引文網(wǎng)絡(luò)數(shù)據(jù)集，每個頂點表示一個作者，從一個作者到另一個作者的參考文獻(xiàn)數(shù)量由這兩個作者之間的邊權(quán)重來記錄。標(biāo)簽上標(biāo)明了研究人員發(fā)表研究成果的4 個領(lǐng)域。

YouTube：YouTube 視頻分享網(wǎng)站用戶之間的社交網(wǎng)絡(luò)。標(biāo)簽代表了喜歡視頻類型（例如動漫視頻）的觀眾群體。

Wikipedia：網(wǎng)頁共現(xiàn)網(wǎng)絡(luò)，節(jié)點表示網(wǎng)頁，邊表示網(wǎng)頁之間的超鏈接。Wikipedia數(shù)據(jù)集的TF-IDF矩陣是描述節(jié)點特征的文本信息，節(jié)點標(biāo)簽是網(wǎng)頁的類別。

Cora、CiteSeer、Pubmed：標(biāo)準(zhǔn)的引文網(wǎng)絡(luò)基準(zhǔn)數(shù)據(jù)集，節(jié)點表示論文，邊表示一篇論文對另一篇論文的引用。節(jié)點特征是論文的詞袋表示，節(jié)點標(biāo)簽是論文的學(xué)術(shù)主題。

Yelp：本地商業(yè)評論和社交網(wǎng)站，用戶可以提交對商家的評論，并與其他人交流。由于缺乏標(biāo)簽信息，該數(shù)據(jù)集常用于鏈接預(yù)測。

Epinions：產(chǎn)品評論網(wǎng)站數(shù)據(jù)集，基于評論的詞袋模型生成節(jié)點屬性，以用戶評論的主要類別作為類別標(biāo)簽。該數(shù)據(jù)集有16 個時間戳。

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

AS(autonomous systems)：由邊界網(wǎng)關(guān)協(xié)議日志構(gòu)建的用戶通信網(wǎng)絡(luò)。該數(shù)據(jù)集包含從1997 年11月8 日到2000 年1 月2 日的733 條通信記錄，通常按照年份將這些記錄劃分為不同快照。

Enron：Enron 公司員工之間的電子郵件通信網(wǎng)絡(luò)。該數(shù)據(jù)集包含1999 年1 月至2002 年7 月期間公司員工之間的電子郵件。

UCI：加州大學(xué)在線學(xué)生社區(qū)用戶之間的通信網(wǎng)絡(luò)。節(jié)點表示用戶，用戶之間的消息通信表示邊緣。每條邊攜帶的時間指示用戶何時通信。

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

網(wǎng)絡(luò)重構(gòu)任務(wù)是利用學(xué)習(xí)到節(jié)點低維向量表示重新構(gòu)建原始圖的拓?fù)浣Y(jié)構(gòu)，評估生成的嵌入保持圖結(jié)構(gòu)信息的能力。通過計算基于節(jié)點嵌入的內(nèi)積或者相似性來預(yù)測節(jié)點間是否存在鏈接，使用前對頂點真實鏈接所占原始圖中鏈接的比例來評估模型的重構(gòu)表現(xiàn)。

網(wǎng)絡(luò)重構(gòu)任務(wù)通常分為3 個步驟：（1）使用圖嵌入模型生成嵌入表示。（2）計算節(jié)點對應(yīng)的重構(gòu)鄰近度并進(jìn)行排序。（3）計算前對節(jié)點的真實鏈接的比例。

網(wǎng)絡(luò)重構(gòu)任務(wù)通常采用MAP（mean average precision）作為評價指標(biāo)：

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

好的網(wǎng)絡(luò)嵌入方法能夠捕捉到具有網(wǎng)絡(luò)結(jié)構(gòu)信息的嵌入表示，從而能夠很好地重構(gòu)網(wǎng)絡(luò)。在Yelp數(shù)據(jù)集上，ANE 和LINE 的結(jié)果要好于僅利用一階相似度的LE 和使用隨機游走的Deepwalk?？梢?，表示局部結(jié)構(gòu)的一階相似性和表示全局結(jié)構(gòu)的二階相似性在保持網(wǎng)絡(luò)結(jié)構(gòu)方面都起著重要的作用。由于ANE 采用了對抗性訓(xùn)練，其表現(xiàn)略優(yōu)于LINE。各模型網(wǎng)絡(luò)重構(gòu)性能見圖24。

圖24 網(wǎng)絡(luò)重構(gòu)性能對比Fig.24 Performance comparison of graph reconstruction

3.3 節(jié)點分類

節(jié)點分類任務(wù)是利用圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點特征確定每個節(jié)點所屬類別。現(xiàn)實世界的圖數(shù)據(jù)，可能不是完全標(biāo)簽化的，由于各種因素大部分節(jié)點的標(biāo)簽可能是未知的，節(jié)點分類任務(wù)可以利用已有標(biāo)簽節(jié)點和連接關(guān)系來推斷丟失的標(biāo)簽。此外，節(jié)點分類任務(wù)可分為兩類：多標(biāo)簽分類和多類分類。前者使用的數(shù)據(jù)集中每個節(jié)點僅由一個類別標(biāo)簽標(biāo)記，后者則由多個類別標(biāo)簽標(biāo)記。

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

節(jié)點分類任務(wù)通常采用-1 和-1作為評價指標(biāo)：

式中，1()是標(biāo)簽的1 分?jǐn)?shù)，表示準(zhǔn)確率，表示召回率。對于多分類任務(wù)準(zhǔn)確度（Accuracy）與-1 的值相同。

利用網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點特征預(yù)測節(jié)點標(biāo)簽在網(wǎng)絡(luò)分析中有著廣泛的應(yīng)用。通過將生成的嵌入作為節(jié)點特征對節(jié)點進(jìn)行分類，可以比較各種嵌入方法在該任務(wù)中的有效性。

在CiteSeer 數(shù)據(jù)集上的靜態(tài)圖節(jié)點分類實驗中，同時使用節(jié)點特征和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的GNN 模型均取得了較好的結(jié)果，僅使用網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行無監(jiān)督學(xué)習(xí)的Deepwalk、node2vec 和LINE 模型性能較差。相較原始的GraphSAGE 模型，MF-GCN 使用多個局部GCN 濾波器進(jìn)行特征提取，使模型捕捉到節(jié)點特征的不同方面，從而進(jìn)一步提升了模型性能。同樣突出的GraphAIR 模型分別對鄰域聚合和鄰域交互進(jìn)行建模，與原始的GCN 和GAT 模型結(jié)合使用，提升基礎(chǔ)模型的性能。各模型靜態(tài)圖節(jié)點分類性能見圖25。

圖25 靜態(tài)圖節(jié)點分類性能對比Fig.25 Performance comparison of static graph node classification

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

表6 動態(tài)圖節(jié)點分類性能對比Table 6 Performance comparison of dynamic graph node classification %

3.4 鏈接預(yù)測

鏈接預(yù)測任務(wù)用于預(yù)測兩個節(jié)點之間是否存在邊或者預(yù)測圖中未觀察到的鏈接，評估生成嵌入在保持拓?fù)浣Y(jié)構(gòu)方面的性能。

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

鏈接預(yù)測任務(wù)通常采用AUC（area under the curve）和AP（average precision）作為評價指標(biāo)：

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

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

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

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

3.5 聚類

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

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

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

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

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

3.6 異常檢測

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

異常檢測任務(wù)通常采用AUC 作為評價指標(biāo)。

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

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

3.7 可視化

可視化任務(wù)是對嵌入進(jìn)行降維和可視化，從而直觀地觀察原始圖中某些特征?？梢暬蝿?wù)通常是在有標(biāo)簽數(shù)據(jù)集上進(jìn)行的，不同標(biāo)簽的節(jié)點在二維空間中使用不同的顏色進(jìn)行標(biāo)記。由于嵌入中保留了原始圖的某種信息，可視化結(jié)果直接反映了二維空間中同一社群節(jié)點具有更加相似的特征。

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

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

4 未來研究方向

通過對傳統(tǒng)和新型圖嵌入方法的研究和分析，現(xiàn)階段的主要任務(wù)依然是提升模型對大規(guī)模和復(fù)雜圖數(shù)據(jù)的擴展性、創(chuàng)新模型方法和提高下游任務(wù)性能。據(jù)此，本章提出了未來工作的四個研究方向。

（1）面向大規(guī)模圖數(shù)據(jù)的嵌入模型

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

（2）面向復(fù)雜圖數(shù)據(jù)的嵌入模型

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

（3）改進(jìn)模型訓(xùn)練策略

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

（4）面向特定任務(wù)的嵌入模型

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

5 結(jié)束語

本文對圖嵌入文獻(xiàn)進(jìn)行了全面回顧，給出了圖嵌入有關(guān)定義，提出了靜態(tài)圖和動態(tài)圖模型通用的分類方法，對現(xiàn)有模型的核心策略以及靜態(tài)圖和動態(tài)圖模型理論相關(guān)性進(jìn)行了系統(tǒng)性分析。在應(yīng)用部分，介紹了圖嵌入常用數(shù)據(jù)集以及節(jié)點分類、鏈接預(yù)測等常見的機器學(xué)習(xí)任務(wù)，比較了不同模型的表現(xiàn)。最后，從圖數(shù)據(jù)、模型策略和應(yīng)用場景三方面提出了圖嵌入領(lǐng)域四個未來有希望的研究方向。