最近在學(xué)習(xí)Embedding相關(guān)的知識(shí)的時(shí)候看到了一篇關(guān)于圖嵌入的綜述，覺得寫的不錯(cuò)便把文章中的一部分翻譯了出來。因自身水平有限，文中難免存在一些紕漏，歡迎發(fā)現(xiàn)的知友在評(píng)論區(qū)中指正。

目錄

一、圖嵌入概述

二、圖嵌入的挑戰(zhàn)

三、圖嵌入的方法

---

一、圖嵌入概述

圖，如社交網(wǎng)絡(luò)、單詞共存網(wǎng)絡(luò)和通信網(wǎng)絡(luò)，廣泛地存在于各種現(xiàn)實(shí)應(yīng)用中。通過對(duì)它們的分析，我們可以深入了解社會(huì)結(jié)構(gòu)、語言和不同的交流模式，因此圖一直是學(xué)界研究的熱點(diǎn)。圖分析任務(wù)可以大致抽象為以下四類: ( a )節(jié)點(diǎn)分類，( b )鏈接預(yù)測(cè)，( c )聚類，以及( d )可視化。其中，節(jié)點(diǎn)分類旨在基于其他標(biāo)記的節(jié)點(diǎn)和網(wǎng)絡(luò)拓?fù)鋪泶_定節(jié)點(diǎn)的標(biāo)簽(也稱為頂點(diǎn))。鏈路預(yù)測(cè)是指預(yù)測(cè)缺失鏈路或未來可能出現(xiàn)的鏈路的任務(wù)。聚類用于發(fā)現(xiàn)相似節(jié)點(diǎn)的子集，并將它們分組在一起；最后，可視化有助于深入了解網(wǎng)絡(luò)結(jié)構(gòu)。

真實(shí)的圖（網(wǎng)絡(luò)）往往是高維、難以處理的，20世紀(jì)初，研究人員發(fā)明了圖形嵌入算法，作為降維技術(shù)的一部分。他們首先根據(jù)實(shí)際問題構(gòu)造一個(gè)D維空間中的圖，然后將圖的節(jié)點(diǎn)嵌入到d（d<<D）維向量空間中。嵌入的思想是在向量空間中保持連接的節(jié)點(diǎn)彼此靠近。拉普拉斯特征映射（Laplacian Eigenmaps）和局部線性嵌入（Locally Linear Embedding ，LLE）是基于這一原理的算法的例子。然而，可伸縮性是這種方法的一個(gè)主要問題，它的時(shí)間復(fù)雜度是O (| V| 2)。

自2010年以來，關(guān)于圖嵌入的研究已經(jīng)轉(zhuǎn)移到解決網(wǎng)絡(luò)稀疏性的可伸縮圖嵌入技術(shù)上。例如，圖分解（Graph Factorization）使用鄰接矩陣的近似分解作為嵌入。LINE擴(kuò)展了這種方法，并試圖保持一階和二階近似。HOPE通過使用廣義奇異值分解( SVD )分解相似性矩陣而不是鄰接矩陣來擴(kuò)展LINE以試圖保持高階鄰近性。SDNE 使用自動(dòng)編碼器嵌入圖形節(jié)點(diǎn)并捕捉高度非線性的依賴關(guān)系。這些新的可擴(kuò)展方法的時(shí)間復(fù)雜度為0 ( | E | )。

二、圖嵌入的挑戰(zhàn)

如前所述，圖嵌入的目標(biāo)是發(fā)現(xiàn)高維圖的低維向量表示，而獲取圖中每個(gè)節(jié)點(diǎn)的向量表示是十分困難的，并且具有幾個(gè)挑戰(zhàn)，這些挑戰(zhàn)一直在推動(dòng)本領(lǐng)域的研究：

• 屬性選擇：節(jié)點(diǎn)的“良好”向量表示應(yīng)保留圖的結(jié)構(gòu)和單個(gè)節(jié)點(diǎn)之間的連接。第一個(gè)挑戰(zhàn)是選擇嵌入應(yīng)該保留的圖形屬性。考慮到圖中所定義的距離度量和屬性過多，這種選擇可能很困難，性能可能取決于實(shí)際的應(yīng)用場(chǎng)景。
• 可擴(kuò)展性：大多數(shù)真實(shí)網(wǎng)絡(luò)都很大，包含大量節(jié)點(diǎn)和邊。嵌入方法應(yīng)具有可擴(kuò)展性，能夠處理大型圖。定義一個(gè)可擴(kuò)展的模型具有挑戰(zhàn)性，尤其是當(dāng)該模型旨在保持網(wǎng)絡(luò)的全局屬性時(shí)。
• 嵌入的維數(shù)：實(shí)際嵌入時(shí)很難找到表示的最佳維數(shù)。例如，較高的維數(shù)可能會(huì)提高重建精度，但具有較高的時(shí)間和空間復(fù)雜性。較低的維度雖然時(shí)間、空間復(fù)雜度低，但無疑會(huì)損失很多圖中原有的信息。

