劉華玲，張國(guó)祥，馬俊

（上海對(duì)外經(jīng)貿(mào)大學(xué)統(tǒng)計(jì)與信息學(xué)院，上海 201600）

0 引 言

現(xiàn)實(shí)世界如同一個(gè)完整的復(fù)雜系統(tǒng)，每時(shí)每刻展示著各主體間的聯(lián)系與交互，而由節(jié)點(diǎn)與連邊構(gòu)成的圖網(wǎng)絡(luò)可以有效儲(chǔ)存和表示世界各實(shí)體間的屬性標(biāo)簽及交互信息，自然契合現(xiàn)實(shí)世界的系統(tǒng)特點(diǎn)。因此，利用圖來(lái)研究和表示現(xiàn)實(shí)世界中的系統(tǒng)性問題具有合理性和可行性[1]。隨著社會(huì)的發(fā)展與演化，在多種場(chǎng)景中已形成客觀的真實(shí)網(wǎng)絡(luò)，如交通網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)和生物遺傳網(wǎng)絡(luò)等，這些均以圖數(shù)據(jù)的形式表示與存儲(chǔ)。

近年來(lái)，圖數(shù)據(jù)呈現(xiàn)海量、異構(gòu)、動(dòng)態(tài)、非線性且高維發(fā)展的態(tài)勢(shì)，機(jī)器學(xué)習(xí)模型的非線性對(duì)數(shù)據(jù)維度的選擇具有較高的要求，面對(duì)日趨復(fù)雜的信息網(wǎng)絡(luò)，能否進(jìn)行有效合理的嵌入表達(dá)成為學(xué)術(shù)界未來(lái)研 究 的 重 點(diǎn)[2]。 圖 嵌 入（graph embedding，也 稱network embedding）是解決如何將現(xiàn)實(shí)世界的信息抽象表征為可輸入算法模型的向量或張量的一種技術(shù)方法[3]，是一種將圖數(shù)據(jù)（高維稀疏的矩陣）映射為低維稠密向量的過(guò)程，研究要解決的是找到一種合理的圖嵌入方法，將復(fù)雜的高維數(shù)據(jù)表示為低維向量集[4]。此類向量集可供下游的機(jī)器學(xué)習(xí)模型使用，進(jìn)而解決如社區(qū)發(fā)現(xiàn)、推薦系統(tǒng)[5-6]、連接預(yù)測(cè)[7-8]、節(jié)點(diǎn)分類或聚類等實(shí)際應(yīng)用問題。

本文的主要貢獻(xiàn)：從基于降維方法的圖嵌入[1]、矩陣分解的圖嵌入[6]、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的圖嵌入、神經(jīng)網(wǎng)絡(luò)的圖嵌入、生成式對(duì)抗網(wǎng)絡(luò)的圖嵌入以及超圖網(wǎng)絡(luò)的圖嵌入對(duì)該領(lǐng)域前沿算法的基本原理及核心思想進(jìn)行了梳理和分類研究，結(jié)合近年來(lái)學(xué)術(shù)界、工業(yè)界的前沿研究，對(duì)圖嵌入的實(shí)際應(yīng)用進(jìn)行了歸納，給出了圖嵌入算法的性能評(píng)價(jià)指標(biāo)和常用測(cè)評(píng)數(shù)據(jù)集，并對(duì)圖嵌入算法的發(fā)展進(jìn)行了總結(jié)和展望。

1 圖嵌入算法的基本定義及原理

1.1 基本定義

1.2 原 理

圖嵌入算法是一種將圖數(shù)據(jù)映射為低維稠密向量集的過(guò)程，其中作為輸入的圖數(shù)據(jù)屬于高維稀疏的抽象空間，經(jīng)映射后，圖數(shù)據(jù)中節(jié)點(diǎn)或連邊等信息將在低維稠密的空間中嵌入表示[7]，故通過(guò)圖嵌入，將海量的高維、異構(gòu)、動(dòng)態(tài)且復(fù)雜的圖數(shù)據(jù)[3]處理為可高效輸入機(jī)器學(xué)習(xí)算法的嵌入向量或向量集。根據(jù)輸出粒度的不同，圖嵌入的輸出結(jié)果包括節(jié)點(diǎn)嵌入、連邊嵌入、混合嵌入和全圖嵌入四類，嵌入后的向量或向量集仍帶有圖的拓?fù)浣Y(jié)構(gòu)、連邊關(guān)系、權(quán)重和子圖等屬性信息。此類向量集主要應(yīng)用于節(jié)點(diǎn)分類、節(jié)點(diǎn)聚類、鏈接預(yù)測(cè)、圖重構(gòu)、圖信息可視化、社區(qū)發(fā)現(xiàn)和推薦系統(tǒng)等，如圖1所示。

圖1 圖嵌入原理Fig.1 Graph embedding principle

2 模型與算法

早期，圖數(shù)據(jù)量小、結(jié)構(gòu)常規(guī)且維度較低，往往將圖嵌入作為一種降維技術(shù)。首先將基于鄰域的一組n個(gè)D維節(jié)點(diǎn)構(gòu)建為一個(gè)相似圖，然后將圖的節(jié)點(diǎn)嵌入至d（d?D）維向量空間，使相互鏈接的節(jié)點(diǎn)彼此更靠近，如拉普拉斯特征圖和局部線性嵌入（locally linear embedding，LLE）[1]，主要用于解決可伸縮性，其時(shí)間復(fù)雜度為O（|V|2）[8]。

2010年后，圖嵌入研究轉(zhuǎn)向可擴(kuò)展的技術(shù)領(lǐng)域，以迎合并較好地利用實(shí)際網(wǎng)絡(luò)數(shù)據(jù)的稀疏性。文獻(xiàn)[1]運(yùn)用鄰接矩陣的近似分解，提出了大規(guī)模信息網(wǎng)絡(luò)嵌入方法（large-scale information network embedding，LINE）[1]，嘗試通過(guò)保留一階和二階鄰近度，擴(kuò)展LINE，通過(guò)通用的奇異值分解（singular value decomposition，SVD）處理相似度矩陣，從而保留其高階鄰近度[6]。結(jié)構(gòu)化深度網(wǎng)絡(luò)嵌入（structural deep network embedding，SDNE）通過(guò)自動(dòng)編碼器嵌入節(jié)點(diǎn)并捕獲其高度非線性的依存關(guān)系[9]。此類可伸縮方法的時(shí)間復(fù)雜度為O（|V|2）。

