在數據量越來越大的今天，word2vec是通過字詞的共現關系來學習字詞的向量表示，Graph Embeding的思想類似于word2vec，通過圖中節點與節點的共現關系來學習節點的向量表示，構成文本序列從而計算相互關聯出現的詞的概率，從而計算詞向量表示文本。那么在圖模型中的關鍵的問題就是如何來描述節點與節點的共現關系，于是方法是利用DeepWalk來采樣這樣的文本序列，通過隨機游走(RandomWalk)的方式在圖中進行節點采樣，從而就能夠輸入序列計算圖的向量表示。所以deepwalk算法核心的步驟就是兩步：

RandomWalk

Skip-Gram

RandomWalk是一種可重復訪問已訪問節點的深度優先遍歷算法。給定當前訪問起始節點，從其鄰居中隨機采樣節點作為下一個訪問節點，重復此過程，直到訪問序列長度滿足預設條件。

算法過程就是輸入一個圖，輸出節點表示的矩陣，簡單對步驟進行解析：

初始化：從 $\mathcal{U}^{|V| \times d}$ 樣本空間中采樣，embedding的大小為 $d$

構建一棵二叉樹Hierarchical Softmax

開始做 $\gamma$ 步的隨機游走，這里的 $\gamma$ 是初始化好的超參數

打亂采樣得到的節點

這個循環是開始以每個節點為根節點開始做長度為 $t$ 的隨機游走，這里的 $t$ 為初始化的超參數。然后按窗口 $w$ 進行SkipGram學習文本序列

SkipGram

一般提到word2vec有兩種主要的算法，Cbow和Skip-Gram，都是在統計語言模型的基礎上計算一個詞在文本中出現的概率用來作為這個詞的表示向量，于是優化目標就是最大化$Pr(w_n|w_0,w_1,...,w_{n-1})$ 。 $w$ 表示的就是詞。

SkipGram就是用當前詞來預測上下文。丟掉了詞序并且不考慮與當前詞的距離。優化目標是最大化同一個句子中同時出現的詞的共現概率：

預測給到的詞從整個詞表vocabulary中選擇，因此在輸出的時候會計算softmax進行選擇，維度為 $|V|$ ，計算的維度會非常大，因此采用Hierarchical Softmax來構建二叉樹進行選擇，每個詞就只需要計算 $log_2^{|V|}$ 次。

Node2Vec

node2vec依然采用的是隨機游走的方式獲取頂點的臨近頂點序列，但不同的是node2vec采用的是一種有偏的隨機游走。給定當前頂點 $v$，訪問下一個頂點的概率是：

$\pi{vx}$ 是頂點 $v$ 到頂點 $x$ 之間的轉移概率， $Z$ 是歸一化參數。 node2vec引入兩個超參數 $p$ 和 $q$ 來控制隨機游走的策略，假設當前隨機游走經過邊 $(v, x) $ 到達頂點 $t$ ，設 $\pi{vx}=\alpha{pq}(t, x)\cdot w{vx}$ ， $w_{vx}$ 是頂點 $v$ 和 $x$ 之間的邊權。

$d{tx}$ 為頂點 $t$ 和頂點 $x$ 之間的最短路徑距離。參數$p$和參數$q$的意義：控制重復訪問剛剛訪問過的頂點的概率。$p$作用于$d{tx}=0$，表達的意義就是頂點$x$就是訪問當前頂點$v$之前剛剛訪問過的頂點。如果$p$較高，則訪問剛剛訪問過的頂點的概率會變低，反之變高。$q$控制著游走是向外還是向內，如果$q>1$，隨機游走傾向于訪問和節點$t$相接近的頂點（類似于$BFS$）。如果$q<1$，則傾向于訪問遠離$t$的頂點（類似于$DFS$）。

Graph Convolutional Network

Graph Embedding的意義就在于能夠利用圖結構處理非結構化數據，因此在cv和nlp領域能夠更進一步結合先驗知識進行特征學習，因此是深度學習領域的重要發展方向。定義圖$G=(V,E)$，$V$為節點的集合，$E$為邊的集合，對于每個節點$i$， 均有其特征$x_i$，特征矩陣可以用$X_{N*D}$來表示，其中$N$表示節點數，$D$表示每個節點的特征編碼尺寸，在nlp應用中就是embedding_size。對于圖的理解有一個經典的思想：

圖中的每個結點無時無刻不因為鄰居和更遠的點的影響而在改變著自己的狀態直到最終的平衡，關系越親近的鄰居影響越大。

實際上從鄰居節點獲取信息的思想在很多領域都有應用，例如：word2vec和pagerank。很多參考的理解描述了更加細節的數學原理：從傅立葉變換到拉普拉斯算子到拉普拉斯矩陣。很難理解。

責任編輯：haq