三、圖嵌入的方法

在過去的十年里，在圖形嵌入領(lǐng)域已經(jīng)有了大量的研究，重點(diǎn)是設(shè)計(jì)新的嵌入算法。發(fā)展到現(xiàn)在，大體上可以將這些嵌入方法分為三大類：( 1 )基于因子分解的方法，( 2 )基于隨機(jī)游走的方法，以及( 3 )基于深度學(xué)習(xí)的方法。在下文中我將簡(jiǎn)要解釋每一個(gè)類別的特征與每一類別代表性算法的原理。

1.預(yù)備知識(shí)與符號(hào)定義

定義1 圖：一個(gè)圖G(V,E)由頂點(diǎn)集V={v1,…,vn}與邊集

構(gòu)成，圖的鄰接矩陣S則由每條邊的權(quán)值

構(gòu)成。如果頂點(diǎn)vi和vj之間沒有邊連接，那么

。如果圖是無向圖，則

。

邊的權(quán)值Sij表示vi和vj的相似度，由特定的評(píng)價(jià)函數(shù)得出，值越高則兩個(gè)頂點(diǎn)越相似。

定義2 一階近似：邊緣權(quán)重也被稱為節(jié)點(diǎn)vi和vj之間的一階近似值，因?yàn)樗鼈兪莾蓚€(gè)節(jié)點(diǎn)之間第一個(gè)也是最重要的相似性度量。

定義3 二階近似：一對(duì)節(jié)點(diǎn)之間的二階近似描述了該對(duì)節(jié)點(diǎn)鄰域結(jié)構(gòu)的相似性。設(shè)

表示vi和其他節(jié)點(diǎn)之間的一階接近。然后，根據(jù)si和sj的相似性確定vi和vj之間的二階近似。二階近似比較兩個(gè)節(jié)點(diǎn)的鄰域，如果它們具有相似的鄰域，則將它們視為相似的。

在上圖中因?yàn)?和7之間有邊連接，所以6和7一階近似。5和6之間雖然沒有邊，但是它們有4個(gè)相同的鄰居節(jié)點(diǎn)，所以5和6二階近似。

定義4 圖形嵌入：對(duì)于圖G=（v，e），圖嵌入是圖的頂點(diǎn)的映射

，d<<|v|,函數(shù)f保留了圖G上定義的一些相似度。因此，嵌入會(huì)將每個(gè)節(jié)點(diǎn)映射到低維特征向量，并嘗試保留頂點(diǎn)之間的連接強(qiáng)度。例如，嵌入保留一階近似可通過最小化

來獲得接近。讓兩個(gè)節(jié)點(diǎn)對(duì)( vi，vj )和( vi，vk )與連接強(qiáng)度相關(guān)聯(lián)，假如Sij>Sik。在這種情況下，vj將被映射到嵌入空間中比vk的映射更接近vi的點(diǎn)。

2.基于因子分解的方法

2.1 Locally Linear Embedding (LLE)

LLE假設(shè)每個(gè)節(jié)點(diǎn)都是嵌入空間中相鄰節(jié)點(diǎn)的線性組合。如果假設(shè)圖G的鄰接矩陣元素代表節(jié)點(diǎn)j能夠表示節(jié)點(diǎn)i的權(quán)重，我們定義

于是我們可以通過最小化

來求解嵌入后的圖

。

為了去除退化解，嵌入的方差被約束為

，考慮到平移不變性，嵌入以零為中心：

。

上述約束優(yōu)化問題可以簡(jiǎn)化為特征值問題，其解是取稀疏矩陣

的底部d+1特征向量，并丟棄與最小特征值對(duì)應(yīng)的那個(gè)特征向量。

2.2 Laplacian Eigenmaps

