圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)綜述

李 涵 嚴(yán)明玉 呂征陽 李文明 葉笑春 范東睿 唐志敏

1(計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所) 北京 100190)

2(中國科學(xué)院大學(xué) 北京 100049)

(lihan-ams＠ict.ac.cn)

人工智能時(shí)代,包括卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural networks,CNNs)、循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural networks,RNNs)等在內(nèi)的機(jī)器學(xué)習(xí)應(yīng)用為社會與生活的智能化做出了革新性的巨大貢獻(xiàn).然而傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)只能處理來自歐幾里得空間(Euclidean space)的數(shù)據(jù)[1],該類分布規(guī)整且結(jié)構(gòu)固定的數(shù)據(jù)無法靈活地表示事物間的復(fù)雜關(guān)系.現(xiàn)實(shí)生活中,越來越多的場景采用圖作為表征數(shù)據(jù)屬性與關(guān)系的結(jié)構(gòu).非歐幾里得空間中的圖結(jié)構(gòu)理論上能夠表征世間萬物的互聯(lián)關(guān)系(如社交網(wǎng)絡(luò)、路線圖、基因結(jié)構(gòu)等)[2],具有極為豐富和強(qiáng)大的數(shù)據(jù)表達(dá)能力.圖計(jì)算是一種能夠?qū)D進(jìn)行處理,深入挖掘圖數(shù)據(jù)內(nèi)潛藏信息的重要應(yīng)用,但其不具備對圖數(shù)據(jù)進(jìn)行學(xué)習(xí)的能力.

受到傳統(tǒng)神經(jīng)網(wǎng)絡(luò)與圖計(jì)算應(yīng)用的雙重啟發(fā),圖神經(jīng)網(wǎng)絡(luò)(graph neural networks,GNNs)應(yīng)運(yùn)而生.圖神經(jīng)網(wǎng)絡(luò)使得機(jī)器學(xué)習(xí)能夠應(yīng)用于非歐幾里得空間的圖結(jié)構(gòu)中,具備對圖進(jìn)行學(xué)習(xí)的能力.目前圖神經(jīng)網(wǎng)絡(luò)已經(jīng)廣泛應(yīng)用到節(jié)點(diǎn)分類[3]、風(fēng)控評估[4]、推薦系統(tǒng)[5]等眾多場景中.并且圖神經(jīng)網(wǎng)絡(luò)被認(rèn)為是推動人工智能從“感知智能”階段邁入“認(rèn)知智能”階段的核心要素[6-8],具有極高的研究和應(yīng)用價(jià)值.

圖神經(jīng)網(wǎng)絡(luò)的執(zhí)行過程混合了傳統(tǒng)圖計(jì)算和神經(jīng)網(wǎng)絡(luò)應(yīng)用的不同特點(diǎn).圖神經(jīng)網(wǎng)絡(luò)通常包含圖聚合和圖更新2個(gè)主要階段.1)圖聚合階段的執(zhí)行行為與傳統(tǒng)圖計(jì)算相似,需要對鄰居分布高度不規(guī)則的圖進(jìn)行遍歷,為每個(gè)節(jié)點(diǎn)進(jìn)行鄰居信息的聚合,因此這一階段具有極為不規(guī)則的計(jì)算和訪存行為特點(diǎn).2)圖更新階段的執(zhí)行行為與傳統(tǒng)神經(jīng)網(wǎng)絡(luò)相似,通過多層感知機(jī)(multi-layer perceptrons,MLPs)等方式來進(jìn)行節(jié)點(diǎn)特征向量的變換與更新,這一階段具有規(guī)則的計(jì)算和訪存行為特點(diǎn).

圖神經(jīng)網(wǎng)絡(luò)的混合執(zhí)行行為給應(yīng)用的加速帶來極大挑戰(zhàn),規(guī)則與不規(guī)則的計(jì)算與訪存模式共存使得傳統(tǒng)處理器結(jié)構(gòu)設(shè)計(jì)無法對其進(jìn)行高效處理.圖聚合階段高度不規(guī)則的執(zhí)行行為使得CPU無法從其多層次緩存結(jié)構(gòu)與數(shù)據(jù)預(yù)取機(jī)制中獲益.主要面向密集規(guī)則型計(jì)算的GPU平臺也因圖聚合階段圖遍歷的不規(guī)則性、圖更新階段參數(shù)共享導(dǎo)致的昂貴數(shù)據(jù)復(fù)制和線程同步開銷等因素?zé)o法高效執(zhí)行圖神經(jīng)網(wǎng)絡(luò)[9].而已有的面向傳統(tǒng)圖計(jì)算應(yīng)用和神經(jīng)網(wǎng)絡(luò)應(yīng)用的專用加速結(jié)構(gòu)均只關(guān)注于單類應(yīng)用,無法滿足具有混合應(yīng)用特征的圖神經(jīng)網(wǎng)絡(luò)加速需求.因此為圖神經(jīng)網(wǎng)絡(luò)專門設(shè)計(jì)相應(yīng)的加速結(jié)構(gòu)勢在必行.

自2020年全球首款面向圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的專用加速結(jié)構(gòu)HyGCN[9]發(fā)表后,短時(shí)間內(nèi)學(xué)術(shù)界已在該領(lǐng)域有多篇不同的硬件加速結(jié)構(gòu)成果產(chǎn)出.為使讀者和相關(guān)領(lǐng)域研究人員能夠清晰地了解圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)的現(xiàn)有工作,本文首先對圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)知識、常見算法、應(yīng)用場景、編程模型以及主流的基于通用平臺的框架與擴(kuò)展庫等進(jìn)行介紹.然后以圖神經(jīng)網(wǎng)絡(luò)執(zhí)行行為帶來的加速結(jié)構(gòu)設(shè)計(jì)挑戰(zhàn)為出發(fā)點(diǎn),從整體結(jié)構(gòu)設(shè)計(jì)以及計(jì)算、片上訪存、片外訪存多個(gè)層次對該領(lǐng)域的關(guān)鍵優(yōu)化技術(shù)進(jìn)行詳實(shí)而系統(tǒng)的分析與介紹.最后還從不同角度對圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)設(shè)計(jì)的未來方向進(jìn)行了展望,期望能為該領(lǐng)域的研究人員帶來一定的啟發(fā).

當(dāng)前已有的圖神經(jīng)網(wǎng)絡(luò)應(yīng)用領(lǐng)域綜述論文從不同角度對圖神經(jīng)網(wǎng)絡(luò)算法以及軟件框架進(jìn)行總結(jié)與分析.綜述[1]對應(yīng)用于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域的主流圖神經(jīng)網(wǎng)絡(luò)算法進(jìn)行分類,并討論不同類別算法的關(guān)系與異同.綜述[10]依據(jù)圖神經(jīng)網(wǎng)絡(luò)模型的結(jié)構(gòu)和訓(xùn)練策略的不同,提出新的分類方法,并以模型的發(fā)展歷史為主線進(jìn)行介紹與分析.綜述[11]圍繞圖的表示學(xué)習(xí)(representation learning)方法展開,并建立統(tǒng)一的框架來描述這些相關(guān)模型.綜述[12]關(guān)注于圖神經(jīng)網(wǎng)絡(luò)的理論屬性,總結(jié)圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力(expressive power)并對比分析克服表達(dá)限制的圖神經(jīng)網(wǎng)絡(luò)模型.綜述[13]基于計(jì)算機(jī)的金字塔組織結(jié)構(gòu),對面向圖計(jì)算的加速結(jié)構(gòu)進(jìn)行分類和總結(jié),對于新興的圖神經(jīng)網(wǎng)絡(luò)應(yīng)用,僅以Hy GCN[9]作為案例進(jìn)行了討論.與前述工作側(cè)重點(diǎn)不同的是,本文針對圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)設(shè)計(jì)過程中涉及到的關(guān)鍵優(yōu)化技術(shù),進(jìn)行系統(tǒng)性分析和總結(jié),具有重要意義與啟發(fā)價(jià)值.

1 圖與圖神經(jīng)網(wǎng)絡(luò)

本節(jié)首先對圖數(shù)據(jù)結(jié)構(gòu)和圖神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)知識進(jìn)行簡要描述,然后對主流的圖神經(jīng)網(wǎng)絡(luò)算法、圖神經(jīng)網(wǎng)絡(luò)的應(yīng)用場景以及圖神經(jīng)網(wǎng)絡(luò)與傳統(tǒng)應(yīng)用的異同比較進(jìn)行介紹.

1.1 圖數(shù)據(jù)結(jié)構(gòu)

圖是一種由節(jié)點(diǎn)和邊組成的數(shù)據(jù)結(jié)構(gòu),節(jié)點(diǎn)通過邊進(jìn)行連接來表征節(jié)點(diǎn)之間的關(guān)系.通常將圖以G＝(V,E)的方式進(jìn)行定義,其中V代表節(jié)點(diǎn)集合,E代表節(jié)點(diǎn)之間的邊集合.v i∈V代表編號為i的節(jié)點(diǎn),e ij＝(v i,v j)∈E代表從i號節(jié)點(diǎn)到j(luò)號節(jié)點(diǎn)相連的一條邊.每個(gè)源節(jié)點(diǎn)與不同的目的節(jié)點(diǎn)相連接形成源節(jié)點(diǎn)的鄰居集合,也即N(v)＝{u∈V|(v,u)∈E}.另外,節(jié)點(diǎn)v通過特征向量h v來表征自己的屬性.不同于傳統(tǒng)圖計(jì)算中僅用一個(gè)元素表征節(jié)點(diǎn)屬性,圖神經(jīng)網(wǎng)絡(luò)中節(jié)點(diǎn)的特征向量通常包含成百上千個(gè)元素,該規(guī)模被稱為特征向量維度(feature dimension).本文用h v表示節(jié)點(diǎn)v的特征向量,|h v|表示節(jié)點(diǎn)v的特征向量維度.例如對于包含n個(gè)元素的特征向量h v＝(x1,x2,…,x n),其特征向量維度為n.

鄰接矩陣(adjacency matrix)是最直觀與最簡單的表示圖中節(jié)點(diǎn)分布與相連關(guān)系的方式.對于具有n個(gè)節(jié)點(diǎn)的圖G,可將G中節(jié)點(diǎn)的相連關(guān)系表示為規(guī)模為n×n的矩陣A的形式.當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j之間有相連邊(e ij∈E)時(shí),其在矩陣A中的對應(yīng)位置元素A ij置為1,否則置為0.使用這種存儲方式,鄰接矩陣只能表征圖中節(jié)點(diǎn)的相連關(guān)系,而每個(gè)節(jié)點(diǎn)的屬性(特征向量)需要另外存儲在一個(gè)多維矩陣X∈Rn×d中,其中n為節(jié)點(diǎn)個(gè)數(shù),d＝|h v|(h v∈Rd)為節(jié)點(diǎn)特征向量維度[1].

由于圖結(jié)構(gòu)的不規(guī)則性,其鄰接矩陣通常為稀疏矩陣.有3種主流格式常用以存儲稀疏圖鄰接矩陣:坐標(biāo)列表格式(coordinate list,COO)、壓縮稀疏行格式(compressed sparse row,CSR)以及壓縮稀疏列格式(compressed sparse column,CSC).COO是最簡單的一種存儲稀疏矩陣的方式,它通過3個(gè)一一對應(yīng)的數(shù)組記錄矩陣中所有非零的元素,3個(gè)數(shù)組分別記錄非零元素在矩陣中的行號、列號及節(jié)點(diǎn)特征.COO的方式簡單直觀,但記錄信息較多存在冗余,CSR和CSC格式進(jìn)一步對矩陣的存儲進(jìn)行壓縮.CSR格式同樣通過3個(gè)數(shù)組對稀疏矩陣進(jìn)行存儲,但對行數(shù)組進(jìn)行了壓縮,具體方法是行數(shù)組中的每個(gè)元素依次記錄稀疏矩陣中每行第1個(gè)非零元素在列數(shù)組中的偏移位置,因此也被稱為偏移數(shù)組.列數(shù)組依次記錄對應(yīng)行的非零元素列號,也即單跳(1-hop)鄰居(目標(biāo)節(jié)點(diǎn))的編號,該數(shù)組也被稱為邊數(shù)組,用以存儲出邊.最后通過屬性數(shù)組記錄節(jié)點(diǎn)的特征.CSC格式與CSR形式相似,不同的是進(jìn)行列的壓縮,其邊數(shù)組用以存儲入邊[9].

表1列出了本文所涉及到的標(biāo)識及含義.

Table 1 Commonly Used Notations and Meanings in GNNs表1 圖神經(jīng)網(wǎng)絡(luò)中常用標(biāo)識及含義

圖結(jié)構(gòu)具有極為強(qiáng)大的表示能力,理論上能夠表征任何事物間的互聯(lián)關(guān)系,在我們的日常生活中無處不在.例如圖1(a)是常見的城市地鐵線路圖,其中節(jié)點(diǎn)代表每個(gè)地鐵站點(diǎn),邊代表站點(diǎn)之間的通行路徑;圖1(b)是微博社交網(wǎng)絡(luò)圖,其中節(jié)點(diǎn)代表微博用戶,邊代表用戶之間的關(guān)注與好友關(guān)系;圖1(c)是化學(xué)中的分子結(jié)構(gòu)圖,其中節(jié)點(diǎn)代表組成分子的原子,邊代表原子之間的化學(xué)鍵.圖結(jié)構(gòu)數(shù)據(jù)中蘊(yùn)藏著豐富的信息,因此具有極高的實(shí)用和研究價(jià)值.圖神經(jīng)網(wǎng)絡(luò)是一種典型的處理圖結(jié)構(gòu)數(shù)據(jù)并深入挖掘潛藏信息的應(yīng)用,其應(yīng)用場景和重要性將在1.4節(jié)中加以介紹.

Fig.1 Typical graphs in daily life圖1 生活中的典型圖結(jié)構(gòu)數(shù)據(jù)

現(xiàn)實(shí)世界中的圖具有3個(gè)顯著特征:

1)規(guī)模大.實(shí)際應(yīng)用場景中的真實(shí)圖規(guī)模往往非常大,據(jù)統(tǒng)計(jì),阿里巴巴的用戶產(chǎn)品圖在2018年時(shí)達(dá)到10億用戶與20億產(chǎn)品的規(guī)模[14],臉書(Facebook)的數(shù)據(jù)圖在2015年時(shí)包含超過20億節(jié)點(diǎn)表示用戶以及超過萬億條邊表示用戶間的好友、點(diǎn)贊等不同的關(guān)系[15],拼趣(Pinterest)網(wǎng)站在2018年已達(dá)到超過20億節(jié)點(diǎn)和170億條邊的規(guī)模[16].除邊和節(jié)點(diǎn)規(guī)模外,用于表征現(xiàn)實(shí)圖中節(jié)點(diǎn)和邊屬性的特征向量維度常常也數(shù)以千計(jì),進(jìn)一步擴(kuò)大了圖的規(guī)模.