近年來(lái)，隨著大數(shù)據(jù)、云計(jì)算、物聯(lián)網(wǎng)等新興技術(shù)的不斷發(fā)展，海量數(shù)據(jù)的產(chǎn)生和利用場(chǎng)景的不斷變化，學(xué)術(shù)及工業(yè)界針對(duì)不同的數(shù)據(jù)應(yīng)用場(chǎng)景提出了不同的圖嵌入算法與模型，共分六類：（1）基于降維方法的圖嵌入；（2）基于矩陣分解的圖嵌入；（3）基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的圖嵌入；（4）基于神經(jīng)網(wǎng)絡(luò)的圖嵌入；（5）基于生成式對(duì)抗網(wǎng)絡(luò)的圖嵌入；（6）基于超圖網(wǎng)絡(luò)的圖嵌入。見表1。

表1 嵌入模型概況Table 1 Embedded model overview

2.1 基于降維方法的圖嵌入算法

經(jīng)典的圖嵌入算法是將高維稀疏的圖數(shù)據(jù)的維數(shù)降至低維稠密空間進(jìn)行表示，降維后仍需保留原始數(shù)據(jù)的屬性，通?？煞譃榫€性和非線性2種[10]。

2.1.1 線性降維方法

最具代表性的線性降維方法——主成分分析（principal component analysis，PCA）[11]是一種使用較廣的無(wú)監(jiān)督降維方法，即用原始數(shù)據(jù)中方差較大的主成分代表原始數(shù)據(jù)的重要結(jié)構(gòu)信息，方差較小的代表噪聲，因此，經(jīng)PCA計(jì)算后的低維表示最大化了原始數(shù)據(jù)的差異[12]。通過(guò)求解特征值w，得到線性變換矩陣W∈RD×d，以提取最大方差的權(quán)重向量，降維結(jié)果中各主成分呈正交關(guān)系，可通過(guò)分解矩陣協(xié)方差的特征求解[13]。

文獻(xiàn)[14]提出的線性判別分析（linear discriminant analysis，LDA）是一種有監(jiān)督的降維方法，數(shù)據(jù)集中的每個(gè)樣本均為有類別的輸出，且假設(shè)數(shù)據(jù)集中每個(gè)類別均呈高斯分布，然后通過(guò)使數(shù)據(jù)的類間分布和類內(nèi)分布間的比值最大化，求得線性投影矩陣W∈RD×d。而多維縮放（multidimensional scaling，MDS）[15]模型是一種在低維空間展示“距離”數(shù)據(jù)結(jié)構(gòu)的流行學(xué)習(xí)方法，保留了數(shù)據(jù)的空間距離，得到相異性矩陣D，在盡可能保留數(shù)據(jù)相異性的前提下生成低維向量表示[16]。

2.1.2 非線性降維方法

非線性降維（nonlinear dimensionality redection，NLDR）[17]方法可用于流行學(xué)習(xí)，自動(dòng)學(xué)習(xí)數(shù)據(jù)的非線性結(jié)構(gòu)，文獻(xiàn)[18]提出的等距特征映射（isometric feature mapping，Isomap）也稱等度量映射，能精確保留所有特征向量間的距離，可應(yīng)用于降維、可視化等領(lǐng)域。

LLE[1]作為流行學(xué)習(xí)中經(jīng)典的非線性降維方法，可使降維后的數(shù)據(jù)集較好地保留原始數(shù)據(jù)的流行結(jié)構(gòu)和局部特征向量間的線性結(jié)構(gòu)；內(nèi)核法（kernel methods）[19]是一種與Isomap、LLE相當(dāng)?shù)姆蔷€性降維方法，可用于僅需計(jì)算數(shù)據(jù)對(duì)間內(nèi)積的場(chǎng)合，其優(yōu)點(diǎn)是使原始空間中線性不可分的數(shù)據(jù)在新的高維空間中分離，其中內(nèi)核PCA法通常用于多項(xiàng)式或高斯內(nèi)核的非線性降維。

2.2 基于矩陣分解的圖嵌入算法

基于矩陣分解的圖嵌入算法常以矩陣的形式表示圖的屬性（如節(jié)點(diǎn)的成對(duì)相似性），并進(jìn)行矩陣分解得到節(jié)點(diǎn)的嵌入式表達(dá)[1]。其中拉普拉斯特征圖法[20]通過(guò)最小化成本函數(shù)Y，確保在流形上彼此接近的點(diǎn)映射至低維空間后仍相互接近。為控制映射后的誤差，對(duì)相似映射后距離變遠(yuǎn)的節(jié)點(diǎn)以更大懲罰。

節(jié)點(diǎn)鄰近矩陣分解法[21]則通過(guò)最小化目標(biāo)函數(shù)min|W-YYTc|，并利用矩陣分解計(jì)算低維空間中的節(jié)點(diǎn)鄰近度，其中，W為節(jié)點(diǎn)間的鄰近矩陣，Y為節(jié)點(diǎn)的嵌入，Yc為上下文節(jié)點(diǎn)的嵌入。此外，HSCA[22]模型是對(duì)TADW模型的改進(jìn)，基于skipgram和hierarchical softmax學(xué)習(xí)分布式單詞表示，HSCA的目標(biāo)函數(shù)式為

其中，第1項(xiàng)，使TADW的矩陣分解誤差最小化；第2項(xiàng)，對(duì)W和H施加低級(jí)約束，并用參數(shù)λ進(jìn)行協(xié)調(diào)；最后的正則化項(xiàng)，強(qiáng)制網(wǎng)絡(luò)中鄰近點(diǎn)間的結(jié)構(gòu)同質(zhì)化。該方法將使連接的節(jié)點(diǎn)在網(wǎng)絡(luò)表示中彼此更接近。

