聚類GCN：面向大而深圖卷積網路的高效訓練演算法

關注“

醫學大資料與人工智慧

”公眾號，重磅乾貨，第一時間送達

歡迎個人轉發朋友圈；其他機構或自媒體如需轉載，後臺留言申請授權

整理：煉數之道

摘要

圖卷積網路（GCN）已經成功地應用於許多基於圖的應用，然而，大規模GCN的訓練仍然具有挑戰性。目前基於SGD的演算法要麼面臨著隨GCN層數增加呈指數增長的高計算成本，要麼面臨著儲存整個圖形和每個節點嵌入（embedding）到記憶體的巨大空間需求。本文提出了一種新的基於圖聚類結構且適合於基於SGD訓練的GCN演算法——Cluster-GCN。

Cluster-GCN的工作原理如下：在每個步驟中，它對一個與透過用圖聚類演算法來區分的密集子圖相關聯的一組節點進行取樣，並限制該子圖中的鄰居搜尋。這種簡單且有效的策略可以顯著提高記憶體和計算效率，同時能夠達到與以前演算法相當的測試精度。

為了測試演算法的可擴充套件性，作者建立了一個新的Amazon2M資料集，它有200萬個節點和6100萬條邊，比以前最大的公開可用資料集（Reddit）大5倍多。在該資料集上訓練三層GCN網路，Cluster-GCN比以前最先進的VR-GCN（1523秒 vs 1961秒）更快，並且使用的記憶體更少（2。2GB vs 11。2GB）。此外，在該資料集上訓練4層GCN網路，Cluster-GCN可以在36分鐘內完成，而所有現有的GCN訓練演算法由於記憶體不足而無法訓練。Cluster-GCN允許在短時間和記憶體開銷受限的情況下訓練更深的GCN網路，從而提高了預測精度。使用5層Cluster-GCN，在PPI資料集上實現了最先進的測試集F1值99。36，而之前的最佳結果是98。71。

1. 引言

圖卷積網路（GCN）在處理許多基於圖的應用中日益流行，包括半監督節點分類、連結預測和推薦系統。給定一個圖，GCN採用圖卷積操作逐層獲取節點嵌入：在每一層，要獲取一個節點的嵌入，需要透過採集相鄰節點的嵌入，然後進行一層或幾層線性變換和非線性啟用。最後一層embedding用於一些最終任務。例如，在節點分類問題中，將最後一層embedding傳遞給分類器來預測節點標籤，從而對GCN引數進行端到端訓練。

由於GCN中的圖卷積運算（operator）需要利用圖中節點之間的互動來傳播嵌入，這使得訓練具有挑戰性。其他神經網路的訓練損失可以在每個樣本上完美地分解為單獨的損失項，GCN中的損失項（例如單個節點上的分類損失）依賴於大量的其他節點，尤其是當GCN深度增加時。由於節點依賴性，GCN的訓練非常慢，且需要大量的記憶體。反向傳播需要將計算圖上的所有embeddings儲存在GPU記憶體中。

GCN訓練演算法

為了說明開發可擴充套件GCN訓練演算法的必要性，文章首先討論了現有方法的優缺點，包括：（1）記憶體需求，（2）每個epoch需要的時間，（3）每個epoch的收斂速度（損失減少速度）。這三個因素是評估訓練演算法的關鍵。注意，記憶體需求直接限制了演算法的可擴充套件性，後兩個因素結合決定了訓練速度。在接下來的討論中，用N表示圖中的節點數，F表示embedding的維度，L表示網路成熟，來分析經典的GCN訓練演算法。

全批次梯度下降是在第一篇GCN論文中提出的。為了計算完整梯度，需要儲存所有中間嵌入，導致O（NFL）記憶體需求，這是不可擴充套件的。此外，雖然每個epoch的時間是有效的，但梯度下降的收斂速度很慢，因為每個epoch只更新一次引數。【記憶體：差；每個epoch需要的時間：好；收斂速度：差】

小批次SGD。由於每次更新僅基於一個小批次樣本梯度，它可以減少記憶體需求，並在每個epoch進行多次更新，從而加快收斂速度。然而，mini-batch SGD會因鄰居擴張問題引入額外的計算開銷。在節點層L計算單個節點的損失，它要求節點的鄰居節點在L−1層的嵌入，遞迴需要其鄰居節點在L−2層的嵌入及其上一層依賴的鄰居節點。這將導致GCN的時間複雜度隨網路深度呈指數增長。GraphSAGE［5］提出在透過層反向傳播時使用固定大小的鄰域樣本，FastGCN［1］提出採用重要性取樣，但這些方法的開銷仍然很大，當GCN深度增加時，開銷會變大。【記憶體：好；每個epoch需要的時間：差；收斂速度：好】

VR-GCN［2］提出使用方差約簡技術來減小鄰域取樣節點的數量。儘管成功地減少了取樣樣本大小，但它需要在記憶體中儲存所有節點的所有中間嵌入，導致O（NFL）記憶體需求。如果圖中的節點數量增加到數百萬，VR-GCN的記憶體需求可能太高，無法裝入GPU。【記憶體：差；每個epoch需要的時間：好；收斂速度：好】

