用于非精確圖匹配的改進(jìn)GCN模型*

李昌華，崔李揚(yáng)，李智杰

西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055

1 引言

圖是一種豐富的表示形式，可以描述現(xiàn)實(shí)世界中復(fù)雜的結(jié)構(gòu)數(shù)據(jù)，如化合物集合、蛋白質(zhì)結(jié)構(gòu)、社交網(wǎng)絡(luò)等。隨著深度學(xué)習(xí)技術(shù)應(yīng)用于許多領(lǐng)域，并且較傳統(tǒng)方法有明顯優(yōu)勢(shì)，利用神經(jīng)網(wǎng)絡(luò)對(duì)拓?fù)浣Y(jié)構(gòu)特征的學(xué)習(xí)和查詢?yōu)楦咝У膱D匹配算法帶來(lái)了應(yīng)用需求。

圖匹配方法可以分為兩類，精確圖匹配和非精確圖匹配。精確圖匹配要求被匹配的對(duì)象之間要嚴(yán)格對(duì)應(yīng)[1]。然而，這種匹配算法的強(qiáng)約束條件對(duì)于實(shí)際應(yīng)用來(lái)說(shuō)過(guò)于嚴(yán)格，并被證明是NP完全問(wèn)題。相對(duì)于精確圖匹配，非精確圖匹配方法允許在相似模型下有一定的容錯(cuò)，即使被匹配的圖在結(jié)構(gòu)上有一定的差異，也能進(jìn)行匹配，這使得非精確圖匹配受到研究者們的重視。雖然目前已經(jīng)有很多非精確圖匹配問(wèn)題的研究，但是現(xiàn)有算法的識(shí)別率、有效性仍不能滿足要求。

卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural networks，CNN）作為一種深度監(jiān)督學(xué)習(xí)框架，在計(jì)算機(jī)視覺(jué)[2]、語(yǔ)音識(shí)別[3]、博弈[4]等領(lǐng)域都表現(xiàn)出了優(yōu)異的性能。對(duì)于圖像、視頻和聲音等數(shù)據(jù)，它們都具有固定大小的鄰域，因此CNN 中的卷積、池化等操作是有意義的。然而，圖是一種結(jié)構(gòu)化數(shù)據(jù)類型，沒(méi)有固定的鄰域，傳統(tǒng)的CNN不能直接作用于圖。而為了將CNN應(yīng)用于圖結(jié)構(gòu)數(shù)據(jù)，研究者們提出了多種方法[5-9]。這些方法可以分為兩類：基于空間的方法和基于譜的方法?；诳臻g的方法是利用圖的空間鄰域信息進(jìn)行卷積運(yùn)算。基于譜的方法通常使用拉普拉斯變換對(duì)結(jié)構(gòu)圖進(jìn)行變換，然后使用特征向量作為卷積算子。文獻(xiàn)[10]提出了一個(gè)學(xué)習(xí)圖的CNN 框架，通過(guò)使用圖標(biāo)記程序來(lái)構(gòu)建一個(gè)感受野。上述方法雖然在一定程度上解決了將CNN 應(yīng)用于圖的問(wèn)題，但是依然存在對(duì)圖結(jié)構(gòu)本身挖掘不夠充分的問(wèn)題。

為了解決這些局限性，本文通過(guò)引入圖卷積神經(jīng)網(wǎng)絡(luò)（graph convolutional network，GCN），改進(jìn)從拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)映射為網(wǎng)格結(jié)構(gòu)數(shù)據(jù)作為卷積神經(jīng)網(wǎng)絡(luò)輸入的過(guò)程，主要工作如下：首先通過(guò)社交網(wǎng)絡(luò)分析（social network analysis，SNA）[11]中三種衡量網(wǎng)絡(luò)節(jié)點(diǎn)中心度的方法對(duì)比并獲取最優(yōu)有序節(jié)點(diǎn)序列，選取代表節(jié)點(diǎn)；其次針對(duì)節(jié)點(diǎn)鄰域大小不滿足感受野閾值的情況，對(duì)節(jié)點(diǎn)鄰域進(jìn)行中心度排序，依次獲取鄰域節(jié)點(diǎn)的一階鄰域，直到鄰域大小滿足感受野閾值。改進(jìn)的GCN 在把拓?fù)浣Y(jié)構(gòu)處理為網(wǎng)格結(jié)構(gòu)時(shí)，其節(jié)點(diǎn)鄰域圖能最大限度表示原圖結(jié)構(gòu)，之后對(duì)鄰域進(jìn)行歸一化處理，結(jié)合卷積神經(jīng)網(wǎng)絡(luò)模型對(duì)圖進(jìn)行訓(xùn)練與識(shí)別。圖1展示了該模型的算法流程，其中左邊虛框?yàn)橛?xùn)練過(guò)程，右邊虛框?yàn)闇y(cè)試過(guò)程，實(shí)驗(yàn)表明該方法可以更有效地保留數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)信息，提高非精確圖匹配精度。

