徐立祥 葛 偉 陳恩紅 羅 斌

1（合肥學(xué)院人工智能與大數(shù)據(jù)學(xué)院 合肥 230601）

2（大數(shù)據(jù)分析與應(yīng)用安徽省重點實驗室（中國科學(xué)技術(shù)大學(xué)計算機科學(xué)與技術(shù)學(xué)院） 合肥 230027）

3（安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院 合肥 230601）

（xulixianghf@163.com）

現(xiàn)實世界中的大量問題都可以抽象成圖模型（graph model），也就是節(jié)點和邊的集合，包括自然語言處理[1]、異常檢測[2-3]、學(xué)術(shù)網(wǎng)絡(luò)分析、生物醫(yī)療、推薦系統(tǒng)等.圖是一種不同規(guī)則的非歐氏幾何數(shù)據(jù)，圖數(shù)據(jù)的結(jié)構(gòu)錯綜復(fù)雜，包含大量的信息，比如結(jié)構(gòu)信息、節(jié)點特征信息等.通過學(xué)習(xí)基于圖形的嵌入表示，可以獲取結(jié)構(gòu)化數(shù)據(jù)的順序、拓撲、幾何和其他關(guān)系特征.近年來，圖深度學(xué)習(xí)的研究是學(xué)術(shù)界和產(chǎn)業(yè)界的一個熱點，主要集中在節(jié)點分類[4]、鏈路預(yù)測[5]、圖分類等.本文將重點關(guān)注的是圖分類任務(wù).圖分類任務(wù)的關(guān)鍵是學(xué)習(xí)圖與對應(yīng)標簽的映射關(guān)系.圖分類在生物化學(xué)方面有著廣泛的應(yīng)用，例如對一些化學(xué)分子圖進行分類來判斷其活性、水溶性、毒性等.因此研究圖分類問題有著重要意義.

圖分類的重要方法之一是圖核方法，它是一種計算圖之間相似度的重要方法，把一些在低維空間下非線性不可分的數(shù)據(jù)轉(zhuǎn)化到高維空間中，使得這些數(shù)據(jù)線性可分，是專門針對圖數(shù)據(jù)的一種特殊方法.圖核函數(shù)一般是根據(jù)專家知識設(shè)計的，它考慮了不同子結(jié)構(gòu)的相似性，例如隨機游走核和最短路徑核.不同的圖核函數(shù)之間也能相互融合，例如多圖核學(xué)習(xí)[6].這就為圖分類引入不同的相似度度量方法和不同的偏差，從而生成具有不同性能的圖分類模型.然而在缺乏專家知識的情況下，執(zhí)行圖分類任務(wù)時很難確定選擇哪種圖核函數(shù)是最好的.

隨著深度學(xué)習(xí)的興起，圖卷積神經(jīng)網(wǎng)絡(luò)（graph convolution neural networks,GCN）[7]成為圖數(shù)據(jù)挖掘領(lǐng)域最重要的方法之一.GCN 首次提出了卷積的方式融合圖結(jié)構(gòu)特征，提供了一個全新的視角，即在節(jié)點嵌入表示中將鄰域節(jié)點的特征融入其中，與將節(jié)點特征直接通過全連接層分類的方法相比，在節(jié)點分類準確度上得到了很大提升.然而GCN 存在共享權(quán)重、靈活性差、可擴展性不強的缺點，此外當(dāng)網(wǎng)絡(luò)層數(shù)增加時，會出現(xiàn)過平滑現(xiàn)象，導(dǎo)致每個節(jié)點的特征結(jié)果十分相似.為了解決GCN 領(lǐng)域聚合時權(quán)值共享問題，帶有注意力機制的圖注意力網(wǎng)絡(luò)（graph attention network,GAT）[8]被提出，GAT 具有高效低存儲的優(yōu)點，GAT 是基于鄰居節(jié)點的計算方式，它屬于一種歸納的學(xué)習(xí)方式.GAT 的缺點就是只歸納了1階鄰居，導(dǎo)致GAT 的感受野必須依賴深層的網(wǎng)絡(luò).為了解決GCN 擴展性差的問題，GraphSAGE（graph sample and aggregate）[9]提出了多種節(jié)點采樣和聚合的方法，使圖的嵌入表示更加靈活，當(dāng)圖中有新的節(jié)點加入時，固定的節(jié)點采樣方式使得GraphSAGE 無需對所有的節(jié)點進行重新訓(xùn)練，便可獲取最新的嵌入.圖神經(jīng)網(wǎng)絡(luò)（graph neural network，GNN）主要是針對節(jié)點特征的更新與提取，圖分類要在此基礎(chǔ)上增加圖池化的操作，圖池化主要是在圖節(jié)點嵌入的基礎(chǔ)上得到整個圖的嵌入，其中主流的圖池化方法有2 種，即全局池化和分層池化.全局池化是在疊加圖卷積之后運用全局池化操作（如最大池化和平均池化）選出能代表整張圖表示的節(jié)點信息.分層池化借鑒了CNN 中的池化，每次池化都會縮小數(shù)據(jù)的規(guī)模，對于圖數(shù)據(jù)來說，就是通過某種算法減少節(jié)點的數(shù)目來完成逐層的抽取，從而實現(xiàn)圖的池化，這種算法有Top-k[10]、圖聚類池化等.圖神經(jīng)網(wǎng)絡(luò)用于圖分類的整個過程如圖1 所示.

