【Graph Embedding】DeepWalk：演算法原理，實現和應用
放假前在學校看了一點graph embedding的東西，後面打算大概用幾篇文章做一些簡單的記錄。?Deepwalk之前的一些經典方法就不寫了(我也沒看)，按師兄的話說就是可以適當的放下歷史的包袱。時間有限，我們要向前看，擁抱未來(其實現在還是在看一兩年前的東西，想跟上潮流真的是難~)。
本文首先從整體介紹一下圖表示學習，然後分別從原理，核心代碼，應用三個部分介紹DeepWalk。
圖表示學習
我們都知道在數據結構中，圖是一種基礎且常用的結構。現實世界中許多場景可以抽象為一種圖結構，如社交網路，交通網路，電商網站中用戶與物品的關係等。
目前提到圖演算法一般指：
1. 經典數據結構與演算法層面的：最小生成樹(Prim,Kruskal,...)，最短路(Dijkstra,Floyed,...)，拓撲排序，關鍵路徑等
2. 概率圖模型，涉及圖的表示，推斷和學習，詳細可以參考Koller的書或者公開課
3. 圖神經網路，主要包括Graph Embedding(基於隨機遊走)和Graph CNN(基於鄰居匯聚)兩部分。
這裡先看下Graph Embedding的相關內容。
Graph Embedding技術將圖中的節點以低維稠密向量的形式進行表達，要求在原始圖中相似(不同的方法對相似的定義不同)的節點其在低維表達空間也接近。得到的表達向量可以用來進行下游任務，如節點分類，鏈接預測，可視化或重構原始圖等。
DeepWalk 演算法原理
雖然DeepWalk是KDD 2014的工作，但卻是我們瞭解Graph Embedding無法繞過的一個方法。
我們都知道在NLP任務中，word2vec是一種常用的word embedding方法，word2vec通過語料庫中的句子序列來描述詞與詞的共現關係，進而學習到詞語的向量表示。
DeepWalk的思想類似word2vec，使用圖中節點與節點的共現關係來學習節點的向量表示。那麼關鍵的問題就是如何來描述節點與節點的共現關係，DeepWalk給出的方法是使用隨機遊走(RandomWalk)的方式在圖中進行節點採樣。
RandomWalk是一種可重複訪問已訪問節點的深度優先遍歷演算法。給定當前訪問起始節點，從其鄰居中隨機採樣節點作為下一個訪問節點，重複此過程，直到訪問序列長度滿足預設條件。
獲取足夠數量的節點訪問序列後，使用skip-gram model 進行向量學習。
DeepWalk 核心代碼
DeepWalk演算法主要包括兩個步驟，第一步為隨機遊走採樣節點序列，第二步為使用skip-gram modelword2vec學習表達向量。
①構建同構網路，從網路中的每個節點開始分別進行Random Walk 採樣，得到局部相關聯的訓練數據； ②對採樣數據進行SkipGram訓練，將離散的網路節點表示成向量化，最大化節點共現，使用Hierarchical Softmax來做超大規模分類的分類器
Random Walk
我們可以通過並行的方式加速路徑採樣，在採用多進程進行加速時，相比於開一個進程池讓每次外層循環啟動一個進程，我們採用固定為每個進程分配指定數量的num_walks的方式，這樣可以最大限度減少進程頻繁創建與銷毀的時間開銷。
deepwalk_walk方法對應上一節偽代碼中第6行，_simulate_walks對應偽代碼中第3行開始的外層循環。最後的Parallel為多進程並行時的任務分配操作。
def deepwalk_walk(self, walk_length, start_node):
walk = [start_node]
while len(walk) < walk_length:
cur = walk[-1]
cur_nbrs = list(self.G.neighbors(cur))
if len(cur_nbrs) > 0:
walk.append(random.choice(cur_nbrs))
else:
break
return walk
def _simulate_walks(self, nodes, num_walks, walk_length,):
walks = []
for _ in range(num_walks):
random.shuffle(nodes)
for v in nodes:
walks.append(self.deepwalk_walk(alk_length=walk_length, start_node=v))
return walks
results = Parallel(n_jobs=workers, verbose=verbose, )(
delayed(self._simulate_walks)(nodes, num, walk_length) for num in
partition_num(num_walks, workers))
walks = list(itertools.chain(*results))
Word2vec
這裡就偷個懶直接用gensim裏的Word2Vec了。
from gensim.models import Word2Vec
w2v_model = Word2Vec(walks,sg=1,hs=1)
DeepWalk應用
這裡簡單的用DeepWalk演算法在wiki數據集上進行節點分類任務和可視化任務。 wiki數據集包含 2,405 個網頁和17,981條網頁之間的鏈接關係，以及每個網頁的所屬類別。
本例中的訓練，評測和可視化的完整代碼在下面的git倉庫中，後面還會陸續更新line,node2vec,sdne,struc2vec等graph embedding演算法以及一些GCN演算法
shenweichen/GraphEmbedding
G = nx.read_edgelist(../data/wiki/Wiki_edgelist.txt,create_using=nx.DiGraph(),nodetype=None,data=[(weight,int)])
model = DeepWalk(G,walk_length=10,num_walks=80,workers=1)
model.train(window_size=5,iter=3)
embeddings = model.get_embeddings()
evaluate_embeddings(embeddings)
plot_embeddings(embeddings)
分類任務結果
micro-F1 : 0.6674
macro-F1 : 0.5768
可視化結果
不知道寫清楚了沒，本菜雞認知和文字表達能力有限，還請多多提意見！！
參考資料
- Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014: 701-710.
- Graph Neural Network Review
推薦閱讀：
