基于圖過濾框架對圖卷積濾波器靈活性的研究

徐鑫強,何 鵬,2

(1.湖北大學計算機與信息工程學院,湖北 武漢 430062; 2.湖北省應用數(shù)學重點實驗室,湖北 武漢 430062)

0 引 言

近幾年，為了更有效地處理圖數(shù)據(jù)，研究人員提出了圖卷積神經(jīng)網(wǎng)絡(Graph Convolutional Network)方法，它在圖數(shù)據(jù)的結(jié)點嵌入表征學習中表現(xiàn)出了強大的建模能力。不同于傳統(tǒng)的基線算法(DeepWalk[1]、GraRep[2])，它將卷積神經(jīng)網(wǎng)絡遷移到圖結(jié)構(gòu)上，進行端到端的學習，而且已經(jīng)在許多場景下取得了顯著的效果，例如在推薦系統(tǒng)、交通預測、網(wǎng)絡分析等領(lǐng)域的成功應用。圖卷積神經(jīng)網(wǎng)絡的出現(xiàn)，極大地提高了人們對此類數(shù)據(jù)的信息挖掘能力，因此正受到人們越來越多的關(guān)注和研究。

圖卷積神經(jīng)網(wǎng)絡的最新進展可分為譜方法和空間方法2類。譜方法利用圖上卷積定理從頻譜域定義圖卷積，借助于圖譜理論來實現(xiàn)拓撲圖上的卷積操作；空間方法從結(jié)點域出發(fā)，直接將卷積操作定義在每個結(jié)點的連接關(guān)系上，利用聚合函數(shù)來聚合每個中心結(jié)點和其鄰近結(jié)點，它和傳統(tǒng)的卷積神經(jīng)網(wǎng)絡中的卷積更相似些。譜卷積神經(jīng)網(wǎng)絡通過對圖信號進行傅里葉變換進入譜域，基于卷積定理構(gòu)建可學習的卷積核以實現(xiàn)圖卷積，它避免了在空間域因圖數(shù)據(jù)不滿足平移不變性而造成卷積核定義困難的問題。卷積核刻畫了結(jié)點的局部結(jié)構(gòu)，在損失函數(shù)指導下利用梯度反向回傳學習卷積核，基于譜域的卷積操作將網(wǎng)絡的拓撲結(jié)構(gòu)和結(jié)點的屬性等特征用神經(jīng)網(wǎng)絡進行捕獲，從而完成結(jié)點之間的信息聚合，最終更新結(jié)點的相似度表征，并服務于后續(xù)任務，例如結(jié)點分類、鏈路預測等。因此，卷積核對圖卷積神經(jīng)網(wǎng)絡的特征提取效果起著至關(guān)重要的作用。而不同的圖數(shù)據(jù)需要進行差異化的圖信號處理，為了在實際情況中應對場景不同給圖卷積模型性能發(fā)揮帶來的限制，需要提高卷積核的靈活性，具體來說，就是如何設(shè)計一個更好的卷積核，以便在應對各種圖數(shù)據(jù)時，都可以精確捕獲圖結(jié)構(gòu)以及其他信息(尤其是數(shù)據(jù)特征)來獲得結(jié)點的相似度表征。

