具有高標籤利用率的圖濾波半監督學習方法

本文解讀了一篇被CVPR2019大會接收的半監督學習方向的論文,點擊此處跳轉至arXiv查看原文。在之前AI研習社直播的CVPR論文分享會上，論文的作者之一吳曉明老師做了現場分享，大家可以將第一個回放視頻跳轉到1:59:23處聽吳老師的現場講解。本文基於論文原文和老師的PPT對文章內容進行了重新梳理和解讀，詳略適中，希望對大家有幫助。

《Label-Efficient Semi-Supervised Learning via Graph Filtering》一文研究了半監督學習問題，作者們提出了一種基於圖濾波的半監督學習框架，並利用該框架對兩種典型的圖半監督分類方法LP和GCN進行了改進，新的方法不僅能同時利用圖的連接信息和節點的特徵信息，還能提高標籤的利用效率，文中提出的改進方法在所有的實驗數據集上都取得了最好的效果。作者用圖濾波框架統一了看起來完全不同的LP和GCN，其「低通濾波」的觀點精鍊地解釋了這兩種方法在實際應用中奏效的原因，提高了研究者對於此類方法的認知水平。下文將按以下目錄安排,大家可以點擊鏈接快速跳轉到自己關注的部分：
  • 1. 預備知識
    • 1.1 目標問題
    • 1.2 圖的頻譜分析
    • 1.3 圖卷積濾波
    • 1.4 圖濾波與半監督分類
  • 2. 動機
  • 3. 方法
    • 3.1 圖濾波與LP
      • 1) 原始LP演算法
      • 2) 圖濾波視角下的LP
      • 3) 廣義標籤傳播GLP
    • 3.2 圖濾波與GCN
      • 1) 原始GCN
      • 2) 圖濾波視角下的GCN
      • 3) 圖濾波增強版GCN
  • 4. 實現與驗證
    • 4.1 平滑力度與計算性能
    • 4.2 半監督分類任務對比
    • 4.3 Zero-Shot半監督回歸任務對比
  • 5. 總結

1.預備知識

1.1 目標問題

圖半監督分類問題即給定圖G、圖信號矩陣X以及節點標籤矩陣Y（稀疏矩陣，只有部分節點有標籤）要求輸出標籤矩陣Y』（給出每個節點的類別），以下圖為例：

圖中的節點1、3、4為有標記的節點、節點2為未標記的節點。每個節點對應一個特徵向量x_ix?i??，半監督分類的目的就是利用所有節點的特徵和已標記節點的標籤來預測未標記節點(節點2)的類別。

圖半監督分類根據節點之間的相似度來分配標籤，節點間的相似度越高，其類別相同的概率就越高，於是便可以將其中一個節點的類別賦予另一節點。節點的相似性不僅由圖的連接結構反映，也可能被節點的特徵隱式的表達，所以只有綜合利用節點的連接信息和特徵信息才能得到更好的相似度表徵，進而提高標籤分配的正確率。

1.2 圖的頻譜分析

一個無向圖可以用拉普拉斯矩陣L表示，對L進行特徵分解可以得到一組標準正交的特徵向量（可以組成標準正交基和正交矩陣），每個特徵向量phi_i??i??都有對應的特徵值lambda_iλ?i??。在圖信號處理領域中，這組標準正交基被稱為圖的傅里葉基(Fourier Basis)對應的特徵值代表這個基信號的頻率(Frequency)。相關定義見下式：

其中W為圖的鄰接矩陣，D為度矩陣PhiΦ是L的特徵向量按列排列而成的正交矩陣，LambdaΛ是L的特徵向量組成的對角矩陣。值得注意的是，拉普拉斯矩陣有多種定義，以上第一個公式的定義只是最原始的一種。另外還有歸一化的拉普拉斯和對稱歸一化的拉普拉斯定義如下：

它們的區別主要在「對稱」和「歸一化」上，差別並不是很大，為了避免讀者混淆所以此處先將它們都列舉出來。圖信號的頻率反映了它的變化程度，低頻的信號較平滑，相鄰節點的信號值相似度高，而高頻信號的變化較為劇烈，相鄰節點的信號值可能差異較大。頻譜分析的目的是將複雜信號分解成某種相對簡單的基本信號的線性組合，通過研究這些簡單信號的性質及它們在原始信號中的佔比就能推測出原始信號的性質，這是化繁為簡、化大為小的解構主義哲學的體現。例如一維傅里葉變換將一維信號分解成復指數函數的線性組合（離散信號）或積分求和（連續信號）。而常用的二維圖像DCT變換將圖片分解成餘弦基信號的線性組合。