Fig.1 Algorithm flow of model圖1 模型算法流程

2 GCN的相關(guān)工作

在深度學(xué)習(xí)領(lǐng)域，用于處理圖這種非歐幾里德數(shù)據(jù)的CNN稱之為圖卷積神經(jīng)網(wǎng)絡(luò)（GCN）。這種方法的做法通常是將標(biāo)準(zhǔn)的CNN應(yīng)用于圖數(shù)據(jù)特征學(xué)習(xí)，相對(duì)于在圖像上的卷積[12]，在圖上的卷積需要考慮其空間結(jié)構(gòu)。文獻(xiàn)[13]提出一種圖神經(jīng)網(wǎng)絡(luò)框架，文獻(xiàn)[14]對(duì)其進(jìn)行了簡(jiǎn)化，利用循環(huán)神經(jīng)網(wǎng)絡(luò)將每個(gè)節(jié)點(diǎn)嵌入到歐氏空間中，并將這些嵌入作為節(jié)點(diǎn)或圖的分類與回歸特征，然而這種算法的引入?yún)?shù)較多，效率比較低。為了減少學(xué)習(xí)參數(shù)的數(shù)量，文獻(xiàn)[15]引入了構(gòu)建局部感受野的概念。這種方法的思想是將基于相似性度量的特性組合在一起，例如在兩個(gè)連續(xù)層之間選擇有限數(shù)量的連接。雖然該模型利用局部性假設(shè)減少了參數(shù)的數(shù)量，但并沒(méi)有試圖利用任何平穩(wěn)性，即沒(méi)有權(quán)值共享策略。文獻(xiàn)[16]將這一思想用于圖CNN的空間表示（空間規(guī)劃）。他們使用加權(quán)圖來(lái)定義局部鄰域，并為池操作計(jì)算圖的多尺度聚類。然而，在空間結(jié)構(gòu)中誘導(dǎo)權(quán)重共享是具有挑戰(zhàn)性的，因?yàn)楫?dāng)缺少特定于問(wèn)題的排序（空間、時(shí)間或其他）時(shí)，需要選擇和排序鄰域。文獻(xiàn)[17]提出了一種從數(shù)據(jù)中學(xué)習(xí)圖形結(jié)構(gòu)的策略，并將該模型應(yīng)用于圖像識(shí)別、文本分類和生物信息學(xué)。然而，由于需要與圖的傅里葉基U相乘，這種方法并沒(méi)有擴(kuò)大。

文獻(xiàn)[10]提出了一種獲取圖數(shù)據(jù)的局部接受域并應(yīng)用于CNN 的方法，該方法可以得到一個(gè)標(biāo)準(zhǔn)CNN可以處理的一維數(shù)據(jù)單元，文獻(xiàn)[18]是在該方法的基礎(chǔ)上添加了一個(gè)預(yù)處理卷積層，文獻(xiàn)[19]是在卷積之前對(duì)數(shù)據(jù)進(jìn)行了排序，這些方法雖然在一定程度上優(yōu)化了文獻(xiàn)[10]中的方法，然而它們都局限在對(duì)卷積的處理，并沒(méi)有考慮到把拓?fù)浣Y(jié)構(gòu)映射到網(wǎng)格結(jié)構(gòu)的過(guò)程中對(duì)數(shù)據(jù)的最優(yōu)表示，因此無(wú)法保證獲取的節(jié)點(diǎn)鄰域能最大化表示節(jié)點(diǎn)的領(lǐng)域特征。本文的工作充分利用其優(yōu)點(diǎn)，并且在關(guān)鍵節(jié)點(diǎn)選擇與獲取節(jié)點(diǎn)鄰域上進(jìn)行改進(jìn)，使節(jié)點(diǎn)鄰域能最大化表示拓?fù)鋱D結(jié)構(gòu)，進(jìn)而利用改進(jìn)的GCN 模型處理非精確圖匹配問(wèn)題。

3 改進(jìn)的GCN模型

本章描述了用于圖匹配的改進(jìn)圖卷積神經(jīng)網(wǎng)絡(luò)模型。首先，圖的分類匹配問(wèn)題可以歸結(jié)如下。

標(biāo)記圖可以表示為G=(V,E,α)，V是頂點(diǎn)集合，E=V×V是邊的集合，α是頂點(diǎn)標(biāo)記函數(shù)，α:V→∑V，其中∑V是節(jié)點(diǎn)標(biāo)簽的內(nèi)容。示例：其中x是圖集，xi∈x，yi∈y={+1,-1}是目標(biāo)標(biāo)簽，圖分類匹配問(wèn)題可以映射為f:x→y的函數(shù)求解問(wèn)題。