盡管以前研究已取得了許多進展，但在現(xiàn)有方法的基礎(chǔ)上仍可以做些有益的嘗試和拓展。基于圖譜理論的圖卷積網(wǎng)絡(GCN[3])表現(xiàn)出令人印象深刻的效果。GCN的成功啟發(fā)了許多關(guān)于半監(jiān)督學習的圖神經(jīng)網(wǎng)絡的后續(xù)工作，這是由于其特殊設(shè)計的一階卷積濾波器可以非常有效地對結(jié)點的連接信息和特征信息同時進行學習以獲得結(jié)點相似度表征。但是由于其并未過多地考慮圖的特性，在不同應用場景上濾波器顯得靈活性不夠，例如，當對于只含有很少量標簽的圖時，表征學習的分類準確度會有所下降[4]。最近，GCN的改進模型IGCN(Improved Graph Convolutional Network)[4]從圖濾波框架的角度研究了圖數(shù)據(jù)上的卷積操作。其基本思想是將數(shù)據(jù)特征作為信號放在編碼數(shù)據(jù)樣本之間關(guān)系的基礎(chǔ)圖上，并在該圖上使用適當?shù)牡屯▓D卷積濾波器以生成平滑且具有代表性的特征。平滑是對圖信號進行低通濾波，濾除其劇烈變化的部分(高頻信號)，使得相鄰結(jié)點表征在不斷融合中更為相似。它通過在GCN濾波器上引入指數(shù)參數(shù)k來實現(xiàn)對濾波器強度的控制，增大k值，可以提高濾波器的平滑力度，模型靈活性得到有效增強。但應注意到調(diào)整指數(shù)參數(shù)也會帶來一定的時間損失(時間復雜度和指數(shù)呈線性關(guān)系)[4]。

本文在IGCN的基礎(chǔ)上引入濾波器頻率響應函數(shù)的平移參數(shù)μ，讓此類濾波器在指數(shù)參數(shù)一定的情況下，還具有另一種可調(diào)控濾波器平滑力度的途徑。模型通過在有效范圍內(nèi)控制μ達到了增強濾波器靈活性的目的，且不需要增加額外的神經(jīng)網(wǎng)絡可訓練權(quán)重數(shù)量，保持了模型的淺層結(jié)構(gòu)。同時，本文在圖過濾框架下詳細解釋了平衡參數(shù)的作用原理并從圖劃分的角度提供了更為全面的見解。需要指出的是，IGCN已經(jīng)表現(xiàn)出優(yōu)異的學習效果，當已經(jīng)能為結(jié)點學習到較合適的特征表示時，加入平衡參數(shù)只在微小范圍內(nèi)再根據(jù)具體的濾波需求對濾波器實施微調(diào)操作，但當濾波器的平滑力度不足以產(chǎn)生較好的相似度表征時，只控制平衡參數(shù)μ也可以顯著地提升平滑效果。

基于聚類假設(shè)，本文分別在3個引文網(wǎng)絡和1個知識圖譜數(shù)據(jù)集上使用雙層圖卷積神經(jīng)網(wǎng)絡開展了半監(jiān)督的圖嵌入學習實驗。通過設(shè)置多段平移參數(shù)值進行數(shù)值實驗，并通過實驗分析得出網(wǎng)絡的稀疏程度是平衡參數(shù)μ取值的一個重要參考因素。實驗結(jié)果顯示，在時間不損失的情況下，基于二階濾波器，在小規(guī)模的引文網(wǎng)絡上，半監(jiān)督分類的準確率優(yōu)于最新的IGCN模型。另外在較大規(guī)模的知識圖譜數(shù)據(jù)集上，利用參數(shù)μ可使濾波器在k=2的情況下，實現(xiàn)優(yōu)于IGCN中使用指數(shù)參數(shù)k=5時的分類效果，即平衡參數(shù)μ是除了指數(shù)參數(shù)k外另一個控制濾波器平滑力度的重要參數(shù)。最后本文經(jīng)過合理性分析,將引入平衡參數(shù)的做法推廣到更高階的低通濾波器上。

1 圖過濾

本章將介紹圖信號、圖濾波和圖卷積濾波器的概念。

1.1 定義1(圖信號)

圖信號是圖的頂點集V上的實值函數(shù)f:V→R,可以向量形式表示為f=(f(v1),…,f(vn))T。任何圖形信號f都可以分解為基本信號(φi)1≤i≤n的線性組合：

(1)

