基于重要性池化的層級圖表示學(xué)習(xí)方法

張紅梅，李浩然， 張向利

(1.桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004；2.桂林電子科技大學(xué) 廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

近年來，隨著機(jī)器學(xué)習(xí)技術(shù)的不斷發(fā)展，特別是卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network，簡稱CNN)的優(yōu)秀表現(xiàn)，研究人員開始將卷積操作擴(kuò)展到圖數(shù)據(jù)，希望利用卷積操作強(qiáng)大的特征提取能力給圖任務(wù)帶來更有效的解決方法。但傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)在大規(guī)模圖分類任務(wù)上存在訓(xùn)練過程中噪聲信息過多以及對于圖的層級表征信息挖掘不完整等問題。因此，基于圖的神經(jīng)網(wǎng)絡(luò)算法亟待進(jìn)一步的研究。

圖神經(jīng)網(wǎng)絡(luò)(graph neural network，簡稱GNN)這一概念是由Gori等[1]首次提出，作為循環(huán)神經(jīng)網(wǎng)絡(luò)的一種泛化形式而引入。Bruna等[2]提出的圖卷積神經(jīng)網(wǎng)絡(luò)(graph convolutional network，簡稱GCN)，通過傅里葉變換將圖的Laplacian矩陣從空間域轉(zhuǎn)換至頻域，基于頻域中的概念創(chuàng)造性地將可訓(xùn)練的卷積操作應(yīng)用于圖數(shù)據(jù)。文獻(xiàn)[3-4]在原始GCN的基礎(chǔ)上分別提出了2種簡化操作，在降低了算法復(fù)雜度的同時(shí)極大地提高了算法的效率。但這些GNN算法都存在一定的局限性，它們在本質(zhì)上是平坦的，特征信息僅通過節(jié)點(diǎn)的邊緣傳播，無法以層級的方式推斷和表示信息。因此，Ying等[5]提出了一種可微分的圖池化方法(DiffPool)，通過端到端的形式學(xué)習(xí)圖的層級表示，但該方法空間復(fù)雜度較大，且參數(shù)的數(shù)量與節(jié)點(diǎn)數(shù)相關(guān)，對于大型圖數(shù)據(jù)集不夠友好。Gao等[6]使用gPool池化方法達(dá)到了與DiffPool相當(dāng)?shù)男阅?，并且對空間復(fù)雜度進(jìn)行了優(yōu)化，取得了明顯優(yōu)勢，但未考慮圖結(jié)構(gòu)特征信息的提取。

另一方面，深度學(xué)習(xí)的成功在于深層的網(wǎng)絡(luò)結(jié)構(gòu)，因此神經(jīng)網(wǎng)絡(luò)通常會采用增加網(wǎng)絡(luò)層數(shù)的策略來提高模型的分類效果[7]。但在傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)層數(shù)堆疊至2層以上，模型的分類效果會隨著層數(shù)的增加而下降[3]，這是由于更多的層會傳播更多來自鄰域的噪聲信息。鑒于殘差連接[8]在傳統(tǒng)深度學(xué)習(xí)中的成功應(yīng)用，有研究人員嘗試將殘差網(wǎng)絡(luò)與圖神經(jīng)網(wǎng)絡(luò)結(jié)合[3]，但效果并不理想。于是，Xu等[9]提出了一種跳躍知識網(wǎng)絡(luò)架構(gòu)(jumping knowledge networks，簡稱JK Net)，將每層圖卷積的輸出都連接到網(wǎng)絡(luò)的最后一層，并且在最后一層引入自適應(yīng)的特征聚合機(jī)制，為每個(gè)節(jié)點(diǎn)分配合適的權(quán)重和感受野，這為后續(xù)的研究提供了新的思路。

