論文鏈接：https://arxiv.org/pdf/1812.04202.pdf
關(guān)于圖卷積：論文筆記-Deep Learning on Graphs: A Survey（上）
4.2 讀出操作
使用圖卷積操作，可以學習有用的節(jié)點特征來解決許多以節(jié)點為中心的任務(wù)。然而，為了解決以圖為中心的任務(wù)，需要聚合節(jié)點信息以形成圖級表示。在文獻中，這種程序通常稱為讀出操作（readout operation）。
讀出操作也與圖的粗化（graph coarsening）有關(guān)，（將一個較大的圖縮小為一個較小的圖），因為可以通過將圖粗化為單個節(jié)點來獲得圖形級表示。
CNN可以進行多級卷積或池運算，降低分辨率。但圖缺乏網(wǎng)格結(jié)構(gòu)，無法直接使用。
圖讀出操作的一個關(guān)鍵要求，該操作應(yīng)該對節(jié)點順序保持不變，即，如果我們使用兩個節(jié)點集之間的雙射函數(shù)更改節(jié)點和邊的索引，則整個圖的表示不應(yīng)改變。
4.2.1 統(tǒng)計學
最簡單的順序不變的操作就是統(tǒng)計運算，比如求和、求平均或者 max-pooling。
另一種聚合節(jié)點表示的常用方法是添加一個全連接（FC）層作為最終層。這種方法的優(yōu)點是模型可以為不同的節(jié)點學習不同的權(quán)重；然而，這種方法無法保證順序不變性。
4.2.2 層次聚類
除了節(jié)點和圖級結(jié)構(gòu)之外，圖還表現(xiàn)出豐富的層次結(jié)構(gòu) ，可以通過層次聚類方法進行探索。例如，基于密度的 agglomerative clustering，multi-resolution spectral clustering。 Cheb-Net 和 MoNet 采用了另一種貪心分層聚類算法 Graclus ，一次合并兩個節(jié)點，并采用快速池化方法將節(jié)點重新排列為平衡二叉樹。 ECC 通過特征分解進行分層聚類。然而，這些層次聚類方法都獨立于圖卷積（即，它們可以作為預(yù)處理步驟執(zhí)行，而不是以端到端的方式進行訓練）。
DiffPool 提出了一種與圖卷積聯(lián)合訓練的可微層次聚類算法，作者提出使用隱藏表示來學習每一層的 soft cluster assignment matrix:
這個“粗化”圖的節(jié)點表示和新的鄰接矩陣可以通過根據(jù)取平均獲得:
其中 是通過對
圖卷積得到的。初始節(jié)點數(shù)
，最后一層
，即單個節(jié)點代表整個圖。
由于集群分配操作是軟的，集群之間的連接不是稀疏的；因此，該方法的時間復(fù)雜度原則上為 O（N2）。
什么是 soft clustering？
傳統(tǒng)的聚類算法會將一個點分配到一個聚類，這種分配是一種硬分配（hard assignment），如果一個點到第一個聚類中心和到第二個聚類中心的距離一樣，但是被分配到了第一個聚類，那么它就不會出現(xiàn)在第二個聚類里。
而軟聚類（soft assignment）為每個點分配一個概率向量，而不是一個固定的標簽。向量的長度等于找到的聚類數(shù)。向量的第 i個概率值是該點屬于第 i 個集群成員的概率。
簡而言之，平均或求和等統(tǒng)計數(shù)據(jù)是最簡單的讀出操作，而與圖卷積聯(lián)合訓練的層次聚類算法更先進，但也更復(fù)雜。還有一些其他方法，例如添加偽節(jié)點或強加節(jié)點順序等。
4.3 改進方法
4.3.1 Attention 機制
在GCN中，節(jié)點鄰域以相等或預(yù)定義的權(quán)重聚集。然而，鄰居的影響可能會有很大差異。受 Attention 機制的啟發(fā)，GAT （graph attention networ）通過修改式（13）中的卷積運算，將注意機制引入GCN，如下：
其中 是在第 l 層的節(jié)點
對節(jié)點
的attention：
這里的 是另一個需要學習的函數(shù)，比如多層感知器（MLP）。為了提高模型的容量和穩(wěn)定性，作者還建議使用多個獨立注意并連接結(jié)果，即多頭注意機制，如下圖。
HAN 為異構(gòu)圖提出了一種兩級注意機制，即節(jié)點級和語義級注意機制。具體來說，節(jié)點級注意力機制類似于 GAT，但也考慮了節(jié)點類型；因此，它可以為聚合基于元路徑（meta-path）的鄰居分配不同的權(quán)重。然后語義級注意力學習不同元路徑的重要性并輸出最終結(jié)果。
4.3.2 Residual 與Jumping
許多研究觀察到，現(xiàn)有 GCN 最合適的深度通常非常有限，例如 2 層或 3 層。這個問題可能是由于訓練深度 GCN 所涉及的實際困難或過度平滑問題，即更深層中的所有節(jié)點具有相同的表示。為了解決這個問題，可以將類似于 ResNet 的殘差連接添加到 GCN，通過實驗表明，添加殘差連接可以讓網(wǎng)絡(luò)的深度增加，這與 ResNet 的結(jié)果類似：
Column network（CLN）采用了類似的思想，使用了以下具有可學習權(quán)重的殘差連接：
受個性化 PageRank 的啟發(fā)，PPNP 定義了具有連接到初始層的圖卷積：
其中 和
是一個超參數(shù)。所有參數(shù)都在
中，而不是在圖卷積中。
Jumping knowledge networks（JK-Nets）提出了另一種架構(gòu)，將網(wǎng)絡(luò)的最后一層與所有之前的隱藏層連接，將所有的表示“跳轉(zhuǎn)”到最終的輸出，通過這種方式，模型可以學習選擇性地利用來自不同層的信息。JK-Nets 的公式如下：
JK-Nets使用了三個與 GraphSAGE 類似的聚合函數(shù)：concatenation、max-pooling 和 LSTM attention。實驗結(jié)果表明，增加 jumping connection 可以提高多個GCN的性能。
4.3.3 Edge Features
對于具有離散值的簡單邊緣特征，如 edge type，一種簡單的方法是針對不同的邊緣類型訓練不同的參數(shù)并聚合結(jié)果。
DCNN 提出了另一種方法，將每個邊轉(zhuǎn)換為連接到該邊的頭和尾節(jié)點的節(jié)點。經(jīng)過這種轉(zhuǎn)換，邊特征可以被視為節(jié)點特征。
LGCN 構(gòu)建了一個線圖 以結(jié)合邊的特征。線圖中的節(jié)點是原始圖中的有向邊，如果信息可以通過原始圖中相應(yīng)的邊流動，則線圖中的兩個節(jié)點是連接的。然后，LGCN采用了兩個GCN：一個在原始圖上，一個在線圖上。