類似的，在將此概念推廣到圖信號處理領域，基信號變成了拉普拉斯矩陣的特徵向量phi_i??i??,而任意的圖信號都可以被表示成phi_i??i??的線性組合（標準正交基的線性組合可以表示n維空間中的所有向量）。

圖信號(graph signal)就是在圖上定義的信號，圖中的每一個節點都對應著一個實數值，可以用向量f in R^{n imes 1}f∈R?n×1??表示一個圖信號,其中n代表圖節點的個數。多變數的圖信號或者說多維的圖信號可以用矩陣X in R^{n imes m}X∈R?n×m??表示，此時每個圖節點都對應一個長度為m的一維向量，該向量表示節點的特徵。

1.3 圖卷積濾波

所謂「濾波」是指過濾掉信號頻譜中的特定成分，比如說常見的低通濾波就是指盡量保留信號的低頻成分並過濾掉其高頻成分。可以將濾波看做一個信號映射函數，該函數接收一個原始信號並輸出過濾後的信號。濾波一般通過在原始信號上乘以濾波器實現，論文中定義了如下的圖卷積濾波器：

其中，函數p(lambda_i)p(λ?i??)被稱為頻率響應函數。使用此卷積過濾器對圖信號f進行卷積可得：

可以發現，濾波信號ar f?f?ˉ??中每一個基信號phi_i??i??的比例c_ic?i??都被函數p(lambda_i)p(λ?i??)縮放了。頻率響應函數控制著濾波器對不同頻率的基信號的響應，我們可以設計不同性質的頻率響應函數滿足不同場景的濾波需求。

1.4 圖濾波與半監督分類

圖半監督分類的基本假設是「相鄰節點的標籤相似」，這意味著我們希望有標記節點周圍的圖信號是平滑的、低頻的，我們期望學到低頻的表示信號，所以應該使用具有低通性質的濾波器和頻率響應函數。作者就是用這種「低通圖濾波」的視角統一解釋了LP和GCN並基於此做出了有效的改進。

2. 動機

經典的Label Propagation演算法只能利用圖的結構信息，無法利用節點的特徵。而新興的Graph Convolution Network需要大量的Label用來訓練和驗證，但半監督學習任務的標籤數量本來就少，所以GCN在標籤數據較少的情況下可能難以奏效，因為它的標籤利用效率是低下的。為了解決LP不能利用節點特徵的問題，作者對其做出了改進並提出GLP。為了解決GCN模型複雜度較高且標籤利用率較低的問題，作者對其進行了改並進提出IGCN。兩種方法都是在圖濾波的框架下提出，在理論上可以被統一的解釋，在實踐中也都有很好的效果。

3. 方法介紹

3.1 圖濾波與LP

1) 原始LP演算法

標籤傳播演算法（Lable Propagation）簡稱LP，是一種簡單有效的圖半監督學習方法，在科研和工業實踐中均被廣泛應用。LP的目的是得到一個能滿足真實標籤矩陣Y同時在圖上又足夠平滑的預測/嵌入矩陣Z。LP模型的優化目標如下：

其中矩陣Z in R^{n imes l}Z∈R?n×l??，其中ll表示類別的個數，矩陣的每一行表示一個節點的多類別預測概率(也可以視為節點嵌入向量)。優化目標的第一項約束預測矩陣與真實標籤矩陣的誤差儘可能小，第二項約束目標矩陣ZZ在圖上的變換盡量平滑，被稱為拉普拉斯正則項，正則的力度用參數alphaα控制。這是一個無約束的二次優化問題，有解析解：

得到ZZ之後，可以直接選擇每一行中取值最大的一類作為節點的類別，或者在此之前多做一步列歸一化的操作。

2) 圖濾波視角下的LP

若從圖濾波的視角看,可將LP演算法分成3大部分：

滿足上文中卷積濾波器的定義，被稱為自回歸（Auto-Regressive）濾波器，其激活響應函數為：

從下圖來看，自回歸濾波器顯然是低通的、抑制高頻的，其平滑力度隨alphaα的增大而增大。

3) 推廣的標籤傳播演算法GLP

作者將圖濾波視角下LP的三大組件進行了推廣泛化，提出了廣義標籤傳播演算法（Generalized Label Propagation）GLP。具體推廣如下：

1.圖信號：使用所有節點的特徵向量組成的特徵矩陣X作為輸入信號

2.濾波器：可以是任意滿足定義的低通圖卷積濾波器

3.分類器：可以是在帶標籤節點的嵌入表徵上訓練得到的任意分類器

