Graph Embedding Techniques, Applications, and Performance: A Survey（圖嵌入技術(shù)载城、應(yīng)用及性能）

原文https://arxiv.org/pdf/1705.02801.pdf

定義

1.圖
2.一階相似性
3.二階相似性

嵌入方法的分類

1.因子分解方法（3.3）
2.隨機(jī)漫步技術(shù)（3.4）
3.深度學(xué)習(xí)（3.5）
4.其他雜項(xiàng)戰(zhàn)略（3.6）

圖嵌入的研究?jī)?nèi)容及其進(jìn)化

1.2000s.為一組基于鄰域的n個(gè)D維點(diǎn)建立一個(gè)相似度圖税产，然后把圖的節(jié)點(diǎn)嵌入到d維向量空間中莺葫，其中d<<D.這種嵌入的觀點(diǎn)能保證相連的節(jié)點(diǎn)在向量空間中靠近彼此（Eg.拉普拉斯特征映射算法;局部線性嵌入）
該算法時(shí)間復(fù)雜度

2.2010.利用真實(shí)世界的稀疏性得到可拓展的圖嵌入技術(shù)。(Eg. Graph Factorization使用鄰接矩陣的近似因子分解作為嵌入瓶盛；LINE拓展了上述方法并嘗試保留了一階相似性以及二階相似性，HOPE延伸了LINE嘗試通過常規(guī)的奇異值分解（SVD）來分解相似度矩陣而非鄰接矩陣去保留更高階的距離;SDNE使用了高度非線性的依賴)
新的可拓展的方法的時(shí)間復(fù)雜度為O(|E|)

圖嵌入方法的分類

將圖嵌入方法分為廣義的三個(gè)類別

1.基于矩陣分解

基于因數(shù)分解的算法表示節(jié)點(diǎn)之間的連接構(gòu)成了矩陣，再對(duì)該矩陣進(jìn)行因式分解以獲得嵌入观堂。該矩陣被用于表示包括節(jié)點(diǎn)鄰接矩陣，拉普拉斯矩陣呀忧，節(jié)點(diǎn)躍遷概率矩陣师痕，以及Katz相似度矩陣。分解代表性矩陣的方法根據(jù)矩陣類型的不同而變化而账。
半正定矩陣（如拉普拉斯矩陣）可以應(yīng)用特征值分解
非結(jié)構(gòu)化矩陣 -》 可以應(yīng)用梯度下降法在線性時(shí)間內(nèi)獲得嵌入胰坟。

(1)局部線性嵌入LLE
假設(shè)每個(gè)節(jié)點(diǎn)在潛入空間內(nèi)都是其鄰節(jié)點(diǎn)的結(jié)合，將約束最優(yōu)化問題簡(jiǎn)化成特征值問題泞辐，得到系數(shù)矩陣中最底的d+1個(gè)特征向量笔横，并丟棄最小特征值所對(duì)應(yīng)的特征向量。

(2)拉普拉斯特征映射算法
Laplacian Eigenmaps
保證當(dāng)Wij的權(quán)值較高所對(duì)應(yīng)的倆個(gè)節(jié)點(diǎn)在嵌入空間的距離較近咐吼。
找到第d小的正則化的拉普拉斯矩陣特征值所對(duì)應(yīng)的特征向量吹缔。

(3)柯西圖嵌入Cauchy Graph Embedding
對(duì)于嵌入中的距離使用二次罰函數(shù)。作者根據(jù)節(jié)點(diǎn)之間的距離的相對(duì)強(qiáng)調(diào)的不同（相似度/不相似度）锯茄，提出了幾種不同的變體厢塘，包括高斯函數(shù)、指數(shù)函數(shù)和線性嵌入肌幽。

(4)結(jié)構(gòu)保存嵌入SPE
拉普拉斯特征映射方法的繼承晚碾。目標(biāo)是重建輸入圖。嵌入被保存為一個(gè)半正定核矩陣K和一個(gè)連接算法牍颈。為了處理圖中的噪聲迄薄，需要增加一個(gè)松弛變量。

(5)圖分解GF
圖分解是首個(gè)能夠在O(|E|)的時(shí)間復(fù)雜度內(nèi)獲得嵌入的方法煮岁。GF分解了圖的鄰接矩陣讥蔽，最小化了損失函數(shù)。

(6)GraRep
以 定義了節(jié)點(diǎn)躍遷可能性 并通過最小化保存了k階相似性画机。缺點(diǎn)是可伸縮性冶伞。

(7)HOPE
HOPE通過最小化.其中S是相似度矩陣.作者基于多種相似度度量方法做了實(shí)驗(yàn)。相似度這使得HOPE能夠使用通用的奇異值分解（SVD）來獲得嵌入步氏。

(8)額外變體
為了給高維數(shù)據(jù)降維响禽，還有許多可以執(zhí)行圖嵌入的方法。如主成分分析PCA,線性判別分析LDA,多維拓展MDS,本地屬性保存LPP.和內(nèi)核特征映射。
還有許多最新的方法關(guān)注聯(lián)合學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)以及網(wǎng)絡(luò)中可用的額外節(jié)點(diǎn)屬性信息芋类。

2.基于隨機(jī)漫步