基于DeepWalk改進(jìn)的算法，其概率模型和目標(biāo)函數(shù)普遍難以解釋如何保留圖的高階相似性。為解決此類問題，文獻(xiàn)[23]提出了GraRep模型，通過(guò)鄰接矩陣相乘k次得到第k階過(guò)度矩陣Ak，定義過(guò)度概率，并由skip-gram模型和負(fù)采樣方法定義損失函數(shù)，使嵌入結(jié)果保留了嵌入空間中圖的高階相似性。而HOPE[6]模型在計(jì)算高階相似性時(shí)保留了非對(duì)稱傳遞性，非對(duì)稱傳遞性指有向圖之間特定的相關(guān)性。文獻(xiàn)[6]對(duì)幾種高階近似性的計(jì)算方法，如卡茲指數(shù)法[24]、基于 PageRank的方法、共同鄰居法和Adamic-Adar法進(jìn)行了實(shí)驗(yàn)，其中節(jié)點(diǎn)i的嵌入表達(dá)Vi可通過(guò)分解鄰近矩陣S求得，再用SVD方法等選取前K個(gè)特征值，對(duì)矩陣S進(jìn)行分解。

2.3 基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的圖嵌入算法

較著名的圖嵌入算法為 DeepWalk[25]，借鑒自然語(yǔ)言處理中重要的詞嵌入算法word2vec，通過(guò)隨機(jī)游走將圖嵌入轉(zhuǎn)化為詞嵌入問題。從每個(gè)節(jié)點(diǎn)出發(fā)若干次，用均勻采樣方式選擇當(dāng)前節(jié)點(diǎn)的鄰接節(jié)點(diǎn)，并作為下一步的節(jié)點(diǎn)進(jìn)行隨機(jī)游走，當(dāng)游走路徑達(dá)到規(guī)定長(zhǎng)度時(shí)，停止本次游走，然后將這些節(jié)點(diǎn)序列作為訓(xùn)練樣本輸入skip-gram模型進(jìn)行訓(xùn)練，得到節(jié)點(diǎn)的嵌入表達(dá)。因此，可將DeepWalk視為一種連接序列嵌入和圖嵌入的過(guò)渡方法，其目標(biāo)是最大化隨機(jī)游走序列S中頂點(diǎn)對(duì)的平均對(duì)數(shù)概率，使具有相似鄰域（具有較大的二階相似度）的節(jié)點(diǎn)共享相似的嵌入。其目標(biāo)函數(shù)為

文獻(xiàn)[26-28]證明了DeepWalk算法相當(dāng)于矩陣分解M=WT×H，M∈ R|V|×|V|中的每個(gè)Mij表示頂點(diǎn)Vi在固定步數(shù)內(nèi)可到達(dá)頂點(diǎn)Vj的平均概率的對(duì)數(shù)，W∈Rk×|V|為頂點(diǎn)的嵌入表示，但H∈Rk×|V|中的信息很少被用于經(jīng)典的DeepWalk模型。

DeepWalk采用深度優(yōu)先采樣（depth-first sampling，DFS）策略，即從源節(jié)點(diǎn)開始以距離遞增的方式依次采樣產(chǎn)生節(jié)點(diǎn)序列，其得到的節(jié)點(diǎn)序列具有同質(zhì)性，即以距離作為節(jié)點(diǎn)間相似性的度量。與DFS策略相反，廣度優(yōu)先采樣（breadth-first sampling，BFS）策略是從源節(jié)點(diǎn)開始，探索當(dāng)前深度所有鄰居節(jié)點(diǎn)的結(jié)構(gòu)性，用節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置和結(jié)構(gòu)表示相似性。斯坦福大學(xué)在DeepWalk基礎(chǔ)上推出了 node2vec[30]。node2vec通過(guò)調(diào)整隨機(jī)游走權(quán)重，在同質(zhì)性和結(jié)構(gòu)性間進(jìn)行權(quán)衡，其中提出的概率模型，通過(guò)設(shè)立節(jié)點(diǎn)間的跳轉(zhuǎn)概率控制對(duì)BFS和DFS的傾向性。圖2顯示的為node2vec算法從節(jié)點(diǎn)t跳轉(zhuǎn)至節(jié)點(diǎn)v后下一步以節(jié)點(diǎn)v為起點(diǎn)繼續(xù)跳轉(zhuǎn)的概率。

圖2 Node2vec算法節(jié)點(diǎn)跳轉(zhuǎn)原理Fig.2 Node2vec algorithm node jump principle

從節(jié)點(diǎn)v跳轉(zhuǎn)至下一節(jié)點(diǎn)x的概率為

其中，ωvx為邊Vx的權(quán)重，

dtx為節(jié)點(diǎn)t到節(jié)點(diǎn)x的距離，返回參數(shù)p和進(jìn)出參數(shù)q共同控制隨機(jī)游走的傾向性，其中，p越小，隨機(jī)游走回節(jié)點(diǎn)t的可能性越大，即算法更注重表達(dá)網(wǎng)絡(luò)的同質(zhì)性；q越小，隨機(jī)游走到遠(yuǎn)方節(jié)點(diǎn)的可能性越大，即更注重表達(dá)網(wǎng)絡(luò)的結(jié)構(gòu)性。反之，當(dāng)前節(jié)點(diǎn)更可能在附近節(jié)點(diǎn)游走，同時(shí)node2vec所體現(xiàn)的網(wǎng)絡(luò)的同質(zhì)性和結(jié)構(gòu)性在推薦系統(tǒng)中可得到直觀解釋。