綜上所述，現(xiàn)有GNN算法在處理圖分類任務(wù)時(shí)通常存在3個(gè)問題：1)處理大圖數(shù)據(jù)集時(shí)模型復(fù)雜度較高；2)淺層結(jié)構(gòu)不能完整地挖掘出節(jié)點(diǎn)和圖的表示信息；3)對于圖數(shù)據(jù)層級結(jié)構(gòu)特征的挖掘不夠深入。為了解決上述問題，提出一種端到端的基于重要性池化的層級圖表示學(xué)習(xí)方法。

1 算法框架

基于重要性池化的層級圖表示學(xué)習(xí)方法框架如圖1所示。本方法以層內(nèi)-層間聯(lián)合特征提取結(jié)構(gòu)為基礎(chǔ)，包括層內(nèi)特征提取模塊和層間特征提取模塊2個(gè)部分。首先利用GNN對輸入圖數(shù)據(jù)進(jìn)行特征提取，之后利用圖池化層對處理后的節(jié)點(diǎn)進(jìn)行重要性采樣，并將每層形成的新圖輸入RNN單元，以自適應(yīng)地為每個(gè)節(jié)點(diǎn)分配合適的感受野，最后經(jīng)過一個(gè)多層感知機(jī)(multilayer perceptron，簡稱MLP)對處理后的圖數(shù)據(jù)進(jìn)行分類。

圖1 本方法框架

1.1 層內(nèi)特征提取模塊

以圖G=(V,E)為例，其中V為圖的節(jié)點(diǎn)集合，E為圖的邊集合。設(shè)N為節(jié)點(diǎn)數(shù)，F(xiàn)為特征維度，則A∈RN×N為鄰接矩陣，X∈RN×F為節(jié)點(diǎn)特征矩陣，D∈RN×N為節(jié)點(diǎn)度矩陣。

層內(nèi)特征提取模塊主要實(shí)現(xiàn)了采樣重要節(jié)點(diǎn)的功能。采用GNN提取每層的特征，為節(jié)點(diǎn)生成新的特征。利用新的特征矩陣計(jì)算每個(gè)節(jié)點(diǎn)在可訓(xùn)練向量p上的一維投影分?jǐn)?shù)，以此作為節(jié)點(diǎn)采樣標(biāo)準(zhǔn)，降序選擇投影分?jǐn)?shù)最大的k個(gè)節(jié)點(diǎn)組成一張新的子圖，這個(gè)采樣過程稱為top-rank。

選擇GCN作為特征提取網(wǎng)絡(luò)，以第l(l=0,1,…,L)層為例，經(jīng)過圖卷積神經(jīng)網(wǎng)絡(luò)得到新的特征表示，

(1)

為了進(jìn)一步減小特征圖的尺寸，將Xl+1輸入池化層進(jìn)行池化處理。池化層采用gPool算法的下采樣方法，定義一個(gè)可訓(xùn)練的一維投影向量p∈RF′，計(jì)算每個(gè)節(jié)點(diǎn)特征向量在投影向量p上的一維投影分?jǐn)?shù)y，并對其進(jìn)行歸一化和非線性處理，

(2)

(3)

(4)

輸出的新圖與原始圖相比尺寸較小，同時(shí)保留了原始圖中大部分的特征和屬性，并且由于節(jié)點(diǎn)的選擇與鄰接矩陣的更新同步，新圖中節(jié)點(diǎn)之間的連接具有與原始圖一致的連通性。為了得到均勻的特征分布，需要對Xl+1進(jìn)行歸一化處理，得到輸出的新的特征矩陣，

(5)

其中⊙為哈達(dá)瑪積，表示對2個(gè)維度完全相同的向量或矩陣進(jìn)行對應(yīng)位置元素相乘。

由于每經(jīng)過一次層內(nèi)特征提取，節(jié)點(diǎn)數(shù)N會縮減為kN，導(dǎo)致每層輸出的特征矩陣形狀并不相同，給后續(xù)的計(jì)算帶來不便。因此，對每層的輸出Xl+1進(jìn)行Readout處理，得