拉普拉斯特征映射的目的是在權(quán)重w ij較高時(shí)，保持兩個(gè)節(jié)點(diǎn)嵌入后離得很近，也就是說被分割太遠(yuǎn)的兩個(gè)相似節(jié)點(diǎn)會(huì)得到更多的反饋（懲罰）。具體來說，它最小化了以下目標(biāo)函數(shù)：

其中L是圖G的拉普拉斯算子，目標(biāo)函數(shù)受到

約束，以消除瑣碎的解。這一問題的解可以通過取正則化L的最小的d個(gè)特征值對(duì)應(yīng)的特征向量得到，

。

2.3. Cauchy graph embedding

拉普拉斯特征映射對(duì)嵌入節(jié)點(diǎn)之間的距離使用二次方的懲罰函數(shù)（

）。因此，在保持節(jié)點(diǎn)之間的相似性的同時(shí)，節(jié)點(diǎn)之間的差異性會(huì)被破壞。柯西圖嵌入通過使用

替換二次函數(shù)

來解決這個(gè)問題，重新排列后，要最大化的目標(biāo)函數(shù)變成

，伴隨著

和

兩個(gè)約束。新的目標(biāo)函數(shù)是距離的反函數(shù)，因此更加強(qiáng)調(diào)相似的節(jié)點(diǎn)而不是不同的節(jié)點(diǎn)。

2.4. Structure Preserving Embedding (SPE)

Structure Preserving Embedding (SPE)是另一種擴(kuò)展拉普拉斯特征映射的方法。SPE的目標(biāo)是精確地重建輸入圖。嵌入被存儲(chǔ)為一個(gè)正的半離散核矩陣K，并定義了一個(gè)連接算法G，該算法用來從K重構(gòu)出原來的圖形。

2.5. Graph Factorization (GF)

圖因式分解（GF）應(yīng)該是第一種獲得O（|E|）時(shí)間復(fù)雜度的圖嵌入方法。為了獲得嵌入，GF對(duì)圖的鄰接矩陣進(jìn)行因式分解，以最小化以下?lián)p失函數(shù)：

其中，λ是一個(gè)正則化系數(shù)。注意，求和是在觀察到的邊上，而不是所有可能的邊上。這是一個(gè)考慮到可伸縮性的近似值，因此可能會(huì)在解決方案中引入噪聲。注意，由于鄰接矩陣通常不是半正定的，即使嵌入的維數(shù)為|v|，損失函數(shù)的最小值也大于0。

2.6. GraRep

GraRep將節(jié)點(diǎn)的轉(zhuǎn)換概率定義為：

，并通過最小化

來保持k階近似，其中，

從

中得到（詳細(xì)過程可以閱讀參考文獻(xiàn)）。然后它連接所有k的

以形成

。要注意的是，這和HOPE方法很相似，HOPE通過最小化

來求解，其中，S是一個(gè)合適的相似度矩陣。

GraRep的缺點(diǎn)是可擴(kuò)展性，因?yàn)?/p>

往往會(huì)有

多個(gè)非零項(xiàng)。

2.7. HOPE

HOPE通過最小化

來保留更高階的近似，其中S是相似度矩陣。HOPE的作者測(cè)試了許多不同的相似度衡量方法，包括Katz Index, Rooted Page Rank, Common Neighbors, and Adamic-Adar score，并將S定義為

，這里面

和

都是稀疏的，因此HOPE也可以采用常用的奇異值分解方法來獲得高效的嵌入。

3、基于隨機(jī)游走的方法

3.1. DeepWalk

DeepWalk方法受到word2vec的啟發(fā)，首先選擇某一特定點(diǎn)為起始點(diǎn)，做隨機(jī)游走得到點(diǎn)的序列，然后將這個(gè)得到的序列視為句子，用word2vec來學(xué)習(xí)，得到該點(diǎn)的表示向量。DeepWalk通過隨機(jī)游走去可以獲圖中點(diǎn)的局部上下文信息，因此學(xué)到的表示向量反映的是該點(diǎn)在圖中的局部結(jié)構(gòu)，兩個(gè)點(diǎn)在圖中共有的鄰近點(diǎn)（或者高階鄰近點(diǎn)）越多，則對(duì)應(yīng)的兩個(gè)向量之間的距離就越短。

3.2. node2vec