LINE[1]是一種基于鄰域相似假設(shè)的算法，與DeepWalk使用DFS構(gòu)造鄰域不同，LINE可看作是一種用廣度優(yōu)先搜索（breath first search，BFS）構(gòu)造鄰域算法。在現(xiàn)實(shí)世界網(wǎng)絡(luò)中，相互聯(lián)系的節(jié)點(diǎn)通常表現(xiàn)為較相似或向量距離接近，LINE算法將其定義為一階近鄰，用于描述相鄰頂點(diǎn)之間的局部相似度；二階近鄰則用2個(gè)節(jié)點(diǎn)間的共同鄰居度量，描述節(jié)點(diǎn)與鄰域的關(guān)系。LINE算法分別對(duì)所有具有一階近鄰關(guān)系和二階近鄰關(guān)系的節(jié)點(diǎn)對(duì)進(jìn)行概率建模，通過(guò)最小化其概率分布和經(jīng)驗(yàn)分布的KL散度，得到2個(gè)嵌入；由不同目標(biāo)函數(shù)訓(xùn)練的2個(gè)嵌入向量連接每個(gè)頂點(diǎn)，可更好地表示輸入圖。LINE通過(guò)捕捉網(wǎng)絡(luò)中的一階近鄰關(guān)系和二階近鄰關(guān)系，更完整地描述網(wǎng)絡(luò)，其適用于有向圖、無(wú)向圖、有權(quán)圖和無(wú)權(quán)圖。

GraphSAGE[1]是一種利用頂點(diǎn)屬性信息高效產(chǎn)生未知頂點(diǎn)向量進(jìn)行嵌入的一種歸納式（inductive）學(xué)習(xí)框架。通過(guò)學(xué)習(xí)對(duì)鄰居頂點(diǎn)進(jìn)行聚合表示的函數(shù)產(chǎn)生目標(biāo)頂點(diǎn)的嵌入向量，其運(yùn)行流程可分為頂點(diǎn)采樣、信息聚合和向量表達(dá)3個(gè)步驟，該模型訓(xùn)練的聚合函數(shù)可將本地鄰域的特征（如文本屬性、節(jié)點(diǎn)特征）整合后傳遞給目標(biāo)節(jié)點(diǎn)Vi，并更新節(jié)點(diǎn)Vi的隱藏狀態(tài)，此方法可利用節(jié)點(diǎn)的鄰域信息補(bǔ)充損失的局部結(jié)構(gòu)信息，提升表示向量的準(zhǔn)確性。

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

2010年后，RNNs和CNNs等神經(jīng)網(wǎng)絡(luò)模型快速發(fā)展，并試圖將其推廣應(yīng)用于圖模型。首先將CNN模型作為基礎(chǔ)算法，或采用專為歐幾里得空間設(shè)計(jì)的原始CNN模型，通過(guò)格式化輸入的圖模型，以適應(yīng)原始CNN模型的輸入要求，或?qū)⑸疃壬窠?jīng)網(wǎng)絡(luò)模型泛化為非歐幾里得圖。

其中，SDNE[26]模型和 node2vec[29]是同時(shí)期兩項(xiàng)并列的工作，均發(fā)表于2016年的KDD會(huì)議論文集，可看作是LINE的擴(kuò)展，首次將深度學(xué)習(xí)應(yīng)用于網(wǎng)絡(luò)表示學(xué)習(xí)。SDNE中的相似度定義與LINE相同，使用自動(dòng)編碼器結(jié)構(gòu)同時(shí)優(yōu)化一階和二階相似度，而LINE模型則分別進(jìn)行優(yōu)化，學(xué)習(xí)得到的向量表示能保留局部和全局結(jié)構(gòu)，并對(duì)稀疏網(wǎng)絡(luò)具有魯棒性，結(jié)構(gòu)如圖3所示。

圖3 SDNE模型結(jié)構(gòu)Fig.3 SDNE model structure

GCN模型[27]可對(duì)任意大小和形狀的圖進(jìn)行端到端學(xué)習(xí)，用卷積算子并采取迭代聚合方法對(duì)節(jié)點(diǎn)的鄰近節(jié)點(diǎn)進(jìn)行嵌入表示，該方法已廣泛用于圖結(jié)構(gòu)化數(shù)據(jù)的半監(jiān)督學(xué)習(xí)。由于GCN模型通常只有2個(gè)卷積層，因此無(wú)法很好地解釋其工作原理。

研究表明，GCN模型是拉普拉斯平滑的一種特殊形式[30-31]，模型效果良好，若使用2個(gè)以上卷積層，將導(dǎo)致過(guò)度平滑，令節(jié)點(diǎn)的特征相似，分離困難。

帶有連邊信息的增強(qiáng)圖嵌入（enhanced graph embedding with side information，EGES）[32]模型于2018年由阿里巴巴推出，其基本思想是在嵌入過(guò)程中引入帶權(quán)重的補(bǔ)充信息，解決冷啟動(dòng)問題。該模型是為解決推薦問題而推出的一款基于DeepWalk算法的改進(jìn)模型，面向推薦系統(tǒng)找回階段，其核心任務(wù)是計(jì)算物品間的相似度。文獻(xiàn)[32]根據(jù)用戶歷史行為構(gòu)建物品圖，然后用DeepWalk學(xué)習(xí)每個(gè)物品的嵌入表示，即基圖嵌入（base graph embedding，BGE），同時(shí)為解決少量或無(wú)交互行為物品的準(zhǔn)確表示問題，提出了使用連邊信息增強(qiáng)其學(xué)習(xí)表示過(guò)程，并針對(duì)不同連邊的貢獻(xiàn)度，提出了一種用于學(xué)習(xí)帶有連邊信息的嵌入表示的加權(quán)機(jī)制。EGES并無(wú)復(fù)雜的理論創(chuàng)新，但給出了能融合多種嵌入表示的算法，解決了因某類信息缺失出現(xiàn)冷啟動(dòng)的問題，是一種實(shí)用性較強(qiáng)的圖嵌入算法。

2.5 基于生成式對(duì)抗網(wǎng)絡(luò)的圖嵌入算法