2)冪律分布.現(xiàn)實(shí)圖中的節(jié)點(diǎn)往往呈現(xiàn)冪律分布(power-law)的特征,即少數(shù)節(jié)點(diǎn)會與大部分節(jié)點(diǎn)之間具有相連關(guān)系,而大多數(shù)節(jié)點(diǎn)僅與少量其他節(jié)點(diǎn)之間存在邊相連.例如,在電商的交易行為圖中,少數(shù)的大型企業(yè)及銷量高的商戶節(jié)點(diǎn)會與極高數(shù)目的用戶節(jié)點(diǎn)之間存在交易行為,而圖中占大比例的普通買家用戶節(jié)點(diǎn)僅與少量購買過商品的商戶節(jié)點(diǎn)有邊相連.

3)動態(tài)多樣性.現(xiàn)實(shí)場景中的圖往往具有動態(tài)變化且鄰居節(jié)點(diǎn)分布不規(guī)則的特征.例如,在微博等社交平臺網(wǎng)絡(luò)中,注冊用戶的數(shù)目、用戶的關(guān)注數(shù)、點(diǎn)贊評論行為等每時(shí)每刻都在發(fā)生變化,且圖中用戶節(jié)點(diǎn)間的關(guān)系極為不規(guī)則.另外,現(xiàn)實(shí)圖的種類多變,在不同的應(yīng)用場景中,根據(jù)不同節(jié)點(diǎn)之間是否有指向性要求,分為有向圖或無向圖;根據(jù)不同節(jié)點(diǎn)的類型是否相同,分為同質(zhì)圖和異質(zhì)圖;根據(jù)處理過程中圖結(jié)構(gòu)是否發(fā)生變化,分為動態(tài)圖和靜態(tài)圖.

1.2 圖神經(jīng)網(wǎng)絡(luò)模型

盡管傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)在人工智能領(lǐng)域取得了巨大成功,但它只能應(yīng)用于歐幾里得空間的分布規(guī)整且結(jié)構(gòu)固定的數(shù)據(jù).為使更多現(xiàn)實(shí)應(yīng)用場景智能化,圖神經(jīng)網(wǎng)絡(luò)應(yīng)運(yùn)而生.圖神經(jīng)網(wǎng)絡(luò)同時(shí)受到傳統(tǒng)圖計(jì)算和神經(jīng)網(wǎng)絡(luò)的啟發(fā),擴(kuò)寬和加深了神經(jīng)網(wǎng)絡(luò)的應(yīng)用范圍和學(xué)習(xí)能力.圖神經(jīng)網(wǎng)絡(luò)利用圖結(jié)構(gòu),對節(jié)點(diǎn)的屬性與相連關(guān)系進(jìn)行建模與學(xué)習(xí),通過對輸入的節(jié)點(diǎn)、邊、特征屬性等信息進(jìn)行逐層的迭代處理,最終對指定節(jié)點(diǎn)的特征向量進(jìn)行更新,實(shí)現(xiàn)分類、預(yù)測、推薦、識別等不同的執(zhí)行目的.

現(xiàn)有的主流圖神經(jīng)網(wǎng)絡(luò)算法可以統(tǒng)一抽象為模型:

另外,為了簡化執(zhí)行過程,圖神經(jīng)網(wǎng)絡(luò)算法通常可以在圖聚合階段增加自環(huán)(self-loop),也就是將節(jié)點(diǎn)自身的特征與其鄰居節(jié)點(diǎn)特征同時(shí)進(jìn)行聚合,進(jìn)而在圖更新階段不區(qū)分自身節(jié)點(diǎn)特征和由鄰居節(jié)點(diǎn)聚合形成的中間特征的神經(jīng)網(wǎng)絡(luò)參數(shù).該方法盡管會損失部分模型表達(dá)能力,但執(zhí)行過程簡單并可從一定程度上緩解圖神經(jīng)網(wǎng)絡(luò)可能存在的過擬合(over-fitting)現(xiàn)象[17].增加自環(huán)的圖神經(jīng)網(wǎng)絡(luò)可抽象為模型:

與神經(jīng)網(wǎng)絡(luò)類似,為獲得對知識進(jìn)行學(xué)習(xí)和預(yù)測的能力,一個(gè)完整的圖神經(jīng)網(wǎng)絡(luò)包含訓(xùn)練(train)和推斷(inference)兩個(gè)主要部分.

1)訓(xùn)練過程

訓(xùn)練是一種知識學(xué)習(xí)的過程,通過對網(wǎng)絡(luò)進(jìn)行訓(xùn)練不斷修正模型中的相應(yīng)參數(shù),才能為圖神經(jīng)網(wǎng)絡(luò)應(yīng)用提供更準(zhǔn)確與強(qiáng)大的推斷能力.

圖神經(jīng)網(wǎng)絡(luò)通常可以通過反向傳播(back propagation)的過程對損失函數(shù)進(jìn)行訓(xùn)練[18-20].其中損失函數(shù)用于衡量圖神經(jīng)網(wǎng)絡(luò)中最終得到的節(jié)點(diǎn)預(yù)測值與其真實(shí)值的差距,訓(xùn)練的目的是通過不斷降低損失函數(shù)梯度以期模型對數(shù)據(jù)的預(yù)測更為準(zhǔn)確,該過程通常可以采用隨機(jī)梯度下降或其變形方法實(shí)現(xiàn)[17,21].

依據(jù)學(xué)習(xí)任務(wù)的標(biāo)簽信息,圖神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程可分為有監(jiān)督學(xué)習(xí)(supervised learning)、半監(jiān)督學(xué)習(xí)(semi-supervised learning)和非監(jiān)督學(xué)習(xí)(unsupervised learning).有監(jiān)督學(xué)習(xí)的學(xué)習(xí)樣本包含所有數(shù)據(jù)標(biāo)簽,通常用于整張圖級別的分類,預(yù)測其類別標(biāo)簽[22-25];半監(jiān)督學(xué)習(xí)的學(xué)習(xí)樣本僅包含部分已知的數(shù)據(jù)標(biāo)簽,而圖中其余節(jié)點(diǎn)的標(biāo)簽未知,通常用于節(jié)點(diǎn)級別的分類預(yù)測[3];非監(jiān)督學(xué)習(xí)的學(xué)習(xí)樣本不進(jìn)行專門的數(shù)據(jù)標(biāo)記,通過邊等圖中信息學(xué)習(xí)圖的表示和發(fā)現(xiàn)潛在結(jié)構(gòu)特征[26-28].

另外,許多已有的圖神經(jīng)網(wǎng)絡(luò)算法為提高訓(xùn)練的效率提出了不同策略[11,17].以GraphSAGE[28]為代表的眾多圖神經(jīng)網(wǎng)絡(luò)算法提出采樣訓(xùn)練的策略,不同于傳統(tǒng)需要用整個(gè)圖的拉普拉斯矩陣(Laplacian matrix)[3]作為訓(xùn)練樣本,這些算法通過不同的采樣策略對圖的子集進(jìn)行訓(xùn)練,從而減少冗余計(jì)算并可實(shí)現(xiàn)歸納式學(xué)習(xí)(inductive learning)的效果[16,29-30].Veli kovi等人[31],GPT-GNN[32]等工作提出通過預(yù)訓(xùn)練的方式,在沒有或極少有標(biāo)簽數(shù)據(jù)的情況下,捕獲和學(xué)習(xí)圖的結(jié)構(gòu)和語義信息,從而實(shí)現(xiàn)僅通過少量微調(diào)即可高效預(yù)測同領(lǐng)域圖的效果.

2)推斷過程

通過訓(xùn)練過程對知識進(jìn)行學(xué)習(xí)并不斷對網(wǎng)絡(luò)模型進(jìn)行調(diào)整后,圖神經(jīng)網(wǎng)絡(luò)具備了一定的推斷能力,此時(shí)可執(zhí)行推斷過程,針對不同需求,對新知識進(jìn)行推斷.

推斷同樣遵循本節(jié)前述的通用圖神經(jīng)網(wǎng)絡(luò)模型.此過程主要包含圖聚合(aggregate)和圖更新(update)兩大主要階段,不同的圖神經(jīng)網(wǎng)絡(luò)算法可以通過不同的方法分別對不同階段進(jìn)行實(shí)現(xiàn).圖聚合階段對每個(gè)節(jié)點(diǎn)的鄰居進(jìn)行遍歷,并收集鄰居節(jié)點(diǎn)的信息從而聚合為該節(jié)點(diǎn)在當(dāng)前層的中間特征.圖聚合階段的行為通常可以由累加(accumulate)、均值(mean)、最大(max)、最小(min)、池化(pooling)等方法實(shí)現(xiàn).圖更新階段對聚合過的節(jié)點(diǎn)特征向量通過神經(jīng)網(wǎng)絡(luò)來進(jìn)行節(jié)點(diǎn)的變換與更新,為節(jié)點(diǎn)生成新的特征向量.圖更新階段的行為通常可以由多層感知機(jī)(multi-layer perceptron,MLP)、門控循環(huán)單元(gated recurrent unit,GRU)、長短期記憶網(wǎng)絡(luò)(long short-term memory,LSTM)以及非線性激活函數(shù)等實(shí)現(xiàn),而圖更新階段所需的權(quán)重、偏差等模型參數(shù)均通過訓(xùn)練階段學(xué)習(xí)得到.另外還可通過讀出(readout)操作,將獲取的圖中各節(jié)點(diǎn)的輸出特征整合為整張圖的特征表示.

為提升模型的執(zhí)行性能與效果,主流的圖神經(jīng)網(wǎng)絡(luò)算法也為圖聚合及圖更新階段提出了不同的優(yōu)化執(zhí)行策略.例如,GCN[3]為圖聚合階段增加歸一化(normalization)操作,從而削弱不同節(jié)點(diǎn)的度數(shù)差異引起的梯度不穩(wěn)定等現(xiàn)象;GraphSAGE[28]、He等人[33]工作在圖更新階段引入向量串連(vector concatenation)、跳躍連接(skip connection)等操作,緩解網(wǎng)絡(luò)層數(shù)不斷加深后可能引起的節(jié)點(diǎn)表示過平滑(over-smoothing)的問題.

1.3 典型圖神經(jīng)網(wǎng)絡(luò)算法

隨著圖神經(jīng)網(wǎng)絡(luò)的興起,大量圖神經(jīng)網(wǎng)絡(luò)算法和模型被提出,用于不同的應(yīng)用場景,實(shí)現(xiàn)不同的學(xué)習(xí)與推理目的.如圖2所示,常見的圖神經(jīng)網(wǎng)絡(luò)應(yīng)用可以分為卷積圖神經(jīng)網(wǎng)絡(luò)(convolutional graph neural networks)、循環(huán)圖神經(jīng)網(wǎng)絡(luò)(recurrent graph neural networks)、圖自編碼器(graph autoencoders)和時(shí)空圖神經(jīng)網(wǎng)絡(luò)(spatial-temporal graph neural networks)四大類[1,34],本節(jié)將依次對這四大類圖神經(jīng)網(wǎng)絡(luò)進(jìn)行簡要介紹.

Fig.2 Classification of mainstream graph neural network algorithms圖2 主流圖神經(jīng)網(wǎng)絡(luò)算法分類

1)卷積圖神經(jīng)網(wǎng)絡(luò)

卷積圖神經(jīng)網(wǎng)絡(luò)(convolutional graph neural networks)是目前研究和應(yīng)用范圍最廣、相關(guān)變形算法種類最多的圖神經(jīng)網(wǎng)絡(luò)分支之一.它將傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行擴(kuò)展,使其能夠處理非歐幾里得空間的圖數(shù)據(jù).卷積圖神經(jīng)網(wǎng)絡(luò)還可分為頻域(spectral)和空域(spatial)兩種類型.頻域卷積圖神經(jīng)網(wǎng)絡(luò)通常利用拉普拉斯矩陣對圖實(shí)現(xiàn)傅里葉變換(Fourier transform,FT)和逆傅里葉變換(inverse Fourier transform,IFT).空域卷積圖神經(jīng)網(wǎng)絡(luò)利用圖的信息傳播來實(shí)現(xiàn)卷積,通常會比頻域卷積圖神經(jīng)網(wǎng)絡(luò)具備更強(qiáng)的靈活性和更高的執(zhí)行效率.主流的卷積圖神經(jīng)網(wǎng)絡(luò)算法包括圖卷積網(wǎng)絡(luò)(graph convolutional network,GCN)[3]、自適應(yīng)圖卷積神經(jīng)網(wǎng)絡(luò)(adaptive graph convolutional neural network,AGCN)[35]、采樣聚合圖神經(jīng)網(wǎng)絡(luò)(graph sample and aggregate,Graph-SAGE)[28]、圖同構(gòu)網(wǎng)絡(luò)(graph isomorphism network,GIN)[36]、圖注意力網(wǎng)絡(luò)(graph attention network,GAT)[37]、門控注意力網(wǎng)絡(luò)(gated attention network,Ga AN)[38]等.

2)循環(huán)圖神經(jīng)網(wǎng)絡(luò)

循環(huán)圖神經(jīng)網(wǎng)絡(luò)(recurrent graph neural networks)將循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural networks,RNNs)中的門控機(jī)制引入到圖領(lǐng)域,循環(huán)執(zhí)行從而獲取圖中節(jié)點(diǎn)的高層表示.主流的循環(huán)圖神經(jīng)網(wǎng)絡(luò)包括門控序列圖神經(jīng)網(wǎng)絡(luò)(gated graph sequence neural networks,GGS-NNs)[39]和隨機(jī)穩(wěn)態(tài)嵌入(stochastic steady-state embedding,SSE)[4].GGS-NNs將門控循環(huán)單元(gated recurrent units,GRUs)[40]引入到圖神經(jīng)網(wǎng)絡(luò)中,形成門控圖神經(jīng)網(wǎng)絡(luò)(gated graph neural networks,GG-NNs),并按順序執(zhí)行多個(gè)GG-NNs從而輸出序列化結(jié)果.SSE在執(zhí)行過程中交替進(jìn)行節(jié)點(diǎn)穩(wěn)態(tài)計(jì)算與模型參數(shù)調(diào)優(yōu),是一種能夠?qū)D進(jìn)行穩(wěn)態(tài)學(xué)習(xí)的循環(huán)圖神經(jīng)網(wǎng)絡(luò),并能夠很好地?cái)U(kuò)展到大規(guī)模圖中.

3)圖自編碼器

