網絡表達學習系列(一):深度遊走(Deepwalk)

2021-02-21 深度學習與圖網絡

如果你經常聽到圖卷積，圖嵌入，圖網絡，但是不太了解其中的原理，這是一篇很好的文章，開啟你的網絡之旅：網絡表達學習（Network Representation Learning），或者稱之為網絡嵌入（Network Embedding）。

什麼是網絡表達學習？

網絡表達學習嗎，顧名思義，是指學習出一個網絡的低維度隱含表達。網絡表達學習的目標是將一個複雜網絡中的結點和邊的信息都通過向量來表達，我們通過算法可以學習出這些向量，因此這些向量中包含著網絡的結構信息。學習得到的向量可以作為圖的特徵用在基於圖的各種任務上，比如連接預測，節點分類，社區發現以及可視化等問題上。

網絡表達學習本質上是將網絡進行降維從而更好地利用其它模型來處理網絡數據。對於一個網絡G=(V,E)來說，網絡表達的結果是將這個網絡變成維度為|V|xd的一個二維矩陣，|V|是指網絡節點個數，d是每個節點表達的維度。網絡表達學習相當於一個映射函數，將每個節點映射到一個向量中去。原本網絡中單個節點包含的特徵是複雜且難以把控的，節點的特徵包括周邊鄰接點的信息（結構信息），節點的屬性以及邊的屬性等等，如果我們要同時直接使用節點的所有特徵是非常困難的，每個特徵都有自己的含義，所以我們希望把這些特徵都封裝到一起成為一個向量，這樣既方便讀取也方便模型運算。

深度遊走（DeepWalk）算法

深度遊走算法是近年來第一個有影響力的大規模網絡表達學習算法，它的本質是將隨機遊走（Random Walk）和自然語言處理中的skip-gram算法作組合所產生的算法。我們首先來介紹一下隨機遊走和skip-gram，然後再來看deepwalk是如何工作的。

隨機遊走（Random Walk）

隨機遊走是一個非常基礎的基於網絡的算法。它的本質就是從一個節點出發，隨機選擇它的一個鄰接點，再從這個鄰接點出發到下一個節點，重複這個步驟然後記錄下所經過的所有節點。這個算法的變種在Google搜索和金融領域應用廣泛。通過隨機遊走我們可以得到從每個節點出發的一條路徑，這條路徑就代表了這個節點的結構信息。

Skip-gram算法

Skip-gram算法是自然語言處理中常用的一種方法，它是用一個詞來預測這個詞前後可能會出現哪些詞。舉個例子，對於I can do all things這句話，我們希望學出do這個詞的表達，因此我們要定一個窗口，如圖1所示，1就是我們要學的詞，而uk就是窗口，代表我們要用哪些詞來訓練1的表達。若窗口大小定為3，則對於do這個詞而言，訓練數據為(do, can)，(do, all), 若窗口大小定為5，則對於do這個詞而言，訓練數據為(do, can)，(do, I)，(do all)，(do things)。

圖1. skip-gram窗口

我們是通過神經網絡來學出詞的表達。網絡的結構如圖2。輸入是每個詞的one-hot向量，即，如果字典裡一共有10000個詞，那輸入就是一個10000維的向量，只在這個詞所處的位置上置1其餘全部置0。輸出也是訓練集中對應詞的one-hot向量，此時輸入層和輸出層之間隱含層的值就是我們學習出的詞的表達。對於skip-gram模型，我們採用隨機梯度下降進行參數學習。我們希望將這種方法用在學習網絡節點表達上，接下來將描述如何將隨機遊走和skip-gram結合起來。

圖2. skip-gram模型

深度遊走算法

深度遊走的核心思想總結成一句話就是，短的隨機遊走路徑=句子（short random walk = sentence，quoted from Bryan Perozzi），因此我們只需要設定一個隨機遊走的步數r，通過隨機遊走我們就可以得到一個長度為r的路徑（節點集），此時我們將其中每一個節點都看成單詞，每個節點也都有對應的one-hot編碼，這樣就可以直接用skip-gram模型學出節點的表達。

由於網絡的節點數目可能達到百萬甚至千萬級，節點的one-hot編碼會過於稀疏，不同於傳統的skip-gram模型直接用softmax函數得到輸出，deepwalk採用的是層級softmax方法，如圖3所示，每個節點對應一個完全二叉樹的葉子節點，根節點輸入的是我們目標節點的表達，此時就變成一個二分類問題，我們只需要判斷二叉樹的左右子樹就可以學出節點的表達。

圖3. 層級softmax模型