生成式對(duì)抗網(wǎng)絡(luò)（generative adversarial network，GAN）[33]是一種非監(jiān)督學(xué)習(xí)算法，通過(guò) 2 個(gè)神經(jīng)網(wǎng)絡(luò)之間相互對(duì)抗的方式進(jìn)行學(xué)習(xí)。自2014年GAN問世以來(lái)，其在計(jì)算機(jī)視覺等領(lǐng)域廣受關(guān)注，在其他領(lǐng)域的應(yīng)用研究相對(duì)較少，2019年后，逐漸將GAN思想應(yīng)用于圖嵌入表達(dá)。其中，文獻(xiàn)[31]將圖嵌入學(xué)習(xí)分為生成式（generative）和判別式（discriminative）2種，并提出GraphGAN模型，該模型包含判別器D(v，vc；θD)和生成器G(v∣vc；θG)，借鑒GAN中常見的對(duì)抗機(jī)制，即生成器G盡可能地逼近ptrue(v∣vc)，找到與vc的相鄰節(jié)點(diǎn)極相似的節(jié)點(diǎn)，以欺騙判別器D；反之，判別器D則會(huì)檢測(cè)給定的節(jié)點(diǎn)v是由生成器生成的還是vc的真實(shí)鄰近節(jié)點(diǎn)。故GraphGAN模型的核心是目標(biāo)函數(shù)：

GraphGAN[30]模型，為實(shí)現(xiàn)圖中所有節(jié)點(diǎn)的嵌入，對(duì)每個(gè)節(jié)點(diǎn)做抽樣正樣本和生成負(fù)樣本操作，但這在現(xiàn)實(shí)大型網(wǎng)絡(luò)中難以實(shí)現(xiàn)。文獻(xiàn)[31]提出的NetRA模型可解決當(dāng)抽樣較稀疏時(shí)圖嵌入過(guò)擬合的問題，通過(guò)引入GAN模型的正則項(xiàng)，使編碼器提取到更有用的信息。模型框架如圖4所示，包括自動(dòng)編碼器、GAN和圖嵌入三部分，其中，文獻(xiàn)[31]用LSTM[34]作為編碼器，在對(duì)GAN訓(xùn)練時(shí)需將正負(fù)樣本間的差異反饋給編碼器，幫助編碼器提取更有效的信息以區(qū)分偽樣本，避免編碼器出現(xiàn)過(guò)擬合[35]。圖嵌入部分通過(guò)保留節(jié)點(diǎn)與節(jié)點(diǎn)間的連邊信息獲得局部的連接關(guān)系，NetRA模型并不只有一個(gè)GAN結(jié)構(gòu)，而是將GAN當(dāng)作正則項(xiàng)的一部分嵌入模型得到節(jié)點(diǎn)的表征，這為GAN模型的應(yīng)用提供了不同思路[36]。

圖4 NetRA模型框架Fig.4 NetRA model framework

2.6 基于超圖（hyper-graph）網(wǎng)絡(luò)的圖嵌入算法

近年來(lái)，隨著社交網(wǎng)絡(luò)圖嵌入應(yīng)用的激增，簡(jiǎn)單的圖網(wǎng)絡(luò)已不足以表示真實(shí)網(wǎng)絡(luò)中的復(fù)雜信息，真實(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)間的關(guān)系遠(yuǎn)較頂點(diǎn)到頂點(diǎn)的連邊關(guān)系復(fù)雜，與傳統(tǒng)的圖網(wǎng)絡(luò)不同，超圖網(wǎng)絡(luò)中邊的度可能大于2，且所有相關(guān)節(jié)點(diǎn)通過(guò)超邊連接形成超節(jié)點(diǎn)，一個(gè)超圖可用尺寸為|V|×|E|的入射矩陣H表示[37]。對(duì)每對(duì)超級(jí)節(jié)點(diǎn)均通過(guò)共享的事件頂點(diǎn)建立連接。因此，超圖可更好地表示網(wǎng)絡(luò)圖中的社區(qū)結(jié)構(gòu)，超邊的這些特性使得超圖更具挑戰(zhàn)性，表2為圖與超圖的特性對(duì)比。超圖的嵌入表示學(xué)習(xí)是近年來(lái)的研究熱點(diǎn)，其為社會(huì)網(wǎng)絡(luò)建模提供了有力的工具，由于超圖算法可用于許多其他方式難以實(shí)現(xiàn)的嵌入應(yīng)用場(chǎng)景，且超圖可看作是簡(jiǎn)單圖的一種變體，只要對(duì)傳統(tǒng)圖的嵌入算法稍加修改便可將其應(yīng)用于超圖嵌入[38-39]。

表2 圖與超圖的特性對(duì)比Table 2 Comparison of characteristics between graphs and hyper-graphs

受GCN中圖卷積的啟發(fā)，HGNN[38]將光譜卷積應(yīng)用于超圖，通過(guò)半監(jiān)督的節(jié)點(diǎn)分類任務(wù)訓(xùn)練網(wǎng)絡(luò)，可在卷積層的輸出中獲得節(jié)點(diǎn)表示，模型結(jié)構(gòu)體系如圖5所示，超圖卷積由超圖Laplacian[40]衍生而來(lái)，其為正半定性矩陣，特征值為相應(yīng)的頻率，每層的頻譜卷積為

其中，X為每層的隱藏嵌入，Dv和De為對(duì)角矩陣，輸出分別為頂點(diǎn)和超邊的度。

圖5 圖和超圖圖示[38]Fig.5 Illustrations of graphs and hyper-graphs

2.7 圖嵌入算法對(duì)比分析

圖嵌入算法的特征分析見表3。經(jīng)典的降維方法已被廣泛用于圖嵌入算法，其原理較簡(jiǎn)單且容易理解，但大多模型無(wú)法表示高階相似度?；诰W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的算法不是對(duì)整圖進(jìn)行嵌入表示，而是對(duì)每個(gè)節(jié)點(diǎn)的鄰居信息進(jìn)行采樣，此類算法可以捕獲節(jié)點(diǎn)間的遠(yuǎn)距離關(guān)系，但嵌入后的網(wǎng)絡(luò)表示無(wú)法完全保留原始圖的全部結(jié)構(gòu)信息。