圖自編碼器(graph autoencoders)將自編碼器引入圖領(lǐng)域中,通過編碼器將節(jié)點(diǎn)表示轉(zhuǎn)換為低維向量.圖自編碼器廣泛應(yīng)用于無監(jiān)督學(xué)習(xí)領(lǐng)域[41],進(jìn)行圖的節(jié)點(diǎn)表示學(xué)習(xí)或生成新圖.常見的圖自編碼器有變分圖自編碼器(variational graph autoencoders,VGAE)[26]、深度遞歸網(wǎng)絡(luò)嵌入(deep recursive network embedding,DRNE)[42]等.VGAE是第1個(gè)將變分自編碼器(variational autoencoder,VAE)引入圖領(lǐng)域的算法.VGAE采用GCN作為編碼器,以及一個(gè)簡單的內(nèi)積作為解碼器.DRNE將節(jié)點(diǎn)的鄰居進(jìn)行排序,然后直接利用歸一化的LSTM,通過聚合鄰居節(jié)點(diǎn)的信息,對低維度節(jié)點(diǎn)向量進(jìn)行重建.

4)時(shí)空圖神經(jīng)網(wǎng)絡(luò)

時(shí)空圖神經(jīng)網(wǎng)絡(luò)(spatial-temporal graph neural networks)的核心目的是同時(shí)獲取時(shí)空圖(spatialtemporal graph)中時(shí)間和空間的依賴關(guān)系.時(shí)空圖中每個(gè)節(jié)點(diǎn)的輸入動態(tài)變化.時(shí)空圖神經(jīng)網(wǎng)絡(luò)的目標(biāo)為預(yù)測節(jié)點(diǎn)或時(shí)空圖的數(shù)據(jù)標(biāo)簽[1],在天氣預(yù)測、交通預(yù)測、動作識別等領(lǐng)域有廣泛應(yīng)用.主流的時(shí)空圖神經(jīng)網(wǎng)絡(luò)包括結(jié)構(gòu)神經(jīng)網(wǎng)絡(luò)(structural-RNN,SRNN)[43]、圖 波 網(wǎng)(Graph Wave Net)[44]等.S-RNN將循環(huán)神經(jīng)網(wǎng)絡(luò)RNN和圖時(shí)空建模相結(jié)合,提出了一個(gè)周期性的框架來預(yù)測每個(gè)時(shí)間步的節(jié)點(diǎn)標(biāo)簽.Graph WaveNet在圖卷積層通過有監(jiān)督訓(xùn)練獲取隱藏的空間依賴關(guān)系,同時(shí)通過堆疊擴(kuò)展的因果卷積層(dilated casual convolutions)來獲取隱藏的時(shí)間依賴關(guān)系,從而獲取更高的時(shí)空網(wǎng)絡(luò)執(zhí)行效率和性能.

1.4 圖神經(jīng)網(wǎng)絡(luò)應(yīng)用場景與重要性

得益于對圖結(jié)構(gòu)數(shù)據(jù)強(qiáng)大的處理和學(xué)習(xí)能力,圖神經(jīng)網(wǎng)絡(luò)在愈加廣泛的現(xiàn)實(shí)應(yīng)用場景中大放異彩,對為人們提供更加方便智能化的生活服務(wù)、為企業(yè)提供風(fēng)險(xiǎn)保障、提升業(yè)務(wù)質(zhì)量和用戶體驗(yàn)、推動科學(xué)技術(shù)快速發(fā)展等方面均具有重大意義.如圖3所示,常見的圖神經(jīng)網(wǎng)絡(luò)應(yīng)用場景可分為推薦系統(tǒng)、計(jì)算機(jī)視覺、自然語言處理、自然科學(xué)研究、實(shí)況預(yù)測、金融風(fēng)控六大類,本節(jié)將依次對不同的應(yīng)用場景進(jìn)行介紹.

Fig.3 Common application scenarios of graph neural networks圖3 常見的圖神經(jīng)網(wǎng)絡(luò)應(yīng)用場景

1)推薦系統(tǒng)

推薦系統(tǒng)(recommendation system)是生活中最常見的圖神經(jīng)網(wǎng)絡(luò)應(yīng)用場景之一,多用于社交、電商等具有大量用戶交互的線上平臺.推薦系統(tǒng)的圖中包含用戶節(jié)點(diǎn)和項(xiàng)目節(jié)點(diǎn)(例如商品、電影、歌曲等),通過分析不同節(jié)點(diǎn)間的交互關(guān)系與屬性等附加信息,推薦系統(tǒng)為項(xiàng)目節(jié)點(diǎn)進(jìn)行重要性排序,力求準(zhǔn)確推斷用戶的偏好,為用戶提供優(yōu)質(zhì)的內(nèi)容推薦服務(wù)[45].

GC-MC[46],SpectralCF[47],NGCF[48]等工作利用協(xié)同過濾(collaborative filtering,CF)來處理矩陣補(bǔ)全問題,從而預(yù)測用戶喜愛的項(xiàng)目排名.考慮到用戶購買商品等行為會受到朋友的影響,Diff Net[49],DANSER[50],GraphRec[51]等工作將不同用戶間的社交信息納入用戶節(jié)點(diǎn)與項(xiàng)目節(jié)點(diǎn)的關(guān)系分析中.KGCN[52],KGAT[53]等相關(guān)工作通過建立知識圖譜,深入挖掘圖節(jié)點(diǎn)之間的關(guān)聯(lián)屬性.另外還有DGRec[54],SR-GNN[55]等工作分析用戶的過往行為,基于會話對用戶的后繼行為進(jìn)行預(yù)測,從而實(shí)現(xiàn)序列推薦(sequential recommendation).

2)計(jì)算機(jī)視覺

圖神經(jīng)網(wǎng)絡(luò)在計(jì)算機(jī)視覺(computer vision)領(lǐng)域發(fā)揮重要作用.具體而言,主要應(yīng)用于圖像分類(image classification)、視覺 推 理(visual reasoning)、人體動作識別(action recognition)和點(diǎn)云建模等場景中.

圖像分類是計(jì)算機(jī)視覺中最基礎(chǔ)也極為重要的分支,文獻(xiàn)[56-60]利用知識圖譜、圖像相似度分析、引入語義信息等方法對圖像進(jìn)行零樣本(zero-shot)及少樣本(few-shot)學(xué)習(xí),從而高效地對圖像進(jìn)行分類.文獻(xiàn)[61-64]通過建立場景圖、知識圖譜等方式處理計(jì)算機(jī)視覺中經(jīng)典的視覺問答(visual question answering,VQA)任務(wù),用于推理圖像中的有效信息.文獻(xiàn)[65-68]關(guān)注于人體關(guān)節(jié)之間的關(guān)聯(lián)關(guān)系與時(shí)間序列,應(yīng)用不同的圖神經(jīng)網(wǎng)絡(luò)算法,實(shí)現(xiàn)基于人體骨架數(shù)據(jù)的動作識別(skeleton-based action recognition).文獻(xiàn)[69-71]通過激光檢測與測量方法(light detection and ranging,LiDAR)獲取點(diǎn)云數(shù)據(jù),并在其上實(shí)施圖神經(jīng)網(wǎng)絡(luò),從而實(shí)現(xiàn)點(diǎn)云的分類與分割.

3)自然語言處理

圖神經(jīng)網(wǎng)絡(luò)在自然語言處理(natural language processing)領(lǐng)域的應(yīng)用是當(dāng)前的熱門研究方向之一,其中最主要的是文本分類(text classification),另外還在關(guān)系抽取(relation extraction)和知識發(fā)現(xiàn)(knowledge discovery)等方向進(jìn)行了探索.

文獻(xiàn)[72-75]將文本中的單詞組織成為圖結(jié)構(gòu),在其上實(shí)施不同的圖神經(jīng)網(wǎng)絡(luò),從而能夠挖掘文本詞句間的內(nèi)在聯(lián)系,根據(jù)不同的目標(biāo)實(shí)現(xiàn)文本的分類.文獻(xiàn)[76-79]通過圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)語句的關(guān)系知識,并通過關(guān)系抽取模型實(shí)現(xiàn)自然語言的關(guān)系推理.文獻(xiàn)[80]對自然語言語句進(jìn)行圖神經(jīng)網(wǎng)絡(luò)處理,生成語義圖(semantic graph),從而用于知識發(fā)現(xiàn).

4)自然科學(xué)研究

圖神經(jīng)網(wǎng)絡(luò)在推動包括物理、化學(xué)、生物等多種自然科學(xué)研究的發(fā)展中起到重要作用.在物理學(xué)科方面,文獻(xiàn)[81-83]提出不同的物理互作網(wǎng)絡(luò)(interaction network),通過物體現(xiàn)態(tài)和關(guān)聯(lián)關(guān)系等預(yù)測物體未來的狀態(tài).在化學(xué)和生物學(xué)領(lǐng)域,例如分子、蛋白質(zhì)化合物等依據(jù)其結(jié)構(gòu)能夠方便地形成圖結(jié)構(gòu)數(shù)據(jù).文獻(xiàn)[84-86]將分子表示為原子圖或聯(lián)結(jié)樹的形式,通過不同的圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)和預(yù)測分子指紋(molecular fingerprints).文獻(xiàn)[87-88]通過圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)和預(yù)測蛋白質(zhì)間的相互作用.對蛋白質(zhì)等復(fù)雜結(jié)構(gòu)關(guān)系的學(xué)習(xí)進(jìn)一步也可應(yīng)用于制藥、疾病分類等領(lǐng)域.

5)實(shí)況預(yù)測

近年來,交通和天氣等領(lǐng)域也廣泛利用圖神經(jīng)網(wǎng)絡(luò)進(jìn)行實(shí)況預(yù)測,多采用時(shí)空網(wǎng)絡(luò)模型,同時(shí)對時(shí)間和空間信息進(jìn)行采集和分析.交通方面,圖神經(jīng)網(wǎng)絡(luò)通過對司機(jī)、行人等道路用戶、道路傳感器以及諸如交通法規(guī)、擁堵情況各類附加屬性信息進(jìn)行建模,形成運(yùn)輸系統(tǒng)[89],為用戶的便利出行提供實(shí)時(shí)的道路預(yù)報(bào).文獻(xiàn)[90-93]根據(jù)交通流量預(yù)估出行速度等路況信息,文獻(xiàn)[94]關(guān)注于網(wǎng)約車需求預(yù)測,從而優(yōu)化城市資源分配.天氣方面,文獻(xiàn)[95]對柵格氣候數(shù)據(jù)進(jìn)行圖神經(jīng)網(wǎng)絡(luò)建模,分析氣候依賴,對厄爾尼諾現(xiàn)象(El Ni?o-Southern Oscillation,ENSO)等極端氣象進(jìn)行預(yù)測,從而避免可能的災(zāi)難發(fā)生.

6)金融風(fēng)控

金融行業(yè)存在大量的風(fēng)控需求,是圖神經(jīng)網(wǎng)絡(luò)應(yīng)用最廣泛的領(lǐng)域之一.文獻(xiàn)[96]面向中小型企業(yè)建立企業(yè)互動關(guān)系網(wǎng)絡(luò),為供應(yīng)鏈中的企業(yè)合作關(guān)系進(jìn)行風(fēng)險(xiǎn)評估.文獻(xiàn)[97]對用戶交易關(guān)系建立動態(tài)圖,通過圖神經(jīng)網(wǎng)絡(luò)識別異常行為,對每筆交易進(jìn)行風(fēng)險(xiǎn)評估.文獻(xiàn)[5]針對用戶行為建立圖結(jié)構(gòu),通過圖神經(jīng)網(wǎng)絡(luò)進(jìn)行設(shè)備聚集、時(shí)間聚集等分析,識別惡意賬戶,從而規(guī)避惡意賬戶通過大量注冊“僵尸賬號”進(jìn)行洗錢、欺詐等目的.

1.5 圖神經(jīng)網(wǎng)絡(luò)與傳統(tǒng)應(yīng)用的比較

圖神經(jīng)網(wǎng)絡(luò)整體上可以視為傳統(tǒng)圖計(jì)算應(yīng)用與神經(jīng)網(wǎng)絡(luò)應(yīng)用的結(jié)合體,其同時(shí)具有這2類應(yīng)用的特征,本節(jié)對圖神經(jīng)網(wǎng)絡(luò)與傳統(tǒng)應(yīng)用的比較進(jìn)行介紹.

1)與圖計(jì)算應(yīng)用的比較

①數(shù)據(jù)類型.圖神經(jīng)網(wǎng)絡(luò)與圖計(jì)算均針對非歐幾里得空間的不規(guī)則圖結(jié)構(gòu)數(shù)據(jù)進(jìn)行處理.

②執(zhí)行行為.圖神經(jīng)網(wǎng)絡(luò)的圖聚合階段行為與傳統(tǒng)圖計(jì)算應(yīng)用類似,均為通過逐跳(hop)遍歷圖中節(jié)點(diǎn)收集并聚合鄰居信息.但是通常在圖計(jì)算應(yīng)用處理的圖中,節(jié)點(diǎn)特征只包含單個(gè)元素,用于表征節(jié)點(diǎn)的層次、距離等屬性.而在圖神經(jīng)網(wǎng)絡(luò)應(yīng)用處理的圖中,節(jié)點(diǎn)特征需要通過向量進(jìn)行表示.向量中的元素個(gè)數(shù)往往成百上千,且在執(zhí)行過程中存在動態(tài)變化,能夠表達(dá)非常豐富的屬性信息.盡管圖中節(jié)點(diǎn)分布極不規(guī)則,但得益于更高的特征向量維度,圖神經(jīng)網(wǎng)絡(luò)相較圖計(jì)算而言,具備較高的數(shù)據(jù)空間局部性.

③學(xué)習(xí)能力.圖計(jì)算應(yīng)用不具備知識學(xué)習(xí)的能力,執(zhí)行過程較為簡單,通常應(yīng)用于路徑規(guī)劃、頁面排序、網(wǎng)絡(luò)分析等場景.而圖神經(jīng)網(wǎng)絡(luò)集成神經(jīng)網(wǎng)絡(luò)的行為,具備知識學(xué)習(xí)和推斷的能力,適用場景更為廣泛.

2)與神經(jīng)網(wǎng)絡(luò)應(yīng)用的比較

①數(shù)據(jù)類型.神經(jīng)網(wǎng)絡(luò)只能處理歐幾里得空間的規(guī)整數(shù)據(jù),而圖神經(jīng)網(wǎng)絡(luò)面向的是現(xiàn)實(shí)生活中更廣泛存在的非歐幾里得空間的不規(guī)則且動態(tài)變化的圖結(jié)構(gòu)數(shù)據(jù).

