基于圖卷積神經網絡的圖匹配算法研究

宮月君 賀佳佳

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

關鍵詞：非精確圖匹配;空間句法; 圖卷積神經網絡

中圖分類號：TP393? ? ? ? 文獻標識碼：A

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

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

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

因此本文借鑒建筑學與城市規劃學科中空間關系理論-空間句法的思路對圖中的每個節點構造描述圖的拓撲特征的量化描述，并融合節點和邊領域屬性等非拓撲特征[16]，利用統計的方法構造分布于圖節點上的特征向量，并以此為橋梁將圖節點的特征信息與結構信息在卷積神經網絡中進行端到端的學習，進而實現非精確圖匹配。

本文的組織結構圖如圖1所示：

1 數據集的特征空間表示

1.1 節點拓撲特征的表示

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

1.2數據預處理

本文利用節點的特征對中心節點的鄰域進行隨機采樣，作為圖卷積網絡的輸入。

2 卷積神經網絡的圖匹配算法

2.1算法描述

卷積神經網絡（CNN，Convolutional Neural Network）屬于神經網絡的一種[15]，是近年來高速發展的一類高效的機器學習算法。本文是在卷積神經網絡的基礎上，結合建筑學與城市規劃學科中空間關系理論-空間句法，將圖數據進行特征表達，其次，將圖數據通過預處理。最后，將數據放入卷積神經網絡進行訓練。

2.2改進的算法原理

該算法的原理步驟如下：

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

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

（3）激活函數：

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

（4）全連接層：本文的全連接層主要是將特征表示映射到輸入數據的標記空間。

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

（1） 反向傳播算法

根據神經網絡的實際輸出和期望輸出之間的誤差來決定網絡各層之間連接權值的調整方向和步長。從最后輸出層的誤差開始，利用鏈式求導法則計算損失函數對權值與偏置的偏導數，將一定比例的誤差分配給每個權值。誤差反向傳播之后，利用梯度下降學習算法對權值進行上下調整以減少誤差。

由于學習的圖函數具有非凸性，本文采用RMSProp[21]算法，該算法是在AdaGrad[17]算法的基礎上的改進，以在非凸設定條件下更好。

訓練流程如圖2所示：

3 實驗結果與分析

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

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

② Visual Studio版本：VS2015 with Update 3。

③ CUDA版本：CUDA 8.0。

④ CuDnn版本：CuDnn 6.0

⑤ Tensorflow GPU

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

在本文中的圖卷積神經網絡圖匹配算法實驗中，為了使模型達到最優，本文采用不同的參數對圖卷積神經網絡進行調節。通過實驗，我們發現當Dropout的參數設為0.8的時候，同時學習率調整為0.01時準確率能達到最高。本文還設置了不同的卷積層數，對準確率的結果產生了不一樣的影響，如圖3和圖4分別表示了不同的層數對性能的影響。從圖3和圖4中可以看出，準確率并不是隨著層數的增加而增加。

本文在分析圖卷積神經網絡實驗中使用準確率（Accuracy_rate）指標用來衡量圖匹配算法的性能，通過下圖4和圖5可以看出，隨著迭代次數的增加，準確率持續的上升，當迭代次數在180到200區間時，算法的準確率能達到平穩。

4 結束語

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

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

參考文獻：

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

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

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

[4] 強保華， 陳凌， 余建橋，等.基于BP神經網絡的屬性匹配方法研究[J].計算機科學，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].計算機學報，2017， 40（6）：1229-1251.

[16] 李智杰，李昌華，劉欣.融合拓撲特征和領域特征的非精確圖匹配算法[J].計算機應用與軟件，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] 李航.統計學習方法[M].北京：清華大學出版社，2012.

【通聯編輯：唐一東】