圖嵌入方法介紹
原標題 |Graph Embeddings — The Summary
作 者 |Primo? Godec
翻 譯 |季一帆
審 校| 鳶尾、唐里
圖源：Pixabay — geralt
在現實世界的各種場景中，圖處處可見。社交網路是在人與人構建連接的圖，生物學家使用圖描述蛋白質分子的交互，通信網路本身就以圖的形式存在。在文本挖掘中還會使用詞共現圖進行分析。毫無疑問，在圖數據上探索機器學習受到越來越多的關注。人們試圖通過以此預測社交網路中的新朋友或是發現蛋白質分子新的性質與功能。然而，無論數學家還是統計學家都無法直接在圖上進行計算的，如何將圖數據處理成可直接應用於機器學習的數據是一項極大的挑戰。在這樣的背景下，圖嵌入方法被提出。
什麼是圖嵌入？
圖嵌入是將屬性圖轉換為一個向量（圖)或者一組向量（頂點)。好的嵌入應該儘可能的捕獲圖拓撲結構、頂點之間的關係以及其他一些關於圖/子圖/頂點的信息。儘可能多的捕獲相關屬性會產生更好的嵌入，對下游任務會很有幫助。一般來說，我們可以將圖嵌入大致分為兩類：
頂點嵌入：將圖中的每一個頂點向量化表示。當我們想在節點層次上進行可視化或預測任務的時候就會做頂點嵌入，比如說在2維平面上可視化頂點或者基於頂點之間的相似度預測頂點之間是否連接。
圖嵌入：將整個圖表示成一個向量。當我們對整個圖做預測任務或是與其他圖比較，又或者可視化整張圖，例如比較分子結構時， 我們就進行圖嵌入。
接下來，我們會分別介紹實現這兩種嵌入的方法。頂點嵌入：DeepWalk、node2vec、SDNE方法；圖嵌入：graph2vec。
為什麼必須圖嵌入？
圖是一種信息豐富且易於理解的數據結構，在機器學習中必須對圖進行嵌入的原因如下：
直接在圖上進行機器學習是很困難的。圖由邊和節點組成， 數學、統計學和機器學習方法只能部分處理圖數據，而在向量空間可以更充分的利用圖數據。
嵌入是壓縮表示。鄰接矩陣描述圖中頂點的連接關係，大小為|V| x |V|，其中V為頂點個數。在鄰接矩陣中，非零值表示對應行和列的兩個節點之間有邊。然而對節點數眾多的圖來說，使用鄰接矩陣對圖進行描述是不現實的。想像一下有1M節點的圖，其鄰接矩陣大小會是1M x 1M。基於嵌入的矩陣通過低維向量表示節點，可以避免這種情況。
相對於在圖上比較屬性，在嵌入空間中處理向量更加方便快捷。
挑戰
嵌入方法需要滿足很多要求。在這裡我向大家介紹進行嵌入時面臨的三種主要挑戰：
確保嵌入表示能夠很好的描述圖的屬性，主要包括圖的拓撲結構、頂點連接、頂點周圍節點等。嵌入表示的好壞對後續預測或可視化任務的結果有很大的影響。
嵌入速度應該與圖的大小無關。通常圖都是非常大的，比如社交網路就有超過數百萬人的頂點。好的嵌入方法應該能高效處理這樣的大圖。
嵌入維度也是非常關鍵的問題。更大的維度會保存更多的信息，同時也會花費更多的時間與存儲空間。實驗者應該根據自己的需求選取恰當的嵌入維度。在論文中，作者們一般會將嵌入維度設置為128或256，對多數任務來說這個維度就差不多了。另外你還需要知道，word2vec中作者做得是300維的嵌入。
Word2vec
在介紹圖嵌入之前，我們有必要了解Word2vec和Skip-gram神經網路，這是理解圖嵌入的基礎。如果你還想更深入的了解這些方法，可以查看這篇教程（http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/）或是該視頻（https://www.youtube.com/watch?v=ERibwqs9p38）。
Word2vec是將單詞轉化為嵌入向量的方法。相似的詞應具有相似的嵌入。Word2vec使用只有一個隱藏層的skip-gram神經網路進行訓練。訓練的目標是預測句子中當前詞的相鄰詞。由於這樣的任務只會在訓練階段出現，skip-gram的上下文單詞預測也被稱為偽任務。網路的輸入為一個單詞，通過優化最大化該單詞在句子中相鄰單詞的概率。下圖顯示了這一任務，其中標有綠色的是輸入單詞，通過網路預測其前後各兩個詞。通過這樣的訓練，具有相似含義的兩個詞很可能具有相似的鄰域詞，於是得到相似的嵌入表示。
註：綠色標記的單詞是網路的輸入，通過skip-gram優化使其相鄰單詞的概率最大化。在上圖中，我們考慮所選單詞前後各兩個單詞的出現概率。
如下圖所示，skip-gram神經網路由輸入層、一個隱藏層和輸出層組成。輸入層輸入當前詞的one-hot編碼（one-hot編碼是長度為字典數量的向量，其中除當前詞位置為1外其餘位均為0）；隱藏層沒有激活函數，該層輸出表示單詞的嵌入；輸出層通過softmax分類器輸出鄰域詞的預測概率。想要了解更多詳細信息可以看我之前的教程（http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/）。
Skip-gram神經網路
接下來，我將介紹四種圖嵌入方法，包括三種節點嵌入方法、一種整個圖嵌入方法。這些方法是在word2vec的思想上進行了一些有趣的嘗試。
頂點嵌入方法
這一部分我會介紹三種節點嵌入的方法，這三種方法在實踐中經常被使用，而且通常會產生最好的效果。在深入探討之前，你需要知道，節點嵌入的方法可以分為三大類：分解，隨機遊走和深度學習。
DeepWalk通過隨機遊走的方式生成頂點嵌入。隨機遊走就是從一個頂點出發，隨機移動到它的一個鄰居節點，將該節點作為新的當前節點，如此循環執行若干步，得到一條遊走路徑。
DeepWalk主要可分為三個步驟：
採樣：通過隨機遊走對圖形進行採樣。每個頂點只需要隨機遊走若干次就可以。原始論文中作者表明，從每個頂點執行32到64次隨機遊走就基本足夠了，此外還特別說明，一般每個頂點隨機遊走四十次效果最好。
訓練skip-gram：可以將隨機遊走得到頂點路徑類比為word2vec中的句子。skip-gram將隨機遊走的一個頂點的one-hot向量作為輸入，並最大化其相鄰節點的預測概率。訓練中通常預測20個鄰居節點-左側10個節點，右側10個節點。
計算嵌入：網路隱藏層的輸出即為頂點嵌入。DeepWalk對圖中的所有頂點計算嵌入。
DeepWalk圖示
由於DeepWalk採用隨機遊走策略，無法很好地保留節點的局部信息。Node2vec可以解決這個問題。
Node2vec是對DeepWalk的改進，雖然也是基於隨機遊走但卻不同於完全隨機，它多了兩個參數P和Q。參數Q確定隨機遊走時選擇新頂點的可能性，而參數P確定隨機遊走時返回之前頂點的可能性。參數P使隨機遊走更多的關注頂點領域的信息（也就是傾向廣度優先搜索），參數Q則選擇更深更遠的信息發現（也就是傾向深度優先搜索）。因此，node2vec可以獲取鄰域信息和更複雜的依存信息。
上圖顯示了Node2vec中隨機行走的概率。假設前一步是從紅色節點遊走到綠色節點，那麼此時返回紅色節點的概率為1 / P，到達未與先前紅色節點連接的節點的概率為1 / Q，到達紅色節點鄰居的概率為1。
其餘步驟於DeepWalk基本相同。
結構深層網路嵌入（SDNE）完全不同於前兩種方法，它並不是基於隨機遊走。之所以介紹這種方法是因為它在不同任務上的表現都非常穩定。
SDNE在嵌入中同時保留一階和二階相似度。一階接近相似度是由邊鏈接節點間的局部成對相似性，表徵本地網路結構。如果網路中的兩個節點間有邊，則它們是相似的，例如當一篇論文引用另一篇論文時，意味著它們涉及相似的主題。二階相似度表示節點鄰域結構的相似性，它捕獲全局網路結構。如果兩個節點共享許多鄰居，它們往往是相似的。
作者介紹了一種自動編碼器神經網路-如下圖所示，該網路由兩部分組成，左右的自動編碼器均接收節點的鄰接向量，並進行訓練以重建節點鄰接。這些自動編碼器被稱為vanilla自動編碼器，能夠學習二階相似度。某點與當前節點存在邊那麼對應鄰接向量（鄰接矩陣的一行）位置為正。
該網路結構中左右兩部分之間的連接是受監督的部分。它計算左側嵌入和右側嵌入間的距離，並將其統計到網路的公共損失中。將所有相互連接的節點對分別作為左右自動編碼器的輸入，通過儘可能減小損失保持一階相似度。
在該結構中，網路的總損失=左自動編碼器的損失 右自動編碼器的損失 中間連接的損失。
圖嵌入方法
最後介紹一種對整個圖嵌入的方法，也就是通過一個向量表示整個圖。我只介紹graph2vec這一種方法，因為據我所知，這是最好的圖嵌入方法。
Graph2vec借鑒doc2vec（https://medium.com/scaleabout/a-gentle-introduction-to-doc2vec-db3e8c0cce5e）的思想使用skip-gram網路進行訓練。doc2vector獲取文檔的ID作為輸入，經過訓練使文檔中每個隨機預測的單詞概率最大化。
Graph2vec包括三步：
採樣並重新標記圖中的所有子圖。子圖是出現在所選節點周圍的一組節點，通常來說來說，這些節點距離所選節點不會太遠。
訓練skip-gram模型。圖與文檔十分相似，文檔是單片語成的集合，圖則是子圖構成的集合。於是，可以通過最大化輸入圖子圖的概率的方法對skip-gram進行訓練。最終， 可以得到輸入圖的one-hot向量表示。
訓練完成後，只需提供圖的ID就可以得到該圖的one-hot向量， 隱藏層就是嵌入結果。
由於圖嵌入是通過子圖實現，因此具有相似子圖和結構的圖的嵌入表示更為接近。
其他嵌入方法
本文介紹了常用的四種圖嵌入方法。然而當前圖嵌入非常火熱，其他很多嵌入方法也被提出。這裡我簡單列出其他一些未介紹的方法，有興趣的同學可以去做更深入的了解：
頂點嵌入：LLE, Laplacian Eigenmaps, Graph Factorization, GraRep, HOPE, DNGR, GCN, LINE
圖嵌入: Patchy-san, sub2vec (embed subgraphs), WL kernel andDeep WL kernels
參考資料
[1] C. Manning, R. Socher, Lecture 2 | Word Vector Representations: word2vec (2017), YouTube.
[2] B. Perozzi, R. Al-Rfou, S. Skiena, DeepWalk: Online Learning of Social Representations (2014), arXiv:1403.6652.
[3] C. McCormick. Word2Vec Tutorial — The Skip-Gram Model (2016), http://mccormickml.com.
[4] T. Mikolov, K. Chen, G. Corrado, J. Dean, Efficient Estimation of Word Representations in Vector Space (2013), arXiv:1301.3781.
[5] A. Narayanan, M. Chandramohan, R. Venkatesan, L. Chen, Y. Liu, S. Jaiswal, graph2vec: Learning Distributed Representations of Graphs (2017),arXiv:1707.05005.
[6] P. Goyal, E. Ferrara, Graph Embedding Techniques, Applications, and Performance: A Survey (2018), Knowledge-Based Systems.
[7] D. Wang, P. Cui, W. Zhu, Structural Deep Network Embedding (2016), Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.
[8] A. Grover, J. Leskovec, node2vec: Scalable Feature Learning for Networks (2016), Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.
via https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