Fig.1 The process of graph classification based on graph neural networks圖1 基于圖神經(jīng)網(wǎng)絡(luò)的圖分類過程

為了提升圖神經(jīng)網(wǎng)絡(luò)的圖分類性能，近年來，一些研究人員致力于把圖核與圖神經(jīng)進行融合，提出了許多基于圖核的圖神經(jīng)網(wǎng)絡(luò)框架.例如圖卷積核網(wǎng)絡(luò)（graph convolutional kernel network，GCKN）[11]采用隨機游走核提取路徑并投影到核空間中，然后把核空間中路徑信息聚合到起始節(jié)點上.圖結(jié)構(gòu)核網(wǎng)絡(luò)（graph structural kernel network，GSKN）[12]在GCKN的基礎(chǔ)上增加了匿名隨機游走核，使得提取局部子結(jié)構(gòu)的能力得到了進一步的加強.這2 種框架雖然能在一定程度上提升表達能力，但提取路徑的操作耗費大量時間.核圖神經(jīng)網(wǎng)絡(luò)（kernel graph neural network，KerGNN）[13]也是采用隨機游走核與圖神經(jīng)網(wǎng)絡(luò)進行融合，與先前工作不同的是，它采用可訓(xùn)練隱藏圖作為圖濾波器，與子圖進行結(jié)合，并利用圖核更新節(jié)點嵌入，使得圖神經(jīng)網(wǎng)絡(luò)具有一定的可解釋性，降低了圖核計算的時間復(fù)雜度，然而對于圖分類的性能提升不大.

影響圖分類性能主要有2 個方面：1）對圖節(jié)點的特征編碼；2）對圖的結(jié)構(gòu)編碼.在一些化學(xué)分子圖中，結(jié)構(gòu)對性能的影響占比很大，這類圖的性質(zhì)與特定子圖結(jié)構(gòu)的相關(guān)性比較強，對于一些社交網(wǎng)絡(luò)圖，這類圖不依賴于特定的局部結(jié)構(gòu)，節(jié)點特征分布對圖分類性能影響較大.基于圖核的方法，對圖的結(jié)構(gòu)編碼的方法重點關(guān)注圖之間的結(jié)構(gòu)相似性，本質(zhì)上來說也是對圖的一種結(jié)構(gòu)相似性編碼，因此圖核方法在一些化學(xué)分子圖上表現(xiàn)出良好的性能，但對于一些社交網(wǎng)絡(luò)圖表現(xiàn)出的性能相對較差.而基于圖神經(jīng)網(wǎng)絡(luò)的模型更加關(guān)注節(jié)點的特征.其本質(zhì)上也是基于消息傳遞的框架.當(dāng)今的一些圖神經(jīng)網(wǎng)絡(luò)框架存在3 個問題：1）在圖神經(jīng)網(wǎng)絡(luò)的鄰域聚合的過程中，獲取了圖的樹形結(jié)構(gòu)信息和鄰域內(nèi)的節(jié)點特征信息，卻無法區(qū)分例如多元環(huán)等高階子結(jié)構(gòu)；2）為了獲得更好的性能，圖神經(jīng)網(wǎng)絡(luò)會疊加多層特征信息，但是這個層數(shù)的設(shè)置很難把握，如果設(shè)置過大，會產(chǎn)生過平滑問題，也即是，它使得深層的節(jié)點嵌入表示都十分相似，因此，把這些相似的節(jié)點嵌入堆疊會破壞圖節(jié)點特征編碼與圖標簽的單射關(guān)系，最終會導(dǎo)致圖分類性能下降；3）以往圖核和圖神經(jīng)網(wǎng)絡(luò)融合的工作主要是采用隨機游走核來提升節(jié)點獲取鄰域內(nèi)高階子結(jié)構(gòu)信息的能力，但是這種方法的時間復(fù)雜度較大.此外，隨機游走核具有不確定性，無法保證每一次游走的路徑都包含了高階子結(jié)構(gòu)信息.為了解決這3 個問題，本文將WL（Weisfeiler-Lehman）[14]核與圖神經(jīng)網(wǎng)絡(luò)融合起來，WL 核對圖數(shù)據(jù)進行結(jié)構(gòu)相似性編碼，圖同構(gòu)網(wǎng)絡(luò)（graph isomorphism network，G?N）[15]對圖的節(jié)點特征進行編碼，并將這2 部分編碼通過注意力加權(quán)方式進行融合，相當(dāng)于在基于消息傳遞的圖神經(jīng)網(wǎng)絡(luò)中增加了圖的結(jié)構(gòu)相似性信息，提升圖神經(jīng)網(wǎng)絡(luò)的表達能力.