與DeepWalk相似，node2vec通過最大化隨機(jī)游走得到的序列中的節(jié)點(diǎn)出現(xiàn)的概率來保持節(jié)點(diǎn)之間的高階鄰近性。與DeepWalk的最大區(qū)別在于，node2vec采用有偏隨機(jī)游走，在廣度優(yōu)先（bfs）和深度優(yōu)先（dfs）圖搜索之間進(jìn)行權(quán)衡，從而產(chǎn)生比DeepWalk更高質(zhì)量和更多信息量的嵌入。

3.3. Hierarchical representation learning for networks (HARP)

DeepWalk和node2vec隨機(jī)初始化節(jié)點(diǎn)嵌入以訓(xùn)練模型。由于它們的目標(biāo)函數(shù)是非凸的，這種初始化很可能陷入局部最優(yōu)。HARP引入了一種策略，通過更好的權(quán)重初始化來改進(jìn)解決方案并避免局部最優(yōu)。為此，HARP通過使用圖形粗化聚合層次結(jié)構(gòu)上一層中的節(jié)點(diǎn)來創(chuàng)建節(jié)點(diǎn)的層次結(jié)構(gòu)。然后，它生成最粗糙的圖的嵌入，并用所學(xué)到的嵌入初始化精煉圖的節(jié)點(diǎn)嵌入（層次結(jié)構(gòu)中的一個(gè)）。它通過層次結(jié)構(gòu)傳播這種嵌入，以獲得原始圖形的嵌入。因此，可以將HARP與基于隨機(jī)行走的方法（如DeepWalk和node2vec）結(jié)合使用，以獲得更好的優(yōu)化函數(shù)解。

3.4. Walklets

DeepWalk和node2vec通過隨機(jī)游走生成的序列，隱式地保持節(jié)點(diǎn)之間的高階鄰近性，由于其隨機(jī)性，這些隨機(jī)游走會(huì)得到不同距離的連接節(jié)點(diǎn)。另一方面，基于因子分解的方法，如GF和HOPE，通過在目標(biāo)函數(shù)中對(duì)節(jié)點(diǎn)進(jìn)行建模，明確地保留了節(jié)點(diǎn)之間的距離。Walklets將顯式建模與隨機(jī)游走的思想結(jié)合起來。該模型通過跳過圖中的某些節(jié)點(diǎn)來修改DeepWalk中使用的隨機(jī)游走策略。這是針對(duì)多個(gè)尺度的跳躍長度執(zhí)行的，類似于在GraRep中分解

，并且隨機(jī)行走獲得的一組點(diǎn)的序列用于訓(xùn)練類似于DeepWalk的模型。

4、基于深度學(xué)習(xí)的方法

4.1. Structural deep network embedding (SDNE)

SDNE建議使用深度自動(dòng)編碼器來保持一階和二階網(wǎng)絡(luò)鄰近度。它通過聯(lián)合優(yōu)化這兩個(gè)近似值來實(shí)現(xiàn)這一點(diǎn)。該方法利用高度非線性函數(shù)來獲得嵌入。模型由兩部分組成：無監(jiān)督和監(jiān)督。前者包括一個(gè)自動(dòng)編碼器，目的是尋找一個(gè)可以重構(gòu)其鄰域的節(jié)點(diǎn)的嵌入。后者基于拉普拉斯特征映射，當(dāng)相似頂點(diǎn)在嵌入空間中彼此映射得很遠(yuǎn)時(shí)，該特征映射會(huì)受到懲罰。

4.2. Deep neural networks for learning graph representations (DNGR)

DNGR結(jié)合了隨機(jī)游走和深度自動(dòng)編碼器。該模型由3部分組成：隨機(jī)游走、正點(diǎn)互信息（PPMI）計(jì)算和疊加去噪自編碼器。在輸入圖上使用隨機(jī)游走模型生成概率共現(xiàn)矩陣，類似于HOPE中的相似矩陣。將該矩陣轉(zhuǎn)化為PPMI矩陣，輸入到疊加去噪自動(dòng)編碼器中得到嵌入。輸入PPMI矩陣保證了自動(dòng)編碼器模型能夠捕獲更高階的近似度。此外，使用疊加去噪自動(dòng)編碼器有助于模型在圖中存在噪聲時(shí)的魯棒性，以及捕獲任務(wù)（如鏈路預(yù)測(cè)和節(jié)點(diǎn)分類）所需的底層結(jié)構(gòu)。

4.3. Graph convolutional networks (GCN)

