Abstract：Graph matching is widely used in reality, of which subgraph isomorphic matching is a research hotspot and has important scientific significance and practical value. Most existing subgraph isomorphism algorithms build constraints based on neighbor relationships, ignoring the local neighborhood information of nodes. In order to solve the problem, a subgraph isomorphism matching algorithm based on neighbor information aggregation was proposed. Firstly, the aggregated local neighborhood information of the nodes was obtained by importing the graph attributes and structure into the improved graph convolutional neural network to perform the representation learning of feature vector. Then, the efficiency of the algorithm was improved by optimizing the matching order according to the characteristics such as the label and degree of the graph. Finally, the Constraint Satisfaction Problem (CSP) model of subgraph isomorphism was established by combining the obtained feature vector and the optimized matching order with the search algorithm, and the model was solved by using the CSP backtracking algorithm. Experimental results show that the proposed algorithm significantly improves the solving efficiency of subgraph isomorphism compared with the traditional tree search algorithm and constraint solving algorithm.
徐周波, 李珍, 刘华东, 李萍. 基于邻居信息聚合的子图同构匹配算法[J]. 计算机应用, 2021, 41(1): 43-47.
XU Zhoubo, LI Zhen, LIU Huadong, LI Ping. Subgraph isomorphism matching algorithm based on neighbor information aggregation. Journal of Computer Applications, 2021, 41(1): 43-47.
[1] 于静, 刘燕兵, 张宇, 等. 大规模图数据匹配技术综述[J]. 计算机研究与发展,2015,52(2):391-409.(YU J,LIU Y B,ZHANG Y,et al. Survey on large-scale graph pattern matching[J]. Journal of Computer Research and Development,2015,52(2):391-409.) [2] MCGREGOR J J. Relational consistency algorithms and their application in finding subgraph and graph isomorphisms[J]. Information Sciences,1979,19(3):229-250. [3] CARLETTI V,FOGGIA P,SAGGESE A,et al. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2018,40(4):804-818. [4] ULLMANN J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM,1976,23(1):31-42. [5] CORDELLA L P,FOGGIA P,SANSONE C,et al. Performance evaluation of the VF graph matching algorithm[C]//Proceedings of the 10th International Conference on Image Analysis and Processing. Piscataway:IEEE,1999:1772-1777. [6] CORDELLA L P,FOGGIA P,SANSONE C,et al. A(sub)graph isomorphism algorithm for matching large graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2004, 26(10):1367-1372. [7] LARROSA J,VALIENTE G. Constraint satisfaction algorithms for graph pattern matching[J]. Mathematical Structures in Computer Science,2002,12(4):403-422. [8] SOLNON C. AllDifferent-based filtering for subgraph isomorphism[J]. Artificial Intelligence,2010,174(12/13):850-864. [9] AUDEMARD G,LECOUTRE C,SAMY-MODELIAR M,et al. Scoring-based neighborhood dominance for the subgraph isomorphism problem[C]//Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming, LNCS 8656. Cham:Springer,2014:125-141. [10] SHASHA D E,WANG J T L,GIUGNO R. Algorithmics and applications of tree and graph searching[C]//Proceedings of the 21th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York:ACM,2002:39-52. [11] HE H,SINGH A K. Closure-tree:an index structure for graph queries[C]//Proceedings of the 22nd International Conference on Data Engineering. Piscataway:IEEE,2006:38-38. [12] ZOU L,CHEN L,YU J X,et al. A novel spectral coding in a large graph database[C]//Proceedings of the 11th International Conference on Extending Database Technology. New York:ACM, 2008:181-192. [13] HAN W S,LEE J,LEE J H. TurboISO:towards ultrafast and robust subgraph isomorphism search in large graph data-bases[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York:ACM,2013:337-348. [14] DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Proceedings of the 30th Conference on Neural Information Processing Systems. Red Hook,NY:Curran Associates Inc.,2016:3844-3852. [15] KIPF T N,WELLING M. Semi-supervised classification with graph convolutional networks[EB/OL].[2020-04-08]. https://arxiv.org/pdf/1609.02907.pdf. [16] ZAMPELLI S, DEVILLE Y, SOLNON C. Solving subgraph isomorphism problems with constraint programming[J]. Constraints,2010,15(3):327-353. [17] KOTTHOFF L, MCCREESH C, SOLNON C. Portfolios of subgraph isomorphism algorithms[C]//Proceedings of the 10th Conference on Learning and Intelligent Optimization. Cham:Springer,2016:107-122.
2021, Vol. 41 