本文的主要貢獻包括4 個方面：

1）提供了一個新的視角，將WL 核應(yīng)用到圖神經(jīng)網(wǎng)絡(luò)領(lǐng)域中，通過G?N 與WL 核方法進行融合，豐富圖的結(jié)構(gòu)特征和節(jié)點特征，提升G?N 對高階圖結(jié)構(gòu)的判別能力；

2）針對不同類型的圖數(shù)據(jù)集，提出基于注意力機制的圖結(jié)構(gòu)相似編碼和圖節(jié)點特征編碼的融合方法，完成兩者權(quán)重的自適應(yīng)學(xué)習(xí)；

3）在圖核中，使用Nystr?m 方法構(gòu)建一個低秩矩陣去近似原核矩陣，從而大大降低圖核矩陣的維度，解決圖核矩陣在計算中運算代價大的問題；

4）在7 個公開的圖數(shù)據(jù)集上，與一些當(dāng)前已知性能最好的多種代表性的圖分類基準模型相比，所提出的模型在大多數(shù)數(shù)據(jù)集上可以表現(xiàn)出更好的性能.

1 相關(guān)工作

1.1 基于WL 核的圖分類方法

WL 核是當(dāng)前應(yīng)用最廣泛的圖核方法之一，它是基于子樹的圖核方法，其主要思想是對圖進行子樹分解，使用子樹間的相似度來代替圖的相似度，它是一種基于1-WL 圖同構(gòu)測試所提出的一種快速特征提取算法，詳細的操作步驟為：對于擁有多個節(jié)點標簽的離散圖，首先對各個節(jié)點進行鄰域聚合；然后對鄰居節(jié)點進行排序，與此同時，節(jié)點標簽和排序后的鄰居標簽共同組成多重集，并對這些多重集進行壓縮映射，生成對應(yīng)的新標簽，進而將這些新標簽賦給節(jié)點，這樣就完成了一次迭代.在迭代過程中，重新標記的過程以及多重集的壓縮是所有輸入圖同時進行的，并且所有圖共享標簽壓縮的對應(yīng)關(guān)系.

具有H次迭代的2 個圖G1和圖G2上的WL 子樹核被定義為

1.2 基于圖同構(gòu)網(wǎng)絡(luò)（GIN）的圖分類方法

圖神經(jīng)網(wǎng)絡(luò)的任務(wù)主要是進行圖節(jié)點表征學(xué)習(xí)，并基于學(xué)習(xí)到的節(jié)點表征進行下游的任務(wù)，例如節(jié)點分類或者鏈路預(yù)測等.而G?N 提出了圖級別表示學(xué)習(xí)，即圖表征學(xué)習(xí).圖表征學(xué)習(xí)要求根據(jù)節(jié)點屬性、邊和邊的屬性（如果有的話）生成一個向量作為圖的表征，基于圖表征可以做圖的預(yù)測.基于G?N 的圖表征學(xué)習(xí)主要包含2 個過程：1）計算得到圖的節(jié)點特征，即每一個節(jié)點的特征依次聚合各個鄰居節(jié)點的特征，常用的圖神經(jīng)網(wǎng)絡(luò)節(jié)點聚集函數(shù)有求和函數(shù)、平均函數(shù)和最大化函數(shù).2）在G?N 中，節(jié)點聚集函數(shù)選擇的是求和函數(shù)，而不是選擇平均函數(shù)，原因是平均函數(shù)不能識別某一節(jié)點出現(xiàn)的次數(shù)，不能精確描述多重集，它只能捕捉實體的特征分布，而最大化函數(shù)適合捕捉具有代表性的元素或“骨架”，而不能區(qū)分確切的結(jié)構(gòu)或分布的任務(wù).圖神經(jīng)網(wǎng)絡(luò)還有其他的節(jié)點聚合函數(shù)，如加權(quán)平均、LSTM 池化等，而對判斷同構(gòu)問題來說，本文使用了基于注意力機制的自適應(yīng)加權(quán)求和方法，此方法具有較強的表征能力.

為了實現(xiàn)圖節(jié)點特征編碼與圖標簽的單射，G?N使用加法作為聚合函數(shù)，并使用多層感知機來模擬函數(shù)的組合，實現(xiàn)每層之間的映射關(guān)系，更新G?N 節(jié)點表示函數(shù)為：

其中hG是整個圖的嵌入表示，這里的讀出函數(shù)分別使用了求和、求平均和MLP.

1.3 Nystr?m 方法