②執(zhí)行行為.圖神經(jīng)網(wǎng)絡(luò)的圖更新階段與傳統(tǒng)神經(jīng)網(wǎng)絡(luò)應(yīng)用相似.但傳統(tǒng)神經(jīng)網(wǎng)絡(luò)中,依賴信息僅能以節(jié)點(diǎn)的屬性形式存在,而圖神經(jīng)網(wǎng)絡(luò)能夠通過聚合過程,將圖節(jié)點(diǎn)間的依賴關(guān)系在圖中進(jìn)行傳播.

③學(xué)習(xí)能力.二者均包含訓(xùn)練和推斷的過程,具備知識學(xué)習(xí)的能力.

④可解釋性.許多復(fù)雜的神經(jīng)網(wǎng)絡(luò)僅支持黑箱操作[98],無法有效提供可解釋性.然而可解釋性為智能算法的判定結(jié)果提供可靠證明,是保障其有效性的重要依據(jù).圖神經(jīng)網(wǎng)絡(luò)的執(zhí)行模式為可解釋性帶來更多便利與可能,目前已有少量可解釋性方法的成果[99-100]產(chǎn)出.

2 圖神經(jīng)網(wǎng)絡(luò)編程模型與框架

算法1是一個(gè)圖神經(jīng)網(wǎng)絡(luò)的通用編程模型[101],可適用于各類圖神經(jīng)網(wǎng)絡(luò)算法.編程模型的輸入包括圖結(jié)構(gòu)數(shù)據(jù)G、圖中每個(gè)節(jié)點(diǎn)v(v∈V)的初始特征x v以及圖神經(jīng)網(wǎng)絡(luò)執(zhí)行層數(shù)或所需收集的最大鄰居跳數(shù)(hop)K.首先對圖中每個(gè)節(jié)點(diǎn)進(jìn)行特征h v初始化并對節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行采樣,其中采樣過程為可選項(xiàng).然后依次為圖中每個(gè)節(jié)點(diǎn)收集并聚合其采樣后鄰居節(jié)點(diǎn)的特征,進(jìn)而通過MLP等常見神經(jīng)網(wǎng)絡(luò)對圖中節(jié)點(diǎn)進(jìn)行更新,生成新的特征向量.圖神經(jīng)網(wǎng)絡(luò)的聚合和更新過程交替進(jìn)行,直到執(zhí)行K次后,進(jìn)行輸出.圖神經(jīng)網(wǎng)絡(luò)的輸出可以是圖中每個(gè)節(jié)點(diǎn)的最終特征向量,也可以是通過readout等操作獲取的整張圖的特征表示.

算法1.圖神經(jīng)網(wǎng)絡(luò)通用編程模型.

作為近年來人工智能領(lǐng)域最熱門的研究方向之一,圖神經(jīng)網(wǎng)絡(luò)已產(chǎn)出大量不同的算法.眾多企業(yè)及研究團(tuán)隊(duì)開展了基于通用平臺的面向圖神經(jīng)網(wǎng)絡(luò)的框架與擴(kuò)展庫的研發(fā)工作.由于圖神經(jīng)網(wǎng)絡(luò)應(yīng)用與傳統(tǒng)神經(jīng)網(wǎng)絡(luò)應(yīng)用在很多執(zhí)行方式方面有異曲同工之處,諸多已有工作均基于發(fā)展成熟的神經(jīng)網(wǎng)絡(luò)框架,例如Py Torch和Tensorflow等進(jìn)行擴(kuò)展,形成支持圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的新型框架.這些框架與擴(kuò)展庫支持多種不同的圖神經(jīng)網(wǎng)絡(luò)算法,大多已開源,方便用戶在其上靈活地構(gòu)造圖神經(jīng)網(wǎng)絡(luò).下面將對主流的圖神經(jīng)網(wǎng)絡(luò)框架與擴(kuò)展庫進(jìn)行介紹.

1)Py G

Py Torch Geometric(Py G)[102]由多特蒙德工業(yè)大學(xué)研究團(tuán)隊(duì)提出,是目前最常用的通用圖神經(jīng)網(wǎng)絡(luò)擴(kuò)展庫,它基于Py Torch框架擴(kuò)展而成,同時(shí)支持在CPU和GPU平臺上運(yùn)行,已開源.除了常見的圖結(jié)構(gòu)數(shù)據(jù)處理方法外,PyG還提供對關(guān)系學(xué)習(xí)(relational learning)和3D數(shù)據(jù)處理等方法的支持.

Py G為用戶提供通用的消息傳遞(message passing)接口,使用戶能夠在Py G上快速清晰地實(shí)現(xiàn)有關(guān)圖神經(jīng)網(wǎng)絡(luò)算法的新研究想法.在此接口下,用戶只需要分別定義message和update函數(shù)以及選擇節(jié)點(diǎn)聚合模式,即可完成一個(gè)圖神經(jīng)網(wǎng)絡(luò)算法的構(gòu)建,實(shí)現(xiàn)對節(jié)點(diǎn)進(jìn)行鄰居聚合以及對節(jié)點(diǎn)進(jìn)行更新的操作.

2)DGL

Deep Graph Library(DGL)[103]是由亞馬遜人工智能研究院與紐約大學(xué)合作開發(fā)的開源圖神經(jīng)網(wǎng)絡(luò)擴(kuò)展庫.DGL基于多種已有的神經(jīng)網(wǎng)絡(luò)框架擴(kuò)展實(shí)現(xiàn),目前已支持Tensonflow,Py Torch和MXNet,并最小化用戶跨平臺遷移圖神經(jīng)網(wǎng)絡(luò)模型時(shí)的工作量.

DGL將圖神經(jīng)網(wǎng)絡(luò)計(jì)算過程抽象為用戶可配置的消息傳遞單元,并提取圖神經(jīng)網(wǎng)絡(luò)中的稀疏矩陣乘與消息傳遞機(jī)制間的聯(lián)系,將計(jì)算操作整合為泛化的稀疏 稠密-型矩陣乘(generalized sparsedense matrix multiplication,g-Sp MM)與泛化的采樣稠密-稠密型矩陣乘(generalized sampled densedense matrix multiplication,g-SDDMM).另 外,DGL還引入了不同類別的并行策略,通過對g-Sp MM采用節(jié)點(diǎn)級并行,對g-SDDMM采用邊級并行的方式,使其具備高執(zhí)行速度和訪存效率.

3)AliGraph

AliGraph[101]是阿里巴巴團(tuán)隊(duì)發(fā)布的面向大規(guī)模圖神經(jīng)網(wǎng)絡(luò)的研發(fā)和應(yīng)用設(shè)計(jì)的一款開源分布式框架,其已經(jīng)在阿里巴巴集團(tuán)完成商用落地.

AliGraph的系統(tǒng)分為算子(operator)、采樣(sampling)和數(shù)據(jù)存儲(storage)這3個(gè)層次.算子層將不同的圖神經(jīng)網(wǎng)絡(luò)算法拆解為系統(tǒng)中的采樣(sample)、聚合(aggregate)和組合(combine)三個(gè)算子,并進(jìn)行優(yōu)化計(jì)算;采樣層集成多種不同的采樣策略,使其能夠快速準(zhǔn)確地生成訓(xùn)練樣本;數(shù)據(jù)存儲層通過靈活的圖劃分、對圖中不同屬性進(jìn)行分別存儲以及緩存熱點(diǎn)數(shù)據(jù)等策略來實(shí)現(xiàn)高效的數(shù)據(jù)組織和存儲.

3 圖神經(jīng)網(wǎng)絡(luò)加速的挑戰(zhàn)

圖神經(jīng)網(wǎng)絡(luò)的復(fù)雜執(zhí)行過程為其有效加速帶來了諸多困難,本節(jié)將首先對圖神經(jīng)網(wǎng)絡(luò)的執(zhí)行行為以及導(dǎo)致通用平臺和面向傳統(tǒng)應(yīng)用的加速結(jié)構(gòu)無法高效執(zhí)行圖神經(jīng)網(wǎng)絡(luò)的原因進(jìn)行分析,進(jìn)而給出圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)設(shè)計(jì)過程中遇到的挑戰(zhàn).

3.1 圖神經(jīng)網(wǎng)絡(luò)執(zhí)行行為分析

圖神經(jīng)網(wǎng)絡(luò)是圖計(jì)算與神經(jīng)網(wǎng)絡(luò)的結(jié)合體,其執(zhí)行過程同時(shí)具有這2種傳統(tǒng)應(yīng)用的特點(diǎn),整體而言具有混合的執(zhí)行行為.圖聚合和圖更新階段的執(zhí)行行為的對比總結(jié)如表2所示.混合的執(zhí)行行為給圖神經(jīng)網(wǎng)絡(luò)的高效執(zhí)行帶來極大挑戰(zhàn).

1)圖聚合階段.在此階段,圖神經(jīng)網(wǎng)絡(luò)對每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行遍歷,從而采集和聚合鄰居節(jié)點(diǎn)的特征信息,與圖計(jì)算應(yīng)用相似.這一過程的執(zhí)行在很大程度上依賴于圖結(jié)構(gòu)的分布特征.而現(xiàn)實(shí)世界的圖往往具有極高的稀疏性,其鄰接矩陣的稀疏度高達(dá)99%[104-105],且圖中節(jié)點(diǎn)之間的連接分布不規(guī)則,每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的數(shù)量和位置均不固定.上述行為和特性導(dǎo)致圖神經(jīng)網(wǎng)絡(luò)的圖聚合階段存在大量的動態(tài)計(jì)算與不規(guī)則訪存,受內(nèi)存約束.

2)圖更新階段.在此階段,圖神經(jīng)網(wǎng)絡(luò)對圖中每個(gè)節(jié)點(diǎn)進(jìn)行特征向量的神經(jīng)網(wǎng)絡(luò)變換和更新,與傳統(tǒng)神經(jīng)網(wǎng)絡(luò)應(yīng)用相似.這一過程中,不同節(jié)點(diǎn)共享相同的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu),且每層中神經(jīng)元之間的連接也相同,因此圖更新階段具有靜態(tài)的計(jì)算和規(guī)則的訪存,受計(jì)算約束.

Table 2 Execution Behaviors in GNNs[9]表2 圖神經(jīng)網(wǎng)絡(luò)執(zhí)行行為總結(jié)[9]

3.2 通用平臺的不足

依據(jù)文獻(xiàn)[106]所述,不同的圖神經(jīng)網(wǎng)絡(luò)模型在圖聚合和圖更新階段具有相似的執(zhí)行特性,因此本節(jié)以圖卷積神經(jīng)網(wǎng)絡(luò)的量化數(shù)據(jù)為例說明通用平臺加速的不足之處.

表3列出了COLLAB[107]數(shù)據(jù)集在CPU(Intel Xeon CPU E5-2680 v3)平臺上執(zhí)行GCN模型的結(jié)果,表4列出了Reddit[107]數(shù)據(jù)集在GPU(Nvidia GPU V100)平臺執(zhí)行GraphSAGE模型的結(jié)果,上述實(shí)驗(yàn)均通過Py Torch Geometric實(shí)現(xiàn).從表3中可以發(fā)現(xiàn),圖聚合階段中,每個(gè)操作都比圖更新階段從DRAM訪問更多的數(shù)據(jù),從而導(dǎo)致更高的DRAM訪問能耗.源于每個(gè)節(jié)點(diǎn)鄰居的高度隨機(jī)性,在圖聚合階段中L2和L3緩存的每千條指令缺失次數(shù)(miss-predicts per kilo-instructions,MPKI)極高,同時(shí)也導(dǎo)致無法預(yù)測特征向量的訪存地址.不規(guī)則訪存使得傳統(tǒng)通用處理器的數(shù)據(jù)預(yù)取機(jī)制失效[108].圖更新階段中,每個(gè)操作僅需要從DRAM訪問少量數(shù)據(jù),這是因?yàn)榫仃囅蛄砍说挠?jì)算量很大且多層感知機(jī)的權(quán)重矩陣在節(jié)點(diǎn)之間廣泛共享.然而在CPU上對共享數(shù)據(jù)的復(fù)制和線程之間的同步,執(zhí)行時(shí)間開銷最多可達(dá)36%.對于GPU平臺上,也有類似的結(jié)果(如表4所示).

Table 3 Execution Behaviors of GNNs on CPU[9]表3 圖神經(jīng)網(wǎng)絡(luò)執(zhí)行行為在CPU上的結(jié)果[9]

Table 4 Execution Behaviors of GNNs on GPU[109]表4 圖神經(jīng)網(wǎng)絡(luò)執(zhí)行行為在GPU上的結(jié)果[109]

圖神經(jīng)網(wǎng)絡(luò)的混合執(zhí)行行為,導(dǎo)致通用平臺均無法為圖神經(jīng)網(wǎng)絡(luò)的執(zhí)行提供專屬且高效的算力.對于CPU平臺來說,它們?nèi)鄙儆?jì)算資源,并且圖聚合階段的遍歷不規(guī)則性會導(dǎo)致頻繁的數(shù)據(jù)替換.對于GPU來說,其結(jié)構(gòu)本質(zhì)上是面向類似神經(jīng)網(wǎng)絡(luò)的具有規(guī)則執(zhí)行行為且計(jì)算密集型的應(yīng)用進(jìn)行加速[110],缺少應(yīng)對不規(guī)則性的能力.

3.3 傳統(tǒng)應(yīng)用加速結(jié)構(gòu)的不足

通用平臺下的圖神經(jīng)網(wǎng)絡(luò)框架對圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的加速空間有限,設(shè)計(jì)專用的加速結(jié)構(gòu)就成為了一種順應(yīng)而生的趨勢.由于為特定領(lǐng)域設(shè)計(jì)專用的加速結(jié)構(gòu)可以為特定的應(yīng)用量身定制計(jì)算單元和內(nèi)存層次結(jié)構(gòu),因此其成為解決現(xiàn)有架構(gòu)執(zhí)行效率低下的有效且普遍的方案.

然而面向傳統(tǒng)圖計(jì)算和神經(jīng)網(wǎng)絡(luò)應(yīng)用的加速結(jié)構(gòu)無法高效地應(yīng)對圖神經(jīng)網(wǎng)絡(luò).對于圖計(jì)算加速結(jié)構(gòu)而言,它們主要面向動態(tài)稀疏計(jì)算和不規(guī)則訪存進(jìn)行設(shè)計(jì),且處理的圖結(jié)構(gòu)中節(jié)點(diǎn)特征屬性很小,因此不具備加速圖更新階段密集計(jì)算的能力,并且無法有效挖掘圖更新階段的規(guī)則性和較好的空間局部性.對于神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)而言,它們主要面向靜態(tài)密集計(jì)算和規(guī)則訪存進(jìn)行設(shè)計(jì),盡管已有一些工作將神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)向稀疏矩陣運(yùn)算進(jìn)行擴(kuò)展,但圖神經(jīng)網(wǎng)絡(luò)所處理圖的稀疏度至少比傳統(tǒng)神經(jīng)網(wǎng)絡(luò)所處理的圖高2倍[105].因此神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)不具備應(yīng)對不規(guī)則訪存和不規(guī)則計(jì)算的能力,無法高效執(zhí)行圖神經(jīng)網(wǎng)絡(luò)的圖聚合階段.另外,圖計(jì)算加速結(jié)構(gòu)和神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)均只能針對圖神經(jīng)網(wǎng)絡(luò)中的單一階段進(jìn)行加速,無法融合2個(gè)階段的執(zhí)行[9],不足以應(yīng)對圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的加速需求.

