用于非精確圖匹配的改進GCN模型*

李昌華，崔李揚，李智杰

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

1 引言

圖是一種豐富的表示形式，可以描述現實世界中復雜的結構數據，如化合物集合、蛋白質結構、社交網絡等。隨著深度學習技術應用于許多領域，并且較傳統方法有明顯優勢，利用神經網絡對拓撲結構特征的學習和查詢為高效的圖匹配算法帶來了應用需求。

圖匹配方法可以分為兩類，精確圖匹配和非精確圖匹配。精確圖匹配要求被匹配的對象之間要嚴格對應[1]。然而，這種匹配算法的強約束條件對于實際應用來說過于嚴格，并被證明是NP完全問題。相對于精確圖匹配，非精確圖匹配方法允許在相似模型下有一定的容錯，即使被匹配的圖在結構上有一定的差異，也能進行匹配，這使得非精確圖匹配受到研究者們的重視。雖然目前已經有很多非精確圖匹配問題的研究，但是現有算法的識別率、有效性仍不能滿足要求。

卷積神經網絡（convolutional neural networks，CNN）作為一種深度監督學習框架，在計算機視覺[2]、語音識別[3]、博弈[4]等領域都表現出了優異的性能。對于圖像、視頻和聲音等數據，它們都具有固定大小的鄰域，因此CNN 中的卷積、池化等操作是有意義的。然而，圖是一種結構化數據類型，沒有固定的鄰域，傳統的CNN不能直接作用于圖。而為了將CNN應用于圖結構數據，研究者們提出了多種方法[5-9]。這些方法可以分為兩類：基于空間的方法和基于譜的方法。基于空間的方法是利用圖的空間鄰域信息進行卷積運算。基于譜的方法通常使用拉普拉斯變換對結構圖進行變換，然后使用特征向量作為卷積算子。文獻[10]提出了一個學習圖的CNN 框架，通過使用圖標記程序來構建一個感受野。上述方法雖然在一定程度上解決了將CNN 應用于圖的問題，但是依然存在對圖結構本身挖掘不夠充分的問題。

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

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

2 GCN的相關工作

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

文獻[10]提出了一種獲取圖數據的局部接受域并應用于CNN 的方法，該方法可以得到一個標準CNN可以處理的一維數據單元，文獻[18]是在該方法的基礎上添加了一個預處理卷積層，文獻[19]是在卷積之前對數據進行了排序，這些方法雖然在一定程度上優化了文獻[10]中的方法，然而它們都局限在對卷積的處理，并沒有考慮到把拓撲結構映射到網格結構的過程中對數據的最優表示，因此無法保證獲取的節點鄰域能最大化表示節點的領域特征。本文的工作充分利用其優點，并且在關鍵節點選擇與獲取節點鄰域上進行改進，使節點鄰域能最大化表示拓撲圖結構，進而利用改進的GCN 模型處理非精確圖匹配問題。

3 改進的GCN模型

本章描述了用于圖匹配的改進圖卷積神經網絡模型。首先，圖的分類匹配問題可以歸結如下。

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

因此把CNN 應用于拓撲結構，首先需要對拓撲結構數據進行處理，如何保證選取的關鍵節點具有代表性，以及在獲取節點鄰域過程中保證鄰域節點能較完整表示圖的結構是一些亟待解決的關鍵問題。為解決這些問題，本文提出一種新的算法模型，如圖2 所示。首先使用三種求取網絡節點中心度的方法對節點進行度量并排序，選取關鍵節點，然后利用中心度對鄰域節點排序并依次獲取節點鄰域。模型主要包括：

（1）代表節點選擇：通過SNA中三種網絡節點中心度度量方式計算節點中心度，獲取節點有序序列，通過對比來選取最優代表節點。

（2）鄰域節點排序（neighbour node sort，NNS）：對鄰域節點進行中心度排序，按中心度大小依次進行鄰域節點的選取。

（3）鄰域節點歸一化：把節點鄰域規范化為網格結構，作為卷積神經網絡的輸入。

（4）特征學習：歸一化的圖結構數據經過兩層卷積以及全連接層進行特征學習。

在圖2的模型結構中，其輸入是數據集MUTAG[20]中的任意一個圖，首先節點經過中心度大小排序選出代表節點，圖示給出三個代表節點的例子，其次經過鄰域節點排序，獲得節點鄰域，歸一化之后獲得網格圖，作為卷積神經網絡的輸入。

3.1 代表節點選擇

Fig.2 Improved model structure圖2 改進的模型結構

本文使用三種網絡節點中心度度量方法獲取代表節點。中心度（centrality）[11]是SNA 中常用的一個概念，用以表達社交網絡中一個節點在整個網絡中所在中心的程度，這個程度用數字來表示就被稱作中心度。本文使用的測定節點中心度的方法有度中心度（degree centrality，DC）[11]、接近中心度（closeness centrality，CC）[21]、中介中心度（betweenness centrality，BC）[22]。