因此把CNN 應(yīng)用于拓?fù)浣Y(jié)構(gòu)，首先需要對(duì)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)進(jìn)行處理，如何保證選取的關(guān)鍵節(jié)點(diǎn)具有代表性，以及在獲取節(jié)點(diǎn)鄰域過(guò)程中保證鄰域節(jié)點(diǎn)能較完整表示圖的結(jié)構(gòu)是一些亟待解決的關(guān)鍵問(wèn)題。為解決這些問(wèn)題，本文提出一種新的算法模型，如圖2 所示。首先使用三種求取網(wǎng)絡(luò)節(jié)點(diǎn)中心度的方法對(duì)節(jié)點(diǎn)進(jìn)行度量并排序，選取關(guān)鍵節(jié)點(diǎn)，然后利用中心度對(duì)鄰域節(jié)點(diǎn)排序并依次獲取節(jié)點(diǎn)鄰域。模型主要包括：

（1）代表節(jié)點(diǎn)選擇：通過(guò)SNA中三種網(wǎng)絡(luò)節(jié)點(diǎn)中心度度量方式計(jì)算節(jié)點(diǎn)中心度，獲取節(jié)點(diǎn)有序序列，通過(guò)對(duì)比來(lái)選取最優(yōu)代表節(jié)點(diǎn)。

（2）鄰域節(jié)點(diǎn)排序（neighbour node sort，NNS）：對(duì)鄰域節(jié)點(diǎn)進(jìn)行中心度排序，按中心度大小依次進(jìn)行鄰域節(jié)點(diǎn)的選取。

（3）鄰域節(jié)點(diǎn)歸一化：把節(jié)點(diǎn)鄰域規(guī)范化為網(wǎng)格結(jié)構(gòu)，作為卷積神經(jīng)網(wǎng)絡(luò)的輸入。

（4）特征學(xué)習(xí)：歸一化的圖結(jié)構(gòu)數(shù)據(jù)經(jīng)過(guò)兩層卷積以及全連接層進(jìn)行特征學(xué)習(xí)。

在圖2的模型結(jié)構(gòu)中，其輸入是數(shù)據(jù)集MUTAG[20]中的任意一個(gè)圖，首先節(jié)點(diǎn)經(jīng)過(guò)中心度大小排序選出代表節(jié)點(diǎn)，圖示給出三個(gè)代表節(jié)點(diǎn)的例子，其次經(jīng)過(guò)鄰域節(jié)點(diǎn)排序，獲得節(jié)點(diǎn)鄰域，歸一化之后獲得網(wǎng)格圖，作為卷積神經(jīng)網(wǎng)絡(luò)的輸入。

3.1 代表節(jié)點(diǎn)選擇

Fig.2 Improved model structure圖2 改進(jìn)的模型結(jié)構(gòu)

本文使用三種網(wǎng)絡(luò)節(jié)點(diǎn)中心度度量方法獲取代表節(jié)點(diǎn)。中心度（centrality）[11]是SNA 中常用的一個(gè)概念，用以表達(dá)社交網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中所在中心的程度，這個(gè)程度用數(shù)字來(lái)表示就被稱作中心度。本文使用的測(cè)定節(jié)點(diǎn)中心度的方法有度中心度（degree centrality，DC）[11]、接近中心度（closeness centrality，CC）[21]、中介中心度（betweenness centrality，BC）[22]。

（1）DC：節(jié)點(diǎn)v的度，對(duì)于無(wú)向圖來(lái)說(shuō)是連接該節(jié)點(diǎn)的邊數(shù)，對(duì)于有向圖，存在出度與入度。出度為從節(jié)點(diǎn)v出發(fā)的有向邊，入度為指向節(jié)點(diǎn)v的有向邊。本文主要討論無(wú)向圖，因此節(jié)點(diǎn)v的度中心度：

（2）CC：如果一個(gè)節(jié)點(diǎn)與許多其他節(jié)點(diǎn)接近，那么該節(jié)點(diǎn)處于網(wǎng)絡(luò)中心位置，這種度量方式稱之為接近中心度：

設(shè)圖G(V,E,α)，其中V表示節(jié)點(diǎn)集合，E表示邊的集合，則上式|V|表示節(jié)點(diǎn)的個(gè)數(shù)，dvi表示節(jié)點(diǎn)v與節(jié)點(diǎn)i之間的距離。接近中心度體現(xiàn)的是一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的鄰近程度。

（3）BC：中介中心度是計(jì)算經(jīng)過(guò)一個(gè)點(diǎn)的最短路徑的數(shù)量。經(jīng)過(guò)一個(gè)點(diǎn)的最短路徑數(shù)量越多，就說(shuō)明它的中介中心度越高。中介中心度表示為：

其中，σst(v)表示經(jīng)過(guò)節(jié)點(diǎn)v，s→t的最短路徑數(shù)，σst表示s→t的最短路徑數(shù)。

中心度的計(jì)算決定了代表性節(jié)點(diǎn)的選擇，從而對(duì)訓(xùn)練結(jié)果有著直接的影響，因此一個(gè)好的中心度選取算法的重要性不言而喻。利用中心度獲取代表節(jié)點(diǎn)序列分為兩步，首先根據(jù)中心度算法計(jì)算節(jié)點(diǎn)的中心度并以此排序，其次選取w個(gè)代表節(jié)點(diǎn)序列。其算法流程如下：