圖核方法的計算代價比較大，對于一個有n個圖的數(shù)據(jù)集，得到的圖核矩陣是n2個元素，當(dāng)n非常大時，圖的結(jié)構(gòu)編碼維度就比較大，Nystr?m 方法[19]是作為一種使用簡單正交規(guī)則離散積分方程的方法而被提出的，是一種廣泛使用的降維方法，用于給定的列采樣子集逼近核矩陣[20].Nystr?m 常用在核空間的計算問題中，對于一個樣本集合 {x1,x2,…,xn},以及它們的核矩陣K∈Rn×n，Nystr?m 可通過采樣的方式，構(gòu)建一個低秩矩陣去近似表示原核矩陣，降低核矩陣在計算中的運算代價.Nystr?m 可以作為一種無監(jiān)督的降維編碼.同時，也可以得到核空間中樣本的矩陣表示

2 圖核同構(gòu)網(wǎng)絡(luò)KerGIN

本節(jié)將重點介紹KerG?N，該模型以G?N 為基礎(chǔ)，借助圖核方法，將圖的結(jié)構(gòu)特征和節(jié)點特征進行深度融合.本文提出的模型框架如圖2 所示，整個模型分為3 個部分：G?N 編碼器、圖核和注意力模塊，下面將對模型的每一部分進行詳細的介紹.首先介紹關(guān)于圖核和相關(guān)圖同構(gòu)網(wǎng)絡(luò)模型的一些基本概念.一個圖可以表示為g=(V,X,A)，其中V={v1,v2,…,vN} 表示圖節(jié)點的集合，X∈RN×d表示圖中節(jié)點的特征，總共有N個節(jié)點，每個節(jié)點的特征維度都是d，A∈RN×N表示圖的鄰接矩陣，本文所研究的圖都是無權(quán)無向圖，如果節(jié)點vi與vj之間存在邊，則Aij=1，否則Aij=0.對于圖分類問題，給定一個數(shù)據(jù)集{(g1,y1),(g2,y2),…,(gn,yn)}，其中y表示圖的標簽.圖分類任務(wù)的目的就是學(xué)習(xí)到由圖g到標簽y的映射函數(shù)yg=f(g).本文使用one-hot 編碼處理離散標簽.例如4 個標簽分別由4 維向量(1,0,0,0)，(0,1,0,0)，(0,0,1,0)，(0,0,0,1)來表示.

Fig.2 The overall architecture of KerG?N圖2 KerG?N 總體框架

2.1 GIN 編碼

根據(jù)圖的鄰接矩陣A和圖的特征X，使用G?N 對圖進行編碼，首先對每個節(jié)點進行鄰居的采樣和聚合，采樣一個節(jié)點的所有鄰居，聚合鄰居采用求和函數(shù)，即每個節(jié)點的特征加上鄰居節(jié)點的特征.節(jié)點特征采樣函數(shù)和聚合函數(shù)分別為：

其中Aggregate()是采樣鄰居節(jié)點函數(shù)，Combine()是求和函數(shù)，因為G?N 已經(jīng)證明了求和函數(shù)是單射的.進一步在k層得到的特征向量經(jīng)過一個多層感知機：

2.2 WL 圖核矩陣的生成

在2.1 節(jié)中G?N 已經(jīng)對圖進行了節(jié)點特征編碼，在本節(jié)中重點關(guān)注對于圖的結(jié)構(gòu)特征編碼.由于G?N對圖的結(jié)構(gòu)表征能力有限，所以引入一個圖核矩陣即圖的結(jié)構(gòu)相似性編碼來增強G?N 的結(jié)構(gòu)表征能力.

圖核用于計算2 個圖的相似度，對于一個圖數(shù)據(jù)集G={g1,g2,…,gN}，計算每2 個圖的核值，構(gòu)成核矩陣K∈RN×N，圖核矩陣中的i行表示的圖與其他圖gi的結(jié)構(gòu)相似度，相當(dāng)于對圖gi的結(jié)構(gòu)相似性編碼，本文使用的圖核是不帶節(jié)點標簽的WL 核，即輸入2 個圖的鄰接矩陣A∈RN×N，不需要節(jié)點的特征或者節(jié)點的標簽.如圖3 所示，對于2 個原始的圖，聚合其鄰居節(jié)點，然后對聚合后的每一個節(jié)點進行重新的哈希編碼，即對節(jié)點使用新的顏色來表示，這是進行1 次迭代所得到的結(jié)果，然后按顏色來統(tǒng)計所有節(jié)點的個數(shù)，這樣就把圖轉(zhuǎn)化為特征向量，最后2 個向量之間求內(nèi)積，即得到2 個圖的相似度，求2 個圖的核值函數(shù)為：

Fig.3 Diagram of the implementation process of WL kernel圖3 WL 核執(zhí)行過程圖

在WL 核的計算過程中，用內(nèi)積來度量2 個圖的子樹模式向量.本文也選取了其他常用的圖核函數(shù)進行了對比實驗，如最短路徑（shortest path,SP）核、隨機游走（random walk,RW）核，詳見3.4 節(jié)，最后采用了效果最優(yōu)的WL 核.

