思路一：避開|E|

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

適合情形

當|E|>>|V|時，即邊密度高的圖，尤其是完全圖

優(yōu)化方案

思路二：減少D

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

適合情形

引入attention mechanism的multi-head channels設計

優(yōu)化方案

每個head channel 的消息計算使用較小的hidden dimensions, 通過增加head的數(shù)量來保證模型的capacity，而每個head的attention 分數(shù)在一個節(jié)點上僅僅是一個標量。

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

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

適合情形

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

優(yōu)化方案

更新策略一：預先設定每步更新節(jié)點

更新策略二：隨機抽樣每步更新節(jié)點

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

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

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

思路四：Baking（“烘焙”，即使用臨時memory存放某些計算結果）

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

適合情形

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

優(yōu)化方案

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

思路五：Distillation（蒸餾技術）

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

適合情形

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

優(yōu)化方案

Distillation Loss的設計方案：

• Hidden-based loss

• Attention-based loss

思路六：Partition (or clustering)

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

適合情形

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

優(yōu)化方案

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

① 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

思路七：稀疏圖計算

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

適合情形

當|E|<<|v|*|v|時

優(yōu)化方案

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

TensorFlow:

-  gather, gather_ndm

-  scatter_nd, segment_sum,

-  segment_max, unsored_segment_sum|max

Pytorch: