宮月君 賀佳佳

摘要：為了進一步解決非精確圖匹配中，深度神經(jīng)網(wǎng)絡(luò)算法層級之間全連接造成的參數(shù)冗余所導(dǎo)致的數(shù)量級問題，本文提出利用改進的卷積神經(jīng)網(wǎng)絡(luò)實現(xiàn)非精確圖匹配算法。首先，利用建筑學(xué)與城市規(guī)劃學(xué)科中空間關(guān)系理論-空間句法的思路，對圖結(jié)構(gòu)數(shù)據(jù)進行描述，其次對數(shù)據(jù)進行處理。最后通過在圖上定義卷積運算，對圖節(jié)點的特征信息和結(jié)構(gòu)信息進行端到端的學(xué)習(xí)，實驗表明，該算法能夠高效的降低運算的時間，并且有效的提升準確率。

關(guān)鍵詞：非精確圖匹配;空間句法; 圖卷積神經(jīng)網(wǎng)絡(luò)

中圖分類號：TP393? ? ? ? 文獻標(biāo)識碼：A

文章編號：1009-3044（2019）18-0191-03

由于現(xiàn)實世界中無處不在的網(wǎng)絡(luò)，圖形分析近年來越來越受到關(guān)注。圖已被用于表示各個領(lǐng)域的信息，包括生物學(xué)，社會科學(xué)，和語言學(xué)[1]。將實體之間的交互作為圖形進行建模，使研究人員能夠系統(tǒng)地了解各種網(wǎng)絡(luò)系統(tǒng)。例如社會關(guān)系網(wǎng)絡(luò)，實體和實體之間可以用圖的形式來表示，在這種社會關(guān)系網(wǎng)絡(luò)中查詢特定關(guān)系的人或團體可以轉(zhuǎn)化為圖上指定節(jié)點和子圖匹配問題。在生物分析領(lǐng)域，通過圖匹配技術(shù)查詢具有已知性質(zhì)的蛋白質(zhì)結(jié)構(gòu)，可以快速有效地對未知性質(zhì)的蛋白質(zhì)與基因進行輔助分析，為研究生物組織的結(jié)構(gòu)及功能提供了技術(shù)手段。

根據(jù)調(diào)查以往的圖匹配研究成果，可分為精確和非精確圖匹配兩類思路[2]：前者計算過程比較復(fù)雜，大多歸類為NP難問題;后者則允許在非完全匹配情況下，實現(xiàn)快速分類識別的效果?，F(xiàn)有的非精確圖匹配方法有二分圖匹配[3]、基于BP神經(jīng)網(wǎng)絡(luò)的圖匹配[4]、以及基于圖嵌入的圖匹配[5]等諸多成果，其中，圖嵌入技術(shù)，通過學(xué)習(xí)圖中節(jié)點、邊或子圖的低維向量空間表示。如DeepWalk[6]、LINE[7]、SDNE[8]等方法在網(wǎng)絡(luò)表示學(xué)習(xí)領(lǐng)域取得了很大成功，然而，這些方法在計算上較為復(fù)雜并且在大規(guī)模圖上并不是最優(yōu)的，而GNN旨在解決這些問題，如 21世紀初，研究人員開發(fā)了圖嵌入算法，作為降維技術(shù)的一部分，他們將一組基于鄰域的N維點構(gòu)造一個相似度圖，然后將該圖的節(jié)點嵌入到d維向量空間中，其中，[d?N]。嵌入的思路是保證連接點在向量空間中彼此接近。拉普拉斯特征映射和局部線性嵌入是基于這一原理算法的例子，然而這種方法的主要問題是，其時間復(fù)雜度為[OV2].自2010年以來，關(guān)于圖嵌入的研究已轉(zhuǎn)向可擴展的圖嵌入技術(shù)，該技術(shù)利用了現(xiàn)實世界的稀疏性，圖嵌入技術(shù)的分類涵蓋因式分解[9]、隨機游走[10]和深度學(xué)習(xí)[11][12]。因此如何在保證精度的同時減少參數(shù)冗余，避免高維度數(shù)據(jù)所引發(fā)的應(yīng)用限制，是圖匹配問題研究優(yōu)化的關(guān)鍵所在。