2.3 Nystr?m 降秩分解

在2.2 節(jié)中得到了圖數(shù)據(jù)集的核矩陣，這里的圖核矩陣的維度通常較大，空間復(fù)雜度為O(N2)，如果圖數(shù)據(jù)集的數(shù)量龐大，將導(dǎo)致后續(xù)的計算代價很大.Nystr?m 方法常用在核空間的計算問題中，通過降秩分解，可以顯著降低核矩陣的維度.核矩陣K∈RN×N是對稱正定矩陣，核矩陣的分解過程為：

由于降維后的核矩陣與2.1 節(jié)中G?N 編碼維度不一致，在這里使用神經(jīng)網(wǎng)絡(luò)對核矩陣的維度與G?N 編碼的向量對齊，定義一個2 層的神經(jīng)網(wǎng)絡(luò)，共享1 個隱藏層，為了防止梯度消失或梯度爆炸現(xiàn)象的出現(xiàn)，需要對核矩陣中的每一行進行規(guī)范化，并使用最小值中心化的方法進行歸一化，再經(jīng)過全連接神經(jīng)網(wǎng)絡(luò)得到圖核嵌入向量hk，即圖的結(jié)構(gòu)編碼，計算的函數(shù)表達式為：

2.4 GIN 編碼和WL 核編碼的融合

其中W∈Rd×d為權(quán)重向量，它可以使圖的嵌入計算更加平滑，a∈Rd×1為注意力權(quán)重向量，c∈R2×1為注意力系數(shù)，H∈Rd×1為圖特征編碼和圖結(jié)構(gòu)編碼的注意力加權(quán)融合后的向量表示，進一步將H輸入到多層感知機或者支持向量機中進行圖分類任務(wù).

KerG?N 提取圖特征的算法描述見算法1，輸入為一組圖數(shù)據(jù)集以及圖的鄰接矩陣和節(jié)點的特征.對每個圖使用G?N 進行特征編碼，即對每一個節(jié)點進行鄰域聚合，得到節(jié)點的嵌入表示，然后把所有節(jié)點的嵌入表示加起來，這樣就得到了圖的表征向量.與此同時使用WL 核求每2 個圖之間的核值，即對于每一個節(jié)點進行h次迭代的哈希編碼，這樣就把整個圖映射成一個向量，將2 個圖的向量表示進行內(nèi)積運算，這樣就得到了2 個圖的相似度，也即得到了圖的結(jié)構(gòu)編碼.進一步使用注意力機制將圖的特征編碼和圖的結(jié)構(gòu)編碼進行加權(quán)求和，進而得到圖的特征向量表示，并對所有的圖都進行上述的操作，最后將這些圖的向量表示輸入到多層感知機或支持向量機中進行下游的分類任務(wù).

算法1.KerG?N 提取特征.

3 實 驗

3.1 數(shù)據(jù)集的介紹和實驗設(shè)置

1）數(shù)據(jù)集.本文使用7 個公開的圖分類數(shù)據(jù)集進行實驗，分別為MUTAG[21]，PTC[22]，PROTE?NS[23]，NC?1[24]，?MDB-B[25]，?MDB-M[25]，COLLAB[25].前4 個為化學(xué)分子數(shù)據(jù)集，后3 個為社交網(wǎng)絡(luò)數(shù)據(jù)集.7 個數(shù)據(jù)集的簡介為：

①MUTAG[21].該數(shù)據(jù)集包含了188 個化合物結(jié)構(gòu)圖，依據(jù)它們對細菌的誘變作用，可被分為2 類.圖中的節(jié)點和節(jié)點標簽分別表示原子和原子種類，包括C,N,O,F,?,Cl,Br.

②PTC[22].該數(shù)據(jù)集全稱是預(yù)測毒理學(xué)挑戰(zhàn)，用來發(fā)展先進的SAR 技術(shù)預(yù)測毒理學(xué)模型.這個數(shù)據(jù)集包含了針對嚙齒動物的致癌性標記的化合物.圖中有2 個類別的標簽，分別表示有致癌性和無致癌性.

③PROTE?NS.該數(shù)據(jù)集[23]中有1 113 個蛋白質(zhì)結(jié)構(gòu)圖，圖的標簽分為2 類，分別表示酶或者非酶.節(jié)點表示蛋白質(zhì)的2 級結(jié)構(gòu)，根據(jù)2 級結(jié)構(gòu)在氨基酸序列或者蛋白質(zhì)3 維空間中是否為鄰居來確定節(jié)點之間邊的存在性.

④NC?1[24].該數(shù)據(jù)集是一個關(guān)于化學(xué)分子的數(shù)據(jù)集，是根據(jù)非小細胞肺癌活性篩選的，圖的標簽分為2 類，表示具有或不具有抗癌活性，共包含4 110個化合物的圖結(jié)構(gòu).