隨機(jī)漫步已經(jīng)被用來近似于圖中的許多屬性隆嗅，包括節(jié)點(diǎn)中心和相似度。當(dāng)一個(gè)人只能部分地觀察這個(gè)圖形侯繁，或者這個(gè)圖形太大而不能全部測(cè)量時(shí)胖喳，它們就特別有用。在圖中使用隨機(jī)漫步的方法來獲得節(jié)點(diǎn)表示：DeepWalk和node2vec是兩個(gè)例子贮竟。

(1)DeepWalk
DeepWalk通過最大化觀察最后k個(gè)節(jié)點(diǎn)的概率丽焊，以及在以vi為中心的隨機(jī)漫步中的下k個(gè)節(jié)點(diǎn)，保持了節(jié)點(diǎn)之間的高階相似性咕别。

(2)node2vec
與DeepWalk相同技健，node2vec通過最大限度地增加固定長度隨機(jī)漫步中后續(xù)節(jié)點(diǎn)發(fā)生的概率，保持節(jié)點(diǎn)間的高距離惰拱。他們之間最關(guān)鍵區(qū)別是node2vec采用的是雙隨機(jī)漫步雌贱，它提供了在廣度優(yōu)先（BFS）和深度優(yōu)先（DFS）圖搜索之間的交易，因此產(chǎn)生了比DeepWalk更優(yōu)質(zhì)弓颈、更有信息的嵌入帽芽。

(3)網(wǎng)絡(luò)的分層表示學(xué)習(xí)HARP
DeepWalk和node2vec為模型訓(xùn)練隨機(jī)初始化節(jié)點(diǎn)嵌入删掀。由于它們的目標(biāo)函數(shù)是非凸的翔冀，所以這樣的初始化可以被卡在局部的最優(yōu)值中。
通過更好的權(quán)重初始化披泪，哈普引入了一種改進(jìn)解決方案和避免局部?jī)?yōu)化的策略纤子。為了達(dá)到這個(gè)目的，通過使用圖形粗化來聚合前一層層次的節(jié)點(diǎn)款票，HARP創(chuàng)建了節(jié)點(diǎn)的層次結(jié)構(gòu)控硼。然后，它生成最粗圖的嵌入艾少，并根據(jù)已學(xué)習(xí)的嵌入來初始化精確圖（在層次結(jié)構(gòu)中的一個(gè)）的節(jié)點(diǎn)嵌入卡乾。它通過層次結(jié)構(gòu)傳播這種嵌入，以獲得原始圖的嵌入缚够。因此幔妨，HARP可以與諸如DeepWalk和node2vec等隨機(jī)漫步的方法結(jié)合使用，從而獲得更好的優(yōu)化功能解決方案谍椅。

(4)Walklets
DeepWalk和node2vec通過生成多個(gè)隨機(jī)漫步误堡，含蓄地保留了節(jié)點(diǎn)之間的高階近距離，由于其隨機(jī)特性雏吭，在不同的距離上連接節(jié)點(diǎn)锁施。另一方面，像GF和HOPE這樣的基于因子分解的方法可以通過在目標(biāo)函數(shù)中對(duì)節(jié)點(diǎn)進(jìn)行建模來顯式地保存節(jié)點(diǎn)之間的距離。walklet將這種顯式建模與隨機(jī)漫步的理念結(jié)合在一起悉抵。該模型通過跳過圖中的一些節(jié)點(diǎn)來修改在DeepWalk中使用的隨機(jī)漫步策略肩狂。這是為多個(gè)跳躍長度執(zhí)行的，類似于在GraRep中分解Ak姥饰，而產(chǎn)生的隨機(jī)漫步集用于訓(xùn)練類似于DeepWalk的模型婚温。

(5)額外變體
最近提出的上述方法有幾種不同的變體。類似于基于因子分解增加圖結(jié)構(gòu)中的節(jié)點(diǎn)屬性的方法媳否、Gen向量栅螟、鑒別深度隨機(jī)漫步（DDRW）、三方深網(wǎng)絡(luò)表示（TriDNR）和擴(kuò)展隨機(jī)漫步篱竭，共同學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性力图。

3.基于深度學(xué)習(xí)的方法

對(duì)深度學(xué)習(xí)的不斷增長的研究已經(jīng)導(dǎo)致了大量基于神經(jīng)網(wǎng)絡(luò)的方法應(yīng)用于圖表。深度自動(dòng)編碼器由于其在數(shù)據(jù)中建模非線性結(jié)構(gòu)的能力而被用于維度的減少掺逼。最近吃媒，SDNE，DNGR利用這種深度自動(dòng)編碼器的能力生成了一個(gè)嵌入模型吕喘，可以在圖中捕捉非線性赘那。

(1)構(gòu)造深度網(wǎng)絡(luò)嵌入SDNE
王等人提出要使用深度自動(dòng)編碼器來保存網(wǎng)絡(luò)的第一和第二階相似性。他們通過共同優(yōu)化這兩個(gè)距離來實(shí)現(xiàn)這一目標(biāo)氯质。該方法使用高度非線性的函數(shù)來獲得嵌入募舟。該模型由兩個(gè)部分組成：無人監(jiān)督和監(jiān)督。前者由一個(gè)自動(dòng)編碼器組成闻察，它的目標(biāo)是為一個(gè)可以重建其社區(qū)的節(jié)點(diǎn)找到一個(gè)嵌入拱礁。后者基于Laplacian特征映射，當(dāng)相似的頂點(diǎn)在嵌入空間中相互映射時(shí)辕漂，它會(huì)施加一個(gè)懲罰呢灶。