因此本文借鑒建筑學(xué)與城市規(guī)劃學(xué)科中空間關(guān)系理論-空間句法的思路對圖中的每個節(jié)點構(gòu)造描述圖的拓撲特征的量化描述，并融合節(jié)點和邊領(lǐng)域?qū)傩缘确峭負涮卣鱗16]，利用統(tǒng)計的方法構(gòu)造分布于圖節(jié)點上的特征向量，并以此為橋梁將圖節(jié)點的特征信息與結(jié)構(gòu)信息在卷積神經(jīng)網(wǎng)絡(luò)中進行端到端的學(xué)習(xí)，進而實現(xiàn)非精確圖匹配。

本文的組織結(jié)構(gòu)圖如圖1所示：

1 數(shù)據(jù)集的特征空間表示

1.1 節(jié)點拓撲特征的表示

利用建筑學(xué)與城市規(guī)劃學(xué)科中的空間句法理論，構(gòu)造適合于非精確圖匹配的圖節(jié)點的結(jié)構(gòu)信息。本文采用的空間句法變量[14]有連接值、控制值、集成度、可理解度。因為連接值、控制值、平均深度值以及集成度都是在鄰接矩陣的基礎(chǔ)上得到的，因此維數(shù)與節(jié)點數(shù)相同。

1.2數(shù)據(jù)預(yù)處理

本文利用節(jié)點的特征對中心節(jié)點的鄰域進行隨機采樣，作為圖卷積網(wǎng)絡(luò)的輸入。

2 卷積神經(jīng)網(wǎng)絡(luò)的圖匹配算法

2.1算法描述

卷積神經(jīng)網(wǎng)絡(luò)（CNN，Convolutional Neural Network）屬于神經(jīng)網(wǎng)絡(luò)的一種[15]，是近年來高速發(fā)展的一類高效的機器學(xué)習(xí)算法。本文是在卷積神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上，結(jié)合建筑學(xué)與城市規(guī)劃學(xué)科中空間關(guān)系理論-空間句法，將圖數(shù)據(jù)進行特征表達，其次，將圖數(shù)據(jù)通過預(yù)處理。最后，將數(shù)據(jù)放入卷積神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練。

2.2改進的算法原理

該算法的原理步驟如下：

（1）數(shù)據(jù)的準備：首先將已有的xml格式的圖數(shù)據(jù)，利用空間句法的知識，進行節(jié)點的特征表示，其次，將特征矩陣進行數(shù)據(jù)預(yù)處理。

（2）卷積層：卷積層的作用是聚合傳遞過來的鄰居節(jié)點的特征[13]，然后在迭代的最后一層進行引入readout函數(shù)，該函數(shù)的作用是從局部特征映射到全局特征，來聚合節(jié)點特征獲得全局特征。

（3）激活函數(shù)：

卷積運算是一種線性運算，所以，卷積操作只能表達和模擬線性映射關(guān)系。本文使用ReLU函數(shù)[18]該函數(shù)的優(yōu)點主要有：當(dāng)[x<0]時，輸出恒為0，可以增加網(wǎng)絡(luò)稀疏性，提高泛化能力;當(dāng)[x>0]時，其梯度恒為1，解決了梯度飽和的問題，收斂會比較快;數(shù)學(xué)表達式簡練，便于運算。

（4）全連接層：本文的全連接層主要是將特征表示映射到輸入數(shù)據(jù)的標(biāo)記空間。

（5）softmax層：softmax可以理解為歸一化[19]，如待分類的文本一共有N個類別，那么，經(jīng)過softmax層的輸出就是一個N維的向量。

（1） 反向傳播算法

根據(jù)神經(jīng)網(wǎng)絡(luò)的實際輸出和期望輸出之間的誤差來決定網(wǎng)絡(luò)各層之間連接權(quán)值的調(diào)整方向和步長。從最后輸出層的誤差開始，利用鏈式求導(dǎo)法則計算損失函數(shù)對權(quán)值與偏置的偏導(dǎo)數(shù)，將一定比例的誤差分配給每個權(quán)值。誤差反向傳播之后，利用梯度下降學(xué)習(xí)算法對權(quán)值進行上下調(diào)整以減少誤差。

