【帶你讀論文】向量表徵經典之DeepWalk

語言: CN / TW / HK
摘要:詳細講解DeepWalk,通過隨機遊走的方式對網絡化數據做一個表示學習,它是圖神經網絡的開山之作,借鑑了Word2vec的思想。

本文分享自華為雲社區《[論文閲讀] (25) 向量表徵經典之DeepWalk:從Word2vec到DeepWalk,再到Asm2vec和Log2vec》,作者:eastmount 。

一.圖神經網絡發展歷程

在介紹向量表徵之前,作者先結合清華大學唐傑老師的分享,帶大家看看圖神經網絡的發展歷程,這其中也見證了向量表徵的發展歷程,包括從Word2vec到Deepwalk發展的緣由。

圖神經網絡的發展歷程如下圖所示:

(1)Hinton早期(1986年)

圖神經網絡最早也不是這樣的,從最早期 Hinton 做了相關的思路,並給出了很多的ideas,他説“一個樣本可以分類成不同的representation,換句話,一個樣本我們不應該去關注它的分類結果是什麼,而更應該關注它的representation,並且它有很多不同的representation,每個表達的意思可能不同” ,distributed representation 後接着產生了很多相關的研究。

(2)擴展(Bengio到Word2Vec)

Andrew Ng 將它擴展到網絡結構上(結構化數據),另一個圖靈獎獲得者Yoshua Bengio將它拓展到了自然語言處理上,即NLP領域如何做distributed representation,起初你可能是對一個樣本representation,但對自然語言處理來講,它是sequence,需要表示sequence,並且單詞之間的依賴關係如何表示,因此2003年Bengio提出了 Nerual Probabilistic Language Model,這也是他獲得圖靈獎的一個重要工作。其思路是:每個單詞都有一個或多個表示,我就把sequence兩個單詞之間的關聯關係也考慮進去。

  • Yoshua Bengio, Rejean Ducharme, Pascal Vincent, and Christian Jauvin. A neural probabilistic language model. Journal of Machine Learning Research (JMLR), 3:1137–1155, 2003.
  • 原文地址:https://www.jmlr.org/papers/volume3/bengio03a/bengio03a.pdf

但是,當時做出來後由於其計算複雜度比較高,很多人無法fellow。直到谷歌2013年提出 Word2Vec,基本上做出來一個場景化算法,之後就爆發了,包括將其擴展到paragraph、文檔(Doc2Vec)。補充一句,Word2Vec是非常經典的工作或應用,包括我們安全領域也有相關擴展,比如二進制、審計日誌、惡意代碼分析的Asm2Vec、Log2Vec、Token2Vec等等。

(3) 網絡化數據時期(Deepwalk)

此後,有人將其擴展到網絡化的數據上,2014年Bryan做了 Deepwalk 工作。其原理非常建立,即:原來大家都在自然語言處理或抽象的機器學習樣本空間上做,那能不能針對網絡化的數據,將網絡化數據轉換成一個類似於自然語言處理的sequence,因為網絡非常複雜,網絡也能表示成一個鄰接矩陣,但嚴格意義上沒有上下左右概念,只有我們倆的距離是多少,而且周圍的點可多可少。如果這時候在網絡上直接做很難,那怎麼辦呢?

通過 隨機遊走 從一個節點隨機到另一個節點,此時就變成了一個序列Sequence,並且和NLP問題很像,接下來就能處理了。

隨後又有了LINE(2015)、Node2Vec(2016)、NetMF(2018)、NetSMF(2019)等工作,它們擴展到社交網絡領域。唐老師們的工作也給了證明,這些網絡本質上是一個Model。

(4) 圖卷積神經網絡(GCN)時期

2005年,Marco Gori 實現了 Graph Neural Networks。2014年,Yann Lecun 提出了圖卷積神經網絡 Graph Convolutional Networks。2017年,Max Welling將圖卷積神經網絡和圖數據結合在一起,完成了 GCN for semi-supervised classification,這篇文章引起了很大關注。還有很多不做卷積工作,因此有很多Graph Neural Networks和Neural Message Passing(一個節點的分佈傳播過去)的工作。Jure針對節點和Transductive Learning又完成了 Node2vec 和 grahpSAGE 兩個經典工作。唐老師他們最近也做了一些工作,包括 Graph Attention Network。