(2)用于學(xué)習(xí)圖形表示的深層神經(jīng)網(wǎng)絡(luò)DNGR
DNGR將隨機(jī)沖浪與深度自動(dòng)編碼器結(jié)合在一起。該模型由3個(gè)組成部分組成：隨機(jī)沖浪钉嘹、正點(diǎn)互信息（PPMI）計(jì)算和堆疊去噪的自動(dòng)編碼器鸯乃。在輸入圖上使用隨機(jī)沖浪模型來產(chǎn)生概率共發(fā)生矩陣，類似于HOPE中的相似矩陣跋涣。矩陣被轉(zhuǎn)換成一個(gè)PPMI矩陣缨睡，并將其輸入到一個(gè)堆疊的去噪的自動(dòng)編碼器中，以獲得嵌入仆潮。輸入PPMI矩陣可以確保自動(dòng)編碼器模型能夠捕獲更高階的接近度宏蛉。此外，使用堆疊去噪的自動(dòng)編碼器性置，在圖中存在噪聲的情況下拾并，支持模型的健壯性，以及捕獲諸如鏈接預(yù)測(cè)和節(jié)點(diǎn)分類等任務(wù)所需的底層結(jié)構(gòu)。

(3)圖卷積網(wǎng)絡(luò)
對(duì)于大型稀疏圖而言嗅义，SDNE屏歹、DNGR的效果是昂貴且不理想的。圖形卷積網(wǎng)絡(luò)（GCNs）31通過在圖上定義一個(gè)卷積運(yùn)算符來解決這個(gè)問題之碗。該模型迭代地聚集了一個(gè)節(jié)點(diǎn)的鄰居的嵌入蝙眶，并在以前的迭代中使用了獲得的嵌入和嵌入的功能來獲得新的嵌入。聚集局部鄰居的聚合使其具有可伸縮性褪那，并且多次迭代允許學(xué)習(xí)嵌入一個(gè)節(jié)點(diǎn)來描述全局鄰居幽纷。

(4)變分圖像自動(dòng)編碼器VGAE
該模型應(yīng)用一個(gè)卷積網(wǎng)絡(luò)編碼器和一個(gè)內(nèi)置產(chǎn)品解碼器。它的輸入是鄰接矩陣并且依賴GCN去學(xué)習(xí)節(jié)點(diǎn)之間的高階依賴博敬。們的經(jīng)驗(yàn)表明友浸，與非概率自動(dòng)編碼器相比，使用變分自動(dòng)編碼可以提高性能偏窝。

4.其他方法

1.LINE
LINE明確定義了兩個(gè)函數(shù)收恢，分別為第一和二階相似性，并最小化了兩者的組合祭往。一階近似的函數(shù)類似于圖分解（GF）伦意，因?yàn)樗鼈兌际菫榱吮３粥徑泳仃嚭蛢?nèi)嵌的點(diǎn)積。不同之處在于硼补，GF可以通過直接最小化兩者的差來做到這一點(diǎn)驮肉。相反，LINE定義了每一對(duì)頂點(diǎn)的兩個(gè)聯(lián)合概率分布括勺，一個(gè)是使用了一個(gè)矩陣缆八，另一個(gè)使用了嵌入。然后疾捍，LINE最小化了這兩個(gè)分布的kullback-Leibler（KL）散度。相似的定義了二階相似性的分布和目標(biāo)函數(shù)栏妖。

討論

應(yīng)用

1.網(wǎng)絡(luò)壓縮
費(fèi)德等人 介紹了網(wǎng)絡(luò)壓縮的概念（a.k.a乱豆。圖簡(jiǎn)化）。 對(duì)于圖G吊趾，他們定義了具有較少邊數(shù)的壓縮G. 目標(biāo)是更有效地存儲(chǔ)網(wǎng)絡(luò)并更快地運(yùn)行圖形分析算法宛裕。 他們通過將原始圖劃分為二分派并用樹替換它們來獲得壓縮圖，從而減少了邊數(shù)论泛。 多年來揩尸，許多研究人員使用基于聚合的方法來壓縮圖形。 這一系列工作的主要思想是利用圖的鏈接結(jié)構(gòu)來對(duì)節(jié)點(diǎn)和邊進(jìn)行分組屁奏。 Navlakha等人使用信息論中的最小描述長度(MDL)將圖形總結(jié)為圖形匯總和邊緣校正岩榆。
與這些表示類似，圖形嵌入也可以解釋為圖形的摘要。 王等人和Ou等人通過從嵌入和重建誤差評(píng)估重建原始圖來明確地測(cè)試該假設(shè)勇边。 它們表明每個(gè)節(jié)點(diǎn)的低維表示（大約100s）足以重建高精度的圖形犹撒。

