圖學(xué)習(xí)之圖游走類(lèi)deepwalk,node2vec模型「系列四」
1.圖游走類(lèi)算法原理前言
1.1 Graph Embedding
更多詳情參考：Paddle Graph Learning 圖學(xué)習(xí)之圖游走類(lèi)模型[系列四] https://aistudio.baidu.com/aistudio/projectdetail/5002782?contributionType=1
在開(kāi)始介紹圖游走算法之前，先來(lái)學(xué)習(xí)一下什么是Graph Embedding。
圖嵌入是一種將圖數(shù)據(jù)（通常為高維稠密的矩陣）映射為低微稠密向量的過(guò)程，如下圖所示。圖嵌入需要捕捉到圖的拓?fù)浣Y(jié)構(gòu)，頂點(diǎn)與頂點(diǎn)的關(guān)系，以及其他的信息 （如子圖，連邊等）。如果有更多的信息被表示出來(lái)，那么下游的任務(wù)將會(huì)獲得更好的表現(xiàn)。在嵌入的過(guò)程中存在著一種共識(shí)：向量空間中保持連接的節(jié)點(diǎn)彼此靠近。
總的來(lái)說(shuō)圖嵌入技術(shù)大致可以分為兩種：節(jié)點(diǎn)嵌入和圖嵌入。
當(dāng)需要對(duì)節(jié)點(diǎn)進(jìn)行分類(lèi)，節(jié)點(diǎn)相似度預(yù)測(cè)，節(jié)點(diǎn)分布可視化時(shí)一般采用節(jié)點(diǎn)的嵌入；
當(dāng)需要在圖級(jí)別（graph-level）上進(jìn)行預(yù)測(cè)或者整個(gè)圖結(jié)構(gòu)決策，需要將整個(gè)圖表示為一個(gè)向量進(jìn)行嵌入表示。
圖學(xué)習(xí)的方法，大部分都可以應(yīng)用到圖嵌入問(wèn)題中，所以圖嵌入問(wèn)題屬于圖學(xué)習(xí)中的一個(gè)非常重要的應(yīng)用領(lǐng)域，不同的方法涉及了多方面知識(shí)。
我們可以將圖嵌入的這些方法簡(jiǎn)要分為以下這些類(lèi)別：
|基于矩陣分解傳統(tǒng)方法| 基于游走策略 | 基于游走策略和其他信息 | 基于深度學(xué)習(xí) | 基于GAN | | -------- | -------- | -------- | -------- | -------- | |Laplacian Eigenmaps| deepwalk | CENE | GCN | GraphGAN | |Locally Linear Embedding| node2vec | CANE | SDNE | ANE | |Graph Factorization | struc2vec | Trans-Net | || LINE| || GraRep | | |GraphSAGE|
1.1.1 為什么要使用圖嵌入（graph embedding）
圖是一種簡(jiǎn)單、易于理解的表示形式，但是由于下面的原因，我們需要對(duì)圖進(jìn)行嵌入表示：
在graph上直接進(jìn)行機(jī)器學(xué)習(xí)具有一定的局限性，我們都知道圖是由節(jié)點(diǎn)和邊構(gòu)成，這些向量關(guān)系一般只能使用數(shù)學(xué)，統(tǒng)計(jì)或者特定的子集進(jìn)行表示，但是嵌入之后的向量空間具有更加靈活和豐富的計(jì)算方式。
圖嵌入能夠壓縮數(shù)據(jù)， 我們一般用鄰接矩陣描述圖中節(jié)點(diǎn)之間的連接。 連接矩陣的維度是$|V| \times|V|$，其中$|V|$ 是圖中節(jié)點(diǎn)的個(gè)數(shù)。矩陣中的每一列和每一行都代表一個(gè)節(jié)點(diǎn)。矩陣中的非零值表示兩個(gè)節(jié)點(diǎn)已連接。將鄰接矩陣用用大型圖的特征空間幾乎是不可能的。一個(gè)具有1M節(jié)點(diǎn)和1M $\times$ 1M的鄰接矩陣的圖該怎么表示和計(jì)算呢？但是嵌入可以看做是一種壓縮技術(shù)，能夠起到降維的作用。
向量計(jì)算比直接在圖上操作更加的簡(jiǎn)單、快捷
但是圖嵌入也需要滿(mǎn)足一定的要求
學(xué)習(xí)屬性的選擇：不同的向量化表示方法，都是對(duì)網(wǎng)絡(luò)信息的一種摘要。有時(shí)我們會(huì)傾向于保存網(wǎng)絡(luò)中節(jié)點(diǎn)的近鄰關(guān)系，有時(shí)傾向?qū)W習(xí)節(jié)點(diǎn)在網(wǎng)絡(luò)中的角色（比如中心節(jié)點(diǎn)）。不同的應(yīng)用對(duì)“學(xué)習(xí)屬性”的選擇有不同的要求，故而引發(fā)了各類(lèi)算法的爆發(fā)。
規(guī)?；?/strong>：現(xiàn)實(shí)應(yīng)用中有很多網(wǎng)絡(luò)包含了大量的節(jié)點(diǎn)和邊，高效的向量化方法，能夠在短時(shí)間內(nèi)處理超大規(guī)模的網(wǎng)絡(luò)，才比較有實(shí)際應(yīng)用的可能性。
向量維度：如何確定合適的向量表示維度，是一個(gè)很難的問(wèn)題，并且也是和具體場(chǎng)景相關(guān)的。事實(shí)上，越高的維度可能帶來(lái)越好的效果，但是會(huì)極大降低應(yīng)用性能。平衡性能和效果，在不同的應(yīng)用中需要因地制宜。
1.2 詞語(yǔ)嵌入方法(word2vec)
node2vec是節(jié)點(diǎn)嵌入方法中的代表，而節(jié)點(diǎn)的嵌入方法借鑒了自然語(yǔ)言處理（NLP）中很一個(gè)重要的方法——word2vec。更多資料可以參考詞向量word2vec
該方法能夠成立的核心原因是：圖中的節(jié)點(diǎn)和語(yǔ)料庫(kù)中的單詞的分布都遵循冪定律，我們可以利用基于大量數(shù)據(jù)的學(xué)習(xí)方法來(lái)找出節(jié)點(diǎn)之間、單詞之間的規(guī)律。
圖游走算法：在圖上進(jìn)行游走得到游走序列，通過(guò)圖表示學(xué)習(xí)利用節(jié)點(diǎn)之間的關(guān)系得到節(jié)點(diǎn)的一維表示，進(jìn)而用這些一維表示進(jìn)行下游人物。
圖游走類(lèi)算法的目標(biāo)，就是學(xué)習(xí)出圖中每一個(gè)節(jié)點(diǎn)的低維表示，稱(chēng)為 Node Embeddings，在得到這些 embeddings 之后，就可以利用這些低維表示來(lái)進(jìn)行接下來(lái)的下游任務(wù)，比如節(jié)點(diǎn)分類(lèi)之類(lèi)的等等。
為什么可以用這個(gè)低維表示來(lái)做下游任務(wù)呢？
因?yàn)榭梢岳靡恍┓椒ǎ沟妹總€(gè)節(jié)點(diǎn)的 embeddings 可以學(xué)習(xí)到節(jié)點(diǎn)跟它的鄰居的關(guān)系，更好的表示圖結(jié)構(gòu)和圖特征的信息。
圖游走算法最先參考的是NLP的Word2vec模型，Word2vec模型的其中一種方法是Skip Gram，即根據(jù)中心詞預(yù)測(cè)上下文，之后通過(guò)負(fù)采樣的方式進(jìn)行優(yōu)化。
將Word2vec的思想和圖結(jié)合起來(lái)就會(huì)得到了圖游走類(lèi)算法
算法思想
假設(shè)，如果只給出蘋(píng)果這一個(gè)詞，而沒(méi)有其他的信息，那么，這個(gè)詞的詞義其實(shí)是模糊的。因?yàn)樘O(píng)果可能指的是水果，又或者是手機(jī)，但如果給出有關(guān)于蘋(píng)果的很多個(gè)句子：通過(guò)多個(gè)句子的上下文，其實(shí)可以大概了解到，上面所展示的蘋(píng)果這個(gè)詞的語(yǔ)義，是一種水果、一種食物。通過(guò)這個(gè)例子，可以得出這樣的一個(gè)結(jié)論，即詞的語(yǔ)義由其上下文決定。Word2vec 其實(shí)就是利用了這樣的一個(gè)思想。
整體架構(gòu)
Word2vec 模型，可以簡(jiǎn)單地理解為 Skip Gram + 負(fù)采樣
1.1.1 Skip Gram模型——根據(jù)中心詞預(yù)測(cè)上下文
在Word2vec 中，提出了兩種模型結(jié)構(gòu)用于學(xué)習(xí)詞向量，分別是 CBOW 和 Skip Gram。由于圖游走類(lèi)算法用的多是 skip-gram 模型，因此這里只介紹 skip-gram 模型。Skip Gram的目的很簡(jiǎn)單，就是根據(jù)中心詞，預(yù)測(cè)對(duì)應(yīng)中心詞的上下文詞。這樣做不僅僅能夠利用了詞共現(xiàn)關(guān)系，同時(shí)也體現(xiàn)了 Word2vec的本質(zhì)，即詞的語(yǔ)義由其上下文來(lái)決定。
以下面這張圖片的句子為例，假設(shè) neighbors 為中心詞，同時(shí)我們?cè)O(shè)置了window size為3. 這個(gè)窗口大小表示左右兩邊的上下文詞數(shù)，因此 neighbors 的 context 為 uniformly from the，以及 of the last。
Skip gram 的模型結(jié)構(gòu)很簡(jiǎn)單，輸入層就是中心詞的 one hot 表示，經(jīng)過(guò)中間一個(gè)投影層后，在輸出層預(yù)測(cè)對(duì)應(yīng)的context word，因此最后一層就是一個(gè)softmax分類(lèi)層。
需要補(bǔ)充的一點(diǎn)是，使用 Skipgram語(yǔ)言模型的本質(zhì)并不是為了說(shuō)多么準(zhǔn)確的預(yù)測(cè) context words，而是為了得到模型的副產(chǎn)物，也就是詞向量。
通常在訓(xùn)練結(jié)束后，隱層的權(quán)重 W 會(huì)作為詞向量矩陣。
Word2Vec模型實(shí)際上分為了兩個(gè)部分：
第一部分為建立模型得到隱層參數(shù)，
第二部分是通過(guò)模型獲取嵌入詞向量。
Word2Vec的整個(gè)建模過(guò)程實(shí)際上與自編碼器（auto-encoder）的思想很相似，即先基于訓(xùn)練數(shù)據(jù)構(gòu)建一個(gè)神經(jīng)網(wǎng)絡(luò)，當(dāng)這個(gè)模型訓(xùn)練好以后，我們并不會(huì)用這個(gè)訓(xùn)練好的模型處理新的任務(wù)，我們真正需要的是這個(gè)模型通過(guò)訓(xùn)練數(shù)據(jù)所學(xué)得的參數(shù)，例如隱層的權(quán)重矩陣——后面我們將會(huì)看到這些權(quán)重在Word2Vec中實(shí)際上就是我們?cè)噲D去學(xué)習(xí)的“word vectors”?；谟?xùn)練數(shù)據(jù)建模的過(guò)程，我們給它一個(gè)名字叫“Fake Task”，意味著建模并不是我們最終的目的。
上面提到的這種方法實(shí)際上會(huì)在無(wú)監(jiān)督特征學(xué)習(xí)（unsupervised feature learning）中見(jiàn)到，最常見(jiàn)的就是自編碼器（auto-encoder）：通過(guò)在隱層將輸入進(jìn)行編碼壓縮，繼而在輸出層將數(shù)據(jù)解碼恢復(fù)初始狀態(tài)，訓(xùn)練完成后，我們會(huì)將輸出層“砍掉”，僅保留隱層。
我們?cè)谏厦嫣岬?，?xùn)練模型的真正目的是獲得模型基于訓(xùn)練數(shù)據(jù)學(xué)得的隱層權(quán)重。為了得到這些權(quán)重，我們首先要構(gòu)建一個(gè)完整的神經(jīng)網(wǎng)絡(luò)作為我們的“Fake Task”，后面再返回來(lái)看通過(guò)“Fake Task”我們?nèi)绾伍g接地得到這些詞向量。
模型的輸出概率代表著到我們?cè)~典中每個(gè)詞有多大可能性跟input word同時(shí)出現(xiàn)。舉個(gè)栗子，如果我們向神經(jīng)網(wǎng)絡(luò)模型中輸入一個(gè)單詞“Soviet“，那么最終模型的輸出概率中，像“Union”， ”Russia“這種相關(guān)詞的概率將遠(yuǎn)高于像”watermelon“，”kangaroo“非相關(guān)詞的概率。因?yàn)椤盪nion“，”Russia“在文本中更大可能在”Soviet“的窗口中出現(xiàn)。 我們將通過(guò)給神經(jīng)網(wǎng)絡(luò)輸入文本中成對(duì)的單詞來(lái)訓(xùn)練它完成上面所說(shuō)的概率計(jì)算。下面的圖中給出了一些我們的訓(xùn)練樣本的例子。
我們選定句子“The quick brown fox jumps over lazy dog”，設(shè)定我們的窗口大小為2，也就是說(shuō)我們僅選輸入詞前后各兩個(gè)詞和輸入詞進(jìn)行組合。下圖中，藍(lán)色代表input word，方框內(nèi)代表位于窗口內(nèi)的單詞。
我們的模型將會(huì)從每對(duì)單詞出現(xiàn)的次數(shù)中習(xí)得統(tǒng)計(jì)結(jié)果。例如，我們的神經(jīng)網(wǎng)絡(luò)可能會(huì)得到更多類(lèi)似（“fox”，“quick”）這樣的訓(xùn)練樣本對(duì)，而相對(duì)而言，對(duì)于（“fox”，“l(fā)azy”）這樣的組合卻看到的很少。因此，當(dāng)我們的模型完成訓(xùn)練后，給定一個(gè)單詞“fox”作為輸入，輸出的結(jié)果中“quick”或者“jumps”要比“l(fā)azy”被賦予更高的概率?？梢钥吹剑覀兛偸且灾虚g詞放在第一個(gè)位置，然后跟著我們的前后相鄰詞?？梢钥吹剑恳粚?duì)詞都是一個(gè)輸入和一個(gè)輸出組成的數(shù)據(jù)對(duì)(X,Y)。其中，X是feature，Y是label。
我們都知道神經(jīng)網(wǎng)絡(luò)只能接受數(shù)值輸入，我們不可能把一個(gè)單詞字符串作為輸入，因此我們得想個(gè)辦法來(lái)表示這些單詞。最常用的辦法就是基于訓(xùn)練文檔來(lái)構(gòu)建我們自己的詞匯表（vocabulary）再對(duì)單詞進(jìn)行one-hot編碼。模型的輸入如果為一個(gè)10000維的向量，那么輸出也是一個(gè)10000維度（詞匯表的大?。┑南蛄?，它包含了10000個(gè)概率，每一個(gè)概率代表著當(dāng)前詞是輸入樣本中output word的概率大小。
我們把這樣的詞組對(duì)分別表示成one-hot向量，input word的向量作為Fake Task網(wǎng)絡(luò)的輸入，output word的向量作為學(xué)習(xí)的目標(biāo)。
這樣，我們基于成對(duì)的單詞來(lái)對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，訓(xùn)練樣本是 ( input word, output word ) 這樣的單詞對(duì)，input word和output word都是one-hot編碼的向量。最終模型的輸出是一個(gè)概率分布。 如果我們現(xiàn)在想用300個(gè)特征來(lái)表示一個(gè)單詞（即每個(gè)詞可以被表示為300維的向量）。那么隱層的權(quán)重矩陣應(yīng)該為10000行，300列（隱層有300個(gè)結(jié)點(diǎn)）。
Fake Task的訓(xùn)練過(guò)程，我們最終的目標(biāo)就是學(xué)習(xí)這個(gè)隱層的權(quán)重矩陣。
這個(gè)隱層的權(quán)重矩陣，便成了一個(gè)“查找表（lookup table）”，進(jìn)行矩陣計(jì)算時(shí)，直接去查輸入向量中取值為1的維度下對(duì)應(yīng)的那些權(quán)重值。隱層的輸出就是每個(gè)輸入單詞的“嵌入詞向量”。
Word2Vec模型
經(jīng)過(guò)神經(jīng)網(wǎng)絡(luò)隱層的計(jì)算，ants這個(gè)詞會(huì)從一個(gè)1 x 10000的向量變成1 x 300的向量，再被輸入到輸出層。輸出層是一個(gè)softmax回歸分類(lèi)器，它的每個(gè)結(jié)點(diǎn)將會(huì)輸出一個(gè)0-1之間的值（概率），這些所有輸出層神經(jīng)元結(jié)點(diǎn)的概率之和為1。
現(xiàn)在，我們擁有10000個(gè)單詞的詞匯表，我們?nèi)绻肭度?00維的詞向量，那么我們的輸入-隱層權(quán)重矩陣和隱層-輸出層的權(quán)重矩陣都會(huì)有 10000 x 300 = 300萬(wàn)個(gè)權(quán)重，在如此龐大的神經(jīng)網(wǎng)絡(luò)中進(jìn)行梯度下降是相當(dāng)慢的。更糟糕的是，你需要大量的訓(xùn)練數(shù)據(jù)來(lái)調(diào)整這些權(quán)重并且避免過(guò)擬合。百萬(wàn)數(shù)量級(jí)的權(quán)重矩陣和億萬(wàn)數(shù)量級(jí)的訓(xùn)練樣本意味著訓(xùn)練這個(gè)模型將會(huì)是個(gè)災(zāi)難。
Word2Vec論文提出了三個(gè)創(chuàng)新點(diǎn)：
將常見(jiàn)的單詞組合（word pairs）或者詞組作為單個(gè)“words”來(lái)處理。
對(duì)高頻次單詞抽樣來(lái)減少訓(xùn)練樣本的個(gè)數(shù)。
對(duì)優(yōu)化目標(biāo)采用“negative sampling”方法，這樣每個(gè)訓(xùn)練樣本的訓(xùn)練只會(huì)更新一小部分的模型權(quán)重，從而降低計(jì)算負(fù)擔(dān)。
更多資料可以參考[詞向量word2vec]
1.1.2 Negative Sampling——負(fù)采樣
假設(shè)，給定中心詞 orange，預(yù)測(cè)其上下文詞中的 juice：
Softmax 層在 Skipgram 模型中是用來(lái)計(jì)算詞表的概率的。
為了能夠預(yù)測(cè)出 juice，不僅要預(yù)測(cè)它的概率，還要預(yù)測(cè)整個(gè)詞表中所有單詞的概率。但這樣做的計(jì)算量是非常大的，因此，這里使用負(fù)采樣的方法進(jìn)行優(yōu)化。
負(fù)采樣的思想很簡(jiǎn)單。將中心詞和對(duì)應(yīng)的上下文詞作為正樣本，比如這里的 (orange, juice)。同時(shí)，選取一定數(shù)量的負(fù)樣本，比如3個(gè)。
確定要正樣本和負(fù)樣本之后，就不再需要計(jì)算所有詞的概率，而只需要對(duì)這幾個(gè)樣本進(jìn)行分類(lèi)，如果 Y=1，意味著是正樣本，Y=0，意味著是負(fù)樣本。從而減少了計(jì)算量。
也就是把 softmax 層修改為了多個(gè) sigmoid 函數(shù)，從而大大減少了計(jì)算量和參與權(quán)重更新的參數(shù)數(shù)目。
1.1.3 應(yīng)用到圖嵌入領(lǐng)域
近朱者赤，近墨者黑。
也就是說(shuō)，周遭的環(huán)境對(duì)于我們來(lái)說(shuō)會(huì)有一定的影響，因此也可以表現(xiàn)為，圖中的節(jié)點(diǎn)會(huì)受到其鄰居的影響。
當(dāng)然，這種情況也不僅僅只存在社交網(wǎng)絡(luò)這個(gè)范圍內(nèi)，在很多其他的圖，比如推薦系統(tǒng)等等，節(jié)點(diǎn)都會(huì)受到鄰居的影響。
這也是為什么可以將Word2vec這個(gè)方法遷移到圖嵌入領(lǐng)域的原因
2.DeepWalk（原理+實(shí)踐）
游走模型的鼻祖是DeepWalk模型，它也是第一個(gè)將 NLP 領(lǐng)域的思想運(yùn)用到圖嵌入領(lǐng)域的模型。
2.1 節(jié)點(diǎn)嵌入方法（Node embeddings）
首先為什么要用DeepWalk。我們可以觀察到，Word2Vec中，處理的是語(yǔ)句數(shù)據(jù)，詞語(yǔ)之間只有前后之間的聯(lián)系，可以很自然的將句子中的詞語(yǔ)分成不同的詞組。但是在圖數(shù)據(jù)中，節(jié)點(diǎn)與節(jié)點(diǎn)之前的聯(lián)系——邊，邊的構(gòu)成使得圖數(shù)據(jù)能夠比語(yǔ)句數(shù)據(jù)構(gòu)成節(jié)點(diǎn)之間更加復(fù)雜的關(guān)系。通過(guò)游走策略，我們可以將一個(gè)復(fù)雜的圖數(shù)據(jù)轉(zhuǎn)換為多個(gè)之后前后關(guān)聯(lián)的鏈路數(shù)據(jù)。
DeepWalk通過(guò)隨機(jī)游走(truncated random walk)學(xué)習(xí)出一個(gè)網(wǎng)絡(luò)的表示，在網(wǎng)絡(luò)標(biāo)注頂點(diǎn)很少的情況也能得到比較好的效果。隨機(jī)游走起始于選定的節(jié)點(diǎn)，然后從當(dāng)前節(jié)點(diǎn)移至隨機(jī)鄰居，并執(zhí)行一定的步數(shù)，該方法大致可分為四個(gè)步驟：
圖a展示了原始的用戶(hù)行為序列。
圖b基于這些用戶(hù)行為序列構(gòu)建了物品相關(guān)圖，可以看出，物品A，B之間的邊產(chǎn)生的原因就是因?yàn)橛脩?hù)U1先后購(gòu)買(mǎi)了物品A和物品B，所以產(chǎn)生了一條由A到B的有向邊。如果后續(xù)產(chǎn)生了多條相同的有向邊，則有向邊的權(quán)重被加強(qiáng)。在將所有用戶(hù)行為序列都轉(zhuǎn)換成物品相關(guān)圖中的邊之后，全局的物品相關(guān)圖就建立起來(lái)了。
圖c采用隨機(jī)游走的方式隨機(jī)選擇起始點(diǎn)，重新產(chǎn)生物品序列。
圖d最終將這些物品序列輸入word2vec模型，生成最終的物品Embedding向量。
在上述DeepWalk的算法流程中，核心是第三步，其中唯一需要形式化定義的是隨機(jī)游走的跳轉(zhuǎn)概率，也就是到達(dá)節(jié)點(diǎn)$vi$后，下一步遍歷$vi$的臨接點(diǎn)$vj$的概率。如果物品的相關(guān)圖是有向有權(quán)圖，那么從節(jié)點(diǎn)$vi$跳轉(zhuǎn)到節(jié)點(diǎn)$v_j$的概率定義如下：
$$P(v{j}|v{i})=\left{\begin{matrix} \frac{M{ij}}{\sum{j\in N+(v{i})}M{ij}} & , v{j} \in N+(v{i}),\ 0&, e_{ij}\notin \varepsilon
\end{matrix}\right.$$
其中$N+(vi)$是節(jié)點(diǎn)$vi$所有的出邊集合，$M{ij}$是節(jié)點(diǎn)$vi$到節(jié)點(diǎn)$vj$邊的權(quán)重。
如果物品相關(guān)圖是無(wú)相無(wú)權(quán)重圖，那么跳轉(zhuǎn)概率將是上面公式的一個(gè)特例，即權(quán)重$M{ij}$將為常數(shù)1，且$N+(vi)$應(yīng)是節(jié)點(diǎn)$vi$所有“邊”的集合，而不是所有“出邊”的集合。
DeepWalk通過(guò)隨機(jī)游走去可以獲圖中點(diǎn)的局部上下文信息，因此學(xué)到的表示向量反映的是該點(diǎn)在圖中的局部結(jié)構(gòu)，兩個(gè)點(diǎn)在圖中共有的鄰近點(diǎn)（或者高階鄰近點(diǎn)）越多，則對(duì)應(yīng)的兩個(gè)向量之間的距離就越短
整體架構(gòu)
DeepWalk就相當(dāng)于隨機(jī)游走+Skip Gram+負(fù)采樣的結(jié)合
與 Word2vec 的不同，其實(shí)就是多了一個(gè)采樣節(jié)點(diǎn)序列的隨機(jī)游走部分。因此這兩者實(shí)現(xiàn)起來(lái)其實(shí)是非常類(lèi)似的。
在DeepWalk中，將每個(gè)節(jié)點(diǎn)看作是單詞，節(jié)點(diǎn)序列看作是句子。如下圖
Random Walk
不同于NLP中可以獲取很多的語(yǔ)料，DeepWalk采用了隨機(jī)游走的方法來(lái)獲取節(jié)點(diǎn)序列（可回頭的深度優(yōu)先搜索）。下式中的π是節(jié)點(diǎn)的轉(zhuǎn)移概率分布，Z是歸一化系數(shù)，在DeepWalk中可以理解成轉(zhuǎn)移到每一個(gè)鄰居節(jié)點(diǎn)的概率都是相同的。
具體過(guò)程
從圖中的某個(gè)節(jié)點(diǎn)出發(fā)，游走的每一步都從與當(dāng)前節(jié)點(diǎn)相連的邊中隨機(jī)選擇一條，沿著選定的邊移動(dòng)到下一個(gè)頂點(diǎn)，不斷重復(fù)這個(gè)過(guò)程，直到得到的序列無(wú)法繼續(xù)往下走或者到達(dá)指定最大長(zhǎng)度。
在走了多趟之后，便可以得到多個(gè)游走序列，此時(shí)就可以類(lèi)比 NLP 中的句子了。
隨機(jī)游走的本質(zhì)，其實(shí)就是可以“回頭”的深度優(yōu)先搜索
DeepWalk選取隨機(jī)游走序列中下一個(gè)節(jié)點(diǎn)的方式是均勻隨機(jī)分布的，因此對(duì)于與當(dāng)前節(jié)點(diǎn)有邊相連的節(jié)點(diǎn)，都有相同的概率被選擇。
在 DeepWalk 中，會(huì)針對(duì)圖中的每個(gè)節(jié)點(diǎn)采樣多條序列，得到這些節(jié)點(diǎn)序列之后，就可以直接套用 Word2vec 模型了。
2.2 DeepWalk代碼實(shí)現(xiàn)
更多詳情參考：Paddle Graph Learning 圖學(xué)習(xí)之圖游走類(lèi)模型[系列四] https://aistudio.baidu.com/aistudio/projectdetail/5002782?contributionType=1
3. node2vec（原理+實(shí)踐）
3.1 node2vec原理
Node2vec是圖表征學(xué)習(xí)的一個(gè)重要的算法框架。
框架圖：
2016年，斯坦福大學(xué)在DeepWalk的基礎(chǔ)上更進(jìn)一步，通過(guò)調(diào)整隨機(jī)游走權(quán)重的方法使graph embedding的結(jié)果在網(wǎng)絡(luò)的同質(zhì)性（homophily）和結(jié)構(gòu)性（structural equivalence）中進(jìn)行權(quán)衡權(quán)衡。 具體來(lái)講，網(wǎng)絡(luò)的“同質(zhì)性”指的是距離相近節(jié)點(diǎn)的embedding應(yīng)該盡量近似，如下圖所示，節(jié)點(diǎn)u與其相連的節(jié)點(diǎn)s1、s2、s3、s4的embedding表達(dá)應(yīng)該是接近的，這就是“同質(zhì)性“的體現(xiàn)。“結(jié)構(gòu)性”指的是結(jié)構(gòu)上相似的節(jié)點(diǎn)的embedding應(yīng)該盡量接近，圖中節(jié)點(diǎn)u和節(jié)點(diǎn)s6都是各自局域網(wǎng)絡(luò)的中心節(jié)點(diǎn)，結(jié)構(gòu)上相似，其embedding的表達(dá)也應(yīng)該近似，這是“結(jié)構(gòu)性”的體現(xiàn)。
DeepWalk存在的問(wèn)題是比較簡(jiǎn)單直接，而圖結(jié)構(gòu)往往是一個(gè)復(fù)雜結(jié)構(gòu)，需要考慮很多因素，在深度優(yōu)先搜索方法之外，還有廣度優(yōu)先搜索，結(jié)合以上兩種方式可以更好的探索圖模型，即node2vec。
node2vec和DeepWalk相比主要修改的是轉(zhuǎn)移概率分布，不同于隨機(jī)游走相鄰節(jié)點(diǎn)轉(zhuǎn)移的概率相同，node2vec考慮了邊的權(quán)值和節(jié)點(diǎn)之間的距離，具體如下：
為了使Graph Embedding的結(jié)果能夠表達(dá)網(wǎng)絡(luò)的同質(zhì)性，在隨機(jī)游走的過(guò)程中，需要讓游走的過(guò)程更傾向于寬度優(yōu)先搜索（BFS），因?yàn)锽FS更喜歡游走到跟當(dāng)前節(jié)點(diǎn)有直接連接的節(jié)點(diǎn)上，因此就會(huì)有更多同質(zhì)性信息包含到生成的樣本序列中，從而被embedding表達(dá)；
另一方面，為了抓住網(wǎng)絡(luò)的結(jié)構(gòu)性，就需要隨機(jī)游走更傾向于深度優(yōu)先搜索（DFS），因?yàn)镈FS會(huì)更傾向于通過(guò)多次跳轉(zhuǎn)，游走到遠(yuǎn)方的節(jié)點(diǎn)上，使得生成的樣本序列包含更多網(wǎng)絡(luò)的整體結(jié)構(gòu)信息。
那么在node2vec算法中，是怎樣控制BFS和DFS的傾向性的呢？主要是通過(guò)節(jié)點(diǎn)間的跳轉(zhuǎn)概率。下圖顯示了node2vec算法從節(jié)點(diǎn)t跳轉(zhuǎn)到節(jié)點(diǎn)v后，下一步從節(jié)點(diǎn)v跳轉(zhuǎn)到周?chē)鼽c(diǎn)的跳轉(zhuǎn)概率。
形式化來(lái)講，從節(jié)點(diǎn)v跳轉(zhuǎn)到下一個(gè)節(jié)點(diǎn)x的概率為
上式中的p和q是算法中的超參數(shù)，通過(guò)控制兩個(gè)參數(shù)來(lái)確定圖的游走程度。參數(shù)p控制隨機(jī)游走以多大的概率游走回上一個(gè)節(jié)點(diǎn)，參數(shù)q控制游走的策略是偏向DFS還是BFS，q較大時(shí)偏向于BFS，q較小時(shí)偏向于DFS。當(dāng)p=q=1時(shí)，π=w
node2vec所體現(xiàn)的網(wǎng)絡(luò)的同質(zhì)性和結(jié)構(gòu)性在推薦系統(tǒng)中也是可以被很直觀的解釋的。同質(zhì)性相同的物品很可能是同品類(lèi)、同屬性、或者經(jīng)常被一同購(gòu)買(mǎi)的物品，而結(jié)構(gòu)性相同的物品則是各品類(lèi)的爆款、各品類(lèi)的最佳湊單商品等擁有類(lèi)似趨勢(shì)或者結(jié)構(gòu)性屬性的物品。毫無(wú)疑問(wèn)，二者在推薦系統(tǒng)中都是非常重要的特征表達(dá)。由于node2vec的這種靈活性，以及發(fā)掘不同特征的能力，甚至可以把不同node2vec生成的embedding融合共同輸入后續(xù)深度學(xué)習(xí)網(wǎng)絡(luò)，以保留物品的不同特征信息。
因存在多版本問(wèn)題（基于PGL1.2.1 paddle1.8），這部分的詳細(xì)實(shí)現(xiàn)參考鏈接：圖學(xué)習(xí)【參考資料2】-知識(shí)補(bǔ)充與node2vec代碼注解 https://aistudio.baidu.com/aistudio/projectdetail/5012408?contributionType=1
更多詳情參考：Paddle Graph Learning 圖學(xué)習(xí)之圖游走類(lèi)模型[系列四] https://aistudio.baidu.com/aistudio/projectdetail/5002782?contributionType=1
4.基于PGL2.2版本算法實(shí)現(xiàn)
4.1 數(shù)據(jù)集介紹
4.1.1 引文網(wǎng)絡(luò)（Cora、PubMed、Citeseer）
引文網(wǎng)絡(luò)，顧名思義就是由論文和他們的關(guān)系構(gòu)成的網(wǎng)絡(luò)，這些關(guān)系包括例如引用關(guān)系、共同的作者等，具有天然的圖結(jié)構(gòu)，數(shù)據(jù)集的任務(wù)一般是論文的分類(lèi)和連接的預(yù)測(cè)，比較流行的數(shù)據(jù)集有三個(gè)，分別是Cora、PubMed、Citeseer，它們的組成情況如圖1所示，Nodes也就是數(shù)據(jù)集的論文數(shù)量，features是每篇論文的特征，數(shù)據(jù)集中有一個(gè)包含多個(gè)單詞的詞匯表，去除了出現(xiàn)頻率小于10的詞，但是不進(jìn)行編碼，論文的屬性是由一串二進(jìn)制碼構(gòu)成，只用0和1表示該論文有無(wú)這個(gè)詞匯。
文件構(gòu)成
以cora數(shù)據(jù)集為例，數(shù)據(jù)集包含兩個(gè)文件，cora.cites和cora.content，cora.cites文件中的數(shù)據(jù)如下：
即原論文和引用的論文，剛好構(gòu)成了一條天然的邊，cora.content文件的數(shù)據(jù)如下：
+
有論文id、上面說(shuō)到的二進(jìn)制碼和論文對(duì)應(yīng)的類(lèi)別組成，其余兩個(gè)數(shù)據(jù)集類(lèi)似。
4.1.2 社交網(wǎng)絡(luò)（BlogCatalog、Reddit、Epinions）
BlogCatalog數(shù)據(jù)集是一個(gè)社會(huì)關(guān)系網(wǎng)絡(luò)，圖是由博主和他（她）的社會(huì)關(guān)系（比如好友）組成，labels是博主的興趣愛(ài)好。Reddit數(shù)據(jù)集是由來(lái)自Reddit論壇的帖子組成，如果兩個(gè)帖子被同一人評(píng)論，那么在構(gòu)圖的時(shí)候，就認(rèn)為這兩個(gè)帖子是相關(guān)聯(lián)的，labels就是每個(gè)帖子對(duì)應(yīng)的社區(qū)分類(lèi)。Epinions是一個(gè)從一個(gè)在線商品評(píng)論網(wǎng)站收集的多圖數(shù)據(jù)集，里面包含了多種關(guān)系，比如評(píng)論者對(duì)于另一個(gè)評(píng)論者的態(tài)度（信任/不信任），以及評(píng)論者對(duì)商品的評(píng)級(jí)。
文件構(gòu)成
BlogCatalog數(shù)據(jù)集的結(jié)點(diǎn)數(shù)為10312，邊條數(shù)為333983，label維度為39，數(shù)據(jù)集包含兩個(gè)文件：
Nodes.csv：以字典的形式存儲(chǔ)用戶(hù)的信息，但是只包含節(jié)點(diǎn)id。
Edges.csv：存儲(chǔ)博主的社交網(wǎng)絡(luò)（好友等），以此來(lái)構(gòu)圖。
Epinions數(shù)據(jù)集包含文件如下：
Ratingsdata.txt：包含用戶(hù)對(duì)于一件物品的評(píng)級(jí)，文件中每一行的結(jié)構(gòu)為userid
itemid ratingvalue。
Trustdata.txt：存儲(chǔ)了用戶(hù)對(duì)其他用戶(hù)的信任狀態(tài)，存儲(chǔ)方式為sourceuser_id
targetuserid truststatementvalue，其中信任狀態(tài)只有信任和不信任（1、0）。
由于Reddit comments 數(shù)據(jù)集的文件太多，所以這里略過(guò)了，如果需要或者感興趣的話，可以從文末的連接進(jìn)入查看。
相關(guān)論文：
Rossi, R. A. , & Ahmed, N. K. . (2015). The Network Data Repository with Interactive Graph Analytics and Visualization. Twenty-ninth Aaai Conference on Artificial Intelligence. AAAI Press.
### 4.1.3.生物化學(xué)結(jié)構(gòu)（PPI、NCI-1、NCI-109、MUTAG、QM9、Tox21） PPI是蛋白質(zhì)互作網(wǎng)絡(luò)，數(shù)據(jù)集中共有24張圖，其中20張作為訓(xùn)練，2張作為驗(yàn)證，2張作為測(cè)試，每張圖對(duì)應(yīng)不同的人體組織，實(shí)例如圖3，該數(shù)據(jù)是為了從系統(tǒng)的角度研究疾病分子機(jī)制、發(fā)現(xiàn)新藥靶點(diǎn)等等。
平均每張圖有2372個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)特征長(zhǎng)度為50，其中包含位置基因集，基序集和免疫學(xué)特征?；虮倔w集作為labels（總共121個(gè)），labels不是one-hot編碼。
NCI-1、NCI-109和MUTAG是關(guān)于化學(xué)分子和化合物的數(shù)據(jù)集，原子代表結(jié)點(diǎn)，化學(xué)鍵代表邊。NCI-1和NCI-109數(shù)據(jù)集分別包含4100和4127個(gè)化合物，labels是判斷化合物是否有阻礙癌細(xì)胞增長(zhǎng)得性質(zhì)。MUTAG數(shù)據(jù)集包含188個(gè)硝基化合物，labels是判斷化合物是芳香族還是雜芳族。
QM9數(shù)據(jù)集包括了13萬(wàn)有機(jī)分子的構(gòu)成,空間信息及其對(duì)應(yīng)的屬性. 它被廣泛應(yīng)用于各類(lèi)數(shù)據(jù)驅(qū)動(dòng)的分子屬性預(yù)測(cè)方法的實(shí)驗(yàn)和對(duì)比。
Toxicology in the 21st Century 簡(jiǎn)稱(chēng)tox21，任務(wù)是使用化學(xué)結(jié)構(gòu)數(shù)據(jù)預(yù)測(cè)化合物對(duì)生物化學(xué)途徑的干擾，研究、開(kāi)發(fā)、評(píng)估和翻譯創(chuàng)新的測(cè)試方法，以更好地預(yù)測(cè)物質(zhì)如何影響人類(lèi)和環(huán)境。數(shù)據(jù)集有12707張圖，12個(gè)labels。
文件構(gòu)成 PPI數(shù)據(jù)集的構(gòu)成：
train/test/valid_graph.json：保存了訓(xùn)練、驗(yàn)證、測(cè)試的圖結(jié)構(gòu)數(shù)據(jù)。
train/test/valid_feats.npy ：保存結(jié)點(diǎn)的特征，以numpy.ndarry的形式存儲(chǔ)，shape為[n, v]，n是結(jié)點(diǎn)的個(gè)數(shù)，v是特征的長(zhǎng)度。
train/test/valid_labels.npy：保存結(jié)點(diǎn)的label，也是以numpy.ndarry的形式存儲(chǔ)，形為n*h，h為label的長(zhǎng)度。
train/test/valid/_graph_id.npy ：表示這個(gè)結(jié)點(diǎn)屬于哪張圖，形式為numpy.ndarry，例如[1, 1, 2, 1...20].。
NCI-1、NCI-109和MUTAG數(shù)據(jù)集的文件構(gòu)成如下：（用DS代替數(shù)據(jù)集名稱(chēng)）
n表示結(jié)點(diǎn)數(shù)，m表示邊的個(gè)數(shù)，N表示圖的個(gè)數(shù)
DS_A.txt (m lines)：圖的鄰接矩陣，每一行的結(jié)構(gòu)為(row, col)，即一條邊。
DS_graph_indicator.txt (n lines)：表明結(jié)點(diǎn)屬于哪一個(gè)圖的文件。
DS_graph_labels.txt (N lines)：圖的labels。
DS_node_labels.txt (n lines)：結(jié)點(diǎn)的labels。
DS_edge_labels.txt (m lines)：邊labels。
DS_edge_attributes.txt (m lines)：邊特征。
DS_node_attributes.txt (n lines)：結(jié)點(diǎn)的特征。
DS_graph_attributes.txt (N lines)：圖的特征，可以理解為全局變量。QM9的文件結(jié)構(gòu)如下：QM9_nano.npz：該文件需要用numpy讀取,其中包含三個(gè)字段：
'ID' 分子的id，如:qm9:000001；
'Atom' 分子的原子構(gòu)成，為一個(gè)由原子序數(shù)的列表構(gòu)成,如[6,1,1,1,1]表示該分子由一個(gè)碳(C)原子和4個(gè)氫(H)原子構(gòu)成.；
'Distance' 分子中原子的距離矩陣,以上面[6,1,1,1,1]分子為例,它的距離矩陣即為一個(gè)5x5的矩陣,其中行列的順序和上述列表一致,即矩陣的第N行/列對(duì)應(yīng)的是列表的第N個(gè)原子信息.
'U0' 分子的能量屬性(溫度為0K時(shí)),也是我們需要預(yù)測(cè)的值（分類(lèi)的種類(lèi)為13）
Tox21文件夾中包含13個(gè)文件，其中12個(gè)文件夾就是化合物的分類(lèi)
4.1.4 ArXiv
http://snap.stanford.edu/data/ca-AstroPh.html
Arxiv ASTRO-PH（天體物理學(xué)）協(xié)作網(wǎng)絡(luò)是來(lái)自電子版預(yù)影印平臺(tái)arXiv，涵蓋了提交到Astro Physics類(lèi)別的論文，包含了不同作者之間的科學(xué)合作信息。 如果作者i與作者j共同撰寫(xiě)了論文，則該圖包含從i到j(luò)的無(wú)向邊。 如果論文由k位作者共同撰寫(xiě)，則將在k個(gè)節(jié)點(diǎn)上生成完全連接的（子）圖。
數(shù)據(jù)涵蓋了1993年1月至2003年4月（124個(gè)月）期間的論文。 它始于arXiv成立后的幾個(gè)月內(nèi)，因此基本上代表了其ASTRO-PH部分的完整歷史。
ArXiv數(shù)據(jù)集的結(jié)點(diǎn)數(shù)為18772，邊條數(shù)為198110。
相關(guān)論文 J. Leskovec, J. Kleinberg and C. Faloutsos. Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1), 2007.
4.2deepwalk(多類(lèi)別預(yù)測(cè)任務(wù))
更多詳情參考：Paddle Graph Learning 圖學(xué)習(xí)之圖游走類(lèi)模型[系列四] https://aistudio.baidu.com/aistudio/projectdetail/5002782?contributionType=1
數(shù)據(jù)集為：BlogCatalog
Paddle2.0+是動(dòng)態(tài)圖了，為了進(jìn)一步簡(jiǎn)化使用，將GraphWrapper的概念去掉了，目前可以直接在Graph上進(jìn)行Send/Recv
4.3node2vec多類(lèi)別預(yù)測(cè)任務(wù))
更多詳情參考：Paddle Graph Learning 圖學(xué)習(xí)之圖游走類(lèi)模型[系列四] https://aistudio.baidu.com/aistudio/projectdetail/5002782?contributionType=1
4.4 結(jié)果對(duì)比
Dataset|model|Task|Metric|PGL Result| |--|--|--|--|--| BlogCatalog|deepwalk|multi-label classification|MacroF1|0.2269| BlogCatalog|node2vec|multi-label classification|MacroF1|0.23422|
這里使用默認(rèn)的參數(shù)，需要調(diào)優(yōu)一下，0.260最佳效果。. 更多詳情參考：Paddle Graph Learning 圖學(xué)習(xí)之圖游走類(lèi)模型[系列四] https://aistudio.baidu.com/aistudio/projectdetail/5002782?contributionType=1