總結

Deepwalk是一個非常簡單但很有創意的方法，它將基於圖的經典方法隨機遊走和自然語言處理中的skip-gram模型結合，得到了一個簡單好用的網絡表達學習方法。這也是第一篇將深度學習應用在大規模網絡上，因此這個方法具有很強的可拓展性。Deepwalk作為網絡表達學習中一個開創性工作，從一個簡單的角度切入，用現有的成熟的方法，在一個全新的且尚未成為主流的問題中得到一個行之有效的解，不僅對網絡表達這個問題帶來極大的發展，同時也為我們做研究提供了一個很好的思路。一個優秀的方法是要建立在前人工作的基礎上而不是憑空產生，並且當前最熱門的問題並不一定是最值得研究的，冷門的問題也有其潛在的研究價值。

參考文獻

[1] DeepWalk: Online Learning of Social Representations，KDD' 14

[2] Skip-gram. http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/

相關焦點

  • DeepWalk:圖網絡與NLP的巧妙融合
    一些大佬們的新書：《Graph Representation Learning》、《Deep Learning on Graphs》ok，回到正題，今天要介紹的這篇是『Graph Embedding』系列第一篇
  • 圖神經網絡-圖遊走算法核心代碼DeepWalk實現
    本文主要涉及圖遊走算法DeepWalk的代碼實現。1.
  • 【Graph Embedding】DeepWalk算法原理,實現和應用
    概率圖模型，涉及圖的表示，推斷和學習，詳細可以參考 Koller 的書或者公開課3. 圖神經網絡，主要包括 Graph Embedding (基於隨機遊走)和 Graph CNN (基於鄰居匯聚)兩部分。這裡先看下 Graph Embedding 的相關內容。
  • 神經網絡圖的簡介(基本概念,DeepWalk以及GraphSage算法)
    本文旨在介紹圖形神經網絡的基礎知識兩種較高級的算法，DeepWalk和GraphSage。 圖 在我們學習GAN之前，大家先了解一下什麼圖。在計算機科學中，圖是一種數據結構，由頂點和邊組成。圖G可以通過頂點集合V和它包含的邊E來進行描述。
  • 從圖網絡表示到圖神經網絡
    而在更一般的情況下， 數字和數字之間，是一個互相聯繫的複雜網絡， 這時候我們用節點和連接它們的邊來描述這種數據類型， 這就是我們說的圖網絡結構。對於圖像CNN是目前深度學習的集大成者， 對於時間序列RNN， transformer是集大成者， 那麼對於圖結構呢？這就是當下的圖神經網絡崛起的背景。
  • 萬物皆可Embedding之Deepwalk算法解讀
    DeepWalk論文發表於2014年的KDD會議上，將embedding從item序列推廣至圖序列，它是一種用於學習網絡中頂點的潛在表示的新方法。這些潛在表示將社會關係編碼到連續的向量空間中，編碼到向量空間後的社會關係，很容易應用到統計模型中。DeepWalk將隨機遊走得到的節點序列當做句子，從截斷的隨機遊走序列中得到網絡的局部信息，再通過局部信息來學習節點的潛在表示。
  • 深度強化學習(一)----深度學習介紹系列
  • 使用DeepWalk從圖中提取特徵
    通常是諸如社交網絡，網際網路，已連接的IoT設備，鐵路網絡或電信網絡之類的事物。在圖論中，這些網絡稱為圖。網絡是互連節點的集合。節點表示實體，它們之間的連接是某種關係。我們還可以使用圖和網絡表示其他類型的數據（並且在本文中我們將介紹一個獨特的行業用例）。為什麼我們將數據表示為圖？為什麼不僅僅使用典型的數據可視化技術來可視化數據？為什麼要更複雜並學習新概念？下面我們會給出答案。
  • 一文直擊Graph Embedding圖表示學習的原理及應用
    ，拓撲排序，關鍵路徑等概率圖模型，涉及圖的表示，推斷和學習，詳細可以參考 Koller 的書或者公開課圖神經網絡，主要包括 Graph Embedding (基於隨機遊走)和 Graph CNN (基於鄰居匯聚)兩部分。這裡先看下 Graph Embedding 的相關內容。
  • 深度學習中不得不學的Graph Embedding方法
    在這樣的背景下，對圖結構中間的節點進行表達的graph embedding成為了新的研究方向，並逐漸在深度學習推薦系統領域流行起來。圖4 寬度優先搜索（BFS）和 深度優先搜索（DFS）示意圖為了使Graph Embedding的結果能夠表達網絡的同質性，在隨機遊走的過程中，需要讓遊走的過程更傾向於
  • 【深度學習系列4】深度學習及並行化實現概述
    如果說機器是人類手的延伸、交通工具是人類腿的延伸，那麼人工智慧就是人類大腦的延伸，甚至可以幫助人類自我進化，超越自我。人工智慧也是計算機領域最前沿和最具神秘色彩的學科，科學家希望製造出代替人類思考的智能機器，藝術家將這一題材寫進小說，搬上銀幕，引發人們無限的遐想。然而，作為一門嚴肅的學科，人工智慧在過去的半個多世紀中發展卻不算順利。
  • 什麼是深度學習? - 45分鐘理解深度神經網絡和深度學習
    為了使學生們能夠更好、更快理解和使用深度神經網絡和深度學習，特撰寫此文。本文的目的是幫助非人工智慧領域的學生（主要是計算機圖形學領域的學生及筆者的學生）來搞懂深度學習（這裡指狹義的深度學習，即基於DNN的深度學習）的基本概念和方法。筆者嘗試用通俗的語言，從函數逼近論的角度來闡釋深度神經網絡的本質。
  • 深度學習系列文章Part2:遷移學習和微調深度卷積神經網絡(附論文)
    ，是對遷移學習和微調深度卷積神經網絡的介紹。機器之心此前也已經編譯了該系列的第一部分，詳情點擊《五大主流深度學習框架比較分析：MXNET是最好選擇》。文中涉及到的論文可點擊閱讀原文下載。這是由幾個部分組成的博客系列，我將在此系列中聊一聊我對深度學習的經驗及認識。在第一部分，我討論了不同的有代表性的框架的優劣，以及我選擇 Theano（與 Lasagne）作為我的平臺的原因。
  • 深度學習推薦系統中各類流行的Embedding方法 (下)
    形式上來說，Embedding就是用一個低維的向量表示一個物體，可以是一個詞，一個商品，或是一個電影。作為深度學習的「基本核心操作」，Embedding技術已經在深度學習推薦系統中被廣泛應用，在Youtube、Airbnb等各類推薦系統中都有涉及。更多Embedding技術，可以參考往期文章：深度學習推薦系統中各類流行的Embedding方法 (上)。
  • DeepWalk原理與實踐
    簡介DeepWalk是一種學習圖結構中節點的潛在表示的方法，這些潛在的表示法在連續向量空間中進行編碼，編碼到向量空間後節點的關係很容易被統計模型利用，兩個點在圖中共有的鄰近點（或者高階鄰近點）越多，則對應的兩個向量之間的距 離就越短。DeepWalk將隨機遊走得到的節點序列當做句子，從截斷的隨機遊走序列中得到網絡的局部信息，再通過局部信息來學習節點的潛在表示。
  • 深度學習和深度神經網絡
    深度學習深度學習是眾多機器學習方法中的一種。主要是通過神經網絡來實現。「深度」是指神經網絡的層數。
  • 神經網絡與深度學習
    深度學習筆記深度學習作為當前機器學習一個最熱門的發展方向，仍然保持著傳統機器學習方法的理念與特徵，從監督學習的角度看，深度學習與機器學習並無本質上的差異。至於在這個過程中我們碰到的各種各樣的問題，比如數據質量、模型評價標準、訓練優化方法、過擬合等一系列關乎機器學習模型生死的問題，在這裡不做具體展開，大家可以去補習相關的機器學習知識。在機器學習中，有很多相當成熟的模型和算法。其中有一種很厲害的模型，那就是人工神經網絡。
  • 【深度學習系列】卷積神經網絡CNN原理詳解(一)——基本原理
    ，熟悉Tensorflow，PaddlePaddle等深度學習框架，負責過多個機器學習落地項目，如垃圾評論自動過濾，用戶分級精準營銷，分布式深度學習平臺搭建等，都取了的不錯的效果。博客專欄：https://www.cnblogs.com/charlotte77/前文傳送門：【好書推薦&學習階段】三個月教你從零入門深度學習【深度學習系列】PaddlePaddle之手寫數字識別上篇文章我們給出了用paddlepaddle來做手寫數字識別的示例，並對網絡結構進行到了調整，提高了識別的精度。
  • 《神經網絡和深度學習》系列文章四:神經網絡的結構
    本節譯者：哈工大SCIR碩士生 徐偉 (https://github.com/memeda)聲明：我們將在每周一，周四，周日定期連載該書的中文翻譯，如需轉載請聯繫wechat_editors@ir.hit.edu.cn，未經授權不得轉載。