GraphSAGE 是 2017 年提出的一種圖神經網絡算法,解決了 GCN 網絡的侷限性: GCN 訓練時需要用到整個圖的鄰接矩陣,依賴於具體的圖結構,一般只能用在直推式學習 Transductive Learning。GraphSAGE 使用多層聚合函數,每一層聚合函數會將節點及其鄰居的信息聚合在一起得到下一層的特徵向量,GraphSAGE 採用了節點的鄰域信息,不依賴於全局的圖結構。

  • Hamilton, Will, Zhitao Ying, and Jure Leskovec. “Inductive representation learning on large graphs.” Advances in neural information processing systems. 2017.
  • 原文地址:https://proceedings.neurips.cc/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf

Data Mining over Networks

 

  • DM tasks in networks:
    – Modeling individual behavior
    – Modeling group behavioral patterns
    – Reveal anomaly patterns
    – Deal with big scale

第一部分花費大量時間介紹了研究背景,接下來我們正式介紹這六個工作。

二.Word2vec:NLP經典工作(谷歌)

(詳見前文)

Word2vec是一個用於生成詞向量(word vectors)並預測相似詞彙的高效預測框架,Word2vec是Google公司在2013年開發。

  • Tomás Mikolov, Kai Chen, Greg Corrado, Jeffrey Dean. Efficient Estimation of Word Representations in Vector Space. ICLR, 2013.

三.Doc2vec

(詳見前文)

在Word2Vec方法的基礎上,谷歌兩位大佬Quoc Le和Tomas Mikolov又給出了Doc2Vec的訓練方法,也被稱為Paragraph Vector,其目標是將文檔向量化。

  • Quoc V. Le, Tomás Mikolov. Distributed Representations of Sentences and Documents. ICML, 2014: 1188-1196.

四.DeepWalk:網絡化數據經典工作(KDD2014)

(一).論文閲讀

原文標題:Deepwalk: Online learning of social representations
原文作者:Perozzi B, Al-Rfou R, Skiena S
原文鏈接https://dl.acm.org/doi/abs/10.1145/2623330.2623732
發表會議:2014 KDD,Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining
參考資料:強推B站同濟子豪兄 - https://www.bilibili.com/video/BV1o94y197vf

DeepWalk是圖嵌入(Graph Embedding)的開山之作,於2014年被Bryan Perozzi等提出,旨在將圖中的每一個節點編碼為一個D維向量,為後續節點分類等下游任務提供支撐。DeepWalk通過隨機遊走算法從一個節點隨機到另一個節點,從而將網絡化數據轉換成一個序列(Sequence),再利用類似於NLP的方法處理。DeepWalk將圖當作語言,節點當作單詞來生成Embedding。

1.摘要

本文提出了DeepWalk,一種新穎的(novel)用於學習網絡節點的隱式表徵(latent representations)的方法。這些隱式表徵能夠把節點在圖中的連接關係進行編碼,編碼為一個稠密低維連續的向量空間(vector space),再通過該向量很容易地完成後續的統計機器學習分類。DeepWalk對現有的語言模型和無監督特徵學習(或深度學習)的最新進展進行了概括,將原本用於NLP領域對文本或單詞序列進行建模的方法(如Word2Vec)用至圖中,對節點進行嵌入。

DeepWalk使用有截斷的 隨機遊走(random walks) 序列去學習局部信息的隱層表示,並將隨機遊走序列當作是句子。我們演示了DeepWalk在社交網絡的一些多類別網絡分類任務上的隱式表示,比如BlogCatalog(博客)、Flickr(圖片)和YouTube(視頻)。實驗結果表明DeepWalk的表現優於現有的同類(基線)算法,後者擁有一個網絡的全局視圖,特別是在信息缺失(標註稀疏)的場景下。當標記數據稀疏(sparse)時,DeepWalk的表示可以提供比競爭方法高出10%的F1值。在一些實驗中,DeepWalk的表示優於所有基線方法,並且少使用60%的訓練數據。

