張文濤,苑 斌,張智鵬,崔 斌

1(高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(北京大學(xué)),北京 100871)

2(騰訊科技(北京)有限公司數(shù)據(jù)平臺部,北京 100193)

圖數(shù)據(jù)在現(xiàn)實(shí)生活中普遍存在,例如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電商網(wǎng)絡(luò)等等.隨著人工智能時(shí)代的到來,研究人員開始越來越多地使用機(jī)器學(xué)習(xí)技術(shù)挖掘圖上的信息[1?3],例如圖嵌入(graph embedding)技術(shù).另外,隨著數(shù)據(jù)來源的增加,例如電商、傳媒、社區(qū)、論壇等,人們所面臨的數(shù)據(jù)規(guī)模也在不斷增加.據(jù)統(tǒng)計(jì),谷歌與臉書的數(shù)據(jù)已經(jīng)達(dá)到PB 量級,每日數(shù)據(jù)增加量可達(dá)幾十到幾千TB.因此,在這種環(huán)境下,對大數(shù)據(jù)的處理與迭代能力顯得極為重要.

在這種大數(shù)據(jù)和機(jī)器學(xué)習(xí)的雙重背景下,大規(guī)模的圖嵌入算法也越來越受到人們的關(guān)注與重視.伴隨著人們對業(yè)務(wù)場景時(shí)間要求的緊迫性與互聯(lián)網(wǎng)提供服務(wù)的及時(shí)性,研究分布式圖嵌入算法的性能優(yōu)化也是當(dāng)下的趨勢.開發(fā)高效、大規(guī)模的分布式圖嵌入系統(tǒng)需要考慮通用性和高效性兩個(gè)方面.

? 通用性:目前,研究人員針對不同的場景開發(fā)了各種各樣的圖嵌入算法.在進(jìn)行圖嵌入算法的選擇時(shí),往往需要互相比較,互相借鑒,選擇最適用當(dāng)前場景的算法進(jìn)行使用.另外,在開發(fā)新算法的同時(shí),需要更多地考慮如何進(jìn)行改進(jìn)采樣的部分,以適應(yīng)更好的業(yè)務(wù)需求.針對以上需求,需要對現(xiàn)有的算法進(jìn)行總結(jié)與歸納,通過抽象,將采樣模塊暴露給用戶,并透明化后續(xù)訓(xùn)練模塊,需要支持后續(xù)算法更好的可擴(kuò)展性,需要讓算法的更新與維護(hù)變得更加方便快捷;

? 高效性:互聯(lián)網(wǎng)線上場景的需求需要算法的及時(shí)更新與快速迭代,往往對訓(xùn)練時(shí)間提出了更緊迫的要求,因此需要更好的分布式策略作為支撐[4,5].此外,工業(yè)界的集群數(shù)目眾多,機(jī)器數(shù)目多達(dá)幾千臺,在這種集群規(guī)模下,需要更好的可擴(kuò)展性.目前,在工業(yè)界針對圖嵌入算法有兩種主流的分布式策略:一種為圖簡易嵌入分布式策略,另一種為圖點(diǎn)積嵌入分布式策略.其中:圖點(diǎn)積嵌入分布式策略缺乏良好的可擴(kuò)展性(scalability),而圖簡易嵌入分布式策略具有性能瓶頸,需要進(jìn)一步地優(yōu)化方案.

為了解決以上兩個(gè)挑戰(zhàn),本文首先總結(jié)了目前基于隨機(jī)游走的算法和其他類型的一部分算法,包括深度游走算法(DeepWalk)[6]、大規(guī)模信息網(wǎng)絡(luò)嵌入算法(LINE)[7]、非對稱性臨近可擴(kuò)展圖嵌入算法(APP)[8]、圖節(jié)點(diǎn)向量算法(Node2Vec)[9]等.筆者發(fā)現(xiàn):利用點(diǎn)對描述進(jìn)行圖嵌入表示的輸入是一種良好的抽象,這種抽象能夠與目前的主流詞向量[10]與負(fù)采樣[11]模型完美兼容,并基于此提出了基于高性能高可復(fù)用性的分布式框架.該框架目前支持DeepWalk,LINE,APP 這3 種采樣算法,并且在對后續(xù)算法的更新上起到很好的支持作用.另外,筆者針對參數(shù)服務(wù)器上的分布式實(shí)現(xiàn)提供了性能優(yōu)化的策略,對已有的兩種在Angel[12,13]上實(shí)現(xiàn)的工業(yè)界級別的分布式策略進(jìn)行了詳細(xì)的分析(此外,高維度圖計(jì)算平臺還有AliGraph[14]).提出了一種模型劃分的策略,支持更好的可擴(kuò)展性.

