圖嵌入的用處和方法

導(dǎo)讀

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

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

什么是圖嵌入？

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

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

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

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

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

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

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

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

向量運(yùn)算比圖上的運(yùn)算更簡(jiǎn)單、更快。

挑戰(zhàn)

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

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

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

一個(gè)基本的挑戰(zhàn)是決定嵌入維數(shù)。較長(zhǎng)的嵌入保存了更多的信息，同時(shí)它們比排序器嵌入帶來(lái)更高的時(shí)間和空間復(fù)雜度。用戶需要根據(jù)需求做出權(quán)衡。在文章中，他們通常報(bào)告說(shuō)，嵌入大小在128到256之間就足夠完成大多數(shù)任務(wù)。在Word2vec方法中，他們選擇了嵌入長(zhǎng)度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ò)具有一個(gè)隱含層的神經(jīng)網(wǎng)絡(luò)。skip-gram被訓(xùn)練來(lái)預(yù)測(cè)句子中的相鄰單詞。這個(gè)任務(wù)被稱(chēng)為偽任務(wù)，因?yàn)樗皇窃谟?xùn)練階段使用。網(wǎng)絡(luò)在輸入端接受單詞，并對(duì)其進(jìn)行優(yōu)化，使其能夠以較高的概率預(yù)測(cè)句子中的相鄰單詞。下圖顯示了輸入單詞(用綠色標(biāo)記)和預(yù)測(cè)單詞的示例。通過(guò)這個(gè)任務(wù)，作者實(shí)現(xiàn)了兩個(gè)相似的單詞具有相似的嵌入，因?yàn)榫哂邢嗨坪x的兩個(gè)單詞很可能具有相似的鄰域單詞。

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

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

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

頂點(diǎn)嵌入方法

我將介紹在圖中嵌入節(jié)點(diǎn)的三種方法。之所以選擇它們，是因?yàn)樗鼈冊(cè)趯?shí)踐中經(jīng)常使用，并且通常提供最好的結(jié)果。在深入討論之前，我可能會(huì)提到節(jié)點(diǎn)嵌入的方法可以分為三大類(lèi)：因子分解方法、隨機(jī)游走方法和深度方法。

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

該方法主要包括三個(gè)步驟：

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

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

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

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

Node2vec是DeepWalk的一個(gè)改進(jìn)，只是隨機(jī)游動(dòng)的差異很小。它有參數(shù)P和Q。參數(shù)Q定義了random walk發(fā)現(xiàn)圖中未發(fā)現(xiàn)部分的概率，而參數(shù)P定義了random walk返回到前一個(gè)節(jié)點(diǎn)的概率。參數(shù)P控制發(fā)現(xiàn)節(jié)點(diǎn)周?chē)奈⒂^視圖。參數(shù)Q控制較大鄰域的發(fā)現(xiàn)。它推斷出社區(qū)和復(fù)雜的依賴(lài)關(guān)系。

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

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

結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入(SDNE)與前兩種方法沒(méi)有任何共同之處，因?yàn)樗粓?zhí)行隨機(jī)游走。我之所以提到它，是因?yàn)樗诓煌蝿?wù)上的表現(xiàn)非常穩(wěn)定。

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

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

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

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

圖嵌入方法

最后一種方法對(duì)整個(gè)圖進(jìn)行了嵌入。它計(jì)算一個(gè)描述圖形的向量。我選擇graph2vec方法，因?yàn)閾?jù)我所知，它是圖形嵌入的最佳方法。

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

Graph2vec方法包括三個(gè)步驟：

從圖中采樣并重新標(biāo)記所有子圖。子圖是出現(xiàn)在所選節(jié)點(diǎn)周?chē)囊唤M節(jié)點(diǎn)。子圖中的節(jié)點(diǎn)距離不超過(guò)所選邊數(shù)。

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

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

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

其他的嵌入方法

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

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

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