本文提出了一種基於圖聚類結構的GCN訓練演算法。mini-batch演算法的效率可以用“嵌入利用率”的概念來表徵，它與batch或within-batch links的節點之間的連線數量成正比。這一發現促使作者使用圖聚類演算法來設計batches，該演算法旨在構造節點分割槽，以使在同一分割槽中的節點之間比不同分割槽中的節點之間具有更多的圖連線。基於圖聚類思想，提出了Cluster-GCN演算法，一種基於高效圖聚類演算法（如METIS［8］）的batch設計算法，並進一步提出了一個隨機多聚類框架，以提高Cluster-GCN的收斂性。該策略帶來了巨大的記憶體和計算效益。在記憶體方面，只需要將節點嵌入儲存在當前批處理中，批處理大小為O（bFL），批處理大小為b。這明顯優於VR-GCN和全梯度方法，略優於其他基於sgd的方法。在計算複雜度方面，梯度下降演算法在每個epoch上的時間開銷與鄰域搜尋演算法相同。在收斂速度方面，本演算法與其他基於sgd的方法是有競爭力的。最後，演算法實現簡單，只需計算矩陣乘法，不需要鄰域取樣。【記憶體：好；每個epoch需要的時間：好；收斂速度：好】

作者對多個大型圖資料集進行了綜合實驗，得到如下結果：

Cluster-GCN在大規模圖，特別是深度GCN上獲得了最佳的記憶體利用效果。例如，在Amazon2M上的3層GCN模型中，Cluster-GCN使用的記憶體比VR-GCN少5倍。Amazon2M是一個新的圖資料集，用於展示GCN演算法的可擴充套件性。該資料集包含一個亞馬遜產品共同購買圖，包含超過200萬個節點和6100萬條邊。

對於淺層網路（如2層），Cluster-GCN的訓練速度與VR-GCN相似，但當網路深度增加（如4層）時，可以比VR-GCN更快，因為Cluster-GCN的複雜度與層數L呈線性關係，而VR-GCN的複雜度與層數L呈指數關係。

Cluster-GCN能夠訓練具有較大嵌入大小的深度網路。雖然之前的一些工作表明，深度GCN並沒有提供更好的效能，但我們發現，透過適當的最佳化，深度GCN可以幫助提高精度。例如，使用5層GCN，在PPI資料集獲得了新的基準精度99。36，而之前的最高基準精度為98。71。

2. 研究背景

最近的一些研究試圖將卷積運算應用於圖形資料。在Semi-supervised classification with graph convolutional networks中首次引入了圖卷積網路（GCN），並在多個節點分類任務中實現了最佳效能。作者定義並使用了一種類似卷積的運算，稱為譜圖卷積。這使得CNN可以直接在圖形上操作。基本上，GCN中的每一層透過考慮相鄰節點的特徵來更新圖中每個節點的特徵向量的表示。具體來說，GCN的逐層正向傳播操作可以表示為

X是所有節點的特徵向量構成的特徵矩陣（每一行表示一個節點的特徵），X（l）和X（l+1）分別是第l層網路的輸入和輸出矩陣，X（l）也是第l層所有節點的embedding。對於這兩個矩陣，行數相同，對應於圖中的節點數；而列數可能不同，這取決於輸入和輸出特徵空間的大小。A是圖的鄰接矩陣，A~ = A + I，是帶有自環的無向圖的鄰接矩陣。D~是帶有自環的無向圖的度矩陣，是一個對角矩陣。W（l）是一個可訓練權重矩陣或引數矩陣。σ（⋅）是啟用函式，例如Relu。為了簡化計算，令每一層節點的特徵數量都是F。

3. 演算法原理

作者首先討論了現有訓練方法的瓶頸問題。在GCN的原始論文（2017。 Semi-supervised classification with graph convolutional networks ）中，GCN的訓練使用的是全批次梯度下降（full gradient descent），但是它的計算和記憶體成本很高。在記憶體方面，透過反向傳播來計算全梯度資訊需要儲存所有的嵌入矩陣，需要O（NFL）的記憶體空間（F是特徵數量，N是結點數量，L是網路層數）。在收斂速度方面，由於在每個epoch模型才更新一次，所以需要很多個epoch才會使模型收斂。

研究表明，在最近的一些工作中，使用mini-batch SGD可以提高GCN的訓練速度和記憶體需求。其中的SGD不需要計算全梯度資訊，只需要計算每次更新的mini-batch的梯度。在本文中，使用大小為B的batch，每個SGD步驟計算梯度用下面的公式更新：

儘管在每個epoch收斂得更快，但SGD在GCN訓練上引入了另一個計算開銷，使得SGD的每個epoch時間內比全梯度下降要慢得多。

Cluster-GCN演算法流程

在每個步驟中，它對與圖聚類演算法識別的稠密子圖相關聯的節點塊進行取樣，並限制在該子圖中進行鄰域搜尋。在構建batch進行SGD更新時，沒有隻考慮一個簇，而是隨機選擇q個簇。

圖1：傳統圖卷積與Cluster-GCN方法鄰域擴充套件的差異。紅色節點是擴充套件鄰域節點的起始節點。傳統圖卷積存在指數鄰域展開的問題，而Cluster-GCN可以避免複雜的鄰域展開。

圖2：基於標籤分佈的熵值直方圖。這裡我們在每個批處理中使用隨機分割槽和聚類分割槽。大多數聚類劃分batch的標籤熵較低，說明每個batch的標籤呈偏態分佈。相比之下，隨機劃分將導致batch中更大的標籤熵。這增加了不同批次之間的差異，並可能影響SGD的收斂。為了解決這個問題，作者提出隨機多聚類方法（stochastic multiple clustering）對簇進行合併，從而減少 batch 間的差異。

作者首先將圖分為多個小簇，然後隨機選擇 q 個簇併到 batch 中，這樣便可以減少 batch 之間的差異。下圖展示了隨機組合的 batch：