本文的貢獻(xiàn)可以概括如下:對目前多種圖嵌入算法進(jìn)行了抽象,通過將采樣和訓(xùn)練兩部分解耦,提出了一套高可復(fù)用性的圖嵌入框架;通過對已有兩種分布式策略實(shí)現(xiàn)的分析,發(fā)現(xiàn)這兩種策略在擴(kuò)展性上表現(xiàn)不足,進(jìn)而提出了一種基于圖分割嵌入分布式策略;實(shí)現(xiàn)了一套分布式圖嵌入算法的原型系統(tǒng),并用充分的實(shí)驗(yàn)證明了圖分割嵌入分布式策略的高效性.

本文第1 節(jié)介紹相關(guān)工作.第2 節(jié)介紹高可復(fù)用性的圖嵌入框架.第3 節(jié)介紹圖分割嵌入式策略.第4 節(jié)介紹實(shí)驗(yàn)結(jié)果.最后,第5 節(jié)總結(jié)全文.

1 相關(guān)工作

深度游走算法是圖嵌入算法中較早提出來的基于隨機(jī)游走的算法,其借鑒了詞向量算法.首先選擇某一特定點(diǎn)為起始頂點(diǎn),通過深度優(yōu)先搜索或者寬度優(yōu)先搜索得到圖的序列;再將該序列送入詞向量算法進(jìn)行學(xué)習(xí),得到該點(diǎn)的表示向量.DeepWalk 算法解決了兩大問題:(1)隨機(jī)游走采樣節(jié)點(diǎn)的序列,形成圖節(jié)點(diǎn)序列;(2)利用Skip-gram[15]算法結(jié)合負(fù)采樣進(jìn)行圖節(jié)點(diǎn)向量的計(jì)算.

非對稱臨近可擴(kuò)展性圖嵌入(scalable graph embedding for asymmetric proximity)提出一種保留圖的非對稱結(jié)構(gòu)的基于隨機(jī)游走的圖嵌入方法,并通過理論推導(dǎo)證明了該嵌入式方法保留了根網(wǎng)絡(luò)排名(rooted pagerank)值,DeepWalk 算法和節(jié)點(diǎn)向量算法都無法保留圖的非對稱性結(jié)構(gòu)(有向圖和無向圖).

LINE 是圖嵌入算法中較常用的算法,其適用任意類型的信息網(wǎng)絡(luò)、無向圖、有向圖、無權(quán)圖、有權(quán)圖等,優(yōu)化了目標(biāo)函數(shù),使得其能夠保留局部和全局網(wǎng)絡(luò)結(jié)構(gòu).LINE 還提出了邊緣采樣算法,解決了經(jīng)典隨機(jī)梯度下降的局限性,提高了算法的效率和有效性.

分布式的圖嵌入算法利用參數(shù)服務(wù)器[16?19]進(jìn)行實(shí)現(xiàn),目前在工業(yè)界的應(yīng)用有兩種:一種為圖簡易嵌入分布式策略,另一種為圖點(diǎn)積嵌入分布式策略.兩種策略將在第3 節(jié)詳細(xì)說明.

2 高可復(fù)用的圖嵌入框架

2.1 已有圖嵌入算法分析

圖嵌入算法很多,例如DeepWalk、LINE、APP、節(jié)點(diǎn)向量算法等.其原始訓(xùn)練流程如圖1 所示,以3 種算法為例,其采樣算法模塊與后續(xù)訓(xùn)練模塊相互耦合,從而導(dǎo)致代碼復(fù)用性差,重復(fù)度高.

Fig.1 The original training process圖1 原始訓(xùn)練流程

DeepWalk 基于圖上的隨機(jī)游走進(jìn)行采樣,生成一系列的序列信息,利用采樣得到的序列信息進(jìn)行圖嵌入算法的訓(xùn)練.LINE 采用的采樣算法與DeepWalk 截然不同,其收集邊信息,利用每條邊直接生成點(diǎn)對信息,利用邊信息進(jìn)行訓(xùn)練.而APP 的計(jì)算過程來源于網(wǎng)頁排名值,在網(wǎng)頁排名值中會設(shè)定一個(gè)停留率(stoprate),通過制造隨機(jī)數(shù)與停留率進(jìn)行比較,來決定當(dāng)前頁面是否停留,收集起始點(diǎn)與終點(diǎn)從而生成點(diǎn)對信息.

得到點(diǎn)對信息后,進(jìn)入模型訓(xùn)練的流程.在訓(xùn)練時(shí),采用對損失函數(shù)進(jìn)行求導(dǎo).通用的損失函數(shù)結(jié)合負(fù)采樣算法,通過隨機(jī)梯度下降法對模型進(jìn)行更新,其模型主要包括兩個(gè)部分:第一部分為圖節(jié)點(diǎn)向量,第二部分為負(fù)采樣節(jié)點(diǎn)向量.