DeepWalk也是可擴展的(scalable)。它是一個在線學習算法,可以迭代有用的增量學習結果,並且是並行的。這些特性使得它可以適用於廣泛的現實世界的應用中,如網絡分類(network classification)和異常檢測(anomaly detection)。

2.引言和貢獻

由於引言至關重要,因此該部分會全文介紹,學習這些經典文章如何介紹背景、引出問題及本文的貢獻及動機。

網絡表示的稀疏性(sparsity)既是優點也是缺點。稀疏性使得設計有效的離散算法成為可能,但如果使用統計機器學習模型去分類或迴歸就會很困難。網絡中的機器學習應用(如網絡分類、內容推薦、異常檢測和缺失鏈路預測)必須能夠處理這種稀疏性,才能生存下來(或工作)。

在本文中,我們介紹了深度學習(無監督特徵學習)技術 [3],即Word2Vec,該技術在自然語言處理中已被證明是成功的,並首次將其引入到網絡分析中。

  • [3] Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspectives. 2013.

我們提出了DeepWalk算法,通過建模一連串的隨機遊走序列來學習一個圖的頂點的網絡連接表示(social representations,即連接結構信息)。連接結構信息是捕獲鄰域相似性和社羣成員信息的頂點的隱式特徵。這些隱式表示編碼連接關係成一個連續低維稠密的向量空間。DeepWalk是神經語言模型的推廣,通過隨機遊走序列去類比一個個句子。神經語言模型(Word2Vec)已被證明在捕獲人類語言的語義和句法結構上非常成功,甚至是邏輯類比問題中。

DeepWalk將一個圖作為輸入,併產生一個隱式表示(向量)作為輸出。本文方法應用於經典的空手道網絡數據集的結果如圖1所示。圖1(a)是由人工排版的,圖1(b)顯示了我們方法所生成的2維向量(輸出)。除了原圖中的節點都驚人的相似外,我們注意到在圖1(b)中出現了線性可分的邊界,圖1(b)的聚類結果對應於輸入圖1(a)中模塊最大化的集羣(用頂點顏色顯示)。

圖1的補充內容:

(1) 圖1(a)表示34個人組建的空手道俱樂部的無向圖,連接表示兩個人相互認識,後續分成了不同顏色的派系;圖1(b)是經過DeepWalk編碼後的D維向量(二維),它會將graph的每一個節點編碼為一個D維向量(二維節點),繪製直角座標系中會發現,原圖中相近的節點嵌入後依然相近。該結果説明DeepWalk生成的Embedding隱式包含了graph中的社羣、連接、結構信息。

(2) DeepWalk會將複雜的圖轉換成一個Embedding向量,然後下游任務再對該向量進行分類或聚類。此外,DeepWalk編碼和嵌入屬於無監督過程,沒有用到任何的標記信息,只用到了網絡的連接、結構、社羣屬性的信息,因為隨機遊走不會考慮節點的特徵和類別信息,它只會採樣圖節點之間的順序、結構信息。

(3) Karate Graph(空手道圖)是經典的數據集,類似於機器學習中的鳶尾花數據集。

為了驗證(demonstrate)DeepWalk在真實場景中的潛力,我們評估了它在大型異質圖(heterogeneous graphs)中具有挑戰性的多標籤網絡分類問題上的性能。在關係分類問題中,特徵向量之間的鏈接違反了傳統的獨立同分布假設(i.i.d.)。解決這個問題的技術通常使用近似推理(approximate inference)技術來利用依賴信息以改進分類結果。我們跳出這些傳統的方法(we distance ourselves),通過學習圖的標籤無關的表示來將每個節點表示為一個向量。我們的表示質量不受標記頂點選擇的影響(無監督學習),因此它們可以在任務之間共享。

  • 關係分類問題(relational classification):在圖中標註一些節點,用已有節點去預測未標註節點的類別,如攻擊者識別。
  • 獨立同分布假設:在鳶尾花或MNIST圖譜數據集中,每個樣本(花)之間或數字之間是無關的,彼此互不影響,但它們都是鳶尾花或手寫數字圖像,因此叫獨立同分布,適用於傳統的機器學習。然而,在圖中,比如標註已有的攻擊者去預測未知的攻擊者,圖之間是存在聯繫的,因此既不獨立也不一定滿足同分布,沒法直接用傳統的LR、SVM、DT算法解決。

