本文轉自徐飛翔的“在圖卷積網絡中的可導池化操作”
版權聲明：本文為博主原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接和本聲明。
這一篇擱了很久了，今天突然想到就順手寫完了吧。之前我們在[1,2,3]中曾經討論過圖卷積網絡的推導，以及其和消息傳遞（message passing）之間的關系，但是我們還沒有討論一個重要問題，那就是在圖卷積網絡中的池化（pooling）操作。池化操作對于一個卷積網絡來說是很重要的，特別是對于節點眾多的大規模圖卷積網絡，池化可以使得網絡的參數大幅度減少，增強泛化性能并且提高模型的層次性結構化特征性能等。如何在圖卷積網絡中定義出如同在卷積網絡中的可導的池化操作呢？單純的聚類操作因為缺乏梯度流，不能實現端到端的訓練而不能直接使用，在文章[4]中提出了DiffPool算子，該算子可以實現圖卷積網絡的可導池化。
poolFig 1. 對于卷積網絡中的池化操作，要怎么才能在圖卷積網絡中找到其合適的替代品呢?DiffPool
DiffPool的思路很簡單，可以用Fig 2表示，其中的 是上一層的輸出特征，而
表示第
層的節點數。其中的DiffPool操作其實很簡單，就是用一個分配矩陣（assign matrix）去進行自動聚類，有：
其中的 就是第
層的分配矩陣，注意到其是一個實矩陣。
Fig 2. DiffPool的示意簡圖。
現在的問題在于分配矩陣如何學習得到，可以認為DiffPool是一個自動端到端聚類的過程，其中分配矩陣代表了該層聚類的結果。如Fig 2所示，我們發現第 層的分配矩陣和特征都是由共同輸入
學習得到的，我們有：
其中的 表示的是由圖卷積單元層疊若干次而成的卷積模塊，其中每一層可以表示為
其中的 表示的是經典的消息傳遞過程，具體見[3]。注意到
的形狀決定了下一層的節點數
，參考公式(3)，這個超參數由
指定，而顯然有
。為了約束分配矩陣的值的范圍，對其進行了概率分布化，也即是
，按論文的說法，是逐行（row-wise）生效的。
在 中則負責特征
的生成，再與分配矩陣
進行DiffPool，見式子(1)，即完成了整個操作。輔助訓練目標
然而據文章說，在實踐中，單純依靠梯度流去訓練可導池化版本的GNN難以收斂，需要加些輔助約束條件。作者加了幾個先驗約束，第一作者認為 一個節點鄰居的節點應該盡可能地池化到一起 (nearby nodes should be pooled together)，通過Frobenius 范數進行約束，有式子(4)
另一個約束是，分配矩陣的應該每一行盡可能是一個one-hot向量，這樣每個聚類結果才能更清晰地被定義出來。通過最小化熵可以對其進行約束，有：
其中 表示對
的第
行求熵（entropy）。作者聲稱在圖分類損失中添加(4)和(5)約束可以有著更好的性能，即便訓練收斂需要更長的時間才能達到。從結果Fig 3中可以發現的確是添加了約束的效果要好些。其中在GraphSAGE的基線上，和其他池化方法（SET2SET，SORTPOOL）的對比說明了DiffPool的有效性和先進性。
Fig 3. 實驗結果圖。More
那么DiffPool得到的分配矩陣結果是否可靠呢？是否可以看成是聚類的結果呢？作者在原文中也提及了這件事兒，并且對池化結果進行了可視化，如Fig 4所示?？梢园l現DiffPool其的確是對節點進行了合理的聚類。
visFig 4. DiffPool結果的可視化，可以形成合理的聚類結果。
就筆者個人的讀后感而已，DiffPool的操作類似于現在流行的自注意學習機制，分配矩陣不妨可以看成是自注意力矩陣對節點進行聚類，也可以認為自注意力機制在圖網絡中也是生效的。
Reference
[1]. https://fesian.blog.csdn.net/article/details/88373506
[2]. https://blog.csdn.net/LoseInVain/article/details/90171863
[3]. https://blog.csdn.net/LoseInVain/article/details/90348807
[4]. Ying, Rex, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. “Hierarchical graph representation learning with differentiable pooling.” arXiv preprint arXiv:1806.08804 (2018).