Graph Embedding：DeepWalk算法原理，實現和應用

2019 年 11 月 21 日
筆記

文章作者：沈偉臣內容來源：作者授權發佈出品社區：DataFun 註：歡迎轉載，轉載請註明出處。

導讀：本文系作者（筆名：淺夢）畢業前的系列作品的第一篇，也作為本系列的結束髮給大家，順便也把前面幾篇文章推薦給小夥伴們：

正文：放假前在學校看了一點 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 算法

https://github.com/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

可視化結果

參考資料：

1. 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.

http://www.perozzi.net/publications/14_kdd_deepwalk.pdf

2. Graph Neural Network Review

https://zhuanlan.zhihu.com/p/43972372

作者介紹：

沈偉臣，碩士畢業於浙江大學計算機學院。對機器學習，強化學習技術及其在推薦系統領域內的應用具有濃厚興趣。