(6)

其中，S∈R2F′為處理后具有固定尺寸的輸出，大小與節(jié)點(diǎn)數(shù)目無關(guān)，只與特征維度有關(guān)。

1.2 層間特征提取模塊

層間特征提取模塊主要實(shí)現(xiàn)保留重要特征的功能，模塊架構(gòu)采用層次結(jié)構(gòu)，因?yàn)閷τ诓东@圖的結(jié)構(gòu)信息來說，層次表示非常關(guān)鍵。將整個(gè)模型的層級輸出經(jīng)過Readout處理后，以序列數(shù)據(jù)的形式依次輸入RNN，在訓(xùn)練過程中自適應(yīng)地融合了不同層的特征信息，實(shí)現(xiàn)對于圖數(shù)據(jù)層級表示的捕獲。

在GNN模型中節(jié)點(diǎn)特征的更新規(guī)則是每經(jīng)過一層網(wǎng)絡(luò)，都會聚集來自該節(jié)點(diǎn)一階鄰居的特征信息，在理想狀態(tài)下，當(dāng)經(jīng)過足夠次數(shù)的更新后，每個(gè)節(jié)點(diǎn)都能完全包含整張圖的特征信息。當(dāng)模型層數(shù)較少時(shí)，輸出的結(jié)果無法獲得節(jié)點(diǎn)完整的特征表示，但當(dāng)模型層數(shù)過多時(shí)，又會造成過平滑的問題，即每個(gè)節(jié)點(diǎn)都具有相似的特征表示，反而失去了其個(gè)體的獨(dú)特性。因此，將層內(nèi)特征提取模塊輸出的信息Sl+1按照序列的形式輸入RNN，通過訓(xùn)練為每個(gè)節(jié)點(diǎn)分配感受野，從而自適應(yīng)地將不同層的特征信息融入最終的節(jié)點(diǎn)特征表示。以LSTM為例，每層節(jié)點(diǎn)特征的更新公式為

(7)

圖2 網(wǎng)絡(luò)模型示例圖

3 仿真實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境介紹和數(shù)據(jù)集

實(shí)驗(yàn)硬件環(huán)境：CPU處理器為8核Intel(R)Xeon(R) E5-260，32 GiB內(nèi)存；GPU顯卡為GeForce GTX 1080 TiB，16 GiB內(nèi)存；軟件環(huán)境包括64位Windows 10，CUDA 9.0，Python 3.6.4，Pytorch 1.1.0。

從基準(zhǔn)數(shù)據(jù)集[10]選擇4個(gè)常用的圖分類數(shù)據(jù)集。1)D&D：該數(shù)據(jù)集包含1 178個(gè)蛋白質(zhì)結(jié)構(gòu)，每個(gè)蛋白質(zhì)由一張圖表示，其中節(jié)點(diǎn)代表氨基酸，若2個(gè)節(jié)點(diǎn)之間的距離小于6 ?，則建立一條邊，預(yù)測任務(wù)是將蛋白質(zhì)結(jié)構(gòu)分類為酶、非酶。2)PROTEINS：一組蛋白質(zhì)分子交互網(wǎng)絡(luò)數(shù)據(jù)集，節(jié)點(diǎn)代表二級結(jié)構(gòu)元素，若節(jié)點(diǎn)處于氨基酸序列或緊密的3D空間，則建立邊緣，預(yù)測任務(wù)是對蛋白質(zhì)功能進(jìn)行判斷。3)NCI1：非小細(xì)胞肺癌活性篩選的化合集的平衡子集，預(yù)測任務(wù)是將每種酶分為2類。4)MUTAG：由188種化合物組成的數(shù)據(jù)集，節(jié)點(diǎn)表示原子，邊緣表示化學(xué)鍵，預(yù)測任務(wù)是根據(jù)化合物對細(xì)菌的誘變作用分為2類。數(shù)據(jù)集主要參數(shù)如表1所示。每個(gè)數(shù)據(jù)集10%作為訓(xùn)練集，其余為測試集。

表1 數(shù)據(jù)集主要參數(shù)

3.2 模型和參數(shù)設(shè)置

模型采用圖2網(wǎng)絡(luò)結(jié)構(gòu)，并在層內(nèi)特征提取模塊之間加入BatchNorm層對輸出進(jìn)行歸一化。為了保證對比實(shí)驗(yàn)的有效性，對比模型的GNN設(shè)置為3層。

超參數(shù)設(shè)置：3個(gè)特征提取模塊池化率k=0.8，L2正則化的權(quán)重衰減系數(shù)為10-5，初始學(xué)習(xí)率為10-5，每經(jīng)過200個(gè)訓(xùn)練步驟將學(xué)習(xí)率降低為原來的1/2，批量處理尺寸為128。選擇Adam作為參數(shù)優(yōu)化器，使用L2正則化防止訓(xùn)練過擬合，選擇負(fù)對數(shù)似然作為損失函數(shù)，損失值連續(xù)10次迭代后不再下降時(shí)，停止訓(xùn)練。

3.3 準(zhǔn)確率分析

實(shí)驗(yàn)采用了SAGPool[11]和DiffPool[5]模型作為對比，在4個(gè)數(shù)據(jù)集上的檢測準(zhǔn)確率如表2所示。從表2可看出，本方法的分類精度明顯優(yōu)于對比模型。結(jié)合表1可得，本方法使用的數(shù)據(jù)集越大，其效果提升越明顯。這是因?yàn)樵趯觾?nèi)特提取模塊中應(yīng)用了池化層，每經(jīng)過一次池化操作，不可避免地會損失一些信息，大數(shù)據(jù)集在經(jīng)過池化操作后，仍能保留大部分特征信息，而小數(shù)據(jù)集可能因?yàn)閾p失了大部分信息，導(dǎo)致剩余的特征信息不足以保證自身表達(dá)的完整性。

表2 不同方法的數(shù)據(jù)集檢測準(zhǔn)確率對比 %

3.4 損失值分析

圖3～6為SAGPool、DiffPool和本方法在4個(gè)基準(zhǔn)數(shù)據(jù)集上的損失曲線變化。從圖3～6可看出，本方法的損失曲線更早收斂，且損失值收斂于一個(gè)更小的值，這是由于循環(huán)單元的門結(jié)構(gòu)對于層間傳播的噪聲具有很好的抑制作用。

圖3 D&D數(shù)據(jù)集的損失曲線

圖4 PROTEINS數(shù)據(jù)集的損失曲線

圖5 NCI1數(shù)據(jù)集的損失曲線

圖6 MUTAG數(shù)據(jù)集的損失曲線

4 結(jié)束語

針對傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)處理大規(guī)模圖數(shù)據(jù)集時(shí)模型復(fù)雜度較高、淺層結(jié)構(gòu)不能完整地挖掘出圖數(shù)據(jù)的表示信息以及對于層級結(jié)構(gòu)特征的挖掘不夠深入的問題，提出了一種端到端的基于重要性池化的層級圖表示學(xué)習(xí)方法。通過層內(nèi)特征提取模塊，將圖粗?；癁楦呒壏肿咏Y(jié)構(gòu)，實(shí)現(xiàn)對特征圖尺寸的壓縮，以減少參數(shù)的數(shù)量，并避免過擬合；通過層間特征提取模塊，實(shí)現(xiàn)了節(jié)點(diǎn)自適應(yīng)分配權(quán)重和感受野，在訓(xùn)練過程中合理地融合了不同層的特征信息。實(shí)驗(yàn)驗(yàn)證了該方法的有效性，未來工作考慮將本方法擴(kuò)展至其他領(lǐng)域數(shù)據(jù)集，以解決更多實(shí)際問題。