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

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

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

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

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

圖是復(fù)雜系統(tǒng)中常用的信息載體，可以表示現(xiàn)實(shí)中許多復(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é)點(diǎn)映射到低維空間，生成保留原始圖中某些重要信息的低維向量。目前，圖嵌入不僅在節(jié)點(diǎn)分類、鏈接預(yù)測(cè)、節(jié)點(diǎn)聚類、可視化等復(fù)雜網(wǎng)絡(luò)上的機(jī)器學(xué)習(xí)任務(wù)中獲得成功，還廣泛用于社交影響力建模、內(nèi)容推薦等現(xiàn)實(shí)任務(wù)。

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

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

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

1.1 問題定義

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

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

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

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

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

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

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

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

1.2 符號(hào)表示

本文常用符號(hào)及其定義見表1。

表1 符號(hào)及定義Table 1 Symbols and definitions

2 圖嵌入分類

本章提出一種新的分類方法，用于現(xiàn)有圖嵌入模型的分類。按照模型所使用的算法原理將靜態(tài)圖和動(dòng)態(tài)圖模型同時(shí)分為五大類：基于矩陣分解的圖嵌入、基于隨機(jī)游走的圖嵌入、基于自編碼器的圖嵌入、基于圖神經(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é)點(diǎn)關(guān)系矩陣獲得低維嵌入。不同的關(guān)系矩陣采用的分解方法不同，例如鄰接矩陣通常使用奇異值分解（singular value decomposition，SVD）的方法生成節(jié)點(diǎn)嵌入，而屬性矩陣通常使用特征值分解的方法。

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

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

局部線性映射（locally linear embedding，LLE）將每個(gè)節(jié)點(diǎn)表示為相鄰節(jié)點(diǎn)的線性組合，構(gòu)造鄰域保持映射（見圖6）。具體實(shí)現(xiàn)分為三步：（1）以某種度量方式（如歐氏距離）選擇個(gè)鄰近節(jié)點(diǎn)；（2）由個(gè)近鄰線性加權(quán)重構(gòu)節(jié)點(diǎn)，并最小化節(jié)點(diǎn)重建誤差獲得最優(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é)點(diǎn)與節(jié)點(diǎn)的權(quán)重系數(shù)。作為一種重要的降維算法，LLE 在降維時(shí)能夠保持樣本的局部特征，并通過稀疏矩陣特征分解的方式適當(dāng)降低了計(jì)算復(fù)雜度。但是，該模型對(duì)值的選擇十分敏感，對(duì)最終的降維結(jié)果有極大影響。

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

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

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

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

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

在原始圖上，本征圖用于保留節(jié)點(diǎn)間有利關(guān)聯(lián)，懲罰圖用于保留節(jié)點(diǎn)間的不利關(guān)聯(lián)。為了綜合本征圖和懲罰圖的特點(diǎn)，NGE（non-negative graph embedding）引入非負(fù)矩陣分解（non-negative matrix factorization，NMF）生成嵌入表示。NMF 將數(shù)據(jù)矩陣分解成低階非負(fù)基矩陣和非負(fù)系數(shù)矩陣，并使用L1 損失作為目標(biāo)函數(shù)。在此基礎(chǔ)上，NGE 將和分成兩部分：=[,]；=[,]。由于(,)和(,)是互補(bǔ)空間，可以通過疊加的方式重構(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é)點(diǎn)在嵌入空間中盡可能地靠近。因此，LE 的目標(biāo)函數(shù)為：

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

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

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

圖8 基于矩陣分解的動(dòng)態(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)換為廣義特征值問題，使每個(gè)時(shí)刻生成的低維嵌入保留節(jié)點(diǎn)的高階相似度；動(dòng)態(tài)部分，DHPE 使用矩陣攝動(dòng)理論更新GSVD 的結(jié)果。此外，模型假設(shè)圖中節(jié)點(diǎn)數(shù)恒定（添加或刪除的節(jié)點(diǎn)為孤立節(jié)點(diǎn)），使每個(gè)時(shí)刻圖的變化轉(zhuǎn)化為邊的變化。DHPE 能夠在保持高階相似性的同時(shí)更新節(jié)點(diǎn)嵌入，其增量計(jì)算方案有效提升了動(dòng)態(tài)模型的計(jì)算效率。

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

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