3.4 圖神經(jīng)網(wǎng)絡(luò)加速設(shè)計(jì)挑戰(zhàn)

通用平臺及面向傳統(tǒng)圖計(jì)算和神經(jīng)網(wǎng)絡(luò)應(yīng)用的加速結(jié)構(gòu)處理圖神經(jīng)網(wǎng)絡(luò)效率低下的原因總結(jié)如圖4所示.已有處理器結(jié)構(gòu)的效率低下使得為圖神經(jīng)網(wǎng)絡(luò)專門設(shè)計(jì)相應(yīng)的加速結(jié)構(gòu)勢在必行.

Fig.4 Reasons for low efficiency in existing processors圖4 現(xiàn)有處理器結(jié)構(gòu)效率低下原因總結(jié)

然而由于圖神經(jīng)網(wǎng)絡(luò)混合執(zhí)行行為的特殊性,面向圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的加速結(jié)構(gòu)設(shè)計(jì)仍然面臨諸多挑戰(zhàn),挑戰(zhàn)主要可以分為計(jì)算和訪存2個(gè)方面.計(jì)算方面:圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)需要同時(shí)能夠高效應(yīng)對不規(guī)則和密集規(guī)則型計(jì)算.由于圖中節(jié)點(diǎn)具有極高的不規(guī)則性并服從冪律分布,圖聚合階段對鄰居節(jié)點(diǎn)的遍歷會導(dǎo)致嚴(yán)重的負(fù)載不均衡,為圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)的設(shè)計(jì)帶來更多挑戰(zhàn).另外,圖神經(jīng)網(wǎng)絡(luò)的執(zhí)行過程中還潛藏著不同級別的并行性待加速結(jié)構(gòu)挖掘.訪存方面:圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)需要同時(shí)能夠高效應(yīng)對不規(guī)則和規(guī)則的粗粒度訪存以及高帶寬需求.同時(shí)如何充分地進(jìn)行圖數(shù)據(jù)復(fù)用也為圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)的設(shè)計(jì)提出更高要求.

4 圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)分類方案

自2020年全球首款面向圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的專用加速結(jié)構(gòu)Hy GCN[9]發(fā)表后,短時(shí)間內(nèi)學(xué)術(shù)界已在該領(lǐng)域產(chǎn)出了多篇不同的硬件加速成果.這些工作在所支持的圖神經(jīng)網(wǎng)絡(luò)算法類別、所應(yīng)用的階段、硬件加速平臺、關(guān)鍵優(yōu)化技術(shù)等方面有所差異,表5列出了現(xiàn)有工作的相關(guān)信息對比.

1)支持算法方面

通過表5可以看到,目前現(xiàn)有工作大多針對單一種類圖神經(jīng)網(wǎng)絡(luò)算法進(jìn)行加速,尤其以圖卷積神經(jīng)網(wǎng)絡(luò)GCNs居多.僅Auten等人,Deep Burning-GL,EnGN和Cambricon-G的研究工作能夠支持多種類的圖神經(jīng)網(wǎng)絡(luò)算法.

2)支持階段方面

現(xiàn)有工作大多只能支持對圖神經(jīng)網(wǎng)絡(luò)的訓(xùn)練或推斷中的單一階段進(jìn)行加速,僅有Cambricon-G同時(shí)支持2個(gè)階段,Graph ACT面向訓(xùn)練過程,其余工作均只關(guān)注推斷階段.

3)加速平臺方面

現(xiàn)有工作通常采用CPU-FPGA的異構(gòu)平臺、ASIC平臺或存內(nèi)計(jì)算平臺實(shí)現(xiàn)硬件加速結(jié)構(gòu)搭建.

FPGA是現(xiàn)場可編程邏輯門陣列(field programmable gate array),設(shè)計(jì)人員通過FPGA配置文件定義專用的邏輯電路,實(shí)現(xiàn)所需的硬件功能,具有較強(qiáng)的可配置性和靈活性.CPU-FPGA的異構(gòu)平臺,可以使CPU和FPGA平臺各取所長,分工執(zhí)行圖神經(jīng)網(wǎng)絡(luò)應(yīng)用中的不同步驟,并相互配合達(dá)到更好的效果.

ASIC為專用集成電路(application specific integrated circuit),用戶能夠根據(jù)不同的應(yīng)用場景和用途定制專用的硬件結(jié)構(gòu).ASIC可為設(shè)計(jì)人員提供豐富的計(jì)算和存儲資源.與FPGA相比,ASIC適合復(fù)雜度更高、規(guī)模更大的硬件結(jié)構(gòu)設(shè)計(jì).

存內(nèi)計(jì)算(processing in memory,PIM)是解決硬件結(jié)構(gòu)設(shè)計(jì)中存儲墻(memory wall)問題的有力方案之一.存內(nèi)計(jì)算通過修改內(nèi)存相關(guān)的電路設(shè)計(jì)或引入新型存儲等方式,在內(nèi)存附近或在內(nèi)存之中進(jìn)行計(jì)算,能夠有效拉近計(jì)算單元與所需數(shù)據(jù)間的距離,有助于為硬件結(jié)構(gòu)提供更高的訪存帶寬.

4)關(guān)鍵優(yōu)化技術(shù)方面

針對第3節(jié)介紹的圖神經(jīng)網(wǎng)絡(luò)執(zhí)行行為帶來的加速挑戰(zhàn),現(xiàn)有工作的關(guān)鍵優(yōu)化技術(shù)可以歸納為計(jì)算、片上訪存和片外訪存這3個(gè)層次.

①圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)在計(jì)算層次主要的優(yōu)化目標(biāo)是充分挖掘并行性,常見的優(yōu)化方向包括負(fù)載均衡、脈動陣列、減少冗余計(jì)算與降低計(jì)算復(fù)雜度等.

②目前片上訪存層次主要的優(yōu)化目標(biāo)是深入挖掘粗粒度訪存數(shù)據(jù)的空間局部性和時(shí)間局部性,盡可能減少片上數(shù)據(jù)的頻繁替換.主要的解決思路是采用大容量片上存儲和對圖數(shù)據(jù)進(jìn)行數(shù)據(jù)重排.另外還有新興方法通過優(yōu)化模型壓縮圖神經(jīng)網(wǎng)絡(luò)的模型參數(shù)數(shù)據(jù),降低對片上存儲空間的需求.

③現(xiàn)有的解決片外訪存層次挑戰(zhàn)的主要思路是基于特定的圖數(shù)據(jù)劃分方法提高預(yù)取效率和數(shù)據(jù)重用率,利用稀疏性消除、動態(tài)訪存調(diào)度、數(shù)據(jù)結(jié)構(gòu)重組提高帶寬利用率,通過操作融合減少訪存帶寬需求等.

Table 5 Comparison Among Existing GNN Acceleration Architectures表5 現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)對比

大多數(shù)面向圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的加速結(jié)構(gòu)均從上述3方面進(jìn)行了針對性優(yōu)化,詳細(xì)對比參照表5.由于關(guān)鍵優(yōu)化技術(shù)是加速結(jié)構(gòu)設(shè)計(jì)的核心內(nèi)容,為使相關(guān)研究人員能夠受到啟發(fā),本文將以不同層次的關(guān)鍵優(yōu)化技術(shù)為分類標(biāo)準(zhǔn),在接下來的2節(jié)對已有工作展開詳細(xì)介紹.

5 圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)整體分析

本節(jié)對目前已有的圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)的設(shè)計(jì)核心進(jìn)行總結(jié),并從整體設(shè)計(jì)的角度,對加速結(jié)構(gòu)如何融合不同層次的關(guān)鍵優(yōu)化技術(shù)達(dá)到預(yù)期加速效果進(jìn)行介紹。各層次的優(yōu)化技術(shù)將在第6節(jié)中進(jìn)行具體剖析。

由于圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)面臨計(jì)算和訪存2方面的挑戰(zhàn),因此高效的圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)通常都包含不同層次的優(yōu)化思路和優(yōu)化技術(shù).并且,各個(gè)層次的關(guān)鍵優(yōu)化技術(shù)之間相輔相成,甚至融為一體為同一個(gè)設(shè)計(jì)核心服務(wù).現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)的整體設(shè)計(jì)核心可歸納為表6:

Table 6 Core Design of Existing GNN Acceleration Architectures表6 現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)設(shè)計(jì)核心

從整體設(shè)計(jì)核心出發(fā),可將現(xiàn)有工作分為混合加速結(jié)構(gòu)和一體化加速結(jié)構(gòu)兩大類.同時(shí),這2類加速結(jié)構(gòu)均配合不同層次的關(guān)鍵優(yōu)化技術(shù).各項(xiàng)關(guān)鍵優(yōu)化技術(shù)能夠應(yīng)對圖神經(jīng)網(wǎng)絡(luò)在各個(gè)層次面臨的挑戰(zhàn),同時(shí)又相輔相成,共同實(shí)現(xiàn)圖神經(jīng)網(wǎng)絡(luò)的高效執(zhí)行.

5.1 混合加速結(jié)構(gòu)

為了更有效地針對不同執(zhí)行行為進(jìn)行優(yōu)化,混合加速結(jié)構(gòu)將圖神經(jīng)網(wǎng)絡(luò)算法解耦合為多個(gè)執(zhí)行階段,分別設(shè)計(jì)與不同階段執(zhí)行行為相匹配的計(jì)算單元和存儲單元,從而有針對性地對不同階段進(jìn)行加速和提升執(zhí)行效率.

如圖5所示,Hy GCN[9]分別為圖聚合階段和圖更新階段設(shè)計(jì)了Aggregation加速引擎和Combination加速引擎,并進(jìn)行混合結(jié)構(gòu)的協(xié)調(diào)控制.同時(shí),HyGCN在計(jì)算層次分別對Aggregation和Combination加速引擎設(shè)計(jì)負(fù)載均衡策略以及引入脈動陣列,挖掘運(yùn)算并行性并提升運(yùn)算效率.在訪存層次,Hy GCN通過精巧設(shè)置的大容量片上緩存、滑動收縮窗口消除數(shù)據(jù)稀疏以及動態(tài)調(diào)度訪存等策略提升片外訪存效率與帶寬利用率.訪存層次的優(yōu)化為計(jì)算單元的數(shù)據(jù)持續(xù)供給提供保障,從而有力支撐計(jì)算層次的優(yōu)化技術(shù)更好地發(fā)揮作用.

Graph ACT[111]、文 獻(xiàn)[112]和GCNAR[113]在CPU和FPGA的異構(gòu)系統(tǒng)上執(zhí)行圖神經(jīng)網(wǎng)絡(luò),使CPU和FPGA都能夠分別對所擅長的執(zhí)行行為進(jìn)行加速.如圖6所示,Graph ACT在CPU上主要執(zhí)行訪存密集型或具有不規(guī)則執(zhí)行行為的操作,例如Sample操作、去除冗余Aggregate操作的預(yù)處理、計(jì)算損失等;在FPGA上主要執(zhí)行計(jì)算密集型操作,例如正向以及反向傳輸?shù)腁ggregate操作和Combine操作.同時(shí)Graph ACT也在計(jì)算和訪存層次上提出了多種優(yōu)化技術(shù).Graph ACT在計(jì)算層次上,采用脈動陣列來挖掘運(yùn)算并行性,提高運(yùn)算效率;在訪存層次上,通過設(shè)置不同的片上存儲器盡可能多地存儲計(jì)算所需的各類數(shù)據(jù),提升數(shù)據(jù)復(fù)用率,使計(jì)算單元能夠更快獲取熱點(diǎn)數(shù)據(jù).另外,預(yù)處理過程中的稀疏性消除機(jī)制能夠有效減少圖中的冗余邊,從而降低冗余的計(jì)算量和片外訪存量,也即同時(shí)在計(jì)算和訪存2個(gè)層次產(chǎn)生優(yōu)化效果.

Fig.5 Hybrid architecture of Hy GCN[9]圖5 HyGCN的混合加速結(jié)構(gòu)[9]

Fig.6 Heterogenous pipeline of CPU-FPGA platform in Graph ACT[111]圖6 Graph ACT的CPU-FPGA異構(gòu)流水[111]

FPGAN[114]通過軟硬件協(xié)同優(yōu)化的方式在FPGA平臺上加速圖注意力網(wǎng)絡(luò)的執(zhí)行.硬件方面,FPGAN設(shè)計(jì)特征聚合模塊和線性轉(zhuǎn)換模塊來分別執(zhí)行圖注意力網(wǎng)絡(luò)的圖聚合階段和圖更新階段.軟件方面,FPGA通過轉(zhuǎn)換圖注意力網(wǎng)絡(luò)的執(zhí)行過程,在計(jì)算層次降低復(fù)雜度;通過壓縮權(quán)重、操作融合的方式在訪存層次降低對片上存儲空間及片外帶寬的需求.訪存層次的優(yōu)化配合復(fù)雜度降低的網(wǎng)絡(luò)模型,能夠?yàn)橛?jì)算單元更快更多地提供操作數(shù)據(jù).另外,軟件方面的優(yōu)化技術(shù)幫助圖注意力網(wǎng)絡(luò)適配定制的硬件處理模塊,協(xié)同提升執(zhí)行效率和性能.

5.2 一體化加速結(jié)構(gòu)

與混合加速結(jié)構(gòu)相對的,一體化加速結(jié)構(gòu)對所有的計(jì)算資源進(jìn)行統(tǒng)一調(diào)度,用于執(zhí)行圖神經(jīng)網(wǎng)絡(luò)的各個(gè)階段,同時(shí)配合不同層次的關(guān)鍵優(yōu)化技術(shù),整體加速圖神經(jīng)網(wǎng)絡(luò)的執(zhí)行過程.

AWB-GCN[104]以稀疏-密集矩陣乘(Sp MM)的形式執(zhí)行頻域圖卷積神經(jīng)網(wǎng)絡(luò),并將Sp MM的運(yùn)算操作送入統(tǒng)一結(jié)構(gòu)的PE中.同時(shí),AWB-GCN在計(jì)算層次設(shè)計(jì)運(yùn)行時(shí)的負(fù)載調(diào)度機(jī)制以實(shí)現(xiàn)動態(tài)均衡負(fù)載,在訪存層次輔以大規(guī)模片上存儲器及圖矩陣分塊等方式提升數(shù)據(jù)局部性,減少片外訪存帶寬需求,為計(jì)算單元復(fù)用片上數(shù)據(jù)提供更優(yōu)的支持.

