導(dǎo)讀

這篇文章描述了什么是圖嵌入，圖嵌入的用處，并對比了常用的幾種圖嵌入方法。

圖常用在現(xiàn)實世界的不同場景中。社交網(wǎng)絡(luò)是人們相互聯(lián)系的大型圖，生物學(xué)家使用蛋白質(zhì)相互作用的圖，而通信網(wǎng)絡(luò)本身就是圖。他們在文本挖掘領(lǐng)域使用詞共現(xiàn)圖。對在圖形上使用機器學(xué)習(xí)的興趣正在增長。他們試圖在社交媒體上預(yù)測新的聯(lián)系，而生物學(xué)家預(yù)測蛋白質(zhì)的功能標(biāo)簽。圖上的數(shù)學(xué)和統(tǒng)計操作是有限的，將機器學(xué)習(xí)方法直接應(yīng)用到圖上是很有挑戰(zhàn)性的。在這種情況下，嵌入似乎是一個合理的解決方案。

什么是圖嵌入？

圖嵌入是將屬性圖轉(zhuǎn)換為一個或一組向量。嵌入應(yīng)該捕獲圖的拓撲結(jié)構(gòu)、頂點到頂點的關(guān)系以及關(guān)于圖、子圖和頂點的其他相關(guān)信息。更多的屬性嵌入編碼可以在以后的任務(wù)中獲得更好的結(jié)果。我們大致可以將嵌入分為兩組：

頂點嵌入：我們用每個頂點(節(jié)點)自己的向量表示對其進行編碼。當(dāng)我們想要在頂點層次上執(zhí)行可視化或預(yù)測時，我們會使用這種嵌入，例如在二維平面上對頂點進行可視化，或者基于頂點相似性預(yù)測新的連接。

圖嵌入：這里我們用一個向量表示整個圖。當(dāng)我們想要在圖的層次上做出預(yù)測時，以及當(dāng)我們想要比較或可視化整個圖時，例如比較化學(xué)結(jié)構(gòu)時，就會用到這些嵌入。

稍后，我們將介紹來自第一組的一些常用方法(DeepWalk、node2vec、SDNE)和來自第二組的graph2vec方法。

我們?yōu)槭裁匆玫綀D嵌入？

圖是一種有意義的、可理解的數(shù)據(jù)表示，但是需要使用圖嵌入的原因如下：

機器學(xué)習(xí)在圖上的應(yīng)用是有限的。圖由邊和節(jié)點組成。這些網(wǎng)絡(luò)關(guān)系只能使用數(shù)學(xué)、統(tǒng)計和機器學(xué)習(xí)的特定子集，而向量空間有更豐富的方法工具集。

嵌入是壓縮的表示。鄰接矩陣描述圖中節(jié)點之間的連接。它是一個|V| x |V|矩陣，其中|V|是圖中的一些節(jié)點。矩陣中的每一列和每一行都表示一個節(jié)點。矩陣中的非零值表示兩個節(jié)點連接。對于大型圖，使用鄰接矩陣作為特征空間幾乎是不可能的。假設(shè)一個圖有1M個節(jié)點和一個1M x 1M的鄰接矩陣。嵌入比鄰接矩陣更實用，因為它們將節(jié)點屬性打包到一個維度更小的向量中。

向量運算比圖上的運算更簡單、更快。

挑戰(zhàn)

嵌入方法需要滿足更多的需求。這里我們描述了嵌入方法面臨的三個挑戰(zhàn)：

我們需要確保嵌入能夠很好地描述圖的屬性。它們需要表示圖拓撲、節(jié)點連接和節(jié)點鄰居。預(yù)測或可視化的性能取決于嵌入的質(zhì)量。

網(wǎng)絡(luò)的大小不應(yīng)降低嵌入過程的速度。圖通常很大。想象一下?lián)碛袛?shù)百萬人的社交網(wǎng)絡(luò)。好的嵌入方法需要在大型圖上有效。

一個基本的挑戰(zhàn)是決定嵌入維數(shù)。較長的嵌入保存了更多的信息，同時它們比排序器嵌入帶來更高的時間和空間復(fù)雜度。用戶需要根據(jù)需求做出權(quán)衡。在文章中，他們通常報告說，嵌入大小在128到256之間就足夠完成大多數(shù)任務(wù)。在Word2vec方法中，他們選擇了嵌入長度300。

