實(shí)現(xiàn)大規(guī)模圖計(jì)算的算法思路

思路一：避開|E|

通常情況下，圖中邊的個(gè)數(shù)遠(yuǎn)大于節(jié)點(diǎn)的數(shù)量。極端情況下，當(dāng)邊的密度很高直至完全圖時(shí)，圖的復(fù)雜度可以達(dá)到|V|(|V|-1)/2。如果考慮兩個(gè)節(jié)點(diǎn)間雙向的邊，以及節(jié)點(diǎn)到自身的特殊邊，那么這個(gè)復(fù)雜度就是|V|²。為了降低計(jì)算的復(fù)雜度，一個(gè)思路就是盡量避開圍繞邊的計(jì)算。具體來說，為了讓計(jì)算復(fù)雜度從|E|級別降低為|V|級別，在計(jì)算消息向量（message vectors）時(shí)，我們僅計(jì)算 destination-independent messages。也就是說，從節(jié)點(diǎn)u發(fā)出的所有消息使用同一個(gè)向量，這樣復(fù)雜度從邊數(shù)級別降為了節(jié)點(diǎn)數(shù)級別。值得注意的是，這里會存在一個(gè)問題，消息向量里不區(qū)分不同的destination節(jié)點(diǎn)。那么，能否把不同的destination節(jié)點(diǎn)考慮進(jìn)來呢？當(dāng)然可以，不過需要引入multi-head attention機(jī)制。下面針對這種情況來介紹一下優(yōu)化方案。

適合情形

當(dāng)|E|>>|V|時(shí)，即邊密度高的圖，尤其是完全圖

優(yōu)化方案

思路二：減少D

順著思路一，我們在計(jì)算attention時(shí)，每個(gè)attention分?jǐn)?shù)都是一個(gè)標(biāo)量。我們可以減小計(jì)算attention所用的向量維數(shù),因?yàn)檩敵鍪且粋€(gè)標(biāo)量，信息被壓縮到一維空間，所以計(jì)算時(shí)沒必要使用大向量來提高capacity。如果需要multi-head的話，可以把每個(gè)計(jì)算channel的向量維數(shù)變小，讓它們加起來還等于原來的總維數(shù)。這個(gè)思路很像BERT，BERT雖然不是GNN,但是這種機(jī)制可以運(yùn)用到GNN中。還有一篇論文，提出了Graph Attention Networks，也用到了類似的思路。

適合情形

引入attention mechanism的multi-head channels設(shè)計(jì)

優(yōu)化方案

每個(gè)head channel 的消息計(jì)算使用較小的hidden dimensions, 通過增加head的數(shù)量來保證模型的capacity，而每個(gè)head的attention 分?jǐn)?shù)在一個(gè)節(jié)點(diǎn)上僅僅是一個(gè)標(biāo)量。

思路三：部分迭代更新（選擇性減少T）

前面的思路是減少邊數(shù)量以及計(jì)算維度數(shù)，我們還可以減少迭代次數(shù)T，這樣中間需保留tensors的規(guī)模就會變小，適合非常大的網(wǎng)絡(luò)，尤其當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)刻畫的時(shí)間跨度很大，或者異構(gòu)網(wǎng)絡(luò)的不同節(jié)點(diǎn)需要不同頻次或不同階段下的更新。有些節(jié)點(diǎn)不需要迭代更新那么多次，迭代兩、三次就夠了，有些節(jié)點(diǎn)要更新好多次才行。下圖的右側(cè)部分，每步迭代節(jié)點(diǎn)都更新；左側(cè)部分，節(jié)點(diǎn)只更新一次，即使這樣，它的計(jì)算依賴鏈條還是有四層。至于更新策略，可以人為設(shè)定，比如說，采取隨機(jī)抽樣方式，或者通過學(xué)習(xí)得到哪些節(jié)點(diǎn)需更新的更新策略。更新策略的數(shù)學(xué)實(shí)現(xiàn)，可以采取hard gate的方式（注意不是soft），也可以采取sparse attention即選擇top-K節(jié)點(diǎn)的方式。有paper基于損失函數(shù)設(shè)計(jì)criteria去選擇更新的節(jié)點(diǎn)，如果某個(gè)節(jié)點(diǎn)的當(dāng)前輸出對最終損失函數(shù)的貢獻(xiàn)已經(jīng)很好了，就不再更新。需要注意的是，在hard gate和sparse attention的代碼實(shí)現(xiàn)中，不能簡單地把要略過的節(jié)點(diǎn)的權(quán)重置零,雖然數(shù)學(xué)上等價(jià)，但是CPU或GPU還是要計(jì)算的，所以代碼中需要實(shí)現(xiàn)稀疏性計(jì)算，來減少每次更新所載入的tensor規(guī)模。更新的粒度可以是逐點(diǎn)的，也可以是逐塊的。