En GN[116]加速結(jié)構(gòu)中包含一組規(guī)模為128×16的同構(gòu)處理單元(processing elements,PE)陣列.如圖7所示,PE之間以Ring-Edge-Reduce(RER)的拓?fù)湫问较噙B接,每一列的PE用于執(zhí)行鄰居聚合操作,而每一行的PE用于處理節(jié)點(diǎn)的特征屬性.統(tǒng)一的加速結(jié)構(gòu)之上,En GN在計(jì)算層次通過靈活選擇圖神經(jīng)網(wǎng)絡(luò)每層的階段執(zhí)行順序減少冗余計(jì)算,在訪存層次采用圖分塊及多層次片上存儲器等方式降低片外訪存需求,不同層次共同應(yīng)對圖神經(jīng)網(wǎng)絡(luò)執(zhí)行行為所帶來的不同挑戰(zhàn).

Fig.7 Processing element array in EnGN[116]圖7 EnGN的處理單元陣列[116]

Cambricon-G[118]加速結(jié)構(gòu)的運(yùn)算由一個(gè)3D形式的立方體加速引擎(cuboid engine,CE)完成.CE中包含多個(gè)同構(gòu)的節(jié)點(diǎn)處理單元(vertex processing units,VPUs),不同的VPU組織為2D脈動陣列的形式,用于處理以鄰接立方體形式存儲的圖數(shù)據(jù).在計(jì)算層次,Cambricon-G通過VPU組成的脈動陣列挖掘數(shù)據(jù)局部性和運(yùn)算并行性;在訪存層次,Cambricon-G通過對鄰接立方體進(jìn)行劃分,輔以混合的片上存儲系統(tǒng),實(shí)現(xiàn)多維度的數(shù)據(jù)重用,降低訪存帶寬需求.整體而言,Cambricon-G通過訪存層次的精細(xì)分塊,將子塊數(shù)據(jù)送入VPU陣列中進(jìn)行運(yùn)算,實(shí)現(xiàn)高效加速圖神經(jīng)網(wǎng)絡(luò)的效果.另外,靈活的分塊策略和拓?fù)涓兄狢ache助力Cambricon-G有效應(yīng)對動態(tài)變化的圖.

6 圖神經(jīng)網(wǎng)絡(luò)關(guān)鍵優(yōu)化技術(shù)

本節(jié)將從計(jì)算、片上訪存與片外訪存這3方面對現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)的關(guān)鍵優(yōu)化技術(shù)進(jìn)行分類介紹.

6.1 計(jì)算優(yōu)化層次

混合的執(zhí)行行為給圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)在計(jì)算層次的結(jié)構(gòu)設(shè)計(jì)與優(yōu)化帶來了巨大挑戰(zhàn).從關(guān)鍵優(yōu)化技術(shù)角度看,圖神經(jīng)網(wǎng)絡(luò)芯片在計(jì)算層次主要的優(yōu)化目標(biāo)是充分挖掘并行性和提高計(jì)算部件的利用效率,常見的優(yōu)化方向包括負(fù)載均衡、脈動陣列、減少冗余計(jì)算及降低計(jì)算復(fù)雜度等,下面將依次對其進(jìn)行介紹.

1)負(fù)載均衡

由于圖節(jié)點(diǎn)分布的不規(guī)則性,每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)個(gè)數(shù)各不相同,使得在圖神經(jīng)網(wǎng)絡(luò)的圖聚合階段中,每個(gè)節(jié)點(diǎn)的計(jì)算任務(wù)量差異巨大,導(dǎo)致嚴(yán)重的負(fù)載不均衡.如圖5所示,HyGCN[9]設(shè)計(jì)Aggregation加速引擎,其中包含多個(gè)SIMD(single instruction multiple data)計(jì)算單元和邊調(diào)度器.邊調(diào)度器會依據(jù)邊表中每個(gè)節(jié)點(diǎn)對應(yīng)的鄰居節(jié)點(diǎn)信息,將鄰居節(jié)點(diǎn)進(jìn)行聚合,以特征向量中的元素為單位,分配到SIMD計(jì)算單元的不同通道(lane)中,從而均衡負(fù)載,并能夠更加充分地開發(fā)邊級并行性和節(jié)點(diǎn)內(nèi)部的并行性.

如圖8所示,GCNAR[113]提出的加速結(jié)構(gòu)中包含多個(gè)FPGA節(jié)點(diǎn),該工作將DAGCN圖神經(jīng)網(wǎng)絡(luò)模型[119]中的注意力圖卷積(attention graph convolution,AGC)層均衡分配到各個(gè)FPGA節(jié)點(diǎn)中,也即每個(gè)FPGA節(jié)點(diǎn)處理相同個(gè)數(shù)的圖卷積層,從而保證每個(gè)FPGA節(jié)點(diǎn)的負(fù)載均衡.

Fig.8 CPU-multi-FPGA architecture of GCNAR[113]圖8 GCNAR[113]的CPU-多-FPGA結(jié)構(gòu)

AWB-GCN[104]基于稀疏矩陣設(shè)計(jì)了加速頻域圖卷積神經(jīng)網(wǎng)絡(luò)的加速結(jié)構(gòu),并利用運(yùn)行時(shí)動態(tài)負(fù)載調(diào)度機(jī)制實(shí)現(xiàn)稀疏矩陣不均衡負(fù)載重新分配.運(yùn)行時(shí)動態(tài)負(fù)載調(diào)度機(jī)制包括3種運(yùn)行時(shí)工作負(fù)載重新平衡的技術(shù):負(fù)載平滑分配(distribution smoothing)技術(shù)、負(fù)載遠(yuǎn)程交換(remote switching)技術(shù)以及矩陣行重映射(row remapping)技術(shù).負(fù)載平滑分配技術(shù)在每輪計(jì)算過程中,實(shí)現(xiàn)鄰居處理單元的負(fù)載均勻化.AWB-GCN通過跟蹤處理單元的任務(wù)隊(duì)列(task queues,TQs)中的待處理任務(wù)數(shù)量,來監(jiān)控運(yùn)行時(shí)的計(jì)算單元利用率信息,進(jìn)而將待處理任務(wù)量大的處理單元負(fù)載分擔(dān)給較為空閑的鄰居處理單元.負(fù)載遠(yuǎn)程交換技術(shù)通過在過載和較空閑處理單元(即利用率在波峰和波谷的處理單元)之間部分或完全交換負(fù)載的方式解決負(fù)載局部集群問題(regional clustering).AWB-GCN將包含過多非零元素(出入度極大)的行稱為“邪惡行”(evil row),該行的負(fù)載無法通過上述2種技術(shù)在鄰居間完美消化.矩陣行重映射技術(shù)在遠(yuǎn)程交換的基礎(chǔ)上,將邪惡行負(fù)載進(jìn)行重新映射.自動協(xié)調(diào)器負(fù)責(zé)判定是否需要進(jìn)行行重映射,若需要,則將邪惡行的負(fù)載分配到最空閑的處理單元中,再通過鄰居處理單元進(jìn)行負(fù)載分擔(dān),從而進(jìn)一步實(shí)現(xiàn)全局負(fù)載均衡.通過以上3種策略,AWB-GCN連續(xù)監(jiān)控稀疏矩陣實(shí)時(shí)運(yùn)行信息,動態(tài)調(diào)整處理單元之間的負(fù)載分配,并在效果收斂后復(fù)用已取得的理想配置,解決GCN中大規(guī)模冪律分布結(jié)構(gòu)數(shù)據(jù)導(dǎo)致的處理單元之間負(fù)載不均衡的問題.

GNN-PIM[117]加速結(jié)構(gòu)提出了一種可重配的計(jì)算節(jié)點(diǎn),可配置為對圖節(jié)點(diǎn)進(jìn)行處理的計(jì)算節(jié)點(diǎn)vertex node或?qū)呥M(jìn)行處理的計(jì)算節(jié)點(diǎn)edge node.GNN-PIM根據(jù)圖的拓?fù)浞植记闆r,靈活地對計(jì)算節(jié)點(diǎn)進(jìn)行配置,在一定程度上均衡負(fù)載.

2)脈動陣列

對于圖神經(jīng)網(wǎng)絡(luò)的圖更新階段的規(guī)則執(zhí)行行為,受到TPU[120]設(shè)計(jì)的啟發(fā),目前已有的圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)常采用脈動陣列來執(zhí)行更新操作.

Hy GCN[9]的Combination加速引擎包含多個(gè)由脈動陣列組成的脈動模塊,脈動模塊可以在獨(dú)立執(zhí)行和合作執(zhí)行這2種模式下工作.在獨(dú)立執(zhí)行模式中,每個(gè)脈動模塊獨(dú)立完成一小組節(jié)點(diǎn)的矩陣向量乘(matrix-vector multiplication,MVM)操作.脈動陣列的一行用來完成同一節(jié)點(diǎn)特征向量的神經(jīng)網(wǎng)絡(luò)變換操作,每個(gè)脈沖模塊內(nèi)部的脈動陣列共享權(quán)重?cái)?shù)據(jù).在合作執(zhí)行模式中,Combination加速引擎中的所有脈動模塊聯(lián)合工作,對更多數(shù)量的節(jié)點(diǎn)同時(shí)進(jìn)行神經(jīng)網(wǎng)絡(luò)變換操作,并共享權(quán)重?cái)?shù)據(jù).這2種模式都能夠有效挖掘圖更新階段中的MVM并行性以及節(jié)點(diǎn)間的運(yùn)算并行性,同時(shí)還能夠提升權(quán)重?cái)?shù)據(jù)的重用率.

與Hy GCN類似,Graph ACT[111]、文獻(xiàn)[112]、GCNAR[113]、DeepBurning-GL[115]及Cambricon-G[118]也同樣采用脈動陣列在圖神經(jīng)網(wǎng)絡(luò)的圖更新階段,對特征和權(quán)重進(jìn)行矩陣運(yùn)算,有效挖掘運(yùn)算并行性,提高運(yùn)算效率.

3)減少冗余計(jì)算

Graph ACT[111]通過預(yù)處理的方式,提前完成圖中復(fù)用率較高的部分運(yùn)算,從而去除鄰居節(jié)點(diǎn)的冗余歸約操作,能夠有效減少計(jì)算量以及CPU與FPGA之間的通信開銷.文獻(xiàn)[112]同樣采用預(yù)處理的方式,通過圖稀疏化操作,合并公共鄰居節(jié)點(diǎn),消除高出/入度節(jié)點(diǎn)的邊計(jì)算,其策略與Graph ACT異曲同工.其不同點(diǎn)在于,Graph ACT應(yīng)用于圖神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程,文獻(xiàn)[112]主要應(yīng)用于推斷過程,由于推斷過程中整個(gè)圖的冗余會比訓(xùn)練過程的mini-batch子圖更多,因此該策略在文獻(xiàn)[112]中的冗余消除效果和計(jì)算優(yōu)化水平會更高.GCNAR[113]通過預(yù)處理,消除圖鄰接矩陣中全零的行,并重新組織鄰接矩陣,從而減少算法的計(jì)算量.

另外,文獻(xiàn)[112]和EnGN[116]分析圖神經(jīng)網(wǎng)絡(luò)的編程模型,同時(shí)為每一圖神經(jīng)網(wǎng)絡(luò)層實(shí)現(xiàn)2種計(jì)算順序,并能夠根據(jù)前后層的特征維度判斷采用哪種執(zhí)行模式,從而有效降低計(jì)算量.第1種計(jì)算順序是先執(zhí)行圖聚合階段后執(zhí)行圖更新階段,第2種計(jì)算順序是先執(zhí)行圖更新階段后執(zhí)行圖聚合階段.

4)降低計(jì)算復(fù)雜度

FPGAN[114]在不損失精確度的情況下,通過簡化模型的方法,降低圖注意力網(wǎng)絡(luò)的計(jì)算復(fù)雜度,減少對FPGA中數(shù)字信號處理器(digital signal processors,DSPs)計(jì)算資源的需求,從而提升整體運(yùn)算性能和效能.具體而言,首先,FPGAN將原模型中的激活函數(shù)leakyrelu簡化為relu.其次通過特征量化(feature quantification)步驟,將每層的輸入特征和激活因子(activation)從浮點(diǎn)域轉(zhuǎn)入定點(diǎn)域.然后,FPGAN通過直接檢索查找表(lookup table,LUTs)的方式近似模擬Soft Max函數(shù)中的exp操作.經(jīng)過以上步驟,FPGAN可將圖注意力模型中的所有浮點(diǎn)乘法操作轉(zhuǎn)換為移位操作,有效降低了計(jì)算復(fù)雜度.另外,FPGAN通過引入膨脹系數(shù)(expansion coefficient)等方法保證模型的修改不會影響最終的推斷精確度.在該優(yōu)化方法的幫助下,單個(gè)計(jì)算單元僅需要少量硬件資源即可實(shí)現(xiàn),進(jìn)而削弱圖注意力模型的執(zhí)行性能對DSP的依賴,提高FPGA的資源利用率,提升模型執(zhí)行速度.

6.2 片上訪存優(yōu)化層次

圖神經(jīng)網(wǎng)絡(luò)中節(jié)點(diǎn)的特征屬性為高維數(shù)據(jù),因此對節(jié)點(diǎn)屬性的訪問為粗粒度的不規(guī)則訪問,這也是圖神經(jīng)網(wǎng)絡(luò)與傳統(tǒng)圖計(jì)算執(zhí)行過程的典型區(qū)別之一.不規(guī)則粗粒度訪存導(dǎo)致的片上存儲Cache命中率低的問題,為圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)的設(shè)計(jì)在片上存儲層次帶來極大挑戰(zhàn).解決這一挑戰(zhàn)的主要思路分為2種:1)采用大容量的片上存儲,并配合批量處理與數(shù)據(jù)分割等技術(shù);2)對圖數(shù)據(jù)進(jìn)行數(shù)據(jù)重排.這2種解決思路的目的是一致的,均為深入挖掘粗粒度訪存數(shù)據(jù)的空間局部性和時(shí)間局部性,盡可能減少片上數(shù)據(jù)的頻繁替換.另外還有新興方法通過優(yōu)化圖神經(jīng)網(wǎng)絡(luò)模型、壓縮權(quán)重等模型參數(shù)數(shù)據(jù),降低對片上存儲空間的需求.下面將依次對上述方法進(jìn)行介紹.

1)大容量片上存儲