其中，C=(c1,…,cn)T,ci是φi的系數(shù)。系數(shù)ci的大小表示信號f中呈現(xiàn)的基本信號φi的強度，值越大，表示基本信號φi對信號f的特征表現(xiàn)貢獻越大。與較低頻率相關(guān)的基本信號在圖形上更平滑[6]，即高頻基信號φi(大特征值)代表的是圖信號中劇烈變化的部分，低頻基信號(小特征值)代表的是圖信號中平滑的部分，其中基本信號φi的平滑度由特征值λi來衡量，即：

(2)

因此，平滑的圖形信號f應該主要由低頻基礎(chǔ)信號來組成，以便相近結(jié)點在卷積中學到更為相似的表征。但同時對于各種不同的應用場景及圖特性，還應考慮在結(jié)點的特征信息和連接信息之間調(diào)整捕獲強度。例如，若同類結(jié)點的個性化信息非常豐富時，應當減弱低通濾波器的平滑力度，保持一定的結(jié)點特征多樣性。

圖過濾的基本思想是使用基礎(chǔ)數(shù)據(jù)關(guān)系圖設(shè)計適當?shù)膱D過濾器，將過濾器作用于圖信號以便生成用于下游任務的平滑信號。例如，可以將特征矩陣X的一列視為圖信號，圖濾波提供了一種將圖結(jié)構(gòu)和頂點特征進行集成以進行學習的原理方法。線性的圖濾波器可以表示為矩陣G∈Rn×n，輸出信號是Gf，本文將重點放在圖卷積濾波器上。

1.2 定義2(圖卷積濾波器)

當且僅當存在一個函數(shù)p(λ):R→R且滿足G=Φp(Λ)Φ-1，其中p(Λ)=diag(p(λ1),…,(λn))時，線性圖濾波器G才是卷積濾波器。函數(shù)p(λ)被稱為濾波器G的頻率響應函數(shù)，它控制著對不同頻率的基信號的響應。一般而言，為了產(chǎn)生平滑信號，濾波器G應能夠?qū)⒌皖l基頻信號保留在f中，同時濾除高頻基頻信號。通過公式(1)，輸出信號可以被寫成：

(3)

2 回顧和拓展IGCN

圖卷積網(wǎng)絡(GCN)通過使用頻譜圖卷積的局部一階逼近進一步簡化了ChebyNet[7]，并在半監(jiān)督學習中取得了可喜的成果。GCN模型包含3個步驟：

2)定義分層傳播規(guī)則為：

(4)

3)堆疊2層并在輸出上應用softmax函數(shù)產(chǎn)生預測矩陣的特征為：

(5)

(6)

具有頻率響應函數(shù)為：

(7)

(8)

(9)

IGCN可以通過指數(shù)k方便地調(diào)整過濾強度來實現(xiàn)標簽效率，并保持具有合理數(shù)量的可訓練參數(shù)的淺層結(jié)構(gòu)，從而避免過度擬合[4]。

IGCN模型中低通濾波器的強度由參數(shù)k控制，對于不同的應用場景選擇合適的k是很重要的。直觀地，在半監(jiān)督的圖嵌入學習任務中，當每個類別中的標簽很少時，應增加過濾的強度，以使遠處的結(jié)點可以具有與標簽結(jié)點相似的特征表示，便于分類。但是過度平滑通常會致使不同類結(jié)點表征趨于同質(zhì)化，導致不正確的類邊界。同時，本文注意到，越來越多應用場景的出現(xiàn)帶來了更具差異化的濾波需求。因此，出于精細設(shè)計的考慮，本文引入平衡參數(shù)μ，使濾波器在指數(shù)不變的情況下，還具有一個平滑力度的控制區(qū)間，也就是說可以不需要增加神經(jīng)網(wǎng)絡可訓練權(quán)重數(shù)量，通過調(diào)控平衡參數(shù)也可實現(xiàn)對圖卷積濾波器的平滑力度的控制，進而使模型能適應多樣的應用場景。具體實現(xiàn)過程如下：

