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

RandomWalk

Skip-Gram

RandomWalk是一種可重復(fù)訪問已訪問節(jié)點(diǎn)的深度優(yōu)先遍歷算法。給定當(dāng)前訪問起始節(jié)點(diǎn)，從其鄰居中隨機(jī)采樣節(jié)點(diǎn)作為下一個(gè)訪問節(jié)點(diǎn)，重復(fù)此過程，直到訪問序列長(zhǎng)度滿足預(yù)設(shè)條件。

算法過程就是輸入一個(gè)圖，輸出節(jié)點(diǎn)表示的矩陣，簡(jiǎn)單對(duì)步驟進(jìn)行解析：

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

構(gòu)建一棵二叉樹Hierarchical Softmax

開始做 $\gamma$ 步的隨機(jī)游走，這里的 $\gamma$ 是初始化好的超參數(shù)

打亂采樣得到的節(jié)點(diǎn)

這個(gè)循環(huán)是開始以每個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)開始做長(zhǎng)度為 $t$ 的隨機(jī)游走，這里的 $t$ 為初始化的超參數(shù)。然后按窗口 $w$ 進(jìn)行SkipGram學(xué)習(xí)文本序列

SkipGram

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

SkipGram就是用當(dāng)前詞來預(yù)測(cè)上下文。丟掉了詞序并且不考慮與當(dāng)前詞的距離。優(yōu)化目標(biāo)是最大化同一個(gè)句子中同時(shí)出現(xiàn)的詞的共現(xiàn)概率：

預(yù)測(cè)給到的詞從整個(gè)詞表vocabulary中選擇，因此在輸出的時(shí)候會(huì)計(jì)算softmax進(jìn)行選擇，維度為 $|V|$ ，計(jì)算的維度會(huì)非常大，因此采用Hierarchical Softmax來構(gòu)建二叉樹進(jìn)行選擇，每個(gè)詞就只需要計(jì)算 $log_2^{|V|}$ 次。

Node2Vec

node2vec依然采用的是隨機(jī)游走的方式獲取頂點(diǎn)的臨近頂點(diǎn)序列，但不同的是node2vec采用的是一種有偏的隨機(jī)游走。給定當(dāng)前頂點(diǎn) $v$，訪問下一個(gè)頂點(diǎn)的概率是：

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

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

Graph Convolutional Network

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

圖中的每個(gè)結(jié)點(diǎn)無時(shí)無刻不因?yàn)猷従雍透h(yuǎn)的點(diǎn)的影響而在改變著自己的狀態(tài)直到最終的平衡，關(guān)系越親近的鄰居影響越大。

實(shí)際上從鄰居節(jié)點(diǎn)獲取信息的思想在很多領(lǐng)域都有應(yīng)用，例如：word2vec和pagerank。很多參考的理解描述了更加細(xì)節(jié)的數(shù)學(xué)原理：從傅立葉變換到拉普拉斯算子到拉普拉斯矩陣。很難理解。

責(zé)任編輯：haq