2.可視化
可視化圖形的應(yīng)用可以追溯到1736年，當(dāng)歐拉用它來解決“Konigsberger Bruckenproblem”時(shí)粒褒。 近年來识颊，圖形可視化已經(jīng)在軟件工程，電路奕坟，生物學(xué)和社會(huì)學(xué)中得到應(yīng)用祥款。 Battista等人 和Eades等人調(diào)查了一系列用于繪制圖形的方法，并為此目的定義了美學(xué)標(biāo)準(zhǔn)月杉。 赫爾曼等人 概括這一點(diǎn)并從信息可視化角度查看它镰踏。他們研究和比較用于繪制圖形的各種傳統(tǒng)布局，包括基于樹沙合，3D和雙曲線的布局.
由于嵌入表示向量空間中的圖形奠伪，因此可以應(yīng)用主成分分析（PCA）和t分布隨機(jī)鄰域嵌入（t-SNE）等維數(shù)減少技術(shù)來對(duì)圖形進(jìn)行可視化。作者 DeepWalk 通過可視化Zachary的空手道俱樂部網(wǎng)絡(luò)首懈，展示了他們嵌入方法的優(yōu)點(diǎn)绊率。 LINE 的作者將DBLP合作網(wǎng)絡(luò)可視化，并表明LINE能夠?qū)⒆髡呔奂谕活I(lǐng)域究履。 SDNE的作者將其應(yīng)用于20-Newsgroup文檔相似性網(wǎng)絡(luò)滤否，以獲得基于主題的文檔集群。

3.聚類分析
圖聚類（也就是說最仑，網(wǎng)絡(luò)分區(qū)）可以是兩種類型：（a）基于結(jié)構(gòu)藐俺，（b）基于屬性的聚類。 前者可以進(jìn)一步分為兩類泥彤，即基于社區(qū)和結(jié)構(gòu)上等同的聚類欲芹。
基于結(jié)構(gòu)的方法旨在找到具有大量簇內(nèi)邊緣和較少簇間邊緣的密集子圖。 相反吟吝，結(jié)構(gòu)等價(jià)聚類旨在識(shí)別具有相似作用的節(jié)點(diǎn)（如橋梁和異常值）菱父。 基于屬性的方法除了觀察到的鏈接外，還利用節(jié)點(diǎn)標(biāo)簽來聚類節(jié).White 等人在嵌入上使用k-means來聚類節(jié)點(diǎn)并可視化在Wordnet和NCAA數(shù)據(jù)集上獲得的聚類剑逃，以驗(yàn)證所獲得的聚類具有直觀的解釋浙宜。 最近的嵌入方法沒有明確地評(píng)估它們?cè)谶@個(gè)任務(wù)上的模型，因此它是圖嵌入社區(qū)中一個(gè)很有前景的研究領(lǐng)域蛹磺。

4.鏈路預(yù)測(cè)
指預(yù)測(cè)未來可能在不斷發(fā)展的網(wǎng)絡(luò)中出現(xiàn)的缺失交互或鏈路的任務(wù)粟瞬。在社交網(wǎng)絡(luò)中，可以用于推薦可能的好友關(guān)系萤捆，達(dá)到更好的用戶體驗(yàn)裙品。 Liben Nowell等人俗批，Lu等人和哈桑等人調(diào)查該領(lǐng)域的最新進(jìn)展并將算法分類為（a）基于相似性（局部和全局）（b）基于最大可能性和（c）基于概率的方法。
嵌入可以明確或隱含的捕獲網(wǎng)絡(luò)固有動(dòng)態(tài)清酥，使得應(yīng)用程序可以鏈路預(yù)測(cè)扶镀。經(jīng)驗(yàn)證，在生物網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等數(shù)據(jù)集上焰轻，使用嵌入預(yù)測(cè)的鏈接比上述傳統(tǒng)的基于相似性的鏈接預(yù)測(cè)方法更準(zhǔn)確臭觉。

5.節(jié)點(diǎn)分類
指通過已標(biāo)記的節(jié)點(diǎn)和網(wǎng)絡(luò)中的鏈接來推斷缺少的標(biāo)簽。
通常在網(wǎng)絡(luò)中辱志，標(biāo)記一小部分節(jié)點(diǎn)蝠筑。在社交網(wǎng)絡(luò)中，標(biāo)簽可以表示興趣揩懒，信仰或人口統(tǒng)計(jì)什乙。在語言網(wǎng)絡(luò)中，文檔可以用主題或關(guān)鍵詞標(biāo)記已球，而生物學(xué)網(wǎng)絡(luò)中的實(shí)體的標(biāo)簽可以基于功能臣镣。由于各種因素，對(duì)于大部分節(jié)點(diǎn)智亮，標(biāo)簽可能是未知的忆某。例如，在社交網(wǎng)絡(luò)中阔蛉，由于隱私問題弃舒，許多用戶不提供他們的人口統(tǒng)計(jì)信息∽丛可以使用標(biāo)記的節(jié)點(diǎn)和網(wǎng)絡(luò)中的鏈接來推斷缺少的標(biāo)簽聋呢。預(yù)測(cè)這些缺失標(biāo)簽的任務(wù)也稱為節(jié)點(diǎn)分類。 Bhagat等人調(diào)查文獻(xiàn)中用于此任務(wù)的方法颠区。他們將方法分為兩類削锰，即基于特征提取和基于隨機(jī)游走⊥吆簦基于特征的模型基于其鄰域和局部網(wǎng)絡(luò)統(tǒng)計(jì)為節(jié)點(diǎn)生成特征喂窟，然后應(yīng)用Logistic回歸和樸素貝葉斯等分類器來預(yù)測(cè)標(biāo)簽⊙氪基于隨機(jī)游走的模型通過隨機(jī)游走傳播標(biāo)簽。
嵌入可以被解釋為基于網(wǎng)絡(luò)結(jié)構(gòu)自動(dòng)提取節(jié)點(diǎn)的特征碗啄，因此屬于第一類质和。近期關(guān)于語言、社會(huì)稚字，生物饲宿，和協(xié)作方面的工作證明了圖嵌入可以高精度的預(yù)測(cè)丟失的標(biāo)簽厦酬。

