基于邻居信息聚合的子图同构匹配算法

doi:10.11772/j.issn.1001-9081.2020060935

计算机应用 ›› 2021, Vol. 41 ›› Issue (1): 43-47.DOI: 10.11772/j.issn.1001-9081.2020060935

所属专题：第八届中国数据挖掘会议(CCDM 2020)

• 第八届中国数据挖掘会议(CCDM 2020) • 上一篇下一篇

基于邻居信息聚合的子图同构匹配算法

徐周波, 李珍, 刘华东, 李萍

广西可信软件重点实验室(桂林电子科技大学), 广西桂林 541004

收稿日期:2020-05-31 修回日期:2020-07-16 出版日期:2021-01-10 发布日期:2020-11-12
通讯作者: 刘华东
作者简介:徐周波(1976-),女,浙江奉化人,教授,博士,CCF高级会员,主要研究方向:符号计算、智能规划、约束求解;李珍(1995-),女,浙江温州人,硕士研究生,主要研究方向:图匹配、图数据挖掘;刘华东(1978-),男,江西瑞金人,讲师,硕士,主要研究方向:图数据表示;李萍(1996-),女,安徽六安人,硕士研究生,主要研究方向:图匹配、图数据挖掘。
基金资助:
国家自然科学基金资助项目（61762027）；广西自然科学基金资助项目（2017GXNSFAA198172）。

Subgraph isomorphism matching algorithm based on neighbor information aggregation

XU Zhoubo, LI Zhen, LIU Huadong, LI Ping

Guangxi Key Laboratory of Trusted Software(Guilin University of Electronic Technology), Guilin Guangxi 541004, China

Received:2020-05-31 Revised:2020-07-16 Online:2021-01-10 Published:2020-11-12
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61762027), the Natural Science Foundation of Guangxi (2017GXNSFAA198172).

摘要/Abstract

摘要： 图匹配在现实中被广泛运用，而子图同构匹配是其中的研究热点，具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件，而忽略了节点的局部邻域信息。对此，提出了一种基于邻居信息聚合的子图同构匹配算法。首先，将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习，从而得到聚合后的节点局部邻域信息；然后，根据图的标签、度等特征对匹配顺序进行优化，以提高算法的效率；最后，将得到的特征向量和优化的匹配顺序与搜索算法相结合，建立子图同构的约束满足问题（CSP）模型，并结合CSP回溯算法对模型进行求解。实验结果表明，与经典的树搜索算法和约束求解算法相比，该算法可以有效地提高子图同构的求解效率。

关键词: 子图同构, 约束满足问题, 图卷积神经网络, 信息聚合, 图匹配

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.

Key words: subgraph isomorphism, Constraint Satisfaction Problem (CSP), graph convolutional neural network, information aggregation, graph matching

中图分类号:

TP391

徐周波, 李珍, 刘华东, 李萍. 基于邻居信息聚合的子图同构匹配算法[J]. 计算机应用, 2021, 41(1): 43-47.

XU Zhoubo, LI Zhen, LIU Huadong, LI Ping. Subgraph isomorphism matching algorithm based on neighbor information aggregation[J]. 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.

基于邻居信息聚合的子图同构匹配算法

Subgraph isomorphism matching algorithm based on neighbor information aggregation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	牟长宁, 王海鹏, 周丕宇, 侯鑫行. 基于图卷积神经网络的串联质谱从头测序[J]. 计算机应用, 2021, 41(9): 2773-2779.
[2]	车冰倩, 周栋. 融合网络结构信息及文本内容的标签推荐方法[J]. 计算机应用, 2021, 41(4): 976-983.
[3]	付颖, 王红玲, 王中卿. 基于宏观篇章结构的科技论文摘要模型[J]. 计算机应用, 2021, 41(10): 2864-2870.
[4]	赖自成, 张玉萍, 马燕. 基于门控图卷积神经网络的有机化学反应预测[J]. 计算机应用, 2021, 41(10): 3070-3074.
[5]	温静, 李智宏. 基于带squeeze-and-excitation模块的ResNeXt的单目图像深度估计方法[J]. 计算机应用, 2021, 41(1): 215-219.
[6]	易东义, 邓根强, 董超雄, 祝苗苗, 吕周平, 朱岁松. 基于图卷积神经网络的医保欺诈检测算法[J]. 计算机应用, 2020, 40(5): 1272-1277.
[7]	关皓元, 朱斌, 李冠宇, 蔡永嘉. 基于资源描述框架图切分与顶点选择性的高效子图匹配方法[J]. 计算机应用, 2019, 39(2): 360-369.
[8]	李飞龙, 赵春艳, 范如梦. 基于禁忌搜索算法求解随机约束满足问题[J]. 计算机应用, 2019, 39(12): 3584-3589.
[9]	施炜杰, 董一鸿, 王雄, 潘剑飞. 基于索引的子图查询技术研究进展[J]. 计算机应用, 2019, 39(1): 39-45.
[10]	李龙洋, 董一鸿, 施炜杰, 潘剑飞. SQM:基于Spark的大规模单图上的子图匹配算法[J]. 计算机应用, 2019, 39(1): 46-50.
[11]	关皓元, 朱斌, 李冠宇, 赵玲. 基于RDF图结构切分的高效子图匹配方法[J]. 计算机应用, 2018, 38(7): 1898-1904.
[12]	陈辉, 蒋圭峰, 姜桂圆, 武继刚. 基于海量公交轨迹数据挖掘的地图匹配算法[J]. 计算机应用, 2018, 38(7): 1923-1928.
[13]	郑林江, 刘旭, 易兵. 考虑时空特性的动态权重实时地图匹配算法[J]. 计算机应用, 2017, 37(8): 2381-2386.
[14]	闫华, 高黎, 刘国勇, 王红旗. 基于多时间窗的油料保障模型[J]. 计算机应用, 2015, 35(7): 2096-2100.
[15]	韩亮姜孜锜蒲秀娟. 光学4f系统灰度误差补偿的实现[J]. 计算机应用, 2013, 33(07): 1973-1975.