代表節(jié)點(diǎn)的選擇是算法2 通過(guò)調(diào)用算法1 計(jì)算而來(lái)，首先對(duì)于一個(gè)圖G(V,E,α)，作為算法2 的輸入Selectnode(G)，獲取其節(jié)點(diǎn)V，并通過(guò)算法1Getcentra-lity 獲取每個(gè)節(jié)點(diǎn)的中心度CV={Cv:V}，并按中心度Cv大小對(duì)節(jié)點(diǎn)排序，獲取有序序列Vsort，并從Vsort中獲取前w個(gè)節(jié)點(diǎn)，對(duì)|Vsort|不滿足w大小補(bǔ)充零點(diǎn)vzero，最終得到代表節(jié)點(diǎn)序列Vkey。

3.2 鄰域節(jié)點(diǎn)排序

對(duì)于一個(gè)圖G=(V,E,α)，設(shè)n是圖中節(jié)點(diǎn)的個(gè)數(shù)，m是邊緣個(gè)數(shù)。那么圖可以用一個(gè)n×n鄰接矩陣A表示，如果節(jié)點(diǎn)vi到節(jié)點(diǎn)vj之間有邊存在，令A(yù)i,j=1，否則Ai,j=0。N1(v) 是節(jié)點(diǎn)v的一階鄰域，即N1(v)中的節(jié)點(diǎn)都與節(jié)點(diǎn)v相鄰。

CNN 對(duì)圖像進(jìn)行卷積操作，每個(gè)像素都有相同的鄰域大小，因此節(jié)點(diǎn)鄰域的大小要與第一層卷積的感受野大小相同。本文通過(guò)對(duì)鄰域節(jié)點(diǎn)排序，按照鄰域節(jié)點(diǎn)中心度大小依次獲取鄰域節(jié)點(diǎn)。鄰域可以表示為：

其中，j是圖的節(jié)點(diǎn)數(shù)目并且j∈R，j

當(dāng)j=1 時(shí)，N1(v)表示與節(jié)點(diǎn)v直接相鄰的節(jié)點(diǎn)集合。在本文中獲取關(guān)鍵節(jié)點(diǎn)的鄰域過(guò)程：設(shè)鄰域大小為k，即集合N(v)的長(zhǎng)度len需要等于k。在實(shí)際的算法過(guò)程中，首先獲取節(jié)點(diǎn)v的1 階鄰域，可能會(huì)存在len>k與lenk時(shí)，利用獲取關(guān)鍵節(jié)點(diǎn)中心度的方法對(duì)鄰域節(jié)點(diǎn)進(jìn)行度量并排序，依次獲取1 階有序鄰域節(jié)點(diǎn)，使len=k；當(dāng)len

結(jié)合式（4）和式（5）來(lái)說(shuō)明鄰域節(jié)點(diǎn)排序獲取節(jié)點(diǎn)鄰域的過(guò)程。式（6）表示與節(jié)點(diǎn)v相鄰節(jié)點(diǎn)vi到vm的集合，即1 階鄰域，1 階鄰域通過(guò)式（7）的SN(v)函數(shù)之后獲得有序的鄰域節(jié)點(diǎn)，按中心度大小依次獲取2階鄰域，其2階鄰域表示為式（8），在不滿足預(yù)設(shè)鄰域k時(shí)，以式（6）～式（8）的計(jì)算公式獲取節(jié)點(diǎn)v的Nj鄰域，那么關(guān)鍵節(jié)點(diǎn)的鄰域N(v)表示節(jié)點(diǎn)v的1到j(luò)階鄰域的并集，如式（9）所表示，即式（4）的鄰域。

在上述式子中，C(v)是節(jié)點(diǎn)中心度函數(shù)，sort(?)是按照節(jié)點(diǎn)中心度對(duì)節(jié)點(diǎn)進(jìn)行排序，SN(v)是通過(guò)網(wǎng)絡(luò)中心度獲取的序列集合。

上述過(guò)程描述為NNS 算法，則利用NNS 獲取鄰域的算法步驟如下：

在圖2 中所示的鄰域節(jié)點(diǎn)預(yù)設(shè)長(zhǎng)度為k=5，在獲取N(1) 之后鄰域大小小于5，因此繼續(xù)獲取為N(2)，此時(shí)采用了鄰域節(jié)點(diǎn)排序?yàn)?的節(jié)點(diǎn)鄰域。為了體現(xiàn)這個(gè)過(guò)程，圖3 展示了一個(gè)k=8 的例子。其中在獲取N(1)后鄰域小于8，經(jīng)過(guò)NNS算法排序后依次獲取節(jié)點(diǎn)的2階鄰域。

Fig.3 Neighborhood node sort圖3 鄰域節(jié)點(diǎn)排序

3.3 CNN架構(gòu)