實(shí)驗(yàn)設(shè)置

系統(tǒng)：Ubuntu 14.04.4 LT .該系統(tǒng)具有32個(gè)內(nèi)核，128 GB RAM和2.6 GHz的時(shí)鐘速度瘫想。

用于基于深度網(wǎng)絡(luò)的模型的GPU：Nvidia Tesla K40C仗阅。

數(shù)據(jù)集：一個(gè)合成數(shù)據(jù)集和6個(gè)真實(shí)數(shù)據(jù)集
(1)SYN-SBM
(2)空手道網(wǎng)絡(luò)
(3)BlogCatalog網(wǎng)站上列出的博主的社交關(guān)系網(wǎng)絡(luò)
(4)Youtube
(5)HEP-TH 1993。1-2003.4期間高能物理理論論文寫作網(wǎng)絡(luò)
(6)PPI人類蛋白質(zhì)之間的生物相互作用網(wǎng)絡(luò)

評(píng)估指標(biāo)：
評(píng)估嵌入方法在圖形重建和鏈接預(yù)測(cè)中的性能的指標(biāo)：精度k（Pr @ k）和均值平均精度（MAP）国夜。
評(píng)估節(jié)點(diǎn)分類指標(biāo)：micro-F1和macro-F1减噪。
指標(biāo)定義如下：
Pr @ k:指是前k個(gè)預(yù)測(cè)中正確預(yù)測(cè)的比率。
MAP:估計(jì)每個(gè)節(jié)點(diǎn)的精度车吹，并計(jì)算所有節(jié)點(diǎn)的平均值
macro-F1:在多標(biāo)簽分類任務(wù)中筹裕，定義為所有標(biāo)簽的平均F1值
F1值是精確率和召回率的調(diào)和均值，即F1=2PR/(P+R)窄驹，相當(dāng)于精確率和召回率的綜合評(píng)價(jià)指標(biāo)）朝卒。精確率（Precision）為TP/(TP+FP)，即為在預(yù)測(cè)為壞人的人中乐埠，預(yù)測(cè)正確（實(shí)際為壞人）的人占比抗斤。召回率（Recall）為TP/(TP+FN)，即為在實(shí)際為壞人的人中丈咐，預(yù)測(cè)正確（預(yù)測(cè)為壞人）的人占比瑞眼。]
micro-F1:micro-F1通過計(jì)算總真陽性，假陰性和誤差來全局計(jì)算F1扯罐，給每個(gè)實(shí)例賦予相同的權(quán)重负拟。

實(shí)驗(yàn)及分析

在本節(jié)中，我們將評(píng)估和比較上述任務(wù)中的嵌入方法歹河。 對(duì)于每個(gè)任務(wù)掩浙，我們顯示嵌入維度的數(shù)量對(duì)性能的影響，并比較方法的超參數(shù)靈敏度秸歧。 此外厨姚，我們將嵌入技術(shù)的性能與不同超參數(shù)的各種任務(wù)相關(guān)聯(lián)，以測(cè)試可以在所有任務(wù)上表現(xiàn)良好的“全好”嵌入的概念键菱。

圖重建

期望以低維的表征進(jìn)行圖嵌入來精確的重構(gòu)圖谬墙。
圖2展示了通過128維所獲得的重建精度。
經(jīng)過圖的重建经备， 我們觀察到雖然方法的性能依賴于數(shù)據(jù)集拭抬，但是保持高階鄰近性的嵌入方法通常優(yōu)于其他方法。 拉普拉斯特征圖在SBM上的良好性能可歸因于數(shù)據(jù)集中缺乏更高階的結(jié)構(gòu)侵蒙。 我們還觀察到SDNE在所有數(shù)據(jù)集上始終表現(xiàn)良好造虎。 這可以歸因于它從網(wǎng)絡(luò)中學(xué)習(xí)復(fù)雜結(jié)構(gòu)的能力。 node2vec學(xué)習(xí)的嵌入具有低重建精度纷闺。 這可能是由于高度非線性維度減少算凿，產(chǎn)生非線性流形份蝴。 但是，HOPE可以學(xué)習(xí)線性嵌入但保留更高階的接近度氓轰，可以很好地重建圖形而無需任何其他參數(shù)婚夫。
維度的影響：圖3顯示了維度對(duì)于重建誤差的影響。 除了幾個(gè)例外署鸡，隨著維度數(shù)量的增加案糙，MAP值也會(huì)增加。這是直觀的储玫，因?yàn)楦嗟木S度能夠存儲(chǔ)更多信息侍筛。 我們還觀察到SDNE能夠以高精度將圖形嵌入16維向量空間中，盡管需要解碼器參數(shù)來獲得這樣的精度撒穷。