⑤?MDB-B[25].該數(shù)據(jù)集是一個電影合作數(shù)據(jù)集，來源于互聯(lián)網(wǎng)電影數(shù)據(jù)庫?MDB.圖中的節(jié)點表示演員，如果2 個演員在同一部電影中出現(xiàn)，則他們對應(yīng)的節(jié)點之間就存在一條邊，這些合作圖分為動作和浪漫2 種類型.合作圖是以每個演員為中心的網(wǎng)絡(luò)圖，圖分類的任務(wù)是判斷這些自我中心網(wǎng)絡(luò)圖屬于動作類型還是浪漫類型.此外該數(shù)據(jù)集還有一個多類型版本.

⑥?MDB-M[25].該數(shù)據(jù)集的任務(wù)也是對演員子網(wǎng)絡(luò)圖按電影類型進行分類.

⑦COLLAB[25].該數(shù)據(jù)集是一個關(guān)于科研合作的數(shù)據(jù)集，涵蓋了高能物理、凝聚態(tài)物理和天文物理3個領(lǐng)域中生成的不同研究人員的自我中心網(wǎng)絡(luò)(egonetwork)圖、對應(yīng)的圖標簽為研究人員所屬的研究領(lǐng)域.分類的任務(wù)是確定這些自我中心網(wǎng)絡(luò)圖對應(yīng)的研究人員所屬的研究領(lǐng)域.

實驗中使用的7 個圖數(shù)據(jù)集的信息統(tǒng)計結(jié)果如表1 所示.

Table 1 Information Statistic of Datasets表1 數(shù)據(jù)集的信息統(tǒng)計

2）基準方法.本文將選擇當(dāng)前已知性能最好的多種代表性圖分類方法作為基準方法進行實驗對比，分別為基于圖核的方法、基于圖神經(jīng)網(wǎng)絡(luò)的分類方法、基于圖池化的分類方法以及近幾年一些與圖核結(jié)合的圖神經(jīng)網(wǎng)絡(luò)方法，以此來證明本文模型的有效性.基于圖核的圖分類方法有WL 核[14]和DGK 核[25]，基于圖神經(jīng)網(wǎng)絡(luò)的圖分類方法包括G?N[15]，DCNN[26]，PATCHY-SAN[27].基于圖池化的圖分類方法有SUGAR[28]、AVCN(H)[29]，SL?M[30].基于圖核與圖神經(jīng)網(wǎng)絡(luò)融合的圖分類方法有GCKN[11]，GSKN[12]，GSNN[31].本文的分類任務(wù)屬于有監(jiān)督學(xué)習(xí).

3）參數(shù)設(shè)置.模型訓(xùn)練過程中采用常用的參數(shù)設(shè)置，設(shè)置學(xué)習(xí)率lr=0.000 1，訓(xùn)練批次batch_size=16，epoch=600，Nystr?m 方法[19]中對核矩陣降秩分解后的維度d為數(shù)據(jù)集中圖數(shù)量的1/2，全連接層神經(jīng)網(wǎng)絡(luò)中隱藏層維度分別為16 和8.WL 核的迭代次數(shù)h=3.數(shù)據(jù)集中90%作為訓(xùn)練集，其余的10%作為測試集.

3.2 實驗結(jié)果

本節(jié)將在7 個數(shù)據(jù)集上對KerG?N 和其他所有基準方法進行分類評估.本文采用10 次10 交叉驗證，即將數(shù)據(jù)集分成10 份，每次取1 份作為測試集，剩下的9 份作為訓(xùn)練集；然后對這10 次的結(jié)果求平均.每個數(shù)據(jù)集的分類準確度如表2 所示.

Table 2 Classification Accuracy on Each Public Dataset表2 在各個公開數(shù)據(jù)集上的分類準確度 %

表2 展示所有方法在7 個公開數(shù)據(jù)集的測試準確度.KerG?N 在大多數(shù)數(shù)據(jù)集上的表現(xiàn)優(yōu)于基準方法.其中MUTAG 數(shù)據(jù)集的平均準確度為95.2%，高于除SUGAR 外的所有基準方法.與GSKN 相比，KerG?N 的準確度在PTC 數(shù)據(jù)集上提升了3.3 個百分比.在PROTE?NS 數(shù)據(jù)集上，KerG?N 的準確度相比GSKN 方法提升了6.1 個百分比.對于NC?1 數(shù)據(jù)集，KerG?N 的準確度比GCKN 提升了4.8 個百分比.在?MDB-B 和?MDB-M 數(shù)據(jù)集上，KerG?N 的準確度比準確度排名第2 的GSKN 方法分別提升了1.7 個百分比和0.8 個百分比.在COLLAB 數(shù)據(jù)集上，KerG?N準確度接近于最先進的GCKN 方法.特別是在一些化學(xué)分子數(shù)據(jù)集上KerG?N 表現(xiàn)更突出，與最新的2個基于圖核的圖神經(jīng)網(wǎng)絡(luò)方法相比，KerG?N 具有更優(yōu)越的性能.

