Graph Embedding：深度學習推薦系統的"基本操作"
Embedding 是深度學習十分重要的「基本操作」，不論是 NLP，搜索排序，還是推薦系統，Embedding 都扮演著重要的角色。本文藉由 Graph Embedding 切入，不用一個公式，帶領大家從 Word2Vec 到 DeepWalk，再到 Node2Vec，你也能成為演算法大神~
之前的博文，給大家介紹了很多圖演算法，它們看起來很酷炫，卻不知道如何使用？本期我們關注 Graph Embedding，不但可以「實踐」很多圖演算法，更可以快速瞭解 Embedding 在深度學習推薦系統中的使用，從 Word2Vec 到 DeepWalk，從 LINE 到 Node2Vec，希望能收穫滿滿~ 另外，推薦一個知乎專欄：王喆的機器學習筆記，關於 Graph Embedding，專欄用了幾篇文章相對系統地進行了說明，閱讀之後受益很多。
本文不含公式，需要基本的圖演算法基礎，包括 Random Walk、BFS、DFS 等。如果這些名詞對你來說還很陌生，建議閱讀前序博文。
圖演算法：概覽
Embedding is all you need
允許我做一次標題黨，Embedding 必須是深度學習中的「基本操作」。不論是 NLP（Normal Language Processing，自然語言處理），搜索排序，還是推薦系統，或者 CTR （Click-Through-Rate，點擊通過率）模型，Embedding 都扮演著不可或缺的角色。
什麼是 Embedding？
Embedding 在數學上表示一個映射關係， F: X -> Y， 也就是一個函數。函數具有兩個性質：injective 和 structure-preserving。Injective，即我們所說的單射函數，對於每個 Y 只有唯一的 X 對應，反之亦然；structure-preserving，結構保存，比如在 X 所屬的空間上 X1 < X2，那麼映射後在 Y 所屬空間上 Y1 < Y2。
簡單點說，深度學習中，Embedding 特指用一個低維度向量表示一個實體，可以是一個詞（Word2Vec），可以是一個物品（Item2Vec），亦或者網路關係中的節點（Graph Embedding）。
Embedding 所獲得的低維度向量具有一些特殊的性質。如下圖，我們使用 Word2Vec 將單詞映射（word embedding）到新的向量空間，獲得單詞的新的表達（word representation）。我們能從圖中很容易得出：Embedding(Moscow) - Embedding(Russia) ≈ Embedding(Tokyo) - Embedding(Japan)，說明 Embedding 之後向量可以進行計算。並且，Embedding 之後，距離相近的向量對應的實體有相近的含義，比如 Embedding (Russia) 和 Embedding (Japan) 之間的距離就會很接近，但 Embedding (Russia) 和 Embedding (Tokyo) 的距離就會遠一些。
可見，Embedding 擁有很多優點：得到的向量表達維度更低，並且表達了實體間內在的關係。下面以商品推薦為例，進一步解釋。假設我們有千萬級別的商品，我們通常使用 One-Hot 編碼數字化地代表，則能夠得到千萬個向量，每個向量代表一種商品，並且每個向量都擁有千萬級別的維度。向量只有一位是 1，其他位均為 0，信息量十分「稀疏」。此時，任何商品之間的距離都是一樣的。並且，由於深度學習的特點以及工程方面的原因，深度學習並不善於處理稀疏特徵的向量。相反，Embedding 之後，千萬級別的維度可以縮小到自定義的維度大小（例如1000）。變成向量之後的商品，可以直接通過計算向量相似度，尋找相似的商品，直接推薦給客戶。
這些優點帶來的好處是顯著的，Embedding 主要的三個應用方向：
- 在深度學習網路中使用 Embedding 層，將高維稀疏特徵向量轉換成低維稠密特徵向量，從而減少後續模型參數量，後續模型可以是深度學習模型，或者傳統的機器學習模型；
- 作為預訓練技術，直接使用別人訓練好的 Embedding 向量，與其他特徵向量一同輸入後續模型進行訓練，例如 Word2Vec；
- 通過計算用戶和物品的 Embedding 相似度，Embedding 可以直接作為推薦系統或計算廣告系統的召回層或者召回方法之一，例如 Youtube 推薦系統。
什麼是 Graph Embedding？
Graph Embedding 用低維、稠密、實值的向量表示網路中的節點。目前，Graph Embedding 已經是推薦系統、計算廣告領域非常流行的做法，並且在實踐後取得了非常不錯的線上效果。
為什麼能有這樣的效果呢？
我們很容易理解（如果有困難，可以嘗試閱讀下一章節），Word2Vec 通過序列（sequence）式的樣本：句子，學習單詞的真實含義。仿照 Word2Vec 思想而生的 Item2Vec 也通過商品的組合去生成商品的 Embedding，這裡商品的組合也是序列式的，我們可以稱他們為「Sequence Embedding」。然而，在更多場景下，數據對象之間更多以圖/網路的結構呈現。例如下圖，由淘寶用戶行為數據生成的物品關係圖（Item Graph）：
從上圖的例子中，我們已經能觸碰到一些 Graph Embedding 的本質。Graph Embedding 之所以能好於 「Sequence Embedding」，是因為 Graph Embedding 能夠生成一些「不存在」的序列。例如，上圖數據中沒有這樣的用戶行為數據：B-E-F、D-E-C等等。但是在物品關係圖中，我們有機會生成這樣的序列。
Graph Embedding 常見的同義詞
除了 Graph Embedding，我們還會經常看到 Network Embedding、Node Embedding、Graph Representation 或者 Network Representation Learning，這些名詞可能在定義上會有差異，大部分時間，我們可以在特定場合將他們視為同義詞。
下面就讓我們從 Word2Vec 開始，瞭解 Graph Embedding 吧~
Embedding 流行起點：Word2Vec
Google 的 Tomas Mikolov 在 2013 年的兩篇論文標誌著 Word2Vec 的誕生，論文提出了 CBOW 和 Skip-gram 兩種 Word2Vec 模型結構。下圖是兩種模型結構的架構圖：
CBOW 使用目標詞周邊的詞來預測目標詞，Skip-gram 使用目標詞預測周邊的詞。兩種架構差別不大，我們在 Embedding 中更多使用Skip-gram。圖中輸入輸出均使用詞向量，詞向量初始隨機賦值，隨著預測任務的進行，詞向量在迭代中慢慢優化，使得預測任務指標越來越好，而我們最終需要的是訓練好的詞向量。兩種模型的訓練數據均使用標準的自然語言語料，利用詞與詞的關係（也就是語料序列）去訓練詞向量。
也就是說，只要我們找到詞與詞之間的關聯關係，就能通過 Skip-gram 方法訓練詞的向量。
Word2Vec 有很多技術細節，例如使用 Hierarchical Softmax（層序 Softmax） 和 Negative Sampling 來減少由於辭彙空間過大帶來的計算量，例如優化目標的設置等等等等。由於與主旨無關，本文不作介紹。（事實是網上可以找到太多博文，毫無重寫一份的激情……）
Graph Embedding 早期技術：DeepWalk
Word2Vec 誕生之後，Embedding 的思想迅速從 NLP 領域擴散到幾乎所有的機器學習領域。我們可以對語料序列中的詞進行 Embedding，那麼自然用戶購買序列中的商品，或者用戶觀看序列中的電影，都可以進行 Embedding。這就是 Item2Vec。
回顧上一節的重點：是詞與詞的關聯關係實現了 Embedding 的過程。序列（sequence）是一種「一維」的關係，而圖（graph）是一種「二維」的關係，同樣可以進行 Embedding。然而，我們目前能進行 Embedding 的 「工具」 只有 Skip-gram，只能處理序列這樣一維的關係輸入。因此，我們需要在二維關係上進行 「採樣」，採樣的過程可以使用隨機遊走演算法（Random Walk，我們已在前序博文中進行了介紹）。
DeepWalk 就是 Random Walk 與 Skip-gram 的組合。上圖是 DeepWalk 演算法偽代碼，核心步驟 6 和 7 就是 Random Walk 與 Skip-gram。下圖是演算法流程示意：
Random Walk 負責對圖進行採樣，獲得圖中節點與節點的共現關係，Skip-gram 從關係（也就是採樣的序列）中訓練節點的 Embedding 向量。
上述結果中，比較臨近的節點再 Embedding 空間更為接近，且結構更為相似的節點，距離也更近。這就是網路節點的同質性（homophily）和結構性（structural equivalence），進一步的說明會在下一小節。
所以，DeepWalk 以 Random Walk 的方式從網路中生成序列，進而轉換成傳統 word2vec 的方法生成 Embedding 向量。該演算法可以視為 Graph Embedding 的 baseline 方法，用極小的代價完成從 word2vec 到 graph embedding 的轉換和工程嘗試。
DeepWalk 的改進：從 LINE 到 Node2Vec
DeepWalk 之後，比較重要的工作是微軟亞洲研究院在 2015 年發布的 LINE（Large-scale Information Network Embedding）。閱讀到這裡，我們已經可以知曉，在網路上 「相似」 的節點，最終會擁有相似的 Embedding 向量。在 LINE 的論文中，定義了兩種相似：
First-order proximity（1 階相似度）：用於描述圖中成對頂點之間的局部相似度，形式化描述為若節點之間存在直連邊，則邊的權重即為兩個頂點的相似度，若不存在直連邊，則 1 階相似度為0。 如下圖，節點 6 和 7 之間存在直連邊，且邊權較大，則認為兩者相似且 1 階相似度較高，而 5 和 6 之間不存在直連邊，則兩者間 1 階相似度為 0。也就是我們上一小節所說的同質性相似。
Second-order proximity（2 階相似度）：僅有1階相似度就夠了嗎？顯然不夠，如下圖，雖然節點 5 和 6 之間不存在直連邊，但是他們有很多相同的相鄰節點 （1,2,3,4），這其實也可以表明5和6是相似的，而 2 階相似度就是用來描述這種關係的。 形式化定義為，令表示頂點 u 與所有其他頂點間的1階相似度，則 u 與 v 的2階相似度可以通過 p_u 和 p_v 的相似度表示。若u與v之間不存在相同的鄰居頂點，則2階相似度為0。也就是我們上一小節所說的結構性相似。
相比 DeepWalk 純粹隨機遊走的序列生成方式，LINE 可以應用於有向圖、無向圖以及邊有權重的網路，並通過將一階、二階的鄰近關係引入目標函數，能夠使最終學出的 node embedding 的分佈更為均衡平滑，避免 DeepWalk 容易使 node embedding 聚集的情況發生。下圖是論文中的結果對比：
從圖中可以看出，LINE 的效果最好，DeepWalk 對不同顏色的點分得也不錯，但是圖形中部很多點都擠在一塊，而這些點都是出度很大的點，文章提了一句說對於這種點的處理 DeepWalk 會產生很大噪音，但沒有詳細對此分析。論文還指出，DeepWalk 利用隨機遊走去捕獲鄰近關係，更像是深度優先搜索；而LINE的方式更像是廣度優先搜索，相對而言更合理。上圖中的 GF 代表 graph factorization，本文不作介紹，感興趣的話可以自行 Google。
在 DeepWalk 和 LINE 的基礎之上，斯坦福大學在 2016 年發布了 Node2Vec。演算法不但關注了同質性和結構性的相似，更可以在兩者之間進行權衡。如何做到的呢？讓我們先來回顧，什麼是深度優先（DFS），什麼是廣度優先（BFS）。
那麼，節點 u 與其相連的節點 s1、s2、s3、s4 的 embedding 表達應該是接近的，這是同質性相似。節點 u 和節點 s6 都是各自區域網絡的中心節點，結構上相似，其 embedding 的表達也應該近似，這是結構性相似。
如果我們在隨機遊走的過程中以 BFS 為主，例如獲得序列 u-s1-s2-s3，訓練出來的 Embedding 向量更多反映了結構性的相似；如果隨機遊走以 DFS 為主，例如獲得序列 u-s4-s5-s6 ，則訓練出來的 Embedding 向量，更多反應同質性的相似。至於為什麼，大家可以先自己思考。
那 Node2Vec 是如何權衡同質性和結構性相似的呢？換句話說，Node2Vec 如何參數化控制隨機遊走是更傾向 BFS 還是 DFS 呢？下圖足以說明：
上圖是 Node2Vec 演算法中 Random Walk 的說明，假設我們隨機遊走到了節點 V，下一步有不同的概率到達臨近的節點。假設節點 t 是訪問節點 V 之前的節點，設置參數 p 為 「返回參數」（return parameter），控制節點 V 返回到節點 t 的概率，p 越大，從節點 V 返回節點 t 的概率越小。設置參數 q 為 「進出參數」（in-out parameter），控制節點 V 去往節點 x2、x3 的概率，q > 1 時，節點 V 之後更傾向於訪問前序節點 t 的共同鄰居，q < 1 時，節點 V 之後，更不傾向訪問前序節點 t 的鄰居。節點 x1 顯得有點特殊，因為節點 x1 同時是節點 t 和 V 的鄰居，我們設置權重為 1。通過修改參數 p 和 q，我們就能控制 Random Walk 採樣過程，是更傾向 DFS 還是 BFS。
上圖是 Node2Vec 的結果，同種顏色代表 Embedding 向量比較接近，節點比較相似。圖中上部分參數 p = 1，q = 0.5，結果表現為同質性相似的節點更為接近。下部分參數 p = 1，q = 2，結果表現為結構性相似的節點更為接近。
Node2Vec 所體現的網路的同質性和結構性在推薦系統中也是可以被很直觀的解釋的。同質性相同的物品很可能是同品類、同屬性、或者經常被一同購買的物品，而結構性相同的物品則是各品類的爆款、各品類的最佳湊單商品等擁有類似趨勢或者結構性屬性的物品。毫無疑問，二者在推薦系統中都是非常重要的特徵表達。由於 Node2Vec 的這種靈活性，以及發掘不同特徵的能力，甚至可以把不同 Node2Vec 生成的 embedding 融合共同輸入後續深度學習網路，以保留物品的不同特徵信息。
Graph Embedding 最佳實踐：EGES
我們介紹了一堆概念和演算法，那麼實際應用，效果如何呢？
2018 年，阿里巴巴發表論文，提出了能夠落地的 EGES（Enhanced Graph Embedding with Side Information）演算法，在約十億的用戶和二十億的商品這個數據量，進行了 Graph Embedding。其基本思想是 Embedding 過程中引入帶權重的補充信息（Side Information），從而解決冷啟動的問題。讓我們趕緊來看下流程圖：
步驟如下：
- 首先，我們擁有上億用戶的行為數據，不同的用戶，在每個 Session 中，訪問了一系列商品，例如用戶 u2 兩次訪問淘寶，第一次查看了兩個商品
B-E，第二次產看了三個商品D-E-F； - 然後，通過用戶的行為數據，我們可以建立一個商品圖（Item Graph），可以看出，物品A，B之間的邊產生的原因就是因為用戶U1先後購買了物品A和物品B，所以產生了一條由A到B的有向邊。如果後續產生了多條相同的有向邊，則有向邊的權重被加強。在將所有用戶行為序列都轉換成物品相關圖中的邊之後，全局的物品相關圖就建立起來了。
- 接著，通過 Random Walk 對圖進行採樣，重新獲得商品序列；
- 最後，使用 Skip-gram 模型進行 Embedding 。
仔細的讀者已經能夠發現，如果出現了新的商品怎麼辦，如果有個商品從沒有被人瀏覽過怎麼辦？沒有關係，就意味著在圖上是孤立的點，也意味著，無法獲得 Embedding，這就是冷啟動的問題。淘寶商城每個小時就有百萬級別的商品上線，這些商品該如何推薦呢？
答案其實已在上面給出，新上線的商品雖然沒有被人瀏覽，但是他們也有類別，品牌，所在城市，性別，風格等等各種屬性，也就是 Side Information，我們可以通過這些屬性建立商品間的關聯。下圖是一個簡單的例子：
如何實現呢？其實並不難。如下圖，在訓練 Embedding 的時候，不同的補充信息各自經過 Embedding，加權平均匯總到隱含層之後，再用來預測序列中的目標商品。
論文對模型性能進行了 A/B Test，在 2017 年 9 月的一週裏，EGES 最終比 Base 模型 CTR 高了約 0.5 個百分點。
阿里的 EGES 並沒有過於複雜的理論創新，但給出一個工程性的結合多種 Embedding 的方法，可好解決了冷啟動問題，是實用性極強的 Embedding 方法。
結論
本文一路小跑，終於穿過各種概念，各種演算法，不用一個公式，「友好」 地介紹了 Graph Embedding 技術。作為深度學習推薦系統的最新流行，Graph Embedding 肯定會有新的發展。除了本文涉及的演算法，還有許多：Laplacian Eigenmaps，Structure Preserving Embedding (SPE)，Graph Factorization (GF)，Structural deep network embedding (SDNE) 等等。學海無涯，祝你航行愉快。
References
- 【DeepWalk】DeepWalk- Online Learning of Social Representations，https://arxiv.org/pdf/1403.6652
- 【LINE】LINE - Large-scale Information Network Embedding，微軟 2015，https://arxiv.org/pdf/1503.03578
- 【Node2vec】Node2vec - Scalable Feature Learning for Networks，斯坦福 2016，https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5108654/
- 【EGES】Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba，Alibaba 2018，https://arxiv.org/pdf/1803.02349.pdf
- 【Word2Vec】Efficient Estimation of Word Representations in Vector Space，Google 2013，https://arxiv.org/pdf/1301.3781
- 【Word2Vec】Distributed Representations of Words and Phrases and their Compositionality，Google 2013，https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf
- 知乎答案：有誰可以解釋下 word embedding?，作者：寒蟬鳴泣，https://www.zhihu.com/question/32275069/answer/80188672
- 知乎文章：Embedding 從入門到專家必讀的十篇論文，作者：王喆，https://zhuanlan.zhihu.com/p/58805184
- 知乎文章：萬物皆 Embedding，從經典的 word2vec 到深度學習基本操作 item2vec，作者：王喆，https://zhuanlan.zhihu.com/p/53194407
- 知乎文章：深度學習中不得不學的 Graph Embedding方法，作者：王喆，https://zhuanlan.zhihu.com/p/64200072
- 知乎文章：關於 Node2vec 演算法中 Graph Embedding 同質性和結構性的進一步探討，作者：王喆，https://zhuanlan.zhihu.com/p/64756917
- 知乎答案：Graph Embedding 和 Network representation learning一樣嗎？，作者：張小磊，https://www.zhihu.com/question/292232005/answer/480368644
- 知乎文章：【Graph Embedding】DeepWalk：演算法原理，實現和應用，作者：淺夢，https://zhuanlan.zhihu.com/p/56380812
- 知乎文章：【Graph Embedding】LINE：演算法原理，實現和應用，作者：淺夢，https://zhuanlan.zhihu.com/p/56478167
- 知乎文章：Graph Embedding：從DeepWalk 到 SDNE，作者：羽刻，https://zhuanlan.zhihu.com/p/33732033
歡迎掃碼關注數據科學公眾號
推薦閱讀：
