導讀

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

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

什么是圖嵌入？

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

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

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

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

我們為什么要用到圖嵌入？

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

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

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

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

挑戰

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

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

網絡的大小不應降低嵌入過程的速度。圖通常很大。想象一下擁有數百萬人的社交網絡。好的嵌入方法需要在大型圖上有效。

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

Word2vec

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

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

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

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

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

頂點嵌入方法

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

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

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

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

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

計算嵌入：嵌入是網絡隱含層的輸出，DeepWalk計算圖中每個節點的嵌入。

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

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

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

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

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

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

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

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

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

圖嵌入方法

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

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

Graph2vec方法包括三個步驟：

從圖中采樣并重新標記所有子圖。子圖是出現在所選節點周圍的一組節點。子圖中的節點距離不超過所選邊數。

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

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

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

其他的嵌入方法

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

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

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