本文選取的用于特征學(xué)習(xí)的CNN 擁有兩層卷積，一個(gè)Flatten 層，為防止過(guò)擬合使用了DropOut 方法，其模型如圖4所示，其中第一層卷積，卷積窗口大小為k，步長(zhǎng)為k，輸出Dense 層使用的激活函數(shù)為Sigmoid。

在卷積層Conv1 用一組過(guò)濾器在節(jié)點(diǎn)屬性圖上進(jìn)行滑動(dòng)，提取圖上關(guān)鍵節(jié)點(diǎn)以及鄰域的特征。形式上，在向前傳遞期間，過(guò)濾器滑過(guò)節(jié)點(diǎn)及其鄰域，計(jì)算過(guò)濾器的每個(gè)值與輸入屬性圖之間的點(diǎn)積。過(guò)濾器的輸出計(jì)算如下：

Fig.4 CNN architecture圖4 卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

目標(biāo)函數(shù)經(jīng)過(guò)激活函數(shù)Sigmoid 之后得到下一層神經(jīng)元的激活值，其中a0表示的是輸入層中的神經(jīng)元的值，本文的a0=G(attr)是一個(gè)節(jié)點(diǎn)屬性矩陣，其長(zhǎng)度大小等于關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)w與其鄰域大小k的乘積，維度與節(jié)點(diǎn)的屬性值向量一致。其中l(wèi)表示行，m表示列，s表示Stride 即卷積窗口每次移動(dòng)的大小，l′a表示節(jié)點(diǎn)屬性向量的維度大小。

利用交叉熵?fù)p失函數(shù)來(lái)更新權(quán)重，其損失函數(shù)為：

其中，θ是模型的參數(shù)；yi是圖i的真實(shí)標(biāo)簽；y′i是輸出網(wǎng)絡(luò)模型的輸出。

另外為防止訓(xùn)練過(guò)程過(guò)早結(jié)束，使用RMSProp（root mean square prop）梯度下降算法，利用自適應(yīng)學(xué)習(xí)率對(duì)權(quán)重與偏向進(jìn)行更新，相關(guān)公式如下：

式（13）、式（14）中η為學(xué)習(xí)率，ε是防止分母為0的無(wú)窮小量，是參數(shù)θ的梯度平方求數(shù)學(xué)期望。

圖5 給出了一個(gè)原始訓(xùn)練集圖數(shù)據(jù)在模型中訓(xùn)練的流程圖。利用CNN訓(xùn)練數(shù)據(jù)獲取分類器：

初始化：加載原始圖集G，訓(xùn)練次數(shù)n，感受野大小k，代表節(jié)點(diǎn)個(gè)數(shù)w。

輸入：圖集G。

帶入式（10）y=σ(b+w×a0)訓(xùn)練模型并利用式（12）～式（15）更新權(quán)重

Fig.5 Data training specific process圖5 數(shù)據(jù)訓(xùn)練具體流程

選取帶有標(biāo)簽的數(shù)據(jù)集對(duì)模型進(jìn)行訓(xùn)練，圖5流程的關(guān)鍵步驟如下：

步驟1初始化訓(xùn)練次數(shù)Epoch，感受野大小k，w為圖集節(jié)點(diǎn)的均值。

步驟2輸入訓(xùn)練所使用的數(shù)據(jù)集G。

步驟3根據(jù)算法2獲取關(guān)鍵節(jié)點(diǎn)序列Vkey。

步驟4對(duì)于Vkey中的每一個(gè)節(jié)點(diǎn)，判斷其是否是原圖節(jié)點(diǎn)，若是則利用NNS算法獲取鄰域節(jié)點(diǎn)，并由這些節(jié)點(diǎn)生成子圖subgraph，否則添加一個(gè)星形圖作為子圖subgraph。

步驟5對(duì)每一個(gè)子圖進(jìn)行歸一化，獲得節(jié)點(diǎn)感受野G[N]，獲取子圖節(jié)點(diǎn)的屬性并reshape 屬性矩陣G(attr)大小為k×w與節(jié)點(diǎn)屬性長(zhǎng)度。

步驟6把G(attr)作為卷積神經(jīng)網(wǎng)絡(luò)模型的輸入對(duì)數(shù)據(jù)進(jìn)行訓(xùn)練，最后得到模型分類器。

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

為了驗(yàn)證改進(jìn)的GCN模型在圖上的實(shí)際分類結(jié)果，在多個(gè)基準(zhǔn)數(shù)據(jù)集上進(jìn)行了測(cè)試，并在本部分給出實(shí)驗(yàn)結(jié)果與分析。

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

（1）MUTAG[11]：MUTAG 是有188 個(gè)硝基化合物的數(shù)據(jù)集，其中化合物的分類表示該化合物是否對(duì)細(xì)菌具有誘變作用。

（2）PTC[23]：PTC 由344 種化合物組成，其中化合物的分類表示該化合物是否對(duì)老鼠有致癌性。