為了比較不同方法的綜合性能，分別統(tǒng)計了不同方法的平均排名，即對每一個方法，求出其在各個數(shù)據(jù)集上分類準確度的平均排名情況，相關(guān)的計算公式為：

在圖4（a）中，與所有基準方法比較，KerG?N 在7個公開的圖分類數(shù)據(jù)集上，相比較最優(yōu)的基準方法，準確度的平均排名為1.由此可知KerG?N 的圖分類性能要優(yōu)于大多數(shù)基準方法.如圖4（b）所示，KerG?N相較于最優(yōu)的基準方法在6 個數(shù)據(jù)集上的分類準確度都有不同程度的提升.由于KerG?N 在MUTAG 數(shù)據(jù)集上沒有提升，所以在圖4（b）中只選擇了有提升的6 個數(shù)據(jù)集進行展示.其中，在PROTE?NS 數(shù)據(jù)集上提升了7.5%，在?MDB-B 數(shù)據(jù)集上提升了約2.1%，在PTC 數(shù)據(jù)集上提升了約3.8%，在NC?1 數(shù)據(jù)集上提升了0.93%，在?MDB-M 數(shù)據(jù)集上提升了1.34%，在COLLAB 數(shù)據(jù)集上提升了0.36%.

Fig.4 Average rank and accuracy improvement rate of various methods圖4 各種方法的平均排名和KerG?N 的準確度提升率

3.3 消融實驗

為了驗證圖核模塊是否在整個模型中起關(guān)鍵作用以及MLP 對分類準確度的影響，設(shè)計了一組消融實驗，即將KerG?N 模型中的圖核模塊（G?NMLP），與本文方法KerG?N 和基準模型G?N 進行比較.從表3 可以看出，G?N-MLP 和G?N 的圖分類準確度差異并不大，說明在KerG?N 中起到關(guān)鍵作用的不是MLP.比較G?N-MLP 和KerG?N 模型的圖分類準確度可以得出：圖核模塊在整個模型中起了關(guān)鍵作用.

Table 3 Ablation Experiment Based on MLP and Graph Kernel表3 基于MLP 與圖核的消融實驗

為了研究注意力機制對圖分類結(jié)果的影響及注意力機制的作用，選擇了2 種常見的融合策略進行對比實驗，分別為拼接和求和，即把圖結(jié)構(gòu)編碼和圖特征編碼拼接或者求和.如表4 所示，KerG?N-con 表示采用拼接策略，KerG?N-sum 表示采用求和策略，KerG?N-att 表示采用注意力機制策略.可以看出，采用拼接策略的分類效果不及求和策略和注意力機制策略，而采用注意力機制策略的分類準確度在這3種策略中最高.因此，在本文中注意力機制是較適宜的融合策略.這是因為不同數(shù)據(jù)集對于圖結(jié)構(gòu)編碼和圖特征編碼的偏重程度不同，因此簡單拼接和求和很難獲得好的實驗效果.

Table 4 Ablation Experiment Using with Different Fusion Strategies表4 使用不同融合策略的消融實驗

3.4 實驗分析

本節(jié)將分析模型訓(xùn)練的過程以及圖結(jié)構(gòu)編碼和圖特征編碼在不同類型數(shù)據(jù)集上的變化情況.圖5 展示了 MUTAG，PTC，PROTE?NS，NC?1，?MDB-B，?MDB-M 這6 個數(shù)據(jù)集在訓(xùn)練和測試過程中的損失值隨訓(xùn)練輪數(shù)的變化情況.為便于排版，本文選擇了前6 個數(shù)據(jù)集的損失變化情況進行圖例展示.這6 個數(shù)據(jù)集整體在100 個訓(xùn)練輪數(shù)時損失下降得比較快，在400 個訓(xùn)練輪數(shù)時損失下降的幅度較少，在600 個訓(xùn)練輪數(shù)時基本趨向于收斂.其中MUTAG 數(shù)據(jù)集在500 個訓(xùn)練輪數(shù)時收斂，PTC 數(shù)據(jù)集在450 個訓(xùn)練輪數(shù)時收斂，PROTE?NS 數(shù)據(jù)集在200 個訓(xùn)練輪數(shù)時開始收斂，NC?1 數(shù)據(jù)集在100 個訓(xùn)練輪數(shù)時收斂.?MDB-B 數(shù)據(jù)集大約在600 個訓(xùn)練輪數(shù)時收斂，?MDB-M 在200 個訓(xùn)練輪數(shù)時開始收斂.6 個數(shù)據(jù)集在訓(xùn)練的過程中，訓(xùn)練集損失值和測試集損失值之間的差距很小，所以在訓(xùn)練過程中沒有過擬合或欠擬合現(xiàn)象.

Fig.5 Variation of loss values for training and testing on six datasets圖5 6 個數(shù)據(jù)集上訓(xùn)練與測試的損失值變化