DeepWalk在創建連接維度方面優於其它的隱式表示方法,特別是在標記節點稀疏的情況下。我們的表示具有很強的性能,能夠使用非常簡單的線性分類器(如邏輯迴歸)完成相關實驗。此外,我們的表示方法是通用的,並且可以與任何分類方法(包括傳統的迭代推理方法)相結合。DeepWalk同時也是一個在線學習算法,並且能並行加速。

本文的貢獻如下:

  • 我們引入深度學習作為圖嵌入的工具,以建立適用於統計機器學習建模且魯棒的向量表示。DeepWalk能夠通過隨機遊走序列學習圖的結構規律。
  • 我們在多個社交網絡的多標籤分類任務上評估了本文的表示方法。特別在標註稀疏的場景下,DeepWalk顯著提高了分類的性能,Micro F1值提高了5%到10%。在某些情況下,即使減少了60%的訓練數據,DeepWalk的表現也可以超過競爭算法。
  • 我們通過並行加速將DeepWalk擴展到互聯網級別的圖(如YouTube)上來證明我們算法的可擴展性。此外,我們還進行了一些變種改進,通過構建streaming version所需的最小變化來生成圖嵌入。

3.問題定義

首先需要解決節點分類問題。我們考慮將一個社交網絡的成員劃分為一個或多個類別的問題。

  • G = (V,E):V表示網絡的節點,E表示連接關係。
  • E ⊆ (V×V):E可以表示成一個V行V列的鄰接矩陣,表明第i個節點和第j個節點存在聯繫。
  • G_L = (V,E,X,Y):X表示特徵(每個節點有S維特徵),Y表示類別,|V|表示節點個數,|y|表示類別個數,G_L為被標註的社交網絡。

在傳統機器學習算法中,通常需要擬合一個映射H,它將X的元素映射到標籤集y中。在本文的示例中,由於是圖數據,因此需要利用圖G結構中的依賴重要信息來獲得優越的性能。在本文中,這種稱為關係分類(relational classification)或集體分類(collective classification)問題。

  • 傳統關係分類解決方法:無向馬爾科夫網絡推理,通過迭代近似推理算法(如迭代分類算法、Gibbs採樣、Label relaxation)計算標籤給定網絡結構的後驗概率分佈。
  • 本文關係分類解決方法:提出一種新穎的方法來捕獲網絡拓撲信息。該方法不將標籤和連接特徵混合,而是通過隨機遊走序列來採樣連接信息,即僅在Embedding中通過隨機遊走來編碼連接信息,這是一種無監督的學習方法。

該方法的好處是將網絡的連接結構信息(結構表徵)和標籤信息分開,從而避免誤差累積(cascading errors)。此外,相同的表示方法(即圖嵌入)可以用於各種網絡相關的多分類問題。

本文的目標是學習到一個X_E矩陣,如下所示:比如將10個節點(|V|),每個節點壓縮成128維度(d)的向量。其中,d可以是一個低維分佈的向量,通過該低維連續稠密的向量(每個元素不為0)的每個元素來表達整個網絡。

利用這些結構特徵,我們將反映連接信息的Embedding和反映節點本身的特徵連接,用來幫助分類決策。這些特徵是通用的,可以用於任何分類算法(包括迭代方法)。然而,我們認為這些特性的最大優勢是它們很容易與簡單的機器學習算法集成。它們在現實世界的網絡中能夠被有效地擴展,我們將在第6節中展示。

4.網絡連接的特徵表示

該部分主要是描述Embedding。我們希望DeepWalk學到的Embedding(特徵表示)具有下列特性:

  • 適應性(Adaptabilty):真實網絡在持續地演化,新的節點和關係出現時不需要再重新訓練整個網絡,而是能夠增量或在線訓練。換句話説,網絡的拓撲結構隨着網絡新的節點和連接動態變化
  • 社區意識(Community aware):應該反映社羣的聚類信息,如圖1所示,屬於同一個社區的節點有着相似的表示,網絡中會出現一些特徵相似的點構成的團狀結構,這些節點表示成向量後也必須相似。這允許在具有同質性的網絡中進行泛化。
  • 低維(Low dimensional):當標記數據稀缺時,低維模型可以更好地擴展並加速收斂和推理(防止過擬合)。即每個頂點的向量維度不能過高。
  • 連續(Continuous):低維向量應該是連續的,每個元素的細微變化都會對結果有影響,並且能擬合平滑的決策邊界,從而實現魯棒性更強的分類任務。

