本文主要記錄一些經典的基于随機遊走Graph Embedding方法，以及自己的一些實踐經驗。
-
-
- 引言
-
- a. 獨熱表示（one-hot representation）
- b. 分布式表示（distributed representation）
- c. 圖和embedding？
- 1.deepwalk
-
- 1.1 随機遊走
- 1.2 向量學習
- 2.node2vec
-
- 2.1 DFS和BFS随機遊走
- 2.2 參數p、q對遊走政策的影響
- 2.3 node2vec學習同質性和結構性
- 2.4 向量學習
- 3.metapath2vec
-
- 3.1 Meta-Path-Based Random Walks
- 3.2 Heterogeneous negative sampling
- 4.EGES
- 總結對比
-
引言
在NLP領域，關于如何對詞進行更好的表示，有許多研究者進行了深入的研究。
a. 獨熱表示（one-hot representation）
将每一個表示成一個N維（N是詞表大小）的向量，其中隻有目前詞對應的次元為1，其他為零。一般來說詞表會比較大（至少是十萬量級），是以高維稀疏的表示會導緻維數災難。還有一個重要的問題是，獨熱表示無法描述詞與詞之間的相似性，也就是我們常說的語義鴻溝。
b. 分布式表示（distributed representation）
既然獨熱表示有這麼大的問題，總是需要去解決的。于是人們提出了分布式表示，即用低維稠密的向量來表示。低維稠密向量解決次元過高的問題；同時稠密向量可以計算向量之間的距離（相似度），解決語義鴻溝問題。
既然我們想通過低維稠密的向量來表示詞，那麼接下來就是用什麼方法得到我們想要的向量了。要相信方法總是比問題多的，我在此列舉一些經典的預訓練詞向量方法：word2vec、glove、ELMo、GPT以及BERT等等。
c. 圖和embedding？
在很多場景下，業務問題可以抽象成圖結構，如搜尋點選二部圖、社交網絡、交通網絡、電商網站中使用者與物品的關系等。
1.deepwalk
deepwalk是14年KDD paper: DeepWalk：Online Learning of Social Representations
核心思路： 1) 在圖中随機遊走采樣，擷取節點序列；2) 使用skip-gram + Hierarchical Softmax方式學習節點表達向量。
1.1 随機遊走
1.2 向量學習
把每條遊走後的序列當作句子，每個節點看作一次詞，利用skip-gram語言模型進行學習，且采用Hierarchical Softmax提升訓練效率。
2.node2vec
node2vec是16年KDD paper: node2vec: Scalable Feature Learning for Networks
整體思路和deepwalk一緻，可以看作是deepwalk的改進版。主要對deepwalk的随機遊走政策進行了改進，可以看作是引入DFS和BFS随機遊走的deepwalk。
2.1 DFS和BFS随機遊走
node2vec采用的是一種有偏的随機遊走，給定目前頂點 v v v，通路下一個頂點 x x x 的機率為 P ( c i = x ∣ c i − 1 = v ) P(c_i = x | c_{i-1} = v) P(ci=x∣ci−1=v)
其中 π v x = α p , q ( t , x ) ∗ w v x \pi_{vx} = \alpha_{p,q}(t,x) * w_{vx} πvx=αp,q(t,x)∗wvx，且 w v x w_{vx} wvx 是頂點 v v v 和 x x x之間的邊權重， α p , q ( t , x ) \alpha_{p,q}(t,x) αp,q(t,x)是表示DFS、BFS遊走政策。
d t x d_{tx} dtx為頂點 t t t 和頂點 x x x 之間的最短路徑距離
2.2 參數p、q對遊走政策的影響
Return parameter：p
參數 p p p 控制重複通路剛剛通路過的頂點的機率(即 d t x = 0 d_{tx}=0 dtx=0時)，若 p p p 較大，則通路剛剛通路過的頂點的機率越低，反之越高。
In-out papameter：q
參數 q q q 控制着遊走偏向，如果 q > 1 q>1 q>1 ，随機遊走傾向于BFS；若 q < 1 q<1 q<1 ，随機遊走傾向于DFS。
2.3 node2vec學習同質性和結構性
同質性指的是距離相近節點的embedding應該盡量近似，例如節點u和s1、s2、s3、s4應該屬于同質性相似的節點；
結構性指的是結構上相似的節點的embedding應該盡量接近，例如節點u和節點s6應該屬于結構性相似的節點。
上圖是DFS結果，下圖是BFS結果，顔色接近的節點代表其embedding的相似性更強。
2.4 向量學習
遊走完得到節點序列後，向量學習的方法和deepwalk方式一緻，在此不做贅述。
3.metapath2vec
metapath2vec是17年KDD paper: metapath2vec: Scalable Representation Learning for Heterogeneous Networks
上面所介紹的deepwalk，node2vec等算法雖然可以用于網絡表示學習，但僅适合那些隻包含一類頂點類型和邊類型的同構網絡（Homogeneous Networks），并不能很好地用于包含多種頂點類型和邊類型的複雜關系網絡。于是作者在基于meta-path的基礎上，提出了能很好應對指定scheme結構的異構複雜關系網絡的表示學習方法。
3.1 Meta-Path-Based Random Walks
在同構網絡中，DeepWalk和node2vec等算法通過随機遊走的方式來建構Skip-Gram模型的上下文語料庫。論文作者提出了一種基于meta-path的随機遊走方式，本質上就是遊走過程中将節點類型做為限制。
3.2 Heterogeneous negative sampling
模型依然是skip-gram結構，将word2vec原版的negative sampling改進為Heterogeneous negative sampling，即負樣本不再是從所有節點中選取，而是從某一特定類别的節點中進行随機選取。
4.EGES
EGES是18年KDD paper: Billion-scale commodity embedding for e-commerce recommendation in alibaba
主要亮點：引入節點的side information。
主要流程如下面兩張圖所示：
總結對比
| 方法 | 核心思路 | code |
|---|---|---|
| deepwalk(2014 KDD) | 随機遊走+skip-gram | python原版 、c++版 |
| node2vec(2016 KDD) | 基于DFS和BFS的随機遊走+skip-gram | 原版、斯坦福snap |
| metapath2vec(2017 KDD) | 基于meta-path的異構網絡随機遊走，Heterogeneous negative sampling | 原版 |
| EGES(2018 KDD) | 使用者行為序列構成有向圖，引入節點的side information | python實作版 |