cluster gcn 是graphsage之後，由google提出的一種新的gcn的拓展，解決了gcn的兩個問題：
1 計算量高，視訊記憶體壓力太大，尤其是GCN的基於批梯度下降法（沒有mini-batch直接whole batch ，一個epoch 訓練全部節點），視訊記憶體壓力非常高，並且隨著GCN layer的層數增長，視訊記憶體佔用指數增長；
2 GCN無法insductive（這裡指的是沒有使用sage這類的策略來輔助而是單純指最原始的GCN，不過感覺cluster gcn其實本質上還是要透過sage的取樣策略才能實現indstuctive，這一點有待商榷）
Cluster GCN的思路很巧妙，類似於sage：做取樣，只不過cluster gcn中的取樣，是先對圖進行聚類，然後分別抽取部分圖聚類得到的子圖進行分批訓練，這限制了節點的鄰域的範圍。
接著比較了一下現有的幾種訓練方法：
1 原始GCN，全批次梯度下降（Full-batch gradient descent），要一次性計算整個圖所有節點的梯度，需要儲存所有中間的node的embeddings，大圖分分鐘爆視訊記憶體。
視訊記憶體佔用大，每個epoch的時間短，收斂效果不好
2 GraphSAGE：透過引入鄰節點取樣的方法，使得GCN的訓練進入了 Mini-batch SGD的軌道。大大減少了記憶體佔用，並在每個epoch執行多次更新，從而加快了收斂速度。但是，視訊記憶體壓力還是有，比如我們在第一層取樣5個，第二層取樣10個，則單個樣本（節點）在兩層sage的訓練過程中 需要儲存50個node的embedding向量。
視訊記憶體佔用降低，每個epoch的時間變長（引入mini batch而不會像原始GCN一樣全batch），收斂效果較好；
3 fastGCN：重要性取樣（還沒看這篇）
視訊記憶體佔用降低，每個epochs的時間變長，收斂效果較好，相較於graphsage對GCN的線性提升，fastGCN的提升是數量級的；
3。VR-GCN：（這篇沒看過，大概思路是透過某種方法減少了鄰節點的取樣數量）提出採用variance減少技術來減小鄰域取樣節點的大小。但它需要將所有節點的所有中間的embeddings儲存在記憶體中，從而導致視訊記憶體溢位的問題。
視訊記憶體佔用高，每個epoch的時間短，收斂效果好。
4 cluster GCN：
基於圖聚類（社群發現）改進了GCN的訓練，具體原理後面會提到
視訊記憶體佔用降低，每個epoch的時間短，收斂效果好，並且在是的深層GCN的實現變得可能（前面的幾種改進，在GCN layer層數變深的情況下視訊記憶體佔用會指數上升）
比較的表格如下
那麼為什麼cluster gcn認為 sage還不夠好呢？一個主要的原因在於，sage雖然進行了取樣，這種方法對於較小數量的鄰節點取樣和較低的layer數還可以，但是如果取樣數量較大或層數較深則不行了，比如一個簡單的雙層的graphsage，第一層取樣10，第二層取樣10，則對於每一個節點的訓練來說（在GNN中一個節點的訓練過程需要使用到其鄰域的節點的資料，例如雙層GCN按照10，10的取樣數量，每個節點的訓練需要使用到100個領域節點的資料），其訓練和引數更新需要太多的輸入資料了，這還只是單個樣本點，對於一個256的batch來說計算壓力就更大了。
cluster gcn的思想非常簡單暴力而直接，既然GCN沒法一次性處理一個大圖，我們就將大圖切割為一大堆的小的子圖，然後GCN分別在小的子圖上訓練，這樣不僅可以batch training，還可以有效的降低視訊記憶體的壓力，一個子圖的大小有限，所謂深層GCN也可以跑起來。
具體的思路如上圖，我們以單個節點為例，即上圖的紅色節點，可以看到隨著層數的增加，最終紅色節點的一次前向傳播需要使用到全圖的節點的資料，而cluster gcn，直接做了一個割圖的操作，將原來的大圖轉化為兩個小的子圖，這樣紅色節點撐死也就用到一個cluster裡面的其他節點的資料來完成一次前向傳播。
那麼問題來了，怎麼去做圖的切分，總不能隨便切一堆subgraph出來吧？直觀的思路，我們可以先做社群發現（圖聚類），然後將每個社群當作一個subgraph不就好了？這樣的好處在於，一方面實現了前面的思路，另一方面在一個社群中的節點往往之間的關聯關係更具有顯著性，蘊含著更加豐富的拓撲結構資訊。
cluster-gcn，顧名思義，也確實是用這種方式來做的。
對於一個圖G，我們先將這個G中的所有節點V劃分為一堆的節點cluster構成的一堆社群：
V=［V1，····Vc］，即一共有c個社群，其中Vt包含第t個社群中的所有節點。因此，我們會得到如下的子圖：
那麼原始的鄰接矩陣A就可以被劃分為c^2個子矩陣：
其中，
需要注意，A11，A22的大小不一定是一樣的，比如社群1有10個節點，則A11為一個10X10的矩陣，社群2有50個節點，則A22為一個50X50的矩陣，同時，A12，A21這類表示的是不同社群之間的邊的連線構成的鄰接矩陣，這裡的思路和louvain非常相似，就是我們把subgraph看成一個大的節點，比如上面的A11是一個包含了10個節點的大節點，假設A11中有5個節點和A22這個社群存在edge，則A12這個矩陣為5X5大小，表示的是A11和A12這兩個“大”節點之間的edge的關聯關係。
然後接下來怎麼訓練呢？思路也非常簡單，我們分出了c個cluster，每
個cluster作為一個batch來訓練
就行了。
上述公式看起來複雜，但是其實很簡單，其實就是每個cluster分別跑一下常規的GCN而已，很有意思，我們基本不用改動GCN的模型程式碼，只不過訓練的時候使用GCN處理多個cluster而已，即每個batch處理一個cluster或者說社群或者說subgraph。
看上去cluster-gcn的思路很簡單，但是實際上存在著一些問題：
1 直接丟棄了clusters之間的edge了，顯然模型的精度會有一定下降的；
2 透過圖聚類的方法進行節點的聚類會有一些問題，
（1）一方面不同圖聚類（或者說社群發現演算法）的結果不一定和下游的任務是契合的，感覺不靠譜；
（2）聚類本身就會把一些相似的節點劃分到一起，這樣對於下游任務不一定是好的，比方說，可能在cluster之外的其它節點對於當前cluster中的node classification的任務也會有幫助；
（3）每個batch的subgraph的分佈和整個graph可能會存在一些差異從而導致了資料分佈不一致的問題（圖的分佈差異可以理解為拓撲結構的形狀的差異，可能全圖是一個五角星形狀的拓撲結構，cluster是一個三角形形狀的拓撲結構，當然 node features也很可能存在差異，node features的分佈差異就和表格資料裡的資料的分佈差異的概念是一樣的，比如某個cluster裡面都是老年人節點，而全圖包括了中老年青少年人等型別的節點，而nn訓練的時候我們是希望每個batch和整體的分佈差異儘量小）
針對這些問題，cluster-gcn做了改進，既然簡單的進行圖聚類會導致這麼多問題，那麼就隨機聚類試試？即stochastic multiple clustering approach。
思路也不復雜，還是先對圖進行聚類，劃分為p個cluster，這裡儘量讓p大一點，即聚類出盡量多一點的cluster，然後batch訓練的時候，不再是簡單的一個cluster對應一個batch，而是隨機選擇q個cluster重新放到一起合併成一個大的clsuter，這個時候，前面的
中，三角形部分的資料就派上用場了。我們不是簡單的就把這q個clusters放在一起，而是根據三角形部分的資訊（三角形部分存的是不同cluster之間的edge的關係），將這q個clusters之間的真實的edge還原回去，然後作為一個新的大的cluster進行訓練。
透過這種方法，作者發現，這種方法在reddit上的效果更好，更穩定。
話說這樣做的話。。其實等同於對原始的鄰接矩陣進行行列取樣的操作其實，只不過這裡做的行列取樣不是完全隨機的，同一個cluster中的節點必然會在一次取樣中出現。。。，舉個例子，假設我們有10000個節點，鄰接矩陣是一個10000X10000的矩陣，然後我們cluster比如聚類成1000個clusters，我們隨機選擇500個clsuter（假設一共包含了3000個節點），完了之後還根據這500個clusters之間的edge還原回去，這不等於直接對原始的10000X10000的鄰接矩陣進行了行列取樣比例為0。3的取樣嗎。。最終一個batch是3000X3000的“子”鄰接矩陣。
文中還提到了關於深層GCN訓練的問題，因為GNN的深層訓練本身是一大塊的知識，也有一些比較好的做法來解決，因此這裡就不寫了，後面寫GNN訓練方法的時候一起總結好了。另外關於這篇文章有一些思考的地方：
1 文中提到的圖聚類的演算法有metis 和 Graclus，這塊兒是不是可以用louvain，lpa或者更簡單的connected components之類的社群發現（就是圖聚類）演算法來代替？
2 cluster-gcn 是不是用到了ensemble的思路，本質上就是對鄰接矩陣進行非完全隨機的行列取樣作為batch，因此gcn可以分batch訓練，並且每一個batch處理的subgraph都是原始的graph的子集，從而達到提升模型魯棒性的效果？
3 關於圖的正則化問題，文中有提到，圖上確實有一些特定的不同於其它資料的正則化方法，例如之前看過的dropedge和pairnorm之類的，這塊兒還要系統性的看一看，屬於訓練trick範疇了。
4 單純上面提到的cluster-gcn的做法，其實也沒解決transductive的問題，最終還是需要透過取樣的方法來實現transductive。
cluster-gcn不是一種新的gnn，更像是一種新的幫助gnn訓練的方法，這種方法可以很自然的擴充套件到sage，gat之類的圖神經網路結構上。
實際使用的時候，發現隨機聚類的效果略渣，這裡的隨機聚類的意思就是隨便取樣出一些點就把他們當成一個cluster。。wtf
random_clusters=True
if random_clusters：
# We don‘t have to specify the cluster because the CluserNodeGenerator will take
# care of the random clustering for us。
clusters = number_of_clusters
else：
# We are going to use the METIS clustering algorith，
print（“Graph clustering using the METIS algorithm。”）
import metis
lil_adj = G。to_adjacency_matrix（）。tolil（）
adjlist = ［tuple（neighbours） for neighbours in lil_adj。rows］
edgecuts， parts = metis。part_graph（adjlist， number_of_clusters）
parts = np。array（parts）
clusters = ［］
cluster_ids = np。unique（parts）
for cluster_id in cluster_ids：
mask = np。where（parts == cluster_id）
clusters。append（node_ids［mask］）
來自stellargraph的官方的tutorial，裡面也提到了隨機聚類的效果會比較差。這裡一開始隨機聚類的cluster設定為10個cluster，每個epoch合併兩個cluster，多分類auc如下
後面除錯了一下，把cluster的數量設定為105（和下面louvain聚類出來的cluster數量一致進行對比），val acc直接0。5幾了。。。
因為metis的安裝很麻煩，所以這裡就用louvain做cluster測試一下效果。
g=G。to_networkx（）
import community as community_louvain
partition = community_louvain。best_partition（g）
clusters=pd。DataFrame。from_dict（partition，orient=’index‘）。reset_index（）
clusters。columns=［’node‘，’partition‘］
cluster=［］
for i in range（105）：
cluster。append（clusters。query（’partition==@i‘）。node。tolist（））
louvain將cora資料集cluster成了105個clusters。
重新訓練了一下：
效果好多了