我們發(fā)現(xiàn):在上述這3 個(gè)算法過程中,均能夠生成點(diǎn)對的信息,接下來可以統(tǒng)一利用點(diǎn)對的信息進(jìn)行計(jì)算.因此,可以將基于詞向量與負(fù)采樣模型的圖嵌入算法歸納出先采樣后訓(xùn)練的模式,從而將采樣邏輯協(xié)同訓(xùn)練邏輯相互獨(dú)立,對訓(xùn)練的邏輯進(jìn)行單獨(dú)的優(yōu)化,形成單獨(dú)的模塊.一般新算法的提出往往是在采樣的模塊進(jìn)行更改,優(yōu)化的模塊對于用戶是透明的,用戶只需要修改采樣的代碼即可完成新算法的修改.

2.2 高可復(fù)用的分布式圖嵌入框架

基于上文中的分析,筆者構(gòu)建了一種基于采樣的框架,將各種圖嵌入的算法進(jìn)行統(tǒng)一,提出一個(gè)高可復(fù)用的分布式圖嵌入框架.

如圖2 所示,算法的流程是:首先輸入為原始圖,以邊為單位,通過處理原始圖,利用不同算法進(jìn)行采樣,將這些采樣信息處理為Skip-gram 能夠接受的格式,即點(diǎn)對信息.在Skip-gram 與負(fù)采樣訓(xùn)練過程中,其輸入是處理完畢的點(diǎn)對信息,將這些點(diǎn)對分成批次進(jìn)行訓(xùn)練,每一次訓(xùn)練均通過隨機(jī)梯度下降算法收斂得到最后模型.結(jié)合圖3 介紹高可用的分布式圖嵌入框架.

Fig.2 The training process of single-machine圖2 單機(jī)訓(xùn)練流程

Fig.3 The distributed training framework圖3 分布式訓(xùn)練框架

分布式的訓(xùn)練流程主要分為兩個(gè)部分:第一部分為采樣流程,第二部分為訓(xùn)練部分.采樣流程和訓(xùn)練流程均與單機(jī)不同,接下來介紹這兩個(gè)部分.

? 采樣流程:數(shù)據(jù)輸入為一張圖,在圖上會運(yùn)行一些采樣算法,通過分布式的機(jī)制進(jìn)行采樣.實(shí)際原理是將其轉(zhuǎn)化為Spark[20]上的RDD 算子運(yùn)算,通過將數(shù)據(jù)分發(fā)給不同的運(yùn)算節(jié)點(diǎn)來處理得到結(jié)果,減少采樣時(shí)間;

? 訓(xùn)練流程:在分布式訓(xùn)練模塊中,輸入為點(diǎn)對信息,不同策略對點(diǎn)對信息進(jìn)行分組,放置在不同計(jì)算節(jié)點(diǎn)上.計(jì)算節(jié)點(diǎn)拿取到點(diǎn)對信息后,會分批次進(jìn)行分布式訓(xùn)練.通過在參數(shù)服務(wù)器上放置模型位置的不同,可將分布式策略分為兩種:一種在參數(shù)服務(wù)器上存儲所有模型,另一種在參數(shù)服務(wù)器與計(jì)算節(jié)點(diǎn)同時(shí)存儲模型.在參數(shù)服務(wù)器上存儲所有模型有兩種:圖簡易嵌入分布式策略和圖點(diǎn)積嵌入分布式策略,這兩種策略是目前業(yè)界常見的實(shí)現(xiàn)策略.

以深度游走為例,其采用深度優(yōu)先遍歷的方式,從某個(gè)節(jié)點(diǎn)出發(fā),通過多次深度優(yōu)先游走記錄下節(jié)點(diǎn)遍歷的路徑,從而將路徑轉(zhuǎn)化為一條序列.這種做法稱之為采樣.采樣得到的序列再經(jīng)過SKIP-GRAM 的格式變化之后,可以處理為點(diǎn)對信息.在輸入采樣算法具有相似的目標(biāo)函數(shù)的作用下,分布式訓(xùn)練可以獨(dú)立于采樣算法本身,性能優(yōu)化交給分布式訓(xùn)練的模塊,訓(xùn)練模塊只需顧忌自身的訓(xùn)練性能以及收斂精度即可.完成最終的模型訓(xùn)練,與原先的算法得到同樣好的收斂結(jié)果.

最終的框架具有良好的可擴(kuò)展性,解除了算法采樣與訓(xùn)練之間的耦合關(guān)系,使得該框架成為一種高度內(nèi)聚的實(shí)現(xiàn).當(dāng)有新的算法加入時(shí),只需要將其采樣的部分改寫為框架所支持的代碼即可.大多數(shù)的算法往往會在采樣上做出新的調(diào)整,而訓(xùn)練的損失函數(shù)變動(dòng)不大.當(dāng)目標(biāo)函數(shù)與框架不同時(shí),只需要對分布式的訓(xùn)練模塊進(jìn)行簡單的處理,通過繼承或者接口注入的方式改寫目標(biāo)函數(shù)相對應(yīng)的類即可,用戶無需對新的算法進(jìn)行大量的調(diào)參,也無需對其進(jìn)行分布式上網(wǎng)絡(luò)通信的優(yōu)化(如圖4 所示).