適合情形

具有大時(shí)間跨度或異構(gòu)的網(wǎng)絡(luò)，其節(jié)點(diǎn)需不同頻次或不同階段下的更新

優(yōu)化方案

更新策略一：預(yù)先設(shè)定每步更新節(jié)點(diǎn)

更新策略二：隨機(jī)抽樣每步更新節(jié)點(diǎn)

更新策略三：每步每節(jié)點(diǎn)通過hard gate的開關(guān)決定是否更新

更新策略四：每步通過sparse attention機(jī)制選擇top-K節(jié)點(diǎn)進(jìn)行更新

更新策略五：根據(jù)設(shè)定的criteria選擇更新節(jié)點(diǎn)（如：非shortcut支路上梯度趨零）

思路四：Baking（“烘焙”，即使用臨時(shí)memory存放某些計(jì)算結(jié)果）

Baking這個(gè)名字，是我引用計(jì)算機(jī)3D游戲設(shè)計(jì)中的一個(gè)名詞，來對深度學(xué)習(xí)中一種常見的技巧起的名字。當(dāng)某些數(shù)據(jù)的計(jì)算復(fù)雜度很高時(shí)，我們可以提前算好它，后面需要時(shí)就直接拿來。這些數(shù)據(jù)通常需要一個(gè)臨時(shí)的記憶模塊來存儲。大時(shí)間跨度的早期計(jì)算節(jié)點(diǎn)，或者異構(gòu)網(wǎng)絡(luò)的一些非重要節(jié)點(diǎn)，我們假定它們對當(dāng)前計(jì)算的作用只是參考性的、非決定性的，并設(shè)計(jì)它們只參與前向計(jì)算，不參與梯度的反向傳播，此時(shí)我們可以使用記憶模塊保存這些算好的數(shù)據(jù)。記憶模塊的設(shè)計(jì)，最簡單的就是一組向量，每個(gè)向量為一個(gè)記憶槽（slot），訪問過程可以是嚴(yán)格的索引匹配，或者采用soft attention機(jī)制。

適合情形

大時(shí)間跨度的早期計(jì)算節(jié)點(diǎn)或者異構(gòu)網(wǎng)絡(luò)的一些非重要節(jié)點(diǎn)（只參與前向計(jì)算，不參與梯度的反向傳播）。

優(yōu)化方案

維護(hù)一個(gè)記憶緩存，保存歷史計(jì)算的某些節(jié)點(diǎn)狀態(tài)向量，對緩存的訪問可以是嚴(yán)格索引匹配，也可以使用soft attention機(jī)制。

思路五：Distillation（蒸餾技術(shù)）

蒸餾技術(shù)的應(yīng)用非常普遍。蒸餾的思想就是用層數(shù)更小的網(wǎng)絡(luò)來代替較重的大型網(wǎng)絡(luò)。實(shí)際上，所有神經(jīng)網(wǎng)絡(luò)的蒸餾思路都類似，只不過在圖神經(jīng)網(wǎng)絡(luò)里，要考慮如何把一個(gè)重型網(wǎng)絡(luò)壓縮成小網(wǎng)絡(luò)的具體細(xì)節(jié)，包括要增加什么樣的loss來訓(xùn)練。這里，要明白蒸餾的目的不是僅僅為了學(xué)習(xí)到一個(gè)小網(wǎng)絡(luò)，而是要讓學(xué)習(xí)出的小網(wǎng)絡(luò)可以很好地反映所給的重型網(wǎng)絡(luò)。小網(wǎng)絡(luò)相當(dāng)于重型網(wǎng)絡(luò)在低維空間的一個(gè)投影。實(shí)際上，用一個(gè)小的參數(shù)空間去錨定重型網(wǎng)絡(luò)的中間層features，基于hidden層或者attention層做對齊，盡量讓小網(wǎng)絡(luò)在某些中間層上產(chǎn)生與重型網(wǎng)絡(luò)相對接近的features。

適合情形

對已訓(xùn)練好的重型網(wǎng)絡(luò)進(jìn)行維度壓縮、層壓縮或稀疏性壓縮，讓中間層的feature space表達(dá)更緊湊。

