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

宮月君 賀佳佳

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

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

中圖分類號(hào)：TP393? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）18-0191-03

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

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

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

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

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

1.1 節(jié)點(diǎn)拓?fù)涮卣鞯谋硎?/p>

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

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

本文利用節(jié)點(diǎn)的特征對(duì)中心節(jié)點(diǎn)的鄰域進(jìn)行隨機(jī)采樣，作為圖卷積網(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ā)展的一類高效的機(jī)器學(xué)習(xí)算法。本文是在卷積神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上，結(jié)合建筑學(xué)與城市規(guī)劃學(xué)科中空間關(guān)系理論-空間句法，將圖數(shù)據(jù)進(jìn)行特征表達(dá)，其次，將圖數(shù)據(jù)通過預(yù)處理。最后，將數(shù)據(jù)放入卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練。

2.2改進(jìn)的算法原理

該算法的原理步驟如下：

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

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

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

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

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

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

（1） 反向傳播算法

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

本文的實(shí)驗(yàn)平臺(tái)采用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í)驗(yàn)數(shù)據(jù)來源為伯爾尼大學(xué)基于圖形模式識(shí)別和機(jī)器學(xué)習(xí)的IAM圖形數(shù)據(jù)庫的知識(shí)庫（IAM Graph DataBase Repository）[22]，所有的圖數(shù)據(jù)均使用XML文件格式進(jìn)行記錄。本文從IAM圖形數(shù)據(jù)庫選擇AIDS和GREC數(shù)據(jù)庫進(jìn)行實(shí)驗(yàn)，GREC數(shù)據(jù)集是由表示建筑和電子圖紙符號(hào)的圖形組成。是根據(jù)每幅圖像的失真水平，應(yīng)用侵蝕、膨脹或其他形態(tài)學(xué)方法進(jìn)行的操作處理，通過描繪線條并檢測(cè)交點(diǎn)和拐角，從而得到的去噪圖像中提取圖的結(jié)構(gòu)。AIDS數(shù)據(jù)集是由代表分子化合物的圖組成，包括活躍與不活躍兩個(gè)類別，通過將原子表示為節(jié)點(diǎn)而將共價(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é)點(diǎn)數(shù)，maxedge-Num為平均邊數(shù)，labels_Num為實(shí)驗(yàn)選取的標(biāo)簽數(shù)：

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

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

4 結(jié)束語

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

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

參考文獻(xiàn)：

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

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

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

[4] 強(qiáng)保華， 陳凌， 余建橋，等.基于BP神經(jīng)網(wǎng)絡(luò)的屬性匹配方法研究[J].計(jì)算機(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].計(jì)算機(jī)學(xué)報(bào)，2017， 40（6）：1229-1251.

[16] 李智杰，李昌華，劉欣.融合拓?fù)涮卣骱皖I(lǐng)域特征的非精確圖匹配算法[J].計(jì)算機(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)計(jì)學(xué)習(xí)方法[M].北京：清華大學(xué)出版社，2012.

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