（3）BZR[24]：BZR 由405 個(gè)化學(xué)元素組成，分類表示是否對(duì)醫(yī)學(xué)中一種酶的抑制有活性。

（4）COX2[24]：COX2是有467個(gè)元素的數(shù)據(jù)集，其分類表示在體外對(duì)人體重組酶是否有抑制作用。

（5）D&D[25]：D&D 是有1 178 個(gè)蛋白質(zhì)結(jié)構(gòu)的數(shù)據(jù)集，其中化合物分類表示是否是酶。

表1 是各個(gè)數(shù)據(jù)集的基本數(shù)據(jù)，其中N_max表示數(shù)據(jù)集中拓?fù)鋱D的最大節(jié)點(diǎn)數(shù)，N_avg是數(shù)據(jù)集的平均節(jié)點(diǎn)數(shù)，G_num表示含有的圖數(shù)量。

Table 1 Dataset information表1 數(shù)據(jù)集信息

4.2 實(shí)驗(yàn)設(shè)置

（1）檢驗(yàn)使用DC（degree centrality）、CC（closeness centrality）、BC（betweenness centrality）算法對(duì)模型分類的識(shí)別率與穩(wěn)定性的影響程度，其中DC算法在原始GCN 模型方法PATCHY-SAN（patchy select assemble normalize）中所應(yīng)用。在MUTAG、PTC、BZR、COX2數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，以數(shù)據(jù)集的平均節(jié)點(diǎn)數(shù)為選取關(guān)鍵節(jié)點(diǎn)的閾值，采用5～50 間隔為5 的不同大小鄰域k進(jìn)行10 組實(shí)驗(yàn)，測(cè)試鄰域大小對(duì)算法模型識(shí)別率的影響，對(duì)比3 種算法的匹配精度，另外對(duì)實(shí)驗(yàn)結(jié)果數(shù)據(jù)求解方差，通過(guò)對(duì)數(shù)據(jù)波動(dòng)的程度分析來(lái)檢驗(yàn)算法的穩(wěn)定性。

（2）在實(shí)驗(yàn)結(jié)果分析的前提下獲取本文最優(yōu)算法，在MUTAG、PTC、COX2、BZR 以及D&D 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，每個(gè)數(shù)據(jù)集上進(jìn)行了10次實(shí)驗(yàn)，并與文獻(xiàn)[10,26-28]中算法進(jìn)行對(duì)比，驗(yàn)證本文最優(yōu)算法的識(shí)別率。

（3）為體現(xiàn)算法的性能效率時(shí)間耗費(fèi)代價(jià)優(yōu)劣程度，對(duì)各算法的時(shí)間復(fù)雜度進(jìn)行對(duì)比分析。

上述對(duì)比實(shí)驗(yàn)中所涉及文獻(xiàn)方法分為兩類：

（1）圖核算法：SP（shortest-path）核[27]、WL（Weisfeiler-Lehman）子樹(shù)核[28]。

（2）GCN方法：PATCHY-SAN[10]、LMFGCN（learning molecular fingerprints graph convolution networks）[26]。

其中算法SP與WL為經(jīng)典的圖核方法，PATCHY-SAN方法是本文改進(jìn)之前GCN模型方法，LMFGCN是一種把圖的節(jié)點(diǎn)和邊緣轉(zhuǎn)化為特征向量進(jìn)行端到端學(xué)習(xí)的GCN模型方法。

本文在實(shí)驗(yàn)中所選取的卷積參數(shù)第一層為16個(gè)卷積核，卷積窗口大小為k，步長(zhǎng)為k；第二層卷積為8 個(gè)卷積核，卷積窗口大小為10，步長(zhǎng)為1,全連接的激活函數(shù)為Relu，Dropout為0.5，輸出中添加的Dense層使用的激活函數(shù)為Sigmoid，Epoch的值為10。

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

4.3.1 DC、CC、BC對(duì)比與分析

圖6 展示了算法DC、CC、BC 對(duì)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)在不同鄰域大小下分類匹配的識(shí)別率對(duì)比。以折線圖的方式呈現(xiàn)更能直觀地展現(xiàn)在不同數(shù)據(jù)集上3 種方法對(duì)模型分類匹配的識(shí)別率影響程度。