上面討論的基于深度神經(jīng)網(wǎng)絡(luò)的方法，即SDNE和DNGR，以每個(gè)節(jié)點(diǎn)的全局鄰域（一行DNGR的PPMI和SDNE的鄰接矩陣）作為輸入。對(duì)于大型稀疏圖來說，這可能是一種計(jì)算代價(jià)很高且不適用的方法。圖卷積網(wǎng)絡(luò)（GCN）通過在圖上定義卷積算子來解決這個(gè)問題。該模型迭代地聚合了節(jié)點(diǎn)的鄰域嵌入，并使用在前一次迭代中獲得的嵌入及其嵌入的函數(shù)來獲得新的嵌入。僅局部鄰域的聚合嵌入使其具有可擴(kuò)展性，并且多次迭代允許學(xué)習(xí)嵌入一個(gè)節(jié)點(diǎn)來描述全局鄰域。最近幾篇論文提出了利用圖上的卷積來獲得半監(jiān)督嵌入的方法，這種方法可以通過為每個(gè)節(jié)點(diǎn)定義唯一的標(biāo)簽來獲得無監(jiān)督嵌入。這些方法在卷積濾波器的構(gòu)造上各不相同，卷積濾波器可大致分為空間濾波器和譜濾波器。空間濾波器直接作用于原始圖和鄰接矩陣，而譜濾波器作用于拉普拉斯圖的譜。

4.4. Variational graph auto-encoders (VGAE)

VGAE采用了圖形卷積網(wǎng)絡(luò)（GCN）編碼器和內(nèi)積譯碼器。輸入是鄰接矩陣，它們依賴于GCN來學(xué)習(xí)節(jié)點(diǎn)之間的高階依賴關(guān)系。他們的經(jīng)驗(yàn)表明，與非概率自編碼器相比，使用變分自編碼器可以提高性能。

5、其他

LINE

LINE適用于任意類型的信息網(wǎng)絡(luò)：無向、有向和無權(quán)、有權(quán)。該方法優(yōu)化了精心設(shè)計(jì)的目標(biāo)函數(shù)，能夠保留局部和全局網(wǎng)絡(luò)結(jié)構(gòu)。此外，LINE中還提出了邊緣采樣算法，解決了經(jīng)典隨機(jī)梯度下降的局限性，提高了算法的有效性和效率。具體來說，LINE明確定義了兩個(gè)函數(shù)，分別用于一階和二階近似，并最小化了這兩個(gè)函數(shù)的組合。一階鄰近函數(shù)與圖分解（GF）相似，都是為了保持嵌入的鄰接矩陣和點(diǎn)積接近。區(qū)別在于GF通過直接最小化兩者的差異來實(shí)現(xiàn)這一點(diǎn)。相反，LINE為每對(duì)頂點(diǎn)定義了兩個(gè)聯(lián)合概率分布，一個(gè)使用鄰接矩陣，另一個(gè)使用嵌入。然后，LINE最小化了這兩個(gè)分布的Kullback–Leibler（KL）散度。這兩個(gè)分布和目標(biāo)函數(shù)如下：

作者用和上面相似的方法定義了二階近似的概率分布和目標(biāo)函數(shù)：

為簡(jiǎn)單起見，將λi設(shè)置為頂點(diǎn)i的度數(shù)，即λi= di。同樣采用KL散度作為距離函數(shù)， 用KL散度代替d（·，·）。再省略一些常數(shù)，得到：

參考文獻(xiàn)

[1] Goyal P , Ferrara E . Graph Embedding Techniques, Applications, and Performance: A Survey[J]. Knowledge-Based Systems, 2017.

[2] Roweis, S. T . Nonlinear Dimensionality Reduction by Locally Linear Embedding[J]. Science, 2000, 290(5500):2323-2326.

[3] Perozzi B , Al-Rfou R , Skiena S . DeepWalk: Online Learning of Social Representations[J]. 2014.

[4] Grover A , Leskovec J . node2vec: Scalable Feature Learning for Networks[J]. Kdd, 2016.

[5] Wang D , Cui P , Zhu W . Structural Deep Network Embedding[C]// the 22nd ACM SIGKDD International Conference. ACM, 2016.

[6] Tang J , Qu M , Wang M , et al. LINE: Large-scale information network embedding[J]. 24th International Conference on World Wide Web, WWW 2015, 2015.

總結(jié)

以上是生活随笔為你收集整理的随机邻域嵌入_图嵌入（Graph embedding）综述的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。