可視化

由于嵌入是圖中節(jié)點(diǎn)的低維向量表示匣椰，因此它允許我們可視化節(jié)點(diǎn)以理解網(wǎng)絡(luò)拓?fù)洹?由于不同的嵌入方法保留了網(wǎng)絡(luò)中不同的結(jié)構(gòu)，它們對(duì)節(jié)點(diǎn)可視化的能力和解釋更加困難端礼。
-- 對(duì)于SBM禽笑，我們將學(xué)習(xí)方法的128維嵌入，并輸入到t-SNE(t-SNE是目前來說效果最好的數(shù)據(jù)降維與可視化方法)蛤奥，來將維度降低到2并在2維空間中可視化節(jié)點(diǎn)佳镜。可視化結(jié)果如圖4所示凡桥。
-- 我們可視化空手道圖（見圖5）來說明嵌入方法保留的屬性蟀伸。 LLE和LE（（a）和（f））嘗試將具有高簇內(nèi)邊緣的圖和群集節(jié)點(diǎn)的社區(qū)結(jié)構(gòu)保持在一起。
GF（（b））非常密切地嵌入社區(qū)缅刽，并使葉節(jié)點(diǎn)遠(yuǎn)離其他節(jié)點(diǎn)啊掏。在（d）中，我們觀察到HOPE嵌入節(jié)點(diǎn)16和21衰猛，其原始圖中的Katz相似性非常低（0.0006）迟蜜，相距最遠(yuǎn)（考慮點(diǎn)積相似性）。 node2vec和SDNE（（c）和（e））保留了節(jié)點(diǎn)的社區(qū)結(jié)構(gòu)和結(jié)構(gòu)屬性的混合啡省。節(jié)點(diǎn)32和33娜睛，它們都是高度集中并且在它們的社區(qū)中心，嵌入在一起并且遠(yuǎn)離低度節(jié)點(diǎn)卦睹。此外畦戒，它們更接近屬于其社區(qū)的節(jié)點(diǎn)。 SDNE嵌入節(jié)點(diǎn)0结序，節(jié)點(diǎn)0作為社區(qū)之間的橋梁兢交，遠(yuǎn)離其他節(jié)點(diǎn)。請(qǐng)注意笼痹，與其他方法不同配喳，它并不意味著節(jié)點(diǎn)0與其余節(jié)點(diǎn)斷開連接。這里的含義是SDNE將節(jié)點(diǎn)0識(shí)別為單獨(dú)類型的節(jié)點(diǎn)凳干，并將其與編碼器和解碼器中其他節(jié)點(diǎn)的連接編碼晴裹。深度自動(dòng)編碼器識(shí)別網(wǎng)絡(luò)中重要節(jié)點(diǎn)的能力尚未研究，但鑒于此觀察救赐，我們認(rèn)為這一點(diǎn)方向可能是有希望的涧团。

鏈路預(yù)測(cè)

為了測(cè)試不同嵌入方法在此任務(wù)上的性能，對(duì)于每個(gè)數(shù)據(jù)集经磅，我們隨機(jī)隱藏20％的網(wǎng)絡(luò)邊緣泌绣。我們使用剩余的80％邊緣學(xué)習(xí)嵌入，并預(yù)測(cè)在學(xué)習(xí)嵌入的訓(xùn)練數(shù)據(jù)中未觀察到的最可能的邊緣预厌。node2vec實(shí)現(xiàn)了在BlogCatalog上的良好性能阿迈，但在其他數(shù)據(jù)集上表現(xiàn)不佳。 HOPE在所有數(shù)據(jù)集上都取得了良好的性能轧叽，這意味著保留更高階的鄰近性有助于預(yù)測(cè)未觀察到的鏈路苗沧。同樣，SDNE優(yōu)于其他方法炭晒，但PPI除外待逞，隨著嵌入維數(shù)增加到8以上，性能會(huì)急劇下降网严。
圖7說明了嵌入維度對(duì)鏈路預(yù)測(cè)的影響识樱。有兩個(gè)發(fā)現(xiàn)。1.在PPI和BlogCatalog中震束，與圖形重建性能不同怜庸，隨著維數(shù)的增加，性能沒有提高驴一。 這可能是因?yàn)橛辛烁鄥?shù)休雌，模型會(huì)在觀察到的鏈路上過度擬合，無法預(yù)測(cè)未觀察到的鏈路肝断。2.在相同的數(shù)據(jù)集上杈曲，方法的相對(duì)性能也取決于嵌入維度。

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