這個推廣非常自然，也很容易理解，最關鍵的步驟是對節點特徵矩陣進行低通圖濾波。這一步可以視為特徵提取過程，作者利用低通濾波器提取出了更平滑的數據表徵，並且同時考慮了圖的連接信息和節點特徵信息，彌補了原始LP無法利用節點特徵的缺陷。而濾波器與分類器的推廣泛化則大大提高了演算法的靈活性，使GLP很容易就能整合到不同的問題領域。

3.2 圖濾波與GCN

1) 原始GCN

GCN是一種在頻譜上定義的圖卷積網路，它簡單有效，在半監督分類問題上有優異的表現。GCN首先對鄰接矩陣加入自連接並進行對稱歸一化得到重歸一化矩陣 ilde W_s?W?~???s??:

第一個式子相當於引入了各節點到自身的連接，第二個式子中 ilde W_s?W?~???s??是矩陣 ilde W?W?~??的對稱歸一化拉普拉斯矩陣。基於 ilde W_s?W?~???s??，原文作者定義GCN的層級傳播過程為：

其中H^{(t)}H?(t)??表示第t層的輸入，Theta^{(t)}Θ?(t)??是第t層的待學習參數，sigmaσ可以是神經網路中的各種激活函數。

一層圖卷積先對輸入信號左乘以重歸一化矩陣 ilde W_s?W?~???s??，然後再使用參數矩陣ThetaΘ進行投射變換，最後使用激活函數進行非線性變換。堆疊多個圖卷積層後最後使用softmax激活函數進行分類，比如雙層圖卷積：

可以使用反向傳播演算法對此GCN進行訓練得到最終模型。

2) 圖濾波視角下的GCN

從雙層GCN的式子中可以看到，GCN其實就是不斷地重複著1) 左乘 2)投射變換 3)激活變換 三個步驟。其中投射變換和激活變換是普通神經網路中的通用操作，而「左乘」重歸一化矩陣可以看做對輸入信號進行圖濾波，因為重歸一化矩陣滿足：

其中 ilde L?L?~??為矩陣 ilde W?W?~??的對稱歸一化拉普拉斯。濾波器 ilde W_s?W?~???s??對應的頻率響應函數為：

如果我們將雙層GCN中3個操作的順序稍微替換一下，將兩個圖濾波步驟全部放在第一層，比如：

從下圖可以看到，該濾波器在[0,1]區間內是低通濾波器，且其低通程度隨k的增大而增大。所以多層GCN的濾波器比單層GCN的濾波器更加低通，平滑力度更大。

在圖濾波的視角下，我們可以用頻率響應函數的性質來解釋GCN 1) 使用對稱化歸一化拉普拉斯定義 2) 使用重歸一化技巧(添加自連接) 的原因。採用對稱歸一化拉普拉斯矩陣可以將特徵值的取值範圍限制在[0, 2]之間，而重歸一化技巧可以將特徵值的取值範圍進一步縮小，這促使濾波器越來越接近於完全低通。 作者在Cora數據集上對重歸一化前後GCN的頻率響應函數進行了可視化，如下圖所示：

可以看到，無論是單層還是雙層，重歸一化後的拉普拉斯矩陣的特徵值都被限制到了1.5以內，驗證了作者們對於重歸一化技巧在應用中奏效的解釋。事實上，可以證明重歸一化技巧能使拉普拉斯矩陣的特徵值範圍壓縮到區間：

其中d_md?m??表示圖中節點度（Degree）的最大值，lambda_mλ?m??為對稱歸一化拉普拉斯矩陣的最大特徵值。

3) 圖濾波增強版GCN

雖然堆疊多個GCN層可以增加濾波的平滑力度，但也會引入更多待學習參數，這使得網路需要更多的數據訓練以避免過擬合。為了解決這個問題作者提出了IGCN（Improved Graph Convolutional Network）。IGCN將GCN中的重歸一化矩陣全部替換成了重歸一化濾波器，即：

作者稱濾波器:

為重歸一化（Renormalization）濾波器，其頻率響應函數為：

顯然，IGCN可以通過調節k來直接控制濾波的平滑力度且不會引入額外的待學習參數，這可以使模型維持在淺層水平，無需過多數據即可達到理想的訓練效果，提高了模型的標籤利用效率。

4. 實現與驗證

4.1 平滑力度與計算性能

無論是GLP還是IGCN，都可以通過控制參數或者參數k來控制濾波的平滑力度，那麼應該如何根據應用場景調整平滑力度呢？作者指出數據集的標籤率是調整平滑力度的一個關鍵參考，當標籤率較小時平滑力度應該較大，以使較遠的無標籤節點也能與有標籤節點獲得相似的特徵表示；當標籤率較大時，平滑的力度應該較小，標籤的傳播範圍不宜太遠，以保持特徵的多樣性。作者使用不同平滑力度的RNM濾波器在Cora數據集上做了實驗並做了t-SNE可視化，其結果如下：