任何圖神經(jīng)網(wǎng)絡(luò)編碼器都能用作圖特征編碼，本文除了實驗中使用的G?N 編碼器，還使用了2 種流行的圖神經(jīng)網(wǎng)絡(luò)框架：GCN 和圖注意力網(wǎng)絡(luò)GAT進行了對比實驗.實驗結(jié)果如圖6（a）所示，可以觀察到G?N 的編碼效果要好于GCN 和GAT.這可能是因為G?N 的圖表達能力更加強大，更適用于圖的特征編碼.此外，又研究了圖核編碼器的長度對圖分類性能的影響，圖6（b）顯示了在7 個公開數(shù)據(jù)集上16～160 的不同圖核編碼長度的KerG?N 的準確度.可以看出，在一定范圍內(nèi)，圖分類的準確度會隨圖核編碼器長度的增加而增加，當(dāng)圖核編碼器長度大于160 時，圖核編碼器長度對圖分類準確度的影響較小，所以在一定范圍內(nèi)核編碼器長度對分類準確度有重要影響，因此適當(dāng)降低核編碼器的維度不會影響圖分類的準確度.

Fig.6 KerG?N based on different graph encoders and KerG?N based on different length kernel encoders圖6 基于不同圖編碼器的KerG?N 和基于不同長度圖核編碼器的KerG?N

如圖7（a）所示，7 個數(shù)據(jù)集權(quán)重系數(shù)都不相同，但是可以明顯看出前4 個數(shù)據(jù)集的圖結(jié)構(gòu)編碼的權(quán)重大于圖特征編碼，后3 個數(shù)據(jù)集的圖結(jié)構(gòu)編碼的權(quán)重小于圖特征編碼.由于前4 種圖數(shù)據(jù)集為化學(xué)分子、后3 種圖數(shù)據(jù)集為社交網(wǎng)絡(luò)，因此在這2 種數(shù)據(jù)集上，圖結(jié)構(gòu)編碼和圖特征編碼的權(quán)重系數(shù)不同.進一步，又探討了不同圖核函數(shù)對KerG?N 分類準確度的影響，因為圖核函數(shù)的選擇通常是根據(jù)專家經(jīng)驗進行選取，很難直接確定KerG?N 更適用于哪種圖核函數(shù)，因此，本文選擇了3 種類型的圖核函數(shù)RW，SP，WL，并通過實驗對比展示了哪種圖核更適用于KerG?N 的圖結(jié)構(gòu)編碼.在圖7（b）中，由于RW 核在大數(shù)據(jù)集上運行時間過長，所以選擇了在4 個小數(shù)據(jù)集上進行實驗.可以清楚地看出WL 核在4 個數(shù)據(jù)集上綜合表現(xiàn)最好，其次是SP 核，RW 核實驗效果最差，此外RW 核時間復(fù)雜度比較大，在一定的時間內(nèi)無法完成一些大規(guī)模圖數(shù)據(jù)集的實驗.

Fig.7 The weight ratio of graph feature coding and structure coding,and the classification accuracy under different graph kernels圖7 圖特征編碼和結(jié)構(gòu)編碼的權(quán)重占比和不同圖核下的分類準確度

通過以上實驗分析可以得出，本文方法在化學(xué)分子數(shù)據(jù)集上的分類準確度比在社交網(wǎng)絡(luò)數(shù)據(jù)集上具有明顯的優(yōu)勢，因此本文方法更適用于化學(xué)分子的圖分類任務(wù).此外，化學(xué)分子的特性受特定局部子結(jié)構(gòu)的影響較大，所以圖結(jié)構(gòu)編碼對其分類準確度起至關(guān)重要的作用，甚至1 個局部子結(jié)構(gòu)就可以成為其分類的主要依據(jù)，比如官能團（functional group）.而對于社交網(wǎng)絡(luò)數(shù)據(jù)集來說，它對圖特定子結(jié)構(gòu)的依賴性相對較小，而對圖節(jié)點特征依賴性較大.

4 結(jié)論

本文提出了一種基于G?N、圖核以及注意力機制相融合的圖表征學(xué)習(xí)和圖分類的方法，該方法提升了G?N 對圖中特定結(jié)構(gòu)的判別能力.實驗結(jié)果表明，圖結(jié)構(gòu)編碼對圖分類結(jié)果影響較大，將圖核作為圖結(jié)構(gòu)編碼，在一定程度上解決了基于消息傳遞的圖神經(jīng)網(wǎng)絡(luò)無法識別圖中高階信息的問題，本文方法能夠自適應(yīng)調(diào)節(jié)圖特征編碼與圖結(jié)構(gòu)編碼的權(quán)重，對圖分類的準確度有較大的提升，在分類準確度上優(yōu)于所選的一些基準方法.

作者貢獻聲明：徐立祥提出了算法思路和實驗方案，并撰寫論文；葛偉負責(zé)完成實驗驗證，并整理論文；陳恩紅和羅斌提出指導(dǎo)意見并修改論文.