選取大容量的片上存儲是最為常見的片上存儲層次優(yōu)化策略.HyGCN[9]、文獻(xiàn)[105]、Graph ACT[111]、AWB-GCN[104]、文獻(xiàn)[112]、EnGN[116]、文獻(xiàn)[114]、DeepBurning-GL[115]及Cambricon-G[118]等均采用該方法,并配合相應(yīng)的批量處理與數(shù)據(jù)分割等技術(shù),降低圖神經(jīng)網(wǎng)絡(luò)中被不規(guī)則粗粒度訪存的數(shù)據(jù)在片上和片外間頻繁替換的次數(shù).

如圖5所示,Hy GCN[9]為了挖掘圖神經(jīng)網(wǎng)絡(luò)中涉及的各種數(shù)據(jù)的局部性,基于eDRAM(embedded DRAM)為具有不同訪存模式的數(shù)據(jù)設(shè)計(jì)了不同的緩存(buffer).HyGCN通過邊buffer來存儲Aggregation加速引擎所需的邊數(shù)據(jù),挖掘邊表的空間局部性;通過輸入buffer來存儲每層節(jié)點(diǎn)的輸入特征向量;通過權(quán)重buffer來存儲圖更新階段所需的權(quán)重矩陣,從而挖掘其時(shí)間局部性;通過輸出buffer來合并每層待寫回的節(jié)點(diǎn)特征向量.上述緩存均利用雙緩沖(double buffer)技術(shù)來掩蓋訪存延遲.另外,HyGCN還在Aggregation和Combination加速引擎之間添加Aggregation緩存,用于存儲圖聚合階段的中間數(shù)據(jù),Aggregation緩存分為2個(gè)部分來實(shí)現(xiàn)乒乓緩沖(ping-pong buffer)機(jī)制,從而提升加速引擎之間的并行度.

Fig.9 Module architecture of ref[105]圖9 文獻(xiàn)[105]各模塊結(jié)構(gòu)圖

文獻(xiàn)[105]分別在其加速結(jié)構(gòu)的不同模塊中添加片上存儲來緩存不同類型的數(shù)據(jù),從而挖掘數(shù)據(jù)局部性.如圖9所示,具體實(shí)施方案為:圖處理單元(graph PE,GPE)中設(shè)置片上存儲器來保存應(yīng)用執(zhí)行過程中的狀態(tài)信息.在DNN隊(duì)列(DNN queue,DNQ)中設(shè)置2塊存儲區(qū)域,其中大容量片上存儲器(62 KB)負(fù)責(zé)暫存隊(duì)列數(shù)據(jù)和延遲準(zhǔn)備信息,小容量片上存儲器(2 KB)負(fù)責(zé)存儲路由相應(yīng)的終點(diǎn)信息,大小容量片上存儲器相互配合,為DNN加速器和不同的DNN模型提供運(yùn)行支持.與DNQ相類似的,在聚合器(aggregator,AGG)中添加一對不同容量的片上存儲器,其中大容量片上存儲器(62 KB)負(fù)責(zé)暫存聚合過程的中間結(jié)果,小容量存儲器負(fù)責(zé)存儲每個(gè)聚合節(jié)點(diǎn)的目的地址信息,用于輔助控制邏輯.

Graph ACT[111]利用FPGA上大容量的片上存儲器BRAM來存儲圖神經(jīng)網(wǎng)絡(luò)應(yīng)用訓(xùn)練過程中的各類數(shù)據(jù),具體包括:節(jié)點(diǎn)的特征向量、子圖的拓?fù)鋽?shù)據(jù)、預(yù)處理數(shù)據(jù)、聚合過程的中間結(jié)果數(shù)據(jù)、梯度信息、模型權(quán)重?cái)?shù)據(jù)、優(yōu)化器輔助信息等.賽靈思Alveo開發(fā)板中的一塊BRAM(36 b×1 K),可以存儲1 K個(gè)不同節(jié)點(diǎn)的特征數(shù)據(jù)(32 b浮點(diǎn)).同時(shí),由于圖神經(jīng)網(wǎng)絡(luò)的圖節(jié)點(diǎn)特征數(shù)據(jù)所需空間巨大,片上存儲空間無法完全容納,因此Graph ACT采用文獻(xiàn)[121]中的方法,通過對圖進(jìn)行采樣獲取minibatch,此方法獲取的mini-batch包含子圖在當(dāng)前層的完整負(fù)載.與完整的負(fù)載相比,mini-batch的數(shù)據(jù)信息能夠更好地適應(yīng)有限的片上存儲空間.

文獻(xiàn)[112]首先設(shè)計(jì)數(shù)據(jù)分割策略,在預(yù)處理的過程中將大規(guī)模圖分割為若干小的鄰接矩陣,通過適當(dāng)?shù)膮?shù)選取,每個(gè)數(shù)據(jù)子塊都能夠適配存儲于FPGA的片上BRAM中.與上述各圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)設(shè)計(jì)相類似的,文獻(xiàn)[112]加速結(jié)構(gòu)中同樣具備多種片上存儲器,分別用于存儲聚合過程的中間結(jié)果、權(quán)重矩陣、輸出結(jié)果等相關(guān)數(shù)據(jù),另外還在聚合模塊中對片上存儲采用雙緩沖的技術(shù),與數(shù)據(jù)分割技術(shù)相配合,掩蓋訪存延遲.

En GN[116]首先采用圖分塊策略(graph tiling)對圖數(shù)據(jù)進(jìn)行分塊,使得大規(guī)模圖經(jīng)過劃分,成為適合片上存儲規(guī)模并最大化局部性的若干子圖.同時(shí),配合行導(dǎo)向(row-oriented)或列導(dǎo)向(columnoriented)的數(shù)據(jù)流處理方向選擇,可最大程度重用片上的節(jié)點(diǎn)數(shù)據(jù),并減少訪存開銷.但現(xiàn)實(shí)世界的圖數(shù)據(jù)規(guī)模巨大,導(dǎo)致僅采用圖分塊策略無法讓子圖完全適應(yīng)于處理單元的寄存器堆尺寸以及長延遲的訪存,因此En GN還設(shè)計(jì)了多層次的片上存儲器.如圖10所示,每個(gè)PE的片上存儲器由寄存器堆、度數(shù)感知Cache(degree aware cache,DAVC)和結(jié)果banks組成,上述三者依次作為1級、2級和3級片上存儲.DAVC的空間全部用作緩存高度數(shù)節(jié)點(diǎn),且用目的節(jié)點(diǎn)的ID作為行標(biāo)簽,以確定在DAVC是否命中.如果命中,則節(jié)點(diǎn)數(shù)據(jù)會直接從DAVC中讀出并送往處理單元中的目的節(jié)點(diǎn)寄存器中,否則EnGN進(jìn)行3級片上訪存.

DeepBurning-GL[115]對規(guī)則訪問的數(shù)據(jù)和不規(guī)則訪問的數(shù)據(jù)進(jìn)行區(qū)分,使用常規(guī)的片上存儲器來存儲規(guī)則訪問的數(shù)據(jù),通過1個(gè)度數(shù)感知Cache來存儲不規(guī)則訪問的數(shù)據(jù).度數(shù)感知Cache的核心策略是為高度數(shù)節(jié)點(diǎn)賦予更高的優(yōu)先級,不會被頻繁地替換.由于相較于低度數(shù)節(jié)點(diǎn),高度數(shù)節(jié)點(diǎn)的數(shù)據(jù)被重用的可能性更大,因此該策略能夠有效提升片上數(shù)據(jù)的重用率.

Cambricon-G[118]設(shè)置混合的片上存儲系統(tǒng),其中包含1組便箋存儲器(scratchpad memory,SPM)和1個(gè)拓?fù)涓兄狢ache.Cambricon-G加速結(jié)構(gòu)中共有3塊SPM用于保存規(guī)則訪存的數(shù)據(jù),也即邊特征數(shù)據(jù)、節(jié)點(diǎn)的中間或輸出特征數(shù)據(jù)以及權(quán)重?cái)?shù)據(jù).拓?fù)涓兄狢ache用于保存被不規(guī)則訪問的數(shù)據(jù),也即每層圖神經(jīng)網(wǎng)絡(luò)輸入的節(jié)點(diǎn)特征數(shù)據(jù),從而提升數(shù)據(jù)重用率.另外,感知拓?fù)涞囊饬x在于能夠應(yīng)對動態(tài)變化的圖結(jié)構(gòu),通過節(jié)點(diǎn)重用距離和度數(shù)來衡量節(jié)點(diǎn)的拓?fù)?從而實(shí)現(xiàn)不同的數(shù)據(jù)替換策略.

2)圖數(shù)據(jù)重排序

圖數(shù)據(jù)重排序的核心思想是在數(shù)據(jù)分割的基礎(chǔ)上,通過將鄰居節(jié)點(diǎn)進(jìn)行分組和序號重排,使得鄰居節(jié)點(diǎn)能夠分布在同一個(gè)分塊中,提升圖數(shù)據(jù)的局部性及片上數(shù)據(jù)的重用率.

Fig.10 Three-level on-chip memory of EnGN[112]圖10 EnGN[112]的3級片上存儲結(jié)構(gòu)

文獻(xiàn)[112]在預(yù)處理的過程中,首先對圖數(shù)據(jù)進(jìn)行稀疏化處理,也即去除冗余邊.然后,再對稀疏化的圖數(shù)據(jù)進(jìn)行重排序處理.具體而言,在原始圖中每個(gè)節(jié)點(diǎn)的序號都是隨機(jī)的,由于在圖聚合階段,每個(gè)節(jié)點(diǎn)需要聚合所有鄰居節(jié)點(diǎn)的信息,因此在重排序的過程中,將節(jié)點(diǎn)根據(jù)鄰接關(guān)系進(jìn)行分組和重排.以圖11為例,在原始的圖分布中,節(jié)點(diǎn)隨機(jī)排布,經(jīng)過稀疏化處理后的圖G′中,雖然2,3,4號節(jié)點(diǎn)構(gòu)成一個(gè)完整子圖,但在鄰接矩陣A中這3個(gè)節(jié)點(diǎn)落在了不同的分塊中,導(dǎo)致片上資源不能得到充分利用,并引發(fā)更多的片外訪存.而經(jīng)過重排序的預(yù)處理過程,G′中的2,3,4號節(jié)點(diǎn)在重排形成的圖中變?yōu)?,2,3號節(jié)點(diǎn).如此操作后,這3個(gè)節(jié)點(diǎn)特征的傳播和聚合過程都能夠在同一個(gè)鄰接矩陣子塊中完成.上述過程通過采用文獻(xiàn)[122]中提出的帶寬壓縮算法(bandwidth reduction algorithm,BR)來實(shí)現(xiàn).數(shù)據(jù)重排序的方法能夠?qū)⑧徑庸?jié)點(diǎn)進(jìn)行分組重排,從而有效提升片上存儲資源的重用率.

Fig.11 An example of data preprocessing in ref[112]圖11 文獻(xiàn)[112]的圖數(shù)據(jù)預(yù)處理過程舉例

3)降低片上存儲需求

FPGAN[114]通過壓縮模型權(quán)重的方式,降低圖注意力網(wǎng)絡(luò)對片上存儲空間的需求,使得有限的片上存儲能夠承載規(guī)模更大的模型.壓縮權(quán)重的過程分為2個(gè)步驟:①通過壓縮算法將浮點(diǎn)權(quán)重轉(zhuǎn)換為1組由零或2的冪次方組成的定點(diǎn)數(shù);②參照一系列的規(guī)則進(jìn)行數(shù)值編碼.在此過程中計(jì)算精確度缺失,若缺失過大則需要進(jìn)行重新訓(xùn)練并重復(fù)上述步驟.通過數(shù)值轉(zhuǎn)換和編碼,可使用更小的空間來存儲權(quán)重?cái)?shù)據(jù),從而降低對片上存儲空間的需求.

6.3 片外訪存優(yōu)化層次

圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)設(shè)計(jì)在片外存儲層次需要解決粗粒度不規(guī)則訪存導(dǎo)致的片外訪存效率和帶寬利用率低下的問題.目前主要的解決思路包括:基于特定的圖數(shù)據(jù)劃分方法提高預(yù)取效率和數(shù)據(jù)重用率;利用稀疏性消除、動態(tài)訪存調(diào)度、數(shù)據(jù)結(jié)構(gòu)重組提高帶寬利用率;通過操作融合減少訪存帶寬需求.

1)圖數(shù)據(jù)劃分

為了提高片外帶寬利用率,Hy GCN[9]借鑒文獻(xiàn)[123-124]中的Interval和Shard的抽象概念來對圖神經(jīng)網(wǎng)絡(luò)中的圖數(shù)據(jù)進(jìn)行劃分.每個(gè)Interval中的節(jié)點(diǎn)序號連續(xù),在片外順序存儲,因此這些節(jié)點(diǎn)的特征向量可以被連續(xù)讀進(jìn)輸入緩存中,能夠有效提升帶寬利用率.

AWB-GCN[104]采用矩陣分塊的優(yōu)化方式(matrix blocking optimization)來提升數(shù)據(jù)局部性,減少片外的訪存帶寬需求.如圖12所示,鄰接矩陣A被劃分為多個(gè)子塊,對于鄰接矩陣A與XW(注:X為特征矩陣,W為權(quán)重矩陣)的矩陣乘運(yùn)算,不采用矩陣A的所有子塊與XW的所有對應(yīng)列相乘的方式,AWB-GCN將A(XW)的t列同時(shí)并行運(yùn)算.A中只有等到前一個(gè)子塊被重用了t次并且完成了t列中間結(jié)果運(yùn)算之后,才能開啟下一個(gè)子塊的運(yùn)算.因此,矩陣A的數(shù)據(jù)重用率得到了t倍的提升,從而有效減少了片外訪存.

Fig.12 Matric blocking optimization in AWB-GCN[104]圖12 AWB-GCN[104]的矩陣分塊優(yōu)化策略

Cambricon-G[118]提出一種名為鄰接立方體(adjacent cuboid)的新型結(jié)構(gòu)來存儲圖數(shù)據(jù).鄰接立方體將傳統(tǒng)的2D鄰接矩陣擴(kuò)展到3D空間,每個(gè)維度分別代表源節(jié)點(diǎn)(src)、目的節(jié)點(diǎn)(dst)和節(jié)點(diǎn)的特征(feat).鄰接立方體根據(jù)片上存儲空間,被劃分為若干小方塊(cubelet).Cambricon-G提出多維度時(shí)間分塊策略(multi-dimensional temporal tiling),分別從鄰接立方體的3個(gè)維度進(jìn)行子塊劃分,同時(shí)實(shí)現(xiàn)不同的數(shù)據(jù)重用:feat維度劃分可實(shí)現(xiàn)子塊間的圖拓?fù)?也即源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的邊形成的2D鄰接矩陣)重用;dst維度劃分可實(shí)現(xiàn)相同源節(jié)點(diǎn)所需的節(jié)點(diǎn)數(shù)據(jù)在不同子塊間重用;src維度劃分可實(shí)現(xiàn)節(jié)點(diǎn)特征聚合的中間值重用.另外,對于動態(tài)變化的圖來說,當(dāng)需要新增/刪除邊時(shí),僅需對與之相關(guān)的子塊進(jìn)行數(shù)據(jù)搬移.上述策略能夠盡可能地挖掘圖的局部性,有效提升數(shù)據(jù)重用率,降低片外訪存帶寬需求.