表3 圖嵌入算法特性分析Table 3 Characteristic analysis of graph embedding algorithms

基于矩陣分解的圖嵌入算法，根據(jù)節(jié)點(diǎn)間成對(duì)相似度的統(tǒng)計(jì)信息進(jìn)行圖嵌入，為捕獲全局結(jié)構(gòu)，一些算法考慮了全局節(jié)點(diǎn)的鄰近性，能細(xì)粒度地捕獲1～k階節(jié)點(diǎn)的相似度信息，其性能優(yōu)于基于隨機(jī)游走的深度學(xué)習(xí)算法，因隨機(jī)游走算法僅使用局部采樣窗口，易損失圖的全局結(jié)構(gòu)信息，但由于鄰接矩陣的構(gòu)造及特征分解計(jì)算和存儲(chǔ)復(fù)雜性更高，故此類圖嵌入算法并不適合大規(guī)模的圖數(shù)據(jù)場(chǎng)景，且算法可擴(kuò)展性較差。此外，LLE算法、圖拉普拉斯特征圖法僅保留了圖的一階相似度，在保持圖的二階甚至更高階相似度方面存在不足，易丟失原始圖的部分結(jié)構(gòu)信息。

深度學(xué)習(xí)在不同的圖嵌入算法中均表現(xiàn)良好，能從復(fù)雜的圖結(jié)構(gòu)中自動(dòng)識(shí)別有用的表示。例如，基于隨機(jī)游走的深度學(xué)習(xí)（如DeepWalk、node2vec等）可通過(guò)圖上的采樣路徑自動(dòng)利用鄰域結(jié)構(gòu)；無(wú)隨機(jī)游走的深度學(xué)習(xí)可對(duì)同構(gòu)圖（如GCN、GraphSAGE）中的可變尺寸子圖結(jié)構(gòu)進(jìn)行建模，作為有用的表示。同時(shí)，基于深度學(xué)習(xí)的圖嵌入算法能捕獲網(wǎng)絡(luò)中節(jié)點(diǎn)間的高階非線性關(guān)系。傳統(tǒng)線性降維算法無(wú)法保持圖的非線性結(jié)構(gòu)，基于深度神經(jīng)網(wǎng)絡(luò)的圖嵌入算法主要對(duì)節(jié)點(diǎn)表示間的非線性進(jìn)行建模，能捕獲網(wǎng)絡(luò)結(jié)構(gòu)和屬性中的非線性關(guān)系，并通過(guò)PPMI矩陣，避免大量無(wú)效節(jié)點(diǎn)的嵌入。其局限性為由于深度學(xué)習(xí)框架主要是基于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)搭建的，在模型參數(shù)優(yōu)化上嚴(yán)重依賴現(xiàn)代GPU的性能，且模型處理難，解釋性差，此外，適用BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練模型參數(shù)的時(shí)間復(fù)雜度較高。大型圖嵌入算法（如LGCL、GPNN）可處理大規(guī)模圖數(shù)據(jù)，適合嵌入包含數(shù)千甚至百萬(wàn)個(gè)節(jié)點(diǎn)的社交網(wǎng)絡(luò)，但仍存在限制。首先，時(shí)間復(fù)雜度很高；其次，從本質(zhì)上看圖都是動(dòng)態(tài)的，例如學(xué)術(shù)數(shù)據(jù)庫(kù)中的社交網(wǎng)絡(luò)圖和引文圖均在不斷變化中，且圖的結(jié)構(gòu)復(fù)雜性隨時(shí)間的推移不斷增加，故該類方法通常只適用于靜態(tài)圖；最后，要求對(duì)原始輸入數(shù)據(jù)進(jìn)行預(yù)處理，故需要適用性強(qiáng)的可擴(kuò)展性嵌入技術(shù)。

基于生成式對(duì)抗網(wǎng)絡(luò)的圖嵌入算法，在一個(gè)統(tǒng)一的模型中，利用圖結(jié)構(gòu)、節(jié)點(diǎn)屬性等圖結(jié)構(gòu)信息進(jìn)行嵌入學(xué)習(xí)，由于基于某些分布假設(shè)的觀測(cè)建模難以證明其合理性，且需要大量訓(xùn)練數(shù)據(jù)用以擬合，故此類算法對(duì)小規(guī)模圖數(shù)據(jù)的嵌入效果不佳。

基于超圖網(wǎng)絡(luò)的圖嵌入算法功能強(qiáng)大，可用于復(fù)雜、動(dòng)態(tài)的圖數(shù)據(jù)網(wǎng)絡(luò)，但實(shí)施困難，盡管可用其他途徑替代圖嵌入，但大多數(shù)算法尚處于“證明概念”的研究階段，未得到廣泛使用。內(nèi)核法可將圖映射為單個(gè)向量，所得向量適用于執(zhí)行整圖層面的應(yīng)用任務(wù)（如圖分類），由于只需枚舉圖中所包含的子圖結(jié)構(gòu)，因此較深度網(wǎng)絡(luò)模型更有效，但因在圖嵌入過(guò)程中會(huì)產(chǎn)生冗余的子圖結(jié)構(gòu)，令嵌入表示維度呈幾何級(jí)數(shù)增加。

3 圖嵌入算法的應(yīng)用

因圖嵌入算法可在時(shí)間與空間上有效解決圖數(shù)據(jù)的向量表示問題，所以圖嵌入算法將有利于后續(xù)圖數(shù)據(jù)分析。根據(jù)圖嵌入算法的輸入特征，將圖嵌入算法的應(yīng)用分為三類：與節(jié)點(diǎn)相關(guān)的應(yīng)用、與連邊相關(guān)的應(yīng)用和與整圖相關(guān)的應(yīng)用。

3.1 與節(jié)點(diǎn)相關(guān)的應(yīng)用

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