DeepWalk是通過一連串隨機遊走序列來對節點進行嵌入(或表示)的,並是有最初的語義模型(Word2Vec)進行優化。接下來,我們將簡單回顧隨機遊走和語言模型的知識。

(1) Random Walks

假設將一個起始點v(i)的隨機遊走表示為W(vi),對應的隨機過程(stochastic process)定義為:

其中,k表示隨機遊走的第k步,v(i)表示起始點,之後的第k+1節點是從第k個節點的鄰居節點中隨機選擇一個,屬於均勻的隨機遊走。

隨機遊走已被應用於內容推薦和社區檢測領域中的各種相似性度量問題。通過該方法將離得近且容易走動(或連通)的節點聚集。隨機遊走也是輸出敏感類算法的基礎,這些算法利用隨機遊走來計算與輸入圖大小相關的局部社區結構信息。

  • Random Walk:假設相鄰節點具有相似性
  • Word2Vec:假設相鄰單詞具有相似性

這種局部結構信息可以促使我們利用一連串的隨機遊走來提取網絡的信息。除了捕獲社羣信息外,隨機遊走還有其它兩個比較好的優點。

  • 並行採樣
  • 在線增量學習(迭代學習不需要全局重新計算)

(2) Connection: Power laws(冪律分佈)

選擇在線隨機遊走算法作為捕獲圖結構的雛形後,我們現在需要一種合適的方法來捕獲這些信息。如果連通圖的度(degree)分佈遵循冪律分佈(即無標度圖,重要節點),我們觀察到頂點在隨機遊走中出現的頻率也將遵循冪律分佈。

  • 隨機網絡:節點的度服從正態分佈
  • 真實世界網絡:屬於無標度網絡,比如社交網絡存在大V、銀行客户存在富翁等,存在大型中樞節點,此時服從冪律分佈(長尾分佈或二八分佈)

圖2中展示了冪律分佈現象,圖2(a)是一個無標度圖一系列隨機遊走的分佈圖,圖2(b)是英文維基百科上的10萬篇文章的單詞冪律分佈圖。

  • 圖2(a)的橫軸表示被媒體提及次數,縱軸表示節點個數(UP主數量)
  • 圖2(b)的橫軸表示某個單詞被採樣到的次數,縱軸表示單詞數,比如the\an\we出現較多

冪律分佈參考我的前文:

為什麼介紹這部分內容呢?

我們工作的一個核心貢獻是將用於自然語言模型(冪律分佈或Zipf定律)的技術可以用在圖結構中建模(圖數據挖掘)。換句話説,真實世界中,只有極少部分的單詞被經常使用,或極少部分的節點被經常使用。

(3) Language Modeling

 

語言模型的目標是估計一個特定的單詞序列出現在一個語料中的似然概率(likelihood)。換句話説,給定一系列單詞W,通過上文的前n-1個詞來預測第n個詞。最近的表示學習研究就聚焦於利用神經網絡語言模型來實現詞的表示。

  • 語言模型能反映一句話是否自然、高頻或真實存在。

在本文中,我們提出了一種語言模型的推廣,通過一系列的隨機遊走路徑來進行建模。 隨機遊走可以被看作是一種特殊語言的短句或短語,節點類比成單詞,通過前i-1個節點來預測第i個節點(預測訪問頂點vi的可能性)。公式如下如下:

然而,本文希望利用的是節點的Embedding,而不是節點本身,如何解決呢?
我們的目標是學習一個隱式表示,因此引入一個映射函數Φ,即取出對應節點的Embedding。

接着我們就可以用公式(2)完成計算,通過前i-1個節點的Embedding來預測第i個節點。該問題是要估計它的似然概率 。

然而,隨着隨機遊走長度的增加,計算這個條件概率就變得不可行了(n個概率連續相乘結果太小)。

