導讀

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

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

什么是圖嵌入？

圖嵌入是將屬性圖轉換為一個或一組向量。嵌入應該捕獲圖的拓撲結構、頂點到頂點的關系以及關于圖、子圖和頂點的其他相關信息。更多的屬性嵌入編碼可以在以后的任務中獲得更好的結果。我們大致可以將嵌入分為兩組：

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

圖嵌入：這里我們用一個向量表示整個圖。當我們想要在圖的層次上做出預測時，以及當我們想要比較或可視化整個圖時，例如比較化學結構時，就會用到這些嵌入。

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

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

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

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

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

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

挑戰(zhàn)

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

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

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

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

Word2vec

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

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

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

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

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

頂點嵌入方法

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

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

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

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

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

計算嵌入：嵌入是網(wǎng)絡隱含層的輸出，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ū)和復雜的依賴關系。

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

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

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

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

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

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

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

圖嵌入方法

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

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

Graph2vec方法包括三個步驟：

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

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

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

由于任務是預測子圖，具有相似子圖和相似結構的圖具有相似的嵌入。

其他的嵌入方法

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

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

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