本文轉(zhuǎn)自徐飛翔的“在圖卷積網(wǎng)絡(luò)中的可導(dǎo)池化操作”
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明。
這一篇擱了很久了，今天突然想到就順手寫完了吧。之前我們?cè)赱1,2,3]中曾經(jīng)討論過圖卷積網(wǎng)絡(luò)的推導(dǎo)，以及其和消息傳遞（message passing）之間的關(guān)系，但是我們還沒有討論一個(gè)重要問題，那就是在圖卷積網(wǎng)絡(luò)中的池化（pooling）操作。池化操作對(duì)于一個(gè)卷積網(wǎng)絡(luò)來說是很重要的，特別是對(duì)于節(jié)點(diǎn)眾多的大規(guī)模圖卷積網(wǎng)絡(luò)，池化可以使得網(wǎng)絡(luò)的參數(shù)大幅度減少，增強(qiáng)泛化性能并且提高模型的層次性結(jié)構(gòu)化特征性能等。如何在圖卷積網(wǎng)絡(luò)中定義出如同在卷積網(wǎng)絡(luò)中的可導(dǎo)的池化操作呢？單純的聚類操作因?yàn)槿狈μ荻攘?，不能?shí)現(xiàn)端到端的訓(xùn)練而不能直接使用，在文章[4]中提出了DiffPool算子，該算子可以實(shí)現(xiàn)圖卷積網(wǎng)絡(luò)的可導(dǎo)池化。
poolFig 1. 對(duì)于卷積網(wǎng)絡(luò)中的池化操作，要怎么才能在圖卷積網(wǎng)絡(luò)中找到其合適的替代品呢?DiffPool
DiffPool的思路很簡(jiǎn)單，可以用Fig 2表示，其中的 是上一層的輸出特征，而
表示第
層的節(jié)點(diǎn)數(shù)。其中的DiffPool操作其實(shí)很簡(jiǎn)單，就是用一個(gè)分配矩陣（assign matrix）去進(jìn)行自動(dòng)聚類，有：
其中的 就是第
層的分配矩陣，注意到其是一個(gè)實(shí)矩陣。
Fig 2. DiffPool的示意簡(jiǎn)圖。
現(xiàn)在的問題在于分配矩陣如何學(xué)習(xí)得到，可以認(rèn)為DiffPool是一個(gè)自動(dòng)端到端聚類的過程，其中分配矩陣代表了該層聚類的結(jié)果。如Fig 2所示，我們發(fā)現(xiàn)第 層的分配矩陣和特征都是由共同輸入
學(xué)習(xí)得到的，我們有：
其中的 表示的是由圖卷積單元層疊若干次而成的卷積模塊，其中每一層可以表示為
其中的 表示的是經(jīng)典的消息傳遞過程，具體見[3]。注意到
的形狀決定了下一層的節(jié)點(diǎn)數(shù)
，參考公式(3)，這個(gè)超參數(shù)由
指定，而顯然有
。為了約束分配矩陣的值的范圍，對(duì)其進(jìn)行了概率分布化，也即是
，按論文的說法，是逐行（row-wise）生效的。
在 中則負(fù)責(zé)特征
的生成，再與分配矩陣
進(jìn)行DiffPool，見式子(1)，即完成了整個(gè)操作。輔助訓(xùn)練目標(biāo)
然而據(jù)文章說，在實(shí)踐中，單純依靠梯度流去訓(xùn)練可導(dǎo)池化版本的GNN難以收斂，需要加些輔助約束條件。作者加了幾個(gè)先驗(yàn)約束，第一作者認(rèn)為 一個(gè)節(jié)點(diǎn)鄰居的節(jié)點(diǎn)應(yīng)該盡可能地池化到一起 (nearby nodes should be pooled together)，通過Frobenius 范數(shù)進(jìn)行約束，有式子(4)
另一個(gè)約束是，分配矩陣的應(yīng)該每一行盡可能是一個(gè)one-hot向量，這樣每個(gè)聚類結(jié)果才能更清晰地被定義出來。通過最小化熵可以對(duì)其進(jìn)行約束，有：
其中 表示對(duì)
的第
行求熵（entropy）。作者聲稱在圖分類損失中添加(4)和(5)約束可以有著更好的性能，即便訓(xùn)練收斂需要更長(zhǎng)的時(shí)間才能達(dá)到。從結(jié)果Fig 3中可以發(fā)現(xiàn)的確是添加了約束的效果要好些。其中在GraphSAGE的基線上，和其他池化方法（SET2SET，SORTPOOL）的對(duì)比說明了DiffPool的有效性和先進(jìn)性。
Fig 3. 實(shí)驗(yàn)結(jié)果圖。More
那么DiffPool得到的分配矩陣結(jié)果是否可靠呢？是否可以看成是聚類的結(jié)果呢？作者在原文中也提及了這件事兒，并且對(duì)池化結(jié)果進(jìn)行了可視化，如Fig 4所示?？梢园l(fā)現(xiàn)DiffPool其的確是對(duì)節(jié)點(diǎn)進(jìn)行了合理的聚類。
visFig 4. DiffPool結(jié)果的可視化，可以形成合理的聚類結(jié)果。
就筆者個(gè)人的讀后感而已，DiffPool的操作類似于現(xiàn)在流行的自注意學(xué)習(xí)機(jī)制，分配矩陣不妨可以看成是自注意力矩陣對(duì)節(jié)點(diǎn)進(jìn)行聚類，也可以認(rèn)為自注意力機(jī)制在圖網(wǎng)絡(luò)中也是生效的。
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).