使用網(wǎng)絡(luò)拓?fù)漕A(yù)測(cè)節(jié)點(diǎn)標(biāo)簽在網(wǎng)絡(luò)分析中廣泛流行胸懈，并且具有各種應(yīng)用担扑，包括文檔分類和興趣預(yù)測(cè)。良好的網(wǎng)絡(luò)嵌入應(yīng)該保留了網(wǎng)絡(luò)結(jié)構(gòu)趣钱，因此對(duì)節(jié)點(diǎn)分類很有用涌献。我們通過使用生成的嵌入作為節(jié)點(diǎn)特征對(duì)節(jié)點(diǎn)進(jìn)行分類來比較嵌入方法對(duì)此任務(wù)的有效性。對(duì)于每個(gè)數(shù)據(jù)集首有，我們隨機(jī)抽取10％到90％的節(jié)點(diǎn)作為訓(xùn)練數(shù)據(jù)燕垃，并評(píng)估其余節(jié)點(diǎn)的性能枢劝。
圖8顯示了實(shí)驗(yàn)結(jié)果，可以看到node2vec在節(jié)點(diǎn)分類上優(yōu)于其他方法卜壕。

超參數(shù)靈敏性

（超參數(shù)：根據(jù)經(jīng)典的機(jī)器學(xué)習(xí)文獻(xiàn)您旁，可以將模型看作假設(shè)，而參數(shù)是根據(jù)特定的數(shù)據(jù)集對(duì)假設(shè)進(jìn)行的具體調(diào)整轴捎。模型超參數(shù)是模型外部的配置鹤盒，其值不能從數(shù)據(jù)估計(jì)得到。應(yīng)用于估計(jì)模型參數(shù)的過程中侦副。通常由實(shí)踐者直接指定侦锯，通常可以使用啟發(fā)式方法來設(shè)置秦驯，通常根據(jù)給定的預(yù)測(cè)建模問題而調(diào)整尺碰。）
超參數(shù)靈敏度：參數(shù)設(shè)置對(duì)于嵌入方法性能的影響程度。
-嵌入方法相對(duì)于超參數(shù)有多健壯汇竭？
-最佳超參數(shù)是否依賴于嵌入的下游任務(wù)葱蝗？
-有關(guān)超參數(shù)的性能差異對(duì)數(shù)據(jù)集提供了哪些見解？
（1）圖因子分解GF
圖因子分解的目標(biāo)函數(shù)包含具有系數(shù)的權(quán)重正則化項(xiàng)细燎。該系數(shù)控制著嵌入的普遍性两曼。低正則化系數(shù)有利于更好的重建，但可能過度擬合觀察到的圖導(dǎo)致預(yù)測(cè)性能差玻驻。 另一方面悼凑，高正規(guī)化可能代表數(shù)據(jù)不足，因此在所有任務(wù)上表現(xiàn)不佳璧瞬。圖10展示了鏈路預(yù)測(cè)和節(jié)點(diǎn)分類的性能隨著正則化系數(shù)的增加户辫，先達(dá)到峰值，然后下降嗤锉。且該性能變化是相當(dāng)大的渔欢。因此應(yīng)該根據(jù)給定數(shù)據(jù)集仔細(xì)調(diào)整系數(shù)。
（2）HOPE
HOPE是對(duì)節(jié)點(diǎn)之間的相似性矩陣進(jìn)行分解以獲得嵌入瘟忱，因此 超參數(shù)依賴于獲得相似度矩陣的方法奥额。我們使用了Katz指數(shù)用于此目的。評(píng)估衰減因子（β）的影響访诱，可以將其解釋為性能的高階接近系數(shù)垫挨。圖形結(jié)構(gòu)影響該參數(shù)的最佳值。
對(duì)于具有緊密編織社區(qū)的結(jié)構(gòu)良好的圖形触菜，高的β值將錯(cuò)誤地在嵌入空間中更近地分配不同的節(jié)點(diǎn)九榔。相反，對(duì)于具有弱社區(qū)結(jié)構(gòu)的圖，捕獲更高階距離是很重要的哲泊，β的高值可以產(chǎn)生更好的嵌入剩蟀。
（3）SDNE
SDNE使用耦合深度自動(dòng)編碼器嵌入圖形罚勾。 它利用一個(gè)參數(shù)來控制目標(biāo)函數(shù)中觀察到的和未觀察到的鏈接重建的權(quán)重推盛。高參數(shù)值將集中于重建觀察到的鏈接而忽略不存在未觀察到的鏈接。 此參數(shù)可能至關(guān)重要，因?yàn)檩^低的值可能會(huì)阻礙預(yù)測(cè)隱藏鏈接牢屋。 圖12顯示了我們的分析結(jié)果。
（4）node2vec.
node2vec在圖上執(zhí)行偏向隨機(jī)遍歷槽袄，并將通常一起出現(xiàn)在其中的節(jié)點(diǎn)嵌入到嵌入空間中烙无。在該方法的各種超參數(shù)中（包括行走長度，上下文大小和偏差權(quán)重）遍尺，我們分析偏差權(quán)重對(duì)性能的影響截酷，并采用剩余超參數(shù)的常用值[29]，即上下文大小node2vec具有兩個(gè)偏置權(quán)重：（a）inout參數(shù)（q）乾戏，它控制隨機(jī)游走遠(yuǎn)離傳入節(jié)點(diǎn)的可能性（更高的值有利于更近的節(jié)點(diǎn)）迂苛，以及（b）返回參數(shù)（p），它衡量返回概率（較低的值有利于返回）鼓择。較低的q值將有助于捕獲節(jié)點(diǎn)之間更長的距離三幻，并旨在保持結(jié)構(gòu)等效性。
在節(jié)點(diǎn)分類中（圖13c）呐能，我們觀察到低q值有助于實(shí)現(xiàn)更高的準(zhǔn)確度念搬，這表明需要捕獲結(jié)構(gòu)等價(jià)來準(zhǔn)確地嵌入圖的結(jié)構(gòu)。相反摆出，高q值有利于鏈接預(yù)測(cè)（圖13b）
針對(duì)鏈路預(yù)測(cè)的任務(wù)對(duì)圖14中的SBM進(jìn)行了類似的觀察朗徊，還注意到，由于圖形具有強(qiáng)大的社區(qū)結(jié)構(gòu)偎漫，因此SBM中q的最佳值要高得多爷恳。