Fig.4 The distributed execution process of the simple graph embedding strategy圖4 圖簡易嵌入分布式策略的執(zhí)行流程

3 基于高性能的分布式解決方案

3.1 已有的分布式策略分析

目前,工業(yè)界已有兩種很常見的分布式實(shí)現(xiàn)策略,它們都是在參數(shù)服務(wù)器上存儲所有模型.根據(jù)在計(jì)算節(jié)點(diǎn)和參數(shù)服務(wù)器上點(diǎn)積的不同運(yùn)算方式,可以分為圖簡易嵌入分布式策略與圖點(diǎn)積嵌入分布式策略:圖點(diǎn)積嵌入分布式策略缺乏良好的可擴(kuò)展性;而圖簡易嵌入分布式策略具有性能瓶,需要進(jìn)一步的優(yōu)化方案.本節(jié)簡要介紹這兩種常用的分布式策略.

3.1.1 圖簡易嵌入分布式策略

? 數(shù)據(jù)與模型存儲

圖簡易嵌入分布式策略將點(diǎn)對數(shù)據(jù)獨(dú)立劃分在分布式文件系統(tǒng)[21]上,利用參數(shù)服務(wù)器進(jìn)行節(jié)點(diǎn)向量與負(fù)采樣向量模型的存儲.每個(gè)點(diǎn)的嵌入信息完全存放在一臺機(jī)器上,不存在單點(diǎn)嵌入的切割,這里與圖點(diǎn)積嵌入分布式策略加以區(qū)分.圖簡易嵌入分布式策略與圖點(diǎn)積嵌入分布式策略的執(zhí)行流程分別如圖4 和圖5 所示.

? 訓(xùn)練流程

步驟1.圖簡易嵌入分布式策略進(jìn)行本地的數(shù)據(jù)讀取,得到需要參與計(jì)算的模型索引,模型索引即為每個(gè)圖頂點(diǎn)的索引值.預(yù)先對模型索引進(jìn)行挑選,選取需要用到嵌入信息的頂點(diǎn).在第2 步中,拉取只需拉取需要的模型向量;

步驟2.根據(jù)這些模型索引,從參數(shù)服務(wù)器上拉取需要的模型.只有部分模型需要參與一個(gè)批次的計(jì)算,參與計(jì)算的模型索引在步驟1 中計(jì)算完畢,需要拉取的模型參數(shù)為節(jié)點(diǎn)向量模型與負(fù)采樣向量模型的部分模型,通信開銷為O(2mD),m為每一個(gè)批次下參與計(jì)算的獨(dú)立節(jié)點(diǎn)個(gè)數(shù)(去除重復(fù)節(jié)點(diǎn)之后的結(jié)果);

步驟3.圖簡易嵌入分布式策略利用Skip-gram 中的損失函數(shù)進(jìn)行求導(dǎo),進(jìn)行梯度的計(jì)算,這里需要涉及到節(jié)點(diǎn)向量和負(fù)采樣向量兩個(gè)模型,采用的算法統(tǒng)一為負(fù)采樣.

步驟4.計(jì)算完畢之后,將梯度傳遞回參數(shù)服務(wù)器.因?yàn)楣?jié)點(diǎn)向量和負(fù)采樣向量均需要傳遞D維度的參數(shù),因此這里的通信開銷是O(2mD).模型在參數(shù)服務(wù)器的更新采用的是累加的模式.

總通信開銷為拉取與推送這兩個(gè)操作帶來的模型傳輸和梯度傳輸,一個(gè)批次下需要的通信量為O(4mD).

Fig.5 The distributed execution process of the dotted graph embedding strategy圖5 圖點(diǎn)積嵌入分布式策略執(zhí)行流程

Fig.6 The distributed execution process of the partitioned graph embedding strategy圖6 圖分割嵌入分布式策略分布式訓(xùn)練執(zhí)行流程

3.1.2 圖點(diǎn)積嵌入分布式策略

? 數(shù)據(jù)與模型存儲

數(shù)據(jù)劃分同圖簡易策略,模型分為節(jié)點(diǎn)向量與負(fù)采樣向量.一個(gè)節(jié)點(diǎn)向量的不同列存放在不同的機(jī)器上,與圖簡易嵌入分布式策略不同.

? 訓(xùn)練流程

步驟1.計(jì)算節(jié)點(diǎn)進(jìn)行本地的數(shù)據(jù)讀取,得到需要參與計(jì)算的模型索引;

步驟2.計(jì)算節(jié)點(diǎn)根據(jù)獲取到的模型索引,從參數(shù)服務(wù)器上拉取需要的模型.需要拉取的結(jié)果為點(diǎn)積計(jì)算之后的結(jié)果,點(diǎn)積計(jì)算在參數(shù)服務(wù)器上完成,無需進(jìn)行通信,只需將點(diǎn)積計(jì)算結(jié)果傳遞給計(jì)算節(jié)點(diǎn).傳輸?shù)木S度也從D維變?yōu)榱? 維度.因此,通信開銷為O(2m);