最近語言模型[27,28](Word2Vec)很好地解決了這個問題。它可以利用周圍上下文來預測中間缺失的單詞(CBOW),也可以利用中心詞去預測上下文單詞(Skip-gram),從而構建自監督場景。

  • [27] T. Mikolov, K. Chen, G. Corrado, and J. Dean. Efficient estimation of word representations in vector space. CoRR, abs/1301.3781, 2013.

Word2Vec將單詞編碼成向量如下圖所示:

其次,上下文是由同時出現在給定單詞的左右兩側的單詞組成的。最後,它消除了問題的順序約束,而是要求模型在不知道單詞與給定單詞之間的情況下,最大化上下文中任何單詞出現的偏移的概率。

DeepWalk(Skip-gram)的損失函數定義如下(優化問題),最大化似然概率:

  • 我們期待通過大量的隨機遊走序列訓練,迭代地去優化Φ中的每一個元素,直到這個函數收斂或損失函數最小化,此時的Φ就是每個節點的Embedding。

該方法對於圖嵌入(表示學習)非常適用。

  • 隨機遊走生成的順序沒有意義,符合當前場景,能很好地捕獲鄰近信息。
  • 模型較小能加快訓練時間。

方程3的優化問題:

  • 具有相同鄰居節點將獲得相似的表示(編碼共引相似)

總而言之,本文提出一種圖嵌入的表示方法,通過結合隨機遊走和語言模型,能將圖的每個節點編碼為一個連續、稠密、低維的向量(Embedding),其包含了社羣的語義特徵,適用於各種變化的網絡拓撲結構。==

5.本文方法

該部分將詳細介紹該算法的主要組件及變體。同各種語言模型算法一樣,需要構建語料庫和詞彙表。在DeepWalk中,語料庫就是一系列的隨機遊走序列,詞彙表就是節點集合本身(V)。

(1) Algorithm: DeepWalk

該算法的詳細描述如下圖所示:

a) SkipGram

SkipGram是一種語言模型,旨在利用中心詞去預測上下文單詞,它能反映詞和詞的共現關係,即使句子中出現在窗口w中的單詞共現概率最大化。它使用一個獨立假設來近似方程3中的條件概率,SkipGram計算Pr的算法如下:

  • 通過中心節點的Embedding和上下文的某個節點的Embedding做向量的數量積。

算法2是SkipGram的具體流程。給定vj表示,我們希望在隨機遊走中最大化它鄰居的概率(算法第3行)。此外,它也會遇到和Word2Vec相同的問題。當節點較多時,會有數以萬億的分類預測,其分母會很大。因此,為加快訓練時間,我們使用分層Softmax來近似概率分佈。

b) Hierarchical Softmax

分層Softmax計算如下,它會將頂點分配給二叉樹的葉子節點,將預測問題轉化為層次結構中特定路徑的概率最大化。

  • 時間複雜度從O(n)降至O(log(n))

前一篇Word2Vec論文中已詳細介紹:

  • Hierarchical Softmax:Huffman樹將較短的二進制代碼分配給頻繁出現的單詞,減少需要評估的輸出單元的數量。

如圖3c所示,原來的八分類問題轉換成了3個二分類(log2(8)=3)。圖中,最上層為葉子節點(8個),第二層和第三次的灰色方塊為非葉子節點,即邏輯迴歸二分類器(7個),其參數量和Embedding維度一致。V3和V5是標籤,兩條紅色先為對應的路徑,會按照公式計算對應的損失函數並更新Embedding。

接着詳細分析圖3。

  • 首先,圖3(a)表示從圖中隨機遊走採樣出一個節點序列(紅色標註);
  • 然後生成圖3(b)所示的映射關係,v4表示4號節點,輸入中心節點(v1)來預測上文和下文的節點,每側窗口寬度w=1,通過查表得到中心節點v1映射對應的表示Φ(v1);
  • 最後,將該中心詞的向量輸入到分層Softmax中(圖3c),由於v3和v5都是標籤,兩條路徑回各自計算損失函數,再各自優化更新,這裏存在兩套權重,分別是:N個節點的D維向量,N-1個邏輯迴歸(每個有D個權重),這兩套權重會被同時優化。