優(yōu)化方案

Distillation Loss的設(shè)計(jì)方案：

• Hidden-based loss

• Attention-based loss

思路六：Partition (or clustering)

如果圖非常非常大，那該怎么辦？只能采取圖分割（graph partition）的方法了。我們可以借用傳統(tǒng)的圖分割或節(jié)點(diǎn)聚類算法，但是這些算法大多很耗時(shí)，故不能采取過于復(fù)雜的圖分割或節(jié)點(diǎn)聚類算法。分割過程要注意執(zhí)行分割算法所用的節(jié)點(diǎn)數(shù)據(jù)，最好不要直接在節(jié)點(diǎn)hidden features上做分割或聚類計(jì)算，這是因?yàn)橹挥衕idden features相似的nodes才會聚到一起，可能存在某些相關(guān)但hidden features不接近的節(jié)點(diǎn)需要放在一個(gè)組里。我們可以將hidden features做非線性轉(zhuǎn)換到某個(gè)分割語義下的空間，這個(gè)非線性轉(zhuǎn)換是帶參的，需要訓(xùn)練，即分割或聚類過程是學(xué)習(xí)得到的。每個(gè)分割后的組，組內(nèi)直接進(jìn)行節(jié)點(diǎn)到節(jié)點(diǎn)的消息傳遞，組間消息傳遞時(shí)先對一組節(jié)點(diǎn)做池化（pooling）計(jì)算，得到一個(gè)反映整個(gè)組的狀態(tài)向量，再通過這個(gè)向量與其他組的節(jié)點(diǎn)做消息傳遞。另外的關(guān)鍵一點(diǎn)是如何通過最終的損失函數(shù)來訓(xùn)練分割或聚類計(jì)算中的可訓(xùn)參數(shù)。我們可以把節(jié)點(diǎn)對組的成員關(guān)系（membership）引入到計(jì)算流程中，使得反向傳播時(shí)可以獲得相應(yīng)的梯度信息。當(dāng)然，如果不想這么復(fù)雜，你可以提前對圖做分割, 然后進(jìn)行消息傳遞。

適合情形

針對非常大的圖（尤其是完全圖）

優(yōu)化方案

對圖做快速分割處理，劃分節(jié)點(diǎn)成組，然后在組內(nèi)進(jìn)行節(jié)點(diǎn)到節(jié)點(diǎn)的消息傳遞，在組間進(jìn)行組到節(jié)點(diǎn)、或組到組的消息傳遞。

① Transformation step

• Project hidden features onto the partition-oriented space

② Partitioning step

③ Group-pooling step

• Compute group node states

④ Message-passing step

• Compute messages from within-group neighbors

• Compute messages from the current group node

• Compute messages from other group nodes

思路七：稀疏圖計(jì)算

如何利用好稀疏圖把復(fù)雜度降下來?你不能把稀疏圖當(dāng)作dense矩陣來處理，并用Tensorflow或PyTorch做普通tensors間的計(jì)算，這是沒有效果的。你必須維護(hù)一個(gè)索引列表，而且這個(gè)索引列表支持快速的sort、unique、join等操作。舉個(gè)例子，你需要維護(hù)一份索引列表如下圖，第一列代表batch中每個(gè)sample的index，第二列代表source node的id。當(dāng)用節(jié)點(diǎn)狀態(tài)向量計(jì)算消息向量時(shí)， 需要此索引列表與邊列表edgelist做join，把destination node的id引進(jìn)來，完成節(jié)點(diǎn)狀態(tài)向量到邊向量的轉(zhuǎn)換，然后你可以在邊向量上做一些計(jì)算，如經(jīng)過一兩層的小神經(jīng)網(wǎng)絡(luò)，得到邊上的消息向量。得到消息向量后，對destination node做sort和unique操作。聯(lián)想稀疏矩陣的乘法計(jì)算，類似上述的過程，可以分成兩步，第一步是在非零元素上進(jìn)行element-wise乘操作，第二步是在列上做加操作。

適合情形

當(dāng)|E|<<|v|*|v|時(shí)

優(yōu)化方案

稀疏計(jì)算的關(guān)鍵在于維護(hù)一個(gè)索引列表，能快速進(jìn)行sort、unique、join操作并調(diào)用如下深度學(xué)習(xí)庫函數(shù)：

TensorFlow:

-  gather, gather_ndm

-  scatter_nd, segment_sum,

-  segment_max, unsored_segment_sum|max

Pytorch: