楊志豪，蔣衛(wèi)麗，杜國棟，相 艷，馬 磊，邵黨國，楊嘉林

1(昆明理工大學(xué) 信息工程與自動化學(xué)院，昆明 650504) 2(廈門大學(xué) 人工智能系，福建 廈門 361005)

1 引 言

近年來隨著互聯(lián)網(wǎng)的發(fā)展，圖像、文本等數(shù)據(jù)呈現(xiàn)指數(shù)形式增長，這些數(shù)據(jù)都屬于歐幾里得數(shù)據(jù).現(xiàn)階段，處理該類數(shù)據(jù)一般用機(jī)器學(xué)習(xí)[1，2]、深度學(xué)習(xí)算法，但是這些算法不具備推理學(xué)習(xí)的能力，因此圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)成為研究的熱潮.

圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Network，GNN)最早由PeterW等人[3]提出，通過將非歐幾里得數(shù)據(jù)轉(zhuǎn)化為圖形式，不斷的聚合和更新節(jié)點(diǎn)的狀態(tài)，讓整體的圖結(jié)構(gòu)達(dá)到一個收斂的狀態(tài).Bruna等人[4]根據(jù)圖像、文本等歐幾里得數(shù)據(jù)中卷積思想的啟發(fā)，在此基礎(chǔ)上提出了圖卷積神經(jīng)網(wǎng)絡(luò)(Graph Convolutional network，GCN)更有效的來解決圖結(jié)構(gòu)數(shù)據(jù)的問題，這類網(wǎng)絡(luò)有一個共同的特點(diǎn)，都是基于消息傳遞的圖神經(jīng)網(wǎng)絡(luò)[5].目前關(guān)于圖的任務(wù)主要有兩大類，一類是關(guān)注于圖整體，如：有機(jī)化合物的分類、判斷化學(xué)分子式是否有致癌性、社交網(wǎng)絡(luò)分類等.另一種是關(guān)注于節(jié)點(diǎn)，如鏈接預(yù)測中推薦系統(tǒng)對用戶不同喜好的判斷，節(jié)點(diǎn)分類任務(wù)中引文網(wǎng)絡(luò)中的文章分類等.傳統(tǒng)的圖神經(jīng)網(wǎng)絡(luò)存在過度平滑、訓(xùn)練不穩(wěn)定的問題，因此Xu等人[6]提出的圖同構(gòu)網(wǎng)絡(luò)(Graph Isomorphism Network ，GIN)，該網(wǎng)絡(luò)提出一個滿足圖特征單射的公式，即不同結(jié)構(gòu)的圖得到不同的圖嵌入，設(shè)計(jì)出一個機(jī)構(gòu)簡單，表征能力強(qiáng)的網(wǎng)絡(luò).同時，William L等人[7]提出GraphSAGE網(wǎng)絡(luò)，模型通過使用了多層次的聚合來取得鄰居節(jié)點(diǎn)的信息，因此可以聚合周圍更多距離更遠(yuǎn)的節(jié)點(diǎn)信息.GraphSAGE設(shè)計(jì)了多種聚合函數(shù)，包括MeanAggregate平均聚合函數(shù)(直接取鄰居的節(jié)點(diǎn)的均值)，圖卷積聚合函數(shù)GCN Aggregator(和傳統(tǒng)GCN的基本一致)，LSTM Aggregator 長短時記憶網(wǎng)路聚合函數(shù)(通過LSTM來編碼鄰居的信息)，Pooling Aggregate池化聚合函數(shù)(把圖中所有的節(jié)點(diǎn)經(jīng)過一個全連接網(wǎng)絡(luò)，經(jīng)過池化，得到特征信息).在模型應(yīng)用上，Marino等人[8]用圖神經(jīng)網(wǎng)絡(luò)做圖像分類的任務(wù)，Lee等人[9]將用圖神經(jīng)網(wǎng)絡(luò)做零樣本學(xué)習(xí)，Henaff等人[10]用圖神經(jīng)網(wǎng)絡(luò)做文本分類任務(wù)，Cheng等人[11]用圖神經(jīng)網(wǎng)絡(luò)做動態(tài)鏈路預(yù)測并且取得的效果都優(yōu)于傳統(tǒng)的神經(jīng)網(wǎng)絡(luò).上述的圖卷積的研究，雖然取得不錯的進(jìn)展，但工作的重心在如何構(gòu)造卷積算子，沒有關(guān)注如何利用每一層卷積所提取的特征信息，并且沒有考慮節(jié)點(diǎn)重要程度的問題.

為了解決上述的問題，本文基于GIN網(wǎng)絡(luò)構(gòu)建多層特征動態(tài)加權(quán)模型.首先，本文保存訓(xùn)練中每一次迭代卷積所提取的特征值，并計(jì)算權(quán)重.然后，輸出預(yù)測結(jié)果時，使用這些所有的特征和權(quán)重來預(yù)測輸出.其次，采用度矩陣加權(quán)的方式來增加重要節(jié)點(diǎn)在整個圖中的權(quán)重，使得圖網(wǎng)絡(luò)在學(xué)習(xí)的過程中，關(guān)注這些重要節(jié)點(diǎn)的特征信息.

2 相關(guān)工作

2.1 GCN圖卷積網(wǎng)絡(luò)

由于傳統(tǒng)的一些神經(jīng)網(wǎng)絡(luò)如CNN在非歐幾里得的數(shù)據(jù)結(jié)構(gòu)上不具有平移不變性[12](無法采用同樣大小的卷積核來進(jìn)行卷積)，不能夠處理非歐幾里得的數(shù)據(jù)(Non Euclidean Structure)的數(shù)據(jù)，但是這樣類型數(shù)據(jù)又廣泛的存在于現(xiàn)實(shí)世界中，為了處理這樣的數(shù)據(jù)，GCN圖卷積網(wǎng)絡(luò)應(yīng)運(yùn)而生，使得在不規(guī)則的圖結(jié)構(gòu)上卷積變成了可能.這里介紹的是由kipf等人[13]改進(jìn)的GCN網(wǎng)絡(luò).首先，GCN網(wǎng)絡(luò)根據(jù)圖的相關(guān)信息(包括節(jié)點(diǎn)信息和結(jié)構(gòu)信息)，求出拉普拉斯矩陣.之后對圖進(jìn)行卷積操作，提取原始信息中有用的部分.最后，加上一個全連接神經(jīng)網(wǎng)絡(luò)進(jìn)行圖的分類判斷，過程步驟如下：

1)首先，根據(jù)圖數(shù)據(jù)求出拉普拉斯矩陣(拉普拉斯矩陣具有一個良好的半正定性質(zhì)，可以做特征的分解.)，并進(jìn)行歸一化操作，如公式(1)與公式(2)所示.

L=D-A

(1)

(2)

其中，L為拉普拉斯矩陣(Laplacian matrix)，Lsys為歸一化的拉普拉斯矩陣，D為度矩陣(Degree matrix)，該矩陣為對角矩陣，只有主對角線元素有值，對角線上每個元素分別代表每個節(jié)點(diǎn)鄰居節(jié)點(diǎn)的數(shù)目.A為鄰接矩陣(Adjacency matrix)，該矩陣為一個對稱矩陣(本文討論的圖數(shù)據(jù)為無向圖)，用于表示節(jié)點(diǎn)之間的相鄰關(guān)系，只有圖中的兩個節(jié)點(diǎn)存在邊時有值，且值為1.IN為N維的單位對角矩陣.

2)根據(jù)拉普拉斯矩陣就可以得到拉普拉斯算子，并且對圖結(jié)構(gòu)數(shù)據(jù)進(jìn)行卷積操作，公式如(3)所示.

(3)

3)輸出層函數(shù)：和普通的神經(jīng)網(wǎng)絡(luò)一樣，在獲取到了高維度的節(jié)點(diǎn)表征信息之后，需要接一個全連接層，以便對這些特征輸出成不同的任務(wù)類別.本文中討論的是圖分類任務(wù)，所以輸出的維度為圖的類別數(shù)目.

2.2 GIN網(wǎng)絡(luò)

圖同構(gòu)網(wǎng)絡(luò)(GIN)網(wǎng)絡(luò)是一種更為強(qiáng)大的圖卷積神經(jīng)網(wǎng)絡(luò)，GIN在GCN網(wǎng)絡(luò)上進(jìn)行了改進(jìn).為了衡量圖網(wǎng)絡(luò)學(xué)習(xí)能力的強(qiáng)弱，提出了以WL test作為一個評價指標(biāo)，WLtest 是由Weisfeiler等人[15]提出的一種經(jīng)典圖算法，它解決了如何判斷圖同構(gòu)的問題(兩張圖結(jié)構(gòu)不同，但是具有相同的鄰接矩陣).圖同構(gòu)問題對于圖神經(jīng)網(wǎng)絡(luò)來說，這是一個很難很棘手的問題，如果一個圖網(wǎng)絡(luò)可以完成鑒別兩個圖是否為同構(gòu)，那么就認(rèn)為這個圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)具有強(qiáng)大的學(xué)習(xí)能力.GIN網(wǎng)絡(luò)的改進(jìn)主要有以下幾點(diǎn).

1)提出了一種新架構(gòu)的聚合函數(shù)，如公式(4)所示.

(4)

圖神經(jīng)網(wǎng)絡(luò)的能力的好壞，往往取決于是否有一個好的嵌入(embeding)，如果一個圖神經(jīng)網(wǎng)絡(luò)可以把不同的原始特征信息有效的映射到不同的高維空間中，這個網(wǎng)絡(luò)則具有強(qiáng)大的特征表示能力.上式從原始的特征到高維的特征映射是單射的關(guān)系，滿足這樣關(guān)系的GIN網(wǎng)絡(luò)具有強(qiáng)大的特征表示能力，能夠?qū)W習(xí)到更多更有效的信息.

2)采用加和方式的readout函數(shù).readout函數(shù)可以將屬于同一個圖的節(jié)點(diǎn)信息聚合為一個圖向量[16]，之前的GCN一般采用最大最小值和均值readout，但在聚合節(jié)點(diǎn)的信息的時候，往往忽略一些信息.比如當(dāng)采用最大值readout函數(shù)的時候，網(wǎng)絡(luò)只考慮到了特征表示最大節(jié)點(diǎn)的信息，而沒有全局的考慮整個圖的信息.如果采用的是求和的readout函數(shù)，網(wǎng)絡(luò)就可以考慮到所有節(jié)點(diǎn)的特征信息，學(xué)習(xí)一個全局的特征.

3 多層動態(tài)加權(quán)圖卷積模型

多層動態(tài)加權(quán)圖卷積模型主要由兩個部分構(gòu)成：度矩陣加權(quán)卷積算子，加權(quán)后的多層特征融合，具體細(xì)節(jié)見下文所述.

3.1 度矩陣加權(quán)的卷積

圖結(jié)構(gòu)可用于表示現(xiàn)實(shí)世界中的一些非歐幾里得的數(shù)據(jù)，通過觀察這些數(shù)據(jù)所表示的圖結(jié)構(gòu)可以發(fā)現(xiàn)，在圖中不同的節(jié)點(diǎn)往往重要程度不同，一些處于中心節(jié)點(diǎn)位置的節(jié)點(diǎn)對圖的結(jié)構(gòu)起到了關(guān)鍵的作用，如果圖神經(jīng)網(wǎng)絡(luò)能更好的聚合到這些重要節(jié)點(diǎn)的信息，就能對圖的結(jié)構(gòu)有一個更全面的學(xué)習(xí)，從而提升網(wǎng)絡(luò)的性能.

圖1 節(jié)點(diǎn)根據(jù)權(quán)重的聚合Fig.1 Node aggregation based on weight

(5)

本文的卷積操作如公式(6)所示.

(6)

其中，σ為激活函數(shù)，MLP為全連接網(wǎng)絡(luò)，l代表卷積層的層數(shù)，h(l)為第l層的所有節(jié)點(diǎn)的狀態(tài)特征值.

由于多層的MLP全連接網(wǎng)絡(luò)可以無限的逼近任意的函數(shù)[17]，所以本文選擇MLP全連接網(wǎng)絡(luò)作為映射函數(shù).

3.2 加權(quán)的多層特征融合

在之前的研究中，GCN網(wǎng)絡(luò)沒有充分考慮卷積每一層所聚合的信息，直接簡單的把每一層的特征進(jìn)行相加進(jìn)行特征的融合.本文提出了一種帶權(quán)值的特征融合方法(使用每一層的節(jié)點(diǎn)特征進(jìn)行輸出)，能夠更好的獲析每一層卷積層所提取出來的信息.

公式(6)中h(l)為圖中所有節(jié)點(diǎn)的信息，為了講述動態(tài)加權(quán)的原理，從每個節(jié)點(diǎn)的角度來看，本文卷積操作可以用公式(7)表示.

(7)

h=(h(l)|l∈1,2,…,K)

(8)

其中K代表網(wǎng)絡(luò)的卷積層數(shù).那么所有卷積層總特征表示為公式(9)所示.

(9)

為了給每一層特征根據(jù)其重要程度的不同，進(jìn)行動態(tài)的權(quán)值賦值.本文通過計(jì)算每一層的單個節(jié)點(diǎn)特征表示和總特征表示可以得到一組余弦相似度系數(shù)ε(l).相似度系數(shù)ε(l)越高，意味著相似度越高，該層的層節(jié)點(diǎn)特征就越有效果，賦予更大的權(quán)重，權(quán)重計(jì)算如公式(10)所示.

(10)

根據(jù)節(jié)點(diǎn)特征權(quán)重，計(jì)算節(jié)點(diǎn)每一層特征的權(quán)重，即為把得到的權(quán)重分別和每一層特征的輸出相加權(quán)，得到最終的節(jié)點(diǎn)特征表示，具體如公式(11)所示.

(11)

為了運(yùn)用到圖分類任務(wù)上，需要把節(jié)點(diǎn)特征向量表示轉(zhuǎn)換為圖特征向量表示.采用加和的形式的readout函數(shù)將圖中的每個點(diǎn)特征表示為整個圖的特征信息，如公式(12)所示.

(12)

其中，H(l)為第l層圖特征表示，k代表圖中節(jié)點(diǎn)的總數(shù).

圖2 本文算法模型Fig.2 Algorithm model of this paper

將圖向量特征分別送入每一層的預(yù)測層中預(yù)測，最后將每一層的預(yù)測結(jié)果相加，得到最終的預(yù)測結(jié)果.整個模型分框架如圖2所示.

4 實(shí)驗(yàn)及結(jié)果

4.1 實(shí)驗(yàn)數(shù)據(jù)集和評價指標(biāo)

為了驗(yàn)證本文所提模型的性能，本文將所提的方法在四個數(shù)據(jù)集[18](IMDB-BINARY，MUTAG，PROTEINS，PTC)上進(jìn)行比較，其中，IMDB-BINARY這是一個電影數(shù)據(jù)集，共1000張圖.其中每個節(jié)點(diǎn)表示演員，邊代表著連接的兩個節(jié)點(diǎn)也就是演員出現(xiàn)在同一部電影中，每一個圖都有一個標(biāo)注的屬性(電影的類別，總共有兩個類別)，分類任務(wù)就是根據(jù)不同的節(jié)點(diǎn)和結(jié)構(gòu)來判斷圖的種類；MUTAG是化學(xué)數(shù)據(jù)集，共188張圖.它由芳胺和硝基雜芳環(huán)兩類組成的，節(jié)點(diǎn)有7個離散的標(biāo)簽，來區(qū)別不同的元素，邊代表著兩個節(jié)點(diǎn)之間是否有化學(xué)鍵，分類任務(wù)為判別該化合物對細(xì)菌是否有誘變作用；PROTEINS為生物數(shù)據(jù)集，共1113張圖.其中節(jié)點(diǎn)代表著有機(jī)物的結(jié)構(gòu)，它有三種特征分別為helix(螺旋)、Turn(轉(zhuǎn)角)、sheet(折疊).邊代表著節(jié)點(diǎn)間是否為氨基酸順序.分類任務(wù)為判斷蛋白質(zhì)的二級結(jié)構(gòu)預(yù)測；PTC數(shù)據(jù)集是一個化合物數(shù)據(jù)集，共344張圖.節(jié)點(diǎn)代表不同的化學(xué)分子式(19種)，邊代表了他們之間是否有連接.任務(wù)為判斷該化合物對鼠類是否具有致癌性質(zhì).數(shù)據(jù)集簡要描述如表1所示.

本文采用Accuracy精確度作為評價指標(biāo)，設(shè)A、B、C、D分別為正陽性、假陰性、假陽性和正陰性，那么準(zhǔn)確度為:

(13)

表1 數(shù)據(jù)集介紹Table 1 Data set introduction

4.2 實(shí)驗(yàn)?zāi)Ｐ痛罱ê蛥?shù)設(shè)置

本文實(shí)驗(yàn)操作的環(huán)境為Ubuntu 18.04.3LTS 操作系統(tǒng)、Intel Corei5-8250U CPU、8G RAM、Python3.7.3、Pytorch1.2.0.參數(shù)的設(shè)置如表2所示.

表2 參數(shù)設(shè)置Table 2 Parameter settings

為了選取合適的卷積層數(shù)，本文對近幾年的文獻(xiàn)[2，4，19，20，21]進(jìn)行研究，暫且沒有合適的選取標(biāo)準(zhǔn)，因此，本文利用卷積層數(shù)不同來進(jìn)行對照實(shí)驗(yàn)，給出相對合理的選取依據(jù).本文在ROTEINS數(shù)據(jù)集上，使用GCN，GIN，以及本文模型進(jìn)行了卷積層數(shù)不同準(zhǔn)確了變化的曲線圖，具體結(jié)果如圖3所示.

圖3 卷積層數(shù)對精度的影響Fig.3 Effect of the number of convolution layers on accuracy

通過對比實(shí)驗(yàn)，可以發(fā)現(xiàn)隨著網(wǎng)絡(luò)層數(shù)的加深，各個模型在精確度下均出現(xiàn)了下降，因?yàn)檫^深的網(wǎng)絡(luò)會導(dǎo)致節(jié)點(diǎn)特征的平滑.因此考慮精度的同時也考慮了模型的復(fù)雜程度，最終本文選擇了5層的卷積層作為本文模型的卷積層數(shù).

4.3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文模型的有效性，本文選用了7個模型，分別是GIN網(wǎng)絡(luò)，GCN網(wǎng)絡(luò)，GraphSAGE網(wǎng)絡(luò)，D-GCN網(wǎng)絡(luò)，A-GCN網(wǎng)絡(luò)，WL以及本文模型.在4個數(shù)據(jù)集上進(jìn)行了對比實(shí)驗(yàn)，結(jié)果如表3所示.其中D-GCN為只使用改進(jìn)后的卷積算子模型，A-GCN為只使用動態(tài)特征加權(quán)的模型.加入D-GCN和A-GCN的目的是為了分別驗(yàn)證改進(jìn)的卷積算子和動態(tài)特征加權(quán)對于網(wǎng)絡(luò)效果的提升.