步驟3.計(jì)算節(jié)點(diǎn)進(jìn)行梯度計(jì)算,計(jì)算一維梯度,將一維梯度推送回參數(shù)服務(wù)器,參數(shù)服務(wù)器可利用一維梯度更新每個(gè)維度;

步驟4.計(jì)算完畢后,將一維梯度傳遞回參數(shù)服務(wù)器,節(jié)點(diǎn)向量和負(fù)采樣向量均需要傳遞1 維度參數(shù),參數(shù)服務(wù)器將會利用一維梯度去更新其他維度梯度,更新結(jié)果同原來一致,故通信開銷是O(2m).

總體通信開銷為拉取與推送兩個(gè)操作帶來模型傳輸和梯度傳輸之和,一個(gè)批次下,通信量為O(4m).

3.2 圖分割嵌入分布式策略

? 數(shù)據(jù)存儲與模型存儲

節(jié)點(diǎn)向量模型按照節(jié)點(diǎn)的id 分布在計(jì)算節(jié)點(diǎn)的每臺機(jī)器上,在參數(shù)服務(wù)器上存儲全部的負(fù)采樣向量模型,同一節(jié)點(diǎn)向量的不同維度存放在相同的機(jī)器上,它的訓(xùn)練執(zhí)行流程如圖6 所示.

? 訓(xùn)練流程

步驟1.每臺機(jī)器進(jìn)行本地的數(shù)據(jù)讀取,得到需要參與計(jì)算的模型行索引,數(shù)據(jù)讀取按照圖上節(jié)點(diǎn)id 進(jìn)行哈希劃分,分散在每臺機(jī)器上;

步驟2.需要拉取的模型為負(fù)采樣向量的部分模型,由于圖節(jié)點(diǎn)向量在每個(gè)計(jì)算節(jié)點(diǎn)本地,通信開銷為O(mD);

步驟3.每臺機(jī)器需要進(jìn)行梯度的計(jì)算.節(jié)點(diǎn)向量的模型放置在計(jì)算節(jié)點(diǎn)上,數(shù)據(jù)為點(diǎn)對信息,根據(jù)節(jié)點(diǎn)哈希到不同機(jī)器上,節(jié)點(diǎn)向量模型直接在本地更新;

步驟4.計(jì)算完畢之后,將負(fù)采樣向量模型的梯度傳遞回參數(shù)服務(wù)器,并且在本地更新相應(yīng)節(jié)點(diǎn)向量模型.因?yàn)槊總€(gè)負(fù)采樣向量模型節(jié)點(diǎn)需要傳遞D維度的參數(shù),通信開銷為O(mD).

總體的通信開銷為拉取與推送這兩個(gè)操作帶來的模型傳輸和梯度傳輸之和,一個(gè)批次下需要的通信量為O(2mD),對比圖簡易嵌入分布式策略,減少了一半通信量.

4 實(shí)驗(yàn)與分析

4.1 圖分割嵌入分布式策略

? 數(shù)據(jù)集