數(shù)據(jù)集MUTAG中圖最大節(jié)點(diǎn)數(shù)28，平均節(jié)點(diǎn)數(shù)是18，圖6（a）是其在3 種算法下的識(shí)別率，從圖中可以看到CC 算法在鄰域k=25 可以達(dá)到93%的識(shí)別率，算法BC在鄰域k=20 識(shí)別率取得最大值，然而在鄰域大小取其他值時(shí)，二者的識(shí)別率沒(méi)有使用BC算法時(shí)高。圖6（b）是在數(shù)據(jù)集PTC上的實(shí)驗(yàn)，3種算法的識(shí)別率在k=45 時(shí)均取得最大值，CC與BC算法在10 組實(shí)驗(yàn)室中整體的識(shí)別率差距不大，算法DC 在k=15 與k=20 時(shí)的識(shí)別率較其他兩種算法較高。圖6（c）與圖6（d）分別是在數(shù)據(jù)集BZR與COX2上的實(shí)驗(yàn)結(jié)果，從圖中可以看出分類識(shí)別率達(dá)到90%以上。k=25 時(shí)DC 與BC 算法在兩個(gè)數(shù)據(jù)集上的識(shí)別率差距都比較大，BZR與COX2數(shù)據(jù)集中圖的最大節(jié)點(diǎn)數(shù)與平均節(jié)點(diǎn)數(shù)比較接近，這使得在k的一定閾值內(nèi)兩個(gè)數(shù)據(jù)集實(shí)驗(yàn)出來(lái)的識(shí)別率差距類似，然而當(dāng)k>30時(shí)，BC 算法在數(shù)據(jù)集BZR 上有較好的體現(xiàn)，對(duì)于COX2 則是DC 算法的匹配識(shí)別率更高，當(dāng)k≤20 時(shí)較之其他算法，BC 算法在兩個(gè)數(shù)據(jù)集上都具有較好的識(shí)別率。

整體從識(shí)別率折線圖的數(shù)據(jù)上看，4個(gè)數(shù)據(jù)集在k的個(gè)別取值均存在離散度較大的點(diǎn)，如果排除這些點(diǎn)，BC算法在各個(gè)數(shù)據(jù)集上的匹配識(shí)別率相對(duì)較高。

Fig.6 Classification and recognition rates of 3 algorithms圖6 3種算法的分類識(shí)別率

Fig.7 Variance of experimental data圖7 實(shí)驗(yàn)數(shù)據(jù)方差

圖7 是在數(shù)據(jù)集上3 種算法實(shí)驗(yàn)結(jié)果數(shù)據(jù)的方差。方差可以衡量一組數(shù)據(jù)波動(dòng)大小，方差越小，說(shuō)明這組數(shù)據(jù)的波動(dòng)性比較??；反之，則表明數(shù)據(jù)波動(dòng)性大。通過(guò)實(shí)驗(yàn)結(jié)果的數(shù)據(jù)方差可以確定在不同的k的取值下3種算法的穩(wěn)定性如何。圖7中從左到右依次是在4個(gè)數(shù)據(jù)集上3種算法實(shí)驗(yàn)結(jié)果方差。對(duì)于3 個(gè)數(shù)據(jù)集MUTAG、PTC 與COX2，DC 算法的實(shí)驗(yàn)結(jié)果數(shù)據(jù)方差最大，則此算法穩(wěn)定性在這些數(shù)據(jù)集上較弱。其次，對(duì)于數(shù)據(jù)集BZR，CC 算法的穩(wěn)定性比其他算法較弱。另外，在數(shù)據(jù)集PTC上，CC與BC算法的穩(wěn)定性相差不大，而3 種算法在數(shù)據(jù)集COX2上的穩(wěn)定性都相對(duì)較好，然而可以很明顯地看到黃色柱形圖在4 組方差數(shù)據(jù)中均處于最低，因此BC 算法的穩(wěn)定性最好。在3種算法的對(duì)比實(shí)驗(yàn)中，設(shè)置的k均超過(guò)了數(shù)據(jù)集的平均節(jié)點(diǎn)數(shù)，也就是存在補(bǔ)充節(jié)點(diǎn)。在接下來(lái)的實(shí)驗(yàn)中，為減少引入的節(jié)點(diǎn)所帶來(lái)的誤差，本文選取k=10 進(jìn)行接下來(lái)的實(shí)驗(yàn)。并且從算法的識(shí)別率與穩(wěn)定性分析來(lái)看，BC 算法在3 種算法中最優(yōu)，因此利用BC算法進(jìn)行接下來(lái)的實(shí)驗(yàn)。

由于DC 算法為原始GCN 模型方法PATCHY-SAN 所應(yīng)用，因此證明BC 算法在3 種算法中最優(yōu)的同時(shí)也證明了BC 算法相對(duì)于原始GCN 模型是有效的。

4.3.2 同類方法對(duì)比與分析