圖嵌入的Python庫

我們發(fā)布了一個(gè)開源Python庫，GEM（圖形嵌入方法象踊，https：//github.com/palash1992/GEM）温亲，它為這里介紹的所有方法的實(shí)現(xiàn)及其評(píng)估指標(biāo)提供了統(tǒng)一的接口。 該庫支持加權(quán)和未加權(quán)圖形通危。 GEM的分層設(shè)計(jì)和模塊化實(shí)現(xiàn)應(yīng)該有助于用戶在新數(shù)據(jù)集上測(cè)試已實(shí)現(xiàn)的方法铸豁，并作為平臺(tái)輕松開發(fā)新方法。
GEM（https://github.com/palash1992/GEM）提供了局部線性嵌入[26]菊碟，拉普拉斯特征映射[25]节芥，圖分解[21]，HOPE [24]，SDNE [23]和node2vec [29]的實(shí)現(xiàn)头镊。 對(duì)于node2vec蚣驼，我們使用作者[95]提供的C ++實(shí)現(xiàn)并生成Python接口。 此外相艇，GEM還提供了一個(gè)界面颖杏，用于評(píng)估上述四個(gè)任務(wù)中的學(xué)習(xí)嵌入。 該接口非常靈活坛芽，支持多種邊緣重建指標(biāo)留储，包括余弦相似度，歐氏距離和基于解碼器（基于自動(dòng)編碼器的模型）咙轩。 對(duì)于多標(biāo)記節(jié)點(diǎn)分類获讳，庫使用one-rest-rest邏輯回歸分類器并支持使用其他ad hoc分類器。

結(jié)論與展望

對(duì)圖嵌入技術(shù)的回顧涵蓋了三大類方法：基于分解活喊，基于隨機(jī)游走和基于深度學(xué)習(xí)丐膝。我們研究了通過各種嵌入方法保留的結(jié)構(gòu)和屬性，并描述了圖嵌入技術(shù)以及每種方法所面臨的挑戰(zhàn)钾菊。我們報(bào)告了嵌入的各種應(yīng)用及其各自的評(píng)估指標(biāo)帅矗。我們使用幾個(gè)公開可用的真實(shí)網(wǎng)絡(luò)對(duì)這些應(yīng)用程序的調(diào)查方法進(jìn)行了實(shí)證評(píng)估，并比較了它們的優(yōu)缺點(diǎn)煞烫。最后浑此，我們提出了一個(gè)開源Python庫，名為GEM红竭，我們開發(fā)了實(shí)施的調(diào)查嵌入方法和評(píng)估任務(wù)尤勋，包括圖形重建，鏈接預(yù)測(cè)茵宪，節(jié)點(diǎn)分類和可視化最冰。我們認(rèn)為圖嵌入領(lǐng)域有三個(gè)有前景的研究方向：（1）探索非線性模型，（2）研究網(wǎng)絡(luò)演化稀火，（3）生成具有現(xiàn)實(shí)世界特征的合成網(wǎng)絡(luò)暖哨。如調(diào)查所示，一般的非線性模型（例如基于深度學(xué)習(xí)）在捕獲圖的固有動(dòng)態(tài)方面表現(xiàn)出很大的希望凰狞。它們能夠近似任意函數(shù)篇裁，最好地解釋網(wǎng)絡(luò)邊緣，這可能導(dǎo)致網(wǎng)絡(luò)的高度壓縮表示赡若。這種方法的一個(gè)缺點(diǎn)是可解釋性有限达布。進(jìn)一步研究側(cè)重于解釋這些模型所學(xué)的嵌入可能非常有成效。利用嵌入技術(shù)研究圖形演化是一個(gè)需要進(jìn)一步探索的新研究領(lǐng)域逾冬。最近的工作跟隨了這一思路黍聂，并說明了嵌入如何用于動(dòng)態(tài)圖躺苦。生成具有真實(shí)世界特征的合成網(wǎng)絡(luò)一直是一個(gè)受歡迎的研究領(lǐng)域，主要是為了便于模擬产还。實(shí)圖的低維矢量表示可以幫助理解它們的結(jié)構(gòu)匹厘，因此可用于生成具有真實(shí)世界特征的合成圖。使用生成模型學(xué)習(xí)嵌入可以在這方面幫助我們脐区。