我們采用 3 個(gè)公開的數(shù)據(jù)集(下載地址:https://snap.stanford.edu/data/),即維基百科(WIKI)、油管(YOUTUBE)、現(xiàn)場博客(LIVEJOURNAL)數(shù)據(jù)集.數(shù)據(jù)集的基本信息概括在表1 中.

Table 1 Dataset size表1 數(shù)據(jù)集規(guī)模

? 實(shí)驗(yàn)環(huán)境

目前的實(shí)驗(yàn)在一個(gè)實(shí)驗(yàn)室集群下進(jìn)行,該集群包含了8 臺物理機(jī),每個(gè)機(jī)器包含2 個(gè)CPU,32GB 內(nèi)存,機(jī)器之間的網(wǎng)絡(luò)為1Gb/s.筆者在開源系統(tǒng)Spark 上統(tǒng)一實(shí)現(xiàn)了3 種圖嵌入分布式策略.

? 實(shí)驗(yàn)設(shè)計(jì)

我們從以下3 個(gè)角度設(shè)計(jì)實(shí)驗(yàn):(1)選用3 種常見的圖嵌入算法進(jìn)行實(shí)驗(yàn),以證明算法的通用性;(2)采用常見的圖嵌入算法對3 種不同分布式嵌入策略在不同數(shù)據(jù)集上進(jìn)行對比,以展示圖分割嵌入式策略的高效性;(3)對3 種圖嵌入分布式收斂的情況分析,以證明各種實(shí)現(xiàn)策略均不影響算法的正常收斂.在所有實(shí)驗(yàn)中,采用的圖節(jié)點(diǎn)嵌入向量維度均為128 維,均使用負(fù)采樣算法進(jìn)行訓(xùn)練.

4.2 各分布式策略的性能與可擴(kuò)展性分析

圖點(diǎn)積嵌入分布式策略在較少計(jì)算節(jié)點(diǎn)的數(shù)目下具有性能優(yōu)勢,在2 個(gè)或者4 個(gè)計(jì)算節(jié)點(diǎn)時(shí),其訓(xùn)練的時(shí)間開銷往往低于圖簡易嵌入分布式策略和圖分割嵌入分布式策略.隨著計(jì)算節(jié)點(diǎn)數(shù)目的增加,圖點(diǎn)積嵌入分布式策略的性能開始下降.下降原因來自計(jì)算節(jié)點(diǎn)數(shù)目增加后,點(diǎn)積運(yùn)算帶來的提升有限,并且點(diǎn)積運(yùn)算所需要的加法次數(shù)變多.此外,機(jī)器數(shù)目增多引入額外協(xié)調(diào)開銷,一臺機(jī)器需要等待另外的機(jī)器點(diǎn)積運(yùn)算完畢才能拿到結(jié)果,因此拿到結(jié)果最終取決于最慢的機(jī)器.因此,其核心運(yùn)算優(yōu)勢減少,通信開銷增加,最終導(dǎo)致性能大幅下降(如圖7～圖15 所示).

Fig.7 WIKI-LINE圖7 維基百科-大規(guī)模信息網(wǎng)絡(luò)嵌入

Fig.8 WIKI-APP圖8 維基百科-非對稱臨近可擴(kuò)展性圖嵌入

Fig.9 WIKI-DeepWalk圖9 維基百科-深度游走

Fig.10 YOUTUBE-LINE圖10 油管-大規(guī)模信息網(wǎng)絡(luò)嵌入

Fig.11 YOUTUBE-APP圖11 油管-非對稱臨近可擴(kuò)展性圖嵌入

Fig.12 YOUTUBE-DeepWalk圖12 油管-深度游走

Fig.13 LIVEJOURNAL-LINE圖13 現(xiàn)場博客-大規(guī)模信息網(wǎng)絡(luò)嵌入

Fig.14 LIVEJOURNAL-APP圖14 現(xiàn)場博客-非對稱臨近可擴(kuò)展性圖嵌入

Fig.15 LIVEJOURNAL-DeepWalk圖15 現(xiàn)場博客-深度游走

對于圖簡易嵌入分布式策略而言,當(dāng)計(jì)算節(jié)點(diǎn)和模型切片數(shù)目增加,其點(diǎn)積操作并不與模型切片數(shù)目相關(guān),其具有較好的加速比;另一方面,每一臺機(jī)器的運(yùn)算均可以獨(dú)立進(jìn)行,無需和其他機(jī)器同步,因此機(jī)器的協(xié)調(diào)時(shí)間大大減少.雖然機(jī)器數(shù)目增加會帶來一定的額外時(shí)間開銷,但增大量遠(yuǎn)不如圖點(diǎn)積嵌入分布式策略,其可擴(kuò)展性較好,性能總體而言不如圖分割嵌入分布式策略.

對于圖分割嵌入分布式策略,其具有不錯(cuò)的性能優(yōu)勢.當(dāng)計(jì)算節(jié)點(diǎn)和模型切片數(shù)目增加時(shí),其計(jì)算模式同圖簡易嵌入分布式策略近似;但網(wǎng)絡(luò)開銷比其要少,其節(jié)點(diǎn)向量矩陣的更新與拉取在每臺機(jī)器本地完成,理論上將節(jié)省一半的網(wǎng)絡(luò)通信.同樣,與圖點(diǎn)積嵌入分布式策略不同,其額外開銷與機(jī)器數(shù)目影響不大,內(nèi)積運(yùn)算單獨(dú)在每臺機(jī)器上完成,并未累加.因此,其性能具有良好的可擴(kuò)展性,并且其往往在多個(gè)計(jì)算節(jié)點(diǎn)的情況下,性能比圖點(diǎn)積嵌入分布式策略要好.由于其拉取操作的通信量比圖簡易嵌入分布式策略要少,其實(shí)驗(yàn)表現(xiàn)比圖簡易嵌入分布式策略要好.而對于少許性能震蕩的情況而言,可能出于數(shù)據(jù)劃分的傾斜問題,導(dǎo)致每臺機(jī)器分配的算力不均衡,最終導(dǎo)致個(gè)別結(jié)果不如圖簡易嵌入分布式策略與圖點(diǎn)積嵌入分布式策略.總體而言,對比圖簡易嵌入分布式策略與圖點(diǎn)積嵌入分布式策略的分布式訓(xùn)練策略,圖分割嵌入分布式策略在三者數(shù)據(jù)集上體現(xiàn)出了極好的性能優(yōu)勢,并且表現(xiàn)出了優(yōu)異的可擴(kuò)展性.

4.3 各分布式策略收斂結(jié)果的對比

本文對計(jì)算節(jié)點(diǎn)、圖點(diǎn)積嵌入分布式策略、圖分割嵌入分布式策略這3 種采樣策略均進(jìn)行了LOSS 收斂曲線的實(shí)驗(yàn).實(shí)驗(yàn)中固定嵌入的維度為128,并且采用20 輪次的迭代.出于不同分布式策略的學(xué)習(xí)率與模型適應(yīng)程度不同,并且不同分布式策略具有不同的計(jì)算模式,梯度更新順序與模式不完全一致.因此,為了讓每個(gè)算法取得更好的收斂結(jié)果,本文對于不同的算法采用了不同的學(xué)習(xí)率初始值.

本文以現(xiàn)場博客數(shù)據(jù)集為例,分別繪制了非對稱臨近可擴(kuò)展性圖嵌入、深度游走、大規(guī)模信息網(wǎng)絡(luò)嵌入這3 種采樣策略對應(yīng)的2,4,8,16 個(gè)計(jì)算節(jié)點(diǎn)和模型切片數(shù)目的LOSS 收斂曲線圖.接下來將通過圖表對結(jié)果做進(jìn)一步的分析.

APP 基于根網(wǎng)頁排名,根據(jù)停留率(stoprate)對圖節(jié)點(diǎn)序列進(jìn)行采樣,其中,圖節(jié)點(diǎn)序列采用隨機(jī)游走的方式得到,包括深度優(yōu)先遍歷或?qū)挾葍?yōu)先遍歷.因此,在輸入序列數(shù)據(jù)規(guī)模相同的情況下,其采樣點(diǎn)對會遠(yuǎn)遠(yuǎn)少于DeepWalk 的點(diǎn)對.由于圖嵌入為無監(jiān)督學(xué)習(xí),其LOSS 損失很大程度上取決于輸入數(shù)據(jù)規(guī)模:當(dāng)數(shù)據(jù)規(guī)模擴(kuò)大后,其總體數(shù)據(jù)復(fù)雜程度會有更大機(jī)率擴(kuò)大;當(dāng)輸入數(shù)據(jù)規(guī)模減少時(shí),其數(shù)據(jù)復(fù)雜程度會減少.數(shù)據(jù)復(fù)雜程度影響LOSS 損失函數(shù):當(dāng)LOSS 損失很大時(shí),表明模型對數(shù)據(jù)的認(rèn)知較弱;當(dāng)LOSS 損失較小時(shí),表明此時(shí)模型對數(shù)據(jù)的認(rèn)知較強(qiáng).當(dāng)數(shù)據(jù)復(fù)雜程度較小時(shí),模型會很快收斂.因此,由圖中可以觀察得出:對于非對稱臨近可擴(kuò)展性圖嵌入采樣算法,圖點(diǎn)積嵌入分布式策略、圖簡易嵌入分布式策略、圖分割嵌入分布式策略三者均會穩(wěn)定收斂.以圖16(a)為例:當(dāng)采用兩個(gè)計(jì)算節(jié)點(diǎn)時(shí),3 種分布式策略均在第一輪迭代后很快收斂,并在后續(xù)的迭代中緩慢收斂.圖16(b)～圖16(d)分別表現(xiàn)了采用更多計(jì)算節(jié)點(diǎn)時(shí),LOSS 的收斂情況.從4 張圖中可以發(fā)現(xiàn):擴(kuò)大計(jì)算節(jié)點(diǎn)個(gè)數(shù)后,圖點(diǎn)積嵌入分布式策略、圖簡易嵌入分布式策略、圖分割嵌入分布式策略三者均會穩(wěn)定收斂.

