作者：Elior Cohen
編譯：ronghuaiyang
導讀
圖嵌入是圖學習的重要手段，今天給大家介紹一個非常經典的方法，node2vec，圖嵌入必學方法之一。
原始論文: https://arxiv.org/pdf/1607.00653.pdf
算法實現 — By Elior Cohen：https://github.com/eliorc/node2vec
算法實現 — By the algo author: https://github.com/aditya-grover/node2vec
展示案例代碼: https://github.com/eliorc/Medium/blob/master/Nod2Vec-FIFA17-Example.ipynb
動機
嵌入……每個數據科學家現在都聽說過這個詞，但主要是在NLP上下文中。
那麼，我們為什麼要費盡心思去嵌入呢？
在我看來，創建高質量的嵌入並將其作為模型的輸入，與著名的「Garbage in, garbage out」正好相反。
當你將低質量的數據輸入到模型中時，你將整個學習的負擔都壓在了模型上，因為它將不得不學習從數據中得出的所有必要結論。
相反，當你使用高質量的嵌入時，你已經在數據中放入了一些知識，從而使你的模型更容易地了解問題。
另一個需要考慮的點是信息 vs 領域知識。
例如，讓我們考慮詞嵌入(word2vec)和詞袋錶示。
雖然這兩種單詞表示方式都可以在一個句子中包含某個詞的全部信息，但詞嵌入還包括詞與詞之間的關係等領域知識。
在這篇文章中，我將討論一種稱為node2vec的技術，它的目的是為圖中的節點創建嵌入(在G(V, E, W)的意義上)。
我將解釋它是如何工作的，並用Python 3對它進行了實現，以及一些額外的功能。
嵌入的過程
那麼怎麼做呢？
嵌入本身的學習方法與word2vec的嵌入學習方法相同 — 使用的是skip-gram模型。
我認為解釋node2vec最自然的方式是解釋node2vec如何生成「語料庫」 — 如果我們理解了word2vec，我們就已經知道如何嵌入語料庫了。
如何從圖中生成語料庫呢？這正是node2vec的創新之處，它是用了採樣策略的智能方式來做的。
為了從輸入圖生成語料庫，讓我們將語料庫看作一組有向無環圖，最大輸出度為1。如果我們想一下，這是一個完美的文本句子的表達，句子中的每個單詞都是一個節點，它指向句子中的下一個單詞。
用圖表示句子
通過這種方式，我們可以看到word2vec已經可以對圖進行嵌入，但是是一種非常特殊的圖。
然而，大多數圖並不是那麼簡單，它們可以是(非)有向的，(非)加權的，(無)循環的，基本上在結構上比文本複雜得多。
為了解決這個問題，node2vec使用了一個可調整的(通過超參數)抽樣策略，對這些有向無環子圖進行抽樣。這是通過從圖的每個節點生成隨機遊走來實現的。很簡單對吧？
在我們深入研究採樣策略如何使用超參數生成這些子圖之前，讓我們先來看看這個過程：
Node2vec嵌入過程
採樣策略
現在我們已經有了大致思路，是時候深入挖掘了。
Node2vec的抽樣策略，接受4個參數：
- 行走次數：圖中每個節點產生的隨機行走次數
- 行走長度：每次隨機行走中有多少個節點
- P：返回超參數
- Q：輸入輸出超參數
以及標準的skip-gram參數(上下文窗口大小、疊代次數等)。
前兩個超參數非常容易理解。
隨機遊走生成算法遍歷圖中的每個節點，生成一定長度<遊動長度>的<遊走次數>隨機遊動，。
Q和P，最好用可視化來解釋。
假設你正在進行隨機遊走，並且剛剛在下圖中從節點<t>轉換到節點<v>。
從<v>轉換到他的任何一個鄰居的機率是：< 邊權重 > <α >(歸一化的)，< *α >取決於hyperparameters。
P控制訪問<v>後返回<t>的機率。
Q控制探索圖中未發現部分的機率。
直觀地說，這有點像tSNE中的perplexity參數，它允許你重視圖的局部或者全局結構。
不要忘記權重也是要考慮的，所以最終的路徑的機率是一個函數:
- 1、遍歷的前一個節點
- 2、P和Q
- 3、邊的權值
理解這一部分很重要，因為它是node2vec的本質。如果你沒有完全理解抽樣策略背後的思想，我強烈建議你再讀一遍這部分。
使用抽樣策略，node2vec將生成用於嵌入的「句子」(有向子圖)，就像word2vec中使用文本句子一樣。為什麼要改變一些事情，如果它是正確的？
代碼
現在是時候將node2vec付諸行動了。
你可以在這裡找到這個node2vec的完整代碼：https://github.com/eliorc/medium/blob/master/nod2vec-fifa17example.ipynb。
我使用node2vec算法的實現作為示例，它增加了對分配節點特定參數(q、p、num_walks和walk length)的支持。
我們要做的是，利用歐洲足球隊的隊形，嵌入7個不同俱樂部的球隊、球員和位置。
我將使用的數據取自Kaggle上的FIFA 17數據集。
在國際足聯(通過EASports)中，每支球隊都可以用圖表示，如下圖所示。
來自FIFA17的例子，很容易理解為一個圖
正如我們所看到的，每個位置都與其他位置相連，在比賽中每個位置都被分配給一個球員。
有幾十種不同的陣型，它們之間的連接也不同。也有一些位置在某些陣型中存在，但在其他陣型中不存在，例如「LM」位置在其他陣型中不存在。
我們這樣做：
1、節點是球員、球隊名稱和位置
2、對於每個球隊，創建一個單獨的圖，其中每個球員節點連接到他的球隊名稱節點、連接到他的隊友節點並連接到他的隊友位置節點。
3、對生成的圖應用node2vec
注意：為了為球隊內部和不同球隊之間的每個位置創建單獨的節點，我向類似的節點添加了後綴，並在生成walk之後刪除了它們。這是一個技術問題，為了更好地理解，請檢查代碼中的repo
輸入數據的第一行是這樣的(經過一些排列)：
從輸入數據中採樣行
然後，我們利用FIFA17構造圖。
使用我的node2vec包，圖必須是networkx.Graph的一個實例。
在此之後檢查圖的邊，我們將得到以下結果：
for edge in graph.edges:
print(edge)
>>> ('james_rodriguez', 'real_madrid')
>>> ('james_rodriguez', 'cm_1_real_madrid')
>>> ('james_rodriguez', 'toni_kroos')
>>> ('james_rodriguez', 'cm_2_real_madrid')
>>> ('james_rodriguez', 'luka_modric')
>>> ('lw_real_madrid', 'cm_1_real_madrid')
>>> ('lw_real_madrid', 'lb_real_madrid')
>>> ('lw_real_madrid', 'toni_kroos')
>>> ('lw_real_madrid', 'marcelo')
...
正如我們所看到的，每個球員都和他的球隊，位置和隊友聯繫在一起。
所有附加到位置的後綴將在步長計算後返回到它們原來的字符串(lw_real_madrid lw)。
現在我們有了圖，我們執行node2vec。
# pip install node2vec
from node2vec import Node2Vec
# Generate walks
node2vec = Node2Vec(graph, dimensions=20, walk_length=16, num_walks=100)
# Reformat position nodes
fix_formatted_positions = lambda x: x.split('_')[0] if x in formatted_positions else x
reformatted_walks = [list(map(fix_formatted_positions, walk)) for walk in node2vec.walks]
node2vec.walks = reformatted_walks
# Learn embeddings
model = node2vec.fit(window=10, min_count=1)
我們給 node2vec.Node2Vec一個networkx.Graph實例。在使用 .fit()之後，我們得到一個gensim.models.Word2Vec的實例。
首先，我們將檢查不同節點之間的相似性。
我們期望一個球隊節點最相似的節點是它的球員：
for node, _ in model.most_similar('real_madrid'):
print(node)
>>> james_rodriguez
>>> luka_modric
>>> marcelo
>>> karim_benzema
>>> cristiano_ronaldo
>>> pepe
>>> gareth_bale
>>> sergio_ramos
>>> carvajal
>>> toni_kroos
這些都是真正的皇馬球員！
接下來，我們檢查與特定位置的相似性。我們希望球員在那個位置上或者差一點的情況下接近那個位置。
# Right Wingers
for node, _ in model.most_similar('rw'):
# Show only players
if len(node) > 3:
print(node)
>>> pedro
>>> jose_callejon
>>> raheem_sterling
>>> henrikh_mkhitaryan
>>> gareth_bale
>>> dries_mertens
# Goal keepers
for node, _ in model.most_similar('gk'):
# Show only players
if len(node) > 3:
print(node)
>>> thibaut_courtois
>>> gianluigi_buffon
>>> keylor_navas
>>> azpilicueta
>>> manuel_neuer
在第一次嘗試中(右翼)我們確實從不同的俱樂部得到了不同的右翼，這又是一場完美的匹配。
在第二次嘗試中，我們得到了除了Azpilicueta之外的所有守門員，Azpilicueta實際上是一名後衛。
效果很好，對吧？在我們結束之前，讓我們使用tSNE來降維和可視化球員節點。
球員節點可視化
看看，我們得到了基於不同俱樂部的漂亮的聚類。
英文原文： https://towardsdatascience.com/node2vec-embeddings-for-graph-data-32a866340fef
請長按或掃描二維碼關注本公眾號