可以發現，隨著平滑的力度增大，濾波結果的類簇變得越來越緊湊，簇間距越來越大，分類邊界也變得更加清晰，此時只需要少量的標籤便可以進行分類，這就直觀地解釋了平滑力度設置與數據標籤率之間的關係。

除了平滑力度外，文中還討論了兩種濾波器的計算性能。由於AR濾波器涉及到了運算代價很高的矩陣求逆運算，作者使用k階展開多項式來進行近似以降低計算複雜度。對於k階RNM濾波器，可以利用拉普拉斯矩陣在實際應用中往往是稀疏的特性來進行計算加速。作者在文中分析了兩種濾波器在理論上的計算複雜度，旨在說明其實用性。

4.2 半監督分類任務實驗對比

作者在4個引文網路數據集和1個知識圖譜數據集上進行了半監督分類任務的實驗，並與許多出色的模型進行對比，包括Youshua Bengio團隊的GAT。幾個數據集的節點規模、類別數量以及特徵數量均不相同，這樣的實驗安排能夠衡量模型在各種場景下的表現，比較全面。各數據集的統計指標如下表：

為了方便了解數據的量級，我使用k（千）和w（萬）對數據進行了簡化表示。除了選用不同規模的數據集，作者還為數據集設置了不同的標籤率以觀察平滑力度與標籤率之間的關係，其設定如下表：

各模型在各數據集上的分類正確率如下：

實驗結果顯示，經圖濾波改造的方法在所有場景下的表現均優於其他對比模型。但從運行時間上來看，GLP與IGCN的耗時顯然要更多一些，在規模較大的NELL數據集上最為明顯，不過總的來說是在可接受範圍內的。

4.3 Zero-Shot半監督回歸任務實驗對比

除了分類，GLP和IGCN還可以用於半監督回歸。2018年CVPR的一篇論文使用GCN做了0樣本圖片識別（Zero-Shot image recognition）任務，即只使用類別的文字描述和類別之間的關係為沒有任何訓練樣本的類別(Unseen Class)學習一個視覺分類器。該文在給定一個已知類別的分類器的前提下，使用每個類別的文字描述嵌入特徵和類別關係作為輸入，並以已知分類器最後一層的權重為回歸目標訓練了一個6層的GCN，然後將GCN的輸出作為未知類別的分類器最後一層的權重，並使用新的權重組成分類器對所有類別進行預測。該文將Zero-Shot學習巧妙的轉化成了圖半監督回歸問題，這使許多半監督回歸方法都能應用於0樣本學習任務，該文方法（GCNZ）的整體流程如下圖所示：

作者使用GLP和IGCN替換了此文中的GCN，並在AWA2數據集上使用一個預訓練的ResNet-50網路進行了0樣本學習任務的實驗，各模型的性能對比結果如下表：

可以看到，IGCN的效果最好。由於GCNZ在發表時已經是State-of-the-art級別了，其核心組件是GCN，而GLP和IGCN又比GCN效果好，所以對於它們在0樣本圖片識別任務上的提升是有預期的了，這個實驗說明了圖濾波方法應用的廣泛性。作者已將源代碼公布至其github倉庫

5. 總結

總的來說，圖濾波的想法是又簡潔又實用的，雖然看起來簡單但是理解卻很深刻，有很強的理論指導意義和實踐意義。合上這篇論文，只需記住「低通濾波」四字精髓。由於半監督分類問題是追求平滑和低通的，所以文章就以低通濾波為例為我們展示了圖濾波的簡潔和強大，但圖濾波的框架和思想在「非低通」的問題上也是一貫適用的，例如我們可以設計中通的、高通的濾波器來解決相關的問題。我認為這篇論文的重要貢獻是給圖半監督學習打開了思路，提供了一條寬闊的路線，相信基於圖濾波還可以做不少文章。我從這篇文章再次感受到了對原理的思考與探索的重要性，所有的改進和提升都離不開對原理和運作機制更深的了解。希望日後能在CVPR上看到更多有洞見的，有強解釋性的文章。

以上解讀為本人 @月本誠 在AI研習社CVPR小組原創首發，我已經努力保證解讀的觀點正確、精準，但本人畢竟才學疏淺，文中若有不足之處歡迎大家批評指正。所有方法的解釋權歸原始論文作者所有。

同時CVPR 2019 Oral 論文精選匯總，值得一看的 CV 論文都在這裡，等你來看噢（持續更新中）

AI研習社 - 研習AI產學研新知，助力AI學術開發者成長。?

ai.yanxishe.com

歡迎大家前往AI研習社學習交流~


推薦閱讀：
相关文章