節(jié)點(diǎn)分類已被廣泛應(yīng)用于社區(qū)發(fā)現(xiàn)[41]、欺詐識(shí)別[42]和推薦系統(tǒng)[43-45]等任務(wù)，通過(guò)在標(biāo)記節(jié)點(diǎn)嵌入的結(jié)合上用分類器進(jìn)行訓(xùn)練實(shí)現(xiàn)，如M-NMF[44]、SDNE、HNE[45]等使用SVM分類器，DeepWalk、GraRep等用邏輯回歸作為分類模型，GCN則設(shè)計(jì)了一個(gè)統(tǒng)一框架共同優(yōu)化圖嵌入和節(jié)點(diǎn)分類的效果，學(xué)習(xí)每個(gè)節(jié)點(diǎn)分類的特定表示。

經(jīng)綜合平衡分析后，各試驗(yàn)因素的最優(yōu)組合確定為A3B1C2，即吸孔直徑按位，種箱相對(duì)于滾筒的角度為0°，輸送帶的速度為0.03m/s。此時(shí)空穴率為9.26%，單粒率為68.52%，重播率為22.22%。

3.1.2 節(jié)點(diǎn)聚類

節(jié)點(diǎn)聚類，即將圖中相似的節(jié)點(diǎn)分為一組，以獲得彼此相似的不同節(jié)點(diǎn)分組，其作為一種無(wú)監(jiān)督算法可用于節(jié)點(diǎn)標(biāo)簽不可用的情景?，F(xiàn)有的模型如M-NMF、GraRep、HNE、DNGR[46]等均將K-means作為聚類算法，文獻(xiàn)[47-48]同時(shí)采用優(yōu)化聚類和圖嵌入，以學(xué)習(xí)特定聚類的節(jié)點(diǎn)表示。節(jié)點(diǎn)聚類已被廣泛應(yīng)用于社區(qū)發(fā)現(xiàn)、欺詐識(shí)別、推薦系統(tǒng)和隱私保護(hù)[49]等任務(wù)。

3.2 與連邊相關(guān)的應(yīng)用

3.2.1 連接預(yù)測(cè)

圖嵌入可幫助推斷原始的圖結(jié)構(gòu)[50]。通常，原始的圖結(jié)構(gòu)并不完整，圖嵌入后的低維向量則有望保留不同級(jí)別的網(wǎng)絡(luò)鄰近度（如DeepWalk、LINE）以及不同尺度的結(jié)構(gòu)相似度（如GCN、struc2vec），因此，嵌入后的向量將對(duì)有關(guān)網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行編碼，以預(yù)測(cè)不完整圖中的丟失鏈接。已有文獻(xiàn)對(duì)圖嵌入驅(qū)動(dòng)連接預(yù)測(cè)大多基于同構(gòu)圖，涉及異構(gòu)圖連接預(yù)測(cè)的圖嵌入工作處理與解釋很困難。其中大型圖嵌入算法（如LGCL和GPNN）可處理大規(guī)模的圖數(shù)據(jù)。

3.2.2 三元組預(yù)測(cè)

三元組分類在知識(shí)圖譜中有特定應(yīng)用，如文獻(xiàn)[51-53]均基于三元組的預(yù)測(cè)完成知識(shí)圖譜的相關(guān)任務(wù)，判斷未知三元組〈h；r；t〉的分類是否正確，即預(yù)測(cè)h與t之間的關(guān)系是否為r。

3.3 與圖相關(guān)的應(yīng)用

3.3.1 圖分類

圖分類是將類別標(biāo)簽分配給整幅圖，當(dāng)圖作為一個(gè)數(shù)據(jù)單位時(shí)，此應(yīng)用將變得十分重要，例如文獻(xiàn)[51]，每幅圖表示一種化合物，大多情況下，全圖嵌入往往用于計(jì)算整圖級(jí)別的相似度[49]。近年來(lái)，已出現(xiàn)為相似性圖[54]匹配節(jié)點(diǎn)嵌入，用每幅圖表示一組節(jié)點(diǎn)嵌入向量，進(jìn)而比較基于組節(jié)點(diǎn)的2幅嵌入圖。文獻(xiàn)[54]將圖分解為一組子結(jié)構(gòu)，然后將每個(gè)子結(jié)構(gòu)嵌入為向量表示，進(jìn)而通過(guò)子結(jié)構(gòu)間的相似性比較圖的相似性。

3.3.2 圖重構(gòu)

圖重構(gòu)與連接預(yù)測(cè)具有相似性，但二者應(yīng)用目的不同，評(píng)價(jià)標(biāo)準(zhǔn)也有差異。圖重構(gòu)，旨在重構(gòu)和修正圖數(shù)據(jù)中已存在的連邊，在實(shí)驗(yàn)中，將圖中所有節(jié)點(diǎn)作為訓(xùn)練集，將移除連邊后的節(jié)點(diǎn)作為測(cè)試集，利用預(yù)測(cè)結(jié)果對(duì)原始圖中節(jié)點(diǎn)對(duì)的連邊進(jìn)行重構(gòu)和修正；連接預(yù)測(cè)，旨在預(yù)測(cè)圖中未知或可能存在的連邊，從而補(bǔ)充節(jié)點(diǎn)對(duì)間的連邊。

3.3.3 圖拓?fù)湫畔⒖梢暬?/p>

圖拓?fù)湫畔⑼ǔＪ窃诘途S空間進(jìn)行的可視化表達(dá)，所有節(jié)點(diǎn)均可作為2D向量嵌入，如在2D空間中，用不同顏色繪制的向量表示節(jié)點(diǎn)類別，圖嵌入也可用于降維，可視化圖的拓?fù)湫畔ⅲㄈ鏟CA和t-SNE[55]），DeepWalk 通過(guò)可視化 Zachary′s空手道俱樂部網(wǎng)絡(luò)，說(shuō)明嵌入方法的優(yōu)點(diǎn)，LINE可視化DBLP網(wǎng)絡(luò)，表明LINE能將同一領(lǐng)域的作者聚在一起。將SDNE應(yīng)用于20-Newsgroup文檔相似性網(wǎng)絡(luò)，并基于主題對(duì)文檔進(jìn)行聚類。