Word2vec

在介紹嵌入圖的方法之前，我將討論Word2vec方法和skip-gram神經(jīng)網(wǎng)絡(luò)。它們是圖形嵌入方法的基礎(chǔ)。

Word2vec是一種將單詞轉(zhuǎn)換為嵌入向量的嵌入方法。相似的單詞應(yīng)該有相似的嵌入。Word2vec采用skip-gram網(wǎng)絡(luò)，skip-gram網(wǎng)絡(luò)具有一個隱含層的神經(jīng)網(wǎng)絡(luò)。skip-gram被訓(xùn)練來預(yù)測句子中的相鄰單詞。這個任務(wù)被稱為偽任務(wù)，因為它只是在訓(xùn)練階段使用。網(wǎng)絡(luò)在輸入端接受單詞，并對其進行優(yōu)化，使其能夠以較高的概率預(yù)測句子中的相鄰單詞。下圖顯示了輸入單詞(用綠色標(biāo)記)和預(yù)測單詞的示例。通過這個任務(wù)，作者實現(xiàn)了兩個相似的單詞具有相似的嵌入，因為具有相似含義的兩個單詞很可能具有相似的鄰域單詞。

用綠色表示網(wǎng)絡(luò)。優(yōu)化后的算法能較好地預(yù)測鄰域內(nèi)的詞，具有較高的預(yù)測概率。在本例中，我們考慮距離所選單詞最遠的兩個位置的單詞。

下圖所示的skip-gram神經(jīng)網(wǎng)絡(luò)有輸入層、隱藏層和輸出層。網(wǎng)絡(luò)接受one -hot編碼。one -hot編碼是一個長度與單詞字典數(shù)量相同的向量，只有一個1其他都是0。這個1出現(xiàn)的位置是字典中出現(xiàn)編碼單詞的地方。隱藏層沒有激活函數(shù)，它的輸出是一個單詞的嵌入。輸出層是一個預(yù)測鄰域單詞的softmax分類器。

我將介紹四種圖形嵌入方法。其中三個節(jié)點嵌入節(jié)點，而一個節(jié)點用一個向量嵌入整個圖。他們將Word2vec中的嵌入原則應(yīng)用于三種方法中。

頂點嵌入方法

我將介紹在圖中嵌入節(jié)點的三種方法。之所以選擇它們，是因為它們在實踐中經(jīng)常使用，并且通常提供最好的結(jié)果。在深入討論之前，我可能會提到節(jié)點嵌入的方法可以分為三大類：因子分解方法、隨機游走方法和深度方法。

DeepWalk使用隨機游走來生成嵌入。從選定的節(jié)點開始隨機游走，然后我們從當(dāng)前節(jié)點隨機移動到鄰居，執(zhí)行一定數(shù)量的步驟。

該方法主要包括三個步驟：

抽樣：通過隨機游走對圖進行采樣。從選到的節(jié)點執(zhí)行的隨機游走很少。作者證明，從每個節(jié)點執(zhí)行32到64步隨機游走就足夠了。它們還表明，良好的隨機游走的長度約為40步。

訓(xùn)練skip-gram：隨機游走相當(dāng)于word2vec方法中的句子。skip-gram網(wǎng)絡(luò)接受隨機游走中的一個節(jié)點作為one hot向量作為輸入，最大限度地提高了預(yù)測相鄰節(jié)點的概率。它通常被訓(xùn)練來預(yù)測大約20個鄰居節(jié)點——左邊10個節(jié)點和右邊10個節(jié)點。

計算嵌入：嵌入是網(wǎng)絡(luò)隱含層的輸出，DeepWalk計算圖中每個節(jié)點的嵌入。

DeepWalk方法執(zhí)行隨機遍歷，這意味著嵌入不能很好地保留節(jié)點的局部鄰域。Node2vec方法解決了這個問題。

Node2vec是DeepWalk的一個改進，只是隨機游動的差異很小。它有參數(shù)P和Q。參數(shù)Q定義了random walk發(fā)現(xiàn)圖中未發(fā)現(xiàn)部分的概率，而參數(shù)P定義了random walk返回到前一個節(jié)點的概率。參數(shù)P控制發(fā)現(xiàn)節(jié)點周圍的微觀視圖。參數(shù)Q控制較大鄰域的發(fā)現(xiàn)。它推斷出社區(qū)和復(fù)雜的依賴關(guān)系。