（1）DC：節點v的度，對于無向圖來說是連接該節點的邊數，對于有向圖，存在出度與入度。出度為從節點v出發的有向邊，入度為指向節點v的有向邊。本文主要討論無向圖，因此節點v的度中心度：

（2）CC：如果一個節點與許多其他節點接近，那么該節點處于網絡中心位置，這種度量方式稱之為接近中心度：

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

（3）BC：中介中心度是計算經過一個點的最短路徑的數量。經過一個點的最短路徑數量越多，就說明它的中介中心度越高。中介中心度表示為：

其中，σst(v)表示經過節點v，s→t的最短路徑數，σst表示s→t的最短路徑數。

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

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

3.2 鄰域節點排序

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

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

其中，j是圖的節點數目并且j∈R，j

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

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

在上述式子中，C(v)是節點中心度函數，sort(?)是按照節點中心度對節點進行排序，SN(v)是通過網絡中心度獲取的序列集合。

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

在圖2 中所示的鄰域節點預設長度為k=5，在獲取N(1) 之后鄰域大小小于5，因此繼續獲取為N(2)，此時采用了鄰域節點排序為1的節點鄰域。為了體現這個過程，圖3 展示了一個k=8 的例子。其中在獲取N(1)后鄰域小于8，經過NNS算法排序后依次獲取節點的2階鄰域。

Fig.3 Neighborhood node sort圖3 鄰域節點排序

3.3 CNN架構

本文選取的用于特征學習的CNN 擁有兩層卷積，一個Flatten 層，為防止過擬合使用了DropOut 方法，其模型如圖4所示，其中第一層卷積，卷積窗口大小為k，步長為k，輸出Dense 層使用的激活函數為Sigmoid。

在卷積層Conv1 用一組過濾器在節點屬性圖上進行滑動，提取圖上關鍵節點以及鄰域的特征。形式上，在向前傳遞期間，過濾器滑過節點及其鄰域，計算過濾器的每個值與輸入屬性圖之間的點積。過濾器的輸出計算如下：

Fig.4 CNN architecture圖4 卷積神經網絡結構

目標函數經過激活函數Sigmoid 之后得到下一層神經元的激活值，其中a0表示的是輸入層中的神經元的值，本文的a0=G(attr)是一個節點屬性矩陣，其長度大小等于關鍵節點個數w與其鄰域大小k的乘積，維度與節點的屬性值向量一致。其中l表示行，m表示列，s表示Stride 即卷積窗口每次移動的大小，l′a表示節點屬性向量的維度大小。

利用交叉熵損失函數來更新權重，其損失函數為：

其中，θ是模型的參數；yi是圖i的真實標簽；y′i是輸出網絡模型的輸出。

另外為防止訓練過程過早結束，使用RMSProp（root mean square prop）梯度下降算法，利用自適應學習率對權重與偏向進行更新，相關公式如下：

式（13）、式（14）中η為學習率，ε是防止分母為0的無窮小量，是參數θ的梯度平方求數學期望。

圖5 給出了一個原始訓練集圖數據在模型中訓練的流程圖。利用CNN訓練數據獲取分類器：

初始化：加載原始圖集G，訓練次數n，感受野大小k，代表節點個數w。

輸入：圖集G。

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

Fig.5 Data training specific process圖5 數據訓練具體流程

選取帶有標簽的數據集對模型進行訓練，圖5流程的關鍵步驟如下：

步驟1初始化訓練次數Epoch，感受野大小k，w為圖集節點的均值。

步驟2輸入訓練所使用的數據集G。

步驟3根據算法2獲取關鍵節點序列Vkey。

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

步驟5對每一個子圖進行歸一化，獲得節點感受野G[N]，獲取子圖節點的屬性并reshape 屬性矩陣G(attr)大小為k×w與節點屬性長度。

步驟6把G(attr)作為卷積神經網絡模型的輸入對數據進行訓練，最后得到模型分類器。

4 實驗結果

為了驗證改進的GCN模型在圖上的實際分類結果，在多個基準數據集上進行了測試，并在本部分給出實驗結果與分析。

4.1 數據集

（1）MUTAG[11]：MUTAG 是有188 個硝基化合物的數據集，其中化合物的分類表示該化合物是否對細菌具有誘變作用。

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

（3）BZR[24]：BZR 由405 個化學元素組成，分類表示是否對醫學中一種酶的抑制有活性。

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

（5）D&D[25]：D&D 是有1 178 個蛋白質結構的數據集，其中化合物分類表示是否是酶。

表1 是各個數據集的基本數據，其中N_max表示數據集中拓撲圖的最大節點數，N_avg是數據集的平均節點數，G_num表示含有的圖數量。