表2展示的是6種方法在5個(gè)數(shù)據(jù)集上的分類匹配的識(shí)別率。其中BCNNS是本文的引入了BC算法與NNS 節(jié)點(diǎn)排序算法的方法。而B(niǎo)C 是在沒(méi)有NNS算法的情況下在各個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)，讓BC 與BCNNS 進(jìn)行對(duì)比是為體現(xiàn)算法NNS 的有效性。在之前的對(duì)比實(shí)驗(yàn)中可以得出BC 算法在一定程度上提高了算法的識(shí)別率與穩(wěn)定性，添加了NNS 算法的BCNNS，其在識(shí)別率上較之BC算法有了進(jìn)一步的提升，并且在PTC數(shù)據(jù)集上有較高的提升，在其他數(shù)據(jù)集上的識(shí)別率也有一定程度的提升，因此NNS 算法的引入是有效的。另外，在數(shù)據(jù)集D&D 上的實(shí)驗(yàn)也是為了驗(yàn)證BC 算法較優(yōu)的實(shí)驗(yàn)結(jié)果。本文提出的BCNNS 算法在數(shù)據(jù)集PTC、COX2、BZR 及D&D 上都有較好的分類匹配識(shí)別率，其中在數(shù)據(jù)集PTC 與COX2 上的分類匹配識(shí)別率提升較大。相較于傳統(tǒng)的圖核SP與WL方法，BCNNS方法在大部分?jǐn)?shù)據(jù)集上都有較好的分類匹配率。比較其他兩種基于CNN的拓?fù)鋱D分類匹配算法，BCNNS 算法不僅在分類匹配識(shí)別率上有所提升，其在穩(wěn)定性方面也有優(yōu)勢(shì)（在10組實(shí)驗(yàn)中，BCNNS算法在數(shù)據(jù)集上的識(shí)別率上下波動(dòng)的范圍較?。谋? 中可以看到，對(duì)于數(shù)據(jù)集MUTAG，識(shí)別率峰值不如PATCHY-SAN 方法，原因是該數(shù)據(jù)集平均節(jié)點(diǎn)數(shù)較小，本文提出的鄰域節(jié)點(diǎn)排序?qū)ζ渫負(fù)浣Y(jié)構(gòu)數(shù)據(jù)的影響不是特別大，但是加入了BC 方法的BCNNS 算法在穩(wěn)定性上有所提升。因此，在大部分?jǐn)?shù)據(jù)集上，本文的BCNNS 算法優(yōu)于現(xiàn)有的圖卷積神經(jīng)網(wǎng)絡(luò)方法與圖核方法。

Table 2 Classification and recognition rates of 6 algorithms on 5 datasets表2 6種方法在5個(gè)數(shù)據(jù)集上的分類識(shí)別率 %

4.3.3 算法復(fù)雜度對(duì)比與分析

BCNNS 算法的各個(gè)模塊之間是相對(duì)獨(dú)立的，因此構(gòu)建感受野的過(guò)程是高效的并且可并行實(shí)現(xiàn)。設(shè)N'是圖的個(gè)數(shù)，k是感受野的大小，w是寬度，n為圖的頂點(diǎn)個(gè)數(shù)，m為邊的個(gè)數(shù)。則BCNNS算法在N'個(gè)圖上計(jì)算感受野的最壞時(shí)間復(fù)雜度為O(N′w(nm+nlb(n)+exp(k)))，其中O(nm)是BC算法在一個(gè)圖上的時(shí)間復(fù)雜度，O(nlb(n))為NNS 排序算法的時(shí)間復(fù)雜度，exp(k)是圖歸一化算法Nauty 計(jì)算有n個(gè)節(jié)點(diǎn)的最壞時(shí)間復(fù)雜度。

對(duì)于GCN模型算法LMFGCN與PATCHY-SAN，前者是解決分子指紋識(shí)別問(wèn)題，其中指紋的深度對(duì)應(yīng)鄰域大小w，固定指紋長(zhǎng)度對(duì)應(yīng)的是感受野大小k，則LMFGCN算法復(fù)雜度為O(N′w(Fk+F2))，其中F為節(jié)點(diǎn)與邊緣特征，當(dāng)節(jié)點(diǎn)與邊緣都存在一個(gè)特征時(shí)，F(xiàn)=n+m，此時(shí)復(fù)雜度達(dá)到O(N′w((n+m)k+(n+m)2))；PATCHY-SAN 算法的時(shí)間復(fù)雜度為O(N′w(f(n,m)+nlb(n)+exp(k)))，其在論文中使用的標(biāo)記函數(shù)為f(n,m)，算法復(fù)雜度最壞情況為O(n2)，當(dāng)m

5 結(jié)束語(yǔ)

本文提出的BCNNS算法具有以下特點(diǎn)：

（1）利用中介中心度對(duì)節(jié)點(diǎn)進(jìn)行度量，進(jìn)而使選取的關(guān)鍵節(jié)點(diǎn)更具有代表性，這種度量方式可以適用于任意的無(wú)向圖。

（2）能夠使獲取的鄰域節(jié)點(diǎn)最大限度地表示圖的局部特征，從而由局部到整體，使CNN有針對(duì)性地進(jìn)行學(xué)習(xí)。

通過(guò)實(shí)驗(yàn)證明了算法的有效性，但有待改進(jìn)的地方在于對(duì)鄰域進(jìn)行歸一化的過(guò)程中，會(huì)引入零點(diǎn)，雖然對(duì)算法的效率有所提升，但會(huì)存在冗余情況。因此下一步的工作將對(duì)這一過(guò)程進(jìn)行優(yōu)化，減少冗余的出現(xiàn)，進(jìn)一步提高匹配算法的識(shí)別率。