GCN根據(jù)圖譜卷積ChebyNet使用一階近似簡化計算的方法，從而提出了一種簡單有效的層次傳播模型。ChebyNet的譜卷積定義為：

(10)

(11)

假設(shè)T=1,λmax=2，則ChebyNet卷積公式簡化近似為：

(12)

此處，本文引入平衡參數(shù)μ，即令：

θ=θ0=-μθ1,μ∈[0,2]

(13)

于是圖卷積的定義就近似為：

(14)

運用重歸一化技巧，最后可以得到卷積公式為：

(15)

則頻率響應函數(shù)為：

(16)

圖1 可視化在Cora數(shù)據(jù)集上使用濾波器

3 圖譜和圖劃分

平衡參數(shù)通過控制頻率響應函數(shù)的水平位移來提取合適的平滑信號，此外，本文提出還可以從圖劃分的角度進一步解釋平衡參數(shù)作用的原理。高階Cheeger不等式[8-10]顯示了圖對應的拉普拉斯矩陣譜空間上的特征值和圖空間中的圖劃分(聚類)之間的關(guān)系。本文使用Cheeger常數(shù)(Cheeger constant)，也被稱為圖的傳導(graph conductance)來反映圖的劃分。本文從圖的結(jié)點集合中抽取一個子集，作為圖的劃分，記作Q?V，Cheeger常數(shù)定義為：

(17)

在這里E(Q)是一個結(jié)點在劃分的結(jié)點集Q中的邊的集合，vol(Q)是結(jié)點集Q中的結(jié)點的度的和。Cheeger常數(shù)反映了圖的二劃分的劃分效果，ω(Q)越小，則圖被劃分得越開，劃分效果越明顯。將Cheeger常數(shù)推廣到圖劃分成更多個子集的情形，就是r階Cheeger常數(shù)(r-way Cheeger constant)，它定義為：

ρG(r)=min{max{ω(Qi):Q1,Q2,…,Qr?Vdisjoint}}

(18)

r階Cheeger常數(shù)中，使用r劃分得到的r個劃分結(jié)點集的Cheeger常數(shù)的最大值來衡量該r劃分的效果，并以所有可能的r劃分中的最好效果(最小值)來衡量圖被r劃分的程度，所以它表示的是圖內(nèi)在的劃分(聚類)屬性，ρG(r)越小，則圖能被r劃分的效果越好。

r階Cheeger常數(shù)ρG(r)和圖的譜域中的特征值存在著以下的關(guān)系：

(19)

該不等式叫做高階Cheeger不等式。在高階Cheeger不等式中，第r小的拉普拉斯矩陣的特征值設(shè)置了上下界來控制圖的r劃分指標ρG(r)，所以，可以從譜空間對圖結(jié)構(gòu)進行調(diào)制，使調(diào)整后的圖結(jié)構(gòu)更加強調(diào)局域的平滑信息或全局的聚類信息。

從高階Cheeger不等式(19)可以推斷出，小的拉普拉斯矩陣的特征值控制著圖被劃分成幾個大的子圖的劃分效果，即圖的相對全局的聚類效果；大的特征值控制著圖被劃分成許多個小的子圖的劃分效果，即相對局域的聚類效果。當大特征值衰減時，是對圖的局域平滑效果的增強；對于小特征值的衰減效果，是對圖的全局聚類效果的增強。對于低通濾波器而言，則主要是對高頻信號(大特征值)的衰減。這一結(jié)論可以啟發(fā)通過控制頻譜空間的特征值，來控制圖的高階全局或局域的劃分聚類效果。具體來說，增強低通濾波器的強度，是增大對大特征值的衰減，圖結(jié)構(gòu)的內(nèi)在劃分屬性更加強調(diào)局域聚類，此時在拓撲圖上的卷積操作將使相近結(jié)點的表征更加相似，加強了平滑信號所帶來的作用。

