基于圖核同構網絡的圖分類方法

徐立祥 葛 偉 陳恩紅 羅 斌

1（合肥學院人工智能與大數據學院 合肥 230601）

2（大數據分析與應用安徽省重點實驗室（中國科學技術大學計算機科學與技術學院） 合肥 230027）

3（安徽大學計算機科學與技術學院 合肥 230601）

（xulixianghf@163.com）

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

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

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

Fig.1 The process of graph classification based on graph neural networks圖1 基于圖神經網絡的圖分類過程

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

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

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

1）提供了一個新的視角，將WL 核應用到圖神經網絡領域中，通過G?N 與WL 核方法進行融合，豐富圖的結構特征和節點特征，提升G?N 對高階圖結構的判別能力；

2）針對不同類型的圖數據集，提出基于注意力機制的圖結構相似編碼和圖節點特征編碼的融合方法，完成兩者權重的自適應學習；

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

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

1 相關工作

1.1 基于WL 核的圖分類方法

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

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

1.2 基于圖同構網絡（GIN）的圖分類方法

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

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

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

1.3 Nystr?m 方法

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

2 圖核同構網絡KerGIN

本節將重點介紹KerG?N，該模型以G?N 為基礎，借助圖核方法，將圖的結構特征和節點特征進行深度融合.本文提出的模型框架如圖2 所示，整個模型分為3 個部分：G?N 編碼器、圖核和注意力模塊，下面將對模型的每一部分進行詳細的介紹.首先介紹關于圖核和相關圖同構網絡模型的一些基本概念.一個圖可以表示為g=(V,X,A)，其中V={v1,v2,…,vN} 表示圖節點的集合，X∈RN×d表示圖中節點的特征，總共有N個節點，每個節點的特征維度都是d，A∈RN×N表示圖的鄰接矩陣，本文所研究的圖都是無權無向圖，如果節點vi與vj之間存在邊，則Aij=1，否則Aij=0.對于圖分類問題，給定一個數據集{(g1,y1),(g2,y2),…,(gn,yn)}，其中y表示圖的標簽.圖分類任務的目的就是學習到由圖g到標簽y的映射函數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 編碼

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

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

2.2 WL 圖核矩陣的生成

在2.1 節中G?N 已經對圖進行了節點特征編碼，在本節中重點關注對于圖的結構特征編碼.由于G?N對圖的結構表征能力有限，所以引入一個圖核矩陣即圖的結構相似性編碼來增強G?N 的結構表征能力.

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

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

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

2.3 Nystr?m 降秩分解

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

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

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

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

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

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

3 實 驗

3.1 數據集的介紹和實驗設置

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

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

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

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

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

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

⑥?MDB-M[25].該數據集的任務也是對演員子網絡圖按電影類型進行分類.

⑦COLLAB[25].該數據集是一個關于科研合作的數據集，涵蓋了高能物理、凝聚態物理和天文物理3個領域中生成的不同研究人員的自我中心網絡(egonetwork)圖、對應的圖標簽為研究人員所屬的研究領域.分類的任務是確定這些自我中心網絡圖對應的研究人員所屬的研究領域.

實驗中使用的7 個圖數據集的信息統計結果如表1 所示.

Table 1 Information Statistic of Datasets表1 數據集的信息統計

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

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

3.2 實驗結果

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

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

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

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

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

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

3.3 消融實驗

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

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

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

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

3.4 實驗分析

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

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

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

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

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

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

4 結論

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

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