4 實(shí)驗(yàn)數(shù)據(jù)集及評(píng)價(jià)指標(biāo)

4.1 實(shí)驗(yàn)數(shù)據(jù)集

根據(jù)不同的應(yīng)用領(lǐng)域選取相應(yīng)的實(shí)驗(yàn)數(shù)據(jù)集和評(píng)價(jià)指標(biāo)，常用的五類數(shù)據(jù)集為：（1）社交網(wǎng)絡(luò)，（2）合成網(wǎng)絡(luò)，（3）語(yǔ)言網(wǎng)絡(luò)，（4）協(xié)作網(wǎng)絡(luò)，（5）生物網(wǎng)絡(luò)，共計(jì)10個(gè)數(shù)據(jù)集，如表4所示。

表4 數(shù)據(jù)集概況Table 4 Data set overview

4.2 評(píng)價(jià)指標(biāo)

5 總結(jié)與展望

對(duì)近年來(lái)圖嵌入領(lǐng)域的研究進(jìn)行了全面梳理，首先，對(duì)圖嵌入進(jìn)行了定義并介紹了其基本原理，分析了基于降維方法的、基于矩陣分解的、基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息的、基于神經(jīng)網(wǎng)絡(luò)的、基于生成式對(duì)抗網(wǎng)絡(luò)的和基于超圖網(wǎng)絡(luò)的六類圖嵌入算法的原理、創(chuàng)新點(diǎn)和嵌入效果等，系統(tǒng)梳理了圖嵌入算法的發(fā)展歷程，對(duì)比分析了各算法的優(yōu)劣，介紹了圖嵌入算法的主要應(yīng)用領(lǐng)域，并根據(jù)應(yīng)用領(lǐng)域與頂點(diǎn)、連邊和整圖的關(guān)系將圖嵌入算法分為三類，還介紹了常用數(shù)據(jù)集及對(duì)應(yīng)的評(píng)價(jià)指標(biāo)。

雖然圖嵌入算法在處理高維稀疏數(shù)據(jù)、計(jì)算效率和嵌入效果上已有大幅提升，但面對(duì)不斷發(fā)展和變化的數(shù)據(jù)及應(yīng)用要求，圖嵌入算法仍需進(jìn)一步發(fā)展和創(chuàng)新。

5.1 動(dòng)態(tài)圖嵌入

動(dòng)態(tài)圖嵌入將是圖嵌入算法未來(lái)發(fā)展的重要方向。在現(xiàn)實(shí)世界中，圖數(shù)據(jù)是動(dòng)態(tài)的，如微博的社交圈、DBLP中的引文圖等每時(shí)每刻都在動(dòng)態(tài)變化中，圖的結(jié)構(gòu)（節(jié)點(diǎn)、連邊）信息亦呈動(dòng)態(tài)變化狀態(tài)。一方面，圖結(jié)構(gòu)隨時(shí)間不斷變化，新的節(jié)點(diǎn)或連邊不斷出現(xiàn)，老的節(jié)點(diǎn)或連邊可能消失；另一方面，可通過(guò)不斷變化的信息描述節(jié)點(diǎn)或連邊。已有文獻(xiàn)主要集中于靜態(tài)圖的嵌入研究，對(duì)動(dòng)態(tài)圖的嵌入研究很少。與靜態(tài)圖嵌入算法不同，動(dòng)態(tài)圖嵌入算法需具更強(qiáng)的伸縮性和增量性，以便有效處理圖的動(dòng)態(tài)變化，而現(xiàn)有的大多數(shù)嵌入算法不符合此要求，且動(dòng)態(tài)圖嵌入算法存在效率低下等問題，因此，如何對(duì)動(dòng)態(tài)圖有效進(jìn)行圖嵌入將是未來(lái)重要的研究方向之一[56]。

5.2 圖嵌入的可擴(kuò)展性

隨著社交網(wǎng)絡(luò)規(guī)模的快速增長(zhǎng)，其節(jié)點(diǎn)和連邊數(shù)以億計(jì)，針對(duì)更大規(guī)模和更高多樣性的圖網(wǎng)絡(luò)，如何有效、準(zhǔn)確地嵌入海量圖數(shù)據(jù)是面臨的一大挑戰(zhàn)。盡管深度神經(jīng)網(wǎng)絡(luò)模型具有最為先進(jìn)的功能，但依靠現(xiàn)代GPU查找最佳參數(shù)的效率較低，需要建立更合適的模型，一種可能是用前饋機(jī)器學(xué)習(xí)處理無(wú)BP的圖網(wǎng)絡(luò)，另一種是研究更優(yōu)的圖粗化或分區(qū)方法對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。

5.3 圖嵌入的可解釋性

最新的圖嵌入算法大多為用BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練并確定參數(shù)的CNNs模型，訓(xùn)練復(fù)雜度較高，其中Quickprop用于降低訓(xùn)練復(fù)雜度，由于用BP神經(jīng)網(wǎng)絡(luò)迭代訓(xùn)練模型耗時(shí)較長(zhǎng)且對(duì)硬件的要求較高，最近，出現(xiàn)了有關(guān)神經(jīng)網(wǎng)絡(luò)模型的可解釋性研究[54，56]，文獻(xiàn)[54]采用基于FFdata的方法對(duì)當(dāng)前層的網(wǎng)絡(luò)參數(shù)進(jìn)行基于單詞通過(guò)的前一層輸出的數(shù)據(jù)統(tǒng)計(jì)，試圖用可解釋的前饋設(shè)計(jì)解釋CNNs模型，所得結(jié)論說(shuō)明將前饋機(jī)器學(xué)習(xí)方法應(yīng)用于圖嵌入算法是有效的，因此，可解釋性的設(shè)計(jì)可代替高級(jí)神經(jīng)網(wǎng)絡(luò)的體系結(jié)構(gòu)，進(jìn)而為當(dāng)前圖嵌入相關(guān)任務(wù)的研究提供啟發(fā)。