4 實 驗

本文利用TensorFlow構(gòu)建圖卷積核，在3個引文網(wǎng)絡數(shù)據(jù)集和1個知識圖譜數(shù)據(jù)集上執(zhí)行半監(jiān)督的圖嵌入學習實驗。為了讓所做的對比實驗是針對單一變量的，本文在與IGCN模型的對比實驗中使用二階(濾波器指數(shù)參數(shù)k=2)的雙層神經(jīng)網(wǎng)絡，以確保在公平的實驗設(shè)置環(huán)境下檢驗所做改進的有效性。

4.1 數(shù)據(jù)集

數(shù)據(jù)集的統(tǒng)計總結(jié)在表1中，引文網(wǎng)絡數(shù)據(jù)集(Cora、Citeseer和Pubmed[11])包含每個文檔的稀疏詞袋特征向量以及文檔之間的引文鏈接列表，結(jié)點是文檔，邊是引文鏈接。NELL[12-13]是從具有55864個關(guān)系結(jié)點和9891個實體結(jié)點的知識圖中提取的二部圖數(shù)據(jù)集。網(wǎng)絡的稀疏度是圖數(shù)據(jù)的一個重要特征，本文用邊的數(shù)量與結(jié)點數(shù)的比值來衡量。

表1 數(shù)據(jù)集統(tǒng)計

4.2 實驗設(shè)計

本文將引文鏈接視為(無向)邊，并構(gòu)造一個二進制的對稱矩陣。每個文檔都有一個類標簽。對于訓練，每個類有20個標簽，但使用所有特征向量。半監(jiān)督學習的目的是使用少數(shù)標簽的文檔的類型對文檔進行分類。本文與GCN、IGCN進行比較，在相同的數(shù)據(jù)集劃分中訓練模型，模型迭代訓練200次，并在包含1000個帶標簽的示例的測試集上評估預測準確度。本文使用和文獻[4]一致的超參數(shù)集，對于Cora、Citeseer和Pubmed的參數(shù)值為：0.5(輟學率)、5·10-4(L2正則化)、16(隱藏單元數(shù))、0.01(學習率)；對于NELL的參數(shù)值為：0.1(輟學率)、1·10-5(L2正則化)、64(隱藏單元數(shù))、0.01(學習率)。

5 實驗結(jié)果及分析

(a) Cora數(shù)據(jù)集上的準確度變化

(b) Citeseer數(shù)據(jù)集上的準確度變化

(c) Pubmed數(shù)據(jù)集上的準確度變化

(d) NELL數(shù)據(jù)集上的準確度變化圖2 平衡參數(shù)μ對模型性能的影響

表2 關(guān)于分類準確性的結(jié)果摘要

對于不同的數(shù)據(jù)集，平衡參數(shù)會有一個相應的有效區(qū)間及最優(yōu)解參數(shù)值，超過此區(qū)間，模型的學習能力會急劇地下降，改進也將失去意義。本文以Cora數(shù)據(jù)集為例分析平衡參數(shù)的作用原理以及其取值規(guī)律。對于Cora數(shù)據(jù)集，圖卷積神經(jīng)網(wǎng)絡模型的頻率響應函數(shù)圖像在引入平衡參數(shù)前后進行對比，二階濾波器下，IGCN的頻率響應函數(shù)(μ=1)與優(yōu)化后的模型在調(diào)整μ值后取得最佳分類效果時的頻率響應函數(shù)(μ=1.1)的圖像對比如圖3所示。

圖3 頻率響應函數(shù)的圖像對比

在圖3中，μ值增大，頻率響應函數(shù)右移，此時的

圖4 IGCN模型在不同k值時的頻率響應函數(shù)