由于學(xué)習(xí)的圖函數(shù)具有非凸性，本文采用RMSProp[21]算法，該算法是在AdaGrad[17]算法的基礎(chǔ)上的改進，以在非凸設(shè)定條件下更好。

訓(xùn)練流程如圖2所示：

3 實驗結(jié)果與分析

本文的實驗平臺采用Intel（R）Xeon E5-2603 CPU處理器，主頻為1.7GHz（2處理器），內(nèi)存64GB，NVIDIA Quadro P2000顯示卡，Windows10操作系統(tǒng)以及以下軟件環(huán)境。

① Anconda3，Python版本：64位版本的Python 3.5。

② Visual Studio版本：VS2015 with Update 3。

③ CUDA版本：CUDA 8.0。

④ CuDnn版本：CuDnn 6.0

⑤ Tensorflow GPU

本文實驗數(shù)據(jù)來源為伯爾尼大學(xué)基于圖形模式識別和機器學(xué)習(xí)的IAM圖形數(shù)據(jù)庫的知識庫（IAM Graph DataBase Repository）[22]，所有的圖數(shù)據(jù)均使用XML文件格式進行記錄。本文從IAM圖形數(shù)據(jù)庫選擇AIDS和GREC數(shù)據(jù)庫進行實驗，GREC數(shù)據(jù)集是由表示建筑和電子圖紙符號的圖形組成。是根據(jù)每幅圖像的失真水平，應(yīng)用侵蝕、膨脹或其他形態(tài)學(xué)方法進行的操作處理，通過描繪線條并檢測交點和拐角，從而得到的去噪圖像中提取圖的結(jié)構(gòu)。AIDS數(shù)據(jù)集是由代表分子化合物的圖組成，包括活躍與不活躍兩個類別，通過將原子表示為節(jié)點而將共價鍵表示為邊緣，將分子直接轉(zhuǎn)換為圖的形式。XML文件中主要包含了node，edge，node-symbol，node-labels，node-charge以及edge-valence等相關(guān)屬性。根據(jù)當(dāng)前特征空間構(gòu)成，下表1給出了AIDS及GREC數(shù)據(jù)集的部分特征信息的情況，其中class-Num為類別數(shù)，maxnode-Num平均節(jié)點數(shù)，maxedge-Num為平均邊數(shù)，labels_Num為實驗選取的標(biāo)簽數(shù)：

在本文中的圖卷積神經(jīng)網(wǎng)絡(luò)圖匹配算法實驗中，為了使模型達到最優(yōu)，本文采用不同的參數(shù)對圖卷積神經(jīng)網(wǎng)絡(luò)進行調(diào)節(jié)。通過實驗，我們發(fā)現(xiàn)當(dāng)Dropout的參數(shù)設(shè)為0.8的時候，同時學(xué)習(xí)率調(diào)整為0.01時準確率能達到最高。本文還設(shè)置了不同的卷積層數(shù)，對準確率的結(jié)果產(chǎn)生了不一樣的影響，如圖3和圖4分別表示了不同的層數(shù)對性能的影響。從圖3和圖4中可以看出，準確率并不是隨著層數(shù)的增加而增加。

本文在分析圖卷積神經(jīng)網(wǎng)絡(luò)實驗中使用準確率（Accuracy_rate）指標(biāo)用來衡量圖匹配算法的性能，通過下圖4和圖5可以看出，隨著迭代次數(shù)的增加，準確率持續(xù)的上升，當(dāng)?shù)螖?shù)在180到200區(qū)間時，算法的準確率能達到平穩(wěn)。

4 結(jié)束語

本文使用了一種基于圖卷積神經(jīng)網(wǎng)絡(luò)圖匹配算法，在融合了圖的全局拓撲特征的基礎(chǔ)上，進行數(shù)據(jù)預(yù)處理。其次通過卷積運算將不同層的節(jié)點本身及其鄰居的特征進行聚合，最后通過反向傳播進行參數(shù)的更新進而完成分類任務(wù)。該算法有效地解決了全鏈接造成的參數(shù)冗余，以及在反向傳播中的梯度消失問題。同時避免了傳統(tǒng)算法所面臨的維數(shù)災(zāi)難問題。