MF通過構(gòu)造攜帶重要特征的矩陣因子，使?jié)撛诘腘MF 特征有效地表達(dá)動(dòng)態(tài)信息。為了充分利用不同時(shí)刻的拓?fù)湫畔?，MF 對(duì)嵌入空間的鄰接關(guān)系矩陣進(jìn)行整合，找到在各個(gè)時(shí)刻一致的嵌入矩陣和系數(shù)矩陣，并通過最小化Frobenius 范數(shù)使各時(shí)刻Y和、W和差異最小?；贜MF 加權(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ù)實(shí)例傳播到無標(biāo)簽的數(shù)據(jù)實(shí)例，最后將控制信息量的平滑度項(xiàng)與Semi-NMF 相結(jié)合，優(yōu)化模型參數(shù)生成嵌入。DWSF 將有限的監(jiān)督信息合并為類別標(biāo)簽，在每次迭代中動(dòng)態(tài)更新，大幅提升了模型在分類任務(wù)上的表現(xiàn)。

2.2 基于隨機(jī)游走的圖嵌入

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 基于自編碼器的圖嵌入

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GCN 通常應(yīng)用于固定圖的直推式表示學(xué)習(xí)，GraphSAGE 將其擴(kuò)展到歸納式無監(jiān)督學(xué)習(xí)的任務(wù)中，利用節(jié)點(diǎn)特征（例如文本屬性、節(jié)點(diǎn)度）學(xué)習(xí)不可見節(jié)點(diǎn)的嵌入表示。GraphSAGE 不是為每個(gè)節(jié)點(diǎn)訓(xùn)練單獨(dú)的嵌入，而是通過采樣和聚合節(jié)點(diǎn)的局部鄰域特征訓(xùn)練聚合器函數(shù)，同時(shí)學(xué)習(xí)每個(gè)節(jié)點(diǎn)鄰域的拓?fù)浣Y(jié)構(gòu)及特征分布，生成嵌入表示（見圖18）。相比GCN，GraphSAGE 使用無監(jiān)督損失函數(shù)強(qiáng)制鄰近節(jié)點(diǎn)具有相似表示，遠(yuǎn)距離節(jié)點(diǎn)具有不同的表示。在給定下游任務(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ǔ)上引入注意力機(jī)制，對(duì)鄰近節(jié)點(diǎn)特征加權(quán)求和，分配不同的權(quán)值。針對(duì)單個(gè)節(jié)點(diǎn)，GAT使用self-attention獲得注意力系數(shù)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.5 基于其他方法的圖嵌入

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

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

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

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

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

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

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

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

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

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

圖嵌入可以解釋為生成圖數(shù)據(jù)的向量表示，用于洞察圖的某種特性。表2 和表3 歸納了主要靜態(tài)圖嵌入和動(dòng)態(tài)圖嵌入的模型策略。基于矩陣分解的方法只有包含特定的目標(biāo)函數(shù)，才能學(xué)習(xí)相應(yīng)的圖結(jié)構(gòu)和信息?；陔S機(jī)游走的方法可以通過改變參數(shù)來控制游走方式，還可以與其他模型疊加提升性能?；贏E 和GNN 的方法利用近似定理廣泛建模，使模型能夠同時(shí)學(xué)習(xí)節(jié)點(diǎn)屬性、拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)標(biāo)簽等信息。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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é)點(diǎn)表示用戶，用戶之間的消息通信表示邊緣。每條邊攜帶的時(shí)間指示用戶何時(shí)通信。

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

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

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

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

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

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

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

3.3 節(jié)點(diǎn)分類

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

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

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

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

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

在CiteSeer 數(shù)據(jù)集上的靜態(tài)圖節(jié)點(diǎn)分類實(shí)驗(yàn)中，同時(shí)使用節(jié)點(diǎn)特征和網(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 使用多個(gè)局部GCN 濾波器進(jìn)行特征提取，使模型捕捉到節(jié)點(diǎn)特征的不同方面，從而進(jìn)一步提升了模型性能。同樣突出的GraphAIR 模型分別對(duì)鄰域聚合和鄰域交互進(jìn)行建模，與原始的GCN 和GAT 模型結(jié)合使用，提升基礎(chǔ)模型的性能。各模型靜態(tài)圖節(jié)點(diǎn)分類性能見圖25。

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

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

表6 動(dòng)態(tài)圖節(jié)點(diǎn)分類性能對(duì)比Table 6 Performance comparison of dynamic graph node classification %

3.4 鏈接預(yù)測(cè)

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

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

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

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

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

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

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

3.5 聚類

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

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

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

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

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

3.6 異常檢測(cè)

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

異常檢測(cè)任務(wù)通常采用AUC 作為評(píng)價(jià)指標(biāo)。

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

圖27 異常檢測(cè)性能對(duì)比Fig.27 Performance comparison of anomaly detection

3.7 可視化

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

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

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

4 未來研究方向

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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