圖中顯示了Node2vec中隨機行走步長的概率。我們只是從紅結(jié)點到綠結(jié)點跨了一步。返回到紅色節(jié)點的概率為1/P，而返回到與前一個(紅色)節(jié)點沒有連接的節(jié)點的概率為1/Q。到紅結(jié)點相鄰結(jié)點的概率是1。

嵌入的其他步驟與DeepWalk方法相同。

結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入(SDNE)與前兩種方法沒有任何共同之處，因為它不執(zhí)行隨機游走。我之所以提到它，是因為它在不同任務(wù)上的表現(xiàn)非常穩(wěn)定。

它的設(shè)計使得嵌入保持了一階和二階的接近性。一階近似是由邊連接的節(jié)點之間的局部成對相似性。它描述了局部網(wǎng)絡(luò)結(jié)構(gòu)。如果網(wǎng)絡(luò)中的兩個節(jié)點與邊緣連接，則它們是相似的。當(dāng)一篇論文引用了另一篇論文，這意味著它們涉及了類似的主題。二階鄰近度表示節(jié)點鄰域結(jié)構(gòu)的相似性。它捕獲了全球網(wǎng)絡(luò)結(jié)構(gòu)。如果兩個節(jié)點共享許多鄰居，它們往往是相似的。

作者提出了一個自動編碼器神經(jīng)網(wǎng)絡(luò)，它有兩個部分。自編碼器(左、右網(wǎng)絡(luò))接受節(jié)點鄰接向量，訓(xùn)練自編碼器重構(gòu)節(jié)點鄰接。這些自動編碼器被稱為vanilla自動編碼器，它們學(xué)習(xí)二階近似。鄰接向量(鄰接矩陣中的一行)在表示連接到所選節(jié)點的節(jié)點的位置上具有正值。

還有一個網(wǎng)絡(luò)的監(jiān)督部分——左翼和右翼之間的聯(lián)系。它計算從左到右的嵌入距離，并將其包含在網(wǎng)絡(luò)的共同損失中。網(wǎng)絡(luò)經(jīng)過這樣的訓(xùn)練，左、右自動編碼器得到所有由輸入邊連接的節(jié)點對。距離部分的損失有助于保持一階近似。

網(wǎng)絡(luò)的總損失是由左右自編碼器的損失和中間部分的損失之和來計算的。

圖嵌入方法

最后一種方法對整個圖進行了嵌入。它計算一個描述圖形的向量。我選擇graph2vec方法，因為據(jù)我所知，它是圖形嵌入的最佳方法。

Graph2vec基于doc2vec方法的思想，該方法使用了skip-gram網(wǎng)絡(luò)。它在輸入上獲取文檔的ID，并經(jīng)過訓(xùn)練得到最大化從文檔中預(yù)測隨機單詞的概率。

Graph2vec方法包括三個步驟：

從圖中采樣并重新標(biāo)記所有子圖。子圖是出現(xiàn)在所選節(jié)點周圍的一組節(jié)點。子圖中的節(jié)點距離不超過所選邊數(shù)。

訓(xùn)練跳躍圖模型。圖類似于文檔。由于文檔是一組單詞，所以圖是一組子圖。在此階段，對skip-gram模型進行訓(xùn)練。它被訓(xùn)練來最大限度地預(yù)測存在于輸入圖中的子圖的概率。輸入圖作為獨熱向量。

計算嵌入提供一個圖形ID作為獨熱向量作為輸入。嵌入是隱藏層的結(jié)果。

由于任務(wù)是預(yù)測子圖，具有相似子圖和相似結(jié)構(gòu)的圖具有相似的嵌入。

其他的嵌入方法

我提出了四種文獻中常用的方法。由于這個主題目前非常流行，所以可以使用更多的方法。這里我列出了其他可用的方法：

頂點嵌入方法：LLE，拉普拉斯特征映射，圖分解，GraRep, HOPE, DNGR, GCN, LINE

圖嵌入方法：Patchy-san, sub2vec (embed subgraphs)， WL kernel和deep WL kernel