深度游走采樣算法是最初提出用以建模圖節(jié)點(diǎn)向量,流程為從某一節(jié)點(diǎn)出發(fā),根據(jù)深度優(yōu)先遍歷結(jié)果或?qū)挾葍?yōu)先遍歷統(tǒng)計(jì)節(jié)點(diǎn)鄰域序列,再根據(jù)節(jié)點(diǎn)鄰域序列學(xué)習(xí)得到模型.深度游走采樣對模型的刻畫較為粗糙,數(shù)據(jù)復(fù)雜程度較非對稱臨近可擴(kuò)展性圖嵌入更為復(fù)雜.數(shù)據(jù)規(guī)模比非對稱臨近可擴(kuò)展性圖嵌入大,模型學(xué)習(xí)難度較大.由圖17(a)可以看出:當(dāng)采用2 個(gè)計(jì)算節(jié)點(diǎn)時(shí),模型在第一輪迭代損失會下降,但下降程度并不明顯,隨后的幾輪迭代模型進(jìn)入緩慢收斂期,出于模型的復(fù)雜程度較大,3 類算法對其學(xué)習(xí)程度略微陡峭,收斂速度整體不如非對稱臨近可擴(kuò)展性圖嵌入.其中,圖點(diǎn)積嵌入分布式策略在第一輪次的收斂值相比其他兩者稍顯優(yōu)勢,在后來幾輪迭代中進(jìn)入緩慢收斂期,這一收斂結(jié)果與學(xué)習(xí)率的設(shè)置也有一定關(guān)系.總體三者最終收斂結(jié)果相同,趨于一致,表明3 類算法均可學(xué)習(xí)得到不錯(cuò)的模型結(jié)果,取得優(yōu)異的收斂值.

