今天給大家介紹的是TAMU的Hao Yuan等人的一篇論文，該研究針對目前的大多數圖池化技術忽略了圖結構這一可能會引起重要特征丢失的資訊，巧妙地利用可以捕獲不同節點之間的關系的條件随機場，并進一步将能量函數和圖拓撲資訊結合起來完成結構化的預測問題。作者提出的StructPool在多個資料集上的實驗結果顯示了有效性
1
背景
學習圖的進階表示形式對于圖分析任務非常重要。面對很多大型圖資料，除了圖卷積之外，圖池化也是一個很重要的研究領域。在卷積神經網絡（CNN）中池化層夾在連續的卷積層中間，用于壓縮資料和參數的量，并且，池化操作在許多圖像和自然語言處理任務中都顯示了其有效性，是以很自然地池化操作就被引入到了圖資料進行中。一些性能比較好的圖池化方法例如SORTPOOL，TOPKPOOL, DIFFPOOL和SAGPOOL都未明确地對不同節點之間的關系模組化，是以可能會忽略重要的結構資訊。
這篇文章的任務是圖層面的表征學習。作者從Graph pooling的角度出發，指出現有的很多方法并沒有顯示的考慮圖結構的資訊，并将Graph pooling的過程轉化為節點分類，進而其目标變為學習一個聚類配置設定矩陣（cluster assignment matrix）。對于一個節點的分類不僅與這個節點的特征有關，還與其他節點的分類有關，于是作者采用條件随機場的方法來模組化這種關系，并結合圖結構資訊設計吉布斯（Gibbs）能量方程。
2
模型
當原圖中節點i和j經過
跳是可達的時候取值為1，其餘情況為0，充分考慮了在圖中的拓撲資訊，即每個可達節點之間的關系。這兩部分的特征函數都可以通過神經網絡獲得，其中一進制關系可由GCN得到，在傳統的圖像處理任務中，高斯核可以得到兩元關系，但是計算效率低下，是以作者引入注意力機制，注意力矩陣反映了不同向量之間的相似性，用注意力矩陣可以度量成對能量，并且計算量大大降低。
理論上，在經過m次疊代，含有n個節點的大型圖，并且設定i個層的GCN，STRUCTPOOL的時間複雜度約為
3
實驗
實驗是在八個資料集上進行評估STRUCTPOOL，包括五個生物資訊學蛋白質資料集，ENZYMES，PTC，MUTAG，PROTEINS，D＆D以及三個社交網絡資料集，COLLAB，IMDB-B，IMDB-M。選取的大多數資料集規模較大，是以适合評估深圖模型。
将STRUCTPOOL與通過學習節點表示和節點排序的PATCHYSAN、通過GCN并進行全局池化的DCNN，對子結構的潛在表示進行模組化的DGK、節點特征和邊緣資訊執行GCN調節的ECC、通過采用和聚合進行節點嵌入以及采用全局池化的GRAPHSAGE、利用聚合方法來替代深圖網絡中的全局池化操作的SET2SET、利用SORTPOOL的池化政策的DGCNN、基于GRAPHSAGE體系結構建構的DIFFPOOL進行比較。此外，将STRUCTPOOL與三個圖卷積核進行了比較：Graphlet，Shortest-path，WeisfeilerLehman subtree。比較結果如下圖所示：
上表中STRUCTPOOL在6個資料集中的5個都獲得了最佳性能。對于這5個資料集，文章提出的方法的分類結果明顯優于所有比較方法。值得注意的是，STRUCTPOOL在這5個資料集上的表現均比第二好，平均高出3.58％。
為了證明STRUCTPOOL的有效性，将STRUCTPOOL與現有的幾種圖池化技術進行比較。
在六個資料集中的五個中達到了最佳性能，并且明顯優于所有圖池化池技術。
并且在實驗中設定不同的疊代次數m觀察其如何影響預測精度，
我們可以觀察到性能通常随着m的增加而增加，尤其是對于大規模資料集D＆D。我們還觀察到m=5是時間複雜度和預測性能之間的良好折中。值得注意的是，當m=1時，STRUCTPOOL甚至可以勝過其他方法。此外， STRUCTPOOL的運作時間在大型資料集D＆D對于m=1，m=3，m=5，花費時間分别為0.049秒，0.053秒和0.058秒。DIFFPOOL的時間成本為0.042秒，而即使STRUCTPOOL具有相對較高的計算成本，但鑒于其優越的性能，其時間成本可以忽略。
4
總結
作者提出了一種新的圖池化技術，稱為STRUCTPOOL，它是基于條件随機場而開發的。整體是将圖池化視為一個節點聚類問題，并使用CRF在不同節點的配置設定之間建立關系。此外，通過結合圖拓撲資訊來推廣這個方法，使得STRUCTPOOL可以控制CRF中的成對團集。