高階Cheeger不等式同樣可以解釋IGCN模型中指數(shù)參數(shù)k的作用。如圖4所示，拉普拉斯矩陣特征值在[0,1]范圍時，濾波器具有低通性，而通過設(shè)置同一個頻率響應的最小通過值可以看到，隨著指數(shù)增大，能通過的特征值越來越小，即平滑力度增強，故大特征值衰減效果越加明顯，圖的局域聚類效果加強。

對于越大的數(shù)據(jù)集，為了獲得結(jié)點的相識度表征，需要加大濾波器處理信號的平滑力度[4]。NELL是所有測試數(shù)據(jù)集中稀疏程度最小的，卻沒有在μ>1的區(qū)間上取得最佳分類效果，其分類準確度隨參數(shù)μ的增大而單調(diào)遞減。這是因為對于此規(guī)模的數(shù)據(jù)集，k的設(shè)置應為一個較大的值，如在IGCN中，k設(shè)定為5左右，而本文實驗中對所有數(shù)據(jù)集都使用二階的濾波器，結(jié)點沒有得到嵌入表示學習所需的平滑強度，因此對局部圖結(jié)構(gòu)信息的捕獲表現(xiàn)出更強的需求，這時平衡參數(shù)μ的作用在于將平滑力度提升到一個合適的水平，可以看到模型分類準確度顯著地提升了46%左右，甚至優(yōu)于在IGCN中使用階數(shù)k=5的分類效果。而在另外3個引文數(shù)據(jù)集中由于數(shù)據(jù)規(guī)模并不大，在二階濾波器下已經(jīng)能產(chǎn)生較好的平滑效果，此時參數(shù)μ的作用在于對濾波器強度進行微調(diào)以達到一個最佳的模型性能。此外，從圖4中可以看到，對于此類更高階的低通濾波器，控制參數(shù)μ，使函數(shù)平移，進而控制濾波器的性質(zhì)同樣具有有效性。

6 相關(guān)工作

關(guān)于卷積核的改進優(yōu)化的文獻很多，早期的基于圖的方法采用一個共同的假設(shè)，即附近的頂點可能具有相同的標簽，如拉普拉斯特征圖[15]、光譜核[16-17]。在頻譜域上，譜卷積神經(jīng)網(wǎng)絡(Spectral CNN)[18]是最早利用卷積定理在一般圖結(jié)構(gòu)上定義卷積算子的方法。Henaff等[19]提出了用帶有平滑性約束的插值卷積核，這種方法降低學習參數(shù)的個數(shù)且實現(xiàn)了圖卷積神經(jīng)網(wǎng)絡的局部化。全連接網(wǎng)絡(FCN)[20]以(I-γ

其他相關(guān)研究包括GraphSAGE[27]、圖表關(guān)注網(wǎng)絡[28]、基于注意力的圖神經(jīng)網(wǎng)絡[29]、圖分區(qū)神經(jīng)網(wǎng)絡[30]、FastGCN[31]、雙圖卷積神經(jīng)網(wǎng)絡[32]、隨機GCN[33]、貝葉斯GCN[34]、深層圖infomax[35]、LanczosNet[36]等。

7 結(jié)束語

本文對經(jīng)典圖卷積神經(jīng)網(wǎng)絡的改進模型IGCN做了增強圖濾波器靈活性的處理，引入可變對角矩陣μ作平移參數(shù)，實現(xiàn)了更精細設(shè)計的目的，通過控制參數(shù)μ可以調(diào)整濾波器的性質(zhì)，并且不會帶來時間上的損失和引入額外的待學習權(quán)重參數(shù)，保持了模型的淺層結(jié)構(gòu)。相比于IGCN，模型性能有了進一步的提升，更加容易適應各種應用場景，同時，本文對平衡參數(shù)的作用原理及實驗現(xiàn)象進行了多角度的解釋，包括從圖劃分的角度來看待IGCN模型中指數(shù)參數(shù)k的作用。未來筆者計劃研究針對各種應用場景的適當圖過濾器的設(shè)計和自動選擇，并應用提出的方法解決更多實際應用。