通過觀察發(fā)現(xiàn):在采用大規(guī)模信息網(wǎng)絡(luò)嵌入采樣算法時(shí)(如圖18 所示),圖簡易嵌入分布式策略與圖分割嵌入分布式策略的LOSS 曲線較為一致.這一現(xiàn)象是由于圖簡易嵌入分布式策略與圖分割嵌入分布式策略具有較為近似的計(jì)算模式,其梯度更新順序較為接近.兩者不同之處僅僅在于模型存儲位置以及其存儲帶來的梯度傳輸差異,例如:在圖分割嵌入分布式策略中,其梯度將有一部分在本地更新;而圖簡易嵌入分布式策略則全于參數(shù)服務(wù)器中更新.兩者還具有相應(yīng)的數(shù)據(jù)劃分引入的差異性:在圖簡易嵌入分布式策略中,其數(shù)據(jù)劃分為隨機(jī)進(jìn)行;而圖分割嵌入分布式策略則是預(yù)先進(jìn)行劃分,不含有梯度寫回的誤差.最終,3 種分布式策略在大規(guī)模信息網(wǎng)絡(luò)嵌入采樣算法中達(dá)到同樣的收斂結(jié)果.結(jié)合上述圖表與分析,3 種分布式策略的收斂結(jié)果差異不大,有些算法在收斂中間略有震蕩.這一結(jié)果可能與不同機(jī)器的數(shù)據(jù)分布不同,以及分布式策略對數(shù)據(jù)的依賴性、數(shù)據(jù)打亂的結(jié)果以及初始學(xué)習(xí)率的設(shè)置有關(guān).最終,在3 種圖嵌入采樣算法中,3 類分布式訓(xùn)練策略得到的損失(LOSS)收斂結(jié)果均為一致,表明三者策略對于數(shù)據(jù)的學(xué)習(xí)程度較為接近.

Fig.16 The LOSS curve of APP圖16 非對稱臨近可擴(kuò)展性圖嵌入算法LOSS 曲線

Fig.17 The LOSS curve of DeepWalk圖17 深度游走LOSS 曲線

Fig.18 The LOSS curve of LINE圖18 大規(guī)模信息網(wǎng)絡(luò)嵌入LOSS 曲線

4.4 各分布式策略收斂速度的對比

通過多次實(shí)驗(yàn)發(fā)現(xiàn):機(jī)器學(xué)習(xí)模型的收斂速度與其初始的學(xué)習(xí)率具有較大的關(guān)聯(lián),并且與選擇的優(yōu)化器有直接關(guān)系.其中,優(yōu)化器可以分為有動(dòng)量的與隨機(jī)梯度下降法,出于對分布式多機(jī)器收斂影響的考慮,在此選擇為最基礎(chǔ)的隨機(jī)梯度下降法.若初始的學(xué)習(xí)率較大,那么模型將會很快地進(jìn)入較優(yōu)值,并且LOSS 收斂曲線會隨著迭代輪次數(shù)目的增加時(shí)而震蕩.如果初始的學(xué)習(xí)率較小,模型收斂到達(dá)最優(yōu)解的可能性會增加,通常情況下,LOSS 收斂曲線會在最后迭代次數(shù)下輕微震蕩.不同的分布式訓(xùn)練策略往往有著不同的數(shù)據(jù)依賴,模型向量之間的依賴,每一種訓(xùn)練策略,其并行運(yùn)算的流程與常見的串行算法并不一致,而基于HOGWILD[22]理論,每個(gè)機(jī)器之間可以無序的寫回梯度,使得最終結(jié)果收斂.

5 總結(jié)

本文首先通過對多種現(xiàn)有的圖嵌入方法進(jìn)行調(diào)研,提出了一個(gè)高可用的分布式訓(xùn)練框架.該框架通過將采樣、訓(xùn)練過程解耦,從而能夠表達(dá)多種圖嵌入算法.用戶可以只關(guān)心采樣的流程或只關(guān)心訓(xùn)練的流程,從而使得其中的算法具有高度的可復(fù)用性.另外,筆者針對業(yè)界現(xiàn)有的分布式圖嵌入策略進(jìn)行分析,發(fā)現(xiàn)了這些算法在訓(xùn)練性能以及擴(kuò)展性上的不足,進(jìn)而提出了一種圖分割嵌入分布式策略.筆者實(shí)現(xiàn)了一個(gè)原型系統(tǒng),并通過充分的實(shí)驗(yàn)分析了3 種分布式策略.筆者發(fā)現(xiàn):機(jī)器數(shù)目增加后,圖點(diǎn)積嵌入分布式策略的可擴(kuò)展性變差,在性能對比上處于劣勢地位;而圖簡易嵌入分布式策略和圖分割嵌入分布式策略具有較為不錯(cuò)的可擴(kuò)展性,本文提出的圖分割嵌入分布式策略具有更好的性能優(yōu)勢.