經(jīng)實例驗證，本文算法以往研究方法的基礎(chǔ)上，均達到了有效的提升，對AIDS數(shù)據(jù)集上的識別準確率最高，達到了98.5%，從而證明了該算法的可行性和有效性。

參考文獻：

[1] 于靜， 劉燕兵， 張宇，等. 大規(guī)模圖數(shù)據(jù)匹配技術(shù)綜述[J].計算機研究與發(fā)展，2015， 52（2）：391-409.

[2] 嚴駿馳. 圖匹配問題的研究和算法設(shè)計[D].上海交通大學(xué)，2015.

[3] 鄧水光， 尹建偉， 李瑩，等. 基于二分圖匹配的語義Web服務(wù)發(fā)現(xiàn)方法[J].計算機學(xué)報，2008， 31（8）：1364-1375.

[4] 強保華， 陳凌， 余建橋，等.基于BP神經(jīng)網(wǎng)絡(luò)的屬性匹配方法研究[J].計算機科學(xué)，2006， 33（1）：249-251.

[5] Goyal P， Ferrara E. Graph Embedding Techniques， Applications， and Performance： A Survey[J]. Knowledge-Based Systems， 2018.

[6] Perozzi B， Al-Rfou R， Skiena S. DeepWalk：online learning of social representations[C]Acm Sigkdd International Conference on Knowledge Discovery & Data Mining， 2014.

[7] Tang J ， Qu M ， Wang M ， et al. LINE： Large-scale information network embedding[J]. 24th International Conference on World Wide Web， WWW 2015， 2015.

[8] Wang D， Peng C， Zhu W. Structural Deep Network Embedding[C]Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2016.

[9] Ahmed A， Shervashidze N， Narayanamurthy S， et al. Distributed large-scale natural graph factorization[C]// International Conference on World Wide Web. 2013.

[10] Fouss F， Pirotte A， Saerens M. A Novel Way of Computing Similarities between Nodes of a Graph， with Application to Collaborative Recommendation[C]// IEEE/WIC/ACM International Conference on Web Intelligence. 2005.

[11] Wang D， Peng C， Zhu W. Structural Deep Network Embedding[C]// Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2016.

[12] Cao S， Wei L， Xu Q. Deep neural networks for learning graph representations[C]// Thirtieth Aaai Conference on Artificial Intelligence. 2016.

[13] Hamilton W L ， Ying R ， Leskovec J . Inductive Representation Learning on Large Graphs[J]. 2017.

[14] 張愚， 王建國. 再論“空間句法”[J]. 建筑師， 2004（3）：33-44.

[15] 周飛燕，金林鵬，董軍.卷積神經(jīng)網(wǎng)絡(luò)研究綜述[J].計算機學(xué)報，2017， 40（6）：1229-1251.

[16] 李智杰，李昌華，劉欣.融合拓撲特征和領(lǐng)域特征的非精確圖匹配算法[J].計算機應(yīng)用與軟件，2015.

[17] Mehta N A， Rendell A， Varghese A， et al. CompAdaGrad： A Compressed， Complementary， Computationally-Efficient Adaptive Gradient Method[J]. 2016.

[18] Schmidthieber J. Nonparametric regression using deep neural networks with ReLU activation function[J]. 2018.

[19] Jang E， Gu S， Poole B. Categorical Reparameterization with Gumbel-Softmax[J]. 2016.

[20] Srivastava N， Hinton G， Krizhevsky A， et al. Dropout： a simple way to prevent neural networks from overfitting[J]. Journal of Machine Learning Research， 2014， 15（1）：1929-1958.

[21] Mukkamala M C， Hein M. Variants of RMSProp and Adagrad with Logarithmic Regret Bounds[J]. 2017.

[22] Riesen K， Bunke H. IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning[C]// Structural， Syntactic， & Statistical Pattern Recognition， Joint Iapr International Workshop， Sspr & Spr， Orlando， Usa， December. 2008.

[23] 李航.統(tǒng)計學(xué)習(xí)方法[M].北京：清華大學(xué)出版社，2012.

【通聯(lián)編輯：唐一東】