Pr(bl | Φ(vj)) 可以通過一個二分類器來建模,該分類器被分配給節點bl的父節點,如式6所示:

  • 公式的指數表示詞的Embedding和邏輯迴歸的權重的乘積,再通過Sigmod函數輸出一個後驗概率。

總之,我們通過在隨機遊走中分配更短的路徑來加快訓練過程(Hierarchical Softmax),霍夫曼編碼可以減少樹中頻繁元素的訪問時間。

c) Optimization(優化)

(2) Parallelizability

可以通過多線程異步並行(集羣)來實現DeepWalk,ASGD梯度通過MapReduce實現。實驗結果如圖4所示,證明了加速的有效性(性能不變&加速)。

(3) Algorithm Variants

 

變種算法主要包括:

  • Streaming
    在未知全圖時,直接通過採樣出的隨機遊走訓練Embedding,新的節點會增量對應的Embedding
  • Non-random walks
    不隨機的自然遊走

6.對比實驗

(1) 數據集和Baseline方法

實驗包括三個數據集。

  • BlogCatalog:博客作者提供的社會關係網絡,標籤代表作者提供的主題類別。
  • Flickr:照片分享網站,作者之間的聯繫網絡,標籤代表用户的興趣組。
  • YouTube:視頻分享網站,用户之間的社交網絡,標籤代表喜歡視頻類型(如動漫和摔跤)的觀眾羣體。

對比方法如下:

  • SpectralClustering(譜聚類)
  • Modularity(模塊化)
  • EdgeCluster
  • wvRN
  • Majority

(2) 實驗結果

評估指標包括:

  • T_R:標註的節點比例
  • Macro-F1
  • Micro-F1

實驗參數:

  • γ =80:每個節點被採樣的次數
  • w = 10:滑動窗口
  • d = 128:向量的維度
  • t = 40:遊走的節點長度

通過one-vs-rest邏輯迴歸分類器解決多分類問題(構建多個二分類實現多分類預測)。整個實驗結果如下所示:

  • DeepWalk預測效果優於其它算法
  • 當標註節點比例越小,DeepWalk效果表現越好,甚至只用20%的數據比其他算法用90%的數據更強

參數敏感性對比實驗如下圖所示:

  • TR會影響最優d,TR越大效果越好
  • γ越大,效果越好,但邊際效果逐漸降低

7.個人感受

首先,本文在相關工作中進一步突出DeepWalk的優勢,具體如下:

  • DeepWalk是通過機器學習得到的隱式表示(Embedding),而非人工統計構造。
  • DeepWalk不考慮節點的標註和特徵信息,只考慮Graph的連接信息,屬於無監督學習。後續可以利用無監督的Embedding和標註信息訓練有監督的分類模型。
  • DeepWalk是一種只使用Graph的局部信息且可擴展的在線學習方法,先前的方法都需要全局信息且是離線的。
  • 本文將無監督表示學習思路應用於圖中。

綜上所述,本文提出了DeepWalk,一種用來學習隱式網絡表徵的新穎方法。通過隨機遊走序列捕捉網絡的局部信息,再將每個節點編碼成向量Embedding,能有效表徵原圖的結構規律。通過實驗證明了DeepWalk多分類的有效性。

 

下圖是子豪老師的總結:

個人感受:

DeepWalk是圖嵌入(Graph Embedding)的開山之作,圖神經網絡領域非常重要的一篇論文。其核心思想是將Word2vec應用在圖中,語言模型和圖網絡的轉換非常精妙,DeepWalk將圖當作語言,節點當作單詞來生成Embedding。在DeepWalk中,它通過隨機遊走算法從一個節點隨機到另一個節點,從而將網絡化數據轉換成一個序列(Sequence),再無監督地生成對應的Embedding,其擴展性、性能和並行性都表現良好,且支持在線學習。此外,上一篇文章我們介紹了Word2Vec,推薦大家結合閲讀。

最後,好文章就是好文章,真心值得我們學習。同時,本文除了作者閲讀原文外,也學習了B站同濟子豪老師的視頻,強烈推薦大家去學習和關注。在此表示感謝,他也説到,本文可能存在一些語法錯誤,但最重要的是Idea,大家寫論文也優先把握好的Idea和貢獻,花更多精力在那方面。

 

點擊關注,第一時間瞭解華為雲新鮮技術~