表3 模型精度對比Table 3 Model accuracy comparison

通過對比可以發(fā)現(xiàn)，本文模型的精度在4個數(shù)據(jù)集上均有較好的效果，其中在IMDB-BINARY，PROTEINS，PTC數(shù)據(jù)集上均高于對比模型，說明了本文模型的有效性，在MUTAG數(shù)據(jù)集上和GIN模型基本一致，高于其他的圖卷積模型，和非圖卷積WL算法基本保持一致水平，原因是MUTAG的數(shù)據(jù)集相比于其他三個數(shù)據(jù)集較小，且節(jié)點(diǎn)標(biāo)簽較多，不利于本文模型學(xué)習(xí)圖數(shù)據(jù)結(jié)構(gòu)的信息.從表中可以看出A-GCN網(wǎng)絡(luò)在IMDB-BINARY和PROTEINS上已經(jīng)有提升，證明了動態(tài)加權(quán)對于圖網(wǎng)絡(luò)學(xué)習(xí)是有效的.同時D-GCN在MUTAG上不如本文模型和A-GCN，原因是這個數(shù)據(jù)集的平均節(jié)點(diǎn)數(shù)較少，當(dāng)遇到節(jié)點(diǎn)數(shù)目較少的圖數(shù)據(jù)，只通過度矩陣來給卷積算子加權(quán)就會導(dǎo)致權(quán)重過小的問題，但在IMDB-BINARY和PROTEINS上D-GCN也取得了一定提升，說明了改進(jìn)的卷積算子是有效的.另外，通過和非圖神經(jīng)網(wǎng)絡(luò)的WL算法對比可以發(fā)現(xiàn)，在節(jié)點(diǎn)數(shù)目少或比較簡單的任務(wù)如MUTAG數(shù)據(jù)集上效果不錯，但隨著平均節(jié)點(diǎn)數(shù)目以及數(shù)據(jù)集的加大，比如在PTC數(shù)據(jù)集上，表現(xiàn)就明顯不如圖卷積網(wǎng)絡(luò)，也證明圖卷積網(wǎng)絡(luò)有解決更復(fù)雜問題的能力.

5 結(jié) 論

在圖的任務(wù)中，圖卷積的卷積算子是一個關(guān)鍵點(diǎn)，這關(guān)系著整個網(wǎng)絡(luò)是否能學(xué)習(xí)到更多更有效的信息，這也是之前的GCN網(wǎng)絡(luò)及其變種關(guān)注的重點(diǎn).但僅有一個好的卷積算子也是不夠的.首先，本文關(guān)注與怎么利用提取出的節(jié)點(diǎn)特征進(jìn)行特征的融合，通過計(jì)算每一層節(jié)點(diǎn)特征與總特征的相似度來確定該層的系數(shù)，進(jìn)行特征的融合，更好地利用節(jié)點(diǎn)的信息.同時本文使用了一種加權(quán)的拉普拉斯算子，旨在于區(qū)分重要的節(jié)點(diǎn)和不重要節(jié)點(diǎn)，重要的節(jié)點(diǎn)會獲得更大的權(quán)重，使得網(wǎng)絡(luò)框架在學(xué)習(xí)時更多的考慮重要節(jié)點(diǎn)的信息.通過實(shí)驗(yàn)也證明了本文使用的方法確實(shí)是一種有效的方法.

在下一步的工作中，本文將尋找一種更為合理的相似度的算法，取得更好地效果.同時在后續(xù)的研究中也考慮將圖神經(jīng)網(wǎng)絡(luò)應(yīng)用于圖像和文本任務(wù)中，發(fā)揮圖神經(jīng)網(wǎng)絡(luò)具有推導(dǎo)能力的優(yōu)勢，彌補(bǔ)傳統(tǒng)神經(jīng)網(wǎng)絡(luò)的不足.