Table 1 Dataset information表1 數據集信息

4.2 實驗設置

（1）檢驗使用DC（degree centrality）、CC（closeness centrality）、BC（betweenness centrality）算法對模型分類的識別率與穩定性的影響程度，其中DC算法在原始GCN 模型方法PATCHY-SAN（patchy select assemble normalize）中所應用。在MUTAG、PTC、BZR、COX2數據集上進行實驗，以數據集的平均節點數為選取關鍵節點的閾值，采用5～50 間隔為5 的不同大小鄰域k進行10 組實驗，測試鄰域大小對算法模型識別率的影響，對比3 種算法的匹配精度，另外對實驗結果數據求解方差，通過對數據波動的程度分析來檢驗算法的穩定性。

（2）在實驗結果分析的前提下獲取本文最優算法，在MUTAG、PTC、COX2、BZR 以及D&D 數據集上進行實驗，每個數據集上進行了10次實驗，并與文獻[10,26-28]中算法進行對比，驗證本文最優算法的識別率。

（3）為體現算法的性能效率時間耗費代價優劣程度，對各算法的時間復雜度進行對比分析。

上述對比實驗中所涉及文獻方法分為兩類：

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

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

其中算法SP與WL為經典的圖核方法，PATCHY-SAN方法是本文改進之前GCN模型方法，LMFGCN是一種把圖的節點和邊緣轉化為特征向量進行端到端學習的GCN模型方法。

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

4.3 實驗結果

4.3.1 DC、CC、BC對比與分析

圖6 展示了算法DC、CC、BC 對拓撲結構數據在不同鄰域大小下分類匹配的識別率對比。以折線圖的方式呈現更能直觀地展現在不同數據集上3 種方法對模型分類匹配的識別率影響程度。

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

整體從識別率折線圖的數據上看，4個數據集在k的個別取值均存在離散度較大的點，如果排除這些點，BC算法在各個數據集上的匹配識別率相對較高。

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

Fig.7 Variance of experimental data圖7 實驗數據方差

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

由于DC 算法為原始GCN 模型方法PATCHY-SAN 所應用，因此證明BC 算法在3 種算法中最優的同時也證明了BC 算法相對于原始GCN 模型是有效的。

4.3.2 同類方法對比與分析

表2展示的是6種方法在5個數據集上的分類匹配的識別率。其中BCNNS是本文的引入了BC算法與NNS 節點排序算法的方法。而BC 是在沒有NNS算法的情況下在各個數據集上的實驗，讓BC 與BCNNS 進行對比是為體現算法NNS 的有效性。在之前的對比實驗中可以得出BC 算法在一定程度上提高了算法的識別率與穩定性，添加了NNS 算法的BCNNS，其在識別率上較之BC算法有了進一步的提升，并且在PTC數據集上有較高的提升，在其他數據集上的識別率也有一定程度的提升，因此NNS 算法的引入是有效的。另外，在數據集D&D 上的實驗也是為了驗證BC 算法較優的實驗結果。本文提出的BCNNS 算法在數據集PTC、COX2、BZR 及D&D 上都有較好的分類匹配識別率，其中在數據集PTC 與COX2 上的分類匹配識別率提升較大。相較于傳統的圖核SP與WL方法，BCNNS方法在大部分數據集上都有較好的分類匹配率。比較其他兩種基于CNN的拓撲圖分類匹配算法，BCNNS 算法不僅在分類匹配識別率上有所提升，其在穩定性方面也有優勢（在10組實驗中，BCNNS算法在數據集上的識別率上下波動的范圍較小）。從表2 中可以看到，對于數據集MUTAG，識別率峰值不如PATCHY-SAN 方法，原因是該數據集平均節點數較小，本文提出的鄰域節點排序對其拓撲結構數據的影響不是特別大，但是加入了BC 方法的BCNNS 算法在穩定性上有所提升。因此，在大部分數據集上，本文的BCNNS 算法優于現有的圖卷積神經網絡方法與圖核方法。

Table 2 Classification and recognition rates of 6 algorithms on 5 datasets表2 6種方法在5個數據集上的分類識別率 %

4.3.3 算法復雜度對比與分析

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

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

5 結束語

本文提出的BCNNS算法具有以下特點：

（1）利用中介中心度對節點進行度量，進而使選取的關鍵節點更具有代表性，這種度量方式可以適用于任意的無向圖。

（2）能夠使獲取的鄰域節點最大限度地表示圖的局部特征，從而由局部到整體，使CNN有針對性地進行學習。

通過實驗證明了算法的有效性，但有待改進的地方在于對鄰域進行歸一化的過程中，會引入零點，雖然對算法的效率有所提升，但會存在冗余情況。因此下一步的工作將對這一過程進行優化，減少冗余的出現，進一步提高匹配算法的識別率。