2)稀疏性消除

圖神經(jīng)網(wǎng)絡(luò)的圖數(shù)據(jù)具有很強(qiáng)的稀疏性,導(dǎo)致了很多無用的片外訪存行為.HyGCN[9],Graph ACT[111]和文獻(xiàn)[112]均設(shè)計(jì)消除圖稀疏性的方法來減少片外訪存.

Hy GCN為消除稀疏性,提出了一種基于窗口滑動收縮的稀疏性消除機(jī)制.窗口尺寸與Shard一致.對于每個(gè)節(jié)點(diǎn)Interval,窗口逐漸向下滑動,直到有邊出現(xiàn)在窗口最頂行才會停止.然后,從該窗口底部行的相鄰行開始創(chuàng)建下一個(gè)新窗口,每個(gè)窗口的停止條件都相同.執(zhí)行過程中不斷生成新窗口,并向下滑動.為減少固定大小的窗口底部存在的稀疏,Hy GCN在每個(gè)窗口滑動結(jié)束之后還會進(jìn)行窗口收縮.具體而言,每個(gè)窗口從底部行向上收縮,直到底部行遇到有效邊為止.由于窗口收縮,最終Shard的大小通常會有所不同.每個(gè)窗口中訪存獲取的鄰居節(jié)點(diǎn)特征,能夠被多個(gè)節(jié)點(diǎn)的聚合操作的輸入所共享,也進(jìn)一步降低了片外訪存需求.上述窗口滑動收縮的過程,動態(tài)消除圖神經(jīng)網(wǎng)絡(luò)中圖數(shù)據(jù)的稀疏性,從而減少冗余的片外訪存操作.

Graph ACT[111]和文獻(xiàn)[112]同樣設(shè)計(jì)圖數(shù)據(jù)稀疏性消除機(jī)制作為數(shù)據(jù)預(yù)處理的其中一個(gè)步驟.其主要思想是都是通過消除圖中的冗余邊來消除稀疏性,同時(shí)保證不影響最終的處理結(jié)果.文獻(xiàn)[112]采用Graph ACT中提出的冗余縮減方法來消除邊的冗余,與6.1節(jié)中所述的減少冗余計(jì)算方法一致.通過減少冗余邊,不僅能夠優(yōu)化計(jì)算,同時(shí)也能有效減少冗余的片外訪存需求.圖11為文獻(xiàn)[112]的稀疏性消除與處理過程的簡單示例.對于圖G,首先枚舉每個(gè)節(jié)點(diǎn)的鄰居對,例如1號節(jié)點(diǎn)有鄰居4,5,6號節(jié)點(diǎn),也即枚舉1號節(jié)點(diǎn)的鄰居對為(4,5),(4,6)和(5,6).其中(5,6)鄰居對是被1號和4號節(jié)點(diǎn)共享的鄰居對.類似地,G圖中共有(1,4)和(5,6)兩個(gè)共用鄰居對.接著將共用鄰居對替換為新的節(jié)點(diǎn)u和v.將u和v分別與特征向量相連接,然后合并新節(jié)點(diǎn),刪除冗余的邊,形成新的圖G′.還可通過多個(gè)迭代反復(fù)執(zhí)行這一過程來進(jìn)一步減少冗余.

3)動態(tài)訪存調(diào)度

在實(shí)際的應(yīng)用場合中,HyGCN[9]的Aggregation加速引擎和Combination加速引擎需要的片外帶寬因圖神經(jīng)網(wǎng)絡(luò)模型的差異而不同,因此很難在設(shè)計(jì)階段確定2個(gè)加速引擎之間的內(nèi)存帶寬比率.HyGCN使用統(tǒng)一的片外存儲為2個(gè)加速引擎供應(yīng)數(shù)據(jù),并同時(shí)提供基于優(yōu)先級的動態(tài)內(nèi)存調(diào)度策略.Aggregation加速引擎的片外訪存包括輸入特征向量和邊數(shù)據(jù),Combination加速引擎的片外訪存包括權(quán)重讀入和輸出向量寫回.這些地址不連續(xù)的訪存請求同時(shí)進(jìn)行,會導(dǎo)致DRAM行緩存命中率低下.因此Hy GCN預(yù)定義了訪問優(yōu)先級,根據(jù)訪存優(yōu)先級重新組織這些不連續(xù)的請求為不同的批次,進(jìn)而可以逐批執(zhí)行訪存請求.另外,當(dāng)前批次中低優(yōu)先級的請求也會先于下一批次的高優(yōu)先級請求執(zhí)行,也即當(dāng)前批處理中的低優(yōu)先級訪問將在下一批高優(yōu)先級訪問之前進(jìn)行處理,而不是始終首先進(jìn)行高優(yōu)先級訪問.上述策略可以顯著提高DRAM的行緩存利用率,從而改善片外訪存行為.此外,被連續(xù)請求的數(shù)據(jù)會被分到不同的bank上,以挖掘DRAM的bank級并行性.

4)數(shù)據(jù)結(jié)構(gòu)重組

針對現(xiàn)實(shí)圖數(shù)據(jù)的稀疏性問題,FPGAN[114]提出一種數(shù)據(jù)結(jié)構(gòu)重組的策略,在表示圖結(jié)構(gòu)的傳統(tǒng)鄰接列表基礎(chǔ)上,對圖數(shù)據(jù)進(jìn)行向量化和對齊處理,從而實(shí)現(xiàn)更加高效的數(shù)據(jù)片外訪存.圖13展示了節(jié)點(diǎn)數(shù)據(jù)實(shí)施該策略時(shí)的一個(gè)示例,其中矩陣的行代表節(jié)點(diǎn)的特征向量,NV是節(jié)點(diǎn)向量的尺寸,FV代表特征向量的尺寸.為了能讓行數(shù)被NV整除以及列數(shù)被FV整除,該工作對矩陣向右和向下進(jìn)行填充零的操作.圖13中的方向代表數(shù)據(jù)是從左向右以及從上到下進(jìn)行向量化的.該策略完成后的輸出是一個(gè)一維數(shù)組,每個(gè)向量塊的大小為next_power_of_2(NV×FV),其中next_power_of_2(v)計(jì)算的數(shù)值大于等于v,并且是2的最小次方,以此對齊數(shù)據(jù).除了節(jié)點(diǎn)特征向量之外,該策略還支持對權(quán)重?cái)?shù)據(jù)、鄰接列表的編號等數(shù)據(jù)進(jìn)行操作.

Fig.13 Illustration of data structure reorganization in FPGAN[114]圖13 FPGAN[114]的數(shù)據(jù)結(jié)構(gòu)重組策略示意圖

5)操作融合

對于復(fù)雜的自注意力機(jī)制(self-attention mechanism),FPGAN[114]通過操作融合(operation fusion)的方式剔除其中的存儲同步過程,從而節(jié)省片外訪存帶寬.具體而言,FPGAN將圖注意力網(wǎng)絡(luò)的每一層拆分為特征聚合和線性轉(zhuǎn)換2個(gè)階段,將自注意力機(jī)制拆分為計(jì)算和歸一化注意力系數(shù)2個(gè)步驟.FPGAN首先通過將自注意力機(jī)制中的共享權(quán)重a拆分為用于中心節(jié)點(diǎn)的權(quán)重a1和用于相鄰節(jié)點(diǎn)的權(quán)重a2來修改注意力系數(shù)的計(jì)算方式.然后將注意力系數(shù)的計(jì)算過程映射入線性轉(zhuǎn)換階段,將注意力系數(shù)的歸一化映射入特征聚合階段.上述過程完成自注意力機(jī)制與通用圖注意力網(wǎng)絡(luò)兩階段的操作融合,從而剔除自注意力機(jī)制中的存儲同步過程,降低片外訪存帶寬需求.

6)存內(nèi)計(jì)算

GNN-PIM[117]是首款為圖神經(jīng)網(wǎng)絡(luò)應(yīng)用定制的存內(nèi)計(jì)算加速結(jié)構(gòu),其利用阻變式隨機(jī)存儲器(resistive random access memory,ReRAM)實(shí)現(xiàn)存內(nèi)計(jì)算.如圖14所示,GNN-PIM加速結(jié)構(gòu)由多個(gè)節(jié)點(diǎn)簇(node cluster)構(gòu)成,每個(gè)節(jié)點(diǎn)簇由若干用于處理圖節(jié)點(diǎn)或邊的節(jié)點(diǎn)組成,而每個(gè)節(jié)點(diǎn)中同時(shí)包含計(jì)算單元和存儲單元,PIM的設(shè)計(jì)縮短了計(jì)算單元與存儲單元之間的距離,并能提供更多的空間用于存儲圖數(shù)據(jù).同時(shí)為高效進(jìn)行節(jié)點(diǎn)間的數(shù)據(jù)交互,GNN-PIM設(shè)計(jì)分層片上網(wǎng)絡(luò)(network on chip,NoC)實(shí)現(xiàn)節(jié)點(diǎn)簇之間及節(jié)點(diǎn)簇內(nèi)部節(jié)點(diǎn)之間的通信,為數(shù)據(jù)傳輸提供更高的帶寬.另外PIM的設(shè)計(jì)還能為訪存帶寬帶來更多可擴(kuò)展性空間.

Fig.14 Overall architecture of GNN-PIM[117]圖14 GNN-PIM[117]的整體結(jié)構(gòu)圖

7 總結(jié)與展望

圖神經(jīng)網(wǎng)絡(luò)是時(shí)下學(xué)術(shù)界和工業(yè)界最熱門的研究方向之一,本文首先對圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的基礎(chǔ)知識、常見算法、應(yīng)用場景、編程模型以及主流的基于通用平臺的框架與擴(kuò)展庫等進(jìn)行介紹.然后以圖神經(jīng)網(wǎng)絡(luò)執(zhí)行行為帶來的加速結(jié)構(gòu)設(shè)計(jì)挑戰(zhàn)為出發(fā)點(diǎn),從整體結(jié)構(gòu)設(shè)計(jì)以及計(jì)算、片上訪存、片外訪存多個(gè)層次對該領(lǐng)域的關(guān)鍵優(yōu)化技術(shù)進(jìn)行詳實(shí)而系統(tǒng)的分析與介紹.

由于圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)研究尚處于新興初始研究階段,其仍具備很大的發(fā)展優(yōu)化空間,具體而言有4個(gè)方面:

1)大規(guī)模多節(jié)點(diǎn)加速結(jié)構(gòu).隨著大數(shù)據(jù)時(shí)代圖數(shù)據(jù)規(guī)模的不斷上升,圖神經(jīng)網(wǎng)絡(luò)應(yīng)用對計(jì)算資源的需求也愈加提高,單節(jié)點(diǎn)將難以高效執(zhí)行超大規(guī)模圖神經(jīng)網(wǎng)絡(luò)應(yīng)用,算力甚至可能無法滿足其運(yùn)行需求.因此設(shè)計(jì)可擴(kuò)展的多節(jié)點(diǎn)加速系統(tǒng)勢在必行,目前學(xué)術(shù)界和工業(yè)界尚未有該類成果問世,相信在不久的未來,該方向會成為圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的研究熱點(diǎn)之一.

2)異質(zhì)圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu).現(xiàn)實(shí)生活中相對同質(zhì)圖,異質(zhì)圖是更為常見的圖結(jié)構(gòu),異質(zhì)圖中節(jié)點(diǎn)和邊可以有多種不同的類別,且節(jié)點(diǎn)相連關(guān)系更為復(fù)雜,但數(shù)據(jù)表達(dá)能力更強(qiáng),適用場景更廣.盡管已有針對異質(zhì)圖的圖神經(jīng)網(wǎng)絡(luò)算法實(shí)現(xiàn),DGL框架也開始支持異質(zhì)圖的構(gòu)建,但面向異質(zhì)圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的加速結(jié)構(gòu)領(lǐng)域仍是無人區(qū).

3)算法與階段支持靈活化.目前圖神經(jīng)網(wǎng)絡(luò)專用加速結(jié)構(gòu)多只針對單類別算法進(jìn)行加速支持.但隨著圖神經(jīng)網(wǎng)絡(luò)算法的高速發(fā)展,不僅算法種類會有所增加,并且每種類別中的具體算法也會不斷革新,這就使得加速結(jié)構(gòu)是否能高效適應(yīng)與支持后續(xù)的新型算法成為一個(gè)亟需克服的難題.另外,目前的已有工作大多只能針對訓(xùn)練或者推斷中的單一階段進(jìn)行加速,如何能夠讓加速結(jié)構(gòu)高效地同時(shí)對2個(gè)階段產(chǎn)生加速作用也是一個(gè)值得思考的問題.因此提升圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)設(shè)計(jì)對算法與執(zhí)行階段支持的靈活性是另一個(gè)極具應(yīng)用價(jià)值的研究方向.

4)圖神經(jīng)網(wǎng)絡(luò)加速結(jié)構(gòu)產(chǎn)業(yè)化落地.圖神經(jīng)網(wǎng)絡(luò)作為推動人工智能領(lǐng)域革新、邁入“認(rèn)知智能”時(shí)代的核心主力軍,極富商業(yè)應(yīng)用價(jià)值,有望為人們生活智能化與科技進(jìn)步做出更大的貢獻(xiàn).有寒武紀(jì)等在內(nèi)的國內(nèi)自主研發(fā)的人工智能芯片珠玉在前,相信面向圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的產(chǎn)業(yè)化芯片也指日可待,且必將創(chuàng)造更多輝煌.

圖神經(jīng)網(wǎng)絡(luò)作為推動認(rèn)知智能時(shí)代發(fā)展的重要應(yīng)用之一,具有極高的研究價(jià)值與產(chǎn)業(yè)前景.相信本文對面向圖神經(jīng)網(wǎng)絡(luò)應(yīng)用的加速結(jié)構(gòu)設(shè)計(jì)中涉及到的關(guān)鍵優(yōu)化技術(shù)與未來方向的詳實(shí)介紹,能夠讓讀者清晰地了解該領(lǐng)域的研究現(xiàn)狀,并對相關(guān)研究人員在加速結(jié)構(gòu)設(shè)計(jì)過程中有所啟發(fā).